Основные операции с очередью
Для очереди используется две основные операции: добавление в конец и извлечение из начала очереди.
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-й степени, то, сформировав такое дерево, его можно преобразовать в бинарное, а далее работать как с бинарным деревом.
Как правило, в дереве всегда задают какой-либо принцип упорядоченности, например, по возрастанию какого-то параметра (ключа). То есть, для каждого узла ключи наследников располагаются слева направо по возрастанию. В бинарном дереве для каждого узла значение ключа левого наследника будет меньше значения ключа узла правого наследника.