Методика решения поставленой задачи и обоснование наравления разработки программного продукта
Обоснование выбранного языка программирования
Для реализации поставленной задачи был выбран язык программирования C#. Он является достаточно надежным языком по сравнению с C и C++. Так же он содержит огромное множество стандартных библиотек, которые значительно упрощают процесс написания программного кода. Его главными преимуществами являются лямбда-выражения и анонимные делегаты. С помощью лямбда-выражений и библиотеки LINQ легко реализовать на первый взгляд сложные задачи. Например, сортировка, замена, выборка из множества и тому подобное. C# унаследовал все лучшие качества таких языков, как C, C++, Delphi, Java.
Язык программирования C# базируется на 3 основных принципах: наследование, полиморфизм, инкапсуляция (как и любой другой ОО язык программирования). Он не поддерживает множественное наследование, но не запрещает реализовывать несколько интерфейсов в одном классе.
C# – элегантный, типобезопасный объектно-ориентированный язык, предназначенный для разработки разнообразных безопасных и мощных приложений, выполняемых в среде .NET Framework.
Методика решения поставленной задачи
Для решения поставленной задачи необходимо создать рекурсивный класс «Дерево», который будет содержать в себе все необходимые методы для работы с данными. Действия добавления, удаления, замены узла и визуализации дерева необходимо реализовать на отдельных формах для упорядочивания кода. Для передачи данных в объект класса «Дерево» из других форм удобнее всего будет воспользоваться событиями. Вывод данных и их сортировку проще всего реализовать через методы расширения LINQ и лямбда-выражения.
Добавление элемента в дерево осуществляется по простому рекурсивному алгоритму: если узел пуст, то внести в него значение, иначе сравнить значение узла с тем, которое необходимо занести в дерево. Если вносимое значение меньше, то проделать ту же операцию для левого поддерева, если больше, то для правого.
Для обхода бинарного дерева есть огромное множество алгоритмов, каждый из которых по-своему хорош и используется в зависимости от поставленной задачи. Из всего многообразия разных способов обхода бинарного дерева будут рассмотрены только два способа: обход в ширину и обход в глубину.
Обход в глубину начинается с движения вправо или влево, насколько это возможно и продвигается до восхождения. Далее, переходя по ссылке вверх, обход снова движется направо или налево. Процесс повторяется, пока все узлы не будут посещены. Обход в глубину может быть написан рекурсивно, потому что маршрут движения построен на принципе стека. Существует всего 6 путей обхода и посещения узлов при обходе в глубину. Существует три пути, по которым можно пойти: «перейти влево», «перейти вправо», «посетить»:
– посетить, перейти влево, перейти вправо;
– посетить, перейти вправо, перейти влево;
– перейти влево, посетить, перейти вправо;
– перейти вправо, посетить, перейти влево;
– перейти влево, перейти вправо, посетить;
– перейти вправо, перейти влево, посетить.
Из этих 6 вариаций 3 используются наиболее часто и имеют свои собственные стандартные названия: 1 – обход в прямом порядке, т.к. сперва посещается узел; 3 – симметричный обход, т.к. узлы обходятся в порядке сортировки их значений; и, наконец, 5 – обход в обратном порядке, потому что узел посещается после того, как совершены оба движения.
При обходе дерева в ширину чаще всего используется очередь. Суть этого способа проста:
1. В очередь добавляется первый элемент (корень).
2. Запускается цикл с условием выхода при количестве элементов очереди равным 0.
a) Берется первый элемент из очереди и проверяется на наличие левого поддерева, если оно есть, то левое поддерево добавляется в конец очереди.
b) Берется первый элемент из очереди и проверяется на наличие правого поддерева, если оно есть, то правое поддерево добавляется в конец очереди.
c) Первый элемент очереди удаляется и цикл запускается заново.
Для визуализации дерева есть, возможно не самый эффективный, но все же простой способ, для которого необходимо следующее:
– счетчик отрисованных узлов;
– переменная, отвечающая за «этаж» дерева.
Счетчик отрисованных узлов будет выполнять роль переменной, отвечающей за положение узла в пространстве по оси абсцисс или X. Переменная, отвечающая за этаж – это ось ординат или Y. Обе эти переменные изначально должны быть равны нулю. Далее следует запрограммировать следующий алгоритм:
– если у узла есть левое поддерево, то произвести для него этот же алгоритм сначала, изменив значение Y на +1, иначе отрисовать текущий узел по координате (X,Y), изменив значение X на +1;
– если у узла есть левое поддерево, то отрисовать текущий узел по координате (X,Y), изменив значение X на +1;
– если у узла есть правое поддерево, то проделать для него этот же алгоритм сначала.
У каждого узла должно быть свойство, отвечающее за положение узла (его координаты). И при отрисовке узлов, необходимо записыавть эти координаты в соответствующие свойства. Затем реализовать ещё один простой алгоритм:
– если у узла есть родитель, то провести от координат узла до координат родителя линию;
– если у узла есть левое поддерево, то проделать этот же алгоритм для левого поддерева;
– если у узла есть правое поддерево, то проделать этот же алгоритм для правого поддерева.
Таким образом, с помощью двух предельно простых алгоритмов можно реализовать, казалось бы, сложную задачу.
Визуализация бинарного дерева значительно помогает в понимании принципа его работы. Дает большее представление о том, что же такое бинарное дерево.
Бинарные деревья в целом – это хорошее упражнение, чтобы понять особенности языка, такие как: условные операторы, циклы, рекурсия, классы. В то же время, это возможность решить интересную задачу. Алгоритм бинарного дерева хорошо описан во многих книгах и в интернете. Поэтому сложностей с его программированием обычно не возникает.
Разработка программы
Диаграмма классов
Диаграмма классов – диаграмма, демонстрирующая классы системы, их атрибуты, методы и взаимосвязи между ними [6]. Существует два вида диаграмм классов:
– статический вид диаграммы рассматривает логические взаимосвязи классов между собой;
– аналитический вид диаграммы рассматривает общий вид и взаимосвязи классов, входящих в систему.
Взаимосвязь – это особый тип логических отношений между сущностями, показанных на диаграммах классов и объектов.
Ассоциация – вид отношений между сущностями, показывающий, что объекты одной сущности (класса) связаны с объектами другой сущности.
Рисунок 3.1 – Иерархический вид диаграммы классов
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|