while (! intgueue.isgueueEmpty() ) { intgueue.dequeue(dequeuelnteger);

cout << dequeuelnteger << удаляется из очереди << endl; intQueue.printgueue();

Queue<float> floatQueue; float val = 1.1, dequeueFloat;

cout << обработка очереди чисел с плавающей точкой endl;

for (i = 0; i < 4; i++) { floatgueue.enqueue(val); floatQueue.printQueue(); val += 1.1;

while (!floatQueue.isQueueEmpty0) { floatgueue.dequeue(dequeueFloat);

cout << dequeueFloat << удаляется из очереди << endl; floatQueue.printQueue (); }

return 0;

Рис. 15.12. Обработка очереди (часть 2 из 2) Типичная ошибка программирования 15.7

Отсутствие установки указателя связи в последнем узле очереди в нуль (0).

Программа, приведенная на рис. 15.12 (вывод данных показан на рис. 15.13), создает шаблон класса очередей используя скрытое наследование шаблона класса списков. Потребуем, чтобы очередь имела функции-элементы enqueue, dequeue, isQueueEmpty и printQueue. Заметим, что эти фукции-элементы, по существу, являются функциями-элментами шаблона класса списков inserAtBack, removeFromFront, isEmpty и print соответственно.

QUEUEDRV.CPP

Драйвер для проверки шаблона класса Queue #include <iostream.h> tinclude queue.h

main ( ) {

Queue<int> intgueue; int dequeuelnteger;

cout << обработка очереди целых чисел << endl;

for (int i = 0; i < 4; i++) { intgueue.enqueue(i); intgueue.printgueue();

обработка очереди с целыми числами

М Список состоит из: О I

I Список состоит иэ: 0 1

I Список состоит иэ: 0 12

Список состоит из: 0 12 3

V о удаляется иэ очереди 1 Список состоит из: 12 3

1 удаляется из очереди - Список состоит из: 2 3

2 удаляется из очереди Список состоит из: 3

Н 3 удаляется из очереди 1 Список пуст

обработка очереди со значениями с плавающей точкой

Список состоит иэ: 1.1

Список состоит иэ: 1.1 2.2

<и Список состоит из: 1.1 2.2 3.3

is- Список состоит из: 1. 2.2 3.3 4.4

1.1 удаляется иэ очереди Список состоит из: 2.2 3.3 4.4

2 .2 удаляется иэ очереди Список состоит из: 3.3 4.4

3.3 удаляется иэ очереди , Список состоит из: 4.4

удаляется из очереди ЩД Список пуст

Все узлы удалены

Все узлы удалены

Рис. 15.13. Пример вывода программы, приведенной на рис. 15.12

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

очередей. Когда мы реализуем функции-элементы очереди, они должны вызывать соответствующие функции-элементы класса списков: enqueue должна вызывать insertAtBack, dequeue - removeFromFront, isQueueEmpty - isEmpty, a функция-элемент printQueue должна вызывать print.

Шаблон класса очередей используется в функции main для реализации очереди с данными целого типа intQueue типа Queue<int>. Целый числа от О до 3 помещаются в очередь к intQueue, а затем удаляются из нее по принципу первым вошел - последним вышел . Затем шаблон класса очередь используется для реализации очереди со значениями с плавающей запятой floatQueue типа Queue<float>. Значения с плавающей запятой 1.1, 2.2, 3.3 и 4.4 помещаются в очередь floatQueue, а затем удаляются из нее по тому же принципу первым вошел - последним вышел .

15.7. Деревья

Связные списки, стеки и очереди являются линейными структурами данных. Дерево является нелинейной двумерной структурой данных с особыми свойствами. Узлы дерева могут содержать два и более указателей связи. В этом разделе рассмотрены бинарные деревья (см. рис. 15.14) - деревья, узлы которых содержат по два указателя (ни один из них, один или оба могут быть нулевыми). Корневой узел является первым узлом дерева. Каждый указатель связи в корневом узле ссылается на дочерний узел или узел-потомок. Левый узел-потомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узлы-потомки, порожденные одним каким-либо узлом, называются родственными узлами (или узлами-братьями). Узел без узлов-потомков называется листом дерева или концевым узлом. Специалисты по вычислительной технике обычно рисуют деревья сверху-вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе.

Типичная ошибка программирования 15.8

Отсутствие установки указателей связи в нуль (0) в концевых узлах дерева.

Рис. 15.14. Графическое представление дерева