數據結構課程設計--樹的應用

上傳人：奔*** IP屬地：河北更新時間：2024-05-21 格式：doc 頁數：17 大小：55.50KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構　　課程設計報告　　設計題目：樹的應用　　年級 　　班

2、級 　　姓名 　　學號 　　指導教師 </p&

3、gt;　　起止時間 12—9—24-----------9—28 　　2012--2013 年一學期　　一．實習目的　　更加深入的理解、掌握數據結構的一些算法并加以實現(xiàn)，提高自身的地動手實踐能力，培養(yǎng)更好的團隊合作能力。&l

4、t;/p>　　二．問題描述（具體任務）　　設計、創(chuàng)建一棵樹，實現(xiàn)樹與二叉樹的互相轉換以及對樹的遞歸非遞歸先序遍歷，樹的遞歸非遞歸后序遍歷以及樹的非遞歸層次遍歷的操作。　　三．需求分析　　1、本演示程序中，可以輸入任意個節(jié)點構造你想要的樹，本程序構

5、造時默認的是一個三度的樹，也就是在創(chuàng)建樹時所默認的是每個節(jié)點都有三個孩子，但是你可以通過鍵盤輸入#號來讓某些節(jié)點為空，以此來創(chuàng)建讓您滿意的樹。　　2、程序以用戶和計算機對話的形式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入要創(chuàng)建樹的節(jié)點值，然后通過程序執(zhí)行輸出結果。　　3、程序的執(zhí)行命令包括：&

6、lt;b>　?。?）樹的創(chuàng)建模塊　?。?）樹與二叉樹相互轉換模塊　　（3）樹的先序、后序、層次遍歷（遞歸與非遞歸算法）　　4、測試數據：　?。?）測試數據由用戶從鍵盤上任意輸入。<

7、;p>　　四．算法設計思想及流程圖　　（1）根據老師所提供的課程設計題目及要求我們將程序分了9個模塊，通過主程序調用相應的模塊來實現(xiàn)課程的操作。　　五．C++語言源代碼　　#include <iostream>　　using namespace std;

8、　　#define m 3　　typedef char ElemType;　　typedef struct Node {　　ElemType data;　　struct Node* child[m];<

9、;p>　　}Node,*Tree;　　typedef struct BiTNode{　　ElemType data;　　struct BiTNode*lchild,*rchild;　　}BiTNode,*BiTree;　　t

10、ypedef struct stack { //棧結構定義　　BiTree data[100]; //data 元素類型為指針　　int top; //棧頂指針　　}seqstack;　　/

11、/ 按前序遍歷創(chuàng)建一棵度數為3的樹的遞歸算法　　void createtree(Tree &p) {　　int i;　　char ch;　　if((ch=getchar())==

12、9;#') p=NULL; //建立一棵空樹　　else {　　p=(Tree)malloc(sizeof(Node)); 　　p->data=ch;　　for(i=0;i<m;i++)</p&g

13、t;　　createtree(p->child[i]);　　}　　}　　//樹轉化為二叉樹　　BiTree TreetoBiTre

14、e(Tree &p) {　　int i;　　if(p==NULL)　　return NULL;　　BiTNode* q=(BiTNode*)malloc(sizeof(ElemType)) ;//創(chuàng)建根節(jié)點----------

15、--------------------------------------------------　　q->data =p->data;　　q->lchild=NULL;　　q->rchild=NULL;　　if(p->child[0]!=

16、NULL){　　q->lchild=TreetoBiTree(p->child[0]);//把樹的第一個孩子賦給二叉樹的左孩子　　BiTNode* r=q->lchild;　　if(p->child[1]!=NULL) {　　for(i=1;i&l

17、t;m;i++) {　　if(p->child[i]!=NULL) {　　r->rchild=TreetoBiTree(p->child [i]);　　r=r->rchild;　　}&l

18、t;p>　　else　　return q;　　}　　}　　else if(p->child[2]!=NULL

19、){　　r->rchild=TreetoBiTree(p->child [2]);　　r=r->rchild;　　}　　else&

20、lt;b>　　return q;　　}　　else if((p->child[1]!=NULL)){　　q->lchild=TreetoBiTree(p->child[1]); //把樹的第二個孩子賦給二叉樹的左孩子</

21、p>　　BiTNode* r=q->lchild;　　if(p->child[2]!=NULL) {　　r->rchild=TreetoBiTree(p->child [2]);　　}

22、;　　else　　return q;　　}　　else if(p->child[2]!=NULL) {　　q->lchild=TreetoBiTr

23、ee(p->child[1]); //把樹的第三個孩子賦給二叉樹的左孩子　　}　　return q;　　}　　//二叉樹轉換為樹&

24、lt;/b>　　Tree BiTreetoTree(BiTree &q) {　　int i;　　if(q==NULL)return NULL;　　Node* p=(Node*)malloc(sizeof(ElemType

25、));　　p->data=q->data;//根賦值　　for(i=0;i<m;i++) {　　p->child[i]=NULL;　　}　　if(q->lchil

26、d!=NULL) {　　p->child[0]=BiTreetoTree(q->lchild);　　BiTNode* r=q->lchild ;　　for(i=1;i<m;i++) {　　if(r->rchild!=NULL) {</p

27、>　　p->child[i]=BiTreetoTree(r->rchild );　　r=r->rchild ;　　}　　}　　}&l

28、t;/b>　　return p;　　}　　void push(seqstack* s,BiTree p) { //進棧　　s->data[++s->t

29、op]=p;　　}　　BiTree pop(seqstack* s) { //出棧　　if(s->top!=-1) { //非遞歸遍歷中，top初始值為-1　　s-

30、>top--;　　return (s->data[s->top+1]);　　}　　else 　　return NULL;<p&g

