дающими элемент, который будет использоваться в каче-ре барьера isentinel):

Iprocedure je<?rcA(x: integer; у яг root: ref); таг w: ref;. begin w root; sentinel.key :~ x; while w1.key x do w := wt-next; if Ф seniTnelthm w\.count := w.count + 1 else

tbegin (новый элемент} w :~ root; Tiew(root); (4.21) Viitbroot\ do begin/irej := jc; count:~ 1; next :== w end end end {search}

Разумеется, в этом примере плохо используется мощность и гибкость связанного списка; при поиске можно допустить линейный просмотр всего списка только в том случае, если число элементов ограниченно. Однако легко найти подходящее усовершенствование: поиск в упорядоченном списке. Если список упорядочен (например, по возрастанию ключей), то поиск заканчивается не позднее чем встретится первый ключ, больший, чем искомый. Упорядочение списка достигается включением новых элементов не в начало, а в соответствующие по порядку места. Фактически благодаря легкости включения в связанный список упорядочение обеспечивается почти без дополнительных затрат, т. е. его гибкость используется полностью. Массивы и файлы такой возможности не дают. (Однако заметим, что даже упорядоченные списки не предоставляют ничего эквивалентного бинарному поиску в массивах.)

. Поиск в упорядоченном списке - типичный пример ситуации, описанной в (4.15), когда элемент нужно вставлять перед данным, а именно перед первым элементом, имеющим больший ключ. Однако предложенный здесь прием отличен от fore, который применялся в (4.15). Вместо копирования значений при проходе списка используются две ссылки: w2 отстает на один шаг от wl и, таким образом, указывает на есто включения, когда wl находит слишком большой ключ. общем виде этап включения показан на рис. 4.10. Предварительно мы должны рассмотреть два обстоятельства:

Ссылка на новый элемент (шЗ) должна присваиваться 2\.next, кроме случая, когда список еще пуст. Для простоты и эффективности мы предпочитаем не использовать Для проведения этого различия условный оператор. Един-

ственный способ избежать этого - добавить в начап списка фиктивный элемент. °

2. Проход по списку с двумя ссылками, спускающимися расстоянии в один щаг, требует, чтобы список содержал меньщей мере один элемент (кроме фиктивного). Поэтоы включение первого элемента следует проводить иначе, всех остальных.

Процедура построенная в соответствии с этими указа-ниями, приведена в (4.23). Она использует вспомогательную

Рис. 4.10. Включение в упорядоченный список.

процедуру insert ( включение ), которую нужно локально описать в search. Она размещает в памяти и инициирует новый элемент шЗ, таким образом:

procedure ref);

таг w3: ref; begin new(w3);

with wSt do , 22)

beginfcey :=: x; count:~ 1; next:~ w end ; wl\.next w2 end {insert}

Инициация roof :=:ni! в программе 4.1 соответственно заменяется на

new(root); root \.next := nil

В соответствии с рис. 4.10 мы определяем условие переходе к следующему элементу при просмотре списка; оно состоит из двух частей, а именно:

(w\\ .key <х)А {wl\.пех1фт\)

jjje приведена процедура поиска:

gedure searchix: integer; var root: ref); var wl,w2: ref;

jegin w2 := root; wl := w2t.Rex/; jf wl = nil then insert (nil) else begin

-vAlifr (wl-t.fey < v) A (wlt-wecf Ф nil) do ,

begin w2 := wl; wl .И'2.иел:?

end ;

#if wlt./cey = X then w.count := wl.count + 1 else

end {-ейгсй} ;

К сожалению, несмотря на всю нашу осторожность, сюда вкралась ошибка. Мы предлагаем читателю, прежде чем двигаться дальше, найти здесь логический подвох. Тем же, кто предпочитает избежать этой работы детектива, достаточно сказать, что (4.23) будет всегда проталкивать включенный первым элемент в конец списка. Ошибку можно исправить, указав, что, если поиск заканчивается при невыполнении второй части условия, новый элемент нужно включать после ш1 f, а не перед ним. Следовательно, оператор insert (ш1) заменяется на

begin if wMext = nil then

begin 2 := wl; wl := ш ! end; (4.24)

msert{wl)

Увы, доверчивый читатель вновь введен в заблуждение, так как алгоритм (4.24) по-прежнему неверен. Чтобы обнаружить ошибку, предположим, что новый ключ лежит между последним и предпоследним ключами. Это приведет к тому, что обе Части условия продолжения цикла окажутся ложными, когда будет достигнут конец списка, и, следовательно, включение произойдет после конечного элемента. Если тот же ключ появится позже, он будет включен правильно и, таким образом, Окажется в таблице в двух местах. Это можно исправить, Заменив условие

wlf.next = nil

ь (4.24) на

wli.tiey < х