線索二叉樹課程設(shè)計(jì)說明書模板范本

年4月19日線索二叉樹課程設(shè)計(jì)說明書模板文檔僅供參考數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書課程名稱:數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)課程代碼:6014389題目:線索二叉樹的應(yīng)用年級(jí)/專業(yè)/班:級(jí)軟件1班學(xué)生姓名:學(xué)號(hào):31開始時(shí)間:年12月9日完成時(shí)間:年12月23日課程設(shè)計(jì)成績(jī)：學(xué)習(xí)態(tài)度及平時(shí)成績(jī)（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5）說明書（計(jì)算書、圖紙、分析報(bào)告）撰寫質(zhì)量（45）總分（100）指導(dǎo)教師簽名：年月日摘要首先是對(duì)需求分析的簡(jiǎn)要闡述，說明系統(tǒng)要完成的任務(wù)和相應(yīng)的分析，并給出測(cè)試數(shù)據(jù)。其次是概要設(shè)計(jì)，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關(guān)系，以及ADT描述。然后是詳細(xì)設(shè)計(jì)，描述實(shí)現(xiàn)概要設(shè)計(jì)中定義的基本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實(shí)現(xiàn)。再次是對(duì)系統(tǒng)的調(diào)試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測(cè)試的數(shù)據(jù)和結(jié)果的分析，最后是對(duì)本次課程設(shè)計(jì)的結(jié)論。關(guān)鍵詞：線索化；先序遍歷；中序遍歷；后續(xù)遍歷

引言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，在計(jì)算機(jī)領(lǐng)域應(yīng)用廣泛，計(jì)算機(jī)離不開數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)為了能使我們掌握所學(xué)習(xí)的知識(shí)并有應(yīng)用到實(shí)際的設(shè)計(jì)中的能力，對(duì)于掌握這門課程的學(xué)習(xí)方法有極大的意義。本課程設(shè)計(jì)的題目為“線索二叉樹的應(yīng)用”，完成將二叉樹轉(zhuǎn)化成線索二叉樹，采用前序、中序或后序線索二叉樹的操作。本課程設(shè)計(jì)采用的編程環(huán)境為MicrosoftVisualStdio。

TOC\o"1-2"\h\z目錄TOC\o"1-2"\h\z1需求分析 32開發(fā)及運(yùn)行平臺(tái) 43概要設(shè)計(jì) 54詳細(xì)設(shè)計(jì) 75調(diào)試分析 126測(cè)試結(jié)果 137結(jié)論 18致謝 19參考文獻(xiàn) 20附錄 21

1、需求分析為了能更熟練精準(zhǔn)的掌握二叉樹的各種算法和操作，同時(shí)也為了開拓視野，綜合運(yùn)用所學(xué)的知識(shí)。為此，需要將二叉樹轉(zhuǎn)化成線索二叉樹，采用前序、中序或后序線索二叉樹，以實(shí)現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索等。1.1任務(wù)與分析中次系統(tǒng)要實(shí)現(xiàn)對(duì)二叉樹的建立，以及線索化該二叉樹，同時(shí)實(shí)現(xiàn)對(duì)其先序、中序、后序線索話的并輸出結(jié)果。1.2測(cè)試數(shù)據(jù)表1：入的二叉樹結(jié)點(diǎn)序號(hào)和數(shù)據(jù)結(jié)點(diǎn)序號(hào)數(shù)據(jù)111222333444555666777888999

2開發(fā)及運(yùn)行平臺(tái)開發(fā)平臺(tái)：MicrosoftVisualStudio運(yùn)行平臺(tái)：WindowsXP//7

