Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 46
Текст из файла (страница 46)
рис. 4.40). Переменные и!, и2, иЯ, и4 обозначают начальные и кон чныс позиции левь1х и правых Го(1изонталы1ых ду!' узла. 3. Каждой главной строке предшествуют трп строки, изображающие вертикальные части дуг. Теперь опишем структуру програм.зы 4.б. Ее две основныс составляющие — э1о прош.;ура построения оптимального дсРСВа ПОИСКа ПРИ Залш1НОМ РаСПРСДСЛЕ1ПП! ВССОВ от И ПРОЦСДУРа изображения дерева с заданными индексами узлов т. Вся программа иреднаь1п1чепп дли обопботкн текс'гов программ, д ' 3 ф ) Щ О х с~ Г ОМ о с. „". ы о Ы < ~О > О о СЭ о ~с и. а о -2 Б а (~ и х х а О О о 1= С.) ф ю Р 3 ~ — — о д~ о а ~н Д о О Д ) .О к '4 ~к а ~? < й- 1- ( 1- ~ — — а < У) ~ы а $ ~Ф ~Е СЪ о (Э ~ й3 СЭ Ы О О а. ~ О $ ф о О .О Ф й 5 о а И И о о — — о СЭ ~Е О О Г =:- Е3 Г ' о ОЗ Й М и > а р Г'=:- ~р >" н < ЮΠ— Ю Ы 'С 3 о ш х д о м 4 м О Ш л 1 Ф 1- ~ — -ш ОЗ о ~и — и й ~ н 1 (Е Х ы о к О.
О О. с ~3 о с О Щ О о )- ,— в Г о о д х О о 4нд Древовидные структура в частности папнсанных на языке Паскаль. Таская программа вначале читается, ее идентнфикторы н зарезервированные слова распознаются с установкой счетчиков а,, и Ь; при нахождении зарезервированного слова рл и идентификаторов между й~ и лтрьь После печати частотной статистики программа переходит к вычнслени1о длины пути идеально сбалансированного дерева, определяя корни его поддеревьев. После зтого печатается средняя дчнна пути и изображается полученное дерево.
Та5лпца 4,5. Частоты поввлсппй клточевых слов 203 4 19 15 8 0 О О 0 1 0 О 0 9 23 209 22 17 24 17 0 БЗ 6 16 10 О 6 1 39 0 О 37 Б49 7 27 0 2 О 20 8 га О 12 2 О 13 2 0 о 10 7 2 1 1 8 0 13 12 2 8 5 8 0 АННАУ 8ЕО!М САБЕ СОМБТ огу О О16МТО Оо ЕЬБЕ ЕМО Все еон еомст!Ом пото !Е 1М ЬАВЕЬ МОо МП. ОЕ РНОСЕООЯЕ РНООНАМ НЕСОЯО НЕРЕАТ Бег ТНЕМ То ТУРЕ пмтп. УАН УУНП.Е чати ргоагапг ор!!та1!«ее(~при!,ои!рсн)! соы1 п — — 31; [число ключей) !с!п =,10; [максимала«сая длина ключа) 1уре ои1ех = 0 .. и; а[!а = рае)сед аггау [1., Ип) оГ сйаг; уаг сЬ: сйаг; Ь1, Ьул !и!ееег; !«1: а!1а; [идентившкапсор или слухсебгсое слово) Ьи!'.
аггау [1 .. И~г) оГ сЬа«; [бусйер символов ) Ьеу: аггау [1,, п) оГа[1а! 1,1,1с: !и!екег; а: аггау [1 .. и) оГ !и!сеег; Ь: аггау [инуех) оу !и!екег; р,се: аггау [!пс1ех,тс1ех) ог йс!еее«1 т аггау [исарх,ииуех) ог 1пс1ех; гита, гшнй: !и!екег; )апе11оп ьа1!«ее[Ц: !пасех): !и!екег; гаг 1с: !п1еуе«1 Ь аш Ь:= [!+~+1) д) г; г[1,Л:= Ь! !г с ~ ! 1Ьеп Ьайгее . 'Ь[Ь) е1ае Ьайгее .'= Ьайгее(Ф вЂ” 1) + Ьа11«ееЩ) + и[1,Д епд [Ьа1!гее); ргоеедпге ор!!гее; гаг х, и!и: !и!екег; 1, 1,Ь,й,пс: йЫех! Ьеа)п [аргумент! и, ревулапштгр, г) 1ог с':= О 1о и до р[1,!): !«[1,!)! [ширина дерева Ь = О) Сог с';=- 0 1о и — 1 до [ширина дерева Ь = 1) Ьеа!и 1:= !+1; Р[с)):= Р[! !) + Рйй! [!)):=.! епд; гог Ь:= 2 1о п до [Ь-ширина спекущего дерева) гог с':= — 0 1о п — Ь до [йлевый индекс текущего дерева) Ьеа!п );= !+Ь; Ц-право!й индекс текущего дерева) т;= г[1,)-Ц; т!и:= р[с;т — Ц + р[сп,))! гог 1с '.= т+1 1о г[!+1, 1) до Ьеп)п х;= р[!/с — Ц + р[Ь,Я1 !г х < псс)с 1Ьеп Ьеа)п т: — Ь! т!и;= х епд епд; р[1,!):=- тсп + ге[1, 1); г[1,)):=- т епд евй (оргггее); ргоеейпге ргш1 1гее; соазФ !ге 120; (размер строки АЦПУ) Фуре г ег" Тпос1е; 1шероз!иоп =- О., 1п; йе =- йЬ", тц рог: 1!персе!г!оп ! 1е!О г1КИ, !йй; ге!' евй; таг гооО сиггтг, пех1: ге!',.
а,а1,а2: ген; 1, !с: !пгекег; и, и1, и2, иЗ, и4: !!персе!!!оп 1апеФ1оа ггееЯ: !пс1ех): геЯ чаг р: ге!1 Ъеп1а 1! ! =,у Фвеа р:= а11 е1ее Ьера пев(р); рТЛс!г:= ггее(1, гД,Я вЂ” 1); р!.роз:- ((1 -ИЙК -1)) + (1! й1 2); а:= 1--Н! рТ! у:=1 уИчФЛ1 р7,г1к1н != Фгее(фД, /) евй; ггее:= р евй; Ьйа 1с:= О; гоог:=- ггее(О,п); снггепе:= гоог; гоог!.1п1с Ф - в11; г!ехг:= ш1; вИе сиггепг ~ ш1 йо Век!а (продвиокение вниз, сначала печать вертикальных строк) Фог Ф;= 1 Фо 3 йо Ъеа1а и,'=- О; а:=- сиггепг! гереаь и1:=.
а,,рог; кереаФ иг!ге(' '); и:=- и+1 впО! и =- и1; ггг!!е('~')! и:= и+1; а: д~,1!я!с ваФИ а — в!1; иг1ге1п евй; (печать главной строки! сборка их потомков, спускаясь по узлам текущего списка, и Фоормирование следующего списка) и+1 епй; его а':= сиггеп/; и:= О; терев! ипрас/с(у[./сеу, Ьи/; 1); (иентральный ключ) /:= /г/и; тгИейи/[/) = ' ' йо /:== / — 1; и2:= — д[.ров — ((! — 1) й1ч 2); иЗ:= и2+/; д1:= д[./е/Ц а2:=- г/ .пай/; и' а1 = аИ !Ьеп и1:=- и2 еЬе Ьеп!п и1:= т/1[.рвь", ч1",й/и/с:== ссх/; пех/;=- вой; И в2 = п1! !Ьеп и4:г.= иЗ еЬе Ьеа/п и4: =- д2'.ров+1; ч2'.//пй:. пех/,' пех/ епй; г':= О; ттЬ!/е и < и! йо Ьее!и итйс(' '); и:= и+1 епй; ттИе и < и2 йо Ьеп1п вп/е(' — '); и::= и+1 еай; аЛЛе и < иЗ йо Ьеп/п !:= !+1; и г//е(Ьи [/)); и .
'=- ттЬ1!е и < и4 йо Ьеп!а мгйе(' — '); и:=- и+1 епй; Ч:= И.//пй па!11 а = а11; жг//е/п; [инвертирование следуюи/его списка и превраи/ение в текуи/ий) сатен/:= ай!" ттЬ1!е пех/ ч- пИ йо Ьеп!п у:= пех/; пех/:-= а,л/т/с; д,.//п/с:= скчгспЦ сиггепт ."=- !/ епй епй Фпй [рг/п//гес); % ййп [инициация пгаблииы ключей и счетчиков) Агу[ Ц:=- 'кввм'; /сеу[ 2) ,"= 'вес~и'; ксу[ 3):=:= сдвв; /сей[ 4):== 'сонет; йеу! 5):; — о!ч", /ссу[ 6):=-.
'ооччито". /ссу[ 7):=-- 'оо", /с. [ 8): —. 'всвв'; /ссу[ 9) -- вив йсг[1Я;=,, г!~в ° Агу[/Ц:=- гов; ксу[!2) .== гонст~огг; /се/[!З!:=- 'сото'; йс/[14) .'==- чг'; А.су[15):=- м; ксу[16):=.: Ьквви; йсу[17):=- '61оо'; /сс/[!Ы:=-. 'нг'; /ссу[19):==- ого /с:у['О)::-: ггосвоовп/ Асг[2Ц:= — гвооккм'; /сер[22):==. 'гипсово"; Лег[25): Ве РеАТ' ' /сер[24): - — ' 'вет' ' /геу[25):= — ти.:и;,/ссу[2г',:: 'то'; Леу[27]:=- "туРг; /сеу[29]: =- 'чая'; Ьеу[3!]: — уу!тн", !ог /::=- 1 1о и до Ьерп а[/]:=- 0; Ьи ,'=- О епд; Ь[0):=- О; Ь2:=- Ь/и! [ просмотр входного тектпа и определение а и Ь тгЫ[е —,са/'(/прис) до Ьерп геад(с/~) ! Ы сЬ 1и ['А' ..
'Ж'] йеп Ьеа!в [идентисбикатор или служебное елово) гереа1 Ы И < Ь/п Йеп Ьери /с1:==- И+1; Ьн/'[Ы]:=- сЬ еид; се об(с/г) ппЬИ -тсЬ !в ['А', . '2', 'О',, '9']); Ы И ) Ь2 йеп /с2:=-- И е!ее кереа1 ЬиЯЛ]:=- ' '; /с2:= Ь2 — 1 пв1И /с2 =- Ы! расЬ(Ьи/,!,н/) ! гереа1 /с:= (/+/) д!г 2; Ы Меу[Ь] ~ /~/ Йеп / , '— /с+1,' Ы ЬеуЯ ') и/ Йев /;=- /с-1; пиИ! !>/; ЫЬеу[Ь] =- й/йеп а[Ь];- а[/с] + 1 е!ае Ьерп /с:;= (/+/) д!г 2; Ь[/с]:= Ь[к] «-1 епд епд е!ае Ы сЬ =-: ""'Йеи гереа1 сенс!(с4 ив!0 сЬ .= "" ейе Ы сЬ вЂ”: '[' Йеп кеуеа1 гет/(сЬ) аи61 сЬ =* ')' епд, пгтте/и (кгтв ино гяессенсив оя осссяяспсг.)! гита;=- 0; мнпЬ:=- Ь[0]; !ог /;.
1 1о п до Ьерп гита:=- гита «а[/],' гншЬ;= — ьитЬ-/-Ь[/]; ьс//е/п(Ь[! — !], аи, ' ', /ссу[/]) евд 1 гвт'/с/п(Ь[п])! И: — — О; Е диниминеские информационные структуры 2уа мгле(о(' — )1 жпге!тт(аотЬ, агапа); [определение ти из а и Ь! 1ог т .'== О го п оо Ьея[п и'[61);=- Б[1[; 1ог 1:== т+1 1о и Ео и[1 >! ~= и[1> — Ц + а[>! + БЦ епй; ипге('дчендое Рдтн ьенотн ор вдьднсео тиее= '); жтуге1п(Б«11гее(О,п)1тг[О,п):б;3); ргт11гее[ орнгее; ит11е(дчендое Рдтн еенотн ор орт1мдь тиее= ); >тг(Мп(р[ОЯи[О,п[:б:3)1 ропигее; [исследввание только сл>жебных слов, установив Ь = О! 1ог т';= О го и т)о Ьей(п и[ь1):= О; 1ог >':=- т+1 го и до и[1,>! .= тг[ь> — 1! + «[1! епй; арнгее; ит11е[п(орт!мдь тнее сонзюеннцо кета сны)1 ргупнгее епо Программа 4.6. Построение оптимального дереаа поиска.
На третьем этапе вызывается процедура орйгее, которая строит оптимальное дерево поиска; затем последнее изображается. И наконец, те же процедуры используются для построения и изображения оптимального дерева с учетом лишь частот обращений к ключам. В табл. 4.5 н на рис. 4.4Π— 4.42 приведены результаты, полученные программой 4.6 при обработке се собственного текста.
Различия трех рисунков показывают, что сбалансированное дерево нельзя считать даже близким к оптимальному и что частоты поиска незарезервированных слов сильно влияют на выбор оптимальной структуры. ца. сипьно Ветвягциеся деРеВья До сих пор мы ограничивали наши рассуждения деревьями. в которых каждый узел имеет самое большее двух потомков, т.
е. бинарными деревьями. Этого вполне достаточно, если, например, мы хотим представить родственные отношения с предпочтением «восходящей линии», т. е. когда для каждого человека указываются его родители. В конце концов, ни у кого не бывает более двух родителей. Но как быть тому, Е.5. Сильно вегвяиеиеея деревья 279 к>о предпочитает изображать «нисходя>цую линию»? Ему придется столкнуться с тем фактом, что некоторые люди нме>от более двух детей, поэтому его деревья будут содержать узлы со многими ветвями.
За неимением лучшего термина мы будем называть их сально ветвящимися деревьями. Разумеется, в таких структурах нет ничего необычного, мы уже встречали все средства программирования и описания данных, нужные для того, чтобы справиться с такими ситуациями. Если, например, задана абсолютная верхняя граница количества детей (что, по-видимому, является неким футуристическим предположением), то можно представить детей в виде компоненты-массива в записи, представляющей человска. Но если число детей у разных людей сильно варьируется, то это может привести к неэкономному расходу памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
