第六章 数组

程序设计目录下载 Markdown

关键考点总览

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

---

详细知识点

6.1 一维数组

定义/语法

• 数组定义格式：

  类型 数组名[元素个数];

  示例：int array[5]; [来源：第6章 p7，数组的定义]

• 定义数组时元素个数必须是常量表达式，不能用变量：

  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开始]

• 只能对具体元素操作，不能对数组整体操作：

  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：

  float x[5] = {-1.1, 0.2, 33.0};
  // 等价于 float x[5] = {-1.1, 0.2, 33.0, 0, 0};

  [来源：第6章 p10，初始化]

• 省略数组大小：带初始化的数组可以不定义规模，编译器根据初值个数决定大小：

  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：顺序（线性）查找]

• 代码模式：

  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：二分查找]

• 代码模式：

  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，选择排序法]

• 代码模式：

  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，气泡排序法]

• 代码模式（含优化）：

  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 多维数组

定义/语法

• 多维数组定义：数组的每一个元素又是数组的数组
• 二维数组定义格式：

  类型 数组名[常量表达式1][常量表达式2];

  示例：

  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]

初始化

• 按一维形式初始化（按存储顺序）：

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

  [来源：第6章 p40，多维数组的初始化]

• 用花括号分行初始化：

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

  [来源：第6章 p40，多维数组的初始化]

• 部分初始化（其他元素默认为0）：

  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，多维数组的初始化]

代码模式：矩阵乘法

• 矩阵乘法核心代码：

  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 风格字符串）：

  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 >> 输入：

  cin >> ch;

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

• 用 cin.getline() 输入任意字符串：

  cin.getline(ch, 数组长度, 结束标记);
  // 输入到达"数组长度-1"或遇到标记字符时结束
  // 结束标记可以缺省，此时回车是默认结束标记

  [来源：第6章 p45，字符串的输入输出]

• 输出字符串：

  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
• 代码要点：

  int count[26] = {0};
  char ch;
  ch = cin.get();
  while (ch >= 'a' && ch <= 'z') {
      ++count[ch - 'a'];
      ch = cin.get();
  }

  [来源：第6章 p14-15，字母频率统计]

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

• 问题：输入一行文字，统计有多少个单词（单词之间以空格分开）
• 算法：当发现当前字符为非空格而前一字符是空格时，找到一个新单词
• 代码要点：

  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问题]