コンピュータIIIB（Javaアルゴリズム）第8回

今回も、リストに関するプログラムを紹介します。前回と同様、できるだけ配列の場合とリストの場合を比較します。リストの構成には、前回と同じクラスを用います。

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

次のプログラムは、配列 {1, 2, 3, 4, 5, 6, 7, 8, 9} を作成し、それをコピーし、その要素を出力するものです。コピー元と同じ長さの配列を生成しています。

/*  1*/ class ArrayCopy {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0;
/*  4*/         int[] a = new int[10];
/*  5*/         int[] b;
/*  6*/         a[0] = DUMMY;
/*  7*/         for (i = 1; i <= 9; i++) {
/*  8*/             a[i] = i;
/*  9*/         }
/* 10*/         b = new int[a.length];
/* 11*/         b[0] = DUMMY;
/* 12*/         for (i = 1; i < a.length; i++) {
/* 13*/             b[i] = a[i];
/* 14*/         }
/* 15*/         for (i = 1; i < b.length; i++) {
/* 16*/             System.out.print(" " + b[i]);
/* 17*/         }
/* 18*/         System.out.println();
/* 19*/     }
/* 20*/ }

次のプログラムは、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を作成し、それをコピーし、その要素を出力するものです。コピー元と同じ数だけリストの節点を生成しています。

/*  1*/ class ListCopy {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0;
/*  4*/         ListNode list1 = new ListNode(DUMMY, null);
/*  5*/         ListNode list2 = new ListNode(DUMMY, null);
/*  6*/         ListNode x1, x2;
/*  7*/         x1 = list1;
/*  8*/         for (i = 1; i <= 9; i++) {
/*  9*/             x1.next = new ListNode(i, null);
/* 10*/             x1 = x1.next;
/* 11*/         }
/* 12*/         x2 = list2;
/* 13*/         for (x1 = list1.next; x1 != null; x1 = x1.next) {
/* 14*/             x2.next = new ListNode(x1.data, null);
/* 15*/             x2 = x2.next;
/* 16*/         }
/* 17*/         for (x2 = list2.next; x2 != null; x2 = x2.next) {
/* 18*/             System.out.print(" " + x2.data);
/* 19*/         }
/* 20*/         System.out.println();
/* 21*/     }
/* 22*/ }

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

配列からリストへのコピーは、比較的簡単です。以下のプログラムでは、最初の 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*/ }

リストから配列へのコピーは多少面倒です。なぜなら、配列を生成するには、配列の長さが分からなければならないからです。以下のプログラムでは、最初の 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*/ }

8.1.2 リストの連接

2つのリストを連接するプログラムを考えます。ここで、リスト list1 と list2 を連接するとは、 list1 の要素に続けて list2 の要素を並べたリストを作成することです。例えば、[1, 2, 3] と [4, 5] を連接しますと、[1, 2, 3, 4, 5] となります。

次のプログラムは、配列 {1, 2, 3} と {4, 5} を連接します。 2つの配列が格納できる長さの配列を生成しています。

/*  1*/ class ArrayAppend {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, DUMMY = 0;
/*  4*/         int[] a = new int[4];
/*  5*/         int[] b = new int[3];
/*  6*/         int[] c;
/*  7*/         a[0] = DUMMY;
/*  8*/         a[1] = 1;
/*  9*/         a[2] = 2;
/* 10*/         a[3] = 3;
/* 11*/         b[0] = DUMMY;
/* 12*/         b[1] = 4;
/* 13*/         b[2] = 5;
/* 14*/         c = new int[a.length + b.length - 1];
/* 15*/         c[0] = DUMMY;
/* 16*/         for (i = 1; i < a.length; i++) {
/* 17*/             c[i] = a[i];
/* 18*/         }
/* 19*/         for (i = 1; i < b.length; i++) {
/* 20*/             c[a.length - 1 + i] = b[i];
/* 21*/         }
/* 22*/         for (i = 1; i < c.length; i++) {
/* 23*/             System.out.print(" " + c[i]);
/* 24*/         }
/* 25*/         System.out.println();
/* 26*/     }
/* 27*/ }

プログラムは以下の通りです。ポイントは、リスト list1 の末尾を探し、そこにリスト list2 のダミー・データを除いた部分を格納することです。新しい節点を生成していないことに注意してください。

/*  1*/ class ListAppend {
/*  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 x;
/*  7*/         list1.next = new ListNode(1, null);
/*  8*/         list1.next.next = new ListNode(2, null);
/*  9*/         list1.next.next.next = new ListNode(3, null);
/* 10*/         list2.next = new ListNode(4, null);
/* 11*/         list2.next.next = new ListNode(5, null);
/* 12*/         for (x = list1; x.next != null; x = x.next) {
/* 13*/         }
/* 14*/         x.next = list2.next;
/* 15*/         for (x = list1.next; x != null; x = x.next) {
/* 16*/             System.out.print(" " + x.data);
/* 17*/         }
/* 18*/         System.out.println();
/* 19*/     }
/* 20*/ }

