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

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

2020年11月
1234567
891011121314
15161718192021
22232425262728
2930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

演算子と2分木による式の表現

2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+  # 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか?3/2だろうか?

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド記法の式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) { if ( isdigit( *p ) ) { // ~~(A) // 数字はスタックに積む push( *p - '0' ) ; // ~~~~~~~~(B) } else if ( *p == '+' ) { // 演算子+は上部2つを取出し int r = pop() ; int l = pop() ; // 加算結果をスタックに積む push( l + r ) ; } else if ( *p == '*' ) { // 演算子*は上部2つを取出し int r = pop() ; int l = pop() ; // 乗算結果をスタックに積む push( l * r ) ; }//~~~~~~~~~~~~~(C) } // 最終結果がスタックに残る return pop() ; } void main() { printf( "%d\n" , rpn( "123*+" ) ) ; }

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
                   struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      n->data  = op ;
      n->left  = l ;
      n->right = r ;
   }
   return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL ) {
      // 数値のノードは値を返す
      return p->data ;
   } else {
      // 演算子のノードは、左辺値,右辺値を求め
      // その計算結果を返す
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) ,
                        tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか?
  • 上記プログラム中の(A)~(F)の型を答えよ。

意思決定木と構文解析

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:うちの子供が発熱した時))
       38.5℃以上の発熱がある?
      no/         \yes
   元気がある?        むねがひいひい?
 yes/    \no      no/     \yes
様子をみる 氷枕で病院  解熱剤で病院  速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",NULL,NULL ) ,
                    dtree( "氷枕で病院",NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:翻訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:通訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
      最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
  • エミュレーター
    • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
      近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。

      • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コードとして出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
 ↓       Java コンパイラ
foo.class (中間コード)
 ↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言     「abd|acd」は、abd または acd にマッチする。
グループ化 「a(b|c)d」は、真ん中の c|b をグループ化
量化    パターンの後ろに、繰り返し何回を指定
      ? 直前パターンが0個か1個
       「colou?r」
      * 直前パターンが0個以上繰り返す
       「go*gle」は、ggle,gogle,google
      + 直前パターンが1個以上繰り返す
       「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
      「[0-9]+」012,31415,...数字の列
^     行頭にマッチ
$     行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

  +
 / \
1   *
   / \
  23   456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。

2020年度前期授業アンケート

情報構造論

情報構造論は通年科目なので、中間状況だけど、ひとまず80ポイント越え。1件だけ最低評価が並んでいるのが気がかり。不満のある人が積極的に質問してくれるといいのだが。

オブジェクト指向プログラミング

オブジェクト指向は、専攻科2年相手の前期科目。課題でやや不満が1件あるけど、難しかったのだろうか。設定が曖昧だったのだろうか。

情報制御基礎

情報制御基礎は、3年生の学際科目で全学科対象の授業。「テストの過去問題がWebに掲載してあり勉強しやすかった」といった趣旨の意見もあり、評価も高かった。

どの授業も、コロナによる遠隔授業であったが、例年 Web に掲載している講義資料をそのまま使い、Teams のWeb会議でMicrosoft Edge のペン書き機能を使いながら補足説明を書き込みしながら行なった。Web会議は録画しておき、オンデマンドで視聴できるようにしておいたので、コロナ遠隔授業といいながらも、授業の進め方は今まで通りにすすめたつもり。

AVLと2分ヒープ

前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。

2分探索木へのデータ追加と不均一な木の成長

先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。

しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか?

  • 86, 53, 11 – 降順のデータ
  • 12, 24, 42 – 昇順のデータ

この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。

AVL木

このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。

このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)

この様に、左右の枝の大きさが不均一な場所を見つけ、右回転や左回転を行う処理を繰り返すことで、段数が均一な2分探索木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。

理解確認

  • 木の根からの段数を求める関数 tree_depth() を作成せよ。
    例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数
_____ tree_depth( _______________ p ) {
   if ( p == NULL ) {
      return _____ ;
   } else {
      int d_L = ______________ ;
      int d_R = ______________ ;
      if ( d_L > d_R )
         return _____ ;
      else
         return _____ :
   }
}

