前回のmalloc+freeの理解確認のための課題の２回目ということで、 課題時間とするが、この後の授業進行のために、配列の問題点を説明する。

配列の問題点

現在、mallocの課題で、動的メモリ上に確保した配列上にデータを保存しているが、 基本は以下のような処理だろう。

int data[ 100 ] ;
int size = 0 ;
while( 入力繰り返し判定 ) {
data[ size++ ] = 入力値 ;
}

このプログラムであれば、すでに入力済みの配列にデータ1件を追加する処理は、 配列末尾に入れて、size を増やすだけの一定処理。このため、 データ追加はO(1) となる。
一方、この配列の中から目的データを探すには、登録データがデータ順とデタラメで あれば、配列先頭からループで探すしかない。つまり、データ検索はO(N)となる。

これに比べ、高速な検索方法として紹介した、2分探索法は、比較の度毎に対象が 半分となることから、検索時間はO(log N)となる。
しかしながら、新たにデータを追加する場合は、 挿入すべき場所を探す処理O(log N)と、１件分の場所を確保するために、 以下のようなループでデータをずらす処理となり、その処理時間はO(N) となる。

int pos = データを入れる場所 ;
for( i = N ; i >= pos ; i-- ) {
data[ i + 1 ] = data[ i ] ; // 後ろからずらさなとダメ
}

このことからも、配列は途中にデータを入れる処理が苦手といえる。 また、配列を扱うプログラムでは、データの追加がめったに発生せず、 データを探す処理が中心であれば、２分探索法が効率が良い。 しかし、途中でデータが頻繁に追加され、検索中心でないのであれば、 最初の末尾追加の使い方で良い。

文字コードとN進数の話が終わったので演習。 文字コードとN進数の理解のために、atoi() , itoa() のプログラムについて説明を行う。

ポインタの理解が怪しいので、次回の後半はポインタの説明としよう。

atoi() , iota()

int atoi( char s[] ) {
int ans = 0 ;
int i ;
for( i = 0 ; s[ i ] != '¥0' ; i++ )
if ( '0' <= s[i] && s[i] <= '9' )
ans = ans*10 + (s[i] - '0') ;
return ans ;
}
char* itoa( char ans[] , int x ) {
// x は 16bit相当とする。
int i ;
for( i = 4 ; i >= 0 ; i-- ) {
int d = x % 10 ;
ans[ i ] = '0' + d ;
x /= 10 ;
}
ans[ 5 ] = '¥0' ;
return ans ;
}
void main() {
char str[ 10 ] ;
printf( "%d¥n" , atoi( "123" ) ) ;
printf( "%s¥n" , itoa( str , 1234 ) ) ;
}

課題

前述の10進数文字列と数値の相互変換のatoi,itoaを参考に、 2進数、8進数、16進数などの変換プログラムを作成する。 プログラミングに自信がある場合は、文字列の先頭が"0"なら8進、"0x"なら16進と いった自動判別をしたり、小数点を含む"1.234"を実数に変換するプログラムなどに 取り組むこと。

レポートでは、(1)プログラムリスト、(2)プログラム説明、(3)動作確認、(4)考察 を記載すること。考察では感想ではなく、プログラムで扱える数値の範囲や、 制限を超えるような使い方をしたらどういった現象が発生するのかを検証するなど、 の記載を期待する。

• ビリヤード軌道予測システム
• Google Mapで陣取りゲームの案があったけど、 参考になりそうなリアルタイム系陣取りゲーム。Qix
• 参考 RFIDタグ / NFC
• 授業支援 moodle / ポートフォリオ Mahara

前回の授業でmallocについて説明をしたので、今日は実際に使ってみるということで、 課題。課題のテーマは以下の通り。

mallocを使ったデータベースの作成

構造体を使った昨年度の課題で、例えば「名前と電話番号」で、入力データをすべて記憶し、 そのデータを検索などに取り組んだ。 今回は、これを拡張し、malloc を使ってプログラムを作成する。 例えば、名前は寿限無のような長い名前の人がいるかもしれない。 構造体の配列は1クラスの50人程度ではなくって、1000人かもしれない。 プログラムの実行の前に、想定する最大データ件数を入力してから、データを覚える。

さまざまな宣言でメモリのイメージの違い

上記課題に取り組む前に、さまざまな宣言で、データのイメージがどう違うのかを説明した。

