数据结构—顺序表—删除某个元素

爱被打了一巴掌 2022-08-21 13:41 190阅读 0赞

/*
    假设一个线性表采用顺序表表示。设计一个程序，删除其中所有值为x的元素。
    要求算法的时间复杂度为(n),空间复杂度为O(1)。
    */
    #include <iostream>
    #include <string.h>
    #include <malloc.h>
    #define MaxSize 100
    using namespace std;
    typedef int ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int length;
    } SqList;
    //扫描表L.重建只包含不等于x的元素。用k记录不等于x的元素的个数；若当前元素不为x，则将其插入L中,k++。
    void delnode1(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];
                k++;
            }
        L->length=k;
    }
    //扫描表L.重建只包含不等于x的元素。用k记录不等于x的元素的个数；当前元素等于x时k增1；若元素不为x时将其前移k个位置。
    void delnode2(SqList *&L,ElemType x)
    {
        int k=0,i;
        for(i=0; i<L->length; i++)
        {
            if(L->data[i]==x)
                k++;
            else
                L->data[i-k]=L->data[i];
        }
        L->length-=k;
    }
    int main()
    {
        SqList *L;
        int a[10]= {0,1,2,3,5,4,1,5,1,9};
        L=(SqList *)malloc(sizeof(SqList));
        for(int i=0; i<10; i++)
            L->data[i]=a[i];
        L->length=10;
        cout<<"删除1后：";
        delnode1(L,1);
        for(int i=0; i<L->length; i++)
            cout<<L->data[i]<<" ";
        cout<<endl;
        cout<<"删除5后：";
        delnode2(L,5);
        for(int i=0; i<L->length; i++)
            cout<<L->data[i]<<" ";
        cout<<endl;
        return 0;
    
    }

运行结果：

![Center][]

[Center]: /images/20220724/c8f5df6762b0438a8e2edc57abd42bb7.png