揚聲器1：好吧，所以這是 CS50這是五個星期結束。 而記得我們最後一次 開始尋找在票友數據 即開始解決結構 問題，即開始引入 新的問題，但關鍵就在這 是線程的排序，我們 開始做從節點到節點。 因此，這當然是 一個單向鍊錶。 而由單鍊錶， 我的意思是只有一個 每個這些節點之間線程。 原來，你可以做票友 像雙向鍊錶 因此，你有一個箭頭 要在兩個方向上，這 可以幫助具有一定的效率。 但這個問題是否解決？ 有什麼問題沒有解決這個？ 為什麼我們關心在星期一？ 為什麼在理論上，我們沒在意週一？ 它有什麼作用？ 

聽眾：我們可以動態地調整它的大小。 

揚聲器1：OK，所以我們可以 動態地調整其大小。 幹得好你們倆。 所以，你可以動態調整這個 數據結構，而陣列， 回想一下，你必須知道 先驗多少空間你想 如果你需要更多一點的 空間，你是那種運氣。 你必須創建一個全新的陣列。 你必須將所有的 從一個到另一個數據， 最終釋放舊陣列 如果可以的話，然後繼續。 這只是感覺非常昂貴，非常 效率低，而且確實可以。 但是，這是不是所有的好。 我們付出的代價，究竟是什麼1 較為明顯的價格上漲，我們 通過使用鍊錶買單？ 

聽眾：我們必須使用 為每一個雙層空間。 揚聲器1：是啊，所以我們需要 至少兩倍的空間。 事實上，我意識到這張照片的 甚至有點誤導， 因為在許多現代的CS50 IDE 計算機，一個指針或地址 事實上並非四個字節。 這是很多時候，這些 天8字節，這 裝置的底部最 在現實中的矩形有 是那種兩倍 大如我所繪製的， 您正在使用三倍的手段 多的空間，我們可能有其他方式。 現在，在同一時間，我們 還在說話字節，對不對？ 我們不一定講 MB或GB， 除非這些數據結構變大。 

所以，今天我們開始考慮 我們可以如何發掘數據 更有效地如果 事實上，數據變得更大。 但是，讓我們試著規範化 操作第一 你可以在這些幹什麼 種數據結構。 因此，像一個鏈接 清單普遍支持 操作像刪除， 插入，和搜索。 什麼做我的意思？ 這只是意味著，通常情況下， 如果人們使用鍊錶， 他們或者其他人實施 如刪除，插入功能， 和搜索，這樣你就可以 確實做了什麼 有用的數據結構。 因此，讓我們快速瀏覽一下 我們如何可能實現 一些代碼，一個鍊錶如下。 

所以，這只是一些C代碼， 甚至沒有一個完整的程序 我真的很快刮起了一陣。 這不是在網上分銷 碼，因為它不會實際運行。 但是請注意，我只是 有評論說， 點點點，有什麼東西 在那裡，點點點，東西在那裡。 而且，我們只是看看 什麼多汁的部件。 因此，在三線， 記得，這是現在 我們提出聲明最後一個節點 時間，這些矩形物體中的一個。 它具有我們稱之為為N的INT， 但我們可以把它叫做什麼， 再一個結構節點明星叫旁邊。 而僅僅是明確的，即第二 線，對線6條，那是什麼？ 它是什麼做的我們呢？ 因為它確實看起來更 神秘的比我們平常的變量。 

聽眾：這使得它搬過來的。 

揚聲器1：這使得它搬過來的。 和更精確， 它將存儲的地址 這意味著是該節點的 語義旁邊，對不對？ 所以它不會 不一定移動任何東西。 它只是要 存儲一個值，這是 將是地址 一些其他節點的， 這就是為什麼我們說結構 節點明星，明星表示 的指針或地址。 好了，現在，如果你認為我們有 這款N提供給我們，讓我們 假設別人有 插入一大堆整數 成一個鍊錶。 並且鍊錶是 一些點指向 一個變量調用列表的 在這裡作為參數傳遞， 我怎麼去行 14實現搜索？ 換句話說，如果我實現 功能，其目的在生活中 是採取一個int，然後 開始的鍊錶， 這是一個指向該鏈接的表。 像第一，誰我認為大衛 是我們的志願者在週一， 他指著 整個鍊錶， 就好像我們傳遞 大衛在這裡我們的論點。 我們如何去遍歷這個名單？ 嗯，事實證明，即使 指針是比較新的，現在對我們來說， 我們可以相對做到這一點 直截了當。 

我要繼續前進， 聲明臨時變量 按照慣例，只是走 被稱為指針或PTR， 但你可以把它稱為任何你想要的。 而且我要初始化 它到列表的開頭。 所以，你可以種想到這 作為我的老師有一天， 那種指著別人 在我們人類作為志願者。 所以，我是一個臨時變量，它是 只是指向同一件事 我們不約而同地命名 志願者大衛也指出。 現在，當指針 不為空，因為召回 那空是一些特殊的標記值 所述標定列表的末尾， 因此，雖然我不指著 地面像我們過去的志願者 是，讓我們繼續 並做到以下幾點。 如果pointer--和那種我現在想 做我們的學生做了 結構 - 如果指針點下一個 equals--相反，如果指針點N等於 等於變量N，所述 這就是被傳入的說法， 那麼我想繼續 說返回true。 我已經發現了內部數N 我的一個鍊錶節點。 但點不再 工作在這樣的背景下， 因為指針，PTR，是 確實是一個指針，地址， 我們實際上可以精彩 使用最後一張語法 那種品牌： 直觀感覺，實際上 用一個箭頭這裡，這意味著從去 該地址中的整數那裡。 所以這是非常相似 精神點運算符， 但因為指針不是指針 而不是實際的結構本身， 我們只是用箭頭。 

因此，如果當前節點是我的 臨時變量，我指著 是不是N，我該怎麼想幹什麼？ 好了，我的志願者 我們曾在這裡的一天， 如果我的第一個人是不是一個我 想，也許第二個人是不是 一個我想要的，第三，我 需要保持身體移動。 像我怎麼通過列表步驟？ 當我們有一個數組，你 只是不喜歡我加再加。 但在這種情況下，它足以 做指針，獲取，指針，下一個。 換句話說，下一個字段 就像所有的左手 我們在週一志願者 分別使用以指向某些其它節點。 那是他們的下一個鄰居。 

所以，如果我想一步，通過這個名單， 我不能只是做我加再加了， 我反而不得不說 我，指針，是怎麼回事 等於任何下一個字段是 下一字段，下一個字段是 下面所有這些左手 我們有在舞台上指點 一些後續值。 如果我打通 那整個循環， 最後，我打空沒有 發現ñ然而，我剛剛返回false。 如此反复，所有我們在這裡做， 按照剛才的圖片， 開始通過指向 開頭的名單大概。 然後我檢查，是價值 我在尋找等於九？ 如果是的話，我還真和我完成了。 如果沒有，我更新了我的手， AKA指針，指向 下一個箭頭的位置， 那麼下一個箭頭的位置， 和下一個。 我只是在這個數組中行走。 

