谁能帮忙写一个C语言的哈希排序？小女感激不尽~~

Question

RT
最好简洁一些
谢谢啦

Answer 1

1.选择合适的哈希函数H(key)=key%p(p为小于或等于哈希表长的最大质数)；
2.计算各个关键字的直接哈希函数值；
3.根据处理冲突的方法建立哈希表，并输出；
4.在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。

#include<stdlib.h>
#include<stdio.h>
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
} ElemType;
int haxi(KeyType key,int m) /*根据哈希表长m，构造除留余数法的哈希函数haxi*/
{
int i,p,flag;
for(p=m;p>=2;p--) /*p为不超过m的最大素数*/
{
for(i=2,flag=1;i<=p/2&&flag;i++)
if(p%i==0)
flag=0;
if(flag==1)
break;
}
return key%p; /*哈希函数*/
}
void inputdata(ElemType **ST,int n) /*从键盘输入n个数据，存入数据表ST(采用动态分配的数组空间)*/
{
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\nPlease input %d data:",n);
for(i=1;i<=n;i++)
scanf("%d",&((*ST)[i].key));
}
void createhaxi(ElemType **HASH,ElemType *ST,int n,int m) /*由数据表ST构造哈希表HASH，n、m分别为数据集合ST和哈希表的长度*/
{
int i,j;
(*HASH)=(ElemType *)malloc(m*sizeof(ElemType));
for(i=0;i<m;i++)
(*HASH)[i].key=NULL; /*初始化哈希为空表(以0表示空)*/
for(i=0;i<n;i++)
{
j=haxi(ST[i].key,m); /*获得直接哈希地址*/
while((*HASH)[j].key!=NULL)
j=(j+1)%m; /*用线性探测再散列技术确定存放位置*/
(*HASH)[j].key=ST[i].key; /*将元素存入哈希表的相应位置*/
}
}
int search(ElemType *HASH,KeyType key,int m,int *time) /*在表长为m的哈希表中查找关键字等于key的元素，并用time记录比较次数，若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/
{
int i;
*time=1;
i=haxi(key,m);
while(HASH[i].key!=0&&HASH[i].key!=key)
{
i++;
++*time;
}
if(HASH[i].key==0)
return -1;
else
return i;
}
main()
{
ElemType *ST,*HASH;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\nPlease input n&&m(n<=m)"); /*输入关键字集合元素个数和哈希表长*/
scanf("%d%d",&n,&m);
inputdata(&ST,n); /*输入n个数据*/
createhaxi(&HASH,ST,n,m); /*创建哈希表*/
printf("\nThe haxi Table is\n"); /*输出已建立的哈希表*/
for(i=0;i<m;i++)
printf("%5d",i);
printf("\n");
for(i=0;i<m;i++)
printf("%5d",HASH[i].key);
do /*哈希表的查找，可进行多次查找*/
{
printf("\nInput the key you want to search:");
scanf("%d",&key);
i=search(HASH,key,m,&time);
if(i!=-1) /*查找成功*/
{
printf("\nSuccess,the position is %d",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失败*/
{
printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContiue(y/n):\n"); /*是否继续查找yes or no*/
ch=getch();
}
while(ch=='y'||ch=='Y'); /*计算表在等概率情况下的平均查找长度，并输出*/
for(stime=0,i=0;i<n;i++)
{
search(HASH,ST[i].key,m,&time);
stime+=time;
}
printf("\nThe Average Search Length is %5.2f",(float)stime/n);
ch=getch();
}