>> [音楽再生]
>> ROBボーデン：こんにちは。
私はロブだ。
とのにこのソリューションを出す。
そこでここでは、実装するつもりだ 一般的なテーブル。
当社は、当社の構造ノードが分かり テーブルは次のようにしようとしている。
だから、char型の言葉を持っているために起こっている サイズ長さ+ 1の配列。
最大以来、+ 1を忘れてはいけない 辞書内の単語は45です
文字。
そして、我々は1が余分に必要になるだろう バックスラッシュゼロの文字。
>> して、それぞれに私たちのハッシュテーブル バケットは、保存しようとしている
ノードのリンクリスト。
ここでは、プロービング線形をしていない。
だから次のリンクするために バケット内の要素、私たちが必要とする
次の構造体ノード*。
[OK]をクリックします。
だから、ノードは次のようになります。
>> 今ここで宣言です 私たちのハッシュテーブルの。
これは、16834バケットを持つようになるだろう。
しかし、その数は本当に重要ではありません。
そして最後に、我々は持っているつもりです グローバル変数ハッシュテーブルのサイズ、どの
ゼロとして始めるために起こっている。
そして、それはどのように追跡するために起こっている 多くの言葉は、私たちの辞書にあります。
>> それでは、負荷を見てみましょう。
それはBOOLを返すと、その負荷に注意してください。
それが成功した場合はtrueを返す ロードされ、そうでない場合はfalse。
そしてそれは、constのchar *の辞書を取り 辞書である
我々はオープンしたいという。
だから、最初のことだ 私たちは、やろうとしている。
>> 私たちは、fopenのつもりだ 読書のための辞書。
そして、我々は確認する必要があるとしている それが成功したことを確認してください。
それがNULLを返したのであれば、我々はしませんでした 成功した辞書を開きます。
そして、我々はfalseを返す必要があります。
しかし、それは成功しなかったと仮定して オープン、その後、我々は読んでもらいたい
辞書。
我々はいくつかを見つけるまでそのループを保つ このループから抜け出すための理由、
その我々が表示されます。
そうルーピングキープ。
>> そして今、我々はするつもりだ 単一のノードをのmalloc。
そしてもちろん、我々は必要とする エアチェックをもう一度。
そうmallocingは成功しなかった場合は、 私たちは、任意のノードをアンロードする
前のmallocに起こった、閉じ 辞書とfalseを返します。
しかし、我々が想定していることを無視し 成功し、その後、我々は関数fscanf利用したい
から単一の単語を読むために私たちの 私たちのノード辞書。
だから、そのエントリを覚えている>言葉はCHARです サイズLENGHTH + 1のワードバッファ
我々はインチの単語を保存しようとしていることを
>> だから、fscanfは限り、1を返すために起こっている それが成功してすることができましたように
ファイルから単語を読み込みます。
エラーのいずれかが発生した場合、あるいは我々 ファイルの終わりに達すると、
1を返しません。
その場合は1を返しません、 我々は最終的に抜け出すするつもりだ
このwhileループ。
だから我々は、かつて我々が成功していることがわかります に単語を読む
エントリ>言葉、そして我々はするつもりだ 我々のハッシュ関数を使用して、単語。
>> それでは見てみましょう ハッシュ関数。
だから、本当に必要はありません。 これを理解する。
そして実際に、私たちはちょうどこのハッシュを引っ張っ インターネットからの機能。
あなたが認識する必要がある唯一のものです これはcon​​stのchar *文字の単語を取ること。
だから、入力として文字列を取っている、と 出力として符号なし整数を返す。
だから、すべてのハッシュ関数ですそれは、そうです 入力を取り込んで、あなたに与えます
ハッシュテーブルへのインデックス。
>> 我々はNUM_BUCKETSでモーディングしていることに注意してください、 従ってその値が返さ
実際にハッシュテーブルへのインデックスです 以降もインデックスされない
配列の境界。
だから、その関数を考えると、我々は行っている 我々は読んで単語をハッシュする
辞書。
そして、我々は使用するつもりだ 挿入する、そのハッシュ
ハッシュテーブルへのエントリ。
>> 今ハッシュテーブルハッシュは、現在ある テーブルのリストをリンク。
そして、それは非常に可能性があります それは単にNULLということ。
我々は、我々のエントリを挿入したい このリンクリストの先頭です。
だから我々は我々の現在を持っているつもりです どのようなハッシュテーブルへのエントリポイント
現在を指す。
そして、我々は店に行っている、 で、ハッシュテーブルの
ハッシュ、現在のエントリ。
だから、この2行は正常に挿入 の先頭にエントリー
そのインデックスのリンクリスト ハッシュテーブルにある。
>> 我々はそれに終わったら、知っている 我々は、別の単語を見つけた
辞書、そして我々は再び増加します。
だから我々はやり続けることはfscanfまで、 最終的に何か非1を返しました
その時点ではそれを覚えている 我々は、エントリを解放する必要があります。
だから、ここまで私たちは、エントリをmallocさ。
そして、我々は何かを読み取ろうとしました 辞書から。
そして、我々は正常に読み込まれませんでした 辞書から何か、
我々は、エントリを解放する必要がある場合 私たちは実際に入れたことがないことを
ハッシュテーブル、そして最終的に壊れる。
>> 我々は抜け出すたら、我々は、よく、見る必要がある 我々は、理由があっ抜け出すんでした
ファイルからの読み取りエラーがあった？
あるいは我々が勃発なかったので、私たち ファイルの終わりに達した？
エラーが発生しました場合は、 私たちは、falseを返すようにしたい。
負荷が成功しなかったため。
その過程で、我々はアンロードする 我々が読んですべての単語、および
辞書ファイルを閉じます。
>> 我々は成功しなかったと仮定すると、我々だけで それでも辞書を閉じる必要が
ファイル、および最終的にはtrueを返すため、我々 成功した辞書をロードしました。
そして、それは、負荷のためにそれだ。
だから今、ロードされたハッシュテーブル与えられ、確認してください このように起こっている。
そうである、それはBOOLを返す、確認 渡されたかどうかを示すために行く
char *文字の単語で、かどうかを渡された 文字列に私たちの辞書にある。
だから、辞書内にある場合、 それが私たちのハッシュテーブル内にある場合は、
私たちは、trueを返します。
そうでないならば、我々はfalseを返します。
>> これは言葉で渡さ考えると、我々はしている 単語をハッシュする予定。
今すぐ認識することが重要なことは 負荷に我々は知っていたすべてのこと
私達はより低いケースであるとしている言葉。
しかし、ここではとてもわからない。
我々はハッシュ関数を見てみると、 実際に私たちのハッシュ関数
各文字は、下部筐体である 言葉の。
だから関係なく、総額 言葉、私たちのハッシュ関数はリターンです
何のための同じインデックス 時価総額は、それが持っていると同じように、ある
完全に小文字に返さ Wordのバージョン。
大丈夫。
それが私たちのインデックスはにあります この単語のためのハッシュテーブル。
>> 今、このループのために起こっている リンクリストを反復
つまり、そのインデックスにあった。
だから我々は、エントリを初期化しているに気づく そのインデックスを指すように設定します。
我々は継続するつもりだ エントリー！= NULLながら。
ポインタを更新することを覚えておいてください 次の我々のリンクリストエントリ=エントリ>。
だから私たちの現在のエントリ·ポイントにしてい リンクリストの次のアイテム。
>> だから、リンクリスト内のエントリごとに、 私たちは、strcasecmpを使用するつもりだ。
それはは、StrCompではありません。
再び、我々はしたいので、 区別せず物事のケースを行います。
だから我々は比較にstrcasecmpを使用 この通した言葉
言葉に対する機能 つまり、このエントリにあります。
それがゼロを返した場合、それがあったことを意味 我々がしたい、その場合に一致すると、
trueを返します。
我々が正常に見つかった 私たちのハッシュテーブルにある単語。
>> 一致するものがなかった場合、我々はしている 再びループに行くと見て
次のエントリー。
そして、我々はしばらくの間そこにループし続けます このリンクリスト内のエントリです。
私たちは壊れた場合はどうなります forループこれのうち？
それは我々がそのエントリを見つけられませんでした意味 その場合には、この言葉を一致
私たちは、それを示すためにfalseを返す ハッシュテーブルは、この単語が含まれていませんでした。
そして、それはチェックです。
>> それでは、サイズを見てみましょう。
今のサイズは非常に簡単になるだろう。
以来、単語ごとに、負荷に覚えている 我々はグローバルに増加、発見
可変ハッシュテーブルのサイズ。
だから、size関数はちょうど起こっている グローバル変数を返します。
そして、それはこれだけです。
>> ついに、我々はアンロードする必要があります 辞書すべてが済んだら。
では、どのようにそれをするつもりですか？
右ここでは、以上のループをしている 私たちのテーブルのすべてのバケット。
そうNUM_BUCKETSバケットがあります。
そして、各リンクされたリストについては、 ハッシュテーブルは、をループするつもりだ
リンクリストの全体、 各要素を解放する。
>> 今、私たちは注意する必要があります。
そこでここでは、一時的な変数がある つまり、次のポインタを格納だ
リンクされたリスト内の要素。
そして、我々は自由になるだろう 現在の要素。
我々は、我々以来、これを行うことを確認する必要があり ただ、現在の要素を解放することはできません
して、次のポインタにアクセスしようとする、 一回以来我々はそれを解放しましたが、
メモリは無効になります。
>> だから我々は体へのポインタの周りに維持する必要があります 次の要素は、その後、我々は解放することができます
現在の要素、そして、我々は更新することができます を指すように私たちの現在の要素
次の要素。
要素が存在している間、我々はよループ このリンクリスト内。
我々は、すべてのリンクのためにそれをやる ハッシュテーブル内のリスト。
我々はそれに終わった後、我々はしました 完全にハッシュテーブルをアンロードし、
我々は完了です。
だから、アンロードのために不可能だ 今までにfalseを返すように。
そして、我々は、我々が完了したら ただtrueを返す。
>> のは、このソリューションを試してみましょう。
それでは、どのような私たちを見てみましょう 構造ノードは、次のようになります。
ここで我々はBOOLを持っているつもりです参照してください。 Wordや構造体ノード*子どもたち
ブラケットのアルファベット。
あなたは可能性がありますので、まず最初に アルファベットである理由、不思議
27のように定義ED？
まあ、我々は必要になるだろうことを覚えておいてください アポストロフィを処理する。
だから、多少のことになるだろう このプログラムを通して特殊なケース。
>> 今どのようにトライを覚えている 実際に動作する。
のは、我々は言葉をインデックス化しているとしましょう "猫。"そして、トライのルートから、
私たちは子供たちを見てするつもりだ アレイと、私たちが見ていくつもりです
文字に対応するインデックス C. SO 2をインデックス付けされるようにします。
だから与えられたものは、その意志 私たちに新しいノードを与える。
そして、我々は、そのノードからうまくいく。
>> だから、そのノードを考えると、我々は再びだ 子配列を見に行く。
そして、我々は、インデックスをゼロに見ていくつもりです 猫のAに対応する。
それでは、私たちは、そのノードに行くつもりだ、 そして我々が行っている、そのノードを与えられた
最後に見て、それは相当だ Tに、そのノードに移動する、
最後に、我々は完全に見てきました 私たちの言葉から "猫。"そして今、BOOL
ワードがどうかを示すことになっている この与えられた単語は実際には単語である。
>> では、なぜ我々は、特殊なケースが必要なのでしょうか？
さてどのような単語の "破局" 私たちの辞書にあるが、
単語 "猫"ではないでしょうか？
だから、単語「猫」かどうかを調べ 私たちの辞書には、我々はしている
首尾よく目を通すつもり 領域ノード内のインデックスは、C-A-T。
しかし、それは唯一の理由破局 途中でノードを作成するために起こった
C-A-Tから、すべての方法に 単語の終わり。
そうBOOLワードはかどうかを示すために使用されている この特定の場所
実際の単語を示しています。
>> わかりました。
だから今我々はそれがトライが何であるかを知っていることを のように見に行く、のを見てみましょう
ロード機能。
だから、負荷がBOOLを返すために起こっている どうか、我々は成功したりするため
失敗した辞書をロードしました。
そして、これは辞書になるだろう 私たちは、ロードすること。
>> そのためには私たちがしている最初の事は開いている 読書のため、その辞書をバックアップします。
そして、我々は確認する必要があります 私たちは失敗しませんでした。
辞書ではなかったそうであれば 正常にオープン、それが返されます
ヌル、その場合、我々はしている falseを返しに行く。
しかし、それが正常と仮定すると 開かれた、我々は実際に読むことができます
辞書を通して。
>> 我々はするつもりだそう最初の事 何をしたい我々はこれを持っている
グローバル変数ルート。
今のルートは、ノード*になるだろう。
それは我々がしている私たちのトライのトップだ 繰り返し処理されようとして。
我々は行っているので、最初にすること やりたいようにして割り当ててある
私たちのルートのためのメモリ。
我々はcallocはを使用していることに注意してください 基本的には同じである機能、
malloc関数として、それはある点を除く 何かを返すことが保証
完全にゼロ。
我々はmalloc関数を使用した場合ので、我々はする必要があります 私たちの内のポインタのすべてを行く
ノード、およびことを確認してください 彼らはすべてのNULLだ。
だから、callocは、私たちのためにそれを行うだろう。
>> 今だけのmallocと同じように、我々は確認する必要があり 割り当てが実際にあったことを確認してください
成功。
これはnullを返した場合、我々は 閉じたり、辞書必要がある
提出し、falseを返します。
だから、割り当てがあったと仮定すると 成功した、我々はノードを使用するつもりだ*
私たちのトライを反復処理するためにカーソル。
だから私たちのルーツは変更するつもりはありません、 しかし、我々は、カーソルを使用するつもりだ
実際にノードからノードへ移動します。
>> したがって、このループのために我々は読んでいる 辞書ファイルを使用して。
そして、我々はfgetc関数を使用している。
fgetc関数は、単一のをつかむために起こっている ファイルからの文字。
私たちはつかんで継続するつもりだ 文字我々は達していないながら、
ファイルの終わり。
>> 私たちが処理する必要がある2つのケースがあります。
文字の場合、最初の 新ラインではなかった。
だから我々はそれが、その後、新しい行だったかどうかを知る 我々は新しい単語に移動しようとしている。
しかし、その後、それは新しい行ではなかったと仮定すると ここでは、把握したい
我々はへのインデックスとしている指標 その子配列内の
我々は前に見た。
>> だから、私は前にも言ったように、私たちのことを行う必要があり 特殊なケースアポストロフィ。
我々は、三元を使用している注意してください ここ演算子。
だから我々は、IF、としてこれを読んでするつもりだ 我々が読み取った文字だった
アポストロフィ、その後、我々は設定しようとしている インデックス= "ALPHABET" -1、ウィル
インデックス26であること。
>> それはそこに、アポストロフィでなかった場合には、他の 私たちは、インデックスを設定するつもりだ
- Cに等しい。
だから、戻って、以前のP-セットから覚えて、 C - Aは、私たちに与えるために起こっている
もしそうであればCのアルファベットの位置 Cは、この意志文字Aである
私たちにインデックスゼロを与える。
文字Bのために、与える 私たちのインデックス1、というように。
>> だから、これは私たちへのインデックスを提供します 私たちが望む子ども配列。
今、このインデックスは、現在nullの場合 子供は、そのつまり、ノード
現在存在しません そのパスから。
だから我々は割り当てる必要が そのパスのノード。
それは我々がここでやるんだ。
>> だから我々は再びcalloc関数を使用するつもりだ この関数は、我々はする必要がないように
すべてのポインタをゼロに。
そして、我々は再度確認する必要があります そのcallocは失敗しませんでした。
callocはが失敗したのなら、私たちは必要に 全てをアンロードするには、私たちを閉じる
辞書、falseを返します。
だから、その後、失敗しなかったと仮定して これが私たちのために新しい子を作成します。
そして、我々は、その子に移動します。
当社のカーソルが繰り返されます その子まで。
>> さて、これはそもそもNULLでなかった場合には、 カーソルだけ繰り返すことができます
実際にすることなく、その子まで 何を配分すること。
これは、我々が最初に起こったケースで​​ある 単語割り当てる「CAT」をと
我々は割り当てに行くときには意味 「大災害」では、作成する必要はありません
再びC-A-T用のノード。
彼らはすでに存在しています。
>> この他には何ですか？
これはCだった条件である Cは新しいラインだったバックスラッシュN、。
これは、我々が成功していることを意味します 単語を完成させた。
今、私たちは、ときに我々に何をすべきかをしたいですか 成功裏に単語を完了？
我々は、このWordのフィールドを使用するつもりだ 当社の構造ノードの内部。
私たちは、trueにそれを設定したい。
だから、このノードを示す 成功したことを示す
単語、実際の単語。
>> 今trueにそれを設定します。
我々はポイントに私たちのカーソルをリセットしたい もう一度トライの先頭に。
そして最後に、私たちの辞書をインクリメント サイズ、我々は別の仕事を見つけたことから。
だから我々はそれをやり続けるつもりだ、 文字単位で読み、
私たちのトライで新しいノードを構築し、 辞書内の各単語の日まで
我々はここで、C！= EOFに最終的に到達 場合我々は、ファイルから抜け出す。
>> 今2例は下がある 私たちは、EOFにヒットしているかもしれない。
エラーが発生した場合、まず、ある ファイルからの読み取り。
エラーがあったそうであれば、我々は 典型的な操作を行う必要があります。
近くに、すべてをアンロードする ファイルには、falseを返します。
エラーがなかったと仮定すると ちょうど私達が実際の終了を打つ意味
ファイルは、その場合、我々は、閉じ 我々以来提出し、trueを返す
正常にロードされた辞書 私たちのトライへ。
>> だから今のチェックを確認してみましょう。
チェック機能を見ると、我々が表示さ そのチェックは、BOOLを返すために起こっている。
この言葉は、それがだとした場合にはtrueを返します 私たちのトライである渡される。
それは、そうでない場合はfalseを返します。
それでは、どのようにするかどうかを判断している この言葉は、私たちのトライである？
>> 我々は、その直前のようにここを参照してください、 私たちは、反復するために、カーソルを使用するつもりだ
私たちのトライを通じて。
今、ここでは、繰り返し処理をするつもりだ 私達の全体の単語の上に。
そこで、我々は過去である単語の繰り返し処理を行う 我々は決定するつもりだ
子配列のインデックスという 単語ブラケットIに対応しているので、この
正確に見えるようになるだろう 負荷、単語であれば[I]
アポストロフィは、その後、我々は欲しいさ 1 - インデックス "ALPHABET"を使用する。
我々はそのことを決定しているので 我々は店に行っている場所である
アポストロフィ。
>> 他に我々は2つ​​の下位ワードを使用するつもりだ ブラケットI.だからその単語を覚えることができる
任意の時価総額を持っています。
そして私たちは、私たちがしていることを確認するには 物事の小文字バージョンを使用して。
して、その ''に一度から差し引く 再び私たちに、アルファベットを与える
その文字の位置。
だから、Googleのインデックスになるだろう 子配列に変換する。
>> そして今、子どもたちにそのインデックスの場合 配列がnullの場合、それは我々を意味します
もはや反復を継続することはできません 私たちのトライダウン。
その場合は、この言葉ができない おそらく私たちのトライであること。
それならば、それはだろ日時 パスがあるだろうことを意味
その単語まで。
そして、あなたは、ヌルが発生したことはない。
だから、ヌルに遭遇、我々はfalseを返します。
言葉は辞書にありません。
それがnullでないならば、我々はしている 反復を継​​続する予定。
>> だから我々はそこにカーソルをつもりだ その特定を指すように
そのインデックス位置にあるノード。
私たちは、全体でそれをやり続ける 単語全体、と仮定すると
我々はNULLを打つことはありません。
それは我々が通り抜けることができたことを意味 単語全体、検索
私たちのTRY内のノード。
しかし、我々は非常にまだ終わっていない。
>> 我々だけtrueを返すようにしたくない。
私たちは、カーソル>言葉を返すようにしたい。
もう一度覚えているので、「猫は」ではありません 私たちの辞書内、および「大惨事」
、その後、我々は成功し、我々は取得している 言葉を通じて "猫。"しかし、カーソル
言葉は虚偽と真実ではないでしょう。
だから我々は示すために、カーソルの単語を返す どうか、このノードは、実際に言葉です。
そして、それはチェックのためにそれだ。
>> それでは、サイズを確認してみましょう。
だから、サイズが非常に簡単になるだろう 負荷に覚えているので、我々はしている
辞書サイズをインクリメント 我々が遭遇する各単語。
だから、サイズはちょうどしようとしている 辞書サイズを返す。
そして、それはこれだけです。
>> だから、最後に我々はアンロードしています。
だから我々は使用するつもりだ、アン 実際にすべて実行する再帰関数
私たちのために仕事の。
だから私たちの機能がしようとしている アンローダで呼び出される。
何アンローダは何をするつもりですか？
私たちは、アンローダをしようとしていることがわかり でも子供のすべてを反復
この特定のノード。
および子ノードではない場合 NULLの場合、我々はするつもりだ
子ノードをアンロードします。
>> だから、これはあなたが再帰的にアンロードされる 私たちの子供たちのすべて。
我々は我々の子供たちのすべてのことを確認してもらった 我々はその後、アンロードされた
だから、自分自身を解放することができます 自分自身をアンロードします。
これは再帰的に動作します 全体トライをアンロードします。
して、設定が完了する、 我々だけtrueを返すことができます。
アンロードは失敗することはできません。
私たちは、物事を解放している。
だから我々は解放終わったら すべては、trueを返します。
そして、それはこれだけです。
私の名前はロブです。
そして、これはスペルチェックだった。
>> [音楽再生]