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

Разработка автоматизированной информационной системы «Планета животных»

РЕФЕРАТ

программирование объектный ориентированный

Курсовая работа: страницы, рисунков, таблиц, источников, приложения.

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

Целью работы является разработка Windows-приложение автоматизированной информационной системы «Планета животных».

Объектом разработки являются информационные технологии.

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

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

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

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

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

ВВЕДЕНИЕ

Увеличение в конце XX века использования информационных технологий, привело к интенсивному техническому развитию в этой отрасли. Постепенно уменьшались размеры и стоимость вычислительной техники, делая её общедоступной, совершенствовались носители информации, увеличивая доступные объёмы данных. Вместе с тем появилась необходимость создания эффективных методов, структурирования большого объёма информации. Одним из возможных решений стала организация данных в виде дерева. В наше время такую структуру используют практически все файловые системы доступные потребителям, такие как Windows, Linux, Unix и многие другие. Древовидная структура позволяет группировать имеющиеся данные по некоторым схожим характеристикам, позволяя пользователю эффективно организовывать и использовать данные.

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

В процессе выполнения данной курсовой работы будут решены следующие задачи:

- изучение построения бинарного дерева;

- реализация с помощью бинарного дерева поиска, данных;

- оформление блок-схемы задачи;

- разработка Windows-приложение на языке С#, выполняющее необходимые действия.

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

В пояснительной записке объясняются основные алгоритмы операций для работы с бинарным деревом, а также представлены блок-схемы для каждого из них. В теоретической части описаны общие сведения о бинарных деревьях, что позволяет ознакомиться и понять принцип работы с такого типа структурой. В практической части рассмотрены этапы создания программы, описано, поэтапное создание программы и принцип её работы, а также представлены графические изображения различных компонентов среды MS Visual C# 2012 и представлен код самой программы.

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

1. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ

1.1 Что такое объектно-ориентированное программирование

Элементы объектно-ориентированного программирования (ООП) появились в начале 70-х годов в языке моделирования Симула, затем получили свое развитие, и в настоящее время ООП принадлежит к числу ведущих технологий программирования.

Основная цель ООП, как и большинства других подходов к программированию - повышение эффективности разработки программ. Идеи ООП оказались плодотворными, и нашли применение не только в языках программирования, но и в других областях Computer Science, например, в области разработки операционных систем.

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

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

Объектно-ориентированное программирование является относительно новым подходом к созданию компьютерных приложений, который призван устранить многие из проблем, существующих в традиционных методиках программирования. Вид программирования, с которым пока имели дело, называется функциональным (или процедурным) программированием и часто приводит к созданию так называемых монолитных приложений, все функции которых сконцентрированы в нескольких модулях кода (а то и вовсе в одном). В ООП обычно используется гораздо больше модулей, каждый из которых обеспечивает конкретные функции и может быть изолирован или даже полностью отделен от всех остальных. Такое модульное программирование обеспечивает гораздо большую гибкость и возможности для многократного использования кода [1].

1.2 Сущность объектно-ориентированного подхода в программировании

Развитие объектно-ориентированного метода обусловлено ограниченностью разработанных ранее методов программирования. Задачи, для которых создавались процедурные языки программирования, характеризовались небольшим объемом команд и не требовали дополнительной внутренней организации. Когда же размер программы велик, список команд становится слишком громоздким, и код необходимо разделять на более мелкие логические части. Деление программы на функции и модули является основой структурного программирования, как способа организации программ. Однако существенно упростить большие программы структурный подход к программированию позволяет не всегда.

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

Объект определяется как осязаемая реальность - предмет или явление, имеющие четко определяемое поведение. Объект обладает состоянием, поведением и индивидуальностью; структура и поведение схожих объектов определяют общий для них класс. Термины "экземпляр класса" и "объект'' являются эквивалентными. Состояние объекта характеризуется перечнем всех возможных (статических) свойств данного объекта и текущими значениями (динамическими) каждого из этих свойств. Поведение характеризует воздействие объекта на другие объекты и наоборот относительно изменения состояния этих объектов и передачи сообщений. Иначе говоря, поведение объекта полностью определяется его действиями. Индивидуальность - это свойства объекта, отличающие его от всех других объектов.

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

