數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、陽(yáng)韻2孽瑰?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計(jì)說(shuō)明書(shū)二叉平衡數(shù)算法實(shí)現(xiàn)班級(jí)：計(jì)科1703組別:指導(dǎo)老師：彭代文完成時(shí)間：組長(zhǎng)：學(xué)號(hào):組員1:學(xué)號(hào):組員2:學(xué)號(hào):成績(jī):十七2021.6.20目錄1 .課題設(shè)計(jì)任務(wù)12 .任務(wù)分析13 .概要設(shè)計(jì)23.1 功能模塊的劃分23.1.1 主功能模塊23.1.2 創(chuàng)立樹(shù)模塊23.1.3 遍歷機(jī)t模塊23.2 功能函數(shù)調(diào)用圖24 .詳細(xì)設(shè)計(jì)34.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：34.2 各模塊流程圖及算法：44.2.1 主函數(shù)44.2.2 輸入二叉樹(shù)54.2.3 非遞歸遍歷54.2.4 遞歸遍歷74.3 算法的效率分析：85 .測(cè)試96 .課程設(shè)計(jì)心得106.1 改良方案106.2 設(shè)

2、計(jì)心得107 .參考文獻(xiàn)118 .附錄121 .課題設(shè)計(jì)任務(wù)現(xiàn)實(shí)世界層次化的數(shù)據(jù)模型中,數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系紛繁復(fù)雜.其中很多關(guān)系無(wú)法使用簡(jiǎn)單的線性結(jié)構(gòu)表示清楚,比方祖先與后代的關(guān)系、整體與局部的關(guān)系等.于是人們借鑒自然界中樹(shù)的形象創(chuàng)造了一種強(qiáng)大的非線性結(jié)構(gòu)一一樹(shù).樹(shù)形結(jié)構(gòu)的具體形式有很多種,其中最常用的就是二叉樹(shù).針對(duì)這樣的問(wèn)題,我選擇了二叉樹(shù)的操作作為我的課程設(shè)計(jì)主題,編寫(xiě)程序,實(shí)現(xiàn)對(duì)二叉樹(shù)的遍歷.在本次課程設(shè)計(jì)中,二叉樹(shù)的建立使用了遞歸算法；在前序、中序和后續(xù)遍歷的算法中那么同時(shí)使用了遞歸與非遞歸的算法,即在這些遍歷算法的實(shí)現(xiàn)中使用了棧結(jié)構(gòu)與隊(duì)列結(jié)構(gòu),提供了6種不同的遍歷方式,供使用者選

3、擇.同時(shí),該程序具有輸出層序遍歷的功能,層序遍歷模塊使用了非遞歸算法.該程序根本實(shí)現(xiàn)了二叉樹(shù)的遍歷,對(duì)于遞歸與非遞歸算法,我們應(yīng)從實(shí)際應(yīng)用中體驗(yàn)這些算法的優(yōu)越性.編程實(shí)現(xiàn)二叉樹(shù)的建立,先序、中序、后序遞歸和非遞歸方法、層序遍歷,二叉樹(shù)的高度、統(tǒng)計(jì)葉子節(jié)點(diǎn)的數(shù)目、統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)、輸出結(jié)點(diǎn)的最大值、輸出結(jié)點(diǎn)所在的層數(shù)、打印輸出二叉樹(shù)的單鏈表形式.2 .任務(wù)分析數(shù)據(jù)存儲(chǔ)：采用二叉鏈表存儲(chǔ)功能設(shè)計(jì)：首先,創(chuàng)立二叉樹(shù)；其次打印二叉樹(shù)：假設(shè)二叉樹(shù)為空,那么空操作；否那么依次打印右子樹(shù)、打印根結(jié)點(diǎn)、打印左子樹(shù)；最后,要實(shí)現(xiàn)二叉樹(shù)的一些根本運(yùn)算,包括先序遍歷、中序遍歷、后序遍歷、計(jì)算結(jié)點(diǎn)數(shù)、葉子節(jié)點(diǎn)數(shù)、計(jì)算結(jié)點(diǎn)

4、所在層等操作.具體分別是先序遍歷二叉樹(shù)：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的先序遍歷,先訪問(wèn)根結(jié)點(diǎn),在依次訪問(wèn)左右子樹(shù)；中序遍歷二叉樹(shù)：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的中序遍歷,先訪問(wèn)左子樹(shù),再訪問(wèn)根結(jié)點(diǎn),最后訪問(wèn)右子樹(shù)；后序遍歷二叉樹(shù)：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的后序遍歷,先訪問(wèn)左子樹(shù),再訪問(wèn)右子樹(shù),最后訪問(wèn)根結(jié)點(diǎn)；計(jì)算二叉樹(shù)葉子數(shù)：假設(shè)二叉樹(shù)為空,返回0；假設(shè)只有根結(jié)點(diǎn),返回1；否那么,返回左子樹(shù)+右子樹(shù)；計(jì)算二叉樹(shù)結(jié)點(diǎn)數(shù)：假設(shè)二叉樹(shù)為空,返回0；假設(shè)只有根結(jié)點(diǎn),返回1；否那么,返回左子樹(shù)+右子樹(shù)+1.運(yùn)用手動(dòng)鍵盤(pán)輸入,將二叉樹(shù)序列按先序的順序,從鍵盤(pán)輸入到字符數(shù)組中,實(shí)現(xiàn)二叉樹(shù)的創(chuàng)立.運(yùn)用遞歸的方式,計(jì)算

