1

リンクリストを使用してグラフデータ構造を作成しました。このコードで：

typedef struct vertexNode *vertexPointer;
typedef struct edgeNode *edgePointer;

void freeGraph(vertexPointer); /* announce function */

struct edgeNode{
    vertexPointer connectsTo;
    edgePointer next;
};

struct vertexNode{
    int vertex;
    edgePointer next;
};

次に、A、B、C、D の 4 つのノードを持つグラフを作成します。ここで、A は B を介して D に接続し、A は C を介して D に接続します。リンクされたリストを使用すると、次のようになると思います。

グラフはどのように見えるか

最後に、freeGraph(graph) でグラフを解放しようとします。

void freeEdge(edgePointer e){
    if (e != NULL) {
        freeEdge(e->next);
        freeGraph(e->connectsTo);
        free(e);
        e = NULL;
    }
}

void freeGraph(vertexPointer v){
    if (v != NULL) {
        freeEdge(v->next);
        free(v);
        v = NULL;
    }
}

ここで、valgrind が「サイズ 4 の無効な読み取り」、「アドレス 0x41fb0d4 はサイズ 8 のブロック内の 4 バイトである」、「無効な free()」で不平を言い始めます。また、8回のmallocと9回の解放を行ったとも書かれています。

問題は、ノード D のメモリが既に解放されており、再度解放しようとしていることにあると思います。しかし、データ構造を変更せずにこれを正しく行う方法はありません。

可能であれば、データ構造を変更することなく、これらのエラーを防ぎ、グラフを正しく解放する最善の方法は何ですか? また、このコードに他に問題がある場合は、お知らせください。ありがとう！

あいさつ、セミコロン

4

5 に答える 5

2

グローバルヒープにノードとエッジを割り当てる代わりに、メモリプールに割り当てることができます。グラフを解放するには、プール全体を解放します。

于 2012-10-19T18:14:37.373 に答える
0

はい、問題は、Dが2つのパスを介して到達し、2回解放される可能性があることです。

これは2つのフェーズで実行できます。フェーズ1：到達したノードを「セット」データ構造に挿入します。フェーズ2：「セット」データ構造のノードを解放します。

データ構造を拡張する必要がある、そのセットデータ構造の可能な実装：データ構造内のすべてのノードにブールフラグを付けて、2回挿入しないようにします。すべてのノードの2番目のリンクリストには、別の「次の」ポインタを使用します。シンプルなもの。

データ構造を拡張しない別の実装：C ++ std ::set<>のようなSOmething

別の問題：Aから開始したときに、すべてのノードに到達できることを確認しますか？この問題を回避するには、作成時にすべてのノードを「セット」データ構造に挿入します（その後、マーキングは必要ありません）。

于 2012-10-19T18:13:07.780 に答える
0

これは、ここで 2 つの再帰が行われており、それらが互いに踏み合っているためです。 freeGraphD を解放するために (たとえば、B から) が 1 回呼び出され、 から への最初の呼び出しfreeGraphが戻ってきたときに、freeEdge解放を試みますv。イラストなしで下手な説明ですが、どうぞ。

「クロスオーバー」しないように1つの再帰を取り除くか、各解放の前に、そのノードが再帰の他のブランチによってすでに処理されているかどうかを確認できます。

于 2012-10-19T18:07:15.893 に答える