Реализация стека, дека и очереди на основе ЛСС (Линейного связанного списка)

type pUzel=^TUzel;

TUzel = record

INFO: integer;

next: pUzel

end;

Любой линейный список, реализованный как линейный связанный список, должен иметь голову - указатель на первый элемент линейного списка. Для стека это означает, что элемент HEAD должен быть Var head:pUzel; - который указывает на верхний элемент стека. Тогда добавление нового элемента в стек заключается в разрыве связи между головой и первым элементом:

1. В оперативке выделяется новый элемент рис.1

procedure insert_into_stak

Var tmp:pUzel;

Begin

{1} new(tmp);

{2} tmp^.next=head;

{3} head:=tmp;

end;

Исключение стека заключается:

В tmp мы занесли значение head;

{2} head:=head^.next;

{1} tmp:=head;

{3} delete(tmp);

Таким образом, добавление и удаление элементов в стек происходит за единицу времени O(1).

2. Добавление и удаление в очередь. В случае очереди возникает двусмысленность с понятием головы: т.к. первый элемент располагается "с другой стороны".

Элемент списка

O(N - 1) = O(N)

Добавление в очередь заключается в помещении элемента между "головой" и того элемента, на который голова указывает, а голова фактически указывает на последний элемент. Таким образом, элемент помещается в конец очереди.

Удаление из очереди состоит из двух этапов. Проход по всей очереди для определения её конца, т.е. того первого элемента, который выталкивается из очереди.

Delete.from_queue(head:pUzel);

Var tmp,prev: pUzel;

Begin

If tmp<> nil then

Begin

tmp:= head;

while tmp^.next<>nil do

Begin

End;

tmp:= tmp^.next;

Delete(tmp); prev^.next:= nil;

(*) If head = tmp then head:= nil;

Недостатком данного алгоритма является:

1. Частая проверка оператора *, которую можно было бы избежать или исключить, заметив что элемент "голова" формально является предшественником первого элемента, однако в данном случае типы данных головы и элемента различаются. pUzel и tUzel соответственно. Для обобщения можно использовать в качестве головы статическую переменную типа tUzel. В этом случае при реализации поле head типа tUzel можно использовать двумя способам:

1.1. поле инфо(Info) не используется, а используется только поле next, для указывает ан первый элемент линейного связанного списка

1. 2. поле head, будучи статическим представляет собой первый элемент списка, а все последующие - динамические. Недостаток такого подхода связан с добавлением элемента в голову.

2. Удаление из очереди осуществляется за U(n). Чтобы улучшить оценку необходимо

Вход

Такой способ организации очереди обозначим через очередь с двумя указателями. при этом хвост линейного списка является входом в очередь, а голова - выходом. при такой организации удаление и добавление элементов осуществятся за U(1).

Реализация дека

Дек – двунаправленный список, т.е.

type

tuzel = record

info: ..;

next,prev:pUzel;

end;

Var left,right: pUzel;

Поле next - слева направо, поле prev - справа налево, поэтому имеется две головы. Добавление и удаление аналогично за исключением того, что необходимо корректировать значение как у узла справа, так и слева.

Не линейная структура данных

АТД дерево

Дерево – совокупность элементов называемые узлами, один из которых определен как корень и отношения, образующих иерархическую структуру узлов. Заметим, что узлы могут быть любого типа по аналогии с элементами списка, а при реализации отличаются структурой узлов. Формально дерево можно определить (рекуррентно):

1. Один узел является деревом, этот же узел является корнем. Также выделяют пустое дерево, содержащее Λ(лямду).

2. Пусть n – узел, а T1, T2 и …Tk деревья с корнями n 1, n 2 … n k, тогда можно построить новое дерево, сделав узел n родителем узлов n 1, n 2 … n k и получим T1…Tk - поддеревьями, а n 1, n 2 … n k – корнями этих деревьев, кроме того они являются сыновьями узла n.

Путем из узла n 1 в узел n k является последовательность узлов n 1, n 2 … n k таких, что для всех ni узлов, образующих путь 2 ≤ i ≤ k, ni-1 является родителем узла ni.

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

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

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

- если, существует путь из узла А в узел В, то узел А является предком узла В, а В потомком узла А.

Любой узел одновременно является и предком самого себя. Истинным предком или истинным потомком является предок (или потомок) не являющимся таковым самого себя.

Корень – это узел, не имеющий истинного предка. Узлы не имеющих истинных потомков называются листьями.

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

Порядок узлов

Рассмотрим три дерева, они состоят:

Из одного и того же множества элементов А,В,С – имена и значения метки. В отличаются от А и С отношением предок потомок. В варианте а) и б) одинаковые отношения предок потомок, эти деревья можно считать одинаковыми, если не различать положение сыновей и детей, такое дерево называется не упорядоченным.

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

Правило определение расположения узлов: можно прочертить воображаемую форму линию от корня от узла. Узлы находящиеся на линии связан отношение предок потомок и как бы задают отношения порядка сверху вниз, а не слева на право. Это относится также и к сыновьям.

Прямой, обратный и симметричный обход дерева

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

1. А ВС – прямой.

2. ВСА – обратный, сначала сыновья потом родители.

3. ВАС – симметричный (внутренний).

Формально процедуру обхода можно записать следующим образом, если

дерево Т нулевое, то список обхода пуст. Если дерево состоит из одного

элемента, то список обхода заносится и обход завершается. Если корень Т имеет Тn, то различают следующие варианты обхода: при прохождение в прямом порядке обхода сначала посещается корень дерева (поддерева), а

затем слева на право посещаются его деревья T1,T2 …Tk, причем к поддереву Tk переход осуществится, только после того, как все дерево T1 будет обойдено аналогичным образом в начале корень, а потом сыновья поддеревья; симметричный обход дерева T начинается с обхода левого дерева T1

после чего посещается родитель T1, дальше слева на право посещается T2 …Tk, каждое из деревьев Ti посещается аналогичны образом; обратный обход T1, T2 …Tk, а затем n каждое из поддеревьев обходится аналогичным образом.

1. 5, 1, 2, 11, 6, 12, 7, 8, 9, 4, 3, 10.

2. 2, 11, 1, 12, 6, 5, 8, 7, 9, 4, 10, 3.

3. 11, 2, 12, 6, 1, 8, 4, 9, 7, 10, 3, 5.

Помеченные деревья или деревья выражений

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

( а + в)*(а - с), чтобы вычислить это выражение а, в, +, а, с, -, * получим обратный обход или постфиксное (польскую) представление выражения, который используется при вычисление выражения в нем – P1 P2 Ө, где P1,P2 постфикс соответствующего выражения.

Здесь не требуется скобок для вычисления операций, потому что расставлена как к структуре дерева.

+ а в – а с , Ө P1 P2, префиксная форма запись подвыражения.

а + в * в – с, P1 Ө P2 симметричный (внутренний) инфикс, скобки в данном случае нужны.

Примеры решения задач:

Вычислить 5 9 10 * + Перевести из постфикса в префикс 2 4 3 * - 5 4 + +

Пусть E1 и E2 подвыражения арифметического вида E1 Ө E2, причем Е1 соответствие левого поддерева, а Е2 правое поддерево с корнем в узле Ө. Таки образом Ө соответствует арифметической операции бинарного вида, т.е. Е1 и Е2 построен в подобных структурах. Тогда обход этого дерева в прямом порядке, Ө Р1 Р2 соответствует префиксной форме записи арифметического выражения. Здесь Р1 и Р2 префиксные формы записи выражений Е1 и Е2. Скобки в префиксном выражение не требуются, так как всегда можно посмотреть Ө Р1 Р2 слева на право без возврата, чтобы определить самый короткий префикс Р1 как единственный возможный в выражение Р1 Р2 (Ө Р1 Р2 ≡ Р). Аналогично обратный обход записывается в виде Р1 Р2 Ө, где Р1 и Р2 постфиксная форма записи поддеревьев Е1 и Е2, скобки также не требуются, так как с одной стороны двигаясь слева на право в выражениях Р1 и Р2 всегда можно выделить Е1, как самый короткий постфикс. А с другой стороны само дерево выражений, так как сама структура дерева однозначно определяет приоритет операций, а разбирая префиксное или постфиксное выражение можно однозначно реконструировать самом дерево чего нельзя добиться в случае с инфиксной формой записи.

Сортировка

Сортировка используется:

1. Для вывода в удобном виде (например, по алфавиту)

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

3. Задачи группировки: после сортировки группируемые элементы располагаются подряд ; считается, что 25% машинного времени тратится на упорядочение данных, а первый машинный алгоритм сортировки был разработан или продемонстрирован в 60-м году.

Классификация алгоритмов сортировки

Д.Кнут выделяет пять классов сортировок:

1. Класс обменных сортировок: элементы обмениваются местами, если он не упорядочены