西北工业大学C语言专业课程设计大作业.docx
- 文档编号:14329832
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:75
- 大小:334.02KB
西北工业大学C语言专业课程设计大作业.docx
《西北工业大学C语言专业课程设计大作业.docx》由会员分享,可在线阅读,更多相关《西北工业大学C语言专业课程设计大作业.docx(75页珍藏版)》请在冰点文库上搜索。
西北工业大学C语言专业课程设计大作业
学院
电子信息学院
班级
08031302班
学号
姓名
张昌武
摘要
此次大作业包含一个标准型大作业,一个界面型大作业,两个数学型大作业和一个算法型大作业。
此次联络我选择题目是:
A.数学型
a.歌星大奖赛
b.求最大数
B.标准型
a.打印指定年份公历表和农历表
C.算法型
a.七种排序算法
D.界面型
a.OpenGL图形库程序
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开发工具
codeblock
1.4应用平台
Windows/XP/Vista32位/win7、8
2具体设计
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 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,R2....Rn)构建成大顶堆,此堆为初始无序区; 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,R2....Rn-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 那么,若要将一副扑克牌排成下列次序: 梅花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; else return0; } intGetWeekOfFirstday(intnYear)//3 { if(nYear>) return((nYear-)*365+(nYear-)/4+1)%7; elseif(nYear<) return6-((-nYear)*365+(-nYear)/4)%7; else return6; } 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(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 西北工业大学 语言 专业课程 设计 作业