上海應用技術學院-數(shù)據(jù)結構與算法-課程設計報告

1、上海應用技術學院數(shù)據(jù)結構與算法課程設計報告課程設計目的培養(yǎng)學生用學到的書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)學生以科學理論和工程上能力的技術，規(guī)范地開發(fā)大型、復雜、高質(zhì)量的應用軟件和系統(tǒng)軟件具有關鍵性作用；通過課程設計的實踐，學生可以在程序設計方法、上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。二、課程設計要求1）學生必須仔細閱讀數(shù)據(jù)結構與算法課程設計方案，認真主動完成課程設計的要求。有問題及時主動通過各種方式與教師聯(lián)系溝通。2）學生要發(fā)揮自主學習能力，充分利用時間，安排好課程設計的時間計劃，并在課程設計過程中不斷檢院系專業(yè)班級姓名學號*學院*091*11公

2、孫勝天091*指導老師:何*測自己的計劃完成情況，及時向教師匯報。3）課程設計按照教學計劃需要兩周時間完成，兩周中每天至少要上六小時的上機來調(diào)試C或C+語言設計的程序，總共至少要上機調(diào)試程序30小時。屬教師安排上機時間學生不得缺席。三、課程設計內(nèi)容1、建立二叉樹，層序、先序、中序、后序遍歷（用遞歸或非遞歸的方法都可以）*任務：要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結構的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)、輸出中序遍歷序列的函數(shù)、輸出后序遍歷序列的函數(shù)；2、各種排序任務：用程序實現(xiàn)插入法排序、選擇法排序、起泡法改進算法排序；利用插

3、入排序、選擇法排序和冒泡法的改進算法，將用戶隨機輸入的一列數(shù)按遞增的順序排好。輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個遞增的數(shù)列。四、課程設計細節(jié)（一）第一題設計：a）需求分析：本程序是用鏈式存儲結構來存儲二叉樹并進行一系列的算法，且結點內(nèi)容的數(shù)據(jù)類型為字符型。本程序用C-Free5編寫，可以實現(xiàn)各種二叉樹的遍歷。包括層序遍歷、先序遍歷、中序遍歷、后序遍歷的非遞歸算法。根據(jù)題目知，程序主要是根據(jù)給定二叉樹的四種遍歷結果：(1)先創(chuàng)建二叉樹：按括號表示法輸入二叉樹字符串，然后構造二叉鏈表表示的二叉樹。(2)設計算法：層序遍歷、先序遍歷、中序遍歷、后序遍歷,在做到層序遍歷

4、時，應注意算法如下：根結點入隊，隊頭元素出隊，左孩子不為空入隊右孩子不為空入隊的順序進行。設計main()函數(shù)調(diào)用以上步驟實現(xiàn)相關功能。根據(jù)題目要求，我們主要設計了以下幾個函數(shù)：(1)typedefstructnode定義一個用鏈式存儲結構存儲的二叉樹，其中包括左孩子和右孩子以及數(shù)據(jù)元素的內(nèi)容。和單鏈表類似，一個二叉鏈表由頭指針唯一確定，若二叉樹為空，則頭指針指向空。并且結點內(nèi)容的數(shù)據(jù)類型為字符型。(2)BTNode*CreateBTNode(BTNode*&b)此函數(shù)的功能是構建二叉樹。從鍵盤上按括號表示法輸入二叉樹字符串構造二叉鏈表表示的二叉樹To(3)voidLevelOrder

5、(BTNode*b)此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的層序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的中序遍歷的結果。(4)voidPreOrder(BTNode*b)此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的先序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的先序遍歷的結果。(5)voidInOrder(BTNode*b)此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的中序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的中序遍歷的結果。(6)voidPostOrder(BTNode*b)此函數(shù)的功能是用非遞歸的方法實現(xiàn)二叉樹的后序遍歷算法。調(diào)用此函數(shù)可以獲得二叉樹的非遞歸的后序遍歷的結果。voidDis

