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

它的行为符合预期。