[音楽再生] SPEAKER 1：すべての権利。 誰もがセクションに戻って歓迎しています。 私はあなたのすべてが正常であることを望む あなたのクイズから回収 先週から。 私はそれが時には少しクレイジーだ知っている。 あなたがいるなら、私は、前に言っていたように 標準偏差内、 本当に、特に、それについて心配しないでください あまり快適セクションの。 それはあなたがどこにあるべきかについてです。 あなたは素晴らしいやったならば、素晴らしい。 あなたに賛辞。 そして、あなたが必要とするように感じる場合は、 もう少し助け、お願い致します 到達して自由に感じる TFのいずれかに出。 私達は助けるために、すべてここにある。 私たちは教える理由です。 私はあなたのためにここに毎週月曜日だ理由です 木曜の男とオフィスで時間。 だから、私に知らせて自由に感じなさい あなたは何を心配しているなら か何かがクイズであるかどう ことをあなたは本当に対処したいと思います。 だから、今日の議題は、 すべてのデータ構造に関する。 これらのいくつかはちょうどになるだろうしている あなたはこれらに慣れ取得します。 あなたは今まで実装しない場合があります このクラスの彼ら。 そのうちのいくつかはあなたが意志、 あなたのスペルチェックのPSET用のような。 あなたは、あなたの選択があるでしょう ハッシュテーブルと試行の間。 だから我々は間違いなく、これらの上に行くことがあります。 それは一種の間違いなく、よりになるだろう しかしハイレベル区間今日の、 それらの多くがあるので、とIF 我々は実装の詳細に入った これらのすべてで、私たちはないだろう でも、リンクされたリストを介して取得 多分ハッシュテーブルの少し。 だから、私と一緒に負担する。 私たちはやっているつもりはない できるだけこの時間をコーディング。 あなたはそれについての質問があれば またはあなたはそれが実装見たい または自分自身でそれを試して、 私は間違いなくお勧めします 、study.cs50.netしようとしている これらの全ての例がある。 それは私のパワーポイントがあるでしょう 我々リアクション 使用する傾向があるだけでなく、いくつかのプログラミング 特に物事のため​​の演習、 リンクリストとバイナリのような 木々スタックと合図。 だから、もう少し高いレベル、どの 君たちのためにいいかもしれません。 それとだから、私たちは始めるでしょう。 また、yes--クイズ。 私がしているあなた方のほとんどを考える 私のセクションでは、あなたのクイズを持っている しかし、誰もが何らかの理由で提供できます ない、彼らはここの前にいる。 だから、リストをリンク。 私はこの種のが行く知っている あなたのクイズの前にバックアップします。 それは前の一週間でした 私たちはこのことについて学んだ。 しかし、このケースでは、我々だけでよ 深さにもう少し行く。 では、なぜ私たちは選ぶかもしれません アレイの上にリンクリスト？ 何が彼らを区別する？ はい？ 読者：あなたがリンクさを拡張することができます 配列の固定サイズ対リスト。 SPEAKER 1：右。 アレイは、一方でサイズを固定している リンクリストは、可変サイズを有する。 だから我々は方法がわからない場合 多くの私たちは、保存したい リンクリストは私たちに素晴らしいを与える ので、我々はただできることを行うための方法 別のノードで追加し、アドオン 別のノードとは別のノードに追加します。 しかし、何がトレードオフのでしょうか？ 誰もがトレードオフを覚えていますか 配列やリンクリストの間で？ ビー·マイ·エスケイプ？ 読者：あなたがする必要がある すべての道を通って行く リンクリストを通じて リスト内の要素を見つける。 アレイでは、次のことができます 単に要素を見つける。 SPEAKER 1：右。 だからarrays--付き 読者：[聞こえない]。 SPEAKER 1：アレイでは、我々が持っている ランダムアクセス何と呼ばれています。 私たちが望む場合はどうであることを意味し リストのこれまで五点 私たちのまたは第5のポイント アレイは、我々はそれをつかむことができます。 それはリンクリストの場合、我々は持っている 右、を反復処理する？ だから内の要素にアクセスする アレイは、一定の時間である それはだろリンクリストと、一方 最も可能性が高いので、多分線形時間であること 私たちの要素は、最後にすべての方法である。 私たちはすべてのものを検索する必要があります。 すべてのこれらのデータとそう 私たちが行っている構造 上もう少し時間を費やすべき、 プラスとネガは何ですか。 我々はしたいかもしれないとき 他の上で1つを使うのか？ そして、それはのようなものだ 大きな事は奪うように。 だから我々はここにある ノードの定義。 それは、1つの要素のようなものだ 私たちのリンクリスト、右？ だから我々はすべて精通している 私たちのtypedef構造体と、 我々は前回のレビューで渡ったもの。 それは、基本的には作成していた 我々が使用することができ、別のデータ·タイプ。 そして、この場合には、いくつかのノードの それはいくつかの整数を保持します。 その後、第2の部分は、ここに何ですか？ 誰ですか？ 読者：[聞こえない]。 SPEAKER 1：うん。 それは、次のノードへのポインタだ。 だから、これは実際にはここにアップする必要があります。 これは型のポインタである 次の事にノード。 そして、それはどのような彼らだ 我々のノードを含む。 涼しい。 我々はあったように、検索したので、すべての権利 あなたがいるならちょうど、手を前に言って を検索しようとして、 あなたが実際に反復処理する必要があります あなたのリンクリストを通じて。 だから我々は数を探しているなら 9、私たちは私たちの頭に開始する それは冒頭で私たちを指して 私達のリンクリストの、右？ そして、我々はOK、これを行い、言う ノードは、番号9を含むこと？ いいえ？ すべての権利、次のいずれかに行く。 それに従ってください。 それは9番が含まれていますか？ いいえ。 次の1に従ってください。 だから我々は実際に反復処理する必要があります 私達のリンクリストを通じて。 私達はちょうど9がどこに直接行くことができない。 そしてあなたたちが実際にしたい場合は、 そこにいくつかの擬似コードアップを参照してください。 ここではいくつかの検索機能を持っている それはそれは何をでかかりますかin--かかる？ どう思う？ とても簡単なもの。 これは何ですか？ 読者：[聞こえない]。 SPEAKER 1：私たちが探している数。 右？ そして、何、これは対応するのでしょうか？ それは、体へのポインタですか？ 聴衆：ノード。 SPEAKER 1：リストへのノード 我々は正しい、見ていることを？ だから我々はいくつかのノードがここにポインタである必要があります。 これがために起こっている点である 実際に私たちのリストを反復処理。 我々は、リストに等しく、それを設定する それはただだから へのそれは等しく設定 私達のリンクリストの先頭。 そして、それがNULLではありませんが、しばらく 我々はまだ私たちのリストで物事を持っている、 そのノードが持っているかどうかを確認してください 私たちが探している数。 trueを返します。 そうでない場合は、右、それを更新する？ それがNULLの場合、私たちは私たちのを終了 whileループとfalseを返す それが意味するので、我々はそれを見つけていない。 誰もがそれがどのように機能するかを取得していますか？ [OK]をクリックします。 あなたは、挿入したので、 3つの異なる方法を持っている。 あなたが追加することができ、先頭に追加することができます あなたが詰め合わせに挿入できる。 このケースでは、だ プリペンドをするつもり。 どのようにそれらの人を知っていますか 3例は異なる場合があります？ だから、プリペンドはあなたが置くことを意味します それあなたのリストの先頭に。 だから、意味に関係なく、その あなたのノードは、どんなに何であるか 値が何であるか、あなたが行っている [OK]を、前で右のそれをここに置くか？ それは最初になるだろう あなたのリスト内の要素。 あなたがそれを追加した場合は、それが起こっている あなたのリストの裏に移動します。 そして、あなたがしている各種手段に挿入する 所定の場所に実際に置くつもり それはあなたのリンクリストがソート保存する場所。 ここでも、どのように使う それらとするときに使用 彼らはあなたのケースによって異なります。 それはする必要がない場合 ソートされ、先頭に追加の傾向 何ほとんどの人であると そうしないため、使用する リスト全体を通過する必要があり 右、それを追加するための終わりを見つけるには？ あなたはちょうど右でそれを固執することができます。 だから我々は通過します 挿入1、今。 だから私はするつもりだ一つのことは、 非常にこのPSETにお勧め いつものように、物事を描画することです。 あなたが更新することを、それは非常に重要です 正しい順序であなたのポインタ あなたがそれらを更新した場合ので、 ややアウトオブオーダー、 あなたが終わるつもりです あなたのリストの一部を失う。 したがって、たとえば、この場合には、我々はしている 1にちょうどポイントに頭を伝える。 私達はちょうどそれを行う場合 この1を保存せずに、 私たちはどのような見当がつかない 1今を指している必要があります 私たちは何を失ってしまったので、 頭が指摘した。 だから、一つのことは覚えておくべき あなたがプリペンドをやっているとき 何保存することです まず、ヘッドポイント それを再割り当てしてから、更新 何あなたの新しいノードが指している必要があります。 この場合、これはそれを行う一つの方法である。 だから我々は、このようにそれをやっていれば どこに私たちはただ、頭を再割り当て 私たちは基本的に失う リスト全体、右？ これを行う1つの方法は、〜1点を持つことである 次の、その後1頭点を有する。 それとも、一種のように行うことができます 私が話を一時記憶、。 しかし、あなたの再割り当て 正しい順序でポインタ 非常に、非常になるだろう このPSETのために重要。 そうしないと、ハッシュを持っているつもり テーブルまたはちょうどになるだろう試し あなたの単語の一部のみ 欲しいその後you're--ビー·マイ·エスケイプ？ 聴衆：一時何だった ストレージの事あなたが話していた？ SPEAKER 1：一時記憶。 そこで、基本的に別の あなたがこれを行うことができます方法 同じように、何かの頭部を保管されている それを一時変数に格納します。 1にそれを割り当て、 その後ポイントに1を更新 何でも頭に指すように使用される。 この方法は明らかである よりエレガントなあなたのため 一時的な値を必要としませんが、 ちょうどそれを行うための別の方法を提供する。 そして、我々は実際に持っています このため、いくつかのコード。 リンクリストのためのだから、私たち 実際にいくつかのコードを持っている。 だから、これが前に付加されて、ここに挿入します。 だから、これは頭でそれを入力する。 あなたがする必要があるので、まず最初に、 もちろん、あなたの新しいノードを作成し、 そして、NULLかどうかを確認します。 常に良い。 そして、あなたは値を割り当てる必要があります。 たびに新しいノードを作成するには、 それは次のを指しているのかわからないが、 だから、NULLに初期化したいと思います。 それが何かを指して終わるない場合 他に、それは再割り当てされます、それは大丈夫です。 それは最初のif リストには、必要 なぜならNULLを指すように それはリストの最後です。 だから、それを挿入するために、我々は、我々はここを参照してください 私たちのノードの次の値を代入している 頭が何であることが、 その私たちがここに持っていたものである。 それは我々だけでやったことだ。 そして、我々はポイントに頭を代入している 私たちの新しいノードに、覚えているので、 新しいノードにいくつかのポインタである、 それは頭が何であるかを正確です。 それはまさに、なぜ我々です この矢印のアクセサを持っている。 クール？ ビー·マイ·エスケイプ？ 観客は：私たちがしなければならないの 最初のNULLに新しい次の初期化、 または私達はちょうどそれが頭に初期化することができますか？ SPEAKER 1：次の新 開始するには、NULLである必要がある あなたが知らない理由 それはどこになるだろう。 また、これは一種のです ちょうどパラダイムが好きです。 あなただけのためにNULLに等しく、それを設定する すべての塩基がカバーされていることを確認してください あなたはそのので、任意の再割り当てを行う前に、 あなたは、常にそれがすることを保証しています 特定の値を指している ガベージ値のような対。 なぜなら、ええ、私たちは割り当てる 自動的に次の新しい、 それだけのようなより多くの それを初期化することをお勧め そのようにし、その後再割り当てします。 [OK]を、そのように二重になりましたリストを連動。 私たちはどう思いますか？ 何と違う 二重にリンクされたリストを？ だから私たちのリンクリストで、我々はできる 右、一方向のみに移動？ 我々は唯一の横にあります。 私たちは前進することができます。 二重リンクリストを使用して、 我々はまた、後方に移動することができます。 だから我々は持っているだけでなく、 私たちが保存したい番号、 それは次の指し示すところ、我々は持っている そして私達はちょうどどこから来たのか。 だから、これは可能にする いくつかのより良いトラバーサル。 だから、二重にリンクされたノード、 非常によく似た、右​​？ 唯一の違いは、私たちは今である 次および前のを持っている。 それは、唯一の違いです。 だから我々は前に付加した場合、またはappend--たち here--このため、任意のコードを持っていない しかし、あなたがしようとした場合 、重要なことをそれを挿入 あなたが作る必要があるある あなたが代入していることを確認 以前とあなたの両方 正しく次のポインタ。 したがって、この場合には、でしょう 、次の初期化だけでなく、 あなたは以前初期化します。 我々はリストの先頭にいる場合は、私たち 頭等しいが新規になるだろうだけではなく、 しかし、私たちの新しい、以前はすべき 頭をポイントし、右？ それは唯一の違いです。 そして、あなたはもっと練習が必要な場合と 挿入とリンクリスト、これらの、 インサート、削除した 各種リストに、 study.cs50.netをチェックしてください。 偉大な演習の束があります。 私は非常にそれらをお勧めします。 私たちはそれらを介して行く時間があればいいのに しかし、データ構造の多くがあります を介して取得する。 [OK]を、ハッシュテーブルそう。 これはおそらく最もです あなたのpsetに便利ビット ここにあなたがするつもりだので、 これらのいずれか、または試みを実施しています。 私は実際にハッシュテーブルのような。 彼らはかなりクールだ。 そこで、基本的にどのような 起こるは、ハッシュテーブルである 私たちは本当にスピーディー必要なときである 挿入、削除、および参照。 それらは、私たちがしているものです ハッシュテーブルに優先順位を付ける。 彼らは、かなり大きな得ることができます しかし、我々はトライして表示されますよう、 はるかに大きいですものがあります。 しかし、基本的には、すべてのハッシュ テーブルは、ハッシュ関数である それはそれぞれのを置くためにどのバケットがわかります あなたのデータの、のあなたの各要素。 ハッシュテーブルを考えるための簡単​​な方法 それだけで物事のバケットであるということです、 右？ だから、あなたがすることによって物事をソートするとき 自分の名前の最初の文字のように、 それは一種のハッシュテーブルのようなものだ。 私はグループに君たちならばそうである の名前が​​始まる誰のグループに こっちで、または誕生日は誰だ 、1月、2月、3月である どのような、それが効果的である ハッシュテーブルを作成する。 それはちょうどバケットを作成だということ あなたがにあなたの要素を並べ替える あなたがそれらを簡単に見つけることができるようにします。 私は必要なので、この方法 あなたのいずれかを見つけるために、 私が検索する必要はありません あなたの名前のそれぞれを通る。 私は私が知っている、ああ、のようにすることができます ダニエルの誕生日ですin-- 聴衆：--April。 SPEAKER 1：4月。 だから、私は月に見える バケット、および任意の運と、 彼女はそこに一つだけだろうと 私の時間は、その意味では一定であった 私が見ている場合には、一方 人々の全体の束を経て、 それははるかに長い時間がかかるだろう。 だから、ハッシュテーブルは、本当にただのバケツです。 それらを考えるための簡単​​な方法。 だから、非常に重要なことについての ハッシュテーブルは、ハッシュ関数である。 だから、物事は私はちょうど同じように、の話 あなたの最初の名前の最初の手紙 またはあなたの誕生日の月、 これらは、そのアイデアです 本当にハッシュ関数に相関している。 それはちょうどそれを決定する方法です バケツあなたが要素だ[OK]を、に入る？ だから、これのpsetのため、あなたが調べることができます あなたが望むほとんどすべてのハッシュ関数。 あなた自身である必要はありません。 いくつかの本当にクールなものがそこにいる そこに狂気の数学のすべてのソートを行うこと。 そして、あなたはあなたを作りたい場合は、 超高速スペルチェッカ、 私は間違いだろう それらのいずれかに見える。 しかし、またある 計算のような単純なもの、 言葉の和、等 各文字には番号が付いています。 合計を計算します。 つまり、バケットを決定します。 彼らはまた、簡単なものを持っている ちょうどAのここでのすべてのようなもので、 Bのすべてがここにあるのです。 それらのいずれか。 基本的に、それはちょうどあなたに伝えている 配列インデックスあなたの要素が入るはずです。 ただbucket--を決定 それは、すべてのハッシュ関数であるだ。 そこでここでは、例を持っている 文字列の最初の文字だけ 私はちょうど話していたという。 だから、あなただけだいくつかのハッシュを持っている あなたの文字列を引いAの最初の文字、 あなたにいくつかを与えるもの 0と25の間の数。 そして、何あなたがしたいことはある これが表すことを確認してください あなたのハッシュのサイズtable-- どのように多くのバケットがあります。 これらの多くを持つ ハッシュ機能は、彼らがいる そのかもしれない値を返すことに行く 遠くバケットの数を超えること あなたが実際に持っていること あなたのハッシュテーブル、 だから、確認する必要があり 必ずそれらによるMOD。 それ以外の場合は、言うために起こっている、 ああ、それはバケツ5000にする必要があります しかし、あなたは唯一の30を持っている あなたのハッシュテーブル内のバケット。 そしてもちろん、我々はすべてのそれは知っている いくつかのクレイジーなエラーが発生するだろう。 そうすることによっておよびMODに確認してください あなたのハッシュテーブルのサイズ。 涼しい。 衝突そう。 誰もがこれまでのところは良いですか？ ビー·マイ·エスケイプ？ 読者：それはなぜだろう そのような大規模な値を返す？ SPEAKER 1：アルゴリズムに応じて、 あなたのハッシュ関数を使用する。 それらのいくつかさせていただきます クレイジー乗算。 そして、それは得ることについてすべてです 均一な分布、 ので、彼らは実際にいくつかの操作を行い 時々狂気の事。 それだけだ。 他には？ [OK]をクリックします。 衝突そう。 基本的に、私が先に言ったように、 最良のシナリオで、 私はに見てどのバケットがある 一つのことを持っているつもり、 私は右、全く見てする必要はありません？ 私はどちらかはそれがあると知っているか、それはだ ではない、それは私たちが本当に欲しいものだ。 しかし、我々は数十万のを持っている場合 データ点およびその数未満 バケットの、我々は持っているつもり 衝突場所最終的に何か に終わるために持っているとしている 既に要素を持ってバケツ。 そこで問題は、何ですか 我々はその場合に行うのですか？ 私たちは何をしますか？ 我々はすでにそこに何かを持っている？ 私達はちょうどそれを捨てるのですか？ いいえ。 私たちは、それらの両方を維持する必要があります。 我々だから、道 通常はそれが何であるか？ データ構造は何ですか 私たちはただの話？ 読者：リンクリスト。 SPEAKER 1：リンクリスト。 だから今、代わりにこれらのそれぞれの バケットはちょうど1つの要素を持つ それはのリンクリストが含まれているために起こっている それにハッシュされた要素。 [OK]を、誰もが親切なのアイデアを得るのでしょうか？ 我々は配列を持っていない可能性があるため、 私たちはどのように多くのことを知らないので、 そこにあることを行っている。 リンクリストは、私たちがすることができます ただ正確な数字を持っている 右、そのバケットにハッシュされている？ プロービングとても直線的である 基本的にこのidea-- それは、衝突に対処する一つの方法です。 あなたは何を行うことができ、この中で、あればある ケースは、ベリーは1にハッシュされた そして我々はすでに持っている 何かが、あなただけの まで押し下げ続ける あなたは空のスロットを見つける。 つまり、それを処理する一つの方法です。 処理するための他の方法 それはちょうど私たちとです リンクをcalled-- リストはチェーンと呼ばれています。 だから、このアイデアは、以下の場合に動作します あなたが考えるあなたのハッシュテーブル よりはるかに大きい あなたのデータは、設定したり、場合 試してみて、チェーン化最小限にしたい それは絶対に必要になるまで。 だから、一つのことは、線形である 明らかに意味のプロービング あなたのハッシュ関数という それほど有用ではありません あなたが使用して終了するつもりだので、 あなたのハッシュ関数、ポイントになって、 まであなたリニアプローブ 利用可能であるいくつかの場所。 しかし、今は、もちろん、何でも 、そこに終わるという他 あなたがする必要があるとしている さらにダウン検索。 そしてもっとたくさんあり​​ます 検索費用その 要素を入力することになり 今あなたのハッシュテーブルで、右か？ そして今、あなたが行くと試してみて、見つけたとき ベリー再び、あなたはそれをハッシュするつもりだ、 そしてそれは、言うために起こっている ああ、バケット1で見て、 それがあることを行っていない バケット1に、そうあなたがいる トラバースする必要があるとして これらの残りの部分を通して。 だから、時には便利だ しかし、ほとんどの場合、 我々はそれを言おうとしている 連鎖はあなたが何をしたいです。 だから我々はこの先にについて話しました。 私は自分自身の少し先を得た。 しかし、連鎖は基本的にあり あなたのハッシュテーブル内の各バケット ちょうどリンクリストです。 だから、別の方法、またはそれ以上の技術的 ハッシュテーブルを考えるための方法、 それだけで、配列であるということです リンクリストの、どの あなたの辞書を書いているとき そして、あなたはそれをロードしようとしている、 としてそれを考えて リンクされたリストの配列 それははるかに容易になります あなたは初期化す​​るために。 聴衆：だからハッシュテーブル 所定のサイズを有し、 バケットの[聞こえない]のような？ SPEAKER 1：右。 だから、一連の番号を持つ あなたがdetermine--バケット その君たちがすべき と遊ぶこと自由に感じ。 それはかなり涼しいことができます 何が起こるかを見るために あなたはバケットのあなたの数を変更するように。 しかし、ええ、それはあります バケットの数を設定します。 あなたにフィットすることができますどのような あなたが必要な多くの要素 あなた、この独立したチェーンです 各バケット内のリストをリンクしています。 それはあなたのハッシュテーブルを意味します 丁度サイズになります あなたはそれが、右する必要があること？ つまり、リンクリストの全体のポイントだ。 涼しい。 そこにそのように誰もOK？ わかりました。 ああ。 何が起こった？ 本当に今。 誰かが私を殺してだと思う。 [OK]を私たちは入るつもりです 少し狂っている試み。 私は、ハッシュテーブルのように。 私は、彼らが本当にクールだと思う。 試行は、あまりにも、かっこいいです。 だから、誰もが試しが何であるかを覚えているのでしょうか？ あなたは終わってしまっているはずです それを簡単にレクチャーで？ あなたはそれがどのように動作するかのようなものを覚えていますか？ 読者：私はちょうどうなずいてる 我々はそれを乗り越えたこと。 SPEAKER 1：我々は、その上に行くのですか。 [OK]を、私たちは本当に行くつもりです その上に、今私たちが言っているものです。 聴衆：検索ツリーのためだ。 SPEAKER 1：うん。 それは、検索ツリーです。 恐ろしい。 だからここに注意すべき一つのことは、その私たちです 個々の文字を見ている ここでは、右か？ だから私たちのハッシュ関数の前に、私たち 全体としての言葉を見ていた、 そして今、我々はより多くを探している 文字で、右？ だから我々はこことメンデルの上にマクスウェルを持っている。 そこで、基本的に考える方法をtry-- このことについて、そのすべてのレベルはここにある 文字の配列である。 だから、これはあなたのルートノードは右、ここですか？ これは、すべての文字が含まれている すべての単語の開始のためのアルファベット。 そして、何あなたがしたいことはある たとえば、[OK]を、我々はいくつかのMワードを持っている。 私たちはそのように、マクスウェルを探すつもりだ 我々は全体に、MとMのポイントに行く 他のアレイ場所ごとに 限り、そこに単語、 持っワードです 第二の手紙のように、 限り単語があることありますように 第二の手紙のようにBを有し、 それは、ポインタを持つことになります いくつかの次のアレイに行く。 おそらくそこにはありません 単語のMP何か、 この中でP位置でそう アレイは、それだけではNULLになります。 これは、[OK]を、全く言葉がありません、と言うでしょう それはMはOK、Pに続いたのか？ だから我々はそれについて考える場合には、各 これらの小さいものの一つ 実際にこれらの一つである AからZまで、大きな配列 それでは、ものの一つかもしれません それは、tryの欠点の一種である？ 読者：多くのメモリ。 SPEAKER 1：それは右、メモリのトンですか？ ここで、これらのブロックの各々は 26スペース、26素子アレイを表す。 だから、試みは信じられないほどのスペース重いを取得します。 しかし、彼らは非常に高速です。 信じられないほど高速だが 本当にスペース効率の悪い。 種類の把握する必要があります どちらからあなたが欲しい。 これらはあなたのpsetのために本当にクールである、 しかし、彼らは多くのメモリを占有しません、 だから、トレードオフ。 うん？ 読者：それは可能でしょう そのtryを設定し、する あなたはすべて持っている一度 あなたがneed--ことをその中にデータ それは理にかなっているかどうかは知りません。 私はすべてを退治した NULL文字が、その後、 あなたは、インデックスthem--することができないだろ SPEAKER 1：あなたはまだそれらを必要としています。 読者： - 同じように毎回。 SPEAKER 1：うん。 あなたができるように、NULL文字が必要 単語がそこにはない場合、あなたが知っている。 ベンは、あなたが欲しいものを持っていた？ [OK]をクリックします。 すべての権利、私たちはなるだろう もう少し行く 背後にある技術的な詳細へ 試してみて、例を介して動作。 [OK]を、これは同じものです。 リンクリストで、私たちの主なのに対し、 ？種類of--私が欲しい言葉は何ですか - ブロックを構築するようなノードだった。 トライでは、我々はまた、ノードを持っている しかしそれは異なって定義だ。 だから我々はいくつかのブール値を持っている 実際に単語かどうかを表します この場所に存在し、その後 私たちは、here--またはむしろ、いくつかの配列を持っている これはへのポインタである 27文字の配列。 これは、この場合には、このある 27--私はあなたのすべてが似ていると確信している、待って アルファベットの26文字があります。 なぜ我々は27を持っていますか？ だから、依存 あなたはこれを実装する方法、 これは、プロセッサセットからのものである アポストロフィを可能にした。 だから、なぜ、余分な一つだ。 あなたは、いくつかの中にもあるでしょう 例ヌルターミネータ の一つとして含まれています それがあることを許可のキャラクター、 それは彼らがチェックする方法です それは単語の終わりだかどうかを確認します。 あなたが興味を持っている場合、チェックアウトする study.cs50上のケビンさんのビデオ、 同様にウィキペディアがあります そこにいくつかの良いリソース。 しかし、我々はただ一種を通過するつもりだ あなたは、tryを介して動作する方法の あなたは1を与えられている場合。 だから我々はここでその超簡単1を持っている それらの単語「コウモリ」と「ズーム」を持っています。 そして、我々はここに見るように、 ここで、この小さなスペース 我々のブール値を表す はい、これは言葉である、と言います。 そして、これは私たちを持って 文字の配列、右？ だから我々は通過しようとしている この試みを「バット」を見つける。 だから、右、上から始まり？ そして我々は、bはに対応することを知っている 第二のインデックス、第二の要素 このアレイでは、aとbのため。 だから、およそ秒1。 そして、それはOK、クール、にその従ってください、と言う 次のアレイ、私たちは覚えていればいるため、 それはこれらの各ことではありません 実際に要素が含まれています。 これらの配列の各々は 右、ポインタを含む？ それは作るべき重要な区別です。 私は、これは試行をbe--しようとしているされている知っている 初めてに乗るために本当に一生懸命、 従って、この場合であっても 第二または第三の時間 そしてそれはまだのようなものだ 困難な見せかけの、 あなたが時計を行けば私は約束 明日再び短い、 それはおそらく、多くの方が理にかなっているでしょう。 それは消化するかかる。 私は今でも時々午前 のように、待って、試しては何ですか？ 私はこれをどのように使うのですか？ だから我々は、この場合のBきた その私たちの第二のインデックスです。 我々が持っていた場合は、たとえば、cまたは dまたは他の任意の文字、 私たちは、インデックスにその背中をマップする必要が それが対応するという我々のアレイ。 だから我々はrcharのように取ると、ちょうど私たち 0から25までにそれをマップするためにオフに引く。 どのように我々の良い皆 私たちの文字をマッピング？ [OK]をクリックします。 だから我々は第二の1、私たちに行く はい、それはNULLにはない、ことがわかります。 我々は、この次のアレイに移動することができます。 だから我々はここに、この次のアレイに進みます。 そして、我々は我々は今、[OK]を、言う ここにあるかどうかを確認する必要があります。 nullであるか、それをしない 実際に前進？ だから、実際に動く この配列に転送します。 そして、我々はOK、tは私たちの最後の手紙である、と言う。 だから我々は、インデックスでトンに行く。 そして、我々は前進する もう一つはそこだから。 この1つは、はい、基本的にはそれを言う その単語があることを言うhere-- あなたがこれをたどる場合に パスは、あなたが到着した 私たちが知っている単語、で「コウモリ」です。 はい？ 読者：それは標準のものを持つことである その後インデックス0として1での並べ替えを持って または終了時に持っている？ SPEAKER 1：いいえ。 だから我々は戻って私たちを見れば ここに宣言、それはブール値ですが、 そう、それはあなたのノードに独自の要素です。 だから、アレイの一部ではありません。 涼しい。 だから私たちは私たちの言葉を終え、私たちがいるとき この配列では、我々は何をしたいのか これが単語であるためチェックを行うです。 そして、この場合には、そう返す。 だから、そのノートに、私たちはその「動物園」を知っている - 私たちは、「動物園」は単語であることを人間として知って 右？ しかし、ここだろう試している いや、それはない、と言う。 そして、それはと言うでしょう、私たちのため ここで単語としてそれを指定されていません。 私たちは横断できるにもかかわらず この配列に至るまで、 この試みは、いや、それを言うだろう 動物園は、あなたの辞書にはない 我々はそうではありませんので、 そのように指定された。 that--やることが一つの方法 ああ、申し訳ありませんが、この1。 したがって、この場合には、「動物園」ではない 言葉が、それは私たちの試みである。 しかし、このいずれかで、我々はそれをしたいと言う 「お風呂は、「何が起こるの言葉を紹介する 我々はthrough-- B、Tに従っています。 我々は、この配列内だし、 我々は時間を検索するために行く。 この場合には、ときに我々 hにポインタを見て、 それは[OK]を、NULLを指すのですか？ だから、明示的でない限り 別の配列を指して、 あなたはすべてのポインタと仮定 この配列にはnullを指している。 したがって、この場合には、hが指している nullに私たちは何もできない、 そう、それはまた戻ってくる 偽の、「お風呂」は、ここでではありません。 だから今、私たちは、実際にしている 経由行くつもり 私たちは実際にどのように言うでしょう 「動物園」は私達の試みである。 どのように私たちは試しに "動物園"を挿入しますか？ 使い始めたのと同じ方法でそう 私たちのリンクリスト、我々はルートから始まる。 疑わしい場合に、で開始 これらの事のルート。 そして、我々は、z、[OK]を、と言うでしょう。 zがこの中に存在し、それはありません。 だから、上に移動している あなたの次のアレイ、OK？ した後、次のいずれかで、 我々はOK、oは存在しない、と言う？ それはありません。 この再び。 そしてそう私たちの次のいずれかに、我々は、言ってきた [OK]を、「動物園」はすでにここに存在します。 私たちがやらなければならないことは、これは等しく設定される trueに、そこに単語が存在すること。 あなたはすべてを追っていた場合 そのポイントの前まで、 それは言葉だけなので、 このように等しく、それを設定してください。 はい？ 聴衆：それではことを行います 「BA」も単語であることを意味ですか？ SPEAKER 1：いいえ。 したがって、この場合、「BA」に私たちはなるだろう ここで、我々は、それが単語であると言うでしょう それはまだ全くないであろう。 OK？ ビー·マイ·エスケイプ？ 読者：だから、それしたら 単語とあなたがそれそれから、イエスと言う mまで行くことが含まれます？ SPEAKER 1：これは関係しています with--あなたはこれを読み込んでいる。 あなたは、「動物園」は単語であると言う。 あなたがcheck--に行くとき のような、あなたが言いたいと言う、 「動物園」は、この辞書には存在していますか？ あなただけの「動物園」を検索するつもりだ そしてそれは、Wordのかどうかを確認してください。 あなたが移動するつもりはありませんしている mまでを通してそれがありませんので、 あなたが探しているもの。 だから我々は、実際にしたい場合 この試みに「風呂」を追加し、 我々は同じことをするだろう 我々が行ったように、「動物園」、 ときに我々我々はそれを見ることを除いて 試してみて、時間を取得、それは存在しません。 だから、しようと考えることができ リンクされたリストに新しいノードを追加するには、 私たちは別のものを追加する必要があります そうように、これらのアレイの1つ、。 そして、我々はただ時間を設定されている私たちは何をすべきか これに指してこの配列の要素。 そして、我々はここで何をすべきかをしたいですか？ trueに等しいことを追加します。 なぜならそれは言葉だ。 涼しい。 私は知っている。 試行は、最もエキサイティングではありません。 私が知っている、私を信頼しています。 試行で実現するので、一つのこと、 私は、彼らは非常に効率的だ、と述べた。 だから我々は彼らを見てきました スペースのトンを取る。 彼らは一種の混乱している。 では、なぜ私たちはこれまでにこれらを使用するのでしょうか？ 彼らがしているので、私たちはこれらのを使用 信じられないほど効率的。 だから、あなたが今まで探しているなら 単語まで、あなただけです 単語の長さによって制限。 ので、もしあなたが探している 長さ5である言葉、 あなたは今までに持っているつもり [OK]を、最大でも5比較を行う？ だから、それは基本的に一定になります。 挿入とルックアップのような 基本的には一定の時間である。 だから、あなたがこれまで得ることができるかどうか 一定時間内に何か、 それは恋愛小説家だ。 あなたがより良くなることはできません これらの事のために一定の時間。 だからの一つです 試行の巨大なプラス。 しかし、それは多くのスペースです。 だから、一種の決定する必要があります 何があなたにとってより重要だ。 今日のコンピュータ上で、 トライがかかる場合がありますスペース 多分に影響しません それだけあなたが、多分 あなたが何かを扱っている それは、はるかに、はるかに多くのものを持っています と試してはただ合理的ではありません。 はい？ 聴衆：待って、そうあなたは26を持っている すべての単一の1の文字？ SPEAKER 1：ビー·マイ·エスケイプ。 ええ、あなたは26を持っている。 あなたは、いくつかは、その後の単語マーカーであり、持っている あなたは一人一人で26のポインタを持っている。 そして、彼らはpoint--いる 聴衆：そしてすべての26、 彼らはそれぞれ、26を持っていますか？ SPEAKER 1：はい。 することができますようにそしてそれは、なぜだ それは非常に急速に拡大し、参照してください。 わかりました。 だから我々は、木に取得するつもりだどの おそらく簡単に、意志であるような気がする ちょっといい猶予も そこからトライ。 だから、うまくいけばあなたのほとんど 前のツリーを見てきました。 かなりのようではない 外のものを、どのI 誰かどうかわからない 最近屋外で行きました。 私はこの週末を選ぶリンゴに行きました、 そしておやっ私のああ、それは美しかった。 私は葉を知りませんでした そのかなり見ることができる。 だから、これは右、ちょうど木です？ それはちょうど、いくつかのノードだし、それ 他のノードの束を指す。 ここで見るように、これはある 繰り返されるテーマの一種。 ノードを指しているノードは、一種のである 多くのデータ構造の本質。 それはちょうど、我々方法によって異なります それらが互いに指してい そしてどのように我々はトラバース それらを通して、どのように我々 決定物事を挿入 彼らの異なる特性。 だからいくつかの用語で、 その私が前に使っています。 だから、根は非常に一番上には何でもある。 私たちは常に起動それはどこだ。 また、頭部と考えることができます。 しかし、樹木のために、私たちはする傾向 ルートとしてそれを参照してください。 下部には何もhere-- 非常に、非常にbottom--で 葉と考えられている。 だから、一緒に行く ツリー全体の事、右？ 葉はあなたの木の縁である。 そして、我々はまたのカップルを持っている 関係内のノードについて話をする用語 互い。 だから我々は、親を持つ 子供、兄弟姉妹。 したがって、この場合には、3である 5,6、および7の親。 だから、親が何であれです あなたがしている何でも上記の一歩 を参照すると、これだけ 家系図のような。 うまくいけば、これはすべて少しある ビットトライよりも直感的。 兄弟が持っている任意のものである 同じ親、右？ 彼らはここで同じレベルにしている。 そして私は、あったように と言って、子供たちはちょうどです 下の一歩は何でもある 問題のノード、OK？ 涼しい。 だから、バイナリツリー。 誰もが一つに推測ハザードことができます バイナリツリーの特性？ 読者：マックス2葉。 SPEAKER 1：右。 だから、2葉の最大。 だから前に、このいずれかで、私たちはこの1つを持っていた それは3を持っていましたが、バイナリツリーで、 次の2つの最大を持っている 親ごと子どもたち、右？ もう一つがあります 興味深い特徴。 誰もがそれを知っていますか？ バイナリツリー。 だから、バイナリツリーは、すべてのものを持つことになります the--上でこの1はsorted--ではありません しかしソートバイナリツリーで、 右の上のすべて 親よりも大きい 左側のすべてのもの 親よりも小さい。 そして、それはクイズでした 知っておくととても良い前に質問、。 だから我々はこれを定義する方法、 再び、私たちは別のノードを持っている。 これは何と非常によく似ています？ 二重に 聴衆：リンクリスト SPEAKER 1：二重リンクリスト、右？ だから我々はこれを交換した場合 前と次と、 これは二重にリンクされたリストになります。 しかし、この場合、我々は実際に 左右と、それはそれだしている。 それ以外の場合は、全く同じだ。 我々はまだ要素を持っている あなたが探している、 あなたがちょうど2つのポインタを持っている 次は何に行く。 うん、そう二分探索木。 我々は上の、すべてのものに気づいた場合 右ここthan--大きい またはすべてをすぐに ここで右に すべてのものよりも大きい ここで以下である。 だから我々は、それを介して検索した場合 バイナリ検索に非常に近いはず ここでは、右か？ 代わりに探して除く 半分の配列で、 私達はちょうど左のどちらかを見ている 側またはツリーの右側。 それは少しシンプル取得するので、私は思います。 だからあなたのルートがNULLの場合、 明らかにそれはちょうど偽です。 それがあります場合は、明らかにそれは本当だ。 それはより少ないなら、私たちは左を検索します。 それはより大きいなら、 我々は権利を検索します。 それは、正確にバイナリサーチのようなものだ わずかに異なるデータ構造 私たちが使用していること。 代わりに、アレイの、 それだけでバイナリツリーです。 [OK]を、スタック。 そしてまた、それは我々のように見える 少し時間があるかもしれません。 我々が行う場合、私は行くことがうれしい このいずれかの何度も繰り返し。 [OK]を、のでスタック。 誰もが何を覚えていますかstacks-- スタックのいずれかの特性？ [OK]を、私たちのほとんどので、私が思うに、 ダイニングで食べるhalls-- 私たちが好きではない可能性と同じくらい。 しかし、明らかに、あなたはスタックと考えることができます 文字通りトレーのスタックとして や物事の積み重ね。 そして、何が重要です 実現することがあるということです 特性をsomething-- 我々はそれがby--呼び出すことをLIFOです。 誰もがそれが何の略か知っていますか？ ビー·マイ·エスケイプ？ 観客は：後入れ先出し。 SPEAKER 1：右、後入れ先出し。 だから我々は知っていれば、私たちは物事をスタッキングしている場合 off--つかむための最も簡単な事、アップ そしておそらく唯一のことは、私たちはつかむことができる 私たちのスタックが大きくenough--であればオフ その最上位の要素です。 だから、何でもが上に置くた 私たちはここに見るように、last-- 何でも押された 最もrecently--にあり 最初になるだろう 我々はオフにポップなもの、OK？ だから私たちはここに持っていることである 別のtypedef構造体。 これは本当にただのようなものです データ構造内のクラッシュコース そう君たち投げつけたくさんあり​​ます。 私は知っている。 だから、さらに別の構造体。 構造用のイェーイ。 そして、この場合には、いくつかのポインタの いくつかの容量を持つ配列へ。 だから、これは私たちのスタックを表し ここでは、私たちの実際の配列のような それが私たちの要素を保持している。 その後、ここで我々はいくつかのサイズを有する。 そして一般的に、あなたが残しておきたい あなたのスタックがどのように大きなのトラック それができるように、何が起こっているので、 あなたはサイズがわかっている場合であるためには、 それはあなたが言うことができ、 [OK]を、私は容量でだ？ 私はより多くの何かを追加することはできますか？ そして、それはまたあなたに伝えます どこにあなたのスタックの最上位 だからあなたは何を知っている 実際に離陸することができます。 そして、それは実際に起こっている ここにもう少し明確にする。 だから、プッシュ、一つのことのために、あなたなら プッシュを実現するために、これまであった 私はちょうどあなたの、言っていたように スタックは、右、限られた大きさを有している？ 私たちのアレイは、いくつかの能力を持っていた。 それは配列です。 それは固定サイズなので、私たちのことを行う必要があり 我々はより多くを入れていないことを確認してください 私たちよりも私たちの配列へ 実際のためのスペースを持っている。 だから、プッシュを作成しているとき この関数は、あなたが最初にすることはOK、と言うである、 私は、スタック内のスペースを持っていますか？ 、私がいない場合は、申し訳ありませんので、 私はあなたの要素を格納することはできません。 私が行う場合は、保存したい スタックの一番上にそれ、右？ そして、これは私たちが持っている理由である 我々のサイズを追跡する。 私たちは私たちのサイズを追跡していない場合は、 我々はそれをどこに置くかはわからない。 私たちは、どのように多くのことを知らない すでに我々のアレイに含まれる。 当然のような方法があります それ多分あなたはそれを行うことができます。 あなたがNULLにすべてを初期化することができ その後、最新のNULLをチェックし、 しかしはるかに簡単なことは、ただで と言って、[OK]を、サイズを追跡する。 私が知っているように私は四つの要素を持っている 私のアレイでは、次のことは、そう 我々は上に置くことを、私たちはしている インデックス4で保存しようとして。 そして、もちろん、これはことを意味 あなたが何かを正常にプッシュしました あなたのスタックに、あなた サイズを増やしたい あなたが知っているように、あなたはとてもどこ あなたがより多くのものを上にプッシュすることができます。 だから我々はポップしようとしている場合 スタックから何か、 最初のものになるかもしれないもの 我々はチェックしたいこと？ あなたが取るしようとしている あなたのスタックから何か。 あなたは確かありますです あなたのスタックで何か？ いいえ。 だから何我々はチェックしたいかもしれません？ 読者：[聞こえない]。 SPEAKER 1：サイズを​​確認してください？ サイズ。 だから我々はどうかを確認したい 私たちのサイズは[OK]を、0より大きい？ それがある場合には、その後、我々は減少したい 0による私たちの大きさとはそれを返す。 なぜ？ 最初の1ではなかった プッシュ、我々はそれをプッシュ サイズと、更新サイズへ。 このケースでは、サイズをデクリメントしている その後、それを摘採、それを脱ぐ 私たちの配列から。 なぜ我々はそれを行うのでしょうか？ だから私は私のスタック上に一つのことを持っている場合、 その時点で私のサイズ何でしょう？ 1。 どこ素子1が格納されている？ 何されたインデックスにある？ 聴衆：0。 SPEAKER 1：0。 我々は、この場合はそう 常にsure--確認する必要があり 代わりに返す サイズから1を引いた、私たちのため 我々の要素があることを知っている 1未満で保管される予定 私たちのサイズが何であれ、この ちょうどそれの世話をする。 それはもう少しエレガントな方法だ。 そして私達はちょうど私たちをデクリメント サイズと、サイズを返す。 ビー·マイ·エスケイプ？ 読者：私はちょうど一般的に推測する、 なぜこのデータ構造はだろ 有益である？ SPEAKER 1：それはあなたのコンテキストに依存します。 理論のいくつかについてそう [OK]をwith--作業している場合、 有益なものがあるなら、私は見てみましょう それは外よりに有益である CSの。 スタック、あなたが必要とする任意の時点で その何かを追跡する 最も最近に追加されたときである あなたはスタックを使用するようにするつもりだ。 そして、私は良いと思うことはできません 今では右の例。 しかし、いつでも最新の 事があなたにとって最も重要であり、 それは時のスタックだ 便利になるだろう。 場合、私は考えるようにしようとしている このための良いものがあります。 私は次で良い例を考える場合 20分、私は間違いなくあなたを教えてくれます。 しかし全体的に、何があるのならば、 私はどこで、最新の、最も言ったように それは、最も重要なのである スタックは出番。 キューのに対し、反対の一種である。 そしてすべての小さな犬。 これは正しい、素晴らしいではありませんか？ 私は私がすべきように感じる ただバニーのビデオを持っている 右側の真ん中に 君たちのためのセクション これは強烈なセクションであるためです。 だから、キュー。 基本的にキューはラインのようなものです。 あなた私は確信してこの日常を使うよみんな、 ちょうど私たちのダイニングホールで好きです。 だから我々はに行かなければならない そして私は、私たちのトレーを取得 あなたは並んで待つために持っていることを確認 スワイプまたはあなたの食糧を得るために。 ここでの違いはそう これは、FIFOであるということです。 だから、LIFOは、まず、内の最後だった場合 アウト、FIFOは先入れ先出し、である。 だから、これはあなたがどこに置いた何でもあり 最初にあなたの最も重要である。 だから、待っていた場合には line--であなたをすることができ あなたが行けば想像する 新しいiPhoneを取りに行く それはスタックがあった場所 行の最後の人は、最初にそれを得た 人々はお互いを殺すだろう。 だから、FIFOは、我々はすべての非常に精通している ここで現実の世界のある、 そしてそれはすべて実際に関係しています この行全体を再作成するの種類 構造キューイング。 スタックと一方だから、 私たちは、プッシュとポップを持っている。 キューでは、我々は持っている エンキューおよびデキュー。 そこで、基本的な手段をエンキュー 背中の上にそれを置く、 とデキュー手段は取る 正面からオフ。 だから私たちのデータ構造である もう少し複雑。 私たちはを追跡するための第2のものを持っている。 これは、頭のないので、 右、正確にスタックです？ これにより、スタックと同様の構成である。 別の唯一の事は今ある あなたはどう思いますか、このヘッドを持っている を追跡しようとしている？ 読者：最初の1。 SPEAKER 1：右、 私たちが入れ最初。 私たちのキューの先頭。 誰でも行の最初です。 すべての権利、私たちは、エンキューを行う場合。 再び、のいずれか これらのデータ構造、 私たちは、アレイを扱っているので、 我々はスペースを持っているかどうかを確認する必要があります。 これは言ってちょっと私に似ている あなたたち、あなたがファイルを開いた場合、 あなたがnullかどうかを確認する必要があります。 これらのスタックのいずれか そしてキューは、次のものが必要です 私たちはだからスペースがあるかどうかを確認します 固定サイズの配列を扱う、 我々はすべての5までhere-- 0、1を参照してくださいよう。 だから我々は、その場合に何をすべきかのチェックがある 我々はまだスペースがあるかどうかを確認します。 私たちのサイズが容量より少ない？ もしそうであれば、我々はでそれを保存する必要がある 私たちは私たちのサイズを更新し、尾。 だから、尾は、この場合には何でしょうか？ これは、明示的に書き出されていない。 どのように我々はそれを格納でしょうか？ 尾は何でしょう？ それでは、この例を見てみましょう。 だから、これは右、サイズ6の配列である？ そして、我々は、今、私たちのサイズは5である必要があります。 我々はそれを入れたときに、それは起こっている 第五のインデックスに行くには、右？ だから、最後尾に格納します。 尾を書くためのもう一つの方法だろうちょうど サイズのインデックスで私達の配列は、正しいかも？ これはサイズ5である。 次のことは、5に入るだろう。 クール？ [OK]をクリックします。 それは、少し複雑になります 私たちは頭をいじり始めるとき。 はい？ 読者：それは、その私たちを意味しています 配列を宣言したであろう 五行長かったと その後我々はそれに追加している？ SPEAKER 1：いいえ。 したがって、この場合、これはスタックである。 これが宣言されるだろう サイズ6の配列として。 この場合において、我々 ちょうど1スペース左を持っている。 [OK]を、そのように一つのことは、この中にある 場合、私たちの頭が0である場合、 それから私達はちょうどのサイズでそれを追加することができます。 しかし、それは少しトリッキーを取得します 実際にので、それら スライドを持っていない このため、私は行くよ それはではないので1を描画する あなた一度かなり単純 物事を退治開始。 スタックと一方だから、 あなたは今まで持っている サイズが何であるかを心配する あなたは上に何かを追加しているとき、 キューにあなたも確認する必要があり あなたの頭を占めていることを確認してください、 キューに関するクールな理由 あなたが能力でいないのであればということで、 あなたが実際にそれがラップアラウンドすることができます。 [OK]を、ので、1 thing--ああ、 これはひどいチョークです。 考慮すべきことの一つは、ケースです。 私達はちょうど5をやる。 [OK]を、私たちはするつもりだ 頭がここにあると言う。 これは、0、1、2、3、4である。 頭はそこだし、 それらの中にものを持ってください。 そして、我々は右、で何かを追加したい？ 我々がする必要があるそうだ 知っている頭が常にあるということです このように動こうと その後ループバックの周りに、OK？ だから、このキューは、右のスペースを持って？ これは非常に最初に空間を有し、 これの反対のようなもの。 だから我々は何をする必要があるか、我々はある 尻尾を計算する必要があります。 あなたはあなたのことがわかっている場合 頭部移動していない、尾 でちょうどあなたの配列です 大きさの指標。 しかし、現実には、あなたは、キューを使用している場合、 あなたの頭はおそらく更新されている。 だから、何をする必要があるかである 実際にテールを計算します。 だから、私たちがやっていることは、この式は、 ここで、私はあなたを聞かせするつもりですどの みんな、について考え、 その後、我々はそれについて話をしましょう​​。 だから、これは容量です。 だから、これは実際になります あなたにそれを行うための方法を与える。 そのため、この場合、どのような？ 私たちの頭は1で、私たちのサイズは4です。 我々は5であることを法場合、我々は、0を取得 これはどこに我々はそれを入力すべきである。 それでは次のケースでは、 我々はこれを行うした場合、 我々はOK、のが何かをデキューしましょう​​、と言う。 我々はこれをデキュー。 我々は正しい、この要素を取り出す？ そして今、私たちの頭には、ここで指している そして、我々は別のものを追加したいと思います。 これは基本的に バック私たちのラインの、右？ キューは、アレイの周りにラップすることができます。 つまり、主な違いの一つだ。 スタックは、あなたがこれを行うことはできません。 キューに、次のことができます すべてのことの事項理由 あなたは何を知っているということです 最も最近追加された。 すべてがで追加されようとしているので この左方向、この場合には、 その後のことができ、ラップアラウンド 新しい要素を入れ続ける アレイの前で それは本当にありませんので、 もうアレイの前面。 あなたがの始まりと考えることができます あなたの頭が実際にある場所として配列。 したがって、この式がどのようにある あなたのしっぽを計算します。 それは理にかなっていますか？ [OK]をクリックします。 [OK]を、デキュー、および 君たちは、10分を持っている 私にどんな明確な質問をする 私はそれがクレイジーだ知っているので、あなたが、欲しい。 すべての権利なので、同じway--中 君たちは気づいたかどうかは知りませんが、 しかし、CSはすべてのパターンについてです。 物事はかなりある ほんの微調整と、同じ。 ここでそのように同じこと。 私たちは、実際に我々かどうかをチェックする必要があります 私たちのキュー内の何かを持っている、右？ [OK]を、0よりも私たちのサイズも大きい、と言う？ 涼しい。 我々が行うなら、私たちは私たちの頭を、移動する 私はちょうどここに実証したものです。 私たちは、1以上であることが私たちの頭を更新します。 そして、我々は我々のをデクリメント サイズと要素を返す。 はるかコンクリートがある study.cs50.net上のコード、 と私は非常に行くお勧めします あなたは時間があれば、それを通じて、 それだけの擬似コードであったとしても。 そしてあなたたちはスルー話をしたい場合は、 1上の私と1は、私を教えてください 知っている。 私は幸せになるだろう。 データ構造は、もし あなたは、CS 124を取る、あなたはよ データ構造は非常に得ることを知っている 楽しさと、これは始まったばかりである。 だから私はそれは難しいと知っている。 それはOKです。 私たちは、苦労しています。 私はまだやる。 だからそれについてはあまり心配しないでください。 しかし、それは基本的にあなたのである データ構造のクラッシュコース。 私はそれがたくさんあることを知っている。 その私たちは何がありますか 何度も何度も行きたいですか？ 私たちが通って話をしたい、何？ はい？ 読者：そのたとえば、そう 新しい尾は、その上で0になる？ SPEAKER 1：はい。 読者：[OK]をクリックします。 それではを通じて起こって、 あなたは1プラス4 or--があるんだけど SPEAKER 1：だからあなたが言っていた、 我々は再びこれを行うに行きたいとき？ 聴衆：うん。 あなたがゆうパックで考え出すされたかのようにどこにいる あなたはその中から尾を計算する？ SPEAKER 1：だから尾 私はこれを変更しin--た。 だからここに、この例では、これだった 私たちが見ている配列、OK？ そこで、1、2、3、及び4にものを持っている。 だから私たちは私たちの頭は、少なくとも1に等しい持っている この点は、私たちの大きさは4に等しい。 この時点で、右？ あなたのすべては、そのような場合だ同意する？ だから我々は、頭プラスのサイズを行うもの 私たちに5を与え、その後、我々は5で国防省。 我々は0であることを教えてくれるもの、0を取得 我々はスペースを持っている私たちの尾は、場所です。 読者：キャップは何ですか？ SPEAKER 1：容量。 ごめんなさい。 だから、あなたの配列のサイズです。 はい？ 読者：[聞こえない]の前に 我々は要素を返す？ SPEAKER 1：だから我々は動く 頭やモーメントを返す？ 我々は1を動かすのであれば、サイズをデクリメント？ ちょっと待って。 私は間違いなく別のを忘れてしまった。 気にしない。 別の式がありません。 ええ、あなたは戻りたいだろう 頭とそれを戻す。 聴衆：OK、このためで、 ポイント、ヘッドは0にあった、 そして、あなたは戻りたい インデックス0、次にヘッド1を作る？ SPEAKER 1：右。 私は別のがあると思う このようなの数式一種。 私は、トップに私の頭をそれを持っていない 私はあなたに間違ったものを与えたくない。 しかし、私はそれが完全に有効だと思う たとえば、[OK]を、このelement--を保存何でも 頭の要素があなたのをデクリメントis-- サイズは、あなたの頭の上を移動し、リターン どのような要素である。 それは完全に有効です。 [OK]をクリックします。 これではないような気が most--のようにあなたがわからない ここから歩いて行く はい、私は試みを知っている、などである。 私はそれをすべてを得た。 大丈夫。 私は約束します。 しかし、データ構造は何かされていることを それは慣れるのに時間がかかる。 最も難しいのはおそらく1 物事は、私は当然で、考える。 だから、それは間違いなくかかります 私at--反復と見て 本当にリンクされたリストを知りませんでした 私は彼らとあまりにも多くをやったまで、 同じ方法で、Iはなかった 本当にポインタを理解する 私は2つのためにそれを教えるために持っていたまで 年はそれで自分ののpsetを行う。 それは、繰り返しと多くの時間を要する。 そして最終的に、それは一種のクリックします。 しかし、その間に、あなたは親切があれば 何の高レベルの理解 これら行い、彼らの長所 何であるcons-- 私たちは本当に強調する傾向が、 特にイントロのコースで。 同様に、なぜ我々は使います アレイ全体のtry？ 同様に、陽性は何ですか それらのそれぞれのネガ？ とトレードオフを理解する これらの構造のそれぞれの間 今ははるかに重要だものです。 狂気の1があるかもしれません 質問または2の プッシュを実装するように依頼するつもりか ポップまたはエンキューおよびデキューを実装します。 ほとんどの部分は、それを有する より高いレベルの理解とより されている直感的な把握の 実際よりも重要 それを実装することができる。 あなたのすべての場合、それは本当に素晴らしいことだろう 外に出て、試しを実装行くことができる、 しかし、我々はそれは必ずしもありません理解する 今、最も合理的なもの。 しかし、あなたはあなたがしたい場合は、あなたのPSETでできる にし、次にあなたが練習を得るでしょう、 その後多分あなたはよ 実際にそれを理解しています。 はい？ 聴衆：OK、ものがあるので、 我々はPSETで使用するためのもの？ 私はそれらのいずれかを使用する必要がありますか？ SPEAKER 1：はい。 つまり、あなたの選択肢を持っている。 私は、私たちができる、この場合には、推測 少しのpsetの話 私はこれらを走ったので。 だからあなたのpsetで、あなたを持っている 試行またはハッシュテーブルの選択。 一部の人々がしようとします そして、ブルームフィルタを使用 しかし、それらは技術的には正しくありません。 彼らの確率的な性質のため、 彼らは時々偽陽性を与える。 彼らはしかし、中にクールな表情だ。 非常に見てお勧めします それらで少なくとも。 しかし、あなたはあなたの選択を持っている ハッシュテーブルとの間にトライ。 そして、それはどこになるだろう あなたの辞書にロードします。 そして、あなたは選択する必要があります あなたのハッシュ関数 どのように多くのあなたが選択する必要があります バケットはあなたが持っている、それは異なります。 あなたがより多くのバケツを持っている場合と同様に、 多分それはより速く実行します。 しかし、多分あなたは無駄にしています 多くのスペースそのように、しかし。 あなたがそれを把握する必要があります。 ビー·マイ·エスケイプ？ 読者：あなたは、その前に言った 我々は他のハッシュ関数を使用することができ、 我々はする必要がないこと ハッシュ関数を作成しますか？ SPEAKER 1：はい、右。 だから文字通りハッシュ関数のため、 Googleのような「ハッシュ関数」 そしていくつかのクールなものを探してください。 あなたが構築することが期待されていません 独自のハッシュ関数。 人々は彼らを過ごす これらの事についての論文。 だから、あなた自身を構築する心配しないでください。 で開始する1オンラインを検索します。 そのうちのいくつかはあなたに持っている 少し操作する 作るために必ず戻り値の型は一致 やその他もろもろ、そう初めに、 私は何かを使用してお勧めします 多分ちょうどその本当に簡単 最初の文字でハッシュします。 そして、あなたはその作業をしたら、 クーラーハッシュ関数を組み込む。 ビー·マイ·エスケイプ？ 読者：試しかであるか、 効率的なしかし、like--ちょうど困難 SPEAKER 1：だから試し、私が思うに、 実装するために、直感的には難しいです しかし非常に高速です。 しかし、より多くのスペースを占有します。 ここでも、業者の両方を最適化することができます 異なる方法や方法がありますto-- 聴衆：どのように我々は、この上の等級がありますか？ それはありませんmatter-- SPEAKER 1：それで、あなたは、通常の方法を段階的だ。 あなたは、設計上の等級ことになるだろう。 あなたは、あなたがしたいですかどちらの方法 それはそれができるようにエレガントだことを確認してください そしてそれができるように効率的。 しかし、あなたは、tryまたはハッシュを選択した場合 テーブル、限りそれが動作するように、 私たちはそれで満足しています。 そして、あなたはハッシュ何かを使用している場合 最初の文字で、それはいいのよ、 多分設計ワイズ様様。 我々はまた、到達している このsemester--のポイント あなたかどうかは知りません あなたはならnoticed--男 PSETグレードは少し断る デザインやその他もろもろの理由、 それは完全に罰金です。 それはどこにあなたのポイントになってきた プログラムは、より複雑きている。 より多くの場所があります。 あなたが上で向上させることができます。 だから、完全に正常です。 それはあなたがしていることではありません あなたのpsetに悪化しそう。 それはちょうど私たちが今あなたに難しくさいます。 だから、誰もがそれを感じています。 私はちょうどすべてのあなたのpsetを採点。 私は誰もがそれを感じていることを知っている。 だから気にしないでください。 そして、あなたはについてのご質問がある場合は 前のpsetまたはあなたが改善することができる方法、 私が試してみて、特定のコメント 場所が、時にはそれが手遅れ と私は疲れる。 他のものはありますか 約データ構造？ 私は、君たちが本当にないと確信している もはやそれについて話をしたい、 がある場合しかし、私はうれしいです それらの上に行くだけでなく、何でも 講義からこの過去 週または先週。 私は、先週は、すべてのレビューでした知っている 我々はいくつかのレビューをスキップしている可能性 講義から。 私は答えることができる他の質問？ OK、大丈夫。 さて、皆さんは、早期に15分を出す。 私は、これは少なくとも半有用だった願って、 と私は来週君たちが表示されます、 または木曜日の営業時間。 軽食のためにそこに要求されている 来週のために、それはことだ？ 今日はお菓子を忘れてしまったので。 そして、私は最後のお菓子をもたらした 週が、それは、コロンブスデーだった そう誰6人のようにありました 自分自身にキャンディの4袋を持っていた。 私はスターバーストをもたらすことができます 再びあなたが好きなら。 スターバースト？ OK、いいですね。 、素晴らしい一日みんなを持っている。