福 建 工 程 学 院
课 程 设 计
课程： 算法与数据结构 题目： 哈希表 专业： 网络工程 班级： 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(\ 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(i 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(\ //若哈希地址冲突，进行冲突处理 benGetTime(); 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(); } （3）查找哈希表 void SearchHash1(HashTable* H,int c) //在通讯录里查找姓名关键字，若查找成功，显示信息 {int p,pp;NA str; system(\ //c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); printf(\请输入要查找记录的姓名：\\n\ scanf(\ 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(); } （4）显示哈希表 void ShowInformation(Record* a) //显示输入的用户信息 {int i; system(\ for( i=0;i （5）主函数的设计 void main(int argc, char* argv[]) {Record a[MAXSIZE]; int c,flag=1,i=0; HashTable *H; H=(HashTable*)malloc(LEN); for(i=0;i printf(\ \ printf(\ 欢迎使用同学通讯录录入查找系统 \ printf(\ 哈希表的设计与实现\ printf(\ 【1】. 添加用户信息 \ printf(\ 【2】. 读取所有用户信息 \ printf(\ 【3】. 以姓名建立哈希表(再哈希法解决冲突) \ printf(\ 【4】. 以电话号码建立哈希表(再哈希法解决冲突) \ printf(\ 【5】. 查找并显示给定用户名的记录 \ printf(\ 【6】. 查找并显示给定电话号码的记录 \ printf(\ 【7】. 清屏 \ printf(\ 【8】. 保存 \ printf(\ 【9】. 退出程序 \ printf(\ 温馨提示： \ printf(\ Ⅰ.进行5操作前 请先输出3 \ printf(\ Ⅱ.进行6操作前 请先输出4 \ 第%d 个用户信息:\\n 姓 名：%s\\n 学号：%s\\n 电话号 码：%s\\n\ 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课程设计--哈希表实验报告在线全文阅读。
相关推荐：