リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。

bit演算子

2進数を使った処理をする時には、bit演算子を用いる。

#include <stdio.h>

int main() {
   // bit演算子と論理演算子
   printf( "%d¥n" , 12 &  5 ) ;  // 1100 & 0101 = 0100 よって 4が表示される
   printf( "%d¥n" , 12 && 0 ) ;  // 0が表示　論理演算子とbit演算子の違い
   printf( "%d¥n" , 12 |  5 ) ;  // 1100 | 0101 = 1101 よって 13が表示される
   printf( "%d¥n" , 12 || 0 ) ;  // 1が表示 
   // シフト演算子
   printf( "%d¥n" ,  3 << 2 ) ;  // 12が表示
   printf( "%d¥n" , 12 >> 2 ) ;  // 3が表示
   // おまけ
   printf( "%d¥n" , ~(unsigned)12 + 1 ) ;  // 2の補数(NOT 12 + 1) = -12
   return 0 ;
}

2進数を用いた集合計算

リストによる集合の前に、もっと簡単な集合処理を考える。

最も簡単な方法は、要素に含まれる=1 か 含まれない=0 を配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に1を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、演習課題として穴埋めを含むので注意。

• set-array.cxx

しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報を、整数型で保存しているためメモリの無駄である。

データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc , ba ∪ bc の計算を行う例である。

// 符号なし整数を uint_t とする。
typedef unsigned int uint_t ;

// uint_tのbit数
#define UINT_BITS (sizeof( uint_t ) * 8)

// 集合の内容を表示
void bit_print( uint_t x ) {
   for( int i = 0 ; i < UINT_BITS ; i++ )
      if ( (x & (1 << i)) != 0 )
         printf( "%d " , i ) ;
   printf( "\n" ) ;
}
void main() {     // 98,7654,3210
   // ba = {1,2,3} = 00,0000,1110
   uint_t ba = (1<<1) | (1<<2) | (1<<3) ;
   // bb = {2,4,6} = 00,0101,0100
   uint_t bb = (1<<2) | (1<<4) | (1<<6) ;
   // bc = {4,6,9} = 10,0101,0000
   uint_t bc = (1<<4) | (1<<6) | (1<<9) ;

   bit_print( ba & bb ) ; // ba ∩ bb = {2}                 
   bit_print( bb & bc ) ; // bb ∩ bc = {4,6}
   bit_print( ba | bc ) ; // ba ∪ bc = {1,2,3,4,6,9}
}

このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数探索がある。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。

uint_t prime = 0 ; // 初期値=すべての数は素数とする。

void filter() {
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      if ( (prime & (1 << i)) == 0 ) {
         // iの倍数には、非素数の目印(1)をつける
         for( int j = 2*i ; j < UINT_BITS ; j += i )
            prime |= (1 << j) ;
      }
   }
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      // 目印のついていない数は素数
      if ( (prime & (1 << i)) == 0 )
         printf( "%d\n" , i ) ;
   }
}

ミニ課題

最初に示した、配列による集合の set-array.cxx で、配列による和集合、エラトステネスのふるいの処理の一部を記述していない。未完成の部分を埋めて、動作を確認せよ。

前回授業の、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 ) ; 
}

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

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