Класс - это множество объектов, связанных общностью структуры и поведения. Любой объект является экземпляром класса. Определение классов и объектов - одна из самых сложных задач объектно-ориентированного проектирования.

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

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

Концептуальной основой объектно-ориентированного подхода является объектная модель. Основными се элементами являются: абстрагирование, инкапсуляция, модульность, иерархия.

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

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

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

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

Устойчивость - свойство объекта существовать, но времени (вне зависимости от процесса, породившего данный объект) и/или в пространстве (при перемещении объекта из адресного пространства, в котором он был создан).

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

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

Инкапсуляция - это процесс отделения друг от друга отдельных элементов объекта, определяющих его устройство и поведение. Инкапсуляция служит для того, чтобы изолировать интерфейс объекта, отражающий его внешнее поведение, от внутренней реализации объекта. Объектный подход предполагает, что собственные ресурсы, которыми могут манипулировать только методы самого класса, скрыты от внешней среды. Абстрагирование и инкапсуляция являются взаимодополняющими операциями: абстрагирование фокусирует внимание на внешних особенностях объекта, а инкапсуляция (или, иначе, ограничение доступа) не позволяет объектам-пользователям различать внутреннее устройство объекта.

Важным качеством объектного подхода является согласованность моделей деятельности организации и моделей проектируемой системы от стадии формирования требований до стадии реализации. Требование согласованности моделей выполняется благодаря возможности применения абстрагирования, модульности, полиморфизма на всех стадиях разработки. Модели ранних стадий могут быть непосредственно подвергнуты сравнению с моделями реализации. По объектным моделям может быть прослежено отображение реальных сущностей моделируемой предметной области (организации) в объекты и классы информационной системы [2].

1.3 Объектно-ориентированные языки

Инкапсуляция, наследование и полиморфизм - фундаментальные свойства, требуемые от языка, претендующего называться объектно-ориентированным. (Языки, не имеющие наследования и полиморфизма, но имеющие только классы, обычно называются основанными на классах.) Различные объектно-ориентированные языки используют совершенно разные подходы. Мы можем различать объектно-ориентированные языки, сравнивая механизм контроля типов, способность поддерживать различные программные модели и то, какие объектные модели они поддерживают. Языки объектного программирования принято делить на объектные, в которых существуют классы и объекты, и объектно-ориентированные, в которых программист может не только пользоваться предопределёнными классами, но и задавать собственные пользовательские классы (либо создавать объекты, устройство которых отличается от устройства прототипов - в языках прототипного программирования).

Объектное и объектно-ориентированное программирование возникло в результате развития идеологии процедурного программирования, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в современном объектно-ориентированном программировании часто большое значение имеют понятия события (так называемое событийно-ориентированное программирование) и компонента (компонентное программирование).

