顺序表的插入

戒骄戒躁

顺序的插入操作的实现——算法思想

一、开始插入操作前需要注意的情况:

1、判断插入的位置i是否合法
2、判断顺序表存储空间是否已满，若已满则返回ERROR，
即判断L.length是否等于数组的最大值，如果等于，说明数组已满。

二、避免不发生上述情况就可以开始插入操作：

//空出第i个位置
1、将最后一个元素到第i个元素的位置往后移，空出第i个位置
2、将要插入的新元素e放入第i个位置
3、表长加1，插入元素成功返回OK

伪代码实现：

/*伪代码并不能在电脑上运行，但方便描述算法思想，所以学一门编程语言吧*/
Status Listlnsert_Sq(SqList &L, int i, Elem Type e){
    if(i < 1 || i > L.length + 1)//判断插入位置是否合法，注意这是伪代码i是从1开始的，L.length占了结尾一个结点所以加1
        return ERROR;
        
    if(L.length == MAXSIZE)     //存储空间已满
        return ERROR;
    
    for(j = L.length; j >= i - 1; j--)//将最后一个元素到第i个元素的位置往后移，空出第i个位置
        L.elem[j+1] = L.elem[j];//从最后一个元素开始，把前一个元素的值放到后一个元素
    L.elem[i-1] = e;            //将新元素e放入第i个位置
    L.length ++;//表长加1
    return OK;
}

教材《数据结构》的伪代码就这点不好，在循环里没有迁就C语言下标从0开始。

最佳情况：插入尾结点之后
最坏情况：插入首结点之前

一共有n+1种情况，平均移动次数是n/2,
平均时间复杂度为O(n)。

所以在顺序表上插入是很麻烦的。