{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"99d4a"},{"data":{"image":{"id":"5b06f6479d5cb39718a1aa77"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"2im5u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":30,"offset":73,"style":"BOLD"}],"text":"Сперва давайте разберемся, что это такое и с чем это следует кушать. Под динамической структурой данных понимается любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.","type":"unstyled","key":"atj9c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Существует несколько разновидностей динамических структур: список, дерево.\nПрежде чем переходить к описанию структур, следует запомнить несколько простых определений:","type":"unstyled","key":"1gfm2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"}],"text":"Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.","type":"unordered-list-item","key":"1n8jl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":0,"style":"BOLD"}],"text":"Предок — элемент структуры, идущий до текущего.","type":"unordered-list-item","key":"7hbbl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":16,"offset":0,"style":"BOLD"}],"text":"Головной элемент (Head) — первый элемент списка.","type":"unordered-list-item","key":"7on0s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":0,"style":"BOLD"}],"text":"Хвостовой элемент (Tail) — последний элемент списка.","type":"unordered-list-item","key":"61kuv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":23,"offset":0,"style":"BOLD"}],"text":"Структура данных Список","type":"header-two","key":"248fv"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":7,"offset":238}],"inlineStyleRanges":[{"length":6,"offset":0,"style":"BOLD"}],"text":"Список — это линейная динамическая структура данных, у каждого элемента может быть только один предок и только один потомок. По сути своей это очень похоже на обыкновенный массив, с той лишь разницей, что размер его не имеет ограничений. Списки также подразделяются на несколько типов.","type":"unstyled","key":"3bbjs"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":0,"style":"BOLD"}],"text":"Односвязный список — элемент имеет указатель только на своего потомка.","type":"unordered-list-item","key":"3uv72"},{"data":{"image":{"id":"5b06f6111aa80c0991a52b2e"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Односвязный список","type":"atomic:image","key":"3m4s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":0,"style":"BOLD"}],"text":"Двусвязный список — элемент имеет указатели и на потомка, и на родителя.","type":"unordered-list-item","key":"e07rv"},{"data":{"image":{"id":"5b06f6119d5cb39718a1aa75"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Двусвязный список","type":"atomic:image","key":"dkpof"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"3sc5j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":41,"offset":0,"style":"BOLD"}],"text":"Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга.","type":"unordered-list-item","key":"6n27b"},{"data":{"image":{"id":"5b06f61148267707260f4057"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Замкнутый список","type":"atomic:image","key":"authk"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":8,"offset":91},{"key":2,"length":5,"offset":109}],"inlineStyleRanges":[],"text":"На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).","type":"unstyled","key":"df8lg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"}],"text":"Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.","type":"unstyled","key":"47tqf"},{"data":{"image":{"id":"5b06f612d7bf21742bae29f7"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"apbik"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":0,"style":"BOLD"}],"text":"Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.","type":"unstyled","key":"89i5q"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Двусвязный список на языке C++","type":"header-three","key":"f3ej6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.","type":"unstyled","key":"e4v3t"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Элемент списка","type":"header-three","key":"c3kq7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"//

Структура: элемент списка..

\nstruct Node \n{\n float data; // Данные.\n Node *Next, *Prev; // Указатели на следующий и предыдущий элементы. \n};","type":"blockquote","key":"4u85n"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Список","type":"header-three","key":"19mtb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"//

Класс \"Список\".

\nclass List\n{\n Node *Head, *Tail; // Указатели на первый и последний элементы списка.\n\n public:\n\tList():Head(NULL),Tail(NULL){}; // Создание пустого списка (конструктор).\n\t~List(); // Деструктор.\t\n\n\tvoid Add(float data); // Добавление элемента в список.\n\tvoid Show(); // Отображение списка.\n};\n\n//

Деструктор.

\nList::~List()\n{\n while(Head) // До тех пор, пока головной элемент не равен NULL\n { \n Tail=Head->Next; // Переопределяем хвост\n delete Head;// Удаляем голову\n Head=Tail;// Определяем новую голову\n }\n}\n\n//

Добавление элемента в список..

\n// Информационное поле.\nvoid List::Add(float data)\n{\n Node *temp = new Node; // Создаем новый элемент.\n temp->Next = temp->Prev = NULL; // Обнуляем его указатель на следующий.\n temp->data = data; // Записываем данные.\n if (Head!=NULL) \n {\n\ttemp->Prev = Tail;\n\tTail->Next = temp;\n\tTail = temp;\n }\n else\n {\n\ttemp->Prev = NULL;\n\tHead=Tail=temp;\n }\n}\n\n//

Вывод всех элементов списка в Memo.

\nvoid List::Show() \n{\n Node *temp = Head;\n while(temp!=NULL) // Просматриваем весь список.\n {\n\tForm1->Memo2->Lines->Add(FloatToStr(temp->data)); \n\ttemp = temp->Next;\n }\n}","type":"blockquote","key":"d8p8a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":23,"offset":0,"style":"BOLD"}],"text":"Структура данных Дерево","type":"header-two","key":"agto0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"},{"length":4,"offset":220,"style":"BOLD"}],"text":"Дерево — несколько более интересная структура. В отличие от списка, у одной записи может быть более одного потомка, но только один предок. Кроме того в дереве явно выделяется только головной элемент, называемый корнем (Root). Среди деревьев также существует разбиение на подтипы.","type":"unstyled","key":"3rofh"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":0,"style":"BOLD"}],"text":"Бинарное дерево — у каждой вершины дерева может быть не более двух потомков.","type":"unordered-list-item","key":"700ks"},{"data":{"image":{"id":"5b06f61248267707260f4058"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Бинарное дерево","type":"atomic:image","key":"frk7e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"}],"text":"Сильно разветвленное дерево — у вершины может быть n-ое число потомков.","type":"unordered-list-item","key":"7sl9k"},{"data":{"image":{"id":"5b06f6121410c3b18bef375b"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Сильно разветвленное дерево","type":"atomic:image","key":"dgq2k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В свою очередь для бинарных деревьев существует разбиение в зависимости от высоты поддеревьев, информационной части вершин и т.д. (АВЛ-деревья, красно-черные деревья, и др.).","type":"unstyled","key":"9jh8o"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В отличие от списка при обходе дерева может быть применено насколько различных путей:","type":"unstyled","key":"e8rr2"},{"data":{"image":{"id":"5b06f613d7bf21742bae29f8"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Пути обхода дерева","type":"atomic:image","key":"31dv6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Бинарное дерево поиска на языке C++","type":"header-three","key":"bitus"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рассмотрим реализацию простейшего бинарного дерева поиска. В данном примере используется поперечный обход дерева.","type":"unstyled","key":"5hvbs"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Бинарное дерево","type":"header-three","key":"3o7n1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"//

Структура: \"Вершина дерева\"

\nstruct TreeNode\n{\n\tint info; // Информация в вершине.\n\tint number; // Номер вершины.\n\tTreeNode *left; // Левая дочерняя вершина.\n\tTreeNode *right; // Правая дочерняя вершина.\n\tTreeNode *parent; // Родительская вершина дерева.\n};\n\n//

Класс \"Дерево\".

\nclass Tree \n{\n public: TreeNode *Root; // Корень дерева.\t\t \n\t Tree():Root(NULL),Count(0),LastNum(1),Radius(10){}; // Конструктор \n\t ~Tree();\n\t void RemoveSubtree(TreeNode *subRoot); // Удаление поддерева,\n\t void Add(int info, TreeNode *current, TreeNode *parent); // Добавление \n\t void AddNode(int info); // Добавление вершины.\n void Simmetrical(TreeNode *node); // Поперечный (симметричный) обход.\n};\n\n//

Деструктор.

\nTree::~Tree()\n{\n RemoveSubtree(Root);\n}\n\n//

Удалить поддерево.

\n// Корень удаляемого дерева.\nvoid Tree::RemoveSubtree(TreeNode *subRoot)\n{\n if(subRoot != NULL) \n {\n\tRemoveSubtree(subRoot->left); // Удаляем левую часть дерева.\n\tRemoveSubtree(subRoot->right); // Удаляем правую часть дерева.\n\n\tdelete subRoot;\n }\n}\n\n//

Добавить узел

\n// Информационное поле\nvoid Tree::AddNode(int info)\n{\n if(Root == NULL) \n {\n\tRoot = new TreeNode; \n\tRoot->info = info;\n\tRoot->left = Root->right = Root->parent = NULL;\t\t\n\tCount = 1;\n }\n else\n {\n\tif(Root->info > info)\n\t{\n\t Add(info, Root->left, Root);\n\t}\n\telse\n\t{\n\t Add(info, Root->right, Root);\n\t}\n }\n}\n\n//

Добавить узел

\n// Информационное поле\n// Текущая вершина\n// Родительская вершина\nvoid Tree::Add(int info, TreeNode *current, TreeNode *parent)\n{\n if(current == NULL)\n {\n\tTreeNode *temp = new TreeNode; \n\ttemp->info = info;\n\ttemp->left = temp->right = NULL;\n\ttemp->parent = parent;\n\tif(parent->info > temp->info)\n\t{\n\t parent->left = temp; \n\t}\n\telse\n\t{\n\t parent->right = temp;\n\t}\n\n\t Count++;\n }\n else\n {\n\tif(current->info > info)\n\t{\n\t Add(info, current->left, current);\n\t}\n\telse\n\t{\n\t Add(info, current->right, current);\n\t}\n }\n}\n\n//

Симметричный обход.

\n// Текущая вершина.\nvoid Tree::Simmetrical(TreeNode *node)\n{\n if(node == NULL)\n {\n\treturn;\n }\n else\n {\n\tSimmetricalNumbering(node->left); \t\t\t\n\tSimmetricalNumbering(node->right);\n }\n}","type":"blockquote","key":"c1d5d"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":82,"style":"BOLD"},{"length":3,"offset":101,"style":"BOLD"}],"text":"Одним из интересных примеров сильно разветвленного дерева является так называемая TRIE-структура или БОР. Подобная структура данных можем быть очень\nполезна при создании алгоритма наподобие Т9, потому как в каждой вершине бора содержится всего один символ алфавита или символ конца слова.","type":"unstyled","key":"9318h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Префиксное дерево","type":"header-three","key":"27mud"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"//

Структура: элемент бора.

\nstruct Node\n{\n char Sym;\n Node** Children; // Массив дочерних символов\n int ChildrenCount;\n};\n\n//

Проверка на наличие элемента среди потомков.

\n// Список потомков. \n// Длина списка. \n// Искомый символ. \n// false: символ уже есть в списке; true - символ нужно добавить\nbool CheckChild(Node **children, int count, char sym)\n{\n for(int i = 0; i < count; i++)\n {\n\tif(children[i]->Sym == sym)\n\t{\n\t return false;\n\t}\n }\n\n return true;\n}\n\n//

Добавить дочерний элемент.

\n// Добавляемый символ. \n// Вершина, в которую проводится попытка добавления. \n// Добавленный потомок. \nNode* AddChild(char sym, Node *node)\n{\n if(node->ChildrenCount == 0) // Если дочерних записей нет\n {\n\tnode->Children = new Node*[1];\n\tnode->Children[0] = new Node;\n\tnode->Children[0]->Sym = sym;\n\tnode->Children[0]->Children = NULL;\n\tnode->Children[0]->ChildrenCount = 0;\n\tnode->ChildrenCount = 1;\n\n\treturn node->Children[0];\n }\n else\n {\n\tif(CheckChild(node->Children, node->ChildrenCount, sym))\n\t{\n\t Node **tempChildren = new Node*[node->ChildrenCount + 1]; \n\n\t for(int i = 0; i < node->ChildrenCount; i++)\n\t {\n\t\ttempChildren[i] = node->Children[i];\n\t }\n\n\t delete[] node->Children;\n\n\t tempChildren[node->ChildrenCount] = new Node;\n\t tempChildren[node->ChildrenCount]->Sym = sym;\n\t tempChildren[node->ChildrenCount]->Children = NULL;\n\t tempChildren[node->ChildrenCount]->ChildrenCount = 0;\n\n\t node->Children = tempChildren;\n\t node->ChildrenCount++;\n\n\t return tempChildren[node->ChildrenCount - 1];\n\t}\n\telse\n\t{\n\t for(int i = 0; i < node->ChildrenCount; i++)\n\t {\n\t\tif(node->Children[i]->Sym == sym)\n\t\t{\n\t return node->Children[i]; \n\t\t}\n\t }\n\t}\n }\n\n return node;\n}\n\n//

Подсчитать количество слов в Боре.

\n// Текущая вершина.\n// Количество слов. \nint CountWords(Node *node)\n{\n int count = 0;\n\n if(node->Sym =='$') \n {\n\treturn 1;\n }\n else\n {\n\tfor(int i = 0; i < node->ChildrenCount; i++) \n\t{\n\t count += CountWords(node->Children[i]);\n\t}\n }\n\n return count;\n}","type":"blockquote","key":"9n0mn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.","type":"unstyled","key":"djp7c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" Удачных вам экспериментов с динамическими структурами, коллеги. ","type":"unstyled","key":"c45dn"},{"data":{},"depth":0,"entityRanges":[{"key":3,"length":29,"offset":10}],"inlineStyleRanges":[],"text":"Источник: Динамические структуры данных","type":"unstyled","key":"dkqeu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"P2JjNEMbBIp8KjP21y7O"}],"entityMap":{"0":{"data":{"url":"https://zen.yandex.ru/media/codeblog/sviaznyi-spisok-linked-list-na-iazyke-c-5abb5b72e44a9479f81e72a8"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"url":"https://zen.yandex.ru/media/codeblog/ochered-queue-na-iazyke-c-5ab363ef2f578cd2f914d83e"},"mutability":"MUTABLE","type":"LINK"},"2":{"data":{"url":"https://zen.yandex.ru/media/codeblog/stek-stack-na-iazyke-c-5ab21256f031733f2a62f026"},"mutability":"MUTABLE","type":"LINK"},"3":{"data":{"url":"https://shwanoff.ru/dynamic-structures-cpp/"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}