31、t;　　}　　//二叉樹中序遍歷 (樹的后序非遞歸遍歷)非遞歸算法　　void inorder1(BiTree p) {　　seqstack s;　　s.top=-1;&

32、lt;p>　　while((p!=NULL)||(s.top!=-1)) {　　while(p) {　　push(&s,p); 　　p=p->lchild; //子樹根結點全部進棧　　}

33、　　if(s.top!=-1) {　　p=pop(&s);　　printf("%c",p->data); //輸出根結點，其實也就是左孩子或右孩子(沒有孩子的根結點是它父親的左或右孩子）　　p=p->rchild;

34、 //進入右孩子訪問　　}　　}　　}　　void visit(char ch)　　{cout<<

35、ch;}　　//二叉樹先序遍歷非遞歸算法　　void PreOrderPrint(BiTree p) {　　seqstack s;　　s.top=-1; //top初始值為-1

36、　　while((p!=NULL)||(s.top!=-1)) { // 當前處理的子樹不為空，或棧不為空，則循環(huán)　　while(p) {　　visit(p->data); //訪問當前子樹根結點　　s.top++;</p

37、>　　s.data[s.top]=p; //當前子樹根結點進棧(因為還要訪問右子樹)　　p=p->lchild; //訪問此根結點左孩子　　} //循環(huán)直到遍歷完當前子樹根結點，和其左孩子　　if(s.

38、top>-1) {　　p=pop(&s); //當前子樹跟結點出棧　　p=p->rchild; //訪問其右孩子　　}　　}&l

39、t;/b>　　} 　　//樹的前序遍歷遞歸算法　　void preorder(Tree p) { //P為指向樹根的指針　　int i;<p&

40、gt;　　if(p!=NULL) { //樹不為空　　printf("%c",p->data); //輸出根節(jié)點的值　　for(i=0;i<m;i++) //依次遞歸實現(xiàn)各子樹的前序遍歷　　preorder(p->

41、child[i]);　　}　　}　　//樹的后序遍歷的遞歸算法　　void postorder(Tree p) {　　int i;<

42、;/b>　　if(p!=NULL) {　　for(i=0;i<m;i++) //依次遞歸實現(xiàn)個子樹的后序遍歷　　postorder(p->child[i]);　　printf("%c",p->data);

43、 //輸出根節(jié)點的值　　}　　}　　//樹的非遞歸層次遍歷　　void level(Tree t) {　　Tree queue

44、[20]; //存放等待訪問的節(jié)點隊列,每個元素都是指針型　　int f=0,r=0,i; //f,r 分別是隊頭,隊尾指針　　Tree p;　　queue[0]=t;　　while(f<=r) {

45、　　p=queue[f];　　f++;　　printf("%c",p->data); //訪問隊頭元素　　for(i=0;i<m;i++) //剛被訪問的元素的所有子節(jié)點依次進隊

46、　　if(p->child[i]) {　　++r;　　queue[r]=p->child[i];　　}　　}

