Лекция 11. Использование динамических структур. Стек, очередь
Общие сведения
Используя указатели и динамическое распределение памяти можно создавать и уничтожать самые разнообразные структуры данных. Примером может служить программа, выполняющая вычисление по формуле, которая вводится с клавиатуры или из файла. Формула хранится в виде бинарного дерева.Динамические структуры (списки, деревья, графы) подробно рассмотрены в учебнике [1]. Примеры в этой лекции построены на основе примеров из этого учебника.
Линейные списки
Рассмотрим 2 вида списков: стек и очередь.Эти списки построены из элементов-записей типа TElement:
type tip_info = <тип данных, хранящий информацию, например: integer>;
PElement = ^TElement;
TElement = record
inf : tip_info;
next : PElement;
end;
Описание типа PElement - пример ИСКЛЮЧЕНИЯ из общего правила, согласно которому неизвестный идентификатор должен появиться сначала в левой части описания (а в правой части - его определение) и только после этого может использоваться в правой части. Здесь в правой части описания находится неизвестный идентификатор TElement. Такое исключение допустимо, если этот неизвестный идентификатор описан в следующей строке.
Существуют понятия: ГОЛОВА списка (первый элемент) и КОНЕЦ списка. Рассмотрим устройство списка и действия с ним.
Для создания такого списка нужна переменная head типа PElement, содержащая адрес
1-го элемента списка. Поле next 1-го элемента списка должно содержать адрес
2-го элемента списка (иначе говоря: ссылаться на 2-й элемент списка) и т д.
Поле next последнего элемента списка должно ссылаться на NIL. Это необходимо для распознавания конца списка.
Заполнение и просмотр списка.
Program spisok1;
type tip_info = string;
PElement = ^TElement;
TElement = record
inf : tip_info;
next : PElement;
end;
Tproc = procedure (SomeElement: PElement);
const head: PElement = nil; {указатель на голову списка.
Используем ТИПИЗИРОВАННУЮ константу}
procedure Insert1 (var SomeElement: PElement; info: string);
{Вставка нового элемента в начало списка. Адрес элемента возвращается
через параметр-переменную SomeElement}
var bufi: string; bufel: PElement;
begin
New(bufel);
bufel^.inf := info;
bufel^.next:= SomeElement;
SomeElement:= bufel;
end;
procedure Browser(SomeElement: PElement; Proc: TProc);
{Перемещение по списку. Для каждого элемента выполняется
процедура Proc (параметр процедурного типа)}
begin
writeln(' ----- Просмотр списка ------ '); writeln;
while SomeElement <> Nil do
begin Proc(SomeElement);
SomeElement:= SomeElement^.next;
end;
end;
{$F+}
procedure ShowElement(SomeElement: PElement);
{Показать информацию, хранимую элементом и его адрес}
var se,of1,ad: longint;
begin
se:= seg(SomeElement^); of1:= ofs(SomeElement^) ; ad:= se*16 + of1;
writeln(SomeElement^.inf:20,' SEG= ',se,' OFS= ',of1,' Адрес = ',ad);
end;
{$F-}
procedure IsertHead(var head: PElement);
var info: string;
begin
writeln('Объем доступной памяти кучи (MemAvail) = ',MemAvail);
info:= 'текст';
while info <> '' do
begin
write ('Введи информацию (текст). Выход - пустая строка ');
readln(info); if info = '' then break;
Insert1 (head,info);
writeln(
'Вставил элемент. Объем доступной памяти = ',MemAvail);
end;
end;
begin {начало главной программы}
IsertHead(head);
Browser(head, ShowElement);
end.
----- Результаты работы -----
Объем доступной памяти кучи (MemAvail) = 294752
Введи информацию (текст). Выход - пустая строка aa
Вставил элемент. Объем доступной памяти = 294488
Введи информацию (текст). Выход - пустая строка bb
Вставил элемент. Объем доступной памяти = 294224
Введи информацию (текст). Выход - пустая строка ccc
Вставил элемент. Объем доступной памяти = 293960
Введи информацию (текст). Выход - пустая строка dddd
Вставил элемент. Объем доступной памяти = 293696
Введи информацию (текст). Выход - пустая строка e
Вставил элемент. Объем доступной памяти = 293432
Введи информацию (текст). Выход - пустая строка
----- Просмотр списка ------
e SEG= 22603 OFS= 0 Адрес = 361648
dddd SEG= 22586 OFS= 8 Адрес = 361384
ccc SEG= 22570 OFS= 0 Адрес = 361120
bb SEG= 22553 OFS= 8 Адрес = 360856
aa SEG= 22537 OFS= 0 Адрес = 360592
Комментарии:Рассмотрим схему вставки нового элемента (см рис 2). Ее выполняет процедура Insert1, которая:
- New(bufel); - выделяет память для хранения нового элемента (из кучи).
- bufel^.inf := info; - Заполняет поле inf созданной записи текстом, переданным через параметр-значение info.
- bufel^.next:= SomeElement; - назначает указателю next адрес, на который ранее указывал указатель SomeElement (см пунктир 1 на рис 2).
- SomeElement:= bufel; - теперь первый фактический параметр (при вызове Insert1, т е формальный параметр head процедуры IsertHead, т е фактический параметр при вызове IsertHead, т е типизированная константа head главной программы) будет указывать на вновь созданный элемент. (см пунктир 2 на рис 2)
Стек и очередь
Стек действует по принципу: последний пришел - первый вышел (LIFO - Last Input => First Output). Так действует магазин карабина и винтовки: патрон, вставленный последним, находится сверху и поэтому первым подается из магазина.Очередь.
Принцип действия (как и положено живой очереди): первый пришел - первый вышел (FIFO).
Примеры программ, работающих со списком:
Подсчет числа элементов списка; поиск элемента; включение элемента в заданном месте. - Универсальная программа, содержащая все операции и меню - для выбора операции.
