ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論

情報構造論」カテゴリーアーカイブ

2021年2月
 123456
78910111213
14151617181920
21222324252627
28  

最新の投稿(電子情報)

アーカイブ

カテゴリー

情報構造論とオブジェクト指向

データ構造を扱うプログラムの書き方を説明してきたが、その考え方をプログラムにするためには手間もかかる。こういった手間を少しでも減らすために、プログラム言語が支援してくれる。その代表格がオブジェクト指向プログラミング(Object Oriented Programming:略称OOP)であり、以下にその基本を説明する。

データ指向のプログラム記述

名前と年齢のデータを扱うプログラムをC言語で書く時、私なら以下のようなプログラムを作成する。

このプログラムの書き方では、saitohというデータにset_NameAge() , print_NameAge() を呼び出していて、データに対して処理を加えるという雰囲気がでている。(C言語なのでデータに処理を施す関数には、必ずどのデータに対する処理なのかを与えるポインタがある。) このようにプログラムを書くと、saitoh というデータに対して命令するイメージとなり、擬人化したデータに向かってset,printしろ…って命令しているように見える。

// 名前と年齢の構造体 
struct NameAge {
   char name[ 20 ] ;
   int  age ;
} ;

// NameAgeを初期化する関数
void set_NameAge( struct NameAge* p , char s[] , int a ) {
   strcpy( p->name , s ) ;
   p->age = a ;
}

// NameAgeを表示する関数
void print_NameAge( struct NameAge* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}

void main() {
   struct NameAge saitoh ;

   set_NameAge( &saitoh, "t-saitoh" , 53 ) ;
   print_NameAge( &saitoh ) ;

   // NameAge の中身を知らなくても、
   // set_NameAge(),print_NameAge() の中身を見なくても、
   // saitoh を set して print する....という雰囲気は伝わるよね!!  
}

このプログラムでは、例えば、データに誕生日も覚えたいという改良を加えるとしても、main の前のデータ構造と関数の部分は色々と書き換えることになるだろうけど、main の内部はあまり変わらないだろう。こういう書き方をすればプログラムを作成するときには、データ構造とそれを扱う関数を記述する人と、データ構造を使う人(main内部を書く人)と、分業ができるようになる。

隠蔽化

このような記述では、データ構造の中身を知らなくても、main で、setしてprintして…という処理の雰囲気は分かる。さらに、set_NameAge()とか、print_NameAge() の処理の中身を知らなくても、設定するとか表示するとか…は予想できる。

これは、NameAge というデータをブラックボックス化して捉えていると見れる。データ構造の中身を知らなくてもプログラムを理解できることは、データ構造の隠蔽化という。また、関数の中身を知らなくても理解できることは、手続きの隠蔽化という。

オブジェクト指向プログラミング

前述のように、プログラムを書く時には、データ構造とそのデータを扱う関数を一緒に開発するのが一般的である。オブジェクト指向プログラミングでは、データ構造その関数(メソッドと呼ぶ)をまとめてクラスと呼ぶ。

class NameAge {
private:
   // データ構造の宣言
   char name[ 20 ] ;
   int  age ;

public:
   // メソッドの定義
   void set( char s[] , int a ) { // 初期化関数
      strcpy( name , s ) ;        // どのデータに対する処理かは省略できるので、
      age = a ;                   // データへのポインタ引数は不要。
   }
   void print() {                 // 表示関数
      printf( "%s %d¥n" , name , age ) ;
   }
} ;

void main() {
   NameAge saitoh ;
   saitoh.set( "t-saitoh" , 53 ) ; // set,printはpublicなので自由に使える。
   saitoh.print() ;
   // saitoh.age = 54 ; エラー:クラス外でprivateの要素は触れない。
}

このプログラムでは、saitoh というデータ(具体的なデータが割り当てられたものはオブジェクトと呼ぶ)に対して、set() , print() のメソッドを呼び出している。

# C++ではクラス毎に関数名を区別してくれるので、関数名もシンプルにset,printのようにかける。

オブジェクト指向では、データに対して private を指定すると、クラス以外でその要素やメソッドを扱うことができなくなる。一方 public が指定されたものは、クラス外で使っていい。これにより、クラスを設計する人と、クラスを使う人を明確に分けることができ、クラスを使う人が、クラス内部の変数を勝手に触ることを禁止できる。

プログラムを記述する時には、データ件数を数える時に、カウンタの初期化を忘れて動かないといった、初期化忘れも問題となる。オブジェクト指向のプログラム言語では、こういうミスを減らすために、データ初期化専用の関数(コンストラクタ)を定義することで、初期化忘れを防ぐことができる。

// コンストラクタを使う例
class NameAge {
   // 略
public:
   NameAge( char s[] , int a ) { // データ初期化専用の関数
      strcpy( name , s ) ;       //  コンストラクタと呼ぶ
      age = a ;
   }
   // 略
} ;
void main() {
   NameAge saitoh( "t-saitoh" , 53 ) ; // オブジェクトの宣言と初期化をまとめて記述できる。
   saitoh.print() ;
}

プログラムにオブジェクト指向を取り入れると、クラスを利用する人クラスを記述する人分業ができ、クラスを記述する人は、クラスを利用するプログラマーに迷惑をかけずにプログラムを修正できる。

この結果、クラスを記述する人はプログラムを常により良い状態に書き換えることができるようになる。このように、よりよく改善を常に行うことはリファクタリングと呼ばれ、オブジェクト指向を取り入れる大きな原動力となる。。

最近のC++なら

最近のオブジェクト指向プログラミングは、テンプレート機能と組み合わせると、単純リスト処理が以下のように書けてしまう。struct 宣言やmalloc()なんて出てこない。(^_^;

#include <iostream>
#include <forward_list>
#include <algorithm>

int main() {
  // std::forward_list<>線形リスト
  std::forward_list<int> lst{ 1 , 2 , 3 } ;

  // リスト先頭に 0 を挿入
  lst.push_front( 0 ) ;


  // 以下のような処理を最新のC++なら...
  // * もともとのC言語なら以下のように書くだろう。
  //   for( struct List*p = top ; p != NULL ; p = p->next )
  //     printf( "%d¥n" , p->data ) ;

  // * 通常の反復子iteratorを使って書いてみる。
  //   auto は、lst の型推論。
  //   ちょっと前のC++なら型推論がないので、std::forward_list<int>::iterator itr = lst.begin() と書く。
  for( auto itr = lst.begin() ;
       itr != lst.end() ;
       itr++ ) {
    std::cout << *itr << std::endl ;
  }

  // 同じ処理を algorithm を使って書く。
  std::for_each( lst.begin() ,
                 lst.end() ,
                 []( int x ) { // 配列参照のコールバック関数
                   std::cout << x << std::endl ;
                 } );

  // 特に書かなくてもデストラクタがlstを捨ててくれる。
  return 0 ;
}

テンプレート機能

テンプレート機能は、実際のデータを覚える部分の型を後で指定できるようにしたデータ構造を定義する機能。

template <class >
struct List {
   T   data ;
   struct List* next ;
} ;

int main() {
   List<int>    li ;  // 整数を要素とするList型の宣言
   List<double> ld ;  // 実数を要素とするList型の宣言
}

関数ポインタ

前プログラムのC++のfor_each アルゴリズムでは、コールバック関数が使われていたが、この仕組みを分かるために関数ポインタの考え方が重要。

int add( int x , int y ) {
   return x + y ;
}
int mul( int x , int y ) {
   return x * y ;
}
void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = add ;               // f = add( ... ) ; ではないことに注意
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
   f = mul ;
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}

演習(ハッシュ法)

ハッシュ法のプログラム(オープンアドレス法もしくはチェイン法)を用いて、
(1)名前と電話番号,(2)名前と住所,(3)名前と誕生日について、名前をキーとして検索するプログラムを作成せよ。

原則として「出席番号 % 3 + 1」の番号のテーマに取り組むこと。

レポートを作成する際には、ハッシュ関数を変更してどういった変化があるか確認せよ。
ハッシュサイズは、10〜20件程度で良い。

動的メモリ管理 malloc() と free()

C言語では、動的メモリ領域をどのように管理していくのか解説する。

局所変数とスタック

局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。

関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。

baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…

動的メモリ領域とフリーリスト

動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借りfree()関数で使わなくなったメモリを返却する。

この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。

