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

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

____________________________________________________________________

view_MyList (pHead);

writeln;

end;

end; { end of case }

until choose = 5;

writeln(UTF8ToConsole('Нажмите любую клавишу'));

readkey;

end.

Кроме того, часто встречаются особые списки, где добавление или удале-

ние элементов производится только в начале или в конце списка. Какие это списки:

линейный список, в котором добавление или удаление элементов про-

изводится только в одном конце. Читатель, наверное, уже догадался, что это есть не что иное, как стек!

линейный список, в котором добавление элементов производится на од-

ном конце, а удаление на противоположном конце списка. Если внима-

тельно подумать, то работа такого списка будет напоминать живую оче-

редь людей в магазине. Поэтому такой список так и называют – очередь.

Часто очередь называют структурой FIFO (First In - First Out, т.е. "первый пришел, первый ушел").

линейный список, в котором все добавления и удаления производятся с обоих концов списка. Такой список носит название дек.

Реализуем рассмотренные динамические структуры с помощью линейных списков.

371

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

____________________________________________________________________

4.3.6 Реализация динамических структур линейными списками

4.3.6.1. Реализация стека

Для того чтобы поместить элемент в стек, достаточно написать следующий

код:

New(p); // Резервируем память для нового элемента p ^.data:= ELEM; //Записываем данные

p^.next:= CTEK;// устанавливаем ссылку на текущую вершину стека

CTEK:= p; // Теперь новый элемент стал верхушкой стека Для того чтобы взять элемент из верхушки стека, необходим код:

if CTEK <> nil then // Если стек не пуст begin

ELEM:= CTEK^.data; // Взять элемент

p:= CTEK^.next; // Указатель на следующий элемент

Dispose(CTEK);// Удалить текущий элемент из вершины стека

CTEK:= p; //Предыдущий элемент сделать вершиной стека

Приведем полный листинг программы работы со стеком:

program stack; {$mode objfpc}{$H+} uses

CRT, FileUtil; type

c = ^ MyStack; // указатель

MyStack = record // структура записи data: integer; // содержательная часть стека

372

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

____________________________________________________________________

next: c; // ссылка на следующий элемент end;

var

choose: integer; EMPTY: boolean;

CTEK: c; // указатель, указывает на вершину стека ukaz: c; // рабочий указатель

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

{================================================ } procedure Put_Stack(var ELEM: integer; var CTEK: c);

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

begin

New(ukaz); // создаем новый элемент стека

ukaz^.data:= ELEM; // В поле data записи записываем значение ukaz^.next:= CTEK; // ссылка на следующий элемент

CTEK:= ukaz; // вершиной стека становится новый элемент end;

{ ================================================ } procedure Take_Stack(var ELEM: integer; var CTEK: c;

var EMPTY:Boolean);

{ ================================================ } var ukaz: c;

begin

if CTEK <> nil then begin

ELEM:= CTEK^.data; // Берем элемент из вершины стека ukaz:= CTEK^.next; // Указатель на следующий элемент

Dispose(CTEK); // уничтожение текущей вершины

373

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

____________________________________________________________________

CTEK:= ukaz; // вершиной стека становится следующий элемент

end

else EMPTY:= true;

end;

procedure View_Stack(var CTEK: c);

var ukaz: c;

begin

writeln(UTF8ToConsole('Содержимое стека')); ukaz:= CTEK; // Берем вершину стека

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

begin

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

end;

writeln;

end;

begin

{Инициализация стека}

CTEK:= nil;

repeat

EMPTY:= false;

writeln(UTF8ToConsole('Выберите нужный режим работы :'));

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

374

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

____________________________________________________________________

case choose of 1: begin

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

Put_Stack(ELEM, CTEK); end;

2: begin

Take_Stack(ELEM, CTEK, EMPTY); if EMPTY then

begin

writeln(UTF8ToConsole('Стек пуст'));

end

else

begin

writeln(UTF8ToConsole('Из стека взят элемент '),

ELEM);

end;

end; 3: begin

View_Stack(CTEK); end;

end; { end of case } until choose = 4;

end.

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

Проще всего для этого завести два указателя. Указатель на первый элемент очереди first и указатель на последний элемент очереди last. Листинг про-

граммы:

375