Как называл свою книгу Н.Вирт, «Алгоритмы + структуры данных = программы».
Наиболее популярные структуры данных: массив, очередь, стек, дек, список, дерево, граф.
Стек — это структура данных, организованная по принципу «первый пришел, первый ушел», по английски First In First Out, сокращенно FIFO. В бытовом смысле это обычная очередь.
Список предписаний структуры «Очередь элементов типа 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. Удалить вершину стека
Дек похож на стек, но операции положить/вытолкнуть можно производить не только сверху, но и снизу дека.
Список предписаний структуры «Дек элементов типа 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. Кончить работу
1. Реализация последовательности на базе двух очередей.
Последовательность будем хранить в левой (ЛО) и правой (ПО) очередях. Левая часть будет соответствовать прочитанной части последовательности, а правая — непрочитанной.
Предписание Начать работу
ЛО. Начать работу
ПО. Начать работу
Конец предписания
Предписание Сделать последовательность пустой
ЛО.Сделать очередь пустой
ПО. Сделать очередь пустой
Конец предписания
Предписание Последовательность пуста: да/нет
Ответ := ЛО.пуста и ПО.пуста
Конец предписания
Предписание Добавить элемент <вх: E> в конец последовательности
ПО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Предписание Встать в начало последовательности
// Перекладываем все элементы из правой очереди в левую
Цикл Пока ПО.Очередь не пуста выполнять
ПО.Взять элемент из начала очередь в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец цикла
Утверждение: ПО.Очередь пуста
// Перекладываем все элементы из левой очереди в правую
Цикл Пока ЛО.Очередь не пуста выполнять
ЛО.Взять элемент из начала очередь в <вых: E>
ПО.Добавить элемент <вх: E> в конец очереди
Конец цикла
Утверждение: ЛО.Очередь пуста
Конец предписания
Предписание Есть непрочитанные элементы
Ответ: ПО.очередь не пуста
Конец предписания
Предписание Прочесть очередной элемент в <вых: E>
ПО.Взять элемент из начала очереди в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Предписание Очередной элемент последовательности: E
Ответ := ПО.Начало очереди
Конец предписания
Предписание Пропустить очередной элемент последовательности: E
ПО.Взять элемент из начала очереди в <вых: E>
ЛО.Добавить элемент <вх: E> в конец очереди
Конец предписания
Предписание Кончить работу
ЛО.Кончить работу
ПО.Кончить работу
Конец предписания
2. Задачи на реализацию одних структур на базе других:
1) Реализовать стек на базе L1-списка
2) Реализовать очередь на базе L1-списка
3) Дек на базе L2-списка
Реализация стека вещественных чисел на базе вектора, class RealStack (Борисенко В.В.):
Пример использования класса RealStack для разработки стекового калькулятора на языке C++ (Борисенко В.В.):
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988