1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[音樂播放]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID馬蘭：這是CS50。

5
00:00:14,010 --> 00:00:18,090
這是二者的開始和
end--像literally--差不多結束

6
00:00:18,090 --> 00:00:18,825
六個星期。

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> 我想我會分享
一個有趣的事實點點。

9
00:00:22,640 --> 00:00:25,370
我從一本拉到了
過去學期的數據集。

10
00:00:25,370 --> 00:00:29,710
你可能還記得，我們​​要求你在每個
P組的形式，如果你已經在網上看過

11
00:00:29,710 --> 00:00:31,580
或者，如果你已經親自出席。

12
00:00:31,580 --> 00:00:33,020
這裡是數據。

13
00:00:33,020 --> 00:00:34,710
所以今天是非常可預測性。

14
00:00:34,710 --> 00:00:37,126
但是，我們想花一點
然而時間與您聯繫。

15
00:00:37,126 --> 00:00:40,599
有人想猜測為什麼這個
圖中是那麼的鋸齒，上下，上下，

16
00:00:40,599 --> 00:00:41,265
所以一貫？

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
做什麼每個峰
和波谷代表什麼？

19
00:00:45,130 --> 00:00:46,005
>> 聽眾：[聽不清]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID馬蘭：確實是這樣。

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
而更有趣的是，上帝保佑，
我們舉行一次講座上週五

24
00:00:55,480 --> 00:00:58,960
在學期的開始，
這就是我們看到發生了什麼。

25
00:00:58,960 --> 00:01:03,430
所以今天，我們參加了位
更多關於數據結構。

26
00:01:03,430 --> 00:01:06,660
並給你更多的是固體
對問題的思維模式五，

27
00:01:06,660 --> 00:01:07,450
這就是現在了。

28
00:01:07,450 --> 00:01:10,817
拼寫錯誤，其中，我們將
交給你一個文本文件，大約10萬

29
00:01:10,817 --> 00:01:12,650
再加上英語單詞，
你將有

30
00:01:12,650 --> 00:01:17,770
弄清楚如何巧妙地加載它們
入存儲器，到RAM中，使用一些數據

31
00:01:17,770 --> 00:01:19,330
您所選擇的結構。

32
00:01:19,330 --> 00:01:22,470
>> 現在，這樣的一個數據結構可以
是，但可能不應該，

33
00:01:22,470 --> 00:01:25,630
在相當簡單的鍊錶，
這是我們去年推出的時間。

34
00:01:25,630 --> 00:01:29,220
和一個鍊錶至少有
1優勢的陣列。

35
00:01:29,220 --> 00:01:32,096
什麼是一個優點
鍊錶可以說是？

36
00:01:32,096 --> 00:01:32,950
>> 聽眾：插入。

37
00:01:32,950 --> 00:01:33,908
>> DAVID馬蘭：插入。

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
你是什​​麼意思？

40
00:01:35,196 --> 00:01:37,872
>> 聽眾：任何位置
名單[聽不清]。

41
00:01:37,872 --> 00:01:38,770
>> DAVID馬蘭：好。

42
00:01:38,770 --> 00:01:42,090
所以，你可以插入一個元素的地方
要在列表的中間

43
00:01:42,090 --> 00:01:45,490
無需洗牌什麼，
我們得出的結論，在我們的分類

44
00:01:45,490 --> 00:01:47,630
討論，是不是
一定是好事，

45
00:01:47,630 --> 00:01:51,200
因為它需要時間來實際移動
所有這些人的左邊或右邊。

46
00:01:51,200 --> 00:01:55,540
所以用一個鍊錶，你可以
剛分配使用malloc，一個新的節點，

47
00:01:55,540 --> 00:01:58,385
然後更新了幾個
pointers--二，三次手術max--

48
00:01:58,385 --> 00:02:01,480
而我們能夠插槽人
中的任意位置成一個列表。

49
00:02:01,480 --> 00:02:03,550
>> 還有什麼是有利的
關於鍊錶？

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
是嗎？

52
00:02:05,659 --> 00:02:06,534
>> 聽眾：[聽不清]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID馬蘭：完美。

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
完美的。

57
00:02:11,090 --> 00:02:12,070
這真是動力。

58
00:02:12,070 --> 00:02:15,100
和你沒有犯，
事先，以一些固定的大小

59
00:02:15,100 --> 00:02:18,750
內存塊，就像你會
用一個數組，則上行其中

60
00:02:18,750 --> 00:02:22,455
是，你只能分配上的節點
需求從而只用盡可能多的空間

61
00:02:22,455 --> 00:02:23,330
當你真正需要的。

62
00:02:23,330 --> 00:02:26,830
通過與數組相反，你可能會
一不小心分配太少。

63
00:02:26,830 --> 00:02:28,871
然後它只是去
是在頸部疼痛

64
00:02:28,871 --> 00:02:32,440
重新分配一個新的更大的陣列中，複製
一切都結束了，釋放舊陣列，

65
00:02:32,440 --> 00:02:33,990
然後將您的業務。

66
00:02:33,990 --> 00:02:37,479
或者更糟的是，你可能會分配方式
更多的內存比實際需要，

67
00:02:37,479 --> 00:02:40,520
所以你將有一個非常
人煙稀少的陣列，可以這麼說。

68
00:02:40,520 --> 00:02:44,350
>> 因此，一個鍊錶為您提供了這些
活力和靈活性的優勢

69
00:02:44,350 --> 00:02:46,080
與插入和缺失。

70
00:02:46,080 --> 00:02:48,000
但肯定要有付出了代價。

71
00:02:48,000 --> 00:02:50,000
其實，一個主題
探索對測驗為零

72
00:02:50,000 --> 00:02:52,430
一對夫婦的取捨
我們已經看到迄今。

73
00:02:52,430 --> 00:02:56,161
那麼，什麼是付出了代價或
下行的鏈接列表？

74
00:02:56,161 --> 00:02:56,660
是啊。

75
00:02:56,660 --> 00:02:57,560
>> 聽眾：沒有隨機訪問。

76
00:02:57,560 --> 00:02:58,809
>> DAVID馬蘭：沒有隨機訪問。

77
00:02:58,809 --> 00:02:59,540
但誰在乎呢？

78
00:02:59,540 --> 00:03:01,546
隨機存取聽起來並不引人注目。

79
00:03:01,546 --> 00:03:02,421
>> 聽眾：[聽不清]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID馬蘭：沒錯。

82
00:03:05,740 --> 00:03:07,580
如果你想有
一定的算法 - 

83
00:03:07,580 --> 00:03:10,170
讓我真正提出
在特定的二進制搜索，這

84
00:03:10,170 --> 00:03:12,600
是我們使用相當bit--
如果你沒有隨機訪問，

85
00:03:12,600 --> 00:03:15,516
你不能這樣做簡單的算術題
找到喜歡的中間元件的

86
00:03:15,516 --> 00:03:16,530
和跳躍的權利吧。

87
00:03:16,530 --> 00:03:20,239
你代替不得不開始在所述第一
元素，並從左邊線搜索

88
00:03:20,239 --> 00:03:22,780
向右如果你想找到
中間的或任何其他元件。

89
00:03:22,780 --> 00:03:24,410
>> 聽眾：它可能需要更多的內存。

90
00:03:24,410 --> 00:03:25,040
>> DAVID馬蘭：需要更多的內存。

91
00:03:25,040 --> 00:03:27,464
哪裡是額外的
成本從內存中來？

92
00:03:27,464 --> 00:03:28,339
>> 聽眾：[聽不清]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID馬蘭：沒錯。

95
00:03:33,440 --> 00:03:35,679
在這裡這種情況下，我們有
鍊錶為整數，

96
00:03:35,679 --> 00:03:37,470
但我們正在加倍
的內存量

97
00:03:37,470 --> 00:03:39,680
我們需要同時存儲這些指針。

98
00:03:39,680 --> 00:03:42,090
現在少了一個大問題，因為
您的結構得到較大

99
00:03:42,090 --> 00:03:45,320
與你存儲不是一個數字，但
也許學生或其他物體。

100
00:03:45,320 --> 00:03:46,880
但有一點毫無疑問依然存在。

101
00:03:46,880 --> 00:03:49,421
等數的操作的
上鍊錶被稱為

102
00:03:49,421 --> 00:03:50,570
是N--線性的大O。

103
00:03:50,570 --> 00:03:54,730
之類的東西插入或搜索
或缺失的情況下的元素

104
00:03:54,730 --> 00:03:57,720
正好是在最末端
無論是排序或不列表。

105
00:03:57,720 --> 00:04:01,167
>> 有時候，你可能會得到幸運和
這些操作使下界

106
00:04:01,167 --> 00:04:04,250
也可能是恆定的時間，如果你
一直在尋找的第一個元素，

107
00:04:04,250 --> 00:04:05,070
例如。

108
00:04:05,070 --> 00:04:09,360
但最終，我們承諾
實現了制勝法寶

109
00:04:09,360 --> 00:04:12,630
數據結構，或
一些近似物，

110
00:04:12,630 --> 00:04:14,290
通過固定時間的方式。

111
00:04:14,290 --> 00:04:17,579
我們可以發現元素或添加元素
或刪除列表中的元素？

112
00:04:17,579 --> 00:04:19,059
我們將很很快就會看到。

113
00:04:19,059 --> 00:04:21,100
而事實證明，一個
我們的機制

114
00:04:21,100 --> 00:04:23,464
要開始用至今，
在P年利用設置5，

115
00:04:23,464 --> 00:04:24,630
實際上是非常熟悉的。

116
00:04:24,630 --> 00:04:27,430
例如，如果這是一串
考試圖書，其中每一個

117
00:04:27,430 --> 00:04:29,660
有一個學生的第一
它的名字和姓氏，

118
00:04:29,660 --> 00:04:31,820
我去接他們從
在考試結束後，

119
00:04:31,820 --> 00:04:33,746
而且他們都非常
多以隨機的順序，

120
00:04:33,746 --> 00:04:36,370
我們要著手整理
這些考試，因此一旦分級

121
00:04:36,370 --> 00:04:38,661
它只是一個極大的方便，
快交出他們回來了

122
00:04:38,661 --> 00:04:40,030
學生按字母順序排列。

123
00:04:40,030 --> 00:04:42,770
什麼你的直覺會
一摞這樣的考試？

124
00:04:42,770 --> 00:04:45,019
>> 好吧，如果你像我一樣，你
可以看出這是米，

125
00:04:45,019 --> 00:04:48,505
所以我要那種把這個成，
如果這是我的表或我的樓，

126
00:04:48,505 --> 00:04:50,650
我的東西蔓延
out--或我的數組really--

127
00:04:50,650 --> 00:04:52,210
我可以把所有的小姐在那裡。

128
00:04:52,210 --> 00:04:52,710
呵呵。

129
00:04:52,710 --> 00:04:55,020
這裡有一個答，所以我可能
把作為過來。

130
00:04:55,020 --> 00:04:55,520
呵呵。

131
00:04:55,520 --> 00:04:57,980
這裡的另一個A.我要去
把該在這裡。

132
00:04:57,980 --> 00:05:02,490
這裡有一個Z.這裡是另一個M.所以
我可能會開始做樁這樣的。

133
00:05:02,490 --> 00:05:06,620
然後，也許我以後會去
樣的，非常挑剔-LY排序

134
00:05:06,620 --> 00:05:07,710
個別樁。

135
00:05:07,710 --> 00:05:11,300
但問題是，我想看看
那個我手輸入

136
00:05:11,300 --> 00:05:14,016
我會做一些計算
基於該輸入決定。

137
00:05:14,016 --> 00:05:15,640
如果以A開頭，把它放在那邊。

138
00:05:15,640 --> 00:05:18,980
如果它以Z開頭，把它放在
在那裡，一切都在兩者之間。

139
00:05:18,980 --> 00:05:22,730
>> 因此，這是一種技術，是
一般被稱為hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
這通常意味著要為
輸入，並使用該輸入來計算

141
00:05:26,550 --> 00:05:30,940
的值，通常是一個數字，那
號為索引到一個存儲

142
00:05:30,940 --> 00:05:32,260
容器，如一個數組。

143
00:05:32,260 --> 00:05:35,490
所以，換句話說，我可能有一個
散列函數，像我一樣在我的腦海，

144
00:05:35,490 --> 00:05:37,940
如果我看到有人的
誰的名字開始與A，

145
00:05:37,940 --> 00:05:40,190
我要去映射
零在我的腦海。

146
00:05:40,190 --> 00:05:44,160
如果我看到有人用Z，我
要映射至25日在我頭上

147
00:05:44,160 --> 00:05:46,220
然後它放入
最後最樁。

148
00:05:46,220 --> 00:05:50,990
>> 現在，如果你覺得不是我的大腦
但一個C程序，有什麼數字可能

149
00:05:50,990 --> 00:05:53,170
你靠什麼來實現同樣的結果呢？

150
00:05:53,170 --> 00:05:55,594
換句話說，如果
有ASCII字符A，

151
00:05:55,594 --> 00:05:57,510
你如何確定
什麼桶把它呢？

152
00:05:57,510 --> 00:05:59,801
你可能不希望
把它放進水桶65，這

153
00:05:59,801 --> 00:06:01,840
會像那邊
沒有很好的理由。

154
00:06:01,840 --> 00:06:04,320
你在哪裡要放
在它的ASCII值是多少？

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
你想去哪裡做的ASCII
值拿出一個更聰明的水桶

157
00:06:08,920 --> 00:06:09,480
把它呢？

158
00:06:09,480 --> 00:06:10,206
>> 聽眾：負A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID馬蘭：是啊。

160
00:06:10,956 --> 00:06:13,190
因此，減去或減
特別是65，如果是

161
00:06:13,190 --> 00:06:18,240
資本A.或98，如果
這是一個小寫。

162
00:06:18,240 --> 00:06:21,300
所以這將允許我們，很
簡單，非常算術，

163
00:06:21,300 --> 00:06:23,260
把東西放到這樣一個水桶。

164
00:06:23,260 --> 00:06:26,010
所以，事實證明，我們實際上做
這個問題，以及即使有測驗。

165
00:06:26,010 --> 00:06:29,051
>> 所以，你可能還記得你的盤旋
封面上的教學老鄉的名字。

166
00:06:29,051 --> 00:06:32,270
而TF的名字被組織
到這些列的字母順序，

167
00:06:32,270 --> 00:06:34,400
好了，不管你信不信，
當所有80加上我們

168
00:06:34,400 --> 00:06:37,800
聚在一起的那天晚上等級，
在我們的分級過程中的最後一步

169
00:06:37,800 --> 00:06:41,830
是散列測驗變成了大
地板在[聽不清]空間

170
00:06:41,830 --> 00:06:45,110
並奠定了大家的測驗出來
在他們TF的確切順序

171
00:06:45,110 --> 00:06:47,700
在蓋的名稱，因為
那麼它對於我們來說容易得多

172
00:06:47,700 --> 00:06:51,290
通過使用線性搜索
搜索或某種聰明

173
00:06:51,290 --> 00:06:54,050
對於TF找到他或
她的學生的測驗。

174
00:06:54,050 --> 00:06:56,060
>> 所以這個想法散列
你將看到的是

175
00:06:56,060 --> 00:07:00,520
功能相當強大實際上是非常
司空見慣，非常直觀，

176
00:07:00,520 --> 00:07:03,000
很像也許是分而
征服是零一周。

177
00:07:03,000 --> 00:07:05,250
我快進到黑客馬拉松
幾年前。

178
00:07:05,250 --> 00:07:08,040
這是Zamyla和一對夫婦的
其他工作人員的問候學生

179
00:07:08,040 --> 00:07:09,030
因為他們進來了。

180
00:07:09,030 --> 00:07:12,680
我們有一大堆折疊
表中有與名稱標籤。

181
00:07:12,680 --> 00:07:15,380
我們有名稱標籤組織
有喜歡當那邊

182
00:07:15,380 --> 00:07:16,690
和ZS的那邊。

183
00:07:16,690 --> 00:07:20,350
這樣一來，課題組的一個非常巧妙
寫這個的說明

184
00:07:20,350 --> 00:07:21,030
為天。

185
00:07:21,030 --> 00:07:24,480
而在本學期的第12週
所有的非常有意義，每個人都

186
00:07:24,480 --> 00:07:25,310
知道該怎麼做。

187
00:07:25,310 --> 00:07:27,900
但是，任何時候，你已經
排隊以同樣的方式，

188
00:07:27,900 --> 00:07:30,272
你實現
散列相同的概念。

189
00:07:30,272 --> 00:07:31,730
因此，讓我們正式那麼一點點。

190
00:07:31,730 --> 00:07:32,890
這裡是一個數組。

191
00:07:32,890 --> 00:07:36,820
它繪製的是一個小
寬只是描繪，直觀，

192
00:07:36,820 --> 00:07:38,920
我們不妨把字符串
在這樣的事情。

193
00:07:38,920 --> 00:07:41,970
這陣
顯然是大小共26件。

194
00:07:41,970 --> 00:07:43,935
而且東西被稱為
表隨意。

195
00:07:43,935 --> 00:07:48,930
但是，這僅僅是一個藝術家的再現
什麼樣的哈希表可能。

196
00:07:48,930 --> 00:07:52,799
>> 這樣一個哈希表現在將要
是一個更高層次的數據結構。

197
00:07:52,799 --> 00:07:54,840
在一天結束時
我們即將看到你

198
00:07:54,840 --> 00:07:58,700
可以實現一個哈希表，該表
很像登機

199
00:07:58,700 --> 00:08:02,059
在黑客馬拉松就像這樣
表用於排序的考試書籍。

200
00:08:02,059 --> 00:08:03,850
但一個哈希表
這個排序高水平的

201
00:08:03,850 --> 00:08:08,250
概念，可以使用一個數組
在底層實現它，

202
00:08:08,250 --> 00:08:11,890
或者它可以使用一個長列表，或者甚至
也許一些其他的數據結構。

203
00:08:11,890 --> 00:08:15,590
而現在這就是theme--回吐
一些基本的成分

204
00:08:15,590 --> 00:08:18,310
就像一個數組，這個建築
現在阻止長名單

205
00:08:18,310 --> 00:08:21,740
，看到什麼，我們可以建立
關於這些的頂端，像成分

206
00:08:21,740 --> 00:08:26,550
成一個配方，使得越來越多的
有趣的和有用的最終結果。

207
00:08:26,550 --> 00:08:28,680
>> 所以用哈希表
我們可以實現它

208
00:08:28,680 --> 00:08:32,540
在內存中形象地這樣，但
怎麼可能它實際上被編碼嗎？

209
00:08:32,540 --> 00:08:33,789
好吧，也許因為簡單地說就是這個。

210
00:08:33,789 --> 00:08:38,270
如果產能全部大寫，只是
一些constant--比如26，

211
00:08:38,270 --> 00:08:42,030
為alphabet--的26個字母
我可以叫我的變量表，

212
00:08:42,030 --> 00:08:45,630
我也許會說，我要去
把炭明星在那裡，或字符串。

213
00:08:45,630 --> 00:08:49,880
因此，它是如此簡單，如果你
要實現一個哈希表。

214
00:08:49,880 --> 00:08:51,490
然而，這真的只是一個數組。

215
00:08:51,490 --> 00:08:53,198
但同樣，一個散列
表是現在我們所會

216
00:08:53,198 --> 00:08:57,470
調用一個抽象數據類型，這只是
排序在最前面的概念分層

217
00:08:57,470 --> 00:09:00,780
東西更現實
現在喜歡一個數組。

218
00:09:00,780 --> 00:09:02,960
>> 現在，該怎麼辦才好
關於解決問題？

219
00:09:02,960 --> 00:09:06,980
嗯，剛才我已經奢侈
這裡有足夠的表空間

220
00:09:06,980 --> 00:09:09,460
這樣我就可以把
測驗的任何地方我想要的。

221
00:09:09,460 --> 00:09:10,620
這樣可能會去這裡。

222
00:09:10,620 --> 00:09:12,100
ZS可能會去這裡。

