西北工業(yè)大學(xué)C語(yǔ)言課程設(shè)計(jì)大作業(yè)

1、學(xué) 院電子信息學(xué)院班 級(jí)08031302班學(xué) 號(hào)2013301986姓 名張昌武摘要 本次大作業(yè)包括一個(gè)標(biāo)準(zhǔn)型大作業(yè)，一個(gè)界面型大作業(yè)，兩個(gè)數(shù)學(xué)型大作業(yè)和一個(gè)算法型大作業(yè)。本次聯(lián)系我選擇的題目是：A.數(shù)學(xué)型a.歌星大獎(jiǎng)賽 b.求最大數(shù)B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表C.算法型a.七種排序算法D.界面型a.OpenGL圖形庫(kù)程序目錄1 摘要31.1 設(shè)計(jì)題目31.2 設(shè)計(jì)內(nèi)容31.3 開(kāi)發(fā)工具41.4 應(yīng)用平臺(tái)42 詳細(xì)設(shè)計(jì)42.1 程序結(jié)構(gòu)42.2 主要功能182.3 函數(shù)實(shí)現(xiàn)182.4 開(kāi)發(fā)日志253 程序調(diào)試及運(yùn)行313.1 程序運(yùn)行結(jié)果313.2 程序使用說(shuō)明363.3 程序

2、開(kāi)發(fā)總結(jié)364 附件（源程序）361 摘要1.1 設(shè)計(jì)題目A.數(shù)學(xué)型a.歌星大獎(jiǎng)賽 b.求最大數(shù)B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表C.算法型 a.七種排序算法D.界面型 a.OpenGL圖形庫(kù)程序1.2 設(shè)計(jì)內(nèi)容A. 數(shù)學(xué)型a.十個(gè)評(píng)委打分，分?jǐn)?shù)在1100之間，選手最后得分為：去掉一個(gè)最高分和一個(gè)最低分后其余8個(gè)分?jǐn)?shù)的平均值。b.求555555的約數(shù)中的最大三位數(shù)B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表C.算法型 a.七種排序算法： 快速排序 插入排序 選擇排序 冒泡排序 堆排序 歸并排序 基數(shù)排序D.界面型 a. OpenGL圖形庫(kù)程序: 繪制黑白框 繪制螺旋曲線 繪制彩色立方

3、體1.3 開(kāi)發(fā)工具codeblock1.4 應(yīng)用平臺(tái)Windows 2000/XP/Vista 32位/win 7、82 詳細(xì)設(shè)計(jì)2.1 程序結(jié)構(gòu)A. 數(shù)學(xué)型a.十個(gè)評(píng)委打分，分?jǐn)?shù)在1100之間，選手最后得分為：去掉一個(gè)最高分和一個(gè)最低分后其余8個(gè)分?jǐn)?shù)的平均值。 該題涉及到數(shù)組存儲(chǔ)b.求555555的約數(shù)中的最大三位數(shù)：該題只用到循環(huán)和判斷語(yǔ)句，從999向下搜索即可B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表年歷的設(shè)計(jì)與計(jì)算，應(yīng)首先判斷“某年某月某日是星期幾”，即能被4且不能被100整除或能被400整除的數(shù)。這樣，接下來(lái)的事情就簡(jiǎn)單了，輸入年份，打印出相應(yīng)的日歷。C.算法型 a.七種排序算法：

4、快速排序(QuickSort)劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos,編程時(shí)候的關(guān)鍵點(diǎn)快速排序：既然能把冒泡KO掉，馬上就激起我們的興趣，tnd快排咋這么快，一定要好好研究一下。首先上圖：    從圖中我們可以看到：left指針，right指針，base參照數(shù)。其實(shí)思想是蠻簡(jiǎn)單的，就是通過(guò)第一遍的遍歷（讓left和right指針重合）來(lái)找到數(shù)組的切割點(diǎn)。第一步：首先我們從數(shù)組的left位置取出該數(shù)（20）作為基準(zhǔn)（base）參照物。第二步：從數(shù)組的right位置向前找，一直找到比（base）小的數(shù)，       

5、60;   如果找到，將此數(shù)賦給left位置（也就是將10賦給20），            此時(shí)數(shù)組為：10，40，50，10，60，            left和right指針?lè)謩e為前后的10。第三步：從數(shù)組的left位置向后找，一直找到比（base）大的數(shù)，             如果找到，將此數(shù)賦給right的位置（也就是40賦給10），      &#

6、160;      此時(shí)數(shù)組為：10，40，50，40，60，             left和right指針?lè)謩e為前后的40。第四步：重復(fù)“第二,第三“步驟，直到left和right指針重合，             最后將（base）插入到40的位置，             此時(shí)數(shù)組值為： 10，20，50，40，60，至此完成一次排序。第五步：此時(shí)

7、20已經(jīng)潛入到數(shù)組的內(nèi)部，20的左側(cè)一組數(shù)都比20小，20的右側(cè)作為一組數(shù)都比20大， 以20為切入點(diǎn)對(duì)左右兩邊數(shù)按照"第一，第二，第三，第四"步驟進(jìn)行，最終快排大功告成。 快速排序具有最好的平均性能（average behavior），但最壞性能（worst case behavior）和插入排序相同，也是O(n2)。比如一個(gè)序列5,4,3,2,1，要排為1,2,3,4,5。按照快速排序方法，每次只會(huì)有一個(gè)數(shù)據(jù)進(jìn)入正確順序，不能把數(shù)據(jù)分成大小相當(dāng)?shù)膬煞荩苊黠@，排序的過(guò)程就成了一個(gè)歪脖子樹(shù)，樹(shù)的深度為n，那時(shí)間復(fù)雜度就成了O(n2)。盡管如此，需要排序的情況幾乎

8、都是亂序的，自然性能就保證了。據(jù)書(shū)上的測(cè)試圖來(lái)看，在數(shù)據(jù)量小于20的時(shí)候，插入排序具有最好的性能。當(dāng)大于20時(shí)，快速排序具有最好的性能，歸并(merge sort)和堆排序(heap sort)也望塵莫及，盡管復(fù)雜度都為nlog2(n)。1、算法思想    快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。（1） 分治法的基本思想    分治法的基本思想是：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些

9、子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。（2）快速排序的基本思想    設(shè)當(dāng)前待排序的無(wú)序區(qū)為Rlow.high，利用分治法可將快速排序的基本思想描述為：分解：     在Rlow.high中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間Rlow.pivotpos-1)和Rpivotpos+1.high，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄

10、pivot則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序。  注意：    劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos。劃分的結(jié)果可以簡(jiǎn)單地表示為(注意pivot=Rpivotpos)：    Rlow.pivotpos-1.keysRpivotpos.keyRpivotpos+1.high.keys                &

11、#160; 其中l(wèi)owpivotposhigh。求解：     通過(guò)遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間Rlow.pivotpos-1和Rpivotpos+1.high快速排序。組合：     因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。2、快速排序算法QuickSort  void QuickSort(SeqList R，int low，int high) &#

12、160; /對(duì)Rlow.high快速排序     int pivotpos； /劃分后的基準(zhǔn)記錄的位置     if(low<high)/僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序        pivotpos=Partition(R，low，high)； /對(duì)Rlow.high做劃分        QuickSort(R，low，pivotpos-1)； /對(duì)左區(qū)間遞歸排序

13、0;       QuickSort(R，pivotpos+1，high)； /對(duì)右區(qū)間遞歸排序          /QuickSort  注意：    為排序整個(gè)文件，只須調(diào)用QuickSort(R，1，n)即可完成對(duì)Rl.n的排序。插入排序 算法描述    插入排序：插入即表示將一個(gè)新的數(shù)據(jù)插入到一個(gè)有序數(shù)組中，并繼續(xù)保持有序。例如有一個(gè)長(zhǎng)度為N的無(wú)序數(shù)組，進(jìn)行N-1次的插入即能完成排序；第一

14、次，數(shù)組第1個(gè)數(shù)認(rèn)為是有序的數(shù)組，將數(shù)組第二個(gè)元素插入僅有1個(gè)有序的數(shù)組中；第二次，數(shù)組前兩個(gè)元素組成有序的數(shù)組，將數(shù)組第三個(gè)元素插入由兩個(gè)元素構(gòu)成的有序數(shù)組中.第N-1次，數(shù)組前N-1個(gè)元素組成有序的數(shù)組，將數(shù)組的第N個(gè)元素插入由N-1個(gè)元素構(gòu)成的有序數(shù)組中，則完成了整個(gè)插入排序。以下面5個(gè)無(wú)序的數(shù)據(jù)為例：65 27 59 64 58 （文中僅細(xì)化了第四次插入過(guò)程）第1次插入: 27 65 59 64 58第2次插入: 27 59 65 64 58第3次插入: 27 59 64 65 58第4次插入: 27 58 59 64 65二. 算法分析平均時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)

