コンパイラの処理の流れ

構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。

Cコンパイラのソース
　　↓
プリプロセッサ (#define,#includeなどの処理)
　　↓
コンパイラ
・字句解析(ソースコードをトークンに切り分ける)
・構文解析(トークンから構文木を生成)
・最適化(命令を効率よく動かすために命令を早い命令に書き換え)
・コード生成(構文木から中間コードを生成)
　　|
　　|　リンカでライブラリと結合
　（+）←---ライブラリ
　　↓ 
　機械語

バイトコードインタプリタ

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
　↓       Java コンパイラ
foo.class (中間コード)
　↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

字句解析と構文解析

トークンと正規表現(字句解析)

字句解析でトークンを表現するために、規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言　　　  「abd|acd」は、abd または acd にマッチする。
グループ化　「a(b|c)d」は、真ん中の c|b をグループ化
量化　　　　パターンの後ろに、繰り返し何回を指定
　　　　　　? 直前パターンが0個か1個
　　　　　　　「colou?r」
　　　　　　* 直前パターンが0個以上繰り返す
　　　　　　　「go*gle」は、ggle,gogle,google
　　　　　　+ 直前パターンが1個以上繰り返す
　　　　　　　「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
　　　　　　「[0-9]+」012,31415,...数字の列
^　　　　　行頭にマッチ
$　　　　　行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

• 情報処理技術者試験で出題された正規表現の問題と解説

構文とバッカス記法

言語の文法(構文)を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>    【要注意】わざと間違っている部分あり
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。

import java.util.*;

class ExpTreeNode {
    String      op_val ;
    ExpTreeNode left ;
    ExpTreeNode right ;
    
    ExpTreeNode( String op , ExpTreeNode l , ExpTreeNode r ) {
        this.op_val = op ;
        this.left   = l ;
        this.right  = r ;
    }
    ExpTreeNode( String val ) {
        this.op_val = val ;
        this.left   = null ;
        this.right  = null ;
    }
}

public class Main {
    public static int eval( ExpTreeNode p ) {
        if ( p.left == null && p.right == null ) {
            return Integer.parseInt( p.op_val ) ;
        } else {
            int l_val = eval( p.left) ;
            int r_val = eval( p.right ) ;
            switch( p.op_val ) {
            case "+" : return l_val + r_val ;
            case "*" : return l_val * r_val ;
            }
            return -1 ; // error
        }
    }
    public static void main(String[] args) throws Exception {
        ExpTreeNode top =
            new ExpTreeNode( "+" ,
                             new ExpTreeNode( "1" ) ,
                             new ExpTreeNode( "*" ,
                                              new ExpTreeNode( "2" ) ,
                                              new ExpTreeNode( "3" ) ) ) ;
        
        System.out.println( eval( top ) ) ;
    }
}

• 2分木による構文木(Paiza.io)

オブジェクト指向を使った構文木(テスト範囲外)

前述の2分木を用いた構文木では、式を構成する「整数値」の式、「式 演算子 式」の演算式の二つのパターンを、無理やり１つのクラスで扱っていた。整数値と演算子の文字列の違いがあるため、数値も文字列で保存したものを parseInt() で数値に変換している。

こういった、大きくは式と分類できるけど、数値を表す式、演算子からなる式と異なるデータの場合、Java では、オブジェクト指向プログラミングの抽象クラスと仮想関数のテクニックを用いる。式を表現する基底クラス ExpNode から、数値を表す ExpNodeInteger , 演算子からなる式を表す ExpNodeOperator を派生させ、式の値を求める際には、各クラスに応じた計算処理を行う仮想関数 eval() を使って処理を行っている。

import java.util.* ;

// 抽象基底クラス
abstract class ExpNode {
    abstract public int eval() ;
}

// 整数で具体化
class ExpNodeInteger extends ExpNode {
    int  value ;
    
    ExpNodeInteger( int i ) {
        this.value = i ;
    }
    // 仮想関数
    public int eval() {
        return this.value ;
    }
}

// 演算子で具体化
class ExpNodeOperator extends ExpNode {
    String  op ;
    ExpNode left ;
    ExpNode right ;
    
    ExpNodeOperator( String s , ExpNode l , ExpNode r ) {
        this.op    = s ;
        this.left  = l ;
        this.right = r ;
    }
    // 仮想関数
    public int eval() {
        int l_val = this.left.eval() ;
        int r_val = this.right.eval() ;
        switch( this.op ) {
        case "+" : return l_val + r_val ;
        case "*" : return l_val * r_val ;
        }
        return -1 ;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        ExpNode top =
            new ExpNodeOperator( "+" ,
                                 new ExpNodeInteger( 1 ) ,
                                 new ExpNodeOperator( "*" ,
                                                      new ExpNodeInteger( 2 ) ,
                                                      new ExpNodeInteger( 3 ) ) ) ;

        System.out.println( top.eval() ) ;
    }
}

データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:小さい子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。

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

class TreeNode {
    String qa ;
    TreeNode    yes ;
    TreeNode    no ;
    
    TreeNode( String s , TreeNode y , TreeNode n ) {
        this.qa  = s ;
        this.yes = y ;
        this.no  = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner( System.in ) ;
        TreeNode top =
            new TreeNode( "38.5℃以上の発熱がある?" ,
                          new TreeNode( "胸がひぃひぃ?" ,
                                        new TreeNode( "速攻で病院" ,   null , null ) ,
                                        new TreeNode( "解熱剤で病院" , null , null ) ) ,
                          new TreeNode( "元気がある?" ,
                                        new TreeNode( "様子をみる",    null , null ) ,
                                        new TreeNode( "氷枕で病院",    null , null ) ) ) ;
        TreeNode p = top ;
        while( p.yes != null || p.no != null ) {
            System.out.println( "Question:" + p.qa ) ;
            if ( sc.nextInt() == 1 ) {
                System.out.println( "yes" ) ;
                p = p.yes ;
            } else {
                System.out.println( "no" ) ;
                p = p.no ;
            }
        }
        System.out.println( "Answer:" + p.qa ) ;
    }
}

• 意思決定木(Paiza.io)

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",  NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",  NULL,NULL ) ,
                    dtree( "氷枕で病院",  NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

• decision-tree.cxx

---

2分木の応用として次週以降に式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

2分探索木にデータを追加

前回の2分探索木では、基本的な説明ということで、木の生成では直接木構造を生成していた。しかし、本来であれば、扱うデータに応じて木を生成することが求められる。

Javaの場合

以下の Javaのプログラムの関数 entry( … ) では、再帰を使いながら、value を追加した木を返す関数で記述した。

import java.util.*;

class BTreeNode {
    int       data ;
    BTreeNode left ;
    BTreeNode right ;
    
    BTreeNode( int x , BTreeNode l , BTreeNode r ) {
        this.data  = x ;
        this.left  = l ;
        this.right = r ;
    }
}
public class Main {
    public static void print_tree( BTreeNode p ) {
        // 木構造をわかりやすくするために()をつけて表示
        if ( p != null ) {
            System.out.print( "(" ) ;
            print_tree( p.left ) ;
            System.out.print( p.data ) ;
            print_tree( p.right ) ;
            System.out.print( ")" ) ;
        }
    }
    public static BTreeNode entry( BTreeNode p , int value ) {
        if ( p == null ) {
            return new BTreeNode( value , null , null ) ;
        } else {
            if ( p.data == value )
                ; // 何もしない
            else if ( p.data > value )
                p.left = entry( p.left , value ) ;
            else
                p.right = entry( p.right , value ) ;
            return p ;
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 42 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 13 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
}
// 動作結果
// (((13)27(38))42((64)72(81)))

• 2分探索木へのデータの追加(Paiza.io)

しかしながらこのプログラムでは、以下のように小さい順序でデータを与えると、右に伸びる木が作られてしまう。

    // 不均一な木ができる場合
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 13 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 42 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
    // 動作結果
    // (13(27(38(42(64(72(81)))))))

このような不均一な木が生成されてしまうと、本来であればデータ探索の処理時間は O( log N ) であるが、最悪の状態では O( N ) となってしまう。

AVL木

こういった偏った木が生成されてしまった時には、以下のような処理を加えると、不均一な状態を改善できる。

depth() 関数は与えられた木の深さを求める関数であり、左枝と右枝が大きく違う場所で 木の右回転を行う rotate_right() を実行する。

public class Main {
    public static int depth( BTreeNode p ) { // 木の深さを求める
        if ( p == null ) {
            return 0 ;
        } else {
            int l = depth( p.left ) ;
            int r = depth( p.right ) ;
            if ( l > r )
                return 1 + l ;
            else
                return 1 + r ;
        }
    }
    public static BTreeNode rotate_right( BTreeNode p ) {
        BTreeNode q = p.left ;      //      p
        BTreeNode r = q.right ;     //    ／ ＼
        q.right = p ;               //   q
        p.left  = r ;               // ／ ＼
        return q ;                  //      r
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 86 ) ;
        top = entry( top , 53 ) ;
        top = entry( top , 92 ) ;
        top = entry( top , 11 ) ;
        top = entry( top , 65 ) ;
        top = entry( top , 22 ) ;
        // 不均一な状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
        // top の右回転を実行
        top = rotate_right( top ) ;
        // 改善された状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
    }
}

• AVL木と右回転(Paiza.io)

上記のプログラムでは、左枝が3段で右枝が1段であり不均一な状態となっている。

そこで、最上段の86の左枝を上に移動させるように枝の繋ぎ方を rotate_right() により変更している。実際には、繋ぎ変えを左回転させる処理も作る必要がある。

このように、木の枝の深さが不均一な場所で、このような処理を加えて均一化を図った木構造は AVL 木と呼ぶ。

AVL木は、考案した Velski と Landis の名前が由来(Adelson-Velskii and Landis’ tree)

2分ヒープ(binary heap)

2分探索木では、１つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の１つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。

このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、入れるべきノードの場所でのデータの入れ替えで実現できるため O( log( N ) )で挿入が可能となる。

import java.util.*;

public class Main {
    public static int find_heap( int[] array , int idx , int key ) {
        while( idx < array.length ) { if ( array[ idx ] == key ) return idx ; // 見つかった else if ( array[ idx ] > key )
                idx = idx*2 + 1 ;
            else
                idx = idx*2 + 2 ;
        }
        return -1 ; // 見つからなかった
    }
    public static void main(String[] args) throws Exception {
        int[] a = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;
        System.out.println( find_heap( a , 0 , 22 ) ) ;
    }
}

• 2分ヒープ(Paiza.io)

レポート課題

以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。

1. 名前(name)と電話番号(phone)
2. 名前(name)と誕生日(year,mon,day)
3. 名前(name)とメールアドレス(mail)

プログラムは以下の機能を持つこと。

• 1行1件でデータを入力し、2分木に追加できること。
• 全データを昇順(or降順)で表示できること。
• 検索条件を入力し、目的のデータを探せること。

レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)

// 2分探索法
import java.util.*;

public class Main {
    public static int bin_search( int[] a , int key , int L , int R ) {
        // Lは探す範囲の左端
        // Rは探す範囲の右端+1(注意!!)
        while( R > L ) {
            int m = (L + R) / 2 ;
            if ( a[m] == key )
                return m ;
            else if ( a[m] > key )
                R = m ;
            else
                L = m + 1 ;
        }
        return -1 ;
    }
    public static void main(String[] args) throws Exception {
        int[] array = {
            11, 13, 27, 38, 42, 64, 72, 81
        } ;
        System.out.println( bin_search( array , 64 , 0 , array.length ) ) ;
        System.out.println( bin_search( array , 14 , 0 , array.length ) ) ;
    }
}

• Javaによる2分探索法

// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;

int bin_search( int a[] , int key , int L , int R ) {
   // Lは、範囲の左端
   // Rは、範囲の右端+1 (注意!!)
   while( R > L ) {
      int m = (L + R) / 2 ;
      if ( a[m] == key )
         return m ;
      else if ( a[m] > key )
         R = m ;
      else
         L = m + 1 ;
   }
   return -1 ; // 見つからなかった
}

void main() {
   printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}

一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか？

2分探索木

ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。

この枝の特徴は何だろうか？この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。

特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。

このデータ構造をプログラムで書いてみよう。

import java.util.*;

class BTreeNode {
    int       data ;
    BTreeNode left ;
    BTreeNode right ;
    
    BTreeNode( int x , BTreeNode l , BTreeNode r ) {
        this.data  = x ;
        this.left  = l ;
        this.right = r ;
    }
}

public class Main {
    public static void print_tree( BTreeNode p ) {
        if ( p != null ) {
            print_tree( p.left ) ;
            System.out.print( p.data + " " ) ;
            print_tree( p.right ) ;
        }
    }
    public static int tree_search( BTreeNode p , int key ) {
        while( p != null ) {
            System.out.println( "p.data=" + p.data + " : key=" + key ) ;
            if ( p.data == key )
                return key ;
            else if ( p.data > key )
                p = p.left ;
            else
                p = p.right ;
        }
        return -1 ;
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top =
            new BTreeNode( 42 ,
                           new BTreeNode( 27 ,
                                          new BTreeNode( 13 , null , null ) ,
                                          new BTreeNode( 38 , null , null ) ) ,
                           new BTreeNode( 72 ,
                                          new BTreeNode( 64 , null , null ) ,
                                          new BTreeNode( 81 , null , null ) ) ) ;
        print_tree( top ) ;
        System.out.println() ;
        if ( tree_search( top , 64 ) >= 0 )
            System.out.println( "Find." ) ;
    }
}

• 2分探索木

struct Tree {
   struct Tree* left ;
   int          data ;
   struct Tree* right ;
} ;

// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
                    int          d ,
                    struct Tree* R ) {
   struct Tree* n = (struct Tree*)malloc(
                       sizeof( struct Tree ) ) ;
   if ( n != NULL ) { /* (A) */
      n->left = L ;
      n->data = d ;
      n->right = R ;
   }
   return n ;
}

// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   // 木構造をtcons()を使って直接生成 (B)
   top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
                       27 ,
                       tcons( NULL , 38 , NULL ) ) ,
                42 ,
                tcons( tcons( NULL , 64 , NULL ) ,
                       72 ,
                       tcons( NULL , 81 , NULL ) ) ) ;
   printf( "%d¥n" , tree_search( top , 64 ) ) ;
}

この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

理解度確認

• main() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。

2分木に対する処理

2分探索木に対する簡単な処理を記述してみよう。

// (略)
public class Main {
    public static void print_tree( BTreeNode p ) {
        if ( p != null ) {
            print_tree( p.left ) ;
            System.out.print( p.data + " " ) ;
            print_tree( p.right ) ;
        }
    }
    public static int count( BTreeNode p ) { // データ件数を数える
        // 考えてみよう
    }
    public static int sum( BTreeNode p ) {   // 合計を求める
        // 考えてみよう
    }
    public static int max( BTreeNode p ) {   // 最大値を探す
         // 考えてみよう
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = /*(略)*/ ;
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( count( top ) ) ; // データ件数を数える
        System.out.println( sum( top ) ) ;   // 合計を求める
        System.out.println( max( top ) ) ;   // 最大値を探す
    }
}

下記のC言語のプログラムをヒントとしておく。

