Контрольные вопросы

1. Перечислите методы простой сортировки. В чем заключается их алгоритм.

2. Перечислите алгоритмы улучшенной сортировки.

3. В чем заключается способ сортировки методом Хоора.

4. В чем заключается способ сортировки методом Флойда.

5. В чем заключается способ сортировки методом Шелла.

Статистическое и динамическое распределение памяти. Динамические структуры данных.

Цель работы: получить практические навыки использования указателей и динамических структур данных с помощью средств Turbo Pascal.

СТАТИЧЕСКИЕ И ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

Как правило, при разработке простейших программ используются статические данные и статические переменные. Такие переменные объявляются в начале программы (в разделе описаний) и существуют до завершения ее работы. Соответственно, память для содержания этих переменных выделяется при запуске программы и остается занятой все время, пока программа работает.

Очевидно, что это не самый рациональный способ использования памяти компьютера. Например, некоторая переменная может использоваться только однажды в единственном операторе обширной программы, однако память, выделенная под эту переменную, остается занята все время, пока работает программа. В языке программирования Turbo Pascal можно сделать так, что бы память для такой переменной выделялась в момент, когда переменная начинает использоваться, и освобождалась сразу же по завершении ее использования, чтобы эту память тут же можно было выделить для иных данных. Специально для этой цели в Turbo Pascal введено понятие динамической памяти. Динамическая память, известная также как куча, рассматривается в Turbo Pascal как массив байтов.

Динамическая память (или куча), имеющая объем приблизительно 300000 байт, что позволяет обрабатывать более обширные структуры данных. При использовании (статической) памяти, можно создать массив из 20000 элементов типа LongInt, а используя динамической памяти можно обработать гораздо больший массив.

При динамическом размещении к данным не удастся обращаться по именам, как к статическим данным, и количество и тип динамически размещаемых данных заранее неизвестны. Динамическая память выделяется для данных (и освобождается) в ходе работы программы. Для управления динамической памятью Turbo Pascal предоставляет гибкое средство – указатели.

УКАЗАТЕЛИ

Оперативная память компьютера — это множество ячеек, каждая из которых предназначена для хранения одного байта информации, и каждая имеет собственный адрес, по которому к этой ячейке можно обратиться. Указатель это переменная, объявленная в разделе описаний программы, значение которой и представляет собой адрес одного байта памяти.

Указатели, используемые в Turbo Pascal, бывают типизированные и нетипизированные. Нетипизированный указатель — это переменная, содержащая адрес данных произвольного типа, а типизированный указатель содержит адрес данных, тип которых оговаривается при объявлении данного указателя.

Нетипизированные указатели объявляются следующим образом:

Var

pp:pointer;

где pointer — стандартный тип данных;

рр — переменная, содержащая адрес памяти, по которому могут храниться данные произвольного типа.

Типизированные указатели объявления в программах следующим образом:

Var

px:^char;

py:^integer;

В этом примере описаны два типизированных указателя: px и py. Значения этих переменных представляют собой адреса в оперативной памяти, по которым содержатся данные типа Char и Integer соответственно.

Из примера видно, что описание типизированного указателя отличается от описания статической переменной того же типа только тем, что в случае указателя перед типом присутствует символ «^».

Следовательно, когда требуется воспользоваться динамической памятью, в разделе описаний объявляется не сама переменная, а указатель (или ссылка) на нее. В этом случае указатель представляет собой обычную переменную, а переменная, на которую он ссылается, — динамическую. При этом, если в выражении должен присутствовать указатель, используется идентификатор, объявленный в разделе описаний. Если же, в выражении должна фигурировать динамическая переменная, на которую ссылается указатель, идентификатор указателя дополняется символом «^». Такое действие называется разыменованием. Например, РХ^.

Пример описания указателей:

Type

DataPointer = ^Date;

Date=record

year : 1900..2100;

month : 1..12;

day : 1..31;

next : DatePointer

end;

Var

pd : DatePointer;

