樹的應(yīng)用 課程設(shè)計報告

1、課 程 設(shè) 計課程設(shè)計名稱： 算法分析與綜合課程設(shè)計專 業(yè) 班 級 ： 計 科 0604 學(xué) 生 姓 名 ： 楊 恒 學(xué) 號 ： 20064140405 指 導(dǎo) 教 師 ： 白 浩 課程設(shè)計時間：2008.06.22-2008.06.27 計算機(jī)科學(xué)與技術(shù)專業(yè)課程設(shè)計任務(wù)書學(xué)生姓名楊恒專業(yè)班級計科0604學(xué)號20064140405題 目樹的應(yīng)用課題性質(zhì)其它課題來源自擬課題指導(dǎo)教師白 浩同組姓名無主要內(nèi)容 實(shí)現(xiàn)樹與二叉樹的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實(shí)現(xiàn)，應(yīng)包含建樹的實(shí)現(xiàn)。任務(wù)要求 1.實(shí)現(xiàn)對樹的建立。2.實(shí)現(xiàn)幾種樹的遍歷算法 參考文獻(xiàn) 1.c語言程序設(shè)

2、計（第三版） 清華大學(xué)出版社 譚浩強(qiáng) 著 2數(shù)據(jù)結(jié)構(gòu)（c語言版） 清華大學(xué)出版社 嚴(yán)蔚敏 吳偉民 編著審查意見指導(dǎo)教師簽字：教研室主任簽字： 2008年 5 月 8 日 一、需求分析1首先選擇一種結(jié)點(diǎn)實(shí)現(xiàn)樹結(jié)點(diǎn)的存儲。2首先建立樹，在用戶輸入各結(jié)點(diǎn)信息時，應(yīng)提示用戶輸入結(jié)點(diǎn)的父親，孩子，和兄弟的信息，即要讓用戶明確選擇各結(jié)點(diǎn)之間的相互聯(lián)系。3實(shí)現(xiàn)樹的遍歷算法。在該實(shí)驗(yàn)中，實(shí)現(xiàn)了樹的先根的遞歸和非遞歸算法，后根的遞歸算法以及按層次序的非遞歸算法。4用戶界面的設(shè)計應(yīng)滿足用戶的選擇，可以選擇不同的遍歷算法顯示遍歷結(jié)果。二、概要設(shè)計 1用孩子兄弟表示法作為樹結(jié)點(diǎn)的存儲結(jié)構(gòu)typedef struct

