实验二查找kk问题实验报告 .docVIP

实验二：用分治法查找k1-k2问题 实验内容 从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1=k2。分析时间复杂度。必须用分治法求解，但是不能简单地重复使用求第k小元素的分治法。禁止使用排序算法求解给出复杂度分析过程 算法思想 在解决实验的过程中参考了快速排序中双向扫描的思想。快速排序是一种基于分治技术的重要排序算法。首先选择一个元素，接下来根据该元素的值来划分数组。中轴之前的是小于中轴的数，之后的为大于中轴的数。在这个问题中我们只需要在找到中轴位K1和K2时跳出快排，输出第K1到K2的元素，便得问题的解。在寻找中轴的过程中如果遇到k2则不需要二次快排，否则再次查找中轴为k2。 数据结构：顺序表 算法1 Quicksort(Sqlist L,int low,int high,int k1,int k2,int temp) //用Quicksort对子数组排序 //快排到中轴为k1返回 //输出：k1将数组分为k1前和k1后两部分 if(lowhigh)//长度大于1 { s=Partition(L,low,high);//分区过程 if(sk1)//如果k1小于中轴，对low到s-1部分快排 { if(s==k2) temp=1;//中轴为k2记录temp为真 Quicksort(L,low,s-1,k1,k2,temp); } else if(sk1)//如果k1大于中轴，对s到high部分快排 { Quicksort(L,s+1,high,k1,k2,temp); } else if(s=k1)//如果k1等于于中轴跳出递归将数组分为大于k1和小于k2两部分 { return ; } Partition(Sqlist L,int low,int high) //以L.elem[0]为限位器，以第一个元素为中轴， //输入：顺序表的子顺序表L.elem[low-high] //输出：顺序表的一个分区，分裂点的位置作为函数的返回值 while(lowhigh) { while(lowhigh L.elem[high]=pivotkey)// 从表的两端交替地向中间扫描 --high; L.elem[low]=L.elem[high];//将比中轴小的记录交替到低端 while(lowhigh L.elem[low]=pivotkey) ++low; L.elem[high]=L.elem[low];//将比中轴大的记录交替到高端 } L.elem[low]=L.elem[0];//中轴记录到位 return low; 实验过程 源程序 //**************************************************************************** //****从包含n个整数的无序列表中输出第K1小道第k2小之间的所有整数，其中******** //********k1=k2,分析时间复杂度，在这里采用快排的思想分别找出中轴为k1 和k2*** //*********时输出k1和k2之间的数，便为所需************************************* //***************************************************************************88 #includeiostream using namespace std; //***************结构体********** struct Sqlist { int *elem;//元素指针 int length;//长度 int listsize;// }; //************构造一个空的线性顺序表************ void InitList_Sq(Sqlist L) { L.elem=(int *)malloc(100*sizeof(int));//开辟空间 L.length=0; L.listsize=100;//初始化 } //***********快排的分区过程****************** int Partition(Sqlist L,int low,int high) { int pivotkey; L.elem[0]=L.elem[low];//以L.elem[0]为限位器 pivotkey=L.elem[low];//以第一个元素为中轴 while(lowhigh)//从表的两端交替地向中间扫描 { while(lo