福建工程学院课程设计
课程：算法与数据结构
题目：哈希表
专业：网络工程
班级： xxxxxx班
座号： xxxxxxxxxxxx
姓名： xxxxxxx
2011年 12 月 31 日
实验题目：哈希表
一、要解决的问题
针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。
基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。
运行的环境：Microsoft Visual C++ 6.0
二、算法基本思想描述
设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。
三、设计
1、数据结构的设计和说明
（1）结构体的定义
typedef struct //记录
{
NA name;
NA xuehao;
NA tel;
}Record;
录入信息结构体的定义，包含姓名，学号，电话号码。
typedef struct //哈希表
{
Record *elem[HASHSIZE]; //数据元素存储基址
int count; //当前数据元素个数
int size; //当前容量
}HashTable;
哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。
2、关键算法的设计
（1）姓名的折叠处理
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("\nsum====================%d",sum);
return sum;
}
（2）建立哈希表
1、用除留余数法构建哈希函数
2、用线性探测再散列法处理冲突
int Hash1(NA str) //哈希函数
{
long n;
int m;
n=fold(str); //先将用户名进行折叠处理
m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数
return m; //并返回模值
}Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{
int i,q;
i=c/2+1;
while(iif(c%2==0){
c++;
q=(p+i*i)%HASHSIZE;
if(q>=0) return q;
else i=c/2+1;
}
else{
q=(p-i*i)%HASHSIZE;
c++;
if(q>=0) return q;
else i=c/2+1;
}
}
return UNSUCCESS;
}
void benGetTime();
void CreateHash1(HashTable* H,Record* a) //建表，以人的姓名为关键字，建立相应的散列表
{ int i,p=-1,c,pp;
system("cls"); //若哈希地址冲突，进行冲突处理
benGetTime();
for(i=0;ic=0;
p=Hash1(a[i].name);
pp=p;
while(H->elem[pp]!=NULL) {
pp=collision(p,c);
if(pp<0){
printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出
continue;
} //无法解决冲突，跳入下一循环
}
H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入
H->count++;
printf("第%d个记录冲突次数为%d。\n",i+1,c); //需要显示冲突次数时输出
}
printf("\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count);
benGetTime();
}
（3）查找哈希表
void SearchHash1(HashTable* H,int c) //在通讯录里查找姓名关键字，若查找成功，显示信息
{int p,pp;NA str;
system("cls"); //c用来记录冲突次数,查找成功时显示冲突次数
benGetTime();
printf("\n请输入要查找记录的姓名：\n");
scanf("%s",str);
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查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c);
