《哈希表课程设计--哈希表的实现与应用》由会员分享，可在线阅读，更多相关《哈希表课程设计--哈希表的实现与应用（41页珍藏版）》请在金锄头文库上搜索。
1、数据构造课程设计设计说明书哈希表的实现与应用同学姓名学号班级成绩指导教师曹记东题目同学姓名2021 年 3 月 3 日数据构造课程设计评阅书哈希表的实现与应用学号指导教师评语及成果成果：教师签名：年 月 日辩论教师评语及成果成果：教师签名：年 月 日教研室意见总成果：室主任签名：年 月 日摘要随着计算机的普及，社会的信息化不断普及提高，在此课程设计中。设计了一个人员信息查找系统，本查找系统承受 VC+作为软件开发环境，承受本系统可以简洁地实现人员信息的查询，显示全部人员的信息。在编制人员的信息中，具有人员的姓名、联系 、以及人员的地址。在插入人员信息中，承受以姓名为关键字插入，实现了哈希值的插
2、入运算。在查询具体人员的信息是可以承受以姓名为关键查人员信息，也可以承受以号码作为关键字查找人员信息。在用姓名作为关键字查询信息时承受二次散列法处进展冲突处理，在以 号码进展人员的信息查找时承受线性探测法处理冲突。 在界面设设计方面界面清楚，明白。操作简洁，易于用户所承受。关键词：哈希表;信息查找系统;函数名目1课题描述12需求分析23 设计概要23.1系统菜单23.2各个模块之间调用关系33.3数据构造描述与定义43.4 各个模块主要算法描述及流程图54 具体设计114.1 程序描述114.2 具体步骤115 程序编码146 程序调试与测试257 结果分析328总结33参考文献341课题描述
3、散列表(也叫哈希表),是依据关键码值直接进展访问的数据构造,也就是说,它通过把关键码值映 射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。本课程设计只要完成以下任务：1） 完成哈希表的初始化、哈希函数值的运算、插入元素、查找元素。2） 求出每次哈希表查找的平均查找长度ASL。3)利用线形探测和二次探测再散列处理冲突的功能。92 需求分析哈希表是用散列表 建立关键码字与其存储位置的对应关系，或者说，由关键码的函数值打算数据的存储地址，是依据关键码值直接进展访问的数据构造,查找速度极快O(1),查找效率与元素个数 n 无关！在设计中需要实现哈希表的
4、初始化、插入运算，以及每次查找的哈希表的平均长度ASL,同时在设计中要实现用线性探测和二次散列两种方法处理冲突等功能。在建立哈希表中建立的不同哈希表会有不同的平均长度，同不同的处理冲突方法会有不同的平均查找长度。CreateSearhHSearchHash2();ash1();Hash2(以 电 话以姓名); 以号号 码 建查询用码查询立 哈 希户信息用户信表(线息getin()ShowICreate; 建 立nformHash1(相 应ation() 现 实的 用; 显示添加的3 设计概要进入主函数,用户输入需要功能代号进入选择选 1:建立用户信息,选。2.显示全部用户信息。3.以姓名关键字
5、插入用户信息。4。以姓名产生哈希表。5，以号码产生哈希表。6，以姓名查找关键字。7 以号码查找用户信息。0，退出系统。分别以上述确定的方法分别以用户名为检索以及以以 号码将用户信息添加到哈希表。在查找用户信息时必需先建立哈希表先进展4、5 步骤。只需输入用户的姓名或号码就可以查找到用户信息。程序用构造体存储用户信息，建立的哈希表便利快速的查找到用户信息。程序用链表的方式存储信息以及构造哈希表具体流程图如下所示:查询系统菜单 main()Create Hash2(); 姓名退出系统产 生哈 希表( 用 二次列散法性 探 测发法)3.1 功能模块户信添加用户信息的用息户息信图 3.2菜单系统3.2
6、 程序主流程图Int nt main()插入用户信息 int InsertH()建 立 用 户 信 息Getin()显 示 所 有 信 息ShowInformati;以姓名产生哈希值int Hash1()以号码产生哈希值int Hash1()冲 突 处 理 函 数 Status collision1()冲突处理函数Status collision2()是是否冲突H-elempp=NULLL是否冲突是H-elempp=N ULL否否以姓名建立哈希表int CreateHash1( )否以号码建立哈希表 int CreateHash1( )以 姓 名 查 找 用 户 信 息 int SearchH
7、ash1()以 号 码 查 找 用 户 信 息 int SearchHash1()完毕程序图 3.2各个模块之间调用关系3.3 数据构造描述与定义用构造体数据定义哈希表typedef struct/哈希表Record *elemHASHSIZE;/数据元素存储基址int count;/当前数据元素个数int size;/当前容量HashTable;用构造体定义建立用户记录typedef struct/记录char name20; char tel20; char add20;Record;初始化哈希表地址，初始化哈希表#define LEN sizeof(HashTable)#define H
8、ASHSIZE54/定义哈希表长HashTable *H;H=(HashTable*)malloc(LEN);/申请哈希表空间地址for(i=0;ielemi=NULL;H-size=HASHSIZE;/哈希表大小H-count=0;/记录哈希表内个数大小Record aMAXSIZE;3.4 主要模块算法描述及流程图1增加信息STARint getin(Record*a,int n)scanf(“%d”,&NUM-BER); int I;if(NUM-BERMAXSIZE)yesprintf(“输入过大，请重新输入：n”)for(i=0,iNUM-BER;i+)return UNSUCESS
9、;);printf(“t 联系人%dn“,i+1);printf(“tt 用户名:“); scanf(“%s“,ai+n.name); printf(“tt 号码:“); scanf(“%s“,ai+n.tel); printf(“tt 地址:“); scanf(“%s“,ai+n.add);return n+NUM_BER;Returnn+NUM-BERSTORP图 3.4.1用来输入用户信息，输入用户信息最大不能超过构造体所定义大小2显示存储信息STARTvoid ShowInformation(Record* a,int n)int ifor(i=0;ielempp!=NULL)pp=c
10、ollision(p,c);NOH-elempp=&(aNUM_BER);H-count+;return SUCCESS图 3.4.3 依据关键字以用户姓名添加用户信息4） 冲突处理函数STARStatus collision1(int p,int &c)p=(p+1)%HASHSIZE; c+;If(pHASHSIZE)YESNOreturnpreturnUNSUCCESS图 3.4.4 建立以姓名为关键字的冲突处理函数STARint CreatHash1()H-count=0;5） 建立哈希表姓名for(i=0;ielempp!=NULLm+;pp=colision1(p,c);if (ppHAshizeNOYESprintf(“第%d 记录无法解决!”,i+1);break;H-elempp=&(ai;H-count+;ASL=float(m+n-1)/(n-1);returnSUCCESS;10STORP图 3.4.5以姓名作为关键字建立哈希表6） 查找姓名SARTint SearchHash1()int p,pp; P=Hash1(str);pp=p;While(H-elempp!=NULL&(eq(str,H-elemppPp=collision1(p,c);H-elempp!=NULL&( eq(str,H-elemppNO
