2021dragon的博客

文章目录图图的基本概念图的存储结构邻接矩阵邻接表图的遍历广度优先遍历深度优先遍历最小生成树Kruskal算法Prim算法最短路径单源最短路径-Dijkstra算法单源最短路径-Bellman-Ford算法多源最短路径-Floyd-Warshall算法图图的基本概念图的基本概念图是由顶点集合和边的集合组成的一种数据结构，记作 G=(V,E)G=(V, E)G=(V,E) 。有向图和无向图：在有向图中，顶点对 <x,y><x, y><x,y> 是有序的，顶点

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集通常用森林来表示，森林中的每棵树表示一个集合，树中的结点对应一个元素。虽然利用其他数据结构也能完成不相交集合的合并及查询，但在数据量极大的情况下，其耗费的时间和空间也是极大的。

文章目录什么是格雷码？二进制码转换成格雷码格雷码转换成二进制码什么是格雷码？二进制码转换成格雷码格雷码转换成二进制码

文章目录前言一、难度等级：⭐二、难度等级：⭐⭐三、难度等级：⭐⭐⭐⭐四、难度等级：⭐⭐⭐前言  dragon迄今为止已经遇到了四道名为《只出现一次的数字》的题目了，现决定对这四道题目进行总结。假设难度最高为五星，下面我对这四道题目进行了难度评定（个人认为）。ps：如果博友们还遇到了其他《只出现一次的数字》的题目，欢迎在评论区进行分享。一、难度等级：⭐   给定一个整数数组numsnumsnums，除了某个元素只出现一次以外，其余元素均出现两次。找出那个只出现一次的元素。  当两个数进行异或

文章目录前言一、大数加法1. 基本思想2. 代码实现二、大数减法1. 基本思想2. 代码实现三、大数乘法1. 基本思想2. 代码实现四、大数除法1. 基本思想2. 代码实现前言一、大数加法1. 基本思想2. 代码实现二、大数减法1. 基本思想2. 代码实现三、大数乘法1. 基本思想2. 代码实现四、大数除法1. 基本思想2. 代码实现...

文章目录哈希概念哈希冲突哈希函数哈希冲突解决闭散列开散列哈希概念顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)O(N)O(N)，平衡树中查找的时间复杂度为树的高度O(logN)O(logN)O(logN)。而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为O(1)O(1)O(1)。如果构造一种存储结构，该结构

文章目录插入排序插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序并归排序并归排序插入排序插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序并归排序并归排序...

文章目录哈夫曼树的基本概念哈夫曼树的构建构建思路代码实现哈夫曼编码的生成编码生成思路代码实现完整代码展示以及代码测试哈夫曼树的基本概念在认识哈夫曼树之前，你必须知道以下几个基本术语：1、什么是路径？ 给定N个权值作为N个结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。哈夫曼树的构建构建思路代码实现哈夫曼编码的生成编码生成思路代码实现完整代码展示以及代码测试...

文章目录二叉树的深度优先遍历前序遍历中序遍历后序遍历二叉树的广度优先遍历层序遍历结点的个数叶子结点的个数第k层结点的个数值为x的结点树的最大深度判断二叉树是否是完全二叉树判断二叉树是否是单值二叉树判断二叉树是否是对称二叉树判断二叉树是否是平衡二叉树判断二叉树是否是另一棵二叉树的子树判断两棵二叉树是否相同翻转二叉树二叉树的销毁二叉树的深度遍历（接口型题目）前序遍历中序遍历后序遍历typedef char BTDataType;//结点中存储的元素类型（以char为例）typedef struct BTN

红黑树（C++实现）

AVL树（C++实现）

二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历

给定一个二叉树，找到该树中两个指定结点的最近公共祖先。公共最近祖先的定义为：对于有根树T的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大。（一个结点也可以是它自己的祖先）。示例： 输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4 输出：5思路：代码如下：...

文章目录二叉搜索树的概念二叉搜索树的实现二叉搜索树的应用二叉搜索树的性能分析二叉搜索树的概念二叉搜索树的实现二叉搜索树的应用二叉搜索树的性能分析

