平成31年春期午後問8 ハフマン符号化のトレース3


こちらは平成31年春期午後問8ハフマン符号化のトレース2の続きです。

【プログラム「Huffman」はほとんど加算、代入だけ】

プログラム「Huffman」5行目実行直前の各変数の状況は次の通りです。

5~15行目は繰返処理になりますが、nsizeの値は「4」ですので、5行目の継続条件式「nsize ≧ 2」は真となり、処理は6行目に移ります。6~13行目までは加算、代入が続きます。13行目実行後の状況は次の通りです。

【配列変数でハフマン木が構築されていることが確認できる】

上図を問題文中の図3と比べてみてください。配列parent、left、ridht、freqが、問題文中の図3に近づいていることがわかります。 また、図3はプログラム1の最終的な実行結果(完成したハフマン木が表現されている状態)であることも確認できます。

このまま14行目以降を実行し、5~15行目の繰返処理を2巡、3巡と繰返すと、最終的に図3が完成しますので、ぜひ試してみてください!


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です