mallocが一定サイズの場合

仕組みを理解する第1歩として、free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。free_list には、貸し出すためのメモリ空間をリスト構造で繋がった状態にしておく。

malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。

任意サイズのメモリ確保の場合

最初のステップでの説明は、mallocのメモリサイズを一定としていたが、本来は確保するメモリサイズが指定する。この場合は、以下の様に管理されている。mallocで貸し出されるメモリ空間には、ヒープメモリの利用者が使うブロックの前に、次のメモリブロックへのポインタとブロックサイズを記憶する領域をつけておく。こういったメモリブロックを free_list の考え方と同じようにリスト構造となるようにつないで保存されている。

この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。

malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。malloc(40)

丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。malloc(60)

free()の処理とメモリブロックの併合

この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。

使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。

そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。

また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。

一般的には、上記のようにmalloc(),free()を行うが(K&Rのmallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。(dlmallocのアルゴリズム)

ヒープメモリの断片化

ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。

この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。

(補足) 断片化

断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。

上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。

Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。

共有のあるデータの取扱い

これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数により指定サイズのメモリ空間を借りて、処理が終わったら free() 関数によって返却をしてきた。この返却を忘れたままプログラムを連続して動かそうとすると、返却されなかったメモリが使われない状態(メモリリーク)となり、メモリ領域不足から他のプログラムの動作に悪影響を及ぼす。

メモリリークを防ぐためには、malloc() で借りたら、free() で返すを実践すればいいのだが、複雑なデータ構造になってくると、こういった処理が困難となる。そこで、ヒープメモリの問題点について以下に説明する。

共有のあるデータの取扱の問題

リスト構造で集合計算の和集合を求める処理を考える。

// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{  struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}

void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ; // c = { 1, 2, 3, 4 }
                                     //          ~~~~~~~ ここは b
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;
   list_del( b ) ;
   list_del( c ) ; // list_del(b)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、c=join(a,b) ; が終わると下の図のようなデータ構造となる。しかし処理が終わってリスト廃棄list_del(c), list_del(b), listdel(a)を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p != NULL
        && --(p->refc) <= 0 ) {    // 参照カウンタを減らし
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

unix i-nodeで使われている参照カウンタ

unixのファイルシステムでは、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。

ガベージコレクタ

では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか?
最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、このままでは、メモリを使い切ってしまう。

そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタ(一般的にはGCと略される)である。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、

  1. すべてのメモリ空間に、「不要」の目印をつける。(unmark処理)
  2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理-目印をつける)
  3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理-掃き掃除する)


この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタはメモリ空間が広い場合は、処理時間かかり、さらにこの処理中は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。

最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような関数に入った時点で生成され関数終了ですぐに不要となる領域は、参照カウンタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。

大量のメモリ空間で、メモリが枯渇したタイミングでガベージコレクタを実行すると、長い待ち時間となることから、ユーザインタフェースの待ち時間に、ガベージコレクタを少しづつ動かすなどの方式もとることもある。

 

ハッシュ法

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)2分探索ならO(log N)となる)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか?

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

// メモリ無駄遣いな超高速方法
struct PhoneName {
   int  phone ;
   char name[ 20 ] ;
} ;

// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?

// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
   table[ phone ].phone = phone ;
   strcpy( table[ phone ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   return table[ phone ].name ;
}

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

// ハッシュ衝突を考えないハッシュ法

#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;

// ハッシュ関数
int hash_func( int phone ) {
   return phone % HASH_SIZE ;
}

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   return table[ idx ].name ;
}

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

たとえ話で言うなら、100個の椅子が連番付きで並んでいて、自分の電話番号末尾2桁の場所に座ろうとしたら、先に座っている人がいるような状態である。このような状態で、あなたなら何処に座るだろうか?

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムでなくなってしまう。このことから、ハッシュ関数には以下のような特徴が必要となる。

  • 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
  • 簡単な計算で求まること。
  • 同じデータに対し常に、同じハッシュ値が求まること。

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 )
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故?
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ;
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 ) {
      if ( table[ idx ].phone == phone )
         return table[ idx ].name ;
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故?
   return NULL ; // 見つからなかった
}

注意:このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。

この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。

#define SIZE 100
int hash_func( int ph ) {
   return ph % SIZE ;
}
struct PhoneNameList {
   int phone ;
   char name[ 20 ] ;
   struct PhoneNameList* next ;
} ;
struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化

struct PhoneNameList* cons( int ph ,
                            char* nm ,
                            struct PhoneNameList* nx ) {
   struct PhoneNameList* ans ;
   ans = (struct PhoneNameList*)malloc(
                      sizeof( struct PhoneNameList ) ) ;
   if ( ans != NULL ) {
      ans->phone = ph ;
      strcpy( ans->name , nm ) ;
      ans->next = nx ;
   }
   return ans ;
}

void entry( int phone , char* name ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , name , hash[ idx ] ) ;
}
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   struct PhoneNameList* p ;
   for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
      if ( p->phone == phone )
         return p->name ;
   }
   return NULL ;
}

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum + s[i] ;
   }
   return sum % SIZE ;
}

文字列順で異なる値となるように

前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum*2 + s[i] ;
      // sum = (sum * 小さい素数 + s[i]) % 大きい素数 ;
   }
   return sum % SIZE ;
}

この後の授業の予定

  • 共有のあるデータの取り扱い(参照カウンタ法,ガベージコレクタ) (1/14)
  • 動的メモリ確保(malloc()とfreelist) (1/21)
  • オブジェクト指向 (1/28)
  • 予備 (2/4)

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT                             RESULT
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90

((SQLの例))
select STUDENT.name, RESULT.subject, RESULT.point --射影--
   from STUDENT , RESULT                          --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --   --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

演算子と2分木による式の表現

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言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

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

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

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

逆ポーランド記法の式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) { if ( isdigit( *p ) ) { // ~~(A) // 数字はスタックに積む push( *p - '0' ) ; // ~~~~~~~~(B) } else if ( *p == '+' ) { // 演算子+は上部2つを取出し int r = pop() ; int l = pop() ; // 加算結果をスタックに積む push( l + r ) ; } else if ( *p == '*' ) { // 演算子*は上部2つを取出し int r = pop() ; int l = pop() ; // 乗算結果をスタックに積む push( l * r ) ; }//~~~~~~~~~~~~~(C) } // 最終結果がスタックに残る return pop() ; } void main() { printf( "%d\n" , rpn( "123*+" ) ) ; }

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

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

   +
  / \
 1   *
    / \
   2   3

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

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
                   struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      n->data  = op ;
      n->left  = l ;
      n->right = r ;
   }
   return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL ) {
      // 数値のノードは値を返す
      return p->data ;
   } else {
      // 演算子のノードは、左辺値,右辺値を求め
      // その計算結果を返す
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) ,
                        tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか?
  • 上記プログラム中の(A)~(F)の型を答えよ。

意思決定木と構文解析

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

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

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

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

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

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:翻訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:通訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
      最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
  • エミュレーター
    • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
      近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。

      • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コードとして出力

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

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、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”と区切る処理が、字句解析である。

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

  +
 / \
1   *
   / \
  23   456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。

2020年度前期授業アンケート

情報構造論

情報構造論は通年科目なので、中間状況だけど、ひとまず80ポイント越え。1件だけ最低評価が並んでいるのが気がかり。不満のある人が積極的に質問してくれるといいのだが。

オブジェクト指向プログラミング

オブジェクト指向は、専攻科2年相手の前期科目。課題でやや不満が1件あるけど、難しかったのだろうか。設定が曖昧だったのだろうか。

情報制御基礎

情報制御基礎は、3年生の学際科目で全学科対象の授業。「テストの過去問題がWebに掲載してあり勉強しやすかった」といった趣旨の意見もあり、評価も高かった。

どの授業も、コロナによる遠隔授業であったが、例年 Web に掲載している講義資料をそのまま使い、Teams のWeb会議でMicrosoft Edge のペン書き機能を使いながら補足説明を書き込みしながら行なった。Web会議は録画しておき、オンデマンドで視聴できるようにしておいたので、コロナ遠隔授業といいながらも、授業の進め方は今まで通りにすすめたつもり。

AVLと2分ヒープ

前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。

2分探索木へのデータ追加と不均一な木の成長

先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。

しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか?

  • 86, 53, 11 – 降順のデータ
  • 12, 24, 42 – 昇順のデータ

