Статическая реализация стеков.

Стек – динамический тип данных – количество элементов, которое можно положить в стек, не ограничено (в идеале), но во многих случаях, в том числе в задаче о раскраске карты, известна максимальная глубина стека, то есть стек можно понимать статически. Стандартный приём оперировать с такими типами (абстрактными, но статическими) – моделировать их массивами и переменными стандартных типов.

top heap

  nMax

Куча

type index=1..nMax{ };

T={базовый тип стека};

tStack= record

content: array[index] of T;

heap:index;{указатель на начало «кучи», первую свободную компоненту массива}

end;

procedure push(var stack:tStack;x:T);

begin

with Stack do

begin

content[heap]:=x;

inc(heap);

end;

end;

Реализация не защищена от ошибки – переполнения стека. Предполагается, что ситуацию контролирует пользователь.

procedure pop(stack:tStack;var x:T);

begin

with stack do

begin

dec(heap);

x:=content[heap];

end;

end;

Снова незащищённая реализация: контроль за пустотой стека возлагается на пользователя.

function empty(stack:tStack):boolean;

begin

empty:=stack.heap=1;

end;

procedure init(stack:tStack);{инициализация стека}

begin

stack.heap:=1;

end;

Очереди. Статическая реализация.

Ещё один популярный абстрактный тип данных с простой реализацией.

Множество значений: все конечные последовательности t₁,…,t_n – значения некоторого типа T.

Операции: get и put

Put(q:tQueue;x:T) – поставить в очередь.

Семантика:

{q<t₁,…,t_n>,xX}

{q<x,t₁,…,t_n>,xX}

Get(q:tQueue;var x:T) – вывести из очереди.

Семантика:

{q<t₁,…,t_n>,xX}

{q<t₁,…,t_n-1>,xt_n}

function Empty(q:tQueue):boolean;

procedure Init(q:tQueue);

Семантика как у стеков.

Упражнение. Используя очередь, обратить файл (небольшой длины), то есть вывести его элементы в обратном порядке. Осуществить циклический сдвиг последовательности на заданное количество разрядов.

c₁c_2…c_k



c_kc₁…c_k-1

Реализация:

const cStart=1;cFinish={максимальная длина очереди};

type tIndex=cStart..cFinish;

T={ };

tQueue=record

content:array[tIndex] of T;

heap:index;

first:index;{указатель на первый элемент – начало очереди}

end;

procedure put(q:tQueue;x:T);

begin

with q do

begin

content[heap]:=x;

if heap<cFinish then inc(heap)

else heap:=cStart;

end;

end;

Реализация не защищена от переполнения.

procedure get(q:tQueue;var x:T);

begin

with q do

begin

x:=content[first];

if first<cFinish then inc(first)

else first:=cStart;

end;

end;

Статическая реализация деревьев.

Рассмотрим случай бинарных деревьев (остальные – аналогично).

1

о

2 3 Нумерация в ширину

о о

4 5 6 7

о о о о

const cEmpty=-1; {Признак отсутствия вершины}

type tNodeInfo={Атрибуты вершины и, если нужно, единственные исходящие из неё стрелки}

tIndex=0..nMax; {=2ⁿ, n-число уровней (поколений) дерева}

tTree=record

content=array[1..nMax] of tNodeInfo;

root:index;

end;

function left(t:tTree;c:tIndex):tIndex;

{Найти индекс левого потомка}

begin

left:=2c;

end;