散列表的线性探测查找
XXX 学院
程设计（实习）报告
题 目
姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称:
计算机与电子工程学院
2011年12月
课程设计(实习) 评审表
课程设计(实习) 作品验收表
目录
1 课程设计任务与要求 ············································································ 1 1.1 课程设计任务 ················································································ 1 1.2 问题分析 ························································································· 2 2 系统总体设计 ························································································ 2 2.1 数据结构 ························································································· 2 2.2 模块构成 ························································································· 3 2.3 系统组成 ························································································· 3 3 系统详细设计 ························································································ 4 4 系统实现与测试 ···················································································· 7 4.1 系统测试 ························································································· 7 4.2 系统测试结果 ················································································· 7 5 课程设计总结 ······················································································ 10 参考文献 ·································································································· 11 附录 ··········································································································· 12
1 课程设计任务与要求 1.1 课程设计任务
哈希表操作，采用线性探测法处理冲突并查找
课题的目的和任务：根据数据元素的关键字和哈希函数建立哈希表并初始化哈希表，用开放定址法处理冲突，按屏幕输出的功能表选择所需的功能实现用哈希表对数据元素的插入，显示，查找，删除。
初始化哈希表时把elem[MAXSIZE]、elemflag[MAXSIZE]和count 分别置0。创建哈希表时按哈希函数创建哈希表，输入数据元素的关键字时，以“0”结束输入且要求关键字为正整数，数据元素个数不允许超过表长MAXSIZE 。
输出的形式：根据所选择的哈希表的功能输出相应提示语句和正确结果。 程序的功能：将一组个数不超过哈希表长度的数据元素，按其关键字和哈希函数存入哈希表中，如果产生冲突用开放定址法处理并找出相应的地址。能实现用哈希表对数据元素的插入，显示，查找，删除。
测试数据：maxsize=10 哈希函数：H （key ）=key%7
处理冲突方法：开放定址法 Hi=(H(key)+di)%13 i=1,2,3,…,9
1.2 问题分析
哈希表又称散列表。哈希表存储的基本思想是：以数据表中的每个记录的关键字 k 为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H 为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。
处理冲突的方法：
开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k
2.di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k
3.di=伪随机数序列，称伪随机探测再散列。
再散列法：Hi=RHi(key), i=1,2,…,k. RHi 均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间；
链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中；建立一个公共溢出区。
2 系统总体设计 2.1 数据结构
ADT HashTable {数据对象：D1={ai|ai∈elem[MAXSIZE],i=0,1,2,…,0≦n ≦MAXSIZE }elem [MAXSIZE]是哈希表中关键字的集合，MAXSIZE 为哈希表长。} D2={ai|ai∈elemflag[MAXSIZE]是哈希表中有无关键字的标志的集合，MAXSIZE 为哈希表长。}
基本操作：Hash(key)
初始条件：数据元素关键字key 已存在
操作结果：根据哈希函数计算相应地址，并返回此地址。 基本操作：InitialHash(HashTable &H) 初始条件：哈希表H 已存在
操作结果：初始化哈希表把elem[MAXSIZE]、elemflag[MAXSIZE]和count 分别置0。
基本操作：SearchHash(HashTable &H,int k) 初始条件：哈希表H 已存在
操作结果：在开放定址哈希表H 中查找关键字为k 的元素，若查找成功，并返回SUCCESS ；否则返回UNSUCCESS 。
基本操作：InsertHash(HashTable &H,int e) 初始条件：哈希表H 已存在
操作结果：查找不成功时插入数据元素e 到开放定址哈希表H 中，并返回SUCCESS ；否则输出已有此数！插入失败！并返回UNSUCCESS 。
基本操作：CreateHash(HashTable &H) 操作结果：构造哈希表。 基本操作：PrintHash(HashTable H) 初始条件：哈希表H 已存在
操作结果：将哈希表存储状态显示输出。 基本操作：DeleteHash(HashTable &H,int e) 初始条件：哈希表H 已存在
操作结果：若通过哈希函数找到相应的位置并且此位置的elemflag[MAXSIZE]==1，删除相应位置的数据元素的关键字并把elemflag[MAXSIZE]==2，否则，输出无此数的提示语。
2.2 模块构成
本程序包括如下功能模块：哈希函数模块，冲突处理模块，哈希表初始化模块，哈希表创建模块，哈希表显示模块，按关键字查找模块，插入模块，删除模块和主程序模块。
2.3 系统组成
系统整体流程图如下：
3 系统详细设计
（1）初始化哈希函数
次模块用于初始化哈希函数，便于后面选择操作。如创建哈希表、查找、插入、删除、输出哈希表等功能。 （2）查找函数
查找函数部分流程图如下：
此模块用来查找关键字为k 的元素，先调用哈希函数，如果相应的地址上的
数等于k ，则返回1。如果相应地址有数但不等于k 并且H.elemflag[t]==1，则用开放定址法中的线性探测法处理冲突，否则就返回0。此处用到冲突处理方法。 （3）插入函数
插入函数部分流程图如下：
次模块用来插入元素e ，输入一个元素e ，如果存在此元素，则显示“已有此数！” “查找失败”。若不存在次数，则插入，并显示“插入成功” （4）创建哈希表的函数
次模块用于常见哈希表，方便用户输入数据。任意输入规定范围内的几个数，并以0结束，再调用此函数。 （5）显示函数
此模块定义了显示元素及其位置，方便用户使用与查看，它根据关键字及关键字标志来标识用户需要的数据。 （6）删除函数
此模块用来删除指定的元素，用户根据提示输入任意数据，若该数存在已创建的哈希表里，则能成功删除，并返回1。若该数不存在，则删除失败，并显示“无此数！” （7）主函数
主函数模块定义了功能选择区，包括1、初始化哈希表2、创建哈希表3、查找4、插入5、删除6、输出哈希表0、退出。总共7项，并包括提示输入的各个选项共用户选择使用。
4 系统实现与测试
4.1 系统测试
1、SearchHash 函数中开始处理冲突时没有%MAXSIZE造成查找不完全，影响以后的几乎所有子函数。
2、CreateHash 函数用while 循环创建函数，当输入为0时结束，当输入的数已存在时，没有cin>>e;语句造成无限循环。
3、输出时用”\t”没有加双引号，造成错误。
4.2 系统测试结果
（1）初始化哈希表并输出哈希表：
（2）创建哈希表并输出哈希表：
（3）查找功能的测试：
（4）删除功能的测试并输出结果：
（5）插入功能的测试并输出结果：
5 课程设计总结
本次课程设计，我并没有给出测试用例的分析，也没有用多种方式去实现解决冲突。这些都是不足的地方。希望以后能找到比较好的散列函数，并写出比较好的测试用例。实现不用冲突解决方案的对比。
经过一学期的数据结构课程的学习，我现在编程已经比以前模块化多了，这样既不容易出错，而且出了错也较容易查出，其可读性也加强了。
其次，我现在已习惯编程时写注释了，好像它成了我程序不可缺少的一部分似的，这不仅提高了程序的可读性，因为我是直接上机编的，这也让我的思维更清晰，逻辑更分析的更快些。
对于这次课程设计编的程序，关于hash 表的建立和查找，老师上课是讲过的，这一点上没遇到困难，而在于建立和查找的具体环节，会遇到哪几种情况，这些分析上，开始我并没有想周全，漏洞是在调试的时候发现改正的。这说明我想的还是不够细的，要是程序很大是，出现这种逻辑问题就很难发现了。
最重要的是，我开始没能很好的理解题意，最先的程序是为了建hash 表而建的，这种思维是不对的，经过吉老师的点播后，恍然大悟，这个思想上的突破
很有帮助。
还有开始编的程序是以空格分开单词，这样局限性就很大，经过思考和改良，编了这个和编译器识别关键字同样效果的程序，它以标识符允许之外的字符隔开单词，其实际应用性就很好了。程序的实用性是很重要的，这就是我的收获。
6 软件使用说明书
此程序在VC 软件中编译运行后，根据用户需要进行操作，各步骤如下： 第一步：初始化哈希表并输出哈希表。运行后先是显示各个功能区共用户选择，先输入1后回车，则初始化哈希表。在输入6回车，则输出初始化的哈希表。
第二步：创建哈希表并输出哈希表。用户键入2回车，显示“请输入哈希表：”，则用户依次键入1到7并回车最后键入0在回车，再输入6回车，则显示已创建好的哈希表。
第三步：查找功能的测试。输入3回车，则提示“请输入要查找的关键字：”输任意一个数字5再回车，则显示“查找成功！”。再输入3回车则显示“请输入要查找的关键字：”键入6回车，则显示“查找失败！”。测试完毕。
第四步：删除功能的测试并输出结果。先键入5并回车，显示“请输入要删除的关键字：”用户键入5回车，则显示“删除成功！”再键入6回车，则显示删除后的哈希表。再键入5回车，显示“请输入要删除的关键字：”，键入6回车则显示“无此数! ”“删除失败! ”, 测试完毕。
第五步、插入功能的测试并输出结果。键入4回车，显示“请输入要查找的关键字：”, 输入5则显示“插入成功！”再键入6则显示插入关键字后的哈希表。再输入4回车，显示“请输入要插入的关键字：”输入4则显示“已有此数！”“插入失败！”再输入4回车，显示“请输入要插入的关键字：”输入6则显示“插入成功！”。键入6回车显示插入关键字后的哈希表。最后用户键入0并回车，则显示“Press any key to continue”, 按任意键返回，测试完毕。
参考文献
[1] 严慧敏. 《数据结构》. 清华大学出版社.2009年
[2] 钱能. 《C++程序设计教程(第二版) 》. 清华大学出版社
[3] 陈锐. 《零基础学数据结构》. 北京. 清华大学出版社. 2010年1月
[4] 李春葆. 《数据结构教程（3版）》. 北京. 清华大学出版社. 2009年3月
[5] 左飞. 《C++数据结构原理与经典问题求解》. 北京. 电子工业出版.2008年10月
附录
#include
using namespace std;
#include
#include
#include
#define MAXSIZE 10
#define SUCCESS 1
#define UNSUCCESS 0
typedef struct
{ int elem[MAXSIZE];
int elemflag[MAXSIZE]; int count;
}HashTable;
void InitialHash(HashTable &H)/*哈希表初始化*/
{ int i;
H.count=0;
for(i=0;i
}
int Hash(int kn) /*哈希函数H(key)=key MOD 7*/
{ return (kn%7);
}
{ H.elem[i]=0; H.elemflag[i]=0; }
int SearchHash(HashTable &H,int k) /*查找关键字为k 的元素*/
{ int t,s;
s=t=Hash(k);
xun: if(H.elem[t]==k&&H.elemflag[t]==1) return SUCCESS;
}
int InsertHash(HashTable &H,int e)/*插入元素e*/
{ int p;
p=Hash(e);
if(SearchHash(H,e) )
{ cout
else
{ H.elemflag[p]=1;
H.elem[p]=e;
H.count++;
return SUCCESS;
}
}
void CreateHash(HashTable &H)/*创建哈希表*/
{ int s;
int e; cout>e;
} { s=InsertHash(H,e); } if(!s) { } else cin>>e; cout>e;
void PrintHash(HashTable H) /*显示元素及其位置*/
{ cout
}
int DeleteHash(HashTable &H,int e) /*删除元素e*/
{ int i;
int a=0; for(i=0;i
int i; for(i=0;i
} } a++; return SUCCESS; if(!a) { cout
void main()
{ HashTable H;
int m,k,p;
int R;
do{cout
cout
cout
cin>>m; switch(m) { case 1: InitialHash(H);break; case 2: CreateHash(H);break; case 3: cout>k; p=SearchHash(H,k); if(p) cout
} } break; case 4: cout>R; p=InsertHash(H,R); if(p) cout>R; p=DeleteHash(H,R); if(p) cout