首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

【图解】数据结构代码领背-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)。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20210216A03J0900?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券