《樹地綜合操作 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》由會(huì)員分享，可在線閱讀，更多相關(guān)《樹地綜合操作 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（23頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(論文)樹的綜合操作 院系名稱 專業(yè)班級(jí) 學(xué)號(hào) 學(xué)生 指導(dǎo)教師課程設(shè)計(jì)論文任務(wù)與評(píng)語院系：電子與信息工程學(xué)院 教研室：軟件工程學(xué)號(hào)學(xué)生專業(yè)班級(jí)課程設(shè)計(jì)論文題目樹的綜合操作課程設(shè)計(jì)論文任務(wù)任務(wù)要求：樹的綜合操作實(shí)現(xiàn)以下幾個(gè)功能：1創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；2非遞歸實(shí)現(xiàn)中序遍歷二叉樹3非遞歸實(shí)現(xiàn)先序遍歷二叉樹。4遞歸實(shí)現(xiàn)層次遍歷二叉樹；5求出二叉樹的葉子結(jié)點(diǎn)數(shù)和層次數(shù)。技術(shù)要求：1、數(shù)據(jù)的邏輯結(jié)構(gòu)采用樹形結(jié)構(gòu)，物理結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表。2、軟件能正常運(yùn)行，界面清晰，操作要簡(jiǎn)單。3、系統(tǒng)要有主界面設(shè)計(jì)，調(diào)用各個(gè)功能項(xiàng)。4、采用Viscal C+編寫代碼，可讀性強(qiáng)。5

2、、數(shù)據(jù)類型用typedef 定義。指導(dǎo)教師評(píng)語與成績(jī)平時(shí)成績(jī)：辯論成績(jī)：論文成績(jī)：總成績(jī)：指導(dǎo)教師簽字：年月日注：平時(shí)成績(jī)占20%，辯論成績(jī)占40%，論文成績(jī)占40%。19 / 23摘 要這次的課題主要是創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存，通過這一過程了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力并提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力主要解決以下問題創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；非遞歸實(shí)現(xiàn)中序遍歷二叉樹；非遞歸實(shí)現(xiàn)先序遍歷二叉樹；遞歸實(shí)現(xiàn)層次遍歷二叉樹；求出二叉樹的葉子節(jié)點(diǎn)數(shù)和層次樹；關(guān)鍵詞：存儲(chǔ)結(jié)構(gòu)；二叉樹；C+目 錄第1章緒論1系統(tǒng)的開發(fā)背景1開發(fā)工具與語言1第

3、2章概要設(shè)計(jì)1模塊劃分12.2 數(shù)據(jù)結(jié)構(gòu)的選擇1第3章系統(tǒng)詳細(xì)設(shè)計(jì)與編碼2完整的源程序2程序的輸入和輸出3調(diào)試程序中遇到的問題與解決方案4第4章思考題解析54.1 思考題的選擇5類C算法5程序分析5第5章總結(jié)6參考文獻(xiàn)7附錄8第1章 緒論系統(tǒng)的開發(fā)背景二叉樹結(jié)構(gòu)是C語言中的難點(diǎn)，但是近年來二叉樹的應(yīng)用越發(fā)的廣泛，實(shí)用性越來越強(qiáng)。為了應(yīng)對(duì)日新月異的時(shí)代變化，我參與了這個(gè)課題來提高自己對(duì)二叉樹的掌握與語言本系統(tǒng)使用Viscal C+語言開發(fā)，主界面清晰顯示所有功能項(xiàng)，使用簡(jiǎn)單。各個(gè)功能項(xiàng)均定義一個(gè)函數(shù)來實(shí)現(xiàn)，在主函數(shù)中調(diào)用各個(gè)子函數(shù)實(shí)現(xiàn)不同的功能。第2章 概要設(shè)計(jì)模塊劃分1題目應(yīng)實(shí)現(xiàn)的具體功能；創(chuàng)

4、建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；非遞歸實(shí)現(xiàn)中序遍歷二叉樹；非遞歸實(shí)現(xiàn)先序遍歷二叉樹；遞歸實(shí)現(xiàn)層次遍歷二叉樹；求出二叉樹的葉子節(jié)點(diǎn)數(shù)和層次樹；2.2 數(shù)據(jù)結(jié)構(gòu)的選擇系統(tǒng)數(shù)據(jù)的邏輯結(jié)構(gòu)采用樹形結(jié)構(gòu)，物理結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表。存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct lnodechar data;struct lnode *lchild,*rchild;lnode,*tree;第3章 系統(tǒng)詳細(xì)設(shè)計(jì)與編碼完整的源程序#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define MaxSize 100t

