AB35-有序顺序表中插入元素x

代码实现

/**
 * 在有序顺序表中查找插入位置
 * @param L 有序顺序表（传值调用）
 * @param x 要插入的元素
 * @return 应该插入的位置索引
 */
int find_L(Sqlist L, int x) {
    // 从头开始查找第一个大于x的元素位置
    for (int i = 0; i < L.length; i++) {
        // 找到第一个大于x的元素位置
        if (x < L.data[i]) {
            return i;  // 在此位置插入，保持有序性
        }
    }
    // 如果x大于所有元素，则插入到末尾
    return L.length;
}

/**
 * 在有序顺序表中插入元素并保持有序性
 * @param L 指向顺序表的指针
 * @param x 要插入的元素
 */
void insert_L(Sqlist *L, int x) {
    // 第一步：查找合适的插入位置
    int pos = find_L(*L, x);

    // 第二步：将插入位置及之后的元素后移一位
    for (int i = L->length - 1; i >= pos; i--) {
        L->data[i + 1] = L->data[i];
    }

    // 第三步：在指定位置插入新元素
    L->data[pos] = x;

    // 第四步：顺序表长度加1（重要！）
    L->length++;
}

算法执行流程图

原有序顺序表：[1][3][5][8][10]  插入x=6

第一步：查找插入位置
[1][3][5][8][10]
       ↑
     pos=3 (因为6<8，所以插入位置为3)

第二步：元素后移
[1][3][5][8][10][_]
       ← ← ← ←    (data[4]到data[3]后移)

第三步：插入元素
[1][3][5][6][8][10]
          ↑
         x=6

第四步：长度更新
length: 5 → 6

复杂度分析

时间复杂度：O(n)

• find_L函数：O(n) - 最坏情况需要遍历整个顺序表
• insert_L函数：
• 查找位置：O(n)
• 元素后移：O(n) - 最坏情况需要移动所有元素
• 插入操作：O(1)
• 总体：O(n)

空间复杂度：O(1)

• 分析过程：
• 只使用了常数个额外变量：pos、i
• 没有使用额外的数据结构
• 所有操作都在原数组上进行
• 空间复杂度为 O(1)

算法特点

优点： - 保持了顺序表的有序性 - 实现逻辑清晰 - 空间效率高

缺点： - 插入操作需要移动元素，时间复杂度较高 - 频繁插入时效率较低

核心思想： 1. 查找阶段：利用有序性，找到第一个大于插入元素的位置 2. 插入阶段：通过元素后移为新元素腾出空间 3. 维护有序性：确保插入后仍然保持递增顺序

注意事项

1. 边界处理：当插入元素大于所有现有元素时，插入到末尾
2. 数组容量：确保顺序表有足够的空间进行插入
3. 长度更新：插入完成后必须更新length字段