《数据结构》课程设计报告
（3）关键字的比较
Status eq(NA x,NA y){//关键字比较，相等返回SUCCESS；否则返回FAILURE
if(strcmp(x,y)==0)
return SUCCESS; else return FAILURE;
}Status NUM_BER; //记录的个数
(4)对姓名的折叠处理
long fold(NA s){//人名的折叠处理
char *p; long sum=0; NA ss;
strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\\0') sum+=*p++;
printf(\//将字符串转换成一个int 型的值用于hash表的计算比较
return sum; }
（5）建立哈希函数（两个） int Hash1(NA str){ //哈希函数
long n; int m;
n=fold(str); //先将用户名进行折叠处理
m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数 return m; }
10
//并返回模值
《数据结构》课程设计报告
int Hash2(NA str){ //哈希函数
long n; int m;
n = atoi(str); //把字符串转换成整型数. m=n%HASHSIZE; return m; }
（6）解决冲突
Status collision(int p,int &c){ //冲突处理函数，采用二次探测再散列法解决冲突
int i,q; i=c/2+1; while(i if(c%2==0){ c++; q=(p+i*i)%HASHSIZE; return q; //并返回模值 if(q>=0) else } else{ i=c/2+1; q=(p-i*i)%HASHSIZE; c++; if(q>=0) Else } } return FAILURE; } 11 return q; i=c/2+1; 《数据结构》课程设计报告 （7）创建以姓名为关键字哈希表 void CreateHash1(HashTable* H,Record* a){ //建表，以人的姓名为关键字，建立相应的散列表 //若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;i p=Hash1(a[i].name); pp=p; while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0){ printf(\第%d记录无法解决冲突\需要显示冲突次数时输出 continue; }//无法解决冲突，跳入下一循环 } H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入 H->count++; printf(\第%d个记录冲突次数为%d。\\n\需要显示冲突次数时输出 } printf(\以教师姓名建散列表完成!\\n此哈希表容量为%d,当前表内存储的记录个数为%d.\\n\ benGetTime(); } 12 《数据结构》课程设计报告 (8)查找以姓名为关键字的哈希表（前提条件是步骤7要先创建好哈希函数） void Search_name(HashTable* H,int &c){//在通讯录里查找姓名关键字，若查找成功，显示信息 //c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); NA str; printf(\请输入要查找记录的姓名：\\n\scanf(\int p,pp; p=Hash1(str); pp=p; while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1)) pp=collision(p,c); if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){ printf(\查找成功！\\n查找过程冲突次数为%d．以下是您需要要查找的信息：\\n\\n\printf(\ 姓 名 : %s\\n 电 话 号 码 ： %s\\n 联 系 地 址：%s\\n\} else printf(\此人不存在，查找不成功!\\n\ benGetTime(); } （9）创建以电话号码为关键字的哈希表 void CreateHash2(HashTable* H,Record* a){//建表，以电话号码为关键字，建立相应的散列表 //若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;i 13 《数据结构》课程设计报告 p=Hash2(a[i].tel); pp=p; while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0){ printf(\第%d记录无法解决冲突\需要显示冲突次数时输出 continue; }//无法解决冲突，跳入下一循环 } H->elem[pp]=&(a[i]);//求得哈希地址，将信息存入 H->count++; printf(\第%d个记录冲突次数为%d。\\n\需要显示冲突次数时输出 } printf(\以教师电话号码建散列表完成!\\n此哈希表容量为%d,当前表内存储的记录个数为%d.\\n\ benGetTime(); } （10）查找以电话号码为关键字的哈希表（前提为步骤9要先创建好哈希函数） void Search_phonenumber(HashTable* H,int &c){//在通讯录里查找电话号码关键字，若查找成功，显示信息 //c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); NA tele; printf(\请输入要查找记录的电话号码：\\n\scanf(\int p,pp; p=Hash2(tele); pp=p; while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1)) pp=collision(p,c); 14