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 表示尾部追加。
#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;
}预期输出
10 20 25 30 40如果实际编译器或运行环境不同,输出内容仍应保持这一元素顺序。
边界位置怎么处理
头部插入时 index == 0,所有现有元素都要右移;尾部插入时 index == size,循环条件一开始就不成立,因此不需要移动任何元素。非法情况主要有三类:位置小于 0、位置大于 size、顺序表已满。示例统一返回 0,调用方可以据此决定报错、扩容或结束操作。
时间复杂度为什么是 O(n)
设当前有 n 个元素,在下标 index 插入时,需要移动 n - index 个元素。尾部插入移动 0 次,成本接近 ;头部插入移动 n 次,是最坏情况 。因此,当插入位置任意时,顺序表插入通常按 分析。
连续内存让顺序表具备快速随机访问,但中间插入的代价正来自这份连续性:为了保持逻辑顺序,后续元素必须整体让位。实际实现时,只要先检查边界,再从后向前移动,就能同时保证数据完整和数组安全。