Реализация стеков и очередей списками.

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

type

tComponent=record value:T;next:p:pComponent end;

pComponent=^tComponent;

pStack=pComponent; {ссылка на голову - первую или "верхнюю" компоненту списка}

 

procedure create(var Stack: pStack); begin Stack:=nil end;

 

procedure push (var Stack: pStack; x:T);

var p:pComponent;

begin

new(p); p^.value:=x; p^.next:=Stack; Stack:=p

end;

 

{ стек предполагается непустым }

procedure pop(var Stack: pStack; var x:T);

var p:pComponent;

begin

p:=Stack; x:=Stack^.value; Stack:=Stack^.next; dispose(p); {сборка мусора}

end;

 

function empty(Stack: pStack): boolean; begin empty:= Stack=nil end;

 

{Реализация очередей.}

 

type

tQueue= record Нулевой, Последний: pComponent end;

{указатели на начало и конец очереди}

 

{предусловие: первый элемент существует}

{для этого при создании добавляем нулевой фиктивный элемент, "фантом"}

procedure Put(var Queue: tQueue; x: T); { Поставить В Очередь }

var p:pComponent;

begin

new(p); p^.next:=nil; p^.value:=x;

with Queue do begin Последний^.next:=p; Последний:=p end;

end;

 

procedure Create(var Queue: tQueue);

begin

with Queue do

begin

new(нулевой); {нулевой элемент - фиктивный}

нулевой^.next:=nil;

последний:=нулевой

end;end;

 

function Empty(Queue:t Queue):boolean;

begin with Queue do empty:=нулевой=последний end;

 

procedure Get(Queue: tQueue; var x: T);{ Вывести Из Очереди }

{предполагается, что очередь не пуста; аналогична pop, но надо не забыть про фантом}

var первый:pComponent;

begin

with Queue do

begin

первый:=нулевой^.next;

x:=первый^.value;

нулевой^.next:= первый^.next;

dispose(первый); {сборка мусора}

end; end;

 

 

Алгоритмы полного перебора.

 

Пусть T - множество значений некоторого порядкового типа, T={Первый<Второй<…Последний}, succ - соответствующая функция следования, а Seq(L)=Seq(T,L)=[1..L]àT - множество всех последовательностей длины L.

 

Лексикографический, или словарный порядок на Seq(L) определяется следующим образом. Пусть a,b Î Seq(n), a¹b и N=N(a,b)=min {n: a(n) ¹b(n)}- наименьший номер i, на котором они различаются. Тогда a считается меньшей b, если у а на N-ом месте стоит меньшая (в смысле порядка на T) компонента, чем у b: a<b»def a(N)<_T b(N).

 

Пример. T=кириллица (русский алфавит), последовательности символов - слова. Тогда 'шабаш'< 'шалаш' (в Seq(T,5)).

 

Алгоритм определения следующей последовательности.

 

Следующая(a)=b» найдется число N такое, что для всех i, i Î [1..N], b(i)=a(i), b(N)=succ(a(N)) и b(j)=Первый, для всех j, j Î [N+1..L]. Причем, нетрудно заметить (и доказать), что N в этом случае определяется однозначно - N=max{i:a(i) ¹Последний}.

Идея вычисления функции Следующая:

a) Вынимай из конца последовательности а все последние (в T) значения, пока не найдешь меньшего значения с. Если такого значения с нет, то а - это последняя последовательность.

б) Положи в конец a значение succ(c)

в) Доложи в конец последовательности необходимое число первых значений.

Пример. Построим следующее за 00011 слово (в Seq({0<1},5) - после шага a) получаем 00, после б) 001, после в) - 00100.

 

Обработка последовательностей "с одного конца", как мы помним, реализуется в терминах стеков (см. "Абстрактные линейные типы").

 

{exists,a:=$ b (b=Следующая(a)), Следующая(a)}

