logo标签列表

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

clinked-listmergesort
3
在一个双向链表的实现中，我使用了典型的数据结构：
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 时，我可以对列表进行排序并遍历整个列表来实现，但我想知道是否有更好的方法。

我成功地使用了循环列表来解决问题，但我想避免改变程序的结构。

归并排序通过将列表分割，但将所有术语放在同一侧并保持顺序来工作，然后切换侧面并开始将术语提供给另一侧。然后合并两侧，并重复此过程，直到将列表拆分为一个列表。但是，在这里，您将每个节点分配给不同的侧面...您正在混淆列表...根本没有排序...在合并阶段进行的所有排序都在拆分部分中被破坏。 - Luis Colorado
3个回答
3
您的算法在每个步骤中通过递归在merge函数中使用O（N）堆栈空间。使用这种方法，跟踪tail节点将非常繁琐。您可以简单地扫描列表以查找并更新linklist_sort中的list结构中的tail节点。此额外步骤不会改变排序操作的复杂度。您可以通过从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函数，并且在排序期间不更新后向指针，因为您可以在最后一次扫描期间重新链接整个列表。这最后一次扫描会更长，缓存效率较低，但仍应更有效率且减少错误发生的可能性。
3
使用自底向上的归并排序算法对链表进行排序比使用扫描来分割链表的方法更快。参考链接：https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists - rcgldr
@rcgldr：当然是个好点子！自底向上的归并排序应该更有效率，因为没有扫描来分割列表，而且也更加缓存友好。通过与尾节点而不是NULL进行比较来避免分割列表将有所帮助，这需要跟踪末尾节点，但可以节省最后的扫描。 - chqrlie
使用带有虚拟节点的循环列表意味着在任何运行之前和之后始终存在一个节点。如果列表本身从未被分割，则合并通过与指针参数进行比较来检查运行结束：（第一次运行的开始，第一次运行的结束==第二次运行的开始，第二次运行的结束）。 - rcgldr
对于使用指针数组的自底向上归并排序，第一次运行的开始=当前数组元素，第一次运行的结束==第二次运行的开始=第一个非空数组元素之前的元素，第二次运行的结束==第二个非空数组元素之前或者是指向列表末尾的本地指针。这在将指向运行的数组合并为单个运行时是一个主要问题。需要意识到最右边的运行在array [0]处，并且最左边的运行在array [max used]处（数组索引越高，列表中的位置就越靠左）。 - rcgldr
1

一种选项是将节点视为单个列表节点进行归并排序，然后在完成时进行一次遍历以设置前一个指针，并更新尾指针。

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

将struct node更改为：

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。

谢谢，我非常喜欢虚拟节点的想法，这是一个最优解，但我看到了一个问题：你总是需要将比较函数传递给push、pop等函数，当然你可以传递一个虚拟比较函数，但我更喜欢保持API不变。再次感谢！ - David Ranieri
另一方面，我可以将比较函数传递给构造函数，并保持其余API不变，是的，绝对是一个非常好的想法。 - David Ranieri
@DavidRanieri - 为什么push和pop需要比较函数？ - rcgldr
...小于或等于第二次运行的元素... - David Ranieri
@DavidRanieri - 我不明白，您是否会使用pop和push作为在排序期间重新排列节点的方法？如果是这样，请注意，在任何节点重新排列之前都会进行比较。 - rcgldr
1

我并不是提供关于算法大O符号的深度分析的最佳人选。无论如何，回答一个已经被接受的“典范”答案的问题是很好的，因为有可能在没有太大压力的情况下探索替代解决方案。
即使如此，这还是很有趣的，因为你会发现，所分析的解决方案并不比问题中提出的当前解决方案更好。

该策略的起点是想知道是否可以在不颠覆代码的情况下跟踪候选尾元素。主要候选者是决定排序链表中节点顺序的函数: merge()函数。
现在，由于在比较后我们决定哪个节点将首先出现在排序列表中，因此我们将有一个较接近尾部的"输家"。因此，在每一步进一步与当前尾元素进行比较时，最终我们将能够使用"失败者中的失败者"更新tail元素。
合并函数将具有附加的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;
    }
}

除了在“传播”tail双指针参数通过merge_sort()和linklist_sort()函数外，代码不需要进行更改：

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个“简单步骤”），我们必须进行N*logN次比较，涉及调用函数。 这使得线性搜索仍然是更好的选择。
1
写这篇分析对我来说非常有教育意义。不要因为我付出了很多努力却得到了次优解而对我太苛刻哦。 ;) - Roberto Caboni
1
太好了，Roberto，谢谢！它像魔法一样运行。 - David Ranieri
这使得线性搜索仍然是更好的选择。你说得对，线性搜索在处理10万条记录时少了几毫秒的时间。 - David Ranieri
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接