第1章 函数

1.1 函数详解

1.1.1 函数的基本概念与定义

函数是C++程序的基本组成单位，它将一段具有特定功能的代码块封装起来，通过函数名可以被多次调用，从而提高代码的复用性、可读性和可维护性。

函数定义语法

返回值类型 函数名(参数列表) {
    // 函数体：实现函数功能的语句块
}

各部分说明

• 返回值类型：表示函数执行完毕后返回的数据类型，如int、double、void（表示无返回值）等
• 函数名：遵循标识符命名规则，用于标识函数，应体现函数的功能
• 参数列表：由零个或多个参数组成，每个参数需指定类型和名称，多个参数之间用逗号分隔
• 函数体：用花括号{}包裹的语句块，包含实现函数功能的具体代码

示例

// 定义一个计算两个整数之和的函数
int add(int a, int b) {
    int sum = a + b;
    return sum;  // 返回计算结果
}

// 定义一个无返回值、无参数的函数，用于输出信息
void printHello() {
    cout << "Hello, Function!" << endl;
}

1.1.2 函数的参数

函数的参数是函数与外部进行数据交互的接口，位于函数定义的参数列表中，也称为形式参数（简称形参）。

1.1.2.1 普通参数

普通参数具有具体的类型和名称，用于接收函数调用时传递的具体值。

// 计算矩形面积，width和height为普通参数
double calculateArea(double width, double height) {
    return width * height;
}

1.1.2.2. 默认参数

在函数定义时为参数指定默认值，当函数调用时未提供该参数的值，将使用默认值。

// 带默认参数的函数，discount默认值为0.9
double calculatePrice(double originalPrice, double discount = 0.9) {
    return originalPrice * discount;
}

// 调用示例
int main() {
    cout << calculatePrice(100) << endl;        // 使用默认折扣0.9，输出90
    cout << calculatePrice(100, 0.8) << endl;   // 传入折扣0.8，输出80
    return 0;
}

注意：

• 默认参数必须从右向左定义
• 在函数声明和定义中只能指定一次默认值

1.1.2.3. 占位参数

只有参数类型，没有参数名称的参数，通常用于函数重载或后续扩展。

// 占位参数int，调用时需传递一个int类型的值
void func(int a, int) {
    cout << "a = " << a << endl;
}

// 调用示例
int main() {
    func(10, 20);  // 第二个参数20传递给占位参数，输出 a = 10
    return 0;
}

1.1.3 函数的声明

函数的声明是指告诉编译器函数的名称、返回值类型和参数列表，以便编译器在函数被调用时能够正确检查参数和返回值。

声明的作用

当函数定义在调用之后时，必须先声明函数，否则编译器会报错。函数声明可以放在函数调用之前，通常放在头文件中或源文件的开头。

// 函数声明
int max(int x, int y);

int main() {
    int a = 10, b = 20;
    cout << max(a, b) << endl;  // 调用函数，此时编译器已知max函数的信息
    return 0;
}

// 函数定义（在调用之后，需先声明）
int max(int x, int y) {
    return x > y ? x : y;
}

1.1.4 变量的作用域

变量的作用域是指变量在程序中能够被访问的有效范围，根据作用域的不同，变量可分为局部变量和全局变量。

1.1.4.1 局部变量

在函数内部或代码块（如if、for语句块）中定义的变量，其作用域仅限于定义它的函数或代码块内部。

void func() {
    int a = 10;  // 局部变量，作用域为func函数内部
    
    if (a > 5) {
        int b = 20;  // 局部变量，作用域为if语句块内部
        cout << a + b << endl;  // 正确，a和b在作用域内
    }
    
    // cout << b << endl;  // 错误，b的作用域已结束
}

1.1.4.2. 全局变量

在所有函数外部定义的变量，其作用域是从定义位置开始到整个程序结束，可被多个函数访问。

int globalVar = 100;  // 全局变量

void func1() {
    cout << globalVar << endl;  // 正确，可访问全局变量
}

void func2() {
    globalVar = 200;  // 可修改全局变量
    cout << globalVar << endl;
}

int main() {
    func1();  // 输出100
    func2();  // 输出200
    cout << globalVar << endl;  // 输出200，全局变量已被修改
    return 0;
}

注意事项

• 当局部变量与全局变量同名时，在局部变量的作用域内，局部变量会屏蔽全局变量
• 应尽量避免过多使用全局变量，以免导致变量被意外修改，降低代码的可维护性

1.1.5 函数的调用

函数调用是指使用已定义的函数来执行其功能，调用时需提供与函数参数列表匹配的实参（无参数时省略）。函数调用时传递给形参的具体值称为实际参数（简称实参）。

调用形式

函数名(实参列表);

示例

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

void printInfo(string name, int age) {
    cout << "姓名：" << name << ", 年龄: " << age << endl;
}

int main() {
    int sum = add(3, 5);  // 调用add函数，实参为3和5，返回值赋给sum
    cout << "和为：" << sum << endl;  // 输出8
    
    printInfo("张三", 20);  // 调用printInfo函数，实参为"张三"和20
    
    return 0;
}

1.1.6 函数的嵌套调用与递归调用

1.1.6.1. 嵌套调用

在一个函数的函数体中调用另一个函数，称为函数的嵌套调用。

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

int multiply(int a, int b) {
    return a * b;
}

int calculate(int x, int y) {
    int sum = add(x, y);        // 嵌套调用add函数
    int product = multiply(x, y);  // 嵌套调用multiply函数
    return sum + product;
}

int main() {
    cout << calculate(2, 3) << endl;  // 输出 2+3 + 2*3 = 5 + 6 = 11
    return 0;
}

1.1.6.2. 递归调用

函数直接或间接调用自身，称为递归调用。递归调用需满足两个条件：

1. 存在递归终止条件（避免无限递归）
2. 每次递归调用时，问题规模应逐渐缩小

// 计算n的阶乘
int factorial(int n) {
    if (n == 0 || n == 1) {  // 递归终止条件
        return 1;
    } else {
        return n * factorial(n - 1);  // 递归调用自身，问题规模缩小
    }
}

int main() {
    cout << factorial(5) << endl;  // 输出 5! = 5*4*3*2*1 = 120
    return 0;
}

1.1.7 引用作为函数参数

引用是变量的别名，通过引用传递参数可以避免拷贝大型对象，提高效率，并且可以直接修改实参。

// 通过引用交换两个变量的值
void swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

int main() {
    int a = 10, b = 20;
    swap(a, b);  // 实参a和b被引用传递
    cout << a << " " << b;  // 输出20 10
    return 0;
}

// 传递大型对象（避免拷贝）
struct LargeObject {
    int data[1000];  // 大型数据
};

// 引用传递，避免对象拷贝
void process(const LargeObject &obj) {
    // 处理obj, const确保不修改原对象
}

int main() {
    LargeObject obj;
    process(obj);  // 无需拷贝整个对象，效率高
    return 0;
}

注意：使用const修饰引用参数，可以防止函数内部意外修改实参，同时允许传递常量或临时对象。

1.1.8 函数返回引用

函数可以返回引用，此时返回的是对某个变量的引用（而非值拷贝），通过返回值可以直接修改被引用的变量。

// 返回全局变量的引用
int global = 100;

int &getGlobal() {
    return global;
}

int main() {
    getGlobal() = 200;  // 通过返回的引用修改全局变量
    cout << global;  // 输出200
    return 0;
}

注意：不要返回局部变量的引用，因为局部变量在函数调用结束后会被释放，其引用将变为无效。

---

第2章 指针详解

2.1 指针的基本概念

指针是C++中一种重要的数据类型，它存储了另一个变量的内存地址。通过指针可以直接访问和修改内存中的数据，这使得指针在内存管理、函数参数传递、数组操作等方面有着广泛的应用。

2.1.1. 内存地址

计算机的内存被划分为一个个连续的存储单元，每个存储单元都有一个唯一的编号，这个编号就是内存地址。内存地址通常用十六进制数表示，例如0x7ffd9a3b45c0。

2.1.2. 指针的定义

指针是一个变量，它的值是另一个变量的内存地址。通过指针，我们可以间接访问它所指向的变量。

例如，若变量a的内存地址是0x7ffd9a3b45c0，那么指向a的指针p的值就是0x7ffd9a3b45c0。

2.2 指针的定义与初始化

指针的定义语法

数据类型 *指针变量名;

• 数据类型：指针所指向变量的数据类型，决定了通过指针访问内存时的字节数和解析方式
• \*：表示该变量是一个指针
• 指针变量名：遵循标识符命名规则

示例

int *p;        // 定义一个指向int类型变量的指针p
double *dp;    // 定义一个指向double类型变量的指针dp
char *cp;      // 定义一个指向char类型变量的指针cp

指针的初始化

指针在使用前必须初始化，否则它的值是不确定的（野指针），访问野指针可能导致程序崩溃。指针的初始化方式有以下几种：

1. 指向已定义的变量：通过取地址符&获取变量的地址，赋值给指针

   int a = 10;
   int *p = &a;  // p指向变量a，p的值是a的内存地址
   

2. 初始化为空指针：使用nullptr（C++11引入）或0、NULL将指针初始化为空指针，空指针不指向任何有效内存

   int *p1 = nullptr;  // 空指针
   int *p2 = 0;        // 等价于空指针
   int *p3 = NULL;     // 等价于空指针
   

3. 指向动态分配的内存：通过new运算符动态分配内存，并将地址赋值给指针

   int *p = new int;  // p指向动态分配的int类型内存
   

2.3 指针的解引用

解引用是指通过指针访问它所指向的变量的值，使用解引用运算符*。

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

cout << *p << endl;  // 解引用p，输出a的值10
*p = 20;              // 通过指针修改a的值
cout << a << endl;    // 输出修改后的值20

2.4 指针的运算

指针可以进行一些特殊的运算，包括指针加减整数、指针减指针等，这些运算的结果与指针所指向的数据类型的大小有关。

####2.4.1. 指针加减整数

指针加上或减去一个整数n，表示指针指向当前位置向前或向后移动n个数据类型的长度（单位：字节）。

int arr[] = {10, 20, 30, 40, 50};
int *p = arr;  // 指针p指向数组的第一个元素（arr[0]）

cout << *p << endl;  // 输出10（arr[0]）
p++;                 // 指针向后移动一个int类型的长度，指向arr[1]
cout << *p << endl;  // 输出20（arr[1]）
p += 2;              // 指针向后移动两个int类型的长度，指向arr[3]
cout << *p << endl;  // 输出40（arr[3]）
p--;                 // 指针向前移动一个int类型的长度，指向arr[2]
cout << *p << endl;  // 输出30（arr[2]）

2.4.2. 指针减指针

两个同类型的指针相减，结果是它们之间相差的数据元素个数（而非字节数）。

int arr[] = {10, 20, 30, 40, 50};
int *p1 = &arr[0];
int *p2 = &arr[3];

cout << p2 - p1 << endl;  // 输出3，表示两个指针之间相差3个int元素

2.4.3. 指针的比较运算

同类型的指针可以进行比较运算（==、!=、<、>、<=、>=），比较的是它们所指向的内存地址。

int arr[] = {10, 20, 30};
int *p1 = &arr[0];
int *p2 = &arr[1];

if (p1 < p2) {
    cout << "p1指向的地址在p2之前" << endl;  // 输出此句
}

2.5 指针与数组

