C++笔记(有时间持续更新)(最近更新2月3日)

zyl 喵星人 2023-10-07 23:45:13 2024-03-20 14:21:54 41

2023年10月16日,补充数据结构:链表、哈希表。补充算法:递归、广搜

2023年11月6日,补充排序算法:冒泡排序、选择排序、桶排序。优化了部分排版显示

2024年2月3日,新增了程序优化,补充递归算法、递推算法

梦开始的地方

// 基本框架
#include<iostream>
using namespace std;
int main(){
    return 0;
}

程序优化

将以下代码加到程序第一行(头文件前面),可以实现时间上的优化

1、指令优化,评测机指令架构可能不一样,有可能产生RE错误,慎用!!!

#pragma GCC target("avx,sse2,sse3,sse4,mmx")

2、编译优化,也就是常说的O2优化,主要分为O1,O2,O3三种,只推荐开到O2即可,O3没必要!!!

// 一般只写这一句就会有很大的效果了
#pragma GCC optimize(2)

最后附上我常用的优化代码

#pragma GCC target ("avx")
#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")

第一章:IO

数据输出:

cout & printf

// 输出指令:cout
// 输出运算符:<<   (两个小于)
// 换行指令:endl
cout<<"这是一个输出样例:"<<endl;
cout<<"hello world!";

// C语言格式化输出: printf("<格式化字符串>", <参量表>)
// 常用:%d 整形、%lld 长整型、%c 字符型、%f 浮点型、%lf 高精度浮点、%.3f 保留三位小数
double pi = 3.1415926;
printf("保留小数位数:%.2lf %.3lf", pi, pi);

更多格式化字符串:请点这里

数据输入:

cin & scanf

// 输入指令:cin
// 输入运算符:>>   (两个大于)
// 输入数据前,需要先定义变量来接收
int a;
cin>>a;

// C语言格式化输入: scanf("<格式化字符串>", &<参量表>)
// 使用时变量前面一定要加上取址符 &   对应的格式化字符串类型不能写错
// 常用:%d 整形、%lld 长整型、%c 字符型、%f 浮点型
double pi;
scanf("%lf", &pi);

做题时的文件IO:

做题时只需要正常写在main主函数最开始的地方

// 从文件中读取输入,文件名C.in
freopen("C.in", "r", stdin);
// 将答案写入文件,文件名C.out
freopen("C.out", "w", stdout);

第二章:基本语法

分支结构

if语句

// 第一个if语句必须写,另外两个非必须,根据需求来写
if(){}
else if(){}
else{}

三目运算符

基本格式

如果表达式1为真,那么语句返回的值就是表达式2,否则返回表达式3的值

int a=10, b=10;
// 如果a>b为真,c=a,否则c=b
int c = a>b?a:b;

switch语句

// 小括号只能传整形 和 字符类型。break必须写,不写就会合并多个情况
switch (1) {
    case 1:
        // 第一个选择
        break;
    case 2:
        // 第二个选择
        break;
    default:
        // 以上都没出现的选择
        break;
}

循环结构

for循环

// 从0开始,到100结束
for(int i=0;i<=100;i++){
    cout<<i<<" ";
}

while循环

// 小括号为运行的条件,只要条件为真就会执行循环
while(1){}
// 当小括号里面为1,表示死循环,不会主动结束,需要使用break来结束循环
// continue语句:跳过本次循环

do-while循环

// 优先级t10086,学了就没用过,了解就行
do{
    // 代码,(和while没啥区别,这个是先循环一次,再去判断条件)
}while(1);

goto语句(牛马语句)自行百度了解

函数:封装代码,提高代码复用率

// 函数是一种固定的代码,可以让代码被重复利用,降低冗余
// 函数定义五个步骤
// 1、函数的返回值类型,即调用了这个函数后,你想要得到的数据类型(关联第5点),没有返回值就是void
// 2、函数名,随便定义,只要满足变量命名规则即可
// 3、函数的参数,需要传给函数的变量(可有可无)
// 4、函数的功能(核心代码)
// 5、函数的返回值,函数处理完的结果(关键字:return),只要第一点写的不是void,就必须要写return返回值

// 例:定义找两个整数最大值的函数
// 1、函数返回值类型:两个数的最大值,返回值为int类型
// 2、函数名:my_max
// 3、函数的参数:需要传入两个整数a,b
// 4、函数的功能:找两个整数的最大值:a>b?a:b
// 5、函数的返回值:直接返回最大的值即可
int my_max(int a, int b){
    return a>b?a:b;
}

结构体:可以自己创建数据类型 (不考虑高级用法)

// 结构体关键字:struct
struct xxx{       // 结构体名称:xxx
    string name;  // 结构体属性1
    int age;      // 结构体属性2
    int score;    // 结构体属性3
}a,b,c;  // 定义结构体的时候可以声明结构体变量,写不写都可以
// 使用结构体创建变量,和创建int变量一样:  数据类型  变量名;  
xxx aa;  // 创建了一个结构体变量aa 
struct xxx bb;  // 结构体专属写法,我的评价是不如上面那种。。
// 结构体变量赋值
// 1、在创建时赋值(列表化赋值),必须严格按照结构体定义时的顺序来赋值
xxx aa = {"小明", 12, 250};
// 2、指定属性赋值,可以根据需求指定属性赋值,没有顺序要求
bb.age = 12;
bb.name = "小明";
bb.score = 250;
// 输出结构体时,要指明属性,不能直接输出结构体变量
cout<<aa.name<<" "<<aa.age<<" "<<aa.score;

第三章:数据结构

1、数组

// 相同数据类型的元素按一定顺序排列的集合,就是把有限个类型相同的变量用一个名字命名
// 数据类型  数组名[元素个数];
int a[100];  // 100个元素的int数组,也可以理解为100个变量
a[0] = 999;  // 通过索引访问元素
cout<<a[0];

1、数组的索引从零开始

2、数组的最大索引是长度减一

2、栈

一种数据结构,特点是先进后出

#include<stack>  // 使用时需要导入头文件
// 创建栈
stack<int> st;   // 创建了一个名为st的栈,里面只能存放int类型的数据
stack<Node> st1; // 创建了一个名为st1的栈,里面只能存放Node类型的数据 Node:自己的定义的结构体类型
// 栈的常用操作
st.push(1);    // 往st栈顶添加一个元素1
st.pop();      // 把st栈顶元素弹出(删除、出栈)
st.top():      // 获取st栈顶元素
st.size();     // 获取st栈的元素个数
st.empty();    // 判断st栈是否为空,为空则返回1

3、队列

一种数据结构,特点是先进先出(生活中的排队)

#include<queue>  // 使用时需要导入头文件
// 创建栈
queue<int> st;   // 创建了一个名为st的队列,里面只能存放int类型的数据
queue<Node> st1; // 创建了一个名为st1的队列,里面只能存放Node类型的数据 Node:是自己的定义的结构体类型
// 队列的常用操作
st.push(1);    // 往队尾添加一个元素
st.pop();      // 把队首元素出队(删除)
st.front():    // 获取队首元素
st.back();     // 获取对尾元素
st.size();     // 获取队列中的元素个数
st.empty();    // 判断队列是否为空,为空则返回1

4、链表(结构体+指针)

链表是一种用于存储数据的数据结构,通过如链条一般的指针来连接元素

它的特点是插入与删除数据十分方便,但寻找与读取数据的表现欠佳。

链表分类主要有 单链表 和 双链表

单链表:

struct Node{
	int val;    // 链表的值
	Node *next; // 下一个节点的地址
};

双链表

struct Node{
	int val;     // 链表的值
	Node *left;  // 上一个节点的地址
	Node *right; // 下一个节点的地址
};

链表的实现涉及到指针和动态内存管理,篇幅有限就不贴代码了

5、哈希表(集合)

哈希表又称散列表,一种以「key-value」形式存储数据的数据结构,可以简单看成python中的字典

#include<map>    // 使用时需要导入头文件
// 创建,前一个类型是键的类型,后一个是值的类型
map<int, int> p;     // 创建了一个哈希表变量,键的类型是int,值的类型也是int
map<char, int> p2;   // 创建了一个哈希表变量,键的类型是char,值的类型是int
map<string, int> p3; // 创建了一个哈希表变量,键的类型是string,值的类型是int,可以用来统计字符串出现的数量(比结构体好用)
// 使用
// 1、键不存在:
p2['A'] = 100; // 添加一个数据,键为'A',值为100
// 2、键存在:正常调用即可
cout<<p2['A'];

第四章:基础算法

排序算法

冒泡排序

排序的过程就像冒泡一样,每次都会把待排序数组中最大(最小)的元素冒泡到数组的末尾,排序的核心就是循环比较和交换

例:对数组:12,3,25,99,21,1,33,17,进行冒泡升序排序

从第一个元素开始,依次对相邻的两个元素进行比较判断,并把最大的元素交换到后面去

第一次冒泡,99被交换到末尾,完成排序

3,12,25,21,1,33,17,99

第二次冒泡,33被交换到末尾,完成排序

3,12,21,1,25,17,33,99

第三次冒泡,25被交换到末尾,完成排序

3,12,1,21,17,25,33,99

...... (一直重复这个过程,直到排序结束)

// 排序n个元素,只需要冒泡n-1次即可
for(int i=1;i<=n-1;i++){
	// 每完成一次冒泡排序,就可以少比较一次(排好序的元素越来越多)
	for(int j=1;j<=n-i;j++){
		// 把较大的元素排序到末尾
		if(a[j]>a[j+1]) swap(a[j], a[j+1]);
	}
}

选择排序

本质上和冒泡差不多,选择排序每次都会从待排序数组中选择一个最大(最小)的值,然后放到数组的最前面,相比冒泡排序减少了很多交换次数

例:对数组:12,3,25,99,21,1,33,17,进行选择升序排序

第一次选择,最小值1被交换到待排序数组的最前方

1,3,25,99,21,12,33,17

第二次选择,最小值3被交换到待排序数组的最前方

1,3,25,99,21,12,33,17

第二次选择,最小值12被交换到待排序数组的最前方

1,3,12,99,21,25,33,17

...... (一直重复这个过程,直到排序结束)

// 每次选择一个最小(最大)的元素,放到待排序数组前面
for(int i=1;i<=n-1;i++){
	// 找待排序数组中的最小值
	int k = i, minn = a[i]; // 初始化最小值的信息
	for(int j=i;j<=n;j++){
		if(a[j] < minn){  // 比较找最小值
			k = j;        // 更新最小值索引
			minn = a[j];  // 更新最小值
		}
	}
	swap(a[i], a[k]);  // 把当前的最小值和待排序数组第一个元素交换
}

桶排序

桶排序,是一种用桶数组来辅助的排序算法,适用于数据数据范围较小的情况,且只能对整数排序,去重和排序都比较方便

桶数组:是一个标记数组,用于标记某个数字是否出现,或者统计某个数字的出现次数。因为不管某个数字是否出现,都会占用一个数组空间(数组是连续的),所以数据范围太大的话,桶排序无法完成。(可以考虑用哈希表来优化桶数组)

例:对数组:12,3,25,99,21,1,33,17,进行桶排序(升序)

// 初始化桶,数据中的最大值是99,所以桶的容量必须大于99
// 类型根据是否要去重来选择,去重就用bool数组标记,不去重就int数组统计
int tong[100] = {0};  
int t;
for(int i=1;i<=n;i++){
	cin>>t;
	tong[t]++;  // 每获取一个数据,t的次数+1
}
// 桶的索引就是题目输入的数据
// 最后根据桶的索引输出排序后的数组即可
for(int i=0;i<=100;i++){  // 升序
	// 不去重的排序,根据统计出现的次数来输出
	for(int j=1;j<=tong[i];j++){
		cout<<i<<" ";
	}
	// 要去重的话,桶数组就用bool类型,标记元素是否出现
	// 每个元素出现了,就输出一次即可
	// if(tong[i] == 1) cout<<i<<" ";
}

递归

传送门:算法笔记-递归

递给你一个乌龟

递归:是一种函数直接或者间接调用自己的算法,主要特点就是套娃似的调用自己。在解递归类的题目时,核心思路就是把大问题拆分为很多小问题,然后继续拆分每一个小问题,直到拆分的问题能直接求解为止。学了树结构的同学,可以多画一下递归调用树,很快就能理解啦。

递归解题三要素:

1、递归函数的定义,递归最重要的就是明白函数的功能是什么,充分的理解自己定义的函数。

2、递归表达式,递归是自己调用自己的逻辑,也就是说会把目标问题分成其他的更小、更容易解决的问题,这个过程就是递归表达式。

3、递归边界,可以把递归比作一个循环,不设定结束的条件就会陷入'死循环'。

例:求1~n全部整数之和。

// 1、函数定义:sum(n)表示1~n的全部整数之和,sum(5)=15
// 2、递归表达式:sum(n) = sum(n-1)+n,把要解决的问题拆成了范围更小的问题
// 3、递归边界:当n=1时,可以直接得出sum(1)=1,不需要继续递归了
int sum(int n){
	if(n == 1) return 1;
	return sum(n-1) + n;
}

递归的优化

递归的优化主要集中在记忆化递归尾递归上面。

记忆化递归:就是用一个数组来保存每一次递归计算的结果,当递归到某个值时,先去数组里面找这个值之前有没有计算过,计算过直接获取之前计算的值;没有计算过就计算了再放入数组中。

尾递归:一个函数中所有递归形式的调用都出现在函数的末尾,即递归调用都写在return语句里面

递推

递推是一种数学上的方法,也是计算机中比较重要的基础算法。

递推算法的特点是:在求一个问题时,已知条件和要求的结果之间存在某种联系,这个联系就是递推式,找到递推的关系式后。从问题推导到已知条件叫做逆推;从已知条件推导到问题叫做顺推。