5、出二叉樹(shù)的節(jié)點(diǎn)的個(gè)數(shù)以及二叉樹(shù)的深度,并且在屏幕輸出顯示等等操作比擬根底.遍歷二叉樹(shù)分為四種方式,先序遍歷、中序遍歷、后序遍歷、層次遍歷.其中先序遍歷、中序遍歷和后序遍歷都用遞歸與非遞歸的方法實(shí)現(xiàn),采用鏈表存儲(chǔ)的方式,并在屏幕輸出結(jié)果.層次遍歷運(yùn)用循環(huán)隊(duì)列的方法實(shí)現(xiàn),需要重新定義隊(duì)頭和隊(duì)尾,以及隊(duì)列的最大長(zhǎng)度,并且在屏幕上實(shí)現(xiàn)輸出顯示.第一次成功創(chuàng)立二叉樹(shù)之后,如果想要重新創(chuàng)立,必須將已經(jīng)創(chuàng)立的二叉樹(shù)實(shí)現(xiàn)刪除,并且釋放內(nèi)存空間,實(shí)現(xiàn)第二次重新創(chuàng)立.用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)對(duì)二叉排序樹(shù)的的創(chuàng)立,各種遍歷,樹(shù)高、節(jié)點(diǎn)數(shù)量等根本操作,在整個(gè)程序中可以將程序分為四大代碼塊,首先菜單代碼塊；其次是根底代碼塊,

6、分別包括棧操作代碼塊和隊(duì)列操作代碼塊；再其次是主體代碼塊即各種樹(shù)操作的函數(shù)代碼塊,最后是輸出操作代碼塊.VisualStudio2021編寫(xiě),可以實(shí)現(xiàn)對(duì)二叉樹(shù)的多種方式的創(chuàng)立、采用遞歸和非遞歸等兩種方式先序、中序、后序進(jìn)行遍歷下面是具體介紹.3 .概要設(shè)計(jì)3.1 功能模塊的劃分3.1.1 主功能模塊通過(guò)合理的界面設(shè)計(jì),根據(jù)提示信息,使用者可以方便快捷地運(yùn)行本程序來(lái)完成創(chuàng)建、遍歷二叉樹(shù)、查找結(jié)點(diǎn)等操作.界面美觀,人性化,程序智能,平安性高.3.1.2 創(chuàng)立樹(shù)模塊當(dāng)進(jìn)入程序運(yùn)行界面后,根據(jù)提示輸入需要建立的二叉樹(shù),建立完二叉樹(shù)后自動(dòng)進(jìn)入下一個(gè)功能模塊.3.1.3 遍歷樹(shù)模塊實(shí)現(xiàn)對(duì)該二叉樹(shù)的先序遞歸

7、遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸遍歷、層序非遞歸遍歷等方式的遍歷操作,并輸出各遍歷序列.3.2 功能函數(shù)調(diào)用圖根到節(jié)路能印點(diǎn)子的功打結(jié)葉點(diǎn)徑根到節(jié)路數(shù)印點(diǎn)子的前打結(jié)葉點(diǎn)徑雙數(shù)找函尋親銷毀釋放二叉樹(shù)輸出二叉樹(shù)計(jì)算二叉樹(shù)高度先序遞歸遍歷算法中序遞歸遍歷算法后序遞歸遍歷算法輸出葉子結(jié)點(diǎn)輸出葉子結(jié)點(diǎn)個(gè)數(shù)輸出結(jié)點(diǎn)個(gè)數(shù)輸出結(jié)點(diǎn)的最大值輸出結(jié)點(diǎn)在第幾層初始化棧銷毀棧圖4-1調(diào)用關(guān)系圖其他功能均為單個(gè)函數(shù)實(shí)現(xiàn),不做流程描述4 .詳細(xì)設(shè)計(jì)4.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：BTNode*LchildNode(BTNode*p)/返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針BTNode*Rchild

