Как отладить реализацию зондирования quadrati c для таблиц ha sh в C без использования указателей?

Question

Я просто пытаюсь реализовать quadrati c зондирование для таблиц ha sh, которые должны работать для любого размера таблицы. Код, который я написал ниже, работает, только если размер таблицы ha sh равен 10.

По сути, я должен установить ограничение на время l oop, до которого зондирование может происходить максимально , Я проверил вручную и обнаружил, что для размера таблицы 10 каждые 6 позиций индекса повторяются. Поэтому я установил ограничение 6 на время l oop.

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

#include <stdio.h>
#include<stdlib.h>
#define TS 10

int ht[TS]={};

void insert()
{
  int key,i=0,ind,s=0,hk;
  // printf("\nenter a value to insert into htasht table\n");
  scanf("%d",&key);
  hk=key%TS;

  while(s!=6)// limit=6 which is working only for table size 10
  {
    ind=(hk+i)%TS;
    if(ht[ind] == 0 )
    {
      ht[ind]=key;
      break;
    }
    s=s++;
    i=(s*s)%TS;
  }
  if(s==6)
  {
    printf("value cant be inserted\n");
  }
}

int search(int key)
{

  int ind,i=0,hk,s=0;
  hk=key%TS;
  while(s!=6)
  {
    ind=(hk+i)%TS;
    if(ht[ind]==key)
    {
      printf("value is found at ind %d\n ",ind);
      return ind;
      //      break;
    }s=s++;
    i=(s*s)%TS;
  }
  if(s==6)
  {
    printf("value not found\n");
    return 0;
  }
  //  return 0;
}

void display()
{

  int i;

  printf("\nelements in thte htasht table are \n");

  for(i=0;i< TS; i++)

  printf("\n ind %d -- value = %d",i,ht[i]);

}

void del(int key)
{
  int i,ind;
  ind=search(key);
  if(ind)
  {
    ht[ind]=0;
    printf("deleted");
  }

  ind=0;
}


void main()
{
  int opt,key,n;

  /*printf("Enter step size of hash table\n");
scanf("%d",&s);
*/
  while(1)
  {
    printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Delete\t 5.exit \n");
    scanf("%d",&opt);
    switch(opt)
    {
    case 1:printf("Enter how many values you want to enter\n");
      scanf("%d",&n);
      printf("enter values\n");
      for(int j=0;j<n;j++)
      {insert();}
      // insert();
      break;
    case 2:
      display();
      break;
    case 3:
      printf("Enter search element\n");
      scanf("%d",&key);                search(key);
      break;
    case 4:
      printf("Enter element to be deleted\n");
      scanf("%d",&key);//search(key);
      del(key);
      break;
    case 5:exit(0);
    }
  }
}

Answer 1

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

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

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

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

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

• Из тривиально следует, что максимальное количество зондов, необходимое для данного ключа, равно размеру таблицы ha sh.

Этого можно достичь, но избежать ограниченных размеров таблицы в различные способы. В статье Википедии на топиках c явно перечислены два из них, первый из которых выглядит особенно многообещающим:

• Выберите размер таблицы в виде степени 2 и AND, вместе при таких размерах таблицы
• Используйте числа tri angular в качестве датчиков (0, 1, 3, 6, 10, ...). Это добросовестный квадратичный c зонд, поскольку они соответствуют значениям квадратичной c функции p = ( i + i ² ) / 2

Обратите внимание, что числа tri angular также очень легко вычислить как последовательность: если T _i обозначает число i ^th tri angular (с индексами, начинающимися с 0, например, T ₀ = 0), затем T _i = T _i-1 + i для всех для i больше 0 .