Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 36
Текст из файла (страница 36)
Однако легко найти подходящее усовершенствование: поиск в цпорядочениоег списке. Если список упорядочен (например, по возрастанию ключей), го поиск заканчивается не позднее чем встретится первый ключ, больший, чем искомый. Упорядочение списка достигается включением новьгх элемсгпоа ие в на шло, а в соответствуюигиге по порядку места. Фактически благодаря легкости включения в связанный список упорядочение обеспечивается почти без дополнительных затрат, т. е.
его гибкость используется полностью, Массивы и файлы такой возможности не дают, (Однако заметим, что даже упорядоченные списки не предоставляют шгчего эквивалентного бинарному поиску в массивах.) 11оиск в упорядоченном списке — типичный пример ситуашш, описанной в (4.15), когда элемент нужно вставлять перед данным, а именгсг перед первым элементом, имеющим больший ключ. Однако предложенный здесь прием отличен от того, который применялся в (4.!5). Вместо копирования значений при проходе списка исггользуготсч две ссылки: юй отстает на одни шаг от га1 и, таким образом, указывает иа место включения, когда ш) находит слишком большой ключ.
В общем виде этап вклгочения показан на рис. 4,10, 1!редваргпельно мы должны рассмотреть два обстоятельства: 1. Ссылка на новый элемент (гегЗ) должна присвшгваться ш2).кахг, кроме случая, когда список епш пуст, Для про стоты и эффективное~и мы предпочитаем не использовать для проведения этого различия условный оператор. Един- 4. Динаиические информапионнме сгрдктарм 206 ственныб способ избежать этого — добавить в начало списка фиктивный элемент. 2. Проход по списку с двумя ссылками, спуска»оптимися на расстоянии в од»ш шаг, требует, чтобы список содержал ио меньшей иере одни элемент (кроме фиктивного), Поэтому ,ключсиие первого элемента следует проводить иначе, чем гсех остальных. Процедура, построенная в соответствии с этими указания.:и, приведена в (4.23).
Она использует вспоыогательнучо У вз / Рпс. 4.10. Вкдмчеппе в упоредочевпый список. ргосейрге тзег»(ич геД; тат и3: ге»; Ьси!и иеи(и 3); 'и!»!е и'3 ! йп пед!и Л-еу:== и; соим:= 1; ьех»:= зр епй; и2, жех»:= и'3 епй (»пеег») (4.22) Инициация <гоо»:= и!!» в программе 4.1 соответственно заменяе~ся на пою(гоо») гоо» !.»гех»:= пИ В соответствии с рнс. 4.10 мы определяем условие перехода и следующему элементу при просмотре списка; оно состоит нз двух частей, а нмснпо: (го1)'.йеу < х) Л (ы!'(,пех! Ф п1 !) процедуру тзег» (евхлючениее), которую нужно локально списать в зеагсй.
Опа размещает в памяти и инициирует ио.ки! элемент»о3, таким образом: 4.З. Линейные списки 207 Ниже приведена процедура поиска: ргосевпге хеогс!!(х: !пгеуег; чаг гоог: ге!); чаг в1,и2: ген Ьея!в гч2:= гоог; гч1:=- м27еоехг; !1 и1 = л!1 Игеп омег! (и!1)! е(зе Ьее!и ччЬ!1е (в1мйеу < х) /! (ж1!лех! ч- в!1) г!о Ьеяшм2:= !ч1; гч1:= зч2!лех! епг(; !г" и'1Т.лисеу = х тйев н 1!.соил!:=- и Ц.соип! + 1 е(зе !пиес!(ж1' елй епй (ееогсй); (4.23) К сожалению, несмотря на всю нашу осторожность, сюда вкралась ошибка. Мы предлагаем читателю, прежде чем двигаться дальше, найти здесь логический подвох. Тем же, кто предпочитает избежать этой работы детектива, достаточ~го сказать, что (4.23) будет всегда проталкивать включенный первым элемент в конец списка.
Ошибку можно исправить, указав, что, если поиск заканчивается при невыполнении второй части условия, новый элемент нужно включать после ео1 (, а не перед ним. Следовательно, опсратор «!пзег! (го!)» заменяется на Ьев!и 1Т ггЦ.ггех! = вй !Ьев Ьея!и чч2:= и1; н1:= вП епв; !нее!!(ж1) евв (4.24) и !'.пех! =- и!! в (4,24) на гс! !./геу < х Увы, доверчивый читатель вновь введсн в заблуждение, так как алгоритм (4.24) по-прежнему неверен. Чтобы обнаружить оншбку, предположим, что новый ключ лежит между последним и предпоследним ключами.
Это приведет к тому, что обе части условия продолжения цикла ока:.кутся лочкными, когда оудет достигнут конец списка, и, следовательно, включение произойдет после конечного элемента. Гели тот же ключ появится позже, он будет вклкшен правнлыпг и, таким образом, окажется в таблнпе в двух мес!ах. Это можно исправить, заменив условие 208 4. Динамннеркне инфорлааианнме структуры Чтобы ускорить поиск, условие продолжения в операторе цикла можно вновь упростить, используя барьер. Это требует присутствия грпктианого элемгнтп как в начале, так н в конце. Следовательно, список должен ннпциироваться следующими операторамн: пеш(гоо!); пеаэ(аепипе!); гоо)~.пах):= аеп!!г!ей и процедура поиска заметно упрощается, что видно из (4.25) ргосейиге хна~с!цх; !н!евег! хат )рог: >т~); наг и!,и2,иЗ: ггг! Ъеа!и и2: -.
ганг; и1:.== гг2; пех); эепгше! ~,йеу:= х) иЬ!!е»1;.Аау < х йо Ъса!п и'2:= — и'1; ь21:= иг2;э!тг епй; Ы фг1;,.Ьеу == х) Л (и1 чг; эенгр!е!) гйеп, и!псаппг:=. и1;:,санат + 1 е1яе Ъей!п лги(и 3); )включение згЗ между и1 и и2) и!!Ъ иЗ! йо Ьеа!и )геу;=- х; соипр:=- 1; лехг: — и1 епй; и2! э!ах!:=- иЗ епй епй )кеагсй) '!'спорь пора спросить, какого выигрыша можно ждать от и иска в упорядоченном списке. Учитывая, что дополнительное усло>кнепие невелико, пе следует оэкпдать каких-то потрясиощпх результатов. Допустим, что все слова встречаются в текста с одинаково ! частотой. В этом случае, как только все слова окажутся в списке, выигрыш, достигнутый при помощи лсксикографпчсского упорядо !ения, фактпчсски будет ничтожен; здссь позиция слова не имеет значения, поскольку важна лишь сумма всех шагов и все счова ищутся с одинаковой часто~ой.
Однако вьпщрыш достигается при включснии нового слова, Вместо всего списка просматривается в среднем только около половины списка. Следоватсльпо, включения в упорядоченный список стоит использовать лишь в случае, когда нужно построить словарь с большим числом различных слов, по сравненшо с часто~ой появления. Поэтому прпведенпын выше пропедуры служат в основном в качестве упражнений в программиоованпи, и пе для практического применения.
Помещать данные в связанный! список рскомеплуется в том слуша, если число элемгцтоп мало )скажем, .100), заранее неизвестно п, болсе того, нет никакой информации 4.8. Линейные списки о частоте обращения к ннм. Типичный пример — таблица имен в трансляторах с языков программирования. Как только встречается описание, новое имя добавляется к списку, а прн выходе из области действия описания имя удаляется из списка. Простые связанные списки стоит использовать, если речь вдет о сравнительно коротких программах.
Даже и в этом случае можно значительно повысить эффективность доступа благодаря очень простому приему, который мы здесь еще раз рассмотрим в первую очередь в связи с тем, что он служит хорошим примером для демонстрации гибкости структуры связанного списка. 1 ~ ~ ) яепиое1 Д и~1 Рис. 4.1! Список до переупоряаочееея. ,1ля секста программ характерно частое скопление одного и того же идентификатора, т. е. за одним вхождением часто следует одно или более повторных вхождений того же слова.
Это наводит на мысль реорганизовать список после каждого обращения. переставляя найденное слово в начало списка, так как тем самым мпинмизируется длина прохода по списку прп следующем поиске того же слова. Этот метод называется поиском ссо списку с лереупорлдочениеяс, илп -- несколько претенциозно — гамоореанизуви1имсл поиском по списку.
Описывая соответствующий алгоритм в виде процедуры, которую можно подставить в программу 4.1, мы учтем предыдущий опыт и с самого пача:и введем барьер. Действительно, его наличие в эточ случае пс только ускоряет поиск, но и упрощает програмз1у. С самого начала список не пуст, а уже содержит барьер. Начальные операторы следующие: пек(аеп!спе1); гоо(:= зесиспей Заметим, что основное различие между новым алгоритмом н простым поиском по списку (4,21) — переупорядоченне прн нахождении элемента. Найденный элемент отделяется, илп удаляется со своего старого места и вставляется в начало. Это удаление слова требует использования двух ссылок прн поиске, чтобы можно было установить местонахождение эле- з!о 4.
Дииоии микис информационное сгрдкгдрм мента га2у, предшествующего найденному элементу го1т, чго в сво1о очередь требует особого обращения с первым элементом (т. е. с пустым списком), Чтобы читатель мог наглядно представить себе процесс изменения связей, мы отсылаем его к рис. 4.11. На нем изображены две ссылки в момент, когда ш1) опознан в качестве искомого элемента. )хонфигурация списка после соответствующего переупорядочення показана на рпс.
4.12, а новая процедура поиска целиком оппсава ниже: ргосепиге всагсй(х: 1н1еесг; тиг гоо1: гс!'); хат гг!гж2: гс1; Ьсе!и ж! ."=- гоо1; зсагй1с1;.Ьсу;= — х; К ж1 =.,гсл11ас! Йеп Ьсййп (первьгй элемеггт) пои(гоо1); птЙ гоо1) йо Ьей!и 1ссу: = х; сонн1:=- 1; нсхг,' †- вен(анс! спй епй е)зе йт ж1!Асу = х Йсп зг1;.соаа1:=-: ж1 "+,соип1 + 1 е!эе Ьей!и (зсагс/~) гереат и:2:.= зг1; ж1:= и2, шсх1 ппг!! к11,йсу ==- х; !1 ж1 = всн11пс! Феп Ьеа!и (включение) ж2:= гоо1; пои(гош); и!Й гоо!1 йо Ьей!и йсу:.—.= х; соннг:==- 1; псх1;=- и2 епп епй с!зе Ьсй!и (найден, гнеперо переупорядочивание списка) ж1, сошп:= зг!',.мин "; 1; тй,.псх1;:; — ч1'.псх1; зг1;лсх1:=- гоо1; гоо1:= — ж1 иий еий спй (гссос1~) Выигрыш при таком методе поиска сильно зависит от степени скоплеяия входных данных.
При заданном коэффициенте скопления улучшение более ощутимо в случае больших спн. сков. Для того чтобы получить представление о примерной величине выигрьппа, который можно ожидать, были провалены эмпирические измерения. Припаленная выше программа составления застот' ого словаря применялась к коротким 4.3..ггинеггивге списки 21! и омюсптсльпо длинным текстам, затем сравнивались методы линейного упорядочения (4.21) н псреупорядочення списков до п2 гк1 Рвс. 4.12.
Список после персупорядочсния. (4.26). Результаты измерений приводятся в табл. 4.2. К соисаленгпо, наибольший выигрыш достигается в случаях, когда Таблипа 4.2. Сравиенне методов поиска по списку тест г тест 2 53 582 315 14 341 6 207 3 200 622 4 529 681 584 1,37 4,70 Число разл.шпек ключей Число появлений ключей Время поиска с упорядочеинем Время поиска с переупорядочением Козффпшггент улучшения пожму-либо требуется другая организация данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
