Однонаправленные (односвязные) списки

Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа.

Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка (рис. 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; //указатель на текущий элемент списка (при необходимости)