C语言数组实现栈的动态内存分配问题求助

我正在学习数据结构，尝试用数组手动实现栈。当栈已满时执行push操作，我通过realloc()对之前用malloc()分配的数组指针扩容1个单位后再存入元素，但用valgrind运行代码时出现错误："Invalid write of size4 ... 4 bytes before a block of size 16 alloc'd"。相关代码如下：

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;


stack* build(){
    stack *new = (stack*) malloc(sizeof(stack));
    new->v = (int*) malloc(sizeof(int) * 4);
    new->cap = 4;
    new->sz = 0;
    return new;
}

int is_empty(stack *s){
    return s->sz == 0;
}

int push( stack *s, int e )
{
    int success = 1;

    if (s->sz == s->cap){
        int*tmp =(int*)realloc(s->v,(s->cap+1)*sizeof( int));
        if (( success = tmp != NULL )){
            s->v = tmp;
            ++s->cap;
        }
    }

    if (success){
        s->v[s->sz++] = e;
    }

    return success;
}
int top(stack *s){
    return *(s->v);
}

int pop(stack *s){
    int value;

    if(is_empty(s))
        return -1;

    value = *(s->v);
    s->v--;
    s->sz--;
    return value;   
}

void destroy(stack *s){
    s->v -= s->sz + 1;
    free(s->v);
    free(s);
}

int match(char p1, char p2){
    if(p1 == '(')
        return (p1 - p2) == '(' - ')';
    else if(p1 == '[')
        return (p1 - p2) == '[' - ']';
    else
        return (p1 - p2) == '{' - '}';
}

int main(){
    int c;
    stack *s = build();
    while((c = getchar()) != EOF && c != '\n'){
        if(c == '(' || c == '[' || c == '{')
             push(s, c);
        else if(c == ')' || c == ']' || c == '}'){
            if(!match(pop(s), c)){
                printf("no\n");
                destroy(s);
                return 0;
            }
        }
    }
    puts((is_empty(s)) ? "yes" : "no");
    destroy(s);
    return 0;
}

核心问题分析 #

你的栈实现逻辑完全偏离了数组栈的设计思路——错误地把数组指针v当作栈顶指针移动，而非用sz索引数组元素，直接引发越界写和内存释放错误：

• top()函数错误：当前返回数组第一个元素，栈顶应该是数组的第sz-1位元素
• pop()函数错误：通过s->v--移动数组指针，会让指针指向malloc分配的内存块外部，触发valgrind越界警告；正确逻辑是通过sz的变化管理栈顶，无需移动数组指针
• destroy()函数错误：试图通过指针偏移恢复初始位置的操作完全多余且错误，会导致free时访问非法内存

修复后的完整代码 #

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;


stack* build(){
    stack *new = malloc(sizeof(stack));
    new->v = malloc(sizeof(int) * 4);
    new->cap = 4;
    new->sz = 0;
    return new;
}

int is_empty(stack *s){
    return s->sz == 0;
}

int push( stack *s, int e )
{
    int success = 1;

    if (s->sz == s->cap){
        int* tmp = realloc(s->v, (s->cap + 1) * sizeof(int));
        if ((success = tmp != NULL)){
            s->v = tmp;
            ++s->cap;
        }
    }

    if (success){
        s->v[s->sz++] = e;
    }

    return success;
}

int top(stack *s){
    return s->v[s->sz - 1];
}

int pop(stack *s){
    if(is_empty(s))
        return -1;

    return s->v[--s->sz];
}

void destroy(stack *s){
    free(s->v);
    free(s);
}

int match(char p1, char p2){
    if(p1 == '(')
        return p2 == ')';
    else if(p1 == '[')
        return p2 == ']';
    else if(p1 == '{')
        return p2 == '}';
    return 0;
}

int main(){
    int c;
    stack *s = build();
    while((c = getchar()) != EOF && c != '\n'){
        if(c == '(' || c == '[' || c == '{')
             push(s, c);
        else if(c == ')' || c == ']' || c == '}'){
            if(is_empty(s) || !match(pop(s), c)){
                printf("no\n");
                destroy(s);
                return 0;
            }
        }
    }
    puts(is_empty(s) ? "yes" : "no");
    destroy(s);
    return 0;
}

额外优化建议 #

• 扩容策略优化：每次只扩容1个单位效率低，建议改为当前容量的2倍（如new_cap = s->cap * 2），减少realloc调用次数
• match()函数简化：直接判断字符配对关系，无需计算ASCII差值，逻辑更直观
• 边界检查增强：在处理右括号时先判断栈是否为空，避免空栈调用pop()引发的越界问题

内容的提问来源于stack exchange，提问作者stfp04