《数据结构》课程教学大纲DataStructure.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、 教学方法：讲授为主，辅以课