テスト前のリスト導入の復習

前回のリスト構造の導入では、配列のデータに次のデータの入っている番号を添えることで途中にデータを挿入できるデータ構造の説明をした。

また、それをクラスを用いたプログラムを示した。

ヒープメモリとは

Javaでは、すべてのオブジェクトはヒープメモリに保存する。

ヒープメモリとは、一時的なデータの保管場所であり、new 演算子でデータを保存する場所を確保する。

Javaでは、分かり難いのでC言語で説明を行う。malloc() は、指定されたバイト数のメモリをヒープ領域に確保する命令。malloc() に失敗すると、NULL が返ってくる。また、使い終わったら malloc() の領域は free() 命令で返却が必要となる。

((( 配列をヒープメモリで確保 )))
#include <stdio.h>
#include <stdlib.h>

int main() {
   int a[ 5 ] = { 1 , 2 , 3 , 4 , 5 } ;
   int* b ;
   if ( (b = (int*)malloc( sizeof( int ) * 5 )) != NULL ) {
      for( int i = 0 ; i < 5 ; i++ )
         b[ i ] = i + 1 ;
      free( b ) ;    // malloc() で確保したメモリ領域は返却が必要
   }
   return 0 ;
}

((( オブジェクトをヒープメモリに確保 )))
struct Complex {
   double re ;
   double im ;
} ;
int main() {
   struct Complex* c ;
   if ( (c = (struct Complex*)malloc( sizeof( struct Complex ) )) != NULL ) {
      c->re = 1.23 ;
      c->im = 2.34 ;
      free( c ) ;
      return 0 ;
   } else {
      printf( "No heap memory\n" ) ;
      return 1 ;
   }
}

((( 上記C言語をJavaで書くと )))
class Complex {
   double re ;
   double im ;
   Complex( double r , double i ) {
      this.re = r ;
      this.im = i ;
   }
}

public class Main {
   public static void main( String[] args ) {
      try {
         Complex c = new Complex( 1.23 , 2.34 ) ;
                    // Javaではヒープメモリが確保に失敗したら、
                    // OutOfMemoryErrorの例外が発生する。

         c = null ; // free()はJavaでは不要
                    // nullを代入してもいい。
      } catch( OutOfMemoryError e ) {
         System.out.println( "No heap memory" ) ;
         System.exit( 1 ) ;
      }
   }
}

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存する方法を、next の部分を次のデータへの参照を用いるように、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;   // データ部分
    ListNode next ;   // 次のデータへの参照
    // コンストラクタ
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
        // 途中にデータを入れる
        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

リスト操作

リスト構造に慣れるために簡単な練習をしてみよう。リスト構造のデータに対するメソッドをいくつか作ってみよう。print() や sum() を参考に、データ数を求める count() , 最大値を求める max() , データを検索する find() を完成させてみよう。

class ListNode {
    (略)
} ;

public class Main {
    static void print( ListNode p ) {   // リストを表示
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }

    static int sum( ListNode p ) {      // リストの合計を求める
        int s = 0 ;
        for( ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }

    static int count( ListNode p ) {    // データ件数を数える

    }

    static int max( ListNode p ) {      // データの最大値を求める

    }

    static boolean find( ListNode p , int key ) { // データ列の中から特定のデータを探す
                                                  //   見つかったら true , 見つからなければ false
    }
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        print( top ) ;
        System.out.println( "合計:" + sum( top ) ) ;
        System.out.println( "件数:" + count( top ) ) ;
        System.out.println( "最大:" + max( top ) ) ;
        System.out.println( "検索:" + (find( top , 22 )
                                       ? "みつかった" : "みつからない" ) ) ;
    }
}

オブジェクト指向っぽく書いてみる

前述のプログラムでは、print( top ) のように使う static な関数としてプログラムを書いていた。しかし、オブジェクト指向であれば、オブジェクトに対するメソッドだと top.print() のように書きたい。この場合だと、以下のように書くかもしれない。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    int sum() {    // リストの合計を求める
        int  s = 0 ;
        for( ListNode p = this ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = null ;
        list_empty.print() ;  // 実行時エラー java.lang.NullPointerException ぬるぽ！
    }
}

しかし、データ件数 0件 に対してメソッドを呼び出せない。

ListNode と List というクラスで書いてみる

ひとつの方法として、リストの先頭だけのデータ構造を宣言する方法もある。

