Подробнее это действие описывается оператором (4.17)-

v/hile РФ nil do

begin Р{р\); р:=р\.next и

end )

Из определения оператора цикла с предусловием и списк вой структуры следует, что Р будет выполнено для всех эп° ментов списка и пи для каких других.

Очень частая операция - поиск в списке элемента с зд данным ключом х. Так же как в случае файлов, поиск ведетсд строго последовательно. Он заканчивается, либо когда эле-мент найден, либо когда достигнут конец списка. Снова пред, положим, что начало списка обозначено ссылкой р. Первая jnonbiTKa сформулировать задачу такого поиска приводит к следующему:

v/hile (p=7nil) Л (рЬкеуфх) do р :=p\.next (4.18)

Однако следует заметить, что при р = nil не существует р\. Следовательно, вычисление условия окончания может потре-бовать обращения к несуществующей переменной (в отличие от переменной с неопределенным значением) и может привести к ошибке при выполнении программы. Это можно исправить, используя либо явный выход из цикла, выраженный оператором безусловного перехода (4.19), либо вспомогательную булевскую переменную, отмечающую, найден или нет нужный ключ (4.20),

wblie ? nil do

if p.key X then goto Found (19)

else p p]Mext

Использование оператора безусловного перехода требует присутствия в каком-то месте метки для перехода; несовместимость этого оператора с оператором цикла видна из того факта, что условие while при этом вводит в заблуждение: тело цикла не обязательно выполняется, пока р ф nil.

b :- true;

while (p nil) Л Ь do

. . if p].key X tbm b false (4.20)

else p := p\.next

{(;;=nil)V-nfc}

4.3.2. Упорядоченные списки и реорганизация списков

Алгоритм (4.20) сильно напоминает подпрограммы О' иска при просмотре массива или файла. В самом файл - это в сущности линейный список, в котором гехни!

Л с последующим элементом остается неопределенной или аъйОУ^- Поскольку элсментарныс операции над файлами не дускают включение новых элементов (разве что в конец) ° удаление (разве что уничтожение всех элементов), у раз- яботчика есть большая возможность выбора способов представления, и он может использовать также- последовательное (-положение, помещая следующие одна за другой компо-яенть! в емежнью области памяти. Линейные списки с яв-яыми ссылками обеспечивают большую гибкость и поэтому йХ следует использовать, когда требуется такая дополнитель-дая гибкость.

В качестве примера мы рассмотрим теперь задачу, к которой будем постоянно обращаться в этой главе, чтобы продемонстрировать на ней работу различных методов. Она состоит в чтении некоторого текста, выборе из него всех осталь-Hbix слов и подсчете частоты их появления, т. е. в составлении частотного словаря.

Очевидно, что для этого нужно составить список слов, найденных в тексте. Каждое очередное слово, прочитанное в тексте, ищется в списке. Если слово найдено, счетчик его частоты увеличивается, в противном случае слово добавляется к списку. Мы будем называть этот процесс просто о-иском, хотя ясно, что в него входит также и включение.

Чтобы сосредоточить внимание на основной задаче обработки списка, мы предположим, что слова уже выделены из исследуемого текста, закодированы целыми числами и находятся во входном файле.

Формулировка этой процедуры, называемой search (поиск), непосредственно следует из (4.20). Переменная root указывает на начало списка, в который вставляются новые лова, это действие определено в (4.12). Полный алгоритм описан в программе 4.1; здесь есть подпрограмма для распечатки полученного списка слов в виде таблицы. Печать таблицы служит примером действия, выполняемого с каждым элементом списка один раз, схема этого процесса уже была приведена в (4.17).

Алгоритм линейного просмотра в программе 4.1 напоминает процедуру поиска в массивах и файлах, где, в частности, попользуется простой способ упрощения условия окончания Цикла: использование барьера. При поиске по списку также ожно пользоваться барьером, он представляется фиктивным Лементом в конце списка. Новая процедура (4.21), заменяю-Ц^зя процедуру поиска в программе 4.1, предполагает, что Добавлена глобальная переменная sentinel и что инициация, временной гоо^ заменена операторами

ц., nexsisentinel); root sentinel;

program list (input,output)i (простое включение в список] type ref = Iword;

word record key: integer;

count: integer; next: ref

end ;

m k: integer; root: ref;

procedure search (x: integer; var root: ref); var w: refjbr boolean;

.begin w :=5 root; Ь := true; while (yvФтai) A b йо

if wl.key = л: then b := fcJse else w :== wf.wx/; if b then

begin [новый элемент] w : roo/; TJevf (/-ooO; withroo/f do

begin Jtey := л:; count := 1; лел/ w end end else

Tvt.couH/ :== wxount + 1 end [search) ;

procedureprintlist (w: ref); begin while w ?ь nil do

begin writeln (w].key, w\.count); w := w.next

end {printlist} ; begin root := nil; read(k); while ?b 0 do

begin уей'гсЛ (Ar, TOoO; efl<i?(fc) end ; printlist(root) end .

Программа 4.1. Включение в список.