// データを探す
int search( struct Tree* p , int key ) {
   // 見つかったらその値、見つからないと-1
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
   if ( p != NULL ) {
      print( p->left ) ;
      printf( "%d¥n" , p->data ) ;
      print( p->right ) ;
   }
}
// データ件数を求める
int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1
             + count( p->left )
             + count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data
             + count( p->left )
             + count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
   while( p->right != NULL )
      p = p->right ;
   return p->data ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。

リスト構造の利点と欠点

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。(sizeof()はC言語での指定した型のメモリByte数を返す演算子)

配列の場合	リスト構造の場合
	(ただしヒープ管理用メモリ使用量は無視)

シーケンシャルアクセス・ランダムアクセス

もう１つのリストの欠点はシーケンシャルアクセス。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。配列であれば、N/2 番目のデータをO(1)で簡単に取り出せるから2分探索法が有効だが、リスト構造であれば、N/2番目のデータを取り出すのにO(N)かかってしまう。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、１つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも１つ前にもどるだけでも処理時間を改善してみよう。

単純リストから双方向リストへ

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、１つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、１つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか？

この場合、一つ前のデータの場所を覚えているポインタがあれば良い。

Javaの場合

import java.util.*;

class BDListNode {
    BDListNode prev ;
    int        data ;
    BDListNode next ;
    
