AB31-在顺序表L的第k个位置插入元素x

代码实现

/**
 * 在顺序表L的第k个位置插入元素x
 * @param L 顺序表指针
 * @param k 插入位置（从1开始计数）
 * @param x 要插入的元素
 * @return 插入成功返回true，失败返回false
 */
bool insert_L(Sqlist *L, int k, int x) {
    // 检查插入位置的合法性
    // k必须在[1, length+1]范围内
    if (k < 1 || k > L->length + 1) {
        printf("插入位置不合法，插入失败\n");
        return false;
    }

    // 从后往前移动元素，为新元素腾出空间
    // 将第k个位置及之后的所有元素向后移动一位
    for (int i = L->length - 1; i >= k - 1; i--) {
        L->data[i + 1] = L->data[i];
    }

    // 在第k个位置插入新元素
    L->data[k - 1] = x;

    // 顺序表长度加1
    L->length++;

    return true;
}

复杂度分析

时间复杂度：O(n)

• 最好情况：O(1) - 当k = n+1时，在表尾插入，无需移动元素
• 最坏情况：O(n) - 当k = 1时，在表头插入，需要移动所有n个元素
• 平均情况：O(n) - 平均需要移动n/2个元素

空间复杂度：O(1)

• 只使用了常数个额外变量（i等）
• 没有使用额外的存储空间
• 属于原地操作

关键点总结

1. 位置检查：k >= 1 && k <= length + 1
2. 移动方向：从后往前移动元素
3. 移动范围：i = length-1 到 i = k-1
4. 插入位置：data[k-1] = x（注意数组下标从0开始）
5. 长度更新：length++

注意事项

• 位置k是从1开始计数的，而数组下标从0开始
• 插入位置可以是length+1，表示在表尾插入
• 移动元素时要防止数组越界