ホーム » 2009 » 7月 » 02

日別アーカイブ: 2009年7月2日

2009年7月
« 6月   8月 »
 1234
567891011
12131415161718
19202122232425
262728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト処理の応用

リスト構造への簡単な処理の説明が終わっているので、本日は応用ネタ。

末尾追加

先週説明したリストの生成は、先頭挿入型であったため、データは挿入順序とは逆順にならぶ。 後の説明のキューにも関連するので、末尾追加型の処理も説明する。

struct List {
int  data ;
struct Lint* next ;
} ;
struct List* top = NULL ;
struct List** tail = &top ;
int x ;
while( scanf( "%d" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}

スタックとリスト

スタックは、局所変数のデータや関数の帰りアドレスなどの保管で使われるデータ領域で 使われているが、LIFO(Last In First Out)「最後に入れたデータを最初に取り出せる」 データ構造。配列を使って記述すれば、

int stack[ 100 ] ;
int sp = 0 ; // 機械語の説明であれば、領域末尾から使うんだけど...
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
int ans = stack[ --sp ] ;
return ans ;
}
void main() {
push( 1 ) , push( 2 ) ; push( 3 ) ;
printf( "%d" , pop() ) ;
printf( "%d" , pop() ) ;
printf( "%d" , pop() ) ;
}

しかし配列を使うと、そのサイズ以上のデータを覚えることはできない。そこで、リスト構造のお出まし。

struct List* stack = NULL ;
int push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ; // データ0件のときの処理は別途書いてね。
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

リストと待ち行列

リストとは反対に、FIFO(First In First Out)「最初に入れたデータを最初に取り出せる」タイプの データ構造ま待ち行列(Queue)と呼ばれる。配列を使って記述すれば、

int queue[ 100 ] ;
int wp = 0 ;  // 書き込み用のポインタ
int rp = 0 ;  // 読み出し用のポインタ
void put( int x ) {
queue[ wp ] = x ;  // wpが一周してrpに追いついたときの処理は別途書くこと。
if ( ++wp > 100 ) wp = 0 ;
}
int get() {
int ans = queue[ rp ] ;  // 同じくデータが0件(wpに追いついた)の処理も別途書くこと。
if ( ++ rp > 100 ) rp = 0 ;
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d" , get() ) ;
printf( "%d" , get() ) ;
printf( "%d" , get() ) ;
}

このような配列を使った待ち行列では、配列サイズを超えた場合に、すでにデータを読み出して 使われていない部分を再利用するために、ポインタを先頭に戻す。 このデータ構造は、先頭と末尾が巡回してつながっているようなイメージなので、 「リングバッファ」と呼ばれる。

しかしながら、このリングバッファも配列での実装だから、配列サイズの上限は超えられない。 これまたリスト構造が便利なはず。

struct List* queue = NULL ;
struct List** tail = &queue ;
void put( x ) {
(*tail) = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() {
int ans = queue->data ;
struct List* del = queue ;
queue = queue->next ;
free( del ) ;
return ans ;
}

UML-クラス図

オブジェクト指向の話も、仮想関数などの話や演習も一段落で、次のUMLの説明に入る。

UMLは、システムの構造や処理などを図にして表現するための方法で、 共通の書き方として定められている。

UML

UMLは、オブジェクト指向において、それを図示するために OML などの表現方法として 始まって、現在は UML へと発達してきた。詳しくはwikipedia参照。

UMLの表現は、大きく分けて、データ構造などを示す構造図と、処理順序に関連する振る舞い図 からなる。

構造図は、クラスの構造を表わすクラス図、ファイルやライブラリ・モジュールなどを表現するコンポーネント図、ハードウェアやアプリケーションの関係を図にした配置図、 クラスに具体的なオブジェクトを書き込んでしめしたオブジェクト図などからなる。

振る舞い図は、相互作用図(アクティビティ図)、システムに要求される機能をユーザ視点で示したユースケース図、内部の状態の変化を表現した状態遷移図などからなる。

後半は、GUI&仮想関数の課題のレポート作成の時間とした…