ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 (ページ 11)

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

2025年5月
日 月 火 水 木 金 土
 123
45678910
11121314151617
18192021222324
25262728293031

リンク集

検索・リンク

Google Office 365

意思決定木と構文解析

2021年11月1日

前回までの授業で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仮想化。

に分けられる。

C言語で機械語が生成されるまで

C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。

foo.c C言語のソース
↓     プリプロセッサ処理
foo.c(#行の無いC言語のソース)
↓     コンパイラ
foo.obj(オブジェクトファイル/中間コード)
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)
foo.exe

コンパイラの処理

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

  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”と区切る処理が、字句解析である。

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

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

理解度確認

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

AVLと2分ヒープ

2021年10月25日

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

これらの問題の解決法の１つとして、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分探索木の処理とデータ追加処理

2021年10月18日

前回の授業では、当初予定に加え、この後に示すデータの追加処理の説明を行った。その代わり、簡単な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( ... )

理解確認

深さ優先探索と幅優先探索

2021年10月14日

2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。

幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、データ件数0になる際の処理を手抜きで説明しているため、C++ の deque で記述。

深さ優先探索(deep-first search)は、スタックを使って実装可能なことを示すために、あえて再帰呼び出しを使わずに記述してみた。

#include <deque>
#include <algorithm>

int main() {
   std::deque<struct Tree*> deq ;
   struct Tree* p ;
   // 幅優先探索(FIFOを使って)
   deq.push_front( top ) ;
   while( !deq.empty() ) {
      // 待ち行列の最初を取り出す
      p = deq.front() ;
      deq.pop_front() ;
      if ( p != NULL ) {
         printf( "%d\n" , p->data ) ;
         // 待ち行列に枝葉を追加
         deq.push_back( p->left ) ;
         deq.push_back( p->right ) ;
      }
   }
   // 深さ優先探索(再帰呼び出しを使わずstack/LIFOで実装)
   p = top ;
   for( ;; ) {
      // 分岐をpushしながら左下にまっしぐら
      while( p != NULL ) {
         deq.push_front( p ) ;
         p = p->left ;
      }
      if ( deq.empty() )
         break ;
      // pushしておいた分岐点をpopして繰り返し
      p = deq.front() ;
      deq.pop_front() ;
      printf( "%d\n" , p->data ) ;
      p = p->right ;
   }
   return 0 ;
}

2分探索木

2021年10月11日

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば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 ;
}

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

(2021/10/12)
print() の再帰の処理の流れを説明するなかで、「じゃあデータを降順で表示したかったらどうすればいい？」「じゃあ、データが根っこに近い方から表示したかったらどうすればいい？」みたいな話を、高専プロコンの競技部門の組み合わせ問題に考えてほしくなって、つぶやいちゃったもんだから、話がそれて「再帰で記載するのは、枝の先の処理が終わってから、残りの枝の処理を行うので、深さ優先探索法になる。」、「根っこに近い方から表示したかったら幅優先探索法」になるよ…という話をする。ついでの雑談で、「将棋とかチェスのプログラムだと、次の手を打った後の評価で先読みするけど、あれどうやってる？」という話をして、その中でαβ法というのがあってね…静的評価で良い手の候補を選び、その手は動的評価で再帰処理を行い、本当に良い手を選ぶ…という説明を行った。来週は、２分木の sum() とか count() を考えてもらうことから始めよう。

双方向リスト

2021年10月4日

最初に、前期期末試験で「メモリの番地の理解が怪しい」人が多かったので、その確認のための Forms による小テストを行う。

実施してみらた、各問題とも50%程度の正解率。ひとまず解説をしたうえで、同じような問題を今後も何度かやってみたいと思う。

リスト構造の利点と欠点

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

例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。

配列の場合 リスト構造の場合

(ただしヒープ管理用メモリ使用量は無視)

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

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

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

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

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

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、１つ後ろのデータ(N番目からN+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->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 の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか？
  • 双方向リストが使われる処理の例としてどのようなものがあるか？

変態コード

2021年8月22日

Twitterで以下のようなコードが紹介されていた。
ポイントは、a[i] と書くべき所が、*(a + i) と等価であり、*(i + a) = i[a] と書かれている点。

{CAPTION}

でも、昔どこかで見たという点では、以下のコードの方がさらに変態っぽいでしょ。

{CAPTION}

集合とリスト処理

2021年7月26日

リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。集合処理の記述には、2進数を使った方式やリストを用いた方法が一般的である。以下にその処理について示す。

bit演算子

2進数を用いた集合処理を説明する前に、2進数を使った計算に必要なbit演算子について復習してみる。

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		 x << y は x * 2y と同じ
>> bit 右シフト 12 >> 2
1100)2 >> 2 = 11)2		 x >> y は x / 2y と同じ 
#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言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

2進数を用いた集合計算

扱うデータ件数が少ない場合には、「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 AND)
   bit_print( ba & bb ) ; // ba ∩ bb = {2}                 
   bit_print( bb & bc ) ; // bb ∩ bc = {4,6}
   // 集合和(bit OR)
   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 ) ;
   }
}

リスト処理による積集合

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

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

// 先週までに説明してきたリスト構造と補助関数
struct List {
   int     data ;
   struct List* next ;
} ;
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" ) ;
}
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) の処理を記述せよ。

スタックと待ち行列

2021年7月19日

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

計算処理中に一時的なデータの保存として、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)

２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー: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つのセルで管理する循環リストが使われることが多い。

理解確認

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

リストへの追加処理

2021年7月14日

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

最も単純なリスト先頭への挿入

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

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

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

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

授業では、C言語のプログラムを示しているが、C++を使うと LIST 処理もシンプルに記述できるようになっている。参考資料として、C++で同様の処理を示す。テンプレートを使ったコンテナクラスを使うと、struct List {…} といった記述は不要で、std::forward_list<int> という型を使うだけで書けてしまう。

// 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 ;
}

要素を末尾に追加して追加順序で保存

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

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 ) {
   // p    は要素を入れる前のポインタ
   // 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 ;  // リストの廃棄処理は省略)
}

投稿ナビゲーション

← 過去の投稿 新しい投稿 →

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー