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

1、数据结构 手机号码查询系统方案 报告编号：第5组综合课程设计报告手机号码查询系统指导教师： 所 在 系： 电子工程系 所学专业： 计算机科学与技术 年 级： 2012级 2014 年 6 月摘 要 本文主要介绍了手机号码查询系统，实现对用户手机号码、用户名以及地址的添加、查询、存储。程序主要以手机号码和姓名为关键字建立哈希表，并实现查找功能。其中，以手机号为关键字建立哈希表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突，成功通过设计哈希表实现对用户的手机号码、姓名、地址显示、查询等功能。通过课程设计,巩固和加深对结构体、哈希表等理论知识的理解，掌握现实复杂的分析建模和解决

2、方法,掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人的动手能力，历练自身素质；提高大家的合作能力。关键字：哈希表 线性探测法 链地址法1、课程设计目的和要求1.1 设计目的 本题目最主要的的是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数。1.2 设计要求（1）每个记录有下列数据项：手机号码、用户名、地址；（2）从键盘输入各记录，分别以手机号码和用户名为关键字建立哈希表（哈希函数自选）；（3）以手机号为关键字建立哈希

3、表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突；（4）查找并显示给定手机号码的记录；（5）查找并显示给定用户名的记录。2、课程设计的主要工作2.1 需求分析本题目最主要的要求是设计散列函数，需要设计两个散列函数才能解决问题。程序需要分别为以号码和用户名为关键字建立哈希表。所以要分别以用户名为关键字建立哈希表时采用拉链法解决冲突、以手机号码为关键字时采用线性探测法解决冲突，具体思路为：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。（2）要添加用

4、户信息，以号码为关键字的添加函数即要有实现添加功能的函数，以用户名为关键字的添加函数即要有实现添加结点功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括查找的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()）。（4）测试数据的选择，程序完成后要对程序进行编译调试，执行后要选择数据进行测试；3、课程基本设计说明3.1 概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入号码、用户名、地址三个信息，并要求分别以号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。（1）在链地址

5、法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name20num20address30next其中name20和num20是分别为以号码和用户名为关键字域，存放关键字（key）；address30的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。（2）在线性探测法中，先输入关键字，根据计算哈希地址的函数，求得哈希地址。根据哈希地址找到哈希地址对应的关键字，看哈希地址对应的关键字是否与所查找的关键字相同。若不同，则将哈希地址加一，直到找到关键字为止。3.2程序具体

6、设计本系统分为六个个模块，分别是 主函数，增加用户、查找记录、号码显示、姓名显示。下面就每个功能进行详细说明：（1）主函数：设计用户登录界面（包括增加、显示、查询、退出）。（2）增添用户：选择增加用户数量，再输入对应数量的用户姓名，住址，号码（3）查找记录：分为按姓名查询和按号码查询，并分别调用自己的输入法。按姓名查询是以姓名为关键字的哈希表的查找函数计算哈希地址，并进行判断，当查找的关键字与利用该关键字求得的哈希地址一致时输出该用户所有信息，否则继续查找，直至找到。号码查询是以手机号码为关键字的哈希表的查找函数计算哈希地址，并进行判断，如果元素不在该位置，将元素后移再判断遇到空格表示该元素不

7、存在，最后返回查找到的哈希地址。（4）姓名显示：以姓名为关键字的哈希函数计算姓名中每个字符的ASCII码值相加姓名为关键字创建哈希表计算哈希地址，采用拉链法解决冲突。（5）号码显示：以手机号码为关键字的哈希函数计算号码中每个字符的ASCII码值相加，号码为关键字创建哈希表并计算哈希地址，采用线性探测法解决冲突。3.3 程序流程图（1）本程序设计是运用哈希表来解决问题，其中运用了许多数组和链表中的基本操作，运用C语言程序编写程序，创建哈希表，以及哈希函数的实现等基本功能，同时运用除留余数求得哈希地址，线性探测法以及拉链法解决冲突，在程序设计成功的基础上，进一步深化理解哈希表的作用和实现原理。基本

