[音楽再生] ANDI PENG：セクションの週6へようこそ。 私たちは、標準から外れました 火曜日の区間時間 この素敵な日曜日の朝に午後。 その誰もしていただきありがとうございます 真剣に、今日私に参加しましたが、 拍手。 これはかなり大きな努力です。 私はほとんども、それをしませんでした 時間のアップが、それはOKでした。 だから私はあなたのすべてを知っています ただクイズにそれを作りました。 まず第一に、へようこそ そのの裏返し。 第二に、我々はそれについて話しましょう​​。 私たちは、クイズについて話しましょう​​。 私たちはどのようにについて話しましょう あなたはクラスでやっています。 あなたは大丈夫です。 私はあなたのためのクイズを持っています ここの最後にあなた、 だから君たちは取りたい場合 完全に罰金それを見、。 だから、すぐに私たちは始める前に、 次のように今日の議題です。 あなたが見ることができるように、私たちはしています 基本的に迅速な発射 データ構造の全体の束を通って 本当に、本当に、本当にすぐ。 以下のようなので、それができなくなります 今日スーパーインタラクティブ。 それはちょうど私が一種の叫びになるだろう 物事あなた、そして私はあなたを混同している場合、 私は速すぎるつもりならば、私に知らせてください。 彼らはただ、様々なデータです 構造、および一部として このため、あなたのPSETの 来週、あなたはよ それらのいずれかを実施するよう求められ、 おそらく、それらの2つthem-- 2の あなたのpsetインチ [OK]をので、私はちょうどに行きますよ いくつかの発表で始まります。 我々は、より多くのでスタックとキューの上に行きますよ 私たちはクイズの前に何をしたかよりも深さ。 我々は、リンクの上に行きますよ 、もう一度、もう一度リスト 何よりも深さより 私たちは、クイズの前に持っていました。 そして、我々は、ハッシュについて話しましょう テーブル、木や試行、どの すべてのあなたのpsetのためにかなり必要です。 そして、我々はいくつかの上に行きますよ pset5に役立つヒント。 [OK]を、ので、クイズ0。 平均は58％でした。 それは非常に低く、従って皆​​さんすべて 合わせて、非常に、非常によくやりました それと。 あなたがしている場合、かなり、親指のルールがあります 平均値の標準偏差内 我々は少ないにしている、特に以来 快適なセクション、あなたは完全に罰金です。 あなたが軌道に乗っています。 人生は良いです。 私はそれがことを考えると怖いです知っています 私はこのクイズには40％のようになりました。 私はこのクラスを失敗するつもりです。 私はあなたを約束、あなたがいないなら クラスを失敗するだろう。 あなたは完全に罰金です。 乗り越え人のために 平均、印象的な、印象的な、 以下のように、真剣によくやりました。 私は私と一緒にそれらを持っています。 それらを得るお気軽に セクションの最後に。 あなたがいずれかを持っているなら、私に教えてください 問題、彼らとの質問。 私たちはあなたのスコアを追加した場合 間違って、私たちに知らせてください。 [OK]を、pset5ので、これは本当にあります 意味でのエールのための奇妙な週 私たちのPSETが原因であること 含む正午水曜日 ので、それは実際に遅く日です 正午火曜日理論的に起因します。 おそらく誰もが終わっていません 正午火曜日に。 それは完全に罰金です。 私たちは、オフィスの時間を持っているとしています 今夜だけでなく、月曜の夜。 そして、すべてのセクション、今週はなります 実際にワークショップに変えられます、 そうでポップ気軽に あなたが望む任意のセクション、 彼らは一種のミニPSETになるだろう その上で助けをワークショップ。 そうのような、これが唯一の部分であります ここで、我々は材料を教えています。 他のすべてのセクションは、フォーカシングされます もっぱらのpsetのヘルプに。 うん？ 対象：営業時間はありますか？ ANDI PENG：オフィス・アワー ああtonight--、良い質問。 私は思うの営業時間今夜 ティールまたはコモンズです。 あなたがオンラインCS50をチェックします あなたは、オフィスの時間に行きます そのスケジュールがあるはずです それらのすべてがどこにあるかがわかります。 私は今夜​​のいずれかを知っています または明日はティールです、 私は、我々が持っているかもしれないと思います 他の夜のためのコモン。 よく分かりません。 良い質問。 CS50に確認してください。 クール、ご質問 三日のように、次のスケジュール？ 私はデビッドのような君たちを約束 これは丘の上である、と述べました。 君たちはほとんどあります。 わずか3日以上。 そこに取得し、我々はすべて降りてくるでしょう。 私たちは素敵なCS-無料休憩があるでしょう。 お帰りなさい。 私たちはウェブに飛び込みますよ プログラミングと開発、 比較して非常に楽しいですもの 他のpsetの一部に。 そして、それは寒さもあり、よ 私たちはたくさんの楽しみがあるでしょう。 我々は、より多くのキャンディがあるでしょう。 キャンディのため申し訳ありません。 私はお菓子を忘れてしまいました。 それは荒い朝でした。 だから、あなたたちは、ほとんどがあります 私はあなたたちの本当に誇りに思っています。 [OK]を、ので、スタック。 誰がジャックについての質問を追加しました クイズの彼の服？ 誰も？ [OK]を、それは大丈夫です。 だから、基本的にすることができますように 絵ジャック、ここでこの男、 服を取るのが大好き スタックのトップのうち、 彼は上に戻ってそれを置きます 彼の後にスタックが行われています。 だから、このように、彼は決してありません なっているように見えます の下に 彼の衣服にスタック。 だから、これは一種の説明します 基本的なデータ構造 スタックがどのように実装されるかの。 基本的に、考えます オブジェクトの任意のスタックとして積み重ね あなたが一番上に物を置くと、どこ あなたは上からそれらを飛び出し。 だからLIFOは、私たちが好きな頭字語であります 最後には、まずアウトuse--します。 だからの上部に続きます スタックが出てくる最初のものです。 それで二つの用語 我々は関連付けるのが好き それにプッシュとポップと呼ばれています。 あなたは上に何かを押すと スタック、あなたはバックアップそれをポップ。 だから私は、これは一種のだと思います あなたのそれらのための抽象的な概念 誰のように見てみたいです これの実際の実装 現実の世界です。 どのように多くのあなたのエッセイを書かれています 多分それが原因だったの1時間前のように、 あなたが誤って巨大な削除しました 偶然のようなそれの塊、？ そして、どのような制御を行います 我々はそれを戻すために使用できますか？ コントロール-Z、ええ？ コントロール-Zので、倍の量 コントロール-Zは私の命を救ったこと、 、毎回私のお尻を保存しています それは、スタックを介して実装です。 基本的にすべての情報 それは、Word文書上にあります それは意志でプッシュし、ポップされます。 だから基本的にいつでもあなた 何かを削除、あなたはそれをバックポップ。 そして、あなたは背中にそれを必要とする場合、あなた Control-Cをが何をしている、それを押してください。 だから現実世界の機能 どのように単純なデータ構造の あなたの日常生活を支援することができます。 だから、構造体はそのようです 私たちは実際にスタックを作成します。 それから、構造体を定義し入力し、 私たちは、一番下にあるスタックを呼び出します。 そして、スタック内の、 我々は2つ​​のパラメータを持っています 私たちは基本的に操作することができ、 私たちは、charスター文字列能力を持っています。 それはやっているすべてのこと 配列を作成しています 私たちは、あなたが好きな格納できます これは私たちがその能力を決定することができます。 容量は、単に最大量であり、 アイテムは、我々はこの配列に入れることができます。 int型のサイズが保持するカウンタであります 現在どのように多くの項目のトラック スタックインチ それでは、私たちは、A、を追跡することができます 両方の実際のスタックがどのように大規模な、 そして、B、どのくらいそのスタックの 我々はしたくないので、私たちは満たさ 私たちの能力が何であるかを超えるオーバーフローします。 例えば、この素敵なそう 質問はクイズにありました。 基本的に私たちはプッシュしない方法 スタックの一番上に。 非常にシンプル。 あなたがそれを見れば、 我々はこの中を歩きますよ。 [聞こえない]場合size-- 覚えて、いつでもあなた いずれにもアクセスしたいです 構造内のパラメータ、 あなたはstruct.parameterの名前を行います。 この場合、sは 私たちのスタックの名前。 我々は、サイズにアクセスしたいです それを、私たちはs.sizeありません。 サイズがないようであれば、 容量に等しいか、または限り それは容量以下だとして、 ここでも動作します。 あなたは内部にアクセスしたいです あなたのスタックの、s.stringsので、 あなたはその新しい番号を置くつもりです あなたはそこに挿入すること。 ちょうど私たちがしたいと言ってみましょう スタックにint型のnを挿入し、 我々はs.stringsを行うことができ、 ブラケット、s.sizeは、nに等しいです。 どこサイズがあるので 現在スタックにあります 我々は、プッシュするつもりなら その上に、私たちだけでアクセス どこサイズであります スタックの現在の膨満感、 我々はそれにint型のnを押してください。 そして、我々はことを確認します 我々はまた、n個のサイズをインクリメントしています 私たちはきた私たちを追跡することができます スタックに余分なものを追加しました。 今、私たちはより大きなサイズを有します。 これは、ここに意味がありますか それがどのように動作するか、論理的に皆、？ それは一種の速かったです。 聴衆：あなたはオーバー行くことができます s.stringss.strings【s.size]再び？ ANDI PENG：確かに、そう何がします s.size現在私たちを与えますか？ 観客：それは現在のサイズです。 ANDI PENG：その通りなので、 私たちのサイズがである​​現在のインデックス、 そのため、私たちは新たな整数を配置します 我々はs.sizeに挿入すること。 それは理にかなっていますか？ s.stringsため、すべてのこと 配列の名前です。 それはすべてがアクセスしています 私たちの構造内の配列、 そして私たちがしたい場合は そのインデックスにn個を配置し、 我々はそれにアクセスすることができます 使用してブラケットをs.size。 クール。 すべての権利、ポップ、私はそれを擬似コード あなたたちが、同様のコンセプトのため。 それは理にかなっていますか？ サイズが大きい場合 ゼロよりも、あなた あなたが何かをしたいことを知っています サイズがない場合は理由アウト ゼロより大きく、そしてあなた スタックには何もありません。 だから、あなただけ実行したいです このコード、それができるだけで ポップするものがある場合にポップ。 そのようにサイズが大きい場合 0よりも、私たちマイナスサイズ。 我々は大きさを減分してから戻ります それのために内部で何でもあります ポップし、私たちがしたいです 保存されているものは何でもアクセス スタックの先頭のインデックスです。 すべてが理にかなって？ 私が作った場合、あなたたちは、これを書き出します あなたたちはそれを書くことができるでしょうか？ [OK]を、あなたたちはそれで遊ぶことができます。 あなたはそれを取得しない場合、心配はありません。 私たちは、コーディングする時間を持っていません それアウト今日我々がきたので、 これらの構造の多くを持っ 基本的に通過するが、これに 擬似コード、非常に、非常に似てプッシュします。 ただ、ロジックに沿って従ってください。 あなたはすべてのアクセスしていることを確認してください 正しく構造体の特徴。 うん？ 聴衆：ウィルこれらのスライドと この全体のことは今日までっぽいこと？ ANDI PENG：常に、うん。 私が配置しようとするつもりです このアップ後の時間のように。 私はデビッド、ダビデはしようとしますメールでお知らせいたします この後の時間のようにそれを置きます。 [OK]を、ので、我々は、この他に移動します 素敵なデータ構造は、キューと呼ばれます。 あなたたちはここで見ることができるように、 私たちの中で、英国のキュー、 それはすべての行です。 何に反してそう あなたはスタックがあると思いますが、 キューは、正確に何であります 論理的に、あなたはそれだと思います。 これは、FIFOのルールが保持しています これはファーストイン、ファーストアウトです。 あなたが最初にしている場合 ライン内の1つ、あなたがしています 最初のもの ラインから出てきます。 だから我々はこれを呼び出すために好きなもの デキューとエンキューされます。 私たちは何かを追加したい場合 私たちのキューに、私たちはエンキュー。 我々はデキュー、または利用したい場合 何かが離れて、​​我々はデキュー。 我々は一種のだそう同じ感覚 我々の固定サイズの要素を作成します 特定の保存することができます 物事が、我々はこともできます 我々が配置している変更 それらの内部パラメータ の種類に基づいて、 機能我々が欲しいです。 だから、最後のを望んでいた、スタック 1、N個の第1の1した可能性があります。 キューは、我々は最初のものをしたいです で出て最初にすることができます。 だから、構造型 あなたが見ることができるように、定義され、 それは少し違います スタックがあったものから ためだけでなく、我々は維持する必要があります サイズが現在どこのトラック、 我々はまた、ヘッドのトラックを維持したいです だけでなく、どこに我々は現在。 だから私はそれが簡単だと思います 私はこれを描きます。 それでは、私たちはキューを持って想像してみましょう、 それでは、ヘッドが右ここにあるとしましょう​​。 行の先頭には、してみましょう ただ、それが現在だと言います 我々は挿入したいです キューに何か。 私は基本的にサイズを呼ぶつもりです 尾と同じものであり、 あなたのキューがあるどこの終わり。 ちょうどサイズはここで言ってみましょう。 それでは、どのよう1都合良くはありません キューに何かを挿入しますか？ どのような指標我々が配置したいです 我々は挿入する場所。 これはあなたの始まりである場合 キューに入れ、これはそれの終わりです 我々がそれを行うのか、大きさ、 次のオブジェクトを追加したいですか？ 聴衆：[聞こえません] ANDI鵬：まさに、あなたが追加したいです それはあなたがそれを書かれているに応じて。 このいずれかが空白であるか、それが空白になっています。 だから、おそらくそれを追加したいです こちらのサイズis--場合 これらはすべて完全であれば、あなたがしたいです 右、右ここでそれを追加するには？ 非常に、非常にしながら、そしてそうそれは、です シンプルではなく、かなり常に正しいです 主な違いのため キューとスタックの間 キューができるということです 実際に操作することが そのように頭の変更 希望する場所に応じて あなたのキューの先頭が開始します。 その結果、あなたの尾 また、変更する予定です。 だから見てみましょう 今、このコード。 君たちもするように求めていたように エンキュー、クイズに書き出します。 多分私達はなぜを通して話しましょう 答えはそれが何であったかでした。 私はかなり、1にこのラインに合うことができませんでした コー​​ドの本質的にこ​​の作品 1行でなければなりません。 30秒のようにお過ごしください。 見てください、とその理由を参照してください。 これは、ある方法です。 非常に、非常によく似た構造体に、非常に、非常に 前回と同様の構造 おそらく以外のスタック 1行のコード。 そして、1行のコードこと 機能性を決定します。 そして、それは本当に差別化 スタックからキュー。 誰もが刺しを取りたいです あなたがきた理由を説明する時 ここでは、この複雑なものがあるの？ 私たちは、のリターンを見ます 素晴らしい友人モジュラス。 あなたたちはすぐに来るように プログラミングに認識するためには、 ほとんどいつでもあなたが何かを必要とします 何を包み込むように、 弾性率は、それを行うための方法になるだろう。 だから、それを知っている、誰もが欲しいん コー​​ド行を説明してみてくださいするには？ うん、すべての答えがあります 一般に認められたと歓迎。 観客は：あなたは私に話していますか？ ANDI PENG：うん。 聴衆：ああ、ない申し訳ありません。 ANDI PENG：OK、そうしましょう このコードを歩きます。 あなたがしようとしているとき キューに何かを追加、 ヘッドが発生した場合には美しいです 右ここに、それは私たちのために非常に簡単です ただ最後に移動します 右の何かを挿入？ しかし、キューの全体のポイントは、 ヘッドが実際に動的にできること どこに応じて変化します 私たちのqのスタートになりたいです、 そのように、尾 また、変更する予定です。 だから、これはなかったことを想像します キューむしろこれは、キューがありました。 ヘッドが右ここにあるとしましょう​​。 私たちのキューがこのように見えたとしましょう​​。 我々はどこにシフトしたい場合 行の先頭であり、 我々は頭をずらしましょう この方法ここサイズ。 今、私たちはに何かを追加したいです このキューが、あなたたちが見ることができるよう、 それだけのように単純ではありません サイズの後にあるものは何でも追加 その後、私たちは外に実行されるため 当社の実際の配列の境界。 私たちは本当に追加したい場合はここにあります。 それはキューの美しさです それはそれは、視覚的に、私たちにあります 行はこのように書きますように見えます、 しかし、データ構造に格納されているとき、 彼らはサイクルなどを与えます。 それは一種のラップアラウンド 前と同じように ラインもラップすることができていること どこに応じて周り なるように行の先頭にしたいです。 そして、私たちが取る場合 ここで下を向いて、してみましょう 私たちが作成したいと言います 関数はエンキューと呼ばれます。 我々は、Qへのint nを追加したいです。 もしq.size q--我々は我々のデータ呼ぶことにします 私たちのqueue.sizeがない場合structure-- 容量の場合、または同等 それは容量よりも少ないですが、 q.stringsは、当社のQ内の配列です。 私たちは、設定しようとしています そのq.headsに等しく、 これは右ここにあり、プラスq.size 容量によって弾性率、これ この辺り私たちをバックラップします。 したがって、この例では、インデックス 頭の右側、1ですか？ サイズのインデックスは0、1、2、3、4です。 だから我々は1プラス4モジュラスを行うことができます 5である私たちの能力によって。 それは、私たちに何を与えるのでしょうか？ そのインデックスとは何ですか このから出てきますか？ 聴衆：0。 ANDI PENG：0、どの 右ここにあることを起こります、 そのため、我々はできるようにしたいです 右ここに挿入します。 ので、ここで、この式は、種 ただの数字で動作します 場所に応じてあなたの 頭とあなたのサイズがあります。 あなたはどのようなものを知っていれば 物事はあなたが知っている、あります あなたが挿入したい場所を正確に 何があなたのキューの後です。 それは誰にでも意味がありますか？ 私は、脳のようなものを知っています 特にこの以来のティーザー あなたのクイズの余波​​で来ました。 しかし、うまくいけば、誰も 今理解することができます なぜこの溶液またはこの 関数は、それがあることの方法です。 その上のビットは不明で誰ですか？ OK。 そして今、あなたの場合 この、デキューしたかったです 私たちの頭がシフトされることになる場所です 我々はデキューした場合ので、 我々はqの端を取ることはありません。 私たちは頭を取りたいですよね？ その結果、ヘッドが変更しようとしています、 あなたはエンキュー時に、なぜ、それは、あります あなたはを追跡するために持っています どこにあなたの頭とあなたのサイズ 挿入することができるようになっています 正しい位置に挿入します。 だからあなたがデキュー時に、 私もそれを擬似コード。 あなたがしたい場合にお気軽に これをコード化しようとしています。 あなたは正しい、ヘッドを移動したいですか？ 私はデキューしたい場合は、私 頭の上に移動します。 これは頭​​になります。 そして、私たちの現在のサイズを希望 引くために私たちは、もはや 配列の4つの要素があります。 我々は3つだけを持っている、と我々はしたいです 内部に格納されていたものは何でも返します 頭の我々はこれを利用したいので、 スタックに非常に非常によく似た値アウト。 ちょうどあなたが取っています 別の場所から、 あなたはあなたのポインタを再割り当てする必要があります 結果として、別の場所へ。 論理的には、誰もが従いますか？ グレート。 [OK]を、私たちは少し話をするつもりです リンクされたリストについての深さより 彼らは非常に、非常に価値があるだろうから 今週の過程であなたのために pset。 あなたたちのようにリンクされたリスト、 、彼らはすべてを覚えています 特定のノードであるノードがあります 値とポインタの両方の値 それは、一緒にリンクされています これらのポインタによって。 そしてそう構造方法について ここでは、ノードを作成し、私たちです である、int型nを持っているものは何でも 店舗や文字列のnの値 またはあなたがしたいものは何でも char型のスターnは、それを呼び出します。 ポインタである構造体のノード星、 あなたは、各ノードで持つようにしたいことを、 あなたはそれを持っているつもりです 次の方へのポインタポイント。 あなたは頭を持っています だリンクリストの 残りを指すように行きます ようになどの値 あなたは、最終的に最後に到達するまで。 そして、この最後のノードだけです ポインタを持っていないつもり。 それはを指すように起こっています nullの場合、それはときです あなたがヒットしました知っています あなたのリンクリストの末尾 あるとき、あなたの最後のポインタ 何を指していません。 だから我々は、より多くのビットを行くつもりです 方法1はおそらくだろうに関する深さ リンクリストを検索します。 のいくつかは何を覚えておいてください リンクリストの欠点 検索に関する配列を詩。 配列することができますバイナリ検索が、 なぜあなたはリンクリストでそれを行うことができないのですか？ 聴衆：彼らはすべての接続されているので、 しかし、あなたは非常にどこかわかりません [聞こえません]。 ANDI PENG：うん、まさにそう覚えています その配列の輝き 私達が持っていたという事実がありました ランダム・アクセス・メモリ場所 私は、インデックスから値を望んでいた場合 6、私はインデックス6を言うことができます、 私はその値を与えます。 配列がソートされているので、それはです メモリの連続した​​領域で 一つの場所で、一方、 リンクリストのようなもの ランダムにすべての周りに散在しています、 あなたがものを見つけることができる唯一の​​方法 示していますポインタを介して行われ その次のノードがどこにあるのアドレス。 そして、その結果、唯一の方法 リンクリストを検索します 線形検索があります。 私は場所を正確に知っているわけではないので リンクされたリスト内の12番目の値であります 私は、全体を横断する必要があります そのリンクリスト1の 最初のノードに頭から一つ、 第2のノードに、第3のノードに、 私は最終的に到達するまでダウンすべての方法 私が探しているそのノードがどこにあるの。 だからこの意味で、検索 リンクリストに常にnです。 それは、常にn個です。 これは、線形時間で常にです。 だからコードするで 私たちはこれを実装し、この あなた以来、あなたたちのために少し新しいです 男は本当にについて話しましたか今までになかったです にどのように見られるのポインタ ポインタを検索、 私たちは歩きますよ この非常に、非常にゆっくりと。 だからブール検索、右、 我々が欲しいのは想像してみましょう 関数を作成するには trueを返す検索 あなたは、リンク内の値を発見した場合 リスト、それがそうでない場合はfalseを返します。 ノードスターリストです 現在だけでポインタ あなたのリンクリストの最初の項目へ。 int型nは、あなたがしている値であり、 そのリスト内を検索します。 だから、ノードスターポインタがリストに等しいです。 それは我々が設定していることを意味します ポインタを作成します リストの内側にその最初のノードに。 私と一緒にみんな？ だから、私達は行くした場合 ここに戻って、私が持っているだろう を指すポインタを初期化します 何でもそのリストの先頭です。 そして、あなたは、ここで降りたら、 ポインタが等しくないヌルを行いながら、 だから、私たちはここでループがあります その後に横断することになるだろう 何のため私たちのリストの残りの部分 ポインタがNULLに等しいときどうなりますか？ 我々はhave--ことを知っています 聴衆：[聞こえません] ANDI PENG：まさに、私たちが知っていること 我々は、右側のリストの最後に到達しましたか！ あなたがここに戻ると、各ノード 別のノードに指している必要があり などなど あなたは最終的にヒットするまで、 あなたのリンクリストの末尾、 これはちょうどそのポインタを持っています なし以外の場所を指していません。 だから、あなたは基本的にはそれを知っています あなたのリストには、まだそこにアップしています ポインタが等しくないまで ヌルがnullに等しいいったんので、 あなたはそれ以上のものがないことを知っています。 だから、私たちがしているというループです 実際の検索を持つことになります。 pointer--を行う場合、あなたはを参照してください。 そこに矢印機能のようなもの？ そこで、n個のポインタを指している場合であれば nのポインタは、nに等しい等しく、 そのためには、場合ことを意味し あなたがしているポインタ 各の終わりにを検索 ノードが値に実際に等しいです あなたがして、探しています あなたはtrueを返したいです。 したがって、基本的に、あなたがそのノードにいる場合 あなたが探している値を持っています、 あなたがしてきたことを知っています 正常に検索できるように。 そうしないと、設定したいです 次のノードへのポインタ。 それはここでその行が何をしているかです。 ポインタは、次のポインタに等しいです。 誰もがそれが働いているかを確認？ そして、基本的に、あなただけのつもり 、リスト全体を横切ります 毎回までポインタをリセットします あなたは最終的にはリストの最後にヒット。 そして、あなたは何があることを知っています 複数のノードは、を検索します そして、あなたはfalseを返すことができます あなたが知っているので、それだけでなく、ああ、 私は検索することができました場合 リスト全体を通じ。 この例の場合、私が望んでいた場合 10の値を探すために、 私は頭に開始し、 私は、ダウンすべての方法を検索 私は最終的には、これに持っています nullに指し示すポインタ、 私はしていない、がらくた、私は10を推測することを知っています このリスト私はそれを見つけることができなかったので。 そして、私は、リストの末尾です。 そして、その場合には、あなたが知っています 私はfalseを返すつもりです。 それは少しのためで浸してみましょう。 これはかなりになります あなたのpsetのために重要。 そのロジックは、おそらく、非常に簡単です 構文的にそれを実現しています。 君たちは作りたいです あなたが理解していることを確認してください。 クール。 [OK]を、私たちはどのようになります 右、ノードを挿入し、 リストにあるため覚えています 利益の何がどのようなもの 対リンクリストを持っていることの ストレージの点で配列？ 観客：それはダイナミックですが、 それは簡単ですto-- ANDI PENG：その通り、 それは、どのダイナミックです それが拡大し、縮小することができることを意味します ユーザのニーズに応じ。 だから、そういう意味では、我々は必要はありません 私ので、不要なメモリを無駄にします 私は私が望むどのように多くの値がわからない場合 保存するために、それは私のために意味がありません ため、配列を作成します 私は10個の値を格納する場合 私は千の配列が、それはだ作成します 無駄なメモリの多くは、割り当てられました。 我々はリンクを使用したい理由です 動的にすることができるようにリスト 変更または当社のサイズを縮小します。 そして、そのためには、挿入を作ります ビットは、より複雑。 我々は、ランダム要素にアクセスすることはできませんので、 私たちは、アレイのような方法。 私は、要素を挿入する場合 第七インデックスに、 私はちょうどそれを挿入することができます 第七インデックスに。 リンクされたリストでは、それはしていません 全く同じように簡単に動作し、 そのため、我々は挿入したい場合 ここにリンクされたリスト内の1つ、 視覚的に、それは見ることは非常に簡単です。 私達はちょうどそこにそれを挿入します、 右側のリストの先頭に、 頭の後に右。 しかし、私たちが持っている方法は、再割り当てします ポインタは少し複雑です または、論理的に、それは理にかなっているが、 あなたはそれを持っていることを確認します 完全にダウンしているため あなたがしたい最後のこと ポインタを再割り当てすることです 私たちがここでやっている方法です。 あなたの場合、間接参照 1頭からポインタ、 その後、突然インクルードのすべて あなたのリンクリストの残りの部分 あなたが実際に持っていないため、失われます 一時的なものを作成しました。 それは2を指摘しています。 あなたはポインタを再割り当てする場合は、 あなたのリストの残りの部分は完全に失われます。 だから、になりたいです ここでは非常に、非常に慎重 最初に割り当てます 何でもあなたからのポインタ どこに挿入します あなたがしたいし、その後 あなたのリストの残りの部分を逆参照することができます。 だから、これはどこに適用されます あなたが挿入しようとしています。 あなたがで挿入したい場合は 頭部、あなたがここに答えるようにしたい場合は、 あなたがで挿入する場合 終わり、よく、最後のI あなただけでしょうね あなたは何のポインタを持っていませんが、 あなたがいないことを確認します あなたのリストの残りの部分を失います。 あなたは、常に確認します 新しいノードが指しています 何でも向かって 挿入します、 そして、あなたはチェーンを上に追加することができます。 誰も明確な？ これは、になるだろう 現実の課題の一つ。 ほとんどの主要な問題の一つ あなたのpsetに必要があるとしています あなたが作成しようとしているということです リンクリストとインサートもの しかしその後、ちょうど失います あなたのリンクリストの残りの部分。 そして、あなたは私のようなことになるだろう なぜこれが起こっているかわかりませんか？ そして、それは通過する痛みです あなたのポインタのすべてを検索します。 そして、私はこのPSETであなたを保証します、 これらのノードを書き出すと描画 非常に、非常に参考になります。 だから、完全に追跡することができます すべてのポインタがどこにいるの、 何が間違って起こっています、 すべてのノードがある場合は、 あなたがアクセスするために何をする必要があるか、または 挿入または削除したり、それらのいずれか。 それで良い誰？ クール。 私たちはコードを見てみたかったのであれば？ ああ、私は知っていない場合は、我々 そう、the-- OK]を見ることができます 一番上にそれはすべての関数であります 私たちが望むという名前の挿入 リンクリストへのint nを挿入します。 我々は、このウォークスルーするつもりです。 それは、多くのコード、新しい構文がたくさんです。 我々はOKになるだろう。 だから、一番上のアップ、いつでも 私たちは何かを作成したいです 我々は、特にあなたならば、何をすべきかが必要です それはスタック上に保存されないようにしたいです しかし、ヒープ内の？ 我々は、右のmallocに行きますか？ だから我々は、ポインタを作成しようとしています。 ノード、ポインタ、新しい等号 ノードのサイズををmalloc 私たちがしたいので、そのノードを作成します。 我々は量をしたいです ノードが占めるメモリ 割り当てられたことにします 新しいノードを作成します。 そして、我々は、にチェックするつもりです 新しい等号がnullに等しいかどうかを確認します。 我々が言ったことを覚えていますか？ どのようなあなたはmalloc関数、 あなたはいつも何をしなければなりませんか？ あなたはいつも見にチェックする必要があります かどうか、それはnullです。 たとえば、オペレーティング このシステムは、完全に満ちていました あなたがでこれ以上のメモリを持っていた場合 すべてのあなたはmalloc関数にしてみてください、 それはあなたのためにnullを返します。 そして、あなたはそれを使用しようとした場合 それがnullに指していたとき、 あなたができるするつもりはありません その情報にアクセスします。 そしてそうのような、我々が作りたかったです いつでもあなたがmallocingしていることを確認し、 あなたは、常にかどうかを確認するためにチェックしています あなたに与えられたそのメモリはnullです。 そうでないなら、我々は移動することができます 我々のコードの残りの部分とに。 だから我々はするつもりです 新しいノードを初期化します。 私たちは、新しいnがNに等しいやろうとしています。 そして、我々がやろうとしています 新しい上に新しいポインタを設定 nullに、今、私たちにはありませんので、 それが指すようにするために何かをしたいです。 私たちはどこ見当がつかない それは、あなたを置くために起こっています し、我々がしたい場合は 頭でそれを挿入し、 その後、私たちは再割り当てすることができます 先頭へのポインタ。 誰もがロジックに従っています それが起こっているどこの？ 私たちがやっているすべては、新たに作成しています ノード、nullにポインタを設定し、 して、再割り当て その頭に、私たちの場合 私たちは頭でそれを挿入したい知っています。 そして、ヘッドがしようとしています その新しいノードに向かって指しています。 それでOK誰？ だから、二段階のプロセスです。 最初に割り当てるために持っています あなたが作成しているものは何でも。 へのポインタを設定します。 あなたを参照してから、 間接参照の種類のことができ 最初のポインタ 新規ノードに向かって指しています。 あなたはそれを挿入したい場合はいつでも、 その論理が成り立つとしています。 それは一種の割り当てのようなものです 一時変数。 あなたが持っている、覚えておいてください 必ずことを確認します あなたがスワッピングしている場合のトラックを失うことはありません。 あなたが持っていることを確認します 種類の保持一時変数 どこにそのことのトラック あなたがそのように保存されています コー​​ス内の任意の値を失うことはありません それいじりようなの。 [OK]を、ので、コードはここになります。 君たちはセクションの後を見てみましょう。 それはあるでしょう。 だから私はどうするかと思います 我々が望んでいた場合、これが異なります 途中または最後に挿入するには？ 誰だかのアイデアを持っています 論理的な基準と擬似コード 我々が望んでいた場合、我々はかかるだろうと 途中に挿入するには？ だから我々はでそれを挿入したい場合 ヘッドは、我々が行うすべては、新しいノードを作成することです。 私たちは、そのポインタを設定 何でも頭に新しいノード、 し、我々は、ヘッドセット 新しいノードに、右？ 私たちは途中でそれを挿入したい場合 リストで、私たちがしなければならないのでしょうか？ 観客：それはまだだろう 同様のプロセスであります ポインタを割り当てるなど そのポインタを割り当て、 しかし、我々はそこに見つけなければならないでしょう。 ANDI PENG：その通り、まさにそう あなたを除いて同じプロセス 場所を正​​確に見つける必要があります その新しいポインタがに行きたいです、 私は挿入したい場合は OK list--リンクの真ん中、 のは、それが私たちのリンクリストだとしましょう​​。 我々は右のそれをここに挿入したい場合は、 私たちは、新しいノードを作成しようとしています。 私たちは、malloc関数になるだろう。 私たちは、新しいノードを作成しようとしています。 私たちは、割り当てするつもりです ここでは、このノードのポインタ。 しかし、問題はそれが異なります ヘッドがどこにあるの 我々は正確に知っていたということです ここで、ヘッドがあります。 それは右、最初は右でしたか？ しかし、ここで私たちはトラックを保つために持っています 我々は中にそれを挿入している場所の。 我々は我々を挿入する場合 ここでノードは、我々が持っています ていることを確認します このノードの前の1 ポインタを再割り当てするものです。 だから、あなたはへの種類の持っています 二つのことを追跡します。 あなたはどこにこのを追跡する場合 ノードは、現在に挿入されます。 また、を追跡する必要があります あなたが見ている前のノード そこにもありました。 それで良い誰？ OK。 どのように最後に挿入するでしょうか？ 私が望んでいた場合、私はhere--それを追加したい場合 リストの末尾に新しいノードを追加するには、 どのように私はそれをやって行くのでしょうか？ 聴衆：だから、現在、 最後のヌルを指摘しました。 ANDI PENG：うん。 ちょうどので、この1 現在知ることが指摘され、 ので、私はそれがだ、この意味では、と思います リストの最後に追加することは非常に簡単。 あなたがしなければならないすべてはそれを設定されています ヌルして、ブームに等しいです。 右そこに、非常に簡単。 非常にシンプル。 と非常に似て あなたの頭が、論理的に 手順はそれを確認します あなたは、こののいずれかを実行に向けて取ります あなたに沿って従っています。 それは途中で、と非常に簡単です あなたのコードの、に巻き込まれる ああ、私は非常に多くのポインタを持っています。 私がどこかわかりません 何を指しています。 私も、私は上だどのノードがわかりません。 どうしたの？ 深呼吸をし、落ち着いて、リラックスすることができます。 あなたのリンクリストを描画します。 あなたが言うなら、私は場所を正確に知っています 私はにこれを挿入する必要があります そして、私は再割り当てする方法を正確に知っています ポインタは、はるかに、はるかに簡単に画像に out--はるかに、はるかに容易にありません あなたのコードのバグで迷子に。 それでOK誰？ OK。 だから私たちは持っていない概念を推測します 本当に、今の前にについて話しました そして私はおそらくあなたを推測します 多くのyet--が発生することはありません それは、高度なconcept--のようなものです 私たちは実際にデータを持っているということです 構造は、二重リンクリストと呼ばれます。 だからみんなが見ることができるように、 私たちがやっているすべては作成されています 実際の値は、余分な 私たちの各ノード上のポインタ それはまた、前のノードを指しています。 だからだけでなく、私たちはがありますか ノードは、次のいずれかにポイントします。 彼らはまた、前のものを指します。 私は今、これらの2を無視するつもりです。 だから、あなたは鎖を有していて それは両方の方法を移動することができ、 そして、それは少し簡単です 論理的に沿って追従します。 ここでのように、代わりに 私は、ああ、の追跡 このノードがあることを知っている必要があります 私は再割り当てする必要があります1、 私はここに行くことができ、 ただ、前を引きます。 それから私は、場所を正確に知っています つまり、その後 横断する必要はありません リンクリストの全体。 それは少し簡単です。 しかし、このようなように、あなたが二重に持っています ポインタの量は、 それは二重のメモリの量です。 これは、を追跡するためのポインタがたくさんです。 これは少し複雑ですが、それはです もう少しユーザーフレンドリー応じ あなたが達成しようとしているものに。 そのようにこのタイプのデータ 構造は全く存在して、 そして、するための構造は、非常に、非常にあります あなたが持っているすべてを除いて単純です、 代わりに、次へのポインタだけの、 あなたはまた、前へのポインタを持っています。 それはすべての違いだったのです。 それで良い誰？ クール。 すべての権利、今私は 本当におそらく過ごすために 15〜20分またはバルクのような セクションの残りの時間の ハッシュテーブルの話。 どのようにあなたたちの多く pset5仕様を読んでいますか？ すべての権利、良いです。 それは、通常の50％よりも高いです。 大丈夫です。 だからみんなが見るように、 あなたはpset5に挑戦しています 辞書を実装することになります どこに14万の単語を読み込みます 私たちはあなたとスペルチェックを与えること すべてのテキストに対して、それ。 私たちはあなたのランダムをあげます 文学の作品。 私たちはあなたのオデッセイを与えるでしょう。 私たちはあなたのイリアスを与えるでしょう。 私たちはあなたのオースティンパワーズを与えるでしょう。 そして、あなたの挑戦 スペルチェックをすることになります すべてのすべての単一の単語 これらの辞書の 基本的に私たちのスペルチェッカーと。 だから、いくつかの部品があります このPSETを作成するのではなく、 まずあなたがなりたいです 実際にロードできます あなたにすべての単語 辞書、その後 にできるようにしたいです それらのすべてをスペルチェック。 それでなど、あなたが必要とするつもりです この高速を行うことができますデータ構造 効率的かつ動的。 だから私は、最も簡単なと仮定します これを行う方法は、 おそらく正しい、配列を作成しますか？ ストレージの最も簡単な方法は、あなたです 14万単語の配列を作成することができます ちょうどそこにそれらのすべてを配置し、 その後、バイナリ検索によってそれらを横断します または選択しますか、not-- 残念それは並べ替えています。 あなたはそれらをソートし、それらを横断することができます 二分探索あるいは単に線形探索によって ちょうど最後の言葉が、その メモリの膨大な量をとり、 それは非常に効率的ではありません。 そして、私たちは開始するつもりです 作りの方法について話 私たちの実行時間が、より効率的。 そして、私たちの目標は得ることです 一定時間どこ それはほとんどの配列、のようなものです あなたは瞬時にアクセスできます。 私は何を検索したい場合は、 私は、ちょうどにできるようにしたいです ブームは、まさにそれを見つけて、それを引き出します。 だからその構造中 我々は非常に近くなりつつありますよ 一定アクセスできるようにします 時間、この聖杯 一定のプログラミングで 時間は、ハッシュテーブルと呼ばれています。 それでダビデは、前述 [聞こえない]講義で少し、 しかし、私たちは本当にするつもりです 深い今週中にダイブ 駒に どのようにハッシュテーブルが動作します。 そのようにそうハッシュ テーブルの動作、例えば、 私は言葉の束を保存したい場合、A 英語の単語の束、 私は理論的に入れることができます バナナ、リンゴ、キウイ、マンゴー、ペア、 ちょうどアレイ上のマスクメロンすべて。 彼らはすべての中で合うことができると見つけること。 これは、痛みのようなものになるだろう アクセスを検索、 しかし、これを行うための簡単​​な方法があります 私たちは実際に構造を作成することができます 我々はハッシュハッシュテーブルと呼ばれます。 我々はを通じて当社のすべてのキーを実行します ハッシュ関数、式、 それはにそれらすべてを回します 値のいくつかの並べ替え その後、我々は上に保存することができ リンクリストの基本的配列。 だからここで、私たちは望んでいた場合 英語の単語を格納します、 我々は、潜在的にだけ、私はしません行うことができます 知っている、すべての最初の文字を回します 数のいくつかの並べ替えに。 だから、私が欲しかったたとえば、 apple--と同義であることを または0のインデックスとし、 Bは、1と同義であることを 私たちは26のエントリを持つことができます それはただ保存することができます のすべての文字 私たちは始めましょうアルファベット。 そして、我々は持つことができます 0のインデックスにリンゴ。 私たちは、のインデックスでバナナを持つことができます 1、2の指数でマスクメロン、 などなど。 こうして私は、検索したい場合 私のハッシュテーブルとアクセスリンゴ、 私はリンゴで始まる知っています A、と私は正確に知っています それは、ハッシュであるとしなければならないこと インデックス0のテーブル理由 以前に割り当てられた機能の。 だから私たちは、知りません ユーザプログラム場所 あなたが課金されます 任意ではありませんarbitrarily--、 思慮深くしようとしていると 良い方程式を考えます 広がることができるようにします 自分の価値観のすべてのアウト 彼らは簡単にアクセスできるようにして それ以降の上での式のように あなた、自分で、知っています。 だから、ある意味で、私はに行きたい場合 マンゴーは、私が知っている、ああ、それはメートルで始まります。 それは12のインデックスである必要があります。 私は何を検索する必要はありません。 私はちょうどに行くことができるexactly--私が知っています 12のインデックスとそれを引き出します。 どのように誰も明確な ハッシュテーブルの機能が動作しますか？ それはちょうどより複雑な配列のようなものです。 それはそれはすべてです。 OK。 だから私たちはに実行推測します 何のこの問題 あなたは複数のものを持っている場合はどうなります それはあなたに同じインデックスを与えますか？ だから、私たちの関数は、すべてのこと、言います その最初の文字だったかかりました とにそれを回します それぞれの25のインデックス0〜。 場合には全く問題ありません あなたは、それぞれ1つだけ持っています。 しかし、第二は、あなたが開始します 以上を有する、あなたがしています 衝突と呼ばれるものを持っているつもり。 だから私は、ハッシュに埋める挿入しようとする場合 すでにその上にバナナを持っているテーブル、 何がときに起こるだろう あなたはそれを挿入しようと？ バナナため悪いこと インデックス内にすでに存在しています あなたはそれを保存すること。 ベリーは、種の私が何をする、ああ、のようなものですか？ 私はどこへ行くかわかりません。 私はこれをどのように解決するのですか？ だから君たちは一種の意志 私たちはこのトリッキーなことを行う参照してください。 ここで、我々は一種の実際にすることができます 私たちの列にリンクされたリストを作成します。 それで最も簡単な方法 これについて考えるために、 すべてのハッシュテーブルであります リンクされたリストの配列。 ですから、その意味では、あなたが持っています ポインタのこの美しい配列、 し、各ポインタで その値は、そのインデックスで、 実際に他のものを指すことができます。 だから、あなたはすべてのこれらの別々のを持っています 一つの大きな配列の抜けチェーン。 だからここで、私の場合 ベリーを挿入したかったです、 私は[OK]を、私は入力するつもりだ、知っています それ私のハッシュ関数を通じて。 私はのインデックスで終わるつもりです 1、その後、私が持ってできるようにするつもりです これだけ小さいサブセット 巨大14万語辞書。 そして私はちょうど見ることができます その1/26を通じ。 だから、私はただ挿入することができます バナナの前または後のいずれかにベリー この場合？ 後、右か？ だから、あなたがしたいとしています バナナの後に、このノードを挿入し、 ので、あなたが挿入しようとしています そのリンクリストの末尾。 私は戻って行くつもりです この前のスライドに、 だからあなたたちはどのように見ることができます ハッシュ関数が動作します。 だから、ハッシュ関数は、この方程式であります あなたの入力の種類を実行していること どのようなインデックスを取得するために通過 あなたはそれに向かってを割り当てます。 我々が望んでいたので、この例では、すべての 行うには、最初の文字を取りました 我々はその後、インデックスにそれを回します 私たちのハッシュ関数のそれを保存することができます。 私たちがここでやっているすべては私たちがしているです 最初の文字を変換します。 だからkeykey [0]であるだけで最初の文字 どのような文字列で、私たちは持っています、 我々は渡しています。 我々は上にそれを変換し、しています 我々は、大文字のAで引いています やっているように、すべての 私たちに番号を与えています ここで私たちは私たちの上に値をハッシュすることができます。 そして、我々はするつもりです ハッシュ係数サイズを返します。 非常に、非常に注意してください なぜなら、理論的には、ここで あなたのハッシュ値は無限大である可能性があります。 それはちょうど上と上に行くことができます。 それは実際にいくつかの可能性があり、 本当に大きな値、 しかし、あなたのハッシュテーブルのため、その あなたが作成しただけで26のインデックスを持っています、 あなたは確認します あなたようにmodulusing それは同じだrun--はありません あなたのqueue--ようなもの あなたはオフに実行されないように、 あなたのハッシュ関数の底。 あなたの周りにそれをバックラップしたいです [聞こえない]で同じよう あなたは非常に持っていたように、 非常に大規模な文字、あなた にそれをしたくありませんでした ちょうど端を実行します。 ここで同じことが、あなたは確認します それは、ラッピングによって終わりをオフに実行されません 周りのテーブルの上に。 だから、これは非常にだけです 単純なハッシュ関数。 やったことすべてが取る最初でした どのような私たちの入力の手紙がありました そのインデックスにそれを回します 私たちはハッシュテーブルに入れることができます。 うん、と私は前に言ったように、 我々は衝突を解決する方法 当社のハッシュテーブルが持っています、 我々は連鎖、何を呼び出します。 ですから、複数を挿入しようとした場合 同じことで始まる単語、 あなたは1つのハッシュ値を持っているつもりです。 アボカドとリンゴ、あなたがしている場合 私たちのハッシュ関数を介して実行、 あなたを与えるとしています 同じ数、0の数。 そして、私たちはそれを解決する方法があります 私たちは実際に種類のそれらをリンクすることができます 一緒にリンクされたリストを経由して。 だからこの意味で、 あなたたちは親切見ることができます どのようなデータ構造のこと 我々は以前に設定されてきました レーズンリンクリストのようなもののような いずれかに一緒に来ることができます。 そして、あなたはこれまで作成することができます より効率的なデータ構造 それは、より多くの量を処理することができます データ、すなわち、動的によってリサイズ あなたのニーズに。 誰も明確な？ 明確なのみんなの種類 ここで何が起こるかの？ 私は何insert--したい場合 始まる果物は、私は知りません、 ベリー以外のB、バナナ。 聴衆：ブラックベリー。 ANDI PENG：ブラックベリー、ブラックベリー。 どこでブラックベリーは、ここに行くのですか？ さて、私たちは実際にソートされていません このまだ、しかし、理論的に 我々はこれを持っているしたい場合 アルファベット順に、 どこに行くのブラックベリーべきですか？ 聴衆：[聞こえません] ANDI PENG：その通り、ここの後、右か？ しかし、それはすることが非常に困難だから reorder--私はそれは君たち次第だと思います。 君たちは完全にすることができます あなたが好きな実装。 より効率的な方法 おそらくこれを行います あなたのリンクを並べ替えることであろう アルファベット順に一覧表示し、 ので、あなたがいるとき 物事を挿入する、あなたがしたいです それらを挿入してくださいします アルファベット順に そのため、あなたがいるとき それらを検索しようとすると、 あなたはすべてを横断する必要はありません。 あなたが知っている場所を正確に それは、それが簡単です。 しかし、あなたは親切なのがあれば 物事は、ランダムに散在します あなたはまだ必要があるとしています とにかくそれを横断します。 だから私はちょうどしたい場合 ブラックベリーここに挿入 私はを検索したいです それ、私が知っている、ああ、ブラックベリー 1のインデックスで始まるので、私必要があります 瞬時にちょうど1で検索を知っています。 そして、私はこの種のことができます リンクリストをトラバース 私はブラックベリーに到達するまで、 とええthen--？ 聴衆：あなたはcreate--しようとしている場合 これは非常に単純なハッシュであるように私は推測します 機能。 そして、私たちがやってみたかった場合 そのような複数の層、 [OK]を、私たちは、に分離したいです すべてのアルファベットのような し、再度別のセットを好きに その内のアルファベットの、 我々は、ハッシュのように入れています ハッシュテーブル内のテーブル、 または関数内の関数のような？ それともthat--です ANDI PENG：だからあなたのハッシュ あなたのハッシュテーブルをfunction-- あなたはそれが好きな大きくすることができます。 したがって、この意味では、私は思いました それは非常に、非常に簡単でした ちょうどソートベースのために私のために簡単な 最初の単語の文字に。 そして、これだけ26のオプションがあります。 私は26からオプションを取得することができます 0彼らは唯一の可能性があるため25に AからZに開始しかし、あなたが望んでいた場合 おそらく、より多くの複雑さを追加します あなたの実行時間以上の速度 ハッシュテーブル、絶対に 物事のすべてのソートを行うことができます。 あなた自身作ることができます あなたを与える式 あなたの中に複数の配布 言葉は、あなたが検索し、 それは速くなるだろう。 それは完全にあなたたち次第です どのようにあなたはそれを実装したいです。 ちょうどバケツと考えてください。 私が持っているしたい場合 26バケツ、私は行きますよ これらのバケットに物事をソートします。 しかし、私はたくさんを持っているつもりです 各バケット内のものの、 だから、あなたがそれをしたい場合 より速く、より効率的、 私は百バケツを持ってみましょう。 しかし、あなたは把握する必要があり 彼らはそのようなものをソートする方法 正しいバケツに彼らがでなければなりません。 しかし、ときに実際に そのバケットを見てみたいです、 ありますので、それははるかに高速です 各バケットが少ないもの。 だから、ええ、それは実際にはです pset5で君たちのためのトリック あなたはなるだろうということです ちょうど作成に挑戦 最も効率的であるものは何でも であることをあなたが考えることができる機能 これらの値を保存し、確認することができます。 完全にあなたたちまで しかし、あなたはそれをやってみたいです、 それは本当に良い点です。 そのロジックの一種ます 考え始めるしたいです よく、なぜ私はより多くのバケツをしない、です。 そして、私が検索する必要が 以下のもの、次に多分私 異なるハッシュ関数を持っています。 うん、これを行うための方法はたくさんあり​​ます PSET、一部は他よりも高速です。 私は完全にどれだけ見に行きますよ 速い最速君たちがしますました あなたの関数が動作するように取得することができます。 良いで[OK]をクリックし、すべての人 チェーンとハッシュテーブル？ これは非常に単純なように、実際のです あなたが考えてみれば概念。 それがすべてでは何でも分離されます あなたの入力はバケットにあり、 それらをソートし、次に検索 そこには、関連付けられていることを示しています。 クール。 すべての権利、今、私たちは別の種類を持っています 木と呼ばれるデータ構造の。 それでは、上に行くと試行についてお話しましょう これは明らかに異なっており、 同じカテゴリインチ 基本的に、すべての木は代わりにあります 線形方法でデータを整理します ハッシュテーブルはあなたをdoes--こと 知っている、それは、上部と下部を持っています そして、あなたは一種のit--のオフリンク ツリーは、あなたが根を呼び出すトップを持っています そしてそれはすべてその周りの葉を持っています。 だから、すべてあなたがここにあります ただ最上位ノードであります それが指していることを、他のノードを指します 複数のノードへ、などなど。 だから、あなただけの分割枝を持っています。 これは、整理のちょうど別の方法です データ、そして我々はそれツリーを呼び出すので、 あなたたちはそれだけですjust-- 木のように見えるように出てモデル化しました。 私たちは木と呼んでいます。 ハッシュテーブルには、テーブルのように見えます。 ツリーは、ちょうど木のように見えます。 それはすべてが分離されています ノードを整理する方法 あなたのニーズが何であるかによって異なります。 だから、ルートを持っており、 あなたは葉を持っています。 その私たちは特にすることができる方法 それについて考えるバイナリツリーです、 バイナリツリーはただであります ツリーの特定のタイプ ここで、各ノードは唯一のポイント 最大で、他の2つのノード。 だからここでは、個別の持っています あなたのツリー内の対称性 それは一種の見て、それが容易になります 値何であなたは、あなたですので、 常に左または右を持っています。 左から第三のような存在ことはありません 左または左から4番目。 それはあなたが左右を持っているだけです あなたはこれら二つのどちらかを検索することができます。 そして、なぜこれが便利なのですか？ このことを方法 あなたが探している場合に便利です 右、値を検索するには？ むしろバイナリを実行するよりも エラー配列内の検索、 あなたは、ノードを挿入できるようにしたい場合 また意志でノードを奪うと、 検索を保存します 二分探索の容量。 だから、このように、我々は一種のです ときに我々覚えtricking-- リンクされたリストは、バイナリ検索することはできません言いましたか？ 私たちは、この種のデータ構造を作成しています トリックは、作業にそのことを。 だからリンクされたリストは、直線状であるため、 彼らは次々にリンクします。 私たちは、この種のことができます ポインタの別の種類 別のノードにそのポイント それは、検索で私たちを助けることができます。 だからここで、私がしたい場合 二分探索木を有します 55場合、私はその私の真ん中を知っています。 私はちょうどそれを作成するつもりです 私の真ん中のように、私のルートとして、 そして私は持っているつもりです 値は、それのスピンオフ。 だからここに、私がを検索するつもりだ場合 66の値は、私は55で開始することができます。 これは、55より66大きいのか？ はい、そうですので、私は私が知っている検索MUS I Nこのツリーの右ポインタ。 私は77に行きます。 [OK]を、66未満または77より大きい？ ああ、それはより少ないですので、あなたが知っています、 それは、左ノードにする必要があります。 だからここでは、種の維持しています アレイに関する素晴らしいことのすべて、 そう動的なサイズ変更のような あるオブジェクトの 自由に挿入し、削除することができ、 固定を心配することなく、 スペースの量。 我々はまだすべてを保存します これらの素晴らしいもの また、保存することを可能としながら、 バイナリサーチの時間を記録し、検索 我々は以前にあったこと フレーズを取得することができます。 クールなデータ構造、種類の 複合体は、ノードを実装します。 あなたは、それをすべて見ることができるように ノードの構造体であり、 あなたは左を持っているということです 右のポインタ。 それはそれはすべてです。 だからだけではなく xまたは以前を持ちます。 あなたは、左または右を持っており、 あなたはこの種のそれらを一緒にリンクすることができます しかし、あなたがそう選択します。 [OK]を、私たちは実際に行っています わずか数分かかります。 だから我々はここに戻って行くつもりです。 私が以前言ったように、 私は種類の説明しました どのように我々の背後にあるロジック このを検索します。 我々は試してみるつもりです 見るためにこれをpseudocoding 私たちは、この種の適用できるかどうか バイナリサーチの同じロジック データ構造の異なるタイプ。 あなたたちはカップルのように利用したい場合 ただこれについて考えるために分。 OK。 すべての権利、私はするつもりです 実際にちょうどあなたがノーthe--与えます、 我々は最初の擬似コードについて話しましょう​​。 だから、誰もが欲しいん 何で刺しを与えるために あなたはときに何をしたい最初のこと あなたは、検索が出始めていますか？ 私たちは、探している場合 66の値が、何 我々があればやりたい最初のこと 私たちはこの木二分探索してみませんか？ 聴衆：あなたは、右を見てみたいです そして、[聞こえない]を左見て、参照してください。 より多くの数。 ANDI PENG：うん、まさに。 つまり、あなたのルートを見ていきます。 あなたが呼び出すことができる方法はたくさんあり​​ます それは、あなたの親ノードの人々は言います。 私はので、ルートを言いたいです それは、ツリーのルートのようなものです。 あなたが見てするつもりです あなたのルートノード、あなたがしています 見に行くと、66大きいです 以下より55。 そして、それはよく、それは、より大きいだ場合 より大きく、どこに我々は見てみたいのですか？ どこに右、今検索したいのですか？ 私たちは、検索したいです このツリーの右半分。 だから持って、便利に、 右を指すポインタ。 だから我々は設定することができます 77であるために私たちの新しいルート。 私達はちょうどどこに行くことができます ポインタが指しています。 まあ、ああ、ここでは開始しています 77であり、私たちはすることができます 再帰的に何度も何度もこれを行います。 このように、あなたの種類 機能を有しています。 あなたがいることを検索する方法を持っています ただ何度もオーバーを繰り返すことができ、 あなたが見てみたい場所に応じて あなたは最終的な値に到達するまで あなたが探しているもの。 理にかなって？ 私はあなたに実際に表示されるまでによ コー​​ド、そしてそれは多くのコードです。 フリークアウトする必要はありません。 私たちは、それを介して話しましょう​​。 実際には、ありません。 それはちょうど擬似コードでした。 [OK]を、それはただの擬似コードは、ありました これは少し複雑ですが、 しかし、それは完全に罰金です。 誰もがここに沿って、次の？ ルートがnullの場合、復帰 その手段のため偽 あなたも、そこには何もありません。 ルートnは、もしそうであれば値である場合、それ あなたが見ている1であることを起こります、 あなたがtrueを返すつもりです あなたが知っているので、あなたはそれを見つけました。 しかし、値が小さい場合 n個のルートよりも、あなたがしています 左側の検索に行きます 子供や左葉、 あなたはそれを呼び出すために好きな。 その値は、ルートよりも大きい場合、 あなたは右の木を検索するつもりです、 その後、ちょうど関数を実行 検索を通して再び。 そして、ルートは、そのことを、nullの場合 あなたが最後に達したことを意味？ それはありません、あなたが持っていることを意味します 検索するよりより多くの葉、 その後、あなたが知っている、ああ、私は それがここにいないだと思います 私が通って見てきた後理由 全部、それはここではないですが、 それはちょうどここではないかもしれません。 それは誰にでも意味がありますか？ だから、保存バイナリサーチのようなものです リンクされたリストの機能を提供します。 クール、そして第2のタイプ データ構造の君たち あなたのpsetに実装しようとすることができ、 あなたは1つの方法だけを選択する必要があります。 しかし、おそらく別の方法に ハッシュテーブルは、我々がトライを呼んでいます。 すべてのトライがあります ツリーの特定のタイプのもの 他の値に移動値を持ちます。 だからではなく、バイナリを持ちます 一つだけの意味でのツリー 事は2を指すことができ、あなたが持つことができます 多くの、多くのものを一つのポイント。 あなたは、本質的に配列を持っています そのうちあなたは店内 他の配列を指すポインタ。 だからどのノード トライを定義します 私たちは持っていたいです ブール、Cワード、右？ だから、ノードはブール値です trueまたはfalseのように、 先頭のすべての最初の その配列は、これは言葉ですか？ 第二に、あなたはポインタを持っていたいです 何にそれらの残りの部分があります。 少し複雑、ビット抽象が、 私はどのようなすべての手段ということを説明します。 そこでここでは、上部に、あなたの場合 配列がすでに宣言しています、 あなたがブールを持っているノード 正面に格納された値 それはあなたが、これは言葉で伝えますか！ これは言葉ではないですか？ そして、あなたが持っています ご使用のアレイの残りこと 実際にすべて格納 それは何ができるかの可能性。 だから、例えば、のような あなたが持っている一番上に 真かと言う最初の事 偽、yesまたはno、これは言葉です。 それから、あなたは、26を介して0を持っています あなたが保存することができます文字。 私はここで検索したい場合 バットのために、私がトップに行きます そして、私は私の中でBを見つけるB.探し アレイと、私は知っている、[OK]を、Bは言葉ですか？ Bは言葉ではないので、このように 私が探しておく必要があります。 私は、Bから行く、と私は見に Bが向かって指すポインタ 私は、情報の別の配列を参照してください 我々の前にいたのと同じ構造。 とまあhere--、次の [聞こえない]の文字はAです。 だから我々はその配列に見えます。 私たちは、第八値を見つけ、 し、我々は、ああ、見に見えます ねえ、ある単語ことを、B-Aは、単語のですか？ それは言葉ではありません。 私たちは、探し続けるようになってきました。 だから我々はどこに目を向けます ポイントのポインタ、 それは別の方法を指し これは我々が格納されているより多くの価値を持っています。 そして最終的に、私たちはを取得 単語であるB-A-T、。 だから、次回 あなたが見て、あなたが行っています はい、のチェックを持っています、 このブール関数はtrueです。 だからある意味で、私たちは親切です 配列を持つツリーを持ちます。 だから、あなたは一種のダウン検索することができます。 むしろハッシュ関数よりと リンクリストによって値を割り当て、 あなただけ実装することができます downwords検索トライ。 本当に、本当にものを複雑。 私はのようだから考えることは容易ではありません 非常に多くのデータ構造を吐き あなたに、しかし種類のみんなを行います このロジックがどのように機能するかを理解できますか？ うんいいね。 だから、B-A-T、その後、 あなたは、検索しようとしています。 あなたが行っている次の時間 確認するために、ああ、ちょっと、それは本当です、 このように私はこの言葉でなければなりません知っています。 動物園のために同じこと。 だからここに事があれば、今の私たちです 今、動物園を探索したかったです、 現在、動物園ではありません 私たちの辞書で単語 なぜなら、あなたたちが見ることができるよう、 我々がブールを持っている最初の場所 trueを返すズームの最後にあります。 我々は、Z-O-O-Mを持っています。 だからここで、我々は実際にはありません 私たちの辞書で単語、動物園、 このチェックボックスがチェックされていないため。 だから、コンピュータはしていません 動物園が単語であることを知っています なぜなら私たちはきた道 それを保存され、ここでの唯一のズーム 実際にBoolean値を持っています それが真になっています。 だから我々は、挿入したい場合は 単語、動物園、私たちの辞書に、 どのように我々はそれをやって行くのでしょうか？ 私たちは確認するために行うには何を持っています コンピュータは、Z-O-Oは、単語があることを知っています そして、ではない最初の単語は、Z-O-O-Mのですか？ 聴衆：[聞こえません] ANDI PENG：まさに、我々 このことを確認します ここでは、ブール値であること それが本当だとオフにチェック。 Z-O-Oは、その後、我々はそれを確認しようとしています、 私たちはちょっと、動物園は言葉で、正確に知っています。 私は言うつもりです それはそう言葉だコンピュータ ときにコンピュータをチェックしています、 それは動物園が単語であることを知っています。 すべてのこれらのデータを覚えているので 構造は、それが私たちのために非常に簡単です 言って、ああ、バットは言葉です。 動物園は、言葉です。 ズーム言葉です。 しかし、あなたはそれを構築しているときに、 コンピュータがない考えを持っています。 だから、正確にそれを指示する必要があります どの時点で、これは言葉ですか？ どの時点でそれは言葉ではないのですか？ そして、何点で私を行います 物事を検索する必要があり、 どのような点で私は次行く必要があるのですか？ その明確な誰？ クール。 そしてそうそれから来ます どのように我々の問題だろう 何かを挿入して行きます それが実際にはありませんか？ それでは、ちょうど我々が挿入したいとしましょう 単語、お風呂、私たちのトライに。 あなたたちは、現在のように見ることができるように 我々が今持っているすべては、B-A-Tであります この新しいデータ構造 パイントが持っていました 我々が想定しているためnullに指摘 それは、ああ、何の言葉は、B-A-Tの後にありません なぜ私たちは維持する必要があります そのT.後のものを持ちます 私たちはあなたを行う場合でも、問題が発生します 後に来る言葉を持ちたいです Tの。 あなたがお風呂を持っている場合、あなたはしています Hの右をするつもり。 そして、私たちはそれをやろうとしている方法です 我々は、別のノードを作成しようとしています。 私たちは、どのような量を割り当てていません この新しい配列のためのメモリ、 我々はポインタを再割り当てするつもりです。 私たちは、割り当てするつもりです H、まず第一に、このヌル、 我々は取り除くつもりです。 我々は、必要があるとしています Hポイント下向き。 我々は、Hが表示された場合、我々はそれをしたいです どこか別の場所に移動します。 ここでは、[はい]をオフにチェックすることができます。 我々は、Tの後にHを打つ場合は、ああ、 我々は、これは言葉であることを知っています。 ブール値trueを返すために起こっています。 それが起こったのかを明確に誰？ OK。 だから基本的に、すべての これらのデータ構造 私たちは今日の上に行ってきたことを、私はしました 本当に、本当にすぐにそれらを乗り越え そしてあまりの中 詳細は、それは大丈夫です。 あなたはいじり始めると それを、あなたはなるだろう どこの追跡 すべてのポインタは、 何があなたに起こっています データ構造、エトセトラ。 彼らは非常に便利になるだろう、 そして、それはあなた次第です 男は完全にどのように把握します あなたは物事を実装したいです。 そしてそうpset4の5--ああ、それは間違っています。 Pset5はスペルミスです。 私が前に言ったように、一度、するつもりです 再び、私たちからソースコードをダウンロードしてください。 3主があるように起こっています 物事はあなたがダウンロードされます。 あなたは、辞書をダウンロードします KERS、およびテキスト。 これらすべてのものがありますされています いずれかの単語の辞書 我々はあなたがチェックしたいこと または情報のテスト 私たちは、あなたがチェックをスペルすることを。 だから辞書 私たちは、あなたが行く与えます あなたに私たちが望む実際の言葉を与えるために あなたはだ方法で何とか保存します 配列よりも効率的。 そしてテキストがあります 私たちがしているものになるだろう 確認するために、スペルチェックするように求め すべての単語の本当の言葉があります。 だからの3ブロックは、 私たちはあなたを与えるだろうプログラム dictionary.cと呼ばれ、 dictionary.h、およびspeller.c。 それですべてdictionary.cがされません 何を実装するように求められています。 それは言葉をロードします。 これは、チェックをしてスペル、それは確認します そのすべてが正しく挿入されています。 diction.hはただのライブラリファイルです それはすべてのこれらの機能を宣言します。 そしてspeller.c、私たちはあなたを与えるつもりです。 あなたはそれのいずれかを変更する必要はありません。 speller.cが行うすべてのことを取ることで、 負荷は、それの速度をチェックし、 どのようなのベンチマークをテスト すぐにあなたは物事を行うことができるしています。 これは、スペルチェックです。 ちょうどそれを台無しにしないが、作ります あなたはそれがやっているか理解してください。 我々はGETRUSAGEその呼び出された関数を使用します スペルの性能をテストします チェッカー。 すべてのそれは基本的にテストされてい 辞書内のすべての時間、 あなたはそれを理解しておいてください。 それを台無しにしないように注意してくださいまたは それ以外のものは、正しく動作しません。 そして、この課題の大部分はのためであります 君たちは本当にdictionary.cを変更します。 私たちはあなたを与えるつもりです 辞書内の単語14万。 私たちはあなたのテキストを与えるつもりです これらの言葉を持っているファイル、 そして、我々はあなたが整理できるようにしたいです ハッシュテーブルまたはトライにそれら 我々はスペルをお願いするときのため あなたが呪文なら想像check-- ホメロスのオデッセイのようにチェック。 それはこの巨大な、巨大なテストのようなものです。 一つ一つの場合を想像 言葉あなたが見なければなりませんでした 14万値の配列を通じ。 それは永遠にかかるだろう お使いのマシンを実行するため。 私たちはを整理したい理由です より効率的なデータ構造へのデータ このようなハッシュテーブルやトライなど。 そして、あなたたちは親切なことができます あなたがアクセスを検索したときの 物事をより簡単に、より迅速に。 そしてそう衝突を解決するように注意してください。 あなたは束を取得するつもりです Aとその開始の言葉の あなたはたくさんの単語を取得するつもりです それはあなたまでBで開始します あなたはそれを解決する方法をみんな。 おそらく、もっとあります 効率的なハッシュ関数 のちょうど最初の文字より 何か、などそれはあなた次第です 人は種類のあなたがやりたいします。 たぶん、あなたは、追加したいです 一緒にすべての文字。 たぶん、あなたは奇妙なことを行うが好きにしたいです 文字の数を考慮するために、 なんでも。 あなたがしたいかあなたたちまで。 あなたがあれば、ハッシュテーブルをしたい場合 完全にあなた次第、トライを試してみたいです。 私は前もって警告が表示されます トライは、一般的に少しより困難です たくさんがありますという理由だけで を追跡するために、複数のポインタ。 しかし、完全にあなたたちまで。 それは、はるかに効率的です ほとんどの場合です。 あなたは本当に維持できるようにしたいです あなたのポインタのすべてのトラック。 以下のように同じことを行います 私はここでやっていたこと。 あなたが挿入しようとしているとき ハッシュテーブルに値または削除、 あなたがしていることを確認してください 本当にを追跡すること すべてがあるためであるの 私は場合のために、それは本当に簡単です 単語、アンディのように挿入しようとしています。 ちょうどそれがだとしましょう 本当の単語、単語、アンディ、 言葉の巨大なリストに。 私はちょうど再割り当ててしまった場合 間違ったポインタ、おっと、 全体をそこに行きます 私のリンクリストの残りの部分。 今だけの単語私 持って今アンディで、 内の他のすべての単語 辞書が失われています。 だから、あなたを確認します あなたのポインタのすべてを追跡します あるいはあなたが取得するつもりです あなたのコード内の巨大な問題。 ステップバイステップで慎重に物事を描画します。 それは非常に簡単で考えるようになります。 そして最後に、次のことができるようにしたいです プログラムのパフォーマンスをテストします ビッグボード上。 あなたたちは取る場合 今CS50を見て、 私たちは大きなボードと呼ばれるものがあります。 これは、最速のスコアシートであります CS50のすべてにわたって回スペルチェック 今、私は10のようなトップだと思います 回私はそれらの8スタッフだと思います。 私たちは本当にあなたたちは私たちを打つしたいと思います。 私たちのすべてが実現しようとしていました 可能な限り最速のコード。 私たちは、あなたたちは挑戦してみたいです 私たちと私たちのすべてよりも早く実現 することができます。 そして、これは実際にあります 私たちがしている初めて そのPSETを行うには君たちを求め あなたは本当にどんな方法で行うことができます あなたが欲しいです。 私はいつも、これは、より類似している、と言います 現実のソリューションには、右？ 私はちょっと、私はあなたがこれを行う必要があり、言います。 私のためにこれを行い、プログラムをビルドします。 あなたが欲しいしかし、それを実行してください。 私はちょうど私が断食したいことを知っています。 つまり、この週のあなたの挑戦です。 君たちは、我々が行っています あなたのタスクを得ました。 私たちはあなたの挑戦を与えるつもりです。 そして、それは君たち次第です 完全にちょうど把握します 最も迅速で何 これを実現する効率的な方法。 うん？ 観客：我々は場合に許可されています より高速な方法を研究したかったです オンラインハッシュテーブルを行うには、我々が行うことができます その誰かの他の人のコードを引用？ ANDI PENG：ええ、完全に罰金。 だからみんなが読ん場合 スペックは、行あります 君たちと言う仕様で ハッシュの検索するには完全に無料です 何がいくつかの機能 迅速にハッシュ関数の などを通じて物事を実行します あなたがそのコードを引用として長いです。 だから、何人かの人々がすでに持っています 高速な方法を考え出しました スペルチェッカーを行うための、高速の 情報を保存する方法。 完全にあなたたちまであなたの場合 右、ちょうどそれを取るしたいですか？ あなたが引用していることを確認します。 ここでの課題は、実際に 我々は、テストしようとしていること あなたが知っていることを確認することさ ポインタの周りにあなたの方法。 限りあなたが実現するとして 実際のハッシュ関数 などを考え出します 数学はそれを行うには、 君たちは何でも調べることができ 方法はオンライン君たちが欲しいです。 うん？ 観客：我々だけ挙げることができます [聞こえない]を使用して？ ANDI PENG：うん。 することができますだけで、あなたのコメントで、 あなたは、ああ、のように挙げることができます 矢田から取られ、矢田、 矢田、ハッシュ関数。 誰もが任意の質問がありますか？ 私たちは実際にbreezed 今日貫通部。 私はにここになります 同様の質問に答えます。 また、私が言ったように、オフィス 時間今夜と明日。 今週は実際にスペック 超簡単、読み超短いです。 私は、見てみることをお勧め それの全体をお読みください。 そしてZamylaは実際にあなたを歩きます 機能のそれぞれを介して あなたが実装する必要があり、それはです すべてを行うにはどのように非常に、非常に明確。 ちょうどあなたがしている作ります ポインタを追跡します。 これは非常に困難PSETあります。 以下のようなので、それは、挑戦的ではありません ああ、概念はそんなに多くあり 困難な、またはあなたが学ぶ必要があります そんなに新しい構文方法 あなたは最後のpsetのためにしたこと。 このPSETは困難であるため、 非常に多くのポインタがありますが、 そしてそれは一度に非常に、非常に簡単です あなたはあなたのコードにバグがありことができません そのバグがどこにあるか見つけるために。 あなたの中にそしてそう全くの信仰 みんなは私たちの[聞こえない]を打つことができるように スペル。 私は実際に書かれた鉱山を持っていません まだ、私は私を書くことについてです。 だから、あなたが書いている間 あなたは、私は私を書くことになります。 私が作ってみるつもりです 速くあなたより私のもの。 私たちは、最速の1を持っている人を参照してくださいます。 そして、ええ、私はすべてのを見ることができます ここで火曜日に君たち。 私はPSETのワークショップのような種類を実行します。 セクションのすべてのこの 週のpsetのワークショップであり、 だからあなたたちは機会がたくさんあり​​ます いつものように助けのため、営業時間、 私は本当にを楽しみにしています あなたの男「すべてのコードを読み取ります。 あなた場合、私はここでクイズを持っています 人はそれらを得る来てほしいです。 それで全部です。