浙教版（2019）高中信息技术选修一 2.2.2双向链表课件（14张PPT）

(共14张PPT)
2.2 链表
双向链表
什么是双向链表？
双向链表（又称双链表）每个节点有两个指针prev和next，
分别指向其前驱节点和后继节点，这样可以提供方便的双向
查找功能。
双向链表的表示？
Dui=[[“吴坚”，-1，1],[“王林”,0，2],
[“黄刚”,1，3],[“李丰”,2，-1]]
节点
（由数据区域和前驱节点指针、后继节点指针构成）
我前面没人
我后面没人
我后面是黄刚
双向链表的特性
双向链表中当节点中prev指向为-1（即指向为空）时，表示该节点为链表
中的首个节点；相对的，当节点中next指向为-1时，表示该节点为链表中
的最后一个节点。
下图所示为用二维列表表示一个长度为6的双向链表
data 1
^
data 2
data 3
data 4
data 5
data 6
列表名data
列表索引 数据域 prev指针 next指针
0 data6 4 -1
1 data4 5 4
2 data1 -1 3
3 data2 2 5
4 data5 1 0
5 data3 3 1
head
双向链表的基本操作
一、双向链表的创建
Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来
表示每一个节点，其中第一个元素存储数据，第二、三个元素分别存储
前驱指针prev和后继指针next。
创建一个拥有2个节点的双向链表dblinklist的代码如下：
dblinklist=[[6,-1,1],[8,0,-1],]
head=0
创建一个空链表dblinklist的代码如下：
dblinklist=[]
head=-1
二、双向链表节点的访问
链表节点只能通过头指针（head）进行访问，其他节点通过节点间的next指针
依次访问。
可以设计如下自定义函数输出链表的所有节点：
def shuchu(a,head):
p=head
while a[p][2]!=-1
print(a[p][0],end=“---->”)
p=a[p][2]
print(a[p][0])
三、双向链表节点的插入
链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与
其前驱与后继节点的指针，将新节点插入到链表的正确位置。
从链表头部插入一个新节点（头插法）：例如，在双向链表a的头部插入一个新节点
node的代码如下：
node=[random.randint(1,10),-1,head]
a.append(node)
if head!=-1:
a[head][1]=len(a)-1
head=len(a)-1
在链表a的索引p之后插入一个新节点，可以设计自定义函数如下：:
Def insert_behind(a,p,data):
node=[data,p,a[p][2]]
a.append(node)
if a[p][2]!=-1:
a[a[p][2]][1]=len(a)-1
a[p][2]=len(a)-1
四、双向链表节点的删除
双向链表节点的删除操作比单向链表要简单，它无需查找前驱节点，只需
判断被删除的节点是否有前驱节点或后继节点，然后修改相关指针即可。
尾结点可以直接删除，若删除了头节点，则需要修改头指针。
可设计自定义函数删除索引为p的节点，代码如下：
Def delete(a,head,p):
if a[p][1]!=-1:
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
a[a[p][2]][1]=a[p][1]
if head==p:
head=a[head][2]
return head
1.Python中可以使用二维列表来模拟双向链表，用包含三个元素的
列表来表示每一个节点，其中第一个元素存储数据，第二、三个元素
分别存储前驱指针prev和后继指针next。下列代码创建了一个拥有4
个节点的双链表a：
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
则其头节点和尾结点数据域的值分别为：
A.2和4 B.0和8 C.8和0 D.3和-1
B
练 习
2.Python中可以使用二维列表来模拟双向链表，用包含三个元素的
列表来表示每一个节点，其中第1个元素存储数据，第二、三个元素
分别存储前驱指针prev和后继指针next；同时双向链表使用头指针
head指向第一个节点在列表中的索引。
下列代码创建了一个双向链表a:
a=[[2,2,5],[8,0,5],[0,-1,0],[1,-1,2],[5,5,-1],[3,0,-1]]
head=2
则该双向链表a的节点数量为：
A.3 B.4 C.5 D.6
A
3.有如下python程序段：
a=[[1,-1,1],[2,0,2],[3,1,3],[4,2,-1]]
head=0
while a[head][2]!=-1:
a[head][1],a[head][2]=a[head][2],a[head][1]
head=a[head][1]
a[head][1],a[head][2]=a[head][2],a[head][1]
则程序执行后，链表各节点数据值依次为：
C
A.1 2 3 4 B.1 3 2 4 C.4 3 2 1 D.4 2 3 1
例：廿四节气被列入农历，称为农历的一个重要部分。按照时间顺序，上半年主要
包括立春、雨水、惊蛰、春分、清明、谷雨和立夏这几个节气。小刚创建了一
个双向链表，每个节点存储一个节气名称，可是他不小心漏掉了清明这个节气。
编写程序，实现功能：将清明插入到链表的正确位置。请在划线处填入合适的
代码。
#输出链表a的所有节点
def display(a,head):
p=head
while a[p][2]!=-1:
print(a[p][0],end=“ ”)
p=a[p][2]
print(a[p][0])
#主函数部分
a=[“立春”,-1,1],[“雨水”,0,2],[“惊蛰”,1,3],[“春分”,2,4],[“谷雨”,
3,5],[“立夏”,4,-1]]
head=0
display(a,head)
#先找到春分，再将清明插入到春分后面
p=head
while p!=-1 and a[p][0]!=“春分”:
p=______
node=[“清明”,p,______]
a.append(node)
If a[p][2]!=-1:
a[a[p][2]][1]=len(a)-1
a[p][2]=_______
display(a,head)
a[p][2]
a[p][2]
len(a)-1
谢 谢