1

リンクされたリストを逆にしようとしていましたが、次の関数を実行するたびに最後の要素しか取得しません。たとえば、リストに以前の 11、12、13 が含まれていたとします。関数を実行した後、13しか含まれていません。私のコードのバグを親切に指摘してください

void reverselist() {
    struct node *a, *b, *c;
    a = NULL;
    b = c = start;

    while (c != NULL) {
        c = b->next;
        b->next = a;
        a = b;
        b = c;
    }
    start = c;
}
4

4 に答える 4

1
  1. あなたのループガードはstartがnullであることを保証しませんか？
  2. startを使用してリストの最初の要素を識別していない場合でも、使用している変数は、最初の要素（現在は最後）を指しています。
于 2012-07-17T11:30:37.910 に答える
0 
// Node には、次に呼び出される Node* があると想定する必要があります。
// リスト内の次の項目を指す
// 成功した場合は反転したリストの先頭を返し、それ以外の場合は NULL / 0 を返します
Node *reverse( ノード *ヘッド )
{
    ノード *prev = NULL;

    while( 頭 != NULL )
    {
        // 破棄するので次に保存
        ノード *next = head->next;

        // 次と前が逆になりました
        head->next = prev;

        // リストを進めます
        前 = 頭;
        頭 = 次;
    }
    前に戻る;
}
于 2012-07-17T12:01:39.177 に答える
0

c はヘルパー ポインターです。

void reverselist()
{
    struct node *a, *b, *c;
    a=NULL;
    b=start;
    while(b!=NULL)
    {
        c=b->next
        b->next=a;
        a=b
        b=c
    }
    start=a;
}
于 2012-07-17T14:24:31.353 に答える
0

prepend 関数を作成し、次のようにします。

struct node* prepend(struct node* root, int value)
{
    struct node* new_root = malloc(sizeof(struct node));
    new_root->next = root;
    return new_root;
}

struct node* reverselist(struct node* inlist)
{
    struct node* outlist = NULL;

    while(inlist != NULL) {
        struct node* new_root = prepend(outlist, inlist->value);
        outlist = new_root;
        inlist = inlist->next;
    }

    return outlist;
}

これをテストしていませんが、そのアイデアを理解していると思います。何も説明していない単なる変数名かもしれませんが、このアプローチはよりクリーンで、実際に何が起こるかを理解しやすいと思います。

編集：

なぜインプレースで行わないのかという質問があったので、ここで答えます。

  1. その場でできますか？元のリストを保持しないでよろしいですか?
  2. インプレースで行う必要がありますか？malloc には時間がかかりますか? これはコードのパフォーマンス上重要な部分ですか? 注意: 時期尚早の最適化は諸悪の根源です。

つまり、これは最初の実装です。動作するはずですが、最適化されていません。また、この実装が考えられる前にテストを作成する必要があります。テストに合格するまで、この低速で最適化されていない実装を保持する必要があります。使用するには遅すぎることが証明されます!

単体テストに合格し、実装が遅いことが証明された場合は、コードを最適化し、テストを変更せずにテストに合格することを確認する必要があります。

また、答えであるインプレース操作が必要ですか？元に戻す前にメモリを割り当てるのはどうですか。この方法では、割り当て呼び出しは 1 つだけで、うまくいけばパフォーマンスが大幅に向上するはずです。

このようにして、誰もが満足し、コードがよりきれいになり、ボブおじさんがショットガンを持ってドアに現れるリスクを回避できます。

于 2012-07-17T11:41:52.083 に答える