動的メモリ管理 malloc() と free()
動的メモリ領域とフリーリスト 動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。 この返却されたメモリ領域は、改めて malloc() が呼び […]
ガベージコレクタとスタック領域
ガベージコレクタ 循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか？ 最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、この […]
共有のあるデータの取扱い
これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数に […]
ハッシュ衝突対策と文字列のハッシュ関数
前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか？ ハッシュ法を簡単なイメージで説明 […]
ハッシュ法(導入)
前半は中間試験の返却と解説を行う。後半は次のテーマのハッシュ法の導入話。 ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスがで […]
2分木による構文木とデータベースとB木
2項演算と構文木 演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木 […]
演算子と言語処理系
前回追加で説明した逆ポーランド記法などの説明を再掲したうえで、構文解析といった言語処理系の話を解説する。 逆ポーランド記法 一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+( […]
AVLと意思決定木と演算子
前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。 2分探索木へのデータ追加と不均一な木の成長 先週の講義で説明していた、entry() では […]
2分探索木の処理とデータ追加処理
前回の授業で2分探索木、2分ヒープの説明を行ったが、実際にデータを追加する処理などを踏まえながらの演習の時間とする。 2分木の簡単な処理 int count( struct Tree* p ) { if ( p == N […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]