《中南大学数据结构实验报告》由会员分享，可在线阅读，更多相关《中南大学数据结构实验报告（14页珍藏版）》请在金锄头文库上搜索。
1、中南大学数据结构试验报告题目实验七学生姓名王云鹏学号 8213180228指导老师郑瑾学 院计算机学院专业班级物联网1802完成时间2020.6指导老师评定 签名实验七1. 需求分析本实验目的是使读者，掌握常用排序方法的基本思想，通过实验加深理解各种排序算法，通过实 验掌握各种排序方法的时间复杂度分析，了解各种排序方法的优缺点及适用范围。1排序算法的实现（设计性实验）问题描述 排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素 的任意序列重新排列成一个按键有序的序列。学习和研究各种排序方法是计算机工作者的一项重要工 作课题。基本要求随机产生n个整数（依次为n赋
2、值100、200、300、1 000和2 000），将其存于数组Al.n中。对主 要算法（顺序查找、插入排序、归并排序、堆排序和快速排序）进行实验比较，计算出平均比较次数 c”、平均移动次数m”及执行时间t”。c”和m”由程序自动计算，tn由系统时间计算。对实验结果数据进行对比分析。测试数据由随机数生成器决定。实现提示（1）设计一个驱动程序，其任务是，随机输入一组原始数据A1.”,对于查找还需准备一个键码值（可以随机产生，也可在 A1.”中按索引号挑选若干有代表性的数据）。对每组原始数据，分别调用 查找或排序算法过程。（2）为了自动计算c”和m”需要在每个算法过程中的适当位置插入计数操作。手工
3、计算每个算法的执行时间t”时，为了减少计时误差，删除所插入的计数操作，并按”的大小确 定一个K,对每个查找或排序算法过程反复调用K次，在调用开始前设置一个计时起点t,在K次调用 执行后可打印信息。设计时的终点为几，则 t0）/K便是算法的大致执行时间。选作内容 对不同的输入表长做试验，观察含义相同的变量相对于表长的变化关系，还可以对稳定性做验证。 2统计成绩（综合性实验）问题描述给出”个学生的m门考试的成绩表，每个学生的信息由学号、姓名及各科成绩组成。对学生的考试 成绩进行有关统计，并打印统计表。基本要求（1）按总数高低次序，打印出名次表，分数相同的为同一名次。（2）按名次打印出每个学生的学号
4、、姓名、总分以及各科成绩。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据。选作内容对各科成绩设置不同的权值2. 概要设计设计性实验函数：tempi ate void print_array(t 白厂ay j jint array_size) tempi ate vcid wy_swap(t &b)|class ancestorclass setLsearch : public antes tor- class insert sort : public ancestor- /WFcla55 merge_sort : public ancestor/.：class lheap_sa
5、rt : public ancestor class quick sort : public ancestor/. m int wainO 综合性实验函数：typedef struct t/pede-F struct-templatevoid my swapft &a,丈 &b) void sort(studentinfo* si,int student_num) int main() -3. 详细设计 设计性实验#include #include #include using namespace std;templatevoi_!gg(t array,int array_size) /模 f
6、or(int i=0;iarray_size;i+)coutarrayi;if (i+1)%50=0)coutendl;coutendl;templatevoid my_swap(t &a,t &b)/模板，t temp=a;a=b;b=temp;class ancestorpublic:long cn = 0;/平均比较次数long mn = 0;/平均移动次数long tn = 0;/平均执行时间单位：CPU时钟数int array_size;int *array;ancestor(int n)初始化array,存放待用数字序列array_size = n;/ array=new inta
7、rray_size;array = (int *)malloc(array_size * sizeof(int);/位 array 分配空间/ int xarray_size;/ array=x;srand(unsigned) ti me(NULL);/ 随机数种子for (int i = 0; i array_size; i+)arrayi = rand() % array_size;用随机数序列初始化jrrayclass seq_search : public ancestor /顺序查找public:seq_search(int n,int dest):ancestor(n)clock_
8、t start_time,end_time;st ar t_t ime=clock(); /计时程序int flag=0;是否查找到的标志位for (in t i=0;in;i+)/遍历查找cn+;if (arrayi=des t)/找到flag=1;/ coutdest位于序列的第i+1位endl;end_time=clock();，/停止计时/ tn=(double)(end_time-start_time)/CLOCKS_PER_SEC; tn=end_time-start_time;if (flag=0) 没找到/ cout数字序列中没destendl;； class insert_s
9、ort : public ancestor /插入排序public:insert_sort(int n):ancestor(n)clock_t start_time,end_time;start_time=clock(); /计时for (in t i=1;in;i+)/遍历所有数据，看能否往前插入cn+;if(arrayiarrayi-1)若前一个比当前的大，就接着往前寻找，否则说明当前数据有序,要移动int temp=arrayi;int j;for(j=i-1;temp=0；j-)/移动比当前所有数据大的数向后移动一位，覆盖arrayj+1=arrayj; cn+;/ 计数mn+;/ c
10、outjendl;array j+1= temp;/最后，插入当前数据到比他略小的数据之后end_time=clock();tn=end_time-start_time;class merge_sort : public ancestor /归并排序public:merge_sort(int n):ancestor(n)clock_t start_time,end_time;start_time=clock(); /计时my_sort(array,array_size,0,array_size-1); /排序 end_time=clock();tn=end_time-start_time;vo
11、id my_sort(int array,int array_size,int left,int right)/array 为待的下界，right为上界if (leftright)int mid=(int)(left+right)/2);my_sort(array,array_size,left,mid); /拆开上半部分my_so rt( array,array_size,mid+1,righ t); 拆开下半部分 merge(array,array_size, lef t,mid,righ t); /归并拆开的部分void merge(int array,int array_size,in
12、t left,int mid,int right) /归并int i,j,k;int tempright-left+1;存放需要参加比较的数据for (in t i=lef t;i = righ t;i+) 从 array 赋值，初始化 temptempi-left=arrayi;for(i=left,j=mid+1,k=left;i=mid & j=right;k+)两条数据合并，挨个比较并在一起 if (tempi-left= tempj-left)/i 小，将i 所在数据存入arrayarrayk=tempi-left;i+;else/j小，将j所在数据存入arrayarrayk=tem
13、pj-left;j+;cn+;mn+;while (i=mid)/某条数据放完，将剩下的数据直接放入rrayarrayk+=tempi-left;i+;mn+;while(j=0;i-)heap_adjust(i,array_size-1); /建立一swap(array0,arrayarray_size-1); 将堆顶与堆底互换mn=mn+3;for (in t i=array_size-2;i0;i-) /不断将堆顶与堆底互换，画完调整堆，使之保持大顶堆。而有丿数据都挨个沉到堆底，最终从小到大排序heap_adjust(0,i);swap(array0,arrayi);mn=mn+3;end_time=clock();tn=end_time-start_time;void heap_adjust(int s,int m) /大置不对，其他都是对的)int temp=arrays;mn+;for (in t j=
