前回授業の、sum(),max(),mean(),find() のループ版や、再帰版のプログラム例

// 合計ループ版
int sum( struct List* p ) {
   int s = 0 ;
   for( ; p != NULL ; p = p->next )
      s += p->data ;
   return s ;
}

// 合計再帰版
int sum( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data + sum( p->next ) ; // 場所のデータと以降の合計
}

// 最大値ループ版
int max( struct List* p ) {
   if ( p == NULL ) {
      return 0 ;
   } else {
      int m = p ->data ;                // 先頭を仮の最大値
      for( p = p->next ; p != NULL ; p = p->next )
         if ( m < p->data )             // それ以降から大きい物を見つけたら
            m = p->data ;               // その値を最大値として保存
      return m ;
   }
}

// 最大値再帰版
int max( struct List* p ) {
   if ( p == NULL ) // data0件で0を返すことにする
      return 0 ;
   else if ( p->next == NULL )
      return p->data ;
   else {
      int m = max( p->next ) ;   // 以降のデータの最大値より
      if ( m < p->data )         // その場所のデータが大きい
         return p->data ;
      else
         return m ;
   }
}

// 平均ループ版
double mean( struct List* p ) {
   int c = 0 , s = 0 ;
   for( ; p != NULL ; p = p->next ) {
      c++ ;
      s += p->data ;
   }
   return (double)s / (double)c ;
}

// 平均の再帰版
// ただし、 mean( top , 0 , 0 ) のように呼び出す。
double mean( struct List* p , int s , int c ) { // s はリストの合計
   if ( p == NULL )                             // c はリストの件数
      return (double)s / (double)c ;
   else
      return mean( p->next , s + p->data , c + 1 ) ;
}
// C++なら、meanの宣言に引数のデフォルト値を指定すれば
// double mean( struct List* p , int s = 0 , int c = 0 ) { ... }
// printf( "%lf" , mean( top ) ) ; みたいな使い方ができる。

// findループ版
int find( struct List* p , int key ) {
   int i = 0 ;
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return i ; // 見つかったらi番目
      else
         i++ ;
   return -1 ; // 見つからなかったら(-1)
}

// find再帰版
// ループ版とは返り値の取り扱いが違うので注意
int find( struct List* p , int key ) {
   if ( p == NULL )
      return 0 ; // 見つからなかった
   else if ( p->data == key )
      return 1 ;
   else
      return find( p->next , key ) ;
}

授業のC言語のプログラムで printf 関連でいくつか質問を受けることが多いのでメモ

Visual Studio では printf_s() , scanf_s() を使う

Microsoft の Visual Studio でプログラミングの勉強をする人も多いだろうが、C 言語の基本関数 printf() とか scanf() を使ったプログラムが動かないというトラブルを聞く。

C言語の scanf() がバッファオーバーフロー対策が怪しいため、Visual Studio(Microsoft) では保護対策してある scanf_s() があり、これを使えということになっている。バッファオーバーフローの危険があるのは、scanf() なんだけど、同様に printf() の代わりに、printf_s() が用意されている。

すでに提出されているレポートを見ると、同様に strcpy() もセキュリティ対策の strcpy_s() を使っている人も多いようです。

マイクロソフト御謹製の strcpy_s() を使わなくても、C言語標準関数には strncpy() があるが、若干動きが違うみたい。

バックスラッシュ∖ と円マーク ￥

元々コンピュータの 8bit で表現する基本的な英数字には、ASCII コード表が決められている。ASCII コード表の中では、0x5C には、バックスラッシュ「∖」が割り振られている。コンピュータが日本で使われるようになると、ASCII コード表に、半角カタカナを追加した JIS コード表(1バイト文字) が決められている。文字コード 0x00～0x7F までは ASCII コードと基本的に同じであるが、唯一 0x5C には、∖ の代わりに円マーク「￥」が割り振られた。

このため、C言語の 改行文字を表す “∖n” は、日本のパソコンで表示すると“￥n”と表示されるし、日本語のコンピュータの教科書では、”￥n”にて記載されていることが多い。同様に、Windows のディレクトリ区切り文字は本来∖であり、ファイルパスは“C:∖Users∖foobar” のように示されるが、日本のパソコンでは、“C:￥Users￥foobar” と表示される。

プログラムのエディタでＣ言語のプログラミングをする際は、以前であれば、キーボードの￥マークをタイプすれば、￥が表示されるが、内部的には文字コード 0x5C で保存される。最近の開発環境なら、￥マークをタイプすれば、∖ が表示されるものも増えてきた。

ただ、エディタによっては、今まで内部コードでの 0x5C を、英文字フォントならバックスラッシュ ∖(Unicode 0x5C) 、日本語フォントなら 円マーク ￥ (Unicode 0xA5) と明確に区別している場合がある。

私の講義資料では、改行は “￥n” にて見えるはず。入力時には状態によって∖に見えたり￥に見えたりするので、Web画面で表示される時の文字フォントの影響を受けているようだ。

このため、私の講義資料をコピー＆ペーストで、∖と￥を明確に区別するエディタに張り付けると、0x5C でなく 0xA5 として扱われることがある。この内容をＣ言語でコンパイルしてprintf(“Hello World.￥n”);を実行すると、行末で改行されず「Hello World￥n」と表示されることがある。

この資料を書くにあたって、∖と￥をWordPressのエディタで入力しているが、実は∖は「差集合記号」で記載しているし、￥は「全角円マーク」で記載している。

データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。

int find( int array[] , int left , int right , int key ) {
   // データは left から right-1までに入っているとする。
   while( left < right ) {
      int mid = (left + right) / 2 ; // 中央の場所
      if ( array[ mid ] == key )
         return mid ;                // 見つかった
      else if ( array[ mid ] > key )
         right = mid ;               // 左半分にある
      else
         left = mid + 1 ;            // 右半分にある
   }
   return -1 ; // 見つからない
}

しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。

void entry( int array[] , int* psize , int key ) {
   // データを入れるべき場所を探す処理
   for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、
      if ( array[ i ] > key )          // O(log N) でも書けるけど
         break ;                       // 単純に記載する。
   if ( i < *psize ) {
      // 要素を１つ後ろにずらす処理
      for( int j = *psize ; j > i ; j-- ) //  O(N)の処理
         array[ j ] = array[ j - 1 ] ;
      array[ i ] = key ; 
   } else {
      array[ *psize ] = key ;
   }
   (*psize)++ ;
}

これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。

この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。

順序が重要なデータ列で途中へのデータ挿入削除

例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。

  101   102   103   104   105   106
[ 105 | 106 |  -1 | 102 | 104 | 103 ]

このように次のデータの場所という概念を使うと、データの順序を維持して扱うことができる。

struct LIST {
   int data ;
   int next ;
} ;
struct LIST array[] = {
   /*0*/ { 11 ,  2 } , 
   /*1*/ { 67 ,  3 } ,  // 末尾にデータ34を加える
   /*2*/ { 23 ,  4 } ,  // { 23 , 5 } ,
   /*3*/ { 89 , -1 } ,  // 末尾データの目印
   /*4*/ { 45 ,  1 } ,
   /*5*/ {  0 ,  0 } ,  // { 34 , 4 } ,
} ;
for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
   printf( "%d¥n" , array[ idx ].data ) ; 
}

この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。

しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。