《数据结构》教案.doc

1、1 课 程 简 介 人们在运用程序设计语言编写程序的过程中发现所有的数据都可以抽象为三种结构，而 对这些数据的所有操作都可以转化为对这三种数据的几种基本操作，而大多数的程序设计技 巧都可以抽象为一些最基本的算法。于是人们逐步发展了一门称为数据结构（或数据结构与 算法）的计算机科学，它广泛应用于计算机领域。 数据结构是信息与计算专业的核心基础课程之一。数据是计算机处理的对象，本课程研 究的数据是非数值性、结构性的数据。学习本课程要求掌握各种主要数据结构的特点、计算 机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有 一定程度的了解和掌握。通过本课程的学习，使学生透彻

2、地理解各种数据对象的特点，学会 数据的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。本课程主要包括如 下三个方面的内容： 1基本数据结构： 线性表、栈、队列、串、数组和广义表，掌握它们的特点、表示和 实现，对静态结构要求非常熟练的编程上机实现，对动态结构要求逐步熟悉链表的表示，通 过模仿实验教程中的例子，掌握编程技巧。强调类 C 语言的书写规范，特别注意参数的区 别，输入输出的方式和错误处理方式，以及抽象数据类型的表示和实现。能熟练完成以下的 应用：多项式的计算、语法检查、回朔算法、递归算法、表达式求值、离散事件模拟、文字 的编辑和稀疏矩阵进行矩阵运算采用的处理方法。 2复杂数据结

3、构： 树、二叉树、图。掌握它们的定义和特点、表示和实现，特别注意 与基本数据结构的区别，掌握各种遍历的递归和非递归算法，能熟练完成以下的应用：最优 树、Huffman 编码、拓扑排序、关键路径和最短路径问题。 3数据结构的应用： 查找和内部排序。熟练掌握静态查找表的查找方法和实现，了解 哈希表的构造和查找方法。掌握各种内部排序方法的基本思想、算法特点、排序过程以及它 们的时间复杂度分析。 2 数据结构教学大纲 课程名称：数据结构 课程编号：014100028 适用专业：计算机、信息管理 总学时数：60 学分数： 4 一、课程的性质、目的与任务 数据结构是计算机科学技术、信息管理等专业的核心课程

4、之一，是一门理论与工程实践密切相关的 综合性课程，在计算机学科教学中具有十分重要的作用。大力加强数据结构课程的建设，提高数据结构 课程的教学质量，有利于教学改革和教育创新，有利于高级应用型人才和创新人才的培养。 数据结构课程是计算机专业的专业基础课程，介绍计算机领域的常用数据结构以及各种查找和 排序的算法，是计算机专业学生必修的一门技术基础课程，也是计算机专业的核心课程。数据结构是计 算机专业的一门重要的专业基础课，主要解决数据的表示和数据的处理，系统介绍三大数据结构及其实 现，为操作系统等课程提供必要的知识基础，为计算机人员提供必要的基本技能。 二、课程教学基本要求 本课程介绍常用数据结构之

5、间的逻辑结构、存储结构和对其施加的运算，如：线性表、栈、队列、 串、数组、广义表、树、图等。同时还介绍各种查找和排序的算法。 通过本门课程的学习，应使学生掌握以下几个方面的知识： 1：系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据结构和存 储结构的原则和方法。 2：学习和掌握在各种存储结构上实现的各种算法及其设计思想，从而学习各种分析问题和解决问题 的能力。 3：掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。 4：掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。 三、课程教学内容体系 第一章：概论 1.1 什么是数据结构 1.2 基本

6、概念和术语 1.3 抽象数据类型的表现与实现 1.4 算法和算法分析 教学要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概 念；学会分析算法的时间复杂性和空间复杂性。 第二章：线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现（静态查找表不讲） 2.4 一元多项式的表示及相加 教学要求：理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运 算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法； 以达到利用基本算法 进行较复杂算法设计的目的。 第三章：栈、队列 3.1

7、 栈 3 3.2 栈的应有和举例 3.2.1 数制转换 3.3.4 迷宫求解 3.3 栈与递归的实现 3.4 队列 教学要求：理解栈和队列的定义、特点，学习它们的各种组织方式及算法；掌握它们的空和满的判断条 件；并学会它们的简单应用。 第四章：串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.3 串的块链存储表示 4.3 串的模式匹配算法 4.3.1 求字串位置的定位函数 教学要求：了解串的概念，掌握串的基本运算，学习串运算在不同存储结构下的实现过程。 第五章：多维数组和广义表 5.1 数组的定义 5.2 数组的顺序表现和实现 5.3 矩阵的压缩存储 教学

