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

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

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

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

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

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

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

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

#define TSIZE 45 /* размер массива для хранения названий */

struct film {

char title[TSIZE]; int rating; struct film * next;

};

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

Прежде чем взглянуть на код С для связного списка, давайте подробнее рассмотрим концепции, лежащие в основе такого списка. Предположим, что в качестве названия фильма пользователь вводит Modern Times и 10 для значения рейтинга. Программа выделила бы память для структуры film, скопировала бы строку Modern Times в член title и установила бы значение члена rating равным 10. Чтобы указать на то, что за этой структурой никаких других структур не следует, программа должна была бы установить значение члена-указателя next в NULL. (Вспомните, что NULL — символическая константа, определенная в файле stdio.h, которая представляет нулевой указатель.) Разумеется, необходимо отслеживать место хранения первой структуры. Это можно делать, присвоив адрес отдельному указателю, который мы будем называть указателем на заголовок списка. Указатель на заголовок указывает на первый элемент в связном списке элементов. На рис. 17.2 показано, как выглядит эта структура. (Пустая область в члене title сжата для уменьшения размера рисунка.) Теперь предположим, что пользователь вводит название и рейтинг второго фильма — скажем, Midnight in Paris и 8. Программа выделяет память для второй структуры film и сохраняет адрес новой структуры в члене next первой структуры (перезаписывая ранее установленное значение NULL), чтобы указатель next ссылался на следующую структуру в связном списке.

Рис. 1 7.2. Первый элемент в связном списке

724 глава 17

Затем программа копирует значения Midnight in Paris и 8 в новую структуру и устанавливает значение ее члена next в NULL, указывая, что теперь эта структура является последней в списке. Такой список из двух элементов продемонстрирован на рис. 17.3.