Однонаправленные (односвязные) списки
Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа. Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка (рис. 29.1). В последнем элементе указатель на следующий элемент равен NULL.
Описание простейшего элемента такого списка выглядит следующим образом: struct имя_типа { информационное поле; адресное поле; }; где информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка. Например: struct Node { int key;//информационное поле Node*next;//адресное поле }; Информационных полей может быть несколько. Например: struct point { char*name;//информационное поле int age;//информационное поле point*next;//адресное поле }; Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой. Основными операциями, осуществляемыми с однонаправленными списками, являются:
Особое внимание следует обратить на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен. Рассмотрим подробнее каждую из приведенных операций. Для описания алгоритмов этих основных операций используется следующее объявление: struct Single_List {//структура данных int Data; //информационное поле Single_List *Next; //адресное поле }; .......... Single_List *Head; //указатель на первый элемент списка .......... Single_List *Current; //указатель на текущий элемент списка (при необходимости)
|
