c - 双向链表 - 合并排序后更新列表->尾部

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 节点将非常麻烦。您可以简单地扫描列表以找到它并更新 linklist_sort 中的 list 结构。这个额外的步骤不会改变排序操作的复杂性。从 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;
    }
}

请注意，您还可以简化 merge 函数，并且在排序期间不更新后向指针，因为您可以在上次扫描期间重新链接整个列表。最后一次扫描的时间会更长，对缓存的友好性也会降低，但它仍然应该更高效且更不容易出错。