1.顺序表 - 3.5.2插入操作*** - 《数据结构》

刚才我们也谈到，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListIn-sert（*L,i,e），即在线性表L中的第i个位置插入新元素e，应该如何操作？
举个例子，本来我们在春运时去买火车票，大家都排队排的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？”你心一软，就同意了。这时，你必须得退后一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步。骂声四起。但后面的人也不清楚这加塞是怎么回事，没什么办法。
这个例子其实已经说明了线性表的顺序存储结构，在插入数据时的实现过程
（如图所示）。
插入算法的思路：

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

实现代码如下：
//2.动态顺序表实践，2.4指定位置插入数据https://www.yuque.com/muzichenqing/wpdm33/qrkb1f

/* 初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
//i的含义有两个：
//1、i是数列ai的i，从1~n的正整数
//2、i是数组ai的i，从0~n-1的自然数，容器坐标，数组下标
//要明白i的含义，根据下文题要可知，此操作为中插（头插+中插），所以i(0,size-1]，所以i是坐标，数组下标
Status ListInsert(SqList *L, int i, ElemType e)
{
    /* 顺序线性表已经满 */
    if (L->length == MAXSIZE)                       
        return ERROR;
    //原代码的i是正整数，此处是去掉头插，尾插
    //修改删除代码
    ///* 当i不在范围内时 */
    //if (i < 1 || i >L->length + 1)                  
    //    return ERROR;
    /* 若插入数据位置不在表尾 *///尾插不需要挪动数据元素，所以尾插与头插和中插的逻辑是不同的特殊的，所以无法统一
        //当i是坐标时
        //i = pos，i = 0即头插，i = ps->size即尾插
        //当i是正整数时
        //i = 1时是头插，i = ps->size+1时是尾插
    /* 若插入数据位置不在表尾 *///头插和中插
    //int k;//多弄出一个元素也还好，看似乎复杂，其实明了，k = end
    //if (i <= L->length){
    //    /*将要插入位置后数据元素向后移动一位 */
    //    for (k = L->length - 1; k >= i - 1; k--)    
    //        L->data[k + 1] = L->data[k];
    //}
    //当i是正整数时
    /* 将新元素插入 */
    //L->data[i - 1] = e;                             
    //L->length++;
    //用循环貌似更简单明了//多弄出一个元素也还好，看似乎复杂，其实明了，k = end
    //ListInsert(SqList *L, int i, ElemType e)
    int end = ps->size - 1;
    while (end >= i)//end是数组尾坐标
    {
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    //当i是坐标时
    ps->a[i] = x;
    ps->size++;
    return OK;
}
//头插//全往后挪
void SeqListPushFront(SL* ps, SLDateType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0){
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[0] = x;
    ps->size++;
}
//中插//比较复杂，需要考虑各种情况
void SeqListInsert(SL* ps, int pos, SLDateType x)
{
    assert(ps);
    assert(pos <= ps->size && pos >= 0);//考虑各种情况，pos=0即头插，pos=ps->size即尾插
    SeqListCheckCapacity(ps);//凡是插入，必虑扩容
    //尾插不需要挪动数据元素，所以尾插与头插和中插的逻辑是不同的特殊的，所以无法统一
    int end = ps->size - 1;
    //pos=0即头插，pos=ps->size=end+1即尾插
    while (end >= pos)//end是数组尾坐标{
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[pos] = x;
    ps->size++;
}
//尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    ps->a[ps->size] = x;//从a[0]开始
    ps->size++;
}