第11讲：数组与指针进阶

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

课前准备

在WSL Ubuntu中建立一个专门的目录用于课上练习，如~/course

$ mkdir ~/course

打开VSCode并连接到WSL，打开此目录并新建文件，如~/course/main.cpp
编辑main.cpp，随堂编程练习的代码请直接在此文件中编辑

main.cpp

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

int main() {
  // ============= begin =============

  // =============  end  =============
  return 0;
}

温故

测一测

试判断，下面的程序输出是什么？

strquiz.cpp

#include <iostream>
#include <iomanip>
#include <cstring>

int main() {
  char likui[] = "likui";
  char ligui[] = {'l', 'i', 'k', 'u', 'i'};
  std::cout << std::boolalpha << (std::strcmp(likui, ligui) == 0) << std::endl;
  return 0;
}

学习目标

学习内容
- 多维数组
- 多重指针
- 动态内存分配

学习目标

理解多维数组与多重指针的内存布局
应用多维数组与多重指针表示矩阵等二维数据
掌握动态内存分配与回收的基本方法

一、多维数组

地形分析

地形图

将地面在经度与纬度方向上切分为一个网格

网格的每个点存储该点的海拔高度
若一个格点高于大于上下左右四个格点，则该点为山峰
若一个格点高于小于上下左右四个格点，则该点为山谷

如何在计算机中表示地形图？
编写程序，分析地形信息找寻所有的山峰与山谷

1.1 多维数组的概念

数组的维度可以有多个，每个维度使用独立的索引（下标）
- 一维数组可表示数学中的向量
- 二维数组可表示数学中的矩阵
- 三维及以上数组可表示数学中的张量
n维数组中的元素由一个n维索引\((i_0, i_1, \cdots, i_{n-1})\)唯一确定

多维数组学习方式

研究多维数组，通常以二维数组为例，向更高维度推广

1.2 二维数组的定义

C++数组定义语法为

存储类别 元素类型 数组名[维度1长度][维度2长度];

元素类型可以是任意基础类型或复合类型
数组长度是一个整型表达式，可以是常量或变量

数组定义示例

// 定义一个二维数组
//   - 数组名为a
//   - 数组元素类型为double，表示每个地形点的高度为double类型
//   - 维度1长度为3，表示有3行，合法的索引为0~2
//   - 维度2长度为4，表示有4列，合法的索引为0~3
double a[3][4];

1.3 二维数组的逻辑结构

二维数组的逻辑结构为一个矩阵
- 各行长度与各列长度相同
- 每个元素由两个索引（行号与列号）唯一确定

二维数组逻辑结构

1.4 二维数组的内存布局

在C++中，二维数组的内存布局为行主序（也称行优先），即同一行连续存储

二维数组的内存布局

明察秋毫

二维数组可视为一维数组的数组，即每个元素都是一个一维数组
- 如a[0]、a[1]、a[2]都是长度为4的一维数组

1.5 数组的数组

考考你

如何理解“二维数组是一维数组的数组”？

arrayofarray.cpp

#include <iostream>
int main() {
  double a[3][4];
  double *row0 = a[0]; // a[0]是一个一维数组，本质是一个地址，可赋值给指针
  double *p = a;       // a是一个二维数组，本质也是一个地址，也可赋值给指针？
  return 0;
}

$ g++ -o code/arrayofarray code/arrayofarray.cpp

code/arrayofarray.cpp: In function ‘int main()’:
code/arrayofarray.cpp:5:15: error: cannot convert ‘double (*)[4]’ to ‘double*’ in initialization
    5 |   double *p = a;       // a是一个二维数组，本质也是一个地址，也可赋值给指针？
      |               ^
      |               |
      |               double (*)[4]

1.6 二维数组的初始化

二维数组可在定义的同时进行初始化

arrayinit.cpp

int main() {
  double a[2][3] = {{1, 2, 3}, {4, 5, 6}}; // 嵌套初始化列表，初始化所有元素
  double b[2][3] = {{}, {4}};              // 嵌套初始化列表，初始化部分元素，其他元素被初始化为0
  double c[2][3] = {1, 2, 3, 4, 5, 6};     // 平坦初始化列表，按照存储顺序初始化所有元素
  double d[2][3] = {1, 2, 3, 4, 5};        // 平坦初始化列表，按照存储顺序初始化前面部分元素，其他元素被初始化为0
  double e[][3] = {{1, 2, 3}, {4, 5}};     // 自动推导维度1长度为2
  double f[][] = {{1, 2, 3}, {4, 5, 6}};   // 编译错误，除维度1以外，后续维度长度必须指定
  return 0;
}

$ g++ -o code/arrayinit code/arrayinit.cpp

code/arrayinit.cpp: In function ‘int main()’:
code/arrayinit.cpp:7:10: error: declaration of ‘f’ as multidimensional array must have bounds for all dimensions except the first
    7 |   double f[][] = {{1, 2, 3}, {4, 5, 6}};   // 编译错误，除维度1以外，后续维度长度必须指定
      |          ^
/bin/bash: line 1: ./code/arrayinit: No such file or directory

考考你

为什么只有第一维长度可以省略？

教员箴言

明明白白使用嵌套初始化列表
尽量显式给出所有维度的长度

1.7 索引二维数组元素

二维数组使用两个索引访问元素

arrayaccess.cpp

#include <iostream>
int main() {
  int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
  arr[0][0] += 1;                      // 写第0行第0列的元素
  std::cout << arr[0][0] << std::endl; // 读第0行第0列的元素
  std::cout << arr[3][0] << std::endl; // 行越界
  std::cout << arr[0][4] << std::endl; // 列越界
  arr[0][4] = -1;                      // 列越界
  std::cout << arr[1][0] << std::endl; // 读第1行第0列的元素
  return 0;
}

$ g++ -o code/arrayaccess code/arrayaccess.cpp
$ ./code/arrayaccess

考考你

为什么输出arr[1][0]的值不是5而是-1？

1.8 二维数组的遍历

二维数组的遍历一般使用嵌套循环

arraytraverse.cpp

#include <iostream>
int main() {
  int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
  int sum = 0;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
      sum += arr[i][j]; // 访问二维数组的元素
    }
  }
  std::cout << sum << std::endl;
  return 0;
}

明察秋毫

使用for循环遍历数组最为便利，循环嵌套的顺序决定了遍历维度的顺序。如果希望以先列后行的顺序遍历，应该如何修改代码？

1.9 二维数组做为函数参数

arrayparam.cpp

#include <iostream>
void printMatrix(double matrix[][7], int rows, int cols) {
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j)
      std::cout << matrix[i][j] << " ";
    std::cout << std::endl;
  }
}
int main() {
  double matrix[6][7] = {
      {5039, 5127, 5238, 5259, 5248, 5310, 5299},
      {5150, 5392, 5410, 5401, 5320, 5820, 5321},
      {5290, 5560, 5490, 5421, 5530, 5831, 5210},
      {5110, 5429, 5430, 5411, 5459, 5630, 5319},
      {4920, 5129, 4921, 5821, 4722, 4921, 5129},
      {5023, 5129, 4822, 4872, 4794, 4862, 4245}};
  printMatrix(matrix, 6, 7);
  return 0;
}

$ g++ -o code/arrayparam code/arrayparam.cpp
$ ./code/arrayparam

5039 5127 5238 5259 5248 5310 5299 
5150 5392 5410 5401 5320 5820 5321 
5290 5560 5490 5421 5530 5831 5210 
5110 5429 5430 5411 5459 5630 5319 
4920 5129 4921 5821 4722 4921 5129 
5023 5129 4822 4872 4794 4862 4245

考考你

二维数组作为形式参数时，维度信息是否可以省略？

1.10 二维数组向高维数组的推广

二维数组的性质可以推广到高维数组，以三维数组为例

定义与初始化

int a[2][2][3] = {
  {{1, 2, 3}, {4, 5, 6}},
  {{7, 8, 9}, {10, 11, 12}}
};
int b[][2][3] = { // 仅最高维可省略
  {{1, 2, 3}, {4, 5, 6}},
  {{7, 8, 9}, {10, 11, 12}}
};

内存布局：以二维数组为元素的数组
索引

a[1][0][2] = 9;

遍历

for (int i = 0; i < 2; i++) {
  for (int j = 0; j < 2; j++) {
    for (int k = 0; k < 3; k++) {
      cout << a[i][j][k] << " ";
    }
  }
}

作为函数参数

