プログラミング応用の後半は、 構造体(構造体・共用体・ビットフィールド)と、中間以降はグラフィックスという予定を 説明してから説明を開始。

構造体を使わない場合の問題点として、 名前と電話番号のデータベース構築をテーマに、 問題点を説明。 複数の配列を宣言すれば、途中で１人分のデータに変更が加わって、 配列宣言すべてを見なおさないといけなくなることを紹介。

// まずは構造体の宣言を理解してもらうため
struct Person {  // Personはタグ名
char  name[ 20 ] ;  // 要素の宣言
int   age ;
} table[ 50 ] ;  // table は Person型の50件分
// 実際は、構造体の宣言と、構造体変数の宣言は別に書く。
struct Person {
char name[ 20 ] ;
int   age ;
} ;
struct Person table[ 50 ] ;
void main() {
struct Person saitoh ;
saitoh.age = 46 ;
strcpy( saitoh.name , "斉藤" ) ;
printf( "%s %d¥n" ,
saitoh.name , saitoh.age ) ;
}

構造体は入れ子にすることもできる。

struct Person {
char name[ 20 ] ;
int   age ;
struct Birthday {
int year ;
int month ;
int day ;
} bday ;
} ;

構造体変数の一括代入とか説明したけど、 構造体の初期化を説明しなかったな…

後期１発目で、どこまで説明していたっけ？状態から、確認しながらスタート。 後の双方向・２分木の利点を理解してもらうために、 改めて「リスト構造」の利点・欠点について質問をする。

双方向リスト

基本、シーケンシャルアクセスの単純リストでは、 次のデータ参照は簡単だけれども、テキストエディタみたいなものを作る場合、 １つ前の行を参照…が単純リストでは不便。 そこで１つ前の行に戻れればいいということで、双方向リストを紹介。

struct BDList {
struct BDList* prev ;
int  data ;
struct BDList* next ;
} ;

このデータ構造の特徴を理解してもらうための簡単なプログラムとして、 双方向リストの指定ポインタの後ろに１件データ追記を紹介。

void insert( struct BDList* p , int x ) {
struct BDList* n ;
n = (struct BDList*)malloc( sizeof( struct BDList ) ) ;
if ( n != NULL ) {
n->data = x ;
n->prev = p ;
n->next = p->next ;
p->next->prev = n ;
p->next = n ;
}
}

しかしながら、この補助関数 insert() では、最前のデータを作ることはできない。 1つ前バージョンの補助関数を作ったり、最前データだけ特別処理でプログラムを 書くこともできるけど煩雑になり、プログラムの間違いの可能性も高くなる。 こういう場合は一般的に番兵を用いる。 最前および最尾に、実際には利用しないダミーデータを入れておけば、 特別処理を書かなくて済む。

また、最前・最尾のダミーでは、無駄なデータが２ヶ所現れてしまう。 しかし、最前の番兵データの１つまえを実際の最尾データ、実際の最尾データの次を最前の番兵データとすれば、番兵は１つで済む。こういう構造であれば、末尾が先頭に つながっている構造なので、「双方向循環リスト」と呼ばれる。 となるようにポインタ

2分木の導入

単純リストでは、目的データを検索する場合、シーケンシャルアクセスしかできないため、 検索にはO(N)の処理となってしまう。 高速に検索したいのであれば、配列ならばランダムアクセスができるため、 二分探索法が利用でき、処理もO(log N)となる。 リスト構造でも、二分探索法のように速くかつ、途中にデータの挿入削除のできるように したい。この場合に使われるのが２分木。

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

後期最初の担任クラスの授業ということもあり、 ホームルームも兼ねていたけど、非選択の学生さんが退出して、普通に授業。(^^;

最初の授業ということで、簡単なガイダンスとして、ネットワークが普及した現在、 データベースがどのように使われているのかを説明する。

データベースが情報共有のために重要な技術であり、Webシステムの中での使われ方 ということで、サーチエンジンの話(設立当初のYahooのユーザ登録型)や、 Google に代表されるクローラ・ロボットによるサーチエンジンの説明を行う。 これに伴い、データは巨大化し、大量のユーザを抱える現在、 データ検索を極めて短い時間で返答することの難しさを説明する。 このため、一般的なWebシステムでは、Webサーバを負荷分散目的で大量に配置し、 その後段にスレーブデータベースが待機し、その後段にさらにマスターデータベースが 並ぶという3段スキーマ構成の説明などを行う。 また、最近のIT産業では、システム構築からサービス開始までを短期間に行うために、 LAMP(Linux+Apache+MySQL+PHP)といった構成が多いことなども紹介。 さらに、普及しているリレーショナルデータベースシステムの名称として、 Oracle,MySQL,PostgreSQL,SQLite,BerkleyDBなどを紹介し、ネットワーク型、ファイル型 の違いやSQLを使うもの使わない物などがあることも紹介。

後半はデータベースが無かったら…という視点で説明。

C言語レベルの簡単な演習でデータベースっぽいことをする時は、 fscanf+fprintfだろうけど、大量データを永続的に扱いたいのであれば、 全データ読み込み＆全データ出力のプログラムを書くのが簡単。 でも、データ量が増えれば、修正・追加のあった部分だけ書きこむ必要が出てくる。 しかしながら、1行1件のデータであれば1行の長さが変化するとダメ。 こういう場合には、1件のデータ長を固定として、lseek+fwrite+freadを使って ランダムアクセスのプログラムを書くことになる。

しかし、こういうプログラムは1件のデータ長が変化すれば、プログラムの修正も大変。 さらに、複数の並行処理で書き換えを行えるのであれば、flockなどを使ったプログラムが 必要となる。