2.2 链表 课件(共11张PPT)浙教版（2019）高中信息技术选修1 数据与数据结构

(共11张PPT)
第二章 数组和链表
选修一《数据与数据结构》
2.2 链表的概念、特性与基本操作
01
Part
什么是链表？
链表的节点结构
单向链表、双向链表和循环链表
链表在内存当中的存储
链表的特性
链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
链表是什么？
太抽象了，无法理解
货车
火车
顾客新增加了采购量超出了货车的承载量？
只能选择换一个承载量更大的货车来运输
链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
链表是什么？
数据对象
节点
指针
链表是什么？
1.链表的节点结构
数据区域
指针区域
保存数据区域
保存相邻节点的
存储地址
head
前驱节点
后继节点
头指针（head）的作用
一是链表的入口，用户只有通过头指针才能进入链表
二是为循环链表设立一个边界，便于数据处理时的边界判断与处理
A点宝藏
B点地址
B点宝藏
None
链表是什么？
2.单向链表、双向链表和循环链表
None
单向链表
None
None
双向链表
循环链表
链表是什么？
3.链表在内存当中的存储
数组
有16字节的货物需要存储
4字节
又新增了4字节的存储需求
链表是什么？
3.链表在内存当中的存储
数组
链表
有16字节的货物需要存储
又新增了4字节的存储需求
4字节
链表是什么？
3.链表在内存当中的存储
数组
链表
链表占用的空间不固定
有16字节的货物需要存储
又新增了4字节的存储需求
4字节
链表是什么？
4.链表的特性
a.链表占用的空间不固定
链表
链表的节点间通过指针相连，相邻节点存储时不需要连续空间，充分利用了内存的零散空间，提高了存储空间利用率。
b.每个链表必定有一个头指针（head），以实现对链表的引用和边界处理
head
循环链表
head
c.同一链表中每个节点的结构均相同
数据区域
指针区域
数据类型相同
数量和功能相同
一是链表的入口，用户只有通过头指针才能进入链表
二是为循环链表设立一个边界，便于数据处理时的边界判断与处理
链表要怎么用？
head
小组合作讨论：
有关链表的创建、访问、插入和删除操作要怎么实现呢？