Сперва давайте разберемся, что это такое и с чем это следует кушать. Под динамической структурой данных понимается любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.

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

  • Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
  • Предок — элемент структуры, идущий до текущего.
  • Головной элемент (Head) — первый элемент списка.
  • Хвостовой элемент (Tail) — последний элемент списка.

Структура данных Список

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

  • Односвязный список — элемент имеет указатель только на своего потомка.
Односвязный список

Односвязный список

  • Двусвязный список — элемент имеет указатели и на потомка, и на родителя.
Двусвязный список

Двусвязный список

  • Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга.
Замкнутый список

Замкнутый список

На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).

Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.

Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.

Двусвязный список на языке C++

Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.

Элемент списка

Список

Структура данных Дерево

Дерево  — несколько более интересная структура. В отличие от списка, у одной записи может быть более одного потомка, но только один предок. Кроме того в дереве явно выделяется только головной элемент, называемый корнем (Root). Среди деревьев также существует разбиение на подтипы.

  • Бинарное дерево — у каждой вершины дерева может быть не более двух потомков.
Бинарное дерево

Бинарное дерево

  • Сильно разветвленное дерево — у вершины может быть n-ое число потомков.
Сильно разветвленное дерево

Сильно разветвленное дерево

В свою очередь для бинарных деревьев существует разбиение в зависимости от высоты поддеревьев, информационной части вершин и т.д. (АВЛ-деревья, красно-черные деревья, и др.).

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

Пути обхода дерева

Пути обхода дерева

Бинарное дерево поиска на языке C++

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

Бинарное дерево

Одним из интересных примеров сильно разветвленного дерева является так называемая TRIE-структура или БОР. Подобная структура данных можем быть очень
полезна при создании алгоритма наподобие Т9, потому как в каждой вершине бора содержится всего один символ алфавита или символ конца слова.

Префиксное дерево

При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.

Ну и на сладкое: рассмотрим пример интерактивного ввода дерева. По клику на мышку. Для этого незначительно расширим реализацию простого бинарного дерева. Единственное, что нам понадобится на форме — Image.

Если все сделано верно, на выходе мы получим нечто подобное:

Удачных вам экспериментов с динамическими структурами, коллеги.

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

Вконтакте
Telegram
Facebook
Twitter
Одноклассники
Дзен
Google+

 
×
%d такие блоггеры, как: