欢迎来到天天文库
浏览记录
ID:47964675
大小:39.13 KB
页数:4页
时间:2020-01-18
《线性时间选择实验报告》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、线性时间选择一.实验目的:1.理解算法设计的基本步骤和各步的主要内容、基本要求;2.加深对递归设计方法基本思想的理解,并利用其解决现实生活中的问题;3.通过本次试验初步掌握将算法转化为计算机上机程序的方法。二.实验内容:1.编写实现算法:给定n个元素,在这n个元素中找到第key小的元素;2.将输入的数据存储到指定的文本文件中,而输出数据存放到另一个文本文件中,包括结果和具体的运行时间;3.对实验结果进行分析。三.实验操作:1.线性时间选择的思想:首先将这n个元素分成5组,利用排序算法找到其中的中位数,再将这些中位数排序找到整个数组的中位数median,以这个中
2、位数median为界限,将整个数组划分为三部分,小于median,等于median和大于median三部分,判断key在哪部分中,对那部分进行递归调用,直到找到等于key的元素为止。综上判断,其时间复杂度为:T(n)<=cn(n为实验数据的个数),故为线性时间。2.快速排序:本次排序使用的是快速排序,快速排序是一种相对较快的排序方式,能够减少一定的时间开销。代码实现:voidquickSort(intList[],intlow,inthigh){if(low>=high)return;intfirst=low;intlast=high;intkey=List[
3、first];while(first=key)--last;List[first]=List[last];while(first4、文本文件中,需要采用C++文件流操作,对于数据的输入,由于cin对数据的读取会忽略空格和换行操作,故使用cin流来控制数据的输入。35、4输入代码实现:intwrite(){ofstreamoutFile;outFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt",ios::trunc);if(!outFile.is_open())cout<<"outFilecan'topen!"<6、>start>>end;cout<<"输入要查找的数据个数:"<>length;len=length;int*Array=newint[length];for(inti=0;i7、ay[i]<<"";outFile.close();returnlength;}输出代码实现:int*read(intlength){ifstreaminFile;inFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt");if(!inFile.is_open())cout<<"inFilecan'topen!"<>Array[i++];returnArr8、ay;inFile.close();}4.查找中位数:首先将所有的数据分成五组,找到每组中的中位数,再从找到的中位数中找到整个数组的中位数median,利用median将所有的数分成3份,小于median、等于median和大于median三部分,判断所要找的元素在哪部分中,再将哪部分数据作为整体执行上39、4述操作,直到数组不能再分为止。代码实现:intgrouping(intArray[],intlength,intkey){inti=0,start=0,group,m=0,n=0;group=length/5;if(group==0){quickSort(10、Array,0,length-1);r
4、文本文件中,需要采用C++文件流操作,对于数据的输入,由于cin对数据的读取会忽略空格和换行操作,故使用cin流来控制数据的输入。3
5、4输入代码实现:intwrite(){ofstreamoutFile;outFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt",ios::trunc);if(!outFile.is_open())cout<<"outFilecan'topen!"<
6、>start>>end;cout<<"输入要查找的数据个数:"<>length;len=length;int*Array=newint[length];for(inti=0;i7、ay[i]<<"";outFile.close();returnlength;}输出代码实现:int*read(intlength){ifstreaminFile;inFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt");if(!inFile.is_open())cout<<"inFilecan'topen!"<>Array[i++];returnArr8、ay;inFile.close();}4.查找中位数:首先将所有的数据分成五组,找到每组中的中位数,再从找到的中位数中找到整个数组的中位数median,利用median将所有的数分成3份,小于median、等于median和大于median三部分,判断所要找的元素在哪部分中,再将哪部分数据作为整体执行上39、4述操作,直到数组不能再分为止。代码实现:intgrouping(intArray[],intlength,intkey){inti=0,start=0,group,m=0,n=0;group=length/5;if(group==0){quickSort(10、Array,0,length-1);r
7、ay[i]<<"";outFile.close();returnlength;}输出代码实现:int*read(intlength){ifstreaminFile;inFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt");if(!inFile.is_open())cout<<"inFilecan'topen!"<>Array[i++];returnArr
8、ay;inFile.close();}4.查找中位数:首先将所有的数据分成五组,找到每组中的中位数,再从找到的中位数中找到整个数组的中位数median,利用median将所有的数分成3份,小于median、等于median和大于median三部分,判断所要找的元素在哪部分中,再将哪部分数据作为整体执行上3
9、4述操作,直到数组不能再分为止。代码实现:intgrouping(intArray[],intlength,intkey){inti=0,start=0,group,m=0,n=0;group=length/5;if(group==0){quickSort(
10、Array,0,length-1);r
此文档下载收益归作者所有