ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » リスト処理基本の回答

2020年7月
 1234
567891011
12131415161718
19202122232425
262728293031  

検索・リンク

リスト処理基本の回答

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