新版《数据结构》教学大纲.doc

...wd...新版?数据构造?课程教学大纲一、课程名称?数据构造?二、教学目的数据构造是高等教育计算机信息管理专业中的一门专业根基课，在计算机软件的各个领域中均会使用到数据构造的有关知识本课程的目的和任务是使学生较全面地掌握各种常用的数据构造，为学习后续软件课程提供必要的根基，提高运用数据构造解决实际问题的能力三、教学要求 1. 从数据构造的逻辑构造、存储构造和数据的运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图等常用的数据构造 2. 掌握在各种常用的数据构造上实现的排序和查找运算 3. 对算法的时间和空间复杂性有一定的分析能力 4. 针对简单的应用问题.应能选择适宜的数据构造及设计有效的算法解决之四、教学课时数分配表章 次教学内容课时数分配作业次数备注总课时数理论实践习题第一章绪论22第二章线性表147(6)7(8)2第三章栈和队列6(8)3(4)3(4)2第四章 串4221第五章 数组和广义表4221第六章树和二叉树8442第七章图8442第八章查找8441第九章内部排序10(8)46(4)1合计64323212五、理论教学内容第一章 绪论〔2课时〕内容提要：本章的目的是介绍数据构造中常用的 基本概念和术语以及学习数据构造的意义，要求了解本章介绍的各种 基本概念和术语，掌握算法描述和分析的方法。

教学重点和难点：本章重点是了解数据构造的逻辑构造、存储构造及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法§1.1 基本概念和术语〔1课时〕§1.2 算法的描述和分析〔1课时〕第二章 线性表 〔7课时〕内容提要：本章目的是介绍线性表的逻辑构造和各种存储表示方法，以及定义在逻辑构造上的各种 基本运算及其在存储构造上若何实现这些 基本运算要求在熟悉这些内容的根基上，能够针对具体应用问题的要求和性质，选择适宜的存储构造设计出相应的有效算法，解决与线性表相关的实际问题教学重点和难点：本章重点是熟练掌握顺序表和单链表上实现的各种 基本算法及相关的时间性能分析，难点是能够使用本章所学到的 基本知识设计有效算法解决与线性表相关的应用问题§2.1 线性表的逻辑构造〔2课时〕§2.2 线性表的顺序存储构造〔2课时〕§2.3 线性表的链式存储构造〔2课时〕§2.4 顺序表和链表的比较〔1课时〕第三章 栈和队列〔3课时〕内容提要：本章目的是介绍栈和队列的逻辑构造定义及在两种存储构造上若何实现栈和队列的 基本运算要求在掌握栈和队列的特点的根基上，懂得在什么样的情况下能够使用栈或队列。

教学重点和难点：本章重点是掌握栈和队列在两种存储构造上实现的 基本运算，难点是循环队列中对边界条件的处理§3.1 栈〔1课时〕§3.2 队列〔1课时〕§3.3 栈和队列的应用〔1课时〕第四章 串〔2课时〕内容提要：本章目的是介绍串的逻辑构造、存储构造及其中上的 基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能教学重点和难点：本章重点是掌握串上实现的模式匹配算法，这也是本章的难点§4.1 串及其运算〔1课时〕§4.2 串的存储构造〔1课时〕第五章 数组和广义表〔2课时〕内容提要：本章目的是介绍多维数组的逻辑构造特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容教学重点和难点：本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法§5.1 多维数组〔1课时〕§5.2 矩阵的压缩存储〔0.5课时〕§5.3 广义表的概念〔0.5课时〕第六章 树和二叉树〔4课时〕内容提要：本章目的是介绍二叉树的定义、性质、存储构造、遍历、线索化，树的定义、存储构造、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。

教学重点和难点：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题§6.1 树的概念〔0.5课时〕§6.2 二叉树〔1课时〕§6.3 二叉树的遍历〔1课时〕§6.4 线索二又树〔0.5课时〕§6.5 树和森林〔0.5课时〕§6.6 哈夫曼树及其应用〔0.5课时〕第七章 图 〔4课时〕内容提要：图的定义，有关术语和存贮构造，图的两种遍历算法两个求最小生成树的算法，最短路径，拓扑排序和关键路径算法教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握图存贮构造，图的两种遍历算法本章难点是求最小生成树的算法，最短路径，拓扑排序和关键路径算法§7.1 图的 基本概念和存贮构造〔1课时〕§7.2 最小生成树的算法〔1课时〕§7.3 最短路径，拓扑排序和关键路径算法〔2课时〕第八章 查找〔4课时〕内容提要：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的 基本思想和算法实现。

