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

2
00:00:00,500 --> 00:00:11,137
[音樂播放]

3
00:00:11,137 --> 00:00:12,220
戴維·J·馬蘭：好吧。

4
00:00:12,220 --> 00:00:13,950
這是CS50。

5
00:00:13,950 --> 00:00:18,560
這是本週五繼續進行，我們
有一些好消息和一些壞消息。

6
00:00:18,560 --> 00:00:21,140
好消息是，CS50
推出這個星期五​​。

7
00:00:21,140 --> 00:00:24,430
如果您想加入我們的行列，
前往這裡平時的網址。

8
00:00:24,430 --> 00:00:28,670
更好的消息，沒有演講
下星期一13日。

9
00:00:28,670 --> 00:00:31,970
略顯不足更好的消息，
測驗零點下週三。

10
00:00:31,970 --> 00:00:33,840
更多細節可
在這個網址找到這裡。

11
00:00:33,840 --> 00:00:36,340
而在接下來的幾天
我們將填補空白

12
00:00:36,340 --> 00:00:39,234
與問候房間
我們將有保留。

13
00:00:39,234 --> 00:00:41,400
更好的消息是，有將
是一個過程性的檢討

14
00:00:41,400 --> 00:00:43,570
會議即將來臨
週一晚上。

15
00:00:43,570 --> 00:00:46,270
敬請關注過程的
網站的定位和細節。

16
00:00:46,270 --> 00:00:49,290
部分，即使它是一個
假期，也將滿足為好。

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
最好的消息，講課下週五。

19
00:00:52,940 --> 00:00:56,220
因此，這是一個傳統，我們
有，按照教學大綱。

20
00:00:56,220 --> 00:00:58,100
只是 - 這將是驚人的。

21
00:00:58,100 --> 00:01:02,510
你會看到類似的東西
固定時間的數據結構

22
00:01:02,510 --> 00:01:04,730
和哈希表和樹和嘗試。

23
00:01:04,730 --> 00:01:07,150
我們將談論的生日問題。

24
00:01:07,150 --> 00:01:09,440
一大堆的東西
等待下週五。

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
行。

27
00:01:12,200 --> 00:01:13,190
總之。

28
00:01:13,190 --> 00:01:17,080
>> 所以，記得，我們​​已經
重點是這幅畫的是什麼

29
00:01:17,080 --> 00:01:18,980
我們內部的計算機內存。

30
00:01:18,980 --> 00:01:22,875
這樣存儲器或RAM是其中的程序
你正在運行他們，而存在的。

31
00:01:22,875 --> 00:01:25,215
如果你雙擊一個
圖標來運行一些程序

32
00:01:25,215 --> 00:01:27,520
或雙擊
圖標打開某些文件，

33
00:01:27,520 --> 00:01:30,430
它是從硬盤加載
驅動器或固態驅動器

34
00:01:30,430 --> 00:01:34,190
到RAM中，隨機存取存儲器，其中
它生活，直到電源關閉，

35
00:01:34,190 --> 00:01:36,700
筆記本電腦的蓋子關閉，
或者你退出程序。

36
00:01:36,700 --> 00:01:38,960
>> 現在，記憶，
你可能有

37
00:01:38,960 --> 00:01:41,950
1 GB的這些天，2
千兆字節，甚至更多，

38
00:01:41,950 --> 00:01:44,420
一般佈局
對於一個給定的程序

39
00:01:44,420 --> 00:01:47,170
在這種長方形的
概念模型

40
00:01:47,170 --> 00:01:50,860
由此我們有堆疊在底部
並在頂部一堆其他的東西。

41
00:01:50,860 --> 00:01:53,140
在最高層的事
我們已經看到這個畫面

42
00:01:53,140 --> 00:01:55,670
之前，但從來沒有說過
是所謂的文本段。

43
00:01:55,670 --> 00:01:58,419
文段僅僅是一個奇特的方式
的話說，零和一的

44
00:01:58,419 --> 00:02:01,150
撰寫您的實際編譯的程序。

45
00:02:01,150 --> 00:02:03,910
>> 所以，當你雙擊
微軟的Word在您的Mac或PC，

46
00:02:03,910 --> 00:02:08,030
或者當您運行點斜線馬里奧在
Linux計算機在終端窗口中，

47
00:02:08,030 --> 00:02:12,460
構成該零和一
字或馬里奧被暫時存儲

48
00:02:12,460 --> 00:02:16,610
在所謂的計算機的RAM
文本段對特定的程序。

49
00:02:16,610 --> 00:02:19,080
下面說去初始化
和未初始化的數據。

50
00:02:19,080 --> 00:02:22,655
這東西像全局變量，
我們已經不能用了許多，

51
00:02:22,655 --> 00:02:24,910
但有時，我們已經
有全局變量

52
00:02:24,910 --> 00:02:28,819
或靜態定義的字符串
是硬編碼，如“你好”的話

53
00:02:28,819 --> 00:02:31,860
未從用戶採取
被硬編碼到程序中。

54
00:02:31,860 --> 00:02:34,230
>> 現在，倒在底部我們
有所謂的堆棧。

55
00:02:34,230 --> 00:02:37,665
和棧，迄今為止，我們已經
採用了什麼樣的目的？

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
什麼是棧被用來做什麼？

58
00:02:40,997 --> 00:02:41,160
是嗎？

59
00:02:41,160 --> 00:02:42,070
>> 聽眾：功能。

60
00:02:42,070 --> 00:02:43,320
>> 戴維·J·馬蘭：功能？

61
00:02:43,320 --> 00:02:44,980
在什麼意義上的功能呢？

62
00:02:44,980 --> 00:02:48,660
>> 聽眾：當你調用一個函數時，
參數複製到堆棧中。

63
00:02:48,660 --> 00:02:49,660
>> 戴維·J·馬蘭：沒錯。

64
00:02:49,660 --> 00:02:52,650
當你調用一個函數，它的
參數複製到堆棧中。

65
00:02:52,650 --> 00:02:56,330
因此，某X的或Y的或A或B的
那你傳遞給函數

66
00:02:56,330 --> 00:02:58,680
暫時放在
所謂堆棧，

67
00:02:58,680 --> 00:03:02,000
就像安尼伯格之一
食堂托盤，也事

68
00:03:02,000 --> 00:03:03,190
如局部變量。

69
00:03:03,190 --> 00:03:06,290
如果你的富功能或您的交換
函數有局部變量，

70
00:03:06,290 --> 00:03:08,602
如溫度，這兩個
最終在堆棧中。

71
00:03:08,602 --> 00:03:11,560
現在，我們不會過多談論
他們，但這些環境變量

72
00:03:11,560 --> 00:03:15,690
在底部，我們看到前一段時間，當
我把玩在鍵盤1天

73
00:03:15,690 --> 00:03:20,050
我開始訪問事
像argv的100 ARGV 1,000

74
00:03:20,050 --> 00:03:22,320
只是elements--我忘了
在numbers--但

75
00:03:22,320 --> 00:03:24,330
不應該由我來訪問。

76
00:03:24,330 --> 00:03:26,581
我們開始看到一些
時髦的符號在屏幕上。

77
00:03:26,581 --> 00:03:28,330
這些都是所謂的
環境變量

78
00:03:28,330 --> 00:03:32,390
像全局設置我的
程序或我的電腦，而不是

79
00:03:32,390 --> 00:03:37,090
無關的最近
錯誤，我們所討論的，

80
00:03:37,090 --> 00:03:39,670
Shellshock，這一直
困擾著不少電腦。

81
00:03:39,670 --> 00:03:42,960
>> 現在，最後，在今天的重點
我們最終會在堆中。

82
00:03:42,960 --> 00:03:44,864
這是記憶另一個塊。

83
00:03:44,864 --> 00:03:47,030
從根本上這一切
內存是同樣的東西。

84
00:03:47,030 --> 00:03:48,040
這是同樣的硬件。

85
00:03:48,040 --> 00:03:49,956
我們只是有點
對待不同的集群

86
00:03:49,956 --> 00:03:51,460
的字節用於不同的目的。

87
00:03:51,460 --> 00:03:56,540
堆也將會是在哪裡
您請求的變量和內存

88
00:03:56,540 --> 00:03:58,810
從操作系統
被暫時存儲。

89
00:03:58,810 --> 00:04:01,890
>> 但有樣的問題
這裡，作為圖像暗示。

90
00:04:01,890 --> 00:04:05,261
我們的排序有兩個
關於船舶碰撞。

91
00:04:05,261 --> 00:04:08,010
因為當你使用越來越多
堆棧，並作為我們今天看到的

92
00:04:08,010 --> 00:04:11,800
以後，當你使用更多的多
堆，肯定不好的事情可能會發生。

93
00:04:11,800 --> 00:04:15,054
事實上，我們可以歸納出
有意或無意的。

94
00:04:15,054 --> 00:04:16,970
所以最後扣人心弦
時間是這個程序，

95
00:04:16,970 --> 00:04:20,570
這並沒有起到任何功能
目的除了展示

96
00:04:20,570 --> 00:04:24,750
如何為壞傢伙竟然可以
利用漏洞在別人的程序

97
00:04:24,750 --> 00:04:28,460
並接管程序，甚至是
整個計算機系統或服務器。

98
00:04:28,460 --> 00:04:31,660
所以只是簡單地一瞥，你
請注意，主底部

99
00:04:31,660 --> 00:04:34,510
需要在命令行
參數，按ARGV。

100
00:04:34,510 --> 00:04:38,480
它有一個調用一個函數f，
基本上叫做匿名函數

101
00:04:38,480 --> 00:04:40,250
f和它傳遞的argv [1]。

102
00:04:40,250 --> 00:04:43,960
>> 因此，在任何字的用戶類型
這個節目的名字後，在提示，

103
00:04:43,960 --> 00:04:49,310
然後這個任意函數了
頂，F，需要一個字符串，又名char *的，

104
00:04:49,310 --> 00:04:51,720
因為我們已經開始討論，
它只是將其稱為“巴”。

105
00:04:51,720 --> 00:04:53,310
但我們可以把它叫做什麼。

106
00:04:53,310 --> 00:04:57,470
然後它聲明，裡面
樓字符數組的

107
00:04:57,470 --> 00:04:59,930
所謂C-- 12這樣的人物。

108
00:04:59,930 --> 00:05:03,580
>> 現在，這個故事我告訴
剛才，在內存

109
00:05:03,580 --> 00:05:06,720
為c，或者是那些12
字符要結束了？

110
00:05:06,720 --> 00:05:07,570
只是要清楚。

111
00:05:07,570 --> 00:05:08,070
是嗎？

112
00:05:08,070 --> 00:05:08,590
>> 聽眾：在堆棧中。

113
00:05:08,590 --> 00:05:09,420
>> 戴維·J·馬蘭：在堆棧中。

114
00:05:09,420 --> 00:05:10,720
所以C是一個局部變量。

115
00:05:10,720 --> 00:05:14,079
我們要求12個字符或12個字節。

116
00:05:14,079 --> 00:05:16,120
那些將要結束了
在所謂的堆棧。

117
00:05:16,120 --> 00:05:18,530
現在終於這等功能
這實際上是相當有用的，

118
00:05:18,530 --> 00:05:20,571
但我們還沒有真正使用
它自己，strncopy。

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
這意味著字符串拷貝，但
n只有字母，n個字符。

121
00:05:25,200 --> 00:05:31,990
因此，n個字符會
從酒吧複製成C。

122
00:05:31,990 --> 00:05:32,980
又有多少呢？

123
00:05:32,980 --> 00:05:34,110
條的長度。

124
00:05:34,110 --> 00:05:36,330
因此，換句話說，即
一條線，strncopy，

125
00:05:36,330 --> 00:05:39,500
將要複製
在有效的禁止到c。

126
00:05:39,500 --> 00:05:42,340
>> 現在，只是一種預測
這個故事的寓意，

127
00:05:42,340 --> 00:05:44,750
什麼是潛在的問題在這裡嗎？

128
00:05:44,750 --> 00:05:49,710
儘管我們正在檢查的長度
酒吧，並向其傳遞到strncopy，

129
00:05:49,710 --> 00:05:53,145
什麼是你的直覺告訴你的是
還是打破這個計劃？

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
是嗎？

132
00:05:55,220 --> 00:05:57,491
>> 聽眾：不包括
房間空字符。

133
00:05:57,491 --> 00:05:59,990
戴維·J·馬蘭：不包括
房間空字符。

134
00:05:59,990 --> 00:06:02,073
潛在地，不像在
過去的實踐中，我們甚至不

135
00:06:02,073 --> 00:06:04,810
有這麼多的加1
容納空字符。

136
00:06:04,810 --> 00:06:06,649
但比這更糟糕。

137
00:06:06,649 --> 00:06:07,940
還有什麼是我們不能做什麼？

138
00:06:07,940 --> 00:06:08,432
是嗎？

139
00:06:08,432 --> 00:06:09,307
>> 聽眾：[聽不清]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
戴維·J·馬蘭：完美。

142
00:06:16,440 --> 00:06:18,490
我們已經硬編碼的12相當隨意。

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
這是沒有這麼多的
的問題，但事實