// pをつなぎ替え上部を返り値で返す。
struct Tree*rot_right( struct Tree* p ) {
   struct Tree* pl = p->left ;
   struct Tree* pr = pl->right ;
   pl->right = p ;
   p->left = = pr ;
   return pl ;
}
int main() {
   printf( "%d¥n" , tree_depth( top ) ) ;
   top = rot_right( top ) ;
   return 0 ;
}

2分ヒープ(binary heap)

2分探索木では、1つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の1つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝2×i+1 番目、右の枝2×i+2 番目であることが判る。

このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。

int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;

// 2分ヒープを表示
void print_heap( int array[] , int idx , int size ) {
   if ( idx < size ) {
      // 左の枝を表示
      print_heap( array , 2*idx + 1 , size ) ;
      // 真ん中の枝を表示
      printf( "%d " , array[ idx ] ) ;
      // 右の枝を表示
      print_heap( array , 2*idx + 2 , size ) ;
   }
}

// 2分ヒープから key を検索
int find_heap( int array[] , int idx , int size , int key ) {
   while( idx < size ) {
      if ( array[ idx ] == key )
         return idx ; // 見つかったら配列の番号を返す
      else if ( array[ idx ] _____ key )  // 何が入るか考えよう
         idx = ________________ ;
      else
         idx = ________________ ;
   }
   return -1 ; // 見つからなかったら、-1 を返す
}
int main() {
   print_heap( a , 0 , 7 ) ;
   if ( find_heap( a , 0 , 7 , 65 ) >= 0 )
      printf( "Find!!¥n" ) ;
   return 0 ;
} 

2分探索木の処理とデータ追加処理

前回の授業では、当初予定に加え、この後に示すデータの追加処理の説明を行った。その代わり、簡単な2分木の演習が抜けていたので少し演習を追加。

2分木の簡単な処理

int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->left )
               + count( p->right ) ;
}
int sum( struct Tree* p ) { // データ合計
   if ( p == NULL )
      return 0 ;
   else
      return p->data + sum( p->left )
                     + sum( p->right )
}
int max( struct Tree* p ) { // 最大値
   if ( p == NULL ) {
      return 0 ; // データ件数=0のとき0が最大値でいいのかなぁ?
   } else {
      while( p->right != NULL )
         p = p->right ;
      return p->data ;
   }
}
int depth( struct Tree* p ) { // 木の深さ
   if ( p == NULL ) {
      return 0 ;
   } else {
      int d_l = depth( p->left ) ;
      int d_r = depth( p->right ) ;
      if ( d_l > d_r )
         return d_l + 1 ;
      else
         return d_r + 1 ;
   }
}

int main() {
   struct Tree* top = ..... ;
   printf( "%d\n" , count( top ) ) ; // 木全体のデータ件数
   printf( "%d\n" , sum( top ) ) ;   // 木全体のデータ合計
   printf( "%d\n" , depth( top ) ) ; // 木全体の最大段数

   return 0 ;    
}

2分探索木にデータを追加

前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。

struct Tree* top = NULL ;

// 2分探索木にデータを追加する処理
void entry( int d ) {
   struct Tree** tail = &top ;
   while( *tail != NULL ) {
      if ( (*tail)->data == d )       // 同じデータが見つかった
         break ;
      else if ( (*tail)->data > d )
         tail = &( (*tail)->left ) ;  // 左の枝に進む
      else
         tail = &( (*tail)->right ) ; // 右の枝に進む
   }
   if ( (*tail) == NULL )
      *tail = tcons( d , NULL , NULL ) ;
}

int main() {
   char buff[ 100 ] ;
   int x ;

   while( fgets( buff , sizeof( buff ) , stdin ) != NULL )
      if ( sscanf( buff , "%d" , &x ) != 1 )
         break ;
      entry( x ) ;

   return 0 ;    
}

このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。

理解確認

  • 関数entry() の14行目の if 判定を行う理由を説明せよ。
  • 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
  • sscanf() の返り値を 1 と比較している理由を説明せよ。
  • entry() でデータを格納する処理時間のオーダを説明せよ。
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...

