C++算法
GESP-C++四级考试核心知识点与编程模板
GESP-C++ 四级考试的核心知识点与编程模板。涵盖指针、数组、结构体、函数、递推算法、排序算法、文件操作及异常处理等基础内容。提供了二维数组处理、结构体排序、最大连续子序列、矩阵处理、前缀和等多种常见题型的代码模板，并总结了算法复杂度与稳定性。适合考生考前快速复习与刷题参考。
GESP-C++ 四级考试的核心知识点与编程模板。涵盖指针、数组、结构体、函数、递推算法、排序算法、文件操作及异常处理等基础内容。提供了二维数组处理、结构体排序、最大连续子序列、矩阵处理、前缀和等多种常见题型的代码模板，并总结了算法复杂度与稳定性。适合考生考前快速复习与刷题参考。
（1）概念：指针是存储变量地址的变量。
（2）定义：
int a = 5; int* p = &a; // 定义指向 a 的指针
（3）解引用：
cout << *p; // 输出 a 的值 5
（4）注意事项
指针变量类型必须与所指向变量类型一致。空指针
nullptr，防止野指针。
（1）数组定义：
int a[3][4]; // 3行4列二维数组 int b[2][3][4]; // 三维数组
（2）索引访问：
a[1][2] = 10; // 给第二行第三列赋值
（1）定义与使用：
struct Student { string name; int age; double score; }; Student s1; s1.name = "Alice"; s1.age = 10;
（2）结构体数组：
Student s[10];
（3）结构体指针：
Student* p = &s1; cout << p->name;
（4）结构体嵌套结构体：
struct Date { int day, month, year; }; struct Person { string name; Date birthday; };
（5）结构体做函数参数：
void printStudent(const Student &s) { cout << s.name; }
（6）const 使用场景：
传递函数参数时防止修改原结构体。
(1) 声明与定义：
int add(int a, int b); // 声明 int add(int a, int b) { return a + b; } // 定义
(2) 调用：
int c = add(2,3);
(3) 形参 & 实参：
形参：函数定义中的变量 实参：调用函数时传入的值
(4) 变量作用域：
局部变量：函数内部定义，仅函数内有效 全局变量：函数外定义，全局可访问
(5) 参数传递方式：
// 值传递 void f(int x) { x++; } // 引用传递 void f(int &x) { x++; } // 指针传递 void f(int *x) { (*x)++; }
(1) 基本思想：
通过前面已知的结果推导后续结果
(2) 递推关系式：
f(n) = f(n-1) + f(n-2);
(3) 例：斐波那契：
int fib(int n) { if(n<=2) return 1; return fib(n-1)+fib(n-2); }
(1) 冒泡排序：
for(int i=0;i<n-1;i++) for(int j=0;j<n-1-i;j++) if(a[j]>a[j+1]) swap(a[j], a[j+1]);
(2) 插入排序：
for(int i=1;i<n;i++){ int key=a[i], j=i-1; while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; } a[j+1]=key; }
(3) 选择排序：
for(int i=0;i<n-1;i++){ int min_idx=i; for(int j=i+1;j<n;j++) if(a[j]<a[min_idx]) min_idx=j; swap(a[i],a[min_idx]); }
(4) 算法分析：
选择 → 不稳定 冒泡、插入 → 稳定
// 重定向输入输出 freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); // 文件读写 ofstream fout("data.txt"); fout << "Hello\n"; fout.close(); ifstream fin("data.txt"); string s; fin >> s; fin.close();
try { int x = 10/0; } catch(exception &e) { cout << "Error: " << e.what(); }
#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N][N]; int main() { int n,m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; // 示例操作：求二维数组元素和 int sum = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum += a[i][j]; cout << sum << endl; return 0; }
#include <bits/stdc++.h> using namespace std; struct Item { string name; int price; int priority; }; bool cmp(const Item &a, const Item &b) { if(a.priority != b.priority) return a.priority < b.priority; if(a.price != b.price) return a.price < b.price; return a.name < b.name; } int main() { int n; cin >> n; Item items[n]; for(int i=0;i<n;i++) cin >> items[i].name >> items[i].price >> items[i].priority; sort(items, items+n, cmp); for(int i=0;i<n;i++) cout << items[i].name << endl; return 0; }
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; int cnt=1, mx=1; for(int i=1;i<n;i++){ if(a[i]==a[i-1]+1) cnt++; else cnt=1; mx = max(mx, cnt); } cout << mx << endl; return 0; }
#include <bits/stdc++.h> using namespace std; const int N = 15; int a[N][N]; int main(){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; int ans=0; for(int u=1;u<=n;u++) for(int l=1;l<=m;l++) for(int d=u;d<=n;d++){ int chk=1; for(int r=l;r<=m;r++){ for(int x=u;x<=d;x++) chk &= a[x][r]; if(!chk) break; ans = max(ans, (r-l+1)*(d-u+1)); } } cout << ans << endl; return 0; }
#include <bits/stdc++.h> using namespace std; char s[105][105]; int main(){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> s[i]+1; // 输出子矩阵 int x1,x2,y1,y2; cin >> x1 >> x2 >> y1 >> y2; for(int i=x1;i<=x2;i++){ s[i][y2+1]=0; cout << s[i]+y1 << endl; } return 0; }
const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右 for(int k=0;k<4;k++){ int ni = i + d[k][0]; int nj = j + d[k][1]; }
int sum[N][N]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j] = a[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; // 区域和 int x1,y1,x2,y2; int ans = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; sort(a.begin(), a.end()); int ans=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(a[i]<a[j]) ans++; cout << ans << endl; }
| 知识点 | 关键内容 | 示例 |
|---|---|---|
| 指针 | 存储变量地址的变量 | int a=5; int* p=&a; cout<<*p; |
| 二维/多维数组 | 定义、访问 | int a[3][4]; a[1][2]=10; |
| 结构体 | 定义、数组、指针、嵌套 | struct Student{string name; int age;}; Student s[10]; |
| 函数 | 定义、声明、调用，形参/实参 | int add(int x,int y){return x+y;} int c=add(2,3); |
| 作用域 | 局部 vs 全局 | int x; // 全局 |
| 传参方式 | 值传递、引用、指针 | void f(int &x){x++;} |
| 递推算法 | 由前推后 | f(n)=f(n-1)+f(n-2); |
| 排序算法 | 冒泡/插入/选择 | sort(a,a+n); |
| 文件操作 | 重定向/读/写 | freopen("in.txt","r",stdin); |
| 异常处理 | try/catch | try{…} catch(exception &e){…} |
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡 | O(n²) | O(1) | 稳定 |
| 插入 | O(n²) | O(1) | 稳定 |
| 选择 | O(n²) | O(1) | 不稳定 |
| 快排 | O(n log n) | O(log n) | 不稳定 |
int a[N], n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) cout << a[i] << " ";
解析：
int a[N][N], n, m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j];
解析：
void bubbleSort(int *a, int l, int r){ bool flag = true; while(flag){ flag = false; for(int i=l;i<r;i++){ if(a[i] > a[i+1]){ swap(a[i], a[i+1]); flag = true; } } } }
解析：
（1）数组排序：下标从 0 开始
int a[10]; int n = 10; sort(a, a+n); // 排序 a[0] ~ a[9]
（2）数组排序：下标从 1 开始（考试常用）
int a[110]; int n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; sort(a+1, a+n+1); // 排序 a[1] ~ a[n]
a+1 指向 a[1]a+n+1 是 开区间右端点，所以最后会排序到 a[n]（3）总结：
数组排序 从 0 开始 →
sort(a, a+n)数组排序 从 1 开始 →sort(a+1, a+n+1)
vector<int> v; sort(v.begin(), v.end());
vector 下标一定是 0 开始
.begin()指向第一个元素.end()指向最后元素之后的位置（开区间）不需要加+1，直接用.begin(), .end()
bool check(int xa,int ya){ for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(w[xa+i][ya+j]!=match[i][j]) return false; return true; }
bool check(int xa,int ya,int xb,int yb){ int cnt[2]={0}; for(int i=xa;i<=xb;i++) for(int j=ya;j<=yb;j++) cnt[w[i][j]]++; return cnt[0]==cnt[1]; }
int ans = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=i;ii<=n;ii++) for(int jj=j;jj<=m;jj++) if(check(i,j,ii,jj)) ans = max(ans,(ii-i+1)*(jj-j+1)); cout << ans << "\n";
a[1]=1; vis[1]=1; for(int i=2;i<=n;i++){ if(a[i-1]-i<=0 || vis[a[i-1]-i]) a[i]=a[i-1]+i; else a[i]=a[i-1]-i; vis[a[i]]=1; } sort(a+1,a+n+1);
2、分析：
用于生成满足约束的序列。
vis[]用于记录已使用数字。
sort(a+1,a+n+1); int ans=0; for(int i=1;i<=n;i++){ int sum=0; for(int j=i;j>=1;j--){ if(a[i]-a[j]<=k) sum+=a[j]; else break; } ans = max(ans,sum); } cout << ans << "\n";
2、分析：
用于 连续/可滑动窗口求和。常见题型：限制差值 k 的最大和。
sort(a+1,a+n+1); int ans=0,s=1; for(int j=1;j<=m;j++) for(int k=s;k<=n;k++){ if(j<=a[k]){ ans++; a[k]=j; s=k; break; } } cout << ans;
2、分析：
贪心选择最小可行元素。常见题型：分配/匹配问题。
bool isSimilar(string A,string B){ int m=A.size(), n=B.size(); if(abs(m-n)>1) return false; if(m==n){ int diff=0; for(int i=0;i<m;i++) if(A[i]!=B[i]) if(++diff>1) return false; return true; } else { string &shorter=(m<n?A:B), &longer=(m<n?B:A); int i=0,j=0,diff=0; while(i<shorter.size() && j<longer.size()){ if(shorter[i]!=longer[j]){ if(++diff>1) return false; ++j; } else { ++i; ++j; } } return true; } }
2、分析：
用于检查两个字符串是否最多相差一个字符。可扩展到字符串编辑距离问题。
sort(s+1,s+n+1); string; for(int i=1;i<=n;i++) combined += s[i]; bool ok=true; for(int i=1;i<combined.size();i++) if(combined[i]<combined[i-1]) ok=false; cout << ok << "\n";
2、分析：
适合题型：多字符串排序后检查整体非下降。可以用 STL sort。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online