这是我参与8月更文挑战的第29天，活动详情查看：8月更文挑战

考研算法必会

l．本章重点：

本章主要考查线性表的顺序存储和链式存储。

2．复习提示：

近十年的计算机统考真题在本章的考查知识点为顺序表和链表的操作算法题，并且以大题为主， 所以我们平时应当掌握两种基本操作并且务必亲自动手多写、 多学、多记代码， 掌握算法思想， 尤其是注重时间复杂度和空间复杂度要求及对应的—般解法。

1. 顺序表的插入元素操作

在顺序表L第i (1≤i≤n 个元素之前插入—个新的数据元素， 使顺序表L的长度从n变为n+1

1. 如果插入位置不合理，结束程序，输出异常信息
2. 如果线性表长度大于或者等于数组长度，结束程序，输出异常信息
3. 从顺序表的最后一个元素开始向前遍历到第 i 个位置，依次将其向后移动一个位置。
4. 将元素插入指定位置 i 处
5. 表长增加1

下面在第三个存储位置插入元素作为例子，其中 new 为要插入的新元素。

顺序表的插入元素操作代码实现

//初始条件：顺序线性表 L已存在，1 ≤ i ≤ ListLength(L）
//操作结果：在 L中第i个位置之前插入新的数据元素 e，L的长度加 1
int ListInsert(SeqList *L,int i,ElemType *e){
    int k；
    if(L->length==MAXSIZE)/*顺序线性表已经满*/
        return ERROR;
 if（i<1 || i>L->length+1)/*当 i不在范围内时*/return ERROR; 
    if(i<=L->1ength){/*若插入数据位置不在表尾*/ 
        for(k=L->length-1；k>=i-1；k--)/*将要插入位置后的数据元素向后移动 一位*/
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;/*将新元素插入*/
    L->length++;
    return OK;
}

复制代码

代码分析：

平均情况:
插入到中间某个位置的元素（表中），此时移动：接近一半的元素时间复杂度：O((N/2) =O(N)

2. 顺序表的删除元素操作

不难发现， 与插入操作相反， 删除操作需要将后面的元素（如果有的话）依次往前移动—个单位， 因此其时间复杂度在于移动的次数！

首先整理算法思路：

1. 如果删除的元素位置不正确，结束程序，输出异常信息
2. 取出删除元素，放在元素 e 中
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
4. 表长减去1

顺序表的删除元素操作代码实现

//初始条件：顺序线性表 L已存在，1 ≤ i ≤ List.Length(L)
//操作结果：删除 L的第 i个数据元素，并用 e返回其值，L的长度减 1 
int ListDelete(SqList *L,int i,ElemType *e){
    int k;
    if (L->length==0)/*线性表为空*/
        return ERROR;
    if(i<1|| i>L->length)/*删除位置不正确*/
        return ERROR;
    *e=L->data[i-1];
if(i<L->1ength){/*如果删除不是最后位置*/ 
    for（k=i；k<L->length;k++)/*将删除位置后继元素前移*/
        L->data[k-1]=L->data[k];
    }
    L->length--；
    return OK;
}

复制代码

代码分析：

最好情况：删除末尾元素，不移动任何元素
时间复杂度：O(1)

最坏情况：删除第1个元素，移动次数最多
时间复杂度：O(N)

平均情况：删除中间元素，移动次数平均
时间复杂度：O(N)