8、Node(BTNode*p)/返回*p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針voidCreateBTree(BTNode*&b,char*str/創(chuàng)立樹(shù)intFindNode(BTNode*b,ElemTypex)/查找結(jié)點(diǎn)是否存在voidInitQueue(SqQueue*&q)/創(chuàng)立隊(duì)列boolQueueEmpty(SqQueue*q)/判斷隊(duì)列是否為空boolenQueue(SqQueue*q,BTNode*e)/進(jìn)隊(duì)歹UbooldeQueue(SqQueue*&q,BTNode*&e)/出隊(duì)歹UvoidDestoryBTree(BTNode*&b)/voidDis

9、pBTree(BTNode*b)/intBTHeight(BTNode*b)/voidPreOrder(BTNode*b)/voidInOrder(BTNode*b)/voidPostOrder(BTNode*b)/voidDispLeaf(BTNode*b)/intlistleaf(BTNode*b)/intlistnode(BTNode*b)/intmaxnode(BTNode*b)/intlistfloor(BTNode*b,charx)/voidInitStack(SqStack*&s)/voidDestroyStack(SqStack*&s)/boolStackEmp

10、ty(SqStack*s)/判斷棧是否為空boolPush(SqStack*&s,BTNode*e)/進(jìn)棧boolPop(SqStack*&s,BTNode*&e)/出棧boolGetTop(SqStack*s,BTNode*&e)/取棧頂元素voidPreOrder1(BTNode*b)/先序非遞歸遍歷算法voidInOrder1(BTNode*b)/中序非遞歸遍歷算法voidPostOrder1(BTNode*b)/后序非遞歸遍歷算法voidLevelOrder(BTNode*b)/層次遍歷算法4.2 各模塊流程圖及算法：4.2.1 主函數(shù)intmain()

11、system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序?yàn)槎鏄?shù)的操作"<<endl;charstr20;cout<<"請(qǐng)輸入你的二叉樹(shù)"<<endl;cin.getline(str,20);CreateBTree(b,str);cout<<"創(chuàng)立成功!"<<endl;cout<<"是否繼續(xù)操作繼續(xù)操作請(qǐng)輸入1,否那么輸入0&qu

12、ot;<<endl;cin>>i;while(i!=0)cout<<""<<endl;cout<<"-輸入【0】結(jié)束程序-"<<endl;cout<<"-輸入【1】輸出二叉樹(shù)-"<<endl;cout<<"-輸入【2】計(jì)算二叉樹(shù)高度-"<<endl;cout<<"-輸入【3】查找節(jié)點(diǎn)是否存在-"<<endl;cout<<"-輸入【4

13、】輸出所有葉子結(jié)點(diǎn)-"<<endl;cout<<"-輸入【5】計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)-"<<endl;cout<<"-輸入【6】前序遍歷輸出二叉樹(shù)-"<<endl;cout<<"-輸入【7】中序遍歷輸出二叉樹(shù)-"<<endl;cout<<"-輸入【8】后序遍歷輸出二叉樹(shù)-"<<endl;cout<<"-輸入【9】計(jì)算結(jié)點(diǎn)個(gè)數(shù)-"<<endl;cout<&l

14、t;"-輸入【10】輸出該樹(shù)中結(jié)點(diǎn)最大值-"<<endl;cout<<"-輸入【11】輸出樹(shù)中結(jié)點(diǎn)值為x的層-"<<endl;cout<<"-輸入【12】先序非遞歸算法-"<<endl;cout<<"-輸入【13】中序非遞歸算法-"<<endl;cout<<"-輸入【14】后序非遞歸算法-"<<endl;cout<<"-輸入【15】層次遍歷隊(duì)列算法-"<

