数据结构课程设计-索琳琳.docx

《数据结构课程设计-索琳琳.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》课程设计报告书题目：冒泡排序算法性能分析系别：计算机科学与应用系学号：学生姓名：索琳琳指导教师：薛海燕完成日期：2010年6月14日冒泡排序算法性能分析1.需求分析首先，定义一个数组，规定其最大的存储量是10000数据输入部分，要求用户能从屏幕上输入要测试的数目num，例如num为10。程序通过语句得到这个num，进行分析，如果输入的num<0或者num>10000时，屏幕上提示用户输入错误,请重新输入；如果输入0，表示循环结束；如果数据满足要求程序根据测试的数目num，将随机生成num个无序的数据，并将这些数据存储在数

2、组中。然后，程序调用自定义函数BubbleSort和时间函数，进行冒泡排序并计算出执行的时间。最终，输出部分。如果待测试的数目满足要求输出冒泡排序后排序结果及算法执行时间(ms)，如果不满足要求输出输入错误,请重新输入。2.概要设计从屏幕输入测试的数目输入数据num<0或者num>10000输出显示输入错误请重新输入图1.冒泡排序算法性能分析的流程图输入数据满足要求，调用rand()函数，随机生成数据，存储在数组中显示结果调用冒泡排序函数和时间函数，进行冒泡排序和算法执行时间输入数据为0显示循环结束判断数据是否符合要求程序流程可以用

3、以下流程图来刻画：1.详细设计采用VC++6.0作为开发工具，用数组来存储数据，用函数rand()实现随机数的生成，用函数srand()为函数rand()设置随机种子使之产生的不是伪随机种子，用自定义函数BubbleSort实现冒泡排序，用时间函数实现算法执行时间的计算。3.1冒泡排序的思想描述与算法表示（1）冒泡排序思想描述冒泡排序的过程很简单。首先将容量为n的数组中的第一个数据和第二个数据进行比较，若为逆序，则将两个数据交换之，然后比较第二个数据和第三个数据。依次类推，直至第n-1数据和第n个数据进行过比较为止。上述过程为第一次

4、冒泡排序，其结果使得数据最大的记录安置到数组的第n-1的位置上。然后进行第二次冒泡排序，其结果使得数据次大的记录安置到数组的第n-2位置上。依次类推。整个排序的过程需要进行k(1=

5、for(j=0;jR[j+1]){temp=R[j];R[j]=R[j+1];R[j+1]=temp;}}printf("");}3.2随机生成数据程序每次执行时需要调用函数rand()产生随机数据，并且调用函数srand()为函数rand()设置随机数种子，使之产生不同的随机数序列。定义语句用C语言描述如下：srand(time(NULL));/*用标准库函数srand()为函数rand()设置随机种子,用计算机读取时钟值并把该值自动设置为随机数种子*/for(i=0;i

6、num为用户想要随机生成的数据的数目*/{a[i]=rand();/*用for循环为数组中的每一个元素随机赋值*/}3.3算法执行时间统计在这些数据上程序的执行时间，需要使用库函数中的函数time()，包含在头文件"time.h"中。定义语句C语言描述如下：doubleT,start,end;/*定义变量，代表时间的开始和结束*/start=clock();/*调用clock(),记下程序执行的开始时刻*/BubbleSort(a,num);/*调用自定义函数，进行冒泡排序*/end=clock();/*调用clock(),记下程序

7、执行的结束时刻*/T=(double)(end-start);/*计算程序的执行时间*/1.调试分析在设计过程中主要遇到下列问题：（1）冒泡排序的思想。通过查阅数据结构课本,知道了冒泡排序的思想就是每趟排序比较相邻两个记录的数据并在“逆序”时交换相邻记录，将最大的数据放在最后。一般地，第i趟冒泡排序是从a[0]到a[n-i]依次比较。（2）冒泡排序的算法。根据冒泡排序的思想，查阅了C语言书以及数据结构上机实验参考书，按照从简单到复杂的思想，先从自定义的有限个数据的冒泡排序的过程进行调试分析，然后根据C语言中函数定义的语法要求，自定义

8、了冒泡排序算法实现函数BubbleSort，具体过程描述可以查看详细设计中冒泡排序算法表示。（1）随机数据的生成的方法。通过查阅C语言课本一道猜数游戏程序例题中计算机随机“想”一个数相同的解决办法时，了解到函数rand()产生的是“伪