使用动态内存构建堆栈的问题 (C)

Question

我正在尝试学习数据结构，因此我做了一个练习，我们从用户那里读取一个字符串，然后我们评估该字符串，以检查括号是否格式正确，例如输入：

(()

，输出：

 no

，它们的格式不正确。尽管当我尝试运行我的代码时，它不仅给出了错误的输出，而且还向我显示了错误：

free(): invalid pointer

。我用我的代码运行了 valgrind，它向我显示：

Invalid free() ... Address.. is 12 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;
}

Answer 1

问题出在

pop()

和

destroy()

：你修改了

s->v

而不是更新了

s->sz

。将

s->v

的修改值传递给

free

导致未定义的行为，valgrind 捕获。

这里是修改版：

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

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

stack *build(void) {
    stack *new = (stack *)malloc(sizeof(*new));
    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) {
    if (s->sz == s->cap) {
        int *tmp = (int *)realloc(s->v, (s->cap + 1) * sizeof(int));
        if (tmp == NULL)
            return 0;
        s->v = tmp;
        s->cap += 1;
    }
    s->v[s->sz++] = e;
    return 1;
}

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

int pop(stack *s) {
    if (is_empty(s))
        return -1;
    else
        return s->v[--s->sz];
}

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

int match(char p1, char p2) {
#define MATCH(a, b)  if (p1 == (a)) return p2 == (b)
    MATCH( '(' , ')' );
    MATCH( '[' , ']' );
    MATCH( '{' , '}' );
    return 0;
}

int main() {
    int res = 0;
    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)) {
                res = 1;
                break;
            }
        }
    }
    if (res == 0 && !is_empty(s))
        res = 2;
    puts(res == 0 ? "yes" : "no");
    destroy(s);
    return res;
}

Answer 2

有几处错误

第一个是函数

top

应该返回最后添加的项目。此外，如果堆栈为空，您的函数实现将调用未定义的行为。

函数可以看成下面的样子

int top( stack *s, int *value ) 
{
    int success = !is_empty( s );
  
    if ( success ) *value = s->v[s->sz-1];

    return success;
}

例如像

int value;

if ( top( s, &value ) )
{
    printf( "Top value is %d\n", value );
}

函数

pop

应该什么都不返回。函数

top

提供了对栈顶元素的访问。该函数看起来像

void pop(stack *s) 
{
    if ( !is_empty(s) )
    {
        --s->sz;
    }
}

函数

destroy

应使用原始指针，因为它已在我对您上一个问题的回答中指出。

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

    *s = NULL;
}

还要注意结构类型的对象也是动态分配的。所以你也需要释放它。

函数调用像

destroy( &s );

函数匹配应该是这样的

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

main 中的 while 循环看起来像

while ((c = getchar()) != EOF && c != '\n') {
    if (c == '(' || c == '[' || c == '{')
         push(s, c);
    else if (c == ')' || c == ']' || c == '}') {
        int value;

        if ( !top( s, &value ) || !match( value, c ) )
        {
            printf("no\n");
            destroy( &s );
            return 0;
        }

        pop( s );
    }
}