Здесь объявлен тип DatePointer, представляющий собой указатель на тип Date, который описывает запись. Обратит внимание, что тип DatePointer описан до типа Date, на который он ссылается. В то же время одно из полей записи Date принадлежит типу DatePointer. В целом, в Turbo Pascal не допускается ссылаться на еще не описанные типы, однако в данном случае (достаточно частом, когда приходится иметь дело с указателями) как ни располагай описания, все равно ссылки на еще не описанный тип не избежать. Поэтому единственное исключение сделано для указателей: тип указателя на динамические данные может быть объявлен до описания самих данных.

Операция присваивания, к типизированным указателям, допустима только для указателей, ссылающихся на данные одного типа.

Предположим, в программе объявлены указатели:

Var

px,py:^char;

pz:^integer;

В этом случае операция присваивания допустима для указателей рх и ру:

рх := ру;

Однако совершенно не допустимыми окажутся операторы:

рх := ря; или рz := ру;

Нетипизированный указатель может присутствовать в операторе присваивания в паре с любым типизированным указателем. Например, в программе объявлены указатели:

Var

px:^char;

py:^integer;

pz:pointer;

Для этих переменных допустимы операторы присваивания

рх := рz; ру := рz;

рz := ру; рz := рх;

Нетрудно заметить, что нетипизированные указатели — очень удобное средство преобразования типов данных.

СОСТОЯНИЯ УКАЗАТЕЛЯ

Для указателя, после того как он объявлен в разделе описания переменных, возможны три состояния. Указатель может содержать адрес некоторой переменной, «пустой» адрес NIL или иметь неопределенное состояние.

Если требуется, чтобы указатель никуда не указывал, ему присваивается специальное значение Nil. Неопределенное стояние указатель имеет сразу после начала работы программы (до того как указателю будет присвоен какой-нибудь адрес в памяти или значение Nil), либо после освобождения памяти, на которую данный указатель ссылается. Указатель, который никуда не указывает, это ссылка на область памяти, в которой никакая информация никогда не размещается. Значение Nil — это константа, которую можно присвоить любому указателю.

ВЫДЕЛЕНИЕ И ОСВОБОЖДЕНИЕ ДИНАМИЧЕСКОЙ ПАМЯТИ

ДЛЯ ТИПИЗИРОВАННЫХ УКАЗАТЕЛЕЙ

Для динамически размещаемых переменных, на которые ссылаются типизированные указатели, память выделяется и освобождается с помощью процедур New и Dispose соответственно. Вот как схематически может выглядеть программа, в которой используются указатели на переменные, размещаемые в динамической памяти:

Var

px, py : ^char;

pz : ^integer;

Begin

New(px);

New(py);

New(pz);

px^ := ‘A’;

py^ := ‘7’;

pz^ := 999;

…

Dispose(px);

Dispose(py);

Dispose(pz);

…

End.

В этой программе в разделе описания переменных объявлены три типизированных указателя. Затем в теле программы под динамические переменные, на которые ссылаются эти указатели, с помощью процедуры New выделена динамическая память. После этого динамическим переменным можно присваивать подходящие по типу значения и использовать их в различных выражениях. Когда надобность в переменных рх, ру и pz отпадает, выделенная для них память освобождается с помощью процедуры Dispose.

ДЛЯ НЕТИПИЗИРОВАННЫХ УКАЗАТЕЛЕЙ

Для динамически размещаемых переменных, на которые ссылаются нетипизированные указатели, память выделяется и освобождается с помощью процедур GetMem и FreeMem соответственно. Вот как схематически может выглядеть программа, в которой используются нетипизированные указатели:

Var

px, py : pointer;

pz : ^integer;

Begin

GetMem(px,SizeOf(char));

GetMem(py,SizeOf(integer));

px^ := ‘A’;

py^ := ‘7’;

…

FreeMem(px,SizeOf(char));

FreeMem(py,SizeOf(integer));

…

End.

В этой программе в разделе описания переменных объявлены два не типизированных указателя. Затем в теле программы под динамические переменные, на которые ссылаются эти указатели, с помощью процедуры GetMem выделена динамическая память. После выделения памяти, динамическим переменным можно присваивать значения подходящего типа и использовать их в разного рода выражениях. Когда надобность в переменных рх и ру отпадает, выделенная для них память освобождается с помощью процедуры FreeMem.

