1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> 揚聲器1：好吧，所以這是
CS50這是五個星期結束。

3
00:00:15,860 --> 00:00:19,220
而記得我們最後一次
開始尋找在票友數據

4
00:00:19,220 --> 00:00:22,310
即開始解決結構
問題，即開始引入

5
00:00:22,310 --> 00:00:25,640
新的問題，但關鍵就在這
是線程的排序，我們

6
00:00:25,640 --> 00:00:27,940
開始做從節點到節點。

7
00:00:27,940 --> 00:00:30,085
因此，這當然是
一個單向鍊錶。

8
00:00:30,085 --> 00:00:31,960
而由單鍊錶，
我的意思是只有一個

9
00:00:31,960 --> 00:00:33,380
每個這些節點之間線程。

10
00:00:33,380 --> 00:00:35,890
原來，你可以做票友
像雙向鍊錶

11
00:00:35,890 --> 00:00:38,470
因此，你有一個箭頭
要在兩個方向上，這

12
00:00:38,470 --> 00:00:40,320
可以幫助具有一定的效率。

13
00:00:40,320 --> 00:00:42,000
但這個問題是否解決？

14
00:00:42,000 --> 00:00:43,500
有什麼問題沒有解決這個？

15
00:00:43,500 --> 00:00:46,620
為什麼我們關心在星期一？

16
00:00:46,620 --> 00:00:49,820
為什麼在理論上，我們沒在意週一？

17
00:00:49,820 --> 00:00:50,630
它有什麼作用？

18
00:00:50,630 --> 00:00:51,950
>> 聽眾：我們可以動態地調整它的大小。

19
00:00:51,950 --> 00:00:53,740
>> 揚聲器1：OK，所以我們可以
動態地調整其大小。

20
00:00:53,740 --> 00:00:54,710
幹得好你們倆。

21
00:00:54,710 --> 00:00:57,560
所以，你可以動態調整這個
數據結構，而陣列，

22
00:00:57,560 --> 00:01:00,760
回想一下，你必須知道
先驗多少空間你想

23
00:01:00,760 --> 00:01:03,870
如果你需要更多一點的
空間，你是那種運氣。

24
00:01:03,870 --> 00:01:05,560
你必須創建一個全新的陣列。

25
00:01:05,560 --> 00:01:07,893
你必須將所有的
從一個到另一個數據，

26
00:01:07,893 --> 00:01:10,600
最終釋放舊陣列
如果可以的話，然後繼續。

27
00:01:10,600 --> 00:01:13,891
這只是感覺非常昂貴，非常
效率低，而且確實可以。

28
00:01:13,891 --> 00:01:14,890
但是，這是不是所有的好。

29
00:01:14,890 --> 00:01:18,180
我們付出的代價，究竟是什麼1
較為明顯的價格上漲，我們

30
00:01:18,180 --> 00:01:20,550
通過使用鍊錶買單？

31
00:01:20,550 --> 00:01:22,825
>> 聽眾：我們必須使用
為每一個雙層空間。

32
00:01:22,825 --> 00:01:25,200
揚聲器1：是啊，所以我們需要
至少兩倍的空間。

33
00:01:25,200 --> 00:01:27,700
事實上，我意識到這張照片的
甚至有點誤導，

34
00:01:27,700 --> 00:01:32,200
因為在許多現代的CS50 IDE
計算機，一個指針或地址

35
00:01:32,200 --> 00:01:33,700
事實上並非四個字節。

36
00:01:33,700 --> 00:01:36,090
這是很多時候，這些
天8字節，這

37
00:01:36,090 --> 00:01:38,530
裝置的底部最
在現實中的矩形有

38
00:01:38,530 --> 00:01:40,900
是那種兩倍
大如我所繪製的，

39
00:01:40,900 --> 00:01:44,409
您正在使用三倍的手段
多的空間，我們可能有其他方式。

40
00:01:44,409 --> 00:01:46,700
現在，在同一時間，我們
還在說話字節，對不對？

41
00:01:46,700 --> 00:01:49,140
我們不一定講
MB或GB，

42
00:01:49,140 --> 00:01:51,000
除非這些數據結構變大。

43
00:01:51,000 --> 00:01:54,510
>> 所以，今天我們開始考慮
我們可以如何發掘數據

44
00:01:54,510 --> 00:01:57,310
更有效地如果
事實上，數據變得更大。

45
00:01:57,310 --> 00:02:00,360
但是，讓我們試著規範化
操作第一

46
00:02:00,360 --> 00:02:02,460
你可以在這些幹什麼
種數據結構。

47
00:02:02,460 --> 00:02:04,790
因此，像一個鏈接
清單普遍支持

48
00:02:04,790 --> 00:02:07,514
操作像刪除，
插入，和搜索。

49
00:02:07,514 --> 00:02:08,639
什麼做我的意思？

50
00:02:08,639 --> 00:02:11,222
這只是意味著，通常情況下，
如果人們使用鍊錶，

51
00:02:11,222 --> 00:02:14,287
他們或者其他人實施
如刪除，插入功能，

52
00:02:14,287 --> 00:02:16,120
和搜索，這樣你就可以
確實做了什麼

53
00:02:16,120 --> 00:02:18,030
有用的數據結構。

54
00:02:18,030 --> 00:02:20,760
因此，讓我們快速瀏覽一下
我們如何可能實現

55
00:02:20,760 --> 00:02:24,530
一些代碼，一個鍊錶如下。

56
00:02:24,530 --> 00:02:27,885
>> 所以，這只是一些C代碼，
甚至沒有一個完整的程序

57
00:02:27,885 --> 00:02:29,260
我真的很快刮起了一陣。

58
00:02:29,260 --> 00:02:32,300
這不是在網上分銷
碼，因為它不會實際運行。

59
00:02:32,300 --> 00:02:33,790
但是請注意，我只是
有評論說，

60
00:02:33,790 --> 00:02:36,130
點點點，有什麼東西
在那裡，點點點，東西在那裡。

61
00:02:36,130 --> 00:02:38,410
而且，我們只是看看
什麼多汁的部件。

62
00:02:38,410 --> 00:02:40,790
因此，在三線，
記得，這是現在

63
00:02:40,790 --> 00:02:45,960
我們提出聲明最後一個節點
時間，這些矩形物體中的一個。

64
00:02:45,960 --> 00:02:48,790
它具有我們稱之為為N的INT，
但我們可以把它叫做什麼，

65
00:02:48,790 --> 00:02:51,920
再一個結構節點明星叫旁邊。

66
00:02:51,920 --> 00:02:55,520
而僅僅是明確的，即第二
線，對線6條，那是什麼？

67
00:02:55,520 --> 00:02:57,930
它是什麼做的我們呢？

68
00:02:57,930 --> 00:03:01,044
因為它確實看起來更
神秘的比我們平常的變量。

69
00:03:01,044 --> 00:03:02,740
>> 聽眾：這使得它搬過來的。

70
00:03:02,740 --> 00:03:04,650
>> 揚聲器1：這使得它搬過來的。

71
00:03:04,650 --> 00:03:08,580
和更精確，
它將存儲的地址

72
00:03:08,580 --> 00:03:11,582
這意味著是該節點的
語義旁邊，對不對？

73
00:03:11,582 --> 00:03:13,540
所以它不會
不一定移動任何東西。

74
00:03:13,540 --> 00:03:15,290
它只是要
存儲一個值，這是

75
00:03:15,290 --> 00:03:17,170
將是地址
一些其他節點的，

76
00:03:17,170 --> 00:03:20,810
這就是為什麼我們說結構
節點明星，明星表示

77
00:03:20,810 --> 00:03:22,370
的指針或地址。

78
00:03:22,370 --> 00:03:26,390
好了，現在，如果你認為我們有
這款N提供給我們，讓我們

79
00:03:26,390 --> 00:03:29,490
假設別人有
插入一大堆整數

80
00:03:29,490 --> 00:03:30,400
成一個鍊錶。

81
00:03:30,400 --> 00:03:35,640
並且鍊錶是
一些點指向

82
00:03:35,640 --> 00:03:39,040
一個變量調用列表的
在這裡作為參數傳遞，

83
00:03:39,040 --> 00:03:43,120
我怎麼去行
14實現搜索？

84
00:03:43,120 --> 00:03:45,990
換句話說，如果我實現
功能，其目的在生活中

85
00:03:45,990 --> 00:03:48,889
是採取一個int，然後
開始的鍊錶，

86
00:03:48,889 --> 00:03:50,430
這是一個指向該鏈接的表。

87
00:03:50,430 --> 00:03:52,992
像第一，誰我認為大衛
是我們的志願者在週一，

88
00:03:52,992 --> 00:03:54,700
他指著
整個鍊錶，

89
00:03:54,700 --> 00:03:57,820
就好像我們傳遞
大衛在這裡我們的論點。

90
00:03:57,820 --> 00:03:59,990
我們如何去遍歷這個名單？

91
00:03:59,990 --> 00:04:04,640
嗯，事實證明，即使
指針是比較新的，現在對我們來說，

92
00:04:04,640 --> 00:04:07,010
我們可以相對做到這一點
直截了當。

93
00:04:07,010 --> 00:04:09,500
>> 我要繼續前進，
聲明臨時變量

94
00:04:09,500 --> 00:04:12,364
按照慣例，只是走
被稱為指針或PTR，

95
00:04:12,364 --> 00:04:14,030
但你可以把它稱為任何你想要的。

96
00:04:14,030 --> 00:04:16,470
而且我要初始化
它到列表的開頭。

97
00:04:16,470 --> 00:04:20,050
所以，你可以種想到這
作為我的老師有一天，

98
00:04:20,050 --> 00:04:23,580
那種指著別人
在我們人類作為志願者。

99
00:04:23,580 --> 00:04:26,470
所以，我是一個臨時變量，它是
只是指向同一件事

100
00:04:26,470 --> 00:04:31,390
我們不約而同地命名
志願者大衛也指出。

101
00:04:31,390 --> 00:04:35,440
現在，當指針
不為空，因為召回

102
00:04:35,440 --> 00:04:40,350
那空是一些特殊的標記值
所述標定列表的末尾，

103
00:04:40,350 --> 00:04:44,280
因此，雖然我不指著
地面像我們過去的志願者

104
00:04:44,280 --> 00:04:47,190
是，讓我們繼續
並做到以下幾點。

105
00:04:47,190 --> 00:04:51,820
如果pointer--和那種我現在想
做我們的學生做了

106
00:04:51,820 --> 00:04:57,410
結構 - 如果指針點下一個
equals--相反，如果指針點N等於

107
00:04:57,410 --> 00:05:02,290
等於變量N，所述
這就是被傳入的說法，

108
00:05:02,290 --> 00:05:05,370
那麼我想繼續
說返回true。

109
00:05:05,370 --> 00:05:11,020
我已經發現了內部數N
我的一個鍊錶節點。

110
00:05:11,020 --> 00:05:13,500
但點不再
工作在這樣的背景下，

111
00:05:13,500 --> 00:05:17,260
因為指針，PTR，是
確實是一個指針，地址，

112
00:05:17,260 --> 00:05:20,632
我們實際上可以精彩
使用最後一張語法

113
00:05:20,632 --> 00:05:22,590
那種品牌：
直觀感覺，實際上

114
00:05:22,590 --> 00:05:27,870
用一個箭頭這裡，這意味著從去
該地址中的整數那裡。

115
00:05:27,870 --> 00:05:30,160
所以這是非常相似
精神點運算符，

116
00:05:30,160 --> 00:05:33,860
但因為指針不是指針
而不是實際的結構本身，

117
00:05:33,860 --> 00:05:35,380
我們只是用箭頭。

118
00:05:35,380 --> 00:05:40,620
>> 因此，如果當前節點是我的
臨時變量，我指著

119
00:05:40,620 --> 00:05:43,060
是不是N，我該怎麼想幹什麼？

120
00:05:43,060 --> 00:05:45,910
好了，我的志願者
我們曾在這裡的一天，

121
00:05:45,910 --> 00:05:49,710
如果我的第一個人是不是一個我
想，也許第二個人是不是

122
00:05:49,710 --> 00:05:52,660
一個我想要的，第三，我
需要保持身體移動。

123
00:05:52,660 --> 00:05:54,690
像我怎麼通過列表步驟？

124
00:05:54,690 --> 00:05:57,470
當我們有一個數組，你
只是不喜歡我加再加。

125
00:05:57,470 --> 00:06:03,660
但在這種情況下，它足以
做指針，獲取，指針，下一個。

126
00:06:03,660 --> 00:06:07,580
換句話說，下一個字段
就像所有的左手

127
00:06:07,580 --> 00:06:10,880
我們在週一志願者
分別使用以指向某些其它節點。

128
00:06:10,880 --> 00:06:12,890
那是他們的下一個鄰居。

129
00:06:12,890 --> 00:06:17,060
>> 所以，如果我想一步，通過這個名單，
我不能只是做我加再加了，

130
00:06:17,060 --> 00:06:20,120
我反而不得不說
我，指針，是怎麼回事

131
00:06:20,120 --> 00:06:24,650
等於任何下一個字段是
下一字段，下一個字段是

132
00:06:24,650 --> 00:06:28,350
下面所有這些左手
我們有在舞台上指點

133
00:06:28,350 --> 00:06:30,000
一些後續值。

134
00:06:30,000 --> 00:06:32,590
如果我打通
那整個循環，

135
00:06:32,590 --> 00:06:39,330
最後，我打空沒有
發現ñ然而，我剛剛返回false。

136
00:06:39,330 --> 00:06:44,100
如此反复，所有我們在這裡做，
按照剛才的圖片，

137
00:06:44,100 --> 00:06:47,840
開始通過指向
開頭的名單大概。

138
00:06:47,840 --> 00:06:50,970
然後我檢查，是價值
我在尋找等於九？

139
00:06:50,970 --> 00:06:52,650
如果是的話，我還真和我完成了。

140
00:06:52,650 --> 00:06:56,450
如果沒有，我更新了我的手，
AKA指針，指向

141
00:06:56,450 --> 00:06:59,540
下一個箭頭的位置，
那麼下一個箭頭的位置，

142
00:06:59,540 --> 00:07:00,480
和下一個。

143
00:07:00,480 --> 00:07:03,770
我只是在這個數組中行走。

144
00:07:03,770 --> 00:07:06,010
>> 如此反复，誰在乎呢？

145
00:07:06,010 --> 00:07:07,861
什麼樣的事情，這是一種成分呢？

146
00:07:07,861 --> 00:07:10,360
嗯，記得我們介紹
棧的概念，這

