數(shù)據(jù)排序課程設(shè)計(jì)及數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉樹的操作

黑龍江工程學(xué)院信息科學(xué)與技術(shù)學(xué)院程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)報(bào)告題目名稱：數(shù)據(jù)排序?qū)W生姓名：學(xué)號(hào):專業(yè)班級：計(jì)科2班指導(dǎo)教師：目錄1.課程設(shè)計(jì)題目與要求： 31.1設(shè)計(jì)題目： 31.2設(shè)計(jì)要求： 32總體設(shè)計(jì) 33詳細(xì)設(shè)計(jì)： 33.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 33.2主模塊設(shè)計(jì) 33.2.1輸入數(shù)據(jù)： 33.2.2字符串大小排序 33.2.3整型數(shù)值大小排列： 34運(yùn)行結(jié)果 35、遇到問題及解決方案 36、小結(jié) 37、參考資料 3………171.課程設(shè)計(jì)題目與要求：1.1設(shè)計(jì)題目：編一通用排序程序，程序可以對任意類型的數(shù)值常數(shù)或字符串構(gòu)成的行進(jìn)行排序，通過人機(jī)對話選擇程序是按數(shù)值進(jìn)行排序還是按字符順序進(jìn)行排序。排序是針對數(shù)據(jù)文件的。例如：初始數(shù)據(jù)為：12,24,9,128,3,76,345按數(shù)值大小排序應(yīng)為：3,9,12,24,76,128,345按字符串大小排序應(yīng)為：12,128,24，3,345,76,91.2設(shè)計(jì)要求：（1）只能使用C/C++語言，源程序要有適當(dāng)?shù)淖⑨?，使程序容易閱讀（2）至少采用文本菜單界面（如果能采用圖形菜單界面更好）（3）學(xué)生可自動(dòng)增加新功能模塊（4）完成系統(tǒng)總結(jié)報(bào)告以及系統(tǒng)使用說明書\\2總體設(shè)計(jì)功能框架圖：主函數(shù)輸入數(shù)值1,2,3輸入數(shù)據(jù)插入排序函數(shù)輸出退出函數(shù)

3詳細(xì)設(shè)計(jì)：主函數(shù)輸入數(shù)值1,2,3輸入數(shù)據(jù)插入排序函數(shù)輸出退出函數(shù)3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)開始 開始判斷類型排序輸出輸入數(shù)據(jù)輸入123判斷是否繼續(xù)判斷類型排序輸出輸入數(shù)據(jù)輸入123判斷是否繼續(xù) 01結(jié)束結(jié)束3.2主模塊設(shè)計(jì)3.2.1輸入數(shù)據(jù)：開始開始輸入數(shù)據(jù)輸入數(shù)據(jù)判斷 是判斷 否結(jié)束結(jié)束開始3.2.2字符串大小排序開始傳入字符數(shù)據(jù)strcmp(a[i],a[i+1])>0Str1=a[i];a[i]=a[i+1];a[i+1]=str1=1]輸出字符串判斷i++傳入字符數(shù)據(jù)strcmp(a[i],a[i+1])>0Str1=a[i];a[i]=a[i+1];a[i+1]=str1=1]輸出字符串判斷i++3.2.3整型數(shù)值大小排列：開始傳入整型數(shù)據(jù)開始傳入整型數(shù)據(jù)a[i]>a[i+1] a[i]>a[i+1]k=a[i];a[i]=a[i+1];a[i+1]=k=1]判斷i++k=a[i];a[i]=a[i+1];a[i+1]=k=1]判斷i++ 是輸出字符串 否輸出字符串4運(yùn)行結(jié)果5、遇到問題及解決方案本程序是運(yùn)用類編寫但與平時(shí)作業(yè)不同的是難度較大，涉及內(nèi)容較廣。特別是要用到動(dòng)態(tài)鏈表和對文件進(jìn)行操作。而鏈表老師只是平時(shí)在課堂上簡單介紹，對文件的操作老師又沒講。所以就只有靠我們自學(xué)，在編程期間我自己去圖書館查閱相應(yīng)的資料，逐漸掌握了動(dòng)態(tài)鏈表。通過看教材第13章《輸入輸出流》以及向?qū)W院里的編程高手請教，學(xué)會(huì)了對文件進(jìn)行操作。6、小結(jié)通過本次的C++課程設(shè)計(jì)，讓我學(xué)會(huì)了把書本上的知識(shí)應(yīng)用到了實(shí)際中來。雖然在這幾周中有過挫折和坎坷，有的問題一直到了最后才被解決，但是我認(rèn)為這未必就不是好事，這樣能鍛煉我的意志，磨練我的耐心，失敗是成功之母，這話一點(diǎn)都沒錯(cuò)，沒有失敗就沒有成功。讓我沒有失去信心的是關(guān)懷我們的老師，當(dāng)我們有了問題和疑問，老師就很耐心的給予講解，讓我們有了一個(gè)良好的學(xué)習(xí)氛圍。7、參考資料《C++程序設(shè)計(jì)》譚浩強(qiáng)清華大學(xué)出版社《VISUALC++6.0完全自學(xué)手冊》孔鵬人民郵電出版社8.源代碼#include<iostream>#include<string>#include<Windows.h>usingnamespacestd;template<typenameT>//輸出voidOut(T*array,constinta){ inti=0; for(;i<a;++i) cout<<array[i]<<""; cout<<endl;}template<typenameT>//排序voidfluent(T*array,constintn){ inti,j; Ta; for(i=0;i<n-1;++i) { for(j=0;j<n-i-1;++j) { if(array[j]>array[j+1]) { a=array[j]; array[j]=array[j+1]; array[j+1]=a; } } }}template<typenameT>//輸入數(shù)據(jù)并存放到數(shù)組中voidIn(T*array,intn){ inti=0; cout<<"請輸入值，用空格隔開:"<<endl; for(;i<n;i++) { cin>>array[i]; }}intmain(){ intk,n,a[10],x; doubleb[10]; stringc[10];for(x=0;x<1;){cout<<"*******************************************************************************"<<endl; cout<<"1.按整型數(shù)值排序"<<endl; cout<<"2.按浮點(diǎn)型數(shù)值排序"<<endl;cout<<"3.按字符串排序"<<endl; cin>>k; if(k==1) {cout<<"請輸入數(shù)據(jù)個(gè)數(shù)："<<endl; cin>>n; In(a,n);//調(diào)用函數(shù)cout<<"*******************************************************************************"<<endl; fluent(a,n); cout<<endl<<"整型數(shù)值排序:"<<endl; Out(a,n); } if(k==2) {cout<<"請輸入數(shù)據(jù)個(gè)數(shù)："<<endl; cin>>n; In(b,n);//調(diào)用函數(shù)cout<<"*******************************************************************************"<<endl; fluent(b,n); cout<<endl<<"浮點(diǎn)型數(shù)值排序:"<<endl; Out(b,n); } if(k==3) {cout<<"請輸入數(shù)據(jù)個(gè)數(shù)："<<endl; cin>>n; In(c,n);//調(diào)用函數(shù) cout<<"*******************************************************************************"<<endl; fluent(c,n); cout<<endl<<"按字符串排序:"<<endl; Out(c,n); } cout<<"繼續(xù)請輸入0不繼續(xù)請輸入1"<<endl;//選擇是否繼續(xù); cin>>x;} return0;}數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：二叉樹的操作學(xué)生姓名：學(xué)號(hào)：系部名稱：計(jì)算機(jī)科學(xué)與技術(shù)系專業(yè)班級：指導(dǎo)教師：

