3.5.2 插入操作

刚才我们也谈到，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListInsert（*L,i,e），即在线性表L中的第i个位置插入新元素e ，应该如何操作？

插入算法的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i处；表长加1。

实现代码如下：

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