データベースの授業の１回目として、ガイダンスを行う。 授業で取り扱う内容などのシラバスについて説明い授業開始。

最近のWebシステムでの3段スキーマ・アーキテクチャなどを交えながら、 データベースの使われ方などの説明の後、データベースを使わなかったら どういった処理が大変で、データベースが如何に便利かを説明する。

詳細は、例年同じなので、前年度へのリンクを示す。

後期に入ったということで、中間試験までと期末試験までの予定を 簡単に説明した後で、2分木の説明を行う。

2分木

比較として、最初に配列での高速なデータ検索として、 2分探索法について説明し、データ検索が O(log(N))で表せること、 データの追加の処理などは、配列で実装すれば、O(N)となり、 あまり高速ではないことを説明する。

一方、リスト構造は、シーケンシャルアクセスしかできないから、 中央値を取り出すのには、O(N)の時間を要するため、 2分探索法が出来ないことを説明する。

そこで、2分木のデータ例を図示し、目的のデータを探すのに 要する比較回数を検討してもらう。これにより、 2分木のピラミッド構造の段数が、データ検索の際のループ回数である ことを説明し、段数 m と、データ件数 2^m = N より、 O(log(N))などの説明を行う。

structd Tree {
int  data ;
struct Tree *left ;
struct Tree *right ;
} ;
struct Tree* tcons( int x , struct Tree*l , struct Tree*r )
{
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->data = x ;
n->left = l ;
n->right = r ;
}
return n ;
}
struct Tree* top = // 静的にデータを生成
tcons( 50 ,
tcons( 75 , NULL , NULL ) ,
tcons( 25 , NULL , NULL ) ) ;

例題

2分木データ挿入処理のプログラムは複雑になりそうだし、 いきなりポインタのポインタでは、混乱をすると思われるので、 簡単に検索、データ件数カウントなどの例題を示す。

int  find( struct Tree* p , int key )
{
while( p != NULL ) {
if ( p->data == key )
return 1 ;
else if ( p->data > key )
p = p->left ;
else
p = p->right ;
}
return 0 ;  // 見つからない
}
int count( struct Tree* p )
{   if ( p == NULL )
return 0 ;
else
return 1 + count( p->left ) + count( p->right ) ;
}

後期に入って１回目の授業ということで、簡単に後期の授業の予定 (中間試験まで構造体、以降グラッフィック)といった点を伝えてからの、 説明。 構造体も２年の最後にやっている様ではあるが、 学生も「まだよく解っていない…」とのことで、 あらためて説明を行う。

構造体

最初の説明として、定番の「名前と国語,算数,理科の成績で、クラスの データを扱う…」というネタで、構造体を使わずに記載すると、どうなるか？ 途中で、扱うデータ件数が変更になったら、どうするか？ 複数クラスのデータを扱うようになったらどうするか？ といった変更について、説明を行う。

char name[ 50 ][ 20 ] ;
int  kokugo[ 50 ] ;
int  sansu[ 50 ] ;
int  rika[ 50 ] ;

人数が50と、マジックナンバーのまま。もし、1人分の名前の長さの20が 50であったら、50人クラス→100人との変更要求があれば、1人分の名前の 長さも変更してしまうミスがあるかもしれない。

他のクラスのデータも扱うようになったら？(例：電気科のデータも…)

char e_name[ 50 ][ 20 ] ;
int  e_kokugo[ 50 ] ;
int  e_sansu[ 50 ] ;
int  e_rika[ 50 ] ;

科目名が sansu → sugaku なら、e_sansu → e_sugaku を忘れるかも。 一番の問題は、name,…の入力処理と、e_name,…の入力処理を、 共通化できない。

構造体を使えば、

struct Student {
char  name[ 20 ] ;
int   kokugo ;
int   sansu ;
int   rika
} ;
struct Student saitoh = { "saitoh" , 90,92,96 } ;
struct Student ei[ 50 ] ; // EI学生
struct Student ee[ 50 ] ; // 電気学生...

構造体の入れ子

説明の中で、構造体の要素参照や、初期化を説明した後、 構造体の入れ子を説明する。 その前に、処理の入れ子として、{} による処理の複文の中に、 さらに{}のブロックがあるのも、処理の入れ子として説明。

struct Birthday {
int  month ;
int  day ;
} ;
struct Student {
char    name[ 20 ] ;
struct Birthday
bday
int     kokugo ;
int     sansu ;
} ;