Операция удаленияВыполняется в два действия:
Операция удаления вершины имеет три варианта решения, которые зависят от связи вершины с другими.
В этом случае удаление вершины заключается в удалении самой вершины и обнулении указателя на текущую вершину в родительской вершине.
Удаление вершины заключается в перенаправлении указателя на текущую вершину на вершину-потомок, а затем удаление самой вершины.
Существуют два правила удаления такой вершины: 1. Указатель на текущую вершину перенаправляется на вершину (корень) левого поддерева, а вершина (корень) правого поддерева присоединяется к самой правой вершине левого поддерева. 2. Указатель перенаправляется на корень правого поддерева, а корень левого поддерева присоединяется к самой левой вершине правого поддерева.
36.Структуры данных. Б – деревья. Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных. Структура данных является линейной, если для любого элемента структуры, кроме первого и последнего, имеется только один последующий и только один предыдущий элемент, и первый элемент имеет только один последующий, а последний – только один предыдущий. В противном случае структура нелинейная. Относятся к классу сильно ветвящихся деревьев. Дерево строится на основе следующего типового элемента, который является вершиной дерева:
Вершина дерева содержит n ключей и (n+1) указателей. Указатель p0 указывает на поддерево, содержащее ключи, меньше k1, pn указывает на ключи, большие kn, pi указывает на ключи, большие ki и меньшие ki+1. Ключи отсортированы в порядке возрастания: Свойства В – дерева. 1) В каждой вершине за исключением корня, имеют от n/2 до n-ключей. В корне от одного до n ключей. 2) Ключи расположены в порядке возрастания их значений. 3) Все листья дерева находятся на одном уровне. Для указанного дерева обычно рассматриваются операции выборки и добавления. Для выполнения этих операций выполняется поиск ключа в дереве. Алгоритм поиска: 1) Указатель на текущую вершину получает адрес корня дерева; 2) Если указатель пуст, то искомого значения нет, ошибка, и переход к пункту 5 3) Производится поиск требуемого значения вершин текущей вершины (применяется двоичный поиск). Если значение найдено, то поиск успешный и переходим к пункту 5. 4) Если ключа нет, то указателю на текущую вершину присваивается значение соответствующего указателя по значению ключа. Переход к п.2. 5) Конец Добавление вершины: 1) Поиск вершины с заданным ключом, если ключ обнаружен, то завершение с ошибкой. 2) Добавление заданного ключа в последнюю обрабатываемую вершину. Если число ключей в вершине равно n, то разбиение общего списка ключей на 2 подмножества и создается новый лист с вынесением среднего ключа в вершину-родитель. 3) Повторяется до нормальной вставки нового значения элемента. Б-деревья используются в тех случаях, когда невозможно заданное множество ключей расположить в оперативной памяти. Т.е. нет возможности работать со всем деревом сразу. Таким образом, часть дерева будет в оперативной памяти, а часть дерева будет во внешней памяти и вершины дерева будут вызываться в оперативную память по мере надобности. Вершины Б-дерева называются страницами и их размер соответствует минимальной или кратной единицы хранения данных на внешнем носителе. Ссылки на вершину представляют собой указатель на место вершины на внешнем носителе.
37. Документирование программ. Спецификация. В процессе разработки программных продуктов, необходимо создавать документы на проектирование и использования программных продуктов. Целью документирование на проектирование является указание требований к программному продукту, установления ограничений, согласование связей различных элементов программного продукта. В документах на использование программного продукта указывается инфа необходимая для качественного применения программного продукта и предоставляющая инфу о характеристиках и элементах связи. Основным элементом в документации на проектирование является спецификация. Основным элементом спецификации является типизация(строгая фиксация структуры объекта с указанием порядка размещения элементов и перечня возможных значения элемента.) Понятие типизации применимо к переменным и процедурам и функциям. Для выполнения работ по разработке программ составляют спецификации на структуры и процедуры и функции. Спецификация на структуры денных должна содержать: назначение, перечень элементов структуры с указанием их назначения, типа, возможных значений. Обычно при многоуровневых структурах данных описание приводиться от общего к частному. Спецификация на процедуру содержит заголовок, имена и назначения входных данных, дополнительную инфу. В доп.инфу. может включаться: требования к процедуре, Описание алгоритма, Указание на особенности реализации процедуры, Описание взаимодействия данной процедуры с другими. И т.п. Понятие типизации применяются как к данным, так и к процедурам. Типизация процедуры включает определение типов всех входных и выходных данных процедуры, и способов их передачи. К входным и выходным данной процедуры относят: данные передаваемые по средствам параметров, механизмы глобальных переменных, механизмы доступа к переменным и возврата значения через функцию.
|