Търсачка

Банер

Дипломни Информатика, ИТ Създаване на програмна система за обработка на данни с дървовидно представяне


Дипломна работа, 119 стандартни страници, съдържа таблици, схеми, формули, програма, липсва литература
Цена: 4.80лв.
Безплатно
Спестявате: 100.00%
Задайте въпрос за този материал

v:* {behavior:url(#default#VML);} o:* {behavior:url(#default#VML);} w:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 21 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

СЪДЪРЖАНИЕ

ВЪВЕДЕНИЕ................................................................................................................................................... 4

Основна концепция за дървовидната структура................................................................ 4

Терминология, свързана със структурата дърво................................................................ 6

Основни термини................................................................................................................................. 6

Типове дървета................................................................................................................................... 9

Среда за разработка на информационната система......................................................... 9

АЛГОРИТМИ............................................................................................................................................... 12

Вмъкване на възел в двоично дърво......................................................................................... 12

Изтриване на възел от двоично дърво..................................................................................... 13

ПРОГРАМНА РЕАЛИЗАЦИЯ.................................................................................................................. 14

Методи за представяне на дърветата.................................................................................... 14

“Големите” възли............................................................................................................................. 14

Дъщерни списъци.............................................................................................................................. 15

“Напредваща звезда”...................................................................................................................... 16

Обхождане на дървета.................................................................................................................... 20

Сортирани дървета............................................................................................................................ 26

Добявяне на елементи...................................................................................................................... 26

Премахване на елементи................................................................................................................. 28

Обхождане на сортирани дървета............................................................................................ 32

Дървета с нишки (прошити дървета)........................................................................................ 33

Квадратични дървета...................................................................................................................... 37

РЪКОВОДСТВО ЗА РАБОТА................................................................................................................ 43

Стартиране на системата............................................................................................................. 43

Стартиране на алгоритмите........................................................................................................ 43

Методи за представяне на дървета.......................................................................................... 44

Метод на “Големите възли”......................................................................................................... 44

Метод на дъщерните списъци...................................................................................................... 44

Метод на “Напредващата звезда”............................................................................................. 45

Обхождане на дървета.................................................................................................................... 46

Обхождане на двоично дърво....................................................................................................... 46

Обхождане на дърво, представено по метода на дъщерните списъци........................... 47

Сортирани дървета............................................................................................................................ 48

Квадратични дървета...................................................................................................................... 48

ПРИЛОЖЕНИЕ............................................................................................................................................ 50

Изходен код на програмата.......................................................................................................... 50


ВЪВЕДЕНИЕ

Основна концепция за дървовидната структура

Дървото е йерархична структура от данни, в която данните са подредени по ключовите стойности на елементите. Един елемент от дървото има връзка от типа “едно към много” с другите елементи за разлика от свързания списък, където връзката е “едно към едно”.

Дървото запазва йерархичната взаимна връзка между много елементи. Към този тип стрултури се отнасят пирамидите, приоритетните опашки и игровите дървета.

Дървото за търсене (балансирано) съчетава в себе си средната ефективност на двоичното търсене с ефективността на операциите по вмъкване и изтриване в свързания списък.

Дървовидната структура е нелинейна структура на събития и информация. Това означава, че от произволна точка в дървото може да има нула, една или няколко възможности за напредване. Както се вижда от диаграмите на фиг. 1-1, дървото е един от няколкото начина за представянето на йерархична организация.

Йерархичното структуриране на данните е естествен и полезен за практиката процес. Примери за това има в изобилие. Различните правителствени, образователни, военни и стопански организации имат йерархична структура. Родословното дърво описва произхода на една фамилия през няколко поколения наад, като се създава нелинейна структура, организирана оп стойност на ключа (име) и време на опстъпване (дата на раждане или сключване на брак). На практка повечето масиви с информация са организирани на някакъв йерархичен принцип, като по-сложните компоненти се разбиват на по-прости части. Като пример за йерахична структура на фиг. 1-2 е дадена примерна структура на технически университет.

Йерархичната организация може да описва и действия. Дървовидната структура на фиг. 1-3 описва схемата на турнир по баскетбол между 16 отбора с елиминации. “Деиствието” (мачовете между отборите) се развива отляво надясно.

Терминология, свързана със структурата дърво

Основни термини

Възел, клон

Елементите в дървото се наричат възли. На диаграмите те се означават с кръгчета, които се свързват с помощни линии, наречени ребра или клони. Клонът отразява връзката между два възела, като между два възела може да има само една връзка. В кръгчето обикновено се показва стойността на ключа на възела. На фиг. 1-4 са показани различни дървовидни структури.

Празно дърво

Дърво, което не съдържа възли, се нарича празно дърво.

Ориентирано дърво

Ориентираното дърво е или празно дърво, или запълнено, за което важи следното:

q Конкретен възел е обявен за корен на дървото.

q Останалите възли са разделени на несвързани множества – поддървета, всяко от които представлява ориентирано дърво.

Обиновено под дърво се разбира ориентирано дърво.

Корен на дърво

В непразното ориентирано дърво един от възлите е обявен за корен на дървото. Ориентираните дървета обикновено растат надолу или настрани от корена. Произволно дърво или свободно дърво обикновено няма корен. На фиг. 1-4 и двата възела, означени с 40, са корени.

Път, насочен път, дължина на път

Маршрутът от един възел до друг се нарича път. Между възел А и възел B съществува път, ако всяка двойка възли между тях е свързана с клон. В ориентираното дърво всеки път е насочен, т.е. разрешено е движението само в посока от корена към листата. Броят на възлите по пътя определя неговата дължина.

Цикъл

Път, който започва и завършва в един и същи възел, се нарича цикъл. Дървото не трябва да съдържа цикли.

Родителски възли, възли-наследници, възли-поколение

Ако един клон върви от възел А към възел B, то А е родител на B, а В – наследник на А. Възли В, С и D на фиг. 1-4 са братя – поколението на възел А.

Степен, листо, вътрешен възел

Степента (изходящата степен) на един възел се изразява с броя на наследниците на този възел. Възел със степен 0 (без наследници) се нарича листо или краен възел. Възел със степен 1 или по-голяма се нарича вътрешен възел. Възли В, С и D, 20, 50, 70, z, 7, 30, 55 и 80 на фиг. 1-4 са листа, а всички останали възли са вътрешни.

Прародител и потомък

В ориентираното дърво всички възли по пътя от възел А към В (с изключение на А) са потомци на А, а възел А е прародител на всички тези възли. В ориентираното дърво коренът е прародител на всички останали възли, т.е. всички некоренни възли са потомци на корена, защото от корена до всеки друг възел в дървото има път. На фиг. 1-4 възли y и z са потомци на x, а 40 и 60 –прародители на 70 в съответните дървета.

Поддърво

В ориентираното дърво поддървото се състои от конкретен възел (корен на поддървото) и неговите наследници. Всяко подърво в ориентираното дърво е само по себе си ориентирано дърво. На фиг. 1-5 е показано дърво с 4 от възможните поддървета, означени със затъмнени триъгълници.


Ниво, височина

Дадена хоризонтална редица (респективно вертикална, ако развитието на дървото е в хоризонтална посока) от възли в дървото се нарича ниво. Всяко ниво се означава чрез нарастващи целочислени стойности. Коренът е на ниво 1 (в накои книги на ниво 0). На фиг. 1-5 възел F е на ниво 3, а възел I – на ниво 4. Височината на дървото (лил поддървото) се изразява с броя на възлите по най-дългия път от корена на дървото до възлите-листа. Височината на дървото на фиг. 1-5 е 4, а на поддървото с корен J – 2.

Обхождане на дърво

Операцията, свързана с посещение и обработка на възлите в дървото по определен ред, се нарича обхождане на дървото. В ориентираното дърво обхожданията са от корена към листата, по прав и обратен ред, от листата към корена и по нива.

Типове дървета

Съществуват няколко основни типове дървета.

Произволно дърво

Крайно множество от възли, свързани с клони, което не съдържа цикли, се нарича общо дърво за разлика от ориентираното дърво, където един от възлите е обявен за корен.

Ориентирано дърво

Дефиницията му е дадена по-горе.

Подредено дърво

Ориентирано дърво, при което всеки възел се подрежда йерархично при вмъкване в зависимост от стойността на ключа, се нарича подредено дърво.

Дърво за търсене

Представянето на таблица чрез ориентирано подредено дърво с цел осъществяване на бърз достъп до записи от информация се нарича дърво за търсене.

Двоично дърво

Двоичното дърво е ориентирано дърво, което е :

q празно

или

q непразно, състоящо се от възел и ляво или дясно поддърво, всяко от които е двоично дърво.

 

 

----------------------------------------------------------------------

 

 

 

v:* {behavior:url(#default#VML);} o:* {behavior:url(#default#VML);} w:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 21 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

Обхождане на двоично дърво

От главното меню на приложението изберете командата Алгоритъм/Обхождане на дървета/Пълно двоично дърво. На екрана ще се появи прозорецът, показан на фиг. 4-5.

В текстовото поле Височина на дървото въведете желаната от Вас височина на дървото, което ще се визуализира. След това натиснете бутона Създаване на дърво. За да стартирате алгоритмите за обхождане, използвайте следните бутони от лентата с изнструменти:

Право обхождане в дълбочина

Подредено обхождане в дълбочина

Обратно обхождане в дълбочина

Обхождане в широчина

Резултатите от обхождането се визуализират в лентата на съсъоянието, разположена в долния край на прозореца.

Обхождане на дърво, представено по метода на дъщерните списъци

От главното меню на приложението изберете командата Алгоритъм/Обхождане на дървета/Дърво, представено с дъщерни списъци. На екрана ще се появи, прозорецът показан на фиг. 4-6.

Преди да се стартират алгоритмите за обхождане трябва да се създаде самото дърво. Това става по начина, описан в секцията Представяне на дървета – Метод на дъщерните списъци. Алгоритмите за обхождане се стартират от бутони, аналогични на тези при алгоритъма за обхождане на пълно двоично дърво.

Сортирани дървета

От главното меню на приложението изберете командата Алгоритъм/Сортирани дървета. На екрана ще се появи прозорецът, показан на фиг. 4-7.

За да добавите възел към дървото, трябва да въведете неговата стойност в полето Стойност на лентата с инструменти, след което да натиснете бутона Добавяне на наследник. Изтриването на възел става в същата последователност. Първо се възежда стойността на възела, който трябва да бъде изтрит, а след това се натиска бутона Изтриване на възел. Ако възелът липсва, се извежда предупредително съобщение. В този случай изтриването на възел не води до изтриване на неговите наследници, а до преподреждане на останалите възли в дървото. Броят на възлите можете да видите в лентата на състоянието.

Квадратични дървета

От главното меню на приложението изберете командата Алгоритъм/Квадратични дървета. На екрана ще се появи диалогов прозорец, показан на фиг. 4-7.

В текстовото поле въведете броя на позициите, които желаете да бъдат изобразени върху повърхността. Тази стойност всъщност определя и броя на възлите във квадратичния граф, който ще се формира. Натиснете бутона OK, за да я потвърдите, или натиснете бутона Cancel, при което ще се отчете стойността по подразбиране – 10000. На екрана ще се визуализира прозорецът, показан на фиг. 4-8.

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


Коментари на клиенти:

Все още няма коментари за този материал.
Моля, влезте в системата с потебителско име и парола, за да оставите коментар.


повече категории
Компютърни системи

За сайта

Кой е онлайн

В момента има 468 посетителя и 17 потребителя в сайта

Намерете ни в Facebook


© 2010 znanieto.net Всички права запазени.
znanieto.net избра за свой хостинг партньор Viscomp.bg

Изграден с помощта на Joomla!.