本章难点是二叉查找树的删除算法及B—树上的插入和删除算法§9.1 基本概念〔1 课时〕§9.2 线性表的查找〔1课时〕§9.3 树的查找〔1课时〕§9.4 散列技术〔1课时〕第九章 内部排序〔4课时〕内容提要：本章目的是介绍五类内部排序方法的 基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握快速排序、堆排序、归并排序和基数排序的 基本思想及排序过程本章难点是四个排序算法的实现§9.1 插入排序〔1课时〕§9.2 交换排序〔1课时〕§9.3 选择排序〔0.5课时〕§9.4 归并排序〔0.5课时〕§9.5 分配排序〔0.5课时〕§9.6 各种排序方法的比较和选择〔0.5课时〕八、实践教学内容第一章 线性表 〔7课时〕内容提要：本章目的是介绍线性表的逻辑构造和各种存储表示方法，以及定义在逻辑构造上的各种 基本运算及其在存储构造上若何实现这些 基本运算要求在熟悉这些内容的根基上，能够针对具体应用问题的要求和性质，选择适宜的存储构造设计出相应的有效算法，解决与线性表相关的实际问题。

教学重点和难点：本章重点是熟练掌握顺序表和单链表上实现的各种 基本算法及相关的时间性能分析，难点是能够使用本章所学到的 基本知识设计有效算法解决与线性表相关的应用问题§1.1 线性表的逻辑构造〔1课时〕§1.2 线性表的顺序存储构造〔2课时〕§1.3 线性表的链式存储构造〔2课时〕§1.4 顺序表和链表的比较〔2课时〕第二章 栈和队列〔3课时〕内容提要：本章目的是介绍栈和队列的逻辑构造定义及在两种存储构造上若何实现栈和队列的 基本运算要求在掌握栈和队列的特点的根基上，懂得在什么样的情况下能够使用栈或队列教学重点和难点：本章重点是掌握栈和队列在两种存储构造上实现的 基本运算，难点是循环队列中对边界条件的处理§2.1 栈〔1课时〕§2.2 队列〔1课时〕§2.3 栈和队列的应用〔1课时〕第三章 串〔2课时〕内容提要：本章目的是介绍串的逻辑构造、存储构造及其中上的 基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能教学重点和难点：本章重点是掌握串上实现的模式匹配算法，这也是本章的难点§3.1 串及其运算〔1课时〕§3.2 串的存储构造〔1课时〕第四章 数组和广义表〔2课时〕内容提要：本章目的是介绍多维数组的逻辑构造特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。

教学重点和难点：本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法§4.1 多维数组〔1课时〕§4.2 矩阵的压缩存储〔1课时〕第五章 树和二叉树〔4课时〕内容提要：本章目的是介绍二叉树的定义、性质、存储构造、遍历、线索化，树的定义、存储构造、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容教学重点和难点：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题§5.1二叉树〔1课时〕§5.2线索二又树〔1课时〕§5.3树和森林〔1课时〕§5.4哈夫曼树及其应用〔1课时〕第六章 图 〔4课时〕内容提要：图的定义，有关术语和存贮构造，图的两种遍历算法两个求最小生成树的算法，最短路径，拓扑排序和关键路径算法教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握图存贮构造，图的两种遍历算法本章难点是求最小生成树的算法，最短路径，拓扑排序和关键路径算法§6.1 图的 基本概念和存贮构造〔1课时〕§6.2 最小生成树的算法〔1课时〕§6.3 最短路径，拓扑排序和关键路径算法〔2课时〕第七章 查找〔4课时〕内容提要：本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能(平均查找长度)分析。

教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的 基本思想和算法实现本章难点是二叉查找树的删除算法及B—树上的插入和删除算法§7.1线性表的查找〔1课时〕§7.2树的查找〔2课时〕§7.3散列技术〔1课时〕第八章 内部排序〔6课时〕内容提要：本章目的是介绍五类内部排序方法的 基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择教学重点和难点：要求学生在熟悉这些内容的根基上，重点掌握快速排序、堆排序、归并排序和基数排序的 基本思想及排序过程本章难点是四个排序算法的实现§8.1 插入排序〔1课时〕§8.2 交换排序〔1课时〕§8.3 选择排序〔1课时〕§8.4 归并排序〔1课时〕§8.5 分配排序〔1课时〕§8.6 各种排序方法的比较和选择〔1课时〕九、使用教材：?数据构造?〔C语言版〕严蔚敏著清华大学出版社 1999.6十、参考书目：1、?数据构造〔C语言版〕?清华大学出版社 主编：严蔚敏、吴伟民 2007.3 ；2、?数据构造题集〔C语言版〕?清华大学出版社 主编：严蔚敏 1999.2 ；3、?数据构造?清华大学出版社 主编：李筠、姜学军 2008.8 ；4、?数据构造〔第二版〕?清华大学出版社 主编：张世和 2007.9；。