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 ... */

問題 (の 1 つ) は、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 が作成されます。これがクラッシュの原因ではないかと思います。これを構造化する正しい方法は何でしょうか? それとも、私はこれをすべて間違っていますか？

コードの保守性のために、int よりも struct expr で計算を行う方がはるかに望ましいです。

助けてくれてありがとう。

[編集] これは私の mod 関数です

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) は、オイラーの totient 関数を計算します。

[編集 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、 と の 3 つがexpr*ありa, bますt。

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

今は前に指しtていたものを指し、モジュラスを指していて、ループ本体がこの繰り返しに入ったときに指していたものをまだ指しています。bba

        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 を割り当てていると仮定すると、はい、リークがあります。mod で 1 つを割り当てるよりも、おそらく 3 番目の expr を渡して結果を取得します。これにより、呼び出し元のコードでメモリに関する処理を決定できます。

ちなみに、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 に答える