Разработка программного комплекса. Описание алгоритмов, используемых в программном комплексе

После анализа предметной области было решено использовать следующие языковые средства C++ для решения поставленной задачи:

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

2. Также нам потребуется возможность обходить все вершины, т.к. обход дерева придется осуществлять несколько раз, удобно будет вынести это действие в отдельную функцию и при необходимости вызывать ее в теле основной программы. По мере увеличения размера и сложности программного комплекса следует разделить его на небольшие легко управляемые части, называемые функциями. Каждая функция в вашей программе должна выполнять определенную задачу. Если программе необходимо выполнить определенную задачу, то она вызывает соответствующую функцию, обеспечивая эту функцию информацией, которая ей понадобится в процессе обработки.

3. Для обхода всех вершин дерева воспользуемся рекурсивной функцией. В языке С++ функция может вызывать сама себя. В этом случае такая функция называется рекурсивной. Рекурсия — это процесс определения чего-либо на основе самого себя, из-за чего рекурсию еще называют рекурсивным определением. Рекурсия необходима чтобы пройти по всем вершинам дерева. Так как для хранения дерева была выбрана структура, тогда для обхода дерева нам потребуется рекурсивная функция. Если бы реализация была основана на использовании массива, можно было бы осуществить обход графа через циклы. Но реализация обхода дерева, хранящегося в структурах будет неоправданно усложнена (а в случае не двоичного дерева, невозможна).

Осуществить поиск и удаление повторяющихся вершин двоичного дерева поиска удобно, используя две рекурсивные функции. Функция А будет в своем теле вызывать на исполнение функцию В, передовая ей значение вершины дерева, полученного при обходе в функции А. Далее, Функция В будет сначала (начиная с корня дерева), проверять все вершины дерева, сравнивая их с полученный из функции А значением. Если будет обнаружено более чем одно повторение значения вершины в графе, то все последующие повторяющиеся элементы, будут удалены.

Более подробная реализация алгоритма будет представлена в следующих разделах данной работы.