15、;<endl;cout<<""<<endl;cout<<">>請(qǐng)輸入你的操作<<"<<endl;cin>>i;/以下為功能選擇相應(yīng)的函數(shù),比擬繁雜,在此不做展示)4.2.2 輸入二叉樹(shù)voidCreateBTree(BTNode*&b,char*str)(/創(chuàng)立二叉鏈intMaxSize1=50;BTNode*StMaxSize,*p=NULL;inttop=-1,k=0,j=0;charch=strj;b=NULL;while(ch!='0'

16、;)/str未掃描完時(shí)循環(huán)switch(ch)case'(':top+;Sttop=p;k=1;break;/可能有左孩子結(jié)點(diǎn),進(jìn)棧case')':top-;break;case',':k=2;break;/后面為右孩子default:p=(BTNode*)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1: Sttop->lchild=p;break;case 2: Sttop->rc

17、hild=p;break;)j+;ch=strj;/繼續(xù)掃描str)4.2.3 非遞歸遍歷voidPreOrder1(BTNode*b)/先序非遞歸遍歷算法BTNode*p;SqStack*st;InitStack(st);Push(st,b);while(!StackEmpty(st)Pop(st,p);printf("%c",p->data);if(p->rchild!=NULL)Push(st,p->rchild);if(p->lchild!=NULL)Push(st,p->lchild);printf("n");De

18、stroyStack(st);/定義一個(gè)順序棧指針st/初始化棧st/根節(jié)點(diǎn)進(jìn)棧/棧不為空時(shí)循環(huán)/退棧節(jié)點(diǎn)p并訪問(wèn)它/訪問(wèn)節(jié)點(diǎn)p/有右孩子時(shí)將其進(jìn)棧/有左孩子時(shí)將其進(jìn)棧/銷毀棧/中序非遞歸遍歷/中序非遞歸遍歷算法voidInOrder1(BTNode*b)BTNode*p;SqStack*st;/定義一個(gè)順序棧指針stInitStack(st);/初始化棧stif(b!=NULL)p=b;while(!StackEmpty(st)|p!=NULL)while(p!=NULL)Push(st,p);p=p->lchild;if(!StackEmpty(st)/Pop(st,p);print

19、f("%c",p->data);p=p->rchild;/掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧/節(jié)點(diǎn)p進(jìn)棧/移動(dòng)到左孩子假設(shè)棧不空/出棧節(jié)點(diǎn)p/訪問(wèn)節(jié)點(diǎn)p/轉(zhuǎn)向處理其右子樹(shù)printf("n");DestroyStack(st);/銷毀棧voidPostOrder1(BTNode*b)(BTNode*p,*r;boolflag;SqStack*st;InitStack(st);p=b;do(while(p!=NULL)(Push(st,p);p=p->lchild;r=NULL;flag=true;while(!StackEmpty(st)&

20、amp;&flag)(GetTop(st,p);if(p->rchild=r)(printf("%c",p->data);Pop(st,p);r=p;else(p=p->rchild;flag=false;while(!StackEmpty(st);printf("n");DestroyStack(st);/后序非遞歸遍歷算法/定義一個(gè)順序棧指針st/初始化棧st/掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧/節(jié)點(diǎn)p進(jìn)棧/移動(dòng)到左孩子/r指向剛剛訪問(wèn)的節(jié)點(diǎn),初始時(shí)為空/flag為真表示正在處理?xiàng)ｍ敼?jié)點(diǎn)/取出當(dāng)前的棧頂節(jié)點(diǎn)p/假設(shè)節(jié)點(diǎn)p的右孩子

21、為空或者為剛剛訪問(wèn)過(guò)的節(jié)點(diǎn)/訪問(wèn)節(jié)點(diǎn)p/r指向剛訪問(wèn)過(guò)的節(jié)點(diǎn)/轉(zhuǎn)向處理其右子樹(shù)/表示當(dāng)前不是處理?xiàng)ｍ敼?jié)點(diǎn)/棧不空循環(huán)/銷毀棧4.2.4 遞歸遍歷oidPreOrder(BTNode*b)(/先序遍歷if(b!=NULL)(cout<<(char)b->data;PreOrder(b->lchild);PreOrder(b->rchild);)voidInOrder(BTNode*b)(/中序遍歷if(b!=NULL)(InOrder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);)

22、voidPostOrder(BTNode*b)(/后序遍歷if(b!=NULL)(PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;)4.3算法的效率分析：主函數(shù)：函數(shù)中并不包含for循環(huán)、遞歸等復(fù)雜的算法,時(shí)間復(fù)雜度為O(1);輸入二叉樹(shù)：函數(shù)需要掃描輸入的二叉樹(shù),所以該算法的時(shí)間復(fù)雜度為O(n);非遞歸類遍歷：由于不管是先序遍歷還是中序遍歷以及后序遍歷,我們都需要利用一個(gè)輔助棧來(lái)進(jìn)行每個(gè)節(jié)點(diǎn)的存儲(chǔ)打印,所以每個(gè)節(jié)點(diǎn)都要進(jìn)棧和出棧,不過(guò)是根據(jù)那種遍歷方式改變的是每個(gè)節(jié)點(diǎn)的進(jìn)棧順序,所以時(shí)間

23、復(fù)雜度為O(n),同樣空間復(fù)雜度也為O(n),n為結(jié)點(diǎn)數(shù)；遞歸類遍歷：空間復(fù)雜度與系統(tǒng)堆棧有關(guān),系統(tǒng)棧需要記住每個(gè)節(jié)點(diǎn)的值,所以空間復(fù)雜度為O(n).時(shí)間復(fù)雜度應(yīng)該為O(nlogn),每個(gè)節(jié)點(diǎn)都要遍歷到,需要n次,而且需要將二叉樹(shù)劃分logn次,所以遞歸版的遍歷的空間復(fù)雜度為O(nlogn);層序遍歷：層序遍歷是通過(guò)隊(duì)列來(lái)進(jìn)行每個(gè)節(jié)點(diǎn)的存儲(chǔ)打印的,所以時(shí)間復(fù)雜度和空間復(fù)雜度都為O(n),n為結(jié)點(diǎn)數(shù).5.測(cè)試字輸入佰的二¥另寸(attt<3JtUIp(,±'),e)陽(yáng)濟(jì)森晝姆作去比犍攆優(yōu)請(qǐng)有諭入1.古皿居前,A門(mén)lull1OK山星售旗第存懣叉寅二三一一圖5-1初

24、始化菜單1二叉樹(shù)輸出為a(b(c),d(e(f)3g.)圖5-2輸出二叉樹(shù)2口叉樹(shù)高度為圖5-3輸出樹(shù)的高度4葉子結(jié)點(diǎn)顯示如不kfs圖5-4輸出葉子結(jié)點(diǎn)3后序遞歸遍歷輸出為cbfegda圖5-5輸出后序遞歸遍歷»請(qǐng)輸入你的操作<<11青輸入你摘點(diǎn)圖5-6查找結(jié)點(diǎn)所在層»請(qǐng)輸入你的操作小14后序非遞歸遍歷輸出為cbfggda圖5-7輸出后續(xù)非遞歸遍歷»請(qǐng)輸久你的操作<<15層次遍歷算法輸出：圖5-8層次遍歷輸出結(jié)構(gòu)經(jīng)過(guò)屢次測(cè)試與更改,但是無(wú)法打破原有的界面格式,使得界面輸出不夠美觀,程序的遞歸與非遞歸先序、中序、后序遍歷、層次遍歷、計(jì)算結(jié)點(diǎn)個(gè)

25、數(shù),計(jì)算結(jié)點(diǎn)所在層數(shù)等功能根本能夠流暢地實(shí)現(xiàn),到達(dá)了應(yīng)有的要求；不過(guò)在輸出二叉樹(shù)的時(shí)候,不知道為什么后面會(huì)多出一個(gè)括號(hào),經(jīng)過(guò)屢次的更改與實(shí)驗(yàn)也沒(méi)有將其更改成功,通過(guò)查看相關(guān)書(shū)籍以及網(wǎng)上搜索算法原理,終于明白了錯(cuò)誤所在,并完成了排錯(cuò).6 .課程設(shè)計(jì)心得6.1 改良方案對(duì)自己的設(shè)計(jì)進(jìn)行評(píng)價(jià),指出合理和缺乏之處,提出改良方案；1菜單設(shè)置方面：運(yùn)用了if語(yǔ)句,這樣看著沒(méi)有條理,不適合用在二叉樹(shù)的遍歷上,由于遍歷結(jié)果顯而易見(jiàn)并不十分復(fù)雜,沒(méi)有必要使程序復(fù)雜化,故采用的是程序運(yùn)行輸出模式.2二叉樹(shù)的創(chuàng)立：采用二叉鏈表存儲(chǔ)的方式,利用擴(kuò)展先序遍歷實(shí)現(xiàn)二叉樹(shù)的創(chuàng)立,這樣做相對(duì)簡(jiǎn)單,但是對(duì)有些情況下不太實(shí)用,所

26、以應(yīng)該增加一項(xiàng)根據(jù)后序中序?qū)崿F(xiàn)創(chuàng)立的算法,是程序更加完善.3整體布局：由于存在某兩個(gè)函數(shù)的制約關(guān)系,要求必須先執(zhí)行A在執(zhí)行B,一旦執(zhí)行順序錯(cuò)誤就會(huì)導(dǎo)致輸出結(jié)果錯(cuò)誤.這樣降低了程序的冗錯(cuò)性,不利于用戶操作,可以通過(guò)添加函數(shù)間強(qiáng)制裝換關(guān)系,強(qiáng)制執(zhí)行,或者是在后者運(yùn)行的函數(shù)中添加必要語(yǔ)句,使其脫離制約函數(shù)的制約.6.2 設(shè)計(jì)心得其實(shí)在本程序的設(shè)計(jì)過(guò)程當(dāng)中,沒(méi)有很吸引人的關(guān)鍵技術(shù),由于本人的C語(yǔ)言或C+詡言都不是學(xué)的很好,所以當(dāng)初設(shè)計(jì)的時(shí)候就只是想把功能都實(shí)現(xiàn)就好了,盡可能的把所要求的功能都編進(jìn)程序,這樣就覺(jué)得很滿足了.所以都是設(shè)計(jì)的比擬簡(jiǎn)單易懂的語(yǔ)言,這樣自己能夠更明白一些,所以就沒(méi)有時(shí)間去細(xì)細(xì)地去

27、設(shè)計(jì)自己的程序.本程序要說(shuō)有什么值得說(shuō)的,那就只有人性化這點(diǎn)了,在設(shè)計(jì)成學(xué)的時(shí)候,由于自己怕弄混了,所以添加了很詳盡的提示,這樣在編程的過(guò)程中或調(diào)試的時(shí)候都能夠比擬快的運(yùn)行.還有就是盡可能的應(yīng)用了do-while語(yǔ)句和switch-case語(yǔ)句,這兩個(gè)語(yǔ)句在之前不是很常用,所以在這個(gè)程序中試也是程序有條理一些.我煉了一下,雖然在編寫(xiě)的過(guò)程中總是出錯(cuò),但還是成功的用好了,也知道這些東西別人可能比我弄得還要好,但是我在我所學(xué)的知識(shí)中成功的應(yīng)用了這些,我覺(jué)得就是好事,就是進(jìn)步.唯一的亮點(diǎn)可能就是進(jìn)入系統(tǒng)是的密碼設(shè)計(jì)了,就這一點(diǎn)小小的設(shè)計(jì)就花了我好幾個(gè)小時(shí)去調(diào)試,由于總能在后面程序的參加及運(yùn)行時(shí)發(fā)現(xiàn)一

28、些新的小問(wèn)題.一周多的課程設(shè)計(jì),終于成功的驗(yàn)收了,雖然有些疲憊,但還是有很多的收獲的,像計(jì)算機(jī)組成原理的課設(shè)一樣,我又一次穩(wěn)固了所學(xué)到的知識(shí),之前的學(xué)習(xí)只是停留在理論根底上,現(xiàn)在自己動(dòng)手操作試驗(yàn)后,才是真正的理解及體會(huì).C也學(xué)了近一年,有很多知識(shí)都是似懂非懂,通過(guò)平時(shí)上機(jī)操作,自己也了解了一些,但讓我有了更深的理解和更好的熟悉,那么是在這次的課設(shè)上,之前的困惑也通過(guò)這次的課設(shè)解決了一些,雖然還是不能夠全面的理解,但是有進(jìn)步就很快樂(lè).在課程設(shè)計(jì)之前,由于有了綜合實(shí)驗(yàn)的經(jīng)驗(yàn)與教訓(xùn),明白了寫(xiě)代碼這一步是非常重要的,由于當(dāng)你把代碼輸進(jìn)去之后,并編譯讓其運(yùn)行,發(fā)現(xiàn)通過(guò)不了,再來(lái)檢查出問(wèn)題,是很費(fèi)費(fèi)力的事

29、情,因此分析和規(guī)劃代碼是很重要的,最重要的是要把邏輯結(jié)構(gòu)寫(xiě)好,這樣就不會(huì)出現(xiàn)大問(wèn)題,寫(xiě)代碼就要先找出核心的內(nèi)容,用多種方法來(lái)實(shí)現(xiàn)核心局部,這樣可以盡可能的防止發(fā)現(xiàn)邏輯或編譯不支持的錯(cuò)誤.通過(guò)本次論文設(shè)計(jì),我初步學(xué)會(huì)了論文設(shè)計(jì)的根本方法,學(xué)會(huì)了怎樣去借鑒別人的方法和經(jīng)驗(yàn),知道了如何整合資料和處理這些資料的水平,這為以后做畢設(shè)的論文打下了根底,使我感覺(jué)比擬好的是有一種成功的喜悅,雖然在編譯的時(shí)候會(huì)經(jīng)常由于一些小的錯(cuò)誤而心煩意亂,但是也不失為一件好事,失敗的越多積累的經(jīng)驗(yàn)越豐富,對(duì)人的考驗(yàn)也比擬多,那么在最后編譯成功時(shí)的喜悅就越濃烈,也是自己的水平有了進(jìn)一步的提升.由于知識(shí)和經(jīng)驗(yàn)的缺乏,這個(gè)程序編寫(xiě)

30、的不是很盡如人意,但是融合了自己的心血,就覺(jué)得是最好的,所以在以后還是需要較多的努力的,還是會(huì)在以后的學(xué)習(xí)過(guò)程中不斷地提升和改良的.7 .參考文獻(xiàn)1?算法導(dǎo)論?英文名：IntroductiontoAlgorithm主編：ThomasH.Cormen、CharlesE.Leiserson等譯者：潘金貴、顧鐵成出版社：機(jī)械工業(yè)出版社第三版2?數(shù)據(jù)結(jié)構(gòu)與算法?主編：王曙燕2021年9月第1版人民郵電出版社3?C語(yǔ)言程序設(shè)計(jì)教程?主編：王曙燕2021年9月第1版人民郵電出版社4譚浩強(qiáng).C程序設(shè)計(jì)第三版M.北京：清華大學(xué)出版社,2005.8.附錄#include<fstream>#inclu

31、de<iostream>#include<stdlib.h>#include<stdio.h>#include<string>#include"work.h"usingnamespacestd;#defineMaxSize100usingnamespacestd;typedefcharElemType;typedefstructbElemTypedata;structb*lchild,*rchild;/二叉樹(shù)結(jié)構(gòu)聲明BTNode;typedefstructBTNode*data100;/存放棧中的數(shù)據(jù)元素inttop;/存放棧

32、頂指針,即棧頂元素在data數(shù)組中的下標(biāo)SqStack;typedefstructBTNode*dataMaxSize;存放隊(duì)中元素intfront,rear;/隊(duì)頭隊(duì)尾指針SqQueue;intwidth10=0;/存放各層寬度的數(shù)組BTNode*LchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針*/returnp->lchild;BTNode*RchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針*/returnp->rchild;voidCreateBTree(BTNode*&b,char*str)/創(chuàng)立二叉鏈intMaxSiz

33、el=50;BTNode*StMaxSize,*p=NULL;inttop=-1,k=0,j=0;charch=strj;b=NULL;while(ch!='0")/str未掃描完時(shí)循環(huán)switch(ch)case'(':top+;Sttop=p;k=1;break;/可能有左孩子結(jié)點(diǎn),進(jìn)棧case')':top-;break;case',':k=2;break;/后面為右孩子default:p=(BTNode*)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rch

34、ild=NULL;if(b=NULL)b=p;elseswitch(k)case1:Sttop->lchild=p;break;case2:Sttop->rchild=p;break;j+;ch=strj;/繼續(xù)掃描strintFindNode(BTNode*b,ElemTypex)intp;if(b=NULL)returnNULL;elseif(b->data=x)returnx;elsep=FindNode(b->lchild,x);if(p!=NULL)(returnp;elsereturnFindNode(b->rchild,x);/隊(duì)列的有關(guān)操作void

35、InitQueue(SqQueue*&q)(q=(SqQueue*)malloc(sizeof(SqQueue);q->front=q->rear=0;/判斷隊(duì)列是否為空boolQueueEmpty(SqQueue*q)(return(q->front=q->rear);/進(jìn)隊(duì)列boolenQueue(SqQueue*q,BTNode*e)(if(q->rear+1)%MaxSize=q->front)/隊(duì)滿溢出returnfalse;q->rear=(q->rear+1)%MaxSize;q->dataq->rear=e;r

36、eturntrue;/出隊(duì)列booldeQueue(SqQueue*&q,BTNode*&e)(if(q->front=q->rear)/判斷是否隊(duì)空returnfalse;q->front=(q->front+1)%MaxSize;e=q->dataq->front;returnfalse;voidDestoryBTree(BTNode*&b)(if(b!=NULL)DestoryBTree(b->lchild);DestoryBTree(b->rchild);free(b);voidDispBTree(BTNode*b

37、)(/輸出單鏈表if(b!=NULL)(cout<<(char)b->data<<""if(b->lchild!=NULL|b->rchild!=NULL)(cout<<"("DispBTree(b->lchild);if(b->rchild!=NULL)cout<<","DispBTree(b->rchild);cout<<")"intBTHeight(BTNode*b)(/樹(shù)的高度intlchildh,rchildh

38、;if(b=NULL)return(0);lchildh=BTHeight(b->lchild);rchildh=BTHeight(b->rchild);return(lchildh>rchildh)?(lchildh+1):(rchildh+1);voidPreOrder(BTNode*b)(/先序遍歷if(b!=NULL)(cout<<(char)b->data;PreOrder(b->lchild);return1;PreOrder(b->rchild);)voidInOrder(BTNode*b)(/中序遍歷if(b!=NULL)(InO

39、rder(b->lchild);cout<<(char)b->data;InOrder(b->rchild);)voidPostOrder(BTNode*b)(/后序遍歷if(b!=NULL)(PostOrder(b->lchild);PostOrder(b->rchild);cout<<(char)b->data;)voidDispLeaf(BTNode*b)(/遞歸輸出葉子節(jié)點(diǎn)if(b!=NULL)(if(b->lchild=NULL&b->rchildNULL)cout<<(char)b->

40、data;DispLeaf(b->lchild);DispLeaf(b->rchild);)intlistleaf(BTNode*b)(/輸出葉子結(jié)點(diǎn)個(gè)數(shù)intnum1;if(b=NULL)return0;elseif(b->lchild=NULL&&b->rchildNULL)num1=listleaf(b->rchild)+listleaf(b->lchild);returnnum1;)intlistnode(BTNode*b)(intnum;if(b=NULL)return(0);else(num=listnode(b->lchi

41、ld)+listnode(b->rchild)+1;)returnnum;)intmaxnode(BTNode*b)(if(NULL=b)return0;intmaxLeft=maxnode(b->lchild);intmaxRight=maxnode(b->rchild);intmax=maxLeft>maxRight?maxLeft:maxRight;returnmax>b->data?max:b->data;)intlistfloor(BTNode*b,charx)(intnum2,m,n;if(b=NULL)num2=0;elseif(b-&g

42、t;data=x)num2=1;else(m=listfloor(b->lchild,x);n=listfloor(b->rchild,x);if(m=0&&n=0)num2=0;elsenum2=(m>n)?m:n)+1;)s->top+;intLevel(BTNode*b,ElemTypex,inth)(intl;if(b=NULL)return(0);elseif(char)b->data=(char)x)return(h);else(指針增1s->datas->top=e;/元素e放在棧頂指針處returntrue;)boolP

43、op(SqStack*&s,BTNode*&e)(if(s->top=-1)/棧為空的情況,即棧下溢出l=Level(b->lchild,x,h+1);/左子樹(shù)中查找if(l!=0)returnfalse;e=s->datas->top;/取棧頂指針元素的元素return(l);/在左子樹(shù)中找到,返回lelses->top-;指針減1return(Level(b->rchild,x,h+1);/在左子樹(shù)中未找到再在右子樹(shù)中查找)/棧的所有操作如下returntrue;)boolGetTop(SqStack*s,BTNode*&e)頂元

44、素(voidInitStack(SqStack*&s)/初始化棧(if(s->top=-1)/棧為空的情況,即棧下溢出returnfalse;s=(SqStack*)malloc(sizeof(SqStack);/分配一個(gè)是順序?？臻g,首地址存放在s中s->top=-1;/棧頂指針置為-1)e=s->datas->top;/取棧頂元素returntrue;)voidPreOrder1(BTNode*b)voidDestroyStack(SqStack*&s)/銷毀棧(free(s);)非遞歸遍歷算法(BTNode*p;SqStack*st;一個(gè)順序棧指針

45、stboolStackEmpty(SqStack*s)/判斷棧是否為空(return(s->top=-1);)InitStack(st);/初始化棧stPush(st,b);點(diǎn)進(jìn)棧while(!StackEmpty(st)/boolPush(SqStack*&s,BTNode*e)/進(jìn)棧(if(s->top=MaxSize-1)/棧滿的情況,即棧上溢出時(shí)循環(huán)(Pop(st,p);節(jié)點(diǎn)p并訪問(wèn)它returnnum2;returnfalse;/棧頂/出棧/棧頂/取棧/先序/定義/根節(jié)棧不為空/退棧printf("%c",p->data);/訪問(wèn)節(jié)點(diǎn)Pi

46、f(p->rchild!=NULL)/有右孩子時(shí)將其進(jìn)棧Push(st,p->rchild);if(p->lchild!=NULL)/有左孩子時(shí)將其進(jìn)棧Push(st,p->lchild);printf("n");DestroyStack(st);/銷毀棧/中序非遞歸遍歷voidInOrder1(BTNode*b)/中序非遞歸遍歷算法BTNode*p;SqStack*st;/定義一個(gè)順序棧指針stInitStack(st);/初始化棧stif(b!=NULL)p=b;while(!StackEmpty(st)|p!=NULL)while(p!=NUL

47、L)/掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧Push(st,p);/節(jié)點(diǎn)p進(jìn)棧p=p->lchild;/移動(dòng)到左孩子if(!StackEmpty(st)/假設(shè)棧不空Pop(st,p);/出棧節(jié)點(diǎn)pprintf("%c",p->data);/訪問(wèn)節(jié)點(diǎn)pp=p->rchild;/轉(zhuǎn)向處理其右子樹(shù)printf("n");DestroyStack(st);/銷毀棧voidPostOrder1(BTNode*b)/后序非遞歸遍歷算法BTNode*p,*r;boolflag;SqStack*st;/定義一個(gè)順序棧指針stInitStack(st);/初始化

48、棧stp=b;dowhile(p!=NULL)掃描節(jié)點(diǎn)p的所有左下節(jié)點(diǎn)并進(jìn)棧Push(st,p);/節(jié)點(diǎn)p進(jìn)棧p=p->lchild;/移動(dòng)到左孩子r=NULL;/r指向剛剛訪問(wèn)的節(jié)點(diǎn),初始時(shí)為空f(shuō)lag=true;/flag為真表示正在處理?xiàng)ｍ敼?jié)點(diǎn)while(!StackEmpty(st)&&flag)GetTop(st,p);/取出當(dāng)前的棧頂節(jié)點(diǎn)pif(p->rchild=r)/假設(shè)節(jié)點(diǎn)p的右孩子為空或者為剛剛訪問(wèn)過(guò)的節(jié)點(diǎn)/訪問(wèn)節(jié)點(diǎn)pprintf("%c",p->data);Pop(st,p);r=p;/r指向剛訪問(wèn)過(guò)的節(jié)點(diǎn))else(

49、p=p->rchild;/轉(zhuǎn)向處理其右子樹(shù)flag=false;/表示當(dāng)前不是處理?xiàng)ｍ敼?jié)點(diǎn))while(!StackEmpty(st);/棧不空循環(huán)printf("n");DestroyStack(st);/銷毀棧voidLevelOrder(BTNode*b)(BTNode*p;SqQueue*qu;InitQueue(qu);/初始化隊(duì)列enQueue(qu,b);/根結(jié)點(diǎn)指針進(jìn)入隊(duì)列while(!QueueEmpty(qu)/隊(duì)不為空時(shí)循環(huán)(deQueue(qu,p);/出隊(duì)結(jié)點(diǎn)pcout<<(char)p->data<<"

50、;"if(p->lchild!=NULL)/有(enQueue(qu,p->lchild);if(p->rchild!=NULL)/有右孩子進(jìn)隊(duì)(enQueue(qu,p->rchild);intmain()(system("cls");system("color00a");BTNode*b;inti,n;charx;cout<<"本程序?yàn)槎鏄?shù)的操作"<<endl;charstr20;cout<<"請(qǐng)輸入你的二叉樹(shù)"<<endl;c

51、in.getline(str,20);CreateBTree(b,str);cout<<"創(chuàng)立成功!"<<endl;cout<<"是否繼續(xù)操作繼續(xù)操作請(qǐng)輸入1,否那么輸入0"<<endl;cin>>i;while(i!=0)(cout<<"-"<<endl;cout<<"-輸入【0】結(jié)束程序-"<<endl;cout<<"-輸入【1】輸出二叉樹(shù)-"<<endl;co

52、ut<<"-輸入【2】計(jì)算二叉樹(shù)高度-"<<endl;cout<<"-輸入【3】查找節(jié)點(diǎn)是否存在-"<<endl;cout<<"-輸入【4】輸出所有葉子結(jié)點(diǎn)-"<<endl;cout<<"-輸入【5】計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)-"<<endl;cout<<"-輸入【6】前序遍歷輸出二叉樹(shù)-"<<endl;cout<<"-輸入【7】中序遍歷輸出二叉樹(shù)-"&l

53、t;<endl;cout<<"-輸入【8】后序遍歷輸出二叉樹(shù)-"<<endl;cout<<"-輸入【9】計(jì)算結(jié)點(diǎn)個(gè)數(shù)-"<<endl;cout<<"-輸入【10】輸出該樹(shù)中結(jié)點(diǎn)最大值-"<<endl;cout<<"-輸入【11】輸出樹(shù)中結(jié)點(diǎn)值為x的層-"<<endl;cout<<"-輸入【12】先序非遞歸算法-"<<endl;cout<<"-輸入【13】中序非遞歸算法一"VVendl;