本文将从算法题的角度重新梳理 C/C++ 语言。

一、C/C++

1.用什么语言

以 C 语言为主，同时也使用 C++ 中一些好用的特性。

2.两种输入输出

(1) scanf 和 printf

scanf("%d", &a);
printf("%d", a);

(2) cin 和 cout

cin >> a;
cout << a;

(3) 选择

虽然 cin 和 cout 可以不指定输入输出格式，使用起来比较方便，但是其消耗时间相比 scanf 和 printf 更多。

因此，尽量使用 scanf 和 printf 。

(4) 注意事项

不要再一个程序中同时使用 cout 和 printf ，可能会出现错误。

3. 文件扩展名

将代码保存为 .cpp 文件，防止因为使用了 C++ 的部分特性而在纯 C 编译中出错。

​

二、数据类型

更详细的学习笔记：（纯 C 版）

学习笔记-C语言-第一章-数据类型 - LD’s BLOG

1.变量定义

(1) 变量

变量是在程序运行过程中其值可以改变的量，需要在定义后使用。

(2) 变量名

① 不能是 C 语言标识符

② 第一个字符必须是字母或下划线

③ 区分大小写

2.变量类型

(1) 整型

① int

绝对值在 10⁹ 以内的整数都可以定义为 int 型。

② long long

如果 long long 型赋大于 2³¹ - 1 的初值，则需要在数值后面加上 LL ，否则会编译失败。

(2) 浮点

① float

单精度浮点

② double

双精度浮点

③如何选择？

用double

(3) 字符

①字符常量

用单引号标注，例如：

'a','1','\n'

②ASCII码

A ---- 65
a ---- 97

小写字母的 ASCII 码比对应的大写字母大 32 。

③转义字符

\n ---- 换行
\0 ---- 代表空字符

‘\0’ == 0 ≠ ‘0’

(4) 字符串

①字符串常量

用双引号标注，例如：

"Hello World！"

②以 ‘\0’ 作为字符串结束的标志

③注意区分字符数组和字符串

末尾有 ‘\0’ 的才能称作字符串

(5) 布尔

①使用

C++ 中可以直接用，

C 中需要 #include <stdbool.h> 。

②赋值

给布尔变量赋值时，

数值为 0 则赋值 0 ，表 false；

数值非 0 则赋值 1，表 true。

3.类型转换

(1) 自动类型转换

若一个表达式中含有不同类型的变量和常量，在计算时，会自动将它们转换为统一类型。具体有：

①表达式中出现浮点数，会统一转换为双精度浮点，即 double 类型。

②浮点数赋值给整型，会舍弃小数部分。

(2) 强制类型转换

( 类型 ) ( 表达式 )

4.符号常量和const常量

(1) 符号常量

#define PI (3.14)

(2) const常量

const int PI = 3.14

(3) 二者的区别

①编译程序会在编译前进行预处理，将宏定义转化为对应语句。符号常量会被替换为对应数字。 符号常量仅仅是一个临时的符号 。

② const常量 只能在定义时赋值。const常量 仍然是变量，有数据类型，占存储空间，但无法改变其数值。

③更推荐 const常量 的写法，除非给能加的地方都加上括号。

5.运算符

(1) 算术运算符

①除

当二者都是整数时，会舍去小数部分；

当二者有一个是浮点时，自动按浮点计算。

②自增

i++  ---- 先运算后自增
++i  ---- 先自增后运算

③取模

要求两个数都是整数

(2) 关系运算符

>,>=,<,<=,==,!=

(3) 逻辑运算符

运算符	含义	举例	说明
&&	与	a&&b	仅当a，b同时为真时，结果为真
||	或	a||b	a，b有一个为真，则结果为真
！	非	!a	若a真，则结果为假；若a假，则结果为真

a&&b：当 a 为假时，表达式一定为假，不再判断 b

a||b：当 a 为真时，表达式一定为真，不再判断 b

(4) 条件运算符

条件 ? 语句1 : 语句2 ;

判断条件，

若真则执行 语句1 ，整个条件表达式的值为 语句1 的值；

若假则执行 语句2 ，整个条件表达式的值为 语句2 的值；

(5) 位运算符

位运算符运用较少，在算法题中，较常用的是左移运算符，用于构建无穷大。

int的取值范围为 -2³¹ ~ 2³¹ - 1，因此无穷大可以设置为(1 << 31) - 1 。

为避免相加超过 int 的情况，一般使用 2³⁰ - 1

