Двухсвязные линейные списки

Как мы уже говорили, линейные списки могут быть односвязными и двухсвязными.

Каждый элемент односвязного списка, кроме собственно данных, содержит поле с адресом следующего элемента. Работу с такими списками мы только что рассмотрели.

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

Рассмотрим особенности работы с двухсвязным списком.

1. Как и в случае с односвязным списком, создадим две структуры. Описание этих структур расположим в начале программы (до main() и других функций). Вот возможная реализация структур:

struct Data

{

int a; // данные

};

struct DList

{

Data d;

DList *prev; // указатель на предшествующий элемент

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

};

2. Затем создаём два указателя:

DList *Begin = NULL; // Начало списка

DList *End = NULL; // Конец списка

3. Теперь можно формировать какой-то начальный список. Делаем это по аналогии с тем, как делали при работе с односвязными списками. Начнём формировать список из трёх чисел 3, 5 и 1:

// Создаём первый элемент

DList *t = new DList;

t->d.a = 3;

t->prev = NULL;

t->next = NULL;

// Настроим на него оба указателя

Begin = t;

End = t;

//++++++++++++++++++++++++следующая пара+++++++++++++++

// Создаём второй элемент

t->next = new DList;

DList *p = t;

t = t->next;

t->prev = p;

t->d.a = 5;

t->next = NULL;

End = t;

// Создаём третий элемент

t->next = new DList;

p = t;

t = t->next;

t->prev = p;

t->d.a = 1;

t->next = NULL;

End = t;

Всё, список из трёх чисел создан. Приведём хотя бы некоторые действия с этим списком.

1.Обход списка в прямом направлении и его вывод на экран монитора:

void print_forward(DList *Begin)

{

DList *p = Begin;

cout << "Spisok (forward):" << endl;

while(p)

{

cout << p->d.a << endl;

p = p->next;

}

Возможный вызов функции:

print_forward(Begin);

Как видим, полученная реализация по сути является копией функции print() для печати односвязного списка.

2.Обход списка в обратном направлении и его вывод на экран монитора:

void print_back(DList *End)

{

DList *p = End;

cout << "Spisok (back):" << endl;

while(p)

{

cout << p->d.a << endl;

p = p->prev;

}

Возможный вызов функции:

print_back(End);

И здесь сходство большое. Важно обратить внимание на оператор, за счет которого выполняется движение назад:

p = p->prev;

На других операциях с двухсвязными списками останавливаться не будем, так как их можно разработать по аналогии с операциями для односвязных списков.

Кольцевой список

Кольцевой список — это список, у которого последний элемент связан с первым. Кольцевой список можно сделать как односвязным, так и двухсвязным. Рассмотрим вкратце односвязный кольцевой список.

Схема кольцевого списка представлена на рисунке ниже (используем те же данные, что и для ранее рассмотренного односвязного списка, т.е. список из чисел 3, 5, 1, 9):

Используем те же структуры (Data и List), что применяли для односвязного списка. Точно так же определяем указатель на начало будущего списка:

List *u = NULL;

и так же делаем начальное заполнение списка. Но в конце, после того, как для нашего примера мы занесли число 9 в список, требуется «замкнуть» список на начало:

x->next = u;

В итоге будет получен кольцевой список.

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

void printC(List *u)

{

if(u != NULL)

{

List *p = u;

cout << "Kolcevoj Spisok:" << endl;

cout << p->d.a << endl;

p = p->next;

while(p != u)

{

cout << p->d.a << endl;

p = p->next;

}

else

cout << "Spisok pust." << endl;

}

Возможный вызов функции:

printC(u);

Как видно из примера, после печати первого элемента, мы печатаем не до конца списка, а до нахождения начала.

Другие операции для кольцевого списка разработайте самостоятельно.

Стеки

Определение стека

Стек — динамическая структура данных, для которой выполняется правило: последним пришёл — первым ушёл. Таким образом, и дополнение новых данных, и извлечение их из стека всегда выполняется с одной стороны.

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

Операции со стеком

Рассмотрим основные и дополнительные действия со стеком. Для работы используем структуры Data и Stack:

struct Data

{

int a;

};

struct Stack

{

Data d;

Stack *next;

};

В программе определяем указатель на начало будущего стека:

Stack *u = NULL;

После этого можно начать работать со стеком.

1. Добавление в стек. Функцию добавления назовём Push() — по аналогии с командой ассемблера push, которая заносит целое число в программный стек.

void Push(Stack **u, Data &x)

{

Stack *t = new Stack; // Память под новый элемент

t->d.a = x.a; // Заполнение полей

t->next = *u; // Подключаем новый элемент к имеющимся

*u = t; // Перенастройка вершины

}

Обратиться к функции можно так:

Push(&u,x);

где x — объект типа Data.

2. Извлечение из стека. Здесь снова аналогия с ассемблером (команда pop выталкивает целое число из стека).

bool Pop(Stack **u, Data &x)

{

if(*u == NULL)

{

cout << "Pustoj Stack" << endl;

return false;

}

Stack *t = *u;

x.a = t->d.a; // Получаем значения полей на вершине стека

*u = t->next; // Перенастройка вершины

delete t; // Удаление ненужного элемента

return true;

}

Пример вызова функции:

Data y;

if(Pop(&u, x))

{

y = x;

cout << "y=" << y.a << endl;

}

Дополнительные действия со стеком — распечатка стека (можно взять алгоритм для работы с односвязным списком) и чтение с вершины стека. Чтение напоминает извлечение, но при этом данные из стека не удаляются. Вот возможный вариант реализации:

bool Read(Stack **u, Data &x)

{

if(*u == NULL)

{

cout << "Pustoj Stack" << endl;

return false;

}

Stack *t = *u;

x.a = t->d.a; // Заполнение полей

return true;

}

Использование функции Read() может быть аналогичным использованию Pop().

Очереди

Определение очереди

Очередь — это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры, а удаление (извлечение) — только с начала. В англоязычной литературе этот принцип называется FIFO (First Input — First Output, т.е. первый пришёл — первый ушёл).

Примером из реальной жизни может быть очередь из покупателей к кассе в магазине.

Как не трудно понять, очередь — это линейный список, для которого определены всего две основные операции: добавление в конец и извлечение с начала. Значит, удобно иметь два указателя: на начало и конец этой динамической структуры. Но списки бывают односвязные и двухсвязные. Какой использовать? Подойдёт только двухсвязный список. В этом можно будет убедиться при рассмотрении основных алгоритмов для работы с очередью.

На рисунке ниже показано графическое представление очереди. Как и в предыдущих темах, очередь будем строить из целых чисел, например: 3, 5, 1.

Для работы используем структуры Data (данные) и Queue (очередь):

struct Data

{

int a;

};

struct Queue

{

Data d;

Queue *prev; // указатель на предшествующий элемент

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

};