《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-二叉樹(總29頁).doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-二叉樹(總29頁).doc（29頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、湖南涉外經(jīng)濟(jì)學(xué)院課程設(shè)計(jì)報(bào)告課程名稱： 數(shù)據(jù)結(jié)構(gòu) 報(bào)告題目： 二叉樹的基本操作 學(xué)生姓名： 肖琳桂、康政、張小東、張帆 所在學(xué)院： 信息科學(xué)與工程學(xué)院 專業(yè)班級： 軟工本1402 學(xué)生學(xué)號： 144300211、02、14、08 指導(dǎo)教師： 李春庭 2015 年 12 月 31 日課程設(shè)計(jì)任務(wù)書報(bào)告題目二叉樹的基本操作完成時(shí)間2周學(xué)生姓名肖琳桂 康政專業(yè)班級軟工本 1402指導(dǎo)教師李春庭職稱講師總體設(shè)計(jì)要求和主要功能設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)二叉樹的創(chuàng)建以及二叉樹的遍歷（包括先序遍歷、中序遍歷、后序遍歷和層次遍歷），計(jì)算并輸出二叉樹的深度和結(jié)點(diǎn)個(gè)數(shù)，功能要求：1二叉樹以二叉鏈表存儲，結(jié)點(diǎn)數(shù)據(jù)類型采用字

2、符表示，按二叉樹的先序遍歷序列創(chuàng)建。2用文本編輯器編寫一個(gè)data.txt的文件,包含3個(gè)以上創(chuàng)建按二叉樹的先序遍歷序列(即序列中包含空樹節(jié)點(diǎn))，每個(gè)序列長度不少于10個(gè)，在運(yùn)行程序時(shí)自動載入，也可以由鍵盤輸入創(chuàng)建二叉樹。|3菜單功能：創(chuàng)建二叉樹（二級菜單說明 選擇文件中的第幾個(gè)，輸出創(chuàng)建二叉樹的深度及結(jié)點(diǎn)數(shù)，若失敗則有相應(yīng)提示），遍歷序列（顯示先序，中序，后序和層次遍歷結(jié)果），結(jié)點(diǎn)的孩子信息，退出系統(tǒng)。工作內(nèi)容及時(shí)間進(jìn)度安排第17周：周1-周2 ：立題、論證方案設(shè)計(jì)周3-周5 ：程序設(shè)計(jì)及程序編碼第18周：周1-周3 ：程序調(diào)試周4-周5 ：驗(yàn)收答辯摘 要本課程設(shè)計(jì)主要說明如何在C+編程環(huán)境

3、下實(shí)現(xiàn)二叉樹的遍歷，遍歷方式包括:二叉樹的先序遍歷、中序遍歷、后序遍歷，層次遍歷等四種遍歷方式。同時(shí)，此次課程設(shè)計(jì)還包括了求二叉樹深度和結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)的孩子信息，以及對文件的操作，用文件讀取的方式實(shí)現(xiàn)對二叉樹的建立。以通過此次課程設(shè)計(jì)，使學(xué)生充分掌握樹的基本操作，以及對線性存儲結(jié)構(gòu)的理解。同時(shí)，在對樹的遍歷的操作過程中，同樣是運(yùn)用遞歸的方式實(shí)現(xiàn)遍歷，在對樹實(shí)現(xiàn)層次操作的時(shí)候，要求用循環(huán)隊(duì)列的操作方式來實(shí)現(xiàn)層次遍歷。此次課程設(shè)計(jì)對數(shù)據(jù)結(jié)構(gòu)內(nèi)容綜合性的運(yùn)用的要求較高。關(guān)鍵詞：二叉樹，先序遍歷，中序遍歷，后序遍歷，層次遍歷，節(jié)點(diǎn)，線性存儲, 節(jié)點(diǎn)的孩子信息目 錄課程設(shè)計(jì)任務(wù)書1一、需求分析41問題描

4、述42功能要求4二、概要設(shè)計(jì)51.總體設(shè)計(jì)圖52.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)53.算法設(shè)計(jì)54.主要模塊及模塊之間的關(guān)系5三、詳細(xì)設(shè)計(jì)61.結(jié)構(gòu)體（或類）設(shè)計(jì)62. 主要模塊實(shí)現(xiàn)的流程圖63.算法設(shè)計(jì)7四、測試運(yùn)行81登錄和主界面運(yùn)行效果圖82運(yùn)行說明83. 運(yùn)行效果圖8五、結(jié)論與心得101.總體評價(jià)102.所做的工作及體會10六、程序附錄（源代碼）12七、參考文獻(xiàn)18一、需求分析1問題描述設(shè)計(jì)一個(gè)二叉樹。二叉樹形象地說即樹中每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支，它是一種重要的數(shù)據(jù)類型。可以運(yùn)用于建立家譜，公司所有的員工的職位圖，以及各種事物的分類和各種機(jī)構(gòu)的職位圖表等。二叉樹是通過建立一個(gè)鏈?zhǔn)酱鎯Y(jié)構(gòu)，達(dá)到能夠?qū)崿F(xiàn)前

