计算机科学与技术学院 数据结构教案 西南科技大学计算机科学与技术学院 理论课程教案 学期 2006-2007学年(2) 课程名称 数据结构— 授课对象 。计算机科学与技术专业05级 学时数 56学时 教学大纲《数据结构》教学大纲_ 教材名称《数据结构一一使用C++语言》朱战立20052 西安电子科技大学出版社 参考教材1《数据结构(用面向对象方法与C++描述)》 殷人昆等清华大学出版社 2《数据结构c语言版)》严蔚敏清华大学出版社 3、数据结构与问题求解(C艹版)(第二版) (美 Mark allen weiss著张丽萍译清华大学出版社 主讲教师_ 李学俊 西南科技大学计算机科学与技术学院 http://www.cs.swust.edu.cn/
计算机科学与技术学院 数据结构教案 第1 页 西南科技大学计算机科学与技术学院 理 论 课 程 教 案 学 期 2006~2007 学年（2） 课程名称 数据结构 授课对象 计算机科学与技术专业 05 级 学 时 数 56 学时 教学大纲 《数据结构》教学大纲 教材名称 《数据结构――使用 C++语言》朱战立 2005.2 西安电子科技大学出版社 参考教材 1《数据结构（用面向对象方法与 C++描述）》 殷人昆 等 清华大学出版社 2《数据结构(c 语言版)》严蔚敏清华大学出版社 3、数据结构与问题求解（C++版）（第二版） (美)Mark Allen Weiss 著张丽萍译清华大学出版社 主讲教师 李学俊 西南科技大学计算机科学与技术学院 http://www.cs.swust.edu.cn/
计算机科学与技术学院 数据结构教案 第2页 目录 1、课程教学总体设计 (3) 2、授课计划表 3、课程教案 (9) 4、课程教学总结 (19)
计算机科学与技术学院 数据结构教案 第2 页 目 录 1、课程教学总体设计 ……………………………………（ 3 ） 2、授课计划表….…………………………………………（ 4 ） 3、课程教案 ……………………………………………（ 9 ） 4、课程教学总结 ……………………………………… （ 19 ）
计算机科学与技术学院 数据结构教案 课程教学总体设计 该课程是计算机科学与技术专业的一门专业核心基础课。该课程是在学 生掌握了一门程序设计语言的基础上开设的一门专业课。通过本课程的学 习,使学生学会分析研究计算机加工的数据的结构特性,掌握基本的数据 组织、数据存储及数据处理的方法,掌握算法的效率分析方法,培养学生 根据实际问题的需要选择和设计合适的逻辑结构、存储结构及算法的能力。 教学主要包括以下内容 1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结 构和算法,了解串、广义表、文件、优先队列、线索二叉树、回溯法,掌 握顺序存储、链式存储、索引存储和散列存储; 2、掌握递归方法 3、掌握插入排序、选择排序和交换排序,理解归并排序、基数排序; 4、掌握顺序表查找、索引表査找、散列表查找和树表查找 5、能运用时间和空间复杂度分析算法的效率 6、能针对实际问题,选择和设计合适的逻辑结构、存储结构及算法。 教学方法 1多媒体课件加实际操作演示授课方式 教师完成对基本概念和相关操作的讲解并在此基础上利用编程语 言将相应程序在计算机上进行实际的运行演示。强调理论和实践的结 合 2案例教学 在教学中多使用实例,以增强学生的实战能力。在教学过程中要避 免简单的概念讲解,安排具有实际应用意义的示例进行示范讲解。 3考核方式 采用结构化评分,总成绩中建议平时成绩(作业、课堂提问、案例 分析、课堂测试等)占50%、期未笔试成绩占50%
计算机科学与技术学院 数据结构教案 第3 页 课 程 教 学 总 体 设 计 该课程是计算机科学与技术专业的一门专业核心基础课。该课程是在学 生掌握了一门程序设计语言的基础上开设的一门专业课。通过本课程的学 习，使学生学会分析研究计算机加工的数据的结构特性，掌握基本的数据 组织、数据存储及数据处理的方法，掌握算法的效率分析方法，培养学生 根据实际问题的需要选择和设计合适的逻辑结构、存储结构及算法的能力。 教学主要包括以下内容： 1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结 构和算法，了解串、广义表、文件、优先队列、线索二叉树、回溯法，掌 握顺序存储、链式存储、索引存储和散列存储； 2、掌握递归方法； 3、掌握插入排序、选择排序和交换排序，理解归并排序、基数排序； 4、掌握顺序表查找、索引表查找、散列表查找和树表查找； 5、能运用时间和空间复杂度分析算法的效率； 6、能针对实际问题，选择和设计合适的逻辑结构、存储结构及算法。 教学方法： 1 多媒体课件加实际操作演示授课方式。 教师完成对基本概念和相关操作的讲解，并在此基础上利用编程语 言将相应程序在计算机上进行实际的运行演示。强调理论和实践的结 合。 2 案例教学 在教学中多使用实例，以增强学生的实战能力。在教学过程中要避 免简单的概念讲解，安排具有实际应用意义的示例进行示范讲解。 3 考核方式 采用结构化评分，总成绩中建议平时成绩（作业、课堂提问、案例 分析、课堂测试等）占 50%、期末笔试成绩占 50%
计算机科学与技术学院 数据结构教案 2006/2007学年第二学期 授课计划 课程名称:数据结构 授课班级:计算机2005级(本科) 学时数:56学时 其中讲课:56学时 执行的教学大纲(名称、制定日期) 《数据结构》教学大纲 教材(名称、编著者、出版日期) 《数据结构一使用C++语言》主编:朱战立2001.2 主要参考书 1、《数据结构(用面向对象方法与C艹+描述)》 殷人昆等清华大学出版社 2、《数据结构(c语言版)》 严蔚敏等清华大学出版社 3、数据结构与问题求解(C++版)(第二版) (美) Mark allen Weiss著张丽萍译 清华大学出版社 主讲教师:李学俊 辅导教师 教研室主任(签字):曾立胜 2007年2月20日订
计算机科学与技术学院 数据结构教案 第4 页 2006/2007 学年 第 二学期 授 课 计 划 课 程 名 称：数据结构 授 课 班 级：计算机 2005 级（本科） 学 时 数：56 学时 其中讲课：56 学时 执行的教学大纲（名称、制定日期） 《数据结构》教学大纲 教 材（名称、编著者、出版日期） 《数据结构－使用 C++语言》主编：朱战立 2001.2 主 要 参 考 书： 1、《数据结构（用面向对象方法与 C++描述）》 殷人昆 等 清华大学出版社 2、《数据结构(c 语言版)》 严蔚敏 等 清华大学出版社 3、数据结构与问题求解（C++版）（第二版） （美）Mark Allen Weiss 著 张丽萍译 清华大学出版社 主讲教师： 李学俊 辅导教师： 教研室主任（签字）： 曾立胜 2007 年 2 月 20 日订
计算机科学与技术学院 数据结构教案 周别授课 需要作业作业估计 授课章节的内容摘要 时间数量时间 1第1章C艹面向对象程序设计要点 0.5小时 1、函数和函数参数 2、输入和输出 4、抽象类型和模板 第2章面向对象程序设计和算法性 2学 0.5小时 抽象数据类型 1、数据结构 数据类型 3、抽象数据类型 、抽象数据类型的描述方法 5、抽象数据类型的特点 二、面向对象程序设计和类 三、对象 四、算法、算法设计目标和算法性能分析 1、算法 2、算法设计目标 算法的时间效率 4、算法的符号命名、书写格式和注释格式 第3顺序存储结构的表、堆栈和队列 存储结构 表和顺序表 1顺序表的类定义 2顺序表的类实现 顺序表上插入、删除算法的效率分析 顺序表的应用 三、堆栈和顺序堆栈 2学 0.5小时 1、顺序堆栈类定义和实现 2、顺序堆栈应用表达式计算 四、队列和顺序队列 1、顺序循环队列 2学 15小时 2、顺序循环队列类的定义和实现 3、顺序循环队列的应用 五、优先级队列和顺序优先级队列 1、顺序优先级队列类定义和类实现 2、顺序优先级队列应用 六、顺序存储结构的特点
计算机科学与技术学院 数据结构教案 第5 页 周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作业 数量 作业估计 时间 1 1 2 2 3 1 2 3 4 5 第 1 章 C++面向对象程序设计要点 1、 函数和函数参数 2、 输入和输出 3、 类 4、 抽象类型和模板 第 2 章 面向对象程序设计和算法性 一、抽象数据类型 1、数据结构 2、数据类型 3、抽象数据类型 4、抽象数据类型的描述方法 5、抽象数据类型的特点 二、面向对象程序设计和类 三、对象 四、算法、算法设计目标和算法性能分析 1、算法 2、算法设计目标 3、算法的时间效率 4、算法的符号命名、书写格式和注释格式 第 3 顺序存储结构的表、堆栈和队列 一、存储结构 二、表和顺序表 1 顺序表的类定义 2 顺序表的类实现 3、顺序表上插入、删除算法的效率分析 4、顺序表的应用 三、堆栈和顺序堆栈 1、顺序堆栈类定义和实现 2、顺序堆栈应用-表达式计算 四、队列和顺序队列 1、顺序循环队列 2、顺序循环队列类的定义和实现 3、顺序循环队列的应用 五、优先级队列和顺序优先级队列 1、 顺序优先级队列类定义和类实现 2、 顺序优先级队列应用 六、顺序存储结构的特点 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 1 2 1 2 0.5 小时 0.5 小时 0.5 小时 1.5 小时
计算机科学与技术学院 数据结构教案 周别授课 需要作业作业估计 顺序 授课章节的内容摘要 时间数量|时间 第4章链式存储结构表、堆栈和队列 3小时 链式存储结构 单链表 结点类的定义和实现 2、单链表类的定义和实现 3、单链表类的应用 三、单循环链表 2学 1、单循环链表类的定义和实现 2、单循环链表类的应用 双向循环链表 1、双向循环链表概念 2、双向循环链表类定义和实现 五、链式堆栈 1、链式堆栈类的定义和实现 2学 2、链式堆栈类的应用 六、链式队列 七、链式存储结构的特点 5 第5章数组和串 2学 1小时 1、数组 2、特殊矩阵的压缩存储 3、稀疏矩阵的压缩存储 串 2学 第6章递归 1、递归的概念 递归算法设计 3、递归过程和递归工作栈 11第7章树和二叉树 2学 1小时 树的定义 2、树的表示方法 3、树的基本操作 4、树的存储结构 5、类 二叉树 2 1小时 二叉树的定义 2、二叉树的性质 3、二叉树的操作
计算机科学与技术学院 数据结构教案 第6 页 周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作业 数量 作业估计 时间 3 4 4 5 5 6 6 6 7 8 9 10 11 12 第 4 章 链式存储结构表、堆栈和队列 一、链式存储结构 二、单链表 1、 结点类的定义和实现 2、单链表类的定义和实现 3、单链表类的应用 三、单循环链表 1、 单循环链表类的定义和实现 2、 单循环链表类的应用 四、双向循环链表 1、 双向循环链表概念 2、 双向循环链表类定义和实现 五、链式堆栈 1、 链式堆栈类的定义和实现 2、 链式堆栈类的应用 六、链式队列 七、链式存储结构的特点 第 5 章 数组和串 1、 数组 2、特殊矩阵的压缩存储 3、稀疏矩阵的压缩存储 4、串 第 6 章 递归 1、递归的概念 2、递归算法设计 3、递归过程和递归工作栈 第 7 章 树和二叉树 一、树 1、 树的定义 2、树的表示方法 3、树的基本操作 4、树的存储结构 5、 类 二、二叉树 1、二叉树的定义 2、二叉树的性质 3、二叉树的操作 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 3 2 2 2 3 小时 1 小时 1 小时 1 小时
计算机科学与技术学院 数据结构教案 第7页 周别授课 需要作业作时业估 授课章节的内容摘要 时间数量计间 4、二叉树的存储结构 5、树和二叉树的转换 2学 三、链式存储结构的二叉树设计 1、二叉树结点类 2、二叉树的遍历 3、二叉树遍历的应用 4、应用示例 5、二叉树类 学/2 四、二叉树遍历游标类 1、二叉树中序遍历游标类 2、二叉树前序遍历游标类 3、二叉树层序遍历游标类 五、线索二叉树 151、线索二叉树的存储结构 1小时 2、线索二叉树类 3、中序线索二叉树类 六、堆(介绍) 1、堆的定义 2、最小堆类 2.5小时 3、最小堆类的测试 7七、哈夫曼树 1、路径长度和哈夫曼树 1小时 2、哈夫曼编码 3、哈夫曼编码问题数据结构设计 4、哈夫曼编码问题算法设计 第8章图 学 1小时 、图的基本概念和基本操作 、图的基本概念 2、图的基本操作 图的邻接矩阵存储结构 、邻接矩阵 0192、邻接矩阵表示的图类 2 1小时 3、邻接矩阵图类的深度优先搜索遍历 4、邻接矩阵图类的广度优先搜索遍历 5、非连通图和连通分量 6、邻接矩阵图类的测试 三、图的邻接表存储结构 1小时 1、图的邻接表存储结构 2、邻接表存储结构的图类 3、邻接表存储结构图类的测试
计算机科学与技术学院 数据结构教案 第7 页 周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需要 时间 作业 数量 作 时业估 计 间 7 7 8 8 9 9 10 10 13 14 15 16 17 18 19 20 4、二叉树的存储结构 5、树和二叉树的转换 三、链式存储结构的二叉树设计 1、二叉树结点类 2、二叉树的遍历 3、二叉树遍历的应用 4、应用示例 5、二叉树类 四、二叉树遍历游标类 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、邻接表存储结构图类的测试 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 2 2 4 2 2 2 2 1 小时 1 小时 1 小时 2.5 小时 1 小时 1 小时 1 小时 1 小时
计算机科学与技术学院 数据结构教案 第8页 周别授课 需要作业作业估计 授课章节的内容摘要 时间数量时间 四、图的其他存储结构 、逆邻接表 2、十字链表 3、邻接多重表 五、最小生成树 、最小生成树的基本概念 2、普里姆算法 3、克鲁斯卡尔算法 六、最短路径 、最短路径的基本概念 2、从一个顶点到其余各顶点的最短路径 3、所有顶点之间的最短路径 1223第9章排序 1小时 、排序的基本概念 插入排序 1、直接插入排序 2、链表插入排序 3、希尔排序 三、选择排序 1、直接选择排序 2、堆排序 2学3 1小时 交换排序 1、冒泡排序 2、快速排序 五、归并排序 六、基数排序 第10章查找 2学 1小时 、查找的基本概念 二、顺序表查找 1、无序顺序表顺序查找 2、有序顺序表查找 三、索引表查找 1、索引表结构 2、索引结构查找的效率分析 3、倒排索引表 4、平衡二叉树 四、树表查找 2学 1小时 排序树 2、二叉排序树类 3、二叉排序树的性能分析 五、哈希表查找 学 2小时 1、哈希表的基本概念 2、哈希函数构造方法 3、哈希冲突解决方法 4、哈希表类 2学 总结全课程
计算机科学与技术学院 数据结构教案 第8 页 周别 授课 顺序 授 课 章 节 的 内 容 摘 要 需 要 时间 作业 数量 作业估计 时间 11 11 12 12 13 13 14 14 21 22 23 24 25 26 27 28 四、图的其他存储结构 1、 逆邻接表 2、 十字链表 3、 邻接多重表 五、最小生成树 1、 最小生成树的基本概念 2、 普里姆算法 3、 克鲁斯卡尔算法 六、最短路径 1、 最短路径的基本概念 2、 从一个顶点到其余各顶点的最短路径 3、 所有顶点之间的最短路径 第 9 章 排序 一、 排序的基本概念 二、 插入排序 1、 直接插入排序 2、 链表插入排序 3、 希尔排序 三、选择排序 1、 直接选择排序 2、 堆排序 四、交换排序 1、 冒泡排序 2、 快速排序 五、归并排序 六、基数排序 第 10 章 查找 一、 查找的基本概念 二、 顺序表查找 1、 无序顺序表顺序查找 2、 有序顺序表查找 三、索引表查找 1、 索引表结构 2、 索引结构查找的效率分析 3、 倒排索引表 4、 平衡二叉树 四、树表查找 1、 二叉排序树 2、 二叉排序树类 3、 二叉排序树的性能分析 五、哈希表查找 1、 哈希表的基本概念 2、 哈希函数构造方法 3、 哈希冲突解决方法 4、 哈希表类 总结全课程 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 2 学 时 3 3 3 2 2 3 1 小时 1 小时 1 小时 1 小时 1 小时 2 小时
计算机科学与技术学院 数据结构教案 西南科技大学计算机学院《数据结构》教案 授课2学时 授课内「第1章C艹面向对象程序设计要点「授课 学时 容 时间 要解决的1、复习函数和函数参数 问题 2、复习类 3、复习抽象类型和模板 教学目的回顾C“程序设计语言的知识点,为数据结构的学习奠定基础 重点、难点重点:类和模板 难点:类的设计 教学方法多媒体教学、讲授 课后作业复习C+程序设计语言 详细内容1、函数和函数参数 )函数类型 (2)函数名重载 (3)函数参数 (4)成员函数返回值 2、类 3、抽象类型和模板
计算机科学与技术学院 数据结构教案 第9 页 西南科技大学计算机学院《数据结构》教案 授课 学时 2 学时 授课内 容 第 1 章 C ++面向对象程序设计要点 授课 时间 一 要解决的 问题 1、 复习函数和函数参数 2、 复习类 3、 复习抽象类型和模板 二 教学目的 回顾 C ++程序设计语言的知识点，为数据结构的学习奠定基础 三 重点、难点 重点：类和模板 难点：类的设计 四 教学方法 多媒体教学、讲授 五 课后作业 复习 C ＋＋程序设计语言 六 详细内容 1、 函数和函数参数 （1） 函数类型 （2） 函数名重载 （3） 函数参数 （4） 成员函数返回值 2、 类 3、 抽象类型和模板
计算机科学与技术学院 数据结构教案 第10页 授课2学时 授课内第2章面向对象程序设计和算法性|授课 能分析 时间 要解决的1、讲授什么是数据结构,为什么要学习数据结构 问题 2、熟悉数据结构相关术语 3、讲授什么是算法 4、算法的性能以及如何分析算法的性能 教学目的「让学生初步了解什么是数据结构,为什么要学习数据结构,认识和与 数据结构密切相关的几个术语以及学会分析算法的性能 重点、难点「重点:数据结构相关术语和算法以及算法分析 难点:算法性能分析 教学方法多媒体教学、讲授 课后作业习题二1、2、3、4、5、8、10、11题 详细内容1、为什么要学习数据结构 2、数据结构相关术语 3、算法 4、算法设计目的 5、算法的性能分析 (1)时间复杂度 (2)控件复杂度
计算机科学与技术学院 数据结构教案 第10 页 授课 学时 2 学时 授课内 容 第2章 面向对象程序设计和算法性 能分析 授课 时间 一 要解决的 问题 1、 讲授什么是数据结构，为什么要学习数据结构？ 2、 熟悉数据结构相关术语 3、 讲授什么是算法 4、 算法的性能以及如何分析算法的性能 二 教学目的 让学生初步了解什么是数据结构，为什么要学习数据结构，认识和与 数据结构密切相关的几个术语以及学会分析算法的性能 三 重点、难点 重点：数据结构相关术语和算法以及算法分析 难点：算法性能分析 四 教学方法 多媒体教学、讲授 五 课后作业 习题二 1、2、3、4、5、8、10、11 题 六 详细内容 1、 为什么要学习数据结构 2、 数据结构相关术语 3、 算法 4、 算法设计目的 5、 算法的性能分析 （1） 时间复杂度 （2） 控件复杂度