已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (

admin2019-01-16  37

问题 已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。
    (1)给出算法的基本设计思想。
    (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
    (3)说明你所设计算法的时间复杂度和空间复杂度。

选项

答案(1)基本的设计思想:先将偶数号元素复制到一个辅助空间,然后整理数组剩下的奇数号元素,最后将辅助空间中的元素复制到数组的后半部分,但这种思路的空间复杂度为O(n)。 另一种思路: ①在数组尾部从后往前找到第一个奇数号元素,将此元素与其前面的偶数号元素交换。这样,就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。 ④如此继续,直到前一步的“块”前没有元素为止。 (2)算法的设计如下: void Swap(ElemType A[],int n){ int i=n,v=1; //i为工作指针,初始假设n为奇数,v为“块”的大小 ElemType temp: //辅助变量 if(n%2==0)i=n一1; //若n为偶数,则令i为n—1 while(i>1){ //假设数组从1开始存放。当i=1时,气泡浮出水面 temp=A[i一1]; //将“块”前的偶数号元素暂存 for(int j=0;j2)。虽然时间复杂度为O(n2),但因n2前的系数很小,实际达到的效率是很高的。算法的空间复杂度为O(1)。

解析
转载请注明原文地址:https://jikaoti.com/ti/bufjFFFM
0

最新回复(0)