5、序遍歷，中序遍歷，后序遍歷，層次遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)，二叉樹的深度。在此，二叉樹的每一個(gè)結(jié)點(diǎn)中必須包括：值域，左指針域，右指針域。我們抽象出下列問題：實(shí)現(xiàn)文件操作，運(yùn)用文件輸入流，將已經(jīng)寫好二叉樹序列的txt文本文件，加載到程序中，實(shí)現(xiàn)文件創(chuàng)建二叉樹。然后采用鏈表存儲的方式遍歷二叉樹（先序遍歷、中序遍歷、后序遍歷、層次遍歷）。層次遍歷運(yùn)用循環(huán)隊(duì)列的方法實(shí)現(xiàn)，需要重新定義隊(duì)頭和隊(duì)尾，以及隊(duì)列的最大長度，并且在屏幕上實(shí)現(xiàn)輸出顯示。2功能要求(1)用菜單的形式實(shí)現(xiàn)操作界面，提供（14）個(gè)功能選項(xiàng)，功能分別為創(chuàng)建二叉樹、遍歷序列、節(jié)點(diǎn)的孩子信息、退出系統(tǒng)。(2)創(chuàng)建二

6、叉樹。要求用文件讀取和鍵盤輸入兩種不同的方式實(shí)現(xiàn)二叉樹的創(chuàng)建。二級菜單說明，輸出創(chuàng)建二叉樹的深度及結(jié)點(diǎn)數(shù)，若失敗則有相應(yīng)提示。(3)遍歷序列。顯示先序，中序，后序和層次遍歷結(jié)果。先序遍歷、中序遍歷、后序遍歷用遞歸的方法實(shí)現(xiàn)遍歷。層次遍歷，用循環(huán)隊(duì)列的方法實(shí)現(xiàn)。(4)每次實(shí)現(xiàn)一項(xiàng)操作之后，要有相應(yīng)的提示返回菜單。二、概要設(shè)計(jì)1.總體設(shè)計(jì)圖主菜單遍歷序列創(chuàng)建二叉樹節(jié)點(diǎn)的孩子信息退出系統(tǒng)鍵盤輸入文件輸入中序遍歷后序遍歷層次遍歷先序遍歷2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 數(shù)據(jù)元素為字符，邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)，存儲結(jié)構(gòu)為二叉鏈?zhǔn)酱鎯?，系統(tǒng)操作的數(shù)據(jù)元素主要是創(chuàng)建一個(gè)二叉樹，遍歷序列。3.算法設(shè)計(jì)本系統(tǒng)主要用到的算法有先序遍

7、歷、中序遍歷、后序遍歷、層次遍歷、創(chuàng)建二叉樹和查找節(jié)點(diǎn)。從子菜單界面只能返回到主菜單界面，而不是退出程序。4.主要模塊及模塊之間的關(guān)系 運(yùn)行程序后直接進(jìn)入“菜單主界面”模塊，菜單顯示分為4個(gè)模塊，（14）分別為創(chuàng)建二叉樹、遍歷序列、節(jié)點(diǎn)的孩子信息、退出系統(tǒng)。主界面中的各個(gè)模塊都是獨(dú)立運(yùn)行，每完成一項(xiàng)操作后，返回主菜單模塊。通過相應(yīng)定義的函數(shù)（外部接口）實(shí)現(xiàn)，內(nèi)部數(shù)據(jù)的改變由模塊內(nèi)部完成。三、詳細(xì)設(shè)計(jì)1.結(jié)構(gòu)體（或類）設(shè)計(jì)typedef char TElemType;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchi

8、ld;BiTNode,*BiTree;2. 主要模塊實(shí)現(xiàn)的流程圖開始主菜單界面輸入選擇（14） Case=sel？退出系統(tǒng)創(chuàng)建二叉樹遍歷序列中序遍歷層次遍歷先序遍歷后序遍歷結(jié)點(diǎn)的孩子信息Case=1Case=2Case=4Case=33.算法設(shè)計(jì)先序遍歷：void PreOrderTraverse(BiTree T) if(T) coutdate;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 中序遍歷：void InOrderTraver(BiTree T) if(T) InOrderTraver(T-lchild);coutda

9、te;InOrderTraver(T-rchild); 后序遍歷：void PostOrderTraver(BiTree T) if(T) PostOrderTraver(T-lchild);PostOrderTraver(T-rchild);coutdate; 層次遍歷： void ccbl(BiTNode *b) BiTNode *p; BiTNode *qMaxSize; int qm,h; qm=h=-1; h+; qh=b; while(qm != h) qm=(qm+1)%MaxSize; p=qqm; printf(%c ,p-date); if(p-lchild!=NULL)