如此反复，誰在乎呢？ 什麼樣的事情，這是一種成分呢？ 嗯，記得我們介紹 棧的概念，這 是一個抽象數據類型的範圍內，因為它是 不是C的東西，它不是一個CS50的事情， 這是一個抽象的概念，在這一理念 堆疊的東西上彼此之上 可以在實施 不同的方式束。 我們提出了一種方法是用 陣列，或具有一個鍊錶。 而事實證明，規範地，一 棧支持至少兩個操作。 而時髦的話是推，以 推動東西壓入堆棧， 像在一個新的盤 食堂，或流行， 這意味著以除去最上層 從堆棧中的餐盤 大廳裡，然後也許有些 其他操作為好。 那麼，如何可能，我們定義結構 我們現在調用堆棧？ 

好了，我們有所有必要的 語法我們所掌握的C.我說， 給我一個類型定義 一摞內部的結構， 我要說的是一個數組， 一大堆的數字，然後大小。 因此，換句話說，如果我想 在代碼來實現這一點， 讓我去那種公正， 畫什麼，這是說。 因此，這是說，給我一個 那一定陣列結構， 我不知道是什麼能力， 這顯然有些不變，我已經 其他地方定義，這很好。 但是，假如這只是之一， 二，三，四，五。 所以容量為5。 裡面這個元素我 結構將被稱為數字。 然後，我需要 其他變量明顯 最初我打算叫大小 到規定初始化為零。 如果有什麼的 堆棧，大小是零， 而且它在數量上的垃圾值。 我不知道裡面有什麼了，只是還沒有。 

所以，如果我要推 東西壓入堆棧， 假設我調用函數推，並 我說推50，喜歡50號， 在這裡，你會建議 我畫它在這個數組？ 有五種不同的可能的答案。 你想去哪裡推的50號？ 如果這裡的目標，再次撥打 功能推，傳遞一個參數 50，我在哪裡放呢？ 五possible-- 20％的機率 的猜測正確。 是嗎？ 

聽眾：最右。 

揚聲器1：最右。 現在有25％的機率 的猜測正確。 所以這實際上是罰款。 按照慣例，我會說一個數組， 我們一般將開始在左邊， 但我們可以肯定 開始在合適的。 因此，這裡的擾流板會是我 可能將其繪製在左邊， 就像在一個正常的數組，其中 我開始從左到右。 但是，如果你可以翻轉 算術，罰款。 這只是不是常規的。 好吧，我需要做一個 更多的變化，雖然。 現在，我已經把東西 壓入堆棧，接下來會發生什麼？ 

好吧，我得增加尺寸。 因此，讓我繼續前進，只是 更新這，這是零。 而不是現在，我要去 放中的值之一。 現在假設我推另一 數壓入堆棧，如51。 好了，我一定要多一個 變化，這是向上的大小兩種。 再假設我推多了一個 數入堆棧像61， 現在我需要更新的大小多一個 時間，並獲得值3作為大小。 現在假設我叫流行。 現在流行，按照慣例， 不帶參數。 用棧，整 點盤隱喻 是你沒有自由裁量權 去得到那個盤子，你所能做的 是流行最上面的 堆棧，只是因為。 這就是這個數據結構一樣。 

因此，通過這種邏輯，如果我 要說流行，會發生什麼了嗎？ 所以61。 那麼，什麼是真正的計算機 打算做的內存？ 什麼是我的代碼有什麼關係？ 你會建議 我們改變在屏幕上？ 應該怎麼改？ 對不起？ 所以我們擺脫61。 所以，我絕對可以做到這一點。 我可以擺脫61。 然後還有什麼其他 改變需要發生？ 尺寸可能有回去兩種。 所以，這很好。 但是且慢，大小 剛才是三。 讓我們做一個快速的完整性檢查。 我們是怎麼知道我們 想擺脫的61？ 因為我們大跌眼鏡。 所以我有第二個屬性的大小。 

等一下，我 回想起2週 當我們開始談論 陣列，在這位置為零， 這是位置之一，這是位置 二，這是位置三個，四個， 它看起來像 大小之間的關係 而我想要的元素刪除 從陣列似乎只是什麼？ 尺寸減一。 所以，這就是如何為人類 我們知道61是第一位的。 怎麼樣的電腦會知道？ 當你的代碼，你很可能 想做大小減一， 所以三減一為兩個，並且 意味著我們要擺脫61。 然後，我們的確可以更新 這樣大小的體積，現在 進入三到只有兩個。 而剛需迂腐，我要去 提議我做的，對不對？ 你直觀地提出 正確我應該擺脫61。 但是，有一種沒有我 那種擺脫了61？ 我已經有效地忘記 它的實際存在。 而回想起PSET4，如果你讀過 有關取證的文章中，PDF 我們有你們看，或者你 將讀取本週PSET4。 回想一下，這其實是有密切關係的 計算機取證的整體思路。 什麼是電腦一般不為 它只是忘記在那裡的東西是， 但它並沒有去和像 試著刮出來或重寫 這些位與零和一 或一些其它的隨機圖案 除非你自己這樣做的故意。 所以，你的直覺是 好吧，讓我們擺脫61。 但在現實中，我們沒有理會。 我們只需要忘記， 它的存在，通過改變我們的規模。 

現在有這個堆棧的一個問題。 如果我繼續推動東西 壓入堆棧，什麼是 顯然不會發生 在短短的幾分鐘時間？ 我們將用盡空間。 而我們該怎麼辦？ 那種我們搞砸了。 此實現不讓 我們調整陣列，因為使用 這個語法，如果你 回想起每週二， 一旦你已經聲明 陣列的大小， 我們還沒有看到一個機制，但在這裡 可以改變陣列的大小。 事實上C沒有這個功能。 如果你說給我五 國道主幹線，稱他們的數字， 這就是你要得到它。 所以我們現在要做的是週一，有 表達一個解決方案的能力 雖然，我們只需要調整 我們的疊層的定義 不要被一些硬編碼的數組， 但只是以存儲一個地址。 

現在，這是為什麼？ 現在，我們只需要坦然面對 事實證明我的程序運行時， 我大概會 要問的人， 多少個號碼，你想存儲？ 因此，輸入有來自某處。 但是，一旦我知道， 號碼，然後我可以 使用什麼功能給 我的內存塊？ 我可以用malloc。 我可以說，任何數量的 字節，我想回去了這些國道主幹線。 而且我必須存儲在數字 可變這裡這個結構裡面 應該是什麼？ 究竟進入 在這種情況下的數字？ 是啊，一個指向第一 該內存塊的字節， 或更具體地，地址 第一這些字節。 如果它是一個不事 字節或十億字節， 我只需要關心的第一個。 因為什麼樣的malloc擔保， 我的操作系統擔保， 是，存儲器I組塊 得到的，這將是連續的。 還有的不會是空白。 所以，如果我問50 字節或1000個字節， 他們都將是 背靠背回來。 而只要我還記得有多大，怎麼 很多我要求，我所需要知道的 是第一個這樣的地址。 