代码太多,经典题目总结好了,自己看(^_^) 传送门:递推笔记

第五章:进阶算法

搜索:深搜(深度优先)(可以简单理解为一条路走到底)

深搜的基础是递归,通过遍历每一种可能找到最优解,属于暴力的算法,能通过的数据范围有限(一般不会超过20)。

例1:排列组合,从n个数中选择k个数的全排(组合)

#include <iostream> 
using namespace std;

// 从n个数中选k个数全排(组合)
int n,k;
int res[15];  // 答案数字
bool vis[15]; // 标记数组,0表示没被选过,1表示被选

// 函数作用:表示当前选的是第几个数(总共要选k个数)
void dfs(int x){
	// 当前选的数超过k个,就结束搜索(x等于k,即dfs(k)表示选第k个数)
	if(x>k){
		// 输出答案,有k个数字所以要用循环
		for(int i=1;i<=k;i++){
			cout<<res[i]<<" ";
		}
		cout<<endl;
		return;
	}
	// 从1~n个数中选
	for(int i=1;i<=n;i++){
		// 全排列:没有数字大小限制,只有一个条件:数字没被选过即可
		// if(vis[i] != 1){
		
		// 组合:数字没被选过 && 当前选的数字不能小于前一个数字
                // 也就是说,1 2 3 和 2 3 1是一种方案
		if(vis[i] != 1 && res[x-1]<i){

			res[x] = i;  // 把这个数字记录到答案数组中
			vis[i] = 1;  // 标记这个数字,后面的搜索中不能再选了
			dfs(x+1);    // 递归搜索下一个数字
			vis[i] = 0;  // 回溯,本次搜索完后,后续的其他搜索中也可能有这个数字
		}
	}
}

int main(){
	cin>>n>>k;
	dfs(1);
	return 0; 
}

搜索:广搜(宽度优先、广度优先)(每次都会访问同一层的节点,访问完了再访问下一层)

和深搜不同,广搜需要借助队列来完成,解题过程就是先把起点入队,然后在循环出队,每次出队一个元素,就把能从这个点一次能到的点全部入队,循环操作,直到结束

例:有一个n*m的迷宫地图,上面用字符来描述迷宫的情况,其中'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。现在你需要找到从起点到出口最少需要走的步数

#include <iostream>
#include<queue>  // 队列头文件
using namespace std;

// 迷宫格结构体,当前格子的坐标(x,y),以及从起点到当前格子的最少步数step
struct pos{
	int x,y,step;
};


queue<pos> q;        // 广搜队列
char map[105][105];  // 地图数组
int vis[105][105];   // 标记数组,用于标记已经被走过的点
int dx[4] = {0,1,0,-1};  // x方向位移数组:右、下、左、上
int dy[4] = {1,0,-1,0};  // y方向位移数组:右、下、左、上
// 地图大小
int n,m,ans=0;
int sx,sy; // 起点坐标
int ex,ey; // 终点坐标

// 广搜
void bfs(){
        // 起点格子
	pos t = {sx,sy,0};
	vis[sx][sy] = 1; // 标记起点
	q.push(t);       // 起点入队,开始广搜
	while(!q.empty()){
		t = q.front();  // 队首元素出队
		q.pop();        // 队首已经在下面被访问,所以可以先删掉
		// 走到终点结束
		if(t.x == ex && t.y == ey){
			ans = t.step;
			return;
		}
                // 从当前队首的格子能走到的四个方向上的格子
		for(int i=0;i<4;i++){
			int xx = dx[i] + t.x;
			int yy = dy[i] + t.y;
			// 不能超过迷宫边界   遇到墙不能走  走过的不能走
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[xx][yy]!='#'&&vis[xx][yy]!=1){
				q.push({xx,yy,t.step+1});  // 上下左右能走的入队,并更新最少步数step
				vis[xx][yy] = 1; // 下个格子被走过了,标记
			}
		}
	}
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>map[i][j];
			if(map[i][j] == 'S') sx = i, sy = j; 
			if(map[i][j] == 'T') ex = i, ey = j;
		}
	}
	bfs();  // 调用广搜
	cout<<ans;
	return 0;
}
{{ vote && vote.total.up }}

共 13 条回复

jxy2012 qwq

6

pjy

6

czh12 黄金1

支老师我们永远会记住你的

pjy

老师

cw 原劈

支老师我们永远会记住你的

ykj49 Accepted

喵星人

CPP 刷题王

6

root 站长

我直接看成了梦开始的地方

elk

非常实用

ykj73 敬老院战神

好用————666!!!