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

Листинг 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