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

Статической переменной (постоянно размещенной в памяти) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени. Место в памяти для размещения статических переменных определяется при компиляции программы.

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

Работа с динамической областью памяти реализуется с помощью следующих процедур и функций:

New( var p: Pointer ) - процедура выделяет место в динамической области памяти для размещения динамической переменной p^ и ее адрес присваивает указателю p.

Dispose( var p: Pointer ) - процедура освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя p становится неопределенным.

GetMem( var p: Pointer; size: Word ) – процедура выделяет участок памяти в heap - области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.

FreeMem( var p: Pointer; size: Word ) – процедура освобождает участок памяти, адрес начала которого определен указателем p, а размер - параметром size. Значение указателя p становится неопределенным.

Mark( var p: Pointer ) – процедура записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова.

Release( var p: Pointer ) – процедура освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, то есть, очищает ту динамическую память, которая была занята после вызова процедуры Mark.

MaxAvail - функция возвращает длину в байтах самого длинного свободного участка динамической памяти.

MemAvail - функция полный объем свободной динамической памяти в байтах.

SizeOf(X) функция возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.

Динамические переменные можно организовывать в структуры:

- стеки,

- очереди,

- деки,

- списки,

- двоичные деревья.

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

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым. Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная.

Рис. 1. Организация стека.

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

Type

CompPtr= ^Comp;

Comp= Record

Item: TypeItem;

Next: CompPtr

end;

Здесь TypeItem – это тип элементов стека. Описание переменных для работы стека могут иметь следующий вид:

Var Top, Temp: CompPtr;

где Top - указатель вершины стека; Temp - вспомогательный указатель.

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

Procedure CreateStack(var Top: CompPtr; var C: TypeItem);

begin

New(Top);

Top^.Next:=NIL;

Top^.Item:=C

end;

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

Procedure AddComp(var Top: CompPtr; var C: TypeItem);

var Temp: CompPtr;

begin

New(Temp);

Temp^.Next:=Top;

Top:=Temp;

Top^.Item:=C

end;

Рассмотрим процесс выборки компонент из стека и одновременно удаление

Procedure DelComp(var Top: CompPtr; var C:TypeItem);

begin

C:=Top^.Item;

Top:=Top^.Next

end;

Пример: Составить программу, которая формирует стек из цифр довольного большого числа и выводит их в обратном порядке. Ввод данных - с клавиатуры дисплея, признак конца ввода - символ ‘.’ Будем использовать процедуры, приведенные выше.

Program STACK;

Uses Crt;

Type

TypeItem=Integer;

CompPtr= ^Comp;

Comp= Record

Item: TypeItem;

Next: CompPtr

end;

Var

Top: CompPtr;

I: TypeItem;

C: char;

Begin

Clrscr;

Writeln(' ВВЕДИ ЦИФРЫ ЧИСЛА ДО ТОЧКИ: ');

Read(C); i:=ord(C)-ord(‘0’);

CreateStack(Top,i);

Repeat

Read(C); i:=ord(C)-ord(‘0’);

AddComp(Top,i)

Until C='.';

Writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');

Repeat

DelComp(Top,i);

Write(i);

Until Top = NIL

end.

Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу: FIFO (First-In, First-Out) - поступивший первым, обслуживается первым. Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая - конец очереди, третья – вспомогательная.

Рис. 2. Организация очереди.

Описание очереди дадим следующим образом:

type

CompPtr=^Comp;

Comp=record

Item:TypeItem;

Next:CompPtr

end;

Var

pBegin, pEnd, pTemp: CompPtr;

где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pTemp - вспомогательный указатель.

Тип ТypeItem определяет тип данных компоненты очереди, который в зависимости от решаемой задачи определяется в программе перед описанием самой очереди.

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

Procedure CreateQueue(var pBegin,pEnd: CompPtr; var C: TypeItem);

begin

New(pBegin);

pBegin^.Next:=NIL;

pBegin^.Item:=C;

pEnd:=pBegin

end;

Добавление компоненты в очередь производится в конец очереди:

Procedure AddQueue(var pEnd:CompPtr; var C:TypeItem);

var pTemp: PCompPtr;

begin

New(pTemp);

pTemp^.Next:=NIL;

pEnd^.Next:=pTemp;

pEnd:=pTemp;

pEnd^.Item:=C

end;

Выборка компоненты из очереди осуществляется из начала очереди, одновременно компонента исключается из очереди.

Procedure DelQueue(var pBegin: CompPtr; var C: TypeItem);

begin

C:=pBegin^.Item;

pBegin:=pBegin^.pNext

end;

Пример: Необходимо ввести строки по порядку их считывания и вывести в том же порядке. Окончание ввода будет являться слово END. Будем использовать приведенные выше процедуры.

Program QUEUE;

Uses CRT;

Type

TempItem= String[10];

CompPtr= ^Comp;

Comp= record

Item: TempItem;

Next:CompPtr

End;

Var

pBegin, pEnd: CompPtr;

C: TempItem;

Begin

Clrscr;

Writeln(' ВВЕДИТЕ СЛОВА:');

Readln(C);

CreateQueue(pBegin,pEnd,C);

Repeat

Readln(C);

AddQueue(pEnd,C)

Until C='END';

Writeln(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');

Repeat

DelQueue(pBegin,C);

Writeln(C);

Until pBegin=NIL

End.

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

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

Рис. 3. Организация списка.

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

-для чтения доступна любая компонента списка;

-новые компоненты можно добавлять в любое место списка;

-при чтении компонента не удаляется из списка.

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

-начальное формирование списка (запись первой компоненты);

-добавление компоненты в конец списка;

-чтение компоненты с заданным ключом;

-вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);

-исключение компоненты с заданным ключом из списка.

Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая - конец списка, остальные- вспомогательные.

Описание компоненты списка и переменных типа указатель дадим следующим образом:

Type

CompPtr= ^Comp;

Comp= Record

Item:TypeItem;

Next:CompPtr

End;

Var

Top, pEnd, Curr, Pred, Temp: CompPtr;

где Top - указатель начала списка, pEnd - указатель конца списка, Curr, Pred, Temp - вспомогательные указатели.

Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.

New(Top);

Top^.Next:=NIL;

Top^.Item:=C;

pEnd:=Top

Для чтения и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом:

Curr:=Top;

While (Curr<>NIL) and (Key<>Curr^.Item) do Curr:=Curr^.Next;

Здесь Key - ключ, тип которого совпадает с типом данных компоненты. После выполнения этих операторов указатель Curr будет определять компоненту с заданным ключом или такая компонента не будет найдена.

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

New(Temp);

Temp^.Item:= C ;

Temp^.Next:=Curr^.Next; {1}

Curr^.Next:=Temp; {2}

Если такой записи не найдено, то необходимо вставить перед первым элементом в списке и изменить ссылку Top на ссылку Temp:

New(Temp);

Temp^.Item:= C ;

Temp^.Next:=Top;

Top:=Temp;

Рис. 4. Организация вставки в список.

Для удаления компоненты с заданным ключом необходимо при поиске нужной компоненты помнить адрес предшествующей:

Curr:=Top;

Pred:=Nil;

While (Curr<>NIL) and (Key<>Curr^.Item) do

Begin

Pred:=Curr;

Curr:=Curr^.Next

End;

Здесь указатель Curr определяет компоненту с заданным ключом, указатель Pred содержит адрес предыдущей компоненты.

Рис. 5. Организация удаления из списка.

Удаление компоненты с ключом Key выполняется оператором:

Pred^.Next:=Curr^.Next;

Если необходимо удалить первый элемент из списка, то изменяем ссылку Top на Curr^.Next.

Пример: Составить программу, которая формирует список, добавляет в него произвольное количество компонент, выполняет вставку и удаление компоненты по ключу, а затем читает и выводит весь список на экран дисплея. В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

Program LISTLINKED;

Uses Crt;

Type

TypeItem= String[10];

Comp= ^CompPtr;

Comp= Record

Item:TypeItem;

Next:CompPtr;

End;

Var

Top, pEnd, Temp, Curr, Pred: CompPtr;

C, Key: TypeItem;

Cond: Boolean;

Procedure CreateLL(var Top,pEnd: CompPtr; var C: TypeItem);

Begin

New(Top);

Top^.Next:=NIL;

Top^.Item:=C;

pEnd:=Top

End;

Procedure AddLL(var pEnd: CompPtr; var C: TypeItem);

Var Temp: CompPtr;

Begin

New(Temp);

Temp^.Next:=NIL;

pEnd^.Next:=Temp;

pEnd:=Temp;

pEnd^.Item:=C

End;

Function Find(var Key: TypeItem; var Top, Curr,Pred: CompPtr): Boolean;

Var Cond: Boolean;

Begin

Curr:=Top; Pred:=Nil;

While (Curr <> NIL) and (Key <> Curr^.Item) do

Begin

Pred:=Curr;

Curr:=Curr^.Next

End;

If (Curr = NIL) and (Key <> Curr^.Item)

Then Cond:=FALSE

Else Cond:=TRUE;

Find:=Cond;

end;

Procedure InsComp(var Key,C: TypeItem);

Var Temp:PCompPtr;

Begin

If Not Find(Key,Top, Curr, Pred) then begin

New(Temp);

Temp^.Item:=C;

Temp^.Next:=Top;

Top:=Temp;

End

Else begin

