物理

信竞 非常全面的知识点详解(涵盖C++、数据结构、算法)

1.程序基本结构

在C++程序中，我们使用的绝大多数指令都被封装在一个一个的头文件中，要想调用这些指令，我们得先引入他们所在的头文件，语法为

#include <头文件名称>

然后，我们要写上这样一行

using namespace std;

它的作用以后会讲

另外，C++程序有一个入口点，程序从这里开始运行，这就是主函数 ，语法为

int main (){

     代码

}

最后在主函数最后一行写上return 0;这是程序结束的标志，然而作为最后一行也可不写它，因为程序执行完主函数会自动结束。

最终基本模板如下

#include <头文件>

using namespace std;

int main (){

    return 0;

}

2.常量与变量及数学运算

常量，顾名思义，就是恒定不变的量。

比如，我们有一个数998244353，我们要经常使用这个量，那么每次用它的时候都要在程序里写上998244353这个量，非常麻烦。但如果我们用一个别的东西代替他，比如字母p，那么用它的时候写一个p就行，这就是定义了p这个常量，其值为998244353，定义常量语法如下：

const 数据类型 常量名称 = 值;

存储整数，数据类型常用int，取值范围为$-2^{31}到2^{31}-1$，即-2147483648到2147483647

举个例子(栗子 : 我恐高，别举我)

const int p = 998244353;

这就实现了开头那个例子

有一点发现了吗？结尾有分号！看看之前的using namespace std;也是这么写的。其实，一般而言每句代码末尾都要加上他，但也有例外，比如头文件引入。还有一些也不用加分号，以后再讲。

其实const还有一个写法是constexpr，简单了解即可。作者本人倾向于写后者。

变量呢？Very easy! 把常量修饰符去掉即可。语法为

数据类型 变量名 = 值;

这个值不用非得一开始就赋，可以只定义不赋值。语法为

数据类型 变量名;

也可以定义多个变量，中间用逗号隔开，前提是类型相同。

🌰:

int a = 114514, mod, p = 123;

后期可以对变量的值进行修改。语法为

变量名 = 新的值;

运算很简单，变量、常量、数值三者间可以随意搭配进行计算。

加法减法和数学中的写法一样，乘法为*，除法为/，这里的除法默认向下取整。

🌰:

constexpr int A = 3;

int b;

b = A / 2;

此时b值为1

这一切都要在主函数中写。其实也可以在主函数外写，以后细讲。

最后强调:

变量名常量名千万别乱取!命名规则:

1. 只能以数字，字母，下划线组成
2. 不得以数字开头
3. 不得用C++自带的指令

int main (){

    int a = 5；

    constexpr int c = 3；

    a = a * 5 / c;

    return 0;

}

加餐;

a = a + b;等价于a += b;

其余三者同理。

a = a + 1;等价于a++;或++a;区别以后讲。

减法同理。

4.指针和地址与输入输出函数

地址指的是计算机当中变量或常量或其他东西（如以后学的数组）的存储位置。

指针存储的就是他们的地址。

如果我们要定义一个指针，他存储一个某类型变量的地址，应该这样写

数据类型* 指针名 = &变量名;

这里有两个符号，介绍一下：

*在此处告诉计算机，新定义的这个东西是一个指针，不是普通的变量。

&叫做取地址运算符，用于获取他后面跟着的那个东西的地址。

比如我们有一个变量a，这样写

int* p = &a;

这样，p中就存储了a的地址。

输出p，就可以看到a的地址了。

地址一般长这样:

这是我电脑上运行的结果。

下一节就会讲他是什么意思，以及为什么以0x开头。

若我们想要获取指针指着的那个变量它的值，就要写*p，这里的*是解引用运算符。

🌰:

int a = 5;

int* p = &a;

cout << *p;

输出结果为5

当然，指针不用非得定义时就指向变量，只写int* p;也可以，不过最保险最正式的写法是int *p = nullptr;

nullptr叫做空指针，也可写NULL，建议写前者。

指针可以改变指向的变量。语法为

指针名 = 新变量的地址;

如p = &b;

这样p就指向了b。

输入输出函数很简单。

头文件:cstdio

输入为scanf("格式控制符"，变量地址);

对于int而言，格式控制符是%d

输入多个数据就多写几个%d

例如scanf("%d%d", &a, &b);

输出为printf("输出内容"，变量);

输出内容可以加格式控制符，变量可以不加。但加了%d之类的数据类型控制符必须跟上变量。

换行只能写'\n'

🌰：

已知a = 5;b = 4;

printf("happy %d\n%d", a, b);

输出为

happy 5

4

输出:

a

abc

对应的输入和输出:

第一行为输入，第二行为输出。

6.数据类型及其转化

先了解一下常用数据类型

int之前讲过，在此不再赘述。

short:同样也是整数，存储范围-32768到32767

long long:依旧是整数，存储范围$-2^{63}到2^{63}-1$

float:小数（浮点数），准确名称是单精度浮点数，小数精度约6到7位有效数字

double:双精度浮点数，小数精度约15到17位有效数字

bool:布尔值，只有0(false)和1(true)两种取值，常被用于标记真假(例如是否被访问过，是否满足要求等)

char:字符。

string讲过，不再赘述。

这些数据之间是可以相互转化的。

整数转小数很好理解。

小数转整数呢？计算机是这样处理的:直接把小数部分干掉!

比如double型的3.1415926转化成int型就是3

那如果要四舍五入呢？答案是:先加0.5再转化，自己举几个数试一下就会发现原理。

你可能想不到的是，字符和整数也可以互相转化。

依靠的是ASCII码，其中'A'为65，'B'为66，以此类推。'a'为97,同样往后推，'0'为48，同理往后推。

至于转化的语法呢？

法一:强制类型转化

(目标类型)(被转化的式子)

法二:安全类型转化

static_cast<目标类型>(被转化的式子)

🌰：

输出：

97

97

其实还有一种转化方式，叫做自动类型转化，比如int和double做运算时默认把int转double，结果为double

所以，直接两个整数相除，结果为整数，若先给被除数乘上一个1.0，让被除数变成double，这样计算结果也会变成double，例子如下：

输出：

1

1.5

加餐：

类型修饰符，unsigned表示无符号，使用它可以使得数据类型值非负，正数部分上限比原先增大了原本负数部分的值域大小。

例：unsigned int

练习题：

『原创编程题』

题目描述：

给定一个大写英文字母，输出它是第几个字母。

输入格式：

一行，一个英文字母。

输出格式：

一行，一个整数，表示第几个字母。

内存限制：

无

时间限制：

无

数据范围：

对于输入的英文字母，保证合法。

7.if-else if-else语句

首先先讲一下关系运算符，他们成立返回真(true)，不成立返回假(false)。

> 大于

< 小于

>= 大于等于

<= 小于等于

== 等于

!= 不等于

比如5 >= 4就为true，5 == 6就为false，很好理解。

if语句能根据条件是否成立而决定下一步做什么。

基本语法是：

if (条件){

    代码

}

条件别加分号！大括号后也别加分号！

如果条件成立，就执行大括号内的代码，不成立就跳过。

如果条件不成立，要执行某些代码，就写else

if (条件){

    条件成立时执行的代码

}

else{

    条件不成立时执行的代码

}

如果条件不成立还要再判断另一个条件，就用else if新增条件，在if条件不成立时就判断else if条件是否成立。

若多个else if存在，就挨个判断，一个成立，剩下的else if和else都跳过。

例如

模拟一下程序执行过程。

若输入a为5，if中的条件成立，输出1，跳过else if和else，程序结束。

若输入a为0，if中条件不成立，看else if条件，成立，输出2，跳过else，程序结束。

若输入a为-1，if中的条件不成立，看else if，也不成立，执行else，输出3，程序结束。

当if ，else if，else以及后续要学的for，while语句大括号内只有一句代码，大括号可以省略不写，如下

练习:

『原创编程题』

题目描述：

给定一个a (a∈Z)，输出他的绝对值。

输入格式：

一行，一个整数。

输出格式：

一行，一个整数，表示a的绝对值。

时间限制：

无。

内存限制：

无。

数据范围：

题目保证$-2^{63} ≤ a ≤ 2^{63} - 1 且 a∈Z$

8.switch-case-default语句

