Сперва давайте разберемся, что это такое и с чем это следует кушать. Динамические структуры данных — это любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.
Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!
Существует несколько разновидностей динамических структур: список, дерево.
Прежде чем переходить к описанию структур, следует запомнить несколько простых определений:
- Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
- Предок — элемент структуры, идущий до текущего.
- Головной элемент (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 ==' При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.
Ну и на сладкое: рассмотрим пример интерактивного ввода дерева. По клику на мышку. Для этого незначительно расширим реализацию простого бинарного дерева. Единственное, что нам понадобится на форме — Image.
// <summary> Структура: вершина дерева.</summary>
struct TreeNode
{
int info; // Информация в вершине.
int number; // Номер вершины.
int X; // Координата Х.
int Y; // Координата Y.
TreeNode *left; // Левая дочерняя вершина.
TreeNode *right; // Правая дочерняя вершина.
TreeNode *parent; // Родительская вершина дерева.
};
// <summary> Класс "Дерево".</summary>
class Tree
{
public: TreeNode *Root; // Корень дерева.
int Radius; // Радиус вершины.
Tree():Root(NULL),Count(0),Radius(10){}; // Конструктор
~Tree();
void RemoveSubtree(TreeNode *subRoot); // Удаление поддерева.
void Add(int info, TreeNode *current, TreeNode *parent, int x, int y); // Добавление
void AddNode(int info, int x, int y); // Добавление корня.
};
// <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 = node> Текущая вершина.</params>
void DrawSceleton(TreeNode *node)
{
if(node == NULL)
{
return;
}
Form1->Image1->Canvas->MoveTo(node->X, node->Y);
if(node->parent != NULL)
{
Form1->Image1->Canvas->LineTo(node->parent->X, node->parent->Y);
}
DrawSceleton(node->left);
DrawSceleton(node->right);
}
//<summary> Отрисовка вершин. </summary>
//<params name = node> Текущая вершина.</params>
void DrawCirles(TreeNode *node)
{
if(node == NULL)
{
return;
}
Form1->Image1->Canvas->Brush->Color = clGreen;
Form1->Image1->Canvas->Ellipse(node->X - tree.Radius, node->Y - tree.Radius,
node->X + tree.Radius, node->Y + tree.Radius);
Form1->Image1->Canvas->Brush->Style = bsClear;
Form1->Image1->Canvas->TextOutW(node->X - tree.Radius / 2,
node->Y - tree.Radius / 1.5, node->info);
DrawCirles(node->left);
DrawCirles(node->right);
}
//<summary> Установить текущую вершину по координатам</summary>
//<params name = x> Координата х</params>
//<params name = y> Координата у</params>
//<params name = node> Рассматриваемая вершина</params>
void GetNodeByCoords(int x, int y, TreeNode *node)
{
if(node == NULL)
{
return;
}
if((node->X - tree.Radius) <= x && (node->X + tree.Radius) >= x &&
(node->Y - tree.Radius) <= y && (node->Y + tree.Radius) >= y)
{
Current = node;
Form1->Image1->Canvas->Brush->Color = clRed;
Form1->Image1->Canvas->Ellipse(node->X - tree.Radius, node->Y - tree.Radius,
node->X + tree.Radius, node->Y + tree.Radius);
return;
}
GetNodeByCoords(x, y, node->left);
GetNodeByCoords(x, y, node->right);
}
//Дерево
Tree tree;
//Флаг на перерисовку при передвижении
bool reDraw = false;
// Выбранная вершина
TreeNode *Current;
//<summary> Отрисовка дерева.</summary>
void DrawTree()
{
Form1->Image1->Canvas->Brush->Color = clWhite;
Form1->Image1->Canvas->FillRect(Form1->Image1->ClientRect);
Form1->Image1->Canvas->Brush->Color = clBlack;
DrawSceleton(tree.Root);
Form1->Image1->Canvas->Brush->Color = clGreen;
DrawCirles(tree.Root);
}
//<summary> Обработка зажатия левой кнопки мыши.</summary>
void __fastcall TForm1::Image1MouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift,
int X, int Y)
{
Image1->Canvas->Brush->Color = clGreen;
if(Current != NULL)
{
Image1->Canvas->Ellipse(Current->X - tree.Radius, Current->Y - tree.Radius,
Current->X + tree.Radius, Current->Y + tree.Radius);
}
Current = NULL;
GetNodeByCoords(X, Y, tree.Root);
if(Current == NULL)
{
int info = StrToInt(InputBox("Введите информационного поля", "Введите число", "0"));
tree.AddNode(info, X, Y);
Form1->Image1->Canvas->Brush->Color = clWhite;
Form1->Image1->Canvas->FillRect(Form1->Image1->ClientRect);
Form1->Image1->Canvas->Brush->Color = clBlack;
DrawSceleton(tree.Root);
Form1->Image1->Canvas->Brush->Color = clGreen;
DrawCirles(tree.Root);
}
reDraw = true;
}
//---------------------------------------------------------------------------
//<summary> Обработка поднятия кнопки мыши.</summary>
void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift,
int X, int Y)
{
reDraw = false;
}
//---------------------------------------------------------------------------
//<summary> Обработка движения мыши по канве.</summary>
void __fastcall TForm1::Image1MouseMove(TObject *Sender, TShiftState Shift, int X,
int Y)
{
if(Current != NULL && reDraw)
{
Current->X = X;
Current->Y = Y;
Form1->Image1->Canvas->Brush->Color = clWhite;
Form1->Image1->Canvas->FillRect(Form1->Image1->ClientRect);
Form1->Image1->Canvas->Brush->Color = clBlack;
DrawSceleton(tree.Root);
Form1->Image1->Canvas->Brush->Color = clGreen;
DrawCirles(tree.Root);
}
}
Динамические структуры данных С++. Заключение
Удачных вам экспериментов с динамическими структурами, коллеги.
Кроме того, рекомендую прочитать статью Set C# | Структура данных Множество C#. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.
