《数据结构》课件总结.ppt

1、1.1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，如一维数组中一个区域熟练掌握这两类存储结构的描述方法，如一维数组中一个区域i.ji.j的上、下界和长度之间的变换公式的上、下界和长度之间的变换公式,寻址公式，链表中寻址公式，

2、链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。特点等。链表是本章的重点和难点。3.3.熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。和删除的算法。4.4.熟练掌握在各种链表结构中实现线性表操作的基本方法，能在熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。实际应用中选用适当的链表结构。5.5.能够从时间和空间复杂度的角度综合比较线性表两种存储结构能够从时间和空间复杂度的角度综合比较线性

3、表两种存储结构的不同特点及其适用场合。的不同特点及其适用场合。第二章第二章 线性表的学习要点：线性表的学习要点：1.1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。应用问题中正确选用它们。2.2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。它们的描述方法。3.3.熟练掌握循环队列和链队列的基本操作实现算法，特别注熟练掌握循环队列和链队列的基本操作

4、实现算法，特别注意队满和队空的描述方法。意队满和队空的描述方法。4.4.理解递归算法执行过程中栈的状态变化过程。理解递归算法执行过程中栈的状态变化过程。第三章第三章 栈、队列的学习要点：栈、队列的学习要点：1.1.了解数组的两种存储表示方法，并掌握数组在以行为主的存了解数组的两种存储表示方法，并掌握数组在以行为主的存 储结构中的地址计算方法。储结构中的地址计算方法。2.2.掌握对特殊矩阵进行压缩存储时的下标变换公式。掌握对特殊矩阵进行压缩存储时的下标变换公式。3.3.了解稀疏矩阵的压缩存储方法的特点，领会以三元组表示稀疏了解稀疏矩阵的压缩存储方法的特点，领会以三元组表示稀疏矩阵时进行矩阵运算采

5、用的处理方法。矩阵时进行矩阵运算采用的处理方法。4.4.掌握广义表的结构特点及其存储表示方法，可将一个非空广义掌握广义表的结构特点及其存储表示方法，可将一个非空广义表分解为表头和表尾两部分。表分解为表头和表尾两部分。第四章第四章 数组和广义表的学习要点：数组和广义表的学习要点：1.1.熟悉串的七种基本操作的定义，并能利用这些基本熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作。操作来实现串的其它各种操作。2.2.熟练掌握在串的定长顺序存储结构上实现串的各种熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。操作的方法。3.3.了解串操作的应用方法和特点。了解串操作的应

6、用方法和特点。第五章第五章 串的学习要点：串的学习要点：1.熟练掌握树、二叉树中的基本概念和性质。熟练掌握树、二叉树中的基本概念和性质。2 2.遍历二叉树是二叉树各种操作的基础。不仅要熟练掌握各遍历二叉树是二叉树各种操作的基础。不仅要熟练掌握各 种遍历策略的递归和非递归算法，了解遍历过程中种遍历策略的递归和非递归算法，了解遍历过程中“栈栈”的的 作用和状态，而且能灵活运用遍历算法实现二叉树的其它作用和状态，而且能灵活运用遍历算法实现二叉树的其它 操作。操作。3 3.理解二叉树线索化的实质是建立结点与其在相应序列中的理解二叉树线索化的实质是建立结点与其在相应序列中的 前驱或后继之间的直接联系。前

7、驱或后继之间的直接联系。4 4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树熟悉树的各种存储结构及其特点，掌握树和森林与二叉树 的转换方法。的转换方法。5 5.学会编写实现树的各种操作的算法。学会编写实现树的各种操作的算法。6 6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。第六章第六章 树的学习要点：树的学习要点：1.1.熟悉图的各种存储结构及其构造算法，了解求解实际问题应采熟悉图的各种存储结构及其构造算法，了解求解实际问题应采 用何种存储结构。用何种存储结构。2.2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优熟练

8、掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优 先搜索的两种形式（递归和非递归）和广度优先搜索的算法。先搜索的两种形式（递归和非递归）和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差在学习中应注意图的遍历算法与树的遍历算法之间的类似和差 异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是 一种广度优先搜索策略。一种广度优先搜索策略。3.3.理解教科书中讨论的各种图的算法。理解教科书中讨论的各种图的算法。第七章第七章 图的学习要点：图的学习要点：1.1.熟练掌握顺序表和有序表的查找方法，理解分块查找的方法熟

9、练掌握顺序表和有序表的查找方法，理解分块查找的方法和索引存储结构。和索引存储结构。2.熟练掌握二叉排序树的构造和查找方法。熟练掌握二叉排序树的构造和查找方法。3.3.理解在二叉排序树上删除结点的过程。理解在二叉排序树上删除结点的过程。3.掌握二叉平衡树的维护平衡方法。掌握二叉平衡树的维护平衡方法。4.掌握掌握B-树的概念，理解建树、查找和删除结点的过程。树的概念，理解建树、查找和删除结点的过程。5.5.掌握掌握B+树和键树的概念及其特点，以及在其上查找关键字的树和键树的概念及其特点，以及在其上查找关键字的过程。过程。6.熟练掌握哈希表的构造方法和解决冲突的策略，深刻理解哈熟练掌握哈希表的构造方

10、法和解决冲突的策略，深刻理解哈希表与其它结构的表的实质性的差别。希表与其它结构的表的实质性的差别。第八章第八章 查找表的学习要点：查找表的学习要点：1.1.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应深刻理解排序的定义和各种排序方法的特点，并能加以灵活应 用。用。2.2.了解各种方法的排序过程及其依据的原则。基于了解各种方法的排序过程及其依据的原则。基于“关键字间的关键字间的比较比较”进行排序的方法可以按排序过程所依据的不同原则分为进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。插入排序、交换排序、选择排序、归并排序和计数排序等

11、五类。3.3.掌握各种排序方法的时间复杂度的分析方法。能从掌握各种排序方法的时间复杂度的分析方法。能从“关键字间关键字间的比较次数的比较次数”分析排序算法的平均情况和最坏情况的时间性能。分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：按平均时间复杂度划分，内部排序可分为三类：O(nO(n2 2)的简单的简单排序方法，排序方法，O(nO(nlogn)logn)的高效排序方法和的高效排序方法和O(dO(dn)n)的基数排序的基数排序方法。方法。4 4理解排序方法理解排序方法“稳定稳定”或或“不稳定不稳定”的含义。的含义。第九章第九章 排序的学习要点：排序的学习要点：