145
00:06:21,330 --> 00:06:25,630
我們甚至不檢查，如果
條的長度是小於12，

146
00:06:25,630 --> 00:06:28,530
在這種情況下，這將是
安全地把它放入內存

147
00:06:28,530 --> 00:06:30,260
我們已經分配名為c。

148
00:06:30,260 --> 00:06:32,960
事實上，如果酒吧是像
20個字符長，

149
00:06:32,960 --> 00:06:39,010
這個功能似乎被複製
從酒吧到C，使20個字符

150
00:06:39,010 --> 00:06:41,310
服用至少8個字節
它不應該。

151
00:06:41,310 --> 00:06:42,690
這是這裡的含義。

152
00:06:42,690 --> 00:06:44,347
>> 因此，在短期，斷程序。

153
00:06:44,347 --> 00:06:45,180
沒有什麼大不了的。

154
00:06:45,180 --> 00:06:46,360
也許你會得到一個段錯誤。

155
00:06:46,360 --> 00:06:47,651
我們都有過在程序中的bug。

156
00:06:47,651 --> 00:06:50,196
我們都可能有缺陷
在節目現在。

157
00:06:50,196 --> 00:06:51,320
但是，有什麼寓意？

158
00:06:51,320 --> 00:06:54,390
嗯，這裡是一個放大版本
那張照片是我的電腦的內存中。

159
00:06:54,390 --> 00:06:56,230
這是我的堆棧的底部。

160
00:06:56,230 --> 00:06:59,644
事實上，在最底層是什麼
所謂的母常規堆棧，奇特的方式

161
00:06:59,644 --> 00:07:00,560
的話說，就是主。

162
00:07:00,560 --> 00:07:03,772
所以，無論誰調用的函數
˚F，我們正在談論的。

163
00:07:03,772 --> 00:07:05,230
所以這是堆棧的底部。

164
00:07:05,230 --> 00:07:06,640
返回地址是新的東西。

165
00:07:06,640 --> 00:07:08,810
這是一直存在的，
一直在圖片。

166
00:07:08,810 --> 00:07:10,440
我們只是從來沒有所謂的重視。

167
00:07:10,440 --> 00:07:15,290
因為事實證明，C工作的方式是
當一個函數調用另一個，

168
00:07:15,290 --> 00:07:18,780
不僅做到了參數的
功能得到壓入堆棧，

169
00:07:18,780 --> 00:07:22,470
不僅做到了功能的地方
得到的變量壓入堆棧，

170
00:07:22,470 --> 00:07:26,820
一些所謂的返回地址
也被放到堆棧。

171
00:07:26,820 --> 00:07:33,330
特別是，如果主調用foo，主要的
自己的地址在內存中，牛事，

172
00:07:33,330 --> 00:07:38,240
有效地被放置到堆棧
這樣，當f為完成執行它

173
00:07:38,240 --> 00:07:43,630
知道在哪裡可以跳回到文本
段，以繼續執行。

174
00:07:43,630 --> 00:07:47,760
>> 所以，如果我們在這裡概念，
在主，則f被調用。

175
00:07:47,760 --> 00:07:50,200
如何˚F知道是誰
以手控回來？

176
00:07:50,200 --> 00:07:52,020
好了，這個小
麵包屑紅色在這裡，

177
00:07:52,020 --> 00:07:54,978
所謂的返回地址，這只是
支票，那是什麼的返回地址？

178
00:07:54,978 --> 00:07:57,039
哦，讓我跳回到主這裡。

179
00:07:57,039 --> 00:07:59,080
這就是一點點
過於簡單化的，

180
00:07:59,080 --> 00:08:00,750
因為在零和一
主在技術上

181
00:08:00,750 --> 00:08:01,967
在這裡，在高科技領域。

182
00:08:01,967 --> 00:08:03,800
但是，這是這個想法。 ˚F
只是必須知道什麼

183
00:08:03,800 --> 00:08:06,680
到控制，最終又回到。

184
00:08:06,680 --> 00:08:09,790
>> 但是，電腦的方式
早就奠定了東西

185
00:08:09,790 --> 00:08:12,320
如局部變量和
論點是這樣的。

186
00:08:12,320 --> 00:08:17,180
所以，在這張照片中名列前茅
藍色是在f的棧幀，因此所有

187
00:08:17,180 --> 00:08:19,630
存儲器的使f
特別是使用。

188
00:08:19,630 --> 00:08:22,990
所以因此，請注意
酒吧是在這張照片。

189
00:08:22,990 --> 00:08:23,980
酒吧是它的參數。

190
00:08:23,980 --> 00:08:27,240
我們宣稱的參數
功能得到壓入堆棧。

191
00:08:27,240 --> 00:08:29,910
和c，當然是
同時在這張照片。

192
00:08:29,910 --> 00:08:33,520
>> 而就在符號上的目的，
注意在頂部左上角

193
00:08:33,520 --> 00:08:37,020
是會什麼C支架0
隨後小幅回落向右

194
00:08:37,020 --> 00:08:38,220
為c支架11。

195
00:08:38,220 --> 00:08:41,240
所以，換句話說，你可以想像
這有一個字節格

196
00:08:41,240 --> 00:08:44,380
還有，第一個是
左上角，底部其中

197
00:08:44,380 --> 00:08:48,360
是最後的這12個字節。

198
00:08:48,360 --> 00:08:49,930
>> 但現在盡量快進。

199
00:08:49,930 --> 00:08:55,580
什麼是即將發生，如果我們通過
在一個字符串中的酒吧，是比C更久？

200
00:08:55,580 --> 00:08:59,130
而且我們不是，如果檢查
這的確是超過12。

201
00:08:59,130 --> 00:09:03,146
此圖片的一部分是要
得到由字節0，1，2，3覆蓋，

202
00:09:03,146 --> 00:09:07,890
點點點，11，然後
糟糕，12，13至19？

203
00:09:07,890 --> 00:09:11,820
什麼會發生在這裡，
如果從訂貨推斷

204
00:09:11,820 --> 00:09:14,790
將c支架0頂部
和c支架11是有點下降

205
00:09:14,790 --> 00:09:15,812
對吧？

206
00:09:15,812 --> 00:09:16,796
是嗎？

207
00:09:16,796 --> 00:09:19,260
>> 聽眾：嗯，這是怎麼回事
覆蓋char *的吧。

208
00:09:19,260 --> 00:09:22,260
>> 戴維·J·馬蘭：是的，它看起來像
你要覆蓋char *的吧。

209
00:09:22,260 --> 00:09:26,245
更糟糕的是，如果你發送一個很長的
字符串，你甚至可以覆蓋哪些？

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
返回地址。

212
00:09:28,570 --> 00:09:31,380
這再次，就像是
麵包屑告訴程序在哪裡

213
00:09:31,380 --> 00:09:34,060
在f回去
完成被調用。

214
00:09:34,060 --> 00:09:37,140
>> 那麼，什麼壞人通常做
是，如果他們遇到一個程序

215
00:09:37,140 --> 00:09:41,290
他們很好奇是否
利用，越野車以這樣的方式

216
00:09:41,290 --> 00:09:43,550
他或她可以利用
優點是錯誤的，

217
00:09:43,550 --> 00:09:45,720
一般他們沒有得到
這種權利的第一次。

218
00:09:45,720 --> 00:09:48,590
他們剛開始發送，例如，
隨機字符串到你的程序，

219
00:09:48,590 --> 00:09:50,260
是否在鍵盤
或者坦白地說，他們可能

220
00:09:50,260 --> 00:09:52,740
寫一個小程序只是
自動生成的字符串，

221
00:09:52,740 --> 00:09:55,430
並開始通過敲打你的程序
派遣在許多不同的輸入

222
00:09:55,430 --> 00:09:56,340
在不同的長度。

223
00:09:56,340 --> 00:09:58,990
>> 只要你的程序崩潰，
這是一個了不起的事情。

224
00:09:58,990 --> 00:10:01,020
因為這意味著他
或她已經發現

225
00:10:01,020 --> 00:10:02,660
什麼是可能的確是一個錯誤。

226
00:10:02,660 --> 00:10:05,830
然後，他們可以得到更聰明
並開始關注更窄

227
00:10:05,830 --> 00:10:07,420
如何利用這個bug。

228
00:10:07,420 --> 00:10:11,480
特別是，他或她可能
要做的就是發送，在最好的情況下，你好。

229
00:10:11,480 --> 00:10:12,210
沒什麼大不了的。

230
00:10:12,210 --> 00:10:14,750
這是一個字符串，它是足夠短。

231
00:10:14,750 --> 00:10:18,100
但是，如果他或她送什麼，
我們將其概括為，

232
00:10:18,100 --> 00:10:20,890
攻擊代碼 - 讓零
而那些做的事情

233
00:10:20,890 --> 00:10:25,150
如RM-RF，即去除一切
從硬盤驅動器或發送垃圾郵件

234
00:10:25,150 --> 00:10:27,000
或以某種方式攻擊機？

235
00:10:27,000 --> 00:10:29,570
>> 因此，如果每個這些
字母A代表公正，

236
00:10:29,570 --> 00:10:32,380
從概念上講，攻擊，攻擊，
攻擊，攻擊，一些不好的代碼

237
00:10:32,380 --> 00:10:36,410
別人寫的，但
如果那人是足夠聰明

238
00:10:36,410 --> 00:10:40,790
不僅包括所有
那些RM-RFS的，但也

239
00:10:40,790 --> 00:10:46,100
有他或她的最後幾個字節
是一個數字，對應

240
00:10:46,100 --> 00:10:50,540
到的地址他
或她自己的攻擊代碼

241
00:10:50,540 --> 00:10:53,820
他（或她）在剛剛過去的
在提示符下提供的，

242
00:10:53,820 --> 00:10:58,760
可以有效地欺騙電腦
為在f執行完畢注意到，

243
00:10:58,760 --> 00:11:02,400
哦，是時候讓我跳
回紅返回地址。

244
00:11:02,400 --> 00:11:06,070
但是，因為他或她有莫名其妙
重疊的返回地址

245
00:11:06,070 --> 00:11:09,602
用自己的號碼，
而且他們足夠聰明

246
00:11:09,602 --> 00:11:11,560
已配置的
數量是指，當你

247
00:11:11,560 --> 00:11:13,740
看到超級頂
左上角有，

248
00:11:13,740 --> 00:11:18,020
在計算機的實際地址
他們的一些攻擊代碼的內存，

249
00:11:18,020 --> 00:11:21,740
壞人可以欺騙計算機
為執行他或她自己的代碼。

250
00:11:21,740 --> 00:11:23,700
>> 而這些代碼，再次可以是任何東西。

251
00:11:23,700 --> 00:11:26,120
它通常被稱為
shell代碼，這僅僅是

252
00:11:26,120 --> 00:11:29,030
的話說，這不是一個辦法
通常一些簡單的RM-RF。

253
00:11:29,030 --> 00:11:32,340
它實際上是這樣猛砸，
或實際的方案，讓他

254
00:11:32,340 --> 00:11:37,230
或她的程序控制執行
別的，他們想要。

255
00:11:37,230 --> 00:11:40,210
因此，在短期，這一切
從一個簡單的事實推導出

256
00:11:40,210 --> 00:11:44,490
這個錯誤不涉及檢查
陣列的界限。

257
00:11:44,490 --> 00:11:47,250
而由於道路
計算機工作，他們

258
00:11:47,250 --> 00:11:49,430
使用堆棧
有效的，在概念上，

259
00:11:49,430 --> 00:11:54,830
底上了，但隨後的元素
你推入堆棧增長自上而下，

260
00:11:54,830 --> 00:11:56,624
這是令人難以置信的問題。

261
00:11:56,624 --> 00:11:58,290
現在，有方法可以解決這個問題。

262
00:11:58,290 --> 00:12:00,800
坦率地說，有語言
與合作解決這個問題。

263
00:12:00,800 --> 00:12:03,100
Java是免疫，例如
這個特定問題。

264
00:12:03,100 --> 00:12:04,110
因為他們不給你指點。

265
00:12:04,110 --> 00:12:05,943
他們不給你
直接內存地址。

266
00:12:05,943 --> 00:12:08,560
因此，與這種力量，我們有
在內存按兵不動

267
00:12:08,560 --> 00:12:11,580
我們要來了，誠然，巨大的風險。

268
00:12:11,580 --> 00:12:12,430
>> 所以留意。

269
00:12:12,430 --> 00:12:14,596
如果坦率地說，在未來數月
或幾年來，隨時

270
00:12:14,596 --> 00:12:17,740
你讀一些開發
中，一個程序或服務器

271
00:12:17,740 --> 00:12:22,370
如果你曾經看到的東西的提示
就像一個緩衝區溢出攻擊，

272
00:12:22,370 --> 00:12:25,390
或堆棧溢出是另一種類型
攻擊中，在精神上同樣，

273
00:12:25,390 --> 00:12:28,770
就像激發網站的
名字，如果你知道的話，

274
00:12:28,770 --> 00:12:33,170
這一切都在談論剛剛
滿溢一些字符的大小

275
00:12:33,170 --> 00:12:36,200
數組或數組中更普遍。

276
00:12:36,200 --> 00:12:38,822
有任何疑問的話，在這？