147
00:07:10,360 --> 00:07:15,400
是一個抽象數據類型的範圍內，因為它是
不是C的東西，它不是一個CS50的事情，

148
00:07:15,400 --> 00:07:19,430
這是一個抽象的概念，在這一理念
堆疊的東西上彼此之上

149
00:07:19,430 --> 00:07:21,820
可以在實施
不同的方式束。

150
00:07:21,820 --> 00:07:25,600
我們提出了一種方法是用
陣列，或具有一個鍊錶。

151
00:07:25,600 --> 00:07:29,570
而事實證明，規範地，一
棧支持至少兩個操作。

152
00:07:29,570 --> 00:07:32,320
而時髦的話是推，以
推動東西壓入堆棧，

153
00:07:32,320 --> 00:07:34,770
像在一個新的盤
食堂，或流行，

154
00:07:34,770 --> 00:07:39,000
這意味著以除去最上層
從堆棧中的餐盤

155
00:07:39,000 --> 00:07:41,500
大廳裡，然後也許有些
其他操作為好。

156
00:07:41,500 --> 00:07:45,770
那麼，如何可能，我們定義結構
我們現在調用堆棧？

157
00:07:45,770 --> 00:07:50,020
>> 好了，我們有所有必要的
語法我們所掌握的C.我說，

158
00:07:50,020 --> 00:07:53,830
給我一個類型定義
一摞內部的結構，

159
00:07:53,830 --> 00:07:58,030
我要說的是一個數組，
一大堆的數字，然後大小。

160
00:07:58,030 --> 00:08:00,930
因此，換句話說，如果我想
在代碼來實現這一點，

161
00:08:00,930 --> 00:08:03,830
讓我去那種公正，
畫什麼，這是說。

162
00:08:03,830 --> 00:08:06,317
因此，這是說，給我一個
那一定陣列結構，

163
00:08:06,317 --> 00:08:09,400
我不知道是什麼能力，
這顯然有些不變，我已經

164
00:08:09,400 --> 00:08:10,858
其他地方定義，這很好。

165
00:08:10,858 --> 00:08:15,260
但是，假如這只是之一，
二，三，四，五。

166
00:08:15,260 --> 00:08:16,700
所以容量為5。

167
00:08:16,700 --> 00:08:21,730
裡面這個元素我
結構將被稱為數字。

168
00:08:21,730 --> 00:08:24,020
然後，我需要
其他變量明顯

169
00:08:24,020 --> 00:08:27,814
最初我打算叫大小
到規定初始化為零。

170
00:08:27,814 --> 00:08:29,730
如果有什麼的
堆棧，大小是零，

171
00:08:29,730 --> 00:08:31,420
而且它在數量上的垃圾值。

172
00:08:31,420 --> 00:08:33,450
我不知道裡面有什麼了，只是還沒有。

173
00:08:33,450 --> 00:08:36,059
>> 所以，如果我要推
東西壓入堆棧，

174
00:08:36,059 --> 00:08:40,780
假設我調用函數推，並
我說推50，喜歡50號，

175
00:08:40,780 --> 00:08:44,090
在這裡，你會建議
我畫它在這個數組？

176
00:08:44,090 --> 00:08:47,124
有五種不同的可能的答案。

177
00:08:47,124 --> 00:08:48,790
你想去哪裡推的50號？

178
00:08:48,790 --> 00:08:51,899
如果這裡的目標，再次撥打
功能推，傳遞一個參數

179
00:08:51,899 --> 00:08:52,940
50，我在哪裡放呢？

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
五possible-- 20％的機率
的猜測正確。

182
00:08:59,052 --> 00:08:59,896
是嗎？

183
00:08:59,896 --> 00:09:00,740
>> 聽眾：最右。

184
00:09:00,740 --> 00:09:01,990
>> 揚聲器1：最右。

185
00:09:01,990 --> 00:09:08,359
現在有25％的機率
的猜測正確。

186
00:09:08,359 --> 00:09:09,650
所以這實際上是罰款。

187
00:09:09,650 --> 00:09:12,770
按照慣例，我會說一個數組，
我們一般將開始在左邊，

188
00:09:12,770 --> 00:09:14,519
但我們可以肯定
開始在合適的。

189
00:09:14,519 --> 00:09:17,478
因此，這裡的擾流板會是我
可能將其繪製在左邊，

190
00:09:17,478 --> 00:09:20,060
就像在一個正常的數組，其中
我開始從左到右。

191
00:09:20,060 --> 00:09:21,780
但是，如果你可以翻轉
算術，罰款。

192
00:09:21,780 --> 00:09:23,060
這只是不是常規的。

193
00:09:23,060 --> 00:09:24,880
好吧，我需要做一個
更多的變化，雖然。

194
00:09:24,880 --> 00:09:27,710
現在，我已經把東西
壓入堆棧，接下來會發生什麼？

195
00:09:27,710 --> 00:09:29,400
>> 好吧，我得增加尺寸。

196
00:09:29,400 --> 00:09:32,600
因此，讓我繼續前進，只是
更新這，這是零。

197
00:09:32,600 --> 00:09:35,950
而不是現在，我要去
放中的值之一。

198
00:09:35,950 --> 00:09:39,460
現在假設我推另一
數壓入堆棧，如51。

199
00:09:39,460 --> 00:09:42,680
好了，我一定要多一個
變化，這是向上的大小兩種。

200
00:09:42,680 --> 00:09:46,100
再假設我推多了一個
數入堆棧像61，

201
00:09:46,100 --> 00:09:52,530
現在我需要更新的大小多一個
時間，並獲得值3作為大小。

202
00:09:52,530 --> 00:09:54,690
現在假設我叫流行。

203
00:09:54,690 --> 00:09:57,250
現在流行，按照慣例，
不帶參數。

204
00:09:57,250 --> 00:10:00,430
用棧，整
點盤隱喻

205
00:10:00,430 --> 00:10:03,450
是你沒有自由裁量權
去得到那個盤子，你所能做的

206
00:10:03,450 --> 00:10:06,330
是流行最上面的
堆棧，只是因為。

207
00:10:06,330 --> 00:10:08,010
這就是這個數據結構一樣。

208
00:10:08,010 --> 00:10:12,250
>> 因此，通過這種邏輯，如果我
要說流行，會發生什麼了嗎？

209
00:10:12,250 --> 00:10:13,080
所以61。

210
00:10:13,080 --> 00:10:15,402
那麼，什麼是真正的計算機
打算做的內存？

211
00:10:15,402 --> 00:10:16,610
什麼是我的代碼有什麼關係？

212
00:10:16,610 --> 00:10:20,330
你會建議
我們改變在屏幕上？

213
00:10:20,330 --> 00:10:23,410
應該怎麼改？

214
00:10:23,410 --> 00:10:24,960
對不起？

215
00:10:24,960 --> 00:10:26,334
所以我們擺脫61。

216
00:10:26,334 --> 00:10:27,500
所以，我絕對可以做到這一點。

217
00:10:27,500 --> 00:10:28,640
我可以擺脫61。

218
00:10:28,640 --> 00:10:30,980
然後還有什麼其他
改變需要發生？

219
00:10:30,980 --> 00:10:33,160
尺寸可能有回去兩種。

220
00:10:33,160 --> 00:10:34,210
所以，這很好。

221
00:10:34,210 --> 00:10:36,690
但是且慢，大小
剛才是三。

222
00:10:36,690 --> 00:10:38,240
讓我們做一個快速的完整性檢查。

223
00:10:38,240 --> 00:10:41,810
我們是怎麼知道我們
想擺脫的61？

224
00:10:41,810 --> 00:10:42,760
因為我們大跌眼鏡。

225
00:10:42,760 --> 00:10:46,450
所以我有第二個屬性的大小。

226
00:10:46,450 --> 00:10:48,470
>> 等一下，我
回想起2週

227
00:10:48,470 --> 00:10:51,660
當我們開始談論
陣列，在這位置為零，

228
00:10:51,660 --> 00:10:55,920
這是位置之一，這是位置
二，這是位置三個，四個，

229
00:10:55,920 --> 00:10:58,460
它看起來像
大小之間的關係

230
00:10:58,460 --> 00:11:02,780
而我想要的元素刪除
從陣列似乎只是什麼？

231
00:11:02,780 --> 00:11:05,120
尺寸減一。

232
00:11:05,120 --> 00:11:07,786
所以，這就是如何為人類
我們知道61是第一位的。

233
00:11:07,786 --> 00:11:09,160
怎麼樣的電腦會知道？

234
00:11:09,160 --> 00:11:11,701
當你的代碼，你很可能
想做大小減一，

235
00:11:11,701 --> 00:11:14,950
所以三減一為兩個，並且
意味著我們要擺脫61。

236
00:11:14,950 --> 00:11:18,000
然後，我們的確可以更新
這樣大小的體積，現在

237
00:11:18,000 --> 00:11:20,300
進入三到只有兩個。

238
00:11:20,300 --> 00:11:24,520
而剛需迂腐，我要去
提議我做的，對不對？

239
00:11:24,520 --> 00:11:27,660
你直觀地提出
正確我應該擺脫61。

240
00:11:27,660 --> 00:11:30,700
但是，有一種沒有我
那種擺脫了61？

241
00:11:30,700 --> 00:11:33,790
我已經有效地忘記
它的實際存在。

242
00:11:33,790 --> 00:11:37,680
而回想起PSET4，如果你讀過
有關取證的文章中，PDF

243
00:11:37,680 --> 00:11:40,780
我們有你們看，或者你
將讀取本週PSET4。

244
00:11:40,780 --> 00:11:44,300
回想一下，這其實是有密切關係的
計算機取證的整體思路。

245
00:11:44,300 --> 00:11:47,820
什麼是電腦一般不為
它只是忘記在那裡的東西是，

246
00:11:47,820 --> 00:11:51,300
但它並沒有去和像
試著刮出來或重寫

247
00:11:51,300 --> 00:11:54,560
這些位與零和一
或一些其它的隨機圖案

248
00:11:54,560 --> 00:11:56,690
除非你自己這樣做的故意。

249
00:11:56,690 --> 00:11:58,930
所以，你的直覺是
好吧，讓我們擺脫61。

250
00:11:58,930 --> 00:12:00,650
但在現實中，我們沒有理會。

251
00:12:00,650 --> 00:12:04,040
我們只需要忘記，
它的存在，通過改變我們的規模。

252
00:12:04,040 --> 00:12:05,662
>> 現在有這個堆棧的一個問題。

253
00:12:05,662 --> 00:12:07,620
如果我繼續推動東西
壓入堆棧，什麼是

254
00:12:07,620 --> 00:12:11,167
顯然不會發生
在短短的幾分鐘時間？

255
00:12:11,167 --> 00:12:12,500
我們將用盡空間。

256
00:12:12,500 --> 00:12:13,580
而我們該怎麼辦？

257
00:12:13,580 --> 00:12:14,680
那種我們搞砸了。

258
00:12:14,680 --> 00:12:19,000
此實現不讓
我們調整陣列，因為使用

259
00:12:19,000 --> 00:12:21,240
這個語法，如果你
回想起每週二，

260
00:12:21,240 --> 00:12:23,520
一旦你已經聲明
陣列的大小，

261
00:12:23,520 --> 00:12:26,780
我們還沒有看到一個機制，但在這裡
可以改變陣列的大小。

262
00:12:26,780 --> 00:12:29,020
事實上C沒有這個功能。

263
00:12:29,020 --> 00:12:32,524
如果你說給我五
國道主幹線，稱他們的數字，

264
00:12:32,524 --> 00:12:33,940
這就是你要得到它。

265
00:12:33,940 --> 00:12:38,790
所以我們現在要做的是週一，有
表達一個解決方案的能力

266
00:12:38,790 --> 00:12:42,480
雖然，我們只需要調整
我們的疊層的定義

267
00:12:42,480 --> 00:12:46,840
不要被一些硬編碼的數組，
但只是以存儲一個地址。

268
00:12:46,840 --> 00:12:47,890
>> 現在，這是為什麼？

269
00:12:47,890 --> 00:12:51,690
現在，我們只需要坦然面對
事實證明我的程序運行時，

270
00:12:51,690 --> 00:12:53,730
我大概會
要問的人，

271
00:12:53,730 --> 00:12:55,110
多少個號碼，你想存儲？

272
00:12:55,110 --> 00:12:56,776
因此，輸入有來自某處。

273
00:12:56,776 --> 00:12:59,140
但是，一旦我知道，
號碼，然後我可以

274
00:12:59,140 --> 00:13:02,470
使用什麼功能給
我的內存塊？

275
00:13:02,470 --> 00:13:03,580
我可以用malloc。

276
00:13:03,580 --> 00:13:06,710
我可以說，任何數量的
字節，我想回去了這些國道主幹線。

277
00:13:06,710 --> 00:13:10,910
而且我必須存儲在數字
可變這裡這個結構裡面

278
00:13:10,910 --> 00:13:13,480
應該是什麼？

279
00:13:13,480 --> 00:13:18,440
究竟進入
在這種情況下的數字？

280
00:13:18,440 --> 00:13:21,300
是啊，一個指向第一
該內存塊的字節，

281
00:13:21,300 --> 00:13:24,940
或更具體地，地址
第一這些字節。

282
00:13:24,940 --> 00:13:27,300
如果它是一個不事
字節或十億字節，

283
00:13:27,300 --> 00:13:28,890
我只需要關心的第一個。

284
00:13:28,890 --> 00:13:31,530
因為什麼樣的malloc擔保，
我的操作系統擔保，

285
00:13:31,530 --> 00:13:34,170
是，存儲器I組塊
得到的，這將是連續的。

286
00:13:34,170 --> 00:13:35,378
還有的不會是空白。

287
00:13:35,378 --> 00:13:38,576
所以，如果我問50
字節或1000個字節，

288
00:13:38,576 --> 00:13:40,450
他們都將是
背靠背回來。

289
00:13:40,450 --> 00:13:44,500
而只要我還記得有多大，怎麼
很多我要求，我所需要知道的

290
00:13:44,500 --> 00:13:46,230
是第一個這樣的地址。

291
00:13:46,230 --> 00:13:48,660
>> 所以，現在我們已經在代碼的能力。

292
00:13:48,660 --> 00:13:51,280
雖然，這將帶我們
更多的時間來寫這件事，

293
00:13:51,280 --> 00:13:55,900
我們現在可以通過重新分配內存
只是存儲不同的地址有

294
00:13:55,900 --> 00:13:59,060
如果我們想要一個更大的，甚至
較小的組塊的存儲器。

295
00:13:59,060 --> 00:14:00,170
因此，在這裡一個權衡。

