1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> 揚聲器1：對，所以我們又回來了。

3
00:00:13,120 --> 00:00:14,480
歡迎CS50。

4
00:00:14,480 --> 00:00:16,510
是星期七月底。

5
00:00:16,510 --> 00:00:20,200
所以記得，最後一次，我們開始
稍微複雜的看

6
00:00:20,200 --> 00:00:21,100
的數據結構。

7
00:00:21,100 --> 00:00:25,110
由於到現在為止，我們真的
在我們的處置是這樣的，一個數組。

8
00:00:25,110 --> 00:00:29,340
>> 但在此之前我們不會丟棄數組
所有有趣的，這的確

9
00:00:29,340 --> 00:00:33,570
實際上，是一些什麼
加上這個簡單的數據

10
00:00:33,570 --> 00:00:34,560
結構，從而有多遠？

11
00:00:34,560 --> 00:00:36,110
什麼是它擅長的？

12
00:00:36,110 --> 00:00:39,450
到目前為止，我們已經看到？

13
00:00:39,450 --> 00:00:42,540
你得到了什麼？

14
00:00:42,540 --> 00:00:44,028
什麼也沒有。

15
00:00:44,028 --> 00:00:45,020
>> 學生：[聽不清]。

16
00:00:45,020 --> 00:00:45,395
>> 揚聲器1：那是什麼？

17
00:00:45,395 --> 00:00:46,410
>> 學生：[聽不清]。

18
00:00:46,410 --> 00:00:47,000
>> 揚聲器1：固定尺寸。

19
00:00:47,000 --> 00:00:51,260
OK，那麼，為什麼是固定大小的好，雖然？

20
00:00:51,260 --> 00:00:53,180
>> 學生：[聽不清]。

21
00:00:53,180 --> 00:00:56,240
>> 揚聲器1：確定的，所以它的效率
這個意義上，你可以分配一個

22
00:00:56,240 --> 00:01:00,070
固定大小的空間，希望
恰恰是盡可能多

23
00:01:00,070 --> 00:01:01,180
空間，只要你想。

24
00:01:01,180 --> 00:01:02,720
所以這可能是一個絕對加分。

25
00:01:02,720 --> 00:01:06,530
>> 一個數組的另一側什麼？

26
00:01:06,530 --> 00:01:07,610
是嗎？

27
00:01:07,610 --> 00:01:08,750
>> 學生：[聽不清]。

28
00:01:08,750 --> 00:01:09,550
>> 揚聲器1：所有的 - 對不起？

29
00:01:09,550 --> 00:01:11,270
>> 學生：[聽不清]。

30
00:01:11,270 --> 00:01:13,620
>> 揚聲器1：在內存中的所有箱子
或給對方。

31
00:01:13,620 --> 00:01:15,220
這是有幫助的 - 為什麼？

32
00:01:15,220 --> 00:01:15,970
這是相當正確的。

33
00:01:15,970 --> 00:01:18,611
但如何才能利用這一真理嗎？

34
00:01:18,611 --> 00:01:21,500
>> 學生：[聽不清]。

35
00:01:21,500 --> 00:01:24,490
>> 揚聲器1：沒錯，我們可以跟踪
一切都只是知道

36
00:01:24,490 --> 00:01:28,560
一個地址，即地址
該內存塊的第一個字節。

37
00:01:28,560 --> 00:01:30,420
或字符串的情況下，
地址的第一個

38
00:01:30,420 --> 00:01:31,460
在該字符串中的字符。

39
00:01:31,460 --> 00:01:33,330
並從那裡，我們可以找到
結束的字符串。

40
00:01:33,330 --> 00:01:35,710
我們可以找到的第二個元素，
第三個元素，依此類推。

41
00:01:35,710 --> 00:01:38,740
>> 等花俏的手法描述，
特點是陣列給我們

42
00:01:38,740 --> 00:01:40,020
隨機訪問。

43
00:01:40,020 --> 00:01:44,330
只需使用方括號
符號和數字，你可以跳

44
00:01:44,330 --> 00:01:48,070
一個特定的數組中的元素
在固定時間內，大O

45
00:01:48,070 --> 00:01:49,810
之一，可以這麼說。

46
00:01:49,810 --> 00:01:51,080
>> 但也有一些缺點。

47
00:01:51,080 --> 00:01:53,110
數組不是很容易做嗎？

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
什麼不擅長什麼？

50
00:01:57,170 --> 00:01:58,810
>> 學生：[聽不清]。

51
00:01:58,810 --> 00:01:59,860
>> 揚聲器1：那是什麼？

52
00:01:59,860 --> 00:02:00,530
>> 學生：[聽不清]。

53
00:02:00,530 --> 00:02:01,460
>> 揚聲器1：在規模擴大。

54
00:02:01,460 --> 00:02:04,800
所以的缺點數組是
正好相反的是什麼

55
00:02:04,800 --> 00:02:05,540
一面是。

56
00:02:05,540 --> 00:02:07,610
所以，一個缺點是
，這是一個固定大小的。

57
00:02:07,610 --> 00:02:09,400
所以你不能真正成長。

58
00:02:09,400 --> 00:02:13,510
您可以重新分配更大的大塊
內存中，然後將舊的元素

59
00:02:13,510 --> 00:02:14,460
到新的數組。

60
00:02:14,460 --> 00:02:18,060
然後釋放舊的陣列，
例如，通過用malloc或類似的

61
00:02:18,060 --> 00:02:21,180
函數調用realloc的，
重新分配內存。

62
00:02:21,180 --> 00:02:25,490
>> REALLOC，順便說一句，試圖給你
內存陣列旁邊

63
00:02:25,490 --> 00:02:26,610
你已經有了。

64
00:02:26,610 --> 00:02:28,740
但它也可能移動的東西
周圍完全。

65
00:02:28,740 --> 00:02:30,710
但總之，這是昂貴的，對不對？

66
00:02:30,710 --> 00:02:33,440
因為如果你有一大塊的內存
這個長度，但是你真的想要一個

67
00:02:33,440 --> 00:02:36,710
這種規模，你要保留
你有原創要素，

68
00:02:36,710 --> 00:02:40,510
大致的線性時間複製過程
需要發生

69
00:02:40,510 --> 00:02:41,900
新的舊的陣列。

70
00:02:41,900 --> 00:02:44,630
和現實要求的經營
系統一而再，再而

71
00:02:44,630 --> 00:02:48,340
再大的內存塊，就可以開始
花費你一些時間。

72
00:02:48,340 --> 00:02:52,250
因此，它既是祝福和詛咒
偽裝，但事實上，這些陣列

73
00:02:52,250 --> 00:02:53,860
固定大小。

74
00:02:53,860 --> 00:02:56,790
但是，如果我們引入，而不是東西
這樣，我們稱為聯

75
00:02:56,790 --> 00:03:00,580
列表中，我們得到了一些積極和
幾個缺點在這裡。

76
00:03:00,580 --> 00:03:05,780
>> 所以一個鍊錶是一個簡單的數據
結構由C結構

77
00:03:05,780 --> 00:03:09,850
情況下，當一個struct，召回，只是
用容器的一個或多個特定

78
00:03:09,850 --> 00:03:11,100
類型的變量。

79
00:03:11,100 --> 00:03:16,110
在這種情況下，什麼數據類型
似乎是裡面的結構，

80
00:03:16,110 --> 00:03:17,600
我們最後一次稱為一個節點？

81
00:03:17,600 --> 00:03:19,380
這些矩形中的每一個是一個節點。

82
00:03:19,380 --> 00:03:22,660
並且每個小矩形
裡面它是一種數據類型。

83
00:03:22,660 --> 00:03:25,300
什麼樣的類型，我們說
他們在星期一？

84
00:03:25,300 --> 00:03:26,478
是嗎？

85
00:03:26,478 --> 00:03:27,870
>> 學生：[聽不清]。

86
00:03:27,870 --> 00:03:30,721
>> 揚聲器1：變量和指針，或
更具體地說，一個int，對n，

87
00:03:30,721 --> 00:03:32,180
和指針底部。

88
00:03:32,180 --> 00:03:35,360
兩個那些碰巧是32位，在
至少在電腦上像這樣CS50

89
00:03:35,360 --> 00:03:37,980
電器，所以他們
得出同樣的大小。

90
00:03:37,980 --> 00:03:42,260
>> 那麼，什麼是使用指針
但顯然？

91
00:03:42,260 --> 00:03:47,690
為什麼現在這個箭頭數組時
這麼漂亮，乾淨和簡單的？

92
00:03:47,690 --> 00:03:50,460
指針是什麼做的
我們在這些節點中的每個節點？

93
00:03:50,460 --> 00:03:52,160
>> 學生：[聽不清]。

94
00:03:52,160 --> 00:03:52,465
>> 揚聲器1：沒錯。

95
00:03:52,465 --> 00:03:54,120
它告訴你在哪裡
下一個是。

96
00:03:54,120 --> 00:03:57,350
所以我使用的比喻
使用一個線程來排序

97
00:03:57,350 --> 00:03:59,180
線程這些節點連接在一起。

98
00:03:59,180 --> 00:04:01,760
這正是我們正在做的
指針，因為每個這些

99
00:04:01,760 --> 00:04:06,360
內存塊可能會或可能不會
連續回背靠背

100
00:04:06,360 --> 00:04:09,500
內側RAM因為每次
調用malloc說，給我足夠的

101
00:04:09,500 --> 00:04:12,510
字節一個新的節點，它可能
在這裡，或者它可能是在這裡。

102
00:04:12,510 --> 00:04:13,120
這可能是在這裡。

103
00:04:13,120 --> 00:04:13,730
這可能是在這裡。

104
00:04:13,730 --> 00:04:14,640
你只是不知道。

105
00:04:14,640 --> 00:04:17,880
>> 但是，使用指針的地址
這些節點，你可以拼接

106
00:04:17,880 --> 00:04:22,370
一起在視覺上看起來的方式
即使這些東西都像一個列表

107
00:04:22,370 --> 00:04:26,770
傳遍你的一個或
你的兩個或4 GB的RAM

108
00:04:26,770 --> 00:04:28,760
自己的電腦裡面。

109
00:04:28,760 --> 00:04:33,230
>> 所以下行，那麼，
鍊錶是什麼？

110
00:04:33,230 --> 00:04:34,670
什麼是我們的價格
顯然支付？

111
00:04:34,670 --> 00:04:36,010
>> 學生：[聽不清]。

112
00:04:36,010 --> 00:04:36,920
>> 揚聲器1：更多的空間，對不對？

113
00:04:36,920 --> 00:04:39,340
在這種情況下，我們已經增加了一倍
空間，因為我們已經走了

114
00:04:39,340 --> 00:04:43,500
從32位的每個節點，每個
INT，所以現在64位的，因為我們有

115
00:04:43,500 --> 00:04:45,050
保持周圍的指針。

116
00:04:45,050 --> 00:04:48,860
你得到更多的效率，如果你的結構
是大於這個簡單的事情。

117
00:04:48,860 --> 00:04:52,020
如果你確實有一個學生裡面
這是一對夫婦的字符串

118
00:04:52,020 --> 00:04:55,430
名稱和房子，也許是一個ID號，
也許其他一些領域完全。

119
00:04:55,430 --> 00:04:59,000
>> 所以，如果你有一個足夠大的結構，
那麼也許成本的指針

120
00:04:59,000 --> 00:05:00,010
沒有什麼大不了的。

121
00:05:00,010 --> 00:05:03,570
這是一個位在一個角落的情況下
我們存儲這樣一個簡單的原始

122
00:05:03,570 --> 00:05:04,760
內的鏈接的列表。

123
00:05:04,760 --> 00:05:05,790
但問題是相同的。

124
00:05:05,790 --> 00:05:08,230
你肯定花更多
內存，但你得到

125
00:05:08,230 --> 00:05:08,990
的靈活性。

126
00:05:08,990 --> 00:05:12,280
因為現在如果我想添加一個元素
在此列表的開頭，

127
00:05:12,280 --> 00:05:14,340
我必須分配一個新的節點。

128
00:05:14,340 --> 00:05:17,180
我有只更新那些
不知何故只是移動箭頭

129
00:05:17,180 --> 00:05:17,980
周圍一些指針。

130
00:05:17,980 --> 00:05:20,580
>> 如果我要插入到的東西
中間的列表，我不必

131
00:05:20,580 --> 00:05:24,410
拋開眾人推像我們一樣
週過去與我們的志願者

132
00:05:24,410 --> 00:05:25,700
表示一個數組。

133
00:05:25,700 --> 00:05:29,470
我可以只分配一個新的節點，
然後就點中的箭頭

134
00:05:29,470 --> 00:05:32,290
不同的方向，因為它不
必須保持以實際的

135
00:05:32,290 --> 00:05:35,670
內存一個真正像我畫的線
這裡的屏幕上。

136
00:05:35,670 --> 00:05:38,400
>> 最後，如果你想插入
在列表末尾的東西，這是

137
00:05:38,400 --> 00:05:39,210
更容易。

138
00:05:39,210 --> 00:05:43,320
這是任意符號，
但34的指針，以此來猜測。

139
00:05:43,320 --> 00:05:46,710
其指針的價值是什麼
可能拉有點像一個老

140
00:05:46,710 --> 00:05:47,700
有學校天線？

141
00:05:47,700 --> 00:05:48,920
>> 學生：[聽不清]。

142
00:05:48,920 --> 00:05:49,900
>> 揚聲器1：這可能是空的。

143
00:05:49,900 --> 00:05:52,710
事實上，這是一個作者的
表示空。