3概要設(shè)計(jì)3.1ADT描述ADTBiTree{數(shù)據(jù)對(duì)象：D={“樹節(jié)點(diǎn)”}；數(shù)據(jù)關(guān)系：R＝{H}若D=∮為空，則R=∮,Tree為空樹；若D僅有一個(gè)數(shù)據(jù)元素，則R=∮；否則R={H}詳細(xì)描述如下：D中存在唯一的稱之為根的節(jié)點(diǎn)root，它在關(guān)系H下無前驅(qū)；若D-{root}≠∮，則存在對(duì)根以外剩余元素的一個(gè)劃分D1、D2，Dm（m>0），并對(duì)任意j≠k（1≦j≦m，1≦k≦m）有Dj∩Dk=∮；且對(duì)任意i（1≦i≦m）唯一存在數(shù)據(jù)元素xi∈Di，有二元關(guān)系<root,xi>∈H。這里描述的是從總節(jié)點(diǎn)到各個(gè)子樹根節(jié)點(diǎn)xi的邊。對(duì)應(yīng)于D-{root}的劃分，關(guān)系集H-{<root,x1>，<root,x2>，<root,xm>}也有唯一的劃分H1、H2Hm(m>0)，而且對(duì)任意的j≠k（1≦j≦m，1≦k≦m）有Hj∩Hk=∮，對(duì)任意的i（1≦i≦m），Hi是Di上的二元關(guān)系，則（Di，{H}）是一顆樹，且是root的子樹?；静僮鳎簐oidcreat();//創(chuàng)立一個(gè)二叉樹。voidinorder();//中序便利。voidThTree::threpreorder();//先序遍歷二叉樹。voidThTree::threinorder();//中序遍歷二叉樹。voidThTree::threpostorder();//后序遍歷二叉樹。voidThTree::destroy();//刪除線索二叉樹。intmain();//主函數(shù)。}3.2程序模塊結(jié)構(gòu)圖2程序模塊結(jié)構(gòu)結(jié)構(gòu)體定義書的結(jié)構(gòu)體定義如下：structThreNode//定義結(jié)點(diǎn)結(jié)構(gòu)體{ ElemTypedata;ThreNode*lch; ThreNode*rch; intltag,rtag;};3.3各功能模塊新建模塊:voidThTree::creat()新建二叉樹并儲(chǔ)存。樹類模塊:voidThTree()定義書的結(jié)點(diǎn)，孩子以及各成員函數(shù)。先序遍歷模塊:voidThTree::threpreorder()對(duì)樹進(jìn)行先序線索遍歷。中序遍歷模塊:voidThTree::threinorder()對(duì)樹進(jìn)行中序線索遍歷。后序遍歷模塊:voidThTree::threpostorder()對(duì)樹進(jìn)行后序線索遍歷。刪除模塊:voidThTree::destroy()：刪除所有節(jié)點(diǎn)。

4詳細(xì)設(shè)計(jì)4.1結(jié)構(gòu)體定義樹的結(jié)構(gòu)體定義如下：structThreNode//定義結(jié)點(diǎn)結(jié)構(gòu)體{ ThreTypedata;ThreNode*lch; ThreNode*rch; intltag,rtag;};4.2初始化構(gòu)造函數(shù)初始化變量，定義雙親結(jié)點(diǎn)和左右標(biāo)志域以及根結(jié)點(diǎn)：voidThTree::creat()//建立二叉樹{ ThreNode*q,*s[20];ElemTypex;inti,j; cout<<"\n請(qǐng)按二叉樹的層序自上而下自左至右順序組織數(shù)據(jù)"<<endl; cout<<"\n每次輸入結(jié)點(diǎn)的序號(hào)和數(shù)據(jù)，假設(shè)根結(jié)點(diǎn)值是11；"<<endl; cout<<"\n那么輸入應(yīng)該是：111"<<endl; cout<<"\ni,x="; cin>>i>>x; while(i!=0&&x!=0) { q=newThreNode;//產(chǎn)生一個(gè)接點(diǎn) q->data=x;q->lch=NULL;q->rch=NULL; q->ltag=0;q->rtag=0;//左右標(biāo)志域 s[i]=q; if(i==1)root=q;//q為根接點(diǎn) else{j=i/2; if((i%2)==0)s[j]->lch=q;elses[j]->rch=q;//j為雙親結(jié)點(diǎn)編號(hào) } cout<<"\ni,x=";cin>>i>>x;}}4.3新建操作voidThTree::creat()//建立二叉樹{ ThreNode*q,*s[20];ElemTypex;inti,j; cout<<"\n請(qǐng)按二叉樹的層序自上而下自左至右順序組織數(shù)據(jù)"<<endl; cout<<"\n每次輸入結(jié)點(diǎn)的序號(hào)和數(shù)據(jù)，假設(shè)根結(jié)點(diǎn)值是11；"<<endl; cout<<"\n那么輸入應(yīng)該是：111"<<endl; cout<<"\ni,x="; cin>>i>>x; while(i!=0&&x!=0) { q=newThreNode;//產(chǎn)生一個(gè)接點(diǎn) q->data=x;q->lch=NULL;q->rch=NULL; q->ltag=0;q->rtag=0;//左右標(biāo)志域 s[i]=q; if(i==1)root=q;//q為根接點(diǎn) else{j=i/2; if((i%2)==0)s[j]->lch=q;elses[j]->rch=q;//j為雙親結(jié)點(diǎn)編號(hào) } cout<<"\ni,x=";cin>>i>>x;}}voidThTree::threpreorder(ThreNode*p,ThreNode*pre)//先根線索化二叉樹{if(p!=NULL){cout<<p->data<<"";if(p->lch==NULL){p->lch=pre;p->ltag=1; } pre=p; if(p->ltag==0)threpreorder(p->lch,pre); threpreorder(p->rch,pre); 4.4、錄入信息intmain(){ intk;ThTreeroot0; do{cout<<"\n\n"; cout<<"\n\n1.建立二叉樹"; cout<<"\n\n2.中序遞歸線索二叉樹"; cout<<"\n\n3.先序線索化二叉樹"; cout<<"\n\n4.后續(xù)線索化二叉樹"; cout<<"\n\n5.結(jié)束程序運(yùn)行"; cout<<"\n\n請(qǐng)輸入您的選擇:";cin>>k; switch(k)}4.5先序遍歷線索化操作voidThTree::threpreorder(ThreNode*p,ThreNode*pre)//先根線索化二叉樹{if(p!=NULL){cout<<p->data<<"";if(p->lch==NULL){p->lch=pre;p->ltag=1; } pre=p; if(p->ltag==0)threpreorder(p->lch,pre); threpreorder(p->rch,pre);}}4.6中序遍歷線索化操作voidThTree::threinorder(ThreNode*p,ThreNode*pre)//中根線索化二叉樹{ if(p!=NULL) { threinorder(p->lch,pre); {p->lch=pre; p->ltag=1; } if(pre!=0&&pre->rch==0) { pre->rch=p;pre->rtag=1; } pre=p; threinorder(p->rch,pre); }}4.7后續(xù)遍歷線索化操作voidThTree::threpostorder(ThreNode*p,ThreNode*pre)//后根線索化二叉樹{ if(p!=NULL) { threpostorder(p->lch,pre);threpostorder(p->rch,pre); cout<<p->data<<""; if(p->lch==NULL){p->lch=pre;p->ltag=1;} pre=p; }}4.8主函數(shù)intmain(){ intk;ThTreeroot0; do{cout<<"\n\n"; cout<<"\n\n1.建立二叉樹"; cout<<"\n\n2.中序遞歸線索二叉樹"; cout<<"\n\n3.先序線索化二叉樹"; cout<<"\n\n4.后續(xù)線索化二叉樹"; cout<<"\n\n5.結(jié)束程序運(yùn)行"; cout<<"\n\n請(qǐng)輸入您的選擇:";cin>>k; switch(k) {case1:{cout<<"\n建立二叉樹："; root0.creat(); }break; case2:{cout<<"\n中序遞歸線索二叉樹的結(jié)果："; root0.threinorder(); }break; case3:{cout<<"\n先序遞歸線索二叉樹的結(jié)果："; root0.threpreorder(); }break; case4:{cout<<"\n后續(xù)遞歸線索化二叉樹的結(jié)果："; root0.threpostorder(); }break; } }while(k>=0&&k<5); _getch(); return0;}5調(diào)試分析5.1測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)見表1.5.2調(diào)試問題在測(cè)試過程中沒有給測(cè)試者提供相關(guān)的錄入信息要求，導(dǎo)致錄入要求不合格，程序不能正常運(yùn)行，經(jīng)過添加了錄入信息提示之后就解決了這個(gè)問題。5.3算法時(shí)間復(fù)雜度錄入：時(shí)間復(fù)雜度為O(n);先根線索化二叉樹:時(shí)間復(fù)雜度為O(n);中根線索化二叉樹:時(shí)間復(fù)雜度為O(n);后根線索化二叉樹:時(shí)間復(fù)雜度為O(n);刪除結(jié)點(diǎn):時(shí)間復(fù)雜度為O(n)；5.4經(jīng)驗(yàn)和體會(huì)在本次課程設(shè)計(jì)中主要是對(duì)圖的數(shù)據(jù)結(jié)構(gòu)操作，所有剛開始對(duì)知識(shí)不是很熟悉操作起來有一定難度，容易在程序的關(guān)鍵地方但經(jīng)過翻閱教材能較好的解決問題。

6測(cè)試結(jié)果6.1錄入信息圖3錄入信息界面

6.2新建模塊圖5查詢景點(diǎn)信息界面

6.3中序遞歸線索化模塊圖6中序遞歸線索化界面6.4先序遞歸線索化模塊圖7先序遞歸線索化界面

6.5后序遞歸線索化模塊圖8后序遞歸線索化界面

結(jié)論本次課程設(shè)計(jì)“二叉樹的線索化”按照任務(wù)書相應(yīng)的要求成功的完成了任務(wù)，由于本課程設(shè)計(jì)涉及先序、后序、中序的線索化，以及相應(yīng)的相關(guān)插入刪除的操作，因此對(duì)算法的設(shè)計(jì)以及相關(guān)函數(shù)的調(diào)用要求很高，需要經(jīng)過重復(fù)的查看相關(guān)書籍才能完成。

致謝在本次課程設(shè)計(jì)過程中，首先感謝輔導(dǎo)老師周立章，在數(shù)據(jù)結(jié)構(gòu)課堂上為課程設(shè)計(jì)需要的前期知識(shí)打下了基礎(chǔ)，在課程設(shè)計(jì)過程中抽出休息時(shí)間來做相應(yīng)的課程設(shè)計(jì)指導(dǎo)。同時(shí)在這次課程設(shè)計(jì)中，也要感謝許多樂意同學(xué)對(duì)我不懂的地方的指導(dǎo)和耐心講解

參考文獻(xiàn)[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京.清華大學(xué)出版社出版。[2]嚴(yán)蔚敏，吳偉民.