C: Fusionner Trier pour la liste liée, sous-tableau fusionné pas capturé correctement dans la fonction de tri

Question

Basé sur le pseudo-code sur le site Wikipedia pour Merge Sort, je peux descendre au cas de base d'un nœud qui fusionne correctement dans une liste de deux nœuds . Cependant, la partie fusionnée est inversée je pense quand ils remontent la chaîne récursive.

J'utilise un Makefile:

sort: main.c sort.c 
    gcc -Wall -std=c99 -o $@ main.c sort.c ll.c 

J'utilise un struct en-tête de liste qui contient un pointeur de tête et pointeur de la queue. La tête indique le premier nœud et la queue jusqu'au dernier.
La fonction de fusion fonctionne mais voici la fonction de tri.

void list_sort(list_t *list) 
{ 
printf("in sort 1\n"); 

    //base case of 0 or 1 element 
    if (list->head == NULL || list->head->next == NULL) { 
     return; 
    } 

    list_t *sublistA = list_create(); 
    assert(sublistA); 
    list_t *sublistB = list_create(); 
    assert(sublistB); 

    int len = Length(list); 
    int mid = (len)/2; 
    printf("mid is %d\n", mid); 
    int i = 0; 
    element_t *current = list->head; 
    //make sublists 
    while (i < len) { 
     if (i < mid) { 
      printf("append sublistA\n"); 
      list_append(sublistA, current->val); 
     } else { 
      printf("append sub B\n"); 
      list_append(sublistB, current->val); 
     } 
     i++; 
     current = current->next;  
    } 
    list_print(sublistA); 
    list_print(sublistB); 

    printf("going to sort A\n"); 
    list_sort(sublistA); 

    printf("going to sort B\n"); 
    list_sort(sublistB); 
    //this was just added to capture returned list from merge 
    list_t* capture = NULL; 
    assert(capture);//the assertion failed 
    capture = merge(sublistA, sublistB); 
    } 

Edit: Assertion n'a donc je suis passé à:

list_t* capture = list_create(); 
    assert(capture); 

    capture = merge(sublistA, sublistB); 

Je suis certain que ce ne soit pas capturé correctement à partir printf dans les principaux, fusionner et tri.

Voici la sortie à la ligne de commande qui montre l'inversion involontaire:

/* left and right lists to merge://at the start of the merge function 
{ 8, } 
{ 7, } 
in merge while 1 
in merge else 1 
{ 7, } 
final result 
{ 7, 8, }//yay! this is the last line of merge function 
in merge//came right back again to merge 
left and right lists to merge: 
{ 9, } 
{ 8, 7, }//doh!*/ 

Edit: Voici la fonction de fusion:

list_t *merge(list_t *left, list_t *right) { 
    printf("in merge\n"); 
    list_t *result = list_create(); 
    assert(result); 

    element_t *curr1 = left->head; 
    element_t *curr2 = right->head; 
    //list_t *result = list_create(); 
    printf("left and right lists to merge: \n"); 
    list_print(left); 
    list_print(right); 

    while (curr1 != NULL && curr2 != NULL) { 
printf("in merge while 1\n"); 
     if (curr1->val <= curr2->val) { 
      list_append(result, curr1->val); 
      printf("merge while 1 if\n"); 
      curr1 = curr1->next; 
      //curr2 = curr2->next; 
     } 
     else //curr1->val > curr2->val 
     { 
      printf("in merge else 1\n"); 
      list_append(result, curr2->val); 
      curr2 = curr2->next; 
     } 
    } 
    list_print(result); 

    //leftovers need to be allocated 
    while (curr1 != NULL) { 
     list_append(result, curr1->val); 
     curr1 = curr1->next; 
    } 

    while (curr2 != NULL) { 
     list_append(result, curr2->val); 
     curr2 = curr2->next; 
    } 

    //printf("curr1->val is %d\n", curr1->val); 
    //printf("curr2->val is %d\n", curr2->val); 
    list_destroy(left); 
    list_destroy(right); 
    printf("final result\n"); 
    list_print(result); 

    return result; 
} 

Answer 1

J'ai remarqué que votre fonction merge fonctionne en modifiant destructivement la listes d'entrée: vous prenez les deux listes en entrée, produisez une nouvelle liste fusionnée en sortie, puis renvoyez la liste résultante. Cependant, dans votre fonction list_sort, vous ne capturez pas la nouvelle liste renvoyée, et par conséquent vous ne mettez pas à jour la liste d'entrée fournie pour contenir la séquence nouvellement triée. Essayez de capturer la valeur de retour de merge et de l'utiliser pour mettre à jour le paramètre de liste d'entrée.