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

Размещено на http://www.allbest.ru/

Кафедра «Компьютерные технологии и системы»

КУРСОВОЙ ПРОЕКТ

Дисциплина: «Языки программирования»

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

Выполнил студент гр. 15-БАС

Бартенева Н.И.

Руководитель

к.т.н., доц. Леонов Ю.А.

Брянск 2016



ВВЕДЕНИЕ

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

Тема бинарных деревьев на сегодняшний день широко изучена и перешла из раздела актуальных задач в раздел классических. На использовании бинарных деревьев построено решение многих прикладных задач:

1. Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).

2. Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.

3. Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации.

Терминология, применяемая для описания бинарных деревьев:

· узел - это точка, где может возникнуть ветвь;

· корень - «верхний» узел дерева;

· ветвь - отрезок, описывающий связь между двумя узлами;

· лист - узел, из которого не выходят ветви, т.е. не имеющий поддеревьев;

· родительским - называется узел, который находится непосредственно над другим узлом;

· дочерним - называется узел, который находится непосредственно под другим узлом;

· предки данного узла - это все узлы на пути вверх от данного узла до корня;

· потомки - все узлы, расположенные ниже данного;

· внутренний узел - узел, не являющийся листом;

· порядок узла - количество его дочерних узлов;

· глубина узла - количество его предков плюс единица;

· глубина (высота) дерева - максимальная глубина всех узлов;

· длина пути к узлу - количество ветвей, которые нужно пройти, чтобы дойди от корня к данному узлу;

· длина пути дерева (длина внутреннего пути) - сумма длин путей всех его узлов.

В основу курсового проекта легли классические требования к разрабатываемому программному решению, а именно:

· добавление узла;

· удаление узла;

· поиск узла;

· балансировка дерева.

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

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Общая формулировка задания

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

Требования к графическому и пользовательскому интерфейсу:

· должно быть реализовано графическое представление дерева;

· необходимо разработать интуитивно-понятный пользовательский интерфейс;

· при поиске и добавлении необходимо выделять найденные/добавленные узлы дерева цветом, отличным от основного.

Требования к функциональным возможностям:

· необходимо реализовать балансировку дерева;

· необходимо предусмотреть возможность перемещения приложения по экрану без потери изображения;

· должна быть реализована система сообщений об ошибках и подсказок пользователю;

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

· должен быть реализован поиск узла дерева.



1. АНАЛИТИЧЕСКИЙ РАЗДЕЛ

1.1 Обзор и анализ существующих программных решений

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

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

Программа «Бинарное дерево поиска на C#»

Первым примером для анализа стала работа Андрея Амельченя «Бинарное дерево поиска на C#» (рис. 1.1). Автор решил продемонстрировать работу с бинарным деревом поиска.

Рис. 1.1 Программа «Бинарное дерево поиска на C#»

Бинарное дерево поиска (рис. 1.2) - это особое двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

· оба поддерева - левое и правое - являются двоичными деревьями поиска;

· у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X;

· в то время, как значения ключей данных у всех узлов правого поддерева (того же узла X) больше, нежели значение ключа данных узла X.

Рис. 1.2 Пример бинарного дерева поиска

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

1. Разработанный автором класс дерева.

2. Наличие методов добавления, удаления и поиска элемента.

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

1. Консольный вывод дерева.

2. Отсутствие балансировки.

Программа «BinTree»

Еще одна работа, рассмотренная в рамках анализа, принадлежит Дмитрию Мгали (рис. 1.3). Программа также написана на языке программирования C#, но в отличие от предыдущей работы создана в формате Windows Forms приложения, благодаря чему имеет более приятный для использования графический интерфейс.

Рис. 1.3 Программа «BinTree»

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

1. Графический интерфейс.

2. Наличие кнопки «информация о дереве», которая выводит диалоговое окно с данными о высоте дерева и количестве элементов в нем.

3. Дополнительный функционал, включающий возможность сохранить построенное дерево и загрузить дерево из сохраненного файла.

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

1. Дерево формируется только путем последовательного добавления вершин;

2. Возможность задать количество элементов в дереве отсутствует;

