1
00:00:00,000 --> 00:00:03,423
>> [音樂播放]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI鵬：歡迎來到第6個星期

4
00:00:08,210 --> 00:00:11,620
我們從標準的偏離
週二的部分時間

5
00:00:11,620 --> 00:00:14,130
下午這個可愛的星期天早晨。

6
00:00:14,130 --> 00:00:17,330
謝謝大家了
加入我的今天，但嚴重的是，

7
00:00:17,330 --> 00:00:18,170
掌聲雷動。

8
00:00:18,170 --> 00:00:20,600
>> 這是一個相當大的努力。

9
00:00:20,600 --> 00:00:23,600
我幾乎沒有，甚至使它
在時間，但它是確定。

10
00:00:23,600 --> 00:00:27,520
所以，我知道所有的你，
剛剛去到測驗。

11
00:00:27,520 --> 00:00:30,370
首先，歡迎
另一面的那個。

12
00:00:30,370 --> 00:00:32,917
>> 其次，我們會談論它。

13
00:00:32,917 --> 00:00:34,000
我們將討論的測驗。

14
00:00:34,000 --> 00:00:35,700
我們將談論如何
你正在做的類。

15
00:00:35,700 --> 00:00:36,550
你會沒事的。

16
00:00:36,550 --> 00:00:39,080
我有你的測驗為
你在這裡結束，

17
00:00:39,080 --> 00:00:42,120
所以如果你們想帶
看看吧，完全罰款。

18
00:00:42,120 --> 00:00:46,590
>> 所以很快我們開始的前
今天的議程如下。

19
00:00:46,590 --> 00:00:48,430
正如你所看到的，我們是
基本上速射

20
00:00:48,430 --> 00:00:52,120
通過一大堆數據結構
真的，真的，真的很快。

21
00:00:52,120 --> 00:00:54,380
如此，因此，它不會被
超級互動的今天。

22
00:00:54,380 --> 00:00:59,620
這將只是我的一種喊
事情是你，如果我迷惑你，

23
00:00:59,620 --> 00:01:02,680
如果我走得太快，讓我知道。

24
00:01:02,680 --> 00:01:05,200
他們只是各種數據
結構，並作為部分

25
00:01:05,200 --> 00:01:07,070
您pset獲取如此
即將到來的一周，你會

26
00:01:07,070 --> 00:01:10,340
被要求執行其中的一個，
兩人或許them--他們兩個

27
00:01:10,340 --> 00:01:12,319
在你的pset中。

28
00:01:12,319 --> 00:01:14,610
好了，我只是要
開始與一些公告。

29
00:01:14,610 --> 00:01:19,070
我們一起去了棧和隊列的更多的
深度比我們的測驗以前那樣。

30
00:01:19,070 --> 00:01:20,990
我們一起去了掛
再次，再次列出，

31
00:01:20,990 --> 00:01:23,899
更深入的比
我們在測驗前了。

32
00:01:23,899 --> 00:01:26,440
然後我們來談談哈希
表，樹和嘗試，這

33
00:01:26,440 --> 00:01:28,890
都是很必要的PSET。

34
00:01:28,890 --> 00:01:32,925
然後我們將介紹一些
有用的技巧pset5。

35
00:01:32,925 --> 00:01:37,360
>> 好了，測驗0。

36
00:01:37,360 --> 00:01:41,090
平均為58％。

37
00:01:41,090 --> 00:01:45,370
這是非常低的，所以你們所有
按照表現非常，非常好

38
00:01:45,370 --> 00:01:46,510
這一點。

39
00:01:46,510 --> 00:01:49,970
>> 好看多了，經驗法則是，如果你是
內的平均值的標準偏差

40
00:01:49,970 --> 00:01:52,990
特別是因為我們正處在一個較小
舒適的部分，你完全罰款。

41
00:01:52,990 --> 00:01:54,120
你的軌道上。

42
00:01:54,120 --> 00:01:55,190
生活是美好的。

43
00:01:55,190 --> 00:01:58,952
>> 我知道它的可怕認為
我喜歡這個測驗40％。

44
00:01:58,952 --> 00:02:00,160
我要失敗，這個類。

45
00:02:00,160 --> 00:02:02,243
我答應你，你不
要失敗的類。

46
00:02:02,243 --> 00:02:03,680
你完全罰款。

47
00:02:03,680 --> 00:02:06,850
>> 對於那些你們誰得到了
平均，令人印象深刻的，令人印象深刻，

48
00:02:06,850 --> 00:02:08,780
像，認真做得很好。

49
00:02:08,780 --> 00:02:09,689
我讓他們和我在一起。

50
00:02:09,689 --> 00:02:11,730
隨時來讓他們
在段的末端。

51
00:02:11,730 --> 00:02:14,520
我們如果您有任何我知道，
問題，與他們的問題。

52
00:02:14,520 --> 00:02:17,204
如果我們增加了你的分數
錯了，讓我們知道。

53
00:02:17,204 --> 00:02:21,240
>> 好了，pset5，這是一個非常
奇怪的一周耶魯大學的意義

54
00:02:21,240 --> 00:02:24,240
我們的PSET是由於
週三中午，包括

55
00:02:24,240 --> 00:02:27,317
晚一天，所以它實際上
中午星期二理論上所致。

56
00:02:27,317 --> 00:02:29,150
大概沒有人完成
在週二中午。

57
00:02:29,150 --> 00:02:30,830
這是完全正常。

58
00:02:30,830 --> 00:02:33,700
我們將有辦公時間
今晚以及週一晚上。

59
00:02:33,700 --> 00:02:36,810
和所有的部分將於本週
實際上變成車間，

60
00:02:36,810 --> 00:02:38,800
您可以隨意彈出的
你想要的任何部分，

61
00:02:38,800 --> 00:02:42,810
他們會是怎樣的迷你PSET
講習班上的幫助。

62
00:02:42,810 --> 00:02:45,620
因此，作為這樣的，這是唯一的部
在這裡我們教材。

63
00:02:45,620 --> 00:02:49,220
所有其他部分將集中
專門對pset的幫助。

64
00:02:49,220 --> 00:02:50,146
是嗎？

65
00:02:50,146 --> 00:02:52,000
>> 聽眾：在哪裡上班時間？

66
00:02:52,000 --> 00:02:56,120
>> ANDI彭：辦公時間
tonight--哦，很好的問題。

67
00:02:56,120 --> 00:03:00,580
我想今晚辦公時間
在蒂爾或共享。

68
00:03:00,580 --> 00:03:02,984
如果你在網上查詢CS50
你去辦公時間，

69
00:03:02,984 --> 00:03:05,650
應該有一個時間表
告訴您所有的人都。

70
00:03:05,650 --> 00:03:07,954
>> 我知道，無論是今晚
或者明天是水鴨，

71
00:03:07,954 --> 00:03:10,120
我想我們可以有
公地的晚上。

72
00:03:10,120 --> 00:03:11,020
我不太肯定。

73
00:03:11,020 --> 00:03:11,700
好問題。

74
00:03:11,700 --> 00:03:14,430
檢查CS50。

75
00:03:14,430 --> 00:03:18,780
>> 酷，任何有關的問題
計劃在未來像三個日子嗎？

76
00:03:18,780 --> 00:03:21,690
我保證你們喜歡大衛
說，這是在山頂上。

77
00:03:21,690 --> 00:03:23,050
你們是幾乎沒有。

78
00:03:23,050 --> 00:03:24,644
僅僅三天。

79
00:03:24,644 --> 00:03:26,310
到達那裡，然後我們都來了。

80
00:03:26,310 --> 00:03:28,114
我們將有一個很好的CS-免費休息。

81
00:03:28,114 --> 00:03:28,780
我們會回來的。

82
00:03:28,780 --> 00:03:30,779
我們將深入到網絡
編程與開發，

83
00:03:30,779 --> 00:03:35,150
事情是非常有趣的對比
一些其他的pset的。

84
00:03:35,150 --> 00:03:37,974
而這將是淒涼，
我們有很多的樂趣。

85
00:03:37,974 --> 00:03:38,890
我們將有更多的糖果。

86
00:03:38,890 --> 00:03:39,730
對不起，糖果。

87
00:03:39,730 --> 00:03:40,945
我忘了糖果。

88
00:03:40,945 --> 00:03:43,310
這是一個粗糙的早晨。

89
00:03:43,310 --> 00:03:46,340
所以，你們是幾乎沒有，
而且我非常自豪的你們的。

90
00:03:46,340 --> 00:03:49,570
>> 好了，棧。

91
00:03:49,570 --> 00:03:53,331
誰愛傑克的問題
和他的衣服上的測驗？

92
00:03:53,331 --> 00:03:53,830
沒有人？

93
00:03:53,830 --> 00:03:56,500
好了，這很好。

94
00:03:56,500 --> 00:04:00,200
>> 所以基本上，你可以
圖片傑克，這個傢伙在這裡，

95
00:04:00,200 --> 00:04:03,350
喜歡拿衣服
出棧的頂部，

96
00:04:03,350 --> 00:04:05,750
他把它放回
之後，他在堆棧的完成。

97
00:04:05,750 --> 00:04:07,600
因此以這種方式，他從未
似乎越來越

98
00:04:07,600 --> 00:04:10,090
到的底部
堆在他的衣服。

99
00:04:10,090 --> 00:04:12,600
所以，這樣的描述
基本的數據結構

100
00:04:12,600 --> 00:04:16,610
一個堆棧是如何實現的。

101
00:04:16,610 --> 00:04:20,060
>> 從本質上講，想想
協議棧的任何棧對象

102
00:04:20,060 --> 00:04:24,900
你把東西到頂部，
那麼你從頂部彈出出來。

103
00:04:24,900 --> 00:04:28,600
因此，後進先出法是我們喜歡的縮寫
以use--後進先出。

104
00:04:28,600 --> 00:04:32,480
所以，最後到的頂部
棧是第一個出來。

105
00:04:32,480 --> 00:04:34,260
這樣一來，兩個詞
我們喜歡聯想

106
00:04:34,260 --> 00:04:36,190
與被稱為push和pop。

107
00:04:36,190 --> 00:04:39,790
當你把一些東西到
堆棧和你的流行回來了。

108
00:04:39,790 --> 00:04:43,422
>> 所以我想這是種
抽象的概念，對於那些你

109
00:04:43,422 --> 00:04:45,630
誰希望看到像
這實際執行

110
00:04:45,630 --> 00:04:46,740
在現實世界中。

111
00:04:46,740 --> 00:04:50,170
你們有多少人寫了一篇文章，
也許就像一個小時之前，這是由於，

112
00:04:50,170 --> 00:04:54,510
你不小心刪除了一個巨大的
大塊的它，就像不小心？

113
00:04:54,510 --> 00:04:58,560
然後呢控制做
我們用它來把它放回去？

114
00:04:58,560 --> 00:05:00,030
控制-Z，是嗎？

115
00:05:00,030 --> 00:05:03,640
控制-Z，所以倍量
控制-Z已經救了我的命，

116
00:05:03,640 --> 00:05:08,820
救了我的屁股，每次
該真實通過煙囪實現。

117
00:05:08,820 --> 00:05:13,020
>> 基本上所有的信息
這是您的Word文檔，

118
00:05:13,020 --> 00:05:15,080
它被壓入和彈出的意願。

119
00:05:15,080 --> 00:05:19,460
所以基本上每當你
刪除任何東西，你的流行回來了。

120
00:05:19,460 --> 00:05:22,820
然後，如果你需要它回來，你
推，這是控制-C一樣。

121
00:05:22,820 --> 00:05:26,770
所以，現實世界中的功能
多麼簡單的數據結構

122
00:05:26,770 --> 00:05:28,690
可以幫助你的日常生活。

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> 因此，一個結構的方式，
我們實際上創建一個堆。

125
00:05:40,150 --> 00:05:44,720
我們定義類型結構，然後
我們把它在底部堆。

126
00:05:44,720 --> 00:05:47,440
和棧內，
我們有兩個參數

127
00:05:47,440 --> 00:05:51,580
我們基本上可以操縱，
所以我們有字符的字符串星能力。

128
00:05:51,580 --> 00:05:55,150
>> 所有這一切是做
正在創建一個數組

129
00:05:55,150 --> 00:05:58,835
我們可以存儲任何你想要的
我們可以判斷其能力。

130
00:05:58,835 --> 00:06:01,990
能力是剛剛最大金額
項目我們可以把這個數組。

131
00:06:01,990 --> 00:06:05,660
INT大小是保持計數器
跟踪有多少項目是目前

132
00:06:05,660 --> 00:06:07,850
在棧。

133
00:06:07,850 --> 00:06:11,860
所以後來我們就可以跟踪，A，
無論有多大的實際堆棧，

134
00:06:11,860 --> 00:06:14,850
和，B多少該堆棧的
我們充滿因為我們不希望

135
00:06:14,850 --> 00:06:18,800
溢出超過了我們的能力。

136
00:06:18,800 --> 00:06:24,340
>> 因此，例如，這個可愛的
問題是你的測驗。

137
00:06:24,340 --> 00:06:28,160
從本質上講，我們如何推動
到堆棧的頂部。

138
00:06:28,160 --> 00:06:28,830
很簡單。

139
00:06:28,830 --> 00:06:30,621
如果你看看吧，
我們將穿行於此。

140
00:06:30,621 --> 00:06:32,640
如果[聽不清] size--
請記住，當你

141
00:06:32,640 --> 00:06:35,300
要訪問任何
一個結構內的參數，

142
00:06:35,300 --> 00:06:40,320
你做struct.parameter的名稱。

143
00:06:40,320 --> 00:06:42,720
>> 在這種情況下，s是
我們的疊層的名稱。

144
00:06:42,720 --> 00:06:46,230
我們要訪問的大小
這一點，所以我們做s.size。

145
00:06:46,230 --> 00:06:50,280
所以只要尺寸不
等於能力，長

146
00:06:50,280 --> 00:06:52,940
因為它是低於產能，
要么就在這裡工作。

147
00:06:52,940 --> 00:06:57,180
>> 你想訪問內
你的籌碼，所以s.strings，

148
00:06:57,180 --> 00:07:00,790
你打算把新號碼
要插入到那裡。

149
00:07:00,790 --> 00:07:05,030
遠的不說，我們將要
插入INTñ壓入堆棧，

150
00:07:05,030 --> 00:07:08,905
我們可以做s.strings，
括號，s.size等於ñ。

151
00:07:08,905 --> 00:07:11,030
由於尺寸是我們
當前有在堆棧

152
00:07:11,030 --> 00:07:14,590
如果我們要推動
它，我們剛剛訪問

153
00:07:14,590 --> 00:07:17,370
無論大小，則
疊層的當​​前飽脹，

154
00:07:17,370 --> 00:07:21,729
我們推INTñ到它。

155
00:07:21,729 --> 00:07:24,770
然後我們要確保
我們也遞增了n個大小，

156
00:07:24,770 --> 00:07:27,436
所以我們可以跟踪我們已經
增加了一個額外的東西到堆棧中。

157
00:07:27,436 --> 00:07:29,660
現在我們有一個更大的尺寸。

158
00:07:29,660 --> 00:07:33,196
這是否在這裡是有意義的
大家，如何在邏輯上是否可行？