296
00:14:00,170 --> 00:14:01,360
現在，我們得到的活力。

297
00:14:01,360 --> 00:14:03,350
我們仍然有
contiguousness我自稱。

298
00:14:03,350 --> 00:14:05,881
因為malloc的給我們
一個連續的內存塊。

299
00:14:05,881 --> 00:14:08,630
但是，這將是一個痛苦
脖子對我們來說，程序員，

300
00:14:08,630 --> 00:14:09,770
實際代碼了。

301
00:14:09,770 --> 00:14:10,730
這只是更多的工作。

302
00:14:10,730 --> 00:14:13,930
我們需要的代碼類似於我是什麼
剛才撞了。

303
00:14:13,930 --> 00:14:16,120
非常可行，但增加了複雜性。

304
00:14:16,120 --> 00:14:19,520
因此開發時，程序員
時間是另一個資源

305
00:14:19,520 --> 00:14:22,520
我們可能需要花
一段時間來獲得新的功能。

306
00:14:22,520 --> 00:14:24,020
然後當然還有一個隊列。

307
00:14:24,020 --> 00:14:26,227
我們不會進入這個
之一，很多細節。

308
00:14:26,227 --> 00:14:27,560
但它在精神上非常相似。

309
00:14:27,560 --> 00:14:31,220
我可以實現一個隊列，
其相應的操作，

310
00:14:31,220 --> 00:14:35,660
入隊或出隊，像添加或刪除，
它是說這只是一個華麗的方式，

311
00:14:35,660 --> 00:14:38,100
入隊或出隊，如下。

312
00:14:38,100 --> 00:14:41,170
我只能給自己一個結構
一遍的數的陣列，

313
00:14:41,170 --> 00:14:44,000
一遍的尺寸，
但為什麼我現在需要

314
00:14:44,000 --> 00:14:46,940
跟踪一個隊列的前面的？

315
00:14:46,940 --> 00:14:50,630
我並不需要知道
前面我堆棧。

316
00:14:50,630 --> 00:14:53,570
好吧，如果我再一
queue--就讓我們很難

317
00:14:53,570 --> 00:14:57,870
它編碼具有到五
整數這裡可能。

318
00:14:57,870 --> 00:15:00,940
因此，這是零，一，二，三，四。

319
00:15:00,940 --> 00:15:03,430
這將是
撥打的號碼了。

320
00:15:03,430 --> 00:15:06,940
而這將是所謂的大小。

321
00:15:06,940 --> 00:15:10,056
>> 為什麼不充分
以剛才的大小？

322
00:15:10,056 --> 00:15:11,680
好吧，讓我們推動這些相同的數字。

323
00:15:11,680 --> 00:15:14,220
所以我pushed--我入隊，或推。

324
00:15:14,220 --> 00:15:20,150
現在，我將排隊50，然後
51，然後61，和點點點。

325
00:15:20,150 --> 00:15:21,070
所以這是入隊。

326
00:15:21,070 --> 00:15:23,176
我入隊的50，然後51，然後61。

327
00:15:23,176 --> 00:15:25,050
這看起來相同
到煙囪迄今

328
00:15:25,050 --> 00:15:27,190
但我確實需要做出一個改變。

329
00:15:27,190 --> 00:15:33,680
我需要更新這個尺寸，所以我去
從零到一到兩到三現在。

330
00:15:33,680 --> 00:15:35,760
我如何出列？

331
00:15:35,760 --> 00:15:36,890
與出隊會發生什麼？

332
00:15:36,890 --> 00:15:41,950
誰應該打這個名單第一
如果是該行的蘋果專賣店？

333
00:15:41,950 --> 00:15:42,780
所以50。

334
00:15:42,780 --> 00:15:44,700
因此，它是有點棘手這個時候。

335
00:15:44,700 --> 00:15:47,880
而上一次是超級
易只是做大小減一，

336
00:15:47,880 --> 00:15:51,440
我得到我的數組的末尾有效
其中數字是，它消除61。

337
00:15:51,440 --> 00:15:52,920
但我不希望刪除61。

338
00:15:52,920 --> 00:15:55,030
我想利用50，誰
在那裡上午5:00

339
00:15:55,030 --> 00:15:56,790
排隊的
新的iPhone或諸如此類的東西。

340
00:15:56,790 --> 00:16:01,200
所以，要擺脫50，我
不能僅僅做到這一點，對不對？

341
00:16:01,200 --> 00:16:02,547
我可以劃掉50。

342
00:16:02,547 --> 00:16:04,380
但是，我們剛才說了，我們
不必如此肛門

343
00:16:04,380 --> 00:16:06,330
以劃掉或隱藏數據。

344
00:16:06,330 --> 00:16:08,090
我們可以忘記它在哪裡。

345
00:16:08,090 --> 00:16:12,330
>> 但是，如果我現在改變我的尺寸，
二，這是足夠的信息

346
00:16:12,330 --> 00:16:15,711
知道什麼是我的排隊怎麼回事？

347
00:16:15,711 --> 00:16:16,680
不盡然。

348
00:16:16,680 --> 00:16:19,830
就像我的尺寸是兩個，而是
哪裡排隊開始，

349
00:16:19,830 --> 00:16:22,980
尤其是如果我仍然有
那些相同的標號在存儲器中。

350
00:16:22,980 --> 00:16:24,260
50，51，61。

351
00:16:24,260 --> 00:16:27,090
所以，我需要記住
現在所在的前面。

352
00:16:27,090 --> 00:16:29,630
所以，我提出了
在那裡，我們將剛才叫

353
00:16:29,630 --> 00:16:33,729
第N次前，其初始
價值應該是什麼呢？

354
00:16:33,729 --> 00:16:35,270
零，列表僅僅是個開始。

355
00:16:35,270 --> 00:16:40,876
但現在除了遞減
規模，我們只是增加了前面。

356
00:16:40,876 --> 00:16:42,000
現在，這裡是另外一個問題。

357
00:16:42,000 --> 00:16:43,030
所以一旦我繼續前進。

358
00:16:43,030 --> 00:16:47,520
假設這是數
像121，124，然後，該死，

359
00:16:47,520 --> 00:16:48,610
我的空間。

360
00:16:48,610 --> 00:16:50,390
但是且慢，我不是。

361
00:16:50,390 --> 00:16:55,630
所以在這一點中的故事，
假設尺寸是一，二，

362
00:16:55,630 --> 00:17:00,370
三個，四個，所以假設
大小為4，前一個，

363
00:17:00,370 --> 00:17:01,621
所以51是在前面。

364
00:17:01,621 --> 00:17:04,329
我想提出另一個號碼在這裡，
但是，該死，我出了空間。

365
00:17:04,329 --> 00:17:06,710
但我不是真的，對不對？

366
00:17:06,710 --> 00:17:11,192
我在哪裡可以把一些
附加價值，如171？

367
00:17:11,192 --> 00:17:13,400
是的，我能正中下懷
回去那邊了吧？

368
00:17:13,400 --> 00:17:18,161
然後過了50，或
只是簡單地覆蓋它與171。

369
00:17:18,161 --> 00:17:20,410
如果你想知道為什麼
我們的數字變得如此隨意，

370
00:17:20,410 --> 00:17:24,150
這些通常採取計算機
科學課程在哈佛CS50之後。

371
00:17:24,150 --> 00:17:27,510
但是，這是一個很好的優化，
因為現在我沒有浪費的空間。

372
00:17:27,510 --> 00:17:30,750
我還是要記住
有多大這個東西是總。

373
00:17:30,750 --> 00:17:31,500
它共有五次總。

374
00:17:31,500 --> 00:17:33,375
因為我不希望
開始覆蓋51。

375
00:17:33,375 --> 00:17:36,260
所以，我現在還在外面的空間，
從而前同樣的問題。

376
00:17:36,260 --> 00:17:39,140
但是你可以看到現在
在你的代碼，你可能

377
00:17:39,140 --> 00:17:41,910
有一點寫更多
複雜性來實現這一目標。

378
00:17:41,910 --> 00:17:44,510
而事實上，運營商所
C語言可能讓

379
00:17:44,510 --> 00:17:48,110
你神奇地做到這一點的圓？

380
00:17:48,110 --> 00:17:50,160
是的模運算符，
百分號。

381
00:17:50,160 --> 00:17:53,160
那麼，有什麼樣的酷的隊列，
儘管我們不斷吸引數組

382
00:17:53,160 --> 00:17:56,520
因為這些象直線，如果
那種認為關於這個問題，彎曲

383
00:17:56,520 --> 00:18:00,341
作為周圍一圈，然後就
一種直覺它的工作精神

384
00:18:00,341 --> 00:18:01,590
我覺得有點更乾淨。

385
00:18:01,590 --> 00:18:05,190
你仍然必須執行
在代碼中的心智模式。

386
00:18:05,190 --> 00:18:07,550
所以並不難，
最終，實施，

387
00:18:07,550 --> 00:18:12,430
但我們還是失去了size--相當，
能力來調整，除非我們做到這一點。

388
00:18:12,430 --> 00:18:15,310
>> 我們必須擺脫的數組，我們
它與單個指針替換，

389
00:18:15,310 --> 00:18:20,010
然後地方在我的代碼我有
一個叫什麼函數來實際創建

390
00:18:20,010 --> 00:18:23,720
數組撥打的號碼？

391
00:18:23,720 --> 00:18:26,190
malloc或一些類似
功能，沒錯。

392
00:18:26,190 --> 00:18:30,481
在棧或隊列的任何問題。

393
00:18:30,481 --> 00:18:30,980
是嗎？

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
好問題。

396
00:18:34,240 --> 00:18:35,830
你會用什麼在這裡模。

397
00:18:35,830 --> 00:18:38,520
所以一般地，在使用
MOD，你會做

398
00:18:38,520 --> 00:18:40,620
同的大小
整體的數據結構。

399
00:18:40,620 --> 00:18:44,120
因此，像五容量，如果
這是不變的，可能是參與。

400
00:18:44,120 --> 00:18:47,100
但只是在做模數5
可能是不足夠的，

401
00:18:47,100 --> 00:18:51,380
因為我們需要知道我們是否
環繞在這裡或在這裡或在這裡。

402
00:18:51,380 --> 00:18:54,160
所以，你可能還
將要涉及到

403
00:18:54,160 --> 00:18:57,220
事物的大小，或
前面的變量也是如此。

404
00:18:57,220 --> 00:19:00,140
所以，它只是這個比較
簡單的算術表達式，

405
00:19:00,140 --> 00:19:02,000
但模將是關鍵因素。

406
00:19:02,000 --> 00:19:03,330
>> 所以，短片，如果你會的。

407
00:19:03,330 --> 00:19:05,780
一個動畫，一些
人們在另一所大學

408
00:19:05,780 --> 00:19:08,060
放在一起，我們已經
適用於本次討論。

409
00:19:08,060 --> 00:19:12,630
它涉及傑克學習
有關隊列和統計數據的事實。

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> 電影：曾幾何時，
有一個叫傑克的傢伙。

412
00:19:21,890 --> 00:19:25,330
當它來交朋友，
傑克沒有一個訣竅。

413
00:19:25,330 --> 00:19:28,220
於是傑克就去找了
最流行的傢伙，他知道。

414
00:19:28,220 --> 00:19:30,920
他到樓，問道，我該怎麼辦？

415
00:19:30,920 --> 00:19:33,400
婁看到他的朋友
真的很心疼。

416
00:19:33,400 --> 00:19:36,050
好了，他開始，就
看你如何打扮。

417
00:19:36,050 --> 00:19:38,680
你沒有任何的衣服
以不同的面貌？

418
00:19:38,680 --> 00:19:39,660
是的，傑克說。

419
00:19:39,660 --> 00:19:40,840
我當然有。

420
00:19:40,840 --> 00:19:43,320
來我家，
我會告訴他們你。

421
00:19:43,320 --> 00:19:44,550
於是他們去了傑克的。

422
00:19:44,550 --> 00:19:47,520
和傑克表明婁盒
在那裡他保持他的所有襯衫，

423
00:19:47,520 --> 00:19:49,260
和他的褲子，他的襪子。

424
00:19:49,260 --> 00:19:52,290
樓繼偉說，我看你有沒有
你的衣服在一堆。

425
00:19:52,290 --> 00:19:54,870
你為什麼不穿些
其他人曾經在一段時間？

426
00:19:54,870 --> 00:19:58,020
>> 傑克說，好吧，當我
脫去衣服和襪子，

427
00:19:58,020 --> 00:20:00,780
我把它們洗乾淨，並把
他們走在框中。

428
00:20:00,780 --> 00:20:03,210
然後是下一個
早晨，起來我一跳。

429
00:20:03,210 --> 00:20:06,380
我去的箱子，並得到
我的衣服上。

430
00:20:06,380 --> 00:20:09,070
婁很快就意識到
這個問題與傑克。

431
00:20:09,070 --> 00:20:12,080
他不停的衣服，光盤，
並且堆疊的書籍。

432
00:20:12,080 --> 00:20:14,420
當他伸手
一些閱讀或磨損，

433
00:20:14,420 --> 00:20:17,100
他會選擇頂部的書或內衣。

434
00:20:17,100 --> 00:20:19,500
然後，當他完成，他
會把它的右後衛。

435
00:20:19,500 --> 00:20:21,970
回到它會去，在堆棧的頂部。

436
00:20:21,970 --> 00:20:24,460
我知道解決的辦法，
說勝利響亮。

437
00:20:24,460 --> 00:20:27,090
你需要學習
開始使用一個隊列。

438
00:20:27,090 --> 00:20:29,870
婁花了傑克的衣服，
他們掛在衣櫃裡。

439
00:20:29,870 --> 00:20:32,710
而當他已經清空
盒子，他只是扔。

440
00:20:32,710 --> 00:20:36,500
>> 然後他說，現在的傑克，在年底
當天，穿上你的衣服左邊

441
00:20:36,500 --> 00:20:37,990
當你把他們帶走。

442
00:20:37,990 --> 00:20:41,300
然後明天早上，當你
看到陽光，讓你的衣服

443
00:20:41,300 --> 00:20:43,440
在右邊，從行的末端。

444
00:20:43,440 --> 00:20:44,880
你難道不明白嗎？說樓。

445
00:20:44,880 --> 00:20:46,370
這將是那麼好。

446
00:20:46,370 --> 00:20:49,770
你會沖刷一切的一次
你穿的東西之前兩次。

447
00:20:49,770 --> 00:20:52,670
而隨著一切都在排隊
在他的衣櫃和書架，

448
00:20:52,670 --> 00:20:55,160
傑克開始感覺
十分肯定自己。

