哈希表查找的设计.docx

1、哈希表查找的设计哈希表查找的设计一问题描述：哈希表查找的设计：设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。二需求分析：程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含数据的录入、查找、删除、显示等功能。本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类型为简单的整型数字，在实用性上还有所欠缺。但根据用户需求的变化，可以对程序的基本数据类型进行改造，以实现更为丰富的功能，进而体现哈希表在查找数据时的优越性。三算法思想：在设定哈希表的抽

2、象数据类型时，要有查找数据元素的操作。另外，插入操作和删除操作也要用到查找数据元素操作，以查看该数据元素是否存在，因此可以设计查找元素操作包括插入和删除操作的查找。因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另一种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。插入操作时寻找空闲单元查找的特征是哈希表中不存在该对象，设计此时查找函数返回该空闲单元位置的“正”值；查找和删除操作时寻找该元素是否在哈希表中已存在的特征是哈希表中已存在该数据元素，设计此时查找函数返回该数据单元位置的“负”值。进而执行后续操作。为了区分哈希表中每一个表元素的当前状态，为每一个表元素

3、设置一个“标志”定为tag。tag=0表示该元素为空；tag=1表示该元素以存放有数据元素；tag=-1表示该元素中存放的数据元素已被删除。判断当tag为0或-1时都可以进行插入操作。四概要设计：1. 哈希表抽象数据类型的定义：ADT HashTable 数据对象：D=ai|aiElemSet, i=1,2,.n, n0 数据关系：R1=|ai-1D, i=1,2,.n 基本操作：Initiate( &h ) 操作结果：构造一个空的哈希表h。SearchHash( h, x, p ) 初始条件：哈希表h已存在；p为除留余数法中除数，由用户指定。 操作结果：查找表中元素与指定数据x比较。元素已存

4、在时返回其所在位置的负数下标、不存在时返回其位置的正数下标、遍历哈希表后未查找到时返回表长。Insert( &h, x, p ) 初始条件：哈希表h已存在。 操作结果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已满时插入操作失败，返回值为0。Delete(&h, x, p ) 初始条件：哈希表h已存在。 操作结果：查找操作后从哈希表中删除元素x。若元素不在表中时删除操作失败，返回值为0。Print( h ) 初始条件：哈希表h已存在。 操作结果：显示哈希表中元素及存储状态。Clear( &h ) 初始条件：哈希表h已存在。 操作结果：清空哈希表。ADT HashTable2. 程序模块

5、：Hash.h头文件，包含哈希表抽象数据类型。Hash.cpp主程序，为哈希表操作面板。 五程序代码：Hash.h文件 #include #include #include #include #include #define TableSize 20 /哈希表长20 #define SUCCESS 1 #define UNSUCCESS 0 typedef int Status; typedef struct /定义元素关键字类型 int key; Elemtype; typedef struct /定义哈希表中基本单元,包含数据与标志两部分 Elemtype elem; /数据部分,存放关键

6、字 int tag; /标志部分,tag=0表示表单元为空, /tag=1表示表单元已存放数据元素, /tag=-1表示表单元中存放的数据已被删除 HashItem; typedef struct /定义哈希表,包含表单元数组与当前存储量 HashItem tableTableSize; int currentSize; /当前哈希表存储量 HashTable; Status Initiate(HashTable *h) /初始化操作 int i; for(i=0; iTableSize; i+) (*h).tablei.tag=0; /tag标志置为0 (*h).tablei.elem.ke

7、y=NULL; /空单元默认值设为NULL (*h).currentSize=0; return SUCCESS; int SearchHash(HashTable h, Elemtype x, int p) /查找元素操作 int i=x.key%p; /除留余数法定哈希地址,主程序中定义一不大于表长的素数p int j=i; while(h.tablej.tag=1 & h.tablej.elem.key!=x.key) /冲突时 j=(j+1)%TableSize; /开放定址法,线性探测再散列,求出新位置j if(j=i) cout哈希表中未查找到x.keyendl; return T

8、ableSize; /全表遍历后未搜索到所给元素,返回表长 if(h.tablej.tag=1) /元素已存在时返回其位置的负数下标 cout该元素在哈希表的第j位endl; return -j; else /元素不存在时返回其位置的下标 cout哈希表中未查找到x.keyendl; return j; Status Insert(HashTable *h, Elemtype x, int p) /插入元素操作 int i=SearchHash(*h, x, p); /先调用查找操作 if(i0) /元素已存在时,插入失败 coutx.key元素已存在,无法再录入,操作失败！endlendl;

