删除特定元素--顺序表

问题：
         假设一个线性表采用顺序表表示。设计一个程序，删除其中所有值为x的元素。
         要求算法的时间复杂度为(n),空间复杂度为O(1)。

样例：

输入：5 1 2 3 2 5 2

输出：1 3 5

方法一：

扫描表L,重建只包含不等于x的元素的表。用k记录不等于x的元素的个数；若当前元素不为x，则将其插入L中,k++。

#include<bits/stdc++.h>
const int MaxSize=100;
using namespace std;
typedef int ElemType;
typedef struct
{ElemType data[MaxSize];int length;
}SqList;void CreateList(SqList *&L,ElemType a[],int n)
{int i;L=(SqList *)malloc(sizeof(SqList));for(i=0;i<n;i++)L->data[i]=a[i];L->length=n;
}void delnode(SqList *&L,ElemType x)
{int k=0,i;for(i=0; i<L->length; i++)if(L->data[i]!=x)L->data[k++]=L->data[i];L->length=k;
}void DispList(SqList *&L)
{int i;for(i=0;i<L->length;i++)cout << L->data[i] << " ";cout << endl;
}int main()
{SqList *L;int n;cin >> n;ElemType a[n],x;for(int i=0;i<n;i++)cin >> a[i];cin >> x;CreateList(L,a,n);delnode(L,x);DispList(L);return 0;
}

方法二：

扫描表L,重建只包含不等于x的元素。用k记录不等于x的元素的个数；当前元素等于x时k增1；若元素不为x时将其前移k个位置。

#include<bits/stdc++.h>
const int MaxSize=100;
using namespace std;
typedef int ElemType;
typedef struct
{ElemType data[MaxSize];int length;
}SqList;void CreateList(SqList *&L,ElemType a[],int n)
{int i;L=(SqList *)malloc(sizeof(SqList));for(i=0;i<n;i++)L->data[i]=a[i];L->length=n;
}void delnode(SqList *&L,ElemType x)
{int k=0,i;for(i=0; i<L->length; i++){if(L->data[i]==x)k++;elseL->data[i-k]=L->data[i];}L->length-=k;
}void DispList(SqList *&L)
{int i;for(i=0;i<L->length;i++)cout << L->data[i] << " ";cout << endl;
}int main()
{SqList *L;int n;cin >> n;ElemType a[n],x;for(int i=0;i<n;i++)cin >> a[i];cin >> x;CreateList(L,a,n);delnode(L,x);DispList(L);return 0;
}

总结：

方法一和二的本质是相同的，只是在实现时表达不同。