8.1.3 リストの併合

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

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

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

次のプログラムは、配列 {1, 3} と {2, 4} を併合して、配列 {1, 2, 3, 4} を作るものです。 2つの配列が格納できる長さの配列を生成しています。

/*  1*/ class ArrayMerge {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i, j, k, DUMMY = 0;
/*  4*/         int[] a = new int[3];
/*  5*/         int[] b = new int[3];
/*  6*/         int[] c;
/*  7*/         a[0] = DUMMY;
/*  8*/         a[1] = 1;
/*  9*/         a[2] = 3;
/* 10*/         b[0] = DUMMY;
/* 11*/         b[1] = 2;
/* 12*/         b[2] = 4;
/* 13*/         c = new int[a.length + b.length - 1];
/* 14*/         c[0] = DUMMY;
/* 15*/         i = 1;
/* 16*/         j = 1;
/* 17*/         k = 1;
/* 18*/         while (i < a.length && j < b.length) {
/* 19*/             if (a[i] <= b[j]) {
/* 20*/                 c[k] = a[i];
/* 21*/                 k++;
/* 22*/                 i++;
/* 23*/             } else {
/* 24*/                 c[k] = b[j];
/* 25*/                 k++;
/* 26*/                 j++;
/* 27*/             }
/* 28*/         }
/* 29*/         if (i < a.length) {
/* 30*/             while (i < a.length) {
/* 31*/                 c[k] = a[i];
/* 32*/                 k++;
/* 33*/                 i++;
/* 34*/             }
/* 35*/         } else {
/* 36*/             while (j < b.length) {
/* 37*/                 c[k] = b[j];
/* 38*/                 k++;
/* 39*/                 j++;
/* 40*/             }
/* 41*/         }
/* 42*/         for (k = 1; k < c.length; k++) {
/* 43*/             System.out.print(" " + c[k]);
/* 44*/         }
/* 45*/         System.out.println();
/* 46*/     }
/* 47*/ }

次のプログラムは、リスト [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 list3, x1, x2, x3;
/*  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*/         list3 = list1;
/* 12*/         x1 = list1.next;
/* 13*/         x2 = list2.next;
/* 14*/         x3 = list3;
/* 15*/         while (x1 != null && x2 != null) {
/* 16*/             if (x1.data <= x2.data) {
/* 17*/                 x3.next = x1;
/* 18*/                 x3 = x3.next;
/* 19*/                 x1 = x1.next;
/* 20*/             } else {
/* 21*/                 x3.next = x2;
/* 22*/                 x3 = x3.next;
/* 23*/                 x2 = x2.next;
/* 24*/             }
/* 25*/         }
/* 26*/         if (x1 != null) {
/* 27*/             x3.next = x1;
/* 28*/         } else {
/* 29*/             x3.next = x2;
/* 30*/         }
/* 31*/         for (x3 = list3.next; x3 != null; x3 = x3.next) {
/* 32*/             System.out.print(" " + x3.data);
/* 33*/         }
/* 34*/         System.out.println();
/* 35*/     }
/* 36*/ }

併合のイメージは次の通りです。新しい節点を生成していないことに注意してください。

8.1.4 リストとメソッド

これまで、リストに関するプログラムをいくつか作成してきました。それらのプログラムを見比べると、似たような部分が見つかります。そのような部分をメソッドにまとめて、プログラムを分かりやすくしてみます。

以下のプログラムは、前回のプログラム ListLoop を書き直したものです。 ListLoop は、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を生成して表示するものでした。

メソッド makeEmptyList は、空のリストを生成するものです。引数はありません。返り値は、生成したリストです。

メソッド addNode は、リストの末尾に、次の節点を追加するものです。引数は、リストの末尾と、追加する節点のデータです。返り値は、追加した節点です。

メソッド printList は、リストの要素をすべて表示するものです。引数はリストです。

