Однонаправленные (односвязные) списки
Динамические структуры данных – список.
Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.
Списком (или связанным списком) называется упорядоченное множество, состоящее из переменного числа элементов, связанных между собой, к которым применимы операции включения, исключения.
Основные отличия связного списка от стека и очереди следующие:
- для чтения доступен любой компонент списка;
- новые компоненты можно добавлять в любое место списка;
- при чтении компонент не удаляется из списка.
Из всего многообразия связанных списков можно выделить следующие основные:
- однонаправленные (односвязные) списки;
- двунаправленные (двусвязные) списки;
- циклические (кольцевые) списки.
В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.
Над списками выполняются следующие операции:
- начальное формирование списка (запись первого компонента);
- добавление компонента в конец списка;
- чтение компонента с заданным ключом;
- вставка компонента в заданное место списка (обычно после компонента с заданным ключом);
- исключение компонента с заданным ключом из списка.
Для формирования списка и работы с ним необходимо иметь четыре переменные типа указатель, первая из которых определяет начало списка, остальные вспомогательные.
Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа.
Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка (рис. 29.1). В последнем элементе указатель на следующий элемент равен NULL.
Рис. 29.1. Линейный однонаправленный список
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа
{
информационное поле;
адресное поле;
};
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.
Например:
struct pointer
{
int d; //информационное поле
pointer *p; //адресное поле
};
Информационных полей может быть несколько.
Например:
struct point
{
char *name; //информационное поле
int age; //информационное поле
point *next; //адресное поле
};
Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.
Основными операциями, осуществляемыми с однонаправленными списками, являются:
- формирование списка;
- добавление в список
- печать или просмотр (извлечение) списка;
- вставка элемента в список;
- удаление элемента из списка;
- поиск элемента в списке
- проверка пустоты списка;
- удаление списка.
Особое внимание следует обратить на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.
Рассмотрим подробнее каждую из приведенных операций.
Для описания алгоритмов этих основных операций используется следующее объявления:
struct pointer
{
int d; //информационное поле
pointer *p; //адресное поле
};
. . . . . . . . . .
pointer *ph; //указатель на первый элемент списка
pointer *pk; //указатель на конец списка
. . . . . . . . . .
pointer *pc; //указатель на текущий элемент списка (при необходимости)