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

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание ди- намических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения за- дач.

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

Для дальнейшего рассмотрения представим отдельную компоненту в ви- де:

г=====¦ D ¦¦=====¦¦ p ¦L=====-

где поле p - указатель; поле D - данные. Описание этой компоненты дадим следующим образом:

type Pointer = ^Comp; Comp = record D:T; pNext:Pointer end;

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

СТЕКИ

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

LIFO (Last-In, First-Out) -

поступивший последним, обслуживается первым.

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

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

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

var pTop, pAux: Pointer;где pTop - указатель вершины стека;pAux - вспомогательный указатель.

ачальное формирование стека выполняется следующими операторами: г===== г===== New(pTop); ¦ *--¦--- ¦ ¦ L=====- ¦ ¦=====¦ pTop L-->¦ ¦ L=====- г===== г===== pTop^.pNext:=NIL; ¦ *--¦--- ¦ ¦ L=====- ¦ ¦=====¦ pTop L-->¦ NIL ¦ L=====- г===== г===== pTop^.D:=D1; ¦ *--¦--- ¦ D1 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ NIL ¦ L=====-

Последний оператор или группа операторов записывает содержимое поля данных первой компоненты.

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

г===== г===== г===== New(pAux); ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦ ¦ L=====- pTop ¦ ¦ ¦<--- pAux ¦ L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ L-->¦ NIL ¦ L=====- г===== г===== г===== pAux^.pNext:=pTop; ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦<--- L=====- pTop ¦ ¦ *--¦- pAux ¦ L=====- ¦ ¦ ¦ ¦ г===== ¦ ¦ ¦ D1 ¦ ¦ ¦ ¦=====¦ ¦ L-->¦ NIL ¦<- L=====- г===== г===== г===== pTop:=pAux; ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦<--- L=====- pTop L-->¦ *--¦- pAux L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====- г===== г===== pTop^.D:=D2; ¦ *--¦--- ¦ D2 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====-

Добавление последующих компонент производится аналогично.

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

г===== г===== ¦ *--¦--- ¦ D3 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D2 ¦ ¦ ¦=====¦ ¦ --¦--* ¦<- ¦ L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ L>¦ NIL ¦ L=====-

Первый оператор или группа операторов осуществляет чтение данных из компоненты - вершины стека. Второй оператор изменяет значение ука- зателя вершины стека:

г===== г===== D3:=pTop^.D; ¦ *--¦--- ¦ D3 ¦ pTop:=pTop^.pNext; L=====- ¦ ¦=====¦ pTop ¦ ¦ ¦ ¦ L=====- ¦ ¦ г===== ¦ ¦ D2 ¦ ¦ ¦=====¦ L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====-

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

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

Program STACK; uses Crt; type Alfa= String[10]; PComp= ^Comp; Comp= Record sD: Alfa; pNext: PComp end; var pTop: PComp; sC: Alfa; Procedure CreateStack(var pTop: PComp; var sC: Alfa); begin New(pTop); pTop^.pNext:=NIL; pTop^.sD:=sC end; Procedure AddComp(var pTop: PComp; var sC: Alfa); var pAux: PComp; begin NEW(pAux); pAux^.pNext:=pTop; pTop:=pAux; pTop^.sD:=sC end; Procedure DelComp(var pTop: PComp; var sC:ALFA); begin sC:=pTop^.sD; pTop:=pTop^.pNext end; begin Clrscr; writeln(' ВВЕДИ СТРОКУ '); readln(sC); CreateStack(pTop,sC); repeat writeln(' ВВЕДИ СТРОКУ '); readln(sC); AddComp(pTop,sC) until sC='END'; writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******'); repeat DelComp(pTop,sC); writeln(sC); until pTop = NIL end.