15、 (用于記錄需要插入的數(shù)據(jù))穩(wěn)定性：穩(wěn)定選擇排序 算法描述    選擇排序：比如在一個(gè)長(zhǎng)度為N的無(wú)序數(shù)組中，在第一趟遍歷N個(gè)數(shù)據(jù)，找出其中最小的數(shù)值與第一個(gè)元素交換，第二趟遍歷剩下的N-1個(gè)數(shù)據(jù)，找出其中最小的數(shù)值與第二個(gè)元素交換.第N-1趟遍歷剩下的2個(gè)數(shù)據(jù)，找出其中最小的數(shù)值與第N-1個(gè)元素交換，至此選擇排序完成。以下面5個(gè)無(wú)序的數(shù)據(jù)為例：56 12 80 91 20（文中僅細(xì)化了第一趟的選擇過(guò)程）第1趟：12 56 80 91 20第2趟：12 20 80 91 56第3趟：12 20 56 91 80第4趟：12 20 56 80 91算法分析平均時(shí)間復(fù)雜

16、度：O(n2)空間復(fù)雜度：O(1)  (用于交換和記錄索引)穩(wěn)定性：不穩(wěn)定 （比如序列【5， 5， 3】第一趟就將第一個(gè)5與3交換，導(dǎo)致第一個(gè)5挪動(dòng)到第二個(gè)5后面）冒泡排序冒泡排序法的基本思想：（以升序?yàn)槔┖衝個(gè)元素的數(shù)組原則上要進(jìn)行n-1次排序。對(duì)于每一躺的排序，從第一個(gè)數(shù)開(kāi)始，依次比較前一個(gè)數(shù)與后一個(gè)數(shù)的大小。如果前一個(gè)數(shù)比后一個(gè)數(shù)大，則進(jìn)行交換。這樣一輪過(guò)后，最大的數(shù)將會(huì)出現(xiàn)稱為最末位的數(shù)組元素。第二輪則去掉最后一個(gè)數(shù)，對(duì)前n-1個(gè)數(shù)再按照上面的步驟找出最大數(shù)，該數(shù)將稱為倒數(shù)第二的數(shù)組元素.n-1輪過(guò)后，就完成了排序。若要以降序順序排列，則只需將 if(array

17、j>arrayj+1)語(yǔ)句中的大于號(hào)改為小于號(hào)即可。堆排序  堆排序是利用堆的性質(zhì)進(jìn)行的一種選擇排序。下面先討論一下堆。1.堆  堆實(shí)際上是一棵完全二叉樹(shù)，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)：  Keyi<=key2i+1&&Keyi<=key2i+2或者Keyi>=Key2i+1&&key>=key2i+2  即任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字。  堆分為大頂堆和小頂堆，滿足Keyi>=Key2i+1&&key>=key2i+

18、2稱為大頂堆，滿足 Keyi<=key2i+1&&Keyi<=key2i+2稱為小頂堆。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。2.堆排序的思想   利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無(wú)序中選擇最大記錄(最小記錄)變得簡(jiǎn)單。    其基本思想為(大頂堆)：    1)將初始待排序關(guān)鍵字序列(R1,R2.Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；    2)將

19、堆頂元素R1與最后一個(gè)元素Rn交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,.Rn-1)和新的有序區(qū)(Rn),且滿足R1,2.n-1<=Rn;     3)由于交換后新的堆頂R1可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,.Rn-1)調(diào)整為新堆，然后再次將R1與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2.Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。    操作過(guò)程如下：     1)初始化堆：將R1.n構(gòu)造為堆

20、；     2)將當(dāng)前無(wú)序區(qū)的堆頂元素R1同該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為新的堆。    因此對(duì)于堆排序，最重要的兩個(gè)操作就是構(gòu)造初始堆和調(diào)整堆，其實(shí)構(gòu)造初始堆事實(shí)上也是調(diào)整堆的過(guò)程，只不過(guò)構(gòu)造初始堆是對(duì)所有的非葉節(jié)點(diǎn)都進(jìn)行調(diào)整。    下面舉例說(shuō)明：     給定一個(gè)整形數(shù)組a=16,7,3,20,17,8，對(duì)其進(jìn)行堆排序。    首先根據(jù)該數(shù)組元素構(gòu)建一個(gè)完全二叉樹(shù)，得到  

