|
大小: 6873
备注:
|
大小: 12666
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 3: | 行号 3: |
| * 课程名称：数据结构 | * 课程名称：["数据结构"] |
| 行号 5: | 行号 5: |
| * 教材：数据结构 * 授课教师：陈忠克 |
* 教材：[:数据结构教材:数据结构——C语言描述] * 授课教师：[:czk:陈忠克] |
| 行号 18: | 行号 18: |
| 数据结构中的基本概念和术语 == 本授课单元教学目标： == 让学生了解计算机程序设计语言的发展；理解面向对象的概念和方法；理解程序的开发过程和面向对象程序的开发过程。 == 本授课单元教学重点和难点： == 面向对象的方法 == 本授课单元教学过程设计： == * 基础知识 * 参考书 * 如何学习C++和面向对象编程 * 结构化的程序设计 * 面向对象程序设计基本原理 * 面向对象的三个特点 * 面向对象程序设计的作用 * 计算机语言的发展 * 程序设计范式 * 程序执行方式 * 为什么选择C++ * C++语言的发展历史 * C++开发环境 * 常用集成开发环境 * C++程序开发流程 |
[:数据结构概述:数据结构中的基本概念和术语] == 本授课单元教学目标： == 熟悉数据结构中各名词、术语的含义，掌握其基本概念；理解数据类型和抽象数据类型的含义；理解算法五个要素的确切含义，注意算法与程序的区别；掌握计算语句频度和估算算法时间复杂度的方法。 == 本授课单元教学重点和难点： == * 重点：数据结构中的基本概念、算法复杂度 * 难点：算法复杂度分析 == 本授课单元教学过程设计： == 1. （5分钟）介绍计算机处理信息的类型 1. （15分钟）实例分析数据结构可以解决的问题（电话号码查询问题、田径赛的时间安排问题） 1. （10分钟）介绍数据结构的课程安排 1. （20分钟）介绍数据、数据元素、逻辑结构、存储结构、运算、数据结构等概念 1. （5分钟）介绍抽象数据类型的概念 1. （5分钟）介绍算法的概念以及算法的基本要求 1. （20分钟）介绍算法时间复杂度和空间复杂度的表示方式和分析的方法 1. （10分钟）实例分析算法的时间复杂度 |
| 行号 51: | 行号 45: |
| 线性表 == 本授课单元教学目标： == 让学生掌握C++与C语言的不同，包括注释、输入输出、命名空间。 == 本授课单元教学重点和难点： == * 重点：C++输入输出 * 难点：命名空间 == 本授课单元教学过程设计： == 1. 简单的C++程序实例 1. 第一个C++程序 输出Hello world 1. 第二个C++程序 求两数之和 1. 第三个C++程序 求两个数中较大的一个 1. 引出C++的新的注释风格 1. 引出名字空间语法，为什么需要名字空间 1. 引出C++的头文件习惯 1. 引出C++的输入输出，介绍相对于C语言输入输出的好处 1. 练习使用C++的输入输出 |
["线性表"] == 本授课单元教学目标： == 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。 == 本授课单元教学重点和难点： == * 重点：顺序表和链表的实现 * 难点：链表的实现 == 本授课单元教学过程设计： == 1. （20分钟）介绍线性表的概念、特点和操作 1. （20分钟）线性表的顺序存储的原理 1. （20分钟）线性表的顺序存储结构的定义 1. （30分钟）线性表的顺序存储简单操作的实现 1. （20分钟）练习：顺序表的翻转和合并等操作 1. （20分钟）线性表的链式存储的原理 1. （20分钟）线性表的链式存储结构 1. （30分钟）线性表的链式存储简单操作的实现 1. （30分钟）练习：链表的合并和翻转等操作 1. （30分钟）循环链表的概念、特点和实现 1. （30分钟）双向链表的概念、特点和实现 1. （40分钟）线性表的具体应用：一元多项式的表示和操作 1. （20分钟）顺序表与链表的比较 1. （30分钟）综合练习（约瑟夫环等问题） |
| 行号 80: | 行号 78: |
| 栈和队列 == 本授课单元教学目标： == 掌握引用类型的使用，理解函数的引用参数传递，返回引用类型 == 本授课单元教学重点和难点： == * 重点：引用参数传递 * 难点：引用返回类型 == 本授课单元教学过程设计： == 1. 引用的定义 1. 由swap函数引出引用参数的定义和用途 1. 引用返回类型的定义和用途 1. const引用的定义和用途 1. 定义常量 1. 强制类型转换 1. bool类型 1. 定义变量 1. 结构体 |
["栈"]和["队列"] == 本授课单元教学目标： == 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。 == 本授课单元教学重点和难点： == * 重点：栈和队列的概念、实现，栈的应用 * 难点：循环队列的实现 == 本授课单元教学过程设计： == 1. （20分钟）栈的定义、特点和基本操作 1. （15分钟）顺序栈的表示和原理 1. （30分钟）顺序栈的定义和实现 1. （15分钟）链栈的表示和原理 1. （20分钟）链栈的定义和实现 1. （30分钟）栈的应用：括号匹配 1. （20分钟）队列的定义、特点和基本操作 1. （40分钟）循环队列的表示和基本操作 1. （30分钟）链式队列的表示和基本操作 1. （20分钟）队列的应用：输入缓冲 1. （30分钟）综合练习：医院模拟 |
| 行号 110: | 行号 109: |
| 串 == 本授课单元教学目标： == 掌握内联函数、带缺省参数的函数的语法和适用场合；掌握函数重载的用途、定义。 == 本授课单元教学重点和难点： == * 重点：函数重载、缺省参数 |
["串"] == 本授课单元教学目标： == 熟悉串的定义及串的基本操作；熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；了解串的堆存储结构及块链存储结构；掌握串的模式匹配算法的基本算法，了解其改进算法。 == 本授课单元教学重点和难点： == * 重点： * 难点：KMP算法 == 本授课单元教学过程设计： == 1. （20分钟）串的定义 1. （20分钟）串的表示和实现 1. （15分钟）串的简单模式匹配算法 1. （35分钟）KMP算法 = 第五课 = == 授课时间： == 4课时 == 授课类型： == 理论课 == 授课题目： == [:数组(数据结构):数组]和["广义表"] == 本授课单元教学目标： == 了解数组的存储结构，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，掌握以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。 == 本授课单元教学重点和难点： == * 重点：稀疏矩阵 |
| 行号 120: | 行号 142: |
| * 函数的声明与定义 * 由带参数宏引出内联函数 * 由很多参数的函数引出代缺省参数的函数 * 重载函数 = 第五课 = == 授课时间： == 4课时 == 授课类型： == 理论课 == 授课题目： == 数组 == 本授课单元教学目标： == 掌握C++内存分配、bool类型、string类型、变量定义规则、新型强制类型转换语法、const常量定义。 == 本授课单元教学重点和难点： == * 重点：string类型 * 难点：内存分配 == 本授课单元教学过程设计： == * 介绍const常量定义 * 介绍bool类型 * 介绍四种强制类型转换 * 介绍C++变量可以在多种地方定义 * 对比C语言和C++语言的内存分配 * 对比C语言的字符串和C++的string类 |
1. （15分钟）数组的定义 1. （20分钟）数组的顺序存储表示和实现 1. （20分钟）稀疏矩阵的概念 1. （35分钟）稀疏矩阵的三元组表示 1. （45分钟）稀疏矩阵的三元组表示的操作实现 1. （45分钟）广义表的基本概念 |
| 行号 158: | 行号 157: |
| 树和二叉树 == 本授课单元教学目标： == 掌握面向对象程序设计的基本概念，牢固掌握类的声明，类成员的访问控制，类的成员函数，对象的声明等类与对象的基本语法内容 == 本授课单元教学重点和难点： == 重点：成员函数 难点：成员函数、访问权限 == 本授课单元教学过程设计： == 1. 用例子说明C语言中定义自定义类型的方法：用C语言结构体定义自定义类型，用函数实现操作结构体的方法 1. 将C语言的结构体和操作结构体的函数结合在一起，引出C++类的概念 1. 举例说明C++类的语法 1. 举例说明对象的定义方法 1. 练习类和对象的使用 1. 举例说明类成员的访问权限控制 |
["树和二叉树"] == 本授课单元教学目标： == 熟练掌握二叉树的结构特性(五个性质)，了解相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围；遍历二叉树是二叉树各种操作的基础，熟练掌握各种遍历策略的递归算法，了解其非递归算法；熟悉树的各种存储结构及其特点，掌握树和森林与二叉树之间的相互转换方法；了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法。 == 本授课单元教学重点和难点： == 重点：树与二叉树的概念，二叉树的性质，二叉树的存储表示和实现，二叉树的遍历算法 难点：Huffman算法和Huffman编码 == 本授课单元教学过程设计： == 1. （30分钟）树的基本概念 1. （20分钟）二叉树的概念 1. （40分钟）二叉树的性质 1. （30分钟）二叉树的存储表示 1. （30分钟）二叉树的递归创建算法 1. （30分钟）二叉树的前序、中序、后序遍历原理 1. （30分钟）二叉树的遍历算法的递归实现 1. （30分钟）二叉树的遍历算法的非递归实现 1. （30分钟）线索二叉树的作用和原理 1. （30分钟）练习：二叉树简单算法的实现（统计叶子个数、计算结点的总和等） 1. （30分钟）树和森林的存储表示和实现 1. （30分钟）树和森林与二叉树之间的相互转换 1. （30分钟）Huffman算法的原理和用途 1. （30分钟）Huffman算法的实现 1. （30分钟）Huffman编码的原理和实现 |
| 行号 184: | 行号 195: |
| 图 == 本授课单元教学目标： == 牢固掌握构造函数和析构函数，拷贝构造函数的概念和写法 == 本授课单元教学重点和难点： == * 重点：构造函数 * 难点：拷贝构造函数 == 本授课单元教学过程设计： == 1. 举例说明构造函数的作用 1. 介绍构造函数的定义语法 1. 举例说明构造函数可以重载 1. 举例说明调用构造函数定义对象的方法 1. 组合对象的构造 1. 举例说明对象的析构函数的作用 1. 举例说明拷贝构造函数的作用 1. 练习构造函数、拷贝构造函数、析构函数的使用 |
["图"] == 本授课单元教学目标： == 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径（深度优先和广度优先）的遍历算法，注意图的遍历算法与树的遍历算法之间的类似和差异；熟练掌握求最小生成树的Prim算法。 == 本授课单元教学重点和难点： == * 重点：图的基本概念、图的存储结构、图的遍历算法、拓扑排序算法、最小生成树算法、最短路径算法 * 难点：最短路径算法 == 本授课单元教学过程设计： == 1. （30分钟）图的定义和基本概念 1. （20分钟）图的邻接矩阵存储结构 1. （30分钟）图的邻接表和逆邻接表存储结构 1. （30分钟）图的创建算法 1. （20分钟）图的深度优先遍历算法的原理 1. （20分钟）图的深度优先遍历算法的实现 1. （20分钟）图的广度优先遍历算法的原理 1. （20分钟）图的广度优先遍历算法的实现 1. （15分钟）图的最小生成树的概念 1. （20分钟）最小生成树的Prim算法的原理 1. （20分钟）最小生成树的Kruskal算法的原理 1. （30分钟）最短路径djikstra算法的原理 1. （25分钟）最短路径djikstra算法的实现 1. （30分钟）拓扑排序算法的原理 1. （30分钟）练习：图的简单算法实现（存储结构的转换） |
| 行号 210: | 行号 232: |
| 查找 == 本授课单元教学目标： == 牢固掌握静态数据成员的定义，掌握静态成员函数的定义和使用；理解并掌握友元函数和友元类，friend保留字；理解并掌握常引用、常对象和常成员函数。 == 本授课单元教学重点和难点： == * 重点： * 难点：静态成员 == 本授课单元教学过程设计： == 1. 举例说明静态数据成员的用途 1. 举例说明静态成员函数的用途 1. 练习使用静态成员 1. 举例说明友员函数的作用 1. 举例说明友员类的作用 1. 举例说明常成员函数的用法 1. 举例说明常对象的用法 |
["查找"] == 本授课单元教学目标： == 熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 == 本授课单元教学重点和难点： == * 重点：折半查找算法、二叉排序树的概念及有关算法、平衡二叉排序树的概念、哈希表的概念和算法 * 难点：平衡二叉树有关算法 == 本授课单元教学过程设计： == 1. （20分钟）查找表的基本概念 1. （15分钟）顺序查找算法的原理和实现 1. （20分钟）折半查找算法的原理和实现 1. （25分钟）平均查找长度的概念和分析 1. （20分钟）二叉排序树的定义 1. （20分钟）二叉树的创建方法和实现 1. （20分钟）二叉树的查找算法和实现 1. （20分钟）平衡二叉树的定义，AVL树的定义 1. （45分钟）AVL平衡算法的原理 1. （30分钟）练习：AVL树的创建 1. （15分钟）哈希表的概念 1. （30分钟）哈希函数的实现 1. （30分钟）哈希表处理冲突的方法 1. （20分钟）哈希表的查找过程和性能分析 1. （30分钟）练习：哈希表创建和查找 |
| 行号 236: | 行号 268: |
| 内部排序 == 本授课单元教学目标： == 掌握派生类的声明，派生的访问控制；理解派生类的构造和析构函数。 == 本授课单元教学重点和难点： == * 重点：继承的概念，派生类定义方法，派生类的构造 * 难点：派生类的权限 == 本授课单元教学过程设计： == 1. 举实例说明继承的概念 1. 派生类的定义方法 1. 举例说明派生类的初始化方法，构造函数的定义 1. 举例说明派生类的析构函数 1. 举例说明派生类的权限控制 |
内部["排序"] == 本授课单元教学目标： == 了解排序的定义和各种排序方法的特点，熟悉各种方法的排序过程及其依据的原则；熟练掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序的实现算法；掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。 == 本授课单元教学重点和难点： == * 重点：直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序，各种排序方法的比较 * 难点：堆排序 == 本授课单元教学过程设计： == 1. （20分钟）排序的概念和特性 1. （20分钟）直接插入排序的原理和实现 1. （25分钟）冒泡排序的原理和实现 1. （25分钟）简单选择排序的原理和实现 1. （45分钟）快速排序的原理和实现 1. （45分钟）堆排序的原理和实现 1. （40分钟）归并排序的原理和实现 1. （30分钟）各种排序方法的比较 1. （20分钟）综合练习：各种排序方法的选择 |
温州大学课程教案
- 学院：计算机科学与学院
- 课程名称：["数据结构"]
- 学时：54
- 教材：[:数据结构教材:数据结构——C语言描述]
- 授课教师：[:czk:陈忠克]
- 授课对象：计算机本科
第一课
1. 授课时间：
2课时
2. 授课类型：
理论课
3. 授课题目：
[:数据结构概述:数据结构中的基本概念和术语]
4. 本授课单元教学目标：
熟悉数据结构中各名词、术语的含义，掌握其基本概念；理解数据类型和抽象数据类型的含义；理解算法五个要素的确切含义，注意算法与程序的区别；掌握计算语句频度和估算算法时间复杂度的方法。
5. 本授课单元教学重点和难点：
- 重点：数据结构中的基本概念、算法复杂度
- 难点：算法复杂度分析
6. 本授课单元教学过程设计：
- （5分钟）介绍计算机处理信息的类型
- （15分钟）实例分析数据结构可以解决的问题（电话号码查询问题、田径赛的时间安排问题）
- （10分钟）介绍数据结构的课程安排
- （20分钟）介绍数据、数据元素、逻辑结构、存储结构、运算、数据结构等概念
- （5分钟）介绍抽象数据类型的概念
- （5分钟）介绍算法的概念以及算法的基本要求
- （20分钟）介绍算法时间复杂度和空间复杂度的表示方式和分析的方法
- （10分钟）实例分析算法的时间复杂度
第二课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
["线性表"]
4. 本授课单元教学目标：
了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。
5. 本授课单元教学重点和难点：
- 重点：顺序表和链表的实现
- 难点：链表的实现
6. 本授课单元教学过程设计：
- （20分钟）介绍线性表的概念、特点和操作
- （20分钟）线性表的顺序存储的原理
- （20分钟）线性表的顺序存储结构的定义
- （30分钟）线性表的顺序存储简单操作的实现
- （20分钟）练习：顺序表的翻转和合并等操作
- （20分钟）线性表的链式存储的原理
- （20分钟）线性表的链式存储结构
- （30分钟）线性表的链式存储简单操作的实现
- （30分钟）练习：链表的合并和翻转等操作
- （30分钟）循环链表的概念、特点和实现
- （30分钟）双向链表的概念、特点和实现
- （40分钟）线性表的具体应用：一元多项式的表示和操作
- （20分钟）顺序表与链表的比较
- （30分钟）综合练习（约瑟夫环等问题）
第三课
1. 授课时间：
6课时
2. 授课类型：
理论课
3. 授课题目：
["栈"]和["队列"]
4. 本授课单元教学目标：
掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。
5. 本授课单元教学重点和难点：
- 重点：栈和队列的概念、实现，栈的应用
- 难点：循环队列的实现
6. 本授课单元教学过程设计：
- （20分钟）栈的定义、特点和基本操作
- （15分钟）顺序栈的表示和原理
- （30分钟）顺序栈的定义和实现
- （15分钟）链栈的表示和原理
- （20分钟）链栈的定义和实现
- （30分钟）栈的应用：括号匹配
- （20分钟）队列的定义、特点和基本操作
- （40分钟）循环队列的表示和基本操作
- （30分钟）链式队列的表示和基本操作
- （20分钟）队列的应用：输入缓冲
- （30分钟）综合练习：医院模拟
第四课
1. 授课时间：
2课时
2. 授课类型：
理论课
3. 授课题目：
["串"]
4. 本授课单元教学目标：
熟悉串的定义及串的基本操作；熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；了解串的堆存储结构及块链存储结构；掌握串的模式匹配算法的基本算法，了解其改进算法。
5. 本授课单元教学重点和难点：
- 重点：
- 难点：KMP算法
6. 本授课单元教学过程设计：
- （20分钟）串的定义
- （20分钟）串的表示和实现
- （15分钟）串的简单模式匹配算法
- （35分钟）KMP算法
第五课
1. 授课时间：
4课时
2. 授课类型：
理论课
3. 授课题目：
[:数组(数据结构):数组]和["广义表"]
4. 本授课单元教学目标：
了解数组的存储结构，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，掌握以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。
5. 本授课单元教学重点和难点：
- 重点：稀疏矩阵
- 难点：
6. 本授课单元教学过程设计：
- （15分钟）数组的定义
- （20分钟）数组的顺序存储表示和实现
- （20分钟）稀疏矩阵的概念
- （35分钟）稀疏矩阵的三元组表示
- （45分钟）稀疏矩阵的三元组表示的操作实现
- （45分钟）广义表的基本概念
第六课
1. 授课时间：
10课时
2. 授课类型：
理论课
3. 授课题目：
["树和二叉树"]
4. 本授课单元教学目标：
熟练掌握二叉树的结构特性(五个性质)，了解相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围；遍历二叉树是二叉树各种操作的基础，熟练掌握各种遍历策略的递归算法，了解其非递归算法；熟悉树的各种存储结构及其特点，掌握树和森林与二叉树之间的相互转换方法；了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法。
5. 本授课单元教学重点和难点：
重点：树与二叉树的概念，二叉树的性质，二叉树的存储表示和实现，二叉树的遍历算法 难点：Huffman算法和Huffman编码
6. 本授课单元教学过程设计：
- （30分钟）树的基本概念
- （20分钟）二叉树的概念
- （40分钟）二叉树的性质
- （30分钟）二叉树的存储表示
- （30分钟）二叉树的递归创建算法
- （30分钟）二叉树的前序、中序、后序遍历原理
- （30分钟）二叉树的遍历算法的递归实现
- （30分钟）二叉树的遍历算法的非递归实现
- （30分钟）线索二叉树的作用和原理
- （30分钟）练习：二叉树简单算法的实现（统计叶子个数、计算结点的总和等）
- （30分钟）树和森林的存储表示和实现
- （30分钟）树和森林与二叉树之间的相互转换
- （30分钟）Huffman算法的原理和用途
- （30分钟）Huffman算法的实现
- （30分钟）Huffman编码的原理和实现
第七课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
["图"]
4. 本授课单元教学目标：
熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径（深度优先和广度优先）的遍历算法，注意图的遍历算法与树的遍历算法之间的类似和差异；熟练掌握求最小生成树的Prim算法。
5. 本授课单元教学重点和难点：
- 重点：图的基本概念、图的存储结构、图的遍历算法、拓扑排序算法、最小生成树算法、最短路径算法
- 难点：最短路径算法
6. 本授课单元教学过程设计：
- （30分钟）图的定义和基本概念
- （20分钟）图的邻接矩阵存储结构
- （30分钟）图的邻接表和逆邻接表存储结构
- （30分钟）图的创建算法
- （20分钟）图的深度优先遍历算法的原理
- （20分钟）图的深度优先遍历算法的实现
- （20分钟）图的广度优先遍历算法的原理
- （20分钟）图的广度优先遍历算法的实现
- （15分钟）图的最小生成树的概念
- （20分钟）最小生成树的Prim算法的原理
- （20分钟）最小生成树的Kruskal算法的原理
- （30分钟）最短路径djikstra算法的原理
- （25分钟）最短路径djikstra算法的实现
- （30分钟）拓扑排序算法的原理
- （30分钟）练习：图的简单算法实现（存储结构的转换）
第八课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
["查找"]
4. 本授课单元教学目标：
熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
5. 本授课单元教学重点和难点：
- 重点：折半查找算法、二叉排序树的概念及有关算法、平衡二叉排序树的概念、哈希表的概念和算法
- 难点：平衡二叉树有关算法
6. 本授课单元教学过程设计：
- （20分钟）查找表的基本概念
- （15分钟）顺序查找算法的原理和实现
- （20分钟）折半查找算法的原理和实现
- （25分钟）平均查找长度的概念和分析
- （20分钟）二叉排序树的定义
- （20分钟）二叉树的创建方法和实现
- （20分钟）二叉树的查找算法和实现
- （20分钟）平衡二叉树的定义，AVL树的定义
- （45分钟）AVL平衡算法的原理
- （30分钟）练习：AVL树的创建
- （15分钟）哈希表的概念
- （30分钟）哈希函数的实现
- （30分钟）哈希表处理冲突的方法
- （20分钟）哈希表的查找过程和性能分析
- （30分钟）练习：哈希表创建和查找
第九课
1. 授课时间：
6课时
2. 授课类型：
理论课
3. 授课题目：
内部["排序"]
4. 本授课单元教学目标：
了解排序的定义和各种排序方法的特点，熟悉各种方法的排序过程及其依据的原则；熟练掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序的实现算法；掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
5. 本授课单元教学重点和难点：
- 重点：直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序，各种排序方法的比较
- 难点：堆排序
6. 本授课单元教学过程设计：
- （20分钟）排序的概念和特性
- （20分钟）直接插入排序的原理和实现
- （25分钟）冒泡排序的原理和实现
- （25分钟）简单选择排序的原理和实现
- （45分钟）快速排序的原理和实现
- （45分钟）堆排序的原理和实现
- （40分钟）归并排序的原理和实现
- （30分钟）各种排序方法的比较
- （20分钟）综合练习：各种排序方法的选择