hanafuda_store's Blog

堆是一种满足特定条件的完全二叉树，其中大顶堆中任意节点的值大于等于其子节点的值，小顶堆中任意节点的值小于等于其子节点的值。 其具有一下特点： 最底层节点靠左填充，其他层的节点都被填满 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底” 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的 堆的常用操作 堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。 C未直接提供heap类，C++代码如下： 1234567891011121314151617181920212223242526272829priority_queue<int,vector<int>,greater<int>>minHeap; // 小顶堆priority_queue<int,vector<int>,less<int>maxHeap>; // 大顶堆// 元素入堆maxHeap.push(1);maxHeap.p...

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从O(log⁡n)O(\log n)O(logn)劣化为O(n)O(n)O(n)。 而AVL树确保在持续添加和删除节点后其不会退化，从而使得各种操作的时间复杂度保持在O(log⁡n)O(\log n)O(logn)级别。 AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质。 由于 AVL 树的相关操作需要获取节点高度，因此我们需要为节点类添加 height 变量： 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)); ...

二叉搜索树 在二叉搜索树中，左子树所有节点的值<根节点值<右侧所有节点的值，且任意节点的左右子树也是二叉搜索树。 二叉搜索树的操作 查找节点 类比二分算法，每轮排除一半情况，所以时间复杂度是O(log⁡n)O(\log n)O(logn)： 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;} 二叉树常见术语 根节点 位于二叉树顶层的节点，没有父节点 叶节点 没有子节点的节点，其两个指针均指...

总览图: 前置知识 虚拟地址 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(); 栈的实现 当我们使用的语言未提供栈类时，我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。 基于链表的实现 将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，只需将元素插入链表头部，这种节点插入方法被称为“头插法” 12345678910111213141516171819202122232425...

数组 数组是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。 数组常用操作 初始化数组 在数组中访问元素非常高效，我们可以在O(1)O(1)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) { ...

Windows窗口程序基础在屏幕上显示一个窗口的过程一般包括以下步骤，也就是入口函数WinMain的执行流程： 注册窗口类 在注册之前，要先填写RegisterClassEx函数的参数WNDCLASSEX结构的各个字段。 创建窗口 显示窗口 、刷新窗口客户区 运行消息循环 获取消息、转换消息、将消息分发到回调函数WindowProc处理。 接下来分别介绍每一个步骤： 注册窗口类RegisterClassEx函数用于注册窗口类，其函数原型如下： 1ATOM RegisterClassEx(_In_const WNDCLASSEX* lpwcx); 其中参数lpwcx是一个指向WNDCLASSEX结构的指针，调用RegisterClassEx函数必须先初始化此结构： 1234567891011121314typedef struct tagWNDCLASSEX { UINT cbSize; // 结构体大小 UINT style; // 窗口类的样式 WNDPROC lpfnWndProc; // 窗口过程函数 ...