当有一个变量，他有不同的值，每一个值就对应一种结果，很容易想到if-else if-else语句。

还有另一种语句，专门用于处理这类问题，即本节内容。

先摆上语法：

switch (变量名){

    case 值1：语句1；break；

    case 值2：语句2；break；

}

当变量值为值1时执行语句1，变量值为值2时执行语句2，所有case以此类推。当所有case都没有匹配上，执行default的语句，当然，default也可以不写。

🌰：

输入a，a值为1时输出"one"，a值为2时输出"two"，a值为3时输出"three"，都不是输出"no"。

练习题：

编写代码，输入一个字符，用switch语句处理他，使得无论输入什么字符，输出总是'A'。

9.for循环

循环，顾名思义就是重复地做一件事。

for循环的基础语法如下：

for (循环初始化；循环条件；循环迭代){

    循环体

}

循环初始化就是执行到for循环时，先执行初始化语句。

然后判断循环条件是否满足，若满足，就执行循环体（就是要重复执行的代码），然后进行循环迭代（一轮循环结束后对变量等进行修改）。接下来再判断循环条件是否满足，就是一直走刚刚所述的流程（不包括初始化），直到条件不满足为止。

比如要循环n次，就可以定义一个用于统计循环次数的变量i，从1开始，直到i > n为止，也就是循环需满足i <= n，每次循环完就把i加1，表示循环完的轮数增加了1。也就是说，初始化int i = 1，条件i <= n，迭代i++

即for (int i = 1；i <= n；i++)

由for循环的底层原理可知，在循环的时候，i的值是会不断改变的。像这样，在循环中的变量，称为循环变量。而循环变量的值也是可以像一般的变量一样输出的。🌰：

输出1到10之间所有整数

其实for循环三个部分不一定都要写，甚至三个部分都不写（无限循环）。

比如for (int i = 1；i <= 10；)

再比如for (；i > 0；)

加餐(别噎着)：

从初始值循环到终止值，循环变量每次都增减某个固定的常数，这种循环就是形如for (int i = 初始值；i 大小关系 终止值；i 增或减 常数)的循环，一开始的那个例子就是。在这种循环中，循环变量每次改变的值称为循环的步长。

步长是可以改变的。比如，输出[1,n]之间所有的奇数，由于1本身是奇数，相邻两个奇数相差2，故可以这样写

饭后甜点(小心血糖飙升):

有没有发现刚刚加餐里的那种循环，在步长为1和终止值大于初始值的时候，for循环和数学上的$\sum$求和很像？

小练习:

利用for循环求值$\sum_{i=1}^{10}i^2$

10.while循环和do-while循环

while循环，可以理解成只有循环条件的for循环。基本语法为:

while (条件){

    循环体

}

当条件成立时，执行循环体。他等价于for (；条件；)。乍一看，这不有for循环就行了？搞出个while循环干啥？

代码要注重可读性，这在你写完代码后回头看的时候会体现出来。while循环是不是比他等价的for循环更美观？况且那种三个部分都有的for循环特别常见，写习惯了他们就不习惯这种缺两项的for循环。

while循环可以干啥呢？仔细看一看，只要同条件满足，就一直执行循环体。所以while循环可以被用来榨干某些东西。

先讲一讲模运算。符号为%，用于计算两个数相除的余数。

判断偶数的方法：当且仅当a % 2 == 0成立。等于1就是判断奇数，很好理解。

有了这一点，我们就可以榨干一个偶数的所有因子2。

🌰：给出一个数，若他是偶数，就不断地除以2，直到它是奇数，并输出最终剩下的数。参考代码：

do-while循环先执行循环体，再根据条件来判断是否进入下一次循环。

语法：

do{

    循环体

}while(条件)；

例如，给定一个数，不管他是啥，先除以2，向下取整，再榨干全部质因子2。代码：

练习题：

『原创编程题』

题目描述：

给定一个数$a$，判断素因子$2$和$3$谁多，输出较多者的个数。

输入格式：

一行，一个数$a$。

输出格式：

一行，一个整数，含义如题目所述。

时间限制：

无。

内存限制：

无。

数据范围：

题目保证$a∈N^{*}，a ≤ 10^5，6|a$