源程序.c

哈希算法的描述

#define M 30//源表长
#define N  50//哈希表长
#define p 47//除数，为质数,且不能超过五十，初次散列的表达式：d=L[i].shuzhi%p;
             //再次散列的表达式：d=(d-1+(7*d))%p;（）
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.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;

hshlst H[N];

 Init_list(yuanbiao L[]){
    printf("init\n");
	L[0].name="陈红霞";L[0].pinyin="chenhonxia";
    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;	
    t=*a;
	for(i=0;*a!='\0';a++,i++)			
		t+=(*(a+i)); 
	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].dizhi=0;
		H[j].biaoji=0;
		H[j].sum=0;
	}
    printf("create nil hashist over\n");
	for(i=0;i<M;i++){
		d=L[i].shuzhi%p;//
		if(!H[d].biaoji){
			H[d].name=L[i].name;
			H[d].pinyin=L[i].pinyin;
			//strcpy(H[d].name,L[i].name);
			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-1+(7*d))%p;
			   t++;
			}
			H[d].name=L[i].name;
			H[d].shuzhi=L[i].shuzhi;
			H[d].pinyin=L[i].pinyin;
			H[d].dizhi=d;
			H[d].biaoji =1;
			H[d].sum=t;
		}//else*/
	}//for
	printf("end create\n");
}//create

/*search(hshlst H[]){
	int i,t,d;
	char *a,str[20];
	a=str;
	printf("please input the name you want to search:\n");
	scanf("%s",a);
	t=transform(a);
	d=t%p;
	if(H[d].biaoji){
		if(!(strcmp(a,H[d].pinyin)))
			printf("the person you want to search has found,")
	}






}*/

void main(){
    int i;
	yuanbiao L[M];	
    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");

    //**********创建哈希表
	create_hash(L,H);
    //**********创建哈希表

	//以下调试语句二
	for(i=0;i<N;i++)
		if(H[i].name!="")
		   printf("%s ",H[i].name);//差点气死我，%s写成了%d，让我调了一下午！！！
	/*printf("\n");
	printf("%s",H[1].name);
    printf("\n");
    printf("%s",H[0].name);
    printf("\n");*/
	//search(H);
}