[音楽再生] DAVIDマラン：これはCS50です。 そして、これは開始との両方である literally--ほぼ終わりのようend-- 週6の。 私は共有したいと思った 楽しい事実を少し。 私はからリブログ引き上げられてきた 過去の学期のデータセット。 あなたは、私たちはすべての上をお願いすることを思い出すかもしれ あなたがオンラインで見てきた場合には、P·セット·フォーム またはあなたが個人的に出席してしまった場合。 そして、ここでのデータです。 だから、今日は非常に予測可能だった。 しかし、我々は少しを過ごすしたかった 時間のあなたと、それにもかかわらず。 誰もがなぜこれを推測したいと思います グラフは、アップダウン、アップダウン、そうジャギーです そう一貫して？ どのようなピークの各々を行う と谷が表す？ 読者：[聞こえない] DAVIDマラン：確かに。 そして、もっと面白いこと、神が禁じて、 我々は金曜日に1講座を開催 学期の初めに、 それは我々が起こる見るものだ。 だから、今日、私たちは少しは参加 データ構造の詳細。 そしてあなたに固体の多くを与えるために 5での問題のためのメンタルモデル、 これ、今出ている。 スペルミス、特徴、我々はよ 手あなたのテキストフ​​ァイル10万 プラス英単語、および あなたが持っているつもり 巧みにそれらをロードする方法を見つけ出すために メモリに、いくつかのデータを使用して、RAMに お好みの構造。 今、そのようなデータ構造は、可能性 ことが、おそらくすべきではない、 かなり単純化したリンクリスト、 その私たちが最後の時間を導入しました。 とリンクされたリストには、少なくとも持っていた 配列上の1つの利点。 の一つの利点は何ですか 間違いなくリンクリスト？ 聴衆：挿入。 DAVIDマラン：挿入。 あなたはそのことで何を意味するのですか？ 読者：どこに沿って リスト[聞こえない]。 DAVIDマラン：良い。 だから、どこに要素を挿入することができます あなたは、リストの途中で欲しい 何をシャッフルすることなく、 その私たちのソートで、結論 議論ではない 必ずしも良いこと、 実際に移動する時間がかかるため これらの人間の全てを左右。 そしてそう、リンクされたリストで、次のことができます ただ、malloc関数で新しいノードを割り当てる、 その後のカップルを更新 max-- 2、3の操作をpointers-- 私たちは誰かをスロットにできるしている リストに任意の場所で。 他に何が有利であった リンクリストはどうですか？ うん？ 読者：[聞こえない] DAVIDマラン：パーフェクト。 パーフェクト。 それは本当にダイナミックだ。 そして、あなたがコミットしていないことを、 事前に、いくつかの固定サイズへ メモリのチャンク、あなたがしているのと同じよう アレイの逆さまとする あなたが唯一の上のノードを割り当てることができるということです それによってのみできるだけ多くのスペースを使用してオンデマンド あなたが実際に必要として。 配列とは対照的に、あなたがかもしれない 誤って少なすぎるを割り当てる。 そしてそれはちょうど起こっている 首の痛みであると 新しい大きな配列を再割り当てするには、copy 古い配列を解放し、すべてのものの上、 その後、あなたのビジネスを動き回る。 良くも悪くも、あなたは道を割り当てるかもしれません あなたが実際に必要とするよりも多くのメモリ、 ので、あなたは非常に持っているつもり いわば、配列を過疎。 だから、リンクリストはあなたにこれらを提供します ダイナミズムと柔軟性の利点 挿入および欠失を持つ。 しかし確実に支払われる価格が存在しなければならない。 テーマ実際に、ある クイズゼロで探索 トレードオフのカップルがいた 我々はこれまで見てきました。 だから、支払った価格または何 リンクリストの欠点？ うん。 聴衆：いいえランダムアクセス。 DAVIDマラン：いいえランダムアクセス。 しかし、誰が気に？ ランダムアクセスが説得力のある音は鳴りません。 読者：[聞こえない] DAVIDマラン：その通り。 あなたが持っているしたい場合は 特定のalgorithm-- と私は実際に提案してみましょう 特にバイナリサーチ、どの 私たちはかなりbit--を使用しました1です もしランダムアクセスを持っていない場合、 あなたはその単純な算術演算を行うことはできません 真ん中の要素と同様見つける そして右のそれにジャンプする。 代わりに、最初に起動する必要があります 要素と直線的に左から検索 右にあなたが検索したい場合は、 中間または任意の他の要素。 聴衆：それはおそらくより多くのメモリを取る。 DAVIDマランは：より多くのメモリをとります。 どこにその追加的である メモリ内から来るコスト？ 読者：[聞こえない] DAVIDマラン：その通り。 ここで、このケースでは、持っていた 整数のリンクリスト、 そしてまだ我々は倍増している メモリー容量 我々はまた、これらのポインタを格納することによって必要とする。 今ではあまり大したことのよう あなたの構造体は大きくなる そしてあなたがいない番号を記憶しているが、 多分学生や他のいくつかのオブジェクト。 しかし、ポイントは確かに残っている。 だから操作の数 リンクされたリストに呼ばれていました N--リニアのビッグOのだった。 挿入や検索のようなもの または削除場合の要素 の一番最後にあることを起こった それがソートされていないかどうかをリスト。 時には、あなたが幸運を得ると中かもしれません これらの操作のため、下界 あなたがならも、一定の時間かもしれない 常に最初の要素を見て、 例えば。 しかし最終的に、私たちは約束した 聖杯を達成するために データ構造、または それらのいくつかの近似、 一定の時間を経て。 我々は、要素を見つけるか、要素を追加することができます またはリストから要素を削除する？ 我々は非常にすぐに参照しなければならない。 そしてそれは、そのいずれかを判明 私たちがしているメカニズムの 今日の使用を開始する予定、 Pの年間使用は、5を設定 実際にはかなり精通している。 例えば、これは束である場合 各試験の書籍、の 学生の最初のを持ってい その上で姓と名、 と私はからそれらを拾う 試験の終わりに、 それらはすべてき​​れいです ランダムな順序で多く、 そして我々は、ソートについて行くたい これらの試験はその結果、一度等級 それだけで非常に簡単だし、 より速く、それらをバック手へ 学生にアルファベット順に。 あなたの本能は何だろう このような試験の杭のため？ さて、あなたは私に似ている場合は、 これはMであることを表示されることがあり、 私は、ソートのにこれを置くつもりだ これが私のテーブルや私の床である場合 私は物事を広めています ゆうパックや私の配列really-- 私はそこにおけるMSのすべてを置くことがあります。 ああ。 ここで、Aは、だから私はかもしれないです こっちAsを置く。 ああ。 ここで私は行くよもうA.です こっちのことを置くために。 ここZ.は、別のMであるので、ここだ 私はこのような山を作り始めるかもしれません。 その後多分私は以降でいいと思う ソートの非常にせこい-LYソート 個々の杭。 しかし、ポイントは、私はなりです 私は左利きだ入力で と私はいくつかの計算されてしまいます その入力に基づいて決定。 それがで始まる場合、あそこにそれを置く。 それは、Zで始まる場合、それを上に置く そこに、との間のすべて。 だから、これはだ技法である 一般hashing-- H-A-S-H--として知られている これは一般のように取って意味 計算するためにその入力を入力して使用して 値は、一般的に数、およびその 番号は、ストレージへのインデックスです 配列のような容器。 換言すれば、私が持っているかもしれません ハッシュ関数は、私は私の頭の中でそうであるように、 その私が誰かの見たら Aで始まる名前、 私はそれをマップするつもりだ 私の頭の中でゼロに。 私はZで誰かを参照している場合と、私は今 私の頭の中で25にそれをマップするために行く その後にそれを置く 最後のほとんどの杭。 さて、あなたがいない私の脳を考える場合には しかし、Cプログラム、どのような番号ができた あなたは、同じ結果を達成するために頼る？ 言い換えれば、あなたの場合 ASCII文字Aを持っていた どのように決定するのですか 何バケツにそれを置くか？ あなたは、おそらくしたくない これ、バケット65に入れて あそこようなものだ 正当な理由なく。 あなたはAを置く場所を選択してください そのASCII値の面で？ どこのASCIIにしたいん 賢くバケツを思い付くする値 でそれを置くか？ 読者：マイナスA. DAVIDマラン：うん。 だから、マイナスAまたはマイナス 特に65それはだ場合は、 資本A.または98の場合 それは小文字のaをだ。 そしてその結果は、非常に、私たちができるようになる 簡単かつ非常に算術的に、 そのようなバケツに何かを置く。 だから、私たちが実際に行う判明 このだけでなくても、クイズ付き。 だから、あなたはあなたの丸思い出すかもしれません 表紙に仲間の名前を教える。 とTFの名が組織された アルファベット順にこれらの列に、 よく、それを信じるかどうか、 とき私たちのすべての80プラス 、グレードに他の夜集まりました 私たちのグレーディングプロセスの最後のステップ ビッグにクイズをハッシュすることです [聞こえない]のフロアのスペース そしてみんなのクイズをレイアウトする 彼らのTFの正確順 カバー上の名前、理由 それは私たちのためにはるかに簡単です その用いた線形を検索する 検索や賢さのいくつかの種類 彼または検索するためのTF 彼女の生徒のクイズ。 ハッシングのため、このアイデア であるあなたが見るだろうと 実際にはかなり非常に強力である ありふれた、非常に直感的な、 ずっとおそらく分裂などが挙げられる 統治は、週にゼロだった。 私早送りハッカソンへ 数年前。 これはZamylaとのカップルだった 他のスタッフの挨拶の学生 彼らが入って来たように。 そして、我々は折りたたみの全体の束を持っていた 名前タグとそこにテーブル。 そして、我々は組織化さ名札を持っていた 同様のようなあそこで そしてあそこZsは。 そしてそうTFの1は非常に巧妙に 命令としてこれを書いた 一日のために。 学期の週で12本 すべて完璧な感覚と皆を作った 何をすべきかを知っていた。 しかし、いつでもあなたがした 同じようにキューイングされ、 あなたが実装しようとしている ハッシュの同じ概念。 それでは、それは少し形式化してみましょう。 ここでは配列です。 それは、少しであることが描かれています 広いだけで視覚的に、描写するために、 私たちは、文字列を置く可能性があること このようなもので。 そして、この配列は、 明らかにサイズが26の合計の。 そして事が呼び出されます テーブルを任意。 しかし、これは単に芸術家の演出です ハッシュテーブルが何であるかの。 だから、ハッシュテーブルは今まで起こっている より高いレベルのデータ構造である。 一日の終わりに 私たちはあなたことを確認しようとしている ハッシュテーブルを実装することができる 多くのチェックイン·ラインのようなものです このような多くのハッカソンで 表には、試験の本をソートするために使用。 しかし、ハッシュテーブルである この高レベルのソート 配列を使用することができますコンセプト それを実装するためにボンネットの下に、 またはそれは長のリストを使用するか、またはさえなかった おそらくいくつかの他のデータ構造。 そして今、それはtheme--取っている これらの基本的な成分の一部 アレイおよびこの建物のように 長リストのようになりましブロック そして私たちが構築することができます他に何見て 食材のようなものの上に レシピに、より多くを作る 興味深く、有用な最終結果。 ハッシュテーブルを持つので、 我々はそれを実装する場合があります メモリ内に絵画的にこのような、しかし それはどのように実際にアップするコード化されたことがあります？ まあ、単にこれです。 すべて大文字で容量が、ちょうどある場合 いくつかは、例えば26 constant-- alphabet--の26文字のために 私は私の変数テーブルを呼ぶかもしれない、 と私はするつもりだと主張しているかもしれません char型星そこに、または文字列を置く。 あなたのであれば、それはこのように単純だ ハッシュテーブルを実装したい。 そして、まだ、これは実際には単なる配列です。 しかし、再び、ハッシュ テーブルには、今私たちはよです ただの抽象データ型を呼び出す 上に概念的なレイヤリングのようなもの もっと世俗的な何かの 今のアレイが好きです。 さて、どのように我々は行くのですか 問題を解決するでしょうか？ さて、以前の私は贅沢を持っていた ここでは十分な表スペースを持っていることの 私は置くことができるように、 クイズはどこでも私が望んでいた。 ようにすると、ここに行くかもしれない。 ZSはここに行くかもしれない。 Msはここに行くかもしれない。 そして私は、いくつかの余分なスペースを持っていた。 しかし、これはチート右のビットです 今、このテーブルのため、実際に私の場合 配列のようなものと考え、ちょうどある いくつかの固定サイズになるだろう。 だから、技術的には、私が引っ張っている場合 別の生徒のクイズアップ そしてこの人の、ああ、参照してください。 名前は、あまりにもAで始まる 私は種類のそれをそこに置きたい。 しかし、すぐに、私はそこにそれを置くように、もし この表には、実際に配列を表し、 私はオーバーライドまたはつかうことするつもりだ 誰でもこの生徒のクイズです。 右？ これが配列の場合、一つだけ缶 これらの細胞または要素のそれぞれに行く。 そして、私は一種の持っている ピックアップして選択します。 さて、以前の私のようなもの このまたは私を騙していた だけの種類の積層 互いに上記の彼ら。 しかし、それはコードの中で飛ぶことはないだろう。 だから私はどこに置くことができる 名前は第二学生 Aは私が持っていたすべてはこれである場合である 利用可能な表スペース？ そして、私は3つのスロットと、それを使用しました わずか数他がありますように見えます。 あなたは何ができますか？ 読者：[聞こえない] DAVIDマラン：うん。 多分ちょうどそれをシンプルに保つみましょう。 右？ 私はそれを置きたい場所、それは適合しません。 だから私はそれを置くつもりだ 技術的にはここで、Bは行くだろう。 さて、もちろん、私が始めている コー​​ナーに自分自身をペイントする。 私は学生に取得する場合 名前が実際にBであり、 現在、Bは少し移動されようとしている フォワードとしてはうん、起こるかもしれない、 これがBであれば、今ではここに行かなければならない。 ので、この非常に迅速に 問題となる可能性があり、 それは実際にテクニックだ プロービング線形と呼ばれ、 あなたは自分を検討することにより アレイは、行に沿うようである。 そして、あなたは単にプローブの種類や 利用可能な各要素を検査 利用可能なスポットを探している。 とすぐあなたが見つけるように 1、あなたはそこにドロップします。 さて、価格は今支払われている このソリューションのために何ですか？ 我々は、固定サイズの配列を持っている、 と私は名前を挿入したとき その中に、少なくとも最初は、何ですか 挿入の実行時間 学生を「置くため 右のバケットでクイズ？ 何のビッグOの？ 聴衆：N。 DAVIDマラン：私は、nのビッグOのを聞いた。 真実ではない。 しかし、我々は離れていじめるよ なぜ一瞬で。 それは他に何でしょうか？ 読者：[聞こえない] DAVIDマラン：そして私は視覚的にそれをやってみましょう。 だからこの手紙Sであると仮定し 聴衆：それは一つだ。 DAVIDマラン：それは一つだ。 右？ これは、どの配列です 我々は、ランダムアクセスを持っていることを意味します。 そして、私たちはこの考えている場合 25ゼロこのような、 そして我々はそれを実現するため、 ああ、ここに私の入力Sです、 私は確かに変換することができます S、ASCII文字、 対応する数 ゼロと25の間 その後すぐに それが属する場所に置きます。 しかし、もちろん、とすぐに私がに着くように 名前の二人目は、AまたはBまたはC 最終的に、私が使用した場合には 私の解決策としてプロービングリニア、 の実行時間 最悪の場合には挿入 実際にどのように委譲しようとしている？ そして、私はここでそれを聞いてなかった 正しく早い段階で。 読者：[聞こえない] DAVIDマラン：だからそれはかつて確かにnとする あなたが十分に大きなデータセットを持っている。 したがって、一方では、もし あなたの配列が十分な大きさ そして、あなたのデータはあなたが、十分に希薄である この美しい時定数を得る。 しかし、すぐに作業を開始するように より多くの要素を取得し、 ちょうど統計的にあなたが得る 手紙を持つ多くの人々 として自分の名前や手紙 Bは、潜在的可能性 何かもっと直線的に委譲。 だから、非常に完璧ではない。 だから我々はやれること？ さて、私たちのものだった ときに我々の前に解決策 より多くのダイナミズムを持ちたい 許可された配列のようなもの？ 読者：[聞こえない] DAVIDマラン：我々は何を紹介したのですか？ うん。 だから、リンクリスト。 さて、リンクされたものを見てみましょう リストには、代わりに私たちのために行う可能性があります。 さて、私は、その私たちを提案してみましょう 次のように絵を描く。 さて、これは異なっている 例からの画像 別のテキストから、実際には、その 実際にはサイズ31の配列を使用している。 この著者は、単に 文字列をハッシュすることを決めた 人名に基づいていない、 しかし彼らの生年月日に基づいて。 かかわらず、月の、彼らが考え出し あなたは月の最初の日に生まれている場合 または月の31日、作者 その値に基づいてハッシュ化する、 少し外に名前を広がるように ちょうど26のスポットが許すかもしれないよりもっと。 そして、おそらくそれは少しより均一だ アルファベット文字と一緒に行くよりも、 理由はもちろん、おそらくあります 名前を持つ、世界で多くの人々 それは、より確かで始まる アルファベットのいくつかの他の文字。 だから、多分これは少しある より均一と仮定すると 一様分布 今月渡って赤ちゃんの。 しかし、もちろん、これはまだ不完全である。 右？ 私たちは、衝突を抱えている。 この中で、複数の人 データ構造は、依然として 少なくとも同じ誕生日を持つ あなたは関係なく、月のだ。 しかし、著者は何をしたのか？ 我々は配列を持っているようにまあ、それは見えます 垂直に描かれた左側に、 それはちょうどアーティストの演奏だ。 それは問題ではありませんどのような方向ます 配列を描く、それはまだアレイだ。 これは明らかの配列は何ですか？ 読者：リンクリスト。 DAVIDマラン：うん。 それはだように見えます リンクリストの配列。 だからもう一度、ソートのこの時点まで 現在、これらのデータ構造を使用する それ以上の成分として 興味深いソリューション、 あなたは絶対に取ることができます 配列のような、基本的な、 そして、より多くの何かを取る リンクリストのような興味深い とさえさえにそれらを組み合わせる より興味深いデータ構造。 そして実際に、これはあまりにだろう ハッシュテーブルと呼ばれる、 それによって配列である 実際には、ハッシュテーブル、 しかし、そのハッシュテーブルはあります チェーン、いわば、 それはに基づいて拡大または縮小することができます 挿入したい要素の数。 さて、それに応じて、何が 今の時間を実行している？ 私は誰かを挿入したい場合は その誕生日10月31日である、 彼または彼女はどこに行くのでしょうか？ わかりました。 それは31と言う非常に下部にある。 そして、それは完璧だ。 つまり、一定の時間でした。 しかし、我々は他の誰かを見つける場合には その誕生日です、見てみましょう、 10月、11月、12月31日？ どこ彼または彼女は行くつもりですか？ 同じこと。 しかし二つのステップ。 つまり、それはしかし、一定ではないですね。 わかりました。 現時点ではそれがある。 しかし、一般的な場合において、 我々は追加より多くの人々、 確率的に、我々はつもりだ より多くの衝突を取得します。 さて、これは少しある より良い技術的理由 今、私のチェーンは中かもしれない 最悪の場合どのくらい？ 私は、このよりにn個の人を挿入した場合 高度なデータ構造であり、n人 最悪の場合、それがn個になるだろう。 なぜ？ 読者：ので、もし誰も 同じ誕生日を持つ、 彼らは一行ことになるだろう。 DAVIDマラン：パーフェクト。 それは少し不自然かもしれませんが、 しかし、本当に最悪の場合には、 全員が同じ誕生日を持つ場合、 あなたが持っている入力が与えられ、 あなたが持っているつもり 大規模な長鎖。 だから、あなたはそれを呼び出すことができ テーブルをハッシュが、本当にそれはだ とだけ大規模なリンクリスト 無駄なスペースの全体の多く。 しかし、一般的に、私たちはと仮定した場合 少なくとも、誕生日はuniform--です そしてそれはおそらくありません。 私はそれをアップする作ってるんだ。 しかし、我々は仮定した場合、用 議論のために 彼らは、その後理論的には、場合であること これは垂直表現です アレイで、よくして、うまくいけばあなたがいる あるチェーンを取得するつもり、あなたが知っている、 ほぼ同じ長さの場所のそれぞれ これらは、その月の日を表す。 月に31日間があるかどうか、今、 それは本当に私の走行時間を意味し、 31以上のn個のビッグOが、ある リニアよりも良い感じ。 しかし、私たちの一つ何だった 公約数週間 前にそれを表現するに来たときはいつでも アルゴリズムの実行時間？ ただ唯一の高次項を見てください。 右？ 31は間違いなく便利です。 しかし、これはまだ、nのビッグOで。 しかし、テーマの一つ 問題は、5つの設定 になるだろう 絶対にそれを認める、 漸近的に、理論的には このデータ構造 ただ同然ではない 1大規模なリンクリスト。 実際、最悪の場合には、この ハッシュテーブルには、その中に委譲可能性があります。 しかし、現実の世界では、私達と人間 その自身のMacやPCまたは何 そして現実の世界を実行している 実世界のデータ上のソフトウェア、 どのアルゴリズムあなたが好むするつもりですか？ 終了ステップまたは取るもの かかるnは31の手順で割った1 データの一部作品を見つけるために、または いくつかの情報を検索するには？ 私は絶対に31になり、意味 現実の世界の違い。 それが31倍高速である。 そして私たち人間は確かにある ことを理解しようとして。 だから、二分法を実現 そこに実際に間 理論的に物事について話 間違いと漸近的にどの 私たちが見てきたように値を持ち、 しかし現実の世界では、 あなただけのことを心配している場合 一般的な入力のための人間の幸せ、 あなたは非常によく受け入れたいかもしれません はい、これが線形である、という事実は、 それが31倍高速だ より直線的である可能性があります。 そしていっそのこと、私たちはする必要はありません 誕生日のような任意の何かを、 我々は少しを過ごすことができ より多くの時間と賢さ そして私たちがやるかもしれないものを考え、 多分人の名前を与えられ、 それらを組み合わせることが彼らの誕生日 何かを把握するための成分 それは本当に多い 均一かつ少ないジャギー、 ので、この絵よりも、話すこと 現在、それは可能性があります示唆している。 どのように我々はコード内でこれを実装するだろうか？ さて、私は、その私たちを提案してみましょう ちょうど私達がしたいくつかの構文を借りる これまで数回を使用していました。 と私は定義するつもりです 再びノード、 ほんの一部の総称である いくつかのデータ構造のコンテナ。 私はそれを提案するつもりだ 文字列がそこに起こっている。 しかし、我々は服用開始するつもりだ 今、これらの補助輪オフ。 これ以上のCS50ライブラリない 本当に、あなたが望む場合を除き あなたの最後のためにそれを使用する 結構ですプロジェクトは、 しかし、今、私たちは引き戻すするつもりだ カーテンとそれだけでchar型のスターだと言う。 だから、そこに言葉があることを行っている 問題になっている人の名前。 そして今、私はリンクを持っている ここで次のノードに これらが表すように ノードの各々 チェーン内の、潜在的に、 リンクリストの。 そして今、どのように私は宣言しない ハッシュテーブル自体？ どのように私はこの全体の構造体を宣言しますか？ まあ、本当に、私はポインタを使用し多くのように リストの最初の要素だけに 前、同じように私は言うことができます 私はちょうどポインタの束を必要とする この全体のハッシュテーブルを実装します。 私は配列を持っているつもりだ ハッシュテーブル用のテーブルと呼ばれる。 それは、サイズ容量であることになるだろう。 それはそれで収まることができますどのように多くの要素です。 これで、これらの要素のそれぞれ アレイは、ノードのスターになるだろう。 なぜ？ さて、この絵あたり、私は何だ ハッシュテーブルなどを実装 効果的に初めにちょうどある 我々は垂直に描かれてきたこの配列、 その正方形の各 ポインタを表す。 スラッシュを持っているものという それらを介してだけではnullです。 そして持っているものは、 右に行く矢印 実際のノードへの実際のポインタである、 リンクリストの開始をエルゴ。 だからここに、その後、どのように我々はかもしれないです ハッシュテーブルを実装する 別々のチェーンを実装しています。 今、私たちはより良い行うことができますか？ すべての権利は​​、私は最後の時間を約束したこと 我々は、一定の時間を達成することができます。 そして、私は一種のあなたを与えた ここで、一定時間、 が、その後、本当にいないと述べ 一定の時間、それはまだだから 合計に依存 素子数 あなたが入力することにしている データ構造。 しかし、我々はこれをしなかったとします。 私はこっちの画面に戻りましょう。 明確な、私はまたここにこれを投影してみましょう 画面には、と私はこれをしなかったとします。 私は名前を挿入するとし Davenの私のデータ構造に変換する。 だから私は、文字列を挿入したい データ構造にDaven。 私は何を使用していない場合は、 テーブルをハッシュが、私は使用し さらに重要なものツリー状 家系図のような あなたは、いくつかのルートを持っている トップその後ノードとリーフ それが下向きと外側に行く。 、そのIと仮定する Davenのを挿入したい 現在、空のリストに何に。 私は、次の操作を実行するつもりです：私は このファミリ内のノードを作成するつもり ツリー状のデータ構造に見える それぞれのこのような小さな 長方形があり、それでは言わせて、 その中に今26要素について。 そして、各セル この配列に起こっている アルファベットの文字を表します。 具体的には、私が治療するつもりです これは、次にB、次にC、次いでDである ここで、この1。 だから、これは効果的にしようとしている 手紙D.を表す しかしDavenのすべてを挿入する 私はもう少しを行う必要が名前を付けます。 だから私は最初いわば、ハッシュするつもりです。 私は最初の文字を見てするつもりです Davenのは明らかにDであるもので、 と私は割り当てるつもりです 見えノード のような大きな大きな四角形をthis-- 全体アルファベットを収まるほど。 今、Dが行われます。 今A. D-A-V-E-Nは目標である。 だから今、私はするつもりです何これです。 できるだけ早く私は、D通知を始めとして そこにはポインタがありません。 これは、現時点では、ガベージ値の または私はヌルに初期化可能性があります。 しかし、私は一緒に行く続けるみましょう ツリーを構築するこのアイデア。 私はこれらの別のものを割り当てさせ その中に26の要素を持つノード。 そして、あなたは何を知っていますか？ これは、メモリ内だけのノードである場合、その 私は、構造体を使用して、malloc関数を使用して作成 我々はすぐにわかりますように、 私はthis--するつもりです 私はから矢印を引くつもりだ ダウンDを表すもの この新しいノードに。 そして今、第一次の Davenの名前の文字、 私が先に行くつもりV--のD-A-V-- そして、このように別のノードを描き、 それによって、ここにV族元素、どの 我々はinstance--おっとために描きます。 私たちはそこに描画されません。 それはここに行くために起こっている。 その後、我々はするつもりだ これはV.であると考える その後、ここまで私たちはインデックスになるだろう ダウンVから我々はEを検討します何に その後、ここから私たちはするつもりだ ここでこれらのノードのいずれかを持って行く。 そして今、我々は答えるために質問があります。 私は何とかあることを示すために必要 私たちは、文字列の末尾にDavenだ。 だから、僕はそれがnull残すことができる。 しかし、我々はDavenのが何を持っている場合は、 フルネームも、その 我々は、ダベンポートと述べてきたように、ありますか？ だからDavenは何である場合 実際に部分文字列、 はるかに長い文字列の接頭辞？ 私達はちょうど永久にできない 何も起こっていないと言う 我々は可能性があるので、そこに行くために ダベンポートのような単語を挿入することはありません このデータ構造に だから我々は何ができるか、代わりです これらの各要素を処理する 多分2を有するものとして それらの内の要素。 一つは、確かに、ポインタである 私が行ってきたように。 これらのボックスのため、各 ただ一つのセルではありません。 しかし、どのような場合トップ 底の1のひとつ選ぶ ので、ヌルになるだろう ただまだダベンポートありません。 何なら、トップ1 いくつかの特別な値はありますか？ そして、それは少しになるだろう それをこのサイズを描画するのは難しい。 しかし、それだけでチェックマークだと仮定します。 チェックしてください。 D-A-V-E-Nが文字列である このデータ構造である。 一方、私はより多くのスペースを持っていた場合 ここで、私は、P-O-R-Tを行うことができます と私は、ノードにチェックを入れることができます それは非常に最後に手紙Tを有する。 だから、これは大規模である 複雑に見えるデータ構造。 そして、私の手書き 確かに助けにはならない。 しかし、私は、何かを挿入したい場合 他に、私たちはどうなるのかを検討してください。 我々はデビッドを入れたい場合は、 私たちは、同じロジック、D-A-Vに従うだろう しかし、今私は次に指すことになり 要素ではないEから、私からDへ そうであるように起こっている このツリー内の複数のノード。 私たちは、以上のコールのmallocを持っているつもりです。 しかし、私はしたくない この絵の完全な混乱。 それでは、1つではなく、見てみましょう その、プリ策定されています このようにして、ドットをドットではない、 ドットが、ちょうど略さ配列。 しかし、各ノードの ここでは、この木のアップで 同じthing--を表し サイズ26の配列レイ。 または私達はなりたい場合は、 本当に適切な今、何を 誰かの名前などの場合 アポストロフィ、レッツ 各ノードが実際に持っていることを前提とし その中に27のインデックスだけでなく、26のような。 だから、これは今のデータであることを行っている 構造はtrie--、T-R-I-Eと呼ばれる。 たぶんあるトライ、 ツリーの歴史的に巧妙な名前 そのはのために最適化さだ もちろん、検索、 それはトライですので、I-Eで綴られている。 しかし、それはトライの歴史です。 だから、トライがこのツリー状のデータであり、 家系図のような構造 それは、最終的にはそのように動作します。 そして、ここでのほんの一例です 他の人の名前の全体の束。 しかし、今の質問 手元に持っているものです。 我々は間違いなく、よりを導入することによって得られる 複雑なデータ構造、および一 率直に言って、それは大量のメモリを使用しています。 、たとえ理由 現時点では、私が唯一だ D'sのポインタを使用して AとVとESとNS、 私は多くのメモリの一体を無駄にしています。 しかし、私は一つのリソースを費やす場所、 私は戻って別のものを獲得する傾向があります。 だから私はより多くのスペースを費やしている場合には、 おそらく望み何ですか？ 私は何より少ない支出てること？ 読者：少ない時間。 DAVIDマラン：時間。 さて、なぜそれがでしょうか？ さて、挿入は何ですか 時間、今やビッグOの観点から、 Davenのような名前の またはダベンポートまたはデビッド？ さて、Davenは5つのステップだった。 ダベンポートは、9つのステップになり、 ので、それはさらにいくつかの手順になります。 デビッドは、同様に5つのステップになります。 だから、それらは、コンクリートである 数字、しかし確実にあります の上限 誰かの名前の長さ。 そして実際、問題で 5仕様のセット、 我々は提案するつもりだ それは何か、その それが40-いくつか奇数の文字です。 現実的には、誰も持っていません 無限に長い名前、 αの長さということである 名前または当社がかもしれない文字列の長さ の特定の状態を有する 構造は間違いなく何ですか？ それは一定です。 右？ それはのような大きな一定かもしれない 40代が、それは一定である。 そしてそれはどのように多くのへの依存を持たない その他の名称は、このデータ構造である。 換言すれば、I場合 今挿入したかった コルトンまたはガブリエルまたはロブまたはZamylaまたは アリソンまたはベリンダまたはその他の名前 スタッフからこのデータに変換 構造は、実行時間である 他の名前を挿入する 全く影響されようとして どのように多くの他の要素によるものである 既にデータ構造内？ そうではありません。 右？ 我々は効果的に使用しているため この多層ハッシュテーブル。 との実行時間 これらの操作のいずれか の数に依存しているではない データ構造内の要素 最終的にしようとしているか データ構造内とすることで、 しかし、どのような特別の長さ？ 対象の文字列 作るんおり、挿入された この漸近的に一定 1のtime--大きなO。 と率直に言って、ただで 現実の世界では、この Davenの名前をとり挿入手段 5つのステップ、またはダベンポート9様 ステップ、またはデビッドの5つのステップ。 それはかなりくそ小さな実行時間です。 そして、確かに、それは非常にだ 良いこと、特に それは総に依存しません そこにある要素の数。 だから我々はこれを実装する方法 コー​​ド内の構造の種類は？ それはもう少しだ 複雑な、まだそれはだ のアプリケーションだけ 基本的なビルディングブロック。 私は再定義するつもりです 私たちノードを次のように BOOL word--と呼ばれ、この 何でも呼び出すことができた。 しかし、ブール値を表す 私は、チェックマークとして描いたもの。 はい。 これは文字列の終わりです このデータ構造である。 もちろん、ノードスター 子供に言及がある。 そして、確かに、ただ好き 家系、あなた ノードを検討する それをオフにぶら下がっている 一部の親の底部の 子どもされる要素。 だから子供たちがしようとしている 27の配列を、27日いずれかになり ちょうどアポストロフィためのものである。 私たちは、ソートするつもりだ 特別な場合のこと。 ですから、特定のを持つことができます アポストロフィを含む名前。 多分ハイフンべき そこに行くが、あなたはよ p個セット5我々は唯一のケアに表示 文字やアポストロフィ約。 そして、あなたはどのように表すか データ構造自体？ どのようにルートを表します このトライの、いわば？ さて、あなたは、リンクされたリストと同じように 最初の要素へのポインタを必要としています。 トライであなただけのいずれかが必要 このトライのルートへのポインタ。 そこからあなたがハッシュすることができます あなたのようにダウンして深く深く 構造内の他のすべてのノードに。 だから、単純にこの缶の持つ 私たちは、その構造体を表しています。 今ああ、質問をMeanwhile--。 読者：BOOL言葉は何ですか？ DAVIDマラン：ブール·ワードがある ちょうどこのC化身 私が説明したものの ここでは、ときに、このボックスに 私は、それぞれの分割開始 2ピースに配列の要素。 一つは、次のノードへのポインタである。 もう一つは、である必要があります チェックボックスのようなもの はい、ありますと言って ここで終了Daven語、 私たちはしたくないので、 現時点では、デイブ。 Daveはあることを行っているにもかかわらず 合法的な言葉は、彼がトライではありません まだ。 そしてDは言葉ではない。 とD-Aは、単語や名前ではありません。 だから、チェックマーク あなただけ一度示している このノードがヒット 文字の前の道 実際にあなたが挿入した文字列。 だから、すべてのブール値です そこには私たちのためにやっている。 トライ上の任意の他の質問？ うん。 聴衆：オーバーラップとは何ですか？ あなたがDaveとDavenを持っている場合はどうなりますか？ DAVIDマラン：パーフェクト。 あなたがDaveとDavenを持っている場合はどうなりますか？ 我々は挿入した場合ので、ニックネームを言う David-- Dave--のD-A-V-Eの？ これは実際に超簡単です。 だから我々は唯一の4つのステップを取るつもりだ。 D-A-V-E。そして、私はに何がありますか 私はその第4のノードを打つ一度やる？ ちょうどチェックしよう。 我々はすでに行ってもいいです。 Doneを。 4つのステップ。 漸近的に一定の時間。 そして今、我々はそれが両方のデイブ示さきた そしてDavenは、構造内の文字列です。 そうではない問題。 そして、どのように存在に気づく Davenのそれをしなかった いつでも多かれ少なかれを取る デイブおよびその逆のための時間。 だから我々は今、他に何ができますか？ 私たちは前にこの比喩を使ってきた トレーのようなものを表す。 しかし、それはことが判明 トレイスタックは、実際に 別の抽象データの実証 より高いレベルのデータ構造type-- 終わりの日はちょうどであること 配列やリンクリストのような 以上の世俗的な何か。 しかし、それはもっと面白い 概念的なコンセプト。 これらのようなスタック、 ここメイザーでトレイ、 一般的に呼ばれている ちょうどスタックをthat--。 データ構造のこの種の あなたは2 operations--を持っている あなたがのために1いわゆるプッシュを持っている スタックに何かを追加 別のトレイを置くように スタックの一番上にバックアップします。 そして、あなたを意味する、ポップ 一番上のトレイを脱ぐ。 しかし、どのようなスタックに関する重要なのは、ということです それがこの奇妙な特性を持っている。 食堂のスタッフの通りです 次の食事のためのトレイを並べ替える、 何がになるだろう どのように学生約真 このデータ構造と相互作用？ 読者：彼らは1オフをポップするつもりだ。 DAVIDマラン：彼らはするつもりだ 1オフ、うまくいけばトップをポップ。 それ以外の場合は、だけの種類の愚かだ 底にすべての道を行く。 右？ データ構造は、実際には許可しない あなたは、少なくとも底のトレイをつかむために 簡単に。 したがって、この好奇心があります スタックへのプロパティ 最後の項目であること 最初の1外になるだろう。 およびコンピュータ科学者が呼び出す これは後入れ先出しLIFO--。 そして、それは実際に持っているん 興味深い応用。 それは必然的にいくつかのように明確ではありません 他のものは、それが、実際には、有用であり得る それは、実際に実現することができる いくつかの異なる方法で。 だから一つであり、実際に、みましょう 私にその飛び込むまでもありません。 のではなく、これをやってみましょう。 ほとんどの1を見てみましょう 同じ考えが、それはちょっと公平だ。 右？ あなたはこれらのファンの男の子の一つ以上なら 本当にアップル製品が好きな女の子 あなたが午前3:00に目が覚めた いくつかの店で並ぶ 非常に最新のiPhoneを取得するには、 このようにキューに入れられた可能性があります。 今、キューは非常に意図的に名前が付けられています。 ありますので、それはラインだ それにはいくつかの公平性。 右？ あなたがしている場合、それは一種の吸い込まだろう アップルストアで最初にそこに着いた しかし、あなたは効果的に一番下です トレイその後のAppleの従業員のため 誰が最後の人をポップ 実際にラインに入った。 スタックやキュー、たとえそう 機能的に彼らはsame--の一種だ それはちょうどこのコレクションだ 資源のの 成長しshrink--するつもりはあります それは、この公平性の側面、 現実の世界では、少なくとも、 どこで行使操作 根本的に異なっている。 キューstack-- rather--持っていると言われて 二つの操作：n個のキューおよびdキュー。 またはあなたはそれらを呼び出すことができます 物事の任意の数。 しかし、あなたは単にキャプチャしたい 1が追加されているという考え 一つは、最終的に減算される。 さてボンネットの下に、両方のスタック キューがどのように実装することができますか？ 私たちは、のコードに行くことはありません それより高いレベルのため、 アイデアは、ソートのより明白である。 私は意味、人間は何をしますか？ 私はAppleの最初の人間だ場合 ストアこれはフロントドアで、 あなたが知っている、私はここに立ってするつもりです。 そして次の人の ここに立つつもり。 そして次の人の ここに立つつもり。 だから何のデータ構造 キューに向いている？ 聴衆：キュー。 DAVIDマラン：まあ、待ち行列。 かしこまりました。 他には？ 読者：リンクリスト。 DAVIDマラン：リンク あなたが実装できるリスト。 とリンクされたリストが原因その後いいです 対照的に、それは長い任意に成長することができます いくつかの固定された数を有することに ストア内の人々の。 しかし、おそらく固定数 場所の合法的である。 彼らは唯一の20のように持っている場合ので、 初日のiPhone、多分 彼らは唯一のサイズの配列を必要とする そのキューを表すために20、その 私たちが話し始めると、今だけと言うことです これらのより高いレベルの問題について、 あなたはそれを実装することができます 任意の数の方法。 そしておそらくちょうどに行くあります 空間と時間にトレードオフである あるいは単に自分のコードの複雑さ。 スタックはどう？ さて、スタックは、我々はあまりにも見てきました ちょうどこれらのトレイである可能性があります。 そして、あなたは、この配列を実装することができます。 しかし、いくつかの点では、アレイを使用する場合は、 何トレーに起こるだろう あなたが鎮圧しようとしている？ わかりました。 あなただけになるだろう それほど高く行くことができる。 そして、私は彼らがマザーにしていると思う 実際にその開口部に凹ん。 だから、確かに、それはほとんどだ メイザーが使用しているような 固定サイズの配列、 あなただけのことができるので、 その開口部で非常に多くのトレイに収まる 人々の膝の下にある下壁。 そしてその結果は次のようになります 配列であると言われ、 しかし、我々は確かにそれを実装することができ より一般的にはリンクされたリストを持つ。 さて、どのような別のデータ構造はどうですか？ 私はここに視覚的な他の1を引き上げてみましょう。 ここで、この約1どのようなもの？ なぜそれが持っていないために役に立つかもしれない トライのように空想何か、どの 我々はこれらの非常に広いのノードを持っていた見て、 それらの各々は、アレイ内にある？ しかし、我々はより多くの何かを何をすれば 単純に、古い学校の家系図のように、 ここに、そのノードのそれぞれ ほんの数を記憶している。 代わりに、名前または子孫の ちょうどこのような番号を記憶している。 我々が使用するだけでなく、専門用語 データ構造は、両方の試行で トライは、再び、である木、 ちょうど1そのノード配列です、 あなたがまだあるかもしれない 小学校から、使用 あなたは家族を作ったとき tree--葉や根 木との子の 親とその兄弟。 そして、私たちは木を実装する場合があり、 例えば、単にこのよう。 ツリーは、ノードとして場合、一 数はこれらの円、 それは持っているつもりはない つのポインタが、二つ。 そしてできるだけ早くあなたが追加する 第2のポインタ、あなた 実際に今ソートすることができます 二次元データの メモリ内の構造。 ずっと二次元様 配列は、次の操作を実行でき 二次元のようなものを持っている リンクされたリストが、もの それがパターンに従う どこに何サイクルがありません。 それは本当に1を持つツリーです 祖父母方法ここまで、その後 いくつかの両親と子供たちと 孫とひ孫。 等。 しかし、あまりにもこのことについては本当にきちんとしたものだ ちょうどコードのビットであなたをいじめるために、 からリコール再帰 しばらく前に、それによって あなたが自分自身を呼び出す関数を書く。 これは美しい機会です 何かを実装する 再帰のように、このためを考えてみましょう。 これが木です。 と私はどのようで少し肛門してきた 私は通りに整数を入れる。 それは特別になるようにそんなに 二分探索木をname--。 今、私たちは、バイナリを聞いた あなたを検索することができますが、 この事の名前から逆動作しますか？ どのように私のパターンとは何ですか このツリーに整数を挿入？ それは任意ではありません。 いくつかのパターンがあります。 うん。 読者：左側の小さいもの。 DAVIDマラン：うん。 小さいものは左側にある。 大きなものは右側にあります。 そのような真のステートメントがあること 親は、その左側の子よりも大きい その右の子よりも小さい。 そして一人でいることさえある 再帰的な言葉の定義 あなたはそれを適用することができますので、 すべてのノードに同じロジック それだけボトムス アウト、ベースケースあなたなら あなたのいずれかを打ったとき、意志 葉、いわば、 休暇は、さらに子を持たないところ。 今、どのように数44を見つけるかもしれない？ あなたはHM、ルートから始まると言うでしょう。 55は44ではないだから私は行きたくない 右または、私は左に行きたいですか？ さて、明らかにあなたが左に行きたい。 そしてそれはちょうど携帯電話のようなものだ バイナリ検索で書籍の例 より一般的。 しかし、我々はそれを実装している 今もう少し動的に 配列ができる場合がありますより。 そして実際に、あなたが見てみたい場合は、 コー​​ドで、一見してください。 これは、ラインの全体の束のように見えます。 しかし、それは美しく簡単です。 あなたは、関数を実装する場合 その目的は生活の中で呼ば検索 値を検索することです のようなnは、整数、 あなたが1 pointer--で渡されている 根のノードへのポインタ、 むしろ、そこからそのツリーの あなたが他のすべてにアクセスすることができ、 どのように素直に気付く あなたはロジックを実装することができます。 木がnullの場合、 明らかにそれはありません。 ちょうどfalseを返してみましょう。 右？ あなたはそれに何も渡していない場合、 そこには何もありません。 そうでなければ、nがより小さい場合 今n個の矢印N--ツリー矢印、 我々は、スーパーを導入しましたリコール 簡潔に先日、 それはちょうど、デリファレンスを意味し、 ポインタとnと呼ばれるフィールドを見てください。 だから、そこに行くと意味 Nと呼ばれるフィールドを見てください。 nのであれば、あなたが与えられている値は、小さい 木々の整数の値よりも、 どこに行きたいですか？ 左へ。 だから、再帰を気づく。 私は真実ではないreturning--よ。 偽ません。 私はどんな答えを返すよ 渡し、呼び出しから自分自身にある 冗長で再びnは、 今は少し異なる何ですか？ どうすれば問題を小さくするのですか？ 私は2番目として渡している 引数ではなく、ツリーのルート、 しかし、この場合は左の子。 だから私は左の子に渡している。 一方、nがより大きい場合 私は現在見ているノード、 私は右側を検索します。 そうでなければ、木は、nullでない場合と 要素は左にはない場合 それは、右にはない ケース素晴らしく何ですか？ 私たちは実際にノードを見つけた 質問、および私たちはtrueを返します。 だから我々は単に表面に傷だ 現在、これらのデータ構造の一部。 問題は5を設定では、よ なおさらこれらを探る、 そして、あなたのデザインが与えられます このことについて移動する方法の選択。 私が上で結論付けたいのですがどのような わずか30秒ティーザーです 来週以降を待って何の。 我々はありがたいbegin--として、あなたはかもしれない ゆっくりと私たちの移行をthink-- Cと下の世界から レベルの実装の詳細、 我々は取ることができている世界へ 他の誰かが最終的に持っていることを付与された これらのデータを実装 私たちのための構造、 そして我々は理解することから始めましょう 実装の現実世界の手段 ウェブベースのプログラムと より一般的にウェブサイト そしてまた、非常にセキュリティ 我々は唯一だ含意 の表面を傷つけるし始めて。 ここで私たちを待って何です 来る日。 [ビデオ再生] -Heは、メッセージに付属している、 すべての彼の独自のプロトコルを持つ。 彼は残酷の世界に来た ファイアウォール、思いやりルータ、 そして危険、死よりもはるかに悪い。 彼は速いです。 彼は強いです。 彼は、TCP / IPのだ、と彼はあなたのアドレスを持っている。 「ネットの戦士たち。」 [ENDビデオ再生] DAVIDマラン：来週来る。 私たちは、あなたが表示されます。 [ビデオ再生] -and今、「ディープ思考」 Davenファーナムによる。 -Davidはいつも始まる 、と講演「よし。」 なぜ、 "ここソリューションです 「今週の問題セットに または「私たちは、Aのすべてを与えている？」 [笑い] [ENDビデオ再生]