1

我正在用c实现一个非常简单的计算机代数系统。我的程序在一段时间后崩溃时遇到了一些问题。

这个想法是有一个像 3^(21+8^(3^100)) + 4 这样的表达式，并看到它等于 2 mod 7。我已经用 java 编写了程序，并试图将它移植到 c。

我就是这样做的：我有一个名为 expr 的结构。它可以是二进制表达式或原子 int

struct expr
{
    struct expr* a;
    struct expr* b;
    char op;
    int value;
};
typedef struct expr expr;

expr* new_expr(int i)
{
    expr* e = malloc(sizeof(expr));
    e->op='i';
    e->value = i;
    return e;
}

expr* new_expr2(expr* a, expr* b, char op)
{
    expr* e = malloc(sizeof(expr));
    e->a=a;
    e->b=b;
    e->op=op;
    e->value = 0;
    return e;
}

void free_expr(expr* e)
{
    free_expr(e->a);
    free_expr(e->b);
    free(e);
}
/* ... other methods ... */

我怀疑（其中一个）问题是我没有在 gcd 函数中释放内存。这就是我编写 gcd 函数的方式。

expr* gcd(expr* a, expr* b)
{
    expr* t = b;
    while(!equals(b, zero))
    {
        t=b;
        b=mod(a, b);
        a=t;
    }
    return a;
}

这在java中很好用，但我不确定它是否在c中有效，因为它没有自动垃圾收集。当函数是递归的时，我不确定如何构造它。所以我想我的问题是，我应该把 free_expr 函数放在哪里？mod(a, b) 分配一个新的 expr 结构，因此它最终会创建很多永远不会被释放的 expr。我怀疑这可能是它崩溃的原因。构建这个的正确方法是什么？还是我做错了？

由于代码可维护性，我宁愿在 struct expr 中进行计算，而不是在 int 中进行计算。

谢谢你的帮助。

[编辑] 这是我的模组功能

expr* mod(expr* number, expr* modulo)
{
    expr* result;
    if(number->op=='i')
    {
        if(modulo->op=='i')
        {
            int i = (number->value)%(modulo->value);
            while(i<0)
            {
                i=i+(modulo->value);
            }
            return new_expr(i);
        }
    }
    switch(number->op)
    {
    case '+':
        result = new_expr(mod(number->a,modulo)->value+mod(number->b,modulo)->value);
        break;
    case '-':
        result = new_expr(mod(number->a,modulo)->value-mod(number->b,modulo)->value);
        break;
    case '*':
        result = new_expr(mod(number->a,modulo)->value*mod(number->b,modulo)->value);
        break;
    case '/':
        result = new_expr(mod(number->a,modulo)->value/mod(number->b,modulo)->value);
        break;
    case '^':
        result = modexpEuler(number->a,number->b, modulo);
        break;
    }
    (result->value)%=(modulo->value);
    return result;
}


expr* modexpEuler(expr* a, expr* b, expr* n)
{
if(!(a->op=='i')||!(n->op=='i'))
{
    printf("wrong input ");
    exit(0);
}

if(equals(b, one))
{
    return mod(a,n);
}
if(equals(b, zero))
{
    if(b->op=='^'){
        printf("adf %d\n",b->a->value);
        printf("asdf %d\n", b->b->value);
    }else{

        printf("asdf %c\n", b->op);
        printf("asdf %d\n", b->value);
        printf("asdf %d\n", a->value);
        printf("asdf %d\n", a->b->value);
    }
    return copy_expr(zero);
}
if(equals(mod(a, n), zero))
{
    return copy_expr(zero);
}
if(b->op == 'i')
{
    return expmod(a, b, n);
}
if(equals(gcd(a,n), one))
{
    expr* tempA = mod(a, n);
    expr* tempB = mod(b, phi(n));
    printf("trying to use euler\n");
    printf("%d\n",a->value);
    printf("%d\n",b->value);
    return modexpEuler(tempA, tempB, n);
}
else
{
    printf("gcd not 1 ");
    exit(0);
}

}

phi(n) 计算欧拉函数。

[编辑 2] 这是我的平等

int equals(expr* a, expr* b)
{
    if((a->op)!=(b->op))
    {
        return 0;
    }
    if((a->op)=='i')
    {
        return (a->value)==(b->value);
    }else{
        return equals(a->a,b->a)&&equals(a->b,b->b);
    }
}
4

3 回答 3

2

在gcd，你有三个expr*，即a, b和t。

expr* gcd(expr* a, expr* b)
{
    expr* t = b;
    while(!equals(b, zero))
    {
        t=b;
        b=mod(a, b);

现在t指向b之前指向的内容，b指向模数，并且a仍然指向它在本次迭代中进入循环体时所指向的内容。

        a=t;

现在它被覆盖并且变得无法访问。因此，释放它的正确时间将在该任务之前。在那之前你不能释放它，因为它在mod(a, b). 之后你无法释放它，因为那时你不再拥有它的句柄。

    }
    return a;
}

请注意，传入的指向结构因此在 中被销毁gcd，因此如果之后在函数之外需要它们，则应该制作（深度）副本。

段错误的直接原因可能是

void free_expr(expr* e)
{
    free_expr(e->a);
    free_expr(e->b);
    free(e);
}

那绝对需要NULL检查。照原样，您尝试free_expr(0->a)，这是未定义的行为，几乎肯定会崩溃。

于 2012-12-25T21:44:52.680 回答
1

假设 mod 正在分配一个新的 expr，那么是的，有一个泄漏。我可能会传入第三个 expr 来获取结果，而不是在 mod 中分配一个。这允许您的调用代码决定在内存方面做什么。

顺便检查一下 valgrind 可能很有用。它可以用来查找内存问题，而且它很容易用于基本的东西。

于 2012-12-25T21:39:25.523 回答
1 
typedef struct expr
{
    struct expr* a;
    struct expr* b;
    char op;
    int value;
} expr;

expr* new_expr(int i)
{
    expr* e = malloc(sizeof(expr));
    e->a=NULL                          <----
    e->b=NULL                          <----
    e->op='i';
    e->value = i;
    return e;
}

expr* new_expr2(expr* a, expr* b, char op)
{
    expr* e = malloc(sizeof(expr));
    e->a=a;
    e->b=b;
    e->op=op;
    e->value = 0;
    return e;
}

void free_expr(expr* e)
{
    if (e!=NULL) {
        free_expr(e->a);
        free_expr(e->b);
        free(e);
    }
}
/* ... other methods ... */

expr* gcd(expr* aa, expr* bb)
{
    expr *a = copy_of(aa), *b = copy_of(bb);
    expr* t = b;
    while(!equals(b, zero))
    {
        t=b;
        b=mod(a, b);
        free_expr(a);
        a=t;
    }
    free_expr(b);
    return a;
}
于 2012-12-25T21:49:11.003 回答