如何将二维数组元素的指针传递给函数？（递归矩阵乘法实现）

云上老周

2026-7-12

递归矩阵乘法实现中的指针传递问题

我正在阅读Cormen所著的《算法导论》，在实现4.2章Strassen算法中的Square-Matrix-Multiply-Recursive递归矩阵乘法时遇到了问题：

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A, B)
1 n = A.rows
2 let C be a new n × n matrix
3 if n == 1
4 c₁₁ = a₁₁ ⋅ b₁₁
5 else partition A, B, and C as in equations (4.9)
6 C₁₁ = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₁₁, B₁₁) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₁₂, B₂₁)
7 C₁₂ = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₁₁, B₁₂) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₁₂, B₂₂)
8 C₂₁ = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₂₁, B₁₁) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₂₂, B₂₁)
9 C₂₂ = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₂₁, B₁₂) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A₂₂, B₂₂)
10 return C

我将算法实现为如下函数：

int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N);

但在递归调用该函数时，我需要传递矩阵元素的指针，却不知道该如何操作。以下是我的测试代码：

#include <stdio.h>
#include <stdlib.h>

#define SIZE_STRING_A 2
#define SIZE_STRING_B 2
#define SIZE_COLUMN_A 2
#define SIZE_COLUMN_B 2

int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N);

int main (void)
{
    int ** arr_a;
    arr_a = (int**) calloc (SIZE_STRING_A, sizeof (int*));
    for (int i = 0; i < SIZE_STRING_A; i++)
        arr_a [i] = (int*) calloc (SIZE_COLUMN_A, sizeof (int));
    for (int i = 0; i < SIZE_STRING_A; i++)
        for (int j = 0; j < SIZE_COLUMN_A; j++)
            arr_a [i] [j] = i + j;
    for (int i = 0; i < SIZE_STRING_A; i++)
    {
        for (int j = 0; j < SIZE_COLUMN_B; j++)
            printf ("%d ", arr_a [i] [j]);
        printf ("\n");
    }
    
    int ** arr_b;
    arr_b = (int**) calloc (SIZE_STRING_B, sizeof (int*));
    for (int i = 0; i < SIZE_STRING_B; i++)
        arr_b [i] = (int*) calloc (SIZE_COLUMN_B, sizeof (int));
    for (int i = 0; i < SIZE_STRING_B; i++)
        for (int j = 0; j < SIZE_COLUMN_B; j++)
            arr_b [i] [j] = i + j;
    for (int i = 0; i < SIZE_STRING_A; i++)
    {
        for (int j = 0; j < SIZE_COLUMN_B; j++)
            printf ("%d ", arr_b [i] [j]);
        printf ("\n");
    }
    
    int ** arr_c;
    arr_c = (int**) calloc (SIZE_STRING_A, sizeof (int*));
    for (int i = 0; i < SIZE_STRING_B; i++)
        arr_c [i] = (int*) calloc (SIZE_COLUMN_B, sizeof (int));

    square_matrix_multiply_recursive (arr_a, arr_b, arr_c, 2);
    
    for (int i = 0; i < SIZE_STRING_A; i++)
    {
        for (int j = 0; j < SIZE_COLUMN_B; j++)
            printf ("%d ", arr_c [i] [j]);
        printf ("\n");
    }

    return 0;
}


int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N)
{
    if (N == 1)
    {
        (**arr_c) = (**arr_b) * (**arr_a);
        return arr_c;
    }
    else 
    {
        arr_c [0] [0] = (**square_matrix_multiply_recursive (/*arr_a [0] [0]*/, /*arr_b [0] [0]*/, /*arr_c [0] [0]*/, N / 2)) + (**square_matrix_multiply_recursive (/*arr_a [0] [1]*/, /*arr_b [1] [0]*/, /*arr_c [0] [0]*/, N / 2));
        
    }
    return arr_c;
}

代码存在诸多问题（这是测试版本），但最致命的是无法正确传递矩阵元素的指针。

解决方法

核心问题在于：当前用二级指针表示的矩阵，无法直接传递子矩阵的起始地址给递归函数——因为二级指针的每一行是独立分配的内存，子矩阵的行并不是连续的指针数组。

下面提供基于临时指针数组的修改方案，直接解决指针传递问题，同时修正原代码中的逻辑错误：

#include <stdio.h>
#include <stdlib.h>

#define SIZE 2

// 创建子矩阵的指针数组，指向原矩阵的对应区域
int** create_submatrix(int** original, int start_row, int start_col, int n) {
    int** sub = (int**)calloc(n, sizeof(int*));
    for (int i = 0; i < n; i++) {
        sub[i] = &original[start_row + i][start_col];
    }
    return sub;
}

// 释放子矩阵的指针数组（仅释放指针数组本身，不影响原矩阵）
void free_submatrix(int** sub) {
    free(sub);
}

