Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.3 Динамические структуры данных

____________________________________________________________________

program queue; // queue означает по английски очередь

{$mode objfpc}{$H+} uses

CRT, FileUtil; type

PQueue = ^Element; // указатель

Element = record // структура записи

data : integer; // содержательная часть очереди next : PQueue; // ссылка на следующий элемент end;

TQueue = record // структура для реализации очереди

first: PQueue; // указатель, указывает на первый элемент очереди last: PQueue; // указатель, указывает на последний элемент очереди end;

{============================================= } procedure Put_Que(ELEM: integer; var Que: TQueue);

{============================================= }

var ukaz: PQueue; // временный указатель

begin

if (Que.last = nil) then

{Если очередь пуста, то указатели на первый и последний элемент будут совпадать}

begin

{Выделяем память для нового элемента}

Que.last:= New(PQueue);

Que.first:= Que.last; // Приравниваем указатели

Que.last^.data:= ELEM; // записываем данные

376

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Que.last^.next:= nil; // Следующий элемент пока пустой end

else begin

ukaz:= New(PQueue); ukaz^.data:= ELEM; ukaz^.next:= nil;

Que.last^.next:= ukaz; // ссылка на следующий элемент

Que.last:= ukaz; // Сдвигаем указатель на последний элемент end;

end;

{ ================================================== } procedure Take_Que(var ELEM: integer; var Que: TQueue;

var EMPTY:Boolean);

{ ================================================== }

var ukaz: PQueue; begin

if (Que.first = nil) then begin

EMPTY:= true; end

else begin

ELEM:= Que.first^.data; {Первый элемент очереди} ukaz:= Que.first; // Запомним ссылку

Que.first:= Que.first^.next; {переход на следующий элемент}

377

4.3 Динамические структуры данных

____________________________________________________________________

Dispose(ukaz); {уничтожение текущего элемента} end;

end;

{================================ } procedure View_Que(var Que: TQueue);

{================================ }

var

ukaz: PQueue; begin

writeln(UTF8ToConsole('Содержимое очереди')); ukaz:= Que.first; // Берем первый элемент очереди

{В цикле проходим все элементы очереди и печатаем их} while ukaz <> nil do

begin

write(ukaz^.data, ' '); ukaz:= ukaz^.next;

end;

writeln;

end;

var

choose: integer; EMPTY: boolean; Que: TQueue;

ELEM: integer; // содержательный элемент очереди begin

{Инициализация очереди}

378

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Que.last:= nil;

repeat

EMPTY:= false;

writeln(UTF8ToConsole('Выберите нужный режим работы :')); writeln(UTF8ToConsole('Поместить элемент в очередь 1'));

writeln(UTF8ToConsole('Взять элемент из очереди 2'));

writeln(UTF8ToConsole('Просмотреть содержимое очереди 3'));

writeln(UTF8ToConsole('Введите новый элемент')); readln(ELEM);

Put_Que(ELEM, Que); end;

2: begin

Take_Que(ELEM, Que, EMPTY); if EMPTY then

begin

writeln(UTF8ToConsole('Очередь пуста'));

end

else

begin

writeln(UTF8ToConsole('Из очереди взят элемент '),

ELEM);

end;

end; 3: begin

View_Que(Que);

379

4.3 Динамические структуры данных

____________________________________________________________________

end;

end; { end of case }

until choose = 4;

end.

Реализация дека теперь для вас не представляет такой уж сложной задачей.

Попробуйте реализовать его самостоятельно.

4.3.6.3. Реализация двоичного дерева с помощью линейного списка

Двоичное дерево можно представить с помощью двухсвязного списка сле-

дующим образом:

left: PTree; // Ссылка на левое поддерево right: PTree; // Ссылка на правое поддерево end;

Здесь для разнообразия в качестве значений вершин мы взяли строки сим-

волов. Напишем рекурсивную процедуру поиска вершины по его значению:

procedure search_node(Elem: string;

ptr_tree: PTree;

var current_tree: PTree);

var

p: ^Tree; // рабочий указатель begin

380