3. Существует два алгоритма поиска, но оба ориентированы на поиск пути к элементу, что не рационально. Первый, реализуемый кнопкой «Найти» выводит сообщение, в котором путь к элементу представлен как последовательность букв R и L (правое поддерево и левое поддерево соответственно). Второй, реализуемый кнопкой «Показать», изменяет цвет линий, соединяющих корень с заданным элементом.

4. Удаление элемента реализовано в двух вариантах, разницы между которыми замечено не было.

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

6. Программа не устойчива к неверным действиям пользователя. Например, при нажатии кнопки «Загрузить», а потом кнопки «Отмена» в диалоговом окне, происходит ошибка.

1.2 Определение функциональных требований к разрабатываемой программной системе

На основе проделанного предварительного анализа существующих программных решений были сформулированы следующие принципы работы:

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

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

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

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

· необходимо реализовать отдельный класс для работы с динамической структурой - бинарное дерево поиска;

· должно быть реализовано графическое представление дерева;

· должна присутствовать возможность задавать количество узлов в дереве и их диапазон перед построением автоматически и вручную;

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

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

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

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

· необходимо предусмотреть возможность перемещения приложения по экрану без потери изображения дерева;

· программа должна корректно реагировать на ошибки пользователей;

· должна быть реализована система сообщений об ошибках и подсказок пользователю.

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

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



2. КОНСТРУКТОРСКИЙ РАЗДЕЛ

2.1 Обоснование выбора языка и среды программирования

Для реализации программного продукта было решено использовать язык программирования C# и среду программирования Microsoft Visual Studio.

C# (произносится «си шарп») - объектно-ориентированный язык программирования, относится к семье языков с C-подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку (в том числе операторов явного и неявного приведения типа), атрибуты, события, свойства, обобщённые типы и методы, исключения, комментарии в формате XML.

C# перенял многое от своих предшественников - языков C++, Pascal, Модула, Smalltalk и, в особенности, Java, опираясь на практику их использования, C# исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# в отличие от C++ не поддерживает множественное наследование классов (между тем допускается множественное наследование интерфейсов).

Microsoft Visual Studio - линейка продуктов компании Microsoft, включающих интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии Windows Forms.

На сегодняшний день существует большое количество языков программирования, у каждого из которых есть свои достоинства и недостатки. Для реализации данного приложения, а также для полного выполнения поставленной задачи язык программирования C# является наиболее подходящим. С этим языком удобнее всего работать в среде программирования Microsoft Visual Studio, предназначенной специально, в том числе и для C#, а также обладающей широкими возможностями по отладке и для работы с графическими элементами.

2.2 Функциональная схема работы программы

В данном разделе была разработана функциональная схема работы программного комплекса, которая в общем виде описывает состав комплекса, характер и виды взаимодействия отдельных функциональных блоков между собой (рис. 2.1).

Рис. 2.1 Функциональная схема работы программы



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

Функция генерации случайных чисел предназначена для заполнения массива, из которого впоследствии будет инициализировано дерево, числами.

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

Функция прорисовки дерева является ключевой во взаимодействии программы с пользователем. Эта функция отображает хранимое в оперативной памяти компьютера дерево.

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

Функция удаления узла получает значение удаляемого узла из функции получения данных от пользователя и передает его в функцию инициализации дерева. Если переданное значение совпадает со значением элемента массива, то элемент удаляется из массива и исключается из расчета при выделении памяти под узлы дерева.

Организация данных и проектирование интерфейсов обмена данными в программной системе

Данные - интерпретируемое формализованным способом представление информации, пригодное для коммуникации, интерпретации или обработки [1].

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

Пользователь сможет передать данные двух видов:

· величины из заполняемых пользователем форм;

· события, создаваемые пользователем.

Не все характеристики дерева будут вынесены в формы для определения пользователем. К передаваемым пользователем величинам будет относиться только значение узлов в дереве. Также пользователь сможет передать значение узла для добавления или удаления.

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

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

· строковые данные;

· целочисленные данные;

· данные, представленные в виде объекта класса узел.

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

Функция инициализации дерева получит строковый массив и на его основе выделит память под новый целочисленный массив, значениями из которого будут инициализированы информационные поля объектов класса узел. Выходными данными функции будет являться упорядоченный набор узлов.

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



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

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

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

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

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

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

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

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() - конструктор пустого дерева;

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,

int LevelH, int radius, int left, int right, int top, Color NodesColor,

