[音楽再生] DAVID J.マラン:すべての権利。 これはCS50である。 これは継続的な週5であり、私達 いくつかの良いニュースと悪いニュースがあります。 だから、良いニュースは、そのCS50です 今週の金曜日が起動します。 あなたは私たちに参加したい場合は、 ここで通常のURLに向かう。 さらに良いニュース、無講義 今度の月曜日13日。 やや少ないより良いニュース、 クイズゼロは次の水曜日です。 詳細はことができます ここで、次のURLで確認。 そして、次の数日にわたる 私たちは、ブランクを埋めることでしょう 部屋に関しては 私たちが予約しているであろう。 よりよいニュースがあるということです もちろん全体の評価である セッションは、この来る 夕方には月曜日。 もちろんのにご注目 場所や詳細についてはウェブサイト。 それにもかかわらずセクション 休日、また、同様に会う予定だ。 最高のニュースは、次の金曜日講義。 だから、これは伝統の私たちです シラバスに従って、持っている。 それは素晴らしいことになるだろうJust--。 あなたは、のようなものが表示されます 一定時間のデータ構造 ハッシュテーブルと木と試みる。 そして、私たちは誕生日の問題について話します。 ものの全体の束 次の金曜日お待ちしています。 [OK]をクリックします。 いずれにせよ。 だから、私たちがしてきたことを思い出して 何、この絵に注力 私たちのコンピュータのメモリの内部。 だから、メモリやRAMはどこのプログラムです あなたがそれらを実行している間に存在する。 あなたはダブルクリックすると いくつかのプログラムを実行するためのアイコン またはダブルクリック いくつかのファイルを開くには、アイコンを、 それはあなたのハードからロードされる ドライブまたはソリッド·ステート·ドライブ RAM、ランダムアクセスメモリ内へ 電源がオフになるまで、それは、住んでいる ラップトップの蓋が閉じ または、プログラムを終了します。 今では、メモリの これは、おそらく持っている 1ギガバイトこれらの日、2 ギガバイト、あるいははるかに、 一般的にレイアウトされている 与えられたプログラムのための 長方形のこの種の中で 概念モデル 私たちは一番下のスタックを持っていることにより、 そして上部に他の原料の束。 非常に上部にあるもの 私たちはこの絵で見てきた 前決して語ら いわゆるテキストセグメントである。 テキストセグメントは変わった方法である 0と1を言うと 実際のコンパイルされたプログラムを構成している。 だから、ダブルクリックしたとき お使いのMacまたはPC上のMicrosoft Word、 あなたは、ドットを実行したときに、または上のマリオを大幅に削減 端末ウィンドウで、Linuxコンピュータ、 構成する0と1 Wordやマリオが一時的に格納される いわゆるにおけるコンピュータのRAMに 特定のプログラムのためのテキストセグメント。 その下には、初期化行く および初期化されていないデータ。 これは、グローバル変数のようなもので、 私たちはの多くを使用していないところで、 しかし機会に私たちはき グローバル変数を持っていた または静的に文字列を定義した ハード "こんにちは"のような言葉を符号化されている ユーザーから取り込まれない それはあなたのプログラムにハードコードされている。 さて、下に下部に、私たち いわゆるスタックを持っている。 そしてスタックは、これまで、私たちはしてきた 目的のものを種類のご利用ですか? のために使用されてスタックとは何ですか? うん? 聴衆:関数。 DAVID J.マラン:関数については? 機能のためにどのような意味で? 聴衆:あなたは関数を呼び出し、 引数はスタックにコピーされます。 DAVID J.マラン:その通りです。 あなたは、関数を呼び出すと、その 引数はスタックにコピーされます。 だから、どんなのXまたはYのまたはAさんやBさんの あなたが関数に渡していることを 一時的に置かれる いわゆるスタック、 ただアネンバーグのような 食堂トレイ、また物事 ローカル変数のように。 もし、あなたのfoo関数またはスワップ この関数はローカル変数を持っている、 一時のように、これら二つの スタックになってしまう。 今、私たちは、についてはあまり話すことはありません それらが、これらの環境変数 一番下に私たちはしばらく前に見たとき、 私は1日にキーボードをいじくった と私は物事をアクセス開始 argvは100のargv千のような、 ちょうど私が忘れてelements-- numbers--それ 私がアクセスすることを想定していなかった。 私たちは、いくつかのを見て始めた 画面上のファンキーなシンボル。 これらは、いわゆるでした 環境変数 のグローバル設定のような私 プログラムまたは自分のコンピュータのために、ではない 最近に関係のない 私たちが議論したバグ、 シェルショック、それはされています かなりの数のコンピュータを苦しめる。 さて最後に、今日の焦点が合って 私たちは最終的にはヒープ上になるでしょう。 これは、メモリの別の塊です。 そして、基本的にすべてこの メモリは同じものです。 これは、同じハードウェアだ。 私達はちょうど一種のだ 異なるクラスタの治療 異なる目的のためにバイト。 ヒープはまた、どこになるだろう あなたが要求した変数とメモリ オペレーティングシステムから 一時的に記憶される。 しかし、問題の種類があります ここでは、絵のように示唆している。 私たちは、ソートのうちの2つを持っている 衝突しようとして出荷されます。 あなたはより多くのを使用しているためのように スタックの、そして私たちが今日見るように 以降、あなたはより多くのを使用したよう ヒープ、​​確かに悪いことが起こる可能性があります。 実際には、それを誘導することができる 意図的または意図せず。 最後のクリフハンガーだから 時間は、このプログラムでした、 任意の機能を提供しなかった 実証する以外の目的 どのように悪い男として、実際に取ることができます 誰かのプログラムのバグの利点 プログラムあるいは引き継ぐ コンピュータシステム全体またはサーバ。 だから一見に簡単に、あなたは 一番下には、メインに気付く コマンドラインで取り ARGVに従って引数。 そして、関数fへの呼び出しを有し、 基本的に無名関数が呼び出さ F、それが[1]のargvを渡しています。 だから、どのような言葉で、ユーザーの種類 このプログラムの名前の後にプロンプ​​ト、 そして、この任意の関数まで トップ、fは、文字列を取り込み、AKAのはchar *、 私たちが議論し始めてきたように、 そしてそれだけで「バー」と呼んでいます しかし、私たちは何もそれを呼び出すことができます。 そして、それは内部の宣言 F、文字の配列の 12そのような文字C--呼んだ。 今、私は言っていた話による 先ほど、ここで、メモリ内の cは、またはそれらの12である 結局つもり文字? ただ明確にする。 うん? 聴衆:スタック上。 DAVID J.マラン:スタック上。 だからcがローカル変数です。 私たちは、12文字または12バイトを求めている。 これらは結局しようとしている いわゆるスタック上。 今、最終的にこの他の関数である それは、実際にはかなり便利だ 私たちは、実際に使用されていませんでした それ自身、strncopy。 これは、文字列のコピーを意味するが、 n個の文字、n文字だけ。 だから、n文字は次のようになります。 Cにバーからコピー。 そして、どのように多くの? バーの長さ。 つまり、言い換えれば、そのように 一行、strncopy、 コピーしようとしている 効果的にCへのバー。 さて、だけの種類の予測する この話の教訓、 ここに潜在的に問題は何ですか? 私たちは、長さをチェックしているにもかかわらず バーとstrncopyにそれを渡し、 あなたの腸はあなたに言って何をされている まだこのプログラムについて壊れ? うん? 聴衆:含まれていません ヌル文字のための部屋。 DAVID J.マラン:含まれていません ヌル文字のための部屋。 潜在的に、とは異なり 過去の練習私たちもしません 持っているプラ​​ス1となるように多くの そのヌル文字に対応しています。 しかし、それはそれよりもさらに悪いです。 他に何私たちは何を失敗している? うん? 聴衆:[聞き取れない] DAVID J.マラン:パーフェクト。 私たちは、ハードはかなり任意に12をコード化しました。 それはそんなにありません 問題が、実は 私たちも、どうかをチェックしていないこと バーの長さは、12未満である その場合、それはなるだろう メモリに入れても安全 私たちが割り当てられてきたというC。 確かに、バーが似ている場合 20文字の長さ、 この関数は、コピーされるようである Cへのバーから20文字、それによって 少なくとも8バイトを取る それがあってはならないこと。 それはここに意味です。 ショート、壊れたプログラムでそう。 大したことなどはありません。 たぶん、あなたはセグメンテーションフォールトを取得します。 私たちは、すべてのプログラムのバグを持っていた。 私達はすべてのバグがあるかもしれません 今のプログラムで。 しかし、意味するところは何ですか? さて、ここでのズームインされたバージョンです 私のコンピュータのメモリのその写真。 これは私のスタックの最下部である。 そして実際、一番下のものです と呼ばれる親ルーチンのスタック、ファンシーな方法 それがメインだと言っている。 誰が関数を呼び出したように、 私たちが話をしているF。 これは、スタックの最下部である。 リターンアドレスは新しい何かである。 それは常に、そこにあっただ 常にその絵にあった。 私達はちょうどそれに注意を呼び出されることはありません。 結局のところのでcが動作する方法です 1関数が別のを呼び出すときに、 それだけでなく、引数を行う 関数がスタックにプッシュされます、 だけではなく、関数のローカルを行う 変数はスタックにプッシュされます、 リターンアドレスと呼ばれるもの また、スタックに置かれます。 具体的には、主通話がfooた場合、メインの メモリ内の自分のアドレス、牛何か、 効果的にスタックに置かれます なるようにfはそれを実行して実行されたとき 本文中にジャンプする場所を知っている 実行を継続するためには、セグメント。 私たちは、概念的にここにいるのであれば、 主に、それからfが呼び出されます。 fは知ってどのように人 バックハンドコントロールへ? さて、この小さな ここに赤でブレッドクラム、 それだけで、リターンアドレスと呼ばれる チェックし、そのリターンアドレスは何ですか? ああ、私はここに戻って主にジャンプしてみましょう。 そして、それは少しだ 単純化の、 0と1のため 主のために技術的にである ここではハイテク部門のアップ。 しかし、それはアイデアだ。 F ただ何を知っている必要があります コントロールが最終的に戻ってどこに行くに。 しかしやり方コンピュータ 長いものを打ち出してきた ローカル変数のようにして 引数は、このようなものです。 だから、この絵の上部の内 青いので、すべて、fに対するスタックフレームです メモリはf 特に使用しています。 だからそれに応じて、ことに気づく バーはこの絵にあります。 バーでは、その引数だった。 そして、私たちは主張し、引数にその 関数がスタックにプッシュされます。 cは、もちろん、ある また、この写真の。 そして、ちょうど表記の目的のために、 左上隅に気付く Cブラケット0になるものであり、 その後、わずかに右にダウン C型ブラケット11である。 換言すれば、あなたが想像することができます バイトのグリッドがあること そこであり、そのうちの最初の 左上の底 これらの12バイトの最後である。 しかし、今早送りしてみてください。 私たちは合格したらどうしようとは何ですか cより長い文字列のバーにある? そして、私たちはどうかをチェックしていない それは確かに長い12よりもだ。 この写真のどの部分をしようとしている バイト0、1、2、3で上書きされる、 ドットドットドット、11、その後、 悪い、12、19を経て13? ここで何が起こるだろう、 あなたが発注から推測した場合 そのCブラケット0が一番上にある そしてcブラケット11は、ソー​​トのダウンしている 右に? うん? 聴衆:まあ、それは起こっている はchar *バーを上書きします。 DAVID J.マラン:ええ、それがどのように見える あなたは、char *バーを上書きするつもりだ。 さらに悪いことには、本当に長いに送信する場合 文字列、あなたも何を上書きする可能性がありますか? リターンアドレス。 どの場合も、同じようにある どこにプログラムに指示するためのブレッドクラム 時Fに戻ります 呼び出されて実行されます。 だから、悪者は一般的に何をすべきか 彼らはプログラムに遭遇した場合です。 彼らはあるかどうか興味があること そのような方法で悪用可能な、バギー 彼または彼女は取ることができること そのバグの利点、 一般的に、彼らは得ることはありません この権利は初めて。 彼らはただ、たとえば、送信を開始し、 あなたのプログラムへのランダム文字列、 キーボードであるかどうかにかかわらず、 または率直に彼らはおそらく 小さなプログラムを書き込むだけで 自動的に文字列を生成、 として、プログラムを叩い開始 異なる入力のロットで送る 異なる長さで。 とすぐにプログラムがクラッシュとして、 それは驚くべきことだ。 それは彼が意味しているので または彼女が発見した 何が実際にはおそらくバグです。 そして、彼らはより巧妙な取得することができます そしてより狭く焦点を開始 そのバグを悪用する方法について。 特に、どのような彼または彼女がかもしれない 何こんにちは、最良の場合には、送信される。 大したことはありません。 それは十分に短いです文字列です。 しかし彼または彼女が送信した場合、 私たちは、それを一般化するようにします 攻撃はそのようにゼロをcode-- そして物事を行うものは RM-RFのように、すべてのものを削除し、その ハードドライブから、またはスパムを送信 または何らかの方法でマシンを攻撃? これらの各もしそうであれば 文字Aはちょうど表し 概念的には、攻撃、攻撃、 攻撃、攻撃、いくつかの悪いコード 他の誰かが書いたことが、 その人は十分にスマートである場合 全て含めるだけでなく、 これらのRM-RFのではなく、 彼または彼女の最後の数バイトを持っている 対応する番号であること 彼のアドレスに 自身の攻撃コード 彼または彼女はちょうどに合格したことを プロンプトを提供することによって、 あなたが効果的にコンピュータをだましことができます fを実行して完了したときに気付いへ、 ああ、それは私がジャンプするための時間です バック赤いリターンアドレスへ。 しかし、彼または彼女は何とか持っているので そのリターンアドレスを重複し 自分の番号を持つ、 彼らは十分にスマートだ ことを設定しているために あなたのように、参照するための番号 スーパートップに表示 そこ左隅、 コンピュータの中に実際のアドレス 彼らの攻撃コードのいくつかのメモリ、 悪者は、コンピュータをだましことができ 彼または彼女自身のコードを実行中に。 そして、そのコードは、再び、何もすることができます。 これは、一般的に呼ばれています ただでシェルコード、 そうでないと言っての道 一般的にRM-RFのような単純なもの。 これは、実際にはBashのようなものだ、 または実際のプログラムは彼を与えること または彼女のプログラム制御に実行する 彼らがしたいことを何か他のもの。 だから要するに、このすべて 単純な事実から派生 関係するこのバグはチェックしていないこと ご使用のアレイの境界。 そして、方法が原因 コンピュータの仕事は、彼らということです からスタックを使用 効果的に、概念的には、 アップの一番下のが、その後の要素 あなたは、トップダウンで育てるスタックにプッシュする これは信じられないほど問題がある。 さて、この問題を回避する方法があります。 そして、率直に言って、言語があります これでこの問題を回避します。 Javaは、例えば、免疫がある この特定の問題に。 彼らはあなたのポインターを与えていないからです。 彼らはあなたを与えていない ダイレクト·メモリ·アドレス。 私たちが持っているこの力を持つので、 メモリには何も触れ 私たちは確かに、大きなリスク、来たいと思います。 だから目を光らせる。 ヶ月で、率直に言って、もし または今後数年間は、いつでも あなたは、いくつかの搾取について読む プログラムやサーバーの、 あなたは今まで何かのヒントを表示された場合 バッファオーバーフロー攻撃のように、 またはスタックオーバーフローは、別のタイプです 攻撃の、基本的に変わるところ、 ウェブサイトのを鼓舞とほとんど あなたがそれを知っていれば、名前を付け、 それはすべてただの話だ いくつかの文字のサイズをオーバーフロー 配列や、より一般的にいくつかの配列。 これについて、次にご質問、、? 自宅でこれをしようとしないでください。 かしこまりました。 これまでの私たちの新しいそれでmalloc関数であった その中で友人たちはメモリを割り当てることができます 私たちは、必ずしも中知らないこと 私たちが持っていないので、することを進める 私たちの中にハードコードする 12のようなプログラム番号。 ユーザーは、どのくらいのを教えてくれるたら 彼または彼女が入力したいデータ、 私たちは、その多くのメモリをmallocをすることができます。 だから、malloc関数にはに、判明 私たちはそれを使用してきた程度は、 明示的に最後の時間、その後、 あなたたちはそれを使用している のために無意識のうちにgetString用 数週間、malloc関数のメモリのすべて いわゆるヒープから来ている。 そして、これは、たとえば、なぜのgetStringです 動的にメモリを割り当てることができます あなたがしているかを知らなくても 事前に入力しようとして、 手あなたに戻っそのメモリへのポインタ、 そのメモリは、まだあなたのものに保つことである、 でもリターンをのgetStringた。 そのため、リコール後にすべてのこと スタックは常に、上下に起こっている 上下に。 そして、すぐにそれが行くように ダウン、それは任意のメモリを意味し、 使用されるこの機能はず 他人が使用することはできませ。 現在では、ごみ値です。 しかし、ヒープがここにある。 そして、何のmallocの良いのはということです malloc関数は、ここでメモリを割り当てる場合、 それがために、影響を受けないです スタックによる大部分は、。 だから任意の関数にアクセスすることができます mallocされていますメモリ、 さえのgetStringなどの機能により、 た後でも、それが返されます。 さて、malloc関数の逆は無料です。 そして実際、ルールあなた 採用開始する必要があります いずれかの、いずれかの、あなたはmalloc関数を使用するすべての時間がある あなた自身は、最終的には、無料で使用する必要があります その同じポインタについて。 私たちが書いているこのすべての時間 多くの理由のためのバギー、バギーコード、。 しかしの一つであった CS50ライブラリを使用して、どの 自身が意図的である バギーは、メモリリークが発生します。 あなたはgetStringメソッドと呼んでいるときはいつでも 過去数週間で 私たちは、動作を求めている メモリのためのシステム、Linuxでは、。 そして、あなたは、一度戻ってそれを与えたことがありません。 そして、これはで、ではありません 実際、良いこと。 そして、Valgrindの、一 のPset 4で導入ツール、 すべてのあなたを助けることについてです 今そのようなバグを見つける。 しかし、ありがたいことのPset 4のためにあなたがする必要はありません CS50ライブラリまたはにgetStringを使用します。 だから、メモリに関連するバグがある 最終的には自分自身のことになるだろう。 だから、malloc関数は単なる以上のものです この目的のために便利。 私たちは、実際には現在、解決することができます 根本的に異なる問題、 そして基本的に多くの問題を解決 効果的に、0週目の約束に従って。 これまでのところ、これは最もセクシーです 私たちが持っていたデータ構造。 そして、データ構造によって私はちょうど意味 概念化メモリの道 ただ言っ超えた形で、 これは、これはchar型で、intです。 私たちは、物事を一緒にクラスタ化を開始することができます。 だから、配列はこのように見えた。 約における重要なものだった アレイは、それはあなたを与えるということです バック·トゥ·バックの塊 メモリ、これらのそれぞれ 同じタイプのものであることを行っている、int型、 int型、int型、int型、またはchar、char型、char型、 チャー。 しかし、いくつか欠点があります。 これは、例えば、ある サイズ6の配列。 あなたが6で、この配列を埋めるとします 数字その後、何らかの理由で、 ユーザーは、提供したいと考えて あなた七番号。 あなたはそれをどこに置けばいいの? あなたが持っている場合解決策は何だ スタック上の配列を作成し、 例えば、ちょうど一週間で 私たちが導入された2つの表記法、 内部番号の角括弧の? さて、あなたは6を持っている これらのボックス内の番号。 あなたの本能は何でしょうか? どこにそれを置くしたいですか? 聴衆:[聞き取れない] DAVID J.マラン:申し訳ありません? ユーザ:エンド​​の上に置きます。 DAVID J.マラン:最後にそれを入れてください。 だから上の右に、 この箱の外側。 どのいいだろうが、それ あなたがそれを行うことはできませんが判明した。 あなたが尋ねていないてしまった場合のため このメモリチャンクの、 それはこのことを偶然かもしれない いくつかの他の変数によって使用されている 完全に。 私たちが置かれたときに一週間かそこらバックだと思う Zamylaとデーヴィンアウトとゲイブの名称 メモリ内の。 彼らは文字通りだった 背中合わせにバックアップします。 だから私たちは必ずしもできない その何でものを信頼 私が使用するためにここの上で利用可能です。 だから、他に何をするかもしれない? さて、一度あなたを実現 サイズ7の配列を必要とする、 あなただけの作成することができます サイズ7の配列は、次に使用する ループまたはwhileループの、 新しい配列にコピーし、 した後、何とかちょうど取り除く この配列は、またはそれを使用して停止します。 しかし、それは、特に効率的ではありません。 要するに、配列はさせてください あなたが動的にサイズを変更します。 だから一方ではあなたが得る すごいランダムアクセス、。 それは、私たちは物事を行うことができますので 分割統治のような、 私たちがしたそのすべてが二分探索、 ここで画面上にについて話しました。 しかし、あなたは隅に自分を描く。 とすぐにヒットとして あなたの配列の末尾、 あなたは非常にをしなければならない 高価な操作 またはコードの全体の束を書く 今その問題に対処する。 だからではなく、あれば私たちは持っていたもの 何かがリストと呼ばれる または特にリンクリスト? どのような場合の代わりになる 矩形は、バックアップするバックアップするバックアップ 私たちは少し離れる長方形を持つ それらの間での余地のビット? そして、私はこれを描いたにも関わらず、 画像またはこの写真を適応 テキストのいずれかからここに戻ってのためであると 後ろ現実には、非常に整然としたバックアップする、 これらの長方形の1 ここまでメモリ内である可能性があります。 そのうちの一つはここにある可能性があります。 そのうちの一つは、ここまでとすることができ、 こっちなどが挙げられる。 しかし、私たちが描いた場合、 この場合、矢印 それは何とかこれらをリンク 四角形一緒に? 確かに、私たちは技術的に見てきました 矢印の化身。 私たちは、最近に使用されている 、そのフードの下に日、 矢印の代表である? ポインタ、右か? それではもし、代わりに 数字だけを格納し、 様9、17、22、26、34、 私たちではありません格納されている場合は、 数が、ポインタのみ このような各番号の横に? だから、ずっとあなたがスレッドになるように 生地の全体の束を通して針、 何とか同点物事 一緒に、同じようにすることができます ポインタを持つ私たちは、として ここに矢印で転生、 一緒に織りの種類 これらの個別の矩形 効果的に、ポインタを使用して その各番号の横に そのいくつかの次の番号を指し、 ポイントには、順番に、いくつかの次の番号? そのように、換言すれば、どのような 私たちは実際たい場合 このような何かを実装するには? さて、残念ながら、これらは長方形、 9との少なくとも一方、17、22において、 など、これらはもはやありません 単一番号で素敵な正方形。 ボトム、四角形 9以下、例えば、 どうあるべきかを表す 32ビットのポインタである。 今、私はまだ、任意のデータ型を認識していないよ C言語でそれはあなただけでなく、int型を提供します しかしポインタ完全に。 だから、私たちが望む場合は、解決策は何ですか これに対する私たち自身の答えを発明するには? うん? 聴衆:[聞き取れない] DAVID J.マラン:それは何ですか? 聴衆:新構造。 DAVID J.マラン:ええ、なぜ 私たちは、新しい構造を作成しないでください またはC言語で、構造体? 私たちは、もし簡単に、前に構造体を見てきました 私たちは学生の構造を扱っ場所 このように、名前と家を持っていた人。 のPset 3ブレイクアウトでは、全体の使用 structs-- GRectとGOvalsの束 スタンフォードは、作成していること 一緒にクラスタ情報。 それでは、私たちはこれと同じ考え方を取る場合 キーワード「型定義」と「構造体」 した後、一部の学生に固有のもの、 そして、次にこれを進化さ: されている構造体node--とノードのtypedef ただ、非常に汎用的なコンピュータサイエンス データ構造内の何かのための用語、 データ構造内のコンテナ。 私が主張するノードが持っているとしている 全く単純なint型のnを、 した後、もう少しひそかに、 この二行目は、次の構造体ノード*。 しかし、あまり技術的な観点から、 その二行目は何ですか 中括弧内のコードの? うん? 聴衆:[聞き取れない] DAVID J.マラン: 別のノードへのポインタ。 だから確かに、少し不可解な構文。 しかし、あなたは文字通り、それを読めば、 次の変数の名前です。 そのデータ型は何ですか? それは、今回は少し冗長だ それは*型の構造体ノードのだ。 私たちは、何かの星を見てきたときはいつでも、その それは、そのデータ型へのポインタであることを意味します。 だから次は明らかである 構造ノードへのポインタ。 ここで、構造体のノードは何ですか? さて、あなたはそれらを参照してください気付く 右上の同じ言葉。 そして実際、あなたはまた、単語を参照してください。 ダウンここで左下にある「ノード」。 そして、これは実際には便利です。 私たちの学生の定義の中のことに注意してください 一度だけ単語 "学生"はあります。 そして、それは学生ためだ オブジェクトは、自己参照はありませんでした。 学生の内側は何もありません それはまた別の生徒をポイントする必要があり、 persay。 それは一種のだろう 現実の世界で奇妙な。 しかし、内のノードとリンク リストは、ノードをしたいですか 類似のオブジェクトへの参照であると。 だから、ここで変更はありません気づく 中括弧の内側だけで何だ。 しかし、私たちは「ノード」という言葉を追加 一番上にあるだけでなく、 一番下に追加する の代わりに "学生。" そして、これは唯一の技術的な詳細です データ構造は、再び、そのよう 、自己参照することができるように ノードは、別のそのようなノードを指すことができます。 だから、これは最終的には何ですか 私たちのために意味するつもり? さて、1、このようなものの内側 私達のノードの内容である。 ここまでこの事、 右上、ちょうどそうです それは、再び、私たちは自分自身を参照することができます。 そして最も外側のもの、 ノードは、新しい用語であるにもかかわらず、 多分、それはまだだ 学生とものと同じ SPLでのフードの下にあった。 だから私たちは今を開始したい場合 このリンクリストを実装し、 どのように翻訳することがあります コー​​ドにこのような何か? さて、ちょうど見てみましょう そのプログラムの一例 実際にリンクされたリストを使用しています。 今日の流通コードのうち、 リストゼロと呼ばれるプログラムです。 私はこれを実行する場合、私は、スーパーを作成 シンプルなGUI、グラフィカル·ユーザー·インターフェース、 それは本当にただのprintfです。 そして今、私は自分自身にいくつかのメニューを与えてくれた options--削​​除、挿入、検索、 とトラバース。 そして、終了します。 これらは、上だけで一般的な操作である リンクリストとして知られているデータ構造。 今、しようとしているの削除 リストから番号を削除します。 インサートを追加しようとしています リストへの番号。 Searchは見に行くされている リスト内の番号の。 トラバースは変わった方法である というのは、リストの中を歩く、 それをプリントアウトするが、それはそれだ。 どのような方法でそれを変更しないでください。 それでは、これを試してみましょう。 それでは先に行くと2を入力してみましょう。 そして私はするつもりだ 番号を挿入する、9は言う。 入力してください。 そして今、私のプログラムはただです と言うようにプログラムされ、リストが9である。 今、私は先に行く場合には 、再び挿入してみましょうか 私は先に行くと、ズームアウトして17を入力します。 今私のリストは、17 9です。 私は再び挿入して行うと、のいずれかを飛ばしてみましょう。 代わりに、私たちがした絵に従って22の ここを見てされて、私は先にジャンプしてみましょう そして、次の26を挿入します。 だから私は、26を入力するつもりです。 私が期待するようにリストである。 しかし、今、ちょうどこのコードかどうかを確認します 柔軟であることを行っている、今私をしましょう 少なくともタイプ22、 概念的に、私たちはなら 確かにある、ソートされ、これを維持する 今は別の目標になるだろう、 17と26の間に行く必要があります。 だから私はEnterキーを押します。 確かに、それが動作します。 だから今私は挿入せ 最後、絵、34あたり。 かしこまりました。 だから、今の私にはそれを明記しましょう 削除し、トラバースして検索が行う、 実際には、働いています。 私が検索を実行しないと実際には、、してみましょう 番号22を検索し、入力します。 それは22を発見した。 だから、何これです プログラムリストゼロません。 しかし、何が実際に起こっている その上で、これは実装して? さて、最初に私が持っている、と確かに可能性があります 私は、list0.hというファイルを持っています。 そして、これがあるとどこかで 行、typedefは、構造ノード、 その後私は、私の中括弧、int型nを持ち、 その後、定義したものをstruct--? 次の構造体ノード。 だから私たちは星を必要としています。 今、技術的に私たちは入る ここでそれを描くのが習慣。 あなたは教科書を参照してください可能性があり、 オンラインの参照があり、それを行う。 それは機能的に同等です。 実際には、これは、もう少し一般的である。 しかし、私は何と一致しているだろう 私たちは前回を行なったし、これを行う。 そして最後に、私はこれを行うつもりです。 ヘッダファイル中のSO list0.hのどこか、 本日、この構造体の定義である、 そしておそらくいくつかの他のもの。 一方list0cにあります いくつかのことになるだろう。 しかし、私たちはただになるだろう 開始し、これを終了しない。 List0.hは私が欲しいファイルである 私のCファイルに含める。 そして、いくつかの点で私は今 無効メインint型を、持っているつもり。 そして私はするつもりだ しなければならないこと、いくつかはここにあります。 私も持っているつもりです プロトタイプ、ボイド、検索、int型のように、 その目的は生活の中ではn、 要素を検索します。 そして、ダウンここに私が主張 今日のコード、空所、検索、int型、nは、 セミコロンないが、オープン中括弧。 そして今、私は何とか検索したい このリスト内の要素の。 しかし、私たちは十分に持っていない まだ画面の情報。 私は実際に持っていない リスト自体を表していた。 私たちが実装できるので、1つの方法 プログラム内のリンクリスト 私はこの種の何かをしたいている 宣言のようにここにリストがリンクアップ。 簡単にするために、私はするつもりだ このグローバル、たとえ一般われわれ中 このあまりすべきではない。 しかし、それはこの例を単純化します。 だから私は宣言したい ここにリンクされたリストアップ。 今、私はそれをどのように行うのでしょうか? ここにリンクされたリストの写真です。 そして、私は本当にない どの瞬間に知っている 私が代表に取り掛かるつもりだ ひとつでたくさんのこと メモリ内の変数。 しかし、背中の瞬間だと思います。 私たちが持っていたこのすべての時間 私たちは、その後、文字列、 の配列であることが明らかに 文字、その、私たち ただポインタであることが明らかに 最初の文字へ 文字の配列内の それがnullで終了だ。 そのロジックによると、これにそう 自分の考えを播種のピクチャ種類、 私たちは実際に私たちに何を書き込む必要が リンクリストを表現するためのコード? どのくらいこの情報の私たちが必要なのです Cコードでキャプチャするには、次のように言うでしょうか? うん? 聴衆:私たちは、ノードへのポインタを必要としています。 DAVID J.マラン:ノードへのポインタ。 具体的には、どのノードがあなたのだろう 本能はへのポインタを保持すること? 聴衆:最初のノード。 DAVID J.マラン:ええ、 たぶん最初。 そして、第1に気付く ノードは、異なる形状である。 これは、構造体の唯一の半分の大きさですが、 ので、それは確かにポインタだけだ。 だから、実際に何ができるかを宣言です 型ノードであるとリンクリスト*。 そして、ちょうど最初にそれを呼ぶことにしましょう ヌルに初期化。 だからヌル、もう一度、来ている ここに絵に。 ヌル特殊な等として使用されるだけでなく、 のgetStringのようなものの戻り値 とmalloc関数は、nullもゼロである ポインタは、ポインタの欠如、 可能ならば。 それはちょうど何もまだここにないことを意味します。 さて、最初に私がいたかもしれない これは何と呼ばれる。 私は、「リスト」と呼んでいる可能性が または他のものの任意の数。 しかし、私はそのように「最初」と呼んでいます この絵でそれラインアップ。 だから文字列のように表すことができ、 その最初のバイトのアドレスと、 そうリンクリストができます。 そして、私たちは、他のデータが表示されます 構造が表現され ちょうど1ポインタで、 32ビットの矢印、ポインティング 構造的には非常に最初のノードで。 しかし、今のは、問題を予測してみましょう。 私は覚えていた場合 私のプログラム内のアドレス 最初のノードの、最初の このデータ構造矩形、 何が良いの約ケースでいた 私のリストの残りの部分の実装? 起こっているキー詳細は何ですか これは実際に動作することを確認するには? そして、私は「実際に動作する」ことで 多くの文字列のように、意味、 私たちは最初の文字から行くことができます 第二にデーヴィンの名前に、 第三に、へ 最後の最後に、第四、 私たちは最後にいるとき、どのように知っていますか このようになりますリンクリストの? た場合は、nullです。 そして、私は、この種の表現だ 電気技師のかもしれないよう、 少しアース付き ある種のシンボル、。 しかし、それはただ、この場合にはnullを意味します。 あなたはそれを任意の数を描くことができます いくつかの方法が、この作者 ここにこのシンボルを使用するように起こった。 私たちは糸引きしているものであれば これらのノードのすべて一緒に、 場所だけ覚えて 最初のものは、とても長いです 私たちは時に特殊記号を置くように リスト内の最後のノードが、 それだから、私たちは、ヌルを使用します 私たちは私たちが利用できる持っているもの、 このリストは完全である。 そして、私は唯一にあなたのポインタを与える場合でも、 最初の要素、あなた、プログラマ、 確かにそれの残りの部分にアクセスすることができます。 しかし、ここであなたの心を聞かせてみましょう 少しさまよい、 彼らはすでにいないのであれば かなり何wandered-- の実行時間になるだろう このリストには何も見つけられませんか? それくそー、それは、nの大きなOはだ、 これは、公平で、悪いことではありません。 しかし、それは線形である。 私たちは、どのような機能をあきらめた よりを移動させることにより、配列の 動的にこの絵に向かって 一緒に織られたまたはリンクされたノードの? 私たちは、ラン​​ダムアクセスを与えてくれた。 配列が原因いいです 数学的にすべてのもの 背面にバックアップする背中合わせにある。 でも、この絵も きれいに見える、とさえ それはこれらのノードのように見えますが うまく実際には、離間している 彼らはどこにでもある可能性があります。 OX1、OX50、Ox123、Ox99、これらの ノードは、どこにでもある可能性があります。 malloc関数はメモリを割り当てないため、 ヒープから、どこにでもヒープに。 あなたは、必ずしもそれがだと知らない 背面に背中合わせになるだろう。 そして、現実の中でそのようにこの絵 かなりこれはかなりあることを行っていない。 だから、少しを取るつもりだ この機能を実装するために働く。 それでは、今の検索を実装してみましょう。 そして、私たちはのようなものを表示されます これを行うための巧妙な方法。 私は、検索機能ですので、もしと I変数、整数nを与えられている を探すために、私が知っている必要があります 内部検索するための新しい構文 だ構造の n個を見つけるために、と指摘した。 それでは、これを実行しましょう​​。 だから最初に私は行くつもりです 先にノードを宣言*。 そして、私はそれを呼び出すつもりだ ただ、慣例により、ポインタ、。 そして、私は最初にそれを初期化するつもりです。 そして今、私はこれを行うことができます いくつかの方法で。 しかし、私は一般的なアプローチを取るつもりです。 ポインタが等しくないですが ヌル、それは有効な構文です。 そして、それはちょうどので、次の操作を行いますことを意味 限り、あなたは何を指していないよう。 私は何をしたいですか? ポインタドットnの場合は、私が戻って来るように そのため、equals--は何に等しい? どのような値私を探しています? 渡された実際のn。 だからここにもう一つの特徴です Cと多くの言語の。 構造は、ノードと呼ばれるにもかかわらず 値nを有する、完全に正当な また、地元の引数を持っている または変数は、nと呼ばれる。 でも私たちは、とあるので 人間の目には、区別することができます このnがおそらくあることを このnは異なる。 構文は異なっているからです。 あなたは、ドットとポインタを持っている、 これに対し、そのようなものを持っていません。 だから、これはOKです。 つまり、同じこと、それらを呼び出すためにOKです。 私はあなたがこれを見つけるしなければ、私は今 何かをしたいとして のような私たちは、nを見つけたことを発表。 そして、私たちは、それを残しておきます コメントや擬似コードコード。 そうでなければ、そしてここにある 興味深い部分、何 現在のノードかどうかはやってみたいん 私が気にn個を含有しないのですか? どのように私は次のことを実現するのですか? で私の指の場合 瞬間はPTRであり、それはだ 何を指して 最初は、を指している どのように私は私の指を動かすん コー​​ド内の次のノードに? さて、私たちがしているブレッドクラムは何ですか この場合には従うつもり? 聴衆:[聞こえない]。 DAVID J.マラン:うん、そう隣。 だから私は戻って私に行けば ここでは、コード、確かに、私は 、ポインタを先に行くと言おうとしている それはだ単に一時的なvariable--です 変な名前、PTRが、 それだけでtemp--ようなものだ 私はポインタを設定するつもりだ どのようなポインタに等しくis-- そして、再び、これがあることを行っている 次moment--ドットのために少しバギー。 言い換えれば、私は私のを取るつもりだ このノードを指しての指 ここに私はあなたが知っている、と言うつもりです 何を、次のフィールドを見てみましょう とに指を動かす それがで指して何でも。 そして、これはしようとしている 繰り返し、繰り返し、繰り返し。 しかし、ときに私の指を行います まったく何をやって止める? とすぐにどのようなコードキックのラインのように? 聴衆:[聞き取れない] DAVID J.マラン:もしポイントながら ポインタはnullに等しいではありません。 ある時点で私の指の ヌルを指してするつもり と私は実現するつもりだ それは、このリストの最後です。 さて、これは少ない 簡単のために罪のない嘘。 それも、私たちにもかかわらずことが判明 ちょうどこのドット表記法を学んだ 構造に対して、ポインタ、構造体ではありません。 PTRは何ですか? ただもっとせこいことです。 これは、ノードへのポインタです。 これは、ノード自体ではありません。 私はここには星がなかった場合は、ポインタ それはノードのabsolutely--。 これは週1のようなものです 変数の宣言、 言葉「ノード」は新しく追加されていても。 しかし、すぐに私たちが紹介するように 星は、今ノードへのポインタです。 そして、残念ながらあなたが使用することはできません ポインタのドット表記法。 あなたは、矢印を使用する必要が 表記法、際立っている、、 初めては、どの作品です 構文の直感的に見えます。 これは文字通り、矢印のように見えます。 だからそれは良いことだ。 そして、ここでダウン、文字通り 矢印のように見えます。 だから私はそれは私にはないla--だと思う 私はオーバーコミット私はhere--だと思う それは最後の新しい作品だと思う 構文の私たちは見ることになるだろう。 そしてありがたいことに、それは確かだ もう少し直感的。 さて、あなたのそれらのために誰が 古い方法を好むかもしれないが、 あなたはまだドット表記を使用することができます。 しかし、月曜日のあたりなど 会話、まず それに行く、そこに行く必要がある アドレスを入力し、[フィールドにアクセス。 これはまた正しい。 そして、率直に言って、これは もう少し知識をひけらかす。 あなたは文字通り言っている、間接参照 ポインタとそこに行く。 その後.Nつかむ、フィールドは、nと呼ばれる。 しかし、率直に言って、誰も望んでいない 入力するか、これを読んでいる。 それで世界が発明した 矢印記法、これ 同一の、同等であり、 それだけでシンタックスシュガーです。 これを言ってはそう空想の方法 良く見える、またはより単純に見えます。 だから今私は1つの他のことをするつもりです。 私がしたら、「休憩」と言うつもりです それので、私はそれを探して保管しないで発見した。 しかし、これは要旨である 検索機能の。 でしかし、それは、はるかに簡単です 最後に、コードをウォークスルーしない。 これは確かに正式な実装である 今日の流通コードの検索の。 私は挿入がないことをあえて言う 中を歩くのが特に楽しい 視覚的に、またしても、削除 一日の終わりにも 彼らはかなりまで煮詰める シンプルなヒューリスティック。 それでは、これを実行しましょう​​。 あなたはここでユーモアに私を、私がやっただろう場合 ストレスボールの束を持って来る。 私は数字の束を持って来た。 そして、私たちは、わずか数人のボランティアを得ることができる 9、17、20、22、29、および34を表すため? だから、基本的に誰もが 誰が今日ここだ。 すなわち、一つ、二つ、三つだった 4、5、6人。 そして、私はいや、見ることgo--するように求めてきた 後ろの1は彼らの手を発生させます。 OK、一つ、二つ、三つ、四つ five--私は6をbalance--ロードしましょう​​。 [OK]を、あなた6アップ点灯。 私たちは他の人が必要になります。 私たちは余分なストレスボールを持って来た。 そして、あなたができれば、のために 一瞬、ライン ただ自分アップ ここで、この絵のように。 かしこまりました。 あなたの名前は何、見てみましょう? 聴衆:アンドリュー。 DAVID J.マラン:アンドリュー、 あなたは9番である。 よろしくね。 ほら 聴衆:ジェン。 DAVID J.マラン:ジェン。 デビッド。 ナンバー17。 はい? 聴衆:私はジュリアです。 DAVID J.マラン:ジュリア、デビッド。 ナンバー20。 聴衆:クリスチャン。 DAVID J.マラン:クリスチャン、デビッド。 ナンバー22。 と? 聴衆:JP。 DAVID J.マラン:JP。 ナンバー29。 だから先に行くとああええとin--取得。 Uhオハイオ州。 スタンバイ。 20。 誰もが、マーカーを持っていますか? 聴衆:私はシャーピーを持っている。 DAVID J.マラン:あなたはシャーピーを得たか。 [OK]をクリックします。 そして、誰もが一枚の紙がありますか? 講義を保存します。 さあ。 聴衆:私たちはそれを持っている。 DAVID J.マラン:私たちはそれを得た? すべての権利、ありがとうございました。 ここで私達は行く。 これはあなたからでしたか? あなただけの一日保存した。 だから29。 かしこまりました。 私は29のスペルを間違えたが、[OK]をクリックします。 どうぞ召しあがれ。 すべての権利、私はあなたをあげる バック一瞬ペン。 だから私たちはここで、これらの人々を持っている。 それでは、他のものを持ってみましょう。 ゲイブは、あなたがプレイしたいですか ここで最初の要素? 私たちは、ポイントするように、あなたが必要です これらの細かい人たちで。 したがって、9、17、20、22、ソート 29、次に34。 私たちは誰かを失うしましたか? 私は34を持っている。 34になりたい場合はdid-- OK、? [OK]を、34、アップ時に来る。 すべての権利、これは次のようになります。 クライマックス価値は十分。 あなたの名前は? 聴衆:ピーター。 DAVID J.マラン:ピーターは、アップ時に来る。 すべての権利、とてもここにある ノードの全体の束。 あなたたちは、それぞれ表している これらの四角形の一つ。 そしてゲイブ、少し奇妙な 男アウトは、最初に表しています。 だから、彼のポインタが少し小さくなっている 他のみんなよりも画面上で。 この場合には、あなたのそれぞれは、左 手が、ダウン指すようにどちらかが起こっている それによって、そのように、nullを表す 単にポインタが存​​在しない場合、 またはそれは指しているために起こっている あなたの隣にノード。 だから、今、あなたが飾る場合には 絵のような自分 ここでは、先に行くとポイント ゲイブと、お互いに における特定のポインティング中 リストを表現するための番号9。 [OK]をクリックし、数34、左手 ただ床を指している必要があります。 [OK]を、これはリンクされたリストである。 これは、問題のシナリオがある。 実際、これは、代表的 問題のクラスの あなたがコードで解決しようとする可能性がある。 あなたが最終的に挿入したい リストに新しい要素。 この場合、私たちはするつもりだ 番号55を挿入してみてください。 しかし、あるように起こっている 考慮すべき別のケース。 そして実際、これは1つになるだろう 全体像がここに持ち帰りの、ある、 異なるケースは何ですか。 もし異なる条件はどのようなものがありますか あなたのプログラムが持っているかもしれない支店? さて、その数はあなたがしようとしている 私たちは55であることを今知って、挿入、 しかし、あなたは知らなかった場合は、 事前に、私はあえて 少なくとも三つに分類さ 考えられる状況。 新しい要素はどこでしょうか? 聴衆:そして最後または中間。 DAVID J.マラン:最後に、中 中間、または冒頭に。 だから私は、少なくともそこの主張 3つの問題が、私たちは、解決する必要があります。 のは、おそらく何を選択しましょう 間違いなく最も簡単な 1、どこに新しい要素を 初めに属します。 だから私は非常にコードを持っているつもりです 私は書いた検索、などである。 そして、私は、これPTRを持っているつもりです 私は私の指でここに表します いつものように。 そして、どのような値を覚えている 私達はにptrを初期化したのですか? だから私たちは、最初はnullに初期化されました。 しかし、私たちは、かつて何をした Googleの検索関数内でしたか? 私たちは、最初にそれが等しくなるように設定 これを行うことを意味しな​​い。 私が最初に等しくptrが設定されている場合、どのような 私の手は本当に指し示すすべきですか? 右。 ゲイブと私がしようとしているのであれば ここに等しい値とすることで、 私たちは数9の両方でポイントにする必要があります。 だから、これは私たちの物語の始まりだった。 そして今、これはただ単純である、 にもかかわらず、構文は新しく追加されました。 概念的には、これは単なる線形探索である。 9に等しい55ですか? というか、のは9よりも小さいとしましょう​​。 私がしようとしているため、 55を配置する場所を見つけ出す。 9未満、17未満、より少ない 20未満、22未満、29未満、 未満34、ない。 だから今、私たちは、大文字にしている 少なくとも三つの一つ。 私はここの上に55を挿入したい場合、どのような コー​​ドの行が実行される必要がありますか? どのようにこの写真を行います 人間は変更する必要がありますか? 私は私の左手で何をしますか? これは、最初はnullでなければなりません 私はリストの最後に来ているので。 そして、何をどうすべき ここでは、ピーターと、それがあった? 彼は明らかに私を指すようになるだろう。 だから私は、少なくとも2行があります主張 本日からのサンプルコード内のコードの それがこれを実装するために起こっている 末尾55を追加したシナリオ。 そして、私は誰かのホップを持つことができ 上下わずか55を表す? すべての権利は​​、新しい55です。 だから今何次かの シナリオは、やって来る 私たちは時に挿入したい 始まるか、このリストの先頭? そして、あなたの名前、番号55は何ですか? 聴衆:ジャック。 DAVID J.マラン:ジャック? OK、はじめまして。 ご搭乗ありがとうございます。 だから今、私たちはするつもりだ 、たとえば、5番を挿入します。 ここでの第二のケースです 3私たちは前に思い付いた。 だから5が先頭に属している場合、 それでは私たちはそれを見つける方法を見てみましょう。 私は私のPTRを初期化 再び9番へのポインタ。 そして、私は、ああ、5が9未満であり、実現した。 だから、私たちのためにこの絵を修正。 誰の手、ゲイブさんやダビデの or-- 9番の名前は何ですか? 聴衆:ジェン。 DAVID J.マラン:ジェンのhands-- 私たちの手のどの変更する必要がある? そう、ゲイブは今何を指して? 私を。 私は、新しいノードです。 だから私は移動だけの種類よ ここで、視覚的にそれを見ることができます。 そして、その間何を私はそれを指すのですか? それでも私はどこを指しています。 だから、それはそれだ。 コー​​ド修正のだから本当に一行 この特定の問題は、それが思われる。 すべての権利、その結果は良いことだ。 そして、誰かが5のプレースホルダことができますか? アップさあ。 私たちはあなたの次の時間を取得します。 そうnow--すべての権利、および 余談ですが、名前など 私は権利の明示的な言及をしていないよ 今、predがポインタ、前身ポインタ そして新しいポインタ、それはだ 指定された名前だけ ポインタへのサンプルコードで、または 周りのポインティングのようなものだ私の手。 あなたの名前は? 聴衆:クリスティン。 DAVID J.マラン:クリスティン。 ご搭乗ありがとうございます。 すべての権利なので、今度は、考えてみましょう 少し厄介なシナリオでは、 私が挿入したいとなる この中に26のようなもの。 20? なに? これらは、私たちはこのペンを持って良いことをare--。 すべての権利、20。 誰かがの別の部分を得ることができれば 紙だけで大丈夫case--にお​​いて、準備ができて。 ああ、面白い。 さて、これは一例です 講義のバグ。 [OK]をので、あなたの名前が再び何ですか? 聴衆:ジュリア。 DAVID J.マラン:ジュリア、あなたが開くことができます アウトとあなたがそこに決してなかったふり? [OK]を、これは決して起こらなかった。 ありがとう。 だから私たちは挿入​​するとします このリンクリストにジュリア。 彼女は20番です。 そしてもちろん、彼女はだ に属しているつもり begin--まだ何を指していません。 だからあなたの手が種類のものであってもよい nullまたは一部のごみ値ダウン。 のクイック話をしてみましょう。 私は5番で、この時間を指しています。 それから私は9をご確認ください。 それから私は、17をご確認ください。 それから私は、22をご確認ください。 そして、私は、oohの、ジュリアを実現 22の前に行く必要がある。 だから何が起こる必要がある? 誰の手に変更する必要がありますか? ジュリアさん、鉱山、or-- もう一度お名前は何ですか? 聴衆:クリスチャン。 DAVID J.マラン:キリスト教や? 聴衆:アンディ。 DAVID J.マラン:アンディ。 クリスチャンやアンディ? アンディはを指すように必要ですか? ジュリア。 かしこまりました。 だからアンディ、あなたはジュリアを指すようにしたいですか? しかし、ちょっと待って。 これまでの話では、 私は1つのようなものだ 担当は、その意味で ポインタのですものです リストを移動する。 私たちは、アンディの名前を持っているかもしれませんが アンディと呼ばない変数がありません。 私たちが持っている唯一の他の変数です まず、ゲイブで表さだ人。 だから、これは、なぜこのように実際に ここまでは、これを必要に応じていませんでした。 しかし、今、画面にあります PREDのポインタ再び言及。 だから私はより明確になるであろう。 これがポインタである場合、私はより良い持っていた もう少しインテリジェント取得 私の反復に関する。 あなたは私がここを通過する気にしない場合 もう一度、ここで指して、ここに指摘した。 しかし、私はPREDポインタを持ってみましょう 前身ポインタは、それはだ を指し示すの種類 要素私はちょうどにあった。 だから私は今、ここに行くとき 私の左手の更新。 私はここに私の左手の更新を行ったとき。 そして今、私はへのポインタだけでなく、を持っている ジュリアの後に行く要素、 私はまだへのポインタを持っている アンディ、前の要素。 だから、基本的に、アクセス権を持って パン粉、可能ならば、 必要なポインタのすべてに。 私が指差しているのであれば アンディと私も向いています その手のクリスチャン、で 今別の場所で指摘しておかなければならない? アンディだから今ジュリアで指すことができます。 ジュリアは今クリスチャンで指すことができます。 彼女は私をコピーすることができますので、 右手のポインタ。 そして、それは効果的にあなたを置きます ここに戻ってこの場所へ。 だから要するに、これでもかの 永遠の種類の私たちを取っている 実際に更新する リストをリンクし、実現 操作すること 比較的簡単である。 これは、一つ、二つ、三つのだ 最終的にはコードの行。 しかし、それらの周りに巻か おそらくコードの行 ロジックのビットは、その効果的です。 私たちは質問を、尋ねる? 私たちが先頭にいる、 中間、または末尾? さて、いくつかの他は確かにありま​​す 私たちが実装する場合があり操作。 そして、ここでこれらの写真はただ描く 私たちはただ人間でやった。 どのような除去はどうですか? 私がしたい場合は、例えば、 番号を削除する34または55、 私は、同じ種類のコードを持っているかもしれません しかし、私は、1つまたは2つのステップを必要とするつもりです。 新しいものだから? 私が最後に誰かを削除した場合、 番号のような55、次に34、 何も、私はそれを行うように変更することがあります? 私はevict--しないように持っている もう一度お名前は何ですか? 聴衆:ジャック。 DAVID J.マラン:ジャック。 私は、evict--無料ジャックだけでなく、する必要が そう、文字通り自由なジャックに電話するか、少なくとも そこにポインタすぎたが、今 何がピーターに変更する必要がある? 彼の手が、より下向き始める。 とすぐに私は無料の呼び出しとしてあるため ジャックは、ピーターのは、まだジャックを指している場合 そして私はそのため横断続ける リストおよびアクセスこのポインタ、 それは時に私たちの古くからの友人のセグメンテーションだ 障害が実際に蹴ることがあります。 私たちが与えてくれたので ジャックへのメモリバック。 あなたはそこに滞在することができます ぎこちなくただ一瞬。 私たちはいくつかありますので 考慮すべき最後の操作。 リストの先頭を削除する、 またはbeginning--、この1つの 少し迷惑。 私達はあることを知っている必要があるのでゲイブ このプログラムでは一種の特別なものです。 確かに、彼は彼自身のポインタを有しているからである。 彼はただ、指し示されてないです として、ここで他のほとんどの人がある。 だから、リストの先頭であるとき その手の今変更する必要がある、削除? もう一度お名前は何ですか? 聴衆:クリスティン。 DAVID J.マラン:私はひどいよ 名で、明らかに。 だから、クリスティンとゲイブ、 その手に変更する必要があり 私たちはクリスティーヌを削除しようとすると、 画像からナンバー5、? OK、それでは、ゲイブをやらせる。 ゲイブが指すようになるだろう、 おそらく、9番で。 しかし、次は何が起こるのでしょうか? 聴衆:クリスティンべき [聞き取れない] nullになる。 DAVID J.マラン:OK、私たちはおそらくべき make--私はどこかに「ヌル」を聞いた。 聴衆:ヌルと彼女の自由。 DAVID J.マラン:ヌル何? 聴衆:ヌルと彼女の自由。 DAVID J.マラン:ヌルと彼女の自由。 だから、これは非常に簡単です。 そして、それはあなたが今、ソートしていることを完璧だ そこに立っての、属していない。 あなたがしてきたので リストから切り離さ。 あなたが効果的にしてきた リストから孤立した。 だから私たちはより良い今の空き呼び出していた クリスティーヌは、その記憶をお返しします。 それ以外の場合は毎回、私たち リストからノードを削除 私たちは、リストを作るかもしれない 短いが、実際には減少していない メモリ内のサイズ。 だから私たちは追加し続ける場合 リストに物事を追加、追加、 私のコンピュータは遅い得るかもしれない 遅い遅い、 私は外に実行しているので、 私は実際にいないよ場合でも、メモリ、 クリスティンのバイトを使用して メモリのもう。 だから、最終的には他の存在 course--除去のシナリオ、 途中で、除去 私達が見たように、最後に。 しかし、より興味深いの 現在の課題はある 正確に考慮することになるだろう 実行時間は何ですか。 つまり、あなたの保つことができるだけでなく、 紙片、ゲイブ、もし、 あなたが与えて気にしないだろう 誰もがストレスボール。 私達のリンクリストにどうもありがとうございます あなたができれば、ここにボランティアの。 [拍手] DAVID J.マラン:すべての権利。 分析のだからカップル その後の質問、私はできれば。 私たちは、以前にこの表記を見てきました、 ビッグOとオメガ、上限 上と下限 いくつかのアルゴリズムの実行時間。 それでは、ただ考えてみましょう 質問のカップル。 一、私たちはそれを言った 前、ランニングは何ですか のための検索時 ビッグOの点でリスト? ランニングの上限は何ですか リンクリストを検索する時 ここに私たちのボランティアによって実施されるように? これは、n個の大O、線形です。 最悪の場合にはあるので、 55のような要素、 私たちが探しているかもしれないと、どこに可能性があります ジャックは、最後にすべての方法でした。 そして残念ながら、配列とは異なり、 私たちは、この時間は空想取得することはできません。 私たち人間のすべてであったにもかかわらず、 小さな要素、5から選別、 大きな要素までのすべての方法、 55、それは通常は良い​​ことだ。 しかし、その仮定を何 もはや私たちが行うことができない? 聴衆:[聞き取れない] DAVID J.マランは:もう一度言って? 聴衆:ランダムアクセス。 DAVID J.マラン:ランダムアクセス。 そして、今度はそれがありません私たちができることを意味します 長く、弱いゼロ、直感を使う バイナリを使用すると自明性 検索し、分割統治。 たとえあるため、私たち 人間は明らかにできた アンディまたはクリスチャンであったことがわかります 大体、リストの途中で、 私たちは、としてそれを知っている リストをスキミングすることにより、コンピュータ 当初から。 だから私たちは、ラン​​ダムアクセスを与えてくれた。 だから、nの大きなOが今アッパーです Googleの検索時に結合した。 どのようなGoogleの検索のオメガはどうですか? 下界検索についての周辺情報 このリスト内のいくつかの数の? 聴衆:[聞き取れない] DAVID J.マランは:もう一度言って? 聴衆:One。 DAVID J.マラン:One。 だから、一定の時間。 最良のケースでは、クリスティーンは、 確かに、リストの先頭に。 そして、私たちは探している 5番は、私たちは彼女を見つけた。 だから大したことない。 しかし、彼女は時があるはずだ この場合、リストの先頭。 どのような削除のようなものでしょうか? あなたは要素を削除したい場合は? 何が上限と下限の リンクされたから何かを削除について リスト? 聴衆:[聞き取れない] DAVID J.マランは:もう一度言って? 聴衆:nである。 DAVID J.マラン:nは 確かに上限を。 最悪の場合、私たちは試しているので 先ほど行ったよう、ジャックを削除します。 彼は最後に、すべての方法です。 永遠に私たちを取りますか、 彼を見つけるためにn個のステップ。 だから上限です。 つまり、必ず、線形です。 そして、最高のケースは、実行時間、または 最良の場合下限 一定の時間になります。 多分私達は、削除しようとしているため クリスティン、そして私たちは幸運を得る 彼女が初めにあります。 今ちょっと待って。 ゲイブは、冒頭でもありました そして私たちもゲイブを更新する必要がありました。 だから、あと一歩ではありませんでした。 だから、確かに一定であり、 時間、最良の場合には、 最小の要素を削除するには? それは、2つである場合でも、である、 コー​​ドの3、またはさらには100ライン、 それは、同じ数の場合は、 ラインではなく、いくつかのループ内で、 とサイズに依存しない リストの、絶対に。 にある要素を削除する リストの先頭に、 私達はに対処する必要があっても、 ゲイブは、まだ一定の時間である。 だから、これはのように思える 後方に巨大なステップ。 そして、時間のもったいない 週1週中に、もし 私たちだけではなく、持っていたゼロ 擬似コードコードが、実際のコード ログの何かを実装する ベースnは、またはログ、むしろ、nは、ベース2、 その実行時間の点で。 それでいったい私たちは開始したいと思う理由 リンクリストのようなものを使用して? うん。 聴衆:だからあなたが追加することができます 配列に要素。 DAVID J.マラン:だからあなたができる 配列に要素を追加します。 そして、これはあまりにもテーマのある。 そして、私たちは表示され続けるだろう この、このトレードオフ、多くの のような私たちが見てきた マージソートとトレードオフ。 私たちは本当にスピードアップできた むしろ、検索または並べ替え、 私たちはもう少しスペースを費やす場合には メモリの追加のチャンクを持っている またはマージソートのための配列。 しかし、私たちはより多くを過ごす スペースが、私たちは時間を節約できます。 このケースでは、だ 時間をあきらめるが、私たちがしている 柔軟性を増し、 ダイナミズム可能ならば、 これは間違いなくポジティブな機能です。 また、スペースを費やしている。 どのような意味ではリンクされている より高価一覧表示 配列以外のスペースの面で? どこに余分なスペースがから来ている? うん? 聴衆:[聞こえない]ポインタ。 DAVID J.マラン:ええ、私たち また、ポインタを持っている。 だから、これはminorly迷惑です そのもはや午前中 私はint型を格納 int型を表します。 私はint型であり、aを格納しています また32ビットであるポインタ。 だから私は、文字通り倍増してい スペースの量は、含まれる。 だから、トレードオフだが、 それがint型の場合にはあります。 あなたはint型を格納していないと仮定し、 これらの各矩形を想定 またはこれらの人間のそれぞれが表すた 単語、英語の単語こと 5文字、10かもしれない 文字、多分もっと。 それからちょうど32以上のビットを追加する 大したことの少ない可能性があります。 どのような学生のそれぞれの場合 デモ中 文字通り、その生徒の構造体であった 多分名前と住宅やを持っている 電話番号やツイッター ハンドル等が挙げられる。 だから、すべてのフィールドの私達が開始 先日の話、 など大したことのはるかに少ない 私達のノードがより面白くなる 追加と過ごすことが大きい、ええ、 ポインタは、単にそれらを一緒にリンクします。 しかし、確かに、それはトレードオフです。 そして実際、コードは あなたとわかるように、より複雑な を通してスキミングによる参照 その特定の例。 しかし、何があった場合 ここでいくつかの聖杯。 私たちが一歩を踏み出すないとどう 後方が、巨大な一歩 およびデータを実装する 私たちは経由構造 ジャックなどの要素を見つけることができます クリスティンまたはその他の要素 真の定数時間でこの配列内の? 検索は一定である。 削除は定数である。 挿入は一定である。 これらの操作の全ては一定である。 それが私たちの聖杯になります。 そしてそれはどこに私たち 次回をピックアップします。 その後お会いしましょう​​。