年4月19日西北工業大學C語言課程設計大作業文檔僅供參考，不當之處，請聯系改正。學院電子信息學院班級08031302班學號姓名張昌武摘要本次大作業包括一個標準型大作業，一個界面型大作業，兩個數學型大作業和一個算法型大作業。本次聯系我選擇的題目是：A.數學型a.歌星大獎賽b.求最大數B.標準型 a.打印指定年份的公歷表和農歷表C.算法型a.七種排序算法D.界面型a.OpenGL圖形庫程序目錄TOC\o"1-4"\h\z1摘要 31.1設計題目 31.2設計內容 31.3開發工具 41.4應用平臺 42詳細設計 42.1程序結構 42.2主要功能 182.3函數實現 182.4開發日志 253程序調試及運行 313.1程序運行結果 313.2程序使用說明 363.3程序開發總結 364附件（源程序） 36

1摘要1.1設計題目A.數學型a.歌星大獎賽b.求最大數B.標準型a.打印指定年份的公歷表和農歷表C.算法型a.七種排序算法D.界面型a.OpenGL圖形庫程序1.2設計內容A.數學型a.十個評委打分，分數在1~100之間，選手最后得分為：去掉一個最高分和一個最低分后其余8個分數的平均值。b.求555555的約數中的最大三位數B.標準型a.打印指定年份的公歷表和農歷表C.算法型a.七種排序算法：快速排序插入排序選擇排序冒泡排序堆排序歸并排序基數排序D.界面型a.OpenGL圖形庫程序:繪制黑白框繪制螺旋曲線繪制彩色立方體1.3開發工具codeblock1.4應用平臺Windows/XP/Vista32位/win7、82詳細設計2.1程序結構A.數學型a.十個評委打分，分數在1~100之間，選手最后得分為：去掉一個最高分和一個最低分后其余8個分數的平均值。該題涉及到數組存儲b.求555555的約數中的最大三位數：該題只用到循環和判斷語句，從999向下搜索即可B.標準型a.打印指定年份的公歷表和農歷表年歷的設計與計算，應首先判斷“某年某月某日是星期幾”，即能被4且不能被100整除或能被400整除的數。這樣，接下來的事情就簡單了，輸入年份，打印出相應的日歷。C.算法型a.七種排序算法：快速排序(QuickSort)

劃分的關鍵是要求出基準記錄所在的位置pivotpos,編程時候的關鍵點快速排序：既然能把冒泡KO掉，馬上就激起我們的興趣，tnd快排咋這么快，一定要好好研究一下。首先上圖：

從圖中我們能夠看到：left指針，right指針，base參照數。其實思想是蠻簡單的，就是經過第一遍的遍歷（讓left和right指針重合）來找到數組的切割點。第一步：首先我們從數組的left位置取出該數（20）作為基準（base）參照物。第二步：從數組的right位置向前找，一直找到比（base）小的數，

如果找到，將此數賦給left位置（也就是將10賦給20），

此時數組為：10，40，50，10，60，

left和right指針分別為前后的10。第三步：從數組的left位置向后找，一直找到比（base）大的數，

如果找到，將此數賦給right的位置（也就是40賦給10），

此時數組為：10，40，50，40，60，

left和right指針分別為前后的40。第四步：重復“第二,第三“步驟，直到left和right指針重合，

最后將（base）插入到40的位置，

此時數組值為：10，20，50，40，60，至此完成一次排序。第五步：此時20已經潛入到數組的內部，20的左側一組數都比20小，20的右側作為一組數都比20大，以20為切入點對左右兩邊數按照"第一，第二，第三，第四"步驟進行，最終快排大功告成。

快速排序具有最好的平均性能（averagebehavior），但最壞性能（worstcasebehavior）和插入排序相同，也是O(n^2)。比如一個序列5,4,3,2,1，要排為1,2,3,4,5。按照快速排序方法，每次只會有一個數據進入正確順序，不能把數據分成大小相當的兩份，很明顯，排序的過程就成了一個歪脖子樹，樹的深度為n，那時間復雜度就成了O(n^2)。盡管如此，需要排序的情況幾乎都是亂序的，自然性能就保證了。據書上的測試圖來看，在數據量小于20的時候，插入排序具有最好的性能。當大于20時，快速排序具有最好的性能，歸并(mergesort)和堆排序(heapsort)也望塵莫及，盡管復雜度都為nlog2(n)。

1、算法思想

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，一般稱其為分治法(Divide-and-ConquerMethod)。

（1）分治法的基本思想

分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

（2）快速排序的基本思想

設當前待排序的無序區為R[low..high]，利用分治法可將快速排序的基本思想描述為：

①分解：

在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續的排序。

注意：

劃分的關鍵是要求出基準記錄所在的位置pivotpos。劃分的結果能夠簡單地表示為(注意pivot=R[pivotpos])：

R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

其中low≤pivotpos≤high。

②求解：

經過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。③組合：

因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。

2、快速排序算法QuickSort

voidQuickSort(SeqListR，intlow，inthigh)

{//對R[low..high]快速排序

intpivotpos；//劃分后的基準記錄的位置

if(low<high){//僅當區間長度大于1時才須排序

pivotpos=Partition(R，low，high)；//對R[low..high]做劃分

QuickSort(R，low，pivotpos-1)；//對左區間遞歸排序

QuickSort(R，pivotpos+1，high)；//對右區間遞歸排序

}

}//QuickSort

注意：

為排序整個文件，只須調用QuickSort(R，1，n)即可完成對R[l..n]的排序。插入排序算法描述

插入排序：插入即表示將一個新的數據插入到一個有序數組中，并繼續保持有序。例如有一個長度為N的無序數組，進行N-1次的插入即能完成排序；第一次，數組第1個數認為是有序的數組，將數組第二個元素插入僅有1個有序的數組中；第二次，數組前兩個元素組成有序的數組，將數組第三個元素插入由兩個元素構成的有序數組中第N-1次，數組前N-1個元素組成有序的數組，將數組的第N個元素插入由N-1個元素構成的有序數組中，則完成了整個插入排序。以下面5個無序的數據為例：6527596458（文中僅細化了第四次插入過程）第1次插入:2765596458第2次插入:2759656458第3次插入:2759646558第4次插入:2758596465二.算法分析平均時間復雜度：O(n2)空間復雜度：O(1)

(用于記錄需要插入的數據)穩定性：穩定選擇排序算法描述

選擇排序：比如在一個長度為N的無序數組中，在第一趟遍歷N個數據，找出其中最小的數值與第一個元素交換，第二趟遍歷剩下的N-1個數據，找出其中最小的數值與第二個元素交換第N-1趟遍歷剩下的2個數據，找出其中最小的數值與第N-1個元素交換，至此選擇排序完成。以下面5個無序的數據為例：5612809120（文中僅細化了第一趟的選擇過程）第1趟：1256809120第2趟：1220809156第3趟：1220569180第4趟：1220568091算法分析平均時間復雜度：O(n2)空間復雜度：O(1)

(用于交換和記錄索引)穩定性：不穩定（比如序列【5，5，3】第一趟就將第一個[5]與[3]交換，導致第一個5挪動到第二個5后面）冒泡排序冒泡排序法的基本思想：（以升序為例）含有n個元素的數組原則上要進行n-1次排序。對于每一躺的排序，從第一個數開始，依次比較前一個數與后一個數的大小。如果前一個數比后一個數大，則進行交換。這樣一輪過后，最大的數將會出現稱為最末位的數組元素。第二輪則去掉最后一個數，對前n-1個數再按照上面的步驟找出最大數，該數將稱為倒數第二的數組元素n-1輪過后，就完成了排序。若要以降序順序排列，則只需將

if(array[j]>array[j+1])語句中的大于號改為小于號即可。堆排序

堆排序是利用堆的性質進行的一種選擇排序。下面先討論一下堆。1.堆

堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。

堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質可知大頂堆的堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。2.堆排序的思想

利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。

其基本思想為(大頂堆)：

1)將初始待排序關鍵字序列(R1,R2Rn)構建成大頂堆，此堆為初始的無序區；

2)將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n];

3)由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

操作過程如下：

1)初始化堆：將R[1..n]構造為堆；

2)將當前無序區的堆頂元素R[1]同該區間的最后一個記錄交換，然后將新的無序區調整為新的堆。

因此對于堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程，只不過構造初始堆是對所有的非葉節點都進行調整。

下面舉例說明：

給定一個整形數組a[]={16,7,3,20,17,8}，對其進行堆排序。

首先根據該數組元素構建一個完全二叉樹，得到

然后需要構造初始堆，則從最后一個非葉節點開始調整，調整過程如下：20和16交換后導致16不滿足堆的性質，因此需重新調整這樣就得到了初始堆。即每次調整都是從父節點、左孩子節點、右孩子節點三者中選擇最大者跟父節點進行交換(交換之后可能造成被交換的孩子節點不滿足堆的性質，因此每次交換之后要重新對被交換的孩子節點進行調整)。有了初始堆之后就能夠進行排序了。此時3位于堆頂不滿堆的性質，則需調整繼續調整

這樣整個區間便已經有序了。

從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，而樹形選擇排序恰好利用樹形的特點保存了部分前面的比較結果，因此能夠減少比較次數。對于n個關鍵字序列，最壞情況下每個節點需比較log2(n)次，因此其最壞情況下時間復雜度為nlogn。堆排序為不穩定排序，不適合記錄較少的排序。歸并排序歸并排序的基本操作是

將兩個或兩個以上的記錄有序序列歸并為一個有序序列。最簡單的情況是，只含一個記錄的序列顯然是個有序序列，經過"逐趟歸并"使整個序列中的有序子序列的長度逐趟增大，

直至整個記錄序列為有序序列止。

它的基本操作是將兩個相鄰的有序子序列"歸并"為一個有序序列，

如右側所示。這個操作對順序表而言是極其容易實現的，只要依關鍵字從小到大進行"復制"即可基數排序簡略概述：基數排序是經過“分配”和“收集”過程來實現排序。而這個思想該如何理解呢？請看以下例子。（1）假設有欲排數據序列如下所示：73

22

93

43

55

14

28

65

39

81首先根據個位數的數值，在遍歷數據時將它們各自分配到編號0至9的桶（個位數值與桶號一一對應）中。分配結果（邏輯想象）如下圖所示：分配結束后。接下來將所有桶中所盛數據按照桶號由小到大（桶中由頂至底）依次重新收集串起來，得到如下依然無序的數據序列：81

22

73

93

43

14

55

65

28

39接著，再進行一次分配，這次根據十位數值來分配（原理同上），分配結果（邏輯想象）如下圖所示：分配結束后。接下來再將所有桶中所盛的數據（原理同上）依次重新收集串接起來，得到如下的數據序列：14

22

28

39

43

55

65

73

81

93觀察能夠看到，此時原無序數據序列已經排序完畢。如果排序的數據序列有三位數以上的數據，則重復進行以上的動作直至最高位數為止。那么，到這里為止，你覺得你是不是一個細心的人？不要不假思索的回答我。不論回答什么樣的問題，都要做到心比頭快，頭比嘴快。仔細看看你對整個排序的過程中還有哪些疑惑？真看不到？覺得我做得很好？抑或前面沒看懂？如果你看到這里真心沒有意識到或發現這個問題，那我告訴你：悄悄去找個墻角蹲下用小拇指畫圈圈（好好反省反省）。追問：觀察原無序數據序列中73

93

43三個數據的順序，在經過第一次（按照個位數值，它們三者應該是在同一個桶中）分配之后，在桶中順序由底至頂應該為73

93

43（即就是裝的遲的在最上面，對應我們上面的邏輯想象應該是43

93

73），對吧？這個應該能夠想明白吧？理論上應該是這樣的。可是，可是，可是分配后很明顯在3號桶中三者的順序剛好相反。這點難道你沒有發現嗎？或者是發現了覺得不屑談及（算我貽笑大方）？其實這個也正是基數排序穩定性的原因（分配時由末位向首位進行），請看下文的詳細分析。再思考一個問題：既然我們能夠從最低位到最高位進行如此的分配收集，那么是否能夠由最高位到最低位依次操作呢？答案是完全能夠的。基于兩種不同的排序順序，我們將基數排序分為LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由數值的最右邊（低位）開始，而MSD則相反，由數值的最左邊（高位）開始。注意一點：LSD的基數排序適用于位數少的數列，如果位數多的話，使用MSD的效率會比較好。MSD的方式與LSD相反，是由高位數為基底開始進行分配，但在分配之后并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照下一數位的值分配到“子桶”中。在進行完最低位數的分配后再合并回單一的數組中。（2）我們把撲克牌的排序看成由花色和面值兩個數據項組成的主關鍵字排序。要求如下：花色順序：梅花<方塊<紅心<黑桃面值順序：2<3<4<...<10<J<Q<K<A那么，若要將一副撲克牌排成下列次序：梅花2，...，梅花A，方塊2，...，方塊A，紅心2，...，紅心A，黑桃2，...，黑桃A。有兩種排序方法：<1>先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。稱為"最高位優先"(MSD)法。<2>先按面值由小到大排列成13堆，然后從小到大收集起來；再按花色不同分成四堆，最后順序收集起來。稱為"最低位優先"(LSD)法。【2】代碼實現（1）MSD法實現最高位優先法一般是一個遞歸的過程：<1>先根據最高位關鍵碼K1排序，得到若干對象組，對象組中每個對象都有相同關鍵碼K1。<2>再分別對每組中對象根據關鍵碼K2進行排序，按K2值的不同，再分成若干個更小的子組，每個子組中的對象具有相同的K1和K2值。<3>依此重復，直到對關鍵碼Kd完成排序為止。<4>

最后，把所有子組中的對象依次連接起來，就得到一個有序的對象序列。（2）LSD法實現最低位優先法首先依據最低位關鍵碼Kd對所有對象進行一趟排序，再依據次低位關鍵碼Kd-1對上一趟排序的結果再排序，依次重復，直到依據關鍵碼K1最后一趟排序完成，就能夠得到一個有序的序列。使用這種排序方法對每一個關鍵碼進行排序時，不需要再分組，而是整個對象組。【3】基數排序穩定性分析基數排序是穩定性排序算法，那么，到底如何理解它所謂的穩定特性呢？比如：我們有如下欲排數據序列：下面選擇LSD邏輯演示第一次按個位數值分配，結果如下圖所示：

