Сперва давайте разберемся, что это такое и с чем это следует кушать. Под динамической структурой данных понимается любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.
Существует несколько разновидностей динамических структур: список, дерево.
Прежде чем переходить к описанию структур, следует запомнить несколько простых определений:
- Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
- Предок — элемент структуры, идущий до текущего.
- Головной элемент (Head) — первый элемент списка.
- Хвостовой элемент (Tail) — последний элемент списка.
Структура данных Список
Список — это линейная динамическая структура данных, у каждого элемента может быть только один предок и только один потомок. По сути своей это очень похоже на обыкновенный массив, с той лишь разницей, что размер его не имеет ограничений. Списки также подразделяются на несколько типов.
- Односвязный список — элемент имеет указатель только на своего потомка.
- Двусвязный список — элемент имеет указатели и на потомка, и на родителя.
- Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга.
На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).
Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.
Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.
Двусвязный список на языке C++
Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.
Элемент списка
// <summary> Структура: элемент списка..</summary>
struct Node
{
float data; // Данные.
Node *Next, *Prev; // Указатели на следующий и предыдущий элементы.
};
Список
// <summary> Класс "Список".</summary>
class List
{
Node *Head, *Tail; // Указатели на первый и последний элементы списка.
public:
List():Head(NULL),Tail(NULL){}; // Создание пустого списка (конструктор).
~List(); // Деструктор.
void Add(float data); // Добавление элемента в список.
void Show(); // Отображение списка.
};
// <summary> Деструктор.</summary>
List::~List()
{
while(Head) // До тех пор, пока головной элемент не равен NULL
{
Tail=Head->Next; // Переопределяем хвост
delete Head;// Удаляем голову
Head=Tail;// Определяем новую голову
}
}
// <summary> Добавление элемента в список..</summary>
// <params name = data> Информационное поле.</params>
void List::Add(float data)
{
Node *temp = new Node; // Создаем новый элемент.
temp->Next = temp->Prev = NULL; // Обнуляем его указатель на следующий.
temp->data = data; // Записываем данные.
if (Head!=NULL)
{
temp->Prev = Tail;
Tail->Next = temp;
Tail = temp;
}
else
{
temp->Prev = NULL;
Head=Tail=temp;
}
}
// <summary> Вывод всех элементов списка в Memo.</summary>
void List::Show()
{
Node *temp = Head;
while(temp!=NULL) // Просматриваем весь список.
{
Form1->Memo2->Lines->Add(FloatToStr(temp->data));
temp = temp->Next;
}
}
Структура данных Дерево
Дерево — несколько более интересная структура. В отличие от списка, у одной записи может быть более одного потомка, но только один предок. Кроме того в дереве явно выделяется только головной элемент, называемый корнем (Root). Среди деревьев также существует разбиение на подтипы.
- Бинарное дерево — у каждой вершины дерева может быть не более двух потомков.
- Сильно разветвленное дерево — у вершины может быть n-ое число потомков.
В свою очередь для бинарных деревьев существует разбиение в зависимости от высоты поддеревьев, информационной части вершин и т.д. (АВЛ-деревья, красно-черные деревья, и др.).
В отличие от списка при обходе дерева может быть применено насколько различных путей:
Бинарное дерево поиска на языке C++
Рассмотрим реализацию простейшего бинарного дерева поиска. В данном примере используется поперечный обход дерева.
Бинарное дерево
// <summary> Структура: "Вершина дерева"</summary>
struct TreeNode
{
int info; // Информация в вершине.
int number; // Номер вершины.
TreeNode *left; // Левая дочерняя вершина.
TreeNode *right; // Правая дочерняя вершина.
TreeNode *parent; // Родительская вершина дерева.
};
// <summary> Класс "Дерево".</summary>
class Tree
{
public: TreeNode *Root; // Корень дерева.
Tree():Root(NULL),Count(0),LastNum(1),Radius(10){}; // Конструктор
~Tree();
void RemoveSubtree(TreeNode *subRoot); // Удаление поддерева,
void Add(int info, TreeNode *current, TreeNode *parent); // Добавление
void AddNode(int info); // Добавление вершины.
void Simmetrical(TreeNode *node); // Поперечный (симметричный) обход.
};
// <summary> Деструктор.</summary>
Tree::~Tree()
{
RemoveSubtree(Root);
}
// <summary> Удалить поддерево.</summary>
// <params name = subRoot> Корень удаляемого дерева.</params>
void Tree::RemoveSubtree(TreeNode *subRoot)
{
if(subRoot != NULL)
{
RemoveSubtree(subRoot->left); // Удаляем левую часть дерева.
RemoveSubtree(subRoot->right); // Удаляем правую часть дерева.
delete subRoot;
}
}
// <summary> Добавить узел</summary>
// <params name = info> Информационное поле</params>
void Tree::AddNode(int info)
{
if(Root == NULL)
{
Root = new TreeNode;
Root->info = info;
Root->left = Root->right = Root->parent = NULL;
Count = 1;
}
else
{
if(Root->info > info)
{
Add(info, Root->left, Root);
}
else
{
Add(info, Root->right, Root);
}
}
}
// <summary> Добавить узел</summary>
// <params name = info> Информационное поле</params>
// <params name = current> Текущая вершина</params>
// <params name = parent> Родительская вершина</params>
void Tree::Add(int info, TreeNode *current, TreeNode *parent)
{
if(current == NULL)
{
TreeNode *temp = new TreeNode;
temp->info = info;
temp->left = temp->right = NULL;
temp->parent = parent;
if(parent->info > temp->info)
{
parent->left = temp;
}
else
{
parent->right = temp;
}
Count++;
}
else
{
if(current->info > info)
{
Add(info, current->left, current);
}
else
{
Add(info, current->right, current);
}
}
}
// <summary> Симметричный обход.</summary>
// <params name = node> Текущая вершина.</params>
void Tree::Simmetrical(TreeNode *node)
{
if(node == NULL)
{
return;
}
else
{
SimmetricalNumbering(node->left);
SimmetricalNumbering(node->right);
}
}
Одним из интересных примеров сильно разветвленного дерева является так называемая TRIE-структура или БОР. Подобная структура данных можем быть очень
полезна при создании алгоритма наподобие Т9, потому как в каждой вершине бора содержится всего один символ алфавита или символ конца слова.
Префиксное дерево
// <summary> Структура: элемент бора.</summary>
struct Node
{
char Sym;
Node** Children; // Массив дочерних символов
int ChildrenCount;
};
// <summary> Проверка на наличие элемента среди потомков.</summary>
// <params name = children> Список потомков. </params>
// <params name = count> Длина списка. </params>
// <params name = sym> Искомый символ. </params>
// <result> false: символ уже есть в списке; true - символ нужно добавить</result>
bool CheckChild(Node **children, int count, char sym)
{
for(int i = 0; i < count; i++)
{
if(children[i]->Sym == sym)
{
return false;
}
}
return true;
}
// <summary> Добавить дочерний элемент.</summary>
// <params name = sym> Добавляемый символ. </params>
// <params name = node> Вершина, в которую проводится попытка добавления. </params>
// <result> Добавленный потомок. </result>
Node* AddChild(char sym, Node *node)
{
if(node->ChildrenCount == 0) // Если дочерних записей нет
{
node->Children = new Node*[1];
node->Children[0] = new Node;
node->Children[0]->Sym = sym;
node->Children[0]->Children = NULL;
node->Children[0]->ChildrenCount = 0;
node->ChildrenCount = 1;
return node->Children[0];
}
else
{
if(CheckChild(node->Children, node->ChildrenCount, sym))
{
Node **tempChildren = new Node*[node->ChildrenCount + 1];
for(int i = 0; i < node->ChildrenCount; i++)
{
tempChildren[i] = node->Children[i];
}
delete[] node->Children;
tempChildren[node->ChildrenCount] = new Node;
tempChildren[node->ChildrenCount]->Sym = sym;
tempChildren[node->ChildrenCount]->Children = NULL;
tempChildren[node->ChildrenCount]->ChildrenCount = 0;
node->Children = tempChildren;
node->ChildrenCount++;
return tempChildren[node->ChildrenCount - 1];
}
else
{
for(int i = 0; i < node->ChildrenCount; i++)
{
if(node->Children[i]->Sym == sym)
{
return node->Children[i];
}
}
}
}
return node;
}
// <summary> Подсчитать количество слов в Боре.</summary>
// <params name = node> Текущая вершина.</params>
// <result> Количество слов. </result>
int CountWords(Node *node)
{
int count = 0;
if(node->Sym =='$')
{
return 1;
}
else
{
for(int i = 0; i < node->ChildrenCount; i++)
{
count += CountWords(node->Children[i]);
}
}
return count;
}
При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.
Удачных вам экспериментов с динамическими структурами, коллеги.
Источник: Динамические структуры данных
