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

．[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表使得所有值为负数的元素移到正数元素的前面这可采用快速排序的思想来实现只是提出暂存的第一个元素(枢轴)并不作为以后的比较标准比较的标准是元素是否为负数

int Rearrange(SeqList a; int n)∥a是具有n个元素的线性表以顺序存储结构存储线性表的元素是整数本算法重排线性表a使所有值为负数的元素移到所有值为正数的数的前面

{i=; j=n;∥ ij为工作指针(下标)初始指向线性表a的第个和第n个元素

t=a[];∥暂存枢轴元素

while(i<j)

{while(i<j && a[j]>=) j;∥ 若当前元素为大于等于零则指针前移

if(i<j){a[i]=a[j];i++;}∥ 将负数前移

while(i<j &&a[i]<)i++;∥ 当前元素为负数时指针后移

if(i<j) a[j]=a[i];∥ 正数后移

}

a[i]=t;∥将原第一元素放到最终位置

}

[算法讨论] 本算法时间复杂度为O(n)算法只是按题目要求把正负数分开如要求统计负数和大于等于零的个数则最后以t来定如t为负数则至i共i+个负数ni个正数(包括零)另外题目并未提及零的问题笔者将零放到正数一边对此问题的扩充是若元素包含正数负数和零并要求按负数零正数的顺序重排线性表统计负数零正数的个数请读者利用上面解题思想自行解答

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