1

私は単一のリンクされたリストで作業しており、整数の値が小さいものから大きいものへと並べ替えたいと考えています。アイデアはありましたが、実行が無限ループに入り、その理由がはっきりわかりません。これは、私が使用したコードの一部です。

class Node {

    int data;
    Node* next;

public:

    Node() { };
    void SetData(int aData) { data = aData; };
    void SetNext(Node* aNext) { next = aNext; };
    int Data() { return data; };
    Node* Next() { return next; };
};

class List {

    Node *head;

public:

    List() { head = NULL; };
    void Print();
    void Append(int data);
    void Delete(int data);
};

void List::Append(int data) {

    // Create a new node
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->SetNext(NULL);

    // Create a temp pointer
    Node *tmp = head;

    if ( tmp != NULL ) {
        // Nodes already present in the list
        // Parse to end of list anytime the next data has lower value
        while ( tmp->Next() != NULL && tmp->Next()->Data() <= newNode->Data() ) {
            tmp = tmp->Next();
        }

        // Point the lower value node to the new node
        tmp->SetNext(newNode);
        newNode->SetNext(tmp->Next());
    }
    else {
        // First node in the list
        head = newNode;
    }
}

void List::Print() {

    // Temp pointer
    Node *tmp = head;

    // No nodes
    if ( tmp == NULL ) {
        cout << "EMPTY" << endl;
        return;
    }

    // One node in the list
    if ( tmp->Next() == NULL ) {
        cout << tmp->Data();
        cout << " --> ";
        cout << "NULL" << endl;
    }
    else {
        // Parse and print the list
        do {
            cout << tmp->Data();
            cout << " --> ";
            tmp = tmp->Next();
        }
        while ( tmp != NULL );

        cout << "NULL" << endl;
    }
}

リストが無限に増加するのか、それともエラーが印刷機能に起因するのか、私は混乱しています...おそらくダミーエラーで申し訳ありません。ありがとう。

4

3 に答える 3

0 
// Point the lower value node to the new node
tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());

最初の呼び出しで上書きtmp->nextするため、2 番目の呼び出しは実際にはそれ自体を指しており、サイクルを作成していますnewNode->next。newNodeこれにより、呼び出し時に無限ループが発生しますPrint;-)

解決策は、次のようなことをすることです...

Node* _next = tmp->Next();
tmp->SetNext(newNode);
newNode->SetNext(_next);

そうは言っても、あなたのコードはまだ壊れています。問題は、リストの先頭の前に配置する必要があるかどうかを確認しないことです。次のようにしてみてください。

if ( tmp ) {
    // Check whether to become new head
    if ( tmp->Data() > newNode->Data() ) {
      newNode->SetNext(tmp);
      head = newNode;
    }
    else {
      // Nodes already present in the list
      // Parse to end of list anytime the next data has lower value
      while ( tmp->Next() && tmp->Next()->Data() <= newNode->Data() ) {
          tmp = tmp->Next();
      }

      // Point the lower value node to the new node
      Node* _next = tmp->Next();
      tmp->SetNext(newNode);
      newNode->SetNext(_next);
  }
}
else {
    // First node in the list
    head = newNode;
}

補足: イニシャライザ リストを使用して、次のようなコードを書き換えることができます...

List() : head(NULL) { };

さらに、NULLが と等価である場合0、フォームX == NULLとの条件をX != NULL単にXととして単純化でき!Xます。

修正されたバージョンについては、私のアイデアの貼り付けを例とともに参照してください。

int main() {
    List l;
    l.Append(15);
    l.Append(40);
    l.Append(7);
    l.Print();
    return 0;
}

～を生み出す

7 --> 15 --> 40 --> ヌル

于 2012-09-12T04:21:08.897 に答える
0

問題は次の 2 行です。

tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());

それらを逆にする必要があります。現在、tmp.next = newNode を設定してから、newNode.next = tmp.next (= newNode) を設定しているため、newNode はそれ自体を指しています。その後、newNode を通過すると無限ループに陥ります。

于 2012-09-12T04:24:53.913 に答える
0

2 つの既存のノードを適切にリンクできません。あなたのコードのこの断片を見てください：

tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());

たとえば、次のリストがある場合:

頭 -> 5

4番のノードを挿入すると、次のようになります。

ヘッド -> 5 <- tmp newNode -> 4

tmp->SetNext(newNode) で

head (および tmp) -> 5 -> 4 <- newNode

newNode->SetNext(tmp->Next()); を使用

head (および tmp) -> 5 -> 4 <- newNode

したがって、リストを反復しようとすると、無限ループが発生します。

5 4 4 4 4 ……永遠に

于 2012-09-12T04:35:42.170 に答える