Программирование на языке С - Последовательный поиск

 

2.3.1. Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К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); }