>> [音楽再生]
>> DOUG LLOYD：OK、そうで もちろんこの点、
我々は、Cの基礎をたくさん紹介してきました 私たちは、変数、配列について多くのことを知っています
ポインタ、すべてが良いもの。
これらは、すべての種類の構築されています 基礎として参照するには、
しかし、我々は正しい、より多くを行うことができますか？
私たちは物事を組み合わせることができます 一緒に興味深い方法です。
>> そしてそれでは始めましょう、のはそれをやらせます Cは私たちを与えるもののうち分岐します、
私たち自身のデータを作成するために開始 これらの建物を利用した構造
一緒にブロックが何かをします 本当に、貴重な便利。
我々はこれを行うことができます一つの方法です コレクションについて話をします。
だから、これまでのところ、私たちはデータの種類を持っていました コレクションを表現するための構造
以下のような値の、類似した値。
それは、配列となります。
私たちは、整数のコレクションを持っている、または ように、文字のコレクションと。
>> 構造は、データの並べ替えです 情報を収集するための構造、
それは値のように収集するためではありません。
それは、通常、異なるデータ型を混合 一緒に単一のボックスの内側。
しかし、それは、それ自体ではありません 一緒にチェーンに使用
または一緒に類似の接続 配列のような項目、。
配列は最適です 要素は、ルックアップが、リコール
それは非常に難しいこと 配列に挿入します、
我々はに挿入していない限り、 その配列の最後。
>> そして、最高の例では、私が持っています そのために挿入ソートです。
あなたは私たちのビデオをリコールした場合 挿入ソートに、
たくさんのがありました 持つに関わる費用
要素をピックアップし、それらをシフトします 何かをフィットする方法のうち
あなたの配列の真ん中に。
配列は、別のに苦しみます 柔軟性のある問題、。
私たちは、配列を宣言すると、 我々はそれに1つのショットを取得。
私たちは、私が欲しい、と言ってもらいます この多くの要素。
それは、100かもしれないかもしれません それは、千場合がございます
xは、そのユーザ数であるxは プロンプトまたはコマンドで私たちを与えました
ライン。
>> しかし、私たちはそれだけで1ショットを取得、我々 その後、私は実際に、ああ言うために得ることはありません
101を必要とするか、私は、xプラス20を必要としていました。
遅すぎる、我々はすでに宣言しました アレイと、私たちは101以上を取得したい場合は、X
プラス20、我々は宣言する必要が 全く異なる配列、
配列のすべての要素をコピーします オーバーした後、我々は十分なを持っています。
そして、私たちは再び間違っている場合、どのような 私たちは実際に102、またはXプラス40を必要とする場合、
我々は再びこれをしなければなりません。
そこで、彼らは非常に融通の利きませんよ 我々のデータのサイズを変更するために、
私たちは一緒にいくつかを組み合わせた場合 我々はすでにきた基礎の
ポインタと構造について学び、 特に、動的メモリを使用します
malloc関数で割り当て、我々 一緒にこれらの作品を置くことができます
新しいデータstructure-- Aを作成します 我々はsay--かもしれない単独でリンクされたリスト
それは、私たちが成長することができますし、 値のコレクションを縮小
我々は、任意の無駄なスペースがありません。
>> だからもう一度、私たちはこのアイデアを呼び出し、 この概念、リンクされたリスト。
具体的には、このビデオでは、我々はしています 単独でリンクされたリストについて話して、
し、別のビデオでは、我々が話しましょう 約二重リンクリスト、これ
ここでテーマにだけバリエーションがあります。
しかし、単独でリンクされたリスト ノードから構成され、
単に抽象term--ているノード それはちょうど私が呼んでいるものです
それはのようなものです 構造は、基本的に、私はね？
ただnode--このそれを呼び出すに行きます ノードが二つの部材、または2つのフィールドがあります。
これは、通常、データを持ってい 整数、文字フロート、
またはいくつかの他のデータ型とすることができます あなたがタイプのデフで定義されたこと。
そして、それはへのポインタが含まれています 同じタイプの別のノード。
>> だから我々は、内部の二つのことを持っています このノード、データおよびポインタ
別のノードに。
そして、あなたが視覚化するために開始した場合 これは、あなたはそれについて考えることができます
そのノードのチェーンのような 互いに接続されています。
私たちは、それを最初のノードを持っています データ、およびポインタが含まれています
含まれている第2のノードに データ、および第3のノードへのポインタ。
そしてそうそれは我々がそれを呼び出す理由です リンクされたリストは、それらが一緒にリンクされています。
>> この特別に何 ノード構造のように見えますか？
さて、あなたは上の私達のビデオからリコール場合 式デフと、カスタムタイプを定義します、
我々はstructure--を定義することができますし、 このような構造を定義する入力します。
構造体sllist tyepdef、その後、私は 任意に、ここでワード値を使用して
実際には任意のデータタイプを示します。
あなたは、整数または浮動小数点数に渡すことができます あなたが好きな可能性があります。
それはちょうどに限定されていません 整数、またはそのような何か。
だから、値は単に任意です その後、データ・タイプ、およびポインタ
同じタイプの別のノードに。
>> さて、少しキャッチがあります ここで構造を定義すると
とき、それは自己参照構造です。
私は一時的なを持っている必要があります 私の構造の名前。
日Iの終わりに 明らかにそれを呼び出したいです
SLLノードは、それが最終的に新機能 私のタイプ定義の一部に名前を付け、
私はSLLノードを使用することはできません これの真ん中インチ
理由が、私はそうではありません SLLノードと呼ばれるタイプの作成
私はここで、この最後の点を打つまで。
それまで、私が持っている必要があります このデータ型を参照する別の方法。
>> そして、これは自己であります 参照データ型。
これは、のデータ型をよ データを含む構造体、
別のポインタ 同じタイプの構造。
だから私はを参照できるようにする必要があります このデータタイプは、少なくとも一時的に、
そのために一時的に与えます 構造体sllistの名前
私は、私がしたいと言うことができます 別の構造体へのポインタsllist、
構造体sllistスター、その後、 私は定義を完了した後、
私は今、このタイプSLLノード呼び出すことができます。
>> あなたがあります参照してくださいだから、なぜです ここでは一時的な名前、
しかし、ここで永続的な名前。
時々、あなたが見るかもしれません 構造体の定義は、
例えば、それはありません その自己参照、
ここで指定の名前があ​​りません。
それはちょうど、typedefは構造体を言います 中かっこを開き、それを定義します。
あなたがしている場合でも、構造体は、自己があります これは、そのまま、参考
次のように指定する必要があります 一時的な型名。
しかし、最終的には、今 我々はこれをやったことを、
私たちはを参照することができます これらのノードは、これらのユニット、
目的のためのSLLノードとして このビデオの残りの部分。
>> すべての権利、私たちはどのように知っています リンクリストのノードを作成します。
私たちは、定義する方法を知っています 連結リストノード。
今、私たちを開始するつもりなら 情報を収集するためにそれらを使用して、
操作のカップルは、私たちがあります 理解して作業する必要があります。
私たちは、作成する方法を知っておく必要があります 薄い空気のうちにリンクされたリスト。
何のリストが既にがない場合、 我々は、いずれかを開始します。
だから我々はできるようにする必要があります リンクリストを作成するには、
我々は、おそらく検索する必要があります リンクリストを介して、
我々が探している要素を検索します。
我々が挿入できるようにする必要があります リストに新しいもの、
私たちは私たちのリストが成長できるようにしたいです。
そして同様に、我々はできるようにしたいです 私たちのリストから物事を削除するには、
私たちは私たちのリストを縮小できるようにしたいです。
そして、私たちの終わりに 特にプログラム、
あなたは私たちがいることを思い出した場合 動的にメモリを割り当てます
一般的にこれらのリストを構築するために、 我々はそのすべてのメモリを解放したいです
私たちは、それを扱う完了したら。
そして、私たちは、削除できるようにする必要があります 急襲の失敗1で全体のリンクリスト。
それでは、通さ これらの操作の一部
私たちはそれらを視覚化する方法、 特に擬似コードコードで話し。
だから我々は、作成したいです リストをリンクするので、多分私達
関数を定義します このプロトタイプを持ちます。
SLLノード星、作成し、私が渡しています 1引数に、いくつかの任意のデータ
いくつかの任意のデータ型で、もう一度入力します。
しかし、私は、この関数をする必要がありますreturning--よ 単独に、私へのポインタを返します
連結リストノード。
ここでも、作成しようとしています 薄い空気のうちリンクリスト、
私はへのポインタを必要とします 私が行っている、そのリスト。
>> だからここに必要な手順は何ですか？
まあ、私は最初のものです 何をするつもりは、動的です
新しいノード用の領域​​を割り当てます。
繰り返しますが、我々は薄いからそれを作成しています 空気ので、我々はそれのためのmallocスペースにする必要があります。
そしてもちろん、すぐに 私たちはをmallocした後、
我々は常にことを確認するためにチェックする私たちの pointer--我々は戻ってnullを取得できませんでした。
そのため、私たちがしようとする場合 NULLポインタを服従、
我々は苦しむことになるだろう セグメンテーションフォールトと我々はそれを望んでいません。
>> その後、我々は、フィールドに入力したい場合は、 我々は、値フィールドを初期化します
そして、次のフィールドを初期化します。
そして、我々は最終的にはto--たい 私たちが望むindicates--関数プロトタイプ
SLLノードへのポインタを返します。
それでは、これは視覚的のように見えるように？
さて、最初に我々は、動的にするつもりです 新しいSLLノード用の領域​​を割り当てます、
私たちはそれはですmalloc-- 視覚的に表現
先ほど作成したノードの。
そして、我々は確認してください それは、この場合にはnull--いません
画像は持っていません それがnullの場合、最大示し、
我々は、メモリが不足しているだろう 私たちはそこに行ってもいいです。
だから今、私たちは、ステップCににしています ノードの値フィールドを初期化します。
さて、この関数に基づいて 私はここで使用している呼び出し、
私は6に渡したいように見えます、 私はvalueフィールドの6はよ。
さて、次のフィールドを初期化します。
さて、どのような私はそこにするつもりです、 次のものは、右、ありません
これは、リスト内の唯一のものです。
だから、リストの次の事は何ですか？
>> それは右、何を指してはなりません。
そこに他には何もいないので、何であります 私たちはそのことを知っている概念がnothing--です
何へのポインタ？
それは多分私達が望むでなければなりません そこにNULLポインタを置くために、
私はヌルを表します ちょうど赤いボックスのようなポインタ、
我々は先に進むことはできません。
我々は少し後でわかるように、 我々は最終的にチェーンを持っています
結ぶ矢印の 一緒にこれらのノード、
しかし、あなたが打ったとき ヌルだ赤いボックス、
我々は、先に進むことはできません それは、リストの最後です。
>> そして最後に、私たちはしたいです このノードへのポインタを返します。
だから我々は新しいそれを呼ぶことにします、 そして、新しいが返されます
それは、で使用することができ どんな機能がそれを作成しました。
だから私達は行く、私達は単独で作成しました 薄い空気のうち連結リストノード、
そして今、我々は我々が働くことができるリストがあります。
>> さて、すでに私たちをしましょう 大きな鎖を有し、
我々はそれで何かを見つけたいです。
そして、我々は起こっている機能が欲しいです 応じて、trueまたはfalseを返します
値がそのリストに存在するかどうか。
関数プロトタイプ、または その関数の宣言、
見つけるBOOL this--のように見える、と可能性があります その後、我々は二つの引数を渡したいです。
>> 最初は、へのポインタです リンクされたリストの最初の要素。
これは実際にあなたがよものです いつものトラックを維持したいです、
そして実際に何かあるかもしれません あなたも、グローバル変数に入れました。
あなたがリストを作成したら、 いつもいつもあなた、
非常のトラックを維持したいです リストの最初の要素。
あなたが他のすべてを参照することができますその方法 ちょうどチェーンに従うことによって要素、
ポインタを維持することなく、 一つ一つの要素にそのまま。
あなただけの最初のトラックを保持する必要があります 1これらはすべて一緒に連鎖している場合。
>> そして、二つ目 我々は再びで渡しています
任意ですsome-- どのようなデータ型我々がいます
そこを探しているの内側にあります うまくいけば、リスト内のノードの一つ。
だから手順は何ですか？
さて、まず最初にすることです 私たちは、横方向のポインタを作成します
リストの先頭を指しています。
さて、なぜ我々はすでに我々、ということをしていますか リストの先頭にポインタを持っています、
なぜ私たちは周りのその1を移動しませんか？
まあ、私は言ったように、 それは私たちにとって本当に重要です
いつものトラックを維持します リスト内の非常に最初の要素。
そしてそれは実際には良いです その複製を作成するには、
そして、私たちを決して動き回るないためにそれを使用 誤って私たちは常に離れて移動したり、
あるいくつかの点でポインタを持っています 右側のリストの最初の要素に。
だから、作成する方が良いでしょう 私たちが移動するために使用する第1。
>> その後、我々はちょうどかどうかを比較します そのノードでの値フィールド
我々が探しているものであり、それはだ場合 ない、私たちは次のノードに移動します。
そして、我々はそれをやり続けます オーバー、およびオーバー、およびオーバー、
我々は、いずれかを見つけるまで 要素、あるいは我々ヒット
null--我々は最後に到達しました リストのそれはありません。
これがうまくいけば、ベルを鳴らす必要があります ちょうどリニアサーチなどのあなたに、
私達はちょうどそれを複製しています 単独でリンクされたリスト構造
代わりにそれを行うには、配列を使用します。
>> だからここの例を示します。 単独でリンクされたリスト。
この1の構成は 5つのノード、我々は持っています
の先頭へのポインタ リストと呼ばれるリスト。
私たちがやりたい最初のものです 再び、そのトラバースポインタを作成します。
つまり、2つのポインタを持っています 同じことをポイント。
>> さて、ここにも気づく、私はしませんでした TRAVのための任意の領域ををmallocする必要があります。
私はTRAVはmalloc関数に等しいと言っていませんでした 何かが、そのノードが既に存在して
メモリ内のそのスペースはすでに存在しています。
だから私は実際にやっているすべてがあります それへの別のポインタを作成します。
私は、追加のmallocingありませんよ スペース、ちょうど今二つのポインタを持っています
同じことを指しています。
>> だから2は私が探しているのですか？
まあ、ないので、代わりに私は 次のいずれかに移動しよう。
だから基本的に私は言うだろう、 TRAVは、次のTRAVに等しいです。
いいえ、私が探しているものを3です。
だから私は行き続けます 最終的になるまで
私が探しているものである6を取得 関数呼び出しをもとにしています
私が一番上に持っています そこに、と私は終わりです。
>> 私は今、どのような場合、要素 探して、リストに表示されていません
それはまだ仕事に行くのですか？
まあ、そのリストに気付きます ここでは、微妙に異なっています
これは別のものであるのです リンクリストとの重要な、
あなたが保存する必要はありません 特定の順序でそれら。
あなたがしたい場合は、することができますが、 すでにお気づきかもしれません
私たちはを追跡していないこと 私たちはどのような数の要素をです。
>> そして、それは、我々1取引の一種です アレイの詩リンクリストを持っています、
それは我々が持っていないです もはやランダムアクセス。
私達はちょうど私が欲しい、と言うことはできません 0番目の要素に移動するには、
または私の配列の6番目の要素、 これは私が配列に行うことができます。
私は私がに行きたいと言うことはできません 0番目の要素、または第六の要素、
または私のリンクリストの25の要素、 それらに関連付けられているインデックスがありません。
そしてそれは本当に問題ではありません。 私たちは順番に私たちのリストを保存する場合。
あなたがしたい場合は 確かにすることができますが、あります
彼らがする必要がない理由ありません 任意の順序で保存されます。
だからもう一度、試してみましょうと このリストに6を見つけます。
まあ、我々はで開始 始めに、我々は、6が見つかりません
し、我々は見つけることはない続けます 6、私たちは最終的にここに到達するまで。
ノードへのだから今TRAVポイント 8を含む、6がそこにはありません。
>> だから、次のステップは次のようになります 次のポインタに移動するには、
そうTRAVは、次のTRAVに等しいと言います。
で示さまあ、TRAV次、 そこに赤いボックスは、nullです。
だからに他のどこにもあります 行くので、この時点で
我々は達したと結論付けることができます リンクリストの最後に、
および図6は、そこにはありません。
そして、それが返されます この場合にはfalse。
>> [OK]を、どのように我々は新しいを挿入します リンクリストにノード？
だから我々は、作成することができました どこからともなくリンクリスト、
しかし、我々はおそらくしたいです チェーンを構築していません
別個のリストの束を作成します。
私たちは、1つのリストを持ってしたいこと その内のノードの束を持って、
単一ノードでのリストの束ではありません。
だから我々はちょうど作成を使用して維持することはできません 我々は今、先に定義した関数
挿入します すでに存在するリスト。
>> したがって、この場合、我々はつもりです 二つの引数を渡すために、
その先頭へのポインタ 我々はに追加するリンクリスト。
繰り返しますが、それはそれはそうだ理由です 重要なこと、我々は常に
ので、それを追跡します それは、私たちは本当に唯一の方法です
全リストを参照する必要がありさ ちょうど最初の要素へのポインタで。
だから我々はに渡したいです その最初の要素へのポインタ、
そしてどのような値私たち リストに追加します。
そして、最終的にはこの機能 ポインタを返すために起こっています
連結リストの新しいヘッドに。
>> ここに含まれるステップは何ですか？
まあ、ちょうど作成と同様に、 我々は、動的に割り当てる必要があります
新しいノードのためのスペース、およびことを確認してください 我々は再び、メモリが不足していないことを確認、
我々はmalloc関数を使用しているため。
その後、我々は移入したいです ノードを挿入し、
そう番号を入れて、どんな valがノードに、あります。
私達はでノードを挿入します リンクリストの先頭。
>> 私は理由があります それはこれをしたい、と
第二を取る価値があるかもしれません ここにビデオを一時停止するには、
私はしたい理由を考えます リンクの先頭に挿入します
リスト。
繰り返しますが、私は先に述べました それは実際にないこと
私たちはいずれかでそれを維持する場合の問題 順序は、ので、多分それが手がかりです。
そして、あなたは私たちがどうなるかを見 to--たかっまたはちょうど二から
前ときに我々が行っていました 検索を通してあなた
何を見ることができるかもしれません 我々がしようとしていた場合に発生
リストの末尾に挿入します。
我々は持っていないので リストの最後へのポインタ。
>> だから理由は、私が望むこと 先頭に挿入します、
私はすぐにそれを行うことができるためです。
私が先頭にポインタを持っており、 我々は、第二​​に、視覚的にこれが表示されます。
しかし、私は最後に挿入する場合、 私が最初に開始する必要があり、
へのすべての道を横断します 終了してから、それをタック。
だから、それを意味します リストの最後に挿入します
n個のOになります 操作は、戻って
私たちの議論に 計算の複雑さ。
これは、n個の動作のOになるだろう リストが大きく、そして大きくなったように、
そして大きな、それがよりになるだろうと 何かを付け加えることがより困難
最後に上。
しかし、それは常にには本当に簡単です 最初に上の何かをタック、
あなたは初めに常にしています。
>> そして、我々は再びこれを視覚的に表示されます。
そして、我々はかつて、終わったら 私たちは、新しいノードを挿入しました、
私たちは私たちへのポインタを返すようにしたいです 連結リストの新しいヘッド、どの
我々はに挿入しているので、 始め、実際になります
私たちが作成したノードへのポインタ。
それでは、これを視覚化してみましょう、 ので、私はそれに役立つと思います。
>> だからここに私たちのリストだ、それはで構成されてい 4つの要素が、ノードは、15を含みます
どのノードを指します 9を含む、どの
13を含むノードを指し、 含むノードを指しています
ヌルを持っている10、 その次のポインタとしてポインタ
そのためには、リストの最後です。
だから我々は、挿入したいです 値12を使用して新しいノード
この初めに リスト、我々は何をしていますか？
さて、最初に我々はのためのスペースををmalloc ノード、その後、我々はそこに12を置きます。
>> だから今我々が達しました 決定ポイント、右？
我々は、いくつかあります ポインタ、我々は可能性が
一つは、我々が最初に移動する必要がある、移動？
私たちは12点までを行う必要があります list--の新しいヘッド
または恐れ入りますが、我々は12をしなければなりません リストの古い頭にポイント？
それともと言うべきです リストには、12から始まります。
区別があります そこに、私たちは見てみましょう
第二の両方のと何が起こるかで。
>> しかし、これはにつながります サイドバーのための大きいトピック、
の一つがあります リンクリストとトリッキーなもの
ポインタを配置することです 正しい順序です。
あなたが順不同で物事を移動した場合、 あなたが誤って終わることができ
リストの残りの部分を孤立。
そして、ここではその一例です。
それでは、アイデアを手放しますof-- よく、私達はちょうど12を作成しました。
私たちは12になるだろう知っています リストの新しいヘッド、
そしてなぜ私達はちょうど移動しません リストポインタが指すように設定します。
>> [OK]を、ので、それは良いことです。
だから今どこに12次のポイントはいますか？
私は視覚的に私たちが見ることができる、意味します それが15を指すようになりますことを、
人間として、それは私たちには本当に明らかです。
どのようにコンピュータが知っているのですか？
私たちは何も持っていません もう15を指し、右？
>> 私たちは、15を参照する任意の能力を失ってしまいました。
私たちは、新しい矢印次の等号を言うことはできません 何かが、そこには何もありません。
実際には、我々は孤立しました リストの残り
そうすることによって、我々はしました 誤ってチェーンを破壊しました。
そして、我々は確かにそれを行うにはしたくありません。
>> それでは、戻って再びこれを試してみましょう。
たぶん正しいことを行うには 12の次のポインタを設定することです
最初のリストの古い頭に、 その後、我々はリストの上に移動することができます。
実際には、すなわち 正しい順序、我々
私たちがしている際に従わなければなりません 単独でリンクされたリストでの作業。
我々は常に接続したいです リストに新しい要素、
我々は、のようなものを取る前に、 変化の重要なステップ
どこにリンクされたリストの先頭です。
繰り返しますが、それはそのような基本的なことです、 我々はそれのトラックを失いたくありません。
>> だから我々はそれを確認します すべてが一緒に連鎖しています、
我々はそのポインタを移動する前に。
そして、これは正しい順序であろうが、 これは、リストに12を接続することです、
そのリストは12を起動することを言います。
我々が言った場合、リストには、12から始まり、 その後、リストに12を接続しようとしました
我々はすでに何が起こるか見てきました。
我々は誤ってリストを失います。
>> [OK]を、について話をするので、もう一つ。
私たちはを取り除くしたい場合は 全体を一度リンクリスト？
繰り返しますが、私たちはmallocingしています すべてこのスペース、およびので、
我々が完了したら、それを解放する必要があります。
だから今、私たちは、削除したいです 全体のリンクリスト。
さて、私たちは何をしたいですか？
>> 私たちは、NULLポインタに達した場合は、我々 それ以外の場合は、停止したい、ただ削除
そのリストの残りの部分とは、私を解放します。
リストの残りの部分を削除し、 して、現在のノードを解放します。
以下のようなその音は何、 どんな技術我々が話をしています
以前のようなその音していますか？
その後、他のみんなを削除 戻ってきて、私を削除します。
>> それは再帰だ、私たちが作りました 少し小さい問題、
私たちは皆を削除すると言っています 他に、あなたは私を削除することができます。
さらに道を、そのノード 他のみんなを削除、と言うだろう。
しかし、最終的に我々はに取得します リストがnullである点、
それが私たちのベースケースです。
>> それでは、これを見てみましょう、 これはうまくいくかもしれませんか。
だからここに私たちのリストだ、それは同じです 私たちは話していたリスト、
そして、手順があります。
テキストの多くは、ここにありますが、 うまくいけば、可視化が役立ちます。
>> だから我々はhave--と私も引き込ま 私たちのスタックフレームのイラストアップ
コー​​ルスタック上の私たちのビデオから、 うまくいけば、このすべての
一緒に何が起こっているかを紹介します。
だからここに私達の擬似コードコードです。
我々はNULLに達した場合 ポインタが、そうでない場合、停止します
リストの残りの部分を削除し、 その後、現在のノードを解放します。
だから今、list-- 私たちがしているポインタ
12にポイントを破壊することで渡します。
図12は、NULLポインタでないので、我々はしています リストの残りの部分を削除しようとして。
>> 何が削除されます 私たちの残りの部分は、関係しますか？
まあ、それは作る意味します 言って、破壊するために呼び出します
15ということの始まりです 私たちが破壊するリストの残りの部分。
だから呼び出しが破壊します 12は、種類の保留になっています。
それを待って、そこに凍結しています その仕事を終えるために、15を破壊するために呼び出します。
>> さて、図15は、NULLポインタではなく、 それは、すべての権利を言うために起こっています
よく、リストの残りの部分を削除します。
リストの残りが開始 9であり、私たちはちょうどよ
あなたはすべてのことを削除するまで待ちます もの、その後戻ってきて、私を削除します。
まあ9まあ、言うために起こっています、 私は、NULLポインタではありませんよ
ので、ここから残りにリストを削除します。
だから試してみて、13を破壊します。
13は、私がNULLポインタではないよ、と言います 同じことは、それがバックに渡します。
10は、10 NULLポインタではありません NULLポインタが含まれています、
しかし10は、それ自体ではありません 今NULLポインタ、
そしてそれはあまりにもバックを渡します。
>> そして今、そこにポイントを一覧表示 本当にsome--を指します
私は、画像内のより多くのスペースがあった場合、 それはいくつかのランダムな空間を指します
我々はそれが何であるかを知らないことを。
それは、しかしリストNULLポインタです 文字通り、今ではNULL値です設定されています。
それは、その赤いボックス内を右向いています。
私たちはそのように、NULLポインタに達しました 私たちは停止することができ、我々は完了です。
>> そしてその結果、紫色のフレームがでnow--です アクティブなフレームですstack--の上、
それが行われています。
我々はNULLポインタに達した場合は、停止します。
我々は、我々が何もしません nullポインタを解放することはできません、
我々は、いずれかををmallocしませんでした スペースは、と私たちは完了です。
だから、関数フレーム 破壊され、私たちさ
我々は左のどこが拾いますresume-- 次に高い1、でオフします
このダークブルーフレームはこちらです。
だから我々は我々がオフに左、右を拾います。
我々は残りの削除しました すでにリスト、今私たちがしています
現在のノードを解放するつもり。
だから今、私たちは今、このノードを解放し、することができます 我々は、関数の最後に達しました。
だから、その関数のフレームが破壊され、 我々は水色1で拾います。
>> だから、私はすでにdone--ましsays-- そう、リストの残りの部分を削除します
現在のノードを解放します。
そして今、黄色の枠があります バックスタックの一番上に。
あなたが見るようにそしてそう、私たちは今です 右から左にリストを破壊します。
>> 何が、しかし、起こっているだろう 私たちは物事を間違った方向に行っていた場合はどうなりますか？
ちょうど私たちがしようとしたときのような 要素を追加します。
我々は、チェーンを台無しにした場合、もし 我々はポインタを接続しませんでした
正しい順序で、私たちの場合 ただ最初の要素を解放し、
私達はちょうど解放された場合 リストの先頭、今
を参照する方法がありません リストの残り。
そして、私たちは持っているだろう 孤立したすべてのもの、
我々は何を持っていただろう メモリリークと呼ばれます。
あなたは私達のビデオからリコールした場合 動的メモリ割り当てに、
それは非常に良いことではありません。
>> だから私はそこに、言ったように いくつかの操作されています
私たちは仕事に使用する必要があること 効果的にリンクされたリストを持ちます。
そして、あなたは、私は1つを省略して気づいたかもしれません リンクから単一の要素を削除します
リスト。
私がやったことを理由 それは実際に一種のだです
削除する方法を考えるためにトリッキー 単独での単一の要素
リンクリスト。
私たちは、スキップできるようにする必要があります リストに何か、どの
我々はpoint--たちに到達することを意味 このnode--を削除したいです
しかし、私たちがそれを作るために、 すべての情報を失うことはありません、
我々はこれを接続する必要があります こっちノード、ここに。
>> だから私はおそらく間違っているをしました 視覚的な観点から。
だから私たちは私たちの最初にしています リストには、我々は、を介して進行しています
私たちは、このノードを削除したいです。
我々はそれを削除した場合、 私たちは、チェーンが壊れました。
右ここでこのノード 他のすべてを意味し、
それがここに上からチェーンが含まれています。
>> だから我々は実際に何をする必要がありますか 我々はこの点に到達した後、
我々は1つ前のステップに必要であり、 このノードにこのノードを介して接続、
私たちはその後、削除することができます 真ん中の1。
しかし、単独でリンクされたリストにはありません 私たちの後方に移動するための方法を提供します。
だから我々はどちらか維持する必要があります 二つのポインタ、およびそれらを移動
オフステップの一種、前後に 私達は行く、またはポイントに到達するように、他の
そして、その後を介して他のポインタを送信します。
そして、あなたは、それを見ることができるように 少し厄介を得ることができます。
幸いなことに、私たちは持っています それを解決する別の方法、
我々は、二重リンクリストについて話すとき。
>> 私はダグロイドだけど、これはCS50です。