当前位置：首页 > news >正文

傻瓜式建站平台外贸营销型网站制作公司

news 2025/7/1 9:05:27

傻瓜式建站平台,外贸营销型网站制作公司,网站建设与服务技能实训,汕头市城乡与住房建设局本节主要介绍双向链表及双向链表的插入算法。本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频] 1. 双向链表 （1）为什么讨论双向链表单链表的结点 → 有指示后继的指针域 → 找后继结点方便&…

本节主要介绍双向链表及双向链表的插入算法。

本文部分ppt、视频截图来自：[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]

1. 双向链表

（1）为什么讨论双向链表

在这里插入图片描述

单链表的结点 → 有指示后继的指针域 → 找后继结点方便，即查找某结点的后继结点的执行时间为O(1)。
单链表 → 无指示前驱的指针域 → 找前驱结点难：从表头出发查找，即：查找某结点的前驱结点的执行时间为O(n)。因此，可以采用双向链表，能够克服单链表不便找前驱结点的缺点。

（2）双向链表定义

双向链表是什么？

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域 prior ，这样链表中就形成了有两个方向不同的链，故称为双向链表。

双向链表的结构和结构定义

在这里插入图片描述

双向链表结构可定义如下：

typedef struct DuLNode{Elemtype   data;struct DuLNode *prior,*next;
}DuLNode, *DuLinkList;

在这里插入图片描述
（3）双向循环链表

和单链的循环表类似，双向链表也可以有循环表

让头结点的前驱指针指向链表的最后一个结点；
让最后一个结点的后继指针指向头结点。

在这里插入图片描述

（4）双向链表结构的对称性

双向链表结构的对称性（设指针 p 指向某一结点）：

//要找某个结点，可以通过它前驱的后继，也可以通过它后继的前驱找到
p -> prior -> next = p = p -> next -> prior

在双向链表中有些操作(如:ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为 O(n)。

2. 双向链表的插入、删除算法

（1）双向链表的插入

在 a 结点和 b 结点中间插入新结点 x ：此时只知道b的地址p和x的地址s
在这里插入图片描述

【分析】
① 新结点 x 的前驱指针指向结点 a。
s -> prior = p -> prior;
② 结点 a 的后继指针指向新结点 x
p -> prior -> next = s;
③ 新结点 x 的后继指针指向结点 b
s -> next = p;
④ 结点 b 的前驱指针指向新结点 x
p -> prior = s;

【双向链表的插入算法描述】
void ListInsert_DuL(DuLinkList &L, int i, ElemType e){ //在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 eif(!(p = GetElemP_DuL(L,i)))  return ERROR;s = new DuLNode;  s -> data = e;s -> prior = p -> prior;  p -> prior -> next = s;s -> next = p;  p -> prior = s;return OK;
} //ListInsert_DuL