专业课程设计试验报告哈希表的设计和实现.doc

数据构造课程设计题 目 哈希表设计与实现 作 者 院 系 信息工程学院 专 业 信息管理与信息系统 学 号 指引教师 张 慧 答辩时间 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按姓名查找流程图:72.34按号码查找流程图82.35主程序流程图92.4详细设计编码112.41建立节点112.42对哈希函数定义112.43哈希查找122.44主函数123系统测试133.1上机调试133.2调试成果与分析144总结185附录181系统需求分析在信息化时代今天，计算机技术已经是发展到一种很可观地步了，特别是面向窗口操作系统浮现，使得程序设计更加容易了。在过去计算机内存容量小，CPU计算速度慢，关于程序设计中数据构造也因而提出来诸多关于解决这方面问题。哈希表就是其中之一，哈希表是一种由核心字与值构成特殊一种数据构造。它浮现重要是为理解决在构造中查找记录时需要进行一系列和核心字比较,这一类查找办法是建立在“比较”基本上，在顺序等查找中，查找效率是依赖于查找过程中所比较次数。抱负状况是但愿不通过任何比较一次存取便能得到所查记录，那就必要在记录存储位置和它核心字之间建立一种拟定相应关系，使得每个核心字和构造中一种唯一存储位置相相应。因而在查找时只要依照这个相应关系找到给定值像。若构造中存在核心字和该值相等记录，则所要查找数就必然就是这个所查找到记录。哈希函数是建立哈希表一种重要成员，它构造办法分为如下几种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。本程序中重要用是除余取留法,除留取余法重要是取核心字被某个不不不大于哈希表表长m数p出后所得余数为哈希地址即:H(key)=key MOD p，pnextq 不为空调用hash()函数中新结点q指向phonekey-next开始2.34按号码查找流程图开始调用hash2()函数中新结点q指向phonekey-nextq 不为空q=q-nextq不为空输出无记录输出相应记录结束2.35主程序流程图开 始Main ()初始化散列链表（1）并为其动态分派内存空间初始化散列链表（2）并为其动态分派内存空间Menu（）主菜单输入选取选取1选选7查找号码find()查找顾客find2()输出成果输出成果选取2选取0选取3选取4选取5进行姓名散列list2()姓名散列成果添加记录 apend()退出系统return 0进行号码散列 list()清空creat();creat2()列表已清空号码散列成果结 束2.4详细设计编码2.41建立节点struct node /建节点 char name8,address20;/节点中要包括顾客名，顾客地址，电话号码以及指向下一种结点指针char num11；node * next；typedef node* pnode；/typedef可觉得一种已有数据类型声明各种别名，这里为该类型声明了两个指针typedef node* mingzi；node *phone；node *nam；node *a;2.42对哈希函数定义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；2.43哈希查找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)；2.44主函数主函数本程序需要创立一种主菜单和一种主函数，主菜单便于顾客使用，主函数中，涉及所有功能相应数值，使之和主菜单相相应。*主函数界面设计如下* 0添加记录 1查找记录 2姓名散列 3号码散列 4清空记录 5退出系统void menu() /菜单 system(color 2d);printf(*n);printf(ttt*欢迎使用*tttn);printf(n);printf(tttt 0.添加记录ttttn)；printf(tttt 1.查找记录ttttn)；printf(tttt 2.姓名散列ttttn)；printf(tttt 3.号码散列ttttn)；printf(tttt 4.清空记录ttttn)；printf(tttt 5.退出系统ttttn)； 3系统测试3.1上机调试1一方面键入0,添加结点信息,然后按1进行查找,分别进行号码和姓名查找,最后可在主菜单中，选取号码散列和姓名散列,由此查看程序运营成果。2语法错误及修改：程序是分块写,调试时可以使用分步调试方式进行,以便能查找看程序是在哪出错了。本算法使用了链表构造和链地址法解决冲突问题，在以姓名为核心字哈希表中要注意涉及ASCLL码类型转换，要注意输出不能是“%d”，否则不能输出成果。编写程序时要多注意程序中各种指针使用，尚有各类变量定义，函数使用。这些问题均可以依照编译器警告提示，相应将其解决。3逻辑问题修改和调节：链表构造办法虽然以便了运营，但是增长了对算法过程结识难度。在本程序中每一种函数中都需要涉及到指针操作。因此需要仔细分析函数中指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数相应，一定要一致，这样才干保证运营时不会出错。4时间，空间性能分析：散列法本质上是一种通过核心字直接计算存储地址办法。在抱负状况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。但在实际使用过程中，为了将范畴广泛核心字映射到一组持续存储空间，往往会发生同义词冲突，这时在查找过程中就需要进行核心字比较。因而散列法查找性能取决于3个因素：散列函数、冲突解决办法和填充因子。采用链地址法，可以从主线上杜绝“二次汇集”发生，从而提高散列表均匀度，提高查找性能，但是也会“挥霍”一某些散列表空间。当散列函数和冲突解决办法固定期，散列法查找性能就取决于散列表填充因子。填充因子a=表中已有结点数/表长度。填充因子a标志表添满限度。很显然，a越小则发生冲突机会就越小；反之，a越大冲突机会就越大，查找性能也就越低。哈希表链地址法查找成功平均查找长度SNc=1+a/2。链地址法查找不成功平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表平均查找长度是填充因子函数，和散列表长度没关于系，因而在实际应用中，咱们应当选取一种恰当填充因子，以便把平均查找长度控制在一种尽量小范畴内。3.2调试成果与分析程序主菜单添加记录:分别按电话号码和姓名查找:分别输出按姓名和号码散列成果:清空记录:4总结通过为期两周课程设计，本次课程设计时间虽然比较短暂，但是我通过这次实践学到了诸多知识，也理解了自己诸多局限性之处。我是一名信息工程学院学生，数据构造对于我来说就显得尤为重要，这也是我必要认真学懂一门课程。在课程设计之前，咱们已经学习C语言这门课程已经一种学期，对其有了一定理解，但是更多还是停留在学习理解范畴，对里面好多东西还是很陌生，并不是很纯熟，有着许多欠缺，更多在运用起来时候还是感到很不好动手。C语言课堂上许多关于C语言语法规则，听起来十分枯燥无味，也不容易记住，死记硬背是不可取。然而要使用C语言这个工具解决实际问题，又必要掌握它。通过多次上机练习，对于语法知识有了感性结识，加深对它理解，在理解基本上就会自然而然地掌握C语言语法规定。对于某些内容自己以为在课堂上听懂了，但上机实践中会发现本来理解偏差，更加巩固了学过知识，并且在设计时候学要系统知识，也是一种较大挑战，某一方面知识欠缺都将影响到整个程序设计。我从本来对这门课程不懂，到当前可以独立完毕一种小型程序。这次课程设计，重温了和学习了许多关于c语言知识，还掌握了某些现实中编程某些小技巧，实际编程能力也得到了历练，本次课程设计对我协助诸多。5附录*程序源代码*#include#include #define NULL 0 unsigned 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;inext=NULL； void create2() /新建节点 int 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!= 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)； 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) return 0； return 0；