0

C++ を使用してリンク リストを反転し、反転したリストを出力しようとしています。

例: 元のリストは復帰後 1->2->3 です: 3->2->1

しかし、反転した連結リストを印刷しようとすると、3->2->1 が 3<->2 のような循環連結リストになりました。

以下は私のコードです：

#include <iostream>
#include <sstream>
using namespace std;
class List{
public:
    int value;
    List *next;
    List(int);
    List(int, List *);
};

List::List(int v){
    value = v;
    next = NULL;
}

List::List(int v, List *ne){
    value = v;
    next = ne;
}

string IntToString(int val){
    stringstream temp;
    temp<<val;
    return temp.str();
}

void print(List *l){
    string output= "";
    while(l->next != NULL){
        output+=(IntToString(l->value)+"-->");
        l = l->next;
    }
    output+=(IntToString(l->value)+"-->NULL");
    cout<<output<<endl;
}

List reverse(List L){
    if(L.next == NULL) return L;
    List remain = reverse(*(L.next));
    List *current = &remain;
    while(current->next != NULL)
        current = (current->next);
    L.next = NULL;
    current->next = &L;
    //print(remain);
    return remain;
}

List copy(List l){
    return l;
}

int main() {
    List L3(3);
    List L2(2, &L3);
    List L1(1, &L2);
    List L4 = reverse(L1);
    print(&L4);
    return 0;
}

なぜこれが起こるのか誰か教えてもらえますか？どうもありがとう！

4

3 に答える 3

0

関数を見るだけで、reverse()と呼ばれるスタック上にオブジェクトを作成し、remainこれをリストに挿入します。これは機能しません。関数から戻ると、このオブジェクトはスコープ外になります（元のオブジェクトにmain()も同じ問題がありますが、離れた後にそれらを使用しようとはしませんmain()）。また、reverse()関数は線形である必要がありますが、2次のパフォーマンスを持っているようです。私はこのような何かがトリックをするだろうと思います：

List* reverse(List* head) {
    List* tail(0);
    while (head) {
        List* tmp(head);
        head = head->next;
        tmp->next = tail;
        tail = tmp;
    }
    return tail;
}

上記の実装は、再帰も回避します。

于 2012-09-03T05:29:01.020 に答える
0

listまず、ポインタを含む aanother listは概念的に間違っていることを指摘したいと思います。

リスト ノード クラスを個別に作成します。

struct ListNode {
    int value;
    Node *next;
};

その後、あなたListは、

class List {
    ...
    ListNode *head;
    ...
};

では逆走です。このメソッドではList reverse( List L )、L は単なるローカル変数です。の後に範囲外になります。

    return remain;
} // Here the scope of L ends

したがって、値が L の位置である aListを返すことは論理的に正しくありません。next

current->next = &L;
return remain; // remain is equal to *current and current->next = &L

これにより、実装で未定義の動作が発生します。

編集: 自由な時間があるので、この実装を思いつきました。呼び出された元のリストを変更しますが、同じアルゴリズムを使用します。

于 2012-09-03T06:05:24.313 に答える
0

逆アルゴリズムは正しいと思いますremainが、ローカル変数であり、戻り後に無効になるため、L4 には無効なポインターが含まれます。の署名reverse()を take と return に変更しますList *。

リスト *reverse(リスト *L){
    if(L->next == NULL) L を返します。
    List *remain = reverse(L->next);
    リスト *現在 = 残ります。
    while(現在->次!= NULL)
        現在 = (現在->次);
    L->next = NULL;
    現在 -> 次 = L;
    //印刷（残り）;
    戻ります。
}
于 2012-09-03T02:27:25.487 に答える