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

2017年10月
« 9月   11月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分探索木の演習

先週までで、2分探索木の説明を終えたので、今日は演習を行う。

課題テーマ(基本)

2分探索木を使ったプログラムの作成。データ構造は、以下の中から出席番号にて選ぶ。(出席番号%3)

  1. 名前と生年月日(年月日は別要素が望ましい)
  2. 名前と電話番号
  3. 学科・学年・出席番号・名前の名簿

上記のデータ構造にて、データを入力し「保存」、その後「検索」し目的のデータを表示する機能を実装せよ。

定番ではあるが、(a)プログラム説明、(b)プログラムリスト、(c)動作検証、(d)動作考察の観点で評価を行う。

課題テーマ(オプション)

上記の基本テーマは簡単であるため、オプションテーマを以下に示す。基本テーマの代わりにオプションテーマにてレポートを提出せよ。

数値をデータとする2分木を、その構造がイメージできるようにアスキーアート的に、あるいはグラフィック的に表示するプログラムを作成せよ。

(例1)            (例2)  {[29] 51 [(60) 75 (80)]}
  51
 / \          (例3)          51
29   75                      |
   / \       +------+-------+
    60      80            |              |
                         29              75
                                         |
                                     +---+---+
                                     |       |
                                    60       80

複数項目の比較

基本課題のようなプログラムで、2分木のための比較をしたいのなら、以下のような補助関数を作ると分かりやすいコードになるかな。

struct NameMonDayTree {
    char name[ 20 ] ;
    int  mon ;
    int  day ;
    struct NameMonDayTree* left ;
    struct NameMonDayTree* right ;
} ;
int cmp_NameMonDayTree( struct NameMonDayTree* p ,
                        int m , int d , char* n ) {
    // 比較結果に応じて、負,0,正の値を返す。
    //   月>日>名前の優先順位で比較
    if ( p->mon != m )
        return p->mon - m ;
    else if ( p->day != d  )
        return p->day - d ;
    else
        return strcmp( p->name , n ) ; 
}
void insert( char n[] , int m , int d ) {
    struct NameMonDayTree* tail = &top ;
    while( *tail != NULL ) {
        int cmp = cmp_NameMonDayTree( *tail , m , d , n ) ;
        if ( cmp == 0 )
            ...
        else if ( cmp > 0 )
            ...
        else
            ...
    }
    if ( ... ) {
        *tail = ...cons...
    }
}