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

Рассмотрим конкретный случай представления данных. Предположим, что нужно написать программу, которая позволяет вводить список всех фильмов (на видеокассетах, дисках DVD и дисках Blu-ray), просмотренных в течение года. Для каждого фильма желательно регистрировать разнообразную информацию, такую как название, год выпуска, имена и фамилии режиссера и ведущих актеров, продолжительность и жанр (комедия, научная фантастика, романтика, мелодрама и т.п.), рейтинг и т.д. Это предполагает применение структуры для каждого фильма и массива структур для списка фильмов. В целях простоты ограничим структуру двумя членами: названием фильма и собственной оценкой его рейтинга по 10-балыюй шкале. В листинге 17.1 приведена элементарная реализация, использующая этот подход.

Листинг 17.1. Программа films 1. c

720 глава 17

Программа создает массив структур и заполняет его данными, которые вводит пользователь. Ввод продолжается вплоть до заполнения массива (проверка FMAX), до достижения конца файла (проверка NULL) или до нажатия пользователем клавиши в начале строки (проверка ‘\0’).

Такая организация программы сопряжена с рядом проблем. Во-первых, скорее всего, программа будет напрасно тратить большой объем памяти, поскольку названия большинства фильмов содержат меньше 40 символов, но, в то же время, названия некоторых фильмов могут быть весьма длинными, такими как “Скромное обаяние буржуазии” или “Вон Тон Тон, пес, который спас Голливуд”. Во-вторых, ограничение в пять фильмов в год многим покажется излишне строгим. Конечно, этот предел можно увеличить, но каким он должен быть? Кто-то просматривает до 500 фильмов в год, поэтому значение FMAX можно было бы увеличить до 500, но для некоторых и этого может

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

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

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

Здесь, как и в главе 12, указатель movies можно применять так, как если бы он был именем массива:

while (i < FMAX && gets (movies [i].title) != NULL && movies[i].title [0] != '\0')

За счет использования функции malloc() вы можете отложить определение количества элементов до момента выполнения программы, поэтому не придется выделять память для 500 элементов, если их необходимо только 20. Но при таком подходе обязанность ввести корректное значение для количества записей возлагается на пользователя.

От массива к связному списку

В идеале было бы желательно иметь возможность добавлять данные неограниченно (или до тех пор, пока программа не исчерпает свою доступную память), не указывая заранее количество записей, которые будут созданы, и не вынуждая программу выделять огромное пространство памяти без реальной на то необходимости. Этой цели можно достигнуть, вызывая malloc() после ввода каждой записи и выделяя лишь такой объем памяти, которого достаточно для новой записи. Если пользователь вводит информацию о трех фильмах, программа вызывает функцию malloc() три раза. Если пользователь вводит информацию о 300 фильмах, программа вызывает malloc() триста раз.

Такая, прекрасная на первый взгляд, идея порождает новую проблему. Чтобы увидеть, в чем она заключается, сравните однократный вызов malloc() для выделения памяти под300 структур film с 300-кратным вызовом этой функции для выделения памяти каждый раз только для одной структуры film. В первом случае память распределяется в виде одного непрерывного блока, и для отслеживания содержимого требуется