c - 如何在 C 中实现通用的、动态增长的数组？

Question

我的要求:

• 数据结构必须能够容纳任意数量的元素(大约数十万)。
• 数据结构必须有效地使用内存。在这种情况下，这意味着在需要时添加额外的十万个项目。
• 数据结构必须包含未知但统一类型的项目。

我期望能够构建一个的方式是定义一个表示数组的结构。该结构包含数组的长度和数组中元素的数量。它还包含一个指向 void 指针数组的指针，该数组指向实际数据。

使用指针是因为随着数组的增长，内存被 malloc() 和 realloc() 。该数组是空指针，因为元素的类型未知。用户有责任创建和初始化元素，将它们传递给数组实现，并跟踪正在使用的类型。

在内存中，结构体将存在于堆栈或堆中(用户选择)，元素本身将分散在整个堆中，并且指向元素的指针数组将存在于堆中。

问题是，当我去实现这个时，我需要能够将 void 指针分配给指针数组中的某个位置(例如，在附加元素时)，但我无法这样做，因为 void 指针不能被分配(编译器说“不完整类型'void'不可分配”)。

我应该使用不同的方法吗？

<小时/>

Nguai 的代码帮助我做对了!他的回答如下，这是我根据他的代码编写的实现:

typedef struct {
    void **head;
    size_t used_size;
    size_t free_size;
    size_t current_size;
    size_t size_increment;
} GrowingArray;

GrowingArray createEmptyGrowingArray(int initial_size, int size_increment) {
    GrowingArray empty_growing_array;
    empty_growing_array.head = malloc(initial_size * sizeof(void *));
    empty_growing_array.used_size = 0;
    empty_growing_array.free_size = initial_size;
    empty_growing_array.current_size = initial_size;
    empty_growing_array.size_increment = size_increment;

    return empty_growing_array;
}

GrowingArray appendToGrowingArray(GrowingArray growing_array, void *new_element) {

    void *new_head_of_array;

    if (growing_array.free_size == 0) {
        new_head_of_array = realloc(growing_array.head, (growing_array.current_size + growing_array.size_increment) * sizeof(void*));
        if (new_head_of_array == NULL) {
            printf("Reallocation failure.\n");
        }

        growing_array.free_size = growing_array.size_increment;
        growing_array.current_size += growing_array.size_increment;
        growing_array.head = new_head_of_array;
    }

    growing_array.head[growing_array.used_size++] = new_element;
    growing_array.free_size--;

    return growing_array;
}

void finalizeGrowingArrayMemory(GrowingArray growing_array) {
    growing_array.head = realloc(growing_array.head, growing_array.current_size * sizeof(void *));
}

void freeGrowingArray(GrowingArray growing_array) {
    free(growing_array.head);
}

int main(int argc, char* argv[]) {
    GrowingArray test_array = createEmptyGrowingArray(5, 1);

    int *test_integer = (int *)malloc(1 * sizeof(int));
    *test_integer = 4;

    int *another_integer = (int *)malloc(1 * sizeof(int));
    *another_integer = 6;

    int *yet_another_integer = (int *)malloc(sizeof(int));
    *yet_another_integer = 9;

    test_array = appendToGrowingArray(test_array, test_integer);
    test_array = appendToGrowingArray(test_array, another_integer);
    test_array = appendToGrowingArray(test_array, yet_another_integer);
    finalizeGrowingArrayMemory(test_array);

    printf("%x,", *(int *)test_array.head[0]);
    printf("%x,", *(int *)test_array.head[1]);
    printf("%x\n", *(int *)test_array.head[2]);

    freeGrowingArray(test_array);

    printf("Going to free %llx\n", (long long int)test_integer);
    free(test_integer);

    printf("Going to free %llx\n", (long long int)another_integer);
    free(another_integer);

    printf("Going to free %llx\n", (long long int)yet_another_integer);
    free(yet_another_integer);

    return 0;
}

Answer 1

这是一段代码，试图让您了解您所描述的内容。 这绝不是一个解决方案。 该比例为 2，因此您可以对其进行拉伸(stretch)。

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

 const size_t stIncrement = 2;

 typedef struct
 {
    size_t space_left;
    size_t size;
    void **vptrX;
 }T;

 T t;

 void
 vStoreData( void *data )
 {
    void *vptrTemp;
    size_t stMaxLength;

   if( t.space_left == 0 )
   {
       stMaxLength = t.size + stIncrement;
       vptrTemp = realloc(t.vptrX, stMaxLength * sizeof(void *) );
       if( vptrTemp == NULL ){
          printf( "Failed realloc");
         exit(1);
       }
       t.space_left = stIncrement;
       t.vptrX = vptrTemp;
   }

   t.vptrX[t.size++] = data;
   t.space_left--;
}

//This will make the memory efficient.
void
vFinalizeMemory()
{
   t.vptrX = realloc(t.vptrX, t.size * sizeof(void *));
}

int
main(void)
{
   int i;
   char c;
   float d;
   char *cp = "How are you";
   i = 10;
   c ='O';

   d = 40.12345;

   t.vptrX = malloc(stIncrement*sizeof(void *));
   t.size = 0;
   t.space_left = 2;

   vStoreData( &i );

   vStoreData( &c );

   vStoreData( cp );

   vStoreData( &d );

   vStoreData( &c );

   vStoreData( cp );
   vStoreData( &d );

   vFinalizeMemory();
   printf( "%d\n", *((int *)t.vptrX[0]) );
   printf( "%c\n", *((char *)t.vptrX[1] ));
   printf( "%s\n", (char *)t.vptrX[2] );
   printf( "%f\n", *((float*)t.vptrX[3] ));
   printf( "%c\n", *((char *)t.vptrX[4] ));
   printf( "%s\n", (char *)t.vptrX[5] );
   printf( "%f\n", *((float*)t.vptrX[6] ));

   return 0; 
}