(( 名前の配列 ))
// 基本10文字50人なら
char name[ 50 ][ 10 ] ;
// 名前に寿限無のような人がいるかも...
char *name[ 50 ] ;
for( i = 0 ; i < 50 ; i++ ) {
char buff[ 1000 ] ;
scanf( "%s" , buff ) ;
name[ i ] = (char*)malloc( strlen( buff ) + 1 ) ;
if ( name[ i ] != NULL ) {
strcpy( name[ i ] , buff ) ;
}
}
// クラスも最大何人かは、動かす時にしかわからない？
char **name ;
int  size ;
scanf("%d" , &size ) ; // データ件数を入力
name = (char**)malloc( sizeof( char* ) * size ) ;
if ( name != NULL ) {
for( i = 0 ; i < size ; i++ ) {
char buff[ 1000 ] ;
scanf( "%s" , buff ) ;
name[ i ] = strdup( buff ) ; // malloc+strcpy
}
}

構造体の場合

構造体を使う例として、複素数のデータの配列の作り方の違いも、説明。

(( 構造体を使う例 ))
struct Complex {
double re , im ;
} ;
// 基本 50 個の複素数
struct Complex array[ 50 ] ;
array[ 0 ].re = 1 ; // array[ 0 ] = 1 + j2 ;
array[ 0 ].im = 2 ;
// ポインタの配列
struct Complex *array[ 50 ] ;
array[ 0 ] = (struct Complex*)malloc(
sizeof( struct Complex ) ) ;
if ( array[ 0 ] != NULL ) {
array[ 0 ]->re = 1 ;
array[ 0 ]->im = 2 ;
}
// 配列へのポインタ
struct Complex *array ;
array = (struct Complex*)malloc(
sizeof( struct Complex ) * 50 ) ;
if ( array != NULL ) {
array[ 0 ].re = 1 ;
array[ 0 ].im = 2 ;
}

配列サイズを途中で倍にするテクニック

配列のサイズが実行中もわからない場合のテクニックとして、 配列が不足した際に、配列サイズを倍にする方法を説明。

(( 整数配列サイズがわからない場合 ))
int *array ;
int rsize = 0 ;
int msize = 10 ;
int x ;
array = (int*)malloc( sizeof( int ) * msize ) ;
while( scanf( "%d" , &x ) == 1 ) {
// 配列に入れる前に、サイズ不足の場合
if ( rsize >= msize ) {
int *n_array ;
n_array = (int*)malloc( sizeof( int ) * msize * 2 ) ;
if ( n_array == NULL )
break ;
// 倍の配列に中身をコピー
for( int i = 0 ; i < msize ; i++ )
n_array[ i ] = array[ i ] ;
// 元の配列を捨てる
free( array ) ;
// 倍の配列を使うように
array = n_array ;
msize *= 2 ;
}
// 配列に追加
array[ rsize ] = x ;
rsize++ ;
}

雑談：学生さんが、電話場号を覚える時はどうする？という話をしていたので、 int型で電話を覚えるのはアリだけど、090 とか 0778 といった番号は使えないよね… という説明をする。桁数は？というから、ダイヤルトーン使えば長い番号もあるよね〜 と説明をしたけど、今の学生さんはダイヤルトーンのピポパ音を知らない。

ということで、ダイヤルパルスの話(110番に電話したけりゃ、オンフックボタンを、 ポン、ポン、ポポポポポポポポポポ(1秒以内に10回連打)とすればかかる)とか、 DTMF音(低群と高群の2つの音の合成で、正確に2つの音を発することができればかかる)とかを説明する。

前回の授業で話せなかった浮動小数点の話の後、N進数について説明し 演習などを行う。

浮動小数点の扱い

浮動小数点で扱える数値の範囲についても解説。 科学技術計算などで小数点以下のデータを扱う場合、float(単精度実数),double(倍精度実数) を利用する。この場合、数値は仮数部と指数部で扱うことを説明。

	符号(s)	仮数部(e)	指数部(d)	意味
float	1bit	8bit	23bit
double	1bit	11bit	52bit

float型は、小数を32bitのデータで扱い、double型は64bitで扱う。このため、以下の様な プログラムを書くと、異常な値が求まるため注意が必要。

double x ;
scanf( "%f" , &x ) ; // 3を入力
printf( "%f" , x ) ; // 3は表示されない。
// double型では"%lf"を使う。

N進数

N進数の取扱いということで、 整数部はNで割った余りを下の桁から並べる方法と、 小数部はNをかけて整数部を書き並べる方法について説明する。 例として、0.1₎₁₀を2進数に変換すると無限小数になることなども説明。

さらに配布資料を元に、ASCIIコード表や文字コードを使った計算例などを示す。 特に、8進数がC言語では、0123 といった0で始まる数字で表すこと、 16進数が、0x123 といった0xで始まる数字で表すことを説明。 さらに、printfなどのフォーマット指定では、
%d(10進数),%o(8進数),%x(16進数),
%f(float型/小数点形式),%e(float型/指数形式),%g(%f,%eの分かりやすい書式を利用)
といった話を説明する。

来週は、atoi() や itoa() を説明して演習を行う予定。