int** square_matrix_multiply_recursive(int** arr_a, int** arr_b, int** arr_c, int N) {
    if (N == 1) {
        arr_c[0][0] = arr_a[0][0] * arr_b[0][0];
        return arr_c;
    } else {
        int half = N / 2;
        
        // 生成各个子矩阵的指针数组
        int** A11 = create_submatrix(arr_a, 0, 0, half);
        int** A12 = create_submatrix(arr_a, 0, half, half);
        int** A21 = create_submatrix(arr_a, half, 0, half);
        int** A22 = create_submatrix(arr_a, half, half, half);
        
        int** B11 = create_submatrix(arr_b, 0, 0, half);
        int** B12 = create_submatrix(arr_b, 0, half, half);
        int** B21 = create_submatrix(arr_b, half, 0, half);
        int** B22 = create_submatrix(arr_b, half, half, half);
        
        int** C11 = create_submatrix(arr_c, 0, 0, half);
        int** C12 = create_submatrix(arr_c, 0, half, half);
        int** C21 = create_submatrix(arr_c, half, 0, half);
        int** C22 = create_submatrix(arr_c, half, half, half);
        
        // 分配临时矩阵存储乘法结果
        int** temp1 = (int**)calloc(half, sizeof(int*));
        int** temp2 = (int**)calloc(half, sizeof(int*));
        for (int i = 0; i < half; i++) {
            temp1[i] = (int*)calloc(half, sizeof(int));
            temp2[i] = (int*)calloc(half, sizeof(int));
        }
        
        // 计算C11 = A11*B11 + A12*B21
        square_matrix_multiply_recursive(A11, B11, temp1, half);
        square_matrix_multiply_recursive(A12, B21, temp2, half);
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                C11[i][j] = temp1[i][j] + temp2[i][j];
            }
        }
        
        // 计算C12 = A11*B12 + A12*B22
        square_matrix_multiply_recursive(A11, B12, temp1, half);
        square_matrix_multiply_recursive(A12, B22, temp2, half);
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                C12[i][j] = temp1[i][j] + temp2[i][j];
            }
        }
        
        // 计算C21 = A21*B11 + A22*B21
        square_matrix_multiply_recursive(A21, B11, temp1, half);
        square_matrix_multiply_recursive(A22, B21, temp2, half);
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                C21[i][j] = temp1[i][j] + temp2[i][j];
            }
        }
        
        // 计算C22 = A21*B12 + A22*B22
        square_matrix_multiply_recursive(A21, B12, temp1, half);
        square_matrix_multiply_recursive(A22, B22, temp2, half);
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                C22[i][j] = temp1[i][j] + temp2[i][j];
            }
        }
        
        // 释放临时矩阵
        for (int i = 0; i < half; i++) {
            free(temp1[i]);
            free(temp2[i]);
        }
        free(temp1);
        free(temp2);
        
        // 释放子矩阵指针数组
        free_submatrix(A11);
        free_submatrix(A12);
        free_submatrix(A21);
        free_submatrix(A22);
        
        free_submatrix(B11);
        free_submatrix(B12);
        free_submatrix(B21);
        free_submatrix(B22);
        
        free_submatrix(C11);
        free_submatrix(C12);
        free_submatrix(C21);
        free_submatrix(C22);
        
        return arr_c;
    }
}

int main(void) {
    int** arr_a = (int**)calloc(SIZE, sizeof(int*));
    for (int i = 0; i < SIZE; i++) {
        arr_a[i] = (int*)calloc(SIZE, sizeof(int));
        for (int j = 0; j < SIZE; j++) {
            arr_a[i][j] = i + j;
        }
    }
    
    int** arr_b = (int**)calloc(SIZE, sizeof(int*));
    for (int i = 0; i < SIZE; i++) {
        arr_b[i] = (int*)calloc(SIZE, sizeof(int));
        for (int j = 0; j < SIZE; j++) {
            arr_b[i][j] = i + j;
        }
    }
    
    int** arr_c = (int**)calloc(SIZE, sizeof(int*));
    for (int i = 0; i < SIZE; i++) {
        arr_c[i] = (int*)calloc(SIZE, sizeof(int));
    }
    
    printf("矩阵A:\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", arr_a[i][j]);
        }
        printf("\n");
    }
    
    printf("\n矩阵B:\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", arr_b[i][j]);
        }
        printf("\n");
    }
    
    square_matrix_multiply_recursive(arr_a, arr_b, arr_c, SIZE);
    
    printf("\n结果矩阵C:\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", arr_c[i][j]);
        }
        printf("\n");
    }
    
    // 释放原矩阵内存
    for (int i = 0; i < SIZE; i++) {
        free(arr_a[i]);
        free(arr_b[i]);
        free(arr_c[i]);
    }
    free(arr_a);
    free(arr_b);
    free(arr_c);
    
    return 0;
}

关键修改说明：

子矩阵指针生成：通过create_submatrix函数生成指向原矩阵子区域的二级指针数组，让递归函数可以直接操作子矩阵。
矩阵加法修正：原代码试图直接对递归返回的矩阵取单个元素相加，这是错误的。这里通过临时矩阵存储乘法结果，再手动完成矩阵加法。
内存管理：添加了子矩阵指针和临时矩阵的释放逻辑，避免内存泄漏。
代码简化：将冗余的宏定义合并为SIZE，提升代码可读性。

内容的提问来源于stack exchange，提问作者Lexa

如何将二维数组元素的指针传递给函数？（递归矩阵乘法实现）

关键修改说明： #

关键修改说明：