散列表的设计与实现报告.docx
《散列表的设计与实现报告.docx》由会员分享，可在线阅读，更多相关《散列表的设计与实现报告.docx（17页珍藏版）》请在冰点文库上搜索。
散列表的设计与实现报告
数据结构课程设计
题目：
散列表的设计与实现
专业：
计算机科学与技术
指导教师：
李竹林
姓名：
刘朋飞（14）
何伟（12）
一、需求分析：
1.任务需求：
设计散列表实现电话号码查找系统；
2.功能需求：
.设每个记录有下列数据项：
电话号码、用户名、地址；
.从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
.采用一定的方法解决冲突；
.查找并显示给定电话号码的记录；
.查找并显示给定用户名的记录；
3.其他功能：
.系统功能的完善；
.设计不同的散列函数，比较冲突率；
.在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化；
二、总体设计：
1.系统功能设计：
定义电话本记录数量（MAXSIZE）、表长（HASHSIZE）、姓名长度（MAX_SIZE）以和结构体typedefstruct的内容，构造两个哈希函数hash1和hash2。
功能示意图：
2.系统功能设计：
增加系统功能如下:
添加用户信息;读取所有用户信息;以姓名建立哈希表;以电话号码建立哈希表;查找并显示给定用户名的记录;查找并显示给定电话号码的记录;清屏以和保存功能；
处理流程示意图：
3.功能模块设计：
.运用main函数输出电话本信息系统的整体界面，在调试运行后如下：
.利用添加功能voidgetin（Record*a）实现用户信息的录入，在调试运行后如下：
.利用哈希函数CREATEHASH1.2来构造哈希表并用Statuscollision函数的相应功能来查找并解决冲突：
.利用voidSearchHash1（HashTable*H,int&c）在通讯录里查找姓名关键字，若查找成功，显示信息，c用来记录冲突次数,查找成功时显示冲突次数：
三、详细设计与实现部分：
定义头文件和基本属性
#include
#include
#include
#include
#include
#defineMAXSIZE20//电话薄记录数量
#defineMAX_SIZE20//人名的最大长度
#defineHASHSIZE53//定义表长
#defineSUCCESS1
#defineUNSUCCESS-1
#defineLENsizeof（HashTable）
typedefintStatus;
typedefcharNA[MAX_SIZE];
定义结构体
typedefstruct{//记录
NAname;
NAtel;
NAadd;
}Record;
typedefstruct{//哈希表
Record*elem[HASHSIZE];//数据元素存储基址
intcount;//当前数据元素个数
intsize;//当前容量
}HashTable;
关键字比较功能的实现
Statuseq（NAx,NAy）{//关键字比较，相等返回SUCCESS；否则返回UNSUCCESS
if（strcmp（x,y）==0）
returnSUCCESS;
elsereturnUNSUCCESS;
}
记录个数功能的实现
StatusNUM_BER;//记录的个数
输入信息功能
voidgetin（Record*a）{//键盘输入各人的信息
cout<<"输入要添加的个数：
\n";
cin>>NUM_BER;
inti;
for（i=0;icout<<"请输入第"<\n";
cin>>a[i].name;
cout<<"请输入第"<\n";
cin>>a[i].tel;
cout<<"请输入第"<\n";
cin>>a[i].add;//gets（str2）;?
?
?
?
?
?
}
}
显示输入信息的实现
voidShowInformation（Record*a）//显示输入的用户信息
{
inti;
for（i=0;icout<<"\n第"<\n姓名：
"<"<"<}
清屏功能的实现
voidCls（Record*a）{
cout<<"*";
system（"cls"）;
}
longfold（NAs）{//人名的折叠处理
char*p;
longsum=0;
NAss;
strcpy（ss,s）;//复制字符串，不改变原字符串的大小写
strupr（ss）;//将字符串ss转换为大写形式
p=ss;
while（*p!
='\0'）
sum+=*p++;
cout<<"\nsum===================="<returnsum;
}
构造哈希函数
intHash1（NAstr）{//哈希函数
longn;
intm;
n=fold（str）;//先将用户名进行折叠处理
m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数
returnm;//并返回模值
}
intHash2（NAstr）{//哈希函数
longn;
intm;
n=atoi（str）;//把字符串转换成整型数.
m=n%HASHSIZE;//用除留余数法构造哈希函数
returnm;//并返回模值
}
冲突处理函数，用于解决冲突
Statuscollision（intp,int&c）{//冲突处理函数，采用二次探测再散列法解决冲突
inti,q;
i=c/2+1;
while（iif（c%2==0）{
c++;
q=（p+i*i）%HASHSIZE;
if（q>=0）returnq;
elsei=c/2+1;
}
else{
q=（p-i*i）%HASHSIZE;
c++;
if（q>=0）returnq;
elsei=c/2+1;
}
}
returnUNSUCCESS;
}
voidbenGetTime（）;
voidCreateHash1（HashTable*H,Record*a）{//建表，以人的姓名为关键字，建立相应的散列表benGetTime（）;
inti,p=-1,c,pp;
for（i=0;ic=0;
p=Hash1（a[i].name）;
pp=p;
while（H->elem[pp]!
=NULL）{
pp=collision（p,c）;
if（pp<0）{
cout<<"第"<continue;
}//无法解决冲突，跳入下一循环
}
H->elem[pp]=&（a[i]）;//求得哈希地址，将信息存入
H->count++;
cout<<"第"<}
cout<<"\n建表完成!
\n此哈希表容量为"<count<<".\n";
benGetTime（）;
}
查找功能的实现
voidSearchHash1（HashTable*H,int&c）{//在通讯录里查找姓名关键字，若查找成功，显示信息
benGetTime（）;
NAstr;
cout<<"\n请输入要查找记录的姓名：
\n";
cin>>str;
intp,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）{
cout<<"\n查找成功！
\n查找过程冲突次数为"<\n\n";
cout<<"姓名：
"<elem[pp]->name<<"\n电话号码：
"<elem[pp]->tel<<"\n联系地址：
"<elem[pp]->add<<"\n";
}
elsecout<<"\n此人不存在，查找不成功!
\n";
benGetTime（）;
}
voidbenGetTime（）{
SYSTEMTIMEsys;
GetLocalTime（&sys）;
cout<}
voidCreateHash2（HashTable*H,Record*a）{//建表，以电话号码为关键字，建立相应的散列表
benGetTime（）;
inti,p=-1,c,pp;
for（i=0;ic=0;
p=Hash2（a[i].tel）;
pp=p;
while（H->elem[pp]!
=NULL）{
pp=collision（p,c）;
if（pp<0）{
cout<<"第"<continue;
}//无法解决冲突，跳入下一循环
}
H->elem[pp]=&（a[i]）;//求得哈希地址，将信息存入
H->count++;
cout<<"第"<\n";//需要显示冲突次数时输出
}
cout<<"\n建表完成!
\n此哈希表容量为"<count<<".\n";
benGetTime（）;
}
voidSearchHash2（HashTable*H,int&c）{//在通讯录里查找电话号码关键字，若查找成功，显示信息
benGetTime（）;
NAtele;
cout<<"\n请输入要查找记录的电话号码：
\n";
cin>>tele;
intp,pp;
p=Hash2（tele）;
pp=p;
while（（H->elem[pp]!
=NULL）&&（eq（tele,H->elem[pp]->tel）==-1））
pp=collision（p,c）;
if（H->elem[pp]!
=NULL&&eq（tele,H->elem[pp]->tel）==1）{
cout<<"\n查找成功！
\n查找过程冲突次数为"<\n\n";
cout<<"姓名：
"<elem[pp]->name<<"\n电话号码：
"<elem[pp]->tel<<"\n联系地址：
"<elem[pp]->add<<"\n";
}
elsecout<<"\n此人不存在，查找不成功!
\n";
benGetTime（）;
}
存盘功能的实现：
voidSave（）{
FILE*fp;
if（（fp=fopen（"c:
\test.txt","w"））==NULL）{
printf（"\nERRORopeningcustometfile"）;
}
fclose（fp）;
}
主界面功能的实现：
intmain（intargc,char*argv[]）{
intc,flag=1;
HashTable*H;
H=（HashTable*）malloc（LEN）;
for（inti=0;iH->elem[i]=NULL;
H->size=HASHSIZE;
H->count=0;
Recorda[MAXSIZE];
while
（1）{
cout<<"\n┏━━━━━━━━━━━━━━━━━━━━━┓";
cout<<"\n┃欢迎使用电话号码查找系统┃";
cout<<"\n┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓";
cout<<"\n┃★★★★★★★哈希表的设计与实现★★★★★★★┃";
cout<<"\n┃【1】.添加用户信息┃";
cout<<"\n┃【2】.读取所有用户信息┃";
cout<<"\n┃【3】.以姓名建立哈希表（再哈希法解决冲突）┃";
cout<<"\n┃【4】.以电话号码建立哈希表（再哈希法解决冲突）┃";
cout<<"\n┃【5】.查找并显示给定用户名的记录┃";
cout<<"\n┃【6】.查找并显示给定电话号码的记录┃";
cout<<"\n┃【7】.清屏┃";
cout<<"\n┃【8】.保存┃";
cout<<"\n┃【9】.退出程序┃";
cout<<"\n┃温馨提示：
┃";
cout<<"\n┃Ⅰ.进行5操作前请先输出3┃";
cout<<"\n┃Ⅱ.进行6操作前请先输出4┃";
cout<<"\n┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛";
cout<<"\n";
cout<<"请输入一个任务选项>>>";
cout<<"\n";
intnum;
cin>>num;
switch（num）{
case1:
getin（a）;
break;
case2:
ShowInformation（a）;
break;
case3:
CreateHash1（H,a）;/*以姓名建立哈希表*/
break;
case4:
CreateHash2（H,a）;/*以电话号码建立哈希表*/
break;
case5:
c=0;
SearchHash1（H,c）;
break;
case6:
c=0;
SearchHash2（H,c）;
break;
case7:
Cls（a）;
break;
case8:
Save（）;
break;
case9:
return0;
break;
default:
cout<<"你输错了，请重新输入!
";
cout<<"\n";
}
}
system（"pause"）;
return0;
}
四、程序测试
1、程序经测试后大部分功能正常，但是在建立哈希表后存盘出现错误，经仔细查找发现是由于定义时范围过小造成的溢出现象，经处理后程序功能一切运行正常。
2、调试后的界面：
五、总结
课程设计顺利完成，在这几天的程序测试中，虽然是按照课程设计所要求的功能进行编程，但是还是有一些功能的实现不尽人意，比如在处理冲突时，遇到寻址失败利用再哈希法解决冲突的过程中会有一些异常现象的产生。
同时经过这阶段的课程设计可以体会出团队合作的重要性。
升级会员 