Односвязный список.

Односвязный список. Наиболее простая динамическая информационная структура - это односвязный список, элементами (звеньями) которого служат объекты, например, такою структурного типа:

struct имя_структурного_типа

{

элементы _структуры; /* данные */

struct имя_структурного_типа * указатель;

};

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

Чтобы продемонстрировать некоторые особенности обработки простых динамических информационных структур, разработаем программу, в которой определим структурный тип для представления звеньев односвязного списка и решим такую простейшую задачу: "Ввести с клавиатуры произвольное количество структур, объединяя их в односвязный список, а затем вывести на экран дисплея содержимое введенного списка в порядке формирования его звеньев".

Анализ динамических информационных структур удобнее всего выполнять с помощью их графического изображения. На рис. 6.3 приведены схема односвязного списка и обозначения, которые будут использованы в программе. Для работы со списком понадобятся три указателя: beg - на начало списка; end -на последний элемент, уже включенный в список; rex - указатель для "перебора" элементов списка от его начала.

Рис. 6.3. Односвязный динамический список

Следующая программа решает сформулированную задачу.

Пример выполнения программы:

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

В программе ввод данных, т.е. заполнение односвязного списка структур, выполняется в цикле. Условием окончания цикла служит нулевое значение, введенное для элемента int weight, очередной структуры.

Формирование списка структур происходит динамически. Указатели beg, end инициализированы нулевыми значениями - вначале список пуст.

Обратите внимание на преобразование типов (struct cell *) при выделении памяти для структуры типа struct cell. Функция malloc( ) независимо от типа параметров всегда возвращает указатель типа void *, а слева от знака присваивания находится указатель rex типа struct cell *.

Используется явное приведение типов, хотя это не обязательно - тип void * совместим по операции присваивания с указателем на объект любого типа.

Остальные особенности программы поясняются комментариями в ее тексте.