数据结构-线性表-应用题-2.2-4

从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。

有序顺序表如无特殊说明,一般指递增有序

先找到值大于等于s的第一个元素,然后找值大于t的第一个元素,将后面的元素前移覆盖待删除元素序列

bool del(SqList &L, int s, int t) {
    int i, j;
    if (s >= t || L.length == 0) {
        return false;
    }
    // 找到第一个大于等于s的元素的位置
    for (i = 0; i < L.length && L.data[i] < s; i++);
    // 若没有找到大于等于s的元素或遍历到末尾,则返回false
    if (i >= L.length) {
        return false;
    }
    // 找到第一个大于t的元素的位置
    for (j = i; j < L.length && L.data[j] <= t; j++);
    // 将[j, L.length)区间的元素向前移动到[i, L.length-(j-i))区间
    for (; j < L.length; i++, j++) {
        L.data[i] = L.data[j];
    }
    // 更新顺序表的长度
    L.length = i;
    return true;
}
  • s >= t || L.length == 0:首先进行边界检查,如果 s 大于等于 t 或者顺序表为空,则无法删除任何元素,直接返回 false
  • for (i = 0; i < L.length && L.data[i] < s; i++);:从顺序表的起始位置开始,查找第一个大于等于 s 的元素位置 i
  • if (i >= L.length):若没有找到大于等于 s 的元素,说明顺序表中不存在需要删除的元素,直接返回 false
  • for (j = i; j < L.length && L.data[j] <= t; j++);:继续从位置 i 开始,查找第一个大于 t 的元素位置 j
  • for (; j < L.length; i++, j++) { L.data[i] = L.data[j]; }:将 [j, L.length) 区间的元素向前移动到 [i, L.length-(j-i)) 区间,实现删除操作。
  • L.length = i;:更新顺序表的长度为 i,即删除操作后的新长度。
  • return true;:删除成功,返回 true。

删除元素不包括s和t

为什么是这个区间?

考虑以下情况:
区间 [j, L.length)包括从位置 j 到顺序表末尾的所有元素。这些元素需要被保留,因为它们不在要删除的范围 [s, t] 内。
区间 [i, L.length-(j-i))表示将上述元素移动到的新位置。这个区间的起始位置是 i,这是因为 i 是在 [s, t] 范围内找到的第一个元素的位置,即从这里开始的元素需要被删除或覆盖。

通过设置新的顺序表长度为 i 的值(即移动完成后的最后一个元素的索引加一),我们有效地切除了数组尾部的多余部分,这部分现在包含了重复的、不再需要的数据。

上一篇:【C语言】static关键字用法-一、static修饰局部变量


下一篇:MY SQL 实验一: