2023年動(dòng)態(tài)查找表實(shí)驗(yàn)報(bào)告

動(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),檢查所學(xué)知識(shí)和能力,發(fā)現(xiàn)學(xué)習(xí)中存在的問題。進(jìn)而達(dá)成純熟地運(yùn)用本課程中的基礎(chǔ)知識(shí)及技術(shù)的目的。實(shí)驗(yàn)規(guī)定如下：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)教師的認(rèn)可,并寫出明確的抽象數(shù)據(jù)類型定義及說明。２.實(shí)驗(yàn)前要作好充足準(zhǔn)備,涉及：理解實(shí)驗(yàn)規(guī)定,掌握輔助工具的使用,了解該抽象數(shù)據(jù)類型的定義及意義，以及其基本操作的算法并設(shè)計(jì)合理的存儲(chǔ)結(jié)構(gòu)。3.實(shí)驗(yàn)時(shí)嚴(yán)厲認(rèn)真，要嚴(yán)格按照規(guī)定獨(dú)立進(jìn)行設(shè)計(jì),不能隨意更改。注意觀測(cè)并記錄各種錯(cuò)誤現(xiàn)象，糾正錯(cuò)誤,使程序滿足預(yù)定的規(guī)定,實(shí)驗(yàn)記錄應(yīng)作為實(shí)驗(yàn)報(bào)告的一部分。４.實(shí)驗(yàn)后要及時(shí)總結(jié),寫出實(shí)驗(yàn)報(bào)告，并附所打印的問題解答、程序清單,所輸入的數(shù)據(jù)及相應(yīng)的運(yùn)營結(jié)果。所用軟件環(huán)境或工具:DＥV-C++5可視化編程環(huán)境.3.動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型?ADTDｙnａmicSｅａrchＴabｌe{

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素具有類型相同的關(guān)鍵字,可唯一?標(biāo)記數(shù)據(jù)元素。

數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合。

基本操作P:

InｉｔDSTaｂle(&DT);?操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DＴ。

ＤesｔroyDSTable(＆DT);?初始條件：動(dòng)態(tài)查找表DＴ存在；?操作結(jié)果：銷毀動(dòng)態(tài)查找表ＤT。

SeaｒchDSTaｂle（DT，key）;?初始條件:動(dòng)態(tài)查找表DＴ存在,key為和關(guān)鍵字類型相同的給定值；

操作結(jié)果：若ＤT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否?則為“空”。

ＩｎｓeｒtDSTaｂle(&DＴ,e);

初始條件:動(dòng)態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；

操作結(jié)果：若DT中不存在其關(guān)鍵字等于e．kｅy的數(shù)據(jù)元素,則插入e到DＴ。?DeleｔeＤSＴaｂｌe（＆T，keｙ)；?初始條件:動(dòng)態(tài)查找表DT存在,kｅｙ為和關(guān)鍵字類型相同的給定值；?操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。

TraverｓeDSTable(DT,Visit（）);?初始條件：動(dòng)態(tài)查找表DＴ存在，Ｖisit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；

操作結(jié)果：按某種順序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)viｓｉt（）一次且至多一次。一旦visit()失敗，則?操作失敗。?}ＡDTDynamicＳearchTａbｌｅ動(dòng)態(tài)查找表的特點(diǎn)二叉排序樹是一種動(dòng)態(tài)樹表,其特點(diǎn)是,樹的結(jié)構(gòu)通常不是一資生成的,面是在查找過程中，當(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ì)#incluｄe<stdio．ｈ>#iｎclｕｄe<malｌoc.ｈ＞＃include＜coｎiｏ．h>#inclｕｄe<cｓｔｄlib>＃ｉnｃlude<iｏstream>typｅdｅｆｓｔｒuｃtElemType{ iｎtkey;}ElｅmType;tｙpeｄｅfｓｔｒuctbitnoｄe{//二叉樹的二叉鏈表存儲(chǔ)表達(dá)?ElｅｍTypeｄatａ;?ｓtructbiｔｎｏｄe＊lchｉlｄ,*rchiｌd；//左右孩子指針?iｎtｌｅｎｇth;}bitnode,*bｉtｒee；bitreeＳearch(bitreeT,ＥlｅｍTypｅｅ,bｉtreｅｆ,biｔｒee&p)//在二叉排序樹中查找數(shù)據(jù){ if(!Ｔ）?｛ ?ｐ＝f； ?retｕrnNULL；?}//查找不成功?elseif(Ｔ->ｄata.ｋｅy==ｅ.key） { p=T;reｔurnT; }//查找成功 eｌseif(T->ｄata．key＞e.keｙ） ?retｕrnSeaｒch(T->lchiｌd,e,T,p); else ｒｅturnSearch(Ｔ－>rchild,e，T，p）;}／／在二叉排序樹中查找數(shù)據(jù)ｖoidＩｎsert（bitrｅe(cuò)&T,EleｍTｙpee)/／在二叉排序樹中插入數(shù)據(jù){ ｂiｔｒeｅp,s;?iｆ(!Search(T,e,NUＬL,p))／／查找不成功 { ?s=（bitree）maｌloc(sizeof（bitnｏdｅ)）;? ｓ->dａｔa=e； s->lchiｌｄ=s->rchiｌd=ＮULL;??if(!p)T=s;/／被插入結(jié)點(diǎn)*s為新的根結(jié)點(diǎn) elseif(e.keｙ<p-＞data.key)ｐ－>ｌchiｌd=s;／/被插結(jié)點(diǎn)*s為左孩子 ?elｓep-＞rchild＝ｓ；/／被插結(jié)點(diǎn)*ｓ為右孩子??ｒeturn； } elsｅretuｒｎ;｝ｖoｉｄＩnit(bitreｅ＆Ｔ)//構(gòu)造一個(gè)動(dòng)態(tài)查找表T{intx;ｉnti;inｔn;EleｍTypee； ｐrintｆ（"請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù):"）；?ｓcaｎf("%d",&x);?for(i=1;ｉ<＝x;i++） {?prinｔｆ("第%d個(gè)結(jié)點(diǎn)數(shù)據(jù)值:",ｉ);?scaｎf（＂%d",&n); ｅ.kｅy＝n;?Iｎsert（T,e); }prｉntf(＂二叉排序樹已經(jīng)建立！\ｎ");}voidDeｓtｏry(ｂitｒeeT)//后序遍歷二叉樹,銷毀動(dòng)態(tài)查找表T｛?if（T) {if(Ｔ－>lcｈild) ＤｅstoｒyTree(T->lchild);ｉf(T-＞rcｈild) DestｏryTree（T->rchｉld); frｅe(cuò)(T);??Ｔ=NULL;?}}voidDｅlete(bｉtreｅ&p）//從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹｛?bitrｅe(cuò)ｑ，ｓ;?if(！p-＞ｒｃhｉlｄ)／／右子樹空,只需重接它的左子樹?{ q=p;??p＝p->lｃhild;? free（q); ｑ=NULＬ；?}?elseif(！p－＞lchiｌｄ)/／左子樹空，只需重接它的右子樹?｛??q＝p;??ｐ＝p-＞rchilｄ;??ｆree(q);? ｑ=NＵLＬ； }?else{/／左右子樹均不空 ?q=ｐ； s=p->ｌcｈilｄ; whilｅ(s->rcｈiｌｄ)／/向右走到盡頭??｛ ??ｑ＝s;?? s=ｓ->ｒchｉld; ?}? p-＞data=s－>ｄaｔa；/／將被刪結(jié)點(diǎn)的前驅(qū)s的內(nèi)容直接替代該結(jié)點(diǎn)的內(nèi)容 ｉf(ｑ!=p)//若被刪除結(jié)點(diǎn)的左子樹的右子樹不為空 ??q->ｒchild＝s-＞ｌchild;/／重接*q的右子樹? else ? ｑ-＞lchild=s->lchild;／/重接*q的左子樹? fｒee(s）; ?s＝NULL; }}//刪除結(jié)點(diǎn)ｖoiｄDelｅｔebit(bｉｔrｅｅ&T，intn)//刪除二叉排序樹中的數(shù)據(jù){?iｆ(!Ｔ) ｒeturn;//不存在關(guān)鍵字等于n的數(shù)據(jù)元素 elsｅ{??if(T－>ｄａｔa．key＝=n) ?rｅtuｒｎ(Delete（T));／/找到關(guān)鍵字等于n的數(shù)據(jù)元素并刪除它??elsｅif(T->data.key＞n)? Ｄelｅtebit(T->ｌcｈiｌd,n);/／繼續(xù)在左子樹中刪除? else ? Dｅletebｉt（T－>rchild，n);//繼續(xù)在右子樹中刪除??reｔurｎ;?}｝voidXｉanxu（bitrｅｅT)//先序遍歷{ ｉf(T！=NＵＬL）?{?ｐｒiｎtf（"%d\t",T-＞ｄata.keｙ）; Xiaｎxu(T->lchｉlｄ); ?Xianxu(T-＞rｃhild）;?}}vｏｉｄZhｏngｘｕ(bｉtreeT)//中序遍歷｛ if(T!=NUＬL)?{ ?Zｈonｇxu(Ｔ->lｃhild)；?ｐｒintf("%d＼t"，T->datａ．key)； ?Ｚhongxu(T->ｒｃhiｌｄ）; }}voidHｏｕxu(ｂiｔｒｅe(cuò)T)/／后序遍歷{ if(T!=NULL)?{??Ｈouxu(T-＞lchild); Houｘｕ(T->rｃｈilｄ）;??prｉｎｔf("%d\ｔ"，T->dａt(yī)ａ．kｅy); }}intmaｉｎ()｛ bitｒeeT=NULL,ｐ; ＥleｍTyｐee; ｉｎtn; inｔh;?ｃｈａｒc;dｏ{ｐrintｆ(＂*＊*******＊******＊**＊＊＊****＊****＊******＊****＊****＊*＊＊**＊****\n");prｉntf（"*＊＼n＂);ｐｒintf(＂*動(dòng)態(tài)查找表*\ｎ")；pｒinｔf("＊1.建立二叉排序樹*＼n");ｐｒｉnｔｆ("*2.二叉排序樹查找元素*\n");ｐrintf("*3.二叉排序樹插入元素＊\n");ｐrｉntf（＂＊4.二叉排序樹刪除元素＊＼n")；prｉｎtf(＂*５．遍歷二叉排序樹＊\n＂);ｐrintf("＊6．銷毀二叉排序樹*\n")；pｒｉntf("*7.退出＊\n");priｎｔf(＂**＼n");priｎtｆ("**＊******＊＊****＊***＊*******＊***＊**＊***********＊*＊*＊**＊**＊＊＊＼ｎ＂)；??ｐrinｔf("請(qǐng)輸入你的選擇:＼n");? scanf("%ｄ",&h)； switch(h)? {? ｃase1:????Init(T）;???breａk; ??casｅ2:chara； ???prｉｎtf(＂請(qǐng)輸入要查找的數(shù)據(jù):\ｎ＂)；?? scanf("%ｄ",&ｎ);? ?e.kｅy＝n;????ｉｆ(Search（T,e，NULL,ｐ))? ??printf("數(shù)據(jù)已經(jīng)存在！\n＂); ? elｓe ?? {?prｉｎtf("數(shù)據(jù)不存在!\ｎ＂)； ? }?? ?break; case3:? ?ｐｒinｔf（"請(qǐng)輸入要插入的數(shù)據(jù):\n"); ? ?scａnf("%ｄ",＆ｎ);? e．key=n; ? if(Sｅarｃh（T,e,NＵLL,p)) ????ｐrintf（"已經(jīng)存在!＼n＂);??? eｌse ? {?? ? Inserｔ(T,e);? printf("成功插入！\n")；? ??} ? brｅak； caｓｅ4：??? printf（"請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):\n"）; ???scanｆ("％ｄ"，&n);? ?e.kｅy=n； ? iｆ(Search（T,e，NULＬ，p)) ? { ???Ｄeletebｉt(T,ｎ)；? ? ｐrｉntｆ("已經(jīng)成功刪除!\n"）；?? ?}? ?eｌseprintf("數(shù)據(jù)不存在!\n");? ?bｒeak;?case5:inｔz;do {ｐｒiｎtf(＂**＊*＊＊****＊＊*＊******＊**＊*＊*************＊*＊******＊***＊＊***＊****＊＊*＊**\ｎ＂);prinｔｆ("*＊\ｎ"）;priｎtｆ(＂*遍歷二叉排序樹＊\n");prinｔｆ("*１.先序遍歷二叉排序樹*\ｎ");prinｔf（＂*2.中序遍歷二叉排序樹*\n")；prｉｎtf("*３.后序遍歷二叉排序樹＊\n")；printｆ（"*４.退出＊＼n");pｒintf（"**\n");pｒintf(＂*******＊***＊***＊*＊*＊＊*＊**********＊＊*****＊＊＊＊******＊*****＊****＊＊***＊*\n");printf("請(qǐng)輸入你的選擇:\n");sｃanf("%ｄ＂，＆z)；ｓwitch(z)??{caｓｅ1:? ?printf（＂先序遍歷二叉排序樹:"); ? ?Ｘianxu(Ｔ);?? ?pｒｉnｔｆ("\n")；? ?bｒｅak;?? ｃase２： ???priｎｔf("中序遍歷二叉排序樹：");??? Ｚhｏnｇxｕ(T）; pｒｉntf（"\ｎ＂);? ??bｒeａｋ;? case3: ??printｆ（"后序遍歷二叉排序樹:＂);?? ?Ｈoｕxｕ(T); ?? pｒintf("\n"); ??ｂreak;casｅ4:??? ｐrintf（"退出!返回上級(jí)菜單！\n")； ??break;?defauｌt：prｉｎtf(＂選擇錯(cuò)誤，重新開始!\n＂);}}whｉｌe(z!=4）；break;case6: ??pｒｉｎtf（＂擬定是否要銷毀二叉排序樹？（y／ｎ)\n");scanｆ("\ｎ％c",&c)；? ?getcｈ()；? ?ｉf(c==＇y＇) ??{ ? Dｅｓtｏry(T);? ? printf("所選數(shù)據(jù)已成功銷毀!\n")； getch（)；? ? T=NＵLL;｝ ?? elｓｅ? ??prｉｎtf("所選數(shù)據(jù)銷毀失??！\n＂）;? ??ｂrｅaｋ;cａｓe7:??? ｐｒiｎtｆ("退出?。躰");? ?? brｅak；??ｄeｆault：prｉntf(＂選擇錯(cuò)誤，重新開始!\ｎ"）；??? }}whｉle(h!=7);}調(diào)試主頁面建立二叉排序樹輸入十個(gè)數(shù)據(jù):1０，15,26,96,82,3７,４6，50,61，０3,99查找元素：26存在則輸出插入元素:刪除元素：56(不存在)９９(存在）遍歷:跳入二級(jí)子菜單，里邊分別有三種遍歷方式可供選擇，分別為先序,中序，后序6.在子菜單中選擇4退出則返回到上級(jí)菜單，即主頁面7銷毀二叉樹：先詢問是否確認(rèn)要銷毀,輸入y則銷