>> 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を更新するつもり。
そして、私はするつもりです - うーん、何 あなたの名前を再び？
>> 学生：ダイアナ。
>> 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：どのようにインターネットで 来週のように動作しなければならない。