リスト処理の応用として、集合演算について説明を行う。 今日は、わざと間違ったプログラムを書いて、どう変なのかを色々と聞いてみた。

まずは、集合演算を簡単にするための補助プログラム。 間違っている所をなぜ？と聞いたけど、反応が悪かったかな….

(( リストから特定データを探す／間違ったプログラム ))
int find( struct List* p , int x ) {
for( ; p != NULL ; p = p->next ) {
if ( p->data == x )
return 1 ;
else
return 0 ;
}
}
(( リストから特定データを探す ))
int find( struct List* p , int x ) {
for( ; p != NULL ; p = p->next )
if ( p->data == x )
return 1 ;
return 0 ;
}

次に、実際に集合演算A∩Bの計算例。これも、findを使わなかったら…という例を書いて 考えてもらった。徐々に自分で考えて、○○がダメじゃ？といった意見が飛び交うようになってきた。

(( リストの集合積／正しい例 ))
struct List* list_and( struct List*p1 , struct List*p2 ) {
struct List* ans = NULL ;
for( ; p2 != NULL ; p2 = p2->next ) {
if ( find( p1 , p2->data ) )
ans = cons( p2->data , ans ) ;
}
return ans ;
}
(( リストの集合積／findを使わずに間違った場合 ))
struct List* list_and( struct List*p1 , struct List*p2 ) {
struct List* ans = NULL ;
for( ; p2 != NULL ; p2 = p2->next ) {
for( ; p1 != NULL ; p1 = p1->next ) {
if ( p1->data == p2->data )
ans = cons( p2->data , ans ) ;
}
}
return ans ;
}

最後にリスト処理で作られたデータを捨てる処理。

(( リスト全部を捨てる／安易に書いたダメな例 ))
void list_free( struct List* p ) {
for( ; p != NULL ; p = p->next )
free( p ) ;
}
(( リスト全部を捨てる ))
void list_free( struct List* p ) {
struct List* d ;
while( p != NULL ) {
d = p ;
p = p->next ;
free( d ) ;
}
}

ダメな例とかを説明していたら、再帰でかけるんじゃ？みたいな意見を言う人がいたので、 実際に説明する。 「親亀こけたら子亀もこける。親亀が自殺するときゃ、子亀を確実に殺してから死にましょう」 と説明したら、その倫理観はやばいよね～みたいに受けた。説明用の倫理観は別な話。

(( 自分が死ぬ前に、尻尾は先に殺しましょう ))
void list_free( struct List* p ) {
if ( p != NULL ) {
list_free( p->next ) ;
free( p ) ;
}
}

UML表記法の第3弾として、振る舞い図の説明を行う。

振る舞い図として、 アクティビティ図、ユースケース図、ステートチャート、シーケンス図、コミュニケーション図 について説明を行う。

アクティビティ図は、システムのフローを記述するもので、フローチャート図に近い図で、 プログラムの細部の記述に使われる。
ユースケース図は、 要求仕様を記述する時などに使われるもので、「システムに対するユーザの役割や、連携する外部システムなどを表す」アクタと、「アクターによるシステムの利用の仕方を表す」ユースケースで記述する。
ステートチャート(状態遷移図)は、 論理回路の順序論理を示すための図と同じように、状態の遷移を「入力・条件」と遷移の際の「出力・関数」を示す。
シーケンス図は、 オブジェクト間のやり取りをタイムラインで示す図で、生存線上に活性区間と、オブジェクト間の メッセージのやり取りを示す。

後半は、想定していた時間が余ったので、 ソフトウェア工学としての トップダウン設計(ウォータフォールモデル)や、ボトムアップ設計などの一般論を話、 最近の少メンバーでの開発の際のアジャイル開発の事例も紹介する。 アジャイルでは、PDCAといったイテレーションの間隔を短くとらえて、 反復開発を行う方法が増えている事例を紹介する。 特に、オブジェクト指向をうまく取り入れてブラックボックス化ができていれば、 修正を随時行っていくリファクタリングが可能となることを説明する。 特に、エクストリームプログラミングでのペアプログラミング・テスト駆動開発などの 言葉も紹介してみた。

今週末の高専大会にて、投票ができなくなるので、 不在者投票に初チャレンジ。 6時頃に越前市役所の指定場所に出向く。

まだ手元には投票用紙が届いていないので、 まずは「住所・氏名・理由」を記載すると、 投票者確認の端末を操作する4人組の前にて作業をしてもらう。 （といっても、混み合っている雰囲気はなく、端末操作の人も暇そう） その際に身分証明が必要となり、運転免許証を提示する。 んで、確認結果の用紙が投票用紙代わりとなり、 参院選地方区、参院選比例区、越前市市議選と投票を行った。

しかし私自身の投票経験という意味では、ひとまず「政変なくして改革なし」との スタンスから、野党・無所属への投票ばっかり。 おかげで、私の投票する人が当選することはほとんど無い。
# さて、今回の投票だけど、結果はどうなるんだろう….

ともかく、高専大会に参加する5年で20歳を超えている人は、かならず不在者投票すべし!

先週のOSの歴史に引き続き、プログラミング応用で「ファイル」の説明の一環で、 ファイルとディレクトリの説明を行う。

コマンドプロンプトを開き、CUIで絶対PATH,相対PATHの説明を行う。 GUIでは、ファイルの位置が指定できないことや、異なるディレクトリツリーの中に、 同名のディレクトリがあった場合の曖昧さなどを話ながら、 実際に dir , cd , mkdir , rmdir , type , echo >file などのコマンドを説明し、 PATHに慣れてもらう。

後半は、簡単なディレクトリツリーを、CUI で実際に作成するまでの流れを、 絶対PATH , 相対PATHの2通りで作業してもらい、そのコマンドでタイプした内容を、 出席確認を兼ねて提出してもらった。

リスト構造の利点は、データを扱う件数が可変にできる所。 通常なら配列で書いていたプログラムも、リストを使うと便利。 以下のようにデータの途中にデータを挿入する場合でも、 記入場所を確保するためのデータの移動 の処理が不要で、 単純なリストのつなぎかえの の処理で済む。

// あえてcons()を使わずに書いておく
void insert_next( int x , struct List* p ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = p->next ;
p->next = ans ;
}
}

Stack(スタック)

データの後入れ先出し(Last In First Out)を行う Stack は基本的なデータの管理法。 配列で実装すれば、以下のような処理となる。

int 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" , pop() ) ;  // 3
printf( "%d" , pop() ) ;  // 2
printf( "%d" , pop() ) ;  // 1
}

しかし配列であれば、SIZEを超えるデータは保管できない。そこで、push/pop をリスト構造で 記載してみる。

struct List* stack = NULL ;
void push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ;
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

Queue(待ち行列)

先入れ先出し(First In First Out)は、一般的に待ち行列と呼ばれ、 プログラムは、先頭データと末尾データの2つの情報で管理される。

int queue[ SIZE ] ;
int wp = 0 , int rp = 0 ;
void put( int x ) {
queue[ wp++ ] = x ;         // リングバッファ法
if ( wp >= SIZE ) wp = 0 ;  // 末尾なら先頭に戻る
}
int get() {
int ans = queue[ rp++ ] ;
if ( rp >= SIZE ) rp = 0 ;  // 末尾なら先頭に戻る
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d" , get() ) ;  // 1
printf( "%d" , get() ) ;  // 2
printf( "%d" , get() ) ;  // 3
}

ただし、上記プログラムは登録件数が0になったことのチェックが無い手抜き記載なので、 理解できている人はさらに対策を記載する必要があることを考えること。

この待ち行列をリストを使ってプログラムで書けば、以下のようになる。 ただし、このリストのつなぎかえでは、データ件数0の状態が問題になるため、 最初にdummyデータが1件入れてあるものとする。

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

# 先週の講義のメモが残してないので、１週遅れで記載。

前回の説明では、リストを処理で手作業で作っていたが、 データの入力に合わせて追加して区処理を説明する。

先頭挿入型の追加処理

配列でデータを扱えば、C言語では固定サイズになるため、リスト構造を使えば不定長の データの取り扱いも楽。

struct List {
int data ;
struct List* next ;
} ;
struct List* cons( int x , struct List* n ) {
struct List* ans ;
if ( (ans = (struct List*)malloc( sizeof(struct List ))) != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
void main() {
struct List* top = NULL ;
int  x ;
while( scanf( "%d" , &x ) == 1 ) {
top = cons( x , top ) ;
}
}

このプログラムでは、リストの先頭に次々とデータを挿入していく。 このためデータは、挿入順と逆に並ぶことになる。

末尾追加型の追加処理

前の例では、管理するためのポインタがtopだけで良いため、シンプルではあるが、 データが逆順になってしまう。データの挿入順に並びたいのであれば、以下のような プログラムとなる。

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

しかしこのプログラムでは、tail の宣言が『Listへのポインタのポインタ』といった宣言で、 必ずしも読みやすいものではない。しかし、式の部分的な型が何なのかを明確に 理解できれば、イメージ図があれば、それなりに理解もできるようになるはず。

// ややこしい部分の型を考える。
&( (*tail)->next ) の型は？
tail               : List**
*tail              : List*  (List**の先を参照)
(*tail)->next      : List*  (List*の先のnext部を参照)
&( (*tail)->next ) : List** (next部のアドレスを取り出す)

先週のUMLの全体像の説明を受け、今日はデータ構造の説明のための図ということで、 構造図について説明する。

まずは、基本のクラス図について説明し、 可視性：public(+),private(-),protected(#)を、要素やメソッドにつけてあらわす。 継承がある場合には、派生側から基底クラスに白抜き三角矢印"―▹"で結ぶ。 クラス間の関係は、関連(assosiation)といい、直線で結ぶ。 直線の上には関連の説明をする意味を書き添え、両端には役割(ロール)を記載する。 直線の下には、多重度などを書き添える。

クラス間に包含関係がある場合には、全体と部分という関係があり、集約と呼ぶ。 この集約のうち、特に結びつきが強いものは合成(コンポジション)と呼ぶ。 単なる集約は、部品が単独でも存在しうる場合に使われ、"―◇"で接続する。 一方、コンポジションは親クラスと共に消滅するような強い結びつきであり、 UML記号としては"―◆"で接続する。

クラス図を具体的なデータを交えて記載するものは、オブジェクト図と呼ばれ、 設計開始時に関係者にヒアリングしながら書いたり、クラス設計が進む中で、 設計を検証するために具体的なインスタンスを書き込んで使う。

パッケージ図は、複数のクラスからなるものの全体的なグルーピングして記述するもので、 グループ化されたものをフォルダアイコンでまとめて、その間の関連を記載する。

コンポーネント図は、複数のクラスで構成される処理で、１つ以上のインタフェースを用意し、 あたかも１つのクラスのように取り扱って表現する図。 提供側インタフェース"―○"と、要求側インタフェース"―⊂"で結びつきを表現する。

(図は、Wikipediaなどからの引用)