C語言課程設(shè)計(jì)說明書排序算法系統(tǒng)設(shè)計(jì)

1、摘 要c是一種通用的程序設(shè)計(jì)語言，c語言在很多方面繼承和發(fā)展了以往許多高級程序設(shè)計(jì)語言的成功經(jīng)驗(yàn)和特色，具有書寫格式自由、數(shù)據(jù)類型豐富、語句功能強(qiáng)大、執(zhí)行速度快和存儲控制能力強(qiáng)等優(yōu)點(diǎn)。排序算法系統(tǒng)設(shè)計(jì)是關(guān)于順序表排序算法來設(shè)計(jì)的一個系統(tǒng)。整個系統(tǒng)從符合操作簡便、界面友好、靈活、實(shí)用、安全的要求出發(fā)，完成順序表排序算法的全過程，包括直接插入排序、二分法插入排序、直接選擇排序、冒泡排序、兩路冒泡排序、分塊歸并排序、歸并排序以及重新生成隨機(jī)數(shù)組。本課程主要介紹了本課題的開發(fā)背景，所要完成的功能和開發(fā)的過程。重點(diǎn)說明了系統(tǒng)的設(shè)計(jì)思路、總體設(shè)計(jì)、各個功能模塊的設(shè)計(jì)與實(shí)現(xiàn)方法。關(guān)鍵詞：排序算法系統(tǒng)，c語言

2、，數(shù)據(jù)結(jié)構(gòu)，cfreev5.0目錄1課題背景的介紹11.1 課題背景11.2 目的12需求分析22.1 數(shù)據(jù)需求分析22.2 功能需求分析23系統(tǒng)總體設(shè)計(jì)33.1 系統(tǒng)模塊劃分33.2 系統(tǒng)模塊結(jié)構(gòu)圖34系統(tǒng)詳細(xì)設(shè)計(jì)44.1 系統(tǒng)主界面設(shè)計(jì)44.2初始化學(xué)生信息44.3查找學(xué)生信息44.4刪除學(xué)生信息54.5更新學(xué)生信息54.6排序74.7統(tǒng)計(jì)學(xué)生信息114.8插入學(xué)生信息115系統(tǒng)連編與運(yùn)行126總 結(jié)13參考文獻(xiàn)141 課題背景的介紹1.1 課題背景算法是程序的核心，對數(shù)據(jù)進(jìn)行排序是各種管理系統(tǒng)中不可缺少的一部分，大量的數(shù)據(jù)進(jìn)行排序處理，算法的好壞決定著程序的執(zhí)行效率以及用戶的使用感受，而

3、作為最為常用的順序表存儲結(jié)構(gòu)排序，我們針對其設(shè)計(jì)了一個排序算法系統(tǒng)，并將歸并排序和冒泡排序進(jìn)行優(yōu)化設(shè)計(jì)，這也是我們研究這個課程的目的。為了能夠更好的來實(shí)現(xiàn)對順序表結(jié)構(gòu)的數(shù)據(jù)排序，通過對日常工作的詳細(xì)調(diào)查，搜集了大量的資料，從系統(tǒng)結(jié)構(gòu)的組織，功能的實(shí)現(xiàn)，技術(shù)的要求以及可行性等多方面進(jìn)行考慮，認(rèn)為本課題是一個適應(yīng)現(xiàn)今排序算法需求的計(jì)算機(jī)排序算法系統(tǒng)，具有一定的實(shí)際開發(fā)價(jià)值和使用價(jià)值。1.2 目的本課題運(yùn)用c語言進(jìn)行開發(fā)，c語言能夠簡單的進(jìn)行編譯一些程序，來實(shí)現(xiàn)對一些問題的解決。它雖然比較簡單的處理一些問題，但卻有更高的效率。它能夠被大多數(shù)用戶所接受，因?yàn)樗軌虺尸F(xiàn)出清晰的界面，是人們能夠很好的理解

4、。能在一些方面給人們更好的服務(wù)，成為人們的好幫手。經(jīng)過這一個學(xué)期對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，我們都學(xué)到了不少東西，可能有些學(xué)的還不夠理想，但無論如何這些知識都為我們的下一步學(xué)習(xí)打下了堅(jiān)實(shí)的基礎(chǔ)。做這么一個課程設(shè)計(jì)，一方面是為了檢查我們一個學(xué)期以來的學(xué)習(xí)成果，另一方面也是為了讓我們進(jìn)一步的掌握和運(yùn)用它，同時也讓我們認(rèn)清自己的不足之處和薄弱環(huán)節(jié)，加以彌補(bǔ)和加強(qiáng)。2 需求分析隨著日常處理數(shù)據(jù)規(guī)模的不斷擴(kuò)大，程序向著大型化，規(guī)?；l(fā)展，而對于數(shù)據(jù)排序效率的要求不斷提高。在這種情況下單靠人工來處理信息不但顯得大不從心，而且極容易出錯。因此，需要開發(fā)排序算法系統(tǒng)，該系統(tǒng)可以實(shí)現(xiàn)由計(jì)算機(jī)代替人工執(zhí)行一系列復(fù)雜而繁瑣的

5、排序操作，使得程序設(shè)計(jì)人員可以輕松快捷的完成對各種數(shù)據(jù)的排序管理的任務(wù)。2.1 數(shù)據(jù)需求分析本系統(tǒng)的主要數(shù)據(jù)是順序表數(shù)組。為了有更好的排序算法展示效果，數(shù)組的數(shù)據(jù)由單獨(dú)的隨機(jī)數(shù)組生成函數(shù)創(chuàng)建。2.2 功能需求分析本系統(tǒng)主要實(shí)現(xiàn)對數(shù)據(jù)的各種排序算法，需要實(shí)現(xiàn)以下幾個方面的功能：（1）直接插入排序（2）二分法插入排序（3）直接選擇排序（4）冒泡排序（5）兩路冒泡排序（6）分塊歸并排序（7）歸并排序（8）重新生成隨機(jī)數(shù)組3 系統(tǒng)總體設(shè)計(jì)3.1 系統(tǒng)模塊劃分本系統(tǒng)主要是對數(shù)據(jù)的排序算法，包括了排序算法有：直接插入排序，二分法插入排序，直接選擇排序，冒泡排序，兩路冒泡排序，分塊歸并排序，歸并排序。整個系

6、統(tǒng)分為以下幾個模塊。1、菜單模塊 本模塊實(shí)現(xiàn)菜單列表，通過用戶選擇列表調(diào)用相關(guān)函數(shù)實(shí)現(xiàn)功能。2、排序算法模塊本模塊用于實(shí)現(xiàn)對數(shù)據(jù)的各種排序算法。其中包括：1、直接插入排序2、二分法插入排序3、直接選擇排序4、冒泡排序排序5、兩路冒泡排序6、分塊歸并排序7、歸并排序3.2系統(tǒng)模塊結(jié)構(gòu)圖根據(jù)排序算法系統(tǒng)功能設(shè)計(jì)，對應(yīng)的系統(tǒng)模塊結(jié)構(gòu)圖如圖3.2.1所示：圖3.2.1 系統(tǒng)模塊結(jié)構(gòu)圖冒泡排序歸并排序法分塊歸并排序兩路冒泡排序兩路冒泡排序二分法排序直接插入法直接選擇法退出各種排序算法重新生成數(shù)組程序菜單4 系統(tǒng)詳細(xì)設(shè)計(jì)4.1 系統(tǒng)主界面設(shè)計(jì)統(tǒng)過對該系統(tǒng)設(shè)計(jì)的了解與討論，同時也為了廣大使用者的方便與快捷。

7、我們最后設(shè)計(jì)了這樣的一個界面。首先要讓使用者明白怎樣使用此系統(tǒng)。這就需要通過界面來給他們一個清晰而明白的空間。而我們設(shè)計(jì)的這個界面恰好符合了這一要求。通過調(diào)用界面函數(shù)來使使用者能夠很方便的進(jìn)行各種排序算法的操作。doputlogo();printf( 1直接插入排序n);printf( 2二分法插入排序n);printf( 3直接選擇排序n);printf( 4冒泡排序n);printf( 5兩路冒泡排序n);printf( 6分塊歸并排序 n);printf( 7歸并排序n);printf( 8重新生成隨機(jī)數(shù)組n);printf( 9退出n);printf(n 請用鍵盤選擇：);key=us

