Основные понятия алгоритмического языка
writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3);
p1:=p2;
writeln('p1^=',p1^:3,' p2^=',p2^:3)
end.
на экран дисплея будут выведены результаты:
p1^= 2 p2^= 4 p3^= 18
p1^= 4 p2^= 4
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=====-
г=====¬