# 第六章 数组

> Arietids Learn · 个人课程复习笔记
> 在线阅读：https://learn.arietids.net/courses/programming/chapter-06/

## 关键考点总览

1. 数组的定义格式（元素个数必须是常量表达式）
2. 数组的初始化方式（完全初始化、部分初始化、省略大小）
3. 数组下标从0开始，范围0至n-1
4. 数组在内存中连续存储，下标超界问题
5. 顺序查找与二分查找算法
6. 选择排序与冒泡排序算法
7. 时间复杂度分析：O(N) vs O(log₂N)
8. 多维数组的定义、内存排列（行优先/后下标先变）
9. 字符串的表示（字符数组 + '\0'）
10. 字符串处理函数（cstring库）

---

## 详细知识点

### 6.1 一维数组

#### 定义/语法

- **数组定义格式**：
  ```cpp
  类型 数组名[元素个数];
  ```
  示例：`int array[5];`
  [来源：第6章 p7，数组的定义]

- **定义数组时元素个数必须是常量表达式**，不能用变量：
  ```cpp
  int n = 5;
  int array[n];  // ❌ 标准 C++ 不支持变长数组(VLA)；少数编译器扩展可能允许，但不具可移植性
  
  const int NumOfElement = 5;  // ✅ 编译期常量（需用常量表达式初始化）
  int array[NumOfElement];  // ✅ 正确：数组长度必须是常量表达式
  ```
  [来源：第6章 p7，数组的定义]

- **数组元素引用方式**：通过数组名和下标引用，如 `array[2]`
  - 下标可为任意整型表达式（整数常量、整型变量、整型算术表达式）
  [来源：第6章 p7，数组的定义]

#### 规则/规范

- **数组下标从0开始**，当数组大小为n时，下标范围为 **0 至 n-1**
  [来源：第6章 p7，数组的定义]

- **下标从0开始的原因**（戴克斯特拉主张）：
  1. 子序列 a[i..j) 包含的元素个数就是 j-i（更优雅）
  2. 第i个元素的位置是 基地址 + i×元素大小（即从基地址偏移 i 个元素），避免偏移量计算中的减法
  3. [i, i) 自然表示空序列
  [来源：第6章 p8，为什么下标应该从0开始]

- **只能对具体元素操作，不能对数组整体操作**：
  ```cpp
  int arr[5];
  cin >> arr;  // ❌ 错误：不能直接输入整个数组
  
  for (int i = 0; i < 5; i++)
      cin >> arr[i];  // ✅ 正确：逐个元素输入
  
  arr = {1,2,3,4,5};  // ❌ 错误：内置数组不可整体赋值（只能在定义时用{}初始化）
 // ✅ 正确做法：在定义时初始化：int arr2[5] = {1,2,3,4,5};
  ```
  [来源：第6章 p11，数组的操作]

#### 初始化

- **完全初始化**：
  ```cpp
  float x[5] = {-1.1, 0.2, 33.0, 4.4, 5.05};
  ```
  [来源：第6章 p10，初始化]

- **部分初始化**：初始化表长度短于数组元素数目时，**剩余元素被初始化为0**：
  ```cpp
  float x[5] = {-1.1, 0.2, 33.0};
  // 等价于 float x[5] = {-1.1, 0.2, 33.0, 0, 0};
  ```
  [来源：第6章 p10，初始化]

- **省略数组大小**：带初始化的数组可以不定义规模，编译器根据初值个数决定大小：
  ```cpp
  int a[] = {1,2,3,4,5};  // 默认数组大小为5
  ```
  [来源：第6章 p10，初始化]

#### 内存模型

- **数组在内存中连续存储**：定义数组就是定义了一块连续的内存空间，空间大小 = 元素个数 × 每个元素所占空间大小
  [来源：第6章 p12，数组存在于内存中]

- 示例：
  - `char string[4]` 占用4个连续字节（地址如99, 100, 101, 102）
  - `short scores[3]` 占用 `3×sizeof(short)` 个连续字节（`sizeof(short)` 至少为2，常见为2）
  [来源：第6章 p12，数组存在于内存中]

#### 易错点与辨析

- ⚠️ **数组下标越界（越界访问/缓冲区溢出）**：
  - 对内置数组（原生数组），C/C++语言层面**不做运行时下标越界检查**
  - 如定义 `int array[10]`，合法下标范围是0至9；访问 `array[10]` **属于未定义行为（UB）**，可能“看起来没事”，也可能崩溃或破坏数据
  - 超界访问可能改写其他变量的数据，造成程序甚至系统崩溃
  - **语言本身不提供自动越界检查**；编译器/IDE 有时能对“明显的常量越界”给出告警，但一般无法保证发现所有越界。可借助静态分析、AddressSanitizer(ASan)/UBSan 等工具辅助排查
  [来源：第6章 p13，数组下标超界问题]

- ⚠️ **更常见的越界来自输入/拷贝写入**（如 `cin >> char数组`、`strcpy/strcat` 等），可能导致缓冲区溢出；编译器通常不会在运行时阻止
  [来源：第6章 p13，Notes]

---

### 6.2 查找和排序

#### 算法1：顺序（线性）查找

- **适用条件**：无需有序（任意序列都可用；对有序序列还可加入“提前停止”优化）
- **算法描述**：从头到尾扫描序列，逐个比较每个元素的值是否与目标值相同；找到则返回序号并结束，否则直到序列结束返回-1表示未找到
  [来源：第6章 p17，算法1：顺序（线性）查找]

- **代码模式**：
  ```cpp
  int k, x;
  int array[] = {2, 3, 1, 7, 5, 8, 9, 0, 4, 6};
  cout << "请输入要查找的元素值："; cin >> x;
  for (k = 0; k < 10; ++k)
      if (x == array[k]) {
          cout << k;
          break;
      }
  if (k == 10) cout << "-1";
  ```
  [来源：第6章 p17，顺序查找代码]

#### 算法2：二分查找

- **适用条件**：序列**已排序**
- **算法描述**：每次拿出序列中间的元素与目标值比较：
  - 如果相同则找到
  - 如果目标值大于中间元素，则取序列后一半重复
  - 如果目标值小于中间元素，则取序列前一半重复
  - 直到找到或没有可再分的序列为止
  [来源：第6章 p18，算法2：二分查找]

- **代码模式**：
  ```cpp
  int lh, rh, mid, x;
  int array[] = {0,1,2,3,4,5,6,7,8,9};
  cout << "请输入要查找的数据："; cin >> x;
  lh = 0, rh = 9;
  while (lh <= rh) {
      mid = lh + (rh - lh) / 2;  // 更稳妥：避免(lh+rh)在大规模下标时溢出
      if (x == array[mid]) {
          cout << x << "的位置是：" << mid << endl;
          break;
      }
      if (x < array[mid])
          rh = mid - 1;
      else
          lh = mid + 1;
  }
  if (lh > rh) cout << "没有找到" << endl;
  ```
  [来源：第6章 p19，二分查找代码]

- ⚠️ **易错点**：二分查找中 `mid+1` 和 `mid-1` 不能省略，否则可能陷入死循环
  - 例如：在 `{0,1,2,3,4,6,7,8,9,10,11}` 中查找5会陷入死循环
  [来源：第6章 p19，Notes]

#### 选择排序法

- **算法描述**：
  1. 从未排序部分找到最小元素
  2. 与未排序部分的第一个元素交换
  3. 重复直到全部排序完成
  [来源：第6章 p21，选择排序法]

- **代码模式**：
  ```cpp
  int array[] = {2, 5, 1, 9, 10, 0, 4, 8, 7, 6};
  int lh, minh, k, tmp, n = 10;
  
  for (lh = 0; lh < n-1; lh++) {
      minh = lh;
      for (k = lh; k < n; ++k)
          if (array[k] < array[minh]) minh = k;
      tmp = array[lh];
      array[lh] = array[minh];
      array[minh] = tmp;
  }
  ```
  [来源：第6章 p22，选择排序代码]

- **循环结构**：两重循环
  - 外层循环：`lh` 从0到n-2（控制已排序边界）
  - 内层循环：`k` 从lh到n-1（寻找最小元素）
  [来源：第6章 p21-22]

#### 冒泡排序法

- **算法描述**：
  1. 对序列从头扫描，比较相邻两个元素
  2. 如果大的在前小的在后，就交换（冒泡过程）
  3. 一趟扫描后最大元素到最后位置
  4. 重复以上过程
  [来源：第6章 p23，气泡排序法]

- **代码模式**（含优化）：
  ```cpp
  int a[] = {0, 3, 5, 1, 8, 7, 9, 4, 2, 10, 6};
  int i, j, tmp, n = 11;
  bool flag;
  
  for (i = n-1; i > 0; i--) {  // i表示本趟比较的上界（未排序区间末尾下标），最大元素会“冒”到 i 位置
      flag = true;
      for (j = 0; j < i; ++j)  // j遍历待冒泡序列
          if (a[j] > a[j+1]) {
              tmp = a[j];
              a[j] = a[j+1];
              a[j+1] = tmp;
              flag = false;
          }
      if (flag) break;  // 一趟冒泡中没有发生交换，排序结束
  }
  ```
  [来源：第6章 p25，冒泡排序代码]

- **优化点**：使用 `flag` 标志，若一趟冒泡中没有发生交换，说明已排序完成，可提前结束
  [来源：第6章 p25，Notes]

#### 时间复杂度分析

- **算法效率衡量标准**：
  - **时间复杂度**：程序执行时间与问题规模之间的关系
  - **空间复杂度**：程序运行所占用的存储空间与问题规模之间的关系
  [来源：第6章 p26，哪个算法更好]

- **线性搜索时间复杂度**：
  - 最好情况：1步（第一个元素就找到）
  - 最坏情况：N步
  - 平均情况：(N+1)/2次
  - **最坏时间复杂度：O(N)**
  [来源：第6章 p27，时间复杂度分析]

- **二分搜索时间复杂度**：
  - 最好情况：1步（中间位置找到）
  - 最坏情况：log₂N步（不断二分直到不可再分）
  - 平均情况：log₂N级别
  - **最坏时间复杂度：O(log₂N)**
  [来源：第6章 p27，时间复杂度分析]

- **效率对比实例**：搜索10⁶个元素的列表，二分搜索只需**20步**，而线性搜索需要**10⁶步**
  [来源：第6章 p28，不同时间复杂度算法的效率]

- **为什么是log₂N**：每次二分至少筛选掉剩余元素的一半，经历log₂N次二分就能找到答案（N/2^m，所以 m = log₂N）
  [来源：第6章 p27，Notes]

---

### 6.3 多维数组

#### 定义/语法

- **多维数组定义**：数组的每一个元素又是数组的数组
- **二维数组定义格式**：
  ```cpp
  类型 数组名[常量表达式1][常量表达式2];
  ```
  示例：
  ```cpp
  int a[4][5];
  // 可以理解为定义了一维数组a[4]，每个元素又是一维数组int[5]
  // a[0], a[1]等就是数组名，其元素就是a[0][0], a[0][1], a[1][0]等
  ```
  [来源：第6章 p38，多维数组]

#### 内存排列（重要）

- **二维数组在内存中按一维连续存放**，采用**行优先（后下标先变）**的方式：
  ```
  a[0][0], a[0][1], a[0][2], a[0][3], a[0][4],
  a[1][0], a[1][1], ...
  ```
  [来源：第6章 p39，二维数组的表示]

- **规则**：最后一位下标先改变，进行一轮之后，倒数第二个下标加一，依次轮替
  [来源：第6章 p39，Notes]

#### 初始化

- **按一维形式初始化**（按存储顺序）：
  ```cpp
  int a[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
  ```
  [来源：第6章 p40，多维数组的初始化]

- **用花括号分行初始化**：
  ```cpp
  int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
  ```
  [来源：第6章 p40，多维数组的初始化]

- **部分初始化**（其他元素默认为0）：
  ```cpp
  int a[3][4] = {1, 2, 3, 4, 5};  // 按一维顺序，后面补0
  int a[3][4] = {{1, 2}, {3, 4}, {5}};  // 每行部分初始化
  // 结果：第0行[1,2,0,0]，第1行[3,4,0,0]，第2行[5,0,0,0]
  ```
  [来源：第6章 p40，多维数组的初始化]

#### 代码模式：矩阵乘法

- **矩阵乘法核心代码**：
  ```cpp
  for (i = 0; i < NumOfRowA; ++i)
      for (j = 0; j < NumOfColB; ++j) {
          c[i][j] = 0;
          for (k = 0; k < NumOfColA; ++k)
              c[i][j] += a[i][k] * b[k][j];
      }
  ```
  [来源：第6章 p42，矩阵乘法代码]

---

### 6.4 字符串

#### 定义/语法

- **字符串**：由一系列字符组成的一维数组
- **字符串常量**：用一对双引号括起来，如 `"Hello!"`
- **字符串变量**：用字符类型的数组表示和存储
  [来源：第6章 p44，字符串]

- **字符串初始化的三种常见方式（C 风格字符串）**：
  ```cpp
  char ch1[] = "Hello!";                       // 编译器自动补 '\0'，数组长度为 7
  char ch2[7] = "Hello!";                      // 显式给出长度（需包含 '\0'）
  char ch3[] = {'H','e','l','l','o','!','\0'}; // 字符列表（需手动写 '\0'）  
  ```
  [来源：第6章 p44，字符串]

- **空字符串**：不包含任何字符的字符串 `""`，占用1个字节（存储 `'\0'`）
  [来源：第6章 p44，字符串]

#### 规则/规范

- **字符串以 `'\0'` 结尾**：字符串除了存放指定数据，还要默认存一位空字符 `'\0'`，所以尺寸是元素个数+1
  [来源：第6章 p44，字符串]

- ⚠️ **注意 `'a'` 和 `"a"` 的区别**：
  - `'a'` 是一个单字符，占**1个字节**
  - `"a"` 是一个字符串，占**2个字节**（'a' + '\0'）
  [来源：第6章 p44，字符串]

#### 字符串的输入输出

- **用 `cin >>` 输入**：
  ```cpp
  cin >> ch;
  ```
  - ⚠️ 无法输入包含空白字符的字符串（空格会被当作输入结束）
  - ⚠️ cin不检查输入是否越界
  [来源：第6章 p45，字符串的输入输出]

