Комбинаторные алгоритмы для программистов



             

Последовательный поиск - часть 3


Единственным недостатком алгоритма 13.2 является то, что при безуспешном поиске (поиске имен, которых нет в таблице) всегда просматривается вся таблица. Если такой поиск возникает часто, то имена надо хранить в естественном порядке; это позволяет завершать поиск, как только при просмотре попалось первое имя, большее или равное аргументу поиска. В этом случае в конец таблицы следует добавить фиктивное имя

\infty
для того, чтобы гарантировать выполнение условия завершения (
\infty
- это новое имя, которое по предположению больше любого имени из пространства имен
S
). Таким образом получаем алгоритм 13.3.

 x_{n+1} \leftarrow \infty

i

1 while z > xi do i
i+1 if z=xi then{найдено:i указывает на z} else{не найдено}


Алгоритм 13.3.Последовательный поиск по таблице, хранимой в естественном порядке




Содержание  Назад  Вперед