数据结构经典算法题2-CSDN博客

本文链接：https://blog.csdn.net/Protinx/article/details/136847434

本文提供了两种方法实现删除顺序表中所有值为x的数据元素的算法，一种是用K记录不等于x的元素个数，另一种是统计等于x的元素个数并前移非x元素。两种方法的时间复杂度均为O(n)，空间复杂度为O(1)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

温馨提醒：后期更新将发布在超翔之逸微信公众号里哦！

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

算法思想1：用K记录顺序表L中不等于x的元素个数(即需要保存的元素个数)，扫描时将不等于x的元素移动到下标左的位置，并更新K值。扫描结束后修改L的长度

实现代码：

void del_x_1(Sqlist &L,ElemType x) {    int k=0,i;//记录值不等于x的元素个数    for(i=0;i<L.lenght();i++)        if(L.data[i]!=x){            L.data[k]=L.data[i];            k++;//不等于x的元素增1    }    L.length=k;//顺序表L的长度等于k}

另解：用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的长度递减}