Разработка автоматизированной информационной системы "Пиццерия"

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЕРЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ П. О. СУХОГО

Факультет автоматизированных и информационных систем

Кафедра: «Информационные технологии»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине: «Объектно-ориентированное программирование»

на тему: «Разработка автоматизированной информационной системы «Пиццерия»

Исполнитель: студентка группы ИТ-22

Бажкова А.С.

Руководитель:преподаватель

Кухаренко А.А.

Гомель 2014



ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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



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

1.1 Развитие технологии и языков программирования

Появления вычислительных машин программирование, как область знания, находилось в зачаточном состоянии. Первые программы создавались посредством переключателей на панели компьютера. Очевидно, что такой способ подходил только для небольших программ. Затем программы стали писать на языке машинных команд, а изобретение ассемблера позволило писать уже сравнительно длинные программы. Следующий шаг был сделан в 1950 году, когда был создан первый язык программирования высокого уровня Фортран.

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

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

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

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

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

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

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

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

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

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

1.3 Основные понятия объектно-ориентированного программирования

В основе объектно-ориентированного язык программирования лежат два основных понятия: объект и класс.

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

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

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

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

1.4 Основные принципы объектно-ориентированного программирования

Объектно-ориентированное программирование базируется на трех основных принципах:

инкапсуляция;

наследование;

полиморфизм.

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

Наследование (inheritance) - один из самых важных механизмов в ООП. Любой класс может наследоваться от другого класса, а это значит, что он будет иметь все те члены, что и класс, от которого он унаследован. В терминологии ООП класс, от которого наследуется (порождается) другой класс, называется родительским или базовым классом. Классы в C# могут непосредственно наследоваться только от одного базового класса, хотя у того базового класса может быть собственный базовый класс, и т.д.Механизм наследования позволяет расширять или создавать конкретные классы от одного более общего базового класса.

Полиморфизм. В значительной степени мощь объектно-ориентированного программирования вытекает из применения различных форм полиморфизма. Слово полиморфизм греческого происхождения и означает приблизительно «много форм».

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

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

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

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

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

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

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

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

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

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

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



2. ИСПОЛЬЗОВАНИЕ БИНИРНОГО ДЕРЕВА ДЛЯ ПОИСКА ИНФОРМАЦИИ.

2.1 Бинарное дерево

Бинарное дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый - корнем дерева,и,возможно,другиеэлементы.Эти элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом.Такие подмножества называются левым и правым поддеревьями исходного дерева.Каждый элемент бинарного дерева называется узлом.Будем предполагать,что каждый узел двоичного дерева имеет идентифицирующий его ключ.Нарис.2.1 приведен пример бинарного дерева,у которого 9 узлов,A - корень дерева,B - корень левого поддерева,C - корень правого поддерева. Каждый узел двоичного дерева может иметь 0,1 или 2 поддерева. Так на рис. 2.1 левое поддерево с корнем C исходного бинарного дерева пусто[2].

Рисунок2.1 - Бинарное дерево



Если X - корень бинарного дерева и Y - корень его левого или правого поддерева, то говорят,что X - отец Y,а Y - левый или правый сынX.В примере на рис.2.1 A - отец для B и C,B - левый сын A,E - отец G,G - его левый сын.Узел, не имеющий сыновей,называется листом.В примере 2.1 листья: D,G,H,I. Два узла являются братьями,если они сыновья одного отца (B, C - братья). Глубина бинарного дерева определяется длиной самого длинного пути от корня к листу дерева (на рисунке 2.1 глубина дерева равна 3).

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

Бинарное дерево является рекурсивной структурой,поскольку каждое его поддерево само является бинарным деревом и,следовательно,каждый его узел в свою очередь является корнем дерева.Ознакомившись с концепцией бинарного дерева, можно заметить,что не все деревья позволяют организовать эффективный поиск по ним.Такие деревья называются вырожденными и некоторые из них представлены на рисунке 2.2.[2]

Рисунок2.2 - Вырожденное бинарное дерево

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

Описание множеств в виде списков позволяет использовать для множеств целевое утверждение, принадлежит определенное ранее для списков.

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

