#c

C++二维数组

多维数据的组织与处理

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 二维数组的基本概念

1.1 什么是二维数组？

  • 二维数组是由多个一维数组组成的数组
  • 可以看作是具有行和列的表格结构
  • 每个元素由两个下标确定：行下标和列下标
  • 适合表示矩阵、网格、表格等二维数据
// 一个3行4列的二维数组示例
int grid[3][4] = {
    {1, 2, 3, 4},    // 第0行
    {5, 6, 7, 8},    // 第1行
    {9, 10, 11, 12}  // 第2行
};

// 二维数组在内存中的示意图
// [1][2][3][4][5][6][7][8][9][10][11][12]
//  ↑
// 数组的第一个元素(0行0列)

1.2 二维数组的内存布局

行主序存储：

  • C++中二维数组采用行主序存储
  • 同一行的元素在内存中连续存储
  • 整个数组在内存中是连续的
  • 可以看作是"数组的数组"

内存布局示例：

int arr[3][4];

// 内存布局:
// arr[0][0] arr[0][1] arr[0][2] arr[0][3]
// arr[1][0] arr[1][1] arr[1][2] arr[1][3]
// arr[2][0] arr[2][1] arr[2][2] arr[2][3]

内存计算：

  • 对于int arr[3][4]
  • 总元素数：3 × 4 = 12个元素
  • 总内存大小：12 × sizeof(int)字节
  • 每行大小：4 × sizeof(int)字节

访问元素：

  • 元素arr[i][j]的内存位置：
    • 基地址 + (i × 列数 + j) × 元素大小
  • 例如：arr[1][2]的位置：
    • 基地址 + (1 × 4 + 2) × sizeof(int)
    • 基地址 + 6 × sizeof(int)

1.3 二维数组的应用场景

二维数组适合表示：

  1. 矩阵：数学中的矩阵运算
  2. 游戏棋盘：如井字棋、围棋、象棋等
  3. 像素图像：每个元素表示一个像素
    int image[height][width]; // 灰度图像
  4. 地图数据：表示地形、障碍物等
  5. 表格数据：如学生成绩表
    double grades[students][subjects]; // 成绩表
  6. 动态规划：存储中间计算结果

2. 二维数组的声明和初始化

2.1 二维数组的声明

基本语法：

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

示例：

int matrix[3][4];// 声明一个3行4列的整数数组
char grid[5][5];// 声明一个5行5列的字符数组
double values[2][3];// 声明一个2行3列的浮点数数组
// 使用常量定义大小
const int ROWS = 3;
const int COLS = 4;
int table[ROWS][COLS];
// 错误的声明方式
int n = 5;
int wrong[n][n];  // 错误：数组大小必须是常量

2.2 二维数组的初始化

完整初始化：

// 方法1：使用嵌套的花括号
int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// 方法2：省略内部花括号
int matrix[3][4] = {
    1, 2, 3, 4,
    5, 6, 7, 8,
    9, 10, 11, 12
};

// 方法3：全部初始化为0
int matrix[3][4] = {0};

部分初始化：

// 只初始化部分元素
int matrix[3][4] = {
    {1, 2},
    {5, 6, 7},
    {9}
};
// 未初始化的元素自动设为0
// matrix = {
//    {1, 2, 0, 0},
//    {5, 6, 7, 0},
//    {9, 0, 0, 0}
// }

// 只初始化第一行
int matrix[3][4] = {{1, 2, 3, 4}};
// 其余元素自动设为0

2.3 特殊的初始化方式

省略行数：

// 可以省略行数，编译器会根据初始化列表计算
int matrix[][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};// 编译器确定行数为3

// 但不能省略列数
int wrong[][] = {{1,2}, {3,4}};  // 错误

特定元素初始化：

// 初始化后手动设置特定元素
int matrix[3][3] = {0};  // 全部初始化为0
matrix[1][1] = 5;        // 设置中心元素为5

// 使用循环初始化
int table[5][5];
for(int i = 0; i < 5; i++) {
    for(int j = 0; j < 5; j++) {
        table[i][j] = i * j;  // 乘法表
    }
}

3. 访问和修改元素

3.1 访问二维数组元素

  • 使用两个下标访问二维数组元素：数组名[行下标][列下标]
  • 下标从0开始计数
  • 行下标范围：0到行数-1
  • 列下标范围：0到列数-1
int matrix[3][4] = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};
// 访问元素
cout << matrix[0][0] << endl;  // 输出：1（第一行第一列）
cout << matrix[1][2] << endl;  // 输出：7（第二行第三列）
cout << matrix[2][3] << endl;  // 输出：12（第三行第四列）
// 使用变量作为下标
int row = 1, col = 2;
cout << matrix[row][col] << endl;  // 输出：7

// 注意：访问越界会导致未定义行为
cout << matrix[3][0] << endl;  // 错误：行下标越界
cout << matrix[0][4] << endl;  // 错误：列下标越界

3.2 修改二维数组元素

直接赋值：

int matrix[3][3] = {0};  // 全部初始化为0

// 修改单个元素
matrix[0][0] = 1;
matrix[1][1] = 5;
matrix[2][2] = 9;

// 使用变量
int row = 0, col = 2, value = 3;
matrix[row][col] = value;

// 使用表达式
matrix[1][0] = matrix[0][0] * 2;

常见错误：

int matrix[3][3];

// 越界访问
matrix[3][3] = 1;  // 错误：行列都越界

// 行列顺序错误
// 假设想访问第2行第1列
matrix[1][2];  // 错误：这是第1行第2列

// 不能整行赋值
matrix[0] = {1, 2, 3};  // 错误

// 不能整个数组赋值
int another[3][3];
matrix = another;  // 错误

3.3 二维数组的边界检查

C++不会自动检查数组边界，需要程序员自己确保下标合法。

const int ROWS = 3;
const int COLS = 4;
int matrix[ROWS][COLS];

// 安全的访问函数
bool getElement(int row, int col, int& value) {
    if(row >= 0 && row < ROWS && col >= 0 && col < COLS) {
        value = matrix[row][col];
        return true;
    }
    return false;
}

4. 二维数组的遍历

4.1 按行优先遍历

按行优先是最常见的遍历方式，外层循环遍历行，内层循环遍历列

const int ROWS = 3;
const int COLS = 4;
int matrix[ROWS][COLS] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};
// 按行优先遍历（先遍历第0行，再遍历第1行，...）
for(int i = 0; i < ROWS; i++) {
    for(int j = 0; j < COLS; j++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;  // 每行结束后换行
}
// 输出:
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12

4.2 按列优先遍历

按列优先遍历方式是外层循环遍历列，内层循环遍历行

// 按列优先遍历
// (先遍历第0列，再遍历第1列，...)
for(int j = 0; j < COLS; j++) {
    for(int i = 0; i < ROWS; i++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;  // 每列结束后换行
}
// 输出:
// 1 5 9
// 2 6 10
// 3 7 11
// 4 8 12

其他遍历方式：

  • 对角线遍历
  • 螺旋遍历
  • 之字形遍历
// 主对角线遍历（方阵）
for(int i = 0; i < N; i++) {
    cout << matrix[i][i] << " ";
}
// 副对角线遍历（方阵）
for(int i = 0; i < N; i++) {
    cout << matrix[i][N-1-i] << " ";
}

4.3 特殊遍历模式

螺旋遍历：从外向内螺旋遍历二维数组

void spiralTraversal(int matrix[ROWS][COLS]) {
    int top = 0, bottom = ROWS - 1;
    int left = 0, right = COLS - 1;
    
    while(top <= bottom && left <= right) {
        // 遍历上边
        for(int j = left; j <= right; j++) {
            cout << matrix[top][j] << " ";
        }
        top++;
        
        // 遍历右边
        for(int i = top; i <= bottom; i++) {
            cout << matrix[i][right] << " ";
        }
        right--;
        
        // 遍历下边
        if(top <= bottom) {
            for(int j = right; j >= left; j--) {
                cout << matrix[bottom][j] << " ";
            }
            bottom--;
        }
        
        // 遍历左边
        if(left <= right) {
            for(int i = bottom; i >= top; i--) {
                cout << matrix[i][left] << " ";
            }
            left++;
        }
    }
}

5. 常见操作

5.1 矩阵操作

矩阵转置：行列互换

for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
        result[j][i] = original[i][j];
    }
}

