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

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

Последовательный поиск предполагает последовательный просмотр всех записей множества, организованного как массив.
Пример: Найти в массиве элемент со значением, равным 3.

#include <stdio.h>
#include <stdlib.h>
int search(int *k, int n, int key) {
  int index = -1;
  for(int i=0; i<n; i++) {
    if(k[i] == key) {
      index = i;
      break;
    }
  }
  return(index);
}
int main() {
  int i, k[8];
  int point;
  system("chcp 1251");
  system("cls");
  for(i=0;i<8;i++) {
    printf("Введите k[%d]: ",i);
    scanf("%d",&k[i]);
  }
  point = search(k,8,3);
  if(point == -1)
    printf("Элементов равных 3 в массиве нет!\n");
  else
    printf("Элемент с индексом %d равен 3", point);
  getchar(); getchar();
  return 0;
}
Метод транспозиции

Улучшением рассмотренного метода является метод транспозиции: каждый запрос к записи сопровождается сменой мест этой и предшествующий записи; в итоге наиболее часто используемые записи постепенно перемещаются в начало таблицы; и при последующем обращении к ней запись будет находиться почти сразу.

int search(int *k, int n, int key) {
  int index = -1;
  int temp;
  for(int i=0; i<n;i++) {
    if(k[i] == key) {
      index = i;
      if(index==0)
        break;
      temp = k[i];
      k[i] = k[i-1];
      k[i-1] = temp;
      break;
    }
  }
  return(index);
}
int main() {
  int i, k[8];
  int point;
  system("chcp 1251");
  system("cls");
  for(i=0;i<8;i++) {
    printf("Введите k[%d]: ",i);
    scanf("%d",&k[i]);
  }
  for(i=0; i<6; i++) {
    point = search(k,8,3);
    if(point == -1)
      printf("Элементов равных 3 в массиве нет!\n");
    else
      printf("Элемент с индексом %d равен 3", point);
  }
getchar(); getchar();
  return 0;
}

Результат выполнения
Метод транспозиции

Метод перемещения в начало

Каждый запрос к записи сопровождается её перемещением в начало таблицы; в итоге в начале таблицы оказывается запись, используемая в последний раз.

int search(int *k, int n, int key) {
  int index = -1;
  int temp;
  for(int i=0; i<n;i++) {
    if(k[i] == key) {
      index = i;
      temp = k[i];
      k[i] = k[0];
      k[0] = temp;
      break;
    }
  }
  return(index);
}

Назад

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

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