21、然后需要構(gòu)造初始堆，則從最后一個(gè)非葉節(jié)點(diǎn)開(kāi)始調(diào)整，調(diào)整過(guò)程如下：20和16交換后導(dǎo)致16不滿足堆的性質(zhì)，因此需重新調(diào)整這樣就得到了初始堆。即每次調(diào)整都是從父節(jié)點(diǎn)、左孩子節(jié)點(diǎn)、右孩子節(jié)點(diǎn)三者中選擇最大者跟父節(jié)點(diǎn)進(jìn)行交換(交換之后可能造成被交換的孩子節(jié)點(diǎn)不滿足堆的性質(zhì)，因此每次交換之后要重新對(duì)被交換的孩子節(jié)點(diǎn)進(jìn)行調(diào)整)。有了初始堆之后就可以進(jìn)行排序了。此時(shí)3位于堆頂不滿堆的性質(zhì)，則需調(diào)整繼續(xù)調(diào)整 這樣整個(gè)區(qū)間便已經(jīng)有序了。    從上述過(guò)程可知，堆排序其實(shí)也是一種選擇排序，是一種樹(shù)形選擇排序。只不過(guò)直接選擇排序中，為了從R1.n中選擇最大記錄，需比較n-1次

22、，然后從R1.n-2中選擇最大記錄需比較n-2次。事實(shí)上這n-2次比較中有很多已經(jīng)在前面的n-1次比較中已經(jīng)做過(guò)，而樹(shù)形選擇排序恰好利用樹(shù)形的特點(diǎn)保存了部分前面的比較結(jié)果，因此可以減少比較次數(shù)。對(duì)于n個(gè)關(guān)鍵字序列，最壞情況下每個(gè)節(jié)點(diǎn)需比較log2(n)次，因此其最壞情況下時(shí)間復(fù)雜度為nlogn。堆排序?yàn)椴环€(wěn)定排序，不適合記錄較少的排序。歸并排序 歸并排序的基本操作是 將兩個(gè)或兩個(gè)以上的記錄有序序列歸并為一個(gè)有序序列。最簡(jiǎn)單的情況是，只含一個(gè)記錄的序列顯然是個(gè)有序序列，經(jīng)過(guò)"逐趟歸并"使整個(gè)序列中的有序子序列的長(zhǎng)度逐趟增大， 直至整個(gè)記錄序列為有序序列止。

23、 它的基本操作是將兩個(gè)相鄰的有序子序列"歸并"為一個(gè)有序序列， 如右側(cè)所示。這個(gè)操作對(duì)順序表而言是極其容易實(shí)現(xiàn)的，只要依關(guān)鍵字從小到大進(jìn)行"復(fù)制"即可基數(shù)排序簡(jiǎn)略概述：基數(shù)排序是通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序。而這個(gè)思想該如何理解呢？請(qǐng)看以下例子。（1）假設(shè)有欲排數(shù)據(jù)序列如下所示：73  22  93  43  55  14  28  65  39  81首先根據(jù)個(gè)位數(shù)的數(shù)值，在遍歷數(shù)據(jù)時(shí)將它們各自分配到編號(hào)0至9的桶（個(gè)位數(shù)值與桶號(hào)一一對(duì)

24、應(yīng)）中。分配結(jié)果（邏輯想象）如下圖所示：分配結(jié)束后。接下來(lái)將所有桶中所盛數(shù)據(jù)按照桶號(hào)由小到大（桶中由頂至底）依次重新收集串起來(lái)，得到如下仍然無(wú)序的數(shù)據(jù)序列：81  22  73  93  43  14  55  65  28  39接著，再進(jìn)行一次分配，這次根據(jù)十位數(shù)值來(lái)分配（原理同上），分配結(jié)果（邏輯想象）如下圖所示：分配結(jié)束后。接下來(lái)再將所有桶中所盛的數(shù)據(jù)（原理同上）依次重新收集串接起來(lái)，得到如下的數(shù)據(jù)序列：14  22  28  39  43  55

