Основы программирования на C++, PASCAL

Однонаправленная цепочка — простейший вариант связанного списка. В практике программирования используются двунаправленные цепочки (когда каждый элемент хранит указатель на следующий и на предыдущий элементы списка), а также двоичные деревья. Подобные структуры данных называются динамическими структурами.

Пример 3. Задача о стеке. Одной из часто употребляемых в программировании динамических структур данных является стек. Стек — это связанная цепочка, начало которой называется вершиной. Состав элементов постоянно меняется. Каждый вновь поступающий элемент размещается в вершине стека. Удаление элементов из стека также производится с вершины.

Стек подобен детской пирамидке, в которой на стержень надеваются кольца. Всякое новое кольцо оказывается на вершине пирамиды. Снимать кольца можно только сверху. Принцип изменения содержания стека часто формулируют так: «Последним пришел — первым вышел».

Составим процедуры добавления элемента в стек (INSTEK) и исключения элемента из стека (OUTSTEK). При этом будем считать, что элементы стека — символьные величины.

В процедурах используется тип Pе, который должен быть глобально объявлен в основной программе.

Type Pe=^TypElem;

TypElem=Record

С: Char; P: Ре

End;

В процедуре INSTEK аргументом является параметр Sim, содержащий включаемый в стек символ. Ссылочная переменная Beg содержит указатель на вершину стека при входе в процедуру и при выходе из нее. Следовательно, этот параметр является и аргументом, и результатом процедуры. В случае, когда стек пустой, указатель Beg равен Nil.

Procedure INSTEK(Var Beg: Ре; Sim: Char);

Var X: Pe;

Begin New(X);

X^.C:=Sim;

X^.P:=Beg;

Beg:=X

End;

В процедуре OUTSTEK параметр Beg играет ту же роль, что и в предыдущей процедуре. После удаления последнего символа его значение станет равным Nil. Ясно, что если стек пустой, то удалять из него нечего. Логический параметр Flag позволяет распознать этот случай. Если на выходе из процедуры Flag=True, то, значит, удаление произошло; если Flag=False, значит, стек был пуст и ничего не изменилось.

Процедура не оставляет после себя «мусора», освобождая память из-под удаленных элементов.

Procedure OUTSTEK(Var Beg: Pe; Var Flag: Boolean);

Var X: Pe;

Begin

If Beg=Nil