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

НА ЗАМЕТКУ! Поддержка строгости типа 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. с.

Листинг 17.8. Программа use q.c

754 Глава 17

Ниже показаны результаты пробного запуска. Вы должны также протестировать корректность работы реализации в случае, когда очередь полна.

Тестирование интерфейса Queue. Введите а, чтобы добавить значение,

введите d, чтобы удалить значение, или введите q для выхода из программы.

а

Целое число для добавления: 40 Помещение 40 в очередь

1 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: а

Целое число для добавления: 20 Помещение 20 в очередь

2 элемент(ов) в очереди

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

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: а

Целое число для добавления: 55 Помещение 55 в очередь 3 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 40 из очереди 2 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 20 из очереди 1 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Удаление 55 из очереди 0 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы: d

Элементы для удаления отсутствуют!

0 элемент(ов) в очереди

Введите а, чтобы добавить, d, чтобы удалить, или q для выхода из программы:

q

Программа завершена.

Моделирование реальной очереди

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

Предположим, что некий Зигмунд Ландер установил консультационный киоск в торговом центре. Клиенты могут заплатить за одну, две или три мицугы консультаций. Для обеспечения свободного прохода действующие в торговом центре правила ограничивают количество клиентов в очереди до 10 (что легко определяет максимальный размер очереди в программе). Представим, что люди подходят к киоску случайным образом, а время, которое они тратят на получение консультации, произвольно распределяется между тремя возможными вариантами (одна, две или три минуты). Сколько в среднем клиентов придется обслужить Зигмунду в течение часа? Сколько в среднем каждому клиенту придется дожидаться своей очереди? Какой будет средняя длина очереди? Моделирование может дать ответы на вопросы такого рода.

Прежде всего, давайте решим, что именно помещать в очередь. Каждого клиента можно описывать в терминах времени, когда он становится в очередь, и количества минут, которые он собирается потратить на консультацию. Это предполагает следующее определение элемента Item: