《哈希表》课程设计报告

《《哈希表》课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计《哈希表的操作》设计报告一目的通过此次课程设计，让学生充分掌握对哈希表的有关操作，例如除留余数法的运用，处理冲突的三个办法：线性探测再散列，二次探测再散列，连地址法等。加深学生对于哈希表这种独特存储方式（区别于线性存储和链式存储）的理解，和几种算法之间的优越性的体会。二需求分析1、功能需求①．用户能够自定义输入单词，存入哈希表里；②．用户能够对当前哈希表进行管理。操作内容包括：查看当前哈希表、搜索某个单词、插入任意单词、删除表中某个单词、查看当前表的平均搜索长度、置空当前哈希表。③．程序有良好的交互界面，有操作提

2、示和出错提示，方便用户使用和进出入程序。2、程序约束①．哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。②．使用C/C++语言编写，程序模块化设计。三概要设计1、模块设计程序分为主程序模块和哈希表类定义模块，主程序存放在main.app中，哈希表类存放在HashTable.h头文件中。①．主程序模块用于数据和DOS用户界面的初始化，主函数mai()内部定义子函数function()，调用哈希表类中的各个功能函数。②．哈希表类定义Calculate(strings)单词key值计算函数，类友元形参s传送输入的单词。由于单

3、词为string型，不方便直接拿来参与取余数计算，故用计算函数求出一个key来，同时可以减少冲突（字母相同的单词key有可能不同）。FindPos(intkey,stringvalue)地址查找函数，类成员key传送计算出的单词的关键值，value传送输入的单词，下同。此函数为查找、插入、删除等函数提供地址搜索服务。Search(intkey,stringvalue)查找函数，类成员Insert(stringvalue)插入函数，类成员Remove(intkey,stringvalue)删除函数，类成员makeEmpty()置空哈希

4、表函数，类成员15《数据结构》课程设计getInfo(intaddress)获取某个地址中元素的信息，类成员形参address是哈希表中某元素的地址（数组下标），通过key%divitor得到getSize(HashTableHT)获取哈希表存储情况，类友员ASL(HashTableHT)平均查找长度计算函数，类友元四详细设计1、主要功能实现①．全局定义：#defineDefaultSize30数组最大容量divitor取余除数，设为29（≤30的最大质数）②．单词key计算：intCalculate(strings){//key计

5、算函数：word前5个字符的ASCII码+单词长度//不足5个字符的word，用所有字符的ASCII码+单词长度intk=0,len;len=s.length();if(len<5){for(unsignedinti=0;i

6、配的元素，搜索成功，则函数返回改元素的位置//否则返回插入点（如果有足够空间的话）intaddress=key%divitor;intj=address;do{if(info[j]==Empty

7、

8、(info[j]==Active&&ht[j]==value)){t1++;returnj;}//找到else{j=(j+1)%TableSize;t1++;}//当做循环表处理，找出下一个空地址}while(j!=address);returnj;//转一圈回到起点，表已满，失败}//t1在这个函数体里面增加的量△t1为某一元素探查的次

9、数④．搜索、插入、删除函数相同结构：TypeName(type1paramater1,type2paramater2){//调用FindPos（type1paramater1,type2paramater2）//检查FindPos返回值，并对此作出相应判断//根据以上内容作出处理15《数据结构》课程设计//返回}⑤．ASL设计：第一步：设立全局变量t1,t2，分别代表成功和不成功的ASL公式的分子。第二步：在FindPos处设立一个监听变量t，每次查找t自加1，直到查找到合适地址。t的增量△t就是这个元素的查找次数。第三步：在Ins

10、ert处用t监听，插入成功t不变，失败则t自减1。第四步：在Remove处用t监听，首先将t赋值给一个中间变量temp，经过FindPos地址查找后，t的增量△t=t-temp。删除这个元素，意味着这个元素的t要减去这元素的查找次数，