上海應(yīng)用技術(shù)學(xué)院-數(shù)據(jù)結(jié)構(gòu)與算法-課程設(shè)計(jì)報(bào)告

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

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

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

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

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

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

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

8、叉樹(shù)。按二叉樹(shù)帶空指針的先序次序輸入結(jié)點(diǎn)值，結(jié)點(diǎn)類型為字符型。按先序次序輸入，其中*表示空結(jié)點(diǎn)。算法是按照先序遍歷思想設(shè)計(jì)的。構(gòu)造二叉鏈表表示的二叉樹(shù)T,星號(hào)表示空樹(shù)。其中mark的值1、2、3、4分別指stri為字母、（、，、）；tag為左、右孩子的標(biāo)志。建立二叉樹(shù)的流程圖如下：二叉樹(shù)的非遞歸先序遍歷流程圖如下:c）詳細(xì)設(shè)計(jì):本題的源程序如下:myBTree.cpp:/*copyright:孤獨(dú)的野狼*版權(quán)所有，請(qǐng)勿侵權(quán)*文件名：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;/*建立的二叉樹(shù)初始時(shí)為空*/ch=strj;while(ch!=0)/*str未掃描完時(shí)循環(huán)*/switch(ch)/*數(shù)據(jù)元素*/*指向左孩子*/*指向右孩子*/*/case(:top+;S

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

11、*/if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();/*有孩子結(jié)點(diǎn)時(shí)才輸出(*/DispBTNode(b-lchild);/*遞歸處理左子樹(shù)*/if(b-rchild!=NULL)printf(,);/*有右孩子結(jié)點(diǎn)時(shí)才輸出，*/DispBTNode(b-rchild);/*遞歸處理右子樹(shù)*/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)形隊(duì)列，存放結(jié)點(diǎn)指針*/*定義隊(duì)頭和隊(duì)尾指針*/*置隊(duì)列為空隊(duì)列*/*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/*隊(duì)列不為空*/*隊(duì)頭出隊(duì)列*/*訪問(wèn)結(jié)點(diǎn)*/*有左孩子時(shí)將其進(jìn)隊(duì)*/*有右孩子時(shí)將其進(jìn)隊(duì)*/*有孩子結(jié)點(diǎn)時(shí)才輸出）*/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+;/*右孩子結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-lchild;Sttop.tag=1;top+;/*根結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p;Sttop.tag=0;if(Sttop.tag=0)/*直接訪問(wèn)的

14、情況*/printf(%c,Sttop.pt-data);while(top-1)/*棧不空日循環(huán)*/if(Sttop.tag=1)/*不能直接訪問(wèn)的情況*/*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+;/*右孩子結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-rchild;Sttop.tag

15、=1;top+;/*根結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p;Sttop.tag=0;top+;/*左孩子結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-lchild;top-；/*棧不空時(shí)循環(huán)*/*不能直接訪問(wèn)的情況*/Sttop.tag=1;if(Sttop.tag=0)/*直接訪問(wèn)的情況*/printf(%c,Sttop.pt-data);top-;)/*while*/)Sttop.tag=0;top+;/*右孩子結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子結(jié)點(diǎn)進(jìn)棧*/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)*/*不能直接訪問(wèn)的情況*/*根結(jié)點(diǎn)進(jìn)棧*/Sttop.pt=p-lchild;Sttop.tag=1;)if(Sttop.tag=0)/*直接訪問(wèn)的情況*/printf(%c,Sttop.pt-data);top-;)/*while*/)FirstProg.cpp:/copyright:孤獨(dú)的野狼*版權(quán)

17、所有，請(qǐng)勿侵權(quán)*文件名：FirstProg.cpp*日期：2012/6/25*/#include#includemyBTree.cppexternBTNode*CreateBTNode(BTNode*&b);/*建立二叉樹(shù)*/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:孤獨(dú)的野狼，printf(請(qǐng)輸入二叉樹(shù)：);/*二叉樹(shù)輸出函數(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),其對(duì)應(yīng)的二叉樹(shù)為:KM1printf(您輸入的二叉樹(shù)為：);DispBTNode(b);printf(n);測(cè)試所得結(jié)果為:j CAUMAclminist的位rDe&kt叩饋健百構(gòu)與算法設(shè)計(jì)詼代碼木伐回的6才=回copyright：孤獨(dú)的野狼，孤獨(dú)的野狼，AILrightsreserud!請(qǐng)輸入二叉樹(shù)：請(qǐng)輸入二叉樹(shù)：ft(B(D.E(H(J,K(LtM(,N)C(F;G(,1)題輸入的二叉樹(shù)為題輸入的二叉樹(shù)為： 雙雙D,E(H(J層次遍歷序?qū)哟?/p>

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

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

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

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

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

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

26、data;/*其他數(shù)據(jù)項(xiàng)，類型為InfoType*/c）詳細(xì)設(shè)計(jì)：本題的源程序?yàn)椋篠ort.cpp;/*copyright:孤獨(dú)的野狼*版權(quán)所有，請(qǐng)勿侵權(quán)*文件名：sort.cpp*日期：2012/6/25*/#include#defineMAXE20typedefintKeyType;typedefcharInfoType10;KeyTypekey;/*關(guān)鍵字項(xiàng)*/*線性表中最多元素個(gè)數(shù)*/typedefstructRecType/*記錄類型*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng)，類型為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/*在當(dāng)前無(wú)序區(qū)Ri.n-1中選key最小的Rk*/記下目前找到的最小關(guān)鍵字所在的位置*/if(k!=i)/*交換Ri和Rk*/temp=Ri;Ri=Rk;Rk=temp;printf(i=%d,i);/*輸出每一趟的排序結(jié)果*/for(l=0;ln;l+)printf(%2d,Rl.key);printf(n);)voidInsertSort(RecTypeR,intn)/*按遞增有序進(jìn)行直

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

29、temp=Rj;/*Rj與Rj-1進(jìn)行交換，將最小關(guān)鍵字記錄前移*/Rj=Rj-1;Rj-1=temp;exchange=1;printf(i=%d,i);/*輸出每一趟的排序結(jié)果*/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:孤獨(dú)的野狼，AllRightsReserved!n);printf(請(qǐng)輸入您要排序的數(shù)字的個(gè)數(shù)：);scanf(%d,&n);for(i=0;in;i+)(printf(請(qǐng)輸入第外數(shù)字：,i+1);scanf(%d,&m);Ri.key=m;backupi.key=m;)printf(您輸入的數(shù)字序列為：);for(i=0;in;i+)/*輸出初始關(guān)鍵字序列(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(起泡法改進(jìn)算法排序：n);BubbleSort(R,n);printf(排好序的序列為：)；/*輸出初始關(guān)鍵字序列*/for(i=0;in;i+)printf(%2d,Ri.key);printf(n);d)調(diào)試分析本次測(cè)試輸入的數(shù)字序列