哈希表实验报告.docx

《哈希表实验报告.docx》由会员分享，可在线阅读，更多相关《哈希表实验报告.docx（22页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计报告哈希表问题姓 名：郑健专 业：信息管理与信息系统班 级：083221学 号：08322126指导老师:刘自强设计时间：2010年5月7日一，摘要1二，设计要求与分析2.1课程设计要求22.2 程序分析2三，数据结构选择与概要设计3.1 数据结构选择33.2 Hash函数流程图49四，设计算法4.1 建立节点104.2 哈希函数的定义104.3 哈希查找114.4程序测试11五，使用说明与测试结果5.1使用说明115.2主菜单截图125.3添加记录截图125.4查找截图135.5散列结果截图135.6清空记录截图14六，程序源代码及实验心得6.1 源代码14186.2 实验心

2、得19课程设计评分表20摘要本设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找 功能。所以本设计的核心问题是如何解决散列的问题，由于结点的个数无法确认， 并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以 采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把 同义词链接在一起。首先，解决的是定义链表结点，在链接地址法中，每个结点对应一个链表结 点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立 哈希表，所以该链表结点它是由四个域组成.name8、num11和 address20都 是char浮点型采用链地址法，其中的所有

3、同义词构成一个单链表，再由一个表 头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希 表。二，设计要求与分析2.1 课程设计要求设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。2.2程序分析具体思路为：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值

4、相加，然后对20求余。（2）要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括 一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数 （main（）。（4）测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据 进行测试，这里选择的测试数据为：1. 姓名：郑健；电话：1234567 ；地址：江西九江；2. 姓名：吴任；电话：2345678；地址：江西南昌；3. 姓名：黄鑫；电话：3456789；地址：江西上饶；三，数据结构选择与概要设计3.1数据结构选择本设计

5、涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息， 并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行 哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分 别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链接地址 法结点结构如图：name8num11address20next其中name8和num11是分别为以电话号码和用户名为关键字域，存放关键字（key）； address20（data）为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点 的地址。3.2 Hash函数流

6、程图以号码为关键字的hash函数流程图始开numi!=0结束Key=key+(int) numiKey=key%20取整型num赋给keyi从3开始取i+以姓名为关键字的hash函数流程图amei不为空结束开 始Key2+=nameiKey2=key%20取整型name0赋给key2i从0开始取i+申请新的结点newphone,newname即新的号码和名字Newphone=input()Newname 指向 newphone调用hash()函数调用hash()函数拉链法处理冲突利用用户名为关键字插入结束结束四，设计算法4.1建立节点struct nodechar name8,address2

7、0;char num11;node * next;typedef node* pnode; 可以为一个已有的数据类型声明多个别名，这里为该类型声明了 两个指针typedef node* mingzi;node *phone;node *nam;node *a;4.2哈希函数的定义本程序要设计两个hash()函数，分别对应电话号码和用户名。对关键字进行模运算， 将运算结果所得的余数作为关键字(或结点)的存储地址，方法如下：以电话号码为关键字 建立哈希函数hash(char num11)。以用户名为关键字建立哈希函数hash2(char name8)。利 用强制类型转换，将用户名的每一个字母的AS

8、CLL码值相加并且除以20后的余数。将计 算出来的数作为该结点的地址赋给key2。void hash(char num11); 以电话号码为关键字建立哈希函数哈希函数的主旨是将电话号码的十一位数字全部加起来int i = 3;key=(int)num2;while(numi!=NULL)key+=(int)numi;i+;key=key%20; /利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除 以20后的余数void hash2(char name8); /哈希函数 以用户名为关键字建立哈希函数int i = 1;key2=(int)name0;while(namei!=NU

9、LL)key2+=(int)namei;i+;key2=key2%20;4.3哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字， 首先，都需要利用hash函数来计算出地址。再通过比对，如果是以电话号码为关键字，比 较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比 较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输 出“无此记录”。void find(char num11) ; /在以电话号码为关键字的哈希表中查找用户信息hash(num);node *q=phonekey-next;while(q!

10、= 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;4.4程序测试首先键入0,添加结点信息，然后按1进行查找，分别进行号码和姓名查找，最后可在主菜中， 选择号码散列

11、和姓名散列，由此查看程序运行结果。至此，就解决了哈希表的设计与实现算法可能出现的各种问题，那么根据以上思路以及对问 题的分析和对出现情况的解决则可以写出源程序。五，使用说明与测试结果5.1使用说明由于address20、name8和num11可以看出地址可输入的最大字符数是20，姓名可 输入的最大字符数是8，电话号码都为11位。5.2主菜单截图网 *C:DOCUHENTS AND SETTINGSADINISTRATOR.录录列列录统 苗记郝找名码空出 -。1I2.I3.4 S5.3添加记录截图XIC:DOCU1ENTS AND SETT ING SADIINISTRATOR. 添名最址饶话i

12、ffiA:录录列列录统1E江话？记记系藏九电56加找名码空出入入地 冗西入SIC:DOCU1ENTS AMD SETTIHGSADIIHISTRATORX旬名的3.录T歹歹录统 K姓找TE记记系 骚入查-YJ加找名码空出 1出健警姓tikW 16 CS 1 2 3 4 55.5散列结果截图g *C:DOCU1ENTS口同录录列列录3己己_L_Li E I力找名码空I - 0 127 86 75 64 53 42 3_1_2 和江饶 最 膳西西 -曰一( wLk.ml-匿坷5A录录列列录统列TETE记记系_Y-Y加队者码空出 ts 1 213-145 3 号 0六，程序源代码及实验心得6.1源代

13、码#include#include#define NULL 0unsigned int key;unsigned int key2;int *p;struct nodechar name8,address20;char num11;node * next;typedef node* pnode;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

14、(char name8)int i = 1;key2=(int)name0;while(namei!=NULL)key2+=(int)namei;i+;key2=key2%20;node* input()node *temp;temp = new node;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 *n

15、ewname;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;inext=NULL;void create2()in

16、t i;nam=new mingzi20;for(i=0;inext=NULL;void list()int i;node *p;for(i=0;inext;while(p)printf(%s_%s_%sn,p-name,p-address,p-num);p=p-next;void list2()int i;node *p;for(i=0;inext;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!= NU

17、LL)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() /菜单prin

18、tf(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)

19、;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;6.2实验心得一周的课程设计今天结束了。很快，收获很多。感觉像是一个从无到有的 过程，非常的充实。我做的课题是“

20、哈希表问题”。基本算法老师在课堂上有涉 及过，但具体的还要靠自己去钻研。我在一边做上机实验时，一边到图书馆查阅 书籍，反复实践操作，往往比书本上得到的更多，体会也更深刻。通过本次课程 设计对哈希表问题有了一个比较全面的认识和了解。哈希表问题，在存储位置和关键字之间建立对应关系f，根据对应关系f 找到定值K。若结构中存在关键字和定值K相等的记录，必定在f（K）的存储 位置上，由此可以省去比较过程，直接找到所查记录。哈希表其实不难，课程设 计考验的是我们的学习态度，独立思考问题，和解决问题的能力。把握这次机会 肯定大有收获。东华理工学院长江学院课程设计评分表学生姓名：郑 健 班级：083221 学

21、号：08322126课程设计题目：哈希表问题项目内容满分实评选题能结合所学课程知识、有一定的能力训练。符合选题要求（5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、制 图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练完整，概念清楚、立论正确、技术用语准确、 结论严谨合理；分析处理科学、条理分明、语言流畅、结构严 谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。 格式、 绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总分100指导教师指导教师签名：年 月 日