AB36-用顺序表最后一个元素覆盖最小元素，并返回该最小元素

代码实现

/**
 * 用顺序表最后一个元素覆盖最小元素，并返回该最小元素
 * @param L 指向顺序表的指针
 * @return 最小元素的值
 */
int Del_min(Sqlist *L) {
    // 初始化最小值和位置
    int pos = 0;                    // 最小元素的位置索引
    int min = L->data[0];          // 假设第一个元素为最小值

    // 遍历整个顺序表查找最小元素（若有多个相同最小值，取第一个）
    for (int i = 0; i < L->length; i++) {
        // 发现更小的元素
        if (min > L->data[i]) {
            min = L->data[i];      // 更新最小值
            pos = i;               // 记录最小值位置
        }
    }

    // 特殊情况处理：如果最小元素就是最后一个元素
    if (pos == L->length - 1) {
        // 不需要任何操作，直接返回最小值
        return min;
    }

    // 一般情况：用最后一个元素覆盖最小元素
    L->data[pos] = L->data[L->length - 1];

    // 更新顺序表长度（可选，根据题目要求而定）
    L->length--;

    // 返回最小元素值
    return min;
}

算法执行流程图解

情况1：最小元素不是最后一个元素

原顺序表：[3][7][1][9][5][1]  (length=6)
索引：     0  1  2  3  4  5

查找过程：
i=0: min=3, pos=0
i=1: 3>7? 否
i=2: 3>1? 是 → min=1, pos=2  // 找到第一个最小值
i=3: 1>9? 否
i=4: 1>5? 否  
i=5: 1>1? 否

执行覆盖操作：
pos=2 ≠ length-1=5  需要覆盖
L->data[2] = L->data[5] = 1

结果：[3][7][1][9][5]  (length=5)
返回：min = 1

情况2：最小元素就是最后一个元素

原顺序表：[3][7][5][9][1]  (length=5)
索引：     0  1  2  3  4

查找过程：
i=0: min=3, pos=0
i=1: 3>7? 否
i=2: 3>5? 否
i=3: 3>9? 否
i=4: 3>1? 是 → min=1, pos=4

特殊情况处理：
pos=4 == length-1=4  最小元素就是最后一个
直接返回，不做任何修改

结果：[3][7][5][9][1]  (length=5不变)
返回：min = 1

复杂度分析

时间复杂度：O(n)

• 查找最小元素：需要遍历整个顺序表一次，O(n)
• 覆盖操作：常数时间O(1)
• 总体：O(n)

空间复杂度：O(1)

• 只使用了常数个额外变量：pos、min、i
• 没有使用额外的数据结构
• 空间复杂度为 O(1)

增强版本：添加边界条件检查

/**
 * 增强版本：添加边界条件检查
 */
int Del_min_Enhanced(Sqlist *L) {
    // 边界条件检查
    if (L == NULL || L->length <= 0) {
        printf("顺序表为空或不存在\n");
        return -1;  // 或者根据需求返回其他错误值
    }

    // 只有一个元素的情况
    if (L->length == 1) {
        int min = L->data[0];
        L->length--;  // 可选
        return min;
    }

    // 原有逻辑...
    int pos = 0;
    int min = L->data[0];

    for (int i = 1; i < L->length; i++) {  // 从i=1开始更合理
        if (min > L->data[i]) {
            min = L->data[i];
            pos = i;
        }
    }

    if (pos != L->length - 1) {
        L->data[pos] = L->data[L->length - 1];
    }

    L->length--;  // 根据具体需求决定是否更新长度
    return min;
}

算法特点

核心思想： 1. 遍历顺序表找到最小元素及其位置 2. 如果最小元素不是最后一个元素，则用最后一个元素覆盖它 3. 返回最小元素值

关键点： - 处理最小元素恰好是最后一个元素的特殊情况 - 题目对长度更新的表述有歧义，需根据具体要求决定是否更新length

应用场景： 这种操作常用于优先队列或堆的实现中，是一种特殊的删除最小值操作。