>> [音樂播放]
>> DOUG LLOYD：好，因此在 這一點在使用過程中，
我們已經介紹了很多C的基礎知識 我們知道了很多關於變量，數組，
指針，所有的好東西。
排序的所有這些都是建立 在看到的基本面，
但我們可以做更多的，對不對？
我們可以結合東西 一起以有趣的方式。
>> 因此，讓我們做的是，讓我們開始 另闢蹊徑的什麼C給我們，
並開始創建自己的數據 利用這些建築結構
塊一起做一些事情 真正有價值的，有用的。
我們能做到這一點的方法之一是 談收藏。
因此，到目前為止，我們已經有某一種數據 結構較集合
對喜歡價值觀，相似的價值觀。
這將是一個數組。
我們有一個整數集合或 字符等的集合。
>> 的結構也進行排序數據的 結構收集信息，
但它不是用來收集類似的值。
它通常混合了不同的數據類型 一起在單一盒子。
但它本身並不是 用於鏈接在一起
或者連接到一起類似 項，如一個數組。
數組是偉大的 元素查找，但召回
這是非常困難 插入到一個數組，
除非我們插入的 該數組的末尾。
>> 而最好的例子，我有 因為這是插入排序。
如果你還記得我們的視頻 在插入排序，
有很多的 參與其費用
拿起元素，將它們轉移 出適合的東西的方式
成陣列的中間。
陣列也從另一個患 問題，這是不靈活。
當我們聲明一個數組， 我們這一次機會吧。
我們得到的說法，我想 這些元素。
可能是100，它可能 是1000，它可能
是x，其中x是一個數字，用戶 給了我們一個提示，或在命令
行。
>> 但是，我們只有一次機會吧，我們 沒有得到，然後說，哦，其實我
需要101，或者我需要X加20。
太晚了，我們已經宣布了 數組，如果我們想要獲得101或x
加上20，我們要聲明 一個完全不同的陣列，
複製數組中的所有元素 過來，然後我們有足夠。
而如果我們又錯了，是什麼 如果我們真的需要102或x加40，
我們要再次做到這一點。
因此，他們非常不靈活 對於調整我們的數據，
但如果我們結合在一起的一些 我們已經已經基本知識
了解指針和結構， 特別是使用動態存儲
分配使用malloc，我們 可以把這些碎片拼湊起來
創建一個新的數據結構 - 一個 單鍊錶，我們可能say--
這使我們能夠成長， 收縮值的集合
我們不會有任何浪費的空間。
>> 所以，再一次，我們稱這樣的想法， 這個概念，一個鍊錶。
特別是，在這個視頻我們 談到單向鍊錶，
然後另一個視頻中，我們將討論 關於雙向鍊錶，這
只是在這裡一個主題的變化。
但一個單向鍊錶 由節點，
節點僅僅是一個抽象的term-- 這只是一些我打電話
這是一種 結構，基本上，我？
只是要稱之為node--，這 節點具有兩個構件，或兩個字段。
它的數據，通常是一個 整數，字符浮子，
或者可以是某種其他數據類型 您已經定義了類型定義。
它包含一個指向 相同類型的另一節點。
>> 因此，我們有兩件事情裡面 這個節點，數據和指針
到另一個節點。
如果你開始顯現 這一點，你可以考慮一下
像鏈節點的那 連接在一起。
我們的第一個節點，它 包含數據，和一個指針
到第二個節點，其中包含 數據，和一個指針到該第三節點。
所以這就是為什麼我們稱它為 鏈接列表，它們鏈接在一起。
>> 這是什麼特別的 節點結構是什麼樣子？
好吧，如果你從我們的視頻回憶 定義自定義類型，類型高清，
我們可以定義一個結構 - 和 鍵入這樣定義的結構。
tyepdef結構sllist，然後我 使用這個詞的價值在這裡隨意
以指示真的任何數據類型。
你可以傳遞一個整數或浮點數， 你可以有一切你想要的。
它不再僅僅限於 整數，或者類似的東西。
因此，值是任意 數據類型，然後一個指針
到同一類型的另一節點。
>> 現在，有一個小抓 這裡定義的結構
當它是一個自我參照結構。
我必須有一個臨時的 命名為我的結構。
在這一天我的結束 顯然想將它命名
SLL節點，這是最終的新 名字我喜歡的類型定義的一部分，
但我不能使用SLL節點 在這中間。
是的原因，我沒有 創建了一個名為類型SLL節點
直到我在這裡打這個最後一點。
直到這一點，我必須有 另一種方式來參考此數據類型。
>> 而這是一個自 參照數據類型。
它; S的一個數據類型 結構，它包含一個數據，
和一個指針到另一個 相同類型的結構。
所以，我需要能夠引用 這種數據類型至少暫時
所以給它一個暫時的 結構sllist名
讓我那麼說我想要一個 指向另一個結構sllist，
一個結構sllist明星，然後 我已經完成了定義後，
我現在可以把這種類型的SLL節點。
>> 所以這就是為什麼你看到有 一個臨時的名字在這裡，
但這裡的永久名字。
有時候，你可能會看到 結構的定義，
例如，是不 自我指涉，是
沒有說明的名字在這裡。
它只想說typedef結構， 打開大括號，然後定義它。
但是，如果你是結構是自 引用，因為這個人是，
你需要指定一個 臨時類型名稱。
但最終，現在 我們已經做到了這一點，
我們只能參考 這些節點，這些單位，
作為目的SLL節點 這段視頻的其餘部分。
>> 好吧，讓我們知道如何 創建一個鏈接列表節點。
我們知道如何定義 一個鏈接列表節點。
現在，如果我們要開始 用它們來收集信息，
有一對夫婦經營的我們 需要了解和使用。
我們需要知道如何創建 鍊錶憑空。
如果沒有清單已經， 我們要開始的。
因此，我們需要能夠 以創建一個鍊錶，
我們需要大概搜索 通過鏈接列表
找到我們正在尋找的元素。
我們需要的是能夠插入 新事物進入榜單，
我們希望我們的名單能夠成長。
同樣，我們希望能夠 從我們的名單中刪除的東西，
我們希望我們的名單，以便能夠收縮。
而在年底我們 計劃，特別是
如果你還記得，我們​​是 動態分配內存
以通常建這些列表， 我們要釋放所有的內存
當我們用它做的工作。
因此，我們需要能夠刪除一個 整個鍊錶在一個失敗的一舉。
因此，讓我們通過 某些操作
和我們怎樣才能使其可視化， 在偽代碼說話特別。
因此，我們要創建一個 鍊錶，所以也許我們
要定義一個函數 這個原型。
SLL節點明星，創造，而我路過 在一個參數，一些任意數據
再次鍵入某些任意數據類型的，。
但是我returning--這個功能應該 還給我一個指針，以一個單
鏈接列表節點。
同樣，我們正在努力創造 鍊錶憑空，
所以我需要一個指針 當我做了該名單。
>> 那麼，什麼是這裡涉及的步驟？
好了，第一件事我 要做的是動態
分配空間用於新的節點。
同樣，我們正在創造出來的薄 空氣中，所以我們需要為它的malloc空間。
當然，馬上 我們的malloc後，
我們經常檢查，以確保我們的 pointer--我們沒有得到回空。
因為如果我們嘗試 尊重一個空指針，
我們要遭受 段錯誤，我們不希望出現這種情況。
>> 然後，我們要填補該領域， 我們要初始化值字段
並初始化下一字段。
然後我們想用於：最終的 函數原型indicates--我們要
的指針返回到SLL節點。
那麼是什麼讓這個樣子視覺？
嗯，首先我們要動態地 分配空間用於新SLL節點，
所以我們malloc--這 視覺表示
節點，我們剛剛創建。
我們檢查，以確保 它不是null--在這種情況下，
畫面不會有 示，如果它為空，
我們會耗盡內存， 所以我們好去那裡。
所以，現在我們是在步驟C， 初始化節點值字段​​。
那麼，在此基礎上功能 叫我用在這裡，
貌似我想通過在6， 所以我會在值字段6。
現在，初始化下一個字段。
好了，我該怎麼辦那裡， 旁邊有個什麼吧，
這是在列表中的唯一事情。
那麼什麼是列表中，接下來的事情？
>> 它不應該指向什麼，對吧。
還有沒有別的那裡，所以有什麼 我們知道，這一概念的nothing--
指向什麼？
它應該是，也許我們要 把一個空指針出現，
我會代表空 指針只是一個紅盒子，
我們不能再往前走。
正如我們將看到一個小以後， 我們將有最終鏈
箭頭連接 這些節點一起，
但是當你打的 紅色的框，這就是空，
我們不能再往前走， 這是該列表的末尾。
>> 最後，我們只是想 返回一個指向該節點。
因此，我們會打電話給它新的， 並返回新
因此它可被用 無論函數創建它。
所以我們去，我們已經創建了一個單 鍊錶節點無中生有，
現在我們有了一個可以使用的列表。
>> 現在，讓我們說，我們已經 有大型連鎖，
我們要找到的東西在裡面。
我們希望有一個功能是怎麼回事 返回true或false，這取決於
在該列表中是否存在某個值。
函數原型，或 聲明該函數，
可能看起來像this-- BOOL發現，和 那麼我們想傳遞的兩個參數。
>> 第一，是一個指針，指向 該鏈接的表的第一個元素。
這實際上是你會 總想跟踪，
實際上可能是東西， 你甚至放在一個全局變量。
一旦你創建一個列表， 你永遠，永遠
要保持的非常軌跡 列表的第一個元素。
這樣，你可以參考其他所有 只是簡單地跟著鏈條元素，
無需保持指針 完整的每一個元素。
你只需要跟踪第一 一個，如果他們都鏈接在一起。
>> 然後是第二件事 我們傳遞再次
是任意some-- 我們的任何數據類型
尋找有內 希望列表中的節點之一。
那麼哪些步驟？
好了，我們做的第一件事是 我們創建了一個橫向的指針
指向列表頭部。
那麼，為什麼我們這樣做，我們已經 有一個指針在表頭，
為什麼我們不只是移動了一繞？
嗯，就像我剛才說的， 這對我們來說真的很重要
要始終保持軌道的 列表中的第一個元素。
所以它實際上更好 創建一個副本，
並用它來從不左右移動，所以我們 意外離開，否則我們永遠
有一個指針在某些時候是 右邊上的列表中的第一個元素。
因此，它是最好創建一個 我們使用移動第二個。
>> 然後，我們只是比較是否 在該節點的值字段
就是我們正在尋找的東西，如果它是 不，我們只是移動到下一個節點。
我們繼續這樣做， 過來，過來，過來，
直到我們要么找到 元素，或者我們打
null--我們已經走到了盡頭 列表，它是不存在的。
這應該有希望打鈴 你剛才線性搜索，
我們只是複製它 一個單向鍊錶結構
代替使用一個陣列，以做到這一點。
>> 所以這裡有一個例子 一個單向鍊錶。
這其中包括 五個節點，我們有
一個指針的頭 列表中，這就是所謂的列表。
我們要做的第一件事就是 再次，創建遍歷指針。
所以，我們現在兩個指針 這點同樣的事情。
>> 現在，請注意這裡。此外，我也沒 必須對malloc的TRAV任何空間。
我並沒有說TRAV等於的malloc 東西時，該節點已經存在，
在內存空間已經存在。
因此，所有我實際上做的是 創建另一個指針。
我不是mallocing額外 空間，只是現在的兩個指針
指向同樣的事情。
>> 所以是2我在找什麼？
哦，不，所以不是我 將移動到下一個。
所以基本上我會說， TRAV等於TRAV旁邊。
3我在尋找什麼，沒有。
所以，我繼續走 通過，直到最後
到6這就是我要找 用於基於所述函數調用
我在上面 在那裡，所以我做了。
>> 現在，如果元件我什麼 尋找的是不在列表中，
難道還要去上班？
好了，注意到列表 這裡是微妙的不同，
這是另一件事是 用鍊錶重要的，
不必保留 它們在任何特定的順序。
你可以，如果你想要的，但 你可能已經注意到了
我們不是跟踪 我們是在什麼數量的元素。
>> 這就是那種一筆交易中，我們 有鍊錶節陣列，
難道我們沒有 隨機訪問了。
我們不能只是說，我想 去第0個元素，
或者我的數組的第6元， 我可以在一個陣列做。
我不能說我想去的 第0個元素，或者第6元，
或我的鍊錶25元件， 有沒有與之相關的索引。
因此它並不真正的問題 如果我們保留以我們的名單。
如果你想你 當然可以，但有
沒有理由，他們需要 以任何順序被保留。
如此反复，讓我們試著 在此列表中發現6。
好了，我們開始在 開始，我們沒有發現6，
然後我們繼續沒有找到 6，直到我們最終到達這裡。
所以現在TRAV指向節點 含有8，和六不在那裡。
>> 因此，下一步將是 去下一個指針，
所以說TRAV等於TRAV旁邊。
好了，接下來TRAV，以表示 紅色框出現，為空。
因此，有無處可 走，所以在這一點
我們可以得出結論，我們已經達到 鍊錶的末尾，
和圖6是不是在那裡。
並且將它返回 假在這種情況下。
>> 好了，我們怎麼插入一個新的 節點插入到鍊錶？
因此，我們已經能夠創造 鍊錶從哪兒冒出來，
但我們可能要 建立一個鏈條，而不是
創建一批獨特的名單。
我們希望有一列表 有一堆在它的節點，
不是一堆列表與單個節點。
因此，我們不能只是一味地使用Create 功能我們前面定義的，現在我們
要插入到一個 已經存在列表。
>> 所以這種情況下，我們將 傳入兩個參數，
指針的頭部 鍊錶，我們要添加到。
再次，這就是為什麼它是如此 重要的是，我們始終
跟踪它，因為 這是我們唯一的辦法真的
不得不指整個列表是 剛剛通過的指針的第一個元素。
因此，我們要傳遞一個 指針，該第一元件，
和任何價值，我們 要添加到列表中。
而最終這個功能 是否會返回一個指針
到鍊錶的新掌門人。
>> 什麼是這裡涉及的步驟？
好了，就像創建， 我們需要動態分配
一個新的節點空間，並進行檢查，以 確保我們不會耗盡內存，再一次，
因為我們使用的malloc。
然後，我們要填充 並插入節點，
所以放多少，什麼 val為，到節點。
我們要在插入節點 鍊錶的開頭。
>> 還有一個原因是我 要做到這一點，它
可能是值得考慮第二 在這裡暫停視頻，
想想我為什麼會想 在插入一個鏈接開始
名單。
再次，我前面提到的 它並沒有真正
的問題，如果我們在任何保護它 順序，所以也許這是一個線索。
而你看到的，如果我們會發生什麼 想用於：或者只是第二
以前，當我們打算 通過搜索你
可以看到什麼可能 發生，如果我們試圖
插入在列表的末尾。
因為我們沒有一個 指針的列表的末尾。
>> 因此原因，我想 插入開頭，
是因為我可以馬上做到這一點。
我有一個指針指向開始， 我們將看到這一場視覺在第二。
但是，如果我想插入底， 我要從頭開始，
遍歷所有的方式向 到底，然後把它釘住。
因此，這將意味著 在列表的末尾插入
將成為n的Ø 操作時，要回
我們的討論 計算複雜性。
它會變成n操作，其中的鄰 作為列表越來越大，大，
大，它會變得越來越 更難以粘性的東西
上在末端。
但它總是很容易 釘東西之初，
你總是在開頭。
>> 我們將看到一個可視化的這個了。
然後，一旦我們完成了，一旦 我們插入新的節點，
我們希望我們的指針返回 鍊錶新的頭，這
因為我們要插入在 開始，居然會
一個指向我們剛剛創建的節點。
讓我們想像這一點， 因為我認為這將幫助。
>> 因此，這裡是我們的名單，它由 四個元素，一個節點含有15，
它指向一個節點 含有9，其
指向包含13的節點， 指向包含一個節點
10，它具有空 指針作為其下一個指針
所以這是該列表的末尾。
因此，我們要插入一個 用價值12新節點
在這個初 列表中，我們怎麼辦？
嗯，首先，我們的malloc空間的 節點，然後我們把12在那裡。
>> 所以，現在我們已經到了一個 決策點，對不對？
我們有幾個 指針，我們可以
移動，哪一個應該我們搬進去？
我們應該做出12點 列表中 - 新掌門
或不好意思，我們應該讓12 指向老首長的名單？
或者我們應該說， 列表現在開始在12。
有一個區別 在那裡，我們將看看
在與兩國在第二會發生什麼。
>> 但是這將導致一個 對於側邊欄很大的話題，
這是一個的 用鍊錶最棘手的事情
被安排指針 以正確的順序。
如果你搬東西壞了， 你可以結束了意外
孤兒列表的其餘部分。
這裡是一個很好的例子。
所以，讓我們的想法of-- 好了，我們已經創建了12。
我們知道，12將是 列表中的新掌門人，
所以我們為什麼不正義之舉 該列表指針指向那裡。
>> 好了，這是很好的。
所以，現在在那裡做12下一個點？
我的意思是，在視覺上我們可以看到 它將指向15，
作為人類，它真的很明顯給我們。
計算機如何知道的？
我們沒有任何東西 指著15了，對不對？
>> 我們已經失去了任何參考15的能力。
我們不能說新的箭頭旁邊的equals 什麼東西，有什麼也沒有。
事實上，我們已經成為孤兒 列表的其餘
通過這樣做，我們已經 不小心打破了鏈條。
我們當然不希望這樣做。
>> 因此，讓我們回去再試試這個。
也許做正確的事 是設置12的下一個指針
到舊頭部列表的第一， 那麼我們可以將名單上。
而事實上，是這樣的 正確的順序我們
需要遵循當我們 正與單向鍊錶。
我們總是希望連接 新元素到列表中，
之前，我們需要的那種 改變的重要一步
其中鍊錶的頭。
再次，這是這樣一個根本的東西， 我們不想失去它的軌道。
>> 所以我們要確保 一切都鏈接在一起，
我們繼續之前的指針。
所以，這將是正確的順序， 這是連接12到列表中，
然後說，該清單啟動12。
如果我們所說的名單開始在12和 然後試圖連接12到列表中，
我們已經看到發生了什麼。
我們失去了對列表進行的錯誤。
>> 好了，還有一件事談。
如果我們要擺脫什麼 整個鍊錶一次？
同樣，我們mallocing 這一切的空間，所以我們
需要釋放它的時候，我們就大功告成了。
所以，現在我們想刪除 整個鍊錶。
那麼，我們要怎麼辦？
>> 如果我們已經達到了空指針，我們 想停下來，否則，只是刪除
該列表的其餘部分，然後讓我自由。
刪除列表的其餘部分， 然後釋放當前節點。
這是什麼聲音一樣， 有什麼技術，我們聊
有關以前這聽起來像不像？
刪除其他人，然後 回來並刪除了我。
>> 這是遞歸的，我們所做的 問題稍微小了一點，
我們說每個人都刪除 否則的話，你可以刪除我。
而進一步下跌的道路，節點 會說，否則刪除每一個人。
但最終，我們會得到的 點的列表為空，
這就是我們的基本情況。
>> 因此，讓我們來看看這個， 以及這可能會奏效。
因此，這裡是我們的名單，這是相同的 列出我們只是在談論，
這裡面的步驟。
有大量的文字在這裡，但 希望可視化將幫助。
>> 因此，我們have--，我還拉 我們的堆棧幀圖
從我們的視頻調用棧， 並希望這一切
同時會告訴你這是怎麼回事。
因此，這裡是我們的偽代碼。
如果我們到達空 指針，停止，否則，
刪除列表的其餘部分， 然後釋放當前節點。
所以，現在，列表中 - 我們是指針
傳遞摧毀點至12。
12不是一個空指針，所以我們 要刪除列表的其餘部分。
>> 什麼是刪除 我們剩下的參與？
嗯，這意味著製作 呼籲摧毀，說
即圖15是的開頭 其餘的，我們要摧毀名單。
這樣一來，呼籲銷毀 12是種擱置。
它凍結在那裡，等待 呼籲摧毀15，完成其工作。
>> 好了，15不是一個空指針， 所以它會說，沒事，
同時，刪除列表的其餘部分。
列表的其餘部分開始 9，所以我們只
等到你刪除所有 的東西，然後回來，並刪除了我。
那麼9會說，好吧， 我不是一個空指針，
所以從這裡刪除其餘的名單。
所以盡量和銷毀13。
13說，我不是空指針， 同樣的事情，它通過降壓。
10不是空指針，10 包含一個空指針，
但10本身不是一個 空指針現在，
因此它通過降壓太。
>> 現在列出點那裡， 真正將指向some--
如果我的形象有更多的空間， 它會指向一些隨機的空間
我們不知道它是什麼。
這是空指針雖然名單 簡直是現在設置它的值空。
它指向正確的紅色方框內。
我們達到了一個空指針，所以 我們可以停下來，我們就大功告成了。
>> 所以那紫色幀now--在 stack--的頂部是這樣的活動框架，
但它的完成。
如果我們已經達到了一個空指針，停止。
我們沒有做任何事情，我們 無法釋放空指針，
我們沒有任何的malloc 空間，所以我們就大功告成了。
這樣功能框架 被破壞，並且我們
resume--我們拿起我們離開 關具有下一最高一個，這
這是深藍色的框在這裡。
於是我們拿起身在何方，我們不放過。
我們刪除的休息 列表了，所以現在我們
要釋放當前節點。
所以，現在我們可以免費這個節點，現在 我們已經達到了函數的結束。
而這樣的功能框架被破壞， 我們拿起在淺藍色的。
>> 因此，says--我已經done-- 刪除列表的其餘部分，所以
釋放當前節點。
而現在的黃色框為 回堆棧的頂部。
所以你看，我們現在是 從右破壞列表中離開了。
>> 會發生什麼，不過， 如果我們做事情的方法不對？
就像當我們試圖 添加元素。
如果我們搞砸鏈，如果 我們沒有連接的指針
以正確的順序，如果我們 剛剛釋放的第一個元素，
如果我們只是釋放了 頭列表，現在我們
沒有辦法參考 列表的其餘部分。
因此，我們將有 孤立的一切，
我們將不得不什麼 所謂的內存洩漏。
如果您從我們的視頻回憶 動態內存分配，
這不是很好的事情。
>> 因此，正如我所說， 有幾個操作
我們需要用工作 與有效鍊錶。
你可能已經注意到我省略之一， 從鏈接中刪除一個單個元件
名單。
我這樣做的原因 是它是一種實際
棘手思考如何刪除 從一個單獨的單個元件
鍊錶。
我們需要能夠跳過 一些在列表中，這
意味著我們得到一個point--我們 要刪除這node--
但為了使其所以我們 不會丟失任何信息，
我們需要連接這 節點在這裡，在這裡。
>> 所以我大概那個做錯了 從視覺角度。
因此，我們在一開始，我們 列表中，我們正在著手通過，
我們要刪除此節點。
如果我們只是將其刪除， 我們已經打破了鏈條。
這個節點就在這裡 指的是一切，
它包含從這裡掉了鍊子。
>> 因此，我們需要做的其實 之後，我們到了這一點，
是我們需要退一步之一， 在連接這個節點，這個節點，
所以我們可以再刪除 一個在中間。
但單鍊錶不 為我們提供了一種倒退。
因此，我們需要可以保持 兩個指針，然後將它們移動
一前一後的排序斷步驟， 另外，因為我們去，或者到一個地步
然後通過發送另一個指針。
正如你所看到的， 可以變得有些混亂。
幸運的是，我們有 另一種方式來解決，
當我們談論雙向鍊錶。
>> 我是道格·勞埃德，這是CS50。