B木の構造とデータベース
2分探索木の考え方を拡張したもので、B木がある。 B木の構造 B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ […]
式の構文木と評価
2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。また、これらを用いてコンパイラを作るための知識を解説する。 2項演算と構文木 演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で […]
意志決定木と式を表す木
意志決定木 2分木の応用で最も単純な物として、意志決定木がある。 yes/no の答えを回答すると、最終的に「あなたの性格は✕✕です」と表示するようなヤツ。 struct Tree { char* q_a ; struc […]
2分探索木の演習
先週までで、2分探索木の説明を終えたので、今日は演習を行う。 課題テーマ(基本) 2分探索木を使ったプログラムの作成。データ構造は、以下の中から出席番号にて選ぶ。(出席番号%3) 名前と生年月日(年月日は別要素が望ましい […]
2分探索木への追加
2分木へのデータの追記 前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。 struct Tree { int data ; struct Tree* left ; struct […]
2分探索木
2分木(2分探索木) struct Tree { int data ; struct Tree* left ; struct Tree* right ; } ; struct Tree* tcons( int x, st […]
リストの利点/欠点と双方向リスト
リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣 […]
構造体と実体について
構造体と実体の違いや、Javaに慣れている学生さんに あらためて、データ構造のイメージを持って欲しいので、 以下のコードを示す。 struct Complex { double re ; double im ; } ; […]
2分木の生成
先週に2分木に対する再帰などを交えたプログラムの説明をしたので、 今週は木の生成について、AVL木などを交えて説明。 後半は、情報処理センターで演習。 #include <stdio.h> #include […]
再帰関数の処理と再帰方程式
前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。 特殊な処理時間の見積もり 前回授業の最後に検討しておくように […]