为不同大小的结构数组动态分配 space

Question

我遇到了一个对我来说似乎很复杂的问题，所以我将非常感谢能帮助我的人。

我有点想只用结构来复制字符串行为的数组所以而不是例如

char **mys={"hello","this is a long message"};

我正在尝试使用结构数组（每个结构包含一个可变长度数组）。我不太确定我是否很好地暴露了我的问题，所以我希望代码能够表明我正在尝试做什么：

我的两个结构：

typedef struct
{
    int *iTab;
    int iTail;
}strDynArr;

typedef struct
{
    strDynArr **iTab;
    int iTailStruct;
    int iTail;
}strDynDynArr;

与这两个结构相关的所有函数：

void initArray(strDynArr *ar)
{
    ar->iTab=malloc(sizeof(int));
    ar->iTail=1;
}

void pushArray(int iElement,strDynArr *ar)
{
    ar->iTab[ar->iTail-1]=iElement;
    realloc(ar->iTab,(ar->iTail++)*sizeof(int));
}

void freeDynArray(strDynArr *ar)
{
    free(*ar->iTab);
}

void initDynDynArray(strDynDynArr *ar)
{
    ar->iTab=malloc(sizeof(int));
    ar->iTail=1;
    ar->iTailStruct=1;
}

//the problem
void pushDynDynArray(strDynArr *daElement,strDynDynArr *ar)
{
    //ar->iTab[ar->iTail-1]=daElement;
    ar->iTailStruct+=(daElement->iTail+1);
    realloc(ar->iTab,(ar->iTailStruct)*sizeof(int));
    ar->iTab[ar->iTailStruct-(daElement->iTail+1)]=daElement;
    //realloc(ar->iTab,(ar->iTail++)*sizeof(int));
}
void freeDynDynDynArray(strDynDynArr *ar)
{
    free(*ar->iTab);
}

我被卡住的一个函数是 pushDynDynArray 到目前为止，我已经尝试了两件事，要么只是使用指向结构 strDynArr 的指针，但我不知道 space 是如何管理的所以我尝试分配结构 strDynDynArr 数组中包含的所有结构的大小。

所以我想知道的是如何为我的数组 (iTab) 分配 space 类型为 strDynDynArr 的结构。

换句话说，我存储多个结构的方式是什么，例如：

//content of structure 1
int *iTab={2,3,4};
int iTail=3;

//content of structure 2
int *iTab={5,8,9,10,54,8,2};
int iTail=7;

欢迎所有帮助，非常感谢！

Answer 1

为简单起见，我们称每个 "strings" 数组为 table（数组），每个 "string" 为项目数组。在您的情况下，项目类型似乎是 int:

typedef int  item;

typedef struct {
    size_t  size;   /* Number of items allocated for */
    size_t  used;   /* Number of items in item[] */
    item   *item;
} array;

typedef struct {
    size_t  size;   /* Number of array (pointers) allocated for */
    size_t  used;   /* Number of arrays in array[] */
    array  *array;
} table;

通常为此类类型定义初始化宏和函数：

#define  ARRAY_INIT  { 0, 0, NULL }
#define  TABLE_INIT  { 0, 0, NULL }

static inline void array_init(array *ref)
{
    if (!ref) {
        fprintf(stderr, "array_init(): NULL array!\n");
        exit(EXIT_FAILURE);
    }
    ref->size = 0;
    ref->used = 0;
    ref->item = NULL;
}

static inline void table_init(table *ref)
{
    if (!ref) {
        fprintf(stderr, "table_init(): NULL table!\n");
        exit(EXIT_FAILURE);
    }
    ref->size = 0;
    ref->used = 0;
    ref->array = NULL;
}

此外，免费功能显然很有用：

static inline void array_free(array *ref)
{
    if (!ref) {
        fprintf(stderr, "array_free(): NULL array!\n");
        exit(EXIT_FAILURE);
    }

    free(ref->item); /* Note: free(NULL) is safe; it does nothing. */
    ref->size = 0;
    ref->used = 0;
    ref->item = NULL;
}

static inline void table_free(table *ref)
{
    size_t  i;

    if (!ref) {
        fprintf(stderr, "table_free(): NULL table!\n");
        exit(EXIT_FAILURE);
    }

    i = ref->size;
    while (i-->0)
        array_free(ref->array + i); /* array_free(&(ref->array[i])); */

    free(ref->array);
    ref->size = 0;
    ref->used = 0;
    ref->array = NULL;
}

