1. 四级新增知识框架

• 函数声明、定义、调用。
• 形参、实参、全局/局部作用域。
• 值传递、引用传递、指针传递。
• 指针定义、赋值、解引用。
• struct 结构体。
• 二维/多维数组。
• 递推算法与递推关系。
• 冒泡、插入、选择排序；稳定性；时间/空间复杂度。
• 文件重定向、文件读写。
• 异常处理。

2. 函数三要素

返回值类型 函数名(参数列表) {
    函数体;
    return 返回值;
}

例如：

int add(int a, int b) {
    return a + b;
}

概念	含义
函数声明	告诉编译器函数接口，如 int add(int,int);
函数定义	给出函数完整实现
函数调用	add(2,3)
形参	定义函数时的参数变量
实参	调用函数时给出的实际值/变量

3. 作用域

类型	定义位置	生效范围
全局变量	所有函数之外	从定义处到文件相应可见范围
局部变量	函数/语句块内部	当前块内

局部变量与全局变量同名时，局部变量通常遮蔽全局变量。

4. 三种参数传递

方式	形参写法	修改形参会影响实参吗	典型用途
值传递	void f(int x)	否	只读小对象
引用传递	void f(int &x)	是	修改实参、避免拷贝
指针传递	void f(int *p)	通过 *p 可修改	地址操作、数组等

const 引用【辅助补充】

void print(const string &s);

表示不修改对象，同时避免大对象复制。

5. 指针

int a = 10;
int *p = &a;
*p = 20;

符号	含义
&a	取变量 a 的地址
int *p	声明指向 int 的指针
*p	解引用，访问指针指向的对象
nullptr	空指针【辅助补充】

数组与指针基础：数组名在很多表达式中会转换为指向首元素的指针，但数组与指针并不是同一种类型。

6. 结构体

struct Student {
    string name;
    int score;
};

Student s;
s.name = "Tom";
s.score = 95;

指针访问成员：p->score 等价于 (*p).score。

7. 二维与多维数组

int a[100][100];

二维数组 a[n][m] 可理解为 n 行、每行 m 个元素。

典型遍历：

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];

总访问次数约为 $n\times m$。

8. 递推

**递推：**从已知的较小状态出发，按照确定的关系逐步计算更大状态。

例如 Fibonacci：

• $f_1=1$
• $f_2=1$
• $f_n=f_{n-1}+f_{n-2}$

递推三要素：

1. 状态含义。
2. 初始状态。
3. 递推关系与计算顺序。

**递推 ≠ 递归。**递推通常用循环从小到大算；递归是函数自己调用自己，五级重点学习。

9. 三种基础排序

排序	核心思想	最坏时间	额外空间	稳定性
冒泡排序	相邻逆序就交换，大元素逐步“冒”到后面	$O(n^2)$	$O(1)$	稳定
插入排序	将当前元素插入前面已有序区间
选择排序	每轮找最小/最大元素放到目标位置			不稳定

冒泡排序骨架

for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

插入排序骨架

for (int i = 1; i < n; i++) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = x;
}

选择排序骨架

for (int i = 0; i < n - 1; i++) {
    int p = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[p]) p = j;
    swap(a[i], a[p]);
}

10. 稳定排序定义

若两个元素关键字相同，排序后它们的相对先后顺序不变，称排序稳定。

11. 简单复杂度估算

代码结构	典型时间复杂度
常数条语句	$O(1)$
一重 n 次循环	$O(n)$
两重各 n 次循环	$O(n^2)$
三重各 n 次循环	$O(n^3)$
每次规模减半	$O(\log n)$
枚举所有二进制选择	常见 $O(2^n)$

复杂度忽略常数和低阶项，例如 $3n^2+10n+5$ 记为 $O(n^2)$。

12. 文件重定向与文件读写

freopen

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

fstream【辅助补充】

#include <fstream>
ifstream fin("input.txt");
ofstream fout("output.txt");
int x;
fin >> x;
fout << x;

模式	含义
r	读
w	写，通常覆盖原内容
a	追加

13. 异常处理

try {
    if (bad) throw 1;
} catch (int e) {
    // 处理异常
}

关键字	作用
try	包含可能出异常的代码
throw	抛出异常
catch	捕获并处理异常

14. 四级必背易错点

1. 形参和实参不是同一概念。
2. 值传递修改形参不影响实参；引用/指针可影响。
3. & 在声明 int &x 中表示引用，在表达式 &a 中表示取地址。
4. * 在声明 int *p 中表示指针类型，在表达式 *p 中表示解引用。
5. 递推和递归不要混淆。
6. 选择排序通常不稳定。
7. 多重循环复杂度要结合边界，不是看到两层就一定 $O(n^2)$。

15. 四级背诵清单

• [ ] 函数声明/定义/调用、形参/实参、作用域。
• [ ] 值/引用/指针传递区别。
• [ ] 指针 & 与 *。
• [ ] 结构体和二维数组。
• [ ] 递推三要素。
• [ ] 冒泡/插入/选择：思想、复杂度、稳定性。
• [ ] freopen、try/throw/catch。