ДЕЙСТВИЯ НАД УКАЗАТЕЛЯМИ И ДИНАМИЧЕСКИМИ ПЕРЕМЕННЫМИ

После того как указатель объявлен (в разделе описаний программы) и под динамическую переменную, на которую он ссылается, выделена память (с помощью процедуры New или GetMem), над указателем и динамической переменной обычно производятся какие-то манипуляции. К динамическим переменным применимы все действия, допустимые для данных этого типа, т.е. динамической переменной можно манипулировать так же, как и аналогичной статической переменной. Некоторые из этих действий иллюстрирует рисунку 2.1.

Рисунок 2.1 – Действия над динамическими переменными

На рисунке 2.1(а) представлены операции присваивания.

На рисунке 2.1(6) представлена операция сложения.

Па рисунке 2.1(в) представлены операции ввода с клавиатуры и вывода на экран.

Кроме вышеперечисленных действий, над динамическими переменными, можно производить операции, допустимые для данного типа статических переменных.

Для указателей (а не данных, на которые они указывают), допустимо только следующее действия:

1. Проверка равенства. Например:

If рх = ру

Then …

где рх и ру — указатели. Этот оператор проверяет, ссылаются ли указатели на один и тот же адрес памяти. (Если вместо рх=ру записать рх<ру или рх>ру, то компилятор укажет ошибку).

2. Значение одного указателя можно присвоить другому указателю, если оба указателя ссылаются на динамическую переменную одного типа. Например:

рх := ру; {где рх и ру — указатели}

Ограничение распространяется на типизированные указатели. Нетипизированному указателю можно присвоить значение любого указателя. Точно так же, любому указателю можно присвоить значение нетипизированного указателя.

3. Значения указателям (представляющие собой адреса памяти) присваиваются процедурой New или GetMem при выделении памяти для динамических переменных. Поэтому присваивать (с помощью оператора присваивания) указателям какие - либо явно заданные значения нельзя - за исключением Nil.

ДВА ВИДА ДИНАМИЧЕСКИХ ДАННЫХ

Динамические данные, на которые ссылаются указатели можно разделить на две категории: данные без внутренних ссылок и данные с внутренними ссылками.

ДИНАМИЧЕСКИЕ ДАННЫЕ БЕЗ ВНУТРЕННИХ ССЫЛОК

Эти данные отличаются от статических данных только тем, что в разделе описания переменных объявляются не переменные, а указатели на них. Сами же переменные создаются и ликвидируются входе работы программы, когда под них выделяется память (процедурой New или GetMem) или эта память освобождается (процедурой Dispose или FreeMem).

Преимущества использования динамических типов данных по сравнению с аналогичными статическими данными:

– Во-первых, для статических данных память выделяется при запуске программы, и эта память остается занята, пока программа не завершит работу. А для динамических данных (с внутренними ссылками и без них) память выделяется в момент начала использования той или иной динамической переменной и освобождается сразу же по завершении ее использования. (Применяя динамические переменные, можно обойтись меньшим объемом оперативной памяти).

– Во-вторых, динамическая память предоставляет возможность работать с данными структурированных типов гораздо большего объема.

Примеры использования статических и аналогичных динамических (без внутренних ссылок) структур данных можно видеть в таблицу 2.1.

Таблица 2.1 – Использование статических и динамических данных

Статические переменные	Динамические переменные
Var a : Boolean; b : integer; x : array[1..10] of integer; j : 1..10; Begin a:=true; b:=44; For j:=1 to 10 do Read(x[j]); … End.	Type v : array[1..10] of integer; Var pa : ^Boolean; pb : ^integer; px : ^v; j : 1..10; Begin New(pa); New(pb); New(px); pa^ := true; pb^ := 44; For j:=1 to 10 do Read(px^[j]); … Dispose(pa); Dispose(pb); Dispose(px); End.

Обрати внимание! В первой программе в разделе описания переменных массив объявлен так:

x : array[1..10] of integer;

А во второй программе в разделе описания типов объявлен тип v:

