来週からのテストということもあり、前半に簡単なリスト処理の基本を説明したあと、 後半はテスト勉強時間とした。

最初に復習のおまけとして、typedef や C++でのリストの宣言の違いを説明。

// 授業でのスタイル
struct List {
int          data ;
struct List* next ;
} ;
// C言語でtypedefを使うスタイル
typedef struct LIST {
int          data ;
struct LIST* next ;
} List ;
List* top = .... ;
// C++では、構造体名がそのまま使える
struct List {
int   data ;
List* next ;
} ;
List* top = .... ;

簡単な補助関数を示して、基礎的なプログラム例を演習として行う。

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 print( struct List* p ) {
for( ; p != NULL ; p = p->next ) {
printf( "%d" , p->data ) ;
}
}
int sum( struct List* p ) {
int ans ;
for( ans = 0 ; p != NULL ; p = p->next ) {
ans += p->data ;
}
return ans ;
}
void main() {
struct List* top = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
print( top ) ;
printf( "%d" , sum( top ) ) ;
}

今年度は、福井高専では学位授与機構にによる認証評価とJABEE審査が行われる。 講演では、認証評価に備えた説明があった。

この中で、特徴的と思われる点は、第2サイクルの評価に当たり、 「学生による事前学習」が重要とのことであった。 このため、シラバスには事前学習の内容を明記などが、必要となりそう。 特に各週毎に明記が理想とのことであった。

うーむ、シラバスの管理システムに、記述欄そんなに増やせるのかな…

先週の純粋仮想基底クラスの事例を、具体的なプログラムでの演習とすべく、 下記資料を配布し、演習を行う。

• 仮想関数とsort
• 仮想関数プログラムと課題レポート

最初に、他学科の学生であればGrWinを知らない可能性もあり、 本科3年向けの資料を配布し、説明を行う。 ただし、電気電子OB学生が中心であるため、GrWinは授業で経験済みであった。

Figure というdraw()という仮想関数を持つ純粋仮想基底クラスを宣言し、 FigureBox , FigureCircle という、具体的な図形のクラスを派生させ、 各描画関数 draw を示す。演習では、別の図形を派生させたり、 色つきクラスに拡張してもらうなどして、次のクラス設計の元ネタとすべく演習を予定。

授業アンケート(2011年度)のデータが送付されてきた。 ということで、例年通りそのまま記載。

データベース

75.9→77.8でポイントは微増。 黒板やOHP資料のポイントが低い。 担任クラスでもあり、甘めの評価の懸念あり。

情報構造論

81.3→82.3でポイントは微増。 黒板やOHP資料のポイントが低い。 意見欄では、良かったや分かりやすかったの意見があり、 総じて良い評価であったと思われる。

創造工学演習

時間不足を指摘する意見が多い。 前年度の授業段階から事前準備などの提案もあり、 目的意識を持って取り組んだという意味では、良い傾向と思われる。

プログラミング応用

77.3→81.0でポイントも上がっている。 この科目では、黒板OHPのポイントが特に悪いという程ではない。 意見欄でも、プリントが分かりやすいとか理解が深まったとの 好印象な意見が得られた。 一方、授業中の演習が座学と区別しているため、実際にどんな動きをするのか見てみたかったとの意見もあった。

計算機システム

• 2010年度結果

前回の授業で、#defineマクロやbit演算の説明をしたけど、 まだ詰めが甘かったので、開いたサブルーチン・閉じたサブルーチンなどの 説明を行い、標準関数などの説明も行う。

開いたサブルーチンと閉じたサブルーチン

#define マクロと、関数の違いを理解してもらうために、 プリプロセッサ・コンパイル・リンクといった機械語生成までの流れを説明し、 #define マクロを多用すると、同じ機械語が何度も生成され、機械語が肥大する 可能性を説明する。逆に関数を何度も利用しても、一箇所の機械語が使われるため 機械語の肥大は無いことを説明する。一方、関数では実引数・仮引数の 値渡しなどが発生するので、わずかとはいえ余計な処理時間を要することを説明。 この結果、#define マクロは、小さな関数向きであることを述べる。 また、関数は入口・出口が明確に作られることから、閉じたサブルーチンと呼ばれる。 逆に #define マクロは入口・出口が明確でなく、開いたサブルーチンと呼ばれることを 説明する。

N進数変換や文字列処理で使う標準関数

N進数変換や文字列処理で、ctype.h の isdigit() 関数や、stdlib.h の strtol() などの 標準関数を説明する。

型の問題と実行時のトラブル

1桁の数値と+,-記号で式の値を求めるeval() という関数を示し、 文字列処理のサンプルを説明する。このあと、以下の様な呼び出しの問題点を考えてもらう。

int eval( char s[] ) {
// 一桁の数値と"+","-"の計算式
// 例 printf( "%d" , eval( "1+2+3" ) ) ; // 6
}
void main() {
printf( "%d" , eval( 1+2+3 ) ) ;  // 引数型の不一致
printf( "%d" , eval( '1+2+3' ) ) ; // 文字定数エラー
printf( "%d" , eval( "1+2+3" ) ) ; // OK
// よくありそうな書き間違い
char s[ 100 ] ;
scanf( "%s" , s ) ;
printf( "%d" , eval( s[100] ) ) ; // 引数型不一致
// 文字列ポインタの間違い
char* s ;
scanf( "%s" , s ) ;  // 変な場所に文字列格納でメモリエラー
printf( "%d" , eval( s ) ) ;
//
char s[ 5 ] ;
scanf( "%s" , s ) ; // 1+2+3+4+5+6 を入力したら!?
printf( "%d" , eval( s ) ) ;
}

