リスト構造の特徴として、リストの可変長データの便利さの反面、 シーケンシャルアクセスしかできないため、N番目データの参照がO(N)で 効率が悪い点を再確認したあと、その問題の解決方法として、双方向リストを説明する。

テキストエディタのような、１つ前の行、次の行をアクセスするような処理が多い場合、 単純リストでは、1つ前の参照は効率が悪い。 その対策として、１つ前のデータの場所を保存すればよい。

struct BDList {
struct BDList* prev ;
int            data ;
struct BDList* next ;
} ;
void bdinsert( 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 ;
}
}

しかしながら、このプログラムは、データが数件存在している場合は正しく動作するが、 データ件数が0件の場合には、問題が発生する。 データ件数が0の状態で、top = NULL であれば、この場合だけの特別処理を 記載することになる。これは、効率も悪いしプログラムも分りにくくなる。 この対策として、データ0件の状態を作らなければいい。このため、ダミーのデータを つくりリストの最前端と最後端に入れておけば特別処理が不要となる。 このような、データの端に処理の簡略化のために入れるデータを番兵(sentinel)と呼ぶ。

しかし、双方向リストでは、最前端と最後端に番兵を設けなくても、最後端の１つ前が、 最前端のデータを指すように循環リストを構成してやれば、番兵が１つで済む。 双方向リストでは、このような『双方向循環リスト』として扱う場合が多い。

説明補足用の図がいいのがないかなぁ～と、Google の画像検索をかけると、 イマイチな図ばっかり…と数回次次次とみていって、良い絵をみつける。 けど、よくみりゃ去年自分で書いた図だった…

入出力系の関数の説明として、 getchar() / putchar() , fgetc() / fputc() , gets() / puts() , fgets() / fputs() などの関数の説明を行う。 この話の中で、while( (c = getchar()) != EOF ) putchar( toupper( c ) ) のような プログラムを紹介し、その話の中から、fgetc() の EOFチェックや、fgets() のNULLチェック という話などを交えながら説明を行う。

特に、安全な入力手段ということで、fgets() + sscanf() による方法の説明を行う。

char buff[ 100 ] ;
char name[ 100 ] ;
int  age ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
// 色々な入力チェック() ;
if ( sscanf( buff , "%s%d" , name , &age ) == 2 ) {
// 入力値を使った処理...
}
}

リダイレクト

前の説明の toupper のプログラムを使って、入力リダイレクト、出力リダイレクトの説明を行う。

Z:>> toupper.exe > upper.txt
This is a pen.
That is a pencil.
^Z
Z:> type upper.txt
THIS IS A PEN.
THAT IS A PENCIL.
Z:> toupper.exe < toupper.c
#INCLUDE <stdio.h>
VOID MAIN() {
INT C ;
:

本当は、標準エラー出力・バッファリング・パイプの話もしたいんだけど、 来週から前期期末試験だし、重要な用語も多い講義だったこともあり、試験後のまとめにて 説明を行う予定。 話せる範囲が減ったから、テストの出題範囲もちょいと狭いなぁ… さて、難しいひねった問題出すしかねぇなぁ…(^_^;

C言語でのファイル操作ということで、FILE型のイメージや、 fopen() , fclose() の説明を行う。 特に、Windowsでのディレクトリ名区切り"￥"の問題の説明と、 ファイルモード"r/w/a"などの説明を行う。 また、OSでの違いの影響として、テキストモード・バイナリモードの違いを、 タイプライターの動きを例にしながら、"\n"と"\r"の違いなどを交えながら説明する。 ファイルの入出力命令は、導入なので現段階では、fscanf() , fprintf() のみを紹介に留める。

後半は、演習ということで、ファイルに、1行1件で複数人数のデータが保存されているときの データの読み込みと出力をテーマに課題とする。 レポートの動作確認のネタとして、定番でよくトラブルとして報告される、scanf("%d",…) で、 非数値データを入力したら無限ループ…あたりが面白いので、 「数値データがあったら数値以外を入力したら…」と伏線をひいておく。

来週には、fgetc(),fputc() , fgets() , fputs() あたりを紹介し、 fgets() + sscanf() による入力などを解説しよう。

北陸地区の高専大会が金沢にて開催中。残念ながら昨日の団体戦では男子５位女子３位の結果となった。昨日の後半から個人戦が始まり、 個人戦女子ダブルスにて、奈良本・小椋組が3位決勝戦に残ったが、惜しくも4位、同じく個人戦シングルスでも小椋さんの４位となりました。

来年の主管に向けたメモ

来年の高専大会は本校が主管。 今回のバドミントンで気づいた点を以下にメモ。

• インターバルの看板

  18-11などのスコアでの1分間のインターバルの際、 インターバル中、看板を設置することになった。 （今年度は新ルールでバドミントン協会から借りた）

• スコア管理ソフトでは、有名なフリーウェアがある様子。

  交歓試合で操作に慣れてもらってから運用。

• アバブウエスト・アバブハンド・フットフォルトなどの主審の注意。
• サーブ時は、主審はサーブの手前のラインとセンターラインを担当。
• 線審の判定を下した後、主審が覆すのはアリ。

  （当たり前だけど規定として明確じゃなかった？）

• 線審のイン/アウトのはっきりしたモーションをすること。 アウトも聞こえるようにはっきりと。
• ゲーム中の応援の移動は迷惑のないように。
• 忘れそうなネタ（ドリンク用のカゴはコート×２個）
• 閉会式の次第：成績発表・団体/個人複/個人単・校長講評・審判長講評・閉式の辞
• 来年度の高専大会は7/9,10?と思われるが、会場の予約なども含めて早々に決める必要あり。 理想：県立体育館(12面)・越前市体育館(10面)・鯖江市体育館(8面)

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

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

(( リストから特定データを探す／間違ったプログラム ))
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 ;
}