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

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

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

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

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

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;

//указатель на текущий элемент списка (при необходимости)

Date: 2016-07-25; view: 377; Нарушение авторских прав