我正在尝试使用数组在 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 将新空间放在哪里并不重要。我想我在脑海中混淆了一些东西。
那么下一个问题 - 如果使用数组实现堆栈,我是否必须指定堆栈的最大大小?
最佳答案
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() 是一个繁重的函数),尤其是当插入过程在一个单位时间内发生很多次时(插入开销)。
关于c - 如何在 C 中为 int(不是 int*)数组动态分配内存?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46392503/