223
00:09:12,100 --> 00:09:13,230
小姐可能會去這裡。

224
00:09:13,230 --> 00:09:14,740
然後我有一些額外的空間。

225
00:09:14,740 --> 00:09:18,740
但是，這是一個有點作弊權
因為現在這個表，如果我真的

226
00:09:18,740 --> 00:09:22,720
想到這是一個數組，只是
一些將要固定的尺寸。

227
00:09:22,720 --> 00:09:25,380
>> 所以，從技術上說，如果我拉
了另一名學生的測驗

228
00:09:25,380 --> 00:09:28,490
看看，哦，這個人的
名稱與A開始過，

229
00:09:28,490 --> 00:09:30,980
我有點想要把它放在那裡。

230
00:09:30,980 --> 00:09:34,740
但是，當我把它放在那裡，如果
這個表確實表示一個數組，

231
00:09:34,740 --> 00:09:37,840
我會被覆蓋或重挫
誰該學生的測驗是。

232
00:09:37,840 --> 00:09:38,340
對不對？

233
00:09:38,340 --> 00:09:41,972
如果這是一個數組，只有一件事可以
走在這些細胞或元件。

234
00:09:41,972 --> 00:09:43,680
所以，我種有
挑選。

235
00:09:43,680 --> 00:09:45,735
>> 剛才那種下面我
被騙了，做這個還是我

236
00:09:45,735 --> 00:09:47,526
只是一種堆疊
他們在彼此之上。

237
00:09:47,526 --> 00:09:49,170
但是，這並不是要在代碼中飛翔。

238
00:09:49,170 --> 00:09:52,260
那麼，我能放
第二個學生的名字

239
00:09:52,260 --> 00:09:54,964
是A，如果所有我是這樣的
可用的表空間？

240
00:09:54,964 --> 00:09:57,880
而且我用三個插槽，它
貌似有只是少數人。

241
00:09:57,880 --> 00:09:58,959
你該怎麼辦？

242
00:09:58,959 --> 00:09:59,834
聽眾：[聽不清]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID馬蘭：是啊。

245
00:10:01,315 --> 00:10:02,370
也許我們只是保持簡單。

246
00:10:02,370 --> 00:10:02,660
對不對？

247
00:10:02,660 --> 00:10:04,243
它不適合在這裡我想把它。

248
00:10:04,243 --> 00:10:07,450
所以我打算把它放在
技術上，其中A，B會去。

249
00:10:07,450 --> 00:10:09,932
當然，現在，我開始
畫自己陷入了困境。

250
00:10:09,932 --> 00:10:11,890
如果我去一個學生
他的名字實際上是B，

251
00:10:11,890 --> 00:10:14,840
現在乙將要被移動一點點
未來，為可能發生的事情，是的，

252
00:10:14,840 --> 00:10:17,530
如果這是一個B中，現在它已去這裡。

253
00:10:17,530 --> 00:10:20,180
>> 所以這非常迅速
可能成為問題，

254
00:10:20,180 --> 00:10:23,850
但它是一個技術，實際上是
被稱為線性探測，

255
00:10:23,850 --> 00:10:26,650
因此你只要考慮你
陣列是沿著線。

256
00:10:26,650 --> 00:10:29,680
正中下懷，你探頭或
檢查每個可用的元素

257
00:10:29,680 --> 00:10:31,360
尋找一個備有現貨。

258
00:10:31,360 --> 00:10:34,010
而且只要你找到
1，你在那裡將其刪除。

259
00:10:34,010 --> 00:10:38,390
>> 現在，這個價格現在正在支付
這個解決方案是什麼？

260
00:10:38,390 --> 00:10:41,300
我們有一個固定大小的數組，
當我插入的名字

261
00:10:41,300 --> 00:10:44,059
進去，至少在最初階段，有什麼
插入的運行時間

262
00:10:44,059 --> 00:10:46,350
為把學生
在右邊的桶測驗？

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
什麼大O？

265
00:10:50,002 --> 00:10:51,147
>> 聽眾：N。

266
00:10:51,147 --> 00:10:52,480
DAVID馬蘭：我聽說的n大O。

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
事實並非如此。

269
00:10:54,300 --> 00:10:56,490
但我們將梳理出
為什麼在短短的一瞬間。

270
00:10:56,490 --> 00:10:57,702
還有什麼會是什麼？

271
00:10:57,702 --> 00:10:58,755
>> 聽眾：[聽不清]

272
00:10:58,755 --> 00:11:00,380
DAVID馬蘭：讓我做視覺。

273
00:11:00,380 --> 00:11:04,720
因此，假設這是字母S.

274
00:11:04,720 --> 00:11:05,604
>> 聽眾：這是之一。

275
00:11:05,604 --> 00:11:06,520
DAVID馬蘭：這是之一。

276
00:11:06,520 --> 00:11:06,710
對不對？

277
00:11:06,710 --> 00:11:08,950
這是一個數組，它
意味著我們有隨機訪問。

278
00:11:08,950 --> 00:11:11,790
如果我們認為這
零，這為25，

279
00:11:11,790 --> 00:11:13,800
我們認識到，
哦，這是我的輸入S，

280
00:11:13,800 --> 00:11:16,350
我當然可以轉換
S，一個ASCII字符，

281
00:11:16,350 --> 00:11:18,540
到一個相應的數字
零到25之間

282
00:11:18,540 --> 00:11:20,910
然後立即
把它原來的位置。

283
00:11:20,910 --> 00:11:26,120
>> 但當然，當我到達
第二個人誰的名字是A或B或C

284
00:11:26,120 --> 00:11:29,300
最後，如果我用了
線性探測作為我的解決方案，

285
00:11:29,300 --> 00:11:31,360
的運行時間
插入在最壞的情況下

286
00:11:31,360 --> 00:11:33,120
實際上是要下放成什麼樣？

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
我也聽到了這裡
正確的早期。

289
00:11:36,045 --> 00:11:36,920
聽眾：[聽不清]

290
00:11:36,920 --> 00:11:41,620
DAVID馬蘭：所以這是正確一次
有一個足夠大的數據集。

291
00:11:41,620 --> 00:11:44,410
這樣，一方面，如果
陣列足夠大

292
00:11:44,410 --> 00:11:48,287
和你的數據是稀疏的話，你
得到這個美麗的固定時間。

293
00:11:48,287 --> 00:11:50,620
但只要你開始
越來越多的元素，

294
00:11:50,620 --> 00:11:53,200
而只是統計上你
更多的人信

295
00:11:53,200 --> 00:11:56,030
A作為自己的名稱或字母
B時，它可能潛在

296
00:11:56,030 --> 00:11:57,900
下放成更線性的。

297
00:11:57,900 --> 00:11:59,640
所以，不是很完美。

298
00:11:59,640 --> 00:12:00,690
所以，我們可以做的更好？

299
00:12:00,690 --> 00:12:03,210
>> 那麼，什麼是我們的
之前的解決方案時，我們

300
00:12:03,210 --> 00:12:06,820
希望有更多的比活力
像一個數組允許的？

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
聽眾：[聽不清]

303
00:12:08,960 --> 00:12:10,030
DAVID馬蘭：沒有介紹什麼？

304
00:12:10,030 --> 00:12:10,530
是啊。

305
00:12:10,530 --> 00:12:11,430
這樣一個鍊錶。

306
00:12:11,430 --> 00:12:14,430
好吧，讓我們看看一個鏈接
清單可能對我們不是做的。

307
00:12:14,430 --> 00:12:17,630
那麼，讓我建議大家
畫圖如下。

308
00:12:17,630 --> 00:12:19,620
現在這是一個不同的
從例圖

309
00:12:19,620 --> 00:12:24,750
從不同的文本，實際上，這
實際上是用粒度31的陣列。

310
00:12:24,750 --> 00:12:28,220
而筆​​者簡單
決定散列字符串

311
00:12:28,220 --> 00:12:32,430
不基於該人的姓名，
但基於其生日。

312
00:12:32,430 --> 00:12:35,680
不論該月，他們得出
如果你在第一次一個月的正在誕生

313
00:12:35,680 --> 00:12:39,580
或一個月的31日，筆者
基於該值會出現亂碼，

314
00:12:39,580 --> 00:12:44,154
從而被散佈的名字出一個位
不僅僅是26點可能會允許。

315
00:12:44,154 --> 00:12:47,320
也許這是一個小更均勻
比用字母去，

316
00:12:47,320 --> 00:12:50,236
當然，因為有可能
更多的人在世界上的名字

317
00:12:50,236 --> 00:12:54,020
開始的被肯定比
其他一些英文字母。

318
00:12:54,020 --> 00:12:56,380
所以，也許這是一個小
更均勻，假定

319
00:12:56,380 --> 00:12:58,640
均勻分佈
的嬰兒跨越了一個月。

320
00:12:58,640 --> 00:12:59,990
>> 但是，當然，這仍然是不完美的。

321
00:12:59,990 --> 00:13:00,370
對不對？

322
00:13:00,370 --> 00:13:01,370
我們有衝突。

323
00:13:01,370 --> 00:13:04,680
多人在這
數據結構仍然

324
00:13:04,680 --> 00:13:08,432
具有相同的出生日期的至少
你不論一個月。

325
00:13:08,432 --> 00:13:09,640
但什麼筆者做了什麼？

326
00:13:09,640 --> 00:13:13,427
好吧，看來我們有一個數組
在左側的垂直繪製，

327
00:13:13,427 --> 00:13:15,010
但是這只是一個藝術家的再現。

328
00:13:15,010 --> 00:13:18,009
不要緊，什麼方向，你
畫一個數組，它仍然是一個數組。

329
00:13:18,009 --> 00:13:20,225
這是什麼的顯然是一個數組？

330
00:13:20,225 --> 00:13:21,500
>> 聽眾：鍊錶。

331
00:13:21,500 --> 00:13:21,650
>> DAVID馬蘭：是啊。

332
00:13:21,650 --> 00:13:23,490
它看起來像它的一個
陣列的鍊錶。

333
00:13:23,490 --> 00:13:26,490
如此反复，這點排序
利用這些數據結構現在的

334
00:13:26,490 --> 00:13:28,550
作為成分更多
有趣的解決方案，

335
00:13:28,550 --> 00:13:30,862
你完全可以採取
基本一樣的陣列，

336
00:13:30,862 --> 00:13:33,320
然後拿更多的東西
有趣像一個鍊錶

337
00:13:33,320 --> 00:13:36,660
甚至將它們組合成一個更
更有趣的數據結構。

338
00:13:36,660 --> 00:13:39,630
事實上，這也將
被稱為哈希表

339
00:13:39,630 --> 00:13:42,610
由此，陣列是
真哈希表，

340
00:13:42,610 --> 00:13:45,600
但是哈希表中有
鏈，可以這麼說，

341
00:13:45,600 --> 00:13:50,220
可增大或縮小基礎上，
你想要的元素的數量插入。

342
00:13:50,220 --> 00:13:52,990
>> 現在，因此，什麼是
在運行的時候嗎？

343
00:13:52,990 --> 00:13:58,030
如果我要插入人
他的生日是10月31日，

344
00:13:58,030 --> 00:13:59,040
在那裡他或她去嗎？

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
行。

347
00:14:01,030 --> 00:14:02,819
在最底層的地方說31。

348
00:14:02,819 --> 00:14:03,610
這就是完美的。

349
00:14:03,610 --> 00:14:05,060
那是一定的時間。

350
00:14:05,060 --> 00:14:08,760
但是，如果我們發現了什麼別人
他的生日，讓我們來看看，

351
00:14:08,760 --> 00:14:10,950
十月，十一月，十二月三十一日止？

352
00:14:10,950 --> 00:14:12,790
哪裡是他或她會去嗎？

353
00:14:12,790 --> 00:14:13,290
同樣的事情。

354
00:14:13,290 --> 00:14:13,970
兩步雖然。

355
00:14:13,970 --> 00:14:15,303
這是恆定的，雖然不是嗎？

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
行。

358
00:14:16,860 --> 00:14:17,840
目前，它是。

359
00:14:17,840 --> 00:14:20,570
但在一般情況下，
越來越多的人加入我們，

360
00:14:20,570 --> 00:14:23,790
概率，我們要
得到越來越多的碰撞。

361
00:14:23,790 --> 00:14:26,820
>> 現在，這是一個小
更好，因為在技術上

362
00:14:26,820 --> 00:14:34,580
現在我的連鎖店可以在
在最壞的情況下多久？

363
00:14:34,580 --> 00:14:38,890
如果我插入N多人進入這個多
複雜的數據結構，N多人，

364
00:14:38,890 --> 00:14:41,080
在最壞的情況下，它會為n。

365
00:14:41,080 --> 00:14:41,815
為什麼呢？

366
00:14:41,815 --> 00:14:43,332
>> 聽眾：因為如果每個人都
有相同的生日，

367
00:14:43,332 --> 00:14:44,545
他們將成為一條線。

368
00:14:44,545 --> 00:14:45,420
DAVID馬蘭：完美。

369
00:14:45,420 --> 00:14:47,480
這可能是一個有點做作，
但真正在最壞的情況下，

370
00:14:47,480 --> 00:14:50,117
如果每個人都擁有相同的生日，
給你的投入，

371
00:14:50,117 --> 00:14:51,950
你將有一個
大量的長鏈。

372
00:14:51,950 --> 00:14:54,241
所以，你可以把它稱為一個
哈希表，但實際上它是

373
00:14:54,241 --> 00:14:56,810
只是一個大規模的鍊錶
一大堆浪費的空間。

374
00:14:56,810 --> 00:15:00,460
但在一般情況下，如果我們假定
至少生日是uniform--

375
00:15:00,460 --> 00:15:01,750
它可能不是。

376
00:15:01,750 --> 00:15:02,587
我正在做這件事。

377
00:15:02,587 --> 00:15:04,420
但是，如果我們假定，對於
就事論事

378
00:15:04,420 --> 00:15:07,717
它們是，那麼在理論上，如果
這是垂直的表示

379
00:15:07,717 --> 00:15:11,050
數組的，那麼希望你
將得到的是，你知道鏈，

380
00:15:11,050 --> 00:15:15,880
大致相同的長度，其中每個
這些代表月中的某一天。

381
00:15:15,880 --> 00:15:19,930
>> 現在，如果有31天的月份，
這意味著我的運行時間真的

382
00:15:19,930 --> 00:15:25,230
為n超過31大O，這
感覺比線性好。

383
00:15:25,230 --> 00:15:27,950
但是，什麼是我們的一個
承諾一兩個星期

384
00:15:27,950 --> 00:15:31,145
以前，每當它來表達
一個算法的運行時間？

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
剛剛只看高次項。

387
00:15:35,190 --> 00:15:35,690
對不對？

388
00:15:35,690 --> 00:15:37,400
31絕對是有幫助的。

389
00:15:37,400 --> 00:15:39,610
但是，這仍然是n個大O。

390
00:15:39,610 --> 00:15:41,730
但主題之一
問題設置5

391
00:15:41,730 --> 00:15:43,950
將是對
承認絕對的，

392
00:15:43,950 --> 00:15:47,320
漸近，理論上
這種數據結構

393
00:15:47,320 --> 00:15:50,470
沒有比剛剛好
一台龐大的鍊錶。

394
00:15:50,470 --> 00:15:53,550
而事實上，在最壞的情況下，這
哈希表可能下放成。

395
00:15:53,550 --> 00:15:57,620
>> 但在現實世界中，我們人類
那自己的Mac或PC或其他

396
00:15:57,620 --> 00:16:01,240
而正在運行真實世界
軟件在真實世界中的數據，

397
00:16:01,240 --> 00:16:03,260
該算法你要選哪個？

398
00:16:03,260 --> 00:16:09,180
而其中，需要結束步驟或
一種採用N以31級分

399
00:16:09,180 --> 00:16:12,900
找一些數據塊或
找了一些資料？

400
00:16:12,900 --> 00:16:16,580
我的意思是，絕對是31品牌
在現實世界中的差。

401
00:16:16,580 --> 00:16:18,540
這是快31倍。

402
00:16:18,540 --> 00:16:20,880
而我們人類是肯定
要明白這一點。

403
00:16:20,880 --> 00:16:23,004
>> 因此，實現二分法
之間居然有

404
00:16:23,004 --> 00:16:25,920
說起理論上的東西
和漸近這無疑

405
00:16:25,920 --> 00:16:28,760
具有價值，因為我們已經看到，
但在現實世界中，

406
00:16:28,760 --> 00:16:32,930
如果你關心只是使
人類對幸福的通用輸入，

407
00:16:32,930 --> 00:16:36,010
你很可能要接受
事實證明，是的，這是線性的，

408
00:16:36,010 --> 00:16:38,360
但它的速度更快31倍
比線性可能。

409
00:16:38,360 --> 00:16:41,610
而且更重要的是，我們不只是要
做一些亂像一個生日，

410
00:16:41,610 --> 00:16:44,030
我們可以花一點
更多的時間和聰明

411
00:16:44,030 --> 00:16:47,140
想想我們可能會做，
定一個人的名字，也許

412
00:16:47,140 --> 00:16:50,130
他們的出生日期相結合的
成分搞清楚的東西

413
00:16:50,130 --> 00:16:52,720
這是真正的多
均勻，少鋸齒，

414
00:16:52,720 --> 00:16:56,250
這麼說不是這幅畫
目前表明它可能是。

415
00:16:56,250 --> 00:16:57,750
在代碼中，我們如何才能實現呢？

416
00:16:57,750 --> 00:17:00,280
那麼，讓我建議大家
只是借用一些語法，我們已經

417
00:17:00,280 --> 00:17:01,799
使用幾次迄今。

418
00:17:01,799 --> 00:17:03,590
我要去定義
一節點，該節點再次

419
00:17:03,590 --> 00:17:06,812
是一個通用術語，只是一些
容器為一些數據結構。

420
00:17:06,812 --> 00:17:09,020
我要建議
字符串會在那裡。

421
00:17:09,020 --> 00:17:11,369
但是，我們要開始服用
這些培訓輪子掉了。

422
00:17:11,369 --> 00:17:13,230
>> 沒有更多的CS50庫
真的，除非你想

423
00:17:13,230 --> 00:17:15,230
將其用於您的最終
項目，這是好的，

424
00:17:15,230 --> 00:17:18,569
但現在我們要拉回來了
窗簾，說這只是一個char明星。

425
00:17:18,569 --> 00:17:22,069
所以這個詞有將是
有問題的人的名字。

426
00:17:22,069 --> 00:17:25,079
現在我有一個鏈接
這裡下一個節點

427
00:17:25,079 --> 00:17:28,170
使這些代表
每個節點

428
00:17:28,170 --> 00:17:30,950
在鏈中，潛在地，
的一個鍊錶。

429
00:17:30,950 --> 00:17:34,090
>> 現在該怎麼辦，我宣布
哈希表本身？

430
00:17:34,090 --> 00:17:36,660
我如何申報這整個結構？

431
00:17:36,660 --> 00:17:40,960
好了，說真的，就像我用一個指針
以列表的只是第一元件

432
00:17:40,960 --> 00:17:44,510
之前，同樣我能說
我只需要一堆指針

433
00:17:44,510 --> 00:17:46,270
實現這整個哈希表。

434
00:17:46,270 --> 00:17:49,484
我將有一個數組
所謂表為哈希表。

435
00:17:49,484 --> 00:17:50,900
這將是規模生產能力。

436
00:17:50,900 --> 00:17:52,525
這就是很多元素可以適應它。

437
00:17:52,525 --> 00:17:56,180
並且每個在此這些元素的
陣列將是一個節點的明星。

438
00:17:56,180 --> 00:17:56,810
為什麼呢？

439
00:17:56,810 --> 00:18:00,160
那麼，每個這張照片，就是我
執行哈希表作為

440
00:18:00,160 --> 00:18:04,330
有效地在一開始僅僅是
這個數組，我們已經垂直繪製，

441
00:18:04,330 --> 00:18:06,820
其每個的平方
代表一個指針。

442
00:18:06,820 --> 00:18:09,170
那那些有斜杠
通過他們只是空。

