咱们来聊聊顺序表插入一个新元素这个事儿。说真的，这玩意儿在数据结构里头，简直就是新手村的第一个小BOSS，看着不难，但一不留神，就能把你写代码的逻辑给搅得一团乱。
你得先在脑子里有个画面。啥是顺序表？别想得太复杂，它就是咱们最熟悉的数组。它的最大特点，也是它所有麻烦的根源，就是连续存储。哥们儿，记住这四个字，像刻在DNA里一样。连续存储意味着所有元素都肩并肩、手拉手地站成一排，内存地址一个挨着一个，中间连个苍蝇都飞不进去。
好了，现在问题来了。这么一排整整齐齐的队伍，你想在中间某个位置，比如说第 i 个位置，硬塞进去一个新兵蛋子。你怎么办？
你总不能直接一脚把原来站在第 i 个位置的老兵给踹飞，然后让新兵站上去吧？那老兵不就“牺牲”了嘛，数据就丢了。这就是覆盖，绝对不行。
正确的做法，跟咱们在电影院找座位，或者挤地铁一模一样。你得对从第 i 个位置开始，一直到队尾的所有人喊一嗓子：“嘿，哥们儿们，都往后挪一个位置！”
这就是顺序表插入一个新元素的灵魂所在——元素后移。
想象一下这个过程，非常关键，因为魔鬼就在细节里。假设你有一支10个人的队伍，已经站了5个人，你想在第3个位置（下标为2）插入一个新成员。
你该怎么挪？
是从前往后挪？也就是让第3个人先挪到第4个位置，再让第4个人挪到第5个位置？
千万别！
你脑补一下，如果第3个人先动，他一屁股坐到第4个人的位置上，第4个人原来的数据就被他覆盖了！等你再想去挪第4个人的时候，你找到的已经是刚刚挪过来的第3个人了。这么一路挪下去，最后的结果就是从第3个位置开始，后面全都是同一个元素。灾难现场，对吧？
所以，正确的“挪动”指令，必须是从后往前的！
- 先找到队伍的最后一个人（当前是第5个人，下标为4），让他往后挪一步，站到第6个位置（下标为5）去。
- 然后，再让倒数第二个人（原来第4个，下标为3），挪到刚才空出来的第5个位置（下标为4）。
- 最后，才轮到我们目标位置的那位（原来第3个，下标为2），让他挪到第4个位置（下标为3）。
看到没？像多米诺骨牌一样，但我们是反着推的。这么一折腾，原先第3个位置（下标为2）是不是就光荣地空出来了？
好极了！现在，把你的新兵蛋子，稳稳地放在这个空位上。
整个行动还没结束！别忘了最后一步，也是最容易忘的一步：更新队伍的总人数。原来是5个人，现在加了一个，总长度（length）就得变成6。
总结一下这个“三步走”战略：
- 第一步：腾位置。 从顺序表的最后一个元素开始，直到要插入的位置
i，依次将所有元素向后移动一位。 - 第二步：萝卜蹲。 将新元素放入位置
i。 - 第三步：报总数。 顺序表的长度加1。
当然，在实际写代码的时候，还得加点“防御性编程”的意识。比如，你得先判断一下，想插入的位置 i 是不是合法的？不能超出范围吧。另外，队伍本身有没有满员？如果一个能装10个人的顺序表已经装满了10个人，那你还想插？门儿都没有，内存溢出了哥们儿。
下面，我们来看一段C语言风格的伪代码，感受一下这个过程的精髓：
“`c
// 假设顺序表结构体是这样定义的
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int length; // 当前长度
} SqList;
// 在顺序表 L 的第 i 个位置插入新元素 e
bool ListInsert(SqList &L, int i, int e) {
// 检查插入位置的合法性 (i的范围通常是1到length+1)
if (i < 1 || i > L.length + 1) {
return false; // 位置不合法
}
// 检查顺序表是否已满
if (L.length >= MAX_SIZE) {
return false; // 存不下了
}
// 关键的核心：元素后移
// 注意看这个循环的起始和结束条件
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1]; // 将元素向后移动
}
// 放入新元素 (注意数组下标是i-1)
L.data[i - 1] = e;
// 更新长度
L.length++;
return true; // 插入成功
}
“`
看懂了吗？那个 for 循环就是整个操作的心脏。j 从 L.length 开始，而不是 L.length - 1，因为我们要操作的是新位置的下标。j 的目标是把 j-1 的东西搬过来。
最后，我们来聊聊代价。你看，为了插入一个元素，我们可能需要移动大半个表的人。如果这个顺序表有一万个元素，而你偏偏要插在最前面（i=1），那就意味着后面9999个元素都得挪窝。这可真是个体力活！所以，顺序表插入一个新元素的时间复杂度是O(n)。这个 n 就是顺序表的长度。
当然，如果你运气好，总是在最后面追加元素，那就不需要移动任何人，直接放上去，长度加一，搞定！这种情况下，效率是最高的，时间复杂度是O(1)。
所以你看，顺序表这个结构，它的优点和缺点就像光和影子一样共生。它查找起来快得飞起（因为地址连续，可以直接计算定位），但一旦涉及到“动筋骨”的插入和删除操作，就显得有点笨拙和迟缓了。
搞懂了这一点，你就真正理解了顺序表插入一个新元素的全部内涵，也为将来学习链表那种“灵活的胖子”打下了坚实的基础。
发表回复