(05)王道数据结构-顺序表的插入与删除

插入操作：

#define MaxSize 10  //定义最大长度
typedef struct {
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义
//基本操作-初始化顺序表
void InitList(SqList &L);
//基本操作-插入元素
bool ListInsert(SqList &L, int i, int e);
int main(void) {
    SqList L;     //声明一个顺序表
    InitList(L);  //初始化顺序表

    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    return 0;
}

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;   //将所有数据元素设置为默认初始值
    }                   //顺序表初始长度为0
    L.length = 0;
}

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[j] = L.data[j-1];
    }       
    L.data[i-1] = e;        //在位置i处放入e
    L.length++;             //长度加1
    return true;
}

时间复杂度

最好情况：新元素插入到表尾，不需要移动元素，其中i = n + 1时循环0次，最好时间复杂度为 O(1)

最坏情况：新元素插入到表头，需要将原有的n个元素全部都向后移动，其中i = 1，循环n次，最坏时间复杂度O(n)

平均情况：假设新元素插入任何一个位置的概率相同，即i = 1, 2,3, …, length+1的概率都是 $$ p = \frac{1}{n+1} $$ i = 1, 循环n次；i = 2时，循环n-1次；i=3，循环n-2次…i = n + 1时循环0次 $$ 平均循环次数平均循环次数 = np + (n-1)p + (n-2)p + … + 1p=\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2} $$

删除操作：

#define MaxSize 10  //定义最大长度
typedef struct {
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义
//基本操作-初始化顺序表
void InitList(SqList &L);
//基本操作-插入元素
bool ListInsert(SqList &L, int i, int e);
bool ListDelete(SqList &L, )
int main(void) {
    SqList L;     //声明一个顺序表
    InitList(L);  //初始化顺序表

    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    return 0;
}

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;   //将所有数据元素设置为默认初始值
    }                   //顺序表初始长度为0
    L.length = 0;
}

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[j] = L.data[j-1];
    }       
    L.data[i-1] = e;        //在位置i处放入e
    L.length++;             //长度加1
    return true;
}