數(shù)據(jù)結(jié)構(gòu)樹的實(shí)現(xiàn)實(shí)驗(yàn)報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu)設(shè)計性實(shí)驗(yàn)報告 課程名稱_ _ 題目名稱 學(xué)生學(xué)院 專業(yè)班級 學(xué) 號 學(xué)生姓名 指導(dǎo)教師 2010 年 7 月 6 日 抽象數(shù)據(jù)類型：樹的實(shí)現(xiàn)1 需求分析 樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用，直觀來看，樹是以分支關(guān)系定義的內(nèi)部結(jié)構(gòu)。樹的結(jié)構(gòu)在客觀世界廣泛存在，如人類社會的族譜和各種社會組織機(jī)構(gòu)都可以用樹來形象表示。樹在計算機(jī)領(lǐng)域中也得廣泛應(yīng)用，如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)，又如在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)也是信息的重要組織形式之一。2 實(shí)驗(yàn)?zāi)康?對某個具體的抽象數(shù)據(jù)類型，運(yùn)用課程所學(xué)的知識和方法，設(shè)計合理的數(shù)據(jù)結(jié)構(gòu)，并在

2、此基礎(chǔ)上實(shí)現(xiàn)該抽象數(shù)據(jù)類型的全部基本操作。通過本設(shè)計性實(shí)驗(yàn)，檢驗(yàn)所學(xué)知識和能力，發(fā)現(xiàn)學(xué)習(xí)中存在的問題。 進(jìn)而達(dá)到熟練地運(yùn)用本課程中的基礎(chǔ)知識及技術(shù)的目的。3 實(shí)驗(yàn)環(huán)境 1、 硬件：PC機(jī) 2、 軟件：Microsoft Visual C+ 6.04 設(shè)計說明 本程序采用樹的二叉鏈表（孩子指針-兄弟指針-雙親指針）存儲表示，以下是樹的結(jié)構(gòu)定義和基本操作：ADT Tree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹； 若D僅含有一個數(shù)據(jù)元素，則R為空集，否則R=H，H是如下二元關(guān)系： (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)； (

3、2) 若D-rootNULL，則存在D-root的一個劃分D1,D2,D3, ,Dm(m0)，對于任意jk(1j,km)有DjDk=NULL,且對任意的i(1im)，唯一存在數(shù)據(jù)元素xiDi有H;(3) 對應(yīng)于D-root的劃分，H-,有唯一的一個劃分H1，H2,Hm(m0)，對任意jk(1j,km)有HjHk=NULL，且對任意i(1im),Hi是Di上的二元關(guān)系，(Di,Hi)是一棵符合本定義的樹，稱為根root的子樹。 基本操作P：InitTree(&T);操作結(jié)果：構(gòu)造空樹T。DestroyTree(&T);初始條件：樹T存在。操作結(jié)果：銷毀樹T。CreateTree(&T,defin

4、ition);初始條件：definition給出樹T的定義。操作結(jié)果：按definition構(gòu)造樹T。ClearTree(&T);初始條件：樹T存在。操作結(jié)果：將樹T清為空樹。TreeEmpty(T);初始條件：樹T存在。操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。TreeDepth(T);初始條件：樹T存在。操作結(jié)果：返回的深度。Root(T);初始條件：樹T存在。操作結(jié)果：返回T的根。Value(T,cur_e);初始條件：樹T存在，cur_e是T中某個結(jié)點(diǎn)。操作結(jié)果：返回cur_e的值。Assign(T,cur_e,value);初始條件：樹T存在，cur_e是T中某個結(jié)點(diǎn)

5、。操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。Parent(T,cur_e);初始條件：樹T存在，cur_e是T中某個結(jié)點(diǎn)。操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。LeftChild(T,cur_e);初始條件：樹T存在，cur_e是T中某個結(jié)點(diǎn)。操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。RightSibling(T,cur_e);初始條件：樹T存在，cur_e是T中某個結(jié)點(diǎn)。操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則返回“空”。InsertChild(&T,&p,I,c);初始條件：樹存在，指向中某個結(jié)點(diǎn)，1ip指