所以，現在我們已經在代碼的能力。 雖然，這將帶我們 更多的時間來寫這件事， 我們現在可以通過重新分配內存 只是存儲不同的地址有 如果我們想要一個更大的，甚至 較小的組塊的存儲器。 因此，在這裡一個權衡。 現在，我們得到的活力。 我們仍然有 contiguousness我自稱。 因為malloc的給我們 一個連續的內存塊。 但是，這將是一個痛苦 脖子對我們來說，程序員， 實際代碼了。 這只是更多的工作。 我們需要的代碼類似於我是什麼 剛才撞了。 非常可行，但增加了複雜性。 因此開發時，程序員 時間是另一個資源 我們可能需要花 一段時間來獲得新的功能。 然後當然還有一個隊列。 我們不會進入這個 之一，很多細節。 但它在精神上非常相似。 我可以實現一個隊列， 其相應的操作， 入隊或出隊，像添加或刪除， 它是說這只是一個華麗的方式， 入隊或出隊，如下。 我只能給自己一個結構 一遍的數的陣列， 一遍的尺寸， 但為什麼我現在需要 跟踪一個隊列的前面的？ 我並不需要知道 前面我堆棧。 好吧，如果我再一 queue--就讓我們很難 它編碼具有到五 整數這裡可能。 因此，這是零，一，二，三，四。 這將是 撥打的號碼了。 而這將是所謂的大小。 

為什麼不充分 以剛才的大小？ 好吧，讓我們推動這些相同的數字。 所以我pushed--我入隊，或推。 現在，我將排隊50，然後 51，然後61，和點點點。 所以這是入隊。 我入隊的50，然後51，然後61。 這看起來相同 到煙囪迄今 但我確實需要做出一個改變。 我需要更新這個尺寸，所以我去 從零到一到兩到三現在。 我如何出列？ 與出隊會發生什麼？ 誰應該打這個名單第一 如果是該行的蘋果專賣店？ 所以50。 因此，它是有點棘手這個時候。 而上一次是超級 易只是做大小減一， 我得到我的數組的末尾有效 其中數字是，它消除61。 但我不希望刪除61。 我想利用50，誰 在那裡上午5:00 排隊的 新的iPhone或諸如此類的東西。 所以，要擺脫50，我 不能僅僅做到這一點，對不對？ 我可以劃掉50。 但是，我們剛才說了，我們 不必如此肛門 以劃掉或隱藏數據。 我們可以忘記它在哪裡。 

但是，如果我現在改變我的尺寸， 二，這是足夠的信息 知道什麼是我的排隊怎麼回事？ 不盡然。 就像我的尺寸是兩個，而是 哪裡排隊開始， 尤其是如果我仍然有 那些相同的標號在存儲器中。 50，51，61。 所以，我需要記住 現在所在的前面。 所以，我提出了 在那裡，我們將剛才叫 第N次前，其初始 價值應該是什麼呢？ 零，列表僅僅是個開始。 但現在除了遞減 規模，我們只是增加了前面。 現在，這裡是另外一個問題。 所以一旦我繼續前進。 假設這是數 像121，124，然後，該死， 我的空間。 但是且慢，我不是。 所以在這一點中的故事， 假設尺寸是一，二， 三個，四個，所以假設 大小為4，前一個， 所以51是在前面。 我想提出另一個號碼在這裡， 但是，該死，我出了空間。 但我不是真的，對不對？ 我在哪裡可以把一些 附加價值，如171？ 是的，我能正中下懷 回去那邊了吧？ 然後過了50，或 只是簡單地覆蓋它與171。 如果你想知道為什麼 我們的數字變得如此隨意， 這些通常採取計算機 科學課程在哈佛CS50之後。 但是，這是一個很好的優化， 因為現在我沒有浪費的空間。 我還是要記住 有多大這個東西是總。 它共有五次總。 因為我不希望 開始覆蓋51。 所以，我現在還在外面的空間， 從而前同樣的問題。 但是你可以看到現在 在你的代碼，你可能 有一點寫更多 複雜性來實現這一目標。 而事實上，運營商所 C語言可能讓 你神奇地做到這一點的圓？ 是的模運算符， 百分號。 那麼，有什麼樣的酷的隊列， 儘管我們不斷吸引數組 因為這些象直線，如果 那種認為關於這個問題，彎曲 作為周圍一圈，然後就 一種直覺它的工作精神 我覺得有點更乾淨。 你仍然必須執行 在代碼中的心智模式。 所以並不難， 最終，實施， 但我們還是失去了size--相當， 能力來調整，除非我們做到這一點。 

我們必須擺脫的數組，我們 它與單個指針替換， 然後地方在我的代碼我有 一個叫什麼函數來實際創建 數組撥打的號碼？ malloc或一些類似 功能，沒錯。 在棧或隊列的任何問題。 是嗎？ 好問題。 你會用什麼在這裡模。 所以一般地，在使用 MOD，你會做 同的大小 整體的數據結構。 因此，像五容量，如果 這是不變的，可能是參與。 但只是在做模數5 可能是不足夠的， 因為我們需要知道我們是否 環繞在這裡或在這裡或在這裡。 所以，你可能還 將要涉及到 事物的大小，或 前面的變量也是如此。 所以，它只是這個比較 簡單的算術表達式， 但模將是關鍵因素。 

所以，短片，如果你會的。 一個動畫，一些 人們在另一所大學 放在一起，我們已經 適用於本次討論。 它涉及傑克學習 有關隊列和統計數據的事實。 

電影：曾幾何時， 有一個叫傑克的傢伙。 當它來交朋友， 傑克沒有一個訣竅。 於是傑克就去找了 最流行的傢伙，他知道。 他到樓，問道，我該怎麼辦？ 婁看到他的朋友 真的很心疼。 好了，他開始，就 看你如何打扮。 你沒有任何的衣服 以不同的面貌？ 是的，傑克說。 我當然有。 來我家， 我會告訴他們你。 於是他們去了傑克的。 和傑克表明婁盒 在那裡他保持他的所有襯衫， 和他的褲子，他的襪子。 樓繼偉說，我看你有沒有 你的衣服在一堆。 你為什麼不穿些 其他人曾經在一段時間？ 

傑克說，好吧，當我 脫去衣服和襪子， 我把它們洗乾淨，並把 他們走在框中。 然後是下一個 早晨，起來我一跳。 我去的箱子，並得到 我的衣服上。 婁很快就意識到 這個問題與傑克。 他不停的衣服，光盤， 並且堆疊的書籍。 當他伸手 一些閱讀或磨損， 他會選擇頂部的書或內衣。 然後，當他完成，他 會把它的右後衛。 回到它會去，在堆棧的頂部。 我知道解決的辦法， 說勝利響亮。 你需要學習 開始使用一個隊列。 婁花了傑克的衣服， 他們掛在衣櫃裡。 而當他已經清空 盒子，他只是扔。 

