ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論

情報構造論」カテゴリーアーカイブ

2020年9月
 12345
6789101112
13141516171819
20212223242526
27282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

集合とリスト処理

リストを用いた待ち行列の補足

# リストによる待ち行列を早速に創造工学演習で応用した人からの質問より…

以前に説明したリストを用いた待ち行列(queue)において、時間的都合から詳しく説明できなかった点の注意点を説明する。

待ち行列の説明では、get() の処理を以下のように示していた。しかし、このままでは、待ち行列が1件の状態で、以下のような get() を実行するとポインタが以下のような図に示される状態となり、tail ポインタがおかしい状態となる。

struct List* queue = NULL ;
struct List** tail = &queue ;
// 待ち行列の先頭から取り出す。
int get() {
   struct List* d = queue ;
   int ans = d->data ;
   queue = queue->next ;
   free( d ) ;
}

このため、待ち行列内のデータ件数が 0 件になる時だけ、tail ポインタが正しくなるような特別処理を加える必要がある。こういった特別処理は、以後の授業で説明する双方向リスト(deque:double-ended queue)などでは、プログラムを複雑化させてしまうので、別途「番兵」というテクニックが使われる。

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)

しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。また、今までの授業で説明してきた cons() などを使って表現すれば、簡単なプログラムでリストの処理が記述できる。

// 先週までに説明してきたリスト構造と補助関数
struct List {
   int     data ;
   struct List* next ;
} ;
// リストの入れ物を1つ作る
struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}
// リストを表示
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next ) {
      printf( "%d " , p->data ) ;
   }
   printf( "\n" ) ;
}
// リストの中に指定要素があるか判定(有れば1,無ければ0)
int find( struct List* p , int key ) {
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return 1 ;
   return 0 ;
}

例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 両方に含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。

// 集合積の計算
struct List* set_prod( struct List* a , struct List* b ) {
   struct List* ans = NULL ;
   for( ; a != NULL ; a = a->next ) {
      // aの要素がbにも含まれていたら、ansに加える
      if ( find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   }
   return ans ;
}
void main() {
   struct List* a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
   struct List* b = cons( 2, cons( 4, cons( 6, NULL ) ) ) ;
   struct List* c = cons( 4, cons( 6, cons( 9, NULL ) ) ) ;
   print( set_prod( a , b ) ) ;
   print( set_prod( b , c ) ) ;
}

例題として、和集合差集合などを考えてみよう。

リストの共有と削除の問題

リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。リストの全要素を捨てる処理であれば、以下のようになるであろう。

void list_free( struct List* p ) {
   while( p != NULL ) {
      struct List* d = p ;
      p = p->next ;
      free( d ) ; // 順序に注意
   }
}

一方、前説明の和集合(a ∪ b)のプログラムを以下のように作った場合、list_freeの処理は問題となる。

// 集合和
struct List* set_union( struct List*a, struct List*b ) {
   struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
void main() {
   struct List*a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
   struct List*b = cons( 2, cons( 3, cons( 4, NULL ) ) ) ;
   struct List*c = set_union( a , b ) ;
   // a,b,cを使った処理
   // 処理が終わったので、a,b,cを捨てる
   list_free( a ) ;
   list_free( b ) ;
   list_free( c ) ;
   // c = { 1 , (bのリスト) }
   // (b)の部分は先のlist_free(b)で解放済み
}

このような、リストb,リストcで共有されている部分があると、データの廃棄処理をどのように記述すべきなのか、問題となる。

これらの解決方法としては、(1) set_union() の最初で、ans=b となっている部分を別にコピーしておく、(2) 参照カウンタ法を用いる、(3) ガベージコレクタのある言語を用いる…などがある。(2),(3)は後期授業で改めて解説を行う。

// 同じ要素を含む、新しいリストを作る
struct List* copy( struct List*p ) {
   struct List*ans = NULL ;
   for( ; p != NULL ; p = p->next )
      ans = cons( p->data , ans ) ;
   return ans ;
}
struct List* set_union( struct List*a, struct List* b ) {
   struct List* ans = copy( b ) ;
   // この後は自分で考えよう。
}

理解確認

  • 2進数を用いた集合処理は、どのように行うか?
  • リスト構造を用いた集合処理は、どのように行うか?
  • 積集合(A ∩ B)、和集合(A ∪ B)、差集合(A – B) の処理を記述せよ。

集合とビット演算

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

bit演算子

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

bit AND 3 & 5
0011)2 & 0101)2= 0001)2
論理演算子
if ( a == 1 && b == 2 ) …
bit OR 3 | 5
0011)2 | 0101)2= 0111)2
論理演算子
if ( a == 1 || b == 2 ) …
bit NOT ~5
~ 00..00,0101)2= 11..11,1010)2
論理否定演算子
if ( !a == 1 ) …
bit EXOR 3 ^ 5
0011)2 ^ 0101)2= 0110)2
bit 左シフト 3 << 2
0011)2 << 2 = 001100)2
3 * 22 と同じ
bit 右シフト 12 >> 2
1100)2 >> 2 = 11)2
12 / 22 と同じ
#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を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、演習課題として穴埋めを含むので注意。

しかし、上述のプログラムでは、要素に含まれる/含まれないという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 で、配列による和集合、エラトステネスのふるいの処理の一部を記述していない。未完成の部分を埋めて、動作を確認せよ。

スタックと待ち行列

前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。

計算処理中に一時的なデータの保存として、stackとqueueがよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。

スタック

配列を用いたスタック

一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;

void push( int x ) { // データをスタックの一番上に積む
    stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
    return stack[ --sp ] ;
}
void main() {
    push( 1 ) ; push( 2 ) ; push( 3 ) ;
    printf( "%d\n" , pop() ) ; // 3
    printf( "%d\n" , pop() ) ; // 2
    printf( "%d\n" , pop() ) ; // 1
}

++,–の前置型と後置型の違い

// 後置インクリメント演算子
int i = 100 ;
printf( "%d" , i++ ) ;
// これは、
printf( "%d" , i ) ;
i++ ;
// と同じ。100が表示された後、101になる。

// 前置インクリメント演算子
int i = 100 ;
printf( "%d" , ++i ) ;
//   これは、
i++ ;
printf( "%d" , i ) ;
// と同じ。101になった後、101を表示。

リスト構造を用いたスタック

しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。

struct List* stack = NULL ;

void push( int x ) { // リスト先頭に挿入
    stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
    int ans = stack->data ;
    struct List* d = stack ;
    stack = stack->next ;
    free( d ) ;
    return ans ;
}

キュー(QUEUE)

2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。

配列を用いたQUEUE / リングバッファ

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。

#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read  pointer(読み出し用)

void put( int x ) { // 書き込んで後ろ(次)に移動
    queue[ wp++ ] = x ;
    if ( wp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
    int ans = queue[ rp++ ] ;
    if ( rp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        rp = 0 ;
    return ans ;
}
void main() {
    put( 1 ) ; put( 2 ) ; put( 3 ) ;
    printf( "%d\n" , get() ) ; // 1
    printf( "%d\n" , get() ) ; // 2
    printf( "%d\n" , get() ) ; // 3
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか?

リスト構造を用いたQUEUE

前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。

この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。

struct List* queue = NULL ;
struct List** tail = &queue ;

void put( int x ) { // リスト末尾に追加
    *tail = cons( x , NULL ) ;
    tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
    int ans = queue->data ;
    struct List* d = queue ;
    queue = queue->next ;
    free( d ) ;
    return ans ;
}

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。

理解確認

  • 配列を用いたスタック・待ち行列は、どのような処理か?図などを用いて説明せよ。
  • リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
  • スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか?欠点があるか説明せよ。

リスト処理基本の回答

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

 

リストへの追加処理

最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。

最も単純なリスト挿入

struct List {
   int          data ;
   struct List* next ;
} ;

// 保存するリストの先頭
struct List* top = NULL ;

void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
                      //  ~~~~~~~(A)
      printf( "%d " , p->data ) ;
           // ~~~~~(B)
   printf( "¥n" ) ;
}//~~~~~~~~~~~~~~(C)
int main() {
   int x ;
   while( scanf( "%d" , &x ) == 1 ) {
      //  ~~~~~~~~~~~~~~~~~~(D)
      top = cons( x , top ) ;
   }
   print( top ) ; // 前回示したリスト全要素表示
   return 0 ;
}
// (1) 入力で、11 , 22 を与えるとどうなる? - 下図参照
// (2) 練習問題(A),(B),(C),(D)の型は?
// (3) 入力で、11,22 の後に 33 を与えるとどうなる?

// C++ コンテナクラスで書くと...(auto を使うには C++11 以上)
// #include <iostream>
// #include <forward_list>
// #include <algorithm>
// int main() {
//    std::forward_list<int> top ;
//    int x ;
//    while( std::cin >> x )
//       top.push_front( x ) ;
//    for( auto i = top.cbegin() ; i != top.cend() ; ++i )
//       std::cout << *i << std::endl ;
//    return 0 ;
// }

ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい。

要素を末尾に追加

前に示した方法は、逆順になるので、与えられた要素が末尾に追加する方法を示す。

struct List* top = NULL ;
struct List** tail = &top ;

int main() {
   int x ;
   while( scanf( "%d" , &x ) == 1 ) {
      //  ~~~~~~~~~~~~~~~~~~~~~~~(A)
      *tail = cons( x , NULL ) ;
      tail = &((*tail)->next) ;
   }//~~~~~~~~~~~~~~~~~~~~~~~(B) 下記の解説参照
   print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(C)
   return 0 ;
}
// (1) 入力で 11,22 を与えるとどうなる? - 下図参照 
// (2) 練習問題(A),(C)の型は?
// (3) 11,22の後に、さらに 33 を与えるとどうなる?

この方法は、次回にデータを追加する場所(末尾だからNULLが入っている)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。

理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。

途中でデータ挿入・データ削除

リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。

void insert( struct List*p , int data ) {
   // あえて、補助関数consを使わずに書いてみる
   struct List* n ;
   n = (struct List*)malloc( sizeof( struct List ) ) ;
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A)
   if ( n != NULL ) {
      n->data = data ;
                ~~~~(B)
      n->next = p->next ;
                ~~~~~~~(C)
      p->next = n ;
   }
   // consを使って書けば、簡単
   //  p->next = cons( data , p->next ) ;
}

int main() {
   struct List* top = cons( 11 , cons( 22 , cons( 44 , NULL ) ) ) ;
   //                                      ↑
   insert( top->next , 33 ) ;           // ここに33を挿入したい
   return 0 ;
}

void remove_after( struct List* p ) {
   struct List* del = p->next ;
   p->next = del->next ;
   free( del ) ;
}

int main() {
   struct List* top = cons( 11 , cons( 22 , cons( 33 , cons( 44 , NULL ) ) ) ) ;
   remove_after( top->next ) ;                //  ↑
   return 0 ;                                 // これを消したい
}

理解度確認

上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。

レポート課題

以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) の番号の課題に取り組むこと。

  1. 緯度(latitude)経度(longitude)とその場所の都市名(city)
  2. 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
  3. 複素数(re,im)

