3.1. Поиск в неупорядоченных таблицах
 

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

При поиске всех элементов, отвечающих заданному условию поиска, осуществляется последовательный просмотр до конца таблицы, выбираются и обрабатываются все элементы, удовлетворяющие условию поиска. Оценка времени поиска. Минимальное время (длина) поиска, когда элемент нахо-дится в начале таблицы, O(1), максимальное время О(n), n — число элементов таблицы. Среднее время поиска при равновероятном распределении элементов в таблице О(n/2) т.е. О(n).

Рассмотрим пример, когда элемент таблицы содержит только целочисленный ключ, а поля данных отсутствуют. Таблица задана в виде одномерного массива целых чисел (ключей записей). Функция поиска возвращает индекс элемента либо -1 в случае отсутствия искомого элемента.
Пример.
/* ПОИСК ЭЛЕМЕНТА ПО СОВПАДЕНИЮ */
int poiski (int A[],int n, int k)
{ int i = 0;
while (A[i] != k && i < n)
i++;
return (A[i] == k) ? i : -1; }
}

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

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

Приведем пример использования заграждающего элемента.
Пример.
/* ПОИСК ПО СОВПАДЕНИЮ КЛЮЧА — ЗАГРАЖДАЮЩИЙ ЭЛЕМЕНТ* /
#include <stdio.h>
#include <conio.h>
#define size 10
int A[size] = {1,7,3,4,8,5,2,6,0,9};
mainQ
{ int poisk2(int A[],int n,int key);
int key ;
int ind;
printf("\n Поиск элемента по совпадению");
printf("\n Введите ключ поиска =>");
flushall();
scanf("%d",&key);
ind= poisk2(A,size,key);
if (ind == -1)
printf("\n Элемент %d не найден \n",key);
else
printf("\n Элемент %d имеет индекс %d\n",key,ind);
getch(); return 0;
}

/* ФУНКЦИЯ ПОИСКА ЭЛЕМЕНТА ПО СОВПАДЕНИЮ С ЗАГРАЖДАЮЩИМ ЭЛЕМЕНТОМ */
int poisk2(int A[],int n, int key)
{ int i = 0,r;
r=A[n-1];
A[n-1]=key;          /* заграждающий элемент */
while (A[i] != key )
i++;
A[n-1]=r;                /* восстановили последний элемент */
if ((i==n-1) && (r!=key))
return -1;
else return i;
}