>> KEVINシュミット：時々、ビルドするとき このプログラムは、あなたが利用することをお勧めします
辞書として知られているデータ構造。
ある辞書のマップキー、 通常の値に、文字列、整数、
文字、いくつかのオブジェクトへのポインタ、 我々は好き。
それは、普通の辞書のようなものだ 定義を通じてそのマップは言葉。
>> 辞書はを提供してくれる 情報を記憶する能力
何かに関連付けられている 後でそれを検索します。
では、どのように実際に実装するのですか Cコード、たとえば、辞書たちができる
私たちのプログラムのいずれかで使うのか？
まあ、それの方法はたくさんあり​​ます 私たちは辞書を実装することができます。
>> 1のために、我々は我々の配列を使用することができます 動的に再サイズや、我々は使用することができます
リンクリスト、ハッシュテーブル またはバイナリツリー。
しかし、我々は選択したものは何でも、私たちはすべき 効率に留意し、
実装のパフォーマンス。
我々は、使用されるアルゴリズムを考える必要があります に項目を挿入して、ルックアップする
私たちのデータ構造。
>> ここでは、のは、その私たちを想定してみましょう キーとして文字列を使用したいと思います。
それでは一つの可能​​性についてお話しましょう​​、 データ構造は、トライと呼ばれる。
だからここに視覚的な表現です トライの。
>> 写真は、トライを示唆しているように とツリーデータ構造である
互いにリンクされたノード。
我々はルートが明確があることを参照してください。 に至るいくつかのリンクを持つノード
他のノード。
しかし、各ノードは、で構成されていますか？
私たちは鍵を格納していると仮定した場合 英字のみとし、
私たちは、大文字と小文字を気にしない、 ここに、そのノードの定義を示します
十分です。
>> 型が構造体であるオブジェクト ノードには2つの部分があります
データや子供たちを呼んだ。
私たちは、コメントとしてデータ部分を残してきた 成分によって置換される
構造ノードである宣言 Cプログラムに組み込ま。
ノードのデータ部分は次のようになります。 かどうかを示すブール値
いないノードが完了したことを表している 辞書のキーのまたはそれはあるかもしれない
定義を表す文字列 辞書内の単語の。
>> 我々は示すためにスマイリーフェイスを使用します データは、ノード内に存在する場合。
私たちの中の26の要素があります。 子配列、1インデックス
英字あたり。
私たちは、意義が表示されます すぐにこのの。
>> のルートノードを詳しく見ていきましょう データがない私たちの図に
で示されるように、それに関連付けられた 中スマイリーフェイスの欠如
データ部。
の部分から延びる矢印 子配列は、非ノードを表す
他のノードへのポインタ。
例えば、矢印は、から延びる 子供の二番目の要素
手紙Bを表し、 辞書のキーにある。
より大きな図中の 我々はBでラベルを付け
>> より大きな図では、ときに我々に注意してください 別のノードへのポインタを描き、それ
どこ矢じりは関係ありません そのほかのノードを満たしています。
このサンプル辞書トライは含まれています 二つの言葉は、そのズーム。
それではの例を見てみましょう キーのデータを検索する。
>> 我々が見ていたとします キー風呂の値を対応する。
私たちは、ルックアップを始めましょう ルートノードた。
その後、我々は我々の最初の文字を取るよ 、鍵B、および対応を見つける
私たちの子供たち配列内のスポット。
正確に26のスポットがあることに注意してください 配列の各文字のための1中
アルファベット。
そして、我々は斑点が表す必要があります 順にアルファベットの文字。
>> 私たちは、2番目のインデックスを見てみましょう 一般的にはBのインデックス1、我々の場合
いくつかのアルファベット文字C、我々が持っている 対応するスポットを決定することができる
使用して子配列内の このような計算。
私たちは、より大きな子を使用することもできます 我々は、ルックアップを提供したい場合は、アレイ
文字の広い範囲でキー、 このような全体としての
ASCII文字セット。
>> この場合、ポインタ で私達の子供·アレイ内の
インデックス1はNULLではありません。
だから我々は見続けます キー風呂上り。
我々はこれまでに、nullポインタが発生した場合 子供の適切な箇所に
配列我々はノードを横断しながら、 その後、我々はその我々が言うことがあるでしょう
そのキーの何かを見つけることができませんでした。
>> 今、私たちは第二の手紙を取るよ 当社の主要A、および以下継続
私たちまで、このように、ポインタ 当社の主要の最後に到達する。
私たちはせずに、キーの最後に到達した場合 任意の行き止まり、ヌルポインタを打つ、
我々だけにして、ここではそうであるように もう一つのことをチェックする必要があります。
このキーは、実際には 辞書内の？
>> もしそうなら、我々はAだけでなく、値を見つける必要があります 私たちの図中のスマイリーフェイスアイコンを場所
言葉は終了します。
何か他のものがあった場合に格納されている データは、その後、我々はそれを返すことができます。
例えば、キー動物園ではありません 我々が持っている可能性にもかかわらず、辞書、
これまでにすることなく、このキーの終わりに達し 我ながら、NULLポインタを打つ
トライを反復。
>> 我々は主要なお風呂を検索しようとすると、 第二の最後のノードの配列インデックスに、
、文字Hになり、対応する NULLポインタを開催しています。
だから、お風呂は辞書にありません。
だからトライは、キーという点で独特である 明示的に保存されることはありません
データ構造。
では、どのように何かを挿入しない トライへ？
>> キーを挿入してみましょう 私たちのトライに動物園があります。
覚えておいて、そのノードのスマイリーフェイス 簡単な、コードに対応することができる
その動物園を示すブール値 辞書にあるか、それができた
我々より多くの情報に対応 キー動物園に関連付ける、
の定義のような 単語または何か他のもの。
ある意味では、プロセスは、挿入する トライへ何かに似ている
トライで何かを調べる。
>> 我々は再びルートノードから始めましょう、 に対応する次のポインタ
当社の主要の手紙。
幸いなことに、我々はポインタをたどることができました 私たちに達するまで、すべての道
キーの最後。
動物園は、単語の接頭語であるため、 のメンバーである、ズーム、
辞書には、我々はする必要はありません 任意の新しいノードを割り当てます。
>> 我々はそれを示すためにノードを変更することができます につながる文字のパス
それが私たちの辞書内のキーを表します。
それでは、挿入してみましょう トライにキーBATH。
私たちは、ルート·ノードから開始します そして、再びポインタに従ってください。
しかし、このような状況では、我々は死者を打つ 我々が得ることができるしている前に終了
キーの最後。
今、我々はいくつかの新しいを割り当てる必要があります ノードは、新しいものを割り当てる必要があります
残りの各ノードのための 当社の主要の手紙。
>> この場合、我々だけが必要 1新しいノードを割り当てます。
その後、我々は、H·インデックスを作成する必要があります この新しいノードを参照。
もう一度、我々は、ノードを変更することができます 文字のパスを示している
それにつながることを表す 私たちのディクショナリのキー。
漸近約レッツ理由 これらのための私たちの手続きの複雑さ
2事業。
>> 我々は両方のケースで数いることがわかり 我々のアルゴリズムがかかった手順
の数に比例 キーワードの文字。
そう。
あなたが単語を検索したいとき あなただけを反復処理する必要がトライ
文字1つずつ必要になるまでのどちらか 単語の最後に到達するか、
トライで行き止まりにヒット。
>> そして、あなたはキーを挿入したいとき 使用してトライへと値のペア
我々は議論の手順、最悪の場合 新しいノードを割り当てる必要があります
各文字。
そして、我々はその割り当てを仮定します 一定時間操作があ​​る。
我々は、キーの長さであると仮定しそうである場合 固定された定数の両方で囲まれた
挿入と見上げる一定である トライの時間操作。
>> 私たちは、この仮定をしない場合は、その キーの長さは固定で囲まれ
定数は、挿入と見上げる、 最悪の場合には、線形である
キーの長さ。
項目の数が格納されていることに注意してください トライでルックアップには影響しません
または挿入時間。
それが唯一の影響を受けているの キーの長さ。
>> これとは対照的に、たとえば、にエントリを追加する ハッシュテーブルは作成する傾向がある
未来が遅く調べる。
これは、最初は魅力的に聞こえるかもしれないが、 我々は心に留めておくべきこと
有利な漸近的複雑さはない 実際には、データをその意味
構造は必然である 非難を超えた。
我々はまた、保存するためにそれを考慮する必要があります 我々が必要とトライ中の単語、最悪の中
ケース、ノード数に比例 単語自体の長さに。
>> 試みは、多くのスペースを使用する傾向がある。
すなわち、ハッシュテーブルとは対照的だ 私たちは、1つの新しいノードを必要な場所
いくつかのキーと値のペアを格納します。
今、再び理論的には、大きなスペース 消費量が大きいように見えるしていません
特に現代のことを考えると契約、 コンピュータはギガバイトを持っており、
メモリのギガバイト。
しかし、それは、我々はまだ持っていることが判明 メモリ使用量を気にすると
のための組織 現代のコンピュータからパフォーマンス、
下の場所でのメカニズムを持っている メモリアクセスを高速化するフード。
>> しかし、これらのメカニズムは、最高のときに動作 メモリアクセスはコンパクトに作られてい
領域または地域。
とトライのノードが存在する可能性が そのヒープ内の任意の場所。
しかし、これらはトレードオフである 我々は考慮しなければならないこと。
>> データを選択する際に、以下のことを覚えている 特定のタスクのための構造、私たち
どのような考えなければならない 操作は、データ構造は、必要に
サポートとどのくらいの性能 それらの各々の
操作は、私たちにとって重要。
これらの操作でもよい ちょうど超えて拡張
基本的なルックアップおよび挿入。
我々は親切を実装したいとし オートコンプリート機能は、多くの
Googleのように検索エンジンがありません。
つまり、すべてのキーを返し、 潜在的にどの値
指定された接頭辞が付いています。
>> トライは一意に便利です この動作を行います。
これは、反復処理するために簡単です 各文字のためのトライ
接頭辞。
ただ見上げる動作と同様に、 私たちは、ポインタをたどることができ
文字単位。
その後、我々は最後に到着したとき 接頭辞は、反復処理ができ
データ構造の残りの部分 キーのいずれかを超えて以来、
この点は、接頭辞を持っている。
>> それは、このリストを得ることも簡単です 以来、アルファベット順に
子配列の要素 アルファベット順に並べられます。
だから、うまくいけば、検討します 寄付は、トライをしようとします。
私はケビン·シュミットだし、これはCS50である。
>> ああ、これが始まりです 衰退。
ごめんなさい。
申し訳ありません。
>> ストライク4。
私は思います。
申し訳ありません。
誰が人を作るために残念 これは夢中に編集することがあります。
>> 申し訳ありません。
申し訳ありません。
>> スピーカ1：よくやった。
それは本当によく行われていた。