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

3 回答 3

1

您可以消除第三种情况（代码中列出的当前 else 块），并将第二种情况从 更改a > b为else- 现在它将处理任何情况 where a >= b，并且始终a位于排序列表的第一位。

于 2011-05-01T23:38:48.143 回答
1

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

于 2011-05-01T22:12:45.793 回答
1

如果要保留重复项，请将两者都添加到链接列表中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不是具有新节点的新链表）。

于 2011-05-01T22:13:10.127 回答