// 仅最高维可省略
void func(int a[][2][3]) {
  // ...
}

二维数组应用：地形分析

地形数据放在二维数组matrix中，编写程序计算山峰与山谷的数目
- 网格边缘的格点不计入统计

landscape.cpp

#include <iostream>
void landscape(const double matrix[][7], int row, int col, int &numPeaks, int &numValleys) {
  numPeaks = numValleys = 0;
  // ------------- begin -------------
  // ------------- end ---------------
}
int main() {
  double matrix[6][7] = {{5039, 5127, 5238, 5259, 5248, 5310, 5299},
                         {5150, 5392, 5410, 5401, 5320, 5820, 5321},
                         {5290, 5560, 5490, 5421, 5530, 5831, 5210},
                         {5110, 5429, 5430, 5411, 5459, 5630, 5319},
                         {4920, 5129, 4921, 5821, 4722, 4921, 5129},
                         {5023, 5129, 4822, 4872, 4794, 4862, 4245}};
  int numPeaks, numValleys;
  landscape(matrix, 6, 7, numPeaks, numValleys);
  std::cout << "Number of peaks: " << numPeaks << std::endl;
  std::cout << "Number of valleys: " << numValleys << std::endl;
  return 0;
}

二、多重指针

2.1 多重指针的概念

指向指针的指针，称为多重指针

ptrptr.cpp

#include <iostream>

int main() {
  int a = 10;
  int *pa = &a;
  int **ppa = &pa;
  std::cout << "a = " << a << ", *pa = " << *pa << ", **ppa = " << **ppa << std::endl;
  return 0;
}

$ g++ -o code/ptrptr code/ptrptr.cpp
$ ./code/ptrptr

a = 10, *pa = 10, **ppa = 10

考考你

多重指针有什么用？

2.2 指针数组

若数组的元素类型为指针，则称为指针数组

ptrarray.cpp

#include <iostream>

int main() {
  char hello[] = "hello";
  char space[] = " ";
  char world[] = "world";
  char *message[] = {hello, space, world};
  for (int i = 0; i < 3; i++)
    std::cout << message[i];
  return 0;
}

$ g++ -o code/ptrarray code/ptrarray.cpp
$ ./code/ptrarray

hello world

考考你

以上代码中的几个数组在内存中是如何分布的？

2.3 指针数组与二维数组

使用指针数组也可实现二维数据的存储与表示

matrixasptrarray.cpp

#include <iostream>

int main() {
  int row0[] = {0, 1, 2, 3, 4};
  int row1[] = {5, 6, 7, 8, 9};
  int row2[] = {10, 11, 12, 13, 14};
  int *matrix[] = {row0, row1, row2};
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 5; j++)
      std::cout << matrix[i][j] << " ";
    std::cout << std::endl;
  }
  return 0;
}

$ g++ -o code/matrixasptrarray code/matrixasptrarray.cpp
$ ./code/matrixasptrarray

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

考考你

请解释第10行中使用两个索引操作符访问数据的原理
这与二维数组的索引方式有什么联系？
两种方式各有什么优缺点？试从存储空间与访问时间两个角度分析。

2.3 指针数组与二维数组

明察秋毫

多维数组无额外存储开销、访问效率高（一次访存）
指针数组有额外存储开销、访问效率低（多次访存），但对于不规则形态的二维数据，可减少内存浪费

2.4 指针数组与多重指针

考考你

数组名的本质是一个地址（指针），那么指针数组名的本质是一个什么类型的指针？

指针数组与多重指针

#include <iostream>
int main() {
  char hello[] = "hello";
  char space[] = " ";
  char world[] = "world";
  char *message[] = {hello, space, world};
  char **ptr = message;
  std::cout << ptr[2][1] << std::endl; // 输出o
  return 0;
}

教员箴言

指针数组与多重指针的关系，就是指针与数组的关系
- 前者常量，后者变量，在使用上具有互换性

多重指针练习

测一测

编写函数findMaxRow，找到指针数组表示的矩阵中最大值所在行的首地址（以参数形式返回）

findmaxrow.cpp

#include <iostream>
#include <cstdlib>
void findMaxRow(double **matrix, int row, int col, double **maxRow) {
  double max = matrix[0][0];
  // ========= begin =========
  // ========= end =========
}

