數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：14 大?。?48.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換_第1頁(yè)

已閱讀1頁(yè)，還剩13頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　綱要　　一程序設(shè)計(jì)要求與目的　　二存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)　　三算法設(shè)計(jì)（流程圖）　　四詳細(xì)設(shè)計(jì)（源代碼）　　五調(diào)試

2、與分析　　六實(shí)驗(yàn)總結(jié)　　七參考文獻(xiàn)　　第一章程序設(shè)計(jì)要求與目的　　題目：樹(shù)與二叉樹(shù)的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹(shù)的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)

3、包含建樹(shù)的實(shí)現(xiàn)。　　第二章存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)　　引入頭文件：　　#include <stdio.h>　　#include <malloc.h>　　#include <

4、stdlib.h>　　設(shè)置常量：　　#define MAX_TREE_SIZE 100　　一般樹(shù)的存儲(chǔ)結(jié)構(gòu)有以下幾種：雙親結(jié)點(diǎn)，孩子結(jié)點(diǎn)，孩子兄弟結(jié)點(diǎn)。本實(shí)驗(yàn)運(yùn)用到的是雙親結(jié)點(diǎn)和孩子兄弟結(jié)點(diǎn)。具體存儲(chǔ)結(jié)構(gòu)如下：　　/*樹(shù)的雙親表

5、示結(jié)點(diǎn)結(jié)構(gòu)定義*/　　typedef struct 　　{　　int data;　　int parent; //雙親位置域<b

6、>　　}PTNode;　　/*雙親表示法樹(shù)結(jié)構(gòu)*/　　typedef struct 　　{　　PTNode node[MAX_TREE_SIZE];

7、int count; //根的位置和節(jié)點(diǎn)個(gè)數(shù)　　}PTree;　　/*樹(shù)的孩子兄弟表示結(jié)點(diǎn)結(jié)構(gòu)定義*/　　typedef struct node{　　int data;</p&

8、gt;　　struct node *firstchild;　　struct node *rightsib;　　}BTNode,*BTree;　　第三章算法設(shè)計(jì)（流程圖）　　流程圖：<

9、;p>　　第四章詳細(xì)設(shè)計(jì)（源代碼）　　詳細(xì)設(shè)計(jì)共有以下函數(shù)的實(shí)現(xiàn)：　　樹(shù)的初始化函數(shù)（雙親法和孩子結(jié)點(diǎn)法兩種），建樹(shù)函數(shù)，輸出樹(shù)函數(shù)，樹(shù)的前序遍歷函數(shù)（遞歸和非遞歸兩種），樹(shù)的后序遍歷函數(shù)(遞歸和非遞歸兩種）,樹(shù)的層次遍歷函數(shù)，一般樹(shù)和二叉樹(shù)的轉(zhuǎn)換函數(shù)。　　主菜單和副菜單。</b&

10、gt;　　主函數(shù)。　　具體代碼如下：　　//初始化樹(shù)(雙親表示法)　　void init_ptree(PTree *tree)　　{&l

11、t;/b>　　tree->count=-1;　　}　　//初始化樹(shù)結(jié)點(diǎn)(孩子兄弟表示法)　　BTNode GetTreeNode(int x)　　{</b&

12、gt;　　BTNode t;　　t.data=x;　　t.firstchild=t.rightsib=NULL;　　return t;

13、　　}　　//樹(shù)的前序遍歷(遞歸)　　void preorder(BTNode *T)　　{　　if(T!=NULL)

14、　　{　　printf("%d ",T->data);　　preorder(T->firstchild);　　preorder(T->rightsib);　　}</p&g

15、t;　　}　　//樹(shù)的前序遍歷(非遞歸)　　void preorder2(PTree T)　　{　　int i;

16、　　for(i=0;i<T.count;i++)　　{　　printf("%d ",T.node[i]);　　}　　}</b&g

17、t;　　//樹(shù)后序遍歷(遞歸)　　void inoeder(BTNode *T)　　{　　if(T!=NULL)　　{<p&

18、gt;　　inoeder(T->firstchild);　　printf("%d ",T->data);　　inoeder(T->rightsib);　　}　　}</b&

