西北工业大学C语言课程设计大作业文档格式.docx
《西北工业大学C语言课程设计大作业文档格式.docx》由会员分享，可在线阅读，更多相关《西北工业大学C语言课程设计大作业文档格式.docx（78页珍藏版）》请在冰点文库上搜索。
绘制彩色立方体
1.3开发工具
codeblock
1.4应用平台
Windows2000/XP/Vista32位/win7、8
2详细设计
2.1程序结构
该题涉及到数组存储
b.求555555的约数中的最大三位数：
该题只用到循环和判断语句，从999向下搜索即可
年历的设计与计算，应首先判断“某年某月某日是星期几”，即能被4且不能被100整除或能被400整除的数。
这样，接下来的事情就简单了，输入年份，打印出相应的日历。
快速排序（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个元素交换，至此选择排序完成。
5612809120（文中仅细化了第一趟的选择过程）
第1趟：
1256809120
第2趟：
1220809156
第3趟：
1220569180
第4趟：
1220568091
算法分析
（用于交换和记录索引）
不稳定（比如序列【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+2]称为大顶堆，满足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
73
39
接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：
接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：
14
81
93
观察可以看到，此时原无序数据序列已经排序完毕。
如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。
那么，到这里为止，你觉得你是不是一个细心的人？
不要不假思索的回答我。
不论回答什么样的问题，都要做到心比头快，头比嘴快。
仔细看看你对整个排序的过程中还有哪些疑惑？
真看不到？
觉得我做得很好？
抑或前面没看懂？
如果你看到这里真心没有意识到或发现这个问题，那我告诉你：
悄悄去找个墙角蹲下用小拇指画圈圈（好好反省反省）。
追问：
观察原无序数据序列中73
43三个数据的顺序，在经过第一次（按照个位数值，它们三者应该是在同一个桶中）分配之后，
在桶中顺序由底至顶应该为73
43（即就是装的迟的在最上面，对应我们上面的逻辑想象应该是43
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法实现
最高位优先法通常是一个递归的过程：
先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。
再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。
3>
依此重复，直到对关键码Kd完成排序为止。
4>
最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。
（2）LSD法实现
最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，
再依据次低位关键码Kd-1对上一趟排序的结果再排序，
依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。
使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。
【3】基数排序稳定性分析
基数排序是稳定性排序算法，那么，到底如何理解它所谓的稳定特性呢？
比如：
我们有如下欲排数据序列：
下面选择LSD逻辑演示
第一次按个位数值分配，结果如下图所示：
然后收集数据结果如下：
第二次按十位数值分配，结果如下图所示：
分配时是从欲排数据序列的末位开始进行，逐次分配至首位。
a.OpenGL图形库程序
openGL（OpenGraphicsLibrary）从本质上说，它是一个3D图形和模型库，具有高度的移植性。
我们可以将openGL看做是一个C运行时的函数库，这个函数库可以帮助我们绘制二维或三维的图像。
静态链接库和动态链接库
静态库：
lib文件。
编译时代码编译进exe中，会使得程序体积非常庞大。
不利于模块的共享。
优点：
不会有dllhell的问题。
好像“企业间的吞并”。
动态库：
dll文件。
代码在dll中，其他程序调用dll中的代码，多个程序可以共享。
缺点：
dllhell（dll地狱），版本问题。
另外，主要用到的就是“glut.h”这个头文件，它包括了我们所需的大多数函数，直接调用很方便！
我们利用OpenGl函数库编写了三个简单的程序，分别是：
绘制黑白框、绘制螺旋曲线、绘制彩色立方体。
2.2主要功能
该题主要实现赛场的积分统计
该题主要实现一个数的约数的求解
该题主要实现制定年月日期的输出
该题主要实现一组数据的排序
a.OpenGL图形库程序
该题主要实现OpenGl图形库在Windows系统下的图形设计
/*请在这里说明你的大作业程序功能，并详细描述它们实现的原理和方法（包含算法、数据结构）。
*/
2.3函数实现
voidDateTrans（char*chDate,int*nYear,int*nMonth,int*nDay）//1
{
*nYear=（chDate[0]-'
0'
）*1000+（chDate[1]-'
）*100+（chDate[2]-'
）*10+chDate[3]-'
;
*nMonth=（chDate[5]-'
）*10+chDate[6]-'
*nDay=（chDate[8]-'
）*10+chDate[9]-'
}
intIsLeapYear（intnYear）//2
if（nYear%4==0）
return1;
else
return0;
intGetWeekOfFirstday（intnYear）//3
if（nYear>
2000）
return（（nYear-2001）*365+（nYear-2001）/4+1）%7;
elseif（nYear<
return6-（（2000-nYear）*365+（2000-nYear）/4）%7;
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;
{
for（i=0;
i<
（nMonth-1）;
i++）
sum+=nDaysLeapYear[i];
return（sum+nDay+nWeekOfFirstday-1）%7;
sum+=nDaysYear[i];
voidPrintCalendar（intnWeek,intnDay,intnMonthDays,char*chDate）//5
inti,j;
printf（"
thecalenderofthismonthasfollowing:
\n"
）;
***
升级会员 