const int INF = (1 << 30) - 1;
等价形式：
const int INF = 0x3fffffff;

​

三、顺序结构

1.赋值表达式

(1) 一般形式

int a = 5;

(2) 复合赋值

n /= m + 1;
等价于：
n = n / (m + 1);

2.scanf/printf

(1) scanf

scanf("格式声明", 地址);

除了读入字符外，scanf 都是以空白符（空格、回车、TAB等）为结束判断标志，因此都会默认跳过空格。

此外，读入字符数组时，会以空白符作为读入结束的标志。

(2) printf

printf("格式声明", 值);

(3) 常见变量及其格式符号

数据类型	输入格式	输出格式
int	%d	%d
long	%ld	%ld
long long	%lld	%lld
float	%f	%f
double	%lf	%f
char	%c	%c
str	%s	%s

(4) 输出格式

%m.nf

小数点后保留 n 位，最少输出 m 位（前+小数点+后 >= m），不足用空格填补。

%0m.nf

小数点后保留 n 位，最少输出 m 位（前+小数点+后 >= m），不足用 0 填补。

3.getchar/putchar

c = getchar();

putchar(c);

getchar() 可用于吸收空格等符号

4.typedef

用于给数据结构起别名，例如：

typedef int I;

typedef struct{
	int data;
	int flag;
}Node;

5.常用 math 函数

(1) fabs 绝对值

用于对 double 类型的变量取绝对值。

int abs(int x);  // 整型取绝对值

double fabs(double x);  // 浮点取绝对值(整型也能用)

(2) floor 和 ceil 取整

分别用于对 double 型变量向下取整和向上取整。

double num1 = -5.2;
double num2 = 5.2;
printf("%f %f", floor(num1), ceil(num1));  // -6 -5 
printf("%f %f", floor(num2), ceil(num2));  //  5  6

(3) pow 次方

double pow(double x, double y);

该函数用于返回 x^y 。

(4) sqrt 平方根

double sqrt(double x);

用于返回变量的算术平方根。

(5) log 求对数

double log(double x);

返回 x 以 e 为底的对数，即 ln x 。

注意：

C 语言中没有对任意底数求对数的函数，因此若要求以某数为底的对数，需要借助换底公式。（log_ab = ln b / ln a）

(6) sin cos tan 三角函数

函数定义：

double sin(double x);

函数调用：

#define 3.14 PI
double num = sin(x / 360 * 2 * PI);

(7) asin acos atan 反三角函数

函数定义:

double asin(double x);

函数调用：

double angle = asin(num);

(8) round 四舍五入

用于将变量四舍五入，化为 double 型的整数。

double round(double x);

​

四、选择结构

1.if

if(表达式){
    语句1;
}else{
    语句2;
}

(1) 判断语句的简化

if (n)
if (!n)

(2) if 的嵌套

else 总是与最近的 if 配对（除非在不同的代码块内）

2.switch

switch(表达式){
    case 1:
      语句1;
      break;
    case 2:
      语句2;
      break;
    ...
    default:
      语句n;
}

• 先计算表达式的结果（表达式结果只能是整数）
• 假设结果为 n，则执行 case n: 之后的语句
• 若结果没有对应语句，则执行 default: 之后的语句
• case n: 仅起指示作用而不起分隔作用，若没有 break ，则会从 case n: 之后一直执行到 switch 结束

​

五、循环结构

1.while

while(循环条件){
    循环体;
}

当循环条件为 真 时，执行循环体，继续判断循环条件；当循环条件为 假 时，停止循环。

循环体应该能使循环条件发生改变，否则就会死循环。

条件为假时，一次都不执行。

2.do while

do{
    循环体;
}while(循环条件)

①先执行一次循环体；

②判断循环条件，为 真 时执行循环体，继续判断循环条件；为 假 时停止循环。

至少执行一次代码块。

3.for

for(初始语句;循环条件;末尾循环体){
    循环体;
}

①先执行初始语句，初始语句会且仅会被执行一次；

②判断循环条件，当循环条件为 真 时，执行循环体，执行末尾循环体，继续判断循环条件；

③判断循环条件，当循环条件为 假 时，停止循环。

4.break

用于跳出循环，即跳出整个循环，并继续执行循环之后的语句。

5.continue

用于结束本轮循环，（若是 for 循环，仍会执行末尾循环体），继续执行下一轮循环。

多层嵌套循环时， break 和 continue 只对一层有效

​

六、数组

1.一维数组

(1) 概念

数组就是从某个地址开始连续若干个位置形成的元素集合。

