C: 函数调用覆盖的堆栈元素

Question

我正在做一项学校作业，我遇到了两个问题。我必须用数组来模拟堆栈。我当前的代码如下：

#include <stdlib.h>
#include <stdio.h>
typedef struct {
    int capacity;
    int * array;
    int size;
} stack_tt;
int pop(stack_tt * stack_p);
void push(stack_tt * stack_p, int value);
int top(stack_tt * stack_p);
stack_tt * newStack(void);
int empty(stack_tt * stack_p);
int main() {
    stack_tt * myStack = newStack();
    push(myStack, 123);
    push(myStack, 99);
    push(myStack, 4444);
    while (!empty(myStack)) {
        int value;
        value = pop(myStack);
        printf("popped: %dn", value);
    }
    return 0; }
stack_tt * newStack(){
    stack_tt * newS = malloc(sizeof(stack_tt) * 20);
    (*newS).capacity = 1;
    (*newS).size = 0;
    return newS;
}
void push(stack_tt * stack_p, int value){
    if ((*stack_p).size >= (*stack_p).capacity) {
        (*stack_p).capacity*=2;
        //realloc(stack_p, stack_p->capacity * sizeof(stack_tt));
    }
    (*stack_p).array = &value;
    (*stack_p).size++;
}
int pop(stack_tt * stack_p){
    (*stack_p).size--;
    int fap = *(*stack_p).array;
    return fap;
}
int empty(stack_tt * stack_p){
    if ((*stack_p).size >= 1)
        return 0;
    return 1;
}

当我打电话时while（！empty（myStack））它将数组中的值更改为1。

其次，每当我尝试以下操作时，我都无法更改数组中的单个值：（*stack_p）.array[0]=值；它不知道该在记忆中寻找什么。我希望有人能帮我：）

Answer 1

在我看来，代码有几个问题。

让我们在进行时使用push函数

(*stack_p).array = &value;

这将使array结构成员指向本地变量value，一旦函数返回，该变量将不存在，留下一个游离指针，使用该指针将导致未定义的行为。

该代码的第二个问题是，堆栈只会（非法）指向最后添加的元素。

必须为array显式分配内存，并使用capacity来跟踪分配的内存量。使用size作为索引进入分配的数组进行推送和弹出。类似的东西

stack_tt * newStack(){
    stack_tt * newS = malloc(sizeof(stack_tt));  // Only allocate *one* structure
    newS->capacity = 0;  // Start with zero capacity
    newS->size = 0;
    newS->array = NULL;
    return newS;
}
void push(stack_tt * stack_p, int value){
    if (stack_p->size + 1 > stack_p->capacity){
        // Increase capacity by ten elements
        int new_capacity = stack_p->capacity + 10;
        int * temp_array = realloc(stack_p->array, new_capacity * sizeof(int));
        if (temp_srray == NULL)
            return;
        stack_p->capacity = new_capacity;
        stack_p->array = temp_array;
    }
    stack_p->array[stack_p->size++] = value;
}
int pop(stack_tt * stack_p){
    if (stack_p->size > 0)
        return stack_p->array[--stack_p->size];
    return 0;
}
int empty(stack_tt * stack_p){
    return stack_p->size == 0;
}

Answer 2

不需要为20个stack_tt类型的结构分配空间，只需要为一个分配空间：

stack_tt * newS = malloc(sizeof(stack_tt));

但是，您需要为结构成员数组的元素分配空间：

newS->array = malloc( sizeof(int)*20);
newS->size = 0;
newS->capacity = 20;

现在您可以使用数组成员了。

---

当你把一个值推送到"堆栈"时，你不应该用本地变量的地址覆盖数组成员，这没有意义，除了会丢失之前分配的内存外，还会导致未定义的行为。相反，只需在函数push:中将值分配给成员array

stack_p->array[stack_p->size] = value;
stack_p->size++;

---

类似地，当您弹出一个元素时，从成员array:中获取当前元素

stack_p->size--;
int fap = stack_p->array[stack_p->size];

其余的函数和代码应该以相同的方式固定。

Answer 3

您的代码不错，但可能不了解realloc:的用法

//realloc(stack_p, stack_p->capacity * sizeof(stack_tt));

此函数返回一个指向新分配内存的指针，如果请求失败，则返回NULL。

realloc（如函数所示）获取您传递的指针所指向的内存，并将该内存块复制到新的并调整大小的块中。所以正确的代码应该是。

stack_p->array = realloc(stack_p->array, stack_p->capacity * sizeof(stack_tt));

另一行错了：

(*stack_p).array = &value;

更改为：

stack_p->array[stack_p->size] = value;

另一个小建议是，每个(*stack_p).都可以用stack_p->代替，这样更优雅。

在newStack()中，你是malloc和20个结构，这有点无用。你只需要一个。

那么你应该第一次malloc数组：

newS->array = malloc(sizeof(int));
newS->capacity = 1;