2014广工数据结构实验报告哈希表

1、数据结构设计性实验报告课程名称数据结构实验题目名称哈希表学生学院_ 计算机学院专业班级学 号学生姓名指导教师2015 年7 月2 日1. 题目采用哈希表为存储结构，实现抽象数据类型 HashTable 。ADT HAS数据对象 D：D 是具有相同特性的数据元素的集合。数据关系 R ：根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个连续的有 限地址集上，并以关键字在地址集中的“像” 作为记录在表中的存储位置， 这种表称为哈希 表。这一映像过程称为造表或散列，所得存储位置称哈希地址或散列地址。基本操作：InitHash(&H)操作结果：初始化哈希表H。DestoyHash(&H)初始条件：

2、哈希表 H 已存在。操作结果：销毁哈希表H。CreateHash(&H)初始条件：哈希表 H 已存在。 操作结果：构造哈希表H。SearchHash(H)初始条件：哈希表已存在。 操作结果：查找哈希表 H 中元素。InsertHash(&H)初始条件：哈希表 H 已存在。 操作结果：插入元素到哈希表DeleteHash( &H, key, & e) 初始条件：哈希表已存在且非空。操作结果：删除H的第i个元素，并用e返回其值，H的长度减1。 ADT List3. 算法设计#include #include #include #include #include#define random(x) (

3、rand()%x)#define OK 1#define SUCCESS 1#define UNSUCCESS 0#define DUPLICAPE -1#define OVERFLOW 0typedef int KeyType;typedef int Status;typedef struct KeyType key;int tag;RecordrdType, RcdType;typedef struct RcdType *rcd;int size;int count;HashTable;int InitHash(HashTable *H, int size) / 初始化哈希表 int i;

4、H-rcd=(RcdType*)malloc(size*sizeof(RcdType); if(NULL=H -rcd)return OVERFLOW;for(i=0;ircdi.tag=0;H-size=size;H-count=0;return OK;int DestoyHash(HashTable *H)/ 销毁哈希表free(H -rcd);H-rcd=NULL;H-count=0;H-size=0;return OK;int SearchHash(HashTable H, KeyType key , int &p,int &c )/查找哈希表c=0;p=key%H.size;/ 求得

5、哈希地址-1=H.rcdp.tag)while(H.rcdp.tag!=0&(H.rcdp.key!=key| p=(p+1)%H.size;c+;/ 求得下一探测地址 if(H.rcdp.key=key)return SUCCESS; else return UNSUCCESS;int InsertHash(HashTable *H, RcdType e)/ 哈希表的插入int c=0,j;if(SUCCESS=SearchHash(*H,e.key,j,c)return -1;else H -rcdj=e;H -rcdj.tag=1;+H -count;return c;int Delet

6、eHash(HashTable *H,KeyType key,RcdType e) /哈希表的删除 int j,c;if(UNSUCCESS=SearchHash(*H,key,j,c)return UNSUCCESS;else e=H-rcdj;H-rcdj.tag= -1;H-count -;return SUCCESS;void display(HashTable *H)printf(n 哈希表数据 :);for(int i=1;icount;i+)printf(%d ,H -rcdi);printf(n);4测试int main()int i,j,select,x1,x2,x3,x4,g,n,k,b,f;RcdType e;KeyType key;srand(time(0); / 初始化随机种子HashTable H;InitHash(&H,9);for(i=1;i0 & select sclcEt 4 潘鑫的除xniput; ynix select:頤舉騒羲*能定输人4否则输入05S芙散于为;1Frias any kov to cDntxnu96. 实验总结和体会本次实验令我对哈希表的含义及用法有更多的了解， 还对编程能力的提高有一定的帮助， 学会自己找资料