重新分配参数

Question

我正在使用带有以下代码的数组实现 Stack

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

struct Stack{
int top;
int capacity;
int *array;
};

struct Stack *createStack()
{
        struct Stack *stack=malloc(sizeof(struct Stack));
        stack->top=-1;
        stack->capacity=1;
        stack->array=malloc(sizeof(sizeof(int)*stack->capacity));
}
void doubleStack(struct Stack *stack)
{
        stack->capacity=stack->capacity*2;
        stack->array=realloc(stack,stack->capacity);
}
void push( struct Stack *stack , int data)
{
        if(stack->top==(stack->capacity)-1)
                doubleStack(stack);
        stack->array[++stack->top]=data;
}

我的疑问是，一旦堆栈已满，调用 doubleStack 时，我应该使用 stack->array 作为 realloc() 的第一个参数还是 stack 作为 realloc() 的第一个参数？

嗯，我认为 stack->array 应该通过。因为我们只需要重新分配那部分内存。

但不小心我通过了 stack，这似乎也有效。请指教。

Answer 1

如您所想，

  stack->array=realloc(stack,stack->capacity);

至少应该是

  stack->array=realloc(stack->array,stack->capacity);

否则，如果成功，您将 free()-ing up stack 本身，然后您将最终访问它。这会调用 undefined behaviour。获得 UB 后，许多事情 "seem" 都可以使用。

也就是说，从使用的角度来说，

 p = realloc(p, q);

这种代码很糟糕，好像realloc()失败了，它不会修改作为参数传递的p，但是由于[=的直接赋值realloc() 的 40=] 值变为 p，p 将被设置为 NULL，丢失实际存储的指针。

提示：始终使用临时指针收集 realloc() 的 return 值，然后检查 realloc() 是否成功，如果成功，分配新的 returned 指向已传递给 realloc().

的指针

Answer 2

您应该向 realloc 传递一个指向您希望扩展的数组的指针。由于 stack 不是您希望扩展的数组，而 stack->array 是，您应该将 stack->array 作为第一个参数传递。

但是，您应该将 realloc 的结果存储在一个单独的变量中并进行 NULL 检查。

If the function fails to allocate the requested block of memory, a null pointer is returned, and the memory block pointed to by argument ptr is not deallocated (it is still valid, and with its contents unchanged).

否则您可能会造成内存泄漏：

int *tmp = realloc(stack->array, stack->capacity);
if (tmp) {
    stack->array = tmp;
} else {
    ... // Deal with the allocation error here
}

Answer 3

首先函数push是错误的

void push( struct Stack *stack , int data)
{
        if(stack->top==(stack->capacity)-1)
                doubleStack(stack);
        stack->array[++stack->top]=data;
}

最初top设置为1，capacity也设置为1。

所以这个条件

if(stack->top==(stack->capacity)-1)

产生 false 和下面的语句

stack->array[++stack->top]=data;

被执行。它写入超出分配数组的内存 stack->array[2]。

我认为最初top应该设置为0。函数应该按以下方式定义

void push( struct Stack *stack , int data )
{
        if ( stack->top != stack->capacity || doubleStack( stack ) )
        {
            stack->array[stack->top++] = data;
        } 
}

在这种情况下，您可以简单地定义一个报告堆栈是否为空的函数，方法如下

int empty( struct Stack *stack ) { return stack->top == 0; }

至于函数doubleStack那么应该这样定义

int doubleStack(struct Stack *stack)
{
        int success = 0;

        int new_capacity = 2 * stack->capacity;

        int *tmp = = realloc( stack->array, new_capacity * sizeof( int ) );

        if ( ( success = tmp != NULL ) ) 
        {
            stack->capacity = new_capacity;
            stack->array = tmp;
        }

        return success
}

考虑到我将函数的 return 类型从 void 更改为 int。我还使用了一个中间变量 new_capacity。如果重新分配失败，当前容量将不会改变

重新分配参数

Realloc Arguments

c

realloc

dynamic-memory-allocation