144
00:05:52,710 --> 00:05:56,310
它是空的，因為你絕對
需要知道在哪裡結束的聯

145
00:05:56,310 --> 00:06:00,050
名單，免得你保持以下
後，並按照這些箭頭

146
00:06:00,050 --> 00:06:01,170
一些垃圾值。

147
00:06:01,170 --> 00:06:06,230
因此，空表示沒有任何
更多的節點號為34的右側，

148
00:06:06,230 --> 00:06:07,200
在這種情況下。

149
00:06:07,200 --> 00:06:10,270
>> 因此，我們提出，我們可以實現
這個節點的代碼。

150
00:06:10,270 --> 00:06:12,130
我們已經看到這種
之前的語法。

151
00:06:12,130 --> 00:06:15,090
用typedef定義一個新類型
我們，為我們提供了這樣的代名詞

152
00:06:15,090 --> 00:06:17,100
對於char *字符串。

153
00:06:17,100 --> 00:06:21,030
在這種情況下，它給我們
速記符號，使結構節點

154
00:06:21,030 --> 00:06:24,010
而是可以被寫成
節點，它是乾淨了很多。

155
00:06:24,010 --> 00:06:25,360
這是少了很多冗長。

156
00:06:25,360 --> 00:06:30,080
>> 節點內顯然是一個int
稱為n和結構節點*

157
00:06:30,080 --> 00:06:34,670
這意味著正是我們想要的
箭頭的意思是，到另一個指針

158
00:06:34,670 --> 00:06:36,940
完全相同的數據類型的節點。

159
00:06:36,940 --> 00:06:40,300
我建議，我們可以實現一個
搜索這樣的功能，這在

160
00:06:40,300 --> 00:06:41,890
乍一看似乎
有點複雜。

161
00:06:41,890 --> 00:06:43,330
但是，讓我們來看看它在上下文中。

162
00:06:43,330 --> 00:06:45,480
>> 讓我去到這裡的家電。

163
00:06:45,480 --> 00:06:48,460
讓我打開一個名為
列表零點H。

164
00:06:48,460 --> 00:06:53,950
只包含的定義，我們
只是剛才也看到了這些數據

165
00:06:53,950 --> 00:06:55,390
類型稱為一個節點。

166
00:06:55,390 --> 00:06:57,350
因此，我們已經把到一個點h文件。

167
00:06:57,350 --> 00:07:01,430
>> 而順便說一句，儘管這
程序，你將要看到的是

168
00:07:01,430 --> 00:07:05,410
不是所有的，複雜的，它的的確確
當編寫一個程序來公約

169
00:07:05,410 --> 00:07:10,270
數據類型一樣，把東西拉
有時，在裡面你的常量

170
00:07:10,270 --> 00:07:13,210
頭文件不一定
你的C文件，當然，當你的

171
00:07:13,210 --> 00:07:17,370
方案變得越來越大，從而使
你知道到哪裡尋找既為

172
00:07:17,370 --> 00:07:20,840
在某些情況下，文檔或
基本這個樣子，

173
00:07:20,840 --> 00:07:22,360
某種類型的定義。

174
00:07:22,360 --> 00:07:25,680
>> 如果我現在打開列表零點
C，注意的幾件事情。

175
00:07:25,680 --> 00:07:29,090
它包括了幾個頭文件，最
我們之前見過。

176
00:07:29,090 --> 00:07:31,980
它包括其自己的頭文件。

177
00:07:31,980 --> 00:07:35,200
>> 順便說一句，這就是為什麼雙
報價。在這裡，相對於角度

178
00:07:35,200 --> 00:07:38,340
括號就行了，
我已經強調了那裡？

179
00:07:38,340 --> 00:07:39,180
>> 學生：[聽不清]。

180
00:07:39,180 --> 00:07:40,460
>> 揚聲器1：是啊，所以它是一個本地文件。

181
00:07:40,460 --> 00:07:44,300
所以，如果你自己在這裡的本地文件
第15行，例如，您可以使用

182
00:07:44,300 --> 00:07:46,570
雙引號，而不是
的尖括號。

183
00:07:46,570 --> 00:07:48,270
>> 現在，這是一種有趣的。

184
00:07:48,270 --> 00:07:51,830
注意，我已經宣布為全球
這個程序的第18行的變量

185
00:07:51,830 --> 00:07:55,910
被稱為第一想法是這是
將是一個指針指向第一個

186
00:07:55,910 --> 00:07:59,190
在我的鍊錶節點，並且我
初始化為null，因為我

187
00:07:59,190 --> 00:08:02,310
沒有分配任何實際
節點只是還沒有。

188
00:08:02,310 --> 00:08:07,570
>> 因此，這代表1973年，我們
剛才也看到了圖片作為

189
00:08:07,570 --> 00:08:10,090
該指針遠
左手側。

190
00:08:10,090 --> 00:08:12,260
所以現在，該指針
不會有一個箭頭。

191
00:08:12,260 --> 00:08:14,590
相反，它僅僅是空的。

192
00:08:14,590 --> 00:08:17,880
但它代表的會是怎樣的
第一個實際的地址

193
00:08:17,880 --> 00:08:19,480
在此列表中的節點。

194
00:08:19,480 --> 00:08:22,120
所以，我已經實現了它是一個全球
因為，你會看到，這一切

195
00:08:22,120 --> 00:08:25,310
計劃並落實在生活中是
一個鍊錶為我。

196
00:08:25,310 --> 00:08:27,050
>> 現在我已經得到了一些原型。

197
00:08:27,050 --> 00:08:31,190
我決定實現的功能，如
缺失，插入，搜索和

198
00:08:31,190 --> 00:08:31,740
穿越 - 

199
00:08:31,740 --> 00:08:35,210
最後只是徒步穿越
列表，打印出它的元素。

200
00:08:35,210 --> 00:08:36,750
而現在，這裡是我的主程序。

201
00:08:36,750 --> 00:08:39,890
並且我們不會花太多時間
這些，因為這是那種，希望

202
00:08:39,890 --> 00:08:41,780
現在的舊帽子。

203
00:08:41,780 --> 00:08:45,370
>> 我要做到以下幾點：
而用戶合作。

204
00:08:45,370 --> 00:08:47,300
所以，我要打印
出此菜單。

205
00:08:47,300 --> 00:08:49,420
我格式化它作為
乾淨，盡我所能。

206
00:08:49,420 --> 00:08:52,240
如果用戶在一個類型，即表示
他們要刪除的東西。

207
00:08:52,240 --> 00:08:54,560
如果用戶有兩種類型，即表示
他們要插入的東西。

208
00:08:54,560 --> 00:08:55,930
等等。

209
00:08:55,930 --> 00:08:58,270
我要提示
然後命令。

210
00:08:58,270 --> 00:08:59,300
然後我要使用調用getInt。

211
00:08:59,300 --> 00:09:02,790
>> 所以這是一個非常簡單的menuing
界面，您只需要輸入

212
00:09:02,790 --> 00:09:05,270
一些映射到一個
這些命令。

213
00:09:05,270 --> 00:09:08,730
現在我有一個漂亮乾淨的開關
語句要切換

214
00:09:08,730 --> 00:09:10,090
無論用戶輸入。

215
00:09:10,090 --> 00:09:12,180
而且，如果他們輸入了一個，我會
調用delete和突破。

216
00:09:12,180 --> 00:09:14,380
鍵入兩個我
調用插入和突破。

217
00:09:14,380 --> 00:09:16,490
>> 現在請注意，我已經把每
這些在同一行上。

218
00:09:16,490 --> 00:09:18,360
這是一種風格上的決定。

219
00:09:18,360 --> 00:09:20,210
通常情況下，我們已經看到的東西
像這樣。

220
00:09:20,210 --> 00:09:23,260
但我剛剛決定，坦率地說，我的程序
看上去更具可讀性，因為

221
00:09:23,260 --> 00:09:25,980
它只有四個案件
像這樣只列出。

222
00:09:25,980 --> 00:09:28,360
完全合法使用樣式。

223
00:09:28,360 --> 00:09:31,480
我要做到這一點，只要
用戶沒有輸入零，這是我

224
00:09:31,480 --> 00:09:33,910
決定將意味著他們想戒菸。

225
00:09:33,910 --> 00:09:36,630
>> 所以，現在發現我什麼
要在這裡做。

226
00:09:36,630 --> 00:09:38,650
我要去顯然釋放的清單。

227
00:09:38,650 --> 00:09:40,230
但在短短的時刻。

228
00:09:40,230 --> 00:09:41,640
首先，讓我們來運行這個程序。

229
00:09:41,640 --> 00:09:45,250
因此，讓我一個更大的終端
窗口，點斜線列表0。

230
00:09:45,250 --> 00:09:49,510
我要繼續前進並插入
50這樣的數字，現在打字兩

231
00:09:49,510 --> 00:09:51,590
你會看到列表中現在是50。

232
00:09:51,590 --> 00:09:53,380
我的文字只是滾動了一下。

233
00:09:53,380 --> 00:09:55,940
所以，現在看到列表中包含
數字50。

234
00:09:55,940 --> 00:09:58,220
>> 讓我們做另一個採取兩個插入。

235
00:09:58,220 --> 00:10:01,630
讓我們像一個輸入的數量。

236
00:10:01,630 --> 00:10:03,940
列表現在，接著為50。

237
00:10:03,940 --> 00:10:06,020
所以這僅僅是一個文字表述
列表。

238
00:10:06,020 --> 00:10:10,550
我們插入一個像
數字42，這是有希望的

239
00:10:10,550 --> 00:10:14,620
要結束了，因為在中間
特別是各種程序

240
00:10:14,620 --> 00:10:16,320
它插入他們的元素。

241
00:10:16,320 --> 00:10:17,220
因此，我們有它。

242
00:10:17,220 --> 00:10:20,730
超級簡單的程序，可以
絕對使用一個數組，但我

243
00:10:20,730 --> 00:10:23,280
碰巧使用一個鍊錶
就這樣我就可以動態地

244
00:10:23,280 --> 00:10:24,610
增長和收縮。

245
00:10:24,610 --> 00:10:28,470
>> 因此，讓我們來看看搜索，如果我
運行命令三，我想搜索

246
00:10:28,470 --> 00:10:31,040
，也就是說，43號。

247
00:10:31,040 --> 00:10:34,190
顯然並沒有什麼發現，
因為我回來沒有反應。

248
00:10:34,190 --> 00:10:35,010
因此，讓我們再次做到這一點。

249
00:10:35,010 --> 00:10:35,690
搜索。

250
00:10:35,690 --> 00:10:39,520
50，或者更確切地說，搜索的搜索
42，有一個很好的

251
00:10:39,520 --> 00:10:40,850
有點微妙的含義。

252
00:10:40,850 --> 00:10:42,610
而且我發現有生命的意義。

253
00:10:42,610 --> 00:10:44,990
42，如果你不知道
參考谷歌。

254
00:10:44,990 --> 00:10:45,350
好的。

255
00:10:45,350 --> 00:10:47,130
那麼是什麼為我做這個程序？

256
00:10:47,130 --> 00:10:50,660
它只是讓我插入從而
到目前為止，搜索元素。

257
00:10:50,660 --> 00:10:53,650
>> 讓我們快進，那麼，
我們瞟了一眼那個函數

258
00:10:53,650 --> 00:10:55,360
週一傳情。

259
00:10:55,360 --> 00:10:59,620
所以，我要求這個功能，搜索
第一列表中的一個元素

260
00:10:59,620 --> 00:11:03,830
一，提示用戶，然後調用
調用getInt得到一個實際的int

261
00:11:03,830 --> 00:11:05,060
要搜索。

262
00:11:05,060 --> 00:11:06,460
>> 然後注意到這一點。

263
00:11:06,460 --> 00:11:10,690
我要創建一個臨時變量
在第188行稱為指針 - 

264
00:11:10,690 --> 00:11:11,270
PTR  - 

265
00:11:11,270 --> 00:11:12,440
可以把它叫做什麼。

266
00:11:12,440 --> 00:11:16,140
這是一個節點的指針
因為我說有節點*。

267
00:11:16,140 --> 00:11:19,900
我初始化它等於
首先，讓我實際上是我的

268
00:11:19,900 --> 00:11:22,860
手指，可以這麼說，就非常
列表中的第一個元素。

269
00:11:22,860 --> 00:11:27,460
所以，如果我的右手是PTR我
指向同一件事，第一

270
00:11:27,460 --> 00:11:28,670
是否對準。

271
00:11:28,670 --> 00:11:31,430
>> 現在，我們回到代碼中，
接下來會發生什麼 - 

272
00:11:31,430 --> 00:11:35,070
迭代時，這是一個共同的範式
像結構

273
00:11:35,070 --> 00:11:35,970
鍊錶。

274
00:11:35,970 --> 00:11:40,410
我要做到以下幾點，同時
指針不等於空，因此，

275
00:11:40,410 --> 00:11:47,530
我的手指指著一些空
值，如果指針箭頭n等於N。

276
00:11:47,530 --> 00:11:52,290
我們首先會注意到，n是什麼
用戶輸入每GetInts這裡打電話。

277
00:11:52,290 --> 00:11:54,280
>> 和指針箭頭N意味著什麼呢？

278
00:11:54,280 --> 00:11:59,020
好吧，如果我們再回到這裡的圖片，
如果我有一個手指指著

279
00:11:59,020 --> 00:12:02,960
九，即第一個節點
箭頭基本上意味著去那

280
00:12:02,960 --> 00:12:08,860
節點，並搶在位置n的值，
在這種情況下，數據字段稱為N。

