ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 2分探索木にデータ追加と演習

2019年10月
 12345
6789101112
13141516171819
20212223242526
2728293031  

検索・リンク

2分探索木にデータ追加と演習

2分探索木にデータを追加

前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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* 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* 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() でデータを格納する処理時間のオーダを説明せよ。
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
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 ) ;
}
}
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... 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 ) ; } }
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...

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)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// プログラムのおおまかな全体像の例
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 ;
}
// プログラムのおおまかな全体像の例 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 ; }
// プログラムのおおまかな全体像の例
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 ;
}

動かないプログラムのヒント

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
// ちなみに、こう書くと動く
// 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 ) ;
}
}
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... // ちなみに、こう書くと動く // 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 ) ; } }
// 前述プログラムは、データ追加先が大域変数なのがダサい。
// 局所変数で追加処理ができるように、したいけど...
// ちなみに、こう書くと動く

// 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() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 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個のフィールドを抜き出せた)
// 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個のフィールドを抜き出せた)
// 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個のフィールドを抜き出せた)

理解確認

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー