如何在 C 中的结构数组中使用动态二维数组?

How to use dynamic 2d array inside a struct array in C?

我想做什么?

我正在做一个关于动态矩阵乘法的项目。我想从用户那里输入有多少矩阵,he/she 想要执行乘法,并基于此我想创建一个如下所示的结构:

typedef struct
{
    size_t rows, columns;
    int table[];
} Matrix;

然后,检查要相乘的矩阵的有效性 (using very simple maths)

然后创建一个 Matrix 类型的数组,并根据用户要相乘的矩阵数量为其分配内存。

+---------------------------------------------------------------------------------------------------+
|    +------------------------------+  +---------------------------------------------------------+  |
|    |   Matrix struct type array   |  |  ..... More arrays depending on the number of matrices. |  |
|    +------------------------------+  +---------------------------------------------------------+  |
+---------------------------------------------------------------------------------------------------+



Eg. 2 Matrices [2][2] & [2][1]

    +----------------> rows <-------------+      
    |                                     |              
    |  +------------> columns <-----------|--+
    |  |                                  |  |
    |  |  +------------------------+      |  |  +------------------+
{ { 2, 2, | { { 1, 2 }, { 2, 1 } } | }, { 2, 1, | { { 1 }, { 3 } } | } } 
          +------------------------+            +------------------+
                      |                                   |
                      |                                   |
                      |                                   |
                      v                                   v
                  | 1   2 |                             | 1 |
                  |       |                             |   | 
                  | 2   1 |                             | 3 |

创建结构类型数组的原因

对于这个问题的一些读者来说,有一件事可能看起来很奇怪,那就是,为什么我想要创建一个类型数组 struct Matrix,而不是创建 2 个不同类型的对象并在 "user_defined_matrix"->table 上执行乘法。那么,原因如下:

言归正传,分配内存后,我想让用户填充矩阵的每个槽位,然后对它们进行乘法运算,得到结果。


到目前为止我做了什么

注意:我知道你不能在结构中声明一个真正的 2d VLA,你必须首先声明一个 1d 数组,它后来变成一个损坏的版本二维数组,在使用它之前将其转换为二维数组,如此 .

所示

我制作了一个真正的二维数组来存储用户输入的行和列。

int dimensions[NUMBER_OF_MATRIX][2];

然后使用这些 dimensions,我计算了我必须分配多少内存。

int total_matrix_size = 0;
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
    total_matrix_size += (dimensions[i][0] * dimensions[i][1]);
}

然后使用total_matrix_size分配内存给struct Martix类型的数组。

Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));

之后,我要求用户填充矩阵,在填充矩阵之前,我借助下面代码中的宏将数组转换为二维数组。

注意:我将多次引用下面的代码块,为了简单起见,我们将其命名为输入区块.

#define get_array(arr) \
    _Generic((arr),    \
             Matrix    \
             : (int(*)[(arr).columns])(arr).table)

for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
        {
            matrix[i].rows = dimensions[i][0];
            matrix[i].columns = dimensions[i][1];

            for (uint x = 0; x < matrix[i].rows; x++)
            {
                for (uint y = 0; y < matrix[i].columns; y++)
                {
                    printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
                    scanf("%d", &get_array(matrix[i])[x][y]);
                    printf("%d\n", get_array(matrix[i])[x][y]); // print statement 1
                }
            }
        }

然后为了测试目的,我正在打印所有矩阵。

注意:我将多次引用下面的代码块,为了简单起见,我们将其命名为输出区块.

for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
        {
            printf("Matrix %d\n", i+1);
            for (uint x = 0; x < matrix[i].rows; x++)
            {
                for (uint y = 0; y < matrix[i].columns; y++)
                {

                    printf("%d ", get_array(matrix[i])[x][y]); // print statement 2
                }
                printf("\n");
            }
        }

那么,问题出在哪里?

如您所见,我在上面的 2 个代码块 inputoutput 块中编写了 2 个完全相同的打印语句.

printf("%d ", get_array(matrix[i])[x][y]);

但它们都产生了不同的输出。 输入块.

生成的输出
Enter the rows of matrix 1 : 2 2
Enter the rows of matrix 2 : 2 2
Enter values of matrix 1 a[1x1] : 1
1
Enter values of matrix 1 a[1x2] : 0
0
Enter values of matrix 1 a[2x1] : 1
1
Enter values of matrix 1 a[2x2] : 0
0
Enter values of matrix 2 a[1x1] : 2
2
Enter values of matrix 2 a[1x2] : 3
3
Enter values of matrix 2 a[2x1] : 2
2
Enter values of matrix 2 a[2x2] : 3
3