/*  1*/ class ListMethod {
/*  2*/     public static void main (String[] args) {
/*  3*/         int i;
/*  4*/         ListNode list = makeEmptyList();
/*  5*/         ListNode x;
/*  6*/         x = list;
/*  7*/         for (i = 1; i <= 9; i++) {
/*  8*/             x = addNode(x, i);
/*  9*/         }
/* 10*/         printList(list);
/* 11*/     }
/* 12*/     static ListNode makeEmptyList () {
/* 13*/         int DUMMY = 0;
/* 14*/         return new ListNode(DUMMY, null);
/* 15*/     }
/* 16*/     static ListNode addNode (ListNode x, int data) {
/* 17*/         x.next = new ListNode(data, null);
/* 18*/         return x.next;
/* 19*/     }
/* 20*/     static void printList (ListNode list) {
/* 21*/         ListNode x;
/* 22*/         for (x = list.next; x != null; x = x.next) {
/* 23*/             System.out.print(" " + x.data);
/* 24*/         }
/* 25*/         System.out.println();
/* 26*/     }
/* 27*/ }

以下のプログラムは、前回のプログラム ListDelete を書き直したものです。 ListDelete は、リスト [1, 2, 3] の先頭の要素を削除するものでした。

メソッド deleteNode は、リストの節点の次の節点を削除するものです。引数はリストの節点です。

/*  1*/ class ListDelete2 {
/*  2*/     public static void main (String[] args) {
/*  3*/         ListNode list = makeEmptyList();
/*  4*/         ListNode x;
/*  5*/         x = list;
/*  6*/         x = addNode(x, 1);
/*  7*/         x = addNode(x, 2);
/*  8*/         x = addNode(x, 3);
/*  9*/         x = list;
/* 10*/         deleteNode(x);
/* 11*/         printList(list);
/* 12*/     }
/* 13*/     static ListNode makeEmptyList () {
/* 14*/         int DUMMY = 0;
/* 15*/         return new ListNode(DUMMY, null);
/* 16*/     }
/* 17*/     static ListNode addNode (ListNode x, int data) {
/* 18*/         x.next = new ListNode(data, null);
/* 19*/         return x.next;
/* 20*/     }
/* 21*/     static void deleteNode (ListNode x) {
/* 22*/         x.next = x.next.next;
/* 23*/     }
/* 24*/     static void printList (ListNode list) {
/* 25*/         ListNode x;
/* 26*/         for (x = list.next; x != null; x = x.next) {
/* 27*/             System.out.print(" " + x.data);
/* 28*/         }
/* 29*/         System.out.println();
/* 30*/     }
/* 31*/ }

以下のプログラムは、前回のプログラム ListInsert を書き直したものです。 ListInsert は、リスト [2, 3] の先頭に要素 1 を挿入するものでした。

メソッド insertNode は、リストの節点の次に節点を挿入するものです。引数はリストの節点と、挿入する節点のデータです。

/*  1*/ class ListInsert2 {
/*  2*/     public static void main (String[] args) {
/*  3*/         ListNode list = makeEmptyList();
/*  4*/         ListNode x;
/*  5*/         x = list;
/*  6*/         x = addNode(x, 2);
/*  7*/         x = addNode(x, 3);
/*  8*/         x = list;
/*  9*/         insertNode(x, 1);
/* 10*/         printList(list);
/* 11*/     }
/* 12*/     static ListNode makeEmptyList () {
/* 13*/         int DUMMY = 0;
/* 14*/         return new ListNode(DUMMY, null);
/* 15*/     }
/* 16*/     static ListNode addNode (ListNode x, int data) {
/* 17*/         x.next = new ListNode(data, null);
/* 18*/         return x.next;
/* 19*/     }
/* 20*/     static void insertNode (ListNode x, int data) {
/* 21*/         x.next = new ListNode(data, x.next);
/* 22*/     }
/* 23*/     static void printList (ListNode list) {
/* 24*/         ListNode x;
/* 25*/         for (x = list.next; x != null; x = x.next) {
/* 26*/             System.out.print(" " + x.data);
/* 27*/         }
/* 28*/         System.out.println();
/* 29*/     }
/* 30*/ }

8.2 演習8

リストの長さを求めるメソッド listLength を定義してください。プログラムは穴埋めとします。前回のプログラム ListLength を参考にしてください。

class ListLength2 {
    public static void main (String[] args) {
        int i;
        ListNode list = makeEmptyList();
        ListNode x;
        x = list;
        for (i = 1; i <= 9; i++) {
            x = addNode(x, i);
        }
        System.out.println(listLength(list));
    }
    static ListNode makeEmptyList () {
        int DUMMY = 0;
        return new ListNode(DUMMY, null);
    }
    static ListNode addNode (ListNode x, int data) {
        x.next = new ListNode(data, null);
        return x.next;
    }

    ???

}

8.3 レポート課題

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

コンピュータIIIB（Javaアルゴリズム）第8回

8.1 リスト（2）

8.1.1 リストのコピー

8.1.2 リストの連接

8.1.3 リストの併合

8.1.4 リストとメソッド

8.2 演習8

8.3 レポート課題

8.4 参考文献