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

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

思想:
记录等于X的值的个数i,遇到不是X的位置就把值放到前面i个位置上

代码展示:

#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#define InitSize 100
#define addsize 10


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


typedef struct{
    ElemType *data;
    int Length,MaxSize;
}SqList;
void InitList(SqList &L){//构造一个空的线性表L
    L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
    L.Length=0;
    L.MaxSize=InitSize;
}
int Length(SqList L){//返回线性表L的长度
    return L.Length;
}
int LocateElem(SqList L,ElemType e){//返回线性表L中值为e的位置
    for(int i=0;i<L.Length;i++){
        if(e==L.data[i]){
            return i+1;//位置比下标多1
        }
    }
    return -1;//没找到返回-1
}
int GetElem(SqList L,int i){//返回线性表L中第i位的值
    if(i<1||i>L.Length) {
        printf("位置不合理!\n");
    }
    return L.data[i-1];
}
int ListInsert(SqList &L,int i,ElemType e){//在线性表L的第i个元素前插入新元素e
    if(i<1||i>L.Length+1) return 0;//位置不合理
    bool newbase=true;//用来判断分配空间是否成功
    if(L.Length>=L.MaxSize){//位置不够了,需要重新分配空间
        newbase=(ElemType*)realloc(L.data,(L.MaxSize+addsize)*sizeof(ElemType));
    }
    if(!newbase){//分配失败
        return 0;
    }
    int j;
    for(j=L.Length;j>=i;j--){
        L.data[j]=L.data[j-1];
    }
    L.data[j]=e;
    L.Length++;
}
int ListDelete(SqList &L,int i,ElemType &e){//删除表线性表L中第i个位置的元素,并用e返回删除元素的值
    if(i<1||i>L.Length) return -1;//位置不合理
    e=L.data[i-1];
    L.Length--;
}
void PrintList(SqList L){//输出线性表L中的所有元素值
    for(int i=0;i<L.Length;i++){
        printf("%d ",L.data[i]);
    }
    printf("\n");
}
int Empty(SqList &L){//判断L是否为空,若为空返回1否则返回0
    if(L.Length==0) return 1;
    else return 0;
}
int DestoryList(SqList &L){//销毁线性表L
    free(L.data);
}

int main()
{
    //创建顺序表并初始化,存入数据
    SqList L;
    InitList(L);
    int n;
    scanf("%d",&n);
    int data;
    for (int i = 0; i < n; ++i) {
        scanf("%d",&data);
        ListInsert(L,i+1,data);
    }

    //将值为X的元素全部删除
    int X;
    int e;
    scanf("%d",&X);
    int count = 0, i = 0;
    while(i<L.Length)
    {
        if(L.data[i]==X)
        {
            count++;
        }
        else
        {
            L.data[i-count] = L.data[i];
        }
        i++;
    }
    while(count>0)
    {
        ListDelete(L,L.Length,e);
        count--;
    }
    PrintList(L);
    return 0;
}
上一篇:顺序存储的线性表的基本操作


下一篇:基于c语言数据结构+严蔚敏——线性表章节源码,利用Codeblocks编译通过