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

#define MAXSIZE 100 typedef struct list {

Item entries[MAXSIZE]; /* массив элементов */

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

} List;

744 Глава 17

Это снова потребует переписывания файла list .с, но программа, использующая такой список, в изменениях не нуждается.

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

Создание очереди с помощью ADT

Как вы видели, подход к программированию на С с применением абстрактных типов данных подразумевает выполнение следующих трех шагов.

1. Описание типа, включая его операции, в абстрактной обобщенной манере.

2. Определение интерфейса в виде функций для представления нового типа.

3. Написание подробного кода для реализации интерфейса.

Этот подход был задействован при создании простого списка. Теперь воспользуемся им для построения несколько более сложного объекта — очереди.

Определение абстрактного типа данных для представления очереди

Очередь — это список, обладающий двумя особыми свойствами. Во-первых, новые элементы могут добавляться только в конец списка. В этом смысле очередь подобна простому списку. Во-вторых, элементы могут удаляться только из начала списка. Очередь можно сравнить с цепочкой людей, стоящих друг за другом в билетную кассу. Каждый новый человек становится в конец цепочки и покидает ее в самом начале после приобретения билетов. Очередь является формой данных типа первым прибыл, первым обслужен (first in, first out — EIFO), подобной очереди в кассу (если только никто не вклинится в очередь). Ниже дано неформальное абстрактное определение.

Имя типа: Очередь

Свойства типа: Может содержать упорядоченную последовательность элементов

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

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

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