Рисунок2.3 - Упорядоченное бинарное дерево

Упорядочение приводит не к единственному варианту представления множества с помощью дерева.Будем называть линейным представление такого вида,как на рис. 2.1.4,и сбалансированным - такое, как на рис. 2.1.3[2].

Рисунок2.4 - Линейное представление

2.2 Способы обхода бинарного дерева

Процедуру перемещения по дереву называют обходом (traversal).Существуют четыре основных алгоритма обхода-обходом в ширину (pre-order), симметричным обходом(in-order),обходом в глубину(post-order) и обходом по уровням (level-order).Последний алгоритм - обход по уровням - наиболее прост для визуального представления,но наиболее сложен для кодирования.Этот алгоритм предполагает посещение каждого из узлов,начиная с корневого,и просмотр узлов сверху вниз,уровень за уровнем. На каждом уровне мы посещаем узлы слева направо.Таким образом,мы посещаем корневой узел,левый дочерний узел корневого узла, правый дочерний узел корневого узла,левый дочерний узел левого дочернего узла корневого узла,правый дочерний узел левого дочернего узла корневого узла и т.д.

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

В качестве примера рассмотрим следующее дерево, представленное на рисунке 2.5:

Рисунок2.5-Бинарное дерево

Обход дерев в ширину:A,B,C,D,E,F,G,H,I,J;

Симметричный обход дерева:D,H,B,E,A,I,F,J,C,G;

Обход дерева в глубину:A,B,D,H,E,C,F,I,J,G.

2.3 Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

FIND(K) - поиск узла,в котором хранится пара (key, value) с key = K;

INSERT(K,V) - добавление в дерево пары (key, value) = (K, V);

REMOVE(K) - удаление узла, в котором хранится пара (key, value) с key = K;

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

«Телефонная книжка» - хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека, и операцией добавления новой записи;

Domain Name Server - хранилище пар (доменное имя, IP адрес)с операциями модификации и поиска;

Names pace - хранилище имен переменных с их значениями ,возникающее в трансляторах языков программирования.

По сути, двоичное дерево поиска - это структура данных, способная хранить таблицу пар (key,value) и поддерживающая три операции: FIND,INSERT,REMOVE.

Кроме того,интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева:I NFIX_ TRAVERSE,PREFIX_TRAVERSEиPOSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

2.3.1 Поиск элемента

Дано:деревоТиключK.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да,то вернуть ссылку на этот узел.

Алгоритм:

Если дерево пусто, сообщить,что узел не найден, и остановиться;

Иначе сравнить K со значением ключа корневого узла X;

Если K=X, выдать ссылку на этот узел и остановиться;

Если K>X,рекурсивно искать ключ K в правом поддереве Т;

Если K<X,рекурсивно искать ключ K в левом поддереве Т.

2.3.2 Добавление элемента

Дано: деревоТипара(K,V).

Задача: вставить пару(K,V) в дерево Т(при совпадении K,заменить V).

Алгоритм:

Если дерево пусто,заменить его на дерево с одним корневым узлом((K,V), null, null) и остановиться;

Иначе сравнить K с ключом корневого узла X;

Если K>X,циклически добавить (K,V) в правое поддерево Т;

Если K<X,циклически добавить(K,V)в левое поддерево Т;

еслиK=X,заменить V текущего узла новым значением. (хотя можно и организовать список значений V, но это другая тема).

2.3.3 Удаление узла

Дано: дерево Т с корнем n и ключом K.

Задача:удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

Если дерево T пусто,остановиться;

Иначе сравнить K с ключом X корневого узла n.

Если K>X,циклически удалить K из правого поддереваТ;

если K<X,циклически удалить K из левого поддереваТ;

если K=X, то не обходимо рассмотреть три случая;

если обоих детей нет,то удаляем текущий узел и обнуляем ссылку на него у родительского узла;

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

если оба ребёнка присутствуют, то;

если левый узел m правого поддерева отсутствует (n->right->left);

копируем из (8)в(4)поляK,V и ссылку на правый узел;

иначе;

возьмем самый левый узел m,правого поддерева n->right;