47、　　}　　void main() {　　system("color 1F"); //設置控制臺的背景色為藍色 　　printf("\t\t**********************************\n"

48、);　　printf("\t\t 第五組實驗內容：樹的應用 \n");　　printf("\t\t 組員：趙攀攀，張姣姣，聶永勝 \n");　　printf("\t\t*******************

49、***************\n");　　Tree T;　　Tree T1;　　BiTree p;　　printf("=====輸入要創(chuàng)

50、建的樹=====:\n");　　createtree(T);//創(chuàng)建一棵樹　　printf("\n樹的先序遞歸遍歷:");　　preorder(T);　　printf("\n樹的后序遞歸遍歷:");

51、　　postorder(T);　　printf("\n樹的層序非遞歸遍歷:");　　level(T);　　printf("\n");　　printf("\n====

52、=樹轉換為二叉樹=====\n");　　p=TreetoBiTree(T);　　printf("\n二叉樹先序非遞歸遍歷(樹的先序非遞歸):");　　PreOrderPrint(p);　　printf("\n二叉樹中序非遞歸遍歷(樹

53、的后序非遞歸):");　　inorder1(p);　　printf("\n");　　printf("\n=====二叉樹轉換為樹=====\n");　　T1=BiTreetoTree(p);<

54、p>　　printf("\n按先序遞歸遍歷此樹:");　　preorder(T1);　　printf("\n");　　printf("\n按后序遞歸遍歷此樹:");　　postorder(T1);</

55、p>　　printf("\n");　　printf("\n按層次非遞歸遍歷此樹:");　　level(T1);　　printf("\n");　　return ;<

56、;/b>　　}　　六．測試分析（運行結果）　　比如說輸入以下內容：　　RAD###E####B###CFG###H###K#####　　將會輸出下面內容：</b&

57、gt;　　樹的先序遞歸遍歷：RADEBCFGHK　　樹的后序遞歸遍歷：DEABGHKFCR　　樹的層次非遞歸遍歷：RABCDEFGHK　　====樹轉換為二叉樹====　　二叉樹先序非遞歸遍歷（樹的先序非遞歸）：RADEBCFGH

58、K　　二叉樹中序非遞歸遍歷（樹的后序非遞歸）：DEABGHKFCR　　====二叉樹轉換為樹====　　按先序遞歸遍歷此樹：RADEBCFGHK　　按按后序遞歸遍歷此樹：DEABGHKFCR　　按按后序遞歸遍歷此樹: RABCDE

59、FGHK　　七．總結（收獲及體會）　　1、收獲及體會；　　在學習數據結構這門課的時候，對一些算法的設計和應用并不是太理解，而且不知道怎么結合實際去實現(xiàn)這些算法，這次課程設計，我們通過各種途徑去掌握了解樹的應用各個分塊的算法并加以實現(xiàn)，使我們對樹的各種操作得到了很好的掌握，剛開

60、始時一直在選用樹的存儲結構上產生了意見分歧，一直糾結徘徊在是用孩子兄弟法還是孩子法來創(chuàng)建，最后考慮到后面的遍歷操作，我們統(tǒng)一了意見，決定采用孩子法。在編程過程中我們遇到了很多問題，最終都是通過資料的查詢及小組成員的討論攻克了一個又一個的難題，在此期間我們充分認識到了團隊合作的重要性，這對于以后我們的工作起到了一個很好的磨礪機會。這次的實習讓我們收獲到的不僅僅是知識的積累與鞏固，更重要的是對團隊合作的認識。<

61、p>　　2、在此部分最后部分注明每位同學所做的具體工作。　　對于此次課程設計，我們小組做了明確的分工，在程序的9個模塊中，聶永勝同學主要負責樹的創(chuàng)建，樹轉換為二叉樹及二叉樹轉換為樹三個模塊，張姣姣同學負責樹的先序遞歸遍歷，樹的后序遞歸遍歷以及主程序對各個模塊的融合三個模塊，趙攀攀同學負責樹的先序，后序，層次的非遞歸遍歷三個模塊，在每個人將其工作任務完成后再將自己的編程思想講授給另外兩個同學

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構課程設計--樹的應用

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計--樹的應用

文檔簡介

溫馨提示

最新文檔

評論

免費下載