Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 51
Текст из файла (страница 51)
ред. т'. Дикамккеские информационные структуры Для разрешения конфликтов в литературе предлагались различные функции. Обзор этой темы Моррисом в 1968 г, 14,8] стимулировал активную деятельность в этой области. Простейший метод — это, считая, что таблица круговая, исследовать следующее место и так до тех пор, пока не будет найден элемент с заданным ключом или не встретится свободное место. Следовательно, 6(1) = й индексы йь используемые для поиска, в этом случае имеют вид: йе = Н (и) й,=(бе+1)шой М, 1=1...йт — 1.
(4.90) Этот метод называется линейным опробированием, он имеет тот недостаток, что элементы обычно скапливаются вокруг первичных ключей (ключей, при которых мы не столкнулись с конфликтом при включении). В идеале, конечно, следует выбирать такую функцию О, которая вновь равномерно рассеивает ключи на оставшемся пространстве. Но на практшке это требует слишком больших затрат, н предпочтение от- зывание в цепочку всех элементов с одинаковым первичным индексом Н(й). Этот прием называется непосредственным сцеплением. Элементы такого списка могут либо находиться в первичной таблице, либо нет, в последнем случае память, в которой они размещаются, называется областью переполнения.
Этот метод довольно эффективен, хотя он имеет тот недостаток, что нужно вести вторичные списки и что каждая строка должна содержать пространство для ссылки (или индекса) на список элементов, вступающих с ним в конфликт. Другой метод разрешения конфликтов состоит в том, чтобы полностью отказаться от ссылок и просто просматривать один за другим различные элементы таблицы, пока не будет найден нужный элемент или не встретится свободное место, что означает отсутствие в таблице данного ключа. Этот метод называется открытой адресацией 14.9). Разумеется, последовательность индексов при вторичных пробах для данного ключа должна быть всегда одной и той >ке. Можно набросать примерно такой алгоритм просмотра таблицы: й:= Н(й) 1:=О; гереа( И Т>1>)Леу = й 1Ьеп элемент найден е(зе 14 Т1й),йеу =свободно 1Ьеп элемента нет в таблице е1зе Ьеп>п (конфликт) 1;=1+ 1, й:= Н()е)+ 6(1) епй ««111 найден или нет в таблице (или таблица полна) 4.6.
Преобраввваннн ключи (раеетакввка) Зот дается методам, представляющим компромисс; будучи простыми для вычисления, они все же лучше линейной функции (4,90). Один из них состоит в использовании квадратичной функции, такой, что последовательность индексов для опробирования есть Ьа —— О (й), Ь, =(йе+ 1а)глоб йГ (Е > О), (4.91) Отметим, что вычисление следующего индекса не требует возведения в квадрат, если использовать рекуррентное соотношение (4.92) для Л, = 1х и И; = 21 + 1: 6;„,=6;+д, И И +2 (1>0) с йе = 0 н Ив = — 1.
Эгот метод называется квидратичньем опробированием, он успешно позволяет избежать первичного скопления, хотя практически не требует никаких дополнительных вычислений. Небольшой недостаток заключается в том, что прн опробировании рассматриваются не все строки таблицы, так что при включении можно не встретить свободного места, хотя такие места еще остаются. Фактически если ес размер )ч' — простое число, то при квадратичном опробировании используется по меньшей мере половина таблицы. Это можно получить из следующих рассуждений: если 1-я и 1-я пробы приводят к одной и той же строке таблицы, то справедливо равенство 1е шоИ)У =)'шоИ ЛГ 1' — )а = 0 (гпоИ йГ).
Разбивая разность иа два множителя, мы получаем (1+ 1) (1 — 1) = — 0(шоИ М), Поскольку 1чь(, мы видим, что либо 1, либо 1 должно быть не менее У/2, чтобы получить с'+1 = сЛ', где с — целое число. На практике этот недостаток не так существенен, поскольку необходимость выполнять У/2 вторичных проб для разрешения конфликтов встречается очень редко и лишь в том случае, когда таблица уже почти заполнена, Чтобы на примере продемонстрировать метод рассеянных таблиц, мы переписали программу 4.5 — формирование таблицы перекрестных ссылок — в виде программы 4.8.
Принципиальное отличие заключается в формулировке процедуры поиска (веагсй) и в замене ссылочного типа гсогдге1 таблицей слов Т. Функция расстановки и есть модуль размера таблицы; для разрешения конфликтов выбрано квадратичное ргопгапг сгоггге3' (3,оигриг); (построение таблицы перекрестных ссылок с использованием расстановки) (аЬе( 13; еопэ( с( ==- 10; (длина слова) с2 =-. 8; (количество слов в строке) сЗ = б; (количество циФр в числе) с4 =- 9999; (максимальный номер строки) р = 997; (простое число) фгее .— = ' (уре 1пг(ех == О ..р," !1етге3 =- '(!1егп; п'огг(:--- гееогд А.еу: а13а; 3!ггг, !агг: 11егпге3; 1о!: (пйех епа; 11ет =- расЬед гееогд 1по: О..с4; пех1: 1гетге3' епд; гаг ю, 1ор: и1йЕХ; Арй( й71еаег и: и1ееег; (номер пгекуи(ей ппроки) и1: а13а; 3' 1ех!; а: агапу (1 ..
с)) оХ сйаг; 1: аггау (О., р) оГ ггоы; (массив длл расапаиовки) ргьеейпге геогсй; гаг 1ий,1: йи,'..т; х: йетге3; 3: Ьоо1еап; (глобальные переменные: 1, Ы, 1ор) Ьеайп Ь:=- огй(й1) гаод р; „1':== 3а(ге; Ы:== 1; пеи(х); х(.1по:= и; х(.пех1:=- пН; гереаг К 1(Ь) (геу — — И 1Ьеп Ьер!п (найдено) 1':= ггие; 1(Ь) .1агг(гпехг:= х; 1(Ь).(аг1:= х епд е(ае И 1(Ь) (сеу =- 3гее (Ьеп ьеп!п (новый элемент) 3':== ггие; И)1Ь 1(Ь) до Ьеп(п (геу :== и1;,фгг1;= х; 1ае1 .'= х; 3Ь1 )= 1ор ' епй; Сор:= Ъ евй.е!ее Ьеп!п (конфликт) Ъ: Ъ+4 а:= й+2; Ы Ъ > р СЬеп Ъ:= Ъ вЂ” р; !С гС = р ЬЬеп Ъеп1в итССе1п(тАВИ ОЧЕвйол!); иеСо 13 евй епй пвф)1 С епй (оеагсЪ): угесейпге рппссаЪ1с „' так 1,1,т: !паек; ркесейвсе рг1п !поги(ж.
"жогд); тес 1: Сп!екег; х: !СетгеЯ Ьеп1в и г!Сс(' ', ейсеу) „ х:= гг.угггс; 1:== О; хереае зЕ 1 =- с2 СЬев Ьерп ггг!!е1п; 1:.= О; ьг!Сс(' 'с1+1) елй; 1;= 1+1; ггг!се(хтлпо:сз)! х;= хТ,пехс ы01 х = л11'; и кис!и епй (рппсггогг1) 1 Ъеп!в 1:= Сор; вЬИе 1 Ф р йе ъеп!п (просмотр связанного списка и поиск минимйгсьиого ключа) т:= 1; Л '= 6Я.~о!' пЬ!1е Л ~ р йо Ьев)п 11 С(Л)ЛссУ < С(т)ЛгеУ СЬеп т:= Л; Л:=- СИЮ епй; рг1пСпогИЯт)) ! Ми ФССЬеп Ьев1п г(т)Лсеу:= ф)./ссу; С(т)ЯМ:=- г(1)рог; ~т),1акС:= СЯЛаьС епй; 1:= С(!1Ло! елй евй (рг1пССаЪ!е); Ьеп(в и:= О; И:= с1; сор:= р; геьеСЯ; В1О 4.
Динамические информояиокные структуры тот 1 г:= 0 то р Йо 1[1).1сеу:= угее; аЫ!е -зео/'(Д до Ьед1п И н =- с4 1Ьеп л;= О; и:=- и+1; тугие(кпсЗ); [следуютаал си[рока) ятйе(' '); аЫ1е —,ео[л(~) до Ьед!п [ просмотр непустой строки'1 И Д' 1п ['А' ..'Е') 1Ьеп Ьее1п В:=- О; тереа1 И Ь < с1 тйеп Ьерп lс: — к-1-1; а[к):* епд; жесте(гт [); кот(тг) аа1Н з(У[ Ра ['А'., 'Е', 'О'..'9'))1 И и, И 11сеп И;=- )1 е1ке тереа1 а[/сЦ: — ' '; И:= И вЂ” 1 ап01 И =- 1с; раск(а,1,гИ); зсагсй; еаб е1зе ,, Ьед1п [проверка на кавычку или коимви~цриЦ И у[ "" 1Ьеп гереа1 юФе(т [); Хесе апб1 „г[ =- "" е)ке И Л == '(' 1Ьеп гереа1 кгйе(Д); дстЯ апб1 Г[ =- ')' 1 и'гйс(т [); гет(г') ;па епс1; нтйе)н; уст(у р епд; 13: раке; рггпгаЫе епд . Программа 4.8.
Построение таблицы перекрестных ссылок с использованием Функция расстановки. опробирование. Отметим, что для эффективной работы сушественно, чтобы размер таблицы был простым числом. Несмотря на то что метод преобразования ключа в этом случае очень эффектннен — намного эффективнее, чем использование деревьев, — он имеет недостаток. После просмотра текста н выбора слов мы хотим расположить эти слова АЕ.
Првобравованин ключа (расстановка) в алфавитном порядке, При работе с деревьями это очень просто, так как в их основе уже лежит упорядоченность. Но это не так в случае преобразования ключа. Вот здесь и сказывается, что таблицы — «рассеянные». Поэтому печати таблицы должна предшествовать сортировка (для простоты в программе 4.8 используется сортировка простым выбором); но кроме того, оказывается полезным сохранять историю включения элементов, для чего они связываются в специальный список.
Поэтому преимущества метода расстановки при поиске отчасти уменьшаются из-за необходимости дополнительных действий при выполнении всей задачи построения упорядоченной таблицы перекрестных ссылок. 4.6.3. Анализ метода преобразования ключа Очевидно, что в наихудшем случае включение и поиск прн использовании метода расстановки будут иметь очень плохие характеристики. Ведь вполне может быть, что аргумент поиска будет таким, что все пробы будут попадать как раз на занятые места и пропускать нужные (или свободные), В самом деле, тому, кто использует метод расстановки, нужно свято верить в теорию вероятностей. Все, в чем мы хотим быть уверенными,— это что е среднем число проб мало.
Следующие вероятностные рассуждения показывают, что оно даже очень мало. Вновь предположим, что все возможные ключи равновероятны н функция расстановки Н равномерно рассеивает их по всему интервалу индексов. Затем предположим, что нужно вставить ключ в таблицу размером и, которая уже содержит й элементов. Вероятность попадания на свободное место с первого раза в этом случае равна 1 — й/и. Одновременно это есть вероятность р! того, что потребуется только одно сравнение. Вероятность, что понадобится ровно одна вторая проба, равна вероятности конфликта при первой попытке, умноженной иа вероятность попадания на свободное место в следуюший раз.
В целом мы получаем вероятность р; того, что включение потребует ! проб: Р! = к И вЂ” и р, = — ' —, и и — 1' (4.93) й — 1 а — и з Рз= „ и — 1 и — 2 ' !т — 1 и — 2 й †!+2 и — и и и — 1 и — 2 ''' и — т+2 и — !+! 2!2 4. Динамические информиционные структуры Следовательно, среднее значение числа проб, требующихся при вставке (й+ 1)-го ключа, равно а+! и — и 1с и — и а+! Х 11 ц + и и — 1 +' ! ! ..+(у+1) —" " ' — ',' ... ' )= "+' ~Ь й — 1 и — 2 1 ) и+1 и и — 1 и — 2 ' и — а+!) и — 6+1* (4.94) Поскольку число проб при включении элемента равно числу проб при его поиске, результат (4.94) можно использовать для вычисления среднего числа Е проб, требующихся прн обращении к произвольному ключу в таблице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
