>> ZAMYLA陳：讓我們 一個拼寫檢查器。
如果你打開speller.c，然後你會看到 大部分的功能​​為
檢查對一個文本文件 字典是已經為你做。
/拼寫檢查，傳遞一個字典文字 文件，然後另一個文本文件，
將檢查的文本文件 對字典。
>> 現在，詞典文本文件將包含 有效的話，每行一個。
然後speller.c將調用Load 在字典中的文本文件。
它會調用被調用函數檢查 每一個字的輸入的文本文件，
打印所有拼寫錯誤的單詞。
>> Speller.c還將呼籲大小來 決定在單詞數
字典和調用卸載 以釋放內存。
speller.c也將跟踪如何 多少時間是用來進行這些
過程，但我們會 到後來。
>> 那麼，我們需要做什麼？
我們需要填寫dictionary.c。
在dictionary.c，我們有幫手 功能加載，加載了
字典。
功能檢查，如果它檢查 一個給定的字在字典中。
該函數大小返回數字 在字典中的字。
最後，我們已經卸載，這 從存儲器釋放字典。
>> 因此，首先讓我們來解決負載。
在字典中的文字每個字 文件，加載將存儲在那些話
的詞典數據的結構 您的選擇，無論是中
哈希表或線索。
我過去無論是在 此穿行。
>> 首先，讓我們來談談哈希表。
說你有10台球和 你想存儲它們。
你不妨把它們放在一個桶裡， 當你需要一個特定的
編號的球，你會採取一 出桶時間的
尋找那個球。
而只有10球，你應該 能夠找到你的球在一個合理的
量的時間。
>> 但是，如果你有20個球？
現在它可能需要一點時間。
怎麼樣100？
1,000？
現在，這將是容易得多，如果 你有多個桶。
也許有鬥球編號為零 經過九個，另一桶
球編號為10至 19，依此類推。
>> 現在，當您需要尋找特定 球，你可以自動
去一個特定的桶和 搜索通過桶。
如果每個桶中有大約10 球，那麼你可以很容易地搜索
通過它。
>> 現在，因為我們正在處理 字典，一個用於單鬥
所有在字典中的單詞會 可能是太少桶。
因此，讓我們來看看哈希表。
>> 把它看成是水桶的數組。
並且在這種情況下，該桶 是我們的鍊錶。
我們將分發所有的我們的話 其中在這些多重鍊錶
一個有組織的方式使用哈希函數， 它會告訴我們哪些
鬥一個給定的鍵，一個給定的 字，屬於。
>> 讓我們代表這示意性的。
藍色方框這裡包含的價值觀和 紅色方框指向另一個值
指針對。
我們稱這些成對節點。
現在，每個桶，正如我所說 早期，是一個鍊錶。
在鍊錶中，每個節點都有一個值， 以及一個指針，指向
下一個值。
>> 現在，處理鍊錶， 這是非常重要的，你
不輸任何鏈接。
而另一個事實要記住的是， 最後一個節點，如果它不指向
另一個節點，指向空。
>> 那麼，我們如何代表在C？
在這裡，我們定義我們的結構。
在這種情況下的值是 長度的字符數組。
長度加1，其中長度是 最大長度的任何單詞，加1
空終止。
然後我們有一個指針 另一個節點叫做下一步。
>> 因此，讓我們做一個小的鍊錶。
首先，你會想用malloc您的節點， 它在內存中創建空間
您的節點類型的大小。
並讓另一個節點， 再次mallocing。
>> 現在，如果你想要一個值賦給一個 字，那麼我們可能會說node1上箭頭
字等於“你好。”這個箭頭操作符 取消引用指針和
訪問結構體的變量。
這樣，我們就不必同時使用 點和星算。
>> 於是我有node2上箭頭字等於 “世界”。而且，這些值是
居住在我的節點。
為了使鏈接，我會通過在節點1 旁邊的箭頭，訪問該節點的明星，
該節點的指針，等於節點2， 指向節點1到節點2。
我們在那裡有一個鍊錶。
>> 所以這只是一個鍊錶，但 哈希表是整個陣列
鍊錶。
好了，我們將有相同的節點 如前結構。
但是，如果我們想要一個實際的哈希表， 那麼我們可以只讓一個節點指針
數組在這裡。
例如，大小500。
>> 現在通知，還有的將是一個貿易 關的大小之間的
哈希表及大小 您的鍊錶。
如果你有一個非常高數 水桶，想像不必跑回來
和向前一行 找到你的水​​桶。
但你也不想少數 水桶，因為那時我們又回到了
如何具有原始問題 太多的球，我們的水桶。
>> 好了，但那些我們的球去了？
那麼，我們首先需要 有一個球，對不對？
因此，讓我們的malloc為每一個節點 新詞，我們有。
節點* new_node等號 的malloc（的sizeof（節點））。
>> 現在我們有了這個結構，我們 可以掃描中，使用功能
的fscanf，從我們的文件中的字符串，如果 這是一個字典文件，進
new_node箭頭字，其中new_node 箭頭的話是我們
該單詞的目的地。
>> 接下來，我們將要哈希 字使用哈希函數。
散列函數將一個字符串 並返回一個索引。
在這種情況下，索引有 小於的數量
你有水桶。
>> 現在，散列函數，當你試圖 找到一個，並創建一個
你自己，記住他們 必須是確定性的。
這意味著相同的值需要 每次映射到同一個桶
您哈希它。
>> 這有點像一個圖書館。
當你把一本書的基礎上， 作者，你知道哪個貨架它應該
去，無論是貨架編號 一個，兩個或三個。
而這本書將永遠屬於上 任一貨架的一個，兩個或三個。
>> 所以，如果new_node箭頭字的 從你的字典​​中的單詞，然後
散列new_node箭頭會字 給我們的索引
鬥哈希表中。
然後我們將其插入該 由指定的特定鍊錶
回到我們的哈希函數的值。
>> 讓我們看一個例子 插入一個節點到
開始的鍊錶。
如果頭是一個節點指針，指示 的一個鏈接的開始
列表，並new_node表示新 要進入，只是節點
分配頭new_node將失去 鏈接列表的其餘部分。
所以，我們不希望這樣做。
>> 相反，我們要確保 我們堅持每
在我們的節目單節點。
所以運行new_node箭頭旁邊的equals 頭，然後頭等於new_node
將保留所有的 鏈接和不會丟失任何。
>> 但如果你想你的列表是 排序，因為有一個排序的鏈接
清單可能為更容易 尋找它以後？
那麼，對於這一點，你需要知道的 如何遍歷鍊錶。
>> 遍歷一個鍊錶，讓我們 一個節點的指針，一個節點*，充當
你的光標，指示哪些 節點你在起
在第一個元素。
循環，直到光標為空，我們可以 進行一定的處理，然後
向前移動光標，​​當我們需要 使用光標箭頭的價值。
>> 請記住，這是同樣的事情 話說明星光標，提領
光標，然後使用 點運算符值。
所以通過將更新光標 光標移動到光標箭頭旁邊。
>> 說你確定D變為在 與C和E要插入的節點，
有new_node C點到 節點E，這是下一個光標。
然後C，光標，可以再點 到D這樣，你保持一個列表。
小心不要失去你的鏈接 移動光標箭頭旁邊到D
的時候了。
>> 好的。
所以這就是你會如何插入節點， 加載它們，負載話到這些
個節點，並把它們插入 到你的哈希表。
所以，現在讓我們來看看嘗試。
>> 在字典樹中，每個節點將包含一個 結點的指針，一個用於每個陣列
字母在字母表 加一個單引號。
並且陣列中的每個元素 將指向另一節點。
如果該節點為null，則該信 不會成為下一個字母
在一個序列中的任何一句話，因為每 字指示它是否是最後
字一個字或不是。
>> 讓我們看一個圖。
希望事情會 有點清晰。
在此圖中，我們看到只有 某些字母及若干子
被列出。
這樣你就可以遵循一定的路徑， 所有這些路徑將導致你
不同的詞。
>> 那麼，我們如何代表在C？
那麼，每一個節點現在將不得不 一個布爾值，表示是否
該節點的端 一個給定的字或沒有。
然後還會有一個數組 所謂的子節點指針，
有將是他們中的27。
請記住，你也想要 保持你的第一個節點的軌道。
我們要調用根。
>> 所以這是一個線索的結構。
我們如何代表這 作為一本字典？
好吧，加載字，每 字典中的單詞，你會想
遍歷線索。
而在孩子的每個元素 對應於不同的字母。
>> 因此，在孩子檢查值 索引i，其中i代表
信的特定索引 你想插入。
好吧，如果這是null，那麼你要 malloc的一個新節點，並有孩子
我指向該節點。
>> 如果它不為null，那麼這意味著， ，鑑於分支，即給定
子，已經存在。
這樣的話你只移動到 新的節點，然後繼續。
如果你在單詞的末尾的 你想在加載
字典，那麼你可以設置 你是在為true當前節點。
>> 因此，讓我們來看看插入的一個例子 單詞“狐狸”到我們
字典。
假裝我們開始 一個空的字典。
第一個字母F，將設 小兒指數五根
兒童數組。
因此，我們插入英寸
>> 然後字母O將在兒童 指標15，這樓後，再進行X
甚至會低於，分支 關中的O的孩子。
然後，因為X是最後一個字母 這個詞的“狐狸”，那麼我要去
顏色是綠色，表示 它是字的末尾。
在C語言中，這將被設定為 字布爾值true值。
>> 現在，如果下一個字，你是 加載中為單詞“富”？
那麼，你不需要用malloc任何更多 空間F或為O，因為
那些已經存在。
但在foo中的最後2 O
那一個，你就必須對malloc。
使該新節點，設置 的是字布爾為true。
>> 所以，現在讓我們將“狗”。狗會 先從根指數3
孩子，因為D有沒有 尚未建立。
我們將遵循類似的過程， 之前，創建子狗，
哪來的G被染成綠色，因為 這是一個字的結尾。
>> 現在，如果我們要插入“做”什麼？
那麼，這是狗的一個子串，所以 我們並不需要將malloc了。
但是，我們需要指出，我們已經 達到該字的結束。
所以O將被標記為綠色。
持續這一過程的每一個 詞在你的字典中，你已經
在加載它們到任何你 哈希表或您的線索。
>> speller.c將通過在字符串 dictionary.c進行檢查。
現在，檢查函數來操作 在不區分大小寫。
這意味著，大寫字母和 小寫字母和兩者的混合
應該都等同於真實的，如果任何 的該組合是在
字典。
您也可以假設字符串 只會包含字母
字符或單引號。
>> 因此，讓我們看看如何可以檢查 用哈希表結構。
好吧，如果存在的話，那麼它 可以在哈希表中找到。
這樣，那麼你可以嘗試尋找 單詞在相關水桶。
>> 因此，這將鬥那個詞是？
好了，你會得到多少，該索引 鏟斗，通過散列該字
然後搜索在該鍊錶， 在整個穿越
鍊錶，使用String 比較功能。
>> 如果鍊錶的末端是 達到了，這意味著你的光標
達到零，那麼這個詞是不是 在字典中找到。
它不會在任何其他桶。
所以在這裡，你可能會看到怎麼有可能 是具有兩種之間的權衡
排序的鍊錶或無序的。
要么會在需要更多的時間 檢查過程中加載或更多的時間。
>> 你會如何檢查 一個線索結構？
我們將向下行進 在特里。
在輸入單詞的每個字母 我們正在檢查，我們去了
對應於孩子元素。
>> 如果該元素為null，則該方法 有沒有子
包含我們輸入字，所以 單詞拼寫錯誤。
如果它不為空，我們可以移動到 我們是這個詞的下一個字母
檢查和繼續這一進程 直到我們到達終點
的輸入字。
然後我們可以檢查 如果是的話是真實的。
如果是，那也不錯。
這個詞是正確的。
但如果沒有，即使該子 存在於字典樹，單詞是
拼寫錯誤。
>> 當函數大小被調用時，大小 應返回字的數目是
在你的字典中給出 數據結構。
所以，如果你正在使用一個哈希表，你 可以通過每一個
鍊錶中的每一個 鬥數著數
話在那裡。
如果您使用的是特里，你可以 經過每一個非空
路徑在您的線索。
或者你正在加載的字典，而 中，也許你可以保持跟踪如何
您正在加載英寸多的話
>> 一旦speller.c完成檢查 對字典的文本文件，然後
它的完成，所以它調用卸載，其中 你的工作是什麼自由
你已經malloced。
所以，如果你使用一個哈希表，那麼你 需要特別小心，以避免
通過不釋放任何內存洩漏 過早和持有到每
之前你免​​單鏈接。
>> 因此，對於在哈希表中的每一個元素 並在鍊錶的每個節點，
你要釋放該節點。
你怎麼去釋放 鍊錶？
設置您的節點指針光標 頭部，以的開頭
鍊錶，那麼當你的光標 不為空，你可以設置一個臨時的
節點指針光標。
然後向前移動光標。
然後你就可以釋放該臨時 價值，同時仍堅持著
一切之後。
>> 如果您使用的是特里什麼？
那麼做到這一點的最好辦法 是從一卸
底部到頂部。
通過旅行到盡可能低的 節點，你可以釋放所有指針
孩子，然後原路返回 向上，釋放所有的所有元素
孩子陣列，直到 你打你的頂級根節點。
這裡就是遞歸 會派上用場。
>> 為了確保你可能已經被釋放 一切，你已經malloced，
您可以使用Valgrind的。
運行Valgrind的運行你的程序 計數的內存多少字節
你使用，並確保你已經 釋放他們，告訴你
在那裡你可能有 忘記了自由。
這樣運行的，一旦Valgrind的告訴你 並為您提供了繼續前進的話
你已經完成卸載。
>> 現在，一對夫婦的秘訣在你走之前 關閉並開始實施你的
字典。
我建議你通過在一個較小的 字典，當你試圖測試
出來的東西和調試國內生產總值。
拼寫檢查器的用法。​​/拼寫檢查器，一個 可選的字典，然後一個文本。
>> 默認情況下，它在加載 大字典。
所以，你可能想通過在小 字典，或者甚至讓你的
自己的，定制你的字典 和你的文本文件。
>> 然後最後，我也建議 拿一支筆和紙，畫
東西出來之前，期間和之後 你寫的所有代碼。
只要確保你有 這些指針恰到好處。
>> 祝你好運。
一旦您完成後，如果你想 挑戰大板和
看看你的程序是如何比較快 你的同學'，那麼我鼓勵
你檢查出來。
>> 就這樣，你已經完成了 在拼寫檢查PSET。
我的名字是Zamyla，這是CS50。