449
00:20:55,160 --> 00:20:59,720
婁所有的感謝和
他精彩的隊列。

450
00:20:59,720 --> 00:21:01,220
揚聲器1：好吧，這是可愛的。

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
那麼，什麼是怎麼回事
在現在的引擎蓋下？

453
00:21:10,080 --> 00:21:12,370
我們有三分球，
我們擁有的malloc，

454
00:21:12,370 --> 00:21:15,680
我們有能力創造
內存佔為己有塊

455
00:21:15,680 --> 00:21:16,344
動態。

456
00:21:16,344 --> 00:21:18,510
所以這是一個圖片我們
瞥見就在幾天前。

457
00:21:18,510 --> 00:21:21,180
我們真的不糾纏
就可以了，但這張照片

458
00:21:21,180 --> 00:21:24,180
已經持續下
現在引擎蓋幾個星期。

459
00:21:24,180 --> 00:21:27,050
所以這代表，只是
我們已經繪製一個矩形，

460
00:21:27,050 --> 00:21:28,180
您的計算機的內存。

461
00:21:28,180 --> 00:21:31,850
也許你的電腦，或者CS50
ID，具有存儲器或RAM一個千兆字節

462
00:21:31,850 --> 00:21:33,050
兩個千兆字節或四個。

463
00:21:33,050 --> 00:21:34,450
這其實並不重要。

464
00:21:34,450 --> 00:21:37,240
您的操作系統
Windows或Mac OS或Linux，

465
00:21:37,240 --> 00:21:41,120
基本上可以讓你的程序
認為它能夠訪問

466
00:21:41,120 --> 00:21:42,982
到的全部
您的計算機的內存，

467
00:21:42,982 --> 00:21:45,440
即使你可能正在運行
多程序同時應用。

468
00:21:45,440 --> 00:21:46,990
因此，在現實中，沒有真正發揮作用。

469
00:21:46,990 --> 00:21:49,448
但它是一種一種假象
給所有的程序。

470
00:21:49,448 --> 00:21:53,110
所以，如果你有內存2音樂會，這
是怎樣的計算機可能會想到它。

471
00:21:53,110 --> 00:21:57,110
>> 現在，巧合的是，其中一個
事，內存這些領域之一，

472
00:21:57,110 --> 00:21:58,350
被稱為堆。

473
00:21:58,350 --> 00:22:01,680
實際上，任何時候
迄今在編寫代碼

474
00:22:01,680 --> 00:22:05,900
你已經被稱為
功能，比如主。

475
00:22:05,900 --> 00:22:08,410
回想一下，任何時候我已經
得出計算機的內存，

476
00:22:08,410 --> 00:22:10,640
我總是吸引排序
一半的矩形的這裡

477
00:22:10,640 --> 00:22:12,520
也懶得說話
關於什麼的上面。

478
00:22:12,520 --> 00:22:15,980
因為當主被調用時，我要求
你得到這個條子的記憶

479
00:22:15,980 --> 00:22:16,970
該下降這裡。

480
00:22:16,970 --> 00:22:20,650
如果主稱為函數
像掉期，以及交換到這裡。

481
00:22:20,650 --> 00:22:23,720
而事實證明，這是
其中，它的結束了。

482
00:22:23,720 --> 00:22:26,277
在被稱為堆的東西
在你的計算機的內存中。

483
00:22:26,277 --> 00:22:28,360
現在在一天結束時，
這僅僅是解決了。

484
00:22:28,360 --> 00:22:30,680
這就像一個字節零，
字節之一字節2十億。

485
00:22:30,680 --> 00:22:33,130
但是，如果你仔細想想
因為這樣的矩形對象，

486
00:22:33,130 --> 00:22:35,130
我們所做的每一個
一次，我們調用一個函數

487
00:22:35,130 --> 00:22:37,180
分層存儲新的切片。

488
00:22:37,180 --> 00:22:41,700
我們給這個函數片
自身的存儲器的工作。

489
00:22:41,700 --> 00:22:44,490
>> 現在回憶起來，這是非常重要的。

490
00:22:44,490 --> 00:22:46,400
因為如果我們確實有
類似的交換

491
00:22:46,400 --> 00:22:51,610
像A和B兩個局部變量
我們改變這些值從一個和兩個

492
00:22:51,610 --> 00:22:55,130
兩個和一個，召回
當交換返回，

493
00:22:55,130 --> 00:22:58,330
這是因為雖然這片
內存只是走了。

494
00:22:58,330 --> 00:23:00,080
在現實中，它仍然
有取證。

495
00:23:00,080 --> 00:23:01,940
而一些仍然居然有。

496
00:23:01,940 --> 00:23:05,410
但在概念上，這是因為
雖然它完全消失了。

497
00:23:05,410 --> 00:23:10,910
所以主不知道任何工作
這是在交換功能完成後，

498
00:23:10,910 --> 00:23:14,890
除非它實際上是通過這些
通過指針或引用參數。

499
00:23:14,890 --> 00:23:17,790
現在，從根本上解決
該問題與交換

500
00:23:17,790 --> 00:23:19,970
通過地址傳遞的東西研究。

501
00:23:19,970 --> 00:23:23,250
但事實證明也是如此，什麼是
已經持續了上面那一部分

502
00:23:23,250 --> 00:23:26,330
矩形的這段時間是
但有更多的內存在那裡。

503
00:23:26,330 --> 00:23:28,790
動態當你
分配內存，

504
00:23:28,790 --> 00:23:32,020
無論是GetString的，裡面的這
我們在CS50已經為你做

505
00:23:32,020 --> 00:23:34,710
圖書館，或者，如果你們
調用malloc和要求

506
00:23:34,710 --> 00:23:37,950
對於一大塊的操作系統
存儲器，它不是來自堆棧。

507
00:23:37,950 --> 00:23:40,960
它來自另一個地方
在您的計算機的內存

508
00:23:40,960 --> 00:23:42,220
這就是所謂的堆。

509
00:23:42,220 --> 00:23:43,430
而這沒有什麼不同。

510
00:23:43,430 --> 00:23:44,285
這是相同的RAM。

511
00:23:44,285 --> 00:23:45,160
這是同樣的內存。

512
00:23:45,160 --> 00:23:49,080
這只是在RAM那達
那裡，而不是到這裡。

513
00:23:49,080 --> 00:23:50,750
>> 所以，這是什麼意思？

514
00:23:50,750 --> 00:23:53,650
好吧，如果你的電腦有
的存儲器量有限

515
00:23:53,650 --> 00:23:57,450
與堆棧長大，所以
說話，堆，根據

516
00:23:57,450 --> 00:23:59,349
這一箭，越來越大了。

517
00:23:59,349 --> 00:24:01,140
換句話說，每
一次調用malloc，

518
00:24:01,140 --> 00:24:03,430
你被賦予了片
的存儲器從上方

519
00:24:03,430 --> 00:24:06,630
那麼也許更低一點，然後一點點
低，每次調用malloc的時候，

520
00:24:06,630 --> 00:24:10,100
堆，它的使用情況，
是一種成長，

521
00:24:10,100 --> 00:24:11,950
日益密切的是什麼？

522
00:24:11,950 --> 00:24:13,382
堆棧。

523
00:24:13,382 --> 00:24:14,840
那麼，這似乎是一個好主意嗎？

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
我的意思是，它並不真正清楚
如果你只可以做什麼

526
00:24:22,140 --> 00:24:23,910
具有存儲器的有限數量。

527
00:24:23,910 --> 00:24:25,200
但是，這肯定是不好的。

528
00:24:25,200 --> 00:24:27,920
這兩個箭頭都在一個
當然崩潰彼此。

529
00:24:27,920 --> 00:24:31,930
>> 而事實證明，壞傢伙，人們誰
與節目特別好，

530
00:24:31,930 --> 00:24:36,140
並試圖侵入電腦，
可以利用這個現實。

531
00:24:36,140 --> 00:24:38,290
事實上，我們考慮
一個小片段。

532
00:24:38,290 --> 00:24:41,350
因此，這是你可以閱讀的一個例子
關於維基百科上的更詳細。

533
00:24:41,350 --> 00:24:43,100
我們將向您在
文章，如果好奇。

534
00:24:43,100 --> 00:24:45,650
但是有一般的攻擊
被稱為緩衝區溢出的

535
00:24:45,650 --> 00:24:49,570
只要已經存在了作為人類
不得不操縱能力

536
00:24:49,570 --> 00:24:53,120
計算機的內存，尤其是在C中
所以這是一個非常隨意的程序，

537
00:24:53,120 --> 00:24:55,130
但讓​​我們從下往上看。

538
00:24:55,130 --> 00:24:57,650
主要為焦炭ARGC ARGV明星。

539
00:24:57,650 --> 00:24:59,830
所以這是一個程序，它
命令行參數。

540
00:24:59,830 --> 00:25:03,620
和所有主要的也顯然是通話
一個函數，調用它F代表簡單。

541
00:25:03,620 --> 00:25:04,610
它在傳遞什麼？

542
00:25:04,610 --> 00:25:05,490
ARGV之一。

543
00:25:05,490 --> 00:25:09,320
因此，它傳遞到f中的任何
的話，就是用戶鍵入

544
00:25:09,320 --> 00:25:11,500
在之後的提示
節目的名字都沒有。

545
00:25:11,500 --> 00:25:15,730
那麼像撒或的Vigenere，這
你可能還記得與ARGV做。

546
00:25:15,730 --> 00:25:16,680
>> 那麼，什麼是F？

547
00:25:16,680 --> 00:25:19,760
˚F接受一個字符串
作為其唯一的參數，

548
00:25:19,760 --> 00:25:22,100
AKA一個char明星，同
首先，作為一個字符串。

549
00:25:22,100 --> 00:25:24,920
而這就是所謂的任意
禁止在這個例子。

550
00:25:24,920 --> 00:25:27,710
然後焦炭C 12，
只是外行人的話說，

551
00:25:27,710 --> 00:25:31,750
什麼是CHARÇ支架12做的我們呢？

552
00:25:31,750 --> 00:25:33,440
它是什麼呢？

553
00:25:33,440 --> 00:25:36,490
分配內存，專
12個字節為12個字符。

554
00:25:36,490 --> 00:25:36,990
沒錯。

555
00:25:36,990 --> 00:25:40,000
然後最後一行，攪拌，
副本，你可能沒見過。

556
00:25:40,000 --> 00:25:43,360
這是一個字符串拷貝
功能，其目的在生活中

557
00:25:43,360 --> 00:25:48,160
是複製它的第二個參數
到了第一個參數，

558
00:25:48,160 --> 00:25:51,190
但只達到一個
一定數量的字節。

559
00:25:51,190 --> 00:25:53,860
所以第三個參數說：
你應該有多少個字節複製？

560
00:25:53,860 --> 00:25:56,720
條的長度，
無論用戶鍵入。

561
00:25:56,720 --> 00:25:59,320
及內容
酒吧，該字符串，是

562
00:25:59,320 --> 00:26:02,330
拷貝到存儲指向在C.

563
00:26:02,330 --> 00:26:04,060
>> 因此，這似乎是一種愚蠢的，它是。

564
00:26:04,060 --> 00:26:06,300
這是一個人為的例子，
但它代表

565
00:26:06,300 --> 00:26:10,100
一類攻擊向量的，
一種方式攻擊的程序。

566
00:26:10,100 --> 00:26:15,050
一切都很好，好，如果用戶
在一個字那是11個字符類型

567
00:26:15,050 --> 00:26:18,040
或更少，加上反斜杠零。

568
00:26:18,040 --> 00:26:22,830
如果在用戶鍵入超過什麼
11或12或20或50個字符？

569
00:26:22,830 --> 00:26:25,090
這是什麼程序該怎麼辦？

570
00:26:25,090 --> 00:26:29,360
潛在的賽格故障。這是怎麼回事
要盲目照搬一切都在酒吧起來

571
00:26:29,360 --> 00:26:31,750
其長度，這是
從字面上的一切吧，

572
00:26:31,750 --> 00:26:36,307
到地址指向C.但Ç
只搶先給出12個字節。

573
00:26:36,307 --> 00:26:37,640
但是，沒有任何額外的檢查。

574
00:26:37,640 --> 00:26:38,700
有沒有，如果條件。

575
00:26:38,700 --> 00:26:40,580
有沒有錯誤檢查在這裡。

576
00:26:40,580 --> 00:26:43,270
>> 所以這個計劃是什麼
要做的只是一味的

577
00:26:43,270 --> 00:26:45,750
一件事複製到其他。

578
00:26:45,750 --> 00:26:47,880
所以，如果我們得出這樣的
作為一個圖片，這裡的

579
00:26:47,880 --> 00:26:49,860
內存空間只是一個條子。

580
00:26:49,860 --> 00:26:53,470
所以，注意在底部，我們
有局部變量吧。

581
00:26:53,470 --> 00:26:57,330
這樣的指針，那將store--
而當地的論點，即是

582
00:26:57,330 --> 00:26:58,672
將存儲字符串吧。

583
00:26:58,672 --> 00:27:00,380
然後請注意只​​是
它在一組的上方，

584
00:27:00,380 --> 00:27:02,505
因為每次你問的時間
為存儲器的棧上，

585
00:27:02,505 --> 00:27:04,310
它會一點點
它形象地上面，

586
00:27:04,310 --> 00:27:06,270
我們已經得到了12個字節有通知。

587
00:27:06,270 --> 00:27:10,690
頂部左邊的一個是C支架為零，
底部正確的是C支架11。

588
00:27:10,690 --> 00:27:12,870
這是多麼的電腦
要打好它。

589
00:27:12,870 --> 00:27:18,300
因此，只要憑直覺，如果酒吧有更多的
超過12個字符共包括

590
00:27:18,300 --> 00:27:25,790
反斜杠零，在哪裡
12的C支架12要去？

591
00:27:25,790 --> 00:27:28,440
或者說在這裡是第12個
字符或13個字符，

592
00:27:28,440 --> 00:27:30,900
第一百字去
結束了在圖片？

593
00:27:30,900 --> 00:27:33,400
高於或低於？

594
00:27:33,400 --> 00:27:36,300
>> 對，因為即使
棧本身是向上增長，

595
00:27:36,300 --> 00:27:39,590
一旦你把東西在
它，它的設計的原因，

596
00:27:39,590 --> 00:27:41,294
放存儲器從上到下。

597
00:27:41,294 --> 00:27:44,460
所以，如果你有超過12個字節，
你將開始覆蓋吧。

598
00:27:44,460 --> 00:27:47,280
現在，這是一個錯誤，但它的
不是一個真正的大問題。

