1、動(dòng)態(tài)查找表實(shí)驗(yàn)報(bào)告1、實(shí)驗(yàn)概要實(shí)驗(yàn)項(xiàng)目名稱：抽象數(shù)據(jù)類型的實(shí)現(xiàn)實(shí)驗(yàn)項(xiàng)目性質(zhì)：設(shè)計(jì)性實(shí)驗(yàn)所屬課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)計(jì)劃學(xué)時(shí)：62、實(shí)驗(yàn)?zāi)康膶?duì)某個(gè)具體的抽象數(shù)據(jù)類型，運(yùn)用課程所學(xué)的知識(shí)和方法，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上實(shí)現(xiàn)該抽象數(shù)據(jù)類型的全部基本操作。通過本設(shè)計(jì)性實(shí)驗(yàn)，檢驗(yàn)所學(xué)知識(shí)和能力，發(fā)現(xiàn)學(xué)習(xí)中存在的問題。進(jìn)而達(dá)到熟練地運(yùn)用本課程中的基礎(chǔ)知識(shí)及技術(shù)的目的。實(shí)驗(yàn)要求如下：1.參加實(shí)驗(yàn)的學(xué)生應(yīng)首先了解設(shè)計(jì)的任務(wù)，然后根據(jù)自己的基礎(chǔ)和能力從中選擇一題。一般來說，選擇題目應(yīng)以在規(guī)定的時(shí)間內(nèi)能完成，并能得到應(yīng)有的鍛煉為原則。若學(xué)生對(duì)教材以外的相關(guān)題目較感興趣，希望選作實(shí)驗(yàn)的題目時(shí)，應(yīng)征得指導(dǎo)教師的

2、認(rèn)可，并寫出明確的抽象數(shù)據(jù)類型定義及說明。2.實(shí)驗(yàn)前要作好充分準(zhǔn)備，包括：理解實(shí)驗(yàn)要求，掌握輔助工具的使用，了解該抽象數(shù)據(jù)類型的定義及意義，以及其基本操作的算法并設(shè)計(jì)合理的存儲(chǔ)結(jié)構(gòu)。3.實(shí)驗(yàn)時(shí)嚴(yán)肅認(rèn)真，要嚴(yán)格按照要求獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更改。注意觀察并記錄各種錯(cuò)誤現(xiàn)象，糾正錯(cuò)誤，使程序滿足預(yù)定的要求，實(shí)驗(yàn)記錄應(yīng)作為實(shí)驗(yàn)報(bào)告的一部分。4.實(shí)驗(yàn)后要及時(shí)總結(jié)，寫出實(shí)驗(yàn)報(bào)告，并附所打印的問題解答、程序清單，所輸入的數(shù)據(jù)及相應(yīng)的運(yùn)行結(jié)果。所用軟件環(huán)境或工具：DEV-C+5可視化編程環(huán)境3.動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型ADTDynamicSearchTable數(shù)據(jù)象D:D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)

3、數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌:InitDSTable(&DT);操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。DestroyDSTable(&DT);初始條件：動(dòng)態(tài)查找表DT存在；操作結(jié)果：銷毀動(dòng)態(tài)查找表DT。SearchDSTable(DT,key);初始條件：動(dòng)態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空二InsertDSTable(&DT,e);初始條件：動(dòng)態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；操作結(jié)

4、果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。DeleteDSTable(&T,key);初始條件：動(dòng)態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。TraverseDSTable(DT,Visit();初始條件：動(dòng)態(tài)查找表DT存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果：按某種次序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗,則操作失敗。ADTDynamicSearchTable二 .動(dòng)態(tài)查找表的特點(diǎn)二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)是，樹的結(jié)構(gòu)通常不是一資生成的

5、，面是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)三 .算法設(shè)計(jì)#include#include#include#include#includetypedefstructElemTypeintkey;ElemType;typedefstructbitnode/二叉樹的二叉鏈表存儲(chǔ)表示ElemTypedata;structbitnode*lchild,*rchild;左右孩子指針intlength;bitnode,*bitree;bitreeSearch(bitreeT,E

6、lemTypee,bitreef,bitree&p)/在二叉排序樹中查找數(shù)據(jù)if(!T)p=f;returnNULL;/查找不成功elseif(T-data.key=e.key)(p=T;returnT;)/查找成功elseif(T-data.keye.key)returnSearch(T-lchild,e,T,p);elsereturnSearch(T-rchild,e,T,p);/在二叉排序樹中查找數(shù)據(jù)voidInsert(bitree&T,ElemTypee)在二叉排序樹中插入數(shù)據(jù)(bitreep,s;if(!Search(T,e,NULL,p)查找不成功(s=(bitr

7、ee)malloc(sizeof(bitnode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/被插入結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)elseif(e.keydata.key)elsep-rchild=s;/被插結(jié)點(diǎn)*s為右孩子return;)elsereturn;)voidInit(bitree&T)/構(gòu)造一個(gè)動(dòng)態(tài)查找表Tintx;inti;intn;ElemTypee;printf(請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：);scanf(%d,&x);for(i=1;ilchild)DestoryTree(T-lchild);if(T-rchild)DestoryTr

8、ee(T-rchild);free(T);T=NULL;)voidDelete(bitree&p)/從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹bitreeq,s;if(!p-rchild)/右子樹空，只需重接它的左子樹q=p;p=p-lchild;free(q);q=NULL;)elseif(!p-lchild)/左子樹空，只需重接它的右子樹(q=p；p=p-rchild;free(q);q=NULL;)else/左右子樹均不空q=p;s=p-lchild;while(s-rchild)/向右走到盡頭q=s;s=s-rchild;)p-data=s-data;/將被刪結(jié)點(diǎn)的前驅(qū)s的

9、內(nèi)容直接替代該結(jié)點(diǎn)的內(nèi)容if(q!=p)若被刪除結(jié)點(diǎn)的左子樹的右子樹不為空q-rchild=s-lchild;/重接*q的右子樹elseq-lchild=s-lchild;重接*q的左子樹free(s);s=NULL;)/刪除結(jié)點(diǎn)voidDeletebit(bitree&T,intn)/刪除二叉排序樹中的數(shù)據(jù)(if(!T)return;不存在關(guān)鍵字等于n的數(shù)據(jù)元素elseif(T-data.key=n)return(Delete(T);/找到關(guān)鍵字等于n的數(shù)據(jù)元素并刪除它elseif(T-data.keyn)Deletebit(T-lchild,n);/繼續(xù)在左子樹中刪除elseDel

10、etebit(T-rchild,n);繼續(xù)在右子樹中刪除return;)voidXianxu(bitreeT)/先序遍歷(if(T!=NULL)(printf(%dt,T-data.key);Xianxu(T-lchild);Xianxu(T-rchild);voidZhongxu(bitreeT)/中序遍歷(if(T!=NULL)(Zhongxu(T-lchild);printf(%dt,T-data.key);Zhongxu(T-rchild);voidHouxu(bitreeT)/后序遍歷(if(T!=NULL)(Houxu(T-lchild);Houxu(T-rchild);print

11、f(%dt,T-data.key);intmain()bitreeT=NULL,p;ElemTypee;intn;inth;charc;doprintf(*n);printf(*printf(*動(dòng)態(tài)查找表*n);*n);printf(*1.建立二叉排序樹*n)printf(*2.二叉排序樹查找元素*n)printf(*3.二叉排序樹插入元素*n)printf(*4.二叉排序樹刪除元素*n)printf(*5.遍歷二叉排序樹*n)printf(*6.銷毀二叉排序樹*n)printf(*7.退出*n)printf(*n);0討*”*printf（請(qǐng)輸入你的選擇：n）;scanf(%d,&h

12、);switch(h)case 1:Init(T);break;case 2:chara;printf（請(qǐng)輸入要查找的數(shù)據(jù)：n）;scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)printf（數(shù)據(jù)已經(jīng)存在!n）;elseprintf(數(shù)據(jù)不存在!n);)break;case 3:printf(請(qǐng)輸入要插入的數(shù)據(jù):n);scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)printf(已經(jīng)存在!n);elseInsert(T,e);printf(成功插入!n);)break;case 4:printf(請(qǐng)輸入要?jiǎng)h

13、除的數(shù)據(jù)：n);scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)(Deletebit(T,n);printf(已經(jīng)成功刪除!n);elseprintf(數(shù)據(jù)不存在!n);break;case 5:intz;doprintf(*n);printf(*遍歷二叉排序樹*n);printf(*1.先序遍歷二叉排序樹*n);printf(*2.中序遍歷二叉排序樹*n);printf(*3.后序遍歷二叉排序樹*n);printf(*4.退出*n);printf(*n);printf(請(qǐng)輸入你的選擇：n);scanf(%d,&z);switch(z)(ca

14、se 1:printf(”*n);printf(”*n);printf(先序遍歷二叉排序樹:);Xianxu(T);printf(n);break;case 2:printf(中序遍歷二叉排序樹：);Zhongxu(T);printf(n);break;case 3:printf(后序遍歷二叉排序樹:);Houxu(T);printf(n);break;case 4:printf(退出!返回上級(jí)菜單！n);break;default:printf(選擇錯(cuò)誤，重新開始!n);while(z!=4);break;case 6:printf(確定是否要銷毀二叉排序樹?(y/n)n);scanf(n%

15、c,&c);getch();if(c=y)Destory(T);printf(所選數(shù)據(jù)已成功銷毀!n);getch();T=NULL;elseprintf(所選數(shù)據(jù)銷毀失敗!n);break;case 7:printf(退出！n);break;default:printf(選擇錯(cuò)誤，重新開始!n);請(qǐng)輸入你的選擇:1.建立二叉排序樹輸入十個(gè)數(shù)據(jù)：10,15,26,96,82,37,46,50,61,03,99while(h!=7);四.調(diào)試主頁(yè)面L-L-r1 1:入除 Eg：一表自插刪常-1-14 4方！1414. .X X了廣J J T TJrzJrz查叉 Ito：叉叉一芯-二一一動(dòng)

16、立叉叉叉歷毀出建二二二遍銷退123456712345672.查找元素：26存在則輸出請(qǐng)輸入你的選擇：3 3輸入要查找的數(shù)據(jù):2626數(shù)據(jù)己經(jīng)存在！3.插入元素:請(qǐng)輸入你的選擇：營(yíng)輸入要插入的數(shù)據(jù):皂flnrl*9056627601391129834560:9056627601391129834560:一*A-A-婁居居后后居后隹話后嘲e e數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)筌“點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)點(diǎn)2 2烈士口士口-HU士口士口士口土口士口土口第粉個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)0案12m412m4，s-s-啟- -.7.00-91.7.00-91100100成功插入，請(qǐng)輸入你的選擇：卷輸入要?jiǎng)h除的數(shù)據(jù)二數(shù)據(jù)不存在？5.遍歷：跳入二

17、級(jí)子菜單，里邊分別有三種遍歷方式可供選擇，分別為先序，中序，后序請(qǐng)輸入你的選擇:5 5請(qǐng)輸入你的選擇:6.在子菜單中選擇4退出則返回到上級(jí)菜單，即主頁(yè)面7銷毀二叉樹：先詢問是否確認(rèn)要銷毀，輸入y則銷毀，輸入n則銷毀失敗請(qǐng)輸入你的選擇：確定是否要銷毀二叉排序樹?Cy/nCy/n）地寨Eg立射.說明:(1)輸入十個(gè)數(shù)據(jù)：10,15,26,96,82,37,46,50,61,03,994.刪除元素：56（不存在）99（存在）序排靈身叉叉二二二二歷歷歷歷遍遍遍遍先中后退12341234(2)查找26,26存在則輸出(3)插入100(4)刪除56和99,56不存在則輸出“該數(shù)據(jù)不存在”，99存在則輸出“

18、成功刪除”(5)遍歷：跳入二級(jí)子菜單，里邊分別有三種遍歷方式可供選擇分別是先序：15,3,13,26,96,82,37,46,50,61,100中序：3,13,15,26,37,46,50,100,61,82,96,后序：13,3,100,61,50,46,37,82,96,26,15,退出后則返回到上級(jí)菜單(6)銷毀二叉樹：先詢問是否確認(rèn)要銷毀，輸入Y/y則銷毀，輸入N/n則銷毀失敗五.實(shí)驗(yàn)總結(jié)這次實(shí)驗(yàn)難度不是很大，因?yàn)楹芏嗨惴〞旧嫌?，而且我在圖書館里也找了幾本數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)的書，參考了很多，而且我選擇了最簡(jiǎn)單的二叉樹的存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)。這次實(shí)驗(yàn)使我認(rèn)識(shí)到存儲(chǔ)結(jié)構(gòu)和算法實(shí)現(xiàn)之間的關(guān)連。存儲(chǔ)結(jié)構(gòu)決定算法的實(shí)現(xiàn)。不同的存儲(chǔ)結(jié)構(gòu)，在算法的實(shí)現(xiàn)方面有很大差別。例如你選擇B樹或鍵樹的話相對(duì)于我來說就比較困難，