JASON HIRSCHHORN：歡迎大家 在第七節。 我們是在使用過程中七個星期。 而這個即將到來的週四 是萬聖節，所以我 打扮得像個南瓜。 我不能彎腰，把上 我的鞋，所以這就是為什麼我 只是穿著襪子。 我也沒有下穿什麼 這一點，所以我不能把它關閉，如果它的 分心給你。 我提前表示歉意。 你不需要想像 這是怎麼回事。 我穿的拳擊手。 所以，這一切都很好。 我為什麼我是一個較長的故事 打扮成一個南瓜，但我要去 保存後在本節 因為我確實想上手。 我們有很多令人興奮的事情 走在這個星期。 他們大多​​直接涉及到這一點 本週的問題集，拼寫錯誤。 我們打算是想在聯 列表和哈希表 整個一節。 我每星期把這個名單了，名單 你來幫助您的資源 本課程的材料。 如果處於虧損狀態，或者尋找一些 更多信息，請查看之一 這些資源。 再次，pset6是拼寫錯誤， 本週的pset中。 它也鼓勵你，和我 鼓勵你，使用一些其他的 資源專門為這個pset中。 特別是，這三個我已經 列出在屏幕上 - gdb的，這是我們一直熟悉的 並一直在使用了一段時間了，是 打算這週是非常有益的。 所以，我把那在這裡。 但每當你用C的工作， 你應該總是使用gdb來 調試程序。 這個星期也Valgrind的。 有誰知道什麼Valgrind的呢？ 觀眾：它檢查內存洩漏？ JASON HIRSCHHORN：Valgrind的 檢查內存洩漏。 所以，如果你在malloc的東西你 程序，你要求的內存。 在程序結束時，你有 寫免費的你已經一切 malloced給記憶回來了。 如果你不寫免費在年底 你的程序涉及到一個結論， 一切都將自動 被釋放。 而對於小程序，它的 不是什麼大不了的事。 但是，如果你正在編寫一個較長的運行 程序不會退出， 不一定，在一兩分鐘或中 幾秒鐘，然後內存洩漏 可以成為一個巨大的交易。 所以對於pset6，期望是 你將有零內存洩漏與 你的程序。 要檢查內存洩漏，運行的valgrind 它會給你一些不錯的 輸出讓你知道是否 或不是一切是免費的。 我們將用它以後練 今天，有希望。 最後，diff命令。 你用類似於它的東西 在pset5與偷看工具。 讓你看看裡面。 您也使用差異，同樣，每 問題設置規範。 但允許你 比較兩個文件。 你可以比較的位圖文件和 一名工作人員解決方案信息標題和 在pset5你的解決方案，如果 您選擇使用它。 差異可以讓你 做到這一點，也是如此。 您可以比較正確的答案 本週的問題設​​置為你的答案 ，看看它是否行向上或 其中誤差。 因此，這些都是三個好工具， 你應該使用這個星期， 一定要檢查你的程序 這三個工具 將其入夥前 同樣，正如我剛才所說的每一周， 如果您有任何意見對我來說 - 無論是 積極和建設性的 - 可以自由地前往網站 在這張幻燈片的底部 並且輸入它。 我真的很感激任何 和所有的反饋。 如果你給我具體的東西， 我可以做些什麼來改善或者說我 做得很好，你想我 繼續，我採取的心臟和 真的努力去傾聽 您的反饋。 我不能保證我會做 一切，不過，就像穿了 每週南瓜服裝。 因此，我們要花費大量的 部分，正如我所說，談論 鍊錶和哈希表，這 將直接適用於 問題本週設置。 鍊錶我們就去了相對 很快，因為我​​們已經花了一個公平的位 的時間段去了它。 所以我們會得到直入 編碼問題的鍊錶。 然後在最後我們來談談 哈希表和它們如何適用於本 本週的問題集。 你以前見過這個代碼。 這是一個結構，它被定義 新的東西稱為一個節點。 和一個節點內有一個整數 在這裡，有一個指針 另一節點。 我們之前已經看到這一點。 這已經上來的 一對夫婦現在星期。 它結合了三分球，這是我們一直 與和結構，這讓工作 我們將兩個不同的 事成一種數據類型。 有很多在屏幕上怎麼回事。 但是，這一切應該是比較 熟悉你。 在第一行中，我們 聲明一個新的節點。 然後將該新節點裡面，我設置 一個在該節點的整數。 我們的下一行我做了見 printf命令，但我已經變灰 printf命令，因為真的 重要的是這條線在這裡 - new_node.n。 什麼是圓點是什麼意思？ 觀眾：轉到節點， 評估它的N值。 JASON HIRSCHHORN：這是 完全正確。 點指訪問n個部分 這個新的節點。 下面這一行做什麼？ 邁克爾。 觀眾：它創建另一個節點 將指向新的節點。 JASON HIRSCHHORN：所以它不 創建新的節點。 它創建了一個什麼？ 觀眾：一個指針。 JASON HIRSCHHORN：一個指針，指向一個節點， 通過該節點*這裡所示。 因此它產生一個指針指向一個節點。 和哪一個節點指向它 到，邁克爾？ 觀眾：新的節點？ JASON HIRSCHHORN：新節點。 和它的指向那裡，因為我們已經 賦予它新的節點的地址。 現在在這條線，我們看到 兩種不同的方法 表達了同樣的事情。 而我想指出如​​何將這些 兩件事情是相同的。 在第一行中，我們解引用 指針。 所以我們去的節點。 這就是這個星號表示。 我們已經看到，之前與指針。 去那個節點。 這就是在括號中。 然後通過點操作符訪問 該節點的n個元素。 所以這走的語法 我們看到在這裡和現在 使用它的指針。 當然，它得到的忙，如果樣 你寫的那些括號 - 這星和那點。 它變得有點忙。 因此，我們有一些語法糖。 而這條線就在這裡 - ptr_node - >ñ。 這做同樣的事情。 因此，在這兩行代碼是 等效，並會盡 完全相同的事情。 但我想指出那些之前 我們再往前走讓你明白 真的這個東西在這裡是 只是語法糖提領 的指針，然後將要 該結構的n個部分。 這個幻燈片有任何疑問？ 確定。 因此，我們要經過幾個 操作，你可以做的 鍊錶。 鍊錶，召回，是一系列的 指向另一個節點。 而我們一般先從一個指針 稱為頭，一般地，一個指向 在列表中的第一件事情。 所以在第一行這裡，我們 首先我們原裝L。 所以，那個東西你能想到的 - 這 這裡的文字，你能想到的作為 剛剛我們已經存儲的指針 某處點 第一個元素。 而在這個鍊錶 我們有四個節點。 每個節點都是一個大箱子。 裡面的大較大的方框 框是整數部分。 然後我們有一個指針組成部分。 這些箱子都沒有吸引到 因為規模是多大 以字節為單位的整數 現在有多大？ 四。 多大是一個指針？ 四。 因此，其實，如果我們繪製 這個擴展的兩個方塊 將是相同的大小。 在這種情況下，我們希望插入 事到鍊錶。 所以，你可以下來看看我們在這裡插入 5，我們通過遍歷 鍊錶，找到其中5 去，然後將其插入。 讓我們打破了，去 多一點點慢。 我要指出的板。 因此，我們有我們的節點5的 我們在mallocs創建。 為什麼大家都笑了？ 只是在開玩笑。 確定。 因此，我們已經malloced五位。 我們創建這個節點 別的地方。 我們必須準備好去。 我們開始在前面 我們的名單有兩個。 我們要插入 在已排序的方式。 所以，如果我們看到了兩個，我們希望把 五，我們該怎麼做，當我們看到 東西不到我們？ 什麼？ 我們要插入五成這 鍊錶，保持它排序。 我們看到第二。 那麼，我們該怎麼辦？ 馬庫斯？ 觀眾：調用指針 到下一個節點。 JASON HIRSCHHORN：為什麼做 我們去下一個？ 觀眾：因為它是 列表中的下一個節點。 而我們只知道其他位置。 JASON HIRSCHHORN：而且五是更大 大於2，尤其如此。 因為我們要保持它排序。 因此，五是大於二。 因此，我們就移動到下一個。 現在我們達到四。 而當我們達到四會發生什麼？ 五是大於四。 因此，我們繼續前進。 現在我們是在六人。 什麼我們六看？ 是的，卡洛斯？ 觀眾：六是大於五。 JASON HIRSCHHORN：六是 大於五。 所以這就是我們想要的 插入五位。 但是，請記住，如果我們 只有一個指針在這裡 - 這是我們額外的指針，它是 遍歷整個列表。 我們正在指向6。 我們已經失去了什麼軌道 談到前六。 因此，如果我們要插入到的東西 這個列表保持排序，我們 大概需要多少個三分球？ 觀眾：兩個。 JASON HIRSCHORN：兩個。 一個以跟踪當前的 1，一個用於跟踪 前一個。 這僅僅是一個單向鍊錶。 那就只一個方向。 如果我們有一個雙向鍊錶，其中 一切都指向一點 之後和之前的事情了，然後 我們不需要那樣做。 但在這種情況下，我們不希望失去 軌道的情況下，我們面前什麼來 我們需要插入五個地方 在中間。 說我們被插入9。 什麼時候會發生 我們得到了八？ 觀眾：你不得不 拿到零點。 而不必空點你不得不 添加一個元素，然後有 這點九。 JASON HIRSCHORN：沒錯。 所以我們得到8。 我們到達列表的末尾，因為 這是指向空。 而不是有和現在，它指向 空我們把它指向我們的新節點。 而我們在設置指針 我們的新節點為null。 沒有任何人有任何疑問， 有關插入？ 如果我不關心什麼 保持排序的列表？ 觀眾：在堅持它 開始或結束。 JASON HIRSCHORN：在堅持它 的開始或結束。 哪一個才好呢？ 鮑比？ 為什麼要結束了嗎？ 觀眾：因為開始時 已經充滿。 JASON HIRSCHORN：確定。 一開始已經充滿。 誰想要反駁鮑比。 馬庫斯。 觀眾：那麼你可能想 把它貼在一開始，因為 否則，如果你把它在 最後，你不得不 遍歷整個列表。 JASON HIRSCHORN：沒錯。 因此，如果我們正在考慮運行時， 在最後插入的運行時 將N，這個尺寸。 什麼是插入的大O運行 在開始？ 常量時間。 所以，如果你不關心保持 整理東西，好多只 插入此列表的開頭。 並可以在常數時間內完成。 確定。 接下來的操作就是找到，這是其它 - 我們這個措辭作為搜索。 但我們要看看通過 鍊錶的一些對象。 你們已經看到代碼 以前搜索的講座。 樣的，但我們只是做了它與 插入，或者至少插入 東西來分類的。 你通過，由節點將節點， 直到你發現你的號 尋找。 如果你達到會發生什麼 該列表的末尾？ 說我在找九和我 到達列表末尾。 我們該怎麼辦？ 觀眾：返回false？ JASON HIRSCHORN：返回false。 我們沒有發現它。 如果到達列表的末尾， 你沒有找到你的號 尋找的，它不是在那裡。 大約有任何疑問找到？ 如果這是一個排序的列表，會是什麼 對我們的搜索有什麼不同？ 是啊。 觀眾：它會找到的第一個值 這是大於1 你正在尋找和 然後返回false。 JASON HIRSCHORN：沒錯。 所以，如果這是一個排序的列表，如果我們得到 東西是比什麼 我們要尋找的，我們不需要 繼續前進到列表的末尾。 我們可以在這一點上返回false 因為我們不會找到它。 現在的問題是，我們已經討論過 保持鍊錶排序， 保持它們排序。 那將是什麼你 可能將不得不去思考 當編碼問題設置5，如果你 選擇配有獨立的哈希表 鏈接的方法，這 我們將在以後討論。 但它是值得的，以保持列表 排序，然後才能有可能 更快的搜索？ 還是更快速插入 東西在不斷的運行，但隨後 有較長的搜索？ 這是一個折中就在那裡，你 去決定什麼是更合適 針對您的具體問題。 而且也並不一定是 絕對正確的答案。 但它肯定是你的決定 做了，大概好保衛 在，也就是說，一個或兩個註釋為什麼 你選擇了一個比其他。 最後，刪除。 我們已經看到刪除。 它類似於搜索。 我們期待的元素。 假設我們正在試圖刪除6。 因此，我們發現了六個就在這裡。 我們必須確保我們的東西 做的是，無論是指向 6 - 正如我們在一步看 兩下在這裡 - 凡是指著六個需要 跳過6現在改為 無論6指向。 我們不希望永遠孤兒的其餘部分 通過忘記來設定我們的名單 以前的指針。 然後，具體情況取決於 上節目，他們就會 完全刪除該節點。 有時候你會想回到 該值，在此節點。 所以這就是如何刪除工作。 對任何問題刪除？ 觀眾：所以，如果你要刪除 它，你只需要使用免費的，因為 想必有人malloced？ JASON HIRSCHORN：如果你想釋放 東西是完全正確的，你 malloced它。 假設我們想返回這個值。 我們可能會選出6位，然後免費 這個節點和呼叫免費就可以了。 或者，我們可能會調用free第一 然後選出6。 確定。 因此，讓我們繼續前進練習編碼。 我們要編寫三個函數。 第一個被稱為insert_node。 所以，你有我發郵件給你的代碼， 如果你看這個以後 您可以訪問代碼linked.c 在CS50網站。 但在linked.c，有一些 框架代碼的已經 已為你寫好。 然後有一對夫婦的功能 你需要寫。 首先我們要 寫insert_node。 什麼insert_node呢 就是插入一個整數。 而你給的整數 成一個鍊錶。 特別是，你需要 保持排序的列表 從最小到最大。 此外，您不希望 插入任何重複。 最後，你可以看到insert_node 返回一個布爾值。 所以你應該讓用戶知道 是否插入了 成功通過返回true或false。 在這個程序結束 - 而這個階段你不需要 不用擔心釋放任何東西。 因此，所有你正在做的是採取一個整數 並將其插入到一個列表中。 這就是我要問你現在要做的。 再次，在linked.c，你 全有，是框架代碼。 你應該向底部看 示例函數聲明。 然而，在進入它的編碼 在C中，我強烈建議你去 經過的步驟，我們已經 每星期練習。 我們已經通過了 在此照片。 所以，你應該有一定的了解 是如何工作的。 但我會鼓勵你寫 跳水英寸之前的一些偽代碼 我們要去投奔 偽代碼為一組。 然後，一旦你寫你的 偽代碼，一旦我們寫我們 偽代碼為一組，你可以 進入編碼它在C 作為一名負責人時，insert_node功能 可能是最棘手的 三，我們要去寫，因為我 增加了一些額外的限制， 你的編程，尤其是 你不會插入任何 重複，並且列表 應保持有序。 所以這是一個不平凡的程序 你需要的代碼。 而你為什麼不採取六時五十五 分鐘，只是為了讓工作在 偽代碼和代碼。 然後我們將開始 要為一組。 同樣，如果你​​有任何問題，只是 舉起你的手，我會回到你身邊。 。 我們一般做這些 - 或者我沒有明確說你 能與人合作。 但很明顯，我強烈鼓勵你， 如果你有問題，問 鄰居坐在你旁邊 甚至是與別人合作 否則，如果你想。 這不必是一個單獨的 沉默的活動。 讓我們開始寫一些 偽代碼在黑板上。 誰可以給我的第一行 偽代碼對這一計劃？ 對於此功能，而 - insert_node。 奧爾登？ 觀眾：所以第一件事是 創建一個新的指針的節點和餘 初始化它指向相同 東西的清單指向。 JASON HIRSCHORN：確定。 所以，你要創建一個新的指針 到列表中，而不是到該節點。 觀眾：對。 是啊。 JASON HIRSCHORN：確定。 然後我們究竟想幹什麼？ 什麼之後呢？ 怎麼樣的節點？ 我們沒有一個節點。 我們只是有一個值。 如果我們要插入一個節點，我們怎麼辦 需要之前，我們甚至可以先做 想想插入呢？ 觀眾：哦，對不起。 我們需要將malloc空間的節點。 JASON HIRSCHORN：優秀。 讓我們做 - 確定。 無法達到那麼高。 確定。 我們要往下走，然後 我們使用的是兩列。 我不能去了 - 確定。 創建新的節點。 您可以創建另一個指針列表 或者你可以用列表作為它的存在。 你並不真的需要做到這一點。 因此，我們創建了一個新的節點。 大。 這就是我們做的第一個。 下一步是什麼？ 觀眾：請等待。 如果我們現在創建一個新的節點或 我們應該等待，以確保 有節點沒有重複 名單上之前，我們創建它嗎？ JASON HIRSCHORN：好問題。 讓我們認為，對於後來因為 大部分我們將要創建的時間 一個新節點。 因此，我們會繼續在這裡。 但是，這是一個很好的問題。 如果我們創建它，我們發現 一式兩份，又該 我們返回之前做的？ 觀眾：釋放它。 JASON HIRSCHORN：是啊。 可能釋放它。 確定。 我們之後我們做什麼 創建一個新的節點？ 安妮？ 觀眾：我們把 在節點數量？ JASON HIRSCHORN：沒錯。 我們把數字 - 我們用malloc空間。 我要離開了 所有為一行。 但你說得對。 我們malloc的空間，然後 我們把數英寸 我們甚至可以設置指針 它的一部分為null。 這是完全正確的。 再怎麼樣之後呢？ 我們畫了這幅畫在黑板上。 那麼，我們該怎麼辦？ 觀眾：我們通過列表。 JASON HIRSCHORN：穿過列表。 確定。 什麼我們在每個節點檢查。 庫爾特，什麼我們檢查 於每個節點？ 觀眾：看有無N值的 該節點是大於n值 我們的節點。 JASON HIRSCHORN：確定。 我該怎麼辦 - 是的，確定。 所以它的北 - 我會說，如果值大於 比這個節點，那麼我們怎麼辦？ 觀眾：好，那我們插入 前正確的事情。 JASON HIRSCHORN：確定。 所以，如果它大於這個， 那麼我們要插入。 但我們要正確之前，將其插入 因為我們也將需要 跟踪，然後， 什麼是以前。 所以之前插入。 因此，我們可能錯過了什麼 較早前。 我們可能需要被保留 軌道發生了什麼事情。 但我們會回到那裡。 那麼，什麼值小於？ 庫爾特，我們該怎麼做，如果 值小於？ 觀眾：那你只是繼續前進 除非它是最後一個。 JASON HIRSCHORN：我喜歡這樣。 所以去到下一個節點。 除非它是最後一個 - 我們可能檢查的 中的一個條件的條件。 但是，是的，下一個節點。 而且是越來越過低， 因此，我們將在這裡搬過來。 但是，如果 - 大家可以看到這個？ 如果我們是平等的我們該怎麼做？ 如果這個值我們試圖插入 等於該節點的值？ 是嗎？ 觀眾：[聽不清]。 JASON HIRSCHORN：是啊。 鑑於這一點 - 馬庫斯是正確的。 我們也可以或許做 不同的東西。 但鑑於我們已經創造了它，在這裡 我們應該釋放，然後返回。 哦男孩。 是更好嗎？ 怎麼樣？ 確定。 免費，然後我們怎麼辦 返回[聽不清]？ 確定。 我們是否缺少什麼？ 那麼，我們要跟踪 事先節點？ 觀眾：我覺得它會去 之後創建一個新的節點。 JASON HIRSCHORN：確定。 所以，在一開始我們可能會 - 是的，我們可以創建一個指向新 節點，就像前一個節點的指針和 當前節點的指針。 因此，讓我們插入這裡。 創建當前和以前 指向的節點。 但是，當我們調整這些指針？ 我們在哪裡做的代碼？ 傑夫？ 觀眾： - 值條件是什麼？ JASON HIRSCHORN：哪 一個特殊？ 觀眾：我只是困惑。 如果值大於這個節點， 並不意味著你要去 到下一個節點？ JASON HIRSCHHORN：所以，如果我們的價值 大於該節點的值。 觀眾：是啊，那你想要 進一步向下行去，對不對？ JASON HIRSCHHORN：對。 所以我們不要插入在這裡。 如果值小於當前節點，然後 我們進入下一個節點 - 或者那我們 前插入。 觀眾：等一下，這是本 節點，這是價值？ JASON HIRSCHHORN：好問題。 根據該函數的定義值 就是我們給出。 因此，價值是我們給出的數字。 因此，如果該值小於該 節點，我們需要時間來插入。 如果值大於這個節點， 我們去到下一個節點。 再回到原來的問題， 不過，在這裡 - 觀眾：如果值大於 比這個節點。 JASON HIRSCHHORN：所以 我們該怎麼做嗎？ 甜蜜。 這是正確的。 我只是去寫 更新指針。 但是，是的，與當前的 你會更新到 指向下一個。 別的我們缺少什麼？ 所以，我要輸入此 編碼成gedit的。 而我做到這一點，你可以有一個 夫婦多鐘上班編碼 這在C 所以，我有輸入的偽代碼。 一個快速的音符在我們開始之前。 我們未必能夠完全 在完成所有這 這三個功能。 有正確的解決辦法 我會發電子郵件到你們 部後，它會 張貼在CS50.net。 所以我不鼓勵你 去看看部分。 我鼓勵你在嘗試這些你 自己，然後用實踐 問題來檢查你的答案。 這些都被設計成緊密 與堅持什麼 你所要做的習題集。 因此，我鼓勵你練習這個 在你自己的，然後使用代碼 檢查你的答案。 因為我確實想移動到哈希 表在某些部分點。 因此，我們可能不會得到通過這一切。 但我們現在會做盡可能多的，我們可以。 確定。 讓我們開始吧。 阿薩姆，我們如何創建一個新的節點？ 觀眾：你STRUCT *。 JASON HIRSCHHORN：所以我們 有一個在這裡。 哦，對不起。 你是說結構*。 觀眾：然後[？樣？] 節點或c節點。 JASON HIRSCHHORN：確定。 我要叫它new_node 所以我們可以保持一致。 觀眾：你要設置的 頭，第一個節點。 JASON HIRSCHHORN：確定。 所以，現在這個指向 - 所以這 還沒有創建一個新的節點呢。 這僅僅是指向 列表中的第一個節點。 我如何創建一個新的節點？ 如果我需要空間來創建一個新的節點。 malloc的。 有多大？ 觀眾：結構體的大小。 JASON HIRSCHHORN：該 該結構的大小。 和什麼所謂的結構？ 觀眾：節點？ JASON HIRSCHHORN：節點。 所以的malloc（的sizeof（節點））; 給我們空間。 而就是這條線 - 有一件事是不正確的這條線。 是new_node一個指向結構的指針？ 這是一個通用名稱。 這是什麼 - 節點，沒錯。 這是一個結點*。 右後我們該怎麼做 我們malloc的東西，阿三？ 什麼是我們做的第一件事？ 如果它不工作？ 觀眾：哦，檢查它是否 指向的節點？ JASON HIRSCHHORN：沒錯。 所以，如果你new_node等於等於 空，我們該怎麼做？ 這會返回一個布爾值，此功能。 沒錯。 看起來不錯。 什麼要補充的嗎？ 我們會在末尾添加的東西。 但是，到目前為止，看起來不錯。 創建當前和以前的指針。 邁克爾，我該怎麼辦呢？ 觀眾：你將不得不 做一個結點*。 你必須做一個不 為new_node但對於 節點我們已經有了。 JASON HIRSCHHORN：確定。 因此，在當前節點我們是在。 我會打電話給那個CURR。 好的。 我們已經決定，我們希望保持 2，因為我們需要知道 什麼才。 他們得到什麼初始化？ 觀眾：他們在我們的列表值。 JASON HIRSCHHORN：那麼什麼是 我們的名單上的第一件事？ 或者，我們怎麼知道在哪裡 一開始我們的名單是什麼？ 觀眾：是不是應該通過 進入功能？ JASON HIRSCHHORN：對。 它是通過在這裡。 這樣，如果它的傳遞給函數，該 啟動列表中，我們應該怎樣 設置電流等於？ 觀眾：列表。 JASON HIRSCHHORN：列表。 這是完全正確的。 現在，它擁有的地址 我們的列表的開始。 又是怎麼回事以前？ 觀眾：原價減一？ JASON HIRSCHHORN：有 什麼才。 所以，我們能做些什麼來表示什麼？ 觀眾：空。 JASON HIRSCHHORN：是啊。 這聽起來是個好主意。 完美的。 謝謝。 經過列表。 康斯坦丁，多久我們要 要經過的名單？ 觀眾：直到我們到達空。 JASON HIRSCHHORN：確定。 所以，如果，而對於循環。 我們在做什麼？ 觀眾：也許一個for循環？ JASON HIRSCHHORN：讓我們做一個for循環。 確定。 觀眾：我們說的 - 直到當前指針 不等於空。 JASON HIRSCHHORN：所以，如果我們知道 條件下，我們怎麼能寫一個循環 根據關閉的狀態。 我們應該使用什麼樣的循環？ 觀眾：雖然。 JASON HIRSCHHORN：是啊。 這使得基於更有意義 關閉你說什麼。 如果我們只是想進入我們它會 只知道那個東西，它將使 踏踏實實做一個while循環。 而當前不等於空值， 如果值小於該節點。 AKSHAR，給我這條線。 觀眾：如果電流>Ñ Ñ​​低於價值。 或推翻。 開關的支架。 JASON HIRSCHHORN：對不起。 觀眾：更換支架。 JASON HIRSCHHORN：所以，如果它是 比價值更大。 因為這是混亂的 上面的評論，我會做到這一點。 但肯定的。 如果我們的價值低於本 節點，我們該怎麼做？ 呵呵。 我就在這裡。 前插入。 確定。 我們該怎麼做呢？ 觀眾：是不是還是我？ JASON HIRSCHHORN：是啊。 觀眾：你 - new_node - >下一個。 JASON HIRSCHHORN：那麼什麼是 這將等於？ 觀眾：這將相等的電流。 JASON HIRSCHHORN：沒錯。 這樣一來，其他 - 我們需要更新什麼？ 觀眾：檢查過去等於null。 JASON HIRSCHHORN：如果上一個 - 所以，如果前一個等於null。 觀眾：這意味著它是怎麼回事 成為頭部。 JASON HIRSCHHORN：這意味著 它已經成為了頭。 這樣的話我們該怎麼做？ 觀眾：我們做頭部等於new_node。 JASON HIRSCHHORN：頭 等於new_node。 以及為什麼在這裡頭，沒有列出？ 觀眾：因為頭是一個全球性的 變量，它是起始位。 JASON HIRSCHHORN：甜。 確定。 和 - 觀眾：那你別的上一頁 - > 接下來等於new_node。 然後返回true。 JASON HIRSCHHORN：在哪裡做 我們設置new_node結束了嗎？ 觀眾：我會 - 我設置的開始。 JASON HIRSCHHORN：那麼什麼線？ 觀眾：在if語句 如果它被稱為檢查。 JASON HIRSCHHORN：就在這裡？ 觀眾：我願意做new_node - >Ñ 等於價值。 JASON HIRSCHHORN：聽起來不錯。 也許這是有道理的 - 我們不這樣做 要知道我們是在什麼名單 因為我們只處理 用一個列表。 因此，一個更好的函數聲明為 這只是為了擺脫這種 完全和剛插入 一個值到頭部。 我們甚至不需要知道 我們在做什麼榜單中。 但我會保持它現在和 那麼在更新變化 幻燈片和代碼。 所以，看起來很不錯的了。 如果值 - 誰可以做這行？ 如果 - 我們該怎麼做在這裡，諾亞。 觀眾：如果值大於 比CURR - >北 - JASON HIRSCHHORN：如何做 我們進入下一個節點？ 觀眾：CURR-> n是 等於new_node。 JASON HIRSCHHORN：那麼n是 什麼樣的結構的一部分？ 整數。 和new_node是一個指針，指向的節點。 因此，我們應該更新什麼CURR的一部分？ 如果沒有n，那麼有什麼其他部分？ 諾亞，有什麼其他部分。 觀眾：呵呵，下次。 JASON HIRSCHHORN：下一步，沒錯。 沒錯。 接下來是正確的。 還有什麼我們需要 更新，諾亞？ 觀眾：該指針。 JASON HIRSCHHORN：所以 我們更新了電流。 觀眾：上一頁 - >下一個。 JASON HIRSCHHORN：是啊。 OK，我們會暫停。 誰可以幫助我們在這裡？ 馬努，我們應該怎樣做？ 觀眾：你一定要設置 它等於CURR - >下一個。 但做到這一點之前的前行。 JASON HIRSCHHORN：確定。 還有別的嗎？ AKSHAR。 觀眾：我不認為你是 為了改變未來CURR->。 我覺得你的意思做CURR等於 CURR - >下次去到下一個節點。 JASON HIRSCHHORN：那麼對不起，在哪裡？ 在哪一行？ 這條線？ 觀眾：是啊。 讓CURR等於CURR - >下一個。 JASON HIRSCHHORN：所以這是正確的 因為電流是 指針到一個節點。 我們希望它指向下一個 什麼是越來越當前節點 指出。 CURR本身所具有的未來。 但如果我們要更新curr.next，我們 將更新的實際音符 本身，而不是這個地方 指針指著。 那麼這條線，雖然。 阿維？ 觀眾：上一頁 - >下一次等於CURR。 JASON HIRSCHHORN：如此反复，如果上一個是一個 指針指向一個節點，前值 - >下一個是 實際的指針中的節點。 所以這將是一個更新 指針在一個節點CURR。 我們不希望更新 指針中的一個節點。 我們要更新以前。 那麼，如何才能做到這一點？ 觀眾：這純粹是上一個。 JASON HIRSCHHORN：對。 上一個是指向的節點。 現在，我們正在改變到一個 新的指針的節點。 OK，讓我們向下移動。 最後，這最後一個條件。 傑夫，我們該怎麼做嗎？ 觀眾：如果值是 等於CURR->ñ。 JASON HIRSCHHORN：對不起。 哦，我的天啊。 什麼？ 值== CURR->ñ。 我們該怎麼辦？ 觀眾：你會釋放我們的new_node， 然後你會返回false。 JASON HIRSCHHORN：這是什麼 我們已經寫了這麼遠。 沒有任何人有什麼 加入我們做出過嗎？ 確定。 讓我們試試吧。 控制可能到達終點 非void函數。 阿維，這是怎麼回事？ 觀眾：你應該把回報 while循環的外面真的嗎？ JASON HIRSCHHORN：我不知道。 難道你要我？ 觀眾：沒關係。 號 JASON HIRSCHHORN：AKSHAR？ 觀眾：我覺得你的意思是 把返回false在年底 while循環。 JASON HIRSCHHORN：那麼， 你希望它去？ 觀眾：像while循環之外。 所以，如果你退出while循環的方式 你已經走到了盡頭，並 什麼也沒有發生過。 JASON HIRSCHHORN：確定。 那麼，我們在做什麼在這裡？ 觀眾：你返回false 有作為。 JASON HIRSCHHORN：哦，我們 這樣做在這兩個地方？ 觀眾：是啊。 JASON HIRSCHHORN：確定。 我們是否應該去？ 哦，我的天啊。 對不起。 我的屏幕道歉。 那種它嚇壞了我們。 因此，選擇一個選項。 零，每代碼，退出程序。 一要插入一些東西。 讓我們來插入三個。 插入未成功。 我要打印出來。 我沒有任何東西。 確定。 也許這只是一個僥倖。 插一句。 沒有成功。 確定。 讓我們通過GDB真的快速運行 要看看是怎麼回事。 還記得GDB /姓名您的 計劃將引領我們進入GDB。 是很多來處理？ 閃爍的？ 也許吧。 閉上你的眼睛，並採取一些深 如果你厭倦了喘氣，呼吸的 看著它。 我在廣發行。 什麼是我做的第一件事在廣發行？ 我們必須搞清楚 這是怎麼回事。 讓我們來看看。 我們有六分鐘圖 發生了什麼事情。 突破為主。 然後我該怎麼辦？ 卡洛斯？ 運行。 確定。 讓我們選擇一個選項。 又是什麼Ñ辦？ 下一步。 是啊。 觀眾：你沒提 - 沒有你說的那個頭，那是 初始化為null開頭。 不過，我想你說還行。 JASON HIRSCHHORN：讓我們去 - 讓我們來看看 在GDB中，然後我們就回去。 但它聽起來像你已經有 一些想法發生了什麼事情。 因此，我們要插入一些東西。 確定。 我們已經插入。 請輸入一個整數。 我們會插入三個。 然後我在這行。 我該如何去開始調試 插入已知的功能？ 哦，我的天啊。 這是一個很多。 是嚇壞了很多嗎？ 觀眾：哦，它死了。 JASON HIRSCHHORN：我剛 拉出來。 確定。 觀眾：也許這是 導線的另一端。 JASON HIRSCHHORN：哇。 因此，底線 - 你說什麼？ 觀眾：我說的技術上的諷刺 困難在這個類中。 JASON HIRSCHHORN：我知道。 如果我有過這部分控制權。 [聽不清] 這聽起來不錯。 為什麼你們不開始思考 我們可能做錯了， 我們將回到90秒。 Avica，我要問你怎麼走 裡面insert_node調試它。 所以這是我們最後離開的。 我怎麼進去insert_node，Avica， 檢查是怎麼回事？ 什麼GDB命令？ 休息也不會帶我裡面。 請問侯爵夫人知道嗎？ 觀眾：是什麼？ JASON HIRSCHHORN：什麼GDB命令 我用走這個函數裡面？ 觀眾：步驟？ JASON HIRSCHHORN：通過步驟 S.這裡面需要我。 確定。 New_node mallocing一些空間。 這一切看起來像它去。 讓我們來看看new_node。 它得到了一些內存地址。 讓我們來看看 - 這是正確的。 所以，這裡的一切似乎 可以正常工作。 觀眾：有什麼區別 之間的P和顯示器？ JASON HIRSCHHORN：P代表打印。 所以你問有什麼 那這之間的區別？ 在這種情況下，沒有什麼。 但一般有 一些差異。 而且你應該看看在GDB手冊。 但在這種情況下，沒有什麼。 我們傾向於使用打印，但因為 我們並不需要做得更多，不 打印單個值。 確定。 因此，我們對我們的代碼80行， 設置節點* CURR等於列表。 讓我們打印出CURR。 它等於列表。 甜蜜。 等待。 它等於什麼。 這看起來不正確。 我們走吧。 這是因為在GDB中，右，如果 這是你在這行 還沒有執行。 所以，你需要實際輸入 執行下一行 之前看到它的結果。 所以，我們在這裡。 我們只是執行這條線， 以前等於null。 如此反复，如果我們以前的打印 我們將不會看到什麼奇怪。 但是，如果我們實際執行的 行，那麼我們會看到 即該行的工作。 因此，我們有CURR。 這些都是很好的。 對不對？ 現在，我們在這條線就在這裡。 雖然CURR不等於空。 那麼，有哪些呢CURR相等？ 我們只是看到它等於空。 我們把它打印出來。 我會再次把它打印出來。 所以是while循環 去執行？ 觀眾：號 JASON HIRSCHHORN：所以，當我輸入了 行，你看我們跳了一路 下到谷底，返回false。 然後我們要返回false 然後回到我們的節目和 最終打印出來，就像我們所看到的， 插入沒有成功。 因此，任何人有什麼什麼想法 我們需要做些什麼來解決呢？ 我要等到我看到 一對夫婦的手走了。 我們沒有執行這個。 請記住，這是第一次 我們正在做的事情。 我不打算做一對夫婦。 我打算做幾個。 因為一對夫婦意味著兩。 我等了兩個多。 第一插入，CURR， 默認情況下等於null。 而這個循環只執行 如果CURR不為null。 所以，我怎麼能解決這個問題呢？ 我看見三只手。 我等了三個多。 馬庫斯，你有什麼感想？ 觀眾：好吧，如果你需要它 執行一次以上，你只是 將其更改為一個do-whil​​e循環。 JASON HIRSCHHORN：確定。 這將解決我們的問題有關係嗎？ 觀眾：在這種情況下，不因 事實上，該列表為空。 所以，那麼你可能只需要添加 聲明說，如果循環退出 那麼你必須要在年底 在列表中，此時您 只需將其插入。 JASON HIRSCHHORN：我喜歡這樣。 這是有道理的。 如果循環退出 - 因為它會在這裡返回false。 所以，如果退出循環，然後我們在 該列表的末尾，或者也許是 啟動列表中，如果有什麼的 它，這是相同的端部。 所以，現在我們要插入 這裡的東西。 那麼，如何該代碼看，馬庫斯？ 觀眾：如果你已經拿到了節點 malloced，你可以只說 new_node - >下一次等於null，因為 它必須是在末端。 或new_node - >下一個等於null。 JASON HIRSCHHORN：確定。 抱歉。 New_node - >下一個等於null 因為我們是在最後。 不把它英寸 我們如何把它在列表中？ 右。 這只是設置它等於。 沒有我們如何做實際上 把它在列表中？ 什麼是指向 列表的末尾？ 觀眾：頭。 JASON HIRSCHHORN：對不起？ 觀眾：頭指向 到該列表的末尾。 JASON HIRSCHHORN：如果有什麼的 列表中，頭是指向 列表的末尾。 所以說要工作 首先插入。 怎麼樣，如果有一對夫婦 列表中的東西呢？ 不是我們不想設置 頭等於new_node。 我們究竟想幹什麼呢？ 是嗎？ 可能是以前的。 將這項工作？ 回想一下，以前只是 一個指針指向一個節點。 和以前的是一個局部變量。 所以，這條線將設置一個局部變量， 以前，等於或 指向該新節點。 這實際上不會把它 在我們的名單，雖然。 我們如何把它在我們的名單？ Akchar？ 觀眾：我覺得你 做電流>下一個。 JASON HIRSCHHORN：確定。 CURR - >下一個。 所以，再一次，我們是下來的唯一理由 這裡是有哪些呢電流等於？ 觀眾：等於null。 JASON HIRSCHHORN：還等什麼 發生，如果我們做空 - >下一個？ 我們究竟要得到什麼？ 我們會得到一個段錯誤。 觀眾：做CURR等於null。 JASON HIRSCHHORN：這是同樣的事情 如前一個，不過，因為有 我們設置一個局部變量 等於這個新的節點。 讓我們回到我們的圖片 中插入一些東西。 說我們要插入在最後 列表中的，所以就在這裡。 我們有一個當前指針這是 指著空，以前的點 這是指向8 那麼，我們需要什麼更新，AVI？ 觀眾：上一頁 - >下一個？ JASON HIRSCHHORN：上 - >下一個是什麼 我們要更新，因為這 實際上在插入 該列表的末尾。 我們仍然有一個缺陷，不過， 那我們要碰上。 那是什麼錯誤？ 是嗎？ 觀眾：這將返回 假在這種情況下？ JASON HIRSCHHORN：哦，是的 要返回false。 但還有一個問題。 所以，我們需要把返回true。 觀眾：以前還是否相等 在列表的頂部空？ JASON HIRSCHHORN：所以以前仍 等於null在開始的時候。 那麼，如何才能克服呢？ 是嗎？ 觀眾：我覺得你可以做一個檢查 前while循環，看它是否是 一個空的列表。 JASON HIRSCHHORN：確定。 因此，讓我們去這裡。 做一個檢查。 如果 - 觀眾：所以，如果頭 等於等於null。 JASON HIRSCHHORN：如果頭 等於等於null - 這會告訴我們，如果它是一個空列表。 觀眾：然後你 做頭等於新的。 JASON HIRSCHHORN：頭 等於new_node？ 還有什麼我們需要做什麼？ 觀眾：然後你返回true。 JASON HIRSCHHORN：不太。 我們缺少的一個步驟。 觀眾：New_node未來 有指向空。 JASON HIRSCHHORN：沒錯，奧爾登。 然後我們就可以返回true。 確定。 但它仍然是一個好主意，做的事情 在列表的最後，對不對？ 好的。 我們仍然可能真正得到 到該列表的末尾。 因此，這是代碼罰款，如果我們在 列表結束，還有一些 列表中的東西呢？ 對不對？ 因為我們還有馬庫斯的想法。 我們可能會退出這個循環，因為 我們在列表的末尾。 所以，我們還是希望這 這裡的代碼了嗎？ 觀眾：是的。 JASON HIRSCHHORN：是啊。 什麼我們需要改變這？ 真的。 這聽起來不錯 大家這麼遠嗎？ 任何人有任何 - AVI，你有什麼要補充的嗎？ 觀眾：號 JASON HIRSCHHORN：確定。 因此，我們已經做了一些改動。 我們已經我們之前做這個檢查 在去為一個空列表。 因此，我們採取了一個空列表的照顧。 在這裡，我們把插入的護理 一些在列表的末尾。 因此，它似乎是這個while循環回吐 處理後事之間， 某處在列表中，如果有 在列表中的東西。 確定。 讓我們再次運行這個程序。 沒有成功。 觀眾：你沒能成功。 JASON HIRSCHHORN：哦， 我沒有做它。 好點，邁克爾。 讓我們添加鏈接的化妝。 第87行有一個錯誤。 第87行。 奧爾登，這是你給我就行了。 什麼是錯的？ 觀眾：它必須為null。 JASON HIRSCHHORN：優秀。 完全正確。 它應為null。 讓我們再次做。 編譯。 確定。 讓我們來插入三個。 該插入是成功的。 讓我們把它打印出來。 哦，如果我們能檢查。 但我們沒有這樣做的 但打印功能。 讓我們進入別的東西。 我們應該怎樣輸入？ 對象：七。 JASON HIRSCHHORN：七？ 觀眾：是的。 JASON HIRSCHHORN：我們有一個賽格故障。 因此，我們得到了一個，但我們清楚地 不能得到兩個。 它是5:07。 這樣我們就可以調試這個 三分鐘。 但我要離開這裡，我們 並移動到哈希表。 但同樣，答案這個代碼 我將通過電子郵件發送給您的一點。 我們非常接近它。 我強烈鼓勵你找出 這是怎麼回事，並解決它。 所以我會向您發送電子郵件將該代碼作為 加上良好的解決方案 - 提供可能的解決以後。 首先這個代碼。 另一件事我想我們以前做的 終點是我們還沒有釋放任何東西。 所以我想告訴你什麼 Valgrind的樣子。 如果我們運行Valgrind的邊界 在我們的節目，。/掛鉤。 再次，根據這張幻燈片，我們 應與某些類型的Valgrind的運行 選項，在這種情況 - 洩漏檢查=滿。 因此，讓我們寫的valgrind - 洩漏檢查=滿。 因此，這將運行Valgrind的 在我們的節目。 而現在的程序實際運行。 所以，我們要運行它，就像 之前，把東西英寸 我打算把三個。 這一工程。 我不會嘗試把某事 別的，因為我們要 得到在這種情況下一個段錯誤。 所以我只是要退出。 現在你看到這兒 洩漏和堆總結。 這些都是好東西， 你想看看。 因此堆匯總 - 它說，在使用 在出口 - 在一個塊中8個字節。 一個塊是 節點我們malloced。 Michael，你說一個節點是前八 叮咬，因為它具有整數 和指針。 所以這是我們的節點。 然後它說，我們使用的malloc 七次，我們釋放 東西六次。 但我們從來沒有所謂的自由，所以我沒有 知道這是什麼說什麼。 但我只想說，當你的 程序運行時，malloc的是被稱為 在其他一些地方，我們 不必擔心。 所以malloc的可能是所謂的 在一些地方。 我們並不需要擔心的地方。 但是，這真的是我們。 這第一行是我們。 我們離開了該塊。 而且你可以看到，這裡 在洩漏概要。 仍可達 - 在一個塊中8個字節。 這意味著，存儲器 - 我們已經洩露內存。 肯定丟失了 - 有些東西失去了為好。 一般來說，你不會 看不到任何東西在那裡。 仍然是可到達的地方一般 你會看到的東西，在那裡你會想 看看，看看代碼你應該 已釋放，但你忘了釋放。 然後，如果這是不是這種情況， 如果我們做了免費的一切， 我們可以檢查。 讓我們只運行程序 不把任何東西。 你會看到這兒使用在出口 - 在零塊零字節。 這意味著我們已經一無所有 當這個程序退出。 所以，在轉彎前pset6，運行Valgrind的 並確保你沒有 任何內存洩漏的程序。 如果您有Valgrind的任何問題， 隨意伸手。 但是，這是你如何使用它。 很簡單 - 看看你 有在使用中退出 - 在任何阻止任何字節。 所以，我們正在努力插入節點上。 我有其他兩個函數在這裡 - 打印節點和自由節點。 再次，這些功能是 將是對你有好處練習 因為他們會幫你不僅 這些樣品的練習，但也 關於這個問題集。 他們非常緊密映射到的東西 你將要做的 問題集。 但我想，以確保 我們接觸的一切。 和哈希表也是至關重要的 我們正在做的這節 星期 - 或在習題集。 所以，我們要完成的部分 談論哈希表。 如果您發現我犯了一個 小哈希表。 這不是我們所談論 但是，關於。 我們談論的是一個不同的 類型的哈希表。 並在其核心，一個哈希表 是不是僅此而已 陣列加一個散列函數。 我們要談的一點只是為了 確保每個人都明白一個 散列函數是。 而我現在告訴你，這是 無非兩件事 - 數組和散列函數。 和這裡的步驟，通過 而這個操作。 還有我們的數組。 還有我們的函數。 特別是，散列函數需要 做了幾件事情與此有關。 我要特別談談 關於這個問題集。 它可能會 走在一個字符串。 和什麼樣了回來？ 是什麼數據類型？ 奧爾登？ 您的散列函數返回？ 一個整數。 原來這就是散列 表由 - 在陣列形式的表 和散列函數。 它是如何工作的？ 它的工作分三個步驟。 我們給它一個關鍵。 在這種情況下，我們給它一個字符串。 我們每步1調用哈希函數 對關鍵，我們得到的一個值。 具體來說，我們會說 我們得到的整數。 該整數，也有非常具體的 限制到什麼是整數都可以。 在這個例子中，我們的陣 是大小三。 因此，可以認為整數是什麼數字。 什麼是有效值範圍 該整數，這個返回類型 散列函數？ 零，一和二。 散列函數的一點是要 找出該數組中的位置 在那裡我們的關鍵是怎麼回事。 只有三種可能 地方在這裡 - 零個，一個或兩個。 所以這個功能更好的回報 零個，一個或兩個。 此數組中一些有效的指數。 然後不同的地方返回， 你可以看到有數組開放 括弧中的值。 這就是我們把鑰匙。 所以我們扔在南瓜， 我們得到了零。 在陣列支架0，我們把南瓜。 我們扔在貓，我們走出之一。 我們把貓的之一。 我們把蜘蛛。 我們得到了兩次。 我們把蜘蛛在陣列上的兩個。 這將是很好，如果 它的工作就像那個。 但不幸的是，正如我們將看到的， 這是一個比較複雜一點。 在我們那裡，任何問題 關於這個基本 建立一個哈希表？ 這是確切的圖像 我們畫在黑板上。 但由於我們畫在黑板上，我 我不打算再進入它。 從本質上講鍵，神奇的黑盒子 - 或者在這種情況下，深青色盒 - 一個 散列函數把它們放在水桶。 而在這個例子中，我們是 不把這個名字。 我們把相關的電話 名稱中的桶數。 但你很可能只是 把名字中的水桶。 這是什麼只是一個圖片 我們畫在黑板上。 我們有潛在的隱患，雖然。 而且有兩個特別 幻燈片，我想去過。 第一個是對 散列函數。 所以我問的問題，什麼 做一個好的哈希函數？ 我給出兩個答案。 首先是它的確定性。 在哈希函數的情況下， 這是什麼意思？ 是嗎？ 觀眾：它可以找到 指數在常數時間？ JASON HIRSCHHORN：那 是不是這個意思。 但是這是一個很好的猜測。 別人有一個猜想 到這意味著什麼？ 一個好的哈希函數 是確定的？ 安妮？ 觀眾：那一個鍵只能映射 哈希表在同一個地方。 JASON HIRSCHHORN：這是 完全正確。 每當你把南瓜， 它總是返回零。 如果你把南瓜和您的散列 函數返回零，但有一個 返回的東西概率 其他大於零 - 所以也許它可以返回人們有時 或其他兩次 - 這不是一個好的哈希函數。 你說得對。 您的散列函數應該返回 完全相同的整數，在這種情況下，為 完全相同的字符串。 也許它會返回完全相同的整數 對於完全相同的字符串 不分大小寫的。 但在這種情況下，它仍然 確定性，因為多東西 被映射到相同的值。 這很好。 只要僅有一個 輸出對於一個給定的輸入。 確定。 第二件事是，它 返回的有效索引。 我們長大了前面。 該散列函數 - 男孩哦 - 散列函數應該 返回的有效索引。 所以說 - 讓我們回到這個例子。 我的散列函數計數 字母的單詞。 這就是散列函數。 並返回該整數。 所以，如果我有A字，它的 要返回之一。 並且它會放一個就在這裡。 如果我把這個詞蝙蝠？ 這將返回三個。 哪裡蝙蝠去了？ 它不適合。 但它需要去的地方。 這是我的哈希表畢竟，和 一切都需要去的地方。 那麼，應該蝙蝠去了？ 有什麼想法？ 猜測？ 良好的猜測？ 對象：零。 JASON HIRSCHHORN：為什麼零？ 觀眾：因為3 模三是零？ JASON HIRSCHHORN：三 模3是零。 這是一個偉大的猜想， 這就是正確的。 因此，在這種情況下，它應該 大概走為零。 所以一個好的方法，以確保此哈希 函數只返回有效索引的 由該表的大小以模它。 如果通過模本的任何回報 3，你總是會得到 零個，一個，和2之間的東西。 如果這個總是返回七人， 你總是模三個人，你是 總是會得到同樣的事情。 所以它仍然確定性 如果你取模。 但是，這將確保您 從來沒有得到的東西 - 無效的行業。 通常，模應該發生 您的哈希函數裡面。 所以，你不必擔心這一點。 你只要能保證 這是一個有效的指數。 這方面的問題 潛在的缺陷？ 確定。 我們在那裡去。 下一個潛在的缺陷，並 這是大的。 如果哪兩個鍵地圖 為相同的值？ 因此，有兩種方法來處理這個問題。 第一個被稱為線性 探測時，我敢 不打算走了過來。 但是你應該熟悉如何 的作品，這是什麼。 第二個我打算走了過來 因為這是一個多 人們可能會最終決定 在他們的問題集中使用。 當然，你不必。 但對於習題集，很多人 傾向於選擇創建一個哈希表 有獨立的鏈接來實現 他們的字典。 所以，我們要投奔這是什麼意思 創建一個哈希表 單獨的鏈接。 所以我把南瓜。 它返回零。 我把南瓜在這裡。 然後我把 - 什麼是另一個萬聖節為主題的東西嗎？ 觀眾：糖果。 JASON HIRSCHHORN：糖果！ 這是一個偉大的。 我把糖果和糖果 也使我為零。 我該怎麼辦？ 任何想法？ 因為那種大家都知道 什麼單獨的鏈接是。 因此，任何想法怎麼辦？ 是啊。 觀眾：把字符串 實際上哈希表中。 JASON HIRSCHHORN：所以我們要 繪製好主意在這裡。 確定。 觀眾：有哈希表 [聽不清] 指向指針 一個列表的開頭。 然後有南瓜是第一值 在鍊錶和糖果是 在該鍊錶中的第二個值。 JASON HIRSCHHORN：確定。 馬庫斯，這是優秀的。 我要打破下來。 馬庫斯是說不要 覆蓋南瓜。 這將是壞。 不要把糖果別的地方。 我們打算把兩者為零。 但我們要處理 這使他們由零 創建列表為零。 我們要創建的列表 一切映射到零。 我們學會了創造的最佳方式 可以增長和收縮的清單 動態不在 另一個數組。 所以不是一個多維數組。 但只創建一個鍊錶。 那麼，他提出 - 我會得到一個新的 - 是創建一個指針數組， 的指針數組。 確定。 任何想法或暗示的是什麼類型的 這個指針應該是什麼？ 馬庫斯？ 觀眾：指針來 - JASON HIRSCHHORN：因為你 說一個鍊錶，所以 - 觀眾：節點的指針？ JASON HIRSCHHORN：節點的指針。 如果東西在我們的鏈接 列表是節點，那麼他們 應該是節點的指針。 又哪裡等於最初？ 觀眾：空。 JASON HIRSCHHORN：無。 所以這是我們的空的東西。 南瓜返回零。 我們該怎麼辦？ 通過它走我嗎？ 其實，馬庫斯已經給了我。 別人走我走過它。 我們做什麼，當我們 - 這看起來非常相似， 我們只是在做。 阿維。 觀眾：我要去參加一個猜測。 所以，當你得到糖果。 JASON HIRSCHHORN：是啊。 好了，我們得到了南瓜。 讓我們得到我們的第一個。 我們得到了南瓜。 觀眾：確定。 南瓜返回零。 所以你把它放在那。 或者實際上，你把它 在鍊錶。 JASON HIRSCHHORN：我們如何 把它放在鍊錶？ 觀眾：呵呵，實際的語法？ JASON HIRSCHHORN：只是走 - 多說了。 我們該怎麼辦？ 觀眾：你剛才插入 它作為第一個節點。 JASON HIRSCHHORN：確定。 因此，我們有我們的節點，南瓜。 現在我怎麼插入？ 觀眾：你分配 它的指針。 JASON HIRSCHHORN：哪個指標？ 觀眾：零指針。 JASON HIRSCHHORN：那麼， 確實這一點呢？ 觀眾：為NULL現在。 JASON HIRSCHHORN：嗯， 它指向空。 但我把南瓜。 那麼，它應該指向？ 觀眾：南瓜。 JASON HIRSCHHORN：南瓜。 沒錯。 所以這個指向南瓜。 並在執行此指針 在南瓜呢？ 至 觀眾：空。 JASON HIRSCHHORN：為NULL。 沒錯。 所以我們剛才插入的東西 成該鏈接的表。 我們只是寫了這個代碼來做到這一點。 幾乎我們幾乎得到了它 完全破解。 現在我們插入的糖果。 我們的糖果也變為零。 所以，我們做糖果什麼？ 觀眾：這取決於是否 不是我們試圖對它進行排序。 JASON HIRSCHHORN：這是 完全正確。 這取決於是否不 我們正在試圖對它進行排序。 讓我們假設我們不是 要排序。 觀眾：那麼，正如我們所討論 之前，它最簡單的只是把它 在一開始使指針 從零點到糖果。 JASON HIRSCHHORN：確定。 堅持住。 我創建的糖果就在這裡。 所以這個指針 - 觀眾：是啊，現在應該 是指向糖果。 再有從指針 糖果點南瓜。 JASON HIRSCHHORN：像這樣？ 並說我們得到了另一個 東西映射到零？ 觀眾：嗯，你只是 做同樣的事情？ JASON HIRSCHHORN：做同樣的事情。 所以在這種情況下，如果不 要保持它整理了 聽起來相當簡單。 我們帶指針的指數 我們的哈希函數由下式給出。 我們有一點我們的新節點。 然後不管它是指向 以前 - 在這種情況下空，在 第二種情況南瓜 - ，不管它的指向 以前，我們添加到下一個的 我們的新節點。 我們要插入一些 在開始。 事實上，這是不是簡單多了 試圖保持列表排序。 但同樣，搜索會 更複雜的在這裡。 我們總是要走到最後。 確定。 關於單獨的鏈接有問題嗎？ 該怎麼做？ 請立即問他們。 我真的想確保你的所有 明白這一點之前，我們把頭伸出。 觀眾：你為什麼把南瓜 和糖果到相同的 哈希表的一部分？ JASON HIRSCHHORN：好問題。 為什麼我們把它們放在同一個 哈希表的一部分？ 那麼，在這種情況下，我們的散列函數 返回零為他們兩個。 因此，他們需要去的指數為零 因為這就是我們要 找他們，如果我們曾經 想看看他們。 再次，用線性探測方法 我們不會把他們兩個零。 但在不同的鏈方法， 我們打算把他們兩個零 然後創建一個列表銷為零。 我們不希望覆蓋南瓜 只是對於因為那時我們將 假設是南瓜 從來沒有插入。 如果我們只是一味地一件事在 這將是壞的位置。 那麼就沒有 我們曾經的機會 - 如果我們曾經有一個重複的，那麼我們 只會抹掉我們的初始值。 所以這就是為什麼我們這樣做的方法。 或者，這就是為什麼我們選擇了 - 但同樣，我們 選擇了不同的鏈接方式， 它還有許多其他的方法 人們可以選擇。 這是否回答你的問題？ 確定。 卡洛斯。 線性探測將涉及 - 如果我們發現了一個碰撞為零，我們 看起來在一個景點，看是否 它是開放的，並把它放在那裡。 然後我們來看看在未來的體育和 看看是否是公開的，把它放在那裡。 因此，我們發現下一個可用的 開放式現場，把它放在那裡。 還有沒有其他問題？ 是啊，AVI。 觀眾：作為一個跟進的是， 你是什​​麼下一個景點是什麼意思？ 在哈希表或鍊錶。 JASON HIRSCHHORN：對於線性 編程，無鍊錶。 哈希表上的下一個點。 觀眾：確定。 因此，哈希表會 初始化為大小 - 像串數 你被插入？ JASON HIRSCHHORN：你會 希望它是真正的大。 是。 這裡就是我們的圖片 只是畫在黑板上。 再次，我們有一個碰撞就在這裡。 在152。 你會看到我們創建 鍊錶關閉它。 再次，哈希表單獨鏈接 做法是不是你 要為設置問題 6不過是一個很多 學生傾向於採取。 所以，關於這一點，讓我們簡要談 之前，我們把頭伸出約問題6， 然後我會跟大家分享一個故事。 我們有三分鐘。 問題組六。 你有四個功能 - 負載，檢查，尺寸和卸載。 負載 - 好了，我們已經去 過載剛才。 我們畫了負載在黑板上。 我們甚至開始編碼了很多 插入一個鍊錶。 所以負載不大於多 我們剛才一直在做。 入住的是，一旦你有 裝的東西。 這是相同的過程，因為這。 在那裡你把相同的前兩部分 事到哈希函數 並獲得其值。 但是現在我們還沒有插入。 現在，我們正在尋找它。 我的示例代碼寫的尋找 東西在一個鍊錶。 我鼓勵你練習了。 但直覺發現的東西是 非常類似於插入的東西。 事實上，我們發現畫的圖片 東西在一個鍊錶，移動 通過直到你到了年底。 如果你到了結束，不能 找到它，那麼它不存在。 所以這是支票，基本上。 下一個是大小。 讓我們跳過大小。 最後，你已經卸載。 卸載是我們還沒有得出 在董事會或編碼呢。 但我鼓勵你去嘗試它的編碼 在我們的樣本鍊錶的例子。 但直覺上卸載 類似於自由 - 或者我的意思是類似的檢查。 除了現在每次你要時間 通過，你不能簡單地檢查， 看看你是否有你的價值在那裡。 但你服用的節點， 釋放它，基本上。 這就是卸載要求你這樣做。 免費一切你malloced。 所以，你經歷了整個名單 再次，要通過整個哈希 表一次。 這個時候不檢查 看看那裡的東西。 剛解放那裡的東西。 終於大小。 大小應該得到實施。 如果不實現規模 - 我會說像這樣。 如果你沒有在完全相同實現規模 一行代碼，包括 return語句，你是 不正確地做大小。 因此，請確保大小，完整的設計 點，你做的只有一個 行代碼，其中包括 return語句。 並且不收拾然而，Akchar。 做事勤奮。 我想說謝謝你們 前來部分。 有一個快樂的萬聖節。 這是我的服裝。 我會在週四穿著這 如果我看到你在上班時間。 如果您想了解更多一些 背景為這件衣服，覺得 免費檢查出2011條 關於為什麼我一個故事 穿著南瓜服裝。 它是一個悲傷的故事。 所以一定要確保你有 附近的一些組織。 但是，如果您有任何 的問題，我會堅持圍繞 後段之外。 祝你好運問題組六。 和往常一樣，如果您有任何 的問題，讓我知道。