西北工业大学C语言课程设计大作业

年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;