DOUG LLOYD：所以在CS50，我們已經介紹 大量不同的數據結構， 對不對？ 我們已經看到陣列和鏈接 列表和哈希表， 和嘗試，堆棧和隊列。 我們還學了一點 關於樹和堆， 但實際上這些都只是結束 了是變化的一個主題。 真的有這些 樣的四個基本思路 這一切可以歸結為。 數組，鍊錶， 哈希表，和嘗試。 就像我說的，有 一些變化在他們身上， 但是這是非常 多去總結 一切，我們要談 有關本類C的條件 但如何做這些所有的措施了，對不對？ 我們已經討論過的利弊 每對他們單獨的視頻中， 但有很多數字 越來越拋來拋去。 有很多的一般 想法得到拋來拋去。 讓我們嘗試和鞏固 它變成一個地方。 讓我們權衡利弊反對 的利弊，並考慮 該數據結構 可能是正確的數據 結構特定的情形， 什麼樣的數據要存儲。 你不一定總是需要 使用超快速插入，刪除， 和查找一個線索的，如果你真的 不在乎插入和刪除 太多。 如果你只需要快速隨機 訪問，也許一個數組更好。 因此，讓我們提煉出。 讓我們來談談四個的 主要類型的數據結構的 我們已經談到，和 剛看的時候，他們可能是很好的， 當他們也許不會這麼好。 所以，讓我們開始陣列。 所以插入，這是一種不好的。 

在插入數組的結束是確定的， 如果我們建立一個數組，因為我們去。 但是，如果我們需要插入 元素融入到中間， 回想起插入 排序，有很多 中移動在那裡，以適應一個元素。 所以，如果我們要插入 任何地方，但一個數組的末尾， 這可能不是那麼大。 

同樣，刪除，除非我們 刪除從陣列的端部， 恐怕也沒有那麼大，如果 我們不想留出空白的差距， 通常我們不知道。 我們要刪除的元素， 那麼幾分使其再次貼身。 因此刪除從要素 一個數組，也沒有那麼大。 

查找，雖然是很大的。 我們有隨機訪問， 恆定的時間查找。 我們只是說有七個，我們走 陣列搬遷七人。 我們說20，與進入 陣列搬遷20。 我們沒有迭代的對面。 這是相當不錯的。 

陣列也比較容易進行排序。 我們談了排序每次 算法，如選擇排序， 插入排序，冒泡排序，合併 排序，我們總是用數組來做到這一點， 因為數組是很容易 排序，相對於所述的數據結構 我們已經看到了這麼遠。 

他們也比較小。 這裡沒有很多額外的空間。 你只留出完全一樣多的 因為你需要把你的數據， 而這幾乎是它。 因此，他們是非常小 而高效的方式。 但另一個缺點，不過， 是，它們被固定在尺寸。 我們必須明確的聲明如何 大，我們希望我們的陣是， 我們只有一次機會吧。 我們不能增大和縮小它。 

如果我們需要擴大或縮小它，我們 需要聲明一個全新的陣列， 複製所有的元素 第一陣列到第二陣列。 如果我們失算了 的時候，我們需要再次做到這一點。 沒有那麼大。 所以數組不給我們的靈活性 有元素的變量的號碼。 

用一個鍊錶， 插入是很容易的。 我們只是釘到前。 刪除也非常的方便。 我們必須找到的元素。 這涉及到一些搜索。 

但是，一旦你找到了元 你要找的，所有你需要做的 是改變一個指針， 可能是兩個，如果你有 鏈接列表中 - 一個雙 鍊錶，rather-- 然後你可以自由的節點。 你沒有轉移 周圍的一切。 你只需要改變兩個指針， 所以這是相當快。 

查找不好，雖然，對不對？ 為了讓我們能夠找到一個 在一個鍊錶中的元素， 無論是單獨或雙重鏈接， 我們必須線性搜索。 我們必須開始在開始和 移動端，或開始在年底招 到開始處。 我們沒有隨機訪問了。 因此，如果我們做一個 大量的搜索，也許 鍊錶是不 對我們這麼好。 

他們也很 難以理清，對不對？ 只有這樣，你可以 真正排序鍊錶 是排序為你構建它。 但是，如果你解決它，你 構造它，你不再 進行快速插入了。 你不只是套結 東西到前。 你必須找到 合適的地方把它， 然後你插 變得幾乎一樣糟糕 作為插入到一個數組。 所以鍊錶不 因此非常適合對數據進行排序。 

他們還非常小，大小明智的。 雙鍊錶略 比單鍊錶較大， 這是稍大 比陣列，但它不是 大量的空間浪費。 因此，如果空間是非常寶貴的，但 不是一個真正的激烈的溢價， 這可能是正確的道路要走。 

哈希表。 插入到哈希表 是相當簡單的。 它是一個兩步過程。 首先，我們需要通過運行自己的數據 散列函數以獲得散列碼， 然後我們插入元素插入 哈希表在這個哈希碼位置。 

缺失，類似於鍊錶， 很容易，一旦你找到的元素。 你必須先找到它， 但是當你刪除它， 你只需要更換 一對夫婦的指針， 如果你使用的是單獨的鏈接。 如果你使用的探測， 或者如果你不 使用鏈接在所有 在哈希表， 缺失其實是很容易的。 所有你需要做的是哈希 數據，然後去那個位置。 假設你不 有任何衝突， 你就可以很快刪除。 

現在，查找是那裡的東西 變得有點複雜。 它是在平均水平 比鍊錶。 如果您使用的是鏈接， 你還有一個鍊錶， 這意味著你仍然有 搜索有損鍊錶。 但是，因為你把你的鏈接 列表，將其分割在100或1000 或N在哈希表的元素，你 鍊錶都是一個第n的大小。 他們都小得多。 您有n個鏈接列表，而不是 大小n的一個鍊錶。 

所以這個真實世界的不變 因素，一般我們 不要談論時間的複雜性， 沒有真正發揮作用在這裡。 所以查找仍然是線性的 如果你使用的鏈接進行搜索， 但該列表的長度 您正在搜索通過 很相比之下很短。 再次，如果排序是你的 目標這裡，哈希表的 可能不是正確的道路要走。 只需使用一個數組，如果排序 對你真的很重要。 

他們可以運行大小的色域。 這是很難說是否 哈希表是大或小， 因為它實際上取決於 你有多大的哈希表。 如果你只打算將存儲 在哈希表五行， 和你有一個哈希表 在這10,000個元素， 你可能會浪費了很多空間。 作為對比，你也可以 具有非常緊湊的哈希表， 但較小的哈希表得到， 每個那些鍊錶的長 得到。 所以真的沒有辦法定義 完全是一個哈希表的大小， 但它可能是安全的 說這是一般 將是大於鏈接的 列表存儲相同的數據， 但是比線索更小。 

並試圖列第四 這些結構的 我們一直在談論。 插入到一個線索是複雜的。 有很多動態 存儲器分配， 尤其是在開始時， 因為你開始建立。 但它的恆定時間。 這只是人為因素 在這裡，可以很棘手。 說完就遇到空指針，的malloc 空間，去那裡，可能的malloc空間 從那裡了。 的威脅因子排序 在動態內存分配指針 是的障礙清除。 但是，一旦你清除它，插入 其實說到很簡單， 而且可以肯定的是恆定的時間。 

刪除很容易。 所有你需要做的就是導航下來 夫婦指針和自由節點， 所以這是相當不錯的。 查找也非常快。 它只是基於 長度的數據。 所以，如果您的所有數據是 五個字符的字符串， 例如，你存儲5 在線索字符串， 只需要五個步驟 找到你要找的東西。 五是只是一個常數因子，因此 再次，插入，缺失，和查找 這裡都是固定的時間，有效。 

另一件事是，你的線索是 其實那種已經排序，對吧？ 憑藉我們如何是 插入元素， 由信去信 鍵，或數字通過鑰匙位， 通常情況下，你的線索最終被 種排序為您打造它。 它並沒有真正使 有意義的思考整理 以同樣的方式，我們考慮 它使用數組或鍊錶， 或哈希表。 但在某種意義上，你 當您去線索進行排序。 

當然，不利的一面，是 一個線索迅速變得巨大。 從每一個結點，你可能 have--如果你的密鑰由數字， 你有其他10個 地方可以去，哪些 意味著每個節點 包含的信息 有關數據要存儲 在該節點處，加10的指針。 其中，在CS50的IDE，為80個字節。 所以這是至少80個字節 您創建的每個節點， 而這還沒有算上數據。 如果你的節點 字母代替數字， 現在你有26球 從每一個位置。 而26倍8大概是200 字節，或者類似的東西。 你有資本 和lowercase--可以 看到我要與這一點，對不對？ 您的節點可以得到真正 大，所以線索 本身，總體而言，可以 得到真正的大了。 因此，如果空間是在一個較高的 您的系統上的溢價， 一個線索可能不是正確的方式 走，即使它的其他好處 開始發揮作用。 我是道格·勞埃德。 這是CS50。