情報構造論2025-講義録
情報構造論ガイダンス2025 繰り返し処理と処理時間の見積もり 再帰呼び出しと処理時間の見積もり ハノイの塔と再帰を使った並び替え クイックソートと選択ソート 処理速度を計測 Javaのオブジェクト指向の基礎 配列に要素 […]
関数ポインタとラムダ式
関数ポインタとコールバック関数 JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワー […]
レポート課題(後期期末) ハッシュ法
課題内容 以下の内容の中から１つを選びハッシュ法でデータを登録・検索するプログラムを作成せよ。 メールアドレスと電話番号のデータベース メールアドレスと誕生日のデータベース ハッシュ関数などを考え、データをメールや電話番 […]
ヒープメモリの管理方法
動的メモリ領域とフリーリスト 動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。 この返却されたメモリ領域は、改めて malloc() (Ja […]
ヒープ領域と参照カウンタ・ガベージコレクタ
ヒープ領域 リスト処理のようなプログラムでは、データを覚える領域は、関数が終わった後も使われる領域なので、局所変数のように「関数が終わったらそのデータの場所が不要になる」といったLast In First Out のよう […]
メモリ管理・スタック領域
ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のような […]
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできない […]
データベースとB木
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを […]
木構造の探索・深さ優先探索・幅優先探索
深さ優先探索(前順) 以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。 しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を […]
2分木による構文木
逆ポーランド記法とスタックマシン 逆ポーランド記法(RPN)は、(1+2)*3 であれば “1 2 + 3 *” のように表すことができ、この書き方は「1と2を加える、(それに)3を掛ける」という […]