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

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

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

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

typedef struct {

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

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

int year;//год издания

float price;//цена

}book;

struct list {

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

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

};

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

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

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

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

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

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

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

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

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 () – удаление элемента из списка с поиском от конца списка.

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

Очереди.

Основные примитивы для работы с очередью.

Очередь – это структура данных, организованная по принципу: первым вошёл, первым ушёл, или реализующая дисциплину FIFO.

Очередь элемента может быть реализована с использованием массивов связного списка или другим способом. Базовыми операциями для работы с очередью являются:

put () – поместить элемент в очередь;

get () – удалить элемент из очереди.

Чтобы не ограничивать максимальное число элементов в очереди наиболее целесообразно её построение в виде односвязного списка. Начало списка хранится во внутренней переменной head. Добавление новых элементов происходит в голову. Последний элемент помещается особым образом, например, после указателя на следующий элемент равного NULL. Извлечение элемента из очереди требует сканирование списка для поиска последнего элемента. Этот элемент удаляется из списка.

Стеки.

Дисциплина LIFO. Определение стека.

В отличие от очереди стек – это структура данных, которая реализует дисциплину: последним пришёл, первым вышел. Базовыми операциями для стека являются:

push () – добавить новый элемент в стек;

pop () – извлечь элемент из вершины стека;

реек () – взять элемент из вершины стека, не извлекая его, стек может быть реализован как массив элементов, связный список или каким-либо другим образом.