![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Последовательный поиск
Под последовательным поиском понимается просмотр записей в том порядке, в котором они встречаются в наборе данных. Он заключается в последовательном сравнении аргумента поиска А с ключом каждой записи. Этот метод можно использовать для поиска в упорядоченной и неупорядоченной последовательности записей. При этом, если набор неупорядоченный, то последовательный способ поиска является единственным. В неупорядоченной последовательности сравненение ключей продолжается до тех пор, пока не будут просмотрены все N записей. Запись с искомым ключом выводится на печать. Структурограмма алгоритма последовательного поиска в неупорядоченной последовательности записей приведена на рис
Пример. Осуществить последовательный поиск аргумента 32 в массиве ключей: 37 25 32 29 20. i = 1: 37 25 32 29 20 i = 2: 37 25 32 29 20 i = 3: 37 25 32 29 20
Подчеркивание означает выбор Ki для сравнения с А. Поиск окончен удачно, ключ 32 имеет порядковый номер, равный 3. Пример реализации? function SearchPer (K: array of Integer; N, A: Integer): Integer; var I: Integer; begin Result: = -1; for I: = 1 to N do if K [I] = A then begin Result: = I; Exit; end; end;
Возможно ускорение работы последовательного поиска путем добавления в конец набора данных фиктивной записи XN+1 с ключом KN+1, равным аргументу поиска А. Структурограмма алгоритма последовательного поиска в этом случае будет выглядеть так, как представлена на рис.
Выигрыш в быстродействии здесь достигается за счет того, что проверка на окончание последовательности записей выполняется только один раз - при совпадении аргумента поиска с ключом записи. В последовательности, упорядоченной, например, по возрастанию ключей записей, поиск можно прекратить сразу же, как только значение ключа текущей записи превысит значение аргумента поиска. Для ускорения в конец списка добавляют фиктивную запись XN+1 с ключом KN+1, превышающим аргумент поиска А. Рис. Пример (на обороте) Если известно, что записи упорядочены, то существует несколько методов, которые могуть быть использованы для увеличения эффективности поиска.
|