2

我在为链表实现合并排序时遇到问题，特别是合并部分。我正在尝试对包含字符串的链接列表进行排序并按字母顺序对其进行排序。但是，我的合并代码有时会由于某些原因跳过指针，具体取决于原始列表的顺序。目前我有：

public node merge(node left, node right){
        node result = null;

        if(left == null){
            return right;
        }else if(right == null){
            return left;
        }   

        // The data in the node are stored as strings.
        // Compare if the string in the left node is less that 
        // the string in the right.
        if(left.info.compareTo(right.info) < 0){
            result = left;
            result.next = merge(left.next, right);
        }else{
            result = right;
            result.next = merge(left, right.next);
        }

        return result;
    }

如果我有一个包含例如 f->t->c->t->h 的列表，我的合并将返回 h->t->t，其中缺少指针。但是，如果我的列表由 b->a->t->t->c 组成，那么它会按字母顺序正确显示，a->b->c->t->t，并且不会丢失任何指针。

任何帮助表示赞赏。

谢谢。

4

2 回答 2

2

我认为这是因为您持有指向左右的旧指针，这可能不再是子列表的头。

改变

 mergeSort(left);
 mergeSort(right);

到

 left = mergeSort(left);
 right = mergeSort(right);
于 2012-04-11T10:43:23.513 回答
1

这可能不值得回答，但在这里。

弄清楚那里发生了什么有点困难，我没有注意到实现中的任何明显错误（尽管我不会在合并部分使用递归，但“迭代地”实现它更简单）。

在我看来，您需要逐步弄清楚发生了什么。如果您知道几个有效的示例和无效的示例（看起来像您这样做），请使用预期的输入直接调用每个方法。

例如，要确定您的拆分是否有效，请创建一个列表并将其传递给拆分，然后打印结果。然后在 split 创建的两个列表上调用 split 等等，以确保发生了什么。（现在是使用 JUnit 的好时机，但如果您愿意，可以“手动”完成）。

如果 split 在您能想到的几种情况下都可以正常工作，则使用两个列表调用合并例程，并以相同的方式分析结果。如果一切正常，则将一些调试输出添加到您的合并中。

基本上，独立地测试你算法的每个部分，我会更快地找出问题然后将其作为一个整体来看待。

很抱歉写了一堵文字墙但仍然没有回答问题，但这就是我尝试解决问题的方法。

于 2012-04-11T10:45:11.010 回答