[音樂播放] 揚聲器1：好吧。 每個人都歡迎回款。 我希望大家都成功 從你的測驗回收 從上週。 我知道這是一個有點瘋狂的時候。 正如我之前說，如果你是 的標準偏差之內， 真的不擔心，尤其是 一個不太舒適的部分。 這是什麼地方，你應該的。 如果你做得很好，那麼真棒。 榮譽給你。 如果你覺得你需要 多一點點的幫助，請 隨時到達 出任何的轉錄因子。 我們都在這裡幫忙。 這就是為什麼我們教。 這就是為什麼我在這裡每週一為你 球員和在辦公時間星期四休息。 因此，請隨時讓我知道 如果你擔心什麼 或者，如果有對任何競猜 你真的想解決的問題。 因此，對於今天的議程 所有關於數據結構。 其中一些只是要公正 為了讓你熟悉這些。 你可能永遠不會實現 他們在這個類中。 有些人你會的， 像你的拼寫PSET。 你有你的選擇 哈希表和嘗試的。 所以我們一定會去在那些。 這將是肯定更有種 高電平部分的今天，雖然 因為有很多人，如果 我們進入的實施細則 所有這些，我們不會 甚至可以通過鏈接列表 也許哈希表的一點點。 所以多多包涵。 我們不打算做 盡可能多的編碼這個時候。 如果您有任何關於它的問題 或者你想看到它實現的 還是自己試試看， 我絕對推薦 要study.cs50.net，這 具有所有的這些例子。 這將有我的學習認證 用音符，我們 傾向於使用以及一些編程 練習，特別是對事 如鍊錶和二進制 樹木堆棧和線索。 這麼少的較高水平，這 也許是很好的你們。 所以這樣，我們就開始吧。 而且，yes--測驗。 我想絕大多數人誰是 我的部分有你的測驗， 但任何人進來，或某種原因，你 不這樣做，他們就在這裡，在前面。 所以鍊錶。 我知道這種雲 您的測驗前備份。 這是一周前 我們了解了這一點。 但是，在這種情況下，我們只 走多一點點深入。 那麼，為什麼我們會選擇一個 鍊錶一個數組？ 有什麼區別呢？ 是嗎？ 聽眾：您還可以擴大一個鏈接 列出與數組的固定大小。 揚聲器1：沒錯。 數組有固定的大小，而一 鍊錶具有可變的大小。 因此，如果我們不知道如何 我們多麼希望存儲， 鍊錶給我們帶來了很大的 辦法做到這一點，因為我們可以只 添加另一個節點上，並添加上 另一個節點，並添加另一個節點上。 但可能是一個權衡？ 有誰還記得權衡 數組和鍊錶之間？ Mmhmm​​？ 聽眾：你必須 經過一路 通過該鏈接的表 發現列表中的一個元素。 在一個陣列，可以 只要找到一個元素。 揚聲器1：沒錯。 因此，與arrays-- 聽眾：[聽不清]。 揚聲器1：數組，我們有 什麼叫做隨機訪問。 也就是說，如果我們要的是 有史以來第五點名單 或第五點是我們 數組，我們只要抓住它。 如果它是一個鍊錶，我們有 遍歷，對不對？ 所以，在訪問一個元素 一個陣列是恆定時間， 而用一個鍊錶的那樣 最有可能是線性的時間，因為也許 我們的元件是一路在末端。 我們有過的一切進行搜索。 因此，所有這些數據 我們要去結構 要在花多一點的時間， 哪些長處和底片。 什麼時候我們可能要 使用一個比其他？ 這就是種的 更大的東西拿走。 因此，我們必須在這裡 定義一個節點。 這就像在一個元素 我們的鍊錶，對不對？ 所以，我們都很熟悉 我們的typedef結構， 我們走過去，在回顧過去的時候。 它基本上只是創造 我們可以使用另一種數據類型。 在這種情況下，它的一些節點 這將在一定整數。 然後什麼是第二部分在這裡？ 任何人嗎？ 聽眾：[聽不清]。 揚聲器1：是啊。 這是一個指向下一個節點。 因此，這實際上應該是在這裡。 這類型的指針 節點到下一件事情。 而這正是他們 包括我們的節點。 涼爽。 好吧，所以用搜索，因為我們 只是說前手，如果你 要通過搜索， 你必須真正迭代 通過您的鏈接列表。 因此，如果我們要尋找的數量 9，我們將開始在我們的頭上 並指向我們開始 我們的鍊錶，對不對？ 我們說好，這是否 節點包含數字9？ 不是嗎？ 好吧，去下一個。 遵循它。 它包含數字9？ 號 按照下一個。 因此，我們必須以實際循環 通過我們的鏈接列表。 我們不能只是去直接到9。 如果你們真的想 看到一些偽代碼在那裡。 在這裡，我們有一些搜索功能 這需要in--需要做些什麼呢？ 你有什麼感想？ 那麼容易的。 這是什麼？ 聽眾：[聽不清]。 揚聲器1：我們正在尋找的數量。 對不對？ 什麼會這樣對應？ 這是一個指針？ 聽眾：一個節點。 揚聲器1：節點列表 我們正在尋找的，對不對？ 因此，我們有一些節點的指針位置。 這是一個點，那將 通過我們的名單實際上迭代。 我們設置它等於列表 因為這只是 設置它等於 開始我們的鍊錶。 雖然它不為NULL，而 我們還有東西在我們的列表中， 檢查，看看是否有節點 我們正在尋找的數字。 返回true。 否則，更新它，對不對？ 如果為NULL，我們退出我們 while循環並返回false 因為這意味著我們還沒有找到它。 每個人都得到如何工作的？ 行。 因此，與插入，你 有三種不同的方式。 您可以預先準備，可以追加 你可以插入到什。 在這種情況下，我們 打算做一個預先準備。 有誰知道這些 3案件可能會有所不同？ 所以在前面加上意味著你把 它在列表的前面。 因此，這將意味著，不管 你的節點，無論 價值是什麼，你要 把它放在這裡在前面，好不好？ 這將成為第一 元素在列表中。 如果您添加它，它是怎麼回事 去你的列表的後面。 並插入到什意味著你 打算把實際進入的地方 它讓你的鏈接列表進行排序。 同樣，你如何使用 這些，當你使用 他們會根據你的情況而有所不同。 如果不需要 進行排序，在前面加上趨於 是大多數人 使用，因為你不知道 要經過整個列表 尋找到底添加它，對不對？ 你可以把它貼對世權。 因此，我們將通過一個 插入1現在。 這麼一件事，我要去 強烈建議在此PSET 是畫出來的東西，一如既往。 這是你更新是非常重要的 以正確的順序你的指針 因為如果你更新它們 稍微亂序， 你要結束了 失去你的列表的一部分。 因此，例如，在這種情況下，我們 告訴頭只點1。 如果我們只是做了 不保存這個1， 我們不知道是什麼 1應指向現在 因為我們已經失去了什麼 該負責人指出。 所以，有一點要記住 當你做了預先準備 是拯救什麼 頭分排名第一， 然後重新分配它，然後更新 你的新節點應該指向。 在這種情況下，這是為了做到這一點的方法之一。 因此，如果我們做了這種方式 在這裡我們只是重新分配頭， 我們失去了我們的基本 整個列表，對不對？ 做到這一點的方法之一是有1個點 接下來，再有頭點1。 或者，你可以種不喜歡的 臨時存儲，這是我所津津樂道。 但是，重新分配你的 以正確的順序指針 將是非常，非常 重要的是這個PSET。 否則，你將有一個哈希 表或一個嘗試，這只是將要 的話只有部分是你 想要再you're-- mmhmm？ 聽眾：什麼是臨時 存儲的東西你在說什麼？ 揚聲器1：臨時存儲。 所以基本上另一 這樣你可以這樣做 是存放東西的腦袋，像 存放臨時變量。 其分配到1 然後更新1點 以什麼頭用來指向。 這種方式顯然是 因為你更優雅 不需要一個臨時值，但 只是提供了另一種方式來做到這一點。 而我們實際上做有 一些代碼這一點。 所以對於鍊錶，我們 實際上有一些代碼。 所以在此處插入，這是預先考慮。 所以這個進入它的頭。 所以第一件事情，你需要 當然，創造你的新節點， 並檢查是否為NULL。 總是好的。 然後你需要指定的值。 當你創建一個新的節點，你 不知道它的指向下一個， 所以你想要初始化為NULL。 如果它最終指向事 否則，它就會被重新分配，它的罰款。 如果這是第一件事情 在列表中，則需要 指向null，因為 這是該列表的末尾。 所以後來插入的話，我們在這裡看到我們 被分配了節點的下一個值 是什麼頭， 這就是我們不得不在這裡。 這就是我們只是做了。 然後我們分配頭點 我們的新節點，因為要記住， 新是一些指針到一個節點， 而這正是頭是什麼。 這就是為什麼我們 有這個箭頭訪問。 很酷吧？ Mmhmm​​？ 聽眾：我們得 初始化新的下一位第一為NULL， 或者我們只是把它初始化為頭？ 揚聲器1：新下一個 需要為NULL啟動 因為你不知道 那裡將是。 此外，這是怎麼樣的 就像一個範例。 你將其設置為NULL只是為了 確保你所有的基地都覆蓋 你這樣做，任何重新分配前 你總是保證它會 被指向的特定值 與像一個垃圾值。 因為，是的，我們分配 新的自動接下來， 但它更多的只是像 好的做法進行初始化 以這種方式，並重新分配。 好了，現在雙鍊錶。 我們怎麼想的？ 有什麼不同 雙向鍊錶？ 所以在我們的鍊錶，我們可以 只朝一個方向，對不對？ 我們只有下一個。 我們只能往前走。 用一個雙向鍊錶， 我們還可以向後移動。 因此，我們不僅 我們要存儲號碼， 我們有它指向下一個 當我們剛剛從。 所以這允許 一些更好的遍歷。 因此，雙向鍊錶節點， 非常相似的，對不對？ 唯一不同的是，現在我們 有下一個和前一個。 這是唯一的區別。 所以，如果我們要在前面或append--我們 沒有任何代碼此向上這裡 - 但如果你要嘗試 插入，最重要的事情 就是你需要 確保你分配 無論你以前和你 下一個指針正常。 因此，在這種情況下，你會 不僅初始化旁邊， 在初始化以前。 如果我們在列表的頭部，我們 不但使頭部等於新， 但我們的新的前應 點了頭，對吧？ 這是唯一的區別。 如果你想有更多的實踐 這些用鍊錶，用插入， 與刪除，插入帶 成什錦列表， 請查看study.cs50.net。 有一群偉大的演習。 我極力推薦他們。 我希望我們有時間去通過他們 但有很多數據結構 打通。 好了，哈希表。 這可能是最 您PSET有用位 在這裡，因為你將要 執行其中的一個或一試。 我真的很喜歡哈希表。 他們很酷。 所以基本上什麼 發生的情況是一個哈希表 當我們真正需要迅速 插入，刪除和查找。 這些都是東西，我們 在哈希表中優先考慮。 他們可以得到相當大的， 但我們會嘗試用看， 有些事情是要大得多。 但基本上，所有的散列 表是散列函數 告訴你哪個桶把每 您的數據，每一個在你的元素。 一個簡單的方法去思考一個哈希表 是它的事情只是水桶， 對不對？ 所以，當你被排序的東西 就像他們的名字的第一個字母， 這有點像一個哈希表。 所以，如果我是組你們是 到誰的名字開始組 用A看過來，或者誰的生日 在一月，二月，三月， 什麼，那就是有效 創建哈希表。 它只是創造了水桶 你的元素進行排序成 這樣您就可以找到他們更容易。 所以這樣一來，當我需要 找一個你， 我沒有搜索 通過您的每一個名字。 我可以想，哦，我知道， 丹妮的生日是in-- 聽眾：--April。 揚聲器1：四月。 所以我看在我四月份 鬥，與任何運氣， 她會在那裡唯一的一個， 我的時間是在這個意義上不變， 而如果我要看看 通過一大堆的人， 這將花費更長的時間。 因此，哈希表是真的只是水桶。 簡單的方法，他們的看法。 因此，關於一個很重要的事情 哈希表是一個散列函數。 所以事情我剛才講的，像 您的名字的第一個字母 或者你的生日月， 這些想法， 真關聯到哈希函數。 這是確定的只是一個方式，也 鬥你是元素進入，OK？ 因此，對於這pset中，你可以看一下 幾乎任何你想要的哈希函數。 並不一定是你自己。 有一些很酷的的人了 那裡，做各種瘋狂的數學。 如果你想使你的 拼寫檢查超快， 我肯定會 看看其中的一個。 但也有在 簡單的，如計算 的話，總和一樣 每個字母的數。 計算總和。 用於確定桶。 他們也有難辦的 就像所有的A的位置， 所有的B的在這裡。 這些中的任何一個。 基本上，它只是告訴你哪個 數組索引你的元素應該進入。 剛剛決定bucket-- 這是所有的哈希函數是。 所以在這裡，我們有一個例子是 字符串的只是第一信 我只是在談論。 所以，你有一些散，這僅僅是 您的字符串減去A的第一個字母， 這會給你一些 介於0和25號。 和你想要做的是什麼 確保這代表 您的散列的大小table-- 多少個水桶也有。 許多這類 散列函數，它們是 將要返回的值可能 要遠遠高於桶的數量 那你確實有 在哈希表 所以你需要 肯定和那些國防部。 否則，它會說， 哦，應該是在5000桶 但你只有30 水桶中的哈希表。 當然，我們都知道這是 會導致一些瘋狂的錯誤。 所以一定要確保由於MOD 您的哈希表的大小。 涼爽。 所以碰撞。 是每個人都好這麼遠嗎？ Mmhmm​​？ 聽眾：為什麼會 返回這樣一個龐大的價值呢？ 揚聲器1：根據不同的算法 您的哈希函數使用。 有些人會做 瘋狂繁殖。 它的所有有關獲取 一個均勻分佈， 所以他們做一些真正 有時是瘋狂的事情。 就這樣。 還要別的嗎？ 行。 所以碰撞。 基本上，正如我剛才所說， 在最好的情況下， 任何鬥我看看是 將有一件事， 所以我沒有看全，對不對？ 我不是知道它的存在，或者它 不，這是我們真正想要的。 但是，如果我們有數万 數據點和小於號 桶，我們將有 碰撞中，最終的東西 即將要結束了 鬥已經有一個元素。 所以，問題是，什麼樣 我們在這種情況下怎麼辦？ 我們該怎麼辦？ 我們已經有了的東西呢？ 難道我們只是把它扔出去？ 號 我們必須保持他們兩個。 這樣的方式，我們 通常做的是什麼嗎？ 是什麼數據結構 我們剛才講？ 聽眾：鍊錶。 揚聲器1：鍊錶。 所以，現在的，而不是每個這些 水桶只是有一個元素， 它會包含一個鏈接列表 這被散列到它的元素。 好了，大家都種得出來的？ 因為我們不能有一個數組 因為我們不知道有多少東西 將要在那裡。 鍊錶可以讓我們 剛剛確切的數字， 被散列成水桶，對不對？ 所以線性探測是 基本上這idea-- 這是應對碰撞的一種方式。 你可以做的是，如果在這 情況下，漿果被散列到1 我們已經有了 那裡的東西，你只要 繼續下去，直到 你找到一個空槽。 這是一種方式來處理它。 另一種方式來處理 它是我們剛才 called--鏈接 列表被稱為鏈接。 所以這個想法，如果工作 您的哈希表，你認為 比大得多 您的數據集，或者如果你 想嘗試和減少鏈接 直到它的絕對必要。 因此，有一點是線性的 探測手段明顯 您的散列函數 是不是很實用 因為你要使用到結束 您的散列函數，得到一個點， 你的線陣探頭向下 一些地方可用。 但現在，當然，任何事情 別人說結束了那裡， 你將不得不 搜索甚至進一步下跌。 而且還有很多更 搜索的費用 進入輸入一個元素 在現在的哈希表，對不對？ 而現在，當你去嘗試和發現 漿果再次，你要湊吧， 而且它會說， 哦，在鬥1看， 而且它不會是 在鬥1，所以你 將不得不穿越 通過對這些休息。 所以，它有時是有用的， 但在大多數情況下， 我們要指出， 鏈接是你想做的事。 所以，我們談到了這點。 我得到了我自己一點點前進。 但鏈基本上是 在哈希表中的每一桶 僅僅是一個鍊錶。 這樣的另一種方式，或更多的技術 這樣，想到一個哈希表 是，它只是一個數組 鍊錶，哪 你寫你的字典時， 而你試圖加載它， 想到它是一個 鍊錶的數組 將使它更容易 為您初始化。 聽眾：所以哈希表 具有預定的大小， 像水桶的[聽不清]？ 揚聲器1：沒錯。 所以它有一組數 你determine--桶 這你們應該 隨便玩。 它可以是很酷 看看會發生什麼 當你改變你的桶數。 但是，是的，它有一個 桶的設置數量。 是什麼讓你滿足的 因為你需要很多元素 這是單獨的鏈接，你 已在每個桶鍊錶。 這意味著你的哈希表 會完全大小 你需要它，對不對？ 這就是鍊錶的整點。 涼爽。 所以每個人都需要幫助嗎？ 行。 啊。 剛剛發生了什麼？ 現在真的。 猜猜誰是殺害我。 OK，我們要進入 嘗試，這是一個有點瘋狂。 我喜歡的哈希表。 我覺得他們真的很酷。 嘗試涼爽了。 因此，沒有人記得一試的是？ 你應該已經走了過來 它簡要地講？ 你還記得那種它是如何工作的？ 聽眾：我只是點頭 我們也去了吧。 揚聲器1：我們過目一下。 OK，我們真的要去 在它現在是我們在說什麼。 聽眾：這是一個檢索樹。 揚聲器1：是啊。 這是一個檢索樹。 真棒。 所以，有一點這裡要注意的是，我們 正在尋找單個字符 在這裡，對不對？ 所以在我們的哈希函數，我們 所尋找的單詞作為一個整體， 現在我們正在尋找更多的 在人物了吧？ 因此，我們有麥克斯韋在這裡和孟德爾。 所以基本上一個try--的方式來思考 這個是每個層次在這裡 是字母數組。 因此，這是你的根結在這裡，對不對？ 這具有的所有字符 字母的每一個字的開始。 和你想要做的是什麼 說好，我們有一些M個字。 我們要尋找麥克斯韋，所以 我們去的M.和M點整 另外一個數組，其中每 總之，只要存在 是一個具有一個字 作為第二個字母， 只要有一個字 有B作為第二個字母， 它將有一個指針 去一些旁邊的數組。 有可能不是一個 詞MP的東西， 所以在此P位置 數組，它只是為NULL。 它會說，OK，沒有字 即有m個後跟一個P，好不好？ 因此，如果我們仔細想想，每個 這些較小的事情之一 實際上是其中之一 到Z大陣列從A 那麼，什麼可能的事情之一 這是怎樣的一個嘗試的缺點呢？ 聽眾：大量的內存。 揚聲器1：這是一噸的記憶，不是嗎？ 每一個這些塊在這裡 代表26位，26個元素的數組。 因此，試圖獲得令人難以置信的太空沉重。 但他們都非常快。 如此令人難以置信的速度快，但 真是浪費空間。 那種有圖 哪一個你想要的。 這是真的很酷您PSET， 但他們佔用了大量的內存， 所以你權衡。 是嗎？ 聽眾：有沒有可能 建立一個嘗試，然後 一旦你把所有的 你need--在它的數據 我不知道這是否會是有意義的。 我擺脫所有 NULL字符，但隨後 你就不能夠索引them-- 揚聲器1：您仍然需要他們。 聽眾： - 每次以相同的方式。 揚聲器1：是啊。 您需要NULL字符來讓 你知道，如果有沒有一個字出現。 奔你有什麼，你想要什麼？ 行。 好了，所以我們要 去多一點點 進入技術細節的背後 一試，並通過一個實例運行。 好了，這是同樣的事情。 而在一個鍊錶，我們的主要 那種of--什麼是我想要的字？ - 像積木是一個節點。 在一個嘗試，我們也有一個節點， 但它的定義不同。 因此，我們有一些布爾值， 代表實際上無論是詞 存在於這個位置，然後 我們有一些陣這裡 - 或者更確切地說， 這是一個指向 陣列的27個字符。 這是因為，在這種情況下，這 27--我相信在座的各位都是這樣，等待， 有字母表中的26個字母。 為什麼我們有27？ 這樣根據不同的 要實現這種方式， 這是從一個pset中那 允許撇號。 所以這就是為什麼額外的之一。 您還可以有一些 情況下，空終止 被包含的所述一個 即它允許為字符， 這就是他們如何檢查 看它是否是該字的結束。 如果您有興趣，請查看 凱文的視頻study.cs50， 以及維基百科 一些很好的資源在那裡。 但是，我們要通過正中下懷 您可能如何工作，通過一試 如果你正在考慮之一。 因此，我們有一個超級簡單的在這裡， 有句話“蝙蝠”和“縮放”在其中。 正如我們看到的在這裡， 在這裡這個小空間 代表了我們的布爾值， 說，是的，這是一個字。 然後這有我們 字符數組，對不對？ 所以，我們要通過 發現在這個嘗試“蝙蝠”。 所以，從高層開始，對不對？ 我們知道，B對應 第二索引，所述第二元件 在這個陣列中，因為a和b。 所以大約第二個。 它說，OK，冷靜，按照成 下一個陣列，因為如果我們記得， 這並不是說所有這些 實際上包含元件。 這些陣列中的每一個 包含一個指針，對不對？ 這是做一個重要的區別。 我知道這是要be--嘗試的 真的很難得上是第一次， 所以，即使是這樣的 第二次或第三次 而且它仍然是一種 看似很難的， 我保證，如果你去觀看 短期再度明天 這可能會使得很多更有意義。 這需要大量的消化。 我有時仍然很 象，等等，什麼是一試？ 我該如何使用呢？ 所以我們B在這種情況下， 這是我們的第二個索引。 如果我們有，比方說，C或 d或任何其他字母， 我們需要映射回索引 我們的數組的對應。 因此，我們將採取類似rchar，我們只是 減去掀起了將其映射到0〜25。 大家好，我們怎麼樣 地圖我們的角色？ 行。 所以我們去的第二個和我們 看，是的，它不是為NULL。 我們可以繼續在下一個數組。 所以我們去到這一個陣列在這裡。 和我們說，好了，現在我們 需要看到，如果是在這裡。 為空或做它 其實往前走？ 所以實際上移動 轉發此數組中。 我們說好，t是我們的最後一個字母。 所以我們去到T的索引。 然後我們繼續前進 因為有另一個。 而這一次，基本上說，是的， 它說，有一句話這裡 - 如果你遵循這一點， 路徑，你已經到了 在一個字，這是我們所知道的是“蝙蝠”。 是嗎？ 聽眾：是不是標準有 為索引0，然後有一個排序的1 或有在結束了嗎？ 揚聲器1：第 因此，如果我們回頭看我們的 在這裡聲明，這是一個布爾值， 所以它在你的節點自身的元素。 所以它不是數組的一部分。 涼爽。 所以，當我們完成我們的話，我們很 在這個數組，我們想要做的 是做一個檢查，這是一個單詞。 在這種情況下，它會返回是。 所以，關於這一點，我們知道“動物園” - 我們知道，作為人類的“動物園”是一個詞， 對不對？ 但盡量會在這裡 說，不，它不是。 它會說，因為我們 沒有指定它作為這裡一個字。 儘管我們可以遍歷 通過對這個陣列中， 這種嘗試會說，不， 動物園是不是在你的字典 因為我們還沒有 指定它是這樣。 因此從另一個角度做that-- 哦，對不起，這一項。 所以在這種情況下，“動物園”是不 一個字，但它是在我們的嘗試。 但在這其中，說我們想讓它 介紹詞“洗澡”，會發生什麼 是我們遵循through-- B，A，T。 我們在這個數組中， 我們去尋找小時。 在這種情況下，當我們 看指針小時， 它指向NULL，好不好？ 所以，除非它是明確的 指著另一個數組， 你以為所有的指針 在這個陣列指向空。 所以在這種情況中，h是指向 為null，所以我們不能做任何事情， 因此它也將返回 假的，“洗澡”是不是在這裡。 所以，現在我們實際上 要經過 怎麼會，我們實際上說 該“動物園”是我們的嘗試。 我們如何將“動物園”到我們試試？ 所以在我們開始以相同的方式 我們的鍊錶，我們從根開始。 如有疑問，開始 這些東西的根源。 我們會說，OK，Z。 ž存在於此，並且它的作用。 所以你移動到 你的下一個陣列，好不好？ 然後就下單， 我們說好，不Ø存在嗎？ 它的作用。 這再次。 等我們下單，我們已經說過了， OK，“動物園”已經存在這裡。 所有我們需要做的是設置此相等 為true時，有一個詞出現。 如果你遵循了一切 到該點之前， 這是一個字，所以只 設置它等於這樣的。 是嗎？ 聽眾：所以後來做了 意思是“巴”是一個字也？ 揚聲器1：第 因此，在這種情況下，“巴”，我們會得到 在這裡，我們想說的是一個字， 並且它仍然是否定的。 行？ Mmhmm​​？ 聽眾：所以一旦你是一個 一句話，你說是，那麼它 將包含去米？ 揚聲器1：所以這個必須做 with--你加載此研究。 你說的“動物園”一詞。 當你去check-- 喜歡，說你想說的話， 在這個字典裡“動物園”的存在？ 你只會搜索“動物園” 然後檢查，看它是否是一個字。 你永遠不會動 通過對米，因為這不是 您要查找的內容。 因此，如果我們真的想 添加“洗澡”這個嘗試， 我們會做同樣的事情 當我們用做“動物園” 除了我們看到，當我們 嘗試，並得到為h，它不存在。 所以，你可以認為這是試圖 以添加新節點插入到一個鍊錶， 所以我們需要添加另一個 其中的一個陣列，像這樣。 然後我們要做的是，我們剛剛成立的H 這個數組指向這個元素。 然後什麼我們要在這裡做？ 添加它等於true 因為它是一個字。 涼爽。 我知道。 嘗試都不是最激動人心的。 相信我，我知道。 這麼一件事與嘗試實現， 我說，他們是非常有效的。 因此，我們已經看到了他們 佔用大量的空間。 種他們混淆。 那麼，為什麼我們曾經使用過這些？ 我們使用這些，因為他們是 令人難以置信的高效。 因此，如果你曾經期待 一個字，你是唯一的 由字的長度的限制。 所以，如果你正在尋找一個 字是一個長度為5的， 你永遠只能將不得不 讓最多5攀比，好不好？ 所以它使基本上是一個常數。 就像插入和查詢 基本上都是固定的時間。 所以，如果你能永遠得到 東西在一定的時間， 這是因為它得到不錯的。 你不能得到更好的比 固定時間為這些事情。 以便為所述一個 嘗試了巨大的加號。 但它是一個很大的空間。 樣的，所以你必須決定 什麼對你更重要。 而在今天的電腦， 空間的一個嘗試可能最多 也許不影響 你那麼多，但也許 你在處理事情 有遠遠更多的東西， 並嘗試恰恰是不合理的。 是嗎？ 聽眾：等等，讓你有26 在每一個人信嗎？ 揚聲器1：Mmhmm​​。 是啊，你有26。 你有一些是字標記，然後 你有26球在每個人。 他們正在point-- 聽眾：和每一個26， 難道他們各有26？ 揚聲器1：是的。 這就是為什麼，因為你可以 看，它擴展相當迅速。 行。 所以，我們要進入樹， 我覺得喜歡的是更簡單，大概會 是一個可愛的小死緩 從那裡嘗試。 所以希望你們中的大多數 以前看過一棵樹。 不喜歡漂亮 外面的人，這是我 不知道是否有人 去戶外最近。 我去採摘蘋果本週末， 哦，我的天哪，這是美麗的。 我不知道葉子 可以看看那個漂亮。 所以這只是一棵樹，對不對？ 這只是一些節點，並且它 指著一堆其他節點。 正如你在這裡看到，這是 樣一個反复出現的主題。 節點指向的節點是怎麼樣的 許多數據結構的本質。 這只是取決於我們如何 讓他們指向對方 以及我們如何遍歷 通過他們，我們如何 插入的東西，它決定 各自不同的特性。 所以只是一些術語， 我以前使用過。 所以，根本是不管是在最高層。 這就是我們總是開始。 你可以把它作為負責人也。 但對於樹木，我們往往 稱其為根部。 凡是在底部這裡 - 在非常，非常bottom-- 都認為葉。 因此，隨之而來的 整棵樹的事，對不對？ 葉子是在你的樹的邊緣。 然後我們也有幾個 術語談論有關節點 給對方。 因此，我們有父母， 孩子和兄弟姐妹。 所以在這種情況下，圖3是 父的5，6和7。 因此，家長無論是 一步以上不管你是 參照，所以才 就像一個家庭樹。 但願，這是所有有點 位比嘗試更直觀。 兄弟姐妹是任何有 同樣的父母，對不對？ 他們在這裡的同一水平。 然後，因為我是 他說，孩子們剛 無論是低於一步 有問題的節點，好不好？ 涼爽。 這樣的二進制樹。 任何人都可以猜測的一 二叉樹的特點是什麼？ 聽眾：最多兩片葉子。 揚聲器1：沒錯。 所以，最大的兩片葉子。 因此，在這個人之前，我們有這個 這有三個，但在一個二叉樹， 你有最多兩個 每個父母的孩子，對不對？ 還有一個 有趣的特性。 有誰知道？ 二叉樹。 所以二叉樹將擁有一切 在the--這個人是不是sorted-- 但在一個排序二叉樹， 一切都在正確的 大於父 一切都在左邊 小於母體。 並且已經交了白卷 問題之前，那麼好就知道了。 因此，我們定義這個方式， 再次，我們有另一個節點。 這看起來非常相似呢？ 雙 聽眾：鍊錶 揚聲器1：雙鍊錶，對不對？ 因此，如果我們替換此 有一個和下一個， 這將是一個雙向鍊錶。 但是，在這種情況下，我們實際上 有左，右，僅此而已。 否則，它是完全相同的。 我們還有元素 你要找的， 而你只需要兩個指針 要去什麼是下一個。 是啊，所以二叉搜索樹。 如果我們發現，一切都在 這裡是更大than-- 或立即的一切 這裡的權利 是大於一切 這裡是小於。 所以，如果我們通過搜索，它 看起來應該非常接近二分查找 在這裡，對不對？ 除外，而不是找 在一半的陣列， 我們只是在尋找在任左 側或右側的樹。 所以就有點簡單，我想。 所以，如果你的根是空的， 顯然這只是假的。 而如果它的存在，很明顯這是真的。 如果是小於，我們尋找的左側。 如果是大於， 我們搜查的權利。 它是完全一樣的二進制搜索， 只是一個不同的數據結構 我們使用。 代替數組， 它只是一個二叉樹。 OK，棧。 而且，看起來我們 可能有一點點時間。 如果我們這樣做，我很高興去 在任何這一次。 OK，所以棧。 有誰還記得stacks-- 一摞任何特點？ 好了，我們大多數人，我想， 在餐廳吃飯halls-- 就像我們可能不喜歡。 但很明顯，你可以把一疊 從字面上就如同一摞托盤 或堆疊的事情。 和什麼是重要的 要知道的是，它的 something--特徵 我們把它叫做by--是後進先出法。 有誰知道這代表著什麼？ Mmhmm​​？ 聽眾：後進先出。 揚聲器1：沒錯，後進先出。 所以，如果我們知道，如果我們的東西堆放 起來，最簡單的事情搶off-- 也許我們唯一可以搶 關閉如果我們的協議棧是大enough-- 是頂級元素。 所以，無論是放在 last--我們在這裡看到， 不管是推 在大多數recently--是 將成為第一 我們流行過，東西好不好？ 所以，我們在這裡是 另一個typedef結構。 這真的只是喜歡 在數據結構速成班， 所以有很多扔向你們。 我知道。 因此，另一種結構。 耶的結構。 在這種情況下，它的一些指針 到具有一定容量的陣列。 因此，這代表了我們的協議棧 在這裡，像我們實際的數組 這是我們持有的元素。 然後在這裡我們有一些大小。 而通常情況下，你要保持 曲目有多大的堆棧 因為它是怎麼回事，讓 你要做的就是，如果你知道的大小， 它可以讓你說的， 好吧，我是在能力？ 我可以添加些什麼？ 它也告訴你 在您的堆棧的頂部 那麼你知道你 其實可以起飛。 而這實際上是要 有一點更清楚這裡。 因此，對於推，一件事，如果你 是有史以來實施推， 我只是說，你的 棧的大小有限，對不對？ 我們的陣列有一些能力。 這是一個數組。 這是一個固定大小的，所以我們需要 確保我們不會把更多 到我們的數組要比我們 實際上有空間。 所以，當你創建一個推 功能，你做的是說好第一句話， 做我的空間我的籌碼？ 因為如果我不這樣做，對不起， 我不能存儲你的元素。 如果我這樣做，那麼你想存儲 它在堆棧的頂部，對不對？ 這就是為什麼我們有 跟踪我們的規模。 如果我們不保持我們這樣規模的軌道， 我們不知道放在哪裡。 我們不知道有多少東西 在我們的數組了。 就像明明有方法 也許你可以做到這一點。 你可以初始化所有設置為NULL 然後檢查最新NULL， 但一個更容易的事情僅僅是 說，OK，跟踪大小。 就像我知道我有四個要素 在我的數組，所以接下來的事情 我們換上，我們 將存儲在索引4。 然後，當然，這意味著 你已經成功地推的東西 到你的籌碼，你 要增加大小 讓你知道你是如此 那你可以把更多的東西。 所以，如果我們試圖彈出 事關棧， 可能是什麼的第一件事 我們要檢查？ 你想採取 事關你的籌碼。 你肯定有 在堆棧中的東西嗎？ 號 所以，什麼才是我們要檢查？ 聽眾：[聽不清]。 揚聲器1：檢查的大小？ 尺寸。 因此，我們要檢查，如果看 我們的規模是大於0，OK？ 如果是，那麼我們需要減小 我們的規模由0和返回。 為什麼呢？ 在第一個我們 推，我們推 上的尺寸，然後更新的大小。 在這種情況下，我們正在遞減大小 然後把它關閉，它拔毛 從我們的數組。 為什麼會那樣做？ 所以，如果我有一件事對我的籌碼， 這將是我的尺寸在這一點？ 1。 何為元素1儲存在哪裡？ 什麼指標？ 聽眾：0。 揚聲器1：0。 所以在這種情況下，我們 總是需要使sure-- 而不是返回 大小減去1，因為我們 知道我們的元素是 將要被存儲在1以下 無論我們的規模是，這 只需要照顧它。 這是一個稍微更優雅的方式。 我們只是減小了 大小，然後返回大小。 Mmhmm​​？ 觀眾：我想剛才在一般情況下， 為什麼會這個數據結構 是有益的？ 揚聲器1：這取決於你的環境。 因此對於一些理論， 如果你的工作with-- OK， 讓我看看，如果有一個有利的1 那就是超過外面有利 的CS。 隨著棧，任何時候你需要 跟踪事 是最近添加的是當 你將要使用的堆棧。 我想不出一個好 舉例說，現在。 但每當最近 事情是對你最重要， 這是一個堆棧時， 將是有用的。 我試圖想，如果 有一個很好的這一點。 如果我覺得一個很好的例子，在未來 20分鐘後，我一定會告訴你的。 但總體而言，如果有什麼事， 就像我說的最多的，其中，最近 最重要的是，這是 其中，一摞用武之地。 而隊列是一種相反的。 和所有的小狗狗。 這不是很大的，對不對？ 我覺得我應該 只是有一個小兔子的視頻 右中的中間 節為你們 因為這是一個強烈的部分。 這樣一個隊列。 基本上一個隊列是像一條線。 你們我敢肯定，使用這種日常生活， 就像在我們的食堂。 因此，我們必須去 並得到我們的托盤，我 確保你有排隊等候 刷卡或讓你的食物。 因此，區別就在這裡 是，這是FIFO中。 所以，如果是後進先出後進，先 出，先進先出是先入先出。 因此，這是不管你把 第一次是你最重要的。 所以，如果你在等待 在line--可以嗎 想像一下，如果你去了 去獲得新的iPhone 並且它是一個堆棧，其中 最後一個人符合了它​​的第一， 人們會互相殘殺。 所以FIFO，我們都很熟悉 在這裡，在現實世界中， 而這一切，是因為有實際 種重現這一整條生產線 和排隊結構。 如此而用棧， 我們有push和pop。 同一個隊列，我們有 入隊和出隊。 所以排隊的基本含義 把它放到後面， 和出隊採取的手段 斷從前面。 因此，我們的數據結構是一 稍微有點複雜。 我們有第二個事情防不勝防。 因此，沒有了頭，這 正是堆棧，對不對？ 這是相同的結構的堆疊。 唯一不同的是，現在我們 有這個頭，這你怎麼看 是要跟踪的？ 聽眾：第一個。 揚聲器1：對， 我們把第一件事。 我們的隊列的頭。 誰是排在第一位。 好吧，如果我們做排隊。 再次，與任何 這些數據結構 因為我們處理的是一個數組， 我們需要檢查一下，如果我們有空間。 這有點像我說 你們這些傢伙，如果你打開一個文件， 你需要檢查空。 與任何這些堆棧 和隊列，你需要 看看是否有空間，因為我們 處理一個固定尺寸數組， 我們看到這裡 - 0，1都達5。 那麼，我們在這種情況下是檢查 看看我們仍然有空間。 是我們的規模小於容量是多少？ 如果是這樣，我們需要將其存儲在 尾部，我們更新我們的規模。 那麼，什麼可能的尾巴在這種情況下？ 它沒有明確地寫出來。 我們將如何保存呢？ 什麼尾巴呢？ 因此，讓我們步行穿過這個例子。 因此，這是一個大小為6的數組，對不對？ 而我們現在所擁有的，我們的規模是5。 而當我們把它放在，這是怎麼回事 進入第五個指標，對不對？ 因此，存儲在尾部。 另一種方式來寫尾部也只是 是我們的數組大小​​的指標，對不對？ 這是5號。 接下來的事情將要進入5。 很酷吧？ 行。 它變得稍微複雜 當我們開始用頭搞亂。 是嗎？ 聽眾：這是否意味著我們 會宣布一個數組， 是五行長 那麼，我們要添加到它？ 揚聲器1：第 所以在這種情況下，這是一個堆棧。 這將宣布 作為規模6的數組。 在這種情況下，我們 只有一個剩餘空間。 好了，有一件事是在這 情況下，如果我們的頭是0， 那麼我們就可以在大小添加。 但它變得有點棘手 因為實際上，他們 不具備滑動 對於這一點，所以我要去 畫之一，因為它不是 曾經想像中的那麼簡單，你 開始擺脫的東西。 因此，而用棧 你永遠只能有 擔心大小是什麼 當你添加的東西上， 一個隊列，你還需要 確保你的頭被佔， 由於對隊列一件很酷的事情 是，如果你沒有能力， 你其實可以把它環繞。 OK，所以一件事 - 哦， 這是可怕的粉筆。 有一點要考慮的是這種情況。 我們就做五。 好了，我們要 說的頭就在這裡。 這是0，1，2，3，4。 頭的存在，並 請有東西在其中。 我們要添加的東西，對吧？ 於是事情，我們需要 知道的是，頭總是 要移動這樣的， 然後循環回到我的身邊，好不好？ 所以這個隊列有空間的，對不對？ 它有空間，在一開始， 那種此相反的。 因此，我們需要做的是我們 需要計算的尾巴。 如果你知道你的 頭沒有移動，尾巴 只是你的數組 大小的指標。 但在現實中，如果你使用一個隊列， 你的腦袋可能是被更新。 所以，你需要做的是 實際計算的尾巴。 所以，我們做的是這個公式 在這裡，我打算讓你 你們想想，和 然後我們會談論它。 因此，這是能力。 所以這實際上 給你一個辦法做到這一點。 因為在這種情況下，是什麼？ 我們的頭是1，我們的規模是4。 如果我們這國防部5，我們得到0， 這是我們應該輸入它。 如此則在下一情況下， 如果要做到這一點， 我們說，好吧，讓我們出列的東西。 我們出列了。 我們拿出這個元素，對不對？ 現在我們的頭指指點點， 我們要在另一件事情補充。 這基本上是 回到我們這行的，對不對？ 隊列可以在陣列周圍包裹。 這是主要區別之一。 堆棧，你不能做到這一點。 隨著隊列，您可以 因為所有的事項 是，你知道什麼 最近被添加。 因為一切都在以复加 此向左方向，在這種情況下， 然後環繞，你可以 繼續投入新元素 在陣列的前 因為它不是真的 陣列的前面了。 你能想到的初 數組的地方你的頭居然是。 所以這個公式是怎麼 你計算你的尾巴。 這是否有道理？ 行。 OK，出列，然後 你們有10分鐘 要問我任何澄清的問題 你想要的，因為我知道這很瘋狂。 好吧，所以在相同的方式 - 我不知道你們注意到了， 但CS是所有關於模式。 東西是相當多的 同樣的，只需用很小的調整。 這裡這麼一回事。 我們需要檢查一下，看看我們是否真正 有東西在我們的隊列，對不對？ 說好，是我們的規模大於0？ 涼爽。 如果我們這樣做，那麼我們把我們的頭，這 就是我剛才在這裡展示。 我們更新我們的頭要多一個。 然後我們減了 尺寸，並返回該元素。 有更具體 在study.cs50.net代碼， 我強烈建議你 通過它，如果你有時間， 即使它只是一個偽代碼。 如果你們想通過談話 與我一對一，請讓我 知道了。 我很樂意。 數據結構中，如果 你把CS 124，你會 知道數據結構變得非常 樂趣，這是剛剛開始。 所以，我知道這很難。 沒關係。 我們奮鬥。 我還是做了。 所以不要太擔心了。 但是，這基本上是你 在數據結構速成班。 我知道這是一個很大。 還有什麼是我們 想去一遍？ 任何我們想通過談話？ 是嗎？ 顧客：這個例子，所以 新尾為0了嗎？ 揚聲器1：是的。 聽眾：OK。 所以後來經歷， 你有1加4 or-- 揚聲器1：所以你是說， 當我們想要去做到這一點了嗎？ 聽眾：是的。 所以，如果你搞清楚out--在哪裡 你計算從該尾？ 揚聲器1：所以尾巴 是in--我改變了這一點。 所以在這裡本實施例中，這是 我們正在尋找，確定的數組？ 因此，我們必須在1，2，3和4的東西。 因此，我們有我們的頭是等於1 這一點，我們的大小等於4 在這一點上，對不對？ 大家都同意的話？ 所以我們做頭部加上大小，這 給我們5，然後我們用5國防部。 我們得到0，這告訴我們，0 哪裡是我們的尾巴，在那裡我們有空間。 聽眾：什麼是上限？ 揚聲器1：容量。 抱歉。 所以這是你的數組的大小。 是嗎？ 聽眾：[聽不清]前 我們返回的元素？ 揚聲器1：因此，我們將 前往或返回的那一刻？ 因此，如果我們移動一個，減小尺寸是多少？ 堅持，稍等。 我肯定忘了另外一個。 沒關係。 沒有另一個公式。 是的，你會想返回 頭，然後將其移回。 聽眾：OK，因為在這 點，頭是0， 然後，你要回 指數0，然後使頭1？ 揚聲器1：沒錯。 我認為還有另一種 公式有點像這樣。 我沒有在這上面我的​​頭 我不想給你錯了。 但我認為這是完全有效的 比方說，OK，保存該element--什麼 頭部的元素is--遞減的 大小，移動你的頭了，而歸 無論這個元素。 這是完全有效的。 行。 我覺得這不是 像most--你不 要走出這裡 喜歡，是的，我知道嘗試。 我得到了這一切。 沒關係。 我保證。 但是數據結構的東西， 它需要大量的時間來用於獲得。 最難的可能是1 的東西，我認為，在使用過程中。 因此，它肯定需要 重複和期待at--我 真的不知道鍊錶 直到我做了太多與他們， 在同樣的方式，我沒有 真正了解指針 直到我已經教了兩個 多年來，做自己的pset它。 這需要大量的重申和時間。 最終，它會有種點擊。 但在此期間，如果你有實物 的高水平的理解什麼 這些幹什麼，他們的優點 和cons--這就是 我們真的傾向於強調， 特別是在介紹過程。 喜歡，為什麼我們使用 試試在一個數組？ 喜歡，什麼是陽性 並且其中的每個的底片？ 和理解的取捨 每個這些結構之間 是什麼是更重要的現在。 可以有一個瘋 兩個問題那 要問你實現或推 實施POP或入隊和出隊。 但在大多數情況下，具有 更高層次的認識和更 一個直觀的把握是 比實際更重要 能夠實現它。 這會是真的真棒，如果在座的各位 能夠走出去，去實現一個嘗試， 但我們知道它並不一定 最合理的事情，現在。 但是你可以在你的pset，如果你想 到，然後你會得到實踐， 然後也許你會 真正了解它。 是嗎？ 聽眾：好，那麼哪些是 我們的意思，在pset中使用？ 我是否需要使用其中的一個？ 揚聲器1：是的。 所以，你有你的選擇。 我在這種情況下猜測，我們可以 說說PSET一點點 因為我跑過這些。 因此，在你的pset，你有你的 選擇嘗試或哈希表。 有些人會嘗試 並使用布隆過濾器， 但這些在技術上是不正確的。 因為他們的概率性質， 他們給假陽性的時候。 他們冷靜地審視之中，雖然。 強烈推薦看 在他們最少。 但是，你有你的選擇 一個哈希表，並一試的。 而這將是哪裡 你在你的字典中加載。 你需要選擇 您的散列函數 你需要選擇多少 鏟斗有，它會有所不同。 就像如果你有更多的桶， 也許它會跑得更快。 但是，也許你就是在浪費一個 很多空間的方式，雖然。 你必須弄明白。 Mmhmm​​？ 聽眾：你之前說 我們可以用其它散列函數 我們不必 創建一個哈希函數？ 揚聲器1：是的，沒錯。 因此，從字面上你的哈希函數， 像谷歌“散列函數” 並尋找一些很酷的人。 你是不是有望建成 你自己的哈希函數。 人一生 論文對這些東西。 所以不用擔心構建自己的。 找到一個網上開始。 他們中的一些，你必須 操縱一點點 以確保返回類型匹配 及諸如此類的東西，所以在開始時， 我會建議使用一些 真的很簡單，也許只是 哈希的第一個字母。 然後，一旦你有工作， 結合有冷卻器的散列函數。 Mmhmm​​？ 聽眾：請問一個嘗試是或 高效而只是更難，like-- 揚聲器1：那麼一試，我想， 直覺是難以實現 但是非常快的。 但是，佔用了更多的空間。 同樣，你可以在優化這兩個的 不同的方式和有辦法to-- 聽眾：我們怎樣分級的呢？ 它matter-- 揚聲器1：所以你正常的分級方式。 你要對設計進行分級。 無論你的方式，你要 確保它的優雅，因為它可以 並作為有效的，因為它可以。 但是，如果你選擇一個試或哈希 表的，只要它工作， 我們很高興。 如果你使用的東西，哈希 第一個字母，這很好， 如可能喜歡的設計，明智的。 我們也到達 點這semester-- 我不知道，如果你 球員noticed--如果你 PSET等級下降一點點 因為設計和諸如此類的東西的， 這是完全正常的。 它讓到一個地步，你 程序正變得越來越複雜。 還有更多的地方 你可以改善。 所以這是完全正常的。 這並不是說你 您PSET做差。 這只是我們是很難對你現在。 所以每個人的感覺吧。 我只是分級所有pset中。 我知道每個人都感覺到了。 所以不用擔心。 如果您有任何問題， 之前的pset或方法可以改善， 我嘗試了具體的意見 的地方，但有時它的後期 我累了。 是否有任何其他的東西 關於數據結構？ 我敢肯定，你們真的不 要談他們了， 但如果有，我很高興 走過去了，還有什麼 講座從過去 上週，上一周。 我知道，上週所有檢討， 我們可能已經跳過了一些檢討 從講座。 還有沒有其他問題我可以回答？ 好了，沒事了。 好了，你們早出去15分鐘。 我希望這至少是半很有幫助， 我會看到你下週的傢伙， 或週四的辦公時間。 是否有小吃請求 下週，它的東西嗎？ 因為我忘了今天的糖果。 我帶過去的糖果 上週，但它是哥倫布日， 所以就像六個人誰 有四袋糖果的自己。 我可以帶星形圖案 再次，如果你喜歡。 星形圖案？ OK，聽起來不錯。 有一個偉大的日子，伙計們。