然後他說，現在的傑克，在年底 當天，穿上你的衣服左邊 當你把他們帶走。 然後明天早上，當你 看到陽光，讓你的衣服 在右邊，從行的末端。 你難道不明白嗎？說樓。 這將是那麼好。 你會沖刷一切的一次 你穿的東西之前兩次。 而隨著一切都在排隊 在他的衣櫃和書架， 傑克開始感覺 十分肯定自己。 婁所有的感謝和 他精彩的隊列。 揚聲器1：好吧，這是可愛的。 那麼，什麼是怎麼回事 在現在的引擎蓋下？ 我們有三分球， 我們擁有的malloc， 我們有能力創造 內存佔為己有塊 動態。 所以這是一個圖片我們 瞥見就在幾天前。 我們真的不糾纏 就可以了，但這張照片 已經持續下 現在引擎蓋幾個星期。 所以這代表，只是 我們已經繪製一個矩形， 您的計算機的內存。 也許你的電腦，或者CS50 ID，具有存儲器或RAM一個千兆字節 兩個千兆字節或四個。 這其實並不重要。 您的操作系統 Windows或Mac OS或Linux， 基本上可以讓你的程序 認為它能夠訪問 到的全部 您的計算機的內存， 即使你可能正在運行 多程序同時應用。 因此，在現實中，沒有真正發揮作用。 但它是一種一種假象 給所有的程序。 所以，如果你有內存2音樂會，這 是怎樣的計算機可能會想到它。 

現在，巧合的是，其中一個 事，內存這些領域之一， 被稱為堆。 實際上，任何時候 迄今在編寫代碼 你已經被稱為 功能，比如主。 回想一下，任何時候我已經 得出計算機的內存， 我總是吸引排序 一半的矩形的這裡 也懶得說話 關於什麼的上面。 因為當主被調用時，我要求 你得到這個條子的記憶 該下降這裡。 如果主稱為函數 像掉期，以及交換到這裡。 而事實證明，這是 其中，它的結束了。 在被稱為堆的東西 在你的計算機的內存中。 現在在一天結束時， 這僅僅是解決了。 這就像一個字節零， 字節之一字節2十億。 但是，如果你仔細想想 因為這樣的矩形對象， 我們所做的每一個 一次，我們調用一個函數 分層存儲新的切片。 我們給這個函數片 自身的存儲器的工作。 

現在回憶起來，這是非常重要的。 因為如果我們確實有 類似的交換 像A和B兩個局部變量 我們改變這些值從一個和兩個 兩個和一個，召回 當交換返回， 這是因為雖然這片 內存只是走了。 在現實中，它仍然 有取證。 而一些仍然居然有。 但在概念上，這是因為 雖然它完全消失了。 所以主不知道任何工作 這是在交換功能完成後， 除非它實際上是通過這些 通過指針或引用參數。 現在，從根本上解決 該問題與交換 通過地址傳遞的東西研究。 但事實證明也是如此，什麼是 已經持續了上面那一部分 矩形的這段時間是 但有更多的內存在那裡。 動態當你 分配內存， 無論是GetString的，裡面的這 我們在CS50已經為你做 圖書館，或者，如果你們 調用malloc和要求 對於一大塊的操作系統 存儲器，它不是來自堆棧。 它來自另一個地方 在您的計算機的內存 這就是所謂的堆。 而這沒有什麼不同。 這是相同的RAM。 這是同樣的內存。 這只是在RAM那達 那裡，而不是到這裡。 

所以，這是什麼意思？ 好吧，如果你的電腦有 的存儲器量有限 與堆棧長大，所以 說話，堆，根據 這一箭，越來越大了。 換句話說，每 一次調用malloc， 你被賦予了片 的存儲器從上方 那麼也許更低一點，然後一點點 低，每次調用malloc的時候， 堆，它的使用情況， 是一種成長， 日益密切的是什麼？ 堆棧。 那麼，這似乎是一個好主意嗎？ 我的意思是，它並不真正清楚 如果你只可以做什麼 具有存儲器的有限數量。 但是，這肯定是不好的。 這兩個箭頭都在一個 當然崩潰彼此。 

而事實證明，壞傢伙，人們誰 與節目特別好， 並試圖侵入電腦， 可以利用這個現實。 事實上，我們考慮 一個小片段。 因此，這是你可以閱讀的一個例子 關於維基百科上的更詳細。 我們將向您在 文章，如果好奇。 但是有一般的攻擊 被稱為緩衝區溢出的 只要已經存在了作為人類 不得不操縱能力 計算機的內存，尤其是在C中 所以這是一個非常隨意的程序， 但讓​​我們從下往上看。 主要為焦炭ARGC ARGV明星。 所以這是一個程序，它 命令行參數。 和所有主要的也顯然是通話 一個函數，調用它F代表簡單。 它在傳遞什麼？ ARGV之一。 因此，它傳遞到f中的任何 的話，就是用戶鍵入 在之後的提示 節目的名字都沒有。 那麼像撒或的Vigenere，這 你可能還記得與ARGV做。 

那麼，什麼是F？ ˚F接受一個字符串 作為其唯一的參數， AKA一個char明星，同 首先，作為一個字符串。 而這就是所謂的任意 禁止在這個例子。 然後焦炭C 12， 只是外行人的話說， 什麼是CHARÇ支架12做的我們呢？ 它是什麼呢？ 分配內存，專 12個字節為12個字符。 沒錯。 然後最後一行，攪拌， 副本，你可能沒見過。 這是一個字符串拷貝 功能，其目的在生活中 是複製它的第二個參數 到了第一個參數， 但只達到一個 一定數量的字節。 所以第三個參數說： 你應該有多少個字節複製？ 條的長度， 無論用戶鍵入。 及內容 酒吧，該字符串，是 拷貝到存儲指向在C. 

因此，這似乎是一種愚蠢的，它是。 這是一個人為的例子， 但它代表 一類攻擊向量的， 一種方式攻擊的程序。 一切都很好，好，如果用戶 在一個字那是11個字符類型 或更少，加上反斜杠零。 如果在用戶鍵入超過什麼 11或12或20或50個字符？ 這是什麼程序該怎麼辦？ 潛在的賽格故障。這是怎麼回事 要盲目照搬一切都在酒吧起來 其長度，這是 從字面上的一切吧， 到地址指向C.但Ç 只搶先給出12個字節。 但是，沒有任何額外的檢查。 有沒有，如果條件。 有沒有錯誤檢查在這裡。 

所以這個計劃是什麼 要做的只是一味的 一件事複製到其他。 所以，如果我們得出這樣的 作為一個圖片，這裡的 內存空間只是一個條子。 所以，注意在底部，我們 有局部變量吧。 這樣的指針，那將store-- 而當地的論點，即是 將存儲字符串吧。 然後請注意只​​是 它在一組的上方， 因為每次你問的時間 為存儲器的棧上， 它會一點點 它形象地上面， 我們已經得到了12個字節有通知。 頂部左邊的一個是C支架為零， 底部正確的是C支架11。 這是多麼的電腦 要打好它。 因此，只要憑直覺，如果酒吧有更多的 超過12個字符共包括 反斜杠零，在哪裡 12的C支架12要去？ 或者說在這裡是第12個 字符或13個字符， 第一百字去 結束了在圖片？ 高於或低於？ 

