二叉搜索树
二叉搜索树在二叉搜索树中，左子树所有节点的值<根节点值<右侧所有节点的值，且任意节点的左右子树也是二叉搜索树。 二叉搜索树的操作查找节点类比二分算法，每轮排除一半情况，所以时间复杂度是$O(\log n)$： 123456789101112131415TreeNdoe *search(BinarySearchTree *bst,int num){ TreeNdoe *cur=bst->root; while(cur!=NULL){ if(cur->val<num){ cur=cur->right; } else if(cur->val>num){ cur=cur->left; } else{ break; } } return cur;} 插入节点分为两步：...
树
二叉树二叉树是一种非线性数据结构，体现了“一分为二”的分治逻辑。与链表类似，其基本单元是节点每个节点包含值和左右两个节点引用。 C语言实现二叉树如下： 1234567891011121314151617typedef struct TreeNode{ int val; int height; struct TreeNode *left; struct TreeNode *right;}TreeNode;// 构造函数TreeNode *newTreeNode(int val){ TreeNode *node; node=(TreeNode*)malloc(sizeof(TreeNode)); node->val=val; node->height=0; node->left=NULL; node->right=NULL; return node;} 二叉树常见术语 根节点位于二叉树顶层的节点，没有父节点 叶节点没有子节点的节点，其两个指针均指向None...
PE文件格式
总览图: 前置知识 虚拟地址 WIndows系统中，PE文件被系统加载器映射到内存中，每个程序都有自己的虚拟空间，该虚拟空间中的内存地址称为虚拟地址（VA）。 相对虚拟地址 PE文件虽然有一个首选的载入地址，但是其可在进程空间的任何地方载入，故需要有一种方式方式来指定内存中的具体地址。为避免PE文件中出现绝对地址故引入了相对虚拟地址（RVA），其是相对于PE文件载入地址的一个偏移量，计算公式为目标地址-载入地址=RVA。 文件偏移地址 PE文件储存在磁盘里时某个数据相对于文件头的偏移量。 DOS头PE文件都是从一个DOS程序开始的，程序在DOS下执行时系统能识别这是一个有效的执行体并运行紧随MZ header的DOS stub中的内容，即显示一个简单的错误提示。程序员也可以自行在此处实现完整的DOS程序代码。 MS-DOS头部完整结构如下： 123456789101112131415161718192021typedef struct _IMAGE_DOS_HEADER { // DOS .EXE header WORD e_magic; // Magic nu...
哈希表
哈希表又称散列表，其通过建立键key和值value之间的映射以实现高效的元素查询。与数组和链表对比，其添加元素、查询元素和删除元素的时间均为$O(1)$. 哈希表常用操作初始化、查询操作、添加键值对和删除键值对1234567891011121314151617// 初始化哈希表unordered_maps<int,string>map;// 在哈希表中添加键值对map[12345]="凉宫";map[12346]="长门";map[15532]="朝比奈";map[11451]="阿虚";map[18946]="古泉";// 查询操作// 向哈希表中输入键 key ，得到值 valuestring name = map[12346];// 删除操作// 在哈希表中删除键值对 (key, value)map.erase(12346); 123456789101112131415161718# 初始化哈希表hmap: dict = {}# 添加操作#...
栈与队列
栈栈（stack）是一种遵循先入后出逻辑的线性数据结构 通常我们能直接使用编程语言内置的栈类（C语言未提供） 123456789101112131415161718192021/* 初始化栈 */stack<int> stack;/* 元素入栈 */stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);/* 访问栈顶元素 */int top=stack.top();/* 元素出栈 */stack.pop();/* 获取栈的长度 */int size = stack.top();/* 判断是否为空 */int size=stack.empty(); 栈的实现当我们使用的语言未提供栈类时，我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。 基于链表的实现 将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，只需将元素插入链表头部，这种节点插入方法被称为“头插法” 1234567891011121314151617181920212223242526...
数组与链表
数组数组是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。 数组常用操作 初始化数组 在数组中访问元素非常高效，我们可以在$O(1)$时间内随机访问数组中的任意一个元素 123456int randomAccess(int *nums,int size){ int randomIndex=rand()%size; int randomNum=nums[randomIndex]; return randomNum;} 增删元素 数组元素在内存中是紧挨着的，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。 12345678void insert(int*nums,int size,int num,int index){ for(int i=size-1;i>index;i--) { nums[i]=nums[i-1]; } nums[index]=num;} 同理，删...
时间&空间复杂度
我个人理解的复杂度其实就是数量级。对于时间复杂度来说，其即为算法循环次数的数量级。确定的常数次就是$O(1)$，$x$层循环就是$O(n^x)$。 比较特殊的复杂度： 指数阶$O(2^n)$ 123456789101112131415int exponentail(int n){ int count=0; int bas=1; //类比细胞分裂一分二，二分四的过程 for(int i=0;i<n;i++) { for(int j=0;j<bas;j++) { count++; } bas*=2; } return count;} 对数阶$O(log n)$ 1234567891011int logarithmic(int n){ int count=0; //对数阶反映了“每轮缩减到一半”的情况 while(n>1) { ...
WindowsAPI学习笔记
Windows窗口程序基础在屏幕上显示一个窗口的过程一般包括以下步骤，也就是入口函数WinMain的执行流程： 注册窗口类 在注册之前，要先填写RegisterClassEx函数的参数WNDCLASSEX结构的各个字段。 创建窗口 显示窗口 、刷新窗口客户区 运行消息循环 获取消息、转换消息、将消息分发到回调函数WindowProc处理。 接下来分别介绍每一个步骤： 注册窗口类RegisterClassEx函数用于注册窗口类，其函数原型如下： 1ATOM RegisterClassEx(_In_const WNDCLASSEX* lpwcx); 其中参数lpwcx是一个指向WNDCLASSEX结构的指针，调用RegisterClassEx函数必须先初始化此结构： 1234567891011121314typedef struct tagWNDCLASSEX { UINT cbSize; // 结构体大小 UINT style; // 窗口类的样式 WNDPROC lpfnWndProc; // 窗口过程函数 ...
C++学习笔记（更新中）
基础的输入与输出 输出工具cout 1cout << "Hello World"; // 输出Hello World cout可根据变量类型自动识别输出格式，免去printf中要使用的如%d的格式控制符。 换行符endl 1cout << "Hello World" << endl; // 输出Hello World并换行 等效于输出"\n" 输入工具cin 12int a; cin >> a; // 输入a的值 cin根据变量类型自动识别输入格式，免去scanf中要使用的如%d的格式控制符。 插入运算符<<和>> 指明信息流动的路径 cout是一个ostream类对象，cin是istream类对象，它们都定义在iostream头文件中。要使用cout和cin，必须在程序开头包含iostream头文件，并使用using namespace std;编译指令使std名称空间内的名称可用。 数据处理 以...
ChaCha20算法总结
算法详解ChaCha20 是一种基于流密码的加密算法，由 Daniel J. Bernstein 于 2008 年提出，是 Salsa20 的改进版本。它的主要优点是速度快 、安全性高 且易于实现 。ChaCha20 将密钥（256 位） 、随机数（Nonce，96 位）和** 计数器（Counter，32 位）**经过一系列混合运算生成密钥流（Key Stream），再与明文进行按位异或得到密文。 ChaCha20 内部状态为一个 4×4 的 32 位无符号整数矩阵 ，初始排列如下： 1234[ 常量 ][ 常量 ][ 常量 ][ 常量 ] [ key0 ][ key1 ][ key2 ][ key3 ] [ key4 ][ key5 ][ key6 ][ key7 ] [counter][nonce0][nonce1][nonce2] 每一次加密生成 64 字节的密钥流块 ，ChaCha20 的核心是 Quarter Round（四分之一轮） ，它使用加法、异或、循环左移（ROTL）混合数据。 加密流程示意图： 实战识别在逆向分析中判断 ChaCha20 的常...