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

Алгоритмы сортировки и поиска / Индексно-последовательный поиск

Для индексно-последовательного поиска в дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной. Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующей этому ключу. Элементы в индексной таблице, как элементы в основной таблице, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий 1/8 от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице.

Индексная таблица

Если размер основной таблицы — n, то размер индексной таблицы — ind_size = n/8.

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

Реализация индексно-последовательного поиска
#include <stdio.h>
#include <stdlib.h>
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("%d. k[%d]= %d: r[%d]=",i,i,k[i],i);
    scanf("%d",&r[i]);
  }
// Формирование индексной таблицы
  for(i=0, j=0;i<20;i=i+8) {
    kindex[j] = k[i];
    pindex[j] = i;
    j++;
  }
  ind_size = j;
  pindex[j] = 20;
// Поиск
  printf("Введите key: ");
  scanf("%d",&key);
  for(j=0; j<ind_size; j++) {
    if(key < kindex[j])
      break;
  }
  if(j==0)  i=0;
  else        i = pindex[j-1];
  for(i; i<pindex[j];i++) {
    if(k[i]==key)
      printf("%d. key= %d. r[%d]=%d",i,k[i],i,r[i]);
  }
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат индексно-последовательного поиска
Назад

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *