リンクされたリストのための私のmergesortを改善する。どうやって？

Question

私が説明に入る前に、次のコードが本当に悪いかもしれないことに注意してください。私は約2ヶ月前にプログラミングを始めました（そこに2,3時間あります）。だから私は経験がなく、コーディングスタイルは非常に改善されており、私はまだ練習や多くの（基本的な）知識を欠場しています。これには、間違った名前で物事を呼び出すこともあります:)。

私はアルゴリズム（大学）に興味を持ち、いくつかのポインタ処理を練習したいと思っていました（最初はかなり問題がありました）ので、単一リンクリストでmergesortを実行し、mergeSortアルゴリズム私の教授（配列をソートする）。これは宿題ではありません（私の大学のコース（電気工学）は宿題がありません）。これは私のアルゴリズムの理解を深め、Cを実践しています。

---

私のコードはすでに動作しています。テスト目的のために、私は常に逆ソートリストを作成しました。それは、リストがNULLであるというような場合にはまだ何かが欠落しています。

だから、コードを投稿する前に私が使用している構造体のthats：

struct list{ 
    int nbr; 
    struct list *next_el; 
}; 
typedef struct list LIST; 
typedef LIST *z_LIST; 

私は2つの機能、マージソートを持って、マージします。 mergeSortはソートされた（サブ）リストの新しいヘッドを返し、mergeはマージされたシーケンスの先頭を返します。

今私は、ソートされていないリストの現在の頭と要素の量をmergeSortします。 その後、リストを再帰的に分解します（明らかに:)）。 次のコードでどれくらい言いたいのか分かりません。何かが不明である場合は私が答えると、可能な限り迅速に説明したが、

z_LIST mergeSort (z_LIST head, int length) { 

    int steps; 
    int m = 0; 
    z_LIST head1 = NULL, head2 = NULL, new_head = NULL; 

if(length > 1) { 

    m = (length+1)/2; 


    head2 = head; 
    for(steps = 0; steps<m; steps++) { 
    head2 = head2->next_el; 
    } 

    head1 = mergeSort(head, m); 
    head2 = mergeSort(head2, length-m); 

    new_head = merge(head1, head2, m, length-m); 

    return new_head; 

    } else { 
    return head; 
    } 
} 

マージは、（いずれか一つの要素またはすでにソート配列である）二つのサブリストの頭部と第一の要素を受け取ります2番目のリスト。

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2) { 

    int i,j; 
    z_LIST part1 = head1, part2 = head2; 
    z_LIST temp_head = NULL, head = NULL; 

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0 
or i=0/j=1.*/ 

    if(part1->nbr < part2->nbr){ 
    head = part1; 
    if(part1->next_el != NULL) { 
     part1 = part1->next_el; 
    } 
    i=1; 
    j=0; 
    } else { 
    head = part2; 
    if(part2->next_el != NULL) { //The last element of the original list points 
     part2 = part2->next_el;  //to NULL. If I would then make part2 = NULL, 
    }        //then there wouldn't be part2->nbr ->lots 
    i=0; 
    j=1; 
    } 

    temp_head = head; 

    while((i<l1) || (j<l2)) { 
    if(((part1->nbr < part2->nbr) && i<l1)||(j>=l2)) { 
     temp_head->next_el = part1; 
     part1 = part1->next_el; 
     temp_head = temp_head->next_el; 
     if (j>=l2) { //If j>=l2 then I let merge add one more item of list1 
     break;  //since list 1 is already sorted and linked correctly. 
     }    //Same below. Should shave off some operations/time? 
     i++; 
    } else { 
     temp_head->next_el = part2; 
     part2 = part2->next_el; 
     temp_head = temp_head->next_el; 
     if (i>=l1) { 
     break; 
     } 
     j++; 
    } 
    } 

    return head; 
} 

は、だから私は、私は可能性のある問題、いくつかの入力コードブレークコードについて考えていなかった場合は、プレーン愚かやっているのか、より良い、それを行う方法上の任意のコメントを歓迎するだろう、私は確信しています改善の可能性はまだかなりあります。前もって感謝します。

Answer 1

ソートのマージ・フェーズのために「正常な」構造は以下の通りである：

set output list to empty 
while (list1 not empty && list2 not empty) 
{ 
    if (list1->headvalue < list2->headvalue 
     move head of list1 to output list 
    else 
     move head of list2 to output list 
} 
while (list1 not empty) 
    move head of list1 to output list 
while (list2 not empty) 
    move head of list2 to output list 

「移動」操作は、リスト内の次の項目へのポインタを更新することを含みます。

merge()の機能には多少異なる構造があります。

リストをカウントすることも慣習的です。通常、リストが純粋に線形かどうか、またはそれが循環リストであるかどうかによって、 'next is null'または 'next is head'のいずれかを使用してリストの終わりを決定します。