前回の授業で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)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(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( ... )
理解確認
- 標準入力からの1行入力関数 gets() 関数が危険な理由を説明せよ。