按升序对链表进行排序C++

所以我有一个单独的链表。新项目被添加到链的前端，所以如果你添加了8,4,10，那么列表将是10,4,8。无论如何，现在我想在插入完成后对列表进行排序，除非我无法弄清楚如何循环这些数字并按升序重新排列它们。我可能会在这里休息一下，稍微回来，希望这会帮助我弄清楚这一点。按升序对链表进行排序C++

*这是一个学校项目，所以建议我使用其他容器在我的情况下没有帮助，除了信息丰富，因为我无法改变我正在使用的内容。

布局列表

struct Node 
    { 
     int Item;  // User data item 
     Node * Succ; // Link to the node's successor 
    }; 

unsigned Num //number of items in the list 
Node * Head //pointer to the first node

我的插入函数看起来像这样

Node * newOne; 
newOne = new (nothrow) Node; 
newOne->Item = X; 
newOne->Succ = NULL; 

if(Head == NULL) 
{ 
     Head = newOne; 
} 
else 
{ 
     newOne->Succ = Head; 
     Head = newOne; 
} 
Num++;

来源

2012-11-15 sharkman

该作业还有其他限制吗？你可以将内容复制到另一个容器进行分类吗？ – Chad

这真的很难。我怀疑即使在休息之后，正确的解决方案也会来临（尽管你可能是一个天才，谁知道呢）。看看这里的最佳解决方案http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html – john

也许你应该在插入时对它进行排序？即把元素放在正确的位置... – Caribou

这可以通过两种方式完成，我不会发布代码，但希望这会对您有所帮助。

1插入

这涉及以升序总是添加元素中排列按升序排列。例如，如果链接列表是

  | 1 |

，并添加5新的链接列表是

  |1|--->|5|

，如果你加3下一个应该是

  |1| ---> |3| ----> |5|

这涉及到的比较直到你找到正确的位置为止的新元素。

2.等到所有元素都插入后，按升序排列。

这将涉及使用排序算法，如合并排序，插入排序，冒泡排序等链接列表的元素。

完成数字排序后，按正确的顺序重写链接列表。

实施例：

如果链接列表包含

 3 2 5 1 6

通过链路列表通过算法

1 2 3 5 6 (stored in an array)

排序现在环路之后并替换以正确的顺序的元素。

要小心如果节点包含其他元素，那些其他元素也需要被替换。

注意：这需要额外的内存，另一种方式是交换需要更长时间的节点。除非链接列表包含大量节点（从而使内存很重要）或者具有其他元素，否则使用数组会更简单。

来源

2012-11-15 17:05:15

谢谢，这很有道理。我结束了方法2，因为没有其他信息除了该int。所以我做了一个矢量，对它进行排序，然后根据矢量的顺序更新节点！谢谢！ – sharkman

排序单链表是讨厌的代码（除非你喜欢的线性排序，如冒泡排序或插入排序）。将内容复制到矢量中，对矢量进行排序，然后重新构建列表就简单多了。

来源

2012-11-15 17:01:23

按升序对链表进行排序C++

回答

相关问题