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

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

admin2019-08-01  32
问题 已知顺序表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；j＜v；j++) ／／将大小为v的“块”整体向前平移 A[i一1+j]=A[i+j] ／／从前往后依次向前平移 A[i+v一1]=temp： ／／暂存的奇数号元素复制到平移后空出的位置 i一一；v++； ／／指针向前，块大小增1 }／／while } (3)一共进行了n／2次交换，每次交换的元素个数从1一n／2，因此时间复杂度为O(n2)。虽然时间复杂度为O(n2)，但因n2前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/jACi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)