2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Хеширование в Си
Сообщение23.05.2010, 21:04 


21/06/09
171
ребят, помогите как-нибудь получше реализовать программу
Работа состоит из двух частей: сортировка и поиск.
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 сообщение ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group