SPEAKER 1：すべての権利は​​、これがあります CS50これを週に5回の終わりです。 そしてその最後の時間を思い出すたち 手の込んだデータを見始めました 解決するために開始した構造 導入を開始した問題、 新たな問題が、このための鍵 スレッドの一種であることが確認された私たち ノードからノードに行うようになりました。 だから、もちろん、これはあります 単独でリンクされたリスト。 そして単独で連結され、 私が意味するものはそこです これらのノードとの間に通します。 判明あなたは手の込んだ行うことができます 二重リンクリストのようなもの あなたは、矢印を持っていることによって 、両方の方向に向かっています 一定の効率化を支援することができます。 しかし、これは問題を解決し？ これは何の問題を解決しましたか？ なぜ我々は月曜日に気にしたのですか？ なぜ、理論的には、我々は月曜日に気にしたのですか？ それは何をするのか？ 観客：我々は、動的にサイズを変更することができます。 SPEAKER 1：OK、私たちすることができますので、 動的にサイズを変更します。 さてあなたの両方を行います。 だから、これを動的にサイズを変更することができます データ構造、配列、一方、 リコール、あなたが知っている必要があります あなたが望むどのくらいのスペース先験的 あなたがもう少し必要な場合は、 スペースは、あなたは運のうち、一種のです。 あなたは、全体の新しい配列を作成する必要があります。 あなたはあなたのすべてを移動する必要があります 一方から他方へのデータ、 最終的には古い配列を解放 することができますし、次に進みます。 どれだけの非常に高価な感じ、非常に 非効率的で、実際には、とすることができます。 しかし、これはすべての良いではありません。 私たちは一つであったどのような価格を支払います より明白な価格の我々 リンクリストを使用して支払いますか？ 観客：我々は、使用する必要があります それぞれのダブルスペース。 SPEAKER 1：うん、私たちが必要とします 少なくとも2倍くらいのスペースとして。 実際に、私はこの絵の実現しました 少しでも誤解を招きます、 現代の多くでCS50のIDEのため コンピュータ、ポインタまたはアドレス 実際には4バイトではありません。 それは非常に多くの場合、これらのです 日8バイト、どの ほとんど底を意味 実際にそこに長方形 二倍の一種であります 私が描いたものとして大きな、 これはあなたが3倍を使用していることを意味 我々はそうでないかもしれませんが、多くのスペース。 今、同時に、私たちはしています まだバイトを話し、右？ 私たちは必ずしも話していません MBまたはGB、 これらのデータ構造は大きくなる場合を除きます。 だから、今日、私たちは検討を開始 我々は、データを探索する方法 より効率的であれば 実際のデータが大きくなります。 しかし、ここでは、正規化してみましょう 最初の操作 あなたはこれらの上で行うことができます データ構造の種類。 だから、リンクのようなもの リストは一般的にサポートしています 削除などの操作、 挿入して、検索します。 そして私は何を意味するのですか？ それはちょうど、通常、そのことを意味します 人々がリンクされたリストを使用している場合は、 これらまたは他の誰かが実施しています 削除、挿入等の機能、 そして、することができますので、検索 実際に何かをします データ構造と便利。 それでは、簡単に見てみましょう 我々が実装する方法で 次のようにリンクされたリストのためのいくつかのコードです。 だから、これはいくつかのCコードで、 いなくても完全なプログラム 私は本当にすぐにホイップこと。 これは、ディストリビューションでは、オンラインではありません コー​​ド、それは実際には実行されませんので。 しかし、私はちょうどしたことに注意しましょう コメントは言ったと、 ドットドットドット、何かあります そこに、そこに、何かをドットドットドット。 そして、ちょうど見てみましょう ジューシーな部分が何でありますか。 だから、ライン3に、 これが今であることを思い出します 我々は最後のノードを宣言提案します 時間、これらの長方形オブジェクトの一つ。 それは、我々はNと呼ぶことにしますint型を持っています しかし、我々は何もそれを呼び出すことができ、 し、次の構造体と呼ばれるノードの星。 そして、ちょうど明確にするために、その二 行は、行6の上に、それは何ですか？ それが私たちのために何をしているのですか？ それは確かに多く見えるので いつもの変数よりも不可解。 観客：それは1つの上に移動することができます。 SPEAKER 1：それは1つの上に移動することができます。 そして、より正確には それは、アドレスを格納します であることを意味していたノードの 意味的に横に、右か？ だから、ことはないだろう 必ずしも何かを移動します。 それだけに起こっています 値を格納 アドレスになるだろう いくつかの他のノードの、 私たちは構造体を言った理由です ノードスター、表す星 ポインタまたはアドレス。 [OK]を、今、あなたは我々が持っていると仮定した場合 私たちに利用できるこのN、としましょう 他の誰かが持っていることを前提としてい 整数の全体の束を挿入 リンクされたリストに。 そして、リンクされたリストであること いくつかの点で指さ だ変数と呼ばれるリスト パラメータとして、ここに渡され、 どのように私は行行くのです 14検索を実行しますか？ 言い換えれば、私は実装していた場合 その目的は生活の中で機能 その後、int型とを取ることです リンクリストの始まり、 それは、リンクされたリストへのポインタです。 最初と同じように、私はダビデを誰だと思います 私たちボランティアは、月曜日にありました 彼が指さしました 全体のリンクリスト、 私たちが渡しているかのように、です ここに私たちの引数としてデビッド。 どのように我々は、このリストを横断については行くのですか？ まあ、それは判明しているにもかかわらず ポインタは、私たちに今、比較的新しいです 我々は比較的これを行うことができます 素直に。 私は先に行くつもりだと 一時的な変数を宣言しています 慣例によりちょうど起こっています ポインタ、またはPTRと呼ばれます、 しかし、あなたが欲しいものを呼び出すことができます。 そして、私は初期化す​​るつもりです そのリストの先頭に。 だから、一種の考えることができ 私と先生先日、 誰かを指すの種類 ボランティアとしての人間の間で。 だから私は、だ一時変数です ちょうど同じことを指し 私たちは偶然という名前のこと ボランティアのDavidも指摘されました。 今ポインタがある間 リコールので、nullではありません そのnullは、いくつかの特別なセンチネル値であり、 、リストの終わりを画定します 私は指していないんだしながら、 私たちの最後のボランティアのように地面 だった、のは先に行ってみましょう そして次の操作を行います。 pointer--もし、今、私は一種の希望 私たちは学生とやった何をすべきか ポインタドット次の場合structure-- むしろequals--、ポインタドットNが等しい場合 、変数Nに等しく に渡されています引数、 その後、私は先に行きたいです そして、trueを返すと言います。 私は内部の数Nを発見しました 私のリンクリストのノードのいずれか。 しかし、ドットもはや このコンテキストで動作します、 ポインタは、PTRは、ある理由 確かに、ポインタ、アドレス、 私たちは実際に素晴らしくすることができます 最終的には構文の一部を使用します 作りのようなもの 直感的な感覚と実際 から行くことを意味し、ここで矢印を使用し そこに整数にそのアドレス。 だから、中に非常に似ています ドット演算子の精神、 しかし、ポインタはポインタではありませんので、 そして、は実際の構造体自体は、 私たちは、矢印を使用しています。 だから私現在のノード、もし 一時変数は、を指しています N、私は何をしたいのではないですか？ まあ、私のヒトボランティアで 私たちは先日ここで持っていたこと、 私の最初の人間は、一私でない場合 たい、多分二人ではありません 私が欲しい1、第三に、私 移動物理的に維持する必要があります。 同様に、どのように私は、リストをステップ実行しますか？ 我々は配列を持っていたとき、あなたを ちょうど私プラスプラスのようでした。 しかし、この場合にはすればよいです 次に、ポインタ、取得、ポインタを行います。 言い換えると、次のフィールド 左手のすべてのようなものです その月曜日に私たち人間のボランティア 他のいくつかのノードを指すように使用していました。 それらは彼らの次の隣人でした。 だから私はこのリストをステップ実行したい場合は、 私はちょうど私プラスプラスもうできません、 私が代わりに言っています 私、ポインタが、起こっています どのような次のフィールドに等しくなるようにすることで、 次のフィールドは、次のフィールドがあり、 これらの左手、次のすべて 我々は、ステージ上でポインティング持っていたこと いくつかの後続の値に。 そして、私が通って取得する場合 その全体の反復、 そして最後に、私が持っていないヌルヒット 見つかったNはまだ、私はfalseを返します。 だからもう一度、私たちはここでやっていることすべて、 少し前画像のとおり、 でポイントすることによって開始されます おそらく、リストの先頭。 そして、私はチェックし、値であり、 私は9に等しいを探していますか？ もしそうなら、私はtrueを返すと私は終わりです。 そうでない場合、私は私の手を更新し、 ポイントへのAKAのポインタ、 次の矢印の位置にあり、 その後、次の矢印の位置、 そして次。 私は単純に、この配列を歩いています。 そこで再び、誰が気に？ これはのための成分である何を？ まあ、我々は導入することを思い出します スタックの概念、どの 抽象データ型は、それがだ限りにおいてです Cではない事、それはCS50のことではありません、 それは、このアイデア抽象的なアイデアです 互いの上にものを積み重ねます すなわち、で実現することができます さまざまな方法の束。 そして、私たちが提案した一つの方法はしていました 配列、またはリンクされたリストを持ちます。 そしてそれは、その正準判明します スタックは、少なくとも2つの操作をサポートしています。 そして話題の言葉はに、プッシュされています スタックに何かをプッシュし、 で、新しいトレイのような ダイニングホール、またはポップ、 これは、最上位を削除することを意味します ダイニングでスタックからトレイ ホール、多分いくつかの 他の操作にも。 では、どのような構造を定義できます 我々は今、スタックを呼び出していること？ まあ、我々は必要なのすべてを持っています 私が言うCで私達の処分で、構文、 私のタイプの定義を与えます スタックの内部構造、 私が言うつもりAの配列であり、 数字、次にサイズの全体の束。 だから、他の言葉で、私がしたい場合 コー​​ドでこれを実現するために、 私が手放すとだけの種類 これは言っていることを描きます。 だから、これは私に与える、と言っています 配列を持っている構造、 私は、能力があるかわかりません それは私がしたことを明らかにいくつかの定数です 別の場所で定義され、それは大丈夫です。 しかし、それはただ一つだと仮定し、 2つ、3つ、4つ、5。 だから、容量は5です。 私の内側にこの要素 構造は、番号を呼ばれます。 そして、私は1つを必要とします 他の変数明らかに 最初に私が行くよと呼ばれるサイズ ゼロに初期化される規定します。 何もでがない場合 スタックサイズは、ゼロであります それは数のゴミ値です。 私はまだそこに何があるかわかりません。 だから私はプッシュする場合 スタックに何か、 私は機能プッシュを呼び出すと仮定し、 私は、数50のように、50を押してくださいと言います あなたはどこを提案します 私は、この配列にそれを描きますか？ 5別の可能な答えがあります。 どこで番号50をプッシュしたいですか？ ここでの目的ならば、もう一度、呼び出します 機能プッシュは、引数に渡します 私はそれを置けばいい50の？ ファイブpossible-- 20％の確率で 正しく推測します。 はい？ 聴衆：右端。 SPEAKER 1：右端。 25％の確率で用意されました 正しく推測します。 だから、実際には罰金になります。 慣例では、私は配列を言いますよ、 当社は通常、左側に開始します しかし、我々は確かに可能性 右から始まります。 だからここスポイラーは、私はだろう おそらく、左側にそれを描画しようとして、 ただここで通常の配列のように 私は右に左に行くを開始します。 しかし、あなたが反転することができた場合 算術、罰金。 それはちょうど、従来ではありません。 [OK]を、私は1つをする必要があります しかし、より変更。 今私は何かをプッシュしたこと スタックに、次は何？ すべての権利、私はサイズを増加する必要があります。 だから私は先にだけ行ってみよう ゼロであった、これを更新します。 そして代わりに、今、私は行きますよ 値1を入れます。 そして今、私は別のをプッシュするとし スタックに数51のように。 まあ、私は1つ以上を行う必要があります サイズ2までです変化。 そして、私は1つ以上をプッシュするとし 61のようなスタックに数、 今私はサイズを更新する必要がある1つ以上の 時間、サイズなどの値3を取得します。 そして今、私はポップを呼び出すとします。 今大会によって、ポップ、 引数を取りません。 スタックでは、全体の トレイメタファーのポイント あなたは裁量権を持っていないということです そのトレイを取りに行くために、すべてのあなたが行うことができます から最上位の1をポップされています スタック、という理由だけで。 つまり、このデータ構造が何をするかです。 もしそのロジックによるだから私 ポップ、何が外れ言いますか？ だから61。 それでは、実際にコンピュータであり、 メモリに何をするつもり？ 何私のコードは何をするのでしょうか？ あなたは何を提案します 私たちは、画面上の変更しますか？ 何を変更する必要がありますか？ ごめんなさい？ だから我々は61を取り除きます。 だから私は間違いなくそれを行うことができます。 そして、私は61を取り除くことができます。 そして、他のもの 変更が発生する必要がありますか？ サイズは、おそらく2に戻っています。 そしてそうそれは大丈夫です。 しかし、サイズが数分待ちます 少し前3でした。 ちょうど迅速な健全性チェックをしましょう​​。 我々は、我々の方法を知っていました 61を取り除くしたいですか？ 私たちはポップだから。 そして私は、この第2の特性サイズを有します。 私は、ちょっと待って 週2に戻って考えて 私たちは話して始めたとき これは場所ゼロであったの配列、 これがこの場所だった、場所一つでした 2つのこの場所は三つ、四つであり、 それは次のようになります サイズの関係 私は削除する要素を アレイからだけで何のように見えますか？ サイズから1を引きました。 そして、そのためには、どのようにヒトのようです 私たちは、61は最初に来る知っています。 どのようにコンピュータが知っているだろうか？ ときあなたはおそらくあなたのコード、 サイズから1を引いたものをやってみたいです、 そう3マイナス1は2であり、かつ 私たちは61を取り除きたいことを意味します。 そして、我々は確かに更新することができます そのサイズので、サイズ今 ちょうど3つから2つになります。 そして、ちょうど知識をひけらかすことを、私は行きますよ 右、私は終わりだことを提案しますか？ あなたは直感的に提案しました 正しく私は61を取り除く必要があります。 しかし、私は一種の持っていません ソートの61の脱却？ 私は効果的に忘れてしまいました ことそれは実際にあります。 あなたが読んだなら、バックPSET4に思います フォレンジックに関する記事、PDF 私たちは、あなたたちは読んでいたかということ PSET4今週読み込みます。 これは実際に密接であることを思い出してください コンピュータフォレンジックの全体的なアイデア。 どのようなコンピュータは一般的にないです 何かがどこにあるか、それだけで、忘れ それはで行くと好きではありません それをスクラッチしてみてくださいまたはオーバーライド 0と1とのそれらのビット またはいくつかの他のランダムパターン あなたがない限り、自分が意図的にそう。 だからあなたの直感がありました 右のは、61を取り除くましょう。 しかし現実には、我々は気にする必要はありません。 私達はちょうどそれを忘れする必要があります それが私たちのサイズを変更してあります。 今、このスタックに問題があります。 私は物事をプッシュし続ける場合 スタックに、何の 明らかに起こるだろう わずかな時間の時間の？ 私たちは、スペースが不足するつもりです。 そして、我々は何をしていますか？ 私たちは、種類のネジ止めしています。 この実装はできません 使用しているので、私たちは、配列のサイズを変更します この構文、よろしければ 週2に戻って考えて、 あなたが宣言した後に アレイのサイズは、 我々はまだどこメカニズムを見ていません あなたは、配列のサイズを変更することができます。 そして実際、Cはその機能がありません。 あなたが言う場合は私に5を与えます NTHS、それらを呼び出す番号、 それはあなたがそれを取得するつもりだすべてです。 だから我々は、月曜日のようになりまし持っていますか 解決策を表現する能力 しかし、私達はちょうど微調整する必要があります 私たちのスタックの定義 いくつかのハードコードされた配列されないように、 ちょうどアドレスを格納します。 今、これはなぜですか？ 今、私たちはただで快適でなければなりません 私のプログラムが実行されるという事実は、 私はおそらくに行きますよ 人間を依頼する必要があり、 どのように多くの数字あなたが保存したいですか？ そこで入力がどこから来ています。 しかし、私はことを知っていたら、 数、私はちょうどすることができます 与えるように機能するものを使用 私のメモリの塊？ 私は、malloc関数を使用することができます。 そして、私は、任意の数を言うことができます バイト私は、これらのNTHSのために戻って欲しいです。 そして、私が持っているすべてを数字に格納します この構造体の内部に、ここで可変 何すべきですか？ 実際に何に入ります このシナリオの数字？ うん、最初のポインタ メモリのチャンクのバイト、 より具体的に、アドレス それらのバイトの最初の。 それは一つだ場合は問題ではありません バイトまたは億バイト、 私は最初に気にする必要があります。 そのため何のmalloc保証および 私のオペレーティングシステムの保証、 すなわち、メモリIのチャンクであります 取得するには、それが連続したことになるだろう。 ギャップがあるようにはないだろう。 だから私は、50を求めてしまった場合 バイトまたは1,000バイトとして、 彼らはすべてのことになるだろう 背中合わせにバックアップします。 そして長い間、私はどのように、どのように大きな覚えて ずっと私は私が知っている必要があり、すべてを求め 最初のそのようなアドレスです。 だから今、私たちはコード内の能力を持っています。 いえ、それは私たちを取るために起こっています これを書くために多くの時間、 私たちは、今ではそのメモリを再割り当て可能性 そこに別のアドレスを格納します 私たちも、大きくなったりしたい場合は、 メモリの小さいチャンク。 だからここにトレードオフに。 今、私たちはダイナミズムを得ます。 我々はまだ持っています 私が主張している連続性。 malloc関数は、私たちを与えるため、 メモリの連続チャンク。 しかし、これは痛みになるだろう 私たちのために首、プログラマー、 実際にアップコードに。 それはちょうどより多くの仕事です。 私たちは、私が何であったかに似たコードを必要とします ちょっと前に出叩い。 非常になんとか、それは複雑になります。 だから開発者の時間、プログラマ 時間はまだ別のリソースであります 私たちが過ごすために必要かもしれません 新しい機能を得るためにいくつかの時間。 そしてもちろんキューがあります。 我々は、このにはなりません 多くの詳細で1。 しかし、それは心の中で非常に似ています。 私はキューを実装することができ、および その対応する動作、 エンキューまたはデキュー、追加または削除のような、 それを言うだけ手の込んだ方法です、 エンキューまたはデキュー、次のように。 私はちょうど自分自身の構造体を与えることができます その再び数のアレイを有し、 その再度サイズを有し、 しかし、なぜ私は今必要なのですか キューの先頭を追跡するには？ 私が知っている必要はありませんでした 私のスタックの正面。 さて、もし私が再び用 ちょうどハードのを聞かせてqueue-- 5のようなものとして、それをコーディング 潜在的に、ここで整数。 これは、0個、1個、2個、3個、4です。 これは、になるだろう もう一度番号を呼ばれます。 そして、これはサイズと呼ばれます。 なぜそれが十分ではありません サイズだけを持っていますか？ さて、上でそれらの同じ番号を押してみましょう。 だから、私はキューに入れられた、または押されpushed--。 今、私は50をエンキューします、その後、 51、次に61、ドットドットドット。 だから、エンキューです。 私は、61、その後50、51をエンキュー。 そして、それは同じに見えます これまでのスタックに、 除いて私は1つの変更を行う必要があります。 私はこのサイズを更新する必要があるので、私は行きます ゼロ二から一に今3。 私はどのようにデキューできますか？ 何がデキューとどうなりますか？ 誰が最初​​にこのリストをオフに来る必要があります それはアップルストアでのラインですか？ だから50。 だから、ちょっとトリッキーこの時間です。 前回のに対し、それはスーパーでした ジャストサイズのマイナスいずれかの操作を実行するのは簡単、 私は効果的に私の配列の最後に到達します 数字である場合、それは61を除去します。 しかし、私は61を削除する必要はありません。 私は、50をしたい人 5:00でした 以下のためにラインアップします 新しいiPhoneやその他もろもろ。 そして私は、50を取り除くために ちょうど、これを行うことができないのですか？ 私は50を越えることができます。 しかし、我々はちょうど私達言いました そう肛門である必要はありません スクラッチアウトまたはデータを非表示にするように。 それがどこにあるか私達はちょうど忘れることができます。 しかし、私は今、私のサイズを変更した場合 2、この十分な情報があります 私のキューに何が起こっているか知っていますか？ あんまり。 私のサイズが2であると同様ですが、 キューは、どこから始めません、 私はまだ持っている場合は特に メモリのものと同じ番号。 50、51、61。 だから私は覚えておく必要があります 今どこに正面です。 そして、私が提案したように、 そこに、私たちは求めているでしょう その最初のN番目の前、 値は何だったでしょうか？ ゼロ、リストの始まりに過ぎません。 しかし、今デクリメントに加えて、 大きさは、私たちは前をインクリメント。 今ここで別の問題です。 だから一度、私は続けます。 これは数あるとし くそ、124、121のように、その後、 私は宇宙の外です。 しかし、私はないんだけど、ちょっと待って。 だから、物語の中で、この時点では、 サイズが1、2であると仮定し、 3、4、そうしたと サイズは、フロントが1である、4です そう51は、前面にあります。 私はここで別の番号を入れたいです、 しかし、くそ、私は宇宙の外です。 しかし、私は、右、本当にないんだけど？ 私はいくつかをどこに置くことができます 171のような付加価値、？ ええ、私はできるだけの種類 右、そこに戻って？ そして50を横断する、または ちょうど171でそれを上書きします。 そして、あなたは、なぜ迷っている場合 私たちの数値は、そのようにランダムです これらは、一般的にコンピュータをとっています CS50後ハーバード大学の科学コース。 しかし、それは良い最適化しました、 今ので、私はスペースを無駄にしませんよ。 私はまだ覚えておく必要があります どのように大きなこのことは、合計です。 これは、5つの合計です。 私はしたくないので 51の上書きを開始します。 だから今私はまだ空き容量が不足しています、 前と同じ問題。 しかし、あなたはどのように見ることができるようになりまし あなたのコードでは、おそらく もう少しを記述する必要があり それを実現するために複雑。 そして実際に、どのようなオペレータ C言語で、おそらくすることができます あなたは魔法のように、この円形のですか？ うん、モジュロ演算子、 パーセント記号。 だから、キューについての種類のクールなものを、 我々は描画の配列を維持するにもかかわらず、 このような直線として、あなたの場合 一種の湾曲としてこれについて考えます 周りの円として、そしてちょうど 直感的に、それは一種の精神的に動作します 私はもう少しきれいだと思います。 あなたはまだ実装する必要があります コー​​ド内でそのメンタルモデル。 そうではないこと、ハード、 最終的には、実装するために、 しかし、我々はまだ、かなりsize--を失います 我々はこれを行う場合を除き、サイズを変更する機能。 私たちは、配列の解消を取得する必要があります 単一のポインタと交換し、 して、どこかに私のコードで私が持っています 実際にどのような関数を作成するための呼び出し 配列と呼ばれる番号？ malloc関数、またはいくつかの類似しました 機能、正確に。 スタックやキュー上の任意の質問。 うん？ 良い質問。 何モジュロここで使用します。 そこで、一般的に、使用している場合 MOD、あなたはそれを行うだろう の大きさに 全データ構造。 だから、5または容量のようなもの、であれば それは一定ですが、おそらく関与しています。 しかし、単にモジュロ5をやって おそらく、十分ではありません 私たちが知っている必要がありますので、我々を行います ここかここか、ここで折り返します。 だから、おそらくもいます 関与するするつもり 事の大きさ、または 同様にフロント変数。 だから、比較的ちょうどこのです 単純な算術式、 しかし、モジュロは重要な要素になります。 だから短編映画あなたがする場合。 アニメーション一部 他大学の人たち 私たちがしたことをまとめて この議論のために適合。 それはジャックが学習関与します キューと統計についての事実。 FILM：むかしむかし、 ジャックという名前の男がありました。 それは友達を作るに来たとき、 ジャックはコツがありませんでした。 そこでジャックはに話に行きました 最も人気のある男と彼は知っていました。 彼はルーに行って尋ねた、私は何をしますか？ ルーは彼の友人のを見ました 本当に悩んでいました。 まあ、彼はただ、始まりました あなたが服を着ているかに見えます。 あなたは、任意の服を持っていません 異なる表情で？ はい、ジャックは言いました。 私は確信しております。 私の家に来て、 私はあなたにそれらを紹介します。 そこで、彼らはジャックのに消えました。 そして、ジャックはルーにボックスを示しました 彼はすべての彼のシャツを保ったところ、 彼のズボン、彼の靴下。 ルーは、私はあなたが持っている参照してください、と述べました 山のすべてのあなたの服。 なぜあなたは、いくつかを着用しません しばらくの間に一度他の人？ ジャックは、言っただけでなく、ときに私 服や靴下を削除し、 私はそれらを洗って置きます ボックスにそれらを離れて。 そして、次が来ます 朝、最大私はホップ。 私はボックスに移動してもらいます 上から私の服。 ルーはすぐに実現します ジャックに問題。 彼は、服、CDを保持しました スタック内の図書。 彼はのために達したとき 読みしたり、着用するもの、 彼はトップの本や下着を選ぶと思います。 そして、彼が行ったときに、彼 すぐに戻ってそれを置くことになります。 戻るには、スタックの一番上に、行くだろう。 私は解決策を知っています、 勝ち誇ったラウド言いました。 あなたがすることを学ぶ必要があります キューを使用して起動します。 ルーは、ジャックの服を取り、 クローゼットの中にそれらを切りました。 そして、彼は空になった時 ボックスには、彼はそれを投げました。 それから彼はジャックの最後に、今、言いました 日、左にあなたの服を置きます あなたはそれらを片付けるとき。 そして、明日の朝とき あなたの服を取得し、太陽の光を参照してください。 右に、行の末尾から。 分かりませんの？ルーは言いました。 それはとても素敵になります。 あなたは、一度にすべてを着用しましょう 前に二回何かを着用してください。 そして、キュー内のすべてと 彼のクローゼットや棚で、 ジャックは感じ始め 自分自身の非常に確認してください。 ルーへのすべてのおかげで、 彼の素晴らしいキュー。 SPEAKER 1：すべての権利、それは愛らしいです。 だから何が本当に起こってきました 今ボンネットの下に？ 我々はポインタを持っていること、 我々はmalloc関数を持っていること、 我々は、作成する能力を持っていること 自分のためにメモリのチャンク 動的に。 だから、これは絵たちです ちょうど先日垣間見。 私たちは本当に住むませんでした その上に、この絵 下に続いています 今週間のフード。 そして、これはただ表し、 私たちが描いた四角形、 コンピュータのメモリ。 そして多分あなたのコンピュータ、またはCS50 IDは、メモリやRAMのギガバイトを持っています または2ギガバイトまたは4。 それは本当に問題ではありません。 お使いのオペレーティングシステム WindowsやMac OSのやLinux、 基本的に、あなたのプログラムが可能に それがアクセス権を持つことを考えて 全体に コンピュータのメモリ、 あなたが実行されている可能性があっても 一度に複数のプログラム。 だから実際には、それが実際に動作しません。 しかし、それは幻想のようなものです あなたのプログラムのすべてに与えられました。 だから、RAMの2ギグ、これを持っていた場合 コンピュータはそれを考えるかもしれない方法です。 今偶然、これらのいずれか 物事、メモリのこれらのセグメントの一つ、 スタックと呼ば​​れています。 そして、実際には任意の時間 これまで書き込みコードで あなたが求めていること インスタンスメインための機能、。 いつでも私がしたことを思い出してください 描かれたコンピュータのメモリ、 私はいつも一種の描画します ここでは、長方形の半分 そして、話を気にしないでください 上記の何について。 主が呼び出されたとき、私は主張するため、 あなたは、このメモリのスライバーを取得すること それはここでダウンしました。 そして、メイン関数を呼び出された場合 スワップのように、よくスワップがここに入ります。 そして、それはそれだ、判明します どこに終わるです。 スタックと呼ば​​れるもので、 コンピュータのメモリの内部。 今一日の終わりに、 これはただのアドレスです。 これは、バイトゼロのようなものです バイト1、バイト2億円となりました。 しかし、あなたはそれについて考える場合 この長方形のオブジェクトとして、 すべての我々は、すべてをやっています 我々は関数を呼び出す時です メモリの新しいスライスを重ねます。 我々は、スライスその機能を与えています で動作するように、独自のメモリ。 そして今、これが重要であることを思い出してください。 私たちがしなければ持っているため、 スワップのようなもの AとBなど、および2つのローカル変数 私たちは、1と2からこれらの値を変更 2と1、リコールへ スワップを返すときに、 それは、このスライスかのようです メモリのちょうどなくなっています。 実際に、それはまだです そこフォレンジック。 そして、何かが実際にそこにまだあります。 しかし、概念的に、それは同様です けれどもそれは完全に逝ってしまいました。 それで主は、作業のいずれかを知りません。 それは、そのスワップ機能に行われていました それは実際にそれらに渡された場合を除き ポインタまたは参照によって引数を指定します。 さて、根本的な解決策 スワップでその問題に アドレスによってで物事を通過します。 しかし、それは何も、結局のところ その部分の上に続いてき すべてのこの時間は、長方形の まだより多くのメモリアップがあります。 そして、ときに動的に メモリを割り当て、 それは、のGetStringの内側にいるのですか 我々はCS50であなたのために行ってきました ライブラリー、または君たち場合 malloc関数を呼び出すと尋ねます のチャンクのためのオペレーティングシステム メモリは、それがスタックから付属していません。 それは別の場所から来ています お使いのコンピュータのメモリに それは、ヒープと呼ばれています。 そして、それは何が違うのではありません。 これは、同じRAMです。 これは、同じメモリです。 それはアップちょうどRAMです そこの代わりに、ダウンここに。 そしてそうそれは何を意味するのでしょうか？ さて、あなたのコンピュータがある場合は メモリの有限量 スタックので、育っています 話し、ヒープ、に従ってします この矢印に、ダウン成長しています。 言い換えれば、すべての 時間あなたはmalloc関数を呼び出し、 あなたのスライスを与えられています メモリの上から、 多分少し低い、その後少し 下、あなたはmalloc関数を呼び出すたびに、 ヒープは、それは使用ですが、 成長の一種です、 ものに近づく成長？ スタック。 だから、これは良いアイデアのように見えるのでしょうか？ それは本当にはっきりしていない場合は、私は、意味します あなた場合にのみ、あなたは他に何を行うことができます メモリの有限量を持っています。 しかし、これは確かに悪いです。 これら2矢印が上にあります 互いのためのコースをクラッシュ。 そして、それはその悪いやつ、人々が判明 プログラミングに特に優れています、 コンピュータに侵入しようとすると、 この現実を利用することができます。 実際には、のは、考えてみましょう 少しスニペット。 だから、これはあなたが読むことができる例であり、 ウィキペディアでより詳細に示します。 私たちはであなたを指します 記事であれば好奇心。 しかし、攻撃が一般的にあります バッファオーバーフローとして知られていること 人間である限りのために存在していました 操作する能力を持っていました 特にC言語で、コンピュータのメモリ、 だから、これは非常に任意のプログラムです、 しかしそれでは、ボトムアップからそれを読んでみましょう。 ARGCチャースターARGVにメイン。 だから、かかるプログラムです コマンドライン引数。 そして、すべての主は明らかに呼び出しがあるん この関数は、簡単のためにFを呼び出します。 そして、それは何に渡しますか？ 1のARGV。 だから、Fに入るものは何でも 単語は、ユーザーが入力したことです 後のプロンプトで まったくプログラムの名前。 シーザーやVigenereようなので、多くの、どの あなたはARGVにやって思い出すかもしれません。 だから、Fは何ですか？ Fは文字列を取り込み、 その唯一の引数として、 char型のスターAKA、同じ 事、文字列として。 そして、それは任意に呼ばれています この例では、バー。 そして、char型のC 12、 ただ普通の言葉で、 私たちのためにやって文字Cブラケット12は何ですか？ それは何をするのか？ 具体的には、メモリの割り当て 12文字のための12バイト。 その通りです。 そして、最後の行は、攪拌し、 コピーは、おそらく見ていませんでした。 これは文字列のコピーです その目的は生活の中で機能 その第二引数をコピーすることです 最初の引数に、 だけまで 一定のバイト数。 だから、3番目の引数は、言います あなたはどのように多くのバイトをコピーする必要がありますか？ バーの長さは、 何で入力したユーザー。 のと内容 バー、その文字列、されています Cで指さメモリにコピー だから、これは一種の愚かなようで、それはあります。 それは不自然な例ですが、 それは代表的です 攻撃ベクトルのクラスの、 プログラムを攻撃する方法です。 すべては、ユーザーならば罰金と良いです 11文字の言葉でタイプ または少ない、プラスバックスラッシュゼロ。 何よりものユーザーが、タイプの場合 11または12または20または50文字？ どうするつもりこのプログラムは何ですか？ 潜在的にワンセグ障害。それは起こっています 盲目的アップバーのすべてをコピーします で、その長さに バーで文字通りすべてのもの、 C.しかし、Cで指摘アドレスに 唯一の先制12バイトとして与えています。 しかし、追加のチェックはありません。 条件がない場合はありません。 ここでチェックエラーはありません。 だから、このプログラムは何ですか 何をするつもりは、やみくもにあります 他に一つのことをコピーします。 そして、私たちはこれを描く場合 絵のように、ここです メモリ空間のちょうどスライバー。 だから私たちは、一番下に気付きます ローカル変数のバーを持っています。 store--ために起こっているので、ポインタ だと地元の引数ではなく 文字列のバーを保存するために行きます。 そして、ちょうど気づきます それ以上のスタックで、 なぜならあなたが尋ねるたびに スタック上のメモリのため、 それは少し行きます それ以上の絵、 私たちはそこに12バイトを持っていることに気づきます。 左上1は、Cブラケットゼロであり、 右下の1は、Cブラケット11です。 それはどれだけのコンピュータです それをレイアウトする予定。 だから直感的に、バーはより多くを持っている場合 含めた合計で12文字、より バックスラッシュゼロであり、 12またはCブラケット12は行くつもり？ かここ12日です 文字または13日文字、 百文字に行きます 絵に終わるには？ 上または下に？ 右、たとえ理由 スタック自体は、上方に成長します あなたは中のものを入れてしたら それ、それ、設計上の理由から、 上から下にメモリを置きます。 あなたは12以上のバイトを持っているのであれば、 あなたがバーを上書きする開始するつもりです。 今ではバグですが、それはです 本当に大したこと。 ありますので、しかし、それは、大したことです メモリで起こってより多くのもの。 どのように我々はかもしれないので、ここです 明確にするために、ハロー置きます。 私は、プロンプトにハローで入力した場合。 H-E-L-L-Oバックスラッシュゼロ、内終わります これらの12バイトは、我々は超安全です。 すべては順調です。 しかし、私は何かを入力した場合 長く、潜在的にそれはです バースペースに忍び込むつもり。 しかし、さらに悪いことに、それはターン すべてのこの時間外に、 我々はについて話したことがないにもかかわらず、 これは、スタックが他のもののために使用されます。 これは、ローカル変数だけではありません。 Cは非常に低レベルの言語です。 そして、それ一種の密か また、スタックを使用しています ときに覚えておきます 関数は、何と呼ばれています アドレスは、前の関数であります それは戻って、その関数にジャンプすることができます。 だから、メインの呼び出しはの間で、交換時 物事がスタックにプッシュ ローカル変数だけを交換していません、 またはその引数、また密かにプッシュ スタック上に表されるように ここで赤スライスすることにより、 物理的にメインのアドレスであります コンピュータのメモリで、 コンピュータは、交換が行われたときにそのよう 私は主に戻って行く必要がある知っています main関数の実行を終了します。 これは、今危険であるかの理由 こんにちはよりよく、より内のユーザーの種類、 ユーザーの入力が上書きしてしまうような または、その赤い部分が上書きされます 論理的であれば、コンピュータの やみくもと仮定しよう その赤いスライス内のバイトがあること それは返す必要があります先の住所、 敵がどのようであれば十分にスマートまたは バイトのシーケンスを置くには十分に幸運 そこアドレスのように見えること、 それはコードのアドレスです 彼または彼女はコンピュータを望んでいます 代わりに、メインの実行するには？ 言い換えれば、どのような場合 ユーザは、プロンプトで入力しています ただものではありません こんにちは、無害のように 実際には同等のコードです このすべてのユーザーのファイルを削除するには？ それとも私に自分のパスワードを電子メールで送信！ それとも自分のロギングを開始 キーストロークは、右？ 方法があり、今日は明記しましょう 彼らはハローないだけで入力できること 世界や自分の名前、 彼らは基本的にできました コー​​ド、ゼロに渡し、 もの、そのコンピュータ コー​​ドと住所の両方のミス。 もし、やや抽象的にいえそう 十分な敵対コード内のユーザーの種類 私たちはここのように一般化するだろうと A. Aは、攻撃や敵です。 だから悪いもの。 私たちは気にしません 数字または0または1 今日、あなたは、終わること その赤い部分が上書きされ、 バイトの順序に注意してください。 O 835 Cゼロ8ゼロ。 そして今ここにWikipediaの記事など あなたは今、実際に起動した場合、提案しています お使いのコンピュータの中でバイトを標識 メモリは、Wikipediaの記事は何ですか 提案は、どのような場合のアドレス、ということです その左上のバイトの80 C 0 3508です。 換言すれば、悪者がある場合 自分のコードで十分にスマート 実際にここ数を入れています コー​​ドのアドレスに対応します 彼または彼女は注入しました コンピュータに、あなた コンピュータをだますことができます 何もしてへ。 、ファイルの削除電子メールで送信 物事、あなたのトラフィックを盗聴、 文字通り何でもすることができ コンピュータに注入しました。 だからバッファオーバーフロー その中核に攻撃 ただ愚かな、愚かです その配列のオーバーライド その境界が確認されていませんでした。 そして、これは超危険は何かということです そして、同時に超強力 C言語で私たちが実際に持っているということです メモリ内の任意の場所へのアクセス。 それは私たち次第だ、プログラマー、 元のコードを書く人 いずれかのくその長さをチェックします 私たちが操作している配列。 だから明確にする、修正は何ですか？ 私たちはこれにロールバックする場合 コー​​ド、私はいけません バーの長さを変更し、どのような 他に私がチェックすべきですか？ 他に何私がやるべきこと 完全にこの攻撃を防ぎますか？ 私はただやみくもに言いたくありません あなたは多くのバイトとしてコピーする必要があること バーの長さです。 私が言いたい、としてコピー バーにあるように多くのバイト 割り当てられたまで メモリ、最大12。 だから私は、条件の場合のいくつかの種類を必要とします それは、バーの長さをチェックし、 それが12を超える場合は、我々だけでハードコード 可能な最大距離として12。 それ以外の場合は、いわゆるバッファ オーバーフロー攻撃が発生する可能性があります。 これらのスライドの下部には、 あなたはより多くを読み興味があれば 実際のオリジナル記事です。 あなたが見てみたいと思います。 しかし、今、価格の中 こちらで負担することは非効率でした。 だから、それは簡単でした どのローレベルの外観 問題は、今、我々が発生する可能性が コンピュータのメモリにアクセスすることができます。 しかし、別の問題、我々 すでに月曜日につまずい ただ非効率でした リンクリストの。 我々は戻って線形時間にしています。 私たちは、もはや連続した配列を有していません。 我々は、ランダムアクセスを持っていません。 私たちは、角括弧表記を使用することはできません。 我々は文字通り、whileループを使用する必要があります 私は少し前に書いたような。 しかし、月曜日に、私たちができることを主張しました 効率の領域に戻ってクリープ 何かを達成 対数多分、または最高のまだ、 だ多分何か 一定の時間、いわゆる。 それでは、どのよう我々は、これらの新しいを使用していることを行うことができます ツール、これらのアドレス、これらのポインタ、 そして、私たち自身のものをスレッド？ まあ、あるとし ここで、これらがたくさんあり​​ます 我々はに格納する数字の 効率的なデータ構造と検索。 私たちは絶対に週に巻き戻すことができます 2、配列にこれらを投げます、 バイナリ検索を使って検索します。 分割統治。 そして、実際にあなたが書きました PSET3でバイナリ検索、 どこに検索プログラムを実施しました。 しかし、あなたは何を知っています。 より多くの種類があります これを行うための賢い方法。 それはもう少しです おそらくそれは、洗練されたと なぜバイナリ私たちが見ることができます 検索はとてもはるかに高速です。 まずは、ご紹介しましょう ツリーの概念。 どれでも中かかわらず 現実の木の種類の コンピュータの世界では、このように育ちます 彼らは一種の下方への成長科学 あなたが持っている家系図のような あなたの祖父母や偉大な祖父母 またはその他もろもろトップ、家長でと 家族の女家長、​​一つだけ 以下のいわゆるルート、ノード、 その子供がいるが、 その子であるその下に、または より一般的にはその子孫。 そして、誰もがぶら下がっ 家族の底 であることに加え、ツリー、 家族の中で最年少、 また、単に一般的にすることができます ツリーのリーフと呼ばれます。 だから、これはちょうど束であります 単語と定義 コンピュータのツリーと呼ばれるもののために 科学、家系図のようにずっと。 しかし、愛好家の化身があります 木の、そのうちの1つ 二分探索木と呼ばれています。 そして、あなたのことができいじめるの種類 このことは何を離れて。 まあ、それはどのような意味でのバイナリですか？ どこにバイナリがここから来たのでしょうか？ ごめんなさい？ それはどちらかそれほどではありませんか。 これは、各ノードが全くあることがよりです 二つ以上の子どもたちが、私たちはここを参照してくださいよう。 一般的に、tree--と あなたの両親や祖父母 など、多くの子供を持つことができますか 孫彼らが実際に必要として、 そのため、インスタンスのためにそこに我々は3を持っています その右手ノードオフ子どもたち、 しかし、バイナリツリーで、ノードが持っています 最大で0個、1個、または2人の子供。 そして、それは、素晴らしい特性です それは2でキャップだ場合ので、 私たちのことができるようにするつもりです 小さなログベース2を取得 アクションは最終的にここで起こって。 だから我々は、対数何かを持っています。 しかし、現時点でその上より。 探索木の数であることを意味 配置など左側の子のこと 値は、ルートよりも大きいです。 そして、その右の子です ルートよりも大きいです。 つまり、のいずれかをとる場合 ノード、この写真のサークル、 その左側に見えます 子供とその右の子、 最初は、より小さくなければなりません 第二は、より大きくする必要があります。 それで正気は55をご確認ください。 これは、子供が33で残っています。 それはより少ないです。 55、その右の子は77です。 それはより大きいです。 そして、それは再帰的な定義です。 私たちはそれらの一つ一つをチェックすることができます ノードと同じパターン開催します。 だからでの素敵なものです 二分探索木であります その一つは、我々はそれを実装することができます 構造体で、これだけが好きです。 そして、私たちが投げているにもかかわらず、 あなたに構造の多く、 彼らは多少です 直感的な今うまくいけば。 構文は、まだ確かに難解です しかし、この内のノードの内容 context--我々は保ちます 単語のノードを使用して、 それは長方形ですか 画面または円に、 それだけでいくつかの一般的なコンテナですが、 以下のような木のこの場合、 私たちが見て、私たちは整数を必要とします 各ノードで そして私は指す2つのポインタを必要とします 左の子と右の子に、 それぞれ。 それはですので、どのようにかもしれません 構造体のそれを実装します。 そして、どのように私は、コードでそれを実装するのでしょうか？ さて、素早くてみましょう この小さな例を見てみましょう。 それは機能していないのですが、私はしました コピーされ、その構造体を貼り付けました。 そして、もしバイナリのための私の機能 探索木は、検索と呼ばれ、 これは2つの引数を取り、 整数Nとポインタ ツリーのノードなので、ポインタへ またはツリーのルートへのポインタ、 どのように私は、Nを探して行くのですか？ さて、最初に、私はだから ポインタを扱います、 私は健全性チェックをするつもりです。 ツリーがヌルに等しい等しい場合、Nは このツリー内のか、このツリー内の？ それは右、することはできませんか？ 私はヌル過ぎだ場合は、 そこには何もありません。 私かもしれないとしても、単に やみくもにはfalseを返すと言います。 あなたが私に何を与えていない場合、私は確かにすることはできません 他のN.だから、私は可能性のある番号を検索 今確認？ 私はよく、他のNがある場合を言うつもりです ツリーノードにあるものは何でも未満 私はN値を渡してきたこと。 言い換えれば、私は数あれば N、探して、ノードよりも小さいです 私は見ていていること。 そして、ノードは、私が探しています ツリーと呼ばれているで、 そして、前の例からリコール ポインタの値を取得するには、 私は矢印の表記法を使用します。 Nツリー矢印未満であれば Nは、私は概念的に左に行きたいです。 どのように私は左サーチし表現するのですか？ これがある場合は、明確にするために、 問題の画像、 私は、その最上位に合格してきました それが下を向いています矢印。 それは私の木のポインタです。 私は、ツリーのルートを指しています。 そして、私はのために、と言う探しています 数44、任意に。 44以下であります 明らかに55よりも大きいですか？ だから、より少ないです。 だから、この条件に該当する場合。 だから、概念的に、私はに何をしたいです 私は44を探している場合は、次の検索？ うん？ まさに、私がしたいです 左の子を検索し、 またはこの画像の左部分木。 そして実際に、私を通します ここに絵ダウン ちょっと、以来、 私はこれを傷つけることはできません。 私は55で、ここで起動した場合、および 私が知っている値44 にあるため、私は探しています 左は、それはようなものです 中で電話帳を引き裂くような 半分または半分にツリーを引き裂きます。 私はもう気にする必要はありません ツリーのこの全体の半分。 そして、まだ、不思議の観点から 構造、こっち、この事 、33で始まること自体 二分探索木です。 ため、私は前の単語が再帰言っ 確かに、これは、そのデータ構造であります 定義によって再帰的です。 あなたはこののツリーを持っている可能性があります 大きいが、その子供たちの一人一人 ほんの少し小さいツリーを表しています。 代わりに、それはおじいちゃんであることの または、今はちょうどママおばあちゃんの or--私はお母さんないsay--することはできません またはお父さん、それは奇妙なことだろう。 そこに二人の子供の代わりに 兄と兄弟のようになります。 家系の新世代。 しかし、構造的に、それは同じ考えです。 そして、それは私が機能を持つ判明します これで私は二分探索を検索することができます 木。 それは、検索と呼ばれています。 私は木の矢印左側にNを検索 他のNの値よりも大きい場合 ことを私は現在でよ。 少し前の話で55。 私はと呼ばれる機能を持っています 検索私はすることができます Nこれを通過して、再帰的に検索 サブツリーだけリターン 何でもその答え。 他の私はここにいくつかの最終的なベースケースを持っています。 最後のケースは何ですか？ ツリーは、どちらかnullです。 私はどちらかを探していた値であります それより小さいかそれよりも大きいです またはそれに等しいです。 そして、私は同じと言うことができます 等しく、しかし論理的にそれはです ちょうどここに、他の言うのと同等。 だから、本当の私は何かを見つける方法です。 だから、うまくいけば、これは さらに説得力のある例 愚かなシグマ関数より 私たちは、戻っていくつかの講義を行いました どこにループを使用するのも簡単でした 1からすべての数字をカウントアップします データ構造を持つ。ここでNに 自身が再帰的であること 我々は今、定義され、再帰的に描かれました 自分自身を表現する能力を持っています コー​​ド自体は再帰的です。 だから、これはここにまったく同じコードです。 だから我々は、他のどのような問題を解決することができますか？ 離れてからだからクイックステップ ちょっと木。 ここではドイツのフラグは、たとえば、あります。 そして、明らかにありま​​す このフラグのパターン。 そして、たくさんのがあります 世界のフラグいます 点では、このような単純なされています その色やパターンの。 これは以下のように格納されていると仮定する .GIF、またはJPEG、ビットマップ、またはpingを実行、 グラフィカルファイル形式 これであなたは、精通しています 私たちがしているそのうちのいくつか PSET4で一緒に遊ん。 これは、保存する価値は思えません 黒画素、黒画素、黒画素、 ドット、ドット、ドット、の全体の束 最初の走査線用の黒画素、 その後または行の全体の束 同じ、その後、全体の束 同じ、およびその後の 赤色画素の全体の束、 その後、赤色画素、赤色画素、全体 黄色ピクセルの束、黄色、右？ ここで、このような非効率性があります。 どのように直感的にあなたのだろう ドイツの旗を圧縮 ファイルとして、それを実装する場合は？ どのような情報のように、私たちがすることはできません ために、ディスク上に保存する気に 私達のファイルサイズが等から減少させます キロバイト、何かにメガバイト 小さいですか？ ここで冗長性があります ここで明確にするには？ 君に何ができただろうか？ うん？ その通りです。 なぜではなく、覚えています すべてのくそピクセルの色 ちょうどあなたがPSET4でやっているような ビットマップのファイル形式と、 なぜあなたは単に表すものではありません 例えば、画素の左端の列、 黒画素の束、束 赤、黄の束の、 して、ちょうど何とかエンコード 繰り返しのアイデアこの100回 または、この千回繰り返しますか？ どこに100または1,000です ちょうど整数、あなたので、 ただ一つの番号で逃げることができます 代わりに何百、何千もの 追加のピクセル。 そして実際、それはどのように我々です ドイツの旗を圧縮することができます。 と フランス国旗について今度は何なの？ のいくつかの並べ替えとリトル 頭の体操、どのフラグ ディスクの詳細を圧縮することができますか？ ドイツのフラグまたはフランス語 フラグ、我々はそのアプローチを取る場合はどうなりますか？ ドイツの旗、ありますので、 より水平冗長。 そして設計により、多くのグラフィックファイル フォーマットは確かに走査線として機能します 水平。 彼らは仕事ができます 垂直方向に、ちょうど人間性 決め年前、我々はよ 一般的に物事の行を考えます 列で行の代わりに列で。 だから、実際にあなたがいた場合 ファイルを見て ドイツの旗の大きさとフランス フラグ、限り解像度があるとして、 同じ、同じ幅 高さ、この1 ここでは、大きくなるとしているあなたのために 自分自身を3回繰り返す必要があります。 あなたは青、繰り返しを指定する必要があります 自分では、白、赤、自分自身を繰り返します 自分自身を繰り返します。 あなたはすべて行くことができません 右への道。 また余談として、作るために 圧縮をクリア これらのであれば、どこにでもあります video--あなたからの4つのフレーム その映画を思い出すかもしれません またはビデオは、一般的です 毎秒29または30フレームのように。 それはあなたの小さなフリップブックのようなものです ちょうど画像、画像、画像、画像を参照してください、 画像それがどのように見えるので、ちょうど超高速 画面上の俳優が移動しています。 ここで熊蜂のです 花の束の一番上。 そして、それは一種のかもしれませんが 最初の一目で確認するのは難しいです、 に移動する唯一のもの この映画は、蜂です。 何保管についてのダムです ビデオは非圧縮しますか？ これは、ビデオを保存するために、廃棄物のようなものです 4ほぼ同一の画像のようなもの のみ限り蜂がどこにあるかのように異なります。 あなたは、ほとんどを捨てることができます その情報の そして、だけ覚えて、例えば、 最初のフレームと最後のフレーム、 あなたがしている場合はキーフレーム これまでに、単語を聞きました わずかに格納 蜂があるミドル。 そして、あなたがする必要はありません 、ピンクのすべてを保存します そして青、及び 緑の値も同様に。 だから、これはのみということです 圧縮はどこにでもあります。 それは私たちがよく使うテクニックです または許可されて、これらの日のために取ります。 しかし、どのようにテキストを圧縮していますか？ どのようにテキストを圧縮して行くのですか？ さて、文字のそれぞれに ASCIIは1バイト、または8ビットです。 そして、それは一種のダム、右ですか？ あなたはおそらく、Aを入力しているため EとIとOとUたくさん より頻繁に、WまたはQまたはZ様より、 で、言語に応じて あなたは確かに書いています。 そして、なぜ我々が使用しています すべての文字のための8ビット、 少なくとも含みます 人気の文字、右？ 以下のためのより少ないビットを使用しないのはなぜ 超人気の手紙、 Eのように、物事はあなたが推測します 運命の輪の最初の、 そして、のために多くのビットを使用します あまり人気の手紙？ なぜ？ 私達はちょうどしようとしているため、 あまり頻繁にそれらを使用しています。 まあ、それはそこに持っていることが判明 これを行うために作られた試みであっ。 そして、あなたはグレードからリコール場合 学校や高校、モールス信号。 モールス信号は、ドットを持っています ダッシュができること ワイヤに沿っとして送信 ある種の音や信号。 しかし、モールス信号はスーパークリーンです。 これは、バイナリシステムのようなものです あなたは、ドットやダッシュを持っています。 しかし、あなたは、例えば、2つのドットが表示された場合。 それとも、オペレータに戻ってと思われる場合 誰がビープ音​​、ビープ音、ビープ音のようになり、 ビープ音、少しトリガーを打ちます それは、信号を送信し、 あなたならば、受信者は、2を受け取り、 ドットは、あなたがどの​​ようなメッセージを受信しましたか？ 完全に任意。 私？ 私？ または何about--またはI？ 多分それはちょうど2つのEの右でしたか？ したがって、この問題があります モールスでデコード可能の コー​​ド、それによってない限り あなたのメッセージを送信した人 実際にそのようにあなたが並べ替えることができます一時停止 参照または文字間のギャップを聞き、 それだけに十分ではありません 0と1のストリームを送信し、 ドットやダッシュや、 曖昧さがありますので。 Eは単一のドットであるので、あなたの場合 2つのドットを参照するか、2つのドットを聞き、 多分それは2つの電子のですか多分それは1 I.です だから我々はのシステムを必要とします それよりももう少し賢いです。 だから、男の名前ハフマン年 前まさにこの思い付きました。 だから我々はちょうどつもりです チラッを取ります どのように木はこれに密接な関係がある。 これはいくつかあるとし あなたが送信する愚かなメッセージ、 ただ、A、B、CのDのとEのから構成され、 しかし、冗長性の多くはここにあります。 これは、英語であることを意味していません。 これは、暗号化されていません。 それはちょうど愚かなメッセージです 繰り返しの多いです。 ですから、実際にすべてのアウトカウント場合 A、Bの、Cの、Dの、およびEの、ここです 周波数。 文字の20％です 手紙の45％ Eさん、3他の周波数です。 我々は、手動であっカウントアップ ちょうど数学をしました。 だから、ことが判明 ハフマン、いくつかの時間前に、 あなたが知っている、ことを実現 何を、私は建物を起動した場合 木、または木の森、あなたがする場合は、 次のように、私は次の操作を行うことができます。 私はそれぞれにノードを与えるつもりです 私が気に手紙の 私は保存するつもりです そのノードの内部 浮動小数点として周波数 値は、またはあなたは、あまりにも、Nそれを使用することができます しかし、我々はちょうどここにフロートを使用します。 そして、そのアルゴリズム 彼は提案しますということです 単一ノードのこの森を取ります 木なので、超短木、 そしてあなたがそれらを接続開始します 新しいグループ、新しい両親​​、可能ならば。 そして、あなたが選択することによってこれを行います 一度に2最小周波数。 だから私は、10％と10％を取りました。 私は、新しいノードを作成します。 そして、私は20％の新しいノードを呼び出します。 どの二つのノード私は次の組み合わせ？ それは少しあいまいです。 だから、いくつかのコーナーケースがあります 検討したが、かなりのものを維持するために、 私は20％を選択するつもりです - 私は今、子供たちを無視します。 私は20％を選択するつもりだと 15％と、2つの新しいエッジを描きます。 そして今、これは、2つのノード 私は論理的に結合するのですか？ すべての子を無視し、すべての 孫は、ちょうど根を見て 今。 私は、どの2つのノードが一緒に結ぶのですか？ ポイント2と0.35。 だから私は、2つの新しいエッジを描画してみましょう。 そして、私は唯一の左を持っています。 だからここツリーです。 そして、それは意図的に描かれています 種類のかわいい探すために、 しかし、エッジが持っていることに気づきます また、0と1のラベル付けされて。 だから、左エッジのすべてがゼロであります 任意に、しかし、一貫して。 すべての権利エッジはものです。 そしてそうホフマンは、提案されているもの あなたはBを表現したい場合は、 数66を表すのではなく、 8全ビットであるアスキー、 あなたは何、ちょうど店を知っています パターンゼロ、ゼロ、ゼロ、 ゼロ、それはパスだから 私のツリーから、氏ハフマンの木、 ルートからリーフまで。 あなたが保存したい場合は Eは、対照的に、しないでください E.を表す8ビットを送信します 代わりに、ビットのどのパターンを送信しますか？ 1。 そして、これがあるのいいものです そのEは最も人気のある文字です、 あなたが使用しています それのための最短のコード。 次の最も人気のあります 手紙はそれのように見えます A.だったので、どのように多くのビット 彼はそのために使用して提案したのですか？ ゼロ、1。 そして、それは実現していますので、 今のところ、この木のように 私はあります規定しましょう モールスのように曖昧ません コー​​ド、すべての理由 あなたが気に手紙 これらのエッジの端部にあります。 だから、ただ一つです 木の応用。 これはis--と私は波よ どのようにこの時私の手 C構造体としてこれを実装する場合があります。 私達はちょうど結合する必要があります 記号、文字のような、 左右での周波数。 しかし、ここでは、2つを見てみましょう 最後の例あなたはよ 後にはかなり慣れます 問題でクイズゼロが5に設定します。 そのようにデータ構造が存在します ハッシュテーブルとして知られています。 そして、ハッシュテーブルは一種のです それはバケツを持っていることで冷却し​​ます。 そして、4バケットがあると仮定し ここでは、わずか4空白。 ここでは、カードのデッキだと、ここにあります クラブ、スペード、クラブ、ダイヤモンド、クラブ、 ダイヤモンド、クラブ、ダイヤモンド、 clubs--ので、これはランダムです。 ハーツ、hearts--ので、私はよ ここではすべての入力をbucketizing。 ハッシュテーブルのニーズ あなたの入力を見て、 して、一定に入れ あなたが見たものに基づいて配置します。 それはアルゴリズムです。 そして、私はスーパーを使用していました 簡単な目視アルゴリズム。 最も難しい部分はありました 写真は何であったか覚えて。 そして、合計4つのものがあります。 今スタックは、成長しました ここでは意図的な設計上のものです。 しかし、私は他に何を行う可能性がありますか？ だから、実際にここで私たちが持っています 古い学校の試験の本の束。 の束と仮定 学生の名前はここにあります。 ここで大きなハッシュテーブルです。 代わりに、バケットが4つの、 私が持っている、のは、26をしましょう​​。 そして、我々は26を借りに行きたくありませんでした 外[からのもの？アネンバーグ？]ので、 ここで表す5です 〜Zのそして私の場合 その名で始まり、学生を参照してください、 私はそこに彼または彼女のクイズを置くつもりです。 誰かがCで始まる場合、あそこ、 A--実際に、それを行うにはしたくありませんでした。 Bは、ここを乗り越えます。 だから私は、AとBとCを持っていると 今ここに他の生徒です。 このハッシュ・テーブルがある場合 配列で実装、 私は種類のネジ止めています この時点で、右？ 私は一種のこのどこかに配置する必要があります。 だから私はこの問題を解決することができます一つの方法はすべて、あります 右、Aがビジー状態である、Bがビジーである、Cがビジー状態です。 私は、だからDに彼を置くつもりです 最初、私はランダム瞬時にアクセスを持っています 学生のためのバケットのそれぞれに。 しかし、今では、委譲のようなものです 何かリニアに、 私は誰かを検索する場合のため 名前がAで始まる、私はここで確認してください。 しかし、これはAでない場合 私が探している学生、 私は種類のチェックを開始する必要があります バケツ、私がやったので、 ソートの直線的でした データ構造を調べます。 ちょうど見えるというのが愚かな方法 最初に使用可能な開口部のために、 そして、、いわば、プランBと置きます この場合、またはプランD、値 その場所に代わりに。 あなたがきた場合、これはちょうどようにあります 26場所となしの学生を持って 名前のQまたはZ、またはのようなもので ことは、少なくともあなたは、スペースを使用しています。 しかし、我々はすでに、より多くのを見てきました ここに巧妙なソリューションは、右？ あなたの代わりに何をするだろう あなたは衝突を持っている場合はどうなりますか？ 二人が持っている場合 何だろう名A、 賢く以上となっています ちょうどより直感的なソリューション DがあることになっているAを入れて？ なぜ私は行っていません [外？アネンバーグ？]、 malloc関数、他のノードのように、それを置きます ここで、その後、ここで学生ということに置きます。 私は基本的に持っているように、 配列のいくつかの種類、 または私たちがしているように、多分よりエレガント リンクリストを見るために開始。 だからハッシュテーブルは構造体であります それは、ちょうどこのようになります。 しかし、より巧みに、あなたが何かと呼ばれます 別々の連鎖、それによってハッシュテーブル 非常に単純にアレイの各々は、あります その要素数ではありません、 それ自体は、リンクされたリストです。 あなたは超高速アクセスを得るようにするには ここにあなたの価値をハッシュを決めます。 多くのカードの例と同様に、 私は超迅速な意思決定をしました。 ハーツダイヤモンドはここに、ここに行きます。 ここでは同じ、Aは、ここに行きます DはBはここに、ここに行きます。 だから、超高速ルックアップ、および場合 あなたはケースに遭遇してしまいました あなたが持っている衝突、2 同じ名前の人たち、よくして あなたはそれらをリンク開始します。 そして多分あなたはそれらをソートしておきます アルファベット順に、多分あなたはしないでください。 しかし、少なくとも今はダイナミズムを持っています。 だから、一方で我々は、超高速の持っています 一定時間、および線形時間の種類 これらのリンクリスト場合関与 少し長くなるが開始されます。 だから、愚かなこの種の、 マニアックなジョーク年前。 CS50ハック - ソンでは、 学生はチェックインの際、 いくつかのTFまたはCA毎年 それは我慢し面白いと思っ このような記号、それだけ あなたの名前がAで始まる場合を意味し、 この道を行きます。 あなたの名前が開始された場合 Bで、this-- [OK]を移動し、 それは多分、後学期で面白いです。 しかし、別のがあります あまりにも、これを行う方法。 バックそれに来ます。 したがって、この構造があります。 そして、これが私たちの最後です 今日のための構造、 これはトライと呼ばれるものです。 何らかの理由で短いT-R-I-E、 検索のために、それはトライと呼ばれています。 だから、トライは別の興味深いです これらのアイデアの多くのアマルガム。 それは、今まで見てきた木、です。 これは、二分探索木ではありません。 それは、子どもの任意の数の木です トライの子供のが、各 配列です。 サイズの配列、言う、26または多分27 あなたはハイフネーションされた名前をサポートする場合 または人の名前でアポストロフィ。 そしてこれは、データ構造です。 そして、あなたは上から見ると 下に、あなたの場合のように であり、そこにトップノード、Mを見て そこに一番左のものを指し、 次いで、A、X、W、E、Lは、Lが、これはです 任意にそのちょうどデータ構造 人の名前を記憶しています。 そして、マクスウェルはちょうど次によって保存されています 配列への配列への配列のパス。 トライは約しかし、驚くべきものです リンクリストのに対し、さらには、その アレイは、私たちが今まで得てきた最高です 線形時間または対数時間探し 誰かアップ。 トライのこのデータ構造で、もし 私のデータ構造は、その内の1つの名前を持っています 私はマクスウェルを探しています、私はよ かなり迅速に彼を見つけるつもり。 私は、M-A-X-W-E-L-Lを探します。もし このデータ構造は、対照的に、 あるかどうか、Nは、万人である場合 このデータ構造100万名、 マクスウェルはまだあることを行っています ただ、M-A-X-W-E-L-Lの後に発見 ステップ。 そしてDavid-- D-A-V-I-Dの手順を実行します。 言い換えれば、構築することにより、 データ構造 そのすべてが、これらの配列のすべてを、持って それ自体は、ランダムアクセスをサポート 私は人々ののを見て開始することができます な時間の量を使用して名前 ない数に比例 データ構造内のものの、 百既存の名前のように。 それを見つけるために私を要する時間 M-A-X-W-E-L-Lこのデータ構造であります 比例せずに データ構造のサイズは、 しかし、名前の長さ。 そして現実的に 私たちが見上げている名前 長いクレイジーになるだろうことはありません。 たぶん誰かが10文字を持っています 、20文字の名前です。 それは右、確かに有限ですか？ 地球上の人間が誰ですか 可能な限り長い名前を持っています、 しかし、その名前は一定であります 値の長さは、右？ それは、いかなる意味においても変化しません。 だから、このように、我々はしました データ構造を達成し それは、一定の時間ルックアップです。 これは、ステップ数を取るん 入力の長さに応じて、 しかし、名前の数ではありません データ構造です。 だから我々は、名前の数を倍増場合 億から20億に来年、 マクスウェルを見つけること取るために起こっています 7つのステップの正確な同じ数 彼を見つけることができます。 そして、私たちは達成しているように見えます 時間を実行している私たちの聖杯。 だから、迅速な発表のカップル。 クイズゼロが来ています。 コー​​スのウェブサイト上でその上のその他の 日の次のカップルを超えます。 月曜日のそれは休日ですlecture-- ここでハーバード大学の月曜日に。 これは、ニューヘブンではありません 私たちはクラスを取っています 月曜日の講義のためのニューヘブンに。 すべてが撮影されます そして、、いつものように、ライブストリーミング しかし、今日は終了してみましょう 30秒のクリップで 「ディープ思考」と呼ばれます 祈るファーナム、これによって、 土曜日昨年触発されました ナイト・ライブの「ディープ思考」 ジャック・ハンディ、これによって、 今の意味を確認する必要があります。 FILM：そして今、「ディープ 祈るファーナムによって思考」。 ハッシュテーブル。 SPEAKER 1：すべての権利、それは今のところこれだけです。 私たちは来週お会いしましょう​​。 DOUG：アクションでそれを見るために。 それでは、今それを見てみましょう。 そこでここでは、我々は、ソートされていない配列を持っています。 IAN：ダグ、あなたが先に行くことができますし、再起動 ちょうど1秒これでお願いします。 すべての権利は​​、カメラがそのように、展開しています あなたは準備ができているときはいつでも、アクション、ダグ、OK？ DOUG：すべての権利なので、私たち ここでソートされていない配列である必要があります。 そして、私はすべての要素を着色しました それが実際にあることを示すために赤、 ソートされていません。 そこで、まず私たちが行うことを思い出してください 私たちは、アレイの左半分を並べ替えるです。 その後、我々は権利を並べ替えます 配列の半分。 そして、YA-DA、YA-DA、YA-DA、 私たちはそれらを一緒にマージされます。 そして、我々は完全にソートされた配列を持っています。 だから、働くマージソート方法です。 IAN：おっ、おっ、おっ、 カット、カット、カット、カットします。 ダグ、あなただけのYA-DAことはできませんが、YA-DA、 YA-DA、マージソートを通してあなたの方法。 DOUG：私はちょうどでした。 それは大丈夫です。 私たちは行ってもいいです。 ちょうどローリングを維持しましょう​​。 とにかく、 IAN：あなたは説明する必要があります それより完全にそれよりも。 それはちょうど十分ではありません。 DOUG：イアン、私たちにはありません 1に戻って行く必要があります。 それは大丈夫です。 とにかく、我々はmerge--を続ける場合 イアンは、我々は撮影の真ん中にいます。 IAN：私は知っています。 そして、私たちはただYA-DAことはできませんが、YA-DA、 プロセス全体を通してYA-DA、。 あなたはどのように説明する必要があります 両者を一緒にマージされます。 DOUG：しかし、我々はすでにしました 説明方法2 sides-- IAN：あなただけ示してきました それらマージ配列。 DOUG：彼らは、プロセスを知っています。 彼らはいいですよ。 私たちは、その上に10回行ってきました。 IAN：あなたはちょうどその上にスキップ。 私たちは、1に戻るつもりだ、あなた あなたYA-DA、YA-DAそれ以上のことはできません。 1つ前に、すべての権利。 DOUG：私は戻って行かなければなりません スライドのすべてを？ 我が神よ。 これは6回目、イアンのようなものです。 それは大丈夫です。 IAN：すべての権利。 あなたは〜を用意する？ グレート。 アクション。