《数据结构》教案

1 课课程程简简介介 人们在运用程序设计语言编写程序的过程中发现所有的数据都可以抽象为三种结构 而 对这些数据的所有操作都可以转化为对这三种数据的几种基本操作 而大多数的程序设计技 巧都可以抽象为一些最基本的算法 于是人们逐步发展了一门称为数据结构 或数据结构与 算法 的计算机科学 它广泛应用于计算机领域 数据结构是信息与计算专业的核心基础课程之一 数据是计算机处理的对象 本课程研 究的数据是非数值性 结构性的数据 学习本课程要求掌握各种主要数据结构的特点 计算 机内的表示方法 以及处理数据的算法 对于算法所花费的时间和空间代价的分析也要求有 一定程度的了解和掌握 通过本课程的学习 使学生透彻地理解各种数据对象的特点 学会 数据的组织方法和实现方法 并进一步培养基本的良好的程序设计能力 本课程主要包括如 下三个方面的内容 1 基本数据结构 线性表 栈 队列 串 数组和广义表 掌握它们的特点 表示和 实现 对静态结构要求非常熟练的编程上机实现 对动态结构要求逐步熟悉链表的表示 通 过模仿实验教程中的例子 掌握编程技巧 强调类 C 语言的书写规范 特别注意参数的区 别 输入输出的方式和错误处理方式 以及抽象数据类型的表示和实现 能熟练完成以下的 应用 多项式的计算 语法检查 回朔算法 递归算法 表达式求值 离散事件模拟 文字 的编辑和稀疏矩阵进行矩阵运算采用的处理方法 2 复杂数据结构 树 二叉树 图 掌握它们的定义和特点 表示和实现 特别注意 与基本数据结构的区别 掌握各种遍历的递归和非递归算法 能熟练完成以下的应用 最优 树 Huffman 编码 拓扑排序 关键路径和最短路径问题 3 数据结构的应用 查找和内部排序 熟练掌握静态查找表的查找方法和实现 了解 哈希表的构造和查找方法 掌握各种内部排序方法的基本思想 算法特点 排序过程以及它 们的时间复杂度分析 2 数据结构数据结构 教学大纲教学大纲 课程名称 数据结构 课程编号 适用专业 计算机 信息管理 总学时数 60 学分数 4 一 课程的性质 目的与任务一 课程的性质 目的与任务 数据结构是计算机科学技术 信息管理等专业的核心课程之一 是一门理论与工程实践密切相关的 综合性课程 在计算机学科教学中具有十分重要的作用 大力加强数据结构课程的建设 提高数据结构 课程的教学质量 有利于教学改革和教育创新 有利于高级应用型人才和创新人才的培养 数据结构 课程是计算机专业的专业基础课程 介绍计算机领域的常用数据结构以及各种查找和 排序的算法 是计算机专业学生必修的一门技术基础课程 也是计算机专业的核心课程 数据结构是计 算机专业的一门重要的专业基础课 主要解决数据的表示和数据的处理 系统介绍三大数据结构及其实 现 为操作系统等课程提供必要的知识基础 为计算机人员提供必要的基本技能 二 课程教学基本要求二 课程教学基本要求 本课程介绍常用数据结构之间的逻辑结构 存储结构和对其施加的运算 如 线性表 栈 队列 串 数组 广义表 树 图等 同时还介绍各种查找和排序的算法 通过本门课程的学习 应使学生掌握以下几个方面的知识 1 系统学习常用基本数据结构及其在不同存储方式下的实现 掌握分析 选择不同的数据结构和存 储结构的原则和方法 2 学习和掌握在各种存储结构上实现的各种算法及其设计思想 从而学习各种分析问题和解决问题 的能力 3 掌握各种算法的时空效率的分析方法 学会在实际应用中选择合适的算法 4 掌握各种查找和排序的算法以及效率 并将其应用在程序设计中 三 课程教学内容体系三 课程教学内容体系 第一章 概论第一章 概论 1 1 什么是数据结构 1 2 基本概念和术语 1 3 抽象数据类型的表现与实现 1 4 算法和算法分析 教学要求 理解数据 数据元素 数据项的概念 掌握逻辑结构和存储结构的关系 理解算法的基本概 念 学会分析算法的时间复杂性和空间复杂性 第二章 线性表第二章 线性表 2 1 线性表的类型定义 2 2 线性表的顺序表示和实现 2 3 线性表的链式表示和实现 静态查找表不讲 2 4 一元多项式的表示及相加 教学要求 理解线性表的定义和特点 掌握顺序表和链表的特点 掌握在这两种存储结构上各种基本运 算的实现算法以及效率的分析 并学习在这两种存储结构上进行算法设计的方法 以达到利用基本算法 进行较复杂算法设计的目的 第三章 栈 队列第三章 栈 队列 3 1 栈 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 矩阵的压缩存储 教学要求 领会数组的定义 数组的两种顺序存储结构 并领会几种特殊矩阵和稀疏矩阵的压缩存储方 法 第六章 树第六章 树 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 赫夫曼编码 教学要求 理解树型结构的概念和术语 领会二叉树的定义 形态 性质和存储结构 掌握二叉树的各 种遍历算法极其实现过程 了解树和森林及其相互转换 掌握哈夫曼树极其应用 第七章 图第七章 图 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 从某个源点到其余各顶点的最短路径 教学要求 理解图型结构的概念和术语 掌握图的邻接矩阵和邻接表两种存储形式 理解图的遍历 的基本思想 掌握图的两种遍历的方法和其实现的过程 学会图在最小生成树 拓扑排序 最短路径 关键路径中的应用 第九章 查找第九章 查找 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 快速排序 10 4 选择排序 10 4 1 简单选择排序 10 5 归并排序 教学要求 熟练掌握各种排序方法的思想和特点 如 插入排序 交换排序 选择排序 分配排序等 学会分析它们的优点和缺点以及时空性能 并学会选择和应用各种排序方法解决实际问题 5 四 学时分配四 学时分配 章节内容讲授学时上机学时习题学时 一概 论400 二线性表611 三栈 队列611 四串211 五数组和广义表411 六树和二叉树811 七图811 九查找211 十内部排序411 总学时数 60 课时4488 五 推荐教材及教学参考书五 推荐教材及教学参考书 1 教材 数据结构 严蔚敏编著 清华大学出版社 2 教学参考书 算法与数据结构 C 语言版 范策等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 数据结构实用教程 第二版 徐孝凯编著 清华大学出版社 2006 数据结构辅导与提高实用教程 第二版 徐孝凯 清华大学出版社 2003 数据结构 谢楚屏等 人民邮电出版社 2001 算法与数据结构 C 语言描述 张乃孝等 高等教育出版社 2002 数据结构 殷人昆 清华大学出版社 2001 计算机算法设计与分析 苏德富 电子工业出版社 2001 算法与数据结构 傅清祥 王哓冬 电子工业出版社 1998 数据结构 C 与面向对象的途径 张乃孝 裘宗燕 高等教育出版社 2001 数据结构 用面向对象方法与 C 描述 殷人昆等清华大学出版社 算法设计与分析 梁田贵 张鹏编著 冶金工业出版社 2004 六 考核办法和成绩评定标准六 考核办法和成绩评定标准 根据教学要求进行期末考试 由任课教师根据完成情况进行评定 并最终结合平时成绩的考核给出 综合成绩 制定 制定日期 6 教教案案 首首页页 授课时间 教案编写时间 课程代码 课程名称数据结构 学 分 课程性质 必修课 选修课 理论课 实验课 任课教师职称 总学时 讲课 学时 上机 学时 实习 周 授课对象专业 年级 班级 教材 和 主要参考 资料 选用教材 数据结构 严蔚敏编著 清华大学出版社 主要参考书 主要参考书 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 数据结构实用教程 第二版 徐孝凯编著 清华大学出版社 2006 数据结构辅导与提高实用教程 第二版 徐孝凯 清华大学出版社 2003 数据结构 谢楚屏等 人民邮电出版社 2001 算法与数据结构 C 语言描述 张乃孝等 高等教育出版社 2002 数据结构 殷人昆 清华大学出版社 2001 计算机算法设计与分析 苏德富 电子工业出版社 2001 算法与数据结构 傅清祥 王哓冬 电子工业出版社 1998 数据结构 C 与面向对象的途径 张乃孝 裘宗燕 高等教育出版社 2001 数据结构 用面向对象方法与 C 描述 殷人昆等清华大学出版社 算法设计与分析 梁田贵 张鹏编著 冶金工业出版社 2004 教学目的 和 教学要求 通过本门课程的学习 应使学生掌握以下几个方面的知识 1 系统学习常用基本数据结构及其在不同存储方式下的实现 掌握分析 选择不同的数据 结构和存储结构的原则和方法 2 学习和掌握在各种存储结构上实现的各种算法及其设计思想 从而学习各种分析问题和 解决问题的能力 3 掌握各种算法的时空效率的分析方法 学会在实际应用中选择合适的算法 4 掌握各种查找和排序的算法以及效率 并将其应用在程序设计中 7 教学重点 和 教学难点 重点掌握数据结构之间的逻辑结构 存储结构和对其施加的运算 如 线性表 栈 队 列 串 数组 广义表 树 图等 应掌握各种查找和排序的算法 难点章节 第六章 树和第七章 图 教学进程 8 第 1 次课 第 2 次课 第 3 次课 第 4 次课 第 5 次课 第 6 次课 第 7 次课 第 8 次课 第 9 次课 第 10 次课 第 11 次课 第 12 次课 第 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 一元多项式的表示及相加 第 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 树的相关内容 第 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 学时 2 章 节第 1 章 绪论 1 1 什么是数据结构 1 2 基本概念和术语 教学目的 和 教学要求 了解数据结构的课程性质 内容 应用领域及其与其他学科的关系 掌握数据结构的相关 概念和术语 掌握四类基本的数据关系 教 学 重 点 难 点 教学重点 数据结构的相关概念和术语 教学难点 四类基本的数据关系 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 计算机的应用不再局限于科学计算 更多地用于控制 管理 数据处理等非数值计算的 处理工作 计算机加工处理的对象 数值 字符 表格 图形声音 图象等具有一定结构的 数据 进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系 产生背 景 1 1 什么是数据结构 1 2 数据结构的基本概念和术语 1 数据 Data 2 数据元素 Data Element 3 数据对象 Data Object 4 结构 Data Structure 存储结构 抽象数据类型 抽象数据类型 Abstract Data Type ADT 的定义格式不唯一 我们采用下述格式定义一个 ADT ADT 抽象数据类型名 数据对象 数据关系 基本操作 ADT 抽象数据类型名 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业图 1 5 要求理解和掌握四类基本的数据关系 并在日常生活中举例进行说明 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 10 教教案案 分分教教案案 课次 2 学时 2 章 节第 1 章 1 3 抽象数据类型的表现与实现 1 4 算法和算法分析 教学目的 和 教学要求 理解抽象数据类型的表示及实现 对算法 算法要求 算法效率的度量进行有效的分析 教 学 重 点 难 点 教学重点 抽象数据类型的表示及实现 算法 算法要求 教学难点 算法效率的度量及有效的分析 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 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 算法的特性 3 算法设计的要求 算法的正确性 1 所设计的程序没有语法错误 2 所设计的程序对于几组输入数据能够得出满足要求的结果 3 所设计的程序对于精心选择的典型 苛刻而带有刁难性的几组输入数据能够得到 满足要求的结果 4 程序对于一切合法的输入数据都能产生满足要求的结果 2 可读性 3 健壮性 4 高效率和低存储量 算法 语言和程序的关系 时间复杂度时间复杂度 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 1 5 P13 算法的 5 个特征 2 P15 两段程序的语句的频度的分析 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 11 教教案案 分分教教案案 课次 3 学时 2 章 节第 2 章 线性表 2 1 线性表的类型定义 2 2 线性表的顺序表示 教学目的 和 教学要求 理解线性表的定义和特点 掌握顺序表以达到利用基本算法进行较复杂算法设计的目的 教 学 重 点 难 点 教学重点 线性表的定义和特点 线性表的顺序表示 教学难点 线性表的顺序表示 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 线性结构的特点 在数据元素的非空有限集中 存在唯一的一个被称为 第一个 的数据元素 存在唯一的一个被称为 最后一个 的数据元素 除第一个元素之外 集合中的每个元素均只有一个前驱 除最后一个元素之外 集合中的每个元素均只有一个后继 2 1 线性表的类型定义 2 1 1 线性表的逻辑结构 2 1 2 线性表的抽象数据类型定义 2 2 线性表的顺序表示和实现 2 2 1 线性表的顺序存储结构 2 2 2 线性表顺序存储结构上的基本运算 1 初始化操作 2 插入操作 3 删除操作 算法 2 1 算法 2 3 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 算法 2 1 图 2 2 算法 2 4 2 算法 2 5 算法 2 6 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 12 教教案案 分分教教案案 课次 4 学时 2 章 节第 2 章 2 3 线性表的链式表示和实现 1 教学目的 和 教学要求 理解线性表的链表的特点 掌握在这种存储结构上各种基本运算的实现算法以及效率的 分析 并学习在这种存储结构上进行算法设计的方法 以达到利用基本算法进行较复杂算 法设计的目的 教 学 重 点 难 点 教学重点 线性表的链式表示和实现 教学难点 单链表的插入 删除 查找和归并操作 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 2 3 线性表的链式表示和实现 2 3 1 单链表 线性表的链式存储 图 2 6 单链表的逻辑状态 图 2 7 带头结点单链表图示 2 3 2 单链表上的基本运算 1 建立单链表 2 查找 3 单链表插入操作 4 删除 5 合并单链表 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 2 5 图 2 8 图 2 9 2 算法 2 8 算法 2 9 算法 2 10 算法 2 11 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 13 14 教教案案 分分教教案案 课次 5 学时 2 章 节第 2 章 2 3 2 2 4 一元多项式的表示及相加 教学目的 和 教学要求 理解线性表的链表的特点 掌握在这种存储结构上各种基本运算的实现算法以及效率的 分析 掌握一元多项式的表示及相加的方法与算法 教 学 重 点 难 点 教学重点 循环链表 双向链表及其算法 一元多项式的表示及相加的方法与算法 教学难点 双向链表及其算法 一元多项式相加的方法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 2 3 3 循环链表 2 3 4 双向链表 1 双向链表的前插操作 2 双向链表的删除操作 2 3 6 顺序表和链表的比较 1 基于空间的考虑 2 基于时间的考虑 3 基于语言的考虑 2 4 一元多项式的表示及相加 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 2 12 图 2 14 图 2 15 图 2 16 图 2 17 图 2 18 2 算法 2 18 算法 2 19 算法 2 23 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 15 16 教教案案 分分教教案案 课次 6 学时 2 章 节第 3 章 栈和队列 3 1 栈 3 2 1 数制转换 教学目的 和 教学要求 理解栈的定义 特点 学习它的各种组织方式及算法 掌握它的空和满的判断条件 并 学会它的简单应用 教 学 重 点 难 点 教学重点 栈的定义 特点 学习它的各种组织方式及算法 教学难点 栈的简单应用 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 3 1 栈 3 1 1 栈的定义 3 1 2 栈的表示和实现 1 顺序栈 顺序栈基本操作的实现 1 初始化 2 取栈顶元素 3 入栈 4 出栈 2 链栈 3 2 栈的应用举例 1 数制转换 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 3 1 3 2 2 P47 栈基本操作的算法描述 算法 3 1 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 17 备注 18 教教案案 分分教教案案 课次 7 学时 2 章 节第 3 章 栈和队列 3 2 4 迷宫求解 3 3 栈与递归的实现 教学目的和 教学要求 了解迷宫求解的算法思路 了解计算机图形学中的种子填充苏算法 掌握汉诺塔算法及其过程 教 学 重 点 难 点 教学重点 迷宫求解的算法思路 汉诺塔算法及其过程 教学难点 汉诺塔算法及其过程 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 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 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 7 2 算法 3 5 种子填充算法 两种算法求解 n 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 19 20 教教案案 分分教教案案 课次 8 学时 2 章 节 第 3 章 栈和队列 3 4 队列 教学目的和 教学要求 掌握队列的数据结构和链队列的相关操作 掌握循环队列的相关内容 教 学 重点 难点 教学重点 列的数据结构和链队列的相关操作 教学难点 循环队列的相关操作 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 3 4 队 列 3 4 1 队列的定义 队列 Queue 是另一种限定性的线性表 它只允许在表的一端插入元素 而在另一端删 除元素 所以队列具有先进先出 Fist 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 队满 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 3 8 图 3 10 图 3 11 图 3 14 2 P62 队列的基本操作算法 P64 循环队列的基本操作算法 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 21 22 教教案案 分分教教案案 课次 9 学时 2 章 节综合习题课 1 前 3 章的相关内容 教学目的 和 教学要求 要求掌握栈的应用及递归算法 教 学 重 点 难 点 教学重点 教学难点 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 1 求 N 的递归算法 2 求 N 的栈的算法 3 数制转换算法的具体实现 4 种子填充算法的具体过程 四向连通填充算法 a 种子像素压入栈中 b 如果栈为空 则转 e 否则转 c c 弹出一个像素 并将该像素置成填充色 并判断该像素相邻的四连通像素是否为边 界色或已经置成多边形的填充色 若不是 则将该像素压入栈 d 转 b e 结束 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 23 教教案案 分分教教案案 课次 10 学时 2 章 节 综合实验课 1 前 3 章的相关内容 教学目的 和 教学要求 1 求 N 的递归算法 2 求 N 的栈的算法 3 数制转换算法的具体实现 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 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 n 8 printf 转换为 8 进制以后的值 n d 10 m while w top w base printf d w top printf 8 n 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 24 25 教教案案 分分教教案案 课次 11 学时 2 章 节 第 4 章 串 4 1 串的定义 4 2 1 定长顺序存储表示 4 2 3 串的块链存储表示 4 3 1 求子串位置的定位函数 教学目的和 教学要求 掌握串的定义 定长顺序存储表示 了解串的块链存储表示 掌握求子串位置的定位函数 模式匹配算法 教 学 重 点 难 点 教学重点 串的定义 定长顺序存储表示 串的块链存储表示 教学难点 求子串位置的定位函数 模式匹配算法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 4 1 串的定义 串 String 是零个或多个字符组成的有限序列 一般记为 S a1a2 an n 0 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 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 26 27 教教案案 分分教教案案 课次 12 学时 2 章 节第 5 章 数组和广义表 5 1 数组的定义 5 2 数组的顺序表示和实现 教学目的和 教学要求 掌握数组的定义 数组的顺序表示和实现 教 学 重 点 难 点 教学重点 数组的定义 数组的顺序表示和实现 教学难点 数组的顺序表示和实现 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 5 1 数组的定义 数组和广义表可看成是一种特殊的线性表 其特殊在于 表中的数据元素本身也是一种 线性表 对于数组的操作一般只有两类 1 获得特定位置的元素值 2 修改特定位置的元素值 5 2 数组的顺序表示和实现 数组一般不做插入和删除操作 因此采用顺序存储结构 由于存储单元是一维结构 而 数组是多维结构 则用一组连续存储单元存放数组的数据元素就有个次序约定问题 数组的顺序存储结构有两种 一种是按行序存储 另一种是按列序存储 Loc i j Loc 1 1 n i 1 j 1 Loc i j k Loc 1 1 1 i 1 m n j 1 n k 1 对于 维数组 A c1 d1 c2 d2 cn dn 我们只要把上式推广 就可以容易地 得到 维数组中任意元素 aj1j2 jn 的存储地址的计算公式 LOC aj1j2 jn LOC a00 0 b2 b3 bn j1 b3 bn j2 bn jn 1 jn l LOC aj1j2 jn LOC a00 0 LOC a00 0 其中 cn L ci 1 bi ci 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业计算 1 3 维数组的任意元素的存储地址 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 28 29 教教案案 分分教教案案 课次 13 学时 2 章 节第 5 章 数组和广义表 5 3 矩阵的压缩存储 5 3 1 特殊矩阵 5 3 2 稀疏矩阵 教学目的和 教学要求 掌握特殊矩阵和稀疏矩阵的存储方法 掌握稀疏矩阵的转置算法 教 学 重 点 难 点 教学重点 特殊矩阵和稀疏矩阵的存储方法 稀疏矩阵的转置算法 教学难点 稀疏矩阵的转置算法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 5 3 矩阵的压缩存储 压缩存储 为多个值相同的元素只分配一个存储空间 对零元素不分配空间 特殊矩阵 值相同的元素或零元素在矩阵中的分布有一定的规律 稀疏矩阵 矩阵中元素分布没有规律 但零元素较多 5 3 1 特殊矩阵 三角矩阵大体分为三类 下三角矩阵 上三角矩阵和对称矩阵 LocLoc i i j j Loc Loc 1 1 1 1 i i 1 2 j 1 i i 1 2 j 1 带状矩阵 5 3 2 稀疏矩阵 方法一 按照 b data 中三元组的次序依次在 a data 中找到相应的三元组进行转置 方法二 按照 a data 中三元组的次序进行转置 并将转置后的三元组置入 b 中的恰当位置 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 下三角 对称 带状矩阵的数据元素的下标地址的计算方法 2 稀疏矩阵的两个转置算法 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 30 31 教教案案 分分教教案案 课次 14 学时 2 章 节综合实验课 2 第 4 5 章的相关内容 教学目的和 教学要求 要求编程实现串的模式匹配算法 稀疏矩阵的两个转置算法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 1 串的模式匹配算法 2 稀疏矩阵的转置算法 一 3 稀疏矩阵的转置算法 二 include stdio h void main char sa 7 a b c d e f g char sb 3 e f g int i 0 j 0 while i 6 else printf 抱歉 没有找到 n include stdio h define mu 3 define nu 8 define tu 8 void main int M 8 3 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 int T 8 3 int q 0 col p i j printf 转换之前的矩阵为 n for i 0 i 7 i for j 0 j 2 j printf d M i j printf n for col 1 col nu col for p 0 p tu 1 p if M p 1 col T q 0 M p 1 T q 1 M p 0 T q 2 M p 2 q printf 转换之后的矩阵为 n for i 0 i 7 i for j 0 j0 时 该集合满足如 下条件 1 其中必有一个称为根 root 的特定结点 它没有直接前驱 但有零个或多个直接 后继 2 其余 n 1 个结点可以划分成 m m 0 个互不相交的有限集 T1 T2 T3 Tm 其中 Ti 又是一棵树 称为根 root 的子树 每棵子树的根结点有且仅有一个直接前驱 但 有零个或多个直接后继 6 2 二叉树的定义 6 2 1 二叉树的定义 定义 我们把满足以下两个条件的树形结构叫做二叉树 Binary Tree 1 每个结点至多只有二棵子树 即度都不大于 2 2 二叉树的子树有左右之分 其次序不能任意颠倒 6 2 2 二叉树的性质 满二叉树 完全二叉树 深度为 k 结点数为 n 的二叉树 如果其结点 1 n 的位置序号分别与满二叉树的结点 1 n 的位置序号一一对应 则为完全二叉树 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 图 6 3 二叉树的基本形态 2 二叉树的五个性质 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 33 教教案案 分分教教案案 课次 16 学时 2 章 节 第 6 章 树和二叉树 6 2 3 二叉树的存储结构 6 3 1 遍历二叉树 教学目的和 教学要求 熟练掌握二叉树的两种存储结构 熟练掌握二叉树的三种遍历方法 教 学 重 点 难 点 教学重点 二叉树的两种存储结构 二叉树的三种遍历方法 教学难点 二叉树的三种遍历方法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 6 2 3 二叉树的存储结构 二叉树的结构是非线性的 每一结点最多可有两个后继 二叉树的存储结构有两种 顺序存储结构和链式存储结构 1 顺序存储结构 2 链式存储结构 对于任意的二叉树来说 每个结点只有两个孩子 一个双亲结点 我们可以设计每个结 点至少包括三个域 数据域 左孩子域和右孩子 6 3 1二叉树的遍历 三种遍历方法的递归定义 先序遍历 DLR 操作过程 若二叉树为空 则空操作 否则依次执行如下 3 个操作 1 访问根结点 2 按先序遍历左子树 3 按先序遍历右子树 中序遍历 LDR 操作过程 若二叉树为空 则空操作 否则依次执行如下 3 个操作 1 按中序遍历左子树 2 访问根结点 3 按中序遍历右子树 后序遍历 LRD 操作过程 若二叉树为空 则空操作 否则依次执行如下 3 个操作 1 按后序遍历左子树 2 按后序遍历右子树 3 访问根结点 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 对一些特殊样式的二叉树进行顺序存储 2 对二叉树进行三种遍历操作 课后自我总 结分析 备注 34 教教案案 分分教教案案 课次 17 学时 2 章 节 第 6 章 6 4 树和森林 6 4 1 树的存储结构 6 4 2 森林与二叉树的转换 6 4 3 树和森林的遍历 教学目的和 教学要求 熟练掌握树的三种存储结构 熟练掌握森林与二叉树的转换 熟练掌握树和森林的遍历 教 学 重 点 难 点 教学重点 树的三种存储结构 森林与二叉树的转换 教学难点 树和森林的遍历 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 6 4 树和森林 6 4 1 树的存储结构 树的主要存储方法有以下三种 1 双亲表示法 2 孩子表示法 3 孩子兄弟表示法 6 4 2 森林与二叉树的转换 1 树转换为二叉树 将一棵树转换为二叉树的方法是 1 树中所有相邻兄弟之间加一条连线 2 对树中的每个结点 只保留其与第一个孩子结点之间的连线 删去其与其它孩子结 点之间的连线 3 以树的根结点为轴心 将整棵树顺时针旋转一定的角度 使之结构层次分明 2 森林转换为二叉树 森林是若干棵树的集合 树可以转换为二叉树 森林同样也可以转换为二叉树 因此 森林也可以方便地用孩子兄弟链表表示 森林转换为二叉树的方法如下 1 将森林中的每棵树转换成相应的二叉树 2 第一棵二叉树不动 从第二棵二叉树开始 依次把后一棵二叉树的根结点作为前一 棵二叉树根结点的右孩子 当所有二叉树连在一起后 所得到的二叉树就是由森林转换得 到的二叉树 3 二叉树还原为树或森林 6 4 3 树的遍历 1 树的遍历 树的遍历方法主要有以下两种 1 先根遍历 2 后根遍历 2 森林的遍历 森林的遍历方法主要有以下三种 1 先序遍历 2 中序遍历 3 后序遍历 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 把树用三种方法存储 2 把树和森林与二叉树进行相互转换 3 对树和森林进行遍历 课后自我总 结分析 备注 35 教教案案 分分教教案案 课次 18 学时 2 章 节 第 6 章 6 6 赫夫曼树及其应用 6 6 1 最优二叉树 赫夫曼树 6 6 2 赫夫曼编码 教学目的和 教学要求 熟练掌握哈夫曼树的构造方法 熟练掌握哈夫曼编码的编码方法 教 学 重 点 难 点 教学重点 哈夫曼树的构造方法 教学难点 哈夫曼编码的编码方法 教学进程 含章节 教学内容 学时分配 教学方法 辅助手段 教学进程 教学进程 6 6 赫夫曼树及其应用 6 6 1 最优二叉树 1 路径和路径长度 2 结点的权和带权路径长度 3 树的带权路径长度 构造赫夫曼算法的步骤如下 1 用给定的 n 个权值 w1 w2 wn 对应的 n 个结点构成 n 棵二叉树的森林 F T1 T2 Tn 其中每一棵二叉树 Ti 1 i n 都只有一个权值为 wi 的根结点 其 左 右子树为空 2 在森林 F 中选择两棵根结点权值最小的二叉树 作为一棵新二叉树的左 右子树 标记新二叉树的根结点权值为其左右子树的根结点权值之和 3 从 F 中删除被选中 的那两棵二叉树 同时把新构成的二叉树加入到森林 F 中 4 重复 2 3 操作 直到森林中只含有一棵二叉树为止 此时得到的这棵二叉 树就是赫夫曼树 6 6 2 赫夫曼编码 前缀编码 任一个字符的编码都不是另一个字符编码的前缀 可利用二叉树设计前缀编码 6 6 3 赫夫曼编码算法的实现 教学方法 教学方法 课堂讲解 例题演示 课件演示 辅助手段 辅助手段 电脑 投影仪 教科书 作 业 1 构造哈夫曼树 2 生成哈夫曼编码 主要 参考资料 算法与数据结构 C 语言版 范策 周世平 胡哓琨 等编著 机械工业出版社 2004 数据结构 C 语言版 严蔚敏等编著 清华大学出版社 2004 数据结构与算法 许卓群 杨冬青 唐世渭 张铭 高等教育出版社 2004 课后自我总 结分析 备注 36 教教案案 分分教教案案 课次 19 学时 2 章 节综合习题