AB32-删除顺序表L的第k个元素并返回其值

代码实现

/**
 * 删除顺序表L的第k个元素并返回其值
 * @param L 顺序表指针
 * @param k 删除位置（从1开始计数）
 * @return 删除成功返回被删除元素的值，失败返回-100
 */
int delete_L(Sqlist *L, int k) {
    // 检查删除位置的合法性
    // k必须在[1, length]范围内（注意与插入操作的区别）
    if (k < 1 || k > L->length) {
        printf("删除位置不合法，删除失败\n");
        return -100;
    }

    // 保存要删除的元素值
    int res = L->data[k - 1];

    // 从第k+1个位置开始，将后续元素向前移动一位
    for (int i = k; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }

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

    return res;
}

复杂度分析

时间复杂度：O(n)

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

空间复杂度：O(1)

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

关键点总结

1. 位置检查：k >= 1 && k <= length（注意与插入的区别）
2. 保存元素：res = data[k-1]
3. 移动方向：从前往后移动元素
4. 移动范围：i = k 到 i = length-1
5. 移动操作：data[i-1] = data[i]（向前移动一位）
6. 长度更新：length--

与插入操作的主要区别

操作	位置范围	移动方向	移动起始位置	移动终点
插入	[1, length+1]	从后往前	length-1	k-1
删除	[1, length]	从前往后	k	length-1

注意事项

• 删除位置k不能等于length+1（不存在该位置）
• 移动元素时注意数组下标的对应关系
• 返回值-100作为错误标识，实际应用中可能需要更合适的错误处理方式