[Powered by Google Translate] [チュートリアル - 問題セット6] [Zamylaチャン - ハーバード大学] [これはCS50です。 - CS50.TV] みなさん、こんにちは、そしてチュートリアル6へようこそ：Huff'nパフを。 Huff'nパフでは我々がやっていることは、ハフマン圧縮ファイルを扱うことになるだろう その後、バックアップしてそれを吹かしので、それを解凍する ので、我々は、ユーザーが問い合わせを送信することを、0と1から翻訳できること と元のテキストに戻すように変換。 PSET 6では、ツールのいくつかを見ることになるので、かなりクールになるだろう あなたは、pset 4とPSET 5と1はかなりきちんとしたコンセプトにそれらを組み合わせるの種​​類で使用されている あなたがそれについて考えるようになったとき。 また、間違いなく、psetの4と5は、我々が提供しなければならなかった最も困難なのpsetであった。 だから今から、我々は、C言語では、この他に1 psetを持っている して、その後に我々は、Webプログラミングににしている。 だからCS50の中で最も過酷なこぶを乗り越えるために自分自身を祝福します。 Huff'nパフのために動いて、このpsetの私たちのツールボックスには、ハフマン木になるだろうしている そう理解するだけでなく、どのようにバイナリツリーの仕事だけでなく、具体的にハフマン木、 どのように彼らが構築している。 そして、我々は、このpset内分布のコードの多くを持っているつもりです そして我々はいくつかのコードを実際に見に来てよ 我々は、まだ完全には理解できないかもしれません そしてそうそれらがcファイルが、その後、それに付随する。hファイルになります 私たちは、我々はそれらの機能がどのように動作するかを知っているので、必要とする十分な理解を与える または少なくとも何彼らが行うことになっている - それらの入力と出力 - 我々はブラックボックスで何が起こっているかわからない場合でも またはブラックボックス内で何が起こっている理解していない。 そして最後に、いつものように、我々は、新しいデータ構造を扱っている そのノードの特定の種類は、特定のものを指す ので、ここでは設計プロセスのためだけでなく、紙とペンを持って そして、あなたのpsetがどのように働くべきか把握しようとしているとき だけでなく、デバッグ中に。 あなたは値が何であるかをテイクダウンしながら、あなたのペンと紙と並んでGDBを持つことができます どこにあなたの矢印が指している、とそのようなことされています。 最初のハフマン木を見てみましょう。 ハフマン木は各ノードが唯一の2人の子供を持っていることを意味し、バイナリツリーです。 ハフマン木に特徴は、最も頻度の高い値 最少ビットで表されます。 我々は、モールス信号の講義の例、連結の種類いくつかの文字を見ました。 あなたは、例えば、AまたはEを翻訳しようとしている場合、 あなたは、その頻繁に翻訳しているので、代わりにビットのフルセットを使用する必要が その通常のデータ型のために割り当てられた、あなたは、より少ないにそれを圧縮する その後あまり頻繁に表現されるそれらの手紙は長いビットで表現さ あなたはそれらの文字が表示されていることを周波数成分を量るときはそれを買う余裕ができるからです。 我々は、ハフマン木にここに同じアイデアを持っている ここで我々は、チェーン、特定の文字を取得するパスの種類を作っている。 そして、ほとんどの周波数を持つ文字 少ないビットで表現しようとしている。 あなたがハフマン木を構築する方法 テキストで表示されたすべての文字を配置することです とその頻度を計算し、どのくらいの頻度でそれらが表示されます。 これは、いずれかのこれらの文字が表示された回数をカウントすることができる または多分各1が表示されますどのように多くのすべての文字のうちの割合。 それで、何をやっていることは、一度そのマップされたうちのすべてを持っていることです その後、あなたは2低い周波数を探して、その後に兄弟としてそれらを結合 どこで、親ノードは、その2人の子供との和である周波数を持っています。 そして、慣例によりあなたは、その左ノード言う あなたは、0枝に従うことによってそれをフォロー その後右端のノードが1ブランチです。 我々はモールス信号で見たように、一つの落とし穴は、あなただけのビープ音とビープ音があったらということでした それがあいまいでした。 これは、いずれかの1文字であるか、2文字のシーケンスである可能性があります。 それで何ハフマン木が行うことは、文字の性質からです または私達の最終的な実際の文字のブランチの最後のノードである - 我々は葉としてそれらを参照してください - のおかげで、あいまいさがあるはずがありません あなたは一連のビットでエンコードしようとしている手紙の面で なぜなら1文字を表すビットに沿ってどこにも あなたは別の全体の文字に遭遇するでしょうし、そこに混乱がないでしょう。 しかし、我々はあなたたちが実際にそれを見ることができることの例に行くよ 代わりに我々は、ちょうどそれが本当だということを伝える。 ハフマンツリーの簡単な例を見てみましょう。 私は12文字の長さでここに文字列を持っている。 私は6位、そして2 CSとして、4を持っています。 私の最初のステップは、カウントすることであろう。 何回表示されますか？これは、文字列に4回表示されます。 Bは6回表示され、Cが2回表示されます。 当然のことながら、私は私が最も頻繁にBを使用していると言うつもりです、 ので、私はビット数が最も少ない、0と1の数が最も少ないBを表現したい。 そして私はまた、Cも同様に0と1のほとんどの量を必要とすることを期待したいと思います。 最初に私がここで何をしたか私は、周波数の面で昇順に配置されます。 我々は、Cと見、それらは私たちの2最低の周波数である。 我々は、親ノードを作成し、その親ノードは、それに関連付けられた手紙を持っていません それは和の周波数を、持っていません。 和が6である2 + 4となります。 その後、我々は左の枝に従ってください。 我々は6ノードであった場合、我々は、Cに到達するために0に従うだろう Aに取得した後、1 だから今我々は2つ​​のノードを持っています。 我々は、値6を持っているし、我々はまた、値6を持つ別のノードを持っています。 それで、それらの2が最低の2も残っているわずか2だけではなく、アール 従って私達は合計が12であることと、別の親がそれらを結合します。 そこでここでは、私たちのハフマンツリーを持っている Bに取得する場合には、それは少しだけ1になります それから私達は01を持っているし、00を有するCになるために。 そこでここでは、基本的に我々は1または2ビットのいずれかで、これらの文字を表現していることがわかり ここで、Bは、予測したように、少なくともを持っています。 その後、我々は、Cはほとんど持っていると予想していたが、それはそのような小さなハフマンツリーなので その後もどこか途中でするのではなく、2ビットで表される。 ちょうどハフマンツリーの別の単純な例を越えるためには、 あなたは文字列を持っていると言う "こんにちは。" あなたは何をすることで、Hはこれで何回表示されるんだと思います第一ですか？ Hは一回とし、eが表示されたら、それから私達は2回表示されるlを持っている そしてoは一度現れる。 それで、我々は少なくともビット数で表すことがどの文字期待？ [学生]リットル。 >>のl。 Yeah。 lは右です。 我々は、lがビットのうちの数で表されることを期待する lは "こんにちは"という文字列の中で最も使用されているため、 私は今やろうとしているもの、これらのノードを引き出しています。 私はHである、1を持っているし、oである別の電子が1であり、した後、1、 - リットルであるし、2 - 右今私は順序でそれらを入れている。 その後、私は、ハフマン木を構築する方法は、少なくとも周波数で2つのノードを見つけることであると言う と親ノードを作成することによって、それらの兄弟作る。 ここでは、最も低い周波数を持つ3つのノードを持っています。彼らはすべての1だ。 そこでここでは、我々が最初にリンクしようとしているのかを選択する。 Let 'sは、私はHとeを選ぶと言う。 1の合計+ 1は2ですが、このノードは、それに関連付けられた手紙を持っていません。 それだけで値を保持します。 今、私たちは、次の2最も低い周波数を見てみましょう。 それは2と1です。それはどちらかそれらの2のかもしれないが、私はこのいずれかを選択するつもりです。 和は3です。 そして最後に、私は唯一の5になるようにしてから、左の2を持っています。 その後、ここで、予想通り、私はそのための符号を記入した場合、 1S常に右枝と0は左1アールアール。 その後、我々は2でちょうど1ビットし、oで表さリットルを持っている その後2によるe、その後Hは3ビットに落ちる。 だからあなたは、 "Hello"このメッセージを送信することができる代わりに、実際に文字を使用して ちょうど0と1によって。 しかし、いくつかのケースで我々は周波数との関係を持っていたことを覚えています。 我々は、いずれか多分最初のHとOに参加している可能性があります。 またはその後、我々は2で表さリットルを持っていたときに 同様に（2）で表される1に参加しました、我々は、いずれかリンクされている可能性があります。 それで、あなたは、0と1を送るとき、それは実際に保証するものではありません 受信者は、完全に右バットを離れてあなたのメッセージを読み取ることができることを 彼らはあなたが作られた意思決定を知らないかもしれないので。 だから我々はハフマン圧縮を扱っているときに、 何とか我々は我々が決めたどのように我々のメッセージの受信者に指示する必要があります - 彼らは余分な情報のいくつかの種類を知っておく必要があります 圧縮されたメッセージに加えて。 彼らは、木が実際にどのように見えるかを理解する必要があります 私たちは実際にそれらの決定をどのように作った。 ここでは、単に実際のカウントに基づいた例をやっていた、 時にはあなたもハフマンツリーを持つことができます 文字が表示される頻度に基づいて、それはまったく同じプロセスだ。 ここで私は、パーセンテージまたは分数の面でそれを表現しています ので、ここでは全く同じもの。 私は、それらを合計して、最低2週間、それらを合計し、2最低を見つける 私は完全なツリーを持つまで。 我々はそれを我々が扱っている割合はどちらの方法でも、何ができるにもかかわらず、 我々は物事を分割し、小数または浮動小数点数ではなく扱っていることを意味し 私たちは頭のデータ構造を考えている場合。 私たちは、山車について何を知っていますか？ 我々が山車を扱っている一般的な問題は何ですか？ [学生]不正確な算術。 >>うん。不正確。 このpsetの、浮動小数点の不正確さのため、我々は確認してくださいよう 我々は任意の値が失われることはありませんし、我々は、実際に点数を扱うことになるだろう。 あなたはここで構造体に戻って見れば、ハフマンノードを考えていたのであれば、 あなたは緑色のものを見ればそれは、それに関連付けられた周波数を持ってい 同様にそれはその左側にノードだけでなく、その右にあるノードを指しています。 続いて赤のものがあり、またそれらに関連付けられている文字を持っています。 私たちは、両親や、最終的なノードに別々のものを作るつもりはない その我々は、葉と呼ぶのではなく、それらは単にNULL値を持つことになります。 我々が文字、そのノードが表すシンボルを持っていますが、ノードごとに その後、周波数だけでなく、その左の子だけでなく、その右の子へのポインタ。 一番下にある葉も、ノードポインタを持っているでしょう その左とその右に、それらの値は、実際のノードを指していませんので、 その価値は何でしょうか？ >> [学生]はNULL。 >>の場合はNULL。その通りです。 ここでは、浮動小数点数で周波数を表すかもしれない方法の例を、だ しかし、我々は、整数とそれに対処することになるだろう ので、私がしたすべては、そこにデータ型を変更することです。 のは、複雑な例をもう少し上に行ってみよう。 しかし、今、我々は単純なものをやったことは、それだけで同じプロセスだ。 あなたは2点の最も低い周波数を見つけ、周波数を合計 そしてそれは、あなたの親ノードの新しい周波数だ 次にその0枝と1枝と右とその左を指しています。 我々は文字列 "これはCS50ですが、"持っているならば、我々は、Tの記載されて何回カウント hが述べたように、I、S、C、5、0。 その後、私はここで何をしたかは、私はちょうど植え赤のノードを使用することです 私はツリーの一番下に、最終的にこれらの文字を持っているつもりだと語った。 それらは、葉の全てになるだろうしている。 それから私が何をしたか私は、昇順に周波数別にソートされている そして、これは実際のpsetコードはそれをしないという方法です。 それは周波数によってソートした後、アルファベット順です。 だから、周波数のアルファベット順に最初にして数字を持っています。 それから私は何であろうと、私は最低の2を見つけるだろうということです。つまり、0〜5です。 私はそれらを合計するであろう、そしてそれは2です。それから私は、次の2最低のを見つけて、続けているでしょう。 それらは2つの1ですし、それらは同様に2になる。 さて、私の次のステップは、最小の番号を参加されようとしていることを知っている これは、1 Tであり、その後、周波数として2を持つノードのいずれかを選択します。 そこでここでは、3つのオプションがあります。 私はスライドのために何をしようとしているものだけで視覚的にあなたのためにそれらを再配置され そのように私はそれを作っているかを見ることができます。 コー​​ドとしているディストリビューション·コードが何をするつもりなのかは、Tいずれかに参加されるであろう 0と5ノードを持つ。 それでは、次に3〜和、そして、我々はプロセスを続行すること。 2と2は、ここでその後、4〜それらの合計が最も低い。 誰もがこれまでに以下の？オーケー。 その後、その後、我々は、3以上追加する必要がある3を持っている あなたはそれがあまりにも厄介にならないように視覚的に確認できるようので、もう一度私はちょうどそれを切り替えています。 その後、我々は6を持って、私たちの最後のステップは、今我々は2つ​​のノードのみを持っているということです 我々は10です私たちのツリーのルートを作るためにそれらを合計します。 各ノードが表されるためと10番は、理にかなっている それらの値は、その周波数番号は、それらが文字列で登場何回あった その後我々は文字列内の5文字を​​持って、理にかなっているように。 我々は我々が実際にそれをエンコードする方法を見上げる場合は、 最も頻繁に現れる予想通り、iとs、 ビット数が最も少ない数で表されます。 ここで注意してください。 ハフマン木でケースは、実際に問題になります。 大文字のSは小文字のsとは異なります。 我々が持っていた場合は、小文字のsは二回しか思わその後、大文字で "これはCS50です" その値として2を持つノードになるでしょうし、大文字のSは一度だけだろう。 あなたが実際にここに余分な葉を持っているので、それでは、あなたのツリーは構造を変更することになります。 しかし、合計はまだ10だろう。 つまり、我々が実際にチェックサムを呼び出すことになるだろう何 カウントのすべての追加。 今、私たちは、ハフマン木を紹介してきたことを、我々はHuff'nパフ、psetに飛び込むことができます。 ここでは、質問のセクションで開始しようとしている、 そしてこれはあなたがバイナリツリー方法と、その周りに操作方法に慣れて取得するつもりされています。 描画のノードのノードのために、独自のtypedef構造体を作成し、 そしてあなたがバイナリツリー、ソートされただ1つに挿入する方法を見て、 それを通過すると、そのようなもの。 その知識は間違いなく時Huff'nパフ部分にあなたがダイビングのお手伝いをしようとしている psetの。 psetの標準版では、あなたのタスクは、パフを実装することです やハッカーのバージョンでは、あなたのタスクは、ハフを実装することです。 ハフは何をするか、それはテキストを受け取り、それは0と1に変換します ので、我々は周波数をカウントどこさて、上記のことをプロセス し、ツリーを作って、次に言った、 "どのように私はTを得るのですか？" Tは100で表され、そのようなもの、 その後ハフは、テキストとし、出力そのバイナリを取るだろう。 しかし、また、私達は私達が私達のメッセージの受信者を許可することを知っているので、 まったく同じツリーを再作成するために、それはまた、周波数カウントに関する情報が含まれています。 その後、パフと私たちは、0と1のバイナリ·ファイルを与えられている また、周波数に関する情報を与えられた。 我々は、であった元のメッセージにそれらの0と1の背中のすべてを翻訳 ので、我々はそれを解凍している。 あなたは、標準版をやっている場合、あなたは、ハフを実装する必要はありません そう、あなただけのハフのスタッフの実装を使用することができます。 それを行う方法についての仕様の指示があります。 あなたは、特定のテキストフ​​ァイルに基づいハフのスタッフの実装を実行することができます その後パフへの入力としてその出力を使用しています。 私は前に述べたように、我々はこの1つのディストリビューションのコードの多くを持っています。 私はそれを通過開始するつもりだ。 私はほとんどの時間を過ごすつもりです。hファイル cファイルであるため、我々は。hを持っているので、 それは、関数のプロトタイプを提供してくれます 我々は完全に正確に理解する必要はありません - あなたは。cファイルで何が起こっているか理解していない場合、その後、あまり心配しないでください それはいくつかのヒントを与えるかもしれないので、間違いなく見てみるとしよう そしてそれは他の人のコードを読むことに慣れておくと便利です。 huffile.hを見ると、コメント欄では、ハフマン符号化されたファイルのための抽象化層を宣言します。 我々がダウンした場合、我々はのためのコードを必要とするかもしれない256シンボルの最大値が設定されていることがわかります。 大文字と小文字の - - これはアルファベットのすべての文字が含まれています その後記号と数字など その後、ここで我々は、ハフマン符号化されたファイルを識別するマジックナンバーを持っています。 ハフマン·コード内で、彼らは特定のマジックナンバーを持っているつもりです ヘッダーに関連付けられている。 これは、単にランダムなマジックナンバーのようになります。 あなたが実際にASCIIにそれを翻訳した場合しかし、それは実際にハフを綴ります。 ここでは、ハフマン符号化されたファイルのための構造体を持っています。 ハフファイルに関連付けられた次の特性のすべてがあります。 その後、ダウンここではハフファイルのヘッダを持っているので、我々はそれHuffeader呼び出す 代わりに、それはとにかく同じに聞こえるので、余分な時間を追加する。 かわいい。 我々は、それに関連付けられたマジックナンバーを持っています。 それは実際のハフファイルなら、それは上記の電話番号まで、この魔法の1になるだろう。 そしてそれは、配列を持つことになります。 だからシンボルごとに、そのうちの256は、ある それはそれらのシンボルの周波数はハフファイル内にあるものを記入して起こっている。 そして最後に、我々は、周波数のチェックサムを持っている これは、これらの周波数の合計になります。 だからのHuffeaderが何であるか。 その後、我々はハフファイルに次のビットを返すいくつかの機能を持っている 同様hfcloseは、ここでは、この機能次に、ハフファイルにビットを書き込み、 それは実際にハフファイルを閉じます。 前に、我々はストレートだけfcloseを扱っていた、 しかし、あなたはハフファイルがある場合、代わりにそれをfclosingの 何を実際にやろうとしていることは、それをhfcloseとhfopenです。 それらは、我々が扱うことになるだろうことをハフファイルに固有の機能です。 その後、ここで私たちは、ヘッダーを読み込んで、そのヘッダーを書き込みます。 ちょうど私達が種類のハフファイルが何であるかの感覚を得ることができます。hファイルを読み取ることによって、 それは、実際にhuffile.cに入ることなく、持っているものの特性 れ、私たちが潜る場合は、もう少し複雑になるだろう。 これは、I / Oはここにポインタを扱うファイルのすべてを持っています。 ここで我々はhfreadを呼び出したときに、例えば、それはまだfread関数を扱っていることがわかります。 我々は完全にこれらの機能を退治していないが、我々の世話をするためにそれらを送っている 代わりに自分自身のすべてを行うのハフファイル内。 あなたが興味を持っている場合は、この全体をスキャンして自由に感じることができます と行くとバック層少しはがします。 我々が見しようとしている次のファイルがtree.h.です チュートリアルでは、我々はハフマンノードを期待すると述べた滑り込む前 そして我々は、typedef structのノードを作りました。 我々は、それがその後のシンボル、周波数、2ノードの星を持っていることを期待しています。 このケースでは、私たちがやっていることは、これは本質的に同じである 代わりにノードを除いて、我々は彼らの木呼ぶつもりです。 我々は、あなたが木を作る呼び出すときにそれはあなたの木へのポインタを返す関数を持っています。 新しいノードを作っていたときに、スペルチェックに戻る あなたは、ノード*新しい単語=のmalloc（sizeof演算）とそのようなことを言った。 基本的に、mktreeはあなたのためにそれに対処しようとしている。 同様に、ツリーを削除するときに、 そう、それは本質的に、あなたはそれで終わったツリーを解放だ 代わりに、明示的にその上に無料通話するのではなく、実際にちょうどrmtree関数を使用するつもりだ あなたは、そのツリーにポインタを渡すと、どこ子ですがあなたのためにそれの世話をします。 我々はtree.c.のぞき込む 我々としても実装を参照する以外に同じ機能を期待しています。 我々が期待したように、あなたはmktree呼び出すときには、ポインタにツリーのサイズをmallocを ので、0またはNULL値は、NULL値にすべての値を初期化する その後、ちょうどあなたにmallocさきたことを、その木へのポインタを返します。 ここでは、ツリーを削除呼び出すときには、まずあなたが二重解放していないことを確認します。 それはあなたが実際に削除したいツリーを持っていることを確認します。 ツリーには、その子を含み、ここにいるのは、 これは何をするか、それは再帰的にツリーの左ノードにツリーを削除呼び出し 同様に右側のノードとして。 それは親を解放する前に、それは同様に子供たちを解放する必要があります。 親はまた、ルートと交換可能である。 とても素晴らしい、曾曾曾祖父のような史上初の親、 や祖母の木は、まず第一のレベルをダウン解放する必要があります。 ので、これらの無料の、一番下に横断し、それらなど、戻っフリー思い付く だからツリーです。 今、私たちは森を見てみましょう。 あなたは、ハフマン木のすべてを配置する場所の森です。 それは、我々はプロットと呼ばれるものを持っているつもりだと言っている それは木だけでなく、次に呼び出さプロットへのポインタへのポインタが含まれます。 この種の構造はどのようなもののように見えるのでしょうか？ それは一種の存在それを上に述べています。 こっちに右。 リンクリスト。 我々はプロットを持っているとき、それがプロットのリンクリストのようなものだことがわかります。 森は、プロットのリンクリストとして定義されている など森林の構造が私達はちょうど私達の最初のプロットへのポインタを持っているつもりさ そのプロットは、その中のツリーまたはツリーにかなりのポイントを持っている その後などなど、次のプロットを指しています。 森を作るために、我々はmkforestを呼び出します。 その後、我々はここでいくつかの非常に有用な機能を持っています。 、我々は、あなたが森の中で渡す場所ピックアップしていると、戻り値はツリーです* ツリーへのポインタ。 どんなピックを行いますと、それはあなたが指していることを森の中に入って行くということです その森から最低周波数でツリーを削除 そして、そのツリーにあなたにポインタを与える。 一度あなたが選ぶ呼び出し、ツリーは、もう森の中に存在しません しかし、戻り値はその木へのポインタです。 その後、工場を持っています。 あなたが非0の周波数を持つツリーへのポインタを渡すことを条件に、 どんな植物が行​​いますが、それは森を取る木を取り、植える予定しているフォレストのツリー内部。 ここでは、rmforestを持っています。 基本的に私たちのために私達の木のすべてを解放したツリーを削除するための同様の 森を削除するには、その森の中に含まれる遊離すべては意志。 我々はforest.cに見れば、我々は、そこには少なくとも1 rmtreeコマンドを見ることを期待します 、森の木々はそれを持っている場合、フォレスト内のメモリを解放するために その後、最終的にはあなたはあまりにもそれらの木を除去する必要があるとしている。 我々はforest.cに見れば、我々は我々が期待どおりである私たちのmkforestを持っています。 我々は、mallocの事を。 それが最初から空ですので、我々は、NULLとしては、フォレスト内の最初のプロットを初期化する 次に我々は、最も低い重量でツリーを返しピック、、最低周波数を参照してください そして、その特定のノードを取り除くことがその木を指し、次のいずれか、 ので、それは森のリンクされたリストのことを取り出す。 そして、ここで我々は挿入するリンクリストにツリー工場を持っています。 何森はそれはうまくそれが私たちのためにソートされ続けているん。 そして最後に、我々は、予想通り、我々はそこrmtreeと呼ばれている、rmforestを持っていると。 これまでの流通コードを見てみると、huffile.cは、理解することがはるかに困難なことでおそらくあった 他のファイルwhereas自身が従うのは非常にシンプルでした。 ポインタやリンクリストなどの我々の知識があれば、 我々は、かなりよく従うことができました。 しかし、我々は本当に私たちが完全に理解していることを確認する必要があるすべては、hファイルである あなたは、それらの戻り値を扱う、それらの関数を呼び出すする必要があるため、 ので、完全にアクションが実行されることに何が起こっているか理解していることを確認してください あなたがそれらのいずれかの関数を呼び出すたびに。 しかし、実際にその中に理解することは我々がそれらを持っているので、非常に必要ではありません。hファイル。 私たちは、流通コードのままに2以上のファイルを持っています。 ダンプを見てみましょう。 そのコメントにあったダンプは、ここでハフマン圧縮ファイルを取り その後変換し、ダンプそのコンテンツのすべてのアウト。 ここで我々はそれがhfopenを呼び出していることがわかります。 これは、*入力= fopenを提出するミラーリングの一種である そして、あなたは情報を渡します。 それは、代わりにあなたはHuffileで渡しているファイル*を除いてほとんど同じです; 代わりにfopenのはhfopenに渡しています。 ここで我々は、ヘッダーで読む方法と同様の一種である、最初のヘッダーで読む ビットマップファイルの。 ここでやっているのはどうかを確認しているかどうかヘッダー情報 それは実際のハフファイルだということを示し、右のマジック番号が含まれ、 次に確認するためにこれらのチェックのすべての我々はオープンhuffed実際のファイルができていないか、またはファイルがその。 これが何を行うのは、それは我々が見ることができるシンボルのすべての周波数を出力している グラフィカルなテーブルに端末内。 この部分は便利になるだろう。 それは少しを持っており、可変ビットにビットずつ読み込み、それをプリントアウトします。 私は、ファイルを吸引した結果であるhth.bin、上でダンプを呼び出すようにしているとし スタッフソリューションを使用して、私はこれを取得することになります。 それは、これらのすべての文字を出力してから、それらが現れる頻度を入れている。 二回表示され、H、、：私たちが見ている場合は、それらのほとんどは、これ以外のことは、0である その後、一度表示されたT、。 そして、ここでは0と1で実際のメッセージを持っています。 我々は、おそらく怒るされた元のメッセージであるhth.txt、見れば 我々は、そこにいくつかのHsとTsを期待しています。 具体的には、わずか1 Tと2 HSを期待しています。 ここでは、hth.txtにあります。それは確かHTH持っています。 我々はそれを見ることはできませんが、そこに含まれて、改行文字です。 ハフファイルhth.binも同様に改行文字をエンコードしている。 ここでは、注文は、HTH、次に改行であることを知っているので、 我々は、おそらくHはちょうど単一（1）で表されていることがわかります その後Tは恐らく01ですそして次のHは1であるだけでなく、 その後我々は2つ​​の0で示される改行を持っています。 クール。 そして最後に、我々は複数の。cとhファイルを扱っているので、 我々は、コンパイラにかなり複雑な引数を持っているつもりです ので、ここで私たちはあなたのためにダンプを行うMakefileを持っています。 しかし、実際には、あなた自身のpuff.cファイルを作ることを行かなければならない。 Makefileは実際にあなたのためのpuff.c作りに対処しません。 我々は、Makefileを編集し、あなたにそれを任せている。 あなたが作るすべてのようなコマンドを入力すると、例えば、それはあなたのためにそれらのすべてを行います。 過去のpsetからMakefileの例を見て自由に感じる だけでなく、あなたのパフ·ファイルを作ることができるかもしれない方法を確認するには、このいずれかのオフに行く このMakefileを編集します。 それが私たちの流通コードのところはこれでおしまい。 かつて我々はそれを介して手に入れたし、ここだけ別のお知らせです どのように我々は、ハフマンノードを扱うことになるだろう。 我々は、もはやそれらのノードを呼び出すことするつもりはない、我々は彼らに木を呼ぶことになるだろう 我々は、charとのシンボルを表すことになるだろうここで、 その頻度、出現数、整数を持つ。 それはfloatよりも正確だから我々はそれを使用しています。 そして、我々は左の子と右の子に別のポインタを持っています。 森林は、私たちが見たように、ちょうど木のリンクリストです。 結局のところ、我々はハフファイルを構築しているときに、 私達は私達の森林はわずか1ツリーを入れたい - 1ツリー、複数の子を持つ1ルート。 以前我々は、弊社のハフマン木を作っていたときに、 我々は画面上のすべてのノードを配置することによって始まった そして、我々は、これらのノードを持っているつもりですと言って 結局、彼らは葉であることを行っているが、これは彼らのシンボルであり、これは彼らの周波数です。 我々はわずか3文字があれば、当社の森では、それは3木の森です。 そして、我々は、我々が最初に親を追加したときに、上に行くと、 我々は2つ​​のツリーの森を作った。 私たちは、森林からそれらの子供の2を削除してから、親ノードに置き換え それは子供のように、それらの2つのノードを持っていた。 そして最後に、私たちの最後のように、BSとの我々の例を作る際の手順、およびCs 最後の親を作成することです、 などを1に森の木々の私達の合計数をもたらすこと。 誰もがあなたが森の中に複数のツリーから始める方法を見ていない と1で終わる？オーケー。クール。 我々は、パフのために行うためには何が必要ですか？ 私たちに何が必要なのは、いつものように、彼らは私たちに、入力の右のタイプを与える、次のことを確認している 私たちは実際にプログラムを実行できるようにします。 この場合、彼らは彼らの最初のコマンドライン引数の後で私達を与えることになるだろう さらに2：私たちは解凍し、解凍されたファイルの出力したいファイル。 しかし、いったん我々は、彼らが値の右の量で私たちを渡すことを確認してください 我々は、入力がハフファイルであるかどうか確認する。 そして、かつて私たちは、その後、私たちは木を構築したい、それがハフファイルだという保証 それはメッセージを送ってきた人が建てたツリーに一致するようにツリーを構築します。 私たちは木を構築した後に続いて、次に我々は、彼らが渡されたことを、0と1を扱うことができ、 それは同じだから、私たちの木に沿ってその指示に従ってください。 その後、そのメッセージを書き出すcharsに戻ってビットを解釈。 そして、終わりに私たちはここでポインタを扱っているので、 我々は、任意のメモリリークを持っていないことを確認したい そして我々はすべて無料。 適切な使用を確保することは今では私たちのために古い帽子です。 我々はパフするファイルの名前であることを行っている入力、見に行く それから私達は、出力を指定 ので、テキストフ​​ァイルになります膨化出力のためのファイルの名前を指定します。 それは使用です。そして今、我々は、入力が怒るか、されていないことを確認したいと思います。 振り返って、そこに私たちを助けるかもしれない流通コードで何かあった ファイルは怒るされているかどうかを理解しますか？ Huffeader約huffile.cの情報がありました。 我々は、すべてのハフファイルはマジックナンバーとそれに関連付けられたHuffeaderを持っていることを知っている 各シンボルの周波数だけでなく、配列 同様にチェックサムなど。 我々は知っているが、我々はまた、dump.cを覗いた その年にはハフファイルに読んでいた。 それで、それを実行するために、それが本当に怒るされたかどうかを確認する必要がありました。 だから、おそらく我々はpuff.c.ための構造体として使用することができますdump.c 戻るPSET 4〜私たちはRGBの3でコピーしたファイルそれなのにを持っていたとき そして我々は、推理小説とResizeのためにそれを解釈 同様に、何を行う可能性は、単にCP dump.c puff.cのようなコマンドを実行している とそこにコードの一部を使用します。 しかし、それはプロセスのように簡単ではないだろう puff.cにあなたdump.cを翻訳するための、 少なくともそれが起動するためにどこかにあなたを与える 入力が実際に怒るか、されていないことを確認する方法について 同様にいくつか他のもののように。 我々は、適切な使用を確保し、入力が怒るされていることを確保している。 我々は我々の適切なエラーチェックを行っていることをやったことを毎回、 ので、問題があったら、戻っていくつかの障害が発生した場合、関数を終了する。 今、私たちが何をしたいのか、実際のツリーを構築しています。 私たちは森を見てみると、2つの主要機能があります 我々は非常に精通しになりたいと思ってしようとしている。 その植物私たちの森の中の非0の周波数ツリーをブール関数工場があります。 それでそこには森や木へのポインタへのポインタを渡します。 簡単な質問：あなたは、ハフマン木を構築しているときにどのように多くの森林あなたが持っているのだろうか？ 私たちの森が右、私たちのキャンバスのようなものです？ だから我々は1つだけの森を持っているつもりですが、我々は複数のツリーを持っているつもりです。 あなたが植物を呼び出すので、前に、あなたは、おそらくあなたの森を作りたいとしている。 あなたが森を作ることができる方法でforest.hのぞき込むと、このコマンドはそのためにあります。 あなたは木を植えることができます。我々はそれを行う方法を知っている。 そして、あなたはまた、森から木を選ぶことができます 最低重量とツリーを削除し、それにあなたにポインタを与える。 私達は私達自身の例をやっていた時に戻って考えると、 我々はそれを引き出したときに、我々は、単に単にリンクを追加しました。 しかし、ここだけではなく、リンクを追加する、 あなたはそれらのノードの2を削除し、別の1でそれを交換しているようにもっと考えることもできます。 、ピッキングや植栽の面でそれを表現する あなたは2本の木をピッキングして、別の木を植えています それは、あなたが子供として選んだこれらの2本の木を持っています。 ハフマンのツリーを構築するには、順序で記号と周波数で読むことができます Huffeaderはあなたにそれを与えるので、 あなたに周波数の配列を与える。 だから先に行くと、ちょうどそれに0を使って何かを無視することができます 我々はそれの終わりに256葉をしたくないので。 我々は唯一の文字である葉の数が欲しい それは実際にはファイルで使用されています。 あなたは、これらのシンボルを読み込み、0以外の周波数を持っているそれらのシンボルの各々ができる それらは木になるだろうしている。 何を行うことができますことは、あなたが非0の周波数シンボルで読むたびにです あなたは森の中にその木を植えることができます。 いったん森の中に木を植え、あなたは、兄弟のようにそれらの木に参加することができます そう植えて、2を選択してから、どこで拾っプラント1に戻って、 その1あなたの植物は、あなたが選んだ2人の子供の親であること。 それでは、あなたの最終的な結果は、フォレスト内の単一のツリーになるだろう。 それは、あなたのツリーを構築する方法です。 ここで間違って行くことができることがいくつかあります ので、我々は新しい木を作り、そのようなポインタや物事に対処を扱っている。 我々はポインタを扱う前にしたとき、 我々はmallocされるたびに、我々はそれが私たちにNULLポインタ値を返さなかったことを確認したかった。 したがって、このプロセス内のいくつかの段階でいくつかの例があるように行く どこにあなたのプログラムが失敗する可能性があります。 あなたは何をしたいのは、あなたがこれらのエラーを処理することを確認したいです とspecには、優雅にそれらを処理すると言う ので、プログラムが終了しなければならない理由、それらを伝えるユーザーにメッセージをプリントアウトしたい その後速やかにそれを終了します。 このエラー処理を行うには、あなたがそれをチェックすることを忘れないでください 障害があるかもしれないことを毎回。 あなたは新しいポインタを作っている一つ一つの時間 あなたはそれが成功したということを確認する必要があります。 我々は新しいポインタとmallocそれを作るされているものを行うために使用する前に、 それから私達はそのポインタがNULLであるかどうかをチェックします。 だから、あなたがちょうどそれを行うことができるいくつかの事例があるように起こっており、 しかし、時にはあなたは、実際に関数を呼び出しています そして、その関数内では、それはmallocingをやっている一つだ。 その場合、我々はコード内の機能の一部に戻って見れば、 そのうちのいくつかは、ブール関数です。 抽象的なケースでは、fooというブール関数を持っている場合、 基本的に、我々は、ほかにfooがないものは何でもやっていると仮定することができます それはブール関数なので、それがtrueまたはfalseを返します - 成功した場合はtrue、そうでない場合はfalseです。 だから我々は、fooの戻り値がtrueであるかfalseであるかどうかを確認する。 もしfalseであれば、それは我々がメッセージのいくつかの種類を印刷したいとしていることを意味します その後、プログラムを終了します。 私たちがやりたいことは、fooの戻り値をチェックすることです。 fooがfalseを返した場合、我々は何らかのエラーが発生したことを知っている そして私達は私達のプログラムを終了する必要があります。 これを行うための方法は、実際の関数自体があなたの条件である条件を持っていることです。 fooはxにかかると言う。 我々は、if条件として持つことができます（この例ではfoo（x））を。 fooを実行の終わりにそれがtrueを返した場合、基本的に、それは、意味 関数はfooを評価する必要があるため、我々はこれを行うことができます 全体の状態を評価するために。 それでは、それは関数がtrueを返し、成功した場合、あなたが何かをすることができる方法です。 しかし、あなたは、エラーチェックしているときに、あなただけの関数がfalseを返した場合、辞めたい。 あなたは何を行う可能性は、単に追加するだけです== falseまたはちょうどそれの前に強打を追加 そして、あなたは（！foo）があれば持っています。 その条件とは身体の中では、エラー処理のすべてを持っているでしょう ので、 "このツリーを作成できませんでした"とし、1またはそのような何かを返すこと、好きです。 それが何をするかは、しかし、fooはfalseが返された場合でも、それは - fooがtrueを返したと言う。 その後、再度fooを呼び出す必要はありません。それはよくある誤解です。 それはあなたの条件にあったので、すでに評価'S、 ので、すでにあなたがそのような木か何かを作る使用している場合は、その結果を持っている または植物またはピックか何か。 それは、すでにその値を持っています。それはすでに実行だ。 だから、条件としてブール関数を使用すると便利です あなたが実際にループ本体を実行するかどうかので、 それはとにかく関数を実行します。 最後のステップへの我々の2番目はファイルにメッセージを書き込んでいます。 かつて我々は、ハフマン木を作成してから、そのファイルにメッセージを書くことが非常に簡単です。 それはちょうど、0と1に従うようになりましたかなり簡単です。 それで、慣例により、我々はハフマンツリーで0が残って示していることを知っている と1sは右を示す。 それでは、あなたは、少しずつでは0（ゼロ）を取得するたびに読めば あなたは1で読み取るたびに、次に左の分岐に従っており、よ あなたは右の枝に従うつもりだ。 あなたが葉を打つまで、その後、続けていくつもりです 葉は枝の端にあることを行っているためです。 どのように我々は我々が葉を打ったかどうかを見分けることができるか？ 我々は前にそれを言った。 [学生]のポインタがNULLである場合。 >>うん。 左と右の両方のツリーへのポインタがNULLである場合、我々は葉を襲った場合、我々は知ることができます。 パーフェクト。 我々は、我々はハフファイルにビットごとに読みたいと思うことを知っています。 我々は、彼らが何をしたか、dump.cで前に見た彼らは、ハフファイルにビットごとに読み取られているように そしてちょうどそれらのビットが何であったかプリントアウト。 我々はそれをやっているつもりはない。我々は、もう少し複雑な何かをやっているつもりです。 しかし、私たちが出来ることは、我々は少しに読み取るコードのそのビットを取ることができますです。 ここで我々は上にいることを、現在のビットを表す整数ビットを持っています。 あなたがファイルの終わりに到達するまでこれは、ファイルのすべてのビットを反復するの面倒を見る。 それに基づいて、その後、イテレータのいくつかの種類を持ってするつもりだ あなたのツリーをトラバースする。 そして、ビットは、0か1であるか否かに基づいて、 あなたはどちらを左にその反復子を移動したり、右に移動するつもりだ ずっとあなたが葉に到達するまでの間なので、ずっとあなたがいることを、そのノードまで 任意の複数のノードを指していません。 なぜ我々はハフマンファイルではなく、モールス信号でこれを行うことができますか？ モールス信号で、あいまいさのビットが存在だからです。 ああ待って、同じように我々は可能性があり、我々は、これは私たちの文字ですので、多分、道に沿って文字を打ちました 我々は少しだけ長く続けた場合のに対し、我々は、別の文字を打っていただろう。 しかし、それは、ハフマン符号化で起こることはないだろう ので、我々が行っていることが唯一の方法は、文字を打つために安心することができ そのノードの左右の子供がNULLである場合です。 最後に、我々はすべてのメモリを解放したい。 我々は両方の我々が扱ってきたことハフファイルを閉じたい だけでなく、私たちの森の木々のすべてを削除します。 あなたの実装に基づいて、あなたはおそらく森を削除呼び出すするつもりだ 代わりに、実際に木を自分のすべてを通過する。 あなたは、任意の一時的な木を作った場合しかし、あなたはそれを解放したいと思う。 あなたは最高のあなたのコードを知っているので、メモリを割り当てている場所あなたが知っている。 あなたが行くそうだとすれば、mallocのF'ingさえコントロールすることから始め、 たびにmallocを見て、あなたはそれのすべてを解放することを確認すること しかしその後、ちょうどあなたのコードを経由する場合は、 あなたがメモリを割り当てている可能性のある場所を理解。 通常は単に "ファイルの終わりに私はちょうど私の森で森林を削除するつもりです"、と言うかもしれない ので、基本的に、その自由は、そのメモリをクリア "そして私はまた、ファイルを閉じ、その後、私のプログラムが終了しようとしているつもりです。" しかし、あなたのプログラムが終了したことをそのときだけです？ いや、時にはために起きたエラーがあったかもしれない。 多分、我々はファイルを開けませんでしたか、我々は別のツリーを作ることができなかった または何らかのエラーはメモリ割り当てプロセスで起こったので、それはNULLを返していました。 エラーが起こった後、私達は戻されて終了します。 それでは、あなたは、あなたのプログラムが終了することができ、すべての可能な時間ということを確認したい、 あなたはそこにあなたのすべてのメモリを解放したい。 それはちょうどあなたがあなたのコードを終了することをmain関数の一番最後にするつもりはない。 あなたのコードは、潜在的に時期尚早に返すかもしれないが、すべてのインスタンスに戻って見てみたい その後フリーどんなメモリが理にかなっています。 あなたが森を作ると呼んでいたと言う、それはfalseが返された場合。 あなたはおそらくあなたの森を削除する必要はありません あなたはまだ森を持っていないので。 しかし、あなたが途中で返される可能性があり、コード内のあらゆるポイントで あなたはすべての可能なメモリを解放することを確認したい。 だから我々はメモリを解放し、潜在的なリークを持つ扱っているときに、 我々は我々の判断と私たちのロジックを使用しないようにだけしたい だけでなく、我々は適切かどうか私たちのすべてのメモリを解放したかどうかを判断するためにValgrindを使用しています。 どちらかパフでValgrindは実行することができ、その後、また、それを渡す必要があります コマンドライン引数の数は右のvalgrind。 あなたはそれを実行することができますが、出力は少し不可解です。 我々は、スペルチェックでそれに使用されるビットを得ているが、我々はまだもう少し助けが必要 さて、漏れのチェック=フルのようないくつかの複数のフラグを付けて実行 それはおそらく私たちにValgrindの上のいくつかのより有用な出力が得られます。 次に、デバッグしているもう一つの有用な先端は、diffコマンドです。 あなたは、テキストフ​​ァイルであることを実行ハフのスタッフの実装にアクセスすることができます その後具体的には、バイナリファイル、バイナリ·ハフファイルに出力する。 次に、そのバイナリファイルで独自のパフを実行する場合、 次に、理想的には、実行すると、出力するテキストフ​​ァイルは同一であることを行っている あなたが渡された元の1に ここでは、例としてhth.txtを使用している、そしてそれはあなたのスペックでの話一つだ。 それは文字通り、HTH、次に改行です。 しかし、間違いなくお気軽に、あなたは間違いなく長い例を使用するよう奨励されます テキストフ​​ァイルの。 あなたも、もしかしたら圧縮し、その後解凍でショットを取ることができます 戦争と平和のようにあなたはスペルチェックで使用したファイルの一部 ジェーン·オースティンなど何か - クールの一種だろう - またはオースティン·パワーズ、 我々はそれにダウンして来ようとしないため、大きいファイルを扱う一種の 我々はここで次のツールは、ls-lを使用した場合。 我々は基本的には私たちの現在のディレクトリにあるすべての内容をリストするls、に慣れている。 -lオプションを渡すと、実際にそれらのファイルのサイズが表示されます。 あなたのpsetスペックを通過する場合、それは実際には、バイナリファイルを作成する方法について説明し のそれを吸引し、あなたは非常に小さなファイルに対してそれを参照してください。 それを圧縮し、その情報のすべてを翻訳するスペースのコスト 実際の利点を上回るそのようなすべての周波数や物事の 最初の場所でファイルを圧縮する。 しかし、あなたには、いくつかの長いテキストフ​​ァイルにそれを実行した場合、その後、あなたはいくつかの利点を得るために始めることがわかるかもしれません これらのファイルを圧縮インチ そして最後に、我々は間違いなくあまりにも便利になるだろうとしている私たちの古い友人のGDBを持っています。 私たちは木を作るのは多分ハフツリーやプロセス上の任意の質問がありますか またはHuff'nパフ上の他の質問？ オーケー。私は少しのために周りにいるよ。 おかげで、みんな。これはチュートリアル6であった。そして幸運。 [CS50.TV]