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


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

【4行目で他のプログラムへ 引数に注意!】

プログラム1の4行目でプログラム「SortNode」(16行目)へジャンプします。「SortNode」の仕様は問題文中の表3をご覧ください。引数size、parent[]、freq[]は「入力」用の引数となっていますので、実行前に具体的なデータが必要になりますが、sizeの値は4、 parent[]、freq[]は プログラム「Huffman」の時と同じ内容です。

また、表3のプログラム「SortNode」の仕様から、引数nsizeとnode[]は「出力」となっていますので、「SortNode」実行後の結果が格納される引数です。そのため、プログラム実行前にデータを格納する必要はありません。加えて、17行目で変数「i」も宣言していますので、まとめると下記のようになります。

【ようやくトレースらしくなるのは18行目以降から】

ここから18行目以降のトレースとなります。
18行目でnsizeに0が入ります。
19行目は24行目までの繰返処理の始端となっており、変数iに0が設定され、継続条件の「i < size」が「真」となりますので、処理は20行目に移ります。
20行目は条件判定文です。ここでは、「i=0」なので「parent[0]=-1」となり、条件判定文「Parent[i] < 0」は「真」です。処理は21行目に進みます。
21、22行目は順次処理、23行目は条件判定文の終端で特に何も処理しません。24行目は繰返処理の終端なので、処理は19行目に戻ります。

ここから、繰返処理(19~24行目)の2巡目。19行目では「i」に1が加算(i=1となる)された後、継続条件式「i < size」は、まだ「真」なので、処理は20行目に移ります。
i=1の状況ですが、20行目の条件判定文「Parent[i] < 0」はまた「真」なので、処理は21行目に進みます。

この要領で繰返処理(19~24行目)を実行します。繰返処理終了後、25行目に処理が移った時の各変数の状況は下記のとおりです。

<参考>繰返処理終了の流れ
基本文法ですが、念のため繰返処理終了の流れを再確認しますと、19~24行目の処理の終盤、「i=3」の状況で22・23・24行目と処理が進みます。24行目は繰返処理の終端となりますので、処理が19行目に戻ります。
19行目でiに1が加算され「i=4」になった時点で繰返しの継続条件「i < size」が偽となるので、繰返処理終了となり、処理は25行目に移ります。

【仕様のみのプログラム 入出力データを確認すれば怖くない!】

25行目はプログラム「Sort」にジャンプしますが‥。「Sort」のプログラムは「仕様」のみで、実際のプログラムは記載されていません。試験問題ではこんなケースもあります。なので、このような時は、プログラム中に「入力」されたデータが、どのように「出力」されるかを考えます。

プログラム「Sort」に関しては「プログラム1の説明」の(5)に「配列nodeを受け取り‥」「要素番号に対応する要素組が表す節の値が昇順となるように整列‥」と記載されています。

次に表4からプログラム「Sort」はfreq[]、nsize、node[]が「入力データ」、node[]のみが「出力データ」であることがわかります。ここまでの処理でnsize=4、freq[]、node[]は下記のとおりです。

プログラム「Sort」の処理終了後、配列nodeが下記の通りとなって出力結果となります。「nodeに格納されているデータ」を「freqに格納されているデータの昇順」になるように整列しています。

以上でプログラム「Sort」は終了。プログラム全体に「26行目」はありませんので、ここでプログラム「SortNode」も終了となり、処理は元々の呼出し元だった4行目の次の5行目に移ります。


コメントを残す

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