[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIIB(Javaアルゴリズム)第6回

目次
6.1 リスト(2)
6.1.1 リストと配列の間のコピー
6.1.2 リストの併合
6.1.3 併合整列
6.2 演習6
6.3 レポート課題
6.4 参考文献
索引
併合   併合整列  

6.1 リスト(2)

6.1.1 リストと配列の間のコピー

リストと配列は、ともにデータの列が格納できるデータ構造でした。 ここでは、リストと配列の間で相互にコピーすることを考えます。 リストの構成には、前回と同じクラスを用います。

/*  1*/ class ListNode {
/*  2*/     int data;
/*  3*/     ListNode next;
/*  4*/     ListNode (int data, ListNode next) {
/*  5*/         this.data = data;
/*  6*/         this.next = next;
/*  7*/     }
/*  8*/ }

配列からリストへのコピーは、比較的簡単です。 以下のプログラムでは、最初の for 文で配列を構成し、次の for 文でそれをリストへコピーし、最後の for 文でリストを出力しています。

/*  1*/ class ArrayToList {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0;
/*  4*/         int[] a = new int[10];
/*  5*/         ListNode list = new ListNode(DUMMY, null);
/*  6*/         ListNode x;
/*  7*/         a[0] = DUMMY;
/*  8*/         for (i = 1; i <= 9; i++) {
/*  9*/             a[i] = i;
/* 10*/         }
/* 11*/         x = list;
/* 12*/         for (i = 1; i < a.length; i++) {
/* 13*/             x.next = new ListNode(a[i], null);
/* 14*/             x = x.next;
/* 15*/         }
/* 16*/         for (x = list.next; x != null; x = x.next) {
/* 17*/             System.out.print(" " + x.data);
/* 18*/         }
/* 19*/         System.out.println();
/* 20*/     }
/* 21*/ }
b04a001@AsiaA1:~/comp3b% java ArrayToList
 1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%

リストから配列へのコピーは多少面倒です。 なぜなら、配列を生成するには、配列の長さが分からなければならないからです。 以下のプログラムでは、最初の for 文でリストを構成し、次の for 文でその長さを求め、その次の for 文でリストを配列へコピーし、最後の for 文で配列を出力しています。

/*  1*/ class ListToArray {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0, len;
/*  4*/         int[] a;
/*  5*/         ListNode list = new ListNode(DUMMY, null);
/*  6*/         ListNode x;
/*  7*/         x = list;
/*  8*/         for (i = 1; i <= 9; i++) {
/*  9*/             x.next = new ListNode(i, null);
/* 10*/             x = x.next;
/* 11*/         }
/* 12*/         len = 0;
/* 13*/         for (x = list.next; x != null; x = x.next) {
/* 14*/             len++;
/* 15*/         }
/* 16*/         a = new int[len + 1];
/* 17*/         a[0] = DUMMY;
/* 18*/         i = 1;
/* 19*/         for (x = list.next; x != null; x = x.next) {
/* 20*/             a[i] = x.data;
/* 21*/             i++;
/* 22*/         }
/* 23*/         for (i = 1; i < a.length; i++) {
/* 24*/             System.out.print(" " + a[i]);
/* 25*/         }
/* 26*/         System.out.println();
/* 27*/     }
/* 28*/ }
b04a001@AsiaA1:~/comp3b% java ListToArray
 1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%

6.1.2 リストの併合

併合merging ) とは、整列済みの複数の数列をまとめて、1つの整列済みの数列を作ることです。 ここでは、特に2つの数列を1つにまとめることを考えます。

2つの数列を併合するには、まず、双方の先頭要素を比較し、小さい方を結果の先頭に移動します。 次に、残りの先頭要素を比較し、小さい方を結果の先頭の次に移動します。 この移動を繰り返し、もし一方の要素がなくなったら、他方の残りをすべて結果の最後に移動します。

併合は、配列に対してもできますが、リストのほうが向いています。

次のプログラムは、リスト [1, 3] と [2, 4] を併合して、リスト [1, 2, 3, 4] を作るものです。

/*  1*/ class ListMerge {
/*  2*/     public static void main (String[] args) {
/*  3*/         int DUMMY = 0;
/*  4*/         ListNode list1 = new ListNode(DUMMY, null);
/*  5*/         ListNode list2 = new ListNode(DUMMY, null);
/*  6*/         ListNode list0, x0, x1, x2;
/*  7*/         list1.next = new ListNode(1, null);
/*  8*/         list1.next.next = new ListNode(3, null);
/*  9*/         list2.next = new ListNode(2, null);
/* 10*/         list2.next.next = new ListNode(4, null);
/* 11*/         list0 = list1;
/* 12*/         x0 = list0;
/* 13*/         x1 = list1.next;
/* 14*/         x2 = list2.next;
/* 15*/         while (x1 != null && x2 != null) {
/* 16*/             if (x1.data <= x2.data) {
/* 17*/                 x0.next = x1;
/* 18*/                 x0 = x0.next;
/* 19*/                 x1 = x1.next;
/* 20*/             } else {
/* 21*/                 x0.next = x2;
/* 22*/                 x0 = x0.next;
/* 23*/                 x2 = x2.next;
/* 24*/             }
/* 25*/         }
/* 26*/         if (x1 == null) {
/* 27*/             x0.next = x2;
/* 28*/         } else {
/* 29*/             x0.next = x1;
/* 30*/         }
/* 31*/         System.out.println(list0.next.data);
/* 32*/         System.out.println(list0.next.next.data);
/* 33*/         System.out.println(list0.next.next.next.data);
/* 34*/         System.out.println(list0.next.next.next.next.data);
/* 35*/     }
/* 36*/ }
b04a001@AsiaA1:~/comp3b% java ListMerge
1
2
3
4
b04a001@AsiaA1:~/comp3b%