159
00:07:33,196 --> 00:07:34,160
這是一種快捷。

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
聽眾：你可以走了
在s.stringss.strings [s.size]了嗎？

162
00:07:42,160 --> 00:07:45,808
ANDI彭：當然，有什麼呢
s.size目前給我們？

163
00:07:45,808 --> 00:07:47,440
聽眾：這是當前大小。

164
00:07:47,440 --> 00:07:50,890
ANDI鵬：沒錯，所以
目前的指數，我們的規模是，

165
00:07:50,890 --> 00:07:57,780
所以我們希望把新的整數
我們要插入s.size。

166
00:07:57,780 --> 00:07:58,760
這是否有意義？

167
00:07:58,760 --> 00:08:01,110
因為s.strings，所有的
是是陣列的名稱。

168
00:08:01,110 --> 00:08:03,510
所有這是訪問
我們的結構內的數組，

169
00:08:03,510 --> 00:08:06,030
因此，如果我們想
將正成指數，

170
00:08:06,030 --> 00:08:09,651
我們可以只訪問
使用括號s.size。

171
00:08:09,651 --> 00:08:10,150
酷。

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> 好吧，流行，我偽出來
為你們這些傢伙，但類似的概念。

174
00:08:18,916 --> 00:08:19,790
這是否有意義？

175
00:08:19,790 --> 00:08:22,310
如果尺寸大於
大於零，則

176
00:08:22,310 --> 00:08:25,350
知道你想要拿東西
出，因為如果尺寸不

177
00:08:25,350 --> 00:08:27,620
大於零，則
有沒有在堆棧中。

178
00:08:27,620 --> 00:08:29,840
>> 所以，你只需要執行
這段代碼，它只能

179
00:08:29,840 --> 00:08:32,320
彈出如果有什麼流行。

180
00:08:32,320 --> 00:08:35,830
所以如果尺寸更大
大於0，我們減去大小。

181
00:08:35,830 --> 00:08:40,020
我們減小大小，然後返回
無論是內部的，因為

182
00:08:40,020 --> 00:08:42,710
通過彈出，我們要
無論是存儲的訪問

183
00:08:42,710 --> 00:08:45,694
在堆棧的頂部的索引。

184
00:08:45,694 --> 00:08:46,610
一切有意義嗎？

185
00:08:46,610 --> 00:08:49,693
如果我讓你們寫了這一點，
將你們能寫出來？

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK，你們可以玩它。

188
00:08:53,570 --> 00:08:55,252
不用擔心，如果你不明白這一點。

189
00:08:55,252 --> 00:08:57,460
我們沒有時間去編寫
它今天因為我們

190
00:08:57,460 --> 00:08:59,959
得到了很多這些結構
穿過去，但本質

191
00:08:59,959 --> 00:09:02,214
偽代碼，非常，非常相似推。

192
00:09:02,214 --> 00:09:03,380
只要跟著邏輯。

193
00:09:03,380 --> 00:09:06,092
請確保你所訪問的所有
你的結構功能正常。

194
00:09:06,092 --> 00:09:06,574
是嗎？

195
00:09:06,574 --> 00:09:09,282
>> 聽眾：請問這些幻燈片和
這整個事情高達今天十歲上下的？

196
00:09:09,282 --> 00:09:11,586
ANDI彭：始終，是的。

197
00:09:11,586 --> 00:09:13,710
我會盡量把
這像一個小時後。

198
00:09:13,710 --> 00:09:16,626
我會通過電子郵件大衛，大衛將嘗試
把它像在此之後一個小時。

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> 好了，接下來我們進入這個其他
可愛的數據結構稱為隊列。

201
00:09:25,470 --> 00:09:30,140
正如你們所看到的，一
隊列，對於我們中間英國，

202
00:09:30,140 --> 00:09:32,010
所有這是一條線。

203
00:09:32,010 --> 00:09:34,680
那麼相反的是
你覺得一個堆棧，

204
00:09:34,680 --> 00:09:37,750
隊列是什麼
在邏輯上，你認為它是。

205
00:09:37,750 --> 00:09:41,914
它保持由FIFO的規則，
這是先入先出。

206
00:09:41,914 --> 00:09:43,705
如果你是第一個
一個在行，你

207
00:09:43,705 --> 00:09:46,230
第一個
出來的線。

208
00:09:46,230 --> 00:09:49,680
>> 所以，我們喜歡把這種
在出隊，並排入隊列。

209
00:09:49,680 --> 00:09:52,380
如果我們想要添加的東西
我們的隊列中，我們入隊。

210
00:09:52,380 --> 00:09:55,690
如果我們要離隊，或採取
一些東西，我們出隊。

211
00:09:55,690 --> 00:10:03,350
>> 因此，同樣的道理，我們是那種
創建固定大小的元素，我們

212
00:10:03,350 --> 00:10:06,500
可以存儲一定的
的事情，但是我們也可以

213
00:10:06,500 --> 00:10:10,100
改變我們正在把
他們的內部參數

214
00:10:10,100 --> 00:10:13,140
基於什麼類型
功能我們想要的。

215
00:10:13,140 --> 00:10:16,700
所以棧，我們希望最後
酮，N是第一個出來。

216
00:10:16,700 --> 00:10:19,800
排隊是我們要的第一件事情
在成為第一件事出去。

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> 因此，結構型
定義，你可以看到，

219
00:10:26,710 --> 00:10:29,470
這是一個有點不同
從什麼堆棧是

220
00:10:29,470 --> 00:10:33,120
因為我們不僅要保持
軌道的其中該尺寸是目前，

221
00:10:33,120 --> 00:10:37,420
我們也想跟踪頭
以及我們當前有。

222
00:10:37,420 --> 00:10:39,580
所以我覺得它更容易
如果我畫這件事。

223
00:10:39,580 --> 00:10:53,270
因此，讓我們想像一下，我們已經有了一個隊列，
所以我們說，頭就在這裡。

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
該行的負責人，讓我們
只是說這是目前在那裡，

226
00:10:58,310 --> 00:11:01,809
我們要插入
事到隊列。

227
00:11:01,809 --> 00:11:04,350
我要去基本上調用大小
是同樣的事情，尾，

228
00:11:04,350 --> 00:11:06,314
哪裡的隊列的末尾。

229
00:11:06,314 --> 00:11:07,730
遠的不說大小就在這裡。

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> 那麼，如何切實
東西插入到隊列中？

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
什麼樣的指標，我們要放置
在這裡我們要插入。

234
00:11:24,130 --> 00:11:29,320
如果這是開頭的
排隊，這是它的結束

235
00:11:29,320 --> 00:11:31,860
或者它的大小，我們在哪裡
要添加的下一個對象？

236
00:11:31,860 --> 00:11:32,920
>> 聽眾：[聽不清]

237
00:11:32,920 --> 00:11:35,920
ANDI鵬：沒錯，你想添加
它取決於你寫的。

238
00:11:35,920 --> 00:11:37,840
這要么是空白，或為空。

239
00:11:37,840 --> 00:11:42,630
所以，你想可能添加
在這裡，因為如果大小is--

240
00:11:42,630 --> 00:11:50,540
如果這些都滿了，你想
將其添加在這裡，對不對？

241
00:11:50,540 --> 00:11:57,150
>> 所以這就是，雖然非常非常
簡單，不太總是正確的

242
00:11:57,150 --> 00:12:00,690
因為主要的區​​別
隊列和堆之間

243
00:12:00,690 --> 00:12:04,350
是，隊列可以
實際上被操縱

244
00:12:04,350 --> 00:12:06,980
使頭部的變化
這取決於你想上哪兒

245
00:12:06,980 --> 00:12:08,650
您的線索年初啟動。

246
00:12:08,650 --> 00:12:11,900
其結果，你的尾巴
也不會改變。

247
00:12:11,900 --> 00:12:14,770
所以看看
此代碼現在。

248
00:12:14,770 --> 00:12:18,620
正如你們也被要求
寫出來的測驗，入隊。

249
00:12:18,620 --> 00:12:22,580
也許我們會聊過為什麼
答案是什麼。

250
00:12:22,580 --> 00:12:26,790
>> 在一個我不太適合這一行，
但本質上這一段代碼

251
00:12:26,790 --> 00:12:29,030
應該是在一行上。

252
00:12:29,030 --> 00:12:30,140
花想30秒。

253
00:12:30,140 --> 00:12:33,000
看看，看看為什麼
這是，它是這樣的。

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> 非常，非常相似的結構，非常，非常
類似的結構與前面

256
00:12:55,420 --> 00:12:58,090
堆疊除了可能
一行代碼。

257
00:12:58,090 --> 00:13:01,190
而這一行代碼
確定的功能。

258
00:13:01,190 --> 00:13:03,900
它真的與眾不同
從一摞一個隊列。

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> 任何人想採取刺
在解釋為什麼你

261
00:13:22,010 --> 00:13:24,980
拿到這裡這個複雜的事情？

262
00:13:24,980 --> 00:13:27,845
我們看到的回報我們
美妙的朋友模量。

263
00:13:27,845 --> 00:13:31,020
正如你們很快就會到來
在編程認識到，

264
00:13:31,020 --> 00:13:34,910
幾乎任何時候，你需要的東西
環繞什麼，

265
00:13:34,910 --> 00:13:36,850
模將是這樣做的方式。

266
00:13:36,850 --> 00:13:40,510
因此，了解的是，沒有人想
嘗試解釋該行代碼？

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
是的，所有的答案都
接受和歡迎。

269
00:13:47,507 --> 00:13:48,840
聽眾：你是在跟我說話？

270
00:13:48,840 --> 00:13:49,506
ANDI彭：是的。

271
00:13:49,506 --> 00:13:56,200
聽眾：哦，不後悔。

272
00:13:56,200 --> 00:14:00,250
ANDI彭：好，讓我們
穿行此代碼。

273
00:14:00,250 --> 00:14:03,642
所以，當你想
添加的東西到一個隊列，

274
00:14:03,642 --> 00:14:08,510
在可愛的情況下頭部發生
是在這裡，這很容易讓我們

275
00:14:08,510 --> 00:14:10,960
剛走到最後
插入的東西，對不對？

276
00:14:10,960 --> 00:14:14,690
但是隊列的整點
頭部實際上可以動態地

277
00:14:14,690 --> 00:14:17,280
不同的地方改變我們
希望我們的Q的開始是，

278
00:14:17,280 --> 00:14:19,880
正因為如此，在尾
也不會改變。

279
00:14:19,880 --> 00:14:31,100
>> 所以，想像一下，這是不是
排隊，而是這是隊列。

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
比方說，頭就在這裡。

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
比方說，我們的隊列看上去像這樣。

284
00:14:56,980 --> 00:15:00,190
如果我們想轉向哪裡
該行的開始是，

285
00:15:00,190 --> 00:15:03,400
假設我們轉向頭
這種方式和尺寸在這裡。

286
00:15:03,400 --> 00:15:07,100
>> 現在我們要添加一些
此隊列，但你們可以看到，

287
00:15:07,100 --> 00:15:11,150
它不是那麼簡單，只是
添加任何的尺寸後，

288
00:15:11,150 --> 00:15:13,630
因為那樣的話，我們用完
我們的實際數組的邊界。

289
00:15:13,630 --> 00:15:16,190
當我們要真正增加在這裡。

290
00:15:16,190 --> 00:15:18,610
這是一個隊列的美
是我們的，視覺上

291
00:15:18,610 --> 00:15:22,380
看起來像行是這樣的，
但是，當存儲在數據結構中，

292
00:15:22,380 --> 00:15:29,370
他們給它像一個循環。

293
00:15:29,370 --> 00:15:32,360
它種環繞
到前以同樣的方式

294
00:15:32,360 --> 00:15:34,780
該行也可以換
各地根據地方你

295
00:15:34,780 --> 00:15:36,279
希望該行的開頭是。

296
00:15:36,279 --> 00:15:38,630
因此，如果我們拿
往下看這裡，讓我們

297
00:15:38,630 --> 00:15:40,880
說我們想創造一個
函數調用排隊。

298
00:15:40,880 --> 00:15:43,980
我們希望加INT n為進的Q值。

299
00:15:43,980 --> 00:15:49,250
如果q.size q--我們會打電話給我們的數據
結構 - 如果我們的queue.size不

300
00:15:49,250 --> 00:15:52,520
等於能力，或者
這是不到容量，

301
00:15:52,520 --> 00:15:55,120
q.strings是我們q內的陣列。

302
00:15:55,120 --> 00:15:58,380
我們要設置
這等於q.heads，

303
00:15:58,380 --> 00:16:02,730
這是在這裡，再加上q.size
模量由容量，這

304
00:16:02,730 --> 00:16:04,290
包裹我們回在這裡。

305
00:16:04,290 --> 00:16:08,040
>> 所以在這個例子中，索引
頭是1，對吧？

306
00:16:08,040 --> 00:16:11,480
大小的指數為0，1，2，3，4。

307
00:16:11,480 --> 00:16:19,500
因此，我們可以做到1加4模
我們的產能是5。

308
00:16:19,500 --> 00:16:20,920
是什麼給我們？

309
00:16:20,920 --> 00:16:23,270
什麼是索引
這樣來的？

310
00:16:23,270 --> 00:16:24,080
>> 聽眾：0。

311
00:16:24,080 --> 00:16:27,870
>> ANDI彭：0，
恰好就在這裡，

312
00:16:27,870 --> 00:16:30,640
所以我們希望能夠
插入到這裡。

313
00:16:30,640 --> 00:16:34,730
所以這個公式在這裡種
僅適用於任何數字

314
00:16:34,730 --> 00:16:36,750
不同的地方你
頭部和你的尺寸是。

315
00:16:36,750 --> 00:16:38,541
如果你知道這些
事情是，你知道

316
00:16:38,541 --> 00:16:43,170
正是您要插入
您的隊列後，無論是。

317
00:16:43,170 --> 00:16:44,640
這是否有意義給大家？

318
00:16:44,640 --> 00:16:48,560
>> 我知道怎樣的一個大腦
傳情特別是因為這

319
00:16:48,560 --> 00:16:50,512
排在你競猜的善後工作。

320
00:16:50,512 --> 00:16:52,220
但希望大家
現在可以理解

321
00:16:52,220 --> 00:16:57,800
為什麼這個解決方案或本
功能是，它是這樣的。

322
00:16:57,800 --> 00:16:59,840
任何人都有點不清楚的是什麼？

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
確定。

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> 所以現在，如果你
要離隊，這

327
00:17:09,970 --> 00:17:15,240
是我們的頭會轉向
因為如果我們要出列，

328
00:17:15,240 --> 00:17:17,030
我們不取下q的末端。

329
00:17:17,030 --> 00:17:19,130
我們要起飛的頭，對不對？

330
00:17:19,130 --> 00:17:24,260
因此，作為結果，磁頭會改變，
這就是為什麼當你入隊，

331
00:17:24,260 --> 00:17:26,800
你必須保持跟踪
在這裡你的頭，你的尺寸

332
00:17:26,800 --> 00:17:29,450
是能夠插入
到正確的位置。

333
00:17:29,450 --> 00:17:32,740
>> 所以，當你出列，
我還偽出來。

334
00:17:32,740 --> 00:17:35,480
隨意，如果你想
嘗試編碼了這一點。

335
00:17:35,480 --> 00:17:36,980
要移動頭部，對不對？

336
00:17:36,980 --> 00:17:39,320
如果我想離隊，我
將移動頭以上。

337
00:17:39,320 --> 00:17:40,800
這將是頭部。

338
00:17:40,800 --> 00:17:45,617
>> 而我們目前的規模會
減去因為我們不再

339
00:17:45,617 --> 00:17:46,950
在陣列中四個元素。

340
00:17:46,950 --> 00:17:51,370
我們只有三個，然後我們要
返回不管裡面儲存

341
00:17:51,370 --> 00:17:56,260
頭部，因為我們希望藉此
值出所以非常相似的棧。

342
00:17:56,260 --> 00:17:58,010
只要你參加
來自不同的地方，

343
00:17:58,010 --> 00:18:01,770
你必須重新分配指針
不同的地方作為一個結果。

344
00:18:01,770 --> 00:18:03,890
從邏輯上講，每個人都遵循？

345
00:18:03,890 --> 00:18:05,690
太好了。

346
00:18:05,690 --> 00:18:10,156
>> 好了，我們要商量了一下
更深入的了解鍊錶

347
00:18:10,156 --> 00:18:13,280
因為他們將是非常，非常有價值
您在本週的過程

348
00:18:13,280 --> 00:18:14,964
pset中。

349
00:18:14,964 --> 00:18:17,130
鍊錶，因為你們
能記住，一切又都

350
00:18:17,130 --> 00:18:22,570
是有一定的節點節點
兩者的值和一個指針值

351
00:18:22,570 --> 00:18:26,290
連接在一起的
通過這些指針。

352
00:18:26,290 --> 00:18:29,880
因此如何在結構
我們在這裡創建一個節點，我們

353
00:18:29,880 --> 00:18:33,569
是int n，這個是什麼
在商店或字符串值n

354
00:18:33,569 --> 00:18:35,610
或者任何你想
調用它，焦炭星ñ。

355
00:18:35,610 --> 00:18:41,482
結構節點星，這是指針
要在每個節點上，

356
00:18:41,482 --> 00:18:43,690
你將有
對下一個指針點。

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
你得頭
鍊錶那

359
00:18:50,040 --> 00:18:53,140
要指出的其餘部分
等等，等等的值

360
00:18:53,140 --> 00:18:55,290
直到你最終到達終點。

361
00:18:55,290 --> 00:18:58,040
而這最後一個節點僅僅是
要沒有一個指針。

362
00:18:58,040 --> 00:18:59,952
這將指向
空，這就是當

363
00:18:59,952 --> 00:19:01,910
你知道你已經打了
您的鏈接列表的末尾

364
00:19:01,910 --> 00:19:04,076
就是當你的最後一個指針
不指向任何東西。

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> 因此，我們要去多一點的
關於深入怎麼一會可能

367
00:19:10,990 --> 00:19:12,400
搜索一個鍊錶。

368
00:19:12,400 --> 00:19:15,460
記住是一些
該鍊錶的缺點

369
00:19:15,460 --> 00:19:19,340
詩句關於搜索的陣列。

370
00:19:19,340 --> 00:19:22,565
數組可以二進制搜索，但
你為什麼不能做，在一個鍊錶？

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> 聽眾：因為他們都是互相聯繫在一起，
但你不太知道在哪裡

373
00:19:30,320 --> 00:19:31,330
[聽不清]。

374
00:19:31,330 --> 00:19:34,600
>> ANDI彭：是的，正是這樣記
一個數組的輝煌

375
00:19:34,600 --> 00:19:37,190
是事實，我們有
隨機存取存儲器，其中

376
00:19:37,190 --> 00:19:41,580
如果我想從指數值
六，我可以說，指數六，

377
00:19:41,580 --> 00:19:42,407
給我的價值。

378
00:19:42,407 --> 00:19:45,240
那是因為數組排序
在一個連續的內存空間

379
00:19:45,240 --> 00:19:48,020
在一個地方，而
一種鍊錶

380
00:19:48,020 --> 00:19:52,820
是隨機散佈各地，
而只有這樣，你可以找到一個

381
00:19:52,820 --> 00:19:56,890
是通過指針，告訴你
的，其中該下一個節點是地址。

382
00:19:56,890 --> 00:20:00,290
>> 所以作為結果，只有這樣
通過一個鏈接列表來搜索

383
00:20:00,290 --> 00:20:01,560
是線性搜索。

384
00:20:01,560 --> 00:20:05,890
因為我完全不知道在哪裡
在該鏈接的表的第12值是，

385
00:20:05,890 --> 00:20:08,780
我必須遍歷全部
那鏈接列表中的一個

386
00:20:08,780 --> 00:20:12,450
由一個從頭部到第一節點，
到第二個節點，到第三節點，

387
00:20:12,450 --> 00:20:17,690
一路下來，直到我終於搞定
到這個節點，我要找的是。

388
00:20:17,690 --> 00:20:22,110
因此在這個意義上說，搜索
上鍊錶總是n。

389
00:20:22,110 --> 00:20:23,040
它總是ñ。

390
00:20:23,040 --> 00:20:25,690
它總是以線性時間。

391
00:20:25,690 --> 00:20:28,470
>> 這樣一來，代碼中
我們實現這一點，而這

392
00:20:28,470 --> 00:20:32,620
有點新的你們，因為你們
人還沒有真正談過或曾經

393
00:20:32,620 --> 00:20:35,000
在如何看到指針
通過搜索指針，

394
00:20:35,000 --> 00:20:37,670
因此，我們將演練
這個非常，非常緩慢。

395
00:20:37,670 --> 00:20:40,200
所以布爾檢索，權，
讓我們想像一下，我們希望

396
00:20:40,200 --> 00:20:42,820
創建一個名為函數
搜索返回true

397
00:20:42,820 --> 00:20:46,820
如果您發現裡面的鏈接的價值
列表，並將否則返回​​false。

398
00:20:46,820 --> 00:20:50,030
節點明星名單
目前只是指針

399
00:20:50,030 --> 00:20:52,960
在你的鏈接列表中的第一項。

400
00:20:52,960 --> 00:20:56,700
INT N是你的價值
搜尋在該列表中。

401
00:20:56,700 --> 00:20:58,770
>> 因此，節點星指針等於名單。

402
00:20:58,770 --> 00:21:00,970
這意味著我們正在設置
和創建的指針

403
00:21:00,970 --> 00:21:03,592
到列表的內部該第一個節點。

404
00:21:03,592 --> 00:21:04,300
每個人都和我在一起？

405
00:21:04,300 --> 00:21:06,530
因此，如果我們當中去
回到這裡，我會

406
00:21:06,530 --> 00:21:13,850
初始化指針指向
無論頭部的名單。

407
00:21:13,850 --> 00:21:18,600
>> 然後，一旦你到這裡，
同時指針不等於空，

408
00:21:18,600 --> 00:21:22,160
所以這是我們在其中循環
將要隨後遍歷

409
00:21:22,160 --> 00:21:25,940
我們因為什麼列表的其餘部分
發生在指針等於null？

410
00:21:25,940 --> 00:21:27,550
我們知道，我們have--

411
00:21:27,550 --> 00:21:28,450
>> 聽眾：[聽不清]

412
00:21:28,450 --> 00:21:31,491
>> ANDI鵬：沒錯，所以我們知道，
我們已經達到列表的末尾，對不對？

413
00:21:31,491 --> 00:21:34,470
如果你回到這裡，每個節點
應指向另一節點

414
00:21:34,470 --> 00:21:36,550
等等等等
直到你打最後

415
00:21:36,550 --> 00:21:41,589
您鍊錶的尾部，
它具有一個指針，只是

416
00:21:41,589 --> 00:21:43,130
不點不是沒有其他任何地方。

417
00:21:43,130 --> 00:21:47,510
所以你基本上知道
你的名單仍然有上升

418
00:21:47,510 --> 00:21:50,900
直到指針不等於
null，因為一旦它等於空，

419
00:21:50,900 --> 00:21:53,310
你知道，有沒有更多的東西。

420
00:21:53,310 --> 00:21:56,930
>> 所以這是循環，其中我們
將有實際的搜索。

421
00:21:56,930 --> 00:22:01,690
而如果pointer--你看
那種箭功能那裡？

422
00:22:01,690 --> 00:22:06,930
因此，如果指針指向為n，如果
在n等於等於n個指針，

423
00:22:06,930 --> 00:22:09,180
因此，這意味著，如果
你是指針

424
00:22:09,180 --> 00:22:13,420
在每個結束搜索
節點實際上等於值

425
00:22:13,420 --> 00:22:15,990
你要找的話
要返回true。

426
00:22:15,990 --> 00:22:19,280
所以基本上，如果你在一個節點
有你正在尋找的價值，

427
00:22:19,280 --> 00:22:23,550
你知道你已經
能夠成功地搜索。

428
00:22:23,550 --> 00:22:27,150
>> 否則，你要設置
指針到下一個節點。

429
00:22:27,150 --> 00:22:28,850
這就是這條線在這裡做。

430
00:22:28,850 --> 00:22:31,750
指針等於下一個指針。

431
00:22:31,750 --> 00:22:33,360
每個人都看到了的工作？

432
00:22:33,360 --> 00:22:36,580
>> 而且基本上你要只
遍歷列表的全部，

433
00:22:36,580 --> 00:22:41,920
重置每一次，直到你的指針
你最終擊中列表的末尾。

434
00:22:41,920 --> 00:22:45,030
你知道有沒有
更多的節點進行搜索，

435
00:22:45,030 --> 00:22:47,999
然後你就可以返回false
因為你知道，哦，好吧，

436
00:22:47,999 --> 00:22:50,540
如果我已經能夠搜索
通過列表的全部。

437
00:22:50,540 --> 00:22:54,530
如果在這個例子中，如果我想
尋找值10，

438
00:22:54,530 --> 00:22:57,250
我開始在頭，
我搜索一路下跌，

439
00:22:57,250 --> 00:23:00,550
而我最終得到了這一點，這
一個指針指向空，

440
00:23:00,550 --> 00:23:04,415
我知道，廢話，我想10不
這個名單是因為我找不到它。

441
00:23:04,415 --> 00:23:06,520
而我在列表的末尾。

442
00:23:06,520 --> 00:23:11,040
而在這種情況下，你知道
我將返​​回false。

443
00:23:11,040 --> 00:23:12,900
>> 讓那浸泡在一點點。

444
00:23:12,900 --> 00:23:17,350
這將是非常
重要的是你的pset中。

445
00:23:17,350 --> 00:23:21,140
它的邏輯很簡單，也許
語法只是實現它。

446
00:23:21,140 --> 00:23:23,365
你們想使
確保你理解。

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
酷。

449
00:23:27,650 --> 00:23:32,560
>> 好了，我們怎麼會
插入節點，右，

450
00:23:32,560 --> 00:23:35,380
到列表中，因為記住
是什麼的有什麼好處，

451
00:23:35,380 --> 00:23:39,230
具有的鏈接列表與
在存儲方面的陣列？

452
00:23:39,230 --> 00:23:41,110
>> 聽眾：這是動態的，
所以它更容易用於：

453
00:23:41,110 --> 00:23:43,180
>> ANDI鵬：沒錯，
所以它是動態的，

454
00:23:43,180 --> 00:23:46,880
意味著它可以擴大和縮小
取決於用戶的需要。

455
00:23:46,880 --> 00:23:56,570
因此，在這個意義上，我們並不需要
浪費不必要的內存，因為我

456
00:23:56,570 --> 00:24:00,850
如果我不知道有多少值要
存儲，它沒有任何意義，我

457
00:24:00,850 --> 00:24:04,310
創建因為數組
如果我想存儲10個值

458
00:24:04,310 --> 00:24:08,380
我創建的1000陣列，這是
大量浪費的內存，配發。

459
00:24:08,380 --> 00:24:11,180
這就是為什麼我們要使用一個鏈接
列表能夠動態

460
00:24:11,180 --> 00:24:13,860
改變或縮小我們的規模。

461
00:24:13,860 --> 00:24:17,040
>> 而這樣就使得插入
有點複雜。

462
00:24:17,040 --> 00:24:20,810
既然我們不能隨意訪問元素
將我們的數組的方式。

463
00:24:20,810 --> 00:24:24,270
如果我想插入元素
進入第七個指標，

464
00:24:24,270 --> 00:24:26,930
我只是將它插入
進入第七個指標。

465
00:24:26,930 --> 00:24:30,020
上一個鍊錶，它不
很容易地工作，

466
00:24:30,020 --> 00:24:34,947
所以如果我們想插入
這裡一個在該鏈接的表，

467
00:24:34,947 --> 00:24:36,280
在視覺上，它很容易看到。

468
00:24:36,280 --> 00:24:39,363
我們只是希望將其插入那裡，
就在列表的開頭，

469
00:24:39,363 --> 00:24:40,840
後頭部右側。

470
00:24:40,840 --> 00:24:44,579
>> 但在其中，我們有方式重新分配
指針是不是有點繞口

471
00:24:44,579 --> 00:24:47,620
或者，從邏輯上講，這是有道理的，但
你要確保你擁有了它

472
00:24:47,620 --> 00:24:50,250
完全下來，因為
你想的最後一件事

473
00:24:50,250 --> 00:24:52,990
是重新分配的指針的
我們在這裡做的方式。

474
00:24:52,990 --> 00:24:58,170
如果取消引用
從頭指針為1，

475
00:24:58,170 --> 00:25:01,086
然後突然的的
您的鏈接列表的其餘部分

476
00:25:01,086 --> 00:25:04,680
是丟失，因為你還沒有真正
創建的臨時任何東西。

477
00:25:04,680 --> 00:25:06,220
這是指著2。

478
00:25:06,220 --> 00:25:10,080
如果重新分配的指針，那麼
列表的其餘部分完全喪失。

479
00:25:10,080 --> 00:25:13,310
所以，你想成為
非常非常小心這裡

480
00:25:13,310 --> 00:25:17,010
先分配
無論從任何你指針

481
00:25:17,010 --> 00:25:20,150
要插入到哪裡
你想，然後你

482
00:25:20,150 --> 00:25:22,710
可以取消引用列表的其餘部分。

483
00:25:22,710 --> 00:25:25,250
>> 因此，這適用於任何地方
你想插入。

484
00:25:25,250 --> 00:25:27,520
如果要插入的
頭，如果你想在這裡回答，

485
00:25:27,520 --> 00:25:29,455
如果要插入的
最後，好了，我到底

486
00:25:29,455 --> 00:25:30,910
猜你只想
有沒有指針，但你

487
00:25:30,910 --> 00:25:33,830
要確保你不
失去你的列表的其餘部分。

488
00:25:33,830 --> 00:25:36,640
你總是要確保
你的新節點指向

489
00:25:36,640 --> 00:25:39,330
對任何你
要插入，

490
00:25:39,330 --> 00:25:42,170
然後您可以添加鏈接上。

491
00:25:42,170 --> 00:25:43,330
大家都清楚了嗎？

492
00:25:43,330 --> 00:25:45,427
>> 這將是
一個真正的問題。

493
00:25:45,427 --> 00:25:48,010
其中一個最重要的問題
你要對你的pset

