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

Простейшей формой поиска является последовательный поиск. Этот поиск применяется к таблице, которая организована или как массив, или как связанный список [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;

}

}

…

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

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

Если таблица упорядочена по уменьшающемуся или увеличивающемуся значению ключа записей, то последовательный поиск по такой таблице эффективен. Он требует намного меньше сравнений, чем в не отсортированной таблице [3].

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

Для увеличения эффективности поиска в отсортированном файле существует другой метод, но он приводит к увеличению требуемого пространства. Этот метод называется индексно-последовательным методом поиска. В дополнение к отсортированному файлу заводится некоторая вспомогательная таблица, называемая индексом. Каждый ее элемент состоит из ключа k_index и указателя на запись в файле, соответствующую этому ключу p_index. Элементы в таблице index должны быть отсортированы по этому ключу также как и элементы в файле. Рассмотрим пример такого построения [3].

Рис. 4.1. Индексно-последовательный файл

Алгоритм, используемый для поиска в индексно-последовательном файле, прост.

Пусть k_index будет массивом ключей в индексе, и пусть p_index будет массивом указателей внутри индекса на записи в файле. Пусть данный файл представлен в виде массива, n — размер файла, n_index — размер таблицы индекса; тогда алгоритм может быть представлен следующим фрагментом программы:

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

…

search=0;

i=1;

while ((i<=nindex) && (kindex[i]<=key)) i:=i+1;

// установить lowlim на наименьшую возм. позиц.в таблице

if (i==1) lowlim=1;

else lowlim=pindex[i-1];

//установить hillim на наиб. возм. позиц.в таблице

if (i==nindex+1) hillim=n; // последний элемент

else hillim=pindex[i];

// поиск в таблице от позиции lowlim по дозиции hilim

for (j= lowlim;j<= hillim;j++)

{

if (k[j]==key )

{

search:=j; cout<<”Элемент найден. Его номер =”<< j;

return;

}

}

…

Последовательный поиск вначале выполняется по меньшей таблице индекса. Когда найден индекс или диапазон, где ключ должен находиться, то дальнейший поиск выполняется по небольшой части записей самой таблицы.

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

Рис. 4.2. Использование вторичного индекса

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

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

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