数据结构电话号码查询系统设计报告及代码.docx
《数据结构电话号码查询系统设计报告及代码.docx》由会员分享，可在线阅读，更多相关《数据结构电话号码查询系统设计报告及代码.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构电话号码查询系统设计报告及代码
郑州轻工业学院
课程设计任务书
题目电话号码查询系统
专业、班级计科10-01学号41姓名王平
主要内容：
设计哈希表实现电话号码查找系统
基本要求：
从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率；采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型处理冲突的方法，考察平均查找长度的变化；查找并显示给定电话号码的记录；查找并显示给定用户名的记录。
主要参考资料等：
数据结构课本（c语言版）
完成期限：
21012年6月21号
指导教师签名：
课程负责人签名：
12年6月21日
郑州轻工业学院本科
数据结构课程设计总结报告
设计题目：
电话号码查询系统
学生姓名：
王平
系别：
计算机科学与通信工程学院
专业：
计算机科学与技术
班级：
10-01
学号：
541007010141
指导教师：
卢冰、李晔
2012年6月21日
设计题目
题目：
电话号码查询系统
每个记录有下列数据项：
电话号码、用户名、地址；从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率；采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型处理冲突的方法，考察平均查找长度的变化；查找并显示给定电话号码的记录；查找并显示给定用户名的记录。
运行环境（软、硬件环境）
Vc6.0
算法设计的思想
电话号码查询系统主要是考察我们对哈希查找的掌握。
题目要求用电话号码和姓名两种方式查找；第一大部份是用电话号码查找，第二部分是用姓名查找。
1：
电话号码查找（先建立哈希表读入数据，然后再处理冲突，查找）：
在这部分中，我用了除留取余法和数字分析法设计的哈希表，用的是开放定址法进行的冲突处理。
除留取余法思想：
取关键字被某个不大于哈希表表长的数p除后所得余数为哈希地址即：
H（key）=key%p。
数字分析法：
已知关键字是以r为基础的数，哈希表中出现的关键字是事先知道的，选择关键字是候，我们应该尽量避免冲突。
开放地址法：
开放地址法主要公式;H=（H+di）%m,di的取法有三种，但是我的程序中只用到了线性探测在散列，本可以用再哈希函数解决冲突的，但是考虑到再哈希函数会增加计算时间，所以就没用。
2：
姓名查找（先建立哈希表读入数据，然后再处理冲突，查找）方式:
这个过程中，我选取了数字分析法，解释如上。
主菜单的设计在设计效果上已经显示，不过多说明。
建立主菜单
算法的流程
电话号码查询
姓名查询
输入错误重新输
除留取余法
数字分析法
数字分析法
主菜单建立－＞除留取余和数字分析法存储－＞开放地址法解决冲突－＞查找。
算法设计分析
这段代码是哈希存储时从第三个数开始求，提高了代码效率。
inti=3;
while（s.num[i]!
='\0'）//关键字
{
key+=（s.num[i]-'0'）;//关键字求和
i++;
}
key=key%21;
线性探测再散列处理冲突
if（!
strcmp（W.t[key].num,""））//查找，解决冲突
W.t[key]=s;
else
{//第一次没解决彻底，继续解决冲突
intj=1;
while（strcmp（W.t[（key+j）%21].num,""））j++;
W.t[（key+j）%21]=s;
}
}
查找代码;
while（xnum[i]!
='\0'）
{
key+=（xnum[i]-'0'）;//求和
i++;
}
key=key%21;
if（!
strcmp（W.t[key].num,xnum））//第一次查找，如果值相等直接赋值
printf（"%s%s%s\n",W.t[key].name,W.t[key].address,W.t[key].num）;
else
{//第一次没找到，继续查找
intj=1;
while（strcmp（W.t[（key+j）%21].num,xnum））j++;
if（j==20）
printf（"查找元素不存在！
"）;
else
printf（"%s%s%s\n",W.t[（key+j）%21].name,W.t[（key+j）%21].address,W.t[（key+j）%21].num）;//输出查找到得元素
}
主界面：
printf（"********电话号码查询系统********\n"）;
printf（"用电话号码查询1\n"）;
printf（"用用户名查询2\n"）;
printf（"********************************\n"）;
printf（"请输入您要的选项：
\n"）;
intx,y;
while（scanf（"%d",&x）!
=-1）
{
if（x==1）
{
printf（"********电话号码查询********\n"）;
printf（"除留取余法1\n"）;
printf（"数字分析法2\n"）;
printf（"****************************\n"）;
printf（"请输入y值：
\n"）;
scanf（"%d",&y）;
while（y<3）
{
switch（y）
{
case1:
chuliu（）;break;//调用除留取余函数
case2:
shuzi（）;break;//调用数字分析函数
default:
printf（"输入指令不存在！
\n"）;
}
printf（"********电话号码查询********\n"）;
printf（"除留取余法1\n"）;
printf（"数字分析法2\n"）;
printf（"****************************\n"）;
printf（"请输入您要的选项：
\n"）;
scanf（"%d",&y）;
}
}
elseif（x==2）
{
printf（"********用户名查询********\n"）;
printf（"分析法3\n"）;
printf（"****************************\n"）;
fenxi（）;//调用分析函数
}
else
printf（"查找方式不存在！
请重新输入\n"）;
}
}
运行结果分析
测试实例：
wangpingkaifeng123456
wangdoudouluoyang456789
zhaijiajaizhengzhou147258
sunxuepingzhoukou258369
收获及体会
本次试验电话号码查询系统，看起来也不是想我想象中的那么难，他比较具有针对性，要求我们用哈希函数解决这倒比较实用的题目，但是这道题目用到的哈希函数仅仅是哈希中的九牛一毛，虽然写了大程序，但是对哈希表的了解还是一无所知，数据结构这门课程我认为有点难，也许是我c语言基础不够强吧，好多代码都不是很理解，以至于不能够灵活运用，其实通过每次实验我们都可以发现，数据结构的知识好像就是草原的草，密密麻麻的等待我们去拔掉，这是一项浩大的工程等待我们去建设，与此同时，也要求我们要踏实的完成每一次作业，认真的去分析重要的代码，只有端正自己的态度，才能不断地学到新的知识，提高自己。
程序设计代码：
#include
#include
#include
#defineNULL0
int*p;
structnode//建节点
{
charname[20],address[50];
charnum[11];
node*next;
};
structNode//建节点
{
charname[20],address[50];
charnum[11];
};
typedefnode*Lnode;
typedefNodeTnode;
typedefstructlode
{
Lnodenext;
}lode;
typedefstruct{//顺序表存储下的哈希表
intsize;
Tnodet[10000];
}Qnode;
typedefstruct{//链表存储下的哈希表
intsize;
lodeL[10000];
}Pnode;
voidchuliu（）//除留取余法查询电话号码
{
QnodeW;
memset（W.t,0,sizeof（W.t））;//初始化
Tnodes;
printf（"输入录入数据个数：
"）;
intn;
scanf（"%d",&n）;
W.size=n;
//录入元素
printf（"请输入你要录入的元素：
"）;
while（n--）
{
printf（"姓名地址电话号码\n"）;
scanf（"%s%s%s",s.name,s.address,s.num）;
inti=3,key;
while（s.num[i]!
='\0'）//关键字
{
key+=（s.num[i]-'0'）;//关键字求和
i++;
}
key=key%21;
//线性探测再散列处理冲突
if（!
strcmp（W.t[key].num,""））//查找，解决冲突
W.t[key]=s;
else
{//第一次没解决彻底，继续解决冲突
intj=1;
while（strcmp（W.t[（key+j）%21].num,""））j++;
W.t[（key+j）%21]=s;
}
}
printf（"请输入您要查找的电话号码：
"）;
//查找
charxnum[11];
scanf（"%s",xnum）;
inti=3;
intkey=xnum[2]-'0';
while（xnum[i]!
='\0'）
{
key+=（xnum[i]-'0'）;//求和
i++;
}
key=key%21;
if（!
strcmp（W.t[key].num,xnum））//第一次查找，如果值相等直接赋值
printf（"%s%s%s\n",W.t[key].name,W.t[key].address,W.t[key].num）;
else
{//第一次没找到，继续查找
intj=1;
while（strcmp（W.t[（key+j）%21].num,xnum））j++;
if（j==20）
printf（"查找元素不存在！
"）;
else
printf（"%s%s%s\n",W.t[（key+j）%21].name,W.t[（key+j）%21].address,W.t[（key+j）%21].num）;//输出查找到得元素
}
}
voidshuzi（）//按电话号码-数字分析法
{
Qnodeq1;
printf（"请输入您要输入的数据个数：
"）;
intn,m1,m2;
memset（q1.t,0,sizeof（q1.t））;//初始化
Tnodes;
scanf（"%d",&n）;
q1.size=n;
for（inti=0;i<10000;i++）
strcpy（q1.t[i].num,""）;//置空
m1=m2=0;
while（n--）
{
printf（"请输入您要录入的元素：
"）;
printf（"姓名地址电话号码\n"）;
scanf（"%s%s%s",s.name,s.address,s.num）;//读入数据
__int64key;
key=（（__int64）s.num）%10000;
//处理冲突（方法同上）
if（!
strcmp（q1.t[key].num,""））
q1.t[key]=s;
else
{
i=1;
m1++;
while（strcmp（q1.t[（key+i）%10000].num,""））i++;
q1.t[（key+i）%10000]=s;
}
}
printf（"请输入您要查找的电话号码：
"）;
//查找
charxnum[11];
scanf（"%s",xnum）;
intk=3;
__int64key=（__int64）xnum;
key=key%10000;
if（!
strcmp（q1.t[key].num,xnum））
printf（"%s%s%s",q1.t[key].name,q1.t[key].address,q1.t[key].num）;
else
{
intj=1;
while（strcmp（q1.t[（key+j）%10000].num,xnum））j++;
if（j==20）
printf（"查找元素不存在！
"）;
else
printf（"%s%s%s\n",q1.t[（key+j）%10000].name,q1.t[（key+j）%10000].address,q1.t[（key+j）%10000].num）;
}
}
voidfenxi（）
{
Qnodeq2;
printf（"请输入您要输入的数据个数：
"）;
intn,m1,m2;
memset（q2.t,0,sizeof（q2.t））;//初始化
Tnodes;
scanf（"%d",&n）;
q2.size=n;
for（inti=0;i<10000;i++）
strcpy（q2.t[i].name,""）;//置空
m1=m2=0;
while（n--）
{
printf（"请输入您要录入的元素：
"）;
printf（"姓名地址电话号码\n"）;
scanf（"%s%s%s",s.name,s.address,s.num）;
__int64key;
key=（（__int64）s.name）%10000;
//处理冲突
if（!
strcmp（q2.t[key].name,""））
q2.t[key]=s;
else
{
i=1;
m1++;
while（strcmp（q2.t[（key+i）%10000].name,""））i++;
q2.t[（key+i）%10000]=s;
}
}
printf（"请输入您要查找的名字：
"）;
//查找
charxname[20];
scanf（"%s",xname）;
intk=1;
__int64key=（__int64）xname;
key=key%10000;
if（!
strcmp（q2.t[key].name,xname））
printf（"%s%s%s",q2.t[key].name,q2.t[key].address,q2.t[key].num）;
else
{
intj=1;
while（strcmp（q2.t[（key+j）%10000].name,xname））j++;
if（j==20）
printf（"查找元素不存在！
"）;
else
printf（"%s%s%s\n",q2.t[（key+j）%10000].name,q2.t[（key+j）%10000].address,q2.t[（key+j）%10000].num）;
}
}
voidmenu（）
{
printf（"********电话号码查询系统********\n"）;
printf（"用电话号码查询1\n"）;
printf（"用用户名查询2\n"）;
printf（"********************************\n"）;
printf（"请输入您要的选项：
\n"）;
intx,y;
while（scanf（"%d",&x）!
=-1）
{
if（x==1）
{
printf（"********电话号码查询********\n"）;
printf（"除留取余法1\n"）;
printf（"数字分析法2\n"）;
printf（"****************************\n"）;
printf（"请输入y值：
\n"）;
scanf（"%d",&y）;
while（y<3）
{
switch（y）
{
case1:
chuliu（）;break;//调用除留取余函数
case2:
shuzi（）;break;//调用数字分析函数
default:
printf（"输入指令不存在！
\n"）;
}
printf（"********电话号码查询********\n"）;
printf（"除留取余法1\n"）;
printf（"数字分析法2\n"）;
printf（"****************************\n"）;
printf（"请输入您要的选项：
\n"）;
scanf（"%d",&y）;
}
}
elseif（x==2）
{
printf（"********用户名查询********\n"）;
printf（"分析法3\n"）;
printf（"****************************\n"）;
fenxi（）;//调用分析函数
}
else
printf（"查找方式不存在！
请重新输入\n"）;
}
}
intmain（）//函数
{
menu（）;
return0;
}
升级会员 