1 00:00:00,000 --> 00:00:02,832 >> [音樂播放] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD:好,因此在 這一點在使用過程中, 4 00:00:08,560 --> 00:00:15,300 我們已經介紹了很多C的基礎知識 我們知道了很多關於變量,數組, 5 00:00:15,300 --> 00:00:17,610 指針,所有的好東西。 6 00:00:17,610 --> 00:00:21,610 排序的所有這些都是建立 在看到的基本面, 7 00:00:21,610 --> 00:00:23,880 但我們可以做更多的,對不對? 8 00:00:23,880 --> 00:00:27,930 我們可以結合東西 一起以有趣的方式。 9 00:00:27,930 --> 00:00:31,010 >> 因此,讓我們做的是,讓我們開始 另闢蹊徑的什麼C給我們, 10 00:00:31,010 --> 00:00:35,270 並開始創建自己的數據 利用這些建築結構 11 00:00:35,270 --> 00:00:40,590 塊一起做一些事情 真正有價值的,有用的。 12 00:00:40,590 --> 00:00:43,420 我們能做到這一點的方法之一是 談收藏。 13 00:00:43,420 --> 00:00:48,360 因此,到目前為止,我們已經有某一種數據 結構較集合 14 00:00:48,360 --> 00:00:51,030 對喜歡價值觀,相似的價值觀。 15 00:00:51,030 --> 00:00:52,350 這將是一個數組。 16 00:00:52,350 --> 00:00:57,020 我們有一個整數集合或 字符等的集合。 17 00:00:57,020 --> 00:01:00,890 >> 的結構也進行排序數據的 結構收集信息, 18 00:01:00,890 --> 00:01:03,220 但它不是用來收集類似的值。 19 00:01:03,220 --> 00:01:08,090 它通常混合了不同的數據類型 一起在單一盒子。 20 00:01:08,090 --> 00:01:10,750 但它本身並不是 用於鏈接在一起 21 00:01:10,750 --> 00:01:16,920 或者連接到一起類似 項,如一個數組。 22 00:01:16,920 --> 00:01:20,960 數組是偉大的 元素查找,但召回 23 00:01:20,960 --> 00:01:24,262 這是非常困難 插入到一個數組, 24 00:01:24,262 --> 00:01:26,470 除非我們插入的 該數組的末尾。 25 00:01:26,470 --> 00:01:29,730 >> 而最好的例子,我有 因為這是插入排序。 26 00:01:29,730 --> 00:01:31,650 如果你還記得我們的視頻 在插入排序, 27 00:01:31,650 --> 00:01:34,110 有很多的 參與其費用 28 00:01:34,110 --> 00:01:37,970 拿起元素,將它們轉移 出適合的東西的方式 29 00:01:37,970 --> 00:01:41,290 成陣列的中間。 30 00:01:41,290 --> 00:01:44,690 陣列也從另一個患 問題,這是不靈活。 31 00:01:44,690 --> 00:01:47,150 當我們聲明一個數組, 我們這一次機會吧。 32 00:01:47,150 --> 00:01:49,790 我們得到的說法,我想 這些元素。 33 00:01:49,790 --> 00:01:51,940 可能是100,它可能 是1000,它可能 34 00:01:51,940 --> 00:01:55,930 是x,其中x是一個數字,用戶 給了我們一個提示,或在命令 35 00:01:55,930 --> 00:01:56,630 行。 36 00:01:56,630 --> 00:01:59,905 >> 但是,我們只有一次機會吧,我們 沒有得到,然後說,哦,其實我 37 00:01:59,905 --> 00:02:04,360 需要101,或者我需要X加20。 38 00:02:04,360 --> 00:02:07,910 太晚了,我們已經宣布了 數組,如果我們想要獲得101或x 39 00:02:07,910 --> 00:02:12,050 加上20,我們要聲明 一個完全不同的陣列, 40 00:02:12,050 --> 00:02:15,540 複製數組中的所有元素 過來,然後我們有足夠。 41 00:02:15,540 --> 00:02:19,880 而如果我們又錯了,是什麼 如果我們真的需要102或x加40, 42 00:02:19,880 --> 00:02:21,970 我們要再次做到這一點。 43 00:02:21,970 --> 00:02:26,250 因此,他們非常不靈活 對於調整我們的數據, 44 00:02:26,250 --> 00:02:29,360 但如果我們結合在一起的一些 我們已經已經基本知識 45 00:02:29,360 --> 00:02:33,230 了解指針和結構, 特別是使用動態存儲 46 00:02:33,230 --> 00:02:36,180 分配使用malloc,我們 可以把這些碎片拼湊起來 47 00:02:36,180 --> 00:02:40,960 創建一個新的數據結構 - 一個 單鍊錶,我們可能say-- 48 00:02:40,960 --> 00:02:45,400 這使我們能夠成長, 收縮值的集合 49 00:02:45,400 --> 00:02:48,800 我們不會有任何浪費的空間。 50 00:02:48,800 --> 00:02:53,320 >> 所以,再一次,我們稱這樣的想法, 這個概念,一個鍊錶。 51 00:02:53,320 --> 00:02:56,320 特別是,在這個視頻我們 談到單向鍊錶, 52 00:02:56,320 --> 00:02:59,185 然後另一個視頻中,我們將討論 關於雙向鍊錶,這 53 00:02:59,185 --> 00:03:01,560 只是在這裡一個主題的變化。 54 00:03:01,560 --> 00:03:05,200 但一個單向鍊錶 由節點, 55 00:03:05,200 --> 00:03:08,559 節點僅僅是一個抽象的term-- 這只是一些我打電話 56 00:03:08,559 --> 00:03:10,350 這是一種 結構,基本上,我? 57 00:03:10,350 --> 00:03:16,190 只是要稱之為node--,這 節點具有兩個構件,或兩個字段。 58 00:03:16,190 --> 00:03:20,300 它的數據,通常是一個 整數,字符浮子, 59 00:03:20,300 --> 00:03:23,790 或者可以是某種其他數據類型 您已經定義了類型定義。 60 00:03:23,790 --> 00:03:29,290 它包含一個指向 相同類型的另一節點。 61 00:03:29,290 --> 00:03:34,710 >> 因此,我們有兩件事情裡面 這個節點,數據和指針 62 00:03:34,710 --> 00:03:36,380 到另一個節點。 63 00:03:36,380 --> 00:03:39,370 如果你開始顯現 這一點,你可以考慮一下 64 00:03:39,370 --> 00:03:42,280 像鏈節點的那 連接在一起。 65 00:03:42,280 --> 00:03:45,070 我們的第一個節點,它 包含數據,和一個指針 66 00:03:45,070 --> 00:03:49,110 到第二個節點,其中包含 數據,和一個指針到該第三節點。 67 00:03:49,110 --> 00:03:52,940 所以這就是為什麼我們稱它為 鏈接列表,它們鏈接在一起。 68 00:03:52,940 --> 00:03:56,070 >> 這是什麼特別的 節點結構是什麼樣子? 69 00:03:56,070 --> 00:04:01,120 好吧,如果你從我們的視頻回憶 定義自定義類型,類型高清, 70 00:04:01,120 --> 00:04:05,400 我們可以定義一個結構 - 和 鍵入這樣定義的結構。 71 00:04:05,400 --> 00:04:11,240 tyepdef結構sllist,然後我 使用這個詞的價值在這裡隨意 72 00:04:11,240 --> 00:04:13,891 以指示真的任何數據類型。 73 00:04:13,891 --> 00:04:16,890 你可以傳遞一個整數或浮點數, 你可以有一切你想要的。 74 00:04:16,890 --> 00:04:19,389 它不再僅僅限於 整數,或者類似的東西。 75 00:04:19,389 --> 00:04:22,790 因此,值是任意 數據類型,然後一個指針 76 00:04:22,790 --> 00:04:26,310 到同一類型的另一節點。 77 00:04:26,310 --> 00:04:29,690 >> 現在,有一個小抓 這裡定義的結構 78 00:04:29,690 --> 00:04:33,030 當它是一個自我參照結構。 79 00:04:33,030 --> 00:04:35,340 我必須有一個臨時的 命名為我的結構。 80 00:04:35,340 --> 00:04:37,640 在這一天我的結束 顯然想將它命名 81 00:04:37,640 --> 00:04:43,030 SLL節點,這是最終的新 名字我喜歡的類型定義的一部分, 82 00:04:43,030 --> 00:04:47,450 但我不能使用SLL節點 在這中間。 83 00:04:47,450 --> 00:04:51,430 是的原因,我沒有 創建了一個名為類型SLL節點 84 00:04:51,430 --> 00:04:55,200 直到我在這裡打這個最後一點。 85 00:04:55,200 --> 00:04:59,720 直到這一點,我必須有 另一種方式來參考此數據類型。 86 00:04:59,720 --> 00:05:02,440 >> 而這是一個自 參照數據類型。 87 00:05:02,440 --> 00:05:06,314 它; S的一個數據類型 結構,它包含一個數據, 88 00:05:06,314 --> 00:05:08,480 和一個指針到另一個 相同類型的結構。 89 00:05:08,480 --> 00:05:11,750 所以,我需要能夠引用 這種數據類型至少暫時 90 00:05:11,750 --> 00:05:14,910 所以給它一個暫時的 結構sllist名 91 00:05:14,910 --> 00:05:18,540 讓我那麼說我想要一個 指向另一個結構sllist, 92 00:05:18,540 --> 00:05:24,690 一個結構sllist明星,然後 我已經完成了定義後, 93 00:05:24,690 --> 00:05:27,220 我現在可以把這種類型的SLL節點。 94 00:05:27,220 --> 00:05:30,520 >> 所以這就是為什麼你看到有 一個臨時的名字在這裡, 95 00:05:30,520 --> 00:05:31,879 但這裡的永久名字。 96 00:05:31,879 --> 00:05:33,920 有時候,你可能會看到 結構的定義, 97 00:05:33,920 --> 00:05:36,570 例如,是不 自我指涉,是 98 00:05:36,570 --> 00:05:39,390 沒有說明的名字在這裡。 99 00:05:39,390 --> 00:05:43,040 它只想說typedef結構, 打開大括號,然後定義它。 100 00:05:43,040 --> 00:05:45,620 但是,如果你是結構是自 引用,因為這個人是, 101 00:05:45,620 --> 00:05:49,010 你需要指定一個 臨時類型名稱。 102 00:05:49,010 --> 00:05:51,310 但最終,現在 我們已經做到了這一點, 103 00:05:51,310 --> 00:05:53,620 我們只能參考 這些節點,這些單位, 104 00:05:53,620 --> 00:05:57,900 作為目的SLL節點 這段視頻的其餘部分。 105 00:05:57,900 --> 00:06:00,900 >> 好吧,讓我們知道如何 創建一個鏈接列表節點。 106 00:06:00,900 --> 00:06:03,240 我們知道如何定義 一個鏈接列表節點。 107 00:06:03,240 --> 00:06:06,670 現在,如果我們要開始 用它們來收集信息, 108 00:06:06,670 --> 00:06:10,360 有一對夫婦經營的我們 需要了解和使用。 109 00:06:10,360 --> 00:06:12,860 我們需要知道如何創建 鍊錶憑空。 110 00:06:12,860 --> 00:06:14,901 如果沒有清單已經, 我們要開始的。 111 00:06:14,901 --> 00:06:16,960 因此,我們需要能夠 以創建一個鍊錶, 112 00:06:16,960 --> 00:06:19,130 我們需要大概搜索 通過鏈接列表 113 00:06:19,130 --> 00:06:21,830 找到我們正在尋找的元素。 114 00:06:21,830 --> 00:06:24,430 我們需要的是能夠插入 新事物進入榜單, 115 00:06:24,430 --> 00:06:25,930 我們希望我們的名單能夠成長。 116 00:06:25,930 --> 00:06:28,638 同樣,我們希望能夠 從我們的名單中刪除的東西, 117 00:06:28,638 --> 00:06:30,250 我們希望我們的名單,以便能夠收縮。 118 00:06:30,250 --> 00:06:32,160 而在年底我們 計劃,特別是 119 00:06:32,160 --> 00:06:34,550 如果你還記得,我們​​是 動態分配內存 120 00:06:34,550 --> 00:06:38,337 以通常建這些列表, 我們要釋放所有的內存 121 00:06:38,337 --> 00:06:39,670 當我們用它做的工作。 122 00:06:39,670 --> 00:06:44,627 因此,我們需要能夠刪除一個 整個鍊錶在一個失敗的一舉。 123 00:06:44,627 --> 00:06:46,460 因此,讓我們通過 某些操作 124 00:06:46,460 --> 00:06:51,192 和我們怎樣才能使其可視化, 在偽代碼說話特別。 125 00:06:51,192 --> 00:06:53,150 因此,我們要創建一個 鍊錶,所以也許我們 126 00:06:53,150 --> 00:06:56,480 要定義一個函數 這個原型。 127 00:06:56,480 --> 00:07:01,690 SLL節點明星,創造,而我路過 在一個參數,一些任意數據 128 00:07:01,690 --> 00:07:05,530 再次鍵入某些任意數據類型的,。 129 00:07:05,530 --> 00:07:10,482 但是我returning--這個功能應該 還給我一個指針,以一個單 130 00:07:10,482 --> 00:07:11,190 鏈接列表節點。 131 00:07:11,190 --> 00:07:14,050 同樣,我們正在努力創造 鍊錶憑空, 132 00:07:14,050 --> 00:07:17,900 所以我需要一個指針 當我做了該名單。 133 00:07:17,900 --> 00:07:19,420 >> 那麼,什麼是這裡涉及的步驟? 134 00:07:19,420 --> 00:07:20,960 好了,第一件事我 要做的是動態 135 00:07:20,960 --> 00:07:22,550 分配空間用於新的節點。 136 00:07:22,550 --> 00:07:26,689 同樣,我們正在創造出來的薄 空氣中,所以我們需要為它的malloc空間。 137 00:07:26,689 --> 00:07:28,480 當然,馬上 我們的malloc後, 138 00:07:28,480 --> 00:07:31,692 我們經常檢查,以確保我們的 pointer--我們沒有得到回空。 139 00:07:31,692 --> 00:07:33,650 因為如果我們嘗試 尊重一個空指針, 140 00:07:33,650 --> 00:07:36,190 我們要遭受 段錯誤,我們不希望出現這種情況。 141 00:07:36,190 --> 00:07:39,510 >> 然後,我們要填補該領域, 我們要初始化值字段 142 00:07:39,510 --> 00:07:41,690 並初始化下一字段。 143 00:07:41,690 --> 00:07:45,450 然後我們想用於:最終的 函數原型indicates--我們要 144 00:07:45,450 --> 00:07:49,940 的指針返回到SLL節點。 145 00:07:49,940 --> 00:07:51,710 那麼是什麼讓這個樣子視覺? 146 00:07:51,710 --> 00:07:55,230 嗯,首先我們要動態地 分配空間用於新SLL節點, 147 00:07:55,230 --> 00:07:58,320 所以我們malloc--這 視覺表示 148 00:07:58,320 --> 00:08:00,020 節點,我們剛剛創建。 149 00:08:00,020 --> 00:08:02,757 我們檢查,以確保 它不是null--在這種情況下, 150 00:08:02,757 --> 00:08:04,840 畫面不會有 示,如果它為空, 151 00:08:04,840 --> 00:08:07,298 我們會耗盡內存, 所以我們好去那裡。 152 00:08:07,298 --> 00:08:10,200 所以,現在我們是在步驟C, 初始化節點值字段​​。 153 00:08:10,200 --> 00:08:12,280 那麼,在此基礎上功能 叫我用在這裡, 154 00:08:12,280 --> 00:08:16,700 貌似我想通過在6, 所以我會在值字段6。 155 00:08:16,700 --> 00:08:18,865 現在,初始化下一個字段。 156 00:08:18,865 --> 00:08:21,640 好了,我該怎麼辦那裡, 旁邊有個什麼吧, 157 00:08:21,640 --> 00:08:23,600 這是在列表中的唯一事情。 158 00:08:23,600 --> 00:08:27,206 那麼什麼是列表中,接下來的事情? 159 00:08:27,206 --> 00:08:29,660 >> 它不應該指向什麼,對吧。 160 00:08:29,660 --> 00:08:33,600 還有沒有別的那裡,所以有什麼 我們知道,這一概念的nothing-- 161 00:08:33,600 --> 00:08:35,638 指向什麼? 162 00:08:35,638 --> 00:08:37,929 它應該是,也許我們要 把一個空指針出現, 163 00:08:37,929 --> 00:08:40,178 我會代表空 指針只是一個紅盒子, 164 00:08:40,178 --> 00:08:41,559 我們不能再往前走。 165 00:08:41,559 --> 00:08:44,430 正如我們將看到一個小以後, 我們將有最終鏈 166 00:08:44,430 --> 00:08:46,330 箭頭連接 這些節點一起, 167 00:08:46,330 --> 00:08:48,480 但是當你打的 紅色的框,這就是空, 168 00:08:48,480 --> 00:08:51,150 我們不能再往前走, 這是該列表的末尾。 169 00:08:51,150 --> 00:08:53,960 >> 最後,我們只是想 返回一個指向該節點。 170 00:08:53,960 --> 00:08:56,160 因此,我們會打電話給它新的, 並返回新 171 00:08:56,160 --> 00:08:59,370 因此它可被用 無論函數創建它。 172 00:08:59,370 --> 00:09:03,100 所以我們去,我們已經創建了一個單 鍊錶節點無中生有, 173 00:09:03,100 --> 00:09:05,920 現在我們有了一個可以使用的列表。 174 00:09:05,920 --> 00:09:08,260 >> 現在,讓我們說,我們已經 有大型連鎖, 175 00:09:08,260 --> 00:09:09,800 我們要找到的東西在裡面。 176 00:09:09,800 --> 00:09:12,716 我們希望有一個功能是怎麼回事 返回true或false,這取決於 177 00:09:12,716 --> 00:09:15,840 在該列表中是否存在某個值。 178 00:09:15,840 --> 00:09:18,160 函數原型,或 聲明該函數, 179 00:09:18,160 --> 00:09:23,320 可能看起來像this-- BOOL發現,和 那麼我們想傳遞的兩個參數。 180 00:09:23,320 --> 00:09:26,996 >> 第一,是一個指針,指向 該鏈接的表的第一個元素。 181 00:09:26,996 --> 00:09:29,620 這實際上是你會 總想跟踪, 182 00:09:29,620 --> 00:09:33,110 實際上可能是東西, 你甚至放在一個全局變量。 183 00:09:33,110 --> 00:09:35,360 一旦你創建一個列表, 你永遠,永遠 184 00:09:35,360 --> 00:09:38,990 要保持的非常軌跡 列表的第一個元素。 185 00:09:38,990 --> 00:09:43,690 這樣,你可以參考其他所有 只是簡單地跟著鏈條元素, 186 00:09:43,690 --> 00:09:47,300 無需保持指針 完整的每一個元素。 187 00:09:47,300 --> 00:09:50,920 你只需要跟踪第一 一個,如果他們都鏈接在一起。 188 00:09:50,920 --> 00:09:52,460 >> 然後是第二件事 我們傳遞再次 189 00:09:52,460 --> 00:09:54,376 是任意some-- 我們的任何數據類型 190 00:09:54,376 --> 00:09:59,640 尋找有內 希望列表中的節點之一。 191 00:09:59,640 --> 00:10:00,980 那麼哪些步驟? 192 00:10:00,980 --> 00:10:04,250 好了,我們做的第一件事是 我們創建了一個橫向的指針 193 00:10:04,250 --> 00:10:06,015 指向列表頭部。 194 00:10:06,015 --> 00:10:08,890 那麼,為什麼我們這樣做,我們已經 有一個指針在表頭, 195 00:10:08,890 --> 00:10:10,974 為什麼我們不只是移動了一繞? 196 00:10:10,974 --> 00:10:13,140 嗯,就像我剛才說的, 這對我們來說真的很重要 197 00:10:13,140 --> 00:10:17,580 要始終保持軌道的 列表中的第一個元素。 198 00:10:17,580 --> 00:10:21,270 所以它實際上更好 創建一個副本, 199 00:10:21,270 --> 00:10:25,350 並用它來從不左右移動,所以我們 意外離開,否則我們永遠 200 00:10:25,350 --> 00:10:30,430 有一個指針在某些時候是 右邊上的列表中的第一個元素。 201 00:10:30,430 --> 00:10:33,290 因此,它是最好創建一個 我們使用移動第二個。 202 00:10:33,290 --> 00:10:35,877 >> 然後,我們只是比較是否 在該節點的值字段 203 00:10:35,877 --> 00:10:38,960 就是我們正在尋找的東西,如果它是 不,我們只是移動到下一個節點。 204 00:10:38,960 --> 00:10:41,040 我們繼續這樣做, 過來,過來,過來, 205 00:10:41,040 --> 00:10:44,811 直到我們要么找到 元素,或者我們打 206 00:10:44,811 --> 00:10:47,310 null--我們已經走到了盡頭 列表,它是不存在的。 207 00:10:47,310 --> 00:10:50,540 這應該有希望打鈴 你剛才線性搜索, 208 00:10:50,540 --> 00:10:54,430 我們只是複製它 一個單向鍊錶結構 209 00:10:54,430 --> 00:10:56,280 代替使用一個陣列,以做到這一點。 210 00:10:56,280 --> 00:10:58,210 >> 所以這裡有一個例子 一個單向鍊錶。 211 00:10:58,210 --> 00:11:00,043 這其中包括 五個節點,我們有 212 00:11:00,043 --> 00:11:04,330 一個指針的頭 列表中,這就是所謂的列表。 213 00:11:04,330 --> 00:11:07,385 我們要做的第一件事就是 再次,創建遍歷指針。 214 00:11:07,385 --> 00:11:09,760 所以,我們現在兩個指針 這點同樣的事情。 215 00:11:09,760 --> 00:11:15,025 >> 現在,請注意這裡。此外,我也沒 必須對malloc的TRAV任何空間。 216 00:11:15,025 --> 00:11:18,970 我並沒有說TRAV等於的malloc 東西時,該節點已經存在, 217 00:11:18,970 --> 00:11:21,160 在內存空間已經存在。 218 00:11:21,160 --> 00:11:24,290 因此,所有我實際上做的是 創建另一個指針。 219 00:11:24,290 --> 00:11:28,210 我不是mallocing額外 空間,只是現在的兩個指針 220 00:11:28,210 --> 00:11:31,370 指向同樣的事情。 221 00:11:31,370 --> 00:11:33,710 >> 所以是2我在找什麼? 222 00:11:33,710 --> 00:11:37,220 哦,不,所以不是我 將移動到下一個。 223 00:11:37,220 --> 00:11:41,740 所以基本上我會說, TRAV等於TRAV旁邊。 224 00:11:41,740 --> 00:11:43,630 3我在尋找什麼,沒有。 225 00:11:43,630 --> 00:11:45,780 所以,我繼續走 通過,直到最後 226 00:11:45,780 --> 00:11:48,690 到6這就是我要找 用於基於所述函數調用 227 00:11:48,690 --> 00:11:51,600 我在上面 在那裡,所以我做了。 228 00:11:51,600 --> 00:11:54,150 >> 現在,如果元件我什麼 尋找的是不在列表中, 229 00:11:54,150 --> 00:11:55,510 難道還要去上班? 230 00:11:55,510 --> 00:11:57,120 好了,注意到列表 這裡是微妙的不同, 231 00:11:57,120 --> 00:11:59,410 這是另一件事是 用鍊錶重要的, 232 00:11:59,410 --> 00:12:01,780 不必保留 它們在任何特定的順序。 233 00:12:01,780 --> 00:12:05,390 你可以,如果你想要的,但 你可能已經注意到了 234 00:12:05,390 --> 00:12:09,310 我們不是跟踪 我們是在什麼數量的元素。 235 00:12:09,310 --> 00:12:13,150 >> 這就是那種一筆交易中,我們 有鍊錶節陣列, 236 00:12:13,150 --> 00:12:15,300 難道我們沒有 隨機訪問了。 237 00:12:15,300 --> 00:12:18,150 我們不能只是說,我想 去第0個元素, 238 00:12:18,150 --> 00:12:21,410 或者我的數組的第6元, 我可以在一個陣列做。 239 00:12:21,410 --> 00:12:25,080 我不能說我想去的 第0個元素,或者第6元, 240 00:12:25,080 --> 00:12:30,360 或我的鍊錶25元件, 有沒有與之相關的索引。 241 00:12:30,360 --> 00:12:33,660 因此它並不真正的問題 如果我們保留以我們的名單。 242 00:12:33,660 --> 00:12:36,080 如果你想你 當然可以,但有 243 00:12:36,080 --> 00:12:38,567 沒有理由,他們需要 以任何順序被保留。 244 00:12:38,567 --> 00:12:40,400 如此反复,讓我們試著 在此列表中發現6。 245 00:12:40,400 --> 00:12:43,200 好了,我們開始在 開始,我們沒有發現6, 246 00:12:43,200 --> 00:12:47,690 然後我們繼續沒有找到 6,直到我們最終到達這裡。 247 00:12:47,690 --> 00:12:52,790 所以現在TRAV指向節點 含有8,和六不在那裡。 248 00:12:52,790 --> 00:12:55,250 >> 因此,下一步將是 去下一個指針, 249 00:12:55,250 --> 00:12:57,440 所以說TRAV等於TRAV旁邊。 250 00:12:57,440 --> 00:13:00,750 好了,接下來TRAV,以表示 紅色框出現,為空。 251 00:13:00,750 --> 00:13:03,020 因此,有無處可 走,所以在這一點 252 00:13:03,020 --> 00:13:06,120 我們可以得出結論,我們已經達到 鍊錶的末尾, 253 00:13:06,120 --> 00:13:07,190 和圖6是不是在那裡。 254 00:13:07,190 --> 00:13:10,980 並且將它返回 假在這種情況下。 255 00:13:10,980 --> 00:13:14,540 >> 好了,我們怎麼插入一個新的 節點插入到鍊錶? 256 00:13:14,540 --> 00:13:17,310 因此,我們已經能夠創造 鍊錶從哪兒冒出來, 257 00:13:17,310 --> 00:13:19,370 但我們可能要 建立一個鏈條,而不是 258 00:13:19,370 --> 00:13:22,620 創建一批獨特的名單。 259 00:13:22,620 --> 00:13:25,700 我們希望有一列表 有一堆在它的節點, 260 00:13:25,700 --> 00:13:28,040 不是一堆列表與單個節點。 261 00:13:28,040 --> 00:13:31,260 因此,我們不能只是一味地使用Create 功能我們前面定義的,現在我們 262 00:13:31,260 --> 00:13:33,860 要插入到一個 已經存在列表。 263 00:13:33,860 --> 00:13:36,499 >> 所以這種情況下,我們將 傳入兩個參數, 264 00:13:36,499 --> 00:13:39,290 指針的頭部 鍊錶,我們要添加到。 265 00:13:39,290 --> 00:13:40,910 再次,這就是為什麼它是如此 重要的是,我們始終 266 00:13:40,910 --> 00:13:43,400 跟踪它,因為 這是我們唯一的辦法真的 267 00:13:43,400 --> 00:13:46,690 不得不指整個列表是 剛剛通過的指針的第一個元素。 268 00:13:46,690 --> 00:13:49,360 因此,我們要傳遞一個 指針,該第一元件, 269 00:13:49,360 --> 00:13:52,226 和任何價值,我們 要添加到列表中。 270 00:13:52,226 --> 00:13:54,600 而最終這個功能 是否會返回一個指針 271 00:13:54,600 --> 00:13:57,980 到鍊錶的新掌門人。 272 00:13:57,980 --> 00:13:59,700 >> 什麼是這裡涉及的步驟? 273 00:13:59,700 --> 00:14:02,249 好了,就像創建, 我們需要動態分配 274 00:14:02,249 --> 00:14:05,540 一個新的節點空間,並進行檢查,以 確保我們不會耗盡內存,再一次, 275 00:14:05,540 --> 00:14:07,150 因為我們使用的malloc。 276 00:14:07,150 --> 00:14:09,080 然後,我們要填充 並插入節點, 277 00:14:09,080 --> 00:14:12,730 所以放多少,什麼 val為,到節點。 278 00:14:12,730 --> 00:14:17,310 我們要在插入節點 鍊錶的開頭。 279 00:14:17,310 --> 00:14:19,619 >> 還有一個原因是我 要做到這一點,它 280 00:14:19,619 --> 00:14:21,910 可能是值得考慮第二 在這裡暫停視頻, 281 00:14:21,910 --> 00:14:25,860 想想我為什麼會想 在插入一個鏈接開始 282 00:14:25,860 --> 00:14:26,589 名單。 283 00:14:26,589 --> 00:14:28,630 再次,我前面提到的 它並沒有真正 284 00:14:28,630 --> 00:14:33,020 的問題,如果我們在任何保護它 順序,所以也許這是一個線索。 285 00:14:33,020 --> 00:14:36,040 而你看到的,如果我們會發生什麼 想用於:或者只是第二 286 00:14:36,040 --> 00:14:37,360 以前,當我們打算 通過搜索你 287 00:14:37,360 --> 00:14:39,235 可以看到什麼可能 發生,如果我們試圖 288 00:14:39,235 --> 00:14:41,330 插入在列表的末尾。 289 00:14:41,330 --> 00:14:44,750 因為我們沒有一個 指針的列表的末尾。 290 00:14:44,750 --> 00:14:47,490 >> 因此原因,我想 插入開頭, 291 00:14:47,490 --> 00:14:49,380 是因為我可以馬上做到這一點。 292 00:14:49,380 --> 00:14:52,730 我有一個指針指向開始, 我們將看到這一場視覺在第二。 293 00:14:52,730 --> 00:14:55,605 但是,如果我想插入底, 我要從頭開始, 294 00:14:55,605 --> 00:14:58,760 遍歷所有的方式向 到底,然後把它釘住。 295 00:14:58,760 --> 00:15:01,420 因此,這將意味著 在列表的末尾插入 296 00:15:01,420 --> 00:15:04,140 將成為n的Ø 操作時,要回 297 00:15:04,140 --> 00:15:06,720 我們的討論 計算複雜性。 298 00:15:06,720 --> 00:15:10,140 它會變成n操作,其中的鄰 作為列表越來越大,大, 299 00:15:10,140 --> 00:15:13,310 大,它會變得越來越 更難以粘性的東西 300 00:15:13,310 --> 00:15:14,661 上在末端。 301 00:15:14,661 --> 00:15:17,410 但它總是很容易 釘東西之初, 302 00:15:17,410 --> 00:15:19,060 你總是在開頭。 303 00:15:19,060 --> 00:15:21,620 >> 我們將看到一個可視化的這個了。 304 00:15:21,620 --> 00:15:24,100 然後,一旦我們完成了,一旦 我們插入新的節點, 305 00:15:24,100 --> 00:15:26,880 我們希望我們的指針返回 鍊錶新的頭,這 306 00:15:26,880 --> 00:15:29,213 因為我們要插入在 開始,居然會 307 00:15:29,213 --> 00:15:31,060 一個指向我們剛剛創建的節點。 308 00:15:31,060 --> 00:15:33,280 讓我們想像這一點, 因為我認為這將幫助。 309 00:15:33,280 --> 00:15:36,661 >> 因此,這裡是我們的名單,它由 四個元素,一個節點含有15, 310 00:15:36,661 --> 00:15:38,410 它指向一個節點 含有9,其 311 00:15:38,410 --> 00:15:41,370 指向包含13的節點, 指向包含一個節點 312 00:15:41,370 --> 00:15:44,840 10,它具有空 指針作為其下一個指針 313 00:15:44,840 --> 00:15:47,010 所以這是該列表的末尾。 314 00:15:47,010 --> 00:15:50,200 因此,我們要插入一個 用價值12新節點 315 00:15:50,200 --> 00:15:52,720 在這個初 列表中,我們怎麼辦? 316 00:15:52,720 --> 00:15:58,770 嗯,首先,我們的malloc空間的 節點,然後我們把12在那裡。 317 00:15:58,770 --> 00:16:02,211 >> 所以,現在我們已經到了一個 決策點,對不對? 318 00:16:02,211 --> 00:16:03,960 我們有幾個 指針,我們可以 319 00:16:03,960 --> 00:16:06,770 移動,哪一個應該我們搬進去? 320 00:16:06,770 --> 00:16:09,250 我們應該做出12點 列表中 - 新掌門 321 00:16:09,250 --> 00:16:13,020 或不好意思,我們應該讓12 指向老首長的名單? 322 00:16:13,020 --> 00:16:15,319 或者我們應該說, 列表現在開始在12。 323 00:16:15,319 --> 00:16:17,110 有一個區別 在那裡,我們將看看 324 00:16:17,110 --> 00:16:19,870 在與兩國在第二會發生什麼。 325 00:16:19,870 --> 00:16:23,350 >> 但是這將導致一個 對於側邊欄很大的話題, 326 00:16:23,350 --> 00:16:26,280 這是一個的 用鍊錶最棘手的事情 327 00:16:26,280 --> 00:16:30,980 被安排指針 以正確的順序。 328 00:16:30,980 --> 00:16:34,520 如果你搬東西壞了, 你可以結束了意外 329 00:16:34,520 --> 00:16:36,050 孤兒列表的其餘部分。 330 00:16:36,050 --> 00:16:37,300 這裡是一個很好的例子。 331 00:16:37,300 --> 00:16:40,540 所以,讓我們的想法of-- 好了,我們已經創建了12。 332 00:16:40,540 --> 00:16:43,180 我們知道,12將是 列表中的新掌門人, 333 00:16:43,180 --> 00:16:47,660 所以我們為什麼不正義之舉 該列表指針指向那裡。 334 00:16:47,660 --> 00:16:49,070 >> 好了,這是很好的。 335 00:16:49,070 --> 00:16:51,560 所以,現在在那裡做12下一個點? 336 00:16:51,560 --> 00:16:54,580 我的意思是,在視覺上我們可以看到 它將指向15, 337 00:16:54,580 --> 00:16:57,250 作為人類,它真的很明顯給我們。 338 00:16:57,250 --> 00:17:00,300 計算機如何知道的? 339 00:17:00,300 --> 00:17:02,720 我們沒有任何東西 指著15了,對不對? 340 00:17:02,720 --> 00:17:05,869 >> 我們已經失去了任何參考15的能力。 341 00:17:05,869 --> 00:17:11,460 我們不能說新的箭頭旁邊的equals 什麼東西,有什麼也沒有。 342 00:17:11,460 --> 00:17:13,510 事實上,我們已經成為孤兒 列表的其餘 343 00:17:13,510 --> 00:17:16,465 通過這樣做,我們已經 不小心打破了鏈條。 344 00:17:16,465 --> 00:17:18,089 我們當然不希望這樣做。 345 00:17:18,089 --> 00:17:20,000 >> 因此,讓我們回去再試試這個。 346 00:17:20,000 --> 00:17:24,060 也許做正確的事 是設置12的下一個指針 347 00:17:24,060 --> 00:17:28,290 到舊頭部列表的第一, 那麼我們可以將名單上。 348 00:17:28,290 --> 00:17:30,420 而事實上,是這樣的 正確的順序我們 349 00:17:30,420 --> 00:17:32,836 需要遵循當我們 正與單向鍊錶。 350 00:17:32,836 --> 00:17:36,460 我們總是希望連接 新元素到列表中, 351 00:17:36,460 --> 00:17:41,010 之前,我們需要的那種 改變的重要一步 352 00:17:41,010 --> 00:17:43,360 其中鍊錶的頭。 353 00:17:43,360 --> 00:17:46,740 再次,這是這樣一個根本的東西, 我們不想失去它的軌道。 354 00:17:46,740 --> 00:17:49,310 >> 所以我們要確保 一切都鏈接在一起, 355 00:17:49,310 --> 00:17:52,040 我們繼續之前的指針。 356 00:17:52,040 --> 00:17:55,300 所以,這將是正確的順序, 這是連接12到列表中, 357 00:17:55,300 --> 00:17:57,630 然後說,該清單啟動12。 358 00:17:57,630 --> 00:18:00,860 如果我們所說的名單開始在12和 然後試圖連接12到列表中, 359 00:18:00,860 --> 00:18:02,193 我們已經看到發生了什麼。 360 00:18:02,193 --> 00:18:04,920 我們失去了對列表進行的錯誤。 361 00:18:04,920 --> 00:18:06,740 >> 好了,還有一件事談。 362 00:18:06,740 --> 00:18:09,750 如果我們要擺脫什麼 整個鍊錶一次? 363 00:18:09,750 --> 00:18:11,750 同樣,我們mallocing 這一切的空間,所以我們 364 00:18:11,750 --> 00:18:13,351 需要釋放它的時候,我們就大功告成了。 365 00:18:13,351 --> 00:18:15,350 所以,現在我們想刪除 整個鍊錶。 366 00:18:15,350 --> 00:18:16,850 那麼,我們要怎麼辦? 367 00:18:16,850 --> 00:18:20,460 >> 如果我們已經達到了空指針,我們 想停下來,否則,只是刪除 368 00:18:20,460 --> 00:18:23,420 該列表的其餘部分,然後讓我自由。 369 00:18:23,420 --> 00:18:28,890 刪除列表的其餘部分, 然後釋放當前節點。 370 00:18:28,890 --> 00:18:32,850 這是什麼聲音一樣, 有什麼技術,我們聊 371 00:18:32,850 --> 00:18:35,440 有關以前這聽起來像不像? 372 00:18:35,440 --> 00:18:39,560 刪除其他人,然後 回來並刪除了我。 373 00:18:39,560 --> 00:18:42,380 >> 這是遞歸的,我們所做的 問題稍微小了一點, 374 00:18:42,380 --> 00:18:46,910 我們說每個人都刪除 否則的話,你可以刪除我。 375 00:18:46,910 --> 00:18:50,940 而進一步下跌的道路,節點 會說,否則刪除每一個人。 376 00:18:50,940 --> 00:18:53,940 但最終,我們會得到的 點的列表為空, 377 00:18:53,940 --> 00:18:55,310 這就是我們的基本情況。 378 00:18:55,310 --> 00:18:57,010 >> 因此,讓我們來看看這個, 以及這可能會奏效。 379 00:18:57,010 --> 00:18:59,759 因此,這裡是我們的名單,這是相同的 列出我們只是在談論, 380 00:18:59,759 --> 00:19:00,980 這裡面的步驟。 381 00:19:00,980 --> 00:19:04,200 有大量的文字在這裡,但 希望可視化將幫助。 382 00:19:04,200 --> 00:19:08,557 >> 因此,我們have--,我還拉 我們的堆棧幀圖 383 00:19:08,557 --> 00:19:10,890 從我們的視頻調用棧, 並希望這一切 384 00:19:10,890 --> 00:19:13,260 同時會告訴你這是怎麼回事。 385 00:19:13,260 --> 00:19:14,510 因此,這裡是我們的偽代碼。 386 00:19:14,510 --> 00:19:17,830 如果我們到達空 指針,停止,否則, 387 00:19:17,830 --> 00:19:21,320 刪除列表的其餘部分, 然後釋放當前節點。 388 00:19:21,320 --> 00:19:25,700 所以,現在,列表中 - 我們是指針 389 00:19:25,700 --> 00:19:28,410 傳遞摧毀點至12。 390 00:19:28,410 --> 00:19:33,340 12不是一個空指針,所以我們 要刪除列表的其餘部分。 391 00:19:33,340 --> 00:19:35,450 >> 什麼是刪除 我們剩下的參與? 392 00:19:35,450 --> 00:19:37,950 嗯,這意味著製作 呼籲摧毀,說 393 00:19:37,950 --> 00:19:42,060 即圖15是的開頭 其餘的,我們要摧毀名單。 394 00:19:42,060 --> 00:19:47,480 這樣一來,呼籲銷毀 12是種擱置。 395 00:19:47,480 --> 00:19:52,690 它凍結在那裡,等待 呼籲摧毀15,完成其工作。 396 00:19:52,690 --> 00:19:56,280 >> 好了,15不是一個空指針, 所以它會說,沒事, 397 00:19:56,280 --> 00:19:58,450 同時,刪除列表的其餘部分。 398 00:19:58,450 --> 00:20:00,760 列表的其餘部分開始 9,所以我們只 399 00:20:00,760 --> 00:20:04,514 等到你刪除所有 的東西,然後回來,並刪除了我。 400 00:20:04,514 --> 00:20:06,680 那麼9會說,好吧, 我不是一個空指針, 401 00:20:06,680 --> 00:20:09,020 所以從這裡刪除其餘的名單。 402 00:20:09,020 --> 00:20:11,805 所以盡量和銷毀13。 403 00:20:11,805 --> 00:20:15,550 13說,我不是空指針, 同樣的事情,它通過降壓。 404 00:20:15,550 --> 00:20:17,930 10不是空指針,10 包含一個空指針, 405 00:20:17,930 --> 00:20:20,200 但10本身不是一個 空指針現在, 406 00:20:20,200 --> 00:20:22,470 因此它通過降壓太。 407 00:20:22,470 --> 00:20:25,560 >> 現在列出點那裡, 真正將指向some-- 408 00:20:25,560 --> 00:20:28,710 如果我的形象有更多的空間, 它會指向一些隨機的空間 409 00:20:28,710 --> 00:20:29,960 我們不知道它是什麼。 410 00:20:29,960 --> 00:20:34,680 這是空指針雖然名單 簡直是現在設置它的值空。 411 00:20:34,680 --> 00:20:36,820 它指向正確的紅色方框內。 412 00:20:36,820 --> 00:20:39,960 我們達到了一個空指針,所以 我們可以停下來,我們就大功告成了。 413 00:20:39,960 --> 00:20:46,230 >> 所以那紫色幀now--在 stack--的頂部是這樣的活動框架, 414 00:20:46,230 --> 00:20:47,017 但它的完成。 415 00:20:47,017 --> 00:20:48,600 如果我們已經達到了一個空指針,停止。 416 00:20:48,600 --> 00:20:51,290 我們沒有做任何事情,我們 無法釋放空指針, 417 00:20:51,290 --> 00:20:55,070 我們沒有任何的malloc 空間,所以我們就大功告成了。 418 00:20:55,070 --> 00:20:57,590 這樣功能框架 被破壞,並且我們 419 00:20:57,590 --> 00:21:00,930 resume--我們拿起我們離開 關具有下一最高一個,這 420 00:21:00,930 --> 00:21:02,807 這是深藍色的框在這裡。 421 00:21:02,807 --> 00:21:04,390 於是我們拿起身在何方,我們不放過。 422 00:21:04,390 --> 00:21:06,598 我們刪除的休息 列表了,所以現在我們 423 00:21:06,598 --> 00:21:08,000 要釋放當前節點。 424 00:21:08,000 --> 00:21:12,920 所以,現在我們可以免費這個節點,現在 我們已經達到了函數的結束。 425 00:21:12,920 --> 00:21:16,810 而這樣的功能框架被破壞, 我們拿起在淺藍色的。 426 00:21:16,810 --> 00:21:20,650 >> 因此,says--我已經done-- 刪除列表的其餘部分,所以 427 00:21:20,650 --> 00:21:23,140 釋放當前節點。 428 00:21:23,140 --> 00:21:26,520 而現在的黃色框為 回堆棧的頂部。 429 00:21:26,520 --> 00:21:29,655 所以你看,我們現在是 從右破壞列表中離開了。 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> 會發生什麼,不過, 如果我們做事情的方法不對? 432 00:21:37,280 --> 00:21:39,410 就像當我們試圖 添加元素。 433 00:21:39,410 --> 00:21:41,909 如果我們搞砸鏈,如果 我們沒有連接的指針 434 00:21:41,909 --> 00:21:44,690 以正確的順序,如果我們 剛剛釋放的第一個元素, 435 00:21:44,690 --> 00:21:47,420 如果我們只是釋放了 頭列表,現在我們 436 00:21:47,420 --> 00:21:49,642 沒有辦法參考 列表的其餘部分。 437 00:21:49,642 --> 00:21:51,350 因此,我們將有 孤立的一切, 438 00:21:51,350 --> 00:21:53,880 我們將不得不什麼 所謂的內存洩漏。 439 00:21:53,880 --> 00:21:56,800 如果您從我們的視頻回憶 動態內存分配, 440 00:21:56,800 --> 00:21:58,650 這不是很好的事情。 441 00:21:58,650 --> 00:22:00,810 >> 因此,正如我所說, 有幾個操作 442 00:22:00,810 --> 00:22:04,010 我們需要用工作 與有效鍊錶。 443 00:22:04,010 --> 00:22:08,430 你可能已經注意到我省略之一, 從鏈接中刪除一個單個元件 444 00:22:08,430 --> 00:22:09,064 名單。 445 00:22:09,064 --> 00:22:10,980 我這樣做的原因 是它是一種實際 446 00:22:10,980 --> 00:22:14,360 棘手思考如何刪除 從一個單獨的單個元件 447 00:22:14,360 --> 00:22:15,600 鍊錶。 448 00:22:15,600 --> 00:22:19,950 我們需要能夠跳過 一些在列表中,這 449 00:22:19,950 --> 00:22:22,975 意味著我們得到一個point--我們 要刪除這node-- 450 00:22:22,975 --> 00:22:25,350 但為了使其所以我們 不會丟失任何信息, 451 00:22:25,350 --> 00:22:30,530 我們需要連接這 節點在這裡,在這裡。 452 00:22:30,530 --> 00:22:33,390 >> 所以我大概那個做錯了 從視覺角度。 453 00:22:33,390 --> 00:22:36,830 因此,我們在一開始,我們 列表中,我們正在著手通過, 454 00:22:36,830 --> 00:22:40,510 我們要刪除此節點。 455 00:22:40,510 --> 00:22:43,440 如果我們只是將其刪除, 我們已經打破了鏈條。 456 00:22:43,440 --> 00:22:45,950 這個節點就在這裡 指的是一切, 457 00:22:45,950 --> 00:22:48,260 它包含從這裡掉了鍊子。 458 00:22:48,260 --> 00:22:51,190 >> 因此,我們需要做的其實 之後,我們到了這一點, 459 00:22:51,190 --> 00:22:56,670 是我們需要退一步之一, 在連接這個節點,這個節點, 460 00:22:56,670 --> 00:22:58,590 所以我們可以再刪除 一個在中間。 461 00:22:58,590 --> 00:23:02,120 但單鍊錶不 為我們提供了一種倒退。 462 00:23:02,120 --> 00:23:05,160 因此,我們需要可以保持 兩個指針,然後將它們移動 463 00:23:05,160 --> 00:23:09,527 一前一後的排序斷步驟, 另外,因為我們去,或者到一個地步 464 00:23:09,527 --> 00:23:11,110 然後通過發送另一個指針。 465 00:23:11,110 --> 00:23:13,150 正如你所看到的, 可以變得有些混亂。 466 00:23:13,150 --> 00:23:15,360 幸運的是,我們有 另一種方式來解決, 467 00:23:15,360 --> 00:23:17,810 當我們談論雙向鍊錶。 468 00:23:17,810 --> 00:23:20,720 >> 我是道格·勞埃德,這是CS50。 469 00:23:20,720 --> 00:23:22,298