    BDListNode( BDListNode p , int d , BDListNode n ) {
        this.prev = p ;
        this.data = d ;
        this.next = n ;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BDListNode top
            = new BDListNode( null , 1 ,
                 new BDListNode( null , 2 ,
                    new BDListNode( null , 3 , null ) ) ) ;
        top.next.prev = top ;
        top.next.next.prev = top.next ;
        for( BDListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,3
        for( BDListNode p = top.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 3,2,1
    }
}

• Javaによる双方向リスト

C言語の場合

// 双方向リストの宣言
struct BD_List {
    struct BD_List* prev ; // 1つ前のデータへのポインタ
    int             data ;
    struct BD_List* next ; // 次のデータへのポインタ
} ;

このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。

// リスト生成補助関数
struct BD_List* bd_cons( struct BD_List* p ,
                         int d ,
                         struct BD_List* n ) {
    struct BD_List* ans ;
    ans = (struct BD_List*)malloc(
                         sizeof( struct BD_List ) ) ;
    if ( ans != NULL ) {
        ans->prev = p ;
        ans->data = d ;
        ans->next = n ;
    }
    return ans ;
}
void main() {
    struct BD_List* top ;
    struct BD_List* p ;

    // 順方向のポインタでリストを生成
    top = bd_cons( NULL , 1 ,
          bd_cons( NULL , 2 ,
          bd_cons( NULL , 3 , NULL ) ) ) ;
    // 逆方向のポインタを埋める
    top->next->prev = top ;
    top->next->next->prev = top->next ;

    // リストを辿る処理
    for( p = top ; p->next != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    for(         ; p->prev != NULL ; p = p->prev )
        printf( "%d\n" , p->data ) ;
}

• bidirectional-list.cxx

双方向リストの関数作成

以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。

先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。

Javaの場合

public class Main {
    // 指定したノードの後ろに1件追加
    static void bd_insert( BDListNode p , int d ) {
        p.next = new BDListNode( null , d , p.next ) ;
        p.next.next.prev = p.next ;
        p.next.prev = p ;
    }
    // 指定したノードの後ろを1件削除
    static void bd_delete( BDListNode p ) {
        p.next = p.next.next ;
        p.next.prev = p ;
    }
    public static void main(String[] args) throws Exception {
        // 双方向リストの追加,削除            
        BDListNode top2
            = new BDListNode( null , 1 ,
                 new BDListNode( null , 2 ,
                    new BDListNode( null , 4 , null ) ) ) ;
        top2.next.prev = top2 ;
        top2.next.next.prev = top2.next ;
        
        // 途中に挿入の実験
        bd_insert( top2.next , 3 ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,3,4
        for( BDListNode p = top2.next.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,3,2,1
        
        // 途中を削除の実験
        bd_delete( top2.next ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,4
        for( BDListNode p = top2.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,2,1
    }
}

C言語の場合

// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。
void bd_insert( struct BD_List* p , int d ) {
   struct BD_List*n = bd_cons( p , d , p->next ) ;
   if ( n != NULL ) {
      p->next->prev = n ;
      p->next = n ;
   }
}

// 双方向リストの指定場所 p の後ろのデータを消す処理は？
void bd_delete( struct BD_List* p ) {
   struct BD_List* d = p->next ;
   d->next->prev = p ;
   p->next = d->next ;
   free( d ) ;
}

// この手のリスト処理のプログラムでは、命令の順序が重要となる。
// コツとしては、修正したい箇所の遠くの部分を操作する処理から
// 書いていくと間違いが少ない。

番兵と双方向循環リスト

前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか？
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか？

同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか？
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか？

こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。

しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。

リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。集合処理の記述には、2進数を使った方式やリストを用いた方法が一般的である。以下にその処理について示す。

bit演算子

2進数を用いた集合処理を説明する前に、2進数を使った計算に必要なbit演算子について復習してみる。

bit演算子は、その数値を2進数表記とした時の各ビットをそれぞれAND,OR,EXOR,NOTなどの計算を行う。

bit演算子	計算の意味	関連知識
& bit AND	3 & 5 0011)2 & 0101)2= 0001)2	論理積演算子 if ( a == 1 && b == 2 ) …
| bit OR	3 | 5 0011)2 | 0101)2= 0111)2	論理和演算子 if ( a == 1 || b == 2 ) …
~ bit NOT	~5 ~ 00..00,0101)2= 11..11,1010)2	論理否定演算子 if ( !a == 1 ) …
^ bit EXOR	3 ^ 5 0011)2 ^ 0101)2= 0110)2
<< bit 左シフト	3 << 2 0011)2 << 2 = 001100)2	x << y は と同じ
>> bit 右シフト	12 >> 2 1100)2 >> 2 = 11)2	x >> y は  と同じ