(2) 定义

类型 数组名称[数组大小];

数组大小必须是整数常量

若要使用整数变量，请动态分配

(3) 访问

数组名称[下标]

下标范围为： 0 ~ 数组大小 - 1

(4) 初始化

int a[10] = {3, 5, 2};

• 用被大括号括住，并由逗号隔开的若干数组赋值
• 赋值一部分后，剩下未被赋值的元素默认初始化为 0（也可能是很大的随机数，视编译器而定）

2.冒泡排序

依次比对并排序相邻的两项，每一趟将一个数字沉底，直至一趟排序中没有发生交换为止。

void Bubble(int A[], int n){
	for (i = n - 1; i >= 1; i--){
		flag = 0;
		for (j = 1; j <= i; j++){
			if (A[j - 1] > A[j]){
				swap(A[j - 1], A[j]);
				flag = 1;
			}
		}
		if (flag == 0)  return;
	}
}

3.二维数组

(1) 定义

二维数组是一维数组的扩展，其格式如下：

数据类型 数组名称[数组大小1][数组大小2];

(2) 访问

数组名[下标][下标]

(3) 理解

可以将二维数组看作每一个元素都是一个数组的数组。

例如int a[2][5] ，可以看作数组 a 有两个元素，每个元素又分别是一个长度为5的一维数组。

(4) 初始化

①分别给每行赋值：

int a[2][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}};

②也可以不加括号：

int a[2][4] = {1, 2, 3, 4, 5, 6, 7, 8};

② 的效果与 ① 相同，但 ① 的形式更不容易出错。

③对部分元素赋初值：

int a[2][4] = {{1}, {5, 6}};

仅对部分元素赋初值，未赋值元素自动初始化为 0

④省略 数组大小1：

int a[ ][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}};

(5) 特别提醒

如果数组大小较大（大概 10⁶ 级别），则需要将其定义在主函数外，否则会使函数异常退出。

原因是：

局部变量分配至动态存储区，由于系统栈的空间相对较小，将会异常退出。

而全局变量分配至静态存储区，允许的空间更大。

4.memset

(1) 格式

memset(数组名, 值, sizeof(数组名));

(2) 前置条件

#include <string.h>

(3) 函数原理

对数组的每个字节赋相同的值。

int a[5];
memset(a, 1, sizeof(a));

此段代码会将 a 中的每个元素中的每个字节赋值为 1 ，

例如 a[0] ：

0000 0001,0000 0001,0000 0001,0000 0001

结果使得 a[0] 的值为 16843009，而不是想象中的 1 。

(4) 建议用法

①

memset(数组名, 0, sizeof(数组名));

将数组各元素置为 0

②

memset(数组名, -1, sizeof(数组名));

将数组各元素置为 -1

5.字符数组

(1) 初始化

char str[] = {'h','e','l','l','o'};

若要通过此方法定义字符串，应指定数组大小（大于等于元素个数+1），或在后面大括号中增加末尾的’\0’

char str[] = "hello";

此段代码的本质是将“常量”的字符串复制到数组中，因此会复制所有元素，以及末尾的结束符号。

(2) 输入输出

① scanf/printf

%s – 字符串

%c – 字符

② getchar/putchar

a = getchar();
putchar(a);

③ gets/puts

gets 并不安全

技术分享 不安全的gets() - LD’s BLOG

(3) 字符数组的存放方式

字符数组由若干个 char 类型的元素组成，因此字符数组的每一位都是一个 char 字符。

在字符串中，末尾以空字符 '\0' 表示字符串的结束，因此有结束标志的字符数组，才能被称作字符串。

6.string.h

(1) strlen

strlen(字符串);

返回字符串的长度。

(2) strcmp

strcmp(字符串1, 字符串2);

比较 字符串1 和 字符串2 的大小，若相等返回0；

若 字符串1 更大则返回正数；

若 字符串2 大则返回负数。

比较方法与字典单词排序类似：

从首字母开始，按 ASCII 值比较，不相等则结束比较返回结果，相等则继续比较下一位。

小写字母大于大写字母。

(3) strcpy

strcpy(字符串1, 字符串2);

将 字符串2 复制给 字符串1 。

(4) strcat

strcat(字符串1, 字符串2);

将 字符串2 连接到 字符串1 之后。

7.sscanf和sprintf

(1) sscanf

sscanf(str, "%d", &n);

将 字符串str 中的内容以 %d 的格式写入到 n 中。

例如：

