《数据结构课程设计-散列法的研究》由会员分享，可在线阅读，更多相关《数据结构课程设计-散列法的研究（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计数据结构课程设计说说 明明 书书学 院： 信息科学与工程学院 班 级： 计算机科学与技术 完 成 人：姓 名： 学 号： 指导教师： 山山 东东 科科 技技 大大 学学2013 年 12 月 25 日课课 程程 设设 计计 任任 务务 书书一、课程设计题目：一、课程设计题目： 散列法的实验研究 二、课程设计应解决的主要问题：二、课程设计应解决的主要问题：（1） 数据元素的输入和输出 （2） 线性再散列法建立哈希表 （3） 二次探测再散列法建立哈希表 （4） 链地址法建立哈希表 （5） 线性再散列法进行数据查找 （6） 二次探测再散列法进行数据查找 （7） 链地址法进行数据查找
2、（8） 退出系统 三、任务发出日期：三、任务发出日期： 2013-10-01 课程设计完成日期：课程设计完成日期： 2013-12-20 小组分工说明小组分工说明小组编号小组编号 7 题题 目：目： 散列法的实验研究 小组分工情况：小组分工情况：一人独立完成所有工作。组长签字：组长签字： 20132013 年年 1212 月月 3131 日日指导教师对课程设计的评价指导教师对课程设计的评价成绩：成绩： 指导教师签字：指导教师签字： 年年 月月 日日 目目 录录1需求分析说明-32概要设计说明-43详细设计说明-54调试分析-75用户使用说明-86课程设计总结-107测试结果-108参考书目-1
3、2需求分析说明需求分析说明内部排序教学软件的总体功能要求：内部排序教学软件的总体功能要求：散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲 突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型 的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。基本功能如下： （1）界面友好，易与操作。采用菜单方式进行选择。 （2）实现三种方法进行哈希表的构造。包括线性再散列法、二次探测再 散列法和链地址法。 （3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时 输出探查/冲突次数。以下是各功能模块的功能描述： 1 1主函数模块主函数模块 本模块的主要功
4、能是初始化图形界面，调用各模块，实现功能。 2 2构造哈希表子模块构造哈希表子模块 本模块的主要功能是采用线性再散列法、二次探测再散列法、链地址法 三种方法构造哈希表。 3 3查找功能及输出子模块查找功能及输出子模块 本模块的主要功能是在采用线性再散列法、二次探测再散列法、链地址 法三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算 探查/冲突次数。 4 4输入子模块输入子模块 本模块的主要功能是从键盘中输入数据元素用于构造哈希表。 5.5.输出子模块输出子模块本模块的主要功能是将数据元素显示在屏幕上。概要设计说明概要设计说明模块调用图：模块调用图： 各种构造方法的哈希表数据类型
5、定义为： typedef structint key; /*关键字*/int si; /*插入成功时的次数*/ HashTable1; /*哈希表线性探测再散列数据类型定义*/typedef struct Haint elem; /*数据项*/struct Ha *next2; /*指向下一个结点的指针*/ HashTable2; /*哈希表链地址法数据类型定义*/typedef structint elemHashSize; /*表中储存数据元素的数组*/int count; /*表中储存数据元素的个数*/int size; /*哈希表的尺寸*/ HashTable3; /*哈希表二次探测再
6、散列法数据类型定义*/#define HashSize 53 /*哈希表最大长度*/ int num; /*输入数据的个数*/void GetIn(int *a) /*从键盘输入数据*/ void GetOut(int *a) /*在屏幕上输出数据*/ void CreateHashTable1(HashTable1 *H,int *a,int num)/*线性探测在散 列哈希表*/ void SearchHash1(HashTable1 *h,int data) /*线性探测在散列法查找*/ void CreateHashTable2(HashTable2 *H,int *a,int num
7、)/*哈希表链地 址*/ int SearchHash2(HashTable2 *h,int data,int num) /*链地址法查找*/ void CreateHash3(HashTable3 *h,int *a,int num) /*二次探索表*/ int Collision(int p,int c) /*二次探测再散列法解决冲突*/ void SearchHash3(HashTable3 *h,int data) /*哈希表二次探索再散列查 找*/ int system(const char *string) /*清屏*/ 详细设计说明详细设计说明1 1主函数模块主函数模块 首先构造
8、三种类型的哈希表，并对哈希表进行初始化。进入循环后在屏 幕上输出相应的操作指示，然后通过输入 0-8 调用所选择的函数进行相应操 作。 主函数代码如下： int main() int data,i;HashTable1 hash1HashSize;HashTable2 hash2HashSize;HashTable3 * ha; /*定义三种类型的哈希表*/ha=(HashTable3 *)malloc(sizeof(HashTable3);for(i=0; ielemi=0;ha-count=0;ha-size=HashSize;int aHashSize;a0=0;while(1)prin
9、tf(“n “);printf(“n 欢迎使用本系统 “);printf(“n “);printf(“n 散列法的实验研究 “);printf(“n 【1】. 添加数据信息 “);printf(“n 【2】. 数据的输出 “);printf(“n 【3】. 建立哈希表(线性再散列) “);printf(“n 【4】. 建立哈希表(二次探测再散列) “);printf(“n 【5】. 建立哈希表(链地址法) “);printf(“n 【6】. 线性再散列法查找 “);printf(“n 【7】. 二次探测再散列法查找 “);printf(“n 【8】. 链地址法查找 “);printf(“n 【
10、0】. 退出程序 “);printf(“n “);printf(“n“);printf(“n“);printf(“请输入一个任务选项“);int x;scanf(“%d“,switch(x)case 1: /*调用输入函数，从键盘键入需要添加的数据*/GetIn (a);break;case 2: /*若已有数据输入，则调用数据输出函数*/if(a0=0)printf(“您还没有输入任何数据!n“);elseGetOut(a);break;case 3: /*调用函数用线性再散列法构造哈希表*/if(a0=0)printf(“您还没有输入任何数据!n“);elseCreateHashTable
11、1(hash1,a,num);break;case 4: /*调用函数用二次探测再散列法构造哈希表*/if(a0=0)printf(“您还没有输入任何数据!n“);elseCreateHash3(ha,a,num);break;case 5: /*调用函数用链地址法构造哈希表*/if(a0=0)printf(“您还没有输入任何数据!n“);elseCreateHashTable2(hash2,a,num);break;case 6: /*调用函数用线性再散列法查找*/if(a0=0)printf(“您还没有输入任何数据!n“);elseprintf(“请输入你查找的数据“);scanf(“%d
12、“,SearchHash1(hash1,data);break;case 7: /*调用函数用二次探测再散列法查找*/if(a0=0)printf(“您还没有输入任何数据!n“);elseprintf(“请输入你查找的数据“);scanf(“%d“,SearchHash3(ha,data);break;case 8: /*调用函数用链地址法查找*/if(a0=0)printf(“您还没有输入任何数据!n“);elseprintf(“请输入你查找的数据“);scanf(“%d“,SearchHash2(hash2,data,num);break;case 0: /*退出系统*/exit(-1);break;getchar();printf(“n 请按回车键返回n“);getchar();system(“cls“); /*清屏*/ 2 2查找功能及输出子模块查找功能及输出子模块 根据题目要求，可将这个系统分为以下几个模块： 1.线性再散列法建立哈希表：线性再散列法建立哈希表：构造哈希函数 h(x)=h(key)%HashSiz
