问题描述

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

算法思想1">算法思想1

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

算法描述">算法描述

void DelX(SqList *L, ElemType e)
{
    int k=0, i;
    for(i=0;i<L->length;i++){
        if(L->data[i]!=e){
            L->data[k++]=L->data[i];
        }
    }
    L->length=k;
}

具体代码见附件1

---

算法思想2">算法思想2

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

算法描述-1">算法描述

void DelX(SqList *L, ElemType e)
{
    int k=0, i=0;
    while(i<L->length){
        if(L->data[i]==e){
            k++;
        }else{
            L->data[i-k]=L->data[i];
        }
        i++;
    }
    L->length=L->length-k;
}

具体代码见附件2

---

附件1

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

int DelX(SqList *, ElemType);
void print(SqList *);

int main(int argc, char* argv[])
{
    SqList SL;
    SL.length=10;
    for(int i=0;i<SL.length;i++){
        SL.data[i]=2*i+1;
    }
    ElemType e=5;

    int flag;
    print(&SL);
    flag=DelX(&SL, e);
    print(&SL);


    if(flag==0){
        printf("Delete Success!\n");
    }else{
        printf("Find not the number!\n");
    }

    return 0;
}

int DelX(SqList *L, ElemType e)
{
    int k=0, i;
    for(i=0;i<L->length;i++){
        if(L->data[i]!=e){
            L->data[k++]=L->data[i];
        }
    }
    if(L->length==k){
        return -1;
    }else{
        L->length=k;
        return 0;
    }
}

void print(SqList *L)
{
    for(int i=0;i<L->length;i++){
        printf("%d\t",L->data[i]);
    }
    printf("\n");
}

---

附件2

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;
void DelX(SqList *, ElemType);
void Print(SqList *);
int main(int argc, char* argv[])
{
    SqList SL;
    SL.length=10;
    for(int i=0;i<SL.length;i++){
        SL.data[i]=2*i+1;
    }
    ElemType e=5;
    Print(&SL);
    DelX(&SL, e);
    Print(&SL);
    return 0;
}
void DelX(SqList *L, ElemType e)
{
    int k=0, i=0;
    while(i<L->length){
        if(L->data[i]==e){
            k++;
        }else{
            L->data[i-k]=L->data[i];
        }
        i++;
    }
    L->length=L->length-k;
}
void Print(SqList *L)
{
    for(int i=0;i<L->length;i++){
        printf("%d\t",L->data[i]);
    }
    printf("\n");
}