Объектно-ориентированное программирование в настоящее время является абсолютным лидером в области прикладного программирования (языки Java, C#, C++, JavaScript, ActionScript и др.). В то же время в области системного программирования до сих пор лидирует парадигма процедурного программирования, и основным языком программирования является язык C. Хотя при взаимодействии системного и прикладного уровней операционных систем заметное влияние стали оказывать языки объектно-ориентированного программирования. Например, мультиплатформенным стандартом стала система Qt, написанная на языке C++.

Си++ - это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей Си++ является надмножеством языка программирования Cи. Помимо возможностей, которые дает Cи, Си++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы.

Первым языком программирования, в котором были предложены принципы объектной ориентированности, была Симула. В момент своего появления, этот язык программирования предложил поистине революционные идеи: объекты, классы, виртуальные методы и др., однако это всё не было воспринято современниками как нечто грандиозное. Тем не менее, большинство концепций были развиты Аланом Кэйем и Дэном Ингаллсом в языке Smalltalk. Именно он стал первым широко распространённым объектно-ориентированным языком программирования.

Различаются чистые и гибридные объектно-ориентированные языки. Чистые - это те, которые позволяют использовать только одну модель программирования - объектно-ориентированную. Можно объявлять классы и методы, но заводить глобальные переменные и обычные функции и процедуры старого типа нельзя.

Среди трех языков, только Java(и его клон C#) является чистым объектно-ориентированным языком (как Eiffel и Smalltalk). На первый взгляд это кажется положительной идеей. Однако она ведет к тому, что используется куча статических методов и статических данных, что не так уж отличается от использования глобальных функций и данных, за исключением более сложного синтаксиса. Чистые объектно-ориентированные языки дают преимущество новичкам в объектно-ориентированном программировании, потому что программист вынужден использовать (и учить) модель объектно-ориентированного программирования. C++ и Object Pascal, наоборот, - типичные примеры гибридных языков, которые позволяют программистам использовать при необходимости традиционный подход C или Pascal.

Smalltalk расширяет эту идею до уровня «обобъекчивания» таких предопределенных типов данных, как целые и символы, а также языковых конструкций (таких как циклы). Это теоретически интересно, но сильно уменьшает эффективность. Java останавливается много раньше, допуская присутствие простых не объектно-ориентированных типов данных (хотя имеются необязательные классы-обертки и для простых типов) [3].

2. ИСПОЛЬЗОВАНИЕ БИНАРНЫХ ДЕРЕВЬЕВ ДЛЯ ПОИСКА ДАННЫХ

2.1 Понятие корневого дерева

В теории графов конечное корневое дерево формально определяется как непустое конечное множество узлов Т, таких что: существует один, специально выделенный узел, называемый корнем, а остальные узлы образуют попарно непересекающиеся подмножества множества узлов Т, каждое из которых является деревом. Это определение позволяет интерпретировать корневое дерево как рекурсивный объект, который содержит сам себя и определяется с помощью себя самого (т. е. дерево определяется в терминах дерева). Определение корневого дерева как определение любого рекурсивного объекта содержит базисную и рекурсивную части. Базисная часть, определяющая корень дерева является не рекурсивным утверждением. Рекурсивная часть определения записана так, чтобы она редуцировалась (сводилась) к базе цепочкой повторных применений. В данном случае дерево с числом узлов n>1 индуктивно определяется через деревья с числом узлов меньше, чем n, пока не достигнут базисный шаг, где дерево состоит из единственного узла - корня.

Рекурсивное определение корневого дерева позволяет более простым способом формализовать его структуру и алгоритмы обработки. Для неформального описания корневых деревьев часто используется генеалогическая терминология, согласно которой каждая ветвь отражает отношение потомок-предок между инцидентными ей узлами. Корень дерева - это узел, который не имеет предка. Узлы дерева, которые не имеют потомков называются листьями. Остальные узлы (не листья и не корень) называются разветвлениями.

Рисунок 2.1 иллюстрирует классическое изображение корневого дерева средствами теории графов, где вершины и ребра графа представляют узлы и ветви дерева.

Рисунок 2.1 - Классическое изображение корневого дерева

На этом рисунке заглавные буквы латинского алфавита обозначают узлы, а строчные - ветви корневого дерева. Конфигурация ветвей этого корневого дерева такова, что узел А является корнем, узлы В, С и D - разветвлениями, а узлы E, F, G, H, и K - листьями.

Следует отметить, что кроме классического изображения, принятого в теории графов, в области информационных технологий применяются альтернативные способы представления корневых деревьев (рисунок 2.2):

- с помощью вложенных скобок;

- уступчатый список;

- десятичная система Дьюи.

Рисунок 2.2 - Альтернативные способы представления корневых деревьев

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

Степенью узла корневого дерева считается число поддеревьев, для которых он является корнем. Для рассмотренного примера корневого дерева: корень А имеет степень 3, степени разветвлений B и D равны 2, а степень разветвления С равна 1. Степени остальных узлов равны 0, потому что они являются листьями, т. е. не имеют поддеревьев.

Уровень узла корневого дерева определяется длиной пути, образованного чередующейся последовательностью узлов и ветвей, который соединяет его с корнем. Длина пути измеряется числом узлов в нем. Для рассмотренного примера корень А имеет уровень 1, разветвления B, C и D имеют уровень 2, а листья E, F, G, H и K - уровень 3. При измерении длины пути числом ветвей в нем, указанные уровни узлов надо уменьшить на 1.

2.2 Понятие бинарного дерева

Важной разновидностью корневых деревьев является класс бинарных деревьев, где каждый узел может иметь не более 2-х потомков. В рекурсивном варианте определения бинарное дерево состоит из корня и 2-х бинарных поддеревьев: левого и правого, причем любое из них может быть пустым. Рисунок 2.3 иллюстрирует изображение бинарного дерева из 8-ми узлов A, B, C, D, E, F, G, H средствами теории графов.

Рисунок 2.3 - Изображение бинарного дерева

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

Рисунок 2.4 - Отличие корневых и бинарных деревьев

Эти бинарные деревья различны по структуре, потому что корень первого из них имеет только левый потомок, а корень второго - только правый. Однако, как деревья они эквивалентны дереву из 2-х узлов А и В, которое также изображено на рисунке 2.4.

В общем случае различие между корневым деревом и бинарным деревом состоит в том, что каждый узел корневого дерева может иметь произвольное число поддеревьев, в то время как любой узел бинарного дерева может иметь только 0, 1 или 2 поддерева и существует различие между левыми и правыми поддеревьями. Несмотря на эти отличия бинарные деревья могут быть использованы для представления корневых деревьев. Возможность такого представления устанавливает следующее естественное соответствие между корневыми и бинарными деревьями. Левая ветвь каждого узла соединяет его с первым узлом следующего уровня, а правая - с другими узлами следующего уровня (братьями). Рисунок 2.5 демонстрирует естественное соответствие 3-х уровневого корневого дерева его бинарному представлению.

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

Рисунок 2.5 - Естественное соответствие между корневым и бинарным деревьями

2.3 Алгоритм поиска по бинарному дереву

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

Рисунок 2.6 - Фрагмент бинарного дерева поиска

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

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

2.4 Алгоритмы обхода бинарных деревьев

Обход бинарного дерева означает систематическое перечисление всех узлов для выполнения необходимой функциональной обработки. Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева. Можно проходить узлы в прямом порядке (сверху-вниз), в симметричном порядке (слева-направо) и, наконец, в концевом порядке (снизу-вверх). Рекурсивные алгоритмы прохождения бинарного дерева по каждому из перечисленных способов включают 3 одинаковых процедуры, где нужно пройти корень поддерева, левое поддерево текущего корня и правое поддерево текущего корня. Направление обхода однозначно определяет последовательность выполнения указанных процедур. Последовательность их рекурсивного вызова для каждого способа прохождения перечислена в таблице 2.1.

Таблица 2.1 - Порядок прохождения узлов для каждого способа обхода

№	Порядок прохождения
	Прямой (префиксный)	Симметричный (инфиксный)	Концевой (постфиксный)
1	Корень поддерева	Левое поддерево	Левое поддерево
2	Левое поддерево	Корень поддерева	Правое поддерево
3	Правое поддерево	Правое поддерево	Корень поддерева

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

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

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

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

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

Рисунок 2.7 - Схема алгоритма поиска элемента

Остальные графические схемы алгоритмов работы с бинарным деревом, а также диаграмма классов представлены в Приложении А.

2.5 Постановка задачи

Разработать Windows-приложение на языке C#, обладающее следующими функциями:

- чтение информации из xml-файла. Количество записей не менее 50;

- вывод исходных данных в виде таблицы;

- возможность демонстрации перегрузок;

- на основе полученных данных сформировать бинарное дерево (ключ - наименование животного, способ обхода - в глубину, с помощью стека);

- визуализация бинарного дерева;

- редактирование информации (добавление, удаление, изменение информации о зоопарке и животном);

- поиск информации по наименованию животного;

- отображение информации о приложении и об авторе.

Создать все необходимые классы. Классы должны содержать следующие элементы:

- описание полей класса;

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

- перегрузку одного из операторов отношения (сравниваются два животных по весу);

- перегрузку постфиксного и префиксного инкремента (инкрементируется вес на килограмм у выбранного животного);

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

2.6 Исходные данные

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

- название зоопарка;

- площадь;

- город;

- страна;

- список животных (наименование животного, вид, вес, возраст, личный номер);

Файл находится в директории: CourseProjectKovaleva\ZooList.xml.

3. Описание разработанного приложения

3.1 Структура программного комплекса

Программа состоит из 4 классов: RealPlanetNode, RealPlanetTree, Animal, Zoo и 9 форм. Каждая форма выполняет свои действия. Листинг программы находится в Приложении Г.

- Класс RealPlanetNode, служит для создание узла бинарного дерева. Структура класса описана в таблице 3.1;

Таблица 3.1 - Элементы класса RealPlanetNode

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
left	Закрытое поле	RealPlanetNode	private	Указатель на левого потомка
right	Закрытое поле	RealPlanetNode	private	Указатель на правого потомка
parent	Закрытое поле	RealPlanetNode	private	Указатель на предка
key	Закрытое поле	String	private	Ключ узла
nodeValue	Закрытое поле	Animal	private	Значение узла
visited	Открытое поле	Int	public	Посещаемость
Value	Свойство	Animal	public	Св-во доступа к значению узла
Key	Свойство	Animal	public	Св-во доступа к ключу узла
LeftNode	Свойство	RealPlanetNode	public	Свойство доступа к указателю на левого потомка
RightNode	Свойство	RealPlanetNode	Public	Свойство доступа к указателю на правого потомка
ParrentNode	Свойство	RealPlanetNode	public	Свойство доступа к указателю на предка
RealPlanetNode (Animal animal)	Конструктор	-	public	Конструктор с параметрами
operator >( RealPlanetNode node1, RealPlanetNode node2)	Статический метод	Bool	public static	Перегруженный оператор больше
operator <( RealPlanetNode node1, RealPlanetNode node2)	Статический метод	Autoinfo	public static	Перегруженный оператор меньше
BuildTreeNode(RealPlanetNode node, ref TreeNode parent)	Метод	Void	void	Построение дерева

- Класс RealPlanetTree, служит для описания бинарного дерева. Элементы класса описаны в таблице 3.2;

Таблица 3.2 - Элементы класса RealPlanetTree

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
AnimalsTree	Поле	List<Animal>	private	Список животных
root	Поле	RealPlanetNode	private	Корневой узел
RealPlanetTree (List<Animal> animals)	Конструктор	-	public	Конструктор c параметрами
Animals	Свойство	List<Animal>	public	Св-во доступа к списку животных
Root	Свойство	RealPlanetNode	public	Св-во доступа к узлу
FindAnimalInList(string key)	Метод	int	public	Поиск индекса животного в списке
Insert(Animal animal)	Метод	void	public	Вставка
InsertLeft(RealPlanetNode node, RealPlanetNode newNode)	Метод	bool	private	Вставка слева
InsertRight(RealPlanetNode node, RealPlanetNode newNode)	Метод	bool	private	Вставка справа
Change(Animal animal)	Метод	void	public	Изменение
Remove(Animal animal)	Метод	void	public	Удаление
GetEndRightNode(RealPlanetNode node)	Метод	RealPlanetNode	private	Получаем самый правый узел
GetMaxAnimalByWeight()	Метод	Animal	public	Животное с максимальным весом

Класс Zoo, является ведущим и служит для создания экземпляра класса Animal. Элементы класса описаны в таблице 3.3;

Таблица 3.3 - Элементы класса Zoo

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
ZName	Свойство	string	public	Название зоопарка
ZSquare	Свойство	string	public	Площадь
ZTown	Свойство	string	public	Город
ZCountry	Свойство	string	public	Страна
Animal	Поле	List<Animal>	public	Список животных
WriteToTable(DataGridViewRow data, bool number)	Метод	void	public	Метод для записи данных в таблицу

- Класс Animal, содержит поля и свойства, описывающие основные характеристики животного. Элементы класса описаны в таблице 3.4;

Таблица 3.4 - Элементы класса Animal

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
AnimName	Свойство	string	public	Наименование животного
AnimSpec	Свойство	Species	public	Вид животного
Weight	Свойство	int	public	Вес животного
SizeOfPopul	Свойство	int	public	Порядковый номер животного
Age	Свойство	int	public	Возраст животного
WriteToTable(DataGridViewRow data)	Метод	void	public	Метод для записи данных в таблицу
Operator>( Animal animal1, Animal animal2)	Статический метод	bool	public static	Перегрузка оператора >
Operator<( Animal animal1, Animal animal2)	Статический метод	bool	public static	Перегрузка оператора <
operator ++(Animal animal)	Статический метод	Animal	public static	Перегрузка инкремента

- Класс MainForm, содержит основную информацию и основные функции для работы с приложением;

- Класс AddAnimalWindow, который служит для добавления зоопарка и животного;

- Класс DelZooWindow, служит для удаления, добавления зоопарков;

- Класс AboutZoo, служит для получения информации о зоопарках;

- Класс SearchEnter, который служит для получения ключа для поиска;

- Класс ReplaceAnim, служит для замены животного;

- Класс ReloadAtitudeOperator, служит для демонстрации перегрузкок;

- Класс ChooseForm, служит для получения ключа для поиска животного с максимальным весом;

- Класс AboutAthor содержит краткую информацию об авторе.

3.2 Описание работы приложения

Для запуска программы следует запустить файл: CourseProjectKovaleva\bin\Debug\ CourseProjectKovaleva.exe.

На рисунке 3.1 изображено главное окно при старте приложения.



Рисунок 3.1 - Окно приложения при его первоначальном запуске

Пункт меню «Файл» содержит:

- «Открыть» - Открывает файл со списком зоопарков и животных;

- «Выход» - Выход из программы.

Пункт меню «Действия» содержит:

- «Увеличение веса» - Увеличение веса животного;

- «Уменьшение веса» - Уменьшение веса животного;

- «Перегрузка операций отношения» - Сравнивает выбранных животных по весу;

- «Животное с максимальным весом» - Показывает максимальный элемент.

Пункт меню «Справка» содержит краткую информацию о программе.

Пункт меню «Об Авторе» содержит краткую информация об авторе.

В приложении Б изложена более подробная краткая информация о проекте, в которой описана вся структура программы. Информация о проекте дает возможность пользователю увидеть, какие действия можно реализовывать, используя это Windows-приложение. Данная информация о проекте кратко описывает все эти действия.

3.3 Описание результатов

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

На рисунке 3.2 изображен файл с исходными данными.

Рисунок 3.2 - Исходные данные для работы с бинарным деревом

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



Рисунок 3.3 - Окно для добавления элемента

В главном окне приложения можно увидеть, что добавление прошло успешно (рисунок 3.4).

Рисунок 3.4 - Добавление нового животного

Как происходит удаление животного (рисунок 3.5 и рисунок 3.6)



Рисунок 3.5 - Список животных до удаления

Рисунок 3.6 - Список животных после удаления

Рассмотрим, как происходит поиск (рисунок 3.7).

Рисунок 3.7 - Поиск животного по заданному ключу

Рассмотрим, как происходит добавление зоопарка. В окне добавления (рисунок 4.3) необходимо выбрать поля для добавления зоопарка. В данном окне появится новый зоопарк (рисунок 4.8):

Рисунок 3.8 - Добавление зоопарка

Рассмотрим удаление животного. Из списка выберем необходимое животное и нажнём кнопку удалить (рисунок 4.9).

Рисунок 3.9 - Удаление животного

Убедимся, что он действительно удален (рисунок 3.10).



Рисунок 3.10 - Список животных после удаления

ЗАКЛЮЧЕНИЕ

Практическим результатом проделанной курсовой работы стала справочно-информационная система «Планета животных», представляющая собой приложение Windows Forms, написанное на языке C# с использованием принципа событийного управления. Разработанное приложение использует абстрактную структуру данных - бинарное дерево поиска. Способ обхода - в глубину. Обход производится с помощью стека.

Для эффективной работы разработанного приложения потребовалось:

? глубоко изучить теоретические сведенья о бинарном дереве поиска;

? грамотно спроектировать архитектуру приложения;

? разработать тип бинарное дерево поиска на языке C#;

? создать удобный интерфейс пользователя;

? создать справочное руководство.

В итоге, разработанная информационно-справочная система может:

? считывать данные из xml-файла;

? добавлять данные вручную, с помощью специальной формы;

? редактировать записи;

? удалять записи;

? эффективно искать записи;

? сохранять записи в xml-формате;

? выполнять дополнительные функции;

? оперативно предоставлять пользователю справочную информацию (с основной частью разработанного справочного руководства можно ознакомиться в приложении Б).

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

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

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

1. Информационные технологии // [Электронный ресурс]. - Режим доступа: http://bibliofond.ru/bp6z. - Дата доступа: 16.05.2014.

2. Основы объектно-ориентированного программирования // [Электронный ресурс]. - Режим доступа: http://object.newmail.ru/bp6y. - Дата доступа: 20.05.2014.

3. Внедрение в объектно-ориентированное программирование // [Электронный ресурс]. - Режим доступа: http://urlid.ru/bp72. - Дата доступа: 20.05.3014.

4. Бинарное поисковое дерево // [Электронный ресурс]. - Режим доступа: http://www.bsu.by/Cache/pdf/177533.pdf- Дата доступа: 22.05.2014.

5. Михалкович, С.С. Основы программирования: Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы / С.С. Михалкович -- Ростов н/Д.: УПЛ ЮФУ, 2007. -- 48 с.

ПРИЛОЖЕНИЕ

Графические схемы проекта

На рисунке А.1 изображена диаграмма разработаного проекта.

Рисунок А.1 - Диаграмма зависимостей классов

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

Рисунок А.2 - Схема алгоритма добавления узла

На рисунке А.3 и А.4 изображена графическая схема алгоритма удаления, который принимает один параметр - удаляемый элемент.



Рисунок А.3 - Схема алгоритма удаления узла

Рисунок А.4 - Схема алгоритма удаления узла

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

1. Введение

Данное руководство указывает:

- сведения о назначении программного продукта и информацию, достаточную для понимания функций программного продукта и его эксплуатации;

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

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

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

2. Подготовка к работе

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

1) перейти в директорию, в которой находится программа (Coursework\bin\Debug);

2) активизировать файл CourseProjectKovaleva.exe;

