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

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

  • Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
  • Предок — элемент структуры, идущий до текущего.
  • Головной элемент (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», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.

Ну и на сладкое: рассмотрим пример интерактивного ввода дерева. По клику на мышку. Для этого незначительно расширим реализацию простого бинарного дерева. Единственное, что нам понадобится на форме — 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);
    }
}

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

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

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

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

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