10、h=(h+1)%MaxSize; qh=p-lchild; if(p-rchild!=NULL) h=(h+1)%MaxSize; qh=p-rchild; 四、測試運(yùn)行1登錄和主界面運(yùn)行效果圖2運(yùn)行說明主程序運(yùn)行后，直接到菜單選擇界面。其中有(14個(gè)選項(xiàng)可以選擇)1.創(chuàng)建二叉樹 2.遍歷序列 3.節(jié)點(diǎn)的孩子信息 4.退出系統(tǒng)。除退出以外,每個(gè)功能模塊運(yùn)行完后，返回到主菜單界面，每個(gè)界面相互獨(dú)立。3. 運(yùn)行效果圖表 學(xué)生情況統(tǒng)計(jì)表序號姓名性別出生日期學(xué)號專業(yè)聯(lián)系電話備注1康政男1994.12144300202軟件工程 15717488160組長2肖琳桂男1996.08144300211軟件工程

11、 157175144943張小東男1994.07144300214軟件工程 4張帆 男1995.08144300208軟件工程五、結(jié)論與心得1.總體評價(jià)在此次的課程設(shè)計(jì)中，由于不夠細(xì)心，在程序設(shè)計(jì)中犯了一些錯(cuò)誤，花了挺多的時(shí)間。但是經(jīng)過一番思考并且在老師的幫助下，找到了導(dǎo)致程序錯(cuò)誤的原因，經(jīng)過幾次修改和調(diào)試，程序能正常運(yùn)行，并且能夠完成課程設(shè)計(jì)任務(wù)中的大部分功能。同時(shí)在此次的課程設(shè)計(jì)中讓我更深刻的了解了二叉樹的基本操作，增加了對專業(yè)只是學(xué)習(xí)的興趣。我想在以后的學(xué)習(xí)中，我們會繼續(xù)努力，希望在計(jì)算機(jī)方面有好的成績，也感謝老師給我們這次課程設(shè)計(jì)的機(jī)會，讓我們認(rèn)識到了自身的不足，讓我們能夠不斷地完善自

12、己!2. 所做的工作及體會肖琳桂：編寫程序和課程設(shè)計(jì)報(bào)告。課程設(shè)計(jì)中我主要擔(dān)任程序設(shè)計(jì)的編寫和設(shè)計(jì)報(bào)告的編寫工作，經(jīng)過兩個(gè)星期的上機(jī)實(shí)踐學(xué)習(xí)，使我對數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識和理解，也知道了要想學(xué)好它要重在實(shí)踐，要通過不斷的上機(jī)操作才能更好地學(xué)習(xí)它。通過實(shí)踐我發(fā)現(xiàn)我的很多不足之處，然感覺理論上已經(jīng)掌握，但在運(yùn)用到實(shí)踐的過程中仍有意想不到的困惑，因?yàn)樽约簩χR點(diǎn)的掌握不夠熟悉，但通過學(xué)習(xí)有很大改進(jìn)。在這次課程設(shè)計(jì)中使我知道了二又樹的先序、中序、后序、層次遍歷。同時(shí)，還包括了求二叉樹深度和結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)的孩子信息，以及對文件的操作，用文件讀取的方式實(shí)現(xiàn)對二叉樹的建立。充分掌握樹的基本操作，以及對線

13、性存儲結(jié)構(gòu)的理解。也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在設(shè)計(jì)過程中，和同學(xué)們相互探討，相互學(xué)習(xí)，相互監(jiān)督。我學(xué)會了運(yùn)籌帷幌，學(xué)會了寬容，學(xué)會了理解，也學(xué)會了做人與處世，這次課程設(shè)計(jì)對找來說受益良多。在今后的日子里，我會認(rèn)真對待每一件事情，爭取做到最好，努力將知識與實(shí)踐相結(jié)合，不斷鞏固，加深所學(xué)的知識，做到學(xué)以致用。另外感謝老師的細(xì)心教導(dǎo)，以及同學(xué)們的幫助。康政：編寫程序和課程設(shè)計(jì)報(bào)告。我在小組中做了編寫程序和撰寫報(bào)告的工作。在編寫程序時(shí)，遇到很多困難，例如缺少聲明，調(diào)用函數(shù)錯(cuò)誤等等。通過網(wǎng)上搜查，查詢資料以及老師的指點(diǎn)幫助，完成了很多任務(wù)。作為基礎(chǔ)不是很好的學(xué)生，我在克服自己知識不足的過程中也在努力學(xué)習(xí)新的知識，運(yùn)用不同的原理編寫出不同的算法。也學(xué)習(xí)到，算法不能盲目抄襲，很多東西是不同的，必須通過自己的思考和努力的鉆研才能寫出一套完整的代碼，不可心急，越是急越不可能精細(xì)的完成任務(wù)