Последовательный поиск
Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и
список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения
Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается
ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.
Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним
Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi -
относительная частота использования элемента Кi в В, а Si - количество сравнений,
необходимое для его поиска, то
n
Max{А} = max{ Si, i=1,n } ; Avg{А} = Pi Si .
i=1
Последовательный поиск предусматривает последовательный просмотр всех элементов списка В
в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно,
что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел
за пределы списка, что достигается использованием стоппера.
Очевидно, что Max последовательного поиска равен N. Если частота использования каждого
элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При
различной частоте использования элементов Avg можно улучшить, если поместить часто
встречаемые элементы в начало списка.
Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим
программу для последовательного хранения элементов Кi и поиска среди них элемента,
равного V, причем такого элемента может и не быть в списке. Без использования стоппера
программа может быть реализована следующим образом:
/* последовательный поиск без стоппера */
#include
main()
{
int k[100],v,i;
for (i=0;i<100;i++) scanf("%d",&k[i]);
scanf("%d",&v); i="0"; while(k[i]!="v" && i<100) i++;
if (k[i]="=v)" printf("%d %d",v,i);
else printf("%d не найден",v); }
С использованием стоппера программу можно записать в виде:
/* последовательный поиск со стоппером */
#include
main()
{
int k[101],v,i;
for (i=0;i<100;i++) scanf("%d",&k[i]);/* ввод данных*/
scanf("%d",&v); k[100]="v;" /* стоппер */
i="0;" while(k[i]!="v)" i++;
if (i<100) printf ("%d %d",v,i);
else printf ("%d не найден",v); }