0

所以我有一个单链表。新项目被添加到链的前面，因此如果添加 8、4、10，则列表将为 10、4、8。无论如何，现在我正在尝试在插入完成后对列表进行排序，但我只是无法弄清楚如何遍历这些数字并按升序重新排列它们。我可能会在这里休息一下，稍后再回来，希望这能帮助我解决这个问题。

*这是一个学校项目，因此建议我使用其他容器对我的情况没有帮助，除非提供信息，因为我无法更改我正在使用的内容。

列表的布局

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++;
4

2 回答 2

4

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

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-15T17:05:15.947 回答
1

对单链表进行排序对代码来说很麻烦（除非您喜欢线性排序，例如冒泡排序或插入排序）。将内容复制到向量中，对向量进行排序，然后重建列表要简单得多。

于 2012-11-15T17:01:23.457 回答