《数据结构》课程教学资源（教案设计）02 链表

编号：003 课程 章节 课程讲 数据结构 第二章线性表 45分钟 名称 名称 2.3线性表的链接存储结构及实现授学时 学习要求 知识点 熟练 识记理解 掌握 应用 分析 综合 课堂 线性表的链式存储 √ 教学 基于顺序表和单链表基本操作的实现 态度 积极主动学习 目的 熟练掌握线性表的两种存储结构的表示和其上基本操作的实现； 会用算法的时间复杂度和空间复杂分析方法分析这些操作： 能力 学会用线性这种数据结构解决实际问题并对编写的算法复杂性进行分 析 教学内容（教学过程设计） 教学安排 复习与新课导人 5分钟 复习： 顺序表的存储与操作 5分钟 由顺序表的缺点引出链接存储结构，导入新课 根据一个实例给出线性表链接存储的实际内存状态，复习C语言中指 25分钟 的有关知识，抽象出单链表的存储示意图 2.3线性表的链接存储结构及实现 给出单链表的存储结构定义及C语言描述 区分指针变量和结点变量，说明头指针、尾标志和头结点 给出单链表的按位查找算法，总结单链表算法的设计模式 设计单链表的插入算法，分析时间性能 5分钟 比较带头结点和不带头结点的单链表上的插入操作 给出单链表的册别除算法，注意分析边果情况 给出单链表建立算法中的头插法和尾插法 5分钟 提出问题：如何在连续存储区实现链接存储？引出静态链表 给出静态链表的定义，总结静态链表存储结构的优缺点 通过图示理解静态链表的插入和删别除操作的执行过程

编号：003 课程 名称 数据结构 章节 名称 第二章 线性表 2.3 线性表的链接存储结构及实现 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 线性表的链式存储 √ √ √ 基于顺序表和单链表基本操作的实现 √ √ √ √ 态度 积极主动学习 能力 ➢ 熟练掌握线性表的两种存储结构的表示和其上基本操作的实现； ➢ 会用算法的时间复杂度和空间复杂分析方法分析这些操作； ➢ 学会用线性这种数据结构解决实际问题并对编写的算法复杂性进行分 析 教学内容（教学过程设计） 教学安排 复习与新课导入 复习： 顺序表的存储与操作 ↓ 由顺序表的缺点引出链接存储结构，导入新课。 根据一个实例给出线性表链接存储的实际内存状态，复习 C 语言中指针 的有关知识，抽象出单链表的存储示意图 ↓ 2．3 线性表的链接存储结构及实现 给出单链表的存储结构定义及 C 语言描述 区分指针变量和结点变量，说明头指针、尾标志和头结点 给出单链表的按位查找算法，总结单链表算法的设计模式 设计单链表的插入算法，分析时间性能 比较带头结点和不带头结点的单链表上的插入操作 给出单链表的删除算法，注意分析边界情况 给出单链表建立算法中的头插法和尾插法 ↓ 提出问题：如何在连续存储区实现链接存储？引出静态链表 ↓ 给出静态链表的定义，总结静态链表存储结构的优缺点 通过图示理解静态链表的插入和删除操作的执行过程 5 分钟 5 分钟 25 分钟 5 分钟 5 分钟

提出问邀：将数组和指针结合起来存储线性表会怎样？引出间接寻址 通过图示理解间接寻址存储结构上如何实现插入和删除操作，并与顺序 表的插入和别除操作做比较 教学提示： >~熟练使用指针是学好单链表的基本前提，首先需要复习指针的有关内容 在精讲单链表查找算法的基础上，总结单链表算法的设计模式 > 单链表算法设计的关键是多练 存储结构的设计是个很灵活的过程，本讲的重点在于种存储结构的设计 思想，要把灵活的思想讲出来 重点： （1)顺序存储结构和链式存储结构的基本思想 (2)基于顺序表和单链表基本操作的实现； 重点 难点： 与 （1)线性表的抽象数据类型定义； 难点 （2)基于单链表的算法设计，尤其是要求算法满足一定的时间性能和空间性能 对策 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目—提出问题，引导学生 积极参与一尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 方法 教学方法：导入，配合图形、实例讲解，提问、讨论 与 手段 教学手段：PPT课件，板书，动画演示 作些： (1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使 用原来两个链表的存储空间，不另外占用其它的存储空间。表中不允许有重复的数 据。 作业 (2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表 及 仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的 数据。 (3)已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法 盗源 求出A与B的交集，并存放于A链表中。 （4)已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法 求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的 集合)，并以同样的形式存储，同时返回该集合的元素个数。 课后导读：

↓ 提出问题：将数组和指针结合起来存储线性表会怎样？引出间接寻址 ↓ 通过图示理解间接寻址存储结构上如何实现插入和删除操作，并与顺序 表的插入和删除操作做比较 教学提示： ➢ 熟练使用指针是学好单链表的基本前提，首先需要复习指针的有关内容 ➢ 在精讲单链表查找算法的基础上，总结单链表算法的设计模式 ➢ 单链表算法设计的关键是多练 ➢ 存储结构的设计是个很灵活的过程，本讲的重点在于种存储结构的设计 思想，要把灵活的思想讲出来 重点 与 难点 对策 重点： （1）顺序存储结构和链式存储结构的基本思想； （2）基于顺序表和单链表基本操作的实现； 难点： （1）线性表的抽象数据类型定义； （2）基于单链表的算法设计，尤其是要求算法满足一定的时间性能和空间性能； 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使 用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数 据。 （2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表 仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的 数据。 （3）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法 求出 A 与 B 的交集，并存放于 A 链表中。 （4）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法 求出两个集合 A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的 集合），并以同样的形式存储，同时返回该集合的元素个数。 课后导读：

关于线性表的定义有二元组、三元组、五元组，请参阅相关资料 顺序表、单链表的实现方法在种资料中不尽相同，请参阅相关内容 线性表的间接寻址存储结构在各教材中的介绍都较少。 教学 后记

➢ 关于线性表的定义有二元组、三元组、五元组，请参阅相关资料 ➢ 顺序表、单链表的实现方法在种资料中不尽相同，请参阅相关内容 ➢ 线性表的间接寻址存储结构在各教材中的介绍都较少。 教 学 后记