合并列表的合并排序

黄南

我有一个Mergesort的源代码，用于如下的无序链接列表。假设我已经完成了merge功能，并且z是哨兵钥匙。

node *mergesort(node *c)
{
    node *a, *b;
    if (c->next != z)
    {
        a = c;
        b = c->next->next->next;
        while (b != z)
        {
            c = c->next;
            b = b->next->next;
        }
        b = c->next;
        c->next = c;
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}

我对此实现有3个怀疑：

如您所见，b指向链接列表的第三个元素。我不知道为什么，因为我认为只需要b = c->next足够就可以了。
据我所知，在循环中while它还b = b->next->next继续指向c该数组之后的第四个元素。如果我写可以b = b->next吗？
据我了解的算法mergesort，它的阵列分成两个子阵a和b再归并每一个子阵列递归，但我只看到它唯一的工作与阵列b。这个实现有什么问题吗？

chqrlie

此代码中存在多个问题：

b = c->next->next->next;如果c->next->next为null，则具有未定义的行为
b = b->next->next;如果b->next为null，则具有未定义的行为
该列表之前未正确拆分b，此外c->next = c;还会创建一个循环，该循环将导致算法因无限循环而失败。

该功能需要进行实质性更改才能解决这些问题。

这是修改后的版本：

node *mergesort(node *c) {
    node *a, *b;
    /* test if list has at least 2 elements */
    if (c != z && c->next != z) {
        /* locate the middle node */
        a = b = c;
        while (b->next != z && b->next->next != z) {
            c = c->next;
            b = b->next->next;
        }
        /* split the list between c and c->next */
        b = c->next;
        c->next = z;
        /* sort both sublists and merge them */
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。