哈希表的设计与实现.docx

合肥学院计算机科学与技术系课程设计报告20072008学年第 2学期课程数据结构与算法课程设计名称哈希表的设计与实现学生姓名学号0604011026专业班级06计科(1)指导教师2008 年9 月一、课程设计题目：（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址； （2）从键盘输入各记录， 分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。二、问题分析和任务定义1、问题分析要完成如下要求：设计哈希表实现电话号码查询系统。实现本程序需要解决以下几个问题：（1）如何设计一个结点使该结点包括电话号码、用户名、地址。（2）如何分别以电话号码和用户名为关键字建立哈希表。（3）如何利用再哈希法解决冲突。（4）如何实现用哈希法查找并显示给定电话号码的记录。（5）如何查找并显示给定用户的记录。2、任务定义由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失” 的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构 把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点， 在链地址法中，每个结点对应一个链表结点，它由三个 域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成.name8 、num11和address20都是char浮点型，输入输出都只能 是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表即哈希表。数组元素的下标对应由散列函的第一个结点。这些表头结点组成一个一维数组， 数求出的散列地址。拉链法处理冲突的散列表结构:3、主程序分析本题目最主要的要求是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、 号码为关键字建立两个散列函数，具体思路为：对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数， 是将所有字母的 ASCLL码值相加，然后对 20求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数(main()。4、测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：1、姓名：张三 电话号码：地址：合肥2、姓名：Jack电话号码：地址： Shangha i三、概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图:name8num11address20nextkey)；Next指针是用来指向下一个结点其中name8和num11是分别为以电话号码和用户名为关键字域，存放关键字(address20(data)为结点的数据域，用来存储用户的地址。的地址。主要算法的流程图如下：以号码为关键字的Hash()函数流程图以姓名为关键字的Hash()函数流程图取整型name0赋给key2i从0开始取namei不为空Key2+=nameii+Key2=key%20结束结束添加结点信息流程图厂'一申请专利开始开始申请新的结点newphone,newname 即新的号码和名字Newphone=input()Newname 指向 newphone调用hash()函数调用hash()函数拉链法处理冲突利用用户名为关键字插入按姓名查找流程图：开始空录结束q不为q不为空输出无记输出相应记录调用hash()函数中新结点q指向phonekey->nextq=q->next按号码查找流程图：开始空结束q不为q不为空录q=q->next输出无记输出相应记录调用hash2()函数中新结点q指向phonekey->next主程序流程图其动态分配内存空间其动态分配内存空间选6结果选择1输出结查找用户选7果find2()选择2列结果选择0号码散列选择3结果清空 creat();creat2()选择4选择5结束查找号码 find()列表已清 空添加记录apend()进行姓名散列list2()进行号码散列list()输出退出系统return 0姓名散初始化散列链表(2)并为初始化散列链表(1)并为始)1Main ()Menu ()主菜单1输入选择四、详细设计和编码首先定义结点结构体类型， 在链地址法中，每个结点对应一个链表结点， 它由三个域组 成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表， 所以该链表结点它是 由四个域组成，链地址法结点结构如图：name8num11address20next其中name8和num11是分别为以电话号码和用户名为关键字域（ key），存放关键字； address20为结点的数据域（data），用来存储用户的地址信息。next指针是用来指向下一个结点的地址。unsigned int key 和unsigned int key2 分别被定义为电话号码和用户名关键字。块如下：* 程序部分源代码 *程序的主要模1、建立节点struct node / 建节点 char name8,address20;/节点中要包含用户名，用户地址，电话号码以及指向下一个结点的指针char num11;node * next;typedef node* pnode; /typedef可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指针typedef node* mingzi;node *phone;node *nam;node *a;2、对哈希函数的定义本程序要设计两个 hash（）函数，分别对应电话号码和用户名。本设计中对散列函数选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，即H（ key）=key mod p,本设计中p取20,然后将计算出来的数作为该结点的地 址赋给key。具体方法如下：以电话号码为关键字建立哈希函数名为关键字建立哈希函数hash2（char name8）。利用强制类型转换，将用户名的每一个字母hash(char num11)。以用户的ASCLL码值相加并且除以 20后的余数。将计算出来的数作为该结点的地址赋给* 程序部分源代码 *key2。a）void hash（char num11） /以电话号码为关键字建立哈希函数key=(int)num2;while(numi!=NULL)key+=(int)numi;i+；key=key%20;b)void hash2(char name8)以用户名为关键字建立哈希函数int i = 1;key2=(int)name0;while(namei!=NULL)key2+=(int)namei;i+;key2=key2%20;然后，建立结点，并添加结点，利用链地址法解决冲突。建立结点应包括动态申请内存空间。向结点中输入信息。同时将结点中的next指针等于null。添加结点，首先需要利用哈希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后，当然由于分别以用户名和电话号码为关键字，所以分两种情况，如果以用户名为关键字则调用void hash2(char name8)函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则 调用void hash(char num11)函数，并且将结点插入对应的散列链表中。并且，需要两个建立散列链表的函数，分别动态申请一定的空间，用于动态申请散列链表。void create。用来动态创建以电话号码为关键字的链表数组，void create2()用来动态创建以用户名为关键字的链表数组。&&&&&&&&&&&&&&&&&&&&&&&& 个个个个个个个个个个个个个个个个个个个个个个个个程序部分源代码&&&&&&&&&&&&&&&&&&&&&&&&& 个个个个个个个个个个个个个个个个个个个个个个个个个void create2() / 新建姓名节点int i;nam=new mingzi20;void create() /新建号码节点int i;phone=new pnode20; /动态创建对象数组for(i=0;i<20;i+)phonei=new node;phonei->next=NULL;for(i=0;i<20;i+)nami->next=NULL;nami=new node;同样，需要两个显示链表的函数，利用for循环和while语句将表中信息按要求输出来。3 .哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以电话号码为关键字，比较其电话号码是否相同， 如果相同则输出该结点的所有信息，如果以用户名为关键字，贝世较用户名是否相同，如果相同则输出该结点的所有信息。出“无此记录”。&&&&&&&&&&&&&&&&&&&&&&&& 个个个个个个个个个个个个个个个个个个个个个个个个如果找不到与之对应相同的，则输部 分 源 代 码&&&&&&&&&&&&&&&&&&&&&&&& & _ 个个个个个个个个个个个个个个个个个个个个个个个个个1、-一一 一 一_一一_ .在以电话号码为关键字的哈希表中查a) 、void find(char num11) /找用户信息hash(num);node *q=phonekey->next;while(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");b)、void find2(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->address,q->num);else printf(" 无此记录 n");3、主函数本程序需要创建一个主菜单和一个主函数，主菜单便于用户的使用，主函数中，包括所有功能对应的数值，使之和主菜单相对应。主函数界面设计如下0添加记录1. 查找记录2. 姓名散列3号码散列4清空记录5 退出系统4、程序数据测试当程序设计出来后的测试数据为：1、姓名：张三 电话号码：地址：合肥2、姓名：Jack电话号码：地址：Shanghai首先键入0,添加结点信息，然后按1进行查找，分别进行号码和姓名查找，最后可在主菜单中，选择号码散列和姓名散列，由此查看程序运行结果。至此，就解决了哈希表的设计与实现算法可能出现的各种问题，那么根据以上思路以及对问题的 分析和对出现情况的解决则可以写出源程序。五、上机调试1、 语法错误及修改：程序是分块写的 ，调试时可以使用分步调试的方式进行 ，以便能查 找看程序是在哪出错了。 本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关键字的哈希表中要注意涉及 ASCLL码的类型转换，要注意输出不能是“ %d ”，否则不能输出 结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。这些问题均可以根据编译器的警告提示，对应的将其解决。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这 样才能保证运行时不会出错。3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O ( n) =1。但在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间， 往往会发生同义词冲突，这时在查找过程中就需要进行关键字比较。因此散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也 会“浪费” 一部分散列表的空间。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之， a越大冲突的机会就越大，查 找的性能也就越低。哈希表链地址法查找成功的平均查找长度S=1+a/2。链地址法查找不成功的平均查找长度U满足：U =a+e .由以上可以看出，散列表的平均查找长度是填充因nnc-a子的函数，和散列表的长度没有关系，因此在实际应用中， 我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。4、经验和体会：本设计用到的数据结构是哈希表，并且要实现查找功能，在刚拿到本问题时，我首先想到的查找方法是顺序查找，这就没有用到哈希表，而本设计要求必需使用哈希表这一存储结构，另外本设计也可以用C+中的类来解决，可以用类来设计哈希表。六、用户使用说明本程序运行过程时带有提示性语句，由于address20、name8和num11可以看出地址可输入的最大字符数是 20，姓名可输入的最大字符数是 8,电话号码都为11位。在输入的 时候，用户特别注意电话号码的位数。实现添加结点，将信息从键盘输入，然后根据屏幕的提示进行操作，由此，本设计的要求就可以被用户实现了。七、测试结果程序主菜单：记蓄散记加找名码空添杳普W清添加记录:俞入他址请输人萼添加的内容 请输人姓&分别按电话号码和姓名查找画C二曰与l5、ti g巳户氏kto p 哓程设k-+£花云源化ShxbDeSli日ikd .exeE；Kl CLscrsytigerDesktop'鹿苣：5fH>hxb1Dbu gh«h.exc沼出系统. 一 . F iML退出系统D MG质人申话 颂玻海1也 /扪记录 n灌名标13500400«99金林记录 I- '. -隋椅入要添加的内容;清粉好JalK,k由诘： 35000899 &i己录 土查找记衰号码音曲.=7号码查询，7姓老查询.退出系统洼输入电话号码=暖三岳§口3由幽6列141"忝加记虽查珏记录【号有肮列活|4豹巴呆列录纬电驰抵胡记晶散装瑚蛔曲三旅杏sn土里SUmrntiQeADes&玖漫程苗治哈耗盖Stt®拙d切DebuWh由Few与砖查询，？姓名鸯旬请瑜人姓名:乘三命出查找豹信息W底三台肥d3M5E>?W141查瓦祀云世名散刻史脸1-g XlC'湛出家统分别输出按姓名和号码散列的结果m CU5trstigerA.Desktcpis ；thKbOebughxb.exe，GTU阳rsMfgmpestel误程就t踏若表毒代宿gb阴L u g'hjsbn玲清空记录:釜费列及 记密散讯 filn密码空 一流晋姓号洁f七1.匚=4、1"虾4,汁言声代言蓦山此%口南-日讣心口心倨码查谊，？姓宫查胃 -I -F U R -姓名散引 n号码音.清空记录3退出系统s>列列录统洁记记散散*己加找嘉空出哀添5姓号萼fl 4 1 1 1?FJ -Jo L lw ? 1 ->2037请输A中话M砰 输冒宣找的信息= 无此记录 。.添加记录 E .查投记录 L姓名昔柯 、号蹄忽1 ) Il d_ , . I JK L 清 ±4A ? 八、参考书目谭浩强，C语言程序设计，北京：清华大学出版社，2005年7月第3版。王昆仑，李红，数据结构与算法，中国铁道出版社，2007年6月第1版。李春葆，数据结构题集，北京：清华大学出版社，1992年2月第一版。九、附录* 程序源代码 *#include<stdio.h> #include<string.h>#define NULL 0unsigned int key; /定义两个关键字unsigned int key2;int *p;struct node / 建节点 每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针char name8,address20;char num11;node * next;typedef node* pnode; /typedef可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指typedef node* mingzi;node *phone;node *nam;node *a;void hash(char num11) /哈希函数，以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来int i = 3;key=(int)num2;while(numi!=NULL) key+=(int)numi;i+;key=key%20;void hash2(char name8) /哈希函数 以用户名为关键字建立哈希函数/利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数int i = 1;key2=(int)name0;while(namei!=NULL)key2+=(int)namei;i+;key2=key2%20;node* input() / 输入节点信息，建立结点，并将结点的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 apend() /添加节点node *newphone;node *newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;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 pnode20;/动态创建对象数组for(i=0;i<20;i+)phonei=new node;phonei->next=NULL;void create2() / 新建节点int i;nam=new mingzi20;for(i=0;i<20;i+)nami=new node;nami->next=NULL;void list() / 显示列表int i;node *p;for(i=0;i<20;i+)p=phonei->next;while(p)printf("%s_%s_%sn",p->name,p->address,p->num);p=p->next;void list2() / 显示列表int i;node *p;for(i=0;i<20;i+)p=nami->next;while(p)printf("%s_%s_%sn",p->name,p->address,p->num);p=p->next;void find(char num11) /在以电话号码为关键字的哈希表中查找用户信息hash(num);node *q=phonekey->next;while(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 find2(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->address,q->num);else printf("无此记录 n");void menu() / 菜单 printf("0.添加记录 n");printf("1.查找记录 n");printf("2.姓名散列 n");printf("3.号码散列 n");printf("4.清空记录 n");printf("5.退出系统 n");int main()char num11;char name8;create();create2();int sel;while(1)menu();scanf("%d",&sel);if(sel=1)printf("6 号码查询，7姓名查询n");int b;scanf("%d",&b);if(b=6)printf(-请输入电话号码:n");scanf("%s",num);printf(" 输出查找的信息:n");find(num);elseprintf(-请输入姓名:n");scanf("%s",name);printf(" 输出查找的信息:n");find2(name);if(sel=2)printf("姓名散列结果:n");list2();if(sel=0)(printf(" 请输入要添加的内容：n")；apend();if(sel=3)(printf(" 号码散列结果:n");list();if(sel=4)printf(" 列表已清空:n");create();create2();if(sel=6) return 0;return 0;