最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。今回は、前回のリスト操作のプログラムの確認などと合わせ、リストへのデータの追加処理について説明する。

ループによるリスト操作・再帰によるリスト操作

ループによるリスト操作のプログラム例を以下に示す。

// リストの全要素を出力
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 sum( struct List* p ) {
   int s = 0 ;
   for( ; p != NULL ; p = p->next )
      s += p->data ;
   return s ;
}
// リストの最大値を返す
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 ( p->data > m )
            m = p->data ;
      return m ;
   }
}
// リストの中から指定したkeyが含まれるか探す
int find( struct List* p , int key ) {
   // 要素を見つけたら 1 、見つからなかったら 0 を返す
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return 1 ;
   return 0 ;
}

同じプログラムを再帰呼び出しで書いた場合。

// リストの全要素を再帰処理で出力
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 ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data + sum( p->next ) ;
}
// リストの最大値を再帰処理で求める
int max( struct List* p ) {
   if ( p == NULL ) {
      return 0 ;
   } else {
      int tm = p->data ;
      int rm = max( p->next ) ;
      return tm > rm ? tm : rm ;          // if ( tm > rm )
   }                                      //    return tm ;
}                                         // else
                                          //    return rm ;
// リストの中から指定した値 key を再帰処理で探す
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 ) ;
}

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

リスト構造を使うと、必要に応じてメモリを確保しながらデータをつなげることができるので、配列のように最初に最大データ件数を想定した入れ物を最初に作って保存するような処理をしなくて済む。

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 ;  // リストの廃棄処理は省略)
}

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

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。しかし、配列には苦手な処理がある。

例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。処理に要する時間としては となる。

// この関数は見つかったら、見つかった場所、見つからない場合は -1 を返す。
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 ; // 見つからない
}

int a[] = { 12 , 34 , 41 , 53 , 62 , 79 , 80 } ;
int main() {
   int ans = find( a , 0 , 7 , 62 ) ; // 配列 a[] から 62 を探す
   printf( "%d¥n" , ans ) ;           // 4が表示される
   return 0 ;
}

しかし、この配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。

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 ) {
      // 要素を１つ後ろにずらす処理(A)
      for( int j = *psize ; j > i ; j-- ) //  O(N)の処理
         array[ j ] = array[ j - 1 ] ;
      array[ i ] = key ; 
   } else {
      array[ *psize ] = key ;
   }
   (*psize)++ ;
}
   /// よくある間違い ///
   /// 上記処理の(A)の部分を以下のように記載した ///
   /// 問題点はなにか答えよ ///
   //   for( int j = i ; j < size ; j++ )
   //      array[ j + 1 ] = array[ j ] ;
   //   array[ i ] = key ;

int main() {
   int a[ 100 ] ;
   int size = 0 ;
   int x ;
   // 入力された値を登録していく繰り返し処理
   while( scanf( "%d" , &x ) == 1 ) {
      // x を追加する。
      entry( a , &size , x ) ;
   }
   return 0 ;
}

これで判るように、昇順に並んだ配列にデータを追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。

この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。

このことから、昇順に並べられた配列は、データの追加処理の発生頻度が少ない場合は2分探索法で効率が良いが、データの追加や削除が頻繁に発生する時はあまり効率が良くない。

順序が重要なデータ列で途中へのデータ挿入削除を高速化

例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
以下の説明のような方法であれば、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、スムーズに回覧板を回すことができる。

  101   102   103   104   105   106   アパートの番号
[ 105 | 106 |  -1 | 102 | 104 | 103 ] 回覧板を回す次の人の部屋番号

101号室の次は、105号室、
105号室の次は、104号室、
  :
106号室の次は、103号室、
103号室の次は、おしまい(-1)

このように「次のデータの場所」という概念を使うと、データの順序を持って扱うことができる。これをプログラムにしてみよう。

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

int main() {
   for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
      printf( "%d\n" , array[ idx ].data ) ; 
   }
   // 11,23,45,67,89,終

   array[5].data = 34 ;
   array[5].next =  4 ; // /*4*/ {45,1}
   array[2].next =  5 ;
   // O(1)で1件追加

   for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
      printf( "%d\n" , array[ idx ].data ) ;
   }
   // 11,23,[[34]],45,67,89,終
   return 0 ;
}

この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。(O(N)の処理が発生しない)

しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。そこで、必要に応じてメモリを確保するテクニックを導入する。

ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、データ保存場所としてのポインタを多用するので、ポインタの処理に慣れない人のために説明。

値渡しとポインタ渡し

