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

Простейшей формой поиска является последовательный поиск. Этот поиск применяется к таблице, которая организована или как массив, или как связанный список [3].

Предположим, что k есть некоторый массив из n ключей, а r — некоторый массив записей, такой, что k(i) является ключом для r(i). Предположим также, что key является некоторым аргументом поиска. Мы хотим установить в переменную searchнаименьшее целое число i, такое что k(i) = key, если такое i существует, и 0 в противном случае. Алгоритм выполнения этих действий следующий:

search=0;

for( i=1; i<=n; i + +)

{

if(key = = k[i]) search = i;

}

Этот алгоритм может быть просто модифицирован для того, чтобы добавлять некоторую запись recс ключом keyв таблицу, если ключ keyне находится в таблице. Следующие операторы добавляются в приведенные выше:

if( search = = 0)

{

n++; // увеличиваем размер таблицы

k[n] = key // вставляем новый ключ и запись

r[n]= rec;

search = n;

}

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

// key — искомый ключ записи

…

flag=false;

qq=q; // q — указатель на начало списка

i=0; // n — число элементов в списке

while( (flag==false) && (i<=n))

{

i++;

if (qq->key==key)

{

q1=q; // q1 — указатель на искомый элемент

cout<<”Запись найдена\n”;

flag=true;

}

else

{

q2=qq; // q2 – указатель, ссылающийся.ся на qq

qq=qq->next;

}

// вставка элемента zapis с заданным ключом key в начало списка

if (flag==false)

{

item *kon=new kon(next,key,nam); // kon - указатель на ячейку

kon->next=q;

kon->key=key;

kon->nam=zapis;

q=kon;

}

// удаление элемента с ключом key из списка

else

{

q2.next=q1.next;

delete q1;

}

}

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