列表中的简单 merge_sort - 分析

Question

我写了一个简单的函数，将两个排序列表合并为一个。不幸的是，我无法得到结果，我不知道为什么。编译器不显示任何语句，并在启动函数时停止工作。看来我一切都好。请检查一下。下面显示了代码。

node list_sort (node*& h, node*& h1, node*& h2)
{
    if (h1 && h2 == NULL)
    {
        h = h1;
        return *h;
    }

    if (h2 && h1 == NULL)
    {
        h = h2;
        return* h;
    }

    if (h1 == NULL && h2== NULL)
    {
        h = NULL;
        return* h;
    }

    if (h1 && h2) // condition required to set a head
    {
        if (h1->vol > h2->vol)
            h = h2;

        else
            h = h1;
    }

    mode* p;
    p = h;

    while (h1 && h2)
    {
        if (h1->vol > h2->vol)
        {
            p->next = h2;
            h2 = h2->next;
        }

        else
        {
            p->next = h1;
            h1 = h1->next;
        }

        p = p->next;
    }

    if (h1)
    {
        while (h1)
        {
            p->next = h1;
            h1 = h1->next;
            p = p->next;
        }
    }

    else
    {
        while (h2)
        {
            p->next = h2;
            h2 = h2->next;
            p = p->next;
        }
    }

    h1 = NULL;
    h2 = NULL;
    return* h;
}

Answer 1

分配新负责人时，您还必须推进您从中获取的列表：

if (h1 && h2)
{
    if (h1->vol > h2->vol) {
        h = h2;
        h2 = h2->next;
    } else {
        h = h1;
        h1 = h1->next;
    }
}

否则你会取同一个节点，在while循环中再次说h1，但它的next指针是h1。无穷无尽...

条件if (h1 && h2) ...也是多余的，因为你之前已经处理了所有其他情况。（但在这些情况下，您也应该将源列表设置为 NULL，以维护函数的逻辑：源列表已用完，所有元素现在都在合并列表 h 中。）

请注意，您不需要最后两个 while 循环：列表的其余部分已经具有正确的连接。您只需设置：

p->next = (h1 != NULL) ? h1 : h2;
h1 = NULL;
h2 = NULL;

您函数的语义也很不寻常。如果将合并的列表头作为参考传递，则不必 return a node。你可以 return 新的负责人，但那是多余的。您可以 return 一些相关信息，比如合并列表的计数，调用者可以随意忽略这些信息。或者只是使函数 void.

您可以 return 新列表头并省略第一个参数：

node *list_merge(node *&h1, node *&h2)
{
    node *h = NULL;

    // merge list

    return h;
}

最后，当您使用指向节点指针的指针构建新列表时，您可以捕获所有特殊情况并合并 if 和 while 循环：

node *list_sort(node *&h1, node *&h2)
{
    node *h = NULL;
    node **p = &h;

    while (h1 && h2) {
        if (h1->vol > h2->vol) {
            *p = h2;
            h2 = h2->next;
        } else {
            *p = h1;
            h1 = h1->next;
        }
        p = &(*p)->next;
    }

    *p = h1 ? h1 : h2;
    h1 = NULL;
    h2 = NULL;

    return h;
}

就是这样，你可以通过使用一级间接来获得简洁性：指向 head-pointer 的指针在它的第一个赋值中填充头部 h 和新的 next 成员随时列出。

列表中的简单 merge_sort - 分析

Simple merge_sort on list - analysis

c

merge

function

list

sorted