数据结构 | 每日一练(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-

原文发布于微信公众号 - C语言入门到精通(yclzl960229)

原文发表时间:2019-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券