New(Temp);

Temp^.Item:=C;

Temp^.Next:=Curr^.Next;

Curr^.Next:=Temp

End;

End;

Procedure DelComp(var Key: TypeItem; var Top: CompPtr);

Begin

If not Find(Key, Top, Curr, Pred) then exit;

If Pred<>Nil

Then Pred^.Next:=Curr^.Next

Else Top:=Curr^.Next;

End;

Begin

ClrScr;

Writeln(' ВВЕДИ СТРОКИ ДО END : ');

Readln(C);

CreateLL(Top, pEnd, C);

Repeat

Readln(C);

AddLL(pEnd,C)

Until C='END';

Writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****');

Temp:=Top;

Repeat

Writeln(temp^.Item);

Temp:=Temp^.Next;

Until Temp=NIL;

Writeln;

Writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ');

Readln(Key);

Writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ');

Readln(C);

InsComp(Key, C);

Writeln;

Writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ');

Readln(Key);

DelComp(Key, Top);

Writeln;

Writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****');

Temp:=Top;

Repeat

Writeln(Temp^.Item);

Temp:=Temp^.Next;

Until Temp=NIL

End.

Приведем примеры применения связанных списков: задача сложения и умножения многочленов, представления разреженных матриц с помощью циклических списков и списков с двумя и одной связями, построение карты дорог. Пусть t1, t2,t3, t4 - названия городов, города соединены между собой дорогами (см. рис.6).

Рис. 6. a) карта дорог; b) виды звеньев

Рис. 7. Представление карты дорог с помощью сцепления

Чтобы представить такой граф в памяти, можно использовать звенья двух видов: звенья для городов, применяя указатели для связывания города с проходящими через него дорогами, и звенья для дорог для представления ребер графа. Один из способов представления карты можно видеть на рис.7.

Построение карты дорог можно выполнить в несколько шагов:

1. Прежде всего, надо определить точки входа в карту. Каждая точка должна содержать указатель на звено для города. Этот этап можно реализовать либо созданием массива точек входа, либо связанного списка точек входа; в последнем случае достаточно хранить только указатель на начало этого списка.

2. В динамической памяти создаются элементы с одной связью, содержащие информацию о городах. Заполняется ссылочная часть элементов, созданных на шаге 1.

3. Цикл по количеству городов. Для каждого города строится в динамической памяти список элементов с двумя связями – информация о дорогах. Число элементов списка заранее неизвестно. Адресная часть элемента-города связывается с адресом первого элемент списка.

4. Циклы по элементам списка ”дороги”. Заполняется поле “Указатель на пункт назначения”.

Деревья относятся к разряду структур, которые удобно строить в динамической памяти с использованием указателей. Наиболее важный тип деревьев – двоичные (бинарные) деревья, в которых каждый узел имеет самое большее два поддерева: левое и правое. Подробнее, если имеем дерево вида (рис. 8a), то ему может соответствовать в динамической памяти структура (рис. 8б).

Рис. 8. Двоичное дерево и его представление с помощью списочных структур памяти: а – двоичное дерево; б – представление дерева с помощью списков с использованием звеньев одинакового размера

Для построения такого бинарного дерева используется следующий ссылочный тип:

Type

Ptr=^Node;
Node=record
Key:TypeItem;
Left,Right:Ptr;
End;

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

var p:ptr;st:Typeitem;

Тогда двоичное дерево можно построить с помощью следующей рекурсивной процедуры:

Procedure V(var p:ptr);
Var

st:typeitem;
Begin
   Readln(st);
  If st<>'.' Then
      Begin
        New(p);
        p^.key:=st;
        V(p^.Left);
        V(p^.Right);
      End
     Else p:=nil
End;

Структура дерева отражается во входном потоке данных: каждой вводимой пустой связи соответствует условный символ (в данном случае точка). Для примера на рис. 1 входной поток имеет вид:

A B D . G . . . C E . . F H . . J . . .

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

Следующие рекурсивные процедуры PreOrder, PostOrder и InOrder выполняют обход дерева в прямом, обратном и внутреннем порядке.

Procedure Preorder(P:Ptr); {Прямой порядок: ABDGCEFHJ}

Begin

If P<>nil then begin

Write(P^.Key:3);

Preorder(P^.left);

Preorder(P^.right);

End

End;

Procedure Inorder(P:ptr); {Внутренний порядок: DGBAECHFJ}

Begin

If P<>nil then begin

Inorder(P^.left);

Write(P^.key:3);

Inorder(P^.right);

End

End;

Procedure Postorder(P:ptr); {Обратный порядок:GDBEHJFCA}

Begin

If P<>nil then begin

Postorder(P^.left);

Postorder(P^.right);

Write(P^.key:3);

End

End;

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