v : array[1..10] of integer;

затем в разделе описания переменных объявлен указатель рх на данные типа v:

px : ^v;

Возникает вопрос, а почему бы во второй программе не поступить как в первой – объявить указатель на массив?

x : ^array[1..10] of integer;

Этого делать нельзя. Если вы так сделать, а затем откомпилируете программу, появится сообщение об ошибке «в этой точке программы (те. после знака ^) ожидается идентификатор. Array – это не идентификатор, а зарезервированное слово, т. е., объявить указатель непосредственно на массив нельзя. Для решения этой проблемы, сначала необходимо объявить пользовательский тип v:

v : array[1..10] of integer;

а затем – указатель на данные типа v:

px : ^v;

ДИНАМИЧЕСКИЕ ДАННЫЕ С ВНУТРЕННИМИ ССЫЛКАМИ

Помимо простых (т.е. без внутренних ссылок) динамических данных, возможно существование динамических структур, в которых элементы ссылаются один на другой. Как это реализуется? Очевидно, что элемент подобной структуры должен представлять собой запись с не менее чем двумя полями. Одно поле такой записи предназначено для информации, а второе — для ссылки на следующий элемент этой же структуры.

Вот как данная структура может быть объявлена в разделе описания типов:

Type

P=^item;

item=record

data:integer;

reference:p;

end;

При описании указателя на запись, одно из полей которого ссылается на этот указатель, первым должно следовать описание указателя (в данном случае р). Запись объявленного выше типа Item состоит из полей Date и Reference. Первое поле предназначено для данных, а второе — для указателя, ссылающегося на следующую запись типа Item.

Графическое представление вышеприведенной структуры, показано на рисунке 2.2.

Рисунок 2.2 – Простейшая структура данных с внутренними ссылками (Item – элемент, Date – д анные, Reference – ссылка)

На рисунке 2.2 изображена цепочка элементов данной структуры с внутренними ссылками. Каждый элемент – это запись, принадлежащая типу Item.

Обратите внимание!

Указатель, содержащийся в поле Reference каждого элемента, ссылается не на одно из полей следующего элемента структуры: как это можно понять по изображению, а на элемент (запись) в целом. Такая структура называется – связным списком.

Можно сделать вывод, что связный список с точки зрения экономии памяти — не самый удобный способ организации данных, поскольку каждый элемент списка, помимо байтов памяти для информации, нуждается в памяти для указателя, ссылающегося на следующий элемент списка. Однако при большем расходе памяти списки обеспечивают и большую гибкость. Действительно, если аналогичные данные организовать в виде массива, для того чтобы включить в структуру новый элемент или исключить один из элементов, потребуется преобразовывать весь массив. В то же время для того чтобы добавить в список новый элемент, достаточно сделать так, чтобы указатель предыдущего элемента ссылался на новый элемент, а указатель нового элемента — на следующий элемёнт списка. Аналогично, при исключении одного из элементов списка достаточно только изменить значение указателя предыдущего элемента так, чтобы он указывал на элемент, следующий за исключаемым (см. рисунок 2.3).

Включение нового элемента в список	Исключение одного из элементов списка
Было P^.Reference=Q; Стало P^.Reference=L; L^.Reference=Q;	Было P^.Reference=L; L^.Reference=Q; Стало P^.Reference=Q;

Рисунок 2.3 – Включение и исключение элементов списка

Существует несколько разновидностей связного списка:

– Кольцевой список. В этом списке указатель последнего элемента ссылается на первый.

– Очередь. Эта разновидность связного списка допускает только добавление нового элемента в конец очереди и исключение элемента в начале очереди.

– Стек. Для этой разновидности связного списка можно только добавлять или исключать элементы с одного его конца.

Помимо линейных связных списков существуют иерархические структуры произвольной конфигурации, известные как деревья. Пример такого дерева показан на рисунке 2.4.

Здесь изображено дерево, каждый элемент (или узел) которого содержит два поля указателя. Поскольку каждый из этих указателей может иметь значение Nil у каждого из узлов может быть ни одного, один или два последующих узла. При этом число полей-указателей в узле двоичного дерева явно не ограничивается. Чем больше таких полей, тем потенциально «разветвленным» может быть дерево.

