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

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

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

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

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

г=====

¦ D ¦

¦=====¦

¦ p ¦

L=====-

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

type

Pointer = ^Comp;

Comp = record

D:T;

pNext:Pointer

end;

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

СТЕКИ

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

LIFO (Last-In, First-Out) -

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

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

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

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

3. выборка компоненты (удаление).

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

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.

ОЧЕРЕДИ

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

FIFO (First-In, First-Out) -

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

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

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

type

PComp=^Comp;

Comp=record

D:T;

pNext:PComp

end;

var

pBegin, pEnd, pAux: PComp;

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

Тип Т определяет тип данных компоненты очереди.

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

г===== г===== г=====

New(pBegin); ¦ *--¦--- ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ ¦ pEnd

L=====-

г===== г===== г=====

pBegin^.pNext:=NIL; ¦ *--¦--- ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦ pEnd

L=====-

г===== г===== г=====

pBegin^.D:=D1; ¦ *--¦--- ¦ D1 ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦ pEnd

L=====-

г===== г===== г=====

pEnd:=pBegin; ¦ *--¦--- ¦ D1 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd

L=====-

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

New(pAux);

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ ¦<--- pAux

L=====- L=====-

pAux^.pNext:=NIL;

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

pBegin^.pNext:=pAux;

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

pEnd:=pAux;

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ¦ *--¦--- ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ L=====- ¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦ pEnd L-->¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

pEnd^.D:=D2;

г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦-------------------->¦ NIL ¦<--- pEnd

L=====- L=====-

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

Выборка компоненты из очереди осуществляется из начала очереди, одновременно компонента исключается из очереди. Пусть в памяти ЭВМ сформирована очередь, состоящая из трех элементов:

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦------>¦ *--¦------>¦ NIL ¦<--- pEnd

L=====- L=====- L=====-

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

D1:=pBegin^.D;

pBegin:=pBegin^.pNext;

г===== г===== г===== г===== г=====

¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin ¦ ¦ ¦ --->¦ *--¦------>¦ NIL ¦<--- pEnd

¦ L=====- ¦ L=====- L=====-

¦ ¦

L--------------

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

Program QUEUE;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;

Comp= record

sD:Alfa;

pNext:PComp

end;

var

pBegin, pEnd: PComp;

sC: Alfa;

Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);

begin

New(pBegin);

pBegin^.pNext:=NIL;

pBegin^.sD:=sC;

pEnd:=pBegin

end;

Procedure AddQueue(var pEnd:PComp; var sC:Alfa);

var pAux: PComp;

begin

New(pAux);

pAux^.pNext:=NIL;

pEnd^.pNext:=pAux;

pEnd:=pAux;

pEnd^.sD:=sC

end;

Procedure DelQueue(var pBegin: PComp; var sC: Alfa);

begin

sC:=pBegin^.sD;

pBegin:=pBegin^.pNext

end;

begin

Clrscr;

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

CreateQueue(pBegin,pEnd,sC);

repeat

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

AddQueue(pEnd,sC)

until sC='END';

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

repeat

DelQueue(pBegin,sC);

writeln(sC);

until pBegin=NIL

end.

ЛИНЕЙНЫЕ СПИСКИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

type

PComp= ^Comp;

Comp= record

D:T;

pNext:PComp

end;

var

pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

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

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

г===== г===== г===== г===== г===== г=====

¦ *--¦- ¦ D1 ¦ ¦ D2 ¦ ¦ DN1 ¦ ¦ DN ¦ --¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦--->¦ *--¦-....->¦ *--¦--->¦ NIL ¦<-- pEnd

L=====- L=====- L=====- L=====-

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

pCKey:=pBegin;

while (pCKey<>NIL) and (Key<>pCKey^.D) DO

pCKey:=pCKey^.pNext;

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

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

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

New(pAux); г===

pAux^.D:= DK1; ---¦-* ¦

¦ L===-

¦ pCKey

¦

г=== г=== г=== г=== г=== г===

¦ *-¦-- ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ *-¦---->¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- L===- L===-

г=== г===

¦DK1¦ ---¦-* ¦

¦===¦ ¦ L===-

¦ ¦<-- pAux

L===-

pAux^.pNext:=pCKey^.pNext;

pCKey^.pNext:=pAux;

г===

---¦-* ¦

¦ L===-

¦ pCKey

¦

г=== г=== г=== г=== г=== г===

¦ *-¦-- ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ * ¦ ¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- L===- L===-

¦ ^

¦ ¦ г=== г===

¦ ¦ ¦DK1¦ ---¦-* ¦

¦ L----------¦===¦ ¦ L===-

L------------------->¦-* ¦<-- pAux

L===-

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

pCKey:=pBegin;

while (pCKey<>NIL) and (Key<>pCKey^.D) do

begin

pPreComp:=pCKey;

pCKey:=pCKey^.pNext

end;

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

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

pPreComp^.pNext:=pCKey^.pNext;

pPreComp pCKey

г=== г===

¦ * ¦ ¦ * ¦

L===- L===-

¦ ¦

¦ ¦

¦ ¦

г=== г=== г=== г=== г=== г=== г===

¦ *-¦-- ¦D1 ¦ ¦KK1¦ ¦Key¦ ¦KK2¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ *-¦- ¦ *-¦--->¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- ¦ L===- L===- L===-

¦ ^

¦ ¦

L---------------

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

Program LISTLINKED;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;

Comp= record

sD:Alfa;

pNext:PComp

end;

var

pBegin, pEnd, pAux, pCKey, pPreComp: PComp;

sC, sKey: Alfa;

bCond: Boolean;

Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa);

begin

New(pBegin);

pBegin^.pNext:=NIL;

pBegin^.sD:=sC;

pEnd:=pBegin

end;

Procedure AddLL(var pEnd: PComp; var sC: Alfa);

var pAux: PComp;

begin

New(pAux);

pAux^.pNext:=NIL;

pEnd^.pNext:=pAux;

pEnd:=pAux;

pEnd^.sD:=sC

end;

Procedure Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp;

var bCond: Boolean);

begin

pCKey:=pBegin;

while (pCKey <> NIL) and (sKey <> pCKey^.D) do

begin

pPreComp:=pCKey;

pCKey:=pCKey^.pNext

end;

if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE

else bCond:=TRUE

end;

Procedure InsComp(var sKey,sC: Alfa);

var pAux:PComp;

begin

Find(sKey,pBegin,pCKey,pPreComp,bCond);

New(pAux);

pAux^.sD:=sC;

pAux^.pNext:=pCKey^.pNext;

pCKey^.pNext:=pAux

end;

Procedure DelComp(var sKey: Alfa; var pBegin: PComp);

begin

Find(sKey,pBegin,pCKey,pPreComp,bCond);

pPreComp^.pNext:=pCKey^.pNext

end;

begin

ClrScr;

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

CreateLL(pBegin,pEnd,sC);

repeat

writeln('ВВЕДИ СТРОКУ ');

readln(sC);

AddLL(pEnd,sC)

until sC='END';

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

pAux:=pBegin;

repeat

writeln(pAux^.sD);

pAux:=pAux^.pNext;

until pAux=NIL;

writeln;

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

readln(sKey);

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

readln(sC);

InsComp(sKey,sC);

writeln;

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

readln(sKey);

DelComp(sKey,pBegin);

writeln;

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

pAux:=pBegin;

repeat

writeln(pAux^.sD);

pAux:=pAux^.pNext;

until pAux=NIL

end.

Не нашли, что искали? Воспользуйтесь поиском по сайту: