2.2.1 链表的概念、特性、基本操作 课件-2021-2022学年高中信息技术浙教版（2019）选修1 数据 与数据结构

选择性必修1《数据与数据结构》 第二章 数组与链表 2.2.1链表的概念、特性、基本操作 1 情境导入——排队与插队 情境导入——排队与插队 数组的缺点： 插入和删除元素操作需要移动大量的元素 频繁增、删数据导致数据规模不稳，形成存储空间“碎片” 需要限定最大空间，造成资源浪费 链表基本概念 整队前的位置和链接关系 链表指的是将需要处理的数据对象以结点的形式，通过指针串联在一起的一种数据结构。 链表结点结构 保存数据元素 保存相邻结点的存储地址 链表基本概念： 头指针（head）作用： 一是链表的入口，只有通过头指针才能进入链表 二是为循环链表设立一个边界，便于数据处理时的边界判断和处理 链表基本概念 链表的基本概念 根据每个结点中指针的数量分为： 单向链表： 双向链表： 循环链表： 第一个结点和最后一个结点使用指针链接，这样就形成了循环链表。 next 吴坚 黄刚 王林 李丰 head next next next 链表基本概念 单向链表中各个结点在内存中可以随意存储，每个结点使用指针指向其后继结点的存储地址。进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。 链表的特性 （1）同一链表中每个结点的结构均相同 数据类型相同 指针数量和功能相同 （2）每个链表必定有一个头指针，以实现对链表的引用和边界处理 head （3）链表占用的空间不固定 链表的基本操作——链表的创建 Item=[] Head=-1 其中head值为–1，表示头指针指向为空，该链表为空链表。 创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。 链表的基本操作——链表的访问 链表只能通过头指针（head）进行访问，其他结点通过结点间的指针依次访问。如图，当想访问单向链表中data3所在的结点时，需通过头指针进入链表，再分别按照各个结点的指针指向经过data1和data2所在结点，最后通过data2所在结点的指针才能访问 data3所在的结点。 链表的基本操作——链表结点的插入与删除 New data next data1 next data2