void entry( struct Tree* top , int d ) {
   struct Tree** tail = &top ;
   while( *tail != NULL ) {
      :
      // 上記の entry() と同じとする
}
void main() {
   // 追加対象の top は局所変数
   struct Tree* top = NULL ;
 
   char buff[ 100 ] ;
   int  x ;
   while( fgets(buff,sizeof(buff),stdin) != NULL ) {
      if ( sscanf( buff , "%d" , &x ) != 1 )
         break ;
      entry( top , x ) ;
   }
}

上記のプログラム↑は動かない。なぜ?
このヒントは、このページ末尾に示す。

演習課題

以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。

  1. 名前(name)と電話番号(phone)
  2. 名前(name)と誕生日(year,mon,day)
  3. 名前(name)とメールアドレス(mail)

プログラムは以下の機能を持つこと。

  • 1行1件でデータを入力し、2分木に追加できること。
  • 全データを昇順(or降順)で表示できること。
  • 検索条件を入力し、目的のデータを探せること。

レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。

// プログラムのおおまかな全体像の例
struct Tree {
    //
    // この部分を考えて
    //   以下の例は、名前と電話番号を想定
} ;

struct Tree* top = NULL ;
void tree_entry( char n[] , char ph[] ) {
    // n:名前,ph:電話番号 を追加
}
void tree_print( struct Tree* p ) {
    // 全データを表示
}

struct Tree* tree_search_by_name( char n[] ) {
    // n:名前でデータを探す
}

int main() {
    char name[ 20 ] , phone[ 20 ] ;
    char buff[ 1000 ] ;
    struct Tree* p ;

    // データを登録する処理(空行を入力するまで繰り返し)
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        if ( sscanf( buff , "%s%s" , name , phone ) != 2 )
            break ; // 入力で、2つの文字列が無い場合はループを抜ける
        tree_entry( name , phone ) ;
    }

    // 全データの表示
    tree_print( top ) ;

    // データをさがす
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        if ( sscanf( buff , "%s" , name ) != 1 )
            break ; // 入力で、1つの文字列が無い場合はループを抜ける
        if ( (p = tree_search_by_name( name )) == NULL )
            printf( "見つからない¥n" ) ;
        else
            printf( "%s %s¥n" , p->name , p->phone ) ;
    }
    return 0 ;
}

動かないプログラムのヒント

// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
// ちなみに、こう書くと動く

// Tree*を返すように変更
struct Tree* entry( struct Tree* top , int d ) {
   :
   // 最初の entry と同じ
   :
   return top ;
}
void main() {
   // 追加対象のポインタ
   struct Tree* top = NULL ;
   while( ... ) {
      :

      // entry() の返り値を top に代入
      top = entry( top , x ) ;
   }
}

fgets()とsscanf()による入力の解説

前述のプログラムの入力では、fgets() と sscanf() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。

// scanf() で苦手なこと -------------------------//
// scanf() のダメな点
// (1) 何も入力しなかったら...という判定が難しい。
// (2) 間違えて、abc みたいに文字を入力したら、
// scanf()では以後の入力ができない。(入力関数に詳しければ別だけどさ)
int x ;
while( scanf( "%d" , &x ) == 1 ) {
   entry( x ) ;
}

// scanf() で危険なこと -------------------------//
// 以下の入力プログラムに対して、10文字以上を入力すると危険。
// バッファオーバーフローが発生する。
char name[ 10 ] ;
scanf( "%s" , name ) ;

// 安全な入力 fgets() ---------------------------//
// fgets() は、行末文字"¥n"まで配列 buff[]に読み込む。
// ただし、sizeof(buuf) 文字より長い場合は、途中まで。
char buff[ 100 ] ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
    // buff を使う処理
}
// 文字列からデータを抜き出す sscanf() -------------//
// sscanf は、文字列の中から、データを抜き出せる。
// 入力が文字列であることを除き、scanf() と同じ。
char str[] = "123 abcde" ;
int  x ;
char y[10] ;
sscanf( str , "%d%s" , &x , y ) ;
// x=123 , y="abcde" となる。
// sscanf() の返り値は、2 (2個のフィールドを抜き出せた)

// ただし、Microsoft Visual Studio では、以下のように関数名を読み替えること。
// scanf( ... )  → scanf_s( ... )
// fscanf( ... ) → fscanf_s( ... )
// sscanf( ... ) → sscanf_s( ... )

理解確認

2分探索木

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)

// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;

int bin_search( int a[] , int key , int L , int R ) {
   // Lは、範囲の左端
   // Rは、範囲の右端+1 (注意!!)
   while( R > L ) {
      int m = (L + R) / 2 ;
      if ( a[m] == key )
         return key ;
      else if ( a[m] > key )
         R = m ;
      else
         L = m + 1 ;
   }
   return -1 ; // 見つからなかった
}