494
00:25:48,010 --> 00:25:51,340
是，你要嘗試創建
鍊錶和插入件事情

495
00:25:51,340 --> 00:25:53,340
但當時只是失去了
剩下的鍊錶中。

496
00:25:53,340 --> 00:25:54,900
而你要像我
不知道為什麼會這樣？

497
00:25:54,900 --> 00:25:58,040
而且這是一個痛苦的經歷
並搜索所有的指針。

498
00:25:58,040 --> 00:26:02,100
>> 我保證你在這pset中，
書寫和繪畫這些節點出

499
00:26:02,100 --> 00:26:03,344
將是非常，非常有幫助。

500
00:26:03,344 --> 00:26:06,010
所以，你可以完全跟踪
在那裡所有的指針，

501
00:26:06,010 --> 00:26:08,540
什麼錯，
您所有的節點，

502
00:26:08,540 --> 00:26:12,660
你需要做的訪問或
插入或刪除，或任何人。

503
00:26:12,660 --> 00:26:14,550
每個人都好有嗎？

504
00:26:14,550 --> 00:26:15,050
酷。

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> 因此，如果我們想看看代碼？

507
00:26:22,600 --> 00:26:24,470
哦，我不知道，如果我們
可以看到the--好了，

508
00:26:24,470 --> 00:26:27,940
頂部所有它是一個功能
在這裡我們要命名插入

509
00:26:27,940 --> 00:26:31,365
插入INT n為進鍊錶。

510
00:26:31,365 --> 00:26:32,740
我們將穿行於此。

511
00:26:32,740 --> 00:26:34,770
這是一個很大的代碼，有很多新的語法。

512
00:26:34,770 --> 00:26:36,220
我們會沒事的。

513
00:26:36,220 --> 00:26:39,120
>> 所以在頂部，每當
我們要創建什麼

514
00:26:39,120 --> 00:26:42,380
什麼我們需要做的，特別是如果你
希望它不被存儲在棧上

515
00:26:42,380 --> 00:26:43,920
但在堆？

516
00:26:43,920 --> 00:26:45,460
我們去的malloc，對不對？

517
00:26:45,460 --> 00:26:48,240
因此，我們要創建一個指針。

518
00:26:48,240 --> 00:26:52,074
節點，指針，新的平等
MALLOC一個節點的大小

519
00:26:52,074 --> 00:26:53,740
因為我們要創建的節點。

520
00:26:53,740 --> 00:26:56,720
我們想要的量
內存節點佔用

521
00:26:56,720 --> 00:26:59,300
將予配發的
創建新的節點。

522
00:26:59,300 --> 00:27:02,270
>> 然後我們要去檢查
查看是否有新的equals等於空。

523
00:27:02,270 --> 00:27:03,370
還記得我們說什麼？

524
00:27:03,370 --> 00:27:06,470
不管你的malloc，
要做就要你總是做什麼？

525
00:27:06,470 --> 00:27:09,490
你必須經常檢查，看看
無論是否是空。

526
00:27:09,490 --> 00:27:13,620
>> 例如，如果你的工作
系統完全滿，

527
00:27:13,620 --> 00:27:17,060
如果你在沒有更多的內存
所有你嘗試的malloc，

528
00:27:17,060 --> 00:27:18,410
它會返回null為您服務。

529
00:27:18,410 --> 00:27:21,094
所以，如果你嘗試使用它
當它指向空，

530
00:27:21,094 --> 00:27:23,260
你不打算能
來訪問該信息。

531
00:27:23,260 --> 00:27:27,010
所以，正因為如此，我們希望使
相信只要你mallocing，

532
00:27:27,010 --> 00:27:30,500
你總是檢查，如果看到
給你的內存為空。

533
00:27:30,500 --> 00:27:33,670
如果不是，那麼我們可以將
與我們的代碼的其餘部分。

534
00:27:33,670 --> 00:27:36,140
>> 所以，我們要
初始化新節點。

535
00:27:36,140 --> 00:27:39,050
我們要做新的n等於ñ。

536
00:27:39,050 --> 00:27:42,390
然後我們要做的
設置新的新指針

537
00:27:42,390 --> 00:27:46,900
為null，因為現在我們不這樣做
想要的任何東西它指向。

538
00:27:46,900 --> 00:27:48,755
我們不知道在哪裡
它會放你，

539
00:27:48,755 --> 00:27:50,630
然後，如果我們想
在頭部插入，

540
00:27:50,630 --> 00:27:53,820
那麼我們就可以重新分配
指針的頭部。

541
00:27:53,820 --> 00:27:58,530
每個人都遵循的邏輯
在那裡發生的事情？

542
00:27:58,530 --> 00:28:02,502
>> 我們所要做的是創建一個新的
節點，設置指針為空，

543
00:28:02,502 --> 00:28:04,210
然後重新分配
它的頭部，如果我們

544
00:28:04,210 --> 00:28:06,320
知道我們要在頭部，將其插入。

545
00:28:06,320 --> 00:28:09,420
然後將頭是要
指向新的節點。

546
00:28:09,420 --> 00:28:11,060
每個人都與該行嗎？

547
00:28:11,060 --> 00:28:12,380
>> 所以這是一個兩步過程。

548
00:28:12,380 --> 00:28:14,760
你必須先分配
無論你正在創建。

549
00:28:14,760 --> 00:28:18,260
設置指針到
引用，然後你

550
00:28:18,260 --> 00:28:21,400
能種非關聯化
第一個指針

551
00:28:21,400 --> 00:28:22,972
並指出其向新的節點。

552
00:28:22,972 --> 00:28:25,680
不管你想要去插入，
該邏輯要成立。

553
00:28:25,680 --> 00:28:27,530
>> 這有點像分配
臨時變量。

554
00:28:27,530 --> 00:28:28,700
請記住，你已經有了
確保你

555
00:28:28,700 --> 00:28:30,346
不要失去跟踪，如果你換了。

556
00:28:30,346 --> 00:28:33,470
你要確保你有一個
那種保持臨時變量

557
00:28:33,470 --> 00:28:35,620
軌道，其中那些事兒
存儲，讓你

558
00:28:35,620 --> 00:28:41,190
不丟失任何價值的過程
像瞎搞吧。

559
00:28:41,190 --> 00:28:42,710
>> OK，這樣的代碼將出現在這裡。

560
00:28:42,710 --> 00:28:45,020
你們採取部分後的樣子。

561
00:28:45,020 --> 00:28:48,060
它會在那裡。

562
00:28:48,060 --> 00:28:50,280
>> 所以我想如何做
這種差異，如果我們想要

563
00:28:50,280 --> 00:28:52,300
插入到中間或結束？

564
00:28:52,300 --> 00:28:57,892
有沒有人有什麼想法
偽代碼作為邏輯參照

565
00:28:57,892 --> 00:29:00,350
我們將採取如果我們想要
將其插入中間？

566
00:29:00,350 --> 00:29:03,391
因此，如果我們想在將其插入
頭，我們所要做的就是創建一個新的節點。

567
00:29:03,391 --> 00:29:06,311
我們設定的指針
新節點的任何頭部，

568
00:29:06,311 --> 00:29:08,310
然後我們設置了頭
新的節點，對不對？

569
00:29:08,310 --> 00:29:11,560
如果我們想將其插入到中間
名單，你會我們有什麼關係？

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> 聽眾：它仍然
是類似的過程

572
00:29:16,110 --> 00:29:19,114
像分配指針
然後，指派該指針，

573
00:29:19,114 --> 00:29:20,530
但我們必須找到那裡。

574
00:29:20,530 --> 00:29:23,560
>> ANDI鵬：沒錯，所以完全
但你同樣的過程

575
00:29:23,560 --> 00:29:27,820
必須找到在什麼地方你
希望該新指針進入，

576
00:29:27,820 --> 00:29:44,790
所以如果我要插入到
中間的鏈接列表中 - 確定，

577
00:29:44,790 --> 00:29:46,370
讓我們說這是我們的鍊錶。

578
00:29:46,370 --> 00:29:49,500
如果我們想，就在這裡插，
我們要創建一個新的節點。

579
00:29:49,500 --> 00:29:50,520
我們要去的malloc。

580
00:29:50,520 --> 00:29:52,220
我們要創建一個新的節點。

581
00:29:52,220 --> 00:29:55,940
我們將分配
指針在這裡這個節點。

582
00:29:55,940 --> 00:29:58,335
>> 但問題是不同
從其中頭部是

583
00:29:58,335 --> 00:30:00,490
是，我們確切地知道
其中頭。

584
00:30:00,490 --> 00:30:01,930
這是正確的，在第一次，對嗎？

585
00:30:01,930 --> 00:30:04,870
但在這裡，我們一定要保持跟踪
在那裡我們將其插入。

586
00:30:04,870 --> 00:30:07,930
如果我們插入我們
在此節點，我們有

587
00:30:07,930 --> 00:30:12,270
以確保該
一個先前到該節點

588
00:30:12,270 --> 00:30:14,172
是一個重新分配的指針。

589
00:30:14,172 --> 00:30:16,380
所以，那麼你必須種
跟踪兩件事情。

590
00:30:16,380 --> 00:30:19,420
如果你跟踪，其中這
節點當前的插入。

591
00:30:19,420 --> 00:30:23,280
您還可以跟踪在哪裡
那你看前面的節點

592
00:30:23,280 --> 00:30:24,340
也有。

593
00:30:24,340 --> 00:30:25,830
每個人都好有嗎？

594
00:30:25,830 --> 00:30:26,500
確定。

595
00:30:26,500 --> 00:30:28,000
>> 如何插入結束了嗎？

596
00:30:28,000 --> 00:30:34,220
如果我想將其添加這裡 - 如果我想
到一個新的節點添加到列表的末尾，

597
00:30:34,220 --> 00:30:37,009
怎麼可能我去這樣做？

598
00:30:37,009 --> 00:30:39,300
聽眾：那麼目前，
最後一個人指著空。

599
00:30:39,300 --> 00:30:40,960
ANDI彭：是的。

600
00:30:40,960 --> 00:30:43,560
沒錯，所以這一塊
目前指向知道，

601
00:30:43,560 --> 00:30:46,720
所以我想，在這個意義上，它是
很容易添加到列表的末尾。

602
00:30:46,720 --> 00:30:51,810
所有你需要做的是設置
等於空，然後繁榮。

603
00:30:51,810 --> 00:30:53,070
就在那裡，很容易。

604
00:30:53,070 --> 00:30:53,960
很簡單。

605
00:30:53,960 --> 00:30:56,430
>> 非常相似的
頭，但在邏輯上你

606
00:30:56,430 --> 00:30:59,690
想確保該步驟
你邁出做任何的這個，

607
00:30:59,690 --> 00:31:01,500
您關注的沿。

608
00:31:01,500 --> 00:31:04,420
這是很容易的，在中間
你的代碼，陷入上，

609
00:31:04,420 --> 00:31:05,671
哦，我有這麼多的三分球。

610
00:31:05,671 --> 00:31:07,461
我不知道在哪裡
任何指向。

611
00:31:07,461 --> 00:31:09,170
我甚至不知道我在哪個節點。

612
00:31:09,170 --> 00:31:11,490
這是怎麼回事？

613
00:31:11,490 --> 00:31:13,620
>> 放鬆，平靜下來，深呼吸。

614
00:31:13,620 --> 00:31:15,530
繪製出你的鏈接列表。

615
00:31:15,530 --> 00:31:18,800
如果你說，我知道在什麼地方
我需要插入到這

616
00:31:18,800 --> 00:31:22,970
我知道如何重新分配我
指針，多，更容易圖片

617
00:31:22,970 --> 00:31:27,200
out--多，更容易不
迷失在你的代碼的漏洞。

618
00:31:27,200 --> 00:31:29,410
每個人都與該行嗎？

619
00:31:29,410 --> 00:31:31,380
確定。

620
00:31:31,380 --> 00:31:35,120
>> 所以我想一個概念，我們還沒有
真之前談到現在，

621
00:31:35,120 --> 00:31:38,131
我猜你可能
不會遇到太大yet--

622
00:31:38,131 --> 00:31:40,880
它是一種先進的concept--
是，我們其實有一個數據

623
00:31:40,880 --> 00:31:43,900
結構，稱為一個雙向鍊錶。

624
00:31:43,900 --> 00:31:46,390
所以當你們看到的，
所有我們正在做的是創造

625
00:31:46,390 --> 00:31:50,400
一個實際值，額外
指針在我們每個節點

626
00:31:50,400 --> 00:31:52,660
也指向前一個節點。

627
00:31:52,660 --> 00:31:58,170
因此，我們不僅有我們的
節點指向下一個。

628
00:31:58,170 --> 00:32:01,430
他們還指出，前一個。

629
00:32:01,430 --> 00:32:04,310
我將忽略這兩個現在。

630
00:32:04,310 --> 00:32:06,740
>> 所以，那麼你有一個鏈
可以移動兩種方式，

631
00:32:06,740 --> 00:32:09,630
然後它是一個更容易一些
從邏輯上跟隨。

632
00:32:09,630 --> 00:32:11,896
喜歡這裡，而不是
飼養的，哦軌道，我

633
00:32:11,896 --> 00:32:14,520
要知道，這個節點是
一個，我不得不重新分配，

634
00:32:14,520 --> 00:32:17,532
我可以去這裡
只是拉前面的。

635
00:32:17,532 --> 00:32:19,490
後來我知道確切位置
也就是說，然後你

636
00:32:19,490 --> 00:32:21,130
不必遍歷
整體鍊錶。

637
00:32:21,130 --> 00:32:22,180
這是一個更容易一些。

638
00:32:22,180 --> 00:32:24,960
>> 但正因為如此，你必須加倍
指針的量，

639
00:32:24,960 --> 00:32:26,960
這是內存的兩倍。

640
00:32:26,960 --> 00:32:28,950
這是一個很大的指針跟踪。

641
00:32:28,950 --> 00:32:32,140
這是一個有點複雜，但它的
多一點人性視

642
00:32:32,140 --> 00:32:34,080
你試圖完成什麼。

643
00:32:34,080 --> 00:32:36,910
>> 所以這種類型的數據
結構完全存在，

644
00:32:36,910 --> 00:32:40,280
和結構是非常非常
簡單以外的所有你遇到的，

645
00:32:40,280 --> 00:32:43,850
而不只是一個指向下，
你也有一個指針以前。

646
00:32:43,850 --> 00:32:45,940
這就是差異。

647
00:32:45,940 --> 00:32:47,740
每個人都好有嗎？

648
00:32:47,740 --> 00:32:48,240
酷。

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> 好了，所以現在我
要真正花可能

651
00:32:53,280 --> 00:32:56,870
像15至20分鐘或散裝
在節剩下的時間中

652
00:32:56,870 --> 00:32:58,360
談論哈希表。

653
00:32:58,360 --> 00:33:02,590
有多少你們的
已經閱讀pset5規範呢？

654
00:33:02,590 --> 00:33:03,620
好了，好了。

655
00:33:03,620 --> 00:33:06,160
這比通常的50％以上。

656
00:33:06,160 --> 00:33:07,560
這是確定的。

657
00:33:07,560 --> 00:33:10,345
>> 所以當你們將會看到，
你在pset5挑戰

658
00:33:10,345 --> 00:33:16,790
將實施字典
在這裡裝載了14萬字

