[音樂播放]
>> DAVID馬蘭：這是CS50。
這是二者的開始和 end--像literally--差不多結束
六個星期。
>> 我想我會分享 一個有趣的事實點點。
我從一本拉到了 過去學期的數據集。
你可能還記得，我們​​要求你在每個 P組的形式，如果你已經在網上看過
或者，如果你已經親自出席。
這裡是數據。
所以今天是非常可預測性。
但是，我們想花一點 然而時間與您聯繫。
有人想猜測為什麼這個 圖中是那麼的鋸齒，上下，上下，
所以一貫？
做什麼每個峰 和波谷代表什麼？
>> 聽眾：[聽不清]
DAVID馬蘭：確實是這樣。
而更有趣的是，上帝保佑， 我們舉行一次講座上週五
在學期的開始， 這就是我們看到發生了什麼。
所以今天，我們參加了位 更多關於數據結構。
並給你更多的是固體 對問題的思維模式五，
這就是現在了。
拼寫錯誤，其中，我們將 交給你一個文本文件，大約10萬
再加上英語單詞， 你將有
弄清楚如何巧妙地加載它們 入存儲器，到RAM中，使用一些數據
您所選擇的結構。
>> 現在，這樣的一個數據結構可以 是，但可能不應該，
在相當簡單的鍊錶， 這是我們去年推出的時間。
和一個鍊錶至少有 1優勢的陣列。
什麼是一個優點 鍊錶可以說是？
>> 聽眾：插入。
>> DAVID馬蘭：插入。
你是什​​麼意思？
>> 聽眾：任何位置 名單[聽不清]。
>> DAVID馬蘭：好。
所以，你可以插入一個元素的地方 要在列表的中間
無需洗牌什麼， 我們得出的結論，在我們的分類
討論，是不是 一定是好事，
因為它需要時間來實際移動 所有這些人的左邊或右邊。
所以用一個鍊錶，你可以 剛分配使用malloc，一個新的節點，
然後更新了幾個 pointers--二，三次手術max--
而我們能夠插槽人 中的任意位置成一個列表。
>> 還有什麼是有利的 關於鍊錶？
是嗎？
>> 聽眾：[聽不清]
DAVID馬蘭：完美。
完美的。
這真是動力。
和你沒有犯， 事先，以一些固定的大小
內存塊，就像你會 用一個數組，則上行其中
是，你只能分配上的節點 需求從而只用盡可能多的空間
當你真正需要的。
通過與數組相反，你可能會 一不小心分配太少。
然後它只是去 是在頸部疼痛
重新分配一個新的更大的陣列中，複製 一切都結束了，釋放舊陣列，
然後將您的業務。
或者更糟的是，你可能會分配方式 更多的內存比實際需要，
所以你將有一個非常 人煙稀少的陣列，可以這麼說。
>> 因此，一個鍊錶為您提供了這些 活力和靈活性的優勢
與插入和缺失。
但肯定要有付出了代價。
其實，一個主題 探索對測驗為零
一對夫婦的取捨 我們已經看到迄今。
那麼，什麼是付出了代價或 下行的鏈接列表？
是啊。
>> 聽眾：沒有隨機訪問。
>> DAVID馬蘭：沒有隨機訪問。
但誰在乎呢？
隨機存取聽起來並不引人注目。
>> 聽眾：[聽不清]
DAVID馬蘭：沒錯。
如果你想有 一定的算法 -
讓我真正提出 在特定的二進制搜索，這
是我們使用相當bit-- 如果你沒有隨機訪問，
你不能這樣做簡單的算術題 找到喜歡的中間元件的
和跳躍的權利吧。
你代替不得不開始在所述第一 元素，並從左邊線搜索
向右如果你想找到 中間的或任何其他元件。
>> 聽眾：它可能需要更多的內存。
>> DAVID馬蘭：需要更多的內存。
哪裡是額外的 成本從內存中來？
>> 聽眾：[聽不清]
DAVID馬蘭：沒錯。
在這裡這種情況下，我們有 鍊錶為整數，
但我們正在加倍 的內存量
我們需要同時存儲這些指針。
現在少了一個大問題，因為 您的結構得到較大
與你存儲不是一個數字，但 也許學生或其他物體。
但有一點毫無疑問依然存在。
等數的操作的 上鍊錶被稱為
是N--線性的大O。
之類的東西插入或搜索 或缺失的情況下的元素
正好是在最末端 無論是排序或不列表。
>> 有時候，你可能會得到幸運和 這些操作使下界
也可能是恆定的時間，如果你 一直在尋找的第一個元素，
例如。
但最終，我們承諾 實現了制勝法寶
數據結構，或 一些近似物，
通過固定時間的方式。
我們可以發現元素或添加元素 或刪除列表中的元素？
我們將很很快就會看到。
而事實證明，一個 我們的機制
要開始用至今， 在P年利用設置5，
實際上是非常熟悉的。
例如，如果這是一串 考試圖書，其中每一個
有一個學生的第一 它的名字和姓氏，
我去接他們從 在考試結束後，
而且他們都非常 多以隨機的順序，
我們要著手整理 這些考試，因此一旦分級
它只是一個極大的方便， 快交出他們回來了
學生按字母順序排列。
什麼你的直覺會 一摞這樣的考試？
>> 好吧，如果你像我一樣，你 可以看出這是米，
所以我要那種把這個成， 如果這是我的表或我的樓，
我的東西蔓延 out--或我的數組really--
我可以把所有的小姐在那裡。
呵呵。
這裡有一個答，所以我可能 把作為過來。
呵呵。
這裡的另一個A.我要去 把該在這裡。
這裡有一個Z.這裡是另一個M.所以 我可能會開始做樁這樣的。
然後，也許我以後會去 樣的，非常挑剔-LY排序
個別樁。
但問題是，我想看看 那個我手輸入
我會做一些計算 基於該輸入決定。
如果以A開頭，把它放在那邊。
如果它以Z開頭，把它放在 在那裡，一切都在兩者之間。
>> 因此，這是一種技術，是 一般被稱為hashing-- H-A-S-H--
這通常意味著要為 輸入，並使用該輸入來計算
的值，通常是一個數字，那 號為索引到一個存儲
容器，如一個數組。
所以，換句話說，我可能有一個 散列函數，像我一樣在我的腦海，
如果我看到有人的 誰的名字開始與A，
我要去映射 零在我的腦海。
如果我看到有人用Z，我 要映射至25日在我頭上
然後它放入 最後最樁。
>> 現在，如果你覺得不是我的大腦 但一個C程序，有什麼數字可能
你靠什麼來實現同樣的結果呢？
換句話說，如果 有ASCII字符A，
你如何確定 什麼桶把它呢？
你可能不希望 把它放進水桶65，這
會像那邊 沒有很好的理由。
你在哪裡要放 在它的ASCII值是多少？
你想去哪裡做的ASCII 值拿出一個更聰明的水桶
把它呢？
>> 聽眾：負A.
>> DAVID馬蘭：是啊。
因此，減去或減 特別是65，如果是
資本A.或98，如果 這是一個小寫。
所以這將允許我們，很 簡單，非常算術，
把東西放到這樣一個水桶。
所以，事實證明，我們實際上做 這個問題，以及即使有測驗。
>> 所以，你可能還記得你的盤旋 封面上的教學老鄉的名字。
而TF的名字被組織 到這些列的字母順序，
好了，不管你信不信， 當所有80加上我們
聚在一起的那天晚上等級， 在我們的分級過程中的最後一步
是散列測驗變成了大 地板在[聽不清]空間
並奠定了大家的測驗出來 在他們TF的確切順序
在蓋的名稱，因為 那麼它對於我們來說容易得多
通過使用線性搜索 搜索或某種聰明
對於TF找到他或 她的學生的測驗。
>> 所以這個想法散列 你將看到的是
功能相當強大實際上是非常 司空見慣，非常直觀，
很像也許是分而 征服是零一周。
我快進到黑客馬拉松 幾年前。
這是Zamyla和一對夫婦的 其他工作人員的問候學生
因為他們進來了。
我們有一大堆折疊 表中有與名稱標籤。
我們有名稱標籤組織 有喜歡當那邊
和ZS的那邊。
這樣一來，課題組的一個非常巧妙 寫這個的說明
為天。
而在本學期的第12週 所有的非常有意義，每個人都
知道該怎麼做。
但是，任何時候，你已經 排隊以同樣的方式，
你實現 散列相同的概念。
因此，讓我們正式那麼一點點。
這裡是一個數組。
它繪製的是一個小 寬只是描繪，直觀，
我們不妨把字符串 在這樣的事情。
這陣 顯然是大小共26件。
而且東西被稱為 表隨意。
但是，這僅僅是一個藝術家的再現 什麼樣的哈希表可能。
>> 這樣一個哈希表現在將要 是一個更高層次的數據結構。
在一天結束時 我們即將看到你
可以實現一個哈希表，該表 很像登機
在黑客馬拉松就像這樣 表用於排序的考試書籍。
但一個哈希表 這個排序高水平的
概念，可以使用一個數組 在底層實現它，
或者它可以使用一個長列表，或者甚至 也許一些其他的數據結構。
而現在這就是theme--回吐 一些基本的成分
就像一個數組，這個建築 現在阻止長名單
，看到什麼，我們可以建立 關於這些的頂端，像成分
成一個配方，使得越來越多的 有趣的和有用的最終結果。
>> 所以用哈希表 我們可以實現它
在內存中形象地這樣，但 怎麼可能它實際上被編碼嗎？
好吧，也許因為簡單地說就是這個。
如果產能全部大寫，只是 一些constant--比如26，
為alphabet--的26個字母 我可以叫我的變量表，
我也許會說，我要去 把炭明星在那裡，或字符串。
因此，它是如此簡單，如果你 要實現一個哈希表。
然而，這真的只是一個數組。
但同樣，一個散列 表是現在我們所會
調用一個抽象數據類型，這只是 排序在最前面的概念分層
東西更現實 現在喜歡一個數組。
>> 現在，該怎麼辦才好 關於解決問題？
嗯，剛才我已經奢侈 這裡有足夠的表空間
這樣我就可以把 測驗的任何地方我想要的。
這樣可能會去這裡。
ZS可能會去這裡。
小姐可能會去這裡。
然後我有一些額外的空間。
但是，這是一個有點作弊權 因為現在這個表，如果我真的
想到這是一個數組，只是 一些將要固定的尺寸。
>> 所以，從技術上說，如果我拉 了另一名學生的測驗
看看，哦，這個人的 名稱與A開始過，
我有點想要把它放在那裡。
但是，當我把它放在那裡，如果 這個表確實表示一個數組，
我會被覆蓋或重挫 誰該學生的測驗是。
對不對？
如果這是一個數組，只有一件事可以 走在這些細胞或元件。
所以，我種有 挑選。
>> 剛才那種下面我 被騙了，做這個還是我
只是一種堆疊 他們在彼此之上。
但是，這並不是要在代碼中飛翔。
那麼，我能放 第二個學生的名字
是A，如果所有我是這樣的 可用的表空間？
而且我用三個插槽，它 貌似有只是少數人。
你該怎麼辦？
聽眾：[聽不清]
DAVID馬蘭：是啊。
也許我們只是保持簡單。
對不對？
它不適合在這裡我想把它。
所以我打算把它放在 技術上，其中A，B會去。
當然，現在，我開始 畫自己陷入了困境。
如果我去一個學生 他的名字實際上是B，
現在乙將要被移動一點點 未來，為可能發生的事情，是的，
如果這是一個B中，現在它已去這裡。
>> 所以這非常迅速 可能成為問題，
但它是一個技術，實際上是 被稱為線性探測，
因此你只要考慮你 陣列是沿著線。
正中下懷，你探頭或 檢查每個可用的元素
尋找一個備有現貨。
而且只要你找到 1，你在那裡將其刪除。
>> 現在，這個價格現在正在支付 這個解決方案是什麼？
我們有一個固定大小的數組， 當我插入的名字
進去，至少在最初階段，有什麼 插入的運行時間
為把學生 在右邊的桶測驗？
什麼大O？
>> 聽眾：N。
DAVID馬蘭：我聽說的n大O。
事實並非如此。
但我們將梳理出 為什麼在短短的一瞬間。
還有什麼會是什麼？
>> 聽眾：[聽不清]
DAVID馬蘭：讓我做視覺。
因此，假設這是字母S.
>> 聽眾：這是之一。
DAVID馬蘭：這是之一。
對不對？
這是一個數組，它 意味著我們有隨機訪問。
如果我們認為這 零，這為25，
我們認識到， 哦，這是我的輸入S，
我當然可以轉換 S，一個ASCII字符，
到一個相應的數字 零到25之間
然後立即 把它原來的位置。
>> 但當然，當我到達 第二個人誰的名字是A或B或C
最後，如果我用了 線性探測作為我的解決方案，
的運行時間 插入在最壞的情況下
實際上是要下放成什麼樣？
我也聽到了這裡 正確的早期。
聽眾：[聽不清]
DAVID馬蘭：所以這是正確一次 有一個足夠大的數據集。
這樣，一方面，如果 陣列足夠大
和你的數據是稀疏的話，你 得到這個美麗的固定時間。
但只要你開始 越來越多的元素，
而只是統計上你 更多的人信
A作為自己的名稱或字母 B時，它可能潛在
下放成更線性的。
所以，不是很完美。
所以，我們可以做的更好？
>> 那麼，什麼是我們的 之前的解決方案時，我們
希望有更多的比活力 像一個數組允許的？
聽眾：[聽不清]
DAVID馬蘭：沒有介紹什麼？
是啊。
這樣一個鍊錶。
好吧，讓我們看看一個鏈接 清單可能對我們不是做的。
那麼，讓我建議大家 畫圖如下。
現在這是一個不同的 從例圖
從不同的文本，實際上，這 實際上是用粒度31的陣列。
而筆​​者簡單 決定散列字符串
不基於該人的姓名， 但基於其生日。
不論該月，他們得出 如果你在第一次一個月的正在誕生
或一個月的31日，筆者 基於該值會出現亂碼，
從而被散佈的名字出一個位 不僅僅是26點可能會允許。
也許這是一個小更均勻 比用字母去，
當然，因為有可能 更多的人在世界上的名字
開始的被肯定比 其他一些英文字母。
所以，也許這是一個小 更均勻，假定
均勻分佈 的嬰兒跨越了一個月。
>> 但是，當然，這仍然是不完美的。
對不對？
我們有衝突。
多人在這 數據結構仍然
具有相同的出生日期的至少 你不論一個月。
但什麼筆者做了什麼？
好吧，看來我們有一個數組 在左側的垂直繪製，
但是這只是一個藝術家的再現。
不要緊，什麼方向，你 畫一個數組，它仍然是一個數組。
這是什麼的顯然是一個數組？
>> 聽眾：鍊錶。
>> DAVID馬蘭：是啊。
它看起來像它的一個 陣列的鍊錶。
如此反复，這點排序 利用這些數據結構現在的
作為成分更多 有趣的解決方案，
你完全可以採取 基本一樣的陣列，
然後拿更多的東西 有趣像一個鍊錶
甚至將它們組合成一個更 更有趣的數據結構。
事實上，這也將 被稱為哈希表
由此，陣列是 真哈希表，
但是哈希表中有 鏈，可以這麼說，
可增大或縮小基礎上， 你想要的元素的數量插入。
>> 現在，因此，什麼是 在運行的時候嗎？
如果我要插入人 他的生日是10月31日，
在那裡他或她去嗎？
行。
在最底層的地方說31。
這就是完美的。
那是一定的時間。
但是，如果我們發現了什麼別人 他的生日，讓我們來看看，
十月，十一月，十二月三十一日止？
哪裡是他或她會去嗎？
同樣的事情。
兩步雖然。
這是恆定的，雖然不是嗎？
行。
目前，它是。
但在一般情況下， 越來越多的人加入我們，
概率，我們要 得到越來越多的碰撞。
>> 現在，這是一個小 更好，因為在技術上
現在我的連鎖店可以在 在最壞的情況下多久？
如果我插入N多人進入這個多 複雜的數據結構，N多人，
在最壞的情況下，它會為n。
為什麼呢？
>> 聽眾：因為如果每個人都 有相同的生日，
他們將成為一條線。
DAVID馬蘭：完美。
這可能是一個有點做作， 但真正在最壞的情況下，
如果每個人都擁有相同的生日， 給你的投入，
你將有一個 大量的長鏈。
所以，你可以把它稱為一個 哈希表，但實際上它是
只是一個大規模的鍊錶 一大堆浪費的空間。
但在一般情況下，如果我們假定 至少生日是uniform--
它可能不是。
我正在做這件事。
但是，如果我們假定，對於 就事論事
它們是，那麼在理論上，如果 這是垂直的表示
數組的，那麼希望你 將得到的是，你知道鏈，
大致相同的長度，其中每個 這些代表月中的某一天。
>> 現在，如果有31天的月份， 這意味著我的運行時間真的
為n超過31大O，這 感覺比線性好。
但是，什麼是我們的一個 承諾一兩個星期
以前，每當它來表達 一個算法的運行時間？
剛剛只看高次項。
對不對？
31絕對是有幫助的。
但是，這仍然是n個大O。
但主題之一 問題設置5
將是對 承認絕對的，
漸近，理論上 這種數據結構
沒有比剛剛好 一台龐大的鍊錶。
而事實上，在最壞的情況下，這 哈希表可能下放成。
>> 但在現實世界中，我們人類 那自己的Mac或PC或其他
而正在運行真實世界 軟件在真實世界中的數據，
該算法你要選哪個？
而其中，需要結束步驟或 一種採用N以31級分
找一些數據塊或 找了一些資料？
我的意思是，絕對是31品牌 在現實世界中的差。
這是快31倍。
而我們人類是肯定 要明白這一點。
>> 因此，實現二分法 之間居然有
說起理論上的東西 和漸近這無疑
具有價值，因為我們已經看到， 但在現實世界中，
如果你關心只是使 人類對幸福的通用輸入，
你很可能要接受 事實證明，是的，這是線性的，
但它的速度更快31倍 比線性可能。
而且更重要的是，我們不只是要 做一些亂像一個生日，
我們可以花一點 更多的時間和聰明
想想我們可能會做， 定一個人的名字，也許
他們的出生日期相結合的 成分搞清楚的東西
這是真正的多 均勻，少鋸齒，
這麼說不是這幅畫 目前表明它可能是。
在代碼中，我們如何才能實現呢？
那麼，讓我建議大家 只是借用一些語法，我們已經
使用幾次迄今。
我要去定義 一節點，該節點再次
是一個通用術語，只是一些 容器為一些數據結構。
我要建議 字符串會在那裡。
但是，我們要開始服用 這些培訓輪子掉了。
>> 沒有更多的CS50庫 真的，除非你想
將其用於您的最終 項目，這是好的，
但現在我們要拉回來了 窗簾，說這只是一個char明星。
所以這個詞有將是 有問題的人的名字。
現在我有一個鏈接 這裡下一個節點
使這些代表 每個節點
在鏈中，潛在地， 的一個鍊錶。
>> 現在該怎麼辦，我宣布 哈希表本身？
我如何申報這整個結構？
好了，說真的，就像我用一個指針 以列表的只是第一元件
之前，同樣我能說 我只需要一堆指針
實現這整個哈希表。
我將有一個數組 所謂表為哈希表。
這將是規模生產能力。
這就是很多元素可以適應它。
並且每個在此這些元素的 陣列將是一個節點的明星。
為什麼呢？
那麼，每個這張照片，就是我 執行哈希表作為
有效地在一開始僅僅是 這個數組，我們已經垂直繪製，
其每個的平方 代表一個指針。
那那些有斜杠 通過他們只是空。
和那些有 箭頭要正確
在實際指向實際的節點， 人體工程學的鏈接列表的開始。
>> 所以在這裡的話，我們怎麼可能 實現一個哈希表，該表
實現獨立的鏈接。
現在，我們可以做的更好？
好吧，我答應最後一次 我們可以實現一定的時間。
我種了你 固定的時間在這裡，
但後​​來說不是真的 固定的時間，因為它仍
依賴於總上 元件的數目
你輸入到 的數據結構。
但是，假如我們這樣做。
讓我回到屏幕在這裡。
也讓我在這裡預測這件事，清楚 在屏幕上，並且假設我這樣做。
假設我想插入的名字 Daven在為我的數據結構。
>> 所以我想插入一個字符串 Daven成的數據結構。
如果我不使用什麼 哈希表，但我用
一些更樹狀 就像一個家族樹，其中
你有一些根本的 頂部，然後節點和葉
那去向下和向外。
假設這時，我才 要插入Daven的
到什麼是當前一個空列表。
我要做到以下幾點：我 要在這個家庭創建節點
樹狀數據結構，它看起來 有點像這樣的，其中每一個
矩形有，比方說， 現在26在裡面的元素。
和每個小區的 在這陣是怎麼回事
代表字母表的字母。
>> 具體來說，我要去治療 這是A，那麼B，然後是C，則D，
這一個在這裡。
所以這將有效地 代表字母D.
但插入所有Daven年代 名字我需要做多一點。
所以我首先要散列，可以這麼說。
我要去看看第一個字母 在Daven的這顯然是一個D，
我要去分配 看起來一個節點
像this--一個大的矩形大 夠以適應整個字母表。
>> 現在D被完成。
現在A. D-A-V-E-N是目標。
所以，現在我什麼都做的就是這一點。
當我開始D的通知 沒有指針那裡。
這是垃圾值的那一刻， 或者我可以把它初始化為空。
不過，讓我趕上去 這個想法建立一個樹。
讓我分配一個又一個的這些 節點中有26個元素。
>> 你知道嗎？
如果這僅僅是在存儲器中的節點 我使用malloc創建，用一個struct
因為我們很快就會看到， 我該怎麼辦this--
我會從畫一個箭頭 這代表的D-下來的東西
該新節點。
而現在，第一個下一個 信Daven的名字，
V-- D-A-V--我要繼續前進 並得出另一個節點是這樣，
由此，此處的V族元素，其 我們將繪製的instance--哎呦。
我們不會畫在那裡。
它會去這裡。
>> 然後，我們要 認為這是V.
再往下在這裡我們要索引 下來從V到我們會考慮E.
然後從這裡，我們要 去這裡有這些節點之一。
現在我們有一個問題來回答。
我需要以某種方式表明， 我們在字符串Daven的結束。
所以，我可以把它空。
>> 但是，如果我們有Daven的 全名也，其
是，正如我們已經說過，達文波特？
所以，如果Daven是什麼 實際上是一個子串，
一個更長的字符串的前綴？
我們不能僅僅永久 什麼也不說是怎麼回事
去那裡，因為我們可以 切勿將像達文波特一個字
入該數據結構
>> 所以，我們可以做的是 把這些元素
因為也許有兩個 他們中的元素。
一個是一個指針，的確， 因為我一直在做。
所以每個這些框 不只是一個小區。
但是，如果頂部 埃德蒙頓底部一個人的
要為null，因為 有沒有達文波特，只是還沒有。
如果那頂一個 為一些特殊的價值？
而這將是一個小 很難得出它這種規模。
但是，假如它只是一個复選標記。
檢查。
D-A-V-E-N是一個字符串 在此數據結構中。
>> 同時，如果我有更多的空間 在這裡，我所能做的P-O-R-T，
我可以把檢查的節點 有字母T在最後。
因此，這是一個大規模 複雜的外觀的數據結構。
和我的筆跡 肯定沒有幫助。
但是，如果我想插入的東西 否則，考慮一下我們會怎麼做。
如果我們希望把大衛， 我們會遵循同樣的邏輯，D-A-V，
但現在我想指出，在未來 元素不是從E，但是從我到D.
因此，有將是 在這棵樹多個節點。
我們將不得不調用malloc更多。
但是，我不想做一個 這幅畫的一塌糊塗。
所以讓我們來看看1 一個已經預先制定
像這樣與不點，點， 點，但只是略陣列。
但每個節點 在這棵樹在這裡
表示同一件事 - 數組的大小26雷。
>> 或者，如果我們想成為 現在真的很合適，有什麼
如果某人的名字 一個撇號，讓我們
假設每個節點實際上具有 像27指數在裡面，不只是26。
所以這個現在將是一個數據 結構稱為trie-- T-R-I-E。
一個線索，這是假想 歷史上的一棵樹一個聰明的名字
這對優化 當然，檢索，其中，
拼寫與I-E所以它的線索。
但是，這是對線索的歷史。
>> 因此，一個線索是這樣的樹狀數據 就像一個家庭樹結構
最終表現那樣。
這裡是一個又一個的例子 一大堆別人的名字。
但現在的問題 手頭有什麼
我們獲得了通過引入可以說是一個更 複雜的數據結構，和一，
坦率地說，使用了大量的內存。
>> 因為即使， 此刻，我只
使用D的指針和 A和V和ES和NS，
我在浪費大量的內存赫克。
但是，在這裡我度過一個資源， 我傾向於不爭回另一個。
所以，如果我花了更多的空間， 什麼是可能的希望嗎？
那我花少了什麼？
聽眾：更少的時間。
DAVID馬蘭：時間。
現在為什麼會這樣呢？
那麼，什麼是插 時間，在目前大O方面，
像Daven一個名字 或者達文波特還是大衛？
好吧，Daven是五個步驟。
達文波特將九個步驟， 所以這將是一個幾個步驟。
大衛將五個步驟為好。
因此，這些都是具體的 數字，但肯定有
的上限的 長別人的名字。
而事實上，在該問題 台五規範，
我們要提出 它的東西
這是40-一些多字符。
>> 實際上，沒有人有 一個無限長的名字，
這就是說，一個長度 名稱或字符串的長度，我們可能
有一定的狀態 結構可以說是什麼？
這是不變的。
對不對？
這可能是一個很大的不變樣 40多歲的，但它是恆定的。
它有多少不依賴 其它名稱是在該數據結構中。
換句話說，如果我 想現在插入
科爾頓或加布里埃爾或搶或Zamyla或 艾莉森或貝琳達或任何其他名稱
從工作人員到該數據 結構，是在運行時間
中插入其他名稱 將要在所有受影響的
被多少其他元素 在已經將數據結構？
它不是。
對不對？
由於我們有效地利用 這個多層哈希表。
和運行時間 這些操作
取決於不上的數 這是在數據結構中的元素
或者被最終將 是在數據結構中，
但在什麼具體的長度是多少？
>> 該字符串是 插入，這確實讓
這種漸進恆 一時間 - 大O。
坦率地說，就在 現實世界中，這
指插入Daven的名字取 像五個步驟，或者達文波特9
步驟或大衛五個步驟。
這是相當不錯的小的運行時間。
而且，事實上，這是一個非常 好東西，尤其是當
它不依賴於總量 在那裡的元素個數。
那麼如何才能實現我們這個 這種結構的代碼？
這是一個多一點 複雜，但它仍然是
只是一個應用 基本構建塊。
我要重新定義 我們節點如下：
布爾稱為word--這 可以被稱為什麼。
但布爾代表 我畫了一個對號。
是。
這是一個字符串的末尾 在此數據結構中。
>> 並且，當然，節點星 有指兒童。
而且，事實上，就像 一個家譜，你
會考慮節點 被掛
一些家長的底部 元素是兒童。
這樣一來，孩子們將要 是27的數組，第27屆1
擺明了撇號。
我們要進行排序 的特殊情況。
所以，你可以有一定 名稱以撇號。
甚至連字符應 去那裡，但你
見P組5，我們只關心 有關信件和單引號。
>> 然後你怎麼代表 數據結構本身？
你怎麼代表根 這個線索的，可以這麼說？
嗯，就像一個鍊錶，你 需要一個指針的第一個元素。
有線索，你只需要1 指向此線索的根。
從那裡，你可以散列 你的路陷的越來越深
以在結構中每一個其他節點。
因此，簡單地用這個就可以 我們代表的結構。
>> 現在Meanwhile--呵呵，問題。
>> 聽眾：什麼是布爾字？
>> DAVID馬蘭：BOOL字 只是這款C化身
什麼，我描述 在這裡，在這個盒子
我開始分裂各 數組的元素分為兩部分。
之一是一個指向下一個節點。
其它必須是 類似的複選框
要說的是，有一個 字Daven說到此為止，
因為我們不想要的， 此刻，戴夫。
>> 即使戴夫將是一個 合法的一句話，他不是在特里
還沒有。
和D是不發一言。
和D-A是不是一個單詞或一個名稱。
因此，复選標記 表示只有當你
打這個節點是 字符前面的路
實際上，你已經插入一個字符串。
這就是所有的布爾 那裡是做給我們。
>> 在嘗試任何其他問題？
是啊。
>> 聽眾：什麼是重疊？
如果你有一個戴夫和Daven？
DAVID馬蘭：完美。
如果你有一個戴夫和Daven？
所以，如果我們插入，說一個綽號， 對於David-- Dave-- D-A-V-E？
其實，這是超級簡單。
因此，我們只是要帶四個步驟。
D-A-V-E。和我有什麼要 做一次，我打了四節點？
只是去檢查。
我們已經好到哪裡去。
完成的。
四個步驟。
固定時間漸近。
現在我們已經表明，無論戴夫 和Daven是在結構中的字符串。
所以不存在問題。
並注意存在 Daven的沒能
需要更多的時間或更少 時間戴夫，反之亦然。
>> 那麼還有什麼可以，現在我們怎麼辦？
我們以前使用過這個隱喻 托盤代表什麼。
但事實證明，一個 托盤堆實際上是
示範的另一個抽象數據 類型 - 一個更高層次的數據結構
這在最後的日子就是 像陣列或鏈接的列表
什麼更現實。
但它是一個更有趣 概念的概念。
堆棧，這樣的 托盤在這裡馬瑟
通常被稱為 只是that--堆棧。
>> 並且在這種類型的數據結構 你有兩個operations--
你有一個叫推 添加的東西到堆棧，
就像把另一盤 備份在堆棧的頂部。
然後彈出，這意味著你 把最上面的托盤掉。
但是，什麼是關鍵關於堆棧是 它有這種奇怪的特點。
由於食堂工作人員 重新排列的托盤為下一頓飯，
這是怎麼回事是 真正了解學生如何
這種數據結構進行交互？
聽眾：他們將彈出一關。
DAVID馬蘭：他們要去 彈出一關，希望上面。
否則，它只是一種愚蠢 一路走到底。
對不對？
該數據結構並沒有真正允許 你至少要搶底盤
很容易。
因此，有這種奇怪的 屬性堆棧
在最後一個項目是 將成為第1列。
和計算機科學家稱之為 這LIFO--後進先出。
它實際上確實有 有趣的應用程序。
它並不一定那麼明顯一些 其他人，但它確實能是有用的，
它確實能實現 在幾個不同的方式。
>> 所以一個，實際上，讓 我不要潛入了。
讓我們這樣做吧。
讓我們來看看一個幾乎在 同樣的想法，但它是一個更公平一點。
對不對？
如果你是這些球迷的一個男孩或 女生真的喜歡蘋果產品
而你在上午03點00分就醒了 排隊在一些商店
獲得最新的iPhone，你 可能排隊這樣的。
>> 現在隊列很刻意的名字命名。
這是一條線，因為有 一些公平吧。
對不對？
種它將如果你吸 到了那裡在Apple Store第一
但你有效的最底部 托盤是因為蘋果公司的員工，然後
流行的最後一個人誰 實際上得到的線。
因此，棧和隊列，即使 在功能上，他們是那種same--的
它只是這個集合 資源，這是
要發展和shrink--還有的 這種公平性方面吧，
至少在現實世界中， 其中，操作你鍛煉
是根本不同的。
一個stack--隊列 rather--據說有
兩個操作：N隊列和D隊列。
或者你可以給他們打電話 任何數目的東西。
但是，你只是想捕捉 一個是增加的概念
和一個最終被減去。
>> 現在的發動機罩的下面，兩者的堆棧 和隊列可以實現怎麼樣？
我們不會進入代碼 這是因為在較高的水平
思想是那種比較明顯。
我的意思是，人類該怎麼辦？
如果我是第一人，在蘋果 存儲，這是前門，
你知道，我要站在這裡。
和旁邊的人的 站在這裡。
那麼，什麼數據結構 適合於一個隊列？
>> 聽眾：隊列。
DAVID馬蘭：嗯，一個隊列。
當然可以。
還有什麼？
>> 聽眾：鍊錶。
>> DAVID馬蘭：一個鏈接 列出你可以實現。
和鍊錶是好的，因為這樣 而不是可任意長長
具有一些固定的數 人在店裡。
但也許一個固定的數 地方是合法的。
因為如果他們只有像20 iPhone手機的第一天，也許
它們只需要尺寸的陣列 20代表該隊列，這
只是現在說一旦我們開始討論 關於這些較高級別的問題，
你可以實現它 在任何數量的方式。
還有的可能只是要 是一個折衷在空間和時間
或只是在自己的代碼的複雜性。
>> 那麼堆棧？
好了，一個棧，我們已經看到太多 可能僅僅是這些托盤。
而且你可以實現這個數組。
但在某些時候，如果你使用一個數組， 什麼事情要發生在托盤
你想放下？
行。
你只打算 能走這麼高。
我認為，在馬瑟他們 實際上凹進的開放。
所以，事實上，它幾乎 像奧美使用
固定大小的陣列， 因為你只能
在開放符合這麼多托盤 牆壁向下跌破人們的膝蓋。
因此，可能是 說是一個數組，
但我們可以肯定的實施 更一般地用一個鍊錶。
>> 那麼，關於另一個數據結構？
我拉起另一個視覺這裡。
像這個怎麼在這裡？
為什麼會到沒有它是有用的 一些花哨的線索，這
我們看到了這些非常寬的節點， 其中每一個是在一個數組中？
但是，如果我們做更多的事情 簡單地說，就像一個老同學的家譜，
每一個在這裡的節點 只是存儲號碼。
而不是一個名稱或後裔 只是存儲了一些類似這樣的。
>> 好了，我們行話使用 數據結構是既嘗試
和樹木，其中一個線索，再次，是 只有一個的節點陣列，
依然是你可能會 從小學使用
當你犯了一個家庭 tree--葉和根
樹和兒童 父母和兄弟姐妹物。
我們可以實現一個樹， 例如，作為簡單的了。
樹，如果它作為一個節點，一個 這些圓，其具有數，
它不會有 1指針，而是兩個。
而且只要你加入 第二個指針，
實際上現在做排序 的二維數據
結構在存儲器中。
很像一個二維 數組，你可以
有種類的二維 鍊錶但那些
下面的模式 那裡沒有週期。
這是一個真正的有一棵樹 了祖父母的方式在這裡再
一些家長和孩子 孫子和曾孫。
等等。
>> 但是，什麼是真正的整潔對此也 只是逗你一些代碼，
從調用遞歸 一段時間回來，因此
你寫一個函數，該函數調用自身。
這是一個美麗的機會 實施東西
像遞歸，因為考慮這一點。
>> 這是一個樹。
我已經有點肛門如何 我把整數到街上。
正因如此，它有一個特殊的 名稱 - 二叉查找樹。
現在，我們已經聽說二進制 搜索，但你能
從這個東西的名字倒著工作？
什麼是我如何的格局 插入整數到這棵樹？
它不是隨意的。
這裡也有一些圖案。
是啊。
>> 聽眾：在左邊較小的。
>> DAVID馬蘭：是啊。
較小的是在左側。
更大的是在右側。
這樣，真正的語句是 家長大於它的左孩子，
但比其右孩子少。
而這僅僅是一個連 遞歸定義語言
因為你可以應用 相同的邏輯的每一個節點
而且它僅塔底 如果你出去，基本情況
會的，當你打一個 葉子，可以這麼說，
凡請假沒有孩子更進一步。
>> 現在，你怎麼可能找到44號？
你會從根開始，說，嗯。
55不是44，我想去 正確的還是我想往左走？
顯然，你想要去左邊。
所以它就像手機 在二進制搜索本書實例
更普遍。
但我們實現它 現在多了幾分動態
不是一個數組可以允許。
而事實上，如果你想看看 在代碼中，第一眼肯定。
它看起來像一大堆線。
但它的美麗很簡單。
如果你想實現一個功能 所謂的搜索，其目的在生活中
是要搜索的一個值 像N，整數，
和你在一pointer--正在通過 一個指向根的節點，
那棵樹的相當，從 您可以訪問其他的一切，
注意如何直截了當地 你可以實現的邏輯。
如果樹是空， 顯然它不存在。
讓我們只返回false。
對不對？
如果你把它什麼都沒有， 有什麼也沒有。
>> 否則，如果n小於 樹箭頭N--現在箭頭N，
記得我們推出超 短暫的一天，
那只是意味著去參考 指針看看所謂的n個場。
因此，這意味著去那裡 看看所謂的n個場。
所以，如果N，你給出的值，小於 比在樹木整數的值，
你想去哪兒去了？
向左轉。
>> 所以，注意遞歸。
我returning--不正確的。
不假。
我回來什麼的答案 是通過調用自己，路過
的n再次，這是多餘的， 但什麼是略有不同呢？
我怎麼做的問題更小？
我傳遞的第二個 參數，該樹的不根，
但左子在這種情況下。
所以我通過左邊的孩子。
>> 同時，如果n是大於 該節點目前，我正在看，
我搜索的右側。
否則，如果樹不為空，而 如果元素不是向左
它並不是正確的， 什麼是奇妙的情況？
實際上我們發現，節點 的問題，所以我們返回true。
>> 所以我們剛剛觸及表面 現在一些數據結構。
在問題設置5，你會 再進一步探討這些，
你會得到你的設計 選擇如何去了解這一點。
我想締結 僅僅30秒的預告片
下週及以後有什麼在等待著。
>> 正如我們begin--謝天謝地你可能 慢慢think--我們的轉型
從C和下部的世界 層次的實現細節，
一個世界裡，我們可以採取的 理所當然地認為別人終於
實現了這些數據 結構對於我們來說，
我們將開始了解 現實世界是指實施
基於網絡的程序和 網站更普遍
並且也很安全 我們只已經影響
開始劃傷的表面上。
這是什麼等待著我們 在未來的日子裡。
>> [視頻回放]
>> - 他想出了一個消息， 有協議的所有他自己的。
他來到了殘酷的世界 防火牆，路由器漠不關心，
和危險遠遠比死還要痛苦。
他的速度快。
他是強大的。
他是TCP / IP，和他有你的地址。
“勇士的網。”
[完視頻回放]
DAVID馬蘭：下週即將。
我們會看到你呢。
[視頻回放]
- 和現在，“深度思考” 通過Daven法納姆。
-David總是開始 與講座，“好吧。”
心動不如行動，“這裡的解決方案 本週的問題集“
或者“我們給大家一個A？”
[笑氣]
[完視頻回放]