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

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

____________________________________________________________________

Pop_Stack. Сначала реализуем стек с помощью массива, рисунок 4.26.

N Глубина стека Рис. 4.26 Реализация стека на основе массивов.

Из рисунка видно, что для реализации стека нам нужны два массива, мас-

сив-указатель, назовем его ukaz[1..3] и массив-тело стека, назовем его

CTEK. Для определенности пусть он состоит из 100 элементов, т.е. глубина сте-

ка равна 100 элементам. Пусть, также для определенности, элементами стека являются просто целые числа. На практике элементами стека могут являться и более сложные структуры, например, записи. В массиве ukaz первый элемент,

т.е. ukaz[1] содержит индекс массива СТЕК, равный началу стека, обычно это

1. Элемент ukaz[3] содержит индекс массива СТЕК, равный концу стека, т.е.

заданной глубине стека N = 100 и обычно совпадает с максимальным размером массива СТЕК. Элемент массива ukaz[2] – это индекс в массиве СТЕК, куда будет помещен новый элемент стека, а ukaz[2]-1 это индекс, по которому из

СТЕК можно будет взять последний помещенный в него элемент.

Программа будет выводить на экран меню, с помощью которого можно помещать новый элемент в стек, брать элемент из верхушки стека и просматри-

341

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

____________________________________________________________________

вать весь массив стека.

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

CRT, FileUtil; const

SizeOfArray = 100; type

c= array[1..SizeOfArray] of integer; u= array[1..3] of integer;

var

choose: integer; EMPTY: boolean; ERROR: boolean; CTEK: c;

ukaz: u; ELEM: integer;

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

var ukaz: u; var ERROR: Boolean); { ================================================= }

var k: integer; begin

if ukaz[2] > ukaz[3] then ERROR:= true

else begin

342

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

____________________________________________________________________

k:= ukaz[2]; CTEK[k]:= ELEM; ukaz[2]:= k + 1;

end;

end;

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

var ukaz: u; var EMPTY: Boolean); { ================================================== } var k: integer;

begin

if ukaz[2] <= ukaz[1] then EMPTY:= true

else begin

k:= ukaz[2] - 1; ELEM:= CTEK[k]; ukaz[2]:= k;

end;

end;

procedure View_Stack(var CTEK: c; var ukaz: u); var

i: integer; begin

writeln(UTF8ToConsole('Массив стека')); for i:= 1 to ukaz[2] - 1 do

write(CTEK[i], ' '); writeln;

343

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

____________________________________________________________________

end;

begin

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

ukaz[1]:= 1;

ukaz[2]:= 1;

ukaz[3]:= SizeOfArray;

repeat

EMPTY:= false;

ERROR:= false;

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

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

Put_Stack(ELEM, CTEK, ukaz, ERROR); if ERROR then

begin

writeln(UTF8ToConsole('Переполнение стека.')); writeln(UTF8ToConsole('Увеличьте размер массива')); writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end;

end;

344

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

____________________________________________________________________

2: begin

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

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

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

end;

3: View_Stack(CTEK, ukaz); end; { end of case }

until choose = 4; end.

Процедура Put_Stack просто помещает новый элемент в массив СТЕК по индексу ukaz[2] и затем увеличивает значение этого индекса на единицу.

Перед этим процедура проверяет стек на переполнение, т.е. не перешли ли мы за пределы массива СТЕК.

Процедура Take_Stack возвращает элемент массива СТЕК с индексом ukaz[2]-1 и уменьшает значение индекса на единицу. Перед этим она прове-

ряет не пуст ли уже стек.

Если внимательно присмотреться к процедурам Put_Stack и Take_Stack, то возникает вполне резонный вопрос, а зачем, собственно гово-

ря, здесь нужен массив-указатель ukaz? И мы будем абсолютно правы. При реализации стека вполне можно обходиться одним массивом, только для раз-

мещения элементов стека. А в качестве указателя использовать простую цело-