3) двойным щелчком мыши или нажатием клавиши ENTER на клавиатуре запустить программу.

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

Для того что бы загрузить файл необходимо выбрать пункт меню “Файл” и затем выбрать пункт “Открыть” (рисунок Б.1).



Рисунок Б.1 - Кнопка “Открыть”

После нажатия “Открыть” появляется диалоговое окно с файлами (рисунок Б.2), отображаются только xml-файлы.

Рисунок Б.2 - Диалоговое окно для выбора файла

Если в файле есть некорректные данные, при загрузке они обрабатываться не будут. После этого на экран выведется список всех загруженных элементов (рисунок Б.3 и рисунок Б.4). При этом станут активными все кнопки для работы с данными.



Рисунок Б.3 - Вид окна при открытии файла (список животных)

Рисунок Б.4 - Вид окна при открытии файла (зоопарки)

3. Описание операций

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

- добавление записей;

- удаление записей;

- редактирование записей;

- поиск;

- и т.д.

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

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

После нажатия на кнопку откроется окно для добавления элементов (рисунок Б.5)

Рисунок Б.5 - Окно для добавления элементов

Для добавления нового зоопарка, необходимо заполнять соответствующие поля по добавлению зоопарка. Для добавления животного необходимо выбрать зоопарк (выделить строку в таблице зоопарков) и заполнить поля по добавлению животного (рисунок Б.6 и Б.7).

