手撕AVL树
AVL树的概念二叉搜索树的不足二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
AVL树的提出两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即构建一颗绝对的平衡搜索二叉树,即可降低树的高度,从而减少平均搜索长度。
定义: 一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(log_2 n),搜索的时间复杂度O(log_2 n)
封装AVL树头文件12#include <utility>#include <cassert>
封装AVL树的节点
这里采用键值(KV)类型的二叉树节点,使其泛用性更高
...
C++特殊类的设计
接下来我们设计一些C++的常用特殊类,同时加深对C++类和对象的理解
设计一个不能被拷贝的类拷贝只会放生在两个场景中:拷贝构造函数以及赋值运算符重载,因此想要让一个类禁止拷贝,只需让该类不能调用拷贝构造函数以及赋值运算符重载即可。
C++98
将拷贝构造和赋值重载只私有声明且不定义即可
分析:
设为私有:防止类外调用,还能防止类外定义重新实现拷贝功能
只声明不定义:防止类内成员函数对其调用1234567//C++98class NoCopy{private://设置成私有 NoCopy(const NoCopy&); NoCopy& operator=(const NoCopy&);//只声明不定义};
C++11
C++11扩展了delete关键字的用法,可用于删除成员函数,尤其是删除默认成员函数
123456//C++11class CopyBan{ CopyBan(const CopyBan&) = delete; CopyBan& operator=(const CopyBan&) = delet ...
进程间通信
本篇博客更偏向于总括和导航,部分概念更细致的介绍将内嵌链接在文章中
重点内容
初识进程间通信
管道
消息队列
共享内存
信号量
进程间通信的目的
数据传输: 一个进程需要将它的数据发送给另一个进程
资源共享: 多个进程之间共享同样的资源
通知事件:一个进程需要向另一个或一组进程发送消息,通知它(它们)发生了某种事件(如子进程终止时要通知父进程)
进程控制: 有些进程希望完全控制另一个进程的执行(如Debug进程),此时控制进程希望能够拦截另一个进程的所有陷入和异常,并能够及时知道它的状态改变
进程间通信的主要方式
管道
System V进程间通信
POSIX进程间通信
进程间通信的分类管道
匿名管道
命名管道
System V IPC
System V 消息队列
SysTem V 共享内存
System V 信号量
POSIX IPC
消息队列
共享内存
信号量
互斥量
条件变量
读写锁
管道怎么使用?戳我去管道博客🔗
首先,管道是Unix中最古老的进程间通信的形式。它用于进程间的单向通信
那么具体是怎样实现的呢?从标题里就可以发现,是基于文件
既然一个文件可以被多个进 ...
进程间通信--匿名管道与命名管道
什么是管道文件首先,管道是Unix中最古老的进程间通信的形式。它用于进程间的单向通信
那么具体是怎样实现的呢?从标题里就可以发现,是基于文件
既然一个文件可以被多个进程打开,那么不妨将文件作为两个进程通信的媒介。但是一般位于磁盘上的文件,IO效率相比于CPU,内存之类的读写速度慢了几个数量级,但文件是可以被加载到内存中的,而专门建立在内存中,而没有磁盘文件,专门用于进程间通信的内存级文件,我们就叫它管道文件
管道文件由内核维护
管道文件是单向的,可以是父进程->子进程,也可以子进程->父进程
管道读写规则
写端未关闭,但读端无数据可读时
(默认)O_NONBLOCK disable:read调用阻塞,即进程暂停执行,一直等到有数据来到为止。
O_NONBLOCK enable:read调用返回-1,errno值为EAGAIN。
读端未关闭,但写端写入管道已经写满时
(默认) O_NONBLOCK disable: write调用阻塞,直到有进程读走数据
O_NONBLOCK enable:wrtie调用返回-1,errno值为EAGAIN
若写端关闭,则read返 ...
【Linux】简易进程池
原理匿名管道可用于父子进程间的通讯,于是可以有父进程创建多个子进程形成进程池,并通过匿名管道文件向各个子进程派发任务
戳我去管道原理🔗
这里使用C++编写进程池代码,在程序中创建多个进程,并在父进程中使用自定义类channel用于描述和管理子进程,然后在task.hpp中模拟一些任务给主程序随机派发
代码代码规范这次对形参有了新的规范,这里用variable代指形参名
输入: const &variable
输出: *variable
输入输出: &variable
准备makefile文件这里使用g++编译,规定语法标准为C++11
123456processPool:processPool.cc g++ -o $@ $^ -std=c++11.PHONY:cleanclean: rm -rf processPool
准备任务文件首先要准备前后需要用到的头文件,然后构建模拟任务,并提供加载任务列表的函数
task.hpp
12345678910111213141516171819202122232425262728293031323334353637383 ...
【数据结构】一步到胃,键值对版二叉搜索树
什么是二叉搜索树二叉搜索树的定义是一颗二叉树的所有节点满足:根的左右孩子存在时,满足 左孩子 < 根 < 右孩子
递归定义则是:
左子树的根 < 根 < 右子树的根
左子树是二叉搜索树,右子树是二叉搜索树
写一个验证二叉搜索树的函数Leetecode题目链接🔗
封装一个二叉树类文件布置
BSTree.h用于声明和实现BSTree类
test.cpp用于测试
头文件BSTree.h
123#include <iostream>#include <utility>
test.cpp
1#include "BSTree.h"
命名空间1namespace key_value
这里使用key_value作为命名空间,表示这是键值表示的搜索二叉树
定义节点二叉树的节点用于储存键值对和左右指针,并提供默认构造函数,使用初始化列表初始化成员变量
123456789101112131415template<class K,class V>class BSTNode{public: BSTNode(c ...
文件缓冲区
前置博客 基础IO
为什么有缓冲因为磁盘的读写与内存的读写操作速度相比,磁盘的读写是相差数量级的慢,所以为了提高内存多次,频繁读写磁盘文件的效率,缓冲区被投入使用。尤其是内存内容写入磁盘时,常常先写入内存级缓冲区,再在特定规则下一次性将缓冲区的内容写入磁盘
**本文以C语言提供的用户级缓冲区为例介绍缓冲区
缓冲区的刷新规则首先当一个进程正常退出时,会先刷新缓冲区再关闭文件,此时必定有一次刷新
而当进程运行时缓冲区的刷新策略主要有以下三种
无缓冲 内容直接写入文件
行缓冲 输入一般内容不刷新,遇到\n时刷新一次缓冲区
全缓冲 缓冲区有容量限制,满了之后就刷新
认识一下C语言的缓冲区这里的系统环境是Linux
刷新规则运行如下代码
12345678910111213#include <stdio.h>#include <unistd.h>int main(){ FILE* pfile = fopen("file.txt","w");//打开空文件 fprintf(stdout,"stdout ...
Linux文件系统
文件系统的组织方式
这里介绍一下Block Group里的分区内容
超级块(Super Block): 存放文件系统本身的结构信息。记录的信息主要有:bolck(数据块) 和 inode(属性块)的总量,未使用的block和inode的数量,一个block和inode的大小,最近一次挂载的时间,最近一次写入数据的时间,最近一次检验磁盘的时间等其他文件系统的相关信息。Super Block的信息被破坏,可以说整个文件系统结构就被破坏了
GDT(Group Descriptor Table): 块组描述符,描述块组属性信息。这里不作详细介绍
块位图(Block Bitmap):位图中的比特位记录着Data Block中哪个数据块已经被占用,哪个数据块没有被占用
inode位图(inode Bitmap):每个比特位表示一个inode是否空闲可用。
inode表(inode Table):每一个inode存放了各自文件的属性,如文件大小,所有者,最近修改时间等
数据区:存放文件内容
Linux系统中文件的增删查改Linux中,每一个文件都有自己的inode,而每一个inode有自己的in ...
C语言文件操作
用户级文件操作C语言的文件操作也是用户级的文件操作,通过FILE对象来管理每一个被打开的文件,以及提供了用户级文件缓冲区,因此还涉及到冲刷缓冲区等问题
FILE 类FILE类描述了一个文件流。里面存储了文件控制所需的信息:
指向自身缓冲区的的指针
位置指示器
状态指示器
所以C语言中对文件的管理就是对FILE对象的管理
基础操作 - 针对一般文件基础示例1234567891011#include <stdio.h>int main(){ FILE* pfile = fopen("file.txt", "w");//"w"模式打开文件file.txt int code = 1; const char* msg = "this is a msg"; fprintf(pfile, "get msg : %s code:%d", msg, code);//格式化输出字符串 fclose(pfile);//冲刷缓冲区并关闭文件 return 0;}
以上代码创建 ...
=C++= sizeof关键字详解
简介sizeof作为C/C++关键字,基本用法是求字节大小,但仅仅这一项用法在细节上就有很多说法了
求内置类型变量的大小有两种写法,以int a = 0的变量a为例
sizeof a
sizeof(a)
都可以求变量a的大小,但注意,该变量的大小仅与变量类型有关,而与值无关
求内置类型的大小求类型大小时必须加上括号
例如sizeof(int)
求数组的大小
当数组声明在全局或sizeof处于数组声明语句的局部作用范围时,能够用sizeof(<数组名>)求数组大小
当数组名经过函数传参或加减常量运算后,退化为指针变量,类型大小在32位机器中为4,64位机器中为8
12345678910111213141516171819#include <iostream>using namespace std;int g_arr[10] = { 0 };void func(int st_arr[]){ cout << sizeof(st_arr) << endl;//此处退化为指针变量,输出4或8} ...