對，因為即使 棧本身是向上增長， 一旦你把東西在 它，它的設計的原因， 放存儲器從上到下。 所以，如果你有超過12個字節， 你將開始覆蓋吧。 現在，這是一個錯誤，但它的 不是一個真正的大問題。 但是，這是一個大問題，因為有 更多的東西在內存回事。 因此，這裡是我們如何能夠 把你好，是明確的。 如果我輸入打招呼的提示。 H-E-L-L-O反斜杠零，在結束了 這12個字節，而且我們的超級安全。 一切都很好。 但是，如果我輸入一些東西 時間越長，可能是 要潛入酒吧空間。 但更糟糕的是，事實證明 出這麼長的時間， 即使我們從來沒有談過 它的堆棧用於其他的東西。 這不只是局部變量。 

C是一個非常低的水平的語言。 排序，並偷偷 使用堆棧也 要記住，當 函數被調用，什麼 地址是以前的功能， 因此它可以跳轉回該功能。 因此，當主呼叫交換，其中 的事情壓入堆棧 不只是交換局部變量， 或者它的參數，還偷偷推 入堆棧為代表 這裡由紅切片， 是主要的地址物理 在計算機的內存， 這樣，當交換完成時，計算機 知道我需要回到主 並完成執行的主要功能。 所以，現在這樣是很危險的，因為如果 中公比你好更多的用戶類型， 使得用戶的輸入則會覆蓋 或將覆蓋紅色的部分， 邏輯上，如果計算機的 只是要盲目地承擔 在這片紅色的字節 地址到它應該返回， 如果對手是足夠聰明或 幸運地把字節序列 還有，看起來像一個地址， 但它的代碼的地址 他或她想要的計算機 而不是主要的執行？ 

換句話說，如果什麼 用戶在提示符下敲入， 不只是一些 無害喜歡你好， 但它實際上代碼是等價 刪除所有該用戶的文件？ 或者通過電子郵件發送密碼到我嗎？ 或者，開始記錄自己的 按鍵，對不對？ 有一種方法，讓我們今天的規定， 他們可以輸入不只是打招呼 世界還是他們的名字， 他們可能根本 通過在代碼中，零和 的，該計算機 錯誤的代碼和一個地址。 因此，儘管有些抽象，如果 足夠的對抗代碼用戶類型 我們將歸納這裡 答：是的攻擊或敵對。 所以只要壞的東西。 我們不關心 數字或零或1 今天，這樣你最終 覆蓋的紅色款， 請注意字節的順序。 Ø835℃零八零。 現在，維基百科的文章在這裡 建議，如果你現在居然開始 標籤在您的計算機中的字節 內存，維基百科的文章是什麼 的提出的是，如果有什麼的地址 除此之外左字節為80℃0 3508。 

換句話說，如果壞傢伙是 與他或她的代碼足夠聰明 實際上把一些在這裡， 對應於編碼的地址 他或她注入 插入電腦，你 可以欺騙計算機 為做任何事情。 刪除文件，電子郵件 事，嗅探您的流量， 從字面上什麼事情都可能會 注入到計算機。 所以緩衝區溢出 進攻的核心 僅僅是一個愚蠢，愚蠢 數組壓倒一切的 沒有它的邊界檢查。 這是什麼是超級危險 同時超級強大 在C是，我們確實有 訪問在存儲器的任何位置。 這取決於我們的程序員， 誰寫的原代碼 檢查所有的織補長度 陣列，我們正在操縱。 所以要清楚，有什麼解決？ 如果我們回滾到該 代碼，我不應該只是 改變桿的長度，什麼 別的我應該檢查？ 還有什麼我應該做的到 防止這種攻擊完全？ 我不想只是一味地說 你要複製的字節數 作為是條的長度。 我想說，複製為 許多字節都在酒吧 向上到分配 存儲器，或12最大限度。 所以，我需要某種形式的if條件 ，做檢查吧的長度， 但如果超過12，我們只是硬編碼 12的最大可能距離。 否則所謂緩衝 溢出攻擊可能發生。 在這些幻燈片的底部， 如果你好奇閱讀更多 是真正的原創文章 如果你想看看。 

但現在，其中的價格 在這裡付出了效率低下。 所以這是一個快速 低水平看看什麼 現在出現的問題，我們 有權訪問的計算機的存儲器中。 但另一個問題，我們 已經迷迷糊糊週一 這僅僅是低效率 的一個鍊錶。 我們又回到了線性時間。 我們不再有一個連續的數組。 我們沒有隨機訪問。 我們不能用方括號。 我們實際上不得不使用whil​​e循環 像我剛才寫的。 但在週一，我們宣稱我們能 悄悄放回效率的境界 實現東西是 對數也許，或者最好的是， 甚至東西是 所謂一定時間。 那麼，如何才能做到這一點通過使用這些新的 工具，這些地址，這些指針， 和線程我們自己的東西呢？ 好吧，假設 在這裡，這些都是一堆 我們要存儲在數字 高效的數據結構和搜索。 我們完全可以後退到週 二，把這些放到一個數組， 並使用二進制搜索尋找他們。 分而治之。 而事實上，你寫的 在PSET3二進制搜索， 在那裡你實現find程序。 但是你知道嗎。 還有一種更 這樣做的聰明的方式。 這是一個有點多 成熟，它可能 讓我們看到了為什麼二進制 搜索是如此之快。 首先，我們來介紹 樹的概念。 其中，即使在 樣的現實樹 成長就是這樣，在計算機世界 學他們那種向下生長 就像一個家庭樹，在這裡你有 你的祖父母或曾祖父母 或者諸如此類的東西在上面，族長和 家族的女家長，只有一個 所謂根，節點，下面 這是它的孩子， 下面這是它的孩子，或 它的後代更普遍。 任何人都掛 家庭的底部 樹，除了是 最年輕的家庭， 也可以只是一般 稱為樹的葉子。 

因此，這只是一堆 詞和定義 對於一些所謂電腦一棵樹 科學，就像一個家庭樹。 但是，還有票友變身 的樹木，其中之一 被稱為一個二分搜索樹。 你可以種挑逗 除了這個東西做什麼。 那麼，它的二進制在什麼意義？ 哪裡二進制從何而來嗎？ 對不起？ 這與其說是一個非此即彼的。 它更，每個節點具有無 兩個以上的孩子，我們在這裡看到。 在一般情況下，一個tree--和 你的父母和祖父母 可以有很多孩子或 孫子，因為他們真正想要的， 所以比如有，我們有三個 關閉該右手節點的孩子， 但在一個二叉樹，一個節點具有 零個，一個或兩個孩子最大限度。 這是一個很好的屬性， 因為如果它的上限由二， 我們將能夠 得到一點點的日誌基地二期 行動回事大勢所趨。 因此，我們有一些東西對數。 但是，更詳細的介紹了一下。 搜索樹指數是 佈置成使得左孩子的 值大於根。 而它的右子是 比根大。 換句話說，如果你把所有的 節點，在這張照片中圈， 並期待在其左 兒童和其右孩子， 第一應小於， 第二應大於。 因此，合理性檢查55。 它的左子是33。 它的不足。 55，其右孩子是77。 它是大於。 這是一個遞歸定義。 我們可以檢查每個人的那些 節點和相同的圖案將舉行。 

那麼什麼是不錯的 二叉搜索樹，是 這一塊，我們可以實現它 有一個結構，就這樣。 而且即使我們扔 很多結構在你的， 他們是有點 直觀現在有希望。 語法仍然是神秘的肯定， 但一個節點在該內容 context--和我們保持 使用這個詞的節點， 無論是一個矩形 屏幕或圓上， 它只是一些通用的容器， 在這種情況下，一棵樹的，像一個 我們看到，我們需要一個整數。 在每個節點 然後我需要兩個指點指點 到左子和右子， 分別。 所以這就是我們如何 實現在一個結構。 怎麼可能我在代碼中實現它？ 好吧，讓我們快速瀏覽 看看這個小小的例子。 這不是功能，但我已經 複製並粘貼該結構。 如果我的函數的二進制 搜索樹被稱為搜索， 而這需要兩個參數， 整數N和一個指針 到一個節點，以便一個指向樹 或一個指向樹的根， 我該如何去尋找N + 嗯，首先，因為我 處理球， 我會做一個全面的檢查。 如果樹等於等於空，是N 在這棵樹還是沒有這棵樹？ 這是不可能的，對不對？ 如果我過去的空， 有什麼也沒有。 我乾脆 一味地說，返回false。 如果你給我什麼，我當然不能 找到任何數量N.那麼還有什麼可能我 現在檢查？ 我會說好東西如果N 小於任何位於樹節點 我一直在流傳N值。 換句話說，如果數字我 尋找，N，小於節點 那我看。 和節點我期待 在被稱為樹， 和前面的例子召回 得到的價值指針， 我用的是箭頭符號。 因此，如果N小於樹箭頭 N，我想概念去左邊。 我如何搜索明示離開？ 需要明確的是，如果這是 圖片中的問題， 我已經過了那個最上面 箭頭指針下降。 這是我的樹指針。 我指著樹的根。 我期待說，對於 數44，隨意。 比44少或 超過55顯然更大？ 所以這是不到。 所以這一點，如果條件適用。 所以概念上，我該怎麼想 搜索下一個，如果我在尋找44？ 是嗎？ 

沒錯，我想 搜索左子， 或該圖像的左側的子樹。 而事實上，讓我通過 圖片到這裡 就一下，因為 我也不會劃傷了這一點。 如果我從這裡開始在55，和 我知道，值44 我在尋找是 左邊的，它是一種 像撕開電話簿 一半或撕裂樹的一半。 我不再去在乎 這整個樹的一半。 然而，奇怪的是在條款 結構，這件事情在這裡 始於33，這本身 是二叉查找樹。 我之前說的，因為這個詞遞歸 的確這是一個數據結構，它 顧名思義就是遞歸。 你可能有一個樹是這個 大，但它的每一個孩子 代表一棵樹只是有點小。 而不是它是爺爺 或奶奶，現在它只是媽媽 or--我不能say--沒有媽媽 或爸爸，那將是不可思議。 相反，兩個孩子有 會像兄弟和姐妹。 新一代的家族樹。 但在結構上，這是同樣的想法。 而事實證明，我有一個函數 與我可以搜索二進制搜索 樹。 這就是所謂的搜索。 我在樹的箭頭左邊搜索對於N 否則，如果N大於該值 我目前在。 55中的故事剛才。 我有一個調用的函數 搜索，我可以只 通過N本和遞歸搜索 子樹和剛剛回歸 不管這個答案。 否則我這裡有一些最後的基本情況。 

是什麼最終的情況？ 樹為null。 我現在不是在尋找的價值 比小於它或更大 或等於它。 而且我可以說等於 相等，但在邏輯上是 相當於只是說人在這裡。 所以，真正的是我找到的東西。 因此，希望這是一個 更引人注目的例子 比愚蠢的西格瑪功能 我們做了一些講課回來， 其中，使用循環是一樣簡單 計算了從一個所有的數字 為N.這裡用的數據結構 這本身就是遞歸 定義和遞歸拉，現在我們 要表達自己的能力 在代碼本身是遞歸的。 因此，這是這裡的完全相同的代碼。 

所以，我們能解決什麼其他的問題？ 因此，一個快人一步遠離 樹木只是一瞬間。 這裡，說，德國國旗。 還有的顯然是一個 模式這個標誌。 而且還有很多的 在世界上的標誌是 是這麼簡單的條件 它們的顏色和圖案。 但是，假如這個存儲為 .gif或JPEG格式，或位圖或平， 任何圖形文件格式 與你熟悉， 其中一些我們 在PSET4玩。 這似乎並不值得保存 黑色像素，黑色像素，黑像素， 點，點，點，一大堆 黑色像素的第一掃描線， 或行，然後一大堆 同樣的，然後一大堆 的相同，然後一​​個 一大堆的紅色像素， 紅像素，紅色像素，然後整體 一束黃色的像素，黃色的，對不對？ 

有這樣的效率在這裡。 你將如何直觀地 壓縮德國國旗 如果其實現為一個文件？ 像什麼信息能不 懶得為了存儲在磁盤上 從喜歡減少我們的文件大小 一兆字節到千字節，東西 小？ 其中位於冗餘 這裡要清楚？ 你該怎麼辦？ 是嗎？ 沒錯。 為什麼不，而不是記住 每一次縫補像素的顏色 就像你做的PSET4 與位圖文件格式， 你為什麼不只是代表 像素的最左邊的列，例如 一堆黑色像素，一串 紅，和一堆黃色， 然後不知怎麼竟編碼 重複這個想法100倍 或者重複這個1000倍？ 其中100或者1000是 只是一個整數，所以你 可以逃脫只是一個單一的數字 而不是數百或數千 的追加像素。 事實上，這就是我們如何 可以壓縮的德國國旗。 和 現在來談談法國國旗？ 還有一點某種 腦力鍛煉，這標誌 可以壓縮更多的磁盤上？ 德國國旗或法國的 標誌，如果我們採取這種做法？ 德國國旗，因為有 更水平的冗餘。 而在設計上，許多圖形文件 格式確實工作作為掃描線 水平。 他們可以工作 垂直，只是人類 決定多年前，我們會 一般認為事情排 由行，而不是逐列。 所以，事實上，如果你是 看文件 德國國旗和法國的大小 標誌，只要分辨率 相同的，相同的寬度 和高度，這其中 這裡將是更大，因為你 不得不重複自己的三倍。 你必須指定藍色，重複 自己，白，重複自己，紅色， 重複自己。 你不能只是全力以赴 的方式向右邊。 和作為一旁，以使 清除壓縮 無處不在，如果這些 從video--四個幀您 可能還記得，影片 或視頻一般是 就像每秒29或30幀。 這就像一個小翻轉書，你 只是看到圖像，圖像，圖像，圖像， 圖像只是超級快，所以它看起來像 屏幕上的演員們動人。 這裡有一個大黃蜂 一束花的頂部。 雖然它可能是一種 很難看到的第一眼， 唯一移動 這部電影是蜜蜂。 

什麼是愚蠢的有關存儲 視頻解壓縮？ 這是一種浪費存儲視頻 四個幾乎相同的圖像， 不同僅僅是因為那裡的蜂。 你可以扔掉最 該信息 只記得，例如， 第一幀和最後一幀， 如果你的關鍵幀 聽說過這個詞， 而只是存儲在 中間那裡的蜂。 而你也不必 存儲所有的粉紅色， 和藍色，並在該 綠色價值觀為好。 因此，這是只說 壓縮是無處不在。 這是一個技術，我們經常使用 或者認為理所當然，這些天。 

但是你如何壓縮文本？ 你怎麼去壓縮的文本？ 那麼，每一個人物的 ascii的是一個字節或八個比特。 這就是那種愚蠢的，對不對？ 因為你可能A型 而E和I和O和U很多 往往比像W或Q或Z， 根據所用的語言 你寫的肯定。 所以我們為什麼要使用 八位的每一個字母， 包括最不 流行的信，對不對？ 為什麼不使用較少的位 超人氣的信件， 像E，你猜的東西 首先在命運之輪， 並使用更多的比特用於 冷門信嗎？ 為什麼呢？ 因為我們只是要 使用這些較不頻繁。 

嗯，事實證明，有有 已經提出這樣做的嘗試。 如果你的等級召回 學校或高中，莫爾斯電碼。 莫爾斯電碼具有點 和破折號，可以 沿導線作為發送 聲音或某種信號。 但摩爾斯電碼是一個超級乾淨。 這是怎樣的一個雙星系統中 你必須點或破折號。 但是，如果你看到，例如，兩個點。 或者，如果你想給操作 誰是這樣嘟，嘟，嘟， 蜂鳴聲，創下了小觸發 該發送信號， 如果，接收方，接收兩個 點，你有沒有收到什麼樣的信息？ 完全是任意的。 

我？ 我？ 還是什麼about--還是我？ 也許這只是二號E的吧？ 因此，有這個問題 可解碼與莫爾斯 代碼，從而除非 人向您發送消息 實際上暫停，因此您可以排序的 看到或聽到的字母之間的差距， 這是不夠的只是 送的零和一的流， 或者點和線， 因為有歧義。 E是一個點，因此，如果您 看到兩個點或聽到兩個點， 也許這兩架E的或者它的One I. 因此，我們需要一個系統，是一個 小比這更聰明。 所以叫一個人霍夫曼年 前想出正是這一點。 因此，我們只是要 採取快速瀏覽 如何樹是有密切關係這一點。 假設這是一些 要發送愚蠢的消息， 只是A，B組成，C的D'和E的， 但有很多冗餘這裡。 這並不意味著是英語。 這不是加密的。 這只是一個愚蠢的消息 有很多重複。 所以，如果你真的算出來的所有 A的，B公司，C公司，D的，和E的，這裡的 頻率。 字母的20％是 A的，字母的45％ 為E的，和其他三個頻率。 我們人手點算在那裡 而只是做數學。 

所以，事實證明， 霍夫曼，前一段時間， 意識到這一點，你知道 什麼，如果我開建 一棵樹，或森林的樹木，如果你願意， 如下所示，我可以做以下。 我想給一個節點到每個 我關心的字母 我要去存儲 該節點的內 頻率作為一個浮點 值，或者你可以使用它的N，也 但是我們只用一個浮點數在這裡。 而算法 他提出的是你 藉此森林單個節點 樹木，所以超短樹， 你開始與連接它們 新的群體，新的父母，如果你願意。 而你做到這一點，選擇 兩個最小頻率的時間。 於是，我花了10％和10％。 我創建了一個新的節點。 而我所說的新節點20％。 

這兩個節點結合我下？ 這是一個有點曖昧。 因此，有一些角落情況下 考慮，而是讓事情變得漂亮， 我會選擇20％ -  我現在忽略了孩子。 我會選擇20％ 15％和繪製兩條新邊。 而現在這兩個節點 我邏輯組合？ 忽略所有的孩子，所有的 孫子，只看根 現在。 這兩個節點我綁在一起？ 第二點和0.35。 因此，讓我得出兩個新的邊緣。 然後，我只有一個了。 因此，這裡的一棵樹。 而且它被畫刻意 看那種漂亮， 但是請注意，邊緣有 也被貼上零和一。 因此，所有的左邊緣都為零 隨意，但始終。 所有的右側邊緣的那些。 

還等什麼霍夫曼提出， 如果要表示B， 而不是表示數字66作為 一個ascii其長度為八​​個整位， 你知道嗎，剛剛店 圖案零，零，零， 零，因為這是路徑 從我的樹，霍夫曼先生的樹， 從根葉。 如果你想存儲 E，相比之下，不 發送代表E.八位 相反，派位的是什麼模式？ 一。 什麼是好的關於這 E是最流行的字母， 而你正在使用的 最短的代碼吧。 接下來最流行 信看起來 是A.所以，有多少位 他才建議用是什麼？ 零點一。 

而且因為它的實現 因為這棵樹，現在 讓我規定有 無歧義的莫爾斯 碼，因為所有的 你關心的信 是在這些邊緣的末端。 所以，這只是一個 應用一棵樹。 這is--我會波 我的手在這你如何 有可能實現這是一個C結構。 我們只需要結合 一個符號，就像一個char， 和在頻率左右。 但是，讓我們看兩個 最後的例子，你會 得到相當熟悉後， 測驗零習題集五位。 

因此，有該數據結構 稱為哈希表。 而一個哈希表是怎麼樣的 冷卻在於它具有水桶。 假設有四個桶 在這裡，只有四個空格。 下面是一副撲克牌，並在這裡被 俱樂部，鐵鍬，俱樂部，鑽石，俱樂部， 鑽石，俱樂部，鑽石， clubs--所以這是隨機的。 心，hearts--所以我 bucketizing所有輸入這裡。 而一個哈希表的需求 看你的輸入， 然後把它放在一個特定的 基於你所看到的地方。 這是一個算法。 而我使用的是超 簡單的視覺算法。 其中最困難的部分是 記住哪些圖片是。 再有就是總共四個東西。 

現在堆棧的長勢，這 是故意設計的東西在這裡。 還有什麼我可以做什麼？ 所以實際上我們在這裡有一個 一群老同學考試用書。 假設一堆 學生的名字都在這裡。 這裡有一個更大的哈希表。 而不是四個桶， 我有，比方說26。 我們不想去借錢26 從外面[事情？安嫩伯格？]，所以 這裡共有五次代表 A到Z.如果我 看到學生的名稱以A， 我打算把他或她的測驗那裡。 如果有人以C開頭，在那裡， A--實際上，並不想這樣做。 B進入到這裡。 所以，我有A和B和C和 現在這裡的另一個學生。 但是，如果這個散列表是 以與陣列實現， 我有點擰 在這一點上，對不對？ 那種我需要把這個地方。 

因此，我可以解決這個問題的一個方法是，所有的 沒錯，A佔線，B忙，C忙。 我打算把他D.因此，在 首先，我有隨機即時訪問 每個桶的學生。 但是，現在這是一種下放 弄成線性的， 因為如果我要尋找的人 其名稱開頭，我點擊這裡。 但如果不是這種甲 學生，我正在尋找， 那種我要開始檢查 水桶，因為我做了什麼 是那種線性 探測數據結構。 一個說笨方法只是看 第一個可用的開放， 並把作為一個B計劃，可以這麼說， 或者在這種情況下的計劃D，則值 在該位置代替。 這僅僅是這樣，如果你​​已經 有26個地點，並沒有學生 名為Q或Z或喜歡的事 即，至少你正在使用的空間。 

但是，我們已經看到了更多的 聰明的解決方案，在這裡，對不對？ 你會怎麼做，而不是 如果你有一個碰撞？ 如果兩個人有 該名稱的，會是什麼 是一個更聰明或更 直觀的解決方案不僅僅是 把一個其中D應該是？ 為什麼不讓我走 外[？安嫩伯格？] 喜歡的malloc，另一個節點，把它 在這裡，然後把這裡的學生。 所以，我基本上是有 一些類型的數組，， 或者更優雅的，因為我們是 開始看到一個鍊錶。 

因此一個哈希表的結構 這可能看起來就像這樣， 但更聰明，你的東西被稱為 分離鏈，從而哈希表 很簡單，是一個數組，每個 其元素不是數字， 本身是一個鍊錶。 使您獲得超快速訪問 決定在哪裡你的價值散列到。 就像用卡的例子， 我做了超級快速決策。 心放在這裡，鑽石放在這裡。 同樣在這裡，一個放在這裡， ð放在這裡，B放在這裡。 因此，超快速的查找窗口，如果 你碰巧遇到一個案例 在這裡你有碰撞，二 人具有相同的名稱，以及再 你剛開始把它們連接起來。 也許你讓他們排序 按字母順序，也許你不知道。 但至少現在我們有活力。 因此，一方面，我們有超級快 固定的時間和形式的線性時間 如果這些鍊錶參與 開始變得有點長。 

因此，這種愚蠢的， 令人討厭的笑話年前。 在CS50黑客馬拉松， 當學生入住， 一些TF或CA每年 認為這是有趣忍受 像這樣的一個標誌，它只是 也就是說，如果你的名字開始與A， 走這條路。 如果你的名字開始 用A，B，去this-- OK， 這很有趣，也許在以後的學期。 但是，還有一個 這樣，太的方式。 回過頭來的。 

因此，有這種結構。 這是我們最後一次 結構的今天， 這是一些所謂的線索。 T-R-I-E，這對於某些原因是短 檢索，但它被稱為線索。 因此，一個線索是另一個有趣 汞合金很多這樣的想法。 這是一棵樹，這是我們以前見過。 這不是一個二叉搜索樹。 這是一個樹的任何數量的孩子， 但每一個線索的孩子 是一個數組。 大小的數組，說，26或者27 如果你想支持複姓名字 還是在人的名字撇號。 

所以這是一個數據結構。 而如果你從上 到底，就像如果你 頂一下節點有，男，是 指向左邊的事情存在， 然後將其A，X，W，E，L，L。這是 只是一種數據結構，任意地 是存儲人的名字。 和麥克斯韋是剛剛以下存儲 數組的數組陣列的路徑。 但令人驚訝的有關線索是 如此，而一個鍊錶，甚至 一個數組，我們曾經得到的最好的是 線性時間或對數時間尋找 有人了。 在一個線索的此數據結構中，如果 我的數據結構中有一個名字 而我在尋找麥克斯韋，我 要找到他很快。 我只是尋找M-A-X-W-E-L-L。是否 此數據結構中，通過對比， 如果N是一百萬，如果有一個 在這種數據結構萬個名字， 麥克斯韋仍然將是 發現剛剛M-A-X-W-E-L-L後 步驟。 而David-- D-A-V-I-D的步驟。 換句話說，通過建立 一種數據結構，是 得到了所有這些陣列的，所有這些都 本身支持隨機訪問， 我可以開始尋找達人的 使用的時候這是一個量的名字 成比例的數量不限 的東西，在數據結構中， 像一百萬現有名稱。 花費的時間我找的金額 的M-A-X-W-E-L-L的這種數據結構是 比例不到 的數據結構的大小， 但對名稱的長度。 而現實的 名字我們仰視 永遠不會長瘋了。 也許有人有10個字符 名，20個字符的名稱。 這當然是有限的，對不對？ 有地球上的人誰 有最長可能的名稱， 但這個名字是一個常數 值長，對不對？ 它並不在任何意義上有所不同。 因此，在這種方式中，我們 實現了數據結構 這是恆定的時間查找。 它採取了一些措施 根據輸入的長度， 的名字，但沒有數量 在數據結構中。 因此，如果我們加倍名的數量 從十億一二十億明年， 發現麥克斯韋是要採取 的七個步驟完全相同的數 找到他。 因此，我們似乎已經達到 我們神聖的運行時間的法寶。 

因此，一對夫婦的快速​​公告。 測驗零快到了。 更多的是在球場上的網站 在接下來的幾天。 週一的lecture--這是一個節日 你們是哈佛在星期一。 這不是在紐黑文， 所以我們採取了類 紐黑文的演講在星期一。 一切都將被拍攝下來， 和流現場像往常一樣， 但讓​​今天的結束 用30秒的剪輯 所謂的“深度思考” 通過Daven法納姆，這 在週六的啟發，去年 夜直播的“深度思考” 傑克得心應手，這 現在應該是有意義的。 

電影：現在，“深 思考“由Daven法納姆。 哈希表。 

揚聲器1：好吧，這就是它了。 我們會看到你下週。 

道格：要看到它在行動。 所以，讓我們來看看這個現在。 所以在這裡，我們有一個排序的數組。 

IAN：道格，你能繼續前進，重新啟動 這只是一秒，請。 好吧，相機滾動，所以 的動作，當你準備好，道格，好不好？ 道格：好的，所以我們 這裡是一個未排序的數組。 我也有色的所有元素 紅色，以表明它是，事實上， 未分類。 所以記得的第一件事情，我們做的 是我們排序陣列的左半。 然後我們排序的權利 一半的陣列。 雅達，雅，達，雅，達， 我們把它們合併起來。 我們有一個完全排序的數組。 所以這是如何歸併排序工作。 

IAN：哇，哇，哇， 切，切，切，切。 道格，你不能隨便亞達，雅，達， 雅-DA，通過歸併排序的方式。 

道格：我只是做了。 它的罰款。 我們是好去。 我們只是不停地滾動。 所以無論如何， 

伊恩：你有解釋 它比更充分。 這只是還不夠。 道格：伊恩，我們不 需要回去之一。 它的罰款。 所以無論如何，如果我們繼續merge-- 伊恩，我們在拍戲的中間。 

伊恩：我知道。 我們不能只是亞達，雅，達， 雅-DA，通過全過程。 你必須解釋為什麼 雙方得到合併在一起。 

道格：但我們已經 解釋了兩個sides-- 

伊恩：你剛才表示 他們合併數組。 道格：他們知道這個過程。 他們是很好。 我們已經討論了10次， 

伊恩：你剛才跳過權權。 我們要回一個，你 不能你丫達，雅，達權。 好了，回到之一。 

道格：我要回去 通過所有的幻燈片？ 我的上帝。 這就像第六次，伊恩。 它的罰款。 

伊恩：好的。 你準備好了嗎？ 太好了。 動作。