大きなプログラムを作成する場合、変数名の使い方には注意が必要となる。大域変数は、どこでも利用できるが、間違った使い方をすると値が予想外の変化があったりするため危険である。一方で、局所変数を使うと、関数呼び出しでデータの受け渡しに注意が必要となる。

値渡し(call by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。

言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。実引数の値は、仮引数の変数に copy し代入される。

でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
}

ポインタ渡し(call by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
void main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
}               // さらに125と増える。

C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は：結果を入れてもらう場所を伝え、関数側は：指定されたアドレスに結果を書き込む。

変数の寿命とスコープ

変数の管理では、変数の寿命とスコープの理解が重要。

静的変数：変数は、プログラムの起動時に初期化、プログラムの終了時に廃棄。
動的変数：変数は、関数に入るときに初期化、関数を抜けるときに廃棄。
もしくは、ブロックに入るときに初期化、ブロックを抜けるときに廃棄。

大域変数：大域変数は、プログラム全体で参照できる。
局所変数：関数の中 or そのブロックの中でのみ参照できる。

ブロックの中で変数が宣言されると、そのブロックの外の変数とは別の入れ物となる。そのブロックの中では、新たに宣言された変数が使われる。

int i = 111 ;    // 静的大域変数

void foo() {
   int i = 222 ; // 動的局所変数
   i++ ;
   printf( "%d\n" , i ) ;
}
void bar() {
   static int i = 333 ; // 静的局所変数(プログラム起動時に初期化)
   i++ ;
   printf( "%d\n" , i ) ;
}
void hoge( int x ) {    // x: 動的局所変数(値渡し)
   x++ ;
   printf( "%d\n" , x ) ;
}
void fuga( int* p ) {   // p: 動的局所変数(ポインタ渡し)
   (*p)++ ;
   printf( "%d\n" , (*p) ) ;
}
int main() {
   int i = 444 , j = 555 ;
   foo() ;      // 223 (副作用ナシ)
   bar() ;      // 334
   hoge( i ) ;  // 445 (副作用ナシ)
   fuga( &j ) ; // 556
   printf( "%d\n" , i ) ;
   foo() ;      // 223 (副作用ナシ)
   bar() ;      // 335
   hoge( i ) ;  // 445 (副作用ナシ)
   fuga( &j ) ; // 557

   printf( "%d\n" , i ) ;                     // 444
   for( int i = 0 ; i < 2 ; i++ ) { // (a)    // A:0
      printf( "A:%d\n" , i ) ;                // B:0
      for( int i = 0 ; i < 2 ; i++ ) { // (b) // B:1
         printf( "B:%d\n" , i ) ;             // A:1
      }                                       // B:0
   }                                          // B:1

   printf( "%d\n" , i ) ;  // 333 ← 要注意C言語のバージョンによっては
                           //       2 になる場合あり。(a)の変数iの値
   return 0 ;
}

JavaScriptのvarとletのスコープ

C言語でのスコープと寿命と、JavaScriptのvar宣言では考え方が違うので要注意。
C言語では、変数はその宣言された場所がブロックの中であれば、その中でのみ使用できる局所変数となる。JavaScript の let 宣言も基本は同じ考え方。ただし、JavaScript の var 宣言は、その変数が使われる関数ブロックの中(もしくはグローバルスコープ)に関連付けられる。この変数の宣言部分がもっとも近い関数の先頭に移動しているように見える動作のことを変数の巻き上げ（hoisting）と呼ばれる。

C言語の局所変数のスコープ。

JavaScript の let 宣言は、C言語のスコープと同じ考え方。

JavaScript の var 宣言は、関数スコープであり、ブロック{} 内で新しく宣言があっても、関数スコープまで巻き上げられる。

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '¥0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s¥n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '¥0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '¥0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '¥0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '¥0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

構造体とポインタ

構造体を関数に渡して処理を行う例を示す。

struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person table[3] = {
   { "t-saitoh" , 55 } ,
   { "tomoko" ,   44 } ,
   { "mitsuki" ,  19 } ,
} ;

void print_Person( struct Person* p ) {
   printf( "%s %d\n" ,
           (*p).name , // * と . では . の方が優先順位が高い
                       // p->name と簡単に書ける。
           p->age ) ;  // (*p).age の簡単な書き方
}

void main() {
   for( int i = 0 ; i < 3 ; i++ ) {
      print_Person( &(table[i]) ) ;
   // print_Person( table + i ) ; でも良い
   }
}

構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。

練習問題(2018年度中間試験問題より)

printf() に慣れていない人もいるので…ヒント：%d 引数を10進数で表示、%s 引数の文字列として表示(文字列の先頭アドレスから’\0’までの文字を表示)、%c 引数を文字(char型)として表示。