C / C++ / 系统课时
删除元素并保持顺序
删除元素并保持顺序
顺序表删除某个位置后,不能只把该单元“清空”,因为有效元素必须继续占据前 size 个位置。正确删除需要先保存被删值,再把后续元素依次左移,并处理空表、非法下标等边界。本节完成一个可运行的 C 实现。
学习目标
- 能实现按下标删除并保持剩余元素原顺序
- 能正确处理空表、非法下标和被删值返回
- 理解左移范围与删除操作的时间复杂度
删除后为什么必须左移
假设顺序表为 10, 20, 30, 40, 50,删除下标 1 的 20。如果只把 data[1] 改成某个特殊值,顺序表中就出现“空洞”,而 size 也无法再准确表示前多少个位置有效。
正确做法是让 30 覆盖 20 的位置,再让 40、50 依次左移,最后把 size 减一。数组尾部原先的值即使还留在内存中,也已经不属于顺序表的有效范围。

与插入相反,删除后的移动要从删除位置向后执行。此时每一步读取 data[i + 1] 再写入 data[i],不会破坏下一步仍需读取的源数据。
用 C 实现按位置删除
下面的 remove_at 通过输出参数 removed 返回被删除的值。只有删除成功时才修改 size,这样失败操作不会破坏顺序表状态。
#include <stdio.h>
#define CAPACITY 8
typedef struct {
int data[CAPACITY];
int size;
} SeqList;
int remove_at(SeqList *list, int index, int *removed) {
if (list == NULL || removed == NULL) {
return 0;
}
if (list->size == 0) {
return 0;
}
if (index < 0 || index >= list->size) {
return 0;
}
*removed = list->data[index];
// 用后一个元素覆盖前一个位置,使有效区继续保持连续。
for (int i = index; i < list->size - 1; ++i) {
list->data[i] = list->data[i + 1];
}
list->size--;
return 1;
}
void print_list(const SeqList *list) {
for (int i = 0; i < list->size; ++i) {
printf("%d%s", list->data[i], i == list->size - 1 ? "\n" : " ");
}
}
int main(void) {
SeqList list = {{10, 20, 30, 40, 50}, 5};
int removed = 0;
if (!remove_at(&list, 1, &removed)) {
printf("remove failed\n");
return 1;
}
printf("removed: %d\n", removed);
print_list(&list);
return 0;
}预期输出
removed: 20
10 30 40 50删除成功后,size 从 5 变为 4,因此只有下标 0 到 3 属于有效数据。
边界条件怎么判断
合法删除位置只能满足 0 <= index < size。当 size == 0 时没有任何可删除元素;当 index == size 时也属于越界,因为最后一个有效下标其实是 size - 1。若要删除尾元素,移动循环不会执行,只需把 size 减一即可。
时间复杂度与删除位置有关
若当前有 n 个元素,删除下标 index 后需要移动 n - index - 1 个元素。删除尾元素不需要移动,接近 ;删除头元素要搬动其余所有元素,最坏为 。因此,任意位置删除通常按 处理。
顺序表删除的关键不在“擦掉一个值”,而在维护连续有效区:先验证下标,保存目标元素,从删除点开始向左覆盖,最后再缩小 size。这个顺序能避免越界,也能保证剩余元素的相对顺序完全不变。