并查集详解及相关例题解析

参考内容: 图论——并查集(详细版) 并查集(Disjoint-set)是一种精巧的树形数据结构,它主要用于处理一些不相交集合的合并及查询问题。一些常见用途,比如求联通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(LCA)等。 并查集的理念是只关注个体属于哪个阵营,并不关心这个阵营中个体内部的关系,比如我们常说的张三是李家沟的,王二是王家坝的。同时并查集借助个体代表集体的思想,用一个元素代表整个群体,就像我们开学都会有学生代表、教师代表讲话一样,在台上讲话的那一个学生就代表了学校所有的学生。 并查集基本操作 并查集的基本操作主要有初始化 init、查询 find和合并 union操作。 初始化 在使用并查集的时候,常常使用一个数组fa来存储每个元素的父节点,在一开始的时候所有元素与其它元素都没有任何关系,即大家相互之间还不认识,所以我们把每个元素的父节点设为自己。 #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } 查询 查询即找到指定元素的祖先。需要注意的是,这里我们需要找到指定元素的根祖先,不能找到爸爸或者爷爷就停止了,而是要找到查找不下去了为止,所以要不断的去递归下去,直到找到父亲为自己的结点才结束。 int find(int i) { if(i == fa[i]) // 递归出口 return i; else return find(fa[i]); // 不断向上查找祖先 } 考虑下面的场景,假如第一次我们需要查询元素5的祖先,第二次需要查询元素4的祖先,会发现第一次查询包含了第二次查询的计算过程,但我们的程序却傻傻的计算了两次,有没有办法去来优化查询过程,让每一次查询都能利用到此前查询计算的便利? 考虑到并查集并不关心某个元素的爸爸、爷爷是谁,只关心最终的祖先是谁,所以我们可以在查询的过程中顺便做一些修改,比如在查询5的过程中,顺便就把4和2的父亲给修改为1,即我们在查找过程中进行路经压缩 int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); // 进行路径压缩 return fa[i]; } } 合并 合并操作即介绍两个人相互认识,将他们纳入同一个帮派,只需要将俩元素的父亲修改为同一个即可。 void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } 相关练习题目 洛谷 P1551 亲戚 题目连接:https://www.luogu.com.cn/problem/P1551 题目描述 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:xxx 和 yyy 是亲戚,yyy 和 zzz 是亲戚,那么 xxx 和 zzz 也是亲戚。如果 x,yx,yx,y 是亲戚,那么 xxx 的亲戚都是 yyy 的亲戚,yyy 的亲戚也都是 xxx 的亲戚。 输入格式 第一行:三个整数 n,m,p,(n,m,p≤5000)n,m,p,(n,m,p≤5000)n,m,p,(n,m,p≤5000) 分别表示有 nnn 个人,mmm 个亲戚关系,询问 ppp 对亲戚关系。 以下 mmm 行:每行两个数 Mi,Mj,1≤Mi,Mj≤nM_i,M_j,1≤M_i,M_j≤nMi​,Mj​,1≤Mi​,Mj​≤n,表示 MiM_iMi​ 和 MjM_jMj​ 具有亲戚关系。 接下来 ppp 行:每行两个数 Pi,PjP_i,P_jPi​,Pj​,询问 PiP_iPi​ 和 PjP_jPj​ 是否具有亲戚关系。 输出格式 ppp 行,每行一个Yes或No。表示第 iii 个询问的答案为“具有”或“不具有”亲戚关系。 输入输出样例 # 输入 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 # 输出 Yes Yes No 题目解析 可以发现这是一个非常标准的并查集问题,简直和并查集模版如出一辙,因此直接将所有关系读取后进行合并,然后直接查询父亲是否为同一个即可。 #include<bits/stdc++.h> using namespace std; #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } int main() { int n, m, p; int a, b; cin>> n >> m >> p; init(n); for(int i = 0; i < m; i++){ cin >> a >> b; union(a, b); } for(int i = 0; i < p; i++){ cin >> a >> b; int fa_a = find(a); int fa_b = find(b); if(fa_a == fa_b) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } 杭电 OJ1213 How Many Tables 题目连接:https://acm.hdu.edu.cn/showproblem.php?pid=1213 题目描述 Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least. 输入格式 The input starts with an integer T(1<=T<=25)T(1<=T<=25)T(1<=T<=25) which indicate the number of test cases. Then TTT test cases follow. Each test case starts with two integers NNN and M(1<=N,M<=1000)M(1<=N,M<=1000)M(1<=N,M<=1000). NNN indicates the number of friends, the friends are marked from 111 to NNN. Then MMM lines follow. Each line consists of two integers AAA and B(A!=B)B(A!=B)B(A!=B), that means friend AAA and friend BBB know each other. There will be a blank line between two cases. 输出格式 For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks. 输入输出样例 # 输入 2 5 3 1 2 2 3 4 5 5 1 2 5 # 输出 2 4 题目解析 分析可以发现,这个问题要我们做的是统计在所有元素合并之后,统计总共有多个和集合。很轻松就能写出下面的 AC 代码。类似的问题还有杭电 OJ1232 畅通工程。 读者大人可以在此基础上继续进行延伸,我们实际生活中每个桌子只能坐 8 个人,假设还需要考虑每桌人数的容量,又如何进行改进呢? #include<bits/stdc++.h> using namespace std; #define ARR_LEN 6000 int fa[ARR_LEN]; void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); fa[fa_i] = fa_j; } int main() { int n, m, a, b, t; cin>>t; for(int i = 0; i < t; i++){ cin>>n>>m; int ans = 0; init(n); for(int i = 0; i < m; i++) { cin>>a>>b; union(a, b); } for(int i = 1; i <= n; i++) { // 如果父亲是自己,那么就表示一个独立的集合 if(find(i) == i) ans++; } cout<<ans<<endl; } } 杭电 OJ1272 小希的迷宫 题目连接:https://acm.hdu.edu.cn/showproblem.php?pid=1272 题目描述 小希设计了一个迷宫让 Gardon 玩,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间 A 和 B,那么既可以通过它从房间 A 走到房间 B,也可以通过它从房间 B 走到房间 A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从 5 到达 8。 输入格式 输入包含多组数据,每组数据是一个以 0 0 结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为 1,且不超过 100000。每两组数据之间有一个空行。整个文件以两个 -1 结尾。 输出格式 对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出Yes,否则输出No。 输入输出样例 # 输入 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 # 输出 Yes Yes No 题目解析 其实这个问题就是让我们判断一个连通图中是否存在环,那么问题就转换为寻找出现环的条件。其实不难发现出现下面两种情况时,连通图即存在环。 在查找过程中,发现两个不同元素的父亲是相同的; 若不存在环,则边的数量一定比顶点数量少 1。 #include<bits/stdc++.h> using namespace std; #define ARR_LEN 100010 int fa[ARR_LEN]; bool visited[ARR_LEN]; // 用于辅助记录顶点的数量 int edges, points; // 记录顶点和边的数量 bool hascycle; // 是否存在环 void init() { hascycle = false; edges = 0; points = 0; for(int i = 1; i < ARR_LEN; i++) fa[i] = i, visited[i] = false; } int find(int i) { if(i == fa[i]){ return i; } else { fa[i] = find(fa[i]); return fa[i]; } } void union(int i, int j) { int fa_i = find(i); int fa_j = find(j); // 两个元素祖先相同,存在环 if(fa_i == fa_j) { hascycle = true; } else { visited[i] = true; visited[j] = true; edges++; fa[fa_i] = fa_j; } } int main() { int a, b; init(); while(cin>>a>>b) { if(a == 0 && b == 0) { cout<<"Yes"<<endl; continue; } if(a == -1 && b == -1) { return 0; } union(a, b); while(cin>>a>>b){ if(a == 0 && b == 0) { break; } union(a, b); } if(hascycle) { cout<<"No"<<endl; continue; } for(int i = 1; i < ARR_LEN; i++){ if(visited[i]) { points++; } } if(points == edges + 1) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } init(); } }
Read More ~

《算法竞赛进阶指南》165 小猫爬山题解