25、  65  73  81  93觀察可以看到，此時(shí)原無(wú)序數(shù)據(jù)序列已經(jīng)排序完畢。如果排序的數(shù)據(jù)序列有三位數(shù)以上的數(shù)據(jù)，則重復(fù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。那么，到這里為止，你覺(jué)得你是不是一個(gè)細(xì)心的人？不要不假思索的回答我。不論回答什么樣的問(wèn)題，都要做到心比頭快，頭比嘴快。仔細(xì)看看你對(duì)整個(gè)排序的過(guò)程中還有哪些疑惑？真看不到？覺(jué)得我做得很好？抑或前面沒(méi)看懂？如果你看到這里真心沒(méi)有意識(shí)到或發(fā)現(xiàn)這個(gè)問(wèn)題，那我告訴你：悄悄去找個(gè)墻角蹲下用小拇指畫(huà)圈圈（好好反省反省）。追問(wèn)：觀察原無(wú)序數(shù)據(jù)序列中73   93   43 三個(gè)數(shù)

26、據(jù)的順序，在經(jīng)過(guò)第一次（按照個(gè)位數(shù)值，它們?nèi)邞?yīng)該是在同一個(gè)桶中）分配之后，在桶中順序由底至頂應(yīng)該為73  93  43（即就是裝的遲的在最上面，對(duì)應(yīng)我們上面的邏輯想象應(yīng)該是43  93  73），對(duì)吧？這個(gè)應(yīng)該可以想明白吧？理論上應(yīng)該是這樣的。但是，但是，但是分配后很明顯在3號(hào)桶中三者的順序剛好相反。這點(diǎn)難道你沒(méi)有發(fā)現(xiàn)嗎？或者是發(fā)現(xiàn)了覺(jué)得不屑談及（算我貽笑大方）？其實(shí)這個(gè)也正是基數(shù)排序穩(wěn)定性的原因（分配時(shí)由末位向首位進(jìn)行），請(qǐng)看下文的詳細(xì)分析。再思考一個(gè)問(wèn)題：既然我們可以從最低位到最高位進(jìn)行如此的分配收集，那么是否可以由最高位到最低位依次操作呢？ 答案

27、是完全可以的。基于兩種不同的排序順序，我們將基數(shù)排序分為L(zhǎng)SD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由數(shù)值的最右邊（低位）開(kāi)始，而MSD則相反，由數(shù)值的最左邊（高位）開(kāi)始。注意一點(diǎn)：LSD的基數(shù)排序適用于位數(shù)少的數(shù)列，如果位數(shù)多的話，使用MSD的效率會(huì)比較好。MSD的方式與LSD相反，是由高位數(shù)為基底開(kāi)始進(jìn)行分配，但在分配之后并不馬上合并回一個(gè)數(shù)組中，而是在每個(gè)“桶子”中建立“子桶”，將每個(gè)桶子中的數(shù)值按照下一數(shù)位的值分配到“子桶”中。在進(jìn)行完最低位數(shù)的分配后再合并回單一的數(shù)組中。（2）我們把撲克牌的

28、排序看成由花色和面值兩個(gè)數(shù)據(jù)項(xiàng)組成的主關(guān)鍵字排序。要求如下：花色順序：梅花<方塊<紅心<黑桃面值順序：2<3<4<.<10<J<Q<K<A那么，若要將一副撲克牌排成下列次序：梅花2，.，梅花A，方塊2，.，方塊A，紅心2，.，紅心A，黑桃2，.，黑桃A。有兩種排序方法：<1>先按花色分成四堆，把各堆收集起來(lái)；然后對(duì)每堆按面值由小到大排列，再按花色從小到大按堆收疊起來(lái)。-稱為"最高位優(yōu)先"(MSD)法。<2>先按面值由小到大排列成13堆，然后從小到大收集起來(lái)；再按花色不同分成四堆，最后順

29、序收集起來(lái)。-稱為"最低位優(yōu)先"(LSD)法。【2】代碼實(shí)現(xiàn)（1）MSD法實(shí)現(xiàn)最高位優(yōu)先法通常是一個(gè)遞歸的過(guò)程：<1>先根據(jù)最高位關(guān)鍵碼K1排序，得到若干對(duì)象組，對(duì)象組中每個(gè)對(duì)象都有相同關(guān)鍵碼K1。<2>再分別對(duì)每組中對(duì)象根據(jù)關(guān)鍵碼K2進(jìn)行排序，按K2值的不同，再分成若干個(gè)更小的子組，每個(gè)子組中的對(duì)象具有相同的K1和K2值。<3>依此重復(fù)，直到對(duì)關(guān)鍵碼Kd完成排序?yàn)橹埂?lt;4> 最后，把所有子組中的對(duì)象依次連接起來(lái)，就得到一個(gè)有序的對(duì)象序列。（2）LSD法實(shí)現(xiàn)最低位優(yōu)先法首先依據(jù)最低位關(guān)鍵碼Kd對(duì)所有對(duì)象進(jìn)行一趟排序，

30、再依據(jù)次低位關(guān)鍵碼Kd-1對(duì)上一趟排序的結(jié)果再排序，依次重復(fù)，直到依據(jù)關(guān)鍵碼K1最后一趟排序完成，就可以得到一個(gè)有序的序列。使用這種排序方法對(duì)每一個(gè)關(guān)鍵碼進(jìn)行排序時(shí)，不需要再分組，而是整個(gè)對(duì)象組?！?】基數(shù)排序穩(wěn)定性分析基數(shù)排序是穩(wěn)定性排序算法，那么，到底如何理解它所謂的穩(wěn)定特性呢？比如：我們有如下欲排數(shù)據(jù)序列：下面選擇LSD邏輯演示第一次按個(gè)位數(shù)值分配，結(jié)果如下圖所示：然后收集數(shù)據(jù)結(jié)果如下：第二次按十位數(shù)值分配，結(jié)果如下圖所示：然后收集數(shù)據(jù)結(jié)果如下：注意：分配時(shí)是從欲排數(shù)據(jù)序列的末位開(kāi)始進(jìn)行，逐次分配至首位。D.界面型a. OpenGL圖形庫(kù)程序openGL（Open Graphics Li

31、brary）從本質(zhì)上說(shuō)，它是一個(gè)3D圖形和模型庫(kù)，具有高度的移植性。我們可以將openGL看做是一個(gè)C運(yùn)行時(shí)的函數(shù)庫(kù)，這個(gè)函數(shù)庫(kù)可以幫助我們繪制二維或三維的圖像。靜態(tài)鏈接庫(kù)和動(dòng)態(tài)鏈接庫(kù)靜態(tài)庫(kù)：lib文件。編譯時(shí)代碼編譯進(jìn)exe中，會(huì)使得程序體積非常龐大。不利于模塊的共享。優(yōu)點(diǎn)：不會(huì)有dll hell的問(wèn)題。好像“企業(yè)間的吞并”。動(dòng)態(tài)庫(kù)：dll文件。代碼在dll中，其他程序調(diào)用dll中的代碼，多個(gè)程序可以共享。缺點(diǎn)：dll hell(dll地獄)，版本問(wèn)題。另外，主要用到的就是“glut.h”這個(gè)頭文件，它包括了我們所需的大多數(shù)函數(shù)，直接調(diào)用很方便！我們利用OpenGl函數(shù)庫(kù)編寫(xiě)了三個(gè)簡(jiǎn)單的程序

32、，分別是：繪制黑白框、繪制螺旋曲線、繪制彩色立方體。2.2 主要功能A. 數(shù)學(xué)型a.十個(gè)評(píng)委打分，分?jǐn)?shù)在1100之間，選手最后得分為：去掉一個(gè)最高分和一個(gè)最低分后其余8個(gè)分?jǐn)?shù)的平均值。該題主要實(shí)現(xiàn)賽場(chǎng)的積分統(tǒng)計(jì)b.求555555的約數(shù)中的最大三位數(shù) 該題主要實(shí)現(xiàn)一個(gè)數(shù)的約數(shù)的求解B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表 該題主要實(shí)現(xiàn)制定年月日期的輸出C.算法型 a.七種排序算法： 快速排序 插入排序 選擇排序 冒泡排序 堆排序 歸并排序 基數(shù)排序 該題主要實(shí)現(xiàn)一組數(shù)據(jù)的排序D.界面型 a. OpenGL圖形庫(kù)程序 該題主要實(shí)現(xiàn)OpenGl圖形庫(kù)在Windows系統(tǒng)下的圖形設(shè)計(jì)/*請(qǐng)?jiān)谶@里說(shuō)

33、明你的大作業(yè)程序功能，并詳細(xì)描述它們實(shí)現(xiàn)的原理和方法（包含算法、數(shù)據(jù)結(jié)構(gòu)）。*/2.3 函數(shù)實(shí)現(xiàn)B.標(biāo)準(zhǔn)型 a.打印指定年份的公歷表和農(nóng)歷表void DateTrans(char *chDate,int *nYear,int *nMonth,int *nDay) / 1 *nYear=(chDate0-'0')*1000+(chDate1-'0')*100+(chDate2-'0')*10+chDate3-'0' *nMonth=(chDate5-'0')*10+chDate6-'0' *nDay=

34、(chDate8-'0')*10+chDate9-'0'int IsLeapYear(int nYear) / 2 if(nYear%4=0) return 1; else return 0;int GetWeekOfFirstday(int nYear) / 3 if(nYear>2000) return (nYear-2001)*365+(nYear-2001)/4+1)%7; else if(nYear<2000) return 6-(2000-nYear)*365+(2000-nYear)/4)%7; else return 6;int Ge

35、tWeek(int nYear,int nMonth,int nDay,int nWeekOfFirstday) / 4 int nDaysYear=31,28,31,30,31,30,31,31,30,31,30,31; int nDaysLeapYear=31,29,31,30,31,30,31,31,30,31,30,31; int i,sum=0; if(nYear%4=0) for(i=0;i<(nMonth-1);i+) sum+=nDaysLeapYeari; return (sum+nDay+nWeekOfFirstday-1)%7; else for(i=0;i<

36、(nMonth-1);i+) sum+=nDaysYeari; return (sum+nDay+nWeekOfFirstday-1)%7; void PrintCalendar(int nWeek,int nDay,int nMonthDays,char *chDate) / 5 int i,j; printf("the calender of this month as following:n"); printf("*n"); printf(" SUN MON TUE WEN THU FRI STAn"); for(i=1,j=1

37、;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.七種排序算法： 快速排序void quickSort(int a,int left,int right)int i=left;int j=right;int temp=aleft;if(left>=right)re

38、turn;while(i!=j)while(i<j&&aj>=temp) j-;if(j>i)ai=aj;/ai已經(jīng)賦值給temp,所以直接將aj賦值給ai,賦值完之后aj,有空位while(i<j&&ai<=temp)i+;if(i<j)aj=ai;ai=temp;/把基準(zhǔn)插入,此時(shí)i與j已經(jīng)相等Rlow.pivotpos-1.keysRpivotpos.keyRpivotpos+1.high.keysquickSort(a,left,i-1);/*遞歸左邊*/quickSort(a,i+1,right);/*遞歸右邊*/

39、插入排序 選擇排序void SelectionSort(int *a, int n)    int i, j, index, value;    for (i = 0; i < n - 1; i +)         index = i;        value = ai;        for (j = i + 1;

40、j < n; j +)            if (value > aj)                 index = j;                value =

41、aj;                    aindex = ai;        ai = value;        Display(a, n);    冒泡排序void BubbleSort(int array,int n) int

42、 i,j,temp;/外循環(huán)控制循環(huán)趟數(shù) for(i=0; i<n-1; i+) /內(nèi)循環(huán)選擇要進(jìn)行比較的數(shù)  for(j=0; j<n-1-i; j+)     if(arrayj>arrayj+1)       temp=arrayj;    arrayj=arrayj+1;    arrayj+1=temp;  &

43、#160;    printf("nThe sorted numbers are:"); for(i=0; i<n; i+)   printf("",arrayi);  printf("nn"); 堆排序void HeapAdjust(int *a,int i,int size) /調(diào)整堆 int lchild=2*i; /i的左孩子節(jié)點(diǎn)序號(hào) int rchild=2*i+1; /i的右孩子節(jié)點(diǎn)序號(hào) int max=i; /臨時(shí)變

44、量 if(i<=size/2) /如果i是葉節(jié)點(diǎn)就不用進(jìn)行調(diào)整 if(lchild<=size&&alchild>amax) max=lchild; if(rchild<=size&&archild>amax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size); /避免調(diào)整之后以max為父節(jié)點(diǎn)的子樹(shù)不是堆 void BuildHeap(int *a,int size) /建立堆 int i; for(i=size/2;i>=1;i-) /非葉節(jié)點(diǎn)最大序號(hào)值

45、為size/2 HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序 int i; BuildHeap(a,size); for(i=size;i>=1;i-) /cout<<a1<<" " swap(a1,ai); /交換堆頂和最后一個(gè)元素，即每次將剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /將余下元素重新建立為大頂堆 HeapAdjust(a,1,i-1); /重新調(diào)整堆頂節(jié)點(diǎn)成為大頂堆 歸并排序void Merge(int *SR, int *TR,

46、int i, int m, int n)    / 將有序的SRi.m和SRm+1.n歸并為有序的TRi.n    int j = m+1;    int k = i;    for(; i<=m && j<=n; +k)/ 將SR中記錄按關(guān)鍵字從小到大地復(fù)制到TR中        if (SRi<=SRj)      &#

47、160;      TRk = SRi+;        else            TRk = SRj+;                while (i<=m) TRk+ = SRi+;   / 將剩余的 SRi.m 復(fù)制到TR 

48、60;  while (j<=n) TRk+ = SRj+;   / 將剩余的 SRj.n 復(fù)制到TR/Mergevoid Msort( int *SR, int *TR1, int s, int t )    / 對(duì)SRs.t進(jìn)行歸并排序，排序后的記錄存入TR1s.t    if (s=t)        TR1s = SRs;    else    

49、60;   int TR210 ;        int m = (s+t)/2;   / 將 SRs.t 平分為 SRs.m 和 SRm+1.t        Msort(SR,TR2,s,m);  / 遞歸地將 SRs.m 歸并為有序的 TR2s.m        Msort(SR,TR2,m+1, t); / 遞歸地將SRm+1.t

50、歸并為有序的TR2m+1.t        Merge(TR2,TR1,s,m,t); / 將TR2s.m和TR2m+1.t 歸并到 TR1s.t    / else / Msort 基數(shù)排序int getdigit(int x,int d) int a = 1, 1, 10; /因?yàn)榇艛?shù)據(jù)最大數(shù)據(jù)也只是兩位數(shù)，所以在此只需要到十位就滿足 return (x / ad) % 10); /確定桶號(hào) void PrintArr(int ar,int n) for(int i = 0; i

51、 < n; +i) cout<<ari<<" " cout<<endl;void msdradix_sort(int arr,int begin,int end,int d) const int radix = 10; int countradix, i, j; /置空 for(i = 0; i < radix; +i) counti = 0; /分配桶存儲(chǔ)空間 int *bucket = (int *) malloc(end-begin+1) * sizeof(int); /統(tǒng)計(jì)各桶需要裝的元素的個(gè)數(shù) for(i = beg

52、in;i <= end; +i) countgetdigit(arri, d)+; /求出桶的邊界索引，counti值為第i個(gè)桶的右邊界索引+1 for(i = 1; i < radix; +i) counti = counti + counti-1; /這里要從右向左掃描，保證排序穩(wěn)定性 for(i = end;i >= begin; -i) j = getdigit(arri, d); /求出關(guān)鍵碼的第d位的數(shù)字， 例如：576的第3位是5 bucketcountj-1 = arri; /放入對(duì)應(yīng)的桶中，countj-1是第j個(gè)桶的右邊界索引 -countj; /第j個(gè)桶

53、放下一個(gè)元素的位置(右邊界索引+1) /注意：此時(shí)counti為第i個(gè)桶左邊界 /從各個(gè)桶中收集數(shù)據(jù) for(i = begin, j = 0;i <= end; +i, +j) arri = bucketj; /釋放存儲(chǔ)空間 free(bucket); /對(duì)各桶中數(shù)據(jù)進(jìn)行再排序 for(i = 0;i < radix; i+) int p1 = begin + counti; /第i個(gè)桶的左邊界 int p2 = begin + counti+1-1; /第i個(gè)桶的右邊界 if(p1 < p2 && d > 1) msdradix_sort(arr,

54、p1, p2, d-1); /對(duì)第i個(gè)桶遞歸調(diào)用，進(jìn)行基數(shù)排序，數(shù)位降 1 D.界面型 a. OpenGL圖形庫(kù)程序 黑白框 void init( void ) glClearColor( 0.0, 0.0, 0.0, 0.0 ); glShadeModel( GL_FLAT );void display( 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

55、, 25.0 ); glPopMatrix( ); glutSwapBuffers( );void spinDisplay( void ) spin = spin + 2.0; if ( spin > 360.0 ) spin = spin - 360.0; glutPostRedisplay( );void reshape( int w, int h ) glViewport( 0, 0, (GLsizei)w, (GLsizei)h ); glMatrixMode( GL_PROJECTION ); glLoadIdentity( ); /void glOrtho(GLdouble

56、left,GLdouble right,GLdouble bottom,GLdouble top,GLdouble near,GLdouble far); glOrtho( -50.0, 50.0, -50.0, 50.0, -1.0, 1.0 ); glMatrixMode( GL_MODELVIEW ); glLoadIdentity( );void mouse( int button, int state, int x, int y ) switch ( button ) case GLUT_LEFT_BUTTON: if ( state = GLUT_DOWN ) glutIdleFu

57、nc( spinDisplay ); break; case GLUT_MIDDLE_BUTTON: if ( state = GLUT_DOWN ) glutIdleFunc( 0 ); break; default: break; void keyboard( unsigned char key, int x, int y ) switch (key) case 'a': glutIdleFunc( spinDisplay ); break; case 's': glutIdleFunc( 0 ); break; 螺旋曲線void SetupRC() glClearColor(0.0f,0.0f,0.0f,1.0f); glColor3f(1.0f,1.0f,1.0f);void RenderScene(void) GLfloat x,y,z,angle; glClear(GL_COLOR_BUFFER_BIT); glPushMatrix(); glTranslatef(0