数组名本质上是一个指向数组第一个元素的常量指针（不能被修改），因此指针与数组的关系十分密切，可以通过指针来访问和操作数组元素。

2.5.1. 通过指针访问数组元素

int arr[] = {10, 20, 30, 40, 50};
int *p = arr;  // 等价于 int *p = &arr[0]

// 通过指针访问数组元素
for (int i = 0; i < 5; i++) {
    cout << *(p + i) << " ";  // 等价于 arr[i] 或 *(arr + i)
}
// 输出：10 20 30 40 50

2.5.2. 指针数组

指针数组是一个数组，其每个元素都是一个指针。

int a = 10, b = 20, c = 30;
int *arr[] = {&a, &b, &c};  // 指针数组，每个元素都是int*类型

for (int i = 0; i < 3; i++) {
    cout << *arr[i] << " ";  // 访问每个指针所指向的变量的值
}
// 输出：10 20 30

2.6 指针与函数

指针可以作为函数的参数、返回值，实现通过函数修改外部变量、传递数组等功能。

2.6.1. 指针作为函数参数

指针作为函数参数时，函数内部可以通过指针修改参数变量的值（类似引用传递的效果）。

// 通过指针交换两个变量的值
void swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int main() {
    int a = 10, b = 20;
    swap(&a, &b);  // 传递变量的地址
    cout << "a = " << a << ", b = " << b << endl;  // 输出 a = 20, b = 10
    return 0;
}

2.6.2. 指针作为函数返回值

函数可以返回一个指针，通常用于返回动态分配的内存或静态变量的地址。

注意：不要返回局部变量的地址，因为局部变量在函数调用结束后会被释放，其地址变为无效地址。

// 返回动态分配的int类型内存的指针
int* createInt(int value) {
    int* p = new int;
    *p = value;
    return p;
}

int main() {
    int* p = createInt(100);
    cout << *p << endl;  // 输出100
    
    delete p;  // 释放动态分配的内存
    return 0;
}

2.6.3. 指向函数的指针（函数指针）

指向函数的指针（函数指针）可以存储函数的地址，通过函数指针可以调用它所指向的函数。

语法：

返回值类型 (*指针变量名)(参数列表);

示例：

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

int subtract(int a, int b) {
    return a - b;
}

int main() {
    int (*funcPtr)(int, int);  // 定义一个函数指针
    
    funcPtr = add;  // 函数指针指向add函数
    cout << funcPtr(3, 5) << endl;  // 通过函数指针调用add，输出8
    
    funcPtr = subtract;  // 函数指针指向subtract函数
    cout << funcPtr(3, 5) << endl;  // 通过函数指针调用subtract，输出-2
    
    return 0;
}

2.7 const与指针

const与指针结合使用时，可以限制指针的操作，常见的有三种形式：指向常量的指针、常量指针、指向常量的常量指针。

2.7.1. 指向常量的指针

指针可以被修改（指向其他地址），但不能通过指针修改所指向的变量的值。

语法：

const 数据类型 *指针变量名;
// 或
数据类型 const *指针变量名;

示例：

int a = 10, b = 20;
const int *p = &a;  // p是指向常量的指针

// *p = 30;  // 错误！不能通过p修改a的值
p = &b;      // 正确，可以修改指针本身，让它指向另一个变量

2.7.2. 常量指针

指针本身是常量，不能被修改（不能指向其他地址），但可以通过指针修改所指向的变量的值。

语法：

数据类型 *const 指针变量名;

示例：

int a = 10, b = 20;
int *const p = &a;  // p是常量指针

*p = 30;  // 正确，可以通过p修改a的值
// p = &b;  // 错误！不能修改指针本身

2.7.3. 指向常量的常量指针

指针本身不能被修改，也不能通过指针修改所指向的变量的值。

语法：

const 数据类型 *const 指针变量名;

示例：

int a = 10, b = 20;
const int *const p = &a;  // p是指向常量的常量指针

// *p = 30;  // 错误！不能通过p修改a的值
// p = &b;   // 错误！不能修改指针本身

---

第3章. 引用

3.1 基本概念

引用（Reference） 是 C++ 语言特有的语法特性，它为已存在的变量提供一个别名，通过引用可以直接操作原变量。

3.1.1 定义方式

类型 &引用名 = 变量名；

示例：

int a = 10;
int &b = a;  // 声明 b 是 a 的引用（别名）
b = 20;     // 等价于 a = 20
cout << a;  // 输出 20

3.1.2 主要特性

• 必须初始化：引用在定义时必须绑定到一个已存在的变量

  int &r;      // 错误：引用未初始化
  int x = 5;
  int &r = x;  // 正确：r 绑定到 x
  

• 绑定不可更改：引用一旦与某个变量绑定，就不能再改为引用其他变量

  int a = 10, b = 20;
  int &r = a;
  r = b;  // 不是更改引用的绑定，而是将 b 的值赋给 a
  

• 不分配独立内存：引用本身不占用额外的内存空间

• 类型严格匹配：引用的类型必须与被引用变量的类型完全一致（常量引用除外）

3.2 引用与指针的区别

特性	引用	指针
定义与初始化	必须初始化，绑定到一个变量	可先声明后初始化，可指向 NULL
重新绑定	一旦绑定，不可更改引用的变量	可随时指向其他变量
内存占用	不占用额外内存（编译器层面）	占用内存（存储变量地址）
操作方式	直接使用，无需解引用	需通过 * 解引用访问变量
空值	无空引用（必须绑定有效变量）	有空指针（NULL 或 nullptr）
安全性	较高（避免野指针风险）	较低（可能出现野指针、空指针）
语法复杂度	简单（隐藏指针细节）	较复杂（需手动管理地址）

示例对比：

// 指针实现
int a = 10;
int *p = &a;  // 指针指向 a 的地址
*p = 20;      // 解引用并修改 a 的值

// 引用实现
int a = 10;
int &r = a;   // 引用绑定到 a
r = 20;       // 直接修改 a 的值

3.3 引用的应用场景

3.3.1 函数参数传递

引用作为函数参数时，实参将直接传递给形参（而非值拷贝），函数内部对引用的修改会影响外部实参。

应用场景 1：修改实参的值

// 交换两个整数的值
void swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

int main() {
    int a = 10, b = 20;
    swap(a, b);  // 实参 a 和 b 被引用传递
    cout << a << " " << b;  // 输出 20 10
    return 0;
}

应用场景 2：传递大型对象（避免拷贝）

struct LargeObject {
    int data[1000];  // 大型数据
};

// 引用传递，避免对象拷贝
void process(const LargeObject &obj) {
    // 处理 obj, const 确保不修改原对象
}

int main() {
    LargeObject obj;
    process(obj);  // 无需拷贝整个对象，效率高
    return 0;
}

注意：使用 const 修饰引用参数，可以防止函数内部意外修改实参，同时允许传递常量或临时对象。

3.3.2 函数返回值

函数可以返回引用，此时返回的是对某个变量的引用（而非值拷贝），通过返回值可以直接修改被引用的变量。

正确示例 1：返回全局变量或静态变量的引用

int global = 100;
// 返回全局变量的引用
int &getGlobal() {
    return global;
}

int main() {
    getGlobal() = 200;  // 通过返回的引用修改全局变量
    cout << global;     // 输出 200
    return 0;
}

正确示例 2：返回类的成员变量引用

class MyClass {
private:
    int value;
public:
    MyClass(int v) : value(v) {}
    // 返回成员变量的引用
    int &getValue() {
        return value;
    }
};

int main() {
    MyClass obj(5);
    obj.getValue() = 10;  // 通过引用修改成员变量
    cout << obj.getValue();  // 输出 10
    return 0;
}

错误示例：禁止返回局部变量的引用

// 错误示例：返回局部变量的引用
int &badFunc() {
    int x = 10;
    return x;  // x 在函数结束后销毁，引用无效
}

3.3.3 常量引用

常量引用（const 引用） 是指向常量的引用，语法为 const 类型 &引用名 = 变量名;

主要特性：

• 不能通过常量引用修改被引用的变量

  int a = 10;
  const int &r = a;
  r = 20;  // 错误：常量引用不能修改被引用变量
  a = 20;  // 正确：可以直接修改原变量
  

• 可以引用常量或临时对象

  const int &r1 = 100;      // 正确：常量引用可以绑定到常量
  const int &r2 = 5 + 3;    // 正确：可以绑定到临时对象（结果为 8）
  

• 允许不同类型的隐式转换（仅限常量引用）

  double d = 3.14;
  const int &r = d;  // 正确，临时 int 变量（值为 3）被创建，r 绑定到该临时变量
  // 注：d 的值修改后，r 的值不变（因为 r 绑定的是临时变量）
  d = 4.5;
  cout << r;  // 输出 3
  

常量引用常用于函数参数，既可以接收常量或临时对象，又能防止函数内部修改实参，是一种安全高效的参数传递方式。

---

第4章. 函数参数的传递

在函数调用中，参数传递方式决定了实参与形参之间的数据交互方式，C++ 中主要有以下三种传递方式：

4.1 三种传递方式

4.1.1 值传递（Pass by Value）

值传递是指函数调用时，将实参的值拷贝一份传递给形参，形参的修改不会影响实参。

特点：

• 形参是实参的副本，二者占用不同的内存空间
• 函数内部对形参的操作仅作用于副本，不影响原实参
• 传递开销与参数大小成正比（大型对象拷贝成本高）

示例：

void increment(int x) {
    x++;  // 修改形参 x（副本）
}

int main() {
    int a = 10;
    increment(a);  // 传递 a 的值（值传递）
    cout << a;     // 输出 10（实参 a 未被修改）
    return 0;
}

适用场景：

• 传递基本数据类型（如 int、char），且无需修改实参
• 传递小型结构体或对象，且不希望函数修改原对象

4.1.2 引用传递（Pass by Reference）

引用传递是指函数调用时，将实参的引用（别名）传递给形参，形参与实参共享同一块内存，形参的修改会直接影响实参。

特点：

• 形参是实参的引用，二者指向同一块内存
• 无需拷贝实参，传递效率高（尤其适合大型对象）
• 函数内部对形参的修改会同步到实参

示例：

void increment(int &x) {
    x++;  // 通过引用修改实参
}

int main() {
    int a = 10;
    increment(a);  // 传递 a 的引用（引用传递）
    cout << a;     // 输出 11（实参 a 被修改）
    return 0;
}

常量引用传递： 若需避免函数修改实参，可使用 const 修饰引用参数：

void print(const LargeObject &obj) {
    // obj.data[0] = 0;  // 错误：常量引用禁止修改实参
    cout << obj.data[0];  // 允许读取
}

常量引用传递的优势：

• 支持传递常量或临时对象
• 避免意外修改实参，同时保持高效传递（无拷贝）

适用场景：

• 需要在函数内部修改实参的值
• 传递大型对象（如结构体、类实例），避免拷贝开销
• 希望函数访问实参但不修改时，使用常量引用

4.1.3 指针传递（Pass by Pointer）

指针传递是指函数调用时，将实参的地址传递给形参（指针变量），通过指针解引用可修改实参。

特点：

• 形参是指针变量，存储实参的地址
• 通过 * 解引用指针可访问或修改实参
• 传递开销小（仅拷贝地址），但语法较复杂

示例：

void increment(int *x) {
    (*x)++;  // 解引用指针，修改实参
}

int main() {
    int a = 10;
    increment(&a);  // 传递 a 的地址（指针传递）
    cout << a;      // 输出 11（实参 a 被修改）
    return 0;
}

适用场景：

• 需要修改实参，且可能传递空值（指针可指向 NULL）
• 处理动态内存（如传递指向堆内存的指针）
• 与 C 语言兼容的场景（C 语言仅支持指针传递）

4.2 三种传递方式的对比

传递方式	核心机制	实参是否可被修改	传递开销	安全性	适用场景
值传递	拷贝实参值到形参	不可修改	与参数大小成正比	高（形参修改不影响实参）	基本类型、小型对象，无需修改实参
引用传递	传递实参的引用	可修改（非常量引用）	低（无拷贝）	较高（无空引用风险）	需修改实参、传递大型对象
指针传递	传递实参的地址	可修改（通过解引用）	低（仅拷贝地址）	较低（可能有空指针、野指针）	需传递空值、处理动态内存、兼容 C 语言

---

第5章. 结构体与联合体

在 C++ 中，结构体（Struct）和联合体（Union）是两种用户自定义的数据类型，用于将不同类型的数据组合在一起，方便数据的管理和操作。

5.1 结构体（Struct）

结构体是一种可以包含多个不同类型成员的复合数据类型，这些成员可以是基本数据类型（如 int、double），也可以是其他结构体、指针等。结构体的成员各自占用独立的内存空间，整体反映一个"事物"的多方面属性。

5.1.1 结构体的定义

语法：

struct 结构体名 {
    成员类型1 成员名1;
    成员类型2 成员名2;
    // ... 更多成员
};

示例：

// 定义一个表示学生的结构体
struct Student {
    string name;    // 姓名
    int age;        // 年龄
    float score;    // 成绩
    char gender;    // 性别 ('M' 表示男, 'F' 表示女)
};

5.1.2 结构体变量的定义与初始化

定义结构体变量的方式：

1. 定义结构体的同时定义变量

   struct Teacher {
       string name;
       int id;
   } t1, t2;  // t1, t2 是 Teacher 类型的变量
   

2. 先定义结构体，再定义变量

   struct Student {
       string name;
       int age;
   };
   Student s1, s2;  // s1, s2 是 Student 类型的变
   

初始化结构体变量：

1. 按成员顺序初始化（需与结构体成员定义顺序一致）

   Student s3 = {"张三", 18};  // name="张三", age=18
   

2. 指定成员名初始化（C++11 及以上支持，顺序可任意）

   Student s4 = {.age = 19, .name = "李四"};  // name="李四", age=19
   

5.1.3 结构体成员的访问

访问结构体变量的成员需使用成员访问运算符 .；若通过指针访问结构体成员，则使用 -> 运算符。

示例：

struct Student {
    string name;
    int age;
};

int main() {
    Student s = {"王五", 20};
    Student* p = &s;
    
    // 通过变量访问成员
    cout << "姓名：" << s.name << ", 年龄: " << s.age << endl;
    
    // 通过指针访问成员
    cout << "姓名：" << p->name << ", 年龄: " << p->age << endl;
    
    // 修改成员的值
    s.age = 21;
    p->name = "赵六";
    cout << "修改后：" << s.name << ", " << s.age << endl;
    
    return 0;
}

5.1.4 结构体数组

结构体数组是由多个相同结构体类型的变量组成的数组，每个元素都是一个结构体变量。

示例：

struct Book {
    string title;   // 书名
    string author;  // 作者
    float price;    // 价格
};

int main() {
    // 定义并初始化结构体数组
    Book books[3] = {
        {"C++ Primer", "Lippman", 89.0f},
        {"算法导论", "CLRS", 128.0f},
        {"编程珠玑", "Bentley", 59.0f}
    };

    // 遍历结构体数组
    for (int i = 0; i < 3; i++) {
        cout << "书名: " << books[i].title
             << ", 作者: " << books[i].author
             << ", 价格: " << books[i].price << endl;
    }
    return 0;
}

5.1.5 结构体作为函数参数与返回值

结构体可以作为函数的参数传递，也可以作为函数的返回值，传递方式包括值传递和地址传递（指针或引用）。

示例：

struct Point {
    int x;
    int y;
};

// 值传递：函数接收结构体的副本
void printPoint(Point p) {
    cout << "(" << p.x << ", " << p.y << ")" << endl;
}

// 引用传递：函数接收结构体的引用，可修改原变量
void movePoint(Point& p, int dx, int dy) {
    p.x += dx;
    p.y += dy;
}

// 返回结构体类型
Point createPoint(int x, int y) {
    Point p = {x, y};
    return p;
}

int main() {
    Point p = createPoint(3, 4);
    printPoint(p);           // 输出(3, 4)
    movePoint(p, 2, 5);
    printPoint(p);           // 输出(5, 9)
    return 0;
}

5.1.6 结构体的嵌套

结构体的成员可以是另一个结构体，这种情况称为结构体的嵌套，用于表示更复杂的复合数据。

示例：

// 定义日期结构体
struct Date {
    int year;
    int month;
    int day;
};

// 定义员工结构体，嵌套 Date 类型的成员
struct Employee {
    string id;
    string name;
    Date hireDate;  // 入职日期（结构体成员）
    float salary;
};

int main() {
    Employee emp = {
        "E001",
        "张三",
        {2020, 3, 15},  // 初始化嵌套的 Date 成员
        8000.0f
    };

    cout << "员工 ID: " << emp.id << endl;
    cout << "入职日期: " << emp.hireDate.year << "-"
         << emp.hireDate.month << "-" << emp.hireDate.day << endl;
    return 0;
}

5.2 联合体（Union）

联合体与结构体类似，也是一种复合数据类型，但联合体的所有成员共享同一块内存空间，同一时间只能存储其中一个成员的值。联合体的大小等于其最大成员的大小，适合在不同场景下使用不同类型的数据但不需要同时存储的情况。

5.2.1 联合体的定义

语法：

union 联合体名 {
    成员类型1 成员名1;
    成员类型2 成员名2;
    // ... 更多成员
};

示例：

// 定义一个存储不同数据类型的联合体
union Data {
    int i;     // 整数
    float f;   // 浮点数
    char c;    // 字符
};

5.2.2 联合体变量的定义与使用

联合体变量的定义和初始化方式与结构体类似，但初始化时只能为一个成员赋值。

示例：

union Data {
    int i;
    float f;
    char c;
};

int main() {
    Data d;
    d.i = 100;  // 存储整数
    cout << "d.i = " << d.i << endl;  // 输出 100
    
    d.f = 3.14f;  // 存储浮点数，覆盖之前的整数
    cout << "d.f = " << d.f << endl;  // 输出 3.14
    
    d.c = 'A';    // 存储字符，覆盖之前的浮点数
    cout << "d.c = " << d.c << endl;  // 输出 'A'
    
    return 0;
}

5.2.3 联合体的大小

联合体的大小等于其最大成员的大小，以确保能容纳最大的成员。

示例：

union SizeTest {
    char a;   // 1字节
    int b;    // 4字节
    double c; // 8字节
};

int main() {
    cout << "SizeTest的大小：" << sizeof(SizeTest) << endl;  // 输出 8（等于最大成员 double 的大小）
    return 0;
}

5.2.4 联合体的应用场景

联合体常用于需要在同一内存空间存储不同类型数据的场景，例如：

1. 节省内存：当数据在不同时刻使用不同类型，且不需要同时存在时，使用联合体可减少内存占用
2. 类型转换：通过联合体可以查看同一内存空间在不同数据类型下的表示（如将浮点数的内存视为整数）
3. 数据解析：在解析二进制数据时，可通过联合体提取不同类型的字段

类型转换示例：

union Converter {
    float f;
    int i;
};

int main() {
    Converter conv;
    conv.f = 3.14f;
    // 查看 3.14f 在内存中的整数表示（IEEE 754 标准）
    cout << "3.14f 对应的整数: " << conv.i << endl;
    return 0;
}

5.3 结构体与联合体的区别

结构体和联合体虽然语法相似，但在内存分配和使用场景上有本质区别，具体对比如下：

特性	结构体 (Struct)	联合体 (Union)
内存分配	每个成员占用独立的内存空间，总大小为所有成员大小之和（可能因内存对齐略有差异）	所有成员共享同一块内存空间，总大小等于最大成员的大小
成员访问	可以同时访问所有成员，修改一个成员不影响其他成员	同一时间只能有效访问一个成员，修改一个成员会覆盖其他成员的值
用途	存储多个相关的不同类型数据，整体描述一个事物的属性	存储不同类型数据但不同时使用，用于节省内存或类型转换
初始化	可以同时初始化多个成员（按顺序或指定成员名）	只能初始化一个成员（通常是第一个）

第6章 内存分区模型

C++程序运行时，内存会被操作系统和编译器划分为几个不同的逻辑区域，每个区域存储特定类型的数据，并具有不同的生命周期和管理方式。理解内存分区对于编写高效、稳定的程序至关重要。

---

6.1 内存分区概述

程序运行时的内存主要划分为以下几个区域：

1. 代码区 (Code Area)
2. 全局区 / 静态区 (Global/Static Area)
3. 栈区 (Stack Area)
4. 堆区 (Heap Area)

这些分区的核心区别在于：

• 存储内容：存放的数据类型不同。
• 生命周期：数据在内存中存在的时间不同。
• 管理方式：由编译器自动管理还是程序员手动管理。

6.2 代码区 (Code Area)

代码区用于存放CPU执行的机器指令（即程序代码）。

特点：

• 只读性：防止程序意外修改自身指令。
• 共享性：相同的程序可以共享一份代码，节省内存。
• 编译时确定：其内容和大小在编译后即固定。

存储内容：

• 所有函数的二进制代码（如 main, add 等函数体）。

示例：

int add(int a, int b) { // 函数 `add` 的指令存储在代码区
    return a + b;
}

6.3 全局区 / 静态区 (Global/Static Area)

此区域用于存储全局变量、静态变量和常量，在程序启动时分配，结束时释放。

特点：

• 生命周期长：伴随整个程序运行期。
• 编译时分配：程序加载时即被初始化。
• 默认初始化：未显式初始化的变量会被置零（0, nullptr等）。

存储内容：

• 全局变量：在所有函数外部定义的变量。
• 静态变量：使用 static 关键字声明的变量（包括局部静态变量）。
• 常量：字符串常量、全局 const 常量。

示例：

#include <iostream>
using namespace std;

int g_a = 10;               // 全局变量
int g_b;                    // 未初始化的全局变量，默认为0
static int s_c = 20;        // 全局静态变量
const int c_d = 30;         // 全局常量

int main() {
    static int s_e = 200;   // 局部静态变量（存储在全局区！）
    cout << "全局变量g_a地址: " << &g_a << endl;
    cout << "局部静态变量s_e地址: " << &s_e << endl;
    cout << "字符串常量地址: " << (void*)"Hello" << endl;
    return 0;
}
// 注意：全局变量、静态变量、常量的地址通常比较接近，而与局部变量地址差异较大。

重点：局部静态变量虽然作用域在函数内，但其生命周期和存储位置与全局变量相同。

6.4 栈区 (Stack Area)

栈区由编译器自动管理，用于存储函数调用相关的数据。

特点：

• 自动管理：函数调用时分配，函数结束时自动释放。
• 先进后出 (FILO)：遵循栈数据结构原则。
• 大小有限：通常为几MB，过大会导致“栈溢出”。
• 高效：分配和释放仅通过移动栈指针实现，速度快。