Рисунок Б.6 - Вид формы элементов



Рисунок Б.7 - Вид формы для добавления животного

Наименование операции - «Замена существующего элемента». Для редактирования записи, необходимо нажать соответствующую кнопку на панели элементов. После этого откроется новое окно для редактирования (рисунок Б.8).

Рисунок Б.8 - Вид формы для редактирования записи о животном

Наименование операции - «Удаление элемента». Для удаления записи, необходимо выбрать в таблице животных необходимое животное и нажать кнопку «Удалить», которая находится на панели элементов (рисунок Б.9).



Рисунок Б.9 - Вид формы для удаления животного

Чтобы перейти к удалению зоопарка необходимо обратиться к пункту меню «Зоопарки», затем выбрать «Информация/Удалить». После чего откроется окно для удаления зоопарка (рисунок Б.10 и Б.11).

Рисунок Б.10 - Переход для удаления зоопарка

Рисунок Б.11 - Вид формы для удаления зоопарка

Наименование операции - «Поиск». Также в приложении, для быстрого нахождения нужной нам записи, предусмотрен поиск. Поиск вызывается, так же нажатием соответствующей клавиши. При выборе пункта меню “Поиск”, открывается новое окно, в котором вводится элемент поиска (рисунок Б.12).

Рисунок Б.12 - Вид формы для поиска записи

