C / C++ / 系统课时

在顺序表中插入元素

在顺序表中插入元素

顺序表把元素连续存放在数组中,因此“在中间插入”不是简单写入一个位置:必须先给新元素腾出空间,再保证原有元素的相对顺序不变。本节用 C 语言实现按位置插入,并把边界检查、移动方向和时间复杂度一起讲清楚。

学习目标

  • 能实现顺序表指定位置插入,并正确处理容量不足和非法位置
  • 理解为什么移动元素时必须从后向前执行
  • 能根据插入位置判断移动次数和时间复杂度

插入操作真正要解决什么

假设顺序表当前保存 10, 20, 30, 40,要在下标 2 插入 25。数组下标 2 已经被 30 占用,不能直接覆盖,否则原数据会丢失。正确做法是先把 40、30 依次向右移动一格,再把 25 写入空出的下标 2。

顺序表中间插入时元素右移示意

移动必须从后向前进行。如果从下标 2 开始向右移动,先执行 data[3] = data[2] 会把原来的 40 覆盖,后续就无法恢复。顺序表插入的核心不只是“移动”,还包括选择不会覆盖源数据的移动方向。

用 C 实现指定位置插入

下面定义一个固定容量顺序表,size 表示当前有效元素个数。允许的插入位置是 0 到 size:其中 0 表示头部插入,size 表示尾部追加。

c
#include <stdio.h>

#define CAPACITY 8

typedef struct {
    int data[CAPACITY];
    int size;
} SeqList;

int insert_at(SeqList *list, int index, int value) {
    if (list == NULL) {
        return 0;
    }
    if (index < 0 || index > list->size) {
        return 0;
    }
    if (list->size >= CAPACITY) {
        return 0;
    }

    // 从最后一个有效元素开始右移,避免覆盖尚未搬走的数据。
    for (int i = list->size; i > index; --i) {
        list->data[i] = list->data[i - 1];
    }

    list->data[index] = value;
    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}, 4};

    if (!insert_at(&list, 2, 25)) {
        printf("insert failed\n");
        return 1;
    }

    print_list(&list);
    return 0;
}

预期输出

text
10 20 25 30 40

如果实际编译器或运行环境不同,输出内容仍应保持这一元素顺序。

边界位置怎么处理

头部插入时 index == 0,所有现有元素都要右移;尾部插入时 index == size,循环条件一开始就不成立,因此不需要移动任何元素。非法情况主要有三类:位置小于 0、位置大于 size、顺序表已满。示例统一返回 0,调用方可以据此决定报错、扩容或结束操作。

时间复杂度为什么是 O(n)

设当前有 n 个元素,在下标 index 插入时,需要移动 n - index 个元素。尾部插入移动 0 次,成本接近 O(1)O(1);头部插入移动 n 次,是最坏情况 O(n)O(n)。因此,当插入位置任意时,顺序表插入通常按 O(n)O(n) 分析。

连续内存让顺序表具备快速随机访问,但中间插入的代价正来自这份连续性:为了保持逻辑顺序,后续元素必须整体让位。实际实现时,只要先检查边界,再从后向前移动,就能同时保证数据完整和数组安全。

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

目录与阅读设置

阅读设置

17

记录一个想法

在顺序表中插入元素

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

登录哪都通