存储内容：

• 局部变量（非 static）
• 函数参数
• 函数返回值
• 函数调用的上下文（返回地址等）

栈溢出示例：

void riskyFunction() {
    int hugeArray[1000000]; // 在栈上分配超大数组，可能导致栈溢出
    // ... 其他操作
}
void infiniteRecursion() {
    int data[1000];
    infiniteRecursion(); // 无限递归，每次调用都会消耗栈空间，最终导致溢出
}

6.5 堆区 (Heap Area)

堆区用于程序运行时的动态内存分配，由程序员手动管理。

特点：

• 手动管理：使用 new/malloc 分配，必须用 delete/free 释放，否则内存泄漏。
• 容量大：大小受系统可用内存限制，通常远大于栈。
• 分配较慢：需要查找合适的内存块。
• 可能产生碎片：频繁不规则地分配和释放会导致内存碎片。

存储内容：

• 所有通过 new 或 malloc 动态创建的数据。

示例：

#include <iostream>
using namespace std;

int* createOnHeap(int value) {
    int* p = new int(value); // 在堆上分配一个整数
    return p; // 返回堆内存地址。栈变量p会被销毁，但堆内存数据保留
}

int main() {
    // 动态分配单个变量和数组
    int* pSingle = new int(42);
    int* pArray = new int[5]{1, 2, 3, 4, 5};

    int* pFromFunc = createOnHeap(100);
    cout << *pFromFunc << endl; // 输出: 100

    // 必须手动释放！
    delete pSingle;
    delete[] pArray; // 释放数组要用 delete[]
    delete pFromFunc;

    return 0;
}

6.6 堆与栈的对比

特性	堆区 (Heap)	栈区 (Stack)
管理方式	程序员手动 (new/delete)	编译器自动
大小	大 (GB级，受系统内存限制)	小 (通常MB级)
分配速度	较慢 (需要查找)	极快 (移动栈指针)
存储内容	动态分配的数据	局部变量、参数、返回地址等
生命周期	从 new 分配到 delete 释放 (手动控制)	所属函数执行期间 (自动控制)
碎片问题	有 (可能产生内存碎片)	无 (连续分配释放)

6.7 常见内存问题

1. 野指针 (Dangling Pointer)：指针指向已被释放或未初始化的内存。

   int* p = new int(10);
   delete p;
   // 此时 p 为野指针，对其解引用 (*p = 20) 行为未定义，非常危险。
   

2. 内存泄漏 (Memory Leak)：分配堆内存后未释放，导致可用内存不断减少。

   void leak() {
       int* p = new int(10);
       // 函数结束，指针 p 被销毁，但堆上的 int(10) 永远无法被释放。
   }
   

3. 栈溢出 (Stack Overflow)：栈空间被耗尽。

   void overflow() {
       int big[10000000]; // 可能超出栈容量
   }
   

4. 修改常量区：试图修改只读的字符串常量。

   char* str = "constant"; // “constant”存储在全局区（只读）
   // str[0] = 'C'; // 运行时错误！试图修改只读内存。
   

---

第7章 异常处理

程序运行时难免出现意外错误（如除零、文件不存在、内存不足）。C++的异常处理机制提供了一种将错误检测与错误处理分离的优雅方式，增强程序的健壮性。

---

7.1 基本概念与语法

异常处理基于三个关键字：try, catch, throw。

• try：包裹可能抛出异常的代码块。
• throw：当检测到错误时，抛出异常对象。
• catch：捕获并处理特定类型的异常。

基本语法：

try {
    // 可能出错的代码
    if (error_condition) {
        throw some_value; // 抛出异常，可以是任意类型
    }
    // 若无异常，继续执行
} catch (ExceptionType1& e) {
    // 处理 ExceptionType1 类型的异常
} catch (ExceptionType2& e) {
    // 处理 ExceptionType2 类型的异常
} catch (...) { // 捕获所有其他类型的异常
    // 处理未知异常
}

示例：除零错误

#include <iostream>
using namespace std;

double divide(double a, double b) {
    if (b == 0) {
        throw "除数不能为零！"; // 抛出 const char* 类型的异常
    }
    return a / b;
}

int main() {
    try {
        double result = divide(10, 0);
        cout << "结果是：" << result << endl;
    } catch (const char* errorMsg) { // 捕获字符串异常
        cout << "捕获到异常：" << errorMsg << endl;
    } catch (...) {
        cout << "捕获到未知异常" << endl;
    }
    return 0;
}

7.2 抛出与捕获不同类型的异常

7.2.1 基本类型异常

#include <iostream>
#include <cmath>
using namespace std;

double triangleArea(double a, double b, double c) {
    if (a <= 0 || b <= 0 || c <= 0) {
        throw -1; // 用整数错误码作为异常
    }
    if (a + b <= c || a + c <= b || b + c <= a) {
        throw -2;
    }
    double s = (a + b + c) / 2;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    try {
        double area = triangleArea(3, 4, 5);
        cout << "面积：" << area << endl;
        area = triangleArea(1, 1, 3); // 会抛出 -2
    } catch (int errCode) {
        if (errCode == -1) {
            cout << "错误：边长必须为正数" << endl;
        } else if (errCode == -2) {
            cout << "错误：无法构成三角形" << endl;
        }
    }
    return 0;
}

7.2.2 自定义类型异常 (GESP四级重点)

使用类可以携带更丰富的错误信息。

#include <iostream>
#include <string>
using namespace std;

class FileException {
private:
    int m_code;
    string m_msg;
public:
    FileException(int code, const string& msg) : m_code(code), m_msg(msg) {}
    int getCode() const { return m_code; }
    string getMsg() const { return m_msg; }
};

void openFile(const string& filename) {
    if (filename.empty()) {
        throw FileException(1001, "文件名不能为空");
    }
    if (filename.find(".txt") == string::npos) {
        throw FileException(1002, "仅支持.txt文件");
    }
    cout << "成功打开文件：" << filename << endl;
}

int main() {
    try {
        openFile("data.txt");
        openFile("report.doc"); // 会抛出 FileException(1002, ...)
    } catch (const FileException& e) { // 注意：使用 const 引用捕获，避免拷贝
        cout << "文件操作失败！" << endl;
        cout << "  错误码：" << e.getCode() << endl;
        cout << "  错误信息：" << e.getMsg() << endl;
    }
    return 0;
}

7.3 异常的传播

重要规则：如果异常在当前的 try-catch 块中没有被捕获，它会沿着函数调用链向上传播（“栈展开”），直到被某个 catch 块捕获。如果始终未被捕获，程序会调用 terminate() 终止。

示例：异常传播过程

#include <iostream>
using namespace std;

void func3() {
    cout << "进入 func3" << endl;
    throw runtime_error("来自func3的严重错误");
    cout << "离开 func3 (不会执行)" << endl;
}
void func2() {
    cout << "进入 func2" << endl;
    func3(); // func3 抛出异常，func2 没有 try-catch，异常继续上传
    cout << "离开 func2 (不会执行)" << endl;
}
void func1() {
    cout << "进入 func1" << endl;
    try {
        func2(); // 异常传播到这里
    } catch (const exception& e) { // 异常被捕获
        cout << "在 func1 中捕获异常：" << e.what() << endl;
    }
    cout << "离开 func1" << endl; // 捕获后，程序从此处继续正常执行
}

int main() {
    func1();
    return 0;
}
/*
输出：
进入 func1
进入 func2
进入 func3
在 func1 中捕获异常：来自func3的严重错误
离开 func1
*/

7.4 标准异常 (GESP四级重点)

C++标准库定义了一组派生自 std::exception 的异常类，位于 <stdexcept> 等头文件中。使用标准异常能使代码更规范、易读。

常见标准异常类：

异常类	描述	触发场景示例
std::exception	所有标准异常的基类	-
std::bad_alloc	内存分配失败	new 分配极大内存时
std::out_of_range	访问容器时索引越界	vector::at()、string::at() 越界访问时
std::invalid_argument	函数接收到无效的参数	传递不符合函数要求的参数时

示例：使用标准异常

#include <iostream>
#include <vector>
#include <stdexcept> // 包含标准异常类
using namespace std;

int main() {
    // 示例1：捕获 out_of_range 异常
    try {
        vector<int> vec = {1, 2, 3};
        cout << vec.at(10) << endl; // 越界访问，抛出 std::out_of_range
    } catch (const out_of_range& e) {
        cout << "捕获到越界异常：" << e.what() << endl;
    }

    // 示例2：捕获 bad_alloc 异常
    try {
        long long huge = 1000000000000LL;
        int* p = new int[huge]; // 尝试分配巨大内存，可能失败
        delete[] p;
    } catch (const bad_alloc& e) {
        cout << "内存分配失败：" << e.what() << endl;
    }

    // 示例3：使用基类 exception 捕获所有标准异常
    try {
        vector<int> v(5);
        v.at(10) = 1;
    } catch (const exception& e) { // 能捕获所有派生自 exception 的标准异常
        cout << "标准异常：" << e.what() << endl;
    }

    return 0;
}

7.5 异常处理 vs. 错误码

在C++中，除了异常，还可以用返回错误码（如 -1, NULL）来表示错误。两者对比如下：

特性	异常处理 (Exception)	错误码 (Error Code)
传递方式	自动向上传播，直到被捕获。	需手动检查并逐层返回。
代码结构	分离：正常逻辑 (try) 与错误处理 (catch) 清晰分离。	混合：正常逻辑中掺杂大量 if 错误判断。
适用场景	罕见、严重的错误（如内存耗尽、关键文件丢失）。	轻微、可预期的错误（如用户输入格式不对）。
信息携带	丰富，可抛出任意类型的对象，包含详细错误信息。	有限，通常只能通过整数或枚举表示错误类型。
性能	未发生异常时开销极小，接近错误码。发生时开销较大。	每次调用后都有判断开销，性能稳定。

7.6 异常处理注意事项

1. 避免过度使用：异常应用于处理“异常”情况。对于可预见的、频繁发生的错误（如用户输入验证），使用条件判断 (if-else) 更合适。
2. 明确异常类型：抛出含义清晰的异常类型（特别是使用标准异常或自定义类），避免滥用 throw 任意值。
3. 确保资源释放：在 try 块中申请的资源（如 new 的内存、打开的文件），必须在异常发生前释放。最佳实践是使用 RAII（资源获取即初始化），例如智能指针 (std::unique_ptr)、fstream 等，它们会在析构时自动释放资源。
4. 不要忽略异常：使用 catch(...) 捕获所有异常后，一定要进行处理（至少记录日志），否则程序可能在不稳定状态下继续运行，导致更严重的问题。
5. 了解标准异常：熟悉 <stdexcept> 等头文件中的标准异常类，在适当时机使用，使代码更专业。

第8章 文件操作

文件操作是程序与外部存储设备（如硬盘）交互的重要方式，它使得程序能够持久化保存数据（如用户配置、日志记录）和批量处理数据（如读取大量输入数据）。标准输入输出重定向则允许程序灵活地从文件读取输入或将输出写入文件，而无需修改代码逻辑。

---

8.1 文件处理的基本概念

8.1.1 文件类型

• 文本文件：以字符编码（如ASCII、UTF-8）存储，内容可被文本编辑器直接读取（如.txt文件）。
• 二进制文件：以字节为单位存储原始数据，内容通常是不可读的（如.exe、.png文件）。

8.1.2 文件指针与流对象

• C语言：使用 FILE* 类型的文件指针操作文件。
• C++：使用流对象（如 ifstream、ofstream、fstream）操作文件，更加面向对象和易用。

8.1.3 文件操作的基本步骤

无论是C语言还是C++，文件操作都遵循以下三个核心步骤：

1. 打开文件：建立程序与文件之间的连接。
2. 读写文件：进行数据的读取或写入。
3. 关闭文件：断开连接，确保数据写入磁盘并释放资源。

---

8.2 C语言的文件处理（简要回顾）

C语言通过 <stdio.h> 头文件提供文件操作函数。

8.2.1 文件的打开与关闭

• 打开文件：FILE* fopen(const char* filename, const char* mode);
• 关闭文件：int fclose(FILE* stream);

打开模式 (mode)：

模式	含义	适用文件类型
"r"	只读，文件必须存在。	文本/二进制
"w"	只写，文件不存在则创建，存在则清空内容。
"a"	追加写入，文件不存在则创建，写入位置在文件末尾。
"r+"	读写，文件必须存在。
"w+"	读写，文件不存在则创建，存在则清空内容。
"a+"	读写，文件不存在则创建，写入位置在文件末尾。
后加"b"	以二进制方式打开（例如"rb"、"wb"）。	二进制文件

示例：

#include <stdio.h>
int main() {
    FILE* fp = fopen("data.txt", "r"); // 以只读方式打开文本文件
    if (fp == NULL) { // 必须检查是否打开成功！
        perror("文件打开失败");
        return 1;
    }
    // ... 文件操作
    fclose(fp); // 必须关闭文件！
    return 0;
}

8.2.2 文本文件的读写

• 字符读写：fgetc, fputc
• 字符串读写：fgets, fputs
• 格式化读写：fscanf, fprintf（类似于 scanf 和 printf）

示例：

// 写入格式化数据
int num = 100;
float pi = 3.14;
fprintf(fp, "数字: %d, 圆周率: %.2f\n", num, pi);

// 读取格式化数据（需与写入格式匹配）
int x;
float y;
fscanf(fp, "数字: %d, 圆周率: %f", &x, &y);

8.2.3 二进制文件的读写

使用 fread 和 fwrite 直接读写内存中的原始数据。

#include <stdio.h>
struct Student {
    char name[20];
    int age;
    float score;
};
int main() {
    // 写入二进制文件
    FILE* fp = fopen("students.bin", "wb");
    struct Student s = {"Alice", 15, 90.5};
    fwrite(&s, sizeof(struct Student), 1, fp); // 写入1个结构体
    fclose(fp);

    // 读取二进制文件
    fp = fopen("students.bin", "rb");
    struct Student s2;
    fread(&s2, sizeof(struct Student), 1, fp); // 读取1个结构体
    printf("姓名：%s，年龄：%d，分数：%.1f\n", s2.name, s2.age, s2.score);
    fclose(fp);
    return 0;
}

---

8.3 C++中的文件处理（重点）

C++通过 <fstream> 头文件提供文件流类，使用起来更加直观和安全。

8.3.1 核心类

• ifstream：输入文件流（用于读文件）。
• ofstream：输出文件流（用于写文件）。
• fstream：输入输出文件流（用于读写文件）。

8.3.2 文件的打开与关闭

打开方式：

1. 通过构造函数在创建对象时打开文件。
2. 通过 open() 方法打开文件。

打开模式（类似于C语言，但使用常量）：

模式	含义
ios::in	只读打开（ifstream 默认模式）
ios::out	只写打开（ofstream 默认模式），会清空文件
ios::app	追加写入，写入位置在文件末尾
ios::trunc	若文件存在则清空内容（ios::out 默认包含）
ios::binary	以二进制方式打开
ios::ate	打开后定位到文件末尾

示例：

#include <fstream>
#include <iostream>
using namespace std;

int main() {
    // 方法1：通过构造函数打开（读文本文件）
    ifstream inFile("data.txt"); // 等价于 inFile.open("data.txt", ios::in)
    if (!inFile.is_open()) { // 判断是否打开成功
        cerr << "文件打开失败" << endl;
        return 1;
    }

    // 方法2：通过open方法打开（写二进制文件）
    ofstream outFile;
    outFile.open("output.bin", ios::out | ios::binary);
    if (!outFile) { // 另一种判断方式：流对象可直接转换为布尔值
        cerr << "文件打开失败" << endl;
        return 1;
    }

    // ... 文件操作

    // 关闭文件
    inFile.close();
    outFile.close(); // 实际上，对象析构时会自动调用close()
    return 0;
}

重点：ios::out 默认会清空文件内容，若要追加，请使用 ios::app。

8.3.3 文本文件的读写

可以使用与 cin、cout 相似的运算符 >> 和 <<，也可以使用 getline 等成员函数。

使用 << 和 >> 读写：

// 写入数据
ofstream outFile("info.txt");
outFile << "姓名：" << "Bob" << ", 年龄: " << 16 << endl;
outFile.close();

// 读取数据（格式需匹配）
ifstream inFile("info.txt");
string name;
int age;
inFile.ignore(3); // 忽略“姓名：”三个字符
getline(inFile, name, ','); // 读取到逗号为止
inFile.ignore(3); // 忽略“, 年龄: ”
inFile >> age;
cout << "读取到：" << name << ", " << age << endl;
inFile.close();

使用 getline 逐行读取：

ifstream inFile("lines.txt");
string line;
while (getline(inFile, line)) { // 读取成功返回true
    cout << "行内容：" << line << endl;
}
inFile.close();

8.3.4 二进制文件的读写（GESP四级重点）

使用 read() 和 write() 成员函数进行二进制读写。

示例：读写结构体

#include <fstream>
#include <iostream>
using namespace std;

struct Student {
    char name[20];
    int age;
    float score;
};

int main() {
    // 写入二进制文件
    ofstream outFile("students.bin", ios::out | ios::binary);
    Student s = {"Charlie", 17, 88.5};
    outFile.write((const char*)&s, sizeof(Student)); // 强制类型转换后写入
    outFile.close();

    // 读取二进制文件
    ifstream inFile("students.bin", ios::in | ios::binary);
    Student s2;
    inFile.read((char*)&s2, sizeof(Student)); // 读取到结构体
    cout << "姓名：" << s2.name << ", 年龄: " << s2.age << ", 分数: " << s2.score << endl;
    inFile.close();

    return 0;
}

重点：二进制读写时必须使用 ios::binary 模式，并使用 read/write 方法，配合强制类型转换和 sizeof 运算符。

---

8.4 标准输入输出重定向

重定向是指将程序默认的输入源（键盘）或输出目标（屏幕）临时更改为文件或其他设备。这在批量测试、日志记录等场景中非常有用。

C++中有三个标准流：

• stdin (C) / cin (C++)：标准输入（默认来自键盘）。
• stdout (C) / cout (C++)：标准输出（默认显示到屏幕）。
• stderr (C) / cerr (C++)：标准错误输出（默认显示到屏幕，通常用于错误信息，不受重定向影响）。

8.4.1 C语言的重定向（freopen）

使用 <stdio.h> 中的 freopen 函数。

#include <stdio.h>
int main() {
    // 将标准输入重定向到 input.txt
    if (freopen("input.txt", "r", stdin) == NULL) {
        perror("重定向输入失败");
        return 1;
    }
    int x;
    scanf("%d", &x); // 现在是从 input.txt 中读取整数
    printf("读取到的数是：%d\n", x); // 输出仍在屏幕

    // 将标准输出重定向到 output.txt
    if (freopen("output.txt", "w", stdout) == NULL) {
        perror("重定向输出失败");
        return 1;
    }
    printf("这行文字将写入output.txt\n"); // 输出到文件

    // 恢复标准输出到屏幕（Windows系统）
    freopen("CON", "w", stdout);
    printf("现在又输出到屏幕了\n");
    return 0;
}

8.4.2 C++的重定向（缓冲区替换，GESP四级重点）

C++通过替换标准流的内部缓冲区（streambuf）来实现重定向。

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    // 1. 保存原始缓冲区指针
    streambuf* orig_cin = cin.rdbuf();
    streambuf* orig_cout = cout.rdbuf();

    // 2. 创建文件流并打开文件
    ifstream inFile("input.txt");
    ofstream outFile("output.txt");

    // 3. 重定向：将标准流的缓冲区替换为文件流的缓冲区
    cin.rdbuf(inFile.rdbuf());  // cin 现在从 input.txt 读取
    cout.rdbuf(outFile.rdbuf()); // cout 现在输出到 output.txt

    // 4. 此时的所有标准输入输出操作都已被重定向
    int x;
    cin >> x; // 从 input.txt 读取
    cout << "读取到的数的两倍是：" << x * 2 << endl; // 写入 output.txt

    // 5. 恢复原始缓冲区（非常重要！）
    cin.rdbuf(orig_cin);
    cout.rdbuf(orig_cout);

    // 6. 关闭文件（对象析构时会自动调用，也可手动关闭）
    inFile.close();
    outFile.close();

    // 现在 cin 和 cout 已恢复正常
    cout << "程序结束，请查看 output.txt 文件。" << endl;
    return 0;
}

核心步骤记忆：保存 -> 替换 -> 操作 -> 恢复。

注意事项：

1. 重定向后，对 cin/cout 的操作就是操作文件。
2. 一定要恢复原始缓冲区，否则后续的 cin/cout 可能无法正常工作。
3. 错误信息输出 cerr 通常不重定向，以确保错误信息能立刻显示给用户。

第9章 二维和多维数组

数组是存储相同类型数据的集合。一维数组是线性排列的数据集合，而二维和多维数组则是在一维数组的基础上扩展而来，用于表示更复杂的数据结构（如矩阵、表格等）。

9.1 二维数组

二维数组可以理解为“数组的数组”，它由若干个一维数组组成，每个一维数组称为二维数组的“行”，行中的元素称为“列”。二维数组常用于表示表格、矩阵等具有行和列结构的数据。

9.1.1 二维数组的定义

二维数组的定义语法如下：

数据类型 数组名[行数][列数];

• 数据类型：数组中所有元素的数据类型（如 int、double 等）。
• 数组名：遵循标识符命名规则。
• 行数：表示二维数组包含的一维数组（行）的数量。
• 列数：表示每个一维数组（行）中包含的元素（列）的数量。

示例：

int matrix[3][4];        // 定义一个 3 行 4 列的 int 类型二维数组，共 3×4=12 个元素
double table[2][3];      // 定义一个 2 行 3 列的 double 类型二维数组，共 6 个元素

9.1.2 二维数组的初始化

二维数组的初始化是指在定义时为其元素赋初值，常见的初始化方式有以下几种：

• 按行初始化：将每行的元素用花括号 {} 包裹，整体再用花括号包裹，行与行之间用逗号分隔。

  int arr1[2][3] = {
      {1, 2, 3}, // 第 0 行元素
      {4, 5, 6}  // 第 1 行元素
  };
  

• 顺序初始化：不区分行，将所有元素按顺序写在一个花括号内，编译器会自动按行填充。

  int arr2[2][3] = {1, 2, 3, 4, 5, 6}; // 效果与 arr1 相同
  

• 部分初始化：只初始化部分元素，未初始化的元素会被自动赋默认值（数值类型为 0）。

  int arr3[3][3] = {
      {1},        // 第 0 行: [1, 0, 0]
      {2, 3},     // 第 1 行: [2, 3, 0]
      {4, 5, 6}   // 第 2 行: [4, 5, 6]
  };
  

