C言語、連結リストのマージ (merge)

Question

C言語で連結リストを作っています。

https://github.com/katahiromz/lst/blob/master/lst.h
https://github.com/katahiromz/lst/blob/master/lst.c

ファイル「lst.c」の505行目、lst_merge関数を実装する方法を具体的に教えてもらえませんか？

外部仕様は、C++のstd::list::mergeと同じで、
第一引数と第二引数のデータを第一引数に併合して、実行後は、第二引数は空になります。
第三引数は、比較に使う関数ポインタです。

よろしくお願いします。

Answer 1

lst_merge()の実装部分を観る限り、マージする連結リストはそれぞれソート済み、という仕様のようですので、下記の手順で実装すればいいと思います。

1. 二つのリストのマージ
2. マージされたリストのソート

マージ処理はリスト1にリスト2をくっつけて空にする処理ですので

     /* リストのマージ */
    PNOD pnod1 = plst1->last;
    PNOD pnod2 = plst2->first;
    pnod1->next = pnod2;
    pnod2->prev = pnod1;
    plst1->last = plst2->last;
    plst2->first = NULL;
    plst2->last = NULL;
    plst2->data_size = 0;

こんなかんじで。後半はplst1に対してソートをかけるのですが、現時点ではlst_sort()は未実装のようですね。

連結リストの場合マージソートというアルゴリズムを使うのが一般的です。「連結リスト マージソート」などのキーワードでweb検索してもらうといろいろ参考になる実装が見つかると思います。コツとしては再帰を使わない実装にした方が実行速度やメモリ消費の点で有利という点でしょうか。
いろいろ試してみてください。

Comments

[katahiromz]

ありがとうございます。解決しました。