скопируем данные (кроме ссылок на дочерние элементы)из m в n;

рекурсивно удалим узел m.



2.3.4 Обход дерева

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция - INFIX_TRAVERSE - позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f,операндом которой является адрес узла. Эта функція обачно работает только с парой (K,V),хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для лівого поддерева,потом запускает данню функцию для корня,потом запускает себя для правого поддерева.

INFIX_TRAVERSE:

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

Если дерево пусто, остановиться;

иначе;

рекурсивно обойти левое поддерево Т;

применить функцию f к корневому узлу;

рекурсивно обойти правое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей.Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева,приведённого в начале статьи.

2.3.5 Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <K0 и ?K0.



2.3.6 Объединение двух деревьев в одно

Обратная операция:есть два дерева поиска,у одного ключи<K0, у другого?K0.Объединить их в одно дерево.

У нас есть два дерева: T1(меньшее) и T2 (большее).Сначала нужно решить, откуда взять корень:изT1 или T2.Стандартного метода нет,возможные варианты:

Взять наугад;

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

2.4 Балансировка дерева

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

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

Для балансировки дерева применяется операция "поворот дерева".Поворот налево выглядит так:

Было Left(A)=L,Right(A)=B,Left(B)=C,Right(B)=R;

Поворот меняет местами A и B,получая Left(A)=L,Right(A)=C,Left(B)=A,Right(B)=R;

Также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.

Поворот на право выглядит также, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое(+1или-1)влияние на глубины всех затронутых поддеревьев.

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

Оба они требуют дополнительной информации в узлах-1 биту красно-черного или знаковое число у АВЛ.

Красно-черное дерево требует<=2 поворотов после добавления и<=3 после удаления, но при этом худший дисбаланс может оказаться до 2раз (самый длинный путь в 2 раза длиннее самого короткого).

АВЛ-дерево требует <=2 поворото в после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более,чем на 1).



3. ОПИСАНИЕ РАЗРАБОТАННОГО ПРИЛОЖЕНИЯ

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

Разработать Windows-приложение на языке С#, выполняющее следующие действия:

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

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

построение для исходных данных бинарного дерева;

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

редактирование исходных данных (вставка, удаление, замена) с внесением соответствующих изменений в бинарное дерево;

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

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

Для хранения данных нужно использовать структуру данных - бинарное дерево. В качестве ключа взять название пиццы. Обход осуществлять в глубину. Создать класс «Пицца», который будет храниться в узле дерева. Полное описание классов и его компонентов показано в приложении А. Класс должен содержать следующие элементы:

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

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

перегрузку одного из операторов отношения;

перегрузку одного из бинарных операторов;

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

предусмотреть обработку и инициализацию исключительных ситуаций;

реализовывать интерфейс IComparable.

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

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

Рисунок 3.1 - Пример записи из XML документа

В теге Tiptrain содержится тип поезда (перечисление), в теге Number - номер поезда, в теге Arrival - пункт отправления, в теге Departure - пункт прибытия, в теге Timearrival - время отправления, в теге Timedeparture - время прибытия. Детально класс Train описан в приложении В.

3.3 Реализация алгоритмов основных функций бинарного дерева

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

Рисунок 3.2 - Блок-схема поиска узла

Функция добавления на входе получает объект класса Pizza. Начинается цикл, в котором для узла поезда ищется подходящее место. Затем, когда находится, создается новый узел и происходит выход. Блок-схема добавления представлена на рисунке 3.3.

Рисунок 3.3 - Блок-схема добавления узла

Функция редактирования на входе получает ключ и объект класса Train. Внутри функции сначала происходит вызов функции удаления и потом вызов функции добавления с соответствующими значениями на входных значениях функций. Блок-схема редактирования представлена на рисунке 3.4.



Рисунок 3.4 - Блок-схема редактирования узла

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



Рисунок 3.5 - Блок-схема удаления узла



ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

Развитие технологии и языков программирования // [Электронный ресурс]. - Режим доступа: http://saisa.chat.ru/oop/oop3.html.- Дата доступа: 12.04.2014.

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

