中南大学数据结构实验报告(七)(共20页).docx

《中南大学数据结构实验报告(七)(共20页).docx》由会员分享，可在线阅读，更多相关《中南大学数据结构实验报告(七)(共20页).docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上中南大学数据结构试验报告题 目 实验七 学生姓名 王云鹏 学 号 指导老师 郑 瑾 学 院 计算机学院 专业班级 物联网1802 完成时间 2020.6 指导老师评定 签名 实验七1. 需求分析本实验目的是使读者，掌握常用排序方法的基本思想，通过实验加深理解各种排序算法，通过实 验掌握各种排序方法的时间复杂度分析，了解各种排序方法的优缺点及适用范围。 1排序算法的实现（设计性实验） 问题描述 排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素 的任意序列重新排列成一个按键有序的序列。学习和研究各种排序方法是计算机工作者的一项重要工 作

2、课题。 基本要求 随机产生n个整数（依次为n赋值100、200、300、1 000和2 000），将其存于数组A1.n中。对主 要算法（顺序查找、插入排序、归并排序、堆排序和快速排序）进行实验比较，计算出平均比较次数 cn、平均移动次数mn及执行时间tn。cn和mn由程序自动计算，tn由系统时间计算。 对实验结果数据进行对比分析。 测试数据 由随机数生成器决定。实现提示 (1) 设计一个驱动程序，其任务是，随机输入一组原始数据A1.n，对于查找还需准备一个键码 值（可以随机产生，也可在A1.n中按索引号挑选若干有代表性的数据）。对每组原始数据，分别调用 查找或排序算法过程。 (2) 为了自动计

3、算cn和mn需要在每个算法过程中的适当位置插入计数操作。 手工计算每个算法的执行时间tn时，为了减少计时误差，删除所插入的计数操作，并按n的大小确 定一个K，对每个查找或排序算法过程反复调用K次，在调用开始前设置一个计时起点t0，在K次调用 执行后可打印信息。设计时的终点为t1，则(t1t0)/K便是算法的大致执行时间。 选作内容 对不同的输入表长做试验，观察含义相同的变量相对于表长的变化关系，还可以对稳定性做验证。 2统计成绩（综合性实验） 问题描述 给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名及各科成绩组成。对学生的考试 成绩进行有关统计，并打印统计表。 基本要求 (1) 按

4、总数高低次序，打印出名次表，分数相同的为同一名次。 (2) 按名次打印出每个学生的学号、姓名、总分以及各科成绩。 测试数据 由读者依据软件工程的测试技术自己确定。注意测试边界数据。 选作内容 对各科成绩设置不同的权值2. 概要设计n 设计性实验函数：n 综合性实验函数：3. 详细设计n 设计性实验#include#include#includeusingnamespacestd;templatevoidprint_array(tarray,intarray_size)/模板，打印数组for(inti=0;iarray_size;i+)coutarrayi;if(i+1)%50=0)couten

