Динамические структуры данных: однонаправленные и двунаправленные списки

Цель лекции: изучить понятия, классификацию и объявление списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

Понятие списка хорошо известно из жизненных примеров: список студентов учебной группы, список призёров олимпиады, список (перечень) документов для представления в приёмную комиссию, список почтовой рассылки, список литературы для самостоятельного чтения и т.п.

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения , исключения. Список , отражающий отношения соседства между элементами, называется линейным.

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

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

Линейные связные списки являются простейшими динамическими структурами данных . Из всего многообразия связанных списков можно выделить следующие основные:

• однонаправленные (односвязные) списки;
• двунаправленные ( двусвязные ) списки;
• циклические (кольцевые) списки.

В основном они отличаются видом взаимосвязи элементов и/или допустимыми операциями.

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

Однонаправленный (односвязный) список – это структура данных , представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка ( рис. 29.1). В последнем элементе указатель на следующий элемент равен NULL .

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

struct имя_типа поле ; адресное поле ; >;

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

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

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

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

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

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке
• проверка пустоты списка;
• удаление списка.

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

Рассмотрим подробнее каждую из приведенных операций.

Для описания алгоритмов этих основных операций используется следующее объявление:

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

Операция печати списка заключается в последовательном просмотре всех элементов списка и выводе их значений на экран. Для обработки списка организуется функция , в которой нужно переставлять указатель на следующий элемент списка до тех пор, пока указатель не станет равен NULL , то есть будет достигнут конец списка. Реализуем данную функцию рекурсивно.