《数据结构》课程教学大纲 Data Structure(精品).doc

《数据结构》课程教学大纲Data Structure一、课程教学目标1、 任务和地位：数据结构是计算机类各专业的一门专业技术基础课主要强调了数据的特性、数据的逻辑结构和数据的存储结构以及相应操作的算法设计思想通过本课程的学习，使学员掌握对数据进行有效组织和存储的方法，提高学生进行软件设计开发的能力，也为操作系统和数据库等后续课程奠定基础2、 知识要求：本课程作为专业必修课，要求学生掌握《C程序设计》、《离散数学》等专业基础课及其相关知识3、 能力要求：要求学生能够熟练掌握C语言，本课程注重理论和实际的结合，通过学生完成实验，对数据结构的相关知识有一个深刻的理解 二、教学内容的基本要求和学时分配1、课程教学总学时数为64学时，其中讲授学时54学时，实验10学时教 学 内 容 章 目本课程学分：学 时 分 配讲课课堂讨论实验小计第1章　绪论33第2章 线性表729第3章 栈和队列8412第4章 矩阵的压缩存储44第5章 递归44第6章 树与二叉树8210第7章　图8210第8章 查找66第9章 排序66合 计5410642、具体要求：第1章 绪论[目的要求]了解数据结构的基本概念，掌握算法效率分析方法[教学内容]1.1 数据结构研究内容1.2 基本概念和术语1.3 算法和算法分析[重点难点] 时间复杂度和空间复杂度的分析[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 3学时第2章 线性表[目的要求]掌握线性表的顺序存储结构及链式存储结构，以及相关操作的实现[教学内容] 2.1 线性表的定义 2.2 线性表的顺序顺序存储结构及其运算 2.3 线性表的链式存储结构及其运算2.3.1 单链表2.3.2 循环链表2.3.3 双向链表2.4 顺序表和链表的比较2.5 线性表的简单应用举例[重点难点] 基本操作的算法实现[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 9学时第3章 栈和队列[目的要求] 掌握两类特殊的线性表：栈和队列，主要操作的实现[教学内容]3.1 栈的定义3.2 栈的存储结构 3.2.1 顺序栈 3.2.2 链式栈3.3 栈的简单应用举例3.4 队列定义3.5 队列的存储结构 3.5.1 循环队列 3.5.2 链式队列3.6 队列的简单应用举例[重点难点] 栈和队列存储结构的表示及算法的实现[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 12学时第4章 矩阵的压缩存储[目的要求] 掌握多维数组、特殊矩阵、稀疏矩阵的压缩存储和相关操的实现[教学内容]4.1 多维数组 4.1.1 数组的定义和操作 4.1.2 数组的顺序存储4.2 特殊矩阵的压缩存储 4.2.1 对称矩阵 4.2.2 三角矩阵 4.2.3 带状矩阵4.3 稀疏矩阵的压缩存储 4.3.1 三元组表 4.3.2 十字链表 [重点难点]　矩阵的压缩存储[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 4学时第5章 递归[目的要求] 了解递归算法的工作原理，掌握递归算法的实现方法[教学内容]5.1 递归的定义5.2 递归算法的工作原理 5.3 递归算法的实现形式5.4 递归算法的分类5.5递归的简单应用举例 [重点难点]　递归算法的工作原理及实现形式[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 4学时第6章 树与二叉树[目的要求]　了解树和二叉树的基本概念与性质，掌握树和二叉树的存储结构及相关操作的实现，特别是遍历二叉树和线索二叉树，掌握哈夫曼树的构造和哈夫曼编码。

[教学内容]6.1 树的基本概念 6.1.1 树的定义及相关术语 6.1.2 树的表示方法 6.1.3 树的性质 6.1.4 树的存储结构6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 二叉树的运算 6.3.1 二叉树的遍历 6.3.2二叉树的其他运算举例6.4 线索化二叉树 6.4.1 线索二叉树的概念 6.4.2 二叉树的线索化 6.4.3 线索二叉树上的运算6.5 树、森林与二叉树的转换 6.5.1 树转换为二叉树 6.5.2 森林转换为二叉树 6.5.3 二叉树转换为树和森林6.6 树与森林的遍历 6.6.1 树的遍历 6.6.2 森林的遍历6.7 Huffman树及其应用 6.7.1 哈夫曼树的基本概念 6.7.2 哈夫曼树的构造及实现 6.7.3 哈夫曼树的应用[重点难点] 二叉树的遍历、线索化的基本思想及算法实现，哈夫曼编码[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 10学时第7章 图[目的要求]了解图的概念，掌握图的存储结构，图的遍历及图的相关应用[教学内容]7.1 图的定义与基本术语7.2 图的存储结构 7.2.1 邻接矩阵表示法 7.2.2 邻接表表示法 7.3 图的遍历 7.3.1 图的深度优先搜索 7.3.2 图的广度优先搜索 7.4 图的生成树和最小生成树 7.4.1 生成树和最小生成树的概念 7.4.2 Prim算法 7.4.3 Kruskal算法7.5拓扑排序及其应用 7.6 最短路径 7.6.1 单源点的最短路径 7.6.2 每一对顶点之间的最短路径[重点难点] 图的存储结构，最小生成树，拓扑排序，关键路径，最短路径[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课堂练习＋课外作业[课 时] 10学时第8章 查找[目的要求]　掌握静态查找、动态查找及哈希查找[教学内容]8.1 查找的基本概念8.2 线性表的查找 8.2.1 顺序查找 8.2.2 折半查找 8.2.3 分块查找 8.3 树表的查找 8.2.1 二叉排序树 8.2.2 AVL树 8.2.3 B_树和B+树 8.3 散列表的查找 8.3.1 散列表的概念 8.3.2 散列函数 8.3.3 解决冲突的方法 8.3.4 散列表的查找及其分析 [重点难点] 二叉排序树，散列表的查找[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课后习题[课 时] 6学时第9章排序[目的要求]　掌握基本的内部排序方法的基本思想及算法实现[教学内容]9.1 排序的基本概念 9.2 插入排序 9.2.1 直接插入排序 9.2.2 希尔排序 9.3 交换排序 9.3.1 冒泡排序 9.3.2 快速排序 9.4 选择排序 9.4.1 直接选择排序 9.4.2 堆排序 9.5 二路归并排序 9.6 基数排序9.7 外部排序[重点难点] 各种基本的内部排序方法的基本思想及算法实现[教学方法] 利用多媒体教学设备进行课堂讲解[作 业] 课后习题[课 时] 6学时三、大纲说明1、 本课程为考试课，采用闭卷考试。

2、 教学方法：讲授为主，辅以课堂讨论和练习,上机实验3、 考试成绩 期末考试：70（80）%，平时30（20）%4、 教材及参考资料：教材: 戴敏.《数据结构》.机械工业出版社，2008.参考教材: 严蔚敏,吴伟民.《数据结构（C语言版）》清华大学出版社,1997.王晓东.《数据结构与算法设计》. 电子工业出版社,1999.。