6/24(月)の大雨による休講で7/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
    }                 // ダミー
}

今日は、テスト返しの残り時間で、4年の情報構造論で、リスト構造などの内容を進める前に、3年プログラミング応用でクラスなどに自信がない人向けの簡単レクチャ。

クラスは、データ構造と手続き

例えば、名前と年齢のデータをクラスで扱うのであれば、以下のようなコードが基本となるだろう。

import java.util.*;

class NameAge {
    String name ;          // インスタンス変数
    int    age ;           // インスタンス変数
    static int count = 0 ; // クラス変数
    // コンストラクタ
    NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

実行結果
tsaitoh,59
member = 1
age = 59
tomoko,48
member = 2

クラスとは、データ構造(オブジェクト)とそのデータ構造を扱うための関数(メソッド)をまとめて扱う。

クラス NameAge の中で宣言されている、NameAge() の関数は、オブジェクトを初期化するための関数(メソッド)であり、特にコンストラクタと呼ばれる。

実際にデータを保存するための tsaitoh や tomoko とよばれる変数に NameAge オブジェクトの実体を作る時には 「new クラス名」 とやることで、初期化ができる。

イメージでは、下図のようなデータ構造ができあがる。

でも、年齢の覚え方は、将来的に誕生日を覚えるように変化するかもしれない。この際に、Main 関数の中で age を使うと後で混乱の元になるかもしれない。こういう時は、NameAge クラス以外では中身を勝手に使わせないために、インスタンス変数などに public / private といったアクセス制限を加える。

import java.util.*;
class NameAge {
    private String name ;          // インスタンス変数
    private int    age ;           // インスタンス変数
    public  static int count = 0 ; // クラス変数
    // コンストラクタ
    public  NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    public void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ここがエラーになる。NameAge::age は private 
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

クラス自体も、public class NameAge … のように宣言することもあるが、public なクラスは 1つ の *.java ファイルの中に1つしか書けないというルールがあるので要注意。

中間試験問題の回答

import java.util.*;
import java.util.* ;

class Item {
    int    id ;
    String name ;
    int    price ;
    Item( int i , String n , int p ) {
        this.id    = i ;
        this.name  = n ;
        this.price = p ;
    }
} ;

class Buy {
    int    id ;
    int    count ;
    Buy( int i , int n ) {
        this.id    = i ;
        this.count = n ;
    }
} ;

public class Main {
    static Item[] item_list = {
        new Item( 1010 , "orange" ,      50 ) ,
        new Item( 1020 , "apple" ,      100 ) ,
        new Item( 1022 , "pineapple" , 1000 ) ,
    } ;
    static Buy[] buy_list = {
        new Buy( 1010 , 5 ) ,
        new Buy( 1020 , 3 ) ,
        new Buy( 1022 , 1 ) ,
    } ;
    public static void main( String[] args ) {
        System.out.println( total_price( item_list , buy_list ) ) ;
    }
    static int total_price( Item[] i_list , Buy[] b_list ) {
        int sum = 0 ;
        for( Item item : i_list )
            for( Buy buy : b_list )
                if ( item.id == buy.id )
                    sum += item.price * buy.count ;
        return sum ;
    }
    // static int total_price( Item[] i_list , Buy[] b_list ) {
    //     int sum = 0 ;
    //     for( int i = 0 ; i < i_list.length ; i++ )
    //         for( int j = 0 ; j < b_list.length ; j++ )
    //             if ( i_list[ i ].id == b_list[ j ].id )
    //                 sum += i_list[ i ].price * b_list[ j ].count ;
    //     return sum ;
    // }
}

練習問題

科目(Subject)と学生(Student)の情報があり、科目を受講した成績(Result)で成績を管理している。
このデータを管理するためのクラスを宣言し、下に示すような出力が得られるプログラムを作成せよ。

今回の中間テストで成績が悪かった人は、テスト前に示したレポート課題ではなく下記の課題で提出してよいこととする。

科目: Subject
id    name       teacher   // Subject[] subject_table = {
10010 情報構造論 t-saitoh   //    new Subject( 10010 , "情報構造論" , "t-saitoh" ) ,
10020 電気磁気学 takaku     //    new Subject( ....
10030 電気回路   komatsu    // } ;

成績: Result
s_id  id         point      // Result[] result_table = {
16213 10020      83         //    new Result( 16213 , 10020 , 83 ) ,
18348 10010      95         //    new Result( ...
17101 10030      64         // } ;
16213 10010      89

学生: Student
s_id  name       age        // Student[] student_table = {
16213 斉藤太郎   18          //    new Student( 16213 , "斉藤太郎" , 18 ) ,
17101 山田次郎   19          //    new Student( ...
18348 渡辺花子   18          // } ;

以下のようなデータが出力されること
斉藤太郎 電気磁気学 83
渡辺花子 情報構造論 95
山田次郎 電気回路   64
斉藤太郎 情報構造論 89