hash227.c

哈希算法的描述

#define M 30//源表长
#define N  50//哈希表长
#define p 47//除数，为质数,且不能超过五十，初次散列的表达式：d=L[i].shuzhi%p;
             //再次散列的表达式：d=(d-10+(7*d))%p
#define K 1000
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<malloc.h>
//#include<dos.h>
/*typedef struct {
    char * a;
	int length;
	int size;
}list;*/
typedef struct{
char *name;
char *pinyin;
int shuzhi;
}yuanbiao;

typedef struct{
//char *pinyin;
	char *name;//这里的名字和源表中一样
	char *pinyin;
	int shuzhi;
	int dizhi;//哈希元素的存放地址
	int biaoji;//
	int sum;//标记计算的次数
}hshlst;


typedef struct{
    hshlst *H;
	int length;
	int size;
}hashlist;

hashlist init_hashlist(){//唐
    hashlist T;
	//char a[20];
	//char b[20];
	T.H=(hshlst *)malloc(N*sizeof(hshlst));
	//T.H->name=a;
	//T.H->pinyin=b;
	T.length=0;
	T.size=N;
	return T;
}

check(char *a){//腾
//char *b;
//b=(char *)malloc((strlen(a)+1)*sizeof);
//strcpy(b,a);
while(*a!='\0')
	{
		if(!(*a>='a'&&*a<='z'))		{
			
           return 0;
		}
		a++;
	}

return 1;

}
//hshlst H[N];//还要记得把H的大小做成可变的！
int number;

 Init_list(yuanbiao L[]){//唐
    printf("init\n");
	L[0].name="陈红霞";L[0].pinyin="chenhongxia";
    L[1].name="王伟";L[1].pinyin="wangwei";
    L[2].name="胡军轻";L[2].pinyin="hujunqing";
    L[3].name="张海霞";L[3].pinyin="zhanghaixia";
    L[4].name="咸正海";L[4].pinyin="xianhaizheng";
    L[5].name="于蔡琰";L[5].pinyin="yucaiyan";
    L[6].name="郭兴燕";L[6].pinyin="guoxingyan";
    L[7].name="刘丽丽";L[7].pinyin="liulili";
    L[8].name="唐骏龙";L[8].pinyin="tangjunlong";
    L[9].name="高睿哲";L[9].pinyin="gaoruizhe";
    L[10].name="唐建雷";L[10].pinyin="tangjianlei";
    L[11].name="王雪域";L[11].pinyin="wangxueyu";
    L[12].name="李蒙山";L[12].pinyin="limengshan";
    L[13].name="任之文";L[13].pinyin="renzhiwen";
    L[15].name="高天骄";L[15].pinyin="gaotianjiao";
    L[14].name="刘通明";L[14].pinyin="liutongming";
    L[16].name="张秀美";L[16].pinyin="zhanxiumei";
    L[17].name="吴莹莹";L[17].pinyin="wuyinyyiny";
    L[18].name="刘晓强";L[18].pinyin="liuxiangqiang";
    L[19].name="乔守星";L[19].pinyin="qiaoshouxing";
    L[20].name="于后康";L[20].pinyin="yuhoukang";
    L[21].name="朱丽娟";L[21].pinyin="zhulijuan";
    L[22].name="付吉亮";L[22].pinyin="fujiliang";
    L[23].name="李谦诚";L[23].pinyin="liqiancheng";
    L[24].name="吴俊杰";L[24].pinyin="wujunjie";
    L[25].name="郑程博";L[25].pinyin="zhengchengbo";
    L[26].name="腾立涛";L[26].pinyin="tenglitao";
    L[27].name="孔伟政";L[27].pinyin="kongweizheng";
    L[28].name="庄佳";L[28].pinyin="zhuangjia";
    L[29].name="王迪";L[29].pinyin="wangdi";
    //L[30].name="赵栋栋";L[30].pinyin="zhangdong";//多了一个，转化时会使程序非正常终止
    //return L[M];//
	printf("init over\n");

}
//****************拼音转化为数字********************//
int transform(char *a){//唐	
	int t,i;
	char *b;
	b=a;
    t=*b;
	for(i=0;*a!='\0'&& i<strlen(a);a+=4,i+=4)//因为a的数组大小是20，如果不判断是否结束的话会出现负值
	//while(*a!='\0')
		//a++;		
	   t+=(*a); 
	//printf("%d \n",t);
	return t;
}