按预期打印所有内容。

输出块不一样

Matrix 1
2 2
2 3
Matrix 2
2 3
2 3

我对答案有何期待?

只有对 :

的深入解释

请保持这种格式


这是完整的代码

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

// TODO Preprocessors
#define get_array(arr) \
    _Generic((arr),    \
             Matrix    \
             : (int(*)[(arr).columns])(arr).table)

// TODO Custom types
typedef unsigned int uint;

// TODO Structs
typedef struct
{
    uint rows, columns;
    int table[];
} Matrix;

// TODO Function Declarations
void flushBuffer(void);

int main(void)
{
    int NUMBER_OF_MATRIX = 2;
    int dimensions[NUMBER_OF_MATRIX][2];

    for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
    {
        printf("Enter the rows of matrix %d : ", i + 1);
        scanf("%d %d", &dimensions[i][0], &dimensions[i][1]);
        flushBuffer();
    }

    if (dimensions[0][1] != dimensions[1][0])
    {
        printf("Matrix multiplication not possible.");
    }
    else
    {
        int total_matrix_size = 0;
        for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
        {
            total_matrix_size += (dimensions[i][0] * dimensions[i][1]);
        }

        Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));

        for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
        {
            matrix[i].rows = dimensions[i][0];
            matrix[i].columns = dimensions[i][1];

            for (uint x = 0; x < matrix[i].rows; x++)
            {
                for (uint y = 0; y < matrix[i].columns; y++)
                {
                    printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
                    scanf("%d", &get_array(matrix[i])[x][y]);
                    printf("%d\n", get_array(matrix[i])[x][y]);
                }
            }
        }

        for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
        {
            printf("Matrix divider\n");
            for (uint x = 0; x < matrix[i].rows; x++)
            {
                for (uint y = 0; y < matrix[i].columns; y++)
                {

                    printf("%d ", get_array(matrix[i])[x][y]);
                }
                printf("\n");
            }
        }
    }

    return 0;
}

// TODO Function Definitions
void flushBuffer(void)
{
    int c;
    while ((c = getchar()) != '\n' && c != EOF)
        ;
}

我将开门见山。我会在之后详细介绍您要求的特定主题。

解决方案

问题

简而言之,您对问题的理论方法在我看来是合理的。但是内存管理没有正确实现。

您想要做的是拥有 Matrix 结构的多个实例。这不是您当前设置的结果。具体来说:

Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));

当然,您在这里为 NUMBER_OF_MATRIX Matrix 个实例分配了足够的内存。但是你这样做是为了 Matrix 类型。给定 matrixpointer to Matrixsizeof *matrix(或 sizeof(Matrix))等于 sizeof(int[2]) (1),当你索引那个数组(即做指针运算)内存偏移增量就是那个大小。

让我们假设 sizeof(int) = 4NUMBER_OF_MATRIX = 2total_matrix_size = 8(2 2x2 矩阵)。如果 matrix 被赋予内存地址 0x0010&(matrix[1]) 将是 0x0018,而不是您期望的 0x0028(24 字节偏移量)。

有关 C 如何处理指针运算的更多参考,您可以参考 this SO answer, and this article,其中对主题有更详细的概述。

IMO 实现你想要的最干净的方法是动态分配 matrix[i].table 单独而不是 pre-allocating 你需要的所有内存一次。这有几个原因:

  1. 这对其他读者和您自己来说会更干净(发生此类问题的可能性较小)
  2. 随着您需要的总内存越来越大,OS 处理单个分配变得越来越困难,因为它试图找到连续的内存部分。这对您的应用程序来说可能是问题,也可能不是问题,但在任何情况下都值得关注。请参阅 this article series 以更深入地了解此事 (2)

(1):我正在考虑给定的结构示例 only ints。这意味着不需要 padding。如果有不同类型的成员,由于添加了填充,结构的总大小可能会略大于成员大小的总和。

(2):可以证明单次分配比多次分配更快。这通常是正确的,因为分配内存具有固有的开销。同样,这是您需要针对您的应用程序单独考虑的事情,而不是将笼统的陈述作为事实

可能的解决方案

我能想到的让你继续遵循这个策略的唯一原因是,如果你出于性能原因需要这样做,并且你想最小化 malloc 调用(也许你工作的平台有内存分配的重罚)。鉴于我可以建议修复您当前方法的一件事是将 get_array 宏修改为类似以下内容:

