【例2-2-14】④设计一个高效算法,从顺序表中删除所有元素值为x的元素,要求空间复杂度为O(1)。

解法1:用i从头开始遍历顺序表L,k置初始0。若L.data[i]不等于x,则将其存放在L.data[k]中,k增1;若L.data[i]等于x,则跳过继续判断下一个元素。最后顺序表长度置为k。对应算法如下。void delall1(SqList &L,ElemType x) int i,k=0//k记录L中不为x的元素个数,初值为Cfor (i=0;iL.length;i++)if (L.data(i]!=x){ L.data[k]=L.data[i];k++L. length=k;/表长置为k上述算法的思路是通过遍历L来新建一个顺序表,只是新顺序表共享原顺序表L的空间。解法2:用i从头开始遍历顺序表L,用k记录下元素值等于x的元素个数,其初值置为0。若L.data[i]不等于x，则将其前移k个位置，即存放在L.data[i-k]中;若L.data[i]等于x，则k增1。对应算法如下。void delal12(SqList &L, ElemType x) int i=C,k=0/k记录1中为x的元素个数,初值为0while (iL.length) if (L.data[i]==x)k++//k增1elseL.data[i-k]*L.data[i];/将不为x的元素前移k个位置i++}L. 1ength-=k//表长减少k这两个算法都只遍历顺序表一次,其时间复杂度为O(n),空间复杂度为O(1)。本题还有多种解法,读者也可以在算法中另设一个顺序表L1,将L中不为x的元素放L1,最后将L1复制回L中,算法如下。void delal13(SqList &L, ElemType x)( SqList L1//临时建立的顺序表L1int i,k=0/k记录L中不为x的元素个数,初值为0for (i=0;iL.length;i++)if (L.data[i]!=x) LI.data[k]=L.data[i]k++}L1.length-k//表长置为kfor (i=C;iL1. length;i++)//将L1复制到L中L.data[i]=L1.data[i]L.length=L1.length本算法的时间复杂度为O(n),但空间复杂度为O(n),显然不如前两种算法好。