邓俊辉专题

数据结构（邓俊辉）学习笔记】排序 5——选取：通用算法

文章目录 1. 尝试2. quickSelect3.linearSelect：算法4. linearSelect：性能分析5. linearSelect：性能分析B6. linearSelect：性能分析C 1. 尝试在讨论过众数以及特殊情况下中位数的计算方法以后，接下来针对一般性的选取问题，介绍优化的通用算法。既然选取问题的查找目标就是在整个数据集中按大小次序秩为 k

数据结构（邓俊辉）学习笔记】串 12——BM_BC算法：性能分析

文章目录 1. 最好情况2. 最坏情况 1. 最好情况以下，就让我们从最好情况的角度，来考察坏字符策略的性能。实际上，在最好情况下的性能之好，要远远超过我们的想象。具体来说，此时的时间成本可以度量为 O(n/m)。没错，除法。你能构造出这样的一个具体实例吗？这就是一个：可以看到，模式串完全由0组成，而文本串呢？则由与模式串等长的若干个片段依次拼接而成。在每一个片段中，末

数据结构（邓俊辉）学习笔记】串 09——BM_BC算法：以终为始

文章目录 1. 不对称性2. 善待教训3.前轻后重4.以终为始 1. 不对称性上一节所介绍的 KMP 算法计算时间，在最坏情况下也可以保证不超过线性。这的确是一个好消息。然而，倘若我们因此就停下继续优化的脚步，那就大错特错了。实际上，串匹配问题与一般的搜索问题的确有着本质的区别。在我们此前所讨论的所有搜索算法中，每次比对都是一种一对一的模式，也就是一个目标与另一个候选者

数据结构（邓俊辉）学习笔记】串 07——KMP算法：分摊分析

文章目录 1.失之粗糙2.精准估计 1.失之粗糙以下，就来对 KMP 算法的性能做一分析。我们知道 KMP 算法的计算过程可以根据对齐位置相应的分为若干个阶段，然而每一个阶段所对应的计算量是有很大区别的。很快就会看到，如果只是简单地从最坏的角度来进行估计，我们将无法准确地来评估这种算法，而实际上真正有效的方法是，放眼整个计算过程，将整体的计算成本分摊到每一个阶段。没错，分摊

数据结构（邓俊辉）学习笔记】串 04——KMP算法：查询表

文章目录 1.制表备查2.主算法3.实例 1.制表备查接下来我们来看看。KMP 算法究竟如何兑现我们刚才所提及的记忆力以及预知力，我们将会看到这种方法非常的便捷与高效，本质上讲，它无非就是构造了一张查询表。回到我们刚才的问题，在当前这一轮比对，首次失败于 T[i] 与 P[j] 之后，我们应当如何地向后滑动模式串，从而等效地以一个新的 P[j] 来与刚才的 T[i] 对

数据结构（邓俊辉）学习笔记】优先级队列 09——左式堆：合并算法

文章目录 1. LeftHeap模板类2. 算法3. 实现4. 实例 1. LeftHeap模板类接下来这节，来讨论左式堆的合并算法。再给出具体算法之前，首先要给出左式堆模板类的定义。比如这就是一种可能的实现方式，可以看到，我们这里再次利用了 C++的多重继承，只不过与完全二叉堆不同，既然左式堆已经不再满足结构性，所有元素在物理上也不可能继续保持紧密的排列，因此继续从向量

数据结构（邓俊辉）学习笔记】优先级队列 08——左式堆：结构

文章目录 1. 第一印象2. 堆之合并3. 奇中求正4. NPL5. 左倾性6. 左展右敛 1. 第一印象在学习过常规的完全二叉堆之后，我们再来学习优先级队列的另一变种，也就是左式堆。所谓的左式堆，也就是在拓扑形态上更加倾向于向左侧倾斜的一种堆，比如这就是一个左式堆由生到长，直至灭亡的整个生命过程。可以看到，相对于常规的完全二叉堆，左式堆的确显得有些别致。那么，为什

【数据结构（邓俊辉）学习笔记】二叉搜索树01——概述

