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

Рис. 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 для принятия решения о дальнейших действиях: