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

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ù)類型的全部基本操作。通過(guò)本設(shè)計(jì)性實(shí)驗(yàn)，檢驗(yàn)所學(xué)知識(shí)和能力，發(fā)現(xiàn)學(xué)習(xí)中存在的問(wèn)題。進(jìn)而達(dá)到熟練地運(yùn)用本課程中的基礎(chǔ)知識(shí)及技術(shù)的目的。實(shí)驗(yàn)要求如下：1參加實(shí)驗(yàn)的學(xué)生應(yīng)首先了解設(shè)計(jì)的任務(wù)，然后根據(jù)自己的基礎(chǔ)和能力從中選擇一題。一般來(lái)說(shuō)，選擇題目應(yīng)以在規(guī)定的時(shí)間內(nèi)能完成，并能得到應(yīng)有的鍛煉為原則。若學(xué)生對(duì)教材以外的相關(guān)題目較感興趣，希望選作實(shí)驗(yàn)的題目時(shí)，應(yīng)征

2、得指導(dǎo)教師的認(rèn)可，并寫出明確的抽象數(shù)據(jù)類型定義及說(shuō)明。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)告，并附所打印的問(wèn)題解答、程序清單，所輸入的.數(shù)據(jù)及相應(yīng)的運(yùn)行結(jié)果。所用軟件環(huán)境或工具：DEV-C+5可視化編程環(huán)境.3. 動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型ADT DynamicSearchTable數(shù)據(jù)對(duì)象 D ： D

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