19、gt;　　//樹(shù)后序遍歷(非遞歸)　　void inoeder2(PTree T)　　{　　int i;　　for(i=T.count-1;i>=0

20、;i--)　　{　　printf("%d ",T.node[i]);　　}　　}<b&g

21、t;　　//層次遍歷　　void level(PTree T)　　{　　int i;　　for(i=0;i<T.count;i++)<p&g

22、t;　　{　　printf("%d ",T.node[i]);　　}　　}　　//水平輸出二叉樹(shù)&l

23、t;/p>　　void PrintBTree(BTNode *root,int level) 　　{ 　　int i;　　if(root!=NULL)

24、;　　{ 　　PrintBTree(root->rightsib,level+1); 　　for(i=1;i<=8*level;i++) 　　printf(" "); 　　printf("-------%d\n

25、",root->data); 　　PrintBTree(root->firstchild,level+1); 　　}　　}　　//輸出樹(shù)

26、　　void print_ptree(PTree tree)　　{　　int i;　　printf(" 序號(hào) 結(jié)點(diǎn) 雙親\n");&l

27、t;p>　　for(i=0;i<=tree.count;i++)　　{　　printf("%8d%8d%8d",i,tree.node[i].data,tree.node[i].parent);　　printf("\n");

28、　　}　　}　　/*用雙親表示法創(chuàng)建樹(shù)*/　　PTree CreatTree(PTree T)　　{</p&g

29、t;　　int i=1;　　int fa,ch;　　PTNode p;　　for(i=1;ch!=-1;i++)　　{

30、;　　printf("輸入第%d結(jié)點(diǎn):\n",i);　　scanf("%d,%d",&fa,&ch);　　printf("\n");　　p.data=ch;　　p.paren

31、t=fa;　　T.count++;　　T.node[T.count].data = p.data;　　T.node[T.count].parent = p.parent;　　}　　printf

32、("\n");　　printf("創(chuàng)建的樹(shù)具體情況如下:\n");　　print_ptree(T);　　return T;　　}&l

33、t;p>　　/*一般樹(shù)轉(zhuǎn)換成二叉樹(shù)*/　　BTNode *change(PTree T)　　{　　int i,j=0;　　BTNode p[MAX_TREE_SIZE];　　BTNode

34、 *ip,*is,*ir,*Tree;　　ip=(BTNode *)malloc(sizeof(BTNode));　　is=(BTNode *)malloc(sizeof(BTNode));　　ir=(BTNode *)malloc(sizeof(BTNode));　　T

35、ree=(BTNode *)malloc(sizeof(BTNode));　　for(i=0;i<T.count;i++)　　{　　p[i]=GetTreeNode(T.node[i].data);　　}<

36、;/b>　　for(i=1;i<T.count;i++)　　{　　ip=&p[i];　　is=&p[j];

37、　　while(T.node[i].parent!=is->data)　　{　　j++;　　is=&p[j];

38、;　　}　　if(!(is->firstchild))　　{　　is->firstchild=ip;　　ir=ip;<

39、;b>　　}　　else　　{　　ir->rightsib=ip;　　ir=ip;&

40、lt;b>　　}　　}　　Tree=&p[0];　　return Tree;　　}　　/*主菜單*/&

41、lt;/b>　　void Menu()　　{　　printf("=================主菜單=======================\n");　　printf("***輸入1---

42、----------以雙親法創(chuàng)建一棵一般樹(shù)***\n");　　printf("***輸入2-------------樹(shù)的前序遍歷(遞歸)*******\n");　　printf("***輸入3-------------樹(shù)的后序遍歷(遞歸)*******\n");

43、　printf("***輸入4-------------樹(shù)的前序遍歷(非遞歸)*****\n");　　printf("***輸入5-------------樹(shù)的后序遍歷(非遞歸)*****\n");　　printf("***輸入6-------------層次序的非遞歸遍歷*******\n")

44、;　　printf("***輸入0-------------退出程序*****************\n");　　printf("==============================================\n");　　printf("請(qǐng)輸入執(zhí)行

45、的指令:");　　}　　/*副菜單*/　　void Menu2()　　{　　printf("**

46、***************副菜單*******************\n");　　printf("***9-------------返回主菜單繼續(xù)操作*******\n");　　printf("***0-------------退出程序*****************\n");

47、　　}　　/*主函數(shù)*/　　void main()　　{　　int i=0,c1,c2;<

48、;b>　　PTree T;　　BTNode *Tree;　　init_ptree(&T);　　loop:　　Menu();

49、;　　scanf("%d",&c1);　　switch(c1)　　{ 　　case 1: 　　printf("建立一般樹(shù),依次輸入各個(gè)結(jié)點(diǎn)情況:\n&quo

50、t;);　　printf("輸入結(jié)點(diǎn)方式:雙親數(shù)據(jù),整型數(shù)據(jù)(第一個(gè)結(jié)點(diǎn)雙親數(shù)據(jù)為-1,最后以-1,-1結(jié)束)\n例子:-1,1 1,3\n");　　T=CreatTree(T);　　Tree=change(T);　　printf("一般樹(shù)

51、轉(zhuǎn)換成二叉樹(shù)后的情況:\n");　　PrintBTree(Tree,i);　　getchar();　　break;　　case 2: 　　pr

52、intf("樹(shù)的前序遍歷(遞歸):\n");　　preorder(Tree);　　printf("\n");　　break;　　case 3:</p

53、>　　printf("樹(shù)的后序遍歷(遞歸):\n");　　inoeder(Tree);　　printf("\n");　　break;　　case

54、4: 　　printf("樹(shù)的前序遍歷(非遞歸):\n");　　preorder2(T);　　printf("\n");　　break;<p&g

55、t;　　case 5: 　　printf("樹(shù)的后序遍歷(非遞歸):\n");　　inoeder2(T);　　printf("\n");　　break;&

56、lt;/p>　　case 6: 　　printf("樹(shù)的層次遍歷:\n");　　level(T);　　printf("\n");　　break;

57、　　case 0:　　exit(1);　　break; 　　}

58、Menu2();　　scanf("%d",&c2);　　if(c2==9)　　goto loop;　　else if(c2==0)<b&g

59、t;　　exit(1);　　}　　第五章調(diào)試與分析　　程序開(kāi)始：　　建立一棵一般樹(shù)：輸入指令1

60、　　輸入結(jié)點(diǎn)的方式：　　雙親數(shù)據(jù)（整型），結(jié)點(diǎn)數(shù)據(jù)（整型）以-1，-1結(jié)束　　如：-1，1 1，2 -1，-1　　一般樹(shù)創(chuàng)建完的具體情況：　　把一般樹(shù)轉(zhuǎn)換為二叉樹(shù)后：　　副菜單選擇：選

61、擇9繼續(xù)操作　　運(yùn)用各種遍歷形式遍歷樹(shù)：　　副菜單選擇:選擇0結(jié)束程序　　第六章實(shí)驗(yàn)總結(jié)　　通過(guò)本次程序設(shè)計(jì)，讓我更深層次地了解到了樹(shù)各種函數(shù)的運(yùn)用，如何運(yùn)用各種存儲(chǔ)結(jié)構(gòu)創(chuàng)建樹(shù)，以及在實(shí)驗(yàn)中還涉及到遞歸的運(yùn)用，遞歸的思想省去了復(fù)雜的

62、算法設(shè)計(jì)。在實(shí)驗(yàn)中不可避免的出現(xiàn)了大大小小的問(wèn)題，在調(diào)試中透徹領(lǐng)悟各種算法的真諦，同樣的錯(cuò)誤在下次遇到時(shí)就可以避免了。在實(shí)驗(yàn)中，分別使用了VC++和Turbo C兩種編譯器，在使用各種編譯器的同時(shí)能了解不同的編譯器的不同之處，取長(zhǎng)補(bǔ)短，更好的設(shè)計(jì)程序。　　參考文獻(xiàn)　　[1]趙堅(jiān)，姜梅主編.據(jù)結(jié)構(gòu)（C語(yǔ)言版）.中

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載