释放table时，我们希望单独释放所有（可能的）数组，然后是指针使用的内存。请注意，可以假设只有 used 个数组在使用中；但是，我希望上面的内容彻底，并释放所有分配给 size 的数组。

上面的 init 和 free 函数都采用指向数组或 table 的指针。它们永远不应该为 NULL。（也就是说，结构中的 item 或 array member 很可能是 NULL；只是你永远不应该调用 array_init(NULL); 或 table_free(NULL).)

让我们实现一个函数来从单个数组（可能是也可能不是 table 的一部分）中压入和弹出单个整数：

void array_push(array *ref, const item value)
{
    if (!ref) {
        fprintf(stderr, "array_push(): NULL array!\n");
        exit(EXIT_FAILURE);
    }

    /* Need to grow the array? */
    if (ref->used >= ref->size) {
        size_t  size; /* Minimum is ref->used + 1 */
        void   *temp;

        /* Dynamic growth policy. Pulled from a hat. */
        if (ref->used < 64)
            size = 64;  /* Minimum 64 elements */
        else
        if (ref->used < 1048576)
            size = (3*ref->used) / 2; /* Grow by 50% up to 1048576 */
        else
            size = (ref->used | 1048575) + 1048577; /* Grow to next multiple of 1048576 */

        temp = realloc(ref->item, size * sizeof ref->item[0]);
        if (!temp)
            return -1; /* Out of memory */

        ref->item = temp;
        ref->size = size;
    }

    /* Append value to array. */
    ref->item[ref->used++] = value;
}

和对应的pop操作：

item array_pop(array *ref)
{
    if (!ref) {
        fprintf(stderr, "array_pop(): NULL array!\n");
        exit(EXIT_FAILURE);
    }

    if (ref->used < 1) {
        fprintf(stderr, "array_pop(): Array is already empty; nothing to pop.\n");
        exit(EXIT_FAILURE);
    }

    /* Since ref->used is the *number* of items in the array,
       we want to decrement it first, to get the last item in array. */
    return ref->item[--ref->used];
}

在你的程序中，你可以这样使用一个数组：

array  scores = ARRAY_INIT;

array_push(&scores, 5);
array_push(&scores, 2);

printf("%d\n", array_pop(&scores)); /* Will print 2 */
printf("%d\n", array_pop(&scores)); /* Will print 5 */

array_free(&scores);

行array scores = ARRAY_INIT; 声明并初始化数组（为空数组）。您也可以等效地使用 array scores; array_init(&scores);.

array_push() 中的调整大小或增长策略大致符合我个人推荐的路线，尽管实际数值是从帽子里拉出来的，您可能希望调整它们。这个想法是分配的项目数量最少（例如，64）。对于更大的数组，我们会少量增加大小，这样当数组很大时，大小增加也很大。许多人使用 100% 的大小增加（将大小加倍，即 size = 2 * ref->used;），但我更喜欢 50% 的大小增加（将大小乘以一又二分之一，size = (3 * ref->used) / 2;）。对于巨大的数组，我们不想浪费潜在的大量内存，所以我们分配固定大小（但很大）的块。（没有必要像我一样将巨大的尺寸与某个倍数对齐，也没有真正的好处；我就是喜欢这样。而且更复杂的代码确保您需要理解它并对其进行编辑，而不是像您一样提交它；否则，你的老师会发现你作弊。）

将单个值推送到 table 中的最后一个数组现在很容易实现：

void table_push_value(table *ref, const item value)
{
    size_t  i;

    if (!ref) {
        fprintf(stderr, "table_push_value(): NULL table!\n");
        exit(EXIT_FAILURE);
    }

    /* Ensure there is at least one array. */
    if (!ref->size < 1) {
        /* Empty table: ref->size = 0, and ref->used must be 0 too. */
        const size_t  size = 1; /* Allocate for exactly one array. */
        void         *temp;

        temp = realloc(ref->array, size * sizeof ref->array[0]);
        if (!temp) {
            fprintf(stderr, "table_push_value(): Out of memory.\n");
            exit(EXIT_FAILURE);
        }

        ref->size = size;
        ref->array = temp;

        for (i = 0; i < size; i++)
            array_init(ref->array + i); /* array_init(&(ref->array[i])); */
    }

    if (ref->used > 0)
        i = ref->used - 1;  /* Last array in table */
    else
        i = 0; /* Table is empty, so use first array */

    array_push(ref->array + i, value); /* array_push(&(ref->array[i])); */
}

这一次，您需要一个空 table 的特殊逻辑，用于分配数组的描述以及推送到何处。

