вторник, 1 ноября 2011 г.

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

Статической переменной (постоянно размещенной в памяти) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени. Место в памяти для размещения статических переменных определяется при компиляции программы.
Динамические переменные создаются и память для них выделяется во время выполнения программы. Размещаются динамические переменные в динамической области памяти (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;
Приведем примеры использования деревьев: проход по лабиринту, вычисление арифметических выражений, записанных в виде строки с использованием скобок, проход шахматной фигуры – коня, ферзя, короля – по шахматному полю с заданными условиями.

Комментариев нет:

Отправить комментарий