277
00:12:38,822 --> 00:12:39,780
不要在家裡嘗試。

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> 好吧。

280
00:12:42,300 --> 00:12:47,270
所以malloc的迄今，我們的新
朋友，我們可以分配內存

281
00:12:47,270 --> 00:12:50,540
我們不一定知道在
前進，我們希望讓我們沒有

282
00:12:50,540 --> 00:12:52,920
硬編碼到我們的
程序號像12。

283
00:12:52,920 --> 00:12:55,550
一旦用戶告訴我們有多少
數據他或她想要輸入

284
00:12:55,550 --> 00:12:58,000
我們的malloc那麼多的記憶。

285
00:12:58,000 --> 00:13:01,484
>> 所以malloc的事實證明，在
程度上，我們一直在使用它，

286
00:13:01,484 --> 00:13:03,900
明確地一次，然後
你們一直在使用它

287
00:13:03,900 --> 00:13:08,160
為的GetString在不知不覺中進行
數週後，所有的malloc的內存的

288
00:13:08,160 --> 00:13:09,820
來自於所謂的堆。

289
00:13:09,820 --> 00:13:13,852
這就是為什麼GetString的，例如
可以動態地分配內存

290
00:13:13,852 --> 00:13:16,060
不知道你在做什麼
將預先輸入，

291
00:13:16,060 --> 00:13:21,520
交給你回一個指向內存中，
而且內存還是你留著，

292
00:13:21,520 --> 00:13:24,080
即使在形式返回。

293
00:13:24,080 --> 00:13:27,450
由於召回畢竟該
堆棧是不斷上升和下降，

294
00:13:27,450 --> 00:13:27,950
向上和向下。

295
00:13:27,950 --> 00:13:30,230
而一旦它進入
下，這意味著任何存儲器

296
00:13:30,230 --> 00:13:33,030
這個功能應該使用
不被其他人使用。

297
00:13:33,030 --> 00:13:34,570
這是垃圾值了。

298
00:13:34,570 --> 00:13:36,120
>> 不過，堆在這裡。

299
00:13:36,120 --> 00:13:39,360
這有什麼好看的malloc左右是
當這裡的malloc分配內存時，

300
00:13:39,360 --> 00:13:42,070
它沒有影響，對
大多數情況下，由堆棧。

301
00:13:42,070 --> 00:13:46,000
所以任何函數都可以訪問
內存已malloc分配，

302
00:13:46,000 --> 00:13:49,120
甚至像的GetString函數，
即使在它被返回。

303
00:13:49,120 --> 00:13:51,700
>> 現在，的malloc的逆是免費的。

304
00:13:51,700 --> 00:13:53,900
事實上，規則你
需要開始採用

305
00:13:53,900 --> 00:13:58,950
就是有，有，你用malloc任何時間
你必須自己使用免費的，最終，

306
00:13:58,950 --> 00:14:00,280
在同樣的指針。

307
00:14:00,280 --> 00:14:03,289
這段時間我們一直在寫
越野車，越野車的代碼，有很多原因。

308
00:14:03,289 --> 00:14:05,580
但其中一個已
使用CS50庫，

309
00:14:05,580 --> 00:14:09,010
本身是故意
越野車，它的內存洩漏。

310
00:14:09,010 --> 00:14:11,410
任何你打電話的GetString時間
在過去的幾個星期

311
00:14:11,410 --> 00:14:13,870
我們問工作
系統，Linux的內存。

312
00:14:13,870 --> 00:14:15,780
而你從來沒有一次給它回來。

313
00:14:15,780 --> 00:14:17,730
這不，在
練，是一件好事。

314
00:14:17,730 --> 00:14:20,330
>> 和Valgrind的，所述一個
在Pset的4引入的工具，

315
00:14:20,330 --> 00:14:22,900
是所有關於幫助您
現在發現這樣的錯誤。

316
00:14:22,900 --> 00:14:27,060
不過，值得慶幸的是在Pset的4你不需要
使用CS50庫或GetString的。

317
00:14:27,060 --> 00:14:31,220
所以涉及到內存中的任何錯誤都
最終將是你自己。

318
00:14:31,220 --> 00:14:34,060
>> 所以malloc的不僅僅是
方便的用於此目的。

319
00:14:34,060 --> 00:14:37,420
我們其實可以現在解決
從根本上不同的問題，

320
00:14:37,420 --> 00:14:41,640
從根本上解決問題，更
有效地為每週為零的承諾。

321
00:14:41,640 --> 00:14:44,720
到目前為止，這是最性感
數據結構，我們已經有。

322
00:14:44,720 --> 00:14:47,804
並通過數據結構我的意思
概念化記憶的一種方式

323
00:14:47,804 --> 00:14:50,720
在超越只是說一種方法，
這是一個int，這是一個字符。

324
00:14:50,720 --> 00:14:52,930
我們可以開始集群的東西放在一起。

325
00:14:52,930 --> 00:14:54,460
>> 所以數組是這樣的。

326
00:14:54,460 --> 00:14:57,270
什麼是對的關鍵
數組是可以讓你

327
00:14:57,270 --> 00:14:59,724
備份到後端的塊
存儲器，其中每個

328
00:14:59,724 --> 00:15:02,765
將是相同的類型，整型，
整型，整型，整型，或CHAR，CHAR，CHAR，

329
00:15:02,765 --> 00:15:03,330
字符。

330
00:15:03,330 --> 00:15:04,496
但是有幾個缺點。

331
00:15:04,496 --> 00:15:06,570
此，例如，是
大小6的陣列。

332
00:15:06,570 --> 00:15:10,650
假設你填充這個數組六
數字，然後，不管是什麼原因，

333
00:15:10,650 --> 00:15:13,187
您的用戶想要得到
你第七號。

334
00:15:13,187 --> 00:15:14,020
你在哪裡放呢？

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> 有什麼解決辦法，如果你有
在堆棧上創建一個數組，

337
00:15:18,990 --> 00:15:22,030
例如，剛與週
2符號，我們介紹了，

338
00:15:22,030 --> 00:15:23,730
方括號與多家裡面？

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
好了，你已經有了6
在這些框中的數字。

341
00:15:27,260 --> 00:15:28,530
什麼你的直覺是什麼？

342
00:15:28,530 --> 00:15:29,973
在那裡你會想要把它？

343
00:15:29,973 --> 00:15:30,860
>> 聽眾：[聽不清]

344
00:15:30,860 --> 00:15:31,315
>> 戴維·J·馬蘭：對不起？

345
00:15:31,315 --> 00:15:32,380
>> 聽眾：把它放在最後。

346
00:15:32,380 --> 00:15:33,796
>> 戴維·J·馬蘭：把它放在最後。

347
00:15:33,796 --> 00:15:35,880
所以才過來的吧，
這個盒子的外面。

348
00:15:35,880 --> 00:15:38,710
這將是很好的，但它
事實證明，你不能這樣做。

349
00:15:38,710 --> 00:15:41,350
因為如果你沒有問
此塊的存儲器，

350
00:15:41,350 --> 00:15:44,490
這可能是巧合，這
正在使用的一些其它變量

351
00:15:44,490 --> 00:15:45,030
乾脆。

352
00:15:45,030 --> 00:15:49,210
回想一個星期左右的時候，我們奠定
出Zamyla和達文和Gabe的名字

353
00:15:49,210 --> 00:15:49,930
在存儲器中。

354
00:15:49,930 --> 00:15:51,638
他們從字面上
回背靠背。

355
00:15:51,638 --> 00:15:53,550
所以我們可以不必
相信凡是

356
00:15:53,550 --> 00:15:55,800
在這裡是供我使用。

357
00:15:55,800 --> 00:15:56,990
>> 所以，你還有什麼可以做？

358
00:15:56,990 --> 00:16:00,282
那麼，一旦你實現
要7號的數組，

359
00:16:00,282 --> 00:16:02,490
你可以只創建一個
尺寸7的陣列，然後使用

360
00:16:02,490 --> 00:16:05,950
for循環或while循環，
將其複製到新的數組，

361
00:16:05,950 --> 00:16:09,680
然後不知何故剛剛擺脫
這個陣列或只是停止使用。

362
00:16:09,680 --> 00:16:12,130
但是，這不是特別有效。

363
00:16:12,130 --> 00:16:15,340
總之，陣列別讓
您動態調整。

364
00:16:15,340 --> 00:16:17,900
>> 因此，一方面你
隨機訪問，這是驚人的。

365
00:16:17,900 --> 00:16:20,108
因為它讓我們做的事情
如分而治之，

366
00:16:20,108 --> 00:16:23,100
二進制搜索，所有這些我們已經
就在屏幕上談到。

367
00:16:23,100 --> 00:16:24,950
但是你畫自己陷入了困境。

368
00:16:24,950 --> 00:16:27,810
只要你打
您的陣列的結尾，

369
00:16:27,810 --> 00:16:29,980
你要做的很
昂貴的操作

370
00:16:29,980 --> 00:16:33,910
或寫一大堆代碼
到現在處理這個問題。

371
00:16:33,910 --> 00:16:36,680
>> 所以，如果不是我們有什麼
一些所謂的名單，

372
00:16:36,680 --> 00:16:38,820
或鍊錶特別？

373
00:16:38,820 --> 00:16:41,930
有如果，而不是
矩形回背靠背，

374
00:16:41,930 --> 00:16:45,730
我們有長方形的留下一點
迴旋餘地在他們之間有點？

375
00:16:45,730 --> 00:16:49,670
而且即使我畫這個
圖片或改編此圖片

376
00:16:49,670 --> 00:16:54,696
從文本之一在這裡要回
背對背的非常有序，在現實中，

377
00:16:54,696 --> 00:16:56,820
這些矩形之一
可以在這裡在存儲器中。

378
00:16:56,820 --> 00:16:58,028
其中一人可能是在這裡。

379
00:16:58,028 --> 00:17:00,420
其中一人可能是在這裡，
在這裡，等等。

380
00:17:00,420 --> 00:17:02,910
>> 但是，如果我們畫了，
在這種情況下，箭頭

381
00:17:02,910 --> 00:17:05,650
不知怎的，這些鏈接
矩形組合在一起？

382
00:17:05,650 --> 00:17:08,170
事實上，我們已經看到了技術
化身箭頭。

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
你有沒有看到最近使用
天那，引擎蓋底下，

385
00:17:13,710 --> 00:17:15,210
是代表一個箭頭的？

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
一個指針，對不對？

388
00:17:17,349 --> 00:17:19,780
>> 那麼，如果，而不是
只存儲該號碼

389
00:17:19,780 --> 00:17:23,130
像9，17，22，26，34，
如果我們不保存

390
00:17:23,130 --> 00:17:27,079
只有一些，但指針
相鄰的數目？

391
00:17:27,079 --> 00:17:30,690
所以這就像你會跟帖
針穿過一大堆面料，

392
00:17:30,690 --> 00:17:32,950
不知何故搭售的東西
同時，同樣可以

393
00:17:32,950 --> 00:17:35,550
我們使用指針，作為
這裡用箭頭體現，

394
00:17:35,550 --> 00:17:38,550
種編織在一起
這些單個矩形

395
00:17:38,550 --> 00:17:41,780
通過有效地使用指針
旁邊的每個數

396
00:17:41,780 --> 00:17:46,065
指出了一些下一個號碼，即
指向，反過來，一些未來數？

397
00:17:46,065 --> 00:17:47,940
因此，換句話說，什麼
如果我們真正想要的

398
00:17:47,940 --> 00:17:49,820
實行這樣的事情？

399
00:17:49,820 --> 00:17:53,610
好可惜，這些矩形，
至少一個與9，17，22，

400
00:17:53,610 --> 00:17:57,040
等等，這些都不再
漂亮的廣場單號。

401
00:17:57,040 --> 00:17:59,960
底部，矩形
以下如圖9所示，例如，

402
00:17:59,960 --> 00:18:04,330
代表什麼應該
是一個指針，32位。

403
00:18:04,330 --> 00:18:09,460
現在，我還不知道任何數據類型
在C中，讓你不僅是一個整數

404
00:18:09,460 --> 00:18:11,630
但指針乾脆。

405
00:18:11,630 --> 00:18:15,020
>> 那麼，有什麼解決方案，如果我們想要
去創造我們自己的答案呢？

406
00:18:15,020 --> 00:18:15,760
是嗎？

407
00:18:15,760 --> 00:18:16,640
>> 聽眾：[聽不清]

408
00:18:16,640 --> 00:18:17,360
>> 戴維·J·馬蘭：這是什麼？

409
00:18:17,360 --> 00:18:17,880
>> 對象：新的結構。

410
00:18:17,880 --> 00:18:19,590
>> 戴維·J·馬蘭：是啊，為什麼
我們不創建一個新的結構，

411
00:18:19,590 --> 00:18:20,920
或在C中，一個結構？

412
00:18:20,920 --> 00:18:25,990
我們已經看到結構之前，如果簡單地說，
我們處理了一個學生結構

413
00:18:25,990 --> 00:18:27,780
這樣，誰的名稱和一所房子。

414
00:18:27,780 --> 00:18:31,980
在Pset的3分場您使用了全
一堆structs-- GRect和GOvals的

