Основные операции с очередью

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

1. Добавление в конец очереди:

void Add(Queue **Begin, Queue **End, Data &x)

{

Queue *t = new Queue; // Память под новый элемент

t->d.a = x.a; // Заполнение полей

if(*Begin == NULL || *End == NULL)

{

// Если очередь была пуста

t->prev = NULL;

t->next = NULL;

*Begin = *End = t;

return;

}

// В очереди был хотя бы один элемент

t->prev = *End; // Подключаем новый элемент к имеющимся

(*End)->next = t;

t->next = NULL;

*End = t; // Перенастройка начала очереди

}

Обратиться к функции можно так:

Add(&Begin, &End, x);

где x — объект типа Data.

Как видим, хотя для добавления надо знать только положение конца очереди, здесь в функцию передаётся и её начало. Зачем? А чтобы правильно обработать ситуацию, когда данные добавляются в пустую очередь. Ведь в этом случае требуется настроить указатель Begin на начало очереди.

2. Извлечение данных из начала очереди:

bool Del(Queue **Begin, Queue **End, Data &x)

{

if(*Begin == NULL)

{

cout << "Pustaj Ocheredj" << endl;

return false;

}

Queue *t = *Begin;

x.a = t->d.a; // Заполнение полей

*Begin = t->next;

if(*Begin == NULL) // Удаляется единственный элемент очереди

*End = NULL;

delete t;

return true;

}

Обратиться к функции можно так:

Del(&Begin, &End, x);

где x — объект типа Data.

Двухсторонняя очередь

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

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

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

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

Очередь с приоритетом

Это очень интересная разновидность очередей. В ней добавление новых данных производится также в конец очереди, а вот выборка — в зависимости от какого-либо правила.

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

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

Пример. Имеется очередь с приоритетом, в которой хранятся целые числа. Пусть удаление отрицательных чисел будет более приоритетным. Так, если в очереди находятся числа 3, -4, 2, -6, то удаляться они могут только в последовательности: -4, -6, 3, 2.

Всё это не так сложно реализовать самостоятельно, поэтому ни каких программных примеров не приводится.

Деревья

Общие сведения о деревьях

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

На самом верхнем уровне такой иерархии всегда имеется только один узел, называемый корнем дерева. У нас это узел A. Каждый узел, кроме корневого, связан только с одним узлом более высокого уровня, называемым узлом-предком. Например, для узла D предком является узел A, предок для узла G — это D и т.д. При этом каждый элемент дерева может быть связан с помощью ветвей (ребер) с одним или несколькими узлами более низкого уровня. Они для данного узла являются дочерними узлами (узлами-потомками). Так, для узла A потомками будут B, C и D, для узла B — E и F и т.д. Элементы, расположенные в конце ветвей и не имеющие дочерних узлов, называют листьями. На рисунке выше листьями являются узлы E, F, C, G, J и I.

От корня до любого узла всегда существует только один путь. Максимальная длина пути от корня до листьев называется высотой дерева. У нас максимально длинный путь образует цепочка узлов A, D, H и J, т.е. высота дерева равна 3.

Любой узел дерева с его потомками также образует дерево, называемое поддеревом (относительно исходного дерева). Например, можно рассматривать поддерево, начинающееся с узла D (это узлы D, G, H, I, J).

Число поддеревьев для данного узла образует степень узла. Для узлов A и D степень равна 3, степень узла B равна 2, узел H имеет степень 1, а у листьев (узлы E, F, C, G, J и I) степень равна 0. Максимальное значение среди степеней всех узлов определяет степень дерева. Если максимальная степень узлов в каком-то дереве равна n, то его называют n-арным деревом. Наше дерево имеет степень 3 (из-за узлов A и D), и его можно называть триарным.

Дерево степени 2 называется бинарным. Бинарные деревья наиболее просты с точки зрения сложности реализации алгоритмов работы с деревьями, поэтому именно бинарные деревья применяются там, где требуется динамическая структура типа дерево. Если формально требуется дерево степени большей, чем 2, например, 5-й степени, то, сформировав такое дерево, его можно преобразовать в бинарное, а далее работать как с бинарным деревом.

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