4、條件：動(dòng)態(tài)查找表DT 存在， e 為待插入的數(shù)據(jù)元素；操作結(jié)果：若DT 中不存在其關(guān)鍵字等于e.key 的數(shù)據(jù)元素，則插入e 到 DT。DeleteDST able(&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() 失敗，則操作失敗。 ADT DynamicSearch

5、Table二. 動(dòng)態(tài)查找表的特點(diǎn)二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表，其特點(diǎn)是， 樹(shù)的結(jié)構(gòu)通常不是一資生成的，面是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。三. 算法設(shè)計(jì)#include.#include#include#include #include typedef struct ElemTypeint key;ElemType;typedef struct bitnodeElemType data;/ 二叉樹(shù)的二叉鏈表存儲(chǔ)表示struct bitnode *lchild,*

6、rchild;int length;bitnode,*bitree;/ 左右孩子指針bitree Search(bitree T,ElemType e,bitree f,bitree &p)/在二叉排序樹(shù)中查找數(shù)據(jù)if(!T)p=f;return NULL;./ 查找不成功else if(T-data.key=e.key)p=T;return T;/ 查找成功else if(T-data.keye.key)return Search(T-lchild,e,T,p);elsereturn Search(T-rchild,e,T,p);/ 在二叉排序樹(shù)中查找數(shù)據(jù)voidInsert(bitree

7、&T,ElemType e)/ 在二叉排序樹(shù)中插入數(shù)據(jù)bitree p,s;if (!Search(T,e,NULL,p)/查找不成功s=(bitree)malloc(sizeof(bitnode);s-data=e;s-lchild=s-rchild=NULL;if (!p) T=s;/ 被插入結(jié)點(diǎn) *s 為新的根結(jié)點(diǎn)else if (e.keydata.key).p-lchild=s;/ 被插結(jié)點(diǎn) *s 為左孩子elsep-rchild=s;/ 被插結(jié)點(diǎn) *s 為右孩子return ;else return ;void Init(bitree &T)/構(gòu)造一個(gè)動(dòng)態(tài)查找表T int x; i

8、nt i; int n; ElemType e;printf( 請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù) : );scanf(%d,&x);for(i=1;ilchild)DestoryTree(T-lchild);if(T-rchild)DestoryTree(T-rchild);free(T);T=NULL;void Delete(bitree &p)/從二叉排序樹(shù)中刪除結(jié)點(diǎn)p ，并重接它的左或右子樹(shù)bitree q,s;if(!p-rchild)/ 右子樹(shù)空，只需重接它的左子樹(shù)q=p;.p=p-lchild;free(q);q=NULL;else if(!p-lchild)/ 左子樹(shù)空，只需重接它的右子樹(shù)q=p;

9、p=p-rchild;free(q);q=NULL;else/ 左右子樹(shù)均不空q=p;s=p-lchild;while(s-rchild)/向右走到盡頭q=s;s=s-rchild;p-data=s-data;/將被刪結(jié)點(diǎn)的前驅(qū)s 的內(nèi)容直接替代該結(jié)點(diǎn)的內(nèi)容if(q!=p)/若被刪除結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)不為空.q-rchild=s-lchild;/ 重接 *q 的右子樹(shù)elseq-lchild=s-lchild;/ 重接 *q 的左子樹(shù)free(s);s=NULL; / 刪除結(jié)點(diǎn)void Deletebit(bitree &T,int n)/刪除二叉排序樹(shù)中的數(shù)據(jù)if(!T)return ;

10、/不存在關(guān)鍵字等于n 的數(shù)據(jù)元素elseif(T-data.key=n)return(Delete(T); /找到關(guān)鍵字等于n 的數(shù)據(jù)元素并刪除它else if(T-data.keyn)Deletebit(T-lchild,n);/ 繼續(xù)在左子樹(shù)中刪除elseDeletebit(T-rchild,n);/ 繼續(xù)在右子樹(shù)中刪除return;.void Xianxu(bitree T) /先序遍歷if (T!=NULL)printf(%dt,T-data.key);Xianxu (T-lchild);Xianxu (T-rchild);void Zhongxu(bitree T)/中序遍歷if(T

11、!=NULL)Zhongxu (T-lchild);printf(%dt, T-data.key);Zhongxu (T-rchild);.void Houxu(bitree T)/后序遍歷if(T!=NULL)Houxu (T-lchild);Houxu (T-rchild);printf(%dt, T-data.key);int main() bitree T=NULL,p; ElemType e;int n;int h;char c;doprintf(*n);printf(*.*n);printf(*動(dòng)態(tài)查找表*n);printf(*1.建立二叉排序樹(shù)*n);printf(*2.二叉排序

12、樹(shù)查找元素*n);printf(*3.二叉排序樹(shù)插入元素*n);printf(*4.二叉排序樹(shù)刪除元素*n);printf(*5.遍歷二叉排序樹(shù)*n);printf(*6.銷毀二叉排序樹(shù)*n);printf(*7.退出*n);printf(*n);printf(*n);printf( 請(qǐng)輸入你的選擇 : n);scanf(%d,&h);.switch(h)case 1:Init(T);break;case 2:char a;printf( 請(qǐng)輸入要查找的數(shù)據(jù) :n);scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)printf( 數(shù)據(jù)已經(jīng)存在 !n);els

13、e printf( 數(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除的數(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:int z

14、;do.printf(*n);printf(*n);printf(*遍 歷二叉排序樹(shù)*n);printf(*1.先序遍歷二叉排序樹(shù)*n);printf(*2.中序遍歷二叉排序樹(shù)*n);printf(*3.后序遍歷二叉排序樹(shù)*n);printf(*4.退出*n);printf(*n);printf(*n);printf( 請(qǐng)輸入你的選擇 : n);scanf(%d,&z);switch(z)case 1:printf( 先序遍歷二叉排序樹(shù) : );Xianxu(T);.printf(n);break;case 2:printf( 中序遍歷二叉排序樹(shù) : );Zhongxu(T);printf(n

15、);break;case 3:printf( 后序遍歷二叉排序樹(shù) : );Houxu(T);printf(n);break;case 4:printf( 退出 !返回上級(jí)菜單！ n);break;default:printf( 選擇錯(cuò)誤，重新開(kāi)始 !n); while(z!=4);break;case 6:.printf( 確定是否要銷毀二叉排序樹(shù)?(y/n)n);scanf(n%c,&c);getch();if(c=y)Destory(T);printf( 所選數(shù)據(jù)已成功銷毀 !n);getch();T = NULL;elseprintf( 所選數(shù)據(jù)銷毀失敗 !n);break;case 7

16、:printf( 退出！ n);break;default:printf( 選擇錯(cuò)誤，重新開(kāi)始 !n); while(h!=7);.四 . 調(diào)試主頁(yè)面1. 建立二叉排序樹(shù)輸入十個(gè)數(shù)據(jù)：10,15,26,96,82,37,46,50,61,03,992. 查找元素 : 26 存在則輸出.3. 插入元素：4. 刪除元素： 56 （不存在）99 （存在）.5. 遍歷：跳入二級(jí)子菜單，里邊分別有三種遍歷方式可供選擇，分別為先序，中序，后序.6. 在子菜單中選擇 4 退出則返回到上級(jí)菜單，即主頁(yè)面7 銷毀二叉樹(shù)：先詢問(wèn)是否確認(rèn)要銷毀，輸入y 則銷毀，輸入n 則銷毀失敗說(shuō)明：（ 1 ）輸入十個(gè)數(shù)據(jù)： 10

17、,15,26,96,82,37,46,50,61,03,99.（ 2 ）查找 26 ，26 存在則輸出（ 3 ）插入 100（ 4 ）刪除 56 和 99,56 不存在則輸出“該數(shù)據(jù)不存在” ， 99 存在則輸出“成功刪除”（ 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 ）銷毀二叉樹(shù)：先詢問(wèn)是否確認(rèn)要銷毀，輸入Y/y則銷毀，輸入N/n則銷毀失敗五 . 實(shí)驗(yàn)總結(jié)這次實(shí)驗(yàn)難度不是很大，因?yàn)楹芏嗨惴〞旧嫌校椅以趫D書館里也找了幾本數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)的書，參考了很多， 而且我選擇了最簡(jiǎn)單的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)來(lái)實(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 樹(shù)或鍵樹(shù)的話相對(duì)于我來(lái)說(shuō)就比較困難，因?yàn)檎莆盏牟皇呛芎?。很開(kāi)