Обоснование выбора языка и среды программирования. Обзор и анализ существующих программных решений. Разработка графического и пользовательского интерфейса. Алгоритм бинарного поиска. Методы добавления, удаления элемента из дерева и вывода на экран.
Аннотация к работе
Терминология, применяемая для описания бинарных деревьев: · узел - это точка, где может возникнуть ветвь; · ветвь - отрезок, описывающий связь между двумя узлами; · родительским - называется узел, который находится непосредственно над другим узлом; · дочерним - называется узел, который находится непосредственно под другим узлом; · длина пути к узлу - количество ветвей, которые нужно пройти, чтобы дойди от корня к данному узлу;Тема бинарных деревьев популярна для исследований, поэтому существует большое количество программных решений, реализующих структуры бинарных деревьев и алгоритмы бинарного поиска. На данном этапе работы был проведен обзор и анализ программ, реализующих работу с бинарными деревьями, с целью определить набор функциональных требований к разрабатываемому программному продукту. Первым примером для анализа стала работа Андрея Амельченя «Бинарное дерево поиска на C#» (рис. Автор решил продемонстрировать работу с бинарным деревом поиска. 1.2) - это особое двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска): · оба поддерева - левое и правое - являются двоичными деревьями поиска;Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку (в том числе операторов явного и неявного приведения типа), атрибуты, события, свойства, обобщенные типы и методы, исключения, комментарии в формате XML. Функция инициализации дерева выделяет память подо все узлы дерева и заполняет их информационное поле значениями, пришедшими из функции генерации случайных чисел. Функция добавления узла получает значение добавляемого узла из функции получения данных от пользователя и передает его в функцию инициализации дерева, где оно записывается в массив и учитывается при выделении памяти под узлы дерева. Функция удаления узла получает значение удаляемого узла из функции получения данных от пользователя и передает его в функцию инициализации дерева. Если переданное значение совпадает со значением элемента массива, то элемент удаляется из массива и исключается из расчета при выделении памяти под узлы дерева.В состав программной системы входят классы, которые содержат конструкторы, поля данных и методы. Конструктор: Random() - инициализирует новый экземпляр класса System.Random с помощью зависимого от времени начального значения по умолчанию. Класс реализует инструментарий по работе с бинарными деревьями. · public void VISUALISETREE(Graphics G, int radius, int width, int height, Color NODESCOLOR, Color LEAVESCOLOR, Font NODESLABEL) - основная функция визуализации дерева; Если нажать на кнопку «Добавить элемент», то на экран пользователю будет представлена возможность ввода значения нового узла, а если пользователь захотел удалить элемент, то это можно выполнить, осуществив нажатие на поле «удаление элемента», где пользователь указывает номер узла, который хотел бы удалить, но, если в дереве не присутствует такого узла, то будет выведена ошибка.Тесты строят так, чтобы проверить правильность реализации заданной логики в ходе программы (белый ящик); Удачным считают тест, который обнаруживает хотя бы одну ошибку. В C#, как и в других появившихся до .NET языков, главная методика по отладке состоит в добавлении точек останова и изучении того, что происходит в коде в конкретные моменты во время его выполнения. Вход в режим приостановки выполнения не приводит к прекращению или завершению работы программы, поэтому выполнение программы может быть продолжено в любое время. Для обеспечения большей гибкости отладчик Visual Studio позволяет задавать следующие свойства, изменяющие поведение точки останова: · Параметр Число попаданий позволяет задать количество попаданий в точку останова перед тем, как отладчик прерывает выполнение программы.Перед разработкой программного комплекса был произведен обзор и анализ существующих программных решений, в результате которого был определен набор функциональных требования к разрабатываемой программной системе. На следующем этапе была разработана функциональная схема работы программы и спроектирован интерфейс обмена данными в программной системе, а также описаны используемые методы и алгоритмы.Листинг программы using System; using System.Collections.Generic; using System.Drawing; using System.Windows.Forms; // следующий код дает доступ к рисованию на картинке PICTDEREVO.Image = (Image)new Bitmap(pw, ph);// является ли узел листовым? public bool ISLEAF() {return (Left == null && Right == null) ? true : false; } {if (low > high) return; // граничное условие - для пустого подмассива int mid = (low high) / 2; // середина подмассива this.Insert(A[mid]); // вставляем элемент из середины подмассива {if (cur.Left == null) // если у cur нет левого потомка // визуализация поддерева с корнем root private void VISUALISETREE(Graphics G, BINARYTREENODE root, int LEVELH, int radius, int left, int right, int top, Color NODESCOLOR, Color LEAVESCOLOR, Font NODESLABEL) // если левое поддерево непустое, считаем его число уровней if (root.Left != null) l
Вывод
Целью курсового проекта являлось создание инструментария для работы с динамической структурой - бинарное дерево.
Перед разработкой программного комплекса был произведен обзор и анализ существующих программных решений, в результате которого был определен набор функциональных требования к разрабатываемой программной системе.
На следующем этапе была разработана функциональная схема работы программы и спроектирован интерфейс обмена данными в программной системе, а также описаны используемые методы и алгоритмы. Последним шагом данного этапа стала разработка графического и пользовательского интерфейса.
После создания программного продукта было разработано руководство пользователя.
Финальным этапом стало тестирование программного продукта на наличие ошибок и их отладка.
В результате выполнения курсового проекта было создано полноценное программное обеспечение.
Список литературы
1. ГОСТ 2.105-95. ЕСКД. Общие требования к текстовым документам. - М.: Изд-во стандартов, 2007. - 31 с.
2. Павловская Т. А. C#. Программирование на языке высокого уровня. - Изд.: Питер, 2009. - 432 с.
3. Пайлон Д., Питмен Н. UML 2 для программистов. - Изд.: Питер, 2012. - 240 с.
4. Троелсен Э. Язык программирования C# 2010 и платформа .NET 4. - Изд.: Вильямс, 2011. - 1392 с.
5. Буч Г., Рамбо Д., Якобсон И. Введение в UML от создателей языка. - Изд.: ДМК Пресс, 2011. - 496 с