矩阵加法：对应元素相加

for(int i = 0; i < ROWS; i++) {
    for(int j = 0; j < COLS; j++) {
        result[i][j] = A[i][j] + B[i][j];
    }
}

矩阵乘法：

for(int i = 0; i < N; i++) {
    for(int j = 0; j < P; j++) {
        result[i][j] = 0;
        for(int k = 0; k < M; k++) {
            result[i][j] += A[i][k] * B[k][j];
        }
    }
}

5.2 查找操作

查找特定值：

bool findElement(int matrix[ROWS][COLS], int target, int& row, int& col) {
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(matrix[i][j] == target) {
                row = i;
                col = j;
                return true;
            }
        }
    }
    return false;
}

查找最大值：

int findMax(int matrix[ROWS][COLS], int& row, int& col) {
    int maxVal = matrix[0][0];
    row = 0;
    col = 0;
    
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(matrix[i][j] > maxVal) {
                maxVal = matrix[i][j];
                row = i;
                col = j;
            }
        }
    }
    return maxVal;
}

5.2 查找操作(续)

查找最小值：

int findMin(int matrix[ROWS][COLS], int& row, int& col) {
    int minVal = matrix[0][0];
    row = 0;
    col = 0;
    
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(matrix[i][j] < minVal) {
                minVal = matrix[i][j];
                row = i;
                col = j;
            }
        }
    }
    return minVal;
}

在有序矩阵中查找：

// 假设矩阵每行和每列都是升序排列的
bool searchSortedMatrix(int matrix[ROWS][COLS], int target) {
    int i = 0, j = COLS - 1;
    while(i < ROWS && j >= 0) {
        if(matrix[i][j] == target) {
            return true;
        } else if(matrix[i][j] > target) {
            j--;
        } else {
            i++;
        }
    }
    return false;
}

5.3 统计和修改操作

计算行和列的和：

// 计算每行的和
void rowSums(int matrix[ROWS][COLS], int result[ROWS]) {
    for(int i = 0; i < ROWS; i++) {
        result[i] = 0;
        for(int j = 0; j < COLS; j++) {
            result[i] += matrix[i][j];
        }
    }
}

// 计算每列的和
void colSums(int matrix[ROWS][COLS], int result[COLS]) {
    for(int j = 0; j < COLS; j++) {
        result[j] = 0;
        for(int i = 0; i < ROWS; i++) {
            result[j] += matrix[i][j];
        }
    }
}

旋转矩阵（顺时针旋转90度）：

// 适用于方阵(N×N)
void rotateMatrix(int matrix[N][N]) {
    // 先转置
    for(int i = 0; i < N; i++) {
        for(int j = i; j < N; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    
    // 然后每行反转
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N/2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][N-1-j];
            matrix[i][N-1-j] = temp;
        }
    }
}

6. 应用实例

6.1 图像处理

题目说明：

  • 目标：实现简单的图像处理操作，包括反转和模糊
  • 输入：一个表示灰度图像的二维数组（0-255）
  • 输出：处理后的图像
const int HEIGHT = 8;
const int WIDTH = 8;

// 显示图像
void displayImage(int image[HEIGHT][WIDTH]) {
    for(int i = 0; i < HEIGHT; i++) {
        for(int j = 0; j < WIDTH; j++) {
            // 使用不同字符表示不同灰度级别
            if(image[i][j] > 200) cout << "@ ";
            else if(image[i][j] > 150) cout << "# ";
            else if(image[i][j] > 100) cout << "o ";
            else if(image[i][j] > 50) cout << ". ";
            else cout << "  ";
        }
        cout << endl;
    }
}

// 图像反转
void invertImage(int image[HEIGHT][WIDTH], int result[HEIGHT][WIDTH]) {
    for(int i = 0; i < HEIGHT; i++) {
        for(int j = 0; j < WIDTH; j++) {
            result[i][j] = 255 - image[i][j];
        }
    }
}

// 图像模糊
void blurImage(int image[HEIGHT][WIDTH], int result[HEIGHT][WIDTH]) {
    for(int i = 1; i < HEIGHT-1; i++) {
        for(int j = 1; j < WIDTH-1; j++) {
            // 3x3邻域平均
            int sum = 0;
            for(int di = -1; di <= 1; di++) {
                for(int dj = -1; dj <= 1; dj++) {
                    sum += image[i+di][j+dj];
                }
            }
            result[i][j] = sum / 9;
        }
    }
    
    // 处理边界
    for(int i = 0; i < HEIGHT; i++) {
        result[i][0] = image[i][0];
        result[i][WIDTH-1] = image[i][WIDTH-1];
    }
    for(int j = 0; j < WIDTH; j++) {
        result[0][j] = image[0][j];
        result[HEIGHT-1][j] = image[HEIGHT-1][j];
    }
}

int main() {
    // 创建一个简单的图像
    int image[HEIGHT][WIDTH] = {
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 100, 100, 100, 100, 100, 100, 0},
        {0, 100, 150, 150, 150, 150, 100, 0},
        {0, 100, 150, 200, 200, 150, 100, 0},
        {0, 100, 150, 200, 200, 150, 100, 0},
        {0, 100, 150, 150, 150, 150, 100, 0},
        {0, 100, 100, 100, 100, 100, 100, 0},
        {0, 0, 0, 0, 0, 0, 0, 0}
    };
    
    int result[HEIGHT][WIDTH];
    
    cout << "原始图像：" << endl;
    displayImage(image);
    
    invertImage(image, result);
    cout << "\n反转后的图像：" << endl;
    displayImage(result);
    
    blurImage(image, result);
    cout << "\n模糊处理后的图像：" << endl;
    displayImage(result);
    
    return 0;
}

6.2 游戏棋盘

题目说明：

  • 目标：实现一个简单的井字棋游戏
  • 输入：玩家的落子位置
  • 输出：当前棋盘状态和游戏结果
const int BOARD_SIZE = 3;