参考内容: [洛谷][noip][算法竞赛进阶指南]小猫爬山 《算法竞赛进阶指南》小猫爬山 小猫爬山 题目描述 题目链接:https://www.acwing.com/problem/content/167/ ​Freda 和 Rainbow 饲养了 N 只小猫。这天,小猫们要去爬山。经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 Freda 和 Rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W,而 N 只小猫的重量分别是C1、C2……Cn。当然,每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车,Freda 和 Rainbow 就要付 1 美元,所以他们想知道,最少需要付多少美元才能把这 N 只小猫都运送下山? 输入格式 ​第一行包含两个用空格隔开的整数,N 和 W。接下来 N 行每行一个整数,其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。 输出格式 输出一个整数,最少需要多少美元,也就是最少需要多少辆缆车。 分析解答 贪心 经过思考发现,我们只需要尽可能的在每辆车上都放更多的小猫,就能以最经济的方式把所有小猫都送下山。所以是一个非常明显的贪心题目,我们将所有小猫按重量排序,尽可能把肥猫先送下山即可。具体实现代码如下: #include<bits/stdc++.h> using namespace std; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } int slove(int *num, int n, int w) { int ans = 0; int remain = 0; int load = 0; sort(num, num+n); while(true){ for(int i = 0; i < n; i++){ // 连当前最小的猫都装不下,那么就新开一辆车 if(num[i] != -1 && remain < num[i]){ ans++; remain = w; break; } } for(int i = n-1; i >= 0; i--){ // 从大到小查找,尽可能装肥猫 if(num[i] != -1 && remain >= num[i]){ remain -= num[i]; // 运送走的小猫重量以 -1 表示 num[i] = -1; load++; break; } } // 如果所有小猫都运走了,那么当前 ans 就是答案 if(load >= n) return ans; } } int main() { int n, w; int cat[1000000]; cin>>n>>w; cin_arr(cat, n); cout<<slove(cat, n, w)<<endl; } 经过实际测试发现,盲目使用贪心思想的算法并不正确,例如如下测试用例。 6 16 9 5 5 5 4 3 贪心的结果是使用 3 辆车,分别为9+5、5+5+4、3;而正确的结果却是使用 2 辆车,分别为9+4+3和5+5+5。 深度优先搜索 既然贪心思想在这里行不通,那么我们就采用暴力搜索,即小猫可以放在现有任意一辆车上。具体实现代码如下: #include<bits/stdc++.h> using namespace std; #define N 2000 int n, w; int cat[N]; int sum[N] = {0}; // 第 i 辆车当前重量 int ans = N; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } void dfs(int cur_cat, int cur_car) { if(cur_car > ans) // 求最小值,不符合直接返回 return ; if(cur_cat == n) { // 所有小猫都上车了 ans = cur_car; return ; } for(int i = 0; i < cur_car; i++) { if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去 sum[i] += cat[cur_cat]; // 当前猫占用重量 dfs(cur_cat+1, cur_car); // 继续放下一只猫 sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来,因为是循环,所以放入下一辆车里面 } } // 新开一辆车,把当前这只猫放到新的车里面 sum[cur_car] = cat[cur_cat]; dfs(cur_cat+1, cur_car+1); sum[cur_car] = 0; // 把猫拿出来 } int main() { cin>>n>>w; cin_arr(cat, n); dfs(0, 0); cout<<ans<<endl; } 搜索优化 考虑到每次都是在车数量固定的情况下进行搜索的,那么少满足一次(sum[i] + cat[cur_cat] <= w)条件,就会少一次递归的调用,也即少一次搜索。那么如何能尽快使得程序尽快不满足该条件呢? 让sum[i]减小的速度加快就会减少搜索分支,即每次放更重一点的猫进去,就能达到效果。所以我们可以在进行搜索前将小猫的重量进行降序排序,这样从肥猫开始搜索就会减少分支。 #include<bits/stdc++.h> using namespace std; #define N 2000 int n, w; int cat[N]; int sum[N] = {0}; // 第 i 辆车当前重量 int ans = N; void cin_arr(int *num, int len) { for(int i = 0; i < len; i++){ cin>>num[i]; } } bool cmp(int a, int b) { return a > b; } void dfs(int cur_cat, int cur_car) { if(cur_car > ans) // 求最小值,不符合直接返回 return ; if(cur_cat == n) { // 所有小猫都上车了 ans = cur_car; return ; } for(int i = 0; i < cur_car; i++) { if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去 sum[i] += cat[cur_cat]; // 当前猫占用重量 dfs(cur_cat+1, cur_car); // 继续放下一只猫 sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来,因为是循环,所以放入下一辆车里面 } } // 新开一辆车,把当前这只猫放到新的车里面 sum[cur_car] = cat[cur_cat]; dfs(cur_cat+1, cur_car+1); sum[cur_car] = 0; // 把猫拿出来 } int main() { cin>>n>>w; cin_arr(cat, n); sort(cat, cat+n, cmp); // 反排序优化搜索 dfs(0, 0); cout<<ans<<endl; }
Read More ~

二叉树的前序、中序、后序、层序遍历

参考内容: 五分钟让你彻底理解二叉树的非递归遍历 Python实现二叉树的非递归遍历 二叉树遍历——深度优先(前中后序)+广度优先(层序遍历) 构造二叉树 定义二叉树结构如下 struct node { int data; node *left; node *right; }; 构造如下形态二叉树 node *init_tree() { node *node1 = (node *)malloc(sizeof(node)); node *node2 = (node *)malloc(sizeof(node)); node *node3 = (node *)malloc(sizeof(node)); node *node4 = (node *)malloc(sizeof(node)); node *node5 = (node *)malloc(sizeof(node)); node *node6 = (node *)malloc(sizeof(node)); node *node7 = (node *)malloc(sizeof(node)); node *node8 = (node *)malloc(sizeof(node)); node1->data = 1; node2->data = 2; node3->data = 3; node4->data = 4; node5->data = 5; node6->data = 6; node7->data = 7; node8->data = 8; node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->right = node6; node5->left = node7; node5->right= node8; return node1; } 前序遍历(递归) 前序遍历顺序为根左右。要遍历整个二叉树我们就需要遍历二叉树的每一个子树,对于任何一个子树它的遍历方式均为根左右顺序遍历。即所有子问题均与父问题除规模大小不同外,其余均相同。所以可以采用递归方式实现前序遍历。 // 前序遍历 根左右 void pre_order_traversal(node *root) { if(root) { cout<<root->data<<" "; pre_order_traversal(root->left); pre_order_traversal(root->right); } } 遍历结果为:1 2 4 5 7 8 3 6 中序遍历(递归) 中序遍历顺序为左根右。其与前序遍历仅顺序不同,其余均相同。 // 中序遍历 左根右 void in_order_traversal(node *root) { if(root) { in_order_traversal(root->left); cout<<root->data<<" "; in_order_traversal(root->right); } } 遍历结果为:4 2 7 5 8 1 3 6 后序遍历(递归) 后序遍历顺序为左右根。其与前序、中序遍历仅顺序不同,其余均相同。 // 后序遍历 左右根 void post_order_traversal(node *root) { if(root) { post_order_traversal(root->left); post_order_traversal(root->right); cout<<root->data<<" "; } } 遍历结果为:4 7 8 5 2 6 3 1 前序遍历方法一(非递归) 因为递归实际上是由系统帮我们进行压栈,所以理论上所有递归算法都可以改为循环+栈实现,那么我们先照着上述前序遍历的样子修改为循环+栈的形态。需要注意的是由于栈先进后出的特性,为了保证左孩子在右孩子前被访问,所以应该先右孩子入栈,再左孩子入栈。 // 前序遍历 根左右 void pre_order_traversal(node *root) { stack<node *> s; s.push(root); while(!s.empty()) { node *cur = s.top(); s.pop(); if(cur) { cout<<cur->data<<" "; s.push(cur->right); s.push(cur->left); } } } 遍历结果为:1 2 4 5 7 8 3 6 前序遍历方法二(非递归) 现在我们换一种思路来实现前序非递归遍历,仔细观察前序遍历的递归调用过程。 先把从根结点开始的所有左子树放入栈中; 弹出栈顶元素 如果栈顶元素有右子树,那么右子树入栈 重复上述过程直到栈为空 因此我们可以写出遍历代码 // 前序遍历 根左右 void pre_order_traversal(node *root) { stack<node *> s; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { cout<<cur->data<<" "; s.push(cur); cur = cur->left; } if(!s.empty()) { cur = s.top(); s.pop(); cur = cur->right; } } } 遍历结果为:1 2 4 5 7 8 3 6 中序遍历(非递归) 有了前面的基础,我们再来考虑中序遍历,会发现中序遍历与前序遍历只是打印结点的位置不一样。前序遍历是在结点入栈时打印,中序遍历只需要替换为在结点出栈时打印即可。 // 中序遍历 左根右 void in_order_traversal(node *root) { stack<node *> s; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { s.push(cur); cur = cur->left; } if(!s.empty()) { cur = s.top(); cout<<cur->data<<" "; s.pop(); cur = cur->right; } } } 遍历结果为:4 2 7 5 8 1 3 6 后序遍历方法一(非递归) 后序遍历相对来说显得更加复杂了。在前序和中序遍历中,只要左子树处理完毕实际上栈顶元素就可以出栈了,但后序遍历需要把左子树和右子树都处理完毕才能出栈,显然我们需要某种方法记录遍历的过程。 实际上我们只需要记录下遍历的前一个结点就能解决问题,因为通过前一个结点我们可以做如下判断: 如果前一个结点是当前结点的右子树,那么说明右子树已经遍历完毕可以出栈了 如果前一个结点是当前结点的左子树而且当前结点没有右子树,那么说明可以出栈了 如果当前结点即没有左子树也没有右子树,即为叶子结点,那么说明可以出栈了 若不属于上述情况,则依次将当前结点的右孩子和做孩子入栈,这样就能保证每次取栈顶元素时,左孩子都在右孩子前面被访问,左孩子和右孩子都在父结点前面被访问。 // 后序遍历 左右根 void post_order_traversal(node *root) { stack<node *> s; node *pre = NULL; node *cur = root; s.push(cur); while(!s.empty()) { cur = s.top(); // 叶子结点 if((!cur->left && !cur->right) // 叶子结点 || pre == cur->right // 前一个结点为当前结点右子树 || (pre == cur->left && !cur->right)) { // 前一个结点为当前结点左子树,且没有右子树 cout<<cur->data<<" "; pre = cur; s.pop(); } else { if(cur->right) s.push(cur->right); if(cur->left) s.push(cur->left); } } } 遍历结果为:4 7 8 5 2 6 3 1 后序遍历方法二(非递归) 后序遍历的顺序是左右根,如果把这个顺序倒过来就是根右左,是不是发现和前序遍历很像?那么我只需要按照根右左的方式遍历完,然后将遍历结果掉一个个儿就可以,而栈就具备掉个儿的功能,因此可写出如下代码。 // 后序遍历 左右根 void post_order_traversal(node *root) { stack<node *> s; stack<int> ans; node *cur = root; while(cur || !s.empty()) { // 将左子树全部入栈 while(cur) { ans.push(cur->data); s.push(cur); cur = cur->right; } if(!s.empty()) { cur = s.top(); s.pop(); cur = cur->left; } } while(!ans.empty()) { cout<<ans.top()<<" "; ans.pop(); } } 遍历结果为:4 7 8 5 2 6 3 1 层序遍历 层序遍历即广度优先遍历,使用队列即可实现。 // 层序遍历 void breadth_first_order_traversal(node *root) { queue<node *> q; q.push(root); while(!q.empty()){ node *cur = q.front(); q.pop(); if(cur){ cout<<cur->data<<" "; q.push(cur->left); q.push(cur->right); } } } 遍历结果为:1 2 3 4 5 6 7 8
Read More ~

动态规划实例——01 背包详解