SY-027課程設(shè)計(jì)任務(wù)書SY-027組內(nèi)學(xué)生姓名人數(shù)1系部名稱計(jì)算機(jī)科學(xué)與技術(shù)系專業(yè)軟件工程班級、學(xué)號(hào)指導(dǎo)教師姓名職稱從事專業(yè)軟件工程題目名稱二叉樹的操作課程設(shè)計(jì)的目的、意義目的在于通過課程設(shè)計(jì)的綜合訓(xùn)練，幫助學(xué)生深入系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容和基本方法，培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí)分析解決實(shí)際問題和編程等實(shí)際動(dòng)手能力。熟練的掌握二叉樹的基本操作。二、課程設(shè)計(jì)的主要內(nèi)容、技術(shù)要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計(jì)要求、工作量要求等）實(shí)現(xiàn)二叉樹的先序、中序和后序遍歷；求二叉樹的結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)及二叉樹的深度。三、課程設(shè)計(jì)完成后應(yīng)提交的成果完整的論文和部分源代碼四、課程設(shè)計(jì)的工作進(jìn)度安排（1）復(fù)習(xí)與設(shè)計(jì)題目相關(guān)的數(shù)據(jù)結(jié)構(gòu)知識(shí)，查閱文獻(xiàn)資料（1天）（2）確定設(shè)計(jì)方案，設(shè)計(jì)模塊結(jié)構(gòu)及各模塊流程（1天）（3）編碼、調(diào)試與測試（5天）（4）撰寫課程設(shè)計(jì)報(bào)告（2天）（5）設(shè)計(jì)演示（1天）五、主要參考資料1.嚴(yán)蔚敏、吳偉民，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），北京：清華大學(xué)出版社，2006.52.寧正元、易金聰，《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)實(shí)驗(yàn)指導(dǎo)》，中國水利水電出版社、上海交通大學(xué)出版社、東南大學(xué)出版社，2002.6六、備注指導(dǎo)教師簽字：年月日教研室主任簽字：年月日程序要求1）完成二叉樹的基本操作。2）建立以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹；3）實(shí)現(xiàn)二叉樹的先序、中序和后序遍歷；4）求二叉樹的結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)及二叉樹的深度。算法分析建立以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹，在次二叉樹上進(jìn)行操作；1先序遍歷二叉樹的操作定義為：若二叉樹唯恐則為空操作；否則（1）訪問根節(jié)點(diǎn)；（2）先序遍歷做字?jǐn)?shù)和；（3）先序遍歷有子樹；2中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作;否則（1）中序遍歷做子樹；（2）訪問根節(jié)點(diǎn)；（3）中序遍歷有子樹；3后續(xù)遍歷二叉樹的操作定義為：若二叉樹為空則為空操作；否則（1)后序遍歷左子樹;（2)后序遍歷右子樹;（3）訪問根節(jié)點(diǎn)；二叉樹的結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)及二叉樹的深度。二叉樹的基本操作和算法實(shí)現(xiàn)二叉樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，是另一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)之多有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn))，并且二叉樹的結(jié)點(diǎn)有左右之分，其次序不能隨便顛倒。二叉樹創(chuàng)建二叉樹的很多操作都是基于遍歷實(shí)現(xiàn)的。二叉樹的遍歷是采用某種策略使得采用樹形結(jié)構(gòu)組織的若干年借點(diǎn)對應(yīng)于一個(gè)線性序列。二叉樹的遍歷策略有四種：先序遍歷中續(xù)遍歷后續(xù)遍歷和層次遍歷?；疽?從鍵盤接受輸入數(shù)據(jù)（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹。2輸出二叉樹。3對二叉樹進(jìn)行遍歷（先序，中序，后序和層次遍歷）4將二叉樹的遍歷打印出來。一．問題描述二叉樹的很多操作都是基于遍歷實(shí)現(xiàn)的。二叉樹的遍歷是采用某種策略使得采用樹型結(jié)構(gòu)組織的若干結(jié)點(diǎn)對應(yīng)于一個(gè)線性序列。二叉樹的遍歷策略有四種：先序遍歷、中序遍歷、后序遍歷和層次遍歷。二．基本要求1．從鍵盤接受輸入數(shù)據(jù)（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹。2．輸出二叉樹。3．對二叉樹進(jìn)行遍歷（先序、中序、后序和層次遍歷）。4．將二叉樹的遍歷結(jié)果打印輸出。三．提示與分析1．主要數(shù)據(jù)類型①二叉鏈表#defineDataTypechar/*元素類型*/typedefstructBiTNode{DataTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;②二叉樹的遍歷序列DataTypepreorder[n];DataTypeinorder[n];DataTypepostorder[n];2．基本功能分析①采用教材上類似于先序遍歷的方法逐個(gè)輸入結(jié)點(diǎn)，建立二叉鏈表存儲(chǔ)的二叉樹。②采用遞歸算法對二叉樹分別進(jìn)行先序、中序、后序遍歷。③以隊(duì)列為輔助結(jié)構(gòu)實(shí)現(xiàn)二叉樹的層次遍歷。④結(jié)合先序遍歷，以凹入表形式輸出二叉樹。//定義二叉樹結(jié)點(diǎn)結(jié)構(gòu)和操作的頭文件btree1.h//定義二叉樹結(jié)點(diǎn)值的類型為字符型typedefcharElemType;//定義二叉樹結(jié)點(diǎn)類型structBTreeNode{ElemTypedata;BTreeNode*left;BTreeNode*right;};//初始化二叉樹，即把樹根指針置空voidInitBTree(BTreeNode*&BT);//判斷二叉樹是否為空boolBTreeEmpty(BTreeNode*BT);1.1.1二叉樹的遍歷二叉樹的遍歷即是如何按照某條路徑尋訪每一個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次?！霸L問”的含義很廣，可以是對結(jié)點(diǎn)做出各種處理，如輸出結(jié)點(diǎn)的信息等。遍歷對線性結(jié)構(gòu)來說是一個(gè)容易解決的問題，而對于二叉樹則不然，由于二叉樹是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有可能有倆棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點(diǎn)都能夠排列在線性隊(duì)列上，從而便于遍歷。二叉樹室友三個(gè)基本單位組成的：根節(jié)點(diǎn)左子樹和右子樹。因而遍歷著三個(gè)部分，便是遍歷了整個(gè)二叉樹。voidTraverseBTree(BTreeNode*BT,intmark){if(mark==1){//先序遍歷if(BT!=NULL){cout<<BT->data<<'';TraverseBTree(BT->left,mark);TraverseBTree(BT->right,mark);}}elseif(mark==2){//中序遍歷if(BT!=NULL){TraverseBTree(BT->left,mark);cout<<BT->data<<'';TraverseBTree(BT->right,mark);}}elseif(mark==3){//后序遍歷if(BT!=NULL){TraverseBTree(BT->left,mark);TraverseBTree(BT->right,mark);cout<<BT->data<<'';}}elseif(mark==4)//按層遍歷{constMaxLength=30;BTreeNode*Q[MaxLength];//定義存儲(chǔ)二叉樹結(jié)點(diǎn)指針的數(shù)組空間作為隊(duì)列使用intfront=0,rear=0;//定義隊(duì)首指針和隊(duì)尾指針，初始均置0表示空隊(duì)BTreeNode*p;｝求二叉樹的結(jié)點(diǎn)總數(shù)葉子節(jié)點(diǎn)個(gè)數(shù)及二叉樹的深度//用于求二叉樹深度的遞歸函數(shù)intDepth(BTreeNode*BT){if(BT==NULL)return0;//對于空樹，返回0并結(jié)束遞歸else{//計(jì)算左子樹的深度intdep1=Depth(BT->left);//計(jì)算右子樹的深度intdep2=Depth(BT->right);//返回樹的深度if(dep1>dep2)returndep1+1;elsereturndep2+1;｝}//求二叉樹中所有結(jié)點(diǎn)數(shù)intBinaryTree::BTreeCount(){returnCount(root);}//用于求二叉樹中所有結(jié)點(diǎn)數(shù)的遞歸函數(shù)intCount(BTreeNode*BT){if(BT==NULL)return0;elsereturnCount(BT->left)+Count(BT->right)+1;}//求二叉樹中所有葉子結(jié)點(diǎn)數(shù)intBinaryTree::BTreeLeafCount(){returnLeafCount(root);}//用于求二叉樹中所有葉子結(jié)點(diǎn)數(shù)的遞歸函數(shù)intLeafCount(BTreeNode*BT){if(BT==NULL)return0;elseif(BT->left==NULL&&BT->right==NULL)return1;elsereturnLeafCount(BT->left)+LeafCount(BT->right);｝調(diào)試結(jié)果測試數(shù)據(jù)1．輸入：ABC+DE+G++F+++（其中+表示空格字符）則輸出結(jié)果為：先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA2．輸入：AB+DG+++CE++F++先序：ABDGCEF中序：BGDAECF后序：GDBEFCA3．輸入：ABDF++++C+E+G++先序：ABDFCEG中序：FDBACEG后序：FDBGECA第五章實(shí)習(xí)體會(huì)數(shù)據(jù)結(jié)構(gòu)的實(shí)習(xí)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程.回顧起此數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)，至今我仍感慨頗多，的確，從選題到定稿，從理論到實(shí)踐，在整整兩星期的日子里，可以說得是苦多于甜，但是可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過的知識(shí)，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識(shí)。通過這次實(shí)習(xí)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與