659
00:33:16,790 --> 00:33:20,610
我們給你和拼寫檢查
這對所有的文字。

660
00:33:20,610 --> 00:33:22,580
我們會給你隨機
文學作品的。

661
00:33:22,580 --> 00:33:23,520
我們會給你奧德賽。

662
00:33:23,520 --> 00:33:24,561
我們會給你伊利亞特。

663
00:33:24,561 --> 00:33:26,350
我們會給你王牌大賤諜。

664
00:33:26,350 --> 00:33:28,220
>> 而你的挑戰
將是拼寫檢查

665
00:33:28,220 --> 00:33:31,760
在所有的每一個字
這些字典

666
00:33:31,760 --> 00:33:34,960
本質上與我們的拼寫檢查器。

667
00:33:34,960 --> 00:33:38,620
所以有幾部分組成
創建這個PSET的，

668
00:33:38,620 --> 00:33:41,970
首先你想成為
能夠實際加載

669
00:33:41,970 --> 00:33:43,970
所有的話到您的
字典，然後你

670
00:33:43,970 --> 00:33:45,530
希望能夠
拼寫檢查所有的人。

671
00:33:45,530 --> 00:33:48,780
所以，正因為如此，你將需要
一個數據結構可以做到這一點快

672
00:33:48,780 --> 00:33:50,790
並有效地和動態。

673
00:33:50,790 --> 00:33:52,900
>> 所以我想最簡單的
辦法做到這一點，你

674
00:33:52,900 --> 00:33:55,010
可能會創建一個數組，對不對？

675
00:33:55,010 --> 00:33:58,910
存儲的最簡單的方法就是你
可以創造14萬字的數組

676
00:33:58,910 --> 00:34:03,400
而只是把它們都在那裡和
然後通過二進制搜索遍歷他們

677
00:34:03,400 --> 00:34:06,780
或者通過選擇或不是 - 
遺憾的是真實的排序。

678
00:34:06,780 --> 00:34:10,729
你可以對它們進行排序，然後遍歷它們
由二進制搜索或者只是線性搜索

679
00:34:10,729 --> 00:34:13,730
和公正的最後的話，但
需要大量的內存，

680
00:34:13,730 --> 00:34:15,190
這不是很有效。

681
00:34:15,190 --> 00:34:18,350
>> 因此，我們要開始
說起製作方法

682
00:34:18,350 --> 00:34:20,110
我們的運行時間更有效。

683
00:34:20,110 --> 00:34:23,190
而我們的目標是獲得
定時間，其中

684
00:34:23,190 --> 00:34:25,810
這幾乎就像陣列，其中
你有即時訪問。

685
00:34:25,810 --> 00:34:28,560
如果我想搜索什麼，
我希望能夠公正，

686
00:34:28,560 --> 00:34:30,810
熱潮，發現它完全，並將其拉出。

687
00:34:30,810 --> 00:34:34,100
等的結構，其中
我們將變得非常接近

688
00:34:34,100 --> 00:34:37,569
到能夠訪問恆定
當時，這聖杯

689
00:34:37,569 --> 00:34:41,370
在恆編程
時間被稱為哈希表。

690
00:34:41,370 --> 00:34:45,370
於是大衛前面提到的
[聽不清]在演講一點點，

691
00:34:45,370 --> 00:34:49,100
但我們要真正
下潛深，本週

692
00:34:49,100 --> 00:34:51,780
對多數民眾贊成有關一片
如何哈希表的工作原理。

693
00:34:51,780 --> 00:34:53,949
>> 這樣的方式，一個散列
表作品，例如，

694
00:34:53,949 --> 00:35:00,230
如果我想存儲一堆話，一
一堆英文單詞的，

695
00:35:00,230 --> 00:35:02,940
我可以在理論上把
香蕉，蘋果，獼猴桃，芒果，對，

696
00:35:02,940 --> 00:35:04,980
和哈密瓜所有的只是一個數組。

697
00:35:04,980 --> 00:35:07,044
他們都可以融入其中，並且被找到。

698
00:35:07,044 --> 00:35:09,210
這將會是一種痛苦來
通過搜索和訪問，

699
00:35:09,210 --> 00:35:12,920
但這樣做的更簡單的方法是
我們實際上可以建立一個結構

700
00:35:12,920 --> 00:35:15,680
所謂的哈希表，其中我們的哈希值。

701
00:35:15,680 --> 00:35:19,880
我們通過運行所有的鑰匙
散列函數，一個方程，

702
00:35:19,880 --> 00:35:22,600
這將它們全部納入
某種形式的值

703
00:35:22,600 --> 00:35:28,740
那我們就可以存儲到
鍊錶基本上陣列。

704
00:35:28,740 --> 00:35:32,570
>> 所以在這裡，如果我們想
存儲英文單詞，

705
00:35:32,570 --> 00:35:37,250
我們可能潛在只是，我不知道
知道了，把所有的第一個字母

706
00:35:37,250 --> 00:35:39,630
成某種形式的數目。

707
00:35:39,630 --> 00:35:43,140
因此，例如，如果我想
一個是同義詞apple--

708
00:35:43,140 --> 00:35:47,460
或為0的索引，和
乙的同義詞1，

709
00:35:47,460 --> 00:35:51,030
我們可以有26項
可以只是存儲

710
00:35:51,030 --> 00:35:53,610
所有的字母
字母表，我們將開始。

711
00:35:53,610 --> 00:35:56,130
然後我們就可以有
蘋果0的指數。

712
00:35:56,130 --> 00:35:59,160
我們的指數有香蕉
1，哈密瓜2的指數，

713
00:35:59,160 --> 00:36:00,540
等，等等。

714
00:36:00,540 --> 00:36:04,460
就這樣，如果我想搜索
我的哈希表和訪問蘋果，

715
00:36:04,460 --> 00:36:07,560
我知道蘋果開始
一個A，我確切地知道

716
00:36:07,560 --> 00:36:10,860
它必須是和散列
表索引0，因為

717
00:36:10,860 --> 00:36:13,620
函數的先前分配。

718
00:36:13,620 --> 00:36:16,572
>> 所以，我不知道，我們是
用戶程序在哪裡

719
00:36:16,572 --> 00:36:18,780
你將被控
arbitrarily--不要隨意，

720
00:36:18,780 --> 00:36:22,530
與試圖若有所思
想好方程

721
00:36:22,530 --> 00:36:25,460
要能傳播
你所有的價值觀

722
00:36:25,460 --> 00:36:29,370
在某種程度上，他們可以輕鬆地訪問
後來在與像一個公式

723
00:36:29,370 --> 00:36:31,130
你，你自己，知道了。

724
00:36:31,130 --> 00:36:35,210
所以，在這個意義上，如果我想去
芒果，我知道，哦，它以M開頭。

725
00:36:35,210 --> 00:36:37,134
它必須是12的索引處。

726
00:36:37,134 --> 00:36:38,800
我沒有通過任何搜索。

727
00:36:38,800 --> 00:36:42,080
我知道exactly--我可以只去
12和指數拉出了這一點。

728
00:36:42,080 --> 00:36:45,520
>> 每個人都清楚如何
哈希表的功能的工作？

729
00:36:45,520 --> 00:36:48,380
這是一種只是一個更複雜的陣列。

730
00:36:48,380 --> 00:36:50,010
這就是它。

731
00:36:50,010 --> 00:36:51,630
確定。

732
00:36:51,630 --> 00:36:57,690
>> 所以我想，我們碰到
這個問題是什麼

733
00:36:57,690 --> 00:37:06,390
發生，如果您有多個事
這給你同樣的指數？

734
00:37:06,390 --> 00:37:10,570
所以說我們的功能，所有這
做的是採取的第一個字母

735
00:37:10,570 --> 00:37:14,490
並把它轉換成一個
相應的0至25指數。

736
00:37:14,490 --> 00:37:17,137
這是完全正常，如果
你只有每個之一。

737
00:37:17,137 --> 00:37:18,970
但第二啟動
有更多的，你

738
00:37:18,970 --> 00:37:20,910
將有什麼所謂的衝突。

739
00:37:20,910 --> 00:37:25,580
>> 所以，如果我嘗試插入埋到一個哈希
表中已經有香蕉就可以了，

740
00:37:25,580 --> 00:37:27,870
有什麼事情發生時，
您嘗試插​​入呢？

741
00:37:27,870 --> 00:37:30,930
壞事情，因為香蕉
在索引中已存在

742
00:37:30,930 --> 00:37:33,800
您希望將其存儲研究。

743
00:37:33,800 --> 00:37:35,560
種漿果是喜歡啊，我該怎麼辦？

744
00:37:35,560 --> 00:37:37,080
我不知道哪裡去了。

745
00:37:37,080 --> 00:37:38,410
我該如何解決呢？

746
00:37:38,410 --> 00:37:41,150
>> 等會有種你們
看到我們做這個棘手的事情

747
00:37:41,150 --> 00:37:44,810
在這裡，我們實際上可以種
創建鏈接的列表中我們的陣列。

748
00:37:44,810 --> 00:37:46,840
這樣一來，最簡單的方法
思考這個問題，

749
00:37:46,840 --> 00:37:50,830
所有的哈希表是一個
數組鍊錶。

750
00:37:50,830 --> 00:37:55,670
因此，在這個意義上說，必須
這個美麗的指針數組，

751
00:37:55,670 --> 00:37:58,740
然後在每個指針
該值，在該索引，

752
00:37:58,740 --> 00:38:00,740
可實際卻指向其他的東西。

753
00:38:00,740 --> 00:38:05,720
所以你把所有這些不同的
鏈條脫落一個大陣。

754
00:38:05,720 --> 00:38:07,960
>> 所以在這裡，如果我
要插入漿果，

755
00:38:07,960 --> 00:38:11,220
我知道，行，我要輸入
它通過我的哈希函數。

756
00:38:11,220 --> 00:38:15,070
我將結束與指數
1，然後我將能夠有

757
00:38:15,070 --> 00:38:20,410
此只是一小的子集
巨大的14萬字的字典。

758
00:38:20,410 --> 00:38:24,220
然後，我來找找看
通過該1/26。

759
00:38:24,220 --> 00:38:27,910
>> 而這樣的話我可以插入
之前或之後香蕉漿果

760
00:38:27,910 --> 00:38:28,820
在這種情況下？

761
00:38:28,820 --> 00:38:29,700
之後，對不對？

762
00:38:29,700 --> 00:38:33,920
所以，你會想
香蕉之後插入這個節點，

763
00:38:33,920 --> 00:38:36,667
所以你要插入
在該鏈接列表的尾部。

764
00:38:36,667 --> 00:38:38,500
我要回去
這一張幻燈片，

765
00:38:38,500 --> 00:38:40,680
所以你們可以看到
哈希函數的工作。

766
00:38:40,680 --> 00:38:43,980
>> 所以散列函數是這樣的方程
你正在運行的一種輸入

767
00:38:43,980 --> 00:38:46,940
通過獲得任何指數
你希望它朝著分配。

768
00:38:46,940 --> 00:38:51,130
因此，在這個例子中，所有我們想要
做的是採取的第一個字母，

769
00:38:51,130 --> 00:38:55,890
把它轉換成一個指數，那麼我們
可以存儲我們的散列函數在。

770
00:38:55,890 --> 00:39:00,160
所有我們在這裡所做的是我們
轉換的第一個字母。

771
00:39:00,160 --> 00:39:04,770
所以keykey [0]只是第​​一個字母
我們遇到的任何字符串，

772
00:39:04,770 --> 00:39:05,720
我們通過研究。

773
00:39:05,720 --> 00:39:09,740
我們要轉換，要上，和
我們用大寫字母A減去，

774
00:39:09,740 --> 00:39:11,740
因此，所有的做
給我們提供了一些

775
00:39:11,740 --> 00:39:13,670
在其中我們可以散列我們的價值觀上。

776
00:39:13,670 --> 00:39:16,550
>> 然後，我們將
返回哈希模量的大小。

777
00:39:16,550 --> 00:39:19,340
要非常，非常小心
因為，從理論上說，在這裡

778
00:39:19,340 --> 00:39:21,870
您的哈希值可以是無窮大。

779
00:39:21,870 --> 00:39:23,660
它可能只是去和和。

780
00:39:23,660 --> 00:39:26,080
這可能是一些非常，
真正大的價值，

781
00:39:26,080 --> 00:39:29,849
但因為你的哈希表
你已經創建只有26指數，

782
00:39:29,849 --> 00:39:31,890
你要確保你的
modulusing讓你

783
00:39:31,890 --> 00:39:33,848
不run--它是相同的
為您的queue--事

784
00:39:33,848 --> 00:39:36,320
這樣你就不會跑出
您的散列函數的底部。

785
00:39:36,320 --> 00:39:39,210
>> 你想換回來各地
在[聽不清]時相同的方式

786
00:39:39,210 --> 00:39:41,750
你必須像一個非常，
非常大的信，你

787
00:39:41,750 --> 00:39:43,740
不想，要
剛跑出結束。

788
00:39:43,740 --> 00:39:46,948
這裡同樣的事情，你要確保
它不流失年底通過包裝

789
00:39:46,948 --> 00:39:48,330
周圍的表的頂部。

790
00:39:48,330 --> 00:39:50,530
所以，這只是一個很
簡單的哈希函數。

791
00:39:50,530 --> 00:39:56,570
所有這一切確實是拿第一
不管我們輸入的字母是

792
00:39:56,570 --> 00:40:01,660
並把它轉換成一個索引
我們可以把我們的哈希表。

793
00:40:01,660 --> 00:40:05,450
>> 是啊，所以我之前說的，
我們解決衝突的方式

794
00:40:05,450 --> 00:40:09,330
在我們的哈希表有，
我們所說的，鏈接。

795
00:40:09,330 --> 00:40:13,860
所以，如果你試圖插入多
字開頭同樣的事情，

796
00:40:13,860 --> 00:40:16,145
你將有一個哈希值。

797
00:40:16,145 --> 00:40:18,770
鱷梨和蘋果，如果你
通過我們的散列函數運行它，

798
00:40:18,770 --> 00:40:21,450
將會給你
數相同，為0的數目。

799
00:40:21,450 --> 00:40:24,550
這樣一來，我們的方式解決是
樣的，我們實際上可以將它們鏈接

800
00:40:24,550 --> 00:40:27,010
通過鍊錶在一起。

801
00:40:27,010 --> 00:40:29,600
>> 因此在這個意義上，
你們可以看樣

802
00:40:29,600 --> 00:40:32,640
如何數據結構
我們已經預先設定

803
00:40:32,640 --> 00:40:35,870
像葡萄乾鍊錶樣
可走到連成一片。

804
00:40:35,870 --> 00:40:38,860
然後你就可以創建遠
更有效的數據結構

805
00:40:38,860 --> 00:40:43,350
可以處理更大的量
數據，動態調整不同

806
00:40:43,350 --> 00:40:44,870
您的需要。

807
00:40:44,870 --> 00:40:45,620
大家都清楚了嗎？

808
00:40:45,620 --> 00:40:47,580
大家一種明確
在這裡會發生什麼？

809
00:40:47,580 --> 00:40:52,110
>> 如果我想insert--什麼是
水果有，我不知道開始，

810
00:40:52,110 --> 00:40:54,726
B，比其他漿果，香蕉。

811
00:40:54,726 --> 00:40:55,710
>> 聽眾：黑莓。

812
00:40:55,710 --> 00:40:57,910
>> ANDI彭：黑莓，黑莓。

813
00:40:57,910 --> 00:41:00,530
哪裡黑莓跑到這裡？

814
00:41:00,530 --> 00:41:04,251
好了，我們實際上已經沒有排序
這還沒有，但理論上

815
00:41:04,251 --> 00:41:06,250
如果我們想有這樣的
按字母順序排列，

816
00:41:06,250 --> 00:41:07,944
應該在哪裡黑莓何去何從？

817
00:41:07,944 --> 00:41:09,210
>> 聽眾：[聽不清]

818
00:41:09,210 --> 00:41:11,100
>> ANDI鵬：沒錯，在這裡後，對不對？

819
00:41:11,100 --> 00:41:14,950
但因為它是非常困難的
reorder--我想這是給你們。

820
00:41:14,950 --> 00:41:17,920
你們可以完全
實現任何你想要的。

821
00:41:17,920 --> 00:41:20,730
的更有效的方式
對這樣做也許

822
00:41:20,730 --> 00:41:24,570
將是您的排序鏈接
列出按字母順序，

823
00:41:24,570 --> 00:41:26,520
所以，當你
插入的事情，你想

824
00:41:26,520 --> 00:41:28,632
以確保將其插入
按字母順序

825
00:41:28,632 --> 00:41:30,590
讓那麼當你
試圖尋找他們，

826
00:41:30,590 --> 00:41:32,410
你不必穿越一切。

827
00:41:32,410 --> 00:41:35,290
你知道確切位置
它是，它更容易。

828
00:41:35,290 --> 00:41:39,100
>> 但是，如果你種得
東西隨意穿插，

829
00:41:39,100 --> 00:41:41,420
你仍然會有
到反正遍歷。

830
00:41:41,420 --> 00:41:44,990
所以，如果我想只
黑莓在這裡插入

831
00:41:44,990 --> 00:41:47,470
我想搜索
它，我知道，哦，黑莓

832
00:41:47,470 --> 00:41:52,012
必須先從1的指數，所以我
認識瞬時只搜索1。

833
00:41:52,012 --> 00:41:53,970
然後，我可以種
遍歷鍊錶

834
00:41:53,970 --> 00:41:56,120
直到我到黑莓，
和then--是嗎？

835
00:41:56,120 --> 00:41:59,550
>> 聽眾：如果你想create--
我想這樣是一個非常簡單的哈希

836
00:41:59,550 --> 00:42:00,050
功能。

837
00:42:00,050 --> 00:42:02,835
如果我們想做的事
多層，像的，

838
00:42:02,835 --> 00:42:05,870
好了，我們要分成
像所有字母文字

839
00:42:05,870 --> 00:42:09,040
然後再次喜歡上另一組
內的字母，

840
00:42:09,040 --> 00:42:11,715
在我們把如哈希
哈希表內的表，

841
00:42:11,715 --> 00:42:13,256
或者像函數中的一個函數？

842
00:42:13,256 --> 00:42:14,880
或者是that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI彭：所以，你的散列
function--你的哈希表

844
00:42:17,510 --> 00:42:19,360
因為你希望它可以大。

845
00:42:19,360 --> 00:42:21,930
因此，在這個意義上，我認為
這是非常容易的，很

846
00:42:21,930 --> 00:42:25,320
簡單對我來說，只是排序依據
在第一個單詞的字母。

847
00:42:25,320 --> 00:42:28,690
所以有唯一的26選項。

848
00:42:28,690 --> 00:42:32,650
我只能得到26選項
0至25，因為它們只能

849
00:42:32,650 --> 00:42:36,510
開始從A到Z，但如果你想
添加，或者，更複雜

850
00:42:36,510 --> 00:42:39,260
或更快的運行時間，以你的
哈希表，你絕對

851
00:42:39,260 --> 00:42:40,760
可以做各種各樣的事情。

852
00:42:40,760 --> 00:42:43,330
你可以讓你自己
公式，讓你

853
00:42:43,330 --> 00:42:48,000
在更多的分銷您
的話，那麼當你搜索，

854
00:42:48,000 --> 00:42:49,300
這將更快。

855
00:42:49,300 --> 00:42:52,100
>> 這完全取決於你的傢伙
要如何實現這一點。

856
00:42:52,100 --> 00:42:55,140
把它看成僅僅桶。

857
00:42:55,140 --> 00:42:57,376
如果我想有
26桶，我要去

858
00:42:57,376 --> 00:42:59,420
整理東西到這些水桶。

859
00:42:59,420 --> 00:43:02,980
但我將有一大堆
的東西在每個桶，

860
00:43:02,980 --> 00:43:05,890
所以如果你想讓它
更快，更高效，

861
00:43:05,890 --> 00:43:07,190
讓我有一百桶。

862
00:43:07,190 --> 00:43:09,290
>> 但你必須找出一個
這樣的事情進行排序，使他們

863
00:43:09,290 --> 00:43:11,040
在適當的水桶他們應該研究。

864
00:43:11,040 --> 00:43:13,331
但是當你真正
想看看那個桶，

865
00:43:13,331 --> 00:43:16,410
它的速度快了很多，因為有
在每個桶少的東西。

866
00:43:16,410 --> 00:43:20,250
所以，是的，這其實
的伎倆你們在pset5

867
00:43:20,250 --> 00:43:22,360
是，你會
面臨的挑戰是只創建

868
00:43:22,360 --> 00:43:26,170
什麼是最有效的
功能，你能想到的是

869
00:43:26,170 --> 00:43:28,520
能夠存儲和查詢這些值。

870
00:43:28,520 --> 00:43:30,840
>> 完全取決於你們
然而，要做到這一點，

871
00:43:30,840 --> 00:43:32,229
但是這是一個非常好的點。

872
00:43:32,229 --> 00:43:34,520
那什麼邏輯你
要開始思考

873
00:43:34,520 --> 00:43:37,236
是，好了，我為什麼不賺更多的桶。

874
00:43:37,236 --> 00:43:39,527
然後，我要搜索
更少的東西，然後也許我

875
00:43:39,527 --> 00:43:41,640
有一個不同的哈希函數。

876
00:43:41,640 --> 00:43:45,500
>> 是啊，有很多方法可以做到這一點
PSET，有些人比別人快。

877
00:43:45,500 --> 00:43:50,630
我完全將只是看看
快速是最快你們會

878
00:43:50,630 --> 00:43:55,170
能夠得到您的功能才能生效。

879
00:43:55,170 --> 00:43:58,176
OK，每個人都好於
鏈接和哈希表？

880
00:43:58,176 --> 00:44:00,800
它實際上是一個非常簡單的
概念，如果你想想看。

881
00:44:00,800 --> 00:44:05,160
所有這是區分什麼
您的輸入是成桶，

882
00:44:05,160 --> 00:44:10,670
對它們進行排序，然後搜索
列出了還有的關​​聯。

883
00:44:10,670 --> 00:44:11,852
>> 酷。

884
00:44:11,852 --> 00:44:18,160
好了，現在我們有一個不同的排序
數據結構，這就是所謂的一棵樹。

885
00:44:18,160 --> 00:44:20,850
讓我們去談談嘗試
這是明顯不同的，

886
00:44:20,850 --> 00:44:22,330
但在同一類別。

887
00:44:22,330 --> 00:44:29,010
從本質上講，所有的一棵樹，而不是
對組織數據以線性方式

888
00:44:29,010 --> 00:44:32,560
一個哈希表does--您
知道的，它有一個頂部和一個底部

889
00:44:32,560 --> 00:44:37,900
然後你有種鏈接關閉它 - 一對
樹有你所說的根上面，

890
00:44:37,900 --> 00:44:40,220
然後它有它周圍的葉子。

891
00:44:40,220 --> 00:44:42,390
>> 所以，你在這裡
僅僅是頂節點

892
00:44:42,390 --> 00:44:45,980
指向其他節點，該點
到更多的節點，依此類推等等。

893
00:44:45,980 --> 00:44:48,130
所以你就必須拆分分支機構。

894
00:44:48,130 --> 00:44:53,255
這是組織的只是以不同的方式
數據，因為我們把它稱為一棵樹，

895
00:44:53,255 --> 00:44:56,270
你們just--這只是
模擬出看起來像一棵樹。

896
00:44:56,270 --> 00:44:57,670
這就是為什麼我們把它叫做樹。

897
00:44:57,670 --> 00:44:59,370
>> 哈希表看起來像一個表。

898
00:44:59,370 --> 00:45:01,310
樹看起來就像一棵樹。

899
00:45:01,310 --> 00:45:03,300
所有這是一個獨立的
節點組織方式

900
00:45:03,300 --> 00:45:06,020
根據你的需求是什麼。

901
00:45:06,020 --> 00:45:11,810
>> 所以，你有一個根，
那麼你有葉子。

902
00:45:11,810 --> 00:45:15,380
該辦法，我們可以特別
想想這是一個二叉樹，

903
00:45:15,380 --> 00:45:18,150
二叉樹只是一個
樹的特定類型

904
00:45:18,150 --> 00:45:22,450
其中每個節點僅分
於，在最大，其他兩個節點。

905
00:45:22,450 --> 00:45:25,434
所以，在這裡你有不同的
對稱性在你的樹

906
00:45:25,434 --> 00:45:28,600
這使得一種更加便捷地查詢
在什麼樣的價值觀，你是因為你

907
00:45:28,600 --> 00:45:30,150
始終左或右。

908
00:45:30,150 --> 00:45:33,150
從未有像從左側第三
向左或從左側的第四。

909
00:45:33,150 --> 00:45:36,358
這只是你有左，右
你可以搜索上述兩種的。

910
00:45:36,358 --> 00:45:38,980
所以這是為什麼有用嗎？

911
00:45:38,980 --> 00:45:40,980
的方式，這是
有用的是，如果你正在尋找

912
00:45:40,980 --> 00:45:42,890
通過值來搜索，對不對？

913
00:45:42,890 --> 00:45:45,640
而不是執行二進制
在一個錯誤數組搜索，

914
00:45:45,640 --> 00:45:49,260
如果你想成為能夠插入節點
並帶走節點的意願，也

915
00:45:49,260 --> 00:45:52,185
保存搜索
二進制搜索的能力。

916
00:45:52,185 --> 00:45:54,560
因此，在這種方式中，我們是那種
tricking--記得當時我們

917
00:45:54,560 --> 00:45:56,530
說鍊錶不能二進制搜索？

918
00:45:56,530 --> 00:46:01,700
樣的，我們正在創建一個數據結構
該技巧，進入工作。

919
00:46:01,700 --> 00:46:05,034
>> 所以因為鍊錶是線性的，
它們只能鏈接一前一後。

920
00:46:05,034 --> 00:46:06,950
那種我們可以有
不同類型的指針

921
00:46:06,950 --> 00:46:09,408
該點不同的節點
這可以幫助我們與搜索。

922
00:46:09,408 --> 00:46:12,590
所以在這裡，如果我想
有一個二進制搜索樹，

923
00:46:12,590 --> 00:46:14,090
我知道，我的中間，如果55。

924
00:46:14,090 --> 00:46:18,280
我只是要創建
因為我的中間，因為我的根，

925
00:46:18,280 --> 00:46:20,770
然後我將有
值剝離它。

926
00:46:20,770 --> 00:46:25,610
>> 所以在這裡，如果我要去尋找
66的價值，我可以在55開始。

927
00:46:25,610 --> 00:46:27,310
這比55 66更高？

928
00:46:27,310 --> 00:46:30,970
的確是這樣，所以我知道我每畝搜索
I N這棵樹的右指針。

929
00:46:30,970 --> 00:46:32,440
我去77。

930
00:46:32,440 --> 00:46:35,367
行，是66小於或大於77？

931
00:46:35,367 --> 00:46:37,950
它的不足，所以你知道，哦，
具有是左節點。

932
00:46:37,950 --> 00:46:41,410
>> 所以，我們在這裡種保護
所有有關數組偉大的事情，

933
00:46:41,410 --> 00:46:44,420
所以像動態調整
的對象，是

934
00:46:44,420 --> 00:46:49,530
能夠插入和刪除隨意，
而不必擔心固定

935
00:46:49,530 --> 00:46:50,370
量的空間。

936
00:46:50,370 --> 00:46:52,820
我們仍然保留所有的
那些美好的事物

937
00:46:52,820 --> 00:46:57,140
同時還能夠保存
登錄並搜索二進制搜索的時間

938
00:46:57,140 --> 00:47:00,450
我們只是以前
能夠得到一個短語。

939
00:47:00,450 --> 00:47:06,310
>> 酷派數據結構，種
複雜的實現，該節點。

940
00:47:06,310 --> 00:47:08,311
正如你所看到的，它
是節點的結構

941
00:47:08,311 --> 00:47:10,143
是，你有一個左
和一個右指針。

942
00:47:10,143 --> 00:47:11,044
這就是它。

943
00:47:11,044 --> 00:47:12,960
因此，而不是僅僅
具有一個X或先前。

944
00:47:12,960 --> 00:47:15,920
你有一個左或右，然後
有種你可以將它們鏈接在一起

945
00:47:15,920 --> 00:47:16,836
然而，你選擇。

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK，我們實際上會
只需要幾分鐘的時間。

948
00:47:24,270 --> 00:47:25,790
所以我們要回去這裡。

949
00:47:25,790 --> 00:47:28,270
正如我以前說過，
我種解釋

950
00:47:28,270 --> 00:47:31,520
後面我們如何邏輯
通過這樣做搜索。

951
00:47:31,520 --> 00:47:33,860
我們要嘗試
pseudocoding了這一點，看看

952
00:47:33,860 --> 00:47:38,000
樣的，如果我們可以應用
二進制搜索的同樣的邏輯

953
00:47:38,000 --> 00:47:40,055
到不同類型的數據結構。

954
00:47:40,055 --> 00:47:45,049
如果你們想採取像情侶
分鐘，只是想想這一點。

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
確定。

957
00:48:46,925 --> 00:48:51,407
好吧，我要去
其實只是給你the--沒有，

958
00:48:51,407 --> 00:48:52,990
我們將談論的偽代碼第一位。

959
00:48:52,990 --> 00:48:56,580
因此，沒有人想
給刺傷了什麼

960
00:48:56,580 --> 00:49:02,100
你想要做的時候第一件事情
你開始搜索？

961
00:49:02,100 --> 00:49:04,460
如果我們正在尋找
66的價值，什麼是

962
00:49:04,460 --> 00:49:07,940
我們想要做的，如果第一件事
我們要的二進制搜索這棵樹？

963
00:49:07,940 --> 00:49:10,760
>> 聽眾：你想要看的權利
看看左邊，看到[聽不清]

964
00:49:10,760 --> 00:49:11,230
更大的數字。

965
00:49:11,230 --> 00:49:12,271
>> ANDI彭：是的，沒錯。

966
00:49:12,271 --> 00:49:15,350
所以，你要看看你的根。

967
00:49:15,350 --> 00:49:18,180
有很多方法可以調用
它，你的父節點的人說。

