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

課題テーマ(基本)

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

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

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

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

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

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

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

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

(さらに…)

2分木へのデータの追記

前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。

struct Tree {
    int data ;
    struct Tree* left ;
    struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
    struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->data  = x ;
        ans->left  = L ;
        ans->right = R ;
    }
    return ans ;
}
struct Tree* top = NULL ;
void insert( int x )
{
    struct Tree** tail = &top ; // 書換えるべき末端ポインタへのポインタ
    while( (*tail) != NULL ) {
        if ( (*tail)->data == x )
            break ; // 同じデータは重複するので、追加処理は行わない
        else if ( (*tail)->data > x )
            tail = &( (*tail)->left ) ; // 左の枝を降りていく
        else
            tail = &( (*tail)->right ) ; // 右の枝を降りていく
    }
    if ( (*tail) == NULL )
        (*tail) = tcons( x , NULL , NULL ) ;
}

単純リストの時は、2重ポインタの混ざった式の部分的に、型を意識する説明をした。今回は、”tail = &( (*tail)->left )“の赤のカッコが省略されたら、青のカッコが省略されたら、どちらが文法エラーかを「演算子の優先順位」の話を交えながら説明する。 (さらに…)

2分木(2分探索木)

struct Tree {
    int data ;
    struct Tree* left ;
    struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
    struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->data  = x ;
        ans->left  = L ;
        ans->right = R ;
    }
    return ans ;
}
void main() {
    struct Tree* top 
        = tcons( 52 ,
                 tcons( 24 ,
                        tcons( 10 , NULL , NULL ) ,
                        tcons( 35 , NULL , NULL ) ) ,
                 tcons( 73 ,
                        tcons( 60 , NULL , NULL ) ,
                        tcons( 95 , NULL , NULL ) ) ) ;
}

出来上がった木構造のイメージ

　　　top
　　　　　＼
　　　　　　52
　　　　　／　＼
　　　　／　　　＼
　　　24　　　　　73
　　／　＼　　　／　＼
　10　　　35　60　　　95

(さらに…)

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

シーケンシャルアクセス・ランダムアクセス

もう１つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、１つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも１つ前にもどるだけでも処理時間を改善してみよう。 (さらに…)