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

(课件网) 2.2 链表 课前学习任务 结合数组的特性和基本操作，针对如下例子设计数组以组织和存储关键数据： ① 处理全班同学的信息，时常需要进行信息访问； ② 处理学校外来人员信息，进校时登记信息，出校时移除信息。 链表基本概念 链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 节点结构 数据区域 指针区域 保存数据元素 保存相邻节点的存储地址 某节点 后继节点 前驱节点 链表基本概念 根据节点中指针的数量可以分为: 单向链表： 双向链表： 循环链表： data next prev data next data next datan nextn ··· 链表的特性 ① 链表占用的空间不固定； ② 每个链表中一般要有一个头指针，以实现链表的引用和边界处理； ③ 同一链表中每个节点的结构均相同。 存储地址 数据区域 后继指针 0 “黄刚” 1 1 “李丰” -1 2 “王林” 0 3 “吴坚” 2 单链表存储结构 head 单链表示意图 吴坚 2 第一个节点 head 王林 0 第二个节点 黄刚 1 第三个节点 李丰 -1 第四个节点 （尾节点） 请同学们暂停视频，尝试并完成“学习任务单”中的“学习任务一”。 【学习任务一】认识链表 为了满足链表能在两个方向都能进行遍历的需求，请在图1为每个节点补充正确的前驱指针。 存储地址 数据区域 前驱指针 后继指针 0 “黄刚” 1 1 “李丰” -1 2 “王林” 0 3 “吴坚” -1 2 图1 双向链表存储结构图 head 单链表示意图 吴坚 2 第一个节点 地址3 head 王林 0 第二个节点 地址2 黄刚 1 第三个节点 地址0 李丰 -1 第四个节点 地址1 3 2 0 【小要求】与数组的相关操作进行比较，各自的操作效率谁优谁劣？为什么？ 链表的基本操作 链表创建 节点访问 节点插入 节点删除 链表的基本操作———链表创建 数据区域 后继指针 链表结构： “姓名+手机号” 头指针head：指向第一个节点 单向链表 校外人员进出登记：信息插入和删除 链表的基本操作———节点插入 data1 next1 data2 next2 data3 next3 修改新节点和前驱节点的指针 data1 next1 data3 next3 data2 -1 data3 next3 head 插入到第一个节点之前 插入尾节点之后 -1 next2 修改新节点指针和头指针 修改新节点和前驱节点的指针 插入到两个节点之间 ①“李彤”入校； 存储地址 数据区域 后继指针 0 “杜刚+1xx.” -1 1 “张强+1xx.” 0 head 2 “李彤+1xx.” -1 2 张强 0 head 杜刚 -1 李彤 -1 新节点 2 链表的基本操作———节点插入 ②“李丰”在“杜刚”之前入校； 存储地址 数据区域 后继指针 0 “杜刚+1xx.” 2 1 “张强+1xx.” 0 2 “李彤+1xx.” -1 head 3 “李丰+1xx.” 0 3 张强 0 head 杜刚 2 链表的基本操作———节点插入 李彤 -1 李丰 0 新节点 3 data1 next data2 next data3 next 删除中间节点 修改前驱节点的后继指针，让待删节点的前驱和后继直接相连 链表的基本操作———节点删除 data2 next data3 next data1 next data2 next 删除第一个节点 head 删除最后一个节点 请同学们暂停视频，尝试并完成“学习任务单”上“【学习任务二】链表基本操作”。 【学习任务二】链表基本操作 存储地址 数据区域 后继指针 0 “杜刚+1xx.” 2 1 “张强+1xx.” 3 2 “李彤+1xx.” -1 3 “李丰+1xx.” 0 （1）“杜刚”出校，请在如下绘制节点链接关系，并在上述存储结构图中进行相应修改： head 张强 3 head 杜刚 2 李彤 -1 李丰 0 2 2 【学习任务二】链表基本操作 存储地址 数据区域 后继指针 1 “张强+1xx.” 3 2 “李彤+1xx.” -1 3 “李丰+1xx.” 2 （2）“胡洁”在“张强”之前入校，请在如下修改节点链接关系，并在上述存储结构图中进行相应修改 head 张强 3 head 李彤 -1 李丰 2 4 “胡洁+1xx.” ... ...