1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [音樂播放] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 揚聲器1:好吧。 5 00:00:12,900 --> 00:00:14,600 每個人都歡迎回款。 6 00:00:14,600 --> 00:00:18,660 我希望大家都成功 從你的測驗回收 7 00:00:18,660 --> 00:00:19,510 從上週。 8 00:00:19,510 --> 00:00:22,564 我知道這是一個有點瘋狂的時候。 9 00:00:22,564 --> 00:00:25,230 正如我之前說,如果你是 的標準偏差之內, 10 00:00:25,230 --> 00:00:28,188 真的不擔心,尤其是 一個不太舒適的部分。 11 00:00:28,188 --> 00:00:30,230 這是什麼地方,你應該的。 12 00:00:30,230 --> 00:00:32,850 >> 如果你做得很好,那麼真棒。 13 00:00:32,850 --> 00:00:33,650 榮譽給你。 14 00:00:33,650 --> 00:00:36,149 如果你覺得你需要 多一點點的幫助,請 15 00:00:36,149 --> 00:00:38,140 隨時到達 出任何的轉錄因子。 16 00:00:38,140 --> 00:00:40,030 我們都在這裡幫忙。 17 00:00:40,030 --> 00:00:40,960 >> 這就是為什麼我們教。 18 00:00:40,960 --> 00:00:44,550 這就是為什麼我在這裡每週一為你 球員和在辦公時間星期四休息。 19 00:00:44,550 --> 00:00:48,130 因此,請隨時讓我知道 如果你擔心什麼 20 00:00:48,130 --> 00:00:52,450 或者,如果有對任何競猜 你真的想解決的問題。 21 00:00:52,450 --> 00:00:56,940 >> 因此,對於今天的議程 所有關於數據結構。 22 00:00:56,940 --> 00:01:01,520 其中一些只是要公正 為了讓你熟悉這些。 23 00:01:01,520 --> 00:01:04,870 你可能永遠不會實現 他們在這個類中。 24 00:01:04,870 --> 00:01:08,690 有些人你會的, 像你的拼寫PSET。 25 00:01:08,690 --> 00:01:11,380 >> 你有你的選擇 哈希表和嘗試的。 26 00:01:11,380 --> 00:01:13,680 所以我們一定會去在那些。 27 00:01:13,680 --> 00:01:18,690 這將是肯定更有種 高電平部分的今天,雖然 28 00:01:18,690 --> 00:01:22,630 因為有很多人,如果 我們進入的實施細則 29 00:01:22,630 --> 00:01:26,490 所有這些,我們不會 甚至可以通過鏈接列表 30 00:01:26,490 --> 00:01:28,520 也許哈希表的一點點。 31 00:01:28,520 --> 00:01:31,200 >> 所以多多包涵。 32 00:01:31,200 --> 00:01:33,530 我們不打算做 盡可能多的編碼這個時候。 33 00:01:33,530 --> 00:01:36,870 如果您有任何關於它的問題 或者你想看到它實現的 34 00:01:36,870 --> 00:01:39,260 還是自己試試看, 我絕對推薦 35 00:01:39,260 --> 00:01:44,250 要study.cs50.net,這 具有所有的這些例子。 36 00:01:44,250 --> 00:01:46,400 這將有我的學習認證 用音符,我們 37 00:01:46,400 --> 00:01:50,860 傾向於使用以及一些編程 練習,特別是對事 38 00:01:50,860 --> 00:01:55,250 如鍊錶和二進制 樹木堆棧和線索。 39 00:01:55,250 --> 00:01:59,590 這麼少的較高水平,這 也許是很好的你們。 40 00:01:59,590 --> 00:02:01,320 >> 所以這樣,我們就開始吧。 41 00:02:01,320 --> 00:02:03,060 而且,yes--測驗。 42 00:02:03,060 --> 00:02:06,550 我想絕大多數人誰是 我的部分有你的測驗, 43 00:02:06,550 --> 00:02:12,060 但任何人進來,或某種原因,你 不這樣做,他們就在這裡,在前面。 44 00:02:12,060 --> 00:02:12,740 >> 所以鍊錶。 45 00:02:12,740 --> 00:02:15,650 我知道這種雲 您的測驗前備份。 46 00:02:15,650 --> 00:02:17,940 這是一周前 我們了解了這一點。 47 00:02:17,940 --> 00:02:21,040 但是,在這種情況下,我們只 走多一點點深入。 48 00:02:21,040 --> 00:02:25,900 >> 那麼,為什麼我們會選擇一個 鍊錶一個數組? 49 00:02:25,900 --> 00:02:27,130 有什麼區別呢? 50 00:02:27,130 --> 00:02:27,630 是嗎? 51 00:02:27,630 --> 00:02:30,464 >> 聽眾:您還可以擴大一個鏈接 列出與數組的固定大小。 52 00:02:30,464 --> 00:02:31,171 揚聲器1:沒錯。 53 00:02:31,171 --> 00:02:33,970 數組有固定的大小,而一 鍊錶具有可變的大小。 54 00:02:33,970 --> 00:02:36,970 因此,如果我們不知道如何 我們多麼希望存儲, 55 00:02:36,970 --> 00:02:39,880 鍊錶給我們帶來了很大的 辦法做到這一點,因為我們可以只 56 00:02:39,880 --> 00:02:43,730 添加另一個節點上,並添加上 另一個節點,並添加另一個節點上。 57 00:02:43,730 --> 00:02:45,750 但可能是一個權衡? 58 00:02:45,750 --> 00:02:49,521 有誰還記得權衡 數組和鍊錶之間? 59 00:02:49,521 --> 00:02:50,020 Mmhmm​​? 60 00:02:50,020 --> 00:02:51,460 >> 聽眾:你必須 經過一路 61 00:02:51,460 --> 00:02:53,738 通過該鏈接的表 發現列表中的一個元素。 62 00:02:53,738 --> 00:02:55,570 在一個陣列,可以 只要找到一個元素。 63 00:02:55,570 --> 00:02:56,278 >> 揚聲器1:沒錯。 64 00:02:56,278 --> 00:02:57,120 因此,與arrays-- 65 00:02:57,120 --> 00:02:58,500 >> 聽眾:[聽不清]。 66 00:02:58,500 --> 00:03:01,090 >> 揚聲器1:數組,我們有 什麼叫做隨機訪問。 67 00:03:01,090 --> 00:03:04,820 也就是說,如果我們要的是 有史以來第五點名單 68 00:03:04,820 --> 00:03:07,230 或第五點是我們 數組,我們只要抓住它。 69 00:03:07,230 --> 00:03:10,440 如果它是一個鍊錶,我們有 遍歷,對不對? 70 00:03:10,440 --> 00:03:14,020 所以,在訪問一個元素 一個陣列是恆定時間, 71 00:03:14,020 --> 00:03:19,530 而用一個鍊錶的那樣 最有可能是線性的時間,因為也許 72 00:03:19,530 --> 00:03:21,370 我們的元件是一路在末端。 73 00:03:21,370 --> 00:03:23,446 我們有過的一切進行搜索。 74 00:03:23,446 --> 00:03:25,320 因此,所有這些數據 我們要去結構 75 00:03:25,320 --> 00:03:29,330 要在花多一點的時間, 哪些長處和底片。 76 00:03:29,330 --> 00:03:31,480 什麼時候我們可能要 使用一個比其他? 77 00:03:31,480 --> 00:03:34,970 這就是種的 更大的東西拿走。 78 00:03:34,970 --> 00:03:40,140 >> 因此,我們必須在這裡 定義一個節點。 79 00:03:40,140 --> 00:03:43,040 這就像在一個元素 我們的鍊錶,對不對? 80 00:03:43,040 --> 00:03:46,180 所以,我們都很熟悉 我們的typedef結構, 81 00:03:46,180 --> 00:03:47,980 我們走過去,在回顧過去的時候。 82 00:03:47,980 --> 00:03:53,180 它基本上只是創造 我們可以使用另一種數據類型。 83 00:03:53,180 --> 00:03:57,930 >> 在這種情況下,它的一些節點 這將在一定整數。 84 00:03:57,930 --> 00:04:00,210 然後什麼是第二部分在這裡? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 任何人嗎? 87 00:04:05,677 --> 00:04:06,680 >> 聽眾:[聽不清]。 88 00:04:06,680 --> 00:04:07,020 >> 揚聲器1:是啊。 89 00:04:07,020 --> 00:04:08,400 這是一個指向下一個節點。 90 00:04:08,400 --> 00:04:12,610 因此,這實際上應該是在這裡。 91 00:04:12,610 --> 00:04:18,790 這類型的指針 節點到下一件事情。 92 00:04:18,790 --> 00:04:22,410 而這正是他們 包括我們的節點。 93 00:04:22,410 --> 00:04:24,060 涼爽。 94 00:04:24,060 --> 00:04:29,390 >> 好吧,所以用搜索,因為我們 只是說前手,如果你 95 00:04:29,390 --> 00:04:31,840 要通過搜索, 你必須真正迭代 96 00:04:31,840 --> 00:04:33,660 通過您的鏈接列表。 97 00:04:33,660 --> 00:04:38,530 因此,如果我們要尋找的數量 9,我們將開始在我們的頭上 98 00:04:38,530 --> 00:04:41,520 並指向我們開始 我們的鍊錶,對不對? 99 00:04:41,520 --> 00:04:44,600 我們說好,這是否 節點包含數字9? 100 00:04:44,600 --> 00:04:45,690 不是嗎? 101 00:04:45,690 --> 00:04:47,500 >> 好吧,去下一個。 102 00:04:47,500 --> 00:04:48,312 遵循它。 103 00:04:48,312 --> 00:04:49,520 它包含數字9? 104 00:04:49,520 --> 00:04:50,570 號 105 00:04:50,570 --> 00:04:51,550 按照下一個。 106 00:04:51,550 --> 00:04:55,490 >> 因此,我們必須以實際循環 通過我們的鏈接列表。 107 00:04:55,490 --> 00:05:00,070 我們不能只是去直接到9。 108 00:05:00,070 --> 00:05:05,860 如果你們真的想 看到一些偽代碼在那裡。 109 00:05:05,860 --> 00:05:10,420 在這裡,我們有一些搜索功能 這需要in--需要做些什麼呢? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 你有什麼感想? 112 00:05:14,320 --> 00:05:15,960 那麼容易的。 113 00:05:15,960 --> 00:05:17,784 這是什麼? 114 00:05:17,784 --> 00:05:18,700 聽眾:[聽不清]。 115 00:05:18,700 --> 00:05:20,366 揚聲器1:我們正在尋找的數量。 116 00:05:20,366 --> 00:05:20,980 對不對? 117 00:05:20,980 --> 00:05:22,875 什麼會這樣對應? 118 00:05:22,875 --> 00:05:25,020 這是一個指針? 119 00:05:25,020 --> 00:05:26,000 >> 聽眾:一個節點。 120 00:05:26,000 --> 00:05:28,980 >> 揚聲器1:節點列表 我們正在尋找的,對不對? 121 00:05:28,980 --> 00:05:33,700 因此,我們有一些節點的指針位置。 122 00:05:33,700 --> 00:05:37,240 這是一個點,那將 通過我們的名單實際上迭代。 123 00:05:37,240 --> 00:05:39,630 我們設置它等於列表 因為這只是 124 00:05:39,630 --> 00:05:44,380 設置它等於 開始我們的鍊錶。 125 00:05:44,380 --> 00:05:50,660 >> 雖然它不為NULL,而 我們還有東西在我們的列表中, 126 00:05:50,660 --> 00:05:55,580 檢查,看看是否有節點 我們正在尋找的數字。 127 00:05:55,580 --> 00:05:57,740 返回true。 128 00:05:57,740 --> 00:06:01,070 否則,更新它,對不對? 129 00:06:01,070 --> 00:06:04,870 >> 如果為NULL,我們退出我們 while循環並返回false 130 00:06:04,870 --> 00:06:08,340 因為這意味著我們還沒有找到它。 131 00:06:08,340 --> 00:06:11,048 每個人都得到如何工作的? 132 00:06:11,048 --> 00:06:11,548 行。 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> 因此,與插入,你 有三種不同的方式。 135 00:06:20,260 --> 00:06:25,250 您可以預先準備,可以追加 你可以插入到什。 136 00:06:25,250 --> 00:06:28,215 在這種情況下,我們 打算做一個預先準備。 137 00:06:28,215 --> 00:06:33,380 有誰知道這些 3案件可能會有所不同? 138 00:06:33,380 --> 00:06:36,920 >> 所以在前面加上意味著你把 它在列表的前面。 139 00:06:36,920 --> 00:06:39,770 因此,這將意味著,不管 你的節點,無論 140 00:06:39,770 --> 00:06:43,160 價值是什麼,你要 把它放在這裡在前面,好不好? 141 00:06:43,160 --> 00:06:45,160 這將成為第一 元素在列表中。 142 00:06:45,160 --> 00:06:49,510 >> 如果您添加它,它是怎麼回事 去你的列表的後面。 143 00:06:49,510 --> 00:06:54,010 並插入到什意味著你 打算把實際進入的地方 144 00:06:54,010 --> 00:06:57,700 它讓你的鏈接列表進行排序。 145 00:06:57,700 --> 00:07:00,810 同樣,你如何使用 這些,當你使用 146 00:07:00,810 --> 00:07:02,530 他們會根據你的情況而有所不同。 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 如果不需要 進行排序,在前面加上趨於 149 00:07:07,750 --> 00:07:10,460 是大多數人 使用,因為你不知道 150 00:07:10,460 --> 00:07:15,680 要經過整個列表 尋找到底添加它,對不對? 151 00:07:15,680 --> 00:07:17,720 你可以把它貼對世權。 152 00:07:17,720 --> 00:07:21,930 >> 因此,我們將通過一個 插入1現在。 153 00:07:21,930 --> 00:07:26,360 這麼一件事,我要去 強烈建議在此PSET 154 00:07:26,360 --> 00:07:29,820 是畫出來的東西,一如既往。 155 00:07:29,820 --> 00:07:35,130 這是你更新是非常重要的 以正確的順序你的指針 156 00:07:35,130 --> 00:07:38,620 因為如果你更新它們 稍微亂序, 157 00:07:38,620 --> 00:07:42,210 你要結束了 失去你的列表的一部分。 158 00:07:42,210 --> 00:07:49,680 >> 因此,例如,在這種情況下,我們 告訴頭只點1。 159 00:07:49,680 --> 00:07:56,070 如果我們只是做了 不保存這個1, 160 00:07:56,070 --> 00:07:58,570 我們不知道是什麼 1應指向現在 161 00:07:58,570 --> 00:08:02,490 因為我們已經失去了什麼 該負責人指出。 162 00:08:02,490 --> 00:08:05,530 所以,有一點要記住 當你做了預先準備 163 00:08:05,530 --> 00:08:09,630 是拯救什麼 頭分排名第一, 164 00:08:09,630 --> 00:08:15,210 然後重新分配它,然後更新 你的新節點應該指向。 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 在這種情況下,這是為了做到這一點的方法之一。 167 00:08:22,560 --> 00:08:25,440 >> 因此,如果我們做了這種方式 在這裡我們只是重新分配頭, 168 00:08:25,440 --> 00:08:30,320 我們失去了我們的基本 整個列表,對不對? 169 00:08:30,320 --> 00:08:38,000 做到這一點的方法之一是有1個點 接下來,再有頭點1。 170 00:08:38,000 --> 00:08:42,650 或者,你可以種不喜歡的 臨時存儲,這是我所津津樂道。 171 00:08:42,650 --> 00:08:45,670 >> 但是,重新分配你的 以正確的順序指針 172 00:08:45,670 --> 00:08:48,750 將是非常,非常 重要的是這個PSET。 173 00:08:48,750 --> 00:08:53,140 否則,你將有一個哈希 表或一個嘗試,這只是將要 174 00:08:53,140 --> 00:08:56,014 的話只有部分是你 想要再you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 聽眾:什麼是臨時 存儲的東西你在說什麼? 176 00:08:58,930 --> 00:09:00,305 揚聲器1:臨時存儲。 177 00:09:00,305 --> 00:09:02,760 所以基本上另一 這樣你可以這樣做 178 00:09:02,760 --> 00:09:07,650 是存放東西的腦袋,像 存放臨時變量。 179 00:09:07,650 --> 00:09:11,250 其分配到1 然後更新1點 180 00:09:11,250 --> 00:09:13,830 以什麼頭用來指向。 181 00:09:13,830 --> 00:09:16,920 這種方式顯然是 因為你更優雅 182 00:09:16,920 --> 00:09:20,770 不需要一個臨時值,但 只是提供了另一種方式來做到這一點。 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 而我們實際上做有 一些代碼這一點。 185 00:09:25,790 --> 00:09:28,080 所以對於鍊錶,我們 實際上有一些代碼。 186 00:09:28,080 --> 00:09:31,930 所以在此處插入,這是預先考慮。 187 00:09:31,930 --> 00:09:34,290 所以這個進入它的頭。 188 00:09:34,290 --> 00:09:38,820 >> 所以第一件事情,你需要 當然,創造你的新節點, 189 00:09:38,820 --> 00:09:40,790 並檢查是否為NULL。 190 00:09:40,790 --> 00:09:43,250 總是好的。 191 00:09:43,250 --> 00:09:47,840 然後你需要指定的值。 192 00:09:47,840 --> 00:09:51,260 當你創建一個新的節點,你 不知道它的指向下一個, 193 00:09:51,260 --> 00:09:54,560 所以你想要初始化為NULL。 194 00:09:54,560 --> 00:09:58,760 如果它最終指向事 否則,它就會被重新分配,它的罰款。 195 00:09:58,760 --> 00:10:00,740 如果這是第一件事情 在列表中,則需要 196 00:10:00,740 --> 00:10:04,270 指向null,因為 這是該列表的末尾。 197 00:10:04,270 --> 00:10:12,410 >> 所以後來插入的話,我們在這裡看到我們 被分配了節點的下一個值 198 00:10:12,410 --> 00:10:17,380 是什麼頭, 這就是我們不得不在這裡。 199 00:10:17,380 --> 00:10:19,930 這就是我們只是做了。 200 00:10:19,930 --> 00:10:25,820 然後我們分配頭點 我們的新節點,因為要記住, 201 00:10:25,820 --> 00:10:31,090 新是一些指針到一個節點, 而這正是頭是什麼。 202 00:10:31,090 --> 00:10:34,370 這就是為什麼我們 有這個箭頭訪問。 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 很酷吧? 205 00:10:37,530 --> 00:10:38,130 Mmhmm​​? 206 00:10:38,130 --> 00:10:41,100 >> 聽眾:我們得 初始化新的下一位第一為NULL, 207 00:10:41,100 --> 00:10:44,240 或者我們只是把它初始化為頭? 208 00:10:44,240 --> 00:10:48,210 >> 揚聲器1:新下一個 需要為NULL啟動 209 00:10:48,210 --> 00:10:53,760 因為你不知道 那裡將是。 210 00:10:53,760 --> 00:10:56,100 此外,這是怎麼樣的 就像一個範例。 211 00:10:56,100 --> 00:10:59,900 你將其設置為NULL只是為了 確保你所有的基地都覆蓋 212 00:10:59,900 --> 00:11:04,070 你這樣做,任何重新分配前 你總是保證它會 213 00:11:04,070 --> 00:11:08,880 被指向的特定值 與像一個垃圾值。 214 00:11:08,880 --> 00:11:12,210 因為,是的,我們分配 新的自動接下來, 215 00:11:12,210 --> 00:11:15,420 但它更多的只是像 好的做法進行初始化 216 00:11:15,420 --> 00:11:19,270 以這種方式,並重新分配。 217 00:11:19,270 --> 00:11:23,420 >> 好了,現在雙鍊錶。 218 00:11:23,420 --> 00:11:24,601 我們怎麼想的? 219 00:11:24,601 --> 00:11:26,350 有什麼不同 雙向鍊錶? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> 所以在我們的鍊錶,我們可以 只朝一個方向,對不對? 222 00:11:34,300 --> 00:11:35,270 我們只有下一個。 223 00:11:35,270 --> 00:11:36,760 我們只能往前走。 224 00:11:36,760 --> 00:11:40,300 >> 用一個雙向鍊錶, 我們還可以向後移動。 225 00:11:40,300 --> 00:11:44,810 因此,我們不僅 我們要存儲號碼, 226 00:11:44,810 --> 00:11:50,110 我們有它指向下一個 當我們剛剛從。 227 00:11:50,110 --> 00:11:52,865 所以這允許 一些更好的遍歷。 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> 因此,雙向鍊錶節點, 非常相似的,對不對? 230 00:12:01,240 --> 00:12:05,000 唯一不同的是,現在我們 有下一個和前一個。 231 00:12:05,000 --> 00:12:06,235 這是唯一的區別。 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> 所以,如果我們要在前面或append--我們 沒有任何代碼此向上這裡 - 234 00:12:14,790 --> 00:12:17,830 但如果你要嘗試 插入,最重要的事情 235 00:12:17,830 --> 00:12:19,980 就是你需要 確保你分配 236 00:12:19,980 --> 00:12:23,360 無論你以前和你 下一個指針正常。 237 00:12:23,360 --> 00:12:29,010 因此,在這種情況下,你會 不僅初始化旁邊, 238 00:12:29,010 --> 00:12:31,820 在初始化以前。 239 00:12:31,820 --> 00:12:36,960 如果我們在列表的頭部,我們 不但使頭部等於新, 240 00:12:36,960 --> 00:12:41,750 但我們的新的前應 點了頭,對吧? 241 00:12:41,750 --> 00:12:43,380 >> 這是唯一的區別。 242 00:12:43,380 --> 00:12:47,200 如果你想有更多的實踐 這些用鍊錶,用插入, 243 00:12:47,200 --> 00:12:49,900 與刪除,插入帶 成什錦列表, 244 00:12:49,900 --> 00:12:52,670 請查看study.cs50.net。 245 00:12:52,670 --> 00:12:54,870 有一群偉大的演習。 246 00:12:54,870 --> 00:12:55,870 我極力推薦他們。 247 00:12:55,870 --> 00:12:59,210 我希望我們有時間去通過他們 但有很多數據結構 248 00:12:59,210 --> 00:13:01,530 打通。 249 00:13:01,530 --> 00:13:02,650 >> 好了,哈希表。 250 00:13:02,650 --> 00:13:07,070 這可能是最 您PSET有用位 251 00:13:07,070 --> 00:13:11,090 在這裡,因為你將要 執行其中的一個或一試。 252 00:13:11,090 --> 00:13:12,200 我真的很喜歡哈希表。 253 00:13:12,200 --> 00:13:13,110 他們很酷。 254 00:13:13,110 --> 00:13:17,080 >> 所以基本上什麼 發生的情況是一個哈希表 255 00:13:17,080 --> 00:13:22,050 當我們真正需要迅速 插入,刪除和查找。 256 00:13:22,050 --> 00:13:25,010 這些都是東西,我們 在哈希表中優先考慮。 257 00:13:25,010 --> 00:13:29,500 他們可以得到相當大的, 但我們會嘗試用看, 258 00:13:29,500 --> 00:13:33,040 有些事情是要大得多。 259 00:13:33,040 --> 00:13:38,330 >> 但基本上,所有的散列 表是散列函數 260 00:13:38,330 --> 00:13:47,215 告訴你哪個桶把每 您的數據,每一個在你的元素。 261 00:13:47,215 --> 00:13:51,140 一個簡單的方法去思考一個哈希表 是它的事情只是水桶, 262 00:13:51,140 --> 00:13:51,770 對不對? 263 00:13:51,770 --> 00:13:59,720 所以,當你被排序的東西 就像他們的名字的第一個字母, 264 00:13:59,720 --> 00:14:01,820 這有點像一個哈希表。 265 00:14:01,820 --> 00:14:06,180 >> 所以,如果我是組你們是 到誰的名字開始組 266 00:14:06,180 --> 00:14:11,670 用A看過來,或者誰的生日 在一月,二月,三月, 267 00:14:11,670 --> 00:14:15,220 什麼,那就是有效 創建哈希表。 268 00:14:15,220 --> 00:14:18,120 它只是創造了水桶 你的元素進行排序成 269 00:14:18,120 --> 00:14:19,520 這樣您就可以找到他們更容易。 270 00:14:19,520 --> 00:14:22,300 所以這樣一來,當我需要 找一個你, 271 00:14:22,300 --> 00:14:24,680 我沒有搜索 通過您的每一個名字。 272 00:14:24,680 --> 00:14:29,490 我可以想,哦,我知道, 丹妮的生日是in-- 273 00:14:29,490 --> 00:14:30,240 聽眾:--April。 274 00:14:30,240 --> 00:14:30,948 揚聲器1:四月。 275 00:14:30,948 --> 00:14:33,120 所以我看在我四月份 鬥,與任何運氣, 276 00:14:33,120 --> 00:14:38,270 她會在那裡唯一的一個, 我的時間是在這個意義上不變, 277 00:14:38,270 --> 00:14:41,230 而如果我要看看 通過一大堆的人, 278 00:14:41,230 --> 00:14:43,090 這將花費更長的時間。 279 00:14:43,090 --> 00:14:45,830 因此,哈希表是真的只是水桶。 280 00:14:45,830 --> 00:14:48,630 簡單的方法,他們的看法。 281 00:14:48,630 --> 00:14:52,930 >> 因此,關於一個很重要的事情 哈希表是一個散列函數。 282 00:14:52,930 --> 00:14:58,140 所以事情我剛才講的,像 您的名字的第一個字母 283 00:14:58,140 --> 00:15:01,450 或者你的生日月, 這些想法, 284 00:15:01,450 --> 00:15:03,070 真關聯到哈希函數。 285 00:15:03,070 --> 00:15:08,900 這是確定的只是一個方式,也 鬥你是元素進入,OK? 286 00:15:08,900 --> 00:15:14,850 因此,對於這pset中,你可以看一下 幾乎任何你想要的哈希函數。 287 00:15:14,850 --> 00:15:16,030 >> 並不一定是你自己。 288 00:15:16,030 --> 00:15:21,140 有一些很酷的的人了 那裡,做各種瘋狂的數學。 289 00:15:21,140 --> 00:15:25,170 如果你想使你的 拼寫檢查超快, 290 00:15:25,170 --> 00:15:27,620 我肯定會 看看其中的一個。 291 00:15:27,620 --> 00:15:32,390 >> 但也有在 簡單的,如計算 292 00:15:32,390 --> 00:15:39,010 的話,總和一樣 每個字母的數。 293 00:15:39,010 --> 00:15:39,940 計算總和。 294 00:15:39,940 --> 00:15:42,230 用於確定桶。 295 00:15:42,230 --> 00:15:45,430 他們也有難辦的 就像所有的A的位置, 296 00:15:45,430 --> 00:15:47,050 所有的B的在這裡。 297 00:15:47,050 --> 00:15:48,920 這些中的任何一個。 298 00:15:48,920 --> 00:15:55,770 >> 基本上,它只是告訴你哪個 數組索引你的元素應該進入。 299 00:15:55,770 --> 00:15:58,690 剛剛決定bucket-- 這是所有的哈希函數是。 300 00:15:58,690 --> 00:16:04,180 所以在這裡,我們有一個例子是 字符串的只是第一信 301 00:16:04,180 --> 00:16:05,900 我只是在談論。 302 00:16:05,900 --> 00:16:11,900 >> 所以,你有一些散,這僅僅是 您的字符串減去A的第一個字母, 303 00:16:11,900 --> 00:16:16,090 這會給你一些 介於0和25號。 304 00:16:16,090 --> 00:16:20,790 和你想要做的是什麼 確保這代表 305 00:16:20,790 --> 00:16:24,110 您的散列的大小table-- 多少個水桶也有。 306 00:16:24,110 --> 00:16:25,860 許多這類 散列函數,它們是 307 00:16:25,860 --> 00:16:31,630 將要返回的值可能 要遠遠高於桶的數量 308 00:16:31,630 --> 00:16:33,610 那你確實有 在哈希表 309 00:16:33,610 --> 00:16:37,240 所以你需要 肯定和那些國防部。 310 00:16:37,240 --> 00:16:42,190 否則,它會說, 哦,應該是在5000桶 311 00:16:42,190 --> 00:16:46,040 但你只有30 水桶中的哈希表。 312 00:16:46,040 --> 00:16:49,360 當然,我們都知道這是 會導致一些瘋狂的錯誤。 313 00:16:49,360 --> 00:16:52,870 所以一定要確保由於MOD 您的哈希表的大小。 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 涼爽。 316 00:16:58,930 --> 00:17:00,506 所以碰撞。 317 00:17:00,506 --> 00:17:02,620 是每個人都好這麼遠嗎? 318 00:17:02,620 --> 00:17:03,120 Mmhmm​​? 319 00:17:03,120 --> 00:17:05,900 >> 聽眾:為什麼會 返回這樣一個龐大的價值呢? 320 00:17:05,900 --> 00:17:09,210 >> 揚聲器1:根據不同的算法 您的哈希函數使用。 321 00:17:09,210 --> 00:17:12,270 有些人會做 瘋狂繁殖。 322 00:17:12,270 --> 00:17:16,270 它的所有有關獲取 一個均勻分佈, 323 00:17:16,270 --> 00:17:18,490 所以他們做一些真正 有時是瘋狂的事情。 324 00:17:18,490 --> 00:17:20,960 就這樣。 325 00:17:20,960 --> 00:17:22,140 還要別的嗎? 326 00:17:22,140 --> 00:17:22,829 行。 327 00:17:22,829 --> 00:17:24,480 >> 所以碰撞。 328 00:17:24,480 --> 00:17:29,270 基本上,正如我剛才所說, 在最好的情況下, 329 00:17:29,270 --> 00:17:32,040 任何鬥我看看是 將有一件事, 330 00:17:32,040 --> 00:17:34,160 所以我沒有看全,對不對? 331 00:17:34,160 --> 00:17:37,040 我不是知道它的存在,或者它 不,這是我們真正想要的。 332 00:17:37,040 --> 00:17:43,960 但是,如果我們有數万 數據點和小於號 333 00:17:43,960 --> 00:17:48,700 桶,我們將有 碰撞中,最終的東西 334 00:17:48,700 --> 00:17:54,210 即將要結束了 鬥已經有一個元素。 335 00:17:54,210 --> 00:17:57,390 >> 所以,問題是,什麼樣 我們在這種情況下怎麼辦? 336 00:17:57,390 --> 00:17:58,480 我們該怎麼辦? 337 00:17:58,480 --> 00:17:59,300 我們已經有了的東西呢? 338 00:17:59,300 --> 00:18:00,060 難道我們只是把它扔出去? 339 00:18:00,060 --> 00:18:00,700 >> 號 340 00:18:00,700 --> 00:18:01,980 我們必須保持他們兩個。 341 00:18:01,980 --> 00:18:06,400 這樣的方式,我們 通常做的是什麼嗎? 342 00:18:06,400 --> 00:18:08,400 是什麼數據結構 我們剛才講? 343 00:18:08,400 --> 00:18:09,316 聽眾:鍊錶。 344 00:18:09,316 --> 00:18:10,500 揚聲器1:鍊錶。 345 00:18:10,500 --> 00:18:16,640 所以,現在的,而不是每個這些 水桶只是有一個元素, 346 00:18:16,640 --> 00:18:24,020 它會包含一個鏈接列表 這被散列到它的元素。 347 00:18:24,020 --> 00:18:27,588 好了,大家都種得出來的? 348 00:18:27,588 --> 00:18:30,546 因為我們不能有一個數組 因為我們不知道有多少東西 349 00:18:30,546 --> 00:18:31,730 將要在那裡。 350 00:18:31,730 --> 00:18:36,540 鍊錶可以讓我們 剛剛確切的數字, 351 00:18:36,540 --> 00:18:38,465 被散列成水桶,對不對? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> 所以線性探測是 基本上這idea-- 354 00:18:50,500 --> 00:18:52,300 這是應對碰撞的一種方式。 355 00:18:52,300 --> 00:18:58,010 你可以做的是,如果在這 情況下,漿果被散列到1 356 00:18:58,010 --> 00:19:01,130 我們已經有了 那裡的東西,你只要 357 00:19:01,130 --> 00:19:04,840 繼續下去,直到 你找到一個空槽。 358 00:19:04,840 --> 00:19:06,370 這是一種方式來處理它。 359 00:19:06,370 --> 00:19:09,020 另一種方式來處理 它是我們剛才 360 00:19:09,020 --> 00:19:12,280 called--鏈接 列表被稱為鏈接。 361 00:19:12,280 --> 00:19:20,510 >> 所以這個想法,如果工作 您的哈希表,你認為 362 00:19:20,510 --> 00:19:24,150 比大得多 您的數據集,或者如果你 363 00:19:24,150 --> 00:19:28,870 想嘗試和減少鏈接 直到它的絕對必要。 364 00:19:28,870 --> 00:19:34,050 因此,有一點是線性的 探測手段明顯 365 00:19:34,050 --> 00:19:37,290 您的散列函數 是不是很實用 366 00:19:37,290 --> 00:19:42,200 因為你要使用到結束 您的散列函數,得到一個點, 367 00:19:42,200 --> 00:19:46,400 你的線陣探頭向下 一些地方可用。 368 00:19:46,400 --> 00:19:49,670 但現在,當然,任何事情 別人說結束了那裡, 369 00:19:49,670 --> 00:19:52,050 你將不得不 搜索甚至進一步下跌。 370 00:19:52,050 --> 00:19:55,650 >> 而且還有很多更 搜索的費用 371 00:19:55,650 --> 00:19:59,820 進入輸入一個元素 在現在的哈希表,對不對? 372 00:19:59,820 --> 00:20:05,640 而現在,當你去嘗試和發現 漿果再次,你要湊吧, 373 00:20:05,640 --> 00:20:07,742 而且它會說, 哦,在鬥1看, 374 00:20:07,742 --> 00:20:09,700 而且它不會是 在鬥1,所以你 375 00:20:09,700 --> 00:20:11,970 將不得不穿越 通過對這些休息。 376 00:20:11,970 --> 00:20:17,720 所以,它有時是有用的, 但在大多數情況下, 377 00:20:17,720 --> 00:20:22,660 我們要指出, 鏈接是你想做的事。 378 00:20:22,660 --> 00:20:25,520 >> 所以,我們談到了這點。 379 00:20:25,520 --> 00:20:27,812 我得到了我自己一點點前進。 380 00:20:27,812 --> 00:20:33,560 但鏈基本上是 在哈希表中的每一桶 381 00:20:33,560 --> 00:20:36,120 僅僅是一個鍊錶。 382 00:20:36,120 --> 00:20:39,660 >> 這樣的另一種方式,或更多的技術 這樣,想到一個哈希表 383 00:20:39,660 --> 00:20:44,490 是,它只是一個數組 鍊錶,哪 384 00:20:44,490 --> 00:20:49,330 你寫你的字典時, 而你試圖加載它, 385 00:20:49,330 --> 00:20:52,070 想到它是一個 鍊錶的數組 386 00:20:52,070 --> 00:20:54,390 將使它更容易 為您初始化。 387 00:20:54,390 --> 00:20:57,680 >> 聽眾:所以哈希表 具有預定的大小, 388 00:20:57,680 --> 00:20:58,980 像水桶的[聽不清]? 389 00:20:58,980 --> 00:20:59,220 >> 揚聲器1:沒錯。 390 00:20:59,220 --> 00:21:01,655 所以它有一組數 你determine--桶 391 00:21:01,655 --> 00:21:03,530 這你們應該 隨便玩。 392 00:21:03,530 --> 00:21:05,269 它可以是很酷 看看會發生什麼 393 00:21:05,269 --> 00:21:06,810 當你改變你的桶數。 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 但是,是的,它有一個 桶的設置數量。 396 00:21:11,510 --> 00:21:15,360 是什麼讓你滿足的 因為你需要很多元素 397 00:21:15,360 --> 00:21:19,350 這是單獨的鏈接,你 已在每個桶鍊錶。 398 00:21:19,350 --> 00:21:22,850 這意味著你的哈希表 會完全大小 399 00:21:22,850 --> 00:21:25,440 你需要它,對不對? 400 00:21:25,440 --> 00:21:27,358 這就是鍊錶的整點。 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 涼爽。 403 00:21:32,480 --> 00:21:38,780 >> 所以每個人都需要幫助嗎? 404 00:21:38,780 --> 00:21:39,801 行。 405 00:21:39,801 --> 00:21:40,300 啊。 406 00:21:40,300 --> 00:21:41,860 剛剛發生了什麼? 407 00:21:41,860 --> 00:21:42,960 現在真的。 408 00:21:42,960 --> 00:21:45,250 猜猜誰是殺害我。 409 00:21:45,250 --> 00:21:52,060 >> OK,我們要進入 嘗試,這是一個有點瘋狂。 410 00:21:52,060 --> 00:21:53,140 我喜歡的哈希表。 411 00:21:53,140 --> 00:21:54,460 我覺得他們真的很酷。 412 00:21:54,460 --> 00:21:56,710 嘗試涼爽了。 413 00:21:56,710 --> 00:21:59,590 >> 因此,沒有人記得一試的是? 414 00:21:59,590 --> 00:22:01,740 你應該已經走了過來 它簡要地講? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 你還記得那種它是如何工作的? 417 00:22:06,377 --> 00:22:08,460 聽眾:我只是點頭 我們也去了吧。 418 00:22:08,460 --> 00:22:09,626 揚聲器1:我們過目一下。 419 00:22:09,626 --> 00:22:13,100 OK,我們真的要去 在它現在是我們在說什麼。 420 00:22:13,100 --> 00:22:14,860 >> 聽眾:這是一個檢索樹。 421 00:22:14,860 --> 00:22:15,280 >> 揚聲器1:是啊。 422 00:22:15,280 --> 00:22:16,196 這是一個檢索樹。 423 00:22:16,196 --> 00:22:16,960 真棒。 424 00:22:16,960 --> 00:22:23,610 所以,有一點這裡要注意的是,我們 正在尋找單個字符 425 00:22:23,610 --> 00:22:24,480 在這裡,對不對? 426 00:22:24,480 --> 00:22:29,710 >> 所以在我們的哈希函數,我們 所尋找的單詞作為一個整體, 427 00:22:29,710 --> 00:22:32,270 現在我們正在尋找更多的 在人物了吧? 428 00:22:32,270 --> 00:22:38,380 因此,我們有麥克斯韋在這裡和孟德爾。 429 00:22:38,380 --> 00:22:47,840 所以基本上一個try--的方式來思考 這個是每個層次在這裡 430 00:22:47,840 --> 00:22:49,000 是字母數組。 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 因此,這是你的根結在這裡,對不對? 433 00:22:55,790 --> 00:23:01,980 這具有的所有字符 字母的每一個字的開始。 434 00:23:01,980 --> 00:23:06,480 >> 和你想要做的是什麼 說好,我們有一些M個字。 435 00:23:06,480 --> 00:23:10,590 我們要尋找麥克斯韋,所以 我們去的M.和M點整 436 00:23:10,590 --> 00:23:14,800 另外一個數組,其中每 總之,只要存在 437 00:23:14,800 --> 00:23:17,044 是一個具有一個字 作為第二個字母, 438 00:23:17,044 --> 00:23:19,460 只要有一個字 有B作為第二個字母, 439 00:23:19,460 --> 00:23:24,630 它將有一個指針 去一些旁邊的數組。 440 00:23:24,630 --> 00:23:29,290 >> 有可能不是一個 詞MP的東西, 441 00:23:29,290 --> 00:23:32,980 所以在此P位置 數組,它只是為NULL。 442 00:23:32,980 --> 00:23:38,840 它會說,OK,沒有字 即有m個後跟一個P,好不好? 443 00:23:38,840 --> 00:23:43,100 因此,如果我們仔細想想,每個 這些較小的事情之一 444 00:23:43,100 --> 00:23:47,990 實際上是其中之一 到Z大陣列從A 445 00:23:47,990 --> 00:23:55,064 那麼,什麼可能的事情之一 這是怎樣的一個嘗試的缺點呢? 446 00:23:55,064 --> 00:23:56,500 >> 聽眾:大量的內存。 447 00:23:56,500 --> 00:23:59,940 >> 揚聲器1:這是一噸的記憶,不是嗎? 448 00:23:59,940 --> 00:24:08,750 每一個這些塊在這裡 代表26位,26個元素的數組。 449 00:24:08,750 --> 00:24:13,680 因此,試圖獲得令人難以置信的太空沉重。 450 00:24:13,680 --> 00:24:17,100 >> 但他們都非常快。 451 00:24:17,100 --> 00:24:22,540 如此令人難以置信的速度快,但 真是浪費空間。 452 00:24:22,540 --> 00:24:24,810 那種有圖 哪一個你想要的。 453 00:24:24,810 --> 00:24:29,470 這是真的很酷您PSET, 但他們佔用了大量的內存, 454 00:24:29,470 --> 00:24:30,290 所以你權衡。 455 00:24:30,290 --> 00:24:31,480 是嗎? 456 00:24:31,480 --> 00:24:34,300 >> 聽眾:有沒有可能 建立一個嘗試,然後 457 00:24:34,300 --> 00:24:37,967 一旦你把所有的 你need--在它的數據 458 00:24:37,967 --> 00:24:39,550 我不知道這是否會是有意義的。 459 00:24:39,550 --> 00:24:42,200 我擺脫所有 NULL字符,但隨後 460 00:24:42,200 --> 00:24:42,910 你就不能夠索引them-- 461 00:24:42,910 --> 00:24:43,275 >> 揚聲器1:您仍然需要他們。 462 00:24:43,275 --> 00:24:44,854 >> 聽眾: - 每次以相同的方式。 463 00:24:44,854 --> 00:24:45,520 揚聲器1:是啊。 464 00:24:45,520 --> 00:24:50,460 您需要NULL字符來讓 你知道,如果有沒有一個字出現。 465 00:24:50,460 --> 00:24:52,040 奔你有什麼,你想要什麼? 466 00:24:52,040 --> 00:24:52,540 行。 467 00:24:52,540 --> 00:24:54,581 好了,所以我們要 去多一點點 468 00:24:54,581 --> 00:24:58,920 進入技術細節的背後 一試,並通過一個實例運行。 469 00:24:58,920 --> 00:25:01,490 >> 好了,這是同樣的事情。 470 00:25:01,490 --> 00:25:06,290 而在一個鍊錶,我們的主要 那種of--什麼是我想要的字? - 471 00:25:06,290 --> 00:25:08,350 像積木是一個節點。 472 00:25:08,350 --> 00:25:12,280 在一個嘗試,我們也有一個節點, 但它的定義不同。 473 00:25:12,280 --> 00:25:17,000 >> 因此,我們有一些布爾值, 代表實際上無論是詞 474 00:25:17,000 --> 00:25:23,530 存在於這個位置,然後 我們有一些陣這裡 - 或者更確切地說, 475 00:25:23,530 --> 00:25:27,840 這是一個指向 陣列的27個字符。 476 00:25:27,840 --> 00:25:33,339 這是因為,在這種情況下,這 27--我相信在座的各位都是這樣,等待, 477 00:25:33,339 --> 00:25:34,880 有字母表中的26個字母。 478 00:25:34,880 --> 00:25:36,010 為什麼我們有27? 479 00:25:36,010 --> 00:25:37,870 >> 這樣根據不同的 要實現這種方式, 480 00:25:37,870 --> 00:25:43,240 這是從一個pset中那 允許撇號。 481 00:25:43,240 --> 00:25:46,010 所以這就是為什麼額外的之一。 482 00:25:46,010 --> 00:25:50,500 您還可以有一些 情況下,空終止 483 00:25:50,500 --> 00:25:53,230 被包含的所述一個 即它允許為字符, 484 00:25:53,230 --> 00:25:56,120 這就是他們如何檢查 看它是否是該字的結束。 485 00:25:56,120 --> 00:26:01,340 如果您有興趣,請查看 凱文的視頻study.cs50, 486 00:26:01,340 --> 00:26:04,790 以及維基百科 一些很好的資源在那裡。 487 00:26:04,790 --> 00:26:09,000 >> 但是,我們要通過正中下懷 您可能如何工作,通過一試 488 00:26:09,000 --> 00:26:11,010 如果你正在考慮之一。 489 00:26:11,010 --> 00:26:16,230 因此,我們有一個超級簡單的在這裡, 有句話“蝙蝠”和“縮放”在其中。 490 00:26:16,230 --> 00:26:18,920 正如我們看到的在這裡, 在這裡這個小空間 491 00:26:18,920 --> 00:26:22,560 代表了我們的布爾值, 說,是的,這是一個字。 492 00:26:22,560 --> 00:26:27,060 然後這有我們 字符數組,對不對? 493 00:26:27,060 --> 00:26:33,480 >> 所以,我們要通過 發現在這個嘗試“蝙蝠”。 494 00:26:33,480 --> 00:26:38,340 所以,從高層開始,對不對? 495 00:26:38,340 --> 00:26:46,290 我們知道,B對應 第二索引,所述第二元件 496 00:26:46,290 --> 00:26:47,840 在這個陣列中,因為a和b。 497 00:26:47,840 --> 00:26:51,340 所以大約第二個。 498 00:26:51,340 --> 00:26:58,820 >> 它說,OK,冷靜,按照成 下一個陣列,因為如果我們記得, 499 00:26:58,820 --> 00:27:02,160 這並不是說所有這些 實際上包含元件。 500 00:27:02,160 --> 00:27:07,110 這些陣列中的每一個 包含一個指針,對不對? 501 00:27:07,110 --> 00:27:10,030 這是做一個重要的區別。 502 00:27:10,030 --> 00:27:13,450 >> 我知道這是要be--嘗試的 真的很難得上是第一次, 503 00:27:13,450 --> 00:27:15,241 所以,即使是這樣的 第二次或第三次 504 00:27:15,241 --> 00:27:18,370 而且它仍然是一種 看似很難的, 505 00:27:18,370 --> 00:27:21,199 我保證,如果你去觀看 短期再度明天 506 00:27:21,199 --> 00:27:22,740 這可能會使得很多更有意義。 507 00:27:22,740 --> 00:27:23,890 這需要大量的消化。 508 00:27:23,890 --> 00:27:27,800 我有時仍然很 象,等等,什麼是一試? 509 00:27:27,800 --> 00:27:29,080 我該如何使用呢? 510 00:27:29,080 --> 00:27:33,880 >> 所以我們B在這種情況下, 這是我們的第二個索引。 511 00:27:33,880 --> 00:27:40,240 如果我們有,比方說,C或 d或任何其他字母, 512 00:27:40,240 --> 00:27:45,810 我們需要映射回索引 我們的數組的對應。 513 00:27:45,810 --> 00:27:56,930 因此,我們將採取類似rchar,我們只是 減去掀起了將其映射到0〜25。 514 00:27:56,930 --> 00:27:58,728 大家好,我們怎麼樣 地圖我們的角色? 515 00:27:58,728 --> 00:28:00,440 行。 516 00:28:00,440 --> 00:28:05,980 >> 所以我們去的第二個和我們 看,是的,它不是為NULL。 517 00:28:05,980 --> 00:28:07,780 我們可以繼續在下一個數組。 518 00:28:07,780 --> 00:28:12,300 所以我們去到這一個陣列在這裡。 519 00:28:12,300 --> 00:28:15,500 >> 和我們說,好了,現在我們 需要看到,如果是在這裡。 520 00:28:15,500 --> 00:28:18,590 為空或做它 其實往前走? 521 00:28:18,590 --> 00:28:21,880 所以實際上移動 轉發此數組中。 522 00:28:21,880 --> 00:28:24,570 我們說好,t是我們的最後一個字母。 523 00:28:24,570 --> 00:28:27,580 所以我們去到T的索引。 524 00:28:27,580 --> 00:28:30,120 然後我們繼續前進 因為有另一個。 525 00:28:30,120 --> 00:28:38,340 而這一次,基本上說,是的, 它說,有一句話這裡 - 526 00:28:38,340 --> 00:28:41,750 如果你遵循這一點, 路徑,你已經到了 527 00:28:41,750 --> 00:28:43,210 在一個字,這是我們所知道的是“蝙蝠”。 528 00:28:43,210 --> 00:28:43,800 是嗎? 529 00:28:43,800 --> 00:28:46,770 >> 聽眾:是不是標準有 為索引0,然後有一個排序的1 530 00:28:46,770 --> 00:28:47,660 或有在結束了嗎? 531 00:28:47,660 --> 00:28:48,243 >> 揚聲器1:第 532 00:28:48,243 --> 00:28:55,360 因此,如果我們回頭看我們的 在這裡聲明,這是一個布爾值, 533 00:28:55,360 --> 00:28:59,490 所以它在你的節點自身的元素。 534 00:28:59,490 --> 00:29:03,331 所以它不是數組的一部分。 535 00:29:03,331 --> 00:29:03,830 涼爽。 536 00:29:03,830 --> 00:29:08,370 所以,當我們完成我們的話,我們很 在這個數組,我們想要做的 537 00:29:08,370 --> 00:29:12,807 是做一個檢查,這是一個單詞。 538 00:29:12,807 --> 00:29:14,390 在這種情況下,它會返回是。 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> 所以,關於這一點,我們知道“動物園” - 我們知道,作為人類的“動物園”是一個詞, 541 00:29:24,090 --> 00:29:24,820 對不對? 542 00:29:24,820 --> 00:29:28,990 但盡量會在這裡 說,不,它不是。 543 00:29:28,990 --> 00:29:33,980 它會說,因為我們 沒有指定它作為這裡一個字。 544 00:29:33,980 --> 00:29:40,440 儘管我們可以遍歷 通過對這個陣列中, 545 00:29:40,440 --> 00:29:43,890 這種嘗試會說,不, 動物園是不是在你的字典 546 00:29:43,890 --> 00:29:47,070 因為我們還沒有 指定它是這樣。 547 00:29:47,070 --> 00:29:52,870 >> 因此從另一個角度做that-- 哦,對不起,這一項。 548 00:29:52,870 --> 00:29:59,450 所以在這種情況下,“動物園”是不 一個字,但它是在我們的嘗試。 549 00:29:59,450 --> 00:30:05,690 但在這其中,說我們想讓它 介紹詞“洗澡”,會發生什麼 550 00:30:05,690 --> 00:30:08,260 是我們遵循through-- B,A,T。 551 00:30:08,260 --> 00:30:11,820 我們在這個數組中, 我們去尋找小時。 552 00:30:11,820 --> 00:30:15,220 >> 在這種情況下,當我們 看指針小時, 553 00:30:15,220 --> 00:30:17,890 它指向NULL,好不好? 554 00:30:17,890 --> 00:30:20,780 所以,除非它是明確的 指著另一個數組, 555 00:30:20,780 --> 00:30:25,000 你以為所有的指針 在這個陣列指向空。 556 00:30:25,000 --> 00:30:28,270 所以在這種情況中,h是指向 為null,所以我們不能做任何事情, 557 00:30:28,270 --> 00:30:31,540 因此它也將返回 假的,“洗澡”是不是在這裡。 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 所以,現在我們實際上 要經過 560 00:30:35,810 --> 00:30:39,790 怎麼會,我們實際上說 該“動物園”是我們的嘗試。 561 00:30:39,790 --> 00:30:42,920 我們如何將“動物園”到我們試試? 562 00:30:42,920 --> 00:30:47,810 所以在我們開始以相同的方式 我們的鍊錶,我們從根開始。 563 00:30:47,810 --> 00:30:50,600 如有疑問,開始 這些東西的根源。 564 00:30:50,600 --> 00:30:53,330 >> 我們會說,OK,Z。 565 00:30:53,330 --> 00:30:55,650 ž存在於此,並且它的作用。 566 00:30:55,650 --> 00:30:58,370 所以你移動到 你的下一個陣列,好不好? 567 00:30:58,370 --> 00:31:01,482 然後就下單, 我們說好,不Ø存在嗎? 568 00:31:01,482 --> 00:31:03,000 它的作用。 569 00:31:03,000 --> 00:31:04,330 這再次。 570 00:31:04,330 --> 00:31:08,670 >> 等我們下單,我們已經說過了, OK,“動物園”已經存在這裡。 571 00:31:08,670 --> 00:31:12,440 所有我們需要做的是設置此相等 為true時,有一個詞出現。 572 00:31:12,440 --> 00:31:15,260 如果你遵循了一切 到該點之前, 573 00:31:15,260 --> 00:31:17,030 這是一個字,所以只 設置它等於這樣的。 574 00:31:17,030 --> 00:31:17,530 是嗎? 575 00:31:17,530 --> 00:31:22,550 >> 聽眾:所以後來做了 意思是“巴”是一個字也? 576 00:31:22,550 --> 00:31:24,120 >> 揚聲器1:第 577 00:31:24,120 --> 00:31:28,870 因此,在這種情況下,“巴”,我們會得到 在這裡,我們想說的是一個字, 578 00:31:28,870 --> 00:31:31,590 並且它仍然是否定的。 579 00:31:31,590 --> 00:31:32,822 行? 580 00:31:32,822 --> 00:31:33,740 Mmhmm​​? 581 00:31:33,740 --> 00:31:36,360 >> 聽眾:所以一旦你是一個 一句話,你說是,那麼它 582 00:31:36,360 --> 00:31:38,380 將包含去米? 583 00:31:38,380 --> 00:31:42,260 >> 揚聲器1:所以這個必須做 with--你加載此研究。 584 00:31:42,260 --> 00:31:43,640 你說的“動物園”一詞。 585 00:31:43,640 --> 00:31:47,020 當你去check-- 喜歡,說你想說的話, 586 00:31:47,020 --> 00:31:49,400 在這個字典裡“動物園”的存在? 587 00:31:49,400 --> 00:31:54,200 你只會搜索“動物園” 然後檢查,看它是否是一個字。 588 00:31:54,200 --> 00:31:57,291 你永遠不會動 通過對米,因為這不是 589 00:31:57,291 --> 00:31:58,290 您要查找的內容。 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> 因此,如果我們真的想 添加“洗澡”這個嘗試, 592 00:32:08,070 --> 00:32:11,390 我們會做同樣的事情 當我們用做“動物園” 593 00:32:11,390 --> 00:32:15,380 除了我們看到,當我們 嘗試,並得到為h,它不存在。 594 00:32:15,380 --> 00:32:20,090 所以,你可以認為這是試圖 以添加新節點插入到一個鍊錶, 595 00:32:20,090 --> 00:32:27,210 所以我們需要添加另一個 其中的一個陣列,像這樣。 596 00:32:27,210 --> 00:32:35,670 然後我們要做的是,我們剛剛成立的H 這個數組指向這個元素。 597 00:32:35,670 --> 00:32:39,430 >> 然後什麼我們要在這裡做? 598 00:32:39,430 --> 00:32:43,110 添加它等於true 因為它是一個字。 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 涼爽。 601 00:32:48,150 --> 00:32:48,700 我知道。 602 00:32:48,700 --> 00:32:51,170 嘗試都不是最激動人心的。 603 00:32:51,170 --> 00:32:54,250 相信我,我知道。 604 00:32:54,250 --> 00:32:58,040 >> 這麼一件事與嘗試實現, 我說,他們是非常有效的。 605 00:32:58,040 --> 00:33:00,080 因此,我們已經看到了他們 佔用大量的空間。 606 00:33:00,080 --> 00:33:01,370 種他們混淆。 607 00:33:01,370 --> 00:33:03,367 那麼,為什麼我們曾經使用過這些? 608 00:33:03,367 --> 00:33:05,450 我們使用這些,因為他們是 令人難以置信的高效。 609 00:33:05,450 --> 00:33:08,130 >> 因此,如果你曾經期待 一個字,你是唯一的 610 00:33:08,130 --> 00:33:10,450 由字的長度的限制。 611 00:33:10,450 --> 00:33:15,210 所以,如果你正在尋找一個 字是一個長度為5的, 612 00:33:15,210 --> 00:33:20,940 你永遠只能將不得不 讓最多5攀比,好不好? 613 00:33:20,940 --> 00:33:25,780 所以它使基本上是一個常數。 614 00:33:25,780 --> 00:33:29,150 就像插入和查詢 基本上都是固定的時間。 615 00:33:29,150 --> 00:33:33,750 >> 所以,如果你能永遠得到 東西在一定的時間, 616 00:33:33,750 --> 00:33:35,150 這是因為它得到不錯的。 617 00:33:35,150 --> 00:33:37,990 你不能得到更好的比 固定時間為這些事情。 618 00:33:37,990 --> 00:33:43,150 以便為所述一個 嘗試了巨大的加號。 619 00:33:43,150 --> 00:33:46,780 >> 但它是一個很大的空間。 620 00:33:46,780 --> 00:33:50,380 樣的,所以你必須決定 什麼對你更重要。 621 00:33:50,380 --> 00:33:54,700 而在今天的電腦, 空間的一個嘗試可能最多 622 00:33:54,700 --> 00:33:57,740 也許不影響 你那麼多,但也許 623 00:33:57,740 --> 00:34:01,350 你在處理事情 有遠遠更多的東西, 624 00:34:01,350 --> 00:34:02,810 並嘗試恰恰是不合理的。 625 00:34:02,810 --> 00:34:03,000 是嗎? 626 00:34:03,000 --> 00:34:05,610 >> 聽眾:等等,讓你有26 在每一個人信嗎? 627 00:34:05,610 --> 00:34:07,440 >> 揚聲器1:Mmhmm​​。 628 00:34:07,440 --> 00:34:08,570 是啊,你有26。 629 00:34:08,570 --> 00:34:16,984 你有一些是字標記,然後 你有26球在每個人。 630 00:34:16,984 --> 00:34:17,775 他們正在point-- 631 00:34:17,775 --> 00:34:20,280 >> 聽眾:和每一個26, 難道他們各有26? 632 00:34:20,280 --> 00:34:21,500 >> 揚聲器1:是的。 633 00:34:21,500 --> 00:34:27,460 這就是為什麼,因為你可以 看,它擴展相當迅速。 634 00:34:27,460 --> 00:34:28,130 行。 635 00:34:28,130 --> 00:34:32,524 所以,我們要進入樹, 我覺得喜歡的是更簡單,大概會 636 00:34:32,524 --> 00:34:36,150 是一個可愛的小死緩 從那裡嘗試。 637 00:34:36,150 --> 00:34:39,620 所以希望你們中的大多數 以前看過一棵樹。 638 00:34:39,620 --> 00:34:41,820 不喜歡漂亮 外面的人,這是我 639 00:34:41,820 --> 00:34:44,340 不知道是否有人 去戶外最近。 640 00:34:44,340 --> 00:34:49,230 我去採摘蘋果本週末, 哦,我的天哪,這是美麗的。 641 00:34:49,230 --> 00:34:52,250 我不知道葉子 可以看看那個漂亮。 642 00:34:52,250 --> 00:34:53,610 >> 所以這只是一棵樹,對不對? 643 00:34:53,610 --> 00:34:56,790 這只是一些節點,並且它 指著一堆其他節點。 644 00:34:56,790 --> 00:34:59,570 正如你在這裡看到,這是 樣一個反复出現的主題。 645 00:34:59,570 --> 00:35:03,720 節點指向的節點是怎麼樣的 許多數據結構的本質。 646 00:35:03,720 --> 00:35:06,670 這只是取決於我們如何 讓他們指向對方 647 00:35:06,670 --> 00:35:08,600 以及我們如何遍歷 通過他們,我們如何 648 00:35:08,600 --> 00:35:14,500 插入的東西,它決定 各自不同的特性。 649 00:35:14,500 --> 00:35:17,600 >> 所以只是一些術語, 我以前使用過。 650 00:35:17,600 --> 00:35:20,010 所以,根本是不管是在最高層。 651 00:35:20,010 --> 00:35:21,200 這就是我們總是開始。 652 00:35:21,200 --> 00:35:23,610 你可以把它作為負責人也。 653 00:35:23,610 --> 00:35:28,750 但對於樹木,我們往往 稱其為根部。 654 00:35:28,750 --> 00:35:32,820 >> 凡是在底部這裡 - 在非常,非常bottom-- 655 00:35:32,820 --> 00:35:34,500 都認為葉。 656 00:35:34,500 --> 00:35:37,210 因此,隨之而來的 整棵樹的事,對不對? 657 00:35:37,210 --> 00:35:39,860 葉子是在你的樹的邊緣。 658 00:35:39,860 --> 00:35:45,820 >> 然後我們也有幾個 術語談論有關節點 659 00:35:45,820 --> 00:35:46,680 給對方。 660 00:35:46,680 --> 00:35:49,700 因此,我們有父母, 孩子和兄弟姐妹。 661 00:35:49,700 --> 00:35:56,260 所以在這種情況下,圖3是 父的5,6和7。 662 00:35:56,260 --> 00:36:00,370 因此,家長無論是 一步以上不管你是 663 00:36:00,370 --> 00:36:02,940 參照,所以才 就像一個家庭樹。 664 00:36:02,940 --> 00:36:07,090 但願,這是所有有點 位比嘗試更直觀。 665 00:36:07,090 --> 00:36:10,970 >> 兄弟姐妹是任何有 同樣的父母,對不對? 666 00:36:10,970 --> 00:36:13,470 他們在這裡的同一水平。 667 00:36:13,470 --> 00:36:16,960 然後,因為我是 他說,孩子們剛 668 00:36:16,960 --> 00:36:22,630 無論是低於一步 有問題的節點,好不好? 669 00:36:22,630 --> 00:36:23,470 涼爽。 670 00:36:23,470 --> 00:36:25,610 這樣的二進制樹。 671 00:36:25,610 --> 00:36:31,450 任何人都可以猜測的一 二叉樹的特點是什麼? 672 00:36:31,450 --> 00:36:32,770 >> 聽眾:最多兩片葉子。 673 00:36:32,770 --> 00:36:33,478 >> 揚聲器1:沒錯。 674 00:36:33,478 --> 00:36:34,640 所以,最大的兩片葉子。 675 00:36:34,640 --> 00:36:39,730 因此,在這個人之前,我們有這個 這有三個,但在一個二叉樹, 676 00:36:39,730 --> 00:36:45,000 你有最多兩個 每個父母的孩子,對不對? 677 00:36:45,000 --> 00:36:46,970 還有一個 有趣的特性。 678 00:36:46,970 --> 00:36:51,550 有誰知道? 679 00:36:51,550 --> 00:36:52,620 二叉樹。 680 00:36:52,620 --> 00:37:00,350 >> 所以二叉樹將擁有一切 在the--這個人是不是sorted-- 681 00:37:00,350 --> 00:37:05,320 但在一個排序二叉樹, 一切都在正確的 682 00:37:05,320 --> 00:37:08,530 大於父 一切都在左邊 683 00:37:08,530 --> 00:37:10,035 小於母體。 684 00:37:10,035 --> 00:37:15,690 並且已經交了白卷 問題之前,那麼好就知道了。 685 00:37:15,690 --> 00:37:19,500 因此,我們定義這個方式, 再次,我們有另一個節點。 686 00:37:19,500 --> 00:37:21,880 這看起來非常相似呢? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 雙 689 00:37:28,836 --> 00:37:29,320 >> 聽眾:鍊錶 690 00:37:29,320 --> 00:37:31,100 >> 揚聲器1:雙鍊錶,對不對? 691 00:37:31,100 --> 00:37:33,690 因此,如果我們替換此 有一個和下一個, 692 00:37:33,690 --> 00:37:35,670 這將是一個雙向鍊錶。 693 00:37:35,670 --> 00:37:40,125 但是,在這種情況下,我們實際上 有左,右,僅此而已。 694 00:37:40,125 --> 00:37:41,500 否則,它是完全相同的。 695 00:37:41,500 --> 00:37:43,374 我們還有元素 你要找的, 696 00:37:43,374 --> 00:37:45,988 而你只需要兩個指針 要去什麼是下一個。 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 是啊,所以二叉搜索樹。 699 00:37:51,870 --> 00:37:57,665 如果我們發現,一切都在 這裡是更大than-- 700 00:37:57,665 --> 00:37:59,850 或立即的一切 這裡的權利 701 00:37:59,850 --> 00:38:02,840 是大於一切 這裡是小於。 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> 所以,如果我們通過搜索,它 看起來應該非常接近二分查找 704 00:38:14,000 --> 00:38:14,910 在這裡,對不對? 705 00:38:14,910 --> 00:38:17,640 除外,而不是找 在一半的陣列, 706 00:38:17,640 --> 00:38:21,720 我們只是在尋找在任左 側或右側的樹。 707 00:38:21,720 --> 00:38:24,850 所以就有點簡單,我想。 708 00:38:24,850 --> 00:38:29,300 >> 所以,如果你的根是空的, 顯然這只是假的。 709 00:38:29,300 --> 00:38:33,470 而如果它的存在,很明顯這是真的。 710 00:38:33,470 --> 00:38:35,320 如果是小於,我們尋找的左側。 711 00:38:35,320 --> 00:38:37,070 如果是大於, 我們搜查的權利。 712 00:38:37,070 --> 00:38:39,890 它是完全一樣的二進制搜索, 只是一個不同的數據結構 713 00:38:39,890 --> 00:38:40,600 我們使用。 714 00:38:40,600 --> 00:38:42,790 代替數組, 它只是一個二叉樹。 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK,棧。 717 00:38:48,090 --> 00:38:51,550 而且,看起來我們 可能有一點點時間。 718 00:38:51,550 --> 00:38:54,460 如果我們這樣做,我很高興去 在任何這一次。 719 00:38:54,460 --> 00:38:56,856 OK,所以棧。 720 00:38:56,856 --> 00:39:02,695 有誰還記得stacks-- 一摞任何特點? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> 好了,我們大多數人,我想, 在餐廳吃飯halls-- 723 00:39:10,400 --> 00:39:13,100 就像我們可能不喜歡。 724 00:39:13,100 --> 00:39:16,900 但很明顯,你可以把一疊 從字面上就如同一摞托盤 725 00:39:16,900 --> 00:39:18,460 或堆疊的事情。 726 00:39:18,460 --> 00:39:21,820 和什麼是重要的 要知道的是,它的 727 00:39:21,820 --> 00:39:26,850 something--特徵 我們把它叫做by--是後進先出法。 728 00:39:26,850 --> 00:39:28,450 有誰知道這代表著什麼? 729 00:39:28,450 --> 00:39:29,070 Mmhmm​​? 730 00:39:29,070 --> 00:39:30,650 >> 聽眾:後進先出。 731 00:39:30,650 --> 00:39:32,250 >> 揚聲器1:沒錯,後進先出。 732 00:39:32,250 --> 00:39:36,585 所以,如果我們知道,如果我們的東西堆放 起來,最簡單的事情搶off-- 733 00:39:36,585 --> 00:39:39,570 也許我們唯一可以搶 關閉如果我們的協議棧是大enough-- 734 00:39:39,570 --> 00:39:40,850 是頂級元素。 735 00:39:40,850 --> 00:39:43,460 所以,無論是放在 last--我們在這裡看到, 736 00:39:43,460 --> 00:39:46,370 不管是推 在大多數recently--是 737 00:39:46,370 --> 00:39:51,160 將成為第一 我們流行過,東西好不好? 738 00:39:51,160 --> 00:39:56,324 >> 所以,我們在這裡是 另一個typedef結構。 739 00:39:56,324 --> 00:39:58,740 這真的只是喜歡 在數據結構速成班, 740 00:39:58,740 --> 00:40:01,650 所以有很多扔向你們。 741 00:40:01,650 --> 00:40:02,540 我知道。 742 00:40:02,540 --> 00:40:04,970 因此,另一種結構。 743 00:40:04,970 --> 00:40:06,740 耶的結構。 744 00:40:06,740 --> 00:40:16,660 >> 在這種情況下,它的一些指針 到具有一定容量的陣列。 745 00:40:16,660 --> 00:40:20,830 因此,這代表了我們的協議棧 在這裡,像我們實際的數組 746 00:40:20,830 --> 00:40:22,520 這是我們持有的元素。 747 00:40:22,520 --> 00:40:24,850 然後在這裡我們有一些大小。 748 00:40:24,850 --> 00:40:31,170 >> 而通常情況下,你要保持 曲目有多大的堆棧 749 00:40:31,170 --> 00:40:36,180 因為它是怎麼回事,讓 你要做的就是,如果你知道的大小, 750 00:40:36,180 --> 00:40:39,170 它可以讓你說的, 好吧,我是在能力? 751 00:40:39,170 --> 00:40:40,570 我可以添加些什麼? 752 00:40:40,570 --> 00:40:44,650 它也告訴你 在您的堆棧的頂部 753 00:40:44,650 --> 00:40:48,180 那麼你知道你 其實可以起飛。 754 00:40:48,180 --> 00:40:51,760 而這實際上是要 有一點更清楚這裡。 755 00:40:51,760 --> 00:40:57,350 >> 因此,對於推,一件事,如果你 是有史以來實施推, 756 00:40:57,350 --> 00:41:01,330 我只是說,你的 棧的大小有限,對不對? 757 00:41:01,330 --> 00:41:03,990 我們的陣列有一些能力。 758 00:41:03,990 --> 00:41:04,910 這是一個數組。 759 00:41:04,910 --> 00:41:08,930 這是一個固定大小的,所以我們需要 確保我們不會把更多 760 00:41:08,930 --> 00:41:11,950 到我們的數組要比我們 實際上有空間。 761 00:41:11,950 --> 00:41:16,900 >> 所以,當你創建一個推 功能,你做的是說好第一句話, 762 00:41:16,900 --> 00:41:18,570 做我的空間我的籌碼? 763 00:41:18,570 --> 00:41:23,330 因為如果我不這樣做,對不起, 我不能存儲你的元素。 764 00:41:23,330 --> 00:41:28,980 如果我這樣做,那麼你想存儲 它在堆棧的頂部,對不對? 765 00:41:28,980 --> 00:41:31,325 >> 這就是為什麼我們有 跟踪我們的規模。 766 00:41:31,325 --> 00:41:35,290 如果我們不保持我們這樣規模的軌道, 我們不知道放在哪裡。 767 00:41:35,290 --> 00:41:39,035 我們不知道有多少東西 在我們的數組了。 768 00:41:39,035 --> 00:41:41,410 就像明明有方法 也許你可以做到這一點。 769 00:41:41,410 --> 00:41:44,610 你可以初始化所有設置為NULL 然後檢查最新NULL, 770 00:41:44,610 --> 00:41:47,950 但一個更容易的事情僅僅是 說,OK,跟踪大小。 771 00:41:47,950 --> 00:41:51,840 就像我知道我有四個要素 在我的數組,所以接下來的事情 772 00:41:51,840 --> 00:41:55,930 我們換上,我們 將存儲在索引4。 773 00:41:55,930 --> 00:42:00,940 然後,當然,這意味著 你已經成功地推的東西 774 00:42:00,940 --> 00:42:03,320 到你的籌碼,你 要增加大小 775 00:42:03,320 --> 00:42:08,880 讓你知道你是如此 那你可以把更多的東西。 776 00:42:08,880 --> 00:42:12,730 >> 所以,如果我們試圖彈出 事關棧, 777 00:42:12,730 --> 00:42:16,072 可能是什麼的第一件事 我們要檢查? 778 00:42:16,072 --> 00:42:18,030 你想採取 事關你的籌碼。 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 你肯定有 在堆棧中的東西嗎? 781 00:42:24,781 --> 00:42:25,280 號 782 00:42:25,280 --> 00:42:26,894 所以,什麼才是我們要檢查? 783 00:42:26,894 --> 00:42:27,810 >> 聽眾:[聽不清]。 784 00:42:27,810 --> 00:42:29,880 揚聲器1:檢查的大小? 785 00:42:29,880 --> 00:42:31,840 尺寸。 786 00:42:31,840 --> 00:42:38,520 因此,我們要檢查,如果看 我們的規模是大於0,OK? 787 00:42:38,520 --> 00:42:44,970 如果是,那麼我們需要減小 我們的規模由0和返回。 788 00:42:44,970 --> 00:42:45,840 為什麼呢? 789 00:42:45,840 --> 00:42:49,950 >> 在第一個我們 推,我們推 790 00:42:49,950 --> 00:42:52,460 上的尺寸,然後更新的大小。 791 00:42:52,460 --> 00:42:57,850 在這種情況下,我們正在遞減大小 然後把它關閉,它拔毛 792 00:42:57,850 --> 00:42:58,952 從我們的數組。 793 00:42:58,952 --> 00:42:59,826 為什麼會那樣做? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 所以,如果我有一件事對我的籌碼, 這將是我的尺寸在這一點? 796 00:43:11,811 --> 00:43:13,140 1。 797 00:43:13,140 --> 00:43:15,180 >> 何為元素1儲存在哪裡? 798 00:43:15,180 --> 00:43:17,621 什麼指標? 799 00:43:17,621 --> 00:43:18,120 聽眾:0。 800 00:43:18,120 --> 00:43:19,060 揚聲器1:0。 801 00:43:19,060 --> 00:43:22,800 所以在這種情況下,我們 總是需要使sure-- 802 00:43:22,800 --> 00:43:27,630 而不是返回 大小減去1,因為我們 803 00:43:27,630 --> 00:43:31,730 知道我們的元素是 將要被存儲在1以下 804 00:43:31,730 --> 00:43:34,705 無論我們的規模是,這 只需要照顧它。 805 00:43:34,705 --> 00:43:36,080 這是一個稍微更優雅的方式。 806 00:43:36,080 --> 00:43:41,220 我們只是減小了 大小,然後返回大小。 807 00:43:41,220 --> 00:43:42,330 Mmhmm​​? 808 00:43:42,330 --> 00:43:45,300 >> 觀眾:我想剛才在一般情況下, 為什麼會這個數據結構 809 00:43:45,300 --> 00:43:47,800 是有益的? 810 00:43:47,800 --> 00:43:50,660 >> 揚聲器1:這取決於你的環境。 811 00:43:50,660 --> 00:43:57,420 因此對於一些理論, 如果你的工作with-- OK, 812 00:43:57,420 --> 00:44:02,750 讓我看看,如果有一個有利的1 那就是超過外面有利 813 00:44:02,750 --> 00:44:05,420 的CS。 814 00:44:05,420 --> 00:44:15,780 隨著棧,任何時候你需要 跟踪事 815 00:44:15,780 --> 00:44:20,456 是最近添加的是當 你將要使用的堆棧。 816 00:44:20,456 --> 00:44:24,770 >> 我想不出一個好 舉例說,現在。 817 00:44:24,770 --> 00:44:29,955 但每當最近 事情是對你最重要, 818 00:44:29,955 --> 00:44:31,705 這是一個堆棧時, 將是有用的。 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 我試圖想,如果 有一個很好的這一點。 821 00:44:39,330 --> 00:44:43,720 如果我覺得一個很好的例子,在未來 20分鐘後,我一定會告訴你的。 822 00:44:43,720 --> 00:44:49,455 >> 但總體而言,如果有什麼事, 就像我說的最多的,其中,最近 823 00:44:49,455 --> 00:44:52,470 最重要的是,這是 其中,一摞用武之地。 824 00:44:52,470 --> 00:44:58,860 而隊列是一種相反的。 825 00:44:58,860 --> 00:44:59,870 和所有的小狗狗。 826 00:44:59,870 --> 00:45:00,890 這不是很大的,對不對? 827 00:45:00,890 --> 00:45:03,299 我覺得我應該 只是有一個小兔子的視頻 828 00:45:03,299 --> 00:45:05,090 右中的中間 節為你們 829 00:45:05,090 --> 00:45:08,870 因為這是一個強烈的部分。 830 00:45:08,870 --> 00:45:10,480 >> 這樣一個隊列。 831 00:45:10,480 --> 00:45:12,710 基本上一個隊列是像一條線。 832 00:45:12,710 --> 00:45:15,780 你們我敢肯定,使用這種日常生活, 就像在我們的食堂。 833 00:45:15,780 --> 00:45:18,160 因此,我們必須去 並得到我們的托盤,我 834 00:45:18,160 --> 00:45:21,260 確保你有排隊等候 刷卡或讓你的食物。 835 00:45:21,260 --> 00:45:24,650 >> 因此,區別就在這裡 是,這是FIFO中。 836 00:45:24,650 --> 00:45:30,090 所以,如果是後進先出後進,先 出,先進先出是先入先出。 837 00:45:30,090 --> 00:45:33,400 因此,這是不管你把 第一次是你最重要的。 838 00:45:33,400 --> 00:45:35,540 所以,如果你在等待 在line--可以嗎 839 00:45:35,540 --> 00:45:39,130 想像一下,如果你去了 去獲得新的iPhone 840 00:45:39,130 --> 00:45:42,800 並且它是一個堆棧,其中 最後一個人符合了它​​的第一, 841 00:45:42,800 --> 00:45:44,160 人們會互相殘殺。 842 00:45:44,160 --> 00:45:49,800 >> 所以FIFO,我們都很熟悉 在這裡,在現實世界中, 843 00:45:49,800 --> 00:45:54,930 而這一切,是因為有實際 種重現這一整條生產線 844 00:45:54,930 --> 00:45:56,900 和排隊結構。 845 00:45:56,900 --> 00:46:02,390 如此而用棧, 我們有push和pop。 846 00:46:02,390 --> 00:46:06,440 同一個隊列,我們有 入隊和出隊。 847 00:46:06,440 --> 00:46:10,910 所以排隊的基本含義 把它放到後面, 848 00:46:10,910 --> 00:46:13,680 和出隊採取的手段 斷從前面。 849 00:46:13,680 --> 00:46:18,680 因此,我們的數據結構是一 稍微有點複雜。 850 00:46:18,680 --> 00:46:21,060 我們有第二個事情防不勝防。 851 00:46:21,060 --> 00:46:25,950 >> 因此,沒有了頭,這 正是堆棧,對不對? 852 00:46:25,950 --> 00:46:27,900 這是相同的結構的堆疊。 853 00:46:27,900 --> 00:46:32,480 唯一不同的是,現在我們 有這個頭,這你怎麼看 854 00:46:32,480 --> 00:46:34,272 是要跟踪的? 855 00:46:34,272 --> 00:46:35,510 >> 聽眾:第一個。 856 00:46:35,510 --> 00:46:38,685 >> 揚聲器1:對, 我們把第一件事。 857 00:46:38,685 --> 00:46:41,130 我們的隊列的頭。 858 00:46:41,130 --> 00:46:42,240 誰是排在第一位。 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 好吧,如果我們做排隊。 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 再次,與任何 這些數據結構 863 00:46:55,920 --> 00:46:59,760 因為我們處理的是一個數組, 我們需要檢查一下,如果我們有空間。 864 00:46:59,760 --> 00:47:03,290 >> 這有點像我說 你們這些傢伙,如果你打開一個文件, 865 00:47:03,290 --> 00:47:04,760 你需要檢查空。 866 00:47:04,760 --> 00:47:08,330 與任何這些堆棧 和隊列,你需要 867 00:47:08,330 --> 00:47:13,420 看看是否有空間,因為我們 處理一個固定尺寸數組, 868 00:47:13,420 --> 00:47:16,030 我們看到這裡 - 0,1都達5。 869 00:47:16,030 --> 00:47:20,690 那麼,我們在這種情況下是檢查 看看我們仍然有空間。 870 00:47:20,690 --> 00:47:23,110 是我們的規模小於容量是多少? 871 00:47:23,110 --> 00:47:28,480 >> 如果是這樣,我們需要將其存儲在 尾部,我們更新我們的規模。 872 00:47:28,480 --> 00:47:30,250 那麼,什麼可能的尾巴在這種情況下? 873 00:47:30,250 --> 00:47:32,360 它沒有明確地寫出來。 874 00:47:32,360 --> 00:47:33,380 我們將如何保存呢? 875 00:47:33,380 --> 00:47:34,928 什麼尾巴呢? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> 因此,讓我們步行穿過這個例子。 878 00:47:40,190 --> 00:47:44,590 因此,這是一個大小為6的數組,對不對? 879 00:47:44,590 --> 00:47:49,220 而我們現在所擁有的,我們的規模是5。 880 00:47:49,220 --> 00:47:55,240 而當我們把它放在,這是怎麼回事 進入第五個指標,對不對? 881 00:47:55,240 --> 00:47:57,030 因此,存儲在尾部。 882 00:47:57,030 --> 00:48:05,600 >> 另一種方式來寫尾部也只是 是我們的數組大小​​的指標,對不對? 883 00:48:05,600 --> 00:48:07,560 這是5號。 884 00:48:07,560 --> 00:48:11,490 接下來的事情將要進入5。 885 00:48:11,490 --> 00:48:12,296 很酷吧? 886 00:48:12,296 --> 00:48:13,290 行。 887 00:48:13,290 --> 00:48:16,350 它變得稍微複雜 當我們開始用頭搞亂。 888 00:48:16,350 --> 00:48:17,060 是嗎? 889 00:48:17,060 --> 00:48:20,090 >> 聽眾:這是否意味著我們 會宣布一個數組, 890 00:48:20,090 --> 00:48:23,880 是五行長 那麼,我們要添加到它? 891 00:48:23,880 --> 00:48:24,730 >> 揚聲器1:第 892 00:48:24,730 --> 00:48:27,560 所以在這種情況下,這是一個堆棧。 893 00:48:27,560 --> 00:48:31,760 這將宣布 作為規模6的數組。 894 00:48:31,760 --> 00:48:37,120 在這種情況下,我們 只有一個剩餘空間。 895 00:48:37,120 --> 00:48:42,720 >> 好了,有一件事是在這 情況下,如果我們的頭是0, 896 00:48:42,720 --> 00:48:45,270 那麼我們就可以在大小添加。 897 00:48:45,270 --> 00:48:51,020 但它變得有點棘手 因為實際上,他們 898 00:48:51,020 --> 00:48:52,840 不具備滑動 對於這一點,所以我要去 899 00:48:52,840 --> 00:48:56,670 畫之一,因為它不是 曾經想像中的那麼簡單,你 900 00:48:56,670 --> 00:48:59,230 開始擺脫的東西。 901 00:48:59,230 --> 00:49:03,920 因此,而用棧 你永遠只能有 902 00:49:03,920 --> 00:49:08,920 擔心大小是什麼 當你添加的東西上, 903 00:49:08,920 --> 00:49:15,710 一個隊列,你還需要 確保你的頭被佔, 904 00:49:15,710 --> 00:49:20,760 由於對隊列一件很酷的事情 是,如果你沒有能力, 905 00:49:20,760 --> 00:49:23,040 你其實可以把它環繞。 906 00:49:23,040 --> 00:49:28,810 >> OK,所以一件事 - 哦, 這是可怕的粉筆。 907 00:49:28,810 --> 00:49:31,815 有一點要考慮的是這種情況。 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 我們就做五。 910 00:49:37,140 --> 00:49:41,810 好了,我們要 說的頭就在這裡。 911 00:49:41,810 --> 00:49:46,140 這是0,1,2,3,4。 912 00:49:46,140 --> 00:49:54,210 >> 頭的存在,並 請有東西在其中。 913 00:49:54,210 --> 00:49:58,340 我們要添加的東西,對吧? 914 00:49:58,340 --> 00:50:01,170 於是事情,我們需要 知道的是,頭總是 915 00:50:01,170 --> 00:50:05,620 要移動這樣的, 然後循環回到我的身邊,好不好? 916 00:50:05,620 --> 00:50:10,190 >> 所以這個隊列有空間的,對不對? 917 00:50:10,190 --> 00:50:13,950 它有空間,在一開始, 那種此相反的。 918 00:50:13,950 --> 00:50:17,920 因此,我們需要做的是我們 需要計算的尾巴。 919 00:50:17,920 --> 00:50:20,530 如果你知道你的 頭沒有移動,尾巴 920 00:50:20,530 --> 00:50:24,630 只是你的數組 大小的指標。 921 00:50:24,630 --> 00:50:30,000 >> 但在現實中,如果你使用一個隊列, 你的腦袋可能是被更新。 922 00:50:30,000 --> 00:50:33,890 所以,你需要做的是 實際計算的尾巴。 923 00:50:33,890 --> 00:50:39,990 所以,我們做的是這個公式 在這裡,我打算讓你 924 00:50:39,990 --> 00:50:42,680 你們想想,和 然後我們會談論它。 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 因此,這是能力。 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> 所以這實際上 給你一個辦法做到這一點。 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 因為在這種情況下,是什麼? 931 00:51:04,330 --> 00:51:09,205 我們的頭是1,我們的規模是4。 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 如果我們這國防部5,我們得到0, 這是我們應該輸入它。 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> 如此則在下一情況下, 如果要做到這一點, 936 00:51:26,080 --> 00:51:33,390 我們說,好吧,讓我們出列的東西。 937 00:51:33,390 --> 00:51:34,390 我們出列了。 938 00:51:34,390 --> 00:51:37,740 我們拿出這個元素,對不對? 939 00:51:37,740 --> 00:51:47,930 >> 現在我們的頭指指點點, 我們要在另一件事情補充。 940 00:51:47,930 --> 00:51:52,470 這基本上是 回到我們這行的,對不對? 941 00:51:52,470 --> 00:51:55,450 隊列可以在陣列周圍包裹。 942 00:51:55,450 --> 00:51:57,310 這是主要區別之一。 943 00:51:57,310 --> 00:51:58,780 堆棧,你不能做到這一點。 944 00:51:58,780 --> 00:52:01,140 >> 隨著隊列,您可以 因為所有的事項 945 00:52:01,140 --> 00:52:03,940 是,你知道什麼 最近被添加。 946 00:52:03,940 --> 00:52:10,650 因為一切都在以复加 此向左方向,在這種情況下, 947 00:52:10,650 --> 00:52:16,480 然後環繞,你可以 繼續投入新元素 948 00:52:16,480 --> 00:52:18,830 在陣列的前 因為它不是真的 949 00:52:18,830 --> 00:52:20,640 陣列的前面了。 950 00:52:20,640 --> 00:52:26,320 你能想到的初 數組的地方你的頭居然是。 951 00:52:26,320 --> 00:52:29,710 >> 所以這個公式是怎麼 你計算你的尾巴。 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 這是否有道理? 954 00:52:35,610 --> 00:52:36,110 行。 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK,出列,然後 你們有10分鐘 957 00:52:44,040 --> 00:52:48,840 要問我任何澄清的問題 你想要的,因為我知道這很瘋狂。 958 00:52:48,840 --> 00:52:51,980 >> 好吧,所以在相同的方式 - 我不知道你們注意到了, 959 00:52:51,980 --> 00:52:53,450 但CS是所有關於模式。 960 00:52:53,450 --> 00:52:57,370 東西是相當多的 同樣的,只需用很小的調整。 961 00:52:57,370 --> 00:52:58,950 這裡這麼一回事。 962 00:52:58,950 --> 00:53:04,040 我們需要檢查一下,看看我們是否真正 有東西在我們的隊列,對不對? 963 00:53:04,040 --> 00:53:05,960 說好,是我們的規模大於0? 964 00:53:05,960 --> 00:53:06,730 涼爽。 965 00:53:06,730 --> 00:53:10,690 >> 如果我們這樣做,那麼我們把我們的頭,這 就是我剛才在這裡展示。 966 00:53:10,690 --> 00:53:13,870 我們更新我們的頭要多一個。 967 00:53:13,870 --> 00:53:18,390 然後我們減了 尺寸,並返回該元素。 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> 有更具體 在study.cs50.net代碼, 970 00:53:26,250 --> 00:53:29,440 我強烈建議你 通過它,如果你有時間, 971 00:53:29,440 --> 00:53:30,980 即使它只是一個偽代碼。 972 00:53:30,980 --> 00:53:35,980 如果你們想通過談話 與我一對一,請讓我 973 00:53:35,980 --> 00:53:37,500 知道了。 974 00:53:37,500 --> 00:53:38,770 我很樂意。 975 00:53:38,770 --> 00:53:42,720 數據結構中,如果 你把CS 124,你會 976 00:53:42,720 --> 00:53:47,830 知道數據結構變得非常 樂趣,這是剛剛開始。 977 00:53:47,830 --> 00:53:50,350 >> 所以,我知道這很難。 978 00:53:50,350 --> 00:53:51,300 沒關係。 979 00:53:51,300 --> 00:53:52,410 我們奮鬥。 980 00:53:52,410 --> 00:53:53,630 我還是做了。 981 00:53:53,630 --> 00:53:56,660 所以不要太擔心了。 982 00:53:56,660 --> 00:54:02,390 >> 但是,這基本上是你 在數據結構速成班。 983 00:54:02,390 --> 00:54:03,400 我知道這是一個很大。 984 00:54:03,400 --> 00:54:06,860 還有什麼是我們 想去一遍? 985 00:54:06,860 --> 00:54:09,400 任何我們想通過談話? 986 00:54:09,400 --> 00:54:10,060 是嗎? 987 00:54:10,060 --> 00:54:16,525 >> 顧客:這個例子,所以 新尾為0了嗎? 988 00:54:16,525 --> 00:54:17,150 揚聲器1:是的。 989 00:54:17,150 --> 00:54:18,230 聽眾:OK。 990 00:54:18,230 --> 00:54:24,220 所以後來經歷, 你有1加4 or-- 991 00:54:24,220 --> 00:54:27,671 >> 揚聲器1:所以你是說, 當我們想要去做到這一點了嗎? 992 00:54:27,671 --> 00:54:28,296 聽眾:是的。 993 00:54:28,296 --> 00:54:38,290 所以,如果你搞清楚out--在哪裡 你計算從該尾? 994 00:54:38,290 --> 00:54:44,260 >> 揚聲器1:所以尾巴 是in--我改變了這一點。 995 00:54:44,260 --> 00:54:52,010 所以在這裡本實施例中,這是 我們正在尋找,確定的數組? 996 00:54:52,010 --> 00:54:54,670 因此,我們必須在1,2,3和4的東西。 997 00:54:54,670 --> 00:55:05,850 因此,我們有我們的頭是等於1 這一點,我們的大小等於4 998 00:55:05,850 --> 00:55:07,050 在這一點上,對不對? 999 00:55:07,050 --> 00:55:08,960 >> 大家都同意的話? 1000 00:55:08,960 --> 00:55:14,620 所以我們做頭部加上大小,這 給我們5,然後我們用5國防部。 1001 00:55:14,620 --> 00:55:20,690 我們得到0,這告訴我們,0 哪裡是我們的尾巴,在那裡我們有空間。 1002 00:55:20,690 --> 00:55:22,010 >> 聽眾:什麼是上限? 1003 00:55:22,010 --> 00:55:23,520 >> 揚聲器1:容量。 1004 00:55:23,520 --> 00:55:24,020 抱歉。 1005 00:55:24,020 --> 00:55:29,640 所以這是你的數組的大小。 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 是嗎? 1008 00:55:36,047 --> 00:55:39,210 >> 聽眾:[聽不清]前 我們返回的元素? 1009 00:55:39,210 --> 00:55:46,270 >> 揚聲器1:因此,我們將 前往或返回的那一刻? 1010 00:55:46,270 --> 00:55:52,680 因此,如果我們移動一個,減小尺寸是多少? 1011 00:55:52,680 --> 00:55:54,150 堅持,稍等。 1012 00:55:54,150 --> 00:55:55,770 我肯定忘了另外一個。 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 沒關係。 1015 00:56:01,990 --> 00:56:04,980 沒有另一個公式。 1016 00:56:04,980 --> 00:56:09,980 是的,你會想返回 頭,然後將其移回。 1017 00:56:09,980 --> 00:56:13,270 >> 聽眾:OK,因為在這 點,頭是0, 1018 00:56:13,270 --> 00:56:18,452 然後,你要回 指數0,然後使頭1? 1019 00:56:18,452 --> 00:56:19,870 >> 揚聲器1:沒錯。 1020 00:56:19,870 --> 00:56:22,820 我認為還有另一種 公式有點像這樣。 1021 00:56:22,820 --> 00:56:26,970 我沒有在這上面我的​​頭 我不想給你錯了。 1022 00:56:26,970 --> 00:56:35,470 但我認為這是完全有效的 比方說,OK,保存該element--什麼 1023 00:56:35,470 --> 00:56:40,759 頭部的元素is--遞減的 大小,移動你的頭了,而歸 1024 00:56:40,759 --> 00:56:41,800 無論這個元素。 1025 00:56:41,800 --> 00:56:44,760 這是完全有效的。 1026 00:56:44,760 --> 00:56:45,260 行。 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 我覺得這不是 像most--你不 1029 00:56:53,560 --> 00:56:55,740 要走出這裡 喜歡,是的,我知道嘗試。 1030 00:56:55,740 --> 00:56:56,880 我得到了這一切。 1031 00:56:56,880 --> 00:56:57,670 沒關係。 1032 00:56:57,670 --> 00:57:00,200 我保證。 1033 00:57:00,200 --> 00:57:05,240 但是數據結構的東西, 它需要大量的時間來用於獲得。 1034 00:57:05,240 --> 00:57:10,010 最難的可能是1 的東西,我認為,在使用過程中。 1035 00:57:10,010 --> 00:57:15,330 >> 因此,它肯定需要 重複和期待at--我 1036 00:57:15,330 --> 00:57:20,050 真的不知道鍊錶 直到我做了太多與他們, 1037 00:57:20,050 --> 00:57:22,550 在同樣的方式,我沒有 真正了解指針 1038 00:57:22,550 --> 00:57:27,040 直到我已經教了兩個 多年來,做自己的pset它。 1039 00:57:27,040 --> 00:57:28,990 這需要大量的重申和時間。 1040 00:57:28,990 --> 00:57:32,600 最終,它會有種點擊。 1041 00:57:32,600 --> 00:57:36,320 >> 但在此期間,如果你有實物 的高水平的理解什麼 1042 00:57:36,320 --> 00:57:39,321 這些幹什麼,他們的優點 和cons--這就是 1043 00:57:39,321 --> 00:57:41,820 我們真的傾向於強調, 特別是在介紹過程。 1044 00:57:41,820 --> 00:57:45,511 喜歡,為什麼我們使用 試試在一個數組? 1045 00:57:45,511 --> 00:57:48,010 喜歡,什麼是陽性 並且其中的每個的底片? 1046 00:57:48,010 --> 00:57:51,610 >> 和理解的取捨 每個這些結構之間 1047 00:57:51,610 --> 00:57:54,910 是什麼是更重要的現在。 1048 00:57:54,910 --> 00:57:58,140 可以有一個瘋 兩個問題那 1049 00:57:58,140 --> 00:58:03,710 要問你實現或推 實施POP或入隊和出隊。 1050 00:58:03,710 --> 00:58:07,340 但在大多數情況下,具有 更高層次的認識和更 1051 00:58:07,340 --> 00:58:09,710 一個直觀的把握是 比實際更重要 1052 00:58:09,710 --> 00:58:11,250 能夠實現它。 1053 00:58:11,250 --> 00:58:14,880 >> 這會是真的真棒,如果在座的各位 能夠走出去,去實現一個嘗試, 1054 00:58:14,880 --> 00:58:19,720 但我們知道它並不一定 最合理的事情,現在。 1055 00:58:19,720 --> 00:58:23,370 但是你可以在你的pset,如果你想 到,然後你會得到實踐, 1056 00:58:23,370 --> 00:58:27,200 然後也許你會 真正了解它。 1057 00:58:27,200 --> 00:58:27,940 是嗎? 1058 00:58:27,940 --> 00:58:30,440 >> 聽眾:好,那麼哪些是 我們的意思,在pset中使用? 1059 00:58:30,440 --> 00:58:31,916 我是否需要使用其中的一個? 1060 00:58:31,916 --> 00:58:32,540 揚聲器1:是的。 1061 00:58:32,540 --> 00:58:34,199 所以,你有你的選擇。 1062 00:58:34,199 --> 00:58:36,740 我在這種情況下猜測,我們可以 說說PSET一點點 1063 00:58:36,740 --> 00:58:40,480 因為我跑過這些。 1064 00:58:40,480 --> 00:58:47,779 因此,在你的pset,你有你的 選擇嘗試或哈希表。 1065 00:58:47,779 --> 00:58:49,570 有些人會嘗試 並使用布隆過濾器, 1066 00:58:49,570 --> 00:58:51,840 但這些在技術上是不正確的。 1067 00:58:51,840 --> 00:58:55,804 因為他們的概率性質, 他們給假陽性的時候。 1068 00:58:55,804 --> 00:58:57,095 他們冷靜地審視之中,雖然。 1069 00:58:57,095 --> 00:58:59,030 強烈推薦看 在他們最少。 1070 00:58:59,030 --> 00:59:03,260 但是,你有你的選擇 一個哈希表,並一試的。 1071 00:59:03,260 --> 00:59:06,660 而這將是哪裡 你在你的字典中加載。 1072 00:59:06,660 --> 00:59:09,230 >> 你需要選擇 您的散列函數 1073 00:59:09,230 --> 00:59:13,420 你需要選擇多少 鏟斗有,它會有所不同。 1074 00:59:13,420 --> 00:59:17,440 就像如果你有更多的桶, 也許它會跑得更快。 1075 00:59:17,440 --> 00:59:22,790 但是,也許你就是在浪費一個 很多空間的方式,雖然。 1076 00:59:22,790 --> 00:59:26,320 你必須弄明白。 1077 00:59:26,320 --> 00:59:27,140 Mmhmm​​? 1078 00:59:27,140 --> 00:59:29,875 >> 聽眾:你之前說 我們可以用其它散列函數 1079 00:59:29,875 --> 00:59:31,750 我們不必 創建一個哈希函數? 1080 00:59:31,750 --> 00:59:32,666 >> 揚聲器1:是的,沒錯。 1081 00:59:32,666 --> 00:59:38,150 因此,從字面上你的哈希函數, 像谷歌“散列函數” 1082 00:59:38,150 --> 00:59:40,770 並尋找一些很酷的人。 1083 00:59:40,770 --> 00:59:43,250 你是不是有望建成 你自己的哈希函數。 1084 00:59:43,250 --> 00:59:46,100 人一生 論文對這些東西。 1085 00:59:46,100 --> 00:59:50,250 >> 所以不用擔心構建自己的。 1086 00:59:50,250 --> 00:59:53,350 找到一個網上開始。 1087 00:59:53,350 --> 00:59:56,120 他們中的一些,你必須 操縱一點點 1088 00:59:56,120 --> 00:59:59,430 以確保返回類型匹配 及諸如此類的東西,所以在開始時, 1089 00:59:59,430 --> 01:00:02,420 我會建議使用一些 真的很簡單,也許只是 1090 01:00:02,420 --> 01:00:04,680 哈希的第一個字母。 1091 01:00:04,680 --> 01:00:08,760 然後,一旦你有工作, 結合有冷卻器的散列函數。 1092 01:00:08,760 --> 01:00:09,260 Mmhmm​​? 1093 01:00:09,260 --> 01:00:13,020 >> 聽眾:請問一個嘗試是或 高效而只是更難,like-- 1094 01:00:13,020 --> 01:00:15,880 >> 揚聲器1:那麼一試,我想, 直覺是難以實現 1095 01:00:15,880 --> 01:00:18,310 但是非常快的。 1096 01:00:18,310 --> 01:00:20,620 但是,佔用了更多的空間。 1097 01:00:20,620 --> 01:00:25,270 同樣,你可以在優化這兩個的 不同的方式和有辦法to-- 1098 01:00:25,270 --> 01:00:26,770 聽眾:我們怎樣分級的呢? 1099 01:00:26,770 --> 01:00:27,540 它matter-- 1100 01:00:27,540 --> 01:00:29,164 >> 揚聲器1:所以你正常的分級方式。 1101 01:00:29,164 --> 01:00:31,330 你要對設計進行分級。 1102 01:00:31,330 --> 01:00:36,020 無論你的方式,你要 確保它的優雅,因為它可以 1103 01:00:36,020 --> 01:00:38,610 並作為有效的,因為它可以。 1104 01:00:38,610 --> 01:00:41,950 但是,如果你選擇一個試或哈希 表的,只要它工作, 1105 01:00:41,950 --> 01:00:45,350 我們很高興。 1106 01:00:45,350 --> 01:00:48,370 如果你使用的東西,哈希 第一個字母,這很好, 1107 01:00:48,370 --> 01:00:51,410 如可能喜歡的設計,明智的。 1108 01:00:51,410 --> 01:00:53,410 我們也到達 點這semester-- 1109 01:00:53,410 --> 01:00:55,340 我不知道,如果你 球員noticed--如果你 1110 01:00:55,340 --> 01:00:58,780 PSET等級下降一點點 因為設計和諸如此類的東西的, 1111 01:00:58,780 --> 01:00:59,900 這是完全正常的。 1112 01:00:59,900 --> 01:01:02,960 它讓到一個地步,你 程序正變得越來越複雜。 1113 01:01:02,960 --> 01:01:04,830 還有更多的地方 你可以改善。 1114 01:01:04,830 --> 01:01:06,370 >> 所以這是完全正常的。 1115 01:01:06,370 --> 01:01:08,810 這並不是說你 您PSET做差。 1116 01:01:08,810 --> 01:01:11,885 這只是我們是很難對你現在。 1117 01:01:11,885 --> 01:01:13,732 所以每個人的感覺吧。 1118 01:01:13,732 --> 01:01:14,940 我只是分級所有pset中。 1119 01:01:14,940 --> 01:01:16,490 我知道每個人都感覺到了。 1120 01:01:16,490 --> 01:01:19,600 >> 所以不用擔心。 1121 01:01:19,600 --> 01:01:23,580 如果您有任何問題, 之前的pset或方法可以改善, 1122 01:01:23,580 --> 01:01:27,760 我嘗試了具體的意見 的地方,但有時它的後期 1123 01:01:27,760 --> 01:01:30,840 我累了。 1124 01:01:30,840 --> 01:01:34,885 是否有任何其他的東西 關於數據結構? 1125 01:01:34,885 --> 01:01:37,510 我敢肯定,你們真的不 要談他們了, 1126 01:01:37,510 --> 01:01:42,650 但如果有,我很高興 走過去了,還有什麼 1127 01:01:42,650 --> 01:01:45,580 講座從過去 上週,上一周。 1128 01:01:45,580 --> 01:01:51,580 >> 我知道,上週所有檢討, 我們可能已經跳過了一些檢討 1129 01:01:51,580 --> 01:01:54,190 從講座。 1130 01:01:54,190 --> 01:01:58,230 還有沒有其他問題我可以回答? 1131 01:01:58,230 --> 01:01:59,350 好了,沒事了。 1132 01:01:59,350 --> 01:02:02,400 好了,你們早出去15分鐘。 1133 01:02:02,400 --> 01:02:08,370 >> 我希望這至少是半很有幫助, 我會看到你下週的傢伙, 1134 01:02:08,370 --> 01:02:12,150 或週四的辦公時間。 1135 01:02:12,150 --> 01:02:15,285 是否有小吃請求 下週,它的東西嗎? 1136 01:02:15,285 --> 01:02:17,459 因為我忘了今天的糖果。 1137 01:02:17,459 --> 01:02:19,750 我帶過去的糖果 上週,但它是哥倫布日, 1138 01:02:19,750 --> 01:02:25,400 所以就像六個人誰 有四袋糖果的自己。 1139 01:02:25,400 --> 01:02:28,820 我可以帶星形圖案 再次,如果你喜歡。 1140 01:02:28,820 --> 01:02:29,580 星形圖案? 1141 01:02:29,580 --> 01:02:32,250 OK,聽起來不錯。 1142 01:02:32,250 --> 01:02:35,050 有一個偉大的日子,伙計們。 1143 01:02:35,050 --> 01:02:39,510