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)。
所以从这个代码我们可以看出,在学习了顺序表和单链表后,我们需要去把学过的代码结合起来,去总结,很多的操作其实思路都是类似的。而且在学完线性表的基本操作后,后续代码的考察,更多的是对于基本操作的灵活应用,大家一定要好好去总结。
领取专属 10元无门槛券
私享最新 技术干货