Похожие презентации:
Стеки, очереди и деки
1.
ФГБОУ ВО РГУПСАлгоритмизация и
программирование
Динамические структуры данных.
Стеки, очереди и деки
Лекция 10
© Составление,
О.В. Игнатьева
Ростов-на-Дону
2020
2.
План лекцииСтеки
Очереди
Деки
2
3.
Стеки, очереди и декиЭто такие динамические структуры,
представляющие собой списки, для
которых разрешены только операции
вставки и удаления первого и/или
последнего элемента.
3
4.
Стеки5.
СтекСтек - извлечение и добавление элементов в
нем происходит по правилу «Последний пришел,
первый вышел» (LIFO — last in, first out).
Добавление и извлечение элементов проводится
с головы.
5
6.
СтекСтек – это упорядоченный набор элементов, в
котором добавление новых и удаление существующих элементов допустимо только с одного
конца, который называется вершиной стека.
На рисунке показан
стек, содержащий 6
элементов.
6
7.
СтекВ современных компьютерах стек используется
для:
размещения локальных переменных;
размещения параметров процедуры или
функции;
сохранения адреса возврата (по какому адресу
надо вернуться из процедуры);
временного хранения данных, особенно при
программировании на Ассемблере.
7
8.
СтекНа стек выделяется ограниченная область памяти.
При каждом вызове функции в стек добавляются
новые элементы (параметры, локальные
переменные, адрес возврата). Поэтому если
вложенных вызовов будет много, стек переполнится.
Очень опасной в отношении переполнения стека
является рекурсия, поскольку она как раз и
предполагает вложенные вызовы одной и той же
функции. При ошибке в программе рекурсия может
стать бесконечной, кроме того, стек может
переполниться, если вложенных вызовов будет
слишком много.
8
9.
СтекСтек можно реализовать на основе двухсвязного списка
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
Стек - это двухсвязный список, в котором разрешены
только операции добавления нового элемента в голову
списка и удаление элемента с головы списка, согласно
принципу LIFO.
9
10.
СтекДля работы со стеком надо определить, как выполняются
две операции – добавление элемента на вершину стека
(Push) и снятие элемента с вершины стека (Pop). При этом
количество элементов стека ограничивается только доступным объемом памяти.
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
10
11.
СтекВ программе надо объявить два новых типа
данных – узел списка Node и указатель на него
PNode.
Синтаксис объявления стека в С++:
Чтобы не работать с отдельными
struct Node
указателями на хвост и голову
{
списка, объявим структуру, в
Тип1 поле1;
которой будет храниться вся
Тип2 поле2;
информация о стеке:
…..
Node *next;
Node *prev;
};
typedef Node * PNode;
struct Stack
{
PNode Head, Tail;
};
11
12.
СтекПример. Объявление стека словаря:
struct Node
{
string word;
Node *next;
Node *prev;
};
typedef Node *PNode;
struct Stack
{
PNode Head, Tail;
};
Stack S;
S.Head = NULL;
S.Tail = NULL;
Например, опишем стек для представления
словаря русских слов.
Область данных
ссылка на следующий узел
ссылка на предыдущий узел
тип данных - указатель на узел
Объявление структуры, где будет
храниться вся информация о стеке
Объявление стековой переменной
Указатель на начало списка. В начале
работы указатель Head равен NULL
Указатель на конец списка. В начале
работы указатель Tail равен NULL
13.
Стеки. ОперацииОперации над стеком:
Добавление нового узла в список – операция Push
Извлечение (удаление) узла из списка – операция Pop
Pop
Push
14.
Создание нового узлаДля стека мы не будем отдельно создавать функцию для создания
нового узла, которая включала только выделение памяти под
новый узел и запоминание адреса выделенного блока, так как у
нас нет возможности вставлять узел в произвольное место списка.
В стеке новый узел можно вставить только в начало списка, поэтому
объединим вместе две операции CreateNode и AddFirst.
Также немного переделаем листинг кода, чтобы работать не с
отдельными указателями, а со структурой типа Stack.
Создание нового узла
PNode NewNode = new Node;
NewNode->word = NewWord;
NewNode->next = NULL;
NewNode->prev = NULL;
14
15.
Добавление узла на вершину стекаПри добавлении нового узла NewNode на вершину стека надо:
2) установить ссылку next
узла NewNode на голову
существующего списка и его
ссылку prev в NULL;
NewNode->next = Head;
NewNode->prev= NULL;
1) создать новый узел
Null
3) установить ссылку prev
бывшего первого узла (если он
существовал) на NewNode;
if ( Head!=NULL )
Head->prev = NewNode;
5) если в списке не было ни одного
элемента, хвост списка также
устанавливается на новый узел.
4) установить голову списка на новый узел;
Head = NewNode;
if ( Tail == NULL ) Tail = Head;
16.
Добавление узла на вершину стека// функция добавления нового узла в стек
void Push ( Stack &S, string data )
{
PNode NewNode;
NewNode = new Node;
NewNode->word = data;
NewNode->next = S.Head;
NewNode->prev = NULL;
if ( S.Head !=NULL)
S.Head->prev = NewNode;
S.Head = NewNode;
if ( S.Tail ==NULL)
S.Tail = S.Head;
}
Важно, что адрес стека
передаётся по ссылке
Алгоритм создания нового
узла
Алгоритм добавления нового
узла в начало двухсвязного
списка
16
17.
Снятие (удаление узла) свершины стека
Функция Pop удаляет верхний элемент и возвращает его
данные.
Эта операция идентична операции
Pop
удаления узла из двухсвязного списка,
но только при условии что он является
первым.
Адрес OldNode нам передавать не
нужно, так как мы знаем, что он первый
18.
Снятие (удаление узла) свершины стека
1) Узнаем адрес первого узла
PNode TopNode = S.Head;
2) Если список пустой, то выведем
сообщение и выходим из функции
if ( TopNode==NULL )
return “Список пустой”;
3) Сохраняем данные об узле
data = TopNode->word;
4) Рассмотрим только один случай
если удаляемый элемент
является первым!!
S.Head = TopNode->next;
5) Проверяем , это был единственный
элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку
головы, а иначе все пусто!
if ( S.Head != NULL )
S.Head->prev = NULL;
else S.Tail = NULL;
}
6) Освобождаем память, которую
занимал узел.
delete TopNode;
7) Выводим данные о узле
return data;
19.
Снятие узла с вершины стекаstring Pop ( Stack &S )
{
PNode TopNode = S.Head;
string data;
if ( TopNode==NULL )
return “Список пустой”;
data = TopNode->word;
S.Head = TopNode->next;
if ( S.Head != NULL )
S.Head->prev = NULL;
else
S.Tail = NULL;
delete TopNode;
return data;
}
// удаляем первый элемент
// встали на начало списка
// если список пустой, то
выведем сообщение и
выходим из функции
// иначе сохранили данные
// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент
// изменяем ссылки головы
// удаляем последний элемент
// освобождаем память
// возвращение данных, чтобы вывести
информацию о узле, который удалили
19
20.
Вывод всех элементов стека// Обход списка с головы списка
void Print ( Stack &S )
{
PNode TopNode = S.Head;
// начинаем с вершины стека
// пока не дошли до конца
while (TopNode != NULL)
{
cout<<TopNode->word<<endl;
// выводим данные узла
TopNode=TopNode->next;
// переходим к следующему
узлу
}
}
20
21.
Поиск узла в спискеЧасто требуется найти в списке нужный элемент (его адрес или данные).
Надо учесть, что требуемого элемента может и не быть, тогда просмотр
заканчивается при достижении конца списка.
Такой подход приводит к следующему алгоритму:
1) начать с головы списка;
PNode q = S.Head;
2) пока текущий элемент существует
(указатель – не NULL), проверить
нужное условие и перейти к
следующему элементу;
3) закончить, когда найден
требуемый элемент или все элементы
while (q->word != NewWord && q!=NULL)
списка
q = q->next;
просмотрены.
return q;
Поиск по данным
21
22.
Поиск узла в спискеНапример, следующая функция ищет в списке элемент,
соответствующий заданному слову (для которого поле word
совпадает с заданной строкой NewWord), и возвращает его адрес
или NULL, если такого узла нет.
// функция поиска узла в списке
PNode Find (Stack S, string NewWord)
//пока текущий элемент существует
{ //начать с головы списка
(указатель – не NULL), проверить
PNode q = S.Head;
нужное условие и перейти к
следующему элементу
while (q->word != NewWord && q != NULL)
q = q->next;
return q;
}
закончить, когда найден
требуемый элемент или все
элементы списка
просмотрены
22
23.
Очередь24.
ОчередьОчередь - список, операции
чтения и добавления
элементов в котором
подвержены правилу «Первый
пришел, первый вышел»
(FIFO — first in, first out) .
При этом, при чтении элемента,
он удаляется из очереди. Таким
образом, для чтения в очереди
доступна только голова, в то
время как добавление
проводится только в хвост.
24
25.
ОчередьОчередь – это упорядоченный набор элементов, в
котором добавление новых элементов допустимо с
одного конца (он называется начало очереди), а
удаление существующих элементов – только с
другого конца, который называется концом
очереди.
25
26.
ОчередьОчередь называют структурой типа FIFO (First In
– First Out) – первым пришел, первым ушел.
Хорошо знакомой моделью является очередь в
магазине. На рисунке изображена очередь из 3-х
элементов.
26
27.
ОчередьНаиболее известные примеры применения очередей в
программировании – очередь событий системы Windows
и ей подобных.
Очереди используются также для моделирования в
задачах массового обслуживания (например,
обслуживания клиентов в банке).
27
28.
ОчередьОчередь можно реализовать на основе двухсвязного списка
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
Очередь - это двухсвязный список, в котором разрешены
только операции добавления нового элемента в хвост
списка и удаление элемента с головы списка, согласно
28
принципу FIFO.
29.
ОчередьДля работы с очередью надо определить, как выполняются
две операции – добавление элемента в конец очереди
(Push) и снятие (удаление) элемента с головы списка (Pop).
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
29
30.
ОчередьВ программе надо объявить два новых типа
данных – узел списка Node и указатель на него
PNode.
Синтаксис объявления очереди в С++:
Чтобы не работать с отдельными
struct Node
указателями на хвост и голову
{
списка, объявим структуру, в
Тип1 поле1;
которой будет храниться вся
Тип2 поле2;
информация о очереди:
…..
Node *next;
Node *prev;
};
typedef Node * PNode;
struct Queue
{
PNode Head, Tail;
};
30
31.
ОчередьПример. Объявление очереди словаря:
struct Node
{
string word;
Node *next;
Node *prev;
};
typedef Node *PNode;
struct Queue
{
PNode Head, Tail;
};
Queue Q;
Q.Head = NULL;
Q.Tail = NULL;
Например, опишем очередь для
представления словаря русских слов.
Область данных
ссылка на следующий узел
ссылка на предыдущий узел
тип данных - указатель на узел
Объявление структуры, где будет
храниться вся информация о очеред
Объявление переменной очереди
Указатель на начало списка. В начале
работы указатель Head равен NULL
Указатель на конец списка. В начале
работы указатель Tail равен NULL
32.
Очередь. ОперацииОперации над очередью:
Добавление нового узла в конец очереди – операция Push
Извлечение (удаление) узла с начала очереди – операция
Pop
Pop
Push
33.
Добавление узла в очередьФактически это добавление нового элемента в конец двусвязного
списка. Объединим две операции создание нового узла и добавление в
конец списка.
Null
1) Создать новый узел
3) установить ссылку next
бывшего конечного узла (если
он существовал) на NewNode;
if ( Tail!=NULL )
Tail->next = NewNode;
4) установить хвост списка на новый узел;
Tail = NewNode;
2) установить ссылку prev
узла NewNode на хвост
существующего списка и его
ссылку next в NULL;
NewNode->prev = Tail;
NewNode->next = NULL;
5) если в списке не было ни одного
элемента, голову списка также
устанавливается на новый узел.
if ( Head == NULL )
Head = Tail;
34.
Добавление узла в конец очереди// функция добавления нового узла в очередь
void Push (Queue &Q, string data )
{
PNode NewNode;
NewNode = new Node;
NewNode->word = data;
NewNode->prev = Q.Tail;
NewNode->next = NULL;
Важно, что адрес очереди
передаётся по ссылке
Алгоритм создания нового
узла
Алгоритм добавления нового
узла в конец двухсвязного
списка
if ( Q.Tail != NULL )
Q.Tail->next = NewNode;
Q.Tail = NewNode;
if (Q.Head == NULL) Q.Head = Q.Tail;
}
34
35.
Снятие (удаление узла) с началаочереди
Функция Pop удаляет верхний элемент и возвращает его
данные.
Более того, функция для получения
первого элемента очереди (Pop)
совпадает с функцией снятия
элемента с вершины стека.
Pop
36.
Снятие (удаление узла) с началаочереди
1) Узнаем адрес первого узла
PNode TopNode = Q.Head;
2) Если список пустой, то выведем
сообщение и выходим из функции
if ( TopNode==NULL )
return “Список пустой”;
3) Сохраняем данные об узле
data = TopNode->word;
4) Рассмотрим только один случай
если удаляемый элемент
является первым!!
Q.Head = TopNode->next;
5) Проверяем , это был единственный
элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку
головы, а иначе все пусто!
if ( Q.Head != NULL )
Q.Head->prev = NULL;
else Q.Tail = NULL;
}
6) Освобождаем память, которую
занимал узел.
delete TopNode;
7) Выводим данные о узле
return data;
37.
Снятие узла с головы очередиstring Pop (Queue &Q )
{
PNode TopNode = Q.Head;
string data;
if ( TopNode==NULL )
return “Список пустой”;
data = TopNode->word;
Q.Head = TopNode->next;
if ( Q.Head != NULL )
Q.Head->prev = NULL;
else
Q.Tail = NULL;
delete TopNode;
return data;
}
// удаляем первый элемент
// встали на начало списка
// если список пустой, то
выведем сообщение и
выходим из функции
// иначе сохранили данные
// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент
// изменяем ссылки головы
// удаляем последний элемент
// освобождаем память
// возвращение данных, чтобы вывести
информацию о узле, который удалили
37
38.
Вывод всех элементов очереди// Обход списка с головы списка
void Print (Queue &Q )
{
PNode TopNode = Q.Head;
// начинаем с вершины очереди
// пока не дошли до конца
while (TopNode != NULL)
{
cout<<TopNode->word<<endl;
// выводим данные узла
TopNode=TopNode->next;
// переходим к следующему
узлу
}
}
38
39.
Дек40.
ДекДек (deque) - это упорядоченный набор
элементов, в котором добавление новых и
удаление существующих элементов
допустимо с любого конца.
40
41.
ДекДек может быть реализован на основе двусвязного
списка. Для дека разрешены четыре операции:
1) добавление элемента в начало;
2) добавление элемента в конец;
3) удаление элемента с начала;
4) удаление элемента с конца.
Их можно реализовать, используя написанные
выше функции для стека и очереди.
41
42.
Спасибо за внимание!43.
Литературные источники1) К. Поляков. Программирование на языке С++.
2). Харви Дейтел, Пол Дейтел. Как программировать на
С++. - М: Вильямс, - 1011 с.
3). Струструп Б. Программирование: принципы и
практика использования С++. – М. : Вильямс, 2011. –
1248 с.
4). Струструп Б. Язык программирования С++. – М.:
Бином. - 1054 с.
5). Лафоре Р. Объектно-ориентированное
программирование в С++. Питер, 2004. – 922 с.
6). Шилдт Г. С++: руководство для начинающих, 2-е
издание. – М: Вильямс, 2005. -672 с.