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

2.2 链表 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。 杭州 上海 苏州 南京 济南 石家庄 北京 青岛 导入 小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；用数组来实现其更改过程。 杭州 上海 苏州 南京 济南 石家庄 北京 青岛 数组的缺点： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。 链表基本概念 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。 链表基本概念： 链表节点结构 保存数据元素 保存相邻节点的存储地址 头指针（head）作用： 一是链表的入口，只有通过头指针才能进入链表 二是为循环链表设立一个边界，便于数据处理时的边界判断和处理 链表基本概念 根据每个节点中指针的数量分为： 单向链表： 双向链表： 循环链表： 第一个节点和最后一个节点使用指针链接，这样就形成了循环链表。 next 吴坚 黄刚 王林 李丰 head next next next 链表基本概念 单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。 链表基本概念 链表的特性 （1）同一链表中每个节点的结构均相同 数据类型相同 指针数量和功能相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 head （3）链表占用的空间不固定 练习 C 链表的基本操作 链表的基本操作有空链表的创建、节点访问、节点的插入和删除。 Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。 用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。 a