599
00:27:47,280 --> 00:27:51,130
但是，這是一個大問題，因為有
更多的東西在內存回事。

600
00:27:51,130 --> 00:27:53,074
因此，這裡是我們如何能夠
把你好，是明確的。

601
00:27:53,074 --> 00:27:54,490
如果我輸入打招呼的提示。

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O反斜杠零，在結束了
這12個字節，而且我們的超級安全。

603
00:27:59,330 --> 00:28:00,330
一切都很好。

604
00:28:00,330 --> 00:28:03,020
但是，如果我輸入一些東西
時間越長，可能是

605
00:28:03,020 --> 00:28:05,860
要潛入酒吧空間。

606
00:28:05,860 --> 00:28:08,405
但更糟糕的是，事實證明
出這麼長的時間，

607
00:28:08,405 --> 00:28:11,530
即使我們從來沒有談過
它的堆棧用於其他的東西。

608
00:28:11,530 --> 00:28:13,560
這不只是局部變量。

609
00:28:13,560 --> 00:28:15,100
>> C是一個非常低的水平的語言。

610
00:28:15,100 --> 00:28:17,810
排序，並偷偷
使用堆棧也

611
00:28:17,810 --> 00:28:21,260
要記住，當
函數被調用，什麼

612
00:28:21,260 --> 00:28:26,040
地址是以前的功能，
因此它可以跳轉回該功能。

613
00:28:26,040 --> 00:28:29,980
因此，當主呼叫交換，其中
的事情壓入堆棧

614
00:28:29,980 --> 00:28:34,380
不只是交換局部變量，
或者它的參數，還偷偷推

615
00:28:34,380 --> 00:28:37,510
入堆棧為代表
這裡由紅切片，

616
00:28:37,510 --> 00:28:40,520
是主要的地址物理
在計算機的內存，

617
00:28:40,520 --> 00:28:44,180
這樣，當交換完成時，計算機
知道我需要回到主

618
00:28:44,180 --> 00:28:46,760
並完成執行的主要功能。

619
00:28:46,760 --> 00:28:51,960
所以，現在這樣是很危險的，因為如果
中公比你好更多的用戶類型，

620
00:28:51,960 --> 00:28:57,030
使得用戶的輸入則會覆蓋
或將覆蓋紅色的部分，

621
00:28:57,030 --> 00:28:59,820
邏輯上，如果計算機的
只是要盲目地承擔

622
00:28:59,820 --> 00:29:03,830
在這片紅色的字節
地址到它應該返回，

623
00:29:03,830 --> 00:29:09,020
如果對手是足夠聰明或
幸運地把字節序列

624
00:29:09,020 --> 00:29:13,450
還有，看起來像一個地址，
但它的代碼的地址

625
00:29:13,450 --> 00:29:18,730
他或她想要的計算機
而不是主要的執行？

626
00:29:18,730 --> 00:29:21,670
>> 換句話說，如果什麼
用戶在提示符下敲入，

627
00:29:21,670 --> 00:29:23,850
不只是一些
無害喜歡你好，

628
00:29:23,850 --> 00:29:28,210
但它實際上代碼是等價
刪除所有該用戶的文件？

629
00:29:28,210 --> 00:29:30,060
或者通過電子郵件發送密碼到我嗎？

630
00:29:30,060 --> 00:29:31,940
或者，開始記錄自己的
按鍵，對不對？

631
00:29:31,940 --> 00:29:34,920
有一種方法，讓我們今天的規定，
他們可以輸入不只是打招呼

632
00:29:34,920 --> 00:29:36,711
世界還是他們的名字，
他們可能根本

633
00:29:36,711 --> 00:29:39,570
通過在代碼中，零和
的，該計算機

634
00:29:39,570 --> 00:29:43,450
錯誤的代碼和一個地址。

635
00:29:43,450 --> 00:29:48,950
因此，儘管有些抽象，如果
足夠的對抗代碼用戶類型

636
00:29:48,950 --> 00:29:52,330
我們將歸納這裡
答：是的攻擊或敵對。

637
00:29:52,330 --> 00:29:53,140
所以只要壞的東西。

638
00:29:53,140 --> 00:29:55,306
我們不關心
數字或零或1

639
00:29:55,306 --> 00:29:59,470
今天，這樣你最終
覆蓋的紅色款，

640
00:29:59,470 --> 00:30:01,580
請注意字節的順序。

641
00:30:01,580 --> 00:30:05,020
Ø835℃零八零。

642
00:30:05,020 --> 00:30:08,960
現在，維基百科的文章在這裡
建議，如果你現在居然開始

643
00:30:08,960 --> 00:30:12,460
標籤在您的計算機中的字節
內存，維基百科的文章是什麼

644
00:30:12,460 --> 00:30:19,060
的提出的是，如果有什麼的地址
除此之外左字節為80℃0 3508。

645
00:30:19,060 --> 00:30:22,200
>> 換句話說，如果壞傢伙是
與他或她的代碼足夠聰明

646
00:30:22,200 --> 00:30:26,650
實際上把一些在這裡，
對應於編碼的地址

647
00:30:26,650 --> 00:30:29,180
他或她注入
插入電腦，你

648
00:30:29,180 --> 00:30:31,050
可以欺騙計算機
為做任何事情。

649
00:30:31,050 --> 00:30:34,140
刪除文件，電子郵件
事，嗅探您的流量，

650
00:30:34,140 --> 00:30:36,710
從字面上什麼事情都可能會
注入到計算機。

651
00:30:36,710 --> 00:30:39,220
所以緩衝區溢出
進攻的核心

652
00:30:39,220 --> 00:30:43,530
僅僅是一個愚蠢，愚蠢
數組壓倒一切的

653
00:30:43,530 --> 00:30:45,840
沒有它的邊界檢查。

654
00:30:45,840 --> 00:30:48,850
這是什麼是超級危險
同時超級強大

655
00:30:48,850 --> 00:30:52,560
在C是，我們確實有
訪問在存儲器的任何位置。

656
00:30:52,560 --> 00:30:55,320
這取決於我們的程序員，
誰寫的原代碼

657
00:30:55,320 --> 00:30:59,330
檢查所有的織補長度
陣列，我們正在操縱。

658
00:30:59,330 --> 00:31:00,750
所以要清楚，有什麼解決？

659
00:31:00,750 --> 00:31:03,190
如果我們回滾到該
代碼，我不應該只是

660
00:31:03,190 --> 00:31:08,000
改變桿的長度，什麼
別的我應該檢查？

661
00:31:08,000 --> 00:31:10,620
還有什麼我應該做的到
防止這種攻擊完全？

662
00:31:10,620 --> 00:31:14,110
我不想只是一味地說
你要複製的字節數

663
00:31:14,110 --> 00:31:16,140
作為是條的長度。

664
00:31:16,140 --> 00:31:18,910
我想說，複製為
許多字節都在酒吧

665
00:31:18,910 --> 00:31:24,090
向上到分配
存儲器，或12最大限度。

666
00:31:24,090 --> 00:31:27,450
所以，我需要某種形式的if條件
，做檢查吧的長度，

667
00:31:27,450 --> 00:31:32,800
但如果超過12，我們只是硬編碼
12的最大可能距離。

668
00:31:32,800 --> 00:31:35,910
否則所謂緩衝
溢出攻擊可能發生。

669
00:31:35,910 --> 00:31:38,451
在這些幻燈片的底部，
如果你好奇閱讀更多

670
00:31:38,451 --> 00:31:41,200
是真正的原創文章
如果你想看看。

671
00:31:41,200 --> 00:31:44,550
>> 但現在，其中的價格
在這裡付出了效率低下。

672
00:31:44,550 --> 00:31:46,680
所以這是一個快速
低水平看看什麼

673
00:31:46,680 --> 00:31:49,709
現在出現的問題，我們
有權訪問的計算機的存儲器中。

674
00:31:49,709 --> 00:31:51,750
但另一個問題，我們
已經迷迷糊糊週一

675
00:31:51,750 --> 00:31:53,800
這僅僅是低效率
的一個鍊錶。

676
00:31:53,800 --> 00:31:56,019
我們又回到了線性時間。

677
00:31:56,019 --> 00:31:57,560
我們不再有一個連續的數組。

678
00:31:57,560 --> 00:31:58,980
我們沒有隨機訪問。

679
00:31:58,980 --> 00:32:00,710
我們不能用方括號。

680
00:32:00,710 --> 00:32:04,590
我們實際上不得不使用whil​​e循環
像我剛才寫的。

681
00:32:04,590 --> 00:32:09,740
但在週一，我們宣稱我們能
悄悄放回效率的境界

682
00:32:09,740 --> 00:32:13,040
實現東西是
對數也許，或者最好的是，

683
00:32:13,040 --> 00:32:16,120
甚至東西是
所謂一定時間。

684
00:32:16,120 --> 00:32:19,840
那麼，如何才能做到這一點通過使用這些新的
工具，這些地址，這些指針，

685
00:32:19,840 --> 00:32:22,210
和線程我們自己的東西呢？

686
00:32:22,210 --> 00:32:23,960
好吧，假設
在這裡，這些都是一堆

687
00:32:23,960 --> 00:32:27,170
我們要存儲在數字
高效的數據結構和搜索。

688
00:32:27,170 --> 00:32:30,960
我們完全可以後退到週
二，把這些放到一個數組，

689
00:32:30,960 --> 00:32:33,150
並使用二進制搜索尋找他們。

690
00:32:33,150 --> 00:32:34,040
分而治之。

691
00:32:34,040 --> 00:32:37,720
而事實上，你寫的
在PSET3二進制搜索，

692
00:32:37,720 --> 00:32:40,100
在那裡你實現find程序。

693
00:32:40,100 --> 00:32:40,890
但是你知道嗎。

694
00:32:40,890 --> 00:32:45,060
還有一種更
這樣做的聰明的方式。

695
00:32:45,060 --> 00:32:47,390
這是一個有點多
成熟，它可能

696
00:32:47,390 --> 00:32:50,830
讓我們看到了為什麼二進制
搜索是如此之快。

697
00:32:50,830 --> 00:32:52,980
首先，我們來介紹
樹的概念。

698
00:32:52,980 --> 00:32:54,730
其中，即使在
樣的現實樹

699
00:32:54,730 --> 00:32:57,730
成長就是這樣，在計算機世界
學他們那種向下生長

700
00:32:57,730 --> 00:33:00,830
就像一個家庭樹，在這裡你有
你的祖父母或曾祖父母

701
00:33:00,830 --> 00:33:04,580
或者諸如此類的東西在上面，族長和
家族的女家長，只有一個

702
00:33:04,580 --> 00:33:07,930
所謂根，節點，下面
這是它的孩子，

703
00:33:07,930 --> 00:33:11,442
下面這是它的孩子，或
它的後代更普遍。

704
00:33:11,442 --> 00:33:13,400
任何人都掛
家庭的底部

705
00:33:13,400 --> 00:33:16,070
樹，除了是
最年輕的家庭，

706
00:33:16,070 --> 00:33:19,520
也可以只是一般
稱為樹的葉子。

707
00:33:19,520 --> 00:33:21,800
>> 因此，這只是一堆
詞和定義

708
00:33:21,800 --> 00:33:25,790
對於一些所謂電腦一棵樹
科學，就像一個家庭樹。

709
00:33:25,790 --> 00:33:28,770
但是，還有票友變身
的樹木，其中之一

710
00:33:28,770 --> 00:33:30,780
被稱為一個二分搜索樹。

711
00:33:30,780 --> 00:33:34,380
你可以種挑逗
除了這個東西做什麼。

712
00:33:34,380 --> 00:33:37,180
那麼，它的二進制在什麼意義？

713
00:33:37,180 --> 00:33:41,455
哪裡二進制從何而來嗎？

714
00:33:41,455 --> 00:33:41,955
對不起？

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
這與其說是一個非此即彼的。

717
00:33:47,210 --> 00:33:52,000
它更，每個節點具有無
兩個以上的孩子，我們在這裡看到。

718
00:33:52,000 --> 00:33:54,990
在一般情況下，一個tree--和
你的父母和祖父母

719
00:33:54,990 --> 00:33:57,640
可以有很多孩子或
孫子，因為他們真正想要的，

720
00:33:57,640 --> 00:34:00,820
所以比如有，我們有三個
關閉該右手節點的孩子，

721
00:34:00,820 --> 00:34:05,480
但在一個二叉樹，一個節點具有
零個，一個或兩個孩子最大限度。

722
00:34:05,480 --> 00:34:08,496
這是一個很好的屬性，
因為如果它的上限由二，

723
00:34:08,496 --> 00:34:10,620
我們將能夠
得到一點點的日誌基地二期

724
00:34:10,620 --> 00:34:11,975
行動回事大勢所趨。

725
00:34:11,975 --> 00:34:13,350
因此，我們有一些東西對數。

726
00:34:13,350 --> 00:34:14,558
但是，更詳細的介紹了一下。

727
00:34:14,558 --> 00:34:19,810
搜索樹指數是
佈置成使得左孩子的

728
00:34:19,810 --> 00:34:22,429
值大於根。

729
00:34:22,429 --> 00:34:26,010
而它的右子是
比根大。

730
00:34:26,010 --> 00:34:29,290
換句話說，如果你把所有的
節點，在這張照片中圈，

731
00:34:29,290 --> 00:34:31,840
並期待在其左
兒童和其右孩子，

732
00:34:31,840 --> 00:34:34,739
第一應小於，
第二應大於。

733
00:34:34,739 --> 00:34:36,159
因此，合理性檢查55。

734
00:34:36,159 --> 00:34:37,780
它的左子是33。

735
00:34:37,780 --> 00:34:38,620
它的不足。

736
00:34:38,620 --> 00:34:40,929
55，其右孩子是77。

737
00:34:40,929 --> 00:34:41,783
它是大於。

738
00:34:41,783 --> 00:34:43,199
這是一個遞歸定義。

739
00:34:43,199 --> 00:34:46,480
我們可以檢查每個人的那些
節點和相同的圖案將舉行。

740
00:34:46,480 --> 00:34:49,389
>> 那麼什麼是不錯的
二叉搜索樹，是

741
00:34:49,389 --> 00:34:52,204
這一塊，我們可以實現它
有一個結構，就這樣。

742
00:34:52,204 --> 00:34:54,620
而且即使我們扔
很多結構在你的，

743
00:34:54,620 --> 00:34:56,560
他們是有點
直觀現在有希望。

744
00:34:56,560 --> 00:35:00,570
語法仍然是神秘的肯定，
但一個節點在該內容

745
00:35:00,570 --> 00:35:02,786
context--和我們保持
使用這個詞的節點，