#define get_array(arr, idx) \
    _Generic((arr),         \
             Matrix *       \
             : (int(*)[(arr)[offset_for_index((arr), (idx))].columns])(arr)[offset_for_index((arr), (idx))].table)

并定义一个 offset_for_index 函数(或者作为一个宏,如果你愿意的话)例如:

static inline size_t offset_for_index(struct x *arr, size_t idx) {
    size_t offset = 0;

    for (size_t i = 0; i < idx; ++i) {
        offset += (sizeof *arr) + sizeof(int[arr[offset].a * arr[offset].b]);
    }

    // No need to safeguard because all our struct members are `int`, so
    // `offset` will, necessarily, be a multiple of `sizeof *arr`
    return offset / sizeof *arr;
}

但在我看来,这绝对很麻烦。我已将其声明为 inline 以尝试遵循避免函数调用的模式(假设您选择将 get_array 定义为宏)。并且该函数甚至可能不会被内联,除非您严格强制编译器这样做。有关内联函数的更多信息 and here.

此新设置的示例用法如下:

/* ... */

#define NUMBER_OF_MATRIX 2
#define TOTAL_TABLE_ELEMENTS 8
#define SIZE ((sizeof *a) * NUMBER_OF_MATRIX + sizeof(int[TOTAL_TABLE_ELEMENTS]))

int main() {
    Matrix *a = calloc(1, SIZE);

    a[offset_for_index(a, 0)].a = 2;
    a[offset_for_index(a, 0)].b = 2;

    a[offset_for_index(a, 1)].a = 2;
    a[offset_for_index(a, 1)].b = 2;

    for (size_t i = 0; i < 2; ++i) {
        for (size_t j = 0; j < 2; ++j) {
            get_array(a, 0)[i][j] = 10 * (i + 1);
            get_array(a, 1)[i][j] = -10 * (i + 1);
        }
    }

    // Your output block
    for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
        printf("Matrix %d\n", i+1);
        size_t idx = offset_for_index(a, i);
        for (uint x = 0; x < a[idx].rows; x++) {
            for (uint y = 0; y < a[idx].columns; y++) {
                printf("%d ", get_array(a, i)[x][y]);
            }
            printf("\n");
        }
    }

    free(a);

    return 0;
}

为什么打印语句在输入块中起作用?

并不是说他们确实在工作。您只是在打印您刚刚设置的内容。您所做的与以下内容几乎相同:

  /* ... */
  
  int n;
  scanf("%d", &n);
  pritnf("%d\n", n);

分配内存的正确方法

“只有西斯才做绝对的交易”。克诺比,Obi-Wan.

我不是特别喜欢通过说某些东西是正确的方法或者某些东西应该永远 used/done来限制方法](甚至 goto 在 IMO 中也有它的位置)。也就是说,我不会告诉您 正确的 内存分配方式是什么。但是,正如我之前提到的,鉴于我目前掌握的信息,我认为最好的方法是为 table 成员动态分配内存。您的结构定义将更新为:

typedef struct {
    uint rows, columns;
    int *table;
} Matrix;

并且在设置新矩阵后,您需要为 table:

分配内存
Matrix *matrix = malloc((sizeof *matrix) * NUMBER_OF_MATRIX);

for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
    matrix[i].rows = dimensions[i][0];
    matrix[i].columns = dimensions[i][1];

    matrix[i].table = malloc(sizeof(int) * matrix[i].rows * matrix[i].columns);
    for (uint x = 0; x < matrix[i].rows; x++) {
        for (uint y = 0; y < matrix[i].columns; y++)
        {
            printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
            scanf("%d", &get_array(matrix[i])[x][y]);
            printf("%d\n", get_array(matrix[i])[x][y]); // print statement 1
            // Mind `get_array` here is your original macro!
        }
    }
}

显然,您需要 free 那些不再需要的记忆。假设只有当你的程序完成时才会出现这种情况,下面的方法就可以了:

for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
    free(matrix[i].table);
}

free(matrix);

我不会回答最后一个问题,因为我相信我已经通过上面的部分一遍又一遍地回答了。简而言之,您应该考虑您的具体需求和您认为更重要的东西(可能是更清晰的代码,或者可能是一点——或更多——更高的性能)。

我希望这能说明问题,您将能够思考并为您的项目选择最佳的前进方式。此致!