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;
    }
}

如果列表无限增加或错误来自 Print 函数，我会感到困惑......对不起，也许是虚拟错误。谢谢。

4

3 回答 3

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

由于您在第一次通话中覆盖tmp->next，您的第二次通话实际上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。

请参阅我的ideone paste以获取带有示例的更正版本。

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

您未能正确链接两个现有节点。看看你的代码片段：

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

例如，如果您有此列表：

头 -> 5

并且您想插入一个编号为 4 的节点，您将拥有：

头 -> 5 <- tmp 新节点 -> 4

使用 tmp->SetNext(newNode)

头（和 tmp）-> 5 -> 4 <- newNode

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

头（和 tmp）-> 5 -> 4 <- newNode

因此，任何遍历列表的尝试都将导致无限循环：

5 4 4 4 4 ......永远

于 2012-09-12T04:35:42.170 回答
0

你的问题是这两行：

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

你应该扭转它们。现在，您设置 tmp.next = newNode，然后设置 newNode.next = tmp.next (= newNode)，因此 newNode 指向自身。然后遍历 newNode 会导致无限循环。

于 2012-09-12T04:24:53.913 回答