746
00:35:02,786 --> 00:35:04,910
無論是一個矩形
屏幕或圓上，

747
00:35:04,910 --> 00:35:08,970
它只是一些通用的容器，
在這種情況下，一棵樹的，像一個

748
00:35:08,970 --> 00:35:11,780
我們看到，我們需要一個整數。
在每個節點

749
00:35:11,780 --> 00:35:15,460
然後我需要兩個指點指點
到左子和右子，

750
00:35:15,460 --> 00:35:16,590
分別。

751
00:35:16,590 --> 00:35:20,730
所以這就是我們如何
實現在一個結構。

752
00:35:20,730 --> 00:35:22,315
怎麼可能我在代碼中實現它？

753
00:35:22,315 --> 00:35:26,730
好吧，讓我們快速瀏覽
看看這個小小的例子。

754
00:35:26,730 --> 00:35:29,820
這不是功能，但我已經
複製並粘貼該結構。

755
00:35:29,820 --> 00:35:33,510
如果我的函數的二進制
搜索樹被稱為搜索，

756
00:35:33,510 --> 00:35:36,980
而這需要兩個參數，
整數N和一個指針

757
00:35:36,980 --> 00:35:41,400
到一個節點，以便一個指向樹
或一個指向樹的根，

758
00:35:41,400 --> 00:35:43,482
我該如何去尋找N +

759
00:35:43,482 --> 00:35:45,440
嗯，首先，因為我
處理球，

760
00:35:45,440 --> 00:35:46,750
我會做一個全面的檢查。

761
00:35:46,750 --> 00:35:54,279
如果樹等於等於空，是N
在這棵樹還是沒有這棵樹？

762
00:35:54,279 --> 00:35:55,070
這是不可能的，對不對？

763
00:35:55,070 --> 00:35:56,870
如果我過去的空，
有什麼也沒有。

764
00:35:56,870 --> 00:35:59,230
我乾脆
一味地說，返回false。

765
00:35:59,230 --> 00:36:04,050
如果你給我什麼，我當然不能
找到任何數量N.那麼還有什麼可能我

766
00:36:04,050 --> 00:36:04,750
現在檢查？

767
00:36:04,750 --> 00:36:12,830
我會說好東西如果N
小於任何位於樹節點

768
00:36:12,830 --> 00:36:16,300
我一直在流傳N值。

769
00:36:16,300 --> 00:36:20,270
換句話說，如果數字我
尋找，N，小於節點

770
00:36:20,270 --> 00:36:21,340
那我看。

771
00:36:21,340 --> 00:36:23,190
和節點我期待
在被稱為樹，

772
00:36:23,190 --> 00:36:26,370
和前面的例子召回
得到的價值指針，

773
00:36:26,370 --> 00:36:28,310
我用的是箭頭符號。

774
00:36:28,310 --> 00:36:35,960
因此，如果N小於樹箭頭
N，我想概念去左邊。

775
00:36:35,960 --> 00:36:38,590
我如何搜索明示離開？

776
00:36:38,590 --> 00:36:41,560
需要明確的是，如果這是
圖片中的問題，

777
00:36:41,560 --> 00:36:44,612
我已經過了那個最上面
箭頭指針下降。

778
00:36:44,612 --> 00:36:45,570
這是我的樹指針。

779
00:36:45,570 --> 00:36:48,060
我指著樹的根。

780
00:36:48,060 --> 00:36:52,100
我期待說，對於
數44，隨意。

781
00:36:52,100 --> 00:36:55,300
比44少或
超過55顯然更大？

782
00:36:55,300 --> 00:36:56,360
所以這是不到。

783
00:36:56,360 --> 00:36:58,760
所以這一點，如果條件適用。

784
00:36:58,760 --> 00:37:03,981
所以概念上，我該怎麼想
搜索下一個，如果我在尋找44？

785
00:37:03,981 --> 00:37:04,480
是嗎？

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> 沒錯，我想
搜索左子，

788
00:37:11,100 --> 00:37:12,789
或該圖像的左側的子樹。

789
00:37:12,789 --> 00:37:14,830
而事實上，讓我通過
圖片到這裡

790
00:37:14,830 --> 00:37:17,770
就一下，因為
我也不會劃傷了這一點。

791
00:37:17,770 --> 00:37:21,150
如果我從這裡開始在55，和
我知道，值44

792
00:37:21,150 --> 00:37:23,180
我在尋找是
左邊的，它是一種

793
00:37:23,180 --> 00:37:26,010
像撕開電話簿
一半或撕裂樹的一半。

794
00:37:26,010 --> 00:37:29,660
我不再去在乎
這整個樹的一半。

795
00:37:29,660 --> 00:37:33,270
然而，奇怪的是在條款
結構，這件事情在這裡

796
00:37:33,270 --> 00:37:36,682
始於33，這本身
是二叉查找樹。

797
00:37:36,682 --> 00:37:39,890
我之前說的，因為這個詞遞歸
的確這是一個數據結構，它

798
00:37:39,890 --> 00:37:41,707
顧名思義就是遞歸。

799
00:37:41,707 --> 00:37:44,540
你可能有一個樹是這個
大，但它的每一個孩子

800
00:37:44,540 --> 00:37:46,870
代表一棵樹只是有點小。

801
00:37:46,870 --> 00:37:50,910
而不是它是爺爺
或奶奶，現在它只是媽媽

802
00:37:50,910 --> 00:37:54,300
or--我不能say--沒有媽媽
或爸爸，那將是不可思議。

803
00:37:54,300 --> 00:37:59,000
相反，兩個孩子有
會像兄弟和姐妹。

804
00:37:59,000 --> 00:38:01,120
新一代的家族樹。

805
00:38:01,120 --> 00:38:02,900
但在結構上，這是同樣的想法。

806
00:38:02,900 --> 00:38:06,790
而事實證明，我有一個函數
與我可以搜索二進制搜索

807
00:38:06,790 --> 00:38:07,290
樹。

808
00:38:07,290 --> 00:38:08,680
這就是所謂的搜索。

809
00:38:08,680 --> 00:38:17,870
我在樹的箭頭左邊搜索對於N
否則，如果N大於該值

810
00:38:17,870 --> 00:38:18,870
我目前在。

811
00:38:18,870 --> 00:38:20,800
55中的故事剛才。

812
00:38:20,800 --> 00:38:23,780
我有一個調用的函數
搜索，我可以只

813
00:38:23,780 --> 00:38:29,660
通過N本和遞歸搜索
子樹和剛剛回歸

814
00:38:29,660 --> 00:38:30,620
不管這個答案。

815
00:38:30,620 --> 00:38:33,530
否則我這裡有一些最後的基本情況。

816
00:38:33,530 --> 00:38:35,310
>> 是什麼最終的情況？

817
00:38:35,310 --> 00:38:36,570
樹為null。

818
00:38:36,570 --> 00:38:39,980
我現在不是在尋找的價值
比小於它或更大

819
00:38:39,980 --> 00:38:42,610
或等於它。

820
00:38:42,610 --> 00:38:44,750
而且我可以說等於
相等，但在邏輯上是

821
00:38:44,750 --> 00:38:46,500
相當於只是說人在這裡。

822
00:38:46,500 --> 00:38:49,150
所以，真正的是我找到的東西。

823
00:38:49,150 --> 00:38:51,710
因此，希望這是一個
更引人注目的例子

824
00:38:51,710 --> 00:38:54,900
比愚蠢的西格瑪功能
我們做了一些講課回來，

825
00:38:54,900 --> 00:38:58,360
其中，使用循環是一樣簡單
計算了從一個所有的數字

826
00:38:58,360 --> 00:39:02,390
為N.這裡用的數據結構
這本身就是遞歸

827
00:39:02,390 --> 00:39:07,050
定義和遞歸拉，現在我們
要表達自己的能力

828
00:39:07,050 --> 00:39:09,780
在代碼本身是遞歸的。

829
00:39:09,780 --> 00:39:12,580
因此，這是這裡的完全相同的代碼。

830
00:39:12,580 --> 00:39:14,400
>> 所以，我們能解決什麼其他的問題？

831
00:39:14,400 --> 00:39:18,160
因此，一個快人一步遠離
樹木只是一瞬間。

832
00:39:18,160 --> 00:39:20,130
這裡，說，德國國旗。

833
00:39:20,130 --> 00:39:22,020
還有的顯然是一個
模式這個標誌。

834
00:39:22,020 --> 00:39:23,811
而且還有很多的
在世界上的標誌是

835
00:39:23,811 --> 00:39:27,560
是這麼簡單的條件
它們的顏色和圖案。

836
00:39:27,560 --> 00:39:31,930
但是，假如這個存儲為
.gif或JPEG格式，或位圖或平，

837
00:39:31,930 --> 00:39:34,240
任何圖形文件格式
與你熟悉，

838
00:39:34,240 --> 00:39:36,460
其中一些我們
在PSET4玩。

839
00:39:36,460 --> 00:39:41,550
這似乎並不值得保存
黑色像素，黑色像素，黑像素，

840
00:39:41,550 --> 00:39:44,790
點，點，點，一大堆
黑色像素的第一掃描線，

841
00:39:44,790 --> 00:39:47,430
或行，然後一大堆
同樣的，然後一大堆

842
00:39:47,430 --> 00:39:49,530
的相同，然後一​​個
一大堆的紅色像素，

843
00:39:49,530 --> 00:39:53,020
紅像素，紅色像素，然後整體
一束黃色的像素，黃色的，對不對？

844
00:39:53,020 --> 00:39:55,050
>> 有這樣的效率在這裡。

845
00:39:55,050 --> 00:39:59,040
你將如何直觀地
壓縮德國國旗

846
00:39:59,040 --> 00:40:01,320
如果其實現為一個文件？

847
00:40:01,320 --> 00:40:04,940
像什麼信息能不
懶得為了存儲在磁盤上

848
00:40:04,940 --> 00:40:08,040
從喜歡減少我們的文件大小
一兆字節到千字節，東西

849
00:40:08,040 --> 00:40:09,430
小？

850
00:40:09,430 --> 00:40:13,130
其中位於冗餘
這裡要清楚？

851
00:40:13,130 --> 00:40:13,880
你該怎麼辦？

852
00:40:13,880 --> 00:40:14,380
是嗎？

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
沒錯。

855
00:40:21,970 --> 00:40:24,550
為什麼不，而不是記住
每一次縫補像素的顏色

856
00:40:24,550 --> 00:40:28,200
就像你做的PSET4
與位圖文件格式，

857
00:40:28,200 --> 00:40:32,060
你為什麼不只是代表
像素的最左邊的列，例如

858
00:40:32,060 --> 00:40:35,370
一堆黑色像素，一串
紅，和一堆黃色，

859
00:40:35,370 --> 00:40:39,210
然後不知怎麼竟編碼
重複這個想法100倍

860
00:40:39,210 --> 00:40:41,020
或者重複這個1000倍？

861
00:40:41,020 --> 00:40:43,430
其中100或者1000是
只是一個整數，所以你

862
00:40:43,430 --> 00:40:47,290
可以逃脫只是一個單一的數字
而不是數百或數千

863
00:40:47,290 --> 00:40:48,270
的追加像素。

864
00:40:48,270 --> 00:40:50,990
事實上，這就是我們如何
可以壓縮的德國國旗。

865
00:40:50,990 --> 00:40:51,490
和

866
00:40:51,490 --> 00:40:53,470
現在來談談法國國旗？

867
00:40:53,470 --> 00:40:58,930
還有一點某種
腦力鍛煉，這標誌

868
00:40:58,930 --> 00:41:01,040
可以壓縮更多的磁盤上？

869
00:41:01,040 --> 00:41:05,720
德國國旗或法國的
標誌，如果我們採取這種做法？

870
00:41:05,720 --> 00:41:08,490
德國國旗，因為有
更水平的冗餘。

871
00:41:08,490 --> 00:41:12,190
而在設計上，許多圖形文件
格式確實工作作為掃描線

872
00:41:12,190 --> 00:41:12,830
水平。

873
00:41:12,830 --> 00:41:14,674
他們可以工作
垂直，只是人類

874
00:41:14,674 --> 00:41:17,090
決定多年前，我們會
一般認為事情排

875
00:41:17,090 --> 00:41:18,880
由行，而不是逐列。

876
00:41:18,880 --> 00:41:20,820
所以，事實上，如果你是
看文件

877
00:41:20,820 --> 00:41:24,670
德國國旗和法國的大小
標誌，只要分辨率

878
00:41:24,670 --> 00:41:27,530
相同的，相同的寬度
和高度，這其中

879
00:41:27,530 --> 00:41:31,580
這裡將是更大，因為你
不得不重複自己的三倍。

880
00:41:31,580 --> 00:41:35,570
你必須指定藍色，重複
自己，白，重複自己，紅色，

881
00:41:35,570 --> 00:41:36,740
重複自己。

882
00:41:36,740 --> 00:41:39,000
你不能只是全力以赴
的方式向右邊。

883
00:41:39,000 --> 00:41:41,200
和作為一旁，以使
清除壓縮

884
00:41:41,200 --> 00:41:43,910
無處不在，如果這些
從video--四個幀您

885
00:41:43,910 --> 00:41:45,890
可能還記得，影片
或視頻一般是

886
00:41:45,890 --> 00:41:47,286
就像每秒29或30幀。

887
00:41:47,286 --> 00:41:50,410
這就像一個小翻轉書，你
只是看到圖像，圖像，圖像，圖像，

888
00:41:50,410 --> 00:41:54,410
圖像只是超級快，所以它看起來像
屏幕上的演員們動人。

889
00:41:54,410 --> 00:41:57,130
這裡有一個大黃蜂
一束花的頂部。

890
00:41:57,130 --> 00:41:59,790
雖然它可能是一種
很難看到的第一眼，

891
00:41:59,790 --> 00:42:04,020
唯一移動
這部電影是蜜蜂。

892
00:42:04,020 --> 00:42:06,880
>> 什麼是愚蠢的有關存儲
視頻解壓縮？

893
00:42:06,880 --> 00:42:11,420
這是一種浪費存儲視頻
四個幾乎相同的圖像，

894
00:42:11,420 --> 00:42:13,670
不同僅僅是因為那裡的蜂。

895
00:42:13,670 --> 00:42:16,280
你可以扔掉最
該信息

896
00:42:16,280 --> 00:42:20,190
只記得，例如，
第一幀和最後一幀，

897
00:42:20,190 --> 00:42:22,180
如果你的關鍵幀
聽說過這個詞，

898
00:42:22,180 --> 00:42:24,337
而只是存儲在
中間那裡的蜂。

