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函数是定位函数,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C语言程序设计 王新萍 大作业 语言程序设计 作业