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

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

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

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

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

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

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

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

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

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

Брянск 2016

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

·        поиск узла;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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