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

学 院电子信息学院班 级08031302班学 号姓 名张昌武摘要 此次大作业包含一个标准型大作业，一个界面型大作业，两个数学型大作业和一个算法型大作业。此次联络我选择题目是：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 /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(nYear) return (nYear-)*365+(nYear-)/4+1)%7; else if(nYear) return 6-(-nYear)*365+(-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); /求出关键码