• 省略行数：初始化时可以省略行数，编译器会根据初始化元素的数量和列数自动计算行数。

  int arr[][3] = {1, 2, 3, 4, 5, 6}; // 编译器自动计算行数为 2（6 个元素 ÷ 3 列 = 2 行）
  

  注意：列数不能省略，否则编译器无法确定数组的布局。

9.1.3 二维数组元素的访问

二维数组的元素通过“行下标”和“列下标”访问，下标从 0 开始计数，语法如下：

数组名[行下标][列下标]

示例：

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
cout << arr[0][0] << endl; // 访问第 0 行第 0 列元素，输出 1
cout << arr[1][2] << endl; // 访问第 1 行第 2 列元素，输出 6
arr[0][1] = 10;            // 修改第 0 行第 1 列元素的值为 10
cout << arr[0][1] << endl; // 输出 10

9.1.4 二维数组的遍历

遍历二维数组需要使用嵌套循环，外层循环控制行，内层循环控制列。

示例：

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 遍历二维数组并输出所有元素
for (int i = 0; i < 3; i++) {       // 外层循环，行
    for (int j = 0; j < 4; j++) {   // 内层循环，列
        cout << matrix[i][j] << " ";
    }
    cout << endl; // 每行输出完毕后换行
}

输出结果：

1 2 3 4
5 6 7 8
9 10 11 12

9.1.5 二维数组的存储方式

在 C++ 中，二维数组在内存中是按 “行优先” 的方式连续存储的，即先存储第 0 行的所有元素，再存储第 1 行的所有元素，以此类推。

例如，int arr[2][3] = {{1, 2, 3}, {4, 5, 6}} 在内存中的存储顺序为：

1, 2, 3, 4, 5, 6

可以通过指针验证这一特性：

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
int* p = &arr[0][0]; // 指向二维数组的第一个元素
for (int i = 0; i < 6; i++) {
    cout << *(p + i) << " "; // 按内存顺序访问所有元素
}
// 输出：1 2 3 4 5 6

9.2 多维数组

多维数组是二维数组的扩展，包含三维、四维等数组，其定义和使用方式与二维数组类似，只是维度更多。实际开发中，三维数组较为常用，更高维度的数组较少见。

9.2.1 三维数组的定义

三维数组可以理解为“二维数组的数组”，定义语法如下：

数据类型 数组名[第一维大小][第二维大小][第三维大小];

第一维、第二维、第三维分别表示不同层次的维度，例如可以表示“页、行、列”。

示例：

int cube[2][3][4]; // 定义一个 2×3×4 的三维 int 数组，共 2×3×4 = 24 个元素

9.2.2 三维数组的初始化

三维数组的初始化与二维数组类似，需要使用多层花括号按维度依次包裹元素。

示例：

// 初始化一个 2×2×2 的三维数组
int cube[2][2][2] = {
    {   // 第 0 页
        {1, 2},
        {3, 4}
    },
    {   // 第 1 页
        {5, 6},
        {7, 8}
    }
};

也可以省略第一维的大小，由编译器自动计算：

int cube[][2][2] = {
    {{1, 2}, {3, 4}},
    {{5, 6}, {7, 8}}
}; // 编译器自动计算第一维大小为 2

9.2.3 三维数组元素的访问与遍历

三维数组的元素通过三个下标访问，遍历需要使用三层嵌套循环。

示例：

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

// 访问元素
cout << cube[0][1][0] << endl; // 访问第 0 页第 1 行第 0 列元素，输出 3

// 遍历三维数组
for (int i = 0; i < 2; i++) {       // 第一维（页）
    cout << "第" << i << "页：" << endl;
    for (int j = 0; j < 2; j++) {   // 第二维（行）
        for (int k = 0; k < 2; k++) { // 第三维（列）
            cout << cube[i][j][k] << " ";
        }
        cout << endl;
    }
}

输出结果：

第 0 页：
1 2
3 4
第 1 页：
5 6
7 8

9.2.4 多维数组的存储方式

与二维数组类似，多维数组在内存中也是按 “行优先” 的方式连续存储的，即先存储第一维第 0 个元素包含的所有低维元素，再存储第一维第 1 个元素包含的所有低维元素，以此类推。

例如，三维数组 int cube[2][2][2] = {{{1, 2}, {3, 4}}, {{5, 6}, {7, 8}}} 的内存存储顺序为：

1, 2, 3, 4, 5, 6, 7, 8

9.3 数组作为函数参数

二维和多维数组可以作为函数的参数传递，传递时需要指定除第一维以外的其他维度的大小（因为编译器需要知道如何计算元素的内存地址）。

9.3.1 二维数组作为函数参数

传递二维数组的常见语法：

// 形式 1：明确指定列数
void printMatrix(int matrix[][4], int rows) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < 4; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

// 形式 2：使用指针形式（等价于形式 1）
void printMatrix2(int (*matrix)[4], int rows) {
    // 函数体与 printMatrix 相同
}

调用示例：

int main() {
    int matrix[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    printMatrix(matrix, 3); // 传递数组名和行数
    return 0;
}

9.3.2 三维数组作为函数参数

传递三维数组时，需要指定第二维和第三维的大小：

void printCube(int cube[][2][2], int pages) {
    for (int i = 0; i < pages; i++) {
        cout << "第" << i << "页：" << endl;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                cout << cube[i][j][k] << " ";
            }
            cout << endl;
        }
    }
}

调用示例：

int main() {
    int cube[2][2][2] = {{{1, 2}, {3, 4}}, {{5, 6}, {7, 8}}};
    printCube(cube, 2);
    return 0;
}

9.4 动态分配二维数组

在实际应用中，二维数组的行数和列数可能需要在运行时确定，此时可以通过动态内存分配创建二维数组（使用指针和 new 运算符）。

9.4.1 动态分配与释放

int main() {
    int rows = 3, cols = 4;
    
    // 动态分配二维数组：先分配行指针
    int** dynamicMatrix = new int*[rows];
    
    // 再为每行分配列元素
    for (int i = 0; i < rows; i++) {
        dynamicMatrix[i] = new int[cols];
    }
    
    // 为动态数组赋值
    int count = 1;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dynamicMatrix[i][j] = count++;
        }
    }
    
    // 访问动态数组元素
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cout << dynamicMatrix[i][j] << " ";
        }
        cout << endl;
    }
    
    // 释放动态数组：先释放每行的列元素
    for (int i = 0; i < rows; i++) {
        delete[] dynamicMatrix[i];
    }
    // 再释放行指针
    delete[] dynamicMatrix;
    dynamicMatrix = nullptr;
    
    return 0;
}

9.4.2 动态二维数组的特点

• 内存不连续：动态二维数组的行在内存中不一定连续（与静态二维数组的连续存储不同）。
• 需手动释放：必须手动释放内存（先释放每行，再释放行指针），否则会导致内存泄漏。

9.4.3 创建 n×n 的二维数组

// 创建 n×n 的二维数组
int** createMatrix(int n) {
    int** matrix = new int*[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new int[n]; // 每行 n 个元素
    }
    return matrix;
}
// 总空间为 n×n，空间复杂度为 O(n²)

9.5 二维数组与指针的关系

二维数组的数组名是一个指向其第一行的指针（行指针），其类型为 “指向包含 n 个元素的一维数组的指针”。

示例：

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
// arr 是指向第一行（int[3] 类型）的指针
int (*p)[3] = arr;      // p 指向 arr 的第 0 行
cout << *(*p) << endl;  // 访问第 0 行第 0 列元素，输出 1
p++;                    // p 指向第 1 行
cout << *(*p) << endl;  // 访问第 1 行第 0 列元素，输出 4

9.6 注意事项

• 下标越界：访问二维或多维数组时，必须确保行下标和列下标在有效范围内（0 ≤ 下标 < 维度大小），否则会导致未定义行为（如程序崩溃、数据错误）。
• 初始化时的维度匹配：初始化二维数组时，每行的元素数量不能超过定义的列数。例如，int arr[2][3] = {{1, 2, 3, 4}, {5, 6}} 是错误的（第一行元素数量为 4，超过列数 3）。
• 函数参数中的维度指定：将多维数组作为函数参数时，除第一维外，其他维度必须明确指定，否则编译器无法正确计算元素地址。
• 内存管理：动态分配的多维数组必须按正确顺序释放（从低维到高维），避免内存泄漏。
• 性能考虑：静态多维数组在编译时分配内存，访问速度快；动态多维数组通过指针间接访问，性能略低，但灵活性更高（维度可动态确定）。

---

第10章 算法的复杂度评估

算法的复杂度是衡量算法效率的重要指标，主要包括 时间复杂度 和 空间复杂度。时间复杂度用于描述算法执行所需的时间与输入规模之间的关系，空间复杂度则用于描述算法执行过程中所需的存储空间与输入规模之间的关系。评估算法的复杂度是选择和优化算法的基础。

10.1 算法复杂度的基本概念

算法是解决特定问题的步骤和方法，同一问题可能有多种不同的算法。评估算法的优劣主要从效率和资源消耗两个角度出发，对应的就是时间复杂度和空间复杂度。

• 输入规模：通常用字母 n 表示，指算法处理的数据量（如数组的长度、图的顶点数等）。
• 复杂度函数：描述算法的时间或空间消耗与输入规模之间的函数关系（如 T(n) 表示时间消耗函数，S(n) 表示空间消耗函数）。
• 渐近复杂度：当输入规模 n 趋近于无穷大时，复杂度函数的变化趋势，是评估算法长期性能的关键。

10.2 时间复杂度

时间复杂度（Time Complexity） 用于衡量算法执行时间随输入规模增长的变化趋势。它不计算具体的执行时间（受硬件、编程语言等因素影响），而是关注 执行次数 与输入规模的关系。

10.2.1 定义与表示方法

时间复杂度通过 大 O 符号（O-notation） 表示，记为 O(f(n))，其中 f(n) 是输入规模 n 的函数，表示算法执行时间的增长量级。

大 O 符号的含义：存在正常数 c 和 n0，使得当 n ≥ n0 时，T(n) ≤ c·f(n)，即 f(n) 是 T(n) 的上界。

10.2.2 时间复杂度的分析规则

分析算法的时间复杂度时，需统计关键操作（如比较、赋值、循环迭代等）的执行次数，并忽略次要因素，遵循以下规则：

1. 忽略常数项：常数项对增长趋势无影响，例如 O(2n + 3) 简化为 O(n)。
2. 忽略低次项：高次项主导增长趋势，例如 O(n² + 5n + 10) 简化为 O(n²)。
3. 关注循环迭代：循环是影响时间复杂度的主要因素，尤其是嵌套循环（时间复杂度为各层循环次数的乘积）。
4. 取最坏情况：若算法的执行时间因输入数据不同而变化，时间复杂度通常取 最坏情况 下的结果。

10.2.3 常见的时间复杂度类型

按增长速度从慢到快，常见的时间复杂度如下：

