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

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

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

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

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

4、76,13,65进行三次交换后27,38,13,97,76,49,65进行四次交换后27,38,13,49,76,97,65JJ完成一趟排序27,38,13,49,76,97,65A一次划分之后Fq27,38,13,49,76,97,65分别进行快排序13,27,3865,76,97有序序列为13,27,38,49,65,76,97具体做法是附设两个指针P和q,它们的初值分别指向第一个数49和最后一个数27,设枢轴为49,首先从q所指的位置起向前搜索找到第一个小于49的数然后跟p所指的数互相交换,然后从p所指的位置向后搜索,找到第一个大于49的数跟q所指的数互相交换。重复这两步直至IJp=q为

5、止。冒泡法的排序效率比较低，总的时间复杂度为0(d)快速排序法的效率高，理想情况下总的时间复杂度为O(n1og2n),最坏的情况下，时间复杂度为0(d)。四、各种变量的定义和作用随机产生的10个099之间叫随机整数存放在数组Sjzs1和sjzs2中。用冒泡法排序时用数组SjZS1作为参数传递，用快速排序时用数组sjzs2作为参数传递，其中Sjzs1定义为内部数组，而sjzs2定义为外部数组。每个数组只用到1号到10号十个元素，0号元素空着没用。mpf函数实现冒泡排序。P,q,t,是三个指向整形的指针,初始时P指向数组sjzs2的1号元素,q指向数组sjzs2的10号元素。t指向sjzs2的1号

6、元素。mcs变量用来统计冒泡法的循环次数kcs变量用来统计快速排序法的循环次数。Sort函数是实现快速排序的递归调用函数Qs函数用来实现在快速排序过程中的指针定位从而对分数据。五、各功能模块的算法处理流程图及说明Qs函数N-S图主函数N-S图当pqkcs+当p=*pq-交换*p与*q当pq并且*p=*qP+交换*p与*qI=P产生10个随机数分别赋给sjzs1和sjzs2调用函数mpf实现冒泡排序调用函数SOrt实现快速排序输出快速排序与冒泡排序的循环次数差冒泡法函数mpfN-S图说明：MPf函数中的形参数组a接受主函数中调用时传递过来的数组Sjzs1的地址，这是地址传递。QS函数是定位函数，

7、将要排序数据对分成独立的两部分。Sort函数首先调用函数qs实现对分，然后通过递归调用对定位数据的前部分数据和后部分数据再分别排序，从而实现快速排序。六、程序设计过程中遇到的问题及解决过程在冒泡法程序设计中，设计双重循环时出现问题。发现循环的起止点容易出问题，后来在外循环跟内循环的起止数据上进行了修改问题才得以解决。在快速排序程序设计时，算法的设计觉得有困难，程序实现阶段，使用指针过程中碰到了死循环，经过大量调试发现是循环条件设置错误。开始时设为p*3发现给5个数的时候不会出问题，但是当给出10个数时就会发生死循环。后改为p*p,问题得到解决。七、设计心得体会经过这个冒泡法和快速排序法程序的设

8、计，感觉到了程序设计的无限魅力，感受到反复失败后成功的喜悦，同时领略了探索和追求的乐趣，体会到成就感带来的自豪与自信。在程序设计过程中，深深觉得算法设计的重要性，算法就是程序设计的灵魂，算法正确了程序就不会出大问题，如果算法是错误的,那么程序就一定不会正确。程序=算法+数据结构+程序设计方法数据结构固然重要，但算法是设计的灵魂，算法是解决“做什么”和“怎么做”的问题。程序只是算法的体现。不了解算法就谈不上程序设计。八、附源程序#inc1udenstdio.hinc1udenstd1ib.h#inc1udentime.h/*定义三个外部指针*/intsjzs211,*t=sjzs2,*p=sjz

9、s2,*q;/*用于存放随机数外部数组sjsz2*/intmcs=0;/*冒泡法的循环次数为mcs*/intkcs=0;/*快速排序法的循环次数为kcs*/*冒泡法排序函数*/intmpf(inta)intij,temp;for(j=1；j=9;j+)for(i=1;iai+1)temp=ai;ai=ai+1;ai+1=temp;)printf(,inputmaopaofasortdetennumbersn);for(i=1;i11;i+)printf(,%d,ai);Printf(n);printf(maopaofaxunhuancishuis:%d,mcs);)*快速排序法定位函数*/in

10、tqs(int*p,int*q)inttemp;whi1e(pq)kcs+;*计算快速排序法循环次数*/whi1e(p=*p)q-;temp=*p;*p=*q;*q=temp;whi1e(pq&*p=*q)p+；temp=*p;*p=*q;*q=temp;t=p；*快速排序法递归调用函数*/intsort(int*p,int*q)if(Pq)qs(p,q);sort(p,t-1);sort(t+1,q);main()inti,sjzs111;/*用于存放随机数的数组sjsz1*/time_tt;c1rscr();/*产生10个0-99之间的随机整数*/srand(unsigned)time(&

11、t)printf(inputtenrandomnumbersfrom0to99nn);for(i=0;i10;i+)sjzs1i+1=rand()%100;sjzs2i+1=sjzs1i+1;printf(%d,sjzs1i+1);)printf(n);mpf(sjzs1);*下面程序段实现快速排序*/q=sjzs2+10;*q指针指向数组元素sjzs210*/sort(p,q);printf(kuaisusort1aternumbersisn,);for(i=1;i=10;i+)printf(,kuaisusort1aternumbersis:%dn,sjzs2i);printf(,kuai

12、susortxunhuancishushi:%d,kcs)printf(kuaisupaixuyumaopaofadeXunhuancishuchaisr%d,kcs-mcs)附调试过程部分图:云D:TurboCTC.EXEinputtenrandomnubersfron0to9928.32.B26627.93653422.inptiZOPnOfasortdetennu*ber3:22,27,28,32,34,65,66,82,92,93,raopaofxunhuanc:ishuis：4SBKC:TurboCTC.EXEinputtenrandomnumbersfrom0to9968,47,19,66.45,96,41,89,39,81,inputaopaofasortdetennunbers：19,39,41,45,47,66,68,81,89,96,naopaofaunhuancishuis：45kuaisusort1aterunberwis19394145476668818996huaisusortunuancisuis：13kuaihenpfunhuancishuchais:-32