数据结构考研分类复习真题 第二章 答案[27]

类似本题的选了 个题其解答如下

()与上面第题不同的是这里要求以an为参考元素将线性表分成左右两部分左半部分的元素都小于等于an右半部分的元素都大于anan位于分界位置上其算法主要片段语句如下:

i=;j=n;

t=a[n];∥暂存参考元素

while(i<j)

{while(i<j && a[i]<=t) i++;∥当前元素不大于参考元素时指针i后移

if(i<j) a[j]=a[i];∥将大于参考元素的元素后移

while(i<j && a[j]>t) j;∥当前元素大于参考元素时指针前移

if(i<j) a[i++]=a[j];∥将小于参考元素的当前元素前移

}

a[i]=t;∥参考元素置于分界位置

() [题目分析]本题要求将线性表A分成B和C两个表表B和表C不另占空间而是利用表A的空间其算法与第题相同这里仅把表B和表C另设空间的算法解答如下

void Rearrange(int A[]B[]C[])∥线性表A有n个整型元素顺序存储本算法将A拆成B和C 两个表B中存放大于等于零的元素C中存放小于零的元素

{i=;∥ijk是工作指针分别指向AB和C表的当前元素

j=k=;∥jk初始化为

while(i<n)

{if(A[i]<) C[++k]=A[i++];∥将小于零的元素放入C表

else B[++j]=A[i++];∥将大于零的元素放入B表

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []