[音樂播放] 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？” [笑氣] [完視頻回放]