この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。

AVL木

このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。

このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)

この様に、左右の枝の大きさが不均一な場所を見つけ、右回転や左回転を行う処理を繰り返すことで、段数が均一な2分探索木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。

理解確認

  • 木の根からの段数を求める関数 tree_depth() を作成せよ。
    例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数
_____ tree_depth( _______________ p ) {
   if ( p == NULL ) {
      return _____ ;
   } else {
      int d_L = ______________ ;
      int d_R = ______________ ;
      if ( d_L > d_R )
         return _____ ;
      else
         return _____ :
   }
}

// pをつなぎ替え上部を返り値で返す。
struct Tree*rot_right( struct Tree* p ) {
   struct Tree* pl = p->left ;
   struct Tree* pr = pl->right ;
   pl->right = p ;
   p->left = = pr ;
   return pl ;
}
int main() {
   printf( "%d¥n" , tree_depth( top ) ) ;
   top = rot_right( top ) ;
   return 0 ;
}

2分ヒープ(binary heap)

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

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

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

int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;

// 2分ヒープを表示
void print_heap( int array[] , int idx , int size ) {
   if ( idx < size ) {
      // 左の枝を表示
      print_heap( array , 2*idx + 1 , size ) ;
      // 真ん中の枝を表示
      printf( "%d " , array[ idx ] ) ;
      // 右の枝を表示
      print_heap( array , 2*idx + 2 , size ) ;
   }
}

// 2分ヒープから key を検索
int find_heap( int array[] , int idx , int size , int key ) {
   while( idx < size ) {
      if ( array[ idx ] == key )
         return idx ; // 見つかったら配列の番号を返す
      else if ( array[ idx ] _____ key )  // 何が入るか考えよう
         idx = ________________ ;
      else
         idx = ________________ ;
   }
   return -1 ; // 見つからなかったら、-1 を返す
}
int main() {
   print_heap( a , 0 , 7 ) ;
   if ( find_heap( a , 0 , 7 , 65 ) >= 0 )
      printf( "Find!!¥n" ) ;
   return 0 ;
} 

2分探索木の処理とデータ追加処理

前回の授業では、当初予定に加え、この後に示すデータの追加処理の説明を行った。その代わり、簡単な2分木の演習が抜けていたので少し演習を追加。

2分木の簡単な処理

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 + sum( p->left )
                     + sum( p->right )
}
int max( struct Tree* p ) { // 最大値
   if ( p == NULL ) {
      return 0 ; // データ件数=0のとき0が最大値でいいのかなぁ?
   } else {
      while( p->right != NULL )
         p = p->right ;
      return p->data ;
   }
}
int depth( struct Tree* p ) { // 木の深さ
   if ( p == NULL ) {
      return 0 ;
   } else {
      int d_l = depth( p->left ) ;
      int d_r = depth( p->right ) ;
      if ( d_l > d_r )
         return d_l + 1 ;
      else
         return d_r + 1 ;
   }
}

int main() {
   struct Tree* top = ..... ;
   printf( "%d\n" , count( top ) ) ; // 木全体のデータ件数
   printf( "%d\n" , sum( top ) ) ;   // 木全体のデータ合計
   printf( "%d\n" , depth( top ) ) ; // 木全体の最大段数

   return 0 ;    
}

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

前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。

struct Tree* top = NULL ;

// 2分探索木にデータを追加する処理
void entry( int d ) {
   struct Tree** tail = &top ;
   while( *tail != NULL ) {
      if ( (*tail)->data == d )       // 同じデータが見つかった
         break ;
      else if ( (*tail)->data > d )
         tail = &( (*tail)->left ) ;  // 左の枝に進む
      else
         tail = &( (*tail)->right ) ; // 右の枝に進む
   }
   if ( (*tail) == NULL )
      *tail = tcons( d , NULL , NULL ) ;
}

int main() {
   char buff[ 100 ] ;
   int x ;

   while( fgets( buff , sizeof( buff ) , stdin ) != NULL )
      if ( sscanf( buff , "%d" , &x ) != 1 )
         break ;
      entry( x ) ;

   return 0 ;    
}

このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。

