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

学 院电子信息学院班 级08031302班学 号2013301986姓 名张昌武摘要 本次大作业包括一个标准型大作业，一个界面型大作业，两个数学型大作业和一个算法型大作业。本次联系我选择的题目是：A.数学型a.歌星大奖赛 b.求最大数B.标准型 a.打印指定年份的公历表和农历表C.算法型a.七种排序算法D.界面型a.OpenGL图形库程序目录1 摘要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 附件（源程序）361 摘要1.1 设计题目A.数学型a.歌星大奖赛 b.求最大数B.标准型 a.打印指定年份的公历表和农历表C.算法型 a.七种排序算法D.界面型 a.OpenGL图形库程序1.2 设计内容A. 数学型a.十个评委打分，分数在1100之间，选手最后得分为：去掉一个最高分和一个最低分后其余8个分数的平均值。b.求555555的约数中的最大三位数B.标准型 a.打印指定年份的公历表和农历表C.算法型 a.七种排序算法： 快速排序 插入排序 选择排序 冒泡排序 堆排序 归并排序 基数排序D.界面型 a. OpenGL图形库程序: 绘制黑白框 绘制螺旋曲线 绘制彩色立方体1.3 开发工具codeblock1.4 应用平台Windows 2000/XP/Vista 32位/win 7、82 详细设计2.1 程序结构A. 数学型a.十个评委打分，分数在1100之间，选手最后得分为：去掉一个最高分和一个最低分后其余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为切入点对左右两边数按照第一，第二，第三，第四步骤进行，最终快排大功告成。快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序相同，也是O(n2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序，不能把数据分成大小相当的两份，很明显，排序的过程就成了一个歪脖子树，树的深度为n，那时间复杂度就成了O(n2)。尽管如此，需要排序的情况几乎都是乱序的，自然性能就保证了。据书上的测试图来看，在数据量小于20的时候，插入排序具有最好的性能。当大于20时，快速排序具有最好的性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度都为nlog2(n)。1、算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。（1） 分治法的基本思想 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。（2）快速排序的基本思想 设当前待排序的无序区为Rlow.high，利用分治法可将快速排序的基本思想描述为：分解：在Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.pivotpos-1)和Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。注意： 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=Rpivotpos)： Rlow.pivotpos-1.keysRpivotpos.keyRpivotpos+1.high.keys 其中lowpivotposhigh。求解：通过递归调用快速排序对左、右子区间Rlow.pivotpos-1和Rpivotpos+1.high快速排序。组合：因为当求解步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，组合步骤无须做什么，可看作是空操作。2、快速排序算法QuickSort void QuickSort(SeqList R，int low，int high) /对Rlow.high快速排序 int pivotpos； /划分后的基准记录的位置 if(lowarrayj+1)语句中的大于号改为小于号即可。堆排序 堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。1.堆堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Keyi=key2i+1&Keyi=Key2i+1&key=key2i+2 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Keyi=Key2i+1&key=key2i+2称为大顶堆，满足 Keyi=key2i+1&Keyi=key2i+2称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2.Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R1与最后一个元素Rn交换，此时得到新的无序区(R1,R2,.Rn-1)和新的有序区(Rn),且满足R1,2.n-1=Rn; 3)由于交换后新的堆顶R1可能违反堆的性质，因此需要对当前无序区(R1,R2,.Rn-1)调整为新堆，然后再次将R1与无序区最后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 操作过程如下： 1)初始化堆：将R1.n构造为堆； 2)将当前无序区的堆顶元素R1同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。下面举例说明： 给定一个整形数组a=16,7,3,20,17,8，对其进行堆排序。 首先根据该数组元素构建一个完全二叉树，得到然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：20和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。此时3位于堆顶不满堆的性质，则需调整继续调整这样整个区间便已经有序了。 从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R1.n中选择最大记录，需比较n-1次，然后从R1.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（Least significant digital）或MSD（Most significant digital），LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。（2）我们把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。要求如下：花色顺序：梅花方块红心黑桃面值顺序：234.10JQKA那么，若要将一副扑克牌排成下列次序：梅花2，.，梅花A，方块2，.，方块A，红心2，.，红心A，黑桃2，.，黑桃A。有两种排序方法：先按花色分成四堆，把各堆收集起来；然后对每堆按面值由小到大排列，再按花色从小到大按堆收叠起来。-称为最高位优先(MSD)法。先按面值由小到大排列成13堆，然后从小到大收集起来；再按花色不同分成四堆，最后顺序收集起来。-称为最低位优先(LSD)法。【2】代码实现（1）MSD法实现最高位优先法通常是一个递归的过程：先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。依此重复，直到对关键码Kd完成排序为止。最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。（2）LSD法实现最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。【3】基数排序稳定性分析基数排序是稳定性排序算法，那么，到底如何理解它所谓的稳定特性呢？比如：我们有如下欲排数据序列：下面选择LSD逻辑演示第一次按个位数值分配，结果如下图所示：然后收集数据结果如下：第二次按十位数值分配，结果如下图所示：然后收集数据结果如下：注意：分配时是从欲排数据序列的末位开始进行，逐次分配至首位。D.界面型a. OpenGL图形库程序openGL（Open Graphics Library）从本质上说，它是一个3D图形和模型库，具有高度的移植性。我们可以将openGL看做是一个C运行时的函数库，这个函数库可以帮助我们绘制二维或三维的图像。静态链接库和动态链接库静态库：lib文件。编译时代码编译进exe中，会使得程序体积非常庞大。不利于模块的共享。优点：不会有dll hell的问题。好像“企业间的吞并”。动态库：dll文件。代码在dll中，其他程序调用dll中的代码，多个程序可以共享。缺点：dll hell(dll地狱)，版本问题。另外，主要用到的就是“glut.h”这个头文件，它包括了我们所需的大多数函数，直接调用很方便！我们利用OpenGl函数库编写了三个简单的程序，分别是：绘制黑白框、绘制螺旋曲线、绘制彩色立方体。2.2 主要功能A. 数学型a.十个评委打分，分数在1100之间，选手最后得分为：去掉一个最高分和一个最低分后其余8个分数的平均值。该题主要实现赛场的积分统计b.求555555的约数中的最大三位数 该题主要实现一个数的约数的求解B.标准型 a.打印指定年份的公历表和农历表 该题主要实现制定年月日期的输出C.算法型 a.七种排序算法： 快速排序 插入排序 选择排序 冒泡排序 堆排序 归并排序 基数排序 该题主要实现一组数据的排序D.界面型 a. OpenGL图形库程序 该题主要实现OpenGl图形库在Windows系统下的图形设计/*请在这里说明你的大作业程序功能，并详细描述它们实现的原理和方法（包含算法、数据结构）。*/2.3 函数实现B.标准型 a.打印指定年份的公历表和农历表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=(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(nYear2000) return (nYear-2001)*365+(nYear-2001)/4+1)%7; else if(nYear2000) return 6-(2000-nYear)*365+(2000-nYear)/4)%7; else return 6;int GetWeek(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(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;j=nMonthDays;i+) if(i=right)return;while(i!=j)while(i=temp) j-;if(ji)ai=aj;/ai已经赋值给temp,所以直接将aj赋值给ai,赋值完之后aj,有空位while(ij&ai=temp)i+;if(ij)aj=ai;ai=temp;/把基准插入,此时i与j已经相等Rlow.pivotpos-1.keysRpivotpos.keyRpivotpos+1.high.keysquickSort(a,left,i-1);/*递归左边*/quickSort(a,i+1,right);/*递归右边*/ 插入排序 选择排序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; j aj) index = j; value = aj; aindex = ai; ai = value; Display(a, n); 冒泡排序void BubbleSort(int array,int n)int i,j,temp;/外循环控制循环趟数for(i=0; in-1; i+)/内循环选择要进行比较的数for(j=0; jarrayj+1)temp=arrayj;arrayj=arrayj+1;arrayj+1=temp;printf(nThe sorted numbers are:);for(i=0; in; i+)printf(,arrayi);printf(nn); 堆排序void HeapAdjust(int *a,int i,int size) /调整堆 int lchild=2*i; /i的左孩子节点序号 int rchild=2*i+1; /i的右孩子节点序号 int max=i; /临时变量 if(i=size/2) /如果i是叶节点就不用进行调整 if(lchildamax) max=lchild; if(rchildamax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size); /避免调整之后以max为父节点的子树不是堆 void BuildHeap(int *a,int size) /建立堆 int i; for(i=size/2;i=1;i-) /非叶节点最大序号值为size/2 HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序 int i; BuildHeap(a,size); for(i=size;i=1;i-) /couta1 ; swap(a1,ai); /交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /将余下元素重新建立为大顶堆 HeapAdjust(a,1,i-1); /重新调整堆顶节点成为大顶堆 归并排序void Merge(int *SR, int *TR, 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中记录按关键字从小到大地复制到TR中 if (SRi=SRj) TRk = SRi+; else TRk = SRj+; while (i=m) TRk+ = SRi+;/ 将剩余的 SRi.m 复制到TR while (j=n) TRk+ = SRj+;/ 将剩余的 SRj.n 复制到TR/Mergevoid Msort( int *SR, int *TR1, int s, int t )/ 对SRs.t进行归并排序，排序后的记录存入TR1s.t if (s=t) TR1s = SRs; else 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归并为有序的TR2m+1.t Merge(TR2,TR1,s,m,t);/ 将TR2s.m和TR2m+1.t 归并到 TR1s.t / else/ Msort 基数排序int getdigit(int x,int d) int a = 1, 1, 10; /因为待排数据最大数据也只是两位数，所以在此只需要到十位就满足 return (x / ad) % 10); /确定桶号 void PrintArr(int ar,int n) for(int i = 0; i n; +i) coutari ; coutendl;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; /分配桶存储空间 int *bucket = (int *) malloc(end-begin+1) * sizeof(int); /统计各桶需要装的元素的个数 for(i = begin;i = end; +i) countgetdigit(arri, d)+; /求出桶的边界索引，counti值为第i个桶的右边界索引+1 for(i = 1; i = begin; -i) j = getdigit(arri, d); /求出关键码的第d位的数字， 例如：576的第3位是5 bucketcountj-1 = arri; /放入对应的桶中，countj-1是第j个桶的右边界索引 -countj; /第j个桶放下一个元素的位置(右边界索引+1) /注意：此时counti为第i个桶左边界 /从各个桶中收集数据 for(i = begin, j = 0;i = end; +i, +j) arri = bucketj; /释放存储空间 free(bucket); /对各桶中数据进行再排序 for(i = 0;i radix; i+) int p1 = begin + counti; /第i个桶的左边界 int p2 = begin + counti+1-1; /第i个桶的右边界 if(p1 1) msdradix_sort(arr, p1, p2, d-1); /对第i个桶递归调用，进行基数排序，数位降 1 D.界面型 a. OpenGL图形库程序 黑白框 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, 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 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 ) glutIdleFunc( 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, 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: 重定义视口及观察点void resize(int width, int height) glViewport(0, 0, width, height); gluPerspective(120, 1.0, 15, -15);void special(int key, int x, int y) switch(key) case GLUT_KEY_LEFT: YRot-=5; glutPostRedisplay(); break; case GLUT_KEY_RIGHT: YRot+=5; glutPostR