ребят, помогите как-нибудь получше реализовать программу
Работа состоит из двух частей: сортировка и поиск.
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);
}
}
конкретно интересует как сделать так,ч то плотность была больше
