c - 如何在 C 中使用单个 malloc 分配三角数组？

Question

我正在尝试使用单个 malloc 分配三角形数组，但我找不到任何解决方案。我的结构是这样的:

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

我使用两个 malloc 来实现它。

Answer 1

您打算如何使用该结构 - 您将编写什么代码来访问数组元素？另外，您要处理的数组大小是多少？

如果数组足够小(比如小于 100x100，但边界值是可以协商的)，那么使用常规矩形数组并像往常一样访问它是有意义的，接受一些分配的空间未使用。如果数组足够大，未使用的空间就会出现问题，那么你就必须更加努力。

您打算使用 lt_matrix[r][c] 表示法，还是可以使用一维数组 lt_matrix[x] 其中 x 是根据r 和c 计算出来的？如果您可以使用一维表示法，那么您可以使用单个分配 - 如下面代码中的技术 1 所示。如果您使用双下标表示法，您可能应该进行两次内存分配 - 如下面代码中的技术 2 所示。如果您不介意生活在危险之中，您可以将技术 3 与技术 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 上提供了良好的运行状况。