>> 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條 關於為什麼我一個故事
穿著南瓜服裝。
它是一個悲傷的故事。
所以一定要確保你有 附近的一些組織。
但是，如果您有任何 的問題，我會堅持圍繞
後段之外。
祝你好運問題組六。
和往常一樣，如果您有任何 的問題，讓我知道。