2.9 Связные списки, очереди, стеки

2.9.1.Односвязные и двусвязные списки.

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

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

Рис. Односвязного списка.

Элемент односвязного списка включает только указатель на следующий элемент.

typedef struct {

char name [20];//автор книги

chartitle[44];//наименование

intyear;//год издания

float price;//цена

}book;

struct list {

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

bookinfo;//информационные поля

};

Предполагается, что память, отводимая под элемент списка выделяется динамически, поэтому при реализации списков памяти его длина ограничивается только доступным объёмом памяти. Информационное поле представляет собой структурную переменную по шаблону book. Признаком последующего элемента списка является равенство на NULL поля next. Реализация односвязного списка требует наличия операций add() – добавление элементов в список, detach() – удаление элемента из списка, destroy() – освобождение памяти, занятой элементом списка. Помимо этих основных операций могут реализовываться и другие операции:

Display( )вывод по порядку всех элементов списка

PrintOn( )вывод заданного элемента списка

HasMember( )определение того содержится ли в списке элемент

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

Пример.

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

А так как список имеет и начало, и конец, описываются 2 указателя головы и хвоста списка. Элемент двусвязного списка содержит 2 указателя и информационные поля.

Пример элемента двусвязного списка.

struct dlist{

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

BOOK *info; //информационные поля

struct dlist *prev; //указатель на предыдущий элемент

};

struct dlist *heed; //указатель на 1 элемент списка

struct dlist *tail; //указатель на последний элемент

Признаком на 1 элемент могут служить равенство на NULL указателя prev. Признаком последнего элемента является next=NULL. Число операций, определяемых для двусвязного списка значительно больше, чем для односвязного, может включать:

add( )– добавление нового элемента к списку. По умолчанию принимают, что добавление применяется в начало списка;

addAtHead ( )– добавление элемента в начало списка;

addAtTail ( )– добавление элемента в конец списка;

AestroyFromHead ()– освобождение памяти, выделенной для данного элемента, поиск которого выполняется от начала;

AestroyFromTeil ()– освобождение с поиском конца;

detach ( )– удаление данного элемента из списка. По умолчанию обычно принимают, что поиск элемента от начала списка;

detachFromHead ()– удаление элемента из списка с поиском от начала списка;

detachFromTail ()– удаление элемента из списка с поиском от конца списка.

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