合并链表的排序代码仅对C中的一半元素进行排序

Question

我有一些代码可以合并对包含字符串作为数据值的链表进行排序。我的目标是按字母顺序对链接列表中的节点进行排序。

这是我定义节点的方式：

struct Node { 
    void *data; 
    struct Node* next; 
}; 

这是我要对主目录中的列表进行排序的电话：

int main() 
{ 

    struct Node* a = NULL; 
    struct Node* sorted = NULL;

    push(&a, "orange"); 
    push(&a, "banana"); 
    push(&a, "strawberry"); 
    push(&a, "apple"); 
    push(&a, "kiwi"); 
    push(&a, "grapes"); 

    sorted = MergeSort(a); 

    printf("Sorted Linked List is: \n"); 
    printList(sorted); 

    return 0; 
} 

push函数在链接列表的开头插入一个元素，而printList函数将在列表中打印每个元素，然后打印换行符。

我可以确认push和printList功能正常工作，因为测试时按预期打印了列表a的所有元素。

这是我用来按字母顺序对列表进行排序的代码：

/* sorts the linked list by changing next pointers (not data) */
struct Node* MergeSort(struct Node* headRef) 
{ 
    struct Node* head = headRef; 
    struct Node* a; 
    struct Node* b; 

    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) { 
        return headRef; 
    } 

    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b); 

    /* Recursively sort the sublists */
    MergeSort(a); 
    MergeSort(b); 

    /* answer = merge the two sorted lists together */
    headRef = SortedMerge(a, b); 
    return headRef;
} 


struct Node* SortedMerge(struct Node* a, struct Node* b) 
{ 
    struct Node* result = NULL; 

    /* Base cases */
    if (a == NULL) 
        return (b); 
    else if (b == NULL) 
        return (a); 

    /* Pick either a or b, and recur */
    if (strcmp(a->data, b->data) <= 0) { 
        result = a; 
        result->next = SortedMerge(a->next, b); 
    } 
    else { 
        result = b; 
        result->next = SortedMerge(a, b->next); 
    } 
    return (result); 
} 

/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves, 
    and return the two lists using the reference parameters. 
    If the length is odd, the extra node should go in the front list. 
    Uses the fast/slow pointer strategy. */
void FrontBackSplit(struct Node* source, 
                    struct Node** frontRef, struct Node** backRef) 
{ 
    struct Node* fast; 
    struct Node* slow; 
    slow = source; 
    fast = source->next; 

    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL) { 
        fast = fast->next; 
        if (fast != NULL) { 
            slow = slow->next; 
            fast = fast->next; 
        } 
    } 

    /* 'slow' is before the midpoint in the list, so split it in two 
    at that point. */
    *frontRef = source; 
    *backRef = slow->next; 
    slow->next = NULL; 
} 

当我在排序过程之后打印列表sorted时，我的输出如下所示：

Sorted Linked List is: 
grapes
kiwi
strawberry

这表明排序工作正常，但是并非所有元素都已输出。我想知道为什么会这样吗？

Answer 1

/* Recursively sort the sublists */
MergeSort(a); 
MergeSort(b); 

这里是有问题的部分。您正在对子列表进行排序，但是对子列表进行了排序之后，就没有更新a和b指向列表的相应新标题。

更改为

/* Recursively sort the sublists */
a = MergeSort(a); 
b = MergeSort(b); 

它的行为符合预期。