8、要求：领会数组的定义，数组的两种顺序存储结构，并领会几种特殊矩阵和稀疏矩阵的压缩存储方 法。 第六章：树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码 教学要求：理解树型结构的概念和术语，领会二叉树的定义、形态、性质和存储结构，掌握二叉树的各 种遍历算法极其实现过程，了解树

9、和森林及其相互转换；掌握哈夫曼树极其应用。 第七章：图 7.1 图的定义和术语 7.2 图的存储结构 7.2.1 数组表示法 4 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 7.4.3 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 教学要求：理解图型结构的概念和术语，掌握图的邻接矩阵和邻接表两种存储形式，理解图的遍历 的基本思想，掌握图的两种

10、遍历的方法和其实现的过程，学会图在最小生成树、拓扑排序、最短路径、 关键路径中的应用。 第九章：查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.1.4 索引顺序表的查找 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 教学要求：掌握查找表的定义和分类，熟练掌握顺序查找和二分查找的思想，了解二叉排序树及其 查找，了解散列查找的思想和有关方法。 第十章：内部排序 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 其他插入排序（表的插入排序不讲） 10.2.3 希尔排序 10.3 快速

11、排序 10.4 选择排序 10.4.1 简单选择排序 10.5 归并排序 教学要求：熟练掌握各种排序方法的思想和特点，如：插入排序、交换排序、选择排序、分配排序等， 学会分析它们的优点和缺点以及时空性能，并学会选择和应用各种排序方法解决实际问题。 5 四、学时分配 章节内容 讲授学时 上机学时 习题学时 一 概 论 4 0 0 二 线性表 6 1 1 三 栈、队列 6 1 1 四 串 2 1 1 五 数组和广义表 4 1 1 六 树和二叉树 8 1 1 七 图 8 1 1 九 查找 2 1 1 十 内部排序 4 1 1 总学时数：60 课时 44 8 8 五、推荐教材及教学参考书 1. 教材

12、数据结构；严蔚敏编著；清华大学出版社 2. 教学参考书 算法与数据结构（C 语言版） ， 范策等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 数据结构实用教程（第二版），徐孝凯编著，清华大学出版社 2006 数据结构辅导与提高实用教程（第二版），徐孝凯，清华大学出版社 2003 数据结构，谢楚屏等，人民邮电出版社，2001 算法与数据结构C 语言描述 ，张乃孝等，高等教育出版社，2002 数据结构，殷人昆，清华大学出版社，2001 计算机算法设计与分析，苏德富，电子工

13、业出版社，2001 算法与数据结构，傅清祥，王哓冬，电子工业出版社，1998 数据结构C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，2001 数据结构用面向对象方法与 C+描述，殷人昆等清华大学出版社 算法设计与分析，梁田贵，张鹏编著，冶金工业出版社，2004 六、考核办法和成绩评定标准 根据教学要求进行期末考试，由任课教师根据完成情况进行评定，并最终结合平时成绩的考核给出 综合成绩。 制定： 制定日期： 6 教 案 （ 首 页 ） 授课时间 教案编写时间 课程代码课程名称 数据结构 学 分 课程性质 必修课（） 选修课（ ）理论课（） 实验课（ ） 任课教师 职称 总学时 讲课： 学

14、时 上机： 学时 实习： 周 授课对象 专业： 年级： 班级： 教材 和 主要参考 资料 选用教材： 数据结构， 严蔚敏编著 清华大学出版社 主要参考书： 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 数据结构实用教程（第二版），徐孝凯编著，清华大学出版社 2006 数据结构辅导与提高实用教程（第二版），徐孝凯，清华大学出版社 2003 数据结构，谢楚屏等，人民邮电出版社，2001 算法与数据结构C 语言描述

15、，张乃孝等，高等教育出版社，2002 数据结构，殷人昆，清华大学出版社，2001 计算机算法设计与分析，苏德富，电子工业出版社，2001 算法与数据结构，傅清祥，王哓冬，电子工业出版社，1998 数据结构C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，2001 数据结构用面向对象方法与 C+描述，殷人昆等清华大学出版社 算法设计与分析，梁田贵，张鹏编著，冶金工业出版社，2004 教学目的 和 教学要求 通过本门课程的学习，应使学生掌握以下几个方面的知识： 1 系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据 结构和存储结构的原则和方法。 2 学习和掌握在各种存

16、储结构上实现的各种算法及其设计思想，从而学习各种分析问题和 解决问题的能力。 3 掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。 4 掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。 7 教学重点 和 教学难点 重点掌握数据结构之间的逻辑结构、存储结构和对其施加的运算，如：线性表、栈、队 列、串、数组、广义表、树、图等。应掌握各种查找和排序的算法。 难点章节：第六章：树和第七章：图。 教学进程 8 第 1 次课 第 2 次课 第 3 次课 第 4 次课 第 5 次课 第 6 次课 第 7 次课 第 8 次课 第 9 次课 第 10 次课 第 11 次课 第 12

17、次课 第 13 次课 第 14 次课 第 15 次课 第 16 次课 第 17 次课 第 18 次课 第 19 次课 第 20 次课 第 21 次课 第 22 次课 第 23 次课 第 24 次课 第 25 次课 第 26 次课 第 27 次课 第 28 次课 第 29 次课 第 30 次课 授课章节 第 1 章 绪论：1.1 什么是数据结构、1.2 基本概念和术语 第 1 章：1.3 抽象数据类型的表现与实现 1.4 算法和算法分析 第 2 章 线性表：2.1 线性表的类型定义 2.2 线性表的顺序表示 第 2 章 ：2.3 线性表的链式表示和实现（1） 第 2 章 ：2.3 （2）2.4

18、一元多项式的表示及相加 第 3 章 栈和队列：3.1、3.2.1 第 3 章 栈和队列：3.2.4、3.2.5、3.3 第 3 章 栈和队列：3.4 综合习题课（1）：前 3 章的相关内容 综合实验课（1）：前 3 章的相关内容 第 4 章 串：4.1、4.2.1、4.2.2、4.2.3、4.3.1 第 5 章 数组和广义表：5.1、5.2 第 5 章 数组和广义表：5.3 综合实验课（2）：第 4-5 章的相关内容 第 6 章 树和二叉树：6.1、6.2 第 6 章 树和二叉树：6.3、6.4.1 第 6 章 树和二叉树：6.4.2、6.6 第 6 章 树和二叉树： 综合习题课（2）：树的相

19、关内容 第 7 章 图：7.1、7.2 第 7 章 图：7.3、7.4.1、7.4.3 第 7 章 图：7.6 第 7 章 图： 综合习题课（3）：图的相关内容 第 9 章 查找：9.1、9.3 综合实验课（3）：第 9 章的相关内容 第 10 章 内部排序：10.1、10.2 第 10 章 内部排序：10.3、10.4 综合习题课（3）：第 9、10 章的相关内容 综合实验课（4）：第 10 章的相关内容 学 时 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 备 注 9 教 案 （ 分 教 案 ） 课 次 ： 1 学

20、时 ： 2 章 节 第 1 章 绪论：1.1 什么是数据结构、1.2 基本概念和术语 教学目的 和 教学要求 了解数据结构的课程性质、内容、应用领域及其与其他学科的关系；掌握数据结构的相关 概念和术语；掌握四类基本的数据关系。 教 学 重 点 难 点 教学重点： 数据结构的相关概念和术语 教学难点： 四类基本的数据关系 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的 处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的 数据。进行程序设计时必须分析待处理的对

21、象的特性及各对象之间存在的关系产生背 景。 1.1 什么是数据结构 1.2 数据结构的基本概念和术语 1. 数据（Data） 2. 数据元素（Data Element） 3. 数据对象（Data Object） 4. 结构（Data Structure）存储结构、抽象数据类型 抽象数据类型 (Abstract Data Type) ADT 的定义格式不唯一, 我们采用下述格式定义一个 ADT: ADT 抽象数据类型名 数据对象: 数据关系: 基本操作: ADT 抽象数据类型名 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 图 1.5：要求理解和掌握四类基本的数

22、据关系；并在日常生活中举例进行说明。 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 10 教 案 （ 分 教 案 ） 课 次 ： 2 学 时 ： 2 章 节 第 1 章：1.3 抽象数据类型的表现与实现 1.4 算法和算法分析 教学目的 和 教学要求 理解抽象数据类型的表示及实现； 对算法、算法要求、算法效率的度量进行有效的分析。 教 学 重 点 难 点 教学重点： 抽