6、結(jié)點(diǎn)的度，非空樹與不相交。操作結(jié)果：插入c為中指結(jié)點(diǎn)的第棵子樹。DeleteChild(&T,&p,i);初始條件：樹T存在，p指向T中某個結(jié)點(diǎn)，1ip指結(jié)點(diǎn)的度。操作結(jié)果：刪除中所指結(jié)點(diǎn)的第棵子樹。TraverseTree(T,visit();初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。CSTree Search(CSTree T,TElemType cur_e);初始條件：樹T存在，cur_e可能是樹T中某一個結(jié)點(diǎn)的值。操作結(jié)果：在樹T中查找值為cur_e的結(jié)點(diǎn)，找到返回指

7、向這個結(jié)點(diǎn)的指針，否則返回空指針。這個函數(shù)的作用是為了幾個基本操作而服務(wù)的。void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType);初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按層次次序?qū)的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType);初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作函數(shù)：按先序次序（先根遍歷）對T的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。函數(shù)的功能實(shí)

8、現(xiàn)是遞歸實(shí)現(xiàn)的。void PostOrderTraverseTree(CSTree T,void (*visit)(TElemType);初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按后根遍歷對T的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。函數(shù)的功能實(shí)現(xiàn)是遞歸實(shí)現(xiàn)的。void visit_print(CSTree p);初始條件：樹T存在，visit_print是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作函數(shù)：對T的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit_print()一次且至多一次。與visit函數(shù)不一樣的是，visit函數(shù)只是輸出一個結(jié)點(diǎn)的值，而visit_print還輸出其結(jié)點(diǎn)，第一個孩

9、子，其右兄弟和雙親的值void Print(CSTree T,void (*visit)(CSTree);附加函數(shù)：用于顯示樹的所有內(nèi)容。初始條件：樹T存在；操作結(jié)果：將樹T的所有結(jié)點(diǎn)顯示出來。ADT TreeR RRRR5 數(shù)據(jù)處理 樹型數(shù)據(jù)存儲樣本： B RRRRC RRRRA RRRRF RRRRE RRRRD RRRRH RRRRG RRRRK RRRRR 轉(zhuǎn)化后樹的二叉鏈表存儲：ABDECFGHHK 以下為數(shù)據(jù)樣本測試：l 操作：判斷樹書否為空？ 結(jié)果：不為空l 返回樹T的深度？ 結(jié)果： 4l 返回樹T的根結(jié)點(diǎn)？ 結(jié)果： Al 返回樹F結(jié)點(diǎn)的值？ 結(jié)果： Fl 將樹根節(jié)點(diǎn)重新賦值為W

10、 ? 結(jié)果：AWl 求出結(jié)點(diǎn)A的雙親? 結(jié)果： Wl 求出結(jié)點(diǎn)A的第一個孩子結(jié)點(diǎn)? 結(jié)果： Dl 求出G的第一個兄弟結(jié)點(diǎn)? 結(jié)果： HXl 插入子樹C至A中第2科子樹？ ZY W 結(jié)果：ADBXCYEZGFHHK l 刪除樹結(jié)點(diǎn)為R的第三顆子樹？結(jié)果：W ADBXYEZ l 多種遍歷方式遍歷樹前序遍歷樹： W-A-D-X-Y-Z-E-B層次序遍歷樹： W-A-B-D-X-E-Y-Z后序遍歷樹： D-Y-Z-X-E-A-B-W 以下為運(yùn)行EXE程序測試過程：選擇1： 選擇14:選擇15：選擇16：選擇4：選擇5： 選擇6：選擇7：選擇8：選擇9：選擇10：選擇11：選擇12：選擇13：選擇14：

11、 選擇15：選擇16： 選擇2：6 程序清單解讀/*抽象數(shù)據(jù)類型樹-源碼*/#include#includeusing namespace std;const int TRUE=1;const int FALSE=0;const int OK=1;const int ERROR=0;const int OVERFLOW=1;const int MAX=30;const char NIL= ; /*樹的二叉鏈表孩子-兄弟-雙親存儲表示*/typedef struct CSnode char data; CSnode *firstchild,*nextsibling,*parent; /*最左孩子

12、指針 、下一個兄弟指針、雙親指針*/CSNode,*CSTree;/*樹的輔助隊列結(jié)構(gòu)定義和操作*/typedef struct QNode CSTree data; QNode *next;QNode,*QueuePtr; /*隊列的單鏈?zhǔn)酱鎯Y(jié)構(gòu)*/typedef struct LinkQueue QueuePtr front,rear; /*隊頭、隊尾指針*/LinkQueue;/*隊列定義*/*構(gòu)造一個空隊列*/int InitQueue (LinkQueue &Q) if(!(Q.front=Q.rear=new QNode) exit(OVERFLOW); Q.front-next

13、=NULL; return OK; /*銷毀隊列Q*/int DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; return OK;/*將Q清為空隊列*/int ClearQueue (LinkQueue &Q) QueuePtr p,q; Q.rear=Q.front; p=Q.front-next; Q.front-next=NULL; while(p) q=p; p=p-next; delete q; return OK;/*若隊列Q為空隊列則返回T

14、RUE，否則返回FALSE*/int QueueEmpty( LinkQueue Q) if(Q.front=Q.rear) return TRUE; else return FALSE;/* 插入元素e為Q的新的隊尾元素 */int EnQueue(LinkQueue &Q, CSTree e) QueuePtr p; if(!(p=new QNode) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;/*若隊列不空,刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR*/int D

15、eQueue(LinkQueue &Q,CSTree &e) QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; delete p; return OK;/*/*樹的二叉鏈表孩子-兄弟-雙親存儲定義*/*操作結(jié)果: 構(gòu)造空樹T*/int InitTree(CSTree &T)T=NULL;return OK;/*初始條件: 樹T存在*/*操作結(jié)果: 銷毀樹T*/void DestroyTree(CSTree

16、 &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delete T;/*初始條件：樹T存在*/*操作結(jié)果：按層次次序創(chuàng)建樹T*/int CreateTree(CSTree &T)char cMAX;CSTree p,p1,temp; LinkQueue q;InitQueue(q); coutdata=c0;T-nextsibling=NULL;T-parent=NULL;EnQueue(q,T);while(!QueueEmpty(q)DeQ

17、ueue(q,p);coutn請輸入datafirstchild=new CSNode; /*建立長子節(jié)點(diǎn)*/temp=p; /*保存該根節(jié)點(diǎn)*/ p1-parent=temp; /*建立雙親域*/p1-data=c0; EnQueue(q,p1); /*第一個孩子節(jié)點(diǎn)入隊列*/for(int i=1;inextsibling=new CSNode; /*建立下一個兄弟節(jié)點(diǎn)*/ p1-nextsibling-data=ci; /* 下一個兄弟節(jié)點(diǎn)賦值*/ p1-nextsibling-parent=temp; /*建立下一個兄弟節(jié)點(diǎn)雙親域*/ EnQueue(q,p1-nextsibling)

18、; /*各兄弟入隊*/ p1=p1-nextsibling;p1-nextsibling=NULL; /*最后的兄弟結(jié)點(diǎn)的nextsibling指針置為空*/ else /*樹無孩子只有根節(jié)點(diǎn)*/p-firstchild=NULL;else T=NULL; /*空樹*/return OK;/*初始條件：樹T存在*/*操作結(jié)果：將樹T清為空樹*/void ClearTree(CSTree &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delet

19、e T; T=NULL;/*初始條件：樹T存在*/*操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE*/int TreeEmpty(CSTree T)if(T=NULL) return TRUE;else return FALSE;/*初始條件：樹T存在*/*操作條件：返回T的深度*/int TreeDepth(CSTree T)CSTree p;int depth,max=0;if(!T)return 0;if(!T-firstchild)return 1;for(p=T-firstchild;p;p=p-nextsibling)depth=TreeDepth(p); /*遞歸求深度

20、*/if(depthmax) max=depth;return max+1; /*返回深度要加上根節(jié)點(diǎn)*/ /*初始條件: 樹T存在*/*操作結(jié)果: 返回T的根*/char Root(CSTree T)if(T) return T-data;else coutdata=cur_e) return a;if(a-firstchild) EnQueue(q,a-firstchild); if(a-nextsibling) EnQueue(q,a-nextsibling); return NULL;/*初始條件：樹T存在，cur_e可能是樹T中某個結(jié)點(diǎn)*/*操作結(jié)果：返回cur_e的值*/char

21、Value(CSTree T, char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(p) return p-data;elsecoutn在樹中找不到值為cur_e的節(jié)點(diǎn);return NIL;elsecoutn樹空，無值為cur_e的節(jié)點(diǎn); return NIL;/*初始條件：樹T存在，cur_e可能是T中的某個結(jié)點(diǎn)*/*操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為空*/char Parent(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(!p)coutn在樹中找不

22、到值為cur_eparent) coutn值為cur_eparent-data; else coutn樹空，無節(jié)點(diǎn);return NIL;/*初始條件: 樹T存在,cur_e是樹T中結(jié)點(diǎn)的值*/*操作結(jié)果: 改cur_e為value*/int Assign(CSTree &T,char cur_e,char value) CSTree p; if(T) p=Search(T,cur_e); if(p) coutn找到節(jié)點(diǎn)cur_e,賦新值為data=value; return OK; else coutn找不到節(jié)點(diǎn)cur_e,操作無法完成; return ERROR; else coutn樹為

23、空，操作無法完成; return ERROR; /*初始條件：樹T存在，cur_e可能是T中某個結(jié)點(diǎn)*/*操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回函數(shù)值為空。*/char LeftChild(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)coutn找不到值為cur_efirstchild)coutfirstchild-data;elsecoutn樹空，不存在值為cur_e的節(jié)點(diǎn);return NIL;/*初始條件：樹T存在，cur_e可能是T中的某個結(jié)點(diǎn)*/*操作結(jié)果：若cur_e有右兄弟，則返回

24、它的右兄弟，否則返回函數(shù)值為空*/char RightSibling(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)coutn找不到值為cur_enextsibling)coutnextsibling-data;elsecoutn樹空，不存在值為cur_e的節(jié)點(diǎn);return NIL;/*初始條件：樹T存在，p指向T中某個結(jié)點(diǎn)，1=i=p所指結(jié)點(diǎn)的度+1，非空樹c與T不相交*/*操作結(jié)果：插入c為T中p指結(jié)點(diǎn)的第i棵子樹*/int InsertChild(CSTree &T,CSTree p,int i,CSTree c)C

25、STree temp=p; /*保存根節(jié)點(diǎn)*/int j; if(!c)coutn子樹為空，不執(zhí)行操作;return OK;if(i1)coutn插入地址選擇出錯，不執(zhí)行操作;return ERROR;if(!p)coutfirstchild&i1)coutnextsibling=p-firstchild;p-firstchild=c;c-parent=p; elsep=p-firstchild;j=2;while(p&jnextsibling;j+; if(j=i) /*找到插入位置*/ c-nextsibling=p-nextsibling;p-nextsibling=c;c-parent

26、=temp; /*設(shè)置雙親節(jié)點(diǎn)*/else /*找不到插入位置*/ coutn插入節(jié)點(diǎn)錯誤; return ERROR; return OK;else /*樹空*/coutn樹空，操作不執(zhí)行;return ERROR;/*初始條件：樹T存在，p指向T中的某個結(jié)點(diǎn)，1=i=p所指結(jié)點(diǎn)的度*/*操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹*/int DeleteChild(CSTree &T,CSTree p,int i)CSTree q; int j; if(!T)coutn樹為空，不執(zhí)行操作;return OK;if(i1)coutn插入地址選擇出錯，不執(zhí)行操作;return ERROR;if(!

27、p)coutfirstchild&i1)coutfirstchild;p-firstchild=q-nextsibling; /*原次子現(xiàn)為長子*/ q-nextsibling=NULL;DestroyTree(q); /*銷毀以q為根的子樹*/ else /*刪除非長子*/p=p-firstchild;j=2; while(p&jnextsibling;j+;if(j=i) /*找到第i棵子數(shù)*/q=p-nextsibling; p-nextsibling=q-nextsibling;q-nextsibling=NULL; DestroyTree(q); else /* 找不到該子樹*/co

28、utn刪除節(jié)點(diǎn)錯誤，不執(zhí)行操作;return ERROR;return OK;else /*樹空*/coutn樹空，刪除錯誤，不執(zhí)行操作;return ERROR;/*訪問對結(jié)點(diǎn)操作的應(yīng)用函數(shù)*/void visit(char value)coutdata); PreOrderTraverseTree(T-firstchild,visit) ; PreOrderTraverseTree(T-nextsibling,visit) ;/*初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)*/*操作結(jié)果：按后根遍歷對T的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次*/void PostOrder

29、TraverseTree(CSTree T,void (*visit)(char)CSTree p; if(T) /*樹不空*/if(T-firstchild) PostOrderTraverseTree(T-firstchild,visit); /*后根遍歷長子子樹*/ p=T-firstchild-nextsibling; /*p指向長子下一個兄弟*/ while(p) PostOrderTraverseTree(p,visit); /* 后根遍歷下一個兄弟子樹*/ p=p-nextsibling; /*p指向下一個兄弟*/ visit(T-data); /*最后訪問根節(jié)點(diǎn)*/ /*初始條

30、件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。*/*操作結(jié)果：按層次次序?qū)的每一個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次*/void LevelOrderTraverseTree(CSTree T,void (* visit)(char)LinkQueue Q;CSTree p,q;if(T) /*樹不空*/InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q) /*隊列不空*/DeQueue(Q,q);visit(q-data); /*訪問節(jié)點(diǎn)*/if(q-firstchild) p=q-firstchild; EnQueue(Q,p); /*第一

31、個孩子入隊列*/while(p-nextsibling)p=p-nextsibling; EnQueue(Q,p); /*兄弟節(jié)點(diǎn)入隊列*/else /*樹空*/coutn樹空，層次遍歷失敗!;/*/*界面函數(shù)*/int menu() int choose; do system(cls);/*清屏*/ coutt *endl; coutt *抽象數(shù)據(jù)類型: 樹的孩子-兄弟-雙親存儲表*endl; coutt *endl; cout endl; coutttt 1. 創(chuàng)建一棵樹endl; coutttt 2. 銷毀樹endl; coutttt 3. 將樹清為空樹endl; coutttt 4.

32、判斷樹是否為空endl; coutttt 5. 返回樹的深度endl; coutttt 6. 返回樹的根節(jié)點(diǎn)endl; coutttt 7. 返回樹中某個節(jié)點(diǎn)值endl; coutttt 8. 將樹中某個節(jié)點(diǎn)重新賦值endl; coutttt 9. 求樹中某節(jié)點(diǎn)雙親endl; coutttt 10. 求樹中某節(jié)點(diǎn)最左孩子endl; coutttt 11. 求樹中某節(jié)點(diǎn)右兄弟endl; coutttt 12. 插入一棵樹endl; coutttt 13. 刪除一棵樹endl; coutttt 14. 先序遍歷樹endl; coutttt 15. 后序遍歷樹endl; coutttt 16. 層次遍歷樹endl; coutttt 17. 退出endl; coutt *endl; coutchoose; system(cls); /*運(yùn)行前清屏*/ while(choose17); return choose; /*主函數(shù)*/int main() int i; CSTree T=NULL,T1,p; char e,e1; for(;) sw