允许在单链表 C++ 上进行合并排序时出现重复项

发布于 2024-11-05 02:59:22 字数 562 浏览 1 评论 0原文

我现在对此感到非常恼火。我正在为大学学习合并排序，并且正在经历这个合并排序我在网上找到的。但是，我似乎没有得到重复项，而且我想要重复项。其内容如下，但我已经对此进行了评论，这使得排序无法正常工作。有什么办法可以保留副本吗？如果您能让答案简单明了，我将不胜感激。谢谢

else
{
    // Both are equal.
    // Arbitraritly chose to add one of them and make
    // sure you skip both!


    if(c == NULL)
    {
        c = a;
    }
    else
    {
        c->next = a;
        c = c->next;
    }

    a = a->next;
    b = b->next;
}

原文

I'm getting really annoyed with this now. I am learning merge sort for univeristy and am going through this merge sort I found on the net. However, I seem to NOT be getting duplicates and I want duplicates. Its this bit as follows but I've commented that bit out and stuff and it made the sort not work properly. Is there any way I could keep the duplicates? I'd appreciate if you could keep the answers simple. Thank you

else
{
    // Both are equal.
    // Arbitraritly chose to add one of them and make
    // sure you skip both!


    if(c == NULL)
    {
        c = a;
    }
    else
    {
        c->next = a;
        c = c->next;
    }

    a = a->next;
    b = b->next;
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

恋你朝朝暮暮 2024-11-12 02:59:22

我认为线索就在代码中的注释中：“确保你跳过两者”。通过增加两个列表指针，您可以向输出添加一个元素，但跳过两个输入元素。所以只增加一个指针。然后，另一个元素将在下一次迭代时移至输出列表中。

回复收藏 0 原文

蓝天 2024-11-12 02:59:22

如果您想保留重复项，请将两者都添加到链表c中。现在您只需将一个（即 a 或 b）附加到链接列表中。

因此，将您的代码更改为如下所示：

temp_a_next = a->next;
temp_b_next = b->next;

if(c == NULL)
{
    c = a;
    c->next = b;
    c = b;
}
else
{
    c->next = a;
    c = a;
    c->next = b;
    c = b;
}

a = temp_a_next;
b = temp_b_next;

还要注意一点：具有重复项的排序列表的最终头将在 a 中开始，因为到该算法结束时 c 将指向列表的末尾，该算法实际上是修改 a 和 b 节点的指针（即 c > 不是一个带有新节点的新链表）。

If you want to keep the duplicates, then add both to the linked list c. Right now you're only appending one (i.e., a or b) to the linked list.

So change your code to look like this:

temp_a_next = a->next;
temp_b_next = b->next;

if(c == NULL)
{
    c = a;
    c->next = b;
    c = b;
}
else
{
    c->next = a;
    c = a;
    c->next = b;
    c = b;
}

a = temp_a_next;
b = temp_b_next;

One more note: the final head of the sorted list with duplicates will have its starting point in a, since by the end of this algorithm c will be pointing to the end of the list, and this algorithm is actually modifying the pointers of the a and b nodes (i.e., c is not a new linked list with new nodes).

回复收藏 0 原文