443
00:18:09,170 --> 00:18:11,410
和那些有
箭頭要正確

444
00:18:11,410 --> 00:18:16,140
在實際指向實際的節點，
人體工程學的鏈接列表的開始。

445
00:18:16,140 --> 00:18:19,050
>> 所以在這裡的話，我們怎麼可能
實現一個哈希表，該表

446
00:18:19,050 --> 00:18:21,580
實現獨立的鏈接。

447
00:18:21,580 --> 00:18:22,840
現在，我們可以做的更好？

448
00:18:22,840 --> 00:18:25,632
好吧，我答應最後一次
我們可以實現一定的時間。

449
00:18:25,632 --> 00:18:27,381
我種了你
固定的時間在這裡，

450
00:18:27,381 --> 00:18:29,850
但後​​來說不是真的
固定的時間，因為它仍

451
00:18:29,850 --> 00:18:31,890
依賴於總上
元件的數目

452
00:18:31,890 --> 00:18:34,500
你輸入到
的數據結構。

453
00:18:34,500 --> 00:18:35,980
但是，假如我們這樣做。

454
00:18:35,980 --> 00:18:39,550
讓我回到屏幕在這裡。

455
00:18:39,550 --> 00:18:44,520
也讓我在這裡預測這件事，清楚
在屏幕上，並且假設我這樣做。

456
00:18:44,520 --> 00:18:49,300
假設我想插入的名字
Daven在為我的數據結構。

457
00:18:49,300 --> 00:18:52,100
>> 所以我想插入一個字符串
Daven成的數據結構。

458
00:18:52,100 --> 00:18:54,370
如果我不使用什麼
哈希表，但我用

459
00:18:54,370 --> 00:18:56,980
一些更樹狀
就像一個家族樹，其中

460
00:18:56,980 --> 00:18:59,670
你有一些根本的
頂部，然後節點和葉

461
00:18:59,670 --> 00:19:01,440
那去向下和向外。

462
00:19:01,440 --> 00:19:04,450
假設這時，我才
要插入Daven的

463
00:19:04,450 --> 00:19:06,430
到什麼是當前一個空列表。

464
00:19:06,430 --> 00:19:09,780
我要做到以下幾點：我
要在這個家庭創建節點

465
00:19:09,780 --> 00:19:15,170
樹狀數據結構，它看起來
有點像這樣的，其中每一個

466
00:19:15,170 --> 00:19:19,640
矩形有，比方說，
現在26在裡面的元素。

467
00:19:19,640 --> 00:19:21,650
和每個小區的
在這陣是怎麼回事

468
00:19:21,650 --> 00:19:23,470
代表字母表的字母。

469
00:19:23,470 --> 00:19:28,190
>> 具體來說，我要去治療
這是A，那麼B，然後是C，則D，

470
00:19:28,190 --> 00:19:29,310
這一個在這裡。

471
00:19:29,310 --> 00:19:32,940
所以這將有效地
代表字母D.

472
00:19:32,940 --> 00:19:36,040
但插入所有Daven年代
名字我需要做多一點。

473
00:19:36,040 --> 00:19:37,840
所以我首先要散列，可以這麼說。

474
00:19:37,840 --> 00:19:41,049
我要去看看第一個字母
在Daven的這顯然是一個D，

475
00:19:41,049 --> 00:19:42,840
我要去分配
看起來一個節點

476
00:19:42,840 --> 00:19:45,570
像this--一個大的矩形大
夠以適應整個字母表。

477
00:19:45,570 --> 00:19:47,140
>> 現在D被完成。

478
00:19:47,140 --> 00:19:49,720
現在A. D-A-V-E-N是目標。

479
00:19:49,720 --> 00:19:51,220
所以，現在我什麼都做的就是這一點。

480
00:19:51,220 --> 00:19:54,027
當我開始D的通知
沒有指針那裡。

481
00:19:54,027 --> 00:19:56,860
這是垃圾值的那一刻，
或者我可以把它初始化為空。

482
00:19:56,860 --> 00:19:59,630
不過，讓我趕上去
這個想法建立一個樹。

483
00:19:59,630 --> 00:20:04,260
讓我分配一個又一個的這些
節點中有26個元素。

484
00:20:04,260 --> 00:20:05,150
>> 你知道嗎？

485
00:20:05,150 --> 00:20:09,130
如果這僅僅是在存儲器中的節點
我使用malloc創建，用一個struct

486
00:20:09,130 --> 00:20:11,240
因為我們很快就會看到，
我該怎麼辦this--

487
00:20:11,240 --> 00:20:14,450
我會從畫一個箭頭
這代表的D-下來的東西

488
00:20:14,450 --> 00:20:15,860
該新節點。

489
00:20:15,860 --> 00:20:19,240
而現在，第一個下一個
信Daven的名字，

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V--我要繼續前進
並得出另一個節點是這樣，

491
00:20:24,150 --> 00:20:30,150
由此，此處的V族元素，其
我們將繪製的instance--哎呦。

492
00:20:30,150 --> 00:20:31,020
我們不會畫在那裡。

493
00:20:31,020 --> 00:20:31,936
它會去這裡。

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> 然後，我們要
認為這是V.

496
00:20:35,712 --> 00:20:44,920
再往下在這裡我們要索引
下來從V到我們會考慮E.

497
00:20:44,920 --> 00:20:50,100
然後從這裡，我們要
去這裡有這些節點之一。

498
00:20:50,100 --> 00:20:52,930
現在我們有一個問題來回答。

499
00:20:52,930 --> 00:20:57,840
我需要以某種方式表明，
我們在字符串Daven的結束。

500
00:20:57,840 --> 00:20:59,490
所以，我可以把它空。

501
00:20:59,490 --> 00:21:02,670
>> 但是，如果我們有Daven的
全名也，其

502
00:21:02,670 --> 00:21:04,280
是，正如我們已經說過，達文波特？

503
00:21:04,280 --> 00:21:06,970
所以，如果Daven是什麼
實際上是一個子串，

504
00:21:06,970 --> 00:21:08,960
一個更長的字符串的前綴？

505
00:21:08,960 --> 00:21:11,450
我們不能僅僅永久
什麼也不說是怎麼回事

506
00:21:11,450 --> 00:21:14,410
去那裡，因為我們可以
切勿將像達文波特一個字

507
00:21:14,410 --> 00:21:15,840
入該數據結構

508
00:21:15,840 --> 00:21:19,560
>> 所以，我們可以做的是
把這些元素

509
00:21:19,560 --> 00:21:22,170
因為也許有兩個
他們中的元素。

510
00:21:22,170 --> 00:21:24,810
一個是一個指針，的確，
因為我一直在做。

511
00:21:24,810 --> 00:21:27,100
所以每個這些框
不只是一個小區。

512
00:21:27,100 --> 00:21:29,855
但是，如果頂部
埃德蒙頓底部一個人的

513
00:21:29,855 --> 00:21:32,230
要為null，因為
有沒有達文波特，只是還沒有。

514
00:21:32,230 --> 00:21:34,197
如果那頂一個
為一些特殊的價值？

515
00:21:34,197 --> 00:21:36,530
而這將是一個小
很難得出它這種規模。

516
00:21:36,530 --> 00:21:38,130
但是，假如它只是一個复選標記。

517
00:21:38,130 --> 00:21:38,920
檢查。

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N是一個字符串
在此數據結構中。

519
00:21:44,230 --> 00:21:48,350
>> 同時，如果我有更多的空間
在這裡，我所能做的P-O-R-T，

520
00:21:48,350 --> 00:21:52,650
我可以把檢查的節點
有字母T在最後。

521
00:21:52,650 --> 00:21:55,460
因此，這是一個大規模
複雜的外觀的數據結構。

522
00:21:55,460 --> 00:21:57,210
和我的筆跡
肯定沒有幫助。

523
00:21:57,210 --> 00:22:00,043
但是，如果我想插入的東西
否則，考慮一下我們會怎麼做。

524
00:22:00,043 --> 00:22:03,370
如果我們希望把大衛，
我們會遵循同樣的邏輯，D-A-V，

525
00:22:03,370 --> 00:22:08,802
但現在我想指出，在未來
元素不是從E，但是從我到D.

526
00:22:08,802 --> 00:22:10,760
因此，有將是
在這棵樹多個節點。

527
00:22:10,760 --> 00:22:12,325
我們將不得不調用malloc更多。

528
00:22:12,325 --> 00:22:14,700
但是，我不想做一個
這幅畫的一塌糊塗。

529
00:22:14,700 --> 00:22:17,710
所以讓我們來看看1
一個已經預先制定

530
00:22:17,710 --> 00:22:21,810
像這樣與不點，點，
點，但只是略陣列。

531
00:22:21,810 --> 00:22:23,950
但每個節點
在這棵樹在這裡

532
00:22:23,950 --> 00:22:26,700
表示同一件事 - 
數組的大小26雷。

533
00:22:26,700 --> 00:22:28,860
>> 或者，如果我們想成為
現在真的很合適，有什麼

534
00:22:28,860 --> 00:22:30,790
如果某人的名字
一個撇號，讓我們

535
00:22:30,790 --> 00:22:35,560
假設每個節點實際上具有
像27指數在裡面，不只是26。

536
00:22:35,560 --> 00:22:42,020
所以這個現在將是一個數據
結構稱為trie-- T-R-I-E。

537
00:22:42,020 --> 00:22:46,120
一個線索，這是假想
歷史上的一棵樹一個聰明的名字

538
00:22:46,120 --> 00:22:49,040
這對優化
當然，檢索，其中，

539
00:22:49,040 --> 00:22:50,870
拼寫與I-E所以它的線索。

540
00:22:50,870 --> 00:22:52,710
但是，這是對線索的歷史。

541
00:22:52,710 --> 00:22:55,860
>> 因此，一個線索是這樣的樹狀數據
就像一個家庭樹結構

542
00:22:55,860 --> 00:22:57,510
最終表現那樣。

543
00:22:57,510 --> 00:23:00,890
這裡是一個又一個的例子
一大堆別人的名字。

544
00:23:00,890 --> 00:23:03,540
但現在的問題
手頭有什麼