import java.util.*;

public class Main {
   public static void main(String[] args) throws Exception {
      System.out.println( 12 & 5 ) ;    // 1100 & 0101 = 0100 = 4
      System.out.println( 12 | 5 ) ;    // 1100 | 0101 = 1101 = 13
      System.out.println( ~12 & 0xF ) ; // ~1100 & 1111 = 0011 = 3
      System.out.println( 3 << 2 ) ;    // 0011 << 2 = 1100
      System.out.println( 12 >> 2 ) ;   // 1100 >> 2 = 0011
      System.out.println( ~12 + 1 ) ;   // ~0..00001100 + 1 = 1..11110011 + 1 = 1..11110100 = -12
   }
}

論理演算子とbit演算子の違い

論理積,論理和という点では、論理演算子&&,|| と bit演算子&,| は複数桁の2進数で計算する違いと思うかもしれないが、論理演算子&&,|| は若干挙動が違う。論理積&&演算子は、左辺の結果が false だと(結果がfalse確定なので) 右辺の計算式や呼び出されない。同じように論理和||演算子は、左辺の結果が true だと(結果がtrue確定なので) 右辺の計算式は呼び出されない。

import java.util.*;

public class Main {
    static boolean boolean_print( boolean yn ) {
        System.out.print( yn + " " ) ;
        return yn ;
    }
    static int int_print( int yn ) {
        System.out.print( yn + " " ) ;
        return yn ;
    }
    public static void main(String[] args) throws Exception {
        boolean ans ;
        int     x ;
        ans = boolean_print( true )  && boolean_print( true ) ;
        System.out.println() ;
        ans = boolean_print( false ) && boolean_print( true ) ;
        System.out.println() ;

        ans = boolean_print( true )  || boolean_print( true ) ;
        System.out.println() ;
        ans = boolean_print( false ) || boolean_print( true ) ;
        System.out.println() ;

        x = int_print( 0 ) & int_print( 1 ) ;
        System.out.println() ;
        x = int_print( 1 ) | int_print( 0 ) ;
        System.out.println() ;
    }
}

• 論理演算子とbit演算子の違い(Paiza.io)

2進数とビットフィールド

例えば、誕生日の年月日の情報を扱う際、20230726で、2023年7月26日を表現することも多い。

しかしこの方法は、この年月日の情報から年(4桁)、月(2桁)、日(2桁)を取り出す処理では、乗算除算が必要となる。通常のCPUであれば、簡単な乗除算は速度的にも問題はないが、組込み系では処理速度の低下も懸念される。

int ymd = 20230726 ;
int y , m , d ;
y = ymd / 10000 ;
m = ymd / 100 % 100 ;
d = ymd % 100 ;

y = 1965 ; m = 2 ; d = 7 ;
ymd = y * 10000 + m * 100 + d ;

こういった処理を扱う際には、2進数の考え方を使って扱う方法がある。
例えば、年は 0..2047 の範囲と考えれば 11 bit で表現でき、月は1..12の範囲であり 4bit で表現可能であり、日は1..31 で 5bit で表現できる。これを踏まえて、年月日を 11+4+5 = 20bit で表す(YYYY,YYYY,YYYM,MMMD,DDDD)なら、以下のプログラムのように書ける。

int ymd = (2024 << 9) + (7 << 5) + 26 ; // YYYY,YYYY,YYYM,MMMD,DDDD
int y , m , d ;                         // 1111,1101,0000,1111,1010
y = ymd >> 9 ;          // YYYYYYYYYYY
m = (ymd >> 5) & 0xF ;  // YYYYYYYYYYYMMMM & 000000000001111
d = (ymd & 0x1F) ;      // YYYYYYYYYYYMMMMDDDDD & 00000000000000011111

y = 1965 ; m = 2 ; d = 7 ;
ymd = (y << 9) + (m << 5) + d ;

C言語でのビットフィールド

しかし、上記のプログラムでは、いちいち2進数bit演算をイメージする必要があって、プログラムが分かりづらい。C言語では、こういった際にに使うのが ビットフィールドである。

// C言語の場合 (Javaではビットフィールドの構文がない)
struct YMD {
   unsigned int year  : 11 ; // ビットフィールドでは、
   unsigned int month :  4 ; // 構造体の要素を何ビットで保存するのか
   unsigned int day   :  5 ; // 指定することができる。
} ;
struct YMD ymd = { 2023 , 7 , 26 } ;
int y , m , d ;
y = ymd.year ;
m = ymd.month ;
d = ymd.day ;

ymd.year = 1965 ; ymd.month = 2 ; ymd.day = 7 ;

2進数を用いた集合計算

リストによる集合の前に、もっと簡単な集合処理を考える。

最も簡単な方法は、要素に含まれる=true か 含まれない=false を boolean型の配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に true を覚えるものとする。この方法で積集合などを記述した例を以下に示す。

import java.util.*;

public class Main {
    public static void boolarray_print( boolean[] a ) {
        for( int i = 0 ; i < a.length ; i++ )
            System.out.print( a[i] ? "T" : "F" ) ;
        System.out.println() ;
    }
    public static void boolarray_and( boolean[] ans , boolean[] a , boolean[] b ) {
        for( int i = 0 ; i < a.length ; i++ )
            ans[i] = a[i] && b[i] ;
    }
    public static void boolarray_or( boolean[] ans , boolean[] a , boolean[] b ) {
        for( int i = 0 ; i < a.length ; i++ )
            ans[i] = a[i] || b[i] ;
    }
    public static void main(String[] args) throws Exception {
        //               0      1      2      3      4      5      6      7      8      9
        boolean[] ba = { false, true,  true,  true,  false, false, false, false, false, false } ; // {1,2,3}
        boolean[] bb = { false, false, true,  false, true,  false, true,  false, false, false } ; // {2,4,6}
        boolean[] bc = { false, false, false, false, true,  false, true,  false, false, true  } ; // {4,6,9}
        boolean[] ans = new boolean[ 10 ] ;
        boolarray_print( ba ) ;
        boolarray_print( bb ) ;
        boolarray_and( ans , ba , bb ) ;
        boolarray_print( ans ) ;
        
        boolarray_print( bb ) ;
        boolarray_print( bc ) ;
        boolarray_or( ans , bb , bc ) ;
        boolarray_print( ans ) ;
    }
}
FTTTFFFFFF // ba
FFTFTFTFFF // bb
FFTFFFFFFF // ba & bb
FFTFTFTFFF // bb
FFFFTFTFFT // bc
FFTFTFTFFT // bb | bc

しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報をboolean型で保存しているが、実体は整数型で保存しているためメモリの無駄となる。

データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

2進数を用いた集合計算

扱うデータ件数が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∪ bc の計算を行う例である。

import java.util.*;

public class Main {
    static void bitfield_print( int x ) {
        for( int i = 0 ; i < 10 ; i++ )
            System.out.print( ((x & (1 << i)) != 0) ? "T" : "F" ) ;
        System.out.println() ;
    }
    public static void main(String[] args) throws Exception {
        int ba = (1 << 1) | (1 << 2) | (1 << 3) ; // {1,2,3}
        int bb = (1 << 2) | (1 << 4) | (1 << 6) ; // {2,4,6}
        int bc = (1 << 4) | (1 << 6) | (1 << 9) ; // {4,6,9}
        bitfield_print( ba ) ;
        bitfield_print( bb ) ;
        bitfield_print( ba & bb ) ;
        
        bitfield_print( bb ) ;
        bitfield_print( bc ) ;
        bitfield_print( bb | bc ) ;
    }
}

有名なものとして、エラトステネスのふるいによる素数計算を2進数を用いて記述してみる。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。

import java.util.*;

public class Main {
    static final int INT_BITS = 31 ;
    static int   prime = 0 ;
    public static void main(String[] args) throws Exception {
        // 倍数に非素数の目印をつける
        for( int i = 2 ; i <= INT_BITS ; i++ ) {
            if ( (prime & (1 << i)) == 0 ) {
                for( int j = 2 * i ; j <= INT_BITS ; j += i )
                    prime |= (1 << j) ;
            }
        }
        // 非素数の目印の無い値を出力
        for( int i = 2 ; i <= INT_BITS ; i++ ) {
            // 目印のついていない値は素数
            if ( (prime & (1 << i)) == 0 )
                System.out.println( i ) ;
        }
    }
}

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、int で 31要素、long int で 63 要素が上限となってしまう。

しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。また、今までの授業で説明してきた cons() などを使って表現すれば、簡単なプログラムでリストの処理が記述できる。

例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 両方に含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。

import java.util.*;

class ListNode {
   int      data ;
   ListNode next ;
   ListNode( int d , ListNode n ) {
       this.data = d ;
       this.next = n ;
   }
   static void print( ListNode p ) {
      for( ; p != null ; p = p.next )
         System.out.print( p.data + " " ) ;
      System.out.println() ;
   }
   static boolean find( ListNode p , int key ) {
      for( ; p != null ; p = p.next )
         if ( p.data == key )
            return true ;
      return false ;
   }
   static ListNode set_prod( ListNode a , ListNode b ) {
      ListNode ans = null ;
      for( ; a != null ; a = a.next ) {
         if ( find( b , a.data ) )
            ans = new ListNode( a.data , ans ) ;
      }
      return ans ;
   }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode b = new ListNode( 2 , new ListNode( 4 , new ListNode( 6 , null ) ) ) ;
        ListNode c = new ListNode( 4 , new ListNode( 6 , new ListNode( 9 , null ) ) ) ;
        ListNode b_and_c = ListNode.set_prod( b , c ) ;
        ListNode.print( b_and_c ) ;
    }
}

例題として、和集合、差集合などを考えてみよう。

理解確認

• 2進数を用いた集合処理は、どのように行うか？
• リスト構造を用いた集合処理は、どのように行うか？
• 積集合(A ∩ B)、和集合(A ∪ B)、差集合(A – B) の処理を記述せよ。

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

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

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 + ")" ) ;
        }
    }
    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<型> , List<型> のようなクラスは使わないこと。(ただし考察にて記述性の対比の対象として使うのはOK)

前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。

計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。

スタック

配列を用いたスタック

一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。

import java.util.*;