23、象数据类型的表示及实现；算法、算法要求； 教学难点： 算法效率的度量及有效的分析； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 1.3 抽象数据类型的表示和实现 1.4 算 法 1. 算法（Algorithm）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是规则的有限集合， 是为解决特定问题而规 定的一系列操作。) 是指令的有限序列，其中每一条指令表示一个或多个操作。 2

24、. 算法的特性 3. 算法设计的要求 ） 算法的正确性 (1) 所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到 满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结果。 2） 可读性 3） 健壮性 4） 高效率和低存储量 、算法、 语言和程序的关系 时间复杂度 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1:图 1.5、P13：算法的 5 个特征；2:P15：两段程序的语句的频度的分析 主要 参考资料 算法与数据结构

25、（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 11 教 案 （ 分 教 案 ） 课 次 ： 3 学 时 ： 2 章 节 第 2 章 线性表：2.1 线性表的类型定义 2.2 线性表的顺序表示 教学目的 和 教学要求 理解线性表的定义和特点；掌握顺序表以达到利用基本算法进行较复杂算法设计的目的。 教 学 重 点 难 点 教学重点：线性表的定义和特点；线性表的顺序表示 教学难点：线性表的顺序表示 教学进

26、程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 线性结构的特点： 在数据元素的非空有限集中， 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。 2.1 线性表的类型定义 2.1.1 线性表的逻辑结构 2.1.2 线性表的抽象数据类型定义 2.2 线性表的顺序表示和实现 2.2.1 线性表的顺序存储结构 2.2.2 线性表顺序存储结构上的基本运算 1. 初始化操作 2. 插入操作 3. 删除操作 算法 2.1 算法 2.3 教

27、学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：算法 2.1、图 2.2、算法 2.42：算法 2.5、算法 2.6 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 12 教 案 （ 分 教 案 ） 课 次 ： 4 学 时 ： 2 章 节 第 2 章 ：2.3 线性表的链式表示和实现（1） 教学目的 和 教学要求 理解线性表的链表的特点，

28、掌握在这种存储结构上各种基本运算的实现算法以及效率的 分析，并学习在这种存储结构上进行算法设计的方法； 以达到利用基本算法进行较复杂算 法设计的目的。 教 学 重 点 难 点 教学重点：线性表的链式表示和实现； 教学难点：单链表的插入、删除、查找和归并操作； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 2.3 线性表的链式表示和实现 2.3.1 单链表 线性表的链式存储： 图 2.6 单链表的逻辑状态 图 2.7 带头结点单链表图示 2.3.2 单链表上的基本运算 1. 建立单链表 2. 查找 3. 单链表插入操作 4. 删除 5合并单链表： 教学方法、课堂

29、讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：图 2.5、图 2.8、图 2.92：算法 2.8、算法 2.9、算法 2.10、算法 2.11 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 13 14 教 案 （ 分 教 案 ） 课 次 ： 5 学 时 ： 2 章 节 第 2 章 ：2.3 （2）2.4 一元多项式的表示及相加 教学目的 和 教学

30、要求 理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的 分析；掌握一元多项式的表示及相加的方法与算法。 教 学 重 点 难 点 教学重点： 循环链表、双向链表及其算法；一元多项式的表示及相加的方法与算法； 教学难点：双向链表及其算法、一元多项式相加的方法； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 2.3.3 循环链表 2.3.4 双向链表 1. 双向链表的前插操作 2. 双向链表的删除操作 2.3.6 顺序表和链表的比较 1. 基于空间的考虑、 2. 基于时间的考虑、 3. 基于语言的考虑 2.4 一元多项式的表示及相加 教学

31、方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：图 2.12、图 2.14、图 2.15、图 2.16、图 2.17、图 2.182：算法 2.18、算法 2.19、算法 2.23 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 15 16 教 案 （ 分 教 案 ） 课 次 ： 6 学 时 ： 2 章 节 第 3 章 栈和队列：3.1 栈

32、、3.2.1 数制转换 教学目的 和 教学要求 理解栈的定义、特点，学习它的各种组织方式及算法；掌握它的空和满的判断条件；并 学会它的简单应用。 教 学 重 点 难 点 教学重点： 栈的定义、特点，学习它的各种组织方式及算法； 教学难点： 栈的简单应用； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现 1. 顺序栈 顺序栈基本操作的实现: (1) 初始化、(2) 取栈顶元素、(3) 入栈、(4) 出栈 2. 链栈 3.2 栈的应用举例 1. 数制转换 教学方法、课堂讲解、例题演示，课件演示 辅助手段：