时间复杂度	名称	示例	特点
O(1)	常数阶	访问数组元素、基本运算（+、-、*、/）	执行时间与 n 无关，效率最高
O(log n)	对数阶	二分查找	增长速度极慢，接近常数阶
O(n)	线性阶	线性查找、单层循环遍历数组	执行时间随 n 线性增长
O(n log n)	线性对数阶	快速排序、归并排序、堆排序	增长速度适中，常用于高效排序算法
O(n²)	平方阶	冒泡排序、插入排序、双层嵌套循环	增长速度较快，适用于小规模数据
O(n³)	立方阶	三层嵌套循环（如矩阵乘法）	增长速度快，仅适用于极小规模数据
O(2ⁿ)	指数阶	递归求解斐波那契数列（未优化）	增长速度极快，实际应用中很少使用
O(n!)	阶乘阶	全排列生成算法	增长速度最快，仅理论研究中出现

10.2.4 时间复杂度分析示例

• 常数阶 O(1)：

  int getFirstElement(int arr[], int n) {
      return arr[0]; // 仅执行 1 次操作，与 n 无关
  }
  

• 线性阶 O(n)：

  int sumArray(int arr[], int n) {
      int sum = 0;
      for (int i = 0; i < n; i++) { // 循环执行 n 次
          sum += arr[i];
      }
      return sum;
  }
  

• 平方阶 O(n²)：

  void bubbleSort(int arr[], int n) {
      for (int i = 0; i < n; i++) {             // 外层循环 n 次
          for (int j = 0; j < n - i - 1; j++) { // 内层循环最多 n 次
              if (arr[j] > arr[j + 1]) {        // 比较操作
                  int temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;            // 交换操作
              }
          }
      }
  }
  // 最坏情况下，比较和交换操作共执行 n + (n-1) + ... + 1 = n(n+1)/2 次，简化为 O(n²)
  

• 对数阶 O(log n)：

  // 二分查找（数组已排序）
  int binarySearch(int arr[], int n, int target) {
      int left = 0, right = n - 1;
      while (left <= right) {
          int mid = (left + right) / 2;
          if (arr[mid] == target) return mid;
          else if (arr[mid] < target) left = mid + 1;
          else right = mid - 1;
      }
      return -1;
  }
  // 每次循环将查找范围缩小一半，循环次数为 log₂n，时间复杂度为 O(log n)
  

10.3 空间复杂度

空间复杂度（Space Complexity） 用于衡量算法执行过程中所需存储空间随输入规模增长的变化趋势，包括算法本身的指令、输入数据、临时变量等所占用的空间。

10.3.1 定义与表示方法

空间复杂度同样使用大 O 符号表示，记为 S(n) = O(g(n))，其中 g(n) 是输入规模 n 的函数，表示存储空间的增长量级。

注意：输入数据本身的存储空间通常不计入空间复杂度（视为问题固有需求），主要关注算法 额外使用 的临时空间。

10.3.2 空间复杂度的分析规则

1. 忽略常数项和低次项：与时间复杂度类似，例如 O(3n + 5) 简化为 O(n)。
2. 关注临时变量和数据结构：算法中创建的数组、链表、栈、队列等数据结构的大小是分析的重点。
3. 递归算法需考虑栈空间：递归调用会在栈上存储函数参数、返回地址等信息，递归深度直接影响空间复杂度。

10.3.3 常见的空间复杂度类型

空间复杂度	名称	示例	特点
O(1)	常数阶	仅使用固定数量的临时变量（如交换两个变量）	空间消耗与 n 无关
O(log n)	对数阶	递归深度为 log n 的算法（如二分查找的递归实现）	空间消耗增长缓慢
O(n)	线性阶	创建与输入规模相同的数组、链表等	空间消耗随 n 线性增长
O(n²)	平方阶	创建二维数组存储中间结果（如动态规划的二维 DP 表）	空间消耗增长较快

10.3.4 空间复杂度分析示例

• 常数阶 O(1)：

  void swap(int& a, int& b) {
      int temp = a; // 仅使用 1 个临时变量
      a = b;
      b = temp;
  }
  // 空间消耗与 n 无关，空间复杂度为 O(1)
  

• 线性阶 O(n)：

  int* copyArray(int arr[], int n) {
      int* newArr = new int[n]; // 创建大小为 n 的新数组
      for (int i = 0; i < n; i++) {
          newArr[i] = arr[i];
      }
      return newArr;
  }
  // 额外空间为 n，空间复杂度为 O(n)
  

• 递归算法的空间复杂度：

  // 递归计算 n 的阶乘
  int factorial(int n) {
      if (n == 0) return 1;
      return n * factorial(n - 1);
  }
  // 递归深度为 n，栈空间消耗为 O(n)，空间复杂度为 O(n)
  

• 二维数组的空间复杂度：

  int** createMatrix(int n) {
      int** matrix = new int*[n];
      for (int i = 0; i < n; i++) {
          matrix[i] = new int[n]; // 每行 n 个元素
      }
      return matrix;
  }
  // 总空间为 n×n，空间复杂度为 O(n²)
  

10.4 时间复杂度与空间复杂度的权衡

在很多情况下，算法的时间复杂度和空间复杂度可以相互转换，即通过增加空间消耗来降低时间消耗，或通过增加时间消耗来减少空间消耗。这种现象称为 “时空权衡”。

• 以空间换时间：哈希表（Hash Table）通过额外存储键值对，将查找时间从 O(n) 降至 O(1)（平均情况）。
• 以时间换空间：某些动态规划算法可以通过优化空间，将二维 DP 表压缩为一维数组，以增加少量时间消耗为代价，将空间复杂度从 O(n²) 降至 O(n)。

在实际应用中，需根据问题需求选择合适的权衡策略：

• 实时性要求高的场景（如高频交易、游戏引擎），通常优先优化时间复杂度。
• 内存资源有限的场景（如嵌入式设备、移动端应用），通常优先优化空间复杂度。

10.5 复杂度分析的注意事项

1. 区分最好、最坏和平均情况：
   • 最好情况：算法在最理想输入下的复杂度（如线性查找恰好第一个元素匹配，时间复杂度 O(1)）。
   • 最坏情况：算法在最不利输入下的复杂度（如线性查找最后一个元素匹配，时间复杂度 O(n)）。
   • 平均情况：考虑所有可能输入的概率分布，计算期望复杂度（如线性查找的平均时间复杂度为 O(n)）。
   • 通常以最坏情况复杂度作为算法的评估标准，确保算法在任何情况下都能满足需求。
2. 循环与递归的复杂度差异：
   • 相同逻辑的算法，递归实现可能比循环实现具有更高的空间复杂度（因递归栈消耗）。
   • 例如，递归实现的斐波那契数列时间复杂度为 O(2ⁿ)，而循环实现为 O(n)，空间复杂度也从 O(n) 降至 O(1)。
3. 避免过度优化：
   • 对于小规模数据（如 n < 100），O(n²) 与 O(n log n) 的算法实际执行时间差异可能很小，此时开发效率更重要。
   • 复杂度只是评估指标之一，还需考虑算法的可读性、可维护性等因素。

---

第11章 排序算法

排序算法的作用是将一组无序的数据按照特定顺序（如升序、降序）重新排列。本章将重点介绍三种简单直观的排序算法——冒泡排序、选择排序、插入排序，以及 C++ 标准库中 sort() 排序函数的使用方法。

11.1 排序算法的基本概念

• 排序：将一组数据元素按照关键字（如数值大小）的递增或递减顺序进行排列的过程。
• 稳定性：若排序后，相同关键字的元素相对位置保持不变，则称该排序算法是 稳定的；否则为 不稳定的。
• 内部排序：所有数据都在内存中完成排序（本章介绍的均为内部排序）。
• 外部排序：数据量过大，需借助外部存储（如磁盘）才能完成排序。

11.2 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，其核心思想是通过重复遍历待排序序列，每次比较相邻的两个元素，若顺序错误则交换它们的位置，直到没有元素需要交换为止。因较小的元素会像“气泡”一样逐渐“浮”到序列的前端而得名。

11.2.1 基本思想

1. 从序列的第一个元素开始，依次比较相邻的两个元素。
2. 若前一个元素大于后一个元素（升序排序），则交换它们的位置。
3. 完成一轮遍历后，最大的元素会“冒泡”到序列的末尾。
4. 忽略已排好序的末尾元素，重复上述过程，直到整个序列有序。

11.2.2 实现代码

// 冒泡排序（升序）
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {           // 控制排序轮数，共需 n-1 轮
        bool swapped = false;                   // 标记本轮是否发生交换
        // 每轮遍历范围: 0 ~ n-1-i（末尾 i 个元素已排好序）
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {          // 前元素 > 后元素，交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) { // 若本轮未发生交换，说明序列已有序，提前退出
            break;
        }
    }
}

11.2.3 复杂度与特点

• 时间复杂度：
  • 最坏情况（完全逆序）：O(n²)（需进行 n-1 轮遍历，每轮最多比较 n-1 次）。
  • 最好情况（已有序）：O(n)（仅需 1 轮遍历，未发生交换则退出）。
  • 平均情况：O(n²)。
• 空间复杂度：O(1)（仅使用常数个临时变量）。
• 稳定性：稳定（相等元素不会发生交换，相对位置不变）。
• 特点：实现简单，适用于小规模数据；优化后可在序列基本有序时高效运行。

11.3 选择排序（Selection Sort）

选择排序的核心思想是每一轮从待排序序列中找出最小（或最大）的元素，将其与序列的起始位置元素交换。然后再从剩余未排序元素中重复这一过程，直到整个序列有序。

11.3.1 基本思想

1. 初始时，待排序序列为整个数组，已排序序列为空。
2. 从待排序序列中找出最小元素，将其与待排序序列的第一个元素交换，此时该元素进入已排序序列。
3. 待排序序列范围缩小（排除已排序的第一个元素），重复步骤 2，直到待排序序列为空。

11.3.2 实现代码

// 选择排序（升序）
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {      // 控制已排序元素数量，共需 n-1 轮
        int minIndex = i;                  // 记录待排序序列中最小元素的下标
        // 遍历待排序序列 (i+1 ~ n-1)，找到最小元素
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小元素与待排序序列的第一个元素交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

11.3.3 复杂度与特点

• 时间复杂度：最好、最坏、平均情况均为 O(n²)（无论序列是否有序，都需遍历 n-1 轮，每轮寻找最小元素）。
• 空间复杂度：O(1)（仅使用常数个临时变量）。
• 稳定性：不稳定（交换过程可能改变相同元素的相对位置，例如 {2, 2, 1} 排序时，第一个 2 可能与 1 交换，导致两个 2 的位置颠倒）。
• 特点：实现简单、交换次数少（每轮最多 1 次交换），但比较次数多，适用于小规模数据。

11.4 插入排序（Insertion Sort）

插入排序的核心思想是将待排序序列分为 “已排序” 和 “未排序” 两部分，每次从“未排序”部分取一个元素，插入到“已排序”部分的合适位置，使“已排序”部分始终保持有序，直到“未排序”部分为空。

11.4.1 基本思想

1. 初始时，“已排序”部分包含第一个元素，“未排序”部分包含剩余元素。
2. 从“未排序”部分取第一个元素（称为“待插入元素”），与“已排序”部分的元素从后往前依次比较。
3. 将“已排序”部分中大于“待插入元素”的元素向后移动一位，腾出位置插入“待插入元素”。
4. 重复步骤 2~3，直到“未排序”部分为空。

11.4.2 实现代码

// 插入排序（升序）
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {          // 控制“未排序”部分的元素，从第 2 个元素开始
        int key = arr[i];                  // 待插入元素
        int j = i - 1;                     // “已排序”部分的最后一个元素下标
        // 从后往前比较，将大于 key 的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;                  // 插入待插入元素到正确位置
    }
}

