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

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

3詳細設(shè)計：主函數(shù)輸入數(shù)值1,2,3輸入數(shù)據(jù)插入排序函數(shù)輸出退出函數(shù)3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計開始 開始判斷類型排序輸出輸入數(shù)據(jù)輸入123判斷是否繼續(xù)判斷類型排序輸出輸入數(shù)據(jù)輸入123判斷是否繼續(xù) 01結(jié)束結(jié)束3.2主模塊設(shè)計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運行結(jié)果5、遇到問題及解決方案本程序是運用類編寫但與平時作業(yè)不同的是難度較大，涉及內(nèi)容較廣。特別是要用到動態(tài)鏈表和對文件進行操作。而鏈表老師只是平時在課堂上簡單介紹，對文件的操作老師又沒講。所以就只有靠我們自學(xué)，在編程期間我自己去圖書館查閱相應(yīng)的資料，逐漸掌握了動態(tài)鏈表。通過看教材第13章《輸入輸出流》以及向?qū)W院里的編程高手請教，學(xué)會了對文件進行操作。6、小結(jié)通過本次的C++課程設(shè)計，讓我學(xué)會了把書本上的知識應(yīng)用到了實際中來。雖然在這幾周中有過挫折和坎坷，有的問題一直到了最后才被解決，但是我認為這未必就不是好事，這樣能鍛煉我的意志，磨練我的耐心，失敗是成功之母，這話一點都沒錯，沒有失敗就沒有成功。讓我沒有失去信心的是關(guān)懷我們的老師，當(dāng)我們有了問題和疑問，老師就很耐心的給予講解，讓我們有了一個良好的學(xué)習(xí)氛圍。7、參考資料《C++程序設(shè)計》譚浩強清華大學(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.按浮點型數(shù)值排序"<<endl;cout<<"3.按字符串排序"<<endl; cin>>k; if(k==1) {cout<<"請輸入數(shù)據(jù)個數(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ù)個數(shù)："<<endl; cin>>n; In(b,n);//調(diào)用函數(shù)cout<<"*******************************************************************************"<<endl; fluent(b,n); cout<<endl<<"浮點型數(shù)值排序:"<<endl; Out(b,n); } if(k==3) {cout<<"請輸入數(shù)據(jù)個數(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è)計題目：二叉樹的操作學(xué)生姓名：學(xué)號：系部名稱：計算機科學(xué)與技術(shù)系專業(yè)班級：指導(dǎo)教師：

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