/*****************构建哈希表******************/
create_hash(yuanbiao L[],hshlst H[]){//高
	int i,j;
    int d,t;
	printf("begin create\n");
	for(j=0;j<N;j++){//置空哈希表
		H[j].name="";
		H[j].shuzhi=0;
        H[j].pinyin="";
	    H[j].dizhi=0;
		H[j].biaoji=0;
		H[j].sum=0;			
	}
    printf("create nil hashist over\n");//////
	/*printf("print\n");
	printf("%d\n",T.H[0].biaoji);*/
	/*for(i=0;i<M;i++)
		printf("%s ",L[i].name);
	printf("\n");*/

	for(i=0;i<M;i++){		
		d=L[i].shuzhi%p;//
		if(!H[d].biaoji){
			H[d].name=L[i].name;
			//printf("%s ",H[d].name);
			H[d].pinyin =L[i].pinyin;
			H[d].shuzhi=L[i].shuzhi;
			H[d].dizhi=d;
			H[d].biaoji =1;
			H[d].sum++;
			
		}//if
		else{
			t=1;
			while(H[d].biaoji){
			   d=(d-10+(7*d))%p;//这个地方刚开始写错了，写成了-500，结果到后面都不打印了！！！
			   t++;
			}
			H[d].name=L[i].name;
			
			//printf("%s ",H[d].name);
			H[d].pinyin =L[i].pinyin;
			H[d].shuzhi=L[i].shuzhi;
			H[d].dizhi=d;
			H[d].biaoji =1;
			H[d].sum=t;
			
		}//else*/
	}//for
	printf("end create\n");
}//create

/*insert(hshlst H[],char *a,int d){
	char temp[20];
	char *b;
	b=temp;

    printf("please input his(or her) chinese name:");
	scanf("%s",b);
	printf("\n");
	H[d].biaoji =1;
	H[d].dizhi =d;
	H[d].name =b;

}//insert*/

insert(hshlst H[],int flag){//高
	int d,t,s=1;
	char b[100],a[100];//b数组很值得研究
	//yuanbiao L[M];
	char *temp;

	if(flag)goto begin;
	printf("input the person's pinyin name\n");
rewrite:	scanf("%s",b);
	if(!check(b)){printf("input error!!\n");goto rewrite;}
    temp=(char *)malloc((strlen(b)+1)*sizeof(char));
	strcpy(temp,b);
	t=transform(temp);
	printf("%d\n",t);
	d=t%p;
	while(H[d].biaoji){
	    if(!strcmp(H[d].pinyin,b)){
		    printf("the data has exist!\n");
		    goto end;
		}
		else {
			d=(d-10+(7*d))%p;
			s++;
		}
	}			
begin:	
	//H[d].pinyin =b;
    H[d].pinyin=(char *)malloc((strlen(b)+1)*sizeof(char));
	strcpy(H[d].pinyin,b);
	H[d].shuzhi=t;
	H[d].dizhi=d;
	H[d].biaoji =1;
	H[d].sum=s;
	printf("please input the person's chinese name:\n");
	scanf("%s",a);
	//if(!(check(a))){printf("input error !re-put!");goto rewrite1;}
	H[d].name =(char *)malloc((strlen(a)+1)*sizeof(char));
	strcpy(H[d].name,a);
    //H[d].name=a;
	//printf("%s\n",H[d].name);	
end:return d;
}


int search(hshlst H[],char *a){//腾
	int t,d;
	char str[20];
	//char m;
	//a=str;	
	
	t=transform(a);
	
	//printf("t=%d\n",t);getch();//t变成了负数？？？
	d=t%p;
	
	while(H[d].biaoji){
		if(!(strcmp(a,H[d].pinyin))){
			//printf("the person you want to search has found,his(or her) chinese name is:%s\n",H[d].name);
			return d;
		}
		else
			d=(d-10+(7*d))%p;		
	}	
	//printf("no match!\n");
	return K;

}//search*/

showhash(hshlst H[]){
	int i,j=0,t;
    for(i=0;i<N;i++)
		if(H[i].pinyin!=""){
			j++;
			t=j%5;			
		    printf("%s ",H[i].pinyin);
			if(!t) printf("\n");			
		}

	printf("\n");
    //j=0;
	/*for(i=0;i<N;i++)
		if(H[i].dizhi){
			t=j%5;			
		    printf("%d ",H[i].dizhi);
			if(!t) printf("\n");
			j++;
		}*/
   number=j;
	return number;
}


deletehash(hshlst H[]){//腾
   char a[20];
   int j;
   printf("please input the pinyin name you want to delete\n");
   scanf("%s",a);
   j=search(H,a);
   //system("cls");
   if(j==K)printf("can't find the person you have input!\n");
   else{
	   
	   H[j].name="";
		H[j].shuzhi=0;
        H[j].pinyin="";
	    H[j].dizhi=0;
		H[j].biaoji=0;
		H[j].sum=0;	
   }
}

 ASL(hshlst H[]){//唐
	int i,n=0,sum=0;
	 
	float ave;
    for (i=0;i<N;i++){
		if(H[i].sum){
		   sum+=H[i].sum;
		   n++;
		}
	}
	printf("%d\n",sum);
	printf("%d\n",n);
	ave=sum/n;
	printf("the ASL is %f\n",ave);
	
}




void main(){//高
    int i,d,j;
	char t[20];
	yuanbiao L[M];	
	hashlist T;
	char a[20];
	T=init_hashlist();	
    Init_list(L);
	printf("trans\n");
	for(i=0;i<M;i++)//因为transform函数要被两次调用到，故用此写法
	    L[i].shuzhi=transform(L[i].pinyin);
	printf("trans over\n");
	//以下是调试用句1,显示转化后的数字
	//***********************
	/*printf("begin\n");
	for(i=0;i<M;i++)
		printf("%d ",L[i].shuzhi);
	printf("end\n");*/
	//*****************调试用句1,显示拼音的转化值

    //**********创建哈希表

	create_hash(L,T.H);T.length =N;
	printf("\n");
	//system("cls");//清屏

    //**********创建哈希表
     
	//以下调试语句二，显示哈希表中的姓名
	//***************//
	/*printf("show\n");
	for(i=0;i<N;i++)
		if(T.H[i].name!="")
		   printf("%s ",T.H[i].name);
		printf("\n");*/
	//***************调试语句二，显示哈希表中的姓名**//
loop:printf("------哈希表查找--------\n");
	 printf("please choose one number\n");
	 
	 printf("1.show the hashlist\n");
	 printf("2.search one name from the hashlist\n");
	 printf("3.insert into one data\n");
	 printf("4.delete one data\n");
	 printf("5.see the ASL of the hashlist\n");
	 printf("6.exit \n");
	 scanf("%s",t);
	 i=atoi(t);
	 if(i==6){printf("thank you ,bye bye\n");exit(1);}
	 if(i==2){
		 printf("please input the name you want to search:\n");
rewrite:scanf("%s",a);
			 if(!check(a)){printf("非法输入！！");goto rewrite;}
		 j=search(T.H,a);
		 if(j==K) printf("no match!\n");
		 else
			 printf("the person you want to search has found,his(or her) chinese name is:%s\n",T.H[j].name);

		 goto loop;
	 }
     if(i==1){showhash(T.H);goto loop;}
	 if(i==3){
		 //printf("input the pinyin\n");
		 //scanf("%s",a);
		 d=insert(T.H,0);
		 printf("%d\n",T.H[d].dizhi);
		 goto loop;
	 }
	 if(i==4) {deletehash(T.H);goto loop;}
	 if(i==5){ASL(T.H);goto loop;}
	 printf("input error!please input again.\n");goto loop;
	
	
}