Алгоритмы поиска

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

Рассмотрим алгоритм поиска на примере программы – словаря. Пусть в ЭВМ введена таблица-словарь из n русских и английских слов вида табл. 5.

Словарь Таблица 5

Размер таблицы фиксирован и известен.

Таблица должна храниться в виде двух массивов слов, причем русскому слову с номером 3 ("метка") соответствует английское с таким же номером ("lable") и т.д.

Далее при работе программы должны вводиться английские слова, а программа должна выводить на экран их русские эквиваленты. Если слова в словаре нет, то выводится "не знаю". Перевод введенного слова на русский язык осуществляется путем его сравнения с каждым английским словом из таблицы. Если слово найдено, то перевод выполняется.

Простейший алгоритм поиска - линейный. При этом эталонный массив просматривается последовательно от первого до последнего элемента. Наиболее сложный случай, когда слова нет в словаре (не найдено). Суждение об этом можно сделать только по окончании просмотра всего массива.