Основные понятия ООП // [Электронный ресурс]. - Режим доступа: http://www.0zd.ru/programmirovanie_kompyutery_i/ponyatie_obektno-orientirovannogo.html. - Дата доступа: 19.05.2014.

Основные концепции объектно-ориентированного программирования. Поля и свойства // Мехатроника [Электронный ресурс]. - 2011. - Режим доступа: http://mehatronics.ru/2011/01/основные-концепции-ооп-поля-и-свойства/. - Дата доступа: 22.05.2014.

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

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

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

ПРИЛОЖЕНИЕ А

(Справочное)

Структура проекта

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

ПРИЛОЖЕНИЕ Б

Описание класса Form1

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

Таблица Б.1 - Элементы классаForm1

Имя	Вид элемента	Тип	Специ-фикатор	Описание
поискToolStripMenuItem_Click	метод	void	private	открытие формы поиска
выходToolStripMenuItem_Click	метод	void	private	закрытие приложения
открытьToolStripMenuItem_Click	метод	void	private	вызывает окно открытия файла
openFileDialog1_FileOk	метод	void	private	вызывает десериализацию данных
сохранитьToolStripMenuItem_Click	метод	void	private	вызывает окно сохранения файла
saveFileDialog1_FileOk	метод	void	private	вызывает сериализацию данных
новыйToolStripMenuItem_Click	метод	void	private	вызывает очистку всех данных
поискМаксимальногоToolStripMenuItem_Click	метод	void	private	выводит сообщение с максимальным элементом
правкаToolStripMenuItem_Click	метод	void	private	вызывает окно формы редактирования
перегрузкиToolStripMenuItem_Click	метод	void	private	вызывает окно формы перегрузок
обАвтореToolStripMenuItem_Click	метод	void	private	выводит сообщение об авторе
оПрограммеToolStripMenuItem1_Click	метод	void	private	выводит сообщение о программе
tree	поле	BinaryTree	public	хранит дерево
trainlist	поле	List<Train>	private	хранит коллекцию поездов



ПРИЛОЖЕНИЕ В

(Справочное)

Описание класса Pizza

Главный класс приложения - Train. Класс Train содержит в себе номер, тип, пункт прибытия, пункт отправления, время прибытия, время отправления, коллекцию вагонов. В таблице В.1 описаны элементы всех вышеперечисленных классов.

Таблица В.1 - Элементы классаTrain

Имя	Вид элемента	Тип	Специ-фикатор	Описание
number	поле	int	private	номер поезда
tiptrain	поле	Tip_train	private	тип поезда
arrival	поле	string	private	пункт отправления
departure	поле	string	private	пункт прибытия
timearrival	поле	string	public	время отправления
timedeparture	поле	string	public	время прибытия
Tiptrain	свойство	Tip_train	public	возвращает и устанавливает тип поезда
Number	свойство	int	public	возвращает и устанавливает номер поезда
Arrival	свойство	string	private	возвращает и устанавливает пункт отправления поезда
Departure	свойство	string	private	возвращает и устанавливает пункт прибытия поезда
Timearrival	свойство	string	private	возвращает и устанавливает время отправления поезда
Timedeparture	свойство	string	private	возвращает и устанавливает время прибытия поезда
operator +	Перегруженный оператор	Train	public	слаживает номера поездов
operator<	Перегруженный оператор	bool	public	сравнивает номера поездов



ПРИЛОЖЕНИЕ Г

(Обязательное)

Листинг класса Binary Tree

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

using System.Xml;

using System.Xml.Serialization;

using System.IO;

using System.Collections;

using System.Xml.Linq;

namespace WindowsApplication1

