《数据结构》课件-总结

NorthChinaElectricPowerUniversity了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式,寻址公式，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。第二章线性表的学习要点：NorthChinaElectricPowerUniversity掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。理解递归算法执行过程中栈的状态变化过程。第三章栈、队列的学习要点：了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的压缩存储方法的特点，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法，可将一个非空广义表分解为表头和表尾两部分。第四章数组和广义表的学习要点：NorthChinaElectricPowerUniversity熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。了解串操作的应用方法和特点。第五章串的学习要点：NorthChinaElectricPowerUniversity

1.熟练掌握树、二叉树中的基本概念和性质。

2.遍历二叉树是二叉树各种操作的基础。不仅要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。

3.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。

4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。

5.学会编写实现树的各种操作的算法。

6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。第六章树的学习要点：NorthChinaElectricPowerUniversity

1.熟悉图的各种存储结构及其构造算法，了解求解实际问题应采用何种存储结构。

2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。

3.理解教科书中讨论的各种图的算法。

第七章图的学习要点：NorthChinaElectricPowerUniversity熟练掌握顺序表和有序表的查找方法，理解分块查找的方法和索引存储结构。2.熟练掌握二叉排序树的构造和查找方法。3.理解在二叉排序树上删除结点的过程。3.掌握二叉平衡树的维护平衡方法。4.掌握B-树的概念，理解建树、查找和删除结点的过程。5.掌握B+树和键树的概念及其特点，以及在其上查找关键字的过程。6.熟练掌握哈希表的构造方法和解决冲突的策略，深刻理解哈希表与其它结构的表的实质性的差别。第八章查找表的学习要点：NorthChinaElectricPowerUniversity深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。2.了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。3.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可