5、ypedef char TElemType;typedef int Status;/二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef struct LNodeBiTree data;struct LNode *next;LNode,*LinkList;/進(jìn)棧Status Push(LinkList& S,BiTree T)LinkList stack;stack=(LinkList)malloc(sizeof(LNode);

6、 /分配空間stack-data=T;stack-next=S-next; /進(jìn)棧S-next=stack;return OK;/Push/出棧Status Pop(LinkList &S,BiTree &T)LinkList stack;stack=S-next; /出棧S-next=stack-next; /棧頂指向下個(gè)元素T=stack-data;return OK;/Pop/是否為空棧Status StackEmpty(LinkList S)if(S-next=NULL) return OK;else return ERROR;/以先序次序建立二叉樹Status CreatBiTree

7、(BiTree &T)TElemType ch;cinch;if(ch=#) T=NULL;else if(!(T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW); /分配存儲(chǔ)空間 T-data=ch; /生成根節(jié)點(diǎn) CreatBiTree(T-lchild); /生成左子樹 CreatBiTree(T-rchild); /生成右子樹return OK; /創(chuàng)建成功/CreatBiTree/非遞歸中序訪問二叉樹BiTree GoFarLeft(BiTree T,LinkList &S) /指到二叉樹最左邊結(jié)點(diǎn)if(!T) return NULL;wh

8、ile(T-lchild) Push(S,T); /結(jié)點(diǎn)進(jìn)棧 T=T-lchild;return T; /返回樹頭結(jié)點(diǎn)void Inorder_I(BiTree T)BiTree t;LinkList S;S=(LinkList)malloc(sizeof(LNode);S-next=NULL;t=GoFarLeft(T,S); /找到最左下的結(jié)點(diǎn)while (t) coutdatarchild) t=GoFarLeft(t-rchild,S); else if(!StackEmpty(S) /?？彰鞔_遍歷完畢 Pop(S,t); else t=NULL;/whilecout0) while(

9、p!=NULL) coutdatalchild; if(top0) top-; p=Stacktop; p=p-rchild; coutnext=NULL;Push(stack,b); /二叉樹頭結(jié)點(diǎn)進(jìn)棧while(!StackEmpty(stack) /是否為空 Pop(stack,p); /出棧 while (p) coutdatarchild)Push(stack,p-rchild); /訪問右指點(diǎn) p=p-lchild; coutlchild; while (top0&stacktop-rchild=p) p=stacktop-; /棧頂結(jié)點(diǎn)出棧 coutdata0) p=stackt

10、op-rchild; /開始遍歷右子樹while(top0);coutlchild)&(!T-rchild) count+; CountLeaf(T-lchild,count); /左子樹葉子個(gè)數(shù) CountLeaf(T-rchild,count); /右子樹葉子個(gè)數(shù)/CountLeaf/計(jì)算雙結(jié)點(diǎn)個(gè)數(shù)void CountParent(BiTree T,int &count)if(T)if(T-lchild&T-rchild) count+;CountParent(T-lchild,count); /左子樹雙結(jié)點(diǎn)個(gè)數(shù)CountParent(T-rchild,count); /右子樹雙結(jié)點(diǎn)個(gè)數(shù)/

