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

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

Д А Н Н Ы Х

Структурированные типы данных, такие, как массивы, множества, за-

писи, представляют собой статические структуры, так как их размеры

неизменны в течение всего времени выполнения программы.

Часто требуется, чтобы структуры данных меняли свои размеры в ходе

решения задачи. Такие структуры данных называются динамическими, к

ним относятся стеки, очереди, списки, деревья и другие. Описание ди-

намических структур с помощью массивов, записей и файлов приводит к

неэкономному использованию памяти ЭВМ и увеличивает время решения за-

дач.

Каждая компонента любой динамической структуры представляет собой

запись, содержащую по крайней мере два поля: одно поле типа указа-

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

содержать не один, а несколько укзателей и несколько полей данных.

Поле данных может быть переменной, массивом, множеством или записью.

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

де:

г=====¬

¦ D ¦

¦=====¦

¦ p ¦

L=====-

где поле p - указатель;

поле D - данные.

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

type

Pointer = ^Comp;

Comp = record

D:T;

pNext:Pointer

end;

здесь T - тип данных.

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

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

компоненты.

38. С Т Е К И

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

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

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

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.