численную переменную, которую назовем также ukaz. Вот листинг другой,

улучшенной реализации стека:

345

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

____________________________________________________________________

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

CRT, FileUtil; const

SizeOfArray = 100; type

c= array[1..SizeOfArray] of integer; var

choose: integer; EMPTY: boolean; ERROR: boolean; CTEK: c;

ukaz: integer; ELEM: integer;

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

var ukaz: integer; var ERROR: Boolean); { =================================================== }

begin

if ukaz > SizeOfArray then ERROR:= true

else begin

CTEK[ukaz]:= ELEM; ukaz:= ukaz + 1;

end;

end;

346

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

____________________________________________________________________

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

var ukaz: integer; var EMPTY: Boolean); { ================================================== }

begin

if ukaz = 1 then EMPTY:= true

else begin

ukaz:= ukaz - 1; ELEM:= CTEK[ukaz];

end;

end;

procedure View_Stack(var CTEK: c; var ukaz: integer); var

i: integer; begin

writeln(UTF8ToConsole('Массив стека')); for i:= 1 to ukaz - 1 do

write(CTEK[i], ' '); writeln;

end;

begin

{Инициализация указателя стека (начального индекса в массиве)}

ukaz:= 1;

repeat

EMPTY:= false;

347

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

____________________________________________________________________

ERROR:= false;

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

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

Put_Stack(ELEM, CTEK, ukaz, ERROR); if ERROR then

begin

writeln(UTF8ToConsole('Переполнение стека.')); writeln(UTF8ToConsole('Увеличьте размер массива')); writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end;

end; 2: begin

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

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

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

ELEM);

end;

3: View_Stack(CTEK, ukaz);

348

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

____________________________________________________________________

end; { end of case }

until choose = 4;

end.

В этой реализации переменная ukaz является индексом (указателем) вер-

хушки стека и одновременно показывает количество элементов в стеке, т.е. оп-

ределяет фактический размер массива. Для того чтобы поместить элемент в стек, мы записываем его в массив CTEK по индексу ukaz и увеличиваем ukaz

на единицу. Для того чтобы взять элемент из стека процедура Take_Stack

должна уменьшить значение ukaz на единицу и возвратить элемент с индексом ukaz. Таким образом, указатель (индекс в массиве) расположен так, как пока-

зано на рисунке 4.26.

Существенным недостатком представления стека векторным способом яв-

ляется необходимость задания максимальной глубины стека, поскольку не все-

гда известна точная глубина стека. Отсюда необходимость задания глубины стека с "запасом", т.е. память используется нерационально. Достоинство – от-

носительная простота работы со стеком.

4.3.3 Представление двоичного дерева в виде массива и реализация алго-

ритма обхода двоичного дерева слева.

Деревья наиболее важные структуры, используемые в программировании.

Поэтому крайне необходимо освоить технику работы с ними. Здесь мы рас-

смотрим представление дерева с помощью массива.

Пусть имеется дерево, рис. 4.27.

349

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

____________________________________________________________________

Рис. 4.27. Двоичное дерево. В качестве вершин выступают целые числа

В этом дереве вершинами являются просто целые числа, хотя в качестве вершин могут выступать любые объекты. Представим наше дерево в виде, рис.

4.28. Отсюда возникает идея хранить в массиве не только саму вершину, но и индексы левого и правого поддерева. Таким образом, каждый элемент массива представляет собой тройку чисел – корень и индексы в массиве левого и право-

го поддерева. Если левое или правое поддеревья пустые, то индекс равен -1

(аналог nil).

1

8 x x 9 x x 10 x x 11 x x 12 x x 13 x x 14 x x 15 x x

Рис. 4.28. Схема представления двоичного дерева с помощью массива

Внимательно присмотритесь к рисунку. Фактически это похоже на связан-

ный список, только вместо указателей мы используем индексы массива. Пред-

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

350