然后收集數據結果如下：第二次按十位數值分配，結果如下圖所示：然后收集數據結果如下：注意：分配時是從欲排數據序列的末位開始進行，逐次分配至首位。D.界面型a.OpenGL圖形庫程序openGL（OpenGraphicsLibrary）從本質上說，它是一個3D圖形和模型庫，具有高度的移植性。我們能夠將openGL看做是一個C運行時的函數庫，這個函數庫能夠幫助我們繪制二維或三維的圖像。靜態鏈接庫和動態鏈接庫靜態庫：lib文件。編譯時代碼編譯進exe中，會使得程序體積非常龐大。不利于模塊的共享。優點：不會有dllhell的問題。仿佛“企業間的吞并”。動態庫：dll文件。代碼在dll中，其它程序調用dll中的代碼，多個程序能夠共享。缺點：dllhell(dll地獄)，版本問題。另外，主要用到的就是“glut.h”這個頭文件，它包括了我們所需的大多數函數，直接調用很方便！我們利用OpenGl函數庫編寫了三個簡單的程序，分別是：繪制黑白框、繪制螺旋曲線、繪制彩色立方體。2.2主要功能A.數學型a.十個評委打分，分數在1~100之間，選手最后得分為：去掉一個最高分和一個最低分后其余8個分數的平均值。該題主要實現賽場的積分統計b.求555555的約數中的最大三位數該題主要實現一個數的約數的求解B.標準型a.打印指定年份的公歷表和農歷表該題主要實現制定年月日期的輸出C.算法型a.七種排序算法：快速排序插入排序選擇排序冒泡排序堆排序歸并排序基數排序該題主要實現一組數據的排序D.界面型a.OpenGL圖形庫程序該題主要實現OpenGl圖形庫在Windows系統下的圖形設計/*請在這里說明你的大作業程序功能，并詳細描述它們實現的原理和方法（包含算法、數據結構）。*/2.3函數實現B.標準型a.打印指定年份的公歷表和農歷表voidDateTrans(char*chDate,int*nYear,int*nMonth,int*nDay)//1{*nYear=(chDate[0]-'0')*1000+(chDate[1]-'0')*100+(chDate[2]-'0')*10+chDate[3]-'0';*nMonth=(chDate[5]-'0')*10+chDate[6]-'0';*nDay=(chDate[8]-'0')*10+chDate[9]-'0';}intIsLeapYear(intnYear)//2{if(nYear%4==0)return1;elsereturn0;}intGetWeekOfFirstday(intnYear)//3{if(nYear>)return((nYear-)*365+(nYear-)/4+1)%7;elseif(nYear<)return6-((-nYear)*365+(-nYear)/4)%7;elsereturn6;}intGetWeek(intnYear,intnMonth,intnDay,intnWeekOfFirstday)//4{intnDaysYear[]={31,28,31,30,31,30,31,31,30,31,30,31};intnDaysLeapYear[]={31,29,31,30,31,30,31,31,30,31,30,31};inti,sum=0;if(nYear%4==0){for(i=0;i<(nMonth-1);i++){sum+=nDaysLeapYear[i];}return(sum+nDay+nWeekOfFirstday-1)%7;}else{for(i=0;i<(nMonth-1);i++){sum+=nDaysYear[i];}return(sum+nDay+nWeekOfFirstday-1)%7;}}voidPrintCalendar(intnWeek,intnDay,intnMonthDays,char*chDate)//5{inti,j;printf("thecalenderofthismonthasfollowing:\n");printf("*********************************\n");printf("SUNMONTUEWENTHUFRISTA\n");for(i=1,j=1;j<=nMonthDays;i++){if(i<=nWeek+1)printf("");else{printf("%4d",j);j++;}if(i%7==0)printf("\n");}printf("\n********************************\n");printf("OK!\n");}C.算法型a.七種排序算法：快速排序voidquickSort(inta[],intleft,intright){inti=left;intj=right;inttemp=a[left];if(left>=right)return;while(i!=j){while(i<j&&a[j]>=temp)j--;if(j>i)a[i]=a[j];//a[i]已經賦值給temp,因此直接將a[j]賦值給a[i],賦值完之后a[j],有空位while(i<j&&a[i]<=temp)i++;if(i<j)a[j]=a[i];}a[i]=temp;//把基準插入,此時i與j已經相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keysquickSort(a,left,i-1);/*遞歸左邊*/quickSort(a,i+1,right);/*遞歸右邊*/}插入排序選擇排序voidSelectionSort(int*a,intn)

{

inti,j,index,value;

for(i=0;i<n-1;i++){

index=i;

value=a[i];

for(j=i+1;j<n;j++)

if(value>a[j]){

index=j;

value=a[j];

}

a[index]=a[i];

a[i]=value;

Display(a,n);

}

}冒泡排序voidBubbleSort(intarray[],intn)

{

inti,j,temp;//外循環控制循環趟數

for(i=0;i<n-1;i++)

{//內循環選擇要進行比較的數

for(j=0;j<n-1-i;j++)

{

if(array[j]>array[j+1])

{

temp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

}

}

}

printf("\nThesortednumbersare:");

for(i=0;i<n;i++)

{

printf("}",array[i]);

}

printf("\n\n");

}

堆排序voidHeapAdjust(int*a,inti,intsize)//調整堆{intlchild=2*i;//i的左孩子節點序號intrchild=2*i+1;//i的右孩子節點序號intmax=i;//臨時變量if(i<=size/2)//如果i是葉節點就不用進行調整{if(lchild<=size&&a[lchild]>a[max]){max=lchild;}if(rchild<=size&&a[rchild]>a[max]){max=rchild;}if(max!=i){swap(a[i],a[max]);HeapAdjust(a,max,size);//避免調整之后以max為父節點的子樹不是堆}}}voidBuildHeap(int*a,intsize)//建立堆{inti;for(i=size/2;i>=1;i--)//非葉節點最大序號值為size/2{HeapAdjust(a,i,size);}}voidHeapSort(int*a,intsize)//堆排序{inti;BuildHeap(a,size);for(i=size;i>=1;i--){//cout<<a[1]<<"";swap(a[1],a[i]);//交換堆頂和最后一個元素，即每次將剩余元素中的最大者放到最后面//BuildHeap(a,i-1);//將余下元素重新建立為大頂堆HeapAdjust(a,1,i-1);//重新調整堆頂節點成為大頂堆}}歸并排序voidMerge(int*SR,int*TR,inti,intm,intn){

//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]

intj=m+1;

intk=i;

for(;i<=m&&j<=n;++k){//將SR中記錄按關鍵字從小到大地復制到TR中

if(SR[i]<=SR[j]){

TR[k]=SR[i++];

}else{

TR[k]=SR[j++];

}

}

while(i<=m)TR[k++]=SR[i++];

//將剩余的SR[i..m]復制到TR

while(j<=n)TR[k++]=SR[j++];

//將剩余的SR[j..n]復制到TR

}//Merge

voidMsort(int*SR,int*TR1,ints,intt){

//對SR[s..t]進行歸并排序，排序后的記錄存入TR1[s..t]

if(s==t){

TR1[s]=SR[s];

}else{

intTR2[10];

intm=(s+t)/2;

//將SR[s..t]平分為SR[s..m]和SR[m+1..t]

Msort(SR,TR2,s,m);

//遞歸地將SR[s..m]歸并為有序的TR2[s..m]

Msort(SR,TR2,m+1,t);

//遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);

//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]

}//else

}

//Msort

基數排序intgetdigit(intx,intd){inta[]={1,1,10};//因為待排數據最大數據也只是兩位數，因此在此只需要到十位就滿足return((x/a[d])%10);//確定桶號}voidPrintArr(intar[],intn){for(inti=0;i<n;++i)cout<<ar[i]<<"";cout<<endl;}voidmsdradix_sort(intarr[],intbegin,intend,intd){constintradix=10;intcount[radix],i,j;//置空for(i=0;i<radix;++i){count[i]=0;}//分配桶存儲空間int*bucket=(int*)malloc((end-begin+1)*sizeof(int));//統計各桶需要裝的元素的個數for(i=begin;i<=end;++i){count[getdigit(arr[i],d)]++;}//求出桶的邊界索引，count[i]值為第i個桶的右邊界索引+1for(i=1;i<radix;++i){count[i]=count[i]+count[i-1];}//這里要從右向左掃描，保證排序穩定性for(i=end;i>=begin;--i){j=getdigit(arr[i],d);//求出關鍵碼的第d位的數字，例如：576的第3位是5bucket[count[j]-1]=arr[i];//放入對應的桶中，count[j]-1是第j個桶的右邊界索引--count[j];//第j個桶放下一個元素的位置(右邊界索引+1)}//注意：此時count[i]為第i個桶左邊界//從各個桶中收集數據for(i=begin,j=0;i<=end;++i,++j){arr[i]=bucket[j];}//釋放存儲空間free(bucket);//對各桶中數據進行再排序for(i=0;i<radix;i++){intp1=begin+count[i];//第i個桶的左邊界intp2=begin+count[i+1]-1;//第i個桶的右邊界if(p1<p2&&d>1){msdradix_sort(arr,p1,p2,d-1);//對第i個桶遞歸調用，進行基數排序，數位降1}}}D.界面型a.OpenGL圖形庫程序黑白框voidinit(void){glClearColor(0.0,0.0,0.0,0.0);glShadeModel(GL_FLAT);}voiddisplay(void){glClear(GL_COLOR_BUFFER_BIT);glPushMatrix();glRotatef(spin,0.0,0.0,1.0);glColor3f(1.0,1.0,1.0);glRectf(-25.0,-25.0,25.0,25.0);glPopMatrix();glutSwapBuffers();}voidspinDisplay(void){spin=spin+2.0;if(spin>360.0)spin=spin-360.0;glutPostRedisplay();}voidreshape(intw,inth){glViewport(0,0,(GLsizei)w,(GLsizei)h);glMatrixMode(GL_PROJECTION);glLoadIdentity();//voidglOrtho(GLdoubleleft,GLdoubleright,GLdoublebottom,GLdoubletop,GLdoublenear,GLdoublefar);glOrtho(-50.0,50.0,-50.0,50.0,-1.0,1.0);glMatrixMode(GL_MODELVIEW);glLoadIdentity();}voidmouse(intbutton,intstate,intx,inty){switch(button){caseGLUT_LEFT_BUTTON:if(state==GLUT_DOWN)glutIdleFunc(spinDisplay);break;caseGLUT_MIDDLE_BUTTON:if(state==GLUT_DOWN)glutIdleFunc(0);break;default:break;}}voidkeyboard(unsignedcharkey,intx,inty){switch(key){case'a':glutIdleFunc(spinDisplay);break;case's':glutIdleFunc(0);break;}}螺旋曲線voidSetupRC(){glClearColor(0.0f,0.0f,0.0f,1.0f);glColor3f(1.0f,1.0f,1.0f);}voidRenderScene(void){GLfloatx,y,z,angle;glClear(GL_COLOR_BUFFER_BIT);glPushMatrix();glTranslatef(0,0,-80);//改動1:改變初始的位置glRotatef(XRot,1.0f,0.0f,0.0f);glRotatef(YRot,0.0f,1.0f,0.0f);glBegin(GL_POINTS);z=-50.0f;for(angle=0.0f;angle<=(2.0f*GL_PI)*3.0f;angle+=0.1f){x=50.0f*sin(angle);y=50.0f*cos(angle);glVertex3f(x,y,z);z+=0.5f;}glEnd();glPopMatrix();glFlush();}//改動2:重定義視口及觀察點voidresize(intwidth,intheight){glViewport(0,0,width,height);gluPerspective(120,1.0,15,-15);}voidspecial(intkey,intx,inty){switch(key){caseGLUT_KEY_LEFT:YRot-=5;glutPostRedisplay();break;caseGLUT_KEY_RIGHT:YRot+=5;glutPostRedisplay();break;caseGLUT_KEY_UP:XRot+=5;glutPostRedisplay();break;caseGLUT_KEY_DOWN:XRot-=5;glutPostRedisplay();break;}}彩色立方體voidChangeSize(intw,inth){GLfloatfAspect;//防止被0所除if(h==0)h=1;//把視口設置為窗口大小glViewport(0,0,w,h);fAspect=(GLfloat)w/(GLfloat)h;//實際窗口的縱橫比//重置透視坐標系統glMatrixMode(GL_PROJECTION);glLoadIdentity();//產生透視投影gluPerspective(60.0f,fAspect,1.0,400); //重置模型視圖矩陣glMatrixMode(GL_MODELVIEW);glLoadIdentity();}voidSetupRC(){glEnable(GL_DEPTH_TEST); //啟用深度測試glEnable(GL_COLOR_MATERIAL);//使用不同顏色來貼物體表面glClearColor(0.0f,0.0f,0.0f,1.0f);//黑色背景}voidSpecialKeys(intkey,intx,inty) { if(key==GLUT_KEY_UP) xRot-=5.0f; if(key==GLUT_KEY_DOWN) xRot+=5.0f; if(key==GLUT_KEY_LEFT) yRot-=5.0f; if(key==GLUT_KEY_RIGHT) yRot+=5.0f;xRot=(GLfloat)((constint)xRot%360);yRot=(GLfloat)((constint)yRot%360); glutPostRedisplay(); }//繪制一個立方體voidRenderScene(void){floatfZ,bZ;//清空顏色緩沖區和深度緩沖區glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);fZ=50.0f;bZ=-50.0f;glPushMatrix(); glTranslatef(0.0f,0.0f,-400.0f);//讓視圖向z軸負方向移動300glRotatef(xRot,1.0f,0.0f,0.0f);glRotatef(yRot,0.0f,1.0f,0.0f);glColor3f(1.0f,0.0f,0.0f);//繪制立方體glBegin(GL_QUADS);//正面，紅色glVertex3f(-50.0f,50.0f,fZ);glVertex3f(-50.0f,-50.0f,fZ);glVertex3f(50.0f,-50.0f,fZ);glVertex3f(50.0f,50.0f,fZ);//左面，藍色glColor3f(0.0f,0.0f,1.0f);glVertex3f(-50.0f,50.0f,bZ);glVertex3f(-50.0f,-50.0f,bZ);glVertex3f(-50.0f,-50.0f,fZ);glVertex3f(-50.0f,50.0f,fZ);//右面，綠色glColor3f(0.0f,1.0f,0.0f);glVertex3f(50.0f,50.0f,fZ);glVertex3f(50.0f,-50.0f,fZ);glVertex3f(50.0f,-50.0f,bZ);glVertex3f(50.0f,50.0f,bZ);//反面，土黃色glColor3f(0.5f,0.5f,0.0f);glVertex3f(50.0f,50.0f,bZ);glVertex3f(50.0f,-50.0f,bZ);glVertex3f(-50.0f,-50.0f,bZ);glVertex3f(-50.0f,50.0f,bZ);//頂面，黃色glColor3f(1.0f,1.0f,0.0f);glVertex3f(-50.0f,50.0f,bZ);glVertex3f(-50.0f,50.0f,fZ);glVertex3f(50.0f,50.0f,fZ);glVertex3f(50.0f,50.0f,bZ);//底面，暗藍色glColor3f(0.0f,0.5f,0.5f);glVertex3f(-50.0f,-50.0f,fZ);glVertex3f(-50.0f,-50.0f,bZ);glVertex3f(50.0f,-50.0f,bZ);glVertex3f(50.0f,-50.0f,fZ);glEnd();glPopMatrix();//交換緩沖區glutSwapBuffers();}2.4開發日志這份大作業共歷時3天，由我小組成員利用課余時間完成。我們不斷地翻閱資料，修改思路，總結方法，最終完成了整份作業。大家一起合作，學到了很多東西。3程序調試及運行3.1程序運行結果A.數學型a.歌星大獎賽b.求最大數B.標準型a.打印指定年份的公歷表和農歷表C.算法型a.七種排序算法：D.界面型a.OpenGL圖形庫程序黑白框螺旋曲線彩色立方體3.2程序使用說明以上程序只需直接運行、讀入數據即可出解。程序運行時皆有說明，按照提示運行即可。3.3程序開發總結個人認為，這份作業給了我很大啟發。做事情一定要注意效率，講究事半功倍，在起初的時候，我走了一些彎路，其后做了些改進，效率立馬提高了，節省了很多精力。4附件（源程序）A.數學型a.歌星大獎賽#include<stdio.h>intmain(){intmax=0,ma,mi,min=100,i,a[10],s=0;for(i=0;i<10;i++){scanf("%d",&a[i]);if(a[i]>max){max=a[i];ma=i;}if(a[i]<min){min=a[i];mi=i;}}for(i=0;i<10;i++)if(i!=ma&&i!=mi)s=s+a[i];if(ma==mi)printf("%.2lf",s/9.0);if(ma!=mi)printf("%.2lf",s/8.0);return0;}b.求最大數#include<stdio.h>intmain(){inti;for(i=999;i>=100;i--)if(555555%i==0){printf("%d",i);break;}return0;}B.標準型a.打印指定年份的公歷表和農歷表#include<stdio.h>voidDateTrans(char*chDate,int*nYear,int*nMonth,int*nDay);//1intIsLeapYear(intnYear);//2intGetWeekOfFirstday(intnYear);//3intGetWeek(intnYear,intnMonth,intnDay,intnWeekOfFirstday);//4voidPrintCalendar(intnWeek,intnDay,intnMonthDays,char*chDate);//5voidDateTrans(char*chDate,int*nYear,int*nMonth,int*nDay)//1{*nYear=(chDate[0]-'0')*1000+(chDate[1]-'0')*100+(chDate[2]-'0')*10+chDate[3]-'0';*nMonth=(chDate[5]-'0')*10+chDate[6]-'0';*nDay=(chDate[8]-'0')*10+chDate[9]-'0';}intIsLeapYear(intnYear)//2{if(nYear%4==0)return1;elsereturn0;}intGetWeekOfFirstday(intnYear)//3{if(nYear>)return((nYear-)*365+(nYear-)/4+1)%7;elseif(nYear<)return6-((-nYear)*365+(-nYear)/4)%7;elsereturn6;}intGetWeek(intnYear,intnMonth,intnDay,intnWeekOfFirstday)//4{intnDaysYear[]={31,28,31,30,31,30,31,31,30,31,30,31};intnDaysLeapYear[]={31,29,31,30,31,30,31,31,30,31,30,31};inti,sum=0;if(nYear%4==0){for(i=0;i<(nMonth-1);i++){sum+=nDaysLeapYear[i];}return(sum+nDay+nWeekOfFirstday-1)%7;}else{for(i=0;i<(nMonth-1);i++){sum+=nDaysYear[i];}return(sum+nDay+nWeekOfFirstday-1)%7;}}voidPrintCalendar(intnWeek,intnDay,intnMonthDays,char*chDate)//5{inti,j;printf("thecalenderofthismonthasfollowing:\n");printf("*********************************\n");printf("SUNMONTUEWENTHUFRISTA\n");for(i=1,j=1;j<=nMonthDays;i++){if(i<=nWeek+1)printf("");else{printf("%4d",j);j++;}if(i%7==0)printf("\n");}printf("\n********************************\n");printf("OK!\n");}main(){charchDate[11],i=0,j,isleapyear;intnYear,nMonth,nDay;intnWeekOfFirstday;intnMonthDays;intnWeek;char*Week;intnDaysYear[]={31,28,31,30,31,30,31,31,30,31,30,31};intnDaysLeapYear[]={31,29,31,30,31,30,31,31,30,31,30,31};printf("請輸入你要查找的日期,如（\\01\\01或.01.01:\n或者是你想要日歷的月份:如（\\01或.01）：\n");do{scanf("%c",&chDate[i]);i++;}while(chDate[i-1]!='\n');if(i==11)chDate[i-1]='\0';elsefor(j=8;j<11;j++)chDate[j]='0';DateTrans(chDate,&nYear,&nMonth,&nDay);//1while(nYear<=0||nMonth<1||nMonth>12){printf("查詢年月chDate非法\n");return0;}nWeekOfFirstday=GetWeekOfFirstday(nYear);//3nWeek=GetWeek(nYear,nMonth,nDay,nWeekOfFirstday);//4isleapyear=IsLeapYear(nYear);//2if(isleapyear==1)nMonthDays=nDaysLeapYear[nMonth-1];elseif(isleapyear==0)nMonthDays=nDaysYear[nMonth-1];if(i==11){while(nDay<1||nDay>nMonthDays){printf("查詢日期chDate非法\n");return0;}switch(nWeek){case0:Week="SUNDAY";break;case1:Week="MONDAY";break;case2:Week="TUESDAY";break;case3:Week="WEDNESDAY";break;case4:Week="THUESDAY";break;case5:Week="FRIDAY";break;case6:Week="SATERDAY";break;}printf("Thisday(%s)is%s\n",chDate,Week);printf("OK!\n");}elsePrintCalendar(nWeek,nDay,nMonthDays,chDate);//5}C.算法型a.七種排序算法：快速排序：#include<stdio.h>voidquickSort(inta[],intleft,intright){inti=left;intj=right;inttemp=a[left];if(left>=right)return;while(i!=j){while(i<j&&a[j]>=temp)j--;if(j>i)a[i]=a[j];//a[i]已經賦值給temp,因此直接將a[j]賦值給a[i],賦值完之后a[j],有空位while(i<j&&a[i]<=temp)i++;if(i<j)a[j]=a[i];}a[i]=temp;//把基準插入,此時i與j已經相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keysquickSort(a,left,i-1);/*遞歸左邊*/quickSort(a,i+1,right);/*遞歸右邊*/}intmain(){inta[9]={8,2,6,12,1,9,5,5,10};inti;quickSort(a,0,8);/*排好序的結果*/for(i=0;i<8;i++)printf("%4d",a[i]);getchar();return0;}插入排序：#include<stdio.h>

intmain()

{

intn[10];

inti,j,k;

inttemp;

for(i=0;i<=9;i++)

{

printf("請輸入第%d個數:",i+1);

scanf("%d",&n[i]);

}

printf("數組排序前效果如下\n");

for(i=0;i<=9;i++)

{

printf("%d",n[i]);

}

printf("\n");

for(i=1;i<=9;i++)

{

for(j=i-1;j>=0;j--)

{

if(n[j]<n[i])

break;

}

if(j!=i-1)

{

temp=n[i];

for(k=i;k>=j+1;k--)

n[k]=n[k-1];

n[j+1]=temp;

}

}

printf("數組排序后效果如下\n");

for(i=0;i<=9;i++)

{

printf("%d",n[i]);

}

printf("\n");

return0;

}選擇排序：#include<stdio.h>

#defineN10

voidDisplay(int*a,intn)

{

inti;

for(i=0;i<n;i++){

printf("%d",a[i]);

}

printf("\n");

}

voidSelectionSort(int*a,intn)

{

inti,j,index,value;

for(i=0;i<n-1;i++){

index=i;

value=a[i];

for(j=i+1;j<n;j++)

if(value>a[j]){

index=j;

value=a[j];

}

a[index]=a[i];

a[i]=value;

Display(a,n);

}

}

voidmain()

{

inta[N],i;

for(i=0;i<N;i++)

a[i]=N-i;

Display(a,N);

SelectionSort(a,N);

}冒泡排序：#include<stdio.h>

#defineN15

voidBubbleSort(intarray[],intn)

{

inti,j,temp;//外循環控制循環趟數

for(i=0;i<n-1;i++)

{//內循環選擇要進行比較的數

for(j=0;j<n-1-i;j++)

{

if(array[j]>array[j+1])

{

temp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

}

}

}

printf("\nThesortednumbersare:");

for(i=0;i<n;i++)

{

printf("}",array[i]);

}

printf("\n\n");

}

voidmain()

{

inti,n,a[N];

do{

printf("Inputn[1-12]:");

scanf("%d",&n);

}while(!(n>=1&&n<=12));

printf("Pleaseinput%dnumbers:",n);

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

printf("\nTheoriginalnumbersare:");

for(i=0;i<n;i++)

{

printf("}",a[i]);

}

BubbleSort(a,n);

return;

}堆排序：#include<iostream>#include<algorithm>usingnamespacestd;voidHeapAdjust(int*a,inti,intsize)//調整堆{intlchild=2*i;//i的左孩子節點序號intrchild=2*i+1;//i的右孩子節點序號intmax=i;