网站首页
这些小活动你都参加了吗？快来围观一下吧！>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » 双向链表

共2条 1/1 1 跳转至页

双向链表

lin35162
高工
2017-12-18 21:29:57     打赏
双向链表1.听名字可能就能猜到双向链表就是链表结点包含两个指针，一个指针是指向下一个结点的，另一个指针当然就是指向上一个结点的。这样的链表就可以通过第一个结点找到最后一个结点，当然也可以通过最后一个结点找到第一个结点，因为它是双向的，下面看下双向链表的示意图：
2.双向链表的初始化：由于这里的链表头结点不参与计算，所以头结点的pPre指针是一直指向NULL指针的。
3.双向链表的创建过程：由于双向链表的每个结点包含两个指针那么这个时候我们就要小心处理好每一个指针的指向，要不然会有很多意想不到的错误。同样的，和单向链表的创建过程一样，需要一个辅助指针来指向最后一个结点，然后每新建一个结点，这个结点的pNext指针都是指向NULL指针的，pPre指针指向上一个结点（这是和单向链表不同的地方），然后让上一个指针的pNext指向新建的结点，这样整个链表就连接起来了。
4.双向链表插入结点过程：知道了双向链表的创建过程，那么插入结点的过程就大同小异 了，有一点需要特别注意的就是这里的变量position范围也是从1到链表长度加1，但是如果待插入的位置是最后一个位置的话，情况就不同了，看到下面的图我们可以很好的理解，因为没新建一个结点的时候都需要处理两个指针，而且新建结点的下一个结点的pPre指针就需要指向这个新建的结点，但是有可能这个新建的结点可能就已经是最后一个结点了，那么这个时候再执行[cpp] view plain copy

  1. ptemp->pNext->pPre = pnew;  

这条指令的时候就会报错了，因为ptemp->pNext已经是个NULL指针了，那空指针哪里还有pPre呢。因此在程序中要进行一次判断，看看结点是否是最后一个结点。
5.双向链表删除结点的过程：要注意的问题和插入结点一样，看看这个结点是否为NULL。这里就不重复了。


回复
收藏
0


vaioshop
专家
2017-12-19 09:08:19     打赏
2楼

不错，学习一下。        


评论
共2条 1/1 1 跳转至页

回复

匿名不能发帖！请先 [ 登陆 注册 ]