KEVIN SCHMID：有時候，構建一個時 程序，你可能想利用 稱為字典的數據結構。 字典映射鍵，這是 通常是字符串，將值，整數， 字符，一個指針到某些對象， 任何我們想要的。 這就像普通的字典 那個地圖的話，通過定義。 字典為我們提供了 存儲信息的能力 與相關的東西 後來看看它。 那麼，如何才能真正實現一 字典，比方說，C代碼，我們可以 在我們的計劃之一使用？ 嗯，有很多的方式， 我們可以實現一個字典。 首先，我們可以使用一個數組，我們 動態調整大小，或者我們可以使用一個 鍊錶，哈希表 或二叉樹。 但無論我們選擇，我們應該 銘記效率和 實施的績效。 我們應該想想所使用的算法 插入和查找物品進入 我們的數據結構。 現在，讓我們假設我們 要使用字符串作為鍵。 讓我們來談談一種可能性， 一個數據結構，稱為特里。 所以這裡有一個可視化表示 的線索。 作為圖像顯示，一個線索 是一個樹形數據結構與 節點連接在一起。 我們看到，有清楚的根 節點與一些鏈接延伸到 其他節點。 但什麼是每個節點組成的呢？ 如果我們假設我們正在存儲密鑰 只有字母字符，並 我們不關心資本化， 這裡有一個節點的定義， 就足夠了。 其類型的對象是結構 節點有兩個部分 所謂的數據和兒童。 我們已經離開了數據部分為註釋 由一個部件來代替 申報時結構節點 在C程序中。 一個節點的數據部分可能是一個 布爾值，表示是否 不是節點為完成 的字典鍵或者它可能是一個 表示定義字符串 在字典中的詞。 我們將使用一個笑臉來表示 當數據存在於一個節點。 有26個元素我們 兒童陣列，一個索引 每個字母字符。 我們將看到的意義 這很快。 讓我們根節點仔細看看 在我們的圖表，它沒有數據 與它相關的，由所指示的 沒有在笑臉的 數據部分。 從該部件延伸的箭頭 孩子們數組表示非節點 指針到其他節點。 例如，箭頭從延伸 兒童的第二元件 代表字母B 在字典鍵。 並且在較大的圖 我們用B。貼上標籤 需要注意的是在更大的框圖，當我們 繪製一個指針到另一個節點，它 不要緊其中箭頭 符合該另一節點。 我們的樣本字典包含特里 兩個詞，那和變焦。 讓我們通過一個例子 查找數據的關鍵。 假設我們要查找 為密鑰浴相應值。 我們將開始我們的樣子了 在根節點。 然後，我們將利用我們的第一個字母 鍵，B和找到對應 發現我們的孩子陣列。 請注意，恰好有26點 數組，一個用於每個字母在 字母表。 我們將有斑點代表 字母表中的順序中的字母。 我們來看看第二個索引的話， 索引1，為B。在一般情況下，如果我們 有一些字母字母C我們 可確定相應的點 在使用兒童陣列 計算是這樣的。 我們可以使用一個較大的孩子 如果數組我們希望提供的看看了 具有更廣泛的字符鍵， 如在整個 ASCII字符集。 在這種情況下，指針 在我們的孩子在陣列 指標之一是不為null。 因此，我們將繼續尋找 了關鍵洗澡。 如果我們曾經遇到過一個空指針 在孩子正確點 數組，而我們所走過的節點， 那麼我們將不得不說，我們 找不到任何為關鍵。 現在，我們將採取的第二個字母 我們的關鍵，A，並繼續以下 這樣的指針，直到我們 達到我們的主要的結束。 如果我們達到了關鍵的結束不 擊中任何死角，空指針， 因為是這裡的情況，那麼我們只 必須檢查一件事。 這是真正的關鍵 在字典？ 如果是這樣，我們應該找到一個值，以及一個 在我們的圖表笑臉圖標在那裡 這個詞結束。 如果還有別的東西與存儲 的數據，那麼我們就可以返回。 例如，關鍵動物園不在 字典，即使我們可以有 達到了這個關鍵的結束而沒有 打一個空指針，而我們 遍歷線索。 如果我們試圖尋找出關鍵洗澡時， 倒數第二個節點的數組索引， 對應的字母H，將 舉行一個空指針。 所以洗澡是不是在字典中。 和這樣一個線索是獨特的，該密鑰 從來沒有明確地存儲在 的數據結構。 那麼，我們如何將東西 成特里？ 讓我們來插入鑰匙 動物園到我們的線索。 請記住，在一個節點一個笑臉 可以在代碼中對應於一個簡單的 Boolean值，表明動物園 在字典中，或者它可以 對應的詳細信息，我們 希望與關鍵動物園相關聯， 類似的定義 字或別的東西。 在某些方面，這個過程要插入 事成特里類似於 仰視的東西在特里。 我們先從根節點再次， 對應下面的指針 我們主要的字母。 幸運的是，我們能夠跟隨指針 所有，直到我們到達方式 該鍵的末端。 由於動物園是這個詞的前綴 變焦，這是其中一個成員 字典，我們不需要 分配任何新的節點。 我們可以修改節點，以指示 字符導致的路徑 它代表了我們的字典的一個關鍵。 現在，讓我們嘗試插入 關鍵沐浴到特里。 我們將開始在根節點 並再次跟隨指針。 但在這種情況下，我們打一個死 最終我們能夠到達之前 關鍵的結束。 現在，我們需要分配一些新的 節點需要分配一個新的 節點的每個剩餘 我們的主要的信。 在這種情況下，我們只需要 分配一個新的節點。 然後，我們將需要使H指數 引用該新節點。 再次，我們可以通過修改節點 顯示的字符的路徑 導致它代表一個 關鍵在我們的字典。 讓我們來推理漸近 我們的程序，這些複雜性 兩個操作。 我們注意到，在這兩種情況下的數 步驟我們的算法是拿了 成比例的數量 信中的關鍵字。 這是正確的。 當你想查找的單詞 特里，你只需要遍歷 字母一個接一個，直到您 達到該字的結尾或 在特里打了一個死胡同。 而當你想插入一個關鍵 值對成特里使用 過程中，我們討論了，最壞的情況下 將你分配一個新節點 每個字母。 我們將假設分配 是一個常數時間的操作。 所以，如果我們假設密鑰長度為 由一個固定的常數，二者有界 插入和查找是不變的 運營時間為線索。 如果我們不做出這種假設， 密鑰的長度是由一個固定的範圍內 常數，則插入和查詢， 在最壞的情況下，是線性的 長的關鍵。 請注意，保存的項目數量 在該線索不影響它的外表向上 或插入時間。 它只能由受影響 長的關鍵。 相比之下，添加條目，比方說， 哈希表往往使 未來看起來更慢。 雖然這聽起來吸引人起初， 我們應該記住，一個 有利的漸近複雜性不 意味著在實踐中，數據 結構是必然 無可非議。 我們還必須考慮到存儲 字在字典樹，我們所需要的，在最壞的 情況下，節點數量成比例 於字本身的長度。 嘗試傾向於使用大量的空間。 這是相對於一個哈希表， 在這裡我們只需要一個新的節點 存儲一些鍵值對。 現在，再從理論上講，空間大 消費似乎並不像一個大 處理，特別是考慮到現代 電腦有千兆字節和 GB的內存。 但事實證明，我們仍然有 不用擔心內存使用和 組織為求 性能，因為現代計算機 有下建立了相關機制 油煙機，以加快內存訪問。 但這些機制最好的工作時 內存訪問是在緊湊的製作 區域或地區。 和特里的節點可以駐留 在堆中的任何地方。 但這些都是權衡 我們必須考慮的問題。 請記住，選擇一個數據時， 結構有一定的任務，我們 應該想想什麼樣的 操作的數據結構需要 支持和多少的性能 這些每個的 操作事項給我們。 這些操作可能連 超越只是 基本外觀和插入。 假設我們要實現一個樣 自動完成功能，多 像谷歌搜索引擎一樣。 也就是說，退還所有鑰匙和 潛在的價值觀， 有一個給定的前綴。 字典樹是唯一有用的 進行此操作。 這是簡單的遍歷 該線索進行的每一個字符 前綴。 就像一個查找操作， 我們可以遵循的指針 逐個字符。 然後，當我們在的底到達 前綴，我們可以遍歷 該數據結構的其餘部分 因為任何按鍵超越 這點有前綴。 它也很容易得到此房產 自中按字母順序 孩子們數組中的元素 按字母順序排序。 所以希望你們能考慮 捐贈試圖一試。 我是凱文·施密德，這是CS50。 啊，這是開始 的下降。 對不起。 抱歉。 抱歉。 抱歉。 罷工四人。 我走了。 抱歉。 抱歉。 抱歉。 對不起，讓誰的人 要編輯這個發瘋。 抱歉。 抱歉。 抱歉。 抱歉。 揚聲器1：幹得好。 這是真的做得很好。