浙教版（2019）高中信息技术选修一 2.2.1单向链表课件（22张PPT）

(共22张PPT)
2.2 链表
单向链表
什么是链表？
链表指的是将需要处理的数据对象以节点
的形式，通过指针串联在一起的一种数据
结构。
链表的表示？
Dui=[[“吴坚”，1],[“王林”，2],
[“黄刚”，3],[“李丰”，-1]]
节点
（由数据区域和指针区域两部分构成）
Dui=[[“吴坚”，1],[“王林”，2],[“黄刚”，3],[“李丰”，-1]]
Dui[0][0]=“吴坚” Dui[0][1]=1
Dui[1][0]=“王林” Dui[1][1]=2
.
.
.
Dui[3][1]=
-1
尾节点指针
想一想：如何访问链表？
head=0
头指针，指向第一个节点
链表的特性
（1）同一链表中每个节点的结构均相同
（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理
（3）链表占用的空间不固定
单向链表的基本操作
1.单向链表的创建
（1）Python中可以使用二维列表来模拟单向链表，用包含两个元素
的列表来表示每一个节点，其中第一个元素存储数据，第二个元素存
储指针（即后继节点在二维列表中的索引）。
（2）创建一个空链表linklist的代码如下：
linklist=[]
head=-1
（3）创建一个拥有2个节点的链表linklist的代码如下：
linklist=[[6,1],[8,-1]]
head=0
2.单向链表节点的访问
链表节点只能通过头指针（head）进行访问，其他节点通过节点间的指针
依次访问。可以设计如下自定义函数输出链表的所有节点：
Def display(a,head):
p=head
while a[p][1]!=-1:
print(a[p][0],end=“—>”)
p=a[p][1]
print(a[p][0])
3.单向链表节点的插入
链表节点的插入指的是根据新输入的实际数据形成节点，然后修改
新节点与其前驱节点的指针，将新节点插入到链表的正确位置。
①从头部插入新节点
next
data1
next
data2
next
data3
-1
head
单向链表从头部插入新节点
new data
next
data1
next
data3
data2
next
-1
head
代码实现
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
a.append([“new_data”,head])
head=len(a)-1
从中间或者尾部插入新节点该怎么实现呢？
②从中间插入新节点
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
P=0
a.append([“new_data”,a[p][1]])
a[p][1]=len(a)-1
③从尾部插入新节点
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
P=head
While a[p][1]!=-1
p=a[p][1]
a.append([“new_data”,a[p][1]])
a[p][1]=len(a)-1
4.单向链表节点的删除
删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。
data1
next
data2
next
data3
-1
head
data1
next
data2
next
head
data3
-1
单向链表删除头节点
代码实现
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
head=a[head][1]
data1
next
data2
next
data3
-1
head
data1
next
data2
next
data3
-1
head
×
×
>
data1
next
data2
next
data3
-1
head
data1
next
next
head
×
>
单向链表删除中间节点
代码实现
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
pre=0
p=a[pre][1]
a[pre][1]=a[p][1]
data1
next
data2
next
data3
-1
head
head
data1
next
data2
next
data3
-1
×
单向链表删除尾部节点
代码实现
a=[[“data1”,1],[“data2”,2],[“data3”,-1]]
head=0
pre=head
while a[a[pre][1]][1]!=-1
pre=a[pre][1]
a[pre][1]=-1
链表节点的删除，并没有将元素从列表中删除，
而仅仅是修改了节点指针域的值，通过将被删除
节点的前驱节点和其后继节点直接相连的方式实现。
尾节点可以直接删除，若删除了头节点，则需要修
改头指针。
删除节点小结：
练一练
1.使用python 的二维列表来模拟单向链表，如下代码创建了
一个拥有4个节点的链表a：
a=[[“hello”,1],[“china”,3],[“Olympics”,-1],
[“winter”,2]]
head=0
①a[1][1]的值为：
A.1 B.2 C.0 D.3
②依次输出各节点数据域的值，则输出内容为________________
__________________
D
hello
china
winter
Olympics
2.单向链表中插入新节点的过程如图所示。使用python的
二维列表来模拟单向链表，已知插入节点前列表a=[[“红”,1]
,[“橙”,2],[“绿”,3],[“青”,-1]]，则在删除节点“橙”之
后，列表a的值为
[[“红”,1],[“绿”,3],[“青”,-1]]
[[“红”,1],[“绿”,2],[“青”,-1]]
[[“红”,1],[“橙”,2],[“绿”,3],[“青”,-1]]
[[“红”,2],[“橙”,2],[“绿”,3],[“青”,-1]]
D
3.在下列列表中将新节点插入到data2和data3中间，则下列步骤
不需要的是：
data1
next
data2
next
data3
next
data4
next
new data
next
A.断开data2与data3的连接
B.断开data3与data4的连接
C.使new data的指针指向data3
D.使data2的指针指向new data
B
4.有如下python程序段，表示一个链表及操作：
a=[[5,-1],[9,4],[7,3],[2,1],[6,0]]
head=2
p=head
b=[ ]
While a[p][1]!=-1:
b.append(a[p][0])
p=a[p][1]
b.append(a[p][0])
print(b)
程序执行后，输出的结果为：
A.[7,2,9,6,5,5] B.[5,9,7,2,6] C.[7,2,9,6,5] D.[2,9,6]
C
谢 谢