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

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

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

Рис. 29.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;

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

Дата добавления: 2015-07-26; просмотров: 160; Нарушение авторских прав

Мы поможем в написании ваших работ!