哈希表.cpp

针对某一集体中的人名(30人)设计一哈希表

#include <stdio.h>
#include <string.h>
void creathash(char hash[][20],int n);
unsigned long int mid(unsigned long int s);
void search(char hash[][20],char name[]);
void main()
{	
	char name[20];
	char hashlist[50][20];
	creathash(hashlist,30);
	printf("enter the name for search:");
	gets(name);
	search(hashlist,name);
}
void creathash(char hash[][20],int n)   /*建哈希表*/
{	int i,j;
	unsigned long int s,l;
	char name[20];
	/*printf("test");*/
	for(i=0;i<50;i++)
	strcpy(hash[i],"null");          /*哈希表初值:null*/
	/*printf("test2");*/
	for(i=0;i<n;i++)
	{
		printf("input the name:\n"); gets(name);
		s=0;j=0;
		while(name[j]!='\0') s+=name[j++];
		l=mid(s)%47;                  /*除留余数法定位*/
		if(strcmp(hash[l],"null")==0)
			strcpy(hash[l],name);
		else{
			do{l=(l+17)%47;              /*补偿性线性探测*/
			}while(strcmp(hash[l],"null")!=0);
			strcpy(hash[l],name);
		}
	}
}
unsigned long int mid(unsigned long int s)         /*mid函数先把参数平方，然后取中间的第4、5位作为地址返回*/
{
	int i=0,a[10];	
	unsigned long int d=1,s0;
	s0=s*s;
	while(s0>d) d*=10;
	d/=10;
	while(d!=0){
		a[i++]=s0/d;                /*分离出s0的各位放在数组a中*/
		s0=s0%d;
		d=d/10;
	}
	return(a[3]*10+a[4]);           /*取中间第4、5位返回*/
}
void search(char hash[][20],char name[])
{
	unsigned long s=0,l;
	int i=0;
	while(name[i]!='\0') s+=name[i++];
	l=mid(s)%47;
	if(strcmp(hash[l],name)==0)
	{
		printf("found!at %d\n",l);
		return;
	}
	while((strcmp(hash[l],name)!=0)&&(strcmp(hash[l],"null")!=0))
		l=(l+17)%47;                /*探测*/
	if(strcmp(hash[l],name)==0)	
		printf("found!at %d\n",l);
	else printf("no found!\n");
}