SPEAKER 1：すべてが正しいので、我々は戻ってきた。 CS50へようこそ。 これは、週7の終わりです。 だから、最後の時間を思い出す、私たちは開始 もう少し洗練された見 データ構造。 今までなので、すべての私たちは本当にいた 私達の処分で、この配列であった。 しかし、我々は配列を破棄しないように前に 確かにすべてのことを面白い、、それ 実際にいくつかのは何か、である この単純なデータのプラス これまでの構造？ それが得意とは何ですか？ これまでのところ、我々は見てきたように？ あなたは何を得たのですか？ 何もない。 学生：[聞こえない]。 SPEAKER 1：あれは、何ですか。 学生：[聞こえない]。 SPEAKER 1：固定サイズ。 [OK]を、なぜ固定サイズはしかし良いです？ 学生：[聞こえない]。 SPEAKER 1：OK、そう、それは中に効率的です あなたが割り当てることができるという意味 スペースの一定量、うまくいけば 正確には同じくらいです。 あなたが望むようなスペース。 だから絶対にプラスになる可能性があります。 アレイの別のアップ側は何ですか？ うん？ 学生：[聞こえない]。 SPEAKER 1：すべて - ごめん？ 学生：[聞こえない]。 SPEAKER 1：メモリ内のすべてのボックス 又は互いに隣接。 そして、それは便利です - なぜですか？ それはかなり本当だ。 しかし、どのように我々はその真実性を利用することができますか？ 学生：[聞こえない]。 SPEAKER 1：その通り、私たちはトラックを保つことができる すべてが知っているだけである すなわち一つのアドレスのアドレス メモリのチャンクの最初のバイト。 または文字列の場合には、 最初のアドレス その文字列のchar。 そこから、我々は見つけることができます 文字列の終わり。 私たちは、二番目の要素、見つけることができます 第三元素などが挙げられる。 そして、その記述のように派手な方法 機能では、配列は私たちを与えるということです ランダムアクセス。 ただ、角括弧を使用することにより 表記と番号、あなたはにジャンプすることができます 配列内の特定の要素 一定時間、ビッグOで いわば一つの。 しかし、いくつかの欠点がありまして。 配列は非常に簡単に何をしませんか？ それは何が得意ではないのですか？ 学生：[聞こえない]。 SPEAKER 1：あれは、何ですか。 学生：[聞こえない]。 SPEAKER：1サイズで展開。 配列の欠点があるので、 ものの正確に反対 五分五分です。 だから、欠点の1つは それは固定サイズだ。 だから、あなたは本当にそれを成長することはできません。 次の要素をbiggerチャンク割り当て直すことができ メモリ、および、古い要素を移動 新しい配列に変換します。 のためのそして自由に古い配列、 malloc関数または同様のを使用してインスタンス、 reallocを呼び出した関数、その 再割り当てメモリ。 reallocのは、余談として、あなたを与えるしよう アレイの横のメモリー あなたはすでに持っていること。 しかし、それは物事を動かすかもしれない 完全に周り。 しかし、要するに、それは右、高価なのですか？ なぜならあなたは、メモリの塊を持っている場合 このサイズが、あなたは本当にいずれかをしたい このサイズの、あなたが保存したい あなたが持っているオリジナルの要素、 ほぼ線形時間コピー処理 から起こる必要があること 新たに古い配列。 そして現実はオペレーティングシステムを求めている 何度も何度も、システムと 再びメモリの大きな塊を開始するために 同様にあなたにいくつかの時間を要します。 だから、祝福と呪いで両方だ 変装、これらの配列その事実 固定サイズである。 しかし、我々は、代わりに何かをご紹介している場合 このように、我々はリンクと呼ばれる リストは、我々はいくつかの五分五分を取得し、 同様にここではいくつかの欠点。 リンクされたリストは、単にデータですので、 構造体は、この中のCの構造体で構成されて 構造体、リコールは、単にある場合、 1のコンテナ以上の特定 変数の型。 この場合には、どのようなデータ型を行う 構造体の内部にそのように見える 最後の時間は、我々は、ノードと呼ばれる？ これらの各四角形は、ノードです。 小さい長方形の各 その中には、データ型である。 私たちは何種類言った 彼らは月曜日でしたか？ うん？ 学生：[聞こえない]。 SPEAKER：1変数とポインタ、または より具体的には、nのint型、、 そして下部にポインタ。 それらの両方がで、32ビットであることが起こる このCS50のようなコンピュータ上に少なくとも アプライアンス、彼らがしているので、 サイズが均等に描かれた。 だから、ポインタを使用している 明らかにするためでも？ 配列があったときに、なぜ今、この矢印を追加 とてもきれいでシンプルな？ ポインタは何をやっている 私たちこれらの各ノードで？ 学生：[聞こえない]。 SPEAKER 1：その通り。 それはどこに言っている 次のいずれかです。 だから私は、ソートののアナロジーを使う 一種のためにスレッドを使用して 一緒にこれらのノードを通します。 そして、それは我々がやっていることがまさにそれだ これらのそれぞれのためのポインタ メモリの塊があってもなくてもよいか 連続して、背中合わせにバックアップする RAMの内側、なぜならたび 十分に私を与える、と言って、mallocを呼び出す 新しいノードのバイト、それかもしれない ここにあるか、それがここにあるかもしれない。 それはここにあるかもしれない。 それはここにあるかもしれない。 あなただけ知らない。 しかしのアドレスにポインタを使用 これらのノードには、ステッチが、それらをすることができ 一緒に視覚的に見えるように これらの事がある場合でも、リストのような すべてのあなたの1または全体に広がる あなたの二つ以上のRAMをあなたの4ギガバイト 自分のコンピュータの内側。 の、その後、欠点は、そう リンクリストは何ですか？ 我々はしている価格は何ですか どうやら払って？ 学生：[聞こえない]。 SPEAKER 1：もっとスペース、右？ 我々は、この場合には、量が倍増した スペースを我々は行ってきたので、 それぞれのノードごとに、32ビットから int型なので、今では64ビットで、私たちがする必要があるため だけでなく、ポインタの周りを保つ。 あなたの構造場合は、より多くの効率を得る このシンプルなものよりも大きいです。 実際には内部の学生を持っている場合 の文字列のカップルとなっている 名前と家、多分ID番号、 完全にかもしれないいくつかの他のフィールド。 ですから、十分な大きさの構造体を持っている場合、 多分ポインタのコストは しないような大したこと。 これは、その中にコーナーケースのビットです 我々はこのような単純なプリミティブを格納している リンクリストの内側。 しかし、ポイントは同じです。 あなたは間違いなく多くを費やしている メモリが、あなたは取得している 柔軟性。 今私は、要素を追加したい場合なので このリストの先頭に、 私は、新しいノードを割り当てる必要があります。 そして私はちょうどそれらを更新する必要が ただ移動することで何とか矢印 周りにいくつかのポインタ。 私に何かを挿入したい場合は リストの途中、私はする必要はありません 我々が行ったように脇に誰をプッシュ 私たちのボランティアと週間の過去誰 配列を表す。 私はちょうど新しいノードを割り当てることができますし、 その後だけに矢印を指す 異なる方向ではないので 実際に残ってする必要があります 私が描いたようなメモリは真行 ここで画面上のそれ。 そして最後に、挿入したい場合 リストの最後に何か、それはだ さらに簡単。 これは、任意の表記法の一種である しかし34のポインタは、推測を取る。 最もそのポインタの値とは何ですか 昔のようなのありそうな描かソート そこに学校のアンテナ？ 学生：[聞こえない]。 SPEAKER 1：それはおそらくヌルです。 そして、確かにそれはある1著者の ヌルの表現。 なぜならあなたは絶対に、それはヌルです 知っておく必要がどこにリンクされているの終わり リストでは、次を維持しないように、である これらの矢印に従い、以下 いくつかのゴミ値に。 だからヌルはありませんことを意味しません 番号34の右側に複数のノード、 このような場合である。 だから我々は我々が実装できることを提案 コー​​ド内でこのノード。 そして我々はこの種を見てきました 構文の前に。 typedefのはただのための新しいタイプを定義 私たちは、のように私たちに同義語を与え 文字列は、char *のためだった。 この場合、それは私達を与えるために起こっている 短縮表記となるよう構造ノード だけではなく、のように書くことができる。 ロットクリーナーであるノード。 それははるかに少ない冗長です。 ノードの内部が明らかにintで と呼ばれるnと、次に構造体ノード* これは、私たちが望んで正確に何を意味する を意味する矢印、別の体へのポインタ まったく同じデータタイプのノード。 と私は、我々が実装できることを提案 このような検索機能、で 一見は思えるかもしれない 少し複雑。 しかし、それは文脈で見てみましょう。 私はここでアプライアンスにフェールオーバ行こう。 私はと呼ばれるファイルを開くみよう リストゼロドットH。 そして、それは唯一の定義を我々が含まれています ただこのデータの瞬間前に見ました タイプは、ノードと呼ばれる。 だから我々は、そのドットhファイルに入れました。 そして余談ですが、これでもかのよう あなたが見たい程度だというプログラムです すべてではない、複雑な、それは確かだ にプログラムを書き込む大会 引っ張って、データ型のようなものを置く 時には、あなたの内部の定数 ヘッダーファイルとは限らないで 確かにあなたのCファイル、ときに プログラムは、大きく、大きくなるので、 の両方を検索する場所をあなたは知っている いくつかのケースでドキュメント、または このような基本的な、ために いくつかの型の定義。 私は今、リストゼロドットを開く場合 Cは、いくつかのことを気づく。 これは、いくつかのヘッダファイルは、ほとんどが含まれています そのうち我々は前に見てきました。 これは、独自のヘッダファイルを含む。 そして余談として、その理由は、二重だ ここで引用符として角度に反対 ライン上の括弧その 私はそこ強調してきた？ 学生：[聞こえない]。 SPEAKER 1：うんので、ローカルファイルです。 もしそうなら、それはここにあなた自身のローカルファイルだ 例えば、15行目で、使用 二重引用符代わりに 山括弧の。 さて、これは面白いの一種である。 私はグローバルに宣言したことに注意してください 18行目で、このプログラムの変数 最初に呼び出され、このことアイデアがある 最初へのポインタになるだろう 私のリンクリスト内のノード、そして私がしました 私がきたので、それはnullに初期化 任意の実際の割り当てられていない ただまだノード。 だから、これは何を我々は、画像で表し、 画像に一瞬前に見たように そのはるか上のポインタ 左側。 だから今は、そのポインタ 矢印を持っていない。 それだけではなくnullになります。 しかし、それはどうなるかを表している 最初に実際のアドレス このリスト内のノード。 だから私は、それがグローバルで実装しました あなたはわかりますように、なぜなら、すべてこの プログラムでは、生活の中で実装されません 私のためのリンクリスト。 今私はここにいくつかのプロトタイプを持っている。 私のような機能を実装することを決定 欠失、挿入、検索、および トラバーサル - 最後はただ歩いて渡ること リスト、その要素をプリントアウト。 そして今、ここに私のメインルーチンです。 そして、我々にあまりにも多くの時間を費やすことはありません これがうまくいけば、一種であるので、これらの 今では古い帽子。 私は、次の操作を実行するつもりです ユーザーが協力しながら。 1だから、私は印刷するつもりです このメニューから。 そして、私はそれのようにフォーマットしました きれいに私ができるように。 意味1で、ユーザーがタイプ、その場合 彼らは何かを削除したい。 二つに、ユーザがタイプした場合、そのことを意味し 彼らは何かを挿入したい。 など。 私はその後、要求するつもり 次にコマンドの。 そして私は場合、getIntを使用するつもりです。 だから、これは本当に簡単メニュー操作です あなただけ入力する必要がインタフェース 1の数字へのマッピング これらのコマンドの。 そして今、私は良いクリーンなスイッチがあり に切り替えることが起こっている声明 ユーザーが入力したログインどんな それらが1つを入力した場合と、私はよ 削除呼び出すと壊れる。 彼らは2を入力した場合、私はよ 挿入呼び出すと壊れる。 そして今、私はそれぞれの置かれているに気づく これらの同じライン上の。 これは単なる文体の決定です。 一般的に我々は何かを見てきました このように。 しかし、私はただ、率直に言って、私のプログラムを決定した 読みやすく見えたので、 それは唯一の4例であった ちょうどこのようにそれを示します。 スタイルの完全に合法的な使用。 そして、私はこれがそう長くするつもりです ユーザがゼロに入力されておらず、そのI それらが終了したいことを意味しますことを決めた。 だから今、私は何に気づく ここで何をするつもり。 私は明らかにリストを解放するつもりです。 一瞬でその上で、より多くの。 最初にこのプログラムを実行してみましょう。 だから私は大きなターミナルを作ろう 窓、ドットスラッシュリスト0。 私が先に行くとによって挿入するつもりです タイピング2、今では50のような数、および あなたは、リストは今50ですがわかります。 そして、私のテキストは少しだけ上にスクロール。 だから今はリストに含まれて気づく 番号50。 2を取ることによって、別の挿入を行うましょう。 1のように番号を入力してみましょう。 リストは現在50に続く一つです。 だからこれは単なるテキスト表現です リストの。 などもう一つの番号を挿入てみましょう うまくいけば、ある番号42、 ので、途中で終わるつもり 特定の種類の中で、このプログラムはそれ それを挿入してなどの要素。 だから、そこに我々はそれを持っている。 できたスーパー簡単なプログラム 絶対に配列を使用しましたが、私た リンクリストを使用することが起こる ちょうどので、私は動的にすることができます 成長し、それを縮小。 私場合それでは、検索のためのを見てみましょう コマンド3を実行し、私が検索したい 数43、言う、のために。 そして、何も明らかに認められなかった、 私は戻っても応答を得ないので。 それでは、再びこれを行うことができます。 検索。 レッツ50の検索、またはむしろ検索 42のために、それは素敵なを持っている 少し微妙な意味。 そして、私はそこに人生の意味を発見した。 あなたがわからない場合は数42、 参照は、それをGoogleに。 わかりました。 それでは、私のためにこのプログラムを行っている？ それはちょうど私は、このように挿入することができている 遠くと要素を検索します。 に、その後、早送りしてみましょう 私たちは、ちらっと見たその関数 ティーザーとして月曜日に。 この関数は、だから、私は主張し、検索のため 最初で、リスト内の要素 1、ユーザーにプロンプ​​トを表示してから、呼び出し 実際のint型を取得する場合、getInt あなたが検索したい。 次に、このに気づく。 私は一時的な変数を作成するつもりです ライン188でポインタと呼ばれる - PTR - それに何と言ったかもしれない。 そしてそれは、ノードへのポインタだ 私はそこに、ノード*と言ったので。 そして、私はそれが等しくなるように初期化しています 最初に私は効果的に持っているというのが私の 非常に指、いわば、 リストの最初の要素。 ここに私の右手はPTR私があるのであれば 同じものを指して、最初 を指している。 だから今バックコードで、 何が次に起こる - 反復するとき、これは一般的なパラダイムである のような構造上の リンクリスト。 私はしばらくの間、次の操作を行うつもりだ ポインタが一方だからnullに等しくない 私の指には、いくつかのヌルを指していません 値は、矢印ポインタnがnと等しい場合。 我々はnが何であることを最初に気づくでしょう 当たりGetIntsで入力したユーザーは、ここで呼び出す。 とポインタ矢印nが何を意味？ さて、我々はここで絵に戻った場合、 私は指を指している場合 9、含むその最初のノード 矢印は、基本的にそれに行くことを意味し ノードと、位置nにおける値をつかむ この場合には、n個のデータ·フィールドと呼ばれる。 余談ですが - と我々はこのカップルを見た 週間前に誰かが尋ねられたとき - この構文は新しいですが、それはしません 私たちに力を与えることを我々 既に持っていませんでした。 使用するのと同じこのフレーズは何だったの ドット表記とスターカップル 週間前、我々は戻って皮をむいたとき 少し早まってこの層？ 学生：[聞こえない]。 SPEAKER 1：その通り、それがスターだった、と それはと、スタードットNだった ルックスここで括弧、、 率直に言って、私は多くのことを考える 読みより不可解。 しかし、星のポインター、いつものように、 手段がそこに行く。 そして、一度はそこにいる、どのようなデータ フィールドには、アクセスしたいのですか？ さてあなたはアクセスするためにドット表記法を使用し 構造体のデータ·フィールド、およびI 特にnが欲しい。 率直に言って、私はこれを主張するだろう 読むためだけに困難です。 それはどこで覚えておくことが難しくなっている 括弧は、行くのですか 星とすべてのこと。 だから、世界はいくつかの構文を採用した 砂糖、いわば。 言うだけのセクシーな方法、 これは等価であり、 おそらくもっと直感的。 ポインタが実際にポインタである場合、 矢印表記手段がそこに行くと見つける この場合のフィールドは、nと呼ばれる。 私はそれを見つけるのであれば、私は何をすべきかに気づく。 私は単に、私がパーセント私を発見し、プリントアウト そのint型の値をプラグイン。 私は種類にただ1秒間スリープ呼び出す に画面上で一時停止の事 ユーザに吸収する第二を与える 何が起こったばかり。 そして私は破る。 そうでなければ、私は何をしますか？ 私は平等へのポインタを更新 次のポインタ矢印。 だから明確にすること、これは行く意味 そこに、私の古い学校の表記を使用して。 だから、これは単に何に行くことを意味します あなたは非常には、そのを指している 最初のケースは、私が指していますです その中に9と構造体。 だから私はそこに行ってきた。 そして、ドット表記を意味し、 次の時の値を取得します。 しかし価値は、それが描かれているにもかかわらず 狭いように、ただの数字です。 それは数値アドレスです。 どうか、この1行のコードでは、そう このように書かれ、多くの不可解な 方法、またはこのような、もう少し 直感的な方法は、ちょうど私の手を動かすことを意味 最初のノードから次のいずれかに、 その後、次のいずれか、その後 など1次、と。 だから私たちは、他にこだわることはありません 挿入、削除の実装 とトラバーサル、最初の2つの そのかなり関与している。 そして、私はそれを得るために非常に簡単だと思う 口頭でそれをやったときに失った。 しかし、私たちはここで行うことができますです 方法を決定しようとする 視覚的にこれを行うことが最善。 私が提案するので、もし我々 これに要素を挿入したい 既存のリスト、その 五行を持っています - 9、17、22、26、および33 - 私は、これを実装しようとしていた場合 コー​​ドは、私が移動する方法を検討する必要があります これを行うことについて。 と私は、赤ちゃんの手順を取って提案する それによって、このケースでは、私は意味が何であるか その我々の可能なシナリオ 一般的に発生する可能性がある？ リンクされたの挿入を実装する場合 リストは、これは単なるであることを起こる サイズ5の具体例を示す。 さてあなたは番号を挿入したい場合は、 ナンバーワンと言うように、と どこに、ソートされた順序を維持 明らかに1がする必要がある数はありません この特定の例で行く？ 冒頭で好き。 しかし興味深い何それはそこにある この中に1を挿入したい場合 リスト、どのような特別なポインタのニーズ 明らかに更新される？ 最初。 だから私は、これが最初のケースである、と主張するだろう 我々は、検討する必要がありますことを で挿入を含むシナリオ リストの先頭。 のも同様に簡単または多分オフ摘み取るう 容易な場合、相対的に言って。 私が挿入したいとしましょう ソートされた順序で番号35。 それは明らかにあそこ属する。 だから、明らかにポインタがに何が起こっているか そのシナリオで更新される必要がありますか？ 34のポインタがnullではないとなって しかし、構造体のアドレス 番号35を含んでいる。 だからケース2です。 だからもう、私は、量子化のようなものだ いくら私がここでしなければならない仕事。 そして最後に、明らかな中間ケースである 確かに、途中で、私がしたい場合は 行くと言う23、のようなものを挿入する 23と26の間に、しかし、 今、物事はもう少し得る 何のために関与 ポインタを変更する必要が？ 22は明らかに変更する必要があるので、 彼はもう26を指すことはできませんので。 彼は新しいノードを指す必要があること 私が呼び出して割り当てる必要があります malloc関数または一部同等。 しかし、私はまた、新しいノード、23が必要 この場合には、そのポインタを持っている 誰を指す？ 26。 とがあるように起こっている ここでは操作の順序。 私は愚かにも、これを行う場合があるため、私 インスタンスの開始時に始動用 リスト、および私の目標は23を挿入することです。 そして、私は確認して、それが属していません ここでは、9の近く？ いいえ。 それは17の隣に、ここに属していますか？ いいえ。 それは22の隣にここに属していますか？ はい。 今私はここに愚かだ、とされていない場合 私は、これを可能性を通して考える 23のための私の新しいノードを割り当てる。 私はからポインタを更新するかもしれません ノードは、ポインティング、22と呼ばれる 新しいノードでのそれ。 そして私は更新する何がありますか 新しいノードのポインタでなければするには？ 学生：[聞こえない]。 SPEAKER 1：その通り。 26でポインティング。 しかし、私はすでに更新されなかった場合くそ この男を指すように22のポインタ、および 今私は孤児、残りを持っている リストでは、いわば。 ここでの操作だから順 重要になるだろう。 これを行うには私は、盗むことができる 、6人のボランティアと言う。 そして、我々はこれを行うことができないかどうかを確認してみましょう 視覚の代わりにコードが賢明。 そして、私たちはいくつかの素敵なストレスを持っている 今日はあなたのためのボール。 [OK]を、どのように約1、2、 バック - そこの端に。 3つ、4つ、あなたの両方 最後にみんな。 と5、6。 かしこまりました。 五六。 すべての権利と私たちは来る 次回君たちへ。 すべての権利は​​、アップに来る。 すべての権利は​​、ここで最初にしているので、 あなたは、ぎこちなく1になりたい ここでGoogleのグラスで？ すべての権利なので、[OK]を、ガラス、 ビデオを録画。 [OK]を、あなたが行ってもいいです。 すべての権利なので、皆さんは上に来ることができる場合 ここで、私が事前に用意しています いくつかの数字。 すべての権利、こっちに来る。 そして、なぜあなたは少しに行かない さらにそのように。 そして、あなたの名前は何だ、見てみましょう Googleのガラスと？ 学生：ベン。 SPEAKER 1：ベン？ OK、ベン、あなたは文字通り、初めてとなる。 だから我々はあなたを送信するつもりだ ステージの最後に。 すべての権利、そしてあなたの名前は？ 学生：ジェイソン。 SPEAKER 1：ジェイソン、OKはよ ナンバーナインなる。 あなたはベンそのようにフォローしたいのであれば。 学生：ジル。 SPEAKER 1：ジルは、ことになるだろう 私はこれ以上行われたい場合17、 インテリジェントに、私が持っているでしょう もう一方の端に開始。 あなたは、その道を行く。 22。 あなたですか？ 学生：メアリー。 SPEAKER 1：メアリーは、22になります。 あなたのお名前は？ 学生：クリス。 SPEAKER 1：クリス、あなたは26になります。 そして最後に。 学生：ダイアナ。 SPEAKER 1：ダイアナ、あなたは34になります。 だから、こっちに来る。 すべての権利なので、並べ替え完成 すでにオーダー。 とのは、先に行くと、これをやらせる - ので、私たちは本当にできること ベンは、見ているだけのようなものだ そこにどこに出て。 OK、それでは、先に行くと、これを描いてみましょう 私がいた同じように、腕を使って、正確に、 何が起こっている。 だから先に行くと自分自身を与える 足や自分の間に2つ。 そして、もう一つの手にと先に行くとポイント 誰でもあなたを指してされるべきである これに基づいて。 あなたがnullなら、ただ指す まっすぐ床に。 OK、とても良い。 だから今我々は、リンクされたリストを持っている、と私を聞かせて 私はの役割を果たすだろうことを提案 PTRので、私は気にしないでしょう これを持ち運び。 そして - 誰か愚か大会 - あなたが欲しい、この何を呼び出すことができます - 前身ポインタ、PREDポインタ - それはちょうど我々が与えたニックネームだ 私の左手に、当社のサンプルコード。 維持されようとしている一方、 で誰が誰であるかを追跡 次のシナリオ。 だから最初に、私はオフ摘み取るしたい、とします 挿入のその最初の例は、言う 20、リストに。 だから私はに誰かを必要とするつもりだ 私たちのために20番を体現。 だから私は、malloc関数の誰かに必要 聴衆から。 までさあ。 あなたの名前は？ 学生：ブライアン。 SPEAKER 1：ブライアン、大丈夫なので、 20を含むノードでなければならない。 すべての権利、こっちに来る。 そして明らかに、どこ ブライアンは属していない？ だから、の途中で - 実際に、 ちょっと待ってください。 私達は順序のこれをやっている。 私たちは、多くの困難にこれを作っている それは最初に必要以上。 [OK]を、我々は自由ブライアンするつもりだ 5として、またreallocのブライアン。 [OK]を、ので、今私たちは、挿入したい 5としてブライアン。 だから隣にこっちに来て ちょっとベン。 そして、あなたはおそらく言うことができます この物語がどこへ行くのか。 しかしみましょうについて慎重に検討 操作の順序。 そしてそれはまさにこの視覚的な 並べるために起こっていること そのサンプルコード付き。 だからここに私は、PTRは最初指しています ベン、それ自体ではなく、どのような時ではない 彼は、含まれているその値は、この場合の です - あなたの名前は再び何ですか？ 学生：ジェイソン。 SPEAKER 1：ジェイソン、ベンと私の両方があるので、 この瞬間にジェイソンを指す。 だから今、私は決定する必要があり、 ブライアンはどこに属しているのでしょうか？ 唯一だから私はへのアクセス権を持って 今は彼のn個のデータ項目である。 だから私は、チェックすることですつもりだ ジェイソン未満ブライアン？ 答えは本当です。 だから今が起こる必要があるか、 正しい順序で？ 私はどのように多くのポインタを更新する必要があります この物語の中で合計で？ 私の手はまだで指している場所 ジェイソン、そしてあなたの手 - あなたがしたい場合 私は、一種の、ようにあなたの手を置く 、疑問符を知らない。 OK、いい。 大丈夫、あなたが持っているので、 いくつかの候補者。 ベンまたはIまたはブライアンまたはジェイソンどちら または皆、どの ポインタは、変更する必要がありますか？ どのように合計で多くの？ [OK]を、ので、2つの。 私のポインターは本当にもう問題ではありません 私はただ一時的だから。 だから、おそらく、これらの二人だ ベンとブライアンの両方。 だから我々は更新することを私は提案してみましょう ベンは、以来、彼が最初だ。 このリストの最初の要素 今ブライアンになるだろう。 ブライアンでとてもベンポイント。 [OK]を、今何？ 誰が誰に指摘される？ 学生：[聞こえない]。 SPEAKER 1：OKブライアンが持っているので、 ジェイソンを指すように。 しかし、私はそのポインタのトラックを失っている？ ジェイソンがどこにあるか私は知っていますか？ 学生：[聞こえない]。 SPEAKER 1：私は以来、私は、やる 一時的なポインタです。 そしておそらく、私は変わっていない 新しいノードを指すように。 だから我々は、単にブライアン·ポイントを持つことができます 誰に私を指しています。 そして我々は完了です。 だからケース1、で挿入 リストの先頭。 2つの主要なステップがありました。 その後一、我々はベンを更新する必要があり、 我々はまた、ブライアンを更新する必要があります。 そして私は気にする必要はありません の残りの部分を通してtraipsing 我々はすでに彼を発見したので、リスト、 彼はに属しているため場所、 最初の要素の左。 すべての権利なので、かなり簡単。 我々は、ほとんどしているように実際には、感じている これはあまりにも複雑になっています。 だから今終わりをオフに摘むてみましょう リストの、どこを参照してください 複雑さが始まります。 聴衆からのだから今なら、私はalloc命令。 誰もが55をプレイしたいですか？ すべての権利、私が最初にあなたの手を見た。 までさあ。 うん。 あなたの名前は？ 学生：[聞こえない]。 SPEAKER 1：Habata。 [OK]を、アップで来る。 あなたは、番号55になります。 だから、もちろん、所属する リストの最後。 それでは、私と一緒にシミュレーションを再生してみましょう ちょっとPTRである。 だから私は最初を指すつもり どんなベンを指している。 我々は今、ブライアンで指している両方。 だから55が5個未満ではありません。 だから私はで自分自身を更新するつもりです 誰が、ブライアンの次のポインタを指す 今は、もちろんジェイソンである。 55はそう、9未満でない 私はPTRを更新するつもりです。 私はPTRを更新するつもりです。 私はPTRを更新するつもりです 私はPTRを更新するつもり。 そして、私はするつもりです - うーん、何 あなたの名前を再び？ 学生：ダイアナ。 SPEAKER：1ダイアナが指している、もちろん、 彼女の左手でヌルで。 だからここで実際にHabataん 明らかに属しているのか？ ここで、左に。 だから私はここで彼女を置く方法を知っていますか 私がめちゃくちゃしたと思う。 PTR芸術とは何かがあるため 時間のこの瞬間？ ヌル。 そうであっても、視覚的に、我々はできる 明らかに、これらのすべてを見る ここでステージ上のみんな。 私は、以前の記録を維持していませんでした リスト内の人。 私は、指摘指を持っていない この場合、ノード番号34。 それでは、実際にこれを最初からやり直すことができます。 だから今私は実際に必要なのですか 第2のローカル変数。 そして、これはあなたが表示されますものです として私は行く実際のサンプルCコード、、 私はポイントに私の右手を更新するとき ジェイソンは、それによって、私が、背後にブライアンを離れる 良い私の左手への使用を開始 私がいたところ、私が行くようになるように、更新 このリストを - もっとぎこちなく私が意図したより 今ここに視覚的に - 私を取得するつもりだ リストの最後。 この手はかなりある、まだnullです 示すこと以外、役に立たない 私は、リストの最後に明らかによ しかし、今では少なくとも私はこれを持っている 前身ポインタはそう、ここで指す 今何手渡し、どのポインタが必要 更新する？ 誰の手にあなたが選択してください 最初に再構成する？ 学生：[聞こえない]。 SPEAKER 1：OK、ダイアナのよう。 どこで指すようにしたいですか でダイアナの左ポインタ？ 55で、おそらく、そのよう 我々はそこに挿入した。 どこで55ポインタが行くべき？ ダウンして、ヌルを表す。 そして、私の手は、この時点では、しないでください 彼らはただだったので問題では 一時変数。 だから今我々は完了です。 だから、そこに追加の複雑さ - と それは、実装することは難しいことではありません しかし、我々は作るために二次的な変数が必要 前に私は私の右に移動することを確認 一方、私は左の値を更新 手、PREDこの場合はポインタなので、 私は末尾のポインタを持っていることを 私がいた場所を追跡する。 さて余談として、あなたがこれを考えている場合 それはのように経由して、これは感じている 続けなければならないことが少しうるさい この左手のトラック。 何が別の解決策は、だろう この問題に行ったことがある？ してデータを再設計するようになった場合 我々は話をしている構造 今スルー？ これだけの種類のは少しを感じた場合 、のように、二つのポインタを持っている迷惑 リストを通過する、誰か他の可能性 、理想的な世界では、維持している 私たちが必要とする情報？ うん？ 学生：[聞こえない]。 SPEAKER 1：その通り。 右のように興味深いのは、実際にあり アイデアの胚芽。 と以前のポインタのこのアイデア、 前の要素を指す。 私はちょうどそれを具現化したらどう リスト自体の内側？ そしてそれは視覚化するのは難しいことになるだろう このすべての用紙なし 床に落下。 しかし、これらの人は両方を使用したことを仮定し 彼らの手の前のを持っている それによって、ポインタ、および次のポインタ、 我々は二重に呼ぶことにします何を実装 リンクリスト。 つまり、私は巻き戻しを並べ替えることができるようになる はるかに容易に私なし、 プログラマ、維持すること 手動で追跡する - 本当に手動で - 私が以前にあった場所に リストに表示されます。 だから我々はそれを行うことはありません。 それだから我々は、それをシンプルに保つよ 価格で来ることを行って、二倍 ポインタのために多くのスペース、 2番目のいずれかをしたい場合。 しかし、それは確かに一般的です と呼ばれるデータ構造 二重リンクリスト。 ここで最後の例を実行し、置いてみましょう 彼らの不幸のうち、これらの人。 mallocの20だから。 そこ通路から上がってさあ。 大丈夫、あなたの名前は何ですか？ 学生：[聞こえない]。 SPEAKER 1：申し訳ありません？ 学生：[聞こえない]。 SPEAKER：1 Demeron？ OKまでに来る。 あなたが20でなければならない。 あなたは明らかにしようとしている 17と22の間に属しています。 だから私は私の教訓を学ぶことができます。 私はポインタを開始するつもりだ ブライアンを指す。 そして私は私の左手を持っているつもりです 私は移動するだけブライアンへのアップデート ジェイソン、チェックは9より20少ないのか？ いいえ。 17以上20未満でありますか？ いいえ。 22以上20未満でありますか？ はい。 それでは、ポインタまたは手が変更する必要があります 彼らは今指している場所？ だから我々は20を指して17を行うことができます。 だから大丈夫です。 どこに指すようにしたいですか 今あなたのポインタ？ 22時。 22がどこにあるか、我々は再び、感謝を知っている 私の一時的なポインタへ。 だから私たちはそこにOKです。 そうこのため一時記憶 私は誰もがどこにあるかを追跡し守ってきた。 そして今、あなたは、視覚的にどこに行くことができます あなたが所属し、今、私たちは、1、2、3、必要 4、5、6、7、8、9ストレスボール、 とのために拍手 これらの人は、我々はできれば。 うまく行って。 [拍手] SPEAKER 1：すべての権利。 そして、あなたは作品を保つかもしれない 記念品としての紙。 すべての権利なので、それは多くの私を信頼 容易にその中を歩くために それは実際のコードであるよりも、人間。 しかし、あなたは一瞬で見つけるのか 今、その同じです - ああ、ありがとうございます。 ありがとう - あなたはその同じデータを見つけることです 構造、リンクされたリストは、実際にすることができます より一層のビルディングブロックとして使用すること 洗練されたデータ構造。 そして、ここであまりにもテーマを実現することです 我々は絶対にそれ以上を導入しました 実装に複雑 このアルゴリズムである。 挿入、そして我々はそれを通り抜けた場合、 削除と検索は、少しです それよりも複雑 配列していました。 しかし、我々はいくつかのダイナミズムを得る。 我々は、適応データ構造を取得します。 しかし、再び、私たちはいくつかを持っていることの代償を払う 両方で追加の複雑さ、 それを実装する。 そして我々は、ランダムアクセスをあきらめている。 と正直に言うと、いくつかの素晴らしいではありません スライドをきれいに私はあなたを与えることができる なぜリンクされたリストであるここで言う 配列よりも優れています。 そして、その時点でそれを残す。 テーマがあっても、すぐ再発するので より多くのように今後数週間のうちに、ある 必ずしも存在しないということ 正解。 我々は独立した軸を持っている理由です 問題セットのデザインの。 これは非常に文脈依存になります このデータを使用するかどうか 構造やその一つであり、それを意志 言葉であなたに重要なものに依存 資源と複雑さ。 しかし、私は、その理想的なデータを提案してみましょう 構造、聖杯は、だろう 定数時間だ何か、 かかわらず、多くのものがどの程度の その中に、それは素晴らしいではない場合 データ構造は、中に答えを返す 時定数。 はい。 この言葉はあなたの巨大な辞書である。 またはNO、この言葉ではありません。 またはそこにそのような問題がある。 我々は、少なくともできない場合まあ見てみましょう それに向かって一歩を踏み出す。 私は新しいデータ構造を提案させている 、別のもののために使用することができます このケースではハッシュテーブルと呼ばれる。 そして、我々はかすめるに戻る実際にしている この場合には配列と、時 幾分任意、私はこれを描いた 一種の持つ配列としてハッシュテーブル 二次元配列 - あるいはむしろそれは、2つとしてここに描かれている 次元配列 - しかし、これはただです このような我々であれば、そのサイズ26の配列、 配列表、表ブラケットを呼び出す ゼロが一番上に矩形です。 テーブルブラケット25は、長方形です 一番下にある。 そして、これは私がデータを描画する方法です 私が保管する構造 人の名前。 だから例えば、私は描くことはありません 私ならオーバーヘッドでここに全部、 私は今に行くよ、この配列を、持っていた ハッシュテーブルを呼び出し、これは再び 場所ゼロ。 これはここの場所です など1、と。 私はこのデータを使用することを主張する 議論のために構造、 人の名前を格納するために、アリスとボブ とチャーリーおよび他のそのような名前。 だから、始まりとして今、この考える 辞書、言う、の 言葉の多くが付いている。 彼らは名前のことが起こる ここに私たちの例では そして、これはには、おそらく、あまりにも密接です。 我々のように、スペルチェッカーを実装 問題のために6を設定することもできます。 だから我々は全体の大きさ26の配列を持っている場合 これは25日の場所になるように 一番下にある、と私はアリスであることを主張する の辞書の最初の単語 私はRAMに挿入する名前、 このデータ構造に、どこにいる あなたを伝える本能そのアリスの 名前は、この配列に行くべきでしょうか？ 我々は26のオプションがあります。 私たちは、彼女を入れたい場所は？ 我々は、ブラケットゼロで彼女にしたいよね？ アリスのために、のはそのゼロを呼び出してみましょう。 AとBは1になり、そしてCは2となる。 だから私たちは書くつもり ここでアリスの名前まで。 我々はその後、ボブ、彼のを挿入した場合 名前はここに行きます。 チャーリーはここに行きます。 などを通じてダウン このデータ構造。 これは素晴らしいデータ構造です。 なぜですか？ 井戸の実行時間は何ですか この中に人間の名前を挿入する 今データ構造？ このテーブルが実装されていることを考えると、 本当に、配列として。 まあそれは、一定の時間です。 それは1つの順序だ。 なぜですか？ さてどのように決定するか アリスは所属どこ？ あなたは、その彼女の名前の文字を見て？ 最初。 それが文字列である場合、あなたは、そこに着くことができます 単に文字列を見て ブラケットゼロ。 文字列のゼロ番目の文字がそう。 それは簡単です。 私たちは、暗号であることをしました 代入週間前。 そして一度はアリスのことを知っている 手紙は首都である、我々は引くことができます 65または資本自体、オフ それは私たちにゼロを与えます。 だから我々は今、アリスが属していることを知っている 位置ゼロに。 そして、このデータへのポインタを与えられる ある種の構造は、どのくらいない それは場所を見つけるために私を取る 配列内のゼロ？ ただ、一歩は、右のそれは一定の時間だ ランダムアクセスのために我々 提案は、配列の特徴であった。 だから要するに、考え出す何インデックス アリスの名前の中、ある、ある この場合は、あるか、みましょうだけで解決する ゼロに、ここで、Bは一つであり、Cであること 2、それを考え出す 時定数である。 私はちょうど、彼女の最初の文字を見ている ゼロがどこにあるかを考え出す 配列はまた、時定数である。 だから技術的にあることです 現在、2つのステップのように。 しかし、それはまだ定数です。 そこで我々は1のその大きなOを呼び出すので、き このテーブルにアリスを挿入 時定数。 しかし、もちろん、私はされています ここで素朴な、右？ どのクラスのアーロンがあったら？ それともアリシア？ または任意の他の名前で始まる A.どこに置くつもりです その人は、右？ 私が意味する、今3つしかありませ テーブルの上の人なので、多分私達 場所でアーロンを置くべき ゼロ1 2 3。 右、私はここに置くことができます。 しかし、その後、我々はにデイビッドを挿入しようとした場合 このリストは、ダビデが行くのでしょうか？ 今、私たちのシステムは破壊開始 ダウン、右？ 今、ダビデはここで終わりますので、 アーロンはここに実際にある場合。 持つことのそして今、この全体的なアイデア 私たちを与えるクリーンなデータ構造 一定時間の挿入はもはや 私がする必要があるので、時定数、 チェック、ああ、クソ、誰かがすでにだ アリスの場所で。 私は、この残りのデータを精査しましょう 置くためのスポットを探している構造、 アーロンの名前のような人。 そしてあまりにも開始されている 線形時間を取る。 また、あなたは今、検索したい場合 このデータ構造でアーロン、そしてあなた チェックして、アーロンの名前はここではありません。 理想的には、あなただけのアーロンのだと思います ていないデータ構造である。 しかし、あなたがのための部屋を作り始めなければ Dがあったはずアーロン またはE、あなた、最悪の場合、チェックする必要があり 全体のデータ構造で それは何かに委譲された場合 テーブルのサイズの線形。 大丈夫だから、私はこれを修正します。 ここでの問題は、私が持っていたということです この配列内の26の要素。 私はそれを変更しましょう​​。 おっと。 むしろの幸福そのように私はそれを変更しましょう 合計でサイズ26、ボトムに気付く インデックスは、nから1を引いた値に変更する予定です。 26は人間のための明らかに小さすぎると 名前、何千ものがあるので、 世界の名は、単に作ってみましょう 100または1,000または10,000。 ただより多くの領域を割り当ててみましょう。 まあ必ずしも低下しないこと 我々は、2つを持っていない確率 で始まる、と名前を持つ人々 だから、あなたが配置しようとするつもりだった まだ場所ゼロで名前。 彼らはまだ、衝突しようとしているどの 我々はまだ配置するソリューションを必要と意味 アリスとアロンとアリシアや他の 他の場所で始まる名前。 しかし、これはどの程度の問題でしょうか？ あなたその確率は何ですか データの衝突を持っている このような構造？ まあ、私を聞かせて - 私たちは戻ってくる ここにその質問へ。 そして、どのように我々は可能性があるを見て 最初にそれを解決する。 私はここでこの提案を引き上げてみましょう。 私たちはただ説明するアルゴリズムであり、 線形と呼ばれるヒューリスティック を挿入しようとした場合、それによってプロービング ここで、このデータで何か ハッシュテーブルと呼ばれる構造で、 と余地あなたは、そこにありません 真のデータ構造を調べる チェックし、これはありますか？ この利用可能な、この利用可能です？ これはありますか？ そして、それは最終的にあるときは、挿入 あなたが最初に意図した名前 他の場所でその位置で。 しかし、最悪の場合には、唯一のスポット データの一番下かもしれない 構造、配列の最後の最後。 だから線形最悪の場合、プロービング、 線形アルゴリズムどこに委譲 アーロンは、彼が最後に挿入されるように発生した場合 このデータ構造では、彼はかもしれ この第一の位置と衝突したが、 その後、一番最後に不運で終了。 だから、これは一定ではありません 時間私たちのために聖杯。 挿入する要素のこのアプローチに データ構造は、ハッシュと呼ばれる 表は、一定時間ではないようです 少なくとも、一般的なケースである。 それは線形なものに委譲することができます。 私たちは、衝突を解決するそれでは場合 多少異なる？ だからここでは、より洗練されただ まだ何へのアプローチ ハッシュテーブルと呼ばれる。 とハッシュによって、余談として、何 私は、そのインデックスであることを意味 私は以前に言及した。 できるハッシュ何かに 動詞として考える。 あなたハッシュアリスは名前だのであれば、 ハッシュ関数、いわば 数を返す必要があります。 彼女が属している場合で、この場合にはゼロである 彼女はに属していれば場所ゼロ、1つ 位置オン、などが挙げられる。 だから私のハッシュ関数はこれまでされている だけを見て超簡単、 誰かの名前の最初の文字。 しかし、ハッシュ関数は次のように取り 入力データのいくつかの作品、 文字列、int型、何でも。 そしてそれは、一般的に数値を出してくれる。 そして、その数はここで、そのデータ 要素は、データ構造に属し ハッシュテーブルとしてここで知られています。 だから直感的に、これは わずかに異なるコンテキスト。 これは、実際の例を参照している 関与誕生日、どこ できるだけ多くのがあるかもしれない 月の31日。 しかし、この人は何をすることを決定しました 衝突が発生した場合にですか？ コンテキストは、現在の衝突はないという 名前が、誕生日の衝突、 二人で同じ誕生日を持っている場合 例えば、10月2日。 学生：[聞こえない]。 SPEAKER 1：うん、そう、ここで我々は持っている リンクリストの活用。 だから、少し異なるように見える よりも我々はそれを以前に描きました。 しかし、我々は配列に持っているように見える 左側に。 それは、1つのインデックスません 特定の理由。 しかし、それはまだ配列です。 これは、ポインタの配列です。 これらの要素のそれぞれの、それぞれの これらの円またはスラッシュ - スラッシュ 表すヌル - これらの各 ポインタが明らかにを指している どのようなデータ構造？ リンクリスト。 だから今我々は能力を持っている 私たちのプログラムにハードコード テーブルのサイズ。 このケースでは、我々はそこことはない知っている 月に31日以上。 だから難しいです31のような値をコーディングする その文脈で妥当。 名前のコンテキストでは、ハードコーディング 26は無理ではありませんそれは人々の 名前だけで、例えば、で始まる Z.を通じて関与アルファベット 我々は、すべて、そのデータにそれらを詰め込むことができます 我々が得る限り、構造、 衝突、我々はここに名前を入れてはいけません、 我々は、代わりにこれらの細胞を考える としてではなく文字列を自分自身、しかし、 例えばへのポインタ、アリス。 そしてアリスは別のポインタを持つことができます で始まる別の名前に A.そして、ボブは実際にこっちに行く。 そして始まる別の名前があ​​る場合 Bで、彼はここにかけて終了します。 そしてそれぞれのこのの要素の 我々は、この設計されていれば表2、 もう少し巧妙に - に来る - 我々はもう少しこれを設計した場合 巧みに、今適応データとなり ないハードリミットがない構造、 を挿入することができますどのように多くの要素について そこにあなたがしている場合は、持っているので、 大丈夫です衝突、。 ただ、先に行くと、それを追加 我々はあった少し前に見たもの リンクリストとして知られています。 まあちょっとのポーズしてみましょう。 衝突の確率は何ですか 最初の場所で？ 右、多分私は上多分、と思ってい 私は、この問題をエンジニアリング上のよ あなたは何を知っているので？ はい、私は、任意のを考え出すことができる のような私の頭の上から例 アリソンとアーロンが、現実には、 の均一な分布所与 入力は、いくつかのランダムな挿入です データ構造に、本当に何ですか 衝突確率？ まあ結局、それは実際の 超高。 私はこれを一般化しましょう 問題は、このようになります。 だから、nの部屋でCS50学生、何 確率は少なくとも 部屋の中で二人の学生 同じ誕生日がありますか？ だから何があるのです。少数フント - ここで、いくつかの200、300人 今日は自宅で百人。 あなたは何自問したかったのであれば 二人の確率 同じ誕生日を持つこの部屋で、 我々はこれを理解することができます。 そして、私は2のある実際に主張する 同じ誕生日を持つ人々。 例えば、誰もいない 今日は誕生日を持っている？ 昨日？ 明日？ 私はつもりのように全ての権利は​​、ので、それは感じている もっとこの363かそこらをしなければならないために 時間は実際に把握する 我々がしなければ、衝突を持っている。 または私達は単に数学的にこれを行うことが よりもむしろうんざりするほど これを行う。 そして次のことを提案する。 だから私は、我々がモデル化できることを提案する 有する二人の確率 1の確率と同じ誕生日 持つ誰のマイナス確率 同じ誕生日。 だから、これを取得するために、これはただです ために、これを書いての派手な方法 部屋の中で最初の人は、彼または彼女 可能性のいずれかを持つことができ 誕生日は、年に365日と仮定して を持つ人への謝罪と 2月29日誕生日。 だからこの部屋の最初の人は無料です 誕生日、任意の数を有すること 出れるように365の可能性 我々は、365で365を割ったことをやる これは、一つです。 部屋の中で次の人、もし目標 衝突を回避することである、唯一の缶 どのように彼または彼女の誕生日を持っている 多くの異なる可能な日？ 364。 したがって、この式の第二項である 本質的に私たちのためにその数学をやって 一つの可能​​な休み減算することによって。 そして次の日、次の日、 ダウン総数翌日 部屋の中の人。 そして我々はそれから考えれば、その後は何です ていないこと誰も確率 ユニークな誕生日が、再び1マイナス 、私たちが得ることは表現であること それはとてもすてきなことができます このように見える。 しかし、それはもっと面白い 視覚的に見ています。 これは、x軸上でチャートである 部屋の中で人々の数は、 誕生日の数。 y軸上の確率である 衝突、2人 同じ誕生日を持つ。 そして、この曲線から持ち帰りです とすぐに40を好きになるように 学生は、あなたが90％の確率で上昇している combinatorically 2の 人以上持つ 同じ誕生日。 そして、一度は、それが58人を好きになる チャンス2のほぼ100％ 部屋の中の人々が持ってしようとしている そこにもかかわらず、同じ誕生日、 365または366可能バケット、および 部屋の中で唯一の58人。 ただ、統計的には、になりそうだ 、衝突を取得している要するに この議論の動機。 我々はここで空想取得し、たとえている これらの鎖を有する開始、我々はまだだ 衝突を持っているつもり。 質問を頼むように、何ですか 挿入と削除を行うための費用 このようなデータ構造に？ まあ私が提案してみましょう - と私は上の画面に戻りましょう ここで - 私たちは、の要素をn個した場合 我々は、挿入しようとしているそうだとすればリスト、 n個の要素、そして我々は持っている どのように多くの合計バケット？ 31合計バケットを言ってみましょう 誕生日の場合には 1の最大の長さは何ですか 潜在的にこれらの鎖の？ 再び可能31がある場合 与えられた月の誕生日。 そして、私たちはただみんなに凝集している - 実際には、愚かな例です。 代わりに26をしてみましょう。 実際に名前が人々を持っているのであれば それによって与え、AからZで始まる 当方26の可能性。 そして、我々のようなデータ構造を使用している 我々は持っているそれによって我々はただ見て1、 それぞれのポインタの配列、 リンクされたリストを指す 最初のリストは誰です 名前アリスと。 番目のリストは、すべてを使用することです 始まる、始まる名前 Bと、などが挙げられる。 それぞれの可能性が高い長さは何ですか これらのリスト我々は良いクリーンを想定した場合 AからZまでの名前の分布 全体のデータ構造全体で？ データ構造におけるnの人々があります 彼らはうまくなら、26で割った値 全体に広がる データ構造。 そこで、これらのそれぞれの長さ チェーンは26で割ってnです。 しかし、ビッグO記法で、それは何ですか？ 本当にそれは何ですか？ だから、右、本当にただNの？ 我々は過去に言ってきたので、 ぐふあなたは26で割ること。 はい、現実には高速です。 しかし、理論的には、それは基本的ではない すべてが速くなります。 だから我々はすべてそれほどしないと思われる 近いこの聖杯へ。 実際には、これは単に線形時間である。 てか、この時点では、なぜ我々はしないでください ただ一つの巨大なリンクされたリストを使用するのか？ なぜ我々は単に巨大なものを使用していない の名前を格納する配列 部屋に誰も？ まあ、何かがまだある ハッシュテーブルに関する説得力のある？ 説得力のある何かがまだある データ構造について これのように見える？ これ。 学生：[聞こえない]。 SPEAKER 1：それだけの権利、そして再び場合 線形時間アルゴリズム、および 線形時間のデータ構造、なぜ私にはありません ただビッグに全員の名前を格納し 配列、または大きなリンクリストに？ とCSはそんなに難しく停止 それは必要以上に？ でも、このことについて説得力のある何です 私はそれを傷付けず？ 学生：[聞こえない]。 SPEAKER 1：挿入は、ないですか？ もう高価。 だから挿入は、潜在的にはまだ可能性 でも、あなたのデータがあれば、一定の時間が 構造は、このような配列に見える を指している、それぞれのポインタ、 潜在的にリンクされたリスト。 どのようにして定数を達成することができ 名前の時間挿入？ 右、前にそれを貼り付け？ 我々はから設計目標を犠牲にする場合 以前、我々は維持したいところ 例えば、みんなの名前、並べ替え、 やステージ上の数字のすべてが、並べ替え 我々が持っていると仮定 ソートされていないリンクリスト。 それだけ、私たちに1つまたは2つの手順がかかります ベンとブライアンの場合​​のように 以前、ある要素を挿入する リストの先頭。 我々はすべてのソートを気にしないのであれば で始まる名前の、またはすべての Bで始まる名前は、我々はまだすることができます 一定時間の挿入を実現しています。 今、アリスやボブまたは任意の名前をルックアップする より一般的にはまだ何ですか？ それは中に26で割った、nのビッグO、だ 皆が一様だ理想的なケース 配布し、できるだけ多くののあるところ Zの、おそらくであるがありますように 非現実的。 しかし、それはまだ直線です。 しかし、ここで、我々はポイントに戻ってくる という漸近表記 理論的には真。 しかし、現実の世界では、私はそれを主張する場合 私のプログラムでは、26回何かを行うことができます そのプログラムは、あなたよりも速く あなたが使用して好むするつもりですか？ ユアーズや鉱山、その 26倍の速さですか。 現実的には、その人は26です 倍の速さも、理論的にはなら 我々のアルゴリズムは同じで実行 漸近的な実行時間。 私は別のを提案してみましょう 完全に解決。 そして、これはあなたの心を爆破していない場合、 私たちは、データ構造の外出。 だから、これは、それはトライです - 愚かな名前の一種。 それはリトリーバル、ワードから来ている ためのトライ、T-R-I-eが綴られ コー​​スの検索はトライのように聞こえる。 しかし、それは歴史だ ワードトライの。 だからトライは、確かに木のいくつかの種類です そしてそれはまた、その単語に遊びだ。 そして、あなたは非常にそれを見ることができないにもかかわらず、 この可視化と、トライです と家系図のようなツリー構造、 上部とたくさんの一つの祖先 孫やひ孫の としては底に残します。 しかしトライの各ノードが配列です。 そしてそれは、配列内のだ - としましょう 瞬間のために極端に単純 - それはだ サイズ26の配列、この場合には、どこ 各ノードは再びサイズの配列です 26、その中でゼロ番目の要素 配列を表し、最後 そのような各要素に アレイは、Zを表し、 だから私は、その後、提案することは、このデータ トライとして知られている構造は、あり得る 単語を格納するためにも使用する。 我々はどのように格納することができた瞬間前に見ました 言葉、またはこの場合名に、そして我々 、我々は数字を格納することができますどのように前に見た しかし、我々は名前や文字列に焦点を当てている場合 ここで、興味深い何気づく。 私は名前マクスウェルであることを主張する このデータ構造の内部。 どこでマクスウェルを見ていますか？ 学生：[聞こえない]。 SPEAKER 1：左側に。 したがって、このデータで面白いものだ 構造は保存ではなく、ある 弦M-A-X-W-E-L-Lスラッシュゼロ、すべて 連続して、代わりに何をすべきか 以下の通りです。 これは、データ構造のようなトライである場合、 そのノードが再び配列ですそれぞれ、 そして、あなたはマクスウェルを保存したい、あなたの最初の インデックスとそこそこrootのノード、 、最上位のノードを話すことを、 場所M、右、でとても ほぼ真ん中に。 そしてそこから、あなたがフォロー いわば子ノードへのポインタ。 だから家系の意味で、 あなたが下方それに従ってください。 そして、それは別のノードにあなたを導く ですそこに左、上 ちょうど別の配列。 そしてあなたはマクスウェルを保存したい場合は、 あなたを表すポインタを見つける ここではこの一つである、。 その後、次のノードに移動します。 と通知 - これはなぜ絵の 少し欺く - このノードは、小さなスーパーに見える。 しかし、これの右にYおよびZです それは、単に著者が切り捨てただ そのため、実際に絵 物事を見る。 そうでない場合、この絵 非常に広いでしょう。 その後場所Xにだから今は、インデックス、 その後、その後、その後W、その後E、L、L.何 この好奇心？ さて、私たちは新たなこの種のを使用している場合 文字列を格納する方法を取る データ構造、まだする必要が 基本的にデータのチェックをオフ 言葉はここで終了する構造。 換言すれば、これらのノードのそれぞれにおいて 何とか我々ことを覚えておく必要があります 実際にこれらのポインタのすべての指示に従い と少しを残している このここに下部にパン粉 M-A-X-W-E-L-Lを示す構造である 実際にこのデータ構造である。 だから私たちは次のようにこれを行うことがあります。 我々だけで画像内の各ノード 鋸れる1個、大きさ27の配列を有している。 電話で、6を設定しているため、それが、今では27だ 私たちは、実際にあなたにアポストロフィをしてあげる、 ので、オライリーのような名前を持つことができます アポストロフィと、その他。 しかし、同じアイデア。 のそれらの各要素 構造体の配列を指し ノード、これだけノード。 だから、これは非常に彷彿とさせる 当社の連結リストの。 そして私は、ブールを持っている私はよ だけであることを行っている単語を、呼び出し 本当の言葉はこの時点で終了した場合 ツリー内のノード。 それは効果的に少しを表し 三角形の我々は少し前を見た。 言葉はでそのノードで終わるのであれば 木、その単語フィールドは、trueになります 概念的にはオフのチェック、またはされている 私たちは、はいそこに、この三角形を描画している ここでの言葉です。 だから、これはトライです。 そして今の質問は、何ですか その稼働時間は？ それは、nのビッグOはありますか？ それは何か他のものはありますか？ さて、あなたは、このデータに名前をnとした場合 構造、マクスウェルは、ただ一つである それらの実行時間とは何か 挿入またはマクスウェルを見つける？ 実行時間は何ですか マクスウェルを挿入する？ nを他の名前があ​​ったら すでにテーブルに？ うん？ 学生：[聞こえない]。 SPEAKER 1：ええ、それは長さだ 名前の、右？ だからM--X-W-E-L-Lには、このように感じているので、 アルゴリズムは、7の大Oです。 さて、もちろん、名前 長さが異なります。 多分それは短い名前です。 多分それは長い名前です。 しかし、ここで重要なのは、つまり それは定数です。 そして多分それは、実際には一定ではありません しかし神、現実的であれば、内 辞書には、いくつかの制限がおそらくあり の文字の数に 特定の国の人の名前。 そして我々はそれを引き受けることができ この値は定数である。 私はそれが何であるかわからない。 それはおそらくより大きいです 我々は、それがあると思います。 いくつかのコーナーは常にあるので、 クレイジー長い名前の場合。 だからK呼び出してみましょう、それはまだだ 定数おそらく、すべての原因 少なくとも世界で名前、 特定の国では、その長さまたは 短いので、それは一定だ。 しかし、我々は言ってきたときに何かが大きい 定数値のO、何だという と本当に同等？ それは実際には同じことだ 時定数を言うように。 今我々は、不正行為の一種だよね？ 我々はいくつかの理論を活用しての一種だ ここでよく、kの順序があることを言うこと 本当にただ、1の順 そしてそれは時定数です。 しかし、それは本当にです。 ここで重要な洞察力であるため、その 我々はこれで既に名前がnしている場合 データ構造、そして我々はマクスウェルを挿入し、 それが私たちに必要な時間の量です 影響を受けるすべてでマクスウェルを挿入 どのように多くの他の人々によって データ構造にありますか？ していないようです。 私はこれに億以上の要素を持っていた場合 次にトライし、マクスウェルを挿入し、ある 彼はまったく影響を受けた？ いいえ。 そして、それはその日のデータを任意のとは違ってい 我々はこれまで見てきた構造が、どこに アルゴリズムの実行時間です どの程度の完全に独立して ものがあるか、または存在していない そのデータ構造である。 そしてこれはあなたが今ある支払うと その意志Pセット6、のための機会 もう一度あなた自身を実装伴う 15万で読むスペルチェッカー、 言葉、最善の方法のことを格納する 必ずしも明白ではありません。 そして、私は見つけることを熱望してきたのに 聖杯は、私はしないでください トライであることを主張する。 実際には、ハッシュテーブルは非常によくことがあり はるかに効率的であることを証明する。 しかし、これらはただです - それは単に設計上の決定の一つだ あなたは確認する必要があります。 しかし、最後にのがみましょう50かそこら あるものを覗いて見て下さいする秒 先に来週、私たち遷移より このコマンドラインから 物事のウェブ​​に、Cプログラムであれば世界 基づいており、PHPのような言語と JavaScriptとインターネット自体、 あなたがしたHTTPなどのプロトコル、 何年も当たり前の 今では、すべてのほとんどの型付け 多分日、または見。 そして、私たちはピール背中に始めましょう インターネットとは何かの層。 とコードは何ですかそれ 根底には、今日のツール。 ここで、このティーザーの50秒はそう。 私はネットの戦士たちを与える。 [ビデオの再生] - 彼はメッセージで来ました。 プロトコルはすべて彼自身で。 彼は、残酷なファイアウォールの世界に来た 思いやりルータ、および危険遠く 死よりも悪い。 彼は高速です。 彼は強いです。 彼はTCPIPです。 そして、彼は、あなたの住所を持っている。 ネットの戦士たち。 [ENDビデオ再生] SPEAKER 1：どのようにインターネットで 来週のように動作しなければならない。