プログラムは書いて・動かして・間違って・直す が重要ということで、以下に前期期末試験前までに取り組むレポート課題をしめす。

レポート課題(プログラム例)

Java を用いて、後に示すデータ処理をするためのリスト構造を定義し、与えられたデータを追加していく処理を作成せよ。

課題の説明用に、複素数のリスト構造を定義し、指定した絶対値以下の複素数を抜き出す関数をつくった例を示す。

import java.util.* ;

class ComplexListNode {
   double          re ;
   double          im ;
   ComplexListNode next ;
   ComplexListNode( double r , double i , ComplexListNode n ) {
       this.re = r ;
       this.im = i ;
       this.next = n ;
   }
} ;

public class Main {
    // 先頭からデータを挿入する方式
    static ComplexListNode top = null ;
    // 全リストを表示する処理
    static void print( ComplexListNode p ) {
        for( ; p != null ; p = p.next ) {
            System.out.println( "(" + p.re + ")+j(" + p.im + ")" ) ;
        }
    }
    // top に要素を追加する処理(先頭に入れる)
    static void add( double r , double i ) {
        top = new ComplexListNode( r , i , top ) ;
    }
    // 特定のデータを対象にした処理の例
    static ComplexListNode filter_lessthan( ComplexListNode p , double v_abs ) {
        ComplexListNode ans = null ;
        for( ; p != null ; p = p.next ) {
            if ( Math.sqrt( p.re * p.re + p.im * p.im ) <= v_abs )
                ans = new ComplexListNode( p.re , p.im , ans ) ;
        }
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        add( 1.0 , 2.0 ) ;
        add( -1.0 , -1.0 ) ;
        add( 2.0 , -1.0 ) ;
        add( 1.0 , 0 ) ;
        print( top ) ;
        
        ComplexListNode less_than_2 = filter_lessthan( top , 2 ) ;
        System.out.println( "less than 2" ) ;
        print( less_than_2 ) ;
    }
}

((( 実行結果の例 )))
(1.0)+j(0.0)
(2.0)+j(-1.0)
(-1.0)+j(-1.0)
(1.0)+j(2.0)
less than 2
(-1.0)+j(-1.0)
(1.0)+j(0.0)

レポート内容

上記のプログラムをまねて、以下のレポート課題を作成すること。テーマは ((出席番号-1)%3+1) を選択すること。

1. 年号のデータが、年号の名称と年号の始まりの年月日がYYYYMMDD形式で
   • “Meiji”,18681023
   • “Taisho”,19120730
   • “Showa”,19261225
   • “Heisei”,19890108
   • “Reiwa”,20190501

   の様に与えられる。このデータ構造を覚えるリスト構造を作成せよ。また ListNode のデータで、西暦の日付のリストが seireki_list = new ListNode( 19650207, new ListNode( 20030903 , null ) ) ; のように与えられたら、そのデータを和暦で表示するプログラムを作成せよ。 (参考2023年前期期末)

2. 市町村名,月,日,最高気温,最低気温のデータが、
   • “fukui”,8月,4日,27.6℃,22.3℃
   • “fukui”,8月,5日,31.5℃,23.3℃
   • “fukui”,8月,7日,34.7℃,25.9℃
   • “obama”,8月,6日,34.2℃,23.9℃

   の様に与えられる。このデータ構造で覚えるリスト構造を作成せよ。また、この中から真夏日(最高気温が30℃以上)でかつ熱帯夜(最低気温が25℃以上)の日のリストを抽出し表示するプログラムを作成せよ。(参考2022年前期期末)

3. ホスト名と、IPアドレス(0～255までの8bitの値✕4個で与えるものとする)のデータ構造で、
   • “www.fukui-nct.ac.jp”,104,215,54,205
   • “perrine.tsaitoh.net”,192,168,11,2
   • “dns.fukui-nct.ac.jp”,10,10,21,51
   • “dns.google.com”,8,8,8,8

   の様に与えられる。このデータ構造をリスト構造で覚えるプログラムを作成せよ。また、この中からプライベートアドレスのリストを抽出し表示するプログラムを作成せよ。プライベートアドレスは 10.x.x.x, 172.16～31.x.x,192.168.x.x とする。(参考2019年前期期末)

プログラムを作るにあたり、リスト構造には add( 与えられたデータ… ) のように呼び出してリストに追加すること。この時、生成されるリストが、登録の逆順になるか(先頭に挿入)、登録順(末尾に追加)になるかは、自分の理解度に応じて選択すること。抽出する処理を書く場合も登録順序どおりにするかは自分の理解度に応じて選べばよい。

また、理解度に自信がある人は、add() などの処理を「オブジェクト指向」のように記述する方法を検討すること。
あくまで、リスト構造の理解を目的とするため、ArrayList<型> , LinkedList<型> のようなクラスは使わないこと。(ただし考察にて記述性の対比の対象として使うのはOK。複素数の場合の LinkedList を使った例を以下に示す。)

import java.util.* ;
import java.util.stream.Collectors ;

class Complex {
   double re ;
   double im ;
   Complex( double r , double i ) {
       this.re = r ;
       this.im = i ;
   }
   public double abs() {
       return Math.sqrt( re * re + im * im ) ;
   }
   @Override
   public String toString() {
       return "(" + re + ")+j(" + im + ")" ;
   }
} ;

public class Main {
    public static LinkedList<Complex> top = new LinkedList<Complex>() ;

    // 絶対値が指定した値以下の要素だけを集める関数
    public static LinkedList<Complex> filter_lessthan(
                            LinkedList<Complex> list , double v_abs ) {
        var ans = new LinkedList() ;
        for( var c : list ) {
            if ( Math.sqrt( c.re * c.re + c.im * c.im ) <= v_abs )
                ans.add( c ) ;
        }
        return ans ;
    }
    public static void main( String[] args ) throws Exception {
        // リストに複素数を追加
        top.add( new Complex(  1.0 ,  2.0 ) ) ;
        top.add( new Complex( -1.0 , -1.0 ) ) ;
        top.add( new Complex(  2.0 , -1.0 ) ) ;
        top.add( new Complex(  1.0 ,  0   ) ) ;
        
        for( var c : top ) {
            System.out.println( c ) ;
        }
        System.out.println( "---" ) ;
        // static な関数でフィルタリング
        for( var c : filter_lessthan( top , 2.0 ) ) {
            System.out.println( c ) ;
        }
        /* Stream API を使ってフィルタリング
        for( var c : top.stream()                    // LinkedList を Stream に変換
                     .filter( c->c.abs() < 2.0 )     // filter条件をラムダ式で渡す
                     .collect( Collectors.toList() ) // Collectorsで結果を集める
            ) {
            System.out.println( c ) ;
        }
        */
    }
}

• LinkedListを使ったプログラム例(Paiza.io)

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

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

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

ヒープメモリとは

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