长度为n的顺序表L,删除线性表中所有值为X的算法

长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为X的数据元素。

要求时间复杂度为O(n)，这里隐藏着条件，排序算法不能使用，因为排序中最低时间复杂度为O(nlogn),这是大于题目中所给的要求为O(n)的条件。因此，我们要把排序算法排除在外，转而采用其它的方法。

删除顺序表中值为X的算法一

下面，博主画了一个线性表，用其举例。在线性表中有2值为X的字母。其实对于线性表来说就是个数组。

题目中所给的长度为n的顺序表L，按照书上关于顺序表的定义，L.data就是数据的部分，L.length就是数组的长度，这两部分是一个结构体，共同构成了题目中的顺序表L。

现在，我们要在顺序表中删除值为X的元素，既然说为O(n)。可以采用遍历的方法。从数组头到尾一次遍历，并且设置两个变量分别为i和k。i表示实际的元素，其把所有的元素都能遍历到的；而k表示要留下的元素。
下面，就看看具体的代码实现。

void del_x_l(Sqlist &L,Elemtype x) {
	int k = 0; // 记录值不等于x的元素的个数，就是要留下的元素。
	for (i=0;i<L.length;i++)
		if(L.data[i] !=x) {
			L.data[k] = L.data[i]; // 下标对的元素值不等于x值就留下
			k++;// 不等于x的元素自增1
		}
		L.length = k;//顺序表长度L等于k
}

从代码中可以看出，经过前两轮的循环后，3和1都留已经留在的数组中。那么，接下来到了第三个位置k=2;i=2。可以发现X不满足if语句，就不会进入循环体中。因此，第三次的for循环，只会执行i++；而k不动，留在原先位置。至于i来到3位置，自然X元素就没有存入，相当于把X删掉了。

接下来i=3，k=2；发现第4个位置的元素不等于X，就可以进入到for循环中。这时data[2]=data[3],进而把原先k空下来的位置填补上2元素。在遍历的过程中k<=i,因为k是最终留下的元素个数，i是要遍历整个数组的元素。若数组中没有X，k和i会同步自增1，这时k=i.若数组中有X，k<i;因此，按照这样的流程遍历完，就会把值为X的元素删除，从做到让这些不等于X的元素往前紧凑填充。

最后让L.length=k。循序表的长度也就为k了。

最终删除x后的效果图：

删除顺序表中值为X的算法二

对于一个data!=x的元素而言，它需要前移的位数取决于在它之前有多少为满足data==x。

譬如，对于图中的数组而言，若删除第一个x，后面的2与3分别向左移动一位，若删除第二个X时，4要向左移动2位，相当前面删除了两个X。

因此，对于一个不等于X的元素向左移动多少为，取决于其左面有多少个要删除的X。假设用k记录X的个数，用i遍历第i位要留下的元素。留下的元素本来在第i位，删除X后，向左移动data[i-k]=data[i]位置，就是把留下的元素左移k位。

具体代码如下：

void del_x_2(Sqlist &L,Elemtype x) {
	int k = 0,i =0;  // k记录值等于x的元素。
	wihle (i<L.length)
		{
		if(L.data[i] ==x) 
			k++;
			else
			L.data[i-k] = L.data[i]; // 当前元素前移k个位置
			i++;
		}
		L.length -= k;//顺序表长度L递减
}