西北工業(yè)大學(xué)程序設(shè)計大作業(yè).doc
《西北工業(yè)大學(xué)程序設(shè)計大作業(yè).doc》由會員分享,可在線閱讀,更多相關(guān)《西北工業(yè)大學(xué)程序設(shè)計大作業(yè).doc(19頁珍藏版)》請在裝配圖網(wǎng)上搜索。
學(xué) 院學(xué)院班 級學(xué) 號姓 名目錄1 摘要31.1 設(shè)計題目31.2 設(shè)計內(nèi)容31.3 開發(fā)工具31.4 應(yīng)用平臺32 詳細設(shè)計32.1 程序結(jié)構(gòu)32.2 主要功能42.3 函數(shù)實現(xiàn)52.4 開發(fā)日志73 程序調(diào)試及運行73.1 程序運行結(jié)果73.2 程序使用說明123.3 程序開發(fā)總結(jié)124 附件(源程序)121 摘要1.1 設(shè)計題目算法型大作業(yè)題目:編寫七種排序算法的演示程序。1.2 設(shè)計內(nèi)容編寫快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數(shù)排序函數(shù),通過主函數(shù)調(diào)用以實現(xiàn)七種排序算法的演示。1.3 開發(fā)工具Visual C+ 6.01.4 應(yīng)用平臺Windows 2000/XP/Vista 32位2 詳細設(shè)計2.1 程序結(jié)構(gòu)程序的整體結(jié)構(gòu)與流程見下圖所示。程序運行時在主菜單中輸入序號選擇排序方法或選擇結(jié)束程序,當進行某種排序方法后,在主函數(shù)中輸入待排數(shù)據(jù)個數(shù)和待排數(shù)據(jù),通過調(diào)用對應(yīng)的排序函數(shù)實現(xiàn)排序并輸出。該排序結(jié)束后再次進入主函數(shù),通過循環(huán)重復(fù)上述操作。其中,主函數(shù)中將數(shù)組地址和待排序數(shù)據(jù)個數(shù)傳遞給排序函數(shù),在排序函數(shù)中實現(xiàn)排序功能。輸出排序結(jié)果開始快速插入選擇冒泡堆排歸并基數(shù)選擇排序方法進入主菜單退出系統(tǒng)2.2 主要功能函數(shù)的功能為對快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數(shù)排序算法的演示。主函數(shù):程序運行時,可使運行者根據(jù)提醒輸入相關(guān)操作,從而進入不同的排序方法或者退出??焖倥判蚝瘮?shù):根據(jù)快速排序的算法,最后輸出插入排序函數(shù):根據(jù)插入排序的算法,最后輸出選擇排序函數(shù):根據(jù)選擇排序的算法,最后輸出冒泡排序函數(shù):根據(jù)冒泡排序的算法,最后輸出堆排序函數(shù):根據(jù)堆排序的算法,最后輸出歸并排序函數(shù):根據(jù)歸并排序的算法,最后輸出基數(shù)排序函數(shù):根據(jù)基數(shù)排序的算法,最后輸出2.3 函數(shù)實現(xiàn)主函數(shù):在主函數(shù)中對菜單輸出,通過switch語句中的case分支選擇所需要的排序方法;通過while循環(huán)使演示程序在運行時能夠持續(xù)進行快速排序: 快速排序(kuaisu)又被稱做分區(qū)交換排序,這是一種平均性能非常好的排序方法。其算法基本思想是:任取排序表中的某個數(shù)據(jù)元素(例如取第一個數(shù)據(jù)元素)作為基準,按照該數(shù)據(jù)元素的關(guān)鍵字大小,將整個排序表劃分為左右兩個子表: 左側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都小于基準數(shù)據(jù)元素的關(guān)鍵字。右側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都大于或等于基準數(shù)據(jù)元素的關(guān)鍵字,基準數(shù)據(jù)元素則排在這兩個子表中間(這也是該數(shù)據(jù)元素最終應(yīng)安放的位置),然后分別對這兩個子表重復(fù)施行上述方法的快速排序,直到所有的子表長度為1,則排序結(jié)束。插入排序:插入排序(charu)的基本思想:開始時把第一個數(shù)據(jù)元素作為初始的有序序列,然后從第二個數(shù)據(jù)元素開始依次把數(shù)據(jù)元素按關(guān)鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1i=n)個數(shù)據(jù)元素時,前面的i-1個數(shù)據(jù)元素已經(jīng)排好序,這時,用第i個數(shù)據(jù)元素的關(guān)鍵字與前面的i-1個數(shù)據(jù)元素的關(guān)鍵字順序進行比較,找到插入位置后就將第i個數(shù)據(jù)元素插入。如此進行n-1次插入,就完成了排序。以下是在順序表上實現(xiàn)的直接插入排序在順序表上進行直接插入排序時,當插入第i(1i=n)個數(shù)據(jù)元素時,前面的A0、A1、Ai-2已經(jīng)排好序,這時,用Ai-1的關(guān)鍵字依次與Ai-2,Ai-3,的關(guān)鍵字順序進行比較,如果這些數(shù)據(jù)元素的關(guān)鍵字大于Ai-1的關(guān)鍵字,則將數(shù)據(jù)元素向后移一個位置,當找到插入位置后就將Ai-1插入,就完成了A0,A1,An-1的排序。選擇排序選擇排序(xuanze)的算法基本思想是:a)開始時設(shè)i的初始值為0。b)如果i=n,因此在則趟歸并中while循環(huán)不執(zhí)行,只做把temptable.arr中的數(shù)據(jù)元素復(fù)制到table.arr的工作?;鶖?shù)排序:“基數(shù)排序法”(radix sort)則是屬于“分配式排序”(distribution sort),基數(shù)排序法又稱“桶子法”(bucket sort)或bin sort,顧名思義,它是透過鍵值的部份資訊,將要排序的元素分配至某些“桶”中,藉以達到排序的作用,基數(shù)排序法是屬于穩(wěn)定性的排序,其時間復(fù)雜度為O (nlog(r)m),其中r為所采取的基數(shù),而m為堆數(shù),在某些時候,基數(shù)排序法的效率高于其它的比較性排序法。具體可以參看后面的代碼進行理解。其它:使用了stdlib頭文件里包含的系統(tǒng)函數(shù),包括清屏函數(shù)和運行時的暫停,增強了程序運行時的效果。2.4 開發(fā)日志在老師布置了大作業(yè)的題目后,我就把題目下載下來并進行分析已選擇合適的題目。經(jīng)過我的慎重考慮,選擇了算法型大作業(yè)題目中的編寫七種排序算法的演示程序,覺得自己有能力把這道題目很好完成。在認真分析連題目后,基本確定了整體的思路,但是其中有堆排序,歸并排序,基數(shù)排序我沒有在教材中接觸過,于是借助了圖書館和網(wǎng)絡(luò)上的資源,重點對這三的函數(shù)進行編寫。在編寫大作業(yè)過程中大的困難我沒有遇到,只是有些小的疏忽常常導(dǎo)致程序無法運行,如形參和實參的不一致等。我也在其中意識到對知識掌握的不夠熟練,在解決了這些問題后,我覺得自己對程序的編寫更加熟練了,對問題的分析也更加嚴謹了。在C程序設(shè)計的實驗和理論考試之前代碼已基本完成。在考試結(jié)束后,我又對程序稍微進行了修改,使之運行時效果更好。接著開始寫實驗報告,整理自己的大作業(yè)。我對我的作業(yè)是很滿意的。3 程序調(diào)試及運行3.1 程序運行結(jié)果1.進入程序運行后所顯示的菜單:2.快速排序:3.插入排序:4.選擇排序:5.冒泡排序:6.堆排序:7.歸并排序:8.基數(shù)排序:9.結(jié)束:3.2 程序使用說明1.打開源程序,調(diào)試完畢后開始運行,開始進行七種算法的演示;2.按照說明進行輸入,選擇數(shù)字17即可進入相應(yīng)的排序算法演示程序,選擇8結(jié)束程序;3.選擇排序的方法后,按要求輸入待排數(shù)據(jù)的個數(shù),然后輸入待排序數(shù)據(jù)即可(數(shù)據(jù)排序結(jié)束后,會自動清屏,進入菜單進行接下來的選擇);4.應(yīng)當注意,本演示程序?qū)?shù)據(jù)進行的是升序;3.3 程序開發(fā)總結(jié)在選擇這個題目時,我覺得難度系數(shù)10對我有挑戰(zhàn)性,并且我對排序有相對比較熟悉,所以就選了這個題目。但是在編寫過程中卻遇到很多問題。我和我的同學(xué)進行了討論,查閱了圖書館和網(wǎng)絡(luò)上的資料,結(jié)合力我個人對本題目的理解對各種問題進行了處理,學(xué)到了很多教材上沒有的知識。從這次實踐中,我意識到自己還有很多不足之處。能力也得到了提高。我在進行編程時還需要翻書查找,對于這一點,只能說對知識的學(xué)習(xí)還不夠扎實,所以有空時還應(yīng)該繼續(xù)熟悉這門課程。另外,就是對于錯誤的處理,不能得心應(yīng)手,不能正確處理一些簡單的錯誤。對于邏輯上的錯誤,不能夠立即找到出錯點,往往需要向同學(xué)請教才能找出錯誤,并且改正。我覺得這是自己獨自思考能力不高的問題,遇事需要自己仔細想想,若還不能改正,再請教別人也不遲。從總體上說,最終結(jié)果我很滿意,我覺得我所設(shè)計的程序操作方便,功能良好。我在上面花費了很多時間和精力,對作業(yè)不斷進行修改和完善,我很有成就感 。我的能力在這之中得到了提高。4 附件(源程序)# include# include/*快速排序*/void kuaisu(int A,int n)int i,j,k,t,p;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(AjAk) k=j;t=Ak;Ak=Ai;Ai=t;printf(第%d趟:,i+1);for(p=0;pn;p+)printf(%d ,Ap);printf(n);printf(n排序結(jié)果:);for(i=0;in;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;in;i+)t=Ai;k=i-1;while(tAk)Ak+1=Ak;k-;if(k=-1)break;printf(第%d趟:,h+);for(j=0;jn;j+)printf(%d ,Aj);printf(n);Ak+1=t;printf(n排序結(jié)果:);for(i=0;in;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;in-1;i+)k=i;for(j=i+1;jn;j+)if(AjAk) k=j;if(i!=k)t=Ai;Ai=Ak;Ak=t;printf(第%d趟:,h+);for(l=0;ln;l+)printf(%d ,Al);printf(n);printf(n排序結(jié)果:);for(i=0;in;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;jn-1;j+)for(i=0;iAi+1)t=Ai,Ai=Ai+1,Ai+1=t,p+;printf(第%d趟:,h+);for(p=0;pn;p+)printf(%d ,Ap);printf(n);printf(n排序結(jié)果:);for(i=0;in;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 (km) if(km-1)&(AkAk+1) k+; if(t=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;jn;j+)printf(%d ,Aj);printf(n);printf(n排序結(jié)果:);for(i=0;in;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 (numberinumberj) 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(firstlast) 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;in;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;in;i+) lsd=(datai/q)%n); templsdorderlsd=datai; orderlsd+; for(i=0;in;i+) if(orderi != 0) for(j=0;jorderi;j+) datak=tempij; k+; orderi = 0; q *= n; k = 0; printf(n排序結(jié)果:);for(i=0;in;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(請輸入序號進行選擇:n);scanf(%d,&p);if(p=8)break;printf(請輸入待排序數(shù)的個數(shù):n);scanf(%d,&n);printf(請輸入待排序數(shù)據(jù):n);for(i=0;in;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- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 西北工業(yè)大學(xué) 程序設(shè)計 作業(yè)
鏈接地址:http://ioszen.com/p-6613142.html