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

Операции типа: Инициализация очереди пустым содержимым Определение, является ли очередь пустой Определение, является ли очередь полной Определение количества элементов в очереди Добавление элемента в конец очереди Удаление и восстановление элемента в начале очереди Опустошение очереди

Определение интерфейса

Определение интерфейса будет помещено в файл queue.h. С помощью средства typedef языка С мы создадим имена для двух типов: Item и Queue. Точная реализация соответствующих структур должна находиться в файле queue.h, но концептуально проектирование структур является частью этапа детальной реализации. А пока будем считать, что типы определены, и сосредоточим внимание на прототипах функций.

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

Прежде всего, следует подумать об инициализации. Она предполагает изменение типа Queue, поэтому функция должна принимать в качестве аргумента адрес переменной Queue:

void InitializeQueue (Queue * pq);

Выяснение, является очередь пустой или полной, предусматривает применение функции, которая должна возвращать истинное или ложное значение. Здесь мы будем считать, что заголовочный файл stdbool.h стандарта С99 доступен. Если это не так, можно использовать тип int или определить тип bool самостоятельно. Поскольку функция не изменяет очередь, она может принимать аргумент Queue. С другой стороны, в зависимости от реального размера объекта типа Queue, передача только адреса переменной Queue может проходить быстрее и с меньшим расходом памяти. Еще одно преимущество такого подхода заключается в том, что все функции будут принимать в качестве аргумента адрес. Для указания на то, что функции не изменяют очередь, можно (да и нужно) применять квалификатор const:

bool QueuelsFull(const Queue * pq);

bool QueuelsEmpty (const Queue * pq);

Иначе говоря, указатель pq ссылается на объект данных Queue, который не может изменяться через pq. Аналогичный прототип можно определить для функции, которая возвращает количество элементов в очереди:

int QueueltemCount(const Queue * pq);

Добавление элемента в конец очереди предусматривает идентификацию элемента и очереди. На этот раз очередь изменяется, так что использование указателя обязательно. Функция может иметь тип void либо же возвращаемое значение можно применять для указания, успешно ли выполнена операция по добавлению элемента. Давайте примем второй подход:

bool EnQueue(Item item, Queue * pq);

Наконец, удаление элемента может быть реализовано несколькими способами. Если элемент определен как структура или один из фундаментальных типов, функция может его возвращать. Аргументом функции могла бы быть переменная Queue либо указатель на нее. Таким образом, один из возможных прототипов выглядит так:

Item DeQueue(Queue q);

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

bool DeQueue(Item * pitem, Queue * pq);

Элемент, удаленный из очереди, помещается в место, на которое ссылается указатель pitem, а возвращаемое значение отражает, успешно ли выполнена операция. Единственным аргументом, который должен быть предоставлен функции опустошения очереди, является адрес очереди, что и демонстрирует приведенный далее прототип:

void EmptyTheQueue(Queue * pq);

Реализация представления данных интерфейса

Первый шаг предусматривает решение о том, какая форма данных С будет использоваться для очереди. Одним из вариантов является массив. Преимущества массивов связаны с простотой их применения и легкостью добавления элемента в конец заполненной части массива. Проблема возникает, когда дело доходит до удаления элемента из начала очереди. Если снова воспользоваться аналогией очереди за билетами,

746 Глава 17 удаление элемента из начала очереди заключается в копировании значения первого элемента в массиве (что просто) и последующем перемещении каждого элемента, оставшегося в массиве, на одну позицию в направлении его начала. Хотя эти действия легко программировать, они занимают много процессорного времени (рис. 17.6).

Рис. 17.6. Использование массива в качестве очереди

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

Рис. 1 7.7. Переопределение начального элемента

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

Более искусное решение проблемы теряемого пространства предполагает превращение очереди в кольцевую. Это означает, что конец массива должен быть соединен с его началом. То есть вообразите, что первый элемент массива следует непосредственно за последним элементом, поэтому при достижении конца массива вы начинаете добавлять элементы в начальные позиции, как если бы они были освобождены (рис. 17.8). Такой процесс можно сравнить с рисованием на бумажной ленте, склеенной в кольцо. Естественно, теперь придется выполнять дополнительные действия по обеспечению того, чтобы конец очереди не перекрывал ее начало.

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

Рис. 1 7.8. Кольцевая очередь

748 Глава 17

Чтобы проверить свои идеи, начнем с создания очереди целых чисел:

typedef int Item;

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

typedef struct node

{

Item item; struct node * next;

} Node;

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

typedef struct queue

{

Node * front; /* указатель на начало очереди */

Node * rear; /* указатель на конец очереди */

int items; /* количество элементов в очереди */

} Queue;

Обратите внимание, что Queue — структура с тремя членами, поэтому ранее принятое решение об использовании в качестве аргументов указателей на очереди, а не самих очередей, экономит время и объем расходуемой памяти.