C语言程序设计王新萍大作业.docx

《C语言程序设计王新萍大作业.docx》由会员分享，可在线阅读，更多相关《C语言程序设计王新萍大作业.docx（16页珍藏版）》请在第一文库网上搜索。

1、C语言程序设计论文班级：会计101601姓名：郭甲琦学号：学1016040106一、 设计题目3二、 设计要求3三、 算法及数据结构设计描述3四、 各种变量的定义和作用6五、 各功能模块的算法处理流程图及说明6六、 程序设计过程中遇到的问题及解决过程8七、 设计心得体会9八、 附源程序9一、设计题目用冒泡法和快速排序法分别实现对10个数由小到大的排序, 二、设计要求在程序中分别输出用两种算法排序后的结果，并能比较冒泡法 和快速排序法这两种算法在处理同一数组数据时的循环次数差并输 出。三、算法及数据结构设计描述冒泡法的思路是：将相邻两个数比较，将小的调到前头见下图1。第二次8 5 2 O 三Il

2、 第 图85 458542O第五次8542O回结果若有6个无序的数9,8,5,420。第一次将8和9对调，第二次将第 二个数和第三个数（9和5）,如此共进行5次，得至U 8-5-4-2-0-9 的顺序，可以看到，最大的数9已“沉底”，成为最下面一个数。二 小的数“上升”。最小的数0已向上“浮起”一个位置，经第一趟（共 5次）后，已得到最大的数。然后进行第二趟比较，对余下的前面5 个数按上法进行比较。见下图2。经过4次比较，得到次大的数8。 如此进行下去。可以推知，6个数要比较5趟。在第一趟中要进行两 两比较5次，在第二趟中要两两比较4次第5趟比较1次。如果有个数，则要进行n-1趟比较。在第j趟

3、比较中要进行n-j次两两 比较。快藉在序是对瞽！法排序的一碗加进,它的浦懑路是施也一趟 排序将待排记录分割成独立的两部分,其中一部分数据均比另一部分 的数据小,则可分别对这两部分数据继续进行排序,以达到整个序列有 序。假设待排序的序列为49, 38, 65, 97, 76, 13, 270首先选取第 一个数据49作为枢轴，然后重新排列其余记录，将所有比它小的数 排在它的前面，所有比它大的数据都安置在它的位置之后。由此可以 由该枢轴所在的位置作为分界线，将序列分割成两个子序列，这个过 程称作一趟快速排序。如下图3初始数据49, 38, 65, 97, 76, 13, 27fpq进行一次交换之后2

4、7, 38, 65, 97, 76, 13, 49进行二次交换后27, 38, 49, 97,76, 13,65进行三次交换后27, 38, 13, 97, 76, 49, 65进行四次交换后27, 38, 13,49,76,97,65J J完成一趟排序27,38, 13,49, 76,97, 65A一次划分之后Fq 27,38, 13,49, 76, 97, 65分别进行快排序 13, 27,3865,76,97有序序列为13, 27,38,49,65,76,97具体做法是附设两个指针P和q,它们的初值分别指向第一个数49和 最后一个数27,设枢轴为49,首先从q所指的位置起向前搜索找到第一

5、 个小于49的数然后跟p所指的数互相交换,然后从p所指的位置向后 搜索,找到第一个大于49的数跟q所指的数互相交换。重复这两步直 至IJ p=q为止。冒泡法的排序效率比较低，总的时间复杂度为0(d)快速排序法的效率高，理想情况下总的时间复杂度为O(nlog2n),最坏 的情况下，时间复杂度为0(d)。四、各种变量的定义和作用随机产生的10个099之间叫随机整数存放在数组Sjzsl和sjzs2 中。用冒泡法排序时用数组SjZSl作为参数传递，用快速排序时用数 组sjzs2作为参数传递，其中Sjzsl定义为内部数组，而sjzs2定义为 外部数组。每个数组只用到1号到10号十个元素，0号元素空着没

6、用。mpf函数实现冒泡排序。P,q,t,是三个指向整形的指针,初始时P指向数组sjzs2的1号元素, q指向数组sjzs2的10号元素。t指向sjzs2的1号元素。mcs变量用来统计冒泡法的循环次数kcs变量用来统计快速排序法的循环次数。Sort函数是实现快速排序的递归调用函数Qs函数用来实现在快速排序过程中的指针定位从而对分数据。五、各功能模块的算法处理流程图及说明Qs函数N-S图主函数N-S图当pqkcs+当p=*pq-交换*p与*q当pq并且*p=*qP+交换*p与*qI=P产生10个随机数分别赋给sjzsl和sjzs2调用函数mpf实现冒泡排序调用函数SOrt实现快速排序输出快速排序与