public class Main {
    static final int STACK_SIZE = 10 ;
    static int[] stack = new int[ STACK_SIZE ] ;
    static int   sp    = 0 ;
    static void push( int x ) {
        stack[ sp++ ] = x ;
    }
    static int pop() {
        return stack[ --sp ] ;
    }
    public static void main(String[] args) throws Exception {
        push( 11 ) ;
        push( 22 ) ;
        push( 33 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}

配列を使った Stack をオブジェクト指向で記述するなら、以下のように書ける。

import java.util.*;

class Stack {
    static final int STACK_SIZE = 10 ;
    int[] array ;
    int   sp ;
    Stack() {
        this.array = new int[ STACK_SIZE ] ;
        this.sp    = 0 ;
    }
    void push( int x ) {
        array[ sp++ ] = x ;
    }
    int pop() {
        return array[ --sp ] ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Stack stack = new Stack() ;
        stack.push( 11 ) ;
        stack.push( 22 ) ;
        stack.push( 33 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

C言語で書いた場合

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;

void push( int x ) { // データをスタックの一番上に積む
    stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
    return stack[ --sp ] ;
}
void main() {
    push( 1 ) ; push( 2 ) ; push( 3 ) ;
    printf( "%d\n" , pop() ) ; // 3
    printf( "%d\n" , pop() ) ; // 2
    printf( "%d\n" , pop() ) ; // 1
}

++,–の前置型と後置型の違い

// 後置インクリメント演算子
int i = 100 ;
printf( "%d" , i++ ) ;
// これは、
printf( "%d" , i ) ;
i++ ;
// と同じ。100が表示された後、101になる。

// 前置インクリメント演算子
int i = 100 ;
printf( "%d" , ++i ) ;
//   これは、
i++ ;
printf( "%d" , i ) ;
// と同じ。101になった後、101を表示。

リスト構造を用いたスタック

しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。

import java.util.*;

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

public class Main {
    static ListNode stack = null ;
    static void push( int x ) {
        stack = new ListNode( x , stack ) ;
    }
    static int pop() {
        int ans = stack.data ;
        stack = stack.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        push( 1 ) ;
        push( 2 ) ;
        push( 3 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}

struct List* stack = NULL ;

void push( int x ) { // リスト先頭に挿入
    stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
    int ans = stack->data ;
    struct List* d = stack ;
    stack = stack->next ;      // データ 0 件で pop() した場合のエラー対策は省略
    free( d ) ;
    return ans ;
}

オブジェクト指向っぽく書くならば、下記のようになるだろう。初期状態で stack = null にしておくと、stack.push() ができないので、stack の先頭には、ダミーデータを入れるようにプログラムを書くと以下のようになるだろう。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    ListNode() {   // stack初期化用のコンストラクタ
        this.data = -1 ;
        this.next = null ;
    }
    void push( int x ) {
        this.next = new ListNode( x , this.next ) ;
    }
    int pop() {
        int ans = this.next.data ;
        this.next = this.next.next ;
        return ans ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode stack = new ListNode() ; // stack初期化用のコンストラクタを使う
        stack.push( 1 ) ;
        stack.push( 2 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

キュー(QUEUE)

２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。

配列を用いたQUEUE / リングバッファ

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。

import java.util.*;

public class Main {
    static final int QUEUE_SIZE = 32 ;
    static int[] queue = new int[ QUEUE_SIZE ] ;
    static int wp = 0 ;
    static int rp = 0 ;
    static void put( int x ) {
        queue[ wp++ ] = x ;
        if ( wp >= QUEUE_SIZE ) // wp = wp % QUEUE_SIZE ; or wp = wp & (QUEUE_SIZE - 1) ;
            wp = 0 ;
    }
    static int get() {
        int ans = queue[ rp++ ] ;
        if ( rp >= QUEUE_SIZE ) // rp = rp % QUEUE_SIZE ; or rp = rp & (QUEUE_SIZE - 1) ;
            rp = 0 ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        // Your code here!
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}

#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read  pointer(読み出し用)

void put( int x ) { // 書き込んで後ろ(次)に移動
    queue[ wp++ ] = x ;
    if ( wp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
    int ans = queue[ rp++ ] ;
    if ( rp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        rp = 0 ;
    return ans ;
}
void main() {
    put( 1 ) ; put( 2 ) ; put( 3 ) ;
    printf( "%d\n" , get() ) ; // 1
    printf( "%d\n" , get() ) ; // 2
    printf( "%d\n" , get() ) ; // 3
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか？

 

リスト構造を用いたQUEUE

前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。

この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。

import java.util.*;

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

public class Main {
    static ListNode top = new ListNode( -1 , null ) ;
    static ListNode tail = top ;
    static void put( int x ) {
        tail.next = new ListNode( x , null ) ;
        tail = tail.next ;
    }
    static int get() {
        int ans = top.next.data ;
        top.next = top.next.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}

Javaで書かれた ListNode を用いた待ち行列のイメージ図は下記のように示される。

struct List* queue = NULL ;
struct List** tail = &queue ;

void put( int x ) { // リスト末尾に追加
    *tail = cons( x , NULL ) ;
    tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
    int ans = queue->data ;
    struct List* d = queue ;
    queue = queue->next ;
    free( d ) ;
    return ans ;
}

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。

理解確認

• 配列を用いたスタック・待ち行列は、どのような処理か？図などを用いて説明せよ。
• リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
• スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか？欠点があるか説明せよ。
• 配列を用いたリングバッファが用いられている身近な例にはどのようなものがあるか？
• 配列を用いたリングバッファを実装する場合配列サイズには 2ⁿ 個を用いることが多いのはなぜだろうか？