Затем появится сообщение о найденном элементе (рисунок Б.13).

Рисунок Б.13 - Вид формы после поиска записи

Так же в программе предусмотрены дополнительные функции.

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



Рисунок Б.14 - Вид формы подробной информации о животном и о зоопарке

Наименование операции - «Перегрузка операторов». Также предусмотрены функции перегрузки операторов, рассмотрим подробнее далее. Чтобы перейти к демонстрации перегруженных операторов, необходимо обратиться к пункту меню «Действия», и выбрать необходимую перегрузку (рисунок Б.16)

Рисунок Б.16 - Выбор необходимой перегрузки

Итак, при выборе операции «Увеличение веса» (операции инкремента) будет добавлен килограмм к весу животного (рисунок Б.17 и Б.18).



Рисунок Б.17 - Демонстрация перегрузки инкремента

Рисунок Б.18 - Результат перегрузки инкремента

При выборе операции «Уменьшение веса» (операции декремента) будет отнят килограмм от веса животного. Принцип работы аналогичен операции «Увеличение веса». При выборе операции «Перегрузка операции отношения» появится форма для выбора животных. Животные будут сравниваться по весу. Затем появится сообщение, показывающее результат сравнения (рисунок Б.19 и Б.20).

Рисунок Б.19 - Окно для выбора животных



