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

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

1. Что требуется для определения типа данных?

2. Почему обход связного списка, приведенного в листинге 17.2, может осуществляться только в одном направлении? Как можно было бы изменить определение struct film, чтобы обход списка стал возможен в обоих направлениях?

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

2. Файл исходного кода содержит код в том виде, в каком он написан на языке, который использует программист. Файл объектного кода содержит код на машинном языке; ему не обязательно быть полным кодом завершенной программы. Исполняемый файл содержит полный код на машинном языке, формирующий исполняемую программу.

3. а Определение целей программы.

б. Проектирование программы.

в. Написание кода программы.

г. Компиляция программы.

д. Запуск программы.

е. Тестирование и отладка программы.

ж. Сопровождение и модификация программы.

4. Компилятор транслирует исходный код (например, код, написанный на языке С) в эквивалентный код на машинном языке, называемый также объектным кодом.

5. Компоновщик объединяет исходный код с кодом библиотек и кодом запуска для создания исполняемой программы.

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

1. Они называются функциями.

2. Синтаксическая ошибка — это нарушение правил, регламентирующих составление предложений или программ. Примером ошибки синтаксиса русского языка может служить предложение: “Говорить моя хорошо по-русски”. Ниже приведен пример синтаксической ошибки в программе на языке С:

printf"Куда подевались скобки?";

3. Семантическая ошибка — это ошибка, связанная с неправильным применением понятий. Например: “Это предложение — прекрасный образец английского языка”. Или в программе на языке С (имя thr ice_n по смыслу означает “трижды п”): thrice_n=3 + n;

4. Строка 1: начните строку с символа #; правильно введите имя файла stdio.h;

поместите это имя файла в угловые скобки.

Строка 2: используйте(), а не {}; завершите комментарий символами */, а не /*. Строка 3: используйте {, а не (.

Строка 4: дополните оператор символом точки с запятой.

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