7、冒泡排序的循环次数差冒泡法函数mpf N-S图说明：MPf函数中的形参数组a接受主函数中调用时传递过来的数组Sjzsl 的地址，这是地址传递。QS函数是定位函数，将要排序数据对分成独立的两部分。Sort函数首先调用函数qs实现对分，然后通过递归调用对定位数据 的前部分数据和后部分数据再分别排序，从而实现快速排序。六、程序设计过程中遇到的问题及解决过程在冒泡法程序设计中，设计双重循环时出现问题。发现循环的 起止点容易出问题，后来在外循环跟内循环的起止数据上进行了修改 问题才得以解决。在快速排序程序设计时，算法的设计觉得有困难， 程序实现阶段，使用指针过程中碰到了死循环，经过大量调试发现是 循环条

8、件设置错误。开始时设为p *3发现给5个数的时 候不会出问题，但是当给出10个数时就会发生死循环。后改为p*p,问题得到解决。七、设计心得体会经过这个冒泡法和快速排序法程序的设计，感觉到了程序设计 的无限魅力，感受到反复失败后成功的喜悦，同时领略了探索和追求 的乐趣，体会到成就感带来的自豪与自信。在程序设计过程中，深深觉得算法设计的重要性，算法就是程 序设计的灵魂，算法正确了程序就不会出大问题，如果算法是错误的, 那么程序就一定不会正确。程序=算法+数据结构+程序设计方法数据结构固然重要，但算法是设计的灵魂，算法是解决“做什 么”和“怎么做”的问题。程序只是算法的体现。不了解算法就谈不 上程序

9、设计。八、附源程序#include nstdio.hinclude nstdlib.h#include ntime.h/*定义三个外部指针*/int sjzs2l 1 ,*t=sjzs2,*p=sjzs2,*q;/*用于存放随机数外部数组sjsz2*/int mcs=0;/*冒泡法的循环次数为mcs*/int kcs=0;/*快速排序法的循环次数为kcs*/*冒泡法排序函数*/int mpf(int a)int ij,temp;for(j=l；j=9;j+)for(i=l;iai+l)temp=ai;ai=ai+l;ai+l=temp;)printf(,input maopaofa sort

10、de ten numbersn);for(i=l;ill;i+)printf(,%d, ,ai);Printf(n);printf(maopaofa xunhuan cishu is:%d,mcs);)*快速排序法定位函数*/int qs(int *p,int *q)int temp;while(pq) kcs+;*计算快速排序法循环次数*/while (p= *p)q-;temp=*p;*p=*q;*q=temp;while(pq & *p=*q)p+；temp=*p;*p=*q;*q=temp;t=p；*快速排序法递归调用函数*/int sort(int *p,int *q)if (Pq)

11、qs(p,q);sort(p,t-l);sort(t+l,q);main() int i,sjzslll; /*用于存放随机数的数组sjszl*/time_t t;clrscr();/*产生10个0-99之间的随机整数*/srand(unsigned) time(&t)printf(input ten random numbers from 0 to 99nn);for(i=0 ; i10; i+)sjzsli+l=rand()%100;sjzs2i+l=sjzsl i+l;printf(%d, ,sjzsl i+l);)printf(n);mpf(sjzsl);*下面程序段实现快速排序*/q

12、= sjzs2+10;*q 指针指向数组元素 sjzs210*/sort(p,q);printf(kuaisu sortlater numbers isn,);for(i=l;i=10;i+)printf(,kuaisusortlater numbers is :%d n,sjzs2i);printf(,kuaisusort xunhuan cishu shi :%d,kcs)printf (kuaisupaixu yu maopaofa de Xunhuancishu chaisr%d,kcs-mcs)附调试过程部分图:云 D:TurboCTC.EXE input ten random nu

13、bers f ron 0 to 9928.32.B26627.93653422.inpti ZOPnOfa sort de ten nu*ber3:22,27,28,32,34,65,66,82,92,93,raopaof xunhuan c:ishu is：4SBK C:TurboCTC.EXE input ten random numbers from 0 to 9968,47,19,66.45,96,41,89,39,81,inputaopaofa sort de tennunbers：19,39,41,45,47,66,68,81,89,96,naopaofa unhuan cishu is：45kuaisu sort later unberw is19394145476668818996huaisu sort unuan cisu is：13kuaihe npf unhuancishuc ha is:-32