2.2 链表课件-2024-2025学年浙教版（2019）高中信息技术选修一

链表（第一课时） 1 项目引入 在高铁站的大屏幕、在12306 APP中，会实时显示列车的各种数据，方便人们出行安排。这背后是少不了计算机内程序对数据的处理。编写程序，根据现实列车的运行情况（如：增开、停运、晚点等），实时调整并按到站时间升序显示最新的列车到站信息（如右图）。 2 抽象关键要素 在高铁站的大屏幕里、在12306 APP中，会实时显示各车次的到站，方便人们出行安排。这背后少不了计算机程序对数据的处理。请编写程序，根据现实列车的运行情况（如：增开、停运、晚点等），实时调整并按到站时间升序显示最新的列车到站信息（如图）。 1.关键数据有哪些？ 2.用什么存储模式来存储这些数据， 即不影响其它数据的存储， 又能高效完成局部数据的操作？ 车次编号、到站时间 数组？ 链表 3 链表的概念与特性 4 链表的概念 ·将需要处理的数据对象以节点形式，通过指针串联在一起的一种数据结构。 例如：数组中的指针 i=0 while i<=3: print(a[i]) i=i+1 指针i指向某元素，通过a[i]取得该元素的值 数组a： 指 针：用来指示一个数据存储地址的变量。 在链表中，指针用来指示一个节点的存储地址 i 指针i指向后一个元素 5 链表的概念 ·将需要处理的数据对象以节点形式，通过指针串联在一起的一种数据结构。 节 点：即数据元素，是数据的基本单元， 一个节点可以由若干个数据项组成。 数据区域 指针区域 相邻节点(前驱节点/后继节点)在列表中的地址 存储实际需要 处理的数据 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 data=[ [“张”,3 ],[“李”,0 ],[“王”,-1 ],[“郑”,2 ]] head=1 head 6 链表的概念 【写一写】若右图节点存储在列表data中， 写出data的值和头指针的值。 data= head= [ [“张”,88,2 ],[“李”,75,-1 ],[“王”,80,1 ],[“郑”,95,0 ]] “张” 2 88 0 “李” -1 75 “王” 1 80 “郑” 0 95 1 2 3 【画一画】用箭头将右图的节点串联起来。 3 head 7 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 1 【说一说】将尾节点的指针 改为1，得到什么链表？ 循环链表 【读一读】分别以head1为入口顺着 红色箭头、以head2为入口顺着绿色 箭头，读一读链表的数据序列？ “李”“张”“郑” “王” “王”“郑”“张”“李” 双向链表 head “张” 1 3 0 “李” -1 0 “王” 3 -1 “郑” 0 2 1 2 3 head1 head2 8 1. 同一链表中每个节点的结构均相同 链表的特性 【画一画】存储每位同学姓名、身高、体重的链表，画出节点结构。 如：["张",175,68,3] 如：["张",175,68,1,3] 姓名 身高 指针 体重 单向链表的节点结构 姓名 身高 指针1 体重 指针2 双向链表的节点结构 9 2.每个链表必定有一个头指针 （链表入口、循环链表的边界处理） “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 1 head 链表的特性 10 链表的特性 3. 链表占用的空间不固定 （不需要连续空间，按需使用空间， 提高存储空间利用率） head = head+1 × head = data[head][1] √ q = head √ 11 1.数组元素的数据类型相同 3.存储空间固定不变 2.通过数组名和下标对数组 元素的值进行访问 数组特性 链表特性 1. 每个节点的结构相同 3. 链表占用的空间不固定 （不需要连续空间） 2. 必有一个头指针 （ 作为链表入口和边界处理） 12 【连一连】 1.在创建时就分配好固定大小的、连续的存储空间。 3.客户在银行办理业务时，需要输入个人身份证号进行排队，叫号软件则根据客户输入信息的先后按次序广播叫号。在叫号软件中存储排队客户的个人信息，采用哪种数据结构更合适？ 2.存储空间不固定，可根据实际需要随时增、删数据。 4.新高一开展军训前，学校收集了每位学生的身高、鞋码数据，小明编写程序来统计各码数的服装和鞋子的采购数量。存储身高、鞋码数据采用哪种数据结构更合适？ 数组 链表 13 链表的基本操作 14 链表的操作——创建链表 【写一写】 1. 创建一个名为data的空链表： data=[ ] head=-1 思考：什么情况下，头指针head值为 -1 ？ 创建空链表时； 链表里所有节点被删除时。 15 链表的操作—访问节点 链表名为data，head值为1， 如何通过指针q访问链中所有节点并输出？请描述算法步骤，写出代码。 1. 让q指向头节点 head “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 q=head ① 输出q指向节点的数据 print(data[q][0]) ② q指向其后继节点 q=data[q][1] 2. 若q未走完链表，则 while q!=-1： q指针：顺藤摸瓜 各节点的指针域 q 16 链表的操作——节点插入 在p指向的“张”与q指向的“郑”之间插入“刘”节点，请描述算法步骤，写出代码。 1. 在列表末尾追加存储新节点，并将其指针 指向“郑”节点（“郑”节点地址已存储在q中） “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 data.append([“刘”, q ]) data[p][1] = len(data)-1 2. 将“张”节点的指针指向新节点“刘”（“刘”节点的地址为len(data)-1 ） “刘” 3 4 4 q p head 17 【写一写】在尾节点（q指向的“王”节点）之后插入新节点“刘”，请写出语句。 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 “刘” -1 . 4 1. 在列表末尾追加存储新节点， 设置其指针域为-1： data.append([“刘”, -1 ]) data[q][1] = len(data)-1 2. 设置q节点的指针指向新节点 4 q head 18 【写一写】在头节点（head指向“李”节点）之前插入新节点“刘”，请写出语句。 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 “刘” 1 . 4 1. 在列表末尾追加存储新节点，并将其指针 指向头节点： data.append([“刘”, head ]) head = len(data)-1 2. 还需要修改什么？ head指向新的头节点（“刘”节点） head 19 链表的操作——删除节点 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 2 删除q指向的节点（p指向q的前驱节点）， 请描述算法步骤，写出代码。 1. 将p节点的指针指向q节点的后继节点 即“王”节点。 data[p][1]=data[q][1] （必要时） 2. q指向其后继节点，保持与p一前一后的关系。 q=data[q][1] q p head 20 “张” 3 0 “李” 0 “王” -1 “郑” 2 1 2 3 1. 删除头节点： head=data[head][1] 2. 删除q指向的尾节点（p指向q的前驱节点）： data[p][1]=-1 【写一写】 -1 q p head 21 数组更适用于： 链表更适用于： 数据规模事先不确定，在解决问题过程中需要频繁增、删数据元素（节点）的情况 数据规模可预测，在解决 问题过程中数据规模稳定 的情况 例如：存储高一年级全体学生的身高、鞋码数据，用于统计采购数量。 例如：由于特殊情况，列车需要增开、停运或晚点处理。 22 项目的数据抽象 在高铁站的购票厅、候车厅的大屏幕里，在12306 APP中，会实时显示各车次的信息，方便人们出行安排。这背后是少不了计算机内程序对数据的处理。编写程序，根据现实列车的运行情况（如：增开、停运、晚点等），实时调整并按到站时间升序显示最新的列车到站信息（如图）。 用链表来存储列车信息，节点结构为： [车次编号,到站时间,指针域] 如： LS=[['G0108', '07:00', 1], ['G7578', '07:25', 2], ['D1000', '07:40', 3], ['G2002', '08:10', 4], ['G5008', '08:35', 5], ['D0500', '09:00', 6], ['D0088', '09:20', -1]] head=0 23 项目任务分解 项目驱动任务1——增开列车 项目驱动任务2——停运列车 项目驱动任务3——列车晚点 24 任务1：增开列车的算法描述： 1. 输入增开列车的车次编号、到站时间； 2. q指向头节点； 3. 如果q非-1，且q指向节点的到站时间早于增开列车 的到站时间，则转到4，否则转到5； 4. q0指向q节点，q指向其后继节点，转到3； 5. 将新节点追加到LS，设置指针域指向q节点 6. 如果q指向头节点，则： head指向新节点 否则： q0节点的指针域指向新节点 7.输出最新时刻表，结束算法 输入新车次数据 查找新车次的插入位置（按到站时间升序） 在链表中插入 新节点 25 增开列车的代码： train=input("输入增开的车次：") arrive=input("输入到站时间：") q=head while q!=-1 and LS[q][1]<arrive: q0=q q=LS[q][2] LS.append([train,arrive,q]) if q==head: head=len(LS)-1 else: LS[q0][2]=len(LS)-1 show(LS,head) #输出最新列车时刻表 def show(link,head): print("---最新列车时刻表---") print("车次" ," 到站时间 ") q=head while q!=-1: print(link[q][0],link[q][1]) q=link[q][2] 26 任务2：停运列车的算法描述： 1. 输入停运列车的车次编号； 2. q指向头节点； 3. 如果q非-1，且q指向节点不是停运列车，则转到4， 否则转到5； 4. q0指向q节点，q指向其后继节点，转到3； 5. 如果q指向头节点，则： head指向其后继节点 否则： q0节点的指针域指向q节点的后继节点 6.输出最新时刻表，结束算法 输入停运列车 编号 查找停运车次 所在节点 删除停运车次 所在节点 27 停运列车的代码： train=input("输入停运的车次：") q=head while q!=-1 and LS[q][0]!=train: q0=q q=LS[q][2] if q==head: head=LS[head][2] else: LS[q0][2]=LS[q][2] show(LS,head) #输出最新列车时刻表 def show(link,head): print("---最新列车时刻表---") print("车次" ," 到站时间 ") q=head while q!=-1: print(link[q][0],link[q][1]) q=link[q][2] 28 任务3：列车晚点的算法描述： 1. 输入晚点列车的车次编号train、晚点到站时间arrive； 2. t指向头节点； 3. 如果t非-1，且t指向节点不是晚点列车，则转到4， 否则转到5； 4. t0指向t节点，t指向其后继节点，转到3； 5.修改到站时间LS[t][1]←arrive 6.查找晚点列车的新插入位置q（q0指向q的前驱节点） 7. 若新插入位置并非原位置，则： 在原位置删除t节点 在新位置插入t节点 8.输出最新时刻表，结束算法 输入晚点列车 编号、时间 查找晚点车次， 修改到站时间 查找晚点车次 新插入位置 更新晚点车次 节点的位置 29 列车晚点的代码： train=input("输入晚点的车次：") arrive=input("输入到站时间：") t=head while LS[t][0]!=train: t0=t;t=LS[t][2] LS[t][1]=arrive q0=t;q=LS[t][2] while q!=-1 and LS[t][1]>LS[q][1]: q0=q; q=LS[q][2] if t!=q0: if t!=head: LS[t0][2]=LS[t][2] else: head=LS[t][2] LS[t][2]=q ; LS[q0][2]=t show(LS,head) def show(link,head): print("---最新列车时刻表---") print("车次" ," 到站时间 ") q=head while q!=-1: print(link[q][0],link[q][1]) q=link[q][2] 30 小结 31 同学们，再见！ 32 $$