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

01

将值单链表的第i个

位置上的结点删除

之前我们讲过了链表的插入和遍历，这次我们来看链表的删除。在顺序表的删除中，删去其中一个元素，就出现了存储空间的空隙，其余的元素就要通过向前移动的方式把这个空隙给弥补上，这就非常的麻烦，需要进行很多次操作。而在单链表中，想要实现删除操作，就是将它的前继结点绕过，指向它的后继结点即可，如图1所示：

图1

我们所要做的实际上就是一步，p->next = p->next->next，用q来取代p->next，即是：q = p->next ; p->next = p->next->next

01

图例

我们可以打个比方来解释这个操作，就好像原本爸爸左手牵着妈妈右手牵着儿子在马路上散步，如图2。

图2

突然对面迎面走过一位美女，爸爸一下子看呆了（图3）

图3

但这情景被妈妈逮了个正着，于是她生气地甩开爸爸的手，绕过他，扯开父子两，牵着宝宝的手就快速往前走，如图4。

图4

此时妈妈是p结点，妈妈的后继是爸爸p->next，也可以叫q结点，妈妈的后继的后继是儿子，即q->next。当妈妈去牵儿子的手时，就与爸爸完全没有联系了（图5）。

图5

02

代码

接下来我们来看这个代码：

03

总结

结合之前的例子和代码，我们可以把整个思路整理成3步：

1.设置辅助指针：设置结点指针p,q分别用来指示要删除结点和它的前驱结点；

2.找到前驱结点：遍历链表找到要删除结点的前驱结点；

3.进行删除操作：把要删除结点的前驱的后继变为被删除的结点的后继，即之前举例介绍的那个操作。

可以用一句话来帮助记忆：设指针（Lnode *p,*q），找前驱（p = GetElem(L,i-1)），删结点（q = p->next ; p->next = p->next->next）。

02

将值为x的结点插入到

单链表的第i个位置上

在上上节中我们就详细介绍了链表的插入，所以这段代码其实是一个对插入操作的灵活应用，同时还需要额外的对链表中结点进行计数。所以我们话不多说直接来看代码。

01

代码

02

总结

其实我们把顺序表中的插入结点拿过来进行比较，思路会非常清楚：

1.判位置：因为我们这里把链表进行了排序，所以需要像顺序表一样判定插入位置是否合法（if(iLength(L)+1)）；

2.创结点：如果位置合法，则创建数据域为x的结点，等待插入（malloc）；

3.插结点：最后利用链表的插入操作插入该结点（s->next = p->next; p->next = s）。

所以从这个代码我们可以看出，在学习了顺序表和单链表后，我们需要去把学过的代码结合起来，去总结，很多的操作其实思路都是类似的。而且在学完线性表的基本操作后，后续代码的考察，更多的是对于基本操作的灵活应用，大家一定要好好去总结。