[音樂播放] ROB BOWDEN：你好。 我搶。 而且我們這個解決方案了。 所以在這裡我們要實現 一個總表。 我們看到，我們的結構節點 表是要這個樣子。 因此，這將有一個char字 數組大小長度+ 1。 不要忘了+1，因為最大 字在字典中是45 字符。 然後，我們將需要一個額外的 字符反斜杠零。 然後我們在每個哈希表 鬥將要存儲 節點鍊錶。 我們沒有做線性探測在這裡。 所以為了鏈接到下一個 在桶的元素，我們需要一個 結構節點*未來。 確定。 所以，這就是一個節點的樣子。 現在，這裡是聲明 我們的哈希表。 這將有16,834桶。 但這個數字其實並不重要。 最後，我們將有 全局變量哈希表大小，這 會作為零開始。 並且它會跟踪如何 許多詞都在我們的字典。 因此，讓我們來看看負荷。 請注意，負載，它返回一個布爾值。 您將返回true，如果它是成功的 加載，否則返回false。 它需要一個為const char *的字典， 這就是詞典 我們要打開。 所以這是第一件事情 我們要做的。 我們要去給fopen的 字典閱讀。 而我們將不得不作出 確保它成功了。 所以，如果它返回NULL，那麼我們沒有 成功打開詞典。 我們需要返回false。 但假設它確實成功 開放的，那麼我們要讀取的 字典。 因此，保持循環，直到我們找到了一些 理由打破這種循環， 我們將拭目以待。 因此，保持循環。 現在我們要 malloc的一個節點。 ，當然，我們需要 宣揚再次檢查。 所以，如果mallocing沒有成功，那麼 我們要卸載的任何節點，我們 碰巧的malloc之前，請關閉 字典和返回false。 但是忽略了，假設我們 成功了，那麼我們要使用的fscanf 從讀一個字我們 字典到我們的節點。 所以請記住該條目>字是字符 大小茸，加1字緩衝區 那我們要存儲的單詞英寸 所以的fscanf會返回1，只要 因為它能夠成功地 從文件中讀一個字。 如果任何一個錯誤發生，或者我們 到達文件的結尾，它 將不會返回1。 在這種情況下，它不會返回1， 我們終於要擺脫 這個while循環。 所以我們看到，一旦我們成功 讀一個字到 入門>字，那麼我們也要去那 詞使用我們的哈希函數。 讓我們來看看 散列函數。 所以，你並不真的需要 要理解這一點。 而實際上我們只是拉著這個散列 從互聯網上起作用。 你需要認識到的唯一一件事就是 這需要為const char *字。 所以它採取一個字符串作為輸入，並 返回一個unsigned int作為輸出。 所以這就是所有的散列函數，它是 需要在輸入和給你一個 索引的哈希表。 請注意，我們被NUM_BUCKETS模變， 使返回值 實際上是一個索引哈希表 並沒有索引超出了 陣列的界限。 所以，有了該功能，我們將 散列，我們讀單詞 字典。 然後我們將使用 散列插入 進入哈希表。 現在，哈希表散列是當前 鏈接表列表中。 而且它很可能 它只是為NULL。 我們要插入我們在入口 開始這個鍊錶中。 所以我們就要有我們目前的 切入點是什麼哈希表 目前指向。 然後我們要保存， 在哈希表在 哈希，當前條目。 所以，這兩條線插入成功 在本月初的入口 鍊錶的索引處 在哈希表。 一旦我們與該做的，我們知道 我們發現了另一個字的 字典，我們增加了。 因此，我們繼續這樣做，直到的fscanf 最後在返回的東西非1 這一點請記住， 我們需要自由進入。 所以，在這裡我們malloced一個條目。 我們試著讀的東西 從字典。 我們沒有成功地讀 東西從字典中，在 我們需要釋放進入這種情況下， 我們從來沒有真正投入 哈希表，並最終破裂。 一旦我們突破了，我們需要看到的，好了， 我們沒有打出來，因為有 從文件中讀取的錯誤？ 還是我們打出來，因為我們 到達文件的末尾？ 如果有錯誤，則 我們要返回false。 由於負載沒有成功。 而在這個過程中，我們要卸載 所有我們在閱讀的話， 關閉字典文件。 假設我們沒有成功，那麼我們就 仍然需要關閉字典 文件，最後返回true，因為我們 成功加載字典。 這就是它的負載。 所以，現在檢查，給定一個哈希表裝， 是要這個樣子。 因此，檢查，它返回一個布爾值，它是 將指示是否通過 以char *的話，是否通過 字符串是在我們的字典。 因此，如果它是在字典中， 如果是在我們的哈希表中， 我們將返回true。 如果不是的話，我們將返回false。 鑑於這種通過在Word中，我們 要哈希的話。 現在認識到的重要一點是 在負載，我​​們知道，所有的 也就是說，我們要為小寫。 但在這裡，我們不是那麼肯定。 如果我們看一看我們的哈希函數， 我們的哈希函數實際上 是下殼體的每個字符 的話。 所以不管資本化 總之，我們的哈希函數是返回 同樣的指數無論 資本化，因為這將有 返回一個完全小寫 版的字。 好吧。 這是我們的指數進入 哈希表這個詞。 現在，這個for循環是要 遍歷鍊錶 這是該索引。 所以請注意，我們初始化入口 指向該索引。 我們將繼續 而進入！= NULL。 請記住，更新指針 在我們的鏈接列表條目=項目>未來。 因此，有我們目前的切入點 在鍊錶中的下一個項目。 因此，對於在該鏈接的表的每個條目， 我們將使用strcasecmp。 這不是STRCOMP。 因為再次，我們要 做事不區別大小寫。 因此我們使用strcasecmp比較 這是通過這個詞通過 對詞功能 那就是在這個條目。 如果返回零，這意味著有 一個匹配，在這種情況下，我們希望 返回true。 我們成功地找到了 字在我們的哈希表。 如果有不匹配，那麼我們 再次要循環，並期待在 下一個條目。 我們將繼續循環，同時有 在此鍊錶條目。 如果我們分手會發生什麼 出這個for循環？ 這意味著我們沒有發現一個條目， 匹配這個詞，在這種情況下， 我們返回false，表明我們的 哈希表中沒有包含這個詞。 ，這是一個檢查。 因此，讓我們來看看大小。 現在，大小將是非常簡單的。 因為記得在負載，每個字 我們發現，我們增加一個全球性的 可變的哈希表大小。 因此，大小功能只是去 返回全局變量。 就是這樣。 現在，終於，我們需要卸載 字典曾經的一切的完成。 那麼我們如何做到這一點？ 在這裡我們要遍歷 本表的所有桶。 因此，有NUM_BUCKETS桶。 並為每個鍊錶我們 哈希表，我們將遍歷 該鏈接的表的全部， 釋放每個元素。 現在，我們必須要小心。 所以在這裡，我們有一個臨時變量 這是存儲指針指向下一個 元件中的鍊錶。 然後我們將免費 當前元素。 我們需要確保我們做到這一點，因為我們 不能只釋放當前元素 然後再試著訪問下一個指針， 因為一旦我們釋放它， 內存變為無效。 因此，我們需要保持周圍的指針 下一個元素，那麼我們就可以釋放 當前元素，然後我們就可以更新 我們目前的元素指向 下一個元素。 我們將循環而有元素 在此鍊錶。 我們將做到這一點的所有鏈接 在哈希表中列出。 有一次，我們正在與該做的，我們已經 完全卸載的哈希表，並 我們就大功告成了。 所以這是不可能的卸載 永遠返回false。 而當我們完成後，我們 剛剛返回true。 讓我們給這個方案一試。 因此，讓我們來看看我們什麼 結構節點的樣子。 在這裡，我們看到，我們就要有一個bool 字和一個結構節點*兒童 支架字母。 所以，你可能是第一件事情 想知道，為什麼是字母 編輯定義為27？ 好了，記住，我們將需要 待處理的單引號。 所以這將是有點的 整個程序中的特殊情況。 現在還記得如何在特里 實際工作。 比方說，我們正在索引字 “貓”。然後從字典樹的根， 我們要看看孩子 數組，我們要看看 對應於字母索引 C.這樣會被索引2。 因此考慮到，那將 給我們一個新的節點。 然後我們將努力從該節點。 所以，有了這個節點，我們再次 去看看孩子們的數組。 而且我們要看看指數為零 對應於貓在A。 這樣的話，我們會去到該節點， 並給予該節點我們將 來看看它到底是一個對應 到T和移動到該節點， 最後，我們已經完全看 通過我們的詞“貓”。現在bool的 單詞應該以指示是否 這個給定的字實際上是一個字。 那麼，為什麼我們需要這種特殊情況？ 什麼樣的詞以及“災難” 是在我們的字典，但 單詞“貓”是不是？ 所以，看，看單詞“貓” 在我們的字典，我們 要成功地去翻 該指數C-A-T的區域節點。 但是，這僅僅是因為災難 發生在其上創建節點的方法 從C-A-T，一路 字的結尾。 所以布爾字被用來指示是否 這個特殊的位置 實際上表示一個字。 好的。 所以，現在我們知道它特里是什麼 會是什麼樣子，讓我們來看看 加載功能。 因此，負載將會返回一個bool 對於我們是否成功 不成功地加載的字典。 這將是字典 我們要加載。 我們是這樣做的第一件事就是打開 了那本詞典閱讀。 我們必須確保 我們沒有失敗。 因此，如果在字典不 成功打開，它將返回 null，在這種情況下，我們 要返回false。 但假設它成功 開了，那麼我們就可以真正閱讀 通過字典。 我們將這樣的第一件事 想要做的是我們有這個 全局變量的根。 現在根將是一個節點*。 這是我們的字典樹的頂部，我們是 將要逐一查看。 所以我們要去的第一件事 想要做的是分配 內存為我們的根。 請注意，我們使用了釋放calloc 功能，這是基本相同 作為malloc函數，除了它的 保證返回的東西是 完全歸零。 因此，如果我們使用的malloc，我們需要 通過所有的指針我們 節點，並確保 它們都是空。 所以釋放calloc會替我們。 現在，就像malloc的，我們需要做 確保分配竟是 成功的。 如果返回null，那麼我們 需要關閉或字典 文件並返回false。 所以，假設分配是 成功，我們將使用一個節點* 游標遍歷我們的線索。 所以，我們的根永遠不會改變， 但我們要使用光標 實際上去從一個節點到另一個節點。 因此，在這個for循環，我們正在閱讀 通過字典文件。 而我們使用的是龜etc。 龜etc是要搶單 字符從該文件。 我們要繼續抓 雖然我們不到達的字符 該文件的末尾。 有兩種情況，我們需要處理。 第一，如果字符 是不是一個新行。 所以我們知道，如果它是一個新行，然後 我們即將進入到一個新詞。 但假設它不是一個新行，然後 在這裡，我們想弄清楚的 指數我們要索引 在孩子陣列 我們看著面前。 所以，就像我之前說的，我們需要 特殊情況下的單引號。 我們正在使用的三元通知 運營商在這裡。 所以，我們要讀這個，因為如果 我們讀到的字符是一個 單引號，那麼我們要設置 指數=“字母”-1，這將 是該指數26。 否則，如果它不是一個單引號，有 我們要設置索引 等於c - 一個。 所以請記住先前對套回， C - 一個是要給我們 C的英文字母位置所以，如果 C是字母A，這將 給我們指數為零。 對於字母B，它會給 我們的索引1，依此類推。 因此，這給了我們中的索引 兒童陣列，我們想要的。 現在，如果該指數是目前在空 子，這意味著，一個節點 目前不存在 從該路徑。 因此，我們需要分配 一個節點的路徑。 這就是我們在這裡做的。 所以，我們要再次使用釋放calloc 功能，這樣我們就不必 零出所有的指針。 而我們又需要檢查 這釋放calloc沒有失敗。 如果釋放calloc會失敗，那麼我們就需要 卸載一切，我們關閉 字典，並返回false。 因此，假如它沒有出現故障，則 這將創建一個新的子我們。 然後我們會去那個孩子。 我們的光標會遍歷 下到那個孩子。 現在，如果這不是空，首先， 然後將光標可以只遍歷 下到那個孩子沒有實際 不必分配任何東西。 這是我們第一次發生的情況 分配單詞“貓”。和 這意味著當我們去分配 “大災難”，我們並不需要創建 再次為C-A-T的節點。 它們已經存在。 這是什麼東西？ 這是其中c是條件 反斜杠N，其中c是一個新行。 這意味著我們已經成功 完成了一個字。 現在，我們究竟想要做的，當我們 成功地完成了一個字？ 我們將用這個詞場 我們的內部結構的節點。 我們要設置為true。 以便表明該節點 表示成功 一句話，一個實際的單詞。 現在設置為true。 我們要重設我們的光標點 在特里的開始了。 最後，增加我們的字典 大小，因為我們發現了另一個工作。 所以，我們要繼續這樣做， 在讀取一個字符一個字符， 構建新的節點在我們的線索和 每個字在字典中，直到 我們終於到達C！= EOF，其中 情況下，我們打出來的文件。 現在有下2箱子 我們可能EOF打擊。 如果有錯誤，首先是 讀取該文件。 所以，如果有錯誤，我們 需要做的典型。 卸載一切，接近 該文件，返回false。 假設沒有了一個錯誤，該 只是意味著我們實際上打的結尾 的文件，在這種情況下，我們關閉 文件，並返回true，因為我們 成功載入字典 進入我們的線索。 所以，現在讓我們看看檢查。 縱觀檢查功能，我們看到 該檢查將要返回一個bool。 如果這個詞，它是返回true 傳遞是在我們的線索。 它，否則返回false。 那麼你是如何判斷是否 這個詞在我們的線索？ 我們在這裡看到的是，就像以前一樣， 我們將使用游標來遍歷 通過我們的線索。 現在，在這裡我們要遍歷 在我們的整個字。 因此，迭代，我們過去的話， 我們要確定 索引的兒童陣列 對應詞支架一所以這 是要完全一樣 負載，其中，如果字[I] 是一個撇號，然後我們想 使用索引“字母” - 1。 因為我們確定了 就是我們要去的地方來存儲 單引號。 否則我們將使用兩個低字 支架一，因此請記住一句話就可以 具有任意大小寫。 所以我們要確保我們 用一個事物的小寫版本。 然後從'a'到一次減 再次給我們按字母順序排列 該字符的位置。 所以這將是我們的索引 進入孩子們的數組。 而現在，如果該索引到孩子 數組為null，這意味著我們 不能再繼續迭代 下來我們的線索。 如果是這樣的話，這個詞不能 可能是在我們的線索。 因為如果它是，這將 意味著將有一個路徑 下到這個詞。 而你永遠不會遇到空。 所以遇到空，返回false。 的字不在字典中。 如果它不為null，那麼我們 要繼續迭代。 所以我們要在那裡光標 以指向特定的 節點的索引處。 我們繼續在整個這樣做 整個單詞，假設 我們從不打空。 這意味著我們能夠獲得通過 整個單詞並找到 在我們的嘗試的一個節點。 但我們還沒有完全完成。 我們不希望只是返回true。 我們要返回游標>字。 由於再次記住，是“貓”不 在我們的字典，和“大災難” ，那麼我們會成功，我們得到 通過字“貓”。但光標 字會是假的，而不是真實的。 所以我們返回游標字來表示 是否該節點實際上是一個字。 就是這樣的檢查。 因此，讓我們看看大小。 所以，大小將是很容易 因為，記得在負載，我​​們 遞增的字典大小 我們遇到的每一個字。 所以，大小只是要 返回字典大小。 就是這樣。 所以最後我們已經卸載。 所以卸載，我們將使用 遞歸函數實際上做 對我們的工作。 因此，我們的功能是要 算得上卸料。 什麼是卸載怎麼辦？ 我們在這裡看到的卸料器是要 遍歷所有的兒童在 這個特殊的節點。 和如果該子節點不是 null，那麼我們要 卸的子節點。 因此，這是你遞歸卸載 我們所有的孩子。 一旦我們確定我們的孩子 已經卸載，那麼我們 可以釋放自己，所以 卸載自己。 這將遞歸工作 卸載整個線索。 然後一旦這樣做了， 我們可以只返回true。 卸載不能失敗。 我們只是釋放的東西。 所以一旦我們完成了解放 一切，返回true。 就是這樣。 我的名字是羅布。 這是拼寫檢查。 [音樂播放]