数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告
哈希表的设计与实现
一、问题描述：
设计哈希表实现电话号码的查询系统
二、基本要求：
1、设每个记录有下列数据项：
电话号、用户名、地址；
2、从键盘输入各记录，分别以电话号和用户名建立关键字哈希表；
3、采用再哈希法解决冲突；
4、查找并显示给定电话号码的记录
5、查找并显示给定用户名的记录
6、在哈希函数确定的前提下，尝试各种不同类型的处理冲突的方法（至少两种），考察平均长度的变化。
三、测试数据
程序运行时通过添加操作输入以下数据并写入名为“telephone.txt”的文件中
用户名电话号地址
xinran1234piaomiaofeng
dongzhen4321shushan
xiaorenfeng2134kunlunshan
shaoyaxi2413xiangshan
zhaoxi1519zhengzhou
预期输出：
显示所有：
显示以上添加到“telephone.txt”文件中的所有数据
添加：
当前文件内有5条记录
请输入添加的个数：
1
请输入第6个人的姓名：
Shaoyuhan
请输入第6个人的电话：
456
请输入第6各人的地址：
Xihu
查找：
建立用户名哈希表后，选择按用户名查找
请输入您要查找的用户名：
shaoyaxi
您要查找的信息为：
姓名：
Shaoyaxi
电话：
2413
地址：
xiangshan
比较次数为1
建立电话哈希表后，选择按电话号码查找
请输入您要查找的用户名：
shaoyaxi
您要查找的信息为：
姓名：
Shaoyaxi
电话：
2413
地址：
xiangshan
比较次数为4
退出：
选择退出操作后，屏幕上显示谢谢使用界面；
四、算法思想：
本程序中用一个数组来存放从文件中读出的记录和用户在程序运行时添加的数据；建立哈希表时，根据选择的关键字和所采取的解决冲突的方法，采用相同的哈希函数计算出一个哈希地址，如果不冲突，该记录在数组中的下标存放到对应哈希地址。
若冲突，通过调用解决的函数得到一个新的地址，判断新地址是否冲突，若冲突继续解决冲突，直到不再冲突时将该记录在数组中的下标存放到对应哈希地址。
查找时，哈希函数将输入的查找信息转换为一个哈希地址。
在哈希表中对应的哈希地址进行判断，若地址为空，查找失败。
若非空，取出存放的下标，然后比较数组为此下标的记录关键字和输入信息是否相等。
相等则查找成功输出信息，不相等解决冲突得到新的哈希地址，重复以上操作。
直到查找成功或失败（若超过了规定的比较次数也认为查找失败）。
程序中的哈希函数：
将字符串中的每一个字符的ASCII值进行累加后除以表长取余
处理冲突的方法：
开放定址法中的线性探测和平方探测法
五、数据结构
structrecord
{charname[20];
chartel[20];
charadd[20];
};
typedefrecord*precord;
structHashTable
{intelem[Maxsize];//存放数组a[]的下标
intcount;
};
typedefHashTable*pHashTable;
六、模块划分
1.voidGetdata（precorda）将文件中的记录读到数组a中
2.voidAdd（precorda）添加记录同时写入文件
3.voidPrint（precorda）输出所有记录
4.intHash（charstr[]）求哈希地址的哈希函数
5.intLine_Sollution（intaddress）线性探测函数
6.intSquare_Sollution（intaddress）平方探测函数
7.voidInit_Hash（pHashTableh）哈希数组初始化函数
8.voidCreathash_Name（pHashTableh,precorda）以姓名间哈希表
9.voidCreathash_tel（pHashTableh,precorda）以电话建哈希表
10.voidSearch_Name（pHashTableh,precorda）按姓名查找
11.voidSearch_tel（pHashTableh,precorda）按电话号查找
12.voidMenu（）功能菜单函数
13.voidexit（）退出界面函数
14.intmain（）主调函数
七．源程序
#include
#include
#include
usingnamespacestd;
#defineMaxsize57
structrecord
{charname[20];
chartel[20];
charadd[20];
};
typedefrecord*precord;
structHashTable
{intelem[Maxsize];//存放数组a[]的下标
intcount;//统计数组中elem[]存放下标的个数
};
typedefHashTable*pHashTable;
intNumber;//统计当前数组a[]中的记录总数
voidGetdata（precorda）//从文件telphone.txt中读取数据存放到数组a[]
{Number=0;
ifstreaminfile（"telphone.txt",ios:
:
in|ios:
:
binary）;
if（!
infile）{cout<<"文件打开失败!
\n";exit
（1）;}
while（!
infile.eof（）&&infile.get（）!
=EOF）//文件不为空并且文件指针没有指到结束符
{infile.seekg（Number*sizeof（a[Number]）,ios:
:
beg）;//定位文件指针
infile.read（（char*）&a[Number],sizeof（a[Number]））;
Number++;
}
infile.close（）;
}
voidAdd（precorda）//添加记录
{inti,num;
cout<<"当前文件内已有"<cout<<"请输入添加的个数:
";
cin>>num;
ofstreamofile（"telphone.txt",ios:
:
app）;
if（!
ofile）{cout<<"文件打开失败!
";exit
（1）;}
for（i=0;i{cout<<"请输入第"<cin>>a[Number].name;
cout<<"请输入第"<cin>>a[Number].tel;
cout<<"请输入第"<cin>>a[Number].add;
ofile.seekp（ios:
:
end）;//定位文件指针到文件末尾
ofile.write（（char*）&a[Number],sizeof（a[Number]））;
Number++;
}
ofile.close（）;
}
voidPrint（precorda）//显示所有记录
{inti;
for（i=0;i{
cout<<"第"<\n";
cout<<"姓名:
"<cout<<"电话:
"<cout<<"地址:
"<}
}
intHash（charstr[]）//除留取余
{longval=0;charp[20],*p1;
strcpy（p,str）;
p1=p;
while（*p1!
='\0'）
val=val+*p1++;//将字符串中的所有字符对应的ASCII值相加
return（val%Maxsize）;
}
intderter;//线性增量
intLine_Sollution（intaddress）//采用线性探测解决冲突
{
derter++;
if（derter==Maxsize）return（-1）;
elsereturn（（address+derter）%Maxsize）;
}
intn;//实现平方探测中的正负交替
intSquare_Sollution（intaddress）//采用平方探测法解决冲突
{intj;
derter++;
if（derter==Maxsize）return-1;
n=n*（-1）;//正负交替
j=（int（pow（derter,2））*n+address）%Maxsize;
return（j）;
}
voidInit_Hash（pHashTableh）//初始化哈希表
{inti;
for（i=0;ih->elem[i]=-1;
}
intmenu;//记录所采取的建表方式
voidCreathash_Name（pHashTableh,precorda）
//以用户名为关键字创建哈希表
{cout<<"--------------------------------------------------------------------------------\n";
cout<<"1----以线性探测建表\n";
cout<<"2----以平方探测建表\n";
cout<<"--------------------------------------------------------------------------------\n";
inti,address;
cin>>menu;
Init_Hash（h）;
for（i=0;i{derter=0;n=-1;
address=Hash（a[i].name）;
while（h->elem[address]!
=-1）
{if（menu==1）address=Line_Sollution（address）;
elseaddress=Square_Sollution（address）;
if（address==-1）break;
}
if（address!
=-1）{h->elem[address]=i;h->count++;}
}
cout<<"姓名哈希表已成功建立!
\n";
}
voidSearch_Name（pHashTableh,precorda）//查找并显示指定姓名的记录
{cout<<"请输入要查找的姓名:
";
charnam[20];intaddress,i=1;
cin>>nam;
address=Hash（nam）;
derter=0;n=-1;
while（h->elem[address]!
=-1&&strcmp（nam,a[h->elem[address]].name）!
=0）
{if（menu==1）address=Line_Sollution（address）;
elseaddress=Square_Sollution（address）;
i++;
if（address==-1）break;
}
if（h->elem[address]!
=-1&&strcmp（nam,a[h->elem[address]].name）==0）
{cout<<"你要查找的信息为:
\n";
cout<<"姓名:
"<elem[address]].name<cout<<"电话:
"<elem[address]].tel<cout<<"地址:
"<elem[address]].add<cout<<"比较次数为"<}
elsecout<<"无此姓名,查找失败!
";
}
voidCreathash_tel（pHashTableh,precorda）
//以电话号为关键字创建哈希表
{cout<<"--------------------------------------------------------------------------------\n";
cout<<"1----以线性探测建表\n";
cout<<"2----以平方探测建表\n";
cout<<"--------------------------------------------------------------------------------\n";
inti,address;
cin>>menu;
Init_Hash（h）;
for（i=0;i{derter=0;n=-1;
address=Hash（a[i].tel）;
while（h->elem[address]!
=-1）
{if（menu==1）address=Line_Sollution（address）;
elseaddress=Square_Sollution（address）;
if（address==-1）break;
}
if（address!
=-1）{h->elem[address]=i;h->count++;}
}
cout<<"电话号哈希表已成功建立!
\n";
}
voidSearch_tel（pHashTableh,precorda）
//查找并显示指定电话号的记录
{cout<<"请输入要查找的电话:
";
chartelphone[20];intaddress,i=1;//i统计比较次数
cin>>telphone;
address=Hash（telphone）;
derter=0;n=-1;//初始化线性增量
while（h->elem[address]!
=-1&&strcmp（telphone,a[h->elem[address]].tel）!
=0）
{if（menu==1）address=Line_Sollution（address）;
elseaddress=Square_Sollution（address）;
i++;
if（address==-1）break;
}
if（h->elem[address]!
=-1&&strcmp（telphone,a[h->elem[address]].tel）==0）
{cout<<"你要查找的信息为:
\n";
cout<<"姓名:
"<elem[address]].name<cout<<"电话:
"<elem[address]].tel<cout<<"地址:
"<elem[address]].add<cout<<"比较次数为"<}
elsecout<<"无此电话,查找失败!
";
}
voidMenu（）//功能菜单函数
{for（inti=1;i<=5;i++）
cout<cout<<"电话号码查询系统\n";
cout<<'\n';
cout<<"★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n";
cout<<"☆0-------退出★\n";
cout<<"★1-------添加☆\n";
cout<<"☆2-------显示所有★\n";
cout<<"★3-------以性命建立哈希表☆\n";
cout<<"☆4-------以电话建立哈希表★\n";
cout<<”★5-------按用户名查找☆\n";
cout<<"☆6-------按电话号查找★\n";
cout<<"★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n";
cout<<"使用说明:
\n";
cout<<"1.添加新纪录后,如要进行查找请先进行3或4操作\n";
cout<<"2.按用户名查找之前,请先进行3操作建立用户名哈希表\n";
cout<<"3.按用户名查找之前,请先进行4操作建立电话号哈希表\n";
}
voidexit（）
{inti;
for（i=1;i<=4;i++）
cout<cout<<"◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◇◆◇\n";
cout<<"◆◆\n";
cout<<"◇电弧号码查询系统◇\n";
cout<<"◆◆\n";
cout<<"◇谢谢您的使用!
◇\n";
cout<<"◆◆\n";
cout<<"◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆\n";
}
intmain（）
{recorda[Maxsize];
pHashTableH=newHashTable;
Getdata（a）;//将文件中的数据读入到数组a中
start:
Menu（）;
intmenu1;
cin>>menu1;
switch（menu1）
{case0:
system（"cls"）;exit（）;break;
case1:
Add（a）;system（"pause"）;system（"cls"）;gotostart;break;
case2:
Print（a）;system（"pause"）;system（"cls"）;gotostart;break;
case3:
Creathash_Name（H,a）;system（"pause"）;system（"cls"）;gotostart;break;
case4:
Creathash_tel（H,a）;system（"pause"）;system（"cls"）;gotostart;break;
case5:
Search_Name（H,a）;system（"pause"）;system（"cls"）;gotostart;break;
case6:
Search_tel（H,a）;system（"pause"）;system（"cls"）;gotostart;break;
default:
cout<<"请输入正确的操作选项!
\n";system（"cls"）;gotostart;break;
}
return0;
}
八、测试情况
显示所有：
建立用户名哈希表
按姓名查找
建立电话号哈希表：
按电话号查找：
退出界面：
九、实验心得
因为此次课程设计做的是设计哈希表实现电话号码查询系统，自己在做课设之前把课本哈希查找那部分反复看了看，所以加深了对哈希查找的理解。
在做课设之前，我感觉这个课题太难了，自己根本我从下手。
所以也计划从网上下一些别人做好程序，读懂后修改一下就行了。
但是找了几个程序，都发现自己看不懂。
后来想想还是自己做吧。
在做的过程中发现并不是太难。
在自己的程序中除了哈希函数受了网上程序的启发，其它的功能（如线性探测、平方探测、记录查找次数等）都是自己设计出来的。
在程序设计过程中自己遇到的最大的麻烦就是文件的读写。
课设的第一天要求的功能就已基本实现，第二天基本都是在解决如何将数据从文件读入到程序和将数据写入到文件。
第三天完善一下程序功能并测试一下程序是不是还有一些没有发现的错误。
此次课设还发现自己对C不是很熟悉。
课设开始自己也是用C在写程序，但考虑到程序中要有对文件的读写操作，而自己对C中文件的操作一无所知，所以最后还是选择了比C方便多了的C++。
课设后还要再补一补C的知识。
本次课设还是有很大收获。
升级会员 