[音楽再生] [ビデオ再生] -HEが横たわっています。 -何について？ -知りません。私たちは何を知っていますか-SO？ 9時15分、レイで - つまり Santoyaは、ATMにありました。 -Yeah。そこで問題は、何ですか彼は9:16でやっていましたか？何かで9ミリメートルを-Shooting。たぶん彼は狙撃兵を見ました。 -orは彼と一緒に仕事をしていました。 -待つ。 1に戻ります。あなたは - 何を見ていますか？全画面までの彼の顔を-Bring。 -Hisメガネ。反射が-Thereです。 - それはヌエビタス野球チームです。それは彼らのロゴです。 - そして彼がに話しています誰がそのジャケットを着ています。 [END再生] DAVIDマラン：すべての権利。これはCS50であり、これはもう少しです [聞こえない]これであなたをしています問題に手を染めには、4つを設定します。今日はもう少し見て開始します深くポインタと呼ばれるこれらの事で、それはだにもかかわらず、これかなり難解な話題、それが起こっていることが判明我々手段であることが構築し、組み立て開始することができますはるかに洗練されたプログラム。しかし、我々は最後の水曜日にそれをやりました最初のいくつかのクレイメーションを介して。これは、リコールがあり、 Binkyと我々は彼を使用しましたそのプログラムを見てみます本当に面白い何もしませんでした、しかし、それはいくつかの問題を明らかにしました。では、なぜ私たちが歩いていない、今日を開始しますすぐにこれらのステップのいくつかを経て、人間の言葉の中に蒸留してみてくださいまさにここで起こっていますそしてなぜこれが悪いですし、その後に移動しますそして実際に何かの構築を開始この技術では？したがって、これらが最初でしたこのプログラム内の2つのラインそして、素人の観点から、どのようなこれらの2行はやっているの？合理的に快適な誰か画面上で宣言されているものと？これらの2行は何をしているのか？それはすべてのことではありません 1週間は異なります、しかし、いくつかの新しい特別なシンボルがあります。うん？そこに戻って。聴衆：ポインタを宣言？ DAVIDマランは：もう一度言って？聴衆：ポインタを宣言？ DAVIDマラン：宣言ポインタとそれでは、もう少しそれを改良してみましょう。聴衆：[聞こえません] アドレスxとyのその後。 DAVIDマラン：そして取り組みます。だから、特に私たちがやっていること我々は2つの変数を宣言しているされています。これらの変数は、しかし、行っています int型のスターであることが、これより具体的な手段彼らは店に行くされています int型のアドレス、それぞれ、x及びy。今、任意の値があるのですか？これらのいずれかの実際のアドレスがありますこの時点での二つの変数？いいえ。それはちょうど、いわゆるゴミ値です。あなたが実際に割り当てない場合 RAMにあったものは何でも変数、以前にゼロを埋めるために起こっていますそして、のものそれらの変数の両方。しかし、我々はまだ知りません彼らは何をしている、それはですなぜBinkyの鍵になるだろう先週彼の頭を失いました。だから、これはクレイメーションましたこのの化身あなただけの2つの変数を持っていることによって、粘土の小さな円形の部分、それは変数を格納するが、のようなことができます包ま矢印が示唆します、彼らは実際には向いていませんどこでもそれ自体知られています。だから我々は、この行があったが、この新しい先週は、メモリ用のmallocましたただ派手な方法で割り当て、オペレーティングシステムを伝える、LinuxのまたはMac OSやWindows、ちょっと、私にいくつかのメモリを与え、あなたが持っているすべてを伝えるためにオペレーティング・システムメモリのためにそれを要求するときにするものです。それは何を気にするつもりはありませんあなたはそれをどうするつもりです、しかし、あなたは、動作を指示する必要があります何malloc関数を介してシステム。うん？聴衆：どのくらい？ DAVIDマラン：どのくらい？どのくらいのバイトで、そのため、この、再び、不自然な例は、単に言っています、私はint型の大きさを与えます。 int型の今、サイズ 4バイトまたは32ビットです。だから、これはただの方法であります言って、ちょっと、オペレーティングシステム、私は4バイトのメモリを与えます私は自由に使用することができ、具体的には、何を mallocの戻り 4バイトのそのチャンクに？聴衆：住所？ DAVIDマラン：アドレス。 4バイトのチャンクのアドレス。その通りです。そしてそうそれは最終的に保存されているものです xのと私たちは本当にない理由です気にどのようなことの数アドレスは、OX1またはOX2だか、ありますまたはいくつかの不可解な16進アドレス。私達はちょうど絵ケアその変数xは今であることメモリのチャンクを指します。だから、矢印はポインタを表し、またはより具体的には、メモリアドレス。しかし、再び、私たちは一般的に気にしませんそれらの実際のアドレスが何でありますか。さて、この行は述べています何普通の言葉で？スターxは42セミコロンを取得します。これは何を意味するのでしょうか？あなたが行きたいですか？あなたの首に傷を付けないでください。聴衆：xのアドレスは42です。 DAVIDマラン：xのアドレスは42です。全くありません。とても近く、しかしかなり、ありますので、このXの前に付けるのスター。だから我々は少しを微調整する必要があります。うん？聴衆：値ポインタxが42であるために指しています。 DAVIDマラン：OK。ポインタxがあると値指し、42でなければならない、のは言わせて、または別の方法で、星を置きます xは任意のアドレスに行く、と言いますそれは1オックスフォードだかどうか、Xであり、ストリートまたは33オックスフォードストリートまたはOX1またはox33、何でもその数値アドレスであり、スターxはxの逆参照です。だから、そのアドレスに移動し、そこ番号42を置きます。だからだろうそう言うのと同等の方法。だから、すべての罰金だとその後我々は、画像を表すことになります我々が追加した場合は、次のように 4のそのチャンクへ42 右側のバイトが、物事がゆがんでどこに行ったこのラインはありましたそして、Binkyの頭がポップこの時点でオフ、悪いことが起こるときのためあなたごみ値を間接参照無効な間接参照したりポインタは、と私は無効と言いますこの時点で理由物語、Yの内側に何ですか？ベースyの値は何ですか過去数ステップの？うん？あれは何でしょう？聴衆：アドレス。 DAVIDマラン：アドレス。それはアドレスでなければなりませんしかし、私はそれを初期化していますか？だから私はまだ持っていません。だから何がそこにあることが知られていますか？それだけでいくつかのゴミ値です。それは、ゼロからの任意のアドレスになります 20億あなたがRAMの2ギグを持っている場合、またはゼロ億4にあなたがしている場合 RAMの4ギガバイトを得ました。これは、いくつかのゴミ値ですしかし、問題がありますオペレーティングシステムなお、それはあなたが与えられていない場合メモリのチャンク、具体的あなたが行くようにしようとしていることを、それは一般的に何を引き起こすことが起こっています私たちは、セグメンテーションフォールトとして見てきました。だから実際には、すべてのあなたの持っている人営業時間での問題で苦戦以上だ問題で一般的に把握しようとセグメンテーションフォールト、それは一般的な手段あなたはのセグメントに触れていますあなたがすべきではないメモリ。あなたは、メモリに触れていることオペレーティングシステムがない持っていますそれはだかどうか、あなたが触れることを許さあなたの配列にすぎ行くことによってかどうか、今始まりますあなたが触れているので、それはです単にいくつかのゴミ値であるメモリ。そこでここではスターxをされてい未定義の動作の一種。オッズので、あなたはそれを行うべきではありません、プログラムだけでクラッシュするだろうし、あなたが言っているので、このアドレスに行きますあなたはどこ見当がつかないそのアドレスが実際にあります。だから、オペレーティングシステムがそうですあなたのプログラムをクラッシュさせるつもり結果として、実際、それはです何がBinkyにそこに起こりました。だから最終的に、Binkyは固定しますこれでこの問題。だから、そのプログラム自体は欠陥ました。しかし、あなたは、ソートの押し進める場合その代わりに、この行を実行し、 yは、xがちょうど何を意味等しいですアドレスは、xである、また、Yに入れます。だから絵、我々はしました 2矢印でこれを表現 Xからとyのポインティングから同じ場所へ。だから、意味的には、xは等しく、 yにあるため、それらの両方同じように保存していますアドレスは、エルゴは、42を指しそして今、あなたは星を言うとき yは、yのアドレスに移動、これは興味深い副作用を有しています。だから、yのアドレスです xのアドレスと同じもの。ですから、アドレスに行くと言えば yに13に値を変更し、他の人に影響を与えているのですか？ Xは、D点で、いわば同様に影響を受けるべきです。そしてニックはこの絵を描いた確かに、どのようにクレイメーションでまさにそれでした。我々はポインタをたどるにもかかわらず yは、我々は、同じ場所で終わりましたそして私たちは、印刷した場合 xまたはyのポインティング先出、その後、我々は13の値を参照してくださいだろう。今、私は指示先があることを言いますビデオと一致しました。私のプログラマ、知識、決して実際に単語指示先を言って、尖っているものではなく、一貫性のためにビデオを実現それがあったことすべてですそのような状況で意味しました。クレイメーションのそうご質問またはポインタやmalloc関数まだ？なし？大丈夫。だから、さらになし ADO、のは見てみましょうこれが実際に有している場合にしばらくの間使用されて。だから我々は、このCS50ライブラリを持っていましたそれは、これらの機能をすべて持っています。私たちは、GetIntでたくさん、のGetStringを使用しましたおそらく以前GetLongLong 私のPSET内の1つまたはそうが、実際に何が起こっているされていますか？さて、簡単に見てみましょうそのプログラムではフードの下に私たちはあなたにCS50を与える理由を鼓舞ライブラリ、および実際に先週のように、我々は、これらのを取り始め補助輪オフ。だから、これは今ソートされます何の死後の続いています CS50ライブラリ内には、我々は今、移動を開始しますにもかかわらず、それから離れてほとんどのプログラムで。だから、これはscanfの0と呼ばれるプログラムです。それは超短いです。それはちょうどこれらの行を持っていますが、それ scanf関数と呼ばれる関数を紹介します我々は、実際に表示しようとしていること CS50ライブラリの内部瞬間、わずかに異なる形ではあるが。ライン16上のため、このプログラム変数xを宣言しています。だから、私はint型のための4つのバイトを与えます。これは、ユーザーが言っています数お願いし、その後これは興味深い行であること実際に先週結びつけますこれ。 scanfの、その後はそれが取る気づきます書式文字列、ちょうどprintfのような、％私はint型を意味し、それがかかります少し見える二番目の引数ファンキー。それはアンパサンドXの、と思い出して、我々は、最後の週に一度これを見ました。アンパサンドxは何を表しているのでしょうか？アンパサンドは、C言語で何をしますか？うん？聴衆：のアドレス。 DAVIDマラン：のアドレス。だから、反対ですスター演算子の、スターオペレータが言うのに対し、に行きますこのアドレス、アンパサンド演算子把握、言いますこの変数のアドレス、ので、これは、鍵となります生活の中でのscanfの目的利用者をスキャンすることですキーボードからの入力、どのような彼または彼女に依存タイプは、その後、そのユーザの入力を読み取ります変数に、しかし、我々過去2週間で見ました我々そのスワップ機能その実装する難なくみましたちょうど壊れていました。スワップ機能でそれを思い出し、私たちはint型としてAとBを宣言した場合、我々が正常に交換しましたスワップの内側に二つの変数ちょうどミルクとOJと同じように、しかし、すぐにスワップが返されます、結果何でした xとyに、元の値？何もありません。うん。何もするので、その時間を起こりませんでしたスワップは、唯一のローカルコピーを変更しますすべて、言うことです私たちがきたときには、この時、引数を渡すされて関数に、私たちはしています単にこれらの引数のコピーを渡します。あなたはそれを行うことができますあなたも一緒にやりたいです、しかし、彼らはありません必要があるとしています元の値への影響。あなたのであればこれは問題があります scanf関数のような機能を持つようにしたいです生活の中で、その目的は、スキャンすることですキーボードからのユーザーの入力そしてそのようにし、空白を埋めます話す、つまり、Xのような変数を与えます値、私がされたかのためにただscanf関数xを渡すには、あなたが最後の論理を考慮すれば、週、scanf関数は、それが望んでいるものは何でも行うことができます xのコピーで、それができませんでした私たちは与えない限り、永久にXを変更宝の地図のscanf、いわば、 xはスポットをマークどこで、これにより、私たちはそのようにxのアドレスを渡します scanf関数は、そこに行くと、実際に変更することができます xの値。だから確かに、すべてのこのプログラムがないこと私は私の元に、scanfの0を加えた場合 5メートルディレクトリ、scanfの0を行い、ドットスラッシュscanf関数、数 50 50、感謝をしてください。だから、すべてが面白いではありませんしかし、実際に何が起こっていますすぐに私が呼んでいることです scanf関数ここで、xの値恒久的に変更されています。さて、これは素敵なようで、良い、と実際には、それ私たちは本当に必要はありませんように思えますもうまったくCS50ライブラリ。たとえば、のは、実行してみましょうここで、この一回以上。私は第二のためにそれを再び開くましょう。番号をお願いしてみましょうと代わりに前のように50というのは、ちょうどノーと言うてみましょう。 [OK]を、それは少し奇妙なことです。 OK。そして、ここではいくつかのナンセンス。だから、していないようです誤った状況を扱います。だから我々はスタートを最小限にする必要がありますいくつかのエラーチェックを追加ユーザーが持っていることを確認します 50のような実際の数で入力し、明らかに単語を入力するため、問題が検出されません、しかし、それはおそらくする必要があります。それでは、それはだ、このバージョンを見てみましょう GetStringを再実装する私の試み。 scanf関数は、このすべてを持っている場合に組み込まれた機能、なぜ私たちは、これらに手を染めてきました GetStringなどの補助輪？さて、ここでは、おそらく自分で GetStringの簡易版これにより一週間前、私は言ったかもしれません、私は文字列を与えるとバッファを呼び出します。今日、私はちょうど開始するつもりです char型のスターを言って、これは、リコール、それだけでは同義です。それは恐ろしい見えますが、それはですまったく同じこと。だから、私はバッファと呼ばれる変数を与えますそれは文字列を格納するために起こっています、ユーザー文字列をしてください教えて、し、その後、直前のように、それでは、このレッスンを借りてみましょうのscanf ％sのこの時間と、バッファに渡します。さて、迅速な健全性チェック。なぜ私は言っていないですアンパサンドは、この時間をバッファ？前の例から推測します。聴衆：チャースターはポインタです。 DAVIDマラン：その通り、この時、文字のため星は、既にポインタ、アドレスでありますそこにいるその星の定義によって。やscanfがアドレスを想定している場合、それだけでバッファに渡すのに十分です。私はアンパサンドバッファを言う必要はありません。好奇心のために、あなたは可能性このような何かを。それは別の意味を持っているでしょう。これは、あなたのポインタを与えるだろう実際にポインタへ C言語ではなく、ために有効なものそれでは、それをシンプルに維持させますそして、一貫性のある話を続けます。私は渡すつもりです緩衝液およびそれが正しいのです。問題は、しかし、このです。私が先に行くと、これを実行してみましょうそれをコンパイル後のプログラム。 scanfの1を作ります。くそそれは、私のコンパイラの私のエラーをキャッチ。私は一秒を与えます。クラン。それでは、scanfの-1.Cを言ってみましょう。 OK。そうしよう。それが必要。 CS50のIDを有し、様々な構成設定それは自分自身に対してあなたを守ります。私はによってそれらを無効にするために必要な手動でこの時間を打ち鳴らすを実行しています。だから、文字列下さい。私が先に行くと入力するつもりです私の好きなハロー世界インチヌル、[OK]をクリックします。それは私が入力した内容ではありません。だから、の指標です何かが間違っています。私が先に行くと入力してみましょう本当に長い文字列です。ヌルのためのおかげで、私は知りません場合、私はそれをクラッシュできるようにするつもりです。のは少しコピーをしてみましょう貼り付け、このことができますかどうかを確認します。ただ、このたくさんのを貼り付けます。それは間違いなく大きいです通常よりも文字列。ちょうど実際にそれを書いてみましょう。いいえ。畜生。コマンドが見つかりません。だから、無関係なのです。私が貼り付けられているためです一部の不正な文字、これが判明仕事に行くされていません。それでは、もう一度、これを試してみましょう、ので、我々は実際にそれをクラッシュ場合には、より楽しいです。それでは、これを入力してみましょう、今、私はよ本当に長い文字列をコピーしようとしてそして今、我々場合を見てみましょうこの事をクラッシュさせることができます。私はスペースを省略し、注意してください新しい行やセミコロンそして、すべてのファンキーな文字。入力します。そして今、ネットワークが遅いだけです。私は明らかに、長すぎるコマンド+ Vを押し続けます。畜生！コマンドが見つかりません。 OK。まあ、ポイントがありますそれにもかかわらず、以下の通りです。だから、実際に何が起こっているのかこの宣言でのライン16上の文字スターバッファの？だから私は何を取得しています私はポインタを宣言するとき？私が得ているすべては、4バイトの値であり、バッファと呼ばれるが、その中に何が現時点では？それだけでいくつかのゴミ値です。いつでもあるので、あなたは変数を宣言 C言語で、それは単にいくつかのゴミ値です、我々はに開始していますこの現実を超える旅。今、私はscanf関数を教えたときに、このアドレスに行きますとにどのようなユーザータイプを置きます。ユーザーがハローであれば世界は、よく、どこに私がそれを置くのですか？バッファは、ガベージ値です。だから、一種の矢印のようなものですそれがどこに知っている指しています。多分それは向いています右ここで私の記憶です。そしてそうするときにユーザーハロー世界で種類、プログラムは入れしようとします文字列のhello worldバックスラッシュ0 メモリのチャンクインチしかし、高い確率ではなく、明確ではない100％の確率、次いで、コンピュータは、クラッシュしようとしていますプログラムこれではありませんので、メモリ私は触れないように許可する必要があります。だから要するに、このプログラムがありますまさにその理由で欠陥。私は基本的に何をやっていませんよ？どのような手順私は同じように、省略されています我々はBinkyの最初の例では省略しましたか？うん？対象：メモリの割り当て？ DAVIDマラン：メモリの割り当て。私は実際に割り当てられていませんその文字列の任意のメモリ。だから我々はいくつかの方法でこの問題を解決することができます。一、私たちはそれをシンプルに保つことができます実際には、今あなたがしていますボケを見に開始する予定何の間の行の配列は、文字列が何であるか、何Aであります char型の星は、文字のどのような配列でありますです。ここで第二の例を示します文字列との通知を含みますすべての私はライン上に行ってきました 16の代わりにというのが、ありますそのバッファは、charになるだろう星、メモリのチャンクへのポインタ、私は非常に積極的に提供するつもりです自分の16文字のバッファ、実際には、あなたが精通している場合用語のバッファリングと、おそらく、ビデオの世界から、ビデオがバッファリング、バッファリングであり、バッファリング。さて、ここでの接続は何ですか？まあ、YouTubeの内部およびビデオプレーヤーの内部一般的に配列ですそれが16より大きいです。それは、サイズ1の配列であるかもしれませんメガバイト、多分10メガバイト、その配列にブラウザを行いますバイトの全体の束をダウンロードし、のメガバイトの全体の束ビデオ、ビデオプレーヤー、 YouTubeのか誰だ、開始その配列からバイトを読み込みます、あなたが見るといつでもワードバッファリング、バッファリング、それはプレイヤーが持っている意味しますその配列の末尾に頂いております。ネットワークは、それがない持っているように遅いですより多くのバイトの配列を再充填そのため、あなたはビットの外出しますユーザに表示します。それでバッファはaptの用語は、ここにありますそれはちょうど、アレイ、メモリの塊です。そして、これはそれを修正しますそれが判明したため、あなたがあるかのように配列を扱うことができること彼らも、バッファが、アドレスでありますそれはだ、ただの記号であります文字のシーケンス、バッファ、それは私のために便利です、プログラマー、あなたの周りにその名前を渡すことができますそれはであるかのようにポインタとして、それにもかかわらずチャンクのアドレスでした 16文字のメモリー。それは言うことですので、私は渡すことができます scanfのまさにその単語そして今、私はこのプログラムを作る場合は、、scanf関数2、ドットスラッシュscanfの2を作りますそして、のHello Worldを入力し、、そのtime--を入力してくださいうーん、何が起こったのか？文字列下さい。私は間違って何をしましたか？こんにちは、バッファ。こんにちは世界。ああ、私はそれがやっているか知っています。 OK。だから、最大読んでいます最初のスペースまで。それでは、ちょっとカンニングしましょうと私はちょうど何かを入力したいと言います本当に長いこれは長文であるようにそれは、1つ、2つ、3つ、4つ、5です 6、7、8、9、 10、11、12、13、14、15、16。 OK。それは確かに長い文です。したがって、この文はあります 16文字より長いですそして私は、Enterキーを押したとき何が起こるだろうか？さて、この場合、話、私は宣言していたバッファ実際には配列であることに行く準備ができて16文字で。そのように、一つ、二つ、三つ、四つ、五つ、六つ、 7個、8個、9、10、11、12、13、14、 15、16。だから16文字、そして今、ときに私このような何かで読ん長いです文、何が起こるために起こっていることです私はこれで読むつもりだということは、長いです S-E-N-T-E-N-C-E、文。だから、これは意図的です私は悪いことでは超えて書き込みを続けます私の配列の境界、私のバッファの境界を越えて。私は幸運を得るとプログラムができました気に走行を続けるとしません、一般的に、これを話します確かに私のプログラムがクラッシュします、そしてそれは私のバグですコード私が足を踏み入れた瞬間境界を越えてその配列の、私のためそれはだかどうかを知りません必ずしもクラッシュに行きますまたは私はちょうど幸運取得するつもりだ場合。だから、これはであるため問題ですこの場合は、それが動作するようには思えませんとのにもかかわらず、ここで運命を誘惑しましょう IDEはかなり耐えているようです of-- そうしよう。最後に。だから私はこれを見ることができる唯一の人です。だから、僕は楽しいタイピングがたくさんありました本当に長い実際のフレーズアウトそれは確かに超えていること 16バイト、私のためこのクレイジーな長い複数行で入力フレーズ、次に何が起こったのかがわかります。プログラムは、それを印刷してみましたして、セグメンテーションフォールトを得ましたそして、セグメンテーションフォールトがあるときこのような何かが起こりますおよびオペレーティング・システムは述べていますいいえ、そのメモリに触れることができません。私たちは殺すつもりです完全プログラム。だから、これは問題と思われます。私はプログラムすることによりを向上させました少なくともいくつかのメモリを持っています、これは閉じ込めるように思われます取得への関数のGetString いくつかの有限長16の文字列。だから、長くサポートしたい場合は 16文字以上の文章、職業はなんですか？さて、あなたは増やすことができます 32に、このバッファのサイズまたはその種の短いようです。なぜ私たちはしないでくださいそれ千しかし押し戻します。直感の応答は何ですかちょうどすることによってこの問題を回避すること千文字のような、大きな私のバッファ？このようにはgetString実装することにより。ここで良いか悪いかは何ですか？うん？聴衆：あなたは多くをバインドする場合スペースの、あなたはそれを使用しないでください、あなたはそのスペースを再割り当てすることはできません。 DAVIDマラン：もちろんです。あなたがいないかのように限り無駄です実際にそれらのバイトの900を必要としますまだあなたが求めていますとにかく、合計1,000、あなただけのより多くのメモリを消費していますあなたがする必要があるよりも、ユーザーのコンピュータ、の、すべての後に、いくつかのあなたは既に遭遇しましたあなたがしていることを生活の中でプログラムの多くを実行していますそして、彼らは、多くのメモリを食べていますこれは実際にパフォーマンスに影響を与える可能性がユーザの経験コンピューター上で。だから、怠惰な解決策のようなものです確かに、逆に、それだけでなく、無駄だし、何の問題まだ私は私のバッファを行う場合であっても、残っています千？うん？観客：文字列の長さが1001です。 DAVIDマラン：その通り。あなたの文字列の長さが1001である場合には、あなたは正確に同じ問題を抱えています、そして、私の議論によって、私は希望ちょうどその2000行い、しかし、あなたはで知りませんそれがどうあるべきか、大きな前進、まだ、私は私のプログラムをコンパイルする必要があります人々は使用せ前とダウンロードそれ。だから、これはまさにの一種でありますスタッフCS50ライブラリ試行しますで私たちを助け、私たちは一目よします基本となる実装の一部でここでは、これはCS50ドットC.です CS50 IDEにされていたファイルですあなたが使用してきたこれらのすべての週。これは、事前にコンパイルだとあなたはしました自動的にそれを使用して持っていることの本質的打ち鳴らすとダッシュのL CS50フラグ、しかし私は、のすべてを下にスクロールした場合これらの機能は、ここでのGetStringです、ちょうどあなた与えるために何が起こっているの味、それでは、簡単に見てみましょう相対的な複雑。それは超ロングではありません機能が、我々はしませんでしたすべてのハードについて考える必要がありますどのように文字列を得ることについて移動します。だからここに私のバッファと私です明らかにNULLに初期化します。これは、もちろん、あります char型の星と同じこと、私はで決めました CS50ライブラリを実装我々がしようとしている場合に完全に動的であること、私は、どのように大きな事前に知っていません文字列のユーザーが取得したいとしています。だから私は開始するつもりですちょうど空の文字列私はできるだけ多くを構築するつもりですメモリ私は、ユーザーの文字列に合わせて必要があるとして、私は持っていない場合十分、私がお願いするつもりですより多くのメモリは、オペレーティング・システム。私は彼らの文字列を移動するつもりですメモリの大きなチャンクへ私は解放または解放するつもりですメモリの不十分大きな塊そして私達はちょうどつもりです反復これを実行します。だからチラッ、ここだけの変数ですこれで私が追跡するつもりです私のバッファの容量の。私はどのように多くのバイトを収めることができますか？ここで、変数nですこれは私が維持するつもりです実際にあるバイト数のトラックバッファまたはユーザが入力したこと。あなたは、この前に見ていないしている場合 int型のような、その変数を指定することができます名前が示唆するように、署名され、それは非負だし、なぜだろうことを意味私が今までに指定を気にしたいです intはint型だけではないこと、それはunsigned int型ですか？これは、負でない整数です。 [聞こえない]とはどういう意味ですか？観客：それは量を記述しています [聞き取れない]ことができるメモリの。 DAVIDマラン：うん。私は、符号なしと言うのであれば、これは実際にありますあなたに余分なメモリの1ビットを与えますそれは一種の愚かなようだが、あなたの場合追加のメモリの1ビットを持っていることあなたが二倍のを持っていることを意味しあなたが表現できる値は、それは、0または1であることができるからです。だから、デフォルトで、int型は、およそすることができます負の20億のすべての方法正の20億まで。これらは大きな範囲ですが、それはまだ種類の無駄ですあなただけ心配している場合ただ直感的なサイズ、非負でなければなりませんか正または0、よくして、なぜあなたは20億を無駄にしています負の数の可能な値あなたがそれらを使用するつもりはありませんしている場合は？符号なしと言ってだから、今、私のINTができます 0とおよそ40億の間であること。だからここに理由のためだけでint型のCです私たちは今のように得ることはありませんそれは代わりにint型だ理由チャーのが、ここにあります何が起こっているの要旨あなたの、そしていくつかの例えば、使用している場合があります、でもPSET 4でのfgetc関数またはその後、我々はそれを参照してくださいよ再び問題に5を設定し、 fgetc関数が原因の名前としていいです種類の、一種のarcanely示唆しています、その関数です、文字を取得しますので、根本的に異なる何私たちはのGetStringでやっていることについて私たちが使用していないです同じ方法でのscanf。私達はちょうどステップバイステップに沿って忍び寄るされています何を介してユーザが入力した中で、私たちは常に1を割り当てることができるため、 char型、そして私たちは常に安全にすることができます一度に一つの文字を見て、マジックはここに起こることを開始します。私はまでスクロールするつもりですこの関数の途中ただ簡単にこの機能を導入します。多くありますように malloc関数は、あります realloc関数のrealloc あなたは、メモリのチャンクを再割り当てすることができますそれが大きくなったり小さくします。だから、長い話短いとと今日は私の手の波、その何のGetStringを知っていますやっている、それは一種ですで魔法の成長またはユーザーとしてのバッファを縮小彼または彼女の文字列内の型。もしそうであれば、ユーザーの種類短い文字列、このコード十分なだけを割り当て文字列に合わせてメモリ。ユーザーが入力を続ける場合私は何度も何度もそれをやったとしてそして再び、よく、場合バッファの最初に、この大きなプログラムはに、実現します私は宇宙の外だけど、ちょっと待って、それは倍増するだろうバッファのサイズそして、バッファのサイズを2倍そして、倍増を実行するコード、我々はここでそれを見れば、それはですちょうどこの賢いワンライナー。あなたはこの構文を見たことがない可能性があります前、しかし、あなたは星が等しいと言えば、これは同じものです容量2倍を言って。だから、ちょうど倍増し続けますバッファの容量して、与えることのreallocを伝えます自身その多くのメモリ。さて、余談ですが、そこのようにその他の機能は、ここにあります我々はすべての詳細に見ていないということ GetIntでに表示する以外に、私たちは、GetIntで中のGetStringを使用しています。我々はそれがないことを確認してくださいヌル、これは、リコール、その特別な値です何かが間違っていたことを意味します。私たちは、メモリが不足しています。より良いことを確認してください。そして、我々はセンチネル値を返します。しかし、私はのようなコメントに従いますなぜ、我々はscanf関数のこのいとこを使用 sscanf関数と呼ばれ、それが判明そのsscanf関数、または文字列のscanf、あなたがその行を見てみましょうユーザーは、で入力し、あなたを聞かせています基本的にそれを分析し、私は何をここで行って、私はsscanf関数を言っているが、ユーザーが持っているどのような分析入力し、確認してください％の私を作ります、そこでの整数であり、私たちはしませんあります正確な理由今日に入ります一言で言えば％のここでC、それが可能に私たちユーザーが入力したかどうかを検出します番号の後に偽のものです。だから理由はGetIntでとのGetString 再試行、再試行するように指示、再試行理由のすべてであります私たちが書いたそのコード、それは種類のユーザーの入力を見ています確認することで、それは完全に数値ですまたはそれは、実際の浮動ですポイント値等どのような値に応じてあなたが使用している機能。やれやれ。 OK。それは一口ましたしかし、ここでのポイントは、私達が持っていた理由はこれらの補助輪のなぜなら最低レベルであり、それだけで非常に多くのものがあります我々が望んでいたことを間違って行くことができます先制処理します確かにそれらのものでクラスの初期の数週間、今PSET 4とPSET 5とし、越えてあなたはそれがわたしの多くはでていることがわかりますあなたも、あなたはより多くのことが可能です問題のこれらの種類を解決します自分自身。 GetStringまたはGetIntでのご質問？うん？聴衆：なぜあなたは倍増しますバッファの容量だけではなく増加それ正確な量だけ？ DAVIDマラン：良い質問。なぜ我々は能力を倍増します対照的に、バッファのそれを増加させることにいくつかの定数値で？これは、設計上の決定でした。私達はちょうどそれがする傾向があるためと判断しました時間的に高価な少し依頼することオペレーティング・システムメモリのために、私たちはしませんでしたなってしまうしたいです大きな文字列の状況我々は求めていたこと何度も何度もOS そして、何度も何度もでメモリの矢継ぎ早。だから我々は単に多少、決定しました任意に我々は合理的に願って、それは、あなたが、してみましょう知っています先に自分の取得しようとしますちょうどようにそれを倍に保ちます我々は倍の量を最小限に抑えます我々はmalloc関数を呼び出す必要がありますか reallocのが、総合判定知っての不存在下で呼び出しますどのユーザーが入力する必要がある場合があります。どちらの方法は、議論の余地がある可能性があります。間違いなく良いです。それでは、カップルを見てみましょうメモリの他の副作用の、間違って行くことができるものおよびツールのことができます。ミスのこれらの種類をキャッチするために使用します。それにもかかわらず、あなたのすべてが判明 check50は、同じくらいあなたに言っていませんバギーを書いています 1週間以降のコード、すべてcheck50のテストがある場合でも、渡され、場合でも、あなたとあなたのTF その超自信を持っています意図したとおりに、あなたのコードが動作します。あなたのコードにバグがされていますかあなたのすべてに欠陥、 CS50ライブラリを使用して、メモリリークされています。あなたは、オペレーティングシステムを求めてきましたプログラムのほとんどのメモリのためのあなたが書いたが、あなたはしました実際にそれをバック与えられたことはありません。あなたはのGetStringと呼ばれてきました GetIntでとはGetFloatと、しかしのGetStringで、あなたはしました unGetStringまたは与えると呼ばれることはありません文字列バックなどが、私たちは見てきました GetStringは、メモリを割り当てないこと malloc関数の方法またはこれによりますちょうどである関数のrealloc、精神が非常に類似し、まだ、我々がしてきましたオペレーティングシステムに依頼メモリとメモリ、何度も何度もしかし、それをバック与えることはありません。さて、余談として、それはことが判明プログラムは、メモリのすべてを終了したとき自動的に解放されます。だから、大きな問題となっていません。それは破ることはないだろう IDEまたは遅くします、しかし、プログラムが行うとき一般に、メモリリークが発生そして、彼らは長い時間のために実行しています。あなたは愚かな少しを見てきた場合 MacのOSや砂時計のビーチボールそれは一種のだWindows上で減速や思考や思考または本当に開始クロールに遅くします、それは非常に可能性があることができメモリリークの結果。書いたプログラマーあなたが使用しているソフトウェアメモリは、オペレーティングシステムに依頼数分ごと、時間ごと。しかし、あなたが実行している場合それはだ場合であっても、ソフトウェア、お使いのコンピュータに最小化最後の数時間から数日のために、あなたはより多くを求めることがありますメモリと、実際にそれを使用することはありませんので、あなたのコードがあること、または可能性がありますプログラムは、メモリリーク可能性がありますあなたがメモリリークが発生し始めた場合、他のプログラムのための少ないメモリがあると、効果はですすべてが遅くなります。さて、これは断然の1であります最も残虐なプログラムあなたは機会を持つことになります CS50で実行する限り、その出力はよりもさらに難解であるとして、打ち鳴らすのか、のをするか、またはコマンドのいずれか私たちは前に実行したラインプログラムが、ありがたいことに、その出力に埋め込まれましたいくつかの超便利なヒントでありますいずれかのpset 4のために有用であろうまたは確かに5をPSET。だから、valgrindのツールですそれを見るために使用することができあなたのプログラムでメモリリークのため。これは、実行するのは比較的簡単です。あなたも、valgrindの、次に実行しますそれは少し冗長ですけれども、ダッシュダッシュリークチェックドットその後完全に等しく、スラッシュとあなたのプログラムの名前。だから、valgrindのは、あなたのプログラムを実行しますそしてあなたのプログラムの最後にそれが終了する前に実行し、あなたに別のプロンプトを与え、それはあなたを分析するために起こっていますプログラムは実行されている間あなたが漏れたことを伝えますいっその任意のメモリと、あなたはそのメモリに触れませんでしたあなたに属していたのですか？それはすべてをキャッチすることはできませんが、それはですほとんどのものをキャッチでかなり良いです。だからここに私の持つランの例を示します。このプログラムは、実行valgrindのを持ちます、呼ばれるプログラムにメモリ、私は行きますよある行を強調表示します最終的に私たちに興味のあります。だから、さらに気晴らしがあります私は、スライドから削除したこと。しかしちょうど何これを見てみましょうプログラムは、私たちに伝えることが可能です。それは私たちのことを伝えることが可能ですサイズ4の無効な書き込みなどがあります。つまり、あなたがメモリに触れる場合には、メモリの特に4バイトあなたが持っているべきではないと、 valgrindのはあなたにそれを伝えることができます。サイズ4の不正な書き込み。あなたは4バイトに触れましたあなたが持っているべきではないこと。あなたはそれをどこで行うのですか？これは美しさです。どこメモリドットC線21がありますめちゃくちゃ、それは便利です理由です。多くのGDBのように、それは助けることができます実際のエラーであなたをポイントします。さて、これはもう少しです冗長な、そうでない場合は混乱を招きます。 1ブロック内の40バイトは間違いなくあります 1の損失レコード1で失われました。どういう意味ですか？まあ、それはちょうどあなたが尋ねたことを意味します 40バイトと、あなたはそれを返したことはありません。あなたは、malloc関数と呼ばれるか、と呼ばれます GetStringおよびオペレーティングシステムあなたに40バイトを与えたが、あなたは決して解放されたか、そのメモリを解放し、かつ公正であることを、我々は示したことがありませんあなたはどのようにメモリをお返しします。判明スーパーがありますシンプルな機能は無料と呼ばれます。一つの引数、ものを取りあなたは、解放するかお返ししたいですしかし、40バイト、明らかに、このプログラムでラインで失われていますメモリドットcの20。それでは、このプログラムを見てみましょう。これは、スーパー無用です。それが唯一の実証しますこの特定のエラー。それでは、見てみましょう。ここでは、メインとメインで、気づく、呼び出し関数をfと呼ばれ、その後、戻ります。だから、すべてが面白くありません。 fは何をするのでしょうか？私はプロトタイプを気にしませんでした注意してください。私は、コードを維持したいですできるだけ最小限。だから私は、メインの上にFを入れて、それは確かに、大丈夫です、このような短いプログラムのため。だから、fは何も返していません。何かを取るが、それはこれを実行しません。それは多くのと同じように、宣言します Binkyの例では、起こっているXと呼ばれるポインタ int型のアドレスを格納します。だから、左側です。英語では、何があります右辺はやって？誰ですか？これは私たちのために何をしているのですか？うん？聴衆：[聞こえません] 回int型のサイズである10倍[聞こえません] DAVIDマラン：良いと私はまとめてみましょう。だから10の整数のための十分なスペースを割り当てますまたは10、int型のサイズは何ですか、それがされている4バイトなので、10回4 40、私はきたように右側ハイライトされた私に40バイトを与えるとあります最初のバイトのアドレスを格納 Xへ。そして今、最後に、ここどこですこのプログラムは、バグが、何そのロジックに基づいて、ライン21と間違って？何がライン21と間違っていますか？うん？聴衆：あなたがすることはできません Xへのインデックス[聞こえません]。 DAVIDマラン：うん。私はそのようなXのインデックスいけません。だから構文的に、それは大丈夫です。何すてきなのははるかにあなたのように、あります配列の名前を扱うことができますそれは同様に、ポインタだかのようにそれはだかのように、あなたはポインタを扱うことができますアレイと、私は構文的にすることができます Xブラケット何かを言う、XブラケットI、しかし10には問題があります。なぜ？観客：それは内部にはありませんので。 DAVIDマラン：それはありませんメモリのチャンク内部。最大値は、私は何をする必要がありますこれらの角括弧内に入れてこと？ 9、0〜9。ゼロのインデックス作成のため。だから、0〜9は大丈夫だと思います。ブラケット10が良好でないとしかし、しかし毎回思い出します私はCS50 IDEを作ってみるように見えます偽の値を入力してクラッシュ、それは常に、協力しません実際に、あなたのことが多いです幸運を得るという理由だけでオペレーティングシステムがありません予告ほんの少しあなたメモリーの一部のチャンクを渡し、あなたが技術的に内滞在理由あなたのセグメントが、よりその上オペレーティング・システムのクラスで、ので、このような何か非常に簡単に検出されない行くことができます。あなたのプログラムがクラッシュするつもりはありませんです一貫多分一度しばらくインチそしてそうのはvalgrindのを試してみましょうこのため、ここでの上ここで、我々は圧倒されるだろう出力によって一瞬。だから、メモリvalgrindのリークチェックを行いますフルドットスラッシュメモリに等しいです。私は約束する理由そして、ここですこれは圧倒だろう。ここでvalgrindの、ここで何だ何ですプログラマ、何年かago- それは良いでしょうことを決めました出力は次のようにするため。それでは、この感覚を作ってみましょう。左側のだからすべての方法正当な理由なくするための側面プログラムのプロセスIDであります私たちは、一意の識別子を実行プログラムのため、私たちはただ走りました。我々は、からそれを削除しましたスライドが、そこここでいくつかの有用な情報があります。のは非常にトップまでスクロールしてみましょう。私たちが始めたのはここです。だから、すべてがはるかに出力されないのです。ここでは、無効な書き込みですライン21上のサイズ4の。まあ、ライン21は何でしたか？ 21行目は、正確でしたこの、それは理にかなっています私は正当にいること私はだから4バイトを書きますこの整数を入れしようとすると、これは何もすることができ、それだけであることを起こりますゼロが、私はしようとしています場所でそれを置くためにそれは私に属していません。また、ダウンここでは、1で40バイトブロックは、間違いなく、レコード1に失われます。私はmalloc関数を呼び出すときからですここで、私が実際にメモリを解放することはありません。では、どのように我々はこの問題を解決することができますか？私が先に行くと少しより安全であるとしますそしてそこに9を行うと、ここで無料のxをさせて頂きます。これは、今日のための新しい機能です。私は今、メモリドットスラッシュを作る再実行すると、、のは、再びその上でValgrindは実行してみましょう私のウィンドウを最大化し、Enterキーを押します。さて、それは良いことです。彼らは良いニュースを埋めますこの出力のすべてインチすべてのヒープブロックは自由でした。私たちは、どのようなヒープに戻ってきますですが、漏れはできません。だから、これはただのですあなたのツールキットのためのツールこれであなたは、に開始することができます今そのようなエラーを見つけます。しかし、それでは、何を見てみましょうもっと間違ってここに行くことができます。今までの移行をしてみましょう実際に問題を解決します。余談として、これが緩和する場合混乱や緊張を少し、これは今面白いです。うん。これはかなり良いです。ポインタであるためアドレスとアドレス慣例により、一般的に進で書かれました。ハ、ハ、これは今面白いです。とにかく、今してみましょう実際に問題を解決します。これは、超となっていますこれまでの超低レベル、私たちは実際に便利を行うことができますこれらの低レベルの詳細との事。だから我々は数週間を導入しました前配列の概念。配列は良かったので、それは私たちのコードをクリーンアップするのは難しいです私たちが書きたい場合のため複数の学生とプログラムまたは複数の名前と家と寮や大学とすべてのこと、我々はより多くのすべてを記憶することができますきれいに配列の内部。しかし、一つの欠点を提案配列のこれまで。あなたはそれを自分で苦しんでいませんでした場合でも、プログラムで、ただ本能的に、悪いことは何ですか配列については、おそらく？私はいくつかの雑音が聞こえます。観客：それは難しいですサイズを変更します。 DAVIDマラン：それは難しいですサイズを変更します。あなたは、サイズを変更することはできません配列の、実際には、それ自体 Cであなたは他の配列を割り当てることができ、古いものからすべてを移動します新しい、およびへいくつかの余分なスペースを持って、それはようではありません JavaやPythonのような言語または他の任意の数言語あなたのいくつかのどこに精通しているかもしれません物事を追加し続けることができます配列の最後にうんざり。あなたはの配列を持っている場合そのサイズでサイズ6、そして、考え、以前のようなので、多くの特定のサイズのバッファを有しますあなたは、ゲートの外に推測する必要がどのようなサイズ、あなたはそれになりたいですか？あなたが大きすぎる推測した場合、あなたは、スペースを無駄にしています。あなたが小さすぎる推測した場合、少なくとも、そのデータを格納することはできませんより多くの作業をせずに。だから、今日、ポインタのおかげで、我々はできます一緒に私たちの独自のカスタムステッチ開始データ構造などで実際、ここで何かありますそれがもう少し見えます一見不可解な、しかし、これは我々がリンクを呼ぶものですリスト、そしてまとめたもので、その名前の種類それ。これは、番号のリストです、またはでこの場合、番号のリスト、それが何のリストではなく、可能性それは、一緒に矢印によって連結されたですちょうど推測を取りますどの技術に我々ができるようにするつもりされています一緒にステッチするために、ソートの糸でポップコーンのように、リンクされたリストはここに長方形？その数字？基本となる言語機能とは何ですか？聴衆：ポインタ。 DAVIDマラン：ポインタ。そこでここではこれらの矢印のそれぞれが表しますポインタやアドレスだけ。だから、他の言葉で、私がしたい場合番号のリストを格納します、私がしたい場合、私はそれを格納することはできません成長し、縮小する機能配列内の私のデータ構造。だから私は少しを持っている必要がありますより洗練され、しかし、このことに気づきます画像種類の示唆あなたはほんの少しのスレッドを持っている場合に一緒にすべてを接続し、おそらく、スペースを作るために、その難しいことではありませんこれらの長方形の二つの間にありますそれらのノードまたは2つ、私たちは始めましょうとして新しいノードに入れ、それらを呼び出すと、して、いくつかの新しいスレッドと、ちょうど一緒に3つのノードを捨てます、最初の、最後の、そして1 あなただけの途中に挿入していること。そして実際にリンクされたリスト、配列とは異なり、動的です。それは、成長することができ、それがすることができます縮小し、あなたはしないでくださいどのように、事前に知っているか気にする必要があります多くのデータは、あなたが保存することになるだろう、しかし、それは我々が少しでなければならない判明しますこれを実装する方法については慎重に。したがって、最初の我々は実装方法考えてみましょうこれらの小さな長方形の一つ。これは、int型を実装するのは簡単です。あなたはちょうどそのint型nと言いますあなたはint型のために4バイトを取得し、しかし、どのように私はint型を得るのですか、それを呼び出すnは、して、ポインタは、のは次のことを呼びましょう。我々は、これらを呼び出すことができます私たちが望むものを何でも私は、カスタムデータ構造を必要としています。うん？聴衆：アンパサンド[聞こえません]。 DAVIDマラン：だから私たちはアンパサンドに使用します。潜在的にノードのアドレスを取得します。しかし、我々は別のものを必要とします順序でCの特徴私に作成する能力を与えるためにこのカスタム四角形、このカスタムメモリ内の変数あなたがする場合は、。聴衆：構造体。 DAVIDマラン：構造体。先週から思い出して、我々が導入しました構造体、この比較的単純なキーワードそれは、私たちはこのようなものを行うことができます。 Cは、データが付属していませんでした構造は、学生と呼ばれます。これは、int型とfloatと文字とが付属していますこのような、それは学生が付属していません、私たちは、生徒データ型を作成することができ、この構文を使用して学生の構造、ここに。そして、あなたは何度も何度もこれを見ることができます。だから、心配しないでくださいキーワードを記憶します、しかし、重要なのキーワードがあります我々が言っていることだけで事実構造体し、我々はそれを学生と呼ばれ、内部学生の名前と家でしたまたは寮など。そして今、今日、のはこのことを提案してみましょう。私はいくつかの単語を追加しましたが、私はしたい場合だこの四角形を実装します int型との両方を持ってポインタ、あなたは私は何を知っています、ノードと呼ばれる構造体を宣言するだろう。私も、その中に、と言うつもりですノード、この長方形は、int型を持っていることそして我々はそれを呼ぶnおよびそれは次のポインタを有しています。そして、これは、少し冗長ですしかし、あなたはそれについて考える場合、絵にあった矢印一瞬前にどのようなデータ型ですか？これらの矢印のそれぞれが指している場所データ構造のどのタイプか？それだけで、それ自体はint型を指していません。それはを指しています全体の長方形のものその長方形のもの、我々はノードと呼ばれ、言いました。そして、私たちは一種のに持っています再帰的にこのようなを定義ノードことを、我々は言うものとし、 nはint型と呼ばれるが含まれています次のと呼ばれ、ポインタデータ構造の種類そのポインタは明らかです構造体のノードになるだろう。だから、これはうるさく冗長ですちょうど衒学的であるために、なぜ私たちができない理由ただこれは率直に言って、これを言います、多くのより読みやすくなります読んCのためのリコールであります物事は、上から下、左から右へ。私たちは、セミコロンを得るまでそれではありませんキーワードのノードが実際に存在していること。だから我々は、この種のを持っているしたい場合データの内部循環参照構造、我々はこれを行うには、どこに私たちは、一番上にある構造体のノードを言います私たちはこれを記述する長い方法を提供します事は、その後の内部に我々は構造体のノードを言います、して、非常に最後の行に私たちが言う、すべての権利、C、方法によって、ちょうどこの全体の気を呼び出します事のノードと停止完全にキーワード構造体を使用して。だから、これはただ一種の構文的です最終的に私たちが作成することができますトリックまさにこのようなもの。私たちは今、仮定した場合、我々はできるように C言語でこのことを実現します、実際にどのように行う我々これを横断を開始？まあ、実際には、我々がしなければならないすべては、左から右に繰り返すだけ種類のノードを挿入したり、ノードを削除します私たちが好きな場所や物事を検索し、これを行うには、のは先に行くとしましょう物事もう少し本当このため、これまでの超低レベルとなっています。誰もが文字通り最初になりたいですか？ OK。アップさあ。あなたの名前は何ですか？ DAVID：デビッド。 DAVIDマラン：デビッド。始めまして。私も。大丈夫。そして、我々は数9が必要です。最初ほど良好ではない、多分。 [OK]を、数9。数17、お願いします。私は少し遠く戻りましょう。ナンバー22、してください、と方法については遠くバック私は手を見ることができればすべての光で、あるいはまったく。誰かがすぐそこにボランティアとして参加しているです。あなたが思い付くしたいですか？あなたの前腕を強制的に上がっています。 [OK]を、17。 22。 26はダウン来ています。誰にもしたいと思います forcefully--までさあ。実際のボランティア。だから非常に迅速に、もし君たち手配ができ同じように自分画面上のノード。ありがとう。そして、あなたは26になるだろう。すべての権利および迅速な導入。だから私はデビッドだとあなたもですか？ DAVID：デビッド。 DAVIDマラン：そして、あなたはありますか？ JAKE：ジェイク。 SUE：スー。 ALEX：アレックス。 RAPHAEL：ラファエル。 TAYLOR：テイラー。 DAVIDマラン：テイラー。優れています。したがって、これらは私たちのボランティアです今日のためにと先に行きますそして、そのように少しシフトちょうど先に行くと維持あなたがそうであるようにあなたの番号を保持したり、最初の兆候と左手を使用して、先に行くと、ちょうど実装これらの矢印は、ちょうど左手は文字通りあるようにあなたが指している必要があり何を指しで、そのように自分自身にいくつかの余地を与えます我々は、視覚的に、実際にあなたの腕を見ることができますポインティング、そしてあなただけ指すことができますソートのグラウンドで結構です。そこでここでは、一つのリンクリストを持っています、最初に2つ、3つ、4つ、5つのノード、私たちはこの特別なを持って気付きますだ先頭のポインタキー我々は追跡する必要があるため全長リストの何とか。彼らが残っているにもかかわらずこれらの人、右に、背中合わせにメモリで、彼らは実際にどこでもすることができますコンピュータのメモリインチだから、これらの人はかもしれませんステージ上の任意の場所に立ってそれはあまりにも長い間、彼らがしているように、大丈夫です実際にお互いを指し、しかし、物事を維持しますクリーンでシンプルな、我々はよちょうどそれらを描くことのように左から右へこれは、しかし、大規模なギャップがあるかもしれませんそれらのノード間のインチ今、私は実際にいくつかを挿入する場合新しい値は、のは先に行くと、これを実行してみましょう。私たちは今機会を持っています別のノードを選択します。 55をmallocingから始めてみましょうと言います。誰かがmalloc関数であることを気にしませんか？ [OK]を、アップに来ます。あなたの名前は何ですか？ RAINBOW：虹。 DAVIDマラン：レインボー？大丈夫。 mallocの虹。アップさあ。だから今、私たちは自問する必要がありますアルゴリズムどこに55を入れることができます。だから、私たちのすべてが知っています、明らかに、ここで彼女はおそらく我々がしようとしている場合に属し保つためにこれをソートそしてあなたたちはいずれかを取ることができれば我々が落下しないようにバックステップステージは、それは素晴らしいことです。そこで実際に、レインボー、私と一緒にここでやり直します、コンピュータとして、我々はできるようになりましたので、一度に一つの変数を参照してください。だから、これは最初のノードである場合。、彼はノードではありません注意してください彼はただのポインタですが、彼はあることが描かれている理由、それはですポインタのサイズのみではなく、それらの完全な四角形の一つ。だから私たちは、それぞれにチェックするつもりです繰り返しは9より55少ないのですか？いいえ。 17以上55以下ですか？いいえ。 22未満？ 26未満？ 34未満？そして今、明らかにレインボーは、最後に属します。だから明確にすると、何しますあなたの名前、テイラーでしたか？ TAYLOR：テイラー。 DAVIDマラン：だからテイラーの間で左手とここに虹の手、その手はに何を指すように必要このリストに55を挿入するため？私たちは何をする必要がありますか？うん？聴衆：テイラーの手左を指している必要があります。 DAVIDマラン：その通り。だから、ノードを挿入しますリストの最後に非常に単純ですので、テイラーだけ地上での代わりに、ポイントする必要がありますまたは私達はそれがnull電話しますよ、 nullが不在の一種でありますポインタまたは特別のゼロポインタ、あなたがしています左手でポイントになるだろう手レインボーして、レインボーで、あなたの場所を残しする必要があります手はおそらくポイント？ダウン。彼女の手がソートされている場合は良いではありませんここでオフ指し示すのか、いずれかの並べ替えどちら。すなわち、と考えられますごみ値、しかし、彼女はを指している場合いくつかの既知の値は、我々はよゼロまたはNULLそれを呼び出す、それは大丈夫です我々はこの中の用語を持っているので、我々はリストが完成しました知っています。だから、別のは何です比較的単純な場合？我々は5をmallocできますか？アップさあ。あなたの名前は何ですか？ TIFFANY：ティファニー。 DAVIDマラン：ごめんなさい！ TIFFANY：ティファニー。 DAVIDマラン：ティファニー。大丈夫。ティファニーは、mallocされています値5を持ちます。アップさあ。この1つは、あまりにも比較的容易だが、それでは、操作の順序を考えてみましょう。それはかなり簡単でしたテイラーと最後に。数5は、もちろん9未満でありますそのため、我々は、我々は、ティファニーのデビッド持っていますあなたの名前は何でしたか？ JAKE：ジェイク。 DAVIDマラン：ジェイク。ティファニー、ジェイク、とデビッド。誰の手が最初に更新すべきですか？何がここに何をしたいですか？カップル可能な方法は、ありますが、一つ以上の間違った方法もあります。対象：一番左から開始します。 DAVIDマラン：一番左から開始します。誰がその後、ここ一番左ですか？聴衆：ファースト。 DAVIDマラン：OK。したがって、最初から始めて、どこで行いますデビッドの手があることを更新したいですか？聴衆：5に向けて。 DAVIDマラン：OK。 5時ダビデ、ポイントまたはティファニーここで、今？聴衆：ティファニーは9を指しますか？ DAVIDマラン：パーフェクト、Binkyさんを除きます頭はちょうど種類の右側、落ちましたか？と間違って何ので、この絵は、文字通り？観客：何も指していません。 DAVIDマラン：何もありません今ジェイクを指します。我々は文字通り9孤立しました 17、私たちは文字通りましたによってので、このメモリのすべてを漏らし最初のダビデの手を更新する、それはですそれは正しくな限り罰金今ティファニーを指し、誰もが持っていない場合ジェイクの点に先見性、その後、我々が失ってしまいましたそのリストの全体。それでは、元に戻すましょう。だから、に良いことでした以上の旅行が、今度は修正してみましょう。私たちは、代わりに最初に行う必要がありますか？うん？観客：ティファニーは9を指し示す必要がありますか？ DAVIDマラン：私はできませんあなたにその近くを取得します。 9で誰を指している必要がありますか？聴衆：ティファニー。 DAVIDマラン：すべての権利。だから、ティファニーは、最初の9時にポイントする必要があります。だから、ティファニーは取る必要があります同一の値にダビデに、それはそうです一瞬のために冗長、それは、第二のために今も元気ですステップ、私たちはダビデの手を更新することができますティファニーで、次に場合を指すように私たちだけの種類のきれいな物事これはバネ状の一種であるかのように、今それは正しい挿入です。だから、優れました。だから今、私たちはほとんどがしています。それでは、最後に1を挿入してみましょう値20のような値。我々は最後に1つのボランティアををmallocことができれば？アップさあ。したがって、この1はもう少しトリッキーです。しかし、実際に、コード我々はしています書き込み、口頭ではあるが、ちょうど束を持っているようなものです今の状態であればの、右？我々は条件を持っていましたそれが属しているかどうかをチェックします最後に、多分開始。我々は、ループのいくつかの種類を必要とします途中で場所を見つけます。それでは、あなたの名前は何でそれをやらせますか？ ERIC：エリック。 DAVIDマラン：エリック？エリック。始めまして。だから我々は20を持っています。 5未満？いいえ。 9未満？いいえ。 17未満？いいえ。 OK。彼はここに属しており、あなたの名前は再びですか？ SUE：スー。 DAVIDマラン：スー。 ALEX：アレックス。 DAVIDマラン：スー、アレックス、と？ ERIC：エリック。 DAVIDマラン：エリック。誰の手が最初に更新されますする必要がありますか？者：エリック。 OK。だから、エリックのはどこを指す必要がありますか？ 22時。良い。そして今、次は何？スーはその後、エリックで指すことができますそして今、もしあなたたちだけ微細でいくつかの部屋を作ります視覚的に、今、私たちは挿入を行ってきました。それでは、今の質問を考えてみましょうが、ボランティアありがとうございました。非常によくやりました。あなたが好きな場合は、それらを維持することができます。そして、私たちは素敵な別れの贈り物の場合がありますあなたはそれぞれのストレスボールを取りたいと思います。私はちょうどこれを伝承してみましょう。だから、これをお持ち帰りは何ですか？これは驚くべきであると思われます我々は今持っているものであれば、の代替を導入そのように限定されない配列いくつかの固定サイズの配列へ。彼らは、動的に成長することができます。しかし、我々のような多くは数週間で見てきました過去には、我々は、自由のための何かを得ることはありません確かにトレードオフがここにありますように。リンクの利点とそうリストには、このダイナミズムのですか？率直に成長し、この能力、我々は、削除したかもしれません必要に応じて、我々は縮小ができます。私たちはどのような価格を払っていますか？ 2倍のスペースとして、すべての最初の。あなたが絵を見れば、もはや私は整数のリストを格納しています。私はのリストを格納しています整数プラスポインタ。だから私は、スペースの量を倍増しています。今、多分それは、ありません大した4バイト、8バイト、それは確かに追加することができます大規模なデータセットのためにアップ。別の欠点は何ですか？うん？観客：我々がする必要がありますそれらを一つ一つを通過します。 DAVIDマラン：うん。私たちはそれらを一つ一つを横断する必要があります。あなたは私たちがこのスーパーをあきらめたものを、知っています角括弧の便利な機能より適切に表記、ランダムアクセスとして知られています、私たちはジャンプできる場所個々の要素にしかし、今私はまだ持っていた場合ここに私のボランティア、私が検索する場合数22、私はできませんブラケット何か何かにジャンプします。私はずっと、リスト上で見ています直線的に私たちの検索例のように、番号22を検索します。だから我々はそこに価格を支払っているように見えます。しかし、我々はそれにもかかわらずことができます他の問題を解決します。実際には、私が紹介しましょうビジュアルだけのカップル。だから、ダウンをしてきた場合最近メイザーのダイニングホール、あなたはそれらのことを思い出しますこのようなトレーのスタック、私たちは、からこれらを借りましたクラスの前にアネンバーグ。だから、トレイのこのスタックは、しかし、代表者は、実際にはコンピュータサイエンスのデータ構造の。データ構造がありますコンピュータサイエンスの非常にうまくスタックとして知られていますまさにこの視覚的に自分自身を貸します。したがって、これらのトレイの各々ではない場合番号のような、私は望んでいたトレイが、数値を格納するために、私ここで1ダウンを置くことができ、私は、ここに別のものを置くことができ数字を積み重ね続けます互いに、そして何の上にこのことについて、潜在的に役立ちます何が含意であるということですこのデータ構造の？私は、どの番号引き出すことができます最初に最も便利？そこに置かれ、最近1。だから、これは私たちが呼ぶものですコンピュータサイエンスLIFOデータ構造。最後の、最初のうち。そして、私たちは長い間、なぜ前に表示されますそれが有用であるが、今のところかもしれません、単にプロパティを検討します。あなたが考える場合、それは一種の愚かです食堂はそれをしない方法について。彼らはトレイをきれいにするたびにと上に新鮮なものを入れて、以前クリーンを持つことができますしかし、最終的には非常に汚れて埃っぽいです一番下のトレイよろしければ決して実際にその底に取得しますスタック、あなたのためだけ新しいを入れておくと、その上にきれいなもの。同じことが起こる可能性がありますスーパーであまりにも。あなたは、ディスプレイケースを持っている場合牛乳と毎回のCVS 以上のミルクを取得します誰でも、あなただけのミルクを突き出しますすでにバックに持っており、あなたは、アップフロント新しいものを置きますあなたには、いくつかのはかなり厄介な必要があるとしていますデータ構造の終わりに、ミルク、それが底に常にだからか等価的に、それは背面に常にです。しかし、考えるための別の方法がありますデータを並べて、インスタンスのために、この。あなたが好きその一人ならアップルストアの外に整列しますときに、新しい製品が来ますアウト、あなたはおそらくしていますスタックデータを使用していません構造あなたのためある他の皆を遠ざけることになりますいくつかの新しいおもちゃを購入するために並びます。むしろ、あなたはおそらく使用していますデータ構造の種類またはシステムの種類現実の世界では？うまくいけば、それが行だ、以上正しく以上の英国のような、キュー。そしてそれは、キューでもあり判明しますコンピュータサイエンスのデータ構造、しかし、キューは非常にされてい別のプロパティ。それはLIFOではありません。最後の、最初のうち。神は禁止します。それは代わりに、FIFOです。まず最初に、インチそして、それは良いことです公正」ために確かにライニングしているとき午前中に超早起き。あなたが最初にそこに到達した場合、同様に最初に取得したいです。だからこれらのデータのすべて構造、キューとスタックその他の房、あなたが判明単にアレイと考えることができます。これは多分、配列であります固定サイズの4、それがしたいです我々だけでパイルができればちょっといいかもほぼ無限に背の高い私たちの場合、トレイその多くのトレイまたは数字を持っています。だから多分私達がしたいですここにリンクされたリストを使用し、しかし、トレードオフがあることを行っています潜在的に、我々はより多くのメモリを必要とすること、我々はもう少し時間がかかりますが、スタックの高さを制限するものではありません、メイザーの陳列ケースのような多くのスタックのサイズが制限される場合があります、そのためこれらは、設計上の決定またはあります最終的に私たちに利用可能なオプション。これらのデータとそう構造は、我々が開始しました潜在的に新しい上限を見て以前に超高速のあったものにそしてどこに残しておきます今日オフと場所我々は、に到達するために願っています水曜日に、我々はよデータを見るために開始私たちが検索できます構造ログ終了時刻のデータを介して、再び。そして、我々は、0週目に、リコール、ことを見ましたバイナリ検索や除算と一そして征服します。それは、まだ戻って、より良い来ますこの水曜日のための聖杯を思い付くことになります本当に実行されるデータ構造または理論的で一定時間、これにより、それはどのように多くの問題ではありません。何百万人や物事の十億我々は、データ構造を持っている、それは意志私たちに一定の時間がかかる、多分一歩または2ステップまたは10ステップ、しかし、ステップの一定数そのデータ構造を検索します。それは確かに聖杯になりますしかし、もっとその上で水曜日に。その後、屋を参照してください。 [音楽再生]