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ボーデン：どれでも過去の質問 クイズには何でしょうか？