33、电脑、投影仪、教科书 作 业 1：图 3.1、3.22：P47：栈基本操作的算法描述、算法 3.1 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 17 备注 18 教 案 （ 分 教 案 ） 课 次 ： 7 学 时 ： 2 章 节 第 3 章 栈和队列：3.2.4 迷宫求解、3.3 栈与递归的实现 教学目的和 教学要求 了解迷宫求解的算法思路、了解计算机图形学中的种子填充苏算

34、法； 掌握汉诺塔算法及其过程。 教 学 重 点 难 点 教学重点： 迷宫求解的算法思路、汉诺塔算法及其过程； 教学难点： 汉诺塔算法及其过程； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 4. 迷宫求解（拓展：填充算法） 3.3 栈与递归的实现 1. 递归特性问题 1) 递归函数 2）汉诺塔算法 三个盘子搬动时 hanoi(3, A, B, C) 递归调用过程： hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1 号搬到 C move(A-B) 2 号搬到 B hanoi(1,C,A,B) move(C-B) 1 号搬到 B

35、 move(A-c) 3 号搬到 C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1 号搬到 A move(B-c) 2 号搬到 C hanoi(1,A,B,C) move(A-C) 1 号搬到 C 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：图 3.72：算法 3.5、种子填充算法、两种算法求解 n! 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，

36、张铭，高等教育出版社，2004 课后自我总 结分析 备注 19 20 教 案 （ 分 教 案 ） 课 次 ： 8 学 时 ： 2 章 节 第 3 章 栈和队列：3.4 队列 教学目的和 教学要求 掌握队列的数据结构和链队列的相关操作；掌握循环队列的相关内容； 教 学 重点、难点 教学重点： 列的数据结构和链队列的相关操作； 教学难点： 循环队列的相关操作； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 3.4 队 列 3.4.1 队列的定义 队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删 除元素，所以队列具有先进先出(Fi

37、st In Fist Out， 缩写为 FIFO)的特性。在队列中，允 许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 3.4.2 队列的表示和实现 链队列: （1） 初始化操作、 （2）销毁队列、 （3） 入队操作、 （4） 出队操作 3.4.3：循环队列 如何区分队列“空”和“满” 1. 另设一个标志位以区分队列是空还是满； 2. 少用一个元素空间，当队列头指针在队列尾指针的下一个位置上时为“满” 。 当 Q.front=Q.rear 时队空；Q.front+1=Q.rear 时队满 循环队列满足条件 (Q.rear+1)%MAXQSIZE= Q.front 队

38、满 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：图 3.8、图 3.10、图 3.11、图 3.14；2：P62：队列的基本操作算法、P64：循环队列的基本操作算法； 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 21 22 教 案 （ 分 教 案 ） 课 次 ： 9 学 时 ： 2 章 节 综合习题课（1）：前 3 章的相关内容

39、 教学目的 和 教学要求 要求掌握栈的应用及递归算法 教 学 重 点 难 点 教学重点： 教学难点： 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 1：求 N！的递归算法； 2：求 N！的栈的算法； 3：数制转换算法的具体实现； 4：种子填充算法的具体过程： 四向连通填充算法： a） 种子像素压入栈中； b） 如果栈为空，则转 e)；否则转 c)； c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边 界色或已经置成多边形的填充色，若不是，则将该像素压入栈； d） 转 b） ； e） 结束。 教学方法、课堂讲解、例题演示，课件演示 辅

40、助手段：电脑、投影仪、教科书 作 业 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 备注 23 教 案 （ 分 教 案 ） 课 次 ： 10 学 时 ： 2 章 节 综合实验课（1）：前 3 章的相关内容 教学目的 和 教学要求 1：求 N！的递归算法； 2：求 N！的栈的算法； 3：数制转换算法的具体实现； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段）

41、 教学进程： 1：求 N！的递归算法； 2：求 N！的栈的算法； 3：数制转换算法的具体实现； #include “stdio.h“ #include “stdlib.h“ #define size 20 typedef struct int *base; int *top; int ssize; ss; void ist(ss s.top=s.base; s.ssize=size; void main() long n,m; ss w; ist(w); printf(“请输入 N 的值(1-32768)：“); scanf(“%d“,m=n; while(n) *w.top+=n%8; n=

