メモリ管理・スタック領域とヒープ領域
ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のような […]
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、2分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできない […]
データベースとB木
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを […]
木構造の探索・深さ優先探索・幅優先探索
深さ優先探索(前順) 以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。 しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を […]
2分木による構文木
コンパイラの処理の流れ 構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。 Cコンパイラのソース ↓ プリプロセッサ (#defin […]
2分木の応用(意思決定木と演算子)
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。 意思決定木 意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹 […]
2分探索木への追加とAVLと2分ヒープ
2分探索木にデータを追加 前回の2分探索木では、基本的な説明ということで、木の生成では直接木構造を生成していた。しかし、本来であれば、扱うデータに応じて木を生成することが求められる。 Javaの場合 以下の Javaのプ […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]
双方向リストとdeque
deque(両端キュー) 双方向循環リストを使うと、(1)先頭にデータを挿入(addFirst/unshift)、(2)先頭のデータを取り出す(removeFirst/shift)、(3)末尾にデータを追加(addLas […]
ランダムアクセス・シーケンシャルアクセスから双方向リスト
ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。 リスト構造の利点と欠点 リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リ […]