数据结构笔记【全 |
您所在的位置：网站首页 › 408数据结构有几道大题 › 数据结构笔记【全 |
数据结构笔记【全
|
数据结构
思维导图
数据 信息的载体数据元素 数据的基本单位数据项 是构成数据元素的不可分割最小单位。学生记录是一个数据元素，由学号姓名这些数据项共同组成数据对象 具有相同性质的数据元素的集合，是数据的子集 数据类型 数据类型是一个值的集合和定义在集合上的一组操作的总称。 原子类型 值不可分的数据类型结构类型 可分的抽象结构类型 抽象数据组织及与之相关的操作 数据结构三要素算法的设计取决于所选的逻辑结构，而算法的实现依赖于所选的存储结构 逻辑结构 数据元素之间的关系，分为线性结构和非线性结构 线性结构 线性表，栈，队列等非线性结构 树、图、集合等集合（无关系）、线性结构（一对一）、树形结构（一对多）、图状结构或网状结构（多对多） 存储结构 顺序存储 可以随机存取，只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。链式存储、 只能顺序存储。不会出现碎片现象，能充分利用所有存储单元，指针要占用额外空间索引存储 检索速度快，附加的索引表额外占用存储空间。增加和删除数据时也要修改索引表，会消耗不少时间散列存储 也叫哈希存儲。根据元素的关键字直接计算出该元素的存储地址，其优点是检索、增加和删除结点的操作都很快：缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。数据的运算 运算的定义针对逻辑结构，运算的实现针对逻辑结构 复杂度分析 算法概念与特性 有穷性、确定性、可行性 、输入、输出 好的算法满足 正确性、可读性、健壮性、效率与低存储量需求 总结： 逻辑结构：栈，线性表，队列顺序表，单链表，邻接表，单双链表，循环链表。 还有一些名词：顺序存储，链式存储，索引存储，散列存储（哈希存储）。 线性表 顺序存储 顺序表 链式存储 单链表、双链表、循环链表、静态链表 总结几个判空 没有头结点的链表判空 head==null有头结点的链表判空 head->next == null循环单链表的判空： L->next =L循环双链表的判空: L-next == L && L->prior==L 栈和队列 操作受限栈 基本概念 栈的数学性质 出栈元素的不同排列个数为 (n个数的排列为A!,计算完排列之后别忘了取出不合适的)基本操作 顺序栈 操作 S.top。S.top=-1 进栈 栈未满的情况下：S.data[++S.top]=x;出栈 栈不空的情况下：x=S.data[S.top–];判空 S.top==-1栈满 S.top==MaxSize-1栈长 S.top+1S.top=0时，即top指向栈顶元素的下一位置。则入栈操作变成S.data[S.top++]=x,出栈为x=S.data[–S.top] 区分top指向的是当前栈顶元素还是下一元素 链栈 共享栈 初始指针 top0=-1，top1=Maxsize栈满 top1-top0=1进栈操作 0号栈先加一再赋值，一号栈先赋值再加一出栈 相反特点 更好的利用存储空间，避免上溢队列 基本概念 队首出（删除），队尾入队（增加） 判空 Q.frontQ.rear0子主题 2判满 无法判断，继而引出循环队列循环队列 三种区分队空与队满方法 牺牲一个元素 队满 (Q.rear+1)%MaxSize ==Q.front队空 Q.front==Q.rear元素个数 （Q. rear-Q. front+MaxSize）% Maxsize增设表示元素个数 增设tag数据成员 P79页循环队列出入队示意图 链式队列 双端队列 输出受限的双端队列输入受限的双端队列 推广数组 一维数组 多维数组 压缩矩阵 对称矩阵 上下三角矩阵 存储元素个数比对称矩阵多一三对角矩阵 特点 ｜i-j｜>1按行优先和按列优先 稀疏矩阵 可采用三元组存储 栈和队列的应用栈 栈的括号匹配 从左到右扫描，最后栈为空才算成功匹配前中后缀表达式 后缀表达式：考虑算法的优先级，没有括号 ，遇到运算符，依次弹出栈中优先级高于或等于的运算符。中缀转前缀：从右往左扫描下一元素。（先出栈的是左操作数）后缀表达式转为中缀表达式表达式之间的互相转换后缀表达式的求值习题解析王道P98页栈的递归 在于能发将原始问题转换为属性相同但规模交较小的问题。 递归调用过程： 在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。队列 队列的层次遍历 层次遍历二叉树过程图的广度优先搜索（使用队列）队列在计算机系统中的应用 树与二叉树 树递归的数据结构，也是一种逻辑结构 定义 两个特点：前驱后继结点个数术语 祖先，双亲，子孙，孩子，兄弟结点 结点的度，树的度 树的度：树中结点的最大度数分支结点，叶子结点 分支结点又称为非终端结点，其度大于0结点的层次，结点的深度，结点的高度，树的高度。 结点的层次：从树根开始结点的深度：从根结点开始自顶向下逐层累加结点的高度：从叶结点开始自底向上逐层累加树的高度：树中结点最大层数有序树，无序树 有序树，结点位置不能互换路径，路径长度 路径是，两个结点之间所经过的结点序列。而路径长度是路径上经过的边的个数树的性质 树中的结点数等于所有结点数+1度为m的数中第i层至多有总结计算：由n=分支数+1，即n=1+n1+2n2+3n3+4*n4=n0+n1+n2+n3+n4 二叉树概念 二叉树是有序树 二叉树和度为2度有序树区别 度为2度有序树，结点至少三个，而二叉树可以为空 二叉树的次序是绝对的，不能颠倒 特殊二叉树 满二叉树 满完全二叉树 左孩子二叉排序树 相比根结点左小右大平衡二叉树 左右子树的深度相差均不超过1二叉树的性质 非空二叉树n0=n2+1二叉树的存储 顺序存储 适合满二叉树和完全二叉树存储时建议数组下标从1开始 链式存储 左右指针和数据域在n哥结点的二叉链表中，含有n+1个指针域总结： 计算完全二叉树的结点个数，根据叶子结点进行计算。需要注意，最多最少的情况下，可能是倒数第二层最右边的代表叶子结点，也可能是最后一层代表。完全二叉树，根据结点个数和叶子结点个数求最多，需要考虑最后一层为奇数还是偶数，偶数的一半为消耗上层叶子结点个数，奇数要+1考虑极端情况下，结点个数根据树的那几个性质进行推算，注意奇偶数目操作 三种遍历 先序遍历 前缀表达式后序遍历 中缀表达式（需要加界限符）中序遍历 后缀表达式时间复杂度，空间复杂度都为O(n) 线索二叉树 引入线索二叉树的目的规定构造过程二叉树的计算题 空指针的个数 中序+后序推导 中序+前序推导 层序+中序推导 王道第五章 08应用 排序二叉树 平衡二叉树哈夫曼树 树，森林树的存储结构 双亲表示法 利用结点唯一双亲的性质 可以很快得到每个结点的双亲，但是求孩子结点，需要遍历整个结构 区别二叉树的顺序存储和树的顺序存储 二叉树的顺序存储即代表了结点的编号，也指示了各结点之间的关系。孩子表示法 将每个结点的孩子结点都用单链表链接起来形成一个线性结构，n个结点n个孩子链表寻找子女非常方便，但是寻找双亲需要遍历孩子兄弟表示法 二叉链表表示：每个结点分为三部分，结点值，指向结点第一个孩子结点的指针，指向结点下一个兄弟结点的指针。 通过第二个指针可以方便找到结点的所有兄弟结点。 最大优点，方便实现树转换为二叉树的操作，易于查找孩子结点。 子主题 1缺点是从当前结点查找父结点比较麻烦 树，森林与二叉树的转换 给定一颗树找到可以唯一的一颗二叉树与之对应，物理结构上看，他们的二叉链表上一样的，只是解释不同 - 二叉树转换为树或者森林也是唯一的树转二叉树的规则 左孩子右兄弟补充：树转成二叉树时，若有几个叶子结点具有共同的双亲，则转换成二叉树后之后一个叶子结点，树转二叉树的画法 1。在兄弟结点之间加一条线2。对每个结点，只保留它与第一个孩子的连线，而与其它孩子的连线全部抹掉3。以树根为轴心，顺时针旋转45度森林转化为二叉树 先将每棵树转换为二叉树，然后把其他树视为右兄弟。与上面相同森林转为二叉树的画法 1。将森林的每棵树转换为响应的二叉树，2。每棵树的根也可视为兄弟关系在每棵树的根之间加一根连线3。以第一棵树的根为轴心顺时针旋转45度二叉树转换为森林的规则 如果二叉树非空，则将二叉树的根和左子树视为第一棵树，将其右链断开二叉树的右子树又可以视为由森林转换的二叉树，直到只剩下一颗右子树为止将每棵二叉树分别转换树和森林的遍历 树的两种方式 补充：无法使用中根遍历，因为可能会有多个孩子。也可使用层次遍历 先根遍历 对应二叉树的先序序列后根遍历 对应二叉树的中序序列森林的两种遍历方式 先序遍历森林 对应二叉树的先序遍历中序遍历森林 对应二叉树的中序遍历补充总结： 考试可能会考，树到二叉树之后的右指针变化，右孩子结点个数，原来两个结点之间的关系。需要我熟练掌握转换。没事多画画，带入特殊构造点。哈哈😄 树和二叉树的应用二叉排序树BST 中序遍历可得到递增序列 二叉排序树的非递归查找算法 查找失败：左或右为空插入 二叉排序树的插入算法构造：从空开始删除 被删除的三种情况 1。叶子结点，直接删除2。若只有一颗左子树或右子树，直接用子树进行代替3。如果左右子树都有，则用其直接后继（或直接前驱）代替。然后从二叉树中删除这个元素，从而转换为前两种情况（中序遍历的后继元素，）（不要忘记对替代的元素删除后进行调整）查找 查找效率取决于树的高度 二分查找和二叉排序树的区别和联系 时间性能差不多二叉排序树的查找不唯一，相同关键字的插入顺序不同，生成的二叉排序树可能不同维护有序时，二叉排序树不需要移动，执行时间为log2n.二分查找为哦（n).所以当有序表时静态时采用顺序表作为存储结构，二分查找实现，为动态查找表时，采用二叉排序树作为逻辑结构。平衡二叉树AVL 概念 平衡因子 左右子树的差值，只能是-1，0，1插入 先检查是否会因插入导致失衡 如果导致了失衡，需要进行调整。先找到距离最近的平衡因子绝对值大于1的结点A，再对以A为根的子树，进行调整到平衡。 平衡二叉树的四种调整 LL平衡旋转（右单旋转） 由于A的左孩子的左子树插入结点引起。左侧结点高，旋转到右侧最后两层看为一个整体，最上层为根结点进行右旋转一次。根结点的右结点变为新右结点的左结点。新右结点为根结点的父结点RR平衡旋转（左单旋转） 由于A的右孩子的右子树上插入结点引起。右侧结点高与ＬＬ相反LR平衡旋转（先左后右双旋转） A的左孩子的右子树上插入了一个结点先左旋C替换B，然后再右旋替换ARL平衡旋转（先右后左双旋转） 由于A的右孩子的左子树上插入新结点先右旋C替换B，然后左旋替换A注意⚠️平衡二叉树根据关键字插入。 平衡二叉树的查找 比较次数 最多比较次数相当于树的最大高度深度为h的平衡二叉树的最少结点 递推公式 这种情况下其非叶子结点平衡因子也都是1n个结点平衡二叉树的最大深度 Log2n向上取整哈夫曼树和哈夫曼编码 带权路径长度（WPL）最小的二叉树称为哈夫曼树 哈夫曼树的wpl计算，只计算叶子结点，别看错啦哈夫曼树的构造过程 哈夫曼树的特点 1。每个初始结点最终都成为叶结点，权值越小的结点到根结点的路径长度越大2。构造过程共新建了n-1个结点，总共2n-1个结点3。哈夫曼树不存在度为1度结点其他补充：哈夫曼树可能构造的不唯一（可为左或者右，影响哈夫曼编码），但wpl一定是相同且最优的哈夫曼编码 编码 固定长度编码 每个字符用相同长度的二进制表示可变长度编码 不同长度的 优点是对频率高的字符赋予短编码，从而使得字符的平均编码长度减短，起到压缩数据的效果前缀编码 没有一个编码是另外一个编码的前缀，称这种为哈夫曼树构造哈夫曼编码 权值为字符出现的次数或频度字符仅出现在叶结点上0转向左孩子，右转向右孩子哈夫曼编码长度计算 遵循前缀编码补充 哈夫曼编码是对于确定的字符串来讲的（根据字符串的次数建立）哈夫曼树的推广 需要添加权为0的假结点，并且离根最远 图 图的基本概念图的定义 图G是由顶点集V和边集E组成，记做G=(V，E)V(G)代表顶点个数，不能为空E(G)代表边关系的集合|V|代表图G的顶点个数，也称为图G的阶补充：线性表可以是空表，树可以是空树，但是图不能是空图，也就是说，图不能一个顶点也没有，可以没有边，不能没有顶点有向图 注意是用表示边无向图 注意是用(v,w)表示简单图 一个图G若满足：①不存在重复边：②不存在顶点到自身的边，则称图G为简单图补充：数据结构中仅讨论简单图。多重图 若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。多重图的定义和简单图是相对的完全图 对于无向图，E的取值范围是0到n（n-1）2，有n（n-1）/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，E的取值范围是0到n(n-1），有n(n-1）条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。子图 顶点和边的集合都是他的子集，可以说是图的子图注意：并非卩和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中连通、连通图、连通分量 在无向图中，若从顶点ν到顶点ν有路径存在，则称ν和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。注意：弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图强连通、强连通分量 在有向图中，若从顶点v到顶点w和从顶点w到顶点ν之间都有路径，则称这两个顶点是强连通的 若图中任何一对顶点都是强连通的，则称此图为强连通图。 强连通图和完全有向图区别有向图中的极大强连通子图称为有向图的强连通分量， 注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性 生成树、生成森林 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。顶点的度，入度和出度 对于有向图，顶点v的度分为入度和出度，有向图的入度与出度和相等，并且等于边数。无向图全部顶点度的和等于边数的二倍顶点的度等于其入度和出度之和边的权和网 边上标的数值称为边的权有权值的图就就叫做网带权路径长度：一条路径上所有边的权值之和稠密图和稀疏图 边的多少，没有具体划分，一般是E |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |