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

知识回顾 组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。 1 CHZX 2.2 链表 浙江省高中信息技术 选择性必修一 《数据与数据结构》 昌化中学 应彤鑫 2 链表的概念与特性 概念 特性 01 3 链表 是指将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 由数据区域和指针区域两部分构成。 链表的概念 lianbiao de gainian 保存数据元素 保存相邻结点的存储地址 一个链表的节点 4 链表的组成 单向链表中各个结点在内存中可以非顺序存储 每个结点使用指针指向其后继结点的存储地址 进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。 链表的概念 lianbiao de gainian 头 节 点：用于进入链表和边界判断 前驱节点：某个节点前面的相邻节点 后继节点：某个节点后面的相邻节点 尾 节 点：最后一个节点，指针指向空 5 链表的存储方式 头指针的作用 (1)链表的入口，只有通过头指针才能进入链表。 (2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。 链表的概念 lianbiao de gainian head (头指针) tail None 数据域 指针域 My_list 前驱节点 后继节点 6 链表的分类 链表的概念 lianbiao de gainian （1）单向链表： （2）双向链表： （3）循环链表： 7 链表的特性 同一链表中每个结点的结构均相同 每个节点的数据区域的数据类型相同，指针区域中的指针数量和功能是相同的。 每个链表必定有一个头指针，以实现对链表的引用和边界处理 链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。 对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。 链表占用的空间不固定 链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。 链表的特性 lianb