281
00:12:08,860 --> 00:12:14,120
>> 順便說一句 - 我們看到一對夫婦
星期前，當有人問 - 

282
00:12:14,120 --> 00:12:18,840
這個語法是新的，但它不
給我們的權力，我們

283
00:12:18,840 --> 00:12:20,040
沒有已經有了。

284
00:12:20,040 --> 00:12:25,325
這句話是什麼相當於使用
點符號和明星夫婦

285
00:12:25,325 --> 00:12:29,490
星期前，當我們剝開
這一層有點過早？

286
00:12:29,490 --> 00:12:31,780
>> 學生：[聽不清]。

287
00:12:31,780 --> 00:12:38,880
>> 揚聲器1：沒錯，這是明星，
那麼它是星點N，

288
00:12:38,880 --> 00:12:41,930
括號在這裡，它看起來，
坦率地說，我想了很多

289
00:12:41,930 --> 00:12:43,320
更神秘的閱讀。

290
00:12:43,320 --> 00:12:46,270
但星級指針，一如既往
手段去那裡。

291
00:12:46,270 --> 00:12:49,090
而一旦你在那裡，什麼樣的數據
現場你要訪問嗎？

292
00:12:49,090 --> 00:12:52,730
那麼你用點符號訪問
一個結構的數據字段，我

293
00:12:52,730 --> 00:12:54,140
特別希望N。

294
00:12:54,140 --> 00:12:56,240
>> 坦率地說，我認為這
只是很難閱讀。

295
00:12:56,240 --> 00:12:58,080
這是很難記得在哪裡
做括號走，

296
00:12:58,080 --> 00:12:59,030
明星和一切。

297
00:12:59,030 --> 00:13:02,150
因此，世界上採取了一些句法
糖，可以這麼說。

298
00:13:02,150 --> 00:13:04,740
只是一個性感的說法，
這是等價的，並且

299
00:13:04,740 --> 00:13:05,970
或許更直觀。

300
00:13:05,970 --> 00:13:09,600
如果指針確實是一個指針，
箭頭符號手段去那裡找

301
00:13:09,600 --> 00:13:11,890
在這種情況下，該領域稱為N。

302
00:13:11,890 --> 00:13:13,660
>> 所以，如果我找到它，發現我做什麼。

303
00:13:13,660 --> 00:13:17,430
我只是打印出來，我發現我％，
堵在這個int值。

304
00:13:17,430 --> 00:13:20,730
我叫睡一秒鐘只是一種
暫停在屏幕上的東西

305
00:13:20,730 --> 00:13:22,900
給用戶一個第二吸收
剛剛發生了什麼。

306
00:13:22,900 --> 00:13:24,290
然後我就打破。

307
00:13:24,290 --> 00:13:26,330
否則，我該怎麼辦？

308
00:13:26,330 --> 00:13:30,960
我更新指針等於
指針旁邊的箭頭。

309
00:13:30,960 --> 00:13:35,840
>> 所以，僅僅是明確的，這意味著去
在那裡，我的老學校的符號。

310
00:13:35,840 --> 00:13:39,580
因此，這只是意味著去任何
你指出，這在很

311
00:13:39,580 --> 00:13:43,660
第一種情況是，我指著
結構九。

312
00:13:43,660 --> 00:13:44,510
所以，我去那裡。

313
00:13:44,510 --> 00:13:47,880
然後點符號表示，
在未來獲得價值。

314
00:13:47,880 --> 00:13:50,470
>> 但該值，即使它的繪製
作為窄，僅僅是一個數字。

315
00:13:50,470 --> 00:13:51,720
這是一個數字地址。

316
00:13:51,720 --> 00:13:55,670
所以這一行代碼，無論
這樣寫，更神秘

317
00:13:55,670 --> 00:14:00,190
的方式，還是這個樣子，稍微
直觀的方式，只是意味著移動我的手

318
00:14:00,190 --> 00:14:03,460
從第一個節點到下一個，
然後下一個，然後

319
00:14:03,460 --> 00:14:05,320
下一個，等等。

320
00:14:05,320 --> 00:14:09,920
>> 因此，我們不會糾纏於其他
插入和刪除的實現

321
00:14:09,920 --> 00:14:14,030
和遍歷，前兩個
這是相當複雜的。

322
00:14:14,030 --> 00:14:17,010
而且，我認為這是很容易得到
做口頭丟失。

323
00:14:17,010 --> 00:14:19,890
但我們可以在這裡做什麼
嘗試，以確定如何

324
00:14:19,890 --> 00:14:21,640
最好做視覺。

325
00:14:21,640 --> 00:14:24,800
因為我會提出，如果我們
要插入元素

326
00:14:24,800 --> 00:14:26,680
現有的名單，其中
有五個要素 - 

327
00:14:26,680 --> 00:14:29,530
9，17，22，26，33  - 

328
00:14:29,530 --> 00:14:33,300
如果我要實現這
代碼，我需要考慮如何去

329
00:14:33,300 --> 00:14:34,160
這樣做。

330
00:14:34,160 --> 00:14:37,720
>> 我建議採取小步
據此，在這種情況下，我的意思是什麼

331
00:14:37,720 --> 00:14:41,090
可能出現的情況，我們
可能遇到的一般？

332
00:14:41,090 --> 00:14:44,120
當執行插入一個鏈接
名單，這恰好是一個

333
00:14:44,120 --> 00:14:46,090
具體例的大小為5。

334
00:14:46,090 --> 00:14:50,420
好吧，如果你要插入一個數字，
喜歡說的頭號

335
00:14:50,420 --> 00:14:53,380
保持排序順序，其中
顯然做一個需要數

336
00:14:53,380 --> 00:14:55,686
走在這個具體的例子嗎？

337
00:14:55,686 --> 00:14:56,840
開始時一樣。

338
00:14:56,840 --> 00:15:00,030
>> 但有趣的是
如果你要插入到這個

339
00:15:00,030 --> 00:15:04,100
列表中，需要什麼特殊的指針
顯然要更新？

340
00:15:04,100 --> 00:15:04,610
第一。

341
00:15:04,610 --> 00:15:07,830
所以，我認為，這是第一種情況
我們可能要考慮，

342
00:15:07,830 --> 00:15:11,140
方案涉及於
在列表的開頭。

343
00:15:11,140 --> 00:15:15,400
>> 讓我們為這事也許容易，甚至
更簡單的情況下，相對來說。

344
00:15:15,400 --> 00:15:18,110
假設我要插入
35號排序。

345
00:15:18,110 --> 00:15:20,600
這顯然屬於那邊。

346
00:15:20,600 --> 00:15:25,320
那麼，什麼指針，顯然是要
在這種情況下必須進行更新？

347
00:15:25,320 --> 00:15:30,060
34的指針變得不空
但該結構的地址

348
00:15:30,060 --> 00:15:31,800
含有數字35。

349
00:15:31,800 --> 00:15:32,750
因此，案例二。

350
00:15:32,750 --> 00:15:36,190
所以，我已經是量化排序
在這裡我必須做多少工作。

351
00:15:36,190 --> 00:15:39,880
>> 最後，明顯的中間的情況下是
的確，如果我在中間，要

352
00:15:39,880 --> 00:15:45,870
插入像說23，雲
在23和26之間，但

353
00:15:45,870 --> 00:15:48,680
現在事情變得有點更
因為涉及什麼

354
00:15:48,680 --> 00:15:52,800
指針需要改變嗎？

355
00:15:52,800 --> 00:15:56,680
因此，22顯然需要改變
因為他不能點到26了。

356
00:15:56,680 --> 00:16:00,320
他需要，以指向新節點
我將不得不通過調用分配

357
00:16:00,320 --> 00:16:01,770
malloc或一些等價。

358
00:16:01,770 --> 00:16:05,990
>> 但是，我也需要新的節點，23
在這種情況下，有它的指針

359
00:16:05,990 --> 00:16:07,870
指向誰？

360
00:16:07,870 --> 00:16:08,560
26。

361
00:16:08,560 --> 00:16:10,380
而且也將是一個
這裡的操作順序。

362
00:16:10,380 --> 00:16:13,410
因為如果我這樣做愚蠢的是，我和
實例的開始處開始

363
00:16:13,410 --> 00:16:16,040
列表中，我的目標是要插入23。

364
00:16:16,040 --> 00:16:18,610
檢查，它屬於
在這裡，近九？

365
00:16:18,610 --> 00:16:18,950
號

366
00:16:18,950 --> 00:16:20,670
它屬於這裡，未來17？

367
00:16:20,670 --> 00:16:20,940
號

368
00:16:20,940 --> 00:16:22,530
是否屬於這裡旁邊22？

369
00:16:22,530 --> 00:16:23,300
是。

370
00:16:23,300 --> 00:16:26,400
>> 現在，如果我在這裡很愚蠢的，而不是
通過思考，我可能

371
00:16:26,400 --> 00:16:28,320
分配我的新節點上為23。

372
00:16:28,320 --> 00:16:32,080
我可能會更新指針
節點稱為22，指著

373
00:16:32,080 --> 00:16:33,080
在新的節點。

374
00:16:33,080 --> 00:16:36,140
然後我有什麼更新
新節點的指針？

375
00:16:36,140 --> 00:16:38,120
>> 學生：[聽不清]。

376
00:16:38,120 --> 00:16:38,385
>> 揚聲器1：沒錯。

377
00:16:38,385 --> 00:16:39,710
指著26。

378
00:16:39,710 --> 00:16:45,590
但是，該死，如果我沒有已經更新
22的指針指向這個傢伙，

379
00:16:45,590 --> 00:16:48,260
現在我有孤兒，其餘
列表，可以這麼說。

380
00:16:48,260 --> 00:16:52,140
所以，這裡的操作順序
會是重要的。

381
00:16:52,140 --> 00:16:55,100
>> 要做到這一點，我能偷，
說，六個月志願者。

382
00:16:55,100 --> 00:16:57,650
讓我們來看看，如果我們不能做到這一點
視覺上，而不是代碼明智。

383
00:16:57,650 --> 00:16:59,330
我們有一些可愛的壓力
今天為你的球。

384
00:16:59,330 --> 00:17:02,510
OK，約一，兩個，在
回 - 到底有沒有。

385
00:17:02,510 --> 00:17:04,530
三，四，雙方你
傢伙到底。

386
00:17:04,530 --> 00:17:05,579
及五，六。

387
00:17:05,579 --> 00:17:05,839
當然。

388
00:17:05,839 --> 00:17:06,450
五和六。

389
00:17:06,450 --> 00:17:08,390
好吧，我們還會回來
你們下一次。

390
00:17:08,390 --> 00:17:09,640
好吧，我們就到了。

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> 所有的權利，因為你先在這裡
你想成為一個笨拙

393
00:17:14,819 --> 00:17:16,119
在谷歌的玻璃在這裡？

394
00:17:16,119 --> 00:17:19,075
好，那麼，OK，玻璃，
錄製視頻。

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK，你去好。

397
00:17:24,589 --> 00:17:27,950
>> 所有的權利，所以如果你們可以過來
在這裡，我已經提前做好準備

398
00:17:27,950 --> 00:17:30,110
一些數字。

399
00:17:30,110 --> 00:17:31,240
好吧，我們在這裡。

400
00:17:31,240 --> 00:17:33,440
而你為什麼不走一點
進一步的方式。

401
00:17:33,440 --> 00:17:35,520
，讓我們看看，你叫什麼名字，
谷歌玻璃？

402
00:17:35,520 --> 00:17:35,910
>> 學生：本。

403
00:17:35,910 --> 00:17:36,230
>> 揚聲器1：本？

404
00:17:36,230 --> 00:17:38,380
OK，奔，你將是第一，從字面上。

405
00:17:38,380 --> 00:17:40,580
因此，我們會向您發送
結束階段。

406
00:17:40,580 --> 00:17:41,670
所有的權利，和你的名字嗎？

407
00:17:41,670 --> 00:17:41,990
>> 學生：賈森。

408
00:17:41,990 --> 00:17:44,530
>> 揚聲器1：傑森，OK你
9號。

409
00:17:44,530 --> 00:17:46,700
所以，如果你想遵循本辦法。

410
00:17:46,700 --> 00:17:47,010
>> 學生：吉爾。

411
00:17:47,010 --> 00:17:49,630
>> 揚聲器1：吉爾，你要去
17，如果我這樣做

412
00:17:49,630 --> 00:17:51,260
智能，我將不得不
在其另一端開始。

413
00:17:51,260 --> 00:17:52,370
你走那條路。

414
00:17:52,370 --> 00:17:53,030
22。

415
00:17:53,030 --> 00:17:53,670
你是誰？

416
00:17:53,670 --> 00:17:53,980
>> 學生：瑪麗。

417
00:17:53,980 --> 00:17:56,130
>> 揚聲器1：瑪麗，你會是22。

418
00:17:56,130 --> 00:17:58,420
你的名字是什麼？

419
00:17:58,420 --> 00:17:58,810
>> 學生：克里斯。

420
00:17:58,810 --> 00:18:00,100
>> 揚聲器1：克里斯，你會是26。

421
00:18:00,100 --> 00:18:00,740
然後最後。

422
00:18:00,740 --> 00:18:01,400
>> 學生：戴安娜。

423
00:18:01,400 --> 00:18:02,670
>> 揚聲器1：戴安娜，你會是34。

424
00:18:02,670 --> 00:18:03,920
所以你在這裡。

425
00:18:03,920 --> 00:18:06,360
>> 好吧，如此完美排序
已經訂購。

