数据结构-手机号码查询系统方案

PAGE.学习帮手.数据结构-手机号码查询系统方案.学习帮手.报告编号：第5组综合课程设计报告手机号码查询系统指导教师：所在系：电子工程系所学专业：计算机科学与技术年级：2012级数据结构-手机号码查询系统方案全文共34页，当前为第1页。2014年6数据结构-手机号码查询系统方案全文共34页，当前为第1页。目录1、课程设计目的和要求 11.1设计目的 11.2设计要求 12、课程设计的主要工作 12.1需求分析 13、课程基本设计说明 13.1概要设计和数据结构选择 13.2程序具体设计 23.3程序流程图 24、程序详细设计 44.1创建 44.2对哈希函数的定义 44.3哈希查找 54.4主函数 65、程序运行结果界面 86、课程设计总结 127、参考文献 138、附录 13数据结构-手机号码查询系统方案全文共34页，当前为第2页。数据结构-手机号码查询系统方案全文共34页，当前为第2页。摘要本文主要介绍了手机号码查询系统，实现对用户手机号码、用户名以及地址的添加、查询、存储。程序主要以手机号码和姓名为关键字建立哈希表，并实现查找功能。其中，以手机号为关键字建立哈希表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突，成功通过设计哈希表实现对用户的手机号码、姓名、地址显示、查询等功能。通过课程设计,巩固和加深对结构体、哈希表等理论知识的理解，掌握现实复杂的分析建模和解决方法,掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人的动手能力，历练自身素质；提高大家的合作能力。关键字：哈希表线性探测法链地址法数据结构数据结构-手机号码查询系统方案全文共34页，当前为第3页。1、课程设计目的和要求1.1设计目的本题目最主要的的是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数。1.2设计要求（1）每个记录有下列数据项：手机号码、用户名、地址；（2）从键盘输入各记录，分别以手机号码和用户名为关键字建立哈希表（哈希函数自选）；（3）以手机号为关键字建立哈希表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突；（4）查找并显示给定手机号码的记录；数据结构-手机号码查询系统方案全文共34页，当前为第4页。数据结构-手机号码查询系统方案全文共34页，当前为第4页。2、课程设计的主要工作2.1需求分析本题目最主要的要求是设计散列函数，需要设计两个散列函数才能解决问题。程序需要分别为以号码和用户名为关键字建立哈希表。所以要分别以用户名为关键字建立哈希表时采用拉链法解决冲突、以手机号码为关键字时采用线性探测法解决冲突，具体思路为：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。（2）要添加用户信息，以号码为关键字的添加函数即要有实现添加功能的函数，以用户名为关键字的添加函数即要有实现添加结点功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括查找的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()）。（4）测试数据的选择，程序完成后要对程序进行编译调试，执行后要选择数据进行测试；3、课程基本设计说明3.1概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入号码、用户名、地址三个信息，并要求分别以号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。数据结构-手机号码查询系统方案全文共34页，当前为第5页。（1）在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地数据结构-手机号码查询系统方案全文共34页，当前为第5页。name[20]num[20]address[30]next其中name[20]和num[20]是分别为以号码和用户名为关键字域，存放关键字（key）；address[30]的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。（2）在线性探测法中，先输入关键字，根据计算哈希地址的函数，求得哈希地址。根据哈希地址找到哈希地址对应的关键字，看哈希地址对应的关键字是否与所查找的关键字相同。若不同，则将哈希地址加一，直到找到关键字为止。3.2程序具体设计本系统分为六个个模块，分别是主函数，增加用户、查找记录、号码显示、姓名显示。下面就每个功能进行详细说明：（1）主函数：设计用户登录界面（包括增加、显示、查询、退出）。（2）增添用户：选择增加用户数量，再输入对应数量的用户姓名，住址，号码（3）查找记录：分为按姓名查询和按号码查询，并分别调用自己的输入法。按姓名查询是以姓名为关键字的哈希表的查找函数计算哈希地址，并进行判断，当查找的关键字与利用该关键字求得的哈希地址一致时输出该用户所有信息，否则继续查找，直至找到。号码查询是以手机号码为关键字的哈希表的查找函数计算哈希地址，并进行判断，如果元素不在该位置，将元素后移再判断遇到空格表示该元素不存在，最后返回查找到的哈希地址。（4）姓名显示：以姓名为关键字的哈希函数计算姓名中每个字符的ASCII码值相加姓名为关键字创建哈希表计算哈希地址，采用拉链法解决冲突。数据结构-手机号码查询系统方案全文共34页，当前为第6页。（5）号码显示：以手机号码为关键字的哈希函数计算号码中每个字符的ASCII码值相加，号码为关键字创建哈希表并计算哈希地址，采用线性探测法数据结构-手机号码查询系统方案全文共34页，当前为第6页。3.3程序流程图数据结构-手机号码查询系统方案全文共34页，当前为第7页。（1）本程序设计是运用哈希表来解决问题，其中运用了许多数组和链表中的基本操作，运用C语言程序编写程序，创建哈希表，以及哈希函数的实现等基本功能，同时运用除留余数求得哈希地址，线性探测法以及拉链法解决冲突，在程序设计成功的基础上，进一步深化理解哈希表的作用和实现原理。数据结构-手机号码查询系统方案全文共34页，当前为第7页。开开始Menu（）主菜单输入选择选择1按号码查找输入按姓名查找输入输出结果输出结果选择2选择3选择4选择5选择5按号码显示号码散列结果按姓名显示退出系统return0按号码查找按姓名查找姓名散列结果号码散列结果结束添加用户姓名散列结果Main()初始化数组并为其动态分配内存空间初始化散列链表并为其动态分配内存空间数据结构-手机号码查询系统方案全文共34页，当前为第8页。图3-3程序基本流程图 数据结构-手机号码查询系统方案全文共34页，当前为第8页。4、程序详细设计4.1创建************************程序部分源代码*************************创建数组typedefstruct{ charname[20];charaddress[30];charnum[20];}Record;RecordInf[M];RecordH[M];创建结点structnode{charname[20];charaddress[30];charnum[20];node*next;};node**nam;数据结构-手机号码查询系统方案全文共34页，当前为第9页。typedefnode*mingzi数据结构-手机号码查询系统方案全文共34页，当前为第9页。4.2对哈希函数的定义本程序要设计两个hash（）函数，分别对应电话号码和用户名。本设计中对散列函数选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，即H（key）=keymodp,本设计中p取19,然后将计算出来的数作为哈希地址赋给key。具体方法如下：以号码为关键字建立哈希函数hash(charnum[20)。以用户名为关键字建立哈希函数hash2(charname[20])。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以19后的余数。将计算出来的数作为该结点的地址赋给key2。************************程序部分源代码*************************inthash(charnum[20]){ inti=0; intb=0; while(num[i]!='\0') {b=b+num[i];i++;} b=b%19; return(b);}voidhash2(charname[20]) {数据结构-手机号码查询系统方案全文共34页，当前为第10页。inti=1;数据结构-手机号码查询系统方案全文共34页，当前为第10页。key2=(int)name[0];while(name[i]!=NULL) {key2+=(int)name[i];i++;}key2=key2%19;}4.3哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以号码为关键字，比较其号码是否相同，如果相同则输出所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录”。************************程序部分源代码*************************intfind(RecordH[],charnum[20]){ intw,key=0;key=hash(num);while(strcmp(num,H[key].num)!=0) { 数据结构-手机号码查询系统方案全文共34页，当前为第11页。 key++;数据结构-手机号码查询系统方案全文共34页，当前为第11页。 if(strcmp(H[key].num,NULLKEY)==0) { printf("查找号码不存在\n"); return-1; break; } }returnkey;}voidfind2(charname[20]){ hash2(name);node*q=nam[key2]->next;while(q!=NULL) { if(strcmp(name,q->name)==0)break;q=q->next; }if(q) printf("\t用户名:\t%s\n\t地址:%s\n\t号码:%s\n",q->name,q->address,q->num);数据结构-手机号码查询系统方案全文共34页，当前为第12页。elseprintf("无此记录\n");数据结构-手机号码查询系统方案全文共34页，当前为第12页。}4.4主函数本程序需要创建一个主菜单和一个主函数，主菜单便于用户的使用，主函数中，包括所有功能对应的数值，使之和主菜单相对应。************************程序部分源代码*************************intmenu_select(){ intc; do{system("cls");printf("**************************\n");printf("**************************\n");printf("*****手机号码查询系统****\n");printf("*1.增添用户*\n");printf("*2.按号码显示*\n"); printf("*3.按姓名显示*\n");printf("*4.按号码查找*\n");printf("*5.按姓名查找*\n");printf("*6.结束程序*\n");printf("**************************\n");printf("请选择您要运行的选项按(1-6):");数据结构-手机号码查询系统方案全文共34页，当前为第13页。scanf("%d",&c);数据结构-手机号码查询系统方案全文共34页，当前为第13页。getchar(); }while(c<1||c>6); return(c);}菜单函数主要有以下功能：1.增添用户2.按号码显示 3.按姓名显示4.按号码查找5.按姓名查找6.结束程序至此，就解决了哈希表的设计与实现算法可能出现的各种问题，那么根据以上思路以及对问题的分析和对出现情况的解决则可以写出源程序。5、程序运行结果界面1）菜单主界面数据结构-手机号码查询系统方案全文共34页，当前为第14页。2）新增用户界面数据结构-手机号码查询系统方案全文共34页，当前为第14页。3）按号码查询输入界面4）按号码显示界面数据结构-手机号码查询系统方案全文共34页，当前为第15页。数据结构-手机号码查询系统方案全文共34页，当前为第15页。5）按号码查询数据结构-手机号码查询系统方案全文共34页，当前为第16页。数据结构-手机号码查询系统方案全文共34页，当前为第16页。6）按姓名查询输入界面7）按姓名显示界面数据结构-手机号码查询系统方案全文共34页，当前为第17页。数据结构-手机号码查询系统方案全文共34页，当前为第17页。8）按姓名查询界面数据结构-手机号码查询系统方案全文共34页，当前为第18页。数据结构-手机号码查询系统方案全文共34页，当前为第18页。9）退出界面6、课程设计总结1、语法错误及修改：程序是分块写的,调试时可以使用分步调试的方式进行,以便能查找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换，要注意输出不能是“%d”，否则不能输出结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。数据结构-手机号码查询系统方案全文共34页，当前为第19页。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这样才能保证运行时不会出错。数据结构-手机号码查询系统方案全文共34页，当前为第19页。3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也会“浪费”一部分散列表的空间。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之，a越大冲突的机会就越大，查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a/2。链地址法查找不成功的平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充因子的函数，和散列表的长度没有关系，因此在实际应用中，我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。4、人员分工：组长王敏编写有关增加的函数和创建哈希表的函数，整个程序的运行及调试工作。组员韦蕾项目报告汇总和修改组员张雪妮编写有关显示的函数组员杨丹编写有关查询的函数和计算哈希地址的函数组员熊佳惠编写菜单和主函数所有组员在编写过程中都认真负责，体现了团队精神，每个人都有明确的分工，都参加了项目报告的撰写，达到了预期团队合作的效果。数据结构-手机号码查询系统方案全文共34页，当前为第20页。5、通过这次课程设计,我们大家巩固和加深了对哈希表等理论知识的理解；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人的动手能力，历练自身素质；提高大家的合作能力。掌握实现复杂问题的分析建模和解决方法；也提高了对书写报告的规范性数据结构-手机号码查询系统方案全文共34页，当前为第20页。7、参考文献[1]严蔚敏.数据结构（C语言版）.北京：清华大学出版社，2007版.[2]谭浩强、张基温编著.《C语言程序设计教程》(第3版).北京：高等教育出版社，2006年[3]李春葆，数据结构题集.北京：清华大学出版社，1992年2月第一版。8、附录程序代码如下：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineM20#defineNULLKEY"\0"#defineNULL0#defineINFEASIBLE-1typedefstruct{ charname[20];charaddress[30];charnum[20];}Record;RecordInf[M];//定义辅助数组为全局变量RecordH[M];//定义哈希表为全局变量unsignedintkey2;structnode//建结点每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针数据结构-手机号码查询系统方案全文共34页，当前为第21页。{数据结构-手机号码查询系统方案全文共34页，当前为第21页。charname[20];charaddress[30];charnum[20];node*next;};typedefnode*mingzi;//typedef可以为一个已有的数据类型声明多个别名，这里为该类型声明了一个指针node**nam;intmenu_select()/*菜单函数*/{ intc; do{system("cls");/*运行前清屏*/printf("**************************\n");printf("*****手机号码查询系统****\n");printf("*1.增添用户*\n");printf("*2.按号码显示*\n"); printf("*3.按姓名显示*\n");printf("*4.按号码查找*\n");printf("*5.按姓名查找*\n");printf("*6.结束程序*\n");printf("**************************\n");printf("请选择您要运行的选项按(1-6):");数据结构-手机号码查询系统方案全文共34页，当前为第22页。scanf("%d",&c);/*读入选择*/数据结构-手机号码查询系统方案全文共34页，当前为第22页。getchar(); }while(c<1||c>6); return(c);/*返回选择*/}inti=0;intadd()//增加用户{ printf("请输入名字\n"); scanf("%s",Inf[i].name); printf("请输入地址\n"); scanf("%s",Inf[i].address); printf("请输入号码\n");scanf("%s",Inf[i].num); i++; returni;}inthash(charnum[20])//以号码为关键字的哈希函数{ inti=0,b=0; while(num[i]!='\0')//计算手机号码中每个字符的ASCII码值相加 { b=b+num[i]; i++;//哈希地址 }数据结构-手机号码查询系统方案全文共34页，当前为第23页。 b=b%19;//除留余法求数据结构-手机号码查询系统方案全文共34页，当前为第23页。 return(b);}voidinput(RecordInf[M],intm,RecordH[M])//以手机号码为关键字创建哈希表{ intj,key=0; for(j=0;j<m;j++) { key=hash(Inf[j].num);//计算哈希地址 while(1) { if(strcmp(H[key].num,NULLKEY)==0)//判断该位置是否为空，为空就把辅助数组中的元素存到该位置 { strcpy(H[key].name,Inf[j].name); strcpy(H[key].num,Inf[j].num); strcpy(H[key].address,Inf[j].address); break; } else key++;//如果不为空，采用线性探测法，将元素后移,解决冲突 } }}数据结构-手机号码查询系统方案全文共34页，当前为第24页。数据结构-手机号码查询系统方案全文共34页，当前为第24页。voidlist(RecordH[M])//以手机号码为关键字的哈希表的输出函数{ inti; for(i=0;i<20;i++) { if(strcmp(H[i].num,"\0")!=0) { printf("\t用户名:%s\n\t地址:%s\n\t号码:%s\n",H[i].name,H[i].address,H[i].num); } }}intfind(RecordH[],charnum[20])//以手机号码为关键字的哈希表的查找函数{ intkey=0;key=hash(num);//计算哈希地址while(strcmp(num,H[key].num)!=0)//如果元素不在该位置，将元素后移再判断 { key++; if(strcmp(H[key].num,NULLKEY)==0)//遇到空格表示该元素不存在 { printf("查找号码不存在\n"); return-1;数据结构-手机号码查询系统方案全文共34页，当前为第25页。 break;数据结构-手机号码查询系统方案全文共34页，当前为第25页。 } }returnkey;//返回查找到的哈希地址}node*input2()//输入节点信息，建立结点，并将结点的next指针指空{ node*temp;temp=newnode;//new的功能是动态分配内存，语法形式：new类型名T（初值列表temp->next=NULL;printf("请输入姓名:\n");scanf("%s",temp->name);printf("输入地址：\n");scanf("%s",temp->address);printf("输入电话：\n");scanf("%s",temp->num);returntemp;//对于指针类型返回的是地址}voidhash2(charname[20])//哈希函数以用户名为关键字建立哈希函数 //利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数{ inti=1;key2=(int)name[0];数据结构-手机号码查询系统方案全文共34页，当前为数据结构-手机号码查询系统方案全文共34页，当前为第26页。while(name[i]!=NULL) { key2+=(int)name[i];i++; }key2=key2%19;}voidcreate()//新建节点{ inti;nam=newmingzi[20];//动态创建对象数组for(i=0;i<20;i++) { nam[i]=newnode;nam[i]->next=NULL; }}intapend()//添加节点{ node*newname;newname=input2();newname->next=NULL;hash2(newname->name);//利用哈希函数计算出对应关键字的存储地址数据结构-手机号码查询系统方案全文共34页，当前为第27页。newname->next=nam[key2]->next;//利用用户名为关键字插入,采用头插入法数据结构-手机号码查询系统方案全文共34页，当前为第27页。nam[key2]->next=newname;//是采用链地址法，拉链法处理冲突的散列表结构return0;}voidlist2()//按姓名显示哈希表{ inti;node*p;for(i=0;i<20;i++) {p=nam[i]->next;while(p) { printf("\t用户名:\t%s\n\t地址:%s\n\t号码:%s\n",p->name,p->address,p->num);p=p->next; } }}voidfind2(charname[20])//在以用户名为关键字的哈希表中查找用户信息{ hash2(name);node*q=nam[key2]->next;while(q!=NULL) {数据结构-手机号码查询系统方案全文共34页，当前为第28页。 if(strcmp(name,q->name)==0)数据结构-手机号码查询系统方案全文共34页，当前为第28页。break;q=q->next; }if(q) printf("\t用户名:\t%s\n\t地址:%s\n\t号码:%s\n",q->name,q->address,q->num);elseprintf("无此记录\n");}intmenu()/*菜单函数*/{ intc; do{system("cls");/*运行前清屏*/printf("**************************\n");printf("*******输入方式选择*******\n");printf("*1.按号码查询输入*\n");printf("*2.按姓名查询输入*\n");printf("**************************\n");printf("请选择您要运行的选项按(1-2):");scanf("%d",&c);/*读入选择*/getchar(); }while(c<1||c>2); return(c);/*返回选择*/}数据结构-手机号码查询系统方案全文共34页，当前为第29页。数据结构-手机号码查询系统方案全文共34页，当前为第29页。voidmain()//主函数{ charname[20],num[20]; intm,n,j,w,k; create(); while(1) { switch(menu