{ясно, exists=$ jÎ [1..LenA] (a(j)<>Последний}

{pa - ссылка на содержимое стека, содержащего последовательность а}

{LenA - константа, длина последовательности}

procedure Следующая(pa:pSeq; exists:boolean);

var

i:integer; {число вынутых компонент}

x:T; {значение последней компоненты}

begin

i:=0; exists:=false;

{a} while (i<=LenA) and not found do

begin pop(pa,c); i:=i+1; if c<>Последний then exists:=true end;

if exists

then begin {b} push(pa,succ(c));

{c} while i<>0 do begin push(pa,Первый);i:=i-1 end

end;

 

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

 

Задача о раскраске графа. Найти ("распечатать") все правильные раскраски произвольного графа с фиксированным числом вершин n (если таковые найдутся) в m цветов. Раскраска правильная, если никакие две соседние (т.е. связанные некоторым ребром) вершины не окрашены в один цвет.

 

Предварительный анализ

found=$ r Î tРаскраска (правильная(r))

где Правильная(r)= " i,jÎ Вершины (Соседи(i,j)àЦвет(r,i)¹ Цвет(r,j))

 

Следующий алгоритм полного перебора раскрасок - тривиальное кратное обобщение задачи поиска (см. "Поиск" и "Вычисление свойств")

 

function Правильная (r:tРаскраска):boolean;

begin

b:=true;

i:=ПерваяВершина;

while (i<=pred(ПоследняяВершина)) and not b do

begin j:=succ(i);

while (j<=ПоследняяВершина) and not b do

if Coседи(i,j) and (Цвет(r,i)=Цвет(r,j))

then b:=false else j:=succ(j);

i:=succ(i)

end;

 

procedure ПолныйПеребор (graph:tGraph; var found:boolean);

var r: tРаскраска; exists:boolean; {}

begin

r:=ПерваяРаскраска; found:=false; exists:=true;

while exists (= not КончилисьРаскраски} do

begin if Правильная(r) then begin found:=true; Печать(r) end

Следующая(r,exists) {r:=Следующая(r)}

end;

end;

 

Дальнейший анализ.

Тип tВершины должен быть порядковым - можно, например пронумеровать все вершины - tВершины=1..n;

Тип tGraph хорошо бы реализовать так, чтобы было легко вычислять функцию Соседи: tВершины ´ tВершины à Boolean. Хороший вариант - задать граф матрицей инциндентности (т.е. табличным определением функции Соседи)

tGraph=array[tВершины, tВершины] of Boolean;

Тип tРаскраска хорошо бы реализовать так, чтобы было легко вычислять цвет каждой вершины r: tВершиныàtЦвет (реализация типа tЦвет произвольна, лишь бы было определено равенство, пусть tЦвет=1..m).

Хороший вариант tРаскраска=array[tВершины] of tЦвет= array[1..n] of tЦвет, но тип array - не порядковый, что требуется нашим алгоритмом. Но - теперь мы умеем организовать перебор последовательностей с помощью стековых операций.

Вывод - реализовать раскраски как стек (который, в свою очередь, в данном случае лучше реализовать массивом).

 

Опустив детали реализации, подведем некоторые предварительные итоги решения. Алгоритм прост, но малоэффективен. Перебор всех mⁿ раскрасок - функций/последовательностей [1..n]à[1..m] - дело долгое.

 

Перебор с возвратом.

 

Как сократить область перебора в переборных алгоритмах? Вернемся к решению задачи о раскрасках карты из § 12 (здесь - повторить постановку и вкратце идею и «дефект» решения алгоритмом полного перебора).

 

Идея сокращения проста, но изящна - рассматривать неполные раскраски - динамические последовательности, т.е. функции [1..k]à[1..m], k£n. Основание - если (неполная) раскраска r уже не правильна, нет никакого смысла терять время на перебор раскрасок большей длины.

 

Для этого доопределим лексикографический порядок на последовательностях Seq произвольной длины, Seq= È {Seq(L):LÎN}. Пусть снова a,b Î Seq - теперь, вообще говоря, разной длины LenA и LenB, a¹b и N=N(a,b)=min {n: a(n) ¹b(n)}- наименьший номер i, на котором они различаются. Тогда a<b, если

a) Либо NÎ Dom(a) (N £ LenA), NÎ Dom(b) (N £ LenB) и a(N)<_T b(N).

b) Либо NÎ Dom(a) (N £ LenA) и NÏ Dom(b) (N > LenB), т.е. a - начальный отрезок последовательности b

(можно свести все к "старому" случаю a), если мысленно доопределить последовательность меньшей длины добавленным в T "пустым" значением Æ, сделав его минимальным Æ =Нулевой=pred(Первый))

Пример. 'шабаш'<'шабашка', 'шабаш'<'шалаш'

Алгоритм определения следующей последовательности - полностью повторяет прежний, за исключением пункта в) (теперь нам не зачем доопределять следующее значение до фиксированной длины). Операцию перехода к следующему значению в таком порядке принято называть возвратом.

 

procedure ПереборCВозвратом (graph:tGraph; var found:boolean);

var r: tРаскраска; exists:boolean;

begin

r:=ПерваяРаскраска; {заметь - теперь это пустая последовательность!}

found:=false; exists:=true;

while exists {= not КончилисьРаскраски длины менее n} do

begin if Правильная(r)

then if Полная(r) {т.е. длины n}

then begin found:=true; Печать(r) end

else { дополнить - добавить первое значение в T}

Push(r, Первый)

else {не правильная} Возврат (r, exists) {=Следующая(r,exists)}

end;

end;

 

Замечание. Экзаменатор вправе потребовать довести реализацию до конца!

 

Нелинейные типы данных.

 