理解確認

  • 関数entry() の14行目の if 判定を行う理由を説明せよ。
  • 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
  • sscanf() の返り値を 1 と比較している理由を説明せよ。
  • entry() でデータを格納する処理時間のオーダを説明せよ。
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...

void entry( struct Tree* top , int d ) {
   struct Tree** tail = &top ;
   while( *tail != NULL ) {
      :
      // 上記の entry() と同じとする
}
void main() {
   // 追加対象の top は局所変数
   struct Tree* top = NULL ;
 
   char buff[ 100 ] ;
   int  x ;
   while( fgets(buff,sizeof(buff),stdin) != NULL ) {
      if ( sscanf( buff , "%d" , &x ) != 1 )
         break ;
      entry( top , x ) ;
   }
}

上記のプログラム↑は動かない。なぜ?
このヒントは、このページ末尾に示す。

演習課題

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

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

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

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

レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。

// プログラムのおおまかな全体像の例
struct Tree {
    //
    // この部分を考えて
    //   以下の例は、名前と電話番号を想定
} ;

struct Tree* top = NULL ;
void tree_entry( char n[] , char ph[] ) {
    // n:名前,ph:電話番号 を追加
}
void tree_print( struct Tree* p ) {
    // 全データを表示
}

struct Tree* tree_search_by_name( char n[] ) {
    // n:名前でデータを探す
}

int main() {
    char name[ 20 ] , phone[ 20 ] ;
    char buff[ 1000 ] ;
    struct Tree* p ;

    // データを登録する処理(空行を入力するまで繰り返し)
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        if ( sscanf( buff , "%s%s" , name , phone ) != 2 )
            break ; // 入力で、2つの文字列が無い場合はループを抜ける
        tree_entry( name , phone ) ;
    }

    // 全データの表示
    tree_print( top ) ;

    // データをさがす
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        if ( sscanf( buff , "%s" , name ) != 1 )
            break ; // 入力で、1つの文字列が無い場合はループを抜ける
        if ( (p = tree_search_by_name( name )) == NULL )
            printf( "見つからない¥n" ) ;
        else
            printf( "%s %s¥n" , p->name , p->phone ) ;
    }
    return 0 ;
}

動かないプログラムのヒント

// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
// ちなみに、こう書くと動く

// Tree*を返すように変更
struct Tree* entry( struct Tree* top , int d ) {
   :
   // 最初の entry と同じ
   :
   return top ;
}
void main() {
   // 追加対象のポインタ
   struct Tree* top = NULL ;
   while( ... ) {
      :

      // entry() の返り値を top に代入
      top = entry( top , x ) ;
   }
}

fgets()とsscanf()による入力の解説

前述のプログラムの入力では、fgets() と sscanf() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。

// scanf() で苦手なこと -------------------------//
// scanf() のダメな点
// (1) 何も入力しなかったら...という判定が難しい。
// (2) 間違えて、abc みたいに文字を入力したら、
// scanf()では以後の入力ができない。(入力関数に詳しければ別だけどさ)
int x ;
while( scanf( "%d" , &x ) == 1 ) {
   entry( x ) ;
}

// scanf() で危険なこと -------------------------//
// 以下の入力プログラムに対して、10文字以上を入力すると危険。
// バッファオーバーフローが発生する。
char name[ 10 ] ;
scanf( "%s" , name ) ;

// 安全な入力 fgets() ---------------------------//
// fgets() は、行末文字"¥n"まで配列 buff[]に読み込む。
// ただし、sizeof(buuf) 文字より長い場合は、途中まで。
char buff[ 100 ] ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
    // buff を使う処理
}
// 文字列からデータを抜き出す sscanf() -------------//
// sscanf は、文字列の中から、データを抜き出せる。
// 入力が文字列であることを除き、scanf() と同じ。
char str[] = "123 abcde" ;
int  x ;
char y[10] ;
sscanf( str , "%d%s" , &x , y ) ;
// x=123 , y="abcde" となる。
// sscanf() の返り値は、2 (2個のフィールドを抜き出せた)

// ただし、Microsoft Visual Studio では、以下のように関数名を読み替えること。
// scanf( ... )  → scanf_s( ... )
// fscanf( ... ) → fscanf_s( ... )
// sscanf( ... ) → sscanf_s( ... )

理解確認