Двухсвязные линейные списки
Как мы уже говорили, линейные списки могут быть односвязными и двухсвязными.
Каждый элемент односвязного списка, кроме собственно данных, содержит поле с адресом следующего элемента. Работу с такими списками мы только что рассмотрели.
В двухсвязном списке каждый элемент имеет поля с данными и два указателя: один указатель хранит адрес предшествующего элемента списка, второй — адрес последующего элемента. Вполне естественно для работы с двухсвязным списком использовать два указателя, хранящие адреса начала и конца такого списка. На рисунке ниже даётся графическое представление двухсвязного списка.
Рассмотрим особенности работы с двухсвязным списком.
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; // указатель на последующий элемент
};
Затем в программе определяем два указателя:
Queue *Begin = NULL; // Начало очереди
Queue *End = NULL; // Конец очереди
После этого можно начать работать с очередью.