1、哈希表实现通讯录数据结构与算法课程设计报告合肥学院计算机科学与技术系课程设计报告20092010学年第二学期课程 数据结构与算法课程设计名称哈希表实现通讯录题目：（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。 一、 问题分析和任务定义 此程序需要完成如下要求：设计哈希表实现电话号码查询系统。实现本程序需要解决以下几个问题：（1） 设计结点使该结点
2、包括电话号码、用户名、地址。（2） 利用再哈希法解决冲突。（3） 分别以电话号码和用户名为关键字建立哈希表。（4） 实现查找并显示给定电话号码的记录。（5） 查找并显示给定用户的记录。本问题的关键和难点在于如何解决散列的问题。由于结点的个数无法的知，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用拉链法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表
3、结点它是由四个域组成.name8 、num11和address20都是char浮点型，输入输出都只能是浮点型的。采用拉链法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。其次，设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数，对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，
4、然后对20求余。再次，需要实现添加结点的功能，则其中必须包括一个输入结点信息、添加结点的函数；需要实现查找函数，则必须包括一个查找结点的函数；需要对文件进行保存，则必需要包括保存文件函数。还需要包括一个主菜单和一个主函数。最后，当程序设计出来后的测试数据为：1、姓名：付杰 电话号码：136*4086地址：安徽蚌埠2、姓名：宁兵 电话号码：138*4181地址：安徽安庆3、姓名：张文学 电话号码：187*8385地址：安徽阜阳二、概要设计和数据结构选择在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链
5、地址法结点结构如图：name8、num11 、address20、 next其中name8和num11是分别为以电话号码和用户名为关键字域，存放关键字；address20为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。主要算法的流程图如下：初始化散列链表（1）并为其动态分配内存空间初始化散列链表（2）并为其动态分配内存空间下列为各个函数的流程图：（1）、Input:(2)、hash：（3）、HASH2：（4）、Add()（5）、Search_name/Search_num三、详细设计和编码首先定义结点结构体类型，在拉链法中，每个结点对应一个链表结点，它由三个域组成，
6、而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name8 num11 address20 next其中name8和num11是分别为以电话号码和用户名为关键字域，存放关键字；address20为结点的数据域，用来存储用户的地址。next指针是用来指向下一个结点的地址。#include 用来输入/输出文件流类包含的文件是fstream。unsigned int key 和unsigned int key2由于题目要求分别以电话号码和用户名为关键字，所以在此设计两个关键字。其次，设计两个hash（）函数，以电话号码为关键字建立哈希函
7、数hash(char num11)。哈希函数的主旨是将电话号码的十一位数字全部加起来，然后在对20求余。将计算出来的数作为该结点的地址赋给key。以用户名为关键字建立哈希函数hash2(char name8)。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。再次，建立结点，并添加结点，利用拉链法解决冲突。建立结点应包括动态申请内存空间。向结点中输入信息。同时将结点中的next指针等于null。添加结点，首先需要利用哈希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后，当然由于分别以用户名和电话号码为关键字
8、，所以分两种情况，如果以用户名为关键字则调用void hash2(char name8)函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则调用void hash(char num11)函数，并且将结点插入对应的散列链表中。并且，需要两个建立散列链表的函数，分别动态申请一定的空间，用于动态申请散列链表。void create()用来动态创建以电话号码为关键字的链表数组，void create2()用来动态创建以用户名为关键字的链表数组。同样，需要两个显示链表的函数，利用for循环和while语句将表中信息按要求输出来。想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码
9、为关键字，首先，都需要利用hash函数来计算出地址。再依次对比，如果是以电话号码为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无记录”。同时需要一个保存文件的函数，利用一个for循环，当用hash函数计算的地址，在链表的动态申请的数组范围之内，则创建一个文件流对象，并将结点信息保存在该文件中。最后，需要创建一个主菜单和一个主函数，主菜单便于用户的使用，主函数中，包括所有功能对应的数值，使之和主菜单相吻合。当程序设计出来后的测试数据为：1、姓名：付杰 电话号码：136
10、*4086地址：安徽蚌埠2、姓名：宁兵 电话号码：138*4181地址：安徽安庆3、姓名：张文学 电话号码：187*8385地址：安徽阜阳 可以首先，实现添加结点，将1中的的信息从键盘输入，然后在主菜单中选择保存文件，再将2、3的信息从键盘输入，然后在主菜单中，选择保存文。到此已实现了对信息的储存。可在主菜单中，选择散列、查找等功能。四、上机调试1、语法错误及修改：由于本算法使用了链表结构和拉链法解决冲突的问题，所以程序可以相对来说得到简化，语句相对简洁。并且冲突得到很好的解决。所以出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字和函数名称的书写，以及一些库函数的规范使用。这些问题
11、均可以根据编译器的警告提示，对应的将其解决。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这样才能保证运行时不会出错。 3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。但在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时在查找过程
12、中就需要进行关键字比较。因此散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。拉链法可以从根本上杜绝二次聚集，从而提高散列表的均匀度，提高查找性能。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之，a越大冲突的机会就越大，查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a/2。链地址法查找不成功的平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充因子的函数，和散列表的长度没有关系，因此在实际
13、应用中，我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。 4、经验和体会：最初拿到这个问题，因为以前在做C语言课程设计的时候做过类似的题目，所以很熟悉，但是数据结构课上多用的是C，所以用C来设计并且参考了以前做的题目，联系了数据结构课本上和题目要求做出了设计。因为电话号码的存储不是固定的一成不变的，所以需要建立动态链表，并且如果采用线性探测法散列算法解决冲突问题，删除结点会引起“信息丢失”的问题。因此当删除了一个结点后，由于标志数组被更新，其后的同义词也将不再被查找到。而采用拉链法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其
14、他的空地址。五、使用说明 本程序运行过程时带有提示性语句，由于address20、name8和num11可以看出地址可输入的最大字符数是20，姓名可输入的最大字符数是8，电话号码都为11位。在输入的时候，用户特别注意电话号码的位数。实现添加结点，将信息从键盘输入，然后在主菜单中选择保存文件，再将其它信息从键盘输入，然后在主菜单中，选择保存文。到此已实现了对信息的储存。可在主菜单中，选择散列、查找等功能。六、测试结果主截面：输入并存储结点信息：按姓名查找：按电话查找：现实记录：清空记录：退出：七、参考书目2007年6月第一版 王昆仑 李红 数据结构与算法 中国铁道出版社其他八、附录#includ
15、e #includestdlib.hint key; /定义两个关键字为全局变量int key2; int *p; struct node /建节点每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针 char name8,address20; char num11; node * next; ; typedef node* pnode; /typedef可为一个已有的数据类型声明多个别名这里为该类型声明了两个指针typedef node* mingzi; node *phone; /指向指针的指针node *nam; /指向指针的指针void hash(char num11) /哈
16、希函数，以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; void hash2(char name8) /哈希函数以用户名为关键字建立哈希函数 /利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以后的余数 int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input()
17、/输入节点信息，建立结点，并将结点的next指针指空 node *temp; temp = new node; /new的功能是动态分配内存，语法形式：new 类型名T（初值列表 temp-next=NULL; printf(请输入姓名:n); scanf(%s,temp-name); printf(输入地址：n); scanf(%s,temp-address); printf(输入电话：n); scanf(%s,temp-num); return temp; /对于指针类型返回的是地址 int add() /添加节点 node *newphone; node *newname; newpho
18、ne=input(); newname=newphone; hash(newphone-num); /利用哈希函数计算出对应关键字的存储地址 hash2(newname-name); newphone-next = phonekey-next; /利用电话号码为关键字插入 phonekey-next=newphone; /是采用链地址法，拉链法处理冲突的散列表结构 newname-next = namkey2-next; /利用用户名为关键字插入 namkey2-next=newname; return 0; void create() /新建节点 int i; phone=new pnode
19、20;/动态创建对象数组 for(i=0;inext=NULL; void create2() /新建节点 int i; nam=new mingzi20; for(i=0;inext=NULL; void display() int i; node *p=NULL; for(i=0;inext; while(p) printf(%s_%s_%sn,p-name,p-address,p-num); p=p-next; void search_num(char num) /在以电话号码为关键字的哈希表中查找用户信息 hash(num); node *q=phonekey-next; while(
20、q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) printf(%s_%s_%sn,q-name,q-address,q-num); else printf(无此记录n); void search_name(char name8) / 在以用户名为关键字的哈希表中查找用户信息 hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(%s_%s_%sn,q-name,q-add
21、ress,q-num); else printf(无此记录n); void menu() /菜单 printf( +-oOOo-(_)-oOOo-+ n); printf(- 菜单如下，请输入您的选择： - nn); printf(- 0.添加记录 ); printf( 1.查找记录 - nn); printf(- 2.显示记录 ); printf( 3.清空记录 - nn); printf(- 4.退出系统 - nn); printf( +-oOOo-(_)-oOOo-+ n); /printf(Please input your choice:); int main() char num1
22、1; /定义类型 char name8; create(); /开始 创建函数 create2() ; int sel; /所要输入的选择 while(1) menu(); scanf(%d,&sel); /输入选择 switch(sel) case 1: system(cls);/清屏 printf(6号码查询，姓名查询n); int b; scanf(%d,&b); if(b=6) /按照号码查询 printf(请输入电话号码:n); scanf(%s,num); printf(输出查找的信息:n); search_num(num); else /按照姓名查询 printf(请输入姓名:n
23、); scanf(%s,name); printf(输出查找的信息:n); search_name(name); break; case 2: /显示记录所记录的信息 system(cls);/清屏 printf(显示结果:n); display();/调用显示函数display() break; case 0: /添加记录 system(cls);/清屏 printf(请输入要添加的内容:n); add();/调用添加函数add() break; case 3: /清空记录 system(cls);/清屏 printf(列表已清空:n); create();/重新创建函数 create2(); break; default :return 0; /否则 退出 /switch return 0;