Рисунок Б.20 - Демонстрация перегрузки оператора отношения

Наименование операции - «Поиск максимального объекта». Одной из последних функция данной информационной системы является нахождение максимального элемента. Для того что бы обратиться к данной функции необходимо нажать “Действия” далее “Животное с максимальным весом”, на экран будет выведено окно, в котором будет выведен максимальный элемент, а также выделена строка в таблице, содержащая данный элемент (рисунок Б.21).

Рисунок Б.22 - Демонстрация поиска максимального элемента в массиве объектов

Также на протяжении всей программы происходит визуализация данных с помощью бинарного дерева. Она нужна для того, чтобы пользователь мог увидеть, как хранятся данные. В данной работе предусмотрена визуализация с помощью TreeView (рисунок Б.23).



Рисунок Б.23 - Визуальное представление хранения данных(TreeView)

В программе также предусмотрена краткая справочная информация (рисунок Б.24 и Б.25) и информация об авторе. Вызвать которые можно через пункт меню.

Рисунок Б.24 - Демонстрация справки



Рисунок Б.25 - Информация о разработчике приложения

5. Аварийные ситуации

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

Аварийные ситуации могут возникать:

? при нарушении порядка выполнения операций;

? при сбое оборудования.

При возникновении неописанных ошибок необходимо предоставить разработчику подробную информацию об ошибке.

Руководство программиста

1. Характеристики программы

Приложение написано на языке программирования C# с использованием платформы .NET Framework 4.5.1.

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

2. Обращение к программе

Управление содержимым осуществляется через пользовательский интерфейс приложения.

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

1) Перейти в каталог CourseProjectKovaleva\bin\Debug\.

2) Запустить CourseProjectKovaleva.exe.

Проект состоит из следующих элементов:

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

? папка Classes, где содержатся все классы, используемые для разработки программы.

Завершение программы осуществляется по желанию пользователям путем выхода из неё.

3. Входные и выходные данные

Программа получает входные данные:

? в формате xml-файла;

? через визуальный интерфейс программы.

Программа генерирует следующую выходную информацию:

? измененные в результате выполнения программы данные в формате xml.

4. Сообщения

В ходе выполнения программы, программисту выдаются сообщения.

При вводе некорректных данных появится окно с сообщением «Неверно введены данные!». При появление такого окна следует нажать «ОК» и ввести данные ещё раз.

Листинг классов проекта

Г.1 MainForm.cs

namespace CourseProjektKovaleva