6、pBTNode(BTNode*b)此函數(shù)的功能是先序輸出二叉樹字符串。b)概要設計：我們的算法設計如下：一、非遞歸遍歷算法用指針數(shù)組stack口代替棧，添加一個top來表示進棧出棧的操作，同時還可以判斷stack是否為空。1、先序遍歷每次將節(jié)點壓入棧，然后彈出，壓右子樹，再壓入左子樹，在遍歷過程中，遍歷序列的右節(jié)點依次被存入棧，左節(jié)點逐次被訪問。2、中序遍歷先尋找最左邊的樹葉輸出(尋找過程中每個根節(jié)點都要入棧)，然后依次出棧，判斷根節(jié)點的右孩子是否有左孩子(即每次都要尋找每個根的最左孩子)知道top=-1,即棧空。3、后序遍歷設置一標志，以判斷節(jié)點是否訪問過。先尋找最左邊的樹葉，但不輸出（尋找

7、過程中每個根節(jié)點都要入棧）取棧頂元素，判斷其有沒有右孩子，沒有的話則輸出，有的話則還要繼續(xù)判斷其有沒有左孩子。知道棧為空。二、非遞歸層次遍歷算法訪問元素所指結點，若該元素所指結點的左右孩子結點非空，則該元素所指結點的左孩子指針和右孩子指針順序入隊。根絕題目要求我們設計main函數(shù)流程圖為：廣開始輸入二叉樹節(jié)點/層序遍歷并輸出前序遍歷并輸出中序遍歷并輸出q后序遍歷并輸出結束先定義二叉樹，用鏈式存儲2構存儲二叉樹。其中，Lchild和Rchild是分別指向該結點左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。定義二叉樹結點值的類型為字符型且結點個數(shù)不超過20個。定義好二叉樹后，創(chuàng)建二叉鏈表存儲的二

8、叉樹。按二叉樹帶空指針的先序次序輸入結點值，結點類型為字符型。按先序次序輸入，其中*表示空結點。算法是按照先序遍歷思想設計的。構造二叉鏈表表示的二叉樹T,星號表示空樹。其中mark的值1、2、3、4分別指stri為字母、（、，、）；tag為左、右孩子的標志。建立二叉樹的流程圖如下：二叉樹的非遞歸先序遍歷流程圖如下:c）詳細設計:本題的源程序如下:myBTree.cpp:/*copyright:孤獨的野狼*版權所有，請勿侵權*文件名：myBtree.cpp*日期：2012/6/25* /#include#include#include#defineMaxSize100typedefcharEle

9、mType;typedefstructnodeElemTypedata;structnode*lchild;structnode*rchild;BTNode;BTNode*CreateBTNode(BTNode*&b)/*夕卜部輸入建立創(chuàng)建二叉鏈BTNode*StMaxSize,*p=NULL;charch,str300;inttop=-1,k,j=0;scanf(%s,str);b=NULL;/*建立的二叉樹初始時為空*/ch=strj;while(ch!=0)/*str未掃描完時循環(huán)*/switch(ch)/*數(shù)據(jù)元素*/*指向左孩子*/*指向右孩子*/*/case(:top+;S

10、ttop=p;k=1;break;/*為左結點*/case):top-;break;case,:k=2;break;/*為右結點*/default:p=(BTNode*)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)/*p指向二叉樹的根結點*/b=p;else/*已建立二叉樹根結點*/switch(k)case1:Sttop-lchild=p;break;case2:Sttop-rchild=p;break;j+;ch=strj;returnb;voidDispBTNode(BTNode*b)/*二叉樹輸出函數(shù)

11、*/if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();/*有孩子結點時才輸出(*/DispBTNode(b-lchild);/*遞歸處理左子樹*/if(b-rchild!=NULL)printf(,);/*有右孩子結點時才輸出，*/DispBTNode(b-rchild);/*遞歸處理右子樹*/printf();voidLevelOrder(BTNode*b)BTNode*p;BTNode*quMaxSize;intfront,rear;front=rear=-1;rear+;qurear=b;whil

12、e(front!=rear)front=(front+1)%MaxSize;p=qufront;printf(%c,p-data);if(p-lchild!=NULL)rear=(rear+1)%MaxSize;qurear=p-lchild;if(p-rchild!=NULL)rear=(rear+1)%MaxSize;qurear=p-rchild;/*層次遍歷算法*/*定義環(huán)形隊列，存放結點指針*/*定義隊頭和隊尾指針*/*置隊列為空隊列*/*根結點指針進入隊列*/*隊列不為空*/*隊頭出隊列*/*訪問結點*/*有左孩子時將其進隊*/*有右孩子時將其進隊*/*有孩子結點時才輸出）*/vo

13、idPreOrder(BTNode*b)/*先序非遞歸遍歷算法*/(BTNode*p;structBTNode*pt;inttag;StMaxSize;inttop=-1;top+;Sttop.pt=b;Sttop.tag=1;p=Sttop.pt;top-;if(p!=NULL)/*(2)式*/top+;/*右孩子結點進棧*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子結點進棧*/Sttop.pt=p-lchild;Sttop.tag=1;top+;/*根結點進棧*/Sttop.pt=p;Sttop.tag=0;if(Sttop.tag=0)/*直接訪問的

14、情況*/printf(%c,Sttop.pt-data);while(top-1)/*棧不空日循環(huán)*/if(Sttop.tag=1)/*不能直接訪問的情況*/*while*/)voidInOrder(BTNode*b)/*中序非遞歸遍歷算法*/(BTNode*p;structBTNode*pt;inttag;StMaxSize;inttop=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)if(Sttop.tag=1)p=Sttop.pt;top-;if(p!=NULL)top+;/*右孩子結點進棧*/Sttop.pt=p-rchild;Sttop.tag

15、=1;top+;/*根結點進棧*/Sttop.pt=p;Sttop.tag=0;top+;/*左孩子結點進棧*/Sttop.pt=p-lchild;top-；/*棧不空時循環(huán)*/*不能直接訪問的情況*/Sttop.tag=1;if(Sttop.tag=0)/*直接訪問的情況*/printf(%c,Sttop.pt-data);top-;)/*while*/)Sttop.tag=0;top+;/*右孩子結點進棧*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子結點進棧*/voidPostOrder(BTNode*b)BTNode*p;structBTNode*p

16、t;inttag;StMaxSize;inttop=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)if(Sttop.tag=1)p=Sttop.pt;top-;if(p!=NULL)top+;Sttop.pt=p;/*后序非遞歸遍歷算法*/*棧不空日循環(huán)*/*不能直接訪問的情況*/*根結點進棧*/Sttop.pt=p-lchild;Sttop.tag=1;)if(Sttop.tag=0)/*直接訪問的情況*/printf(%c,Sttop.pt-data);top-;)/*while*/)FirstProg.cpp:/copyright:孤獨的野狼*版權

17、所有，請勿侵權*文件名：FirstProg.cpp*日期：2012/6/25*/#include#includemyBTree.cppexternBTNode*CreateBTNode(BTNode*&b);/*建立二叉樹*/externvoidDispBTNode(BTNode*b);externvoidLevelOrder(BTNode*b);externvoidPreOrder(BTNode*b);externvoidInOrder(BTNode*b);externvoidPostOrder(BTNode*b);intmain(void)BTNode*b,*p,*lp,*rp;c

18、harc,x;printf(copyright:孤獨的野狼，printf(請輸入二叉樹：);/*二叉樹輸出函數(shù)*/*層次遍歷算法*/*先序非遞歸遍歷算法*/*中序非遞歸遍歷算法*/*后序非遞歸遍歷算法*/Allrightsreserved!n);b=CreateBTNode(*&b);printf(層 次 遍 歷 序 列printf(先 序 遍 歷 序 列printf(中 序 遍 歷 序 列printf(后序遍歷序列d)調(diào)試分析本程序輸入的字符串為JBEDJHL.:);LevelOrder(b);printf(n);:);PreOrder(b);printf(n);:);InOrder

