问C中链接列表合并排序实现中丢失的节点
EN

Stack Overflow用户

提问于 2017-12-13 05:13:08

回答 3查看 267关注 0票数 1

此实现用于按升序字母顺序排列字符串。我已经包含了负责划分节点的函数。head是链接列表的首字母。

我认为mergeSort函数的工作原理是将列表划分开来。见以下输出：

Head: lady apple stone red queen
fast:
slow: stone
front: lady apple stone
back: red queen

Head: lady apple stone
fast:
slow: apple
front: lady apple
back: stone

Head: lady apple
fast: 
slow: lady
front: lady
back: apple

Head: red queen
fast:
slow: red
front: red
back: queen

它清楚地显示了初始列表，lady apple stone red queen被划分为各个节点，所有这些都得到了考虑。

当节点被比较并合并到新的列表中时，问题就出现了。例如:最初，将lady与apple进行比较。它们被合并到列表中：apple, lady。那么这个列表应该与stone合并。但是，首先，将lady与stone进行比较，而不是将apple与stone进行比较。然后生成列表：lady, stone (apple留在后面，而不是在比较中使用)。应该发生的是，将apple与stone进行比较，然后将lady与stone进行比较，然后将条目排序并相应地合并到：apple, lady, stone中。

实际的最终输出是：lady, red, stone。很明显，apple和queen在某个地方迷路了。我不知道什么是违规代码。

void mergeSort(Node *head) {

    Node *front = NULL, *back = NULL, *fast, *slow;

    if(head == NULL || head->next == NULL)
        return;

    ...

    mergeSort(front);
    mergeSort(back);

    head = mergeLists(front, back);

}

merge

linked-list

sorting

云联络中心6.1折起

灵活稳定的一体化云联络中心，助力快速搭建集电话、在线交流、音视频通话为一体的客户联络平台

回答 3

Stack Overflow用户

回答已采纳

发布于 2017-12-13 05:58:30

你的代码几乎是完美的。您正在合并两个列表并将其返回给head。但是，您不能将确切的head返回到以前的mergeSort调用。

Node* mergeSort(Node *head) {

    Node *front = NULL, *back = NULL, *fast, *slow;

    if(head == NULL || head->next == NULL)
        return head; // return head
    ...

    front = mergeSort(front); // save it to front
    back = mergeSort(back); // save it to back

    head = mergeLists(front, back); // save it to head
    return head; // return head
}

在调用mergeSort的主函数中，使用head = mergeSort(head)。代码现在应该起作用了。

票数 2

Stack Overflow用户

发布于 2017-12-13 05:29:03

一个更容易(而且可能更有效，尤其是对于大列表)的方法是首先将链接列表转换为数组。请考虑以下代码：

char ** arr;
int size=getLinkedListSize(head);
arr = malloc(sizeof(*arr)*size);
linkedList2Array(head, arr);
mergeSort(arr, size);
array2LinkedList(arr, size, head);

注意，我使用的是char **类型。点(合)是指向链接列表中的数据。如果数据比简单的字符或ints更复杂，则可以避免不必要的数据复制。

这是更容易写，即使它有一些样板，它不影响任何事情。函数(您必须编写) getLinkedListSize、linkedList2Array和array2LinkedList都可以具有O(n)的复杂性，而mergeSort无论做什么都是O(n*log )。此外，要考虑到此方法对缓存更友好。

唯一的缺点是，它需要更多的内存，但不是太多。数组的最大大小将与列表相同。

我提到的三个函数编写起来很简单。下面是其中的两个：

int getLinkedListSize(Node * head)
{
    int ret=0;
    while(head) {
        ret++;
        head=head->next;
    }
    return ret;
}

void linkedList2Array(Node * head, char ** arr)
{
    int index=0;
    while(head) {
        arr[index++]=&head->data;
        head=head->next;
    }
}

票数 1

Stack Overflow用户

发布于 2017-12-13 07:12:53

不需要慢/快方法(Floyds algoritm)。它也是计数器-effective:排序将总是采取N个日志(N)操作，即使是在排序列表上。

您可以利用现有的订单，只需删除无序元素，并保留其余的元素。然后(递归)对无序部分进行排序，并合并这两个部分。

struct list {
        struct list *next;
        char* data;
        };

#define COMPARE(a,b) strcmp((a),(b))

struct list *splitmerge(struct list *org)
{
struct list *rest ,*this, **pp;

if(!org|| !org->next) return org;

        /* Split off out-of-order nodes*/
rest = NULL;
for (this = org; this;  ){
        struct list* next;
        if(!this->next)break;

        next = this->next;
        if(COMPARE( this->data,  next->data) <= 0) {
                this= next;continue;
                }
                /* Cut next out of the chain */
        this->next = next->next;
        next->next = rest;
        rest = next;
        }

        /* At this point, org is guaranteed to be sorted
        ** rest is not.
         */


        /* Order the trash */
rest = splitmerge(rest);


        /* Merge with the trash */
this=NULL;
for(pp = &this; org && rest; pp = &(*pp)->next ) {
        if(COMPARE( org->data, rest->data) <= 0) {
                *pp = org; org=org->next;
                }
        else    {
                *pp = rest; rest=rest->next;
                }
        }
*pp = (org) ? org : rest;

return this;
}