415
00:18:31,980 --> 00:18:34,810
在斯坦福大學創建的
集群信息一起。

416
00:18:34,810 --> 00:18:38,580
那麼，如果我們採取同樣的想法
關鍵字“類型定義”和“結構”

417
00:18:38,580 --> 00:18:42,890
然後一些學生具體的東西，
並演變成以下這樣的：

418
00:18:42,890 --> 00:18:46,210
typedef結構node--和節點
只是一個很普通的計算機科學

419
00:18:46,210 --> 00:18:49,980
長期的東西，在數據結構中，
容器中的數據結構。

420
00:18:49,980 --> 00:18:53,900
一個節點我要求都將有
一個整數N，完全明了，

421
00:18:53,900 --> 00:18:58,810
然後多一點隱晦，
這第二條線，結構節點*旁邊。

422
00:18:58,810 --> 00:19:01,300
但在更短的技術術語，
什麼是第二行

423
00:19:01,300 --> 00:19:02,980
的花括號內的代碼？

424
00:19:02,980 --> 00:19:03,737
是嗎？

425
00:19:03,737 --> 00:19:04,851
>> 聽眾：[聽不清]

426
00:19:04,851 --> 00:19:06,600
戴維·J·馬蘭：一
指針到另一個節點。

427
00:19:06,600 --> 00:19:09,910
所以不可否認，語法有點神秘。

428
00:19:09,910 --> 00:19:13,250
但是，如果你從字面上看它，
接下來是一個變量的名稱。

429
00:19:13,250 --> 00:19:14,410
什麼是它的數據類型？

430
00:19:14,410 --> 00:19:18,206
這是一個有點冗長這個時候，
但它的類型結構節點*。

431
00:19:18,206 --> 00:19:22,960
任何我們已經看到一些明星的時候，也
意味著它是一個指針，它指向的數據類型。

432
00:19:22,960 --> 00:19:26,810
因此，下顯然是一個
指針指向一個結構節點。

433
00:19:26,810 --> 00:19:28,310
>> 現在，是一個結構的節點？

434
00:19:28,310 --> 00:19:31,044
好了，請注意您看到的那些
同樣的話，在右上角。

435
00:19:31,044 --> 00:19:33,960
事實上，你也看到這個詞
“節點”在這兒，在左下角。

436
00:19:33,960 --> 00:19:35,640
這其實只是一個方便。

437
00:19:35,640 --> 00:19:39,930
請注意，在我們學生的定義
有單詞“學生”只有一次。

438
00:19:39,930 --> 00:19:42,510
那是因為學生
對象不是自我指涉。

439
00:19:42,510 --> 00:19:45,340
沒有什麼是學生的內部
需要指向另一名學生，

440
00:19:45,340 --> 00:19:45,610
PerSay的。

441
00:19:45,610 --> 00:19:47,630
這將是某種
怪異在現實世界中。

442
00:19:47,630 --> 00:19:50,880
>> 但在一個節點鏈接
列表中，我們希望有一個節點

443
00:19:50,880 --> 00:19:53,970
是參考了類似的對象。

444
00:19:53,970 --> 00:19:57,900
等注意到這裡的變化是不
只是什麼花括號內。

445
00:19:57,900 --> 00:20:00,800
但是我們加上“節點”
在頂部，以及

446
00:20:00,800 --> 00:20:02,930
將其添加至底部
代替“學生”。

447
00:20:02,930 --> 00:20:06,000
而這僅僅是一個技術細節
這樣一來，同樣，你的數據結構

448
00:20:06,000 --> 00:20:11,380
可自行參照，讓
節點可以指向另一個這樣的節點。

449
00:20:11,380 --> 00:20:13,840
>> 那麼，這是什麼最終
將意味著我們呢？

450
00:20:13,840 --> 00:20:17,560
嗯，一，這裡面的東西
是我們的節點的內容。

451
00:20:17,560 --> 00:20:19,360
這東西在這裡，
右上方，就是這麼

452
00:20:19,360 --> 00:20:20,860
即，再次，大家可以參考一下自己。

453
00:20:20,860 --> 00:20:23,401
然後最外面的東西，
即使節點是一個新名詞，

454
00:20:23,401 --> 00:20:25,500
也許，它仍然是
一樣的學生，什麼

455
00:20:25,500 --> 00:20:27,520
在SPL引擎蓋下面。

456
00:20:27,520 --> 00:20:31,095
>> 因此，如果我們現在要開始
實施本鍊錶，

457
00:20:31,095 --> 00:20:33,220
怎麼可能，我們翻譯
像這樣的代碼？

458
00:20:33,220 --> 00:20:35,350
好吧，讓我們看到一個
例如一個程序的

459
00:20:35,350 --> 00:20:36,840
實際使用鍊錶。

460
00:20:36,840 --> 00:20:40,870
在今天的分銷代碼
是一個名為List零計劃。

461
00:20:40,870 --> 00:20:44,980
如果我運行這個，我創建了一個超
簡單的圖形用戶界面，圖形用戶界面，

462
00:20:44,980 --> 00:20:46,460
但它真的只是printf的。

463
00:20:46,460 --> 00:20:50,930
現在我已經給自己幾個菜單
選項 - 刪除，插入，檢索，

464
00:20:50,930 --> 00:20:51,750
和導線。

465
00:20:51,750 --> 00:20:52,630
並退出。

466
00:20:52,630 --> 00:20:55,970
這是一個公正的常用操作
被稱為鏈接列表數據結構。

467
00:20:55,970 --> 00:20:58,409
>> 現在，刪除是要
刪除了一些從列表中。

468
00:20:58,409 --> 00:21:00,200
插入件的要加
數到列表中。

469
00:21:00,200 --> 00:21:02,181
搜索是要去看看
對於列表中的號碼。

470
00:21:02,181 --> 00:21:04,930
和遍歷僅僅是一個奇特的方式
的說法，漫步列表，

471
00:21:04,930 --> 00:21:06,245
它打印出來，但僅此而已。

472
00:21:06,245 --> 00:21:07,720
不要以任何方式改變它。

473
00:21:07,720 --> 00:21:08,570
>> 因此，讓我們試試這個。

474
00:21:08,570 --> 00:21:10,160
讓我們繼續前進，2型。

475
00:21:10,160 --> 00:21:12,710
然後我要去
插入的數目，表示9。

476
00:21:12,710 --> 00:21:13,620
輸入。

477
00:21:13,620 --> 00:21:17,480
現在我的計劃就是
編程來說，列表是現在9。

478
00:21:17,480 --> 00:21:20,190
現在，如果我繼續前進，
不要再插入，讓

479
00:21:20,190 --> 00:21:23,680
我繼續前進，縮小並輸入17。

480
00:21:23,680 --> 00:21:25,770
現在我的名單是9，那麼17。

481
00:21:25,770 --> 00:21:27,750
如果我做再次插入，讓我們跳過之一。

482
00:21:27,750 --> 00:21:32,400
相反22，按照圖片中我們已經
一直在看這裡，讓我跳躍前進

483
00:21:32,400 --> 00:21:34,630
並插入26下一頁。

484
00:21:34,630 --> 00:21:36,230
所以，我要輸入26。

485
00:21:36,230 --> 00:21:37,755
這份名單是我所期望的。

486
00:21:37,755 --> 00:21:40,630
但現在，只是如果這個代碼見
將是靈活的，現在讓我

487
00:21:40,630 --> 00:21:43,520
型22，其中至少有
從概念上講，如果我們

488
00:21:43,520 --> 00:21:46,520
保持此排序，這確實是
將是另一個目標，現在，

489
00:21:46,520 --> 00:21:48,690
17和26之間應該在。

490
00:21:48,690 --> 00:21:50,270
所以我敲回車。

491
00:21:50,270 --> 00:21:51,380
事實上，工作的。

492
00:21:51,380 --> 00:21:54,950
所以現在讓我插入
最後，每個圖片，34。

493
00:21:54,950 --> 00:21:55,450
>> 好吧。

494
00:21:55,450 --> 00:21:58,980
所以現在讓我規定
刪除和遍歷和搜索做的，

495
00:21:58,980 --> 00:21:59,760
其實，工作。

496
00:21:59,760 --> 00:22:04,180
事實上，如果我不執行搜索，讓我們
搜索次數22，回車。

497
00:22:04,180 --> 00:22:05,010
研究發現22。

498
00:22:05,010 --> 00:22:07,580
所以這就是這個
程序清單零呢。

499
00:22:07,580 --> 00:22:10,230
>> 但實際上會
在實現這一點？

500
00:22:10,230 --> 00:22:14,530
嗯，首先我可能有，確實
我有一個文件名為list0.h。

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
而在某個地方有這樣的
行，類型定義，結構節點，

503
00:22:20,690 --> 00:22:24,850
然後，我有我的花括號，詮釋n和
然後struct--究竟是什麼定義？

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
結構節點旁邊。

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
因此，我們需要的明星。

508
00:22:31,045 --> 00:22:33,420
現在，技術上我們進入
在這裡畫的習慣。

509
00:22:33,420 --> 00:22:35,670
你可能會看到課本和
網上參考做那裡。

510
00:22:35,670 --> 00:22:36,660
它的功能相當的。

511
00:22:36,660 --> 00:22:37,980
其實，這是一個小更典型。

512
00:22:37,980 --> 00:22:40,563
但我會用什麼樣一致
我們做了最後的時間，做到這一點。

513
00:22:40,563 --> 00:22:42,350
然後最後，我要做到這一點。

514
00:22:42,350 --> 00:22:45,550
>> 因此，在頭文件
某處，在list0.h

515
00:22:45,550 --> 00:22:49,200
今天是這個結構的定義，
也許一些其他的東西。

516
00:22:49,200 --> 00:22:52,580
與此同時，在list0c有
將是一個幾件事情。

517
00:22:52,580 --> 00:22:54,740
但是，我們要公正
開始，而不是結束了。

518
00:22:54,740 --> 00:22:59,690
List0.h是我想要的文件
包括在我的C文件。

519
00:22:59,690 --> 00:23:03,910
然後在某個時候，我
將有整型，主要的，無效的。

520
00:23:03,910 --> 00:23:06,530
然後我要去
有一些待辦事項在這裡。

521
00:23:06,530 --> 00:23:10,620
我也將有一個
原型，如虛空，搜索，INT，

522
00:23:10,620 --> 00:23:13,610
N，在生活中，其目的是
要搜索的元素。

523
00:23:13,610 --> 00:23:18,310
再往下這裡我要求在
今天的碼，無效搜索，INT，N，

524
00:23:18,310 --> 00:23:21,020
別無分號，但開放的花括號。

525
00:23:21,020 --> 00:23:25,049
現在我想以某種方式查詢
對於該列表中的一個元素。

526
00:23:25,049 --> 00:23:27,340
但是，我們沒有足夠的
但在屏幕上的信息。

527
00:23:27,340 --> 00:23:29,800
我沒有實際
表示該清單自身。

528
00:23:29,800 --> 00:23:33,070
所以一個方法，我們可以實現
鍊錶的程序

529
00:23:33,070 --> 00:23:37,520
一種是我想要做的事
如聲明成鍊錶在這裡。

530
00:23:37,520 --> 00:23:40,520
為簡單起見，我將做出
這一全球性的，儘管一般我們

531
00:23:40,520 --> 00:23:41,645
不應該這樣做太過分了。

532
00:23:41,645 --> 00:23:43,260
但它可以簡化這個例子。

533
00:23:43,260 --> 00:23:45,890
所以，我想聲明
鍊錶在這裡。

534
00:23:45,890 --> 00:23:47,010
現在，我怎麼可能這樣做呢？

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> 這裡有一個鏈接列表的畫面。

537
00:23:50,750 --> 00:23:53,030
我真的不
知道此刻如何

538
00:23:53,030 --> 00:23:56,710
我打算去代表
只用一個這麼多東西

539
00:23:56,710 --> 00:23:58,040
變量在內存中。

540
00:23:58,040 --> 00:23:59,160
但回想一下。

541
00:23:59,160 --> 00:24:00,830
這一切的時候，我們已經有
字符串，我們再

542
00:24:00,830 --> 00:24:02,913
發現是數組
字符，然後我們

543
00:24:02,913 --> 00:24:05,740
顯露只是一個指針
到的第一個字符

544
00:24:05,740 --> 00:24:08,890
在字符數組
這是空終止。

545
00:24:08,890 --> 00:24:13,530
所以通過該邏輯，以及與此
圖像種類播種的想法，

546
00:24:13,530 --> 00:24:17,964
有什麼需要我們在實際編寫我們
代碼來表示鍊錶？

547
00:24:17,964 --> 00:24:21,130
如何對這些信息多我們需要
捕捉到的C代碼，你會說什麼？

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
是嗎？

550
00:24:23,154 --> 00:24:24,738
>> 聽眾：我們需要一個指向一個節點。

551
00:24:24,738 --> 00:24:26,237
戴維·J·馬蘭：一個指針，指向一個節點。

552
00:24:26,237 --> 00:24:29,320
特別是，該節點將您的
本能是要保持一個指針？

553
00:24:29,320 --> 00:24:30,026
>> 聽眾：第一節點。

