《数据结构》课程教学大纲绪论.docx

数据结构课程教学大纲L绪论1.1. 学习目标熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。1.2. 重点和难点本章讨论的都是一些基本概念，因此没有难点，重点在于了解有关数据结构的各个名词 和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。1.3. 知识点数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂 度、空间复杂度14学习指南1 .熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关 系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2 . 了解抽象数据类型的定义、表示和实现方法。3 .熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式 以及错误处理方式。4 .理解算法五个要素的确切含义和对算法正确性的理解。5 .掌握计算语句频度和估算算法时间复杂度的方法。2.线性表2.1. 学习目标1 . 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系 的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺 序表，用后者表示的线性表简称为链表。2 .熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实 现。3 .能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场 合。4 .结合线性表类型的定义增强对抽象数据类型的理解。22重点和难点链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基 本要求，分清链表中指针P和结点*p之间的对应关系，区分链表中的头结点、头指针和 首元结点的不同所指以及循环链表、双向链表的特点等。2.3.知识点线性表、顺序表、链表、有序表24学习指南学习数据结构的目标是为了编出质量更高的程序，因此重在“实践”。本章讨论的线性表 是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操 作对以后各章的学习将有很大帮助。3 .栈和队列31学习目标1 .掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2 .熟练掌握栈类型的两种实现方法。3 .熟练掌握循环队列和链队列的基本操作实现算法。4 .理解递归算法执行过程中栈的状态变化过程。32重点和难点栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌 握这两种结构的特点，以便能在应用问题中正确使用。3.3. 知识点顺序栈、链栈、循环队列、链队列34学习指南在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种 存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一 些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。4.串4.1. 学习目标1 .理解“串“类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2 .理解串类型的各种存储表示方法。3 .理解串匹配的各种算法。42重点和难点相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经 实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方 法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP 算法的思想，但它不属本章学习的基本要求。4.3.知识点串的类型定义、串的存储表示、串匹配、KMP算法44学习指南虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此 作为一个软件工作者还是应该了解串的实现方法。5.数组和稀疏矩阵5.1. 学习目标1 .理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以 行为主”的存储表示中的地址计算方法。2 .掌握特殊矩阵的存储压缩表示方法。3 .理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时 进行矩阵运算所采用的处理方法。52重点和难点本章重点是学习数组类型的定义及其存储表示。5.3.知识点数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压 缩存储表示方法54学习指南从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前儿章讨 论的线性结构的顺序存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？ 因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本 章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。6.树和二叉树6.1. 学习目标1 .领会树和二叉树的类型定义，理解树和二叉树的结构差别。2 .熟记二叉树的主要特性，并掌握它们的证明方法。3 .熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4 .理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5 .熟练掌握二叉树和树的各种存储结构及其建立的算法。6 .学会编写实现树的各种操作的算法。7. 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。62重点和难点二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递 归算法也恰是本章的难点所在。6.3.知识点树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和 赫夫曼编码64学习指南本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程 中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。7.图7.L学习目标1 .领会图的类型定义。2 .熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3 .熟练掌握图的两种遍历算法。4 .理解各种图的应用问题的算法。5 .2 ,重点和难点图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解 各种图的算法及其应用场合。73知识点图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向 网的最小生成树、最短路径、拓扑排序、关键路径74学习指南离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性 质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用 等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时 可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的 研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍 一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历 的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。8 .广义表8.1. 学习目标1 .掌握广义表的结构特点及其存储表示方法。2 .学习利用分治法的算法设计思想编制递归算法。82重点和难点本章重点及其难点都是学习并掌握如何对递归定义的数据结构设计实现其操作的递归 算法。8.3.知识点广义表的类型定义、广义表的存储表示、广义表操作的实现84学习指南广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据 结构。但由于广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作 的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过 本章的学习恰好是对实现树操作的递归算法的复习和巩固。希望通过本章的学习能自己总结 出如何利用“分治法”的算法思想设计递归定义的结构的递归算法的规律来。9.查找表91学习目标1 .理解“查找表”的结构特点以及各种表示方法的适用性；2 .熟练掌握以顺序表或有序表表示静态查找表时的查找方法；3 .熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；4 .熟练掌握二叉查找树的构造和查找方法；5 .理解二叉平衡树的构造过程；6 .熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；7 .掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下 查找成功时的平均查找长度。9.2, 重点和难点本章重点在于理解查找表的结构特点及其各种表示方法的特点和适用场合。9.3, 知识点顺序表、有序表、索引顺序表、静态查找树、二叉查找树、二叉平衡树、哈希表94学习指南本章讨论的查找表即为绪论中提到的集合结构，由于它是很多应用软件中的操作对 象，因此本章讨论的内容亦为整个课程的重点之一。由于集合中的数据元素之间不存在任何 关系，因此它的主要操作查找不便进行，为了提高对查找表进行查找的效率需要以另一种 数据结构表示之。10.内排序10.1. 学习目标8 .理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方 法，基于”关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入 排序、交换排序、选择排序、归并排序和计数排序等五类。9 .掌握各种排序方法的时间复杂度的分析方法。能从”关键字间的比较次数”分析排序算法 的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：。 (n2)的简单排序方法，O miogn)的高效排序方法和。外的基数排序方法。10 .理解排序方法“稳定“或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须 是稳定的。10.2. 重点和难点希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。10.3. 知识点排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、 简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。10.4. 学习指南本章学习的要点主要是了解各种排序方法实现时所依据的原则以及它们的主要操作（” 关键字间的比较”和”记录的移动”）的时间分析。学习中应注意掌握各种排序方法实现的要 点，可通过对基础知识题中算法的手工执行和比较分析，切实掌握各种排序过程的排序特点 所在，注意同一排序方法在不同的教科书上可以有不同书写形式描述的算法。教材 数据结构（第二版）殷人昆编箸清华大学出版社2007