C语言删除顺序表中所有值为x的元素

这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识，请查看：数据结构 -> 线性表

问题描述：

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

问题解答：

解法1)：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数)，边扫描 L边统计k，并将不等于x的元素向前放置k位置上，最后修改L的长度。

本题代码如下：

void del_x_1(Sqlist &L, Elemtype x){
    //本算法实现删除顺序表L中所有值为x的数据元素
    int k=0;  //记录值不等于x的元素个数

    for(i=0; i<L.length; i++)
        if(L.data[i] != x){
            L.data[k] = data[i];
            k++;  //不等于x的元素增1
        }

    L.length=k;  //顺序表L的长度等于k
}

解法2)：用k记录顺序表L中等于X的元素个数，边扫描L边统计k，并将不等于X的元素前移k个位置，最后修改L的长度。

本题代码如下：  

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=l, j=n)，从两端向中间移动，凡遇到最左端值X的元素时，直接将最右端值非X的元素左移至值为X的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。