Для индексно-последовательного поиска в дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной.
Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующей этому ключу. Элементы в индексной таблице, как элементы в основной таблице, должны быть отсортированы по этому ключу.
Если индекс имеет размер, составляющий 1/8 от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице.
Если размер основной таблицы — n, то размер индексной таблицы — ind_size = n/8.
Достоинство алгоритма индексно-последовательного поиска заключается в том, что сокращается время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.
Реализация индексно-последовательного поиска на языке Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h> // для использования функций system()
int main()
{
int k[20]; // массив ключей основной таблицы
int r[20]; // массив записей основной таблицы
int i, j, ind_size;
int key;
int kindex[3]; // массив ключей индексной таблицы
int pindex[3]; // массив индексов индексной таблицы
system("chcp 1251"); // перевод русского языка в консоли
system("cls"); // очистка окна консоли
// Инициализация ключевых полей упорядоченными значениями
k[0] = 8; k[1] = 14;
k[2] = 26; k[3] = 28;
k[4] = 38; k[5] = 47;
k[6] = 56; k[7] = 60;
k[8] = 64; k[9] = 69;
k[10] = 70; k[11] = 78;
k[12] = 80; k[13] = 82;
k[14] = 84; k[15] = 87;
k[16] = 90; k[17] = 92;
k[18] = 98; k[19] = 108;
// Ввод записей
for (i = 0; i < 20; i++)
{
printf("%2d. k[%2d]=%3d: r[%2d]= ", i, i, k[i], i);
scanf("%d", &r[i]);
}
// Формирование индексной таблицы
for (i = 0, j = 0; i < 20; i = i + 8, j++)
{
kindex[j] = k[i]; // переносим каждый 8-й ключ в индексную таблицу
pindex[j] = i; // запоминаем текущий индекс
}
ind_size = j; // запоминаем размер индексной таблицы
pindex[j] = 20; // последний индекс равен 20
// Поиск
printf("Введите key: "); // вводим ключевое поле
scanf("%d", &key);
// Просматриваем элементы индексной таблицы
for (j = 0; j < ind_size; j++)
{
if (key < kindex[j]) // если находим ключ меньше введенного,
break; // выходим из цикла - мы нашли нужную область основной таблицы
}
if (j == 0) i = 0; // присваиваем i начальный индекс диапазона поиска в основной таблице
else i = pindex[j - 1];
for (i; i<pindex[j]; i++) // осуществляем поиск в основной таблице
{ //до следующего индекса индексной таблицы
if (k[i] == key) // если найдено введенное значение, выводим его
printf("%2d. key=%3d. r[%2d]=%3d", i, k[i], i, r[i]);
}
getchar(); getchar();
return 0;
}
Результат выполнения
Назад: Алгоритмы сортировки и поиска
Комментариев к записи: 3