8、erchoice(123456789); /提高運(yùn)行效率 確保每一次循環(huán)都有效if(key != 9)cls;switch(key)case 1:/直接插入排序 tmp = straitsort(l); outputsqlist(tmp); break;case 2:/二分法插入排序 tmp = bisort(l); outputsqlist(tmp); break;case 3:/直接選擇排序 tmp = directbisort(l); outputsqlist(tmp); break; case 4:/冒泡排序 tmp = maopaobisort(l); outputsqlist(tm

9、p); break; case 5:/兩路冒泡排序 tmp = twinbubblesort(l); outputsqlist(tmp); break; case 6:/分塊歸并排序 tmp = l; showmergerlistplus(l, s); break; case 7:/歸并排序 tmp = l; mergesort(tmp); outputsqlist(tmp); break; case 8:/重新生成隨機(jī)數(shù)組 createsqlist(l);/創(chuàng)建隨機(jī)數(shù)數(shù)組 outputsqlist(l); break;if(key != 9)pause;while(key!=9);4.2創(chuàng)建

10、部分有序隨機(jī)數(shù)組為排序算法創(chuàng)建隨機(jī)數(shù)組。void createsqlist(sqlist &l)sqlist tmp;l = tmp;int irand;/隨機(jī)數(shù) int rndlength;/隨機(jī)有序數(shù)個數(shù) printf(請輸入數(shù)組長度：); do scanf(%d, &l.length); if (l.length maxsize) printf(輸入有誤！請重新輸入n); while (l.length maxsize); srand(unsigned)time(null);/初始化隨機(jī)數(shù) for(int i=0; i= l.length)/檢查生成隨機(jī)數(shù)數(shù)量是否超過要求數(shù)量 rndle

