2-2链表 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第二章 数组与链表 选修1《数据与数据结构》 2.1 链表 学习目标 链表 链表的概念与特性 链表的基本操作 链表的概念和特性 链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 ·链表的概念 链表 ·节点结构 data(数据域)：用来保存实际需要处理的数据元素。 next(指针域)：用来保存该节点相邻节点的存储地址。 data next 数据域 指针域 一个链表的节点 链表的概念和特性 链表内存存放方式： ·链表的存储方式 链表 head (头指针) tail None 数据域 指针域 My_list 前驱节点 后续节点 头指针(head)：(1)链表的入口，只有通过头指针才能进入链表。 (2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。 链表的概念和特性 ·链表的种类 链表 （1）单向链表： （2）双向链表： （3）循环链表： 链表的概念和特性 （1）同一链表中的每个节点的结构均相同 每个节点的数据区域的数据类型相同，指针区域中的指针数量和功能是相同的。 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。 对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。 （3）链表占用的空间不固定 链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。 ·链表的特性 链表 链表的概念和特性 ·链表的创建 ·链表的基本操作 链表 （1）使用列表模拟链表 例如：a = [ [ 99, 1 ],[ 95, 2 ],[ 88, -1] ] 列表a中有3个元素： [ 99, 1 ] 、