554
00:24:30,026 --> 00:24:31,942
>> 戴維·J·馬蘭：是啊，
可能只是第一個。

555
00:24:31,942 --> 00:24:34,030
並注意，第一
節點是不同的形狀。

556
00:24:34,030 --> 00:24:37,690
它的結構只有一半的大小，
因為它確實只是一個指針。

557
00:24:37,690 --> 00:24:44,650
那麼，你的確可以做的就是聲明
鍊錶是類型的節點*。

558
00:24:44,650 --> 00:24:47,780
而且，我們只是先稱它為
並把它初始化為null。

559
00:24:47,780 --> 00:24:49,910
所以空，再次，是未來
到這裡的畫面。

560
00:24:49,910 --> 00:24:53,620
不僅是空作為像一種特殊的
搞什麼的GetString返回值

561
00:24:53,620 --> 00:24:57,770
和malloc，空也是零
指針，缺乏一個指針，

562
00:24:57,770 --> 00:24:58,430
如果你願意。

563
00:24:58,430 --> 00:25:00,309
它只是意味著什麼又是在這裡。

564
00:25:00,309 --> 00:25:02,100
現在開始，我會一直
所謂的事。

565
00:25:02,100 --> 00:25:04,200
我可以把它叫做“名單”
或任何數目的其他事情。

566
00:25:04,200 --> 00:25:06,960
但我把它稱為“第一”，使
這行了這幅畫。

567
00:25:06,960 --> 00:25:10,280
所以就像一個字符串可以表示
其第一個字節的地址，

568
00:25:10,280 --> 00:25:11,280
所以可以一個鍊錶。

569
00:25:11,280 --> 00:25:13,480
我們會看到其他數據
結構式來表示

570
00:25:13,480 --> 00:25:16,700
只有一個指針，
一個32位的箭頭，指向

571
00:25:16,700 --> 00:25:18,740
在該結構中的第一個節點。

572
00:25:18,740 --> 00:25:20,340
>> 但現在，讓我們期待一個問題。

573
00:25:20,340 --> 00:25:23,230
如果我只記得
在我的程序中的地址

574
00:25:23,230 --> 00:25:27,220
第一節點，所述第一
矩形在此數據結構中，

575
00:25:27,220 --> 00:25:31,760
什麼最好是對的情況下，
實現我的名單的其餘部分？

576
00:25:31,760 --> 00:25:35,820
那是什麼回事的關鍵細節
為確保這一點的實際工作？

577
00:25:35,820 --> 00:25:39,250
並通過“實際工作”我
意思是說，就像一個字符串，

578
00:25:39,250 --> 00:25:42,180
讓我們從第一個字符去
在達文的名稱，以第二，

579
00:25:42,180 --> 00:25:44,755
到第三，對
第四，到了最後，

580
00:25:44,755 --> 00:25:47,880
我們怎麼知道，當我們在最後
鍊錶，看起來像這樣？

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
當它為空。

583
00:25:50,660 --> 00:25:53,640
我已經表示這樣的作為
像電氣工程師可能，

584
00:25:53,640 --> 00:25:56,420
與小接地
各種各樣的符號。

585
00:25:56,420 --> 00:25:58,246
但是，這只是意味著在這種情況下空。

586
00:25:58,246 --> 00:26:00,370
您可以繪製任意數量
的方法，但筆者

587
00:26:00,370 --> 00:26:02,800
發生在這裡使用這個標誌。

588
00:26:02,800 --> 00:26:06,260
>> 只要我們穿線
所有這些節點一起

589
00:26:06,260 --> 00:26:08,600
只記得在哪裡
第一個是，只要

590
00:26:08,600 --> 00:26:11,760
當我們把一個特殊符號，在
在列表中的最後節點，

591
00:26:11,760 --> 00:26:15,130
我們將使用空，因為這是
我們必須提供給我們，

592
00:26:15,130 --> 00:26:16,480
該列表已完成。

593
00:26:16,480 --> 00:26:20,190
即使我只給你一個指針
第一個元素，你，程序員，

594
00:26:20,190 --> 00:26:22,486
當然可以訪問它的其餘部分。

595
00:26:22,486 --> 00:26:24,360
但是，讓我們讓你的頭腦
遊蕩了一點點，

596
00:26:24,360 --> 00:26:26,140
如果他們不是已經
很wandered--什麼

597
00:26:26,140 --> 00:26:28,723
將要的運行時間
發現在這個名單什麼？

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
該死，這n個大O，
這是不壞，在公平性。

600
00:26:33,470 --> 00:26:34,800
但它是線性的。

601
00:26:34,800 --> 00:26:37,980
我們已經放棄了什麼功能
陣列通過移動更多

602
00:26:37,980 --> 00:26:43,130
對這張照片的動態
交織在一起或鏈接的節點？

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
我們已經放棄了隨機訪問。

605
00:26:46,687 --> 00:26:48,770
數組是不錯的，因為
數學上的一切

606
00:26:48,770 --> 00:26:50,340
是背靠背背靠背。

607
00:26:50,340 --> 00:26:52,370
儘管這幅畫
看起來很漂亮，甚至

608
00:26:52,370 --> 00:26:55,830
雖然它看起來像這些節點
是很好的分開，在現實中

609
00:26:55,830 --> 00:26:56,830
他們可以在任何地方。

610
00:26:56,830 --> 00:27:01,590
OX1，OX50，Ox123，Ox99，這些
節點可以在任何地方。

611
00:27:01,590 --> 00:27:05,960
因為做的malloc分配內存
離堆，但在任何地方堆。

612
00:27:05,960 --> 00:27:09,080
你不一定知道它的
將是背靠背回來。

613
00:27:09,080 --> 00:27:12,460
所以這幅畫在現實中的
不會是今天這樣漂亮。

614
00:27:12,460 --> 00:27:16,140
>> 因此，這將需要一些
努力實現這個功能。

615
00:27:16,140 --> 00:27:17,880
現在讓我們實現搜索。

616
00:27:17,880 --> 00:27:20,250
我們將看到種類的
這樣做的聰明的方式。

617
00:27:20,250 --> 00:27:24,660
所以，如果我是一個搜索功能和
我給一個變量，整數n

618
00:27:24,660 --> 00:27:28,490
尋找，我需要知道的
在裡面尋找新的語法

619
00:27:28,490 --> 00:27:32,400
一個結構，是的
指出，為求n。

620
00:27:32,400 --> 00:27:33,210
因此，讓我們做到這一點。

621
00:27:33,210 --> 00:27:36,030
>> 所以，首先我會去
未來，並宣布一個節點*。

622
00:27:36,030 --> 00:27:39,400
我要去把它稱為
指針，只是約定。

623
00:27:39,400 --> 00:27:41,710
我要去把它初始化為先。

624
00:27:41,710 --> 00:27:43,770
現在我可以做到這一點
在許多方面。

625
00:27:43,770 --> 00:27:45,436
不過，我要採取的共同辦法。

626
00:27:45,436 --> 00:27:50,180
而指針不等於
空，這是有效的語法。

627
00:27:50,180 --> 00:27:54,550
它只是意味著做到以下幾點，那麼
只要你不指著什麼。

628
00:27:54,550 --> 00:27:55,800
我該怎麼想呢？

629
00:27:55,800 --> 00:28:01,939
>> 如果指針點N，讓我回來
到，equals--等於什麼？

630
00:28:01,939 --> 00:28:03,105
我在尋找什麼樣的價值？

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
這是通過在實際ñ。

633
00:28:06,590 --> 00:28:09,020
因此，這裡的另一特色
對C和許多語言。

634
00:28:09,020 --> 00:28:13,705
即使所謂的結構節點
有一個n值，完全合法

635
00:28:13,705 --> 00:28:17,530
也有當地的說法
或者叫變量n。

636
00:28:17,530 --> 00:28:20,085
因為即使我們有
人眼可以分辨

637
00:28:20,085 --> 00:28:22,087
這n是推測
不同於該n。

638
00:28:22,087 --> 00:28:23,420
因為語法是不同的。

639
00:28:23,420 --> 00:28:26,211
你有一個點和一個指針，
而這其中有沒有這樣的事情。

640
00:28:26,211 --> 00:28:27,290
因此，這是確定。

641
00:28:27,290 --> 00:28:29,120
這是確定的打電話給他們同樣的事情。

642
00:28:29,120 --> 00:28:32,380
>> 如果我發現你這個，我是
會想要做的事

643
00:28:32,380 --> 00:28:35,000
像大家宣布，我們發現Ñ。

644
00:28:35,000 --> 00:28:37,930
我們會離開，作為一個
發表評論或偽代碼。

645
00:28:37,930 --> 00:28:40,190
否則，和這裡的
有趣的部分，是什麼

646
00:28:40,190 --> 00:28:47,320
做我想做的事情，如果當前節點
不包含n個我在乎？

647
00:28:47,320 --> 00:28:50,700
我如何實現以下？

648
00:28:50,700 --> 00:28:53,710
如果我的手指在
此刻是PTR，它的

649
00:28:53,710 --> 00:28:55,920
指著什麼
第一是指向，

650
00:28:55,920 --> 00:28:59,290
如何將我的手指
在代碼中的下一個節點？

651
00:28:59,290 --> 00:29:01,915
那麼，什麼是我們的麵包屑
要在這種情況下，遵循？

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
聽眾：[聽不清]。

654
00:29:04,380 --> 00:29:05,630
戴維·J·馬蘭：是啊，所以下一步。

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
所以，如果我回到我的
這裡的代碼，事實上，我

657
00:29:09,824 --> 00:29:12,990
要繼續前進，說的指針，這
只是一個暫時的變量 - 這是

658
00:29:12,990 --> 00:29:15,320
一個奇怪的名字，PTR，但
它就像temp--

659
00:29:15,320 --> 00:29:19,234
我要設置指針
等於任何指針is--

660
00:29:19,234 --> 00:29:22,150
又一次，這將是一個
小馬車的moment--點下一步。

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
換句話說，我要去把我的
指的是指向該節點

663
00:29:26,550 --> 00:29:31,247
在這裡，我想說，你知道
什麼，看看下一個字段

664
00:29:31,247 --> 00:29:33,330
移動你的手指
不管它的指向。

665
00:29:33,330 --> 00:29:35,163
並且這將
重複，重複，重複。

666
00:29:35,163 --> 00:29:37,630
但是，什麼時候我的手指
停止做了什麼呢？

667
00:29:37,630 --> 00:29:40,095
只要什麼碼踢行？

668
00:29:40,095 --> 00:29:40,970
聽眾：[聽不清]

669
00:29:40,970 --> 00:29:43,060
戴維·J·馬蘭：如果同時點
指針不等於空。

670
00:29:43,060 --> 00:29:44,900
在某些時候，我的手指的
將要指向空

671
00:29:44,900 --> 00:29:47,070
我要去實現
這是該列表的末尾。

672
00:29:47,070 --> 00:29:48,910
現在，這是一個小
善意的謊言的簡單性。

673
00:29:48,910 --> 00:29:51,580
事實證明，即使我們
剛剛得知這個點符號

674
00:29:51,580 --> 00:29:55,220
對於結構，指針不是一個結構。

675
00:29:55,220 --> 00:29:56,580
PTR是什麼？

676
00:29:56,580 --> 00:29:58,350
只是要更挑剔。

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
這是一個指針，指向一個節點。

679
00:30:01,360 --> 00:30:03,120
這不是一個節點本身。

680
00:30:03,120 --> 00:30:06,650
如果我在這裡沒有明星，指針
absolutely--它是一個節點。

681
00:30:06,650 --> 00:30:08,650
這就好比一個星期
變量聲明，

682
00:30:08,650 --> 00:30:10,120
即使單詞“節點”是新的。

683
00:30:10,120 --> 00:30:13,860
>> 但只要我們引入了
明星，它現在是一個指針，指向一個節點。

684
00:30:13,860 --> 00:30:17,960
但不幸的是你不能使用
點號的一個指針。

685
00:30:17,960 --> 00:30:21,070
你必須使用箭頭
符號，其中，引人注目的是，

686
00:30:21,070 --> 00:30:23,470
是第一次的任何一塊
語法看起來直觀。

687
00:30:23,470 --> 00:30:25,245
這從字面上看起來像一個箭頭。

688
00:30:25,245 --> 00:30:26,370
因此，這是一件好事。

689
00:30:26,370 --> 00:30:28,995
而到這裡字面上
看起來像一個箭頭。

690
00:30:28,995 --> 00:30:31,870
所以，我認為這是la--我不
想我過犯這裡 - ì

691
00:30:31,870 --> 00:30:34,120
認為這是最後的新作品
語法我們要看到的。

692
00:30:34,120 --> 00:30:36,500
而幸運的是，這是真的
多一點直觀。

693
00:30:36,500 --> 00:30:40,090
>> 現在，對於那些你們誰
可能更喜歡舊的方式，

694
00:30:40,090 --> 00:30:42,550
你仍然可以使用點號。

695
00:30:42,550 --> 00:30:45,380
但由於每星期一
談話中，我們首先

696
00:30:45,380 --> 00:30:50,530
需要去那裡，去那
處理，然後訪問字段。

