[音樂播放] ANDI鵬：歡迎來到第6個星期 我們從標準的偏離 週二的部分時間 下午這個可愛的星期天早晨。 謝謝大家了 加入我的今天，但嚴重的是， 掌聲雷動。 這是一個相當大的努力。 我幾乎沒有，甚至使它 在時間，但它是確定。 所以，我知道所有的你， 剛剛去到測驗。 首先，歡迎 另一面的那個。 其次，我們會談論它。 我們將討論的測驗。 我們將談論如何 你正在做的類。 你會沒事的。 我有你的測驗為 你在這裡結束， 所以如果你們想帶 看看吧，完全罰款。 所以很快我們開始的前 今天的議程如下。 正如你所看到的，我們是 基本上速射 通過一大堆數據結構 真的，真的，真的很快。 如此，因此，它不會被 超級互動的今天。 這將只是我的一種喊 事情是你，如果我迷惑你， 如果我走得太快，讓我知道。 他們只是各種數據 結構，並作為部分 您pset獲取如此 即將到來的一周，你會 被要求執行其中的一個， 兩人或許them--他們兩個 在你的pset中。 好了，我只是要 開始與一些公告。 我們一起去了棧和隊列的更多的 深度比我們的測驗以前那樣。 我們一起去了掛 再次，再次列出， 更深入的比 我們在測驗前了。 然後我們來談談哈希 表，樹和嘗試，這 都是很必要的PSET。 然後我們將介紹一些 有用的技巧pset5。 好了，測驗0。 平均為58％。 這是非常低的，所以你們所有 按照表現非常，非常好 這一點。 好看多了，經驗法則是，如果你是 內的平均值的標準偏差 特別是因為我們正處在一個較小 舒適的部分，你完全罰款。 你的軌道上。 生活是美好的。 我知道它的可怕認為 我喜歡這個測驗40％。 我要失敗，這個類。 我答應你，你不 要失敗的類。 你完全罰款。 對於那些你們誰得到了 平均，令人印象深刻的，令人印象深刻， 像，認真做得很好。 我讓他們和我在一起。 隨時來讓他們 在段的末端。 我們如果您有任何我知道， 問題，與他們的問題。 如果我們增加了你的分數 錯了，讓我們知道。 好了，pset5，這是一個非常 奇怪的一周耶魯大學的意義 我們的PSET是由於 週三中午，包括 晚一天，所以它實際上 中午星期二理論上所致。 大概沒有人完成 在週二中午。 這是完全正常。 我們將有辦公時間 今晚以及週一晚上。 和所有的部分將於本週 實際上變成車間， 您可以隨意彈出的 你想要的任何部分， 他們會是怎樣的迷你PSET 講習班上的幫助。 因此，作為這樣的，這是唯一的部 在這裡我們教材。 所有其他部分將集中 專門對pset的幫助。 是嗎？ 聽眾：在哪裡上班時間？ ANDI彭：辦公時間 tonight--哦，很好的問題。 我想今晚辦公時間 在蒂爾或共享。 如果你在網上查詢CS50 你去辦公時間， 應該有一個時間表 告訴您所有的人都。 我知道，無論是今晚 或者明天是水鴨， 我想我們可以有 公地的晚上。 我不太肯定。 好問題。 檢查CS50。 酷，任何有關的問題 計劃在未來像三個日子嗎？ 我保證你們喜歡大衛 說，這是在山頂上。 你們是幾乎沒有。 僅僅三天。 到達那裡，然後我們都來了。 我們將有一個很好的CS-免費休息。 我們會回來的。 我們將深入到網絡 編程與開發， 事情是非常有趣的對比 一些其他的pset的。 而這將是淒涼， 我們有很多的樂趣。 我們將有更多的糖果。 對不起，糖果。 我忘了糖果。 這是一個粗糙的早晨。 所以，你們是幾乎沒有， 而且我非常自豪的你們的。 好了，棧。 誰愛傑克的問題 和他的衣服上的測驗？ 沒有人？ 好了，這很好。 所以基本上，你可以 圖片傑克，這個傢伙在這裡， 喜歡拿衣服 出棧的頂部， 他把它放回 之後，他在堆棧的完成。 因此以這種方式，他從未 似乎越來越 到的底部 堆在他的衣服。 所以，這樣的描述 基本的數據結構 一個堆棧是如何實現的。 從本質上講，想想 協議棧的任何棧對象 你把東西到頂部， 那麼你從頂部彈出出來。 因此，後進先出法是我們喜歡的縮寫 以use--後進先出。 所以，最後到的頂部 棧是第一個出來。 這樣一來，兩個詞 我們喜歡聯想 與被稱為push和pop。 當你把一些東西到 堆棧和你的流行回來了。 所以我想這是種 抽象的概念，對於那些你 誰希望看到像 這實際執行 在現實世界中。 你們有多少人寫了一篇文章， 也許就像一個小時之前，這是由於， 你不小心刪除了一個巨大的 大塊的它，就像不小心？ 然後呢控制做 我們用它來把它放回去？ 控制-Z，是嗎？ 控制-Z，所以倍量 控制-Z已經救了我的命， 救了我的屁股，每次 該真實通過煙囪實現。 基本上所有的信息 這是您的Word文檔， 它被壓入和彈出的意願。 所以基本上每當你 刪除任何東西，你的流行回來了。 然後，如果你需要它回來，你 推，這是控制-C一樣。 所以，現實世界中的功能 多麼簡單的數據結構 可以幫助你的日常生活。 因此，一個結構的方式， 我們實際上創建一個堆。 我們定義類型結構，然後 我們把它在底部堆。 和棧內， 我們有兩個參數 我們基本上可以操縱， 所以我們有字符的字符串星能力。 所有這一切是做 正在創建一個數組 我們可以存儲任何你想要的 我們可以判斷其能力。 能力是剛剛最大金額 項目我們可以把這個數組。 INT大小是保持計數器 跟踪有多少項目是目前 在棧。 所以後來我們就可以跟踪，A， 無論有多大的實際堆棧， 和，B多少該堆棧的 我們充滿因為我們不希望 溢出超過了我們的能力。 因此，例如，這個可愛的 問題是你的測驗。 從本質上講，我們如何推動 到堆棧的頂部。 很簡單。 如果你看看吧， 我們將穿行於此。 如果[聽不清] size-- 請記住，當你 要訪問任何 一個結構內的參數， 你做struct.parameter的名稱。 在這種情況下，s是 我們的疊層的名稱。 我們要訪問的大小 這一點，所以我們做s.size。 所以只要尺寸不 等於能力，長 因為它是低於產能， 要么就在這裡工作。 你想訪問內 你的籌碼，所以s.strings， 你打算把新號碼 要插入到那裡。 遠的不說，我們將要 插入INTñ壓入堆棧， 我們可以做s.strings， 括號，s.size等於ñ。 由於尺寸是我們 當前有在堆棧 如果我們要推動 它，我們剛剛訪問 無論大小，則 疊層的當​​前飽脹， 我們推INTñ到它。 然後我們要確保 我們也遞增了n個大小， 所以我們可以跟踪我們已經 增加了一個額外的東西到堆棧中。 現在我們有一個更大的尺寸。 這是否在這裡是有意義的 大家，如何在邏輯上是否可行？ 這是一種快捷。 聽眾：你可以走了 在s.stringss.strings [s.size]了嗎？ ANDI彭：當然，有什麼呢 s.size目前給我們？ 聽眾：這是當前大小。 ANDI鵬：沒錯，所以 目前的指數，我們的規模是， 所以我們希望把新的整數 我們要插入s.size。 這是否有意義？ 因為s.strings，所有的 是是陣列的名稱。 所有這是訪問 我們的結構內的數組， 因此，如果我們想 將正成指數， 我們可以只訪問 使用括號s.size。 酷。 好吧，流行，我偽出來 為你們這些傢伙，但類似的概念。 這是否有意義？ 如果尺寸大於 大於零，則 知道你想要拿東西 出，因為如果尺寸不 大於零，則 有沒有在堆棧中。 所以，你只需要執行 這段代碼，它只能 彈出如果有什麼流行。 所以如果尺寸更大 大於0，我們減去大小。 我們減小大小，然後返回 無論是內部的，因為 通過彈出，我們要 無論是存儲的訪問 在堆棧的頂部的索引。 一切有意義嗎？ 如果我讓你們寫了這一點， 將你們能寫出來？ OK，你們可以玩它。 不用擔心，如果你不明白這一點。 我們沒有時間去編寫 它今天因為我們 得到了很多這些結構 穿過去，但本質 偽代碼，非常，非常相似推。 只要跟著邏輯。 請確保你所訪問的所有 你的結構功能正常。 是嗎？ 聽眾：請問這些幻燈片和 這整個事情高達今天十歲上下的？ ANDI彭：始終，是的。 我會盡量把 這像一個小時後。 我會通過電子郵件大衛，大衛將嘗試 把它像在此之後一個小時。 好了，接下來我們進入這個其他 可愛的數據結構稱為隊列。 正如你們所看到的，一 隊列，對於我們中間英國， 所有這是一條線。 那麼相反的是 你覺得一個堆棧， 隊列是什麼 在邏輯上，你認為它是。 它保持由FIFO的規則， 這是先入先出。 如果你是第一個 一個在行，你 第一個 出來的線。 所以，我們喜歡把這種 在出隊，並排入隊列。 如果我們想要添加的東西 我們的隊列中，我們入隊。 如果我們要離隊，或採取 一些東西，我們出隊。 因此，同樣的道理，我們是那種 創建固定大小的元素，我們 可以存儲一定的 的事情，但是我們也可以 改變我們正在把 他們的內部參數 基於什麼類型 功能我們想要的。 所以棧，我們希望最後 酮，N是第一個出來。 排隊是我們要的第一件事情 在成為第一件事出去。 因此，結構型 定義，你可以看到， 這是一個有點不同 從什麼堆棧是 因為我們不僅要保持 軌道的其中該尺寸是目前， 我們也想跟踪頭 以及我們當前有。 所以我覺得它更容易 如果我畫這件事。 因此，讓我們想像一下，我們已經有了一個隊列， 所以我們說，頭就在這裡。 該行的負責人，讓我們 只是說這是目前在那裡， 我們要插入 事到隊列。 我要去基本上調用大小 是同樣的事情，尾， 哪裡的隊列的末尾。 遠的不說大小就在這裡。 那麼，如何切實 東西插入到隊列中？ 什麼樣的指標，我們要放置 在這裡我們要插入。 如果這是開頭的 排隊，這是它的結束 或者它的大小，我們在哪裡 要添加的下一個對象？ 聽眾：[聽不清] ANDI鵬：沒錯，你想添加 它取決於你寫的。 這要么是空白，或為空。 所以，你想可能添加 在這裡，因為如果大小is-- 如果這些都滿了，你想 將其添加在這裡，對不對？ 所以這就是，雖然非常非常 簡單，不太總是正確的 因為主要的區​​別 隊列和堆之間 是，隊列可以 實際上被操縱 使頭部的變化 這取決於你想上哪兒 您的線索年初啟動。 其結果，你的尾巴 也不會改變。 所以看看 此代碼現在。 正如你們也被要求 寫出來的測驗，入隊。 也許我們會聊過為什麼 答案是什麼。 在一個我不太適合這一行， 但本質上這一段代碼 應該是在一行上。 花想30秒。 看看，看看為什麼 這是，它是這樣的。 非常，非常相似的結構，非常，非常 類似的結構與前面 堆疊除了可能 一行代碼。 而這一行代碼 確定的功能。 它真的與眾不同 從一摞一個隊列。 任何人想採取刺 在解釋為什麼你 拿到這裡這個複雜的事情？ 我們看到的回報我們 美妙的朋友模量。 正如你們很快就會到來 在編程認識到， 幾乎任何時候，你需要的東西 環繞什麼， 模將是這樣做的方式。 因此，了解的是，沒有人想 嘗試解釋該行代碼？ 是的，所有的答案都 接受和歡迎。 聽眾：你是在跟我說話？ ANDI彭：是的。 聽眾：哦，不後悔。 ANDI彭：好，讓我們 穿行此代碼。 所以，當你想 添加的東西到一個隊列， 在可愛的情況下頭部發生 是在這裡，這很容易讓我們 剛走到最後 插入的東西，對不對？ 但是隊列的整點 頭部實際上可以動態地 不同的地方改變我們 希望我們的Q的開始是， 正因為如此，在尾 也不會改變。 所以，想像一下，這是不是 排隊，而是這是隊列。 比方說，頭就在這裡。 比方說，我們的隊列看上去像這樣。 如果我們想轉向哪裡 該行的開始是， 假設我們轉向頭 這種方式和尺寸在這裡。 現在我們要添加一些 此隊列，但你們可以看到， 它不是那麼簡單，只是 添加任何的尺寸後， 因為那樣的話，我們用完 我們的實際數組的邊界。 當我們要真正增加在這裡。 這是一個隊列的美 是我們的，視覺上 看起來像行是這樣的， 但是，當存儲在數據結構中， 他們給它像一個循環。 它種環繞 到前以同樣的方式 該行也可以換 各地根據地方你 希望該行的開頭是。 因此，如果我們拿 往下看這裡，讓我們 說我們想創造一個 函數調用排隊。 我們希望加INT n為進的Q值。 如果q.size q--我們會打電話給我們的數據 結構 - 如果我們的queue.size不 等於能力，或者 這是不到容量， q.strings是我們q內的陣列。 我們要設置 這等於q.heads， 這是在這裡，再加上q.size 模量由容量，這 包裹我們回在這裡。 所以在這個例子中，索引 頭是1，對吧？ 大小的指數為0，1，2，3，4。 因此，我們可以做到1加4模 我們的產能是5。 是什麼給我們？ 什麼是索引 這樣來的？ 聽眾：0。 ANDI彭：0， 恰好就在這裡， 所以我們希望能夠 插入到這裡。 所以這個公式在這裡種 僅適用於任何數字 不同的地方你 頭部和你的尺寸是。 如果你知道這些 事情是，你知道 正是您要插入 您的隊列後，無論是。 這是否有意義給大家？ 我知道怎樣的一個大腦 傳情特別是因為這 排在你競猜的善後工作。 但希望大家 現在可以理解 為什麼這個解決方案或本 功能是，它是這樣的。 任何人都有點不清楚的是什麼？ 確定。 所以現在，如果你 要離隊，這 是我們的頭會轉向 因為如果我們要出列， 我們不取下q的末端。 我們要起飛的頭，對不對？ 因此，作為結果，磁頭會改變， 這就是為什麼當你入隊， 你必須保持跟踪 在這裡你的頭，你的尺寸 是能夠插入 到正確的位置。 所以，當你出列， 我還偽出來。 隨意，如果你想 嘗試編碼了這一點。 要移動頭部，對不對？ 如果我想離隊，我 將移動頭以上。 這將是頭部。 而我們目前的規模會 減去因為我們不再 在陣列中四個元素。 我們只有三個，然後我們要 返回不管裡面儲存 頭部，因為我們希望藉此 值出所以非常相似的棧。 只要你參加 來自不同的地方， 你必須重新分配指針 不同的地方作為一個結果。 從邏輯上講，每個人都遵循？ 太好了。 好了，我們要商量了一下 更深入的了解鍊錶 因為他們將是非常，非常有價值 您在本週的過程 pset中。 鍊錶，因為你們 能記住，一切又都 是有一定的節點節點 兩者的值和一個指針值 連接在一起的 通過這些指針。 因此如何在結構 我們在這裡創建一個節點，我們 是int n，這個是什麼 在商店或字符串值n 或者任何你想 調用它，焦炭星ñ。 結構節點星，這是指針 要在每個節點上， 你將有 對下一個指針點。 你得頭 鍊錶那 要指出的其餘部分 等等，等等的值 直到你最終到達終點。 而這最後一個節點僅僅是 要沒有一個指針。 這將指向 空，這就是當 你知道你已經打了 您的鏈接列表的末尾 就是當你的最後一個指針 不指向任何東西。 因此，我們要去多一點的 關於深入怎麼一會可能 搜索一個鍊錶。 記住是一些 該鍊錶的缺點 詩句關於搜索的陣列。 數組可以二進制搜索，但 你為什麼不能做，在一個鍊錶？ 聽眾：因為他們都是互相聯繫在一起， 但你不太知道在哪裡 [聽不清]。 ANDI彭：是的，正是這樣記 一個數組的輝煌 是事實，我們有 隨機存取存儲器，其中 如果我想從指數值 六，我可以說，指數六， 給我的價值。 那是因為數組排序 在一個連續的內存空間 在一個地方，而 一種鍊錶 是隨機散佈各地， 而只有這樣，你可以找到一個 是通過指針，告訴你 的，其中該下一個節點是地址。 所以作為結果，只有這樣 通過一個鏈接列表來搜索 是線性搜索。 因為我完全不知道在哪裡 在該鏈接的表的第12值是， 我必須遍歷全部 那鏈接列表中的一個 由一個從頭部到第一節點， 到第二個節點，到第三節點， 一路下來，直到我終於搞定 到這個節點，我要找的是。 因此在這個意義上說，搜索 上鍊錶總是n。 它總是ñ。 它總是以線性時間。 這樣一來，代碼中 我們實現這一點，而這 有點新的你們，因為你們 人還沒有真正談過或曾經 在如何看到指針 通過搜索指針， 因此，我們將演練 這個非常，非常緩慢。 所以布爾檢索，權， 讓我們想像一下，我們希望 創建一個名為函數 搜索返回true 如果您發現裡面的鏈接的價值 列表，並將否則返回​​false。 節點明星名單 目前只是指針 在你的鏈接列表中的第一項。 INT N是你的價值 搜尋在該列表中。 因此，節點星指針等於名單。 這意味著我們正在設置 和創建的指針 到列表的內部該第一個節點。 每個人都和我在一起？ 因此，如果我們當中去 回到這裡，我會 初始化指針指向 無論頭部的名單。 然後，一旦你到這裡， 同時指針不等於空， 所以這是我們在其中循環 將要隨後遍歷 我們因為什麼列表的其餘部分 發生在指針等於null？ 我們知道，我們have-- 聽眾：[聽不清] ANDI鵬：沒錯，所以我們知道， 我們已經達到列表的末尾，對不對？ 如果你回到這裡，每個節點 應指向另一節點 等等等等 直到你打最後 您鍊錶的尾部， 它具有一個指針，只是 不點不是沒有其他任何地方。 所以你基本上知道 你的名單仍然有上升 直到指針不等於 null，因為一旦它等於空， 你知道，有沒有更多的東西。 所以這是循環，其中我們 將有實際的搜索。 而如果pointer--你看 那種箭功能那裡？ 因此，如果指針指向為n，如果 在n等於等於n個指針， 因此，這意味著，如果 你是指針 在每個結束搜索 節點實際上等於值 你要找的話 要返回true。 所以基本上，如果你在一個節點 有你正在尋找的價值， 你知道你已經 能夠成功地搜索。 否則，你要設置 指針到下一個節點。 這就是這條線在這裡做。 指針等於下一個指針。 每個人都看到了的工作？ 而且基本上你要只 遍歷列表的全部， 重置每一次，直到你的指針 你最終擊中列表的末尾。 你知道有沒有 更多的節點進行搜索， 然後你就可以返回false 因為你知道，哦，好吧， 如果我已經能夠搜索 通過列表的全部。 如果在這個例子中，如果我想 尋找值10， 我開始在頭， 我搜索一路下跌， 而我最終得到了這一點，這 一個指針指向空， 我知道，廢話，我想10不 這個名單是因為我找不到它。 而我在列表的末尾。 而在這種情況下，你知道 我將返​​回false。 讓那浸泡在一點點。 這將是非常 重要的是你的pset中。 它的邏輯很簡單，也許 語法只是實現它。 你們想使 確保你理解。 酷。 好了，我們怎麼會 插入節點，右， 到列表中，因為記住 是什麼的有什麼好處， 具有的鏈接列表與 在存儲方面的陣列？ 聽眾：這是動態的， 所以它更容易用於： ANDI鵬：沒錯， 所以它是動態的， 意味著它可以擴大和縮小 取決於用戶的需要。 因此，在這個意義上，我們並不需要 浪費不必要的內存，因為我 如果我不知道有多少值要 存儲，它沒有任何意義，我 創建因為數組 如果我想存儲10個值 我創建的1000陣列，這是 大量浪費的內存，配發。 這就是為什麼我們要使用一個鏈接 列表能夠動態 改變或縮小我們的規模。 而這樣就使得插入 有點複雜。 既然我們不能隨意訪問元素 將我們的數組的方式。 如果我想插入元素 進入第七個指標， 我只是將它插入 進入第七個指標。 上一個鍊錶，它不 很容易地工作， 所以如果我們想插入 這裡一個在該鏈接的表， 在視覺上，它很容易看到。 我們只是希望將其插入那裡， 就在列表的開頭， 後頭部右側。 但在其中，我們有方式重新分配 指針是不是有點繞口 或者，從邏輯上講，這是有道理的，但 你要確保你擁有了它 完全下來，因為 你想的最後一件事 是重新分配的指針的 我們在這裡做的方式。 如果取消引用 從頭指針為1， 然後突然的的 您的鏈接列表的其餘部分 是丟失，因為你還沒有真正 創建的臨時任何東西。 這是指著2。 如果重新分配的指針，那麼 列表的其餘部分完全喪失。 所以，你想成為 非常非常小心這裡 先分配 無論從任何你指針 要插入到哪裡 你想，然後你 可以取消引用列表的其餘部分。 因此，這適用於任何地方 你想插入。 如果要插入的 頭，如果你想在這裡回答， 如果要插入的 最後，好了，我到底 猜你只想 有沒有指針，但你 要確保你不 失去你的列表的其餘部分。 你總是要確保 你的新節點指向 對任何你 要插入， 然後您可以添加鏈接上。 大家都清楚了嗎？ 這將是 一個真正的問題。 其中一個最重要的問題 你要對你的pset 是，你要嘗試創建 鍊錶和插入件事情 但當時只是失去了 剩下的鍊錶中。 而你要像我 不知道為什麼會這樣？ 而且這是一個痛苦的經歷 並搜索所有的指針。 我保證你在這pset中， 書寫和繪畫這些節點出 將是非常，非常有幫助。 所以，你可以完全跟踪 在那裡所有的指針， 什麼錯， 您所有的節點， 你需要做的訪問或 插入或刪除，或任何人。 每個人都好有嗎？ 酷。 因此，如果我們想看看代碼？ 哦，我不知道，如果我們 可以看到the--好了， 頂部所有它是一個功能 在這裡我們要命名插入 插入INT n為進鍊錶。 我們將穿行於此。 這是一個很大的代碼，有很多新的語法。 我們會沒事的。 所以在頂部，每當 我們要創建什麼 什麼我們需要做的，特別是如果你 希望它不被存儲在棧上 但在堆？ 我們去的malloc，對不對？ 因此，我們要創建一個指針。 節點，指針，新的平等 MALLOC一個節點的大小 因為我們要創建的節點。 我們想要的量 內存節點佔用 將予配發的 創建新的節點。 然後我們要去檢查 查看是否有新的equals等於空。 還記得我們說什麼？ 不管你的malloc， 要做就要你總是做什麼？ 你必須經常檢查，看看 無論是否是空。 例如，如果你的工作 系統完全滿， 如果你在沒有更多的內存 所有你嘗試的malloc， 它會返回null為您服務。 所以，如果你嘗試使用它 當它指向空， 你不打算能 來訪問該信息。 所以，正因為如此，我們希望使 相信只要你mallocing， 你總是檢查，如果看到 給你的內存為空。 如果不是，那麼我們可以將 與我們的代碼的其餘部分。 所以，我們要 初始化新節點。 我們要做新的n等於ñ。 然後我們要做的 設置新的新指針 為null，因為現在我們不這樣做 想要的任何東西它指向。 我們不知道在哪裡 它會放你， 然後，如果我們想 在頭部插入， 那麼我們就可以重新分配 指針的頭部。 每個人都遵循的邏輯 在那裡發生的事情？ 我們所要做的是創建一個新的 節點，設置指針為空， 然後重新分配 它的頭部，如果我們 知道我們要在頭部，將其插入。 然後將頭是要 指向新的節點。 每個人都與該行嗎？ 所以這是一個兩步過程。 你必須先分配 無論你正在創建。 設置指針到 引用，然後你 能種非關聯化 第一個指針 並指出其向新的節點。 不管你想要去插入， 該邏輯要成立。 這有點像分配 臨時變量。 請記住，你已經有了 確保你 不要失去跟踪，如果你換了。 你要確保你有一個 那種保持臨時變量 軌道，其中那些事兒 存儲，讓你 不丟失任何價值的過程 像瞎搞吧。 OK，這樣的代碼將出現在這裡。 你們採取部分後的樣子。 它會在那裡。 所以我想如何做 這種差異，如果我們想要 插入到中間或結束？ 有沒有人有什麼想法 偽代碼作為邏輯參照 我們將採取如果我們想要 將其插入中間？ 因此，如果我們想在將其插入 頭，我們所要做的就是創建一個新的節點。 我們設定的指針 新節點的任何頭部， 然後我們設置了頭 新的節點，對不對？ 如果我們想將其插入到中間 名單，你會我們有什麼關係？ 聽眾：它仍然 是類似的過程 像分配指針 然後，指派該指針， 但我們必須找到那裡。 ANDI鵬：沒錯，所以完全 但你同樣的過程 必須找到在什麼地方你 希望該新指針進入， 所以如果我要插入到 中間的鏈接列表中 - 確定， 讓我們說這是我們的鍊錶。 如果我們想，就在這裡插， 我們要創建一個新的節點。 我們要去的malloc。 我們要創建一個新的節點。 我們將分配 指針在這裡這個節點。 但問題是不同 從其中頭部是 是，我們確切地知道 其中頭。 這是正確的，在第一次，對嗎？ 但在這裡，我們一定要保持跟踪 在那裡我們將其插入。 如果我們插入我們 在此節點，我們有 以確保該 一個先前到該節點 是一個重新分配的指針。 所以，那麼你必須種 跟踪兩件事情。 如果你跟踪，其中這 節點當前的插入。 您還可以跟踪在哪裡 那你看前面的節點 也有。 每個人都好有嗎？ 確定。 如何插入結束了嗎？ 如果我想將其添加這裡 - 如果我想 到一個新的節點添加到列表的末尾， 怎麼可能我去這樣做？ 聽眾：那麼目前， 最後一個人指著空。 ANDI彭：是的。 沒錯，所以這一塊 目前指向知道， 所以我想，在這個意義上，它是 很容易添加到列表的末尾。 所有你需要做的是設置 等於空，然後繁榮。 就在那裡，很容易。 很簡單。 非常相似的 頭，但在邏輯上你 想確保該步驟 你邁出做任何的這個， 您關注的沿。 這是很容易的，在中間 你的代碼，陷入上， 哦，我有這麼多的三分球。 我不知道在哪裡 任何指向。 我甚至不知道我在哪個節點。 這是怎麼回事？ 放鬆，平靜下來，深呼吸。 繪製出你的鏈接列表。 如果你說，我知道在什麼地方 我需要插入到這 我知道如何重新分配我 指針，多，更容易圖片 out--多，更容易不 迷失在你的代碼的漏洞。 每個人都與該行嗎？ 確定。 所以我想一個概念，我們還沒有 真之前談到現在， 我猜你可能 不會遇到太大yet-- 它是一種先進的concept-- 是，我們其實有一個數據 結構，稱為一個雙向鍊錶。 所以當你們看到的， 所有我們正在做的是創造 一個實際值，額外 指針在我們每個節點 也指向前一個節點。 因此，我們不僅有我們的 節點指向下一個。 他們還指出，前一個。 我將忽略這兩個現在。 所以，那麼你有一個鏈 可以移動兩種方式， 然後它是一個更容易一些 從邏輯上跟隨。 喜歡這裡，而不是 飼養的，哦軌道，我 要知道，這個節點是 一個，我不得不重新分配， 我可以去這裡 只是拉前面的。 後來我知道確切位置 也就是說，然後你 不必遍歷 整體鍊錶。 這是一個更容易一些。 但正因為如此，你必須加倍 指針的量， 這是內存的兩倍。 這是一個很大的指針跟踪。 這是一個有點複雜，但它的 多一點人性視 你試圖完成什麼。 所以這種類型的數據 結構完全存在， 和結構是非常非常 簡單以外的所有你遇到的， 而不只是一個指向下， 你也有一個指針以前。 這就是差異。 每個人都好有嗎？ 酷。 好了，所以現在我 要真正花可能 像15至20分鐘或散裝 在節剩下的時間中 談論哈希表。 有多少你們的 已經閱讀pset5規範呢？ 好了，好了。 這比通常的50％以上。 這是確定的。 所以當你們將會看到， 你在pset5挑戰 將實施字典 在這裡裝載了14萬字 我們給你和拼寫檢查 這對所有的文字。 我們會給你隨機 文學作品的。 我們會給你奧德賽。 我們會給你伊利亞特。 我們會給你王牌大賤諜。 而你的挑戰 將是拼寫檢查 在所有的每一個字 這些字典 本質上與我們的拼寫檢查器。 所以有幾部分組成 創建這個PSET的， 首先你想成為 能夠實際加載 所有的話到您的 字典，然後你 希望能夠 拼寫檢查所有的人。 所以，正因為如此，你將需要 一個數據結構可以做到這一點快 並有效地和動態。 所以我想最簡單的 辦法做到這一點，你 可能會創建一個數組，對不對？ 存儲的最簡單的方法就是你 可以創造14萬字的數組 而只是把它們都在那裡和 然後通過二進制搜索遍歷他們 或者通過選擇或不是 - 遺憾的是真實的排序。 你可以對它們進行排序，然後遍歷它們 由二進制搜索或者只是線性搜索 和公正的最後的話，但 需要大量的內存， 這不是很有效。 因此，我們要開始 說起製作方法 我們的運行時間更有效。 而我們的目標是獲得 定時間，其中 這幾乎就像陣列，其中 你有即時訪問。 如果我想搜索什麼， 我希望能夠公正， 熱潮，發現它完全，並將其拉出。 等的結構，其中 我們將變得非常接近 到能夠訪問恆定 當時，這聖杯 在恆編程 時間被稱為哈希表。 於是大衛前面提到的 [聽不清]在演講一點點， 但我們要真正 下潛深，本週 對多數民眾贊成有關一片 如何哈希表的工作原理。 這樣的方式，一個散列 表作品，例如， 如果我想存儲一堆話，一 一堆英文單詞的， 我可以在理論上把 香蕉，蘋果，獼猴桃，芒果，對， 和哈密瓜所有的只是一個數組。 他們都可以融入其中，並且被找到。 這將會是一種痛苦來 通過搜索和訪問， 但這樣做的更簡單的方法是 我們實際上可以建立一個結構 所謂的哈希表，其中我們的哈希值。 我們通過運行所有的鑰匙 散列函數，一個方程， 這將它們全部納入 某種形式的值 那我們就可以存儲到 鍊錶基本上陣列。 所以在這裡，如果我們想 存儲英文單詞， 我們可能潛在只是，我不知道 知道了，把所有的第一個字母 成某種形式的數目。 因此，例如，如果我想 一個是同義詞apple-- 或為0的索引，和 乙的同義詞1， 我們可以有26項 可以只是存儲 所有的字母 字母表，我們將開始。 然後我們就可以有 蘋果0的指數。 我們的指數有香蕉 1，哈密瓜2的指數， 等，等等。 就這樣，如果我想搜索 我的哈希表和訪問蘋果， 我知道蘋果開始 一個A，我確切地知道 它必須是和散列 表索引0，因為 函數的先前分配。 所以，我不知道，我們是 用戶程序在哪裡 你將被控 arbitrarily--不要隨意， 與試圖若有所思 想好方程 要能傳播 你所有的價值觀 在某種程度上，他們可以輕鬆地訪問 後來在與像一個公式 你，你自己，知道了。 所以，在這個意義上，如果我想去 芒果，我知道，哦，它以M開頭。 它必須是12的索引處。 我沒有通過任何搜索。 我知道exactly--我可以只去 12和指數拉出了這一點。 每個人都清楚如何 哈希表的功能的工作？ 這是一種只是一個更複雜的陣列。 這就是它。 確定。 所以我想，我們碰到 這個問題是什麼 發生，如果您有多個事 這給你同樣的指數？ 所以說我們的功能，所有這 做的是採取的第一個字母 並把它轉換成一個 相應的0至25指數。 這是完全正常，如果 你只有每個之一。 但第二啟動 有更多的，你 將有什麼所謂的衝突。 所以，如果我嘗試插入埋到一個哈希 表中已經有香蕉就可以了， 有什麼事情發生時， 您嘗試插​​入呢？ 壞事情，因為香蕉 在索引中已存在 您希望將其存儲研究。 種漿果是喜歡啊，我該怎麼辦？ 我不知道哪裡去了。 我該如何解決呢？ 等會有種你們 看到我們做這個棘手的事情 在這裡，我們實際上可以種 創建鏈接的列表中我們的陣列。 這樣一來，最簡單的方法 思考這個問題， 所有的哈希表是一個 數組鍊錶。 因此，在這個意義上說，必須 這個美麗的指針數組， 然後在每個指針 該值，在該索引， 可實際卻指向其他的東西。 所以你把所有這些不同的 鏈條脫落一個大陣。 所以在這裡，如果我 要插入漿果， 我知道，行，我要輸入 它通過我的哈希函數。 我將結束與指數 1，然後我將能夠有 此只是一小的子集 巨大的14萬字的字典。 然後，我來找找看 通過該1/26。 而這樣的話我可以插入 之前或之後香蕉漿果 在這種情況下？ 之後，對不對？ 所以，你會想 香蕉之後插入這個節點， 所以你要插入 在該鏈接列表的尾部。 我要回去 這一張幻燈片， 所以你們可以看到 哈希函數的工作。 所以散列函數是這樣的方程 你正在運行的一種輸入 通過獲得任何指數 你希望它朝著分配。 因此，在這個例子中，所有我們想要 做的是採取的第一個字母， 把它轉換成一個指數，那麼我們 可以存儲我們的散列函數在。 所有我們在這裡所做的是我們 轉換的第一個字母。 所以keykey [0]只是第​​一個字母 我們遇到的任何字符串， 我們通過研究。 我們要轉換，要上，和 我們用大寫字母A減去， 因此，所有的做 給我們提供了一些 在其中我們可以散列我們的價值觀上。 然後，我們將 返回哈希模量的大小。 要非常，非常小心 因為，從理論上說，在這裡 您的哈希值可以是無窮大。 它可能只是去和和。 這可能是一些非常， 真正大的價值， 但因為你的哈希表 你已經創建只有26指數， 你要確保你的 modulusing讓你 不run--它是相同的 為您的queue--事 這樣你就不會跑出 您的散列函數的底部。 你想換回來各地 在[聽不清]時相同的方式 你必須像一個非常， 非常大的信，你 不想，要 剛跑出結束。 這裡同樣的事情，你要確保 它不流失年底通過包裝 周圍的表的頂部。 所以，這只是一個很 簡單的哈希函數。 所有這一切確實是拿第一 不管我們輸入的字母是 並把它轉換成一個索引 我們可以把我們的哈希表。 是啊，所以我之前說的， 我們解決衝突的方式 在我們的哈希表有， 我們所說的，鏈接。 所以，如果你試圖插入多 字開頭同樣的事情， 你將有一個哈希值。 鱷梨和蘋果，如果你 通過我們的散列函數運行它， 將會給你 數相同，為0的數目。 這樣一來，我們的方式解決是 樣的，我們實際上可以將它們鏈接 通過鍊錶在一起。 因此在這個意義上， 你們可以看樣 如何數據結構 我們已經預先設定 像葡萄乾鍊錶樣 可走到連成一片。 然後你就可以創建遠 更有效的數據結構 可以處理更大的量 數據，動態調整不同 您的需要。 大家都清楚了嗎？ 大家一種明確 在這裡會發生什麼？ 如果我想insert--什麼是 水果有，我不知道開始， B，比其他漿果，香蕉。 聽眾：黑莓。 ANDI彭：黑莓，黑莓。 哪裡黑莓跑到這裡？ 好了，我們實際上已經沒有排序 這還沒有，但理論上 如果我們想有這樣的 按字母順序排列， 應該在哪裡黑莓何去何從？ 聽眾：[聽不清] ANDI鵬：沒錯，在這裡後，對不對？ 但因為它是非常困難的 reorder--我想這是給你們。 你們可以完全 實現任何你想要的。 的更有效的方式 對這樣做也許 將是您的排序鏈接 列出按字母順序， 所以，當你 插入的事情，你想 以確保將其插入 按字母順序 讓那麼當你 試圖尋找他們， 你不必穿越一切。 你知道確切位置 它是，它更容易。 但是，如果你種得 東西隨意穿插， 你仍然會有 到反正遍歷。 所以，如果我想只 黑莓在這裡插入 我想搜索 它，我知道，哦，黑莓 必須先從1的指數，所以我 認識瞬時只搜索1。 然後，我可以種 遍歷鍊錶 直到我到黑莓， 和then--是嗎？ 聽眾：如果你想create-- 我想這樣是一個非常簡單的哈希 功能。 如果我們想做的事 多層，像的， 好了，我們要分成 像所有字母文字 然後再次喜歡上另一組 內的字母， 在我們把如哈希 哈希表內的表， 或者像函數中的一個函數？ 或者是that-- ANDI彭：所以，你的散列 function--你的哈希表 因為你希望它可以大。 因此，在這個意義上，我認為 這是非常容易的，很 簡單對我來說，只是排序依據 在第一個單詞的字母。 所以有唯一的26選項。 我只能得到26選項 0至25，因為它們只能 開始從A到Z，但如果你想 添加，或者，更複雜 或更快的運行時間，以你的 哈希表，你絕對 可以做各種各樣的事情。 你可以讓你自己 公式，讓你 在更多的分銷您 的話，那麼當你搜索， 這將更快。 這完全取決於你的傢伙 要如何實現這一點。 把它看成僅僅桶。 如果我想有 26桶，我要去 整理東西到這些水桶。 但我將有一大堆 的東西在每個桶， 所以如果你想讓它 更快，更高效， 讓我有一百桶。 但你必須找出一個 這樣的事情進行排序，使他們 在適當的水桶他們應該研究。 但是當你真正 想看看那個桶， 它的速度快了很多，因為有 在每個桶少的東西。 所以，是的，這其實 的伎倆你們在pset5 是，你會 面臨的挑戰是只創建 什麼是最有效的 功能，你能想到的是 能夠存儲和查詢這些值。 完全取決於你們 然而，要做到這一點， 但是這是一個非常好的點。 那什麼邏輯你 要開始思考 是，好了，我為什麼不賺更多的桶。 然後，我要搜索 更少的東西，然後也許我 有一個不同的哈希函數。 是啊，有很多方法可以做到這一點 PSET，有些人比別人快。 我完全將只是看看 快速是最快你們會 能夠得到您的功能才能生效。 OK，每個人都好於 鏈接和哈希表？ 它實際上是一個非常簡單的 概念，如果你想想看。 所有這是區分什麼 您的輸入是成桶， 對它們進行排序，然後搜索 列出了還有的關​​聯。 酷。 好了，現在我們有一個不同的排序 數據結構，這就是所謂的一棵樹。 讓我們去談談嘗試 這是明顯不同的， 但在同一類別。 從本質上講，所有的一棵樹，而不是 對組織數據以線性方式 一個哈希表does--您 知道的，它有一個頂部和一個底部 然後你有種鏈接關閉它 - 一對 樹有你所說的根上面， 然後它有它周圍的葉子。 所以，你在這裡 僅僅是頂節點 指向其他節點，該點 到更多的節點，依此類推等等。 所以你就必須拆分分支機構。 這是組織的只是以不同的方式 數據，因為我們把它稱為一棵樹， 你們just--這只是 模擬出看起來像一棵樹。 這就是為什麼我們把它叫做樹。 哈希表看起來像一個表。 樹看起來就像一棵樹。 所有這是一個獨立的 節點組織方式 根據你的需求是什麼。 所以，你有一個根， 那麼你有葉子。 該辦法，我們可以特別 想想這是一個二叉樹， 二叉樹只是一個 樹的特定類型 其中每個節點僅分 於，在最大，其他兩個節點。 所以，在這裡你有不同的 對稱性在你的樹 這使得一種更加便捷地查詢 在什麼樣的價值觀，你是因為你 始終左或右。 從未有像從左側第三 向左或從左側的第四。 這只是你有左，右 你可以搜索上述兩種的。 所以這是為什麼有用嗎？ 的方式，這是 有用的是，如果你正在尋找 通過值來搜索，對不對？ 而不是執行二進制 在一個錯誤數組搜索， 如果你想成為能夠插入節點 並帶走節點的意願，也 保存搜索 二進制搜索的能力。 因此，在這種方式中，我們是那種 tricking--記得當時我們 說鍊錶不能二進制搜索？ 樣的，我們正在創建一個數據結構 該技巧，進入工作。 所以因為鍊錶是線性的， 它們只能鏈接一前一後。 那種我們可以有 不同類型的指針 該點不同的節點 這可以幫助我們與搜索。 所以在這裡，如果我想 有一個二進制搜索樹， 我知道，我的中間，如果55。 我只是要創建 因為我的中間，因為我的根， 然後我將有 值剝離它。 所以在這裡，如果我要去尋找 66的價值，我可以在55開始。 這比55 66更高？ 的確是這樣，所以我知道我每畝搜索 I N這棵樹的右指針。 我去77。 行，是66小於或大於77？ 它的不足，所以你知道，哦， 具有是左節點。 所以，我們在這裡種保護 所有有關數組偉大的事情， 所以像動態調整 的對象，是 能夠插入和刪除隨意， 而不必擔心固定 量的空間。 我們仍然保留所有的 那些美好的事物 同時還能夠保存 登錄並搜索二進制搜索的時間 我們只是以前 能夠得到一個短語。 酷派數據結構，種 複雜的實現，該節點。 正如你所看到的，它 是節點的結構 是，你有一個左 和一個右指針。 這就是它。 因此，而不是僅僅 具有一個X或先前。 你有一個左或右，然後 有種你可以將它們鏈接在一起 然而，你選擇。 OK，我們實際上會 只需要幾分鐘的時間。 所以我們要回去這裡。 正如我以前說過， 我種解釋 後面我們如何邏輯 通過這樣做搜索。 我們要嘗試 pseudocoding了這一點，看看 樣的，如果我們可以應用 二進制搜索的同樣的邏輯 到不同類型的數據結構。 如果你們想採取像情侶 分鐘，只是想想這一點。 確定。 好吧，我要去 其實只是給你the--沒有， 我們將談論的偽代碼第一位。 因此，沒有人想 給刺傷了什麼 你想要做的時候第一件事情 你開始搜索？ 如果我們正在尋找 66的價值，什麼是 我們想要做的，如果第一件事 我們要的二進制搜索這棵樹？ 聽眾：你想要看的權利 看看左邊，看到[聽不清] 更大的數字。 ANDI彭：是的，沒錯。 所以，你要看看你的根。 有很多方法可以調用 它，你的父節點的人說。 我想說的根因 這就像樹的根。 你要看看 你的根節點，而你 要看到的是66更大 大於或小於55。 而如果它是大於，很好，這是 大於，在這裡我們想看看嗎？ 我們在哪裡現在要進行搜索，對不對？ 我們要搜索 這種樹的右半邊。 因此，我們有，方便，一 指針指向右側。 而這樣的話，我們可以設置 我們新的根是77。 我們可以去到哪裡 指針指向。 嗯，哦，在這裡我們開始 77，我們可以只 遞歸一次又一次做到這一點。 通過這種方式，你有種 的有一個功能。 你有搜索你的一種方式 只需重複一遍又一遍又一遍， 這取決於你想看看 直到你最終得到的值 您正在搜索。 有意義嗎？ 我要告訴你的實際 代碼，這是一個很大的代碼。 沒有必要驚慌。 我們將討論通過它。 當然沒有。 這只是偽代碼。 好了，這僅僅是偽代碼， 這是一個有點複雜， 但它完全罰款。 下面大家一起在這裡嗎？ 如果根是空的，回報 假的，因為這意味著 你甚至不用任何那裡。 如果根n是價值，因此，如果 恰好是你看一， 那麼你要返回true 因為你知道你發現了它。 但如果該值小於 小於n的根，你 要搜索左 子或左葉， 無論你怎麼稱呼它。 並且如果該值大於根， 你要尋找合適的樹， 然後只需運行功能 通過搜索一次。 如果根是空的，這是 意味著你已經走到了盡頭？ 這意味著你沒有 更多更多的葉子進行搜索， 那麼你知道，哦，我 猜想這是不是在這裡 因為此前我已經通過看 整個事情，它是不是在這裡， 它只是可能不會在這裡。 這是否有意義給大家？ 所以，它就像二進制搜索保存 鍊錶的功能。 涼，所以第二類型 數據結構，你們的 可以嘗試實現你的PSET， 你只需要選擇一種方法。 但是，也許是一個替代方法 哈希表就是我們所說的一個線索。 所有的一個線索是一個 樹的特定類型 有一個去其他值的值。 所以具有代替二進制 樹在這個意義上，只有一個 東西可以指向兩個，可以有 一件事情點很多很多的東西。 本質上，陣列 其中你店內 指針指向其他陣列。 那麼我們如何在節點 將定義一個線索 就是我們希望有一個 布爾，C字，對吧？ 所以該節點是布爾 像真的還是假的， 首先在頭 該數組，這句話嗎？ 其次，你想擁有指針 到任何人，其餘都是。 一個有點複雜，有點抽象，但 我將解釋那是什麼一切手段。 因此，這裡，在頂部，如果 有一個數組已經聲明， 在這裡你有一個布爾節點 存儲在前面的值 告訴你的是這句話嗎？ 這難道不是一個字？ 然後你有 陣列的其餘部分的 實際存儲所有的 什麼可能是可能。 因此，舉例來說，像 頂部有 的第一件事，說真的還是 假，是或否，這是一個詞。 然後你有0到26 您可以存儲的字母。 如果我想在這裡搜索 對於蝙蝠，我去頂 我找B.我發現中的B我 數組，所以我知道，行，為B字？ B是不發一語，所以這樣 我必須繼續尋找。 我從B和我期待的 指針乙組分朝 我看到另一個信息陣列， 相同的結構，我們有過的。 而這裡 - 哦，下 信[聽不清]是A. 因此，我們期待在該數組。 我們發現第八值， 然後我們來看看，看看，哦， 哎，就是一個字，是B-A字？ 它不是一個字。 我們一定要繼續尋找。 所以接下來我們來看看哪裡 的一個點的指針， 並且它指向的另一種方式 我們有更多的價值存儲。 而最終，我們得到 B-A-T，它是一個字。 這樣一來，下一次 你看，你會 有，是的，辦理入住手續， 此布爾函數是真實的。 所以在這個意義上，我們是一種 具有數組的樹。 所以，你可以種向下搜索。 而不是散列函數，並且 通過鍊錶分配值， 你可以實現一個 特里，搜索downwords。 真的，真的複雜的東西。 不容易想到，因為我很喜歡 隨地吐痰，這麼多的數據結構進行 你，但確實有種大家 理解這個邏輯的作品？ OK，涼。 因此，B-A-T，然後 你要搜索。 你要去的下一次 看，哦，嘿嘿，這是真的， 因此，我知道這一定是一個字。 同樣的事情了動物園。 因此，這裡的事情，現在，如果我們 想尋找動物園，現在， 目前動物園是不是 字我們的字典 因為，正如你們所看到的， 我們有一個布爾首位 返回true是在放大的末端。 我們有Z-O-O-M。 所以在這裡，我們實際上並不具備 這個詞，動物園，在我們的字典 因為此複選框未選中。 因此，計算機不 知道動物園是一個字 因為我們已經一路 保存它，只有變焦這裡 實際上有一個布爾值 一個已經變成事實。 因此，如果我們要插入的 一句話，動物園，為我們的字典， 我們怎麼會去這樣做？ 什麼是我們必須做的，以確保我們的 計算機知道的是Z-O-O是一個字 而不是第一個字為Z-O-O-M？ 聽眾：[聽不清] ANDI鵬：沒錯，我們 要確保這 這裡，該布爾值是 檢查過，這是真的。 Z-O-O，然後我們要去檢查， 因此，我們確切地知道，哎，動物園是一個單詞。 我要告訴 電腦，這是一個詞，以便 計算機檢查時， 它知道動物園是一個詞。 因為記住所有這些數據 結構，這很容易讓我們 說，哦，蝙蝠的一個詞。 動物園的一個詞。 Zoom的一個詞。 但是當你構建它， 電腦不知道。 所以，你必須準確地告訴它 在什麼時候，這是一個詞？ 在什麼時候是它不是一個字？ 而在什麼時候做我 需要搜索事情， 和在什麼時候，我需要去下一個？ 每個人都清楚的是什麼？ 酷。 因此然後是 的問題，我們怎麼會 去插入的東西 這實際上不是嗎？ 所以，我們只能說，我們要插入 這個詞，洗澡，到我們的線索。 正如你們可以看到像目前 所有我們現在已經是B-A-T， 和這個新的數據結構 曾有一品脫的 指著空，因為我們假設 即，哦，還有後B-A-T沒有的話， 為什麼我們需要保持 該T之後有東西 但問題出現了，如果我們做的你 想有來後一個字 T的。 如果你有浴缸，你 會想要一個H的權利。 所以，我們要做到這一點的方法是 我們要創建一個單獨的節點。 我們沒有配發任何金額 內存為這個新陣， 而且我們要重新分配指針。 我們將分配 H，首先，此空， 我們要擺脫。 我們將有 轟點向下。 如果我們看到一個H，我們希望它 去別的地方。 在這裡，我們可以勾選肯定。 如果我們的T後擊中H，OH， 那麼我們知道這是一個詞。 布爾將會返回true。 每個人都清楚如何發生的？ 確定。 所以基本上，所有的 這些數據結構 我們已經討論了今天，我已經 走了過來他們真的，真的快 而不是在得多 細節，這就是確定。 一旦你開始搞亂 有了它，你會 保持在那裡的軌道 所有的指針， 什麼在事情你 數據結構，等等。 他們將是非常有用的， 它是由你 傢伙完全弄清楚如何 你想實現的東西。 因此pset4，5--哦，那是錯誤的。 Pset5是拼寫錯誤。 正如我之前說的，你要去，一旦 再次，從我們這裡下載源代碼。 還有的將是三個主要的 事情你會被下載。 你會下載字典， KERS和文本。 所有這些東西都是有 無論是詞詞典 我們希望你檢查 或信息測試 我們希望你能拼寫檢查。 這樣一來，字典 我們給你準備 給你，我們要實際的話 你以某種方式存儲的方式，是 比的陣列更有效。 然後將文本是 會是什麼我們是 要求您進行拼寫檢查，以確保 所有的話有真實的話。 對這樣一來，三大板塊 計劃，我們會給你 被稱為dictionary.c， dictionary.h和speller.c。 因此所有dictionary.c確實是 你在要求執行。 它加載的話。 它拼寫檢查他們，並確保 一切都正確插入。 diction.h只是一個庫文件 聲明所有的這些功能。 而speller.c，我們打算給你。 你不需要修改任何它。 所有speller.c確實是拿去， 它裝載，檢查它的速度， 檢驗了怎麼樣的基準 很快你能夠做到的事情。 這是一個拼寫檢查。 只要不惹它，但要 確保你明白它在做什麼。 我們用一個函數調用的getrusage的 測試你的法術性能 檢查器。 它所做的基本測試 一切都在你的字典的時間， 所以一定要了解它。 注意不要亂用，或 否則事情將無法正常運行。 而大宗這一挑戰的是 你們真的修改dictionary.c。 我們打算給你 14萬字的字典中。 我們將會給你一個文本 文件中有這些話， 我們希望你能夠組織 成一個哈希表或字典樹 因為當我們問你拼 check--想像一下，如果你的法術 檢查像荷馬的奧德賽。 這就像這個巨大的，巨大的考驗。 如果每一個想像 一句話，你不得不看 通過140,000值的數組。 這將採取永遠 為您的機器上運行。 這就是為什麼我們要組織我們 數據轉換成更有效的數據結構 如哈希表或字典樹。 然後你們可以種 當您搜索的訪問 事情更容易，更快速。 所以要小心，以解決衝突。 你會得到一堆 開頭A的話 你會得到一堆話 開頭B.由你 男人要如何解決它。 或許還有更多 高效的散列函數 比僅僅是第一信 一些東西，所以這是給你 樣的人做任何你想要的。 也許你想添加 所有的來信。 也許你想喜歡做奇怪的事情 到賬戶的字母數， 等等。 截至你們要如何做。 如果你想要做一個哈希表，如果你 想嘗試一個線索，完全取決於你。 我會提前發出警告的時間的你 線索通常是有點困難 只是因為有很多 更多的指針來跟踪。 但是，完全取決於你們。 這是更有效 在大多數情況下。 你要真正能夠保持 跟踪你所有的指針的。 像做同樣的事情 我在這裡做什麼。 當你試圖插入 值到一個哈希表或刪除， 請確保你 真的跟踪 對這裡的一切是因為 這是因為，如果我真的很容易 試圖插入之類的詞，安迪。 遠的不說，這是一個 真正的字，詞，劉德華， 成的話一個巨大的列表。 如果我只是碰巧重新分配 指針錯誤，哎呀， 有去的全部 我的鏈接列表的其餘部分。 現在唯一的一句話讓我 已經是安迪，現在 所有的在該換言之 詞典已經丟失。 所以你要確保你 跟踪所有的指針的 否則，你會得到 巨大的問題，在你的代碼。 畫的東西出來仔細一步一步來。 這使得它更容易想到的。 最後，要能 測試你的程序的性能 在大板。 如果你們拿 看CS50現在， 我們有什麼所謂的大板。 它是最快的評分表 在所有的CS50的拼寫檢查倍 現在，我覺得像10上方 有時，我覺得其中八是工作人員。 我們真的希望你們擊敗我們。 我們所有的人都試圖實現 最快的代碼成為可能。 我們希望你們來嘗試挑戰 我們並實現比我們快 可以。 所以這是真的 第一次，我們是 要求你們做一個PSET的 你真的可以為所欲為方法 你想要的。 我總是說，這是更接近 以現實生活中的解決方案，對嗎？ 我說，嘿，我需要你這樣做。 建立一個程序，它為我。 做到這一點，但是你想要的。 我只知道，我要快。 這就是你的挑戰，在這個星期。 你這傢伙，我們要 給你一個任務。 我們將會給你一個挑戰。 然後就看你們 完全只是弄清楚 什麼是最快捷和最 有效的方式來實現這一點。 是嗎？ 聽眾：我們是否允許，如果 要研究更快的方法 做哈希表在網上，我們可以做 這一點，引用別人的代碼？ ANDI彭：是的，完全罰款。 所以，如果你們看 規範，有一條線 在規範中，說你們 完全自由地研究哈希 上有哪些功能 的更快的散列函數 通過為運行的東西 只要你引用的代碼。 因此，一些人已經 想通了快速的方法 中做快速拼寫檢查器， 方式存儲的信息。 完全取決於你的傢伙，如果你 想只取了吧？ 請確保您引用。 這裡的挑戰真的 我們正在試圖測試 是確保你知道 你倒過來指針。 至於你實現 實際的散列函數 而未來與像 數學要做到這一點， 你們可以研究什麼 方法在線你們想要的。 是嗎？ 聽眾：我們能不能只舉 使用[聽不清]？ ANDI彭：是的。 你可以在你的評論， 你可以舉出像，哦， 從亞達採取亞達， 亞達，哈希函數。 任何人有任何問題嗎？ 實際上，我們輕輕鬆鬆 通過板塊今日。 我將在這裡為 回答問題也是如此。 此外，正如我所說，辦公室 今晚和明天小時。 該規範在本週其實是 超級簡單和超短期閱讀。 我建議考慮看看，剛 閱讀它的全部內容。 而Zamyla實際上引導您 通過每個功能 你需要實現，所以它的 非常，非常清楚如何做的一切。 只是為了確保你 跟踪指針。 這是一個非常具有挑戰性的pset。 這不是挑戰，因為喜歡， 哦，其概念是這麼多 困難，或者你要學會 這麼多新的語法方式 你做的最後PSET。 這PSET是困難的，因為 有這麼多的三分球， 然後這是非常，非常容易，一旦 你在你的代碼中的錯誤不能 找到該錯誤是。 而如此完整和你絕對信心 傢伙能夠擊敗我們的[聽不清] 拼寫。 其實，我沒有任何書面礦 然而，但我要寫我的。 你寫的，而因此 你，我會寫我的。 我會盡量讓 我的比你快。 我們將看到誰擁有最快的國家之一。 ，是的，我會看到所有的 你們在這裡在星期二。 我將運行就像一個PSET車間一種。 所有部分的這 本週是PSET車間， 所以你們有很多機會 求助，辦公時間一如既往， 我真的很期待 看完所有的人“的代碼。 我測驗在這裡，如果你 你們要來得到這些。 這就是全部。