Курсовая работа (т): Реализация инструментария по работе с бинарными деревьями

2.3 Описание используемых методов и алгоритмов

Для построения дерева и реализации поиска узла используется алгоритм бинарного поиска.

Бинарный (двоичный, дихотомический) поиск - это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом, который является границей между частями множества или при отсутствии искомого элемента.

Бинарный поиск применяется к отсортированным множествам и заключается в последовательном разбиении множества пополам и поиска элемента только в одной половине на каждой итерации.

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

Алгоритм бинарного поиска:

.        Определить номер среднего элемента массив.

.        Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу.

.        Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности). Перейдем к шагу 1.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Двоичная куча, пирамида, или сортирующее дерево - такое двоичное дерево, для которого выполнены три условия:

·        значение в любой вершине не меньше, чем значения её потомков;

·        глубина листьев (расстояние до корня) отличается не более чем на 1 слой;

·        последний слой заполняется слева направо.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

2.4 Выбор графического и пользовательского интерфейса

Важной частью разработки программного продукта является определение графического и пользовательского интерфейса. От визуального восприятия интерфейса пользователем зависит удобство и скорость выполнения поставленных им задач. Продуманный интерфейс обеспечивает максимально слаженное взаимодействие пользователя с программой и повышает производительность труда пользователя. На рисунке 2.2 представлен пользовательский интерфейс.

К достоинствам этого варианта можно отнести:

·        наличие широкой области построения дерева;

·        компактное размещение элементов управления.

К недостаткам:

·        отсутствие полноэкранного режима;

Рис. 2.2 Пользовательский интерфейса

Данный интерфейс, несмотря на отсутствие некоторых дополнительных возможностей, полностью удовлетворяет всем поставленным требованиям.

3. ТЕХНОЛОГИЧЕСКИЙ РАЗДЕЛ

3.1 Определение структуры и состава программной системы

В состав программной системы входят классы, которые содержат конструкторы, поля данных и методы.

Класс Random

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

Конструктор:

Random() - инициализирует новый экземпляр класса System.Random с помощью зависимого от времени начального значения по умолчанию.

Поле данных:

Random r

Класс BinaryTreeNode

Класс представляет собой узел бинарного дерева.

Конструктор:

BinaryTreeNode(Data Item) - инициализирует новый объект класса BinaryTreeNode.

Поля данных:

·    public Data Item - поле для хранения информационного значения узла;

·        public BinaryTreeNode<Data> left - поле для хранения узла левого;

·        public BinaryTreeNode<Data> right - поле для хранения правого узла;

Класс BinaryTree

Класс реализует инструментарий по работе с бинарными деревьями.

Конструктор:() - конструктор пустого дерева;

BinaryTree(Data [] Records, int NRecords)- конструктор на основе массива;

Методы:

·        private void QuickSort(Data[] A, int low, int high) - метод быстрой сортировки;

·        void IBTInsert(Data[] A, int low, int high) - метод вставки, формирует идеально сбалансированное дерево;

·        public bool Insert(Data NewItem)- метод вставки узла;

·        private void VisualiseTree(Graphics G, BinaryTreeNode<Data> root,LevelH, int radius, int left, int right, int top, Color NodesColor,LeavesColor, Font NodesLabel) - метод визуализации поддерева;

·        private int LevelsAmount(BinaryTreeNode<Data> root) - метод определения количества уровней в поддерева с корнем root;

·        public void VisualiseTree(Graphics G, int radius, int width, int height,NodesColor, Color LeavesColor, Font NodesLabel) - основная функция визуализации дерева;

3.2 Руководство пользователя

Приложение «Демонстрация работы с бинарным деревом» предназначено для выполнения операций с бинарным деревом. В приложении реализованы методы создания и балансировки дерева, добавления и удаления. Приложение может быть применено в области образования для наглядного представления работы бинарного дерева поиска.

Установка программы на компьютер заключается в копировании папки программы и установки ярлыка на Рабочий стол. Создайте в любом разделе жесткого диска новую папку и скопируйте в нее все файлы папки "BinTree".

Запускать следует файл BinTree.exe непосредственно из папки или при помощи ярлыка кнопкой Enter или двойным щелчком мыши.

После запуска на экране монитора появится окно программы (рис. 3.2).

Рис. 3.2 Окно программы «Демонстрация работы с бинарным деревом»

Пользователю необходимо ввести количество узлов дерева в поле «Добавить элемент». В поле «Удалить элемент» появляется возможность выбора номера узла, для его удаления. Также массив можно инициализировать из файла, который будет загружен после нажатия на поле «Загрузить из файла». Также можно построить дерево по случайному набору, который выполнится после нажатия на поле «Построить по случайной коллекции». В области построения отобразится дерево, после нажатия на поле со случайным набором (рис. 3.3).

Рис. 3.3 Созданное дерево

Если нажать на кнопку «Добавить элемент», то на экран пользователю будет представлена возможность ввода значения нового узла, а если пользователь захотел удалить элемент, то это можно выполнить, осуществив нажатие на поле «удаление элемента», где пользователь указывает номер узла, который хотел бы удалить, но, если в дереве не присутствует такого узла, то будет выведена ошибка. (рис. 3.4).

Рис. 3.4 Сообщение об ошибке, связанной с отсутствием элемента в дереве

Теперь пользователь может выполнять операции с деревом.

Для добавления узла в дерево необходимо в поле после нажатия на кнопку «Добавить элемент», после чего нажать на кнопку. Добавленный узел появится в дереве (рис. 3.5).

Рис. 3.5 Дерево с действием добавление элемента