Color LeavesColor, Font NodesLabel) - метод визуализации поддерева;

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

· public void VisualiseTree(Graphics G, int radius, int width, int height,

Color 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. Этот метод использования точек останова называется "точки трассировки".

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



ЗАКЛЮЧЕНИЕ

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

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

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

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

Финальным этапом стало тестирование программного продукта на наличие ошибок и их отладка.

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



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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 с



ПРИЛОЖЕНИЯ

Приложение 1

Листинг программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

namespace BinTree

{

public partial class Form1 : Form

{

BinaryTree<int> Derevo = new BinaryTree<int>();

Graphics pictGraphics; // для доступа к поверхности pictureBox

// шрифт для показа содержимого узлов

Font NodesFont = new Font(FontFamily.GenericMonospace, (float)12.0, FontStyle.Bold);

Color NodesColor = Color.FromArgb(255, 255, 0); // цвет внутренных узлов

Color LeavesColor = Color.FromArgb(255, 127, 0); // цвет листьев

public Form1()

{

InitializeComponent();

}

// при загрузке формы

private void Form1_Load(object sender, EventArgs e)

{

// кнопки "развернуть" и "свернуть" будут недоступны

this.MinimizeBox = false;

this.MaximizeBox = false;

int pw = pictDerevo.Width, ph = pictDerevo.Height; // размеры pictureBox

// следующий код даёт доступ к рисованию на картинке

pictDerevo.Image = (Image)new Bitmap(pw, ph);

pictGraphics = Graphics.FromImage(pictDerevo.Image);

RefreshTree(); // обновляем картинку

}

// содержится ли элемент item среди первых n элементов массива A?

bool ContainsInArray(int[] A, int n, int item)

{

for (int i = 0; i < n; i++)

if (A[i] == item) return true;

return false;

}

// получение случайных чисел в диапазоне [xmin; xmax]

// размер массива случайный от nmin до nmax

int[] GetRandItems(int nmin, int nmax, int xmin, int xmax)

{

// DateTime.Now.Millisecond - для инициализации случайного датчика

Random R = new Random(DateTime.Now.Millisecond);

int n = R.Next(nmin, nmax + 1); // получаем случайный размер

int[] A = new int[n];

for (int i = 0; i < n; i++)

{

int cur = R.Next(xmin, xmax + 1); // генерируем новое случайное число

// если оно уже есть среди ранее сгенерированных случайных чисел

if (ContainsInArray(A, i, cur) == true) i--;

else A[i] = cur; // если оно НОВОЕ

}

return A;

}

void CopyRight() // рисование копирайта

{

string s = "Автор Бартенева Н.И.";

Brush B = new SolidBrush(Color.Red); // цвет надписи копирайта

// центр круга, по которому выведем буквы

double xc = pictDerevo.Width - 80;

double yc = 80;

// h_fi - шаг угла, cur_fi - текущий угол

double h_fi = 2.0 * Math.PI / s.Length, cur_fi = Math.PI / 2.0;

for (int i = 0; i < s.Length; i++, cur_fi += h_fi)

{

// позиция для вывода i-ой буквы

double x = xc - 60 * Math.Cos(cur_fi);

double y = yc - 60 * Math.Sin(cur_fi);

// вывод i-ой буквы

pictGraphics.DrawString(s.Substring(i, 1), NodesFont, B, (float)x, (float)y);

}

}

void RefreshTree() // обновление картинки

{

pictGraphics.Clear(pictDerevo.BackColor); // очищаем картинку

Derevo.VisualiseTree(pictGraphics, 14, pictDerevo.Width, pictDerevo.Height,

NodesColor, LeavesColor, NodesFont); // показываем дерево

CopyRight(); // рисуем копирайт

pictDerevo.Invalidate(); // инициируем отрисовку на картинке

}

private void построитьПоСлучайнойКоллекцииToolStripMenuItem_Click(object sender, EventArgs e)

{

// получаем случайные числа (в данном случае от 1 до 99)

int[] A = GetRandItems(3, 15, 1, 99);

Derevo = new BinaryTree<int>(A, A.Length); // строим дерево

RefreshTree();

}

private void добавитьЭлементToolStripMenuItem_Click(object sender, EventArgs e)

{

MyDlgWindow.SelectedNum = 0; // останется нулём, если пользователь закроет диалог

new MyDlgWindow("Добавление элемента").ShowDialog();

if (MyDlgWindow.SelectedNum == 0) return; // если пользователь закрыл диалог

// если пользователь нажал на ОК в открывшемся диалоге

// Insert возвращает false, если была попытка вставки существующего элемента

if (Derevo.Insert(MyDlgWindow.SelectedNum) == false)

{

MessageBox.Show("Элемент " + MyDlgWindow.SelectedNum.ToString() + " уже имеется");

return;

}

RefreshTree();

}

private void удалитьЭлементToolStripMenuItem_Click(object sender, EventArgs e)

{

MyDlgWindow.SelectedNum = 0;

new MyDlgWindow("Удаление элемента").ShowDialog();

if (MyDlgWindow.SelectedNum == 0) return;

// Remove возвращает false, если была попытка удаления отсутствующего элемента

if (Derevo.Remove(MyDlgWindow.SelectedNum) == false)

{

MessageBox.Show("Элемент " + MyDlgWindow.SelectedNum.ToString() + " отсутствует");

return;

}

RefreshTree();

}

// выбор файла с помощью стандартного диалога

string GetFName()

{

OpenFileDialog dlg = new OpenFileDialog();

dlg.Filter = "Special Tree Files (*.derevo)|*.derevo";

dlg.Multiselect = false;

dlg.InitialDirectory = Path.GetDirectoryName(Application.ExecutablePath);

if (dlg.ShowDialog() == DialogResult.OK)

return dlg.FileName;

return null;

}

private void загрузитьКоллекциюИзФайлаToolStripMenuItem_Click(object sender, EventArgs e)

{

string FileName = GetFName(); // пользователь выбирает файл в стандартном диалоге

if (FileName == null) return; // если пользователь ничего не выбрал

// грузим элементы из файла в список (не в массив, т.к. число элементов

// неясно до полного просмотра файла)

List<int> Items = new List<int>();

StreamReader sr = new StreamReader(FileName, Encoding.GetEncoding(1251));

string buffer;

while ((buffer = sr.ReadLine()) != null)

{

Items.Add(Convert.ToInt32(buffer));

}

sr.Close();

int[] A = Items.ToArray(); // получаем массив по списку элементов

Derevo = new BinaryTree<int>(A, A.Length); // строим дерево

RefreshTree();

}

}

}



Приложение 2

Листинг классов BinaryTree и BinaryTreeNode

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Drawing;

namespace BinTree

{

class BinaryTreeNode<Data> // шаблон класса УЗЕЛ ДЕРЕВА

{

public Data Item; // полезные данные

public BinaryTreeNode<Data> Left, Right; // ссылки на дочерние узлы

public BinaryTreeNode(Data Item) // конструктор

{

this.Item = Item;

this.Left = null;

this.Right = null;

}

// является ли узел листовым?

public bool IsLeaf() { return (Left == null && Right == null) ? true : false; }

}

class BinaryTree<Data> where Data:IComparable<Data> // класс БИНАРНОЕ ДЕРЕВО ПОИСКА

{

private BinaryTreeNode<Data> root; // ссылка на корень

public BinaryTree() // конструктор пустого дерева

{

this.root = null;

}

private void QuickSort(Data[] A, int low, int high) // "быстрая сортировка"

{

int i = low, j = high;

Data x = A[(low + high) / 2];

do

{

while (A[i].CompareTo(x) < 0) i++;

while (A[j].CompareTo(x) > 0) j--;

if (i <= j)

{

Data temp = A[i];

A[i] = A[j];

A[j] = temp;

i++;

j--;

}

}

while (i < j);

if (low < j) QuickSort(A, low, j);

if (i < high) QuickSort(A, i, high);

}

// следующая функция вставки формирует идеально сбалансированное дерево

void IBTInsert(Data[] A, int low, int high)

{

if (low > high) return; // граничное условие - для пустого подмассива

int mid = (low + high) / 2; // середина подмассива

this.Insert(A[mid]); // вставляем элемент из середины подмассива

IBTInsert(A, low, mid - 1); // рекурсия для левой половины

IBTInsert(A, mid + 1, high); // рекурсия для правой половины

}

// конструктор на основе массива

public BinaryTree(Data [] Records, int NRecords)

{

if (NRecords == 0) // если массив пустой

{

this.root = null;

return;

}

// если более одной записи - требуется сортировка

if (NRecords > 1) QuickSort(Records, 0, NRecords - 1);

// строим по отсортированному массиву сбалансированное дерево

IBTInsert(Records, 0, NRecords - 1);

}

public bool Insert(Data NewItem) // вставка

{

if (root == null) // если дерево пустое

{

root = new BinaryTreeNode<Data>(NewItem);

return true;

}

// для непустого дерева

BinaryTreeNode<Data> cur = root;

while (true)

{

// если такой элемент уже есть в дереве, вставка неуспешна

if (cur.Item.CompareTo(NewItem) == 0) return false;

// если элемент в узле cur больше элемента NewItem

if (cur.Item.CompareTo(NewItem) > 0)

{

if (cur.Left == null) // если у cur нет левого потомка

{

// вставляем влево и завершаем вставку

cur.Left = new BinaryTreeNode<Data>(NewItem);

break;

}

cur = cur.Left; // если у cur есть левый потомок, идём к нему

}

else // если элемент в узле cur меньше элемента NewItem

{

// действуем аналогично предыдущей ситуации, но в правом поддереве

if (cur.Right == null)

{

cur.Right = new BinaryTreeNode<Data>(NewItem);

break;

}

cur = cur.Right;

}

}

return true;

}

// визуализация поддерева с корнем root

private void VisualiseTree(Graphics G, BinaryTreeNode<Data> root,

int LevelH, int radius, int left, int right, int top, Color NodesColor,

Color LeavesColor, Font NodesLabel)

{

// levelH - высота области под один уровень, radius - радиус круга, который показывает узел,

// NodesColor - цвет внутренныз узлов, LeavesColor - цвет листьев,

// NodesLabel - шрифт для показа элементов, G - объект, куда выводим

// координаты центра круга, обозначающего узел дерева

int xc = (left + right) / 2, yc = top + LevelH / 2;

// кисть для закраски круга, цвет зависит от того, root - лист или нет

Brush ForEllipse = new SolidBrush((root.IsLeaf() == true) ? LeavesColor : NodesColor);

// рисуем узел-кружок

G.FillEllipse(ForEllipse,

new Rectangle(xc - radius, yc - radius, 2 * radius, 2 * radius));

// показываем элемент узла

G.DrawString(root.Item.ToString(), NodesLabel, Brushes.Black,

new Rectangle(xc - radius, yc - radius / 2, 2 * radius, radius));

int d = (int)(Math.Sqrt(0.5) * ((double)radius));

int rchild_left, rchild_top = top + LevelH, rchild_right;

int xc_child, yc_child = rchild_top + LevelH / 2;

if (root.Left != null) // если есть левое поддерево

{

// координаты области построения

rchild_left = left;

rchild_right = (left + right) / 2;

xc_child = (rchild_left + rchild_right) / 2;

// рисуем соединительную линию между узлом и левым сыном

G.DrawLine(new Pen(Color.Black), xc_child, yc_child - d, xc - d, yc + d);

// рекурсивный вызов для левого сына

VisualiseTree(G, root.Left, LevelH, radius, rchild_left, rchild_right,

rchild_top, NodesColor, LeavesColor, NodesLabel);

}

if (root.Right != null) // если есть правое поддерево (аналогично левому)

{

rchild_left = (left + right) / 2;

rchild_right = right;

xc_child = (rchild_left + rchild_right) / 2;

G.DrawLine(new Pen(Color.Black), xc + d, yc + d, xc_child, yc_child - d);

VisualiseTree(G, root.Right, LevelH, radius, rchild_left, rchild_right,

rchild_top, NodesColor, LeavesColor, NodesLabel);

}

}

// количество уровней в поддереве с корнем root

private int LevelsAmount(BinaryTreeNode<Data> root)

{

int lev_left_sub = 0, lev_right_sub = 0;

// если левое поддерево непустое, считаем его число уровней

if (root.Left != null) lev_left_sub = LevelsAmount(root.Left);

// если правое поддерево непустое, считаем его число уровней

if (root.Right != null) lev_right_sub = LevelsAmount(root.Right);

// число уровней дерева = 1 + число уровней самого высокого поддерева

// если левое поддерево выше правого

if (lev_left_sub >= lev_right_sub)

return lev_left_sub + 1;

return lev_right_sub + 1; // если правое поддерево выше левого

}

// визуализация дерева - главная функция

public void VisualiseTree(Graphics G, int radius, int width, int height,

Color NodesColor, Color LeavesColor, Font NodesLabel)

{

if (this.root == null) // для пустого дерева

{

G.DrawString("Дерево пустое (root = null)", NodesLabel, Brushes.Black,

(float)0.0, (float)0.0);

return;

}

// для непустого дерева

int nLevs = LevelsAmount(this.root); // вычисляем количество уровней

VisualiseTree(G, this.root, height / nLevs, radius, 0, width, 0,

NodesColor, LeavesColor, NodesLabel); // визуализируем дерево

}

// поиск родителя для узла Item

private BinaryTreeNode<Data> FindParent(Data Item)

{

if (this.root.Item.CompareTo(Item) == 0) return null;

BinaryTreeNode<Data> cur = root;

while (true)

{

if (cur.Item.CompareTo(Item) > 0)

{

if (cur.Left == null) break;

if (cur.Left.Item.CompareTo(Item) == 0) break;

cur = cur.Left;

}

else

{

if (cur.Right == null) break;

if (cur.Right.Item.CompareTo(Item) == 0) break;

cur = cur.Right;

}

}

return cur;

}

public bool Remove(Data ToRemove) // удаление элемента ToRemove

{

BinaryTreeNode<Data> nodeToRemove = root;

BinaryTreeNode<Data> parent = null;

// спуск с поиском удаляемого узла

while ((nodeToRemove != null) && (ToRemove.CompareTo(nodeToRemove.Item) != 0))

{

parent = nodeToRemove;

if (ToRemove.CompareTo(nodeToRemove.Item) < 0)

nodeToRemove = nodeToRemove.Left;

else nodeToRemove = nodeToRemove.Right;

}

// если запрашиваемый элемент отсутствует

if (nodeToRemove == null) return false;

// если удаляемый узел - корень, и он единственный

if (nodeToRemove == root && root.IsLeaf() == true)

{

root = null;

return true;

}

// если удаляемый узел является листовым

if (nodeToRemove.Left == null && nodeToRemove.Right == null)

{

// если он - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0)

parent.Left = null;

else parent.Right = null; // если он - правый ребёнок своего родителя

return true;

}

// если у удаляемого узла есть только правое поддерево

if (nodeToRemove.Left == null && nodeToRemove.Right != null)

{

// если удаляемый узел - корень

if (nodeToRemove == root) root = root.Right;

else // если удаляемый узел - не корень

{

// если удаляемый узел - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0)

parent.Left = nodeToRemove.Right;

// если он правый ребёнок своего родителя

else parent.Right = nodeToRemove.Right;

}

return true;

}

// если у удаляемого узла есть только левое поддерево

if (nodeToRemove.Left != null && nodeToRemove.Right == null)

{

// если удаляемый узел - корень

if (nodeToRemove == root) root = root.Left;

else // если удаляемый узел - не корень

{

// если удаляемый узел - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0)

parent.Left = nodeToRemove.Left;

// если удаляемый узел - правый ребёнок своего родителя

else parent.Right = nodeToRemove.Left;

}

return true;

}

// если у удаляемого узла есть оба поддерева

// ищем наибольший элемент в левом поддереве удаляемого узла

BinaryTreeNode<Data> largestItem = nodeToRemove.Left;

while (largestItem.Right != null)

largestItem = largestItem.Right;

// ищем родителя наибольшего элемента в левом поддереве

BinaryTreeNode<Data> ParentOfLI = FindParent(largestItem.Item);

if (nodeToRemove.Left != largestItem) // если этот родитель - не сам удаляемый узел

{

// если у наибольшего элемента есть левое поддерево

if (largestItem.Left != null) ParentOfLI.Right = largestItem.Left;

else ParentOfLI.Right = null; // если у него нет левого поддерева

}

// если этот родитель - сам удаляемый узел

else nodeToRemove.Left = largestItem.Left;

// заменяем элемент удаляемого узла на наибольший элемент в левом поддереве

nodeToRemove.Item = largestItem.Item;

return true;

}

}

}



Приложение 3

Графический интерфейс программы

Размещено на Allbest.ur