如何在C中使用單個malloc分配三角形數組？

Question

我想分配使用單個malloc的三角形數組，但我無法找到任何解決方案。我的結構是這樣的：

  a - - - - 
      b c - - - 
      d e f - - 
      g h i j - 
      k l m n o 

我已經使用了兩個malloc。

Answer 1

如果您想使用一個malloc並創建一個連續數組，您可以只使用malloc(width * height * sizeof(Object))。如果要訪問（x，y）位置，請使用：array[y * width + x]。

使用兩個malloc只是創建一個指針數組，這與指向二維數組的連續數組有點不同。

Answer 2

你打算如何使用這個結構 - 你會寫什麼代碼來訪問一個數組元素？另外，你處理的是多大的數組？

如果數組足夠小（比如小於100x100，但邊界值是可協商的），那麼使用常規矩形數組並訪問像往常一樣接受一些分配的空間是未使用的是合理的。如果陣列足夠大，未使用的空間會有問題，那麼你必須更加努力。

你打算使用lt_matrix[r][c]符號，或者你可以使用其中x從r和c計算出一維數組lt_matrix[x]？如果您可以使用1D符號，那麼您可以使用一次分配 - 如下面代碼中的技術1所示。如果使用雙下標記法，則應該執行兩次內存分配 - 如下面代碼中的技術2所示。如果你不介意生活危險，你可以將其與技巧3混合使用，但不建議你使用它，除非你能確定限制和問題是什麼，併爲自己評估它是否足夠安全使用。 （如果你問我，回答的「不，不使用它」，但可能被視爲過於豐富謹慎。）

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

static inline int lt_index(int r, int c) { assert(r >= c); return r * (r + 1)/2 + c; } 

int main(void) 
{ 
    int matrixsize = 5; 

    /* Technique 1 */ 
    char *lt_matrix1 = malloc(matrixsize * (matrixsize + 1)/2 * sizeof(*lt_matrix1)); 
    assert(lt_matrix1 != 0); // Appalling error checking 

    char value = 'a'; 
    for (int i = 0; i < matrixsize; i++) 
    { 
     for (int j = 0; j <= i; j++) 
      lt_matrix1[lt_index(i, j)] = value++; 
    } 

    for (int i = 0; i < matrixsize; i++) 
    { 
     int j; 
     for (j = 0; j <= i; j++) 
      printf("%-3c", lt_matrix1[lt_index(i, j)]); 
     for (; j < matrixsize; j++) 
      printf("%-3c", '-'); 
     putchar('\n'); 
    } 

    free(lt_matrix1); 

    /* Technique 2 */ 
    char **lt_matrix2 = malloc(matrixsize * sizeof(*lt_matrix2)); 
    assert(lt_matrix2 != 0); // Appalling error checking 
    char *lt_data2 = malloc(matrixsize * (matrixsize + 1)/2 * sizeof(*lt_matrix1)); 
    assert(lt_data2 != 0); // Appalling error checking 
    for (int i = 0; i < matrixsize; i++) 
     lt_matrix2[i] = &lt_data2[lt_index(i, 0)]; 

    value = 'A'; 
    for (int i = 0; i < matrixsize; i++) 
    { 
     for (int j = 0; j <= i; j++) 
      lt_matrix2[i][j] = value++; 
    } 

    for (int i = 0; i < matrixsize; i++) 
    { 
     int j; 
     for (j = 0; j <= i; j++) 
      printf("%-3c", lt_matrix2[i][j]); 
     for (; j < matrixsize; j++) 
      printf("%-3c", '-'); 
     putchar('\n'); 
    } 

    free(lt_data2); 
    free(lt_matrix2); 

    /* Technique 3 - do not use this */ 
    void *lt_data3 = malloc(matrixsize * sizeof(int *) + matrixsize * (matrixsize + 1)/2 * sizeof(int)); 
    assert(lt_data3 != 0); // Appalling error checking 
    int **lt_matrix3 = lt_data3; 
    int *lt_base3 = (int *)((char *)lt_data3 + matrixsize * sizeof(int *)); 
    for (int i = 0; i < matrixsize; i++) 
     lt_matrix3[i] = &lt_base3[lt_index(i, 0)]; 

    value = 1; 
    for (int i = 0; i < matrixsize; i++) 
    { 
     for (int j = 0; j <= i; j++) 
      lt_matrix3[i][j] = value++; 
    } 

    for (int i = 0; i < matrixsize; i++) 
    { 
     int j; 
     for (j = 0; j <= i; j++) 
      printf("%-3d", lt_matrix3[i][j]); 
     for (; j < matrixsize; j++) 
      printf("%-3c", '-'); 
     putchar('\n'); 
    } 

    free(lt_data3); 

    return 0; 
} 

從程序的輸出是：

a - - - - 
b c - - - 
d e f - - 
g h i j - 
k l m n o 
A - - - - 
B C - - - 
D E F - - 
G H I J - 
K L M N O 
1 - - - - 
2 3 - - - 
4 5 6 - - 
7 8 9 10 - 
11 12 13 14 15 

Valgrind版本3.13.0.SVN（修訂版16398）使用GCC 7.1.0爲macOS Sierra 10.12.5提供了一份乾淨的健康法案。