文章目录 1. 纵览2. 寻关键码访问3. 有序性4.单调性5. 接口 1. 纵览二叉搜索树将标志着对数据结构的理解进入到一个更深的层次。回顾向量和列表两类基本数据结构，虽然它们已经可以解决相当多的问题，然而对于进一步的算法设计要求来说，它们都显得力不从心。也正因为此，长久以来最求的目标就是如何将二者的优势结合起来。其实在二叉树上已经做了这方面的尝试，通过对一维列表

【数据结构（邓俊辉）学习笔记】图07——最短路径

文章目录 0. 概述1. 问题2. 最短路径2.1 最短路径树2.1.1 单调性2.1.2 歧义性2.1. 3 无环性 2.2 Dijkstra 算法2.2.1 贪心迭代2.2.2 实现2.2.3 实例2.2.4 复杂度 0. 概述学习下最短路径和Dijistra算法 1. 问题给定带权网络G = (V, E)，以及源点（source）s ∈ V，对于所有的其它顶点

【数据结构（邓俊辉）学习笔记】图04——双连通域分解

文章目录 0. 概述1 关节点与双连通域2 蛮力算法3 可行算法4 实现5 示例6 复杂度 0. 概述学习下双连通域分解，这里略微有一点点难，这个算是DFS算法的非常非常经典的应用，解决的问题也非常非常有用。 1 关节点与双连通域连通性很好理解，两个点在图中只要有一条路径，不管是无向的还是有向的，只要互相可达，就说他们是连通的。但有的时候会要求更严些，不仅要保证自己和某些

【数据结构（邓俊辉）学习笔记】图05——优先级搜索

文章目录 0. 概述1. BAG2. ADT 0. 概述学习下优先级搜索 1. BAG 优先级搜索是非常广义的，概况来说，无论DFS 还是BFS从逻辑上来都属于这种搜索。回忆下什么叫搜索或者遍历，对于像图这种数据结构里的元素逐一的没有重复的也没有遗漏的对它们进行访问，在不同的应用问题里，这种访问其实最最重要的是次序，怎么确定次序？ ~ 以前在初级的数据结构，比

【数据结构（邓俊辉）学习笔记】图06——最小支撑树

文章目录 0. 概述1. 支撑树2. 最小支撑树3. 歧义性4. 蛮力算法5. Prim算法5.1 割与极短跨越边5.2 贪心迭代5.3 实例5.4 实现5.5 复杂度 0. 概述学习下最小支撑树和prim算法。 1. 支撑树最小的连通图是树。连通图G的某一无环连通子图T若覆盖G中所有的顶点，则称作G的一棵支撑树或生成树（spanning tree）。就保留原

【数据结构（邓俊辉）学习笔记】图03——拓扑排序

文章目录 0. 概述1. 零入度算法1. 1 拓扑排序1. 2 算法 2. 零出度算法2.1 算法2.2 实现2.3. 复杂度 0. 概述学习下拓扑排序 1. 零入度算法 1. 1 拓扑排序首先理解下拓扑排序其实老师经常干这事，如编讲义，将已经知道的知识点串起来变成讲课序列。那怎么串起来呢？将知识点列出，将它们之间的相互关系描述下。要讲priority que

【数据结构（邓俊辉）学习笔记】图01——图的表示与实现

文章目录 1. 概述1.1 邻接 + 关联1.2 无向 + 有向1.3 路径 + 环路 2. 邻接矩阵2.1 接口2.2 邻接矩阵 + 关联矩阵2.3 实例2.4 顶点和边2.5 邻接矩阵2.6 顶点静态操作2.7 边操作2.7 顶点动态操作2.8 综合评价 1. 概述 1.1 邻接 + 关联相对于此前的线性以及半线性结构，图结构对其中元素的限定更少，因此反过来，它描述应用

【数据结构（邓俊辉）学习笔记】二叉树01——二叉树表示与实现

文章目录 0.概述1.树1.1 应用1.2 有根树1.3 有序树1.4 路径+环路1.5 深度 + 层。1.6 树的表示 2. 二叉树的概述3 二叉树实现3.1 二叉树节点3.2 二叉树节点操作接口3.3 二叉树的实现 0.概述介绍下二叉树的表示与实现。 1.树 1.1 应用后缀表达式。相对于线性结构O（n），树结构中元素的查找、插入、删除操作几乎提高了一个线性

