《哈希表》课程设计报告

数据结构散列表(哈希表)课程设计报告及源代码

《哈希表的操作》设计报告

一 目的

通过此次课程设计，让学生充分掌握对哈希表的有关操作，例如除留余数法的运用，处理冲突的三个办法：线性探测再散列，二次探测再散列，连地址法等。加深学生对于哈希表这种独特存储方式（区别于线性存储和链式存储）的理解，和几种算法之间的优越性的体会。

二 需求分析

1、功能需求

①．用户能够自定义输入单词，存入哈希表里；

②．用户能够对当前哈希表进行管理。操作内容包括：查看当前哈希表、搜索某个单词、插入任意单词、删除表中某个单词、查看当前表的平均搜索长度、置空当前哈希表。

③．程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程序。

2、程序约束

①．哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。 ②．使用C/C++语言编写，程序模块化设计。

三 概要设计

1、模块设计

程序分为主程序模块和哈希表类定义模块，主程序存放在main.app中，哈希表类存放在HashTable.h头文件中。

①．主程序模块

用于数据和DOS用户界面的初始化，主函数mai()内部定义子函数function()，调用哈希表类中的各个功能函数。

②．哈希表类定义

Calculate(string s) 单词key值计算函数，类友元

形参s传送输入的单词。由于单词为string型，不方便直接拿来参与取余数计算，故用计算函数求出一个key来，同时可以减少冲突（字母相同的单词key有可能不同）。

FindPos(int key,string value) 地址查找函数，类成员

key传送计算出的单词的关键值，value传送输入的单词，下同。此函数为查找、插入、删除等函数提供地址搜索服务。

Search(int key,string value) 查找函数，类成员 Insert(string value) 插入函数，类成员 Remove(int key,string value) 删除函数，类成员 makeEmpty() 置空哈希表函数，类成员

数据结构散列表(哈希表)课程设计报告及源代码

getInfo(int address) 获取某个地址中元素的信息，类成员

形参address是哈希表中某元素的地址（数组下标），通过key % divitor得到 getSize(HashTable HT) 获取哈希表存储情况，类友员 ASL(HashTable HT) 平均查找长度计算函数，类友元

四 详细设计

1、主要功能实现

①．全局定义：#define DefaultSize 30 数组最大容量

divitor 取余除数，设为29（≤30的最大质数） ②．单词key计算： int Calculate(string s){

//key计算函数：word前5个字符的ASCII码 + 单词长度 //不足5个字符的word，用所有字符的ASCII码 + 单词长度 }

③．地址查找：

int HashTable::FindPos(int key,string value) const{

//搜索一个散列表中关键码与key匹配的元素，搜索成功，则函数返回改元素的位置 //否则返回插入点（如果有足够空间的话）

int address= key % divitor; int j = address; do{

if(info[j]==Empty || (info[j]==Active && ht[j]==value)){ t1++;return j;} //找到 else { j=(j+1) % TableSize; t1++; } //当做循环表处理，找出下一个空地址

int k=0,len; len=s.length(); if(len<5){ else{ k+=len; return k;

for(int i=0;i<=4;i++) k+=(int)s[i]; }

for(unsigned int i=0;i<s.length();i++) k+=(int)s[i]; }

}while (j != address);

return j; //转一圈回到起点，表已满，失败

} //t1在这个函数体里面增加的量△t1为某一元素探查的次数 ④．搜索、插入、删除函数相同结构： Type Name(type1 paramater1, type2 paramater2){

//调用FindPos（type1 paramater1, type2 paramater2） //检查FindPos返回值，并对此作出相应判断 //根据以上内容作出处理

数据结构散列表(哈希表)课程设计报告及源代码

//返回 }

⑤．ASL设计：

第一步：设立全局变量t1,t2，分别代表成功和不成功的ASL公式的分子。

第二步：在FindPos处设立一个监听变量t，每次查找t自加1，直到查找到合适地址。t的增量△t就是这个元素的查找次数。

第三步：在Insert处用t监听，插入成功t不变，失败则t自减1。

第四步：在Remove处用t监听，首先将t赋值给一个中间变量temp，经过FindPos地址查找后，t的增量△t=t-temp。删除这个元素，意味着这个元素的t要减去这元素的查找次数，即t-2*(t-temp)。

ASLsucc = t1 / 输入单词的个数（或已用地址的数量） ASLunsucc = t2 / 表长 ， t2的计算如下：

2、流程图

数据结构散列表(哈希表)课程设计报告及源代码

五 调试分析

1、本次课程设计采用的是除留余数法构造了哈希表，除数的选择很重要。如果选得不好，会造成很多冲突，浪费时间和空间代价。例如，本次设计的哈希表最大长度为30，余数如果取得较小，例如23,17等，相比起最接近30的29来说，会使得一部分元素容易形成堆积，平均搜索长度变大，而且取余的时间也会更长。

2、本次设计处理冲突采用了线性探测再散列的办法。相比起同时闭散列方法的二次探测再散列来说，优点在于功能简单易操作性；缺点是当数据量逐渐加大时，前者的平均查找长度会逐渐比后者大。

3、做为闭散列方法处理冲突问题，不能像连地址法那样的开放地址法一样，随意的用物理删除方法删除表里的元素。否则容易引起搜索链的中断，使得该元素后面发生冲突的元素无法查找到，造成程序和实际情况有误。

4、在概要设计的阶段发现，无论是搜索、插入还是删除，首先都要对元素进行寻址操

数据结构散列表(哈希表)课程设计报告及源代码

作，因此独立设立一个寻址函数FindPos，供以上三个函数共用，以减少代码的重复。

六 测试结果

1.单词输入

2.表内存储情况

3.输入完毕立即测试ASL的情况

数据结构散列表(哈希表)课程设计报告及源代码

4查找测试

5. 插入删除测试

数据结构散列表(哈希表)课程设计报告及源代码

测试结果：没有发现错误。

七 用户使用说明

1、功能使用说明

①．查课表：查看当前哈希表的存储情况

②．搜索：输入一个单词，查询表内的情况。不支持key查询，因为相同的key可能有不同的单词对应，例如”pa”和”le”，key都是211。

③．插入：输入单词，插入到哈希表中。插入后会立即显示插入元素的情况。 ④．删除：输入单词，在表中搜索，如果存在则删除，不存在则提示不存在或者已删除。不支持输入key进行删除，原因同②。暂时不支持直接输入地址进行删除。

⑤．显示ASL：查看当前表中的ASL值。 ⑥．置空表：将当前表初始化为一张空表。

2、注意事项

本次设计重点在对哈希表的处理上，没有对选择界面进行很有效的出错处理，请勿在输入数字时输入其他字符， …… 此处隐藏：2820字，全部文档内容请下载后查看。喜欢就下载吧 ……