ПРОЦЕДУРЫ И ФУНКЦИИ ДЛЯ РАБОТЫ С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ

ФУНКЦИЯ Addr

Возвращает адрес переменной, процедуры или функции, указанной в качестве параметра.

Фома функции:

Function Addr(x):Pointer;

В качестве х — задается идентификатор переменной, процедуры или функции. Функция возвращает нетипизированный указатель, ссылающийся на х. Поскольку он принадлежит типу Pointer результат, возвращаемый функцией Addr, совместим со всеми типами указателей.

ОПЕРАЦИЯ @.

Для указателей определены только операции проверки на равенство и неравенство, а также операция присваивания. С помощью указателей можно "накладывать" одну структуру данных на другую. Для этого используется операция @, которая имеет следующий вид:

P:=@X;

где P - указатель; X - переменная. В результате выполнения этого оператора происходит присваивание указателю P адреса переменной X. Аналог @ - функция ADDR(X).

ПРОЦЕДУРА Dispose

Освобождает место, занятое в памяти динамической переменной на которую ссылается типизированный указатель.

Фома процедуры:

Procedure Dispose(Var P:Pointer{, Destructor]);

где р — типизированный указатель.

Возможности процедуры Dispose в Turbo Pascal с версии 7.0 были расширены, и теперь она может также освобождать память, занятую объектом, если деструктор этого объекта указать в качестве второго параметра процедуры.

Например

Dispose(P, Done);

После обращения к процедуре Dispose значение указателя р становится неопределенным. Поэтому повторное обращение к этой процедуре с р в качестве параметра приведет к ошибке исполнения программы.

ПРОЦЕДУРА FreeMem

Освобождает память, занятую динамической переменной данного размера, зарезервированную за нетипизированным указателем (с помощью процедуры GetMem).

Фома процедуры:

Procedure FreeMem(Var P:Pointer; Size : Word);

Здесь р — нетипизированный указатель для которого раньше была выделена память (процедурой GetMem), Size — выражение определяющее размер освобождаемой динамической переменной в байтах. Это значение должно совпадать с числом байтов, выделенных для этой переменной процедурой GetMem.

Процедура FreeMem ликвидирует переменную на которую ссылается указатель р, и освобождает память, занимаемую этой переменной. После обращения к FreeMem, значение указателя р становится неопределенным и при повторном обращении к FreeMem приведет к ошибки. Ошибка также возникнет при попытке сослаться на р.

ПРОЦЕДУРА GetMem

Создает динамическую переменную определенного размера, на которую ссылается нетипизированный указатель.

Фома процедуры:

Procedure Getmem(Var P:Pointer; Size : Word);

Самый большой блок, который может быть зарезервирован за один раз, равен 65520 байт. Если в куче для размещения динамической переменной недостаточно свободного пространства, то возникнет ошибка.

Пример программы, в которой используются процедуры FreeMem и GetMem, а также функция SizeOf:

Type

ar=array[1..10] of integer;

Var

P : Pointer;

Begin

GetMem(р, SizeOf(ar)); {Выделение памяти}

{…}

{Использование памяти}

{…}

FreeMem(р, SizeOf(ar)); {Освобождение памяти}

End.

Использованная функция SizeOf возвращает число байтов, занимаемых объектом, указанным в качестве параметра функции.

ПРОЦЕДУРА Mark

Присваивает динамической переменной, на которую ссылается указатель-аргумент процедурs, текущий адрес начала свободного участка динамической памяти.

Фома процедуры:

Procedure Mark(Var P:Pointer);

где р — нетипизированный указатель.

Процедура Mark часто используется совместно с процедурой Release и не должна использоваться с процедурой FreeMem или Dispose.

ФУНКЦИЯ MaxAvail

Возвращает размер самого большого непрерывного свободного участка в куче. Возвращаемый функцией результат представляет собой значение, принадлежащее типу LongInt.

Фома функции:

Function MaxAvail : LongInt;

ФУНКЦИЯ MemAvail

