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

АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА

Алгоритмы поиска решают задачу поиска определенного элемента путем просмотра существующих элементов списка один за другим. Хотя в алгоритме последовательного поиска не имеет значения, отсортирован ли список, но лучший результат достигается в отсортированном списке. Обычно поиск применяется не только для того, чтобы проверить, есть ли нужный элемент в списке, но и для извлечения информации, которая имеет это ключевое значение. Например, ключ-значение может быть порядковым номером искомого элемента или другим уникальным (унифицированным) идентификатором. Как только нужный ключ найден, программа может изменить данные, соответствующие этому ключу, или просто извлечь все записи. Алгоритм поиска в любом случае применяется для решения задачи определения местоположения ключа. Вот почему алгоритмы поиска выделяют индекс записи, содержащий нужный ключ, в качестве результата. Если ключ-значение не найдено, то алгоритм поиска возвращает значение индекса, которое больше верхней границы массива. Мы предполагаем, что элементы списка пронумерованы с использованием чисел от 1 до n для достижения цели. В этом случае алгоритм выдаст значение 0, если искомый ключ не существует в списке. Для простоты извлекаемые ключи-значения воспринимаются как не повторяющиеся в списке.
Алгоритм последовательного поиска просматривает от первого элемента списка до последнего элемента, пока не найдет искомый элемент. Из этого следует, что чем дальше значение ключа находится в списке, тем дольше длится поиск (относительно времени). Это обстоятельство необходимо будет учитывать при анализе алгоритма последовательного поиска.
Поиск в этом представлении используется, когда данные неупорядочены или их структура неясна. При этом данные последовательно просматриваются в оперативной памяти по всей таблице, начиная с небольшого адреса и заканчивая большим. Последовательный поиск в массиве (переменная search хранит порядковый номер найденного элемента).
Алгоритм последовательного поиска на языке C# будет выглядеть следующим образом:
int qidiruv(int key){
for (int i=0;i
if (k[i]==key) { search = i;return search;}
search = -1;
return search;
}}
Эффективность алгоритма последовательного поиска в массиве можно определить по количеству выполненных сравнений M. Mmin = 1, Mmax = n. Если данные распределены с одинаковой вероятностью в ячейке массива, то хрупкость равна n (n + 1)/2
Если нужный элемент отсутствует в таблице и его необходимо добавить в таблицу, то последние два оператора в алгоритме, приведенном выше, заменяются следующим образом.
n=n+1;
k[n-1]:=key;
r[n-1]:=rec;
search:=n-1;
return search;
Если таблица данных представлена в виде односвязного списка (рис.1), то в списке выполняется последовательный поиск.
Рисунок 1. Вид односвязного списка
Линейный регистр-это программа для поиска элемента, соответствующего ключевому слову, с помощью метода последовательного поиска.
Node *q=NULL;
Node *p=lst;
while (p !=NULL){
if (p->k == key){
search = p;
return search;
}
q = p;
p = p->nxt;
}
Node *s=new Node;;
s->k=key;
s->r=rec;
s->nxt= NULL;
if (q == NULL){ s->nxt=lst; lst = s; }
else q->nxt = s;
search= s;
return search;
Преимущество структуры списка заключается в том, что добавление или удаление элемента в списке выполняется быстро, при этом добавление или удаление элемента не зависит от количества элементов, в то время как в массиве добавление или удаление элемента требует перемещения половины всех элементов в среднем. Эффективность поиска в списке примерно такая же, как и в массиве.