2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Хеширование в Си
Сообщение23.05.2010, 21:04 
ребят, помогите как-нибудь получше реализовать программу
Работа состоит из двух частей: сортировка и поиск.
1. Сортировка. Выполнить сортировку массива записей с использованием хеш-функции. В качестве записей взять фамилии студентов гр. записанные латиницей, в алфавитном порядке. Для получения ключа использовать 3 и 4 символы. Преобразовать ключ в адрес с использованием заданной хеш-функции согласно своему варианту задания. Способ разрешения коллизий – использование области переполнения. Оценить хеш-функцию (2/3 записей должны располагаться в основной области).

2.Поиск. Ввести искомый ключ, преобразовать его в адрес. В основной области поиск выполнять по хеш-функции, в области переполнения – последовательный поиск. Отметить, где найдена запись (в основной области или области переполнения) или запись не найдена.
алгоритм перемешивания: сдвиг разрядов
окончательное вычисление хеш-функции:умножение на константу
Код:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char fams[32][15]={""};
char osn[32][15];
char dop[32][15];

int kluch(char *f)
{ int a,b,hash;
  a=f[0];
  b=f[3];
  if(a<100)
    hash=a%10;//если код первой буквы двузначный, то берем число единиц в качестве младшего разряда.
  else hash=a%32;//код буквы больше 100 => берем число единиц по другой формуле
  if(b<100) // аналогично первой цифре, только берем старший разряд
    hash=hash+b/10;
  else hash=hash+b/100;
  return(hash);
}
int  main()
{
  int i,d=0,g,a,n,min,max,c;
    float Plotnost;
    char p[15];
      min=kluch(fams[0]);//начальные значения
    max=kluch(fams[0]);
    for(i=1;i<32;i++)
    {
      g=kluch(fams[i]);
      if (min>g) min=g;
      if (max<g) max=g;
         }

    printf("min=%d\t max=%d\n",min,max);
     c=31/((float)max - (float)min);//вычисляем вещественную константу
    printf("c=%f\n",c);



    for (i=0; i<32; i++)
   {
         strcpy(osn[i],"");
         strcpy(dop[i],"");
      }

    /*хеширование - распределение записей по основной и дополнительной памяти  */
    for (i=0; i<32; i++)
        {
          g=kluch(fams[i]);
          if (strcmp(osn[g],"")==0)strcpy(osn[g],fams[i]);
                         else {strcpy(dop[d],fams[i]);d++;}
     }
     /*вывод на экран содержимого основной и доп. памяти */
     printf ("Основная область\n");
     for (i=0;i<32;i++)
     if (strcmp(osn[i],"")!=0) printf ("%d - %s\n",i,osn[i]);

     printf ("Дополнительная область\n");
     for (i=0;i<d;i++)
     printf("%d - %s\n", i, dop[i]);

     Plotnost=(31-((float)d+1))/32;
  printf("плотность = %5.2f\n",Plotnost);
     /*поиск записей*/
     printf("\n Хотите воспользоваться поиском? (1-да, 0-нет)\n");
     scanf("%d",&a);
     while (a!=0)
     {
         printf("введите искомую  фамилию\n");
         scanf("%s",&p);
         g=kluch(p);//*c;
         if (strcmp(osn[g],p)==0)
             printf("находится в основной памяти на %d - месте\n",g);
         else{
             i=0;
             while((i<d)&&(strcmp(p,dop[i])!=0))
                i++;
             if(strcmp(p,dop[i])==0)  printf("находится в дополнительной памяти на %d - месте\n",i);
                                      else printf(" фамилия отсутствует\n");
            }

         printf("Хотите воспользоваться  поиском? (1-да, 0-нет)\n");
         scanf("%d",&a);
    }
}


конкретно интересует как сделать так,ч то плотность была больше

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group