数据结构
未读1. 霍夫曼树霍夫曼树（Huffman Tree），又称最优二叉树，它是一种在给定一组带有特定权值的叶子节点后，构建出的带权路径长度（Weighted Path Length, WPL）达到最小的二叉树。
基于下表我们可以构建出这样一棵霍夫曼树：
数据
权值（频率）
A
10
B
15
C
12
D
3
E
4
F
13
G
1
在学习霍夫曼树的过程中，有几个关键概念需要大家深入理解。接下来，我将为大家逐一详细介绍。
1.1 重要概念解析字符频率
定义：字符频率是指在一个数据集中，某个字符出现的次数或概率。
作用：霍夫曼树的构建依赖于字符的频率，频率越高的字符在树中的路径越短，从而获得更短的编码。
示例：在字符串 "aabbbcc" 中，字符 'a' 的频率为 2，'b' 的频率为 3，'c' 的频率为 2。
叶子节点
定义：霍夫曼树中的叶子节点表示字符及其频率。
作用：使用叶子节点存储字符及其频率信息。
示例：在霍夫曼树中，字符 'a' 和 'b& ...
1. 平衡二叉树1.1 概述平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的每个节点的左右子树的高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。这意味着所有的平衡二叉树都必然是二叉搜索树，但并非所有的二叉搜索树都是平衡二叉树。平衡二叉树的主要目的是避免二叉搜索树（BST）在极端情况下退化为链表，从而保证查找、插入和删除操作的时间复杂度为 O(logn)。
常见的平衡二叉树包括：
AVL 树（严格平衡）：通过旋转操作保持平衡。
红黑树（相对平衡）：通过颜色标记和旋转操作保持平衡。
AVL 树的全称是“Adelson-Velsky and Landis Tree”，它以苏联数学家 Georgy Adelson - Velsky 和 Evgenii Landis 的名字命名。这两位数学家在 1962 年的论文中首次提出了这种自平衡的二叉搜索树结构，通过在插入和删除操作时进行旋转操作来保持树的平衡，确保树的高度始终维持在对数级别，从而保证了各种操作（如查找、插入、删除）具有 O(logn) 的时间复杂度。
1.2 平衡因子AVL 树的每个节 ...
1. 二叉树搜索树概述二叉搜索树（Binary Search Tree, BST）也叫二叉排序树（Binary Sort Tree），是一种特殊的二叉树，它满足以下性质：
左子树：左子树上所有节点的值都小于根节点的值。
右子树：右子树上所有节点的值都大于根节点的值。
递归性质：左子树和右子树本身也是二叉排序树。
二叉搜索树的一个重要特性是，它的中序遍历（左 → 根 → 右）结果是一个有序的序列。因此，二叉搜索树常用于实现动态集合的查找、插入和删除操作。
2. 二叉搜索树的基本操作2.1 查找操作二叉搜索树（BST）的查找操作是一种高效的算法，其平均时间复杂度为 O(log n)。查找步骤是基于二叉搜索树的特性：对于每个节点，左子树的所有节点值小于当前节点，右子树的所有节点值大于当前节点。以下是详细的查找步骤：
从根节点开始：查找操作必须从二叉搜索树的根节点开始。
比较目标值与当前节点值
如果 目标值 == 当前节点值，查找成功，返回该节点。
如果 目标值 < 当前节点值，则递归查找左子树。
如果 目标值 > 当前节点值，则递归查找右子树。
...
1. 前言WebSocket 是一种全双工通信协议，允许客户端和服务器之间建立持久化的双向通信连接。使用 WebSocket 可以在单个 TCP 连接上实现客户端与服务器之间的实时、低延迟的数据传输，有效解决了在使用HTTP通信时的局限性。如果还不清楚什么是WebSocket请先行阅读WebSocket 详解
如果涉及到网路通信一般会有两个角色，分别是是客户端和服务器端。在Qt的标准库中为我们提供了相关的操作类，一共有两个，分别是 QWebSocket 和 QWebSocketServer。
QWebSocket ：Qt 提供的用于实现 WebSocket 的数据通信类。
QWebSocketServer： Qt 提供的一个用于实现 WebSocket 服务器的类。它允许创建一个 WebSocket 服务器，接受客户端连接，并与这些客户端进行双向通信（通信过程需要使用 QWebSocket 类）。
Qt提供的这两个类相当于是对 WebSocket 协议进行了封装，不论是建立连接，还是数据通信已经全然看不到协议原有的样子了，我们只需要调用类提供的接口函数就可以非常轻松的实现客户端和 ...
1. WebSocket简介WebSocket 是一种全双工通信协议，允许客户端和服务器之间建立持久化的双向通信连接。WebSocket 协议设计的初衷是解决 HTTP 协议在实时交互上的局限性，例如长轮询、Ajax 等方法的高延迟问题。WebSocket 可以在单个 TCP 连接上实现客户端与服务器之间的实时、低延迟的数据传输。
1.1 单工、半双工和双工这三个术语用于描述通信的方向性，主要适用于数据传输和网络通信。它们的定义如下：
单工（Simplex）：单工通信是单向的，数据只能从发送方传送到接收方，而无法反向传输，通信过程不支持回复或反馈。
电视广播：信号从发射台发送到电视，但观众无法向发射台发送信号。
传统的广播电台：信号从发射台发送到收音机，但听众无法向发射台发送信号。
半双工（Half-Duplex）：半双工通信是双向的，但在任意时刻只能有一个方向的数据传输。发送方和接收方可以交替发送和接收数据，但不能同时进行。
对讲机：一个人说话时，另一方需要等待，直到说话者结束才能回复。
双工（Full-Duplex）：双工通信是完全双向的，数据可以同时在两个方向传 ...
1. 二叉树二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树由一个根节点和两棵互不相交的子树组成，这两棵子树分别称为根的左子树和右子树。二叉树的定义可以递归地描述：二叉树是一个有限的节点集合，这个集合可以是空集（即没有节点），或者由一个根节点和两棵互不相交的二叉树组成。
1.1 二叉树的特点和形态二叉树有三个特点依次是：
每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点
左子树和右子树是有顺序的，次序不能颠倒，也就是说二叉树是有序树
即使树中某节点只有一棵子树，也要区分它是左子树还是右子树
基于以上描述，我们对二叉树的形态做了归纳，一共有五种形态，分别是：
空二叉树
只有一个根节点
根节点只有左子树
根节点只有右子树
根节点既有左子树，又有右子树
以上五种形态应该是比较容易理解的，如果加大难度，大家可以思考一下，如果是有三个节点的二叉树，它一共有几种形态呢？
是的，一共有五种形态，上图中第一种和第二种二叉树比较特殊，它们只有左子树或者只有右子树，和线性表已经无异了。
1.2 特殊的二叉树斜树斜树顾名思义一定要是斜 ...
数据结构
未读1. 树的定义1.1 定义树（Tree）是n（n>=0）个节点的有限集。当n=0时称为空树。在任意一棵非空树中：
有且仅有一个特定的被称为根（Root）的节点
当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1、T2、……、Tm，其中每个集合本身又是一棵树，并且称为根的子树（SubTree），如下图所示：
对于上面这棵树而言，A是它的根节点，左侧橙色部分和右侧黄色部分分别是这棵树的两个子树，而分别在以B、C为根节点的子树中还有子树，所以我们可以说树是递归定义的，树的特性对于它们的子树以及子树的子树而言同样是适用的。
对于树的定义有3点需要特别强调一下：
层次结构：树具有根节点、子节点和叶节点，呈现出一种分层的结构。
无环性：树是一种无环结构，即0任意两个节点之间只有唯一的一条路径。
单一根节点：树只有一个根节点，从根节点可以访问树中的所有其他节点。
1.2 节点的关系和分类对于一棵树而言，里边有一些常用概念是需要大家掌握的：
节点（Node）：树中的每个元素称为节点，即图中的A、B、C、...、H、I、J。
根节点（Ro ...
KMP 算法，全称 Knuth-Morris-Pratt 算法，根据三个作者 Donald Knuth、Vaughan Pratt、James H. Morris 的姓氏的首字母拼接而成的。通过这种模式匹配算法可以大大避免字符串在匹配过程中被重复遍历的情况，它将匹配的时间复杂度提升到了 O(m+n)
1. 使用 PMT 表部分匹配表（Partial Match Table，简称PMT），它记录了模式串的前缀和后缀的最长相等长度，用于在匹配失败时跳过已经匹配的部分，避免回溯，也就是通过已掌握的信息来规避重复的运算。
"前缀"：除了最后一个字符外，字符串的所有头部子串
"后缀"：除了第一个字符外，字符串的所有尾部子串
以上图的"ABCDABD"为例：
“A”的前缀和后缀都为空集，共有元素的长度为0；
“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度为0；
“ABCD” ，共有元素的长度为0；
前缀为[A, AB, ABC]
后 ...
线程池是一种用于管理和重用线程的技术，广泛用于需要大量短生命周期线程的应用场景，如并发任务处理、网络服务和高性能计算等。使用线程池可以有效减少线程创建和销毁的开销，提升系统性能。本文将详细讲解线程池的基本概念、设计原则，并提供一个 C++ 实现的示例。
本文中涉及的C++11特性，不熟悉的话可以查阅C++11新特性文档
1. 线程池的设计线程池的基本思想是预先创建一定数量的线程，并将它们放入一个池中。线程池负责管理线程的生命周期，并将任务分配给空闲线程执行。这样可以避免每次任务执行时都创建和销毁线程的开销。
如果要编写一个线程池，它的组成如下:
线程池管理器：负责创建、销毁线程，维护线程池状态（如空闲线程、忙碌线程）。
任务队列：用于存储待执行的任务。任务通常以函数对象（如 std::function）的形式存储。
工作线程：线程池中的实际线程，它们从任务队列中取出任务并执行。
同步机制：用于保护任务队列和线程池状态的线程安全操作，通常使用互斥锁和条件变量。
在设计线程池时，我们需要考虑以下几个重要原则：
线程池大小管理：
固定大小：线程池中的线程数量固定不变。适用于负载比较稳定 ...
1. 排序的稳定性排序是我们生活中经常会面对的问题，小朋友站队的时候会按照从矮到高的顺序排列；老师查看上课出勤情况时，会按照学生的学号点名；高考录取时，会按照成绩总分降序依次录取等等。那么对于排序它是如何定义的呢？
排序是将一批无序的记录（数据）根据关键字重新排列成有序的记录序列的过程。 在工作和编程过程中我们经常接触的有八种经典的排序算法分别是：
冒泡排序
选择排序
插入排序
希尔排序
快速排序
归并排序
堆排序
基数排序
关于排序还有另一个大家需要掌握的概念就是排序的稳定性。排序的稳定性指的是在排序算法中，如果两个元素的键值相等，排序后它们的相对顺序是否会保持不变。
如果排序算法是稳定的，那么在排序之前和之后，相同键值元素的相对顺序是相同的；
如果排序算法是不稳定的，那么相同键值元素的相对顺序可能会发生变化。
假设我们有一组待排序的对象，其中每个对象有两个属性：键值和姓名。并要求根据键值对每组数据进行排序：
键值
姓名
4
令狐冲
3
任盈盈
4
岳不群
1
杨过
3
小龙女
使用稳定的排序算法（例如插入排序、归并排序、冒泡排序），结果会是 ...
