オブジェクト指向と演習
データ構造を扱うプログラムの書き方を説明してきたので、それらを便利に書くためのオブジェクト指向の入り口を紹介する。 データ指向のプログラム記述 名前と年齢のデータを扱うプログラムを書く時、私なら以下のようなプログラムを作 […]
動的メモリ確保(malloc()とfreelist)
C言語では、動的メモリ領域をどのように管理していくのか解説する。 局所変数とスタック 局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。 関数の中で関数が呼び出 […]
参照カウンタ法とガベージコレクタ
共有のあるデータの取扱の問題 リスト構造で集合計算おこなう場合の和集合を求める処理を考える。 struct List* join( struct List* a , struct List* b ) { struct L […]
ハッシュ法(チェイン法)
前回説明のハッシュ法(オープンアドレス法)は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。 チェイン法 チェイン法は、 […]
ハッシュ法(オープンアドレス法)
ハッシュ法 ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log […]
情報構造論・後期中間テスト結果の講評
情報構造論のテストが終わり、採点中。今回は、各ページごとに採点中。 設問1のイメージ図は、ほぼ全員が正解。簡単過ぎたか。 設問2でprintf(“＼n(%d)＼n”,i) で、未だに￥と＼が同じこ […]
B木とデータベース
2分探索木の考え方を拡張したもので、B木がある。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデー […]
演算子と2分木による式の表現
2分木の応用として、式の表現を行うけどその前に… 逆ポーランド記法 一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような […]
意思決定木と構文解析
意思決定木 意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。 ((意思決定木の例:うちの子供が発熱した時)) 38.5℃以上の発熱がある？ […]
演習part2、およびAVL木
前回、2分木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。 2分木へのデータ追加と不均一な木の成長 先週の講義で説明していた、entry() では、データ […]