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。