Хеширование:

[Necare]

Может быть у кого-нибудь, когда- нибудь было такое задание:

1. Реализовать интерактивное приложение со следующей функциональностью, использующее вышеописанный модуль.
a. Создание хеш-таблицы заданного размера при запуске приложения (размер указывает пользователь).
b. Вставка элемента.
c. Поиск элемента с заданным ключом.
d. Изменение элемента.
e. Удаление элемента с заданным ключом.
f. Распечатка хеш-таблицы (постраничная или в текстовый файл).

Предусмотреть возможность чтения исходных данных из текстового файла.
При тестировании предусмотреть следующие варианты:
1. Количество введенных данных существенно меньше размера хеш-таблицы (коллизий не возникает)
2. Количество введенных данных соответствует размеру хеш-таблицы
3. Количество введенных данных больше размера хеш-таблицы

Тип ключа - целое число на интервале [0 , +1 000 000 000]. Метод хеширования - выбор цифр. Метод разрешения коллизий - двойное хеширование.

Реализация на C++.

Если да - скиньте пожалуйста.

[Necare]

ну или хотя бы посдкажите что за метод: хеширование интодом выбора цифр.

[p51x]

На лекции должны были давать. По названию похоже на:
для элемента выбирается целое число на интервале [0 , +1 000 000 000]

[Necare]

Да. Пришлось долго беседовать с преподом, что бы она объяснила, что мне нужно делать. она сама не поняла задание.

[Necare]

Вот код(метод разрешения коллизий - линейное зондирование, собсно код к заданию почти не имеет отношения )

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#include<string.h>
#include<stdlib.h>
struct Qwe
{
 char valuee[100];
 float key;
};
Qwe **symtab;

const float nullItem = -11000;

//хеш функция
int Hash(float key, int size)
{
 float C,code,codee;
 C=(sqrt(5)-1)/2;             //
 code=key*C;                  //hash fun
 codee=(code-(int)code)*size; //
 if(codee<0)
  return abs(codee);
 return (codee);
}

//вывод хеш-таблицы
void vivod(int size)
{
 int Q;
 float C,code;
 C=(sqrt(5)-1)/2;

 printf("  Хеш-код значения   Ключ    Значение\n");
 for(int i=0;i<size;i++)
  {
    if(symtab[i]!=NULL&&symtab[i]->key!=nullItem)
   {
      code=symtab[i]->key*C;
      Q=(code-(int)code)*size;
      printf("%d.  %8.2d   %10.4f   %s\n",i,Q, symtab[i]->key,symtab[i]->valuee);
     }
    else printf("%d.\n",i);
  }
}


//удаление элемента
void remove(int size, float key)
{
 int h;
 h=Hash(key,size);

 while(symtab[h]!=NULL)
 {
  if(symtab[h]->key==key)
    symtab[h]->key= nullItem;

 if(h==size)
  h=-1;
 h++;
 }
}

int check(int size)
{
 int fl=0;
 for(int i=0;i<size;i++)
  {
   if(symtab[i]==NULL)
    fl=1;
  }
  return fl;
}

//поиск элемента
void lookup(float key, int create, char *value, int size)
{
 int h,fl,i;
 Qwe *sym;
 h=Hash(key,size);

 i=1;
 if(create==0)
 {
 printf("     Ключ      Значение\n");
 while(symtab[h]!=NULL||symtab[h+size-1]==NULL)
 {
  if(symtab[h]->key==key)
   {
    printf("%d.   %.2f   %s\n",i,symtab[h]->key,symtab[h]->valuee);
   }

 if(h==size)
  h=-1;
 i++;
 h++;
 }
 }
 if(create==1)
  {
   fl=0;


   while(!fl)
   {
    if(symtab[h]==NULL || (key==symtab[h]->key&&!strcmp(symtab[h]->valuee,value)))
    {
      sym=new Qwe;
      sym->key=key;
      strcpy(sym->valuee,value);
      symtab[h]=sym;
      fl=1;
    }
    else
    {
     if(h<size)
      {
       h++;
      }
      else h=0;
    }
   }

  }
}


//изменение элемента
void change(int size, float key, char *value)
{
 int h;
 h=Hash(key,size);
 while(symtab[h]!=NULL||symtab[h]->key==nullItem)
  {
   if(symtab[h]->key==key)
    strcpy(symtab[h]->valuee,value);
   h++;
  }
}


void main()
{
textbackground(9);
 clrscr();
 FILE *fo;
 int size,param,i,l=20;
 char *value,s[20],*vvalue,ss[20];
 float key;
 Qwe *temp;
size=15;
 symtab=new Qwe*[size];
 for(i=0;i<size;i++)
  {
   symtab[i]=NULL;
  }

 do {
 clrscr();
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 1.       Вставка элемента в таблицу        |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 2.    Чтение исходных данных из файла      |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 3.    Поиск элемента с заданным ключом     |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 4.   Удаление элемента с заданным ключом   |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 5.  Изменение элемента с заданным ключом   |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 6.           Вывод хеш-таблицы             |\n");
 printf("\t\t+--------------------------------------------+\n");
 printf("\t\t| 0.                   Выход                 |\n");
 printf("\t\t+--------------------------------------------+\n");
 scanf("%d",&param);

 switch (param)
 {
  case 1:
     {
      clrscr();

     for(i=0;i<size;i++)
      if(symtab[i]->key == nullItem)
	symtab[i]=NULL;



      int qa=check(size);
      if(qa==0)
       {
	printf("Tablica zapolnena!!\n");
	getch();
	break;
       }
      printf("Vvedite kluch: ");
      scanf("%f",&key);
      printf("Vvedite znachenie: ");
      scanf("%s",value);
      lookup(key,1,value,size);
     }
     break;
  case 2:
     {
		      clrscr();
		      int mm=0;
		      fo=fopen("e:\\1.txt","r");
		      if  (fo==NULL)
			 puts("Ошибка открытия файла\n");
		      else
			 {
			    do
			    {
			      fgets(s,l,fo);
			      key=atof(s);
			      sprintf(vvalue,&s[8]);
			      int z=strlen(vvalue);
			      strcpy(ss,vvalue);
			      if(ss[z-1]=='\n')
			      ss[z-1]='\0';
			      if(ss[z]=='\n')
			      ss[z]='\0';
			      if(strcmp(ss,"\0")!=0)
				lookup(key,1,ss,size);
			      mm++;
			      if(mm==size)
			      {
			       puts("Таблица заполнена!!");
			       break;
			      }
			    } while(!feof(fo));
			    puts("Элементы из файла добавлены в хеш-таблицу");
			 }
		      fclose(fo);
		      getch();

     }
     break;
  case 3:
     {
      clrscr();
      printf("Vvedite kluch: ");
      scanf("%f",&key);
      clrscr();
      lookup(key,0,"",size);
      getch();
     }
     break;

[Necare]

case 4:
     {
      clrscr();
      printf("Vvedite kluch: ");
      scanf("%f",&key);
      remove(size,key);
     }
     break;
  case 5:
     {
      clrscr();
      printf("Vvedite kluch: ");
      scanf("%f",&key);
      printf("Vvedite znachenie: ");
      scanf("%s",value);
      change(size,key,value);
     }
     break;
  case 6:
     {
      clrscr();
      vivod(size);
      getch();
     }
     break;
  }
 }
  while(param!=0);
 fflush(stdin);
 getch();
}