Если в дереве есть несколько элементов, соответствующих введенному значению, то на экран будет выведено сообщение об ошибке (рис. 3.6).

Рис. 3.6 Сообщение об ошибке, связанной с присутствием элемента в дереве

Для окончания работы необходимо нажать кнопку закрытия приложения, расположенную в правом верхнем углу окна программы.

4. ЭКСПЕРИМЕНТАЛЬНЫЙ РАЗДЕЛ

4.1 Виды контроля качества разрабатываемого ПО

Тестирование - это процесс выполнения программы с целью выявления ошибок.

Процесс разработки ПО предполагает три стадии тестирования:

·    автономное тестирование - это тестирование компонентов ПО;

·        комплексное тестирование;

·        системное (оценочное) тестирование - тестирование на соответствие основным критериям качества.

Принципы тестирования:

·    избегать тестирования программы самим автором;

·        предполагаемые результаты должны быть известны до тестирования;

·        необходимо изучать результаты каждого теста;

·        необходимо проверять действие программы на неверных данных;

Существует два принципиально различных подхода к формированию тестов:

·    структурный - известна структура тестируемого ПО, в том числе его алгоритмы. Тесты строят так, чтобы проверить правильность реализации заданной логики в ходе программы (белый ящик);

·        функциональный - структура ПО неизвестна. Тесты строят по функциональным спецификациям (черный ящик; подход, управляемый данными).

При проведении тестирования следует помнить, что никакое тестирование не может доказать отсутствие ошибок в ПО. Удачным считают тест, который обнаруживает хотя бы одну ошибку. Вероятность наличия необнаруженных ошибок пропорциональна количеству уже найденных ошибок в программе.

4.2 Методика проведения и результаты тестирования

Для обнаружения ошибок было произведено комплексное тестирование программного продукта. Процесс тестирования был осуществлен, следуя всем обозначенным принципам.

К формированию тестов был применен структурный подход. Последовательно были проверены все методы приложения. В ходе проверки ошибок обнаружено не было.

На следующем этапе тестирования программный продукт был проверен на устойчивость к неверным данным и ошибочным действиям пользователя. В результате было выявлено, что не все обработчики событий корректно реагируют на вызов, если он происходит не в предполагаемой последовательности. Так, при нажатии кнопки «Добавить элемент» до создания дерева происходила остановка приложения.

После выявления одной ошибки тесты были продолжены. Особое внимание было уделено остальным обработчикам событий, но больше ошибок выявлено не было.

4.3 Методы и способы устранения ошибок

Отладка - обнаружение, локализация и устранение ошибок в программе вычислительной машины

В C#, как и в других появившихся до .NET языков, главная методика по отладке состоит в добавлении точек останова и изучении того, что происходит в коде в конкретные моменты во время его выполнения.

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

Режим приостановки выполнения можно представить как пребывание программы в неком времени ожидания. В этом режиме все элементы, например функции, переменные и объекты, сохраняются в памяти, но их перемещения и активность приостанавливаются. Во время режима приостановки выполнения можно выполнить поиск ошибок и нарушений целостности данных, проверив положения элементов и их состояние. В режиме приостановки в программу можно вносить коррективы. Например, можно изменить значение переменной. Можно перемещать точку выполнения, изменяя оператор, который будет выполняться следующим при возобновлении выполнения программы. В C# в режиме приостановки выполнения можно даже изменять код с помощью эффективного средства "Изменить и продолжить".

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

Для обеспечения большей гибкости отладчик Visual Studio позволяет задавать следующие свойства, изменяющие поведение точки останова:

·        Параметр Число попаданий позволяет задать количество попаданий в точку останова перед тем, как отладчик прерывает выполнение программы. По умолчанию отладчик прерывает выполнение программы при попадании в точку останова. Можно сделать так, чтобы отладчик прерывал выполнение программы, если число попаданий равняется 2, 10, 512 или любому другому значению. Число попаданий - важное свойство, так как некоторые программные ошибки не обнаруживаются при первом выполнении программой цикла, вызове функции или доступе к переменной. Иногда ошибки могут не проявлять себя до сотен или даже тысяч итераций. Для выявления такой неполадки можно установить точку останова с числом проходов от 100 до 1 000.

·        Условие - это выражение, определяющее, захватывается ли точка останова, или пропускается. При достижении отладчиком точки останова выполняется оценка условия. Попадание в точку останова будет лишь в том случае, если условие выполняется. Условие можно использовать и для позиционной точки останова для остановки в определенном месте программы, но только в случае истинности определенного условия. Предположим, что необходимо выполнить отладку банковской программы, в которой баланс счета никогда не должен опускаться ниже нуля. Для этого следует установить точки останова в определенных местах кода и задать для каждой точки условие balance < 0. После запуска программы ее выполнение будет прервано в этих расположениях только в том случае, когда итог окажется меньше нуля. Можно проверить переменные и состояние программы в первой точке останова и затем продолжить выполнение до второй точки останова и т. д.

·        Действие указывает действие, которое должно происходить при попадании на точку останова. По умолчанию, отладчик приостанавливает выполнение, но можно вместо этого выбрать печать сообщения или запуск макроса Visual Studio. Если вместо приостановки выбрана печать сообщения, работа точки останова будет очень похожа на работу оператора Trace. Этот метод использования точек останова называется "точки трассировки".

·        Фильтр позволяет указать процесс или поток для точки останова.

ЗАКЛЮЧЕНИЕ

Целью курсового проекта являлось создание инструментария для работы с динамической структурой - бинарное дерево.

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