Стивен Прата - Язык программирования 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. В первом случае память распределяется в виде одного непрерывного блока, и для отслеживания содержимого требуется

722 Глава 17 единственная переменная указателя на структуру (film), которая указывает на первую структуру в блоке. Как было показано в приведенном ранее фрагменте кода, простая форма записи с массивом обеспечивает указателю доступ к каждой структуре внутри блока. Проблема со вторым подходом — отсутствие какой-либо гарантии того, что последовательные вызовы malloc() приведут к выделению смежных блоков памяти. Это означает, что структуры не обязательно будут сохранены непрерывно (рис. 17.1). Таким образом, вместо хранения одного указателя на блок из 300 структур придется хранить 300 указателей — по одному для каждой независимо выделенной структуры!

Рис. 17.1. Выделение памяти под структуры одним блоком и выделение памяти под структуры индивидуально

Одно из возможных решений, которое, однако, мы применять не будем, предполагает создание большого массива указателей и присваивание значений указателям друг за другом по мере выделения памяти под новые структуры:

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

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

тво тратится впустую на хранение неиспользуемых указателей, к тому же продолжает действовать ограничение в 500 структур.

Существует более эффективный способ. При каждом вызове функции malloc() для выделения памяти под новую структуру одновременно можно выделять память и для нового указателя. Но вы можете возразить, что тогда потребуется еще один указатель для отслеживания вновь выделенного указателя, а для его отслеживания необходим еще один указатель, и так до бесконечности. Предотвратить эту потенциальную проблему можно путем переопределения структуры так, чтобы она включала указатель на следующую структуру. Тогда при каждом создании новой структуры ее адрес можно будет сохранять в предыдущей структуре. Короче говоря, структуру film нужно переопределить гак, как показано ниже: