引入

前面，我们知道了如何分装一个线性表顺序存储的结构，也知道了如何使用索引地址转下标法得到某个索引对应的值，今天，我们来看看如何在线性表中插入一个元素。

思考如何插入元素

我们说过，线性表的顺序存储结构具有随机存储结构的特点，时间复杂度位 O (1) 。
输入：

线性表指针
要插入的位置
要插入的数值

判断

插入位置是否合理，不合理报错
线性表长度大于等于数组长度，报错，或者动态增加数组容量。

计算

从最后一个元素开始，遍历到第 i 个位置，将遍历的元素都向后移一位。
将要插入的元素填入 i 处
线性表的长度+1

在线性表中插入元素

#define ERROR 0
#define OK 1
#define MAXSIZE 2
typedef int Elemtype;
typedef struct {
int length;
Elemtype data[MAXSIZE];
}Sqlist;
status insertElem(Sqlist *L , int i , Elemtype e){
if(L.length==MAXSIZE || i > L.length+1 || i<1){
//线性表没有满、i 的位置在length 的表尾或者 length 之中。
return ERROR;
}
if(i <= L.length){
for(int k=L.length-1;k>i-1;k--){
L.data[k+1]=L.data[k];
}
// 将 i 之后的所有元素向后移动一位
}
L.data[i-1]=e;
L.length++;
return OK;
}

需要注意的就是判断 i 是否合法，判断 i 是否在表尾，不在表尾，就将 i 之后的所有元素向后移。

思考如何让删除元素

其实删除元素就分两步

找到该元素，删除
把后面的元素逐个顺移

输入

删除的线性表
删除的位置

判断

删除位置是否合理

计算

取出删除元素
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。
表长-1

删除元素

#define ERROR 0
#define OK 1
#define MAXSIZE 20
typedef int Elemtype;
typedef struct{
int length;
Elemtype data[MAXSIZE];
}SqList;
status DeleteElem(SqList *L , int i , Elemtype *e){
if(L.length==0 || i>L.length || i>1){
return ERROR;
}
if(i<L.length){
for(int k=i;k<=L.length;k++){
L.data[k-1]=L.data[k];
// k-1 表示的是 k 索引的数据
// k 表示的 k 索引后面一个的数据
}
}
*e=L.data[i-1];
L.data[L.length]=0;
L.length--;
return OK;
}

时间复杂度

插入和删除的时间复杂度

最好情况：插入和删除的操作刚好要求在最后一位，不需要移动任何元素，不用进循环，所以时间复杂度位 O ( 1 ) 。
最坏情况：插入和删除的操作刚好要求在第一位，要移动所有的元素，所以时间复杂度位 O ( n ) 。
平均情况：最坏的情况-最好的情况 / 2，也就是O((n-1)\2)，简化后还是 O(n)。因为加减常数不要、乘以二分之一也不要，只留 n。

线性表顺序存储结构的特性

存储、读取数据：时间复杂度都是 O ( 1 ) ;
插入、删除数据：时间复杂度都是 O ( n ) ；

所以，这就表示，线性表适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数数据的应用。

线性表顺序存储结构的优缺点

根据我们的使用以及上面的特性，我们总结了一下线性表顺序存储结构的优缺点：
优点：

无需为表示表中元素之间的逻辑关系而增加额外的存储空间。（这个有下标，数据顺序存储，但链表就不同了，要记录下一个数据的指针地址）
可以快速的存取表中的任意元素（因为有连续的下标，指哪个来哪个）

缺点：

插入和删除的时候要移动大量的元素
线性表的长度变化较大时，难以确定存储空间的容量（因为线性表要规定一个 MAXSIZE 的）
容易造成存储空间的碎片

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。