多维数组索引

Question

我在几个地方读到过，这样分配多维数组效率低下，应该避免。

int main(){
    int** arr2d = malloc(3*sizeof(int*));
    for(int m = 0; m < 3 ; ++m){
        arr2d[m] = malloc(sizeof(int)*3);
    }
    for(int m = 0 ; m < 3 ; ++m){
        for(int n = 0; n < 3; ++n){
            arr2d[m][n] = m+n;
        }
    }
    for(int m = 0 ; m < 3 ; ++m){
        for(int n = 0; n < 3; ++n){
            printf("%d,",arr2d[m][n]);
        }
        printf("\n");
    }
    for(int m = 0; m < 3 ; ++m){
        free(arr2d[m]);
    }
    free(arr2d);
    return 0;
}

另一种方法是为 m*n 分配一个足够的数组并相应地对其进行索引，给出 2D

的想法

int main(){
    int* arr = malloc(9*sizeof(int));
    for(int m = 0; m < 3; ++m){
        for(int n = 0; n < 3; ++n){
            int index = m*3+n;
            arr[index] = m+n;
        }
    }
    
    for(int m = 0; m < 3; ++m){
        for(int n = 0; n < 3; ++n){
            int index = m*3+n;
            printf("%d,",arr[index]);
        }
        printf("\n");
    }
    free(arr);
    return 0;
}

我想知道的是，这在资源使用和时间安排方面究竟有多大差异？我知道在第一个示例中总共分配了 32 个字节，在第二个示例中分配了 27 个字节。在处理更大的矩阵时，我可以看到有所不同，但是时间复杂度会改变还是无关紧要，因为无论如何都要循环 m*n 次？我应该始终遵循第二个示例作为基本标准吗？

Answer 1

如果你有一个矩形矩阵，即所有 m x n 值，那么使用第二个选项会更简单、内存消耗更少并且更不容易出错（尽管它可以说仍然是一个品尝者的问题.... ).

如果你没有长方形的东西，第一个选项会更有效，例如类似于不同长度的子数组的数组。
内存浪费在那里变得非常重要。

另一个例子，回到矩阵，将是一个三角矩阵，在三角形之外有 0 或其他已知值。实现可以从该属性中受益，并使用三角形外部的“无聊”或可预测值，而无需存储它们。

Answer 2

您可以通过直接为多维数组分配内存来两全其美：

int (*arr)[3] = malloc(3 * sizeof *arr);

for(int m = 0 ; m < 3 ; ++m){
    for(int n = 0; n < 3; ++n){
        arr[m][n] = m+n;
    }
}
for(int m = 0 ; m < 3 ; ++m){
    for(int n = 0; n < 3; ++n){
        printf("%d,",arr[m][n]);
    }
    printf("\n");
}

free(arr);

这会像第二个示例一样在单个连续块中创建内存，从而提高读写效率，并为您提供二维数组索引，从而更易于阅读代码并让编译器找出最佳方法在内部索引内存块。

多维数组索引

Multidimensional Array indexing

c

multidimensional-array