Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

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

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

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

г=====

¦ 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.