Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 41
Текст из файла (страница 41)
Теперь каждый узел не только содержит слово в качестве значения ключа, но одновременно представляет собой начало списка номеров строк. Каждую запись номера строки мы будем называть отяеткои, Следовательно, в этом примере мы встречаем и деревья, и линенные списки. Программа состоит из двух основных частей (см программу 4.5): фазы чтения текста и построения дерева и фазы печати таблицы. Ясно, что госледняя является частным случаем процедуры обхода дерева, где посешение каж. лого узла предполагает печать значения ключа слова и проход по связанному с ним списку номеров строк (отметок), Кроме того, полезно привести еше некоторые пояснения, от« носящиеся к программе 4.5: 1.
Словом считается любая последовательность букв н цифр, начинающаяся с буквы. ргопгат сгокгге1'(1",оШриг); 1ностроение тиблииь> нерекрестнглх ссылок с использованием двоичного дерева) еопвг с1 10; (длина слави) с2 8; 1количество слов в строке) сЗ =- 6; $количесВ!ВР г1ифр в числе) с4 =- 9999; (максимальаый номер сюпрюки) Фуре а11а =-: раеКед пееву ~1 .. с!1 оу сЬаг1 Вогг1гсг =- ~1гоге1: Ьетге1 = ~йгт; хоп1 = гееогд Ьсу: и11«; 17гвг, 1изг: йенн 3', 1еР, щйг: КОГГ1гсс а; 11ео1 = раеЛед гееогй 1но: О ..~4; нехы 1гсниеу' епй; так гоо1: иогсЬс1'; К1'1: игексг; и: ьнскегг 1номер текуиуей строки) И: а11а; .У', гех1; а: пггеу ~1 ., сЦ оГ сЬиг; ркоеедиге воин сй (уае и'1: 1еогг1ге~); так ъч когс1ге1'; х.
'11егнге/; Ъеа1п и:= »1; 1с и = пИ еЛеп Лерп йее'1и); нее'Я; ирЬ и", ди Ъеп1пАеу:== и1; 1е12:= пП; г1рЬ1 1= пИ; Зглг:=- х; 1авг:=* х епд; х",.1по:=- и; хуоисхс:= пН; пе: --, епд е1ве 0 Ы < н',,Ьеу 1Леп кеагс1~~и ~.1еЯ еЪае И' и1 > и 1,йеу еЛеп яеагсй(нУ.щМ) е!ве Ъеп1п непЯ; х),Ь!о:=- и; х~ еиехг:= пИ; и ~.1ак11снекг:= и; н"~,1акг:= х епп впав '1геагсф; реееейпее рГ1Н11гее(и".
ъагй Я; ргосейиге рг1пгногсс(н; аносов; гаг 1: тссесг; ех Истгс1; Ьей)п игие (' ', ии)сег); х:=- сг.11ггг,' 1:== 0; гереаС И 1 == с2 йеп Ьер)п ссг1гс1гг; г:=-- О; ссг1сс (' "сс1+,1) епй; 1:==- 1-,'.1; иг1ге (х',Лпо.'сЗ)1 х .'= х).пехс пп1И х == пИ; ит11с1п епй (ргипеогс)); Ьер1п 11 и' =~ пИ йеп Ьер)п рйггггсс'(и',,1с)г); рг1пси'огй1(ь',); рг1п11гее(л';.г1цЫ) епй епй (рг1ии!гсс); Ьер)п гоос:=- пИ; и:=- 0; Ь1 .'= с1; ракс (оссгрссс); гсгссЯ; иЬИе — ео/'(Г) йо Ьеп)п 11'и =- сй йеп тг:= О; и:=-- п+1; игие(п:сЗ); (следуюсиая строка\ ни'сс (' псе —.со1п (1) йо Ьей)п (просмотр непустой строки) 111'"; 1п 1'А'., 'гс) йеп Ьедй 1с:=- 0; гереае К 1с < с1 йеп Ьеййп )с:== 1+1; а1)с):= 1~~,' епй; иг1сс (р)); Исг (1) ппРИ вЂ”:(1) й Гас ..
'г','0' .. '9')); 11 1с,, И йеп И:== )с е)ве гереа1 а(И):= ' '; И:= И-1 ипЬИ 1с1 =:.: 1с; рас)с (а,1,1с)); геагсй(гоос) епй е)ее ЬеИ1п (проверка на кавычку или комментарий) И 1т == "" йеп гереаг игссс((~); асс(й ппрй 1, е)ве 11' Д = '(' йеп 4Л, Древовидвьгв структуры 241 В табл. 4.4 показан результат обработки некоторого текста программы. 4,4А. Удаление из дерева Теперь мы переходим к задаче, обратной включению, а именно удаленню. Нам нужно построить алгоритм для удаления узла с ключом х из дерева с упорядоченными ключами. К сожалепиго, удаление элемента обычно не так просто, как 2. 4. тереа1 игп1в!у" 1); двг(у') пп1!1 т"'~ = ')'; жтйв Ду 1); де1 (у) еп4 епй; .Втде!л; увг( г') еп4; раув!счггрщ); ртгп11тве1тоо1); епй Программа 4.5.
Построение таблицы церекрествьгк ссылок. В качестве ключа хранятся только первые с! символов. Таким образом, два слова, у которых первые с1 символов не различаются, считаются одинаковыми. Эти с! символов упаковываются в массив И (типа а!!а). Если с1 достаточно мало, во многих вычислительных маппшах такие упаковапньге массивы могут сравниваться с помощью одной команды. Переменная к! — это индекс, который используется в следующем ннвариантном условии, касающемся буфера символов и: а Ц =' ' для 1= Й!+ 1 ... с1. Это означает, что слова, состоящие нз менее чем с! символов, дополняются соответствукпцнм количеством пробелов, )Келательно, чтобы номера строк в таблице перекрестных ссылок печатались в возрастающем порядке.
Поэтому список отметок должен формироваться в том же порядке, в каком онн печатаются. Это требование предполагает использование в каждом слове-узле двух ссылок, из которых одна указывает на первый, а вторая — на последний элемент списка отметок. Сканер строится таким образом, что слова в кавычках и Впутри комментарнеВ не Включаются В таолнцу перекрестных ссылок; прп этом предполагается, что кавычки и комментарии не переходят через концы строк. 4, динамические информационные структуры Таблица 4.4. 1 РЯО6йЛМ РЕЯМОТЕ (ОСТРОТ)) 2 СОИЗТМ=4; Э ЧЛЯ П (ИТЕОЕН; 4 А; ЛНВЛУ [1,. М] ОР (МТЕОЕЯ! 5 6 7 8 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ВЕОГИ 26 РОН 1;= 1 ТО М ОО А[1]:= )) 27 РЕЯМ (И) 28 ЕМО .
РНОСЕООНЕ Рй(МТ; УЛЯ Г: ГИТЕОЕЯ; 666]И РОЯ 1:= 1 ТО М ОО ЖЯ,'ГЕ (Л[(]:3)) УУН(ТЕ[И ЕМО (Рй(ИТ); РЯОСЕО(ГНЕ РЕЯМ (К: )ИТЕВЕЯ)Г УАЯ Г,Х: !МТЕОЕВ: ВЕ6(И (Р К = 1 ТНЕИ Рй(ИТ ЕЬЕЕ ВЕСмй РЕВМ (К-1); РОЯ 1:= 1 ТО К-1 00 ВЕ6!М Х:- "А[1]; А[1] гм А[К]; А[К]: Х; РеЯм (К-1)т Х:= А[0; АК:= А[К): А[К]:= ХЕ ЕИР ЕМО ЕИО [РЕЯМ); АййАУ А 4 8 18 18 20 20 26 В 14 16 18 2 8 17 26 15 10 21 22 23 8 17 26 15 3 4 7 12 3 7 8 В 20 20 26 26 18 18 20 20 ВЕВГМ СОИЭТ РО ЕЬЕЕ ЕМО РОй (Р )МТЕВЕЯ 1 13 13 17 26 18 18 Пример распечатки, получеииой в результате работы программы 4.5, 44. Древосидиис структуры 243 8 28 27 19 27 18 20 20 включение.
Оно просто в случае, когда удаляемый элемент является терминальным узлом или пмеет одгого потомка. (с! (в1 Рвс. 4.28, Удвдеввс вв дерева Трудность заключается в удалении элементов с двумя потом. ками, поскольку мы ие можем указывать одной ссылкой на два направления. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого подде. И Ор ООТРГСТ РЕВМИТЕ РЕВМ РВ1мт Рносеоона РВ06ВАЧ тнеи то МАВ ФВ!ТЕйн "тт'В 17 6 Х 12 16 20 2 4 4 1 12 16 8 16 6 12 1 16 6 17 3 7 9 8 13 18 Пвннаниеннн 16 17 18 16 :З 20 4.
Динамические инфорнаиионннм о«рак«ура рева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка. Подробно это показано в рекурсивной процедуре, называемой г(е1е1е (4.52), Она различает три случая: 1. Компоненты с ключом, равным х, пет. 2. Компонента с ключом х имеет не более одного потомка. 3. Компонента с ключом х имеет двух потомков. ргосейае йе1еге (х: 1лгеиег, 'тат р: геЯ; тат ц: геД; ргосеепге о(е1(тат г; геу); Ъеи)п 11 г).щЫ Ф а11 1Ъеп с(е1(г).щйг) еЬе ъеа1а ц).ассу:= г)лсеу; д).соил! г = г).соипг1 Ц:= г;~Я ",== «~.йф Р, ~1Д 8се.сг Еиг" еаа еай; Ъеи(а фе1еге) 11 р = ай йеа ит11е!и (' угони га нот 1м тийн') еье Ы х < р).йеу йеп Ие1еге(х, р и)е«г) еЬе 11 х > р).Усеу йеа Ие1еге(х, р'!.па)и) е1ае Ъей)п (де1еге рЦ ц:= р; 11 ц~.ай! = п11 йеа р: = д1.1е!) еЬе И ц).1еЛ = а11 йеа р:= цмпайг е1ае гЕе1(й(.1еЯ) 1 (й1«роге(ц)1 еай Еий (ИЕ)ЕГЕ) )~4>~~' ие~"к 'Еииески ) „, Ы ГАМ' и4«кн4ьеоес4 осе асин а гтп еии гани е.еи е»с Вспомогательная рекурсивная процедура «1е! вызывается только в 3-м случае.
Она «спускастся» вдоль самой правой ветви левого поддерева удаляемого узла ц ) и затем заменяет существенную информацию (ключ и счетчик) в цз соответствующими значениями самой правой коыпонентгя «1 этого ,аевого поддерева, после чего от «1 можно освободптьси. Процедуру г)1зроэе(ц) можно рассматривать как обратную процедуре пса(ц). Последняя занимает память для новой компоненты, а первая может применяться для указания вычислительной системе, что память, которую занимает ц1, можно освободить и потом вновь использовать (некоторый впд чистки памяти).
Для иллюстрации работы процедуры (4.52) мы отсылаем читателя к рис. 4.28. Задано начальное дерево (а), из которого последовательно удаляются узлы с ключамн 13, 15, 5, 10. Полученные деревья показаны на рнс. 4.28 (Ь вЂ” е). 4.4. Дрввовыдкмв структуры 24й 4А.з. Анализ поиска с включениями по дереву Довольно естественно испытывать некоторое недоверие к алгоритму поиска по дереву с включениями. Во всяком случае, до тех пор, пока мы не узнаем более детально о его работе, мы будем испытывать некоторые сомнения. Прежде всего многих программистов беспокоит то, что обычно мы не знаем, каким образом будет расти дерево, и не имеем никакого представления о форме, которую опо примет. Ыы лишь можем догадаться, что оно, скорее всего, не будет идеально сбалансированным. Поскольку среднее число сравнений, необходимых для нахождения ключа в идеально сбалансированном дереве с и узлами, приблизительно равно 6 = (оп и, то число сравнений в дереве, сформированном этим алгоритмом, будет больше Ь.
Но насколько больше? Рнс. 4,29. Распределение песня па ветвям. Прежде всего легко найти наихудший случай. Допустим, что ключи поступают уже в строго возрастающем (или убывающем) порядке. Тогда каждый ключ вставляется непосредственно спрана (илн слева) от предшествующего, н построенное дерево оказывается полностью вырожденным, т. е. оио превращается в линейный список. В этом случае средние затраты на поиск равны л/2 сравнениям. Очевидно, что в таком наихудшем случае алгоритм поиска малоэффективен, и, кажется, что наши сомнения оправдываются. Конечно, встает вопрос, насколько вероятен такой случай. Точнее, мы хотели бы знать длину ак пути поиска, усредненную по всем л ключам и усредненную по всем и! деревьям, которые получаются в результате и! перестановок и исходных различных ключей.
Эта задача анализа алгоритмов оказывается достаточно простой и приводится здесь ие только как типичный пример такого анализа, но и из-за практической важности полученного результата. Пусть даны и различных ключей со значениями (, 2, ..., ш Предположим, что они появля|отся в случайном порядке. Вероятность того, что первый ключ, который становится корневым узлом, будет иметь значение й есть (/и. Его левое поддерево в конце работы будет содержать ~ — ! узлов, а правое поддерево — и — ( узлов .(см. рис.
4.29). Пусть средняя длина пути в левом поддереве обозначается через Е. дннамллнеекне ллнл!ла!лллал!ллнкньее етацктяры а ,, а в правом поддереве ан,. Вновь предполагается, что все возможные перестановки оставшихся л — ! ключей равновероятны. Средняя длина пути в дереве с л узлами равна сумме произведений уровня каждого узла и вероятности обращения к нему. Если предположить, что все узлы ищутся с одинаковой вероятностью, то н ан = )„!тт (4.53) л=! где р, есть длина пути до узла й В лереве на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