// 显示棋盘
void displayBoard(char board[BOARD_SIZE][BOARD_SIZE]) {
    cout << "  0 1 2" << endl;
    for(int i = 0; i < BOARD_SIZE; i++) {
        cout << i << " ";
        for(int j = 0; j < BOARD_SIZE; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

// 检查是否获胜
bool checkWin(char board[BOARD_SIZE][BOARD_SIZE], char player) {
    // 检查行
    for(int i = 0; i < BOARD_SIZE; i++) {
        if(board[i][0] == player && board[i][1] == player && board[i][2] == player) {
            return true;
        }
    }
    
    // 检查列
    for(int j = 0; j < BOARD_SIZE; j++) {
        if(board[0][j] == player && board[1][j] == player && board[2][j] == player) {
            return true;
        }
    }
    
    // 检查对角线
    if(board[0][0] == player && board[1][1] == player && board[2][2] == player) {
        return true;
    }
    if(board[0][2] == player && board[1][1] == player && board[2][0] == player) {
        return true;
    }
    
    return false;
}

// 检查棋盘是否已满
bool isBoardFull(char board[BOARD_SIZE][BOARD_SIZE]) {
    for(int i = 0; i < BOARD_SIZE; i++) {
        for(int j = 0; j < BOARD_SIZE; j++) {
            if(board[i][j] == ' ') {
                return false;
            }
        }
    }
    return true;
}

int main() {
    char board[BOARD_SIZE][BOARD_SIZE];
    
    // 初始化棋盘
    for(int i = 0; i < BOARD_SIZE; i++) {
        for(int j = 0; j < BOARD_SIZE; j++) {
            board[i][j] = ' ';
        }
    }
    
    char currentPlayer = 'X';
    bool gameOver = false;
    
    while(!gameOver) {
        // 显示当前棋盘
        cout << "\n当前棋盘：" << endl;
        displayBoard(board);
        
        // 获取玩家输入
        int row, col;
        cout << "玩家 " << currentPlayer << " 请输入落子位置 (行 列): ";
        cin >> row >> col;
        
        // 检查输入是否有效
        if(row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE || board[row][col] != ' ') {
            cout << "无效的位置，请重试！" << endl;
            continue;
        }
        
        // 落子
        board[row][col] = currentPlayer;
        
        // 检查是否获胜
        if(checkWin(board, currentPlayer)) {
            cout << "\n最终棋盘：" << endl;
            displayBoard(board);
            cout << "玩家 " << currentPlayer << " 获胜！" << endl;
            gameOver = true;
        }
        // 检查是否平局
        else if(isBoardFull(board)) {
            cout << "\n最终棋盘：" << endl;
            displayBoard(board);
            cout << "游戏结束，平局！" << endl;
            gameOver = true;
        }
        // 切换玩家
        else {
            currentPlayer = (currentPlayer == 'X') ? 'O' : 'X';
        }
    }
    
    return 0;
}

6.3 迷宫问题

题目说明：

  • 目标：在迷宫中找到从起点到终点的路径
  • 输入：表示迷宫的二维数组，0表示通道，1表示墙
  • 输出：找到的路径（如果存在）
const int ROWS = 5;
const int COLS = 5;

// 显示迷宫
void displayMaze(int maze[ROWS][COLS]) {
    for(int i = 0; i < ROWS; i++) {
        for(int j = 0; j < COLS; j++) {
            if(maze[i][j] == 0) cout << "  ";      // 通道
            else if(maze[i][j] == 1) cout << "██";  // 墙
            else if(maze[i][j] == 2) cout << "* ";  // 路径
        }
        cout << endl;
    }
}

// 检查位置是否有效
bool isValid(int maze[ROWS][COLS], int row, int col) {
    return (row >= 0 && row < ROWS && col >= 0 && col < COLS && maze[row][col] == 0);
}

// 使用深度优先搜索寻找路径
bool findPath(int maze[ROWS][COLS], int row, int col, int endRow, int endCol) {
    // 到达终点
    if(row == endRow && col == endCol) {
        maze[row][col] = 2;  // 标记为路径
        return true;
    }
    
    // 检查当前位置是否有效
    if(isValid(maze, row, col)) {
        // 标记为路径
        maze[row][col] = 2;
        
        // 向四个方向尝试
        // 向右
        if(findPath(maze, row, col+1, endRow, endCol)) {
            return true;
        }
        // 向下
        if(findPath(maze, row+1, col, endRow, endCol)) {
            return true;
        }
        // 向左
        if(findPath(maze, row, col-1, endRow, endCol)) {
            return true;
        }
        // 向上
        if(findPath(maze, row-1, col, endRow, endCol)) {
            return true;
        }
        
        // 如果所有方向都不行，回溯
        maze[row][col] = 0;
        return false;
    }
    
    return false;
}

int main() {
    // 创建迷宫 (0:通道, 1:墙)
    int maze[ROWS][COLS] = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };
    
    int startRow = 0, startCol = 0;
    int endRow = 4, endCol = 4;
    
    cout << "原始迷宫：" << endl;
    displayMaze(maze);
    
    if(findPath(maze, startRow, startCol, endRow, endCol)) {
        cout << "\n找到路径：" << endl;
        displayMaze(maze);
    } else {
        cout << "\n没有找到路径！" << endl;
    }
    
    return 0;
}

8. 练习题

8.1 基础练习

  1. 创建一个3×3的整数二维数组，初始化为九九乘法表
  2. 编写程序，计算二维数组中所有元素的和与平均值
  3. 编写函数，交换二维数组的两行
  4. 编写函数，判断一个方阵是否为对称矩阵

8.2 中级练习

  1. 实现矩阵的转置操作
  2. 实现两个矩阵的加法和乘法
  3. 在二维数组中查找鞍点（行最大列最小的元素）
  4. 实现顺时针旋转矩阵90度的函数

8.3 实际题目练习

初级题目：

  1. HDU 2035 - 人见人爱A^B (★★☆☆☆)

    • 使用二维数组存储中间结果
    • 练习二维数组的基本操作

  2. 洛谷 P1789 - 插火把 (★★☆☆☆)

    • 使用二维数组模拟网格
    • 处理二维坐标和区域

  3. CSP-J 2021 - 网络连接 (★★☆☆☆)

    • 使用二维数组表示连接关系
    • 练习二维数组的遍历和查询

中级题目：

  1. USACO 2019 Bronze - Shell Game (★★★☆☆)

    • 使用二维数组记录操作和结果
    • 模拟游戏过程

  2. POJ 2386 - Lake Counting (★★★☆☆)

    • 使用二维数组表示地图
    • 实现深度优先搜索

  3. CSES - Grid Paths (★★★☆☆)

    • 使用二维数组进行动态规划
    • 计算从左上角到右下角的路径数

8.4 综合应用题

1. NOIP 2004 普及组 - 方格取数 (★★★★☆)

  • 使用二维数组表示方格
  • 实现动态规划算法
  • 练习二维数组的高级应用

2. CSP-J 2022 - 解密 (★★★☆☆)

  • 使用二维数组处理密码
  • 实现矩阵变换
  • 练习二维数组的操作

3. USACO 2017 Bronze - Why Did the Cow Cross the Road III (★★★☆☆)

  • 使用二维数组表示农场地图
  • 计算最短路径
  • 练习二维数组的遍历和搜索

4. 洛谷 P1605 - 迷宫 (★★★☆☆)

  • 使用二维数组表示迷宫
  • 实现深度优先搜索
  • 找出从起点到终点的路径

8.5 扩展思考题

  1. 如何高效地在二维数组中进行区域求和？
  2. 如何处理稀疏矩阵（大部分元素为0的矩阵）以节省内存？
  3. 二维数组与链表相比，各有什么优缺点？
  4. 如何实现一个不规则的二维数组（每行长度不同）？
  5. 在什么情况下应该使用二维数组而不是两个一维数组？

9. 总结

9.1 重要概念回顾

  • 二维数组定义：由多个一维数组组成的数组，具有行和列
  • 内存布局：C++中采用行主序存储，内存连续
  • 访问方式：使用两个下标array[row][col]访问元素
  • 常见操作：
    • 矩阵运算（转置、加法、乘法）
    • 查找操作（最大值、最小值、特定值）
    • 遍历方式（行优先、列优先、螺旋）
    • 特殊矩阵（单位矩阵、对称矩阵）
  • 作为函数参数：必须指定列数，行数可以省略

9.2 使用建议

  1. 安全性：

    • 始终检查数组边界
    • 使用常量定义数组大小
    • 初始化所有元素

  2. 可维护性：

    • 使用有意义的变量名
    • 添加适当的注释
    • 使用函数封装常用操作

  3. 效率：

    • 优先使用行优先遍历
    • 合理设计数组大小
    • 避免不必要的内存复制

  4. 进阶学习：

    • 学习动态二维数组（vector<vector<T>>）
    • 了解多维数组
    • 掌握常用的矩阵算法

#c

C++二维数组

#c

感谢学习！
如有疑问，请联系：
judal@xmaker.org
魅客科创中心

内容针对已学习一维数组的学生设计，使用简单易懂的语言和示例。 假设学生已经了解一维数组的基本操作。