11、計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)void Count(BiTree T,int &count)if(T) Count(T-lchild,count); Count(T-rchild,count); count+; /結(jié)點(diǎn)個(gè)數(shù)/單結(jié)點(diǎn)個(gè)數(shù)void CountChild(BiTree T,int &count)if(T) if(T-lchild&(!T-rchild)|(T-rchild&(!T-lchild) count+; CountChild(T-lchild,count); /左子樹單結(jié)點(diǎn)個(gè)數(shù) CountChild(T-rchild,count); /右子樹單結(jié)點(diǎn)個(gè)數(shù)/計(jì)算樹的高度int Depth(B

12、iTree T) int depthval,depthLeft,depthRight;if(!T) depthval=0;elsedepthLeft=Depth(T-lchild); /左子樹高度depthRight=Depth(T-rchild); /右子樹高度depthval=1+(depthLeftdepthRight ?depthLeft:depthRight); /取高度最高return depthval; /返回/計(jì)算任意結(jié)點(diǎn)所在的層次int NodeLevel(BiTree T,TElemType &p,int &count)if(T=NULL) return 0;if(T-da

13、ta=p) return 1;if(NodeLevel(T-lchild,p,count)|(NodeLevel(T-rchild,p,count) count+; return 1; return 0;/主函數(shù)void main()char flag;cout操作選項(xiàng)endl;cout1,非遞歸打印二叉樹(前序，中序，后序)endl;cout2,計(jì)算二叉樹的結(jié)點(diǎn)總數(shù)，雙孩子個(gè)數(shù)，單孩子結(jié)點(diǎn)數(shù)，葉子結(jié)點(diǎn)數(shù)目endl;cout3,計(jì)算二叉樹的高度endl;cout4,判斷結(jié)點(diǎn)的層次endl;do int item; coutitem; switch (item) case 1 : BiTree

14、T; cout請(qǐng)輸入要建立的二叉樹,以#表示空樹endl; CreatBiTree(T); cout先序非遞歸輸出二叉樹(兩種算法)endl; cout算法1:endl; PreOrder1(T); cout算法2:endl; PreOrder2(T); cout中序非遞歸輸出二叉樹endl; Inorder_I(T); cout后序非遞歸輸出二叉樹endl; PostOrder(T); coutendl; cout是否繼續(xù)操作?(y/n)flag; break; case 2: BiTree T; int nodeCount=0,leafCount=0,childCount=0,parent

15、Count=0; cout請(qǐng)輸入要建立的二叉樹,以#表示空樹endl; CreatBiTree(T); Count(T,nodeCount); CountParent(T,parentCount); CountChild(T,childCount); CountLeaf(T,leafCount); cout結(jié)點(diǎn)總數(shù)目為:nodeCountendl; cout雙孩子結(jié)點(diǎn)數(shù)目:parentCountendl; cout單孩子結(jié)點(diǎn)數(shù)目:childCountendl; cout葉子結(jié)點(diǎn)數(shù)目:leafCountendl; cout是否繼續(xù)操作?(y/n)flag; break; case 3: BiTr

16、ee T; cout請(qǐng)輸入要建立的二叉樹,以#表示空樹endl; CreatBiTree(T); cout該二叉樹的高度為:Depth(T)endl; cout是否繼續(xù)操作?(y/n)flag; break; case 4: BiTree T; int n=0; char ch; cout請(qǐng)輸入要建立的二叉樹,以#表示空樹endl; CreatBiTree(T); coutch; if(T=NULL) cout空樹endl; else NodeLevel(T,ch,n); cout結(jié)點(diǎn)的層次為:; coutn+1endl; cout是否繼續(xù)操作?(y/n)flag; break; defaul

17、t : cout無此選項(xiàng)請(qǐng)確定后再輸入!lchild);/*計(jì)算左子數(shù)的高度*/rh=btheight(BT-rchild);/*計(jì)算右子數(shù)的高度*/if(lhnum=lh-rh;/*計(jì)算結(jié)點(diǎn)的平衡因子*/return t+1結(jié)點(diǎn)的平衡因子等于其左子樹結(jié)點(diǎn)層次減去其右子樹結(jié)點(diǎn)層次，因此要想求得每個(gè)結(jié)點(diǎn)的平衡因子，就得在遍歷每個(gè)結(jié)點(diǎn)的時(shí)候，算出其左，右子樹的層次，程序中用到了遞歸調(diào)用子函數(shù) btheight(bitnode *bt)第5章 總結(jié)這是一門純屬于設(shè)計(jì)的科目，它需用把理論變?yōu)樯蠙C(jī)調(diào)試。剛開始學(xué)的時(shí)候確實(shí)有很多地方我很不理解，每次上課時(shí)教師都會(huì)給我們出不同的設(shè)計(jì)題目，對(duì)于我們一個(gè)初學(xué)者來

18、說，無疑是一個(gè)具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。教師會(huì)給我們需要編程的容一些講解，順著教師的思路，來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己的程序。剛開始學(xué)的時(shí)候確實(shí)有很多地方我很不理解，每次上上機(jī)課時(shí)教師都會(huì)給我們出不同的設(shè)計(jì)題目，對(duì)于我們一個(gè)初學(xué)者來說，無疑是一個(gè)具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。教師會(huì)給我們需要編程的容一些講解，順著教師的思路，來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己的程序，可是好多處的錯(cuò)誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯(cuò)誤，但是程序還是得繼續(xù)下去，我屢次請(qǐng)教了教師和同學(xué)，逐漸能自己找出錯(cuò)誤，并加以改正。TC里檢查錯(cuò)誤都是

19、用英文來顯示出來的，經(jīng)過了這次課程設(shè)計(jì)，現(xiàn)在已經(jīng)可以了解很多錯(cuò)誤在英文里的提示，這對(duì)我來說是一個(gè)突破性的進(jìn)步，眼看著一個(gè)個(gè)錯(cuò)誤通過自己的努力在我眼前消失，覺得很是開心。此次的程序設(shè)計(jì)能夠成功，是我和我的同學(xué)三個(gè)人共同努力作用的結(jié)果。在這一段努力學(xué)習(xí)的過程中，我們的編程設(shè)計(jì)有了明顯的提高。其實(shí)現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費(fèi)了好多心血，覺得它很難，是需用花費(fèi)了大量的時(shí)間編寫出來的?，F(xiàn)在真正的明白了一些代碼的應(yīng)用，每個(gè)程序都有一些共同點(diǎn)，通用的結(jié)構(gòu)，相似的格式。只要努力去學(xué)習(xí)，就會(huì)靈活的去應(yīng)用它。本人簽字：參考文獻(xiàn)1 徐孝凱編著. 數(shù)據(jù)結(jié)構(gòu)M第一版2 文博編著.數(shù)據(jù)結(jié)構(gòu)M第二版3 許卓群編著.數(shù)據(jù)結(jié)構(gòu)M第一版4 廉治編著.數(shù)據(jù)結(jié)構(gòu)教程M第一版5 晉良潁編著.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程M第三版