Реализация стека через односвязный линейный список
Стек можно рассматривать как частный случай односвязного линейного списка, для которого разрешено добавлять и удалять элементы только с одного конца, а именно с головы. Каждый элемент стека хранится в записи с двумя полями:
inf, содержащего сам элемент, и next, содержащего указатель на запись со следующим элементом.
Указатель Top ссылается на запись, находящуюся в вершине стека.
type ref=^Elem; {Тип указателя на элементы стека}
Elem = record {Тип элемента стека}
inf:integer; {Поле для информации}
next:ref {Поле для указателя на следующий элемент}
end;
var Top:ref;
procedure DoTop; //Создание пустого стека}
begin
Top:=nil
end;
function IsEmpty:boolean; //Проверка, пуст ли стек
begin
Result:=(Top=nil)
end;
procedure Push(x:integer); //Занесение числа x в стек
var p:ref;
begin
new(p);
p^.inf:=x;
p^.next:=Top; {Новый элемент стека указывает на прежнюю вершину стека}
Top:=p {Указатель вершины стека установлен на новый элемент стека}
end;
function Pop:integer; //Выборка из стека целого числа
var p:ref;
begin
Result:=Top^.inf; //Значение из вершины стека
p:=Top;
Top:=Top^.next; //Исключение верхнего элемента
dispose(p) //Освобождение динамической памяти, которую занимал элемент из вершины стека
end;
function InTop:integer; //Просмотр элемента в вершине стека без удаления}
begin
Result:=Top^.inf; //Значение из вершины стека
end;
procedure Swap; //Перемена местами двух элементов в вершине стека
var x:integer;
begin
x:=Top^.inf;
Top^.inf:=Top^.next^.inf;
Top^.next^.inf:=x;
end;
Применение стеков
Стеки используют при синтаксическом анализе текста в компиляторах, при вычислении выражений. Через стек реализован вызов подпрограмм: подпрограмма, вызванная последней, первой заканчивает работу.
Пример. Пусть имеется текстовая строка, сбалансированная по круглым скобкам. Необходимо вывести таблицу, в каждой строке которой будут находиться координаты соответствующих пар скобок, т.е. номера символов ‘(‘ и ‘)’ в строке.
Будем посимвольно просматривать строку и как только встретим открывающую скобку ‘(‘, занесем ее координату в стек. При встрече закрывающей скобки ‘)’ возьмем из стека верхний элемент (это координата открывающей скобки) и выведем ее в таблицу вместе с координатой данной ‘)’. Если при попытке взятия из стека он окажется пустым, а после завершения просмотра строки, наоборот, не пустым, число открывающих и закрывающих скобок не совпадает.
Допустим, имеем строку
| ( | a | + | b | * | c | ) | / | - | ( | a | + | b | ) | * | ( | d | + | c | / | ( | f | - | g | ) | ) | |
Должна быть получена таблица:
Откр Закр
1 7
11 15
22 26
17 27
procedure Error;
begin writeln(‘Число открывающих и закрывающих скобок
не совпадает’);
halt {Прекращение работы программы}
end;
begin {программа}
DoEmpty; {Создание пустого стека}
write(‘Введите строку’); readln(S);
for i:=1 to length(S) do
begin
if S[i]=‘(‘ then Push(i); {Занесение в стек номера символа ‘(‘}
if S[i]=‘)‘
then if not IsEmpty {Стек не пуст при встрече ‘)’}
then writeln(Pop:4,i:4) {Вывод координаты ‘(‘ из стека и координаты ‘)’}
else Error
end;
if not IsEmpty then Error {Если стек не пуст после завершения просмотра строки}
end.
Реализация стека на основе массива
Реализуем стек на одномерном целочисленном массиве AS длины nAS. Указатель на вершину стека Top может принимать значения в диапазоне 0..nAS. Стек пуст, когда Top=0.
const nAS=100;
var Top: 0..nAS;
AS:array[1..nAS] of integer;
Procedure DoTop;
begin Top := 0
end;
function Empty:boolean;
begin Result:=(Top=0)
end;
procedure Push (i: integer);
begin
Top:=Top+1;
AS[Top]:=i;
end;
function Pop: integer;
begin
Result:=AS[Top];
Top:=Top-1;
end;
Деревья
Основные определения
Дерево – это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родитель–сын), образующих иерархическую структуру узлов.
Рекурсивное определение дерева: Дерево – это либо пустая структура, либо узел, с которым связано конечное число деревьев, называемых поддеревьями.
Тип узла называется базовым типом дерева.
Примеры деревьев: файловая система, словарь, календарь, структура университета.
Виды узлов дерева:
• Предок узла y – это узел, из которого исходит дуга, заходящая в узел y.
• Потомок узла x – это узел, в который заходит дуга, исходящая из узла x.
• Корень дерева – узел, не имеющий предков.
• Терминальный узел (или лист) – узел, не имеющий потомков.
• Нетерминальные (внутренние) узлы – все узлы, кроме корня и терминальных узлов.
Уровни дерева:
• Корень дерева расположен на уровне 0.
• Если узел X находится на уровне i, то его потомок Y – на уровне i+1.
• Глубина (высота) дерева – максимальный уровень из уровней всех узлов.
Степени узлов дерева:
• Степень узла – число непосредственных потомков узла.
• Степень дерева – максимальная степень всех узлов.
Упорядоченным деревом называется дерево, у которого дуги, исходящие из каждого узла, упорядочены.
Это разные упорядоченные деревья
Бинарные деревья
Бинарное дерево – это упорядоченное дерево степени 2, где каждый узел связан с двумя бинарными деревьями, называемыми левым поддеревом и правым поддеревом.
Для краткости бинарные деревья будем называть просто «деревьями».