9、 return UNSUCCESS; else if(i!=TableSize & (*h).tablei.tag!=1) /哈希表有剩余空间时,进行插入操作 (*h).tablei.elem.key=x.key; /插入元素 (*h).tablei.tag=1; /tag标志置为1 (*h).currentSize+; /表存储量加1 cout录入成功！endlendl; return SUCCESS; else if(i=TableSize) /哈希表已满时,插入失败 cout哈希表已满,无法再插入x.key，操作失败！endlendl; return UNSUCCESS; Status

10、Delete(HashTable *h, Elemtype x, int p) /删除元素操作 int i=SearchHash(*h, x, p); /先调用查找操作 if(i=0) /查找成功,元素存在时,进行删除操作 (*h).table-i.elem.key=NULL; /单元值设为NULL (*h).table-i.tag=-1; /tag标志置为-1 (*h).currentSize-; /表存储量减1 cout删除成功！endl; return SUCCESS; else cout删除失败！endl; return UNSUCCESS; Status Print(HashTabl

11、e h) /打印表操作 coutendl哈希表序数 存储情况 存储元素endl; for(int i=0;iTableSize;i+) coutsetw(4)isetw(10)h.tablei.tagsetw(10)h.tablei.elem.keyendl; coutendl表中非空元素个数：h.currentSizeendlendl; return SUCCESS; Status Clear(HashTable *h) /置空表操作 for(int i=0;iTableSize;i+) (*h).tablei.tag=0; (*h).tablei.elem.key=NULL; (*h).c

12、urrentSize=NULL; cout哈希表已全部置空！endl; return SUCCESS; Hash.cpp文件int main( ) coutendl* HashTable Test File*endlendl; HashTable h; Initiate(&h); int prime; coutprime; char choice; while(1) coutendl; cout按 a 输出哈希表endl; cout按 b 查找指定元素在表中的位置endl; cout按 c 录入元素endl; cout按 d 删除元素endl; cout按 e 清空哈希表endl; cout按

13、 其他键 退出endlendlchoice; coutendl; switch(choice) casea: Print(h); break; caseb: couta.key; SearchHash(h,a,prime); break; casec: coutn; Elemtype *pi=0; pi=(Elemtype*)malloc(n*sizeof(Elemtype); cout请依次输入n个元素的值：endl; for(i=0;ipii.key; Insert(&h,pii,prime); break; cased: coutc.key; Delete(&h,c,prime); br

14、eak; casee: Clear(&h); break; default: return 0; 六运行结果： 程序运行，先按要求输入一小于20的质数作为除留余数法的除数因子。现取7。 显示主面板，选择录入数据。 先输入本次需要录入数据的个数，现取5。再依次录入数据，现输入326,547,233,145,985。 选择输出哈希表，并显示当前表中存储元素个数。默认未存储的单元“存储元素”为0，可以从“存储情况”一栏判断存储元素为“0”还是为“空”。 选择查找指定元素在表中的位置。输入已存在的元素“233”与不存在的元素“14”，显示如下： 再次选择录入数据。分别输入已存在的元素“233”与不存在

15、的元素“14”，显示如下： 选择删除数据。分别删除已存在的元素“985”与不存在的元素“211”，显示如下： 再次选择输出哈希表。经过上述操作后，哈希表现存储状态如下：其中新增元素14存储在哈希表第0位，删除元素985原所在的第6位“存储情况”标志显示为-1。 七小结：哈希表作为一种存储与查找的优化方式，通过把关键码值映射到数表中一个位置来访问数据，以加快查找速度。在日常生活中，哈希函数的应用也是随处可见。当今十分流行的P2P数据传输技术中一系列的压缩、打包以及积分标准都应用到了hash算法设置。可见利用哈希函数用途之广。本次程序设计中利用“除留余数法”构造哈希函数，并用“开放定址法”中的“线性探测再散列”方式处理冲突，选取较为简单的整型数字作为存储数据。通过此次实验，我对哈希表抽象数据类型的定义以及构造方法有了初步的认识和了解，也为今后编写更复杂的应用程序提供了新的思想方法与实现基础。