Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
| Очередь с приоритетом – структура, реализованная при помощи очереди на основе контейнера, допускающего произвольный доступ к элементам (например, вектора или двусторонней очереди). Первым параметром при описании очереди с приоритетами является тип ключа, вторым последовательный контейнер, третьим – функция определения приоритета.
Поддерживает две обязательные операции: Добавить элемент Извлечь максимум (элемент с наибольшим приоритетом) Двусторонняя очередь (дек) – последовательный контейнер, поддерживающий доступ к произвольным элементам и обеспечивает вставку и удаление из обоих концов очереди за постоянное время. Операции с элементами внутри очереди занимают время, пропорциональное количеству перемещаемых элементов. Доступ к элементам очереди осуществляется за постоянное время (оно несколько больше, чем для вектора). Дек поддерживает следующие операции: Добавить элемент в начало дека Извлечь элемент из начала дека Добавить элемент в конец дека Извлечь элемент из конца дека Проверить, пуст ли дек Иерархическая структура данных – дерево (виды деревьев в том числе: деревья поиска, разбиение пространства, недвоичные деревья; способы представления; операции над деревьями). Дерево – это структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви. Каждое дерево обладает следующими свойствами: существует узел, в который не входит ни одной ветви (корень); в каждую вершину, кроме корня, входит одна ветвь Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Корень дерева не имеет предка, а листья дерева не имеют потомков. Высота (глубина) дерева определяется количеством уровней, на которых располагаются его вершины. Высота пустого дерева равна нулю, высота дерева из одного корня – единице. На нулевом уровне дерева может быть только одна вершина – корень дерева, на первом – потомки корня дерева, на втором – потомки потомков корня дерева и т.д. Степенью вершины в дереве называется количество ветвей (дуг), которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень ноль. По величине степени дерева различают два типа деревьев: двоичные – степень дерева не более двух; сильноветвящиеся – степень дерева более двух Списочное представление деревьев основано на понятии элемента, с помощью которого описываются соответствующие вершины дерева. Каждый элемент имеет поле данных и два поля указателей: указатель на начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня. Следует обратить внимание, что при таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева! жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|