首页 (完整word版)课程设计试验报告-哈希表的设计与实现

(完整word版)课程设计试验报告-哈希表的设计与实现

举报
开通vip

(完整word版)课程设计试验报告-哈希表的设计与实现数据结构课程设计题目哈希表的设计与实现作者院系信息工程学院专业信息管理与信息系统学号1514210117指导老师张慧答辩时间2016年12月18日目录数据结构课程设计......................................................01系统需求分析........................................................21.1用户需求分析...........

(完整word版)课程设计试验报告-哈希表的设计与实现
数据结构课程设计 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目哈希 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的设计与实现作者院系信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院专业信息管理与信息系统学号1514210117指导老师张慧答辩时间2016年12月18日目录数据结构课程设计......................................................01系统需求分析........................................................21.1用户需求分析...................................................31.2功能需求分析...................................................31.3数据需求分析...................................................31.4小结..........................................................42系统设计............................................................42.1设计内容及要求.................................................42.2总体设计思路...................................................42.3程序详细设计流程图.............................................52.31以姓名为关键字的Hash()函数流程图..........................52.32添加结点信息流程图:.......................................72.33按姓名查找流程图:.........................................82.34按号码查找流程图..........................................92.35主程序流程图..............................................92.4详细设计编码..................................................112.41建立节点.................................................112.42对哈希函数的定义.........................................112.43哈希查找.................................................122.44主函数...................................................123系统测试...........................................................133.1上机调试......................................................133.2调试结果与分析................................................144 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ...............................................................185附录...............................................................18系统需求分析在信息化时代的今天,计算机技术已经是发展到一个很可观的地步了,特别是面向窗口的操作系统的出现,使得程序设计更加的容易了。在过去计算机内存容量小,CPU计算速度慢,关于程序设计中的数据结构也因此提出来很多的关于解决这方面的问题。哈希表就是其中之一,哈希表是一个由关键字与值组成的特殊的一种数据结构。它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字的比较,这一类查找方法是建立在“比较”的基础上的,在顺序等的查找中,查找的效率是依赖于查找过程中所比较的次数。理想的情况是希望不经过任何的比较一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系,使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时只要根据这个对应关系找到给定的值的像。若结构中存在关键字和该值相等的记录,则所要查找的数就必定就是这个所查找到的记录。哈希函数是建立哈希表的一个重要的成员,它的构造方法分为以下几种:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。本程序中主要用的是除余取留法,除留取余法主要是取关键字被某个不大于哈希表表长m的数p出后所得余数为哈希地址即:H(key)=keyMODp,p<=m,这是一种最简单,也是一种最常用的构造函数的方法,它不仅可以对关键字直接取模,也可在折叠、平方中等运算之后取模。在哈希表的建立中,很容易出现同义词,这些同义词的出现也导致了建立哈希表时冲突的出现,如果不解决这些冲突那么建立好的哈希表与预料的哈希表不同。关于处理冲突的方法主要有:开放定址法、再哈希法、链地址法。本程序中主要用的就是链地址法莱解决冲突的。1.1用户需求分析设计一个程序能够使用哈希表实现电话号码查询系统。该系统能够从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表,能够从输入记录中查找并显示给定用户的记录,最后并且能够进行清除记录和退出功能。1.2功能需求分析1)设计一个结点使该结点包括电话号码、用户名、地址。2)利用用户名和电话号码为关键字建立哈希表,哈希函数用除留余数法构照。3)利用链表法处理冲突问题。4)查找并显示给定用户名,地址,电话号码的记录。5)显示哈希表中的给定用户的记录。6)当完成操作后,可以退出系统。1.3数据需求分析由问题分析知,本设计主要要求分别以电话号码和用户名为关键字建立哈希表,并实现查找功能。所以本设计的核心问题是如何解决散列的问题,亦即设计一个良好的哈希表。由于结点的个数无法确认,并且如果采用线性探测法散列算法,删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法,当出现同义词冲突时,使用链表结构把同义词链接在一起,即同义词的存储地址不是散列表中其他的空地址。首先,解决的是定义链表结点,在链地址法中,每个结点对应一个链表结点,它由三个域组成,而由于该程序需要分别用电话号码和用户名为关键字建立哈希表,所以该链表结点它是由四个域组成.name[8]、num[11]和address[20]都是char浮点型,输入输出都只能是浮点型的。采用链地址法,其中的所有同义词构成一个单链表,再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组,即哈希表。数组元素的下标对应由散列函数求出的散列地址。1.4小结通过以上需求分析,知道了设计一个哈希表的目的和能够“实现什么功能”,为接下来的操作明确方向,罗列了需要运用到的知识,自己应该在接下来的程序设计和实现应该怎么做。系统设计2.1设计内容及要求本设计主要要求分别以电话号码和用户名为关键字建立哈希表,并实现查找功能。本程序的要求是设计散列函数,亦即设计一个良好的哈希表。本程序需要设计两个散列函数才能解决问题,程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数,要添加用户信息,即要有实现添加结点的功能的函数,所以要设计一个必须包括一个输入结点信息、添加结点的函数;要实现查找函数,则必须包括一个查找结点的函数;另外还有一个必不可少的就是运行之后要有一个主菜单,即要设计一个主函数main())。2.2总体设计思路本设计涉及到的数据结构为:哈希表。要求输入电话号码、用户名、地址三个信息,并要求分别以电话号码和用户名为关键字进行查找,所以本问题要用到两个哈希函数,进行哈希查找。在链地址法中,每个结点对应一个链表结点,它由三个域组成,而由于该程序需要分别用电话号码和用户名为关键字建立哈希表,所以该链表结点它是由四个域组成,链地址法结点结构如图:name[8]num[11]address[20]next其中name[8]和num[11]是分别为以电话号码和用户名为关键字域,存放关键字key);address[20](data)为结点的数据域,用来存储用户的地址。Next指针是用来指向下一个结点的地址。2.3程序详细设计流程图2.31以姓名为关键字的Hash()函数流程图开始取整型name[0]赋给key2从0开始取name[i]不为空Key2+=name[i]i++Key2=key%20结束1-1姓名为关键字的Hash()函数流程图2.32添加结点信息流程图:开始申请新的结点newphone,newname即新的号码和名字Newphone=input()Newname指向newphone调用hash()函数调用hash()函数拉链法处理冲突利用用户名为关键字插入结束1-2添加结点信息流程图:2.33按姓名查找流程图:开始调用hash()函数中新结点q指向phone[key]->next不为空q=q->nextq不为空输出无记输出相应录记录结束2.34按号码查找流程图开始调用hash2()函数中新结点q指向phone[key]->next不为空q=q->nextq不为空输出无记输出相应录记录2.35主程序流程图结束开始Main()初始化散列链表(1)并为其动态分配内存空间初始化散列链表(2)并为其动态分配内存空间Menu()主菜单输入选择选择1选择2选择0选择3选择4选择5查找号码输出选6结果find()输出结果选7查找用户find2()进行姓名散列list2()姓名散列结果添加记录apend()进行号码散列号码散列list()结果清空creat();creat2()列表已清空退出系统return0结束2.4详细设计编码2.41建立节点structnode//建节点{charname[8],address[20];//节点中要包含用户名,用户地址,电话号码以及指向下一个结点的指针charnum[11];node*next;};typedefnode*pnode;//typedef可以为一个已有的数据类型声明多个别名,这里为该类型声明了两个指针typedefnode*mingzi;node**phone;node**nam;node*a;2.42对哈希函数的定义voidhash(charnum[11])//以电话号码为关键字建立哈希函数{key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}b)voidhash2(charname[8])//以用户名为关键字建立哈希函数{inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}2.43哈希查找voidfind(charnum[11])//在以电话号码为关键字的哈希表中查找用户信息{hash(num);node*q=phone[key]->next;while(q!=NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q)printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("无此记录\n");}b)、voidfind2(charname[8])//在以用户名为关键字的哈希表中查找用户信息{hash2(name);node*q=nam[key2]->next;while(q!=NULL){if(strcmp(name,q->name)==0)break;q=q->next;}if(q)printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("无此记录\n");}2.44主函数主函数本程序需要创建一个主菜单和一个主函数,主菜单便于用户的使用,主函数中,包括所有功能对应的数值,使之和主菜单相对应。***************************主函数界面设计如下************************添加记录查找记录姓名散列号码散列清空记录退出系统voidmenu()//菜单{system("color2d");printf("********************************************************************************\n");printf("\t\t\t***********欢迎使用***********\t\t\t\n");printf("\n");printf("\t\t\t\t0.添加记录\t\t\t\t\n");printf("\t\t\t\t1.查找记录\t\t\t\t\n");printf("\t\t\t\t2.姓名散列\t\t\t\t\n");printf("\t\t\t\t3.号码散列\t\t\t\t\n");printf("\t\t\t\t4.清空记录\t\t\t\t\n");printf("\t\t\t\t5.退出系统\t\t\t\t\n");}系统测试3.1上机调试1首先键入0,添加结点信息,然后按1进行查找,分别进行号码和姓名查找,最后可在主菜单中,选择号码散列和姓名散列,由此查看程序运行结果。2语法错误及修改:程序是分块写的,调试时可以使用分步调试的方式进行,以便能查找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题,在以姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换,要注意输出不能是“%d”,否则不能输出结果。编写程序时要多注意程序中各种指针的使用,还有各类变量的定义,函数的使用。这些问题均可以根据编译器的警告提示,对应的将其解决。逻辑问题修改和调整:链表结构方法虽然方便了运行,但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。在插入结点,查找结点时尤为突出。对于主菜单和主函数的对应,一定要一致,这样才能保证运行时不会出错。4时间,空间性能分析:散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下,散列函数可以把结点均匀地分布到散列表中,不发生冲突,则查找过程无需比较,其时间复杂度O(n)=1。但在实际使用过程中,为了将范围广泛的关键字映射到一组连续的存储空间,往往会发生同义词冲突,这时在查找过程中就需要进行关键字比较。因此散列法的查找性能取决于3个因素:散列函数、冲突处理方法和填充因子。采用链地址法,可以从根本上杜绝“二次聚集”的发生,从而提高散列表的均匀度,提高查找性能,不过也会“浪费”一部分散列表的空间。当散列函数和冲突处理办法固定时,散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然,a越小则发生冲突的机会就越小;反之,a越大冲突的机会就越大,查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a/2。链地址法查找不成功的平均查找长度Un满足:Unc=a+e-a.由以上可以看出,散列表的平均查找长度是填充因子的函数,和散列表的长度没有关系,因此在实际应用中,我们应该选择一个适当的填充因子,以便把平均查找长度控制在一个尽量小的范围内。3.2调试结果与分析程序主菜单添加记录:分别按电话号码和姓名查找:分别输出按姓名和号码散列的结果:清空记录:总结经过为期两周的课程设计,此次课程设计时间虽然比较短暂,但是我通过这次实践学到了很多知识,也了解了自己的很多的不足之处。我是一名信息工程学院的学生,数据结构对于我来说就显得尤为重要,这也是我必须认真学懂的一门课程。在课程设计之前,我们已经学习C语言这门课程已经一个学期,对其有了一定的了解,但是更多的还是停留在学习了解的范围,对里面的好多东西还是很陌生,并不是很熟练,有着许多欠缺,更多的在运用起来的时候还是感到很不好动手。C语言课堂上许多关于C语言的语法规则,听起来十分枯燥无味,也不容易记住,死记硬背是不可取的。然而要使用C语言这个工具解决实际问题,又必须掌握它。通过多次上机练习,对于语法知识有了感性的认识,加深对它的理解,在理解的基础上就会自然而然地掌握C语言的语法规定。对于一些内容自己认为在课堂上听懂了,但上机实践中会发现原来理解的偏差,更加巩固了学过的知识,而且在设计的时候学要系统的知识,也是一个较大的挑战,某一方面知识的欠缺都将影响到整个程序的设计。我从原来的对这门课程的不懂,到目前的能够独立完成一个小型程序。这次课程设计,重温了和学习了许多有关c语言的知识,还掌握了一些现实中编程的一些小技巧,实际的编程能力也得到了历练,本次课程设计对我帮助很多。附录************************程序源代码**************************#include#include#defineNULL0unsignedintkey;//定义两个关键字unsignedintkey2;int*p;structnode//建节点每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针{charname[8],address[20];charnum[11];node*next;};typedefnode*pnode;//typedef可以为一个已有的数据类型声明多个别名,这里为该类型声明了两个指针typedefnode*mingzi;node**phone;node**nam;node*a;voidhash(charnum[11])////哈希函数,以电话号码为关键字建立哈希函数哈希函数的主旨是将电话号码的十一位数字全部加起来{inti=3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}voidhash2(charname[8])//哈希函数以用户名为关键字建立哈希函数//利用强制类型转换,将用户名的每一个字母的ASCLL码值相加并且除以20后的余数{inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}node*input()//输入节点信息,建立结点,并将结点的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;//对于指针类型返回的是地址}intapend()//添加节点{node*newphone;node*newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;hash(newphone->num);//利用哈希函数计算出对应关键字的存储地址hash2(newname->name);newphone->next=phone[key]->next;//利用电话号码为关键字插入phone[key]->next=newphone;//是采用链地址法,拉链法处理冲突的散列表结构newname->next=nam[key2]->next;//利用用户名为关键字插入nam[key2]->next=newname;return0;}voidcreate()//新建节点{inti;phone=newpnode[20];//动态创建对象数组for(i=0;i<20;i++){phone[i]=newnode;phone[i]->next=NULL;}}voidcreate2()//新建节点{inti;nam=newmingzi[20];for(i=0;i<20;i++){nam[i]=newnode;nam[i]->next=NULL;}}voidlist()//显示列表{inti;node*p;for(i=0;i<20;i++){p=phone[i]->next;while(p){printf("%s_%s_%s\n",p->name,p->address,p->num);p=p->next;}}}voidlist2()//显示列表{inti;node*p;for(i=0;i<20;i++){p=nam[i]->next;while(p){printf("%s_%s_%s\n",p->name,p->address,p->num);p=p->next;}}}voidfind(charnum[11])//在以电话号码为关键字的哈希表中查找用户信息{hash(num);node*q=phone[key]->next;while(q!=NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q)printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("无此记录\n");}voidfind2(charname[8])//在以用户名为关键字的哈希表中查找用户信息{hash2(name);node*q=nam[key2]->next;while(q!=NULL){if(strcmp(name,q->name)==0)break;q=q->next;}if(q)printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("无此记录\n");}voidmenu()//菜单{printf("0.添加记录\n");printf("1.查找记录\n");printf("2.姓名散列\n");printf("3.号码散列\n");printf("4.清空记录\n");printf("5.退出系统\n");}intmain(){charnum[11];charname[8];create();create2();intsel;while(1){menu();scanf("%d",&sel);if(sel==1){printf("6号码查询,7姓名查询\n");intb;scanf("%d",&b);if(b==6){printf("请输入电话号码:\n");scanf("%s",num);printf("输出查找的信息:\n");find(num);}else{printf("请输入姓名:\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)return0;}return0;}
本文档为【(完整word版)课程设计试验报告-哈希表的设计与实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: ¥13.0 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
is_916672
暂无简介~
格式:doc
大小:650KB
软件:Word
页数:0
分类:
上传时间:2021-10-15
浏览量:9