C：結合リストのマージソート

Question

ウィキペディアのマージソート用の擬似コードに基づいて、2つのノードのリストに正しくマージされる1つのノードのベースケースに到達することができます。しかし、結合された部分は逆転してしまいます。

私はMakefileを使用しています：

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

私はヘッドポインタ及びテールポインタを含むリストヘッダの構造体を使用しています。ヘッドは最初のノードを指し、末尾は最後のノードを指します。
マージ機能は動作していますが、ここではソート機能が使用されています。

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

編集： アサーションは失敗したので、私はに切り替え：

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

    capture = merge(sublistA, sublistB); 

私はマージソート、それがメインでのprintf文から正しく捕獲されていないことを確信しています。ここで

は、意図しない反転を示し、コマンドラインに出力されます。

/* 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!*/ 

編集：私はあなたのmerge機能が破壊的に変更することで動作することに気づいた

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

：ここでは、マージ機能があります入力リスト：入力として2つのリストを取り、出力として新しいマージされたリストを生成し、結果のリストを返します。ただし、list_sort関数では、返された新しいリストをキャプチャしていないので、新しく並べ替えられたシーケンスを保持するために入力リストを更新していません。戻り値をmergeから取得し、入力リストのパラメータを更新するために使用してください。