Question

顺序栈要求空间复杂度和时间复杂度均为O(n).

我的电脑 2017/10/22 14:50:58设顺序栈S中有2n个元素,从栈顶到栈底的元素依次是 a2n,a2n-1,...,a2,a1,要求通过一个辅助的循环队列及相应的入栈,出栈,入队,出队操作来重新排列栈中元素,使得从栈顶到栈底的元素依次为a2n,a2n-2,...,a2,a2n-1,a2n-3,...,a1,请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n).

Answer 1

首先确定顺序表L中的第一个值为x的元素位置i，然后依次检查L.data[i+1]~L.data[L.length-1]中每个元素L.data[j](i+1<=j<L.length)，若L.data[j]!=x,则将L.data[j]存入L.data[i]中，并令i增1。最后顺序表长度为i。算法如下：

[cpp] view plain copy
void delall(Sqlist *l,int x)
{
int i=0,j;
while(i<l->length && l->data[i]!=x)
i++;
for(j=i+1;j<l->length;j++)
if(l->data[j]!=x)
{
l->data[i++]=l->data[j];
}
l->length=i;
}
本算法只扫描一次顺序表，即将值为x的元素前移一次，其时间复杂度为O(n)

解法二：
从头开始扫描顺序表L，用k记录下元素值等于x的元素个数，对于不等于x的元素，前移k个位置，这种算法复杂度为O(n)，其中n为顺序表的长度，算法如下：

[cpp] view plain copy
void delall(Sqlist *l,int x)
{
int i=0,j=0;
while(i<l->length)
{
if(l->data[i]==x)
j++;//j记录被删记录的个数
else
l->data[i-j]=l->data[i];//前移j个位置
i++;
}
l->length-=j;
}

追问

请问这两个效果请问是等价的嘛？答案直接写代码对不对?