2004/2005学年第二学期 授课计划 课程名称:数据结构[B] 授课班级:计算机2003级(本科) 学时数:48学时 其中讲课:48学时 执行的教学大纲(名称、制定日期) 数据结构》教学大纲 教材(名称、编著者、出版日期) 《数据结构一使用C++语言》主编:朱战立20012 主要参考书 1、《数据结枃(用面向对象方法与C艹+描述)》 股人昆等清华大学出版社 2、《数据结构(c语言版)》 严蔚敏等清华大学出版社 主讲教师 辅导教师 教研室主任(签字) 2005年2月20日订
2004/2005 学年 第 二学期 授 课 计 划 课 程 名 称：数据结构[B] 授 课 班 级：计算机 2003 级（本科） 学 时 数：48 学时 其中讲课：48 学时 执行的教学大纲（名称、制定日期） 《数据结构》教学大纲 教 材（名称、编著者、出版日期） 《数据结构－使用 C++语言》主编：朱战立 2001.2 主 要 参 考 书： 1、《数据结构（用面向对象方法与 C++描述）》 殷人昆 等 清华大学出版社 2、《数据结构(c 语言版)》 严蔚敏 等 清华大学出版社 主讲教师： 辅导教师： 教研室主任（签字）： 2005 年 2 月 20 日订
周别授课 需要作作时 顺序 授课章节的内容摘要时间业业 数量估 第1周第1讲第1掌绪论 0.5小时 1、数据结构课程的重要性 2、课程安排 3、回顾算法描述语言c++ 第1周第2第2章面向对象程序设计和算法性 2学 0.5小时 、抽象数据类型 1、数据结构 、数据类型 3、抽象数据类型 4、抽象数据类型的描述方法 5、抽象数据类型的特点 二、面向对象程序设计和类 对象 四、算法、算法设计目标和算法性能分析 1、算法 法设计目标 3、算法的时间效率 4、算法的符号命名、书写格式和注释格式 第2、314、5讲 第3顺序存储结构的表、堆栈和队列 2小时 、存储结构 二、表和顺序表 1顺序表的类定义 2顺序表的类实现 页序表上插入、删除算法的效率分析 4、顺序表的应用 、堆栈和顺序堆栈 1、顺序堆栈类定义和实现 2、顺序堆栈应用-表达式计算 四、队列和顺序队列 2 1、顺序循环队列 2、顺序循环队列类的定义和实现 3、顺序循环队列的应用 五、优先级队列和顺序优先级队列 1、顺序优先级队列类定义和类实现 2、顺序优先级队列应用 六、顺序存储结构的特点
周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作 业 数量 作 时 业 估 计 间 第1 周 第1 周 第 2、3 周 第 1 讲 第 2 讲 第 3、 4、5 讲 第 1 掌 绪论 1、 数据结构课程的重要性 2、 课程安排 3、 回顾算法描述语言 c++ 第 2 章 面向对象程序设计和算法性 一、抽象数据类型 1、数据结构 2、数据类型 3、抽象数据类型 4、抽象数据类型的描述方法 5、抽象数据类型的特点 二、面向对象程序设计和类 三、对象 四、算法、算法设计目标和算法性能分析 1、算法 2、算法设计目标 3、算法的时间效率 4、算法的符号命名、书写格式和注释格式 第 3 顺序存储结构的表、堆栈和队列 一、存储结构 二、表和顺序表 1 顺序表的类定义 2 顺序表的类实现 3、顺序表上插入、删除算法的效率分析 4、顺序表的应用 三、堆栈和顺序堆栈 1、顺序堆栈类定义和实现 2、顺序堆栈应用-表达式计算 四、队列和顺序队列 1、顺序循环队列 2、顺序循环队列类的定义和实现 3、顺序循环队列的应用 五、优先级队列和顺序优先级队列 1、 顺序优先级队列类定义和类实现 2、 顺序优先级队列应用 六、顺序存储结构的特点 2 学 时 2 学 时 6 学 时 1 2 3 1 2 0.5 小时 0.5 小时 2 小时
周别授课 需要作作时 顺序 授课章节的内容摘要 时间业业 数量估 第3、4第6、第4章链式存储结构表、堆栈和队列 6学|3 3小时 7、8讲 链式存储结构 、单链表 1、结点类的定义和实现 2、单链表类的定义和实现 3、单链表类的应用 、单循环链表 1、单循环链表类的定义和实现 2、单循环链表类的应用 四、双向循环链表 双向循环链表概念 2、双向循环链表类定义和实现 五、链式堆栈 1、链式堆栈类的定义和实现 2、链式堆栈类的应用 、链式队列 七、链式存储结构的特点 10学7 第5、第9、第7章树和二叉树 2小时 10 11、12|1、树的定义 、13讲2、树的表示方法 3、树的基本操作 树的存储结构 5、类 二、二叉树 叉树的定义 叉树的性质 3、二叉树的操作 4、二叉树的存储结构 5、树和二叉树的转换 、链式存储结构的二叉树设计 叉树结点类 2、二叉树的遍历 叉树遍历的应用 4、应用示例 4、二叉树类
周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作 业 数量 作 时 业 估 计 间 第 3、4 周 第 5、 6、7 周 第 6、 7、8 讲 第 9、 10 、 11、12 、13 讲 第 4 章 链式存储结构表、堆栈和队列 一、链式存储结构 二、单链表 1、 结点类的定义和实现 2、单链表类的定义和实现 3、单链表类的应用 三、单循环链表 1、 单循环链表类的定义和实现 2、 单循环链表类的应用 四、双向循环链表 1、 双向循环链表概念 2、 双向循环链表类定义和实现 五、链式堆栈 1、 链式堆栈类的定义和实现 2、 链式堆栈类的应用 六、链式队列 七、链式存储结构的特点 第 7 章 树和二叉树 一、树 1、 树的定义 2、树的表示方法 3、树的基本操作 4、树的存储结构 5、 类 二、二叉树 1、二叉树的定义 2、二叉树的性质 3、二叉树的操作 4、二叉树的存储结构 5、树和二叉树的转换 三、链式存储结构的二叉树设计 1、二叉树结点类 2、二叉树的遍历 3、二叉树遍历的应用 4、应用示例 4、 二叉树类 6 学 时 10 学 时 3 7 3 小时 2 小时
授课 需要作业作时业估 授课章节的内容摘要 时间数量计间 四、二叉树遍历游标类 叉树中序遍历游标类 2、二叉树前序遍历游标类 3、二叉树层序遍历游标类 五、线索二叉树 线索二叉树的存储结构 2、线索二叉树类 3、中序线索二叉树类 堆(介绍 1、堆的定义 2、最小堆类 3、最小堆类的测试 七、哈夫曼树 1、路径长度和哈夫曼树 2、哈夫曼编码 3、哈夫曼编码问题数据结构设计 4、哈夫曼编码问题算法设计 第7、第 第8章图 10学4 2.5小时 8、9周1 16 图的基本概念和基本操作 17、181、图的基本概念 2、图的基本操作 、图的邻接矩阵存储结构 1、邻接矩阵 2、邻接矩阵表示的图类 3、邻接矩阵图类的深度优先搜索遍历 4、邻接矩阵图类的广度优先搜索遍历 5、非连通图和连通分量 6、邻接矩阵图类的测试 三、图的邻接表存储结构 1、图的邻接表存储结构 2、邻接表存储结构的图类 3、邻接表存储结构图类的测试 知识点:图的邻接表存储方式 四、图的其他存储结构 1、逆邻接表 2、十字链表 3、邻接多重表 五、最小生成树 1、最小生成树的基本概念 2、普里姆算法 3、克鲁斯卡尔算法
授课 顺序 授 课 章 节 的 内 容 摘 要 需要 时间 作业 数量 作 时业估 计 间 第 7、 8、9 周 第 14、 15 、 16 、 17、18 讲 四、二叉树遍历游标类 1、二叉树中序遍历游标类 2、二叉树前序遍历游标类 3、二叉树层序遍历游标类 五、线索二叉树 1、线索二叉树的存储结构 2、线索二叉树类 3、中序线索二叉树类 六、堆（介绍） 1、堆的定义 2、最小堆类 3、最小堆类的测试 七、哈夫曼树 1、路径长度和哈夫曼树 2、哈夫曼编码 3、哈夫曼编码问题数据结构设计 4、哈夫曼编码问题算法设计 第 8 章 图 一、 图的基本概念和基本操作 1、 图的基本概念 2、 图的基本操作 二、图的邻接矩阵存储结构 1、 邻接矩阵 2、 邻接矩阵表示的图类 3、 邻接矩阵图类的深度优先搜索遍历 4、 邻接矩阵图类的广度优先搜索遍历 5、 非连通图和连通分量 6、 邻接矩阵图类的测试 三、图的邻接表存储结构 1、图的邻接表存储结构 2、邻接表存储结构的图类 3、邻接表存储结构图类的测试 知识点：图的邻接表存储方式 四、图的其他存储结构 1、 逆邻接表 2、 十字链表 3、 邻接多重表 五、最小生成树 1、 最小生成树的基本概念 2、 普里姆算法 3、 克鲁斯卡尔算法 10 学 时 4 2.5 小时
需要作作时 顺序授课章节的内容摘要 时间业业 数量估 第 第19、第9章排序 6学[31小时 11周|20、21 排序的基本概念 、插入排序 直接插入排序 2、链表插入排序 3、希尔排序 选择排序 1、直接选择排序 2、堆排序 四、交换排序 1、冒泡排序 2、快速排序 五、归并排序 六、基数排序 第22、 第11 第10章查找 6学3 12周 查找的基本概念 顺序表查找 1、无序顺序表顺序查找 2、有序顺序表查找 、索引表查找 1、索引表结构 2、索引结构查找的效率分析 3、倒排索引表 四、树表查找 1、二叉排序树 2、二叉排序树类 3、二叉排序树的性能分析 4、平衡二叉树 五、哈希表查找 1、哈希表的基本概念 2、哈希函数构造方法 3、哈希冲突解决方法 4、哈希表类 总结全课程
授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作业 数量 作 时 业估计 间 第 10 、 11 周 第 11 、 12 周 第 19 、 20 、21 讲第 22 、 23 、24 讲 第 9 章 排 序 一、 排序的基本概念 二、 插入排序 1、 直接插入排序 2、 链表插入排序 3、 希尔排序 三、选择排序 1、 直接选择排序 2、 堆排序 四、交换排序 1、 冒泡排序 2、 快速排序 五、归并排序 六、基数排序 第 10 章 查找 一、 查找的基本概念 二、 顺序表查找 1、 无序顺序表顺序查找 2、 有序顺序表查找 三、索引表查找 1、 索引表结构 2、 索引结构查找的效率分析 3、 倒排索引表 四、树表查找 1、 二叉排序树 2、 二叉排序树类 3、 二叉排序树的性能分析 4、 平衡二叉树 五、哈希表查找 1、 哈希表的基本概念 2、 哈希函数构造方法 3、 哈希冲突解决方法 4、 哈希表类 总结全课程 6 学 时6 学 时 3 1 小时 3 1 小时