Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Теперь пора подумать о размере очереди. В случае связного списка размер очереди ограничен объемом доступной памяти, но часто имеет смысл применять очередь значительно меньшего размера. Например, очередь можно использовать для эмуляции самолетов, ожидающих приземления в аэропорту. Если количество ожидающих самолетов становится слишком большим, новые прибывающие самолеты могут направляться в другие аэропорты. Мы установим максимальный размер очереди равным 10. Определения и прототипы интерфейса очереди приведены в листинге 17.6. В нем от сутствует конкретное определение типа Item. Во время применения интерфейса в него будет помещено определение, соответствующее потребностям конкретной программы.

Листинг 17.6. Заголовочный файл queue.h для интерфейса очереди

Расширенное представление данных

Реализация функций интерфейса

Теперь можно приступить к написанию кода интерфейса. Инициализация очереди “пустым содержимым” означает установку указателей на начало и конец очереди в NULL, а счетчика (члена item) — в 0:

void InitializeQueue(Queue * pq)

{

pq->front = pq->rear = NULL; pq->items = 0;

}

С помощью члена item очень легко проверить, является очередь полной или пустой, и возвратить количество элементов в очереди:

750 Глава 17

Добавление элемента в очередь предусматривает выполнение следующих действий.

1. Создание нового узла.

2. Копирование элемента в этот узел.

3. Установка указателя next этого узла в NULL, идентифицируя узел как последний в списке.

4. Установка указателя next текущего конечного узла так, чтобы он ссылался на новый узел, связывая его с очередью.

5. Установка указателя rear для ссылки на новый узел в целях упрощения поиска последнего узла.

6. Увеличение на 1 счетчика элементов.

Кроме того, функция должна обрабатывать два особых случая. Во-первых, если очередь пуста, указатель front должен быть установлен для ссылки на новый узел. Причина в том, что при наличии только одного узла этот узел является одновременно и начальным, и конечным узлом очереди. Во-вторых, если функции не удается выделить память для узла, она должна предпринять какие-то действия. Поскольку мы предполагаем использование небольших очередей, такой отказ будет возникать редко, поэтому в случае нехватки памяти функция будет просто прекращать выполнение программы. Ниже показан код функции EnQueue().

bool EnQueue(Item item, Queue * pq)

{

Node * pnew; if (QueuelsFull(pq)) return false;

pnew = (Node *) malloct sizeof(Node)); if (pnew == NULL)

{

fprintf(stderr, "He удается выделить память!\n"); exit(1);

}

CopyToNode(item, pnew); pnew->next = NULL; if (QueuelsEmpty(pq))

pq->front = pnew; /* элемент помещается в начало очереди */

else

pq->rear->next = pnew; /* связывание с концом очереди */

pq->rear = pnew; /* запись местоположения конца очереди */

pq->items++; /* увеличение на 1 количества элементов в очереди*/

return true;

Расширенное представление данных 751

Функция CopyToNode() — это статическая функция, выполняющая копирование элемента в узел:

static void CopyToNode(Item item, Node * pn)

{

pn->item = item;

}

Удаление элемента из начала очереди требует выполнения следующих действий.

1. Копирование элемента в ожидающую переменную.

2. Освобождение памяти, которая используется удаляемым узлом.

3. Переустановка указателя на начало очереди, чтобы он ссылался на следующий элемент в очереди.

4. Установка указателей на начало и конец очереди в NULL, если удален последний элемент.

5. Уменьшение на 1 счетчика элементов.

Все эти действия реализованы в показанном ниже коде:

bool DeQueue(Item * pitem, Queue * pq)

{

Node * pt;

if (QueuelsEmpty(pq) ) return false;

CopyToItem(pq->front, pitem);

pt = pq->front;

pq->front = pq->front->next;

free (pt);

pq->items--;

if (pq->items == 0) pq->rear = NULL;

return true;

}

Здесь необходимо отметить пару важных фактов. Во-первых, в коде не делается явная установка указателя front в NULL, когда удаляется последний элемент. Причина в том, что указатель front уже установлен в значение указателя next удаляемого узла. Если этот узел является последним в очереди, то значение его указателя next равно NULL, поэтому указатель front получает значение NULL. Во-вторых, код использует временный указатель (pt) для отслеживания местоположения удаленного узла. Это связано с тем, что официальный указатель первого узла (pq->front) переустанавливается так, чтобы указывать на следующий узел. Поэтому без применения временного указателя программа утратила бы возможность отслеживания того, какой блок памяти освобождать.

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

void EmptyTheQueue(Queue * pq)

{

Item dummy;

while (!QueuelsEmpty(pq))

DeQueue(sdummy, pq);

}

752 Глава 17

НА ЗАМЕТКУ! Поддержка строгости типа ADT

После определения интерфейса ADT вы должны применить одну из его функций для поддержки типа данных. Например, обратите внимание, что функция DeQueue() полагается на функцию EnQueue() в выполнении работы по корректной установке указателей и по установке указателя next узла rear в null. Если в программе, использующей ADT, вы решите манипулировать частями очереди напрямую, это может привести к нарушению координации между функциями в пакете интерфейса.

В листинге 17.7 представлены все функции интерфейса, включая функцию

CopyToItem(), применяемую в EnQueue().

Листинг 17.7. Файл реализации queue, с

Расширенное представление данных 753

Тестирование очереди

Прежде чем включать новую структуру, такую как пакет очереди, в важную программу, эту структуру необходимо протестировать. Один из подходов к тестированию предусматривает создание короткой программы, иногда называемой драйвером, единственное назначение которой состоит в тестировании пакета. Например, в коде, приведенном в листинге 17.8, очередь используется для добавления и удаления целых чисел. Прежде чем компилировать программу, убедитесь в наличии следующей строки в файле queue.h:

typedef int item;

Кроме того, не забудьте о необходимости выполнения компоновки с queue, с и use_q. с.