在链表中丢失的节点在C中的合并排序实现 [英] Nodes lost in linked list merge sort implementation in C

问题描述

此实现用于按字母升序对字符串进行排序.我已经包括了负责节点划分的函数. head是链接列表的开头.

This implementation is used to order strings in ascending alphabetical order. I've included the functions responsible for the dividing of nodes. head is the head of the linked list.

我相信mergeSort函数可以按预期的方式工作以划分列表.请参见以下输出:

I believe the mergeSort function is working as intended to divide the list up. See the following ouput:

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被分为各个节点，全部被考虑.

Which clearly shows the initial list, lady apple stone red queen being divided into individual nodes, all accounted for.

当比较节点并将其合并到新列表中时，就会出现问题.例如: 最初，将lady与apple进行比较.它们被合并到列表中:apple, lady.然后，此列表应与石头合并.但是，首先，将lady与stone进行比较，而不是将apple与stone进行比较.然后，将生成列表:lady, stone(apple被留在后面并且未用于比较中).应该发生的是，将apple与stone进行比较，然后将lady与stone进行比较，然后对条目进行排序并相应地合并为:apple, lady, stone.

The problems come when nodes are compared and merged into new lists. For example: Initially, lady is compared to apple. They're merged into the list: apple, lady. Then this list should be merged with stone. However, first, lady is compared with stone, instead of apple being compared to stone. This then generates the list: lady, stone (apple being left behind and not used in a comparison). What should happen, is that apple is compared to stone, then lady is compared to stone, and then the entries are sorted and merged accordingly into: apple, lady, stone.

实际的最终输出是:lady, red, stone.显然，apple和queen已经丢失了某个地方.我不确定什么是令人反感的代码.

The actual final output is: lady, red, stone. Clearly, apple and queen have been lost somewhere. I'm not sure what the offending code is.

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);

}

推荐答案

您的代码几乎是完美的.您正在合并两个列表，并将其返回到head.但是您没有将精确的head返回到先前的mergeSort调用.

Your code is almost perfect. You are merging two lists and returning it to head. But you are not returning that exact head to previous mergeSort calls.

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).该代码现在应该可以正常工作.

In your main function where you are calling mergeSort, use head = mergeSort(head). The code should work now.

这篇关于在链表中丢失的节点在C中的合并排序实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！