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

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

Многие задачи программирования используют динамические структуры данных. Например, организация каталога книг в библиотеке. Нельзя заранее определить количество книг, числящихся в библиотечном фонде, так как идет постоянное поступление новых книг и списание старых. Для реализации таких задач существуют различные связные списки: однонаправленные, двунаправленные; бинарные деревья и т.д.

Элементы списка называются узлами. Узел представляет собой объект, содержащий в себе указатель на другой объект того же типа и данные. Очевидным способом реализации узла является структура:

struct TelNum {

TelNum * next; //указатель на следующий элемент

long telephon; // данные

char name[30]; // данные

};

TelNum *temp = new TelNum; - создается новый узел.

Список представляет собой последовательность узлов, связанных указателями, содержащимися внутри узла. Узлы списка создаются динамически в программе по мере необходимости с помощью соответсвующих функций и располагаются в различных местах динамической памити. При уничтожении узла память обязательно освобождается.

Простейшим списком является линейный или однонаправленный список. Признаком конца списка является значение указателя на следующий элемент равное NULL. Для работы со списком должен существовать указатель на первый элемент - заголовок списка. Иногда удобно иметь и указатель на конец списка.

Указатель

заголовок

Основными операциями, производимыми со списками, являются обход, вставка и удаление узлов. Можно производить эти операции в начале списка, в середине и в конце.