哈希表算法实现的c语言源程序.cpp

哈希表算法实现的C语言源程序

#include <stdio.h>
#include <string.h>
#include <stdlib.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],hashlist[50][20];
  int c; 
  do{printf("\n\n     主菜单\n     ");
     printf("\n   1.创建哈希表\n     ");
     printf("\n   2.查找哈希表中指定的人\n    ");
     printf("\n   3.退出程序  \n    ");
     printf("\n   请输入你的选择:");
     scanf("%d",&c);
     switch(c)
     {case 1:{creathash(hashlist,30);}break;
      case 2:{printf("\n   please input your search name:");scanf("%c",name);gets(name);search(hashlist,name);}break;
      case 3:exit(0);
     }
  }while(c<=3);
}
/*建哈希表*/
void creathash(char hash[][20],int n)
{int i,j;
	unsigned long int s,l;
	char name[20];
	for(i=0;i<50;i++)
	strcpy(hash[i],"null");          /*哈希表初值:null*/
	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);
		}
	}
}
/*mid函数先把参数平方，然后取中间的第4、5位作为地址返回*/
unsigned long int mid(unsigned long int s)        
{
	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");
}