《算法训练营》语言基础(ﾟДﾟ

👂 无论你多怪异我还是会喜欢你（《刺客伍六七》动画推广版片尾曲） - 周子琰 - 单曲 - 网易云音乐

一起补基础！ φ(゜▽゜*)♪

👂 My Nam's Suzie - Susie/Farfashah - 单曲 - 网易云音乐

算法训练营的东西，都会放到《蓝桥杯2024备赛》专栏里

花了我68块买的书，第一章耗时5小时，12032字

🌳基础语法

🌼cout与指针

🌼（浮点）精度，域宽，填充

🌼输出格式

🌳轻松写函数

🌼1，标准函数

🌼2，无返回值函数

🌼3，无参数函数

🌼4，传值参数函数

🌼5，引用参数函数

🌼6，数组参数函数

🌼7，字符串参数函数

🌼8，函数嵌套

🌼9，函数重载

🌼10，函数模板

🌳递归

🌳结构体 -- 信息携带者

🌳数组

🌼先说静态数组

🌼再说动态数组

🌼2，二维数组

🌳字符串

🌼1，C-风格字符串

🌼2，C++ string类字符串

🌳基础语法

🌼cout与指针

利用cout对象输出指针，引用类型的数据。当输出数据为指针或引用类型，与printf()函数用法一致，不带 * 输出的是指针的值，即变量地址；带 * 输出的是指针指向的变量的值。

它比printf()函数简便之处，在于，不必设置数据的输出格式

#include<iostream>
using namespace std;
int main()
{int a = 10, *p;int &b = a; //引用, 变量b和a指向同一个空间p = &a; //指针p存储变量a地址string s = "C++";string *ps = &s;cout<<p<<endl; //地址cout<<b<<endl; //值cout<<*p<<endl; //值cout<<endl;cout<<ps<<endl; //地址cout<<*ps; //值return 0;
}

0x6dfecc
10
100x6dfeb4
C++

🌼（浮点）精度，域宽，填充

操作符	功能
setprecision(int n)	精度为n
setw(int n)	域宽为n
setfill(char c)	填充的字符为c

头文件：#include<iomanip>

训练1-2：将2.0开平方后，设置不同精度和宽度，输出

#include<iostream>
#include<cmath> //sqrt
#include<iomanip> //setw(), setprecision(), setfill()
using namespace std;
int main()
{double d = sqrt(2.0);cout<<"精度设置："<<endl;for(int i = 0; i < 5; ++i)cout<<setprecision(i)<<d<<endl; //设置不同精度cout<<"当前精度为："<<cout.precision()<<endl;cout<<"当前域宽："<<cout.width()<<endl;cout<<setw(6)<<d<<endl; //默认右对齐cout<<"当前填充字符："<<endl;cout<<setfill('*')<<setw(10)<<d<<endl; //setfill()函数可直接插入流return 0;
}

精度设置：
1
1
1.4
1.41
1.414
当前精度为：4
当前域宽：01.414
当前填充字符：
*****1.414

🌼输出格式

操作符	功能
oct	八进制输出
dec	十进制输出
hex	十六进制输出

训练1-3：输入一个三位数，输出个位，十位，百位上数字

#include<iostream>
#include<iomanip> //setw()
using namespace std;int main()
{int n;cin>>n;int ge, shi, bai;ge = n % 10, shi = n / 10 % 10, bai = n / 100 % 10;cout<<ge<<setw(2)<<shi<<setw(2)<<bai;return 0;
}

647
7 4 6

🌳轻松写函数

函数是...实现某一功能代码的...模块化封装，定义如下

返回值类型  函数名(参数类型  参数名1, 参数类型  参数名2...) 
{执行语句...return 返回值;
}

下面介绍10种函数类型，分别是

1，标准函数 2，无返回值函数 3，无参数函数 4，传值参数函数

5，引用参数函数 6，数组参数函数 7，字符串参数函数 8，函数嵌套

9，函数重载 10，函数模板

🌼1，标准函数

训练1-22：输入n对整数a, b，输出它们的和

#include<iostream>
using namespace std;//int add(int a, int b); //函数原型声明
int add(int a, int b) //函数定义
{return a + b;
}int main()
{int n, a, b;cin>>n;int C[n];for(int i = 0; i < n; ++i) {cin>>a>>b;C[i] = add(a, b); //调用函数}for(int i = 0; i < n; ++i)cout<<C[i]<<endl;return 0;
}

🌼2，无返回值函数

如果没有返回值，则返回值类型为void

训练1-23：输入n，输出1~n的所有整数（无返回值）

#include<iostream>
using namespace std;void print(int n) { //无返回值for(int i = 1; i <= n; ++i)cout<<i<<endl;
}int main()
{int n;cin>>n;print(n);return 0;
}

🌼3，无参数函数

训练1-24：输入n，如果n为10的倍数，输出3个“very good!”

#include<iostream>
using namespace std;void print() //无参数
{for(int i = 0; i < 3; ++i)cout<<"very good!"<<endl;
}int main()
{int n;cin>>n;if(n % 10 == 0)print();return 0;
}

20
very good!
very good!
very good!

🌼4，传值参数函数

传值参数在函数内部的改变，出了函数后无效

训练1-25：输入两个整数a, b，交换后输出

#include<iostream>
using namespace std;void swap(int x, int y) //传值参数
{int temp;temp = x;x = y;y = temp;cout<<"交换中"<<x<<"\t"<<y<<endl;
}int main()
{int a, b;cin>>a>>b;cout<<endl;cout<<"交换前"<<a<<"\t"<<b<<endl;swap(a, b);cout<<"交换后"<<a<<"\t"<<b<<endl;return 0;
}

-2 666交换前-2        666
交换中666       -2
交换后-2        666

🌼5，引用参数函数

引用参数在参数前加“&”符号，引用参数在函数内部的改变，除了函数后仍然有效

训练1-26：输入两个整数a和b，交换后输出

#include<iostream>
using namespace std;void swap(int &x, int &y) //引用参数
{int temp;temp = x;x = y;y = temp;cout<<"交换中"<<x<<"\t"<<y<<endl;
}int main()
{int a, b;cin>>a>>b;cout<<endl;cout<<"交换前"<<a<<"\t"<<b<<endl;swap(a, b);cout<<"交换后"<<a<<"\t"<<b<<endl;return 0;
}

对比传值参数，只是在参数前，加了取地址符“&”

-3 666交换前-3        666
交换中666       -3
交换后666       -3

🌼6，数组参数函数

此部分较为陌生

训练1-27：输入n个整数并将其存入a[]数组，求和然后输出和

#include<iostream>
using namespace std;int arrayadd(int a[], int n) //a[n]作为参数时, 要分开写, a[]也可用*a
{int sum = 0;for(int i = 0; i < n; ++i)sum += a[i];return sum;
}int main()
{int n, s;//静态定义长度1000的数组, 静态定义空间数是具体的数值或常量int a[1000];cin>>n;//int *a = new int [n]; //动态定义, 此时n可以为变量for(int i = 0; i < n; ++i)cin>>a[i];s = arrayadd(a, n);cout<<s<<endl;return 0;
}

4
2 7 -5 11
15

🌼7，字符串参数函数

训练1-28：输入n个字母，如果是小写字母，转换为大写字母，输出转换后的字符串

#include<iostream>
//#include<string>
using namespace std;void strconvert(string &s) //char *s字符型数组
{for(int i = 0; i < s.length(); ++i) //strlen(s)if(s[i] >= 'a' && s[i] < 'z')s[i] -= 32;cout<<s<<endl;
}int main()
{string str; //char str[10]字符型数组cin>>str;strconvert(str);cout<<str<<endl;return 0;
}

What'sYourName
WHAT'SYOURNAME
WHAT'SYOURNAME

🌼8，函数嵌套

训练1-29：输入两个整数a和b，求两个整数的最大公约数和最小公倍数

#include<iostream>
using namespace std;int gcd(int x, int y) //辗转相除求最大公约数
{int t;while(x % y) {t = y;y = x % y;x = t;}return y;
}int lcm(int x, int y) //最小公倍数
{int g;g = gcd(x, y); //嵌套return (x * y / g);
}int main()
{int a, b, c, d;cin>>a>>b;c = gcd(a, b);d = lcm(a, b);cout<<c<<"\t"<<d;return 0;
}

80 36
4       720

🌼9，函数重载

函数重载（多态）指的是，多个同名函数，但是每个函数的，参数数量，类型，顺序不同

它可以提高代码的可读性和复用性

训练1-30：写一个函数，对于字符串类型的数据，取其长度一半；对于浮点类型的数据，取其值二分之一

#include<iostream>
//#include<string>
using namespace std;float half(float x)
{return x / 2;
}char *half(string s) //返回一个char型指针, 表示字符串地址
{int n = s.length() / 2;char *str = new char[n + 1]; //new分配的是地址for(int i = 0; i < n; ++i)str[i] = s[i];str[n] = '\0';return str;
}int main()
{float n;string st;cin>>n>>st;cout<<half(n)<<endl;cout<<half(st);return 0;
}

3.22345
HeyGirl
1.61172
Hey

详细解释下代码中的

char *half(string s) //返回一个char型指针, 表示字符串地址
char *str = new char[n + 1]; //new分配的是地址

1，函数定义中，使用了指针类型char*来存储字符串类型的返回值，因为字符数组可以使用指针来访问，并且使用动态内存分配函数new来动态创建一个长度为n + 1的字符数组

2，'\0'是表示字符串结束的空字符

3，C++中，实现带有字符串类型返回值的函数时，通常使用指针类型char *来存储返回值，并使用new动态分配内存来保证内存的正确分配和释放

4，使用指针类型存储分配的内存地址，* 运算符获取该指针指向的值

🌼10，函数模板

在C++中，template 是一种用于定义通用代码的机制，可以用于定义类模板、函数模板和变量模板等。其中，函数模板是一种通用的函数定义方式，使得可以声明和定义多个具有相同结构但参数类型不同的函数，具体的语法格式如下：

template <typename Type1, typename Type2, ...>
ReturnType FunctionName(Type1 arg1, Type2 arg2, ...)
{// function body
}

函数模板（Function Template）使得代码更加灵活，可以避免重复编写相似的代码，同时也更方便管理和维护代码

训练1-31：输入两个数a和b（整数或浮点数），求两个数的和值

#include<iostream>
using namespace std;template<typename T> //模板
T add(T x, T y) //相当于把int, float等替换成自定义名字
{return x + y;
}int main()
{int a, b;double c, d;cin>>a>>b>>c>>d;cout<<add(a, b)<<"\t"<<add(c, d);return 0;
}

18 -22 17.22 1.33
-4      18.55

🌳递归

递归调用是函数内部调用自身的过程，需要结束条件，否则会进入无限递归状态，永远无法结束

1，递归函数

训练1-32：输入n个整数，倒序输出所有整数

#include<iostream>
using namespace std;
int a[100];void print(int i)
{cout<<a[i]<<endl;if(i > 0)print(i - 1);//cout<<a[i]<<endl;
}int main()
{int n;cin>>n;for(int i = 0; i < n; ++i)cin>>a[i];print(n - 1);return 0;
}

2，递归原理

递归 = 递推 + 回归

递推指的是，将原问题不断分解为子问题直到达到结束条件，返回最近子问题的解

然后逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解

阶乘是典型的递归调用问题

先看代码

#include<iostream>
using namespace std;long long fac(int n)
{if(n == 0 || n == 1)return 1;elsereturn n * fac(n - 1);
}int main()
{int n;cin>>n;cout<<fac(n);return 0;
}

5
120

再看原理图

注意

递归中，每一次递推都需要一个栈空间来保存调用记录，so计算空间复杂度时，需要计算递归栈的辅助空间

递归在计算机内部的处理，使用了一种被成为“栈”的数据结构，类似步枪弹匣的装子弹和退子弹

只能从顶端插入和抽取，被称为“后进先出”(Last In First Out, LIFO)

原理图如下（实际递归中传递的是参数的地址）

进栈

出栈

先一步一步把子问题压入栈，直到得到返回值，再一步一步出栈，最终得到递归结果，运算过程使用了n个栈空间作为辅助空间

训练1-34：输入一个整数n，输出斐波那契数列第n项

🌳结构体 -- 信息携带者

多个数据项组合在一起作为一个数据元素

struct student //学生信息结构体
{string name, number, sex;int age;float score;
};
student a; //定义一个结构体类型变量a

有时为了方便，会使用typedef给结构体起个小名

typedef struct student //学生信息结构体
{string name, number, sex;int age;float score;
}stu;
stu a; //定义一个结构体变量a, 与student a等效

typedef语法规则

typedef 类型名称 类型标识符;

使用typedef好处

1，简化复杂的类型声明

2，提高程序可移植性

比如

typedef in ElemType; //给int起个小名ElemType

在程序中就可以直接定义

ElemType a; //等价于int a;

所以，如果由1000个地方用到了ElemType类型，但是现在处理的数据变为字符类型了

可以将类型定义中的int改为char

typedef char ElemType;

这样只需修改类型定义，无需在1000个位置改动，否则容易漏了某处导致错误

使用typedef提高算法通用性，因为很多时候结构体定义并不指定处理的数据是什么类型，不能简单写成某种类型

🌳数组

1，一维数组

🌼先说静态数组

常规用法，懂得都懂，注意数组过大时，考虑声明为全局变量或者vector

数组名表示地址

训练1-38：现在有n盏灯，编号为1~n，开始时所有灯都是关的，编号为1的人把1的倍数的灯开关按下（开的关上，关的打开），编号为2的人把2的倍数的灯开关按下...直到第k个人为止

给定n和k(0 < n, k <= 1000)，输出哪几盏灯是开着的

#include<iostream>
#include<cstring> //memset()
using namespace std;int main()
{int a[1010];memset(a, 0, sizeof(a)); //初始化每个元素为0int n, k;cin>>n>>k;//按下开关for(int i = 1; i <= k; ++i) //k的倍数for(int j = 1; j <= n; ++j)  //n盏灯if(j % i == 0)a[j] = !a[j]; //0的取1, 1的取0//输出结果for(int i = 1; i <= n; ++i) {if(a[i]) {if(i != 1)cout<<" ";cout<<i;}}return 0;
}

关键是代码第16行，a[j] = !a[j]

33 9
1 4 9 10 11 12 13 14 15 17 18 19 21 23 27 29 30 31

训练1-39：输入n个学生成绩，存入数组，求总成绩和平均成绩（浮点数）

为了练习数组参数函数

#include<iostream>
using namespace std;
int a[100];//(int a[], int n)等价于(int *a, int n)
int add(int a[], int n) { //数组作为参数, 不可以直接写a[n]int sum = 0;for(int i = 0; i < n; ++i)sum += a[i];return sum;
}int main()
{int n, s;float avg;cin>>n;for(int i = 0; i < n; ++i)cin>>a[i];s = add(a, n);avg = float(s) / n;cout<<s<<"\t"<<avg;return 0;
}

4
2 3 4 5
14      3.5

🌼再说动态数组

2）动态定义

在程序运行过程中，动态分配空间定义数组，一维数组动态定义：

类型说明符 * 数组名 = new[常量或变量表达式];
int *a = new int[n];

类型说明符 --> 元素类型；常量或变量表达式 --> 数组长度

使用new分配的数组，使用完毕后要用delete释放内存空间

delete[] 数组名
delete[] a;

注意

1，delete释放的是new分配的内存（不要释放其他的）

2，delete只能释放同一个内存块1次

3，new给实体分配内存，delete释放

4，new给数组分配内存，delete[]释放

5，对空指针使用delete是安全的

训练1-41：输入n个学生的成绩，并存入动态数组a[]，统计不及格人数

#include<iostream>
using namespace std;int count(int a[], int n) { //数组作为参数, 不可以直接写a[n]int sum = 0;for(int i = 0; i < n; ++i)if(a[i] < 60)sum++;return sum;
}int main()
{int n;cin>>n;int *a = new int[n]; //动态数组for(int i = 0; i < n; ++i)cin>>a[i];cout<<"no pass: "<<count(a, n);delete[] a; //释放内存return 0;
}

5
55 60 12 100 61
no pass: 2

🌼2，二维数组

1）静态定义

int a[2][4] = {{0,1,2,3},{7,2,9,5}};
int a[2][4] = {0,1,2,3,7,2,9,5};
int a[2][4] = {{0,1,2},{0}};

示例

#include<iostream>
using namespace std;void print(int a[][4])
{for(int i = 0; i < 2; ++i) {for(int j = 0; j < 4; ++j)cout<<a[i][j]<<" ";cout<<endl;}
}int main()
{int a[2][4] = {{0,1,2,3},{7,2,9,5}};print(a);cout<<endl;int b[2][4] = {0,1,2,3,7,2,9,5};print(b);cout<<endl;int c[2][4] = {{0,1,2},{0}};print(c);return 0;
}

0 1 2 3
7 2 9 50 1 2 3
7 2 9 50 1 2 0
0 0 0 0

⚪注意

将二维数组作为参数时，可以省略第1维长度，但必须指定第2维长度

int sum(int a[][5], int n);

2）动态定义

一个 m行n列的二维数组相当于m个长度为n的一维数组

int **array = new int*[m];for(int i = 0; i < m; ++i) {array[i] = new int[n]; //按行分配空间
}for(int i = 0; i < m; ++i) {delete[] array[i]; //按行释放空间
}delete[] array;

对比下一维和二维动态数组的声明

int *a = new int[n]; //一维
int **a = new int*[n]; //二维

训练1-42：蛇形填数，输入一个整数n，按照蛇形填写n * n矩阵

#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
//int a[100][100];int main()
{int n, x, y, total;cin>>n;int **a = new int*[n]; //指向指针的指针afor(int i = 0; i < n; ++i) {a[i] = new int[n]; //按行分配空间memset(a[i], 0, n*sizeof(int));}//输出初始化后的数组for(int i = 0; i < n; ++i) {for(int j = 0; j < n; ++j)cout<<setw(5)<<a[i][j];cout<<endl;}cout<<endl;x = y = 0;total = a[0][0] = 1;//预处理while(total < n*n) {while(y + 1 < n && !a[x][y + 1]) //向右a[x][++y] = ++total;while(x + 1 < n && !a[x + 1][y]) //向下a[++x][y] = ++total;while(y - 1 >= 0 && !a[x][y - 1]) //向左a[x][--y] = ++total;while(x - 1 >= 0 && !a[x - 1][y]) //向上a[--x][y] = ++total;}//输出蛇形矩阵for(int i = 0; i < n; ++i) {for(int j = 0; j < n; ++j)cout<<setw(5)<<a[i][j];cout<<endl;}//释放内存for(int i = 0; i < n; ++i)delete[] a[i]; //按行释放空间delete[] a;return 0;
}

具体解释下第11行和第14行

int **a = new int*[n]; //指向指针的指针a
memset(a[i], 0, n*sizeof(int));

第11行：定义一个指向指针的指针a，该指针指向一个有n个元素的指针数组，每个指针指向一个int类型数组

第14行：memset()函数，对一段内存空间置0，第1个参数是地址，第3个参数要赋值的字节数，所以是n*sizeof(int)

60    0    0    0    0    00    0    0    0    0    00    0    0    0    0    00    0    0    0    0    00    0    0    0    0    00    0    0    0    0    01    2    3    4    5    620   21   22   23   24    719   32   33   34   25    818   31   36   35   26    917   30   29   28   27   1016   15   14   13   12   11

🌳字符串

字符串，指存储在内存的，连续字节中的一系列字符

C++中字符串分为两种形式：C-风格字符串，C++string类字符串

🌼1，C-风格字符串

C-风格头文件#include<cstring>，默认以'\0'结束，在存储空间中不要忘了'\0'

定义方式1

字符数组

char a[8] = {'a','b','c','d','e','f','g','h'};

字符串

char a[8] = {'a','b','c','d','e','f','g','\0'};

定义方式2

字符串

char a[8] = "abcdefg";
char a[] = "affsdjkl;sd";

求长度

1，sizeof：

返回所占总空间字节数，整型/字符型的数组/指针均可

在编译时计算，因此sizeof不能返回动态分配的内存空间大小

2，strlen：

返回字符数组或字符串所占字节数，针对字符数组/指针

区分

cin：空格，制表符，换行符作为结束，因此只能接受一个单词（换行符保留）

getline：读取一行，直到遇到换行符

get：读取一行，直到换行符，但是换行符保留在输入序列中

#include<iostream>
using namespace std;int main()
{char s[100];cin.getline(s, 10); //读入9个字符, 最后一个默认'\0'cout<<s<<endl;//cin.getline(s, 10, ':'); //读到冒号停止//cout<<s<<endl;return 0;
}

(**sjd a221
(**sjd a2

🌼2，C++ string类字符串

C++ string类字符串的长度没有限制，头文件为#include<string>

它隐藏了字符串的数组性质，使用户可以像处理普通变量一样处理字符串

注意

1，string类字符串没有'\0'的概念

2，char数组使用了一组用于存储一个字符串的存储单元，而string变量使用了一个表示字符串的实体

关于长度：.length(), .size()

关于输入

string s;
cin>>s;
getline(cin, s);
getline(cin, s, ':');

训练1-45：输入一些字符串，对其进行复制，拼接，比较等操作

#include<iostream>
#include<cstring> //C 风格
#include<string> //C++风格
using namespace std;/* C-风格
strlen(): 长度
strcpy(): 复制
strcat(): 拼接
strcmp(): 比较
strchr(): 查找字符
strlwr(): 转小写
strupr(): 转大写
*//* string类
.size(), .length(),=,+,==,!=,>=,<=,find
*/int main()
{char s1[100];char s2[20] = "hello!";char s3[] = "a";char s4 = 'a';char s5[3] = {'a','b','c'};char s6[3] = {'a','b','\0'};cin>>s1;cout<<strlen(s1)<<endl;cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<" "<<endl;cout<<s5<<" "<<s6<<" "<<endl;cout<<"jasskfjalsjdl" "123"<<endl;cout<<"aslkjdalksjdl""123"<<endl;cout<<"asdkjasldkjal    123"<<endl;return 0;
}

HelloBoy
8
HelloBoy hello! a a
abca ab
jasskfjalsjdl123
aslkjdalksjdl123
asdkjasldkjal    123

解释下输出第4行为什么是abca ab而不是abc ab呢

因为先输出s5中存储的abc后，由于s5长度只有3，而其中字符数组abc长度为3，没有以空字符'\0'结尾，所以会输出s5后面的内存数据，直到误认为遇到了空字符'\0'，此时是a

所以最终输出abca ab

训练1-46：输入一行字符，统计单词个数

#include<iostream>
using namespace std;int countword(string s)
{int len = s.size(), i = 0, num = 0;while(i < len) {while(s[i] == ' ') //跳过连续空格i++;if(i < len) //单词数+1, 是i < lennum++;while(s[i] != ' ' && i < len) //跳过当前单词i++;}return num; //得到单词数
}int main()
{string s;getline(cin, s);cout<<countword(s);return 0;
}

I love you forever my son
6(一行空格)
0

训练1-47：输入3个字符串，找出其中最小的字符串

#include<iostream>
using namespace std;string minstr(string s1, string s2)
{if(s1 < s2)return s1;elsereturn s2;
}int main()
{string s1, s2, s3, Min;cin>>s1>>s2>>s3;Min = minstr(s1, minstr(s2, s3));cout<<Min;return 0;
}