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

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

Рис. Линейный однонаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле – это указатель на объект того же типа, что и определяемая структура; в него записывается адрес следующего элемента списка, а для последнего элемента значение данного поля NULL.

Например:

struct Node {

int key;//информационное поле

Node*next;//адресное поле

};

Информационных полей может быть несколько.

Например:

struct point {

char*name;//информационное поле

int age;//информационное поле

point*next;//адресное поле

};

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

Над списками можно выполнять следующие операции:

· начальное формирование списка (создание первого элемента);

· добавление элемента в конец списка;

· добавление элемента в начало списка;

· удаление элемента с заданным номером;

· чтение элемента с заданным ключом;

· вставка элемента в заданное место списка (до или после элемента с заданным ключом);

· упорядочивание списка по ключу

· и др.