数据结构课程设计-散列法的研究

《数据结构课程设计-散列法的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计说明书学院：信息科学与工程学院班级：计算机科学与技术完成人：姓名：学号：指导教师：山东科技大学2013年12月25日课程设计任务书一、课程设计题目：散列法的实验研究二、课程设计应解决的主要问题：（1）数据元素的输入和输出（2）线性再散列法建立哈希表（3）二次探测再散列法建立哈希表（4）链地址法建立哈希表（5）线性再散列法进行数据查找（6）二次探测再散列法进行数据查找（7）链地址法进行数据查找（8）退出系统三、任务发出日期：2013-10-01课程设计完成日期：2013-12-20小组分工说明小组编号7题目：散列法的实验研究小组分工情况：一人独立完成所有工作。组长签字：2

2、013年12月31日指导教师对课程设计的评价成绩：指导教师签字：年月日目录1．需求分析说明-32．概要设计说明-43．详细设计说明-54．调试分析-75．用户使用说明-86．课程设计总结-107．测试结果-108．参考书目-12需求分析说明内部排序教学软件的总体功能要求：散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。基本功能如下：（1）界面友好，易与操作。采用菜单方式进行选择。（2）实现三种方法进行哈希表的构造。包括线性再散列法、二次探测

3、再散列法和链地址法。（3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时输出探查/冲突次数。以下是各功能模块的功能描述：1．主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现功能。2．构造哈希表子模块本模块的主要功能是采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表。3．查找功能及输出子模块本模块的主要功能是在采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算探查/冲突次数。4．输入子模块本模块的主要功能是从键盘中输入数据元素用于构造哈希表。5.输出子模块本模块的主要功能是将数据元素显示在屏幕

4、上。概要设计说明模块调用图：各种构造方法的哈希表数据类型定义为： typedefstruct{intkey;/*关键字*/intsi;/*插入成功时的次数*/}HashTable1;/*哈希表线性探测再散列数据类型定义*/typedefstructHa{intelem;/*数据项*/structHa*next2;/*指向下一个结点的指针*/}HashTable2;/*哈希表链地址法数据类型定义*/typedefstruct{intelem[HashSize];/*表中储存数据元素的数组*/intcount;/*表中储存数据元素的个数*/intsize;/*哈希表的尺寸*/}HashTa

5、ble3;/*哈希表二次探测再散列法数据类型定义*/#defineHashSize53/*哈希表最大长度*/intnum;/*输入数据的个数*/voidGetIn(int*a)/*从键盘输入数据*/ voidGetOut(int*a)/*在屏幕上输出数据*/ voidCreateHashTable1(HashTable1*H,int*a,intnum)/*线性探测在散列哈希表*/voidSearchHash1(HashTable1*h,intdata)/*线性探测在散列法查找*/ voidCreateHashTable2(HashTable2*H,int*a,intnum)/*哈希表

6、链地址*/ intSearchHash2(HashTable2*h,intdata,intnum)/*链地址法查找*/ voidCreateHash3(HashTable3*h,int*a,intnum)/*二次探索表*/ intCollision(intp,intc)/*二次探测再散列法解决冲突*/ voidSearchHash3(HashTable3*h,intdata)/*哈希表二次探索再散列查找*/intsystem(constchar*string)/*清屏*/详细设计说明1．主函数模块首先构造三种类型的哈希表，并对哈希表进行初始化。进入循环后在屏幕上输出相应的操作指示，然后

7、通过输入0-8调用所选择的函数进行相应操作。主函数代码如下：intmain(){intdata,i;HashTable1hash1[HashSize];HashTable2hash2[HashSize];HashTable3*ha;/*定义三种类型的哈希表*/ha=(HashTable3*)malloc(sizeof(HashTable3));for(i=0;ielem[i]=0;ha-