配列の利点・欠点を踏まえ、リスト構造の説明を行う。

配列は、N番目のデータ抽出が簡単であり、2分探索法では中央の値を 簡単に取り出せることから、O(log N)の処理が可能となる。 この一方で、C言語では配列サイズは固定であり、 最初の段階で適切なサイズが解らない場合は、メモリの使用効率を 低下させる。

これに加え、配列の欠点としてあげられるのが、途中データの削除・挿入となる。 配列の指定位置にデータを追加しようと思うと、 入れるべき場所に"空き"を作るために、以降のデータを１つ後ろにずらす必要がある。 削除でも同様に、１つ前にずらす処理が必要となる。 これにかかる処理時間は、最悪N件、最低で0件となることから、平均N/2回の ループを要し、O(N)の処理が必要となる。

これらの欠点の対応方法として、配列であれば、次のデータの入っている 場所を使えば良い。

((リストを配列で))
top: 3
data,next
0:  41  1    int data[..] ;
1:  60  -1   int next[..] ;
2:  10  4    for( p = top ; p >= 0 ; p = next[ p ] )
3:   6  2        printf( "%d" , data[ p ] ) ;
4:  22  5
5:  34  0

この方法は、アパートの回覧板で、部屋の住人は「次の部屋の人の番号を知っていれば十分」という状況と同じである。 この方式であれば、たとえデータを追加したい場合でも、 例えば30を追加するのであれば、data[4]の後ろに追加したいのであり、 data[6] = 30 を保存し、next[4] = 6、next[6] = 5 とすれば、途中にデータを混ぜることができる。

この方法によって、データを途中に追加する場合でも、O(1)で挿入が可能となる。 (ただし挿入すべき場所を探すにはO(N)の時間を要する)

リスト構造

一方でこのままでは、data[],next[]の最初の配列サイズ以上のデータを保存することは できない。そこで必要に応じてメモリを確保する方法をとる。

// 基本となるリスト構造の宣言
struct List {
int data ;
struct List* next ;
} ;
// 手作業で地道にリストを生成
struct List* top ;
top = (struct List*)malloc( sizeof(struct List) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->data = 2 ;
top->next->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->next->data = 3 ;
top->next->next->next = NULL ;
// リストデータを表示
struct List* p ;
for( p = top ; p != NULL ; p = p->next )
printf( "%d" , p->data ) ;

このような方法であれば、必要に応じてメモリを確保するため、 配列サイズが途中で不足するといった事態を考える必要がない。 (mallocがNULLを返すことは考える必要があるけど…) 一方、欠点としては、データを参照する場合には、 先頭から１つづつアクセスする必要があり、 中央データを参照して２分探索といったテクニックは使えない。

• 05/21 いいねぇ〜 "素人でも使いやすい回路図エディタBSch3V" http://tinyurl.com/6wdovm #fnct
• 05/21 いいねぇ〜… RT @jun1s: 先日も、市内の某ＩＴ会社の役員達と飲んでいたわけだが、曰く、「いい人材の雇用はとかく難しい。面接やテストだけではなかなか測れない。奥が深い。しかし、高専卒は別。彼らは安心して採用できる。5年間彼らを見てきた先生達から意見を… #fnct

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。

演習も終わった所で、同じプログラムを効率良く記述できることを知ることを 目標に、bit演算や#defineマクロを説明する。

浮動小数点データ

浮動小数点形式のデータは、float,double の2通りがあるが、最近はほとんど double 型で 計算をすれば十分。単精度実数(float)と、その倍の倍精度実数(double)

((float))
S:符号(1bit)
E:指数部(8bit)
F:仮数部(23bit)
SEEE,EEEE,EFFF,FFFF,FFFF,FFFF,FFFF,FFFF
指数部 - 127
float = 1.仮数部 * 2
((double))
S:符号(1bit)
E:指数部(11bit)
F:仮数部(52bit)
SEEE,EEEE...EEEE,FFFF,FFFF,.....,FFFF,FFFF
指数部 - 1023
double = 1.仮数部 * 2

bit演算子

2進数,8進数,16進数の変換プログラムでは、 2,8,16といった数値で割った余りや、商を求めることが多い。 コンピュータ内は2進数で扱っているため、16での余りを求める計算は、 下4bitを取り出したり、16で割るという計算は4ビットシフトに置き換えられる。 そこで、AND(&),OR(|),XOR(^),NOT(~)などのbit演算を説明。

printf( "%d" , 5 & 3 ) ; // 0101 & 0011 = 0001 = 1)10
printf( "%d" , 5 | 3 ) ; // 0101 | 0011 = 0111 = 7)10
printf( "%d" , 5 ^ 3 ) ; // 0101 ^ 0011 = 0110 = 6)10
printf( "%d" , 5 << 2 ) ; // 0101 左2bitシフト = 010100 = 20)10
printf( "%d" , ~10 + 1 ) ; // 反転+1は2の補数 = -10

#defineマクロ

N進数変換のプログラムの中には、下記のような部分があるけど、これを シンプルに書くためには、#defineマクロがよく利用される。

char s[...] ;
if ( '0' <= s[i] && s[i] <= '9' ) ....
#define isdigit(C) ('0' <= (C) && (C) <= '9')
if ( isdigit( s[i] ) ) ...

C言語のプログラムは、最初にプリプロセッサと呼ばれる文字列置換プログラムによって、 #include や、#define の処理が行われる。 #define は、指定された文字を、指定された文字に置換する。 #define マクロは、それを関数的に記載できるようにしたもの。 閉じたサブルーチンと開いたサブルーチンの説明は次回に行う予定。