数据结构 | 每日一练（49）

1

每日一

1．已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负

数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。

类似本题的另外叙述有：

（1）设有一元素为整数的线性表 L=(a 1 ,a 2 ,a3,…,a n ),存放在一维数组 A[N]中,设计一个算法,以表中 a n 作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于 a n ,右半部分每个元素都大于 a n , a n位于分界位置上(要求结果仍存放在 A[N]中)。

（2）顺序存储的线性表 A,其数据元素为整型,试编写一算法,将 A 拆成 B 和 C 两个表,使 A 中元素值大于等于 0 的元素放入 B,小于 0 的放入 C 中.. 要求:

1）表 B 和 C 另外设置存储空间;

2）表 B 和 C 不另外设置,而利用 A 的空间.

（3）知线性表（a1, a2,a3,…,an）按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法。（要求时间最少，辅助空间最少）

(4) 编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为 O（n）

(5) 已知一个由 n （ 设 n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准 pascal语言描述算法，实现将 n 个元素中所有大于等于 19 的整数放在所有小于 19 的整数之后。要求算法的时间复杂度为 O(n),空间复杂度 O(1)。

正确答案

ps：||代表注释

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

int Rearrange（SeqList a; int n)∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a，

∥使所有值为负数的元素移到所有值为正数的数的前面。

{i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。

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

while(i<j)

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

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

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

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

}

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

}

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

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

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

i=1;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; ∥参考元素置于分界位置。

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

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

∥等于零的元素，C中存放小于零的元素。

{i=0; ∥i，j，k是工作指针，分别指向A、B和C表的当前元素。

j=k=-1; ∥j，k初始化为-1。

while(i<n)

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

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

[算法讨论]本题用一维数组存储线性表，结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表，则元素的表示作相应改变，例如A.elem[i]，而最后B和C表应置上表的长度，如B.length=j和C.length=k。

(3) 本题与第8题本质上相同，第8题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是

a[i]%2==0，满足时为偶数，反之为奇数。

(4) 本题与第8题相同，只是叙述不同。

(5) 本题与第8题基本相同，不同之处在于这里的分界元素是整数19（链表中并不要求一定有19）。本题要求用标准pascal描述算法，如下所示。

TYPE arr= ARRAY[1..1000] OF integer；

VAR a：arr；

PROCEDURE Rearrange5（VAR a：arr）；

∥a是n（设n=1000）个整数组成的线性表，用一维数组存储。本算法将n个元素中所有大于等于19的整数放在所有小于19的整数之后。

VAR i,j,t：integer；

BEGIN

i:=1；j:=n；t:=a[1] ；∥i,j指示顺序表的首尾元素的下标，t暂存分界元素

WHILE（i<j） DO

BEGIN

WHILE （i<j） AND（a[j]>=19） DO j:=j-1；

IF（i<j） THEN BEGIN A[i]:=A[j]；i:=i+1 END；

WHILE （i<j） AND（a[i] <19） DO i:=i+1；

IF（i<j） THEN BEGIN A[j]:=A[i]；j:=j-1 END；

END；

a[i]:=t；

END;

[算法讨论] 分界元素t放入a[i]，而不论它的值如何。算法中只用了一个t中间变量，符合空间复杂度O(1)的要求。算法也满足时间复杂度O(n)的要求。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-