做动效很好的网站,wordpress是PHP框架吗,广西电网公司建设年鉴,小程序制作价格目录 一、数据结构概论二、算法概论三、线性表四、栈五、队列六、串七、多维数组与矩阵八、广义表九、树与二叉树十、图 一、数据结构概论
1、数据元素和数据项 数据由数据元素组成#xff0c;即数据元素是数据的基本单位#xff0c;而数据元素又由若干个数据项组成#xf… 目录 一、数据结构概论二、算法概论三、线性表四、栈五、队列六、串七、多维数组与矩阵八、广义表九、树与二叉树十、图 一、数据结构概论
1、数据元素和数据项 数据由数据元素组成即数据元素是数据的基本单位而数据元素又由若干个数据项组成数据项是组成数据元素的最基本、不可分割的最小单位。 2、数据结构 数据结构是数据元素中存在一种或多种特定关系的数据元素的集合即数据结构就是带结构的数据元素集合包括逻辑结构、存储结构物理结构和数据的运算共三个方面三个方面缺一不可。另外可以用抽象数据类型定义一个完整的数据结构。 探究一种数据结构的方法可分为三个步骤 1、数据如何组织 2、数据如何存储 3、数据的运算如何实现 3、逻辑结构 逻辑结构指的是数据元素之间在逻辑上的关系可分为线性结构和非线性结构线性结构是一对一的关系例如有线性表、栈、队列、串、一维数组等非线性结构是一对多或多对多的关系例如有二维数组多维数组、广义表、树二叉树、图等。 #mermaid-svg-nnkhZ48J1VzsH3TF {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .error-icon{fill:#552222;}#mermaid-svg-nnkhZ48J1VzsH3TF .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-nnkhZ48J1VzsH3TF .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-nnkhZ48J1VzsH3TF .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-nnkhZ48J1VzsH3TF .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-nnkhZ48J1VzsH3TF .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-nnkhZ48J1VzsH3TF .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-nnkhZ48J1VzsH3TF .marker{fill:#333333;stroke:#333333;}#mermaid-svg-nnkhZ48J1VzsH3TF .marker.cross{stroke:#333333;}#mermaid-svg-nnkhZ48J1VzsH3TF svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-nnkhZ48J1VzsH3TF .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .cluster-label text{fill:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .cluster-label span{color:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .label text,#mermaid-svg-nnkhZ48J1VzsH3TF span{fill:#333;color:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .node rect,#mermaid-svg-nnkhZ48J1VzsH3TF .node circle,#mermaid-svg-nnkhZ48J1VzsH3TF .node ellipse,#mermaid-svg-nnkhZ48J1VzsH3TF .node polygon,#mermaid-svg-nnkhZ48J1VzsH3TF .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-nnkhZ48J1VzsH3TF .node .label{text-align:center;}#mermaid-svg-nnkhZ48J1VzsH3TF .node.clickable{cursor:pointer;}#mermaid-svg-nnkhZ48J1VzsH3TF .arrowheadPath{fill:#333333;}#mermaid-svg-nnkhZ48J1VzsH3TF .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-nnkhZ48J1VzsH3TF .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-nnkhZ48J1VzsH3TF .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-nnkhZ48J1VzsH3TF .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-nnkhZ48J1VzsH3TF .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-nnkhZ48J1VzsH3TF .cluster text{fill:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF .cluster span{color:#333;}#mermaid-svg-nnkhZ48J1VzsH3TF div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-nnkhZ48J1VzsH3TF :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 逻辑结构 线性结构 一对一 非线性结构 一对多 多对多 4、存储结构物理结构 数据的逻辑结构在计算机中的表示称为存储结构也称为物理结构包括数据元素的表示和关系的表示根据其存储特点可以分为四种存储结构即顺序存储结构、链式存储结构、索引存储结构和散列存储结构。 #mermaid-svg-yrap8nn6zRpEE8pU {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .error-icon{fill:#552222;}#mermaid-svg-yrap8nn6zRpEE8pU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-yrap8nn6zRpEE8pU .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-yrap8nn6zRpEE8pU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-yrap8nn6zRpEE8pU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-yrap8nn6zRpEE8pU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-yrap8nn6zRpEE8pU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-yrap8nn6zRpEE8pU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-yrap8nn6zRpEE8pU .marker.cross{stroke:#333333;}#mermaid-svg-yrap8nn6zRpEE8pU svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-yrap8nn6zRpEE8pU .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .cluster-label text{fill:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .cluster-label span{color:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .label text,#mermaid-svg-yrap8nn6zRpEE8pU span{fill:#333;color:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .node rect,#mermaid-svg-yrap8nn6zRpEE8pU .node circle,#mermaid-svg-yrap8nn6zRpEE8pU .node ellipse,#mermaid-svg-yrap8nn6zRpEE8pU .node polygon,#mermaid-svg-yrap8nn6zRpEE8pU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-yrap8nn6zRpEE8pU .node .label{text-align:center;}#mermaid-svg-yrap8nn6zRpEE8pU .node.clickable{cursor:pointer;}#mermaid-svg-yrap8nn6zRpEE8pU .arrowheadPath{fill:#333333;}#mermaid-svg-yrap8nn6zRpEE8pU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-yrap8nn6zRpEE8pU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-yrap8nn6zRpEE8pU .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-yrap8nn6zRpEE8pU .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-yrap8nn6zRpEE8pU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-yrap8nn6zRpEE8pU .cluster text{fill:#333;}#mermaid-svg-yrap8nn6zRpEE8pU .cluster span{color:#333;}#mermaid-svg-yrap8nn6zRpEE8pU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-yrap8nn6zRpEE8pU :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 存储结构 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 以上四种存储结构由于每种存储结构都有其优缺点不能直接地说哪种存储结构最优只能说在针对某种数据结构中需要选择不同的存储结构时应该选择符合其特点的数据结构才是最优的。 5、顺序存储结构 顺序存储由存储单元的邻接关系体现即把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里其中数据是连续的。该存储结构的优点是可以实现随机存取每个元素占用最少的存储空间缺点是由于只能使用相邻的一整块存储单元从而会产生较多的外部碎片。 以线性表为例通过顺序存储的线性表称为顺序表它是将线性表中所有元素按照其逻辑顺序依次存储到指定存储位置开始的一块连续的存储空间里而通过链式存储的链表中每个结点不仅包含该元素的信息还包含元素之间的逻辑关系的信息。 6、链式存储结构 链式存储不要求逻辑上相邻的元素物理位置上也相邻而是通过指示元素存储地址的指针来体现元素之间的逻辑关系其数据是可离散的。该存储结构的优点是充分利用了所有的存储单元不会造成碎片现象但缺点是由于通过指针来表示逻辑关系所以指针也要存储从而占用额外的存储空间即链式存储的存储结构所占存储空间分两部分一部分存放结点的值另一部分存放表示结点间关系的指针结点内的存储单元要求连续而不同结点的存储空间可以不连续例如顺序表的存储密度1而链表的存储密度1是由于结点中含有指针域。另外链式结构只能顺序存取不能随机存储。 以线性表为例单链表是通过链式存储的其每个结点除了存放数据元素之外还存储指向下一个结点的指针而顺序表是顺序存储的其每个结点只存放数据元素。顺序存储结构可以随机存取、顺序存取而链式存储结构只能顺序存取顺序存储结构不仅可用于存储线性结构还能用于树、图等非线性结构。 针对线性表以上两种存储结构在线性表中的实际选择 在一般情况下若需对表进行频繁的插入、删除操作此时适合选链式存储因为顺序表平均需要移动近一半的元素且耗费时间其插入和删除算法的平均时间复杂度为O(n)而链表在插入和删除操作时不需要移动元素只需修改指针当若表的总数基本稳定且很少进行插入和删除操作则顺序表相较于链表可以充分发挥其存取速度块、存储利用率高的优点。 7、索引存储结构 索引存储在存储数据元素的同时还需要建立附加的索引表其中的索引项的形式为关键字和地址其数据是可离散的。该存储结构的优点是在查找数据元素时很快、容易找到而缺点是由于附加了索引表从而占用了额外的存储空间同时若需要增加和修改数据时需修改索引表会花费较多时间。 例如查找算法中树型查找的B树、B树的应用到了索引存储结构。 8、散列存储结构 散列存储是根据数据元素的关键字直接计算其存储地址也称为哈希存储Hash其数据是可离散的。该存储结构的优点是在对数据元素进行增加、删除结点操作时很快而缺点是若定义的哈希函数不能完全贴合情况则会发生元素存储单元的冲突而减少冲突从而会花费时间和一定的空间上的开销。 例如哈希表即为一种基于散列存储结构的查找表。 二、算法概论
1、算法分析 将解决问题的确定方法和有限步骤称为算法在计算机中算法指的是对特定问题求解步骤的一种描述是若干条指令的有穷序列。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析分析算法的效率以求改进是其目的。通过设计一个具有正确性、可读性、健壮性、高效率执行速度快时间复杂度低和低存储不费内存空间复杂度低的算法再加上合适的数据结构从而构成一个良好的程序。 程序 算法 数据结构 2、算法的特性 算法具有五个特性分别是输入、输出、确定性、可行性和有穷性。 算法可以有零个或多个输入但算法至少有一个或多个输出。 3、时间复杂度 时间复杂度是对算法运行时间的数量级有两种度量方法分别是事后统计法和事前分析估算法计算算法的时间复杂度属于一种事前分析估算的方法。通常对一个算法的时间复杂度考察三个方面即最好情况、平均情况和最坏情况从而对应最好时间复杂度、平均时间复杂度和最坏时间复杂度其中平均时间复杂度是指所有输入在等概率的情况下该算法的期望运行时间。时间复杂度为O(1) 常数阶算法的效率最高而像O(2n) 、 O(n!) 、 O(nn)这类的算法的效率最低如下图 4、空间复杂度 空间复杂度是指定义该算法所需要耗费的存储空间根据其规模函数f(n)可记为O[f(n)]若算法需要的存储空间是常量则其空间复杂度为O(1)。 5、递归算法 一个递归算法必须包括终止条件和递归部分例如二叉树的先序、中序、后序遍历中每一次函数调用都会在内存栈中分配空间都运用了递归算法。另外n的阶乘也是一个递归算法该递归算法停止条件是n0函数可定义如下 n ! { 1 n0 n ( n − 1 ) ! n0 n! \begin{cases} 1 \text{n0}\\ n(n-1)! \text{n0} \end{cases} n!{1n(n−1)!n0n0 6、贪心法 贪心算法不考虑整体上最优而只考虑局部上最优来解决问题即每次选择的都是最优的解决方案不考虑该决策对整体的影响即贪心算法的时间复杂度一般较低但缺点是不能保证得到全局上的最优解。贪心法的两大性质为最优子结构性质【可分割】和贪心选择性质【局部最优】。 贪心算法在处理一些情况下可以得到最优解的很好近似方案例如哈夫曼编码、求最小生成树中的普里姆算法Prim、克鲁斯卡尔算法Kruskal、求单源最短路径中的迪杰斯特拉算法Dijkstra等算法。 7、分治法 分治法分为分解、治理两大步骤主要在于将问题划分成相互独立的子问题。分解是将问题分解成多个规模上较小、内容上相互独立、性质上与原问题相同的子问题治理是对各个子问题直接求解若仍不容易解决则再进行进一步分解后再求解由于性质相同所以求解子问题的解决方法和原问题是相同的另外治理中包含合并是将得到的各个子问题的解进行合并从而得到原问题的解。若各个子问题之间不是相互独立的时则会造成重复分治法会有很高的时间复杂度。 #mermaid-svg-S9X4o3tLAwsQDbaQ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .error-icon{fill:#552222;}#mermaid-svg-S9X4o3tLAwsQDbaQ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-S9X4o3tLAwsQDbaQ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .marker.cross{stroke:#333333;}#mermaid-svg-S9X4o3tLAwsQDbaQ svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .cluster-label text{fill:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .cluster-label span{color:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .label text,#mermaid-svg-S9X4o3tLAwsQDbaQ span{fill:#333;color:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .node rect,#mermaid-svg-S9X4o3tLAwsQDbaQ .node circle,#mermaid-svg-S9X4o3tLAwsQDbaQ .node ellipse,#mermaid-svg-S9X4o3tLAwsQDbaQ .node polygon,#mermaid-svg-S9X4o3tLAwsQDbaQ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .node .label{text-align:center;}#mermaid-svg-S9X4o3tLAwsQDbaQ .node.clickable{cursor:pointer;}#mermaid-svg-S9X4o3tLAwsQDbaQ .arrowheadPath{fill:#333333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-S9X4o3tLAwsQDbaQ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-S9X4o3tLAwsQDbaQ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-S9X4o3tLAwsQDbaQ .cluster text{fill:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ .cluster span{color:#333;}#mermaid-svg-S9X4o3tLAwsQDbaQ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-S9X4o3tLAwsQDbaQ :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 分治法 分解 治理 合并 分治法在查找中的二分折半查找和排序中快速排序、归并排序中应用例如快速排序基于分治思想通过多次划分操作来实现排序 8、动态规划 动态规划通常解决的是具有重叠子问题性质和最优子结构性质的问题其中解决子问题只需一次解决后会将其解保存并重复使用从而避免重复计算。动态规划通常采用自底向上的方式通过先解决子问题再解决大问题的方式进行求解。动态规划适合用于优化问题并且能够保证得到全局最优解。但对比贪心法、分治法算法由于需要存储各种状态所以其需要的空间更大。 贪心法、分治法与动态规划的对比 这三种算法共同点都是在解决问题时通过划分子问题、解决子问题的方法来的贪心法的解决方案呈线性每次都是选择局部最优分治法主要在于将问题划分成相互独立的子问题动态规划主要解决子问题重叠的情况且每个子问题只解决一次子问题的解被存储从而避免了重复计算。 9、搜索算法 1穷举搜索 穷举搜索法也被称为穷举法其基本思想是将问题的所有的候选解都枚举出来然后对候选解按照某种顺序进行逐一枚举和检验并从中找出符合问题要求的候选解作为问题的解。其优点是实现简单且易于理解适合规模较小的问题但当问题的规模较大时由于需要运行问题所有的候选解消耗大量的时间从而导致算法的效率大大降低。 2回溯法 回溯法用到了深度优先搜索DFS的思想首先通过穷举所有可能的解明确搜索范围从初始状态出发以深度优先搜索来搜索解若当前结点不满足则会退一步回溯到上一个结点尝试其他选择直到最后找到包含问题解的结点。当问题规模较大时由于需要穷举所有可能的解此时回溯法的搜索效率较低。【找出解空间树中满足约束条件的所有解】 另外回溯法中还运用了剪枝函数隐约束来避免无效搜索所以可以说回溯法是一种带有约束函数约束条件或限界函数限界条件的深度优先搜索方法。 3分支限界法 分支限界法中通常采用广度优先搜索BFS以最大收益最小耗费的方式来搜索解空间树其中的限界就是利用上界和下界来提高搜索效率即搜索解空间树中利用上界和下界的信息来剪枝搜索树的分支舍弃导致不可行解或导致非最优解的分支。【找出解空间树中满足约束条件的一个解】 回溯法的适用场景有n皇后问题、子集树0-1背包问题、最大团问题、排列树旅行商问题、批处理作业调度问题、组合树图的m着色问题等等 分支限界法的适用场景有0-1背包问题、旅行商问题、集装箱装载问题、电路设计中的布线问题等等。 10、NP完全理论 P类问题是较“容易”的问题在计算机中可以在多项式时间内解决而NP类问题是较“复杂”的问题只能验证是否存在解解是否正确。主要区别在于时间复杂度P类问题时间复杂度较低而NP类问题可以在多项式时间内的不确定性算法来进行判定或求解问题其求解过程较困难。 常见的P类问题有排序、搜索算法等等但不是所有的排序算法都是P类问题例如排序中的快速排序、堆排序和归并排序是P类问题其平均时间复杂度呈多项式而由于插入排序、冒泡排序、简单选择排序的平均时间复杂度都呈指数级所以不属于P类问题属于NP类问题。 NP完全问题是NP问题的一个子类可以说它比NP问题更复杂的问题也是只能在多项式时间内验证问题的解例如多项式变换技术问题、布尔可满足性问题以及旅行商问题TSP、哈密尔顿回路问题等等。
三、线性表
1、线性表 线性表是具有相同数据类型的n个数据元素的有限序列其中n≥0即线性表可以为空有限序列可以为空当n0时称线性表是一个空表。线性表是一种逻辑结构且为线性结构即数据元素之间是一对一关系。另外线性表中表头元素无前驱表尾元素无后继。 2、线性表的存储结构 通过不同的存储结构可以将线性表分为由顺序存储结构的顺序表和由链式存储结构的链表链表包括单链表、双链表、循环链表等顺序存储结构是通过物理上相邻的地址来表示逻辑关系而链式存储结构是通过指针来表示逻辑关系。另外链表还可以细分例如静态链表中指针是通过结点的数组下标表示它是借助数组来描述链式结构。 #mermaid-svg-nOwczjKCiwVcPM1q {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .error-icon{fill:#552222;}#mermaid-svg-nOwczjKCiwVcPM1q .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-nOwczjKCiwVcPM1q .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-nOwczjKCiwVcPM1q .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-nOwczjKCiwVcPM1q .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-nOwczjKCiwVcPM1q .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-nOwczjKCiwVcPM1q .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-nOwczjKCiwVcPM1q .marker{fill:#333333;stroke:#333333;}#mermaid-svg-nOwczjKCiwVcPM1q .marker.cross{stroke:#333333;}#mermaid-svg-nOwczjKCiwVcPM1q svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-nOwczjKCiwVcPM1q .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .cluster-label text{fill:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .cluster-label span{color:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .label text,#mermaid-svg-nOwczjKCiwVcPM1q span{fill:#333;color:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .node rect,#mermaid-svg-nOwczjKCiwVcPM1q .node circle,#mermaid-svg-nOwczjKCiwVcPM1q .node ellipse,#mermaid-svg-nOwczjKCiwVcPM1q .node polygon,#mermaid-svg-nOwczjKCiwVcPM1q .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-nOwczjKCiwVcPM1q .node .label{text-align:center;}#mermaid-svg-nOwczjKCiwVcPM1q .node.clickable{cursor:pointer;}#mermaid-svg-nOwczjKCiwVcPM1q .arrowheadPath{fill:#333333;}#mermaid-svg-nOwczjKCiwVcPM1q .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-nOwczjKCiwVcPM1q .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-nOwczjKCiwVcPM1q .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-nOwczjKCiwVcPM1q .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-nOwczjKCiwVcPM1q .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-nOwczjKCiwVcPM1q .cluster text{fill:#333;}#mermaid-svg-nOwczjKCiwVcPM1q .cluster span{color:#333;}#mermaid-svg-nOwczjKCiwVcPM1q div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-nOwczjKCiwVcPM1q :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 线性表 顺序存储结构 顺序表 顺序存储结构 链表 顺序表和链表的优缺点如下 顺序表实现简单可以随机存取其存储密度大但是执行插入、删除操作需要移动大量元素效率低另外其存储空间需事先分配容易造成空间浪费或溢出。 链表不支持随机存取只能顺序存取通过指针来体现元素之间的逻辑关系存储密度比顺序表小其执行插入、删除操作不需要移动元素只需修改指针效率高另外它还支持动态分配存储空间不会造成空间浪费或溢出。 3、顺序表的插入、删除和查找 1顺序表的插入 若在顺序表的表尾插入元素则不需要执行元素后移操作即最好情况所以最好时间复杂度为O(1)。若在顺序表的表头插入元素需要执行n次元素后移操作即最坏情况所以最坏时间复杂度为O(n)。设在顺序表第i个位置插入元素的概率为pi1/(n1)即设插入概率相同此时为平均情况在长度为n的线性表中插入一个结点所需移动元素的平均次数为n/2故顺序表插入操作的平均时间复杂度为O(n)。
名称插入时间复杂度最好时间复杂度O(1)最坏时间复杂度O(n)平均时间复杂度O(n)
2顺序表的删除 若删除顺序表的表尾元素则不需要执行元素后移操作即最好情况所以最好时间复杂度为O(1)与顺序表的插入操作的最好情况一样。若删除顺序表的表头元素则执行n次移动操作即最坏情况所以最坏时间复杂度为O(n)与顺序表的插入操作的最坏情况一样。设删除顺序表第i个位置上元素的概率为pi1/n即设删除概率相同在长度为n的线性表中删除一个结点若删除第一个结点需移动n-1次……删除第n个结点移动0次即平均情况所需移动元素的平均次数为(n-1)/2故顺序表的删除操作的平均时间复杂度为O(n)。
名称删除时间复杂度最好时间复杂度O(1)最坏时间复杂度O(n)平均时间复杂度O(n) 在长度为n的顺序表中删除第i个结点1≤i≤n时需要移动n-1个结点而在第i个结点1≤i≤n前插入一个结点时需要移动n-i1个结点。 3顺序表的查找 若查找元素在顺序表的表头则在常数级即可查找到该元素即最好情况最好时间复杂度为O(1)。若查找元素在顺序表的表尾或不存在时需要遍历整个顺序表即最坏情况最坏时间复杂度为O(n)。平均情况下按值查找一个元素的平均次数为(n1)/2故顺序表的按值查找的平均时间复杂度为O(n)。
平均情况下顺序表的各种操作数据元素的平均比较次数和平均时间复杂度如下表【插入n/2删除减一查找加一】
名称插入删除查找平均比较次数n/2(n-1)/2(n1)/2平均时间复杂度O(n)O(n)O(n)
4、单链表 单链表是链式存储的其每个结点除了存放数据元素之外还存储指向下一个结点的指针链表中不要求结点所占空间连续但是一个结点内部空间必须连续而顺序表是顺序存储的其每个结点只存放数据元素。单链表无论是否带有头结点其头指针都指向单链表中第一个结点在带头结点的单链表中头结点只作为单链表存在的标志且不存储数据。在带头结点的单链表若L-nextNULL时则该单链表为空即头结点的指针域next为空时此时单链表为空表。 头指针具有标识作用用头指针代指链表的名称同时可以防止链表为空头结点的设置保证了插入元素和删除元素操作的统一性带有头结点的单链表其存储位置存放在头结点L的指针域中指向单链表的第一个结点。 5、单链表的插入、删除 1插入操作——后插操作 单链表中在指针 *p 所指向的结点之后插入结点 *q先将 *q与原本 *p的指针域指向的结点相连再与p相连【先连后再连前】代码如下
q-nextp-next;
p-nextq;2插入操作——前插操作 在单链表中在 *p的前插入一个 *q指向的新结点以temp为中间变量即通过中间变量temp来交换数据域data的代码部分【先后插再交换】代码如下
q-nextp-next;
p-nextq;tempp-data; //交换数据域
p-dataq-data;
q-datatemp;3单链表的删除 在单链表中删除一个以前驱 *p *q指向的结点查找后删除的步骤可概括为【先定位后断开释放】将 *q指针指向要删除的结点p为其前驱结点代码如下
qp-next; //先定位定位删除位置
p-nextq-next; //断开q与p的连接p与下一个结点连接
free(q); //通过free()函数进行释放也可以在单链表中直接删除*p指向的结点代码如下
qp-next; //先定位定位删除位置
p-datap-next-data; //与后继结点交换数据域data
p-nextq-next; //断开q与p的连接p与下一个结点连接
free(q); //通过free()函数进行释放6、双链表 根据线性表的链式存储结构中每一个结点包含的指针个数可将线性链表分成单链表和双链表。双链表是在单链表结点上增添了一个指针域prior指针域prior指向当前结点的前驱结点即此时链表的每个结点中都有两个指针域prior和next从而可以很容易通过后继结点找到前驱结点故访问前驱和后继结点的时间复杂度都为O(1)。一个带头结点L的双链表若L-next NULL时则该双链表为空一个不带头结点的双链表若LNULL时则该双链表为空。 7、双链表的插入、删除 1双链表的插入 由于双链表可以很快地找到前驱结点所以双链表的插入、删除操作的时间复杂度都为O(1)。双链表的插入操作可以概括为【先连后再连前】若在指针 *p 指向的结点之后插入结点 *q首先新结点q与原本 *p的指针域相连即下一个结点然后将结点q插入到结点p之后再将其prior和next域相连代码如下
q-nextp-next;
p-next-priorq;
q-priorp;
p-nextq;这里的代码插入不唯一插入操作必须保证的是不能断链即不能导致*p的后继结点的指针丢掉。 2双链表的删除 双链表的删除的代码如下
p-nextq-next;
q-next-priorp;
free(q);8、循环单链表 1循环单链表的定义 循环单链表的优点是从任一结点出发都可以访问到链表中的每一个元素。在带头结点L的循环单链表中若L head-next时循环单链表为空在不带头结点的循环单链表中若LNULL时循环单链表为空。 2循环单链表的查找 在一个带头结点的循环单链表中 若只设置头指针L则查找表头结点的时间复杂度为O(1)查找表尾结点需要依次遍历整个链表即时间复杂度为O(n)而查找一个结点的前驱结点时的时间复杂度为O(n)若只设置尾指针R这样的好处是可以使查找链表的开始结点和终端结点很方便其查找时间都为O(1)而查找一个结点的前驱结点时的时间复杂度为O(n)。 3循环单链表的插入 循环单链表的插入操作与单链表类似也是【先连后再连前】若在指针 *p 指向的结点后插入结点 *p 步骤是首先将q的指针域与p结点原本的指向下一个结点的指针域相连即q-nextp-next然后再将q结点与p结点相连即p-nextq如下代码
q-nextp-next; //先连后
p-nextq; //再连前3循环单链表的删除 循环单链表的删除操作也与单链表类似删除的步骤可概括为【先定位后断开释放】将*q指针指向要删除的结点p为其前驱结点如下代码
qp-next; //先定位定位删除位置
p-nextq-next; //断开q与p的连接p与下一个结点连接
free(q); //free()函数释放结点9、循环双链表 1循环单链表的定义 循环双链表基于双链表头结点L的prior域指向表尾结点查找表头结点和表尾结点的时间复杂度均为O(1)查找一个结点的前驱结点时的时间复杂度也为O(1)。一个带头结点L的循环双链表若L-prior LL-next L时则该双链表为空。头结点的prior和next域都指向其本身时为空 2循环单链表的插入 若要在指针 *p 指向的结点后插入结点 *p其代码如下
q-nextp-next;
p-next-priorq;
q-priorp;
p-nextq;3循环单链表的删除 将*p指针指向要删除的结点其代码如下
p-next-priorp-prior;
p-prior-nextp-next;
free(p);10、静态链表 根据指针的连接方式链表可分成静态链表和动态链表。静态链表借助数组来描述链式结构每个数组元素有两个分量一是数据元素的值二是指针指针指向下一个元素在数组中的位置 (下标)。静态链表在插入和删除操作时只需修改指针而不需要不移动数据但静态链表不支持随机存取。另外若定义的数组太大有可能浪费较多的存储空间。
四、栈
1、栈 栈是被限制存取点的线性表只允许在一端进行插入或删除操作与队列具有相同的逻辑结构都属于线性结构区别在于对其中元素的处理不同栈遵循的原则是先进后出FILO即后进的元素先被取出来。由于它是一种线性表所以有两种方式顺序存储结构和链式存储结构即顺序栈和链式栈。另外栈的插入操作称为进栈栈的删除操作称为出栈。 栈有以下应用场景 ①递归及函数调用 ②表达式求值例如中后缀表达式、括号匹配等等 ③进制转换例如十进制数转为二进制数等等 ④迷宫求解 ⑤缓存机制 ⑥用栈对二叉树进行前、中、后序遍历 ⑦用栈模拟队列。 2、共享栈 使用共享栈可以更加有效地利用存储空间降低发生上溢的可能通过让两个顺序栈共享一个一维数组空间可以使其中一个栈可用该空间的一半或以上将这两个顺序栈的栈底分别设置在数组空间的两端其中两个栈的栈顶指针都指向栈顶元素当top1-1时顺序栈1为空当top2MaxSize时顺序栈2为空另外当两个栈顶指针相邻即top2-top11时此时共享栈满。 3、顺序栈 顺序栈存储空间的实现是使用数组来存储栈元素的通过一组数组地址的连续的存储单元来存放从栈底开始至栈顶的数据元素同时设置一个栈顶指针top用于指示当前栈顶元素的位置。判断顺序栈是否为空栈的条件是S.top-1判断顺序栈是否为满栈的条件是S.topMaxSize-1。 1进栈 将一个元素插入顺序栈中即进栈首先应判断栈是否为满【进栈先判满】即S.topMaxSize-1进栈的操作可以概括为指针先加1然后再入栈代码如下
/*进栈操作*/
bool StackPush(SqStack S,int x) {if(S.topMaxSize-1)//若栈已满则报错return false;S.top;//top指针始终指向栈顶新的元素进栈所以指针先加1S.data[S.top]x;//将进栈元素的值传入并入栈//S.data[S.top]x;return true;
}2出栈 将一个元素从顺序栈中删除即出栈首先应判断栈是否为空【出栈先判空】即S.top-1出栈的操作可以概括为先出栈然后指针再减1由于栈的特性只能先进后出即从栈顶进行删除操作代码如下
/*出栈操作*/
bool StackPop(SqStack S,int x) {if(S.top-1)//若栈为空则报错return false;xS.data[S.top];//出栈S.top--;//指针减1//xS.data[S.top--];return true;
}4、链栈 由于顺序栈的数组的大小是固定的不能动态分配大小而链栈相比顺序栈的最大优势就是它可以动态地分配存储空间。 1进栈 同单链表当中动态分配新结点的步骤类似创建一个值为x的新结点p通过malloc()函数动态分配需在开头加头文件#includestdlib.h首先将x值赋给新结点p的数据域中然后将新结点p插入到链栈的栈顶前最后再将新结点p作为当前栈顶元素完整代码如下
/*进栈插入操作*/
void PushStack(LinkStack S, int x) {StackNode *p;p (StackNode*)malloc(sizeof(StackNode));//动态分配创建一个新结点pp-data x; //将x放入新结点p的数据域中p-Lhead S; //将新结点p插入到当前链栈的栈顶前S p; //将新结点p作为栈顶元素
}2出栈 出栈操作首先必须判断栈是否为空【出栈先判空】即SNULL然后通过变量x将栈顶元素S-data赋给x取出然后将指针p指向原栈顶为要删除的结点并将栈顶S指向下一个结点最后通过free()函数释放要删除的结点p完整代码如下
/*出栈删除操作*/
bool PopStack(LinkStack S,int x) {StackNode *p;if(SNULL)//若栈为空则报错return false;xS-data;//x记录当前栈顶元素pS;//p指针指向原栈顶SS-Lhead;//S指向下一个结点free(p);//释放栈顶元素return true;
}5、栈的应用——前、中、后缀表达式转换 将常用的中缀表达式转换为前缀表达式、后缀表达式后可以通过栈的相关原理来实现具体的出栈 、入栈操作逻辑从而可以一样完成与中缀表达式相同的运算。 1中缀表达式转换为前缀表达式的思路 首先按照运算优先级将所有的操作数都加上括号然后将运算符移至相对应的括号前最后将括号去掉即可得到前缀表达式。 2中缀表达式转换为后缀表达式的思路 与前缀表达式相反第二步将运算符移至相对应的括号后然后再去掉括号即可。
五、队列
1、队列 队列与栈一样它也是一种特殊的线性表其操作受限与栈具有相同的逻辑结构都属于线性结构区别在于其中元素的处理不同栈遵循的原则是先进后出而队列的原则是先进先出FIFO栈只允许在一端进行插入、删除操作而队列只允许在一端进行插入、另一端进行删除操作。 队列的应用场景有以下 ①缓冲区例如计算机与打印机中间的打印数据缓冲区 ②页面替换算法 ③图的广度优先搜索、树的层次遍历都借助到了队列的基本思想。 2、循环队列 基于顺序存储结构的队列即为顺序队列由于顺序队列会出现“假溢出”的问题所以可以将顺序队列的一维数组首尾相连形成一个环状在逻辑上视为一个环连接起来即为循环队列。初始条件时循环队列为空其队头指针等于队尾指针即判空代码为Q.frontQ.rear指针front、rear都指向同一位置。判断循环队列是否为满队就要另外写代码规定牺牲一个存储单元来区分是否满队入队时少使用一个队列单元即队头指针在队尾指针的下一个位置时此时作为满队的条件【队尾指针加1取余等于队头指针】代码如下
//判断循环队列满队
if((Q.rear1)%MaxSizeQ.front)return true;1入队 其中队头指针、队尾指针加1时通过取余运算实现从而防止队列的“假溢出”。进队操作针对队尾指针即Q.rearQ.rear1%MAXSIZE。每次入队操作时首先判断队列是否为满队【入队先判满】然后先送值到队列的末尾然后再将队尾指针Q.rear加1取模通过%实现代码如下
//入队插入操作
bool EnterQueue(SqQueue Q,int x){if((Q.rear1)%MaxSizeQ.front) //若队列为满则报错 return false;Q.data[Q.rear]x; //送入入队数据元素x的值 Q.rear(Q.rear1)%MaxSize; //队尾指针加1取模 return true;
}2出队 出队操作针对队头指针即Q.frontQ.front1%MAXSIZE。每次出队操作时首先判断队列是否为空队【出队先判空】然后先取队列的队头元素然后再将队头指针Q.front加1取模通过%实现代码如下
//出队删除操作
bool PopQueue(SqQueue Q,int x) {if(Q.frontQ.rear) //若队列为空则报错 return false;xQ.data[Q.front]; //取出队头数据元素x的值 Q.front(Q.front1)%MaxSize; //队头指针加1取模 return true;
}3输出循环队列中的元素个数 若要输出当前循环队列中的元素个数首先判断队列是否为空然后通过队尾指针减队头指针加上MaxSize的值与MaxSize取余可得到数据元素个数即(Q.rear-Q.frontMaxSize)%MaxSize代码如下
//循环队列的数据元素个数
bool NumQueue(SqQueue Q){if(Q.frontQ.rear) //若队列为空则报错 return false;int num(Q.rear-Q.frontMaxSize)%MaxSize;printf(当前循环队列的数据元素个数为%d\n,num);
}3、链队列 链队是通过带有队头指针和队尾指针的单链表实现的使用链队的好处是可以避免出现队满溢出的问题且适用于数据元素变动较大的情形时若使用单链表来表示队列则使用带尾指针的循环单链表最合适。 用循环链表表示的队列长度为n若只设头指针则出队和入队的时间复杂度分别为O(1)和O(n)若只设尾指针则出队和入队的时间复杂度为O(1)和O(1)所以使用带尾指针的循环单链表最合适。 六、串
1、串 串是一种线性结构它也是一种特殊的线性表与栈和队列一样由零个或多个字符组成的有限序列串的数据元素必须是字符其通常以字符串的形式出现。由任意多个连续的字符组成的子序列称为串的子串包含子串的串称为主串线性表是以单个元素进行相关操作而串是以子串进行相关操作的。 空串是任意串的子串任意串是自身的子串。 2、定长顺序存储 通过静态数组实现定长顺序存储一组地址连续的存储单元存储串值的字符序列其中每个串都被分配一个固定长度的ch[MAXLEN]数组。 3、链式存储 对不确定长度的串进行存储时就要用到动态存储方式这里可以采用链式存储链式存储串中每个结点有两个域分为数据域data和指针域next数据域由于存放串的各字符指针域用于存放后继结点的地址。使用链式存储的优点是插入、删除运算方便但缺点是存储、检索效率低其空间利用率低。 4、堆分配存储 与定长顺序存储一样也是采用一组地址连续的存储单元来存放串值的字符序列但堆分配存储的存储空间是动态分配的通过malloc()和free()函数来完成动态存储的分配和释放。分配成功时返回一个指向起始地址的指针*ch作为串的基地址它指向动态分配存储区首地址的字符指针若分配失败则返回NULL。 5、KMP算法 串的模式匹配也称为串的定位搜索串中的子串若存在则返回子串在串S中第一次出现的位置。一般的字符串匹配算法的时间复杂度为O(m×n)而KMP算法的时间复杂度为O(mn)其主串指针不用回溯当主串的长度很大需要部分匹配和一次不能调入内存时其优点较一般匹配更突出。
七、多维数组与矩阵
1、数组 数组是由nn≥1个相同数据类型的数据元素组成的有限序列在定义数组时会为数组分配一个固定大小的内存空间用来存储元素数组在被定义后其维度不可以被改变。 数组在确定其维度和维界后元素的个数是固定的所以不能进行插入和删除运算。数组中最常见的两种操作是查找和修改。 2、多维数组 数组可分为一维数组和多维数组常见的有二维数组二维数组可以看作一维数组的一维数组。顺序表是一个一维数组所以它是线性结构与栈、队列、串的逻辑结构相同而多维数组则是典型的非线性结构也可以说它是嵌套的线性结构。
例如一个二维数组A[3][4]在内存中实际上是一个长度为3的一维数组每个元素是一个长度为4的一维数组即对应三行四列其中元素是从上到下、从左到右依次存储的如下
01230[00][01][02][03]1[10][11][12][13]2[20][21][22][23] 由于数组中是从下标0开始的所以一个m行n列的二维数组中最开始的元素是[00]最后的元素是[m-1n-1]上面三行四列的二维数组A[3][4]中的最后一个元素即为[23]。 3、多维数组的存储 二维数组的存储较一维数组不一样有两种存储方式可分为行优先存储和列优先存储前者是先按每行存储满后再继续下一行后者相反先按每列存储满后再继续下一列。
例如定义一个二维数组A[3][3]在连续的内存空间里如下 若按照行优先存储以A[2][0]为例在存储A[2][0]之前是这样存储的 而按照列优先存储以A[1][1]为例在存储A[1][1]之前是这样存储的 4、特殊矩阵与稀疏矩阵 在数据结构中矩阵是一个按照长方阵列排列的复数或实数集合。它通常由一组数的全体在括号内排列成m行n列横为行竖为列的一个数表并被称为m×n阵。若一个矩阵有n行n列则称该矩阵是一个n阶方阵。相同的元素或零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵反之则为稀疏矩阵。简单的来说特殊矩阵既然特殊说明其中有很多相同或者有零元素且存在一定规律在矩阵中分布。常见的特殊矩阵有对称矩阵、反对称矩阵、上/下三角矩阵、对角矩阵等等例如对角矩阵中只有对角线上有元素其余元素均为零 5、特殊矩阵的压缩存储 对矩阵压缩的目的是节省存储空间。若一个n阶方阵满足Ai×jAj×i则称为对称矩阵。由于对称矩阵中上三角部分和下三角部分的元素对应相同在存储对称矩阵时为了避免空间的浪费可以只存储上或下三角部分的元素将其存放在一个一维数组中数组的大小为12……nn(1n)/2。例如矩阵B如下将其视为一个对称矩阵 若对其进行压缩存储若按行序将元素通过一维数组存储实现首先确定数组大小由于矩阵是4×4的方阵阶数为n4所以需要的一维数组大小为n(1n)/2(4×5)/210由于是对称矩阵只存储上或下三角部分的元素这里以存储上三角元素为例 6、稀疏矩阵的压缩存储 稀疏矩阵中非零元素的分布与特殊矩阵相反是没有规律的。稀疏矩阵中大部分元素都为0且与非零元素的分布一样也是没有规律的稀疏矩阵的两种存储结构是三元组表数组和十字链表。 1三元组表 为了压缩存储稀疏矩阵在存储时不仅要存储矩阵中非零元素的值同时还要存储该元素所在的行与列从而组成一个三元组表行、列、值依此减少了存储空间。由于是将稀疏矩阵中的非零元素以及其对应的行、列号以三元组的形式存储在一个数组中所以经过这种压缩存储后就无法通过数组的下标直接存取矩阵的元素失去了随机存取的特性。
//以整型int为例可替换其他类型
typedef struct{int i,j; //行与列int x; //值
}Sparsematrix;例如一个稀疏矩阵A进行压缩存储 对应的三元组表如下
i行j列x值114132205 例如有一个100×90的稀疏矩阵非0元素有10个设每个整型数占2字节则用三元组表示矩阵时求所需的字节数。 解析三元组表包括行、列、值每个整型数占2字节所以10个非0元素占3×2×1060字节另外还有三元组表中行数、列数和总的非零元素个数共6个字节一共60666字节。 2十字链表 十字链表法中稀疏矩阵的行和列都用一个带头结点的链表表示从而对应着五个分量行、列、数据域、指向下方结点的指针和指向右方结点的指针其结点的结构如下
八、广义表
1、广义表 广义表也是一种特殊的线性表是由nn≥0个数据元素组成的有限序列。线性表中的数据元素只能是单个元素原子它是不可分割的而广义表中的数据元素既可以是原子也可以是一个广义表包括空表和非空表广义表通过圆括号“()”括起来通过逗号“,”隔开表中的各个数据元素。 2、广义表的表头和表尾 广义表是可以递归的一个广义表也可以是其自身的子表广义表中的第一个元素称为广义表的表头而剩余数据元素组成的表称为广义表的表尾广义表的表头和表尾可以看作通过函数head()和tail()对广义表操作。任何一个非空广义表其中表头可能是单个元素原子或广义表但表尾只可能是广义表其原因是广义表的取表尾tail()是非空广义表除去表头元素后剩余元素组成的表所以不可能是原子。 3、广义表的深度和长度 广义表的深度通过括号的层数求得而长度是广义表中所含元素的个数。【深度层数长度个数】 例如一个空广义表G()括号层数为1所以广义表的深度为1而由于是空表所以广义表的长度为0 例如一个广义表H((a,b),(c,(d,e)))括号层数为3所以广义表的深度为3最高层为(c,(d,e))逗号隔开了原子( c )和广义表( d,e )元素个数为2所以广义表的长度为2。 4、广义表表示二叉树 根据广义表中“ 数据元素既可以是原子也可以是一个广义表包括空表和非空表) ”这一点可以来表示二叉树即通过(根结点根结点的广义表)的形式来表示其中可以嵌套。例如下面是一个满二叉树 通过广义表表示该二叉树 (A , ( B , ( D , E ) ) , ( C , ( F , G ) ) ) ) 这个二叉树的解释如下 根结点是A它的左孩子是BB的左孩子是DB的右孩子是E。 根结点A的右孩子是CC的左孩子是FC的右孩子是G。
九、树与二叉树
1、树和森林 树是一种非线性结构它是树形结构含有n个有限元素的数据元素集合其中n≥0n0时为空树线性结构中的数据元素之间是“一对一”的关系而树形结构中的数据元素之间是“一对多”的关系。树n0满足两个条件一个树有且只有一个根结点其中根结点没有前驱结点除了根结点其他所有结点都只有一个前驱结点剩下的结点为m(m≥0)个互不相交的非空集合其中每个集合又可以称为一棵树即根的子树。
树中两个结点之间的路径由两个结点间所经过的序列构成路径长度是路径上所经过的边的个数而树的路径长度是指根结点到每个结点的路径长的总和。如下图是一棵树其中结点的关系是一对多 另外由mm≥0棵互不相交的树的集合称为森林如下图是一个森林 2、结点 以下图这个二叉树每个结点最多有两个结点的树为例介绍结点的相关知识。 1叶子结点叶子结点也称为终端结点它是没有子结点的结点度为0例如下图中D、E、F、G都是叶子结点 2孩子结点一个结点的后继结点称为该结点的孩子结点例如下图中A的孩子结点是B、C 3双亲结点一个结点称为其后继结点的双亲结点例如下图中B、C的双亲结点是AD、E的双亲结点是B 4兄弟结点在同一双亲结点下的孩子结点互为兄弟结点例如下图中B、C互为兄弟结点它们有共同的双亲A另外D、E互为兄弟结点它们有共同的双亲B。 3、树的性质 1树中结点的子结点孩子个数称为该结点的度而树中结点的最大度数称为树的度例如上图这个树中结点B有两个子结点D和E所以结点B的度为2结点D的度为0树的度为2。【二叉树的度小于等于2只有一个结点的二叉树的度为0】
树中结点的个数等于所有结点的度数之和加1。 例如上图的结点的个数为N22217。 另外树中结点的个数也等于总分支数加1其中总分支数1n12n23n3…mnm度为m的结点引出m条分支。 例如上图树中总分支数为6故结点个数为617。 2树中结点的最大层数为树的高度深度结点的深度是由树的根结点开始由上至下而结点的高度是由树的叶子结点开始由下至上的。
度为m的树中第i层上i≥1至多有mi-1个结点。
4、二叉树 二叉树是一种逻辑结构它是一种特殊的树与普通的树相比普通树中结点的后继结点可以是任意多个而二叉树中结点的后继结点最多只能有两个二叉树中不存在度大于2的结点即二叉树的度小于等于2。二叉树是由一个根结点以及两个不相交的非空树分别称为左子树和右子树同样左子树和右子树也是二叉树。另外二叉树是一个特殊的有序树其中结点的各子树从左到右有序左右子树的次序不能任意交换。另有两种特殊的二叉树满二叉树和完全二叉树。 满二叉树是完全二叉树的特例可以说若一棵树是满二叉树则它必是完全二叉树但不能说一个完全二叉树必是满二叉树。 5、二叉树的性质
二叉树中设度为0、1和2的结点个数分别为n0、n1和n2即结点总数Nn0n1n2另外叶子结点数等于度为2的结点数加1即n0n21。 例如下图完全二叉树中可以验证一下度为2的结点个数为4所以度为0的结点叶子结点个数为n0415。 二叉树中分支总数N-1n12n2。 例如下图完全二叉树中分支总数等于9-18或者等于度为1的结点个数加上两倍度为2的结点个数即n12n202×48。 二叉树中第i层上至多有2i-1i≥1个结点这种即为满二叉树的情况。 例如在一棵二叉树中第四层至多有24-1238个结点。 高度为h的二叉树至多有2h-1个结点另外高度为h的m叉树中至多有mh-1/m-1个结点。 例如下图是一个二叉树其高度深度为4h4即至多有24-115个结点这个二叉树并不是一个满二叉树而是一个完全二叉树。 对于n个结点可以组成N种不同的二叉树如下 N C 2 n n n 1 N \frac{C_{2n}^{n}}{n1} Nn1C2nn 例如由3个结点A、B、C构成的二叉树可以有 N C 6 3 3 1 20 / 4 5 种不同的二叉树。 N \frac{C_{6}^{3}}{31}{20/45} 种不同的二叉树。 N31C6320/45种不同的二叉树。 6、满二叉树与完全二叉树 1满二叉树与完全二叉树的定义 满二叉树与完全二叉树的特点如下表
二叉树名称特点满二叉树深度高度为h具有2h-1个结点的二叉树其中每层结点都是满的完全二叉树树中除最后一层外其余层的结点都是满的的二叉树或结点的右子树缺少连续的若干个结点 另外完全二叉树的另一种定义是若对深度为h结点数为n个的二叉树进行编号后各结点的编号与深度为h的满二叉树中相同位置结点上对应的编号均相同时则这种二叉树为完全二叉树。 2满二叉树与完全二叉树的性质
一棵高度为h的满二叉树的结点总数为2h-1若它有n个结点则含有n1/2个叶子结点含有n-1/2个分支结点其高度为hlog2(n1)。 推导过程由于是满二叉树所以度为1的结点为0即n10由于二叉树的性质n0n21以及nn0n1n2可得n2n0-1所以叶子结点n0n1/2 由于分支总数n-1n12n2且n0n21、n10所以分支总数2n2n0-1n-1/2 高度为h的满二叉树的结点数为124……2h-12h-1首项为1公比为2的等比数列即nSn[a1(1-qn)]/1-q2h-1从中解出h高度为hlog2(n1)。 由于完全二叉树的结点排法可知叶子结点尽可能地往左边排故度为1的结点个数只有一个或零个。 例如已知一棵完全二叉树的第6层有8个叶子结点求该完全二叉树的最多和最少结点数。由于第6层有叶子结点所以完全二叉树的高度可能为6或7当为6时完全二叉树拥有最少结点数由于前5层都为满二叉树即124816831839当为7时前6层都为满二叉树其中有8个结点没有左右结点即12481632(32-8)×26348111故该完全二叉树的最多和最少结点数分别为39和111。 一棵含有n个结点的完全二叉树中叶子结点个数等于n/2【n为偶数】或n1/2【n为奇数】。 例如已知一棵完全二叉树有1001个结点所以其叶子结点个数就等于10011/2501个。 例如已知一棵完全二叉树具有124个叶子结点求其最多和最少结点数。当结点数n为偶数时结点数最大124n/2解得n248n为奇数时结点数最小124n1/2解得n247故最多和最少结点数为248和247。 另一种解法是根据n0n21可知n0124n2123由于Nn0n1n2且该树为完全二叉树根据完全二叉树的性质度为1的结点个数只有一个或零个即N1241123248和N1240123247所以最多和最少结点数为248和247。 一棵树高为h的完全二叉树至少有2h-1个结点至多有2h-1个结点总结点N与高h的关系是h⌈log2(n1)⌉。即对于一棵含有n个结点的二叉树当它为完全二叉树时具有最小高度最小高度为h⌈log2(n1)⌉或⌊log2n⌋1其中 ⌈ ⌉表示向上取整取比自己大的最小整数⌊ ⌋表示向下取整取比自己小的最大整数当它为一棵单支树时具有最大高度为一个线性表即最大高度为n。 例如设一颗二叉树的结点个数为50求其最小高度我们知道当这棵树为完全二叉树时高度最小n50即h⌊log250⌋1 516所以其最小高度为6。 例如求一棵具有1025个结点的二叉树的高度首先我们知道当二叉树为单支树时此时具有最大高度即每层只有一个结点最大高度为1025另外当二叉树为完全二叉树时高度最小此时即最小高度为⌊log21025⌋110111故该二叉树的高度为11~1025。 7、平衡二叉树 平衡二叉树的特点是其中任一结点的左右子树的深度之差都不超过1如下是一个平衡二叉树 8、二叉树的存储结构 1顺序存储 二叉树的顺序存储结构通过使用一组地址连续的存储单元数组进行存储其中根结点的编号设定为1若结点的编号为i则对应存储的一维数组下标为i-1但是顺序存储结构存在浪费情况就是在最坏情况下一个高度为h的二叉树需要占据2h-1个数组存储单元非完全二叉树。 2链式存储 二叉树的链式存储结构通过链表实现一个二叉树链表结点由数据域和指针域组成除了data数据域用于存放结点的信息外每个结点含有两个指针左指针域lchild和右指针域rchild分别指向该结点的左孩子结点和右孩子结点它们用于存放该结点左/右子树的地址当左/右子树不存在其指针域为空“^”如下图 例如下面这个树的链式表示如下 对应的链式结构如下 从中可以得到一个结论
在由n个结点组成的二叉链表中含有n1个空指针域含有n-1个非空指针域。 例如上图二叉树中含有8个结点它含有819个空指针域含有8-17个非空指针域。 9、二叉树的遍历 二叉树的遍历是按某种规定的顺序来对访问树中的所有结点且每个结点仅被访问一次由于二叉树由根结点D、左子树L和右子树R组成可分为二叉树的先、中、后遍历另外还有每一层的遍历即层次遍历如下表
名称遍历顺序先序遍历根、左、右中序遍历左、根、右后序遍历左、右、根 二叉树的中序遍历序列中由“左中右”的遍历关系以及根结点可以确认二叉树的左右子树同时由二叉树的前序或后序遍历序列再确定结点中的父子关系从而结合可以唯一确定一棵二叉树。 二叉树的先、中、后序遍历都可以通过递归算法实现递归结束的条件是TNULL即当二叉树为空时遍历结束。 1二叉树的先序遍历DLR 二叉树的先序遍历中首先是根结点遍历完根结点的左子树然后再遍历完根结点的右子树依次下去至所有结点都遍历到例如下图二叉树 其先序遍历序列为ABDCE。 2二叉树的中序遍历LDR 二叉树的中序遍历中首先是遍历完根结点的左子树然后是根结点最后遍历完根结点的右子树依次下去至所有结点都遍历到通过中序遍历可以得到一个递增的有序序列。 例如一个二叉树中根据中序遍历可知中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点若它为叶子结点则先序遍历序列和中序遍历序列的最后一个结点都为该结点若不为叶子结点它还有一个左子结点则该左子结点是前序遍历序列的最后一个结点。 中序遍历序列为DBACE由于中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点所以中序遍历序列的最后一个结点为E由于该结点是叶子结点所以先序遍历序列和中序遍历序列的最后一个结点都为该结点。 先序ABDCE 中序DBACE 3二叉树的后序遍历LRD 二叉树的后序遍历中首先是遍历完根结点的左子树然后遍历完根结点的右子树最后是根结点依次下去至所有结点都遍历到也就是从二叉树的底层往上层依次遍历。 该二叉树的后序遍历序列为DBECA。 4先序、中序和后序遍历的相关性质 在二叉树的前序遍历、中序遍历和后序遍历序列中所有叶子结点的先后顺序是相同的。例如该二叉树的三种遍历分别为ABDCE、DBACE、DBECA可以看出叶子结点D和E的先后顺序总是一样的D结点永远都在E结点的前面。 若一棵二叉树为空树或只有根结点则其先序遍历序列和后序遍历序列相同若二叉树为单右支二叉树或孤立结点则其先序遍历序列和中序遍历序列相同。例如下面单右支二叉树先序遍历序列和中序遍历序列相同的都为ABC 若一棵二叉树为空树或任一结点都缺右子树的单支树则其中序遍历序列和后序遍历序列相同。例如下面二叉树其中任一结点至多只有左子树中序遍历序列和后序遍历序列相同都为DCBA 若一棵非空的二叉树只有一个叶子结点或二叉树的高度等于结点个数则其先序遍历序列和后序遍历序列相反。例如下面二叉树只有一个叶子结点其结点个数为3也等于高度h3所以其先序遍历序列和后序遍历序列相反即ABC和CBA 5二叉树的层次遍历 层次遍历中层次优先当对一层的结点都遍历完后遍历下一层按照次序对每个结点的左、右孩子进行遍历。 例如下面二叉树其层次遍历为ABCDEFG 若一棵二叉树为空树或任一结点至多只有右子树则中序遍历序列与层次遍历序列相同。层次遍历二叉树中可以通过链式队列实现首先二叉树的根结点入队然后进入循环循环条件为队列是否为空若不为空则当前队头结点出队此时该结点被访问到并将该结点的左、右孩子结点插入到队列的队尾。 10、树的存储结构 树的存储结构中反映的是一棵树中各结点之间的关系在存储中不仅存储树中每个结点的值还存储各结点之间的关系主要有三种存储结构分别是双亲表示法、孩子链表示法和孩子兄弟表示法。 1双亲表示法 双亲表示法是通过采用一维数组来存储树中的结点其中每个结点被赋予一个结构体类型包含data域和parent域分别存储结点的数据域和存储该结点双亲的数组下标。
#define MAXSIZE 100
typedef struct
{int data; //数据域int parent; //双亲位置域
}ParNode[MAXSIZE];例如下图该树通过双亲表示法进行存储规定从数组下标为0开始存储根结点下标为0同时设根结点的parent域为-1 通过双亲表示法中可以很容易地找到每个结点的双亲和祖先但是其缺点是若寻找结点的孩子结点或兄弟结点就较为麻烦需遍历整个数组。 2孩子链表表示法 将所有结点存放在一个顺序表中每个数据元素有两个域分别是该结点的数据域和存放该结点的第一个孩子的地址同时为树中每个结点都构建一个单链表它也有两个域分别是存放该孩子结点在顺序表中的数组下标和存放下一个孩子的地址。
#define MAXSIZE 100
/*顺序表定义*/
typedef struct
{int data; //数据域ChildNode *children; //第一个孩子的地址
}Head;/*单链表定义*/
typedef struct Node
{int address; //该孩子结点在顺序表中的数组下标struct Node *next; //下一个孩子的地址
}ChildNode;
Head T[MAXSIZE]; //建立顺序表头结构例如通过孩子链表表示法进行存储上树规定顺序表下标为0的位置存放根结点 通过孩子链表表示法可以很容易地找到该结点的孩子结点但是若要找到结点的双亲则较为麻烦需遍历n个结点中孩子链表指针域所指向的n个孩子链表。 3孩子兄弟表示法 孩子兄弟表示法是采用二叉链表其中包含三个域分别是数据域和两个指针即*child指向第一个孩子结点的地址、*brother指向该结点的下一个兄弟结点的地址。
typedef struct Node
{int data; //数据域struct Node *child,*brother; //第一个孩子结点的地址和下一个兄弟结点的地址
}ChildBNode;例如通过孩子兄弟表示法进行存储树 这种方法的缺点是若从当前结点查找其双亲结点较为麻烦解决方法是为每个结点增设一个parent域用于指向其父结点。 11、树的存储结构 1树转换成二叉树 ①对树中所有的兄弟结点连线【兄弟连线】 ②对树中每个结点只保留它与第一个孩子结点的连线删除其他孩子结点之间的连线【只留第一个孩子】 ③以树的根结点为轴心旋转一定的角度变成一棵二叉树。【旋转】 2二叉树还原成树 二叉树还原成树的前提是该二叉树的根结点无右子树。 ①对二叉树中每个结点若某结点的左孩子有右子树则该结点与其左孩子的右子树的右分支上结点连线 ②删除各结点的右分支连线 ③以树的根结点为轴心旋转一定的角度变成一棵树。 3森林转换成二叉树 ①与树转换成二叉树的第一步一样将该森林中每棵树转换为二叉树即各个树中所有兄弟结点之间连线【兄弟连线】 ②将所有树的根结点相连【根结点连线】 ③每个结点只保留最左边第一个孩子结点的连线删除其他孩子结点之间的连线【只留最左第一个孩子】 ④以树的根结点为轴心旋转一定的角度变成一棵二叉树。【旋转】 4二叉树还原成森林 ①对于双亲若某结点是其双亲的左孩子则将该结点的右孩子、右孩子的右孩子等等都与该结点的双亲结点连接 ②删除二叉树中所有双亲结点与其右孩子结点的连线 ③整理所得到的树和森林。 具体例题可看之前的文章 数据结构学习笔记——树的存储结构以及树、森林与二叉树之间的转换 12、树与森林的遍历 1树的遍历 树的遍历主要分为两种先序遍历和后序遍历和二叉树的遍历规则一样例如下图该树 该树的先序遍历序列为ABDEHMI后序遍历序列为DBHMEIA。 另外也有层次遍历该树的层次遍历序列为ABEIDHM。 将上图中的树转为二叉树后如下 我们知道该二叉树的先序遍历序列为ABDEHMI中序遍历序列为DBHMEIA后序遍历序列为DMHIEBA可以得出
树的先序遍历序列为转换成二叉树后的先序遍历序列树的后序遍历序列为转换成二叉树后的中序遍历序列。
2森林的遍历 森林的遍历也是主要分为两种 先序遍历和后序遍历和二叉树的遍历规则一样例如下图该森林 对其进行先序遍历和后序遍历得到的序列分别为ABDEHMICFJKGL、DBHMEIAJFKCLG。 将上图中的森林转为二叉树后如下 对该二叉树进行先序遍历、中序遍历和后序遍历得到的遍历序列为ABDEHMICFJKGL、DBHMEIAJFKCLG、DMHIEBJKFLGCA。 不难看出可以得到以下结论
森林的先序遍历序列为转换成二叉树后的先序遍历序列森林的后序遍历序列为转换成二叉树后的中序遍历序列。
总结以上结论
对应关系树森林二叉树-先序遍历先序遍历先序遍历-后序遍历中序遍历中序遍历 只需记住 树、森林、二叉树的先序遍历序列都是相同的。 森林和二叉树的中序遍历序列对应树的后序遍历。 13、线索二叉树 1线索二叉树的定义 由于在含有n个结点的二叉树的链式存储结构中有n1个空指针对于叶子结点它有两个空指针对于度为1的结点只有一个子结点它只有一个空指针。将这些空指针利用起来例如可以让其存放指向该结点的前驱或后继从而使遍历二叉树更加简便加快查找结点的前驱或后继的速度即线索二叉树由于线索二叉树是加上线索的链表结构是计算机内部的一种存储结构是一种物理结构。
另外由于有n个结点即有链域指针2n个除了根结点以外每个结点都被一个指针所指向剩余的链域建立线索即n个结点的线索二叉树含义的线索数为2n-(n-1)n1个。 #mermaid-svg-vpVnueECL9t9CT8D {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-vpVnueECL9t9CT8D .error-icon{fill:#552222;}#mermaid-svg-vpVnueECL9t9CT8D .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-vpVnueECL9t9CT8D .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-vpVnueECL9t9CT8D .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-vpVnueECL9t9CT8D .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-vpVnueECL9t9CT8D .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-vpVnueECL9t9CT8D .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-vpVnueECL9t9CT8D .marker{fill:#333333;stroke:#333333;}#mermaid-svg-vpVnueECL9t9CT8D .marker.cross{stroke:#333333;}#mermaid-svg-vpVnueECL9t9CT8D svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-vpVnueECL9t9CT8D .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-vpVnueECL9t9CT8D .cluster-label text{fill:#333;}#mermaid-svg-vpVnueECL9t9CT8D .cluster-label span{color:#333;}#mermaid-svg-vpVnueECL9t9CT8D .label text,#mermaid-svg-vpVnueECL9t9CT8D span{fill:#333;color:#333;}#mermaid-svg-vpVnueECL9t9CT8D .node rect,#mermaid-svg-vpVnueECL9t9CT8D .node circle,#mermaid-svg-vpVnueECL9t9CT8D .node ellipse,#mermaid-svg-vpVnueECL9t9CT8D .node polygon,#mermaid-svg-vpVnueECL9t9CT8D .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-vpVnueECL9t9CT8D .node .label{text-align:center;}#mermaid-svg-vpVnueECL9t9CT8D .node.clickable{cursor:pointer;}#mermaid-svg-vpVnueECL9t9CT8D .arrowheadPath{fill:#333333;}#mermaid-svg-vpVnueECL9t9CT8D .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-vpVnueECL9t9CT8D .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-vpVnueECL9t9CT8D .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-vpVnueECL9t9CT8D .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-vpVnueECL9t9CT8D .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-vpVnueECL9t9CT8D .cluster text{fill:#333;}#mermaid-svg-vpVnueECL9t9CT8D .cluster span{color:#333;}#mermaid-svg-vpVnueECL9t9CT8D div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-vpVnueECL9t9CT8D :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 线索二叉树 先序线索二叉树 中序线索二叉树 后序线索二叉树 线索二叉树也分为前序线索二叉树、中序线索二叉树以及后序线索二叉树即它们都是对二叉树中的所有结点的空指针进行某种遍历方式加线索指向结点前驱和后继的指针称为线索。
2画出二叉树的先/中/后序线索二叉树 简单的来说若要画出二叉树的先/中/后序线索二叉树只需经过以下几个步骤 ①首先求出要画的相应线索二叉树的先/中/后序遍历序列 ②画线索针对二叉树中缺少左、右孩子的结点 若该结点无左孩子则线索指向相应线索二叉树的先/中/后序遍历序列的前驱若无前驱则指向NULL【无左孩子转前驱】 若该结点无右孩子则线索指向相应线索二叉树的先/中/后序遍历序列的后继若无后继则指向NULL。【无右孩子转后继】 14、哈夫曼树 1路径和路径长度 在树中一个结点和另一个结点之间的分支即为这两个结点之间的路径路径长度即为树中路径上的分支数目即路径上所经过的边的个数。树的路径长度等于根结点到树中每个结点的路径长度之和。 2权值 为树中每个叶子结点度为1的结点赋予一个数值则该值称为叶子结点的权值简称为权。 3带权路径长度 叶子结点的权值与树的根结点到该叶子结点之间的路径长度的乘积称为叶子结点的带权路径长度。 例如上图二叉树中叶子结点D的权值为4根结点A到结点D的分支数目为2所以该叶子结点的带权路径长度为4×28。 树中所有叶子结点的权值乘以该结点的路径长度之和即为树的带权路径长度WPL。 例如上图二叉树中该二叉树的带权路径长度为 WPL4×22×23×23×224。 4哈夫曼树 哈夫曼二叉树是哈夫曼n叉树的一种以下都以哈夫曼二叉树为例。 哈夫曼树是一棵最优二叉树给定n个带有权值的叶子结点构造一棵二叉树使构造的二叉树的带权路径长度最小即为最优二叉树也称为哈夫曼树。其中两个权值最小的结点一定是兄弟结点且任意一非叶子结点的权值不小于其下一层的任意一结点的权值。 哈夫曼树既不是满二叉树也不是完全二叉树只是一棵二叉树。另外哈夫曼树中只有度为0和2的结点不存在度为1的结点。 5哈夫曼树的构建步骤 基于给定的n个带权值的结点构成的初始森林首先选出两棵权值最小的树作为左右子树相加得出的权值之和是一个新根结点的权值然后将新结点插入到森林中同时将左右子树从森林中删除重复选取直到森林中只有一棵树时即为哈夫曼树。 6哈夫曼编码 哈夫曼编码是一种可变长度编码且是无前缀编码它根据字符出现的概率来对每个字符设定二进制编码规定一个编码不能是其它编码的前缀主要应用在数据压缩、加密解密等场景。 15、二叉排序树 二叉排序树也称为二叉查找树或二叉搜索树其中各结点值的大小关系是左子树根结点右子树且左、右子树也是一棵二叉排序树满足其条件若对该树进行中序遍历可得到一个递增的序列。
十、图
图的知识点由于过多……这边不放上了可以去我的系列文章中查看 数据结构
