[Powered by Google Translate] [セクション6：あまり快適] [ネイトHardison] [ハーバード大学] [これはCS50です。] [CS50.TV] かしこまりました。第6節へようこそ。 今週、私たちは、セクション内のデータ構造の話をすることになるだろう 今週の問題はspellrで設定主な理由 異なるデータ構造の調査の全体の束がありません。 あなたは問題セットで行くことができるさまざまな方法の束がありますが、 あなたが知っているとより多くのデータ構造は、次の操作を行うことができ、よりクールなもの。 それでは始めましょう。まず、スタックの話をするつもりだ 我々が話をしようとしているスタックとキューのデータ構造。 我々はグラフについて話し始めるときに、スタックやキューは、本当に便利だ その我々が今のように多くのことをするつもりはない。 しかし、彼らは本当にCSの大きな根本的なデータ構造の一つを理解してもいいです。 問題セットの明細書の記載、 と同類のようにスタックに関する、あなたがそれを引っ張り上げて、協議 あなたは食堂で食堂に持っているダイニングトレーの山 ダイニングのスタッフが来て、彼らがそれらを掃除した後、食事のトレイを出したときにどこに 彼らは彼らに他の上に1を積み重ねる。 そして、子供たちは食べ物を得るために来たときに、 彼らはその後、最初のトップ1、その下1、その下1、トレイをやってのける。 だから、実質的には、ダイニングのスタッフは下に置くことを第一トレイが取り出される最後のものである。 ダイニングスタッフが保留にした最後のものが夕食のために離陸される最初のものです。 あなたがすでに持っていない場合は、ダウンロードすることができ、問題のセットの仕様では、 我々は、この種の構造体を使用してスタックデータstuctureのモデリングの話。 だから我々はここに持っているもの、これは、講演で発表されたものと似ています 講義を除いて、我々は、char * sのとは対照的に、int型がこれを発表した。 これは、その店に何をスタックになるだろうか？ ダニエル？我々は、このスタックに何を保存している？ [ダニエル]文字列？ >>我々はまさに、このスタック内の文字列を格納している。 スタックを作成するために持っている必要があるすべての配列です 特定の容量の、この場合であって、 容量は、それが一定だからすべて大文字であることを行っている。 そして、配列に加えて、我々は追跡する必要があるすべては、配列の現在のサイズです。 それはクールなものだここで注意すべきことの一つ 我々は、別のデータ構造、配列の上に積み重ねられたデータ構造を作成しているということです。 スタックを実装するさまざまな方法があります。 我々は、うまくいけば、リンクリストの問題をやった後、非常にまだそれを行うことはありません あなたは簡単にだけでなく、リンクされたリストの上にスタックを実装することができる方法を見ていきます。 しかし、今の私たちは、配列で我慢しましょう​​。 だからもう一度、私たちが必要とするすべては配列であり、我々は単に配列のサイズを追跡する必要があります。 [サム]申し訳ありませんが、なぜそれが、スタックは、文字列の上だと述べているということです？ 文字列がスタック内にあるように僕には思える。 [Hardison]うん。我々は我々の配列データ構造を取っている、作成している - それは素晴らしい質問ですね。そこで質問は、このオンラインを見ている人々のために、なぜ なぜ我々は、スタックは、文字列の上にあると言っている ここでは、文字列がスタック内にあるように見えますか？ので これは完全にケースです。 私が言及していた、我々は、配列のデータ構造を持っているということでした。 我々は、char *の配列、文字列のこの配列を、持っている そして我々は積み重ねられたデータ構造を作成するためにそれに追加しようとしている。 だからスタックは配列よりも若干複雑です。 我々は、スタックを構築するために配列を使用することができます。 我々はスタックは配列の上に構築されていると言うところだからです。 同様に、私が以前言ったように、我々はリンクリストの一番上にスタックを構築することができます。 代わりに我々の要素を保持する配列を使用しての、 私達は私達の要素を保持し、その周りにスタックを構築するためにリンクされたリストを使用することができます。 、いくつかのコードを見て、いくつかの例を歩くましょう ここで実際に何が起こっているかを確認します。 左側には、私はそのスタック構造体がメモリにどのように見えるか下に投げてきた 容量は＃4になるように定義された場合。 我々は4つの要素char *配列を持っている。 私たちは、文字列[0]は、文字列[1]は、文字列[2]文字列[3]を持っている 私達のサイズの整数の後、その最後のスペース。 これは理にかなっていますか？オーケー。 これは、私が右に何をすべきかとどうなるかです 私のコードになるでしょう、これだけのstr​​uct、sと呼ばれる積み重ねられた構造体を宣言することです。 これは、我々が得るものです。これは、メモリ内のこのフットプリントを定めています。 ここで最初の質問は、このスタック構造体の内容は何ですか？ 今の彼らは何もしているが、彼らは全く何もわからないん。 彼らはゴミのこの種だ。我々は考え、その中に何もありません。 我々はスタックsを宣言するとき、我々は単にメモリの上にそれをダウンして投げている。 これは、int iを宣言して初期化しないような種類のものだ。 あなたはそこに何があるかわからない。あなたは、そこに何があるかを読み取ることができます しかしそれは超便利ではないかもしれません。 あなたが常にそうする覚えておきたいことの一つは、初期化する必要がありますどのような初期化です。 この場合において、我々は、ゼロになるようにサイズを初期化しようとしている それは私達のために非常に重要であることが判明するために起こっているからです。 我々は、すべてのchar * sは、先に行くとポインタのすべてを初期化することができ おそらく、いくつかのヌル値になるように理解できる。 しかし、それは我々がそれを行うことが全く必要ありません。 さて、スタック上の2つの主な操作はありますか？ 誰もがあなたがスタックで何をすべきか講義から覚えていますか？はい？ [ステラ]を押すと飛び出る？まさに>>。 プッシュとポップすると、スタック上の2つの主な操作です。 とプッシュが何をするのでしょうか？ >>それは上に何かを置く スタックの、その後飛び出るそれを脱ぐ。 [Hardison]その通りです。だからプッシュは、スタックの一番上に何かをプッシュします。 それは、ダイニングスタッフがカウンターの上にダイニングトレイを下に置くようなものだ。 と飛び出るは、スタックのダイニング·トレイの電源を取っている。 Let 'sは、何が起こるかの例をいくつか通って歩く 我々は、スタックに何かを押したとき。 私達は私達のスタックに文字列 'Hello'をプッシュした場合、 これは私たちの図が今どのように見えるかです。 何が起こるかを参照してください？ 私たちは、文字列配列の最初の要素に押し込ま そして私達は私達のサイズは1にカウント引き上げた。 我々は2つ​​のスライド間の違いを見ればそう、ここ、ここ、プッシュ前に0だた。 ここでプッシュした後です。 プッシュ前に、プッシュした後。 そして今、我々は我々のスタック内で1つの要素を持っています。 これは、文字列 "hello"のだし、それはそれだ。 アレイ内の他のすべては、私たちの文字列配列に、まだゴミです。 我々は、それを初期化していない。 Let 'sは、私たちがスタック上に別の文字列をプッシュすると言う。 我々は、この時間に "世界"をプッシュするつもりだ。 それで、あなたは、 "世界は"ここでは "hello"の上に行くことができます参照してください。 とサイズのカウントが2に上がります。 今、私たちは、 "CS50"をプッシュすることができ、それが再びトップに行くよ。 我々は戻ってしまったら、あなたは私たちがスタックの一番上に物事を推進しているかを見ることができます。 そして今、我々はポップに取得します。 我々は、スタックの何かオフを取り出したときに、何が起こったのか？ 誰もが違いを参照してください？それはかなり微妙です。 [学生]サイズ。 >>うん、サイズが変更されました。 あなたは他の何に変更すると予想しているだろうか？ あまりに[学生]文字列。 >>は右。あまりにも文字列。 それは、あなたがこの方法でそれをやっているときが判明 私達は私達のスタックに要素をコピーしていないので、 私たちは実際に何もする必要はありません、我々はちょうどサイズを使用することができます 私たちの配列で物事の数を追跡する ように、我々は再びポップするとき、再び我々はちょうど1に私たちのサイズをダウンして増減します。 実際に行くと何かを上書きする必要はありません。 ファンキーの一種。 それは私たちが行うためには、それが少ない仕事だから、我々は一般的に言葉だけで物事を残すことが判明した。 我々は戻って、何かを上書きする必要がないならば、なぜそれを行う？ だから我々はスタックからポップしたときに二回、ないことをすべてのサイズが数回デクリメントされています。 そして再び、これは我々が我々のスタックに物事をコピーしていないという理由だけです。 はい？どうぞ召しあがれ。 [学生、不明朗] >>そして、あなたは再び何かを押したときに何が起こるか？ あなたは再び何かを押すと、それはどこに行くのですか？ それはどこに、バジルへ行くのでしょうか？文字列へ>> [1]？ >>は右。 なぜそれが文字列[3]に入らない？ [バジル]それは何かが文字列であったことを忘れていたため[1]と[2]？ [Hardison]その通りです。私たちのスタックは、本質的に、それが何かにつかまっていたことを "忘れて" 文字列内の[1]または文字列[2]ので、ときに我々は "やった"を押して、 それは単なる文字列で、その要素に[1]を入れます。 基本的なレベルで、どのようにこの作品に何か質問はありますか？ [SAM]だから、これは量の面で、どのような方法で動的ではありません またはスタックのサイズの点で？ [Hardison]その通りです。これは、 - ポイントは、これが動的にgrowningスタックではないということだった。 これは、ほとんどの四つで、最も、4のchar * sで、保持できるスタックです。 我々は第五の事をしようとプッシュしていた場合は、どうすべきかと思いますか？ [学生、不明朗] [Hardison]その通りです。起こりうる事柄がいくつかあります。 それはおそらく我々が何であったかに応じて、seg faultを可能性 - 正確にどのように我々は、バックエンドを実装しました。 それは上書きする可能性があります。それは我々はクラスで話をそのバッファオーバーフローを及ぼす可能性があります。 何が上書きされる可能性が最も明白なものになるだろう 我々は、スタック上の余分なものを押し付けようとした場合はどうなりますか？ だからあなたは、バッファオーバーフローを述べた。 何が上書きまたは踏みにじられるであろうことかもしれない 私たちは余分なものをプッシュしようとすることで誤ってオーバーフローした場合はどうなりますか？ [ダニエル、不明朗] >>考えられる。 しかし、当初は、何が起こるのでしょうか？我々は第四の事をプッシュしようとしたら？ それは、少なくとも我々が持っているこのメモリ·ダイアグラムで、サイズを上書きすることがあります。 今日我々が実装されようとしているものであるという問題点セット仕様においては、 私たちが何をしたいかは、単にfalseを返しています。 私たちのpushメソッドはブール値を返すために起こっている、 プッシュが成功した場合、そのブール値はtrueになります とスタックがいっぱいになったため、我々はより多くの何かをプッシュすることはできません場合にはfalseを返します。 今は、そのコードを少しいきましょう。 ここに私たちのプッシュ機能です。 スタックのための私達のプッシュ機能は、スタック上に置くために文字列にかかるとしている。 それは、文字列が正常にプッシュされた場合はtrueを返すようになるだろう スタック上で、それ以外の場合はfalse。 ここで行うには良い最初のものになるかもしれないもの上の任意の提案ですか？ サイズは容量に等しい場合に[サム]がfalseを返す？ [Hardison]ビンゴ。いい仕事。 サイズは容量であれば、我々は、falseを返すつもりだ。 私たちは、スタック内のより多くの何かを置くことはできません。 そうでなければ、我々はスタックの一番上に何かを載せていきたいと思います。 最初は、 "スタックの先頭"とは何ですか？ [ダニエル]サイズ0？ >>サイズ0。 スタック内の1つの事がある後のスタックのトップは何ですか？ミッシー、あなたは知っていますか？ [ミッシー]ワン。 >>サイズは、厳密に1つ、である。あなたは、サイズに追加し続ける あなたは配列内のインデックスのサイズで新しい要素を入れていると毎回。 それが理にかなっている場合我々は、ワンライナーのようなものでそれを行うことができます。 我々は文字列の配列を持っているので、我々は、サイズインデックスでアクセスするつもりだ そして我々はそこに私たちのchar *を保存するつもりです。 ここで起こってない文字列のコピーがない方法に注目して、 メモリーの動的割り当て？ そして、ミッシーは、私たちが今何をして育て 我々は、配列内の適切な場所に文字列が保存されているので、 そして彼女は、我々は次のプッシュのための準備が整いましたように、いずれかのサイズを増加しなければならなかったことを言った。 だから我々はs.size使用して行うことができます+ +。 この時点で、我々は我々の配列にプッシュした。私たちがしなければならない最後のことは何ですか？ [学生]は、trueを返します。 >>は、trueを返します。 だから、かなり単純なコードは非常に簡単です。あまりない。 それがわかれば、スタックがどのように動作するかの周りにあなたの頭をラップして これを実装するのは非常に単純です。 さて、これの次の部分では、スタックから文字列を飛び出しています。 私はあなたたちにこの少し上で動作するようにいくつかの時間を与えるつもりだ。 それはほとんど本質的に我々がここでプッシュでやったことの逆です。 私がやったことは、実際には - おっと。 私は、こっちに、アプライアンスにアプライアンスをブートすれ 私はこの問題は、5の仕様を設定してプルアップされてきました。 我々がここでズームインした場合、我々は、私はcdn.cs50.net/2012/fall/psets/pset5.pdfにいる見ることができます。 君たちは、ここsection6.zipに位置しているこのコードをダウンロードしたことがありますか？ かしこまりました。あなたがそれを行っていない場合は、本当にすぐに、すぐにその権利を行う。 私は、ターミナルウィンドウでそれをやる。 私は実際にそれをここにUPしました。うん。 はい、サム？ >>私はあなたのサイズ= strのs.stringのブラケットを言っていた理由について質問がありますか？ strは何ですか？その前にどこかで定義された、またはされている - ああ、char *文字列str内の？ [Hardison]はい、その通りです。それが根拠となった。 >>ああ、大丈夫。申し訳ありません。 [Hardison]我々はインチプッシュする文字列を指定している 私たちは本当にここの話をしなかったことを思いつくかもしれない他の質問があった 我々はsと呼ばれるこの変数を持っていたことを当然のことと取った その範囲と私たちにアクセス可能であった。 我々は、sはこのスタック構造であったことを当然の取った。 だから、このプッシュコードを振り返る あなたは私たちが渡してしまった、この文字列でものをやっていることがわかります 突然のすべてが、その後、私たちはs.size、好きだから来たのにアクセスしている？ 私たちはセクションアーカイブに見しようとしているコードで あなたの問題のセットでやっているだろうことが、その後のもの、 私達は私達のスタックがグローバル変数を構造体作った 我々はすべて私たちのさまざまな機能でそれへのアクセスを持つことができるように 手動で参照することによって、それを周りに渡すと、それを渡すことなく、 それにもののすべてのようなものをやる。 私達はちょうどよりよいものを作るために、可能ならば、少し浮気している。 そして、それはそれは楽しみのためですので、私たちがここでやっているものだ、それは簡単です。 彼らは一つの大きなデータ構造を持っている場合、多くの場合、あなたは人々がこれを行うに表示されます それは、そのプログラム内で運用されている。 のは、アプライアンスにフェールオーバ戻りましょう。 皆は正常section6.zipを得たのですか？ みんな解凍section6.zipを使用してそれを解凍？ あなたは、セクション6のディレクトリに行く場合 - アーッ、あらゆる場所に - と、ここに何があるかをリストし、あなたが3異なる。cファイルを持っていることがわかります。 あなたは、片方向リンクリストであるキュー、SLL、およびスタックを持っている。 あなたはstack.cを開くと、 あなたは、私たちが私たちのために定義されているこの構造を持っていることがわかります 先ほどスライドで話している正確な構造体。 我々は、スタックのための私達のグローバル変数を持っている 私達は私達のプッシュ機能を持っている、 それから私達は私達のポップアップ機能を持っている。 私は、ここでスライド上に戻って押し上げるためのコードを置くことにしましょう しかし、私があなたたちがやりたいことは、あなたの実力を最大限に発揮し、ある 行くとpop関数を実装します。 一度あなたがそれを実装しました、あなたは、スタックを作ると、これをコンパイルすることができます その後、得られたスタックの実行可能ファイルを実行し、 それがダウンしてここにメインでだとこのテストのすべてのコードを実行されます。 そしてメインは、実際にpushとpopの呼び出しを行うの面倒を見る そして万事通過することを確認すること。 また、右ここでスタックサイズを初期化する ので、あなたはそれを初期化することを心配する必要はありません。 あなたはそれが適切に初期化されていると仮定することができます あなたはポップアップ機能でアクセスしている時間によって。 お分かりでしょうか？ だからここに私達は行く。プッシュコードがあります。 私は君たち5分または10分を与えるでしょう。 そして、あなたがコーディングしているときに、暫定的に質問があれば、 それらを大声で尋ねてください。 あなたはスティッキングポイントに着くそうならば、単に尋ねる。 他のみんなに知らせて、私を知ってみましょう。 あまりにもあなたの隣人と協力してください。 [ダニエル]我々は、ちょうど今ポップアップ実装しようとしている？ただ>>ポップ。 もしそうしたければ、プッシュの実装をコピーすることができますが テストでは、動作するように。 それが入るものをテストするのは難しいので - で始まるに、スタック内の何かが存在しない場合、または、それがスタックからポップなものを試すのは難しい。 返すことになってポップとは何ですか？スタックの先頭から要素。 それはスタックの先頭の要素を降りることになっている その後、スタックのサイズを減少させる そして今あなたは上の要素を失ってしまった。 そして、あなたは一番上の要素を返す。 [学生、不明朗] [Hardison]だからあなたがそれを行うとどうなりますか？ [学生、不明朗] どうした何が起こって終了すると、おそらくどちらかにアクセスしているです まだ初期化されていない要素なので、あなたの計算 最後の要素がどこにあるのはオフになっています。 あなたが気づけばだからここで、プッシュでは、我々はs.size要素に文字列にアクセスしている それは、新しいインデックスだから。 これは、スタックの新しいトップだ。 ポップで、s.sizeは次のスペースであることを行っているのに対し、 あなたのスタック内のすべての要素の上のスペース。 最上位の要素がs.sizeではないので、 むしろ、それはその下だ。 もし他に行うべき事 - ポップで、 あなたのサイズを減少させなければならないのさ。 あなたは右ここに私たちの小さなダイアグラムに戻り覚えていれば、 私たちはPOPと呼ばれるときには本当に、我々が見た唯一のことは起こって このサイズは、1に、最初の2つに、ドロップされたということでした。 その後、我々は上に新しい要素を押したときに、それは適切な場所で上に行くだろう。 [バジル] s.sizeが2であれば、それは、要素2へ行こうとしなかった 次にその要素をポップにしたいと思うだろう？ 我々はに行ってきましたので、もし - >>だから、もう一度これを見てみましょう。 これは、この時点で我々のスタックである場合 そして我々は、ポップアップを呼び出す 位置のインデックスは、最上位の要素ですか？ [バジル] 2で、それは3をポップになるだろう。 >>は右。 それで、我々の大きさが3のところですが、我々はインデックス2にある要素をポップしたいと思います。 それはあなたが配列のゼロインデキシングで持っている1つずれのその典型的なものだ。 だから、第三の要素をポップしたくないが、第三の要素のインデックスは3ではありません。 私たちが推進している我々はそのマイナス1を行う必要はありませんし、理由 今ので、あなたは気付くされている最上位の要素、 我々はこの時点でスタックに何か他のものをプッシュした場合、 私たちは、インデックス3でそれをプッシュしたいと思います。 そして、それはちょうどあなたが推進している時にサイズとインデックスが並ぶように起こります。 稼働中のスタックの実装を持っている誰か？ あなたは、稼働中のスタック1を持っている。あなたはまだ働いてポップを持っていますか？ [ダニエル]はい。そう思います。 >>プログラムが実行されていて、断層ワンセグではない、それはプリントアウトしている？ あなたがそれを実行したとき、それは "成功"をプリントアウトしていますか？ うん。それは "成功"を出力し、ブームを行っていない場合、スタックを確認し、それを実行し、 その後、すべての良いことだ。 かしこまりました。 、のは本当にすぐにアプライアンスに渡ろう そして、私たちはこの見ていきます。 我々は、ポップと一緒にここで何が起こっているのかを見れば、 ダニエルは、あなたがしたことはまず何でしたか？ [ダニエル] s.sizeが0より大きい場合。 [Hardison]オーケー。そして、あなたはなぜそんなことしたの？ [ダニエル]スタック内部の何かがあったことを確認します。 [Hardison]右。あなたはs.sizeが0より大きいことを確認するためにテストしたい; そうでなければ、何が起こるしたと何をしたいですか？ [ダニエル]戻りヌル？ >>リターンヌル、正確に。 だからs.sizeが0より大きい場合。その後、我々は何をするつもりですか？ スタックが空でない場合、我々は何をしますか？ [ステラ]あなたはサイズを減少させる？あなたは大丈夫、サイズをデクリメント。>> ですから、どのようにそれをやったの？ >> s.size- - 。 [Hardison]グレート。そしてあなたは何をしましたか？ [ステラ]そして私がリターンを言っs.string [s.size]。 [Hardison]グレート。 そうでなければnullを返します。はい、サム？ [サム]なぜそれがs.size + 1である必要はありません？ [Hardison]プラス1？ >>うん。 >>はそれを得た。 あなたはうち1つを取っているので、[サム]私は、と思った その後、あなたは、彼らが求めたものは返すべきではないつもりだ。 [Hardison]そしてこれは我々が0のインデックスのこの全体の問題に話をしていたものばかりだった。 だから我々はこっちにはズームインしている場合。 私たちは右ここにこの男を見れば、あなたは、私たちが飛び出したときに見ることができ 私たちは、インデックス2の要素を炊いてるはずだ。 だから我々は大きさが私たちのインデックスと一致した後、最初に私たちのサイズを小さくします。 我々は最初のサイズを減少させていないなら、私たちは-1してからデクリメント大きさをしなければならない。 グレート。すべていいですか？ これについて何か質問はありますか？ 同様に、これを書くためのさまざまな方法があります。 実際には、私たちも何かを行うことができます - 私たちはワンライナーを行うことができます。 私たちは、1行の復帰を行うことができます。 我々はそれを実行して、返す前に私たちは実際に増減できます。 だからパッティング - s.size前。 それはラインが本当に密になります。 どこに違い - Sサイズとs.size- - つまり、この接尾辞 - ので、彼らはそれはpostfix呼び出す - 来る後s.size- - s.sizeがインデックスを見つけることの目的のために評価されることを意味 この行が実行されたときには、現在あるように、 そして、これは - の行が実行された後です。 インデックスs.sizeの要素​​がアクセスされた後。 我々が最初に起こるデクリメントしたいので、それは、我々が望むものではありません。 Othewise、我々は境界のうち、効果的に、配列にアクセスすることになるだろう。 我々は、我々が実際にアクセスしたい1上記の要素にアクセスすることになるだろう。 うん、サム？ >>それが速くなったり、1行で、またはしないように以下のRAMを使用しますか？ [Hardison]は正直なところ、それは実際に依存します。 [サムは、判読不能] >>うん、それは異なります。あなたは、コンパイラのトリックを行うことができます それを認識するようにコンパイラを得るために、通常、私は想像する。 だから我々は、このコンパイラの最適化のものについて少し言及した あなたは、コンパイル時に行うことができます そしてそれは、コンパイラが把握することができるかもしれないという事のようなものだ オハイオ州のように、ちょっと、多分私は、一回の操作でこのすべてを行うことができます RAMからのサイズ変数を読み込むとは対照的に、 戻ってそれを記憶し、それをデクリメントしてから、もう一度それを積み戻し この操作の残りの部分を処理します。 しかし、一般的に、いや、これは一種の事ではありません それが大幅に高速化してプログラムを作るために起こっている。 スタック上の任意のより多くの質問？ だから、プッシュとポップ。君たちはハッカー版を試してみたい場合は、 我々はハッカー版でやったことは実際に行っている そして、このスタックは動的に拡張しました。 ここまでプッシュ機能で主に存在する課題は、 その配列を成長させる方法を見つけ出すために あなたは、スタックに上でより多くの要素をプッシュし続けると。 これは、実際にはあまりにも多くの付加的なコードではありません。 へちょうどコール - あなたは正しくそこにmalloc関数への呼び出しを取得するには忘れてはいけない、 あなたはreallocを呼ぶことにしているときに、次に見つけ出す。 もし興味があるならそれは楽しい挑戦です。 しかし、当分の間、のは先に進みましょう、とキューについて話してみましょう。 ここにスクロールします。 キューはスタックの近い兄弟です。 だから、スタック内の、最後に入れたもの 次に取得する最初のものであった。 私たちは、注文、これで最後の先入れ先出し、またはLIFOを持っている。 キューのに対し、あなたはラインに立っている時から期待として、 ラインで取得する最初の人には、キューに入るためにまず、 キューから取得される最初のものです。 我々はグラフを扱う場合キューは、多くの場合、使用されている 我々は、スタックで簡単に話を、次のよう そしてキューは、他のものの束にするのにも便利です。 頻繁に来ることの一つは、例えば、維持しようとしています 要素のソートされたリスト。 そして、あなたは配列でこれを行うことができます。あなたは、アレイ内の物事のソートされたリストを維持することができます しかしそのトリッキーその後どこにあるか常に見つけなければならない 次のものを挿入するための適切な場所。 だから、10までの数、1の配列を持っている場合、 そしてその後は、100を介してすべての数字を1にそれを展開したい 、あなたがランダムな順序でこれらの番号を取得し、すべてを維持しようとしている あなたが通過するようにソートすると、シフトの多くを行うことを終了。 キューおよび基礎となるデータ構造の特定の種類の特定の種類の、 あなたは実際にはかなりシンプルに保つことができます。 あなたがするたびに何かを追加してから、全体を改造する必要はありません。 また、あなたの周りの内部要素のシフトの多くを行う必要もありません。 我々は待ち行列を見てみると、あなたはそれを参照してください - またqueue.cのセクションコード内 - 私たちはあなたを与えてくれたことを構造体には、我々はスタックにあなたを与えた構造体には本当に似ています。 これに対する1つの例外を除いて、その1つの例外があります 、我々は、この追加の整数がヘッドと呼ばれていることである そしてここで頭が、キューの先頭を追跡するためのものです またはキューの最初の要素。 スタックでは、我々は、我々が取得しようとしていた要素を追跡することができました サイズだけを使用して、スタックの一番上、または キューを持つのに対し、我々は、両端に対処するために抱えている。 我々は、タック末尾で物事をしようとしたが、その後正面から物事を返しています。 だから効果的に、頭を、我々は、キューの先頭のインデックスを持っている とサイズは私達に、キューの最後のインデックスを与える 私たちは頭から物事を取得し、尾に物事を上に追加することができます。 スタックを持つのに対し、我々は唯一のこれまでスタックの最上位に対処した。 我々は、スタックの底にアクセスする必要もなかった。 我々は唯一のトップに物事を追加し、上部のものを脱いだ だから我々は、構造体内部には、余分なフィールドを必要としなかった。 それは一般的に意味していますか？ かしこまりました。はい、シャーロット？ [シャーロット、不明朗] [Hardison]それは素晴らしい質問です、それは講義の中で思いついたものだった。 たぶん、いくつかの例を歩くと、なぜ説明します 我々は、文字列をキューの先頭[0]を使用する必要はありません。 だから我々は我々のキューを持っていることを想像して、我々はそれをキュー呼ぶつもりです。 初めに、我々はそれをインスタンス化したときに、 私たちはそれを宣言したとき、我々は何を初期化していない。 それはすべてゴミです。だからもちろん、我々は初期化す​​ることを確認したい 0、合理的なものにするための大きさと頭の両方のフィールド。 我々はまた、先に行くと、私たちのキュー内の要素をnullでした。 そして、この図に収まるために、今私たちのキューは3つの要素のみを保持することができることに気づく。 私たちのスタックは4を握ることができるのに対し、我々のキューには3つだけを保持することができます。 そして、それは図のフィット感を作ることだけです。 ここで最初に起こることは、私たちが "こんにちは"という文字列をエンキューです。 そして、ちょうど我々がここでひどく異なったものには、スタックでやっていないような、 我々は、文字列での[0]の文字列を投げると1によって私たちのサイズを増加します。 私たちは、それが上に置くされる、 "bye"とエンキューします。 だから、これはほとんどの部分のためのスタックのように見えます。 我々は、ここに新しい要素、新しい要素を始めました、サイズが上がって保持します。 私たちは何かをデキューするとき、何がこの時点ではどうなりますか？ 我々はデキューする要素ですデキューしたいとき？ [バジル]文字列[0]。 >>ゼロ。正確に右、バジル。 我々は最初の文字列は、この1、 "こんにちは"を取り除くためにしたい。 だから変更他の事は何でしたか？ 我々は、スタックの何かオフを取り出したときに注意してください、私たちは、サイズを変更 しかしここで、私たちはその変化物事のカップルを持っている。 サイズの変更が、頭の変更を行うだけでなく、。 これは、以前のシャーロットのポイントに戻ってされています。 なぜ我々は、同様にこの頭を持っていますか？ それが、今ではシャーロットを意味していますか？の>>種類。 の[Hardison]種類は？我々はデキュー時に何が起こったのか？ 頭部は今は面白いと何をしたのか？ [シャルロット]ああ、それが変更されたため - 大丈夫。そうですか。 なぜなら頭 - 頭が場所の条件の変化を指している。 それはもはや、常にゼロインデックス一つだ。 >>うん、その通りです。 高い要素をデキューしたらどう起こったことだった 行われていたと我々はこのヘッドフィールドを持っていなかった 我々は常に我々のインデックス0されているキューの先頭にこの文字列を呼び出していたので、 次に我々は、キューの残りの部分をシフトダウンする必要があると思います。 我々は、文字列からから "さようなら" [1]シフトするための文字列に[0]を持っていると思います。 と文字列[2]を押し、文字列[1]。 そして、我々は、要素のリスト全体に対してこれを行う必要があるだろう 要素の配列全体。 そして、我々は配列でこれをやっているとき、それは本当に高価な取得します。 だからここに、それは大したことではありません。私達はちょうど私達の配列の3つの要素を持っています。 しかし、我々は、1000個の要素のキューまたは万要素を持っていた場合、 その後突然、我々は、すべてのループでデキュー·コールの束を作り始める 物事は実際にそれが常にすべてのダウンシフトとスローダウンしようとしている。 あなたは、1、1によるシフト、1によるシフト、1によるシフトによるシフトを知っている。 代わりに、我々はこのヘッドを使用し、我々はそれが本当にポインタではないにもかかわらず、それを "ポインタ"と呼ぶ 厳密な意味で、それがポインタ型ではありません。 それは、int *またはchar *またはそのような何かではありません。 しかし、それは我々のキューの先頭を指しているかを示す。うん？ [学生]ちょうど頭にあるものからポップする方法デキューは知っていますか？ [Hardison]どのようにデキューが頭に何でもぽんする方法を知っていますか？ >>右、ええ。 >>それは何を見ていることに設定されているだけでも頭のフィールドです。 だから、この最初のケースでは、我々がここに見れば、 私たちの頭には0、インデックス0です。 >>は右。 [Hardison]は、それだけで大丈夫、まあ、インデックス0の要素は、文字列 "こんにちは"と言うだから 私たちの待ち行列の先頭の要素です。 だから我々はその男をデキューしようとしている。 そして、それは、呼び出し元に返される要素になります。 はい、サアド？ >>だから頭は基本的には設定 - インデックス、それをするつもりだどこ？ それはそれの始まりだ？ >>うん。オーケー。>> [Hardison]は配列の新たなスタートになってですね。 だから、あなたが何かをデキューするとき、あなたがしなければならないすべては、インデックスq.headにある要素にアクセスされている そしてそれはあなたがデキューする要素になります。 また、サイズを増減する必要があります。 物事はこれと少しトリッキー取得する場所我々はビットで表示されます。 我々は再びエンキュー場合我々は、現在デキューし、 我々はどこをエンキューしますか？ 次の要素は、私たちのキューにどこに行くのでしょうか？ 私たちは、 "CS"という文字列をエンキューしてみたいと思います。 それは、どのインデックスに行くのだろうか？ [学生]文字列[2]。 >> 2。 なぜ2と0ではない？ [バジル]今、頭が1であるため、リストの先頭のようなものだそうなんですか？ [Hardison]右。そして、何は、リストの終わりを表す？ 私達は私達のキューの終了を示すために何を使っていましたか？ 頭は私達のキューの先頭、私達のキューの始まりです。 私達のキューの最後は何ですか？ [学生]サイズ。 >>サイズ、丁度。 それで、我々の新しい要素は大きさでに行くと、私たちが取ることの要素がオフ頭部に外れます。 我々は次の要素をエンキューしたとき、我々は大きさで、それを入れている。 あなたががでていることを置く前に、[学生]は、サイズが右、1でしたか？ [Hardison]右。そうではないかなりのサイズで。サイズ+ 1ではないが、+ヘッド。 私達は頭部量ですべてをシフトしているため。 そこでここでは、今、私たちは、インデックス1から始まり大きさ1のキューを持っている。 尾はインデックス2になります。はい？ [学生]をデキュー文字列[0]は、メモリ内の文字列 'のスロットはどうなりますか ただ基本的には、空になったため、あるいは単に忘れましたか？ [Hardison]うん。この意味で、我々はそれらを忘れている。 私達はのためにそれらのコピーを保存していた場合 - 多くのデータ構造は、多くの場合、要素の独自のコピーを保存します データ構造を管理する人は心配しないで済むように すべてのこれらのポインタが行く場所について。 データ構造は、すべてのコピーに保持し、すべてのものへに保持してい すべてが適切に解決されないことを確認します。 ただし、この場合には、これらのデータ構造だけで、簡単にするために、 我々は彼らに保存していることを何かのコピーを作成されていません。 [学生]は、だから、これはの連続配列である - ？ >>はい。 我々が定義は、この構造の何だったかを振り返ってみると、それはです。 それは、あなたが見てきたと同じように標準的な配列だ char *型の配列。 それはしていますか - ？ >>うん、私は思っていた あなたは最終的にある程度、メモリー不足にあげるなら、 あなたの配列内のすべてのこれらの空のスポットを持っている場合はどうなりますか？ [Hardison]うん、良い点だ。 我々はこの時点では今起こったことを見れば、 私達が私達のキューをいっぱいにしたら、それは次のようになります。 しかし、我々は本当に私たちのキューをいっぱいにしていない 私達はサイズ2のキューを持っていますが、それはインデックス1、で始まっているため、 私たちのヘッドポインタがどこにあるか、それはだから。 あなたが言っていたように、その文字列の要素[0]は、インデックス0に、本当にありません。 それはもう我々のキューではありません。 私達はちょうどに行くと我々はそれをデキューするとき、それを上書きする気にしませんでした。 だから我々はメモリを使い果たしてしまったように見えるにもかかわらず、私たちは本当に持っていない。 私たちが使用するためにその場所を用意しています。 私たちが何かをしようとする最初のデキューした場合に適切な行動、 さようなら寝つくこと、 "バイバイ"が好きです。 今度は私達のキューはインデックス2から始まり、大きさ1である。 そして今、我々がしようとした場合、もう一度何かをエンキュー、50を言う 50はインデックス0にこの場所に行く必要があります それはまだ私たちのために利用可能だからです。はい、サアド？ [Saadは]それは自動的に発生しますか？ [Hardison]それはかなり自動的には行われません。あなたは数学を行う必要が それを動作させることが、本質的に、私たちが行ったのは我々だけで巻き付けたされている。 [SAAD]そしてこれはそれの真ん中に穴がある場合、それは大丈夫ですか？ [Hardison]我々は数学が適切に動作させることができればそれはある。 そして、それはそれはmod演算子と関係が実際には難しいことではないことが判明した。 だから同じように、我々は、シーザーと暗号のものでやった MODを使用して、我々は物事が一周して取得し続けることができます ぐるぐると周りの私達のキューを持つ、 その先頭ポインタが動き回る保つ。 サイズは常にキュー内に実際にある要素の数を尊重していることに注意してください。 それだけを循環保持ヘッドポインタです。 我々は我々が最初に戻った場合は、ここで何が起こったのかを見れば、 そしてあなただけの頭に何が起こるかを見て 私たちは何かをエンキューしたとき、何も頭に起こらなかった。 我々が何かを待ち行列に入れても、何も頭に何が起こっていません。 私たちは何かをデキューするとすぐに、頭が1ずつ上がります。 私たちが何かを待ち行列に入れても、何も頭に起こりません。 私たちが何かをデキューするとき、突然頭にインクリメントされます。 私たちが何かをエンキューしたとき、何も頭に起こりません。 我々は再び何かをデキューした場合、何がこの時点で起こるのでしょうか？ 任意の考え？何が頭に起こるでしょうか？ 頭に何をすればいいのか 我々は何か他のものをデキューしていた場合はどうなりますか？ 頭部は今、インデックス2の位置にある これは、キューの先頭には文字列[2]であることを意味します。 0を返す[学生]？ >>それは0に戻ります。それはまさに、周りに戻ってラップする必要があります。 これまでのところ、我々は、デキューと呼ばれるたびに、私たちは、頭に1を加えてきた 頭に1を追加して、頭に1を加え、頭に1を追加します。 そのヘッドポインタは、我々の配列の最後のインデックスを取得し、できるだけ早く それから私達は最初に周りにそれを戻してラップする必要があり、0に戻ります。 [シャーロット]スタックでキューの容量を決定しますか？ [Hardison]このケースでは、我々だけで＃定義された定数を使用してきた。オーケー。>> [Hardison]は実際のcファイルでは、あなたがそれで少しに行くとマックができます そしてそれは大きなまたはあなたが望むようにはわずかにします。 [シャーロット]だからあなたはそれを待ち行列を作っているときに、コンピュータが知っているどのように作るのですか あなたがスタックになりたいどのように大きな？ [Hardison]素晴らしい質問ですね。 いくつかの方法があります。一つは、ちょうど正面にそれを定義することです。 これは4つの要素または要素または50万を持っているキューであることを行っていると言う。 他の方法はハッカー版の人たちがやっていることを行うことです 多くの物事はインチ追加取得としてキューが動的に増加持って関数を作成する [シャルロット]だから最初のオプションで行くことに、あなたはどのような構文を使用しますか プログラムに通知するために、キューのサイズは何ですか？ [Hardison]ああ。それでは、これから抜け出すことができます。 私はここではまだstack.cので、私はちょうどここに一番上までスクロールするつもりです。 あなたはこの権利をここに見ることができますか？これは＃10容量を定義しています。 そして、これが我々が待ち行列のために持っていることはほぼまったく同じ構文です。 キューを除いて、我々はここで、余分な構造体のフィールドを持っている。 [シャルロット]ああ、私は容量が文字列のための容量を意味思った。 [Hardison]ああ。それは言葉の最大の長さだ。>> >>はそれを得た。 うん。ここに容量 - 偉大なポイントだ。 そして、これはトリッキーなものです 私たちはここで宣言したことはchar *型の配列であるためです。 ポインタの配列。 これは文字の配列である。 これは、あなたがファイルI / O用のバッファを宣言してきたときに見てきたものと考えられます あなたは、スタック上に手動で文字列を作成してきたとき。 しかし、私たちがここに着いたことはchar *型の配列です。 だからそれはポインタの配列です。 実際、我々は戻ってズームアウト、我々はここで何が起こっているかを見れば プレゼンテーションでは、その実際の要素は、文字データを参照してください。 配列自体に格納されていません。 何がここで我々の配列内に格納されているのは、文字データへのポインタです。 オーケー。だから我々は、キューのサイズがちょうどスタックと同じようにされている方法を見てきました サイズは、常にキュー内の現在の要素数を尊重しています。 2エンキューを行った後で、サイズは2です。 デキューを行った後のサイズは今1です。 別のエンキューを行った後でサイズが2まで戻っています。 だから大きさは間違いなく、キュー内の要素数を尊重 その後頭がちょうどサイクリングを続けている。 それは0-1-2、0-1-2、0-1-2から行く。 そして、我々はdequeueを呼び出すたびに、ヘッドポインタは、次のインデックスに増加します。 頭が上に行くとしている場合、それは0に周りにループバックします。 だからということで、我々は、デキュー関数を書くことができます。 そして、我々はあなたたちではなく、実装するためエンキュー機能を残すつもりだ。 私達は私達のキューの要素をデキューする場合は、 我々はスタックのポップ機能を書き始めたとき、ダニエルはやった最初のことは何でしたか？ 私はまだ語られなかった誰かから聞いてみましょう。 、見サアドましょう、あなたはダニエルは、彼が書いたポップの最初の文として、何をしたか覚えていますか？ [サアド]がありました、それがあった - 彼は何かをテスト。>> [サアド]サイズが0より大きい場合。まさに>>。 そしてそのためのテストはどうでしたか？ [サアド]配列の中に何があるのか​​どうかを確認するためにテストしていたね。 [Hardison]うん。その通りです。それが空の場合、それで、あなたは、スタックの外に何かをポップすることはできません。 それが空の場合同様に、キューから何かをデキューできません。 我々はここで我々のデキュー関数の中で、まず最初にすべきことは何ですか、あなたは思いますか？ [サアド]サイズが0より大きい場合は？ >>うん。 このケースでは、私は実際にちょうどそれが0であるかどうかを確認するためにテストしてみた。 それが0である場合、我々は、nullを返すことができる。 しかし、まったく同じロジック。 とのこれを続けましょう。 サイズが0でない場合、我々はデキューする要素はどこにあるのでしょうか？ [サアド]頭では？まさに>>。 私達はちょうど私達のキューの最初の要素を引き出すことができる 先頭の要素にアクセスすることにより。 クレイジー何もない。 その後、我々は何をすべきでしょうか？何が起こっている？ 我々はデキューでの話他の事は何でしたか？ 私たちのキューが変更されているため、二つのことが、起きるべくして起きる。 [ダニエル]サイズを縮小します。 >>我々はサイズを小さくし、ヘッドを増やす必要があるかも？その通りです。 頭を上げるために、私たちはやみくもに覚えて、頭を上げることができない。 我々だけで行うことはできませんqueue.head + +を 我々はまた、能力によってこのmodを含めなければなりません。 そして、なぜ私たちは、ステラ、容量によってMODのでしょうか？ [ステラ]それが一周しているので。まさに>>。 容量によって、我々はmodが0に戻って周りにラップする必要があるため。 だから今、この時点で、我々は、ダニエルが言ったことを行うことができます。 我々は大きさを増減できます。 そして、我々は単にキューの先頭にあった要素を返すことができます。 最初は危ないの種類を探します。あなたが質問を持っているかもしれません。申し訳ありませんが？ [サム]なぜキューの先頭にある第一ですか？それはどこへ行くのでしょうか？ [Hardison]それは下から4行目から来ている。 私達は私達のキューが空でないことを確認するためにテストした後、 我々が最初にchar *を引き出し、私たちは頭指数の前に座っている要素を引き出し 私たちの配列の、私たちの文字列の配列、>>およびコールが最初の？ [Hardison]そして我々はそれが最初の呼び出し。うん。 ちょうどそれをフォローアップするために、なぜあなたは私たちがそれをしなければならなかったと思いますか？ [SAM]各第ちょうどq.stringsを返している[q.head]？ >>うん。 >>我々は、MOD関数でq.headのこの変化をやっているので、 また、戻りライン内でそのを行う方法はありません。 [Hardison]その通りです。あなたは上のスポットだ。サムは完全に上のスポットだ。 我々は、キューの最初の要素を取り出して、変数に格納しなければならなかった理由 我々だけでq.headいた場所は、この行からである mod演算子は、私たちが行うことができるものがないではあり 1行目の - そしてそれがなくても頭の上に有効になりました。 我々は実際には最初の要素を引き出すために持っているので、その後、ヘッドを調整 サイズを調整した後、私たちが引き出されている要素を返します。 そして、これは我々が後で来るのを見るだろうというものです リンクリスト、我々は彼らと遊んでよう。 頻繁にあなたが解放またはリンクされたリストを廃棄しているとき あなたは次の要素、リンクリストの次のポインタを覚えておく必要が 現在の1を廃棄する前に。 なぜならそうしないと、リストに残っているものの情報を捨てる。 あなたがアプライアンスに行けば今、あなたはこれについてqueue.c-Xを開く。 私はqueue.c開く場合だから、私はここでズームさせ、 あなたは同じような見栄えのファイルを持っていることがわかります。 我々はstack.cと、以前持っていたものに似て見栄えのファイル。 私達はちょうど私達がスライドで見たように定義されたキューのための私達の構造を持っている。 私たちは、あなたが何をするのです私たちのエンキュー機能を持っています。 そして、我々はここでデキュー機能を持っています。 ファイル内のデキュー関数が実装されていない、 しかし、私はあなたが好きな場合は、それを入力することができるようにPowerPointの上でそれを元に戻します。 そこで、次の5分間かそこらのために、君たちは、エンキューに取り組む これは、ほとんどデキューのちょうど逆です。 あなたがエンキューしているときに頭を調整する必要はありませんが、あなたは何を調整する必要があるのですか？ サイズ。あなたがエンキューしたとき、頭が手つかずのままですので、サイズが変更されます。 しかし、それは少しの時間がかかりますか - あなたはMODをいじってあります 新しい要素を挿入する位置を正確に把握する指標。 だから私は、スライド上のデキューを戻して、あなたを少し男をあげる、 君たちは疑問を持っていると、私たちができることをそれらを叫ぶ すべてのグループとしてそれらについて話しています。 また、無関心サイズで - あなたはサイズを調整するときは、常にちょうど缶 - あなたは今までサイズをmodにする必要がありますか？ [ダニエル]第>>あなたは、サイズをmodに権利を持っていない。 you're場合サイズは、常になるので - 、あなたは適切なものを管理していると仮定して サイズは、常に0と3の間になります。 あなたがエンキューをやっているときにmodにどこにありますか？ 頭だけのために[学生]。頭だけのために>>、正確に。 そして、なぜあなたは、エンキューでまったくmodにする必要がありますか？ あなたがMODする必要があるだろうという状況はいつですか？ あなたはスペースでものを持っている場合は、スペース1と2のように[学生] その後あなたは0から何かを追加する必要がありました。 [Hardison]ええ、その通りです。だからあなたのヘッドポインタは非常に最後にある場合は、 またはあなたのサイズに加えてあなたの頭が大きい場合、あるいはむしろ、キュー周りをラップしようとしている。 だから我々は今、スライドにここまで持っていること、このような状況で、 私は、今すぐ何かをキューに登録する場合 私たちは、インデックス0で何かをエンキューする。 だから、50がどこに行くかを見て、私はエンキュー50を呼び出す場合、 それは一番下にあり下がる。これは、インデックス0になります。 それは、すでにデキューされた 'こんにちは'を置き換えます。 [ダニエル]あなたがすでにデキューでの世話をしないでください？ なぜそれがエンキューで頭を使って何をするのでしょうか？ [Hardison]ああ、そうあなたが頭を変更していない、ごめんなさい。 しかし、あなたがアクセスしているときにmod演算子を使用する必要があります あなたがアクセスしているときにエンキューする要素 あなたのキュー内の次の要素。 [バジル]私はそれをしなかった、と私はそこに "成功"を得た。 [ダニエル]ああ、私は何を言ってるのか理解しています。 [Hardisonは]だからあなたはdidn't - あなただけq.sizeでやった？ [バジル]うん。私はちょうどに側面を変え、私の頭で何もしませんでした。 [Hardison]あなたが実際に何かあると頭をリセットする必要はありません、 しかし、文字列の配列に変換するときに、インデックス、 あなたは実際に、先に行くと、次の要素がどこにあるか計算する必要が スタックを小枝、あなたのスタック内の次の要素が常にあったので、 サイズに対応したインデックス位置にある。 我々は我々のスタックプッシュ機能に戻って見上げると、 我々は常に、インデックスのサイズで私たちの新しい要素を右にポンと置くことができます。 キューを持つのに対し、我々はそれを行うことはできません 我々はこのような状況にいる場合があるため、 我々は待ち行列に入れば、50私たちの新しい文字列には文字列[1]で右に行くだろう その我々が行うにはしたくない。 私たちは、新しい文字列のインデックスは0で行くようにしたい。 はい - 誰かいますか？ [学生]私は疑問を持っているが、それは本当に関係ないです。 誰かがちょうどpredはポインタのようなものを呼び出したときに、それはどういう意味ですか？ そのための短い名前は何ですか？私はそれだけで名前を知っている。 [Hardison] PREDポインタ？見てみましょう。どういう事情で？ [学生]は挿入のことだった。あなたが望むなら私は後でお聞きすることができます それは実際には関係ありませんが、私からといって - [Hardison]講義からDavidの挿入コードから？ 我々はそれをプルアップし、そのことについて話すことができます。 我々はその次の話だろう、一度我々は、リンクされたリストを取得する。 だから本当にすぐエンキュー関数がどのように見えるかを見てみましょう。 人々があなたのエンキュー行で実行しようとしました最初のことは何でしたか？このキューに？ あなたはスタックがプッシュするためにやったことに似ています。 あなたは何をしたのか、ステラ？ [ステラ、不明朗] [Hardison]その通りです。 （== CAPACITYをq.size）の場合 - 私は右の場所に私のブレースを配置する必要があります - falseを返します。 少し拡大します。オーケー。 今、私たちがしなければならなかった次の事は何ですか？ 単にスタックと同じように、適切な場所に挿入されます。 そして挿入する正しい場所はそう何でしたか？ スタックとそれはそれは非常に、というわけではないこれで、インデックスの大きさだった。 [ダニエル]私はq.head - またはしている - >> q.strings？ >>うん。 q.strings [q.head + q.size MOD容量]？ [Hardison]我々は、おそらくこれを囲むカッコを入れたい 私たちはみんなに適切な優先などのcleartを取得していること。 そして、それと等しく設定？ strに？>> strに。>>グレート。 そして今、我々がしなければならない最後のものは何ですか？ 我々はスタックに行ったように。 >>サイズをインクリメント？ >>サイズを増やします。 ブーム。その後、スターターコードは単にデフォルトでfalseが返されたため、 我々はすべてが通過するとすべてがうまくいけば、これをtrueに変更したい。 かしこまりました。それはセクションの情報がたくさんです。 我々は、かなりオーバーしていない。我々は、片方向リンクリストについて本当にすぐお話したいと思います。 私はこれを我慢しますので、後でそれに戻って行くことができます。 しかし、ここではより多くのちょうどいくつかのスライドのために私たちのプレゼンテーションに戻りましょう。 だから、エンキューがTODOですが、今、私たちはそれをやった。 今度は、一重リンクリストを見てみましょう。 私たちは、講義の中で、これらの少し話しました。 我々は人々を持っていた場所をどのようにあなたたちの多くはデモを見た ぎこちなくお互い保持番号を指す？ >>私はそれにあった。 >>君たちはどう思いましたか？うまくいけば、これらを少し分かりやすく説明することにしましたか？ リストでは、それは我々がノードを呼び出ししようとしているこのタイプを扱うことが判明した。 キューとスタックを持つのに対し、我々は、我々は、スタックでキューを呼び出したいという構造を持っていた 我々は、スタック型で、これらの新しいキューを持っていた ここにリストが本当にただのノードの束で構成されています。 文字列は文字のちょうど束されるのと同じ方法で、すべてが隣同士に並​​んでいた。 リンクリストは、ただのノードと他のノードと他のノードと他のノードである。 とむしろ一緒に、すべてのノードを壊して、近接してそれらを保存するよりも 右隣同士にメモリ内のすべての、 この次のポインタを持つことは、私たちがランダムに、どこのノードを格納することができます。 そして、ワイヤの種類は、それらすべてを一緒に1から次を指すように設定します。 そして、これはアレイ上に持っていたことの大きな利点は、何でしたか？ 格納するすべてのものの上に連続的にちょうど隣同士に立ち往生？ あなたは覚えていますか？うん？ >>動的メモリ割り当て？ どのような意味に絞っ動的メモリ割り当て？ あなたはそれが大きく、あなたの全体の配列を移動する必要はありません作り続けることができるという点で[学生]？ [Hardison]その通りです。だから、それの真ん中に新しい要素を入れたい配列を持つ、 あなたは、スペースを作るためにすべてのものをシフトする必要があります。 と同じように、我々は、キューとの話 我々はそのヘッドポインタを保つ理由だと、 我々は常に物事をシフトしていないようにします。 あなたが大きな配列を持っている場合、それは高価な取得するため、 そしてあなたは常にこれらのランダムな挿入をやっている。 リストを持つのに対し、あなたがしなければならないすべては、新しいノードにそれをスローで ポインタを調整し、作業は完了です。 何がこのことについて吸う？ それを除いては配列としてで動作するように簡単ではないという事実から？うん？ [ダニエル]まあ、私はそれがリンクされたリスト内の特定の要素にアクセスするためにはるかに困難だと思う？ [Hardison]あなたがちょうどあなたのリンクリストの途中で任意の要素にジャンプすることはできません。 どのようにして、代わりにそれをしなければならないのですか？あなたは全体のことをステップ実行する必要があります。>> [Hardison]うん。あなたは、一度に1つずつ、一つずつ通過する必要があります。 それは巨大だ - それは痛みです。 他のは何ですか - これまで別の没落はそこだ。 [バジル]あなたは前方と後方に行くことができないのですか？あなたは、一つの方向に行かなければならない？ [Hardison]うん。それでは、どのように我々は時々、それを解決するのですか？ [バジル]はリストを二重にリンクされた？まさに>>。二重リンクリストがあります。 もあります - 申し訳ありません？ [サム]がそのPREDものを使用するのと同じです - 私はちょうど思い出した、predは事は何のためであることではありませんか？ ことは、二重の間に、単独ではありませんか？ 彼がやっていたまさにで[Hardison]レッツ外観。 だからここに私達は行く。ここにリストコードがあります。 ここで我々はここで、predptrを持っています。あなたが話していたものですか？ だから、これはあった - 彼はリストを解放し、彼はそれへのポインタを格納しようとしている。 これは二重に、単一リンク·リストではありません。 このリストを解放することについて話しているので、我々は、後でこれについての詳細を話すことができる そして私は、最初のいくつかの他のものを見せたいと思います。 それだけだ - それはptrの値を覚えている [学生]ああ、それは先行するポインタですか？ >>うん。 我々は、その後predptrが何であるかを我々が自由前にptr自体を増やすことができますように。 我々は自由なptrが、その後、右のptr = ptrは次の呼び出しができないので？ それは悪いことだ。 だから、戻ってこの男に、見てみましょう。 リストについては、他の悪いことは、その配列を持つ一方である 我々だけで、自身が隣同士に積み重ねられたすべての要素を持っている ここで我々はまた、このポインタを導入しています。 だから我々は使用しなくしていること、メモリの追加チャンクはあり 私たちは私たちのリストに格納していることのすべての要素について。 我々は柔軟性を得るが、それにはコストがかかります。 それは、今回のコストが付属しています そしてそれはあまりにも、このメモリのコストが付属しています。 我々は今、配列内のすべての要素を通過する必要があるという意味での時間 インデックス10に1つずつ、またはその配列内のインデックス10だったでしょうを見つけることができます。 本当に素早く、ときに我々は図外にこれらのリストを、 一般的に我々は、リストの先頭またはリストの最初のポインタにしがみつく そしてこれが本当のポインタであることに注意してください。 それはちょうど4バイトです。それは実際のノード自体ではありません。 だから、それはそれでなくint型の値を持たず、次のポインタを持っていないことがわかります。 それは文字通りただのポインタだ。 これは、実際のノード構造体である何かを指すようになるだろう。 [SAM]ノードと呼ばれるポインタ？ >>これは - ない。これは、データ型ノードの何かへのポインタです。 これは、ノード構造体へのポインタです。 >>ああ、大丈夫。 左の図では、右側のコード。 我々は、開始するには良い方法ですnullに設定することができます。 ときにダイアグラムには、次のいずれかをnullとしてそれを書くか、またはあなたはそれを好きでそれを介して行を置く。 リストを操作するための最も簡単な方法の一つは、 そして我々は、両方のprependを行う尋ねると、2つの違いを見るためにアペンド しかし、先頭に追加は間違いなく簡単です。 あなたが前に付加するとき、あなたはこの事実はどこにある - あなたが前に付加したとき（7）、 あなたは、ノードの構造体を移動して、作成 そしてあなたは、我々はそれを前に付けているので、今ので、それを指すように最初に設定 それは、リストの先頭になるだろう。 我々の別のノードを作成しプリペンド（3）が、今3が7の前に来る場合。 だから我々は本質的に私達のリストの上に物事を推進している。 さて、あなたは、プリペンド、時には人々はそれがプッシュ呼び出すことがわかります あなたのリストに新しい要素をプッシュしているので。 それは、リストの先頭に削除することも簡単です。 だから人々はしばしば、そのポップアップを呼び出します。 そしてそのように、リンクされたリストを使用してスタックをエミュレートすることができます。 おっと。申し訳ありませんが、今、私たちは、appendに取得している。そこでここでは、（7）が付け、今、私たちは（3）を付けます。 （4）我々は、このリストの上に何か他のものを先頭に付加した場合、我々が前に付加した場合 その後、我々は4、次に3、その後7を持っていると思います。 それでは、私たちがポップして削除3、4を削除することができ、7を削除します。 多くの場合、これを考えるより直感​​的な方法は、appendを使うことです。 だから私はそれがここに追記してどのように見えるかを外に図解しました。 ここでは、添付の（7）何が違うのを見ていません リスト内の1つの要素だけが存在だからです。 と追加（3）終了時にそれを置きます。 たぶん、あなたは今のappendとのトリックを見ることができます それは、リストの先頭がどこにあるか私達が知っているだけですので、 あなたがリストを介してすべての道を歩かなければならないリストに追加する 、最後に取得を停止し、その後、ノードとポンと置くすべてのものを構築します。 すべてのものを配線します。 だからプリペンドと、我々としてはただ、本当に迅速にこれを介してリッピング あなたがリストに付加した場合、それはかなり簡単です。 あなたの新しいノードを作成し、いくつかの動的なメモリ割り当てを伴う。 そこでここでは、malloc（）を使用してノードの構造体を作っている。 それは後でのための私達のためのメモリを確保しますので、我々が使っているので、malloc関数 我々はこれをしたくないので - 私たちは、このメモリは長期間持続したいと思います。 そして、我々は我々だけで割り当てたメモリ内の領域へのポインタを取得します。 我々は、ノードのサイズを使用して、我々はフィールドを合計しないでください。 我々は、手動で、バイト数を生成しない 代わりに我々は、我々は適切なバイト数を取得している知っているようにsizeofを使用しています。 私たちは、malloc呼び出しが成功したことをテストしてください。 これは、一般的に何かやりたいことがあります。 最近のマシンでは、メモリが不足することは簡単だものではありません あなたはもののトンを割り当て、巨大なリストを作っている限り、 しかし、あなたは、iPhoneやAndroidのように、言う、のためのものを構築している場合、 あなたは強烈な何かをやっている場合は特に、限られたメモリリソースを持っている。 だから練習に入るために良いことだ。 ここで私はカップルの異なる機能を使用していることに注目してください あなたは、新しいの一種であることを見てきた。 だから、fprintfはprintfのようになっている。 その最初の引数を除いて、印刷したいストリームです。 この場合において、我々は標準エラー文字列に印刷したい これは、標準outstreamとは異なります。 デフォルトでは、同じ場所に表示されます。 また、端末に出力しますが、次のことができます - これらのコマンドを使用して、あなたについて、リダイレクト技術を学んだ あなたは問題セット4のトミーのビデオで学んだ、あなたはそれを指示することができます 異なる領域にしてから、終了して、プログラム、右ここで、終了します。 これは、mainから返っような本質的な ここでリターンは何もしませんので、我々は出口を使用することを除いて。 我々は、主にいないので、戻って、我々が望むようなプログラムは終了しません。 だから我々は、exit関数を使用して、それはエラーコードを与える。 その後、ここで我々は、iに等しくなるように新しいノードのvalueフィールドに、そのIフィールドを設定した後、我々はそれを配線。 我々は、最初に指すように新しいノードの次のポインタを設定 し、最初の時点で、新しいノードを指すようになります。 これらのコードの最初の行は、我々は実際に新しいノードを構築している。 この関数の最後の2行が、最初のものではない。 あなたが実際にヘルパー関数に、関数に引き出すことができます。 頻繁に私は何をすべきかということは、私は、関数にそれを抜く 私はそれをビルドノードのような何か、呼び出し そしてそれはかなり小さいプリペンド機能を保持し、それは、ちょうど3行です。 自分のビルドノード関数の呼び出しを行ってから、私のワイヤすべてをバックアップ。 私がお見せしたい最終的なもの、 と私は、あなたが自分で追加し、すべてのことをやらせるよ リストを反復処理する方法です。 リストを反復処理するためのさまざまな方法の束があります。 この場合において、我々はリストの長さを見つけるつもりだ。 だから我々は長さ= 0から始まります。 これは文字列のstrlenを書き込むと非常に似ています。 これは、私は右ここでは、このforループでは、お見せしたいものです。 それはちょっとファンキーに見える、それはいつものではないのint i = 0のときは、i <何でも、i + +は。 代わりに、それはリストの先頭になるように私たちの変数nを初期化している。 私たちのイテレータ変数がnullでないことをしながら、その後、我々は続ける。 慣例により、私達のリストの末尾にはnullになり、ためです。 そして、むしろ+ +を行うよりも、インクリメントする +のリンクリストに相当する+ N = N->隣にあります。 我々は時間がなくなっているので、私はあなたがここにギャップを埋めることができます。 あなたはspellrのpsetをに取り組むようにしかし、このことを覚えておいて。 リンクリスト、ハッシュテーブルを実装している場合、 間違いなく非常に便利になるだろう。 そして、物事をループするために、このイディオムを持つことは、うまくいけば、ずっと楽に生活していきます。 どの質問でも、迅速に？ [サム]あなたは完成したSLLとscを出すのでしょうか？ [Hardison]うん。私は完成したスライドを送り出すとsllスタックとqueue.csを完了します。 [CS50.TV]