- **用 `cin.getline()` 输入任意字符串**：
  ```cpp
  cin.getline(ch, 数组长度, 结束标记);
  // 输入到达"数组长度-1"或遇到标记字符时结束
  // 结束标记可以缺省，此时回车是默认结束标记
  ```
  [来源：第6章 p45，字符串的输入输出]

- **输出字符串**：
  ```cpp
  cout << ch;  // 可以直接用数组名输出，一般数组不行
  ```
  [来源：第6章 p45，字符串的输入输出]

#### 字符串处理函数（cstring库）

| 函数 | 功能 |
|------|------|
| `char *strcpy(dst, src)` | 拷贝字符串src到dst，包括'\0'，返回dst |
| `char *strncpy(dst, src, n)` | 至多从src拷贝n个字符到dst；若src长度≥n则不会自动补'\0'；src不足n时其余补0 |
| `char *strcat(dst, src)` | 将src接到dst尾，返回dst |
| `char *strncat(dst, src, n)` | 从src至多取n个字符接到dst尾，并补'\0' |
| `size_t strlen(s)` | 返回s的长度（不含'\0'） |
| `int strcmp(s1, s2)` | 比较s1和s2：s1>s2返回正数，相等返回0，s1<s2返回负数 |
| `int strncmp(s1, s2, n)` | 如strcmp，但至多比较n个字符 |
| `char *strchr(s, ch)` | 返回s中第一次出现ch的地址，不存在返回NULL |
| `char *strrchr(s, ch)` | 返回s中最后出现ch的地址，不存在返回NULL |
| `char *strstr(s1, s2)` | 返回s1中第一次出现s2的地址，不存在返回NULL |

[来源：第6章 p46，字符串处理函数]

- **头文件**：`#include <cstring>`
  [来源：第6章 p46，字符串处理函数]

- ⚠️ **注意**：`strlen()` 和 `sizeof()` 不同：
  - `strlen()` 返回字符串长度（不含'\0'）
  - `sizeof()` 返回数组占用的字节数
  [来源：第6章 p46，Notes]

---

### 6.5 例题结论

#### 【执行结果分析】字母频率统计

- **问题**：输入一串小写字母，统计每个字母出现的次数
- **关键技巧**：利用字符运算 `ch - 'a'` 将字母映射到数组下标0-25
- **代码要点**：
  ```cpp
  int count[26] = {0};
  char ch;
  ch = cin.get();
  while (ch >= 'a' && ch <= 'z') {
      ++count[ch - 'a'];
      ch = cin.get();
  }
  ```
  [来源：第6章 p14-15，字母频率统计]

#### 【执行结果分析】单词统计

- **问题**：输入一行文字，统计有多少个单词（单词之间以空格分开）
- **算法**：当发现当前字符为非空格而前一字符是空格时，找到一个新单词
- **代码要点**：
  ```cpp
  char sentence[80], prev = ' ';
  int i, num = 0;
  cin.getline(sentence, 80);
  for (i = 0; sentence[i] != '\0'; ++i) {
      if (prev == ' ' && sentence[i] != ' ') ++num;
      prev = sentence[i];
  }
  ```
  [来源：第6章 p47-48，单词统计]

#### 例题思路提示

1. **埃拉托斯特尼筛法求素数**：要得到n以内的全部素数，必须把不大于√n的所有素数的倍数剔除
   - 原理：任何非质数都会有一个因数不大于它的算术平方根（因为是一大一小配对相乘）
   [来源：第6章 p50，例题Notes]

2. **ISBN校验**：
   - 旧版（10位 ISBN-10）：设数字为 d1..d10（d10 可能为 X 表示10），满足 (10·d1 + 9·d2 + ... + 1·d10) mod 11 = 0
   - 新版（13位 ISBN-13）：前12位按权 1,3,1,3,... 加权求和为 S，校验位 d13 = (10 - (S mod 10)) mod 10（等价于 (S + d13) mod 10 = 0）
   [来源：第6章 p51，例题]

---

## 扩展知识（了解即可）

### P vs NP问题

- **多项式时间**：存在常数k，使得算法最坏运行时间在O(n^k)以内
- **P问题**：能在多项式时间内被解决的决策问题
- **NP问题**：能在多项式时间内被验证的决策问题
- P ⊆ NP，但 P=NP? 是未解决的千禧年难题之一
  [来源：第6章 p32，P vs NP问题]

### 深度学习与NP问题

- 深度学习为NP难问题提供实用的启发式或近似解法
- 优势：推理速度快、泛化能力强、能处理高维输入
- 局限：无法解决P vs NP理论问题、非精确解法、训练成本高
  [来源：第6章 p35-36，深度学习和NP问题]