545
00:23:03,540 --> 00:23:08,070
我們獲得了通過引入可以說是一個更
複雜的數據結構，和一，

546
00:23:08,070 --> 00:23:09,870
坦率地說，使用了大量的內存。

547
00:23:09,870 --> 00:23:11,703
>> 因為即使，
此刻，我只

548
00:23:11,703 --> 00:23:15,050
使用D的指針和
A和V和ES和NS，

549
00:23:15,050 --> 00:23:16,700
我在浪費大量的內存赫克。

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
但是，在這裡我度過一個資源，
我傾向於不爭回另一個。

552
00:23:22,660 --> 00:23:26,020
所以，如果我花了更多的空間，
什麼是可能的希望嗎？

553
00:23:26,020 --> 00:23:27,407
那我花少了什麼？

554
00:23:27,407 --> 00:23:28,240
聽眾：更少的時間。

555
00:23:28,240 --> 00:23:28,990
DAVID馬蘭：時間。

556
00:23:28,990 --> 00:23:30,320
現在為什麼會這樣呢？

557
00:23:30,320 --> 00:23:33,880
那麼，什麼是插
時間，在目前大O方面，

558
00:23:33,880 --> 00:23:37,660
像Daven一個名字
或者達文波特還是大衛？

559
00:23:37,660 --> 00:23:39,340
好吧，Daven是五個步驟。

560
00:23:39,340 --> 00:23:42,350
達文波特將九個步驟，
所以這將是一個幾個步驟。

561
00:23:42,350 --> 00:23:44,250
大衛將五個步驟為好。

562
00:23:44,250 --> 00:23:47,230
因此，這些都是具體的
數字，但肯定有

563
00:23:47,230 --> 00:23:49,550
的上限的
長別人的名字。

564
00:23:49,550 --> 00:23:52,240
而事實上，在該問題
台五規範，

565
00:23:52,240 --> 00:23:54,050
我們要提出
它的東西

566
00:23:54,050 --> 00:23:55,470
這是40-一些多字符。

567
00:23:55,470 --> 00:23:58,180
>> 實際上，沒有人有
一個無限長的名字，

568
00:23:58,180 --> 00:24:01,542
這就是說，一個長度
名稱或字符串的長度，我們可能

569
00:24:01,542 --> 00:24:03,750
有一定的狀態
結構可以說是什麼？

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
這是不變的。

572
00:24:06,250 --> 00:24:06,430
對不對？

573
00:24:06,430 --> 00:24:09,310
這可能是一個很大的不變樣
40多歲的，但它是恆定的。

574
00:24:09,310 --> 00:24:13,752
它有多少不依賴
其它名稱是在該數據結構中。

575
00:24:13,752 --> 00:24:15,460
換句話說，如果我
想現在插入

576
00:24:15,460 --> 00:24:20,540
科爾頓或加布里埃爾或搶或Zamyla或
艾莉森或貝琳達或任何其他名稱

577
00:24:20,540 --> 00:24:23,940
從工作人員到該數據
結構，是在運行時間

578
00:24:23,940 --> 00:24:26,750
中插入其他名稱
將要在所有受影響的

579
00:24:26,750 --> 00:24:30,220
被多少其他元素
在已經將數據結構？

580
00:24:30,220 --> 00:24:31,040
它不是。

581
00:24:31,040 --> 00:24:31,540
對不對？

582
00:24:31,540 --> 00:24:36,150
由於我們有效地利用
這個多層哈希表。

583
00:24:36,150 --> 00:24:38,280
和運行時間
這些操作

584
00:24:38,280 --> 00:24:41,510
取決於不上的數
這是在數據結構中的元素

585
00:24:41,510 --> 00:24:43,090
或者被最終將
是在數據結構中，

586
00:24:43,090 --> 00:24:44,714
但在什麼具體的長度是多少？

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> 該字符串是
插入，這確實讓

589
00:24:49,200 --> 00:24:52,580
這種漸進恆
一時間 - 大O。

590
00:24:52,580 --> 00:24:54,720
坦率地說，就在
現實世界中，這

591
00:24:54,720 --> 00:24:58,380
指插入Daven的名字取
像五個步驟，或者達文波特9

592
00:24:58,380 --> 00:25:00,100
步驟或大衛五個步驟。

593
00:25:00,100 --> 00:25:03,071
這是相當不錯的小的運行時間。

594
00:25:03,071 --> 00:25:05,320
而且，事實上，這是一個非常
好東西，尤其是當

595
00:25:05,320 --> 00:25:08,126
它不依賴於總量
在那裡的元素個數。

596
00:25:08,126 --> 00:25:10,500
那麼如何才能實現我們這個
這種結構的代碼？

597
00:25:10,500 --> 00:25:12,900
這是一個多一點
複雜，但它仍然是

598
00:25:12,900 --> 00:25:15,050
只是一個應用
基本構建塊。

599
00:25:15,050 --> 00:25:17,830
我要重新定義
我們節點如下：

600
00:25:17,830 --> 00:25:21,100
布爾稱為word--這
可以被稱為什麼。

601
00:25:21,100 --> 00:25:23,970
但布爾代表
我畫了一個對號。

602
00:25:23,970 --> 00:25:24,490
是。

603
00:25:24,490 --> 00:25:26,720
這是一個字符串的末尾
在此數據結構中。

604
00:25:26,720 --> 00:25:30,702
>> 並且，當然，節點星
有指兒童。

605
00:25:30,702 --> 00:25:32,410
而且，事實上，就像
一個家譜，你

606
00:25:32,410 --> 00:25:34,370
會考慮節點
被掛

607
00:25:34,370 --> 00:25:36,920
一些家長的底部
元素是兒童。

608
00:25:36,920 --> 00:25:40,510
這樣一來，孩子們將要
是27的數組，第27屆1

609
00:25:40,510 --> 00:25:41,680
擺明了撇號。

610
00:25:41,680 --> 00:25:43,390
我們要進行排序
的特殊情況。

611
00:25:43,390 --> 00:25:45,400
所以，你可以有一定
名稱以撇號。

612
00:25:45,400 --> 00:25:47,399
甚至連字符應
去那裡，但你

613
00:25:47,399 --> 00:25:50,330
見P組5，我們只關心
有關信件和單引號。

614
00:25:50,330 --> 00:25:52,990
>> 然後你怎麼代表
數據結構本身？

615
00:25:52,990 --> 00:25:56,454
你怎麼代表根
這個線索的，可以這麼說？

616
00:25:56,454 --> 00:25:59,620
嗯，就像一個鍊錶，你
需要一個指針的第一個元素。

617
00:25:59,620 --> 00:26:04,270
有線索，你只需要1
指向此線索的根。

618
00:26:04,270 --> 00:26:07,290
從那裡，你可以散列
你的路陷的越來越深

619
00:26:07,290 --> 00:26:10,460
以在結構中每一個其他節點。

620
00:26:10,460 --> 00:26:13,440
因此，簡單地用這個就可以
我們代表的結構。

621
00:26:13,440 --> 00:26:15,877
>> 現在Meanwhile--呵呵，問題。

622
00:26:15,877 --> 00:26:17,220
>> 聽眾：什麼是布爾字？

623
00:26:17,220 --> 00:26:20,490
>> DAVID馬蘭：BOOL字
只是這款C化身

624
00:26:20,490 --> 00:26:22,920
什麼，我描述
在這裡，在這個盒子

625
00:26:22,920 --> 00:26:26,000
我開始分裂各
數組的元素分為兩部分。

626
00:26:26,000 --> 00:26:27,600
之一是一個指向下一個節點。

627
00:26:27,600 --> 00:26:30,280
其它必須是
類似的複選框

628
00:26:30,280 --> 00:26:33,770
要說的是，有一個
字Daven說到此為止，

629
00:26:33,770 --> 00:26:35,610
因為我們不想要的，
此刻，戴夫。

630
00:26:35,610 --> 00:26:39,320
>> 即使戴夫將是一個
合法的一句話，他不是在特里

631
00:26:39,320 --> 00:26:39,830
還沒有。

632
00:26:39,830 --> 00:26:40,950
和D是不發一言。

633
00:26:40,950 --> 00:26:42,770
和D-A是不是一個單詞或一個名稱。

634
00:26:42,770 --> 00:26:45,020
因此，复選標記
表示只有當你

635
00:26:45,020 --> 00:26:48,190
打這個節點是
字符前面的路

636
00:26:48,190 --> 00:26:50,700
實際上，你已經插入一個字符串。

637
00:26:50,700 --> 00:26:53,660
這就是所有的布爾
那裡是做給我們。

638
00:26:53,660 --> 00:26:55,500
>> 在嘗試任何其他問題？

639
00:26:55,500 --> 00:26:56,215
是啊。

640
00:26:56,215 --> 00:26:58,035
>> 聽眾：什麼是重疊？

641
00:26:58,035 --> 00:26:59,945
如果你有一個戴夫和Daven？

642
00:26:59,945 --> 00:27:00,820
DAVID馬蘭：完美。

643
00:27:00,820 --> 00:27:02,580
如果你有一個戴夫和Daven？

644
00:27:02,580 --> 00:27:06,240
所以，如果我們插入，說一個綽號，
對於David-- Dave-- D-A-V-E？

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
其實，這是超級簡單。

647
00:27:08,700 --> 00:27:10,325
因此，我們只是要帶四個步驟。

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E。和我有什麼要
做一次，我打了四節點？

650
00:27:15,847 --> 00:27:16,680
只是去檢查。

651
00:27:16,680 --> 00:27:18,000
我們已經好到哪裡去。

652
00:27:18,000 --> 00:27:18,840
完成的。

653
00:27:18,840 --> 00:27:19,750
四個步驟。

654
00:27:19,750 --> 00:27:21,590
固定時間漸近。

655
00:27:21,590 --> 00:27:26,300
現在我們已經表明，無論戴夫
和Daven是在結構中的字符串。

656
00:27:26,300 --> 00:27:27,710
所以不存在問題。

657
00:27:27,710 --> 00:27:30,200
並注意存在
Daven的沒能

658
00:27:30,200 --> 00:27:34,750
需要更多的時間或更少
時間戴夫，反之亦然。

