数据结构总结知识点

第一章数据结构概念——数据结构，数据元素，数据项，数据类型，抽象数据类型，算法，等。数据结构定义——指互相有关联的数据元素的集合，用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插入操作时间效率（平均移动次数）2)1(11)1(1111ninninpEniniiis删除操作时间效率（平均移动次数）21)(1)(11ninninqEniniidl线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素;无需为表示表中元素之间的逻辑关系而增加额外的存储空间；缺点：在插入、删除某一元素时，需要移动大量元素；表的容量难以确定，表的容量难以扩充。顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。按位查找：顺序表的时间为Ｏ(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__DLRLDRLRD先序遍历中序遍历后序遍历由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外,去除其与其余孩子之间的关系旋转：将同一孩子的连线绕左孩子旋转45度角。二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足只有一个叶子结点二叉树的1）先序序列与后序序列相同的条件是（或为空树，或为只有根结点的二叉树）2）中序序列与后序序列相同的条件是（或为空树，或为任一结点至多只有左子树的二叉树）3）先序序列与中序序列相同的条件是（或为空树，或为任一结点至多只有右子树的二叉树）4）中序序列与层次遍历序列相同的条件是（或为空树，或为任一结点至多只有右子树的二叉树若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。第七章完全无向图有n(n-1)/2条边。完全有向图有n(n-1)条边。在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量求生成树的方法——DFS（深度优先搜索）和BFS（广度优先搜索）用邻接表表示图进行广度优先遍历时，通常是采用队列来实现算法的。用邻接表表示图进行深度优先遍历时，通常是采用栈来实现算法的。生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。设有一稀疏图G，则G采用邻接表存储较省空间。7.设有一稠密图G，则G采用邻接矩阵存储较省空间。第九章折半查找：使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。具有n个结点的折半查找判定树的深度为log2n+1或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。二叉排序树的删除算法——伪代码1.若结点p是叶子，则直接删除结点p；2.若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则3.1查找结点p的左子树上的最右下结点s及其父结点q；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的左儿子有右子树，则将s的左子树接到结点q的右子树上；否则，将s的左子树接到q的左子树上；3.4删除结点s；第十章按排序的规则不同，可分为5类：插入排序交换排序（重点是快速排序）选择排序归并排序基数排序插入排序有多种具体实现算法：1)直接插入排序2)折半插入排序3)表插入排序4)希尔排序直接插入排序的时间复杂度为o(n2)。直接插入排序是一种稳定的排序方法。折半插入排序就平均性能来说比直接插入排序要快。在插入第i个对象时，需要经过log2i+1次关键码比较，才能确定它应插入的位置。排序效率仍为O(n2)折半插入排序是一个稳定的排序方法。表插入排序算法分析：①无需移动记录，只需修改2n次指针值。但由于比较次数没有减少，故时间效率仍为O(n2)。②空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。③稳定性：25和25*排序前后次序未变，稳定。希尔排序：时间效率：O(n1.25）～O（1.6n1.25）空间效率：O（1）稳定性：不稳定交换排序的主要算法有：1)冒泡排序2)快速排序冒泡：时间效率：O（n2)—因为要考虑最坏情况空间效率：O（1）—只在交换时用到一个缓冲单元稳定性：稳定—25和25*在排序前后的次序未改变快速排序的平均排序效率为O(nlog2n)；但最坏情况(例如已经有序)下仍为O(n2)选择排序有多种具体实现算法：1)简单选择排序2)锦标赛排序3)堆排序选择排序：时间效率：O(n2)——虽移动次数较少，但比较次数仍多。空间效率：O（1）——交换时用到一个暂存单元！算法的稳定性：不稳定——因为排序时，25*到了25的前面。锦标赛排序：时间复杂度：O(nlog2n)—n个记录各自比较约log2n次空间效率：O(n）—胜者树的附加内结点共有n’-1个！稳定性：稳定堆的定义：设有n个元素的序列k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。ki≤k2iki≥k2iki≤k2i+1或ki≥k2i+1如果让满足以上条件的元素序列（k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。时间效率：O(nlog2n)稳定性：不稳定归并排序算法分析：时间效率：O(nlog2n)稳定性：稳定最高位优先法MSD最低位优先法LSD排序方法最好情况平均时间最坏情况辅助存储稳定性简单排序O(n)O(n2)O(n2)O(1）稳定快速排序O(nlgn)O(nlgn)O(n2)O(lgn)不稳定堆排序O(nlgn)O(nlgn)O(nlgn)O(1）不稳定归并排序O(nlgn)O(nlgn)O(nlgn)O(n）稳定基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定简单选择O(n2)O(n2)O(n2)O(1）不稳定对基本有序的情况，可选用直接插入、堆排序、冒泡排序、归并排序等方法；在基本无序的情况下，最好选用快速排序、希尔排序。直接插入O(n)O(n2)O(n2)O(1）稳定折半插入O(nlgn)O(n2)O(n2)O(1）稳定冒泡O(n)O(n2)O(n2)O(1）稳定