《数据结构[Python 语言描述]》 教案 第4课 线性表（2.3）.pdf

课题第4课线性表（2.3）

课时2课时（90min）

知识目标：

（1）掌握单链表和双链表的结构特点及其基本操作的实现

（2）理解循环链表的特点

教学目标技能目标：

能使用线性表解决实际问题

素质目标：

增强主动思考、积极寻求问题解决方法的意识

教学重点：单链表和双链表的结构特点及其基本操作、循环链表的特点

教学重难点

教学难点：单链表和双链表的结构特点及其基本操作

教学方法问答法、讨论法、讲授法、实践法

教学用具电脑、投影仪、多媒体课件、教材

教学过程主要教学内容及步骤

【教师】使APP进行签到

考勤

【学生】班干部报请假人员及原因

【教师】提出以下问题：

问题导入

如何理解链式存储？

（5min）

【学生】思考、举手回答

【教师】通过学生的回答引入要讲的知识，介绍单链表和双链表的结构特点及其基本操作、循环链表

的特点

2.3线性表的链式存储——链表

线性表的链式存储是指，用一组地址任意的存储单元依次存储线性表中的各个数据元素，这些存储

单元可以是连续的，也可以是不连续的。采用链式存储结构的线性表称为链表。

链表又可以分为单链表、双链表和循环链表等。

2.3.1单链表

1．单链表的结构特点

在线性表的链式存储结构中，为了表示每个元素与其后继元素之间的逻辑关系，除了需要存储元素

本身的数据信息外，还要存储一个指示其后继元素地址的信息，这两部分信息共同构成了一个数据元素

的存储结构，称为结点（node）。

传授新知

datanext

其中，存储元素本身数据信息的部分称为数据域（data），存储其后继元素地址信息的部分称为指针

域（next）。

单链表（也称线性链表）是指将n个数据元素通过其对应结点的指针域按其逻辑关系链接成的链表，

其中每个结点只包含一个数据域和一个指针域。

heada0a1…an-1^

其中，head称为头指针，用于指向单链表的第一个结点（也称首元结点）。由于单链表的最后一个

结点没有后继元素，所以其指针域为“空”（None），用符号“^”表示。1

【提示】

在Python中并不存在指针的概念，此处的指针属性实际上存放的是后继结点的引用，但为了表述

方便仍然采用“指针”一词。

✈【教师】讲解实例2-4（详见教材）

在单链表中，逻辑上相邻的两个数据元素，其存储的物理位置不一定相邻，每个数据元素的存储地

址都存放在其前驱结点的指针域中。要想取得第i个结点，必须从头指针出发按照顺序依次在单链表中

寻找，因此，线性表的链式存储结构是一种顺序存取的存储结构。

为了操作方便，通常在单链表的第一个结点之前增加一个头结点。单链表的头指针指向头结点，头

结点的数据域可以不存储任何数据信息，也可以存储与线性表中数据元素类型相同的其他附加信息。头

结点的指针域存储第一个结点的地址信息。

……