3、csnode char data; struct csnode *firstchild; struct csnode *nextbiling; 2一些全局變量的聲明 struct csnode * root;struct btree * x;char flag;3樹建立的算法描述 建立根結(jié)點(diǎn)： void create_root() root = (struct csnode*)malloc(sizeof(struct csnode); printf(請輸入根結(jié)點(diǎn)信息:); scanf(%c,&root-data);遞歸建樹： voidcreate(structcsnode*temp) /構(gòu)造樹

4、 遞歸建樹 if(temp!=null) /輸入長子信息 printf( 是否有孩子?(y/n)n); flag=getchar(); if(flag = y | flag = y) t =(struct csnode*)malloc(sizeof(struct csnode); printf( 請輸入長子信息:n ); t-data=getchar(); temp - firstchild = t;/指向長子 else temp - firstchild = null; /輸入兄弟信息 printf(是否有兄弟?(y/n)n ); if(flag = y | flag = y) m = (s

5、truct csnode*)malloc(sizeof(struct csnode); printf( 請輸入兄弟信息:n); m-data=getchar(); temp - nextbiling = m; /指向兄弟 else temp - nextbiling = null;/遞歸建立結(jié)點(diǎn) create(temp - firstchild); create(temp - nextbiling); 4樹的先根和后根的遞歸算法描述/先序遍歷的遞歸算法void recur_pre_order(struct csnode *root)if(root)printf(%c,root-data);re

6、cur_pre_order(root-firstchild);recur_pre_order(root-nextbiling);/后序遍歷的遞歸算法 void recur_post_order(struct csnode *root)if(root!=null) recur_post_order(root-firstchild); recur_post_order(root-nextbiling); printf(%c,root-data); 5樹的先根的非遞歸算法預(yù)備工作之棧的設(shè)計struct csnode*base100=null;struct csnode*top=base;struct

7、 csnode* pop(struct csnode*top)/ 如果?？?，返回 error ；如果棧不空，刪除棧頂元素，用 e 返回其值，并返回 ok 。push(struct csnode*top,struct csnode*p)/將元素 p插入到棧 s 中，成為新的棧頂元素 6.樹的先根非遞歸算法void non_recur_pre_order(struct csnode *t)struct csnode *p=t; while (p!=null|!stackempty(top) while (p!=null) /遍歷左子樹 printf(%c,p-data); push(top,p);

8、 p=p-firstchild; /endwhile if(!stackempty(top) /通過下一次循環(huán)中的內(nèi)嵌while實(shí)現(xiàn)右子樹遍歷 p=pop(top); p=p-nextbiling; /endif 7樹的按層次序的非遞歸算法 /層次遍歷算法 void levelorder(struct csnode *t) struct csnode *p; struct csnode *qumaxsize; int front,rear; front=rear=-1; rear+; qurear=t; while(front!=rear) front=(front+1)%maxsize; p

9、=qufront; printf(%c ,p-data); if(p-firstchild!=null) rear=(rear+1)%maxsize; qurear=p-firstchild; if(p-nextbiling!=null) rear=(rear+1)%maxsize; qurear=p-nextbiling; 三、 運(yùn)行環(huán)境1硬件環(huán)境pc2軟件環(huán)境止上下windows xpmicrosoft visual c+6.0四、開發(fā)工具和編程語言1開發(fā)工具microsoft visual studio c+ 6.02編程語言c語言五、詳細(xì)設(shè)計1樹建立的算法實(shí)現(xiàn) void create_

10、root() root = (struct csnode*)malloc(sizeof(struct csnode); printf(請輸入根結(jié)點(diǎn)信息:); scanf(%c,&root-data); x = (struct btree*)malloc(sizeof(struct btree); x - data = root - data;voidcreate(struct csnode *temp) /構(gòu)造樹 遞歸建樹 struct csnode *t=null; struct csnode *m=null; if(temp!=null) /輸入長子信息 printf(%c, temp -

11、 data );flag=getchar();printf( 是否有孩子?(y/n)n); flag=getchar();if(flag = y | flag = y) flag=getchar(); t =(struct csnode*)malloc(sizeof(struct csnode); printf( 請輸入長子信息:n ); t-data=getchar(); temp - firstchild = t; else temp - firstchild = null; /輸入兄弟信息 printf(%c, temp - data );flag=getchar();printf(是否

12、有兄弟?(y/n)n ); flag=getchar(); if(flag = y | flag = y) flag=getchar(); m = (struct csnode*)malloc(sizeof(struct csnode); printf( 請輸入兄弟信息:n); m-data=getchar(); temp - nextbiling = m; else temp - nextbiling = null;/遞歸建立結(jié)點(diǎn) create(temp - firstchild); create(temp - nextbiling); 2樹的先根和后根的遞歸算法描述 與概要設(shè)計中的算法基本

13、一致 3樹的先根的非遞歸算法預(yù)備工作之棧的實(shí)現(xiàn)struct csnode* pop(struct csnode*top) struct csnode*t;if (top=base)return null;elset=*top;*top=null;top-;return t; push(struct csnode*top,struct csnode*p)top+;*top=p;int stackempty(struct csnode*top) if(top=base) return 1; else printf (fdhsd);return 0; 4樹的先根非遞歸算法，樹的按層次序的非遞歸算法

14、具體代碼與算法描述一致 5主函數(shù)的設(shè)計main() int cord; do printf(n 主菜單 n); printf( 1 建立樹 n); printf( 2 先根遞歸遍歷 n); printf( 3 先根非遞歸遍歷 n); printf( 4 后根遞歸遍歷 n); printf( 5 按層次非遞歸遍歷 n); printf( 6結(jié)束程序運(yùn)行 n); printf(-n); printf(請輸入您的選擇(1，2，3，4，5，6) ); scanf(%d,&cord); getchar(); switch (cord) case 1: /構(gòu)建樹 create_root(); create

15、(root); printf(樹構(gòu)建成功); printf(n); break; case 2: /先序遍歷的遞歸算法 recur_pre_order(root); printf(n); break; case 3: /先序遍歷的非遞歸算法 non_recur_pre_order(root); break;case 4: /后序遍歷的遞歸算法recur_post_order(root);printf(n); break; case 5: /按層次遍歷的非遞歸算法 levelorder(root); break; case 6:printf( 歡迎使用 n ); break;while(cord

16、6);六、調(diào)試分析 1在設(shè)實(shí)現(xiàn)樹建立算法時遇到了一些問題，當(dāng)輸入根結(jié)點(diǎn)信息后，選擇輸入其長子信息時總不能正確輸入。調(diào)試過后發(fā)現(xiàn)問題是沒有設(shè)計當(dāng)接受輸入結(jié)點(diǎn)信息后結(jié)束用的回車鍵的語句，從而導(dǎo)致判斷是否有長子時，總是判斷為無。同樣的問題，在輸入兄弟信息時遇到。之后才發(fā)現(xiàn)雖然只是小小的幾個getchar()語句在考慮不周時也是不容易發(fā)現(xiàn)錯誤的。 2在設(shè)計先根和后根的遞歸算法時，因?yàn)槌绦蚝唵我淮伪阃ㄟ^ 3在設(shè)計棧的相關(guān)操作總是出現(xiàn)問題，后來發(fā)現(xiàn)原因是。因?yàn)閷５膶?shí)現(xiàn)我采用的是指針數(shù)組，所以指向數(shù)組的應(yīng)是指向指針的指針，而我在傳遞參數(shù)卻只用了一重指針導(dǎo)致錯誤的出現(xiàn)。 4在設(shè)計樹的先根和按層次的非遞歸算法時，因?yàn)樗惴ń咏创a，所以當(dāng)棧的操作設(shè)計成功后，很快就能運(yùn)行，只是花了相當(dāng)一段時間理解這兩個算法。八、心得體會課程設(shè)計是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程.平常我們只學(xué)習(xí)課本上的知識，做一些比較小的程序，起不到運(yùn)用到實(shí)際