実験B 3週目

レポート提出。
出席課題はHuffman符号化の木を葉から生成するアルゴリズム。

記号数をN, 2分木のノードになる構造体をData[0..N−1]とする。この構造体には、"0"と"1"に対応する子へのリンクポインタと出現頻度を保持している。木を作るためのポインタ配列をp[0..N−1]とする。

1. (初期化)対象となるノード数nをNとする。
   全てのデータに対してポインタp[]を張る。つまりp[i]=&Data[i](0 ≦ i < n−1)
2. p[0..n−1]を出現頻度順(降順)にソートする
3. 親になる新しいノードnodeを1つ作る
4. 小さいうちの2つ、つまりp[n−2]とp[n−1]へ向かってnodeからポインタを張る。
   nodeにp[n−2]とp[n−1]の和をnodeの出現頻度として設定する
5. p[n−2]をnodeへのポインタに変える
6. nを1減らす
7. 対象となるノード数nが2以上ならば 2へ
   そうでなければ終了。p[0]が木のルートノードである

あと、雄飛と吉田君のお手伝い。