[Powered by Google Translate] [第6項] [より快適] [ロブボーデン] [ハーバード大学] [これはCS50です。] [CS50.TV] ここでは、質問の私達のセクションに向かうことができる。私は前にスペースのURLを送った。質問のセクションの冒頭は言う - どうやら私は、非常に簡単な質問unsick-が完全に分からないのvalgrindされるだけで何の？ valgrindのは何をしますか？誰もvalgrindのが何を言いたい？ [学生]をチェックし、メモリリークします。うん、Valgrindは一般的なメモリチェッカーです。あなたは、任意のメモリリークがある場合、それは、最終的には、あなたを伝え、それはあなたがしたい場合、我々は理由のためにそれを使用しているものほとんどです問題セットで、またはあなたがしたい場合はうまくやる大きなボードに乗って、あなたは、全くメモリリークがないことが必要ケース内には、あなたが見つけることができないメモリリークが発生しているまた、ファイルを開くたびにことを覚えておいてくださいそしてあなたがそれを閉じない場合、それはメモリリークだ。多くの人々は、彼らが解放していないことをいくつかのノードを探していますときに本当に、彼らは非常に最初のステップで辞書を閉じていませんでした。あなたは、任意の読み込み無効であるか、または書き込みを持っている場合、それはまた、あなたに伝え、あなたがしようとする値を設定した場合は、これは意味そのヒープの末尾を超えてだとそれがseg faultを発生しませんしかし、Valgrindは、あなたが実際にそこに書くべきではありませんので、それをキャッチので、あなたは間違いなくどちらかのもののいずれかを持つべきではありません。どのようにvalgrindのを使うのですか？どのようにvalgrindのを使うのですか？これは、一般的な質問ですの種類は、それを実行して出力を見てみましょう。出力には、多くの時間を圧倒しています。あなたには、いくつかのひどく間違ったことがあれば楽しいのエラーもありますループの中で何が起き、それが最終的には、あまりにも多くのエラーが発生する "、と言うだろう。私は今、カウントを停止するつもりです。 " それはあなたが解析しなければならないことを基本的にはテキスト出力です。最後に、それはあなたが持っている任意のメモリリークを教えてくれる、どのように多くの点で有用であることができるブロック、それは一つのブロック未解放の場合、それは見つけるために通常はより簡単です 1,000以上のブロックは未解放。 1000ブロックは、おそらくあなたが解放していないことを意味未解放適切か何かあなたのリンクリスト。それはvalgrindのです。今、私たちは、質問の私達のセクションを持っているどちらをダウンロードする必要はありません。あなたは私の名前をクリックし、スペースでそれらをプルアップすることができます。今の私をクリックしてください。リビジョン1は我々が最初にやっているスタックになります。リビジョン2には、キューとなり、リビジョン3は、片方向リンクリストになります。私たちのスタックから開始する。それはここで言っているように、スタックは、最も基本的なの一つですコンピュータ科学の基本的なデータ構造。非常に典型的な例ですダイニングホールにあるトレーのスタック。あなたがスタックに導入されているときはいつでも、それは、基本的にはだ誰かが言おうとしている "トレーのスタックのように、ああ。" あなたは、トレイを積み重ねる。その後、トレイを引っ張って行くとき、引っ張らなってきた最初のトレイは、スタック上に置かれた最後のものである。それが言うにも似たここにデュアルスタック我々は、スタックと呼ばれるメモリのセグメントを持っています。そして、なぜそれがスタックと呼ばれる？なぜなら、スタックデータ構造のような、それは、スタック上にスタックフレームをプッシュし、ポップ関数の特定の呼び出しのようにどこにスタックフレームです。と、スタックのように、いつでも返却する必要があります関数呼び出しから、再度下部のスタックフレームにダウンして得ることができる前に。あなたは、メインCALL FOOコールバーとバーメイン直接リターンを持つことができません。それは常に正しいスタックプッシュとポップに従うことを持っている。 2つの操作は、私が言ったように、pushとpopされています。それらは普遍的な用語です。あなたは、スタックが何でという点でpushとpopを知っている必要があります。我々は、キューが異なるの一種であるが表示されます。それは本当に普遍的な言葉を持っていませんが、pushとpopはスタックの普遍的なものである。プッシュは単にスタックに置かれる。ポップはスタックを脱いだ。そして、我々は、我々は我々のtypedef structのスタックを持ってこちらをご覧くださいので、我々はchar **文字列を持っている。任意の**がびっくりしないでください。これは文字列の配列になってしまうために起こっている文字へのポインタの配列や、どこ文字へのポインタが文字列になる傾向があります。それは、文字列である必要はありませんが、ここでは、それらは文字列であることを行っている。私たちは、文字列の配列を持っている。我々は、スタック上に現在どのように多くの要素を表す大きさを、持っているそれから私達はスタック上にどのように多くの要素であることができるである能力を持っています。容量は、1より大きいものとしてオフを開始する必要がありしかし、サイズは0としてスタートする予定です。今、あなたがスタックと考えることができ、3つの異なる方法が基本的にあります。まあ、おそらくよりますが、2つの主要な方法があります。あなたは配列を使用して、それを実装したり、リンクされたリストを使用して実装できます。リンクされたリストからスタックを作るために些細なの一種です。これは、リンクされたリストを使用してスタックを作ることは非常に簡単ですので、ここで私たちは、配列を使用してスタックをするつもりだ、その後配列を使用して、あなたがそれについて考えることができる2つの方法も用意されている。前に、私が言ったとき、我々は、スタックの容量を持っているので、我々は、スタック上に要素を収めることができます。それが起こりうる一つの方法は、できるだけ早くあなたが10個の要素を打つようにして、設定が完了しています。あなたは世界の10の事柄の上限があることを知っているかもしれませんあなたは、あなたのスタックに10以上のものを持っていることは決してないだろうことをその場合には、スタックのサイズに上限を持つことができます。またはあなたは、あなたのスタックが際限のないことかもしれないアレイをやっているけど、それは、一つ一つの時間はあなたが10個の要素をヒットすることを意味しますその後、20個の要素に成長する必要があるとしている、あなたは20個の要素をヒットしたとき、あなたは30の要素または40個の要素に配列を成長させる必要があるとしている。あなたは、私たちがここでやろうとしているな容量を増加する必要があるとしている。我々は、我々のスタックの最大サイズに達する毎回我々は他の何かを押したときに、我々は、容量を増やすことが必要になるだろう。ここでは、プッシュプッシュブール型（char * str）とのように宣言しました。のchar * strは、我々がスタックにプッシュされていることを文字列であるとboolはちょうど私達が成功したか失敗したかと言います。どのように我々は失敗することができますか？あなたが考えることができる唯一の状況は何ですかここで我々は、falseを返す必要があるのでしょうか。うん。 [学生]がいっぱいだと我々は境界の実装を使用している場合。ええ、そうどのように我々が定義する、と彼は答えないそれが完全だと我々は有界実装を使用している場合。その後、我々は間違いなくfalseを返します。とすぐに我々は配列に10の事柄を打つように、我々は11を収めることができないので、我々はfalseを返します。それがバインドされていない場合はどうなりますか？うん。あなたには、いくつかの理由のためのアレイを拡張することができない場合。ええ、そうメモリは、限られたリソースであるそして最終的に、我々は何度もスタックにプッシュすることを続ければ、我々は、フィットするように大きい配列を試してみて、割り当てるつもりだ我々が使っている大容量、およびmallocまたは何でもfalseを返すために起こっている。まあ、malloc関数はnullを返します。、あなたがこれまでにmalloc関数を呼び出すごとに1つの時間を覚えて、あなたはそれかどうかをチェックすべきである nullを返すか、または他のそれが正しさの控除です。我々は、無制限のスタックを持つようにしたいので、我々がしようとした場合、我々はfalseを返すことになるだろう唯一のケースです容量とmallocを増やすか、falseを返します何でも。その後ポップは、引数を取らないそして、それはスタックの一番上の文字列を返します。全てのものが、最近スタックにプッシュされましたが、戻っている何ポップですそしてそれはまた、スタックから削除されます。およびスタック上の何もない場合にはnullを返していることがわかります。これは、スタックが空であることが常に可能である。 Javaでは、あなたがその、あるいは他の言語に慣れている場合、空のスタックからポップしようとすると、例外か何かを引き起こすかもしれません。しかし、C言語では、nullは、我々はこれらの問題をどのように処理するかは多くのケースのようなものです。 nullを返すことは、我々は、スタックが空であったことを意味しようとしている方法です。我々は、あなたのスタックの機能をテストするためのコードを提供してきました pushとpopを実装します。これは、多くのコードではありません。私は意志 - 実際に、我々はそれを行う前に、ヒント、ヒント - あなたがそれを見ていない場合は、malloc関数は唯一の機能ではありませんそれはあなたのためのヒープ上のメモリを割り当てます。アロケーションファミリの関数があります。第一は、これまで使ってmalloc関数です。その後、malloc関数と同じことをしcallocは、そこしかし、それはあなたのためにすべてをゼロにします。あなたは今まで何かをmallocing後にnullにすべてのものを設定したいと思っていた場合あなただけの代わりに書いて最初の場所にあるcallocを使用している必要がありますメモリの全ブロックを0にしてforループ。 reallocは、malloc関数のようなもので、特殊な例をたくさん持っているしかし、基本的には何のreallocでないそれがすでに割り当てられているポインタを受け取ります。 reallocはここに注目したい関数です。それは、すでにmalloc関数から返されたポインタを受け取ります。 Let 'sは、あなたは、mallocから10バイトのポインタを要求すると言う。その後、あなたが20バイトを望んで実現する、ので、20バイトで、そのポインタでreallocを呼び出すとreallocは自動的にあなたのためにすべてをコピーします。私は10バイトのブロックを持っているように、あなただけは、もう一度、malloc（）を呼び出された場合。今私は、20バイトのブロックを必要とする、ので、私がmalloc 20バイトあれば、私は手動で最初のものから10バイトを上書きコピーする必要がありますまず二つ目に、その後フリー。 reallocはあなたのためにそれを処理します。署名は、void *であることを行っていることに気づくそれはちょうど、メモリブロックへのポインタを返している次にボイド* ptrは。あなたは、汎用ポインタとしてvoid *型と考えることができます。一般的には、void *型を扱うことはありませんしかし、mallocはvoid *を返すされており、それは同じように使われているこれは実際にはchar *であることを行っている。 mallocで返されていた以前のvoid * 今のreallocに渡されようとして、次にサイズです割り当てたいバイトの新しい番号なので、あなたの新たな容量です。私はあなたに数分を与え、私たちの空間でそれをやる。リビジョン1から始まります。私は、プッシュを実装するのに十分な時間後に約願わくはあなたを停止しますそして私はあなたにポップアップを行うには別の休憩を与えるでしょう。しかし、それは本当にすべてではそれほどコードではありません。ほとんどのコードは、容量を拡大し、おそらく拡大されるものです。さて、完全に実行するための圧力がない、しかし限り、あなたは正しい道にいるように感じるように、それは良いことだ。誰もが、彼らが私を引き上げ、快適に感じて任意のコードを持っていますか？ええ、私はしますが、誰も私がアップすることができ、任意のコードを持っているのですか？さて、あなたはそれが何であれ、それを保存し、起動することができますか？私はいつも、そのステップを忘れてしまった。さて、プッシュを見て、あなたのコードを説明したいのですか？ [学生]は、まず第一に、私はサイズを増加させた。私は多分私はその、とにかく持っている必要がありますね、私は、サイズを増加それが容量より小さい場合だと、私は参照してください。それが容量より小さい場合だと、私は我々がすでに持っている配列に追加します。それがないならば、私は、2で容量を掛けと私は今、より大きな容量の大きさで何かに文字列の配列を再割り当てする。それが失敗した場合、その後、私はユーザーに伝えると、falseを返すそれは大丈夫ですなら、私は新しい場所に文字列を置く。 [ロブB.]我々はここでは素敵なビット単位の演算子を使用していることも注意してください 2を掛けます。覚えておいて、左シフトは常に2を乗じれようとしている。あなたはそれが意味することを覚えているように、右シフトであれば2分周され 2で割った整数のように、2で割る。それはここまたはそこに1を切り捨てる可能性があります。しかし1だけ左シフトは常に2を乗じれようとしている、あなたは整数オーバーフローの境界をしない限り、そして、次に、それはできません。側のコメント。私は全くコーディングどのような方法を変更するつもりはない、これは、やりたい、しかし私はこのような何かをしたい。それは実際にそれが若干長く作るつもりです。多分これは、このことを示すのに最適なケースではありませんしかし私は、これらのブロックの中にセグメントにそれを好むこの事態が発生した場合場合、大丈夫、私は何かをするつもりだ、してから、関数が実行されます。私はその後、ダウン機能ずっと私の目をスクロールする必要はありません他の後に何が起こるか確認してください。この問題が発生した場合した場合それは、その後、私はちょうど返す。また、この以降はすべての素敵な付加的な利点を持っている今一度、左にシフトされます。あなたがこれまでに途方もなく長い行の近くにいる場合には、私はもはや、必要はありません、それらの4バイトは助けることができ、また、より左のものです少ないような - 大丈夫、私が覚えていたら、気が遠くなる私は、forループのelseの内側の内側のwhileループで、現在です。どこでもあなたは私の種類のような、すぐにこのリターンを行うことができます。それは完全にオプションだし、どのような方法では想定されません。 [学生]はそこサイズである必要があります - 障害状態に？ここで失敗する条件は、我々はそうはい、reallocのに失敗しています。、おそらく、障害状態でどのように注意してください私たちは無料のもの後、我々は常に失敗にしたいのでない限り私たちは何かをプッシュしようと何回でもありません。私達はプッシュし続けるなら、私たちは、インクリメントサイズを維持我々は、スタック上に何かを入れていない場合でも。通常、我々まで、サイズを増加させません我々は正常にスタックの上に置いた後。我々はこことここのどちらか、と言う、それを行うだろう。代わり≤容量をs.size言うのそして、それは、容量よりも小さいですすべてのものがどこにあったかという理由だけで、我々は移動しました。そして、我々はおそらくfalseを返すことができること、唯一の場所を覚えている reallocはnullを返して、ここにあるそしてあなたは、標準エラーを覚えてしまった場合、あなたが標準エラーを出力したい場所多分あなたは、このようなケースを検討するかもしれないだけではなく、標準出力に直接印刷のようにfprintfを標準エラー出力（stderr）。繰り返しになりますが、、それは期待しないが、それは誤りだ場合 printf関数の型、あなたはそれが標準エラー出力の代わりに標準出力に出力しておくことをお勧めします。誰もが注意すべき何かを持っている？はい。 [学生]あなたは[聞こえない]の上に行くことはできますか？ [ロブB.]はい、実際のそれのbinarinessまたはちょうどそれが何であるか？ [学生]だからあなたは2を掛けて？ [ロブB.]うん、基本的に。バイナリ土地では、我々は常に我々の数字のセットを持っています。右側でここは基本的にそれを挿入することで、この1を左シフトする。これに戻る、単なるバイナリでそのすべてを覚えている、2の累乗であるので、これは0から2を表す 1〜2本、この2へ。今右側に0を挿入することによって、我々は、ちょうどすべてを上にシフトします。何が0から2にするために使用すると、今では1〜2で、2から2です。我々は挿入右側必ずしも0になるだろうこれは理にかなっています。あなたがこれまでに2で番号を掛けると、それは、奇数終わることはないだろうので0の場所に2が0でなければなりませんあなたがシフトしてしまったんなら、これは私が半分になる前に何かを警告整数のビット数を超えて、次に、この1はオフに行くことに終わろうとしている。あなたが本当に大容量を扱うことが起こるなら、それは唯一の悩みだ。しかし、その時点で、あなたは、物事の数十億の配列を扱っているとにかくメモリに収まらないかもしれない。今、私たちはさらに簡単ですポップ、取得することができます。あなたは全体の束をポップしてしまった場合は、それが好きなのでした今、あなたは再び半分の容量にいる。あなたは、あなたが持っているメモリの量を縮小することができREALLOC しかし、あなたはそのことについて心配する必要はありませんので、唯一のreallocのケースがあることを行っている成長しているメモリは、メモリを縮小することはありません、これはポップのスーパーを容易にしようとしている。スタックのようになるだろうしている今のキュー、しかし、あなたが物事を取り出した順序が逆になっています。キューの典型例は、ラインですあなたは英語であった場合、私が推測するに、私は言ったでしょうキューの典型例では、キューです。だから線のように、行の最初の人なら、あなたはラインの内、最初の人になることを期待しています。あなたが行の最後の人なら、あなたは修理最後の一人になるだろうしている。スタックはLIFOのパターンだったのに対し、我々は、そのFIFOのパターンを呼び出します。それらの言葉は、かなり普遍的なものである。スタックと同様と配列とは異なり、キューは通常、中間の要素へのアクセスを許可していません。ここでは、スタックは、我々は、pushとpopを持っています。ここでは、それらのエンキューおよびデキューの求めているために起こる。私はまた、彼らはshiftとunshiftを呼ばれるのを聞いた。私は人々がpushとpopキューにも適用すると言う聞いたことがある。私は、削除、挿入、聞いたことがあるあなたがスタックの話をしている場合そうpushとpop、あなたはプッシュとポップされています。あなたがキューの話をしている場合は、使用する語句を選ぶことができ挿入および除去のために、それが呼ばれるべきかについてのコンセンサスはありません。しかし、ここで、我々はエンキューとデキューを持っています。今、構造体はスタック構造体とほぼ同じに見えます。しかし、我々は頭を追跡する必要があります。私はそれがダウンしてここに言うと思いますが、なぜ私たちは頭が必要なのでしょうか？プロトタイプは、pushとpop、基本的に同じです。あなたは、pushとpopと考えることができます。ポップで唯一の違いは、返す代わりに、されている最後のではなく、最初に戻っている。 2、1、3、4、または何か。そして、ここではスタートです。私達のキューが完全にいっぱいになるので、それには4つの要素があります。私達のキューの最後には、現在2であるそして今我々は何か他のものを挿入する行く。私たちは誰か他の何かを挿入したい場合は、スタックのバージョンのために何をした私たちは私たちの記憶のブロックを拡張されています。この場合の問題は何ですか？ [学生]あなたは2点を移動します。私はキューの終わりについての前に言ったことを、これは、我々は1から始まっていることには意味がありませんその後、我々はその後、デキュー3、デキュー4、デキュー1にしたいデキュー2であれば、このいずれかをデキューします。我々は今、reallocを使用することはできません、または非常に少なくとも、あなたは別の方法でreallocを使用する必要があります。しかし、あなたはおそらくちょうどreallocを使うべきではありません。あなたのメモリを手動でコピーする必要があるとしている。メモリをコピーするには、2つの関数があります。 memcopyとmemmove関数があります。私は現在あなたが使用するつもりだどれ見てmanページを読んでいます。さて、memcopy、違いがある memcopyとmemmove関数、1は正しく事件を処理することあなたは、この地域に重なるように起こる領域にコピーしている場所あなたからコピーしている。 Memcopyはそれを処理しません。 memmove関数はありません。あなたは、問題を考えることができますみましょう、私はこの男をコピーしたいと言うこの男の上に、これらの4つ。結局、何の配列は次のようになります。コピーはその後、2、1、2、1、3、4、最後にいくつかのものになった後。しかし、これは、我々が実際にコピーされる順序に依存しています我々は、我々は地域にコピーしているという事実を考慮していない場合導入重なっている我々からコピーしている1、次に我々は、ここから始めて、私たちが行きたい場所に2をコピーするようにするかもしれないその後、前方に私達のポインターを移動します。今、私たちは、こことここにあることを行っている、そして今我々は、コピーしたいこのこの男以上の男とは、我々のポインタを移動します。我々が得ることを終えるつもりだと、2、1、2、1、2、1である代わりに適切な2、1、2、1、3、4の理由 2、1、元の3,4を覆した。 memmove関数は正しくそれを処理します。この場合、基本的には常にmemmove関数を使用それはそれを正しく処理しないため。これは、一般的に任意の悪化を実行しません。アイデアは最初から開始し、この方法でコピーするのではなく、ある私達はちょうどここにやったように、それは、終わりから始まり、でコピーその場合には、問題を持っていることはありません。何のパフォーマンスが失われることはありません。常にmemmove関数を使用します。 memcopy心配はありません。あなたが別々にmemmove関数する必要があるとしている場所、それはだあなたのキューのラップアラウンド部分。心配しないで完全に行われていない場合。これは、スタック、プッシュ、およびポップよりも困難である。誰もが私たちが働くことができる、任意のコードをお持ちですか？でも、完全に不完全な場合？ [学生]ええ、それはしかし、完全に不完全です。我々は、することができますあなたがリビジョンを保存すると、完全に不完全な限り、罰金ですか？私は毎回忘れる。さて、我々は物事のサイズを変更する必要があるときに何が起こるか無視。完全にサイズ変更を無視します。このコードを説明する。サイズはすべての最初のコピー未満である場合、私はまず第一にチェックしているし、その後、私は、頭+サイズを取る私は挿入しと私はそれは、アレイの容量を包み込むことを確認してくださいと私は、その位置に新しい文字列を挿入します。それから私は、サイズを大きくして、trueを返します。 [ロブB.]これは間違いなくあなたはMODを使用したいとしているような事例の1つです。あなたの周りの折り返しと思われる場合は、ラップアラウンドした例あらゆる種類の、即時の思考はmodにする必要があります。迅速な最適化/あなたのコード1行を短くする、などあなたは、その行が直ちにこれを次のことに注意してくださいジャストサイズです+ +ので、あなたは、このラインにマージされ、大きさ+ +。ダウンここに今、私たちはケースを持っている我々は十分なメモリがない場合には、ので、我々は2によって我々の能力を高めています。、私はあなたがここに同じ問題を抱えていることができると思いますが、我々は今それを無視することができますあなたの能力を高めるために失敗した場所ならば、その後、再び2であなたの能力を減少させるためにするつもりだ。別の短いノートはあなたがすることができるだけのようです+ = あなたはまた、<< =を行うことができます。等しい前に行くことができますほとんど何も、+ =、| =、＆=、<< =。 char *の新しいメモリの私達の新しいブロックです。ああ、こっちに。人々はメモリの私達の新しいブロックの型についてどう思いますか？ [学生]それはchar **であるべきである。ここまで我々の構造体に戻って考えると、文字列は、我々は再配分しているものである。我々は、キュー内の要素のための全体の新しい動的なストレージを作っている。私たちはあなたの文字列に代入することになるだろうと、申し訳mallocingているものですますので、新たにはchar **になるだろう。これは、文字列の配列になるだろう。その後、我々は、falseを返すようになるだろうその下のケースは何ですか？ [学生]は、我々はchar *をやるべき？ [ロブB.]はい、良いコール。 [学生]あれは何だ？ [ロブB.]我々は、もはや、いないので、我々は、char *のサイズをやってみたかったはsizeof（char型）が1になるので、これは実際には非常に大きな問題であろう。 sizeof演算のchar * 4であることを行っている、ので、int型を扱っている多くの時間、あなたはintとint *のサイズのためサイズ離れてそれを取得する傾向がある 32ビットシステムでも同じことになるだろうしている。しかし、ここでは、sizeof（char）をsizeofは（char *）は今、同じことになるだろうしている。我々はfalseを返すような状況は何ですか？ [学生]新規はnullになります。新しいがnullの場合、ええ、我々は、falseを返すと私はスローダウンするつもりヒア [学生] [聞こえない] [ロブB.]うん、これは結構です。いずれか2倍の容量、または容量シフト1を実行してからここだけか何かそれを下に設定することができます。我々はそれを持っていたとして、我々はそれをやる。能力>> = 1。そして、あなたは1の地位を失うことを心配する必要がありますするつもりはありませんしているあなたは1だけ左シフトするので、とても1の場所は、必ずしも0であるそう1だけ右シフト、あなたはまだ細かいことになるだろう。 [学生]はリターンの前にそれを行う必要がありますか？ [ロブB.]はい、これは全く意味がありません。さて、最後にtrueを返す羽目になるだろうと仮定します。我々はこれらのmemmovesをやろうとしている方法、我々はそれらを行う方法に注意する必要があります。誰も我々はそれを行う方法についてどんな提案を持っていますか？ここに我々のスタートだ。必然的に、我々は再び先頭から開始したいそこから内とコピーもの、1、3、4、2。どのようにすればよいでしょうか？まず、私は再びmemmove関数のmanページを見ている。 memmove関数は、引数の順序は常に重要です。私達は私達の目的地は、まずソース第二、第三の大きさが欲しい。ソースとデスティネーションを反転機能がたくさんあります。宛先、送信元は、やや一貫性になる傾向がある。それが何を返して、移動しますか？それはあなたがすることを望むかもしれませんどのような理由であれ、目的地へのポインタを返します。私はそれを読むことができる絵が、我々は我々の目的地に移動したい。私たちの目的地は何をされようとしている？ [学生]新。 [ロブB.]はい、我々はどこからコピーされますか？我々がコピーしている最初のものは、この1、図3、図4である。 - この1、3、4とは何ですか。この1のアドレスは何ですか？その1のアドレスは何ですか？ [学生] [聞こえない] [ロブB.]ヘッド+最初の要素のアドレス。どのように我々は配列の最初の要素を取得するのですか？ [学生]キュー。 [ロブB.]はい、q.strings。覚えておいて、ここに、私たちの頭は、1です。それをかがる。私はちょうどそれは魔法のようだと思う - ここでは、私たちの頭は、1です。私はあまりにも私の色を変更するつもりです。そして、ここに文字列です。私たちはこっちに行ったようにこれは、我々はどちらかそれを書くことができますと頭+ q.strings。多くの人々はまた、それを書いて、＆q.strings [頭]。これは本当に任意の少ない効率的ではありません。あなたは、あなたがそれをデリファレンスした後のアドレスを取得していると考えるかもしれませんしかし、コンパイラは、我々はとにかく、q.strings +ヘッドの前に持っていたものにそれを翻訳しようとしている。あなたはそれを考えたくいずれかの方法。そして、どのように多くのバイトたちがコピーしたいのですか？ [学生]容量 - 頭。容量 - 頭。そしてあなたはいつも例を書き出すことが可能そうですかどうかを把握する。 [学生]それはその後、2で割ったする必要があります。うん、だから私たちはサイズを使用できると思います。我々はまだ大きさを持っている - サイズを使用して、我々は4に等しい大きさを有する。私たちのサイズは4です。私たちの頭は、1です。我々は、これらの3つの要素をコピーしたい。その正気は、そのサイズをチェックしている - 頭は正常に3です。我々は前に言ったように、ここに戻ってくる我々が能力を使用した場合は、次に我々は2で割る必要があるだろう我々はすでに我々の能力を成長させてきたので、その代わりに、我々はサイズを使用するつもりです。そのコピーした部分。今、私たちは、他の部分は、開始の残っている部分をコピーする必要があります。それはどのような位置にmemmove関数になるだろう？ [学生]プラスサイズ - 頭。はい、私たちは既にサイズでコピーした - 頭バイトを、それで我々は残りのバイトをコピーすることは新しいですその後サイズがマイナスでなく、バイト数は、我々はすでにインチコピーしたそして、私たちはどこからコピーされますか？ [学生] Q.strings [0]。 [ロブB.]はい、q.strings。我々は、いずれか＆q.strings [0]を行うことができます。これは、これより大幅に少ないのが一般的です。それがちょうど0になるだろう場合は、q.stringsを見る傾向があるでしょう。我々はコピー元の場所です。我々は、コピーする方法を多くのバイトを残しているのですか？>> [学生] 10。右。 [学生]我々は5を掛けなければなりませんか - バイトか何かの10倍？うん、これはどこに - まさに我々がコピーしているのですか？ [学生] [聞こえない] 我々がコピーしているものの種類は何ですか？ [学生] [聞こえない] それらがどこから来ているうん、char *で、我々がコピーしているように、我々は知らない。まあ、それが指している場所に、文字列のように、我々は、キューにプッシュ終わるまたはキューにエンキューする。それらがどこから来ている、私たちにはわかりません。我々だけではchar * sの自分自身を追跡する必要があります。ヘッドバイト - 我々は、サイズをコピーしたくない。頭のchar * sを - 私たちは、サイズをコピーしたいので、我々は、sizeof（char型の*）で、これを掛けるつもりです。同じダウンここで、ヘッド* sizeof（char *）は。 [学生]何について[聞こえない]？ここでこの権利は？頭 - いや、大きさ、その下の[生徒]。 [ロブB.]ここにこの権利は？ポインタ演算。どのようにポインタ演算は、仕事に行くのですそれは自動的に我々が扱っている型のサイズで乗算します。ただ、こっちのような新しい+（サイズ - ヘッド）＆新しい[ - 頭サイズ]とまったく同じです我々は、正しく動作することを期待されるまで、我々はint配列を扱っている場合ので、次に我々は、int-によってインデックスしないに、またはそれが5の大きさだし、第四の要素が必要な場合は、我々は、インデックス int型の配列[4]。あなたドント·[4] int型のサイズ*。つまり、それを自動的に処理し、この場合文字通り同等なので、ブラケット構文ただできるだけ早くあなたがコンパイルしたときにこれに変換されようとしている。それはあなたがそのように注意する必要があることですあなたのサイズを追加している - 頭あなたは、1バイトではありませんが追加されています。あなたは、1バイトまたは任意に指定することが可能です1 char *を、追加している。その他の質問は？さて、デキューが容易になるだろう。私はあなたに実装するための分を与えるでしょう。ああ、私は、これは同じような状況だと思いますどこに何エンキュー場合、我々は、nullをエンキューしている場合、多分私達はそれを処理したい場合は、おそらく我々にはありません。我々はここで再びそれを行うが、我々のスタックケースと同じではありません。私たちがヌルをエンキューした場合、我々はそれを無視したい場合があります。誰も私がアップすることができますいくつかのコードをお持ちですか？ [学生]私はちょうどデキューを持っています。バージョン2は、可もなく不可もなくです。あなたが説明したいと思います？ [学生]はまず、キューに何かがあることを確認してくださいとサイズが1ずつ下がっていることを確認します。あなたはそれを行う必要があり、その後、頭を返すその後1ヘッドアップを移動します。わかりましたので、我々が考慮しなければならないコーナーケースがあります。うん。 [生徒]、あなたの頭は、最後の要素である場合その後は頭が配列の外を指すようにしたくない。ええ、そうとすぐヘッドとしては、我々の配列の最後に行き着く我々はデキュー時、私たちの頭は0に戻ってモッドされるべきである。残念なことに、我々は1つのステップでそれを行うことはできません。私はおそらくそれが解決すると思い方法を推測するこれは、我々は戻っているのか、char *であることを行っている何でもあなたの変数名にはなりたがっている。その後、我々は我々の能力で頭をmodにしたいその後retに返します。ここで、彼らは可能性があります多くの人がdo- この場合はヘッドの人が何を参照してください - you'llのケースです容量 - 容量よりも大きい場合には、頭部を行う。そして、それは単にMODが何であるかを周りに取り組んでいる。ヘッドMOD =容量ははるかにきれいです容量 - 容量の頭よりも大きい場合に比べて頭の周りにラッピング。質問はありますか？さて、私たちが残っている最後のことは、私たちのリンクリストです。あなたがした場合は、リンクされたリストの動作の一部に使用されるかもしれないあなたはハッシュテーブルをしなかった場合、あなたのハッシュテーブル内のリストをリンクしました。私は強く、ハッシュテーブルを行うことをお勧め。あなたは既にトライを行っている可能性があり、しかし、トライは、より難しいものになります。理論的には、彼らは、漸近的に優れている。しかし、ちょうど、大きなボードを見れとうまくやることはありませんしようとし、彼らはより多くのメモリを取る。試みについてのすべては、より多くの仕事のために悪くなってしまう。それはデビッドマランのソリューションは常にあるものだ彼は常に彼のポストトライソリューションであり、彼は現在の場所を確認してみましょう。デビッド·J、彼の下には何でしたか？彼は第18位ですが、、それはひどく悪くはありませんので、そしてそれはあなたが考えることができる最高の試行の一つになるだろうトライの最高の試みの一つであるかを判断する。それも彼の元の解決策ではありません？トライソリューションはRAMの使用量がこの範囲でより多くなる傾向があるような気がします。一番上に行けば、RAMの使用率が一桁台になっています。底部に向かって行けば、その後は見て起動しようとしあなたが絶対に大規模なRAMの使用状況を取得する場所、とトライは、より難しいものになります。あなたは1をやっていない、完全にそれが、教育経験の価値があれば。最後のものは、私たちのリンクリストですそして、これらの3つの事、スタック、キュー、連結リスト、あなたがこれまでにコンピュータ·サイエンスで行う任意の将来の事あなたがこれらの事に精通していると仮定します。彼らはすべてにちょうどそう基本です。リンクされたリストが、ここではシングルリンクリストを持っているが、我々の実装であることを行っている。単独で何がリンクされないように二重にリンクされたとは対照的にどういう意味ですか？はい。 [学生]それだけで、次のポインタではなくポインタをポイントするそれとその後ろの1に先行するもののような。ええ、そう画像形式で、私はちょうど何をしましたか？私は二つのものを持っている。私は絵や写真を持っています。画像形式では、私たちの単一リンクリスト、必然的に、私達は私達のリストの先頭へのポインタのいくつかの種類があるその後私たちのリストの中で、我々だけで、ポインタを持っていそして多分この点はnullになります。それは、片方向リンクリストのあなたの典型的な描画になるだろう。二重連結リストには、後方に行くことができます。私はあなたに、リスト内の任意のノードを与える場合は、必然的にするために得ることができるリスト内の他のノードには、双方向リンクリストである場合。しかし、私はあなたのリストの3番目のノードを取得し、それは、片方向リンクリストの場合には、あなたがこれまでに第1および第2のノードに得ようとしている。方法はありませんと利点と不利益、一つ明らかなものはありあなたがより多くのサイズを取るです、あなたはこれらの事が今指している場所を追跡する必要があります。しかし、我々は唯一の単一リンクを気遣う。私たちが実装する必要があるとしているいくつかのこと。あなたのtypedef structのノードは、int I：構造体のノード*次回、ノード。そのtypedefはあなたの心に焼き付けなければならない。クイズ1は、リンクリストノードのtypedefを与えるようにすべきであると、すぐにその走り書きすることができるはずですそれについて何も考えずに。私はいくつかの質問を推測、なぜ我々はここで構造体が必要なのですか？なぜ我々はノード*を言うことができないのですか？ [学生] [聞こえない] うん。ものとしてのノードを定義する唯一のもの自体typedefです。しかし、この点のように、我々は、この構造体のノード定義を介して解析の一種でいるときに、我々は、typedefが完了していないのでので、まだ私たちのtypedefを完了していないノードが存在しません。しかし、構造体ノードはありませんし、ここでこのノード、これも何かを呼び出すことができます。これは、nと呼ばれるかもしれない。これは、リンクされたリストのノードと呼ばれることもあります。それは何かを呼び出すことができます。しかし、この構造体のノードは、この構造体のノードと同じものを呼び出す必要があります。あなたは、これがまたここに持って呼んでいるもの、となるように、質問の2つ目のポイントに答えるなぜ、あなたは、構造体と構造体のtypedefを参照してください多くの時間、それはあるあなたはあなただけのtypedef structをわかり無名の構造体を参照してくださいよ、構造体、ディクショナリ、または任意の実装。なぜここでは、ノードを言う必要があるのですか？なぜそれが匿名の構造体でなければできないのですか？これは、ほぼ同じ答えだ。 [学生]あなたは構造体の中にそれを参照する必要があります。うん、構造体の中には、構造体自体を参照する必要があります。あなたは構造体に名前を与えていない場合は、匿名構造体の場合は、、あなたはそれを参照することはできません。と最後のではなく、少なくとも、これらはすべて、幾分簡単であるべきですあなたがこれをダウンして書いている場合、彼らはあなたが実現することを助けるべきこのようなことは意味をなさない場合は、何か間違ったことをやっている。最後になりましたが、なぜこれが*構造体ノードである必要はありますか？なぜそれだけで次のノードを構造体でなければできないのですか？ [学生]次の構造体へのポインタ。それは我々が望むものを必然的だ。なぜそれが次の構造体ノードとなることができませんでした？なぜそれが*次の構造体ノードである必要はありますか？うん。 [学生]それは無限ループのようなものだ。うん。 [学生]それはすべて1になります。うん、ちょうど私達がの大きさや何かをするだろうかを考える。構造体自体のサイズは、基本的には+または - ここまたはそこにいくつかのパターン。それは基本的に構造体の中のものの大きさの和になるだろう。ここでこの権利は、何も変更せずに、サイズが容易になるだろう。構造ノードのサイズは、次のi +サイズの大きさになるだろう。私のサイズは4であることを行っている。次回のサイズは4であることを行っている。構造ノードのサイズは8になるだろう。私たちは*、sizeofの思考を持っていない場合、その後はsizeof（i）が4になるだろう。次の構造体ノードのサイズは、iの大きさになるだろう+次のstructノードのサイズを iの+サイズ+次のstructノードのサイズ。これは、ノードの無限再帰になる。これは物事がなければならない方法である理由です。繰り返しになりますが、間違いなく、それを暗記するまたは少なくともあなたのことができるようにできるように、十分にそれを理解それがどのように見えるかを介して理由。私たちが実装するつもりだもの。の長さがあれば、リストあなたはカンニングと周りに保つことができるグローバル長か何かが、我々はそれをするつもりはない。我々は、リストの長さをカウントするつもりだ。我々は含まれていた、それは基本的には検索のようなものだそうので、この整数は、リンクされたリストに含まれているかどうかを確認するための整数のリンクリストを持っています。 Prependはリストの先頭に挿入しようとしている。 Appendは末尾に挿入しようとしている。 Insert_sortedは、リスト内のソートされた位置に挿入しようとしている。 Insert_sortedの種類は、prependを使ったことがないことを前提としていますか悪いかの方法で追加します。あなたが実装しようとしているときにinsert_sorted-Insert_sorted のが我々のリンクリストがあるとしましょう。これは、現在、5、4、2、のように見えるものです。私は、なるように長いリスト自体が既にソートされているように、3を挿入したいそれは3が属する場所が簡単に見つかります。私は2から開始します。さて、3は2よりも大きいので、私は行き続けたい。ああ、4は大きすぎるので、私は3が2と4の間に入るようになるだろう知っていると私はポインタとすべてのものを修正する必要があります。しかし、我々は厳密にinsert_sorted使用しなかった場合、好き聞かせはちょうど、私は6を付加言うその後、私のリンクされたリストは、このなろうとしています。それが今では意味をなさないので、insert_sortedためには、あなただけと仮定することができ操作は存在していてもリストがソートされていることこれは、それをソートしないことがあります、それはそれだ。それらは、実装する必要があるとしている主なものですので、参考にインサートを検索します。今のところは、長さを実行する分を取ると、含まれていますそしてそれらは比較的迅速でなければならない。閉店時間が近づいてますので、誰もが長さのために何を持っているか、含まれています？彼らはほぼ同じことになるだろう。 [学生]長さ。、見改訂してみましょう。オーケー。あなたが説明したいと思います？ [学生]私はただのポインタ·ノードを作成し、当社のグローバルな変数で、最初に初期化し、その後私はワンセグ障害を取得し、その場合は0が返されないようにそれがnullだかどうかを確認します。そうでなければ、私をループして、整数の中を追跡する何回私は、リストの次の要素にアクセスしたと同じインクリメント操作でも、その実際の要素にアクセスするそして、私は継続的に、それがnullの場合は、チェックが見たい作るそれがnullの場合には、それは中止され、ちょうど私がアクセスした要素数を返します。 [ロブB.]誰が何についてのコメントを持っていますか？これは賢明な細かい正確さに見えます。 [学生]私はあなたがノード== nullを必要とは思わない。ええ、そうノード== nullの場合は0を返します。しかし、もしノード== nullの場合、この-OH、正しさの問題があります。それはちょうどあなたが私を返していたが、それは現在のスコープではありません。あなただけのint iを必要とするため、i = 0です。ノードがnullの場合はしかし、その後、私はまだ、0になるだろうそして我々は0を返すつもりなので、この場合は同じです。別の一般的なことは宣言しておくことです forループのノード内の。あなたは、いや、-OHを言うことができる。それはこのように続けましょう。私はおそらく、int型i = 0のここに置いたであろうその後、ノード*ノード=ここで初めて。そして、これはおそらく今これを取り除く方法を引くです。これは、私はそれを書かれているだろうかと思われます。あなたは、このようにそれでも見通しでした。右ここにループ構造のためにこの i = 0のint用者としてのあなたに同じくらい自然であるべき iはi + +の配列の長さよりも小さいそれはあなたが配列を繰り返し処理方法の場合、これは、リンクされたリストを反復処理する方法です。これは、いくつかの点で第二の天性である必要があります。このことを念頭に置いて、これはほぼ同じものになるだろう。あなたは、リンクリストを反復処理するつもりだ。ノードは-I値が呼び出されたか見当がつかない場合。ノードi。そのノードの値= iはtrueを返し、それはそれましょう。ていることに注意してください私たちが今までにfalseを返す唯一の方法我々は全体のリンクリストを反復処理してtrueを返すことがない場合であり、そう、それはのこれが何。サイドノートとして、我々は、おそらく前後どちらに付加するために取得することはありません。クイック最後のノート。あなたはstaticキーワードが表示された場合は、それでは、静的なint型のカウント= 0としましょうそれから私達はカウントを行う+ +では、基本的にグローバル変数と考えることができ、私は、これは我々が長さを実装しようとしている方法ではないと述べたにもかかわらず。私はここでこれをやって、次に+ +をカウントしています。我々は我々の数が増加している私達のリンクリストにノードを入力することができます任意の方法。この方法のポイントは、staticキーワードが何を意味するかである。私はちょうどintカウントを持っていた場合=通常の古いグローバル変数であろう0。何静的intカウント手段と、それは、このファイルのグローバル変数であるということです。それは、いくつかの他のファイルのために不可能であるあなたが起動している場合は、PSET 5考える好きです。は、両方のspeller.cを持っていて、持っているdictionary.c あなたはちょうどspeller.cで、次に何かをグローバルな事を宣言した場合 dictionary.c、またその逆でもアクセスできます。グローバル変数は、任意のcファイルでアクセスできますしかし、静的変数は、ファイル自体の内部からのみアクセスできますそう内部スペルチェッカーまたはdictionary.cの内側の、これは私が私の配列の大きさのための私の変数を宣言する方法の一種であるまたは辞書内の単語の私の数の大きさ。私は誰がアクセスしたことをグローバル変数を宣言する必要はありませんので、私は実際には私自身の目的のためにそれを気遣う。これの良いところは、また、全体の名前の衝突のものです。他のいくつかのファイルがカウントと呼ばれるグローバル変数を使用しようとすると、物事は非常に、非常に間違って行くことは、ので、これはうまく物事を安全に保つ、唯一のあなたはそれにアクセスすることができますと誰もができ、他の誰かが、countという名前のグローバル変数を宣言している場合それはカウントと呼ばれるあなたの静的変数とは干渉しません。それは静的が何であるかです。これは、ファイルグローバル変数です。何についての質問？すべてのセット。さようなら。 [CS50.TV]