Существует много определений одних и тех же (с точки зрения математики) содержательных (интуитивных) понятий. Так, под графами мы содержательно подразумеваем визуальные (зрительное) понятие - диаграммы, состоящие из вершин и соединяющих их ребер - отрезков (неориентированный граф) или стрелок (ориентированный граф).

 

С формальной стороны, (ориентированный/неориентированный) граф можно отождествлять с множеством его ребер Arrows, а последнее, в свою очередь с некоторым (произвольным/симметричным) бинарным отношением, т.е. подмножеством декартового квадрата (множества всех пар) Nodes´Nodes:

" a,bÎ Nodes

(<a,b>Î Arrows» в графе есть стрелка, ведущая из вершины a в вершину b)

Так определенный граф мы, скорее всего, реализуем т.н. функцией инциндентности (соседства) - предикатом Nodes´NodesàBoolean, а последний - булевским массивом

type

tArrows=array[tNodes,tNodes] of boolean;

{при реализации симетричного отношения желательны треугольные массивы, в Паскале отсутствующие}

С другой стороны, граф можно отождествлять с функцией перехода из вершины по данному ребру GoÎArrows´NodesàNodes, для некоторого множества ребер Arrows и множества вершин Nodes:

" rÎ Arrows " a,bÎ Nodes (Go(r,a)=b» ребро r ведет из вершины a в вершину b)

Так определенные диаграммы мы будем называть автоматами (без выхода). При этом вершины из Nodes обычно понимаются как маркировка/именование состояний некоторого объекта, а стрелки - маркировкой некоторых элементарных преобразований состояний.

 

И, соответственно, Go - обозначением операции аппликации (применения функции к аргументу). Ясно, что здесь неявно подразумевается некоторая система обозначений значений и их преобразований, т.е. обозначение некоторого типа данных. Для программиста теория автоматов важна именно в качестве теории обозначений типов данных.

 

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

 

Работа (функционирование) автомата описывается индуктивно определяемой функцией Go*ÎArrow*´NodesàNodes. При этом конечные последовательности из Arrow* понимаются как пути в диаграмме или же - трассы преобразований состояний (см. и сравни "Поиск").

 

type

tArrows=1..nMaxArrows;

tNodes=1..nMaxNodes;

{реализация автомата массивами}

tAutomaton=array[tArrows,tNodes] of tNodes;

{реализация автомата ссылками}

pAutomaton=pNode; {ссылка на начальное состояние автомата - см. a),b) ниже}

pNode=^tNode;

tNode=record

Content:T;{содержимое вершины/ определение значения состояния}

Arrows:array[tArrows] of pNode;

{последовательность исходящих стрелок, реализованная массивом}

{динамический вариант - линейный список}

end;

Здесь нас интересуют графы/автоматы специального вида - бинарные деревья (общую теорию графов и автоматов см. курс дискретной математики). Автомат Go - дерево, если существует корневая вершина (начальное состояние автомата) Æ,

a) в которую не ведет ни одно ребро, " aÎ Nodes (Go(r,a)=Æ à a=Æ),

b) но из которой существует путь в любую вершину,

" aÎ Nodes $ rÎ Arrows (Go(r,Æ)=a),

причем этот путь - единственный, " r,r'Î Arrows (Go(r,Æ)=Go(r',Æ) à r=r').

Go - бинарное дерево, если, к тому же, множество стрелок состоит из лишь из двух стрелок, далее обозначаемых как левая (left) и правая (right), Arrows={left,right}.

 

Другие возможные обозначения: Arrows={0,1} или Arrows={true,false}. При желании и возможности дайте также графовое определение понятие дерева - в частности, рекурсивное определение, соответствуюющее диаграмме ниже.

 

{реализация бинарного дерева ссылками}

pTree=pNode; {дерево задается ссылкой на корень}

pNode=^tNode;

tNode=record

Content:T;{содержимое вершины}

left,right: pNode;

end;

 

Задача обхода дерева заключается в переборе его вершин в некотором порядке, т.е. построении некоторой функции следования (счета) на Arrows*´Nodes.

 

Самый простой, но исключительно важный класс таких порядков связан с лексикографическим порядком на множестве "слов"/путей Arrows* (см. "Перечисление последовательностей"), связанных со всеми возможностями определения такого порядка на "алфавите" - множестве Arrows.

(По старой программистской традиции мы рисуем деревья "вверх тормашками"). Так, при КЛП-обходе для любого поддерева исходного дерева корень обрабатывается (идет в перечислении раньше), чем все нижние вершины, причем все вершины его левого поддерева обрабатываются раньше, чем все вершины правого. Аналогично определяются ЛПК, ЛКП, ПЛК, ПКЛ и КПЛ обходы.

 

