数据结构各章要点汇总.ppt

顺序表——逻辑相邻，物理相邻； 链表——逻辑关系由指针或“游标”体现。 顺序表的存储空间是静态分配的，而算法的执行前必须明确的规定其存储规模；链表的存储空间是动态分配的。当线性表的长度变化较大或问题规模难以确定时，采用动态链表较好。 对于顺序表，可随机访问任一个元素，而在单链表中,需要顺着链逐个进行查找，因此单链表适合于在成批地, 顺序地处理线性表中的元素时采用。 在单链表里进行插入、删除运算比在顺序表里方便、灵活。 * 1.基本概念: 理解什么是数据、数据元素、数据项、数据对象、数据结构(数据的逻辑结构4种)和物理结构、数据类型、抽象数据类型。 第一章 2. 理解算法五要素的确切含义: 有穷性、确定性、可行性、有输入、有输出 3.理解算法设计的目标的确切含义： 正确性、可读性、健壮性、高效率、低存储 4. 掌握计算语句频度和估算算法时间复杂度的方法 第二章 了解线性表的逻辑结构特性是数据元素之间存在 着线性关系，在计算机中表示这种关系的两类不同的 存储结构是顺序存储结构和链式存储结构。用前者表 示的线性表简称为顺序表，用后者表示的线性表简称 为链表。 熟练掌握这两类存储结构的描述方法，以及线性 表的各种基本操作的实现。 能够从时间和空间复杂度的角度综合比较线性表 两种存储结构的不同特点及其适用场合。 掌握栈和队列类型的特点，并能在相应的应用 问题中正确选用它们。 熟练掌握栈类型的两种实现方法，特别应注意 栈满和栈空的条件以及它们的描述方法。 熟练掌握循环队列和链队列的基本操作实现算 法，特别注意队满和队空的描述方法。 理解递归算法执行过程中栈的状态变化过程。 第三章 顺序表与链表的比较 熟悉串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 了解串的堆存储结构以及在其上实现串操作的基本方法。 理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。 了解串操作的应用方法和特点。 第四章 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 掌握对特殊矩阵进行压缩存储时的下标变换公式。 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 掌握广义表的结构特点及其存储表示方法，掌握任意一种结构的链表，学会对非空广义表进行分解的方法:表头.表尾分析法或者分解为n个子表的分析法。 第五章 熟练掌握二叉树的结构特性，了解相应的证明方法。 熟悉二叉树的各种存储结构的特点及适用范围。 遍历二叉树是二叉树各种操作的基础。二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法及一种非递归算法，灵活运用遍历算法实现二叉树的其它操作。 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 第六章 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 学会编写实现树的各种操作的算法。 熟悉哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。 熟悉图的各种存储结构及其构造算法，了解实际 问题的求解效率与采用何种存储结构和算法有密切联 系。 熟练掌握图的两种搜索路径的遍历：遍历的逻辑 定义、深度优先搜索和广度优先搜索的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的 类似和差异。 应用图的遍历算法求简单路径(用栈)和长度最短 路径(用队列)。 掌握图的最小生成树(prim和kruskal)、拓扑排序、 关键路径、带权图的最短路径(Dijkstra和Floyd)等构 造方法。 第七章 顺序表、有序表和索引顺序查找（分块查找）的 查找方法及其平均查找长度。 掌握二叉排序树、平衡二叉树的概念和特点。 熟练掌握哈希表的构造方法和处理冲突方法，深刻理解哈希表与其它结构的表的实质性的差别。 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 第九章 *