完整word版2014廣工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告哈希表

1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)性實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目名稱哈希表學(xué)生學(xué)院計(jì)算機(jī)學(xué)院專業(yè)班級(jí)學(xué)生姓名指導(dǎo)教師2015 年7 月2 日1. 題目采用哈希表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)抽象數(shù)據(jù)類型 HashTable 。ADT HAS數(shù)據(jù)對象 D：D 是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R :根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)連續(xù)的有 限地址集上，并以關(guān)鍵字在地址集中的“像” 作為記錄在表中的存儲(chǔ)位置， 這種表稱為哈希 表。這一映像過程稱為造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址?；静僮?InitHash(操作結(jié)果:DestoyHash(初始條件:操作結(jié)果:CreateHash(&H)初

2、始條件:操作結(jié)果:SearchHash(H)初始條件:操作結(jié)果:InsertHash(&H)初始條件:操作結(jié)果:&H) 初始化哈希表&H) 哈希表 H 已存在。 銷毀哈希表 H。H。哈希表 H 已存在。 構(gòu)造哈希表 H。哈希表已存在。 查找哈希表 H 中元素。哈希表 H 已存在。 插入元素到哈希表DeleteHash(初始條件：操作結(jié)果：&H, key, & e) 哈希表已存在且非空。 刪除H的第i個(gè)元素，并用e返回其值，H的長度減1。 ADT List3. 算法設(shè)計(jì)#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 哈希表數(shù)據(jù) :); 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); / 初始化隨機(jī)種子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( 輸入數(shù)字為 :); scanf(%d,&x1);if(x1=1)return DestoyHash(&H);else break;case 2: printf( 請輸入要查找的數(shù)據(jù)元素 : ); scanf(%d,&key); k=SearchHash(H,key,b,g);if(k=1)printf( 查找成功 n);p

9、rintf(%d在哈希表中的位置為：d,沖突次數(shù)為：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（請輸入要?jiǎng)h除的元素序號(hào)：”）;scan f(%d，&x4);if(DeleteHash(&H,key,e) printf(刪除成功 rr); else printf(錯(cuò)誤宙)；break; while (select。& select

10、 5);return OK;4.程序測試結(jié)果使用VC+編譯軟件，使用c語言表示哈希表的查找，插入，刪除，銷毀功能=-T J - .-產(chǎn)P tr-JT -_a- J=哈垂舌瓠摳雨？申 4V 14 ?K ai .;r1rrt 1 葡鉉哈童表 DrxInyHnshC rlcrt 7 與布農(nóng)的査描!irrtrrhH-nsh ;clcct 1 吟希寺#1荊 InsertJilishO ;cIcct 4 苗希需Ml曲除 lieIctcH-ashC linput Taur select = 2 I頁評S我的數(shù)踞元囂：V 畀1駕礬中的位置為：.沖2唱希表數(shù)里開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磧曙人豊?人仍兀素匕丄號(hào)?gA嚴(yán)龍2149142231 i9B 捋 Sr(iruhHflshT UMKTX： lllIrtfibO 哈齋義啊勵(lì)障ilr 1 rtrHAshO噲-務(wù)表藪捱詢 select I 加】4U：l 2Kfl 1 Kri：t 1 t 4input vuur adcc t = *1湄轍入要?jiǎng)h徐的亓T,卞號(hào)：IfUMKr:哈若喪駐邏:也? 1!1 4? 14 22 J1 Gcicct 1 W霞吐希塞恥“towMaakO sdidct a 畤爺遴的魯坎；EuoiphHjlUiO cdldct iinooithHanbOualact 1 唐爺袁的酈陳 delotitHaehC； inpt your DlQct ：-話芒蕊據(jù)汕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