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

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

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

Множество значений: все конечные последовательности 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;

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

о

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;

Автоматы как структуры данных

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

Возможные операции над доступными вершинами:

1) Чтение атрибутов вершины и исходящих из неё стрелок.

2) Запись новых атрибутов.

3) Добавить/удалить вершину (стрелку) (с пустыми атрибутами).

Понятие доступа продолжается и на возможность выполнения операций: доступ для чтения/записи и т.д. Понятие доступа обычно формулируется в терминах некоторого набора элементов (маркеров) или головок автомата, значениями которых служат вершины автомата и некоторые могут передвигаться в соответствие с (функцией переходов) определением автомата. Фактически мы пришли к знакомому понятию состояния. Поэтому вместо «состояния» используют понятие конфигурации автомата (чтобы не путать с вершинами).

Дата добавления: 2014-01-05