659
00:27:34,750 --> 00:27:36,000
>> 那麼還有什麼可以，現在我們怎麼辦？

660
00:27:36,000 --> 00:27:40,680
我們以前使用過這個隱喻
托盤代表什麼。

661
00:27:40,680 --> 00:27:43,380
但事實證明，一個
托盤堆實際上是

662
00:27:43,380 --> 00:27:47,187
示範的另一個抽象數據
類型 - 一個更高層次的數據結構

663
00:27:47,187 --> 00:27:49,770
這在最後的日子就是
像陣列或鏈接的列表

664
00:27:49,770 --> 00:27:50,970
什麼更現實。

665
00:27:50,970 --> 00:27:53,270
但它是一個更有趣
概念的概念。

666
00:27:53,270 --> 00:27:56,440
堆棧，這樣的
托盤在這裡馬瑟

667
00:27:56,440 --> 00:27:58,750
通常被稱為
只是that--堆棧。

668
00:27:58,750 --> 00:28:02,540
>> 並且在這種類型的數據結構
你有兩個operations--

669
00:28:02,540 --> 00:28:05,880
你有一個叫推
添加的東西到堆棧，

670
00:28:05,880 --> 00:28:08,320
就像把另一盤
備份在堆棧的頂部。

671
00:28:08,320 --> 00:28:11,350
然後彈出，這意味著你
把最上面的托盤掉。

672
00:28:11,350 --> 00:28:16,210
但是，什麼是關鍵關於堆棧是
它有這種奇怪的特點。

673
00:28:16,210 --> 00:28:19,560
由於食堂工作人員
重新排列的托盤為下一頓飯，

674
00:28:19,560 --> 00:28:21,380
這是怎麼回事是
真正了解學生如何

675
00:28:21,380 --> 00:28:22,856
這種數據結構進行交互？

676
00:28:22,856 --> 00:28:24,480
聽眾：他們將彈出一關。

677
00:28:24,480 --> 00:28:26,550
DAVID馬蘭：他們要去
彈出一關，希望上面。

678
00:28:26,550 --> 00:28:28,910
否則，它只是一種愚蠢
一路走到底。

679
00:28:28,910 --> 00:28:29,070
對不對？

680
00:28:29,070 --> 00:28:31,620
該數據結構並沒有真正允許
你至少要搶底盤

681
00:28:31,620 --> 00:28:32,520
很容易。

682
00:28:32,520 --> 00:28:35,040
因此，有這種奇怪的
屬性堆棧

683
00:28:35,040 --> 00:28:39,730
在最後一個項目是
將成為第1列。

684
00:28:39,730 --> 00:28:43,400
和計算機科學家稱之為
這LIFO--後進先出。

685
00:28:43,400 --> 00:28:45,540
它實際上確實有
有趣的應用程序。

686
00:28:45,540 --> 00:28:50,090
它並不一定那麼明顯一些
其他人，但它確實能是有用的，

687
00:28:50,090 --> 00:28:54,040
它確實能實現
在幾個不同的方式。

688
00:28:54,040 --> 00:28:58,550
>> 所以一個，實際上，讓
我不要潛入了。

689
00:28:58,550 --> 00:28:59,860
讓我們這樣做吧。

690
00:28:59,860 --> 00:29:03,700
讓我們來看看一個幾乎在
同樣的想法，但它是一個更公平一點。

691
00:29:03,700 --> 00:29:04,200
對不對？

692
00:29:04,200 --> 00:29:07,560
如果你是這些球迷的一個男孩或
女生真的喜歡蘋果產品

693
00:29:07,560 --> 00:29:10,130
而你在上午03點00分就醒了
排隊在一些商店

694
00:29:10,130 --> 00:29:14,150
獲得最新的iPhone，你
可能排隊這樣的。

695
00:29:14,150 --> 00:29:15,800
>> 現在隊列很刻意的名字命名。

696
00:29:15,800 --> 00:29:18,190
這是一條線，因為有
一些公平吧。

697
00:29:18,190 --> 00:29:18,690
對不對？

698
00:29:18,690 --> 00:29:21,690
種它將如果你吸
到了那裡在Apple Store第一

699
00:29:21,690 --> 00:29:25,700
但你有效的最底部
托盤是因為蘋果公司的員工，然後

700
00:29:25,700 --> 00:29:28,189
流行的最後一個人誰
實際上得到的線。

701
00:29:28,189 --> 00:29:31,230
因此，棧和隊列，即使
在功能上，他們是那種same--的

702
00:29:31,230 --> 00:29:33,105
它只是這個集合
資源，這是

703
00:29:33,105 --> 00:29:36,210
要發展和shrink--還有的
這種公平性方面吧，

704
00:29:36,210 --> 00:29:39,634
至少在現實世界中，
其中，操作你鍛煉

705
00:29:39,634 --> 00:29:40,800
是根本不同的。

706
00:29:40,800 --> 00:29:43,360
一個stack--隊列
rather--據說有

707
00:29:43,360 --> 00:29:45,320
兩個操作：N隊列和D隊列。

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
或者你可以給他們打電話
任何數目的東西。

710
00:29:48,090 --> 00:29:50,770
但是，你只是想捕捉
一個是增加的概念

711
00:29:50,770 --> 00:29:53,230
和一個最終被減去。

712
00:29:53,230 --> 00:29:58,840
>> 現在的發動機罩的下面，兩者的堆棧
和隊列可以實現怎麼樣？

713
00:29:58,840 --> 00:30:01,390
我們不會進入代碼
這是因為在較高的水平

714
00:30:01,390 --> 00:30:03,387
思想是那種比較明顯。

715
00:30:03,387 --> 00:30:04,470
我的意思是，人類該怎麼辦？

716
00:30:04,470 --> 00:30:07,030
如果我是第一人，在蘋果
存儲，這是前門，

717
00:30:07,030 --> 00:30:08,130
你知道，我要站在這裡。

718
00:30:08,130 --> 00:30:09,750
和旁邊的人的
站在這裡。

719
00:30:09,750 --> 00:30:11,500
和旁邊的人的
站在這裡。

720
00:30:11,500 --> 00:30:13,792
那麼，什麼數據結構
適合於一個隊列？

721
00:30:13,792 --> 00:30:14,542
>> 聽眾：隊列。

722
00:30:14,542 --> 00:30:15,667
DAVID馬蘭：嗯，一個隊列。

723
00:30:15,667 --> 00:30:16,390
當然可以。

724
00:30:16,390 --> 00:30:16,920
還有什麼？

725
00:30:16,920 --> 00:30:17,600
>> 聽眾：鍊錶。

726
00:30:17,600 --> 00:30:18,990
>> DAVID馬蘭：一個鏈接
列出你可以實現。

727
00:30:18,990 --> 00:30:22,500
和鍊錶是好的，因為這樣
而不是可任意長長

728
00:30:22,500 --> 00:30:24,880
具有一些固定的數
人在店裡。

729
00:30:24,880 --> 00:30:27,030
但也許一個固定的數
地方是合法的。

730
00:30:27,030 --> 00:30:30,350
因為如果他們只有像20
iPhone手機的第一天，也許

731
00:30:30,350 --> 00:30:33,930
它們只需要尺寸的陣列
20代表該隊列，這

732
00:30:33,930 --> 00:30:37,070
只是現在說一旦我們開始討論
關於這些較高級別的問題，

733
00:30:37,070 --> 00:30:38,890
你可以實現它
在任何數量的方式。

734
00:30:38,890 --> 00:30:42,030
還有的可能只是要
是一個折衷在空間和時間

735
00:30:42,030 --> 00:30:43,950
或只是在自己的代碼的複雜性。

736
00:30:43,950 --> 00:30:45,380
>> 那麼堆棧？

737
00:30:45,380 --> 00:30:48,190
好了，一個棧，我們已經看到太多
可能僅僅是這些托盤。

738
00:30:48,190 --> 00:30:50,007
而且你可以實現這個數組。

739
00:30:50,007 --> 00:30:53,090
但在某些時候，如果你使用一個數組，
什麼事情要發生在托盤

740
00:30:53,090 --> 00:30:54,173
你想放下？

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
行。

743
00:30:55,670 --> 00:30:57,490
你只打算
能走這麼高。

744
00:30:57,490 --> 00:31:00,156
我認為，在馬瑟他們
實際上凹進的開放。

745
00:31:00,156 --> 00:31:01,950
所以，事實上，它幾乎
像奧美使用

746
00:31:01,950 --> 00:31:03,783
固定大小的陣列，
因為你只能

747
00:31:03,783 --> 00:31:08,302
在開放符合這麼多托盤
牆壁向下跌破人們的膝蓋。

748
00:31:08,302 --> 00:31:10,010
因此，可能是
說是一個數組，

749
00:31:10,010 --> 00:31:14,300
但我們可以肯定的實施
更一般地用一個鍊錶。

750
00:31:14,300 --> 00:31:16,390
>> 那麼，關於另一個數據結構？

751
00:31:16,390 --> 00:31:18,760
我拉起另一個視覺這裡。

752
00:31:18,760 --> 00:31:24,710
像這個怎麼在這裡？

753
00:31:24,710 --> 00:31:28,920
為什麼會到沒有它是有用的
一些花哨的線索，這

754
00:31:28,920 --> 00:31:32,370
我們看到了這些非常寬的節點，
其中每一個是在一個數組中？

755
00:31:32,370 --> 00:31:35,740
但是，如果我們做更多的事情
簡單地說，就像一個老同學的家譜，

756
00:31:35,740 --> 00:31:38,110
每一個在這裡的節點
只是存儲號碼。

757
00:31:38,110 --> 00:31:42,180
而不是一個名稱或後裔
只是存儲了一些類似這樣的。

758
00:31:42,180 --> 00:31:45,250
>> 好了，我們行話使用
數據結構是既嘗試

759
00:31:45,250 --> 00:31:49,510
和樹木，其中一個線索，再次，是
只有一個的節點陣列，

760
00:31:49,510 --> 00:31:51,680
依然是你可能會
從小學使用

761
00:31:51,680 --> 00:31:53,860
當你犯了一個家庭
tree--葉和根

