Рассмотрим алгоритмы на языке С++, реализующие различные виды поиска.
В примерах таблицы поиска содержат только целочисленный ключ, а поля данных отсутствуют. Таблицы поиска задаются в виде одномерных массивов целых чисел (ключей записей).
Функция поиска для элемента по совпадению в неупорядоченной таблице возвращает индекс элемента либо -1 в случае отсутствия искомого элемента и имеет следующий вид:
/* ФУНКЦИЯ ПОИСКА ЭЛЕМЕНТА ПО СОВПАДЕНИЮ */
int poisk1(int A[],int n,int key)
{ int j = 0;
while (A[j] != key && j < n-1)
j++;
return (A[j] == key) ? j : -1;
}
Как было сказано выше, для улучшения алгоритма поиска можно использовать заграждающий элемент или барьер. В этом случае последняя запись таблицы запоминается, а после завершения поиска восстанавливается в таблице. В последний элемент массива заносится ключ поиска, и образуется так называемый заграждающий элемент.
Теперь на каждом шаге поиска осуществляется только одно сравнение, а сам поиск продолжается до нахождения элемента с заданным ключом. Если искомого элемента в исходной таблице не было, поиск закончится на барьере. Таким образом, использование барьера в случае числовых ключей существенно сокращает число сравнений. Если ключом поиска является символьная строка, то использование заграждающего элемента вряд ли оправдано.
/* ПОИСК ЭЛЕМЕНТА ПО СОВПАДЕНИЮ С ЗАГРАЖДАЮЩИМ ЭЛЕМЕНТОМ */
int poisk2(int A[],int n,int k)
{ int i = 0;
A[n] = k;
while (A[i] != k )
i++;
return (i == n) ? -1 : i;
}
Как было сказано выше, в случае, если последовательность упорядочена по возрастанию (убыванию), можно использовать более эффективные методы поиска. Приведем листинг примера программы, которая осуществляет бинарный поиск в упорядоченной по возрастанию последовательности чисел.
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ Вариант 1 */
int bisearch1(int A[],int n,int key)
{ int li,rj,k;
li=0; rj=n-1;
while ( li <= rj )
{ k = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
else return k;
printf(" li=%d, rj=%d, k=%d ",li,rj,k);/* отладочная печать*/
}
return -1;
}
/* ========================================== */
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА Вариант 2,
оба варианта равноценны */
int bisearch(int A[],int n,int key)
{ int li,rj,k;
li=0; rj=n-1; k = li;
while ( li <= rj && A[k] != key )
{ k = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
}
return (A[k] == key) ? k : -1;
}
Еще одним эффективным методом поиска в упорядоченной таблице данных является индексно-последовательный поиск. Рассмотрим листинг программы, реализующей данный вид поиска в упорядоченной таблице данных.
/*ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК*/
#include <iostream.h>
#include <conio.h>
struct index
{
int kind; int pind;
};
int poisk(int *mas) /*Функция индексно-последовательного поиска*/
{
const int n = 10;
int step, m;
cout<<"\n Введите шаг поиска \n";
cin>>step;
m = n/step;
int key;
cout<<"Введите ключ поиска"<<endl;
cin>>key;
index* masindex = new index [m];
int i =0;
int j =step-1;
int search;
while ((i<m)&&(mas[j]<=key)&&(j<n))
{
/*masindex[i].idx=i;*/
masindex[i].kind=mas[j]; masindex[i].pind=j;
if (masindex[i].kind == key)
{
search = j; delete mas; return search;
}
j=j+step; i++;
}
int hi, low;
if (i==0)
low = 0;
else
low = masindex[i-1].pind;
if (i == m)
hi =n-1;
else
hi = j - 1;
cout<<"Значение LOW = "<<low<<endl;
cout<<"Значение HIGH = "<<hi<<endl;
for (int z = low;z<=hi; z++)
{
if(key == mas[z])
{
search =z;
delete mas;
return search;
}
}
search=-1;
delete mas;
return search;
}
void main()
{
clrscr();
const int n = 10;
int mas[n];
cout <<" ----Ввод элементов массива в возрастающем порядке-----"<<endl;
for(int j = 0; j<n;j++)
{cout <<" Введите элемент массива с идексом "<<j<<endl; cin>>mas[j];}
int result;
result = poisk(mas);
if (result == -1)
cout<<"\n Таких элементов нет!\n";
else
cout<<"Найденный элемент имеет индекс = "<<result<<endl;
getch();
}
Следует обратить внимание, что в данном листинге для обеспечения ввода шага поиска пользователем используется динамический массив.