697
00:30:50,530 --> 00:30:51,897
因此，這也是正確的。

698
00:30:51,897 --> 00:30:53,730
坦率地說，這是一個
有點迂腐。

699
00:30:53,730 --> 00:30:56,530
你從字面上說，提領
指針和去那裡。

700
00:30:56,530 --> 00:30:59,320
然後抓住.N，現場叫ñ。

701
00:30:59,320 --> 00:31:01,370
但坦率地說，沒有人願意
打字或閱讀。

702
00:31:01,370 --> 00:31:03,620
這樣一來，發明了世界
箭頭符號，其中

703
00:31:03,620 --> 00:31:06,980
是等價的，相同的，
它只是語法糖。

704
00:31:06,980 --> 00:31:10,570
對這個說法如此看中方式
看起來更好，看起來更簡單。

705
00:31:10,570 --> 00:31:12,296
>> 所以現在我要做的一件事。

706
00:31:12,296 --> 00:31:15,420
我會說“休息”一旦我
發現它，所以我不繼續尋找它。

707
00:31:15,420 --> 00:31:17,620
但是，這是依據
的搜索功能。

708
00:31:17,620 --> 00:31:21,710
但它是一個容易得多，在
最後，不要穿行的代碼。

709
00:31:21,710 --> 00:31:25,570
這的確是正式實施
在今天的分銷代碼搜索。

710
00:31:25,570 --> 00:31:30,530
我敢說，插不
特別有趣的穿行

711
00:31:30,530 --> 00:31:33,180
在視覺上，也不是刪除，甚至
雖然在這一天結束時

712
00:31:33,180 --> 00:31:35,460
他們歸結為公平
簡單的啟發式方法。

713
00:31:35,460 --> 00:31:36,330
>> 因此，讓我們做到這一點。

714
00:31:36,330 --> 00:31:39,250
如果你會幽默我在這裡，我沒有
把一堆壓力球。

715
00:31:39,250 --> 00:31:40,620
我帶了一堆數字。

716
00:31:40,620 --> 00:31:46,562
而我們能得到的只是一些志願者
代表9，17，20，22，29和34？

717
00:31:46,562 --> 00:31:48,270
所以基本上每個人都
誰是今天。

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
這是一，二，三，
四，五，六人。

720
00:31:52,760 --> 00:31:55,740
我一直在問go--看，沒有
一個在後面舉手。

721
00:31:55,740 --> 00:32:01,910
好了，一，二，三，四，
five--讓我加載balance-- 6。

722
00:32:01,910 --> 00:32:03,051
好了，你六上來吧。

723
00:32:03,051 --> 00:32:04,050
我們需要其他人。

724
00:32:04,050 --> 00:32:05,460
我們帶來了額外的壓力球。

725
00:32:05,460 --> 00:32:08,200
如果你可以，
只是一瞬間，行

726
00:32:08,200 --> 00:32:10,490
自己剛起來
喜歡這幅畫在這裡。

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> 好吧。

729
00:32:15,959 --> 00:32:17,125
讓我們來看看，你叫什麼名字？

730
00:32:17,125 --> 00:32:17,550
>> 聽眾：安德魯。

731
00:32:17,550 --> 00:32:18,800
>> 戴維·J·馬蘭：安德魯，
你是9號。

732
00:32:18,800 --> 00:32:19,540
很高興認識你。

733
00:32:19,540 --> 00:32:20,400
幹得好。

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
聽眾：仁。

736
00:32:22,176 --> 00:32:22,662
戴維·J·馬蘭：仁。

737
00:32:22,662 --> 00:32:23,162
大衛。

738
00:32:23,162 --> 00:32:23,765
號碼17。

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
是嗎？

741
00:32:25,450 --> 00:32:26,400
>> 聽眾：我是朱莉婭。

742
00:32:26,400 --> 00:32:26,980
>> 戴維·J·馬蘭：朱莉婭大衛。

743
00:32:26,980 --> 00:32:27,545
號碼20。

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
聽眾：基督教。

746
00:32:29,340 --> 00:32:30,715
戴維·J·馬蘭：基督教，大衛。

747
00:32:30,715 --> 00:32:31,541
號碼22。

748
00:32:31,541 --> 00:32:32,040
和？

749
00:32:32,040 --> 00:32:32,649
>> 聽眾：日本。

750
00:32:32,649 --> 00:32:33,440
戴維·J·馬蘭：日本。

751
00:32:33,440 --> 00:32:34,880
號碼29。

752
00:32:34,880 --> 00:32:37,080
所以，儘管獲得in--嗯哦。

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
嗯哦。

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
待機。

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20。

759
00:32:42,390 --> 00:32:43,682
有沒有人有一個標記？

760
00:32:43,682 --> 00:32:44,890
聽眾：我有一個夏普。

761
00:32:44,890 --> 00:32:45,660
戴維·J·馬蘭：你有夏普？

762
00:32:45,660 --> 00:32:46,159
行。

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
並沒有任何人有一張紙？

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
保存了講座。

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
來吧。

769
00:32:55,362 --> 00:32:56,320
聽眾：我們已經知道了。

770
00:32:56,320 --> 00:32:57,600
戴維·J·馬蘭：我們得到了它？

771
00:32:57,600 --> 00:32:58,577
好吧，謝謝你。

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
開始了。

774
00:33:02,520 --> 00:33:03,582
從你是這樣的？

775
00:33:03,582 --> 00:33:04,540
你剛才化險為夷。

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
所以29。

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
好吧。

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
í拼寫錯誤29，但確定。

782
00:33:14,890 --> 00:33:15,720
前進。

783
00:33:15,720 --> 00:33:18,114
好吧，我給你
你的筆回暫時。

784
00:33:18,114 --> 00:33:19,280
所以我們這些人在這裡。

785
00:33:19,280 --> 00:33:20,330
讓我們有一個其他的。

786
00:33:20,330 --> 00:33:23,750
加布，你要玩
這裡的第一個元素？

787
00:33:23,750 --> 00:33:25,705
我們需要你來點
這些精美的鄉親。

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
所以，9，17，20，22，排序
29，然後34。

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
我們失去了一個人？

792
00:33:33,325 --> 00:33:33,950
我有一個34。

793
00:33:33,950 --> 00:33:36,730
凡did--確定，誰願意為34？

794
00:33:36,730 --> 00:33:37,605
好了，上來吧，34。

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
好吧，這將是
非常值得的高潮。

797
00:33:41,220 --> 00:33:41,550
你叫什麼名字？

798
00:33:41,550 --> 00:33:42,040
>> 聽眾：彼得。

799
00:33:42,040 --> 00:33:43,456
>> 戴維·J·馬蘭：彼得，上來吧。

800
00:33:43,456 --> 00:33:46,810
好吧，那麼這裡有一個
一大堆的節點。

801
00:33:46,810 --> 00:33:49,060
每次你們都代表
其中的一個矩形。

802
00:33:49,060 --> 00:33:51,930
和加布，稍奇
男人出來，表示第一。

803
00:33:51,930 --> 00:33:54,850
所以他的指針是一個小一點
在屏幕上比其他人。

804
00:33:54,850 --> 00:33:58,120
並且在這種情況下，每個你的左
手是怎麼回事要么點下去，

805
00:33:58,120 --> 00:34:01,085
從而表示空值，所以
只是沒有指針，

806
00:34:01,085 --> 00:34:03,210
或者它會被人指指點點
在你旁邊的一個節點。

807
00:34:03,210 --> 00:34:05,440
>> 所以現在，如果你佩戴
喜歡的圖片呀

808
00:34:05,440 --> 00:34:07,585
在這裡，繼續和點
對方，用加布

809
00:34:07,585 --> 00:34:11,030
在特定的指向
編號9表示的列表。

810
00:34:11,030 --> 00:34:14,050
確定，34號，你的左手
應該只指向地面。

811
00:34:14,050 --> 00:34:15,750
>> 好了，這就是鍊錶。

812
00:34:15,750 --> 00:34:17,580
所以，這是該方案的問題。

813
00:34:17,580 --> 00:34:20,210
事實上，這是代表
一類的問題

814
00:34:20,210 --> 00:34:21,929
你可能會試圖解決與代碼。

815
00:34:21,929 --> 00:34:25,020
你想最終將
一個新的元素到列表中。

816
00:34:25,020 --> 00:34:27,494
在這種情況下，我們要
請嘗試將數字55。

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
但是，將是
不同的情況來考慮。

819
00:34:30,860 --> 00:34:34,409
事實上，這將是1
的大畫面紀要這裡，是，

820
00:34:34,409 --> 00:34:35,659
什麼是不同的情況。

821
00:34:35,659 --> 00:34:39,120
什麼是如果條件或不同
你的程序可能有分支機構？

822
00:34:39,120 --> 00:34:42,024
>> 嗯，這個數字你要
插入，這是我們現在知道是55，

823
00:34:42,024 --> 00:34:44,650
但如果你不知道
事先，我敢說

824
00:34:44,650 --> 00:34:47,840
落入至少三個
可能出現的情況。

825
00:34:47,840 --> 00:34:49,717
凡可能一個新的元素呢？

826
00:34:49,717 --> 00:34:51,050
聽。結束或中間。

827
00:34:51,050 --> 00:34:54,150
戴維·J·馬蘭：最後，在
的中間，或在開始時。

828
00:34:54,150 --> 00:34:56,650
所以，我要求有至少
我們需要解決三個問題。

829
00:34:56,650 --> 00:34:58,691
讓我們選擇什麼樣的可能
可以說是最簡單的

830
00:34:58,691 --> 00:35:01,090
之一，其中該新元素
屬於開頭。

831
00:35:01,090 --> 00:35:04,040
所以我將有相當代碼
如搜索，我只是寫。

832
00:35:04,040 --> 00:35:07,670
我要去有PTR，這
我在這裡代表我的手指，

833
00:35:07,670 --> 00:35:08,370
照常。

834
00:35:08,370 --> 00:35:12,430
>> 請記住，什麼樣的價值
我們曾初始化PTR什麼？

835
00:35:12,430 --> 00:35:15,300
因此，我們初始化為null開始。

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
但後​​來我們做了一次，我們什麼
是我們的搜索功能裡？

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
我們設置它等於第一次，
這並不意味著這樣做。

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
如果我設置PTR等於一，什麼
應我的手真的是指向？

842
00:35:30,570 --> 00:35:31,070
右。

843
00:35:31,070 --> 00:35:33,290
所以，如果加布和我要去
這裡是相等的值，

844
00:35:33,290 --> 00:35:34,760
我們需要在兩個點在9號。

845
00:35:34,760 --> 00:35:36,420
>> 因此，這是我們的故事的開始。

846
00:35:36,420 --> 00:35:38,700
而現在這僅僅是簡單的，
即使語法是新的。

847
00:35:38,700 --> 00:35:40,580
概念上，這只是線性搜索。

848
00:35:40,580 --> 00:35:42,750
是55等於9？

849
00:35:42,750 --> 00:35:45,559
或者說，讓我們說不到9。

850
00:35:45,559 --> 00:35:47,600
因為我想
找出放在哪裡55。

851
00:35:47,600 --> 00:35:51,270
9以上，小於17，小於
大於20，小於22，小於29，

852
00:35:51,270 --> 00:35:52,510
小於34，沒有。

853
00:35:52,510 --> 00:35:55,080
所以，現在我們的情況下
一個上的至少三個。

854
00:35:55,080 --> 00:35:59,910
>> 如果我要插入55在這裡，有什麼
得到執行的代碼需要行？

855
00:35:59,910 --> 00:36:01,890
請問這個圖片
人類需要改變嗎？

856
00:36:01,890 --> 00:36:03,181
我該怎麼辦我的左手？

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
這應該是零開始，
因為我在列表的末尾。

859
00:36:07,360 --> 00:36:09,318
什麼應該發生
這裡彼得，是嗎？

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
他顯然會指向我。

862
00:36:12,430 --> 00:36:15,580
所以，我要求有至少兩條線路
在今天的示例代碼代碼

863
00:36:15,580 --> 00:36:18,570
這是怎麼回事實現這個
方案中加入55的尾巴。

864
00:36:18,570 --> 00:36:20,950
而我能有一個人跳
起來，只是表示55？

865
00:36:20,950 --> 00:36:22,200
好吧，你是新的55。

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> 所以現在，如果下一個
情景出現時，

868
00:36:27,054 --> 00:36:29,720
我們要插入的
開始的時候還是這個列表的頭？

869
00:36:29,720 --> 00:36:31,100
而你叫什麼名字，號碼55？

870
00:36:31,100 --> 00:36:31,420
>> 聽眾：傑克。

871
00:36:31,420 --> 00:36:32,295
>> 戴維·J·馬蘭：傑克？

872
00:36:32,295 --> 00:36:33,585
好了，很高興見到你。

873
00:36:33,585 --> 00:36:34,210
歡迎登機。

874
00:36:34,210 --> 00:36:36,640
所以，現在我們要
插入，比方說，數字5。

875
00:36:36,640 --> 00:36:39,840
這裡的第二種情況
3，我們想出了之前。

876
00:36:39,840 --> 00:36:43,050
因此，如果5屬於之初，
讓我們來看看我們是如何發現這一點。

877
00:36:43,050 --> 00:36:46,310
í初始化我的PTR
指針再次號碼9。

878
00:36:46,310 --> 00:36:49,140
我意識到，哦，5小於9。

879
00:36:49,140 --> 00:36:50,880
因此，解決這個問題的圖片我們。

880
00:36:50,880 --> 00:36:54,820
誰的手裡，Gabe的還是大衛
or--什麼是數字9的名字？

881
00:36:54,820 --> 00:36:55,740
>> 聽眾：仁。

882
00:36:55,740 --> 00:36:58,406
>> 戴維·J·馬蘭：仁的hands--
其中，我們的手需要改變嗎？

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
好了，加布指著現在該怎麼辦？

885
00:37:00,970 --> 00:37:01,640
看著我。

886
00:37:01,640 --> 00:37:02,750
我的新節點。

887
00:37:02,750 --> 00:37:04,870
所以我就種做法
這裡直觀地看到它。

888
00:37:04,870 --> 00:37:06,435
而與此同時我該怎麼點呢？

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
還在那裡我指指點點。

891
00:37:09,020 --> 00:37:10,000
所以，就是這樣。

892
00:37:10,000 --> 00:37:13,717
所以真的很需要一行代碼修復
這個問題上，似乎。

893
00:37:13,717 --> 00:37:14,800
好了，所以這是很好的。

894
00:37:14,800 --> 00:37:17,580
而也有人是一個佔位符，5？

895
00:37:17,580 --> 00:37:18,080
上來吧。

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
我們將讓您下一次。

898
00:37:21,320 --> 00:37:24,280
>> 好吧，讓now--和
順便說一句，該名

899
00:37:24,280 --> 00:37:28,510
我不是做明確提及的權利
現在，PRED指針，指針的前身

900
00:37:28,510 --> 00:37:31,260
而新的指針，這是
只是名字定

901
00:37:31,260 --> 00:37:35,280
在示例代碼的指針或
我的手說的那種指著身邊。

902
00:37:35,280 --> 00:37:36,060
你叫什麼名字？

903
00:37:36,060 --> 00:37:36,700
>> 聽眾：恭。

904
00:37:36,700 --> 00:37:37,100
>> 戴維·J·馬蘭：恭。

905
00:37:37,100 --> 00:37:38,090
歡迎登機。

906
00:37:38,090 --> 00:37:42,180
好吧，讓我們現在來考慮
一個稍微更惱人的情況，

907
00:37:42,180 --> 00:37:46,350
由此我想插入
像26到這一點。

908
00:37:46,350 --> 00:37:47,090
20？

909
00:37:47,090 --> 00:37:47,590
什麼？

910
00:37:47,590 --> 00:37:50,510
這些are--好事，我們有這樣的筆。

911
00:37:50,510 --> 00:37:51,955
好吧，20。

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
如果有人能得到另一塊
紙準備好了，就在case--所有權利。

914
00:37:57,570 --> 00:37:58,370
呵呵，有意思。

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
嗯，這是一個例子
的講座錯誤。

917
00:38:02,390 --> 00:38:03,894
行，所以你叫什麼名字來著？

918
00:38:03,894 --> 00:38:04,560
聽眾：朱莉婭。

919
00:38:04,560 --> 00:38:07,559
戴維·J·馬蘭：朱莉婭，你可以彈出
出來，假裝你從未在那裡？

920
00:38:07,559 --> 00:38:09,040
OK，這從來沒有發生過。

921
00:38:09,040 --> 00:38:09,680
謝謝。

922
00:38:09,680 --> 00:38:12,180
因此，假設我們要插入
朱成這個鍊錶。

923
00:38:12,180 --> 00:38:13,780
她是20號。

924
00:38:13,780 --> 00:38:15,530
當然，她的
將屬於在

925
00:38:15,530 --> 00:38:17,521
begin--不要在任何地步。

926
00:38:17,521 --> 00:38:20,020
種那麼你的手可
倒空或一些垃圾值。

927
00:38:20,020 --> 00:38:21,210
讓我們告訴了快速的故事。

928
00:38:21,210 --> 00:38:22,980
我指著5號這段時間。

929
00:38:22,980 --> 00:38:23,880
然後我檢查9。

930
00:38:23,880 --> 00:38:25,130
然後我檢查17。

931
00:38:25,130 --> 00:38:26,247
然後我檢查22。

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
我意識到，哦，朱莉婭
需要22日前去。

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
因此，需要做些什麼？

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
誰的手裡需要改變嗎？

938
00:38:36,910 --> 00:38:38,360
Julia的，我的，or--
你叫什麼名字來著？

939
00:38:38,360 --> 00:38:39,230
>> 聽眾：基督教。

940
00:38:39,230 --> 00:38:40,060
>> 戴維·J·馬蘭：基督教還是？

941
00:38:40,060 --> 00:38:40,560
>> 聽眾：安迪。

942
00:38:40,560 --> 00:38:40,905
>> 戴維·J·馬蘭：安迪。

943
00:38:40,905 --> 00:38:41,654
基督教或安迪？

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
安迪需要指向？

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
朱莉婭。

948
00:38:47,341 --> 00:38:47,840
好吧。

949
00:38:47,840 --> 00:38:48,960
所以安迪，你想點的朱莉婭？

950
00:38:48,960 --> 00:38:50,120
但是且慢。

951
00:38:50,120 --> 00:38:53,260
在故事迄今
我是一個排序

952
00:38:53,260 --> 00:38:56,800
在電荷，在這個意義上，
指針的東西，是

953
00:38:56,800 --> 00:38:57,850
在列表中移動。

954
00:38:57,850 --> 00:39:00,800
我們可能對劉德華的名稱，但
有沒有所謂的可變安迪。

955
00:39:00,800 --> 00:39:04,320
我們唯一的其他變量
第一，誰是由加布表示。

956
00:39:04,320 --> 00:39:07,690
>> 因此，這實際上是這樣，為什麼
到目前為止，我們已經沒有必要了。

957
00:39:07,690 --> 00:39:10,846
但現在在屏幕上有
預計值的指針再提起。

958
00:39:10,846 --> 00:39:11,970
因此，讓我更明確。

959
00:39:11,970 --> 00:39:14,820
如果這是指針，我最好
得到一個小更智能

960
00:39:14,820 --> 00:39:15,950
我的迭代。

961
00:39:15,950 --> 00:39:19,580
如果你不介意我的經歷在這裡
再次，指指點點，指指點點。

962
00:39:19,580 --> 00:39:22,500
不過，讓我有一個預計值的指針，
前任的指針，這是

963
00:39:22,500 --> 00:39:24,740
種指著
元我就在。

964
00:39:24,740 --> 00:39:27,330
所以，當我去這裡，現在
我的左手更新。

965
00:39:27,330 --> 00:39:29,370
當我走在這裡我的左手更新。

966
00:39:29,370 --> 00:39:33,090
現在我不僅是一個指針
朱莉婭之後去的元素，

967
00:39:33,090 --> 00:39:36,300
我仍然有一個指針
安迪，之前的元素。

968
00:39:36,300 --> 00:39:39,430
所以，你有機會，基本上，
麵包屑，如果你願意，

969
00:39:39,430 --> 00:39:41,500
到所有必要的指針。

970
00:39:41,500 --> 00:39:43,710
>> 所以，如果我指著
安迪和我還指著

971
00:39:43,710 --> 00:39:47,105
在基督教，他的手
現在應該在別處指出？

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
所以安迪現在可以指向朱莉婭。

974
00:39:51,960 --> 00:39:54,460
朱莉婭現在可以指向基督徒。

975
00:39:54,460 --> 00:39:56,950
因為她能複製我的
右手的指針。

976
00:39:56,950 --> 00:40:00,044
並能有效地使你
回到這裡這個地方。

977
00:40:00,044 --> 00:40:02,460
所以，總之，即使此
正在美國種永

978
00:40:02,460 --> 00:40:04,510
實際更新
鍊錶，實現

979
00:40:04,510 --> 00:40:06,580
該操作
是相對簡單的。

980
00:40:06,580 --> 00:40:10,030
它是一個，兩個，三個
行代碼最終。

981
00:40:10,030 --> 00:40:12,780
但纏的
行的代碼大概

982
00:40:12,780 --> 00:40:16,350
有點邏輯，有效地
問這個問題，我們在哪裡？

983
00:40:16,350 --> 00:40:18,970
難道我們在一開始，
中間還是結束了嗎？

984
00:40:18,970 --> 00:40:21,890
>> 現在，當然也有一些其他的
操作我們有可能實現的。

985
00:40:21,890 --> 00:40:24,880
而這些圖片在這裡只是描述
我們剛剛與人類一樣。

986
00:40:24,880 --> 00:40:26,080
怎麼樣去除？

987
00:40:26,080 --> 00:40:30,650
如果我想，例如，
刪除號碼34或55，

988
00:40:30,650 --> 00:40:34,680
我可能有同樣的代碼，
但我會需要一個或兩個步驟。

989
00:40:34,680 --> 00:40:36,110
因為什麼是新的？

990
00:40:36,110 --> 00:40:40,460
如果我刪除某人的盡頭，
像一些55後34，

991
00:40:40,460 --> 00:40:42,995
什麼也有改變，因為我做到這一點？

992
00:40:42,995 --> 00:40:44,870
我不evict--
你叫什麼名字來著？

993
00:40:44,870 --> 00:40:45,380
>> 聽眾：傑克。

994
00:40:45,380 --> 00:40:46,255
>> 戴維·J·馬蘭：傑克。

995
00:40:46,255 --> 00:40:49,770
我不僅evict--免費傑克，
所以從字面上撥打免費傑克，或者至少

996
00:40:49,770 --> 00:40:53,530
指針有過，但現在
有什麼需要改變與彼得？

997
00:40:53,530 --> 00:40:55,510
他的手好開始朝下。

998
00:40:55,510 --> 00:40:59,300
因為只要我一打電話免費
傑克，如果彼得還指著傑克

999
00:40:59,300 --> 00:41:02,530
因此我繼續穿越
列表和訪問這個指針，

1000
00:41:02,530 --> 00:41:05,650
這時候我們的老朋友分割
故障實際上可能一命嗚呼

1001
00:41:05,650 --> 00:41:07,860
因為我們已經給了
記憶回到傑克。

1002
00:41:07,860 --> 00:41:10,760
>> 你可以呆在那裡
笨拙的只是一瞬間。

1003
00:41:10,760 --> 00:41:13,410
因為我們只是一對夫婦
最終的操作考慮。

1004
00:41:13,410 --> 00:41:15,600
刪除列表的頭部，
或beginning--而這一次的

1005
00:41:15,600 --> 00:41:16,349
有點討厭。

1006
00:41:16,349 --> 00:41:19,640
因為我們要知道，加布
是一種特殊的這一計劃。

1007
00:41:19,640 --> 00:41:21,440
因為事實上，他有自己的指針。

1008
00:41:21,440 --> 00:41:24,860
他不只是被指向，
因為幾乎所有的人在這裡。

1009
00:41:24,860 --> 00:41:28,112
>> 所以當表的標頭是
拆除，誰的手裡現在需要改變嗎？

1010
00:41:28,112 --> 00:41:29,070
你叫什麼名字來著？

1011
00:41:29,070 --> 00:41:29,450
>> 聽眾：恭。

1012
00:41:29,450 --> 00:41:31,408
>> 戴維·J·馬蘭：我是可怕的
在名稱，顯然。

1013
00:41:31,408 --> 00:41:34,011
因此，Christine和加布，
誰的手裡需要改變

1014
00:41:34,011 --> 00:41:36,510
當我們試圖刪除恭，
5號，從圖片？

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
好了，讓我們做加布。

1017
00:41:38,820 --> 00:41:40,950
Gabe的去點，
據推測，在9號。

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
但是，接下來應該發生？

1020
00:41:44,642 --> 00:41:46,600
聽眾：恭應
為null [聽不清]。

1021
00:41:46,600 --> 00:41:50,244
戴維·J·馬蘭：好，我們也許應該
make--聽到“空”的地方。

1022
00:41:50,244 --> 00:41:51,410
聽眾：空和她的自由。

1023
00:41:51,410 --> 00:41:51,855
戴維·J·馬蘭：NULL是什麼？

1024
00:41:51,855 --> 00:41:53,074
聽眾：空和她的自由。

1025
00:41:53,074 --> 00:41:54,490
戴維·J·馬蘭：空和她的自由。

1026
00:41:54,490 --> 00:41:55,422
因此，這是很容易的。

1027
00:41:55,422 --> 00:41:58,380
它是完美的，你現在已經排序
站在那裡，沒有歸屬感。

1028
00:41:58,380 --> 00:42:00,430
因為你已經
從列表中去耦。

1029
00:42:00,430 --> 00:42:02,820
你一直有效
從列表中孤立。

1030
00:42:02,820 --> 00:42:07,770
因此，我們最好稱之為自由現在
恭讓的記憶回來了。

1031
00:42:07,770 --> 00:42:10,240
否則，每次我們
從列表中刪除一個節點

1032
00:42:10,240 --> 00:42:14,230
我們可能會犯名單
短，但實際上不降低

