c - リンクリスト全体を解放しますが、このアルゴリズムは正しいですか？

Question

これは可能ですか？それとも、失われたリストがありますか？原因動作しているか確認できません

void FreeRecurs(struct nodeTag *pFirst)
{
    if(pFirst != NULL)
    {   
            FreeRecurs(pFirst -> pNext);
            free(pFirst);
    }
}

Answer 1

これは機能しますが、長いリストでは、再帰が多く、末尾再帰を使用していないため、スタックオーバーフローが発生する可能性があります。反復バージョンに移動します：

• 現在のノードがNULLでない場合：
  • 次のノードへのポインタを格納します。
  • 現在のノードを解放します。
  • 解放する直前に保存したポインタを使用して、次のノードでの作業を開始します。

Answer 2

理論的にはこれで問題ありませんが、末尾再帰にすることで大幅に改善できます。

void FreeRecurs(struct nodeTag *pFirst)
{
    if(pFirst != NULL)
    {   
            struct nodeTag* const next = pFirst->pNext;
            free(pFirst);
            FreeRecurs(next);
    }
}

FreeRecurs(next)これが関数の最後のステートメントであることに注意してください。コンパイラはこれを認識し、コードはより高速に実行され、スタックを破壊するリスクはありません。

それ以外に、メモリを失っているかどうかわからないときはいつでも、でvalgrind（特にでmassif）プログラムを実行でき、メモリが失われたかどうかがわかります。

Answer 3

このアルゴリズムは機能します。valgrindとは言うものの、コードで何が起こっているのかを正確に監視するなどのツールの使用方法を学ぶ必要がありgdbます。そうすれば、コードが機能しているかどうかを判断できます。

Answer 4

私は再帰を使用せず、代わりに次のようなものを使用します。

void FreeRecurs(struct nodeTag *pFirst)
{
    struct nodeTag *aux = NULL;
    while (pFirst != NULL)
    {   
        aux = pFirst;
        pFirst = pFirst -> pNext;
        free(aux);
    }
}

再帰はスタックオーバーフローにつながり、実際には、各関数呼び出しには実際には何もせずに作成された新しい呼び出しスタックがあるため、遅くなります。