11.4.3 复杂度与特点

• 时间复杂度：
  • 最坏情况（完全逆序）：O(n²)（每轮移动 i 个元素，共移动 1+2+...+(n-1) = n(n-1)/2 次）。
  • 最好情况（已有序）：O(n)（每轮只需比较 1 次，无需移动元素）。
  • 平均情况：O(n²)。
• 空间复杂度：O(1)（仅使用常数个临时变量）。
• 稳定性：稳定（相等元素不交换，相对位置不变）。
• 特点：实现简单，对基本有序的序列效率高（接近 O(n)），适用于小规模数据或作为复杂排序算法的子过程（如归并排序、快速排序的优化）。

11.5 sort() 函数

C++ 标准库 <algorithm> 中提供的 sort() 函数是一种高效的排序函数，其底层通常采用快速排序、堆排序、插入排序的混合算法（如 introsort，当递归深度过大时切换为堆排序，小规模数据时使用插入排序），具有稳定性好、效率高的特点。

11.5.1 基本用法

sort() 函数的语法如下：

#include <algorithm> // 需包含头文件

// 对 [first, last) 范围内的元素按升序排序（默认）
sort(first, last);
// 对 [first, last) 范围内的元素按自定义比较规则 comp 排序
sort(first, last, comp);

• first 和 last：迭代器，分别指向待排序序列的第一个元素和最后一个元素的下一个位置（即 左闭右开区间 [first, last)）。
• comp：可选参数，比较函数或函数对象，用于定义排序规则（如降序）。

11.5.2 使用示例

• 基本类型数组排序：

  #include <iostream>
  #include <algorithm>
  using namespace std;
  
  int main() {
      int arr[] = {3, 1, 4, 1, 5, 9};
      int n = sizeof(arr) / sizeof(arr[0]);
      
      // 升序排序（默认）
      sort(arr, arr + n);
      for (int num : arr) {
          cout << num << " ";
      }
      // 输出：1 1 3 4 5 9
      
      return 0;
  }
  

• 降序排序：

  // 方法 1：使用 greater<>()（需包含 <functional> 头文件）
  #include <functional>
  sort(arr, arr + n, greater<int>());
  
  // 方法 2：自定义比较函数
  bool compare(int a, int b) {
      return a > b; // 若 a > b，则 a 排在 b 前面（降序）
  }
  sort(arr, arr + n, compare);
  

• 自定义类型排序：

  struct Student {
      string name;
      int score;
  };
  
  // 按分数升序排序，分数相同则按姓名升序排序
  bool compareStudent(const Student& s1, const Student& s2) {
      if (s1.score != s2.score) {
          return s1.score < s2.score;
      } else {
          return s1.name < s2.name;
      }
  }
  
  int main() {
      Student students[] = {
          {"Alice", 85},
          {"Bob", 75},
          {"Charlie", 85}
      };
      int n = sizeof(students) / sizeof(students[0]);
      
      sort(students, students + n, compareStudent);
      for (const auto& s : students) {
          cout << s.name << " " << s.score << endl;
      }
      // 输出：
      // Bob 75
      // Alice 85
      // Charlie 85
      return 0;
  }
  

11.5.3 特性与注意事项

• 时间复杂度：平均 O(n log n)，最坏情况 O(n log n)（部分实现为 O(n²)，但标准库通常优化为稳定的 O(n log n)）。
• 空间复杂度：O(log n)（递归调用栈消耗）。
• 稳定性：sort() 函数本身是 不稳定的（相同元素的相对位置可能改变），若需要稳定排序，可使用 stable_sort() 函数。
• 元素要求：待排序元素必须支持比较操作（默认使用 < 运算符，自定义类型需重载 < 或提供比较函数）。

11.6 三种简单排序算法的对比

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	特点
冒泡排序	O(n²)		O(n)	O(1)	稳定	实现简单，适合基本有序序列
选择排序			O(n²)		不稳定	交换次数少，比较次数多
插入排序			O(n)		稳定	适合小规模或基本有序序列，实际应用中表现较好

---

第12章 递推算法

递推算法是一种通过已知条件逐步推导出未知结果的算法思想，它利用问题本身所具有的递推关系，从初始状态出发，按照一定的规律迭代计算，最终得到问题的解。

12.1 递推算法的基本概念

递推算法的核心是 递推关系，即问题的第 n 项结果与前面若干项结果之间存在的确定关系。通过这种关系，我们可以从已知的初始项（或边界条件）出发，逐步计算出后续项，直到得到目标项。

• 递推关系：用数学公式表示为 f(n) = g(f(n-1), f(n-2), …, f(n-k))，其中 g 是关于前 k 项的函数，k 为递推的阶数。
• 初始条件：递推过程的起点，即已知的前若干项（如 f(0), f(1) 等），没有初始条件则无法启动递推。
• 示例：斐波那契数列的递推关系为 f(n) = f(n-1) + f(n-2)，初始条件为 f(0) = 0, f(1) = 1，通过这一关系可逐步计算出任意项 f(n)。

12.2 递推算法的核心思想

递推算法的核心思想是 “由简到繁、逐步迭代”，具体可分为以下步骤：

1. 分析问题：找出问题中隐藏的递推关系，即第 n 项与前面几项的依赖关系。
2. 确定初始条件：明确递推的起点，即已知的初始项值。
3. 迭代计算：根据递推关系和初始条件，从初始项开始，依次计算出后续项，直到得到目标结果。

递推算法的关键在于正确提炼递推关系，一旦递推关系明确，只需通过循环等结构即可实现迭代计算，避免了复杂的递归调用或重复计算。

12.3 递推算法的基本结构

递推算法的实现通常采用循环结构，其基本框架如下：

// 定义初始条件
初始化 f(0), f(1), …, f(k-1)
// 根据递推关系计算后续项
for (int i = k; i <= n; i++) {
    f(i) = g(f(i-1), f(i-2), …, f(i-k)); // 代入递推公式
}
// 输出目标结果 f(n)
return f(n)

其中，k 为递推的阶数（如斐波那契数列是 2 阶递推），g 为递推关系函数。

12.4 递推算法的常见类型

根据递推的方向，递推算法可分为 顺推法 和 逆推法 两类：

12.4.1 顺推法

顺推法是从已知的初始条件出发，按照递推关系逐步计算出后续项，直到得到目标项。这是最常用的递推方式。

示例：斐波那契数列（顺推） 斐波那契数列的定义为：f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) (n≥2)。用顺推法计算第 n 项的代码如下：

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // 初始条件
    int a = 0; // f(0)
    int b = 1; // f(1)
    int result;
    
    // 顺推计算 f(2) 到 f(n)
    for (int i = 2; i <= n; i++) {
        result = a + b; // 递推关系: f(i) = f(i-2) + f(i-1)
        a = b;          // 更新前两项
        b = result;
    }
    return result;
}

12.4.2 逆推法

逆推法是从问题的目标项出发，反向推导出初始条件，适用于已知最终状态而需要求解初始状态的问题。

示例：银行存款问题（逆推） 某人在 n 年后需要获得一定金额的存款，已知年利率，求初始存入的本金。设 f(n) 为第 n 年的存款，年利率为 r，则递推关系为 f(n) = f(n-1) * (1 + r)，逆推可得 f(n-1) = f(n) / (1 + r)。

// 已知 n 年后的目标金额 target，年利率 r，求初始本金
double calculatePrincipal(double target, int n, double r) {
    double f = target; // 第 n 年的存款（目标金额）
    // 逆推计算初始本金（第 0 年）
    for (int i = n; i > 0; i--) {
        f = f / (1 + r); // 递推关系: f(i-1) = f(i) / (1 + r)
    }
    return f; // 返回初始本金 f(0)
}

12.5 递推算法的典型应用

12.5.1 阶乘计算

阶乘的递推关系为 n! = n * (n-1)!，初始条件为 0! = 1。

int factorial(int n) {
    if (n == 0) return 1;
    int result = 1; // 初始条件: 0! = 1
    for (int i = 1; i <= n; i++) {
        result *= i; // 递推关系: i! = i * (i-1)!
    }
    return result;
}

12.5.2 杨辉三角

杨辉三角中第 i 行第 j 列的元素（从 0 开始计数）满足递推关系 C(i, j) = C(i-1, j-1) + C(i-1, j)，初始条件为 C(i, 0) = 1，C(i, i) = 1。

#include <stdio.h>
// 生成杨辉三角，numRows 为行数
void yanghuiTriangle(int numRows) {
    // 用二维数组存储，最大行数为 numRows
    int triangle[numRows][numRows];
    // 生成每一行
    for (int i = 0; i < numRows; i++) {
        // 每行首尾元素为 1
        triangle[i][0] = 1;
        triangle[i][i] = 1;
        // 计算中间元素（上一行相邻两数之和）
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    // 打印结果
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", triangle[i][j]);
        }
        printf("\n");
    }
}

// 示例调用
int main() {
    yanghuiTriangle(5); // 生成并打印 5 行杨辉三角
    return 0;
}

12.5.3 爬楼梯问题

一次可以爬 1 或 2 级台阶，求爬到第 n 级台阶的方法数。递推关系为 f(n) = f(n-1) + f(n-2)（最后一步爬 1 级或 2 级），初始条件为 f(1)=1, f(2)=2。

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, result;
    for (int i = 3; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

12.6 递推算法的复杂度分析

• 时间复杂度：递推算法的时间复杂度通常为 O(n)，其中 n 为问题的规模（如计算第 n 项）。因为算法需要从初始条件开始，依次计算每一项，共执行 n 次迭代。
• 空间复杂度：若仅保留计算所需的前 k 项（如斐波那契数列只保留前两项），空间复杂度为 O(1)；若存储所有计算结果（如杨辉三角存储整个三角形），空间复杂度为 O(n) 或 O(n²)，取决于问题类型。

12.7 递推算法与递归算法的对比

递推算法和递归算法都依赖于问题的递推关系，但实现方式和性能存在差异：

特性	递推算法	递归算法
实现方式	循环迭代，从初始项推出目标项	函数自身调用，从目标项分解到初始项
时间效率	高，无函数调用开销	低，存在重复计算和函数调用开销（未优化时）
空间效率	低，可优化为 O(1)	高，递归栈可能占用 O(n) 空间
可读性	稍差，需手动迭代	较好，逻辑接近问题描述
适用场景	大规模问题，避免栈溢出	小规模问题或逻辑天然递归的场景

例如，计算斐波那契数列时，递推算法的时间复杂度为 O(n)，空间复杂度为 O(1)，而未优化的递归算法时间复杂度为 O(2ⁿ)，空间复杂度为 O(n)，递推算法更具优势。

12.8 使用注意事项

1. 明确递推关系：递推关系是算法的核心，需通过数学分析或问题建模确保其正确性。
2. 设置正确的初始条件：初始条件错误会导致后续所有计算结果错误，需根据问题定义准确设置。
3. 优化空间复杂度：对于高阶递推，无需存储所有历史项，只需保留必要的前 k 项即可（如斐波那契数列只需保留前两项）。
4. 处理边界情况：如 n=0、n=1 等特殊值，需单独处理以避免逻辑错误。
5. 避免数值溢出：对于大规模计算（如阶乘、斐波那契数列的高项），需注意数据类型的范围，必要时使用大数处理技巧。