8、流程图如图3-3。图3-3程序基本流程图 4、程序详细设计4.1 创建*程序部分源代码*1） 创建数组typedef struct char name20; char address30; char num20;Record; Record InfM;Record HM;2） 创建结点struct node char name20;char address30; char num20;node * next; ;node *nam; typedef node* mingzi4.2 对哈希函数的定义本程序要设计两个hash（）函数，分别对应电话号码和用户名。本设计中对散列函数选择的是除留余数法，

9、即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，即H（key）=key mod p,本设计中p取19,然后将计算出来的数作为哈希地址赋给key。具体方法如下：以号码为关键字建立哈希函数hash(char num20)。以用户名为关键字建立哈希函数hash2(char name20)。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以19后的余数。将计算出来的数作为该结点的地址赋给key2。*程序部分源代码*int hash(char num20) int i=0; int b=0; while(numi!=0) b=b+numi; i+; b=b%19

10、; return(b);void hash2(char name20) int i = 1;key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%19; 4.3 哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以号码为关键字，比较其号码是否相同，如果相同则输出所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录”。*程序部分源代码*int find

11、(Record H,char num20) int w,key=0; key=hash(num); while(strcmp(num,Hkey.num)!=0) key+; if(strcmp(Hkey.num,NULLKEY)=0) printf(查找号码不存在n); return -1; break; return key; void find2(char name20) hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(t用户

12、名:t%snt地址:%snt号码:%sn,q-name,q-address,q-num); else printf(无此记录n); 4.4 主函数本程序需要创建一个主菜单和一个主函数，主菜单便于用户的使用，主函数中，包括所有功能对应的数值，使之和主菜单相对应。*程序部分源代码*int menu_select() int c; do system(cls); printf( *n); printf( *n); printf( * 手机号码查询系统*n); printf( * 1. 增添用户 *n); printf( * 2. 按号码显示 *n); printf( * 3. 按姓名显示 *n);

13、printf( * 4. 按号码查找 *n); printf( * 5. 按姓名查找 *n); printf( * 6. 结束程序 *n); printf( *n); printf(请选择您要运行的选项按(1-6):); scanf(%d,&c); getchar(); while(c6); return(c); 菜单函数主要有以下功能： 1. 增添用户 2. 按号码显示 3. 按姓名显示 4. 按号码查找 5. 按姓名查找 6. 结束程序 至此，就解决了哈希表的设计与实现算法可能出现的各种问题，那么根据以上思路以及对问题的分析和对出现情况的解决则可以写出源程序。5、程序运行结果界面1）菜单主

14、界面2）新增用户界面3）按号码查询输入界面4）按号码显示界面5）按号码查询6）按姓名查询输入界面7）按姓名显示界面8）按姓名查询界面9）退出界面6、课程设计总结1、语法错误及修改：程序是分块写的,调试时可以使用分步调试的方式进行,以便能查找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换，要注意输出不能是“%d”，否则不能输出结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到

15、指针的操作。所以需要仔细分析函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这样才能保证运行时不会出错。3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也会“浪费”一部分散列表的空间。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充

16、因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之，a越大冲突的机会就越大，查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a/2。链地址法查找不成功的平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充因子的函数，和散列表的长度没有关系，因此在实际应用中，我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。4、人员分工： 组长 王敏 编写有关增加的函数和创建哈希表的函数，整个程序的运行及调试工作。组员 韦蕾 项目报告汇总和修改 组员 张雪妮 编写有关显示的函数

17、组员 杨丹 编写有关查询的函数和计算哈希地址的函数 组员 熊佳惠 编写菜单和主函数 所有组员在编写过程中都认真负责，体现了团队精神，每个人都有明确的分工，都参加了项目报告的撰写，达到了预期团队合作的效果。5、通过这次课程设计,我们大家巩固和加深了对哈希表等理论知识的理解；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人的动手能力，历练自身素质；提高大家的合作能力。掌握实现复杂问题的分析建模和解决方法；也提高了对书写报告的规范性7、参考文献1 严蔚敏.数据结构（C语言版）.北京：清华大学出版社，2007版.2 谭浩强、张基温编著.C语言程序设计教程(第3版).北京：高等教育出版社，200

