実験B 3週目
レポート提出。
出席課題はHuffman符号化の木を葉から生成するアルゴリズム。
記号数をN, 2分木のノードになる構造体をData[0..N−1]とする。この構造体には、"0"と"1"に対応する子へのリンクポインタと出現頻度を保持している。木を作るためのポインタ配列をp[0..N−1]とする。
- (初期化)対象となるノード数nをNとする。
全てのデータに対してポインタp[]を張る。つまりp[i]=&Data[i](0 ≦ i < n−1) - p[0..n−1]を出現頻度順(降順)にソートする
- 親になる新しいノードnodeを1つ作る
- 小さいうちの2つ、つまりp[n−2]とp[n−1]へ向かってnodeからポインタを張る。
nodeにp[n−2]とp[n−1]の和をnodeの出現頻度として設定する - p[n−2]をnodeへのポインタに変える
- nを1減らす
- 対象となるノード数nが2以上ならば 2へ
そうでなければ終了。p[0]が木のルートノードである
あと、雄飛と吉田君のお手伝い。