合并列表的合并排序

黄南

我有一个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个怀疑:

  1. 如您所见,b指向链接列表的第三个元素。我不知道为什么,因为我认为只需要b = c->next足够就可以了。

  2. 我所知,在循环中while它还b = b->next->next继续指向c该数组之后的第四个元素如果我写可以b = b->next吗?

  3. 据我了解的算法mergesort,它的阵列分成两个子阵ab再归并每一个子阵列递归,但我只看到它唯一的工作与阵列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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档