762
00:31:53,860 --> 00:31:57,250
樹和兒童
父母和兄弟姐妹物。

763
00:31:57,250 --> 00:32:03,670
我們可以實現一個樹，
例如，作為簡單的了。

764
00:32:03,670 --> 00:32:07,420
樹，如果它作為一個節點，一個
這些圓，其具有數，

765
00:32:07,420 --> 00:32:09,947
它不會有
1指針，而是兩個。

766
00:32:09,947 --> 00:32:11,780
而且只要你加入
第二個指針，

767
00:32:11,780 --> 00:32:13,905
實際上現在做排序
的二維數據

768
00:32:13,905 --> 00:32:14,780
結構在存儲器中。

769
00:32:14,780 --> 00:32:16,660
很像一個二維
數組，你可以

770
00:32:16,660 --> 00:32:18,904
有種類的二維
鍊錶但那些

771
00:32:18,904 --> 00:32:20,820
下面的模式
那裡沒有週期。

772
00:32:20,820 --> 00:32:24,487
這是一個真正的有一棵樹
了祖父母的方式在這裡再

773
00:32:24,487 --> 00:32:27,320
一些家長和孩子
孫子和曾孫。

774
00:32:27,320 --> 00:32:28,370
等等。

775
00:32:28,370 --> 00:32:32,390
>> 但是，什麼是真正的整潔對此也
只是逗你一些代碼，

776
00:32:32,390 --> 00:32:35,370
從調用遞歸
一段時間回來，因此

777
00:32:35,370 --> 00:32:38,220
你寫一個函數，該函數調用自身。

778
00:32:38,220 --> 00:32:41,140
這是一個美麗的機會
實施東西

779
00:32:41,140 --> 00:32:42,920
像遞歸，因為考慮這一點。

780
00:32:42,920 --> 00:32:43,860
>> 這是一個樹。

781
00:32:43,860 --> 00:32:48,040
我已經有點肛門如何
我把整數到街上。

782
00:32:48,040 --> 00:32:51,020
正因如此，它有一個特殊的
名稱 - 二叉查找樹。

783
00:32:51,020 --> 00:32:53,460
現在，我們已經聽說二進制
搜索，但你能

784
00:32:53,460 --> 00:32:55,180
從這個東西的名字倒著工作？

785
00:32:55,180 --> 00:32:59,280
什麼是我如何的格局
插入整數到這棵樹？

786
00:32:59,280 --> 00:33:00,696
它不是隨意的。

787
00:33:00,696 --> 00:33:01,570
這裡也有一些圖案。

788
00:33:01,570 --> 00:33:02,090
是啊。

789
00:33:02,090 --> 00:33:03,370
>> 聽眾：在左邊較小的。

790
00:33:03,370 --> 00:33:03,690
>> DAVID馬蘭：是啊。

791
00:33:03,690 --> 00:33:05,062
較小的是在左側。

792
00:33:05,062 --> 00:33:06,270
更大的是在右側。

793
00:33:06,270 --> 00:33:12,940
這樣，真正的語句是
家長大於它的左孩子，

794
00:33:12,940 --> 00:33:14,850
但比其右孩子少。

795
00:33:14,850 --> 00:33:17,750
而這僅僅是一個連
遞歸定義語言

796
00:33:17,750 --> 00:33:20,500
因為你可以應用
相同的邏輯的每一個節點

797
00:33:20,500 --> 00:33:23,080
而且它僅塔底
如果你出去，基本情況

798
00:33:23,080 --> 00:33:25,740
會的，當你打一個
葉子，可以這麼說，

799
00:33:25,740 --> 00:33:28,580
凡請假沒有孩子更進一步。

800
00:33:28,580 --> 00:33:30,614
>> 現在，你怎麼可能找到44號？

801
00:33:30,614 --> 00:33:32,280
你會從根開始，說，嗯。

802
00:33:32,280 --> 00:33:35,690
55不是44，我想去
正確的還是我想往左走？

803
00:33:35,690 --> 00:33:37,190
顯然，你想要去左邊。

804
00:33:37,190 --> 00:33:40,060
所以它就像手機
在二進制搜索本書實例

805
00:33:40,060 --> 00:33:41,099
更普遍。

806
00:33:41,099 --> 00:33:43,390
但我們實現它
現在多了幾分動態

807
00:33:43,390 --> 00:33:45,339
不是一個數組可以允許。

808
00:33:45,339 --> 00:33:48,130
而事實上，如果你想看看
在代碼中，第一眼肯定。

809
00:33:48,130 --> 00:33:49,671
它看起來像一大堆線。

810
00:33:49,671 --> 00:33:51,220
但它的美麗很簡單。

811
00:33:51,220 --> 00:33:54,490
如果你想實現一個功能
所謂的搜索，其目的在生活中

812
00:33:54,490 --> 00:33:57,290
是要搜索的一個值
像N，整數，

813
00:33:57,290 --> 00:34:01,756
和你在一pointer--正在通過
一個指向根的節點，

814
00:34:01,756 --> 00:34:04,380
那棵樹的相當，從
您可以訪問其他的一切，

815
00:34:04,380 --> 00:34:08,850
注意如何直截了當地
你可以實現的邏輯。

816
00:34:08,850 --> 00:34:10,880
如果樹是空，
顯然它不存在。

817
00:34:10,880 --> 00:34:11,880
讓我們只返回false。

818
00:34:11,880 --> 00:34:12,000
對不對？

819
00:34:12,000 --> 00:34:14,040
如果你把它什麼都沒有，
有什麼也沒有。

820
00:34:14,040 --> 00:34:17,900
>> 否則，如果n小於
樹箭頭N--現在箭頭N，

821
00:34:17,900 --> 00:34:20,670
記得我們推出超
短暫的一天，

822
00:34:20,670 --> 00:34:25,100
那只是意味著去參考
指針看看所謂的n個場。

823
00:34:25,100 --> 00:34:27,690
因此，這意味著去那裡
看看所謂的n個場。

824
00:34:27,690 --> 00:34:33,810
所以，如果N，你給出的值，小於
比在樹木整數的值，

825
00:34:33,810 --> 00:34:35,449
你想去哪兒去了？

826
00:34:35,449 --> 00:34:36,389
向左轉。

827
00:34:36,389 --> 00:34:37,780
>> 所以，注意遞歸。

828
00:34:37,780 --> 00:34:39,860
我returning--不正確的。

829
00:34:39,860 --> 00:34:40,989
不假。

830
00:34:40,989 --> 00:34:45,670
我回來什麼的答案
是通過調用自己，路過

831
00:34:45,670 --> 00:34:50,100
的n再次，這是多餘的，
但什麼是略有不同呢？

832
00:34:50,100 --> 00:34:51,989
我怎麼做的問題更小？

833
00:34:51,989 --> 00:34:54,920
我傳遞的第二個
參數，該樹的不根，

834
00:34:54,920 --> 00:34:59,616
但左子在這種情況下。

835
00:34:59,616 --> 00:35:00,990
所以我通過左邊的孩子。

836
00:35:00,990 --> 00:35:04,720
>> 同時，如果n是大於
該節點目前，我正在看，

837
00:35:04,720 --> 00:35:06,690
我搜索的右側。

838
00:35:06,690 --> 00:35:10,880
否則，如果樹不為空，而
如果元素不是向左

839
00:35:10,880 --> 00:35:13,240
它並不是正確的，
什麼是奇妙的情況？

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
實際上我們發現，節點
的問題，所以我們返回true。

842
00:35:18,440 --> 00:35:21,490
>> 所以我們剛剛觸及表面
現在一些數據結構。

843
00:35:21,490 --> 00:35:24,370
在問題設置5，你會
再進一步探討這些，

844
00:35:24,370 --> 00:35:27,250
你會得到你的設計
選擇如何去了解這一點。

845
00:35:27,250 --> 00:35:30,250
我想締結
僅僅30秒的預告片

846
00:35:30,250 --> 00:35:32,080
下週及以後有什麼在等待著。

847
00:35:32,080 --> 00:35:35,390
>> 正如我們begin--謝天謝地你可能
慢慢think--我們的轉型

848
00:35:35,390 --> 00:35:38,680
從C和下部的世界
層次的實現細節，

849
00:35:38,680 --> 00:35:42,090
一個世界裡，我們可以採取的
理所當然地認為別人終於

850
00:35:42,090 --> 00:35:44,010
實現了這些數據
結構對於我們來說，

851
00:35:44,010 --> 00:35:47,570
我們將開始了解
現實世界是指實施

852
00:35:47,570 --> 00:35:50,560
基於網絡的程序和
網站更普遍

853
00:35:50,560 --> 00:35:52,910
並且也很安全
我們只已經影響

854
00:35:52,910 --> 00:35:54,850
開始劃傷的表面上。

855
00:35:54,850 --> 00:35:57,320
這是什麼等待著我們
在未來的日子裡。

856
00:35:57,320 --> 00:36:00,480
>> [視頻回放]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>>  - 他想出了一個消息，
有協議的所有他自己的。

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
他來到了殘酷的世界
防火牆，路由器漠不關心，

861
00:36:30,894 --> 00:36:33,368
和危險遠遠比死還要痛苦。

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
他的速度快。

864
00:36:36,236 --> 00:36:37,980
他是強大的。

865
00:36:37,980 --> 00:36:42,830
他是TCP / IP，和他有你的地址。

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
“勇士的網。”

868
00:36:48,074 --> 00:36:49,660
[完視頻回放]

869
00:36:49,660 --> 00:36:50,910
DAVID馬蘭：下週即將。

870
00:36:50,910 --> 00:36:51,880
我們會看到你呢。

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[視頻回放]

873
00:36:56,060 --> 00:36:59,240
 - 和現在，“深度思考”
通過Daven法納姆。

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David總是開始
與講座，“好吧。”

876
00:37:05,820 --> 00:37:08,750
心動不如行動，“這裡的解決方案
本週的問題集“

877
00:37:08,750 --> 00:37:12,180
或者“我們給大家一個A？”

878
00:37:12,180 --> 00:37:13,380
[笑氣]

879
00:37:13,380 --> 00:37:15,530
[完視頻回放]