426
00:18:06,360 --> 00:18:09,600
，讓我們繼續前進，為此
這樣我們就可以真的 - 

427
00:18:09,600 --> 00:18:11,720
奔你只是尋找一​​種
到無處存在。

428
00:18:11,720 --> 00:18:15,670
OK，讓我們繼續前進，並描繪這個
使用武器，就像我，究竟

429
00:18:15,670 --> 00:18:16,250
這是怎麼回事。

430
00:18:16,250 --> 00:18:19,540
因此，繼續前進，給自己一個
步行或兩個自己之間。

431
00:18:19,540 --> 00:18:22,900
繼續前進，用一隻手點
你應該指向誰

432
00:18:22,900 --> 00:18:23,470
在此基礎上。

433
00:18:23,470 --> 00:18:25,890
如果你只是指向空
直下到地板上。

434
00:18:25,890 --> 00:18:27,690
OK，這樣很好。

435
00:18:27,690 --> 00:18:32,290
>> 所以現在我們有一個鍊錶，讓我
建議，我會發揮的作用

436
00:18:32,290 --> 00:18:35,110
PTR，所以我不會打擾
攜帶這種左右。

437
00:18:35,110 --> 00:18:37,830
然後 - 有人愚蠢的慣例 - 
你可以調用任何你想要的 - 

438
00:18:37,830 --> 00:18:39,800
前身指針，潑尼松指針 - 

439
00:18:39,800 --> 00:18:43,930
它只是我們給的綽號
我們的示例代碼，我的左手。

440
00:18:43,930 --> 00:18:47,240
另一方面，要保持
誰是誰在跟踪

441
00:18:47,240 --> 00:18:48,400
下面的場景。

442
00:18:48,400 --> 00:18:52,390
>> 因此，假設，第一，我要拔掉
，插入第一個例子，說

443
00:18:52,390 --> 00:18:54,330
20，到列表中。

444
00:18:54,330 --> 00:18:57,160
所以我需要有人來
體現我們20號。

445
00:18:57,160 --> 00:18:58,950
所以我需要有人對malloc
從觀眾。

446
00:18:58,950 --> 00:18:59,380
上來吧。

447
00:18:59,380 --> 00:19:00,340
你叫什麼名字？

448
00:19:00,340 --> 00:19:01,300
>> 學生：布萊恩。

449
00:19:01,300 --> 00:19:05,270
>> 揚聲器1：布萊恩，所有的權利，所以你
須含20的節點。

450
00:19:05,270 --> 00:19:06,810
好吧，我們在這裡。

451
00:19:06,810 --> 00:19:10,025
很顯然，
不屬於布賴恩？

452
00:19:10,025 --> 00:19:12,190
因此，在中間 - 實際上，
等待一分鐘。

453
00:19:12,190 --> 00:19:13,420
我們這樣做是為了

454
00:19:13,420 --> 00:19:17,170
我們正在做這個了很多困難
比它需要的是在第一次。

455
00:19:17,170 --> 00:19:21,210
OK，我們要免費布賴恩
和realloc的布賴恩五個。

456
00:19:21,210 --> 00:19:23,680
>> 好了，現在我們要插入
布賴恩五個。

457
00:19:23,680 --> 00:19:25,960
這樣一來就在這裡
本只是一瞬間。

458
00:19:25,960 --> 00:19:28,250
你大概可以告訴
這個故事是怎麼回事。

459
00:19:28,250 --> 00:19:30,500
但是，讓我們仔細想想
操作順序。

460
00:19:30,500 --> 00:19:32,880
和它的正是這種視覺
要排隊

461
00:19:32,880 --> 00:19:34,080
與示例代碼。

462
00:19:34,080 --> 00:19:40,120
所以，我在這裡已經PTR最初指向
不奔，本身的，但在任何

463
00:19:40,120 --> 00:19:43,245
重視他包含在這種情況下
 - 再次你叫什麼名字？

464
00:19:43,245 --> 00:19:43,670
>> 學生：賈森。

465
00:19:43,670 --> 00:19:47,350
>> 揚聲器1：傑森，所以我和Ben
指著傑森在這一刻。

466
00:19:47,350 --> 00:19:49,700
所以現在我必須確定，
布賴恩屬於哪裡？

467
00:19:49,700 --> 00:19:53,500
所以唯一的事情，我有機會到
現在是他的n個數據項。

468
00:19:53,500 --> 00:19:58,280
所以我要來檢查，
布賴恩小於賈森？

469
00:19:58,280 --> 00:19:59,770
答案是真實​​的。

470
00:19:59,770 --> 00:20:03,680
>> 那麼現在需要什麼發生，
以正確的順序？

471
00:20:03,680 --> 00:20:07,120
我需要更新多少指針
總在這個故事呢？

472
00:20:07,120 --> 00:20:10,720
在哪裡，我的手仍指向
傑森，和你的手 - 如果你想

473
00:20:10,720 --> 00:20:12,930
把你的手，有點像，我
不知道，是一個問號。

474
00:20:12,930 --> 00:20:14,070
好，好。

475
00:20:14,070 --> 00:20:15,670
>> 好吧，讓你擁有
幾個候選人。

476
00:20:15,670 --> 00:20:20,500
奔或I或布賴恩或傑森
或其他人，這

477
00:20:20,500 --> 00:20:21,370
指針需要改變嗎？

478
00:20:21,370 --> 00:20:23,260
總共有多少人？

479
00:20:23,260 --> 00:20:24,080
>> OK，所以兩個。

480
00:20:24,080 --> 00:20:27,090
我的指針並不真的無所謂了
因為我只是暫時的。

481
00:20:27,090 --> 00:20:31,370
因此，它是這兩個傢伙，據推測，
Ben和布賴恩。

482
00:20:31,370 --> 00:20:34,410
所以我建議大家更新
奔，因為他是第一。

483
00:20:34,410 --> 00:20:36,350
這個列表的第一個元素
現在將是布萊恩。

484
00:20:36,350 --> 00:20:38,070
因此，本布賴恩點。

485
00:20:38,070 --> 00:20:39,320
OK，現在該怎麼辦呢？

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> 誰被指出在誰？

488
00:20:43,460 --> 00:20:44,710
>> 學生：[聽不清]。

489
00:20:44,710 --> 00:20:46,180
>> 揚聲器1：確定Brian擁有
以指向賈森。

490
00:20:46,180 --> 00:20:48,360
但我已經失去了該指針的軌道？

491
00:20:48,360 --> 00:20:49,980
我知道Jason是嗎？

492
00:20:49,980 --> 00:20:50,790
>> 學生：[聽不清]。

493
00:20:50,790 --> 00:20:52,620
>> 揚聲器1：我做的，因為我
暫時指針。

494
00:20:52,620 --> 00:20:55,110
而據推測，我並沒有改變
指向新的節點。

495
00:20:55,110 --> 00:20:58,300
所以，我們可以簡單地布賴恩點
我指著誰。

496
00:20:58,300 --> 00:20:59,000
我們就大功告成了。

497
00:20:59,000 --> 00:21:01,890
所以，在插入
開始的名單。

498
00:21:01,890 --> 00:21:02,950
有兩個關鍵步驟。

499
00:21:02,950 --> 00:21:06,750
一，我們必須更新奔，然後
我們也有更新布賴恩。

500
00:21:06,750 --> 00:21:09,230
然後我沒有打擾
其餘的疲憊

501
00:21:09,230 --> 00:21:12,680
名單，因為我們已經找到了自己的
位置，因為他屬於

502
00:21:12,680 --> 00:21:14,080
左側的第一個元素。

503
00:21:14,080 --> 00:21:15,400
>> 所有的權利，所以非常簡單。

504
00:21:15,400 --> 00:21:18,110
事實上，感覺就像我們幾乎
這太複雜了。

505
00:21:18,110 --> 00:21:20,240
現在讓我們為這事結束
列表，看到

506
00:21:20,240 --> 00:21:21,380
開始的複雜性。

507
00:21:21,380 --> 00:21:24,560
因此，如果現在，我的alloc從觀眾。

508
00:21:24,560 --> 00:21:25,540
任何人想打55？

509
00:21:25,540 --> 00:21:26,700
好吧，我先看到你的手。

510
00:21:26,700 --> 00:21:29,620
上來吧。

511
00:21:29,620 --> 00:21:30,030
嗯。

512
00:21:30,030 --> 00:21:31,177
你叫什麼名字？

513
00:21:31,177 --> 00:21:32,310
>> 學生：[聽不清]。

514
00:21:32,310 --> 00:21:33,240
>> 揚聲器1 Habata。

515
00:21:33,240 --> 00:21:33,890
OK，就到了。

516
00:21:33,890 --> 00:21:35,730
你會是55號。

517
00:21:35,730 --> 00:21:37,820
所以，你，當然，屬於
上面的列表末尾。

518
00:21:37,820 --> 00:21:41,850
因此，讓我們重播模擬與我
是PTR只是一瞬間。

519
00:21:41,850 --> 00:21:44,050
所以，我首先要指向
無論奔指向。

520
00:21:44,050 --> 00:21:45,900
我們都指向現在在布賴恩。

521
00:21:45,900 --> 00:21:48,420
因此，圖55是不小於5。

522
00:21:48,420 --> 00:21:52,510
所以，我要更新自己的
Brian的下一個指針，指向誰

523
00:21:52,510 --> 00:21:54,450
現在當然賈森。

524
00:21:54,450 --> 00:21:57,310
圖55是不小於9，所以
我要更新PTR。

525
00:21:57,310 --> 00:21:58,890
我要更新PTR。

526
00:21:58,890 --> 00:22:02,290
我要更新的PTR
我更新的PTR。

527
00:22:02,290 --> 00:22:05,060
我要去 - 嗯，有什麼
你的名字嗎？

528
00:22:05,060 --> 00:22:05,560
>> 學生：戴安娜。

529
00:22:05,560 --> 00:22:09,190
>> 揚聲器1：戴安娜是指指點點，當然，
在null與她的左手。

530
00:22:09,190 --> 00:22:13,030
那麼，這實際上Habata
屬於清楚嗎？

531
00:22:13,030 --> 00:22:15,050
到左邊，在這裡。

532
00:22:15,050 --> 00:22:19,460
所以，我怎麼知道在這裡把她
我想我搞砸了。

533
00:22:19,460 --> 00:22:22,420
因為PTR藝術
時間在這一刻？

534
00:22:22,420 --> 00:22:23,240
NULL。

535
00:22:23,240 --> 00:22:25,580
因此，即使，在視覺上，我們就可以
明顯看到所有這些

536
00:22:25,580 --> 00:22:26,610
這裡的人在舞台上。

537
00:22:26,610 --> 00:22:29,680
我以前沒有記錄
在列表中的人。

538
00:22:29,680 --> 00:22:33,210
我沒有手指指出，
在這種情況下，節點號為34。

539
00:22:33,210 --> 00:22:34,760
>> 因此，讓我們真正開始過。

540
00:22:34,760 --> 00:22:37,560
所以，現在我居然需要
一個第二局部變量。

541
00:22:37,560 --> 00:22:40,980
這是什麼，你會看到在
實際樣品的C代碼，在那裡，因為我去，

542
00:22:40,980 --> 00:22:45,860
當我更新我的右手指向
傑森，從而留下布賴恩的背後，我

543
00:22:45,860 --> 00:22:51,440
最好開始用我的左手
更新我在哪裡，讓我去

544
00:22:51,440 --> 00:22:52,700
通過這個名單 - 

545
00:22:52,700 --> 00:22:55,040
比我預期的更笨拙
現在這裡視覺 - 

546
00:22:55,040 --> 00:22:56,740
我會去的
列表末尾。

547
00:22:56,740 --> 00:23:00,020
>> 這手仍是空的，這是非常
沒用的，其他的比來表示

548
00:23:00,020 --> 00:23:02,980
我很清楚在列表末尾，
但現在至少我有這個

549
00:23:02,980 --> 00:23:08,270
前身指向這裡，所以
現在是什麼手和指針需要什麼

550
00:23:08,270 --> 00:23:10,150
要更新？

551
00:23:10,150 --> 00:23:13,214
你想誰的手
先來重新配置？

552
00:23:13,214 --> 00:23:15,190
>> 學生：[聽不清]。

553
00:23:15,190 --> 00:23:16,220
>> 揚聲器1：OK，所以戴安娜的。

554
00:23:16,220 --> 00:23:21,110
在哪裡你想點
戴安娜的左指針？

555
00:23:21,110 --> 00:23:23,620
在55中，據推測，從而使
我們已經有插入。

556
00:23:23,620 --> 00:23:25,560
55指針應該在哪裡去了？

557
00:23:25,560 --> 00:23:27,000
向下，佔空。

558
00:23:27,000 --> 00:23:28,890
而我的手，在這一點上，不
不要緊，因為他們只是

559
00:23:28,890 --> 00:23:30,070
臨時變量。

560
00:23:30,070 --> 00:23:31,030
所以，現在我們就大功告成了。

561
00:23:31,030 --> 00:23:34,650
>> 所以額外的複雜性 - 
它並不難實現，

562
00:23:34,650 --> 00:23:38,660
但我們需要一個輔助變量
確定之前，我將我的權利

563
00:23:38,660 --> 00:23:42,140
另一方面，我更新我的左值
手潑尼松指針，所以

564
00:23:42,140 --> 00:23:45,860
我有一個尾隨指針
跟踪我在哪裡。

565
00:23:45,860 --> 00:23:49,360
順便說一句，如果你以為這
通過，這種感覺就像是一個

566
00:23:49,360 --> 00:23:51,490
必須保持有點煩
跟踪這個左手。

567
00:23:51,490 --> 00:23:54,015
>> 將另一種解決方案
這個問題已被？

568
00:23:54,015 --> 00:23:56,500
如果你得到了重新設計數據
我們正在談論的結構

569
00:23:56,500 --> 00:23:59,630
通過吧？

570
00:23:59,630 --> 00:24:02,690
如果這只是一種感覺有點
惱人的一樣，兩個指針

571
00:24:02,690 --> 00:24:08,430
通過列表，誰還能
有，在一個理想的世界中，保持

572
00:24:08,430 --> 00:24:10,160
我們所需要的信息？

573
00:24:10,160 --> 00:24:11,360
是嗎？

574
00:24:11,360 --> 00:24:12,610
>> 學生：[聽不清]。

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> 揚聲器1：沒錯。

577
00:24:16,150 --> 00:24:19,130
所以實際上是一個有趣的
胚芽的想法。

578
00:24:19,130 --> 00:24:22,470
而前一個指針，這個想法
指向前一個元素。

579
00:24:22,470 --> 00:24:25,580
如果我只是體現
列表本身的內部？

580
00:24:25,580 --> 00:24:27,810
這將是難以想像
沒有所有的紙張

581
00:24:27,810 --> 00:24:28,830
掉落到地板上。

582
00:24:28,830 --> 00:24:31,860
但是，假如這些人同時使用
他們手中沒有先前

583
00:24:31,860 --> 00:24:35,950
指針，和一個下一個指針，從而
執行什麼，我們會打電話給一個雙

584
00:24:35,950 --> 00:24:36,830
鍊錶。

585
00:24:36,830 --> 00:24:41,090
這將允許我排序退，
更容易無我有，

586
00:24:41,090 --> 00:24:43,800
程序員，不得不保持
手動跟踪 - 

587
00:24:43,800 --> 00:24:44,980
真正的手動 - 

588
00:24:44,980 --> 00:24:47,280
以前我一直
在列表中。

589
00:24:47,280 --> 00:24:48,110
因此，我們將無法做到這一點。

590
00:24:48,110 --> 00:24:50,950
我們將保持它的簡單，因為這是
要來的價格，兩倍

591
00:24:50,950 --> 00:24:53,450
多的空間的指針，
如果你想要第二個。

592
00:24:53,450 --> 00:24:55,760
但是，這確實是一個共同的
數據結構被稱為一個

593
00:24:55,760 --> 00:24:57,410
雙向鍊錶。

594
00:24:57,410 --> 00:25:01,310
>> 讓我們在這裡做最後的例子把
這些傢伙，他們的苦難。

595
00:25:01,310 --> 00:25:03,270
所以malloc的20。

596
00:25:03,270 --> 00:25:05,320
來吧從那裡的過道。

597
00:25:05,320 --> 00:25:06,280
好吧，你叫什麼名字？

598
00:25:06,280 --> 00:25:07,440
>> 學生：[聽不清]。

599
00:25:07,440 --> 00:25:07,855
>> 揚聲器1：對不起？

600
00:25:07,855 --> 00:25:08,480
>> 學生：[聽不清]。

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1：Demeron的？

602
00:25:09,410 --> 00:25:10,230
確定上來吧。

603
00:25:10,230 --> 00:25:11,910
您應為20。

604
00:25:11,910 --> 00:25:14,720
你顯然要
屬於17和22之間。

605
00:25:14,720 --> 00:25:16,150
因此，讓我吸取我的教訓。

606
00:25:16,150 --> 00:25:18,150
我要開始指針
指著布賴恩。

607
00:25:18,150 --> 00:25:21,190
我要我的左手
只更新布萊恩，我謹

608
00:25:21,190 --> 00:25:23,600
傑森，檢查少做了20比9？

609
00:25:23,600 --> 00:25:24,060
號

610
00:25:24,060 --> 00:25:25,430
20小於17？

611
00:25:25,430 --> 00:25:25,880
號

612
00:25:25,880 --> 00:25:27,450
20小於22？

613
00:25:27,450 --> 00:25:28,440
是。

614
00:25:28,440 --> 00:25:34,070
那麼，什麼指針或手需要改變
他們指著呢？

615
00:25:34,070 --> 00:25:37,070
>> 因此，我們可以做的17指向20。

616
00:25:37,070 --> 00:25:37,860
所以這就是罰款。

617
00:25:37,860 --> 00:25:40,080
我們要指出在哪裡
你的指針現在？

618
00:25:40,080 --> 00:25:41,330
在22。

619
00:25:41,330 --> 00:25:45,410
我們知道22，再次感謝
我臨時指針。

620
00:25:45,410 --> 00:25:46,760
因此，我們有“確定”。

621
00:25:46,760 --> 00:25:49,440
所以在這臨時存儲
我一直保留著的軌道，每個人都。

622
00:25:49,440 --> 00:25:55,055
現在，你可以直觀地去到哪裡
屬於你，現在我們需要1，2，3，

623
00:25:55,055 --> 00:25:58,410
4，5，6，7，8，9個壓力球，
和掌聲雷動

624
00:25:58,410 --> 00:25:59,770
這些傢伙，如果我們能。

625
00:25:59,770 --> 00:26:00,410
幹得漂亮。

626
00:26:00,410 --> 00:26:05,320
>> [掌聲]

627
00:26:05,320 --> 00:26:06,330
>> 揚聲器1：所有權利。

628
00:26:06,330 --> 00:26:09,860
您可能保持件
紙作為紀念。

629
00:26:09,860 --> 00:26:15,930
>> 好，那麼相信我，這是一個很大
更容易穿行

630
00:26:15,930 --> 00:26:17,680
人類比它的實際代碼。

631
00:26:17,680 --> 00:26:22,690
但你會發現在短短的時刻
現在，是相同的 - 哦，謝謝你。

632
00:26:22,690 --> 00:26:23,630
謝謝 - 

633
00:26:23,630 --> 00:26:29,360
是，你會發現相同的數據
結構，鍊錶，實際上可以

634
00:26:29,360 --> 00:26:33,200
可以使用作為構建塊更
複雜的數據結構。

635
00:26:33,200 --> 00:26:37,620
>> 實現過這裡的主題是
我們絕對介紹

636
00:26:37,620 --> 00:26:40,060
進入實施的複雜性
在此算法中。

637
00:26:40,060 --> 00:26:43,940
插入，如果我們通過它去，
刪除和搜索，是一個小的

638
00:26:43,940 --> 00:26:46,660
比它更複雜
是一個數組。

639
00:26:46,660 --> 00:26:48,040
但是，我們獲得了一些活力。

640
00:26:48,040 --> 00:26:50,180
我們得到一個自適應的數據結構。

641
00:26:50,180 --> 00:26:54,010
>> 但同樣，我們付出的代價有一些
額外的複雜性，無論是在

642
00:26:54,010 --> 00:26:54,910
執行它。

643
00:26:54,910 --> 00:26:56,750
我們放棄了隨機訪問。

644
00:26:56,750 --> 00:27:00,450
而且說實話，有沒有一些不錯的
乾淨的玻片，我可以給你，

645
00:27:00,450 --> 00:27:03,120
這裡說的是為什麼一個鍊錶
優於數組。

646
00:27:03,120 --> 00:27:04,100
離開它。

647
00:27:04,100 --> 00:27:07,520
由於主題現在再次發生，甚至
更何況在未來幾週內，

648
00:27:07,520 --> 00:27:10,200
不一定
一個正確的答案。

649
00:27:10,200 --> 00:27:13,830
>> 這就是為什麼我們有獨立的軸
問題集的設計。

650
00:27:13,830 --> 00:27:17,700
這將是非常敏感的上下文
您是否要使用此數據

651
00:27:17,700 --> 00:27:21,750
結構或那一個，會
取決於什麼對你很重要條款

652
00:27:21,750 --> 00:27:24,620
的資源和複雜性。

653
00:27:24,620 --> 00:27:28,830
>> 但是，讓我提出，理想的數據
結構，聖杯，將

654
00:27:28,830 --> 00:27:32,200
東西是恆定的時間，
不論多少東西

655
00:27:32,200 --> 00:27:36,940
在它裡面，它不會是驚人的，如果一個
返回的數據結構答案

656
00:27:36,940 --> 00:27:37,920
常量時間。

657
00:27:37,920 --> 00:27:38,330
是。

658
00:27:38,330 --> 00:27:40,110
這個詞是在巨大的字典。

659
00:27:40,110 --> 00:27:41,550
“或”否“，這個詞是沒有的。

660
00:27:41,550 --> 00:27:43,270
或任何這樣的問題。

661
00:27:43,270 --> 00:27:46,360
那麼讓我們來看看，如果我們不能至少
走，一步步走向。

662
00:27:46,360 --> 00:27:50,190
>> 讓我提出了一個新的數據結構，
可用於不同的事情，

663
00:27:50,190 --> 00:27:52,260
在這種情況下，所謂的哈希表。

664
00:27:52,260 --> 00:27:55,590
所以我們實際上一眼
在一個數組中，在這種情況下，

665
00:27:55,590 --> 00:28:00,550
有些武斷，我畫這
作為數組排序的哈希表

666
00:28:00,550 --> 00:28:02,810
兩維數組 - 

667
00:28:02,810 --> 00:28:05,410
或者更確切地說，它這裡描繪為兩
維數組 - 但是這僅僅是

668
00:28:05,410 --> 00:28:10,770
大小為26的數組，例如，如果我們
調用數組桌，桌上托架

669
00:28:10,770 --> 00:28:12,440
零是在頂部的矩形。

670
00:28:12,440 --> 00:28:15,090
表托架25是矩形
在底部。

671
00:28:15,090 --> 00:28:18,620
我這是怎麼可能畫出一個數據
我想存儲結構中，

672
00:28:18,620 --> 00:28:19,790
人的名字。

673
00:28:19,790 --> 00:28:24,370
>> 因此，舉例來說，我不會畫
整個事情上的開銷，如果我

674
00:28:24,370 --> 00:28:29,160
該數組，我現在要
調用一個哈希表，這又是

675
00:28:29,160 --> 00:28:31,360
零的位置。

676
00:28:31,360 --> 00:28:34,840
這裡是位置
一個，等等。

677
00:28:34,840 --> 00:28:37,880
我要求，我想用這個數據
結構，為了討論的方便，

678
00:28:37,880 --> 00:28:42,600
存儲人的名字，Alice和Bob
查理和其他類似的名稱。

679
00:28:42,600 --> 00:28:46,110
所以，現在覺得這個作為起點
，也就是說，一個字典

680
00:28:46,110 --> 00:28:47,520
有很多的話。

681
00:28:47,520 --> 00:28:49,435
他們正好是名
在我們的例子。

682
00:28:49,435 --> 00:28:52,560
這是太有密切關係，也許，
實施一個拼寫檢查，因為我們

683
00:28:52,560 --> 00:28:54,400
可能問題設置6。

684
00:28:54,400 --> 00:28:59,300
>> 所以，如果我們有一個總規模26陣列
因此，這是第25的位置

685
00:28:59,300 --> 00:29:03,390
在底部，我要求愛麗絲
字典中的第一個字

686
00:29:03,390 --> 00:29:07,260
名，我想插入RAM，
到該數據結構中，其中

687
00:29:07,260 --> 00:29:12,480
愛麗絲的直覺告訴你，
在這個數組名稱應該去？

688
00:29:12,480 --> 00:29:13,510
>> 我們有26個選項。

689
00:29:13,510 --> 00:29:14,990
如果我們想要把她嗎？

690
00:29:14,990 --> 00:29:16,200
我們希望她在支架為零，對不對？

691
00:29:16,200 --> 00:29:18,280
為愛麗絲，我們稱之為零。

692
00:29:18,280 --> 00:29:20,110
和B，和C將有兩個。

693
00:29:20,110 --> 00:29:22,600
因此，我們打算寫
愛麗絲的名字在這裡。

694
00:29:22,600 --> 00:29:24,890
如果我們再插入鮑勃，他
名稱會去這裡。

695
00:29:24,890 --> 00:29:27,280
查理會去這裡。

696
00:29:27,280 --> 00:29:30,500
如此反复向下
這樣的數據結構。

697
00:29:30,500 --> 00:29:32,090
>> 這是一個美妙的數據結構。

698
00:29:32,090 --> 00:29:32,730
為什麼呢？

699
00:29:32,730 --> 00:29:37,460
那麼什麼是運行時間
插入成這樣的一個人的名字

700
00:29:37,460 --> 00:29:39,850
數據結構的權利嗎？

701
00:29:39,850 --> 00:29:43,702
鑑於實施該表，
誠然，作為一個數組。

702
00:29:43,702 --> 00:29:44,940
那麼它的恆定時間。

703
00:29:44,940 --> 00:29:45,800
這是一個順序。

704
00:29:45,800 --> 00:29:46,360
為什麼呢？

705
00:29:46,360 --> 00:29:48,630
>> 那麼你如何確定
愛麗絲屬於？

706
00:29:48,630 --> 00:29:51,000
你看看她的名字的信嗎？

707
00:29:51,000 --> 00:29:51,490
第一。

708
00:29:51,490 --> 00:29:54,350
在那裡，你可以得到，如果它是一個字符串，
只是看著串

709
00:29:54,350 --> 00:29:55,200
支架零。

710
00:29:55,200 --> 00:29:57,110
因此，第0個字符的字符串。

711
00:29:57,110 --> 00:29:57,610
這是很容易的。

712
00:29:57,610 --> 00:30:00,350
我們已在加密
分配星期前。

713
00:30:00,350 --> 00:30:05,310
然後，一旦你知道Alice的
字母是大寫的A，我們可以減去

714
00:30:05,310 --> 00:30:08,160
關閉65或資本A本身，
這給了我們為零。

715
00:30:08,160 --> 00:30:10,940
因此，我們現在知道，愛麗絲屬於
在零的位置。

716
00:30:10,940 --> 00:30:14,240
>> 和給定的一個指針，指向這個數據
某種結構，多久？

717
00:30:14,240 --> 00:30:18,840
它帶我找到位置
陣列中的零？

718
00:30:18,840 --> 00:30:22,080
只需一個步驟，這是恆定的時間
由於隨機接入中，我們

719
00:30:22,080 --> 00:30:23,780
建議的是一個數組的一個特徵。

720
00:30:23,780 --> 00:30:28,570
因此，在短期，搞清楚什麼索引
Alice的名字，這是在

721
00:30:28,570 --> 00:30:32,610
這種情況下，是A，或讓剛剛解決
為零，其中B是C是

722
00:30:32,610 --> 00:30:34,900
二，計算出
是恆定的時間。

723
00:30:34,900 --> 00:30:38,510
我只是來看看她的第一個字母，
搞清楚其中零為

724
00:30:38,510 --> 00:30:40,460
數組也是恆定的時間。

725
00:30:40,460 --> 00:30:42,140
因此從技術上講這是
像現在兩個步驟。

726
00:30:42,140 --> 00:30:43,330
但是，這仍然不變。

727
00:30:43,330 --> 00:30:46,880
所以，我們稱之為一大O，所以我們
愛麗絲插入到這個表中

728
00:30:46,880 --> 00:30:48,440
常量時間。

729
00:30:48,440 --> 00:30:50,960
>> 不過，當然，我
天真在這裡，對不對？

730
00:30:50,960 --> 00:30:53,240
如果在課堂上有亞倫？

731
00:30:53,240 --> 00:30:53,990
還是艾麗西亞？

732
00:30:53,990 --> 00:30:57,230
或任何其他的名字開始
A.我們要去哪裡放

733
00:30:57,230 --> 00:31:00,800
那人，對不對？

734
00:31:00,800 --> 00:31:03,420
我的意思是，現在只有三個
老百姓餐桌上，所以也許我們

735
00:31:03,420 --> 00:31:07,490
應該把亞倫的位置
零壹兩三個。

736
00:31:07,490 --> 00:31:09,480
>> 好吧，我可以在這裡把A。

737
00:31:09,480 --> 00:31:13,350
然而，如果我們嘗試將大衛
這個名單，大衛去哪裡？

738
00:31:13,350 --> 00:31:15,170
現在，我們的系統開始打破
向下，向右？

739
00:31:15,170 --> 00:31:19,210
因為現在，大衛在這裡結束了
如果阿龍其實是在這裡。

740
00:31:19,210 --> 00:31:23,060
所以現在有一個整體思路
乾淨的數據結構，讓我們

741
00:31:23,060 --> 00:31:28,010
恆定的時間插入不再
恆定的時間，因為我有

742
00:31:28,010 --> 00:31:31,240
檢查，哦，該死的，有人已經
在愛麗絲的位置。

743
00:31:31,240 --> 00:31:35,320
>> 讓我探究這些數據的其餘部分
結構，尋找一個位置把

744
00:31:35,320 --> 00:31:37,130
有人喜歡亞倫的名字。

745
00:31:37,130 --> 00:31:39,390
等也開始
線性時間。

746
00:31:39,390 --> 00:31:42,710
此外，如果你現在想找到
亞倫在此數據結構，你

747
00:31:42,710 --> 00:31:45,430
檢查和亞倫的名字是不是在這裡。

748
00:31:45,430 --> 00:31:47,960
理想情況下，你只說亞倫
而不是在數據結構中。

749
00:31:47,960 --> 00:31:51,530
但是，如果你開始做空間
亞倫那裡應該有一個D

750
00:31:51,530 --> 00:31:55,600
或E，你最壞的情況下，有檢查
整個數據結構，在

751
00:31:55,600 --> 00:31:59,480
這種情況下，移交到的東西
表的大小成線性關係。

752
00:31:59,480 --> 00:32:00,920
>> 所以所有的權利，我會解決這個問題。

753
00:32:00,920 --> 00:32:04,200
這裡的問題是，我不得不
26此數組中元素。

754
00:32:04,200 --> 00:32:05,000
讓我改變它。

755
00:32:05,000 --> 00:32:06,010
哎呀。

756
00:32:06,010 --> 00:32:10,600
讓我改變它，因此而幸福
大小26個，發現底部

757
00:32:10,600 --> 00:32:12,720
指數將改變為n減1。

758
00:32:12,720 --> 00:32:16,610
如果26顯然是太小了人類的
的名字，因為有成千上萬的

759
00:32:16,610 --> 00:32:20,830
世界的名字，讓我們使
在100或1000或10000。

760
00:32:20,830 --> 00:32:22,960
讓我們只分配更多的空間。

761
00:32:22,960 --> 00:32:27,230
>> 嗯，這並不一定減少
的概率，我們不會有兩個

762
00:32:27,230 --> 00:32:31,510
人們起的名字，
所以，你要嘗試將

763
00:32:31,510 --> 00:32:33,120
名位置零。

764
00:32:33,120 --> 00:32:36,850
他們還在碰撞，
意味著我們仍然需要一個解決方案，把

765
00:32:36,850 --> 00:32:41,020
愛麗絲亞倫和艾麗西亞和其他
名開始與A別處。

766
00:32:41,020 --> 00:32:43,460
但多少的問題是什麼？

767
00:32:43,460 --> 00:32:46,870
什麼的概率
有碰撞在一個數據

768
00:32:46,870 --> 00:32:48,240
這樣的結構？

769
00:32:48,240 --> 00:32:52,570
>> 好吧，讓我 - 我們會回來的
這裡這個問題。

770
00:32:52,570 --> 00:32:55,530
看我們如何可能
先解決它。

771
00:32:55,530 --> 00:32:58,480
讓我拉起這個建議。

772
00:32:58,480 --> 00:33:02,020
我們剛剛描述的是一種算法，
一個啟發式稱為線性

773
00:33:02,020 --> 00:33:05,030
探測，即如果你試圖插入
這裡的東西在此數據

774
00:33:05,030 --> 00:33:08,920
結構，該結構被稱為一個哈希表，
而且也沒有的房間裡，你

775
00:33:08,920 --> 00:33:12,000
真正探測的數據結構
檢查，這是可用的？

776
00:33:12,000 --> 00:33:13,430
這是這是可用？

777
00:33:13,430 --> 00:33:13,980
這是？

778
00:33:13,980 --> 00:33:17,550
而當它終於插入
名字，你原本打算

779
00:33:17,550 --> 00:33:19,370
在該位置的其他地方。

780
00:33:19,370 --> 00:33:23,360
但是，在最壞的情況下，唯一的現貨
可能是最底層的數據

781
00:33:23,360 --> 00:33:25,090
結構，數組的盡頭。

782
00:33:25,090 --> 00:33:30,130
>> 因此，線性探測，在最壞的情況下，
下放成線性算法

783
00:33:30,130 --> 00:33:34,500
亞倫，如果他恰好是最後插入
這個數據結構中，他可能會

784
00:33:34,500 --> 00:33:39,540
碰撞，該第一位置，但
然後結束壞運氣的最末尾。

785
00:33:39,540 --> 00:33:43,940
因此，這是不是一個常數
一次聖杯的我們。

786
00:33:43,940 --> 00:33:47,650
這種方法插入元素
一種數據結構，稱為散列

787
00:33:47,650 --> 00:33:52,050
表不似乎是恆定的時間
至少不會在一般的情況下。

788
00:33:52,050 --> 00:33:54,000
它可以下放成線性的東西。

789
00:33:54,000 --> 00:33:56,970
>> 那麼，如果我們解決衝突
有所不同呢？

790
00:33:56,970 --> 00:34:00,740
因此，這裡是一個更複雜
仍然接近

791
00:34:00,740 --> 00:34:02,800
稱為哈希表。

792
00:34:02,800 --> 00:34:05,890
哈希，順便說一句，
我的意思是指數

793
00:34:05,890 --> 00:34:07,070
我前面提到的。

794
00:34:07,070 --> 00:34:09,810
哈希的東西可以
想到作為一個動詞。

795
00:34:09,810 --> 00:34:13,690
>> 所以，如果你哈希愛麗絲一個名字，
哈希函數，可以這麼說，

796
00:34:13,690 --> 00:34:14,710
應該返回一個數字。

797
00:34:14,710 --> 00:34:18,199
在這種情況下是零，如果她是屬於
位置為零，如果她屬於

798
00:34:18,199 --> 00:34:20,000
的位置，等等。

799
00:34:20,000 --> 00:34:24,360
所以，我的哈希函數迄今一直
超級簡單，只看著

800
00:34:24,360 --> 00:34:26,159
在別人的名字的第一個字母。

801
00:34:26,159 --> 00:34:29,090
但是哈希函數需要
輸入某些數據塊，

802
00:34:29,090 --> 00:34:30,210
一個整數，字符串，等等。

803
00:34:30,210 --> 00:34:32,239
它吐出一個典型的數字。

804
00:34:32,239 --> 00:34:35,739
而且這個數字是該數據
在數據結構中的元素屬於

805
00:34:35,739 --> 00:34:37,800
這裡稱為哈希表。

806
00:34:37,800 --> 00:34:41,400
>> 所以只是憑直覺，這是一個
略有不同的上下文中。

807
00:34:41,400 --> 00:34:44,170
這實際上是指一個例子
涉及的生日，

808
00:34:44,170 --> 00:34:46,850
可能有多達
31月份中的天。

809
00:34:46,850 --> 00:34:52,239
但是，什麼人決定
在發生碰撞時？

810
00:34:52,239 --> 00:34:55,304
上下文，而不是現在的碰撞
名，生日，而是碰撞

811
00:34:55,304 --> 00:35:00,760
如果兩個人有相同的生日
10月2日，例如。

812
00:35:00,760 --> 00:35:02,120
>> 學生：[聽不清]。

813
00:35:02,120 --> 00:35:05,010
>> 揚聲器1：是啊，所以我們在這裡有
利用鍊錶。

814
00:35:05,010 --> 00:35:07,830
因此，它看起來有點不同
把它比我們更早。

815
00:35:07,830 --> 00:35:10,790
但是，我們似乎有一個數組
在左手側。

816
00:35:10,790 --> 00:35:13,230
這是一個索引，因為沒有
特別的原因。

817
00:35:13,230 --> 00:35:14,630
但它仍然是一個數組。

818
00:35:14,630 --> 00:35:16,160
這是一個數組的指針。

819
00:35:16,160 --> 00:35:20,670
每一元素，每個
這些圓圈或斜線 - 斜線

820
00:35:20,670 --> 00:35:23,970
代表空 - 這些
指針顯然指向

821
00:35:23,970 --> 00:35:25,730
什麼數據結構？

822
00:35:25,730 --> 00:35:26,890
鍊錶。

823
00:35:26,890 --> 00:35:30,530
>> 所以，現在我們有能力
硬到我們的程序代碼

824
00:35:30,530 --> 00:35:32,010
表的大小。

825
00:35:32,010 --> 00:35:35,360
在這種情況下，我們知道從未有
在一個月內超過31天。

826
00:35:35,360 --> 00:35:38,480
所以硬編碼值，如31
在這種情況下合理。

827
00:35:38,480 --> 00:35:42,700
在名稱的上下文中，硬編碼
26是不講理的人

828
00:35:42,700 --> 00:35:46,340
名字才開始，例如，
涉及A到Z的字母

829
00:35:46,340 --> 00:35:50,180
>> 我們可以塞進他們都到數據
只要結構，當我們得到一個

830
00:35:50,180 --> 00:35:55,330
碰撞，我們不把這裡的名字，
我們反而認為，這些細胞

831
00:35:55,330 --> 00:36:00,270
不是字符串本身，而是作為
的指針，例如，愛麗絲。

832
00:36:00,270 --> 00:36:03,660
然後愛麗絲可以有另一個指針
另一個名字開始

833
00:36:03,660 --> 00:36:06,150
A.和鮑勃實際上是在這裡。

834
00:36:06,150 --> 00:36:10,850
>> 如果有另一個名字開始
B，他結束了在這裡。

835
00:36:10,850 --> 00:36:15,070
等各元素與該
表二，如果我們設計一個

836
00:36:15,070 --> 00:36:17,350
更巧妙一點 - 

837
00:36:17,350 --> 00:36:18,125
來吧 - 

838
00:36:18,125 --> 00:36:22,950
如果我們設計了這個多一點
巧妙的，現在變成了一個自適應數據

839
00:36:22,950 --> 00:36:27,720
結構，那裡是沒有硬性限制
你可以插入多少元素

840
00:36:27,720 --> 00:36:30,700
到它，因為如果你這樣做有
碰撞，這很好。

841
00:36:30,700 --> 00:36:34,690
只要繼續下去，並將它附加到
我們所看到的有點前

842
00:36:34,690 --> 00:36:38,290
被稱為一個鍊錶。

843
00:36:38,290 --> 00:36:39,690
>> 那麼讓我們來的暫停只是一瞬間。

844
00:36:39,690 --> 00:36:42,570
碰撞的概率是什麼
擺在首位？

845
00:36:42,570 --> 00:36:45,480
對的，也許我過思考，也許
我在工程的這個問題，

846
00:36:45,480 --> 00:36:46,370
因為你知道是什麼嗎？

847
00:36:46,370 --> 00:36:49,070
是的，我可以拿出任意
關閉我的頭頂部的例子喜歡

848
00:36:49,070 --> 00:36:52,870
Allison和亞倫，但在現實中，
給定的均勻分佈

849
00:36:52,870 --> 00:36:56,990
投入，是一些隨機插入
到一個數據結構，什麼是真正的

850
00:36:56,990 --> 00:36:58,580
碰撞的概率？

851
00:36:58,580 --> 00:37:01,670
好吧原來，它實際上是
超高。

852
00:37:01,670 --> 00:37:03,850
讓我概括
問題是這個。

853
00:37:03,850 --> 00:37:08,890
>> 因此，在一個房間裡的n CS50學生，什麼是
的概率，至少

854
00:37:08,890 --> 00:37:11,010
兩名學生在房間裡
有相同的生日嗎？

855
00:37:11,010 --> 00:37:13,346
因此，有什麼。幾個洪德 - 

856
00:37:13,346 --> 00:37:16,790
200，300人在這裡和幾個
今天在家百餘人。

857
00:37:16,790 --> 00:37:20,670
所以，如果你要問自己什麼
兩個人的概率

858
00:37:20,670 --> 00:37:23,930
在這個房間裡有相同的生日，
我們可以弄清楚了這一點。

859
00:37:23,930 --> 00:37:26,250
其實我要求有兩個
同一天生日的人。

860
00:37:26,250 --> 00:37:29,560
>> 舉例來說，有沒有人
今天生日嗎？

861
00:37:29,560 --> 00:37:31,340
昨天？

862
00:37:31,340 --> 00:37:32,590
明天？

863
00:37:32,590 --> 00:37:35,980
所有的權利，所以感覺像我要去
不得不做這363左右

864
00:37:35,980 --> 00:37:39,500
次真正弄清楚
如果我們這樣做，有碰撞。

865
00:37:39,500 --> 00:37:42,350
或者，我們可以做到這一點數學
而不是繁瑣

866
00:37:42,350 --> 00:37:43,200
這樣做。

867
00:37:43,200 --> 00:37:44,500
並提出以下建議。

868
00:37:44,500 --> 00:37:48,740
>> 所以，我建議，我們可以模擬
兩個人的概率

869
00:37:48,740 --> 00:37:55,320
同一天生日的概率為1
減去的概率沒有一個具有

870
00:37:55,320 --> 00:37:56,290
同一天生日。

871
00:37:56,290 --> 00:37:59,960
所以就弄這個，這只是
花哨的編寫方式，

872
00:37:59,960 --> 00:38:03,090
在房間裡的第一人，他或她
可以有任何其中一個可能的

873
00:38:03,090 --> 00:38:07,370
生日的一年，假設365天
與人道歉

874
00:38:07,370 --> 00:38:08,760
2月29日的生日。

875
00:38:08,760 --> 00:38:13,470
>> 因此，在這個房間裡的第一人免費
有任意數量的生日

876
00:38:13,470 --> 00:38:18,280
365的可能性，所以，
我們要做的，365除以365，

877
00:38:18,280 --> 00:38:18,990
這是其中之一。

878
00:38:18,990 --> 00:38:22,700
旁邊的人在房間裡，如果我們的目標
是為了避免碰撞時，也只能

879
00:38:22,700 --> 00:38:26,460
有他或她的生日就如何
許多不同的可能的天？

880
00:38:26,460 --> 00:38:27,610
364。

881
00:38:27,610 --> 00:38:31,430
所以這個表達式中的第二項是
基本上這樣做對我們的數學

882
00:38:31,430 --> 00:38:33,460
通過減去一個可能的日子。

883
00:38:33,460 --> 00:38:36,390
然後第二天，第二天，
第二天下來的總數

884
00:38:36,390 --> 00:38:38,100
在房間裡的人。

885
00:38:38,100 --> 00:38:41,290
>> 如果我們再考慮，又是什麼
的概率不是人人有

886
00:38:41,290 --> 00:38:45,265
獨特的生日，但1減去再次
，我們得到了什麼是一個表達式

887
00:38:45,265 --> 00:38:47,810
可以很稀奇
這個樣子。

888
00:38:47,810 --> 00:38:50,330
但它更有趣
看視覺。

889
00:38:50,330 --> 00:38:55,120
這是一個圖表上的x軸
多少人在房間裡，

890
00:38:55,120 --> 00:38:56,180
生日數。

891
00:38:56,180 --> 00:38:59,840
在y軸上的概率是
碰撞時，兩個人

892
00:38:59,840 --> 00:39:01,230
具有相同的生日。

893
00:39:01,230 --> 00:39:05,020
>> 而從這個曲線是外賣
只要你喜歡40

894
00:39:05,020 --> 00:39:11,110
同學們，你們是在90％的概率
，combinatorically兩個

895
00:39:11,110 --> 00:39:13,550
人或以上有
同一天生日。

896
00:39:13,550 --> 00:39:18,600
一旦你得到58人喜歡它的
幾乎100％的機​​會兩個

897
00:39:18,600 --> 00:39:21,310
房間裡的人將不得不
同一天生日，即使有

898
00:39:21,310 --> 00:39:26,650
365或366個可能的桶，
只有58人在房間裡。

899
00:39:26,650 --> 00:39:29,900
只是統計學，你很可能會
得到的碰撞，在短

900
00:39:29,900 --> 00:39:31,810
激勵這個討論。

901
00:39:31,810 --> 00:39:35,890
即使我們得到看中這裡，
開始這些連鎖，我們還是

902
00:39:35,890 --> 00:39:36,950
將有碰撞。

903
00:39:36,950 --> 00:39:42,710
>> 所以引出了一個問題，什麼是
成本做插入和刪除

904
00:39:42,710 --> 00:39:44,850
進入這樣一個數據結構？

905
00:39:44,850 --> 00:39:46,630
那麼讓我提出 - 

906
00:39:46,630 --> 00:39:51,570
並讓我回到屏幕上對
在這裡 - 如果我們有n個元素

907
00:39:51,570 --> 00:39:56,330
列表，所以如果我們試圖插入
n個元素，我們有

908
00:39:56,330 --> 00:39:58,050
總共有多少桶？

909
00:39:58,050 --> 00:40:03,450
比方說，共31桶
在的情況下的生日。

910
00:40:03,450 --> 00:40:09,240
什麼是最大長度為一個
這些鏈可能？

911
00:40:09,240 --> 00:40:12,670
>> 如果再有31個可能
在一個給定月份的生日。

912
00:40:12,670 --> 00:40:14,580
我們只是聚集大家 - 

913
00:40:14,580 --> 00:40:15,580
實際上這是一個愚蠢的例子。

914
00:40:15,580 --> 00:40:16,960
讓做26代替。

915
00:40:16,960 --> 00:40:20,890
因此，如果實際擁有人名列
從A到Z，從而使

916
00:40:20,890 --> 00:40:22,780
我們26的可能性。

917
00:40:22,780 --> 00:40:25,920
我們使用一個數據結構，如
我們剛才看到的，據此，我們有

918
00:40:25,920 --> 00:40:30,210
一個數組的指針，其中每個
指向一個鍊錶地方的

919
00:40:30,210 --> 00:40:32,360
第一份清單是每個人都
愛麗絲的名字。

920
00:40:32,360 --> 00:40:35,770
第二個名單是每週與
命名開始，

921
00:40:35,770 --> 00:40:36,980
為B，依此類推。

922
00:40:36,980 --> 00:40:41,020
>> 什麼可能各有長短
這些列表，如果我們假設一個乾淨的

923
00:40:41,020 --> 00:40:45,410
從A到Z的名稱分配
在整個數據結構？

924
00:40:45,410 --> 00:40:50,210
有n個人的數據結構中
除以26，如果他們很好

925
00:40:50,210 --> 00:40:52,110
攤開在整個
的數據結構。

926
00:40:52,110 --> 00:40:54,970
因此，每個這些的長度
鏈為n除以26。

927
00:40:54,970 --> 00:40:57,380
但在大O表示法，那是什麼？

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
什麼是真的？

930
00:41:02,440 --> 00:41:04,150
所以這真的只是N，對不對？

931
00:41:04,150 --> 00:41:06,620
因為我們說，在過去，
唉你除以26。

932
00:41:06,620 --> 00:41:08,710
是的，在現實中，它是速度更快。

933
00:41:08,710 --> 00:41:12,720
但是，從理論上講，它不能從根本上
所有的更快。

934
00:41:12,720 --> 00:41:16,040
>> 因此，我們不似乎是所有的東西
接近本聖杯。

935
00:41:16,040 --> 00:41:17,750
事實上，這僅僅是線性時間。

936
00:41:17,750 --> 00:41:20,790
哎呀，在這一點上，為什麼我們不
只使用一個巨大的鍊錶？

937
00:41:20,790 --> 00:41:23,510
為什麼我們不只是用一個巨大的
數組來存儲的名稱

938
00:41:23,510 --> 00:41:25,010
每個人都在房間裡嗎？

939
00:41:25,010 --> 00:41:28,280
嗯，還有東西
引人注目的一個哈希表？

940
00:41:28,280 --> 00:41:30,810
還有一些引人注目的
關於數據結構的

941
00:41:30,810 --> 00:41:33,940
看起來像這樣嗎？

942
00:41:33,940 --> 00:41:35,182
此。

943
00:41:35,182 --> 00:41:37,050
>> 學生：[聽不清]。

944
00:41:37,050 --> 00:41:39,840
>> 揚聲器1：右鍵，並再次，如果它只是
一個線性時間算法，並有

945
00:41:39,840 --> 00:41:42,780
線性時間的數據結構，我為什麼不
只是在一個大的存儲每個人的名字

946
00:41:42,780 --> 00:41:44,210
陣列，或在一個大的鍊錶？

947
00:41:44,210 --> 00:41:47,010
停止CS這麼更難
比它需要的嗎？

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
什麼是引人注目的，甚至
雖然我劃出來？

950
00:41:53,190 --> 00:41:54,930
>> 學生：[聽不清]。

951
00:41:54,930 --> 00:41:57,040
>> 揚聲器1：插入都沒有？

952
00:41:57,040 --> 00:41:58,140
昂貴了。

953
00:41:58,140 --> 00:42:03,390
因此，插入可能仍然
時間是恆定的，即使你的數據

954
00:42:03,390 --> 00:42:07,910
結構看起來是這樣的，琳瑯滿目的
指針，其中每個指向

955
00:42:07,910 --> 00:42:09,550
潛在的鍊錶。

956
00:42:09,550 --> 00:42:15,220
你怎麼能實現恆
時間插入的名字？

957
00:42:15,220 --> 00:42:16,280
把它貼在了前面，對不對？

958
00:42:16,280 --> 00:42:19,290
>> 如果我們犧牲一個設計目標
所說，我們希望保持

959
00:42:19,290 --> 00:42:22,650
每個人的名字，例如，排序，
舞台上所有的數字排序，

960
00:42:22,650 --> 00:42:25,020
假設我們有一個
未分類的鍊錶。

961
00:42:25,020 --> 00:42:29,960
我們只需花費一個或兩個步驟，
像Ben和布萊恩的情況下

962
00:42:29,960 --> 00:42:32,750
早些時候，插入一個元素
在列表的開頭。

963
00:42:32,750 --> 00:42:36,090
因此，如果我們不關心排序的所有
開頭的名字或全部

964
00:42:36,090 --> 00:42:39,660
以B開頭的名字，我們仍然可以
實現恆定的時間插入。

965
00:42:39,660 --> 00:42:43,900
現在回頭Alice或Bob或任何名稱
更普遍的仍是什麼？

966
00:42:43,900 --> 00:42:48,100
大O的n除以26，在
理想情況下，每個人的均勻

967
00:42:48,100 --> 00:42:51,190
分佈，其中有盡可能多的
有Z的，這可能是

968
00:42:51,190 --> 00:42:52,220
不現實的。

969
00:42:52,220 --> 00:42:53,880
但是，這仍然是線性的。

970
00:42:53,880 --> 00:42:57,120
>> 但在這裡，我們再回過頭來點
漸近符號

971
00:42:57,120 --> 00:42:58,600
理論上確實如此。

972
00:42:58,600 --> 00:43:02,960
但在現實世界中，如果我要求
我的程序可以做一些26倍

973
00:43:02,960 --> 00:43:06,210
速度比你的，其程序
你要喜歡使用？

974
00:43:06,210 --> 00:43:09,660
你的還是我，
快26倍？

975
00:43:09,660 --> 00:43:14,320
實際上，人是26
倍的速度，即使在理論上

976
00:43:14,320 --> 00:43:18,790
我們的算法運行在相同的
漸近運行時間。

977
00:43:18,790 --> 00:43:20,940
>> 讓我提出一個不同的
完全的解決方案。

978
00:43:20,940 --> 00:43:24,380
如果這不吹你的頭腦，
我們的數據結構。

979
00:43:24,380 --> 00:43:27,420
因此，這是特里 - 

980
00:43:27,420 --> 00:43:28,520
樣的一個愚蠢的名字。

981
00:43:28,520 --> 00:43:32,880
它來自檢索，字
拼寫特里，T-R-I-E，因為

982
00:43:32,880 --> 00:43:34,450
當然檢索聽起來像特里。

983
00:43:34,450 --> 00:43:36,580
但是，這是歷史
的特里字。

984
00:43:36,580 --> 00:43:40,980
>> 因此，一個特里確實是某種樹，
它也是一上場就那個字。

