>> DAVID J.マラン：すべての権利。
初めてにとても歓迎 クイズのCS50の死後。
私達は私達が発足しようと思いました この伝統は今年。
そして、これはチャンスとなります ウォークスルーする
クイズへのソリューションを提供しています。
そして、我々はスピードアップやベース遅くします ここでそれらの利益に。
>> あなたがしているので、それで、あなたは、おそらくここにいる あなたが持っている可能性がどのように興味を持ったり
いくつかに答えている必要があります これらの問題の。
では、なぜ我々は見ていないの 最初のこのセクションでは？
だから、文字列を取得する。
これはあなたに3つの異なるバージョンを与えた されたプログラムの、最終的には、
ユーザから文字列を取得するためのもの。
だったが、それをしたか否かは、 決定するために、あなたに残しました。
>> そして、我々は、質問0で尋ね バージョン1があるとし
コンパイルして実行。
なぜプログラムがセグメンテーション違反でしょうか？
一見すると、何か提案 理由として？
うん。
>> 観客：だから私はこれを覚えている を見ての前の例
CHAR * sおよびsのスキャンを見て、 それは、ポインタだから見て、どのように
それはあなたがスキャンした内容に影響しましたか？
それはSまたはsのアドレスですか？
>> DAVID J.マラン：わかりました。
グッド。
だから最終的に、すべての問題の原因 おそらく削減しようとしている
その変数sに。
そして、それは確かにその変数の。
その変数のデータ·タイプは それがために起こっていることを意味char *を、
文字のアドレスが含まれています。
そしてその中の洞察力はある。
これは、のアドレスが含まれているために起こっている より一般的には文字または、
の最初の文字のアドレス 文字のブロック全体。
>> しかし、漁獲量は、スキャンSという目的です 人生は、アドレスが与えられ、与えられている
書式コードは、％sのように、読み のチャンクに文字列
そのアドレスのメモリ。
しかし、誰等号の前にありませんので、 最初にそのセミコロン
コー​​ドの行、私たちは実際にないので、 でメモリを割り当て
malloc関数、それが実際になかったため、 すべての、いくつかのサイズの配列を割り当て
あなたがやっている、ユーザーのを読んでいる いくつかの完全にキーボード入力
ゴミ値、どの デフォルトでは、Sである。
だから、オッズは、あなたがあればセグメンテーション違反するつもりである そのアドレスは、ちょうどそう発生しません
あなたができる値になるように、 実際には、への書き込み。
割り当てることはないので、悪い そこにあなたの記憶。
>> そこで質問1で、我々は尋ねた、 バージョン2があるとし
コンパイルして実行。
なぜ、このプログラムでは、セグメンテーション違反でしょうか？
したがって、この1はあまりバグが。
一つだけは本当にあります 明白な方法どこにあなたができる
ここでセグメンテーションフォルトをトリガします。
そして、これはテーマ別である。
我々は、メモリにCを使っているときはいつでも、どのような あなたがセグメンテーションフォルトを誘導するために何ができる
バージョン2と？
>> 読者：あなたはでその入力を使用している場合 49よりも長いです文字列
文字。
>> DAVID J.マラン：その通りです。
あなたが何かを固定長を参照してくださいいつでも それが配列になると、あなたの
レーダーは、これは可能性があることを消灯し 問題のあるあなたがチェックしていない場合は、
配列の境界。
そして、それは、ここで問題です。
我々はまだscanf関数を使用している。
我々はまだ試しを意味し、％Sを使用している ユーザーから文字列を読み取ります。
それは、Sに読み込むことになるだろう、 この時点で、効果的である
メモリチャンクのアドレス または、同等です。
これは、配列の名前です メモリの文字数。
>> しかし、正確には、文字列を読めば つまり、49 49文字以上です
あなたは、バックスラッシュのための部屋を必要とするので、 0は、オーバーフローするつもりだ
そのバッファ。
そして、あなたは幸運を得るとすることができるかもしれません 第51文字、第52回、第53回を書く。
しかし、ある時点で、OSの いや、言おうとしています。
これは間違いなくメモリではありません あなたは、タッチすることができています。
プログラムがセグメンテーション違反しようとしている。
>> だから、、ヒューリスティックは任意のものでなければならない あなたは、固定長を持っている時間は、あなたが持っている
あなたは長さをチェックしている作る それはあなたがしようとしているが何であれの
その中に読み取ることができます。
>> 観客：だから、それを解決するには、可能性が 実際にチェックする声明を持っていた
長さ以上である 以上またはより少ない？
>> DAVID J.マラン：もちろんです。
あなただけの条件を持っている 場合には、述べています -
というか、あなたは必ずしも分からない 事前に何文字
ユーザーは、入力しようとしているので、 あなたは鶏と卵を持っている。
あなたはscanf関数でそれを中に読んだではないまで あなたはそれがどのくらい把握することができます。
しかし、その時点で、それは遅すぎる、 あなたは既ににそれを読んだので、
メモリーの一部のブロック。
余談ですが、CS50ライブラリ回避するのでそのように この問題を完全にリコール
fgetc関数を使用します。
そして、それは、一度に1つの文字を読み取り、 ことを知って、一緒に先端糞ガキなんか
場合は、文字をオーバーフローすることはできません 一度に1をお読みください。
>> キャッチのgetStringのリコールとされている 我々は常にサイズ直ししなければならないこと
メモリのチャンク、その ただ痛みです。
これは、行の多くの これを行うためのコード。
だから、別のアプローチをすることであろう 実際にいとこを使用するので、
scanf関数の、話をする。
これらの多くの亜種があります。 実際に確認機能
何文字の長さ あなたが最大限に読むかもしれない。
そして、あなたは読んでいない、指定することができます 50文字以内。
だから、別のアプローチになりますが、 大きな入力の少ない収容。
>> だから、そのバージョンを仮定し、尋ねる質問2 図3に示すようにコンパイルされて実行される。
なぜそのプログラムがセグメンテーション違反でしょうか？
したがって、この1は実際には同じです 、答えにもかかわらず、それ
少し手の込んだ見える。
私たちは、のように感じているのmallocを使用している 我々は自分自身をより多くのオプションを与えている。
そして、我々はそれを解放している 最後にメモリ。
それはまだメモリのわずか50バイトです。
だから我々は、まだ読んでみてください 51、52、1,000バイト中。
それがためにセグメンテーション違反になるだろう まったく同じ理由。
>> しかし、もう一つの理由は、あまりにもあります。
他に何がほかにリターンをのmallocできた メモリチャンクのアドレス？
これはnullを返すことができます。
そして、我々はチェックしていないので、 つまり、我々は何かをするかもしれない
ということで、別の理由で、愚かな 私たちは読み、scanf関数を伝える可能性があります
キーボードからのユーザ入力 0場所に、別名ヌル。
そして、それは、あまりにも、間違いなく意志 セグメンテーションフォルトをトリガします。
だから、クイズの目的のために、我々はだろう として、それらのいずれかを受け入れた
正当な理由。
一つは同じです。
一つは、もう少し微妙である。
>> 最後に、プログラムのに関して バージョン2を実行し、どのようにメモリを使用する、
バージョン3が異なる？
だから、何が価値があるために、我々は見た 可能性の表面上は無限の供給
これに対する答え。
そして、人々の答えの中で、我々はどのようなものだった を期待して、私たちは、他の受け入れ
物事は、いくつかの言及だった バージョン2が使用しているという事実
いわゆるスタック。
バージョン3は、ヒープを使用しています。
そして機能的には、これは本当にない 差のすべてが多くを作る。
一日の終わりに、我々はまだだ ただ、メモリの50バイトを取得。
>> しかし、それは可能な答えの一つであった 我々は見ていたことを。
あなたがクイズを得るようにはできますが、表示されます 背中のTFから、我々が行ったことを
彼らの他の議論を受け入れる 異種のメモリの使用にも。
しかし、スタックとヒープがあったであろう 一緒に行くための簡単​​な答え。
ご質問？
私はあなたにロブを与える。
>> ROBボーデン：だから問題4。
これはあなたが記入しなければならなかったものです すべてのうち、バイト数
これらの異なるタイプを用いる。
私たちが見るので、まず最初に。
32ビットアーキテクチャを前提とし、 このCS50アプライアンスのような。
についての基本的なもののため、1つの を教えてくれる32ビットアーキテクチャ、
ポインタが起こっている正確にどのように大きな アーキテクチャであっする。
>> ので、すぐに、私たちは知っている任意のポインタ 型は32ビットまたは4バイトです。
したがって、この表を見て、A ノード*がポインタ型である。
つまり、4バイトになるだろう。
構造体ノード*、それは文字通りだ ノードのスターと同じ。
そしてその結果は4バイトになるだろう。
文字列なので、似ていない まだポインタが、型定義、A
文字列だけではchar *であり、これ ポインタ型である。
だから、4バイトになるだろう。
>> したがって、これら3つはすべて4バイトです。
今、ノードと学生は 少し複雑。
そうノードと学生を見て、我​​々が表示さ 整数とポインタとしてノード。
学生2つのポインタである その中の。
だから、少なくともここに我々の場合のために、道 我々のサイズを計算してしまうことを
この構造体は単に、すべてを合計している つまり、構造体の中だ。
>> そうノードに対して、我々は整数を有する、 その4バイトです。
我々は、4バイトのポインタを有する。
だから1ノードが起こっている 8バイトを占有します。
と同様に、学生のために、我々は持っている 4バイトと別のポインタ
4バイトのポインタ。
だから、終わりになるだろう 最大8バイトであること。
そうノードと学生が8バイトです。
そして、これら3つはすべて4バイトです。
その上での質問？
はい。
>> 観客：それは64ビットになりましたか 建築、それをう
それらのすべてを倍増？
>> ROBボーデン：それはないでしょう それらのすべてを倍増。
だから、64ビットアーキテクチャ、IT、再び、 変化することを基本的な事、その
ポインタは、64ビットです。
うん。
だから、ポインタは8バイトです。
したがって、これらの4バイトであったことを 8バイトになるだろうしている。
2ポインタた学生、 まあ、今ではなるだろう
8バイト、8バイトである。
それは、16バイトをするつもりだ。
>> しかし、ノードがまだ4バイトです。
したがって、このポインタが起こっている 8バイトになります。
これは4バイトです。
だから、ノードは、起こっている 12バイトになります。
その1上の任意の他の質問？
ので、次の1、これらは HTTPステータスコード。
そして、あなたは事情を説明しなければならなかった その下で、これらのマイト
あなたに返される。
私は何人かの学生を聞いた一つの問題 持っている彼らが作るしようとしたことである
エラーは、クライアントのエンドであること。
だから我々は、要求をしようとするとき サーバに、何かが行く
私たちの最後の間違った。
しかし、一般的に、これらのコードは、 サーバから返されている。
だから我々は何が起こっているのかを把握したい 間違っていたり、そのサーバー上の権利
これらのものが返される。
では、なぜサーバーが返す可能性がある ステータスコード200？
任意の考え？
>> うん。
だから、何かについて成功裏 要求が通って行きました。
そして、彼らは返すことができるしている あなたが求めたものは何でも。
だから、すべてが大丈夫だった。
302についてはどうか？
うん。
>> 観客：サーバが探していた あなたが要求したもののために。
しかし、それはそれを見つけることができませんでした。
ように、エラーがあります。
>> ROBボーデン：だからサーバーだった あなたが何を望むかを探している。
だから、ここで見て、302見つけ、 それはそれを見つけることができた。
>> 観客：ごめんなさい。
発見は、彼らがそれを見つけたことを意味します。
申し訳ありません。
>> ROBボーデン：だから302が見つかりました。
サーバは見つけることができ あなたが何を望むか。
>> 観客：しかし、それは、それを表示していないのですか？
>> ROBボーデン：違い この302と200、それがあることである
あなたが欲しいものを知っている。
しかし、それは正確にどこではありません あなたがお聞きしたかった。
だから、302は、一般的なリダイレクトです。
だから、ページを要求した。
それは私が欲しい、ああ、知っている あなたにこの戻ります。
しかし、これは別のURLにあります。
そうねえ、あなたが実際にこれをしたい。
>> DAVID J.マラン：それは言った一枚です 私たちはあなたたちのリダイレクトを与えたことを
ヘッダー機能を使用する機能 それは、順番に、場所をプリントアウト
コロン、その後、先のURL あなたがユーザーを拒否したい。
あなたは302を見ていないにもかかわらず、 明示的にそこに、それがどのようなPHPのです
魔法のようにヘッダとして挿入します ロブが言ったまさに言って -
発見した。
その代わりに、ここに行く。
>> ROBボーデン：わかりました。
だから、403について何を禁じ？
>> 読者：私はそれがだと思う、そのサーバー 基本的にはクライアントと言っている
ホームページにアクセスすることはできません。
>> ROBボーデン：そうです。
さて、一般的な答えは、私たちはいた 期待して、ファイルのようなものです。
適切chmoddedされていません。
それはおそらくどのような状況の下での あなたがそれらを見た。
しかし、理由があることをクライアント ここに障害が発生している可能性があります。
別のステータスコードは実際にあります -
401。
したがって、これらは非常に似ています。
>> 401は、不正である。
そして403は禁止されている。
そして、あなたがそのように許可されていない独占的 あなたがログインしていない場合は、取得
しかし、ログインすると意味するかもしれない あなたが許可されていること。
しかし、あなたはすでにログインしている場合 それでも、権限を持っていません
また、禁止されている得ることができます。
だから、ログインしているし、持っていない場合 許可、禁止さでもある
あなたが得ることができるもの。
>> DAVID J.マラン：機構による これらの問題は通常、ある
サーバー上にある解決 どのコマンドを経由して？
chmodの、それがなら、確かに、アクセス権 ファイルまたはディレクトリに発行します。
>> ROBボーデン：その後404が見つかりません。
うん。
だから、302とは異なり、それは正確ではなかった場合、 あなたが求めているが、それは何を知っている場合、
あなたが欲しい、これは、それだけであります あなたが望むものは考えていません。
そして、あなたは要求していない 有効な何か。
418私は、ティーポットだと 500内部サーバ。
では、なぜあなたはそれを得るかもしれない？
>> そうセグメンテーションフォルト -
私は実際に等級を知らない このための標準。
しかし、あなたのPHPコードが何かを持っていた場合 それは、理論的には間違った可能性が
実際に、この場合には、これをセグメンテーション違反 500内部サーバーエラー、何か
サーバーのに問題がある コンフィギュレーション。
または構文エラーがあります PHPコード内。
または何か悪いことが起こっている。
>> DAVID J.マラン：私たちは、セグメンテーションフォルトを見た 少数の人々の答えの中で。
技術的に、それが起こる可能性があります。
しかし、それは、PHP、プログラムになります 実際に、他の人が書いた
segfaulted、その場合にのみ、それらの人々 めちゃくちゃとでバギーのコードを書きました
そのインタプリタだろう PHP自体がセグメンテーション違反。
500は、セグメンテーションフォルトのようなものですので、にもかかわらず、 心の中で、それはほとんど常にです
設定ファイルの問題の結果 あなたのWeb​​サーバまたは、ロブが言ったように、
あなたのような構文エラー、 引用符を閉じませんでした。
または、どこかでセミコロンを失った。
>> 読者：だからシャトルPSETのために、私 私はそれをやったときに私がクリックされたらと思います
ブラウザが、何が登場しました、 彼らは白ページと呼んだ。
しかし、それが原因のコードであった。
私はJavaScriptのだったと思いますよね？
>> ROBボーデン：うん。
>> 観客：だろうとエラー まだ出てくる？
>> ROBボーデン：だから得なかったであろう このエラーのため、すべて
Webサーバの視点から 完全に大丈夫だった。
しかし、あなたはindex.htmlに要請した。
あなたはshuttle.jsを要請 とservice.js。
そして、それは成功して戻ることができた もしそれらのもののすべてに -
200。
[OK]をクリックします。
お使いのブラウザがしようとしたときにのみです JavaScriptコードを解釈すること
それはようなものだ、待って、これではありません 有効なJavaScriptエラー。
その他のご質問は？
わかりました。
>> DAVID J.マラン：だから、次の アップは数11であった。
そして11は怖いだった 多くの人々のために。
だから、最も重要なことは、ここで注意すべき これは、確かに、としていたということでした
双方向リンクリスト。
しかし、これは昨年のと同じではありませんでした 双方向リンクリストの問題、
これはあなたに警告を与えていないこと リストは、実際には、ソートされていない可能性があります。
>> リストがソートされていないとなるように、事実 その言葉があったという事実
伝えるためにそこに意味された下線 これは実際には単純化であること
そうであったであろうものの より困難な問題
長い1。
だからここによくある間違いは、入れていることでした あなたの1に昨年のソリューション
ページャ、その後やみくもにそのコピー 正しい答えとしてダウン
別の質問に答える 精神面で似ています。
しかし、ここでは微妙 以下のとおりであった。
>> だから1、我々はノードを宣言しており、 ここで通常の方法で定義されている。
その後、我々はリストにはグローバルに定義されている ポインタはnullに初期化。
そして、明らかに、二つの機能があります 我々はここでのプロトタイプを持って、挿入
および削除します。
そして、我々はここでいくつかのサンプルコードを持っている 挿入の束を行う。
そして、我々が完了するように依頼する このような中で、以下のインサートの実装
それがリストにNを挿入する方法 一定の時間で、また下線、
でも、すでに存在する場合。
>> だから、挿入することができるという美しさ 一定の時間で、それが意味することである
あなたが挿入する必要があること 新しいノードどこ？
前へ。
だから、少なくとも、ありがたいことに、排除 必要とするように使用される例の1
コー​​ドのより一層のライン、それが行ったように 昨年とさえクラスのときに我々
この種のものを通して話 人間とSOMEとともに
口頭での擬似コード。
だからここに溶液中で、のは飛ばしてみましょう それには、Visual上を持っている
画面。
>> 我々は次のことをやっていることに注意してください。
また、他の簡素化に気付く それはだ場合でも、ということでした
既に存在しているので、これはあっても、意味 番号は、あなたができる、そこに既にある
ただやみくもに別のものを挿入する そのコピー。
そして、それは、あまりにも、であることを意図した 簡素化、あなたができるように
本当に、より多くのいくつかに焦点を合わせる 知的興味深い部分と
だけではなく、いくつかの追加のエラーチェック 限られた時間を与えられた。
>> したがって、この試料溶液中に、我々は、割り当てる 左側にポインタ
ノードへのこちら側。
今、として、そのポインタを実現 ロブは言った、唯一の32ビットです。
そして、それは実際には含まれていません あなたまでのアドレス
それにアドレスを割り当てる。
そして、我々は右側にそれを行う malloc関数を介してサイド。
善良な市民と同じように、我々はそれを確認してください ようにmalloc関数は、実際には、nullではない
我々は誤って作成しないでください ここにセグメンテーションフォルト。
あなたは、生活の中であなたをmalloc関数を使用して、いつでも ないように、NULLをチェックする必要があります
あなたは微妙なバグがあります。
>> その後、我々はして、そのヌルを初期化する Nと前後の割り当て。
そして、ここで、この場合、私は初期化さ この新しいため、ヌル前
ノードは、新しいことを行っている 私のリストの先頭。
そうであるように起こって その前に何もない。
そして、私は、基本的に追加したい による新しいノードに既存のリスト
自分自身をリストの横に等しく設定する。
しかし、私はちょうどまだいないよ。
リスト自体はすでに存在し、その場合は および少なくとも1つのノードが存在した
既に配置され、これは、リストの場合は ここに、私は私が、ここに新しいノードを挿入
ていることを確認する必要が私の元のノード 私の新しいノードに後方を指し、
これは、再び、であるので 双方向リンクリスト。
>> だから我々は、健全性チェックを行う。
既にがあるかどうリストは、NULLでない場合 そこつまたは複数のノード、
いわばその後方参照を追加します。
そして、我々が必要とする非常に最後の事 行うには、実際にはグローバルを更新している
ポイントに変数リストそのもの その新しいノードに。
うん。
>> 読者：ポインタアロー [聞こえない]ことを行い、ヌルに等しい
リストに対処するため、 リストがnullの？
>> DAVID J.マラン：いいえ。
それは単に私が積極的にされている これは私の場合は、その中で、慎重に
おそらくいくつかのノードを持つ元のリスト こことかけて私は私のを挿入しています
こっちに新しいノード、そこに起こっている こっちには何もありません。
そして、私はその考えを捕獲したい 前に設定することにより
新しいノードではnullを返します。
おそらく、私のコードが正しい場合 を挿入する他の方法はありません
この関数以外のノード、 おそらく、リストが既に持っている場合でも、
その内の1つ以上のノード、おそらく リストは、最初のノードが有するであろう
ヌル自体の前のポインタ。
>> 観客：そして、ちょうどフォローアップ。
あなたは次の等号ポインタ置く理由 リストには、ポインタを作っているされている
リストの前にそれが指しているという点で、 次の、私は推測する -
私はドント -
ただ一覧表示されます？
>> DAVID J.マラン：その通りです。
そしてそれでは、実際に2例を考えてみましょう ここでは本当に、たとえ
我々は彼らを検討します順番はありません コー​​ドと全く同じ。
しかし、これが表すハイレベルで、場合に リストは、これは32ビットである
ポインタで、最も単純なシナリオ これは、デフォルトではNULLであること。
そして、私は挿入する必要があると 番号50は、最初の数字だった。
だから私は先に行くと割り当てるつもりです 含まれているために起こっているノード、
3フィールド -
N、以前、次。
>> 私は、数50を入れるつもりです ここで、これはNになりますので。
これは、次となります。
そして、これは、前になります。
そして私は、この場合には何をしますか？
まあ、私はちょうどここに1行目をやった。
ポインタnは、nを取得します。
私は、以前、言っている ヌル取得する必要があります。
だから、これはNULLであることを行っている。
それから私は、次の言おうとしています リストを取得する予定です。
>> そして、これは単にうまく動作します。
これはnullになります。
だから私は、新しいノードの次の、言っている フィールドは、これが何であれ取得する必要があります。
だから、そこに別のヌルを置きます。
そして、最後の事 私はここでチェックしているん。
リストはNULLに等しくない場合、それ ヌルに等しいので、我々はそれをスキップ
完全に。
だから私はすべてが次のリストを取得で 絵画的になり、ポインタ、
そのような絵。
だから、1のシナリオだ。
>> そして、あなたが知っ求めていた1 特にこのような状況があり、
我々はすでに1ノードリストを持っているところ。
そして私は、元に戻って上がる場合は、 問題文は、我々は次のよ
インサートはちょうどのために、34であると言う 議論のために。
だから、僕は、便利に行くよ こっちそれを描く。
私はmallocさだ。
のは、私がnullのチェックをしていたとする。
>> 今、私は初期化す​​るつもりだ N 34であると。
そして、これはNになります。
これは、次となります。
そして、これは、前になります。
の私はなかったことを確認してみましょう 後方これを取得。
前回は最初に来る 定義中。
私は、この問題を修正しましょう​​。
これは、前のです。
これは隣接しています。
これらが同一であるにもかかわらず、 一貫性のないところに保管してみましょう。
>> 前。
これは隣接しています。
だから、僕はチェックし、私のノートをmallocさだ nullを、ノードに34を割り当てました。
前回はnullを取得します。
だから私にそれを与えます。
次のリストを取得します。
だから、リストはこれです。
だから、これは今、これを図面と同じである 彼らは1を指すように、矢印
同じ中。
そして私はチェックしていたら、リスト NULLと同じではありません。
そして、それはこの時点ではありません。
それから私は、リストをするつもりです 以前はポインターを取得します。
>> だから、前のリストPTRを取得します。
だから、これは置くことの効果があります ここグラフィカル矢印。
そして、それは少しなってきた 波状、ライン。
そして、最後に、私が更新 ポインタを指すように一覧表示します。
だから今これがこの男を指しています。
そして今、のは、迅速にやらせる 健全性チェック。
>> ここにあるリストは、です グローバル変数。
最初のノードは、実際に、34なぜなら 私はその矢印を次のよ。
私がしたいので、それが正しいです リストの先頭に挿入します
すべての新しいノード。
彼の次のフィールドは、この男に私をリードしています。
私が続けるなら、私は次のヒットnullです。
だから、これ以上のリストがありません。
私は以前にヒットした場合、私が取得 私は期待してどこにバックアップします。
>> だから、いくつかのポインタが残っています、 明らかに、操作する。
しかし、あなたが何を言われたという事実 これは、一定の時間内にあなただけを意味し、
物事の有限数を有する あなたが行うには許可しています。
その数は何ですか？
それは一歩かもしれません。
これは、2かもしれません。
それは千のステップかもしれません。
しかし、それはあなたができないことを意味している、有限だ ループのいずれかの種類が起こっている
ここでは、再帰なし、なしのループ。
それは、単にハードコードされた行があるはずだ 我々は、このサンプルで持っているように、コードの。
>> だから、次の問題12は、私たちを尋ねた 削除の実装を完了
それが削除されるような方法で、以下の 線形時間のリストからN。
だから、もう少しを持っている 余地になりました。
存在する場合には、そのNをとることができる リストに、存在するであろう
一回に過ぎない。
あまりにもクイズ系であることを意味すること 単純化した仮定なので、
それは、番号50のどこかを発見した場合 リストで、あなたもしません
し続けることを心配する必要はあり あらゆる可能な探して、繰り返し処理
ただ委譲う50のコピー、 限られた時間の中で、いくつかの特徴点に。
>> だから削除して、この1は間違いだった より挑戦的かつ詳細
書き込むためのコード。
しかし、一見すると、率直に言って、それは可能性がある 圧倒的と次のようになり
あなたが持つことができる方法はありません クイズに思い付く。
しかし、我々は個々のステップに焦点を当てた場合、 うまくいけば、それは突然ます
これらの個々のそれぞれのことを打つ 手順は、明らかな意味があります
振り返ってみると。
それでは見てみましょう。
>> だからまず、ポインタを初期化 であるとすること自体を一覧表示します。
私は線形時間をしたいので、その手段 私はいくつかのループを持っているつもりです。
そして一般的な方法は、反復するために リスト構造や、あらゆる種類のノード
構造を反復取ることです データの先頭へのポインタ
構造と、ちょうど更新を開始 ITとあなたの道を歩く
データ構造を通る。
だから私はまさにそれをするつもりです。
>> ポインタしばらく、私の一時変数、 みましょう、NULLと等しくない
先に行くとチェックしてください。
私は幸運でしたか？
私は現在、私のノードでNフィールドです に等しく見
番号は私が探しています？
もしそうなら、のは何かをしてみましょう。
今、このことを気づいた場合は、条件 全体を囲んで
次のコード行。
これは私が気に唯一のものです - 問題の番号を見つける。
そう単純化する、全く他にありません 概念的に物事を少し。
>> しかし、今、私が実現し、あなたが持っているかもしれません だけを考えた後、これを実現
それは少しを通して、そこ 実際にここ2例。
ノードがであるものである あるリストの先頭
それだから、少し迷惑 特別な場合には、対処する必要があるため
この事で、どの 唯一の異常である。
他のどこでも、リスト内の、 それは同じことだ。
前のノードと次があります ノード、前のノード、次のノード。
しかし、この男は少し特殊です 彼が先頭にいた場合。
>> そう、ポインタがリストと等しい場合 それ自体、私はの先頭にいたら
リストとI nは発見した、私が必要 物事のカップルをすることができません。
一つは、私はにリストを変更する必要があります 次のフィールドをポイントし、50。
だから私はしようとしていると仮定 34を削除します。
だから、この男の行くようになった わずか瞬間に。
>> だから私は言うつもりは、リスト 次のポインタを取得します。
まあ、これはポインタです。
次のこっちを向いている。
だから、これはこの矢印を右に変化している 今ここにこの男を指すように設定します。
今、我々が持っている、覚えている 一時変数。
だから我々は、あらゆるノードが孤立していないが、 私も、私の中でこの男を持っているので、
削除の実装。
だから今、リスト自体がnullでない場合、 私は少し何かを修正する必要があります。
>> 私は今、必ずこの矢印ことを確認する必要があり、 以前に指している
50から34に、これは離れて行くようになっており、 ので、私は取り除くためにしようとしている場合は、
34、50はいずれも維持し、より良いしていなかった としてそれを後方参照の種類
矢印が示唆された。
だから、僕は、この行をしました。
だから、私は行われています。
その場合は、実際にはかなり簡単です。
リストの先頭を切っチョッピング 比較的簡単である。
>> 残念ながら、これがあります 迷惑なelseブロック。
だから今、私はケースを考慮する必要があります 途中で何かがある場所。
しかし、それは除いて、あまりにもひどいではありません このような構文のために。
だから私はの先頭にいないよ場合は、 リストは、私がどこか真ん中にいるよ。
そして、ここでこのラインは、言っているスタート どのようなノードでは、にいる。
前のノードの次のフィールドに移動 ポインタでそれを指摘している。
>> それでは絵でこれをやってみましょう。
それは複雑になっていた。
だから私はここに、前のフィールドを持っている場合 - それでは、これをやらせる - ここに、次のフィールド。
私はむしろ私のポインタを簡素化するつもりだ の全体の束を描くよりも
物事は前後に縦横に お互い。
そして今、ちょうどこれは、1、2であるとしましょう でも、議論のために3、
それはと整列しませんが 問題となっている問題。
>> だからここに私のリンクリストです。
私はこれで2を削除しようとしています 物語の特定のバージョン。
だから私は、体へのポインタを更新しました この男を指している。
だから、これは、PTRです。
彼はここに指している。
これは、リストされ、存在している 世界的に前と同じように。
そして、彼は何があって、ここで指しているんだ。
そして今、私は2を削除しようとしている。
>> ポインタが、ここで指しているのであれば、私は今 、明らかに、従うつもり
1で私を置き、前のポインタ。
私は次のことを言おうとしています これに私をもたらし、フィールド、
ここBOX、しようとしている 等しいポインタの横。
このポインタのであれば、これが隣接しています。
つまりつまり、この矢印ニーズ この男を指すように設定します。
>> だから、このコード行は、単に何を持っている この少しはあるに行わ。
そして今、これはのように探しています 正しい方向への一歩。
私たちは、基本的に2つを切り取るたい 1および3の中央。
だから、私たちがしたいことを理にかなっている その周りにルートこのポインタを。
ポインタのであれば、この次の行がチェックしている 次のnullでない、そこ
2の右に実際に誰かが、 つまり、我々はまたしなければならないことを意味
ここで少しスニップ。
>> だから私は今、このポインターを実行する必要があります そして、前のポインタを上に更新する
の少しを行うにはこの男 回避策はここにここでのポイント。
そして今、視覚的にこれがいいです。
があることで、それは少し厄介なの もう2を指して誰も。
2は左を指している。
そして2右を指している。
しかし、彼は、彼が望んでいるものは何でもできますので、 彼は解放された取得することについてです。
そして、それはどのような問題ではありません これらの値はもうある。
>> 重要なのは、残りのことです 男は、上のルーティングされる
そして今、彼下記。
そして実際、それは我々が次の仕事だ。
私たちが知ることを意味我々フリーポインタ、 オペレーティングシステムは、あなたを歓迎します
これを再利用する。
した後、最後に、我々は戻って。
我々の場合、暗黙のうちに他の まだ戻っていない、
私たちは探し続けるようになってきました。
だから、ポインタは単に次のポインタに等しい ここでこの男を動かすことを意味します。
ここでこの男を移動します。
ここでこの男を移動すると、実際には、 私たちは番号を見つけることができませんでした
我々はまだ探しています。
>> そう率直に言って、それが完全に見える 最初は、私が思うに、圧倒的
あなたが苦労している場合は特に一見、 これでクイズ中にして参照してください。
このようなもの。
そして、あなたは背中に自分自身をなでる。
さて、私が持っていることができる方法はありません クイズでその思い付く。
あなたが壊れている場合、私はあなたができる、と主張するだろう これらの個々にそれダウン
ただ例で、それを歩く 慎重に、確かに、とはいえ、下
ストレスの多い状況。
>> ありがたいことに、画像が作ら 幸せのすべて。
あなたはこれを引くことができ 任意の数の方法。
あなたが十字交差を行う必要はありません ここの事。
あなたはストレートでそれを行うことができます このような行。
しかし、この問題の要旨、 一般的には、ことを実現することでした
最終的に画像が少しになります なぜなら、このようなもの、
時定数は、あなたが保持することを暗示 ジャミングや妨害と妨害
先頭に新しいノードを リストの。
ご質問？
おそらく最も挑戦 確かに、コードの質問。
>> 観客：そうのようなリストがある 前の例でのヘッド。
>> DAVID J.マラン：その通り、その通りです。
のためだけに別の名前 グローバル変数。
世界的な何？
>> ROBボーデン：わかりました。
だから、これはどこに1です 段落を書かなければならなかった。
一部の人々は、エッセイを書きました この質問のために。
しかし、あなたはちょうどこれらの6の用語を使用する必要があります ときに何が起こるかを説明する
あなたはfacebook.comに連絡してみてください。
だから、僕はプロセスを介して話をしましょう すべてのこれらの用語を使用して。
だから私たちのブラウザでは、我々はfacebook.comを入力 そしてEnterキーを押します。
だから私たちのブラウザは、構築するために起こっている それは送信するために起こっていることを、HTTPリクエスト
のためのFacebookへいくつかの過程を経て との私達に応えるためにFacebook
そのページのHTML。
>> だから、プロセスはで何 そのHTTPリクエスト
実際にFacebookに取得する？
だからまず、翻訳する必要があり Facebook.com。
だから、名前Facebook.com与え 実際にHTTPリクエストを行う場合、
行く必要がある？
だから我々はFacebook.comを変換する必要があります 一意のIPアドレスに
どのようなマシンたちが実際に識別 この要求を送信する。
あなたのラップトップは、IPアドレスを持っています。
インターネットに接続されているものは IPアドレスを持っています。
>> だからDNSは、ドメインネームシステム、すなわち、 何が翻訳を扱うために起こっている
facebook.comからそのIPアドレスに あなたは、実際に連絡を取りたい。
だから我々は、DNSサーバーに問い合わせて、 たとえば、facebook.comは何ですか？
それは、ああ、それはIPアドレス190.212だ、と言う 何か、何か、何か。
わかりました。
今、私は知っているマシン 私が連絡したいと思います。
>> だから、あなたはあなたのHTTPリクエストを送信する そのマシンにフェイルオーバ。
それでは、どのように、そのマシンに到達するのでしょうか？
さて、リクエストがから行く バウンスルータにルータ。
ここで、クラスの例を覚えている 私たちは実際にルートを見た
私たちがしようとしたときのパケットがかかった 通信します。
我々は、大西洋を飛び越えた 1点または任意のオーシャン。
>> だから、最後の項ポート。
これは、お使いのコンピュータに保存されました。
現在、複数のものを持つことができます インターネットとの通信。
だから私は、言う、スカイプを実行することができます。
私は、Webブラウザを開いている場合があります。
私は何かを持っているかもしれません BitTorrentにファイル。
したがって、すべてのこれらの事である との通信
何らかの方法でインターネット。
>> だからあなたのコンピュータは、いくつかのデータを受信したとき インターネットから、どのようにそれはありません
実際にどのようなアプリケーションを知っている データを望んでいる？
それはどのようにこの特定のかどうかわからない データは、のためのものです
対照的に、アプリケーションをBitTorrentに Webブラウザに？
だから、これはその中のポートの目的です これらのアプリケーションのすべてが持っている
お使いのコンピュータのポートを主張した。
だからあなたのWeb​​ブラウザは、ちょっと、と言う 私は、ポート1000上聞いている。
そして、あなたのBitTorrentにプログラムが言っている、 私は、ポート3000上で聞いている。
とSkypeは、私は、ポート4000を使用しています、と言います。
>> ですから、所属するいくつかのデータを取得するとき これらの用途の一つは、データの
どのポートが付いているので、実際に に沿って送信する必要があります。
だから、これはああ、私が所属し、言う ポート1000。
私は、私はこれを転送する必要が知っている 私のWebブラウザに沿い。
だから、その理由は、それはここでは関係者 Webサーバがする傾向があることである
ポート80をリッスンする。
私はFacebook.comに連絡したとき、私はよ いくつかのマシンと通信。
しかし、私はそれのどのポートを言う必要がある 私が通信するマシン。
およびWebサーバがある傾向がある ポート80でリスニングしています。
>> 彼らが望んした場合、彼らはそれを設定することができます それは、ポート7000上のように一覧表示されますので、最大。
した後、Webブラウザで、私ができた 7000：手動Facebook.comを入力
ポート7000に要求を送信 Facebookのウェブサーバーの。
>> DAVID J.マラン：この場合にも、 我々は人々を必要としませんでしたが
これを言及、この場合は、どのポート 要求が実際に行くか？
もう一度やり直してください。
その通りです。
微妙なものを探しているではなく、 つまり、最後のどれもありません。
>> ROBボーデン：だからHTTPSが、それはですので、 のために特別に聞いて
暗号化され、ポート4430上にある。
>> 観客：E-メール配信は25アール、右？
>> DAVID J.マラン：送信 電子メール、25、うん。
>> ROBボーデン：私も、ほとんどのを知らない - 下のもののすべてになりがち
物事のため​​に予約。
私はすべての下で考える 1024は予約されています。
>> 観客：なぜあなたは言った 3は間違った番号でしたか？
>> ROBボーデン：のためのIPアドレス、 数字の4つのグループがあります。
そして、彼らは0から255までだ。
だから、192.168.2.1が一般的です ローカルネットワークのIPアドレス。
それらのすべてが255未満であることに注意してください。
だから私は300で開始すると、その おそらく持っていることができませんでした
数字の一つとなって。
>> DAVID J.マラン：しかし、その愚かなクリップ から - それは彼らが持っていたCSIだった
あまりにも大きかった回数 IPアドレスについて。
>> ROBボーデン：この上の任意の質問？
次の1、で非常に完全な変更 トピックが、我々にはこのPHPの配列を持っている
クワッド内の家々。
そして、我々は順序なしリストを持っている。
そして、我々は各リスト項目を印刷したい ちょうど家の名前が入っている。
だから我々は、foreachループを持っている。
だから、構文がforeachのですが、覚えている 配列内のアイテムとして配列。
だから、ループの各反復を通じて、 家はの1を取るために起こっている
配列の内部値。
>> 最初の繰り返しでは、家 キャボットハウスになります。
2回目の繰り返し、家になります というように宅配便の家であることと。
だから、家の各クワッドのために、我々はしている ただ印刷しようとして -
また、エコーたかもしれない -
リスト項目、その後、家の名前 して、リスト項目を閉じます。
中括弧は、ここで省略可能です。
>> そして、我々はまた、問題の中で述べ それ自体は、クローズするのを忘れないでください
番号なしリストタグ。
だから我々は、PHPモードを終了する必要があります これを実行するためである。
あるいは我々がエコーしている可能性が 番号なしリストタグを閉じます。
>> DAVID J.マラン：ここにも罰金だろう 古い学校を使用するようになっている
$ iは= 0 0とまでカウントを使用したループ 線の長さを把握する。
ただ、あまりにも完全に罰金 少し冗長に。
>> 観客：だから、しようとしている場合は [聞こえない]、あなたがするだろう -
私はループが[聞こえない]が何であるかを忘れている。
もし$クワッドブラケット、私だろうか？
>> DAVID J.マラン：その通りです。
ええ、その通りです。
>> ROBボーデン：他には？
>> DAVID J.マラン：すべての権利。
トレードオフ。
だから、答えの束があった これらのそれぞれの可能な。
私たちは本当にちょうど探していた 逆さまのための説得力のあるものと
欠点。
と数16は、ユーザーの検証、尋ね 入力クライアント·サイドは、JavaScriptと同様に、
代わりに、サーバー側の、PHPと同じように。
そうの利点は何ですか クライアントサイドをやって？
>> まあ、我々が提案ものの一つです あなたので、あなたが、待ち時間を減らすこと
連絡気にする必要はありません いくつかのかかる場合があり、サーバ、
でも、ミリ秒または秒のカップル それを避けることで、ちょうど
で、ユーザーの入力クライアント·サイドの検証 オン提出ハンドラをトリガし、
ちょうど彼らが入力したチェック nameの中の何か？
彼らは何かを入力しましたか 電子メールアドレスのためにある？
彼らはから寮を選んだ ドロップダウンメニュー？
>> あなたは彼らに瞬時にフィードバックを与えることができます ギガヘルツコンピュータを使用して
または何でも彼らはそれはだている 実際に自分の机の上。
だから、それだけで良いのユーザーの 一般的に経験する。
しかし、クライアント側をすることのマイナス面 検証、あなたもすることなく、それを行う場合は、
サーバー側の検証を行うと、ということです CS50から出てくるほとんど誰もが知っている
あなただけのあなたが望む任意のデータを送信できること サーバへの任意の数の方法。
率直に言って、ほとんどすべてのブラウザで、次のことが可能 設定で周りをクリックするだけ
JavaScriptをオフにし、これだろう 従って、任意の形態をディセーブル
検証。
>> しかし、あなたはまたしても私はそれを思い出すかもしれません 使用して、クラスにいくつかの難解なことをした
Telnetと実際のふり GETを送信することで、ブラウザに
サーバへのリクエスト。
そして、それは確かではありません 任意のJavaScriptを使用して。
それはちょうど私は、コマンドを入力するだ キーボードで。
だから本当に、十分な内の任意のプログラマ ウェブとHTTPと快適さ
彼または彼女が望むどのようなデータを送信することができます 検証せずに、サーバーへ。
そして、あなたのサーバーもチェックしていない場合は、 彼らが私に名前を付けたのです
この実際には有効な電子メールアドレス、でした 彼らは寮を選ぶ、あなたが終わるかもしれない
偽のか、単に空白のデータを挿入するまで おそらく、データベース内へ
良いことになるだろうされていない場合 あなたはそれがあったと仮定した。
>> だから、これは厄介な現実である。
しかし、一般的には、クライアント側の 検証は素晴らしいです。
しかし、それは二倍の仕事を意味します。
様々存在しないが のためのライブラリ、JavaScriptライブラリ
例えば、これだけを行うことを 頭痛のはるかに少ない。
そして、あなたはコードの一部を再利用することができます サーバー側、クライアント側の。
しかし、それは一般的であることを認識しない 追加作業。
うん。
>> 観客：もしそうならば、私たちだけで 安全性の低いと -
>> DAVID J.マラン：（笑）
ぐふ。
それらは常に困難です 裁定するもの。
>> ROBボーデン：それだろう 受け入れられている。
>> DAVID J.マラン：何？
>> ROBボーデン：私はこの問題を作成しました。
それが受け入れられたであろう。
>> DAVID J.マラン：うん。
>> 観客：クール。
>> ROBボーデン：しかし、我々は受け入れられませんでした 最初の1のために -
さて、私たちが探していたことである あなたのようなものがする必要はありません
サーバーと通信します。
我々だけ速く受け入れませんでした。
>> 観客：何について ページをリロードしてみませんか？
>> ROBボーデン：はい。
それは受け入れ答えた。
>> DAVID J.マラン：我々は感じたものは それはそうではない可能性の方が高いでした
あなたは何であったか知っていたこと タフである、と言って
時々描画するライン。
代わりに、リンクされたリストを使用して 維持するために、アレイの
整数のリストを並べ替え。
だから我々は、多くの場合に引用逆さまにリンクされた 彼らの全体の動機をリスト
導入には、ダイナミズムを取得しました。
彼らは成長することができます。
彼らは、縮小することができます。
だから、試練をする必要はありません 実際に多くのメモリを作成するには
配列を持つ。
それとも、ただする必要はありません 申し訳ありません、と言うと、ユーザ。
アレイが充填されている。
リストのとてもダイナミックな成長。
リンクリストのもマイナス面？
>> 観客：それは線形です。
リンクリストに検索が線形である 代わりに、あなたがログイン何の
>> DAVID J.マラン：その通りです。
リンクリストに検索は直線的で、 それがソートさであったとしても、あなたは可能性があるため
これらのみパン粉に従って、これらの ポインタは、リストの先頭から
最後まで。
あなたは、ランダム·アクセスを活用することはできません、 このように、二分探索は、それがであったとしても
あなたができることを、ソートされた 配列を使用して行います。
そしてもう一つのコストもあります。
うん。
>> 観客：メモリー非効率的？
>> DAVID J.マラン：うん。
まあ、私は必ずしもないでしょう 非効率的と言う。
しかし、それはあなたに多くのメモリを費用がかかり、 あなたはすべてのために32ビットを必要とするので、
追加のポインタのノード、で シングルリンクリストのための最低。
今、あなたが整数のみを格納している場合と あなたは、ポインタを追加している、それはです
実際にこの種の非自明。
これは、メモリの量を倍増だ。
しかし、現実には、あなたが保存している場合は、 可能性があり、構造体のリンクリスト
8バイト、16バイト、さらにより それよりも、多分それは少ないです
限界費用の。
しかし、それにもかかわらず、コストです。
ので、これらのいずれかがきになる マイナス面として罰金き。
>> 18。
書くことの代わりに、CのPHPを使用して コマンドラインプログラム。
だからここには、使用するために、多くの場合、高速です PHPやRubyやPythonのような言語。
あなただけ素早く開く テキストエディタまで。
あなたは多くのより多くの機能を持っている あなたに利用できる。
PHPは関数の台所の流しがあり、 Cでは、一方、
非常に、非常に少ないがあります。
実際には、人はリジェクト苦労を知っている あなたはハッシュテーブルを持っていないこと。
あなたがリンクリストを持っていません。
あなたがそれらをしたい場合は、その必要はあり 自分で実装しています。
>> だから、1のPHPの上部または実際に任意の インタプリタ型言語は迅速である
これを使用すると、コードを書くことができます。
しかし、欠点は、私たちはこれを見たとき、私 迅速misspellerをホイップ
PHPを使用して、講義での実装は、ある インタプリタ言語を使用して、その
通常は時間がかかります。
そして、我々はして明らかにすることを見ました 3に0.3秒から時間の増加
なぜなら解釈の秒、 それは実際に起こる。
>> 別の利点は、あなたということでした コンパイルする必要はありません。
だから、また、開発をスピードアップ ちなみに、あなたは持っていないため、
プログラムの実行には、2つのステップ。
あなただけの1を持っている。
だからこれはかなりです 魅力的なだけでなく。
SQLデータベースを使用する代わりに、 データを格納するためのCSVファイル。
ように、SQLデータベースがpset7に使用されます。
CSVファイルはあなたがあまり使用しませんでした。
しかし、あなたのようにpset7で間接的に使用される よくヤフーファイナンスに話すことによって。
>> しかし、CSVは単なるExcelファイルに似ていますが、 列がどこにあるか、超簡単
すぐ内側カンマでdemarked そうでなければテキストフ​​ァイルの。
SQLデータベースを使用することはあり もう少し説得力。
あなたは物事をので、逆さまだ のような選択して挿入して、削除します。
そして、あなたは、おそらく、インデックスを取得すること MySQLとのような他のデータベース、
オラクル、メモリ内にあなたのために構築し、その あなたの選択はおそらくないことを意味します
下へ直線的トップになるだろう。
それは実際に何かになるだろう 二分探索か何かのような
精神面で似ています。
そこで、彼らは一般的に高速だ。
>> しかし、欠点は、ということです それだけでより多くの仕事だ。
それは多くの努力です。
あなたがデータベースを理解する必要があります。
あなたはそれを設定する必要があります。
あなたが実行するためのサーバが必要 上のそのデータベース。
あなたが理解する必要があります それを設定する方法。
したがって、これらはちょうどこれらの トレードオフの種類。
CSVファイル、次のことができ、一方、 geditのでそれを作成してください。
そして、あなたは行ってもいいです。
それを超えていない複雑さがありません。
>> トライの代わりにハッシュテーブルを使用して 保存するための別々の連鎖で
連想させる単語の辞書 pset5の。
そのように理論​​的には、上側試みる 少なくとも、何がある？
一定の時間、少なくともあなたがしている場合 個々のそれぞれの上にハッシング
あなたのような単語の文字、 pset5のために持っているかもしれません。
つまり、5ハッシュ、6かもしれない 5または6があるかどうハッシュする
単語の文字。
そして、それはかなり良いです。
そして、どのように上限があるかどう 長いあなたの言葉があるかもしれない、それはです
確かに漸近的に一定の時間。
>> 一方、別々にハッシュ·テーブル それとそこには、問題を連鎖
データ構造の一種であること 通常、アルゴリズムの性能
ものの数に依存します 既にデータ構造である。
そして、それは間違いの場合だ チェーン、あなたが置くことにより、より多くの原料
ハッシュテーブルに、長いもの チェーンは最悪で意味し、行く
場合、あなたが探している可能性があります事 1の最後にすべての方法である
これらのチェインの、その効果的 リニア何かに委譲。
>> さて、実際には、それは絶対にできた ハッシュテーブルの場合の
チェーンは、対応するよりも高速です トライの実装。
しかし、それはの間で、様々な理由のためだ その試みは、全体の多くを使用している
メモリということができ、実際には、遅いもの ダウン、あなたが素敵な取得しないので、
キャッシングと呼ばれるものの利点、 どこに接近しているもの
メモリにアクセスすることができます 多くの場合、より迅速に。
そして、時にはあなたが思い付くことができます 本当に良いハッシュ関数。
あなたが少しを無駄にする必要があっても、 メモリには、確かに、することができるかもしれない
高速ではないものを見つける 直線的に同じくらい悪い。
>> そう簡単に言えば、必ずしもありませんでした これらの1あるいは2のいずれか
私たちが探していた特定の事柄。
説得力のある本当に何 上側および下など
一般的に私たちの目を引いた。
>> ROBボーデン：だから逆に、我々はなかった 自分自身で受け入れられない "速く"あなた
それについて何かを言っていた。
あなたは、理論的に速く前記あっても、 我々はあなたがちょっと理解していることを知っていた
それは1の0だと。
理論的には、ハッシュテーブル、 1の0ではありません。
ランタイムについて何も言及 一般的にはあなたのポイントを得た。
しかし、「より速く、「ソリューションのほとんどに 試みであった大きなボード
ソリューションよりも客観的にも遅い つまり、ハッシュテーブルでした。
とても速く、それ自体の 本当に真実ではありません。
>> DAVID J.マラン：ドム·デ·DOM DOM。
私はおそらく実現だけだ それは、そのがになっている方法です
右、発音される？
>> ROBボーデン：私は実際に理解していませんでした。
>> DAVID J.マラン：それは作られ 私の頭の中で感覚。
>> ROBボーデン：私はこの1つをやっている。
[OK]をクリックします。
だから、これはあなたが描く必要があったものです あなたと同様の図かもしれない
過去の試験で見てきました。
それでは、ちょうどこのを見てみましょう。
だから、HTMLのノードから、我々は2つ​​を持っている 子ども、頭と体。
だから我々の枝 - 頭と体。
ヘッドはタイトルタグを持っています。
だから我々はタイトルを持っている。
>> 今、一つのこと、多くの人々 忘れてしまったこれらのテキストノードであるということです
このツリー内の要素。
そこでここでは、楕円としてそれらを描くことが起こる これらと区別するために、
ノードのタイプ。
しかし、予告もここで我々はトップを持って、 途中、下がされてしまう
テキストノード。
だから、それらは幾分だった忘れて よくある間違いの。
>> ボディは3人の子供がいる - これらの3のdiv。
そうDIV、DIV、DIV、テキスト これらのdiv要素のノードの子。
つまり、かなりそれだ その質問のため。
>> DAVID J.マラン：そして、それは注目に値します、 我々は、これらにこだわるしないにもかかわらず、
私たちが過ごす時間の詳細 注文がないJavaScriptや、中
実際、技術的には問題。
だから、ヘッドが身体の前に来る場合 HTML、それはに表示されます
実際のDOM内の車体左側。
彼は、単にFYI、一般に、ある 文書順序と呼ばれるもの、どこで
それは問題ではありません。
そして、あなたは、パーサーを実装した場合には、 建物内のHTMLを読み込むプログラム
メモリ内の木まで、正直に言うと、 それはおそらく直感的にどのようなあなたです
とにかくやる - 上から下へ、 左から右へ。
>> ROBボーデン：これについての質問？
私は、次のいずれかの操作を実行する必要がありますか？
>> DAVID J.マラン：確かに。
>> ROBボーデン：わかりました。
だから、これはバッファオーバーランです 攻撃質問。
ここで認識するための主なものは、ある さて、どのように敵のトリックかもしれない
実行中にこのプログラム 任意のコード？
そうargv1、最初のコマンドライン このプログラムへの引数であることができる
任意の長さ。
が、ここではコピーするmemcpyをを使用している ここにバーですargv1、。
私たちは、引数として渡している。
そしてそれは名前バーに取っている。
>> だから我々はバーをmemcpyingいる このバッファCに。
我々はどのように多くのバイトをコピーしている？
さてしかし何バイトバーはどうなります 、その引数の長さを使用する。
しかし、Cは12バイト幅である。
だから我々は、コマンドライン引数を入力した場合 それが12バイトより長いですが、我々はしている
これをオーバーフローしよう 特定のバッファ。
今、どのように敵をだますかもしれません 任意のコードを実行させるプログラム？
>> だから、ここで覚えている メインはfooのを呼び出している。
だから、メインの呼び出しは狛犬。
それでは、これを描きましょう。
だから我々は我々のスタックを持っています。
そして主は、スタックフレームを有している 一番下にある。
ある時点で、主コールはfooに。
さて、すぐに、メインの呼び出しは狛犬。
だからfooは、独自のスタックフレームを取得します。
>> 今、いくつかの点で、fooの 返すために起こっている。
とfooリターンを行ってきました、我々は時に知っておく必要があります メイン我々の内部のコードのどの行
知るためであった 私たちは、主に再開する必要があります。
我々は全体からのfooを呼び出すことができます さまざまな場所の束。
どのように我々はどこに返すことを知っていますか？
さて、私たちはどこかに格納する必要があります。
>> だから、どこかで右周りここでは、保存 我々は一度に戻るべき場所
fooの戻ります。
そして、これは、リターンアドレスです。
それでは、どの敵は利点がかかる場合があります これのことである
このバッファーCが格納されている、みましょう cはちょうどここ、と言う。
だから我々は、Cのための12バイトを持っている。
これはCである。
そして、これは、fooのスタックリングです。
だから、悪意のあるユーザーが、よりに入った場合 12バイト以上、またはそれらはコマンドを入力します。
12よりも長いですライン引数 文字は、その後、我々はするつもりだ
このバッファをオーバーフロー。
>> 我々は続けることができます。
そしてある時点で、私たちは遠くに行く 私たちは始めることを十分に
このリターンアドレスを上書きします。
だから我々はリターンアドレスを上書きした後、 これは、ときのfoo
戻って、我々はどこに戻っています 悪意のあるユーザーがすることによって、それを語っている
それはどのようなことで、入力されたどのような値 文字は、ユーザーが入力した。
だから悪意のあるユーザーがされている場合 特に巧妙な、彼はこれを持つことができます
printDef内のどこかに戻る 関数やmalloc関数内のどこかに
機能、どこでも任意の。
>> しかし、さらに巧妙な彼が持っているものであればある ユーザーはここに戻ります。
そして、あなたは実行を開始 これらのコード行として。
だから、その時点で、ユーザーが入力することができます 彼は、この地域に望むものは何でも。
そして、彼は完全に制御を持っている あなたのプログラムの上。
その上での質問？
だから、次の質問が完了しました このような方法でのfooの再実装
それがもはや脆弱だということ。
>> だから、いくつかの方法があります あなたはこれを行っている可能性があります。
我々はまだCのみ持っている 長さ12のもの。
あなたはこれを変更した可能性 あなたのソリューションの一部として。
また、確認してくださいを追加しました 必ずバーがnullではなかった。
あなたは必要としませんでしたが その完全な信用のため。
だから我々は最初にチェックしている バーの文字列の長さ。
それは12を超えます場合には、 実際にコピーをしない。
だから、それを固定する一つの方法です。
>> それを固定する別の方法は、代わりに それだけを持って、長さが12であることを有するC
長さはstrlen（バー）であること。
それを固定する別の方法は、ある 実際には戻ります。
だから、あなただけのすべてを取り除く得ていた場合は、 これは、あなただけのすべて削除した場合は、
コー​​ドの行は、あなたが得ているだろう この関数以来、フルクレジット、
実際には何も達成しない。
これは、コマンドラインをコピーするだ いくつかの配列に引数
そのローカルスタックフレーム。
そして、その後のことは戻っている。
そして何でもそれは達成がなくなっています。
だから、リターンも十分であった フルクレジットを取得する方法。
>> DAVID J·マラン：のない非常精神 質問が、あたりの許容
それにもかかわらずスペック。
>> ROBボーデン：それに関して質問？
あなたは、少なくとも一つのこと コー​​ドをコンパイルしている必要がありました。
だから、技術的にはそうでないにもかかわらず、 脆弱なコードがない場合
コンパイル、我々はそれを受け入れませんでした。
noの質問？
[OK]をクリックします。
>> DAVID J.マラン：あなたがしたいですか このタイトルを避ける？
>> ROBボーデン：いいえ。
>> DAVID J.マラン：だからこれ1において、この 良いニュースか悪いニュースのいずれかであった。
これは文字通り、同じ問題である 最初のクイズなど。
そしてそれはほとんど同じだ PSET1として問題。
しかし、それは意図的であることが簡素化されました 単純なピラミッドであることができる1
少しで解決 単純な反復。
本当に、私達はで何を得ていた ここでは、そのように多くのロジックではなかった
おそらく、この時点で、あなたがしているので あなたがいたよりも快適
ループや、なぜforループで週1において、 しかし、実際にその離れていじめる
あなたは少し慣れ PHPはまさにではありませんという考え
プログラミング。
これは、実際の言語として使用することができる コマンドラインプログラムを書く。
>> そして実際、それは我々がしようとしていたものだ に注意を描画します。
これは、コマンドラインPHPプログラムです。
そこでここでは、Cコード、しばらく正しい C言語で、PHPを補正しない。
しかし、コードは実際には同じである。
あなたはクイズのためのソリューションを比較すると クイズ1対0、あなたはそれを見つけることができます
それは除いて、ほとんど同じだ いくつかのドル記号および用
データ型が存在しないこと。
特に、我々はここで見てみると、 この中で、我々は繰り返し処理いることがわかります
ケース、1から7までアップする。
>> 我々はそれを0のインデックスを行っている可能性があります。
しかし、時には、私はそれだけだと思う 精神的に簡単に物事を考えること
1〜7。
あなたは1ブロックが必要な場合は、2 次いで、ブロック、三つ、次いで
ドット、ドット、ドット7。
我々は1に初期化されてきたJ そして私までに数える。
そして、ここにすべてがある それ以外は同一。
しかし、注目に値するのである 物事のカップル。
私たちはあなたの次の2行、最初にこれを与える ばかみたいにシバンとして名前1、
鋭い強打のため。
そして、それはただ、パスを指定します。 フォルダ、プログラムが可能な
使用したいことを発見 このファイルを解釈する。
>> とのその後、ライン、 コー​​スは、PHPモードに入ることを意味します。
そして一番下の行 終了PHPモードを意味します。
これはと、一般に、動作する 言語を解釈した。
あなたが書く場合にはちょっと迷惑なんだ はFoo.phpというファイル内のプログラム。
そして、あなたのユーザーが持っているだけで [OK]を、覚えて、このプログラムを実行するために、私
入力する必要が "PHPのスペースはFoo.phpを。"種類 何もない場合は迷惑なの。
そしてそれはまた、あなたのプログラムことが明らかになった すべてではありません、PHPで書かれている
そのユーザ用照明。
>> だから、完全に。PHPを削除することができます 講義からリコール。
そして、あなたは実際には。/ fooを行うことができた場合 あなたはそれを作ることによってそれをchmoddedました
実行可​​能。
だからます。chmod a + xはfooがそれを行っているでしょう。
そして、あなたはまた、シバンをここに追加した場合。
しかし、実際に、問題は、なっていた このようなものをプリントアウト。
ノーHTML、必ずノーCコード、 単にいくつかのPHP。
そうミロは、問題25で戻った。
そして25で、あなたは、次の与えられた たスケルトンコード、
非常に単純なWebページ。
とHTMLワイズジューシーな部分がダウンしていた ここで、我々は、本体の内部に有する場合
入力の固有のIDを持つフォーム その内部2入力、1だった
名前の考えと、1 ボタンの考えと。
>> 最初は、text型だった 型の第提出してください。
そして私たちは、実際には、より多くのあなたを与えた あなたはちょうどので、必要以上に食材
あなたたちは、との選択肢を持っていた この問題を解決する。
あなたは厳密には必要ありません これらのIDがすべて表示されます。
しかし、それはあなたが解決することができます それさまざまな方法で。
最大上部に、いることに注意してください 目的は、トリガーにした
このようなウィンドウ -
こんにちは、ミロ！ -
使用してブラウザでポップアップする もし、超簡単
醜いではない、アラート機能。
だから、最終的には、これはつまるところ 概念的には何らかの形でのリスニングをする
フォームのクライアント側の提出 、何とかしないサーバー側、
して、その提出への対応 ユーザーが入力した値をつかむ
[名前]フィールドにログインした後、 アラートの本体に表示する。
>> ですから、これを行うことができます一つの方法はである 少し見えるjQueryの、
最初は構文的に困惑。
あなたは純粋なDOMコードでこれを行うことができます - IDでdocument.getelement。
しかし、ここでは、このバージョンを見てみましょう。
大切なのカップルを持っている 行最初。
したがって、1つは、我々はある、このラインを持っている あなたが見たかもしれないものと同じ
私は信じて、で、form2.html 週9クラスから。
そして、これは単に、実行、と言っている 次のコードとき
文書では、準備ができています。
これは重要であるためだけで HTMLページは、トップ読み込まれる
左から右へ下の、。
>> そのため、あなたは何をしようとした場合 ここまでいくつかのDOMへのコードの中の何か
要素、いくつかのHTMLタグは、それがダウンだ ここで、あなたもすぐにそれをやっている、
これさえしていないため、 メモリに読み込まれて。
したがって、このdocument.readyと言って 行は、我々は言っている、
ここではいくつかのコードは、ブラウザです。
しかし全体まで、これを実行しないでください 文書が準備ができている、即ちDOMある
ツリーはメモリ上に存在しています。
この1は、もう少しです 構文的にはAであれば、簡単な
少し違う、私が言っている、グラブ そのユニークなHTML要素
識別子は、入力である。
つまり、どのようなハッシュタグの 、一意のIDを示している。
そして私は呼んでいる。提出する。
>> そう。ここに提出するには、それ以外の場合は、関数で 方法として知られている、それはです
左側上のオブジェクトの内部 私はハイライト表示しなかったことがある側。
だから、オブジェクトとして入力の思えば メモリに - そして実際にそれがある。
これは、ツリー内のノードの -
。手段を提出する際にこのフォームで このIDが送信され、実行
次のコード。
私は気にしないものの名前 この関数は、私が実行していましてね。
だからここに私は何、以前のように、使用しています ラムダ関数、またはと呼ばれる
無名関数。
それは、知的には全くありません それは名前がない以外は興味深い、
あなただけなら罰金である 今までに一度と呼ぶつもり。
そして、そこの中に私が実際に扱う フォームの送信。
私が最初に変数を宣言 Valueという。
して、この効果は何ですか 今ここの部分を強調した？
それはで何をするのか 私のためのハイレベル？
>> 観客：それは値を取得します ユーザーは、以下のHTMLでなかった。
次に、そのIDを取得し、 ITの価値を発見する。
>> DAVID J.マラン：その通りです。
それは、そのユニークなノードをつかむ 識別子は名前です。
それは、その中の値を取得している で、おそらく、どのような利用者
彼または彼女自身を入力しました。
そしてそれはであることを記憶する 変数は値と呼ばれる。
余談として、あなたも可能性があり 少し違ったこれをし。
何かをすることによって、完全に許容できる 嘘のVAR値を取得
のdocument.getElementById。
それは少しである理由、これがある jQueryを使用しないように面倒。
「名前」。値。
そう完全に許容できる。
これを行うためのさまざまな方法。 jQueryのちょうど もう少し簡潔になる傾向がある
間違いなく、より人気のある プログラマの間。
>> 今、私は正気を少しやっている なぜなら問題で、確認してください
文は、我々は、明示的に、言ったら ユーザーがまだタイプされていない、自分の
名前、アラートが表示されません。
しかし、あなただけで、それをチェックすることができます 空の文字列をチェックする
俗に言うがあるかどう 実際にそこに何もない。
しかし、それは俗に言うと等しくない場合には、 私は警告を呼びたい。
そして、ここで興味深い部分は、ということです 我々は、プラス演算子を使用しているどの
JavaScriptで何をしますか？
連結します。
だから、PHP欠陥のドット演算子のようなものだ。
同じ考え、他とは少し違います。
と私は、その文字列を作成しています あなたはスクリーンショットで見た -
こんにちは、云々。
>> そして、最後の細部はこれです。
なぜ内部falseを返します この無名関数の？
>> 観客：は値がありません。
あなたは、フォームに配置します。
値がない場合にはそれだけで、述べています 空白に等しいし、それを行う。
その申請の空白があった。
>> DAVID J.マラン：わかりました。
しかし注意。
ここに誰もありません。
そして、その戻り値のfalseが外にある もし条件。
これは、falseを返し、行をハイライト表示 どんな時に実行されませ
フォームが送信されます。
何がこの虚偽の内部を返すん メソッドが呼び出されるようにイベントハンドラ、、
対象のイベント 提出されて？
>> 観客：ので 一度だけ発生します。
>> DAVID J.マラン：一度だけ発生します。
はなく、かなり。
うん？
>> 観客：それはからフォームを防ぐ デフォルトの動作に提出する、
ページのリロードを行うことであろう。
>> DAVID J.マラン：その通りです。
だから私は、この用語は、ここに提出する過負荷によ 私が言っているので、フォームがある
提出さ。
あなたが示唆するようにしかし、それは実際にはありません 真のHTTPの方法で提出され。
あなたのために、[送信]をクリックしたときに私たちの のonSubmitハンドラは、傍受している
いわば、そのフォームの送信。
それから、私たちのことをやっている JavaScriptコードで。
しかし、私は意図的に、falseを返すよ 私は起きたくないものを理由
分割は秒後に、フォーム全体のためである それ自体はウェブに提出する
変更することで、キーと値のペアを使用してサーバー のようなものにするためのURL
Q =猫または何我々が行った、 例えば、クラスで。
私は、それが起こるしたくないので、 このため、どのサーバのリスニングはありません
フォーム送信。
これは純粋にJavaScriptコードで行うの。
私も持っていなかった理由、それはだ 私ので、私のフォームのaction属性、
このために意図していない これまでサーバーにアクセスしてください。
>> だから、提出されています。
しかし、我々はそのフォームを傍受している 提出し、デフォルトを防ぐ
に実際に行動、 すべての道のサーバーにアクセスしてください。
>> 観客：だから、クライアント側にそれを維持する。
>> DAVID J.マラン：維持 そのクライアント·サイド。
まったく正しい。
次はMySQLのオーマイた。
>> ROBボーデン：わかりました。
したがって、この最初の質問は、一般的だった 人々のためのラフ。
後のものは、より良い行ってきましたけど。
だから、正しいデータを選択しなければならなかった これらのカラムの両方の型。
これらの両方は、いくつかを有する それらについての事、その
選択を困難にする。
だから、INTは有効ではありませんでした 番号を入力します。
その理由は、12桁のアカウントであること 番号は、INTがするのに十分な大きさではありません
合計の数字を格納します。
だから、有効な選択肢は、ビッグだっただろう あなたがそれを知っているために起こる場合int型。
別の選択があったかもしれない 長さ12のCHARフィールド。
ので、これらのいずれかが働いていただろう。
INTはないでしょう。
>> 今、バランス、バックpset7と思います。
だから我々は、具体的には、小数点を使用 株式の価値を保存したり -
>> DAVID J.マラン：現金。
>> ROBボーデン：現金。
我々の量を格納するために小数を用い ユーザーが現在持って現金。
だから我々はそれを行う理由は、 覚えているので、浮遊する。
精度の浮動小数点があります。
それは、正確に現金を保管することはできません 我々のような値がここに欲しい。
だから、小数は正確に記憶することができる 、言いたい、小数点以下。
バランス、我々はそれをしたい理由です フロートは、小数点とされていないと。
>> DAVID J.マラン：そしてまた、あまりにも、しかし それは他で賢いだったかもしれない
考えるコンテキスト、多分これ int型のためのチャンスです。
私はちょうどを記録しておこう ペニーにあるもの。
我々は、明示的にデフォルトを示したので、 その100.00であることの価値、
それだけでINT可能性を意味します。
あまりにも数が別の微妙 それが意味されていなかったということでした
トリックの質問であると。
しかし、MySQLで、そのINTを思い出す 少なくともにおいては、C言語のように
アプライアンスは、32ビットである。
そして、我々はすることを期待していないにもかかわらず、 正確に何桁ことを知っている
手段は、最も多くのことを思い出してやる あなたは、潜在的に表すことができます
32ビットの数値で、ほぼ何ですか？
>> 私たちは常にお客様番号を言うのですか？
何およそ32、2？
あなたは正確に知っている必要はありません。
しかし、大体の生活に役立ちます。
これは、およそ40億だ。
だから我々は何度かあることを言ってきた。
私が知っている私は何度か述べている。
そして、それはおよそ40億です。
そして、それは良いルールだ 親指の知っている。
あなたが8ビット、256を持っている場合 マジックナンバーです。
あなたは32ビットで、4を持っている場合 億は与えるか、または取る。
だから、あなただけの40億を書き留めている場合、 あなたはそれがより少ない数字だということがわかります
それがはっきりしないということだ12、 キャプチャするための十分な表現力
12桁の口座番号。
>> ROBボーデン：わかりました。
だから、他のものは良く行きました。
だから、銀行と仮定 毎月20ドルを課し
すべてのアカウントでの維持費。
どのようなSQLクエリ可能性があり、銀行との 場合でも、すべてのカウントから20ドルを差し引く
それはいくつかの負の残高になり？
そこで、基本的に、4があります クエリの主な種類 -
挿入、選択、更新、および削除する。
だから我々は我々がしているものだと思いますか ここで使用するつもり？
アップデート。
>> それでは見てみましょう。
そこでここでは、更新している。
どのようなテーブル、我々はアカウントを更新している？
だから、アカウントを更新する。
して、構文は、言っていること 口座に我々は更新している？
まあ、我々と同じバランスを設定している バランスはマイナス20の現在の値。
だから、これはすべての行が更新されます アカウントの減算
残高から20ドル。
>> DAVID J.マラン：ここによくある間違い、 我々は時々それを許したとしても、
実際にここPHPコードを持っていることだった クエリ関数を呼び出すか、置く
そのすべてを引用符で囲む そこにある必要はありませんでした。
>> ROBボーデン：MySQLがあることを忘れないでください PHPとは別の言語。
私たちは、PHPでMySQLを書き込むことが起こる。
そしてPHPはそれからのお届けとなります MySQLサーバにフェールオーバ。
しかし、あなたがするためにPHPを必要としない MySQLサーバと通信します。
>> DAVID J.マラン：その通りです。
ドル記号を持つので、何の変数ません このコンテキスト内にある必要があります
それはちょうど、数学のすべてを行うことができます データベース自体の内部。
>> ROBボーデン：わかりました。
ので、次の1。
これは、次の1か？
うん。
それでは、SQLクエリを使用して銀行でし そのの口座番号を取得
豊かな顧客を有するもの 千より大きい残高？
だから、4つの主なタイプのどの 我々はここにしたいとしていますか？
選択してください。
だから我々は選択したい。
我々は選択しますか？
我々は選択することが何列たいですか？
我々は、特にお勧めします 番号を選択します。
しかし、あなたは星を言ったならば、我々 また、それを受け入れた。
>> それがどうしたテーブルから番号を選択？
アカウント。
そして、我々が望む条件？
どこ千より大きいバランス。
我々はまた、より大きな受け入れ よりか等しい。
ラスト1。
どのようなSQLクエリ可能性があり、銀行との 近く、すなわち、すべてのアカウントを削除するには、その
0ドルの残高を持っている？
だから、四つのどれウィーアー 使用したいとして？
削除します。
だから、そのための構文は？
どのテーブルから削除しますか？
アカウント。
そして、条件、その上に 我々は、削除したい -
残高がゼロに等しい。
だから、アカウントからすべての行を削除 残高はゼロである。
これらのいずれかに関する質問？
キューしてみませんか？
>> DAVID J.マラン：キューガイド。
そのため、この1で、私たちはあなたにいくらかを与えた 我々は探検おなじみの構造
構造体と一緒にクラスのビット、 データだった
精神に関連する構造。
キューにも違いがある 我々は何とか覚えなければならなかったことを誰
大規模で、キューの先頭にあった 一部我々はより多くを作ることができるように、
少なくとも、メモリの効率的な利用、 我々は、配列を使用していた場合。
>> リコールするので、我々は、配列を持っている場合、もし、 例えば、これは、目の前である
キュー、私はここで待ち行列に入る場合には、 そして、誰かがラインに入った
私の後ろに、私の後ろに、私の後ろに、と 1人がラインを抜け出し、あなた
私たちは私たち人間のいくつかを見たように、可能性 クラス内のボランティアは、誰もが持っている
このようにシフトする。
しかし、一般的に、誰もがやるた 何かが時間を最大限に活用ではありません
プログラムでは、それはあなたのことを意味するからだ アルゴリズムとは何で実行されている
漸近実行時間？
それは線形です。
>> それはちょっと愚かだように、私は感じています。
ライン内の次の人が次の場合 に入ることになっている人
店舗、それらはすべて持っていない 一緒に移動します。
ただ、その人がオフに摘み取らとする 時間は、たとえば、来るとき。
だから我々はそこに少しの時間を節約することができます。
だからその手段は、しかしそのためには そのキューの先頭または
キューの先頭をしようとしている 徐々に深く深く移動
配列にし、最終的にかもしれない 我々は使用している場合、実際にラップアラウンド
人々を格納する配列 このキューにある。
だから、ほとんど考えることができます 円形のデータとして配列
その意味で構造。
>> だから、何とかを追跡する必要があります 実際にそれの大きさやそれの終わり
そして、それの始まりです。
だから我々はあなたが宣言することを提案する 呼び出し1、キュー、
それをQ、ちょうど1手紙。
その後、我々は前にすることを提案 ゼロに初期化し、その大きさ
ゼロに初期化する。
>> だから、今は何もありません そのキューの内側。
そして、我々は、完了するかを尋ね 中下のエンキューの実装
関数はnに追加されますよう その後、Qの終わりとtrueを返します。
しかし、qは完全であるか負である場合には、 この関数は代わりにfalseを返す必要があります。
そして、我々はあなたにカップルを与えた 仮定の。
しかし、彼らは本当に機能的じゃない 関連する、ちょうどそのBOOLは存在しますが、
なぜなら、技術的には、BOOLにはない あなたが含まれていない限り、Cに存在する
特定のヘッダファイル。
だから、そこを確認してくださいました NOこれはトリックではないし、
事の質問一種。
>> 我々は、サンプルで提案されているので、エン 解決策次のように実装する。
一つは、我々は最初の使いやすさをチェックし、 低ぶら下げ果物。
キューが満杯または番号である場合は、その あなたが挿入しようとしている小さい
私たちが言っゼロ、より 問題の仕様べき
我々は唯一たいので、許可されない そしてあなたはあるべきであるが、負の値、
ただすぐにfalseを返します。
ので、いくつかは比較的容易 エラーチェック。
あなたはその実際を追加したいかの場合 数には、少しをしなければならなかった
ここに考えて。
それはちょっと迷惑なんだどこに、これはある 精神的に、あなたがしなければならないので
ラップアラウンドを処理する方法を見つけ出す。
>> しかし、のだここでの考え方の生殖に 私たちに関心がそのラップアラウンドです
多くの場合、モジュラー演算を意味し、 mod演算子、パーセント側、
あなたは大きな値から行くことができますどこ ゼロにして、1と2と
3、その後戻って周りのゼロに、 1と2など3および
何度も何度も。
だから我々はこれを行うことを提案の方法です 我々はにインデックスを作成するということ
数字どこと呼ばれる配列 私たちの整数は嘘。
しかし、そこに到達するためには、まず何をしたい キューのサイズがあるが何であれ
その後、どのようなものに追加 リストの先頭です。
そして、それの効果はで私達を置くことです キュー内の正しい位置と
行の最初の人と想定していない 先頭にあり、その彼または
彼女は絶対になることができれば我々 また、すべての人をシフトされた。
しかし、我々は単に仕事を作成している 自分のために私たちがかかった場合
その特定のパス。
>> だから我々は、比較的単純な、それを維持することができます。
我々はちょうどその私たちを覚えておく必要があります キューにint型を追加しました。
そして、我々は単にtrueを返す。
一方、デキューでは、我々は尋ねた あなたは以下を実行する。
このような方法でそれを実装することを、それ デキュー、つまり、除去·リターンである、
キューの先頭にint型。
int型を削除するには、それが十分である それを忘れている。
あなたは、そのビットをオーバーライドする必要はありません。
だから、実際にそこにまだある。
ただ、ハードドライブ上のデータのように、 我々だけで事実を無視している
それはそこになりましたということ。
Qが空である場合、我々はすべき 代わりに負の1を返す。
だから、これは任意で感じている。
なぜ負の戻り1 代わりに、偽？
うん。
>> 観客：Qが収納されている 正の値。
あなたは正の値のみを格納しているため Qは、負はエラーになります。
>> DAVID J.マラン：OK、真。
だから我々は唯一の肯定を保存しているので、 値またはゼロは、それはにいいのよ
センチネルとして負の値を返す 値、特殊記号。
しかし、あなたは、そこに歴史を書き換えている なぜなら我々は唯一だ理由
負でない値を返す 私たちがしたいからです。
標識値を持っている。
より具体的には、なぜだけではなく、 エラーの例ではfalseを返す？
うん。
>> 読者：あなたが失敗しました 整数を返す。
>> DAVID J.マラン：その通りです。
Cが取得する場所と、これはある かなり制約。
あなたが行っていると言っている場合 int型を返すには、持っている
int型を返すことができます。
あなたは空想取得し、戻って起動することはできません BOOLまたはfloatまたは
文字列またはそのような何か。
さて、一方で、JavaScriptとPHPと いくつかの他の言語ができ、実際には、
あなたが異なる戻ってきた 値の型。
そして、それは実際にどこで、便利です あなたは正整数、ゼロを返すことができ、
負の整数、またはFALSEまたはNULL でも、エラーを示すために。
しかし、我々はそれを持っていない Cの汎用性
>> そうデキューと、私たち で行うことを提案する -
>> ROBボーデン：あなたはfalseを返すことができます。
それは、ハッシュだけでは偽ですそれは ゼロにfalseを定義します。
だから、falseを返した場合、 あなたは、ゼロを返している。
ゼロは、我々のキューで有効なものですが、 負の1に対した場合ではありません
偽は、負の1であることを起こった。
しかし、あなたもいけない それを知っている必要があります。
>> DAVID J.マラン：それです。 なぜ私はそれを言わなかった。
>> ROBボーデン：しかし、それは本当ではなかった あなたはfalseを返すことができない。
>> DAVID J.マラン：確かに。
我々は受け入れるので、デキュー、予告 引数として無効になる。
そして、我々はわからないので、それはだ インチ何を渡す
我々だけで要素を削除したい キューの先頭に。
では、どのように我々はこれをやって行くのでしょうか？
さて、まず、これをやらせる 迅速な健全性チェック。
キュー·サイズが0の場合、そこ なすべき仕事ません。
負の1を返します。
行わ。
だから、私のプログラムの数行です。
だから、唯一の4行が残っている。
>> だからここに私はデクリメントすることにした サイズ。
かつ効果的にサイズをデクリメント 私が忘れていることを意味します
何かがそこにある。
しかし、私はまた更新する必要がどこに 数字の前にある。
そうそのためには、私が必要とする 2つのことを行う。
私が最初にどのような番号を覚えておく必要があります キューの先頭にある、
私はそのことを返す必要があるため。
だから私はうっかり忘れたくない それについて、それを上書きします。
私はint型で覚えておくつもりです。
>> そして今、私が更新したい 1をq.frontするq.front。
これがの最初の人だった場合 ラインは、今、私はプラス1をやってみたい
ライン内の次の人を指す。
しかし、私はラップアラウンドを処理する必要があります。
容量がグローバル定数である場合、 それは私が確認するためにできるようになるだろう
私はで非常に最後の人を指すように ライン、モジュロ演算がもたらす
でゼロに私の背中 キューの先頭。
そして、それはここでラップアラウンドを処理します。
そして私は、nを返すように進んでください。
>> 今、厳密に言えば、私はしませんでした Nを宣言する必要があります。
私はそれを取得し、それを格納する必要はありませんでした 一時的に、値であるため
まだある。
だから私はちょうど算術を行うことができます 元ヘッドを返す
キューの。
しかし、私はちょうどこれがより明らかになったと感じていた 実際にint型をつかむために、それを置く
nは、その後、それを返す 明瞭化のためではなく、
必ずしも必要ではありません。
PSST。
彼らはすべての私の頭の中で発音している。
>> ROBボーデン：だから最初の質問 二分木の問題がある。
だから、最初の質問は、私たちがしている、ある これらの数字与えられ。
そして、我々は何とかにそれらを挿入する これらのノードは、であるような
有効な二分探索木。
だから一つのことについて覚えて 二分探索木はそうでないということです
ちょうどその左の事 が少ないとの事です。
右は大きい。
それがする必要があるとツリー全体へ 左が少なく、ツリー全体
右に大きい。
>> だから私がトップでここに34を入れた場合、その後、 私はここで20を置くので、それはとても有効なの
ここまで、34まで、ここからです。
20は左に行っている。
だから少ないです。
しかし、私はそれから、ここに59を置くことができないため、 59は、20の右側にあっても、
それは34の左側にはまだです。
このことを念頭に置いての制約とそう、 おそらく、これを解決する最も簡単な方法
問題は、単にソートすることです。 これらの数の -
そのように20、34、36、52、59、106。
次にそれらを挿入 左から右へ。
>> だから20がここに入ります。
34がここに入ります。
36がここに入ります。
52、59、106。
そして、あなたはまたして考え出したかもしれない 中には、プラグインすると実現
ああ、私は十分な数字を持っていない、待って こっちでこれを埋めるために。
だから私は何を私のreshiftする必要があります ルート·ノートでは、になるだろう。
しかし、もし、最後の3つの中のことに気付く あなたが左から右に読んで、それがである
昇順。
>> だから今、私たちは何を宣言したい 構造体は、ためになるだろう
このツリー内のノード。
だから我々は、二分木に何が必要ですか？
だから我々は、型の値を持っている int型なので、いくつかのint型の値。
私は我々が呼ばれるかわからない 溶液中で -
N int型。
我々は左の子へのポインタを必要とする そして右の子へのポインタ。
だから、このように見えるようになるだろう。
そしてそれは実際に前に見ていきます 二重リンクなかったとき
リストのものなので、通知 -
私はすべてにスクロールする必要がありますするつもりだ 帰りダウン問題11へ。
>> だから、これと同じに見えるに気付く、 私達はちょうどこれらを呼び出すことが起こる除く
別の名前。
我々はまだ、整数を持っている 値と二つのポインタ。
それ扱うのではなく、まさにそれだ 次の事を指すようポインタ
と前の事は、我々は治療している ポインタは左の子を指すように
そして右の子。
[OK]をクリックします。
だから、私たちの構造ノードの。
そして今、唯一の機能は、私たちのことを行う必要があり これはトラバースであるため、実装している
私たちは、木の上に行きたい、印刷 順にツリーの値が不足しています。
>> だからここを見ると、印刷したいと思う アウト20、34、36、52、59、および106。
どのように我々はそれを達成するの​​ですか？
だから、それはかなり似ている。
あなたは過去の試験問題を見た場合 あなたがプリントアウトしたいと
その間にカンマでツリー全体 すべてのもの、それも、実際にあった
それよりも容易になります。
だからここソリューションです。
これはかなり簡単だった あなたは再帰的にそれをしなかった場合には。
誰も試みたかどうかは知りません 反復的にそれを行うには。
>> しかし、最初に、我々は我々のベースケースを持っている。
何ルートがnullの場合は？
その後、我々は単に返すようになるだろう。
私たちは、何も印刷しない。
他に私たちは横断しようとしている 再帰的にダウン。
全体の左部分木を印刷します。
だから、あまり、すべてを印刷する 私の現在の値よりも。
そして私は自分自身を印刷するつもりです。
そして私は私を下に再帰的にするつもりだ 全体右部分木なので、すべてのもの
私の値よりも大きい。
そして、これは、印刷しようとしている 順番にすべてのものが不足しています。
どのようにこの実際に質問 それを実現する？
>> 読者：私は疑問を持っている [聞こえない]に。
>> ROBボーデン：近づくので、一つの方法 任意の再帰的な問題だけで考えることです
それについてあなたが考えなければならないように すべてのコーナーケースについて。
だから我々がしたいと考えている このツリー全体を印刷します。
したがって、すべての私たちは、に焦点を当てるとしている この特定のノードである -
36。
再帰呼び出しは、私たちはふり それらはただ働く。
だからここに、この再帰呼び出し でも何も考えずに、私たちを通過
それについてだけ左をトラバース 3、すでに20を印刷していることを想像する
そして私たちのために34。
して、ときに我々最終的に再帰的に 上のトラバースを呼び出す
右、それが正しく印刷されます 52、59、そして私たちのために106。
>> だから、これは20、34を印刷することができますことを考えると、 もう一つは、52、59、108を印刷することができます
我々が行うことができるように必要なものはプリントです それの真ん中に私たち自身。
だから私たちの前にすべてのものをプリントアウトする。
私たち自身を印刷するため、現在のノードを印刷 36、定期的なprintf関数、その後、
私たちの後にすべてを印刷します。
>> DAVID J.マラン：これはどこ再帰です 本当に美しい取得します。
それは、信仰のこの素晴らしいLEAPのWHERE あなたは仕事の最も小さいビットを行う。
それから、あなたは誰かを聞かせて 他の残りの部分を行う。
そして、そのほかの人 あなたは、皮肉なことに、ある。
深刻なブラウニーポイントの場合、もしそうであれば あなたが質問にスクロールアップ -
>> ROBボーデン：質問か？
>> DAVID J.マラン：およびTo少しダウン ここでの数字は、誰もが知っていますか
これらの数字から来るの？
>> ROBボーデン：私は、文字通りは考えている。
>> DAVID J.マラン：彼らが表示される クイズを通して。
>> 読者：彼らは同じ番号はありますか？
>> DAVID J.マラン：これらの数字。
小さなイースターエッグ。
だから、オンラインで見ているあなたのそれらのために 家は、次の作業を行う電子メールによって私達に伝えることができた場合
heads@CS50.net何の意義 これらの定期的な6つの数字の
クイズ1を通じて、私たちはあなたをシャワーします 最終的に驚くほどの注意を払って
講義やストレスボール。
素敵な、微妙。
>> ROBボーデン：どれでも過去の質問 クイズには何でしょうか？