1033
00:42:14,230 --> 00:42:15,096
在存儲器的大小。

1034
00:42:15,096 --> 00:42:17,720
所以，如果我們繼續增加和
添加，添加的東西的清單，

1035
00:42:17,720 --> 00:42:19,280
我的電腦可能會變慢
和慢，

1036
00:42:19,280 --> 00:42:21,740
因為我跑出來的
內存，即使我沒有實際

1037
00:42:21,740 --> 00:42:25,580
用恭的字節
內存了。

1038
00:42:25,580 --> 00:42:28,500
>> 那麼，到底還有其他
場景course--去除，

1039
00:42:28,500 --> 00:42:30,640
在中間，除去
到了最後，正如我們所看到。

1040
00:42:30,640 --> 00:42:32,348
但更有趣的
現在的挑戰是

1041
00:42:32,348 --> 00:42:34,770
將是準確地考慮
運行時間是什麼。

1042
00:42:34,770 --> 00:42:36,640
這樣不僅可以讓您的
紙片，如果，加布，

1043
00:42:36,640 --> 00:42:38,640
你不會介意
每個人都有壓力球。

1044
00:42:38,640 --> 00:42:42,100
非常感謝你對我們的鍊錶
這裡的志願者，如果你能。

1045
00:42:42,100 --> 00:42:45,320
>> [掌聲]

1046
00:42:45,320 --> 00:42:46,700
>> 戴維·J·馬蘭：好吧。

1047
00:42:46,700 --> 00:42:51,110
因此，一對夫婦的分析
問題的話，如果我能。

1048
00:42:51,110 --> 00:42:59,670
我們以前見過這個符號，
大O和歐米茄，上限

1049
00:42:59,670 --> 00:43:02,520
和上下限
運行一些算法的時間。

1050
00:43:02,520 --> 00:43:04,950
所以讓我們只考慮
幾個問題。

1051
00:43:04,950 --> 00:43:07,090
>> 一，我們說這
之前，有什麼運行

1052
00:43:07,090 --> 00:43:10,647
搜索了時間
在大澳條款清單？

1053
00:43:10,647 --> 00:43:13,480
什麼是上限運行
搜索鏈接列表的時間

1054
00:43:13,480 --> 00:43:16,340
通過我們的志願者在這裡實現的？

1055
00:43:16,340 --> 00:43:17,820
這n個大O，線性的。

1056
00:43:17,820 --> 00:43:20,630
由於在最壞的情況下，
元素，如55，

1057
00:43:20,630 --> 00:43:23,830
我們可能會尋找可能的地方
傑克，一路在末端。

1058
00:43:23,830 --> 00:43:28,250
不幸的是，一個數組不同
我們不能看上這個時候。

1059
00:43:28,250 --> 00:43:31,820
雖然我們所有的人都是
排序由小分子，5，

1060
00:43:31,820 --> 00:43:35,900
一路到更大的元素，
55，這通常是一件好事。

1061
00:43:35,900 --> 00:43:38,815
但到底是什麼這樣的假設
不再允許我們做什麼？

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
聽眾：[聽不清]

1064
00:43:40,650 --> 00:43:40,920
戴維·J·馬蘭：再說一遍嗎？

1065
00:43:40,920 --> 00:43:41,800
聽眾：隨機訪問。

1066
00:43:41,800 --> 00:43:43,049
戴維·J·馬蘭：隨機訪問。

1067
00:43:43,049 --> 00:43:46,330
而反過來，這意味著我們不能
再使用弱零，直覺，

1068
00:43:46,330 --> 00:43:49,365
而顯而易見使用二進制的
搜索和分而治之。

1069
00:43:49,365 --> 00:43:51,240
因為即使我們
人類能明顯

1070
00:43:51,240 --> 00:43:54,610
看到劉德華或基督徒都
大致在表的中間，

1071
00:43:54,610 --> 00:43:57,670
我們只知道，作為一個
計算機通過略讀列表

1072
00:43:57,670 --> 00:43:59,029
從一開始。

1073
00:43:59,029 --> 00:44:00,570
因此，我們已經放棄了隨機訪問。

1074
00:44:00,570 --> 00:44:04,380
>> n個這麼大O，現在是上
必將在我們的搜索時間。

1075
00:44:04,380 --> 00:44:07,920
那麼我們的搜索的歐米茄？

1076
00:44:07,920 --> 00:44:11,535
什麼是搜索上下限
在此列表中的一些數字？

1077
00:44:11,535 --> 00:44:12,410
聽眾：[聽不清]

1078
00:44:12,410 --> 00:44:13,040
戴維·J·馬蘭：再說一遍嗎？

1079
00:44:13,040 --> 00:44:13,420
聽眾：一。

1080
00:44:13,420 --> 00:44:13,800
戴維·J·馬蘭：一。

1081
00:44:13,800 --> 00:44:14,760
因此，一定的時間。

1082
00:44:14,760 --> 00:44:17,020
在最好的情況下，克里斯汀是
的確在列表的開頭。

1083
00:44:17,020 --> 00:44:19,020
我們正在尋找
5號，所以我們找到了她。

1084
00:44:19,020 --> 00:44:19,787
所以，沒什麼大不了的。

1085
00:44:19,787 --> 00:44:22,370
但她一定是在
開始列表在此情況下的。

1086
00:44:22,370 --> 00:44:23,745
那麼什麼樣刪除？

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
如果你想刪除一個元素？

1089
00:44:26,300 --> 00:44:29,200
什麼是上界和下界
有關刪除的東西從鏈接

1090
00:44:29,200 --> 00:44:29,699
上市？

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
聽眾：[聽不清]

1093
00:44:36,070 --> 00:44:36,420
戴維·J·馬蘭：再說一遍嗎？

1094
00:44:36,420 --> 00:44:37,067
聽眾：不適用。

1095
00:44:37,067 --> 00:44:38,900
戴維·J·馬蘭：n為
確的上限。

1096
00:44:38,900 --> 00:44:41,700
由於在最壞的情況下，我們嘗試
刪除傑克，就像我們剛剛做。

1097
00:44:41,700 --> 00:44:43,050
他一路底。

1098
00:44:43,050 --> 00:44:45,419
把我們永遠的，或
n步找到他。

1099
00:44:45,419 --> 00:44:46,460
所以這是一個上限。

1100
00:44:46,460 --> 00:44:47,430
這是線性的，肯定的。

1101
00:44:47,430 --> 00:44:50,970
和最好的情況下的運行時間，或
在最好的情況下，下限

1102
00:44:50,970 --> 00:44:51,975
將恆定時間。

1103
00:44:51,975 --> 00:44:54,600
因為也許我們嘗試刪除
克里斯蒂娜，我們只是很幸運

1104
00:44:54,600 --> 00:44:55,558
她開頭。

1105
00:44:55,558 --> 00:44:56,350
現在，等待一分鐘。

1106
00:44:56,350 --> 00:44:59,370
加布也之初，
我們也必須更新加布。

1107
00:44:59,370 --> 00:45:01,150
所以這不只是一個步驟。

1108
00:45:01,150 --> 00:45:04,210
那麼，這確實是恆定的
時，在最好的情況下，

1109
00:45:04,210 --> 00:45:06,345
去除的最小元素？

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
它，即使它可能是兩個，
3，甚至是100行的代碼，

1112
00:45:10,960 --> 00:45:14,000
如果它的相同數量的
行，而不是在一些環路，

1113
00:45:14,000 --> 00:45:16,577
和獨立的大小
名單的，絕對。

1114
00:45:16,577 --> 00:45:18,660
刪除的元素
在列表的開頭，

1115
00:45:18,660 --> 00:45:21,940
即使我們要處理
加布，仍然是固定的時間。

1116
00:45:21,940 --> 00:45:24,220
>> 因此，這似乎是一個
巨大的倒退。

1117
00:45:24,220 --> 00:45:27,000
什麼時間是浪費
如果，在週1週和

1118
00:45:27,000 --> 00:45:30,250
零，我們不但
偽代碼，但實際的代碼

1119
00:45:30,250 --> 00:45:35,780
實施東西的日誌
基N，或登錄，而是n的基地2個，

1120
00:45:35,780 --> 00:45:37,150
在其運行時間條件。

1121
00:45:37,150 --> 00:45:40,710
那麼，為什麼赫克，我們將要開始
使用類似鍊錶？

1122
00:45:40,710 --> 00:45:41,517
是啊。

1123
00:45:41,517 --> 00:45:44,022
>> 聽眾：所以，你可以添加
元件的陣列。

1124
00:45:44,022 --> 00:45:46,230
戴維·J·馬蘭：所以，你可以
元素添加到數組中。

1125
00:45:46,230 --> 00:45:47,550
而這也是主題。

1126
00:45:47,550 --> 00:45:49,740
我們將繼續看到
這個，這個權衡，多

1127
00:45:49,740 --> 00:45:51,573
就像我們已經看到了
權衡合併排序。

1128
00:45:51,573 --> 00:45:54,606
我們真的可以加快
搜索或排序，相反，

1129
00:45:54,606 --> 00:45:57,480
如果我們花多一點的空間，
有記憶的附加塊

1130
00:45:57,480 --> 00:45:58,760
或數組的歸併排序。

1131
00:45:58,760 --> 00:46:01,270
但是，我們花更多
空間，但我們節省時間。

1132
00:46:01,270 --> 00:46:04,820
在這種情況下，我們
放棄時間，但我們

1133
00:46:04,820 --> 00:46:08,170
獲得的靈活性，
活力，如果你願意，

1134
00:46:08,170 --> 00:46:10,280
這無疑是一個積極的功能。

1135
00:46:10,280 --> 00:46:11,520
>> 我們也花了空間。

1136
00:46:11,520 --> 00:46:13,710
在什麼意義上是一個鏈接
列出更貴

1137
00:46:13,710 --> 00:46:15,700
在空間不是一個數組方面？

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
哪裡是多餘的空間來的呢？

1140
00:46:19,920 --> 00:46:20,460
是嗎？

1141
00:46:20,460 --> 00:46:21,800
>> 聽眾：[聽不清]指針。

1142
00:46:21,800 --> 00:46:23,310
>> 戴維·J·馬蘭：是的，我們
也具有指針。

1143
00:46:23,310 --> 00:46:25,560
因此，這是minorly煩人
在不再是

1144
00:46:25,560 --> 00:46:27,780
存儲I只是一個int
表示一個int。

1145
00:46:27,780 --> 00:46:30,990
我存儲一個int和
指針，這也是32位。

1146
00:46:30,990 --> 00:46:33,470
所以，我從字面上倍增
所涉及的空間量。

1147
00:46:33,470 --> 00:46:36,040
所以這是一個權衡，但
這是在整數的情況下。

1148
00:46:36,040 --> 00:46:39,580
假設你沒有存放整型，
但是假設每個這些矩形

1149
00:46:39,580 --> 00:46:43,290
或者這些人被代表
一個字，一個英語單詞

1150
00:46:43,290 --> 00:46:46,430
可能是五個字符，10
人物，更可能。

1151
00:46:46,430 --> 00:46:49,940
然後加入只有32多個位
也許是少了一個大問題。

1152
00:46:49,940 --> 00:46:52,160
>> 如果每個學生什麼
在演示

1153
00:46:52,160 --> 00:46:55,107
是字面上的學生結構的
有名字和房子，也許

1154
00:46:55,107 --> 00:46:57,065
電話號碼和Twitter
處理等。

1155
00:46:57,065 --> 00:46:59,564
因此，所有的領域，我們開始
說起那天，

1156
00:46:59,564 --> 00:47:02,410
更大不了的
我們的節點變得更加有趣

1157
00:47:02,410 --> 00:47:05,972
和大花，嗯，一個額外的
指針只是將它們連接在一起。

1158
00:47:05,972 --> 00:47:07,180
不過說實在的，這是一個權衡。

1159
00:47:07,180 --> 00:47:09,560
事實上，代碼
更複雜的，因為你會

1160
00:47:09,560 --> 00:47:11,770
看到通過略讀
這特殊的例子。

1161
00:47:11,770 --> 00:47:14,302
但是，如果有什麼
這裡的一些制勝法寶。

1162
00:47:14,302 --> 00:47:17,010
如果我們不採取一步
倒退，但一個巨大的進步

1163
00:47:17,010 --> 00:47:19,180
並實現數據
結構，通過它我們

1164
00:47:19,180 --> 00:47:22,870
可以找到像傑克或元素
恭或任何其他元素

1165
00:47:22,870 --> 00:47:25,870
在這個陣列中的真正的固定時間？

1166
00:47:25,870 --> 00:47:26,920
搜索是恆定的。

1167
00:47:26,920 --> 00:47:28,320
刪除是恆​​定的。

1168
00:47:28,320 --> 00:47:29,570
插入件是恆定的。

1169
00:47:29,570 --> 00:47:32,260
所有這些操作都是恆定的。

1170
00:47:32,260 --> 00:47:33,750
這將是我們的制勝法寶。

1171
00:47:33,750 --> 00:47:36,690
而這正是我們
下次還會回升。

1172
00:47:36,690 --> 00:47:38,600
到時候見。

1173
00:47:38,600 --> 00:47:39,371