Файл: Динамические структуры данных. Бинарные деревья.pdf

Отметим, также, что они характеризуются еще тем, что в них отсутствует физическая смежность элементов структуры в памяти, непостоянство и непредсказуемость размера структуры в процессе ее обработки.

Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента.

Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Рассмотрим достоинства и недостатки работы связного представления данных, которые представлены в таблице 1.1^[7].

Таблица 1.1. – Достоинства и недостатки работы связного представления данных

№	Связное представление данных
	Достоинства	Недостатки
1	Размер структуры ограничивается только доступным объемом машинной памяти	Доступ к элементам связной структуры может быть менее эффективным по времени
2	При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей	На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
3	Большая гибкость структуры

Анализируя таблицу 1.1, можно сделать вывод, что существуют минусы и плюсы при работе со связным представлением днных.

На наш взгляд, последний недостаток является наиболее серьезным и именно им ограничивается применимость связного представления данных.

Рассмотрим алгоритм работы с динамическими структурами данных^[8]:

1. Создать (отвести место в динамической памяти).
2. Работать при помощи указателя.
3. Удалить (освободить занятое структурой место).

Динамические структуры данных могут быть реализованы с помощью типа «указатель» и организованы линейно, в виде дерева и в виде сети. В данной курсовой работе мы более подробно рассмотрим второй вид.

Каждая динамическая структура характеризуется, во-первых, взаимосвязью элементов, и, во-вторых, набором типовых операций над этой структурой. В случае динамической структуры важно решить следующие вопросы:

---

- каким образом может расти и сокращаться данная структура;

- каким образом можно включить в структуру новый и удалить существующий элемент;

- как можно обратиться к конкретному элементу структуры для выполнения над ним определенной операции.

Из динамических структур в программах чаще всего используют линейные списки, их частные случае – стеки и очереди, а также бинарные деревья.

Таким образом, динамические структуры широко применяют для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Например, если в процессе выполнения программы требуется многократно упорядочивать большой массив данных, имеет смысл организовать его в виде динамической структуры.

Для того, чтобы более подробно изучить динамические структуры данных, рассмотрим их классификацию, которая представлена в следующем параграфе.

1.2 Классификация динамических структур данных

Все данные, которые используются в программировании, условно делятся на две большие группы, которые представлены на рисунке 3^[9].

Данные

Данные динамической структуры

Данные статистической структуры

Рисунок 3 – Виды данных

На рисунке 3 представлены два вида данных, которые используются в программировании.

Важно отметить, что взаимосвязь этих двух видов всегда остается постоянной. В данной работе мы более подробно рассмотрим данные динамической структуры.

Как уже было сказано в предыдущем параграфе работы, для того чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных. Рассмотрим подробней данные динамической структуры, которые представлены на рисунке 4^[10].

Рисунок 4 – Данные динамической структуры

---

Изучая рисунок 4, можно сделать вывод, что динамические структуры включают в себя файлы, а также несвязанные и связанные динамические данные.

Заметим, что файлы в данной классификации отнесены к динамическим структурам данных. Это происходит по той причине, что динамические структуры содержат файлы и данные. Отметим, что в данной структуре не допускается удаление и перемещение в середину элементов, и, не смотря на это, длина файла на протяжении всей работы может меняться.

Каждый элемент динамических структур данных состоит из собственно данных и одного или нескольких указателей, ссылающихся на аналогичные элементы.

Это позволяет добавлять в динамическую структуру новые данные или удалять какие-то из имеющихся, не затрагивая при этом другие элементы структуры^[11].

Кроме того, динамические структуры позволяют нам организовать данные так, чтобы их представление в программе было максимально приближено к тому, как эти данные выглядят в реальности. Так, для моделирования обслуживания очереди к кассе в магазине лучше всего подойдет динамическая структура данных под названием «очередь», а не пресловутый массив, а для представления сети автомобильных дорог массив вообще неприемлем. Здесь нужна именно «сеть»^[12].

Динамические структуры данных бывают двух видов, которые представлены на рисунке 5 данной курсовой работы.

