DOUG LLOYD：だからCS50に、私たちは紹介してきました 異なるデータ構造の多くは、
右？
私たちは、配列を見て、とリンクしました リスト、ハッシュテーブル、
そして、しようと、スタックとキュー。
また、少し学びます 木とヒープについて、
しかし、実際にはこれらすべてが終わります アップテーマの変化です。
実際にこれらがあります。 四つの基本的な考え方の種類
他のそのすべてがに煮詰めることができます。
アレイ、リンクリスト、 ハッシュテーブル、および試行。
など私は、言いました それらのバリエーションがあり、
しかし、これはかなりあります 多くの要約に行きます
すべては我々が話をするつもりです Cの点では、このクラスでは約
>> しかし、どのように右、これらすべての措置を行いますか？
我々は、長所と短所について説明しました それらの独立したビデオでそれぞれ、
しかし、数字の多くがあります 周りの投げ。
一般の多くがあります 思考は周りの投げ。
試してみましょうとの統合 それだけで一つの場所に。
それでは、反対長所を比較検討してみましょう 短所、および検討
そのデータ構造 正しいデータであるかもしれません
あなたの特定の状況のた​​めの構造、 あなたが保存しているデータの任意の種類。
あなたは、必ずしもする必要はありません 超高速の挿入、削除を使用して、
トライのルックアップよろしければ本当に 挿入および削除を気にしません
過度に。
あなただけの迅速ランダム必要がある場合 アクセスは、多分、配列が良いです。
それでは、それを蒸留してみましょう。
のは、4つのそれぞれについてお話しましょう データ構造の主な種類
我々はについて話したこと、および 彼らは良いかもしれないときだけ参照してください。
そして、するとき、彼らはとても良いではないかもしれません。
それでは、配列から始めましょう。
だから挿入、それは一種の悪いです。
>> 配列の最後に挿入はOKですが、 私たちが行くように、私たちは、アレイを構築している場合。
しかし、我々は挿入する必要がある場合 中央に要素、
挿入に戻って考えます ソート、たくさんあり​​ます
そこに要素に合わせてシフトします。
そして、私たちは挿入​​しようとしている場合 どこにもなく、配列の終わり、
それはおそらくそれほど大きくはありません。
>> 我々がない限り同様に、削除、 配列の末尾から削除します、
おそらくそうであれば素晴らしいではありません 私たちは、空のギャップを残してしたく​​ありません、
これは通常は行っておりません。
私たちは、要素を削除すると、 その後、ソートのもう一度ぴったり作ります。
だからから要素を削除します 配列も、それほど大きくありません。
>> ルックアップは、しかし、素晴らしいです。
我々は、ランダムアクセスを持っています、 一定時間のルックアップ。
私達はちょうど7言うと、私達は行きます ・アレイ再配置7へ。
私たちは、に行くと、20言います ・アレイ再配置20。
私たちは、全体で反復処理する必要はありません。
これはかなり良いです。
>> アレイはまた、ソートすることが比較的容易です。
私たちは、ソートの話をするたびに このような選択ソートアルゴリズムとして、
挿入ソート、バブルソート、マージ ソート、我々は常にそれを行うために配列を使用し、
アレイは、に非常に簡単であるため、 データ構造への相対的なソート、
我々はこれまでに見てきました。
>> 彼らはまた、比較的小さいです。
余分なスペースがたくさんあり​​ません。
あなたは正確に同じくらい取っておきます あなたのデータを保持する必要があるとして、
それはかなりそれです。
そこで、彼らは非常に小さいです その方法で効率的。
しかし、別の欠点は、しかし、 それらのサイズが固定されていることです。
私たちは、正確にどのように宣言する必要が 大きな我々の配列になりたいです、
私たちはそれだけで1ショットを取得。
私たちは成長し、それを圧縮することはできません。
>> 我々はそれを拡大または縮小する必要がある場合は、我々 全く新しい配列を宣言する必要があり、
コピーのすべての要素 二番目の配列に最初の配列。
そして、我々はそれを誤算場合 時間は、我々は再びそれを行う必要があります。
それほど大きくありません。
だから、配列は、私たちに柔軟性を与えていません 要素の可変数を持っています。
>> リンクされたリストで、 挿入は非常に簡単です。
私達はちょうど前面にタック。
削除も非常に簡単です。
私たちは、要素を見つける必要があります。
それはいくつかの検索を伴います。
>> しかし、あなたは要素を見つけたら あなたが行う必要があり、すべてを探しています
ポインタを変更され、 おそらく2あなたが持っている場合
二重list--リンク リンクリスト、rather--
して、あなただけのノードを解放することができます。
あなたがシフトする必要はありません 周りのすべて。
あなたはちょうど2つのポインタを変更し、 そのためには、かなり速いです。
>> ルックアップは、右の、しかし悪いのですか？
私たちが発見するためには リンクされたリスト内の要素、
単独で、または二重にリンクするかどうか、 我々はそれを検索する線形する必要があります。
私たちは最初から開始する必要がありますし、 最後に移動したり、端移動で開始
先頭に。
私たちはもうランダムアクセスすることはできません。
だから我々がやっている場合 検索の多くは、多分
リンクされたリストではありません 私たちにとってそれほど良いです。
>> 彼らは本当にもしています 並べ替えするのが難しいですよね？
あなたができる唯一の​​方法 本当にリンクされたリストを並べ替えます
あなたがそれを構築するとして、それを並べ替えることです。
しかし、あなたは、あなたのようにそれを並べ替える場合 それを構築し、あなたはもはやじゃないんです
もはや迅速な挿入を行います。
あなただけのタッキングしていません 前面に物事。
あなたが見つけなければなりません それを置くために適切な場所、
そして、あなたの挿入 ちょうど約として悪くなります
配列に挿入など。
だから、リンクされたリストではありません データをソートするように素晴らしいです。
>> 彼らはまた、かなり小さなサイズワイズです。
わずか二重リンクリスト 単独でリンクされたリストよりも大きく、
これはわずかに大きいです アレイよりも、しかし、そうではありません
無駄なスペースの膨大な量。
もしそうであればスペースが限られているが、 本当に強烈なプレミアム、
これは移動するための正しい方法かもしれません。
>> ハッシュテーブル。
ハッシュテーブルへの挿入 非常に簡単です。
それは、2段階のプロセスです。
まず、を通して私たちのデータを実行する必要があります ハッシュコードを取得するためのハッシュ関数
し、我々はに要素を挿入 そのハッシュコードの位置にハッシュテーブル。
>> リンクされたリストに似て削除、 あなたは要素を見つけたら簡単です。
あなたは、まずそれを見つけなければなりません しかし、あなたはそれを削除すると、
あなただけ交換する必要があります ポインタのカップル、
あなたは、別のチェーンを使用している場合。
あなたはプロービング使用している場合、 あるいはあなたがいないのであれば
使用して、すべての連鎖 あなたのハッシュテーブルで、
削除は、実際には本当に簡単です。
すべてを行う必要があるハッシュです データは、その場所に移動します。
そして、あなたがいないと仮定すると 任意の衝突を持っています、
あなたは非常に迅速に削除できるようになります。
>> さて、ルックアップはどこのものです 少し複雑になります。
それは、より良い平均です リンクされたリストより。
あなたはチェーンを使用している場合は、 あなたはまだリンクされたリストを持っています、
これはあなたがまだ持っていることを意味 検索は、リンクリストを損ないます。
あなたが取っているので、しかし、あなたのリンク リストおよび100または1,000以上、それを分割
あるいはnあなたのハッシュテーブルの要素、あなたがしています リンクされたリストは、すべてのサイズのn番目の一つです。
彼らはすべて実質的に小さいです。
あなたは、nの代わりにリストをリンクしています サイズnの1リンクリストの。
>> そしてそうこの現実世界の定数 一般的に、我々の要因、
時間計算では約話をしない、それを ここで実際に違いを生むん。
だから、ルックアップはまだ線形であります あなたがチェーンを使用している場合、検索、
しかし、リストの長さ あなたはを通して検索しています
比較して、非常に、非常に短いです。
繰り返しますが、ソートはあなたのである場合 ここでの目標、ハッシュテーブルの
おそらく正しい方法は行きません。
並べ替えた場合だけで配列を使用 あなたには本当に重要です。
>> そして、彼らはサイズの域を実行することができます。
これは、かどうかを言うのは難しいです ハッシュテーブルは、小さいまたは大きいです
それは実際に依存しているため どのように大きなあなたのハッシュテーブルです。
あなただけ保存するつもりなら あなたのハッシュテーブルの5つの要素、
あなたはハッシュテーブルを持っています それ10,000の要素を持ちます、
あなたは、おそらく多くのスペースを無駄にしています。
あなたもすることができますされてコントラスト 非常にコンパクトなハッシュテーブルを持っています、
しかし、小さいあなたのハッシュテーブルは、取得します これらのリンクされたリストの各長いです
取得します。
だから本当に定義する方法はありません 正確にハッシュテーブルのサイズ、
しかし、それはおそらく安全です それは一般的だと言って
リンクさよりも大きいことになるだろう 同じデータを格納するリスト、
トライよりも小さいです。
>> そして、試行は、第四です これらの構造の
私たちは話してきたこと。
トライに挿入することは複雑です。
ダイナミックがたくさんあり​​ます メモリ割り当て、
特に初めに、 あなたが構築するために始めているよう。
しかし、それは一定の時間です。
それは人間だけの要素です ここではトリッキーになること。
NULLポインタに遭遇すること、のmalloc スペース、そこに行く、おそらくmalloc関数空間
そこから再び。
の脅迫因子の一種 動的メモリ割り当て内のポインタ
クリアするハードルです。
しかし、あなたはそれをクリアしたら、挿入 実際には、非常に簡単来ます
そしてそれは確かに一定の時間です。
>> 削除は簡単です。
あなたがする必要があるのは、ナビゲートであります ポインタとフリーノードのカップル、
そのためには、かなり良いです。
ルックアップもかなり速いです。
これはのみに基づいています あなたのデータの長さ。
だからあなたのすべてのデータがある場合 5文字の文字列、
たとえば、5を保存しています あなたのトライの文字列、
それが唯一の5つのステップを取ります あなたが探しているものを見つけます。
ファイブは、単に一定の係数であるため、 再度、挿入、欠失、および参照
ここでは効果的に、すべて一定の時間です。
>> もう一つは、あなたのトライであるということです 実際に種類の既に右、ソート？
私たちがしている方法のおかげで 挿入要素、
の文字で文字を行くことによって キーの桁キー、または数字、
一般的に、あなたのトライはなってしまいます あなたはそれを構築するような種類のソート。
それは本当になりません。 並べ替えを考える意味
同じように、私たちは考えます それ配列、またはリンクされたリストで、
またはハッシュテーブル。
しかし、ある意味で、あなたの あなたが行くようにトライがソートされます。
>> 欠点は、当然のことです トライは急速に膨大になります。
すべての接合点から、あなたがかもしれません あなたのキーは数字で構成されている場合have--、
あなたは他の10を持っています あなたが行くことができる場所、どの
すべてのノードということ 情報が含まれています
あなたが保存したいデータについて そのノードで、プラス10のポインタ。
CS50 IDEのどちらが、80バイトです。
だから、のために少なくとも80バイトです 作成したすべてのノード、
それがあってもデータをカウントしていません。
そして、あなたのノードである場合 代わりに数字の文字、
今では26のポインタを持っています すべての場所から。
そして、26回8はおそらく200です バイト、またはそのような何か。
そして、あなたは資本を持っています そして、lowercase--することができます
右、私はこれで行くよどこに参照してください？
あなたのノードが実際に取得することができます 大きい、などトライ
それ自体、全体的に、することができます あまりにも、本当に大きな得ます。
だから、スペースが高であれば お使いのシステム上のプレミアム、
トライはする正しい方法ではないかもしれません でも、その他の利点が、行きます
遊びに来て。
私はダグロイドです。
これはCS50です。