西北工業(yè)大學(xué)程序設(shè)計(jì)大作業(yè).doc

學(xué) 院學(xué)院班 級(jí)學(xué) 號(hào)姓 名目錄1 摘要31.1 設(shè)計(jì)題目31.2 設(shè)計(jì)內(nèi)容31.3 開(kāi)發(fā)工具31.4 應(yīng)用平臺(tái)32 詳細(xì)設(shè)計(jì)32.1 程序結(jié)構(gòu)32.2 主要功能42.3 函數(shù)實(shí)現(xiàn)52.4 開(kāi)發(fā)日志73 程序調(diào)試及運(yùn)行73.1 程序運(yùn)行結(jié)果73.2 程序使用說(shuō)明123.3 程序開(kāi)發(fā)總結(jié)124 附件（源程序）121 摘要1.1 設(shè)計(jì)題目算法型大作業(yè)題目：編寫七種排序算法的演示程序。1.2 設(shè)計(jì)內(nèi)容編寫快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數(shù)排序函數(shù)，通過(guò)主函數(shù)調(diào)用以實(shí)現(xiàn)七種排序算法的演示。1.3 開(kāi)發(fā)工具Visual C+ 6.01.4 應(yīng)用平臺(tái)Windows 2000/XP/Vista 32位2 詳細(xì)設(shè)計(jì)2.1 程序結(jié)構(gòu)程序的整體結(jié)構(gòu)與流程見(jiàn)下圖所示。程序運(yùn)行時(shí)在主菜單中輸入序號(hào)選擇排序方法或選擇結(jié)束程序，當(dāng)進(jìn)行某種排序方法后，在主函數(shù)中輸入待排數(shù)據(jù)個(gè)數(shù)和待排數(shù)據(jù)，通過(guò)調(diào)用對(duì)應(yīng)的排序函數(shù)實(shí)現(xiàn)排序并輸出。該排序結(jié)束后再次進(jìn)入主函數(shù)，通過(guò)循環(huán)重復(fù)上述操作。其中，主函數(shù)中將數(shù)組地址和待排序數(shù)據(jù)個(gè)數(shù)傳遞給排序函數(shù)，在排序函數(shù)中實(shí)現(xiàn)排序功能。輸出排序結(jié)果開(kāi)始快速插入選擇冒泡堆排歸并基數(shù)選擇排序方法進(jìn)入主菜單退出系統(tǒng)2.2 主要功能函數(shù)的功能為對(duì)快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數(shù)排序算法的演示。主函數(shù)：程序運(yùn)行時(shí)，可使運(yùn)行者根據(jù)提醒輸入相關(guān)操作，從而進(jìn)入不同的排序方法或者退出。快速排序函數(shù)：根據(jù)快速排序的算法，最后輸出插入排序函數(shù)：根據(jù)插入排序的算法，最后輸出選擇排序函數(shù)：根據(jù)選擇排序的算法，最后輸出冒泡排序函數(shù)：根據(jù)冒泡排序的算法，最后輸出堆排序函數(shù)：根據(jù)堆排序的算法，最后輸出歸并排序函數(shù)：根據(jù)歸并排序的算法，最后輸出基數(shù)排序函數(shù)：根據(jù)基數(shù)排序的算法，最后輸出2.3 函數(shù)實(shí)現(xiàn)主函數(shù):在主函數(shù)中對(duì)菜單輸出，通過(guò)switch語(yǔ)句中的case分支選擇所需要的排序方法；通過(guò)while循環(huán)使演示程序在運(yùn)行時(shí)能夠持續(xù)進(jìn)行快速排序： 快速排序（kuaisu）又被稱做分區(qū)交換排序，這是一種平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某個(gè)數(shù)據(jù)元素(例如取第一個(gè)數(shù)據(jù)元素)作為基準(zhǔn)，按照該數(shù)據(jù)元素的關(guān)鍵字大小，將整個(gè)排序表劃分為左右兩個(gè)子表： 左側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都小于基準(zhǔn)數(shù)據(jù)元素的關(guān)鍵字。右側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都大于或等于基準(zhǔn)數(shù)據(jù)元素的關(guān)鍵字，基準(zhǔn)數(shù)據(jù)元素則排在這兩個(gè)子表中間(這也是該數(shù)據(jù)元素最終應(yīng)安放的位置)，然后分別對(duì)這兩個(gè)子表重復(fù)施行上述方法的快速排序，直到所有的子表長(zhǎng)度為1，則排序結(jié)束。插入排序：插入排序（charu）的基本思想：開(kāi)始時(shí)把第一個(gè)數(shù)據(jù)元素作為初始的有序序列，然后從第二個(gè)數(shù)據(jù)元素開(kāi)始依次把數(shù)據(jù)元素按關(guān)鍵字大小插入到已排序的部分排序表的適當(dāng)位置。當(dāng)插入第i(1<i<=n)個(gè)數(shù)據(jù)元素時(shí)，前面的i-1個(gè)數(shù)據(jù)元素已經(jīng)排好序，這時(shí)，用第i個(gè)數(shù)據(jù)元素的關(guān)鍵字與前面的i-1個(gè)數(shù)據(jù)元素的關(guān)鍵字順序進(jìn)行比較，找到插入位置后就將第i個(gè)數(shù)據(jù)元素插入。如此進(jìn)行n-1次插入，就完成了排序。以下是在順序表上實(shí)現(xiàn)的直接插入排序在順序表上進(jìn)行直接插入排序時(shí)，當(dāng)插入第i(1<i<=n)個(gè)數(shù)據(jù)元素時(shí)，前面的A0、A1、Ai-2已經(jīng)排好序，這時(shí)，用Ai-1的關(guān)鍵字依次與Ai-2,Ai-3,的關(guān)鍵字順序進(jìn)行比較，如果這些數(shù)據(jù)元素的關(guān)鍵字大于Ai-1的關(guān)鍵字，則將數(shù)據(jù)元素向后移一個(gè)位置，當(dāng)找到插入位置后就將Ai-1插入，就完成了A0,A1,An-1的排序。選擇排序選擇排序（xuanze）的算法基本思想是：a)開(kāi)始時(shí)設(shè)i的初始值為0。b)如果i<n-1，在數(shù)據(jù)元素序列Ai(An-1中，選出具有最小關(guān)鍵字的數(shù)據(jù)元素Ak；否則算法結(jié)束。c)若Ak不是這組數(shù)據(jù)元素中的第一個(gè)數(shù)據(jù)元素（ik），則將Ak與Ai這兩數(shù)據(jù)元素的位置對(duì)調(diào)；d)令i=i+1轉(zhuǎn)步驟 b)。冒泡排序：冒泡排序(maopao) 的基本思想是：設(shè)排序表中有n個(gè)數(shù)據(jù)元素。首先對(duì)排序表中第一，二個(gè)數(shù)據(jù)元素的關(guān)鍵字A0和A1進(jìn)行比較。如果前者大于后者，則進(jìn)行交換；然后對(duì)第二，三個(gè)數(shù)據(jù)做同樣的處理；重復(fù)此過(guò)程直到處理完最后兩個(gè)相鄰的數(shù)據(jù)元素。我們稱之為一趟冒泡，它將關(guān)鍵字最大的元素移到排序表的最后一個(gè)位置，其他數(shù)據(jù)元素一般也都向排序的最終位置移動(dòng)。然后進(jìn)行第二趟排序，對(duì)排序表中前n-1個(gè)元素進(jìn)行與上述同樣的操作，其結(jié)果使整個(gè)排序表中關(guān)鍵字次大的數(shù)據(jù)元素被移到An-2的位置。如此最多做n-1趟冒泡就能把所有數(shù)據(jù)元素排好序。堆排序：堆排序(duipai)sa.對(duì)排序表中的數(shù)據(jù)元素，利用堆的調(diào)整算法形成初始堆。b.輸出堆頂元素。c.對(duì)剩余元素重新調(diào)整形成堆。d.重復(fù)執(zhí)行第b、c步，直到所有數(shù)據(jù)元素被輸出。如果建立的堆滿足最大堆的條件，則堆的第一個(gè)數(shù)據(jù)元素A0具有最大的關(guān)鍵字，將A0與An-1對(duì)調(diào)，把具有最大關(guān)鍵字的數(shù)據(jù)元素交換到最后，再對(duì)前面的n-1個(gè)數(shù)據(jù)元素使用堆的調(diào)整算法，重新建立最大堆，結(jié)果把具有次最大關(guān)鍵字的數(shù)據(jù)元素又上浮到堆頂，即A 0的位置，再對(duì)調(diào)A0和An-2，如此反復(fù)執(zhí)行n-1次，最后得到全部排序好的數(shù)據(jù)元素序列。歸并排序：其基本思想是：設(shè)有兩個(gè)有序表A和B，其數(shù)據(jù)元素個(gè)數(shù)（表長(zhǎng)）分別為n和m，變量i和j分別是表A和表B的當(dāng)前檢測(cè)指針；設(shè)表C是歸并后的新有序表，變量k是它的當(dāng)前存放指針。開(kāi)始時(shí)i、j、k都分別指向A、B、C三個(gè)表的起始位置；然后根據(jù)Ai與Bj的關(guān)鍵字的大小，把關(guān)鍵字小的數(shù)據(jù)元素放到新表Ck中；且相應(yīng)的檢測(cè)指針（i或j）和存放指針k增加1.如此循環(huán)，當(dāng)i與j中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表CkCm+n中。下面的歸并算法中，兩個(gè)待歸并的有序表首尾相接存放在數(shù)組sourcetable.arr中，其中第一個(gè)表的下標(biāo)范圍從left到mid，另一個(gè)表的下標(biāo)范圍從mid+1到right。前一個(gè)表中有mid-left+1個(gè)數(shù)據(jù)元素，后一個(gè)表中有right mid個(gè)數(shù)據(jù)元素。歸并后得到的新有序表有right mid個(gè)數(shù)據(jù)元素。歸并后得到的新有序表存放在另一個(gè)輔助數(shù)組mergedtable.arr中，其下標(biāo)范圍從left到right。一趟歸并算法：設(shè)數(shù)組sourcetable.arr0到sourcetable.arrn-1中的n個(gè)數(shù)據(jù)元素已經(jīng)分為一些長(zhǎng)度為len的歸并項(xiàng)，將這些歸并項(xiàng)兩兩歸并，歸并成一些長(zhǎng)度為2len的歸并項(xiàng)，結(jié)果放到mergedtable.arr中。如果n不是2len的整數(shù)倍，則一趟歸并到最后，可能遇到兩種情況：剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和一個(gè)長(zhǎng)度不足len的歸并項(xiàng)，可用一次merge算法，將它們歸并成一個(gè)長(zhǎng)度小于2len的歸并項(xiàng)。只剩下一個(gè)歸并項(xiàng)，其長(zhǎng)度小于或等于len，可將它直接復(fù)制到數(shù)組mergedtable.arr中。在一趟歸并算法的基礎(chǔ)上，實(shí)現(xiàn)兩路歸并排序算法。在兩路歸并排序算法中，初始排序表存放在數(shù)組table.arr中,第一趟歸并將table.arr中的歸并項(xiàng)兩兩歸并，結(jié)果存放在輔助數(shù)組temptable.arr中。第二趟將temptable.arr中的歸并項(xiàng)兩兩歸并，結(jié)果放回原數(shù)組table.arr中，如此反復(fù)進(jìn)行。為了將最后歸并結(jié)果仍放在數(shù)組table.arr中，歸并趟數(shù)應(yīng)為偶數(shù)。如果做奇數(shù)趟就能完成時(shí)，最后還需要執(zhí)行一次一趟歸并過(guò)程，由于這時(shí)的歸并項(xiàng)長(zhǎng)度len>=n，因此在則趟歸并中while循環(huán)不執(zhí)行，只做把temptable.arr中的數(shù)據(jù)元素復(fù)制到table.arr的工作?；鶖?shù)排序：“基數(shù)排序法”（radix sort）則是屬于“分配式排序”（distribution sort），基數(shù)排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。具體可以參看后面的代碼進(jìn)行理解。其它：使用了stdlib頭文件里包含的系統(tǒng)函數(shù)，包括清屏函數(shù)和運(yùn)行時(shí)的暫停，增強(qiáng)了程序運(yùn)行時(shí)的效果。2.4 開(kāi)發(fā)日志在老師布置了大作業(yè)的題目后，我就把題目下載下來(lái)并進(jìn)行分析已選擇合適的題目。經(jīng)過(guò)我的慎重考慮，選擇了算法型大作業(yè)題目中的編寫七種排序算法的演示程序，覺(jué)得自己有能力把這道題目很好完成。在認(rèn)真分析連題目后，基本確定了整體的思路，但是其中有堆排序，歸并排序，基數(shù)排序我沒(méi)有在教材中接觸過(guò)，于是借助了圖書(shū)館和網(wǎng)絡(luò)上的資源，重點(diǎn)對(duì)這三的函數(shù)進(jìn)行編寫。在編寫大作業(yè)過(guò)程中大的困難我沒(méi)有遇到，只是有些小的疏忽常常導(dǎo)致程序無(wú)法運(yùn)行，如形參和實(shí)參的不一致等。我也在其中意識(shí)到對(duì)知識(shí)掌握的不夠熟練，在解決了這些問(wèn)題后，我覺(jué)得自己對(duì)程序的編寫更加熟練了，對(duì)問(wèn)題的分析也更加嚴(yán)謹(jǐn)了。在C程序設(shè)計(jì)的實(shí)驗(yàn)和理論考試之前代碼已基本完成。在考試結(jié)束后，我又對(duì)程序稍微進(jìn)行了修改，使之運(yùn)行時(shí)效果更好。接著開(kāi)始寫實(shí)驗(yàn)報(bào)告，整理自己的大作業(yè)。我對(duì)我的作業(yè)是很滿意的。3 程序調(diào)試及運(yùn)行3.1 程序運(yùn)行結(jié)果1.進(jìn)入程序運(yùn)行后所顯示的菜單：2.快速排序：3.插入排序：4.選擇排序：5.冒泡排序：6.堆排序：7.歸并排序：8.基數(shù)排序：9.結(jié)束：3.2 程序使用說(shuō)明1.打開(kāi)源程序，調(diào)試完畢后開(kāi)始運(yùn)行，開(kāi)始進(jìn)行七種算法的演示；2.按照說(shuō)明進(jìn)行輸入,選擇數(shù)字17即可進(jìn)入相應(yīng)的排序算法演示程序，選擇8結(jié)束程序；3.選擇排序的方法后，按要求輸入待排數(shù)據(jù)的個(gè)數(shù)，然后輸入待排序數(shù)據(jù)即可（數(shù)據(jù)排序結(jié)束后，會(huì)自動(dòng)清屏，進(jìn)入菜單進(jìn)行接下來(lái)的選擇）；4.應(yīng)當(dāng)注意，本演示程序?qū)?shù)據(jù)進(jìn)行的是升序；3.3 程序開(kāi)發(fā)總結(jié)在選擇這個(gè)題目時(shí)，我覺(jué)得難度系數(shù)10對(duì)我有挑戰(zhàn)性，并且我對(duì)排序有相對(duì)比較熟悉，所以就選了這個(gè)題目。但是在編寫過(guò)程中卻遇到很多問(wèn)題。我和我的同學(xué)進(jìn)行了討論，查閱了圖書(shū)館和網(wǎng)絡(luò)上的資料，結(jié)合力我個(gè)人對(duì)本題目的理解對(duì)各種問(wèn)題進(jìn)行了處理，學(xué)到了很多教材上沒(méi)有的知識(shí)。從這次實(shí)踐中，我意識(shí)到自己還有很多不足之處。能力也得到了提高。我在進(jìn)行編程時(shí)還需要翻書(shū)查找，對(duì)于這一點(diǎn)，只能說(shuō)對(duì)知識(shí)的學(xué)習(xí)還不夠扎實(shí)，所以有空時(shí)還應(yīng)該繼續(xù)熟悉這門課程。另外，就是對(duì)于錯(cuò)誤的處理，不能得心應(yīng)手，不能正確處理一些簡(jiǎn)單的錯(cuò)誤。對(duì)于邏輯上的錯(cuò)誤，不能夠立即找到出錯(cuò)點(diǎn)，往往需要向同學(xué)請(qǐng)教才能找出錯(cuò)誤，并且改正。我覺(jué)得這是自己獨(dú)自思考能力不高的問(wèn)題，遇事需要自己仔細(xì)想想，若還不能改正，再請(qǐng)教別人也不遲。從總體上說(shuō)，最終結(jié)果我很滿意，我覺(jué)得我所設(shè)計(jì)的程序操作方便，功能良好。我在上面花費(fèi)了很多時(shí)間和精力，對(duì)作業(yè)不斷進(jìn)行修改和完善，我很有成就感 。我的能力在這之中得到了提高。4 附件（源程序）# include<stdio.h># include<stdlib.h>/*快速排序*/void kuaisu(int A,int n)int i,j,k,t,p;for(i=0;i<n-1;i+)k=i;for(j=i+1;j<n;j+)if(Aj<Ak) k=j;t=Ak;Ak=Ai;Ai=t;printf("第%d趟:",i+1);for(p=0;p<n;p+)printf("%d ",Ap);printf("n");printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*插入排序*/void charu(int A,int n) int i,k,t,j,h=1;for(i=1;i<n;i+)t=Ai;k=i-1;while(t<Ak)Ak+1=Ak;k-;if(k=-1)break;printf("第%d趟:",h+);for(j=0;j<n;j+)printf("%d ",Aj);printf("n");Ak+1=t;printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*選擇排序*/void xuanze(int A,int n) int i,j,k,t,l,h=1;for(i=0;i<n-1;i+)k=i;for(j=i+1;j<n;j+)if(Aj<Ak) k=j;if(i!=k)t=Ai;Ai=Ak;Ak=t;printf("第%d趟:",h+);for(l=0;l<n;l+)printf("%d ",Al);printf("n");printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*冒泡排序*/void maopao(int A,int n) int i,j,t,h=1,p;for(j=0;j<n-1;j+)for(i=0;i<n-1-j;i+)if(Ai>Ai+1)t=Ai,Ai=Ai+1,Ai+1=t,p+;printf("第%d趟:",h+);for(p=0;p<n;p+)printf("%d ",Ap);printf("n");printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*堆排序*/void shift(int A , int i , int m) int k,t; t=Ai;k=2*i+1; while (k<m) if(k<m-1)&&(Ak<Ak+1) k+; if(t<Ak)Ai=Ak;i=k;k=2*i+1; else break; Ai=t;void duipai(int A , int n) /a 為排序數(shù)組，n為數(shù)組大小int i,k,h=1,j;for (i=n/2-1;i>=0;i-)shift(A,i,n); for (i=n-1;i>=1;i-)k=A0;A0=Ai;Ai=k;shift(A,0,i);printf("第%d趟:",h+);for(j=0;j<n;j+)printf("%d ",Aj);printf("n");printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*歸并排序*/void merge(int number,int first,int last,int mid) int number_temp10=0; int i=first,j=mid+1,k; for(k=0;k<=last-first;k+) if (i=mid+1) number_tempk=numberj+; continue; if (j=last+1) number_tempk=numberi+; continue; if (numberi<numberj) number_tempk=numberi+; else number_tempk=numberj+; for (i=first,j=0;i<=last;i+,j+) numberi = number_tempj;void merge_sort(int number,int first,int last) int mid=0; if(first<last) mid=(first+last)/2; merge_sort(number,first,mid); merge_sort(number,mid+1,last); merge(number,first,last,mid); void guibing(int a,int n)int i;merge_sort(a,0,n-1);printf("n排序結(jié)果:");for(i=0;i<n;i+) printf("%d ",ai);printf("n");printf("n");system("pause");system("CLS");/*基數(shù)排序*/void jishu(int data,int n)int temp1010=0; int order10=0; int i,j,k,q,lsd; k=0; q=1; while(q<=n) for(i=0;i<n;i+) lsd=(datai/q)%n); templsdorderlsd=datai; orderlsd+; for(i=0;i<n;i+) if(orderi != 0) for(j=0;j<orderi;j+) datak=tempij; k+; orderi = 0; q *= n; k = 0; printf("n排序結(jié)果:");for(i=0;i<n;i+)printf("%d ",datai);printf("n");printf("n");system("pause");system("CLS"); /*主函數(shù)*/ int main()int A100,p,n,i;while(1)printf("nt* 七種排序算法的演示程序 *n");printf("t* *n");printf("t* 1-快速排序 *n");printf("t* 2-插入排序 *n");printf("t* 3-選擇排序 *n");printf("t* 4-冒泡排序 *n");printf("t* 5- 堆排序 *n");printf("t* 6-歸并排序 *n");printf("t* 7-基數(shù)排序 *n");printf("t* 8-退出程序 *n");printf("t* *n");printf("t*nn");printf("請(qǐng)輸入序號(hào)進(jìn)行選擇:n");scanf("%d",&p);if(p=8)break;printf("請(qǐng)輸入待排序數(shù)的個(gè)數(shù):n");scanf("%d",&n);printf("請(qǐng)輸入待排序數(shù)據(jù):n");for(i=0;i<n;i+)scanf("%d",&Ai);switch(p)case 1:kuaisu(A,n);break;case 2:charu(A,n);break;case 3:xuanze(A,n);break;case 4:maopao(A,n);break;case 5:duipai(A,n);break;case 6:guibing(A,n);break;case 7:jishu(A,n);break;printf("nntttt謝謝您的使用nn");return 0;Email:chengyunhemail.nwpu.edu.cn19