1. 基本框架
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
2. 输入输出
| No. | 类型 | 变量 | 输出 | 输入 |
|---|---|---|---|---|
| 1 | 整型 | int n = 0; |
printf("%d\n",n); |
scanf("%d",&n); |
| 2 | 单精度浮点型 | float f = 0; |
printf("%f\n",f); |
scanf("%f",&f); |
| 3 | 字符串 | string s; |
cout << s << "\n"; |
cin >>s; |
| 4 | 字符 | char c; |
printf("%c",c); |
scanf("%c",&c) |
| 5 | 长整型 | long long l; |
printf("%ldd",l); |
printf("%lld",&l); |
变量名只能英文字母加下划线
小数精确度处理：%.精确度f
整数除法说明
整数除以整数还是整数，如果结果需要是小数，要乘以1.0。例如：
3/2结果为1,1.0*3/2结果为1.5。
3. 字符串
- 字符串变量
string s; - 获取字符串长度
s.size() - 获取字符串
i位置字符s[i] - 遍历字符串
for(int i=0;i<s.size();++i){
printf("%c",s[i]);
}
- 从
i截取长度为len字符串s.substr(i,len); - 从
i截取到字符串结束s.substr(i); - 字符串字典序排序
sort(s.begin(),s.end()); - 在字符串后添加
n个字符cs.append(n,c); - 字符串连接
+,str3 = str1+str2 - 构建一个
n个字符c组成的字符串string(n,c)
4. 数组
- 定长数组：数组长度已知，并且数组大小不能改变
- 变长数组：数组长度未知，并且数组大小可以改变
4.1 一维数组
| No. | 操作 | 定长数组 | 变长数组 |
|---|---|---|---|
| 1 | 定义数组 | int nums[n]; |
vector<int> nums; |
| 2 | 访问下标i元素 |
nums[i] |
nums[i] |
| 3 | 存放数据 | nums[i] |
nums.push_back(数据) |
| 4 | 数据数量 | n |
nums.size() |
- 遍历向量
for(int i=0;i<nums.size();++i){ printf("%d\n",nums[i]); }
4.2 二维数组
| No. | 操作 | 定长数组 | 变长数组 |
|---|---|---|---|
| 1 | 定义数组 | int table[n][m]; |
vector<vector<int> > table; |
| 2 | 行数 | n |
table.size() |
| 3 | 列数 | m |
table[i].size() |
| 4 | 获取第i行第j列数据 |
table[i][j] |
table[i][j] |
- 向量存储数据
vector<vector<int> > table; vector<int> row1; row1.push_back(1); row1.push_back(3); row1.push_back(4); row1.push_back(5); row1.push_back(6); vector<int> row2; row2.push_back(2); row2.push_back(7); row2.push_back(10); vector<int> row3; row3.push_back(8); row3.push_back(9); table.push_back(row1); table.push_back(row2); table.push_back(row3); - 向量遍历
for(int i=0;i<table.size();++i){ for(int j=0;j<table[i].size();++j){ printf("%d ",table[i][j]); } printf("\n"); }
5. 排序
- 排序函数
sort(开始位置,结束位置) - 按照
cmp方式排序sort(开始位置,结束位置,cmp)
sort()默认以字典序排列字符，以升序排列数字。
- 按照字典逆序排列字符串
#include <bits/stdc++.h>
using namespace std;
bool cmp(char a,char b) {
return a > b;// 正确的顺序
}
int main() {
string s; // s[i]
cin >> s;
sort(s.begin(),s.end(),cmp);
cout << s;
return 0;
}
- 按照降序排列数列
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a > b;// 正确的顺序
}
int main() {
int n = 0;
scanf("%d",&n);
int nums[n];
for(int i=0;i<n;++i){
scanf("%d",&nums[i]);
}
sort(nums,nums+n,cmp);
for(int i=0;i<n;++i){
printf("%d ",nums[i]);
}
return 0;
}
6. 结构体
把多个变量绑到一起的一个类型，可以把结构体看成一个多个变量组成包。
struct 结构体{
变量...
};
例如:
定义结构体
struct UserInfo{
string name;
int age;
bool sex;
};
使用
UserInfo zhangsan;
zhangsan.name = "张三";
zhangsan.age = 31;
zhangsan.sex = true;
结构体数组
UserInfo users[n];
users[i].name
users[i].age
users[i].sex
7. 查找
- 排序函数
find(开始位置,结束位置,查找值)
如果找到了，返回查找值位置，反之，返回结束位置。
8. 集合set
set<类型> 集合名
插入数据集合名.insert(数据);
删除数据集合名.erase(数据);
set里面没有重复的值，不能使用[下标]访问。
集合里面存放数据数目集合名.size()
set<string> resset;
resset.insert("00");
resset.insert("10");
resset.insert("11");
resset.insert("01");
resset.insert("00");
resset.insert("01");
resset.insert("00");
resset.insert("00");
resset.insert("01");
resset.insert("00");
resset.insert("01");
// 集合不能使用resset[0];
for(string s:resset){
cout << s << '\n';
}
数据不允许重复，使用集合set<>
9. 基于范围for循环
int nums[4];
nums[0] = 1;
nums[1] = 2;
nums[2] = 3;
nums[3] = 4;
// 基于下标的for循环
for(int i=0;i<4;++i){
printf("%d\n",nums[i]);
}
// 基于范围的for循环
for(int n:nums){
// n相当于nums[i]
printf("%d\n",n);
}
10. 指针
指针是用来存放变量的地址。使用类型 *定义指针，
*指针变量使用指针。
如果指针类型是结构体，使用->访问结构体的变量。
#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 0;
printf("%d\n",a);
int *p = &a;
*p = 10;
printf("%d\n",a);
}
11. 链表
数组类型 数组名[n]
#include <bits/stdc++.h>
using namespace std;
// 链表节点 = 数据 + 索引(指针)
struct Node{
int data;
Node *p;
};
// 10 7 5 3 2 1
int main() {
// 构造链表
Node head; // 头节点(链表的首节点)
head.data = 10;
Node n1;
n1.data = 7;
head.p = &n1;
Node n2;
n2.data = 5;
n1.p = &n2;
Node n3;
n3.data = 3;
n2.p = &n3;
Node n4;
n4.data = 2;
n3.p = &n4;
Node n5;
n5.data = 1;
n4.p = &n5;
n5.p = NULL; // n5后面没有节点了NULL。
// 遍历链表
Node* pNode = &root;
while(pNode != NULL){
printf("%d ",pNode->data);
pNode = pNode->p;
}
}
栈
先进先出LIFO
使用vector<>模拟栈。
vector<char> test;
test.push_back('/');
test.push_back('a');
test.push_back('b');
test.push_back('c');
test.pop_back();
test.push_back('d');
test.pop_back();
test.pop_back();
for(int i=0;i<test.size();++i){
cout << test[i] << "\n";
}
栈的主要用途是，解决括弧匹配问题。
#include <bits/stdc++.h>
using namespace std;
bool check(string s){
vector<char> stack;
for(int i=0;i<s.size();++i){
if(s[i] == '['){
stack.push_back('[');
}else if(s[i] == ']'){
if(stack.empty()){// 如果前面没有做左括号，不匹配
return false;
}
stack.pop_back();
}
}
return stack.empty();
}
int main(){
string s = "[[[]]][][][][][][][]";
printf("%d\n",check(s));
return 0;
}
特殊函数
累加函数accumulate(first,last,init)，累加序列[first,last)区间中的数据，init是累加初始值
树
struct Node{// 双亲孩子表示法
vector<int> children;
};
void DFS(int root,Node* nodes){// 深度优先遍历
stack<int> s;
s.push(root);
while(!s.empty()){
int now = s.top();
s.pop();
printf("%d ",now); // 出栈访问
vector<int> children = nodes[now].children;
for(int i=children.size()-1;i>=0;--i){
int post = children[i];
s.push(post);
}
}
}
void BFS(int root,Node* nodes){// 广度优先遍历
queue<int> s;
s.push(root);
printf("%d ",root); // 入队访问
while(!s.empty()){
int now = s.front();
s.pop();
vector<int> children = nodes[now].children;
for(int i= 0;i<children.size();++i){
int post = children[i];
s.push(post);
printf("%d ",post); // 入队访问
}
}
}
深度遍历递归写法
void DFS2(int root,Node* nodes){// 深度优先遍历
printf("%d ",root); // 出栈访问
vector<int> children = nodes[root].children;
for(int i= 0;i<children.size();++i){
int post = children[i];
DFS2(post,nodes);
}
}