899
00:42:24,337 --> 00:42:26,170
而你也不必
存儲所有的粉紅色，

900
00:42:26,170 --> 00:42:28,330
和藍色，並在該
綠色價值觀為好。

901
00:42:28,330 --> 00:42:31,200
因此，這是只說
壓縮是無處不在。

902
00:42:31,200 --> 00:42:34,900
這是一個技術，我們經常使用
或者認為理所當然，這些天。

903
00:42:34,900 --> 00:42:38,750
>> 但是你如何壓縮文本？

904
00:42:38,750 --> 00:42:40,450
你怎麼去壓縮的文本？

905
00:42:40,450 --> 00:42:45,410
那麼，每一個人物的
ascii的是一個字節或八個比特。

906
00:42:45,410 --> 00:42:47,360
這就是那種愚蠢的，對不對？

907
00:42:47,360 --> 00:42:51,160
因為你可能A型
而E和I和O和U很多

908
00:42:51,160 --> 00:42:55,270
往往比像W或Q或Z，
根據所用的語言

909
00:42:55,270 --> 00:42:56,610
你寫的肯定。

910
00:42:56,610 --> 00:42:59,600
所以我們為什麼要使用
八位的每一個字母，

911
00:42:59,600 --> 00:43:02,040
包括最不
流行的信，對不對？

912
00:43:02,040 --> 00:43:05,300
為什麼不使用較少的位
超人氣的信件，

913
00:43:05,300 --> 00:43:07,760
像E，你猜的東西
首先在命運之輪，

914
00:43:07,760 --> 00:43:10,450
並使用更多的比特用於
冷門信嗎？

915
00:43:10,450 --> 00:43:10,950
為什麼呢？

916
00:43:10,950 --> 00:43:13,130
因為我們只是要
使用這些較不頻繁。

917
00:43:13,130 --> 00:43:15,838
>> 嗯，事實證明，有有
已經提出這樣做的嘗試。

918
00:43:15,838 --> 00:43:18,630
如果你的等級召回
學校或高中，莫爾斯電碼。

919
00:43:18,630 --> 00:43:20,400
莫爾斯電碼具有點
和破折號，可以

920
00:43:20,400 --> 00:43:24,270
沿導線作為發送
聲音或某種信號。

921
00:43:24,270 --> 00:43:25,930
但摩爾斯電碼是一個超級乾淨。

922
00:43:25,930 --> 00:43:29,010
這是怎樣的一個雙星系統中
你必須點或破折號。

923
00:43:29,010 --> 00:43:30,977
但是，如果你看到，例如，兩個點。

924
00:43:30,977 --> 00:43:33,810
或者，如果你想給操作
誰是這樣嘟，嘟，嘟，

925
00:43:33,810 --> 00:43:36,760
蜂鳴聲，創下了小觸發
該發送信號，

926
00:43:36,760 --> 00:43:40,360
如果，接收方，接收兩個
點，你有沒有收到什麼樣的信息？

927
00:43:40,360 --> 00:43:43,490
完全是任意的。

928
00:43:43,490 --> 00:43:44,450
>> 我？

929
00:43:44,450 --> 00:43:45,060
我？

930
00:43:45,060 --> 00:43:47,500
還是什麼about--還是我？

931
00:43:47,500 --> 00:43:49,570
也許這只是二號E的吧？

932
00:43:49,570 --> 00:43:52,480
因此，有這個問題
可解碼與莫爾斯

933
00:43:52,480 --> 00:43:54,890
代碼，從而除非
人向您發送消息

934
00:43:54,890 --> 00:43:59,510
實際上暫停，因此您可以排序的
看到或聽到的字母之間的差距，

935
00:43:59,510 --> 00:44:02,990
這是不夠的只是
送的零和一的流，

936
00:44:02,990 --> 00:44:05,610
或者點和線，
因為有歧義。

937
00:44:05,610 --> 00:44:08,640
E是一個點，因此，如果您
看到兩個點或聽到兩個點，

938
00:44:08,640 --> 00:44:11,254
也許這兩架E的或者它的One I.

939
00:44:11,254 --> 00:44:13,670
因此，我們需要一個系統，是一個
小比這更聰明。

940
00:44:13,670 --> 00:44:16,851
所以叫一個人霍夫曼年
前想出正是這一點。

941
00:44:16,851 --> 00:44:18,600
因此，我們只是要
採取快速瀏覽

942
00:44:18,600 --> 00:44:20,114
如何樹是有密切關係這一點。

943
00:44:20,114 --> 00:44:22,530
假設這是一些
要發送愚蠢的消息，

944
00:44:22,530 --> 00:44:26,342
只是A，B組成，C的D'和E的，
但有很多冗餘這裡。

945
00:44:26,342 --> 00:44:27,550
這並不意味著是英語。

946
00:44:27,550 --> 00:44:28,341
這不是加密的。

947
00:44:28,341 --> 00:44:30,540
這只是一個愚蠢的消息
有很多重複。

948
00:44:30,540 --> 00:44:34,010
所以，如果你真的算出來的所有
A的，B公司，C公司，D的，和E的，這裡的

949
00:44:34,010 --> 00:44:34,890
頻率。

950
00:44:34,890 --> 00:44:37,800
字母的20％是
A的，字母的45％

951
00:44:37,800 --> 00:44:39,660
為E的，和其他三個頻率。

952
00:44:39,660 --> 00:44:41,960
我們人手點算在那裡
而只是做數學。

953
00:44:41,960 --> 00:44:44,579
>> 所以，事實證明，
霍夫曼，前一段時間，

954
00:44:44,579 --> 00:44:46,620
意識到這一點，你知道
什麼，如果我開建

955
00:44:46,620 --> 00:44:51,172
一棵樹，或森林的樹木，如果你願意，
如下所示，我可以做以下。

956
00:44:51,172 --> 00:44:53,880
我想給一個節點到每個
我關心的字母

957
00:44:53,880 --> 00:44:55,530
我要去存儲
該節點的內

958
00:44:55,530 --> 00:44:58,610
頻率作為一個浮點
值，或者你可以使用它的N，也

959
00:44:58,610 --> 00:45:00,210
但是我們只用一個浮點數在這裡。

960
00:45:00,210 --> 00:45:03,100
而算法
他提出的是你

961
00:45:03,100 --> 00:45:07,210
藉此森林單個節點
樹木，所以超短樹，

962
00:45:07,210 --> 00:45:11,920
你開始與連接它們
新的群體，新的父母，如果你願意。

963
00:45:11,920 --> 00:45:16,150
而你做到這一點，選擇
兩個最小頻率的時間。

964
00:45:16,150 --> 00:45:18,110
於是，我花了10％和10％。

965
00:45:18,110 --> 00:45:19,090
我創建了一個新的節點。

966
00:45:19,090 --> 00:45:20,910
而我所說的新節點20％。

967
00:45:20,910 --> 00:45:22,750
>> 這兩個節點結合我下？

968
00:45:22,750 --> 00:45:23,810
這是一個有點曖昧。

969
00:45:23,810 --> 00:45:26,643
因此，有一些角落情況下
考慮，而是讓事情變得漂亮，

970
00:45:26,643 --> 00:45:29,300
我會選擇20％ - 
我現在忽略了孩子。

971
00:45:29,300 --> 00:45:33,640
我會選擇20％
15％和繪製兩條新邊。

972
00:45:33,640 --> 00:45:35,624
而現在這兩個節點
我邏輯組合？

973
00:45:35,624 --> 00:45:38,540
忽略所有的孩子，所有的
孫子，只看根

974
00:45:38,540 --> 00:45:39,070
現在。

975
00:45:39,070 --> 00:45:42,220
這兩個節點我綁在一起？

976
00:45:42,220 --> 00:45:44,530
第二點和0.35。

977
00:45:44,530 --> 00:45:45,890
因此，讓我得出兩個新的邊緣。

978
00:45:45,890 --> 00:45:47,570
然後，我只有一個了。

979
00:45:47,570 --> 00:45:48,650
因此，這裡的一棵樹。

980
00:45:48,650 --> 00:45:51,160
而且它被畫刻意
看那種漂亮，

981
00:45:51,160 --> 00:45:55,870
但是請注意，邊緣有
也被貼上零和一。

982
00:45:55,870 --> 00:45:59,510
因此，所有的左邊緣都為零
隨意，但始終。

983
00:45:59,510 --> 00:46:01,170
所有的右側邊緣的那些。

984
00:46:01,170 --> 00:46:05,070
>> 還等什麼霍夫曼提出，
如果要表示B，

985
00:46:05,070 --> 00:46:10,080
而不是表示數字66作為
一個ascii其長度為八​​個整位，

986
00:46:10,080 --> 00:46:13,360
你知道嗎，剛剛店
圖案零，零，零，

987
00:46:13,360 --> 00:46:17,030
零，因為這是路徑
從我的樹，霍夫曼先生的樹，

988
00:46:17,030 --> 00:46:18,600
從根葉。

989
00:46:18,600 --> 00:46:20,970
如果你想存儲
E，相比之下，不

990
00:46:20,970 --> 00:46:26,290
發送代表E.八位
相反，派位的是什麼模式？

991
00:46:26,290 --> 00:46:26,890
一。

992
00:46:26,890 --> 00:46:30,410
什麼是好的關於這
E是最流行的字母，

993
00:46:30,410 --> 00:46:32,340
而你正在使用的
最短的代碼吧。

994
00:46:32,340 --> 00:46:34,090
接下來最流行
信看起來

995
00:46:34,090 --> 00:46:37,380
是A.所以，有多少位
他才建議用是什麼？

996
00:46:37,380 --> 00:46:38,270
零點一。

997
00:46:38,270 --> 00:46:41,060
>> 而且因為它的實現
因為這棵樹，現在

998
00:46:41,060 --> 00:46:43,350
讓我規定有
無歧義的莫爾斯

999
00:46:43,350 --> 00:46:46,090
碼，因為所有的
你關心的信

1000
00:46:46,090 --> 00:46:48,780
是在這些邊緣的末端。

1001
00:46:48,780 --> 00:46:50,580
所以，這只是一個
應用一棵樹。

1002
00:46:50,580 --> 00:46:52,538
這is--我會波
我的手在這你如何

1003
00:46:52,538 --> 00:46:55,570
有可能實現這是一個C結構。

1004
00:46:55,570 --> 00:46:58,260
我們只需要結合
一個符號，就像一個char，

1005
00:46:58,260 --> 00:46:59,910
和在頻率左右。

1006
00:46:59,910 --> 00:47:02,510
但是，讓我們看兩個
最後的例子，你會

1007
00:47:02,510 --> 00:47:06,070
得到相當熟悉後，
測驗零習題集五位。

1008
00:47:06,070 --> 00:47:09,210
>> 因此，有該數據結構
稱為哈希表。

1009
00:47:09,210 --> 00:47:12,247
而一個哈希表是怎麼樣的
冷卻在於它具有水桶。

1010
00:47:12,247 --> 00:47:14,830
假設有四個桶
在這裡，只有四個空格。

1011
00:47:14,830 --> 00:47:20,830
下面是一副撲克牌，並在這裡被
俱樂部，鐵鍬，俱樂部，鑽石，俱樂部，

1012
00:47:20,830 --> 00:47:25,960
鑽石，俱樂部，鑽石，
clubs--所以這是隨機的。

1013
00:47:25,960 --> 00:47:30,330
心，hearts--所以我
bucketizing所有輸入這裡。

1014
00:47:30,330 --> 00:47:32,430
而一個哈希表的需求
看你的輸入，

1015
00:47:32,430 --> 00:47:34,850
然後把它放在一個特定的
基於你所看到的地方。

1016
00:47:34,850 --> 00:47:35,600
這是一個算法。

1017
00:47:35,600 --> 00:47:37,980
而我使用的是超
簡單的視覺算法。

1018
00:47:37,980 --> 00:47:40,030
其中最困難的部分是
記住哪些圖片是。

1019
00:47:40,030 --> 00:47:41,590
再有就是總共四個東西。

1020
00:47:41,590 --> 00:47:45,440
>> 現在堆棧的長勢，這
是故意設計的東西在這裡。

1021
00:47:45,440 --> 00:47:46,540
還有什麼我可以做什麼？

1022
00:47:46,540 --> 00:47:49,080
所以實際上我們在這裡有一個
一群老同學考試用書。

1023
00:47:49,080 --> 00:47:51,240
假設一堆
學生的名字都在這裡。

1024
00:47:51,240 --> 00:47:52,570
這裡有一個更大的哈希表。

1025
00:47:52,570 --> 00:47:54,867
而不是四個桶，
我有，比方說26。

1026
00:47:54,867 --> 00:47:57,950
我們不想去借錢26
從外面[事情？安嫩伯格？]，所以

1027
00:47:57,950 --> 00:48:00,289
這裡共有五次代表
A到Z.如果我

1028
00:48:00,289 --> 00:48:03,580
看到學生的名稱以A，
我打算把他或她的測驗那裡。

1029
00:48:03,580 --> 00:48:08,850
如果有人以C開頭，在那裡，
A--實際上，並不想這樣做。

1030
00:48:08,850 --> 00:48:10,060
B進入到這裡。

1031
00:48:10,060 --> 00:48:13,390
所以，我有A和B和C和
現在這裡的另一個學生。

1032
00:48:13,390 --> 00:48:16,212
但是，如果這個散列表是
以與陣列實現，

1033
00:48:16,212 --> 00:48:17,920
我有點擰
在這一點上，對不對？

1034
00:48:17,920 --> 00:48:19,510
那種我需要把這個地方。

1035
00:48:19,510 --> 00:48:24,380
>> 因此，我可以解決這個問題的一個方法是，所有的
沒錯，A佔線，B忙，C忙。

1036
00:48:24,380 --> 00:48:28,880
我打算把他D.因此，在
首先，我有隨機即時訪問

1037
00:48:28,880 --> 00:48:31,064
每個桶的學生。

1038
00:48:31,064 --> 00:48:33,230
但是，現在這是一種下放
弄成線性的，

1039
00:48:33,230 --> 00:48:36,750
因為如果我要尋找的人
其名稱開頭，我點擊這裡。

1040
00:48:36,750 --> 00:48:38,854
但如果不是這種甲
學生，我正在尋找，

1041
00:48:38,854 --> 00:48:41,520
那種我要開始檢查
水桶，因為我做了什麼

1042
00:48:41,520 --> 00:48:44,530
是那種線性
探測數據結構。

1043
00:48:44,530 --> 00:48:47,710
一個說笨方法只是看
第一個可用的開放，

1044
00:48:47,710 --> 00:48:51,850
並把作為一個B計劃，可以這麼說，
或者在這種情況下的計劃D，則值

