Как назвал свою книгу Н.Вирт, «Алгоритмы + структуры данных = программы».
Наиболее популярные структуры данных: массив, очередь, стек, дек, список, дерево, граф.
Очередь — это структура данных, организованная по принципу «первый пришел, первый ушел», по английски First In First Out, сокращенно FIFO. В бытовом смысле это обычная очередь.
Queue
Список предписаний структуры «Очередь элементов типа E»:
1. Начать работу
2. Сделать очередь пустой
3. Очередь пуста: да/нет
4. Добавить элемент <вх: E> в конец очереди
5. Взять элемент из начала очереди в <вых: E>
6. Начало очереди: E
7. Удалить начало очереди
8. Кончить работу
Стек — это структура данных, организованная по принципу «последний пришел, первый ушел», по английски Last In First Out, сокращенно LIFO. В бытовом смысле это просто стопка, из которой можно брать и в которую можно класть только сверху.
Список предписаний структуры «Стек элементов типа E»:
1. Начать работу
2. Кончить работу
3. Сделать стек пустым
4. Стек пуст: да/нет
5. Добавить элемент <вх: E> в стек
6. Взять элемент из стека в <вых: E>
7. Вершина стека: E
8. Удалить вершину стека
Дек похож на стек, но операции положить/вытолкнуть можно производить не только сверху, но и снизу дека.
Dequeue
Список предписаний структуры «Дек элементов типа E»:
1. Начать работу
2. Сделать пустым
3. Пуст: да/нет
4. Добавить элемент в начало/конец дека <вх: E>
5. Взять элемент из начала/конца дека в <вых: E>
6. Начало/конец дека: E
7. Удалить начало/конец дека
8. Кончить работу
Список предписаний структуры «Множество элементов типа E»:
1. Начать работу
2. Сделать множество пустым
3. Множество пусто: да/нет
4. Добавить элемент <вх: E> в множество
5. Удалить элемент <вх: E> из множества
6. Элемент <вх: E> принадлежит множеству: да/нет
7. Взять какой-нибудь элемент множества в <вых: E>
8. Кончить работу
Список предписаний структуры «Последовательность элементов типа E»:
1. Начать работу
2. Сделать последовательность пустой
3. Последовательность пуста: да/нет
4. Добавить элемент <вх: E> в конец последовательности
5. Встать в начало последовательности
6. Есть/нет непрочитанные элементы
7. Прочесть очередной элемент последовательности в <вых: E>
8. Очередной элемент последовательности: E
9. Пропустить очередной элемент последовательности
10. Кончить работу
Список предписаний структуры «Л2-список элементов типа E»:
1. Начать работу
2. Сделать список пустым
3. Список пуст: да/нет
4. Установить указатель в начало/конец списка
5. Указатель в начале/конце списка: да/нет
6. Передвинуть указатель списка вперед/назад
7. Добавить элемент <вх: E> до указателя/за указателем списка
8. Взять элемент списка до указателя/за указателем в <вых: E>
9. Элемент списка до указателя/за указателем: E
10. Удалить элемент списка до указателя/за указателем
11. Кончить работу
Название списка «линейный двунаправленный» означает, что элементы списка упорядочены линейно, а указатель можно двигать вперед/назад.
В линейном однонаправленном списке элемены упорядочены тоже линейно, но указатель можно двигать только вперед:
Список предписаний структуры «Л1-список элементов типа E»:
1. Начать работу
2. Сделать список пустым
3. Список пуст: да/нет
4. Установить указатель в начало списка
5. Указатель в конце списка: да/нет
6. Передвинуть указатель списка вперед
7. Добавить элемент <вх: E> за указателем списка
8. Взять элемент списка за указателем в <вых: E>
9. Элемент списка за указателем: E
10. Удалить элемент списка за указателем
11. Кончить работу
Список предписаний структуры «Вектор элементов типа E с индексом типа И»:
1. Начать работу
2. Элемент вектора с индексом <вх: И>: E
3. Положить <вх: Е> в элемент вектора с индексом <вх: И>
4. Кончить работу
1. Реализация последовательности на базе двух очередей.
3 Прочитанные элементы — Левая Очередь
-1
<------------
20 Непрочитанные элементы — Правая Очередь - Голова
11
13
17
«Пропустить очередной элемент последовательности» =>
3 Прочитанные элементы — Левая Очередь
-1
20 Конец очереди
<------------
11 Непрочитанные элементы — Правая Очередь
13
17
50 - добавить
Где голова очереди, а где конец очереди?
1. Первый элемент — голова очереди +++++
2. Последний элемент — голова очереди
Последовательность будем хранить в левой (ЛО) и правой (ПО) очередях. Левая очередь будет соответствовать прочитанной части последовательности, а правая — непрочитанной.
Предписание Начать работу
ЛО. Начать работу
ПО. Начать работу
Конец предписания
Предписание Сделать последовательность пустой
ЛО.Сделать очередь пустой
ПО. Сделать очередь пустой
Конец предписания
Предписание Последовательность пуста: да/нет
Ответ := ЛО.пуста и ПО.пуста
Конец предписания
Предписание Добавить элемент <вх: E> в конец последовательности
ПО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Как встать в начало последовательности?
3 Прочитанные элементы — Левая Очередь
-1
20 Конец очереди
<------------
11 Непрочитанные элементы — Правая Очередь
13
17
============== Невозможно взять число из конца ЛО и невозможно добавить число в начало ПО!!!???
<------------ ЛО пуста
3 Непрочитанные элементы — Правая Очередь
-1
20
11
13
17
============= 1. Перекладываем все элементы из ПО в ЛО (прочитали последовательность до конца)
3 Прочитанные элементы — Левая Очередь
-1
20
11
13
17
<----------- ПО пуста
============= 2. Перекладываем все элементы из ЛО в ПО (порядок сохраняется)
<----------- ЛО пуста
3 Прочитанные элементы — Левая Очередь
-1
20
11
13
17
========================================
Предписание Встать в начало последовательности
// Перекладываем все элементы из правой очереди в левую
Цикл Пока ПО.Очередь не пуста выполнять
ПО.Взять элемент из начала очередь в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец цикла
Утверждение: ПО.Очередь пуста
// Перекладываем все элементы из левой очереди в правую
Цикл Пока ЛО.Очередь не пуста выполнять
ЛО.Взять элемент из начала очередь в <вых: E>
ПО.Добавить элемент <вх: E> в конец очереди
Конец цикла
Утверждение: ЛО.Очередь пуста
Конец предписания
Предписание Есть непрочитанные элементы
Ответ: ПО.очередь не пуста
Конец предписания
Предписание Прочесть очередной элемент в <вых: E>
ПО.Взять элемент из начала очереди в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Предписание Очередной элемент последовательности: E
Ответ := ПО.Начало очереди
Конец предписания
Предписание Пропустить очередной элемент последовательности: E
ПО.Взять элемент из начала очереди в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Предписание Кончить работу
ЛО.Кончить работу
ПО.Кончить работу
Конец предписания
2. Задачи на реализацию одних структур на базе других:
1) Реализовать стек на базе L1-списка
V
O → O → O → O → O → O
Стек — Где вершина стека?
-1. Хвост L1-списка => добавлять элемент в стек — просто (передвинуть указатель в конец списка и доб.эл-т за ук-лем); Взять элемент из стека — не получается, так как не можем найти последний элемент списка (не знаем, что он последний, когда он находится за указателем)
+2. Голова L1-списка => добавлять элемент в стек — Передвинуть ук-ль в начало + Добавить элемент за указателем; Взять элемент из стека — Передвинуть ук-ль в начало L1-списка + Взять элемент за указателем
V
O → O → O → O → O → O
2) Реализовать очередь на базе L1-списка
+1. Начало очереди — начало списка. Доб.в конец очереди == Доб.в конец списка (цикл пока ук.не в конце — передв.ук.вперед; доб.эл-т за ук.); Взять из начала очереди == Взять из начала списка (Ук.в начало, Взять эл-т за ук.)
-2. Начало очереди — конец списка
3) Дек на базе L2-списка
Реализация стека вещественных чисел на базе вектора, class RealStack (Борисенко В.В.):
Пример использования класса RealStack для разработки стекового калькулятора на языке C++ (Борисенко В.В.):
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988