5、dl;coutendl;templatevoidmy_swap(t&a,t&b)/模板，交换数据a、bttemp=a;a=b;b=temp;classancestorpublic:longcn=0;/平均比较次数longmn=0;/平均移动次数longtn=0;/平均执行时间,单位：CPU时钟数intarray_size;int*array;ancestor(intn)/初始化array,存放待用数字序列array_size=n;/array=newintarray_size;array=(int*)malloc(array_size*sizeof(int);/位array分配空间/intxa

6、rray_size;/array=x;srand(unsigned)time(NULL);/随机数种子for(inti=0;iarray_size;i+)arrayi=rand()%array_size;/用随机数序列初始化array;classseq_search:publicancestor/顺序查找public:seq_search(intn,intdest):ancestor(n)clock_tstart_time,end_time;start_time=clock();/计时程序intflag=0;/是否查找到的标志位for(inti=0;in;i+)/遍历查找cn+;if(arra

7、yi=dest)/找到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;classinsert_sort:publicancestor/插入排序public:insert_sort(intn):ancestor(n)clock_tstart_time,end_time;start_time=clock();/计时for(inti

8、=1;in;i+)/遍历所有数据，看能否往前插入cn+;if(arrayiarrayi-1)/若前一个比当前的大，就接着往前寻找，否则说明当前数据有序，不需要移动inttemp=arrayi;intj;for(j=i-1;temp=0;j-)/移动比当前所有数据大的数，向后移动一位，覆盖arrayj+1=arrayj;cn+;/计数mn+;/coutjendl;arrayj+1=temp;/最后，插入当前数据到比他略小的数据之后end_time=clock();tn=end_time-start_time;classmerge_sort:publicancestor/归并排序public:me

9、rge_sort(intn):ancestor(n)clock_tstart_time,end_time;start_time=clock();/计时my_sort(array,array_size,0,array_size-1);/排序end_time=clock();tn=end_time-start_time;voidmy_sort(intarray,intarray_size,intleft,intright)/array为待排序数组，left为拆开的下界，right为上界if(leftright)intmid=(int)(left+right)/2);my_sort(array,ar

10、ray_size,left,mid);/拆开上半部分my_sort(array,array_size,mid+1,right);/拆开下半部分merge(array,array_size,left,mid,right);/归并拆开的部分voidmerge(intarray,intarray_size,intleft,intmid,intright)/归并inti,j,k;inttempright-left+1;/存放需要参加比较的数据for(inti=left;i=right;i+)/从array赋值，初始化temptempi-left=arrayi;for(i=left,j=mid+1,k=

11、left;i=mid&j=right;k+)/两条数据合并，挨个比较并在一起if(tempi-left=tempj-left)/i小，将i所在数据存入arrayarrayk=tempi-left;i+;else/j小，将j所在数据存入arrayarrayk=tempj-left;j+;cn+;mn+;while(i=mid)/某条数据放完，将剩下的数据直接放入arrayarrayk+=tempi-left;i+;mn+;while(j=0;i-)heap_adjust(i,array_size-1);/建立一个大顶堆swap(array0,arrayarray_size-1);/将堆顶与堆底互

12、换mn=mn+3;for(inti=array_size-2;i0;i-)/不断将堆顶与堆底互换，画完调整堆，使之保持大顶堆。而有序的数据都挨个沉到堆底，最终从小到大排序heap_adjust(0,i);swap(array0,arrayi);mn=mn+3;end_time=clock();tn=end_time-start_time;voidheap_adjust(ints,intm)/大顶堆，调整堆，从arrays.m使保持大顶堆（假设：除了以s的位置不对，其他都是对的）inttemp=arrays;mn+;for(intj=2*s+1;j=m;j=j*2+1)/调整以s为顶的堆if(j

13、m&arrayj=arrayj)/若s所在已经是最大的位置，则是大顶堆，推出循环break;arrays=arrayj;/更大的向上浮动s=j;/使s记录已经向上浮动数据的位置mn+;arrays=temp;/s所在数据放回堆中mn+;classquick_sort:publicancestor/快速排序public:quick_sort(intn):ancestor(n)clock_tstart_time,end_time;start_time=clock();/计时q_sort(0,array_size-1);/排序end_time=clock();tn=end_time-start_ti

14、me;intpartition(intlow,inthigh)/分段，并且使一次排序inttemp=arraylow;/分界数，根据分界数将待排序列分成大小的两段mn+;while(lowhigh)/遍历，分别从左右向中间靠近，左右互换，完成一次排序while(low=temp)/从右边，挨个寻找比分界数小的数high-;cn+;if(lowhigh)/判断是处理特殊情况arraylow+=arrayhigh;/找到比分界数小的数，放大左边去mn+;while(lowhigh&arraylow=temp)/从左边，挨个寻找比分界数大的数low+;cn+;if(lowhigh)arrayhigh

15、-=arraylow;/找到比分界数大的数，放到右边去（此时，右边该位置的数，已经放到左边）mn+;arraylow=temp;/将分界数放回mn+;returnlow;voidq_sort(intlow,inthigh)/快排if(lowhigh)intmid=partition(low,high);/分段，排一次，此时，左边都是比分界数小的数，右边都是比分界数大的数q_sort(low,mid-1);/排列左半边的数字序列q_sort(mid+1,high);/排列右半边的数字序列;intmain()inttimes_test=100,200,300,1000,2000,5000,1000

