[Powered by Google Translate] [第4週] [デビッド·J·マラン] [ハーバード大学] [これはCS50です。] [CS50.TV] すべての権利は、これはCS50であり、これは第4週の始まりですこれは最も遅い可能ソートアルゴリズムの一つである。どちらが私達がちょうどそこに見ていることでしたか？それはビッグはO（n ^ 2）+和、順番にバブルソートであったそして実際に、我々は知っているように見えるために、この世界で唯一のものではありませんどんなバブルソートであるか、またはその実行時間。確かに、これはGoogleのエリック·シュミットとのインタビューだったほんの数年前と元上院議員バラク·オバマ。今では、上院議員は、Googleでここにいる、と私は、就職の面接のように大統領職を考えるのが好きです。さて、それは社長として仕事を得るのは難しい、とあなたは今厳し通過している。これは、Googleでの仕事を得ることも難しい。、我々は疑問を持っており、我々は我々の候補者の質問をするそしてこれはラリー·シュワイマーからです。君たちは私をからかっていると思う？それは右ここにあるのです。万人の32ビット整数をソートするための最も効率的な方法は何ですか？ [笑い] よくごめんなさい。>>いや、いや、いや、いや。私は、バブルソートは、移動するための間違った方法だと思う。彼にこのことを告げた人々、上に来る？先週、我々は少なくとも1日、コードから休憩を取ったリコールそしてより一般的に解くいくつかのより高いレベルのアイデアや問題に焦点を当て始めた検索やソートの文脈では、そして我々は、我々は最後の週に、この名前を平手打ちしなかったものを導入しかし漸近記法、ビッグオー、ビッグオメガ、そして時にはビッグシータ表記、これらは単純な方法であったアルゴリズムの実行時間を記述するための、それを実行するためのアルゴリズムのためにかかった時間。そして、あなたは、大きさの点では、実行時間について話しましたことを思い出して我々は一般的に問題があるかもしれないものは何でも、nを呼び出す入力、の、ここで、nは、部屋にいる人々の数です電話帳のページ数、そして我々は物事を書き始めましたはO（n ^ 2）またはO（n）またはO（n log n）のようなと数学はそれほど完璧にうまくいかなかった場合でも、 n / 2個、またはそのような何か - そしてそれは、n²だった我々だけではなく、下位の用語のいくつかを捨てるでしょう私たちが本当に求めているがあるとモチベーション評価の客観的な方法のようなものプログラムのパフォーマンスやアルゴリズムの性能一日の終わりに、例えば何の関係もないことを、お使いのコンピュータの速度今日と。たとえば、あなたはバブルソートを実装する場合、またはあなたは、今日のコンピュータ上で並べ替えや選択マージソートを実装する 2 GHzのコンピュータ、そして、あなたはそれを実行し、そしてそれは3ギガヘルツがある来年、秒のいくつかの番号を取るまたは4 GHzのコンピュータ、あなたはその "うわー、私のアルゴリズムを主張する可能性があります現実には明らかにそうではありませんその時、 "今、2倍の速さである。それは単にハードウェアが速くなったのですが、お使いのコンピュータので、私たちは本当にのようなものを捨てたくなかった 2の倍数または3の倍数、それが説明に来るどのくらいの速またはどのように遅いアルゴリズムがあり、実際にちょうど焦点を合わせる nまたはそのいくつかの因子に先週からのソートの場合、そのようないくつかのパワー。とマージソートの助けを借りていることを思い出す私たちは、バブルソートと選択ソートよりもはるかにうまくやることができましたさらには挿入ソート。我々は、nログnに降りて、再びログnは、一般的に育つ何かを参照していることを思い出すもっとゆっくりと、nので、nログnこれまで良好であったそれは、n²未満であったため。しかし、マージソートとnを達成するn個のログに私たちが活用していたという考え方の基本胚芽何だった我々はまた、0週に戻って活用している？どのように我々はマージソートでソート巧み問題に取り組むたのですか？たぶん、キーの洞察力は何でしたか？誰も全然。さて、のは一歩下がってみましょう。あなた自身の言葉でマージソートを説明してください。それはどのように動作したのですか？さて、私たちは週に0に戻って行う。大丈夫、うん。 [聞き取れない - 学生] さて、良いので、我々は2ピースに数字の配列を分けた。我々は、それらの部分のそれぞれをソートした後、我々はそれらをマージこの大きいです問題を取る前に、我々はこのアイデアを見てきましたそしてこの大きなまたはこの大きいです問題にそれを刻んで。電話帳の例を思い出してください。、数週間前から自己計数アルゴリズムを思い出すので、マージソートはここでこの擬似コードでまとめた。あなたはn個の要素を与えている場合、最初のそれは健全性チェックであった。 N <2はその後まったく何もしていない場合 N <2、nは明らかに0または1の場合、なぜなら、それが0または1のいずれかの場合とそうソートするものは何もありません。あなたは完了です。あなたのリストは既に自明にソートされます。しかし、あなたが2つ以上の要素を持っているそうでなければ先に行くと、それらを分割 2半分に、左と右。それらの半分のそれぞれをソートしてから、ソートの半分をマージします。しかし、ここで問題は、我々がけっているように一見しただけで、これは感じているということです。私はこれらのn個の要素をソートすることが求められてきた場合、これはその中で循環定義です、あなたは、 "よし、大丈夫です、我々はそれらのn / 2にし、それらのn / 2個の要素を並べ替えましょう"私は言っているその後、私の次の質問は "どのようにしてn / 2個の要素を並べ替えるには？、ファイン"になるだろうしかし、このためにプログラムの構造を、このベースケースはありますので、いわば、 nは直ちに2リターンのようないくつかの固定値を<されている場合は言うこの特殊なケース。その同じ円形の答えに応答しません。このプロセスは、この周期性は、最終的に終了します。私はあなたに言わせれば "ファイン、これらのn / 2を並べ替える"、 "これらのn個の要素を並べ替え"とあなたは言う次にあなたが言う、 "ファイン、これらのn / 4、π/ 8、N/16を並べ替える" 最終的には十分に大きな数で割りますあなたは、あなたが言うことができた時点で、わずか1要素の左を持っているだろう "ここ、ここにソート単一の要素です。" 次にこのアルゴリズムの輝きがここまで事実から派生することです一度は、これらの個別にソートされたリストがすべて揃っていること、無用と思われるサイズ1、であるこれらは全て、一度あなたがそれらをマージし、それらをマージし始めたロブは、ビデオで最後にソートされたリストを行ったように、あなたは最終的にビルドアップ。しかし、この考え方は、はるかにソートを超えて延びている。再帰と呼ばれるこのプログラムに組み込まれたこのアイデアは、ありますあなたがプログラムであることによりアイデア、そして、あなた自身を呼び出すいくつかの問題を解決するためにまたは、あなたが機能しているプログラミング言語のコンテキストに配置と問題を解決するためには、関数が自分自身を呼び出す何度も何度もくり返しますが、機能自分自身に無限に多くの時間を呼び出すことはできません。最終的には、いわば底打ちしなければならないと言って、いくつかのハードコードされた基本条件を持っているこの時点では、そうあなた自身の呼び出しを止める、そのプロセス全体最後に、実際には停止はない。これは本当に再帰的に、どういう意味ですか？我々は、言う、の、単純な、簡単な例を行うことができれば、見てみましょうここまでの段階で私と一緒に3人、誰かが快適であれば。まで、2と3で1を、来る。あなたは3がここに来たい場合。あなたがラインにここに私の隣に立って右側にする場合は、手でその問題を仮定非常に些細なことにここにいる人々の数を数えています。しかし、率直に言って、私はこれらすべてのカウント例の疲れ。これは、いくつかの時間、1、2、ドット、ドット、ドットを取るために起こっている。それは永遠に取るつもりです。私はただ助けを借りて、完全パントこの問題の、何あなたの名前ですか？むしろほしいのサラ。>>サラ、大丈夫。ケリー。>>ケリーと？ウィリー。>>ウィリー、サラ、ケリー、ウィリー。今、私は、誰かが質問をされましたどのように多くの人がこのステージに上がっており、私にはわかりません。これは本当に長いリストですので、代わりに私はこのトリックをするつもりです。私はほとんどの作業を行うために私の隣の人に依頼するつもりですが、そして一度、彼女はほとんどの作業をやって行われ私はできるだけ少ない操作を行うと、わずか1を追加するつもりので、ここで我々が行っているものは何でも彼女の答えに。私は、ステージ上にあるどのように多くの人が求めてきた。あなたの左にステージ上で何人ですか？オーケー？>>私の左が、カンニングしないでください。それが正しいだと、良いことだが、我々はこのロジックを続行するかどうか、あなたは同様にあなたの左にパントこの問題をすると仮定してみましょうそうではなく答えより直接先に行くと、ちょうど責任転嫁。ああ、私の左側には何人ですか？左には何人ですか？ 1。 [笑い] さて、0、だから何今ウィリーが行っているあなたはこの方向が0を言っ答えを返されました。さて、あなたは何をすべきでしょうか？>> 1。さて、あなたは1だので、あなたが言う、 "すべての権利、私は1を追加するつもりにどのようなウィリーのカウントだった "ので、1 + 0。右にあなたの答えがあるように、今や1だ今では 1 >>と鉱山は2になります。、良いので、1の前の回答を取っているあなたがやりたい仕事の最小限の量を追加して、1である。これで、2を持っていて、その後、私の値を渡す？ 3、私は、申し訳ありませんが、2を意味する。グッド。まあ、我々は左側に0を持っていた。、その後、我々は1を持っていたし、我々は2を追加そして今、あなたは私の2番を渡している、そして私は3、1、大丈夫、と言っている。この段階で私の隣に立っている3人は、確かにありますので、我々は明らかに、非常に直線的にこれを行っている可能性が明白な方法で非常に多く、私たちは本当に何をしましたか？当初はサイズが3の問題を取った。次に、サイズ2の問題にそれを壊したその後、サイズ1の問題、そして最後に、ベースケース本当に、ああ、そこに誰もありませんでしたその時点でウィリーは、数回効果的にハードコードされた答えを返さそして2つ目は、その後、バブルアップバブルアップ、バブルアップされましたその後追加のこの1 1に追加することによって、我々は、再帰のこの基本的な考え方を実装しました。さて、このケースでは、それは本当に問題を解決しなかった任意のより効果的に、我々はこれまで見てきました。しかし、我々はこれまで、ステージ上で行われてきたアルゴリズムを考える。私たちは、黒板に紙の8個を持っていたビデオにショーンは7番を探していた、と彼は本当に何をしたとき？まあ、彼は、除算のどんなことをして征服しなかった。彼は、再帰のどんなことをしませんでした。むしろ、彼はちょうどこの線形アルゴリズムをやった。しかし、私たちがステージ上でソートされた数字の考え方を導入したとき、先週暮らす次に我々は、真ん中に行くのこの本能を持っていたその時点で我々は、サイズ4またはサイズ4の別のリストの小さいリストを持っていたその後、我々は正確に同じ問題を抱えていたので、私たちは繰り返し、繰り返し、繰り返し。言い換えれば、私たちは再帰。私達と再帰を実証するためにここに私たち3人のボランティアにどうもありがとうございます。、我々は今、もう少し具体的なこれを作ることができないかどうかを確認してみましょう再び我々は非常に簡単に行うことがあった問題を解決するため、しかし、我々はこの基本的な考え方を実装するための足がかりとして、それを使用します。私は数字の束の総和を計算する場合は、例えば、あなたが3番で合格した場合、私はあなたにシグマ3の値を与えたい SO 3の合計+ 2 + 1 + 0。私は、答え6戻って取得したいので、我々はこのシグマ関数、この総和関数を実装しますつまり、もう一度、入力を取り込み、その後総和を返すその番号0までのすべての方法の。我々は、右、非常に簡単にこれを行うことができる？我々は、ループ構造のいくつかの種類でこれを行うことができますので、私は先に行くと、これは始めましょう。 stdio.hをインクルードします。ここで動作するように私は主に自分自身を取得しましょう。 sigma.cとしてこれを保存してみましょう。それから私は、ここに行くつもりです、と私は、int型のnを宣言するつもりだそして私は、ユーザーが協力しないしながら次のことを行うつもりです。ユーザーは私に正番号を与えられていないものの私が先に行くとn =の場合、getIntのためにそれらを促すことができ、そして、私は彼らに何をすべきかなど、いくつかの手順を示すことができそうのprintf（ "正の整数ください"）。時間によって我々は14行目にヒットするように、このような比較的単純なだけで何か我々は今のnおそらく正の整数があります。今それを使って何かをしてみましょう。ので、int型の合計=Σ（n）は、私が先に行くと、総和を計算しましょう。シグマは単なる総和であるので、私は手の込んだ方法でそれを書いています。我々は、ちょうどそこには、シグマと呼ぶことにします。それは和だし、今私は、結果をプリントアウトするつもりだのprintf（ "和は％dは、\ n"の合計）。そして私は良い測定のために0を返しています。我々は、面白い部分を除き、このプログラムが必要とするすべてのものをやったこれは、実際にシグマ関数を実装することです。私は底にここに降りて行き、私はシグマ関数を宣言してみましょうましょう。これは、整数型の変数を取るようになっているどのようなデータ型は、私はシグマからおそらく返すようにしたいのですか？ int型、私はそれが15行目で私の期待を一致させたいので。ここで私が先に行くと、これを実装してみましょうかなり簡単な方法で。先に進み、intの和= 0を言わせて、そして今、私はここでループのために少しを持って行くつもりですそれは、このような何かを言おうとしている合計+ = I（;、I <=番号i + +のint i = 0のとき）のために。そして私は和を返すつもりです。私は、任意の数の方法でこれを実装している可能性があります。私は、whileループを使用することもできました。私は、私が本当にしたい場合はsum変数を使用して、スキップしたかもしれないしかし、一言で言えば、我々はちょうど私がしなかったらへまは和が0であることを宣言している関数を持っています。それは、数字を通って0からの繰り返し処理し、反復のたびに、それは合計にその現在の値を追加し、合計を返します。さて、ここで若干の最適化あり。これはおそらく、無駄なステップですが、そのためである。今のところ、それで結構です。我々は、少なくともしている徹底していると、最大で0すべての道を行く。非常に硬く、非常に簡単ではない、それはシグマ関数と我々は同じ機会を持っていることが判明私たちはステージ上でここで行ったように。ステージ上で私達はちょうど、私の隣にいたどのように多くの人々にカウントその代わりに、我々は数3 + 2 + 1を数えたい場合 0までに我々は関数と同様にパントする可能性私の代わりに再帰的なものとして説明しますことを。ここでは簡単なサニティチェック、私がへまをしなかったことを確認してみましょうか。私が間違ってたんだ、このプログラムの少なくとも1つの事があると知っている。私は入力を打ったとき、私は私に叫んでの任意の種類を取得するつもりです？何私は約怒鳴らするつもりです？ええ、私はプロトタイプを忘れたので、私は15行目でシグマと呼ばれる機能を使用していますしかしそれは22行まで宣言なので、私は積極的にここで最高の上がらないだとプロトタイプを宣言し、私は（int型数値）int型シグマを言うよ、とそれはそれだ。これは、下部に実装されています。私はこれを解決することができ、または別の方法、私は、悪くなっていない、そこに機能を移動することができますしかし、少なくとも、あなたのプログラムは、率直に言って、長く得るために起動したとき私はいつも一番上にメインを持っていることのいくつかの価値があると思うあなたはリーダーでファイルを開き、その直後に見ることができるようにプログラムは、それを介して検索しなくてもやっていることその主な機能を探しています。、のはシグマはシグマを作る作ってみて、ここに私の端末ウィンドウにダウンして行こうと私はここにもしくじった。関数の場合、getIntの暗黙的な宣言は、私は他に何を行うのを忘れたことを意味？ [聞き取れない - 学生] 良いので、明らかに一般的な間違い、それでは、ここで、このアップを入れてみましょう cs50.h、今の私の端末ウィンドウに戻りましょう。私は、画面をクリアします、そして、私はシグマを行い再実行します。これは、コンパイルされているようだ。私は今、シグマを実行してみましょう。私は3番で入力しますと、私は6を手に入れた、そうではない厳密なチェック少なくともそれは一見しただけでは動作しているようだが、今度はそれをバラバラにすることができ、としましょう、実際には、再度、再帰の考え方を活用非常に単純な文脈でそのように数週間の時間内に私たちは、配列よりもより複雑なデータ構造の探索を開始するとき我々は、にしてツールキット内の別のツールを持っている我々がわかるように、これらのデータ構造を操作する。これは、反復的なアプローチは、ループベースのアプローチです。今これを行う代わりにさせて頂いております。数の総和と言う代わりに私を聞かせて 0までに本当にと同じものです番号+シグマ（数 - 1）。言い換えれば、ただステージ上のように私は、私の隣の人のそれぞれにパントそして、彼らは順番に、我々は最終的にウィリーを底までパントに保た誰が0のような、ハードコーディングされた答えを返すことがありました。ここで今、私たちは同様にシグマにパントしているここで最初に呼び出された場合と同じ機能ですが、キーの洞察力我々は同じようにシグマを呼び出していないことです。我々は、nを渡していない。我々は明らかに数を渡している - 1、そうわずかに小さい問題、若干小さい問題。残念ながら、これはまだかなりのソリューションではありません、我々は修正前あなた方のうちの何人かははっきりと何が飛び出すかもしれません私が先に行くとmakeを再実行してみましょう。それは大丈夫コンパイルするようです。私は6でシグマを再実行してみましょう。おっと、私は6でシグマを再実行してみましょう。我々としても誤って前回とはいえ、前にこれを見てきました。なぜ私はこの不可解なセグメンテーションフォールトを取得するのですか？うん。 [聞き取れない - 学生] おそらく何が起こったのか、より具体的にはそこにはベースケースはありません、と？これは何の行動の症状ですか？もう少し大きな声でそれを言う。 [聞き取れない - 学生] それは効果的に無限ループだし、無限ループに問題がある自分自身を呼び出し、彼らがこのケースでは再帰を含む、関数、何は、関数を呼び出すたびに起こりますか？まあ、我々はコンピュータのメモリを打ち出した方法に戻すと思います。我々は、最下部のスタックと呼ばれるメモリのこの塊があることを言ったもう少しメモリが置かれる関数を呼び出すと、毎回その関数のローカル変数やパラメータを含むこのいわゆるスタック上で、シグマはシグマ·コールを呼び出すので、もしシグマはシグマ呼び出しこの物語の終わりを行いどこシグマコールします？まあ、それは最終的にオーバーラン総額お使いのコンピュータに使用可能であることメモリの。あなたは、あなたが内に滞在することになっているセグメントを、オーバーランそしてあなたはこのセグメンテーションフォールトを取得、コアは、ダンプとダンプ何コア意味は、私はコアと呼ばれるファイルを持っているということですこれは、0と1を含むファイルですことは、実際には将来における診断に有用であろう。あなたのバグがどこにあるか、それはあなたに明らかではない場合あなたは実際に、いわば、法医学的分析のビットを行うことができます再び、ちょうどゼロとものの全体の束であり、このコアダンプファイル、上本質的に、メモリ内のプログラムの状態を表す瞬間、それはこのように墜落した。ここで修正は、我々はただやみくもに、シグマを返すことができないということです数+若干小さい問題のシグマ。我々はここで、ベースケースのいくつかの種類を持っている必要があり、とベースケースは、おそらく何すべきですか？ [聞き取れない - 学生] わかりましたので、長い数値が正であるとして、我々は実際に、これを返すべきあるいは別の言い方をすれば、数であれば、言う、<= 0〜あなたは、私が先に行くと0を返します何、知っているウィリーがやったのと同じように、そしてそれ以外に、私は先に行くつもりですこれを返すので、それはそれほど短くないです我々は最初のforループを使って手早くことを反復バージョンより、それにエレガンスのこの種があることがわかります。代わりにいくつかの数を返し、すべてこの演算を行うのとローカル変数で物事を加算これは超簡単な問題である場合は、代わりに、オーケー "と言っている、数が<0であるように、私はすぐに0を返すようにしてください。 " 我々は、支持負の数を気にするつもりはないので、私はハードコードに0の値をつもりです。しかし、そうでなければ、加算のこのアイデアを実装するあなたが効果的に小さな一口を取ることができます一緒にこれらの数字のすべて外の問題、私たちがステージ上でここでやったのと同じように、その後パント次の人に問題の残りの部分、しかしこのケースでは次の人が自分自身である。これは、同じ名前の関数です。ちょうどそれは、小さく、小さく問題を毎回渡すそして我々はここに、コード内ではない非常に形式化されたものを持っているにもかかわらず、これは、電話帳で0週目に何が起こっていたかを正確になります。これはショーンとの過去数週間で起こっていたとおりのものであると番号を検索私たちのデモンストレーション。それは問題を取って、何度も何度もそれを分割だ。言い換えれば、翻訳の今方法があるこの現実世界の構造物、このような高いレベルの構成分割統治と何度も何度も何かをするコードの中で、これは我々が時間をかけて再び表示されます何かである。あなたは再帰に慣れていないさて、余談として、あなたは、少なくとも今理解しておく必要がありますなぜこれが面白いです。私は、google.comに行くつもりですと私は再帰のいくつかのヒントやトリックを検索するつもりだ、と入力します。彼らはちょうど今笑っていなかった場合、あなたの隣の人を教えてください。あなたは、再帰を意味しましたか？あなたがしたことを意味 - ああ、そこに私達は行く。さて、それは皆の残りです。グーグルでどこかに埋め込まれた小さなイースターエッグ。余談ですが、私たちはもちろんのウェブサイトに置くのいずれかのリンク今日のために、単に様々なソートアルゴリズムのこのグリッドです我々は先週見ましたが、何がこの可視化についての素晴らしいですそのうちのいくつかあなたは、アルゴリズムに関連する様々な物事の周りにあなたの心をラップしようとしてあなたは非常に簡単になりました、異なるタイプの入力で開始できることを知っている。入力はすべての入力がランダムなど、入力はほとんどソートされ、逆転した。あなたがしようとして、もう一度、あなたの心にこれらのものを区別する講義ページでコースのウェブサイトにこのURLを実現もしそれらのいくつかを理由に役立つかもしれない。今日、我々は最終的に、しばらく前から、この問題を解決するために取得これは、このスワップ機能がうまく動作しなかったということでしたそして、この関数swapを持つ根本的な問題は何だったの目標は、こことここに値をやりとりするために、再び、でしたこれが発生するような？これは実際には動作しませんでした。なぜですか？うん。 [聞き取れない - 学生] まさに、このbugginessの説明あなたがC言語の関数を呼び出すときというだけの理由だったそれらの関数は、aとbここのように、引数を取るあなたはその関数に提供している任意の値のコピーを渡しています。あなたは、元の値自体を提供していないので、我々は、buggycの文脈でこれを見たこのような少し何かを見てbuggy3.c、。我々はxとyがそれぞれ1と2に初期化していたことを思い出してください。我々は、彼らが何であったかをプリントアウト。私はその後、私はx、yのスワップを呼び出すことによって、それらをスワッピングされたと主張した。しかし、問題は、スワッピングが働いていたということでしただけスワップ機能自体の範囲インチ我々は、40行目これらスワップの値を打つとすぐに捨てられた、など何もない元の関数でメインは実際にはまったく変更されました、ので、これは私たちの記憶の面でどのように見えるかのように当時と思われる場合このボードの左側を表している場合、と私は見て皆のために全力を尽くしますこの-IFボードのこの左側表し、あなたのRAMを言うと、スタックは、この上昇途中で成長しようとしている私たちは主のような関数を呼び出すと、メインは、2つのローカル変数xとyを持っています、ここでxとしてそれらを記述し、これらのヒアyなどを記述してみましょうそして、そう、これはここのメインですが、値1と2を入れてみましょうそしてメインは、オペレーティングシステムのスワップ関数を呼び出すときにスタックにスワップ機能、メモリの独自スワスを与えるスタック上の独自のフレームは、いわば。また、これらの整数のための32ビットを割り当てます。それは彼らとbを呼び出すことになりますが、それは全くの自由です。それはそれは望んでいるものは何でもそれらを呼ばれるかもしれないが、ときにメイン何が起こる通話スワップは、それが、この1を取りそこにコピーを置き、そこにコピーを置きです。スワップの1他のローカル変数があります、しかし、何と呼ばれる？>> tmpです。 tmpは、だから、私は自分自身にここで別の32ビットを与えることができますと私は、この関数の中で何をしましたか？私はint tmpが取得言ったので1を持っているので、我々が最後にこの例でプレイした時、私はこれをしなかった。次にbを取得するので、bが2であるので、今、これは2になり、そして今、bは温度を取得するので、一時は1ですので、今bがこのになります。それは素晴らしいことだ。うまくいった。しかし、その後、できるだけ早く関数が戻ったとしてスワップのメモリを効果的にそれを再利用できるように消える将来的には他のいくつかの関数によって、メインは明らかに完全に変更されていません。我々は、この問題を根本的に解決するための方法が必要今日我々は最終的にそれによってこれを行う方法があるでしょう我々は、ポインタと呼ばれるものを導入することができます。それは、我々はこの問題を解決することができることが判明 xとyのコピーを渡していないことによってその代わりに何かを渡すことによって、スワップ機能に、思いますか？うん、何のアドレスでしょうか？私たちは本当に、はるかに詳細にアドレスについて話をしていないしかし、この黒板は私のコンピュータのメモリを表す場合我々は確かに私のRAMにバイトに番号を開始することができますそして、これは第1バイトであると言う、これはバイト＃3、＃2バイトですバイト＃4、バイト＃...20億私は2 GBのRAMを持っている場合、ので、我々は確かにいくつかの任意のナンバリングスキームを考え出すこと私のコンピュータのメモリ内のすべての個々のバイトのために。私はスワップを呼び出したときに代わりになら xとyのコピーを渡すのではなく、なぜ私が代わりに、ここでxのアドレスを渡さない基本的にここでyのアドレス、住所 xとyの彼は知らされている場合、その後、スワップので xとyのメモリ内のアドレスの、我々は彼を少し訓練した場合、その後、スワップ彼は潜在的に、いわば、そのアドレスに運転できる xおよびyのアドレスにドライブしてから、そこに番号を変更し、実際にそれらの値自身のコピーを取得していないながらも、そこに番号を変更し、我々は、メインのメモリであるとして、このことについて話しましたようにもかかわらず、そしてこれであるスワップのメモリのようなCの強力かつ危険な部分どの関数でも、どこでもコンピュータのメモリに触れることができるということですそしてこれはあなたがC言語でコンピュータプログラムで非常に派手なことを行うことができるという点で強力ですあなたは、非常に簡単に台無しにすることができますので、これは危険です。実際には、これらの日のプログラムのための最も一般的な方法のいずれかが悪用されるまだ実現していないプログラマです彼または彼女はデータを許可されていること意図していなかったメモリ内の場所に書き込まれるようになります。例えば、彼または彼女はサイズ10の配列を宣言しかしその後誤って、メモリの配列に11バイトを入れようそしてあなたは、もはや有効ではないメモリの部分に触れ始める。ちょうどこの文脈に、あなた方のうちの何人かは知っているかもしれないソフトウェアは、多くの場合、シリアル番号または登録キーの入力を求めるプロンプトが表示さ PhotoshopやWordやこのようなプログラム。あなた方のうちの何人かが知っているように、あなたは少しプログラムを実行することができますオンラインの場合には、亀裂が存在すると出来上がり、シリアル番号のためのこれ以上の要求。それはどのように機能しているか？多くの場合、これらの事は、単にコンピュータで発見しているコンピュータの実際のゼロともののテキスト·セグメントシリアル番号が要求され、その機能は、どこにあるのプログラムが実行されている間、あなたはその領域を上書きするか、またはキーが実際に格納されている場所は把握することができます何かを使用すると、デバッガと呼ばれ、あなたは、ソフトウェアをそのように解くことができます。これは、この数日の次のカップルのための私達の目的であると言っているわけではないそれは非常に現実世界の影響を及ぼす。 1つはソフトウェアの窃盗を巻き込むことが起こることを、しかし、全体のマシンの妥協も用意されている。このごろWebサイトが悪用されている事実では、と妥協し、データが流出され、パスワードが盗まれてこれは非常に多くの場合、1つのメモリの貧弱な管理に関しまたは、データベースの場合には、障害が予測する来て数週間で、その上で非常に多くの敵対入力、しかし、今のあなたが行うことができます損傷の一種のちょうどスニークプレビューかなり物事はフードの下にどのように動作するか理解していないことによって。これが壊れた理由の理解については、行ってみようますます便利になるツールを使って我々のプログラムは、より複雑になるとして。これまでのところ、あなたのプログラムのバグを持っていたときどのようにあなたはそれをデバッグする方法行った？何があなたのテクニックは、あなたのタスクフォースによって教えかどうか、これまであったそれとも独学？ [生徒]のPrintf。あなたが見たい場合はprintfのため、printfはおそらくその中にあなたの友人であったあなたのプログラムの内部で何が起こっているのかあなただけのprintfここでは、printfここ、ここのprintf置く。あなたはそれを実行し、あなたは、画面上のものの全体の束を得るあなたは、実際にあなたのプログラムの中で間違っているものを推測するために使用できる。 printfは、非常に強力なものになる傾向があるそれは非常に手動プロセスです。あなたは、printfはここ、ここのprintfを入れているあなたは、ループの中にそれを置けば、あなたは100行を取得する可能性がありあなたは、取捨選択する必要がある出力の。それは、プログラムをデバッグするための非常にユーザーフレンドリーまたは対話メカニズムではありませんしかしありがたいことに代替案が存在する。 GDBというインスタンスのためのプログラム、、、GNUデバッガは、ありそれはあなたがそれを使用する方法で少し難解です。それは、少し複雑ですが、率直に言ってこれはあなたがこの週に置けばそれらのものの一つであり、次の GDBのような何かを理解するために余分な時間それは長期的には、おそらく数十時間を節約します、そうということで、私はあなたにこの事はどのように動作するかのティーザーを与えることができます。私は、ターミナルウィンドウにいるよ。私が先に行くと、このプログラム、buggy3をコンパイルしてみましょう。これは既に最新です。我々はしばらくバックを行なったし、確かに、それが壊れているだけのように私はそれを実行してみましょう。しかし、これはなぜですか？たぶん私はスワップ機能を台無しに。たぶんそれは、aとbです。私は非常にそれらを正しく周りに引っ越すわけではない。私が先に行くとこれをやってみましょう。だけではなく、私が代わりにこのGDBというプログラムを実行してみましょうbuggy3実行と私は、buggy3を実行するためにそれを言うつもりですと私は、コマンドライン引数、-tuiを、含めるつもりです私たちは忘れないようにスペックで将来の問題でこれを置くことにしましょう。そして今、この黒と白のインターフェイスは、再び、それをポップアップこのすべてがあるので、最初は少し圧倒されるここに保証情報が、少なくともおなじみのものがあるように感じる。ウィンドウの上部には、私の実際のコードです。私が上にスクロールした場合、ここで、私は私のファイルの最上部にスクロールしてみましょうそして実際に、このウィンドウの下部にbuggy3.c、予告あり私はこのGDBはプロンプトを使用している。これは私の通常のジョンハーバードプロンプトと同じではありません。これは私がGDBを制御できるように起こっているプロンプトです。 GDBはデバッガです。デバッガでは、ウォークスルーできるプログラムです行ずつ付けて、プログラム行の実行、プログラムしたい何もして道に沿って、でも、もっと重要なのは、関数の呼び出し、または探しさまざまな変数の値で。先に進み、これをやってみましょう。私は先に行くと、GDBのプロンプトで実行で入力するつもりだ、ので、私が入力し実行した画面の左下に気付く、と私は入力を打ちました、それは何をしましたか？それは文字通り私のプログラムを実行しましたが、私は実際にははるかにここに行くのを見ませんでした私は実際にデバッガを語っていないので、特定の時点で一時停止する。ただランを入力すると、プログラムを実行します。私は実際には何も表示されません。私はそれを操作することはできません。代わりに私はこれを行うことができます。このgdbプロンプトで私が代わりに入力して、改行を入力してみましょう。それは私が入力するどのような意味ではありません。代わりにメイン破る入力してみましょう。言い換えれば、私はブレークポイントと呼ばれるものを設定したい、それが壊れる、または一時停止するので、適切に命名されるその特定の場所であなたのプログラムの実行。主は、私の関数の名前です。 GDBはかなりスマートであることに注意してください。これは、メインは18行で約開始に起こることを考え出し buggy3.cから、次に左上にここに気が付く B + 18行目のすぐ隣にあります。それは私が18行目にブレークポイントを設定していることを思い出させてくれている。この時間は、私が実行を入力したとき、私は私のプログラムを実行するつもりですまでそれがそのブレークポイントに達するまで、ので、プログラムは18行目で、私のために一時停止します。ここに私達は行く、実行します。何が起こっているように見えませんが、左下の予告起動プログラム、buggy3、buggy3.cライン18でメインにブレークポイント1。私は今何ができるのか？私は、印刷のようなものを入力して起動することができます注意してください不思議だ今ではないのprintf、プリントx、および。これから見るように$ 1は、単に好奇心ですあなたが何かを印刷するたびに、新しい$値を取得します。つまり、あなたは、念のために以前の値に戻って参照することができるようだしかし今ではプリントが私に言っている何のために物語の中で、この時点でxの値ということですどうやら134514032です。何ですか？それもどこから来たのか？ [聞き取れない - 学生] 確かに、これは我々がゴミ値と呼んでいるものであり、我々は、まだこのことについて話していませんでしたしかし、変数を初期化している理由明らかに、彼らはあなたがそれらを持っているしたいいくつかの値を持っているということです。しかし、漁獲量は、変数を宣言することができることを思い出している私はシグマの例では少し前やったように実際にそれらに価値を与えることなく。私はシグマでこっちにやったことを思い出してください。私は、nを宣言したが、私はそれをどのような価値を与えましたか？なし、私は知っていたので、その次の数行で getIntは、nの値を内部に入れての問題の世話をするだろう。しかし、この時点で11行目の物語およびライン12およびライン13とライン14 それらのいくつかの行全体でnの値は何ですか？ C言語では、あなただけ知らない。これは、一般的にいくつかのゴミの値は、いくつかの完全にランダムな数だ以前のいくつかの関数から本質的に上に残っているあなたのプログラムが実行されるように、実行された関数は、関数、関数、関数を取得することを思い出す。これらのすべてのフレームは、それらの関数の戻り値をメモリに格納され、その取得と同じように私は自分のメモリが再利用され、最終的に消しゴムで示唆された。まあ、それはちょうどので、このプログラムでは、この変数xが起こる 134514032のようないくつかのゴミの値が含まれていたようだ以前のいくつかの機能ではなく、私が書いたものから。これは、オペレーティングシステムと効果的に来るものかもしれないボンネットの下にいくつかの機能。さて、それは大丈夫ですが、今は次の行に進みましょう。私はgdbプロンプトで "次へ"を入力した場合、私は、ENTERキーを押して上下線19に強調表示が移動する予告、しかし、論理的な含意は18行目です "×プリント"私再びタイプ場合は、ここで、実行が終了した私は今、1が表示されるはずですし、実際、私はありません。繰り返しになりますが、$のものはあなたを思い出させてGDBの方法です版画の歴史はあなたがやったことは何です。、今私は先に行くとyをプリントアウトしてみましょう、そして実際に、yは同様にいくつかのクレイジーな値ですしかし、大したことない、我々はそれを代入しようとしている19行目にあるので、値2は、ので、私は再び "次へ"を入力してみましょう。そして今、我々は、printfの行にしている。私はプリントXをやってみましょう。私はプリントyをやってみましょう。率直に言って、私はこれを印刷したのにちょっと飽きたよ。私が代わりに "ディスプレイx"と "ディスプレイyを、"入力しましょうそして今、すべての時間は、私は、将来的にコマンドを入力します。私は何のことを思い出したことでしょう何、xとyは、xとyは、xとyは何でしょう。私がすることができますまた、余談で、タイプとして "info localsを。" infoは、特殊なコマンドです。地元の人々はそれが私にローカル変数を示していますを意味します。私は忘れてしまったり、これはクレイジー、複雑な関数であり、念のために私や他の誰かが地元の人々はあなたを教えてくれる情報を書いたこのローカル関数内に存在するすべてのローカル変数は何ですかあなたはつつくしたい場合は気かもしれない。さて、printfは実行しようとしているので、私が先に行くとだけ入力してみましょう "次。" 我々はこのような環境にいるので、我々は実際にそれを見ていないここに実行されますが、それはここで少し台無しにされたなってきて気づく。しかし、それはそこに画面を上書きして気付くので、ここで完璧なプログラムではありませんが、私はいつも周りをウロウロすることができるので、それは大丈夫だ私が欲しい場合は、プリントを使用しています。私は次回、もう一度入力してみましょうと、今ここには面白い部分です。物語のこの時点では、yは2であり、xは1ですここで示唆したように、再度、私は、コマンドを使用しているので、これは自動的に今表示している理由は、ディスプレイのxとyのディスプレイ、私は次のように入力した瞬間理論xとyでスワップになる必要があります。今、我々はすでにケースであることを行っていないことを知って、しかし、我々は、我々はそれが本当だ理由を把握し深くダイブする方法瞬間にわかります。次に、残念ながら、yは2のままであり、xは1のままである、と私は同じくらいを確認することができます。プリントのx、yをプリント。確かに、スワッピングは、実際に起こっているので、これは最初からやり直してみましょうん。明らかにスワップが壊れています。代わりに、再度 "実行"と入力してみましょう。私は、はい、私は最初からそれを再開したいとしましょう、次のように入力します。今、私は背中のラインアップ18時だ。今では、xとyに気づく再びゴミの値です。次の、次の、次の、次の。私が退屈なら、私もちょうど次のためにnを入力することができます。あなたは文字の最短のシーケンスに短縮することができます。スワップは現在壊れています。代わりに次の入力するので、でのダイビングをしましょう、今私はこの関数の内部ステッピングてるようにステップを入力するつもりですので、私はそれを歩くことができるので、私はステップをヒットしてから入力してください。 36行目に、私のプログラムでダウン強調ジャンプ低いことに注意してください。これで、ローカル変数は何ですか？ info localsを。我々はそのラインに到達していませんでしたので、今はまだ何もありません、それでは、先に行くと言わせて "次。" 今、私たちは、tmp、プリントtmpを持っているように思われる。ガベージ値、右か？そう思います。方法については、プリントB、1と2を印刷しますか？一瞬にして、できるだけ早く、私は次のように入力し、もう一度 tmpは、うまくいけば、1の値をとることになるだろう tmpに値を割り当てることが起こっているからです。さて、プリントBを印刷できますかしてみましょうしかし今tmpを印刷して、それは確かに1です。私は次に何をしましょう。私は次に何をしましょう。私はスワップ機能を終えたところです。私は40行目でその中にまだだので、私はプリントでき、 bを印刷して、私はtmpが何であるかを気にしないでください。それはaとbを入れ替えることになるとスワップが正しいように見えます。しかし、私は今、次の入力した場合、私は、25行目にジャンプそしてもちろん、私は、xとyに印刷と入力した場合彼らはまだ変わらないなら、私たちは問題を修正していない。しかし、診断的に今、おそらくこのGDBのプログラムと我々は少なくとも理解に一歩近づく得てきた何がここにprintfを入れてゴミに我々のコードを持たずに間違っただろう、 printfはここでは、printfここをチェックして何度も何度もそれを実行している間違って何が起こっているのかを把握しよう。私はやめるとまとめて先に行くとこの途中で辞めたいと思います。それは言うだろう "終了しますか？"はい。さて、私の通常のプロンプトに戻っている、と私は、GDBを使用して行われています。余談ですが、この-tuiコマンド·フラグを使用する必要はありません。あなたはそれを省略した場合は実際には、本質的に、画面の下半分を取得します。私はその後、壊すメインを入力し、実行した場合私はまだ私のプログラムを実行しますが、それが何を行いますと、より字面であることができますちょうど時間で私に現在の回線1を示しています。 -tuiコマンド、テキストユーザーインターフェース、ただおそらく少し概念的に簡単である、あなたに一度プログラムの詳細を示しています。しかし、確かに、私はちょうど、次の、次の、次に何をすることができますそして、私は、一度に1つの行を見に行くつもりだし、私は実際に何が起こっているか確認したい場合私はリストを入力し、隣接するラインの全体の束を見ることができます。我々は問題は3を設定するためには、見ることを尋ねてきたビデオがありますたネイトは、GDBの複雑さの一部をカバーこれは、正直なところ、ものの一つがどこにあるのいくつかの非自明な割合 GDBには決して手を触れないようになり、それは悪いことであろう文字通り今学期は後で多くの時間を費やしてしまいますので、バグを追跡し、あなたにはその半分の時間/時間に入れたい場合今週とGDBに慣れるための学習の隣。 printfのあなたの友人だった。 GDBはあなたの友人である必要があります。 GDB上で何か質問はありますか？そして、ここでは最も強力で、有用ないくつかのコマンドの簡単なリストです。うん。>>は、文字列を印刷することはできますか？あなたは、文字列を印刷することができますか？絶対に。それはただの整数である必要はありません。変数sは、印刷sに入力するだけの文字列である場合。それは、その文字列変数が何であるかを紹介します。 [聞き取れない - 学生] それはあなたのアドレスや文字列自体を与える。それはあなたの両方が表示されます。これらはあまりにも知って良いという理由だけと最後にひとつ。バックトレースおよびフレームは、私は、この最後の一時間に飛び込むことができ GDBでまったく同じプログラム。私が先に行くとテキストユーザインタフェースのバージョンを実行してみましょう、メイン破る。私が先に行くと、再び実行してみましょう。私はここに。今私は、次の、次の、次の、次の、次の、ステップを手放すように入力します。そして今は、私が意図的にスワップに今だと仮定しますが、私はのようだ "くそー、xの値は何だったの？" 私はもうxを行うことはできません。彼らは範囲にいないので、私はyを行うことはできません。彼らは、文脈が、問題なしではないね。私は、バックトレースを入力することができます。それは私に、この時点までに実行したすべての関数を示しています。底面に1つ、メインとメイン、ラインアップすることに注意してくださいここに私たちの絵の下部にある。スワップは、スワップがここにメモリにそれより上であることと、それまでの線の上にあるという事実は、と私は一時的にメインに戻って取得したい場合、私は "フレーム"を言うことができる何番？メインフレームでは、＃1です。私は先に行くと言うつもりだ "フレーム1" 今、私はメインに戻っている、と私はxを出力することができます、と私は、yを印刷することができますしかし、私はaまたはbを印刷することはできません。私が言う場合、私は、 "よし、ちょっと待って。どこスワップでしたか？"することができます私が先に行くと言わせて "フレーム0"になります。今私はなりたいところ戻ってきた、と余談ですが、あなたが本当に、次の次の、次の、次のように入力退屈になってしまった場合のような他のコマンドでは、あまりにもありあなたは一般的には "次の10"のようなものを言うことができる、それが次の10行をステップ実行します。また、あなたが本当にそれをステップにうんざりしたら、 "続ける"を書くことができる。それは別のブレークポイントに達するまで継続するが、中断せずにプログラムを実行しますループ内かどうか、プログラムで下げる。この場合、我々は最後まで継続され、プログラムが正常に終了しました。これは空想方法、下位プロセスである。ちょうどあなたのプログラムが正常に終了しました。ビデオの中と来てセッションをデバッグするときに、その方法の詳細。それがたくさんあった。レッツは、ここで我々の5分間の休憩を取り、我々は、構造体やファイルを返しています。あなたはすでに、今週のpsetに飛び込んしている場合あなたは私たちが配布コードで使用することを知っているよ、我々が出発点としてあなたに提供するソースコードは、いくつかの新しい技術。特に、我々は、構造のため、構造体と呼ばれるこの新しいキーワードが導入されましたので、我々はあらゆる種類のカスタマイズされた変数を作成することができます。我々はまた、ファイルI / O、ファイル入出力の概念を導入そしてこれは我々が状態を保存できるようになりあなたのスクランブルボードのディスク上のファイルへティーチングフェローと私は理解できるように、手動で再生することなく、あなたのプログラムの内部で何が起こっているのスクランブルのゲームの数十。我々は、より多くautomatedlyこれを行うことができます。構造体のこのアイデアはかなり説得力のある問題を解決します。我々はいくつかのプログラムを実装したいとし何とかして学生に情報を追跡している、と学生は、例えば、名前をIDをお持ちかもしれませんとハーバード大学のような場所での家なので、これらは、情報の3作品です私たちの周りを維持したいので、私が先に行くと、ここで少しプログラムを書き始めることができ、 stdio.hをインクルード。私はcs50.h.を含めるやってみましょうそして、私の主な機能を起動します。私は、任意のコマンドライン引数を気にしないでしょうそしてここで私は学生を持つようにしたいので、私は言うつもりです学生は名前を持っているので、私は言うつもりです "という文字列の名前を。" それから私はまた、IDを持っているので、int型のID学生を言おうとしてんだけど、と学生が家を持っているので、私も言うつもりです "という文字列の家を。" それから私はこのようにもう少しきれいにこれらを注文します。さて、私は "学生"を生徒に表現すると3つの変数があるので、そして今、私はこれらの値を移入したいので、私が先に行くと何かのように言わせて "ID = 123。" 名前はダビデを取得する予定です。、家はメイザーを得ようとしていると言ってみましょうそして私は任意のprintf（ "％sのような何かをするつもりだ、は、ID％dですが、％sに住んでいます。そして今、私は、ここにプラグインするために、他の後に1が何をしたいですか？名前、ID、家、0を返します。さて私はどこかここで、台無しにしない限り、私たちは一人の学生を格納かなり良いプログラムを持っていると思う。もちろん、これはすべてが面白くありません。私は2名を持つようにしたい場合はどうなりますか？それは大したことない。私は2人をサポートすることができます。私が先に行くと、これをハイライト表示して、ここに行ってみよう、と私はカークランドに住んでいるロブのような誰かのための "id = 456"と言うことができます。さて、、待って、私はこれらの同じものを呼び出すことはできませんと私はこれをコピーする必要がありますするつもりのように見える、ので、私はこれらはダビデの変数になることを言わせて、と私はロブのためにこれらのいくつかのコピーを取得してみましょう。我々は、これらのロブのを呼ぶことにしますが、これは今では仕事に行くのではない私はウェイトを持っているので、私ID1、name1とhouse1に変更してみましょう。ロブは、2になります。私はここ、ここ、ここ、ここ、ここ、ここ、これを変更するんだ。待って、何トミーはどうですか？再びこれを行うにしてみましょう。それでも、これはこれを行うための良い方法だと思う場合、明らかに、それはありませんそんなに悪いコピー/ペーストする。しかし、我々は一週間前にこの問題を解決しました。我々は、同じデータ型の複数のインスタンスを持っていると思ったときに私たちのソリューションは何でしたか？ [学生]配列。アレイは、ので、私はこの上をきれいにしてみましょう。私は一番上に自分のためにいくつかの部屋を作ってみましょう、と私は代わりにここでこれを行うことができます。 "で、int idを"我々は、これらの人を呼ぶことにし、代わりに私が言おうとしてると私は今の私たちの3をサポートするつもりです。私は、 "文字列の名前"と言うと私は、私たちの3をサポートしますつもりですが、そして私は、 "文字列の家"を言おうとしていると私は私達の3をサポートするつもりです。今ここに代わりにダビデの年に彼自身のローカル変数を取得我々はそれらを取り除くことができます。それは我々がこれをクリーンアップしていることを良い感じ。私はその後、デイヴィッドは[0]と名前が[0]であることを行っていると言うことができますや住宅[0]。そして、我々は同様にこれを保存することができますロブ。のは、この下にここに置いてみましょうので、彼は勝手にIDを[1]になるだろう。彼は名前になるだろう[1] その後最後に、家[1]。私はこれを理解しなければ、まだ少し退屈な、そして今、そう言ってみましょう "の名前[0]、ID [0]、ハウス[0]、これを複数形にしてみましょう。 IDS、IDS、イド。そして再び、私はそれをやっているので、もう一度、私はすでに、再びコピー/ペーストに頼るよそうオッズは別の解決策がここにありです。私はおそらく、そのようなループか何かでアップ、さらにこれをきれいにすることができるそう簡単に言えば、それは少しましだけど、まだのような感じ私は、コピー/ペーストに頼るんだけど、この場合でも、私は主張する本当に根本的に正しい解決法ではないので、いつか私たちは、あなたが何を知っていると判断した場合でしょうか？私たちは本当にダビデとロブの電子メールアドレスを格納されている必要がありますそして、このプログラムの皆。また、電話番号を格納する必要があります。また、緊急連絡先の電話番号を格納する必要があります。私たちは、格納するデータのすべてのこれらの部分を持っているので、どのようにあなたはそれをやって行くのですか？あなたは、一番上にある別の配列を宣言してから、手動で追加メールアドレス[0]は、電子メールアドレス[1] デイビッドとロブのためになど。しかし、この設計の基礎となる仮定は本当にあり私はそれを知っている名誉のシステムを使用していること [i]はいくつかの配列のそれぞれのちょうどので、同じ人物を参照するために起こるので、[0] idsに数123、ですと私はその名前を仮定するつもりです[0] ある同じ人の名前や住宅[0] 私が作成したさまざまなアレイのすべてのための同じ人の家などである。しかし、どんな基本的なリンケージがないことに気付く情報、ID、名前、家のそれら3個のうち、にもかかわらず、我々はこのプログラムでモデルにしようとしている実体は配列ではありません。配列は、これを行うだけで、このプログラム的な方法です。私たちは本当に我々のプログラムでモデル化したいのは人であるデビッドは、その内部のロブのような人のようなまたはカプセル化は、名前とIDと家です。我々は何とかカプセル化のこの考えを表現することができますそれによって人は、ID、名前、家を持っているそして本当にこのハックに頼ることができる我々だけそのブラケット何かを信頼これらの異種配列の各々に同じ人間の実体を指す？我々は、実際にこれを行うことができます。私は今のところ、上記のメインに行く、と私は私自身のデータ型を作成させてみましょう初めて本当にために。我々は、スクランブルでこのテクニックを使用しかしここで私は、先に行くとデータ型を作成するつもりです、あなたは何を、私は、それを学生や人呼ぶつもりだ知っていると私は型を定義するためにtypedefを使用するつもりです。私は、これは構造体であることを言おうとしてんだけど、その後この構造はタイプの学生であることを行っている、我々は言うだろうそれは私のために今付け少しは言っても。我々は "int idを。"と言うでしょう私たちは、 "文字列名を"言うよその後、我々は "文字列の家を、"言うよので、今の数行のコードの終わりまで私はただそこに存在することを打ち鳴らすを教えてきました文字列以外にint型以外のデータ型には、ほかに山車のほかに、倍になります。タイムライン11のこの瞬間のように、学生と呼ばれる新しいデータ型は、今があるそして今、私は、どこにも私が欲しい学生の変数を宣言することができますので、私は人々にここまでスクロールダウンしてみましょう。、今私はこれを取り除くことができ、私はここでダビデに戻ってダウン状態になることができますとデビッドのために私は実際にダビデ、と言うことができます我々は、文字通り、自分の後に変数に名前を付けることができますタイプの学生であることを行っている。これは少し奇妙に見えるかもしれませんが、これはすべてその違いはありません intやstringやfloatとして何かを宣言してから。それはちょうどので、今では学生と呼ばれるようなことが起こると私は、この構造体の内部に何かを入れたい場合、私は今、構文の新しい部分を使用する必要がありますが、それは非常に簡単だ david.id = 123、Dの資本david.name = "デビッド"、とdavid.house = "マザー" そして今、私はここでこのようなものを取り除くことができます。私たちが今本当に多くの、より良い方法で我々のプログラムを再設計しました注意してくださいという点で、今私たちのプログラムは、現実の世界を反映しています。人や学生の現実世界の概念があります。ここで我々は今、人またはより具体的に学生のCバージョンを持っています。その人の内側には、これらの関連する特性である ID、名前、家なので、ロブは、本質的にダウンしてここに同じことになり、、学生奪うので、今= 456 rob.id rob.name = "ロブ。" 変数はロブと呼ばれているという事実は無意味のようなものです。我々はそれをxまたはyまたはzということがありました。私たちはただ、それが意味的に矛盾しないようにロブ名前しかし実際の名前には、そのフィールド自体の内部にある今私はこれを持っている。これは、あまりにも私が一生懸命、ダビデをコーディングしましたという点で最高のデザインのような気がしない。私は懸命にロブをコーディングしました。そして、私はまだいくつかのコピーに頼ると私は、新しい変数をするたびに貼り付ける必要があります。また、私は、明らかにこれらの各変数に名前を付ける必要がある私はむしろ、これらの変数を記述したい場合でも、より一般的に学生として。今、私たちは私たちのためによく働いているアイデアをマージすることができますその代わりに、あなたは私と呼ばれる変数の学生を与えるもの、知っている "と言う。そして今、私はこれがさらに絞り込むことができますように "、のそれのサイズが3であることが持ってみましょう、手動で宣言されたデビッドを取り除く、と私の代わりに[0]ここの学生のようなものを言うことができます。私はその後、[0]ここの学生を言うことができます学生[0]ここなど、そして私の周りに行くことができますとロブのためにそれをクリーンアップします。私も今、多分ループを追加することについて行けそして実際にユーザーからこれらの値を取得するGetStringメソッドとgetIntを使用。これは一般的に悪い習慣であるので、私は定数を追加することについて行け右ここでは3のようにハードコードするいくつかの任意の番号その後、ちょうどあなたがそれで3つ以下の学生を置くべきであることを覚えておいてください。それはおそらく私のファイルの先頭に＃defineを使用する方が良いだろうと出ますので、確かに、私が先に行くと、これを一般化させている要因。私は今日の間の例を開けてみよう事前に例structs1。これは、＃ここまで定義し使用するより完全なプログラムです我々は、デフォルトでは3人の学生を持っているとしていると言っている。ここで私は、学生のクラスの価値を宣言しています生徒の教室はそうしましたが、今は、ループを使用していますただ、コードがもう少しエレガントにするために、クラスを生成するユーザの入力と、そうまでのi = 0〜3である学生に反復します。そして私はこのバージョンではユーザにプロンプトを表示何学生のIDだ、と私は場合、getIntでそれを取得します。何が学生の名前だし、私はそれGetStringメソッドと取得。学生の家とは何ですか？私がGetStringメソッドとそれを得る。そして、ここで一番下に私はちょうど変更することを決めた私はこれらをプリントアウトしているし、実際にループを使用する方法、そして、私は誰を印刷しています？コメントによると、私は、マザーの誰を印刷していますそれはそれそうロブとトミーなど、実際にトミーのマザーでだ。トミーとデビッドは、この場合に印刷されるでしょうが、これはどのように機能しているか？私たちは前に、この関数を見ますが、これはどんなことをしている推測を取るていない。文字列を比較します。それが判明したので、それが文字列を比較する方法を少し非は明らかだそれは、文字列が等しいことを意味し、0を返します。それは、一方が他方よりもアルファベット順で前に来ることを意味し、-1を返した場合そしてそれは他の単語がアルファベット順に来る意味1を返した場合他の前に、あなたは、オンラインまたはmanページを見ることができます今やっているされているが、このすべてを正確に確認する方法と、それは言っている [i]とする。家は "マザー"に等しい場合その後、先に行くと云メイザーにあるプリントアウト。しかし、ここで我々は前に見たことがない何かである、と我々はこれに戻ってくる。私が今まで私のプログラムのいずれかでこれをしなければならないことは覚えていません。フリーは明らかに、メモリを解放し、メモリを参照しているしかし、私は明らかに、このプログラムの一番下に、このループで何メモリを解放していますか？私は人の名前を解放しているように見えますその人の家が、なぜそれがですか？それはあなたがGetStringメソッドを使用してきたことが、これらのすべての週判明私達は種類のあなたのプログラムの一つ一つにバグを導入してきました。それはあなたの文字列に戻すことができるように設計がメモリを割り当てることによってgetStringは、デビッド、またはロブ様、あなたはそれからあなたが好きなことを行うことができ私たちはあなたのためのメモリを確保してきたので、あなたのプログラム内でその文字列を持つ。問題は、GetStringメソッドを呼び出すたびにこのすべての時間です我々は、GetStringの著者は、オペレーティング·システムを求めてきた私たちは、この文字列のためのRAMのビットを得た。私たちは、この次の文字列のためのRAMのビットを与える。私たちは、この次の文字列のためのいくつかのより多くのRAMを与える。あなたは、プログラマは、何をやったことがない私たちにそのメモリバックを与えているあなたの書いたプログラムのため、これらの数週間のためのすべて彼らが使用し続けることにより、メモリの飛躍と呼ばれるものを持っていたより多くのメモリをあなたがGetStringメソッドを呼び出すと、それは大丈夫です毎回。それは面白いではありませんので、我々は意図的に最初の数週間でそれを行う文字列がどこから来ていることを心配する必要はあります。あなたが欲しいのは単語は、ユーザーの入力時に、それをインチ戻ってきてロブですしかし、前進して我々は今、このことについて、より洗練された取得を開始する必要があります。我々は我々がより良い最終的に戻ってそれを渡してメモリを割り当てることがいつでも。そうでなければ、時折経験しているかもしれないあなたのMacまたはPC上で現実の世界ではお使いのコンピュータは、最終的に停止して研削される症状または愚か紡績ビーチボールは、ちょうどコンピュータのを占めている全体の注意を、あなたが何かを行うことはできない。そのバグは、任意の数によって説明するが、それらのバグの可能性の間ですることができますそれによってそのソフトウェアを書いた誰かのものはメモリリークと呼ばれていますあなたは、メモリを解放するために覚えていませんでした使用している彼または彼女はのためにオペレーティング·システムを求めていること、それはCS50の事だから、GetStringメソッドを使用しますが、同様の機能を使用していないメモリ用のオペレーティングシステムに依頼すること。あなたまたは彼らは台無しにした場合、実際にそのメモリを返すことはありませんプログラムが遅くなり、遅くなり、遅くなるということであるかもしれませんの症状あなたは自由を呼び出すことを覚えていない限り。私たちは、いつ、なぜ、あなたがフリー呼ぶように戻るでしょうしかし、ここでは単に良い測定のために先に行くと、この特定のプログラムを実行してみましょう。これはstructs1と呼ばれていた、次のように入力します。デビッド·メイザー、私が先に行くとstructs1、123を実行してみましょう、 456、ロブカークランド、789 トミー·メイザー、私たちはマザー、マザーでトミーのでDavidのを参照してください。これは、プログラムが動作していることを、ほんの少しの健全性チェックです。さて、残念なことに、このプログラムは、以下の点で少しイライラさせられる私はすべての仕事は、私が9つの異なる文字列で入力し、ENTERキーを押してなかった、メイザーにあった人たちに語った、まだ明らかに私はそれを入力したために、すでにメイザーで誰か知っていたしました。このプログラムは、より多くのデータベースのようであれば、それは少なくともいいだろうそしてそれは実際に私がタイプしたものを覚えているので、私は再び入力これらの生徒の記録をする必要はありません。多分それはregistrarialシステムのようなものだ。我々は、ファイルI / O、ファイルの入出力として知られているこの技術を用いてこれを行うことができますあなたがファイルを読み取ったり、ファイルを作成したい任意の時間を言うのは非常に一般的な方法あなたは、関数の特定のセットでこれを行うことができます。私が先に行くと、この例のstructs2.cを開いてみましょう、これはほぼ同じですが、それが今では何をするか見てみましょう。ファイルの先頭に、私は学生のクラスを宣言します。私はその後、ユーザーの入力を持つクラスを移入これらのコード行を正確に前に似ているので。メイザーである誰もが勝手に以前のように私はここにスクロールダウンする場合、私は、印刷、しかし、これは興味深い新機能です。、これらのコード行は、新規であり、彼らはここで何かを紹介 FILE、すべて大文字、それもここに*を持っています。ここでも同様にオーバー*、私はここにこれを移動することができます。我々は前に見たことがないこの関数は、fopen、それは開いているファイルを意味しますので、これらを介してのは脱脂せ、これは、我々は将来のpsetにに戻ってくるものですしかしここでこの行は、本質的には、データベースと呼ばれるファイルを開きますそして、それは具体的にそれはそれに何をすることができるような方法でそれを開きますか？ [聞き取れない - 学生] 右ので、 "w"は、ちょうどそれがオペレーティングシステムを語っていることを意味私はそれに書き込むことができるような方法でこのファイルを開きます。私はそれを読みたくありません。私はちょうどそれを見たくありません。私は、それを変更し、それに潜在的なものを追加したいとファイルには、データベースと呼ばれようとしています。これは、何かを呼び出すことができます。これはdatabase.txtである可能性があります。これは可能性があります。デシベル。これはfooのような言葉かもしれないが、私は勝手にファイルデータベースに名前を付けることにしました。これは、我々は時間をかけて丹念にに戻ってくることはほとんど正気チェックです fpは、ファイルポインタの場合、NULLを等しくない場合、それはすべてが順調であることを意味します。手短には、fopenのような関数が失敗することがあります。たぶん、ファイルが存在しません。たぶんあなたは、ディスク容量が不足している。たぶん、あなたは、そのフォルダへのアクセス権がありません fopenがない場合はnullが返されますので、何か悪いことが起こった。 fopenはnullを返さない場合は逆に、すべてが順調ですそして私は、このファイルへの書き込みを開始することができます。ここでは、新しいトリックだ。これは、私の生徒のそれぞれの繰り返し処理を行うのはのためのループですこれは、我々は前にやったことに非常に似ているしかし、この関数は、printfのファイルにfprintf関数と呼ばれるprintfのいとこですそれが唯一の2つの方法で異なることに気づく。一つは、それは、代わりに電話のfで始まるしかし、その最初の引数は明らかに何ですか？ [学生]ファイル。>>それはファイルです。我々は最終的にファイルポインタが何であるかを離れていじめるよFPと呼ばれるこの事、、しかし、今のfpは単に、私が開いているファイルを表すそうfprintfをここにファイルにではなく、画面にこのユーザーのIDを表示と言っている。ファイルへのユーザの名前ではなく、画面に、印刷ファイルにではなく、明らかに、ここでダウンし、画面に、家ファイルを閉じてから、ダウンここでメモリを解放する。このバージョン2とバージョン1の唯一の違い fopenの導入と、*このファイルですとfprintfのこの概念は、その最終的な結果が何であるかを見てみましょう。私は私の端末ウィンドウに行こう。私はstructs2を実行してみましょう、次のように入力します。すべてが順調であるように見えます。 structs2を再実行してみましょう。 123、デビッド·メイザー、456、ロブカークランド、 789、トミー·メイザーは、次のように入力。それは同じように行儀のように見えますが、私は今、lsを行う場合すべての私のコードの中で、ここにあるものに気付くファイル、データベース、それでは、データベースと、geditを開いてみましょう、そしてそれを見て。それは、ファイルフォーマットの最もセクシーではありません。それは本当に、行ごとに行あたりのデータ行の1枚ですしかし、ExcelまたはCSVファイルを使用してあなたの人々の、コンマで区切られた値、私は確かに代わりに多分このような何かをするfprintfを使用することもできました私は実際にExcelファイルと同等のものを作成することができますようにコンマだけでなく、新しい行で物事を分離することによって。この場合において、私は代わりにコンマの代わりに新しい行を使用した場合私が代わりにそれはこのように見えた場合、私は文字通りExcelでこのデータベースファイルを開くことができます。要するに、今、我々はファイルへの書き込みをする力を持っていること我々は今、ディスク上でそれを周りに保ち、永続データを起動することができます我々は何度も何度も周りの情報を保持できるようにします。今ではもう少し慣れている他のいくつかの点に注意してください。このCファイルの先頭に、我々は、typedefを持っている我々はその言葉を表すデータ型を作成したかったので、このタイプはワードと呼ばれるように、内部にこの構造体のそれが今では少し手の込んだ。なぜ言葉は明らかに配列で構成されています？ただ直感的に言葉は何ですか？それは文字の配列です。これは、バックアップする背中合わせに一連の文字です。すべて大文字の文字は、私たちが勝手に言うことを起こる最大長我々はスクランブルのために使用している辞書に載っているような単語の。なぜ私は1を持っていますか？ヌル文字。我々は特別な値を必要としてBananagrams例をやったときを思い出してくださいを追跡するために、単語の末尾に言葉が実際に終了したところの、問題セット仕様が言うようにここでは、与えられた単語とブール値を関連付けるしているいわば、trueまたはfalseのフラグ。私たちは実現するためには、すでにこの言葉を発見した私たちは本当に言葉がスクランブルにあるものだけでなく、覚えるの方法が必要しかし、あなたかどうかにかかわらず、人間は、それを発見したあなたが見つけられた場合に、単語は ""あなただけ入力できないように、次のように入力し、入力し、入力します。と3点、3点、3点、3ポイントを取得します。我々はboolを設定することで、その単語をブラックリストに登録できるようにしたいあなたはすでにそれを見つけたなら、なぜtrueにし、その結果は私たちですこの構造体にカプセル化された。さて、ここでダウンしてスクランブルに入っている辞書と呼ばれるこの他の構造体があります。ここに欠席この場合のための単語typedefです私たちは、辞書のアイデアをカプセル化するために必要なと辞書には、単語の全体の束が含まれていますとしてこの配列によって暗示、そしてどのようにそれらの単語のいくつあるのですか？さて、この変数と呼ばれるサイズが何を言おう。しかし、我々は一つの辞書を必要としています。私たちは辞書と呼ばれるデータ型を必要としません。私達はちょうどそれらのいずれかを必要とするので、それはC言語で判明あなたはtypedefを言わないのであれば、あなただけのstructを言うことは、中カッコ内のあなたが名前を入れた後、あなたの変数を置く。これは、辞書と呼ばれる一つの変数を宣言しているそれはこのようになります。これとは対照的に、これらの行はワードと呼ばれる再利用可能なデータ構造を作成しているあなたは私たちが作成したのと同じように、複数のコピーを作成することができます学生の複数のコピー。これは、最終的に私たちは何ができるのでしょうか？、私はシンプルな時代から簡単な例、みましょうと言う、に戻ってみましょうとcompare1.c、としましょう、私は開くことができます。ここでの問題は、手元に戻って剥がしに実際にある文字列の層と、これらの補助輪を外して起動するそれは、文字列、すべてのこの時間を判明ので私たちは本当に週1でニックネームのみを約束した通りである、もう少し不可解に見える何かのためにCS50ライブラリからシノニム、 char *は、そして我々は前にこの星を見てきました。我々は、ファイルのコンテキストでそれを見た。我々はいくつかの時間が今のこの詳細を隠してきた理由を今見てみましょう。ここcompare1.cというファイルがあり、そしてそれは明らかに、2つの文字列、sとtをユーザーに要求そして、次に、それは、ライン26の平等のためにそれらの文字列を比較しようそれらが等しいなら、それは "あなたが同じことを入力した"と言う。そして、それらが等しくないなら、それは "あなたは別のものを入力した"と言う。私が先に行くと、このプログラムを実行してみましょう。私は私のソースディレクトリに移動してみましょう、compare1を作る。それは大丈夫コンパイル。私はcompare1を実行してみましょう。私は、にズームイン入力します。何かを言う。こんにちは。私は再び何かを言うでしょう。こんにちは。私は間違いなく別のものを入力されていません。私は再びこれを試してみましょう。バイバイ。間違いなく異なるので、ここで何が起こっているのですか？まあ、本当に26行目で比較されているのか？ [聞き取れない - 学生] はい、だからそれは、文字列、データ型は、白い嘘の一種であることが判明した。文字列はchar *ですが、char *型は何ですか？ char *は、彼らが言うように、ポインタであるポインタは、事実上のアドレスです合計メモリ内の場所、およびあなたはHELLOのようなワードで入力したために起こる場合、文字列の過去の議論を思い出してこれはHELLO言葉のようなものです。ハローのような単語が表現できることを覚えておいてくださいこのような文字の配列としてその後末尾には、特殊文字とヌル文字と呼ばれ、 \で囲まれている。実際には文字列とは何ですか？これはメモリの複数の塊であることに注意して、あなたが文字列全体に目を通した後、実際に、それの終わりにのみ知られている特別なNULL文字を探しています。しかし、これは私のコンピュータのメモリからメモリの塊である場合、任意に、この文字列は、単に幸運と言ってみましょうそしてそれは私のコンピュータのRAMの冒頭に置かれてしまった。これは、バイト0、1、2、3、4、5、6です... 私は、GetStringメソッドのようなものを言うと私は、文字列s = GetStringを行うと本当に何が返されるのですか？これらの過去数週間のために、何が本当にsに格納されているこの文字列は、それ自体ではありませんが、このケースに格納されているものです GetStringメソッドは、実際に何をするか理由番号0 それは物理的に文字列を返していないことです。それも本当に概念的な意味をなさない。それはリターンが数値である何。その数は、メモリ内のHELLOのアドレスです。と文字列sはその後、我々は戻って剥がし、この層は、文字列は実際に存在しない場合。それだけCS50ライブラリの簡素化です。これは実際にはchar *と呼ばれているものです。何がHELLOのような単語だからcharは理にかなっている？まあ、それは文字のシリーズは、一連の文字です。 char *は、文字のアドレスを意味しますだから何それが文字列を返すためにどういう意味ですか？文字列を返すの素敵な、簡単な方法というより、私が5または6の異なるバイトに戻す方法を把握しよう私はバイトのアドレスに戻りましょう？最初の1つ。言い換えれば、私はあなたに、メモリ内の文字のアドレスを与えることができます。つまり、char *は何を表しているか、メモリ内の1つの文字のアドレスです。その変数sを呼び出します。私が勝手に言った特定のアドレスは、0であることをsの店舗、物事をシンプルに保つことが、現実には、一般的に大きい数字です。ちょっと待ってください。あなたは私だけに最初の文字のアドレスを与えている場合、どのようにアドレスを知っていますか二番目の文字、第三、第四及び第五の？ [聞き取れない - 学生] 文字列の終わりは、この便利なトリックを介してどこにあるかだけ知っている、ので、あなたは、printf文字通りその引数として取るものprintfのようなものを、使用する場合、我々はこの％sプレースホルダを使用することを思い出して、その後、に渡す文字列を格納している変数。あなたが本当に渡していると、その文字列の最初の文字のアドレスです。 printfはその後、そのアドレスを受信したときにループまたはwhileループのために使用例えば、0、そう、私は今これをやらせるのprintf（ "％sを\ n"、S）; 私は実際にprintfを提供しているものを、私は、printf（ "％sは\ n"のS）を呼び出したときこの任意の場合にはHであるsの最初の文字のアドレスであり、どのようにprintfを画面に表示するかを正確に知るのでしょうか？実装者は、printfのforループ、whileループまたは実装この文字は特別なnull文字が等しくないことは言う？ていない場合は、それを印刷してください。どのようにこの1はどうですか？それを印刷していない場合は、それを印刷し、それを印刷し、それを印刷してください。ああ、この人は特別です。印刷を停止し、ユーザに戻ります。そして、それは、文字通りフードの下に起こっていることすべてだそれは、クラスの初日に消化するために多くのですしかし今のところ、それは本当にすべてのものを理解するのビルディングブロックです私たちのコンピュータのメモリの内側に起こっていること、そして最終的に、我々は少しの助けを借りて、これを離れていじめるよスタンフォード大学の我々の友人の一人から。スタンフォード大学教授ニックParlanteこの素晴らしいビデオシーケンスを行っている導入された異なる言語のすべての種類からこの小さなクレイ文字BINKY。あなただけの数秒のスニーク·プレビューで聞いている声についてスタンフォード大学教授のことであり、あなたが取得している今、この権利のわずか5〜6秒、しかし、これは我々が今日結論を出すでしょうしているノートですそして水曜日に始まる。私はあなたにBINKY、プレビュー付きのポインターの楽しみを与える。 [♪音楽♪] [教授Parlante]ねえ、BINKY。目を覚まして。これは、ポインタの楽しみのための時間です。 [BINKY]それは何ですか？ポインタについて学ぶのか？ああ、すごーい！私たちは、水曜日にお会いしましょう。 [CS50.TV]