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です。