流行更简单：

item table_pop_value(table *ref)
{
    size_t  i;

    if (!ref) {
        fprintf(stderr, "table_pop_value(): NULL table!\n");
        exit(EXIT_FAILURE);
    }

    i = ref->used;

    /* Find the last array with items in it, and pop from it. */
    while (i-- > 0)
        if (ref->array[i].used > 0) {
            return array_pop(ref->array + i); /* array_pop(&(ref->array[i])); */

    fprintf(stderr, "table_pop_value(): Empty table, no items to pop!\n");
    exit(EXIT_FAILURE);
}

将整个数组推送到 table（推送其中的项目数组，而不是复制项目）非常简单，但我们确实需要实现 reallocation/growth再次政策：

void table_push_array(table *ref, array *one)
{
    if (!ref) {
        fprintf(stderr, "table_push_array(): NULL table!\n");
        exit(EXIT_FAILURE);
    }
    if (!one) {
        fprintf(stderr, "table_push_array(): NULL array!\n");
        exit(EXIT_FAILURE);
    }

    if (ref->used >= ref->size) {
        size_t  size, i;
        void   *temp;

        if (ref->used < 1)
            size = 1;  /* Minimum size is 1 */
        else
            size = (ref->used | 7) + 9; /* Next multiple of 8 */

        temp = realloc(ref->array, size * sizeof ref->array[0]);
        if (!temp) {
            fprintf(stderr, "table_push_array(): Out of memory.\n");
            exit(EXIT_FAILURE);
        }

        ref->array = temp;
        for (i = ref->size; i < size; i++)
            array_init(ref->array + i); /* array_init(&(ref->array[i])); */
        ref->size = size;
    }

    ref->array[ref->used] = *one; /* "shallow copy" */
    ref->used++;
}

对应的pop操作应该很明显了：

array *table_pop_array(table *ref)
{
    array  retval = ARRAY_INIT;

    if (!ref) {
        fprintf(stderr, "table_pop_array(): NULL table!\n");
        exit(EXIT_FAILURE);
    }

    if (ref->used < 1) {
        fprintf(stderr, "table_pop_array(): Table is empty, no arrays to pop!\n");
        exit(EXIT_FAILURE);
    }        

    /* Decrement the used count, so it refers to the last array in the table. */
    ref->used--;

    /* Shallow copy the array. */
    retval = ref->array[ref->used];

    /* Init, but do not free, the array in the table. */
    array_init(ref->array + ref->used); /* array_init(&(ref->array[ref->used)); */

    /* Return the array. */
    return retval;
}

上面table_pop_array()中有一个"trick"，你应该明白了。虽然我们不能 return 指向局部变量的指针，但我们可以 return 结构。在上面的例子中，结构体描述的是数组，其中的指针不是指向局部变量，而是指向一个动态分配的数组项。可以像普通标量类型一样分配结构类型（如 int 或 double）；基本上和你分别分配每个成员是一样的。

总的来说，您应该注意到我没有使用过一个 malloc() 调用。这是因为 realloc(NULL, size) 等同于 malloc(size)，简单地将未使用的指针初始化为 NULL 会使一切变得更简单。

当 table 增长（重新分配）时，我们确实需要初始化所有新数组，因为上面 realloc() 使用模式。

上述方法不排除直接访问table中的特定数组或数组中的特定项。如果你打算实现这样的功能，两个辅助函数类似于

void table_need_arrays(table *ref, const size_t size);
void array_need_items(array *ref, const size_t size);

确保 table 至少有 size 个数组的空间，并且一个数组至少有 size 个项目的空间。当连续推送多个项目或数组时，它们也很有用，就像一个人可以做的那样。 table_need_arrays(&mytable, mytable.used + 10); 以确保在 table.

中有额外的 10 个数组的空间

在上面的所有函数中，您都可以看到符号 name_of_array + index，以及带有相应 &(name_of_array[index]) 的注释。这是因为这两个表示法是等价的：指向 name_of_array.

中第 index 个元素的指针

我没有费心编译检查上面的代码，所以那里可能隐藏了错别字。（这也是有意为之的，因为我希望您理解代码，而不是在不了解任何细节的情况下只是复制它并将其用作您自己的代码。）但是，逻辑是合理的。所以，如果您发现拼写错误或问题，请在评论中告诉我，我会改正。

为不同大小的结构数组动态分配 space

dynamically allocate space for varying size structures array

c

memory-management

allocation

dynamic

multidimensional-array