前回の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)考察 を記載すること。考察では感想ではなく、プログラムで扱える数値の範囲や、 制限を超えるような使い方をしたらどういった現象が発生するのかを検証するなど、 の記載を期待する。