int n;
char str[10] = "123";
sscanf(str, "%d", &n);
printf("%d", n);

输出结果：

123

(2) sprintf

sprintf(str, "%d", n);

将 n 以 %d 的格式写入到 字符串str 中。

例如：

int n = 123;
char str[10];
sprintf(str, "%d", n);
printf("%s", str);

输出结果：

123

(3) 高阶应用

int num1;
double num2;
char str[100] = "2048:3.14:hello";
char str2[100];
sscanf(str, "%d : %lf : %s", &num1, &num2, str2);
printf("%d\n%lf\n%s", num1, num2, str2);

输出结果：

2048
3.14
hello

​

七、函数

1.函数的定义

(1) 函数是什么

函数是一个实现一定功能的语句的集合。

(2) 定义

返回值类型 函数名称(参数表){
	代码块;
}

(3) 形参实参

①全局变量

定义后在所有代码块中都有效的变量。

②局部变量

在代码块中定义，且只在代码块中生效的变量，程序跳出代码块后便会被销毁。

③形参

int add(int x, int y);  //函数参数表中的x和y

④实参

add(a, b);  //调用函数时的参数

⑤值传递

实参的值会被拷贝给形参，因此，函数能够获得数值，并根据它进行运算，却无法改变数值。

2.main函数

主函数有且只能有一个，并且无论主函数写在哪个位置，程序一定是从主函数开始执行，并在需要调用其它函数时再去调用。

3.以数组作为函数参数

(1) 形参

数组可以作为函数参数，且数组作为参数时，数组中的第一维不需要填写长度。

void fun(int a[]);

如果是二维数组，那么第二维需要填写长度。

void fun(int a[][10]);

(2) 实参

调用时只需要填写数组名。

fun(str);

(3) 可修改

数组作为参数时，在函数中对数组元素的修改就等同于对原数组元素的修改。

4.函数的嵌套调用

可以在一个函数中调用另一个函数。

5.函数的递归调用

可以在函数中调用自身。

int fun(int x){
	if(n > 1)  return n * fun(n - 1);
	else  return 1;
}

​

八、指针

1.什么是指针

指针是一个变量，其值为另一个变量的地址。

2.指针变量

指针变量用于存放地址。

int *p = &a;

p -- 地址    *p -- 值
a -- 值      &a -- 地址

3.指针变量加减法

指针与指针可以减法，其结果就是两个地址偏移的距离（(地址1 - 地址2) / 单位大小）；

指针与指针的加法没有意义。

指针可以自增自减，指针的地址将会自增或自减一个单元。

4.指针与数组

(1)

数组实际上是 const 类型的指针，是一种无法修改指向的指针。

int *const q = &a;

不能修改指针的指向

const int *q = &a;

可以修改指针的指向，但不能通过指针修改值

(2)

数组名称可以作为数组的首地址使用。

a ---- &a[0]

(3)

对偏移量的应用：

a + i ---- a[i]

(4)

数组自身不可以自增自减，但可以新建指针指向它，从而实现遍历等操作。

int i;
int *q = a;
for (i = 0; i < 10; i++, p++)
	printf("%d", *p);

5.指针变量作为函数参数

指针类型也可以作为函数参数，调用时将变量的地址传入函数。若在函数中对这个地址中的元素进行改变，原先的数据也会被改变。

void add(int *p){
	(*p)++;
}
int main(){
	int a = 5;
	add(&a);
	printf("%d", a);
}

运行结果：

6

6.常见错误

int *p;
*p = 12;

定义一个指针变量，没有让它指向任何变量，就开始使用它。

错误原因在于：

指针在定义时会随机初始化，如果没有修改它的指向，它就将指向某个未知的区域。使用这个指针时，就会修改未知区域的值，可能引发不可知的错误。

7.引用

(1) 引用的含义

引用是 C++ 的特性，引用不产生副本，而是给原变量起了一个别名，且对引用变量的操作就是对原变量的操作。

(2) 引用的使用

void add(int &x){
	x++;
}
int main(){
	int a = 5;
	add(a);
	printf("%d", a);
}

运行结果：

6

(3) 指针的引用

void swap(int *&p1, int *&p2){
	int *temp = p1;
	p1 = p2;
	p2 = temp;
}
int main(){
	int a = 1, b = 2;
	int *p1 = &a;
	int *p2 = &b;
	swap(p1, p2);
	printf("%d %d", *p1, *p2);
}

运行结果：

2 1

​

九、结构体

1.定义

struct Name{
	int data;
	int gender;
	struct Name *next;
}name1, name2;

其中，

Name 是结构体的类型名，

name1， name2 是在定义结构体时一起定义的两个变量。

也可以采用分开的写法：

struct Name{
	int data;
	int gender;
	struct Name *next;
};

struct Name name1;
struct Name name2;

2.typedef

typedef struct Name{
	int data;
	int gender;
	struct Name *next;
}Name;

typedef 用于给一个复杂的数据结构起别名，用此方法定义后便可以使用更简单的别名定义结构体变量。

将 结构体类型名 和 别名 设置为相同，可以避免很多麻烦。

Name name1;
Name name2;

3.结构体的嵌套

(1) 结构体可以包含其它结构体

struct SIMPLE{
	int data;
}
struct COMPLEX{
    char string[100];
    struct SIMPLE a;
};

(2) 结构体可以包含指向同类的指针

struct NODE{
    char string[100];
    struct NODE *next_node;
};

4.访问结构体

定义一个结构体：

struct NODE{
	int id;
	int data;
	struct NODE *next;
};

定义一个结构体变量和结构体指针：

struct NODE node;
struct NODE *p = (struct NODE *)malloc(sizeof(struct NODE));

(1) 访问结构体变量中的元素

node.id = 2e2382;
node.data = 3;

(2) 访问结构体指针中的元素

法一：

(*p).id = 2e2382;
(*p).data = 3;

法二：

p->id = 2e2382;
p->data = 3;

5.结构体初始化

(1) 逐一赋值

struct NODE node;

node.id = 2e2382;
node.data = 3;

(2) 构造函数

①默认构造函数

构造函数是用于初始化结构体的一种函数，它直接定义在结构体中，不需要写返回类型，且函数名与结构体名相同。

一般来说，对一个普通定义的结构体，其内部会生成一个不可见的默认构造函数。因此，才可以直接定义结构体变量而不进行初始化。

②自己构建构造函数

struct NODE{
	int id;
	int data;
	NODE(int xid, int xdata){
		id = xid;
		data = xdata;
	}
};

struct NODE node(324213, 99);

③覆盖问题

如果自己定义了构造函数，则不能不经初始化就定义结构体变量，因此可以手动加上一个无参数无函数体的空构造函数。同时，只要参数个数和类型不完全相同，一个结构体内可以定义多个构造函数，以适应不同场景下的初始化。

struct NODE{
	int id;
	int data;
	
	NODE(){}    //用于不初始化定义变量
	
	NODE(int xid){  //只初始化id 定义变量
		id = xid;
	}
	
	NODE(int xid, int xdata){  //用于全参数定义变量
		id = xid;
		data = xdata;
	}
};

​

十、补充

1.cin和cout

cin 和 cout 是 C++ 的输入输出函数，无需指定格式，使用更加方便。

需要 #include <iostream> 和 using namespace std; 才能使用。

(1) cin

输入：

cin >> a;

输入多个变量以及数组：

cin >> a >> b >> str;

输入一整行：

char str[100];
cin.getline(str, 100);

如果是 string 容器，则需要通过以下方式输入：

string str;
getline(cin, str);

(2) cout

输出：

cout << a << b << str;

输出，加上空格：

cout << a << " " << b << " " << str;

输出，加上字符串：

cout << "a=" << a << "b="  << b << "str=" << str;

两种换行方式：

cout << a << "\n";

cout << a << endl;

控制输出精度：

#include <iomanip>

cout << setiosflags(ios:fixed) << setprecision(2) << 123.4567 << endl

输出结果
123.46

(3) 选用

尽量使用 scanf 和 printf 。

2.浮点数的比较

在 C语言 中，浮点数并不精确，实际上是近似地表达数值，实际数值与存储数值之间存在一个较小地误差。

(1) 等于

引入一个小数，当数值之差小于这个小数时，便将两数视为相等。

const double eps = 1e-8;
#define Equ(a, b) ((fabs((a) - (b)) < (eps))

如此，便可以用 Equ(a, b) 判断两数是否“相等”，例如：

if (Equ(a, b)){

}
if (!Equ(a, b)){

}

(2) 大于

#define More(a, b) (((a) - (b)) > (eps))

(3) 小于

#define Less(a, b) (((a) - (b)) < (-eps))

(4) 大于等于

#define MoreEqu(a, b) (((a) - (b)) > (-eps))

(5) 小于等于

#define Less(a, b) (((a) - (b)) < (eps))

3.圆周率

const double PI = acos(-1.0);

​

参考

• 算法笔记