数据结构总结知识点教程.docx

第一章 数据结构概念——数据结构，数据元素，数据项，数据类型，抽象数据类型，算法，等。 数据结构定义——指互相有关联的数据元素的集合，用D_S=( D, S ) 或 S=( D, R) 表示。 数据结构内容——数据的逻辑结构、存储结构和运算 算法效率指标——时间效率（时间复杂度）和空间效率（空间复杂度） 总结：数据的逻辑结构和存储结构 数据的逻辑结构是数据的机外表示，数据的存储 结构是数据的机内表示。 (2) 一种数据的逻辑结构可以用多种存储结构来存储。 (3) 数据结构的基本操作是定义（存在）于逻辑结构，计算机程序设计过程中实现于存储结构。 (4) 采用不同的存储结构，其数据处理的效率往往是不同的。 数据结构？有限个同构数据元素的集合，存在着一定的结构关系，可进行一定的运算。 算法--是对特定问题求解步骤的一种描述，是指令的有限序列。 算法有5个基本特性： 有穷性、确定性、可行性、输入和输出 第二章 1. 数据的逻辑结构是指数据元素之间的逻辑关系， 是用户按使用需要建立的。对 2. 线性表的逻辑结构定义是唯一的，不依赖于计算机。对 3. 线性结构反映结点间的逻辑关系是一对一的。对 4. 一维向量是线性表，但二维或N维数组不是。错 5. “同一数据逻辑结构中的所有数据元素都具有相同的 特性”是指数据元素所包含的数据项的个数都相等。错 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n 插入操作时间效率（平均移动次数）删除操作时间效率（平均移动次数） 线性表顺序存储结构特点：逻辑关系上相邻的两个元素 在物理存储位置上也相邻； 优点：可以随机存取表中任一元素;无需为表示表中元素 之间的逻辑关系而增加额外的存储空间； 缺点：在插入、删除某一元素时，需要移动大量元素；表的容量难以确定，表的容量难以扩充。 顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。 单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。 按位查找： 顺序表的时间为Ｏ(1)，是随机存取； 单链表的时间为Ｏ(n)，是顺序存取。 插入和删除： 顺序表需移动表长一半的元素，时间为Ｏ(n)； 单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。 第六章 性质1 在二叉树的第i层上至多有2i - 1个结点 第i层上至少有 1 个结点 性质2 深度为k的二叉树至多有2k-1个结点 深度为k的二叉树至少有 k 个结点 性质3 对于任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 完全二叉树的特点 1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。 满二叉树的特点： 叶子只能出现在最下一层 只有度为0和度为2的结点 具有n个结点的完全二叉树，其深度k为 : log2n+1 对于完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，右孩子编号必为2i＋1，双亲的编号必为i/2。 一棵完全二叉树有5000个结点，则其叶子结点的个数是__2500__ DLR LDR LRD 先序遍历 中序遍历 后序遍历 由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树， 但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外,去除其与其余孩子之间的关系 旋转：将同一孩子的连线绕左孩子旋转45度角。 二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 只有一个叶子结点 二叉树的1）先序序列与后序序列相同的条件是（ 或为空树，或为只有根结点的二叉树 ）2）中序序列与后序序列相同的条件是（ 或为空树，或为任一结点至多只有左子树的二叉树 ）3）先序序列与中序序列相同的条件是（ 或为空树，或为任一结点至多只有右子树的二叉树 ）4）