完整word版2014广工数据结构实验报告哈希表

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

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

3、and()%x)#define OK 1#define SUCCESS 1#define UNSUCCESS 0#define DUPLICAPE -1#define OVERFLOW 0 typedef 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

4、 i;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、/ 求得哈希地址 while(H.rcdp.tag!=0&(H.rcdp.key!=key| -1=H.rcdp.tag) 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;in

6、t DeleteHash(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

7、,x1,x2,x3,x4,g,n,k,b,f;RcdType e;KeyType key;srand(time(0); / 初始化随机种子HashTable H;InitHash(&H,9);for(i=1;i=10;i+)e.tag=1;e.key=random(50);InsertHash(&H,e); printf(nn);do display(&H);printf(select 1printf(select 2printf(select 3printf(select 4销毁哈希表 DestoyHash()n); 哈希表的查找 哈希表的插入 哈希表的删除SearchHash()n);In

8、serchHash()n); deleteHash()n);printf(input your select: ); scanf(%d,&select);switch(select) case 1:printf( 销毁哈希表 ,确定输入 1，否则输入 0n);printf( 输入数字为 :); scanf(%d,&x1);if(x1=1)return DestoyHash(&H);else break;case 2: printf( 请输入要查找的数据元素 : ); scanf(%d,&key); k=SearchHash(H,key,b,g);if(k=1)printf( 查找成功 n);p

9、rintf(%d在哈希表中的位置为：d,冲突次数为：dn,key,b,g);else printf( 查找失败 n);break;case 3: printf(请输入要插入的元素：”)；scanf(%d,&e);if(InsertHash(&H,e)printf( 插入成功 n);else printf( 插入失败 n);break;case 4: printf（请输入要删除的元素序号：”）;scan f(%d，&x4);if(DeleteHash(&H,key,e) printf(删除成功 rr); else printf(错误宙)；break; while (select。& select

10、 5);return OK;4.程序测试结果使用VC+编译软件，使用c语言表示哈希表的查找，插入，删除，销毁功能=-T J - .-产P tr-JT -_a- J=哈垂舌瓠抠雨？申 4V 14 ?K ai .;r1rrt 1 葡铉哈童表 DrxInyHnshC rlcrt 7 与布农的査描!irrtrrhH-nsh ;clcct 1 吟希寺#1荊 InsertJilishO ;cIcct 4 苗希需Ml曲除 lieIctcH-ashC linput Taur select = 2 I頁评S我的數踞元囂：V 畀1驾礬中的位置为：.冲2唱希表数里開T 21 49 14 22 31ealact 1

11、蛰毀右希表 teotoyHaah?找 SDarchdDshC?I n音BPchH AC h de LetHahCJiLOQlact 3 eelqct 3 I select 4 【_ inputcelect - 3磧曙人豊?人仍兀素匕丄号?gA嚴龙2149142231 i9B 捋 Sr(iruhHflshT UMKTX： lllIrtfibO 哈斋義啊励障ilr 1 rtrHAshO哙-務表薮捱询 select I 加】4U：l 2Kfl 1 Kri：t 1 t 4input vuur adcc t = *1湄辙入要刪徐的亓T,卞号：IfUMKr:哈若喪駐逻:也? 1!1 4? 14 22 J1 Gcicct 1 W霞吐希塞恥“towMaakO sdidct a 畤爺遴的魯坎；EuoiphHjlUiO cdldct iinooithHanbOualact 1 唐爺袁的郦陈 delotitHaehC； inpt your DlQct ：-话芒蕊据汕21 AS 14 32 Jl :tleut L輻署蚩疸夷片Mio丹町心 r. n In At 7 右希左 mS 抽 RErtlNIaM) eelfl Ct 3菜羞由埼 A IntBFcJiHfttliOLrlrrt挙叢甬由焼 rirli:比HmM)xntijit your select:Fr口3