题目描述 有 n 件物品,每件物品有一个重量和一个价值,分别记为 w1,w2,…,wn 和 c1,c2,…,cn。现在有一个背包,其容量为 wk,要从 n 件物品种任取若干件。要求:(1)重量之和小于或等于 wk;(2)价值之和最大。 输入: 共 3 行,第一行 2 个整数,表示 n 和 wk;第二行 n 个整数表示每一个物品的重量,第三行 n 个整数表示每一个物品的价值。 输出: 一行一个整数,表示符合背包容量的最大价值。 样例: 8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62 暴力枚举 我们以只有 A、B、C 三件物品的情况为例,对于每一个物品都存在拿和不拿两种情况。以0表示不拿当前物品,以1表示拿当前物品,可以有如下分析结果。 可能上面的图看起来不够清晰,我们从左至右逐一列举出来观察,一眼就可以看出来规律。其实就是十进制的 0、1、2、3、4、......可枚举的最大值即 2n-1。 000 001 010 011 100 101 110 111 根据上面的分析,我们可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int main() { int n, wk; int w[10000], c[10000]; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int ans = 0; int max_val = 1 << n; // 逐一枚举 for(int i = 0; i < max_val; i++){ int ww = 0, cc = 0; int index = 0; // 转二进制 int cur = i; while(cur){ int bit = cur % 2; // 若拿第 index 个物品,则累加其重量和价值 if(bit){ ww += w[index]; cc += c[index]; } cur = cur >> 1; index++; } //计算最大值 if(ww <= wk && ans < cc){ ans = cc; } } //输出最大值 cout<<ans<<endl; } 递归求解 我们把背包容量为wk,有n个物品可以选择的问题表示为slove(wk, n)。那么在背包剩余容量可以装下第 n 个物品时,该问题可以表示为求如下两个问题的最大值 选第 n 个物品:c[n-1] + slove(wk-w[n-1], n-1) 不选第 n 个物品:slove(wk, n-1) 在背包剩余容量无法装下第 n 个物品时,问题直接变为 不选第 n 个物品:slove(wk, n-1) 可以发现上述三个子问题可以继续向下拆分为规模更小,但类型一致的子子问题。于是可以写出如下递归求解代码。 #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; // wk 背包剩余重量 // ch 可选项 int slove(int wk, int ch) { if(wk <= 0 || ch <= 0){ return 0; } // 若背包剩余容量无法装下 w[ch-1],则直接丢弃第 ch 个物品 if(w[ch-1] > wk){ return slove(wk, ch-1); } // 若背包剩余容量能装下 w[ch-1],则计算装和不装的最大值 int a = c[ch-1] + slove(wk-w[ch-1],ch-1); int b = slove(wk, ch-1); return a > b ? a : b; } int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } cout<<slove(wk, n); } 动态规划 递归在执行过程中会存在重复计算相同子问题的情况,我们可以将其改为用循环实现,即动态规划的写法。dp[i][j]的含义即为:在背包容量为i,可选物品数量为j的情况下,符合背包容量的最大值。具体代码如下所示: #include<bits/stdc++.h> using namespace std; int w[30]={0}, c[30]={0}; int main() { int n, wk; cin>>n>>wk; for(int i = 0; i < n; i++){ cin>>w[i]; } for(int i = 0; i < n; i++){ cin>>c[i]; } int dp[1000001][21] = { 0 }; for(int i = 1; i <= wk; i++) { for(int j = 1; j <= n; j++) { // 若背包剩余容量无法装下 w[j-1],则直接丢弃第 j 个物品 if(w[j-1] > i) { dp[i][j] = dp[i][j-1]; } else { // 若背包剩余容量能装下 w[j-1],则计算装和不装的最大值 int a = c[j-1] + dp[i-w[j-1]][j-1]; int b = dp[i][j-1]; dp[i][j] = a > b ? a : b; } } } cout<<dp[wk][n]; }
Read More ~

Oracle 安装及 Spring 使用 Oracle

参考内容: docker安装oracle数据库史上最全步骤(带图文) Mac下oracle数据库客户端 Docker安装Oracle docker能安装oracle吗 Batch script for add a auto-increased primary key for exist table with records Docker 安装 Oracle11g 注意:下列安装方式仅适用于x86架构服务器,不适用于arm架构服务器。 # 拉取 oracle11,镜像有点大,需要花一些时间 docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11g # 查看镜像是否拉取成功 docker images # 给镜像重新打 tag,原来的名字太长了 docker tag registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11g oracle11g:latest # 启动 oracle11g 容器 docker run --name=oracle11g -itd -p 1521:1521 # 进入容器进行配置 docker exec -it oracle11g /bin/bash # 切换到 root 用户,密码为:helowin su root # 编辑配置文件 编辑/etc/profile,在其中增加如下内容: export ORACLE_HOME=/home/oracle/app/oracle/product/11.2.0/dbhome_2 export ORACLE_SID=helowin export PATH=$ORACLE_HOME/bin:$PATH 编辑完成后,需要刷新上述环境变量才能使用。 # 刷新环境变量 source /etc/profile # 创建软链接 ln -s $ORACLE_HOME/bin/sqlplus /usr/bin # 切换到 oracle 用户 su - oracle # 登陆 sqlplus sqlplus /nolog conn /as sysdba # 修改 system 用户密码 alter user system identified by system; # 修改 sys 用户密码 alter user sys identified by system; # 创建内部管理员账号 create user test identified by test; # 将 dba 权限授权给内部管理员账号和密码 grant connect,resource,dba to test; # 修改密码规则策略为密码永不过期 ALTER PROFILE DEFAULT LIMIT PASSWORD_LIFE_TIME UNLIMITED; # 修改数据库最大连接数据 alter system set processes=1000 scope=spfile; 修改上述信息后,需要重新启动数据库才会生效。 conn /as sysdba # 关闭数据库 shutdown immediate; # 启动数据库 startup; # 退出软链接 exit; 客户端连接 Oracle 以 Navicat 客户端为例,新建连接时按下图方式填写连接信息即可,密码即为system。需要注意的是,在 Windows 下选择 SID 或是服务名均可连接成功,但是在 Mac 下需要选择 SID 方式才能连接成功。 Oracle 实现主键自增 Oracle 在创建表的时候,不能像 MySQL 那样选择主键直接自增,但是我们可以通过给表创建序列和触发器去实现自增。下文以创建 USER 表为例。 -- 删除原有 USER 表 DROP TABLE "TEST"."USER"; -- 创建 USER 表 CREATE TABLE "TEST"."USER" ( "id" NUMBER NOT NULL, "gmt_create" DATE NOT NULL, "gmt_modified" DATE NOT NULL, "is_deleted" NUMBER NOT NULL, "login" NVARCHAR2(255) NOT NULL, "passwd" NVARCHAR2(255) NOT NULL, "nick" NVARCHAR2(255) NOT NULL, "phone" NVARCHAR2(255), "head_img" NVARCHAR2(255), "status" NVARCHAR2(255), "remark" NCLOB ); -- 删除原有序列 DROP SEQUENCE "TEST"."USER_SEQ"; -- 创建 USER_SEQ 序列,最小值为 1 CREATE SEQUENCE "TEST"."USER_SEQ" -- 最小值为 1 MINVALUE 1 -- 最大值为 9999999999999999999999999999 MAXVALUE 9999999999999999999999999999 -- 每次增加 1 INCREMENT BY 1 -- 将 20 个序列值放入缓存 CACHE 20; -- 创建触发器 CREATE TRIGGER "TEST"."USER_TRIGGER" -- 在插入数据前执行 BEFORE INSERT ON "TEST"."USER" -- 命名老数据为 OLD,新数据为 NEW REFERENCING OLD AS "OLD" NEW AS "NEW" -- 针对表的每一行都执行触发器 FOR EACH ROW -- 将序列值赋值给 id BEGIN :NEW."id" := USER_SEQ.NEXTVAL; END; / 需要注意的是,上面的/符号不能少。执行插入语句时可以发现,id会自动增加。 INSERT INTO "TEST"."USER" ("gmt_create", "gmt_modified", "is_deleted", "login", "passwd", "nick", "phone", "head_img", "status", "remark") VALUES (TO_DATE('2023-04-01 00:00:00', 'SYYYY-MM-DD HH24:MI:SS'), TO_DATE('2023-04-01 17:04:30', 'SYYYY-MM-DD HH24:MI:SS'), '0', 'user', '123', 'Jack', '1111', 'head.jpg', '激活', '测试'); Java Spring+Mybatis 使用 Oracle 及配置分页 application.properties文件配置信息: # mybatis spring.datasource.driver-class-name=oracle.jdbc.driver.OracleDriver spring.datasource.url=jdbc:oracle:thin:@8127.0.0.1:1521:helowin spring.datasource.username=system spring.datasource.password=system mybatis.mapper-locations=classpath*:mybatis/*.xml mybatis.configuration.log-impl=org.apache.ibatis.logging.stdout.StdOutImpl # pageHelper pagehelper.helperDialect=oracle pagehelper.reasonable=true pagehelper.supportMethodsArguments=true pagehelper.params=count=countSql pom.xml配置文件关键信息。 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd"> <properties> <java.version>1.8</java.version> <maven.compiler.target>1.8</maven.compiler.target> <maven.compiler.source>1.8</maven.compiler.source> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding> <spring.boot-version>2.1.3.RELEASE</spring.boot-version> </properties> <dependencyManagement> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-dependencies</artifactId> <version>${spring.boot-version}</version> <type>pom</type> <scope>import</scope> </dependency> <dependency> <groupId>org.mybatis.spring.boot</groupId> <artifactId>mybatis-spring-boot-starter</artifactId> <version>2.1.0</version> </dependency> <dependency> <groupId>com.oracle.ojdbc</groupId> <artifactId>ojdbc8</artifactId> <version>19.3.0.0</version> </dependency> <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.4.3</version> </dependency> <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> </dependency> </dependencies> </dependencyManagement> </project>
Read More ~

动态规划实例——换零钱的方法数(C++详解版)

原写了 Java 版本的如何求解换钱的方法数,近期进行了一些细节上的补充,以及部分错误更正,将语言换为了 C++ 语言。 基础题目 假设你现在拥有不限量的 1 元、5 元、10 元面值纸币,路人甲希望找你换一些零钱,路人甲拿出的是一张 100 元面值的纸币,试求总共有多少种换零钱的方法? 分析:因为总共只有 3 种面值小额纸币,所以将所有可能进行枚举,直接暴力解决即可。 #include<bits/stdc++.h> using namespace std; int slove() { int ans = 0; // 10 元张数 for(int i = 0; i <= 10; i++) { // 5 元张数 for(int j = 0; j <= 20; j++) { // 1 元张数 for(int k = 0; k <= 100; k++) { int cur = i*10 + j*5 + k*1; if(cur == 100) { ans++; } } } } return ans; } int main() { cout<<slove(); } 递归求解 基础题目中是拥有固定种类的小额纸币,即使再多几种小额纸币也没关系,大不了在嵌套几个循环就能解决。现在需要将题目的难度加大一点,改为小额纸币的种类和需要换零钱的总额由用户输入,即小额纸币种类和总额都不在固定,那么如何解决? 输入共有三行: 第一行:小额纸币种类数量 第二行:不同小额纸币的面值 第三行:需要换零钱的总额 分析:虽然现在种类和总额都是变量了,但是上文中的基础版本还是被包含在此问题中,所以我们还是以上文中的 1 元、5 元、10 元换 100 元进行分析,找一找除了枚举是否还有其他方法解决。 我们先固定一种零钱的数量,剩下的钱用剩余零钱去兑换,即: 用 0 张 1 元换,剩下的用 5、10 元换,最终方法数为 count0; 用 1 张 1 元换,剩下的用 5、10 元换,最终方法数为 count1; ...... 用 100 张 1 元换,剩下的用 5、10 元换,最终方法数为 count100; 那么最终换钱的方法综述即为count0 + count1 + count2 + ... + count100。 上面的分析中,我们把原来的大问题拆为了 101 个小问题,且每一个小问题都有很相似的地方,即: 求用 5、10 元换 100 元的方法数 求用 5、10 元换 95 元的方法数 ...... 求用 5、10 元换 0 元的方法数 如果我们对这 101 个小问题再进行同样思路的分析,即再固定 5 元零钱的数量,那么就能把问题划分成了规模更小,但问题类型一样的小小问题。即递归的思路,可以写出如下代码。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // index 表示上文分析中的当前固定第几张 // target 表示现在要兑换的钱的总额 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); ans = ans + slove(index+1, cur_total); } } return ans; } int main() { int target; cin>>len; // 零钱种类 for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; // 兑换总额 cout<<slove(0, target); } 优化递归 可以发现上文所写的递归代码存在大量的重复过程,比如下面两种情况,后面所求的子问题是完全一样的,导致程序运行时间的浪费。 已经使用了 5 张 1 元、0 张 5 元,剩下的 95 元用 5 元和 10 元兑换 已经使用了 0 张 1 元、1 张 5 元,剩下的 95 元用 5 元 和 10 元兑换 既然前面已经求解过相同的子问题了,那么我们是否可以在第一次求解的时候,将计算结果保存下来,这样下次遇到相同子问题的实际,直接查出来用就可以,省去再次求解的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // 用于存储子问题的解 int val_map[1000][1000] = { 0 }; // 0 表示该子问题没有算过 // -1 表示算过,但该子问题无解 // 其它值,即此子问题的方法数 int slove(int index, int target) { int ans = 0; if(index == len) { ans = target == 0 ? 1 : 0; } else { for(int i = 0; i*money[index] <= target; i++) { // 剩余待换零钱的总额 int cur_total = target-(i * money[index]); int pre_val = val_map[index+1][cur_total]; // 如果 val 为 0,说明该子问题没有被计算过 if(pre_val == 0) { ans = ans + slove(index+1, cur_total); } else { ans += pre_val == -1 ? 0 : pre_val; } } } // 存储计算结果 val_map[index][target] = ans == 0 ? -1 : ans; return ans; } int main() { int target; // 零钱种类 cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(0, target); } 动态规划 上面对递归的优化方案已经能看出来动态规划的影子了,沿着前文先计算再查表的思路继续思考,我们能否提前把所有子问题都计算出答案,对每个子问题都进行查表解决。也即将最初的递归方案改为循环的实现。 所有的递归都能改为循环实现 #include<bits/stdc++.h> using namespace std; int money[1000]; // money 表示所有小额纸币的面值 int len; // len 表示 money 数组的长度,即:小额纸币种类 // 用于存储子问题的解 // val_map[i][j] 表示用 money[0...i] 的小面额零钱组成 j 元的方法数 int val_map[1000][1000] = { 0 }; int slove(int target) { // 第一列表示组成 0 元的方法数,所以为 1 for (int i = 0; i < len; i++) { val_map[i][0] = 1; } // 第一行表示只使用 money[0] 一种钱币兑换钱数为i的方法数 // 所以是 money[0] 的倍数的位置为 1,否则为 0 for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { for (int k = 0; j >= money[i]*k; k++) { /* val_map[i][j] 的值为: 用 money[0...i-1] 的零钱组成 j 减去 money[i] 的倍数的方法数 因为相比 val_map[i-1][j],只是多了一种零钱的可选项 */ val_map[i][j] += val_map[i-1][j-money[i]*k]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 动归优化 在上文第一版动态规划代码的优化中已经能发现,其实val_map[i][j]的值由两部分组成,分别为: 用 money[0...i-1] 的零钱组成换 j 元的方法数 用 money[0...i-1] 的零钱换 j-money[i]*k(k=1,1,2,3....)元的方法数之和 对于第二种情况来说,其累加值实际上就是val_map[i][j-money[i]],即用money[0...i]的零钱换 j-money[i]元的方法数。至于具体为什么累加值与val_map[i][j-money[i]]相等,我们可以借助递归方法时的分析方式进行理解。 用 money[0...i-1] 的零钱组成换 j 元的方法数对应: 用 0 张 money[i] 换,剩下的用 money[0...i-1] 换 用 money[0...i-1] 的零钱换 j-money[i]*k(k=1,1,2,3....)元的方法数之和对应: 用 1 张 money[i] 换,剩下的用 money[0...i-1] 换 用 2 张 money[i] 换,剩下的用 money[0...i-1] 换 ...... 所以第二部分的值即为val_map[i][j-money[i]]。依据此处的分析,我们可以在原有基础上去掉第三层循环,减少程序运行所花费的时间。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000][1000] = { 0 }; int slove(int target) { for (int i = 0; i < len; i++) { val_map[i][0] = 1; } for (int i = 1; money[0]*i <= target; i++) { val_map[0][money[0]*i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { val_map[i][j] = val_map[i-1][j]; // 此处需要比较 j 的大小,防止数组越界 // 注意条件时 >= ,否则少计算 j 刚好为 money[i] 的情况 if(j >= money[i]) { val_map[i][j] += val_map[i][j-money[i]]; } } } return val_map[len-1][target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); } 空间压缩 仔细观察能发现,每一次更新val_map[i][j]的值时,它只依赖于上一行和当前这一行前面的元素。对于我们所求解的问题来说,它仅要求我们给出最终的答案即可,那么前面存储中间结果的那些元素实际上就会空间的浪费,因此我们可以思考一下如何在空间上进行压缩。 实际上我们只需要定义一个一维的数组,采用一些技巧对该数组进行滚动更新,按照合适的方向去更新数组,同样可以达到上面使用二维数组的效果。 #include<bits/stdc++.h> using namespace std; int money[1000]; int len; int val_map[1000] = { 0 }; int slove(int target) { // 第一行,只用 money[0] 换零钱 // 所以只能换 money[0] 倍数的钱 for (int i = 0; money[0]*i <= target; i++) { val_map[money[0] * i] = 1; } for (int i = 1; i < len; i++) { for (int j = 1; j <= target; j++) { if(j >= money[i]) { // 在进行下面一步前 val_map[j] 的值就已经是 val_map[i-1][j] 了 val_map[j] += val_map[j-money[i]]; } } } return val_map[target]; } int main() { int target; cin>>len; for(int i = 0; i < len; i++){ cin>>money[i]; } cin>>target; cout<<slove(target); }
Read More ~

linux-5.10.157 内核源码编译

参考内容: Linux内核开发_1_编译LInux内核 编译linux内核报错:flex: not foundscripts 编译kernel5.14报错fatal error: openssl/opensslv.h 编译内核错误——*** 没有规则可制作目标“debian/canonical-certs.pem” 内核错误:BTF: .tmp_vmlinux.btf: pahole (pahole) is not available # 切换到 root 账户 sudo su # 查看操作系统版本 cat /etc/issue # 查看 Linux 内核版本 cat /proc/version # 进入 root 账户目录 cd /home/root # 下载 Linux 内核源码 wget https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.10.157.tar.xz # Linux 其它版本源码 https://www.kernel.org/ # xz 解压 xz -d linux-5.10.157.tar.xz # tar 解压到 /usr/src/linux-5.10.157 目录下 tar -xf linux-5.10.157.tar -C /usr/src/. # 进入源码目录 cd /usr/src/linux-5.10.157 # 查看源码结构 tree . -L 2 # 若没有 tree 命令,可以执行下面命令 # apt-get install tree # 配置编译选项 make menuconfig # 若没有 make,可以执行下面命令 # apt-get install make # 若执行 make 后报错找不到 curses.h,可以执行下面命令 # apt-get install libncurses5-dev # 若报错找不到 flex not found,可以执行下面两条命令 # apt-get install flex # apt-get install bison # 再次运行 make menuconfig 弹出图形化配置页面后 # 若使用默认配置,则直接按两次 Esc 键退出即可 # 此时会在当前目录下生成 .config 文件 # 编译 Linux 源码 make bzImage -j4 # 在编译过程中若报错 fatal error: openssl/opensslv.h,可执行下面命令 # apt-get install libssl-dev # 若还出现同样的问题,可参考 https://blog.csdn.net/ComputerInBook/article/details/107380796 源码编译安装 openssl # 若出现「没有规则可制作目标“debian/canonical-certs.pem”」报错 # 需要删除 .config 中相应的字段,总共有两处 # 一处为 CONFIG_SYSTEM_TRUSTED_KEYS="debian/canonical-certs.pem" # 一处为 CONFIG_SYSTEM_REVOCATION_KEYS="debian/canonical-revoked-certs.pem" vim .config # 删除之后的样子如下(需要保留引号): # 一处为 CONFIG_SYSTEM_TRUSTED_KEYS="" # 一处为 CONFIG_SYSTEM_REVOCATION_KEYS="" # 若出现 BTF: .tmp_vmlinux.btf: pahole (pahole) is not available 错误,则执行下面命令 # apt-get install dwarves # 若在过程中还出现其它问题,大多是因为缺少相关库导致的,直接用 apt-get install 即可
Read More ~

预处理器

C 语言的编译需要经过很多步骤,其中第一个步骤称为预处理阶段。这个阶段的主要任务包括删除注释、插入被#include指令包含的文件的内容、定义和替换#define指令定义的符号以及确定代码的部分内容是否应该跟绝一些条件编译指令进行编译。 #define #define指令就是为数值命名一个符号。比如#define name stuff指令,有了它之后,每当有符号name出现在这条指令后面时,预处理器就会把它替换成stuff,比如下面几个例子: // 为关键字 register 创建了一个简短的别名 #define reg register // 声明了一个更具描述性的符号用来替代实现无限循环的 for 语句 #define do_forever for(;;) // 定义了一个简短记法,在 switch 语句中使用,可以自动把一个 break 放在每个 case 之前 #define CASE break;case 当然如果定义中的stuff非常长,那么也可以将它分成几行,除了最后一行之外,每行的末尾都需要加一个反斜杠。比如: #define log_debug printf("File[%s]line[%d]:" \ " x=[%d], y=[%d], z=[%d]", \ __FILE__, __LINE__, \ x, y, z) // 那么我们将可以很方便的插入一条调试语句打印 x *= 2; y += x; z = x * y; log_debug; 很容易就发现上面的log_debug定义无法进行泛化,当然设计者也考虑到了这个问题,所以#define机制包括了一个规定,即允许把参数替换到文本中,这种实现一般称为宏,其声明方式如下: define name(parameter-list) stuff 需要注意的是parameter-list是一个由逗号分隔的符号列表,他们可能出现在stuff中。参数列表的左括号必须与name紧邻,如果两者之间有任何空白存在,参数列表就会被解释为stuff的一部分。下面我们看一个具体的列子,以此了解宏定义的机制,并将它逐步优化改进: #define SQUARE(x) x * x // 使用 SQUARE(5) // 效果:5 * 5 考虑一下下面的代码段: a = 5; printf("%d\n", SQUARE(a + 1)); 乍一看觉得这段代码将打印36这个值。但实际它却会打印11,我们仔细观察一下被替换的宏文本,即参数x被文本a + 1替换: a = 5; printf("%d\n", a + 1 * a + 1); 很容易想到对参数 x 加一个括号解决上述问题,即: #define SQUARE(x) (x) * (x) // 上述打印将会被替换为 a = 5; printf("%d\n", (a + 1) * (a + 1)); 类似的我们可以再定义一个DOUBLE宏,即: #define DOUBLE(x) (x) + (x) 但是考虑下面的使用方式: a = 5; printf("%d\n", 10 * DOUBLE(5)); 看上去它应该打印的结果是100,但事实上它打印的是55,我们再通过宏替换产生的文本观察问题: printf("%d\n", 10 * (5) + (5)); 所以我们需要在整个表达式两边加上一对括号。所有用于对数值表达式进行求值的宏定义都应该使用下面这种方式加上括号,避免在使用宏时,由于参数中的操作符或邻近的操作符之间不可预料的相互作用。 #define DOUBLE(x) ((x) + (x)) 宏与函数 宏非常频繁的用于执行简单的计算,比如在两个表达式中寻找其中较大(小)的一个: #define MAX(a, b) ((a) > (b) ? (a) : (b)) 那么为什么不使用函数来完成这个任务呢?首先用于调用和从函数返回的代码很可能比实际执行这个小型计算工作的代码更大,所以使用宏比使用函数在程序的规模和速度方面都更胜一筹。 更为重要的是函数必须声明为一种特定的类型,所以它只能在类型合适的表达式上使用。但是上面的这个宏可以用于整型、长整型、单浮点型、双浮点型以及任何其它可以使用>操作符比较值大小的类型,即宏与类型无关。 当然宏也有它的不利之处,因为每次在使用宏时,一份宏定义代码的拷贝都将插入到程序中,除非宏的定义非常短,否则使用宏将会大幅增加程序的长度。 也有一些任务根本无法使用函数实现,比如下面这个宏的第二个参数是一种类型,它无法作为函数参数进行传递。 #define MALLOC(n, type) ((type *)malloc((n) * sizeof(type))) 当宏参数在宏定义中出现的次数超过一次时,如果这个参数具有副作用,那么当使用这个宏的时候就可能出现危险,导致一些不可预料的后果。比如x++就是一个具有副作用的表达式,它会改变x的值,直接会导致下面的代码段出现不可预知的后果: #define MAX(a, b) ((a) > (b) > (a) : (b)) x = 5; y = 8; z = MAX(x++, y++); // z = ((x++) > (y++) > (x++) : (y++)) 属性 #define 宏 函数 代码长度 每次使用时,宏代码都被插入到程序中。除了非常小的宏志伟,程序的长度将大幅度增长 函数代码只出现于一个地方,每次使用这个函数时,都调用那个地方的同一份代码 执行速度 更快 存在函数调用/返回的额外开销 操作符优先级 宏参数的求值是在所有周围表达式的上下文环境里,除非它们加上括号,否则邻近操作符的优先级可能回产生不可预料的结果 函数参数只在函数调用时求值一次,它的结果传递给参数。表达式的求值结果更容易预测 参数求值 参数每次用于宏定义时,它们都将重新求值。由于多次求值,具有副作用的参数可能会产生不可预料的结果 参数在函数被调用前求值一次。在函数中多次使用参数并不会导致多种求值过程。参数的副作用不会造成任何特殊的问题 参数类型 宏与类型无关。只要对参数的操作是合法的,它可以使用于任何参数类型 函数的参数是与类型有关的。如果参数的类型不同,就需要使用不同的函数,即使它们执行的任务时相同的 文件包含 我们知道#include指令可以使另一个文件的内容被编译,就像它实际出现于#include指令出现的位置一样。这种替换的执行方式很简单:预处理器删除这条指令,并用包含头文件的内容取而代之。这样一个头文件如果被包含到 10 个源文件中,它实际上被编译了 10 次。 基于这种替换的方式,当出现嵌套#include文件被多次包含时,就会出现问题: #include "a.h" #include "b.h" // 如果 a.h 和 b.h 中都包含一个 #include x.h // 那么 x.h 在此处就出现了两次 这种多重包含在绝大多数情况下出现于大型程序中,它往往需要很多头文件,所以要发现这种情况并不容易。但是我们可以使用条件编译来解决这个问题: #ifndef _HEADER_NAME_H_ #define _HEADER_NAME_H_ /* * All the stuff that you want in the header file */ #endif
Read More ~

C 语言拾遗

约定:本文所说的标准均为 ANSI (C89) 标准 三字母词 标准定义了几个三字母词,三字母词就是三个字符的序列,合起来表示另一个字符。三字母词使得 C 环境可以在某些缺少一些必需字符的字符集上实现,它使用两个问号开头再尾随一个字符,这种形式一般不会出现在其它表达形式中,这样就不容易引起误解了,下面是一些三字母词的对应关系: ??( [ ??) ] ??! | ??< { ??> } ??' ^ ??= # ??/ \ ??- ~ 所以在一些特殊情况下可能出现下面的情况,希望你不要被意外到。 printf("Delete file (are you really sure??): "); // result is: Delete file (are you really sure]: 字符 直接操作字符会降低代码的可移植性,应该尽可能使用库函数完成。比如下面的代码试图测试ch是否为一个大写字符,它在使用ASCII字符集的机器上能够运行,但是在使用EBCDIC字符集的机器上将会失败。 if( ch >= 'A' && ch <= 'Z') 使用if(isupper(ch))语句则能保证无论在哪种机器上都能正常运行。 字符串比较 库函数提供了int strcmp(const char *s1, const char *s2)函数用于比较两个字符串是否相等,需要注意的是在标准中并没有规定用于提示不相等的具体值。它只是说如果第 1 个字符串大于第 2 个字符串就返回一个大于零的值,如果第 1 个字符串小于第 2 个字符串就返回一个小于零的值。一个常见的错误是以为返回值是1和-1,分别代表大于和小于。 初学者常常会编写下面的表达式。认为如果两个字符串相等,那么它返回的结果将为真。但是这个结果恰好相反,两个字符串相等的情况下返回值是零(假)。 if(strcmp(a, b)) strlen strlen的返回值是一个size_t类型的值,这个类型是在头文件stddef.h中定义的,它是一个无符号整数类型,所以会导致下面表达式的条件永远为真。 if(strlen(x) - strlen(y) >= 0) { // do something } 第二点需要注意的是strlen的返回值没有计算\0的长度,所以下面的代码在一些检查严格或老版本的编译器中会报错,其原因在于少分配了一个存储单位。 // 假设 str 是一个字符串 char *cpy = malloc(strlen(str)); strcpy(cpy, str); // 正确写法应为 char *cpy = malloc(strlen(str) + 1); strcpy(cpy, str); 赋值截断 表达式a = x = y + 3;中x和a被赋予相同值的说法是错误的,因为如果x是一个字符型变量,那么y+3的值就会被截去一段,以便容纳于字符型的变量中,那么a所赋的值就是这个被截短后的值。下面也是一个非常常见的错误。 char ch; // do something while((ch = getchar()) != EOF) { // do something } EOF所需要的位数比字符型值所能提供的位数要多,这也是getchar返回一个整型值而不是字符值的原因。例子中把getchar的返回值存储于字符型变量会导致被截短,然后再把这个被截短的值提升为整型与EOF进行比较,在某些机器的特定场景下就会导致问题。比如在使用有符号字符集的机器上,如果读取了一个的值为\377的字节,上述循环就将终止,因为这个值截短再提升之后与EOF相等。而当这段代码在使用无符号字符集的机器上运行时,这个循环将永远不会终止。 指针与数组 因为数组和指针都具有指针值,都可以进行间接访问和下标操作,所以很多同学都想当然的将它们认为是一样的,为了说明它们是不相等的,我们可以考虑下面的两个声明: int a[5]; int *b; 声明一个数组时,编译器将根据声明所指定的元素数量为数组保留空间,然后再创建数组名,它的值是一个常量,指向这段空间的起始位置。声明一个指针变量时,编译器只为指针本身保留内存空间,它并不为任何整型值分配内存空间。而且,指针变量并未被初始化为任何指向现有的内存空间。所以在上述声明之后,表达式*a是完全合法的,但是表达式*b将访问内存中某个不确定的位置,或者导致程序终止。 硬件操作 我们知道其实表示就是内存中一个地址,所以理论上*100 = 25是一种可行的操作,即让内存中位置为100的地方存储25。但实际上这条语句是非法的,因为字面值100的类型是整型,而间接访问操作只能用于指针类型表达式,所以合法的写法必须使用强制转换,即*(int *)100 = 25。 需要说明的是使用这种技巧的机会是绝无仅有的,只有偶尔需要通过地址访问内存中某个特定的位置才可使用,它并不是访问某个变量,而是访问硬件本身。比如在某些机器上,操作系统需要与输入输出设备控制器通信,启动 I/O 操作并从前面的操作中获得结果,此时这些地址是预先已知的。 += 与 ?: 操作符 我们在这里讨论一下+=操作符,它的用法为a += expr,读作把 expr 加到 a,其实际功能相当于表达式a = a + expr的作用,唯一不同的是+=操作符的左操作数a只会求值一次。可能到目前为止没有感觉到设计两种增加一个变量值的方法有什么意义?下面给出代码示例: // 形式 1 a[ 2 * (y - 6*f(x)) ] = a[ 2 * (y - 6*f(x)) ] + 1; // 形式 2 a[ 2 * (y - 6*f(x)) ] += 1; 在第一种形式中,用于选择增值位置的表达式必须书写两次,一次在赋值号左边,一次在赋值号右边。由于编译器无法知道函数f是否具有副作用,所以它必须两次计算下标表达式的值,而第二种形式的效率会更高,因为下标表达式的值只会被计算一次。同时第二种形式也减少了代码书写错误的概率。 同理三目运算符也可以起到类似的效果。 // 形式 1 if(a > 5) { b[ 2 * c + d * (e / 5) ] = 3; } else { b[ 2 * c + d * (e / 5) ] = -20; } // 形式 2 b[ 2 * c + d * (e / 5) ] = a > 5 ? 3 : -20; 逗号操作符 逗号操作符可以将多个表达式分隔开来。这些表达式自左向右逐个进行求值,整个表达式的值就是最后那个表达式的值。例如: if(b + 1, c / 2, d > 0) { // do something} 当然,正常人不会编写这样的代码,因为对前两个表达式的求值毫无意义,它们的值只是被简单的丢弃了。但是我们可以看看下面的代码: // 形式 1 a = get_value(); count_value(a); while(a > 0) { // do something a = get_value(); count_value(a); } // 形式 2 while(a = get_value(), count_value(), a > 0) { // do something } 指针 int* a, b, c; 人们会很自然的认为上述语句是把所有三个变量都声明为指向整型的指针,但事实上并非如此,星号实际上只是表达式*a的一部分,只对这个标识符有作用。如果要声明三个指针,那么应该使用下面的形式进行初始化。 int *a, *b, *c; 在声明指针变量时可以为它指定初始值,比如下面的代码段,它声明了一个指针,并用一个字符串常量对其进行初始化。 char *msg = "Hello World!"; 需要注意的是,这种类型的声明会让人很容易误解它的意思,看起来初始值似乎是赋给表达式*msg的,但实际上它是赋值给msg本身的,也就是上述声明实际形式如下: char *msg; msg = "Hello World!"; 指针常量: int *pi中pi是一个普通的指向整型的指针, 而变量int const *pci则是一个指向整型常量的指针,你可以修改指针的值,但是不能修改它所指向的值。相比之下int * const cpi则声明cpi为一个指向整型的常量指针。此时指针是常量,它的值无法修改,但是可以修改它所指向的整型的值。在int const * const cpci中,无论是指针本身还是它所指向的值都是常量,无法修改。 枚举类型 枚举(enumerated) 类型就是指它的的值为符号常量而不是字面值的类型,比如下面的语句声明了Jar_Type类型: enum Jar_Type { CUP, PINT, QUART, HALF_GALLON, GALLON }; 需要注意的是,枚举类型实际上是以整型方式存储的,代码段中的符号名实际上都是整型值。在这里CUP的值是0,PINT的值是1,依次类推。 在适当的时候,可以为这些符号名指定特定的值整型值。并且只对部分符号名进行赋值也是合法的,如果某个符号名没有显示的赋值,那么它的值就比前面一个符号名的值大 1。 enum Jar_Type { CUP = 8, PINT = 16, QUART = 32, HALF_GALLON = 64, GALLON = 128 }; 符号名被当作整型处理,这意味着可以把HALF_GALLON这样的值赋给任何整型变量,但是在编程活动中应该避免这种方式使用枚举,因为这样会削弱它们的含义。 typedef 与 define 在实际应用过程中应该使用typedef而不是#define来创建新的类型名,因为#define无法正确的处理指针类型,比如下面的代码段正确的声明了a,但是b却被声明为了一个字符。 #define ptr_to_char char * ptr_to_char a, b; 联合(union) 联合看起来很像结构体,与结构体不同的是联合的所有成员共用同一块内存,所以在同一时刻联合中的有效成员永远只有一个。我们可以看下面一个例子,当一个variable类型的变量被创建时,解释器就创建一个这样的结构并记录变量类型。然后根据变量类型,把变量的值存储在这三个值字段的其中一个。 struct variable { enum { INT, FLOAT, STRING } type; int int_val; float float_val; char *str_val; } 不难发现上述结构的低效之处在于它所使用的内存,每个variable结构存在两个未使用的值字段,造成了内存空间上的不少浪费。使用联合就可以减少这种空间上的浪费,它把这三个值字段的每一个都存储在同一个内存位置。我们知道这三个字段并不会冲突,因为每个变量只可能具有一种类型,所以在具体的某一时刻,联合的这几个字段只有一个被使用。 struct variable { enum { INT, FLOAT, STRING } type; union { int i; float f; char *s; } val; } 现在,对于整型变量,我们只需要将type字段设为INT,并把整型值存储于val.i即可。如果联合中各成员的长度不一样,联合的长度就是它最长成员的长度。 联合的变量也可以被初始化,但是这个初始值必须是联合第 1 个成员的类型,而且它必须位于一对花括号里面。比如: union { int a; float b; chat c[4]; } x = { 5 }; 结构体 在实际编程活动中,存在链表、二叉树等结点自引用的情况,那么结构体的自引用如何编写呢? struct node { int data; struct node next; } 上述写法是非法的,因为成员next是一个完整的结构,其内部还将包含自己的成员next,这第 2 个成员又是另一个完整结构,它还将包含自己的成员next,如此重复下去将永无止境。正确的自引用写法如下: struct node { int data; struct node *next; } 我们需要注意下面的这个陷阱: /* 错误写法:因为类型名 node_t 直到声明末尾才定义 所以在结构中声明的内部 node_t 尚未定义 */ typedef struct { int data; node_t *next; } node_t; // 正确写法 typedef struct node_tag { int data; struct node_tag *next; } node_t; 编译器在实际分配时会按照结构体成员列表的顺序一个接一个的分配内存,并且只有当存储成员需要满足正确的边界对齐要求时,成员之间可能会出现用于填充的额外内存空间。 ```c struct align { char a; int b; char c; } 如果某个机器的整型值长度为 4 个字节,并且它的起始存储位置必须能够被 4 整除,那么这个结构在内存中的存储将是下面这种形式 a b b b b c 我们可以通过改变成员列表的声明顺序,让那些对边界要求严格的成员首先出现,对边界要求弱的成员最后出现,这样可以减少因为边界对齐而带来的空间损失。 struct align { int b; char a; char c; } b b b b a c 当程序创建几百个甚至几千个结构时,减少内存浪费的要求就比程序的可读性更为急迫。我们可以使用sizeof操作符来得出一个结构的整体长度。如果必须要确定结构某个成员的实际位置,则可以使用offsetof(type, member)宏,例如: offset(struct align, b); 一句话 标识符:标识符就是变量、函数、类型等的名字,标识符的长度没有限制,但是 ANSI 标准允许编译器忽略第 31 个字符以后的字符,并且允许编译器对用于表示外部名字(由链接器操作的名字)的标识符进行限制,只识别前 6 位不区分大小写的字符。 注释:代码中所有的注释都会被预处理器拿掉,取而代之的是一个空格。因此,注释可以出现在任何空格可以出现的地方。 类型:C 语言中仅有 4 种基本数据类型,即整型、浮点型、指针和聚合类型(数组、结构等),所有其它的类型都是从这 4 中基本类型的某种组合派生而来。 类型长度:标准只规定了short int至少是 16 位,long int至少是 32 位,至于缺省的int是多少位则直接由编译器设计者决定。并且标准也没有规定这 2 个值必须不一样。如果某种机器的环境字长是 32 位,而且也没有什么指令能够更有效的处理更短的整型值,那它很可能把这 3 个整型值都设定为 32 位。 位域:基于 int 位域被当作有符号还是无符号数、位域成员的内存是从左向右还是从右向左分配、运行在 32 位整数的位域声明可能在 16 位机器无法运行等原因,注重可移植性的程序应该避免使用位域。 结构与指针:什么时候应该向函数传递一个结构而不是一个指向结构的指针呢?很少有这种情况。只有当一个结构特别小(长度和指针相同或更小)时,结构传递方案的效率才不会输给指针传递方案。
Read More ~

为什么宏定义要使用 do {...} while (0) ?

参考内容: do {…} while (0) in macros do {...} while (0) 在宏定义中的作用 do{}while(0)只执行一次无意义?你可能真的没理解 近期参与的项目属于嵌入式软件领域,自然而然就得用 C 语言进行开发,开发过程中发现引入的第三方库里面有一些奇奇怪怪的写法,比如大佬们都喜欢使用do {...} while(0)的宏定义,在 Stack Overflow 上也有人提出了这个问题。之前从事 Linux 内核开发的谷歌大佬 Robert Love 给出了如下的解释: do {…} while(0) is the only construct in C that lets you define macros that always work the same way, so that a semicolon after your macro always has the same effect, regardless of how the macro is used (with particularly emphasis on the issue of nesting the macro in an if without curly-brackets). do {...} while(0) 在 C 中是唯一的构造程序,让你定义的宏总是以相同的方式工作,这样不管怎么使用宏(尤其在没有用大括号包围调用宏的语句),宏后面的分号也是相同的效果。 这句话读起来有些拗口,只觉得大佬的表述曲高和寡,翻译翻译就是:使用do {...} while(0)构造后的宏定义不会受到大括号、分号等影响,总能按照我们期望的方式调用运行。下面我们举几个实际的例子来加深理解。 // 现有如下宏定义 #define foo(x) bar(x); baz(x) // 1. 可以这样调用 foo(wolf); // 上述调用将会被展开为下列代码,完美没有问题 bar(wolf); baz(wolf); // 2. 如果我们像下面这样调用呢? if (!feral) foo(wolf); // 上述调用将会被展开为下列代码,很明显这是错误的,并且是很容易犯的错误 if (!feral) bar(wolf); baz(wolf); 为了避免上面例子所出现的问题,我们可以考虑使用{ }直接把整个宏包裹起来,如下所示: // 修改宏定义为 #define foo(x) { bar(x); baz(x) } // 3. 例 1 调用 if (!feral) foo(wolf); // 现在上述调用将展开为下列代码 if (!feral) { bar(wolf); baz(wolf); }; // 4. 我们再考虑一下如下调用呢 if (!feral) foo(wolf); else bin(wolf); // 上述调用将会被展开为下列代码,很明显又出现了语法错误 if (!feral) { bar(wolf); baz(wolf); }; else bin(wolf); 我们继续考虑比使用{ }直接把整个宏包裹起来更好的方法,即本文标题所说的使用do {...} while (0),即上述宏将定义为如下形式。 // 终极版宏定义 #define foo(x) do { bar(x); baz(x) } while (0) // 5. 例 4 调用 if (!feral) foo(wolf); else bin(wolf); // 现在上述调用将展开为下列形式,很完美 if (!feral) do { bar(wolf); baz(wolf) } while (0); else bin(wolf); do {...} while (0)除了在宏定义中可以发挥完美的作用外,在某些情况下还可以当作goto使用。因为goto不符合软件工程的结构化,并且容易使得代码晦涩难懂,所以很多公司都不倡导使用甚至禁止使用。那么我们可以使用do {...} while (0)来做同样的事情。 #include <stdio.h> #include <stdlib.h> int main() { char *str; /* 最初的内存分配 */ str = (char *) malloc(15); if(str != NULL) goto loop; printf("hello world\n"); loop: printf("malloc success\n"); return 0; } 上述代码我们可以修改为下列形式,使用do {...} while (0)将函数主体包裹起来,而break语句则替代了goto语句的作用,并且代码的可读性与可维护性都比上述goto方式更好。 #include <stdio.h> #include <stdlib.h> int main() { do{ char *str; /* 最初的内存分配 */ str = (char *) malloc(15); if(str != NULL) break; printf("hello world\n"); }while(0); printf("malloc success\n"); return 0; }
Read More ~