985
00:43:40,980 --> 00:43:46,330
即使你可以不太看到它
這個可視化，特里是一個

986
00:43:46,330 --> 00:43:50,790
樹結構，就像一個家庭樹
在頂部和意見的一個祖先

987
00:43:50,790 --> 00:43:54,530
孫子和重孫
離開底部。

988
00:43:54,530 --> 00:43:58,100
但特里在每個節點是一個數組。

989
00:43:58,100 --> 00:44:00,680
，它是在一個數組 - 讓
過於簡單化了一會兒 - 這是一個

990
00:44:00,680 --> 00:44:04,600
陣列，在這種情況下，大小為26，其中
每個節點是數組的大小為

991
00:44:04,600 --> 00:44:09,000
26的方法，其中在第零個元素
數組代表A，最後

992
00:44:09,000 --> 00:44:11,810
在每個這樣的元素
數組代表Z。

993
00:44:11,810 --> 00:44:15,520
>> 所以，我建議，那麼，這個數據
結構，稱為一個特里，可

994
00:44:15,520 --> 00:44:17,600
也用於存儲字。

995
00:44:17,600 --> 00:44:21,740
我們剛才也看到了，我們如何能夠存儲
的話，在這種情況下，名稱，這樣我們

996
00:44:21,740 --> 00:44:25,440
前面所看到的，我們如何能夠存儲數字，
但如果我們專注於名或字符串

997
00:44:25,440 --> 00:44:27,460
這裡，發現什麼有趣的。

998
00:44:27,460 --> 00:44:32,210
我要求麥克斯韋的名字是
內的這樣的數據結構。

999
00:44:32,210 --> 00:44:33,730
你在哪裡看到麥克斯韋？

1000
00:44:33,730 --> 00:44:35,140
>> 學生：[聽不清]。

1001
00:44:35,140 --> 00:44:36,240
>> 揚聲器1：在左邊。

1002
00:44:36,240 --> 00:44:39,910
那麼，有什麼有趣的與此數據
而不是存儲結構

1003
00:44:39,910 --> 00:44:46,200
串M-à-X-W-E-L-L反斜杠零，所有的
連續，就是你，而不是做

1004
00:44:46,200 --> 00:44:46,890
以下。

1005
00:44:46,890 --> 00:44:50,510
如果這是一個類似的數據結構的線索，
的每個節點又是一個數組，

1006
00:44:50,510 --> 00:44:54,650
，你想，你先存儲麥克斯韋
指數和根的節點，所以

1007
00:44:54,650 --> 00:44:57,810
說話，最上面的節點，
右，所以在位置M，

1008
00:44:57,810 --> 00:44:59,160
大致可分為中間。

1009
00:44:59,160 --> 00:45:03,740
然後從那裡，你遵循
一個子節點的指針，可以這麼說。

1010
00:45:03,740 --> 00:45:06,150
所以家譜感，
你跟著它向下。

1011
00:45:06,150 --> 00:45:09,030
導致你到另一個節點
左邊有，這是

1012
00:45:09,030 --> 00:45:10,540
只是另一個數組。

1013
00:45:10,540 --> 00:45:14,710
>> 然後，如果你想存儲麥克斯韋，
你找到指針，表示

1014
00:45:14,710 --> 00:45:16,430
A，這是此人在這裡。

1015
00:45:16,430 --> 00:45:17,840
然後你去到​​下一個節點。

1016
00:45:17,840 --> 00:45:20,100
和通知 - 這就是為什麼圖片的
有點自欺欺人 - 

1017
00:45:20,100 --> 00:45:21,990
這個節點看起來超級微小的。

1018
00:45:21,990 --> 00:45:26,050
但是，這樣做的權利是Y和Z。
這只是筆者已截斷

1019
00:45:26,050 --> 00:45:27,630
圖片，讓你實際上
看到的東西。

1020
00:45:27,630 --> 00:45:30,400
否則這幅畫
將是巨大的寬。

1021
00:45:30,400 --> 00:45:36,180
所以，現在你的索引位置X，然後
W，然後E，那麼L，L，然後有什麼

1022
00:45:36,180 --> 00:45:37,380
這種好奇心？

1023
00:45:37,380 --> 00:45:41,250
>> 那麼，如果我們正在使用這種新
採取有關如何存儲中的字符串

1024
00:45:41,250 --> 00:45:44,500
數據結構，你仍然需要
基本上在數據核對

1025
00:45:44,500 --> 00:45:47,250
結構詞語到此為止。

1026
00:45:47,250 --> 00:45:50,830
換句話說，這些節點中的每個節點
不知何故要記住，我們

1027
00:45:50,830 --> 00:45:53,500
後面其實所有這些指針
並留下一點點

1028
00:45:53,500 --> 00:45:58,370
麵包屑的底部，在這裡對本
結構示意M-à-X-W-E-L-L

1029
00:45:58,370 --> 00:46:00,230
確實這個數據結構中。

1030
00:46:00,230 --> 00:46:02,040
>> 因此，我們可能會做如下。

1031
00:46:02,040 --> 00:46:06,810
我們只是在圖片中的每一個節點
鋸有一個大小為27的數組。

1032
00:46:06,810 --> 00:46:10,550
它現在27，因為在p設置6個，
實際上，我們就會給你一個撇號，

1033
00:46:10,550 --> 00:46:13,590
所以我們可以有名稱，如奧賴利
和其他帶撇號。

1034
00:46:13,590 --> 00:46:14,820
但同樣的想法。

1035
00:46:14,820 --> 00:46:17,710
在這些元素
陣列指向一個struct

1036
00:46:17,710 --> 00:46:19,320
節點，所以只是一個節點。

1037
00:46:19,320 --> 00:46:21,430
因此，這很容易讓人想起
我們的鍊錶。

1038
00:46:21,430 --> 00:46:24,550
>> 然後我有一個布爾值，我將
致電字，這是只是要

1039
00:46:24,550 --> 00:46:29,120
如此，如果一個詞結束
樹中的節點。

1040
00:46:29,120 --> 00:46:32,870
它有效地代表小
三角形，我們剛才也看到了。

1041
00:46:32,870 --> 00:46:37,190
因此，如果有一個字在該節點處結束
樹，那田字是真實的，

1042
00:46:37,190 --> 00:46:41,990
在概念上被檢查過，或
我們繪製這個三角形，是有

1043
00:46:41,990 --> 00:46:44,080
這裡是一個字。

1044
00:46:44,080 --> 00:46:45,120
>> 所以這是一個特里。

1045
00:46:45,120 --> 00:46:48,540
現在的問題是，什麼
是它的運行時間？

1046
00:46:48,540 --> 00:46:49,930
它是大O的n？

1047
00:46:49,930 --> 00:46:51,410
是別的原因呢？

1048
00:46:51,410 --> 00:46:57,330
好吧，如果你有n個名字，在此數據
結構，麥克斯韋只是其中之一

1049
00:46:57,330 --> 00:47:02,330
他們，什麼是運行時間
插入或找到馬克斯韋爾？

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
什麼是運行時間
插入麥克斯韋？

1052
00:47:09,050 --> 00:47:11,740
如果有n其他名稱
已經在表中？

1053
00:47:11,740 --> 00:47:12,507
是嗎？

1054
00:47:12,507 --> 00:47:15,429
>> 學生：[聽不清]。

1055
00:47:15,429 --> 00:47:17,550
>> 揚聲器1：是的，它的長度
的名字，對不對？

1056
00:47:17,550 --> 00:47:24,420
所以M-A-X-W-E-L-L，所以這樣的感覺
算法是大O七。

1057
00:47:24,420 --> 00:47:26,580
現在，當然，該名稱
將長短不一。

1058
00:47:26,580 --> 00:47:27,380
也許這是一個簡短的名稱。

1059
00:47:27,380 --> 00:47:28,600
也許這是一個較長的名稱。

1060
00:47:28,600 --> 00:47:33,390
但這裡的關鍵是，
這是一個常數。

1061
00:47:33,390 --> 00:47:36,810
也許這不是真的不變，
不過神來，如果實事求是，在

1062
00:47:36,810 --> 00:47:41,570
字典裡，可能有一些限制
中的字母的數目

1063
00:47:41,570 --> 00:47:43,820
在某個特定國家的人的名字。

1064
00:47:43,820 --> 00:47:46,940
>> 因此，我們可以假設，
值是一個常數。

1065
00:47:46,940 --> 00:47:47,750
我不知道它是什麼。

1066
00:47:47,750 --> 00:47:50,440
這也可能是大於
我們認為它是。

1067
00:47:50,440 --> 00:47:52,720
因為總有一些角落
一個瘋狂的長名稱的情況。

1068
00:47:52,720 --> 00:47:56,360
因此，讓我們叫它K表，但它仍然是一個
常數，大概，因為每一個

1069
00:47:56,360 --> 00:48:00,190
命名在世界上，至少在
特定的國家，該長度或

1070
00:48:00,190 --> 00:48:01,780
短，所以它是恆定的。

1071
00:48:01,780 --> 00:48:04,490
但是，當我們已經說了一句大
O的一個恆定值，那是什麼

1072
00:48:04,490 --> 00:48:07,760
真的等同嗎？

1073
00:48:07,760 --> 00:48:10,420
這真的是同一件事
說恆定的時間。

1074
00:48:10,420 --> 00:48:11,530
>> 現在，我們是一種欺騙，對吧？

1075
00:48:11,530 --> 00:48:15,340
我們利用一些理論
這裡要說的是，訂單的k

1076
00:48:15,340 --> 00:48:17,450
真的只是為了一個，
和它的持續時間。

1077
00:48:17,450 --> 00:48:18,200
但它確實是。

1078
00:48:18,200 --> 00:48:22,550
因為這裡的關鍵洞察力是
如果我們有n個名字已經在這

1079
00:48:22,550 --> 00:48:26,010
數據結構，我們插入麥克斯韋
是需要我們的時間量

1080
00:48:26,010 --> 00:48:29,530
在所有受影響的插入麥克斯韋
有多少人

1081
00:48:29,530 --> 00:48:31,100
在數據結構中？

1082
00:48:31,100 --> 00:48:31,670
似乎不。

1083
00:48:31,670 --> 00:48:36,280
如果我有一個10億多元素
特里，然後插入麥克斯韋，

1084
00:48:36,280 --> 00:48:38,650
他在所有受影響？

1085
00:48:38,650 --> 00:48:39,050
號

1086
00:48:39,050 --> 00:48:42,950
而這不同於任何一天的數據
結構到目前為止，我們已經看到，其中

1087
00:48:42,950 --> 00:48:46,820
你的算法的運行時間是
完全獨立的多少

1088
00:48:46,820 --> 00:48:51,430
東西已經是或不是
在該數據結構中。

1089
00:48:51,430 --> 00:48:54,650
>> 因此，與這提供了你現在是一個
機會對p六集，這將

1090
00:48:54,650 --> 00:48:58,310
再次涉及實施自己的
拼寫檢查器，讀入150,000

1091
00:48:58,310 --> 00:49:01,050
也就是說，如何最好地儲存，
不一定是顯而易見的。

1092
00:49:01,050 --> 00:49:04,030
雖然我渴望找到
聖杯，我不

1093
00:49:04,030 --> 00:49:05,330
聲稱，特里。

1094
00:49:05,330 --> 00:49:09,810
事實上，一個哈希表，很可能
被證明是更有效的。

1095
00:49:09,810 --> 00:49:10,830
但那些只是 - 

1096
00:49:10,830 --> 00:49:14,620
這只是一個設計決策
你將不得不作出。

1097
00:49:14,620 --> 00:49:18,920
>> 但在收盤讓我們50歲左右
秒採取偷看是什麼樣的

1098
00:49:18,920 --> 00:49:22,190
下週提前超出了我們的過渡
從這個命令行

1099
00:49:22,190 --> 00:49:26,220
世界上，如果C程序網絡的事情
基於語言，如PHP，

1100
00:49:26,220 --> 00:49:30,350
JavaScript和互聯網本身，
協議，如HTTP，你

1101
00:49:30,350 --> 00:49:32,870
理所當然的多年
現在，類型最

1102
00:49:32,870 --> 00:49:34,440
一天，也許，或可見一斑。

1103
00:49:34,440 --> 00:49:37,420
我們將開始剝開
層是什麼是互聯網。

1104
00:49:37,420 --> 00:49:40,650
什麼是代碼，
今天的基礎工具。

1105
00:49:40,650 --> 00:49:43,230
所以，50秒這個傳情。

1106
00:49:43,230 --> 00:49:46,570
我給你的淨勇士。

1107
00:49:46,570 --> 00:49:51,370
>> [視頻回放]

1108
00:49:51,370 --> 00:49:56,764
>> 他帶來一個消息。

1109
00:49:56,764 --> 00:50:00,687
有了自己的協議。

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
他來到世界殘忍防火牆，
漠不關心的路由器和危險遠

1112
00:50:19,780 --> 00:50:22,600
比死亡更糟糕。

1113
00:50:22,600 --> 00:50:23,590
他的速度快。

1114
00:50:23,590 --> 00:50:25,300
他很強壯。

1115
00:50:25,300 --> 00:50:27,700
他的TCPIP。

1116
00:50:27,700 --> 00:50:30,420
他有你的地址。

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
勇士淨。

1119
00:50:34,590 --> 00:50:35,290
>> [END視頻播放]

1120
00:50:35,290 --> 00:50:38,070
>> 揚聲器1：這是如何在互聯網上
應下週工作。

1121
00:50:38,070 --> 00:50:40,406