1045
00:48:51,850 --> 00:48:53,340
在該位置代替。

1046
00:48:53,340 --> 00:48:56,470
這僅僅是這樣，如果你​​已經
有26個地點，並沒有學生

1047
00:48:56,470 --> 00:49:00,600
名為Q或Z或喜歡的事
即，至少你正在使用的空間。

1048
00:49:00,600 --> 00:49:03,140
>> 但是，我們已經看到了更多的
聰明的解決方案，在這裡，對不對？

1049
00:49:03,140 --> 00:49:04,870
你會怎麼做，而不是
如果你有一個碰撞？

1050
00:49:04,870 --> 00:49:06,670
如果兩個人有
該名稱的，會是什麼

1051
00:49:06,670 --> 00:49:09,160
是一個更聰明或更
直觀的解決方案不僅僅是

1052
00:49:09,160 --> 00:49:12,840
把一個其中D應該是？

1053
00:49:12,840 --> 00:49:14,810
為什麼不讓我走
外[？安嫩伯格？]

1054
00:49:14,810 --> 00:49:19,960
喜歡的malloc，另一個節點，把它
在這裡，然後把這裡的學生。

1055
00:49:19,960 --> 00:49:22,120
所以，我基本上是有
一些類型的數組，，

1056
00:49:22,120 --> 00:49:25,590
或者更優雅的，因為我們是
開始看到一個鍊錶。

1057
00:49:25,590 --> 00:49:29,520
>> 因此一個哈希表的結構
這可能看起來就像這樣，

1058
00:49:29,520 --> 00:49:33,900
但更聰明，你的東西被稱為
分離鏈，從而哈希表

1059
00:49:33,900 --> 00:49:38,340
很簡單，是一個數組，每個
其元素不是數字，

1060
00:49:38,340 --> 00:49:40,470
本身是一個鍊錶。

1061
00:49:40,470 --> 00:49:45,080
使您獲得超快速訪問
決定在哪裡你的價值散列到。

1062
00:49:45,080 --> 00:49:48,059
就像用卡的例子，
我做了超級快速決策。

1063
00:49:48,059 --> 00:49:49,600
心放在這裡，鑽石放在這裡。

1064
00:49:49,600 --> 00:49:52,180
同樣在這裡，一個放在這裡，
ð放在這裡，B放在這裡。

1065
00:49:52,180 --> 00:49:55,740
因此，超快速的查找窗口，如果
你碰巧遇到一個案例

1066
00:49:55,740 --> 00:49:59,429
在這裡你有碰撞，二
人具有相同的名稱，以及再

1067
00:49:59,429 --> 00:50:00,970
你剛開始把它們連接起來。

1068
00:50:00,970 --> 00:50:03,900
也許你讓他們排序
按字母順序，也許你不知道。

1069
00:50:03,900 --> 00:50:05,900
但至少現在我們有活力。

1070
00:50:05,900 --> 00:50:10,250
因此，一方面，我們有超級快
固定的時間和形式的線性時間

1071
00:50:10,250 --> 00:50:14,110
如果這些鍊錶參與
開始變得有點長。

1072
00:50:14,110 --> 00:50:16,880
>> 因此，這種愚蠢的，
令人討厭的笑話年前。

1073
00:50:16,880 --> 00:50:19,590
在CS50黑客馬拉松，
當學生入住，

1074
00:50:19,590 --> 00:50:22,040
一些TF或CA每年
認為這是有趣忍受

1075
00:50:22,040 --> 00:50:27,772
像這樣的一個標誌，它只是
也就是說，如果你的名字開始與A，

1076
00:50:27,772 --> 00:50:28,870
走這條路。

1077
00:50:28,870 --> 00:50:31,110
如果你的名字開始
用A，B，去this-- OK，

1078
00:50:31,110 --> 00:50:33,290
這很有趣，也許在以後的學期。

1079
00:50:33,290 --> 00:50:36,420
但是，還有一個
這樣，太的方式。

1080
00:50:36,420 --> 00:50:37,410
回過頭來的。

1081
00:50:37,410 --> 00:50:38,600
>> 因此，有這種結構。

1082
00:50:38,600 --> 00:50:40,420
這是我們最後一次
結構的今天，

1083
00:50:40,420 --> 00:50:42,400
這是一些所謂的線索。

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E，這對於某些原因是短
檢索，但它被稱為線索。

1085
00:50:47,140 --> 00:50:51,389
因此，一個線索是另一個有趣
汞合金很多這樣的想法。

1086
00:50:51,389 --> 00:50:52,930
這是一棵樹，這是我們以前見過。

1087
00:50:52,930 --> 00:50:54,180
這不是一個二叉搜索樹。

1088
00:50:54,180 --> 00:50:58,410
這是一個樹的任何數量的孩子，
但每一個線索的孩子

1089
00:50:58,410 --> 00:51:00,090
是一個數組。

1090
00:51:00,090 --> 00:51:04,790
大小的數組，說，26或者27
如果你想支持複姓名字

1091
00:51:04,790 --> 00:51:06,790
還是在人的名字撇號。

1092
00:51:06,790 --> 00:51:08,280
>> 所以這是一個數據結構。

1093
00:51:08,280 --> 00:51:10,290
而如果你從上
到底，就像如果你

1094
00:51:10,290 --> 00:51:13,710
頂一下節點有，男，是
指向左邊的事情存在，

1095
00:51:13,710 --> 00:51:17,665
然後將其A，X，W，E，L，L。這是
只是一種數據結構，任意地

1096
00:51:17,665 --> 00:51:19,120
是存儲人的名字。

1097
00:51:19,120 --> 00:51:25,720
和麥克斯韋是剛剛以下存儲
數組的數組陣列的路徑。

1098
00:51:25,720 --> 00:51:30,050
但令人驚訝的有關線索是
如此，而一個鍊錶，甚至

1099
00:51:30,050 --> 00:51:34,520
一個數組，我們曾經得到的最好的是
線性時間或對數時間尋找

1100
00:51:34,520 --> 00:51:35,600
有人了。

1101
00:51:35,600 --> 00:51:40,530
在一個線索的此數據結構中，如果
我的數據結構中有一個名字

1102
00:51:40,530 --> 00:51:43,720
而我在尋找麥克斯韋，我
要找到他很快。

1103
00:51:43,720 --> 00:51:47,910
我只是尋找M-A-X-W-E-L-L。是否
此數據結構中，通過對比，

1104
00:51:47,910 --> 00:51:51,830
如果N是一百萬，如果有一個
在這種數據結構萬個名字，

1105
00:51:51,830 --> 00:51:57,100
麥克斯韋仍然將是
發現剛剛M-A-X-W-E-L-L後

1106
00:51:57,100 --> 00:51:58,090
步驟。

1107
00:51:58,090 --> 00:52:01,276
而David-- D-A-V-I-D的步驟。

1108
00:52:01,276 --> 00:52:03,400
換句話說，通過建立
一種數據結構，是

1109
00:52:03,400 --> 00:52:07,240
得到了所有這些陣列的，所有這些都
本身支持隨機訪問，

1110
00:52:07,240 --> 00:52:11,090
我可以開始尋找達人的
使用的時候這是一個量的名字

1111
00:52:11,090 --> 00:52:14,340
成比例的數量不限
的東西，在數據結構中，

1112
00:52:14,340 --> 00:52:16,330
像一百萬現有名稱。

1113
00:52:16,330 --> 00:52:20,135
花費的時間我找的金額
的M-A-X-W-E-L-L的這種數據結構是

1114
00:52:20,135 --> 00:52:22,260
比例不到
的數據結構的大小，

1115
00:52:22,260 --> 00:52:25,930
但對名稱的長度。

1116
00:52:25,930 --> 00:52:28,440
而現實的
名字我們仰視

1117
00:52:28,440 --> 00:52:29,970
永遠不會長瘋了。

1118
00:52:29,970 --> 00:52:32,600
也許有人有10個字符
名，20個字符的名稱。

1119
00:52:32,600 --> 00:52:33,900
這當然是有限的，對不對？

1120
00:52:33,900 --> 00:52:37,110
有地球上的人誰
有最長可能的名稱，

1121
00:52:37,110 --> 00:52:39,920
但這個名字是一個常數
值長，對不對？

1122
00:52:39,920 --> 00:52:41,980
它並不在任何意義上有所不同。

1123
00:52:41,980 --> 00:52:45,090
因此，在這種方式中，我們
實現了數據結構

1124
00:52:45,090 --> 00:52:47,800
這是恆定的時間查找。

1125
00:52:47,800 --> 00:52:50,670
它採取了一些措施
根據輸入的長度，

1126
00:52:50,670 --> 00:52:54,250
的名字，但沒有數量
在數據結構中。

1127
00:52:54,250 --> 00:52:58,700
因此，如果我們加倍名的數量
從十億一二十億明年，

1128
00:52:58,700 --> 00:53:03,720
發現麥克斯韋是要採取
的七個步驟完全相同的數

1129
00:53:03,720 --> 00:53:04,650
找到他。

1130
00:53:04,650 --> 00:53:08,810
因此，我們似乎已經達到
我們神聖的運行時間的法寶。

1131
00:53:08,810 --> 00:53:10,860
>> 因此，一對夫婦的快速​​公告。

1132
00:53:10,860 --> 00:53:11,850
測驗零快到了。

1133
00:53:11,850 --> 00:53:14,600
更多的是在球場上的網站
在接下來的幾天。

1134
00:53:14,600 --> 00:53:17,120
週一的lecture--這是一個節日
你們是哈佛在星期一。

1135
00:53:17,120 --> 00:53:18,850
這不是在紐黑文，
所以我們採取了類

1136
00:53:18,850 --> 00:53:20,310
紐黑文的演講在星期一。

1137
00:53:20,310 --> 00:53:22,550
一切都將被拍攝下來，
和流現場像往常一樣，

1138
00:53:22,550 --> 00:53:24,900
但讓​​今天的結束
用30秒的剪輯

1139
00:53:24,900 --> 00:53:26,910
所謂的“深度思考”
通過Daven法納姆，這

1140
00:53:26,910 --> 00:53:30,850
在週六的啟發，去年
夜直播的“深度思考”

1141
00:53:30,850 --> 00:53:35,700
傑克得心應手，這
現在應該是有意義的。

1142
00:53:35,700 --> 00:53:38,810
>> 電影：現在，“深
思考“由Daven法納姆。

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
哈希表。

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> 揚聲器1：好吧，這就是它了。

1147
00:53:47,660 --> 00:53:48,805
我們會看到你下週。

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> 道格：要看到它在行動。

1150
00:53:56,680 --> 00:53:58,304
所以，讓我們來看看這個現在。

1151
00:53:58,304 --> 00:53:59,890
所以在這裡，我們有一個排序的數組。

1152
00:53:59,890 --> 00:54:04,860
>> IAN：道格，你能繼續前進，重新啟動
這只是一秒，請。

1153
00:54:04,860 --> 00:54:08,562
好吧，相機滾動，所以
的動作，當你準備好，道格，好不好？

1154
00:54:08,562 --> 00:54:11,020
道格：好的，所以我們
這裡是一個未排序的數組。

1155
00:54:11,020 --> 00:54:13,960
我也有色的所有元素
紅色，以表明它是，事實上，

1156
00:54:13,960 --> 00:54:14,460
未分類。

1157
00:54:14,460 --> 00:54:17,960
所以記得的第一件事情，我們做的
是我們排序陣列的左半。

1158
00:54:17,960 --> 00:54:20,630
然後我們排序的權利
一半的陣列。

1159
00:54:20,630 --> 00:54:22,830
雅達，雅，達，雅，達，
我們把它們合併起來。

1160
00:54:22,830 --> 00:54:24,520
我們有一個完全排序的數組。

1161
00:54:24,520 --> 00:54:25,360
所以這是如何歸併排序工作。

1162
00:54:25,360 --> 00:54:27,109
>> IAN：哇，哇，哇，
切，切，切，切。

1163
00:54:27,109 --> 00:54:30,130
道格，你不能隨便亞達，雅，達，
雅-DA，通過歸併排序的方式。

1164
00:54:30,130 --> 00:54:31,970
>> 道格：我只是做了。

1165
00:54:31,970 --> 00:54:32,832
它的罰款。

1166
00:54:32,832 --> 00:54:33,540
我們是好去。

1167
00:54:33,540 --> 00:54:34,760
我們只是不停地滾動。

1168
00:54:34,760 --> 00:54:35,380
所以無論如何，

1169
00:54:35,380 --> 00:54:37,800
>> 伊恩：你有解釋
它比更充分。

1170
00:54:37,800 --> 00:54:39,999
這只是還不夠。

1171
00:54:39,999 --> 00:54:41,790
道格：伊恩，我們不
需要回去之一。

1172
00:54:41,790 --> 00:54:42,350
它的罰款。

1173
00:54:42,350 --> 00:54:45,690
所以無論如何，如果我們繼續merge--
伊恩，我們在拍戲的中間。

1174
00:54:45,690 --> 00:54:46,612
>> 伊恩：我知道。

1175
00:54:46,612 --> 00:54:49,320
我們不能只是亞達，雅，達，
雅-DA，通過全過程。

1176
00:54:49,320 --> 00:54:52,200
你必須解釋為什麼
雙方得到合併在一起。

1177
00:54:52,200 --> 00:54:53,570
>> 道格：但我們已經
解釋了兩個sides--

1178
00:54:53,570 --> 00:54:55,321
>> 伊恩：你剛才表示
他們合併數組。

1179
00:54:55,321 --> 00:54:56,486
道格：他們知道這個過程。

1180
00:54:56,486 --> 00:54:57,172
他們是很好。

1181
00:54:57,172 --> 00:54:58,380
我們已經討論了10次，

1182
00:54:58,380 --> 00:55:00,330
>> 伊恩：你剛才跳過權權。

1183
00:55:00,330 --> 00:55:03,360
我們要回一個，你
不能你丫達，雅，達權。

1184
00:55:03,360 --> 00:55:05,480
好了，回到之一。

1185
00:55:05,480 --> 00:55:07,833
>> 道格：我要回去
通過所有的幻燈片？

1186
00:55:07,833 --> 00:55:08,332
我的上帝。

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
這就像第六次，伊恩。

1189
00:55:13,004 --> 00:55:13,940
它的罰款。

1190
00:55:13,940 --> 00:55:15,200
>> 伊恩：好的。

1191
00:55:15,200 --> 00:55:16,590
你準備好了嗎？

1192
00:55:16,590 --> 00:55:17,400
太好了。

1193
00:55:17,400 --> 00:55:18,950
動作。