从有序顺序表中删除其值在给定值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 的值(即移动完成后的最后一个元素的索引加一),我们有效地切除了数组尾部的多余部分,这部分现在包含了重复的、不再需要的数据。