线性表03

03.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
解法1：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），扫描时将不等于x的元素移动到下表k的位置，并更新k值。扫描结束后修改L的长度。
该解法的代码如下：

//线性表03_1
void del_x_1(SqList &L,ElemType x)
{
	//本算法实现删除顺序表L中所有值为x的数据元素 
	int k=0,i;//记录值不等于x的元素个数 
	for(i=0;i<L.length;i++)
	{
		if(L.data[i]!=x)
		{
			L.data[k]=L.data[i];
			k++;//不等于x的元素增1 
		}
	}
	L.length=k;//顺序表L的长度等于k 
} 

解法2：用k记录顺序表L中等于x的元素个数，边扫描边统计k，并将不等于x的元素前移k个位置。扫描结束后修改L的长度。
该解法的代码如下：

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

此外，本题还可以考虑设头、尾两个指针（ i =1, j = n )，从两端向中间移动，在遇到最左端值 x 的元素时，直接将最右端值非 x 的元素左移至值为 x 的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。