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

計算処理中に一時的なデータの保存として、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つのセルで管理する循環リストが使われることが多い。

理解確認

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

最初のリスト生成の説明では、補助関数 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 ) の番号の課題に取り組むこと。

0. 緯度(latitude)経度(longitude)とその場所の都市名(city)
1. 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
2. 複素数(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 ;  // リストの廃棄処理は省略)
}