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
小龙女
使用稳定的排序算法(例如插入排序、归并排序、冒泡排序),结果会是 ...
1. 二分搜索概述二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
二分搜索是一种高效的查找算法,适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割,从而快速缩小查找范围。
二分搜索每次把搜索区域减少一半,时间复杂度为 O(logn)(n代表集合中元素的个数)。
二分搜索的基本步骤如下:
初始条件:将搜索范围设为数组的整个区间。
查找中间元素:计算当前区间的中间索引。
比较中间元素:将中间元素与目标值进行比较:
如果中间元素等于目标值,查找成功,返回中间索引。
如果中间元素小于目标值,将搜索范围缩小到右半部分。
如果中间元素大于目标值,将搜索范围缩小到左半部分。
重复步骤 2 和 3,直到找到目标值或搜索范围为空。
在下图中为大家展示了二分搜索的过程:
2. 递归实现递归实现二分搜索的代码如下:
1234567891011121314151617181920212223242526272 ...
数据结构
未读1. 串“天行健,君子一自强不息;地势坤,君子以厚德载物”这是《易经》中的原文,对于普通人而言这就是两句话,对于程序员来说这就是一个数据块,是多个相同类型的字符的集合,在数据结构中将其称之为串。
串(String)是由零个或多个字符组成的有限序列,又名叫字符串。一般记作 s=“a1a2a3……an” (n>=0)。其中,s是串的名称,双引号(或单引号)括起来的字符序列是串的值,但是要注意引号不属于串的内容。
空串: 零个字符的串成为空串,它的长度为0,可以用双引号“”表示
串的长度: 串中的字符的数量就是串的总长度
1.1 串的储存结构串的存储结构和线性表相同,分为两种顺序存储结构和链式存储结构。
顺序存储结构:
串的顺序存储结构是用一组地址连续的存储单元(说白了就是数组)来存储串中的字符序列。
大家都学过C语言,此处就不再展开阐述了。
链式存储结构:
对于串的链式存储结构,与线性表相似,但由于串结构的特殊性,结构中的每一个数据元素是一个字符,那么一个链表节点存储一个字符就存在很大的空间浪费,因此可以考虑使用一个节点存储多个字符,最后一个节点如果没有被 ...
1. 用两个栈实现一个队列根据栈的特性,通过一个栈来实现一个队列的行为是做不到的,所以可以再加一个。用两个栈实现一个队列,可以利用栈的后进先出(LIFO)性质,将栈的顺序反转,从而实现队列的先进先出(FIFO)行为。
具体实现方法如下:
定义两个栈:
stack1:用于入队操作。
stack2:用于出队操作
入队操作(enqueue):将新元素压入 stack1。
出队操作(dequeue):
如果 stack2 为空,将 stack1 中的所有元素弹出并压入 stack2。
弹出 stack2 的栈顶元素作为出队元素。
访问队头(front):元素的操作和出队列相似,只是不需要弹出元素。
下图模拟了数据在两个栈(自定义队列)中的移动过程:
通过上面的描述,可以写出如下的C++代码:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374 ...