JASONハーシュホーン：みんなを歓迎 第七。 我々はもちろん、週7である。 この今後の木曜日 ハロウィーンは、私は私である カボチャのようにドレスアップ。 私は腰をかがめると装着ができませんでした 私の靴、私はなぜそれがだ ちょうど靴下を着用しています。 私はまた、下に何も着ていないよ これ、それはですので、もし、私はそれを取ることはできません あなたに邪魔。 私はそのため、事前にお詫び申し上げます。 あなたが想像する必要はありません。 何が起こっている。 私はボクサーを着ています。 だから、すべての良いことだ。 私は、私は理由について長い話を持っている カボチャに扮したが、私はするつもりだ 後でこのセクションのためにそれを保存 私は始めたくないからです。 我々はエキサイティングなことがたくさんある 今週の上に行くために。 それらのほとんどは、これに直接関係 今週の問題セット、スペルミス。 また、リンクされた上で行くことになるだろう リストやハッシュテーブル セクション全体のため。 私は、毎週のリストをこのリストを設置 あなたとあなたを助けるためにするためのリソース このコースに重要。 損失で、またはいくつかを探していた場合： 詳細については、次のいずれかをチェックしてください これらのリソース。 ここでも、pset6はスペル​​ミスで、 今週のPSET。 そしてそれはまた、あなたを奨励し、私 他のいくつかを使用するように、なることをお勧めします 特にこのPSETためのリソース。 特に、3は私だ 画面上にリストアップ - 我々は精通してきたGDB、 そして今、しばらくの間使用してきている 今週非常に参考になるだろう。 だから私はここにそれを広げた。 しかし、いつでも、Cで作業している、 あなたはいつもにGDBを使用する必要があります プログラムをデバッグします。 今週もValgrindは。 誰もがValgrindのが何を知っていますか？ 観客：これは、メモリリークをチェックする？ JASONハーシュホーン：Valgrindの メモリリークをチェックします。 もしそうなら、あなたのmalloc何かお プログラムは、メモリーのために求めている。 あなたのプログラムの最後には、次のものが あなたがしたすべてのものに無料で書き込む メモリをお返しするためにmallocさ。 あなたが最後に自由記述していない場合は あなたのプログラムは、結論に来る、 すべてが自動的になります 解放される。 と小さなプログラムのために、それはだ ていないことを大したこと。 しかし、あなたは長いランニングを書いているのであれば 終了しないプログラム、 必ずしも、分またはAのカップルで 数秒後、メモリリーク 巨大な契約になることができます。 そうpset6ため、期待があることである あなたは、ゼロメモリリークを持つことになります あなたのプログラム。 メモリリークをチェックするには、実行してvalgrindの そしてそれはあなたにいくつかの素敵なをあげる 出力しているかどうかを知らせる またはすべてが無料だったわけではありません。 我々は、後でそれを練習します 今日では、うまくいけば。 最後に、diffコマンド。 あなたはそれに似たものを使用 PEEKツールでpset5中。 あなたの中に見ることができました。 また、あたりも、差分を使用 問題は、仕様を設定してください。 しかし、あなたはに許可された 2つのファイルを比較します。 あなたは、ビットマップファイルとを比較することができ インフォスタッフ液のヘッダと pset5でソリューションの場合 あなたはそれを使用することにしました。 diffはあなたができるようになります だけでなく、それを行う。 あなたがのために正しい答えを比較することができます あなたの答えに設定今週の問題 と表示された場合、それまでの線または参照 どこにエラーがある。 ので、これらは3つの良いツールであることを あなたは今週のために使用する必要がありますし、 間違いなくあなたのプログラムをチェック これら3つのツールで それをインチにする前に 繰り返しますが、私は毎週述べたように、 両方 - あなたは私のためのフィードバックがあれば 正かつ建設 - ウェブサイトに向かう気軽に このスライドの下部にある そして入力がそれ。 私は実際にどんな感謝 そしてすべてのフィードバック。 そして、あなたは私にその具体的なものを与える場合は、 私は、私はあることを改善するために、またはすることができます あなたはに私をしたいことをよくやって 続けて、私は心にそれを取ると、 本当に耳を傾ける努力 ご意見·ご感想を。 私は私がするつもりだ約束することはできません すべてのものは、しかし、身に着けているような 毎週コスチュームパンプキン。 だから我々はの大半を過ごすつもりです セクションには、私が述べたように、の話 リンクリストやハッシュテーブル、その に直接適用されます 問題は、この一週間に設定。 リンクリストは、我々は比較的オーバー行くよ すぐに我々は公平なビットを費やしてきたので、 時間の欄でその上を行く。 そして私たちはまっすぐに買ってあげる リンクされたリストのための問題をコードする。 した後、最後に、我々はについて話します 彼らがこれにどのように適用されるかのテーブルをハッシュし、 今週の問題は、設定してください。 あなたは前に、このコードを見てきました。 これは構造体であり、それは定義されている ノードと呼ばれる新しい何か。 およびノー​​ド内の整数があります 右こことへのポインタがあります 別のノード。 我々は前にこれを見てきました。 これはのために控えてきた 今数週間。 それは我々がしてきたポインタを兼ね備え 可能にし、構造体を操作 私たちは、別の2を結合する 1データ型に物事。 画面上で起こってたくさんあり​​ます。 しかし、それはすべて、比較的であるべき あなたに精通している。 最初の行では、我々 新しいノードを宣言します。 そして、その新しいノードの内部で、私はセット 1にそのノード内の整数。 私たちは、私がやっている次の行を参照してください printfコマンドが、私はグレー表示されました printfコマンドは本当に理由 重要な部分はここに、このラインである - new_node.n。 ドットは何を意味するのでしょうか？ 観客：ノードに移動し、 それのためのn値を評価します。 JASONハーシュホーン：それです。 まったく正しい。 ドットは、n個の部分にアクセスを意味 この新しいノードの。 この次の行は何をしますか？ マイケル。 観客：それは別のノードを作成します つまり、新しいノードを指すようになります。 JASONハーシュホーン：だからそれはしていません 新しいノードを作成します。 それは何を作成します？ 観客：ポインター。 JASONハーシュホーン：ノードへのポインタ、 ここで、このノード*で示すように だから、ノードへのポインタを作成します。 そして、それはどのノードを指している マイケルに？ 観客：新しいノード？ JASONハーシュホーン：新しいノード。 我々はしましたので、それはそこに指して それを新たなノードのアドレスを与えられた。 そして今、この行では、参照してください。 の2種類の方法 同じことを表現する。 と私は指摘したいと思ったどのようにこれらの 二つのことは同じです。 最初の行では、間接参照 ポインター。 だから我々はノードに移動します。 つまり、この星が何を意味するのです。 私たちは、ポインタを持つ前に、それを見てきました。 そのノードに移動します。 これはカッコ内にあります。 して、ドット演算子を経由してアクセスする そのノードのn個の要素。 だから構文を取っている 我々は今ここで見た ポインタとそれを用いた。 もちろん、もし忙しいの種類を取得します あなたは、これらの括弧を書いている - あの星とそのドット。 それは少し忙しい。 だから我々は、いくつかのシンタックスシュガーを持っています。 この行はここ - ptr_node-> N。 つまり、まったく同じことを行います。 ように、コードの2行があります 同等と行います まったく同じこと。 しかし、私は前にそれらを指摘したかった あなたが理解しておりますので先に進む 本当に正しいここにこの事があることを 逆参照のためだけ糖衣構文 ポインタ、その後に行く その構造体のnの部分。 このスライドについてのご質問？ [OK]をクリックします。 だから我々は、カップルを通過しようとしている あなたが行うことができます操作の リンクされたリスト。 リンクリスト、リコールは、一連の 互いを指すノード。 そして、我々は一般的にはポインタで始まる 一般的に、ヘッドと呼ばれる、を指していることを リストの最初のもの。 我々は、ここで最初の行にそう まず私たちのオリジナルのLを持っています。 だから、そのことは、あなたが考えることができます - この テキスト右ここでは、などと考えることができます 我々は保存されてきたばかりのポインタ どこかのポイント 最初の要素へ。 このリンクリスト内の 我々は4つのノードがあります。 各ノードは、大きな箱です。 大きな内部大きな箱 ボックスには、整数部分である。 そして、我々は、ポインタの部分を持っている。 これらのボックスは、描かれていない スケールの大きさとは理由 バイト単位の整数？ どのくらいになりました？ 四つ。 ポインタはどのように大きいです！ 四つ。 だから本当に、我々は描画した場合 この両方のボックスをスケールする 同じサイズになります。 このケースでは、挿入する リンクされたリストに、何か。 だから、我々は挿入している、ここでダウンして見ることができます 5私たちはを横断 リンクリスト、5見つける 行くし、それを挿入します。 それを打破してみましょうと行く もう少しゆっくり。 私は、ボードを指すことにします。 だから我々は我々のノードが5という 私たちは、mallocはで作成しました。 なぜ誰もが笑っている？ ほんの冗談です。 [OK]をクリックします。 だから我々は5をmallocさだ。 私たちは、このノードを作成しました どこか別の場所。 我々は行くこと準備ができている。 私たちは、目の前に開始 2との私たちのリスト。 そして、我々は挿入したい ソートされた方法で。 だから我々は2を参照してください、私たちは入れたい場合は、 我々が見たときに5に、私たちは何をしますか 私たちより少ない何か？ 何が？ 我々は、この中に5を挿入したい リンクリスト、それがソート保つ。 私たちは、数2を参照してください。 だから我々は何をしますか？ マーカス？ 観客：ポインタを呼び出し 次のノードに。 JASONハーシュホーン：そしてなぜ 私たちは、次のいずれかに行く？ 観客：それはだから リスト内の次のノード。 そして、我々はそれだけで、他の場所を知っている。 JASONハーシュホーン：そして5は大きい 特に、2つより。 我々は、ソートそれを維持したいので。 そのように5つが2以上である。 だから我々は、次のものに移動する。 そして今、我々は4に達する。 我々は4に達したときに、何が起こりますか？ ファイブは4より大きい。 だから我々は続ける。 そして今、我々は6にいる。 そして、我々は6で何を見ていますか？ はい、カルロス·？ 観客：シックス5より大きい。 JASONハーシュホーン：シックスです 5よりも大きい。 私たちが望む場所だからです 5を挿入します。 しかし、覚えておいて、もし私たち ここでしか1ポインタを持っている - これはです私達の余分なポインタである リストを横断する。 そして、我々は6を指しています。 私たちは何のトラックを失ってしまった 6の前に来る。 だから我々はに何かを挿入したい場合は、 このリストはソートされ、それを維持し、我々は おそらくどのように多くのポインタが必要ですか？ 観客：二つ。 JASON HIRSCHORN：二つ。 電流を追跡するOne 1とを追跡するための1 以前の1。 これは、シングルリンクリストです。 これは、一方向のみに進む。 私たちは二重にリンクされたリストを持っていた場合、どこで すべてが事を指していた ITとその前のものは、後 我々はそれをする必要はありません。 しかし、このケースでは、失いたくない ケースで私たちの前に来たもののトラック 我々は5のどこかに挿入する必要があります 真ん中に。 我々は9を挿入されたと言う。 ときに何が起こるか 我々は8になった？ 読者：あなたがする必要があるだろう そのヌルポイントを得る。 代わりに、あなたが持っているだろうヌル点を持っていることの 要素を追加してから持っている それは9を指す。 JASON HIRSCHORN：その通りです。 だから我々は8を得る。 我々は、リストの最後に到達するため、 これはNULLを指している。 そして今、代わりになるのが、を指す ヌル我々はそれが私たちの新しいノードを指す必要があります。 そして、我々は中にポインタを設定 nullに私たちの新しいノード。 誰もが疑問を持っていますか 挿入はどうでしょうか？ 私は気にしない場合はどう ソートされたリストを保持する？ 観客：でそれをスティック 先頭または末尾。 JASON HIRSCHORN：でそれをスティック 先頭または末尾。 その1、我々は何をすべき？ ボビー？ なぜ終わり？ 観客：ので、初め すでに満たされている。 JASON HIRSCHORN：わかりました。 初めはすでに満たされている。 誰がボビーに反論したいと考えています。 マーカス。 観客：さてあなたはおそらくしたい 先頭に付いているので そうでなければあなたがでそれを置けば あなたがする必要があるだろう終わり リスト全体を横断する。 JASON HIRSCHORN：その通りです。 だから我々は、ランタイムを考えている場合は、 最後に挿入するランタイム N、これのサイズになります。 挿入するビッグOランタイムは何ですか 先頭の？ 一定の時間。 だから、維持を気にしない場合は、 ただへより良いものにソート、 このリストの先頭に挿入します。 そして、それは一定の時間で行うことができます。 [OK]をクリックします。 次の操作は、見つける他のどのです - 我々は、検索としてこれを言葉で表現しました。 しかし、我々は目を通すつもりだ いくつかのオブジェクトのリンクリスト。 君たちはのためのコードを見てきました 講義で前に検索します。 しかし、我々は一種だけでそれをやった 挿入、または少なくとも挿入 何か替え。 あなたを介して見て、ノードがノードを行く、 あなたがしている番号を見つけるまで、 探している。 あなたが到達した場合はどうなりますか リストの最後に？ 私は9と私を探していますと言う リストの最後に到達する。 私たちは何をしますか？ 観客：falseを返します？ JASON HIRSCHORN：falseを返します。 我々はそれを見つけることができませんでした。 あなたがリストの最後に到達した場合 あなたがしている番号を見つけられませんでした を探している、それはそこにない。 に関するご質問は見つける？ これはソートされたリストであった場合、どのようだろう 私たちの検索に異なること？ うん。 観客：それは最初の値を見つけるだろう それは、2以上の あなたが探していると、 その後、falseを返します。 JASON HIRSCHORN：その通りです。 だから、我々が取得する場合には、ソートされたリストの場合は、 何よりも大きいの何か 私たちが探している、我々はする必要はありません リストの最後に続ける。 私たちは、その時点でfalseを返すことができます 我々はそれを見つけるつもりはないので。 質問は今、我々は話をしましたされている 並べ替えリンクリストを保持することは、 ソートされていないそれらを維持。 それはあなたがしているものになるだろう おそらくについて考える必要があるとして コー​​ディング問題があれば5を設定したとき 別々にハッシュテーブルを選ぶ チェーン化のアプローチ、その 我々は、後で説明。 しかし、それはリストを維持するために価値がある ソートされ、多分持ってできるように より速く検索する？ またはそれはすぐに挿入することをお勧めします 一定のランタイムで何かが、その後 検索長く持っている？ つまり、その権利があるトレードオフです より適切であるかを決めるために取得 特定の問題のために。 そして1は必ずしもありません 絶対的に正しい答え。 それは確かにあなたが得る決断だ にするために、そしておそらく良い守るために その中で、たとえば、コメントや2理由 あなたは他の上1を選択しました。 最後に、削除。 我々は、削除を見てきました。 それは、検索に似ています。 私たちは、要素を探します。 我々は6を削除しようとしていると言う。 だから我々はここ6を見つける。 私たちは必ず私たちをしなければならない事 何何をを指しているということです 6 - 私たちはステップで見るように ダウンここに2 - 6つのニーズを指しているのはどのような 今6をスキップして、に変更する 何でも6は、を指している。 私たちは、これまでの残りの部分を孤立させたくない それを設定し忘れることで私たちのリスト 前のポインタ。 して、時々、依存 プログラムでは、彼らはちょうどよ 完全にこのノードを削除してください。 時には、あなたが戻ってしたいと思う このノードでの値。 だから、作品を削除する方法を説明します。 上の任意の質問は削除しますか？ 観客：だから、削除しようとしている場合は、 それは、あなただけの自由な使用になるため おそらくそれはmallocされたのですか？ JASON HIRSCHORN：あなたは無料にする場合 まったく正しいとあなたです、何か それをmallocさ。 我々は、この値を返すように思ったと言う。 我々は、返される可能性があります6、その後自由 このノードとその上に自由に連絡してください。 または我々は、おそらく最初のフリー呼びたい して、6を返します。 [OK]をクリックします。 それでは、コーディングの練習に移りましょう。 我々は3つの機能をコーディングするつもりだ。 最初の1はinsert_nodeと呼ばれています。 だから、私はあなたを電子メールで送信するコードがあると、 後で、これを見ている場合 あなたはlinked.cにコードにアクセスすることができます CS50のウェブサイトで。 しかしlinked.cに、いくつかあります 既にのスケルトンコード あなたのために書かれて。 して、カップルの関数があります あなたが記述する必要があります。 まず、するつもりだ insert_nodeを記述します。 そして、何insert_nodeん 整数値を挿入する。 そして、あなたは整数を与えている リンクされたリストに変換する。 特に、次のものが必要 ソートされたリストを維持する 最小から最大まで。 また、あなたはしたくない 任意の重複を挿入します。 最後に、insert_nodeを見ることができるように BOOLを返します。 だから、ユーザーが知っているようになっている インサートがあったか否か trueまたはfalseを返すことにより、成功した。 このプログラムの終わりに - この段階のためにあなたがする必要はありません 何を解放することを心配する。 あなたがやっているすべては、整数を取っている そして、リストに挿入する。 それは私が今することを求めているものです。 もう一度、linked.cにおいて、その必要 ならないすべては、スケルトンコードです。 そして、あなたは一番下の方に表示されるはずです サンプル関数の宣言。 しかし、それをコーディングに入る前に C言語で、私は非常に行くことをお勧めします の工程を経て、我々はしてきた 毎週練習。 我々はすでにを通じて行ってきた これの絵。 だから、いくつか理解している必要があります これがどのように動作するかの。 しかし、私は書くことをお勧めだろう インチダイビング前にいくつかの擬似コード そして、我々は以上行くつもり グループとしての擬似コード。 それから、あなたが書いた回は 擬似コード、そして我々は我々を書いたら グループとしての擬似コードは、次の操作を実行でき C言語でそれをコーディングに入る ヘッドアップ、insert_node関数として おそらくのトリッキーです 3我々は書くつもりですので、私 にいくつかの追加の制約を追加しました 特に、プログラミング、その あなたがいずれかを挿入するつもりはない 重複して、そのリスト ソートされたままにしてください。 だから、これは些細なプログラムであり、 あなたがコードする必要がある。 そして、なぜあなたは7に5を取ることはありません 分だけで動作させるために 擬似コードとコード。 そして、我々が開始されます グループとして行く。 もう一度、あなただけの質問がある場合 手を挙げて、私は周りに来る。 。 我々はまた、一般的に、これらを行う - または私は明示的に言うことはありません 人々と働くことができる。 しかし、明らかに、私は非常になることをお勧めします、 ご質問がある場合には、依頼する 隣人があなたの隣に座って あるいは誰かと仕事 他にあなたがしたい場合。 これは、個々である必要はありません サイレント活動。 それでは、いくつかを書き始めましょう ボード上の擬似コード。 誰が私の最初の行を与えることができます このプログラムの擬似コード？ この機能のために、むしろ - insert_node。 オールデン？ 観客：だから私がした最初のものだった ノードに新しいポインタを作成し、私 それは、同じを指す初期化 リストが指しているもの。 JASON HIRSCHORN：わかりました。 だから、新しいポインタを作成している リストにはなく、ノードに。 観客：そうです。 うん。 JASON HIRSCHORN：わかりました。 した後、私たちは何をしたいのですか？ その後何ですか？ どのようなノードはどうでしょうか？ 私たちは、ノードを持っていません。 我々だけで価値がある。 我々はノードを挿入したい場合は、何を行っており 私たちも、できる前に最初に行う必要があります それを挿入する方法はないでしょうか？ 観客：ああ、申し訳ありません。 我々は、ノードのためのスペースをのmallocする必要があります。 JASON HIRSCHORN：優秀。 それではやってみましょう - [OK]をクリックします。 その高に到達することはできません。 [OK]をクリックします。 私たちはダウン行くつもりしてから、している 我々は2つ​​の列を使用している。 私はそれを行くことができない - [OK]をクリックします。 新しいノードを作成します。 リストには、別のポインタを作成することができます それが存在するか、あなただけのリストを使用することができます。 あなたは本当にそれをする必要はありません。 だから我々は、新しいノードを作成します。 素晴らしい。 それは我々が最初に何をすべきかだ。 次は何ですか？ 観客：待ってください。 我々は今、新しいノードを作成する必要がありますか 我々はそれを確認するために待機しなければならない ノードのない重複はありません リスト上の我々はそれを作成する前に？ JASON HIRSCHORN：良い質問。 ので、後でそれを保持してみましょう 我々は作成されます時間の大半 新しいノード。 だから我々は、ここでそれをしておこう。 しかし、それは良い質問です。 我々はそれを作成し、我々は見つけた場合 何をすべき重複し、 私たちは、返す前にいますか？ 観客：それを解放。 JASON HIRSCHORN：うん。 おそらくそれを解放します。 [OK]をクリックします。 我々は、我々の後に何をしますか 新しいノードを作成しますか？ アニー？ 観客：我々は置く ノード内の数字？ JASON HIRSCHORN：その通りです。 我々は数を入れて - 私たちはスペースをのmalloc。 私はそれを残すつもりだ すべて1行として。 しかし、あなたは正しい。 それから、スペースををmallocし、 私たちは、インチ数を入れて 私たちも、ポインタを設定することができます nullにその一部。 それはまさにそうです。 した後、どのようなことをした後はどうでしょうか？ 我々は、ボード上でこの絵を描きました。 だから我々は何をしますか？ 読者：私たちは、リストを通過します。 JASON HIRSCHORN：リストを通過します。 [OK]をクリックします。 そして、我々は、各ノードでのために何をチェックしますか。 クルト、私たちは何をチェックしますか 各ノードでのために？ 読者：のN値かどうかを参照してください そのノードはnの値よりも大きい 私たちのノードの。 JASON HIRSCHORN：わかりました。 私は何をするつもりだ - [OK]を、ええ。 だから、Nさん - 値が大きい場合は私が言おうとしています このノードよりも、我々は何をしますか？ 観客：さて、私たちは、挿入 右その前の事。 JASON HIRSCHORN：わかりました。 だから、これより大きいなら、 その後、我々は挿入する。 しかし、我々は右の前にそれを挿入したい 我々はまた、である必要があるので、 追跡し、次いで、 前だったかの。 そうする前に挿入します。 だから我々は、おそらく何かを逃した それ以前に。 我々は、おそらく維持される必要がある 何が起こっているかを追跡。 しかし、我々はそこに戻って得られます。 それがどうした値よりも小さい？ クルト、私たちは、次の場合に何をしますか 値がより小さい？ 観客：それからちょうど続ける それは、最後の1でない限り。 JASON HIRSCHORN：私はそれが好きです。 だから、次のノードに移動します。 それは、最後の1でない限り - 我々は、おそらくそのためにチェックしている 条件の面で。 しかし、ええ、次のノード。 そして、それは、低すぎるなってきた 私たちはこっちに移動します。 しかし、もし - 誰もがこれを見ることができますか？ 我々は等しいなら、私たちは何をしますか？ 値は、私たちは、挿入しようとしている場合 このノードの値に等しいか？ うん？ 観客：[聞こえない]。 JASON HIRSCHORN：うん。 この与えられた - マーカスは正しい。 私たちは、多分行っている可能性が 何か違う。 しかし、ここで、我々はそれを作成したことを考えると 我々は自由として返す必要があります。 ああ。 それが良いですか？ どのようにそれはです？ [OK]をクリックします。 我々は何をすべきか、空きと リターン、[聞こえない]？ [OK]をクリックします。 我々は何が不足している？ だからここで我々は追跡している 前ノードの？ 読者：私はそれが行くと思う 後に新しいノードを作成します。 JASON HIRSCHORN：わかりました。 だから、初めに我々は、おそらくよ - ええ、私たちは新しい体へのポインタを作成することができます 前のノードポインタのようなノード、および 現在のノードのポインタ。 それでは、ここでそれを挿入してみましょう。 現在および以前の作成 ノードへのポインタ。 しかし、ときに我々はこれらのポインタを調整しますか？ 我々は、コード内でそれをどこで行うのですか？ ジェフ？ 読者： - 値の条件？ JASON HIRSCHORN：どの 特に1？ 読者：私は困惑している。 値は、このノードよりも大きい場合 つまり、どこに行きたいということではありません 次のノードに？ JASONハーシュホーン：だから私たちの値である場合 このノードの値よりも大きい。 観客：うん、あなたがしたいと思う 右、ラインのさらに下に行く？ JASONハーシュホーン：右。 だから我々はそれをここに挿入しないでください。 値は、このノードよりも小さい場合、 我々は次のノードに移動する - あるいは、私たち 前に挿入します。 観客：これはこれであり、待ってください ノードとの値はありますか？ JASONハーシュホーン：良い質問。 この関数の定義あたりの値 我々は与えられているものである。 だから、値は我々が与えられている番号です。 そう値がこれより小さい場合 ノードは、我々は挿入する時間が必要です。 値は、このノードよりも大きい場合 我々は次のノードに移動します。 そして、元の質問に、 しかし、どこに - 観客：値が大きい場合 このノードより。 JASONハーシュホーン：だから 我々はここで何をしますか？ 甘い。 それは正しいです。 私は書くつもりだ 更新ポインタ。 しかし、はい、現在の1に あなたはそれを更新してしまう 次の1を指す。 我々は他の何欠落している？ だから私は、これを入力するつもりです geditのにコード。 私はこれを行うながら、あなたが持つことができます コー​​ディングで動作するようにカップル分以上 このCの だから私は、入力の擬似コードを持っている。 私たちは始める前に、簡単なメモ。 我々は完全にできないことがあります すべてでこれを終える これらの機能の3。 それらへの正しい解決策があります 私はあなたたちに出てメールでお知らせいたしますことを セクションの後、それは意志 CS50.netに掲載される。 だから私はすることをお勧めしません。 のセクションを見に行く。 私はあなたにこれらを試してみることをお勧めします 所有してから練習を使用 あなたの答えをチェックする問題。 これらはすべて密接に設計されています に関連し、どのように付着 あなたは、問題のセットで行う必要があります。 だから私は、これを実践することをお勧めします 自分で、その後にコードを使用し あなたの答えをチェックしてください。 私はハッシュへ移動したいないので、 節のある時点でのテーブル。 だから我々はそれをすべてを介して取得されない場合があります。 しかし、我々は今我々はできる限りやる。 [OK]をクリックします。 私たちは始めましょう。 ASAM、どのように我々は、新しいノードを作成するのですか？ 読者：あなたは*構造です。 JASONハーシュホーン：だから我々 ここでそれをアップする必要があります。 あ、ごめん。 あなたは、構造体*を言っていた。 観客：そして、[？種類は？] ノードまたはCノード。 JASONハーシュホーン：わかりました。 私はそれを呼び出すつもりで、new_node 私たちは一貫して滞在することができます。 観客：そして、あなたはそれを設定したい 、最初のノードを頭に。 JASONハーシュホーン：わかりました。 だから今、このポインティング - ので、この まだ新しいノードを作成していません。 これはちょうどを指している リスト内の最初のノード。 どのように新しいノードを作成するのですか？ 私は、新しいノードを作成するためのスペースが必要な場合。 malloc関数。 そして、どのようにビッグ？ 観客：構造体のサイズ。 JASONハーシュホーン： 構造体のサイズ。 と構造体は何と呼ばれるのか？ 観客：ノード？ JASONハーシュホーン：ノード。 そうはmalloc（sizeof演算（ノード））; 私たちにスペースを提供します。 この行は - 一つのことは、この行が正しくありません。 構造体へのポインタで、new_nodeですか？ これは一般的な名前です。 それは何ですか - ノード、正確に。 これは、*ノードの。 そして、我々は右の後に何をしますか 我々は牙山何かをは、malloc？ 私たちが最初に行うことは何ですか？ それは何が動作しない場合は？ 観客：ああ、確認した場合、それ ノードを指す？ JASONハーシュホーン：その通りです。 ですから、ここで、new_node場合、equalsに等しい ヌル、私たちは何をしますか？ これはBOOL、この関数を返します。 その通りです。 よさそうだ。 そこに追加するものは？ 我々は最後にものを追加します。 しかし、それは今のところよさそうだ。 現在と以前のポインタを作成します。 マイケルは、私はこれをどのように行うのですか？ 読者：あなたが持っているだろう ノードを行うには*。 あなたは1をしないように必要があるだろう ここで、new_nodeのためではなくのために 我々はすでに持っているノード。 JASONハーシュホーン：わかりました。 だから、現在のノードが、我々はにしている。 私はゴロゴロと呼ぶことにします。 わかりました。 我々は維持したいことを決定した 2、我々は知っている必要がありますので、 その前に何が。 彼らは何に初期化されますか？ 読者：私たちのリスト内の値。 JASONハーシュホーン：だから何です 私たちのリスト上の最初の事？ またはどのように我々は知っている場所 私たちのリストの先頭にはある？ 観客：それは渡されません 関数に？ JASONハーシュホーン：右。 それは、まさにここに可決された。 だから、それが関数に渡されたなら、 リストの先頭、我々は何をすべき に等しい電流を設定します？ 観客：リスト。 JASONハーシュホーン：リスト。 それはまさにそうです。 今ではのアドレスを持っている 私たちのリストの先頭。 そして、何前のはどうでしょうか？ 観客：リストから1を引いた？ JASONハーシュホーン：あります その前に何もない。 だから我々は何も意味しないために何ができますか？ 観客：ヌル。 JASONハーシュホーン：うん。 それは良いアイデアのように聞こえる。 完璧。 ありがとう。 リストを通過します。 どのくらい私たちがしようとしているコンスタンティン、 リストを行く？ 観客：我々は、NULLに達するまで。 JASONハーシュホーン：わかりました。 forループ、しばらく、もしそうであれば。 私たちは何してるの？ 観客：たぶん、forループ？ JASONハーシュホーン：のループのためにやってみましょう。 [OK]をクリックします。 観客：そして、我々はのために言う - 現在のポインタになるまで NULLと同じではありません。 JASONハーシュホーン：だから我々は知っている場合 条件、どのように我々は、ループを書くことができます その状態オフに基づいて。 我々は、ループのどのような種類を使用すればよいですか？ 観客：ながら。 JASONハーシュホーン：うん。 つまり、ベースより理にかなって あなたが言ったことのオフ。 私たちはちょうど私達に行きたい場合は、だろう ちょうどその事を知っている、それはなるだろう whileループを実行する感覚。 電流が等しくないNULLをする間、 値は、このノード未満である場合。 Aksharは、私にこのラインを与える。 観客：電流If-> N N値よりも小さい。 またはその逆を行います。 そのブラケットを切り替えます。 JASONハーシュホーン：申し訳ありません。 観客：ブラケットを変更します。 JASONハーシュホーン：だからそれはだ場合には 値より大きい。 それはと混同だから 上記のコメントは、私はそれをするつもりです。 しかし、はい。 我々は、この値よりも小さい場合 ノード、我々は何をしますか？ ああ。 私は右のそれをここに持っている。 前に挿入します。 [OK]をクリックします。 我々はそれをどのように行うのですか？ 観客は：それはまだ私ですか？ JASONハーシュホーン：うん。 読者：あなた - ここで、new_node->次。 JASONハーシュホーン：だから何だ それが等しくなるように行きますか？ 観客：これは、等しい電流になるだろう。 JASONハーシュホーン：その通りです。 だから他の - 我々は更新するために他に何が必要なのですか？ 観客：過去がnullに等しいかどうかを確認します。 JASONハーシュホーン：前の場合 - その前がnullに等しい場合。 観客：それは起こっていることを意味 頭になるために。 JASONハーシュホーン：その手段 それが頭になってきた。 それでは、私たちは何をしますか？ 読者：私たちは、頭を行うには、ここで、new_nodeに等しい。 JASONハーシュホーン：ヘッド ここで、new_nodeに等しい。 そして、なぜ表示されませ、ここに向かう？ 観客：頭がグローバルであるため 出発点である変数、。 JASONハーシュホーン：甘い。 [OK]をクリックします。 そして - 観客：次に、あなたが他の何前のページ - > 次のここで、new_nodeは等しくなります。 そして、あなたはtrueを返します。 JASONハーシュホーン：DO 我々はここで、new_node終わりを設定されていますか？ 読者：私はでしょう - 私は、開始時にそれを設定してください。 JASONハーシュホーン：だから何行？ 読者：IF文の後 それが知られているかどうかをチェックする。 JASONハーシュホーン：右ここに？ 読者：私は何をしたいで、new_node-> N 値に等しい。 JASONハーシュホーン：良さそうですね。 おそらくそれは理にかなっている - 私たちにはありません 私たちがしているものをリスト知っておく必要があります 我々は扱っているので、 1リストで。 のためのとても優れた関数宣言 これはちょうどこのを取り除くことです 完全に、ちょうど挿入 頭に値。 私たちも知っている必要はありません 我々はインチているもののリスト しかし、私は今のためにそれを維持します その後、更新の際にそれを変更 スライドとコード。 だから、今のよさそうだ。 場合には、値 - この行を行うことができますか？ もし - 私たちは、ノアは、ここで何をしますか。 観客：値が大きい場合 Nゴロゴロ - >より - JASONハーシュホーン：どうすれば 我々は次のノードに行く？ 観客：CURR-> nは ここで、new_nodeに等しい。 JASONハーシュホーン：だからnは 構造体のどの部分？ 整数。 そしてここで、new_nodeは、ノードへのポインタである。 だから我々はゴロゴロのどの部分を更新する必要がありますか？ そうでなければnを指定すると、他の部分は何ですか？ ノア、他の部分は何でしょう。 観客：ああ、次の。 JASONハーシュホーン：次に、その通りです。 その通りです。 次の右の1である。 そして、我々は他に何が必要なのですか 、ノアを更新する？ 観客：ポインタ。 JASONハーシュホーン：だから 我々は現在を更新しました。 観客：前のページ - >次。 JASONハーシュホーン：うん。 [OK]を、我々は一時停止します。 誰がここに私たちを助けることができますか？ マヌー、我々は何をすべきか？ 読者：あなたが設定するんだ ゴロゴロ - >次に等しいこと。 しかし、前の行の前にそれを行う。 JASONハーシュホーン：わかりました。 何か他には？ Akshar。 読者：私はあなたがいるとは思わない ゴロゴロ - > [次へ]を変更することを意味した。 私はあなたがゴロゴロ等号を行うことを意図していると思う ゴロゴロ - >次のノードに移動]の横にある。 JASONハーシュホーン：だから申し訳​​ありませんが、どこで？ 何行に？ この行は？ 観客：うん。 ゴロゴロがゴロゴロ - >次に等しいことを確認します。 JASONハーシュホーン：だからそれは正しいです 電流があるため、 ノードへのポインタ。 そして、我々はそれが次のを指すようにしたい 現在なってきたもののノード を指摘した。 ゴロゴロ自体は、次のを持っています。 しかし、我々はcurr.nextを更新した場合、我々は 実際のノートを更新することになる それ自体ではなく、ここ ポインタが指していた。 何でも、この行について。 AVI？ 観客：前のページ - >次のゴロゴロに等しい。 JASONハーシュホーン：だから、もう一度、前の場合はA ノードへのポインタ、前へ - >次です ノード内の実際のポインタ。 だから、これは更新されます ゴロゴロノード内のポインタ。 我々は更新しない ノード内のポインタ。 我々は前回の更新したいと思います。 だから我々はそれをどのように行うのですか？ 観客：それはちょうど前のことになる。 JASONハーシュホーン：右。 前のノードへのポインタである。 今、私たちは、それを変更している ノードへの新しいポインタ。 [OK]を私たちは下に移動してみましょう。 最後に、この最後の条件。 ジェフは、我々はここで何をしますか？ 観客：値がある場合 ゴロゴロ - > Nに等しい。 JASONハーシュホーン：申し訳ありません。 善良私のオハイオ州。 何が？ 値==ゴロゴロ - > N。 私たちは何をしますか？ 読者：あなたは私たちで、new_nodeを解放したい、 そして、あなたはfalseを返すと思います。 JASONハーシュホーン：これは何であるか 我々はこれまでに書かれている。 誰も何も持っていますか 我々が作る前に追加するには？ [OK]をクリックします。 やってみよう。 コントロールが最後に到達する可能性 void以外の関数の。 AVI、何が起こっているの？ 読者：あなたはリターンを置くことになっている whileループの外に本当？ JASONハーシュホーン：私は知らない。 あなたは私をしたいですか？ 観客：気にしないで。 いいえ。 JASONハーシュホーン：Akshar？ 読者：私はあなたがする意味と思う 最後にfalseを返す入れる whileループの。 JASONハーシュホーン：だからここで あなたはそれが行きたいですか？ 読者：whileループの外のように。 だから、その手段には、whileループを終了した場合 あなたが最後に到達したことと、 何も起こらなかっただ。 JASONハーシュホーン：わかりました。 だから我々はここで何をしますか？ 読者：あなたはfalseを返す そこにも。 JASONハーシュホーン：ああ、私たち 両方の場所でそれを行う？ 観客：うん。 JASONハーシュホーン：わかりました。 私達は行くべきでしょうか？ 善良私のオハイオ州。 ごめんなさい。 私は、画面をおかけして申し訳ございません。 それは、私たちに怖がらのようなものだ。 だから、オプションを選択します。 ゼロは、コードごとに、プログラムを終了します。 一つは、何かを挿入します。 それでは3を挿入してみましょう。 インサートは成功しませんでした。 私はプリントアウトするつもりです。 私は何も持っていません。 [OK]をクリックします。 多分それはちょうどまぐれだった。 1を挿入します。 成功していない。 [OK]をクリックします。 それでは本当にすぐに、GDBを介​​して実行しましょう 何が起こっているかをチェックします。 あなたのGDBを覚えています。/名 プログラムは、GDBに私たちを取得します。 たくさん処理するということです？ 明滅していますか？ 多分。 目を閉じて、いくつかの深いを取る あなたは疲れている場合呼吸 それを見ての。 私は、GDBにいるよ。 私は、GDBで最初に行うことは何ですか？ 我々は把握するんだ ここで何が起こっている。 見てみましょう。 私たちは、図のように6分を持っている 何が起こっているか。 主に折り返されます。 そして私は何をしますか？ カルロス·？ 実行します。 [OK]をクリックします。 のオプションを選択してみましょう。 とN何をするのでしょうか？ 次へ。 うん。 読者：あなたは言及しなかった - あなたは頭が、それがあったことを言わなかった 先頭にnullに初期化されます。 しかし、私はあなたがそれがOKと言ったと思った。 JASONハーシュホーン：行きましょう - それでは見てみましょう GDBにし、私たちは戻って行きます。 しかし、あなたはすでに持っているように聞こえる 何が起こっているかについていくつかのアイデア。 だから我々は何かを挿入したい。 [OK]をクリックします。 私たちは、挿入している。 int型を入力してください。 我々は3を挿入します。 そして私は、この行によ。 どのようにしてデバッグを開始する行くのですか インサートは、機能の公知？ 善良私のオハイオ州。 それはたくさんある。 多くのことを怖がらことですか？ 観客：ああ、それは死んだ。 JASONハーシュホーン：ちょうど私 それを取り出した。 [OK]をクリックします。 観客：多分それはだ 線のもう一方の端。 JASONハーシュホーン：うわー。 だから、一番下の行 - 何て言ったの？ 読者：私は言った技術的の皮肉 このクラスの難しさ。 JASONハーシュホーン：私は知っている。 場合にのみ、私はその部分を制御していた。 [聞こえない] それは素晴らしいサウンド。 なぜあなたたちは考えて起動しない 我々は間違って行ったかもしれないもの、 そして我々は戻って90秒になります。 Avica、私はどのように行くをお願いするつもりです それをデバッグする内部insert_node。 我々は最後の中断したところにするためです。 どのように私はinsert_node、Avica内側に行くのですか、 何が起こっているのか調べるために？ どのようなGDBコマンド？ ブレークは内部の私を取らないだろう。 マーキスは知っていますか？ 観客：何？ JASONハーシュホーン：どのようなGDBコマンド 私は、この関数の中で行くことに使うのか？ 観客：ステップ？ JASONハーシュホーン：経てステップ 内部の私を取るS.。 [OK]をクリックします。 いくつかの領域をmallocingで、new_node。 すべては行くようになっていること。 それではここで、new_nodeを調べてみましょう。 これは、いくつかのメモリ·アドレスを得た。 それでは確認してみましょう - つまり、すべて正しい。 だからここにすべてがいるようだ 正しく動作して。 観客：違いは何ですか Pとディスプレイとの間に？ JASONハーシュホーン：Pは、印刷の略です。 だからあなたは何を求めている その本の違いは？ この場合は、何もない。 しかし、一般的に存在する いくつかの違い。 そして、あなたは、GDBのマニュアルになっているはずです。 しかし、この場合は、何もない。 我々は、しかし、印刷を使用する傾向があるので、 我々はより多くを実行する必要はありません 単一の値を印刷します。 [OK]をクリックします。 だから我々は、我々のコードの行80にある リストに等しいノード*のCURRを設定。 私たちがゴロゴロをプリントアウトしてみましょう。 これは、リストに相当します。 甘い。 待つ。 それは何かと等しい。 それは正しいていないようです。 そこに私達は行く。 GDBで、右のであれば、だ それはあなたがそれにしているラインです まだ実行されていません。 だから、実際に入力する必要が 行を実行するために、次の その結果を見てください。 そこでここでは、ある。 私達はちょうどこの行を実行する、 以前はNULLに等しくなります。 だからもう一度、私たちは前の印刷した場合 私たちは奇妙な何も表示されません。 しかし、我々は実際にそれを実行した場合 ライン、そして我々が表示されます その行が働いたことを。 だから我々はゴロゴロしています。 それらは両方の良いです。 右？ 今、私たちはここ、この行にしている。 ゴロゴロが同じヌルをしていませんが。 さて、ゴロゴロ等しい何でしょうか？ 我々はちょうどそれがnullで等しかった。 我々はそれをプリントアウト。 私は再びそれをプリントアウトします。 そうです、そのwhileループ 実行しよう？ 観客：いいえ。 JASONハーシュホーン：だから私は、その入力された 行すると、我々はすべての方法をジャンプ参照してください。 一番下まで、falseを返します。 そして、我々は、falseを返すつもりだ 私たちのプログラムに戻って、 我々が見たように、最終的には、プリントアウトし、 インサートは成功しませんでした。 だから、誰が何の上の任意のアイデアを持っている 我々はこれを修正するために必要？ 私が表示されるまで待つつもりだ 手のカップルは上がる。 我々はこれを実行されませんでした。 覚えておいて、これが最初だった 私たちはやっていた事。 私はカップルをやるつもりはない。 私はいくつかをするつもりです。 カップルが2を意味するので。 私は以上の2のために待っています。 第一の挿入、ゴロゴロ、 デフォルトではNULLに等しくなります。 このループは実行され ゴロゴロがnullでない場合。 だから、どうやってこの問題を回避することができますか？ 私は3の手を参照してください。 私は以上の3のために待っています。 マーカス、あなたはどう思いますか？ 観客：さて、あなたはそれを必要とする場合に 複数回実行するだけで DO-whil​​eループに変更します。 JASONハーシュホーン：わかりました。 それはしかし、我々の問題を解決するのだろうか？ 読者：この場合、何のためにしない リストが空であるという事実。 だから、あなたはおそらくだけ追加する必要があります if文ループが終了すること その後、終了時にする必要が あなたを、その時点でリスト、 ちょうどそれを挿入することができます。 JASONハーシュホーン：私はそれが好きです。 それは理にかなっています。 ループが終了した場合 - それがここにfalseを返すだろうから。 だから、ループが終了した場合、我々はにいる 多分リストの最後、または 中の何もない場合は、リストの先頭 終わりにすることと同じであり、。 だから今我々は、挿入したい ここで何か。 それでは、どのそのコードは、マーカスが見えますか？ 読者：あなたはすでにノードを持っている場合 mallocさ、あなただけの言うことができる ここで、new_node->次のため、ヌルに等しい それが最後である必要があります。 あるいはここで、new_node->次のヌルに等しい。 JASONハーシュホーン：わかりました。 申し訳ありません。 ここで、new_node->次のヌルに等しい 我々は最後にだから。 つまり、それをインチ入れていません どのように我々は、リストに入れていますか？ 右。 それはちょうど等しく、それを設定することです。 実際にどのように我々はありません リストに入れて？ を指しているのか リストの最後に？ 観客：ヘッド。 JASONハーシュホーン：申し訳ありませんが？ 観客：頭を指している リストの最後に。 JASONハーシュホーン：何もでがない場合 リスト、ヘッドはを指している リストの最後。 だからために働くよ 第一の挿入。 いくつかありますかについてあれば リストにあるもの？ 我々は設定しないよりも、 ここで、new_nodeに等しい頭。 我々はそこに何をすべきかをしたいですか？ うん？ おそらく以前の。 それは動作しますか？ 以前はただであることを思い出してください ノードへのポインタ。 そして以前はローカル変数です。 したがって、この行は、ローカル変数を設定します、 、前回と同じか、 この新しいノードを指す。 つまり、実際にそれを置くことはありません 私たちのリストにある、しかし。 どのように我々は私たちのリストに入れていますか？ Akchar？ 読者：私はあなたを思う 次の電流 - >を行います。 JASONハーシュホーン：わかりました。 ゴロゴロ - >次。 だからもう一度、私たちがダウンしている唯一の理由 ここに等しい電流が何です？ 観客：ヌル等しい。 JASONハーシュホーン：だから何 我々は次のヌル->を行う場合はどうなりますか？ 我々は、取得するつもりですか？ 私たちは、セグメンテーションフォールトを取得します。 読者：飲酒CURRがnullに等しい。 JASONハーシュホーン：それは同じことだ 前のように、しかし、そこだから 我々は設定しているローカル変数 この新しいノードに等しい。 私たちの絵に戻りましょう 何かを挿入する。 我々は最後に挿入していると言う リストのため、まさにここ。 私たちは、の現在のポインタを持っている nullにポイントして、前のポイント つまり、8を指しています。 それでは我々は、AVIを更新する必要がありますか？ 観客：前 - >次は？ JASONハーシュホーン：前 - >次は何がある 我々はそのため更新する 実際にそれを挿入します リストの最後。 我々はまだ、しかし、1バグを持っている 我々はに実行するつもりという。 そのバグは何ですか？ うん？ 観客：それは返すために起こっている この場合、偽？ JASONハーシュホーン：ああ、あるさ falseを返しに行く。 しかし、別のバグがあります。 だから我々は真のお返しに配置する必要があります。 観客：か前のまだ等しい リストの一番上にはnull？ JASONハーシュホーン：だから前の、まだ 先頭にヌルに等しい。 では、どのようにそれを乗り越えることができますか？ うん？ 読者：私はあなたがチェックを行うことができると思います それはだ場合は、whileループを確認します前に、 空のリスト。 JASONハーシュホーン：わかりました。 それでは、ここに行きましょう。 チェックを行う。 もし - 観客：そうであればヘッド ヌルに等しい等しい。 JASONハーシュホーン：もし頭 ヌルに等しい等しい - それは、空のリストだ場合には、私たちに教えてあげましょう。 観客：それから、あなた 何頭が新たに等しい。 JASONハーシュホーン：ヘッド ここで、new_nodeに等しい？ そして他に何私たちは何をする必要があります？ 観客：それから、あなたはtrueを返します。 JASONハーシュホーン：非常にされていません。 私たちは、一歩を逃している。 読者：ここで、new_node次の NULLを指しています。 JASONハーシュホーン：その通り、オールデン。 そして、我々は真を返すことができます。 [OK]をクリックします。 しかし、それはまだ物事を行うことをお勧めします リストの最後に、右か？ わかりました。 我々はまだ実際に得るかもしれない リストの最後に。 我々がしているのであれば、このコードの罰金です リストの最後といくつかあります リストにあるもの？ 右？ 我々はまだマーカスのアイデアを持っているので。 我々は、理由このループを終了することがあり 私たちは、リストの最後にいる。 だから我々はまだこれをしたいですか ここでダウンしてコーディングする？ 観客：はい。 JASONハーシュホーン：うん。 そして、我々は、これを変更するには何が必要ですか？ 真。 ないことを、音の良い 誰もがこれまでのところ？ 誰もがいずれかを持っている - aviファイルは、あなたが追加したいアイテムがありますか？ 観客：いいえ。 JASONハーシュホーン：わかりました。 だから我々はいくつかの変更を加えました。 我々は、我々の前に、このチェックを作りました 空のリストについては、中行ってきました。 だから我々は空のリストの世話をしてきました。 そしてここでは、挿入の世話をした リストの最後に何か。 だから、このwhileループの撮影のように思える 間にあるものの世話、 リスト内のどこかにある場合があり リスト中のものがあります。 [OK]をクリックします。 私たちはもう一度、このプログラムを実行してみましょう。 成功していない。 読者：あなたはそれをしなかった。 JASONハーシュホーン：ああ、 私はそれをしなかった。 良い点、マイケル。 の、リンクされたメイクを追加してみましょう。 ライン87にエラーがあります。 ライン87。 オールデン、これはあなたが私を与えたラインだった。 何が気に入らないのだ。 観客：それはnullにしなければならない。 JASONハーシュホーン：優秀。 まったく正しい。 それはNULLでなければなりません。 それでは、もう一度作ってみましょう。 コンパイルします。 [OK]をクリックします。 それでは3を挿入してみましょう。 挿入に成功しました。 のは、それをプリントアウトしてみましょう。 ああ、我々は確認できた場合に限ります。 しかし、我々は行っていない まだ印刷機能。 それでは何か他のものを入力してみましょう。 私たちは何を入力するべきか？ 観客：セブン。 JASONハーシュホーンセブン？ 観客：はい。 JASONハーシュホーン：私たちはワンセグ障害を持っている。 だから我々は1つを得たが、我々を明確に 2を取得することはできません。 それが午前5時07分です。 だから我々はこれをデバッグすることができ 3分間。 しかし、私はここで私たちを残しするつもりだ とハッシュテーブルに移動します。 しかし、再び、このコードのための答え 私は少しであなたにそれをメールでお知らせいたします。 我々はそれに非常に近い。 私は非常に把握することをお勧めします 何がここで起こって、それを修正だ。 だから、私はあなたにこのコードをメールでお知らせいたします よくプラスソリューション - おそらく後でソリューション。 最初にこのコード。 私は、私たちの前にやってみたい他の事 仕上げは、我々は何も解放されていないです。 だから私はあなたに何を表示したい Valgrindのは次のようになります。 私たちは、Valgrindの境界を実行すると 私たちのプログラムで、。/リンク。 繰り返しますが、このスライドによると、我々 いくつかのタイプのValgrindのを実行する必要があります この場合はオプション、 - =フル漏れをチェックします。 それでは、Valgrindのを書いてみましょう - =フル漏れをチェックします。 だから、これはValgrindのを実行します 私たちのプログラムに。 そして今、プログラムが実際に実行されます。 だから我々は同じようにそれを実行しようとしている 前、インチ何かを置く 私は3に置くつもりです。 それが動作します。 私は何かに配置しようとするつもりはない 他に、我々はするつもりだので、 その場合、ワンセグ偽を得る。 だから、僕はやめるつもりです。 そして今、あなたはここでダウンして参照してください。 リークとヒープの要約。 これらは良いものであることを あなたがチェックアウトしたい。 だから、ヒープの要約 - それが言う、使用中 出口で - 1ブロックの8バイト。 その1ブロックです ノード我々はmallocさ。 ノードが8である前に言ったマイケル、 それは、整数を持っているので刺さ ポインタ。 だから、私たちのノードの。 そして、それは我々がmalloc関数を使っ言う 我々は解放された7回 何か6回。 しかし、我々は自由と呼ばれたことがないので、私は持っていない これが何について話しているのか考え。 しかし、そのときに言えば十分 プログラムが実行され、malloc関数が呼び出されている その我々いくつかの他の場所で 心配する必要はありません。 だから、malloc関数は、おそらくと呼ばれていた いくつかの場所で。 我々はどこに心配する必要はありません。 しかし、これは本当に私たちである。 この最初の行は私たちです。 私たちは、そのブロックを残しました。 そして、あなたはそのここで見ることができます リーク要約する。 まだ到達 - 1ブロックの8バイト。 つまり、そのメモリを意味します - 私たちは、そのメモリをリークしています。 確かに失われた - 何かは永久に失われます。 一般的には、あなたではないでしょう そこには何も表示されます。 まだ到達は一般的です あなたが欲しいよなものを、表示されます どのようなコードを使用するとすべき見ることに目を向ける 解放されていますが、解放するのを忘れています。 そして、これは、そうではありませんでした場合は、 我々は自由なすべてをした場合には、 我々はそれを確認することができます。 ちょうどプログラムを実行してみましょう 何を入れていない。 あなたが出口で、ここで使用されているダウン表示されます - ゼロブロック内のゼロバイト。 それは我々が何も残っていなかったことを意味 このプログラムは終了したとき。 そうpset6に電源を入れる前に、valgrindのを実行する そしてあなたが持っていないことを確認してください 任意のメモリは、プログラム内でリークが発生します。 あなたはValgrindので不明な点がございましたら、 手を差し伸べるお気軽に。 しかし、これはあなたがそれを使用する方法である。 非常に単純な - あなたかどうかを確認 出口で使用されている - 任意のブロック内の任意のバイト。 だから我々は、挿入ノード上で作業していた。 私はここ2他の機能を持っていた - ノードと自由なノードを印刷します。 再度、これらは関数である あなたが練習するために良いことになるだろう 彼らはだけでなく、あなたを助けるとなるため、 これらのサンプルの練習だけでなく、 問題に設定してください。 彼らは物事にかなり密接に地図 あなたがで行う必要があるとしている 問題は、設定してください。 しかし、私は確認したいです 我々はすべてのものに触れる。 ハッシュテーブルも非常に重要である 我々はここでこれを何をやっている 週 - または問題セット中。 だから我々は、セクションを終了しようとしている ハッシュテーブルの話。 あなたが気づけば私が作​​ら 小さなハッシュテーブル。 それは我々が話しているものではありません しかしながら、約。 我々は、さまざまな話をしている ハッシュテーブルのタイプ。 そして、そのコア、ハッシュテーブルで 以外の何ものでもありません 配列プラスハッシュ関数。 我々だけに少しのために話をするつもりだ 誰もが何Aを理解し確認してください ハッシュ関数である。 そして私はそれがあることを今、あなたの言っている 二つのこと以外の何物でもない - 配列とハッシュ関数。 そして、ここでの手順は、通っている これはどのように動作する。 私たちの配列があります。 私達の機能があります。 具体的には、ハッシュ関数を実行する必要があり これで物事のカップルを行う。 私は、特に話をするつもりだ については、この問題は、設定してください。 それはおそらくだろう 文字列になります。 そして、何それは返すために起こっているの？ どのようなデータ型？ オールデン？ あなたのハッシュ関数の戻り？ 整数。 だから、これはどのようなハッシュです 表には、で構成されています - 配列の形式で表 ハッシュ関数。 それはどのように動作します？ これは、3段階で動作します。 我々はそれにキーを付けます。 この場合、我々はそれを文字列を与えるでしょう。 我々はステップ1あたりのハッシュ関数を呼び出す キーに、我々は値を取得します。 具体的には言うよ 我々は、整数を取得します。 その整数は、非常に特殊な存在 その整数ができるものに制限されます。 この例では、我々のアレイ サイズ3のものである。 だから、その整数は何の数字をすることができます。 の有効な値の範囲は何ですか その整数は、このコマンドの戻り値の型 関数をハッシュ？ ゼロ、1および2。 ハッシュ関数のポイントがある 配列内の場所を把握 ここで私たちのキーが起こっている。 唯一の3つの可能性があります。 ここの場所 - ゼロ、1、または2。 そのため、この機能は、より良いリターン ゼロ、1、または2。 この配列内のいくつかの有効なindice。 そして、それが返す場所に応じて、 あなたが開いて、配列を確認することができます 値を一括。 我々は、キーを置く場所です。 だから我々は、カボチャを投げる、 我々はゼロを出す。 アレイ·ブラケット0で、我々はカボチャを置く。 我々は1を出す、猫を投げる。 我々は1で猫を置く。 私たちは、クモに置く。 我々は2つ​​を出す。 我々は、アレイブラケット2でクモを置く。 それは、もしそうであればいいだろう それはそのように働いた。 残念ながら、我々は、表示されますように それは少し複雑です。 我々は、そこにどんな質問を受ける前に、 この基本について ハッシュテーブルのセットアップ？ これはまさにのイメージです 我々は、ボード上で描いたものを。 しかし、我々は、ボード上のIそれを描いたので、 さらにそこに行くつもりはありません。 基本的にキー、魔法のブラックボックス - あるいはこの場合は、ティールボックス - の ハッシュ関数は、バケットに格納します。 そしてこの例では、ね ネーム入れはできません。 私たちは、関連付けられている携帯電話を入れている バケット内の名前の数。 しかし、あなたは非常によくできただけで バケツに名前を入れ。 これは何のちょうど写真です 我々は、ボード上で描きました。 我々は、しかし、潜在的な落とし穴があります。 そして二人は特にあり 私は上の行きたいことをスライドさせる。 最初の1程度である ハッシュ関数。 だから私は、質問を何 良いハッシュ関数を作る？ 私は2つの答えを与える。 最初は、それが決定論的であるということです。 ハッシュ関数の文脈において、 これは何を意味するのでしょうか？ はい？ 観客：それは見つけることができます 一定の時間内のインデックス？ JASONハーシュホーン：それ それが何を意味するのかではありません。 しかし、それは良いの推測だ。 誰が推測してい これが何を意味する？ その優れたハッシュ関数 決定論的である？ アニー？ 観客：キーのみをマッピングすることが可能であること。 ハッシュテーブル内の1位に。 JASONハーシュホーン：それです。 まったく正しい。 あなたは、カボチャを入れたびに、 それは常にゼロを返します。 あなたは、カボチャとあなたのハッシュに入れた場合 関数はゼロを返しますが、持って 何かを返す確率 ゼロより誰より - ので、多分それは時々1を返すことができます または2他の回 - それは良いハッシュ関数ではありません。 あなたは正確に正しい。 あなたのハッシュ関数は、返す必要があります この場合は、同じ正確な整数、用 まったく同じ文字列。 多分それは、同じ正確な整数を返します。 まったく同じ文字列の にかかわらず、時価総額の。 しかし、その場合、それはまだだ 確定的なので、複数の事 同じ値にマッピングされます。 それはいい。 限りつだけが存在するように 与えられた入力に対する出力。 [OK]をクリックします。 2つ目は、それ 有効なインデックスを返します。 我々は、以前育てた。 このハッシュ関数 - ああ - ハッシュ機能するはず 有効なインデックスを返す。 そう言う - のは、この例に戻りましょう。 私のハッシュ関数は、カウントアップ 単語の文字。 つまり、ハッシュ関数です。 そして、その整数を返します。 私は言葉のAを持っているのであれば、それはだ 1を返すつもり。 そしてそれは、ここで権利を置くために起こっている。 私は単語のバットに入れたら？ それは3を返すために起こっている。 バットはどこに行くのでしょうか？ それは適合しません。 しかし、それはどこかに行く必要がある。 これは結局、私のハッシュテーブルであり、 すべてがどこかに行く必要がある。 だからここでバットを行くべき？ 任意の考え？ 推測？ 良い推測？ 観客：ゼロ。 JASONハーシュホーン：なぜゼロ？ 観客：3ので、 モジュロ3はゼロです？ JASONハーシュホーン：スリー モジュロ3はゼロです。 それは素晴らしいの推測ですが、 それは正しいです。 したがって、このケースでは、べき おそらくゼロに行く。 、このハッシュを確実にするので、良い方法 関数は、有効なインデックスを返している テーブルのサイズによって、それを法である。 あなたはどのようなことで、この戻り値を法場合 3、あなたは常に取得するつもりだ ゼロ、1、および2の間に何か。 そして、これは常に7を返し、あれば あなたはいつもあなたがしている、3でモジュロ いつも同じものを手に入れるつもり。 だから、まだ確定的だ あなたは法とする場合。 しかし、それは、あなたことを保証します 何かを得ることはありません - 無効な業界。 一般的に、モジュロが起こるべきであること あなたのハッシュ関数の内部。 だから、このことを心配する必要はありません。 あなただけのことを確認することができます これは有効なindiceです。 この上の任意の質問 潜在的な落とし穴？ [OK]をクリックします。 そしてそこに私達は行く。 次の潜在的な落とし穴、および これは大きなものです。 どのような場合、2つのキーマップ 同じ値に？ だから、これを処理する2つの方法があります。 最初の1は、リニアと呼ばれている 私はこれ、プロービング 以上行くつもりはない。 しかし、あなたはどのように精通している必要があります それが動作し、どのようなものがある。 私は以上行くつもり秒1 それは多くの1であるため、 人々は、おそらく決定することになります 彼らの問題のセットで使用する。 もちろん、あなたがする必要はありません。 しかし、問題のセット、多くの人々のため ハッシュテーブルを作成することを選択する傾向がある 実装するために別々の連鎖で 彼らの辞書。 だから我々はそれが何を意味するのか上に行くつもりだ と、ハッシュテーブルを作成する 別々の連鎖。 だから私は、カボチャを入れ。 これは、0を返します。 そして、私はここにカボチャを置く。 それから私は、中に入れ - 別のハロウィーンをテーマにした事は何ですか？ 観客：キャンディ。 JASONハーシュホーン：キャンディ！ それは素晴らしい1です。 私はキャンディー、キャンディーを入れ また、私にはゼロになります。 私は何をしますか？ 任意のアイデア？ あなたはすべての種類の知っているので、 どのような別々の連鎖である。 そのためにはどのような任意のアイデア？ うん。 観客：文字列を置く 実際にハッシュテーブルに。 JASONハーシュホーン：だから我々はするつもりだ こっち良いアイデアを描く。 [OK]をクリックします。 観客：ハッシュテーブルを持っている [聞こえない] を指すポインタ リストの先頭。 した後、カボチャは最初の値である必要な そのリンクリストやキャンディーであること そのリンクリストの2番目の値。 JASONハーシュホーン：わかりました。 傑出していたマーカス、。 私はそれを打破するつもりです。 マーカスはしないでくださいと言っている カボチャが上書きされます。 それは悪いでしょう。 どこか別のお菓子を入れないでください。 我々はゼロでそれらの両方を置くつもりです。 しかし、我々は対処するつもりだ ゼロでそれらを置くこと ゼロからリストを作成する。 そして、我々はリストを作成しましょう ゼロにマップされたすべてのもの。 そして、我々は作ることを学んだ最良の方法 成長し、縮小することができ、リスト 動的内にない 別の配列。 そうではない多次元配列。 しかし、単にリンクされたリストを作成します。 それでは、彼が提案した - 私は新しいを取得するつもりだ - ポインタを持つ配列を作成することです、 ポインタの配列。 [OK]をクリックします。 どのようなタイプの任意のアイデアやヒント このポインタでなければならない？ マーカス？ 観客：へのポインタ - JASONハーシュホーン：あなたので、 リンクリストは言ったので - 読者：ノードポインタ？ JASONハーシュホーン：ノードポインタ。 もし私たちのリンクにあるもの リストそれらのノードである ノードポインタでなければなりません。 そして、彼らは、最初は何を等しくしますか？ 観客：ヌル。 JASONハーシュホーン：ヌル。 だから私たちの空の事があります。 カボチャは、ゼロが返されます。 私たちは何をしますか？ それを通して、私を歩く？ 実際に、マーカスは既に私を与えた。 他の誰かがそれを介して、私を歩く。 我々は何をすべきかときに我々 - これは非常によく似ています 我々だけで何をしていた。 AVI。 読者：私は推測を取るつもりです。 だから、お菓子を取得するとき。 JASONハーシュホーン：うん。 まあ、我々は、カボチャを得た。 私たちの最初のものを取得してみましょう。 私たちは、カボチャを得た。 観客：[OK]をクリックします。 カボチャは、ゼロが返されます。 だから、それに入れて。 または実際に、あなたがそれを置く リンクされたリストの中。 JASONハーシュホーン：どのように我々は何 リンクされたリストに入れて？ 観客：ああ、実際の構文？ JASONハーシュホーン：ただ歩く - より多くを語る。 私たちは何をしますか？ 読者：あなただけの挿入 最初のノードとして。 JASONハーシュホーン：わかりました。 だから我々は我々のノード、カボチャを持っている。 そして今、どのようにそれを挿入しますか？ 観客：割り当てる ポインタへのそれ。 JASONハーシュホーン：ポインタ？ 観客：ゼロにポインタ。 JASONハーシュホーン：だからここで この点はいますか？ 観客：今NULLに。 JASONハーシュホーン：まあ、 それがnullを指しています。 しかし、私はかぼちゃに入れている。 だからここでそれが指している必要があります？ 観客：カボチャへ。 JASONハーシュホーン：カボチャへ。 その通りです。 だから、これはカボチャを指しています。 どここのポインタはない カボチャ点？ へ 観客：ヌル。 JASONハーシュホーン：nullに。 その通りです。 だから我々は、単に何かを挿入 リンクされたリストに変換する。 我々だけでこれを行うには、このコードを書いた。 ほとんど我々はほとんどそれを得た 完全に割れた。 今、私たちはお菓子を挿入します。 私たちのキャンディーもゼロになる。 だから我々は、キャンディで何をしますか？ 観客：それはどうかに依存します 我々はそれを並べ替えしようとしていない。 JASONハーシュホーン：それです。 まったく正しい。 か否かに依存する 我々はそれを並べ替えしようとしている。 のは、我々はわからないとしましょう それをソートするために行く。 観客：それでは、私たちが説明したように 以前は、それだけでそれを置くのが最も簡単です 右ポインタので、先頭に ゼロポイントからキャンディへ。 JASONハーシュホーン：わかりました。 少々お待ちください。 私はここお菓子を作ってみましょう。 そのため、このポインター - 観客：ええ、今すべき キャンディーを指している。 その後のポインタを持っている カボチャのお菓子のポイント。 JASONハーシュホーン：そのような？ そして、我々は別のものを得たと言う ゼロにマップすることは？ 観客：さて、あなただけの 同じことをする？ JASONハーシュホーン：同じことを行う。 したがって、このケースでは、ない場合は それは、それを並べ替えておきたい むしろ簡単に聞こえる。 我々はindice内のポインタを取る 我々のハッシュ関数によって与えられる。 私たちは、新しいノードにそのポイントを持っている。 そして、それが指していたどのような 以前まで - この場合はNULLを、中 第二ケースカボチャ - それが指しているものは何でも、その 以前、我々は次のに追加 私たちの新しいノード。 私たちは、何かを挿入している 初めに。 実際にはこれよりもずっと簡単です。 ソートされたリストを維持しようとしています。 しかし、再び、検索はなり もっとここに複雑。 我々は常に末尾に移動する必要があります。 [OK]をクリックします。 別々の連鎖についてのご質問？ どのようにそれが動作します？ ここでそれらを依頼してください。 私は実際に確認し、すべてのようにしたい 我々は出掛ける前にこれを理解しています。 観客：なぜあなたは、カボチャを入れない と同じにキャンディー ハッシュテーブルの一部？ JASONハーシュホーン：良い質問。 なぜ我々は同じに入れない ハッシュテーブルの一部？ さて、この場合の当社のハッシュ関数 リターンはそれらの両方のためのゼロ。 そこで、彼らはindiceゼロに行く必要がある 我々はするつもりだところですので、 彼らのために見てみると、我々今までに それらを見てみたい。 再び、リニアプロービング手法に 我々はゼロからそれらの両方を入れないでしょう。 しかし、別々の連鎖アプローチでは、 我々はゼロでそれらの両方を置くつもりだ そして、ゼロのオフリストを作成します。 そして、我々はカボチャを上書きしたくない 単にそのため、我々はだろうから カボチャであったことを前提とし 挿入されたことはありません。 私達はちょうどで一つのことを続けると 悪いことする場所。 [いいえがあるだろう 今まで私たちの可能性 - 私たちが今まで重複していたなら、私たち ちょうど私たちの初期値を消すだろう。 我々はこのアプローチをなぜだからです。 またはそれは我々が選んだ理由だ - しかし、繰り返しますが、私たち 別々の連鎖的なアプローチを選択しました、 これは多くの他のアプローチがあります 1が選択できます。 それがあなたの質問に答えるのでしょうか？ [OK]をクリックします。 カルロス。 リニアプロービングが伴うだろう - 我々はゼロからの衝突を発見した場合、我々は かどうかを確認するために次のスポットになります それが開いていたし、そこにそれを置く。 そして、我々は次のスポーツで見て、 それが開いていたかどうかを確認し、そこにそれを置く。 だから我々は、次の利用可能なを見つける。 オープンスポットとそこに置く。 その他のご質問は？ AVI、うん。 観客：それのフォローアップとして、 あなたは次のスポットとはどういう意味ですか？ ハッシュテーブル内またはリンクされたリストにある。 JASONハーシュホーン：リニア プログラミングなしリンクされたリスト。 ハッシュテーブルの上に次のスポット。 観客：[OK]をクリックします。 だから、ハッシュテーブルは次のようになります。 サイズに初期化 - 文字列の数のように あなたが挿入されたこと？ JASONハーシュホーン：あなたでしょう それは本当に大きなことをしたい。 はい。 ここに私たちの写真です ただボードに描きました。 繰り返しますが、私たちはここの衝突を持っている。 152で。 そして、あなたは私たちが作成した表示されます それをオフにリンクされたリスト。 ここでも、ハッシュテーブルの別々の連鎖 アプローチは、1あなたではありません 設定の問題のために取らなければならない 6しかし、一つであることが多く 学生が取る傾向があります。 だから、そのノートに、私たちは簡単に説明しましょう 私たちは、問題6について出掛ける前に、 そして私はあなたと話を共有します。 私たちは、3分している。 問題は、6を設定します。 あなたは、4つの機能を持っている - 負荷、サイズを確認し、アンロードします。 負荷 - さて、私たちは続けられてきた 過負荷ちょうど今。 我々は、ボード上の負荷を描きました。 そして私たちも、多くのコーディング開始 リンクされたリストに挿入。 だから、負荷がよりもはるかに多くはありません 我々だけで何をしてきた。 あなたがしたらチェックがある 何かがロードされた。 それは、これと同じプロセスです。 あなたが投げる同じ第2の部分 ハッシュ関数に何か し、その値を取得します。 しかし、今我々はそれを挿入していない。 今、我々はそれを探しています。 私は見つけることのために書かれたサンプルコードを持っている リンクされたリストの中で何か。 私はそれを実践することをお勧めします。 しかし、直感的に何かをされている発見 何かを挿入するにはかなり似ています。 確かに、我々は見つけることの絵を描いた リンクされたリストの中で何か、移動 あなたが最後に到着するまでを通して。 そして、あなたが最後になったし、できなかった場合 それを見つける、それはそこではありません。 だから、基本的には、チェックだ。 次のサイズです。 のサイズを飛ばしてみましょう。 最後に、アンロードしています。 アンは、我々が描かれていないものです ボード上のか、まだコード化された。 しかし、私はそれをコーディングしようとすることをお勧めします このサンプルリンクリストの例では。 しかし、直感的にアンロードする 自由に似ています - または私は意味チェックすることと似ています。 あなたが行っている現在、その都度除い を通して、あなたは単にチェックしていない あなたがそこにあなたの価値を持っているかどうかを確認します。 しかし、あなたは、そのノードを取っているし、 基本的に、それを解放する。 それはあなたが何を要求し、アンロードものだ。 あなたはmallocさだ無料すべて。 だから、全体のリストを行っている もう一度、全体のハッシュを経由 テーブルを再び。 今回はチェックしません。 そこにあるものを確認します。 ただそこにあるものを解放。 そして最後にサイズ。 サイズは、実装する必要があります。 あなたのサイズを実装しない場合 - 私はこのようにそれを言うよ。 あなたは正確にサイズを実装しない場合 を含む1行のコード 文を返し、あなたは 間違ってサイズをしている。 だから、完全な設計のために、必ずサイズを確認 ポイントは、あなたが正確に1でそれをやっている を含むコード行、 return文。 そして、まだAkcharを荷造りしないでください。 イーガービーバー。 私はあなたたちに感謝言いたかった セクションに来るため。 ハッピーハロウィンを持っています。 これは私の衣装です。 私は木曜日に、これを身に着けていることでしょう 私が営業時間でお会いします。 そして、あなたはいくつかの詳細について興味があれば この衣装、感触などのバックグラウンド 2011セクションをチェックアウトして自由 私は理由の物語のための カボチャの衣装を身に着けている。 そして、それは悲しい物語です。 ですから、持っていることを確認してください 近くのいくつかの組織。 しかし、それでは、いずれかを持っている場合 私は固執よ質問 外側のセクションの後。 幸運は、問題に6を設定します。 そしていつものように、あなたがいずれかを持っている場合 質問、私に知らせてください。