16、0,50000;/用来排序的数字个数，组成的集合inttimes_test_size=sizeof(times_test)/sizeof(int);for(inti=0;itimes_test_size;i+)/测试数据seq_searchss=seq_search(times_testi,times_testi/2);insert_sortis=insert_sort(times_testi);merge_sortms=merge_sort(times_testi);heap_sorths=heap_sort(times_testi);quick_sortqs=quick_sort(time

17、s_testi);cout-times_testi个数-endl;cout方法ttcntmnttntendl;cout顺序查找ttss.mntss.tntendl;cout插入排序ttis.mntis.tntendl;cout归并排序ttms.mntms.tntendl;cout堆排序ttths.mnths.tntendl;cout快速排序ttqs.mntqs.tntendl;/ancestora=ancestor(100);/print_array(a.array,a.array_size);/seq_searchss=seq_search(100,50);/print_array(ss.a

18、rray,ss.array_size);/cout执行时间(单位：CPU时钟数)ss.tnendl;/insert_sortis=insert_sort(100);/print_array(is.array,is.array_size);/cout执行时间(单位：CPU时钟数)is.tnendl;/merge_sortms=merge_sort(100);/print_array(ms.array,ms.array_size);/cout执行时间(单位：CPU时钟数)ms.tnendl;/heap_sorths=heap_sort(100);/print_array(hs.array,hs.a

19、rray_size);/cout执行时间(单位：CPU时钟数)hs.tnendl;/quick_sortqs=quick_sort(100);/print_array(qs.array,qs.array_size);/cout执行时间(单位：CPU时钟数)qs.tnendl;return0;#include#include#include#includeusingnamespacestd;typedefstructintchinese;intmath;intenglish;score;/存放分数信息typedefstructstringID;stringname;scoress;student

20、_info;/存放学生信息templatevoidmy_swap(t&a,t&b)/交换数据，a、bttemp=a;a=b;b=temp;voidsort(student_info*si,intstudent_num)/根据总分排序学生intsumstudent_num;for(inti=0;istudent_num;i+)/求出总分sumi=sii.ss.chinese+sii.ss.math+sii.ss.english;for(inti=0;istudent_num;i+)/选择排序for(intj=i;jstudent_num;j+)if(sumisumj)my_swap(sii,si

21、j);my_swap(sumi,sumj);inttemp_score=sum0;intrank=1;couttotaltranktIDtnametchinesetmathtenglishtendl;/输出排好的学生数组for(inti=0;istudent_num;i+)if(sumi!=temp_score)temp_score=sumi;rank+;coutsumitranktsii.IDtsii.nametsii.ss.chinesetsii.ss.mathtsii.ss.englishtsiindex.ID;infilesiindex.name;infilesiindex.ss.ch

22、inese;infilesiindex.ss.math;infilesiindex.ss.english;index+;sort(si,index);/排序展示return0;n 综合性实验4.调试分析1) 采用IDE中自带的调试功能进行调试，手动添加断点和查看程序。2) 对设计和编码的讨论和分析。该程序实现了顺序栈的操作。分析程序代码的质量，主要从以下几个方面考虑。 正确性。在一定的数据范围内，该程序能实现所需功能，所以正确性是没有问题的。 健壮性。在一定的数据输入范围内，该程序能较好的实现操作。但是如果输入数 据非法，该程序还是可能会产生一些预想不到的输出结构，或是不做任何处理。所以， 该程序的健壮性有待进一步的提高。要综合考虑一些情况，当输入有误时，应返回一个 表示错误的值，并中止程序的执行，以便在更高的抽象层次上进行处理。5.使用说明按照屏幕提示，选择想要的功能并输入对应数字，按下ENTER键后，根据屏幕提示进行输入，即可得到想要的结果。6.测试程序运行结果n 设计性实验n 综合性实验7. 心得体会通过本次实验，使我对数据结构有了更深的理解，对指针的运用更加熟练，熟悉了对函数的定义和操作。专心-专注-专业