968
00:49:18,180 --> 00:49:21,317
我想說的根因
這就像樹的根。

969
00:49:21,317 --> 00:49:23,400
你要看看
你的根節點，而你

970
00:49:23,400 --> 00:49:26,940
要看到的是66更大
大於或小於55。

971
00:49:26,940 --> 00:49:30,360
而如果它是大於，很好，這是
大於，在這裡我們想看看嗎？

972
00:49:30,360 --> 00:49:32,000
我們在哪裡現在要進行搜索，對不對？

973
00:49:32,000 --> 00:49:34,340
我們要搜索
這種樹的右半邊。

974
00:49:34,340 --> 00:49:38,390
>> 因此，我們有，方便，一
指針指向右側。

975
00:49:38,390 --> 00:49:44,325
而這樣的話，我們可以設置
我們新的根是77。

976
00:49:44,325 --> 00:49:46,450
我們可以去到哪裡
指針指向。

977
00:49:46,450 --> 00:49:49,100
嗯，哦，在這裡我們開始
77，我們可以只

978
00:49:49,100 --> 00:49:51,172
遞歸一次又一次做到這一點。

979
00:49:51,172 --> 00:49:52,880
通過這種方式，你有種
的有一個功能。

980
00:49:52,880 --> 00:49:57,430
你有搜索你的一種方式
只需重複一遍又一遍又一遍，

981
00:49:57,430 --> 00:50:02,720
這取決於你想看看
直到你最終得到的值

982
00:50:02,720 --> 00:50:04,730
您正在搜索。

983
00:50:04,730 --> 00:50:05,230
有意義嗎？

984
00:50:05,230 --> 00:50:07,800
>> 我要告訴你的實際
代碼，這是一個很大的代碼。

985
00:50:07,800 --> 00:50:08,674
沒有必要驚慌。

986
00:50:08,674 --> 00:50:09,910
我們將討論通過它。

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> 當然沒有。

989
00:50:14,020 --> 00:50:15,061
這只是偽代碼。

990
00:50:15,061 --> 00:50:17,860
好了，這僅僅是偽代碼，
這是一個有點複雜，

991
00:50:17,860 --> 00:50:19,751
但它完全罰款。

992
00:50:19,751 --> 00:50:21,000
下面大家一起在這裡嗎？

993
00:50:21,000 --> 00:50:24,260
如果根是空的，回報
假的，因為這意味著

994
00:50:24,260 --> 00:50:26,850
你甚至不用任何那裡。

995
00:50:26,850 --> 00:50:31,376
>> 如果根n是價值，因此，如果
恰好是你看一，

996
00:50:31,376 --> 00:50:34,000
那麼你要返回true
因為你知道你發現了它。

997
00:50:34,000 --> 00:50:36,250
但如果該值小於
小於n的根，你

998
00:50:36,250 --> 00:50:38,332
要搜索左
子或左葉，

999
00:50:38,332 --> 00:50:39,540
無論你怎麼稱呼它。

1000
00:50:39,540 --> 00:50:41,750
並且如果該值大於根，
你要尋找合適的樹，

1001
00:50:41,750 --> 00:50:44,610
然後只需運行功能
通過搜索一次。

1002
00:50:44,610 --> 00:50:48,037
>> 如果根是空的，這是
意味著你已經走到了盡頭？

1003
00:50:48,037 --> 00:50:50,120
這意味著你沒有
更多更多的葉子進行搜索，

1004
00:50:50,120 --> 00:50:52,230
那麼你知道，哦，我
猜想這是不是在這裡

1005
00:50:52,230 --> 00:50:55,063
因為此前我已經通過看
整個事情，它是不是在這裡，

1006
00:50:55,063 --> 00:50:56,930
它只是可能不會在這裡。

1007
00:50:56,930 --> 00:50:58,350
>> 這是否有意義給大家？

1008
00:50:58,350 --> 00:51:03,230
所以，它就像二進制搜索保存
鍊錶的功能。

1009
00:51:03,230 --> 00:51:09,200
涼，所以第二類型
數據結構，你們的

1010
00:51:09,200 --> 00:51:13,180
可以嘗試實現你的PSET，
你只需要選擇一種方法。

1011
00:51:13,180 --> 00:51:19,430
但是，也許是一個替代方法
哈希表就是我們所說的一個線索。

1012
00:51:19,430 --> 00:51:24,080
>> 所有的一個線索是一個
樹的特定類型

1013
00:51:24,080 --> 00:51:28,600
有一個去其他值的值。

1014
00:51:28,600 --> 00:51:31,450
所以具有代替二進制
樹在這個意義上，只有一個

1015
00:51:31,450 --> 00:51:35,940
東西可以指向兩個，可以有
一件事情點很多很多的東西。

1016
00:51:35,940 --> 00:51:39,450
本質上，陣列
其中你店內

1017
00:51:39,450 --> 00:51:41,790
指針指向其他陣列。

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> 那麼我們如何在節點
將定義一個線索

1020
00:51:49,460 --> 00:51:52,590
就是我們希望有一個
布爾，C字，對吧？

1021
00:51:52,590 --> 00:51:54,920
所以該節點是布爾
像真的還是假的，

1022
00:51:54,920 --> 00:51:58,490
首先在頭
該數組，這句話嗎？

1023
00:51:58,490 --> 00:52:03,620
其次，你想擁有指針
到任何人，其餘都是。

1024
00:52:03,620 --> 00:52:07,470
一個有點複雜，有點抽象，但
我將解釋那是什麼一切手段。

1025
00:52:07,470 --> 00:52:13,800
>> 因此，這裡，在頂部，如果
有一個數組已經聲明，

1026
00:52:13,800 --> 00:52:17,040
在這裡你有一個布爾節點
存儲在前面的值

1027
00:52:17,040 --> 00:52:19,490
告訴你的是這句話嗎？

1028
00:52:19,490 --> 00:52:20,520
這難道不是一個字？

1029
00:52:20,520 --> 00:52:23,240
然後你有
陣列的其餘部分的

1030
00:52:23,240 --> 00:52:26,040
實際存儲所有的
什麼可能是可能。

1031
00:52:26,040 --> 00:52:28,660
因此，舉例來說，像
頂部有

1032
00:52:28,660 --> 00:52:32,140
的第一件事，說真的還是
假，是或否，這是一個詞。

1033
00:52:32,140 --> 00:52:38,130
>> 然後你有0到26
您可以存儲的字母。

1034
00:52:38,130 --> 00:52:42,790
如果我想在這裡搜索
對於蝙蝠，我去頂

1035
00:52:42,790 --> 00:52:49,200
我找B.我發現中的B我
數組，所以我知道，行，為B字？

1036
00:52:49,200 --> 00:52:53,010
B是不發一語，所以這樣
我必須繼續尋找。

1037
00:52:53,010 --> 00:52:56,410
我從B和我期待的
指針乙組分朝

1038
00:52:56,410 --> 00:53:00,900
我看到另一個信息陣列，
相同的結構，我們有過的。

1039
00:53:00,900 --> 00:53:05,240
>> 而這裡 - 哦，下
信[聽不清]是A.

1040
00:53:05,240 --> 00:53:07,210
因此，我們期待在該數組。

1041
00:53:07,210 --> 00:53:10,860
我們發現第八值，
然後我們來看看，看看，哦，

1042
00:53:10,860 --> 00:53:12,840
哎，就是一個字，是B-A字？

1043
00:53:12,840 --> 00:53:13,807
它不是一個字。

1044
00:53:13,807 --> 00:53:14,890
我們一定要繼續尋找。

1045
00:53:14,890 --> 00:53:17,850
>> 所以接下來我們來看看哪裡
的一個點的指針，

1046
00:53:17,850 --> 00:53:21,130
並且它指向的另一種方式
我們有更多的價值存儲。

1047
00:53:21,130 --> 00:53:24,150
而最終，我們得到
B-A-T，它是一個字。

1048
00:53:24,150 --> 00:53:25,970
這樣一來，下一次
你看，你會

1049
00:53:25,970 --> 00:53:30,850
有，是的，辦理入住手續，
此布爾函數是真實的。

1050
00:53:30,850 --> 00:53:35,450
所以在這個意義上，我們是一種
具有數組的樹。

1051
00:53:35,450 --> 00:53:39,890
>> 所以，你可以種向下搜索。

1052
00:53:39,890 --> 00:53:43,650
而不是散列函數，並且
通過鍊錶分配值，

1053
00:53:43,650 --> 00:53:49,190
你可以實現一個
特里，搜索downwords。

1054
00:53:49,190 --> 00:53:50,850
真的，真的複雜的東西。

1055
00:53:50,850 --> 00:53:54,060
不容易想到，因為我很喜歡
隨地吐痰，這麼多的數據結構進行

1056
00:53:54,060 --> 00:53:58,710
你，但確實有種大家
理解這個邏輯的作品？

1057
00:53:58,710 --> 00:54:01,920
>> OK，涼。

1058
00:54:01,920 --> 00:54:05,600
因此，B-A-T，然後
你要搜索。

1059
00:54:05,600 --> 00:54:07,940
你要去的下一次
看，哦，嘿嘿，這是真的，

1060
00:54:07,940 --> 00:54:09,273
因此，我知道這一定是一個字。

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> 同樣的事情了動物園。

1063
00:54:13,770 --> 00:54:17,960
因此，這裡的事情，現在，如果我們
想尋找動物園，現在，

1064
00:54:17,960 --> 00:54:20,780
目前動物園是不是
字我們的字典

1065
00:54:20,780 --> 00:54:25,300
因為，正如你們所看到的，
我們有一個布爾首位

1066
00:54:25,300 --> 00:54:28,590
返回true是在放大的末端。

1067
00:54:28,590 --> 00:54:30,430
我們有Z-O-O-M。

1068
00:54:30,430 --> 00:54:33,900
>> 所以在這裡，我們實際上並不具備
這個詞，動物園，在我們的字典

1069
00:54:33,900 --> 00:54:36,070
因為此複選框未選中。

1070
00:54:36,070 --> 00:54:39,540
因此，計算機不
知道動物園是一個字

1071
00:54:39,540 --> 00:54:42,430
因為我們已經一路
保存它，只有變焦這裡

1072
00:54:42,430 --> 00:54:44,920
實際上有一個布爾值
一個已經變成事實。

1073
00:54:44,920 --> 00:54:49,380
因此，如果我們要插入的
一句話，動物園，為我們的字典，

1074
00:54:49,380 --> 00:54:51,770
我們怎麼會去這樣做？

1075
00:54:51,770 --> 00:54:55,960
什麼是我們必須做的，以確保我們的
計算機知道的是Z-O-O是一個字

1076
00:54:55,960 --> 00:54:58,130
而不是第一個字為Z-O-O-M？

1077
00:54:58,130 --> 00:54:59,360
>> 聽眾：[聽不清]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI鵬：沒錯，我們
要確保這

1079
00:55:01,450 --> 00:55:07,890
這裡，該布爾值是
檢查過，這是真的。

1080
00:55:07,890 --> 00:55:13,297
Z-O-O，然後我們要去檢查，
因此，我們確切地知道，哎，動物園是一個單詞。

1081
00:55:13,297 --> 00:55:15,380
我要告訴
電腦，這是一個詞，以便

1082
00:55:15,380 --> 00:55:18,000
計算機檢查時，
它知道動物園是一個詞。

1083
00:55:18,000 --> 00:55:21,269
>> 因為記住所有這些數據
結構，這很容易讓我們

1084
00:55:21,269 --> 00:55:22,310
說，哦，蝙蝠的一個詞。

1085
00:55:22,310 --> 00:55:22,851
動物園的一個詞。

1086
00:55:22,851 --> 00:55:23,611
Zoom的一個詞。

1087
00:55:23,611 --> 00:55:25,860
但是當你構建它，
電腦不知道。

1088
00:55:25,860 --> 00:55:28,619
>> 所以，你必須準確地告訴它
在什麼時候，這是一個詞？

1089
00:55:28,619 --> 00:55:29,910
在什麼時候是它不是一個字？

1090
00:55:29,910 --> 00:55:31,784
而在什麼時候做我
需要搜索事情，

1091
00:55:31,784 --> 00:55:34,000
和在什麼時候，我需要去下一個？

1092
00:55:34,000 --> 00:55:37,010
每個人都清楚的是什麼？

1093
00:55:37,010 --> 00:55:39,540
酷。

1094
00:55:39,540 --> 00:55:42,530
>> 因此然後是
的問題，我們怎麼會

1095
00:55:42,530 --> 00:55:45,560
去插入的東西
這實際上不是嗎？

1096
00:55:45,560 --> 00:55:49,090
所以，我們只能說，我們要插入
這個詞，洗澡，到我們的線索。

1097
00:55:49,090 --> 00:55:53,589
正如你們可以看到像目前
所有我們現在已經是B-A-T，

1098
00:55:53,589 --> 00:55:55,630
和這個新的數據結構
曾有一品脫的

1099
00:55:55,630 --> 00:55:59,740
指著空，因為我們假設
即，哦，還有後B-A-T沒有的話，

1100
00:55:59,740 --> 00:56:02,530
為什麼我們需要保持
該T之後有東西

1101
00:56:02,530 --> 00:56:06,581
>> 但問題出現了，如果我們做的你
想有來後一個字

1102
00:56:06,581 --> 00:56:07,080
T的。

1103
00:56:07,080 --> 00:56:09,500
如果你有浴缸，你
會想要一個H的權利。

1104
00:56:09,500 --> 00:56:13,290
所以，我們要做到這一點的方法是
我們要創建一個單獨的節點。

1105
00:56:13,290 --> 00:56:16,840
我們沒有配發任何金額
內存為這個新陣，

1106
00:56:16,840 --> 00:56:20,720
而且我們要重新分配指針。

1107
00:56:20,720 --> 00:56:22,947
>> 我們將分配
H，首先，此空，

1108
00:56:22,947 --> 00:56:24,030
我們要擺脫。

1109
00:56:24,030 --> 00:56:26,590
我們將有
轟點向下。

1110
00:56:26,590 --> 00:56:30,600
如果我們看到一個H，我們希望它
去別的地方。

1111
00:56:30,600 --> 00:56:33,910
>> 在這裡，我們可以勾選肯定。

1112
00:56:33,910 --> 00:56:38,170
如果我們的T後擊中H，OH，
那麼我們知道這是一個詞。

1113
00:56:38,170 --> 00:56:41,110
布爾將會返回true。

1114
00:56:41,110 --> 00:56:42,950
每個人都清楚如何發生的？

1115
00:56:42,950 --> 00:56:45,110
確定。

1116
00:56:45,110 --> 00:56:47,214
>> 所以基本上，所有的
這些數據結構

1117
00:56:47,214 --> 00:56:50,130
我們已經討論了今天，我已經
走了過來他們真的，真的快

1118
00:56:50,130 --> 00:56:52,192
而不是在得多
細節，這就是確定。

1119
00:56:52,192 --> 00:56:53,900
一旦你開始搞亂
有了它，你會

1120
00:56:53,900 --> 00:56:55,733
保持在那裡的軌道
所有的指針，

1121
00:56:55,733 --> 00:56:58,060
什麼在事情你
數據結構，等等。

1122
00:56:58,060 --> 00:56:59,810
他們將是非常有用的，
它是由你