Возвращает количество всей свободной памяти в куче. Свободная память обычно представляет собой не единый блок, а множество разрозненных участков, что объясняется фрагментацией кучи. Возвращаемый функцией результат представляет собой значение типа LongInt.

Фома функции: Function MemAvail : LongInt;

Пример программы, в которой используются функции MaxAvail иMemAvail:

Type

ar=array[1..10] of integer;

Var

P : Pointer;

Begin

WriteLn(‘Свободная память’,Memavail,’наибольший участок’,maxavail);

GetMem(р, SizeOf(ar));

WriteLn(‘Свободная память’,Memavail,’наибольший участок’,maxavail);

End.

ПРОЦЕДУРА New

Создает новую динамическую переменную, на которую ссылается типизированный указатель.

Фома процедуры:

Procedure New(Var P:Pointer[, Init : Constructor]);

где р — типизированный указатель.

Возможности процедуры New в Turbo Pascal с версии 7.0 были расширены, и теперь она также может резервировать память для объекта, если конструктор этого объекта указать в качестве второго параметра процедуры.

Например

New(P, Init(420, 252));

где Init(42О, 252) — метод-конструктор, задающий для объекта некоторые начальные значения (т.е. выполняющий его инициализацию).

Процедура New может также вызываться как функция, возвращающая значение указателя. При этом параметр функции представляет собой не указатель, а тип указателя на объект.

Например:

Type

PChar=^Char; {объявление типа указателя}

Var

P : PChar; {объявление указателя}

Begin

р:=New(PChar); {вызов New как функции}

…

End.

При использовании New в виде функции, как и при традиционном использовании этой процедуры, можно указывать второй параметр, представляющий собой конструктор объектного типа.

ПРОЦЕДУРА Release

Освобождает часть кучи.

Фома процедуры:

Procedure Release(Var P : Pointer);

где р — указатель любого типа, ранее определенный процедурой Mark.

При обращении к процедуре Release освобождается часть кучи от адреса, на который указывает р, до конца кучи.

ФУНКЦИЯ SizeOf

Возвращает число байтов, занимаемых объектом, указанным в качестве параметра функции.

Function SizeOf(x) : Integer;

где Х — идентификатор типа или переменной.

Например, выражение SizeOf(Integer) имеет значение 2. Это же значение имеет выражение SizeOf(x) если x – переменная (но не выражение) типа Integer.

ПРИМЕРЫ ПРОГРАММ С УКАЗАТЕЛЯМИ

Создание динамических массивов (массива с заранее не заданным числом элементов).

Пример 1.

Program Ex;

Type

D=array [1..2] of real;

Var

A:^D {А-указатель на массив типа D}

N,I:word;

{$R-} {Выключение проверки значения индекса массива}

Begin

write('введите размер массива');

readln(N);

GetMem(A, N*6); {6-число байтов, занимаемое переменной типа real}

For I:=1 to N do

A^[I]:=0; {Обнуление элементов массива}

...

FreeMem(A, N*6);

{$R+}

End.

Рассмотрим программу транспонирования квадратной матрицы размера N*N:

Пример 2.

Program Trans;

Type

Mas = array [1..2] of integer;

MasUk = array[1..2] of ^Mas;

Var

M:^MasUk;

N,I,J,R:integer;

Begin

{$R-}

writeln('введите размерность квадратной матрицы');

read(N);

GetMem(M,SizeOf(Mas)*N);

{Ввод матрицы}

For I:=1 to N do

begin

GetMem(M^[I],2*N);

for J:=1 to N do

read(M^[I]^[J]);

end;

{Транспонирование матрицы}

for I:=1 to N do

if I<N

then for J:=I+1 to N do

begin

R:=M^[I]^[J];

M^[I]^[J]:=M^[J]^[I];

M^[J]^[I]:=R;

end;

{Вывод результатов}

for I:=1 to N do

begin

writeln;

for J:=1 to N do

write(M^[I]^[J],' ');

FreeMem(M^[I],2*N);

end;

FreeMem(M,SizeOf(Mas)*N);

{$R+}

End.

Пример 3.

В заданном списке необходимо найти (начиная с элемента St) элемент Res, информационная часть которого содержит I1. Программа, оформленная в виде функции, имеет вид:

Function Poisk(St:Uk; I1:integer; var Res:Uk):boolean;

Var

U:Uk;

begin

Poisk:=false;

Res:=Nil;

U:=St;

While (U<>Nil) and (Res=Nil) do

begin

if U^.I=I1

then

begin

Poisk:=true;

Res:=U;

end;

U:=U^.A;

end;

end;

Пример 4.

В заданный список после элемента Res, найденного с помощью рассмотренной выше функции Poisk, необходимо вставить некоторый элемент, информационная часть которого содержит значение IO. Программа, оформлена в виде процедуры, имеет вид:

Procedure Vstavka(Res:Uk; IO:inteer);

Var

U:UK;

begin

New(U);

U^.I:=IO; U^.A:=Res^.A; Res^.A:=U;

end;

Пример 5.

В заданном списке необходимо удалить элемент, следующий за элементом Res. Данная процедура выглядит следующим образом:

Procedure Udal(Res:UK);

Var

U:UK;

begin

if Re$^.A<>Nil

then

begin

U:=Res^.A; Res^.A:=Res^.A^.A;

Dispose(U);

end;

end;

Пример 6.

Составить программу формирования стека, заполняющегося путем ввода целых положительных чисел с клавиатуры. Как только будет введено первое отрицательное число, содержимое стека выводится на экран. Данная программа выглядит следующим образом:

Program st;

Type Uk=^Stek;

Stek=record

I:integer;

A:Uk;

end;

Var

U1, U2:Uk; I1:integer;

Begin

{формирование стека}

U2:=Nil;

I1:=0;

While I1>=0 do

begin

New(U1);

writeln('введите число'); read(I1);

U1^.I:=I1; U1^.A:=U2; U2:=U1

end;

{Вывод содержимого стека}

repeat

writeln('элемент стека',U1^.I);

U2:=U1^.A;

Dispose(U1);

U1:=U2;

until (U1=Nil);

end.

Пример 7.

Формирование очереди осуществляется с помощью следующей процедуры:

Procedure Form;

Label M;

begin

write('1-й элемент:');

read(k); {Чтение первого элемента} {Пусть значение -32000 будет

признаком окончания процесса формирования очереди}

New(Ku); {Резервируется память под первый элемент очереди}

Ku^.P:=Nil; {Первый элемент не имеет ссылки}

Ku^.I:=K; {Занесение в очередь первого элемента}

Rw:=Ku;

Lw:=Ku;

while True do

begin

write('i-й элемент:');

read(K); {Значение очередного элемента}

if K=-32000

then goto M;

New(Ku);

Lw^.P:=Ku;

Ku^.P:=Nil;

Ku^.I:=K;

Lw:=Ku

end;

M: writeln('Формирование очереди закончено')

end;

В данной процедуре Rw - указатель начала очереди, Lw - указатель конца очереди.

Пример 8.

Удаление элемента из начала очереди производится с помощью следующей процедуры:

Procedure Ud;

begin

T:=Rw;

Rw:=Rw^.P;

Dispose(T);

writeln('удален');

end;

Пример 9.

Процедура добавления элемента в конец очереди имеет вид:

Procedure Dob;

begin

write('добавление элемента:');

read(k);

New(ku);

Ku^.P:=Nil;

Lw^.P:=Ku;

Ku^.I:=K;

Lw:=Ku;

writeln('Новый элемент помещен в очередь');

end;

Пример 10. С использованием вышеприведенных процедур раздел операторов основной программы имеет вид:

begin

form;

Dob;

Ud;

{Печать очереди}

repeat

writeln('элемент очереди',Rw^.I);

Ku:=Rw^.P;

Dispose(Rw);

Rw:=Ku;

until (Rw=Nil);

end.

Задания:

1. Разработать программу перемножения двух матриц A и B размерности n*m. Обе матрицы размещаются в оперативной памяти динамически, а значения n и m вводится по запросу с клавиатуры.

