C语言 如何将指向二维数组元素的指针传递给函数?

h6my8fg2  于 2023-10-16  发布在  其他
关注(0)|答案(1)|浏览(108)

我已经开始阅读Cormen的Introduction to Algorithms,并遇到了斯特拉森算法的问题(第4.2章):
S-M x-M-R s(,)𝐴
1 𝑛 ==𝐴。𝑟𝑜𝑤𝑠
2 设𝐶是一个新的𝑛×𝑛矩阵
3 如果𝑛== 1
4 𝑐 11 =𝑎 11𝑏 11
5 elsepartition𝐴,𝐵和𝐶如等式(4.9)所示
6 𝐶 11 = S-M x-M-R s(𝐴11,𝐵11)
+ S-M x-M-R s(12, 21)𝐴
7 𝐶 12 = S-M x-M-R s(𝐴11,𝐵12)
+ S-M x-M-R s(12, 22)𝐴
8 𝐶 21 = S-M x-M-R s(𝐴21,𝐵11)
+ S-M x-M-R s(22, 21)𝐴
9 𝐶 22 = S-M x-M-R s(𝐴21,𝐵12)
+ S-M x-M-R s(22, 22)𝐴
10 返回𝐶
我决定像这样实现算法函数:

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;
}

代码中有许多问题(这是测试版本),但致命的一个是传递一个指向矩阵元素的指针。

6jjcrrmo

6jjcrrmo1#

由于您的代码无法按原样编译,并且它只尝试分配给arr_c[0][0],因此还有很多工作要做。至于这个问题,“如何传递一个指针到一个矩阵元素”,答案是你不应该。你的矩阵元素是整数,它们不应该是指针。
事实上,在没有显式指针的情况下实现它可能更易读,因为您可以始终使用数组表示法。我还建议:

  • 避免代码重复(如打印逻辑、矩阵分配逻辑等)
  • 创建更多的功能(使用更小的主体),每个功能处理特定的方面

有很多方法可以做到这一点,这里只有一个:

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

typedef struct {
    size_t row;
    size_t col;
} pos;

void print_square_matrix(size_t n, int matrix[][n]) {
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

// Add a number of rows and columns to a position and return it
pos offset(pos anchor, size_t add_row, size_t add_col) {
    anchor.row += add_row;
    anchor.col += add_col;
    return anchor;
}

void square_matrix_multiply_recursive(size_t n, size_t size, 
                                      int a[][n], pos apos, 
                                      int b[][n], pos bpos, 
                                      int c[][n], pos cpos);

void multiply_and_add(size_t n, size_t size, 
                      int a[][n], pos apos1, pos apos2,
                      int b[][n], pos bpos1, pos bpos2, 
                      int c[][n], pos cpos) {
    square_matrix_multiply_recursive(n, size, a, apos1, b, bpos1, c, cpos);
    square_matrix_multiply_recursive(n, size, a, apos2, b, bpos2, c, cpos);
}

void square_matrix_multiply_recursive(size_t n, size_t size, 
                                      int a[][n], pos apos, 
                                      int b[][n], pos bpos, 
                                      int c[][n], pos cpos) {
    if (size == 1) {
        // Use += to accumulate (two) results
        c[cpos.row][cpos.col] += a[apos.row][apos.col] * b[bpos.row][bpos.col];
    } else {
        size /= 2;
        for (size_t row = 0; row <= size; row += size) {
            for (size_t col = 0; col <= size; col += size) {
                multiply_and_add(n, size, 
                    a, offset(apos, row, 0), offset(apos, row, size), 
                    b, offset(bpos, 0, col), offset(bpos, size, col),
                    c, offset(cpos, row, col));
            }
        }
    }
}

void square_matrix_multiply(size_t n, int a[][n], int b[][n], int c[][n]) {
    square_matrix_multiply_recursive(n, n, a, (pos) {0}, b, (pos) {0}, c, (pos) {0});
}

// N must be a power of 2
#define N 4

int main (void)
{
    // Example input:
    int arr_a[N][N] = {{ 0,  2, -1,  3}, 
                       { 2,  1,  0, -4},
                       {-1, -3,  2,  1},
                       { 3,  1, -2,  2}};
    int arr_b[N][N] = {{ 5,  2, -1,  2}, 
                       {-3, -3,  2,  0},
                       { 1,  1, -3,  0},
                       { 2, -2, -4,  3}};
    // Calculate the product
    int arr_c[N][N] = {0}; // Initialize with all zeroes (important)
    square_matrix_multiply(N, arr_a, arr_b, arr_c);
    // Output results
    print_square_matrix(N, arr_a);
    print_square_matrix(N, arr_b);
    print_square_matrix(N, arr_c);
    return 0;
}

此示例运行具有以下输出:

0 2 -1 3 
2 1 0 -4 
-1 -3 2 1 
3 1 -2 2 

5 2 -1 2 
-3 -3 2 0 
1 1 -3 0 
2 -2 -4 3 

-1 -13 -5 9 
-1 9 16 -8 
8 7 -15 1 
14 -3 -3 12

最后,请注意,这并没有完全实现斯特拉森的算法:分而治之的方法是相同的,但是该算法应用不同的矩阵运算集合,以便保存它们的数量。参见𝑀维基百科关于斯特拉森算法的文章中矩阵的用法。

相关问题