1123
00:56:59,810 --> 00:57:03,890
傢伙完全弄清楚如何
你想實現的東西。

1124
00:57:03,890 --> 00:57:07,650
>> 因此pset4，5--哦，那是錯誤的。

1125
00:57:07,650 --> 00:57:10,140
Pset5是拼寫錯誤。

1126
00:57:10,140 --> 00:57:13,710
正如我之前說的，你要去，一旦
再次，從我們這裡下載源代碼。

1127
00:57:13,710 --> 00:57:16,210
還有的將是三個主要的
事情你會被下載。

1128
00:57:16,210 --> 00:57:18,470
你會下載字典，
KERS和文本。

1129
00:57:18,470 --> 00:57:21,660
>> 所有這些東西都是有
無論是詞詞典

1130
00:57:21,660 --> 00:57:25,190
我們希望你檢查
或信息測試

1131
00:57:25,190 --> 00:57:26,930
我們希望你能拼寫檢查。

1132
00:57:26,930 --> 00:57:29,670
這樣一來，字典
我們給你準備

1133
00:57:29,670 --> 00:57:34,870
給你，我們要實際的話
你以某種方式存儲的方式，是

1134
00:57:34,870 --> 00:57:36,530
比的陣列更有效。

1135
00:57:36,530 --> 00:57:38,470
然後將文本是
會是什麼我們是

1136
00:57:38,470 --> 00:57:43,900
要求您進行拼寫檢查，以確保
所有的話有真實的話。

1137
00:57:43,900 --> 00:57:47,970
>> 對這樣一來，三大板塊
計劃，我們會給你

1138
00:57:47,970 --> 00:57:51,130
被稱為dictionary.c，
dictionary.h和speller.c。

1139
00:57:51,130 --> 00:57:56,500
因此所有dictionary.c確實是
你在要求執行。

1140
00:57:56,500 --> 00:57:57,880
它加載的話。

1141
00:57:57,880 --> 00:58:02,000
它拼寫檢查他們，並確保
一切都正確插入。

1142
00:58:02,000 --> 00:58:05,180
>> diction.h只是一個庫文件
聲明所有的這些功能。

1143
00:58:05,180 --> 00:58:07,650
而speller.c，我們打算給你。

1144
00:58:07,650 --> 00:58:09,290
你不需要修改任何它。

1145
00:58:09,290 --> 00:58:14,290
所有speller.c確實是拿去，
它裝載，檢查它的速度，

1146
00:58:14,290 --> 00:58:19,190
檢驗了怎麼樣的基準
很快你能夠做到的事情。

1147
00:58:19,190 --> 00:58:20,410
>> 這是一個拼寫檢查。

1148
00:58:20,410 --> 00:58:23,920
只要不惹它，但要
確保你明白它在做什麼。

1149
00:58:23,920 --> 00:58:28,090
我們用一個函數調用的getrusage的
測試你的法術性能

1150
00:58:28,090 --> 00:58:28,590
檢查器。

1151
00:58:28,590 --> 00:58:32,200
它所做的基本測試
一切都在你的字典的時間，

1152
00:58:32,200 --> 00:58:33,680
所以一定要了解它。

1153
00:58:33,680 --> 00:58:36,660
注意不要亂用，或
否則事情將無法正常運行。

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> 而大宗這一挑戰的是
你們真的修改dictionary.c。

1156
00:58:44,170 --> 00:58:48,526
我們打算給你
14萬字的字典中。

1157
00:58:48,526 --> 00:58:50,900
我們將會給你一個文本
文件中有這些話，

1158
00:58:50,900 --> 00:58:54,840
我們希望你能夠組織
成一個哈希表或字典樹

1159
00:58:54,840 --> 00:58:58,140
因為當我們問你拼
check--想像一下，如果你的法術

1160
00:58:58,140 --> 00:59:00,690
檢查像荷馬的奧德賽。

1161
00:59:00,690 --> 00:59:03,010
這就像這個巨大的，巨大的考驗。

1162
00:59:03,010 --> 00:59:05,190
>> 如果每一個想像
一句話，你不得不看

1163
00:59:05,190 --> 00:59:08,100
通過140,000值的數組。

1164
00:59:08,100 --> 00:59:10,350
這將採取永遠
為您的機器上運行。

1165
00:59:10,350 --> 00:59:14,490
這就是為什麼我們要組織我們
數據轉換成更有效的數據結構

1166
00:59:14,490 --> 00:59:17,270
如哈希表或字典樹。

1167
00:59:17,270 --> 00:59:20,700
然後你們可以種
當您搜索的訪問

1168
00:59:20,700 --> 00:59:22,570
事情更容易，更快速。

1169
00:59:22,570 --> 00:59:24,934
>> 所以要小心，以解決衝突。

1170
00:59:24,934 --> 00:59:27,350
你會得到一堆
開頭A的話

1171
00:59:27,350 --> 00:59:29,957
你會得到一堆話
開頭B.由你

1172
00:59:29,957 --> 00:59:31,290
男人要如何解決它。

1173
00:59:31,290 --> 00:59:34,144
或許還有更多
高效的散列函數

1174
00:59:34,144 --> 00:59:36,810
比僅僅是第一信
一些東西，所以這是給你

1175
00:59:36,810 --> 00:59:38,190
樣的人做任何你想要的。

1176
00:59:38,190 --> 00:59:40,148
>> 也許你想添加
所有的來信。

1177
00:59:40,148 --> 00:59:43,410
也許你想喜歡做奇怪的事情
到賬戶的字母數，

1178
00:59:43,410 --> 00:59:43,970
等等。

1179
00:59:43,970 --> 00:59:45,386
截至你們要如何做。

1180
00:59:45,386 --> 00:59:49,262
如果你想要做一個哈希表，如果你
想嘗試一個線索，完全取決於你。

1181
00:59:49,262 --> 00:59:52,470
我會提前發出警告的時間的你
線索通常是有點困難

1182
00:59:52,470 --> 00:59:54,520
只是因為有很多
更多的指針來跟踪。

1183
00:59:54,520 --> 00:59:55,645
但是，完全取決於你們。

1184
00:59:55,645 --> 00:59:58,742
這是更有效
在大多數情況下。

1185
00:59:58,742 --> 01:00:01,450
你要真正能夠保持
跟踪你所有的指針的。

1186
01:00:01,450 --> 01:00:03,850
像做同樣的事情
我在這裡做什麼。

1187
01:00:03,850 --> 01:00:06,871
當你試圖插入
值到一個哈希表或刪除，

1188
01:00:06,871 --> 01:00:08,620
請確保你
真的跟踪

1189
01:00:08,620 --> 01:00:11,860
對這裡的一切是因為
這是因為，如果我真的很容易

1190
01:00:11,860 --> 01:00:14,727
試圖插入之類的詞，安迪。

1191
01:00:14,727 --> 01:00:16,810
遠的不說，這是一個
真正的字，詞，劉德華，

1192
01:00:16,810 --> 01:00:19,640
成的話一個巨大的列表。

1193
01:00:19,640 --> 01:00:22,450
>> 如果我只是碰巧重新分配
指針錯誤，哎呀，

1194
01:00:22,450 --> 01:00:24,940
有去的全部
我的鏈接列表的其餘部分。

1195
01:00:24,940 --> 01:00:26,897
現在唯一的一句話讓我
已經是安迪，現在

1196
01:00:26,897 --> 01:00:29,230
所有的在該換言之
詞典已經丟失。

1197
01:00:29,230 --> 01:00:31,370
所以你要確保你
跟踪所有的指針的

1198
01:00:31,370 --> 01:00:33,661
否則，你會得到
巨大的問題，在你的代碼。

1199
01:00:33,661 --> 01:00:35,840
畫的東西出來仔細一步一步來。

1200
01:00:35,840 --> 01:00:37,870
這使得它更容易想到的。

1201
01:00:37,870 --> 01:00:40,910
>> 最後，要能
測試你的程序的性能

1202
01:00:40,910 --> 01:00:41,618
在大板。

1203
01:00:41,618 --> 01:00:43,710
如果你們拿
看CS50現在，

1204
01:00:43,710 --> 01:00:45,210
我們有什麼所謂的大板。

1205
01:00:45,210 --> 01:00:50,200
它是最快的評分表
在所有的CS50的拼寫檢查倍

1206
01:00:50,200 --> 01:00:55,720
現在，我覺得像10上方
有時，我覺得其中八是工作人員。

1207
01:00:55,720 --> 01:00:57,960
我們真的希望你們擊敗我們。

1208
01:00:57,960 --> 01:01:00,870
>> 我們所有的人都試圖實現
最快的代碼成為可能。

1209
01:01:00,870 --> 01:01:04,880
我們希望你們來嘗試挑戰
我們並實現比我們快

1210
01:01:04,880 --> 01:01:05,550
可以。

1211
01:01:05,550 --> 01:01:07,970
所以這是真的
第一次，我們是

1212
01:01:07,970 --> 01:01:12,680
要求你們做一個PSET的
你真的可以為所欲為方法

1213
01:01:12,680 --> 01:01:13,760
你想要的。

1214
01:01:13,760 --> 01:01:17,730
>> 我總是說，這是更接近
以現實生活中的解決方案，對嗎？

1215
01:01:17,730 --> 01:01:19,550
我說，嘿，我需要你這樣做。

1216
01:01:19,550 --> 01:01:21,380
建立一個程序，它為我。

1217
01:01:21,380 --> 01:01:22,630
做到這一點，但是你想要的。

1218
01:01:22,630 --> 01:01:24,271
我只知道，我要快。

1219
01:01:24,271 --> 01:01:25,770
這就是你的挑戰，在這個星期。

1220
01:01:25,770 --> 01:01:27,531
你這傢伙，我們要
給你一個任務。

1221
01:01:27,531 --> 01:01:29,030
我們將會給你一個挑戰。

1222
01:01:29,030 --> 01:01:31,559
然後就看你們
完全只是弄清楚

1223
01:01:31,559 --> 01:01:34,100
什麼是最快捷和最
有效的方式來實現這一點。

1224
01:01:34,100 --> 01:01:34,600
是嗎？

1225
01:01:34,600 --> 01:01:37,476
>> 聽眾：我們是否允許，如果
要研究更快的方法

1226
01:01:37,476 --> 01:01:40,821
做哈希表在網上，我們可以做
這一點，引用別人的代碼？

1227
01:01:40,821 --> 01:01:42,070
ANDI彭：是的，完全罰款。

1228
01:01:42,070 --> 01:01:44,320
所以，如果你們看
規範，有一條線

1229
01:01:44,320 --> 01:01:48,310
在規範中，說你們
完全自由地研究哈希

1230
01:01:48,310 --> 01:01:51,070
上有哪些功能
的更快的散列函數

1231
01:01:51,070 --> 01:01:54,720
通過為運行的東西
只要你引用的代碼。

1232
01:01:54,720 --> 01:01:57,220
因此，一些人已經
想通了快速的方法

1233
01:01:57,220 --> 01:02:00,250
中做快速拼寫檢查器，
方式存儲的信息。

1234
01:02:00,250 --> 01:02:02,750
完全取決於你的傢伙，如果你
想只取了吧？

1235
01:02:02,750 --> 01:02:04,045
請確保您引用。

1236
01:02:04,045 --> 01:02:06,170
這裡的挑戰真的
我們正在試圖測試

1237
01:02:06,170 --> 01:02:09,750
是確保你知道
你倒過來指針。

1238
01:02:09,750 --> 01:02:12,700
至於你實現
實際的散列函數

1239
01:02:12,700 --> 01:02:15,070
而未來與像
數學要做到這一點，

1240
01:02:15,070 --> 01:02:17,570
你們可以研究什麼
方法在線你們想要的。

1241
01:02:17,570 --> 01:02:17,996
是嗎？

1242
01:02:17,996 --> 01:02:19,700
>> 聽眾：我們能不能只舉
使用[聽不清]？

1243
01:02:19,700 --> 01:02:20,120
>> ANDI彭：是的。

1244
01:02:20,120 --> 01:02:22,328
你可以在你的評論，
你可以舉出像，哦，

1245
01:02:22,328 --> 01:02:26,127
從亞達採取亞達，
亞達，哈希函數。

1246
01:02:26,127 --> 01:02:27,210
任何人有任何問題嗎？

1247
01:02:27,210 --> 01:02:29,694
實際上，我們輕輕鬆鬆
通過板塊今日。

1248
01:02:29,694 --> 01:02:31,610
我將在這裡為
回答問題也是如此。

1249
01:02:31,610 --> 01:02:36,570
>> 此外，正如我所說，辦公室
今晚和明天小時。

1250
01:02:36,570 --> 01:02:40,307
該規範在本週其實是
超級簡單和超短期閱讀。

1251
01:02:40,307 --> 01:02:43,140
我建議考慮看看，剛
閱讀它的全部內容。

1252
01:02:43,140 --> 01:02:45,730
>> 而Zamyla實際上引導您
通過每個功能

1253
01:02:45,730 --> 01:02:49,796
你需要實現，所以它的
非常，非常清楚如何做的一切。

1254
01:02:49,796 --> 01:02:51,920
只是為了確保你
跟踪指針。

1255
01:02:51,920 --> 01:02:53,650
這是一個非常具有挑戰性的pset。

1256
01:02:53,650 --> 01:02:56,744
>> 這不是挑戰，因為喜歡，
哦，其概念是這麼多

1257
01:02:56,744 --> 01:02:59,160
困難，或者你要學會
這麼多新的語法方式

1258
01:02:59,160 --> 01:03:00,650
你做的最後PSET。

1259
01:03:00,650 --> 01:03:03,320
這PSET是困難的，因為
有這麼多的三分球，

1260
01:03:03,320 --> 01:03:06,980
然後這是非常，非常容易，一旦
你在你的代碼中的錯誤不能

1261
01:03:06,980 --> 01:03:08,315
找到該錯誤是。

1262
01:03:08,315 --> 01:03:13,200
>> 而如此完整和你絕對信心
傢伙能夠擊敗我們的[聽不清]

1263
01:03:13,200 --> 01:03:13,700
拼寫。

1264
01:03:13,700 --> 01:03:16,640
其實，我沒有任何書面礦
然而，但我要寫我的。

1265
01:03:16,640 --> 01:03:19,070
你寫的，而因此
你，我會寫我的。

1266
01:03:19,070 --> 01:03:21,070
我會盡量讓
我的比你快。

1267
01:03:21,070 --> 01:03:23,940
我們將看到誰擁有最快的國家之一。

1268
01:03:23,940 --> 01:03:27,340
>> ，是的，我會看到所有的
你們在這裡在星期二。

1269
01:03:27,340 --> 01:03:29,510
我將運行就像一個PSET車間一種。

1270
01:03:29,510 --> 01:03:32,640
所有部分的這
本週是PSET車間，

1271
01:03:32,640 --> 01:03:36,690
所以你們有很多機會
求助，辦公時間一如既往，

1272
01:03:36,690 --> 01:03:41,330
我真的很期待
看完所有的人“的代碼。

1273
01:03:41,330 --> 01:03:44,160
我測驗在這裡，如果你
你們要來得到這些。

1274
01:03:44,160 --> 01:03:45,880
這就是全部。

1275
01:03:45,880 --> 01:03:48,180