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

#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.

Рис. 1 7.3. Связный список с двумя элементами

Обработка информации о каждом новом фильме будет выполняться аналогично. Адрес новой структуры будет сохраняться в предыдущей структуре, в новую структуру будет помещаться введенная информация, а значение члена next новой структуры будет устанавливаться в NULL, что приведет к созданию связного списка, подобного представленному на рис. 17.4.

Рис. 1 7.4. Связный спшок с несколькими элементами

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

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

Использование связного списка

Теперь, когда вы получили представление о работе связного списка, давайте реализуем его. В листинге 17.2 представлен модифицированный код из листинга 17.1, в котором для хранения информации о фильмах вместо массива применяется связный список.

Листинг 17.2. Программа films2.c

726 глава 17

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

Отображение списка

Идея заключается в том, чтобы начать с установки указателя (назовем его current) в ссылку на первую структуру. Поскольку указатель на заголовок (по имени head) уже указывает, куда нужно, следующего кода вполне достаточно:

current = head;

Затем с помощью формы записи с указателем можно обратиться к членам этой структуры:

printf("Фильм: %s Рейтинг: %d\n", current->title, current->rating);

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

current = current->next;

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

По завершении весь процесс необходимо повторить. После отображения последнего элемента в списке указатель current будет установлен в NULL, т.к. это значение члена next последней структуры. Данным обстоятельством можно воспользоваться для прекращения вывода. Фрагмент кода из films2.c, применяемый для отображения списка, выглядит следующим образом:

while (current != NULL)

{

printf("Фильм: %s Рейтинг: %d\n", current->title, current->rating); current = current->next;

}

Почему бы для перемещения по списку не воспользоваться head вместо того, чтобы создавать новый указатель (current)? Причина в том, что это привело бы к изменению значения head, и программа лишилась бы возможности находить начало списка.

Создание списка

Создание списка предусматривает выполнение трех действий.

1. Использование функции malloc() для выделения достаточного пространства под структуру.

2. Сохранение адреса структуры.

3. Копирование в структуру корректной информации.

Не имеет смысла создавать структуру, если она пока не требуется, поэтому для приема от пользователя информации о названии фильма в программе применяется временное хранилище (массив input). Если пользователь эмулирует с помощью клавиатуры символ EOF или вводит пустую строку, цикл ввода завершается:

while (s_gets (input, TSIZE) != NULL && input [0] != '\n')

При наличии введенных данных программа запрашивает пространство для структуры и присваивает ее адрес переменной типа указателя current:

current = (struct film *) malloc(sizeof(struct film));

Адрес самой первой структуры должен быть сохранен в переменной типа указателя head. Адрес каждой последующей структуры должен сохраняться в члене next предыдущей структуры. Таким образом, программе необходим способ для выяснения того, является ли текущая структура первой. Проще всего решить эту задачу, инициализировав указатель head значением NULL в начале программы. Затем в программе можно использовать значение указателя head для принятия решения о дальнейших действиях: