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

3. Что такое ADT?

4. Функция QueueIsEpty() принимает в качестве аргумента указатель на структуру queue, но ее можно было бы написать так, чтобы она принимала саму структуру queue, а не указатель на нее. Каковы преимущества и недостатки каждого из этих подходов?

5. Стек является еще одной формой данных из семейства списков. В стеке добавления и удаления могут выполняться только с одной стороны списка. Говорят, что элементы “заталкиваются” в стек и “выталкиваются” из него. Следовательно, стек представляет собой структуру LIFO (last in, first out — “последним прибыл, первым обслужен”).

а. Определите тип ADT для стека.

б. Определите программный интерфейс стека, т.е. заголовочный файл stack.h.

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

6. Каково максимальное количество сравнений, которые требуются при последовательном поиске и двоичном поиске для определения того, что конкретный элемент отсутствует в упорядоченном списке из 3 элементов? В списке из 1023 элементов? В списке из 65 535 элементов?

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

а. nice food roam dodge gate office wave

б. wave roam office nice gate food dodge

в. food dodge roam wave office gate nice r. nice roam office food wave gate dodge

8. Взгляните на двоичные деревья, созданные при ответе на вопрос для самоконтроля под номером 7. Как они будут выглядеть после удаления из них слова food с помощью алгоритма, описанного в этой главе?

Упражнения по программированию

1. Модифицируйте код в листинге 17.2 так, чтобы он отображал список фильмов как в исходном, гак и в обратном порядке. Один из возможных подходов предусматривает изменение определения связного списка для обеспечения обхода списка в обоих направлениях. Другой подход заключается в применении рекурсии.

2. Предположим, что в файле list.h (листинг 17.3) используется следующее определение списка:

typedef struct list {

Node * head; /* указывает на начало списка */

Node * end; /* указывает на конец списка */

} List;

Перепишите функции в файле list.с (листинг 17.5), чтобы они соответствовали этому определению, и протестируйте результирующий код с помощью программы films3.c (листинг 17.4).

3. Предположим, что в файле list.h (листинг 17.3) используется следующее определение списка:

#define MAXSIZE 100 typedef struct list {

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

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

} List;

Перепишите функции в файле list.с (листинг 17.5), чтобы они соответствовали этому определению, и протестируйте результирующий код с помощью программы films3.c (листинг 17.4).

4. Перепишите программу mall .с (листинг 17.7), чтобы она моделировала киоск с двумя окошками и двумя очередями.

Глава 17

5. Напишите программу, которая позволяет ввести строку. Программа затем должна заталкивать в стек символы строки по одному (см. вопрос для самоконтроля под номером 5), выталкивать символы из стека и, наконец, отображать их. В результате символы отображаются в обратном порядке.

6. Напишите функцию, которая принимает три аргумента: имя отсортированного массива целых чисел, количество элементов в массиве и целое число, которое нужно найти. Функция возвращает значение 1, если целое число присутствует в массиве, и 0 — если отсутствует. Воспользуйтесь двоичным поиском.

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

8. Модифицируйте программу для клуба любителей животных, чтобы все живот ные с одинаковыми кличками хранились в одном и том же узле списка. Когда пользователь выбирает поиск животного, программа должна запросить кличку животного, после чего вывести список всех животных (вместе с их видами), имеющих данную кличку.

A

Ответы на вопросы для самоконтроля

792 Приложение А

Ответы на вопросы для самоконтроля из главы 1

1. Полностью переносимая программа — это программа, код которой без каких-либо изменений может быть скомпилирован в программу, успешно выполняемую на широком разнообразии компьютерных систем.