Реализация очередей с помощью циклических массивов

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

Элементы очереди располагаются в «круге» ячеек в последовательных позициях. Конец очереди находится по часовой стрелке на определенном расстоянии от начала.

Теперь для вставки нового элемента в очередь достаточно переместить указатель конца на одну позицию по часовой стрелке и записать элемент в эту позицию.

При удалении элемента из очереди надо просто переместить указатель начала по часовой стрелке на одну позицию.

Тогда операции вставки и удаления производятся за фиксированное время, независимое от длины очереди.

Есть одна сложность при таком представлении. Предположим, очередь состоит из maxlength элементов, т.е. полностью заполнила массив. Тогда указатель конца указывает на позицию рядом с указателем начала, но находящуюся против часовой стрелки.

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

Если мы удалим из очереди этот элемент, то указатель начала переместится на одну позицию по часовой стрелке, оформляя пустую очередь.

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

Следовательно, без введения каких-либо механизмов определения пустых очередей при максимальной длине массива maxlength мы не можем позволить очереди иметь более maxlength-1 элементов.

2. АТД «Дек»

Стек позволяет добавлять и удалять элементы только с одного конца. В очередь добавлять элементы можно только с одного конца, а удалять – только с другого. Структура данных, называемая деком (от double-ended queue – «очередь с двумя концами»), позволяет добавлять и удалять элементы с обоих концов.

Нелинейные абстрактные типы данных Деревья

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

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

Узлы, также как и элементы списков, могут быть элементами любого типа.

Формально дерево можно рекуррентно определить так:

1. Один узел является деревом. Этот же узел также является корнем этого дерева.

2. Пусть n – это узел, а Т₁, Т₂, …,Т_к – деревья с корнями n₁,n₂,…,n_k, соответственно. Можно построить новое дерево, сделав n родителем узлов n₁,n₂,…,n_k. В этом дереве n будет корнем, а Т₁, Т₂, …,Т_к – поддеревьями этого корня.

Узлы n₁,n₂,…,n_k называются сыновьями узла n.

3. Существует нулевое дерево, т.е. дерево без узлов.

Пример. Рассмотрим оглавление книги. Это оглавление является деревом, которое можно представить в виде

Книга

Гл.1.

1.1.

1.2.

Гл.2.

2.1.

2.1.1.

2.1.2.

2.2.

2.3

Гл.3.

Отношение родитель–сын отображается в виде линии.

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

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

Узел Книга является родителем узлов Гл.1, Гл.2, Гл.3., а эти три узла являются сыновьями узла Книга.

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

Путем из узла n₁ в узел n_k называется последовательность узлов n₁, n₂,…, n_k, где для всех i, 1 i  k, узел n_i является родителем узла n_i+1.

Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь.

Т.О., путем нулевой длины будет путь из любого узла к самому себе.

Если существует путь из узла a в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла а.

Любой узел одновременно является и предком и потомком по отношению к другим узлам.

Истинным предком называется узел, сам не имеющий предков.

Истинным потомком называется узел, который сам не имеет потомков.

Согласно этому определению корень является истинным предком.

А узел, не имеющий истинных потомков, называется листом.

Высотой узла дерева называется длина самого длинного пути из этого узла до какого-либо листа.

На рис. высота узла Гл.1 равна 1, узла Гл.2 – 2, а узла Гл.3 – 0.

Высота дерева совпадает с высотой корня.

Глубина узла определяется как длина пути (он единственный) от корня до этого узла.

Совокупность деревьев называют лесом.