>> [音楽再生]
>> [ビデオ再生]
>> -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と、
しかしのGe​​tStringで、あなたはしました 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ステップ、 しかし、ステップの一定数
そのデータ構造を検索します。
それは確かに聖杯になります しかし、もっとその上で水曜日に。
その後、屋を参照してください。
>> [音楽再生]