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,这样失败操作不会破坏顺序表状态。

c
#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;
}

预期输出

text
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 个元素。删除尾元素不需要移动,接近 O(1)O(1);删除头元素要搬动其余所有元素,最坏为 O(n)O(n)。因此,任意位置删除通常按 O(n)O(n) 处理。

顺序表删除的关键不在“擦掉一个值”,而在维护连续有效区:先验证下标,保存目标元素,从删除点开始向左覆盖,最后再缩小 size。这个顺序能避免越界,也能保证剩余元素的相对顺序完全不变。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

删除元素并保持顺序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通