[Powered by Google Translate] [第6週] [デビッド·J·マラン] [ハーバード大学] [これはCS50です。] [CS50.TV] 、これはCS50であり、これは第6週の始まりですように、新しいツールのカップルは、今、あなたが利用するために用意されてい CS50スタイルと呼ばれる最初の。あなたは私かティーチングフェローのいずれかのようにしている場合オッズは、あなたはおそらく、そのスタイルこのような少し何かを探し、プログラムを見てきました。、たぶん、あなたは夜遅くいくつかのコーナーをカットし始めるか、後でそれに対処しますその後TFまたはCAが勤務時間中にやってくる。私たちが読むことが、それは難しい。さて、このコードは、構文的には正しいのですが、それがコンパイルされ、それが実際に実行されます。しかし、それは間違いなくスタイルの5ではありません。しかし、今、我々はこのディレクトリに行けばここ - と私はconditions2.cを持っていることに気付くと私はstyle50、この新しいコマンドを実行すると、このファイルconditions2.cに、入力それはそれが定型化されてきたことを私に伝えていることに気づく。 Geditは、ファイルがディスク上で変更されたことに気づいた私はリロード]をクリックした場合と、すべての問題は現在、自動化されています。 [拍手] それは我々がこの週末やってたことの一つだ。いくつかのコードがあるので、それが不完全であることを認識それは単に完全に型にはめることができないだろうということ、しかし、これは今、あなたが利用することができるツールであると認識より誤って配置され、中括弧の一部を片付けるなどにいる場合のみです。しかし、もっと説得力のある今は、CS50チェックです。 CS50チェックを使用すると、実際には同じ正当性のテストを行うことができます教える仲間ができることを自分のコードに。これは、アプライアンスに今来るコマンドラインユーティリティですできるだけ早くあなたが当たりとしてupdate50を行うように PSET 4仕様、あなたはこのように本質的にそれを使用します。は、コマンドcheck50を実行します。次に、コマンドライン引数を渡す、あるいはより一般的に、スイッチまたはフラグとして知られている。一般的には、ハイフンを持っているものはスイッチと呼ばれますので、-cが指定するコマンドラインプログラムへ実行したいかどうかをチェックします。実行したいテストは、この文字列によって一意に識別され 2012/pset4/resize。言い換えれば、それはただの任意ですが、ユニークな文字列です我々は一意のpset 4の正当性のテストを識別するために使用する。そして、あなたがアップロードしたいファイルをスペースで区切ったリストを指定分析用CS50チェックする。例えば、私はここに私のために溶液中に行けばresize.c- 私は大きなターミナルウィンドウを開いてみましょうと私は先に行くとのはcheck50-C 2012/pset4/resizeを、言わせて実行するそして私は、先に行くと、ファイルの名前を指定 resize.c、次に、それは圧縮し、Enterキーを打つそれをアップロードし、それが確認され、私はただテストの全体の束を失敗しました。左上の赤ではresize.cとbmpが存在することを言う。それはテストだった。それは我々が尋ねた質問だった。答えが偽だったので、それは不幸だ。その下の白い文字が存在するbmp.h期待されており、それは単に私のせいだと言う。、私はそれをアップロードするのを忘れたので、私は両方のファイルをアップロードする必要があります resize.cとbmp.h. しかし、今は他のすべてのテストに気づく、彼らが実行していないので、黄色であり、と彼はどちら幸せも悲しいですので、スマイリーフェイスが垂直で、しかし、我々はそれらの他のチェックが実行される前に、赤でその問題を是正する必要があります。私は、この問題を修正しましょう。またbmp.hとこの時間、私はズームアウトしてこれを再実行してみましょうすべてがうまくいけば、コマンドラインで、今入力して、それはチェックしてから、息をホールドの結果を返すために起こっているこれまでのpset 4日に、私は本当によくやっていることを意味し、すべての緑。あなたが見て、ここに記述したテキストから推論することができるそれは我々がテストされているかを正確に。私たちは、最初のファイルが存在しないテスト？次にresize.cコンパイルを行いテスト？その後、我々は、n、リサイズ係数が1であるときに、それが1x1ピクセルのBMPのサイズは変更されませんテストされています。もしnが何であるか見当がつかない場合、今、あなたは一度、PSET 4に飛び込みましょうそれは単にあなたがリサイズじゃないことを確認するために健全性チェックですサイズ変更係数が1であれば、すべての画像。対照的に、それが正しく2x2のに1x1ピクセルBMPに1x1ピクセルのサイズを変更した場合 nが2の場合、その後同様に、鉱山はそれに応じて形成される。要するに、これが意図され、1、交差指を取る右のあなたの前の式のうちあなたのpsetを提出してください。あなたのTFはすぐに知っているかを正確に知っているでしょうあなたはこれらの問題セットの一部を提出しようとするなら、また、教育的な動機が入れて本当にですかが、事前に知っているように、あなたの目の前の機会コード内のバグと渡されていないテストは、そこだとあなたはそれらの問題を解決するために前もって、より効果的な時間に置くことができるポイントを失うのではなく、あなたのTFからのフィードバックを得るため、私がいることを考え出したはずのようにしてから、 "ああ、"行く。少なくとも今あなたがそれを見つけるのに役立つツールがある。それはバグがどこにあるかを指摘するつもりはないが、それはあなたを教えてくれますそれの症状は何です。今すぐテストは必ずしも網羅的ではない実現する。あなたは緑のスマイリーフェイスのフルスクリーンを取得したからといってあなたのコードは完璧であることを意味しませんが、それはどういう意味それは仕様で規定され、特定のテストに合格していること。時には我々はチェックを解放しません。例えば、推理小説、PSET 4の側面の一つ、私たちはあなたに失望の種類を与えるされている場合それが何であるか、そして明らかに、いくつかの方法があるように答え人はあの赤いノイズで誰だ。スペックはいつものpset 5以降のために、将来的に指定します何があなたのために存在をチェックします。あなたは、一番下にあるこの白いURLはそこに気づくでしょう。今のところ、これはただの診断が出力されます。あなたがそのURLを参照してください場合は、狂気、不可解なメッセージの全体の束を買ってあげるあなたは目を通すために歓迎しているが、それはスタッフのために主だということので、我々は診断とcheck50自体のバグをデバッグできること。騒ぎがなければ、のは、我々が去ったところに移りましょう。何週間か当たり前の我々が取ったCS50ライブラリ、しかしその後、先週、我々はそれの層の1つを戻して剥離開始しました。我々はその代わりに何を支持して文字列をどかし始めた？ [学生]シャア。 char *をchar *になっている、すべてのこの時間、しかし、今我々はそれが実際のデータ型は文字列だというふりをする必要はありません。むしろ、それは、char *のための一種の同義語であってと文字列は、文字の並びですなぜそれはchar * sと文字列を表現するのは意味がない？ char *は、文字列のこの概念の文脈で何を表しているのでしょうか？うん。>> [生徒]の最初の文字。良い、最初の文字が、最初の文字はなく、かなり。それは - [生徒]アドレスです。良い、最初の文字のアドレス。コンピュータのメモリに文字列を表すために必要なのは、すべてのただ、非常に最初のバイトの固有のアドレスです。あなたも、それがどれくらい長いか知っている必要はありませんどのように動的にそれを把握することができるので？ [学生]文字列の長さ。あなたは、優れた、文字列の長さを呼び出すのではなく、どのように文字列の長さの作業を行うことができますか？それは何をしますか？うん。 [学生]は、ヌル文字を取得するまでも継続します。うん、正確には、それだけで、whileループ、forループで繰り返し処理 *から最後まで何でもあり、端が表されている \ 0で、いわゆるヌル文字、NUL、ヌルポインタである、と混同しないようにそれは今日も会話の中で出てくる。、我々は戻っ場合、getIntの層を剥離した後、我々は、GetStringメソッドを見ていたそして、実際にはこれらの機能の両方ことを思い出したり、 GetStringメソッドは、特定の機能を使用していた実際に、つまり、読み取りまたは分析し、ユーザーの入力を解析します。その新しい機能は何でしたか？ scanf関数またはsscanf関数。これは、実際にはいくつかの異なる種類があります。 scanfがあり、sscanfがあり、fscanfはそこだ。現在のところ、最も容易に示されたものに集中させるのは、と私が先に行くと、アプライアンスで開くことができこのようなファイルは、scanf1.c。これは、超簡単なプログラムです。しかしそれは我々がやったことがないことを何かをする CS50ライブラリの助けなし。これは、ユーザーからintを取得します。それはどのように動作しますか？まあ、ラインが16で、我々は、xという名前の整数型変数を宣言することがわかり、そして物語のこの時点では、 xの値は何ですか？ [聞き取れない生徒の応答] [デイビッドM.]潜在的に、いくつかのゴミの価値を知っている右は、そう17で、我々だけでユーザに伝えるしてください、私に番号を与え、それが面白いところステップ18です。 scanf関数は、それが引用符でこれらの書式コードを使用する点でのprintfからアイデアを借用しているようだ。％dはもちろんの10進数です。しかし、なぜ私は＆Xだけではなく、xに渡すのですか？前者は正しいです。うん。 [聞き取れない生徒の応答] まさに、このプログラムの目的であれば、関数の場合、getInt自体が好きで、ユーザーからintを取得することです私は、関数を渡すことができます。私はしたいが、私は参照渡ししない場合、すべての変数またはポインタのアドレスによって、または、今日の目的のためにすべての代名詞、その関数がその変数の内容を変更する機能はありません。これは単にスワップのバギー版のようにコピーを渡したい我々は今、何回か話をしたこと。しかし、その代わりに、やっ＆xで、私は文字通り何を渡したんだけど？ [学生]アドレス。>> xのアドレスを。それは、scanf関数は呼び出された関数にマップを描画し、ここで言ってようなものだこれらは、コンピュータのメモリのチャンクへの方向であるあなたはインチいくつかの整数を格納行くことができる sscanfが今、それを実現するためには何オペレータ、どのような構文の一部、それは使用するために持っているとしている他の誰かがこの関数を書きましたので、我々はそれを見ることができないにもかかわらず？言い換えれば - それは何ですか？ [学生] X読んだ。そこにいくつかの読書になるだろうが、ここでしかXに関してだ。 scanf関数は、xのアドレスを渡されている場合構文的には、どのような演算子がどこかに存在するためにバインドされそのscanfのようにscanf関数の実装の内部実際にそのアドレスに2番を書き込むことができますか？ええ、そう*。 *は本質的にそこに行くことを意味私たちの逆参照演算子であることを思い出してください。ケースがここにあるようにしたら、アドレスを渡されてきたが、 scanfはおそらく、場合、私たちは実際にそのソースを見回しコード * xまたは実際にそのアドレスに移動して、そこにいくつかの値を置くために同等のものをやっている。さて、scanf関数は、キーボードからの入力を取得する方法のために、我々は今日のための私達の手を振るよ。ちょうどオペレーティングシステムが話をすることはsscanfができていると仮定ユーザーのキーボードのが、今は19行目のこの時点で、我々は単にxをプリントアウトするとき、それはケースのように思われるそのscanfはxにintを入れている。それはまさにscanf関数がどのように動作するかだし、先週リコールそれは正確にどのようにGetStringメソッドとgetIntおよび機能のそのほかの家族の最終的にはsscanfのような若干の差異はあるものの、動作しますが、これは、キーボードの代わりに文字列をスキャンすることを意味します。しかし、ここではこの少しの差異を見てみましょう。 scanf2では、私は実際にしくじった。何が間違っていると私はできるだけ多くを説明するコメントを非表示にしますバージョン2は、このプログラムを使って何が間違っている？この時、できるだけ技術的なこと。これはかなりよさそうだ。それがうまくインデントが、-Aの大丈夫、方法についての質問には短く、それをダウンプルーン聞かせて？ 16行目。しかし正確な技術英語でやって16行目は何ですか？少しぎこちない取得。はい、マイケル。 [学生]これは文字列の最初の文字を指している。さて、閉じます。私はそれを少し微調整しましょう。文字列の最初の文字を指すようにすれば、あなたは、変数と呼ばれるバッファを宣言しているつまり、文字列の先頭アドレスを指すようになりあるいはむしろ、それは、より具体的にchar型を指すことになります。全く代入演算子がありませんので、それは実際にはどこにも指していないことに気づく。そこには等号ことではありませんので、我々がやっているすべての変数と呼ばれるバッファを割り当てている。それがポインタだから、それは、32ビットであることを起こるバッファの内容おそらく最終的には char型のアドレスが含まれますが、今のバッファは何が含まれているのでしょうか？ただいくつかの偽の、誰が知っている、いくつかのゴミの価値、我々はそれを明示的に初期化されていないため、私たちは何かを仮定するべきではありません。わかりましたので、今では17行目では、何をされている17行目は何でしょうか？たぶんそれはこの上を暖めます。それは右、文字列を出力します？これは、文字列が出力されてください。 18行目は、我々はちょうどこれの差異を見たことが今ではおなじみの一種であるしかし別の書式コードを持つので、18行目で、我々はここでscanfを言っているメモリの塊のアドレスです。％sによって暗示として、私は、あなたが文字列で鳴らしたいしかし、問題は私たちがここで物事のカップルを行っていないということです。問題の一つは何ですか？ [学生]それはNULLポインタを逆参照しようとしている。良い、nullまたはそうでなければ単に未知のポインタ。あなたは、scanf関数にアドレスを渡していますが、さっき言った我々は実際には何に割り当てていなかったため、そのアドレスはいくつかのゴミ値であること、ので、scanfを言っていると効果的に、ここに文字列を入れて行くここではまだですが、私たちは、知らないので、我々は実際にバッファ用のメモリを割り当てていない。また、あなたも、scanfを語っていないにも何ですか？これはメモリの塊だったと仮定し、それはガベージ値ではありませんでしたしかし、あなたはまだ重要scanfの何かを言っていない。 [学生]それが実際にある場合には、アンパサンド。アンパサンドので、この場合、それは大丈夫です。バッファはすでにポインタとして宣言されているため、構文の*部分で、我々は、アンパサンドを使用する必要はありませんので、それはすでにアドレスだが、私は私がここでそれを聞いたと思う。 [学生]それはどのくらいですか？良い、私たちは、このバッファがどの程度の大きscanfを語っていないしているこれは、バッファがポインタであったとしても意味我々はscanfを言っている、ここに文字列を入れて、しかし、ここ2バイトかもしれない、それは10バイトかもしれない、それはメガバイトである可能性があります。 scanfはない考えを持っているが、これはメモリの塊であるため、おそらく、それはまだ文字列ではありません。あなたは文字やメモリのチャンクに\ 0を書き込むいったん文字列のみです。今度はそれは単にメモリの塊だ。 scanf関数はそのアドレスへの書き込みを停止したときに知ることができません。あなたは、私がランダムにキーボードで入力した過去のいくつかの例を思い出してみるとバッファをオーバーフローしようとしている、と我々は正確にそれについては金曜日に語った。敵は何とか自分のプログラムにはるかに大きい単語を注入した場合または文章やフレーズは、次にあなたがオーバーランが発生する可能性が期待していた悪い結果をもたらす可能性があるメモリの塊、全体のプログラム自体を引き継ぐように。我々は何とかしてこの問題を解決する必要があります。私はズームアウトして、このプログラムのバージョン3に行こう。それは少し良いです。このバージョンでは、違いに気付く。 16行目では、私は再び、変数と呼ばれるバッファを宣言していますそれは今何ですか？これは、16文字の配列です。これが意味するのは、私は今、scanfを伝えることができるので、これは良いですここでメモリの実際のチャンクです。あなたはほとんど、今のポインタとして配列を考えることができます彼らは実際には同等じゃないのに。彼らは異なった文脈で異なる振る舞いをします。しかし、それは確かにバッファが参照している場合だ 16個の連続した文字は、その配列が何であるかだからそして今ではいくつかの週のためになっています。ここでは、私がここでscanfを語っていると、メモリの塊だ。今回は、実際にメモリの塊だしかし、なぜこのプログラムはまだ悪用される可能性がある？まだ何が悪いのでしょうか？私は私に16バイトを与えると言ったが、き [学生]彼らは16以上で入力したら？正確には、どのような17文字または1700文字で、ユーザがタイプかな？実際には、我々は今、この間違いつまずかないことができるかどうかを確認してみましょう。それは良いが、完璧ではありません。私が先に行くと、このプログラムをコンパイルするscanf3をmakeを実行してみましょう。こんにちは、私たちは大丈夫と思われる：文字列、私はscanf3を実行してくださいすることができます。私はこんにちはそこに、少し長めのものを試してみましょう。さて、入力し、今日お元気ですかこんにちはのをやってみましょう。ここで幸運の種類を取得、のはどのようにあなたがいるそこに挨拶しましょう。ちくしょう。さて、私たちは幸運。我々はこの問題を解決できない場合は、見てみましょう。いいえ、それは私がコピーできることはないだろう。のは、再びこれを試してみましょう。すべての権利は、そばに立つ。我々は、私はまだこれをしている間集中するふりをすることができますどのくらいの期間が表示されます。ちくしょう。それは実際、むしろ適切です。そうしよう。ポイントは作った。これは、それはまたですが恥ずかしい、それはまた、偉大な混乱の源の一つである彼らが姿を現すので、バグがあるプログラムを作成するとき唯一たまに時々。現実には、あなたのコードが完全に壊れている場合でも、ということであるそれだけであり、これは完全にたまには壊れているかもしれません時には、本質的に何が起こるかは、オペレーティング·システムの割り当てであるため、あなたが実際にどのような理由のために必要なよりも少し多くのメモリ、など誰もが、右に16文字のあなたのチャンクの後にメモリを使用していないあなたは、17、18、19、何でも、それはそのような大したことではありませんに行くので、もし。さて、コンピュータ、それがその時点でクラッシュしていない場合でも、結局、何か他のもののためのバイト数17または18または19を使用する場合があります、その時点で、あなたはそこに置かれていること、データ、過度に長いとはいえ他のいくつかの関数によって、潜在的に上書きしようとしている。それは必ずしも、そのまま残ることはないだろうそれは必ずしもワンセグ障害を引き起こすことはありません。しかし、この場合には、私は最終的に十分な文字を提供私は基本的に私の記憶のセグメント、およびBAMを超えたことオペレーティングシステムは、 "申し訳ありませんが、それはダメ、セグメンテーションフォールトません"と述べた。そして、何が私にここに残っている今見てみましょうディレクトリ私は、ここでコアをこのファイルを持っていることに気づく。これは再びコアダンプと呼ばれていることに注意してください。それは本質的にあなたのプログラムのメモリの内容が含まれているファイルですそれがクラッシュした時点で、そしてちょうど私がここで手放すここで少し例を試すと、コアと呼ばれる3番目の引数を指定した後scanf3上でgdbを実行し、そしてここで気づくこと、私はコードをリストする場合は、我々は、このプログラムを通じて歩行を開始するにはgdbといつものようにできるようになりますと私はそれを実行し、できるだけ早く私はとしてヒットとしてGDB-のステップコマンドでできます私は巨大な文字列を入力した後、潜在的にバグのある行を打つとすぐに、私は実際にここでそれを識別することができるでしょう。コアダンプの観点セクションでは、しかし、これについての詳細そしてあなたが実際に内部のコア·ダンプの周りをウロウロすることができるように希望そしてプログラムはあなたを失敗した何行にしてください。次に、ポインタにしてアドレスに何か質問はありますか？今日の、我々は、これらのものは存在していることを当たり前の服用を開始するつもりですので、そして我々は、彼らがしているのかを正確に知っている。はい。 [学生]は、パートの隣にアンパサンドを付ける必要はありませんでしたどのように来る良い質問です。私は以前と同様に文字配列の隣にアンパサンドを付ける必要はありませんでしたどのように来る私たちの例のほとんどは？短い答えは、配列が少し特別なものです。あなたは、ほぼ、実際にアドレスとしてバッファを考えることができますそしてそれはちょうどので、ケースであることを起こることを角括弧記法我々はブラケット0、ブラケット1に入ることができるように便利です *表記を使用することなく、ブラケット2、。それは白い嘘のビットですので、配列とポインタ実際には、少し異なっていますが、それらはほとんどの場合は交換して使用できます。一言で言えば、この関数はメモリのチャンクへのポインタを期待しているときに、あなたはどちらか、それをmalloc関数によって返されたアドレスを渡すことができるそして我々は長い前に再度malloc関数が表示されます、またはあなたはそれを配列の名前を渡すことができます。彼らは既になっているので、配列でアンパサンドを行う必要はありません基本的にアドレスのよう。それは1つの例外です。角括弧は、それらを特別なもの。あなたは、バッファの隣にアンパサンドを置いてもらえませんか。しないこの場合インチこの角の例は、再度、ため動作しないということどこ配列はかなり実際のアドレスではありません。しかし、我々はおそらく、他の例と、そのずっと前に戻るでしょう。ここで問題を解決しようとしてみましょう。我々は配列として知られているいくつかの時間のために使ってきたデータ構造を持っています。ポイントのケース、私達はちょうど持っていたものだ。しかし、配列は、いくつかの五分五分と欠点を持っています。アレイがいいですなぜですか？あなたが好きなツー一つのことは、配列の配列·程度については好きとは何ですか？それらについての便利な何ですか？説得力のある何ですか？なぜ我々は最初の場所でそれらを紹介したのですか？うん。 [学生]彼らは多くのデータを格納することができます、あなたは全体の事を使用する必要はありません。あなたは、セクションを使用することができます。良い、大量のデータを格納できる配列を持つ、とは、必ずしもそのすべてを使用する必要はありませんので、overallocateできますどのように期待するものの多くは、事前にわからない場合に便利であるかもしれない。 GetStringメソッドは完璧な例です。私達によって書かれGetStringを、期待するどのように多くの文字ない考えを持っている、ので、我々は連続したメモリのチャンクを割り当てることができるという事実は良いです。配列はまた、我々は今、数週間前に見た問題を解決するあなたのコードは非常にうまく設計されていない何かに委譲始めるところ。私はデイビッドと呼ばれる学生の構造を作成したことを思い出してくださいその後、それは、しかし、実際には代替あったという変数名と、私が思うに、家と呼ばれる別の変数を持っていることに、その話の中で私はその後、何か他のものをご紹介したかったので、IDと呼ばれる別の変数プログラムにロブが好きなので、私は数分待つことを決め、私は、これらの変数の名前を変更する必要があります。鉱山NAME1、ID1、house1呼び出してみましょう。ロブのNAME2、house2、ID2を呼び出してみましょう。しかし、その後数分待つ、何トミーはどうですか？その後、我々は3つの変数を持っていた。我々は、他の誰か、変数の4つのセットを導入しました。世界は、非常に迅速に厄介になることを始めたので、我々は、構造体を導入し、何はstructについて説得力のあるのですか？ C言語の構造体には、あなたが何をできるのですか？今日は本当に厄介です。何ですか？>> [聞こえない学生の応答] うん、具体的には、typedefを使用すると、新しいデータ型を作成することができ、とstruct、structキーワードを使用すると、カプセル化することができ一緒にデータの概念的関連作品その後、それらの学生のようなものを呼び出す。今我々がモデル化することができますので、それは良かった変数内の学生の概念的一貫性という概念をはるかにソートのではなく恣意的などの文字列の1、ID用のいずれかを有する、と。彼らは私たちが私たちのコードをクリーンアップを開始することを可能にするので、配列はいいです。しかし、欠点は、今度は配列の何ですか？あなたは何ができないのですか？うん。 [学生]あなたはそれがいかに大きいかを知る必要があります。あなたはそれがどの程度の大き知っている必要がありますので、痛みのようなものだ。あなたのそれらは、従来のプログラミング経験を持つことを知っている多くの言語で、 Javaのように、あなたは、具体的には、メモリの塊、配列を求めることができどのように大きなあなたには、長さ、プロパティを使用して、ですが、いわば、それは本当に便利だ。 C言語では、あなたも、一般的な配列でstrlenを呼び出すことはできません strlenのため、言葉が意味するように、文字列にのみ適用されそしてあなたはこのために人間の大会の文字列の長さを把握することができます \ 0が、配列を使用するのではなく、より一般的に、単にメモリの塊です。それはintの配列なら、いくつかの特殊文字があるようにはならないだろう終わりにあなたを待っています。あなたは、配列の長さを覚えておく必要があります。アレイの別の欠点は、自分自身をGetStringメソッドでその頭を飼育。アレイの別の欠点は何ですか？卿は、ちょうどあなたと私は今日。 [聞き取れない生徒の応答] >>それは何ですか？それはスタック上に宣言された。さて、スタック上に宣言された。なぜあなたはそれを好きではないのですか？ [学生]それは再利用されますので。それは再利用されます。さて、あなたがメモリを割り当てるために配列を使用する場合、それはスタック上だからあなたは、例えば、それを返すことができません。さて、それは不利だ。そして、どのように配列を持つ他の1はどうですか？一度それを割り当てるには、より多くのスペースが必要な場合は、ねじ込むの一種だその配列は、持っているより。その後、我々は、私たちに動的にメモリを割り当てるのに能力を与えたリコール、malloc関数を導入しました。しかし、我々は完全に別の世界に何をしようとした場合はどうなりますか？我々はそれらのいくつかの問題を解決したい場合はどうなりますので、代わりに、私のペンはここに眠っているような落ちている私たちが代わりに本質的にこのように、もはやません世界を作成したいと思った場合はどうなりますか？これは配列であり、もちろん、この種のは、かつて我々は、配列の末尾にヒット悪化と私は今はもう別の整数または別の文字のためのスペースがありません。我々は一種の機先を制してよく言うなら、なぜ我々はリラックスしていないものメモリのすべてのこれらのチャンクは、背中合わせに連続していることを、この要件そして、なぜ私はintやcharを必要とするとき、しないでください、ちょうどそれらの1のために私にスペースを与えるか？そして、私は別のものを必要なときに、私の別のスペースを与える、と私は別のものを必要なときに、私の別のスペースを与える。の利点は、今、その場合、他の誰かであるこっちメモリ、大したことを要する。私はここにしてから、この1メモリのこの追加のチャンクを取るよ。さて、ここで唯一の難点は、私が持っているように、これはほとんど感じることです異なる変数の全体の束。これは、潜在的に5異なる変数のように感じている。しかし、我々は、文字列からのアイデアを何を盗む場合それによって我々は何とか概念的に一緒にこれらの事をリンクし、私はこれをやった場合はどうなりますか？これは私の非常に不十分描か矢印です。しかし、仮定そのメモリのこれらのチャンクの各他に指摘し、彼の右に何の兄弟を持っていないこの男、そのような矢印がありません。これは、リンクされたリストと呼ばれるもの事実である。これは、私たちは大量のメモリーを割り当てることができ、新しいデータ構造ですその後、別の、別の、別の、我々はいつでも好きな時プログラムの実行中に、我々は、彼らがすべて何らかの形で関連していることを覚えている文字通り連鎖によって一緒に、我々は絵でここに矢印が付いていることをやった。しかし、コードの中で、何が、あなたが何らかの形で接続することができ、それを介しメカニズムでしょうほとんどスクラッチのような、別のチャンクに1チャンク？我々は、ポインタを右に使うだろうか？、左上の四角から起こっている矢印は、本当にためこのいずれかにここにこの男は、この正方形の内部に含まれている可能性がだけではなく、いくつかのint型、char型のほんの一部ではないが、私が実際に割り当てられた場合はどうでしょうそのため、今では少し余分なスペース、これが私を費用としているにもかかわらず、メモリの私の塊の各々、今ではもう少し長方形の見える場所のメモリチャンクの1つ番号に使用され、数字の1のように、その後、この男はナンバー2が格納されている場合メモリのこの他のチャンクは、矢印に使用されまたはより具体的には、ポインタ。そして、私はその男を指すように、これを使用している間、私はこっちの数字の3を格納すると仮定そして今、この男は、のは私だけでメモリの3つのような塊にしたいとしましょう。私はnullを示すことに線を描画します。追加の文字はありません。確かに、これは我々が実装して行くことができる方法ですリンクされたリストと呼ばれていますか。リンクされたリストには、新しいデータ構造であり、それは向かっての足がかりだ問題を解決するために始めるずっと複雑なデータ構造 Facebookの型の問題とグーグル型の問題の線に沿ってあなたは巨大なデータセットを持っており、それはそれをカットされなくなりましたどこ連続してすべてのものを保存して、線形探索のようなものを使用するあるいはバイナリサーチのようなもの。あなたも、より良い実行時間を求めています。事実、聖Grailsの一つは、我々は今週後半か、次のについて話しますその実行時間が一定であるアルゴリズムです。言い換えれば、それは常に同じ時間に関係なくかかりますどのように大きな入力があり、それは確かに、魅力的だろうなおさら対数何より。ここで、これは画面上には何ですか？各四角形は、私はちょうど手で描いたものを正確になります。しかし、左の奥の事は特別な変数です。それは1つの落とし穴が単一のポインタになるだろうリンクされたリストを使用して、これらのものが呼び出されるように、あなたがリンクリストの一端にしがみつこうとしなければならないことです。単に文字列と同じように、あなたは最初の文字のアドレスを知っている必要があります。リンクされたリストに同じ取引。あなたが最初のメモリチャンクのアドレスを知っている必要がありますそこからので、あなたは1つおきに到達することができます。欠点。我々は動的を持っていることの、この汎用性のためにどのような価格を支払っているかなり大きなデータ構造、我々はこれまでに多くのメモリを必要とする場合は、罰金、ちょうどもう一つのチャンクを割り当ててから、ポインタを描くリストの新しいテールに古い？うん。 [学生]それは約2倍のスペースを取りません。それは間違いなく欠点だので、2倍の容量をとり、私たちはこれを見てきました時間と空間と柔軟性のトレードオフの前に今では、我々は、これらの数値のそれぞれに32ビットをどこにする必要はありません。私たちは本当にポインタの場合は64、番号の32と32を必要としています。でもねえ、私は2 GBのRAMを持っています。こことここで別の32ビットを追加すると、たいしたことは思えない。しかし、大規模なデータセットのために、それは間違いなく、文字通り最大2倍に追加します。何が今、別の欠点だ、あるいは、我々は、どのような機能をあきらめないまた、リンクされたリストではなく配列で物事のリストを表す場合はどうなりますか？ [学生]あなたは後方にそれを通過できません。あなたが歩いている場合、あなたがねじ込むの一種だそう、後方にそれを横断できません左から右ループまたはwhileループのために使用することにそして、あなたは "ああ、私はリストの先頭に戻りたい。"を実現矢印が示すように、これらのポインタは左から右に行くことができないためです。さて、あなたは、別の変数とリストの開始を覚えることができるそれは心に留めておくべき複雑だ。配列、あなたが行くどこまで関係なく、いつでも、マイナスマイナスマイナス行うことができますが、マイナスそしてあなたが来て、そこから戻ってください。ここでもう一つの欠点は何ですか？うん。 [聞こえない学生の質問] あなたがするので、実際のところ、二重にリンクされたリストと呼ばれるデータ構造を提案していたかもしれないそして実際には、これらの四角形のそれぞれに別のポインタを追加することになります他の方向に行く、逆さまになるのあなたは、前後に横断できるようになりました我々がするために使用されるとしての欠点は、今、あなたは多くのメモリを3回使用しているされているまた、あなたが右のそれを得るために記述しなければならないコードの面で複雑さを加える。反転がより重要であるならば、これらは、おそらくすべての非常に合理的なトレードオフがあります。うん。 [学生]また、2Dのリンクリストを持つことができません。良い、あなたは本当に2Dリンクリストを持つことができません。あなたは可能性があります。これは配列とほぼ同じくらい簡単ではありません。配列と同様に、開き角括弧、閉じブラケット、オープンブラケット、ブラケットを閉じたが、やるそしてあなたには、いくつかの2次元構造を得る。あなたは2次元のリンクリストを実装することができますあなたは、アドオンなど、これらのもののそれぞれに第3のポインタ·提案をするのであれば、あなたが別のリストを考えれば、あなたに3Dスタイルを来画面から、私たちのすべてに、それは単にいくつかの並べ替えの別のチェーンです。我々はそれを行うこともできますが、それは開き括弧、角括弧を入力するだけで簡単ではありません。うん。 [聞こえない学生の質問] 良いので、これは本当のキッカーです。我々は、ああ、バイナリ検索のように、オーバーpinedたのでこれらのアルゴリズムは、あなたは、ボード上の数字の配列を検索することができますあなたが使用している場合や、以前よりもずっと迅速に電話帳が分割統治とバイナリサーチアルゴリズムが、2つの仮定を必要と二分探索。データがソートされたことをひとつ。今、我々はおそらく、これはソート保つことができますので、多分それは問題ではないのですが、バイナリ検索も想定あなたは、番号のリストへのランダムアクセスを持っていたことと配列を使用すると、ランダムアクセスが可能になり、ランダムアクセスによる、あなたは配列を指定しているなら、私が意味する、それはあなたをどのくらいの時間がかかりますかブラケットを0に取得するには？操作は1つ、あなただけの[0]を使用していて、すぐそこだ。位置10に到達するためにどのように多くの手順がかかりますか？ワンステップでは、あなただけの、あなたがそこにいる[10]に進みます。これとは対照的に、どのようにリンクされたリストの10番目の整数を取得するのですか？あなたが唯一覚えているので、初めに開始する必要があります単に文字列のようなリンクリストの先頭が、思い出したされているその最初の文字のアドレスで、その第十intを検索するまたは文字列で、その10番目の文字は、全体こいつを検索する必要があります。再び、我々は我々の問題のすべてを解決するわけではありません。我々は新しいものを導入しているが、それは本当にあなたが設計しようとしているものに依存します。これを実装するという点で、我々はその生徒構造からアイデアを借りることができます。構文は今を除いて、非常に似ていますが、考え方はもう少し抽象的であるより家と名前とID。しかし、私たちはCのデータ構造を持つことができることを提案するスライド上の最後の言葉が示唆するように、ノードと呼ばれている、ノードの内部に、ノードは単にコンピュータサイエンスの汎用コンテナである。これは通常、円または我々が行ったように、正方形または長方形として描かれている。そして、このデータ構造では、我々は、int、nを持っているそう、それは私が保存したい数字です。しかし、この二行は、structノードは*次は何ですか？なぜ、これが正しいか、またはロールはこの事プレイ何それは一見すると少し不可解だにもかかわらず？うん。 [聞き取れない生徒の応答] 正確なので、ある種のポインタ戦利品の*ソートだという。このポインタの名前は、任意に隣接していますしかし、我々はそれを我々が欲しいものを求めていることができますが、このポインタのポイントは何をしますか？ [学生]別のノード。>>まさに、このような別のノードを指しています。さて、これはCの好奇心のようなものです Cは左から右へ、上から下へ、コンパイラによって読み取られることを思い出してくださいそれは、これがあれば私達は学生でやったものとは少し違うことを意味します。我々は学生を定義したとき、私たちは実際にそこに単語を入れていない。それはちょうどtypedefを語った。その後、我々はint ID、文字列名、列の家を持っていたその後構造体の下部にある学生。この宣言は少し異なっていますので、再び、Cコンパイラは少し馬鹿です。それだけで、上から下へ読みになるだろうそれはここで2行目に到達したので、もし次回が宣言され、それが見ている場所、ああ、ここには次のと呼ばれる変数です。それはstructノードへのポインタです。コンパイラは構造体ノードであるものを実現しようとしている？私は、前にこの事を聞いたことがない単語ノードがそうしないと表示されない場合がありますので、底までなので、この冗長性があります。あなたはその後に短縮することができ、ここで、構造体のノードを言わなければならないここにtypedefのおかげで、これはためである我々は、内部構造の構造自体を参照しています。それはそこに1落とし穴だ。いくつかの興味深い問題が生じるとしている。私たちは、番号のリストを持っている。どのように我々はそれに挿入するのですか？我々はそれをどのように検索するには？どのように我々は、そこから削除しますか？特に今、私たちはこれらのポインタのすべてを管理しなければならない。あなたは、ポインタがハラハラドキドキの一種と思っていたあなたはそれにintを読み込もうとしているそのうちの一つを持っていたとき。今、私たちは、リスト全体の価値を操作する必要があります。なぜ我々はここで我々の5分間の休憩を取ることはありませんし、我々は持っていきますステージに上がって何人かの人々は、まさにそれを行う。 Cはそれは演じているはるかに楽しいです。文字通り最初にすることは誰希望ですか？さて、アップで来る。あなたが最初のものである。誰が9になりたい？さて、9。どのように約9？ 17？ここで少し徒党。その最前列に22と26。そして、誰かについてあそこでどの指されている。あなたは34アール。アップに来て、34、オーケー。最初はあそこにあります。さて、皆さんのすべての4つ。そして、我々は9のために誰が言ったの？私たちの9誰ですか？誰が本当に9になりたい？すべての権利は、9でなければ、上に来る。ここに私達は行く。 34は、私たちはそこにあなたを満たすでしょう。最初の部分は、あなた自身がそのように見えるようです。 26、22、17、良い。私たちは一瞬であなたをmalloc関数としているので、あなたが側にスタンドオフができる場合。良い、良い。さて、優秀なので、ここでの質問のいくつかを尋ねてみましょう。そして、実際に、あなたの名前は何ですか？>>アニタ。アニタ、大丈夫、こっちに来る。アニタは最初の1つの非常に単純な疑問を解決するための並べ替えの私たちを助けるために起こっている、これはあなたの値がリスト内にあるかどうかを見つけるにはどうすればよいですか？さて、最初に、ルーカスがここに表されていることがわかり、少し違っていて、紙のように彼の作品は意図的に横にあるそれは、かなり背が高くないですし、多くのビットを占有していませんので、にもかかわらず、技術的に、彼はただ回転し、用紙のサイズと同じになります。しかし彼は、ポインタの32ビットだけ、という点でちょっと違うこれらの人のすべてが数字で、そのうちの64ビット、ハーフであり、半分はポインタです。君たちができればしかし、ポインタがややぎこちなくので、示されていませんあなたの隣の人を指すように左手を使用しています。そして、あなたは数34だ。あなたの名前は？アリ。アリなので、実際には、右手で紙を保持し、左手はまっすぐに行く。あなたが左にnullを表す。現在、私たち人間の絵は非常に一貫性があります。これは、ポインタがどのように動作するか実際にある。私はあなたの方法で分からないので、とした場合は、この方法は少し伸び縮みすることができます。ここアニタ、私22番を見つけ、しかし、紙の破片を保持していない人間の制約を前提としていしかし、これはリストであり、あなただけのルーカスが最初から持っている彼は文字通り最初のポインタであるためです。あなた自身がポインタであり、従って、あなたも何かを指すように能力を持っていると仮定します。なぜあなたは、ルーカスが指している正確に何を指していることから始めませんか？良い、と私はここの上にこれを制定することができます。単に議論のために、私はここに空白のページをアップしましょう。あなたの名前はどうつづるのですか。>>アニタ。さて、アニタ。 Let 'sは、ノード*アニタ=ルーカスを言う。さて、私たちはあなたルーカス呼び出すべきではありません。我々は、あなたが最初の呼び出しがあります。なぜこれがここに現実のものと一致して、実際にはありますか？一つは、最初にすでに存在しています。最初はどこかここまでおそらく割り当てられています。ノード*最初、それが何らかの形でリストが割り当てられている。私はそれが起こったのか分からない。クラスが始まる前にそれは起こった。人間のこのリンクリストが作成されました。そして今、物語これがすべて明らかにFacebook上で起こっているこの時点で、後に物語のこの時点で、アニタは、最初に等しくなるように初期化されているこれはルーカスでアニタ·ポイントという意味ではありません。むしろ、彼女は彼が指差すものを指しなぜならルーカスの32ビットの中を同じアドレス - 1、2、3 - 1、2、3 - アニタの32ビットの内部にもなりました。現在22を見つける。どうやってこれをやって行くだろうか？何への？>>ポイントは何ですか。何を指しているので、先に行くとあなたがここでできる最善として、それを行動に移す。、良い良い、そして今あなたが指している時に、何をあなたの名前は22でですか？ラモン。>>ラモンので、ラモンは22日まで開催しています。ここでチェックを行っている。ラモン== 22、そうであれば、例えば、我々がtrueを返すことができていますか。私をしながらしましょうこれらの人はぎこちなく、ややここに立つ私はすぐに見つけるブールのような何かを行うことができます。私は先に行くと（ノードリスト*、int n）を言うつもりです。私はあなたたちとすぐに戻ります。私はいくつかのコードを記述する必要があります。そして今、私は先に行くと、これは、ノード*アニタ=リストをするつもりです。そして、私は先に行くと言おうとしている間（アニタ！= NULL）。ここに比喩は少し引き伸ばさなっているが、（アニタ！= NULL）は、私が何をすべきかをしたいですかしながら？私が参照しているいくつかの方法が必要アニタが指していることを整数。ノードである我々は構造を持っていた過去、、、で我々は、ドット表記法を使用しており、我々は何かのように言うだろう anita.nが、ここでの問題は、アニタが構造体自体ではないということです。彼女とは何ですか？我々はこの点使用したい場合は彼女がいるので本当に、ポインタの表記をこれは意図的に少し見に行くされている暗号のよう我々は何でもアニタの左手に行くように何かをしなければならないことを指しているし、nという名前のフィールドを取得します。アニタはポインタですが、*アニタは何ですか？あなたはアニタが指しているかに行くときあなたは何を見つけるのですか？構造、ノード、およびノード、リコールは、nというフィールドがありますそれは、リコールされたため、これら2つのフィールドは、次のとn、我々はここに少し前に見た。実際には、コード内でこれを模倣する我々はこれを行うと言うことができる場合（（*アニタ）はn == n）は、私が探していることをN。関数は、私が気に数年に可決されたことに注意してください。それから私は、先に行くと真のリターンのような何かを行うことができます。そうでなければ、それはそうではない場合、私は何をすべきかをしたいですか？どのように私はアニタ、リスト内を歩くことによって、そう直感したことをコーディングするために変換するのですか？私はアニータは左に、左に、そのステップをそのステップを取ってシミュレートするためにここで何をすればいいですか？ [聞き取れない生徒の応答] >>これは何ですか？ [聞き取れない生徒の応答] 、悪い考えではないが、過去に、我々はこれをやったときに、我々は良いやっアニタ+ それはアニタに番号1を追加することになりますので、どの一般的に、ラモンのように、隣の人を指すでしょうまたは彼の隣の人、またはラインの下の彼の隣の人。何このことは、メモリ内のように見えないので、しかし、それはここでかなり良いではないですか？ないこと。我々はそれを無効にする必要があります。それは私が1と2と3が互いに近接して、描画した後もメモリ上にこのように見え、まだ同じ人を指さしながら、我々は本当に、この缶君たちをシミュレートする場合は、あなた方の何人かがランダムステップ戻る、進むあなたのいくつかのランダムな一歩を踏み出すことができますか？この混乱は、まだリンクされたリストです。しかし、これらの人は、メモリ内の任意の場所かもしれませんそうアニタ+ +はなぜ仕事に行くのではないでしょうか？ +位置アニタで何ですか？誰が知っている。それはちょうどので介在するように起こるいくつかの他の値だ偶然これらのすべてのノード間であるため、我々は、配列を使用していない。私たちは、個々に、これらの各ノードに割り当てられた。さて、あなたたちは自分自身をバックアップし、クリーンができる場合。私が代わりにアニータ+ +私たちが代わりにやるアニタのことを提案させて取得し、さて、なぜ我々はありませんその後、アニタが指しているものは何でもに行くとありません。次は？言い換えれば、私たちは22番を保持しているラモン、、に行くアニタは左手のポインタをコピーすることになるかのようにしてから次のです。我々は22を発見したので、しかし、彼女はラモンよりも遠くに行かないだろう。しかし、それはアイデアだろう。さて、これはひどい混乱です。正直なところ、誰も、とてもありがたいことに、この構文を覚えていない、となりますそれは実際には少し意図的なああ、あなたは実際に私が書いたものを見なかったのです。あなたができればこれは、より説得力があるだろう。出来上がり！舞台裏では、私はこの問題をこの方法で解決しました。アニタ、左にその一歩を踏み出すためには、第一、私たちは、アニタが指しているアドレスに行くのですかそしてここで彼女だけではなく、我々だけで比較のためのチェックをnを、見つけるしかし、あなたはまた、次の見つける - このケースでは、ラモンの左手は、リスト内の次のノードを指す。しかし、これは、私が以前に言及するために神のひどい混乱ですしかし、それは、Cは、私たちはこれを簡素化することができますが判明した。書く代わりに（*アニタ）、我々だけではなく、アニタ-> nを書き込むことができますそして、それは機能的にはまったく同じことだが、それは多くの、より直感的だそしてそれは我々が描いてきた絵と、より多くの一貫性のある矢印を使用してすべてのこの時間。最後に、我々はこのプログラムの最後に何をするかが必要なのでしょうか？残りのコードの1行がある。何を返す？偽なぜなら、我々は全体を介して取得する場合は、whileループアニタと彼女はリストの最後にすべての方法を行ったことを意味し、実際には、nullになります彼女が指していた場所で、あなたの名前は何だっけ？ nullであるアリ。>> Ariの左手。アニタは現在nullである、と私はあなただけではどっちつかずの状態でここに立っているぎこちなく実現私はここに独白にオフつもりですので、しかし、我々はほんの一瞬で再びあなたを伴うでしょう。アニタは、物語の中で、その時点ではnullであり、whileループが終了したので、そして我々はfalseを返すように持っているので、彼女はAriのヌルポインタへのすべての道を得た場合それから彼女はリストに求めない番号がありませんでした。我々もこれをクリーンアップすることができますが、これはその後かなり良い実装ですトラバーサル機能により、リンクリストの関数を見つける。それはまだ線形探索だが、それは+ +のポインタのように単純ではありませんまたは+ + iの変数を、今、私たちは推測することはできませんので、これらの各ノードは、メモリ内にどこにある。我々は、より具体的には、文字通りパンくずの道に従わなければならないか、あるノードから別のノードに到達するためのポインタ。今度は、別のものを試してみましょう。アニタ、あなたはここに戻ってきたいですか？なぜ我々は先に行くと、観客からもう一人に割り当てられることはありません？ malloc関数 - 何あなたの名前ですか？>>レベッカ。レベッカ。レベッカは、聴衆からmallocされているそして彼女は今55番を記憶している。アニタ挿入するために、当面の目標は今ですここに適切な場所でリンクリストにレベッカ。しばらくこっちに来る。私はこのような何かをしてきました。私は、ノード*を行っている。そして、あなたの名前は何ですっけ？レベッカ。>>レベッカ、大丈夫。レベッカは、malloc（sizeofの（ノード））を取得します。同じように私たちは、過去に学生やその他もろもろのようなものを割り当てている我々は、ノードのサイズを必要とするので、今レベッカ何を指している？レベッカは55そのうちの1つは彼女の内側の2つのフィールドがあります。やってみましょう何、レベッカ-> = 55。しかし、その後、レベッカ - >次は今、希望されるべきであり、彼女の手は誰が知っているのようなものですか？それはいくつかのゴミの値を指しているので、なぜついでにない左手はすぐに彼女の側にあるように、我々は、少なくともこれを行う。今すぐアニタは、ここからそれを取る。あなたは、レベッカが割り振られた持っています。先に行くと、私たちはレベッカを置くべき場所を見つける。非常に良い、良い。良い、さて、今、私たちは方向のビットを提供するためにあなたを必要とし、ので、アリに達しました。、彼の左手はnullになりますが、レベッカは明らかに右に属しので、どのように我々は、このリンクリストを変更する必要はない適切な場所にレベッカを挿入するためには？必要に応じて、あなたの周りは、文字通り人々の左の手を動かすことができれば、我々はそのように問題を修正します。さて、良い、と一方、レベッカの左手は彼女の側になりました。それはあまりにも簡単だった。 20、これでほぼ完了割り当てる-we'reてみましょう。さて、アップで来る。 20が割り当てられているので、私が先に行くと、ここでもう一度言わせて我々は、ただのノード*サアドをやった。我々は、malloc（sizeofの（ノード））を持っています。我々は、その後、我々は20の前に行ったのと同じ構文を正確に行うそして私は次の= NULLをやる、今ではアニタ次第ですそのまったく同じ役割を果たすことができる場合は、リンクされたリストに挿入する。実行します。さて、良い。あなたの周りに左の手の移動を開始する前に、今、慎重に考える。はるかにあなたは今日最も厄介な役割を得た。その手先に移動する必要がありますか？さて、私はいくつかのないのを聞いて、待って。一部の人々は礼儀正しくここに厄介な状況を解決するのを助けるようにしたい場合。誰の左手おそらく最初に更新する必要がありますか？うん。 [学生]サアドの。さて、サアドの、理由があるのでしょう？ [聞き取れない生徒の応答] 良い、なぜなら我々は移動し、どのような場合、あなたの名前ですか？>>マーシャル。マーシャル、我々はnullにファーストダウンに手を移動した場合、今、私たちは文字通り、このリストに4人孤立している彼は、ラモンと左に誰を指している唯一のものだったので、そのポインタが最初の不良であったことを更新。ことを取り消しましょう。良い、今先に行くと、ラモン指さし適切な左手を動かす。これは、少し冗長に感じている。今そこにラモンを指さし2人ですが、それは大丈夫です今ので、他にどのように我々はリストを更新すればよいですか？他にどのような手が移動しなければならない？優れた、今我々は、任意のメモリを失っているか？いや、とても良い、我々がもう一度、これを壊すことができないかどうかを確認してみましょう。最後にもう一度Mallocing、番号5。背中のすべての方法は、下に来る。それは非常にエキサイティングだ。 [拍手] あなたの名前は何ですか？>>ロン。ロンは、大丈夫、あなたは5番としてmallocされています。我々は、ちょうどこれらのとほぼ同じだコードを実行してきたちょうど別の名前で。優れています。さて、アニタ、今やリストに番号5を挿入する幸運。良い、と？優秀なので、これは本当に合計3例目です。我々は最初のレベッカ、最後に誰かを持っていた。次に、途中で誰かを持っていた。今、私たちは、初めに誰かを持っており、この例では、我々は今、初めてルーカスを更新する必要がありましたリストの最初の要素は、新しいノードを指すように持っているので、人は、順番に、ノード番号9を指しています。これは非常に厄介なデモンストレーションでした、私は確信している、ので、これらの人のために大きな拍手あなたができれば。うまくやった。それがすべてです。あなたは少しメモリとして紙のピースを保持することができます。これは、コードでこれを行うことが判明ちょうど周りに手を移動させるなど非常に簡単ではありませんと異なるものでポインタを指している。しかし、それはのようなものを実装する時が来ることを認識あなたが本当にに焦点を当てる場合は、リンクされたリストまたはその変種これらの基本的なファンダメンタルズ、私が把握する必要があり一口サイズの問題、それはこの手やこの手で、何がそうでなければ、かなり複雑なプログラムであることを認識実際に、このような非常に単純なビルディングブロックに減らすことができます。さらに洗練された方向で物事をみましょう。我々は今、リンクリストの概念があります。背中の提案があり、二重連結リストに我々はまた、持っている - のおかげで、これはほぼ同じに見えますが、今、私たちは、構造体の内部に二つのポインタを持っている代わりの一つであり、我々は、おそらく前と次のこれらのポインタを呼び出すことができます左または右、しかし、我々は、実際には、それらの2つが必要なのでしょうか。コードが少し複雑になります。アニタは、ステージ上でここでより多くの仕事をしなければならなかっただろう。しかし、我々は確かに構造のようなものを実装することができます。実行時間の面では、しかし、何が実行されているのがいいでしょう現在、リンクリストに番号nを見つけるアニタのために？ nは依然として大きなOので、線形探索よりも良いではありません。我々は再び、しかし、二分探索を行うことはできません。なぜそのような場合だったのですか？あなたの周りのジャンプすることはできません。我々は明らかに、ステージ上のすべての人間を見ていても、とアニタ "は、ここではリストの中間である"それをeyeballedと、言ったかもしれない彼女はコンピュータプログラムであったことを知っている場合ではないでしょう彼女が持っていた唯一のものは、シナリオの開始時にラッチするため最初のポインタだったルーカスは、あった。彼女は、必ずしも、それらのリンクをたどってしなければならないでしょう彼女は大体真ん中を見つけるまで、彼女の方法を数えるそしてその時でさえ、彼女は彼女が中央に達しているときに知っておくことはないだろう彼女がいくつあるかを把握するために最後にすべての道を行く限り、あなたが持っていない限り、バックトラックが、それはあまりにも難しいだろうある種の二重連結リスト。今日はいくつかの問題を解決するが、他のものを導入する。完全に別のデータ構造についてはどうですか？これは、マザーハウスにあるトレーの写真ですこの場合、我々はまたの種類が既に話をしてきたデータ構造を持っています。我々は、メモリのコンテキスト内のスタックの話それはメモリの面でスタックので意図的に名前のようなものだ効果的にそれの上に重ね、より多くのものを持つデータ構造体です。しかし、スタックの面白いところは、のように、現実にはそうであるそれはデータ構造の特殊なものだということです。それによって内の最初の要素は、データ構造の最後の要素の外です。あなたは、スタック上に置かれるべき最初のトレイであれば、あなたは、残念ながら、スタックから取るべき最後のトレイであることを行っているそしてそれは良いこととは限らないです。逆に、あなたは、他の方法で周囲にそれについて考えることができますの最後には、最初に出ています。さて、どんなシナリオがスタックを有する場所に頭に来るのかあなたは、そのプロパティを持つデータ構造後入れ先出しで、実際に説得力がある？それは良いことなのでしょうか？ことは悪いことですか？トレイが全て同一ではなかったなら、それは間違いなく悪いことだそして、彼らは、すべての特別な異なった色やその他もろもろあったそしてあなたが望む色は下部にある[すべての方法です。もちろん、あなたは偉大な努力もせずにそれを取得することはできません。あなたはトップからスタートして、あなたの方法を下に仕事をしなければならない。同様に、これらのファンの男の子の一つであった場合はどう誰がiPhoneやラインを取得しようと徹夜し待機こんな所で？それがいいと思いませんかあれば、アップルストアスタックのデータ構造があった？イェーイ？いや？それが唯一の最後の可能な分に現れ人々のために良いことだその後キューから摘み取られ得る。そして、実際に、私がその気されたという事実は、キューを避ける、我々はこの種のデータ構造と呼ぶようなもので実際に一貫している順番は問いませ現実の1つ、、あなたがの最初のものは最初のもののうちにしたい人間の公平のためにいる場合のみ。我々は一般的にキューデータ構造体のことを呼ぶことにします。これは、リンクされたリストのほかに、我々はこれらの同じ基本的な考え方を使用して起動することができ判明と問題の解決策のとは異なった新しいタイプの作成を開始します。例えば、スタックの場合、スタックを表すことができこのようなデータ構造を使用して、私が提案したい。この場合において、私は、structを宣言した、と私はこの構造体の内側に言ってきました数字の配列を出力して、変数と呼ばれるサイズですそして私はこの事スタック呼ぶつもりです。さて、これは実際に動作しませんなぜですか？スタックの場合、私は配列として画面上にこれを効果的に描くことができます。ここに私のスタックです。それらは私の番号です。そして、我々はこれ、これ、これ、これ、これとしてそれらを描画します。そして私は、ここでいくつかの他のデータメンバを持っているサイズと呼ばれている、そう、これは大きさであり、これは数字ですと総称して、ここで全体のiPadは1スタック構造を表します。これからはデフォルトで、大きさはおそらく、0に初期化されることを持っていると最初に数字の配列の内側に何私が最初に配列を割り当てるとき？ごみ。誰が知っているか？そしてそれは実際に重要ではありません。それは完全にランダムに、これは1、2、3、4、5の場合は関係ありません私の構造体に格納されている不運である限り、私は知っているようなので、そのスタックのサイズ 0であるなら、私が知っているプログラムで、配列内の要素のいずれかを見ていない。それは、何があるかは問題ではありません。サイズ0の意味であるように、それらを見てはいけない。しかし、私は先に行くと、スタックに何かを挿入してすぐにあるとします。私は5番を挿入したいので、私はここで5番を入れてそして私はここに何を置くのですか？今、私は実際に、大きさは1を下に置くであろうそして今、スタックのサイズは1である。私は7次、先に行くと番号を挿入する、としましょう場合はどうなりますか？次に、これは2に更新され、その後、我々は、9をやるその後、これは3に更新されます。しかし、このスタックの現在、興味深い特徴は、私は私がポップアップ表示したい場合、どの要素を削除することになってるスタックの何かオフは、いわば？ 9は、移動するための最初のものになるだろう。私はスタックから要素をポップする場合どのように絵は、変更する必要がありますずっとメイザーのトレイのような？うん。>> [生徒] 2サイズを設定します。まさに、私はすべてが2にサイズが設定されており、私は配列を使って何を行うのですか？私は何もする必要はありません。私は、ちょうど肛門のように、そこに0または-1または示すために何かを入れることができますこれは合法的な値ではありませんが、それは問題ではないことを理由私はそれがどのように長い配列自体の外側に記録することができますので、私は知っている唯一のこの配列の最初の2つの要素を見てみましょう。今、私が行って、この配列に8番を追加した場合、どのように絵が次の変更でしょうか？これは8になり、これは3となる。私はここにいくつかのコーナーをカットしています。今、私たちは、5、7、8を持っていると我々は3の大きさに戻っています。これは、実装するために非常に単純です。しかし、ときに我々は、この設計上の決定を後悔するつもりですか？ときに物事は非常に、非常に間違って行くことは起動するのでしょう？うん。 [聞き取れない生徒の応答] あなたは戻って、あなたはインチ入れて最初の要素を取得したいときスタックはボンネットの下に配列であっても、それは、ここで判明私たちが話し始めたこれらのデータ構造はまた、一般的に知られている抽象的なデータ構造により、それらがインプリメントしている方法完全に的外れである。スタックのようなデータ構造は、サポートを追加することになっているスタックの上にトレイをプッシュプッシュ、などの操作、スタックから要素を削除し、それはそれだし、ポップ、。あなたは既に実装され、他の誰かのコードをダウンロードした場合このことは、人が書いたであろうことを、スタックと呼ばれるあなたのための2つだけの関数、pushとpop、人生の唯一の目的まさにそれを行うことです。あなたや彼または彼女のそのプログラムを実施完全に実装する方法を決定するための1だっただろうフードの下にプッシュとポップの意味またはプッシュとポップの機能。そして、私はここでやや近視眼的な意思決定を行っているなぜこのような単純なデータ構造を持つ私のスタックを実装することで？ときに、このデータ構造の休憩をしますか？どの時点で、私は、ユーザーがプッシュ呼び出したときに、例えば、エラーを返さなければならないのですか？ [学生]は、より多くのスペースがない場合。まさに、これ以上のスペースがある場合、私は容量を超えている場合、それはグローバル定数の一部のようなものだことを示唆しているので、これは、すべてのキャップです。じゃあ、私はただ申し訳ありませんが、私は別の値をプッシュすることはできません "と言っているつもりだスタックに、 "ずっとメイザーで好きです。いくつかの点で、彼らはその小さな筐体の上部にヒットするつもりです。何らかのエラーがあるとその時点で、スタック内にそれ以上のスペースまたは容量があります。彼らは、トレイどこか、どこか別の場所に要素を配置する必要がありますまたはどこにも全然。さて、キューに、我々は少し違ったように実装することができます。キューは、フードの下に、それを実現することができるという点で少し異なっています配列として、しかし、なぜ、この場合には、私が提案していますまた、リストのヘッドを表すhead要素を持っている、サイズに加えて、リストの先頭に、アップルストアでのラインの最初の人、？なぜ私はここにデータの追加部分が必要なのでしょうか？何かの数字に戻って考える私はそれは次のように描かれている場合。これは代わりにスタックのキューであると仮定である - ちょうどアップルストアキューのような違いが公平である。リストの先頭にある行の最初の人、この場合は5番、彼または彼女は、最初の店に入ってみましょうされようとしている。ことを行いましょう。これは時間のこの瞬間に私のキューの状態、現在はアップルストアであることを仮定開き、最初の人、番号5は、店舗内に導かれる。どのように私は今、私は最初の人をデキューした画像を変更するのですかラインの前で？それは何ですか？>> [学生]キューを変更します。頭を変更しますので、5が消えます。現実には、これを行うには、あたかも、最善の方法ですか？この男が消えたかのように現実には、それは。 7番は、実際の店で何をしますか？彼らは、大きな前進を取るだろう。それは配列に来るときしかし、私たちは感謝するようになったと周りのものを移動する？それは右、あなたの時間の無駄のようなものだ？なぜあなたは、最初の人を持っているように肛門でなければならないメモリの塊の物理的に開始時に行の先頭に？それは完全に不要です。なぜですか？私だけではなく、何を覚えているだろうか？>> [聞こえない学生の応答] まさに、私はちょうどこの追加データメンバヘッドを覚えることができる現在、リストの先頭は、それが少し前にあった、もはや0でないことを確認します。今では実際に数字の1です。このように、私は若干の最適化を得る。私はアップルストアでの行の先頭に行から誰かをデキューしたからといってリコールは線形動作である、誰もがシフトする必要がありますというわけではありません。私の代わりに、定数だけの時間を過ごすことができますそして、はるかに高速応答を実現。しかし、私が払っている価格は、追加のパフォーマンスを得るためには何ですかと皆をシフトする必要がない？うん。>> [聞こえない学生の応答] より多くの人を追加することができ、まあ、その問題は直交している我々は世界中の人々をシフトしていないという事実に。それは我々が皆をシフトするか、そうかどうか、まだ配列ではありません - ああ、私は大丈夫、あなたが何を意味するかを参照してください。実は、私はあなたはそれがほとんどあたかもという点で言っていることに同意する我々は、今はもう、この配列の開始を使用するつもりはありませんしている私は5を削除するので、その後、私は7を削除します。しかし、私は唯一の右に人を置く。私は、スペースを無駄にしているように感じ、最終的に私のキューは全く何に崩壊そう私達はちょうど、人々の周回を及ぼす可能性がありますそして我々は、環状構造のいくつかの種類としては本当に、この配列を考えることができましたしかし、我々は、ラップアラウンドのその種を行うためにCで何演算子を使用するのか？ [聞き取れない生徒の応答] >>モジュロ演算子。それはあなたのラップアラウンドをどのように行うかをよく考えて少し煩わしいかもしれませんでしょう、しかし、我々はそれを行うことができ、我々は、行の先頭であったもので人を置く作業を開始することができるしかし、我々はちょうどラインの実際のヘッドは、実際にはこのヘッド変数で覚えています。何が、しかし、最終的に我々の目標は、代わりに、もし、我々はアニタと一緒にステージにここで行ったように、番号を調べることであったしかし、我々は本当に、これらすべての世界の最高をしたいですか？我々は、配列が許すよりも洗練されたい我々は、動的データ構造を成長させる能力が欲しいから。しかし、我々は、我々が指摘しているものに頼ることはしたくない最初の講義で、最適なアルゴリズムはありませんでした線形探索のこと。それはあなたが、実際には、達成できることが判明あるいは、少なくとも、それによってアニタのような人、時定数に近い彼女がリンクされたリストではないと彼女のデータ構造を構成している場合は、実際には、キューではないと、スタックができるべきではなく、、彼女は物事を調べることができますデータ構造を思い付くでも、言葉だけではなく、数字は、何で我々は時定数と呼ぶことにします。そして、実際には、先を見て、このクラスでのpsetの一つは、ほとんどの場合であるスペルチェッカーの実装、それによって我々は再び約15万語の単語をあなたに与えると目標は、メモリにそれらをロードして、急速に形の問いに答えることができるこの言葉は正しく入力されている？あなたがそれに答えるためにすべて15万言葉を反復しなければならない場合、それは本当に吸うと思います。しかし、実際には、我々は非常に、非常に迅速な時間でそれを行うことができていることがわかります。そしてそれは、ハッシュテーブルと呼ばれるものを実装巻き込むために起こっている、と一目見ただけでハッシュテーブルと呼ばれるこの事はに起こっているにもかかわらず、、私たちは、これらの超迅速な応答時間を達成しましょうそれは、問題が実際に存在することが判明した。それは、再び呼び出され、このことを実装する時間が来ると、私は再びそれをやってる。私はここだけだ。それが来るときに、このことを実現するまでの時間は、ハッシュテーブルと呼ばれる我々は決断をしなければならないだろう。このことは、実際にどのくらいの大きさであるべきか？そして、我々はこのハッシュテーブルに挿入する数字を起動したときに、どのように我々はそのような方法でそれらを格納しようとしている我々はそれらを得たとして、我々はできるだけ早く戻ってそれらを得ることができる？しかし、我々は、この質問のことをずっと前に表示されますみんなの誕生日がクラスである場合に非常に密接な関係になります。それは、この部屋では、我々は数百人を持っていることが判明私達二人が同じ誕生日はおそらくかなり高い確率があることはそう。わずか40私たちはこの部屋にあった場合は？同じ誕生日を持つ2人のオッズはどれくらいですか？ [学生] 50％以上。うん、50％を超える。実際、私もチャートを持ってきた。それはアウトとなりますこれは本当にただスニークプレビューです - この部屋の中で、私たちの唯一の58、私達の2の確率がある場合。同じ誕生日を持つことは、ほぼ100％の非常に高いですそれは水曜日に私たちのために傷つくの全体の束を引き起こすだろう。そうは言っても、のはここで休会することができます。私たちは、水曜日にお会いしましょう。 [拍手] [CS50.TV]