Линейные списки, стеки, очереди, бинарные деревья.
Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями.
Линейные списки. Самый простой способ связать множество элементов — сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных (ключи разных элементов списка могут совпадать).
| struct Node{ 1nt d; Node *next; Node *prev; }; |
Рассмотрим двунаправленный линейный список. Для формирования списка и работы с ним требуется иметь по крайней мере один указатель — на начало списка. Удобно завести еще один указатель — на конец списка. Допустим, что список состоит из целых чисел, то есть описание элемента списка выглядит следующим образом:
Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. При выборке элемент исключается из стека.
Функция помещения в стек по традиции называется push, а выборки — pop. Указатель для работы со стеком (top) всегда ссылается на его вершину.
Пример кода программы
| #1nclude <1ostream.h>struct Nocle{ 1nt d; Node *p; }; Node * firstdnt d); void pushCNode **top. int d); int pop(Node **top); |
Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. В программировании очереди применяются, например, при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.
Пример кода программы
| #include <iostream.h> struct Node{ 1nt d: Node *p: }: Node * firstdnt d): void addCNode **pend. int d): int del(Node **pbeg): |
Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. На рисунке 10.1 приведен пример бинарного дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы. Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно называется деревом поиска.
Рис. 10.1 Бинарное дерево
Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом. Действия с такими структурами изящнее всего описываются с помощью рекурсивных алгоритмом.
Подробное изложение теоретических вопросов, затронутых в десятой лекции, можно найти в литературе [1, 3].
Знания следует самостоятельно проверить путем ответов на контрольные вопросы.
Список рекомендуемой литературы
a) основная литература:
1. Т. А. Павловская. C/C++. Программирование на языке высокого уровня. - СПб.: Питер, 2003. - 461 с.
б) дополнительная литература:
2. Язык программирования Си для персонального компьютера/ С.О. Бочков, Д.М. Субботин. - 2005.
3. Бьёрн Страуструп Язык программирования C++/ - 2007. – 1104с.
в) прочая литература:
4. Степанов Е.О., Чириков С.В. Стиль программирования на C++. Учебное пособие. - СПб.: СПбГИТМО(ТУ), 2015. - 48 с.
5. Литвиненко Н. А. Технология программирования на С++ - БХВ-Петербург, 2005. – 281с.
Список контрольных вопросов:
1) Перечислите существующие виды моделей памяти.
2) Кратко охарактеризуйте каждую из них.
3) Какие данные называются статистическими?
4) Какие данные называются динамическими?
5) Дайте определение динамической памяти.
6) Перечислите функции, поддерживающие основные операции с динамической памятью.
7) Объясните, что такое линейные списки.
8) Объясните, что такое стеки.
9) Объясните, что такое очереди.
10) Объясните, что такое бинарные деревья.