2.2 链表的概念、特性、基本操作 课件　2023—2024学年浙教版（2019）高中信息技术选修1

信息技术 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2 第二章 数组与链表 计算机中数据的存储模式分为顺序存储和非顺序存储，所有数据结构的存储也可以分为这两类，而作为常用数据结构中的数组与链表，就是这两种存储模式的典型代表,其他的数据结构都是在这两种数据结构的基础上构建的。 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 排队与插队 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 排队与插队 数组的缺点： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 链表是一种存储空间利用率高的数据结构，适用于数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 链表基本概念 整队前的位置和链接关系 链表结点结构 保存数据元素 保存相邻结点的存储地址 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 链表基本概念： 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 头指针（head）作用： 一是链表的入口，只有通过头指针才能进入链表 二是为循环链表设立一个边界，便于数据处理时的边界判断和处理 链表结点结构 保存数据元素 保存相邻结点的存储地址 吴坚 王林 黄刚 李丰 ^ head 前驱节点 后继节点 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 链表的基本概念 根据每个节点中指针的数量分为： 单向链表：只有一个指针用来指向其后继节点； 双向链表：两个指针分别指向其前驱节点和后继节点 循环链表： 第一个结点和最后一个结点使用指针链接， 这样就形成了循环链表。 next 吴坚 黄刚 王林 李丰 head next next next 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 链表基本概念 如何存储？ 单向链表中各个节点在内存中可以非顺序存储， 每个节点使用指针指向其后继节点的存储地址。 如何访问？ 进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾节点的指针指向为null，表示指向为空。 随意存储 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 吴坚 王林 黄刚 李丰 ^ head 在单项链表中： 头节点可以是单独的数据区域为空的节点； 也可以是将序列的第一个作为头节点。 两者头节点有何不同？ 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 链表的特性 （1）同一链表中每个结点的结构均相同 数据类型相同 指针数量和功能相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 head （3）链表占用的空间不固定 访问链表中的某一节点，只能从头指针开始，通过指针链接依次访问，不能像数组那样通过下标直接引用。 边界处理:循环链表，一轮访问的开始和结束都可以借助头指针指向位置来进行判断. 存储：相邻节点存储时不需要连续空间，充分利用内存的零散空间，提高利用率。 由于链表的存储空间由节点数决定，增加或减少节点都会改变链表占用的存储空间，因此链表占用的空间不固定。 选择性必修1 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2021 2.2.2 链表的基本操作 数据类型相同 指针数量和功能相同 本章中链表使用Python中的列表模拟实现，用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个节点的指针区域值为-1时表示指向为空，该节点为尾节点，此时空链表的判定可以使用更方便的方式进行。（本章中的链表实现采用不带头节点的结构） ※链表在实际应用时可以带头节点或不带头节点，在第一章中介绍链表时采用的都是带有头节点的结构，这样可以方便空链表的判断。 选择性必修1 2021 2021 2021 2021 2021 2021