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

郑州轻工业学院课程设计任务书题目电话号码查询系统专业、班级计科10-01学号41姓名王平主要内容:设计哈希表实现电话号码查找系统基本要求:从键盘输入各记录,分别以电话号码和用户名为关键字设计哈希表;采用不同的哈希函数,比较冲突率;采用适当的方法解决冲突;在哈希函数确定的前提下,尝试不同类型处理冲突的方法,考察平均查找长度的变化;查找并显示给定电话号码的记录;查找并显示给定用户名的记录。主要参考资料等:数据结构课本(c语言版)完成期限:21012年6月21号指导教师签名:课程负责人签名:12年6月21日郑州轻工业学院本科数据结构课程设计总结报告设计题目:电话号码查询系统学生姓名:王平系别:计算机科学与通信工程学院专业:计算机科学与技术班级:10-01学号:541007010141指导教师:卢冰、李晔2012年6月21日设计题目题目:电话号码查询系统每个记录有下列数据项:电话号码、用户名、地址;从键盘输入各记录,分别以电话号码和用户名为关键字设计哈希表;采用不同的哈希函数,比较冲突率;采用适当的方法解决冲突;在哈希函数确定的前提下,尝试不同类型处理冲突的方法,考察平均查找长度的变化;查找并显示给定电话号码的记录;查找并显示给定用户名的记录。运行环境(软、硬件环境)。题目要求用电话号码和姓名两种方式查找;第一大部份是用电话号码查找,第二部分是用姓名查找。1:电话号码查找(先建立哈希表读入数据,然后再处理冲突,查找):在这部分中,我用了除留取余法和数字分析法设计的哈希表,用的是开放定址法进行的冲突处理。除留取余法思想:取关键字被某个不大于哈希表表长的数p除后所得余数为哈希地址即:H(key)=key%p。数字分析法:已知关键字是以r为基础的数,哈希表中出现的关键字是事先知道的,选择关键字是候,我们应该尽量避免冲突。开放地址法:开放地址法主要公式;H=(H+di)%m,di的取法有三种,但是我的程序中只用到了线性探测在散列,本可以用再哈希函数解决冲突的,但是考虑到再哈希函数会增加计算时间,所以就没用。2:姓名查找(先建立哈希表读入数据,然后再处理冲突,查找)方式:这个过程中,我选取了数字分析法,解释如上。主菜单的设计在设计效果上已经显示,不过多说明。建立主菜单算法的流程输入错误重新输电话号码查询姓名查询数字分析法数字分析法除留取余法 主菜单建立->除留取余和数字分析法存储->开放地址法解决冲突->查找。算法设计分析这段代码是哈希存储时从第三个数开始求,提高了代码效率。inti=3; while([i]!='\0')//关键字{ key+=([i]-'0');//关键字求和 i++; } key=key%21;线性探测再散列处理冲突 if(!strcmp([key].num,""))//查找,解决冲突 [key]=s; else {//第一次没解决彻底,继续解决冲突 intj=1; while(strcmp([(key+j)%21].num,""))j++; [(key+j)%21]=s; } }查找代码;while(xnum[i]!='\0') { key+=(xnum[i]-'0');//求和 i++; } key=key%21; if(!strcmp([key].num,xnum))//第一次查找,如果值相等直接赋值 printf("%s%s%s\n",[key].name,[key].address,[key].num); else {//第一次没找到,继续查找 intj=1; while(strcmp([(key+j)%21].num,xnum))j++; if(j==20) printf("查找元素不存在!"); else printf("%s%s%s\n",[(key+j)%21].name,[(key+j)%21].address,[(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("**********