第１２回 線型リスト・その４（６／２６）

今日のキーワード

■ リストの結合（append操作）

２つのリストを単純に結合する操作、つまり、１つめのリストの後に、２つめのリストの先頭を繋げる操作を、append という。

append 操作のアルゴリズムは以下のようになる。 

/* リスト l1 にリスト l2 を結合する */
void list_append(Node *l1, Node *l2) {
  Node *p;

  p = l1;
  p の次ノードへのリンクが NULL でない間、以下を実行する。
    p = p -> next;
  p の次ノードへのリンクを l2 の最初のノードとする。
}

ここで、l2 の最初のノードとは、線型リストの最初に置かれたダミーノードではないことに、注意せよ。

例えば、l1 = [1,3,5,7] に l2 = [2,4,6,8] を append すると、l1 = [1,3,5,7,2,4,6,8] となる。

■ リストの合成（merge操作）

ソートされている２つのリストを合成し、ソートされた１つのリストとする操作を merge という。

merge 操作のアルゴリズムは以下のようになる。 

/* リスト l1 にリスト l2 を順序（昇順）を保ち混ぜ合わせる（l2は破壊される） */
void list_merge(Node *l1, Node *l2) {
  Node *p, *q, *t;

  p = l1;
  q = l2;
  p の次ノードへのリンクが NULL でない間、以下を実行する。
    もし、q の次ノードへのリンクが NULL であるならば、
      return;
    もし、p の次ノードの値より q の次ノードの値が小さいならば、
      t に q の次ノードへのリンクを退避（代入）する。
      q の次ノードへのリンクを t の次ノードとする。
      t の次ノードへのリンクを p の次ノードとする。
      p の次ノードへのリンクを t とする。
      p を t とする。
    そうでなければ、
      p を p の次ノードとする。
  p の次ノードを q の次ノードとする。
  q の次ノードへのリンクを NULL とする。
}

例えば、l1 = [1,3,5,7] に l2 = [2,4,6,8] を merge すると、l1 = [1,2,3,4,5,6,7,8] となる。

■ 宿題

以下の２つを両方とも取り組むこと。

  1. まず、append 操作、および、merge 操作を完成させよ。
  2. 以下のメイン関数を実行した結果を提出せよ。ソースの下書きは、 prac1201.c である。この中に、append操作、merge操作を書き込むこと。
  3. 同関数により、merge される過程を作図し、説明せよ。 
main() {
  Node root1, root2, root3;

  root1.next = NULL;
  root2.next = NULL;
  root3.next = NULL;

  list_push(&root1,1);
  list_push(&root1,3);
  list_push(&root1,5);

  list_insert(&root2,4);
  list_insert(&root2,9);
  list_insert(&root2,2);

  list_append(&root1,&root2);

  list_insert(&root3,7);
  list_insert(&root3,3);
  list_insert(&root3,1);

  list_merge(&root3,&root2); /* ← ここの関数内での過程を示すこと */

  list_print(&root1);
  printf("\n");
  list_print(&root2);
  printf("\n");
  list_print(&root3);
}

プログラム作成に必要な、ライブラリ(numlist.c、numlist.h）、Makefile、および、mainのソースは次のものを利用すること。（「リンク先を保存」などブラウザのセーブ機能を使い、ダウンロードすること。Makefile は適宜追加すること。）

(c) Masato TOKUHISA, 2003, June.24