顺序表的插入和删除 | 廖家龙的博客网站

顺序表的插入(最好O(1),最坏O(n),平均O(n))

//顺序表的插入

#include <stdio.h>
#include<stdbool.h> //可以使用bool了

#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

//基本操作：初始化一个顺序表
void InitList(SqList *L){
    for(int i=0;i<MaxSize;i++){
        L->data[i]=0;  //将所有数据元素设置为默认初始值
    }
    L->length=0;  //顺序表初始长度为0
}

//i的取值：[1,length+1]，因为顺序表是连续排列的
bool ListInsert(SqList *L,int i,int e){
    
    if(i<1 || i>L->length+1){  //判断i的范围是否有效
        return false;
    }
    if(L->length >= MaxSize){  //当前存储空间已满，不能插入
        return false;
    }
    
    for(int j=L->length;j>=i;j--){  //将第i个元素及之后的元素后移
        L->data[i]=L->data[j-1];
    }
    L->data[i-1]=e;  //在位置i处放入e
    L->length++;  //长度加1
    
    return true;
}

int main(){
    
    SqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    
    //...此处插入几个元素
    bool b=ListInsert(&L, 3, 4);  //在位置3处放入4
    return 0;
}

顺序表的删除(最好O(1),最坏O(n),平均O(n))

//顺序表的删除

#include <stdio.h>
#include<stdbool.h> //可以使用bool了

#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

//基本操作：初始化一个顺序表
void InitList(SqList *L){
    for(int i=0;i<MaxSize;i++){
        L->data[i]=0;  //将所有数据元素设置为默认初始值
    }
    L->length=0;  //顺序表初始长度为0
}

bool ListDelete(SqList *L,int i,int *e){
    
    if(i<1 || i>L->length){  //判断i的范围是否有效
        return false;
    }
    
    *e=L->data[i-1];  //将被删除的元素赋值给e
    
    for(int j=i;j<L->length;j++){  //将第i个位置后的元素前移
        L->data[j-1]=L->data[j];
    }
    L->length--;  //线性表长度减1
    
    return true;
}

int main(){
    
    SqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    
    //...此处插入几个元素
    int e=-1;  //用变量e把删除的元素“带回来”
    if(ListDelete(&L, 3, &e)){
        printf("已删除第3个元素，删除元素值为%d\n",e);
    }
    else{
        printf("位序i不合法，删除失败\n");
    }
    return 0;
}