判断链表是否有环（龟兔赛跑）题目描述：给定一个链表，判断链表中是否有环。思路： 可以明确的是：若一个链表带环，那么用指针一直顺着链表遍历，最终会回到某个地方。 我们可以定义两个指针（快慢指针），两个指针均从表头开始同时遍历链表，快指针一次走两步，慢指针一次走一步。如果链表带环，那么快慢指针一定会相遇，否则快指针会先遍历完链表（遇到NULL）。 若是你不明白为什么链表带环，快慢指针就一定会相遇，那么你可以想想龟兔赛跑：代码：struct ListNode { int val; struc

TopK问题 输入数组arr，找出其中最大的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最大的4个数字是5、6、7、8。示例一： 输入：arr = [3,2,1], k = 2 输出：[3,2]或者[2,3]示例二： 输入：arr = [0,1,2,1], k = 1 输出：[2]境界一...

文章目录堆的介绍堆的概念堆的结构堆的实现初始化堆堆的向下调整算法销毁堆打印堆堆的插头堆的删除堆的向上调整算法获取堆顶的数据获取堆的数据个数堆的判空堆的介绍堆的概念堆：如果有一个关键码的集合K={k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki<=k2i+1且ki<=k2i+2（或满足ki>=k2i+1且ki>=k2i+2），其中i=0,1,2,…，则称该集合为堆。小堆：将根结点最小的堆叫做小堆，也叫最小堆或小根堆。大

树的概念及结构树的概念 树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做“树”，是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。树的特点： 有一个特殊的结点，称为根结点，根结点没有前驱结点。 除根结点外，其余结点被分成M(M>0)互不相交的集合T1,T2…Tm，其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树。 每棵子树的根结点有且仅有一个前驱，可以有0个或多个后继。 因此，树是递归定义的。树

文章目录创建结点类型打印多项式尾插选择排序多项式相加代码总览 + 结果展示创建结点类型我们用链表存储一个多项式，那么该链表的每一个结点就代表多项式的某一项。所以我们的每一个结点必须包含三个信息：多项式的系数、多项式的指数以及指向下一个结点的指针。typedef int SLTDataType;//指数、系数类型typedef struct SListNode{ SLTDataType coef;//系数 SLTDataType expon;//指数 struct SListNode* ne

题目一：括号匹配问题给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。（题目来源）题目二：用队列实现栈题目三：用栈实现队列题目四：设计循环队列...

文章目录队列的介绍队列的概念队列的结构生活中队列的运用实例队列的实现初始化队列销毁队列队尾入队列队头出队列获取队列头部元素获取队列尾部元素检测队列是否为空获取队列中有效元素个数队列的介绍队列的概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFO（First In First Out）的原则。入队列：队列的插入操作叫做入队列，进行插入操作的一端称为队尾。出队列：队列的删除操作叫做出队列，进行删除操作的一端称为队头。队列的结构生活中队列的运用实例

文章目录栈的介绍栈的概念栈的结构栈的实现初始化栈销毁栈入栈出栈获取栈顶元素检测栈是否为空获取栈中有效元素个数栈的介绍栈的概念栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈 / 压栈 / 入栈。（入数据在栈顶）出栈：栈的删除操作叫做出栈。（出数据也在栈顶）栈的结构栈的实现初始化栈首先，我们需要用结构体创建一个栈，

文章目录题目描述思路代码实现题目描述编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。思路代码实现

文章目录题目描述思路代码实现题目描述对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。（题目来源）思路我们需要找到传入链表的中间结点，并将中间结点及其后面结点进行反转，然后再将原链表的前半部分与反转后的后半部分进行比较，若相同，则该链表是回文结构，否则，不是回文结构。1.找到链表的中间结点。2.反转中间结点及其后面的结点。3.比较链表的前

文章目录题目描述思路代码实现题目描述现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。（题目来源）思路创建两个链表，遍历一遍传入的链表，将值大于x的结点和值小于x的结点依次尾插到两个链表中，最后再将这两个链表链接起来，并返回第一个结点的位置即可。1.把小于x的结点尾插到less链表，把大于x的结点尾插到greater链表。2.将less链表与greater链表链接起来。

文章目录题目描述思路代码实现题目描述将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。（题目来源）思路该题的思路比较简单，我们只需创建一个头结点，然后从两个链表的表头开始依次比较传入的两个链表的结点的大小，并将两个链表中较小的结点尾插到新链表的后面即可。完成一次尾插后，接着比较未尾插的结点，并将较小的结点继续尾插到新链表后面。直到最后两个链表的结点都被尾插到新链表的后面。注意两点：1.在尾插过程中，若某一链表已被遍历完毕，则直接将另一

文章目录题目描述思路代码实现题目描述输入一个链表，输出该链表中倒数第k个结点。（题目来源）思路代码实现

文章目录题目描述思路代码实现题目描述给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。（题目来源）思路代码实现

文章目录题目描述思路一代码实现思路二代码实现题目描述反转一个单链表。（题目来源）思路一其实，反转一个单向链表，我们可以看成是将链表中的每个结点的指向反向（即从后一个结点指向前一个结点）。我们在考虑情况的时候，还是可以先考虑一般情况，再考虑极端情况。一、一般情况要使两个结点之间的指针指向反转，看似用两个变量足矣，直接让后一个结点指向前一个结点。但是仔细思考后发现并没有那么简单，我们如果直接让后一个结点指向前一个结点，那么后一个结点所指向的再后面一个结点的位置就无从知晓了。所以，我们还得定

文章目录题目描述思路代码实现题目描述给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。（题目来源）思路要移除链表中值为val的结点，我们肯定是要将链表遍历一遍，关键是我们在遍历的过程中应该如何操作。我们考虑问题的时候，可以先考虑比较常见的情况，再考虑特殊情况。一、考虑常见情况要移除某一结点，也就是让该结点的前一个结点指向待移除结点的后一个结点，然后将待移除结点释放即可。我们可以定义3个指针变量：pre

文章目录前言前言

文章目录链表介绍初始化链表打印单链表增加数据单链表的头插单链表的尾插删除数据单链表的头删单链表的尾删链表介绍链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。实际中，链表的结构多种多样：1、带头，不带头。2、单向，双向。3、循环，非循环。通过以上的这些情况组合起来，就有八种

文章目录算法效率大O的渐进表示法时间复杂度空间复杂度算法效率算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。这就是为什么我们大多时候听到的是时间复杂度，而很少听到空

文章目录初始化顺序表销毁顺序表打印顺序表增加头插尾插删除查找修改初始化顺序表销毁顺序表打印顺序表增加头插尾插删除查找修改

文章目录前言创建单项链表遍历单项链表测试代码正确性前言链表这个词想必大家都听说过，链表是一种常见而重要的基础数据结构，也是实现复杂数据结构的重要手段。它不按照线性的顺序存储数据，而是由若干个同一结构类型的“结点”依次串联而成的，即每一个结点里保存着下一个结点的地址。链表有很多种不同的类型：单向链表、双向链表以及循环链表。接下来我们来看看如何创建以及如何遍历单项链表。创建单项链表我们知道链表是由多个结点组成，所以要想创建一个链表，首先要创建一个结点。一个结点存储的内容可以分为两部分：数据域，指针域。

文章目录前言基本思路代码总览举例分析前言在单向链表的创建与遍历中，我们知道了如何创建并且遍历单向链表。那么，如果要将一个链表进行逆转（将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素，以此类推），又该如何实现呢？说到这里，有些博友可能会想到：创建一个临时变量temp，并创建两个指针P1，P2，P1指向链表开头，P2指向链表末尾，然后通过temp变量将P1和P2指向的结点的数据域进行交换，然后将P1向后移，P2向前移，继续交换数据域，直到全部交换。这样必然是可行的，但我们这次的要求是：不