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

用户9123

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

这是我定义节点的方式:

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功能将在列表中后跟一个换行打印的每个元素。

我可以确认pushprintList功能正常运行,因为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

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

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

这是有问题的部分。您正在对子列表进行排序,但是在对它们进行排序之后,您就不会更新ab指向列表的相应新标题。

改成

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

它的行为符合预期。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章