[数据结构] 王道数据结构2023 P18_03

问题描述

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

实现代码

bool DeleteSelectX(SeqList &L,ElementType x){
    if(L.lenght == 0){
        printf("线性表为空\n");
        return false;
    }
    int i,j;
    for(i = 0,j = 0;i < L.lenght;i++){
        if(L.data[i] != x){
            L.data[j] = L.data[i];
            j++;
        }
    }
    L.lenght = j;
    return true;
}

全部代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define ElementType int
#define InitSize 100

int arr[] = {1,2,3,4,1,6,1,8,9,0};

typedef struct {
    ElementType *data;
    int MaxLen,lenght;
}SeqList;

void InitSeqList(SeqList &L){
    L.data = (ElementType *)malloc(sizeof(ElementType) * InitSize);
    L.MaxLen = InitSize;
    L.lenght = 0;
}

bool InsertELem(SeqList &L,int i,ElementType data){
    if(i < 1 || i > L.lenght + 1){
        printf("位置不合法\n");
        return false;
    }
    if(L.lenght + 1 > L.MaxLen){
        printf("线性表已满\n");
        return false;
    }
    for(int j = L.lenght;j >= i;j--){
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = data;
    L.lenght += 1;
    return true;
}



void ShowList(SeqList L){
    for(int i = 0;i < L.lenght;i++){
        printf("%d ", L.data[i]);
    }
    printf("\n");
}
bool DeleteSelectX(SeqList &L,ElementType x){
    if(L.lenght == 0){
        printf("线性表为空\n");
        return false;
    }
    int i,j;
    for(i = 0,j = 0;i < L.lenght;i++){
        if(L.data[i] != x){
            L.data[j] = L.data[i];
            j++;
        }
    }
    L.lenght = j;
    return true;
}
int main()
{
    SeqList L;
    InitSeqList(L);
    for(int i = 0;i < 10;i++){
        InsertELem(L,i + 1, arr[i]);
    }
    DeleteSelectX(L,1);
    ShowList(L);
    return 0;
}