Динамические структуры данных

Нелинейные

Линейные

Рисунок 5 – Виды динамических структур данных

Изучая рисунок 5, можно сделать вывод, что существует два вида динамических структур данных:

- линейные (списки, стеки, очереди);

- нелинейные.

К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами).

Линейная динамическая структура представляет собой изменяемую последовательность элементов. Частными случаями таких структур являются:

- стеки, в которых разрешено добавлять элементы только в конец и удалять только последние элементы;

- очереди, в которых добавление элементов осуществляется в конец, а удаление – из начала;

- деки, которые допускают добавление и удаление элементов и с начала, и с конца^[13].

Списком называют структуру, в которой помимо данных хранятся также адреса элементов. Элемент списка состоит из двух частей:

---

- информационной, которая содержит данные;

- адресной, в которой хранятся указатели на следующие элементы.

В зависимости от количества полей в адресной части и порядка связывания элементов различают несколько видов списков, которые представлены в таблице 1.2^[14]..

Таблица 1.2 – Списки элементов связывания

№	Название	Характеристика
	1	2
1	Линейные односвязные списки	Единственное адресное поле содержит адрес следующего элемента, если следующий элемент отсутствует, то в адресное поле заносят константу nil
2	Кольцевые односвязные списки	Единственное адресное поле содержит адрес следующего элемента, а последний элемент ссылается на первый
3	Линейные двусвязные списки	Каждый элемент содержит адреса предыдущего и последующих элементов, соответственно, первый элемент в качестве адреса предыдущего, а последний — в качестве адреса следующего элемента содержат nil
4	Кольцевые двусвязные списки	Каждый элемент содержит адреса предыдущего и последующих элементов, причем первый элемент в качестве предыдущего содержит адрес последнего элемента, а последний элемент в качестве следующего – адрес первого элемента
5	П-связные списки	Каждый элемент включает несколько адресных полей, в которых записаны адреса других элементов или nil

Организация нелинейных структур более сложная. 

Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).

Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят:

- однонаправленные (односвязные) списки;

- двунаправленные (двусвязные) списки;

- циклические списки;

- стек;

- дек;

- очередь;

- бинарные деревья.

Они отличаются способом связи отдельных элементов и/или допустимыми операциями.

Динамическая структура может занимать несмежные участки оперативной памяти.

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

---

Таким образом, мы рассмотрели классификацию динамических структур данных, которые широко применяются в тех случаях, когда необходимо увеличить объем памяти.

Подведем краткие итоги из данного параграфа курсовой работы:

- в программах возникает необходимость обрабатывать данные, размер которых заранее неизвестен;

- для данных с достаточно большим или переменным размером используются динамические структуры;

- динамические структуры не имеют имени, под них выделяется память в процессе выполнения программы, количество их элементов может не фиксироваться, в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры;

- каждой динамической структуре ставится в соответствие статическая переменная – ее адрес;

- представление динамических структур в памяти определяется как связное;

- связное представление данных в программах имеет как достоинства, так и недостатки;

- существует классификация динамических структур данных в зависимости от связей между элементами и допустимых операций;

- элемент динамической структуры состоит как минимум из двух полей: адресного и информационного;

- адресное поле формируется из двух слов: адрес сегмента и смещение;

- доступ к данным в динамических структурах осуществляется с помощью операции косвенного выбора.

Рассмотрим в следующем параграфе работы конкретно один из видов динамических структур данных, который носит название бинарные деревья, который относится к разветвленной структуре.

1.3 Структуры данных: бинарные деревья

В предыдущих параграфах курсовой работы мы определили что такое динамические структуры, описали их необходимость и структуру, а также выделили классификацию структур данных. В этой классификации были определены разветвленные структуры, к которым и относят деревья. Именно данный вид динамической структуры мы рассмотрим более конкретно в данном параграфе работы. Для начала дадим определение «дерево» и рассмотрим основные его характеристики.

Дерево – это структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов^[15].

Каждый элемент дерева называется вершиной или узлом дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. 

---