设计散列表实现电话号码查找系统Word格式文档下载.docx
《设计散列表实现电话号码查找系统Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《设计散列表实现电话号码查找系统Word格式文档下载.docx（34页珍藏版）》请在冰点文库上搜索。
二、概要设计
1、总体设计思路
程序的总体实现思路、方法：
本程序使用了链地址法和开放定址法处理冲突，可以实现从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
查找并显示给定电话号码的记录；
查找并显示给定用户名的记录；
计算使用不同方法处理冲突时的平均查找长度。
当使用链地址法处理冲突，电话号码为关键字建立散列表时，使用除留余数法（t=e->
number%n），确定哈希地址。
当使用链地址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name）的0号位置的字符（name[0]）强制转换为int类型（i），即i=（int）name[0],再使用除留余数法确定哈希地址（i=i%n，n=13）。
当使用开放定址法处理冲突，电话号码为关键字建立散列表时，增量序列取用线性探测再散列法。
当使用开放定址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name2）的0号位置的字符（name2[0]）强制转换为int类型（e），即e=（int）name[0],使用开放定址法取得哈希地址，如果产生冲突增量取用线性探测再散列法。
程序总的功能结构图。
2、模块简介
链地址法：
voidhashlistinit（newnode**p）//初始化散列表
voidhashinputname（newnode**p）//添加记录（以用户名为关键字）
voidhashshow2name（newnode**p）//查询记录（以用户名为关键字）
voidhashinput（newnode**p）//添加记录（以号码为关键字）
voidhashshow（newnode**p）//查询记录（以号码为关键字）
voidASL（newnode**p）//计算ASL
开放定址法
voidhashlistinit2（anode3w）//初始化散列表
voidhashinput2（anode3w）//添加记录（以号码为关键字）
voidhashshow2（anode3w）//查询记录（以号码为关键字）
voidhashinputname2（anode3w{//添加记录（以用户名为关键字）
voidhashshow2name2（anode3w）//查询记录（以用户名为关键字）
voidASL2（anode3w）//计算ASL
intscan（）//菜单显示函数
intscan2（）{//菜单显示函数
三、详细设计
1、数据结构设计
typedefstructnode{0
intnumber;
charaddress[size];
charname[size];
structnode*next;
}newnode,*anode;
13
开放定址法：
typedefstructnode2{
intnumber2;
charaddress2[size];
charname2[size];
intv;
//冲突次数
}newnode2,*anode2;
typedefstructnode3{
anode2q;
//信息录入数组
inti;
//判断存储空间
intj;
//表长
}newnode3,*anode3;
2、算法分析与实现
添加记录（以用户名为关键字）
使用开放定址法，以用户名为关键字，添加记录当输入的电话号码不为-1时，输入姓名（英文），把姓名的第一个英文字母（char型）强制转换为整型e,
再使用开放定址法获取哈希地址，增量取用线性探测再散列法。
Y
N
N
Y
YY
N
NY
四、运行结果和调试分析
测试数据：
姓名
住址
电话号码
Fu
云南
19
Yuan
河北
14
Dong
山西
23
用户名为关键字建立散列表：
ASL=1
以号码为关键字建立散列表：
运行结果图。
1.选用建表方法，初始化散列表。
——————————链地址法
2.添加记录（以用户名为关键字）——————————链地址法
3.查询记录（以用户名为关键字）——————————链地址法
4.计算ASL——————————链地址法
5.添加记录（以号码为关键字）——————————链地址法
6.查询记录（以号码为关键字）——————————链地址法
7.切换开放定址法
8.初始化散列表，添加记录（以用户名为关键字）—————开放定址法
9.查询记录（以用户名为关键字）——————————开放定址法
10.计算ASL——————————开放定址法
11.添加记录（以号码为关键字）——————————开放定址法
12.查询记录（以号码为关键字）——————————开放定址法
13.退出系统
五、总结体会
课程设计使我对数据结构课程的理解更深入，也能够发现自己平时不太注意的语法错误。
当遇到问题时就翻书，或者上网查资料。
在程序调试的过程中也能够完善系统。
在课程设计过程中，使我的思路更为开拓。
参考文献
[1]严蔚敏，吴伟民编著．《数据结构》（C语言版）．清华大学出版社。
[2]孙改平，王德志编著，《C语言程序设计》，清华大学出版社。
程序源码：
#include<
iostream>
stdio.h>
#include<
stdlib.h>
string.h>
#definesize100
#definen13
typedefstructnode{
typedefstructnode2{
voidhashlistinit（newnode**p）{//初始化散列表链地址法
for（i=0;
i<
n;
i++）{
p[i]=NULL;
}
printf（"
亲，散列表已初始化完毕\n"
）;
voidhashinputname（newnode**p）{//添加记录（以用户名为关键字）链地址法
inti,v;
请输入数据\n"
请输入电话号码，输入-1结束\n"
scanf（"
%d"
&
v）;
while（v!
=-1）{
anodee=（anode）malloc（sizeof（newnode））;
e->
number=v;
printf（"
请输入地址\n"
scanf（"
%s"
e->
address）;
请输入名字（英文）\n"
name）;
i=（int）e->
name[0];
i=i%n;
next=p[i];
p[i]=e;
voidhashshow2name（newnode**p）{//查询记录（以用户名为关键字）链地址法
chara[size];
anodet;
请输入要查询用户名\n"
a）;
i=（int）a[0];
i=i%n;
t=p[i];
while（t&
&
strcmp（t->
name,a）!
=0）{
t=t->
next;
if（t==NULL）{
您所查询的用户不存在\n"
else{
------------------------------------------\n"
姓名:
%s\n"
t->
电话:
%d\n"
number）;
地址:
voidhashinput（newnode**p）{//添加记录（以号码为关键字）链地址法
intt,v;
t=e->
number%n;
next=p[t];
p[t]=e;
voidhashshow（newnode**p）{//查询记录（以号码为关键字）链地址法
intd,h;
请输入所要查询的电话号码\n"
d）;
h=d%n;
t=p[h];
t->
number!
=d）{
您所要查询的号码不存在\n"
voidASL（newnode**p）{//计算ASL链地址法
inta[size],l,asl,z,b;
asl=0;
z=0;
anodeu;
for（l=0;
l<
size+1;
l++）{
a[l]=0;
b=1;
u=p[l];
while（u）{
a[b]++;
b++;
u=u->
}
for（l=1;
n+1;
asl=asl+a[l]*l;
z=z+a[l];
asl=asl/z;
用链地址法处理冲突：
ASL=%d\n"
asl）;
voidhashlistinit2（anode3w）{//初始化散列表开放定址法链地址法
anode2e;
e=（anode2）malloc（n*sizeof（newnode2））;
if（!
e）exit（0）;
w->
q=e;
i=n;
j=n;
for（inth=0;
h<
j;
h++）{
w->
q[h].number2=0;
q[h].v=0;
strcpy（w->
q[h].address2,"
无"
q[h].name2,"
voidhashinput2（anode3w）{//添加记录（以号码为关键字）开放定址法
intd,t,k;
k=1;
亲请输入所要录入的信息\n"
电话号码（输入-1结束）：
"
t=d%w->
while（d!
if（w->
q[t].number2==0&
i!
q[t].number2=d;
姓名：
w->
q[t].name2）;
地址：
q[t].address2）;
i=w->
i-1;
q[t].v=1;
elseif（w->
i==0）{
内存已满\n"
q[t].number2!
t=（d+k）%w->
k=k+1;
q[t].v=2;
while（w->
=0&
k<
j）{
q[t].v++;
voidhashshow2（anode3w）{//查询记录（以号码为关键字）开放定址法
intd,k,t;
请输入要查询的电话号码：
q[t].number2==d）{
q[t].number2）;
=d&
if（w->
else{
voidhashinputname2（anode3w）{//添加记录（以用户名为关键字）开放定址法
inte,k,d;
请输入要录入的信息\n"
姓名（英文）：
e=（int）a[0];
e=e%w->
if（strcmp（w->
q[e].name2,"
）==0&
q[e].name2,a）;
q[e].number2=d;
q[e].address2）;
q[e].v=1;
elseif（strcmp（w->
）!
e=（e+k）%w->
q[e].v=2;
while（strcmp（w->
q[e].v++;
voidhashshow2name2（anode3w）{//查询记录（以用户名为关键字）开放定址法
inte,k;
请输入要查询的用户名（英文）:
e=（int）a[0];
e=e%w->
if（strcmp（w->
q[e].name2,a）==0）{
q[e].name2）;
q[e].number2）;
q[e].name2,a）!
if（k>
=w->
voidASL2（anode3w）{//计算ASL开放定址法
intasl,c,z;
for（c=0;
c<
c++）{
asl=asl+w->
q[c].v;
q[c].number2!
z++;
用开放定址法处理冲突：
intscan（）{
intm;
**************************************\n"
菜单1\n"
亲，您要用选用哪个方法？
\n"
1.链地址法\n"
2.开放定址法\n"
--------------------------------------\n"
亲，请您输入要选用的方法：
m）;
returnm;
intscan2（）{
intj1;
菜单2\n"
亲啊，我有如下功能哦~\n"
1.初始化散列表\n"
2.添加记录（以用户名为关键字）\n"
3.查询记录（以用户名为关键字）\n"
4.添加记录（以号码为关键字）\n"
5.查询记录（以号码为关键字）\n"
6.计算ASL\n"
7.选用另一个方法\n"
8.退出系统\n"
亲啊，您要使用那个功能呢：
j1）;
-----------
升级会员 