class ListNode {
    int   data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

class List {
    ListNode top ;
    List( ListNode p ) {
        this.top = p ;
    }
    void print() {
        for( ListNode p = top ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        List list = new List( new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ) ;
        list.print() ;
        
        List list_empty = new List( null ) ;
        list_empty.print() ;
    }
}

しかし、List と ListNode の2つのデータの型でプログラムを書くのは面倒くさい。

授業ではシンプルに説明したいので、今後はこの方法は極力避けていく。

先頭にダミーデータを入れる

複数のクラス宣言するぐらいなら、リストデータの先頭は必ずダミーにしておく方法もあるだろう。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this.next ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode list = new ListNode( -1 , null ) ;
        list.next = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = new ListNode( -1 , null ) ;
        list_empty.print() ;
    }
}

以降、必要に応じて、先頭にダミーを入れる手法も取り混ぜながらプログラムを書くこととする。

入力データをリストに追加

入力しながらデータをリストに格納する処理を考えてみる。

リストでデータを追加保存するのであれば、一番簡単なプログラムは、以下のように先頭にデータを入れていく方法だろう。

class ListNode {
    (略)
    void print() {
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data ) ;
        System.out.println() ;
    }
} ;
    
public class Main {
    public static void main(String[] args) throws Exception {
        int[] inputs = { 11 , 22 , 33 } ;
        ListNode top = null ;

        for( int datum : inputs )
            top = new ListNode( datum , top ) ;
        top.print() ;
    }
}

でもこの方法だと、先頭にデータを入れていくため、保存されたデータは逆順になってしまう。

末尾にデータを入れる

逆順になるのを避けるのであれば、データを末尾に追加する方法があるだろう。ただし初期状態でデータが0件だと処理が書きづらいので、先頭にダミーを入れておく方法で書いてみる。

public class Main {
    public static void main(String[] args) throws Exception {
        int[] test_data = { 11 , 22 , 33 } ;

        ListNode top = new ListNode( -1 , null ) ; // ダミー
        ListNode tail = top ;
        for( int x : test_data ) {
            tail.next = new ListNode( x , null ) ;
            tail = tail.next ;
        }
        top.print() ; // -1   11  22  33
    }                 // ダミー
}

前期中間試験の返却に伴い、補足説明。

C言語,Javaにおける文の定義

テストの時に、下記のようなプログラムで piyo() は、for の範囲？みたいな質問があったので、補足説明

for( ... ; ... ; ... )
   if ( ... )
      foo = bar ;
   else {
      baz() ;
      hoge() ;
   }
piyo() ;

C言語やJavaにおける文の定義は、以下の通り

文 ::= 式 ;    // 単文
     | ;       // 空文
     | { 文 文 ... }        // 複文
     | for( .. ; .. ; .. ) 文   // 制御構文
     | do 文 while( 式 ) ;
     | if ( 式 ) 文 [ else 文 ]
     ;

こういった文の範囲の誤解を避けるためのものが、インデント。

正しいインデントをつける習慣が重要。

• 字下げスタイル

Javaにおけるクラスとデータ構造のイメージ

この後のリスト構造の説明でもオブジェクトがどのように保存されるかを理解するのは重要なので、オブジェクトの説明。

Java では、class 宣言されたデータ構造は、ヒープメモリと呼ばれるデータ領域に保存されている。

class A {
   int data ;
   A( int value ) {
      this.data = value ;
   }
} ;

public class Main {
   public static void main( String[] args ) {
      A a = new A( 123 ) ;
   }
}

ここで、new 演算子は、指定されたオブジェクトをヒープメモリ上に確保する。そして、そのデータの入っている領域アドレスを、インスタンスの変数 a に代入している。

テストで出題した例であれば、

class IdNameAge {
   int    id ;
   String name ;
   Age    age ;
   IdNameAge( int i , String n , int a ) {
      this.id   = i ;
      this.name = n ;
      this.age  = a ;
   }
} ;

IdNameAge[] = people = {
   new IdNameAge( 1001 , "saitoh" ,  60 ) ,
   new IdNameAge( 1002 , "tomoko" ,  49 ) ,
   new IdNameAge( 1003 , "mitsuki" , 26 ) ,
} ;

Integer 型も、整数データを記憶するけど、オブジェクト型である。

ただし、Integer 型を常にヒープメモリに保存するのは、効率が悪いので、-128～127までの値ではIntegerオブジェクトは内部でキャッシュされる。Integer y = 123 ; 書いてはいるけど本来であれば、Integer y = new Integer( 123 ) ;  と書く必要があった。しかしJava5以降に、オートボクシングと呼ばれる機能があるため Integer y = 123 のように書けるし、こう書く方が推奨されている。

public class Main {
    public static void main(String[] args) {
        // Your code here!
        Integer sx = 123 ;
        Integer sy = 123 ;
        System.out.println( sx == sy ) ; // true
        Integer fx = 12345 ;
        Integer fy = 12345 ;
        System.out.println( fx == fy ) ; // false
    }
}