数据结构电话号码查询系统设计报告及代码

郑州轻工业学院课程设计任务书题目电话号码查询系统专业、班级计科10-01学号41姓名王平主要内容：设计哈希表实现电话号码查找系统基本要求：从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率；采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型处理冲突的方法，考察平均查找长度的变化；查找并显示给定电话号码的记录；查找并显示给定用户名的记录。主要参考资料等：数据结构课本（c语言版）完成期限：21012年6月21号指导教师签名：课程负责人签名：12年6月21日2郑州轻工业学院本科数据结构课程设计总结报告设计题目：电话号码查询系统学生姓名：王平系别：计算机科学与通信工程学院专业：计算机科学与技术班级：10-01学号：541007010141指导教师：卢冰、李晔2012年6月21日3设计题目题目：电话号码查询系统每个记录有下列数据项：电话号码、用户名、地址；从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率；采用适当的方法解决冲突；在哈希函数确定的前提下，尝试不同类型处理冲突的方法，考察平均查找长度的变化；查找并显示给定电话号码的记录；查找并显示给定用户名的记录。运行环境（软、硬件环境）Vc6.0算法设计的思想电话号码查询系统主要是考察我们对哈希查找的掌握。题目要求用电话号码和姓名两种方式查找；第一大部份是用电话号码查找，第二部分是用姓名查找。1：电话号码查找（先建立哈希表读入数据，然后再处理冲突，查找）：在这部分中，我用了除留取余法和数字分析法设计的哈希表，用的是开放定址法进行的冲突处理。除留取余法思想：取关键字被某个不大于哈希表表长的数p除后所得余数为哈希地址即：H(key)=key%p。数字分析法：已知关键字是以r为基础的数，哈希表中出现的关键字是事先知道的，选择关键字是候，我们应该尽量避免冲突。开放地址法：开放地址法主要公式;H=(H+di)%m,di的取法有三种，但是我的程序中只用到了线性探测在散列，本可以用再哈希函数解决冲突的，但是考虑到再哈希函数会增加计算时间，所以就没用。2：姓名查找（先建立哈希表读入数据，然后再处理冲突，查4找）方式:这个过程中，我选取了数字分析法，解释如上。主菜单的设计在设计效果上已经显示，不过多说明。算法的流程主菜单建立－＞除留取余和数字分析法存储－＞开放地址法解决冲突－＞查找。算法设计分析这段代码是哈希存储时从第三个数开始求，提高了代码效率。inti=3;while(s.num[i]!='\0')//关键字{key+=(s.num[i]-'0');//关键字求和i++;建立主菜单电话号码查询姓名查询输入错误重新输除留取余法数字分析法数字分析法5}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);else6{//第一次没找到，继续查找intj=1;while(strcmp(W.t[(key+j)%21].num,xnum))j++;if(j==20)printf(查找元素不存在！);elseprintf(%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);7printf(****************************\n);printf(请输入y值：\n);scanf(%d,&y);while(y3){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();//调用分析函数8}elseprintf(查找方式不存在！请重新输入\n);}}运行结果分析910测试实例：wangpingkaifeng123456wangdoudouluoyang456789zhaijiajaizhengzhou147258sunxuepingzhoukou25836911收获及体会本次试验电话号码查询系统，看起来也不是想我想象中的那么难，他比较具有针对性，要求我们用哈希函数解决这倒比较实用的题目，但是这道题目用到的哈希函数仅仅是哈希中的九牛一毛，虽然写了大程序，但是对哈希表的了解还是一无所知，数据结构这门课程我认为有点难，也许是我c语言基础不够强吧，好多代码都不是很理解，以至于不能够灵活运用，其实通过每次实验我们都可以发现，数据结构的知识好像就是草原的草，密密麻麻的等待我们去拔掉，这是一项浩大的工程等待我们去建设，与此同时，也要求我们要踏实的完成每一次作业，认真的去分析重要的代码，只有端正自己的态度，才能不断地学到新的知识，提高自己。程序设计代码：#includestring.h#includestdlib.h#includestdio.h#defineNULL0int*p;structnode//建节点{charname[20],address[50];charnum[11];node*next;};12structNode//建节点{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(输入录入数据个数：);13intn;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;}14}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(查找元素不存在！);else15printf(%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;i10000;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;//处理冲突（方法同上）16if(!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++;17if(j==20)printf(查找元素不存在！);elseprintf(%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