浙教版（2019） 高中信息技术 选修1 第2章第2节 链表 课件（共26张PPT）

(共26张PPT)
2.2 链表（第二课时）
单击此处添加副标题
链表的创建
可以使用如下Python代码创建一个空链表：
head = -1
#头指针指向-1，表示链表为空
#创建一个空链表Item
头指针变量head：存储链表第一个节点在列表中的索引
Item = [ ]
链表的创建
节点
列表模拟单向链表的节点：
data next
根据实际问题的特点规划好节点的数据区域和指针区域
列表
[data,next]
Item.append([data,next])
通过列表的append( )函数将节点保存到列表中
#索引：len(Item)-1
单向链表的创建
Item = [ [“张强”, ] , [“杜刚”, ] ]
head = _______
#存储第一个节点在列表中的索引
1
-1
索引0
索引1
张强
head
杜刚
0
单向链表节点的访问
链表中访问指定节点只能通过头指针指向的第一个节点开始访问，其他节点通过节点间的指针依次访问。
data1
data2
data3
head
data4
访问变量
访问变量
访问变量
访问变量
访问变量== -1 ：访问完最后一个节点
访问变量：当前访问节点在列表中的索引
Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]，
[“李彤”, -1 ] , [“李丰”, 0 ]]
head = 1
#依次访问并输出链表各节点数据
p=head #访问变量，表示当前访问节点的索引
print(Item[p][0],end=” ”) #输出当前节点数据
p=Item[p][1] #访问变量迭代更新为后继的
#按照p的功能：
当前访问节点的数据区域为：
当前访问节点的后继指针为：
Item[p][0]
Item[p][1]
Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]，
[“李彤”, -1 ] , [“李丰”, 0 ]]
head = 1
#依次访问并输出链表各节点数据
p=head #访问变量，表示当前访问节点的索引
#按照p的功能：
当前访问节点的数据区域为：
当前访问节点的后继指针为：
Item[p][0]
while p!=-1:
print(Item[p][0],end=” ”) #输出当前节点数据
p=Item[p][1] #访问变量迭代更新为后继的
Item[p][1]
杜强 李丰 杜刚 李彤
Item = [ [“杜刚”, 2 ] , [“杜强”, 3 ]，
[“李彤”, -1 ] , [“李丰”, 0 ]]
head = 1
#依次访问并输出链表各节点数据
p=head #访问变量，表示当前访问节点的索引
#按照p的功能：
当前访问节点的数据区域为：
当前访问节点的后继指针为：
Item[p][1]
while p!=-1 :
print(Item[p][0],end=” ”) #输出当前节点数据
p=Item[p][1] #访问变量迭代更新为后继的
p!= -1 and Item[p][0]!=”杜刚” ：
杜强 李丰
Item[p][0]
单向链表节点的插入
data1 next1
data3 next3
head
data1 next1
data2 next2
data3 next3
插入到链表最前面
data2 -1
data3 next3
-1
next2
插入到相邻两个节点之间
插入到链表最后面
单向链表节点的插入
data1 next1
data3 next3
head
插入到链表最前面
#新节点
Item[r][1] = head
#头指针
head = r
已知链表的第一个节点的索引保存在head变量上，新节点在列表中的索引是r
索引r
单向链表节点的插入
插入到链表相邻两个节点之间
data1 next1
data2 next2
data3 next3
某相邻两个节点在列表中索引分别为pre和p，在其之间插入一个新节点；新节点在列表中索引为r
#新节点
Item[r][1] = p
#前驱节点
Item[pre][1] = r
索引pre
索引r
索引p
单向链表节点的插入
插入到链表最后面
#新节点
Item[r][1] = -1
#前驱节点
Item[p][1] = r
已知链表的最后一个节点的索引为p，新节点在列表中的索引是r
data2 -1
data3 -1
-1
索引r
r
单向链表节点的删除
data1 next
data2 next
data3 next
data2 next
data3 -1
data1 next
data2 next
删除第一个节点
head
删除中间节点
删除最后一个节点
单向链表节点的删除
变量head保存了第一个节点在列表中索引
#头指针
head = Item [head] [1]
删除第一个节点
data1 next
data2 next
head
单向链表节点的删除
data1 next
data2 next
data3 next
待删除节点在列表中索引为p，其前驱节点在列表列表中索引为pre
索引pre
索引p
#前驱节点
Item[pre][1] = Item [p] [1]
删除中间节点
单向链表节点的删除
待删除节点的前驱节点在列表中索引为pre
#前驱节点
Item[pre][1] = -1
删除最后一个节点
data2 next
data3 -1
索引pre
-1
请同学们暂停视频，回顾单向链表基本操作的实现，尝试并完成“学习任务单”：一、体验系统的基本功能。
简易外来人员进出校园登记系统
入校登记
出校移除
按进校时间查看还在校内的外来人员
简易外来人员进出校园登记系统基本功能架构图
节点规划
姓名+手机号 后继指针
Item = [ ]
head = -1
（1）创建空链表，链表名为Item，头指针为head
节点实现:
[姓名+手机号，后继指针]
（2）杜刚、张强、李彤三人依次进校
将新节点插入到链表末尾
姓名+手机号 后继指针
或者len(Item)-1
[data1,-1]
head=0
节点实现:
[姓名+手机号，后继指针]
（2）杜刚、张强、李彤三人依次进校
将新节点插入到链表末尾
姓名+手机号 后继指针
或len(Item)-1
Item[0][1]=1
node=[data2,-1] #在链表末尾插入节点，所以新节点后继指针为-1
Item.append(node)#将新节点保存到列表中，索引为1
（2）杜刚、张强、李彤三人依次进校
将新节点插入到链表末尾
len(Item)-1
或len(Item)-1
Item[1][1]=2
node=[data3,-1] #在链表末尾插入节点，所以新节点后继指针为-1
Item.append(node)#将新节点保存到列表中，索引为2
单链表中删除指定节点节点
（3）李彤、杜刚依次出校
访问到该节点的前驱节点→删除节点
访问到李彤所在节点时结束访问：
·p变量保存了待删节点的索引
·pre保存了前驱节点的索引
if p==head:#删除第一个节点
head=Item[p][1]
elif Item[p][1]==-1:#删除最后一个节点
Item[pre][1]=-1
else:#删除中间节点
Item[pre][1]=Item[p][1]
（3）李彤、杜刚依次出校
（4）按进校时间查看在校内人员
遍历单向链表
课堂小结
用列表模拟单向链表的基本操作
应用链表编程解决实际问题
【巩固练习】完成课后作业练习
【拓展练习】回顾课堂上的实践过程和程序，尝试在资源包中“简易外来人员进出登记系统.py”文件继续完善项目。
课后作业