11、ngth = l.length - i; printf(n%d個隨機(jī)數(shù) 已生成%d個:, rndlength,i); for(int j=0; jsta = -1; p-end = -1;/ -1 + 1 = 0 即為初個分組起始下標(biāo) for(i=0; i l.datai)/*找到位置?。ó?dāng)前數(shù)小于tmp）*/ r = (spscope *)malloc(sizeof(spscope) r-sta = p-end + 1;r-end = i - 1;p-next = r; p = r; tmp = l.datai; r = (spscope *)malloc(sizeof(spscope);/

12、補(bǔ)上末尾最后一組元素 r-sta = p-end + 1;r-end = i - 1; p-next = r; p = r; p-next = null;/*合并兩個數(shù)組塊*/void mergerlist(sqlist &l, spscope *s1, spscope *s2)int *temp;/臨時存儲排序后的合并數(shù)組 int p=0;/p為temp數(shù)組下標(biāo) int i=s1-sta;int j=s2-sta;temp = (int *)malloc(s2-end - s1-sta + 1)*sizeof(int); while(iend & jend)/塊比較后取數(shù) if(l.data

13、i l.dataj)tempp = l.datai;i+;elsetempp = l.dataj;j+;p+;if(i end)/剩余部分直接插入temp數(shù)組末尾 while(i end)tempp = l.datai;i+;p+;else if(j != s2-end)while(j end)tempp = l.dataj;j+;p+;for(int i=0,j=s1-sta; p0; p-,i+,j+)/用temp數(shù)組覆蓋原數(shù)組 l.dataj = tempi;/*合并所有數(shù)組塊*/ void mergerlistall(sqlist &l, spscope s)spscope *s1,

14、*s2, *p;s1 = s.next;s2 = s1-next;int i=1;while(s.next-next != null)/只要分割表內(nèi)有兩個以上元素就繼續(xù)循環(huán) printf(nn%d-%d %d-%d, s1-sta,s1-end, s2-sta,s2-end);mergerlist(l, s1, s2);/合并塊 p = s2;/分割表合并 s1-end = s2-end;s1-next = s2-next;s1 = s1-next;/將指針指向下兩個元素if(s1 != null)/若s1為null，則訪問s1-next將會出錯！ s2 = s1-next;elses2 =

15、null;free(p);if(s2 = null)/組合已到末尾 重頭繼續(xù)開始合并 s1 = s.next;s2 = s1-next;printf(n*第%d次合并*, i+);outputlist(l);4.4兩路冒泡排序 本算法是對冒泡排序算法的改進(jìn)算法。/*兩路冒泡排序*/sqlist twinbubblesort(sqlist l) int i,j,k,l;int exchangemax, exchangemin;/是否發(fā)生交換標(biāo)記 int tmp;/交換臨時變量 for(i=0; il.length-1; i+) /冒泡出一個最大數(shù) exchangemax = 0; j = i;

16、while(j l.dataj+1)/找到位置！ 交換（找最大） exchangemax = 1; tmp = l.dataj; l.dataj = l.dataj+1; l.dataj+1 = tmp; j+; if(exchangemax = 0) return l; /冒泡出一個最小數(shù) exchangemin = 0; k = i;/起始下標(biāo) l = l.length-1-i-1;while(k l)if(l.datal l.datal-1)/找到位置！ 交換（找最?。?exchangemin = 1; tmp = l.datal; l.datal = l.datal-1; l.data

17、l-1 = tmp; l-;if(exchangemin = 0) return l; /輸出結(jié)果 printf(n); for(int p=0; pl.length; p+) printf(%d , l.datap); printf(n); return l;4.5直接插入排序/*直接插入排序*/sqlist straitsort(sqlist l) int i,j,x; for(i=1; i-1)&(l.datajx) l.dataj+1=l.dataj; j-; l.dataj+1=x; return l;4.6二分法插入排序/*二分法插入排序*/sqlist bisort(sqlist

18、 l) int i,low,high,mid,x,k; for(i=1; i=l.length-1; i+) x=l.datai; low=0; high=i-1; while(lowx) high=mid-1; else low=mid+1; for(k=i-1; k=low; k-) l.datak+1= l.datak; l.datahigh+1=x; return l;4.7直接選擇排序/*直接選擇排序*/sqlist directbisort(sqlist l) int i,k,j,x; for(i=0; i=l.length-2; i+) k=i; for(j=i+1; jl.da

19、taj) k=j; if(k!=i) x=l.datak; l.datak=l.datai; l.datai=x; return l;4.8冒泡排序/*冒泡排序*/sqlist maopaobisort(sqlist l) int i,j,k,flag; for(i=0; i=l.length-2; i+) flag=0; j=0; while(j=l.dataj+1) flag=1; k=l.dataj; l.dataj=l.dataj+1; l.dataj+1=k; j+; if (flag=0) return l; return l;4.9歸并排序/*歸并排序*/void merge(s

20、qlist &l, int low, int mid, int high)int *temp;/臨時存儲排序后的合并數(shù)組 int i=low, j=mid+1, k=0;temp = (int *)malloc(high - low + 1)*sizeof(int);/動態(tài)分配數(shù)組空間 while(i=mid & j=high)if(l.datai l.dataj)tempk = l.datai;i+;k+;elsetempk = l.dataj;j+;k+;while(i = mid)tempk = l.datai;i+;k+;while(j = high)tempk = l.dataj;j

21、+;k+;for(k=0,i=low; i=high; k+,i+)/用temp數(shù)組覆蓋原數(shù)組 l.datai = tempk;void mergepass(sqlist &l, int length, int n)int i;for(i=0; i+2*length-1n; i=i+2*length)merge(l,i,i+length-1,i+2*length-1);if(i+length-1 n)merge(l,i,i+length-1,n-1); void mergesort(sqlist &l)int length;for(length=1;lengthl.length;length=2*length)mergepass(l,length,l.length);5 系統(tǒng)連編與運(yùn)行一個應(yīng)用系統(tǒng)設(shè)計(jì)和創(chuàng)建完成后，還必須進(jìn)行連編，以便生成一個可執(zhí)行文件供最終用戶使用。連編完成后還要運(yùn)行，以檢查整個系統(tǒng)的完整性和準(zhǔn)確性，同時還可增加程序代碼的