{

public classBinaryTree

{

public staticList<Train>trainlist = newList<Train>();

public Nodenode;

public staticQueue<Node> queue = newQueue<Node>();

public BinaryTree()

{

}

public BinaryTree(Train s)

{

node = newNode(null, s);

}

public voidBuildTreeFromList()

{

bool flag = true;

Node main = node;

int i;

for (i = 1; i <trainlist.Count; i++)

{

while (flag)

{

if (trainlist[i].Number <= node.Train.Number)

{

if (node.Left != null)

node = node.Left;

else

{

node.Left = newNode(node, trainlist[i]);

flag = false;

node = main;

}

}

if ((trainlist[i].Number >node.Train.Number) && flag)

{

if (node.Right != null)

node = node.Right;

else

{

node.Right = newNode(node, trainlist[i]);

flag = false;

node = main;

}

}

}

flag = true;

}

}

Public NodeBuildBranchFromList(List<Train>trainlist)

{

if (trainlist.Count == 0)

return (null);

Nodenode = newNode(null, trainlist[0]);

node.Right = null;

node.Left = null;

bool flag = true;

Node main = node;

int i;

for (i = 1; i <trainlist.Count; i++)

{

while (flag)

{

if (trainlist[i].Number <= node.Train.Number)

{

if (node.Left != null)

node = node.Left;

else

{

node.Left = newNode(node, trainlist[i]);

flag = false;

node = main;

}

}

if ((trainlist[i].Number >node.Train.Number) && flag)

{

if (node.Right != null)

node = node.Right;

else

{

node.Right = newNode(node, trainlist[i]);

flag = false;

node = main;

}

}

}

flag = true;

}

return node;

}

public TrainMaxItem(List<Train>trainlist)

{

Train max = newTrain();

max = trainlist[0];

for (int i = 1; i <trainlist.Count; i++)

if (max <trainlist[i])

max = trainlist[i];

return max;

}

Public List<Train>ListFromNode(Node del)

{

List<Train> list = newList<Train>();

Rekursia(del, list);

return (list);

}

public List<Train>Rekursia(Node n, List<Train> list)

{

if (n.Left != null)

{

n = n.Left;

list.Add(n.Train);

Rekursia(n, list);

n = n.Parent;

}

if (n.Right != null)

{

n = n.Right;

list.Add(n.Train);

Rekursia(n, list);

n = n.Parent;

}

return list;

}

public Node Search(int key, refbool flag, Node top)

{

queue.Clear();

queue.Enqueue(top);

do

{

top = queue.Dequeue();

if (top.Train.Number == key)

{

flag = true;

return (top);

}

if (top.Left != null)

queue.Enqueue(top.Left);

if (top.Right != null)

queue.Enqueue(top.Right);

}

while (queue.Count != 0);

return (null);

}

public voidAddItem(TrainnewTr)

{

Node main = node;

while (true)

if (newTr.Number<= node.Train.Number)

if (node.Left != null)

node = node.Left;

else

{

node.Left = newNode(node, newTr);

node = main;

return;

}

else

if (node.Right != null)

node = node.Right;

else

{

node.Right = newNode(node, newTr);

node = main;

return;

}

}

public voidChangeItem(int key, TrainnewTr)

{

DeleteItem(key);

AddItem(newTr);

}

public boolDeleteItem(int key)

{

bool flag = false;

Node main = newNode();

main = node;

NodebuildBranchFromList = newNode();

List<Train> list = newList<Train>();

if (node != null)

node = this.Search(key, ref flag, node);//находимузел

if (node != null)

flag = true;

if (flag)

{

list = this.ListFromNode(node);//составляем коллекцию из потомков узла

buildBranchFromList = this.BuildBranchFromList(list);//строим ветку из коллекции

if (node.Parent != null)

{

if (node.Parent.Left == node)

{

node = node.Parent;

if (buildBranchFromList != null)

{

buildBranchFromList.Parent = node;

node.Left = buildBranchFromList;

}

elsenode.Left = null;

}

elseif (node.Parent.Right == node)

{

node = node.Parent;

if (buildBranchFromList != null)

{

buildBranchFromList.Parent = node;

node.Right = buildBranchFromList;

}

elsenode.Right = null;

}

node = main;

}

else

{

node = buildBranchFromList;

}

}

else node = main;

return flag;

}

public voidTreeToDatagrid(Node temp, refint i, Form1 f)

{

if (temp != null)

{

f.dataGridView1.RowCount++;

f.dataGridView1[0, i].Value = temp.Train.Number;

f.dataGridView1[1, i].Value = temp.Train.Tiptrain;

f.dataGridView1[2, i].Value = temp.Train.Arrival;

f.dataGridView1[3, i].Value = temp.Train.Departure;

f.dataGridView1[4, i].Value = temp.Train.Timearrival;

f.dataGridView1[5, i].Value = temp.Train.Timedeparture;

i++;

if (temp.Right != null)

{

temp = temp.Right;

TreeToDatagrid(temp, ref i, f);

temp = temp.Parent;

}

if (temp.Left != null)

{

temp = temp.Left;

TreeToDatagrid(temp, ref i, f);

temp = temp.Parent;

}

}

}

public voidTreeToTreeView(Form1 f, Node temp)

{

if (temp.Left != null)

{

temp = temp.Left;

f.treeView1.SelectedNode.Nodes.Add(Convert.ToString(temp.Train.Number));

f.treeView1.SelectedNode = f.treeView1.SelectedNode.Nodes[0];

TreeToTreeView(f, temp);

temp = temp.Parent;

f.treeView1.SelectedNode = f.treeView1.SelectedNode.Parent;

}

if (temp.Right != null)

{

temp = temp.Right;

f.treeView1.SelectedNode.Nodes.Insert(0, Convert.ToString(temp.Train.Number));

f.treeView1.SelectedNode = f.treeView1.SelectedNode.Nodes[0];

TreeToTreeView(f, temp);

temp = temp.Parent;

f.treeView1.SelectedNode = f.treeView1.SelectedNode.Parent;

}

}

}

}



ПРИЛОЖЕНИЕ Д

(Справочное)

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

На рисунке Д.1 изображено главное меню программы. Изначально пользователю доступны не все функции, потому что данные не были инициализированы.

Рисунок Д.1 - Главное окно программы

Чтобы использовать программу нужно:

добавить данные для работы с ними;

открыть заранее подготовленный файл.

Чтобы добавить данные необходимо в пункте меню «Файл» выбрать «Новый».

Чтобы открыть файл необходимо в пункте меню «Файл» выбрать «Открыть» (рисунок Д.3). Далее появляется диалоговое окно выбора файла, где необходимо выбрать нужный XML файл.

При успешном чтении файла в главном окне отображаются считанные записи в виде таблицы (рисунок Д.2).

Рисунок Д.2 - Отображение считанных данных в главном окне программы

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

сохранение записей в новый файл;

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

изменение записи;

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

поиск записей по ключу.

Чтобы сохранить записи в новый файл нужно в пункте меню «Файл» выбрать пункт «Сохранить». Затем необходимо указать путь в диалоговом окне сохранения.

Для добавления записи необходимо нажать на пункт «Редактирование» ввести данные и нажать добавить (рисунок Д.3).



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

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

Для изменения записи необходимо ввести номер поезда и нажать найти. Если такой поезд есть, то поля для изменения записи заполнятся, иначе появится сообщение, что поезд не найден. Далее нужно изменить необходимые поля и нажать «Заменить» Если будет введен поезд с уже существующим номером, то появится сообщение (рисунок Д.4).

Рисунок Д.4 - Изменение записи



Для удаления записи нужно ввести номер удаляемого поезда и нажать «Удалить» (рисунок Д.5).

Рисунок Д.5 -Удаление записи

В случае если введенные символы или поезд не найден, то появятся соответствующие сообщение.

Для того чтобы осуществить поиск записей по ключу необходимо в пункте меню «Просмотр» выбрать «Поиск» и ввести номер поезда и нажать «Искать» (рисунок Д.6).

Рисунок Д.6 - Элемент интерфейса для поиска

В программе так же есть следующие функции, которые находятся во вкладке «Просмотр»:

поиск максимального объекта (рисунок Д.7);

перегрузки (рисунок Д.8).

Рисунок Д.7 - Поиск максимального объекта

Рисунок Д.8 - Перегрузки

В пунктах «О программе» и «Об авторе» находится соответствующая информация (рисунок Д.9), (рисунок Д.10).

Рисунок Д.9 - О программе

информационный поиск бинарный дерево



Рисунок Д.10 - Об авторе

Для завершения работы приложения необходимо выбрать пункт меню «Файл» - «Выход».

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