18、6年3李春葆，数据结构题集.北京：清华大学出版社，1992年2月第一版。8、附录程序代码如下：#include #include#include #define M 20 #define NULLKEY 0#define NULL 0 #define INFEASIBLE -1 typedef struct char name20; char address30; char num20;Record; Record InfM;/定义辅助数组为全局变量 Record HM;/定义哈希表为全局变量 unsigned int key2;struct node /建结点 每个结点包括用户姓名、地址、电

19、话号码、以及指向下一个结点的指针 char name20;char address30; char num20;node * next; ;typedef node* mingzi;/typedef可以为一个已有的数据类型声明多个别名，这里为该类型声明了一个指针node *nam; int menu_select() /*菜单函数*/ int c; do system(cls); /*运行前清屏*/ printf( *n); printf( * 手机号码查询系统*n); printf( * 1. 增添用户 *n); printf( * 2. 按号码显示 *n); printf( * 3. 按姓

20、名显示 *n); printf( * 4. 按号码查找 *n); printf( * 5. 按姓名查找 *n); printf( * 6. 结束程序 *n); printf( *n); printf(请选择您要运行的选项按(1-6):); scanf(%d,&c); /*读入选择*/ getchar(); while(c6); return(c); /*返回选择*/ int i=0;int add()/增加用户 printf(请输入名字n); scanf(%s,Infi.name); printf(请输入地址n); scanf(%s,Infi.address); printf(请输入号码n);

21、 scanf(%s,Infi.num); i+; return i;int hash(char num20) /以号码为关键字的哈希函数 int i=0,b=0; while(numi!=0) /计算手机号码中每个字符的ASCII码值相加 b=b+numi; i+; /哈希地址 b=b%19; /除留余法求 return(b);void input(Record InfM,int m,Record HM)/以手机号码为关键字创建哈希表 int j,key=0; for(j=0;jm;j+) key=hash(Infj.num);/计算哈希地址 while(1) if(strcmp(Hkey.n

22、um,NULLKEY)=0)/判断该位置是否为空，为空就把辅助数组中的元素存到该位置 strcpy(Hkey.name,Infj.name); strcpy(Hkey.num,Infj.num); strcpy(Hkey.address,Infj.address); break; else key+; /如果不为空，采用线性探测法，将元素后移,解决冲突 void list(Record HM)/以手机号码为关键字的哈希表的输出函数 int i; for(i=0;inext=NULL; printf(请输入姓名:n); scanf(%s,temp-name); printf(输入地址： n);

23、scanf(%s,temp-address); printf(输入电话：n); scanf(%s,temp-num); return temp; /对于指针类型返回的是地址void hash2(char name20) /哈希函数 以用户名为关键字建立哈希函数 /利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数 int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%19; void create() /新建节点 int i; nam=new mingzi20;/

24、动态创建对象数组 for(i=0;inext=NULL; int apend() /添加节点 node *newname; newname=input2(); newname-next=NULL; hash2(newname-name); /利用哈希函数计算出对应关键字的存储地址 newname-next = namkey2-next; /利用用户名为关键字插入,采用头插入法 namkey2-next=newname;/是采用链地址法，拉链法处理冲突的散列表结构 return 0; void list2() /按姓名显示哈希表 int i; node *p; for(i=0;inext; wh

25、ile(p) printf(t用户名:t%snt地址:%snt号码:%sn,p-name,p-address,p-num); p=p-next; void find2(char name20) / 在以用户名为关键字的哈希表中查找用户信息 hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(t用户名:t%snt地址:%snt号码:%sn,q-name,q-address,q-num); else printf(无此记录n); int menu() /*菜单函数*/ int c; do system(cls); /*运行前清屏*/ printf( *n); printf( *输入方式选