このようなプログラムを作るのであれば、以下の例を参考に。

struct NameAgeList {
   char                name[ 20 ] ; // 名前
   int                 age ;        // 年齢
   struct NameAgeList* next ;       // 次のデータへのポインタ
} ;
struct NameAgeList* na_cons( char* nm, int ag,
                             struct NameAgeList*p )
{  struct NameAgeList* ans ;
   ans = (struct NameAgeList*)malloc(
               sizeof( struct NameAgeList ) ) ;
   if ( ans != NULL ) {
      strcpy( ans->name , nm ) ;
      ans->age  = ag ;
      ans->next = p ;
   }
   return ans ;
}

int main() {
   struct NameAgeList* top = NULL ;
   struct NameAgeList* p ;
   char buff[ 1024 ] ;
   // 1行読み込みの繰り返し
   while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
      char nm[ 100 ] ;
      int ag ;
      // 1行の中から名前と年齢があったら na_cons で挿入保存
      if ( sscanf( buff , "%s%d" , nm , &ag ) == 2 ) {
         top = na_cons( nm , ag , top ) ;
      }     
   }
   // 読み込んだデータを全部出力
   for( p = top ; p != NULL ; p = p->next )
      printf( "%s %d¥n" , p->name , p->age ) ;
   return 0 ;
}

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

授業の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() が用意されている。

C言語標準関数 Microsoft関数 備考
scanf() scanf_s() 汎用フォーマット入力
printf() printf_s() 汎用フォーマット出力
strcpy() strcpy_s() 文字列コピー
同様の関数: strncpy()
strdup() _strdup() 文字列をヒープメモリにコピー

すでに提出されているレポートを見ると、同様に 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” と表示される。

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

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

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

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

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

リスト処理

リスト構造

リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。

まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、1つ1つのデータをポインタでつなげる処理を示す。

#include <stdio.h>
#include <stdlib.h>

// List構造の宣言
struct List {
   int          data ;  // データ保存部
   struct List* next ;  // 次のデータへのポインタ
} ;

int main() {
   struct List* top ;   // データの先頭
   struct List* p ;

   // (1)
   top = (struct List*)malloc( sizeof( struct List ) ) ;
   top->data = 111 ;
   // (2)
   top->next = (struct List*)malloc( sizeof( struct List ) ) ;
   top->next->data = 222 ;
   // (3)
   top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
   top->next->next->data = 333 ;
   top->next->next->next = NULL ; // 末尾データの目印

   for( p = top ; p != NULL ; p = p->next ) {
      printf( "%d¥n" , p->data ) ;
   }
   return 0 ;
}

このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。

NULLって何?

前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。

同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。

#define NULL 0

補助関数

上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。

struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}

int main() {
   struct List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   return 0 ;
}

補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP) というプログラム言語でのリスト(セル)を生成する関数が cons 。

typedefを使った書き方

List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。

// typedef の使い方
//    typedef 型宣言 型名 ;
typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい
uint32 x = 12345 ;

typedef struct LIST {     // 構造体のタグ名と新しくつける型名と重複できない
      int   data ;        // のでこの時点のタグ名は "LIST" としておく
      struct LIST* next ;
   } List ;

List* cons( int x , List* n ) {  // C++なら struct List { ... } ; と書く
   List* ans ;                   // だけでこういう表記が可能
   ans = (List*)malloc( sizeof( List ) ) ;
   :
   ((略))
}
int main() {
   List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   ((略))
}

最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。

// 最近のC++なら...
struct List {
public:
   int   data ;
   List* next ;
public:
   List( int x , List* n )
     : data( x ) , next( n ) {}
} ;

int main() {
   List* top = new List( 1 , new List( 2 , new List( 3 , NULL ) ) ) ;
   :
}

LISPと関数型プログラミング言語

LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらいに遡る。最初は、人工知能(AI)のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。

関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しの関数で書けばいい…。

LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。

古いAI※※と最近のAIの違い

最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。

LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというと「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すようなもの。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。

しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習ディープラーニングという技法により今まで難しかった右脳の機能を実現することで、左脳と右脳の機能を兼ね備えたものとなっている。

将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。

簡単なリスト処理の例

先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。

// 全要素を表示する関数
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
      printf( "%d " , p->data ) ;
   printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
   int c = 0 ;
   for( ; p != NULL ; p = p->next )
      c++ ;
   return c ;
}
int main() {
   struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
   print( top ) ;
   printf( "%d¥n" , count( top ) ) ; 
   return 0 ;
}

リスト処理を自分で考えて作成

以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。

// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
   // (111+444+333)/3=296.0
   自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 (先頭0番目)
   // 見つからなかったら -1
   自分で考えよう
}

再帰呼び出しでリスト処理

リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか?

// 全データを表示
void print( struct List* p ) {
   if ( p == NULL ) {
      printf( "¥n" ) ;
   } else {
      printf( "%d " , p->data ) ;
      print( p->next ) ; // 末尾再帰
   }
}
// データ数を返す関数
int count( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 
   // 見つかったら1 , 見つからなかったら 0
   自分で考えよう
}

理解度確認

上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。

リスト構造について

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

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、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 ) {
      // 要素を1つ後ろにずらす処理
      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 ) ; 
}

 

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

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

遠隔の小テストを実施

遠隔授業の中、自分の担当科目で中間試験(小テスト)を実施した。学校としてはレポート課題で評価していいとの話なのでテスト形式の必要性はないけど、レポート課題方式ばかりだと後々の理解力が心配だし、やってみた。
Teamsでテスト問題を配布し、時間が来たらOfficeLenseで自分の回答をスキャンして、PDFで提出。問題は同じようなものを2つづつ準備し、出席番号が偶数なら、出席番号を2で割った値が偶数なら…で、問題が分散するようにしてある。問題の内容も、「図を交えて具体的に説明」といった形式の問題とした。
実施前は、OfficeLense使いこなせない学生が出ないか心配だったり、裏で情報交換で全員同じような回答にならないかの心配をしてた。でも、ざっと見た雰囲気だと、裏情報交換は少ないかなぁ。

裏で情報交換する可能性もあるけど、そこはあえて何も言わないようにした。「どうせ、みんな裏で情報交換するんだろーしぃ〜♪」といった雰囲気をだすと「だったら、やってもいいのか…」と思われるのもまずいので、実施方法だけを事前方法に伝えていた。

遠隔授業6回目の反省

遠隔授業も6回目。Web掲載の講義資料に、Microsoft Edgeのペン書き機能で、図などを交えた説明のスタイルでやってきた。私としては、講義資料のWeb掲載は数年前からやっていたので、黒板がWeb画面になっただけ…の感覚。

んで、今日は出席確認もかねてForms機能でアンケートで意見聞いたら、「書き込みのメモをとるのが追いつかない」とのご意見。

一応、講義の録画機能は使ってるし、書き込みすぎて逆にみづらくなった書き込みを消したりしてるけど、真面目にノートをとる人にしてみれば、ペースが早いみたい。

これまでも、できるだけ雑談を交えながら、ペースを落とすようにしているけど、雑談ネタでも書き込みしながら説明するもんだから、相変わらず追いつかないか… 反省!!