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

Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на 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-канал. Там еще больше полезного и интересного для программистов.