42、n/8; printf(“转换为 8 进制以后的值：n(%d)10=(“,m); while(w.top!=w.base) printf(“%d“,*-w.top); printf(“)8n“); 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自我总 结分析 24 25 教 案 （ 分 教 案 ） 课 次 ： 11 学

43、时 ： 2 章 节 第 4 章 串：4.1 串的定义、4.2.1 定长顺序存储表示 4.2.3 串的块链存储表示 4.3.1 求子串位置的定位函数 教学目的和 教学要求 掌握串的定义、定长顺序存储表示；了解串的块链存储表示； 掌握求子串位置的定位函数（模式匹配算法） ； 教 学 重 点 难 点 教学重点： 串的定义、定长顺序存储表示；串的块链存储表示； 教学难点：求子串位置的定位函数（模式匹配算法） ； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 4.1 串的定义 串(String)是零个或多个字符组成的有限序列。 一般记为： S= a1a2.an (n0)

44、 4.2 串的表示和实现 4.2.1 定长顺序存储表示串 1.串联接 Concat( j = 1 ; while ( i=S 0 else return 0 ; / Index 算法：4.5 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 1：P73：串的链接操作；图 4.1；2：算法 4.5：串的模式匹配算法、图 4.3； 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2

45、004 课后自我总 结分析 备注 26 27 教 案 （ 分 教 案 ） 课 次 ： 12 学 时 ： 2 章 节 第 5 章 数组和广义表：5.1 数组的定义、5.2 数组的顺序表示和实现 教学目的和 教学要求 掌握数组的定义、数组的顺序表示和实现； 教 学 重 点 难 点 教学重点： 数组的定义、数组的顺序表示和实现 教学难点： 数组的顺序表示和实现 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 5.1 数组的定义 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种 线性表。 对于数组的操作一般只有两类： (1） 获得特定位置的元

46、素值； (2 ） 修改特定位置的元素值。 5.2 数组的顺序表示和实现 数组一般不做插入和删除操作，因此采用顺序存储结构。由于存储单元是一维结构，而 数组是多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。 数组的顺序存储结构有两种：一种是按行序存储，另一种是按列序存储。 Loci, j=Loc1, 1+n(i-1)+(j-1) Loci, j, k=Loc1, 1, 1+(i-1)mn+(j-1)n+(k-1) 对于维数组 A(c1d1, c2d2，, cndn)，我们只要把上式推广，就可以容易地 得到维数组中任意元素 aj1j2jn 的存储地址的计算公式: LOC(aj1

47、j2jn) =LOC(a000)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*l LOC(aj1j2jn)= LOC(a000)+( = LOC(a000)+ 其中 cn=L,ci-1=bi*ci 教学方法、课堂讲解、例题演示，课件演示 辅助手段：电脑、投影仪、教科书 作 业 计算 1-3 维数组的任意元素的存储地址； 主要 参考资料 算法与数据结构（C 语言版） ， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004 数据结构（C 语言版）， 严蔚敏等编著， 清华大学出版社 2004 数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004 课后自

48、我总 结分析 备注 28 29 教 案 （ 分 教 案 ） 课 次 ： 13 学 时 ： 2 章 节 第 5 章 数组和广义表：5.3 矩阵的压缩存储 5.3.1 特殊矩阵、5.3.2 稀疏矩阵 教学目的和 教学要求 掌握特殊矩阵和稀疏矩阵的存储方法；掌握稀疏矩阵的转置算法； 教 学 重 点 难 点 教学重点： 特殊矩阵和稀疏矩阵的存储方法；稀疏矩阵的转置算法； 教学难点：稀疏矩阵的转置算法； 教学进程 （含章节 教学内容、 学时分配、 教学方法、 辅助手段） 教学进程： 5.3 矩阵的压缩存储 压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。特殊矩阵： 值相同的元素或零元素在矩阵中的分布有一定的规律。稀疏矩阵：矩阵中元素分布没有规律， 但零元素较多。 5.3.1 特殊矩阵 三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵 Loci, j=Loc1, 1+i(i-1)/2+j-1 带状矩阵 5.3.2 稀疏矩阵 方法一：按照 b.data 中三元组的次序依次在 a.data 中找到相应的三元组进行转置。 方法二：按照