c - 如何在 C 中为 int(不是 int*)数组动态分配内存？

Question

我正在尝试使用数组在 C 中实现堆栈。我想要一个整数数组，每次我尝试推送一个 int 时，我都想分配一些新内存。但我对 malloc() 的理解是它返回一个指向它在某处分配的内存的指针，如果我有一个 int 指针数组，这会很好，但我没有。这是我分配新内存的地方，我收到警告:

int stack[] = {1};  // stack is allocated like this

stack[lasti + 1] = malloc(sizeof(int));  // assignment makes integer from pointer without a cast

是否可以使用动态分配的非指针数组来实现堆栈？还是 malloc() 只适合使用指针数组？

编辑:我想我正在尝试将数组视为链表？似乎当我想使用 malloc 为数组分配空间时，它看起来像 malloc(sizeof(int) * maxSize)。这将在某处产生大量内存。我不能做的是要求 malloc 在该 block 的末尾给我另一 block 内存，但我可以扩展该 block 。如果我使用链表实现堆栈，malloc 将新空间放在哪里并不重要。我想我在脑海中混淆了一些东西。

那么下一个问题 - 如果使用数组实现堆栈，我是否必须指定堆栈的最大大小？

Answer 1

malloc() 返回的内存可用于存储一定大小的int 数组。实现数据结构的一种方法是使用 malloc() 分配一个固定大小的 int 数组。然后，您可以将元素插入数组，直到达到其最大大小。此时，您可以使用 realloc()(有关更多详细信息，请参见手册页)调整先前分配的 block 的大小以获得更多内存(您可以将先前的 size par 示例加倍)。或者另一种技术是使用多级堆栈，这意味着只要前一个堆栈空间用完，您就可以将新的堆栈帧添加到堆栈库中。避免 realloc() 的另一种可能方法(如果处理大内存块可能会失败)是在前一个堆栈帧已满时将其交换到磁盘中，然后使用相同的帧插入新值.

realloc() 堆栈的实现:

#define SCALE_FACTOR 2  /*  Double stack size at each new realloc   */

typedef struct stack {

    int *array;
    int stack_size;     /* Maximum number of elements */
    int stack_pointer;

} Stack;


int insert(Stack *ptr, int value)
{
    if(ptr->stack_pointer >= ptr->stack_size) {
        int realloc_size = ptr->stack_size * SCALE_FACTOR;
        int *new_array = realloc(ptr->array, realloc_size * sizeof(int));

        if(!new_array)
            return -1;   /* Resizing failed */

        ptr->array = new_array;
        ptr->stack_size = realloc_size;     
    }

    ptr->array[ptr->stack_pointer++] = value;
    return ptr->stack_pointer;
}

您必须在调用 insert() 之前初始化堆栈结构。
我在 ideone.com 上写了一个演示(永久保存文件)展示了堆栈的完整实现，其中包含插入 100 个元素且初始大小为 25 个元素的示例。

有些人建议为每个新插入调用 realloc()。这种方法非常糟糕，因为它会导致可怕的性能下降(realloc() 是一个繁重的函数)，尤其是当插入过程在一个单位时间内发生很多次时(插入开销)。