【图解】数据结构代码领背-02

上次我们讨论了线性表的顺序存储结构，学习了顺序存储的代码。既然我们懂得了，数据如何去存储，那不可避免地要去学习如何对这些数据进行操作，这里我们就来学习一下顺序存储结构的插入与删除。

在具体看代码前我们可以来看一个形象一点的例子：马上就要过年了，大家都在排队买春运的火车票。本来排的好好的，这时候来了一位美女，对着队伍中排第三个的你说：“大哥，求求你帮我个忙，我家母亲得了急病，我着急着回去看她，你看可否让我排你前面？”（如图1）

图1

你一看这美女楚楚可怜，心一软就同意了。这时，你必须得退后一步，不然她没法进到队伍里面来。这可不得了，你一退，后面的人就像蠕虫一样，都得退一步，如图2所示。

图2

一时间骂声四起，但后面的人不清楚这加塞是怎么回事，也就没什么办法。

我们来看在顺序表中插入元素的代码：

”

其实从刚才举的例子中，结合实际的代码，我们不难梳理出顺序表插入的5个步骤：

1. 定位置：一个顺序表（一维数组）中的数据有相应的数组下标，插入位置如果小于第一个数据的下标或者高于最后一个数组的下标，就无法把元素插入到这个顺序表中。

2. 看空间：顺序表存储是事先分配一段连续的内存存储单元，使用完了这段存储单元，也就没法再继续存储数据，所以插入前要判断是否还有存储空间。

3. 移位置：就像排队买车票的例子，有一个元素插入，后面的所有元素就要各自后移为这个元素腾出空间。

4. 加表长：将元素顺利插入到顺序表，现有的顺序表元素变多，表长也就相应增大了，所以插入结束需要将原表长相应加1。

”

我们可以用一首打油诗来帮助记忆：插入位置要规范((iL.length + 1))，空间已满不可行（（L.length >= MaxSize））。入表之前要移位（L.data[j] = L.data[j-1]），结束之后长加一(L.length++)。

在顺序表中删除一个元素，其实可以说是插入元素的逆过程，我们可以接着上面的例子。此时后面意见很大，都说怎么可以这样，再怎么有原因，插队就是违背规则，是不被允许的，有本事，就找火车站开后门去。就在这时，从远处跑来一个胖子，对着美女喊：“可找到你了，你这骗子，把钱还给我。”（图3）

图3

只见这女子二话不说，突然就冲出队伍，胖子追在其后，消失在人群中。哦，原来她是倒卖车票的黄牛，刚才还装可怜。于是排队的人群又想蠕虫一样，各向前移了一步，骂声渐息，队伍也恢复了平静，如图4所示。

图4

下面我们来看代码：

”

根据上面的例子，再结合代码，我们很容易看出从线性表中删除一个元素，是插入一个元素的反过程，主要有4步：

1. 定位置：删除的元素要存在于线性表内，对下标不在线性表范围中的元素显然是不合理的。

2. 删元素：下标合法，则找到要删除的元素，把它提取出来。

3. 移位置：删除了这个元素，意味着原本存储它的位置空了出来，连续存储的情况下后面的元素可以都往前进一位。

4. 减表长：删除了一个元素，线性表中的元素个数减少，线性表的表长也就相应减少。

”

我们也可以用一首打油诗来帮助记忆：删除元素要在列（(iL.length)），找准位置取出来(e = L.data[i-1])。删除空位往前移(L.data[j-1] = L.data[j])，结束之后长减一(L.length--)。

可以看到顺序表的插入与删除是一对互逆操作，把两个的代码与操作放在一起比较，能更方便大家去记忆。