图论(Graph Theory)一、介绍图是用来对对象之间的成对关系建模的数学结构，由”节点”或”顶点”(Vertex）以及连接这些顶点的”边”（Edge）组成。值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。二、图的分类图分为：无向图和有向图(无向图是有向图的特殊形式)无
......
389
0
0
2022-04-17
并查集的路径压缩一、介绍并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。通俗的说就是把find过程中“查找节
......
192
0
0
2022-04-17
并查集基于rank的优化一、介绍背景前面将到并查集基于size的优化，其实仔细想想，还是有可以优化的地方；size[i]是指以i为根节点树的节点数；是将节点数量多的树的根节点向节点数好的树的根节点连接，在一般情况下是得到了优化，但是这里就存在问题了，当出现：节点数多的树它的高度非常高的时候，size的优化方式就不太高效了。rankrank[i]:是用来记录以
......
285
0
0
2022-04-17
并查集基于size的优化一、介绍及逻辑介绍在上一小节我们使用指针的方法将每一个元素都看作是一个节点，并且是节点指向另一个节点(包括自己)，在这一小节中我们将在此基础上进行优化。先来介绍一下什么是”size”size : size[i] 是指用来记录以i为根节点的树所包含的节点个数，本质是一个数组逻辑先来看看下面的图片：现在需要将4，2连接起来，该怎么连？方法
......
192
0
0
2022-04-16
并查集的另一种实现思路(优化)一、介绍在并查集的Union( ) 中使用指针，将每一个元素看作是一个节点，并将每一个节点都指向一个节点(可以是其他节点或节点本身)即Quick Union；使用这种方法在后续可以更好的对并查集进行优化。二、 Union的表示方法及逻辑在Quick Find下的union时间复杂度为( O(n) )将每一个元素看作是一个节点，如
......
182
0
0
2022-04-16
并查集基础一、概念及其介绍并查集是一种树型结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。对于并查集主要支持两个操作：并{ union(p,q) }查找{ find(p) }来回答一个问题：连接{ inConnected
......
250
0
0
2022-04-16
二分搜索树特性及完整源代码一.特性1.顺序性二分搜索树可以当做查找表的一种实现。我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天花板、rank（排名第几的元素）、select（排名第n的元素是谁）这些都是二分搜索树顺序
......
208
0
0
2022-04-16
二分搜索树节点的删除(remove)在这一小节中，我们会介绍二分搜索树中如何查找最小最大值、最小最大值的删除、删除任意节点（删除只有左孩子的节点、删除只有右孩子的节点和删除左右孩子都存在的节点）；下面我们一一讲解：一. 查找最小最大值及其删除查找最小最大值其实很简单，首先我们想一想二分搜索树的定义就会明白，最小值在以跟节点的左孩子节点的左孩子节点………上，看
......
275
0
0
2022-04-16
二分搜索树的遍历一.遍历的分类二分搜索树遍历分为两大类，深度优先遍历和层序遍历。深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk），分别为：1、前序遍历：先访问当前节点，再依次递归访问左右子树。2、中序遍历：先递归访问左子树，再访问自身，再
......
266
0
0
2022-04-15
二分搜索树之查找(Search)-包含(Contain)一. 查找(Search)1. 逻辑前面我们了解了对节点的插入，其实在二分搜索树中对相应节点的查找的过程中也有同样的逻辑下面我们来看看具体的查找(Search):我们在树中查找键值为42的节点将42和41比较，42 > 41,根据二分搜索树的定义可知，我们应该继续往41节点的右孩子查找：此时再将4
......
204
0
0
2022-04-15
二分搜索树节点的插入一. 定义二分搜索树首先定义一颗二分搜索树，C++代码如下：#include <iostream>
#include <queue>
#include <cassert>
using namespace std;
//套用模板函数
template <typename Key, ty
......
220
0
0
2022-04-15
二分搜索树(Binary Search Tree)一.概念及其介绍概念二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件：每个节点的键值大于左孩子每个节点的键值小于右孩子以左右孩子为根的子数仍然为二分搜索树优点可以高效的查找数据，还可以高效的插入，删除，及动态维护数据二分搜索
......
238
0
0
2022-04-15
二分查找法一.介绍二分查找法是一种在计算机中快速查找相应内容的算法，它基于有序数组将其查找，在计算机中广泛使用，已经成为计算机中必不可少的算法，二分查找: 又称为 折半查找,二分查找,适合对已经排序好的数据集合进行查找,时间复杂度O(log2n),效率高。二.逻辑假设有一升序的数据集合{0, 1, 2, 3, 4, 5, 6, 7, 8}先找出升序集合中最中
......
227
0
0
2022-04-15
昨天我和一些人在闲聊的时候，他们说他们并不真正了解栈是如何工作的，而且也不知道如何去查看栈空间。这是一个快速教程，介绍如何使用 GDB 查看 C 程序的栈空间。我认为这对于 Rust 程序来说也是相似的。但我这里仍然使用 C 语言，因为我发现用它更简单，而且用 C 语言也更容易写出错误的程序。我们的测试程序这里是一个简单的 C 程序，声明了一些变量，从标准输
......
309
0
0
2022-04-14
一旦你理解了一般原则，C++ 类成员函数指针不再那么令人生畏。如果你正在寻找性能、复杂性或许多可能的解决方法来解决问题，那么在涉及到极端的情况下，C++ 总是一个很好的选择。当然，功能通常伴随着复杂性，但是一些 C++ 的特性几乎难以分辨。根据我的观点，C++ 的 类成员函数指针 也许是我接触过的最复杂的表达式，但是我会先从一些
......
274
0
0
2022-04-13