int main() {
  double row0[5], row1[5], row2[5];
  for (int i = 0; i < 5; i++) {
    row0[i] = (double)rand() / RAND_MAX;
    row1[i] = (double)rand() / RAND_MAX;
    row2[i] = (double)rand() / RAND_MAX;
  }
  double *matrix[] = {row0, row1, row2};
  double *maxrow;
  findMaxRow(matrix, 3, 5, &maxrow);
  std::cout << "Max row: " << (maxrow == row0? 0 : maxrow == row1? 1 : 2) << std::endl;
}

三、动态内存管理

问题引入：读入多行文本

读入多行文本

要求从标准输入读取多行文本，每次一行，存储在一个二维数组中。若读取行数，每行文本长度均从键盘输入，如何定义这个二维数组？

读取多行文本存入二维数组

#include <iostream>
const int MAX_LINE_LENGTH = 10;
int main() {
  int numLines;
  std::cin >> numLines; // 读取行数
  char lines[numLines][MAX_LINE_LENGTH];
  for (int i = 0; i < numLines; i++) {
    int length;
    std::cin >> length; // 读取每行长度
    if (length > MAX_LINE_LENGTH) {
      std::cerr << "超出最大长度！" << std::endl;
      return 1;
    }
    std::cin >> lines[i]; // 读取每行文本
  }
  return 0;
}

考考你

左边的程序无法处理用户输入文本长度超过MAX_LINE_LENGTH的情况，这个问题能否解决？

关键问题

C++支持定义动态大小的多维数组，但在多行文本输入问题中，二维数组的列数无法在输入文本之前决定！

3.1 静态内存分配与动态内存分配

静态内存分配：在编译时分配内存，程序运行时不可修改
- 如全局变量、静态变量、局部变量
动态内存分配：在程序运行时分配内存，程序运行时可以修改
- 如动态长度数组

3.2 动态内存管理

C++支持动态内存管理（分配与释放），标准方式是使用new与delete运算符

dynamicmemory.cpp

#include <iostream>
int main() {
  int *pLen = new int;   // 动态分配一个int类型的内存空间
  if (pLen == nullptr) { // 检查内存分配是否成功
    std::cout << "动态内存分配失败！" << std::endl;
    return 1;
  }
  std::cin >> *pLen;
  char *pText = new char[*pLen]; // 动态分配长度为length的数组
  if (pText == nullptr) {        // 检查内存分配是否成功
    std::cout << "动态内存分配失败！" << std::endl;
    return 1;
  }
  std::cin >> pText;
  std::cout << pText << std::endl;
  delete[] pText; // 释放动态分配的数组内存
  delete pLen;    // 释放动态分配的变量内存
  return 0;
}

new运算符用于为指定类型的变量分配内存，返回指向新分配内存的指针
delete运算符用于释放内存
new[]与delete[]为数组版本
分配失败则返回nullptr，使用前须检查

3.3 动态内存管理的步骤

动态内存管理应遵循4个步骤
1. 确定需要多少内存
2. 分配所需的内存
3. 使用指针访问获得的内存
4. 使用完后及时释放内存
  - 不释放会造成内存泄漏！
  - 释放不及时会造成内存占用！

动态内存管理应用

测一测

应用动态内存管理技术，采用指针数组，解决多行文本输入问题

读取多行文本存入二维数组

#include <iostream>
const int MAX_LINE_LENGTH = 10;
int main() {
  int numLines;
  std::cin >> numLines; // 读取行数
  char *lines[numLines];
  // ========== begin ===========

  // =========== end ============
  delete[] lines;
  return 0;
}

总结

本节内容

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 20px
---
mindmap
数组与指针进阶
  多维数组
    定义与初始化
    逻辑结构    
    内存布局
    数组的数组
    索引元素
    多维数组遍历
    多维数组参数
  多重指针
    指向指针的指针
    指针数组
    与指针数组的互换性
  动态内存管理
    new与delete运算符
    数组版本
    四步法

学习目标

理解多维数组与多重指针的内存布局
应用多维数组与多重指针表示矩阵等二维数据
掌握动态内存分配与回收的基本方法

课后作业

实训（截止时间2025.04.07）
- C&C++数组实训
- 综合练习—C&C++数组
- 综合练习—C&C++指针
复习（准备第二次单元测试）
- 数组、指针、字符串

计算机程序设计