併合のイメージは次の通りです。

併合のイメージ
図 6.1  併合のイメージ

6.1.3 併合整列

併合整列merge sort ) とは、併合を段階的に行う整列法です。

併合整列のアルゴリズムは、

  1. リストを半分に分ける。
  2. 2つのリストをそれぞれ併合整列する。
  3. 整列された2つのリストを併合する。

となります。 ただし、リストの長さが1のときは何もしません。 このアルゴリズムに再帰が使われていることに注意してください。

今、数列 9, 4, 5, 2, 7, 1, 3, 8, 6 が与えられたとします。 この数列を半分に分けますと、9, 4, 5, 2 と 7, 1, 3, 8, 6 になります。 また半分に分けますと、9, 4 と 5, 2 と 7, 1 と 3, 8, 6 になります。 最後には、数列はバラバラになります。 ここから、併合を開始します。 分けた順の逆順に併合が行われていきます。 すると、最後には、整列済みの数列 1, 2, 3, 4, 5, 6, 7, 8, 9 が得られます。 この様子を図で表しますと、次のようになります。

併合整列のイメージ
図 6.2  併合整列のイメージ

プログラムは以下の通りです。 併合整列を行うのはメソッド msort です。 リストを半分に分けるため、参照 x1x2 を用意し、 x1x2 の半分の速さで右に移動させます。 x2 が右端に来たとき、 x1 の指す節点を末尾にして、リストを分割します。 分割されたリストをそれぞれ併合整列し、メソッド merge を呼び出してそれらを併合します。

/*  1*/ class MergeSort {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0;
/*  4*/         int[] a = {DUMMY, 9, 4, 5, 2, 7, 1, 3, 8, 6};
/*  5*/         ListNode list = new ListNode(DUMMY, null);
/*  6*/         ListNode x;
/*  7*/         x = list;
/*  8*/         for (i = 1; i < a.length; i++) {
/*  9*/             x.next = new ListNode(a[i], null);
/* 10*/             x = x.next;
/* 11*/         }
/* 12*/         for (x = list.next; x != null; x = x.next) {
/* 13*/             System.out.print(" " + x.data);
/* 14*/         }
/* 15*/         System.out.println();
/* 16*/         list = msort(list);
/* 17*/     }
/* 18*/     static ListNode merge (ListNode list1, ListNode list2) {
/* 19*/         ListNode list0, x0, x1, x2;
/* 20*/         list0 = list1;
/* 21*/         x0 = list0;
/* 22*/         x1 = list1.next;
/* 23*/         x2 = list2.next;
/* 24*/         while (x1 != null && x2 != null) {
/* 25*/             if (x1.data <= x2.data) {
/* 26*/                 x0.next = x1;
/* 27*/                 x0 = x0.next;
/* 28*/                 x1 = x1.next;
/* 29*/             } else {
/* 30*/                 x0.next = x2;
/* 31*/                 x0 = x0.next;
/* 32*/                 x2 = x2.next;
/* 33*/             }
/* 34*/         }
/* 35*/         if (x1 == null) {
/* 36*/             x0.next = x2;
/* 37*/         } else {
/* 38*/             x0.next = x1;
/* 39*/         }
/* 40*/         return list0;
/* 41*/     }
/* 42*/     static ListNode msort (ListNode list) {
/* 43*/         int DUMMY = 0;
/* 44*/         ListNode list0, list1, list2, x0, x1, x2;
/* 45*/         if (list.next.next == null) {
/* 46*/             return list;
/* 47*/         } else {
/* 48*/             x1 = list;
/* 49*/             x2 = list;
/* 50*/             while (x2.next != null) {
/* 51*/                 x2 = x2.next;
/* 52*/                 if (x2.next != null) {
/* 53*/                     x2 = x2.next;
/* 54*/                     x1 = x1.next;
/* 55*/                 }
/* 56*/             }
/* 57*/             list2 = new ListNode(DUMMY, x1.next);
/* 58*/             list1 = list;
/* 59*/             x1.next = null;
/* 60*/             list0 = merge(msort(list1), msort(list2));
/* 61*/             for (x0 = list0.next; x0 != null; x0 = x0.next) {
/* 62*/                 System.out.print(" " + x0.data);
/* 63*/             }
/* 64*/             System.out.println();
/* 65*/             return list0;
/* 66*/         }
/* 67*/     }
/* 68*/ }
b04a001@AsiaA1:~/comp3b% java MergeSort
 9 4 5 2 7 1 3 8 6
 4 9
 2 5
 2 4 5 9
 1 7
 6 8
 3 6 8
 1 3 6 7 8
 1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%

6.2 演習6

リストの長さを利用した併合整列のプログラムを作成してください。

上記の併合整列のプログラムでは、リストを半分に分ける方法が難解でした。 もし、リストの長さ len を求めておけば、参照を len / 2 回たどり、その節点を末尾にすれば、リストの分割ができます。

上記のプログラムのメソッド msort を変更し、リスト list の長さ len を求めた後、参照を len / 2 回たどるようにしてください。


6.3 レポート課題

今日の演習6の答案(Javaプログラム)をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(11月17日)を明記してください。


6.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2006年11月17日更新
小西 善二郎 <konishi@twcu.ac.jp>
Copyright (C) 2006 Zenjiro Konishi. All rights reserved.