void main() {
   printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}

一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか?

2分探索木

ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。

この枝の特徴は何だろうか?この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。

特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。

このデータ構造をプログラムで書いてみよう。

struct Tree {
   struct Tree* left ;
   int          data ;
   struct Tree* right ;
} ;

// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
                    int          d ,
                    struct Tree* R ) {
   struct Tree* n = (struct Tree*)malloc(
                       sizeof( struct Tree ) ) ;
   if ( n != NULL ) { /* (A) */
      n->left = L ;
      n->data = d ;
      n->right = R ;
   }
   return n ;
}

// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   // 木構造をtcons()を使って直接生成 (B)
   top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
                       27 ,
                       tcons( NULL , 38 , NULL ) ) ,
                42 ,
                tcons( tcons( NULL , 64 , NULL ) ,
                       72 ,
                       tcons( NULL , 81 , NULL ) ) ) ;
   printf( "%d¥n" , tree_search( top , 64 ) ) ;
}

この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

理解度確認

  • 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
  • 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。

2分木に対する処理

2分探索木に対する簡単な処理を記述してみよう。

// データを探す
int search( struct Tree* p , int key ) {
   // 見つかったらその値、見つからないと-1
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
   if ( p != NULL ) {
      print( p->left ) ;
      printf( "%d¥n" , p->data ) ;
      print( p->right ) ;
   }
}
// データ件数を求める
int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1
             + count( p->left )
             + count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data
             + count( p->left )
             + count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
   while( p->right != NULL )
      p = p->right ;
   return p->data ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

双方向リスト

リスト構造の利点と欠点

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

シーケンシャルアクセス・ランダムアクセス

もう1つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、1つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。

単純リストから双方向リストへ

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか?

この場合、一つ前のデータの場所を覚えているポインタがあれば良い。

// 双方向リストの宣言
struct BD_List {
    struct BD_List* prev ; // 1つ前のデータへのポインタ
    int             data ;
    struct BD_List* next ; // 次のデータへのポインタ
} ;

このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。

// リスト生成補助関数
struct BD_List* bd_cons( struct BD_List* p ,
                         int d ,
                         struct BD_List* n ) {
    struct BD_List* ans ;
    ans = (struct BD_List*)malloc(
                         sizeof( struct BD_List ) ) ;
    if ( ans != NULL ) {
        ans->prev = p ;
        ans->data = d ;
        ans->next = n ;
    }
    return ans ;
}
void main() {
    struct BD_List* top ;
    struct BD_List* p ;

    // 順方向のポインタでリストを生成
    top = bd_cons( NULL , 1 ,
          bd_cons( NULL , 2 ,
          bd_cons( NULL , 3 , NULL ) ) ) ;
    // 逆方向のポインタを埋める
    top->next->prev = top ;
    top->next->next->prev = top->gt;next ;

    // リストを辿る処理
    for( p = top ; p->next != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    for(         ; p->prev != NULL ; p = p->prev )
        printf( "%d\n" , p->data ) ;
}

双方向リストの関数作成

以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。

先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。

// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。
void bd_insert( struct BD_List* p , int d ) {
   struct BD_List*n = bd_cons( p , d , p->next ) ;
   if ( n != NULL ) {
      p->next->prev = n ;
      p->next = n ;
   }
}

// 双方向リストの指定場所 p の後ろのデータを消す処理は?
void bd_delete( struct BD_List* p ) {
   struct BD_List* d = p->next ;
   d->next->prev = p ;
   p->next = d->next ;
   free( d ) ;
}

// この手のリスト処理のプログラムでは、命令の順序が重要となる。
// コツとしては、修正したい箇所の遠くの部分を操作する処理から
// 書いていくと間違いが少ない。

番兵と双方向循環リスト

前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?

同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?

こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。

しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。

deque(両端キュー)

この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。

理解確認

  • 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
  • 双方向リストの利点と欠点はなにか?
  • 番兵を用いる利点を説明せよ。
  • deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
  • 双方向リストが使われる処理の例としてどのようなものがあるか?

集合とリスト処理

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

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

以前に説明したリストを用いた待ち行列(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つのセルで管理する循環リストが使われることが多い。

理解確認

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