合并排序后的更新列表->尾部

Question

在双向链表的实现中，我使用的是典型结构：

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};

我还将在O（1）时间插入列表的末尾，因此我还有另一个struct存储了head和tail：

struct linklist
{
    struct node *head;
    struct node *tail;
    size_t size;
};

程序对于所有插入和删除操作均按预期方式工作，但是排序功能存在问题，我使用的是归并排序算法，因为我知道它是对列表进行排序最有效或最有效的方法之一，该算法效果很好：

static struct node *split(struct node *head)
{
    struct node *fast = head;
    struct node *slow = head;

    while ((fast->next != NULL) && (fast->next->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    struct node *temp = slow->next;

    slow->next = NULL;
    return temp;
}

static struct node *merge(struct node *first, struct node *second, int (*comp)(const void *, const void *))
{
    if (first == NULL)
    {
        return second;
    }
    if (second == NULL)
    {
        return first;
    }
    if (comp(first->data, second->data) < 0)
    {
        first->next = merge(first->next, second, comp);
        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else
    {
        second->next = merge(first, second->next, comp);
        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}

static struct node *merge_sort(struct node *head, int (*comp)(const void *, const void *))
{
    if ((head == NULL) || (head->next == NULL))
    {
        return head;
    }

    struct node *second = split(head);

    head = merge_sort(head, comp);
    second = merge_sort(second, comp);
    return merge(head, second, comp);
}

但是我不知道如何更新list->tail的地址：

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *))
{
    list->head = merge_sort(list->head, comp);
    // list->tail is no longer valid at this point
}

确定我可以在订购后遍历整个列表，并通过蛮力更新list->tail，但我想知道是否有更完美的方法。

我设法使用循环列表解决了问题，但我想避免更改程序的结构。

Answer 1

您的算法通过对每个步骤递归merge函数来使用O（N）堆栈空间。使用这种方法，跟踪tail节点将非常麻烦。您只需扫描列表即可找到并更新list中的linklist_sort结构。这个额外的步骤不会改变分类操作的复杂性。您可以通过从link->tail的当前值开始节省一些时间：如果列表已经排序，循环将立即停止。

这里是修改后的版本：

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

使用合并排序对链表进行排序仅应使用O（log（N））空间和O（N log（N））时间。

以下是一些改进此算法的想法：

• 由于您知道列表的长度，因此无需扫描整个列表进行拆分。您可以将长度与列表指针一起传递，并使用它来确定拆分位置，并且只扫描列表的一半。

• 如果将merge转换为非递归版本，则可以跟踪合并阶段的最后一个节点，并更新作为参数传递的指针struct node **tailp指向最后一个节点。这将保存上一次扫描，并且删除递归将降低空间复杂度。基准测试将告诉我们这是否会提高效率尚不明显。

• 根据经验，使用指向列表节点的N个指针的辅助数组，可以更有效地实现对链接列表的单独排序和双向的链接。您将对该数组进行排序，然后根据排序后的数组的顺序重新链接节点。额外的要求是O（N）大小。

这里是使用列表长度和非递归merge的修改版本：

struct node {
    void *data;
    struct node *prev;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
    size_t size;
};

static struct node *split(struct node *head, size_t pos) {
    struct node *slow = head;

    while (pos-- > 1) {
        slow = slow->next;
    }
    struct node *temp = slow->next;
    slow->next = NULL;
    return temp;
}

static struct node *merge(struct node *first, struct node *second,
                          int (*comp)(const void *, const void *))
{
    struct node *head = NULL;
    struct node *prev = NULL;
    struct node **linkp = &head;

    for (;;) {
        if (first == NULL) {
            second->prev = prev;
            *linkp = second;
            break;
        }
        if (second == NULL) {
            first->prev = prev;
            *linkp = first;
            break;
        }
        if (comp(first->data, second->data)) <= 0 {
            first->prev = prev;
            prev = *linkp = first;
            linkp = &first->next;
        } else {
            second->prev = prev;
            prev = *linkp = second;
            linkp = &second->next;
        }
    }
    return head;
}

static struct node *merge_sort(struct node *head, size_t size,
                               int (*comp)(const void *, const void *))
{
    if (size < 2) {
        return head;
    }

    struct node *second = split(head, size / 2);

    head = merge_sort(head, size / 2, comp);
    second = merge_sort(second, size - size / 2, comp);
    return merge(head, second, comp);
}

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp, list->size);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

Answer 2

[一种选择是将排序的节点视为单个列表节点，然后对其进行排序，然后设置一次以设置先前的指针，并更新尾指针。

另一个选项将使用类似于C ++ std :: list和std :: list :: sort的东西。使用圆形双向链表。有一个虚拟节点，将“下一个”用作“头”，将“上一个”用作“尾”。合并排序和合并的参数是迭代器或指针，并且仅用于跟踪运行边界，因为通过在原始列表中移动节点来合并节点。合并功能使用std :: list :: splice将节点从第二次运行合并到第一次运行。逻辑是，如果第一个运行元素小于或等于第二个运行元素，则只需将迭代器或指针前进到第一个运行，否则从第二个运行中删除该节点并将其插入到第一个运行中的当前节点之前。如果涉及删除+插入步骤，这将自动更新虚拟节点中的头和尾指针。

将结构节点更改为：

struct node
{
    struct node *next;           // used as head for dummy node
    struct node *prev;           // used as tail for dummy node
    void *data;
};

会更加通用。

由于创建列表时分配了虚拟节点，所以开始==虚拟->下一个，最后==虚拟->上一个，结束==虚拟。