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

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) 堆栈 space。使用这种方法，跟踪 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)) space 和 O(N log(N)) 次。

这里有一些改进这个算法的想法：

因为你知道列表的长度，所以你不需要扫描整个列表来进行拆分。您可以将长度与列表指针一起传递，并使用它来确定拆分位置并只扫描列表的一半。
如果将merge转换为非递归版本，则可以跟踪合并阶段的最后一个节点并更新作为参数传递的指针struct node **tailp指向最后一个节点。这将保存最后一次扫描，并且删除递归将降低 space 复杂性。这是否会提高效率并不明显，基准测试会告诉我们。
根据经验，使用辅助数组 N 指向列表节点的指针，可以更有效地对链表进行单链排序和双链排序。您将对该数组进行排序，并根据排序数组的顺序重新链接节点。额外的要求是 O(N) size.

这是使用列表长度和非递归 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 函数，并且在排序期间不更新后向指针，因为您可以在上次扫描期间重新链接整个列表。最后一次扫描的时间会更长，对缓存的友好性也会降低，但它仍然应该更高效且更不容易出错。

Answer 2

一个选项是对节点进行合并排序，就好像它们是单个列表节点一样，然后在完成后一次性通过以设置先前的指针，并更新尾指针。

另一个选项将使用类似于 C++ std::list 和 std::list::sort 的东西。使用循环双向链表。有一个虚拟节点使用 "next" 作为 "head" 和 "prev" 作为 "tail"。合并排序和合并的参数是迭代器或指针，仅用于跟踪运行边界，因为节点是通过在原始列表中移动它们来合并的。 merge 函数使用 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;
};

会更通用一些。

由于在创建列表时分配了虚拟节点，因此begin == dummy->next，last == dummy-> prev，end == dummy。

Answer 3

我不是提供有关算法 Big-O 符号的深入分析的最佳人选。无论如何，用一个已经被接受的 "canonic" 答案来回答问题是很好的，因为可以在没有太大压力的情况下探索替代解决方案。
这很有趣，即使如您所见，分析的解决方案并不比问题中提出的当前解决方案更好。

该策略首先想知道是否有可能在不颠倒代码的情况下跟踪候选尾元素。主要候选者是决定排序列表中节点顺序的函数：merge() 函数。

现在，由于在比较之后我们决定哪个节点将在排序列表中排在第一位，因此我们将有一个更接近尾部的 "loser"。因此，通过与每个步骤的当前尾元素进一步比较，最终我们将能够用 "loser of the losers".[ 更新 tail 元素。 =24=]

合并函数将有额外的struct node **tail参数（双指针是必需的，因为我们将更改列表tail字段就地:

static struct node *merge(struct node *first, struct node *second, struct node **tail, 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, tail, comp);

        /* The 'second' node is the "loser". Let's compare current 'tail' 
           with it, and in case it loses again, let's update  'tail'.      */
        if( comp(second->data, (*tail)->data) > 0)
            *tail = second;
        /******************************************************************/

        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else
    {
        second->next = merge(first, second->next, tail, comp);

        /* The 'first' node is the "loser". Let's compare current 'tail' 
           with it, and in case it loses again, let's update  'tail'.      */
        if( comp(first->data, (*tail)->data) > 0)
            *tail = first;
        /******************************************************************/

        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}

除了通过 merge_sort() 和 linklist_sort() 函数对 tail 双指针参数的 "propagation" 进行更改外，无需对代码进行更多更改：

static struct node *merge_sort(struct node *head, struct node **tail, int (*comp)(const void *, const void *));

void linklist_sort(List_t *list, int (*comp)(const void *, const void *))
{
    list->head = merge_sort(list->head, &(list->tail), comp);
}

测试

为了测试这个修改，我必须编写一个基本的 insert() 函数，一个旨在按降序获取排序列表的 compare() 函数，以及一个 printList() 实用程序。然后我写了一个主程序来测试所有的东西。

我做了几个测试；这里我只举一个例子，其中我省略了问题中和上面这个答案中出现的功能：

#include <stdio.h>

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

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

void insert(List_t *list, int data)
{
    Node_t * newnode = (Node_t *) malloc(sizeof(Node_t) );
    int * newdata = (int *) malloc(sizeof(int));
    *newdata = data;

    newnode->data = newdata;
    newnode->prev = list->tail;
    newnode->next = NULL;
    if(list->tail)
        list->tail->next = newnode;

    list->tail = newnode;

    if( list->size++ == 0 )
        list->head = newnode;   
}

int compare(const void *left, const void *right)
{
    if(!left && !right)
        return 0;

    if(!left && right)
        return 1;
    if(left && !right)
        return -1;

    int lInt = (int)*((int *)left), rInt = (int)*((int *)right);

    return (rInt-lInt); 
}

void printList( List_t *l)
{
    for(Node_t *n = l->head; n != NULL; n = n->next )
    {
        printf( " %d ->", *((int*)n->data));
    }
    printf( " NULL (tail=%d)\n", *((int*)l->tail->data));
}


int main(void)
{
  List_t l = { 0 };

  insert( &l, 5 );
  insert( &l, 3 );
  insert( &l, 15 );
  insert( &l, 11 );
  insert( &l, 2 );
  insert( &l, 66 );
  insert( &l, 77 );
  insert( &l, 4 );
  insert( &l, 13 );
  insert( &l, 9 );
  insert( &l, 23 );

  printList( &l );

  linklist_sort( &l, compare );

  printList( &l );

  /* Free-list utilities omitted */

  return 0;
}

在这个特定的测试中，我得到了以下输出：

 5 -> 3 -> 15 -> 11 -> 2 -> 66 -> 77 -> 4 -> 13 -> 9 -> 23 -> NULL (tail=23)
 77 -> 66 -> 23 -> 15 -> 13 -> 11 -> 9 -> 5 -> 4 -> 3 -> 2 -> NULL (tail=2)

结论

好消息是，理论上我们仍然有一个算法，在最坏的情况下，时间复杂度为 O(N log(N))。
坏消息是，为了避免在链表 (N "simple steps") 中进行线性搜索，我们必须进行 N*logN 比较，涉及调用函数。 这使得线性搜索仍然是更好的选择。

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

Doubly linked list - Update list->tail after a merge sort

c

mergesort

linked-list

测试

结论