2. Разработать программу сортировки (упорядочивания) матрицы размерности n*n так, чтобы элементы в каждой строке отсортированной матрицы располагались по возрастанию и ни один элемент в i-й строке не был больше любого элемента в i+1-й строке. Сортировку выполнять над одномерным массивом из n*n элементов, который "накладывается" на исходную матрицу.

3. Разработать программу формирования стека, куда помещаются целые положительные числа, вводимые с клавиатуры. Процесс ввода должен прекращаться, как только среди вводимых чисел появляется отрицательное число. После этого программа должна вывести на экран терминала содержимое стека, при этом порядок выводимых чисел должен быть обратным по сравнению с последовательностью их ввода.

4. Разработать программу вычисления значения многочлена

P(x)=A₀+A₁x+A₂x²+...+A_nxⁿ в целочисленной точке x. При этом значения коэффициентов A₀,A₁, ..., A_n вводятся с клавиатуры и динамически размещаются в памяти либо в форме массива, либо в форме стека.

5. Разработать программу формирования стека, содержащего целые числа, и упорядочивания по возрастанию элементов в этом стеке. В процессе упорядочивания элементы стека перемещаться не должны.

6. Разработать программу формирования стека, куда помещается последовательность символов в виде отдельных слов, вводимых с клавиатуры. Каждое слово, помещенное в стек, следует вывести на экран терминала; при этом порядок вывода символов в каждом слове должен быть обратным по сравнению с последовательностью их ввода.

7. Разработать программу формирования и вывода на печать двунаправленного списка. Двунаправленный список является динамической структурой данных и отличается от однонаправленного списка тем, что каждый его элемент хранит не одну ссылку (указатель на следующий элемент), а две. Из них одна указывает на предыдущий элемент, другая - на следующий элемент списка.

8. Разработать программу формирования стека, содержащего целые положительные числа, и его преобразования путем удаления из него всех четных чисел (в процессе преобразования стека его элементы в оперативной памяти перемещаться не должны).

9. Разработать программу, формирующую динамическую структуру данных для хранения генеалогического дерева. Каждая вершина дерева должна содержать следующую информацию: имя и год рождения.

10. Разработать программу вычисления суммы элементов массива, состоящего из n вещественных чисел. Массив должен быть размещен в памяти динамически, а значения n вводится с клавиатуры.

11. Разработать программу, определяющую симметричность произвольного текста любой длины. Текст всегда должен оканчиваться точкой. Эту задачу рекомендуется решать с помощью двух стеков. В первый стек следует поместить весь текст, затем во второй стек перенести его половину так, чтобы последний символ текста находился на дне стека. Дале путем поэлементного сравнения этих стеков получить ответ на вопрос о симметричности текста.

12. Разработать программу формирования стека, куда помещается последовательность символов, вводимых с клавиатуры. Процесс ввода символов должен прекращаться, как только среди вводимых символов появляется точка, после этого программа должна реверсировать стек. Под реверсированием здесь понимается изменения направления ссылок в стеке на противоположное, т.е. после реверсирования вершина и дно стека меняется местами.

13. Разработать программу выявления седловой точки в матрице размерности n*n. Матрица размещается в оперативной памяти в форме двухмерного массива динамически (значение n вводится по запросу с клавиатуры). Седловой точкой в матрице называют элемент, одновременно наибольший в своей строке и наименьший в своем столбце.

14. Разработать программу вычисления значения выражения следующего вида:

X₁*X_n+X₂*X_n-1+...+X_n*X₁

При этом значения X₁, X₂, ..., X_n вводятся с клавиатуры и динамически размещаются в оперативной памяти либо в форме массива, либо в форме стека (или двух стеков, один из которых реверсирован по отношению к другому - см. задание №12).

15. Разработать программу слияния двух стеков, содержащих возрастающую последовательность целых положительных чисел, в третий стек так, чтобы его элементы располагались также в порядке возрастания.

16. Разработать программу, которая в матрице размерности n*n меняет местами строку, содержащую элемент с наибольшим значением, со столбцом, содержащим элемент с наименьшим значением. Матрица должна размещаться в оперативной памяти динамически, а значение n вводиться по запросу с клавиатуры.