Чуть точнее: добавим во множество Arrows пустой элемент Æ (соответствующей стрелке из каждой вершины в себя) и рассмотрим всевозможные порядки на множестве Arrows={Æ,left,right}. Любой такой порядок продолжается на множество путей Arrows* - конечных последовательностей <r₁,..,r_L>, рассматриваемое теперь как множество функций r с бесконечной областью определения N таких, что r(i)= r_i, для iÎ [1..L] и r(j)=Æ, для j>L. Положим теперь r1<r2» r1¹r2 и r1(i₀)<r2(i₀) (в смысле выбранного порядка на Arrows), i₀=min {i: r1(i)¹r2(i)}. Например, при сравнении 3-х путей 'Left', 'LeftLeft' и 'LeftRight' {Æ<left<right} влечет 'L'<'LL'<'LR', {left<right<Æ} - 'LL'<'LR'<'L' и {left<Æ<right} - 'LL'<'L'<'LR'.

 

Определение обхода в терминах лексикографического порядка дает следующую идею алгоритма обхода заданием приоритета выбора вершин:

Шаг 0. Начни с первого, в данном порядке, пути

В одних порядках это - пустой путь к корню дерева, в других его необходимо предварительно построить!

Шаг i+1

(если нет никаких направлений - обход окончен, иначе)

(если можно идти в направлении D₁,) иди в направлении D₁,

(если нет, но можно идти в направлении D₂,) иди в направлении D₂,

(если нет, но можно идти в направлении D₃,) иди в направлении D₃,

 

Здесь D₁,D₂,D₃ принадлежат алфавиту {up ("вверх"), left ("налево"), right (направо)}, нумерация задается выбранным на нем порядком, причем ход наверх соответствует значению Æ.

 

Реализация спуска налево и направо от текущей вершины очевидна. Главная трудность - в реализации подъема: в деревьях все пути ведут "вниз"!

Идея

- нужно запоминать ссылки на корни деревьев, которые еще предстоит обработать - самое простое - класть их в конец некоторой (динамической!) последовательности.

- для реализации подъема нужно вытащить ссылку на вершину из хранилища; в зависимости от вида обхода, это может означать как "вытаскивание" как с того же, так и другого конца последовательности.

 

Сказанное определяет тип последовательности-хранилища: это либо стек, реализующий "вытаскивание" с того же конца, либо очередь, реализующая "вытаскивание" с противоположного конца. (См. "Абстрактные линейные типы").

{пример обхода "в глубину"» Æ < {left,right} }

{» более короткие ветки (слова, пути) идут в перечислении раньше более длинных}

procedure КЛП(root:pTree);

var

pt:pNode;{ссылка на текущую вершину}

stack:pStack; { реализация - см. "Абстрактные линейные типы" }

begin

Create(stack);

if root<>nil then push(stack,root);

while not empty(stack) do

begin

pop(stack,pt); {подъем наверх}

with pt^ do

begin

{ какая-то обработка содержимого текущей вершины pt^.value}

if left<>nil {можешь идти налево?}

then {тогда иди, но сохрани правую ссылку}

begin pt:=left; if right<>nil then push(stack,right) end

else {налево нельзя}

if pt^.right<>nil {- можно ли направо?}

then pt:= pt^.right

end;

Destroy(Stack)

end;

 

{пример обхода в ширину - ветви одинаковой длины ("буквы" left, right) соседствуют в перечислении}

procedure (root:pTree);.

var

Queue:pQueue; { реализация - см. "Абстрактные линейные типы" }

pt:pNode;{ссылка на текущую вершину}

begin

Create(Queue); {создать очередь}

if root<>nil then Put(Queue,root); {Поставить В Очередь }

while not Empty(Queue) {очередь не пуста} do

begin

Get(Queue, pt); {Вывести Из Очереди}

{обработать содержимое pt^.value вершины pt}

if pt!.left<>nil then Put(Queue, pt!.left);

if pt!.right<>nil then Put(Queue, pt!.right);

end;

Destroy(Queue)

end;

 

Замечание. Деревья просто определяются рекурсивно, а потому – для проявления эрудиции – нетрудно дополнить ответ рекурсивными вариантами обхода «в глубину». Но – не заменять ими итеративный вариант!

 

Алгоритмы символьной обработки.

 

Последние 3 вопроса относятся к алгоритмам символьной обработки. Важность задач обработки символьных последовательностей (текстов) связана с универсальностью текстов как имен (обозначений). Значение любого типа как-то выражается, определяется текстом его записи (в некоторой системе обозначений).

 

В этой связи круг естественно возникающих при обработке текстов задач можно разделить на 3 части.

1) Вычисление функции значения/именования, т.е. нахождение значения по его обозначению и обратная задача.

2) Формальная обработка («редактирование») текстов как собственно последовательностей, никак не связанная с ролью текстов как обозначений.

3) Формальные вычисления - порождение текста результата некоторого преобразования значений по тексту ее аргументов