排序节点（链接列表）C++

我想排序链接列表。我有一个节点称为头，它指向下一个节点，等排序节点（链接列表）C++

但是，当我尝试按它们携带的值排序节点，我得到排序工作，因为我看到它打印出的东西在if - 声明，但我没有找回链表。我哪里做错了？

Node* head; 
void sortlist(){ 

Node * runner = head; 
Node * runner2; 

for(runner = head; runner->next != NULL; runner = runner->next){ 
    for(runner2 = runner->next; runner2->next != NULL; runner2 = runner2->next){ 
     if(runner->freq < runner2->freq){ 
      cout<< runner->freq<< " is LT "<<runner2->freq<< endl; 
      Node * temp = runner; 
      runner = runner2; 
      runner2 = temp; 
     } 
    } 
} 

head = runner; 
}

我只收回第一个节点。

来源

2013-03-26 Adegoke A

'head = runner;'。我甚至不需要深入了解这是错误的。 – UmNyobe 2013-03-26 15:54:29

交换似乎工作，但我认为我只是返回错误的节点，或者我可能失去了链接？ – 2013-03-26 15:55:08

交换不起作用。你需要交换'runner-> freq'和'runner2-> freq'，而不是指针本身。另外，即使你交换了正确的东西，这个代码也不会排序。 – john 2013-03-26 15:55:53

为了交换链接列表中的两个元素，请考虑需要更改的内容。例如，为了从

Head -> First -> Second -> (NULL)

到

Head -> Second -> First -> (NULL)

你需要更新：Head.next，First.next和Second.next。在尝试交换节点时，您不会更改的任何，因此它不可能达到您期望的效果。

只需调换值（即swap(runner->freq, runner2->freq)）就会简单得多。

来源

2013-03-26 16:04:47 Useless

yup交换值是大多数情况下要走的路。 – UmNyobe 2013-03-26 16:06:08

+1用于建议交换值而不是与指针相混淆。 – 2013-03-26 16:06:54

交换值当然更容易，但如果链接列表在其节点中包含大量内存（如大型结构），则可能会影响性能。 – 2to1mux 2013-03-26 16:37:56

当runner->next == NULL;，你应该停止，这应该是最后一个元素。然后你设置head = runner;，这意味着头将永远是这个例程后的最后一个元素。此外，我不相信这种交换。

看来你隐约想要做一个insertion sort。如果你想在链表上做一个简单的排序，我建议你使用selection sort：你可以创建另一个空列表l2，并且每次从第一个列表中删除最小元素，并将其添加为l2的头部。第二个列表的代码很简单：

void prepend(Node* node, Node** list){ 
    //null checks if you want 
    node->next = *list; 
    *list=node->next; 
}

来源

2013-03-26 15:56:35 UmNyobe

排序节点（链接列表）C++

回答

相关问题