【数据结构（邓俊辉）学习笔记】栈与队列01——栈接口与应用

文章目录 0. 概述1. 操作与接口2. 操作实例3. 实现4. 栈与递归5. 应用5.1 逆序输出5.1.1 进制转换5.1.1.1 思路5.1.1.2 算法实现 5.2 递归嵌套5.2.1 栈混洗5.2.1.1 混洗5.2.1.2 计数5.2.1.3 甄别 5.2.2 括号匹配5.2.2.1 构思5.2.2.2 实现5.2.2.3 实例 5.3 延迟缓冲5.3.1 中缀表达式5.3.

【数据结构（邓俊辉）学习笔记】列表03——有序列表

文章目录 0. 概述1. 唯一化2. 查找2.1 实现2.2 顺序查找2.3 复杂度 0. 概述介绍下有序列表。若列表中所有节点的逻辑次序与其大小次序完全一致，则称作有序列表（sorted list）。为保证节点之间可以定义次序，依然假定元素类型T直接支持大小比较，或已重载相关操作符。 1. 唯一化算法思想：有序列表中的雷同节点也必然（在逻辑上）彼此紧邻。利用这一

【数据结构（邓俊辉）学习笔记】列表01——从向量到列表

文章目录 0.概述1. 从向量到列表1.1 从静态到动态1.2 从向量到列表1.3 从秩到位置1.4 列表 2. 接口2.1 列表节点2.1.1 ADT接口2.1.2 ListNode模板类 2.2 列表2.2.1 ADT接口2.2.2 List模板类 0.概述学习了向量，再介绍下列表。先介绍下列表里的概念和语义，这个对理解列表接口还是比较重要的。 1. 从向量到列表

【数据结构（邓俊辉）学习笔记】向量05——排序器

文章目录 0. 概述1.统一入口2. 起泡排序2.1 起泡排序（基础版）2.1.1 算法分析2.1.2 算法实现2.1.3 重复元素与稳定性2.1.4 复杂度分析 3. 归并排序3.1 有序向量的二路归并3.2 分治策略3.3 实例3.4 二路归并接口的实现3.5 归并时间3.6 排序时间 4.综合评价 0. 概述介绍下有序向量的排序器，包括起泡排序和归并排序。 1.统一入

【数据结构（邓俊辉）学习笔记】向量03——常规向量

文章目录 0.概述1.元素访问2.置乱器3.判等器与比较器4.无序查找4.1 判等器4.2 顺序查找4.3 实现4.4 复杂度 5. 插入5.1 算法实现5.2 复杂度分析 6. 删除6.1 区间删除6.2 单元删除6.3 复杂度 7. 唯一化7.1 实现7.2 正确性7.3 复杂度 8. 遍历8.1 实现8.2 复杂度 9. 总结 0.概述记录向量的元素访问、插入、区间删除、

【数据结构（邓俊辉）学习笔记】绪论03——递归分析

文章目录意图目标1. 线性递归数组求和线性递归减而治之 2. 递归分析递归跟踪递推方程典型递推方程 3. 递归模式多递归基多向递归 4. 递归消除空间成本尾递归及其消除 5. 二分递归分而治之数组求和 6 . 效率7. 算法设计优化总结前n项计算算法意图数据结构中经常用到递归，递归分析和优化也是必要的，记录下递归分析目标理解不同递归形式（线性递归、二分递归和多分支

邓俊辉 c++数据结构第二章向量

数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为：线性结构、线性结构和非线性结构。线性结构根据逻辑次序和物理次序的关系，分为向量和列表。向量的逻辑次序和物理位置是对应的；列表的逻辑次序和物理位置无关，逻辑上相邻的向量物理位置不一定相邻。本章重点是向量的抽象类型接口规范和对应的算法，尤其是高

邓俊辉数据结构第一章:绪论笔记(未完待续)

第一章：绪论计算机科学的学习重心是：具体地深入思考与分析获得对问题本质的透彻理解，按照长期积淀的框架与模式设计出符合问题内在规律的算法。选用、定制、改进足以支撑算法高效实现的数据结构，并在真实的应用环境中充分测试、调校和改进，构成了计算机高效求解实际问题的典型流程和不二法门。每一位有志