19、(b);printf(n);:);PostOrder(b);printf(n);A(B(D,E(H(J,K(L,M(,N),C(F,G(,I),其對應的二叉樹為:KM1printf(您輸入的二叉樹為：);DispBTNode(b);printf(n);測試所得結果為:j CAUMAclminist的位rDe&kt叩饋健百構與算法設計詼代碼木伐回的6才=回copyright：孤獨的野狼，孤獨的野狼，AILrightsreserud!請輸入二叉樹：請輸入二叉樹：ft(B(D.E(H(J,K(LtM(,N)C(F;G(,1)題輸入的二叉樹為題輸入的二叉樹為： 雙雙D,E(H(J層次遍歷序層次

20、遍歷序列列: :口口BCDEFGHIJRLMN版 序 遍 歷 序版 序 遍 歷 序 列列 : : 白白BDEHJKLMNCFGI中 序 遍 后 序中 序 遍 后 序 列列 : : 口口BJHLKMNEAFCGI后 序 通 店 用 歹 力 ：后 序 通 店 用 歹 力 ： 口口JLNMKHEBFIGCA請按任意鍵繼續(xù)請按任意鍵繼續(xù).本程序按非遞歸遍歷所耗費的時間復雜度為O(n),其所耗費的空間復雜度也為O(n)。(二)第二題設計：a)需求分析：排序的方法很多，根據(jù)排序文件所處位置的不同,可將排序分為內(nèi)部排序和外部排序兩大類,本篇課程設計針對內(nèi)部排序的實現(xiàn)程序展開。內(nèi)部排序是指待排序的數(shù)據(jù)量不大，

21、在內(nèi)存中進行的排序，內(nèi)部排序的種類很多，本文主要應用的是直接插入排序、冒泡排序、直接選擇排序。衡量排序算法的性能指標有時間復雜度、空間復雜度和穩(wěn)定性。各種排序方法所需的附加空間量一般都不大，所以時間復雜度是衡量排序算法好壞的重要因素。對內(nèi)部排序而言，其時間主要用在關鍵字的比較和交換上，因此比較次數(shù)和交換次數(shù)的多少直接影響排序方法的效率。在本程序中我們設計如下幾個函數(shù)：(1)直接選擇排序函數(shù)voidSelectSort(RecTypeR,intn)該函數(shù)實現(xiàn)按對R的直接選擇排序，并輸出排序過程。(2)直接插入排序函數(shù)voidInsertSort(RecTypeR,intn)該函數(shù)實現(xiàn)按對R的直接

22、插入排序， 并輸出排序過程。(3)冒泡排序函數(shù)voidBubbleSort(RecTypeR,intn)該函數(shù)實現(xiàn)按對R的冒泡排序，并輸出排序過程。(4)R還原函數(shù)voidrollback(RecTypebackup,RecTypeR,intn)該函數(shù)對R進行回滾，即將R還原為初始值。b)概要設計：根據(jù)題目我們設計如下算法：1、插入排序算法：將數(shù)組分成兩部分， 初始化時， 前部分數(shù)組為只有第一個元素， 用來存儲已排序元素， 我們這里叫arr1;后部分數(shù)組的元素為除第一個元素的所有元素，為待排序或待插入元素，我們這里叫arr2。排序時使用二層循環(huán)：第一層對arr2進行循環(huán)，每次取后部分數(shù)組（待排

23、序數(shù)組）里的第一個元素（我們稱為待排序元素或稱待插入元素）el,然后在第二層循環(huán)中對arrl（已排好序的數(shù)組）從第一個元素往后進行循環(huán)，查到第一個大于待插入元素（如果是升序排列）或第一個小于待插入元素（如果是降序排列）e2，然后對arrl從e2元素開始往后的所有元素向后移，最后把el插入到原來e2所在的位置。這樣反復地對arr2進行循環(huán)，直到arr2中所有的待插入的元素都插入到arrl中。2、選擇排序算法：每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序不像冒泡排序算法那樣先并不急于調(diào)換位置，第一輪（k=1）先從arr

24、ayk開始逐個檢查，看哪個數(shù)最小就記下該數(shù)所在的位置于miniindex中，等一輪掃描完畢，如果找到比arrayk-1更小的元素，則把arrayminlindex和ak-1對調(diào)，這時arrayk到最后一個元素中最小的元素就換到了arrayk-1的位置。如此反復進行第二輪、第三輪直到循環(huán)至最后一元素3、冒泡排序算法：設待排序的文件為r1.n,第1趟（遍）：從r1開始，依次比較兩個相鄰記錄的關鍵字ri.key和ri+1.key,若ri.keyri+1.key,則交換記錄ri和ri+1的位置；否則，不交換。（i=1,2,.n-1）,第1趟之后，n個關鍵字中最大的記錄移到了rn的位置上。第2趟：從r1

25、開始，依次比較兩個相鄰記錄的關鍵字ri.key和ri+1.key,若ri.keyri+1.key,則交換記錄ri和ri+1的位置；否則，不交換。（i=1,2,.n-2）第2趟之后，前n-1個關鍵字中最大的記錄移到了rn-1的位置上，作完n-1趟，或者不需再交換記錄時為止。我們設計的main函數(shù)流程圖如下：選擇法排序結束根據(jù)算法得到的插入排序的流程圖為:選擇排序的流程圖為:冒泡排序的流程圖為:typedefintKeyType;typedefcharInfoType10;KeyTypekey;/*關鍵字項*/RecType;typedefstructRecType/*記錄類型*/InfoType

26、data;/*其他數(shù)據(jù)項，類型為InfoType*/c）詳細設計：本題的源程序為：Sort.cpp;/*copyright:孤獨的野狼*版權所有，請勿侵權*文件名：sort.cpp*日期：2012/6/25*/#include#defineMAXE20typedefintKeyType;typedefcharInfoType10;KeyTypekey;/*關鍵字項*/*線性表中最多元素個數(shù)*/typedefstructRecType/*記錄類型*/InfoTypedata;/*其他數(shù)據(jù)項，類型為InfoType*/RecType;voidSelectSort(RecTypeR口,intn)/*

27、直接選擇排序算法*/inti,j,k,l;RecTypetemp;for(i=0;in-1;i+)/*做第i趟排序*/k=i;for(j=i+1;jn;j+)if(Rj.keyRk.key)k=j;/*k/*在當前無序區(qū)Ri.n-1中選key最小的Rk*/記下目前找到的最小關鍵字所在的位置*/if(k!=i)/*交換Ri和Rk*/temp=Ri;Ri=Rk;Rk=temp;printf(i=%d,i);/*輸出每一趟的排序結果*/for(l=0;ln;l+)printf(%2d,Rl.key);printf(n);)voidInsertSort(RecTypeR,intn)/*按遞增有序進行直

28、接插入排序*/inti,j,k;RecTypetemp;for(i=1;i=0&temp.keyRj.key)Rj+1=Rj;/*將關鍵字大于Ri.key的記錄后移*/j-;)Rj+1=temp;/*在j+1處插入Ri*/printf(i=%d,i);/*輸出每一趟的排序結果*/for(k=0;kn;k+)printf(%2d,Rk.key);printf(n);voidBubbleSort(RecTypeR,intn)(inti,j,k,exchange;RecTypetemp;for(i=0;ii;j-)/*比較，找出本趟最小關鍵字的記錄*/(if(Rj.keyRj-1.key)(

29、temp=Rj;/*Rj與Rj-1進行交換，將最小關鍵字記錄前移*/Rj=Rj-1;Rj-1=temp;exchange=1;printf(i=%d,i);/*輸出每一趟的排序結果*/for(k=0;kn;k+)printf(%2d,Rk.key);printf(n);if(exchange=0)(return;voidrollback(RecTypebackup,RecTypeR,intn)/*inti=0;for(i=0;in;i+)/*冒泡排序算法*/還原*/(Ri.key=backupi.key;)intmain(void)(inti,n,m=5;RecTypeRMAXE;RecTyp

30、ebackupMAXE;printf(CopyRight:孤獨的野狼，AllRightsReserved!n);printf(請輸入您要排序的數(shù)字的個數(shù)：);scanf(%d,&n);for(i=0;in;i+)(printf(請輸入第外數(shù)字：,i+1);scanf(%d,&m);Ri.key=m;backupi.key=m;)printf(您輸入的數(shù)字序列為：);for(i=0;in;i+)/*輸出初始關鍵字序列(printf(%2d,Ri.key);)printf(n);printf(插入法排序：n);InsertSort(R,n);*/rollback(backup,R,n);printf(選擇法排序:n);SelectSort(R,n);rollback(backup,R,n);printf(起泡法改進算法排序：n);BubbleSort(R,n);printf(排好序的序列為：)；/*輸出初始關鍵字序列*/for(i=0;in;i+)printf(%2d,Ri.key);printf(n);d)調(diào)試分析本次測試輸入的數(shù)字序列