1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [第6週]

2
00:00:02,000 --> 00:00:04,000
[戴維·J·馬蘭] [哈佛大學]

3
00:00:04,000 --> 00:00:08,000
這是CS50。[CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> 這是CS50，這是第6週開始，

5
00:00:12,000 --> 00:00:16,000
這樣一對夫婦的新工具現在可供您利用，

6
00:00:16,000 --> 00:00:19,000
其中第一個被稱為CS50風格。

7
00:00:19,000 --> 00:00:22,000
奇怪的是，如果你是像我這樣的教學研究員，

8
00:00:22,000 --> 00:00:26,000
你可能已經看到了一個程序，其風格看起來有點像這樣。

9
00:00:26,000 --> 00:00:30,000
也許你開始削減一些角落深夜，否則你會稍後處理，

10
00:00:30,000 --> 00:00:32,000
然後一個TF或CA在辦公時間內。

11
00:00:32,000 --> 00:00:34,000
然後，我們很難讀。

12
00:00:34,000 --> 00:00:38,000
，此代碼在語法上是正確的，它會編譯，它實際上運行。

13
00:00:38,000 --> 00:00:40,000
但它絕對不是一個風格的5。

14
00:00:40,000 --> 00:00:45,000
>> 但是現在，如果我們去到這個目錄

15
00:00:45,000 --> 00:00:48,000
並請注意，我有conditions2.c

16
00:00:48,000 --> 00:00:55,000
我運行這個新的命令，style50，在這個文件conditions2.c，輸入，

17
00:00:55,000 --> 00:00:57,000
注意，它告訴我，它已經程式化。

18
00:00:57,000 --> 00:01:00,000
Gedit的注意到，該文件已經在磁盤上更改，

19
00:01:00,000 --> 00:01:08,000
如果我點擊重新加載，你所有的問題，現在實現自動化。

20
00:01:08,000 --> 00:01:15,000
[掌聲]

21
00:01:15,000 --> 00:01:17,000
這是我們做這個週末的事情之一。

22
00:01:17,000 --> 00:01:20,000
要認識到，它是不完善的，因為有一些代碼，

23
00:01:20,000 --> 00:01:23,000
，那根本不會是完美的樣式，

24
00:01:23,000 --> 00:01:26,000
但現在意識到這是一個工具，你可以利用

25
00:01:26,000 --> 00:01:33,000
如果僅僅是為了收拾一些更errantly放在花括號等。

26
00:01:33,000 --> 00:01:36,000
>> 但更引人注目的是CS50檢查。

27
00:01:36,000 --> 00:01:39,000
CS50檢查，你其實可以執行相同的正確性測試

28
00:01:39,000 --> 00:01:42,000
對自己的代碼，教學研究員能。

29
00:01:42,000 --> 00:01:44,000
這是一個命令行實用程序，現在在家電

30
00:01:44,000 --> 00:01:46,000
只要你做按update50

31
00:01:46,000 --> 00:01:49,000
pset的4種規格，並使用它基本上是這樣的。

32
00:01:49,000 --> 00:01:51,000
運行該命令check50。

33
00:01:51,000 --> 00:01:56,000
然後，你將在一個命令行參數，或更普遍地被稱為一個開關或標誌。

34
00:01:56,000 --> 00:01:58,000
一般情況下，有連字符的事情，被稱為一個開關

35
00:01:58,000 --> 00:02:02,000
一個命令行程序，-c指定

36
00:02:02,000 --> 00:02:04,000
你要運行的檢查。

37
00:02:04,000 --> 00:02:07,000
>> 要運行的測試，你唯一標識此字符串，

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize。

39
00:02:10,000 --> 00:02:13,000
換句話說，這只是一個任意的，但唯一的字符串

40
00:02:13,000 --> 00:02:18,000
我們用來唯一識別的pset 4的正確性測試。

41
00:02:18,000 --> 00:02:21,000
然後指定一個空間分隔的列表中的文件要上傳

42
00:02:21,000 --> 00:02:24,000
CS50檢查分析。

43
00:02:24,000 --> 00:02:29,000
舉例來說，如果我進入我的解決方案為resize.c這裡

44
00:02:29,000 --> 00:02:31,000
讓我打開了一個更大的終端窗口

45
00:02:31,000 --> 00:02:42,000
和我繼續運行讓我們check50-C 2012/pset4/resize說的，

46
00:02:42,000 --> 00:02:46,000
然後我繼續前進，指定的文件名，

47
00:02:46,000 --> 00:02:49,000
resize.c，然後按Enter鍵，它會壓縮，

48
00:02:49,000 --> 00:02:53,000
它上傳時，它會檢查，我只是一大堆的測試失敗。

49
00:02:53,000 --> 00:02:59,000
在左上角的一個紅說，resize.c和B​​MP存在。

50
00:02:59,000 --> 00:03:01,000
這是測試。這是我們的問題。

51
00:03:01,000 --> 00:03:04,000
它的不開心，因為得到的答案是假的。

52
00:03:04,000 --> 00:03:08,000
白色它下面的文本說，預計bmp.h存在的，而這僅僅是我的錯。

53
00:03:08,000 --> 00:03:11,000
我忘了把它上傳，所以我需要這兩個文件上傳，

54
00:03:11,000 --> 00:03:14,000
resize.c和bmp.h.

55
00:03:14,000 --> 00:03:17,000
但現在發現所有其他測試是黃色的，因為他們還沒有遇到，

56
00:03:17,000 --> 00:03:21,000
等的笑臉是垂直的，因為他既不快樂也不悲傷，

57
00:03:21,000 --> 00:03:25,000
但我們必須糾正這個問題，在紅色之前的其他檢查運行。

58
00:03:25,000 --> 00:03:27,000
>> 讓我來解決這個問題。

59
00:03:27,000 --> 00:03:30,000
讓我放大並重新運行此，這一次bmp.h

60
00:03:30,000 --> 00:03:34,000
在命令行上，輸入，現在如果一切順利的話，

61
00:03:34,000 --> 00:03:38,000
要檢查，然後返回一個結果，屏住呼吸，

62
00:03:38,000 --> 00:03:42,000
所有的綠色，這意味著我做的真的很好的pset 4。

63
00:03:42,000 --> 00:03:44,000
你可以看到和推斷的描述性文字在這裡

64
00:03:44,000 --> 00:03:47,000
它到底是什麼，我們測試。

65
00:03:47,000 --> 00:03:49,000
我們測試了第一個不存在的文件嗎？

66
00:03:49,000 --> 00:03:51,000
然後，我們測試的不resize.c編譯嗎？

67
00:03:51,000 --> 00:03:58,000
然後，我們測試它不能調整一個1x1像素的BMP，調整大小的因素，當n為1。

68
00:03:58,000 --> 00:04:01,000
現在，如果你不知道n是什麼，你會當你潛入的pset 4，

69
00:04:01,000 --> 00:04:04,000
但是，僅僅是進行仔細的檢查，以確保你不調整大小

70
00:04:04,000 --> 00:04:08,000
圖像，如果在所有的大小調整係數為1。

71
00:04:08,000 --> 00:04:14,000
如果相反，它會調整到2x2正確的1x1像素的1x1像素的BMP

72
00:04:14,000 --> 00:04:19,000
當n是2，則同樣地，礦形成相應。

73
00:04:19,000 --> 00:04:22,000
>> 總之，這是，一，採取交叉手指

74
00:04:22,000 --> 00:04:25,000
的等式就在你提交你的pset。

75
00:04:25,000 --> 00:04:28,000
你會確切地知道你的TF很快就會知道

76
00:04:28,000 --> 00:04:30,000
當你去提交一些這些問題集，

77
00:04:30,000 --> 00:04:34,000
也是教學的動機是真的把

78
00:04:34,000 --> 00:04:37,000
這樣的機會在你面前，當你知道一個先驗

79
00:04:37,000 --> 00:04:39,000
有代碼中的錯誤，並沒有被通過的測試，

80
00:04:39,000 --> 00:04:43,000
你可以把前面的更有效的時間來解決這些問題

81
00:04:43,000 --> 00:04:45,000
而不是失分，從你的TF，得到的反饋

82
00:04:45,000 --> 00:04:48,000
，然後走了，“啊，”我應該已經猜到了。

83
00:04:48,000 --> 00:04:50,000
現在，至少有一個工具，以幫助您找到。

84
00:04:50,000 --> 00:04:52,000
這不是要指出其中的錯誤，但它會告訴你

85
00:04:52,000 --> 00:04:54,000
什麼是它的症狀。

86
00:04:54,000 --> 00:04:57,000
>> 現在，實現不一定詳盡的測試。

87
00:04:57,000 --> 00:04:59,000
只是因為你得到滿屏幕的綠色笑臉

88
00:04:59,000 --> 00:05:02,000
並不意味著你的代碼是完美的，但它確實意味著

89
00:05:02,000 --> 00:05:06,000
已通過一定的測試規範所規定的。

90
00:05:06,000 --> 00:05:08,000
有時候，我們將不會公佈檢查。

91
00:05:08,000 --> 00:05:10,000
比如，偵探小說，一個方面的pset 4，

92
00:05:10,000 --> 00:05:15,000
是一種令人失望的，如果我們給你

93
00:05:15,000 --> 00:05:18,000
的答案，因為它是什麼，而且也透露了一些方法來

94
00:05:18,000 --> 00:05:21,000
誰的人是在這紅色的噪音。

95
00:05:21,000 --> 00:05:24,000
該規範將在未來的指定pset的5起

96
00:05:24,000 --> 00:05:26,000
什麼檢查為你存在。

97
00:05:26,000 --> 00:05:28,000
你會發現底部有這個白色的URL。

98
00:05:28,000 --> 00:05:30,000
就目前而言，這僅僅是診斷輸出。

99
00:05:30,000 --> 00:05:33,000
如果您訪問該URL時，你會得到一大堆瘋狂的，神秘的消息

100
00:05:33,000 --> 00:05:36,000
，歡迎您翻閱，但它主要是為工作人員

101
00:05:36,000 --> 00:05:41,000
這樣我們就可以診斷和調試check50本身的錯誤。

102
00:05:41,000 --> 00:05:46,000
>> 沒有廢話不多說，讓我們繼續前進，到我們離開的地方。

103
00:05:46,000 --> 00:05:48,000
CS50庫我們想當然的幾個星期，

104
00:05:48,000 --> 00:05:52,000
但上週，我們開始脫皮層之一。

105
00:05:52,000 --> 00:05:55,000
我們開始擱置贊成什麼，而不是字符串嗎？

106
00:05:55,000 --> 00:05:57,000
[學生]字符。

107
00:05:57,000 --> 00:05:59,000
CHAR *，這一直是一個char *，

108
00:05:59,000 --> 00:06:03,000
但現在我們不必假裝它是一個真正的數據類型的字符串。

109
00:06:03,000 --> 00:06:06,000
相反，它一直為char *各種各樣的代名詞，

110
00:06:06,000 --> 00:06:09,000
字符串是一個字符序列，

111
00:06:09,000 --> 00:06:14,000
那麼，為什麼它的意義表示為char *的字符串？

112
00:06:14,000 --> 00:06:20,000
什麼是一個char *的背景下，這個概念的一個字符串表示？

113
00:06:20,000 --> 00:06:23,000
是的。>> [學生]：第一個字符。

114
00:06:23,000 --> 00:06:25,000
好，第一個字符，但不完全的第一個字符。

115
00:06:25,000 --> 00:06:27,000
[學生]。

116
00:06:27,000 --> 00:06:29,000
好，第一個字符的地址。

117
00:06:29,000 --> 00:06:33,000
這是需要在計算機的內存中表示字符串

118
00:06:33,000 --> 00:06:36,000
只是其第一個字節的唯一地址。

119
00:06:36,000 --> 00:06:38,000
你甚至不知道它有多長

120
00:06:38,000 --> 00:06:42,000
因為你的身影，動態嗎？

121
00:06:42,000 --> 00:06:44,000
[學生]：字符串長度。

122
00:06:44,000 --> 00:06:48,000
您可以調用字符串的長度，優秀的，但如何字符串的長度？

123
00:06:48,000 --> 00:06:50,000
它有什麼作用呢？是啊。

124
00:06:50,000 --> 00:06:52,000
[學生]：保持下去，直到你得到的空字符。

125
00:06:52,000 --> 00:06:54,000
是的，沒錯，它只是遍歷一個for循環，while循環，

126
00:06:54,000 --> 00:06:57,000
表示無論從*到結束，並結束

127
00:06:57,000 --> 00:07:01,000
\ 0，所謂的空字符，NUL，

128
00:07:01,000 --> 00:07:05,000
不要混淆為null，這是一個指針，

129
00:07:05,000 --> 00:07:07,000
會在談話中再次。

130
00:07:07,000 --> 00:07:11,000
>> 我們剝開一層調用getInt，然後在GetString的，我們接過來一看，

131
00:07:11,000 --> 00:07:14,000
和調用這些功能，還是真的，

132
00:07:14,000 --> 00:07:18,000
GetString時，使用一定的函數

133
00:07:18,000 --> 00:07:21,000
實際解析，是讀或分析用戶的輸入。

134
00:07:21,000 --> 00:07:25,000
那是什麼新功能？

135
00:07:25,000 --> 00:07:27,000
scanf或sscanf的。它實際上是在幾個不同的口味。

136
00:07:27,000 --> 00:07:31,000
的scanf，sscanf的，有fscanf。

137
00:07:31,000 --> 00:07:35,000
現在，雖然，讓我們專注於最容易說明的，

138
00:07:35,000 --> 00:07:38,000
讓我去進取，不斷開拓的家電

139
00:07:38,000 --> 00:07:41,000
這樣的文件，scanf1.c。

140
00:07:41,000 --> 00:07:43,000
這是一個超級簡單的程序，

141
00:07:43,000 --> 00:07:46,000
但是，做一些事情，我們從來沒有做過

142
00:07:46,000 --> 00:07:48,000
沒有幫助的CS50庫。

143
00:07:48,000 --> 00:07:51,000
這從用戶得到一個int。它是如何工作的呢？

144
00:07:51,000 --> 00:07:53,000
那麼，在那裡的第16行中，

145
00:07:53,000 --> 00:07:56,000
注意到，我們聲明一個int稱為x，在這一點上的故事，

146
00:07:56,000 --> 00:07:58,000
x的值是什麼？

147
00:07:58,000 --> 00:08:00,000
[聽不見的學生反應]

148
00:08:00,000 --> 00:08:02,000
大衛M.]右，誰知道，一些垃圾的價值可能在17，我們只是告訴用戶

149
00:08:02,000 --> 00:08:06,000
給我一個號碼，請步和第18步是它得到有趣的。

150
00:08:06,000 --> 00:08:11,000
scanf函數似乎借用一個想法從printf的，因為它在引號中使用這些格式代碼。

151
00:08:11,000 --> 00:08:13,000
％d是一個十進制數。

152
00:08:13,000 --> 00:08:21,000
但是，為什麼我通過在＆X是x？

153
00:08:21,000 --> 00:08:24,000
前者是正確的。是啊。

154
00:08:24,000 --> 00:08:26,000
[聽不見的學生反應]

155
00:08:26,000 --> 00:08:31,000
沒錯，如果這項計劃的目標，如的函數調用getInt本身，

156
00:08:31,000 --> 00:08:34,000
是一個int的用戶，我可以通過功能

157
00:08:34,000 --> 00:08:38,000
所有的變量，但我想，如果我不通過引用傳遞

158
00:08:38,000 --> 00:08:41,000
或地址或指針，所有的目的的代名詞，

159
00:08:41,000 --> 00:08:46,000
那麼這個函數有沒有能力改變這個變量的內容。

160
00:08:46,000 --> 00:08:49,000
這將通過在副本一樣的馬車版本的Swap

161
00:08:49,000 --> 00:08:51,000
我們已經談到了幾次。

162
00:08:51,000 --> 00:08:54,000
>> 但是，這樣＆X，我從字面上傳遞什麼？

163
00:08:54,000 --> 00:08:57,000
[學生]的地址。>> x的地址。

164
00:08:57,000 --> 00:09:01,000
這就像scanf函數調用的函數繪製地圖，並在這裡說，

165
00:09:01,000 --> 00:09:04,000
這些都是在計算機的內存塊的方向

166
00:09:04,000 --> 00:09:07,000
，你可以去存儲一些整數中。

167
00:09:07,000 --> 00:09:10,000
為了sscanf的，現在做的，

168
00:09:10,000 --> 00:09:13,000
什麼樣的運營商，什麼樣的語法是要使用

169
00:09:13,000 --> 00:09:19,000
即使我們不能看到它，因為別人寫了這個功能嗎？

170
00:09:19,000 --> 00:09:21,000
換句話說 - 那是什麼？

171
00:09:21,000 --> 00:09:23,000
[學生]：X讀。

172
00:09:23,000 --> 00:09:27,000
還有的將是一些閱讀，但只有考慮到這裡的x。

173
00:09:27,000 --> 00:09:30,000
，如果scanf函數是通過x的地址，

174
00:09:30,000 --> 00:09:35,000
語法，什麼樣的運營商是必然存在的地方

175
00:09:35,000 --> 00:09:38,000
內部，使scanf函數scanf函數的實現

176
00:09:38,000 --> 00:09:42,000
其實可以寫一個2號線到該地址嗎？

177
00:09:42,000 --> 00:09:44,000
是啊，所以*。

178
00:09:44,000 --> 00:09:47,000
回想一下，*是我們的反引用運算符，這實際上意味著去那裡。

179
00:09:47,000 --> 00:09:50,000
>> 一旦你已經交給一個地址，是這裡的情況，

180
00:09:50,000 --> 00:09:53,000
scanf的可能是，如果我們環顧四周，它的源代碼

181
00:09:53,000 --> 00:09:59,000
* x或相當於真正去到該地址，並把一定的價值。

182
00:09:59,000 --> 00:10:02,000
現在，scanf是如何從鍵盤輸入的，

183
00:10:02,000 --> 00:10:04,000
我們會揮動我們手中的今天。

184
00:10:04,000 --> 00:10:07,000
只是假設操作系統允許sscanf的談

185
00:10:07,000 --> 00:10:11,000
用戶的鍵盤，但在這一點上，現在在第19行中，

186
00:10:11,000 --> 00:10:14,000
當我們簡單地打印出x，它似乎是

187
00:10:14,000 --> 00:10:17,000
scanf函數把一個int x中。

188
00:10:17,000 --> 00:10:19,000
這正是scanf是如何工作的，記得上週

189
00:10:19,000 --> 00:10:25,000
這也正是GetString和調用getInt和其他家庭的功能

190
00:10:25,000 --> 00:10:28,000
最終的作品，儘管略有差異，如sscanf的，

191
00:10:28,000 --> 00:10:31,000
這意味著一個字符串，而不是掃描的鍵盤。

192
00:10:31,000 --> 00:10:33,000
但是，讓我們來看看在這一點差異。

193
00:10:33,000 --> 00:10:37,000
在scanf2，其實我搞砸了。

194
00:10:37,000 --> 00:10:42,000
什麼是錯的，我會隱藏的評論來解釋盡可能多的

195
00:10:42,000 --> 00:10:47,000
這個程序有什麼不妥，第2版？

196
00:10:47,000 --> 00:10:55,000
技術可能。

197
00:10:55,000 --> 00:10:57,000
它看起來不錯。

198
00:10:57,000 --> 00:11:03,000
它很好地縮進，但

199
00:11:03,000 --> 00:11:07,000
好了，怎麼樣讓我們修剪下來，以更短的問題嗎？

200
00:11:07,000 --> 00:11:17,000
第16行。第16行做精確，但技術的英語是什麼？

201
00:11:17,000 --> 00:11:20,000
開始有點尷尬。是的，邁克爾。

202
00:11:20,000 --> 00:11:25,000
[學生]：它指向一個字符串的第一個字母。

203
00:11:25,000 --> 00:11:27,000
>> 好了，很近的。讓我有一點點進行調整。

204
00:11:27,000 --> 00:11:33,000
指向一個字符串的第一個字母，你聲明一個變量叫做緩衝

205
00:11:33,000 --> 00:11:36,000
都將指向一個字符串的首地址，

206
00:11:36,000 --> 00:11:39,000
或者更確切地說，將指向更具體的一個字符。

207
00:11:39,000 --> 00:11:42,000
請注意，它實際上沒有指向任何地方，因為沒有任何賦值操作符。

208
00:11:42,000 --> 00:11:46,000
有沒有等號，所以我們正在做的是所謂的緩衝區分配變量。

209
00:11:46,000 --> 00:11:49,000
它正好是32位的，因為它是一個指針，

210
00:11:49,000 --> 00:11:52,000
和緩衝區的內容想必最終

211
00:11:52,000 --> 00:11:57,000
將包含一個字符的地址，但現在，緩衝包含什麼？

212
00:11:57,000 --> 00:11:59,000
只是一些假的，誰知道，一些垃圾的價值，

213
00:11:59,000 --> 00:12:03,000
因為我們並沒有顯式初始化，所以，我們不應該做任何假設。

214
00:12:03,000 --> 00:12:06,000
好了，現在17行，什麼17行辦呢？

215
00:12:06,000 --> 00:12:08,000
也許這將溫暖起來。

216
00:12:08,000 --> 00:12:10,000
它打印一個字符串，對不對？

217
00:12:10,000 --> 00:12:12,000
它打印出字符串請。

218
00:12:12,000 --> 00:12:15,000
>> 第18行是一種熟悉的，現在在我們剛剛看到的方差

219
00:12:15,000 --> 00:12:18,000
但具有不同的格式代碼，所以在第18行中，

220
00:12:18,000 --> 00:12:23,000
我們在這裡告訴scanf函數是一個內存塊的地址。

221
00:12:23,000 --> 00:12:27,000
我希望你能響在一個字符串中，暗示的％s的，

222
00:12:27,000 --> 00:12:32,000
但問題是，我們並沒有在這裡做了幾件事情。

223
00:12:32,000 --> 00:12:35,000
的問題之一是什麼呢？

224
00:12:35,000 --> 00:12:38,000
[學生]：它試圖取消引用一個空指針。

225
00:12:38,000 --> 00:12:41,000
好，空，否則未知的指針。

226
00:12:41,000 --> 00:12:45,000
你交給scanf函數的地址，但你剛才說剛才

227
00:12:45,000 --> 00:12:49,000
該地址是一些垃圾的價值，因為我們沒有實際分配任何東西，

228
00:12:49,000 --> 00:12:53,000
所以你告訴scanf函數有效地去把一個字符串，

229
00:12:53,000 --> 00:12:56,000
但我們不知道這裡還

230
00:12:56,000 --> 00:12:59,000
所以我們並沒有實際分配的內存的緩衝區。

231
00:12:59,000 --> 00:13:03,000
此外，你甚至也沒有告訴scanf函數嗎？

232
00:13:03,000 --> 00:13:06,000
假設這是一個內存塊，它是不是垃圾的價值，

233
00:13:06,000 --> 00:13:09,000
但你還是沒有告訴scanf的一些重要的東西。

234
00:13:09,000 --> 00:13:12,000
[學生]：它實際上是符號。

235
00:13:12,000 --> 00:13:15,000
與符號，所以在這種情況下，它沒關係。

236
00:13:15,000 --> 00:13:18,000
因為緩衝區已經被聲明為一個指針

237
00:13:18,000 --> 00:13:22,000
*的語法，我們並不需要使用符號

238
00:13:22,000 --> 00:13:25,000
，因為它是一個地址，但我想我聽到了這裡。

239
00:13:25,000 --> 00:13:27,000
[學生]：它有多大？

240
00:13:27,000 --> 00:13:29,000
好，我們沒有告訴scanf函數有多大，這個緩衝區，

241
00:13:29,000 --> 00:13:32,000
這意味著即使緩衝區的指針，

242
00:13:32,000 --> 00:13:35,000
我們說scanf函數，把一個字符串在這裡，

243
00:13:35,000 --> 00:13:38,000
但在這裡，可能是2個字節，也可能是10個字節​​，它可能是一個兆字節。

244
00:13:38,000 --> 00:13:41,000
scanf函數不知道，因為這是一個內存塊

245
00:13:41,000 --> 00:13:43,000
據推測，它不是一個字符串還。

246
00:13:43,000 --> 00:13:48,000
這只是一個字符串，一旦你寫個字符，\ 0到該內存塊。

247
00:13:48,000 --> 00:13:51,000
現在，它只是一些的內存塊。

248
00:13:51,000 --> 00:13:55,000
scanf函數不知道什麼時候停止寫入到該地址。

249
00:13:55,000 --> 00:13:59,000
>> 如果你還記得我隨意在鍵盤上鍵入一些例子，在過去的

250
00:13:59,000 --> 00:14:03,000
嘗試緩衝區溢出，正是和我們聊上週五。

251
00:14:03,000 --> 00:14:07,000
如果攻擊者以某種方式注入到你的程序中一個更大的字

252
00:14:07,000 --> 00:14:10,000
或句子或短語，那麼你，希望你可以溢出

253
00:14:10,000 --> 00:14:13,000
一個內存塊，它可以有不良後果，

254
00:14:13,000 --> 00:14:15,000
如在整個程序本身。

255
00:14:15,000 --> 00:14:17,000
我們需要以某種方式解決這個問題。

256
00:14:17,000 --> 00:14:20,000
讓我縮小，進入第3版的這個方案。

257
00:14:20,000 --> 00:14:22,000
這是一個稍微好一點。

258
00:14:22,000 --> 00:14:24,000
在這個版本中，發現其中的差別。

259
00:14:24,000 --> 00:14:27,000
在第16行，我再次聲明一個變量叫做緩衝，

260
00:14:27,000 --> 00:14:29,000
但究竟是什麼呢？

261
00:14:29,000 --> 00:14:33,000
這是一個數組的16個字符。

262
00:14:33,000 --> 00:14:36,000
這是一件好事，因為這意味著我現在可以告訴scanf函數

263
00:14:36,000 --> 00:14:39,000
這裡是一個實際的內存塊。

264
00:14:39,000 --> 00:14:42,000
現在為指針的數組，你幾乎可以認為，

265
00:14:42,000 --> 00:14:44,000
即使他們不是實際上是等效的。

266
00:14:44,000 --> 00:14:47,000
他們會在不同的上下文中有不同的表現。

267
00:14:47,000 --> 00:14:50,000
但它肯定是緩衝區被引用的情況下，

268
00:14:50,000 --> 00:14:53,000
16個連續的字符，因為這是一個數組是

269
00:14:53,000 --> 00:14:55,000
和現在已經有好幾個星期。

270
00:14:55,000 --> 00:14:59,000
>> 在這裡，我說的，scanf是這裡的一大塊的內存。

271
00:14:59,000 --> 00:15:01,000
這一次，它實際上是一個內存塊，

272
00:15:01,000 --> 00:15:07,000
但為什麼這個程序仍然可利用的呢？

273
00:15:07,000 --> 00:15:11,000
什麼仍然是錯的？

274
00:15:11,000 --> 00:15:14,000
我說給我16個字節，但是，

275
00:15:14,000 --> 00:15:16,000
[學生]：如果輸入超過16？

276
00:15:16,000 --> 00:15:20,000
沒錯，如果用戶鍵入17個字符或1700個字符是什麼？

277
00:15:20,000 --> 00:15:23,000
事實上，讓我們看看如果我們不能現在絆倒這個錯誤。

278
00:15:23,000 --> 00:15:25,000
這是更好，但並不完美。

279
00:15:25,000 --> 00:15:28,000
讓，我繼續運行編譯這個程序，使scanf3的。

280
00:15:28,000 --> 00:15:34,000
讓我跑scanf3，字符串，請：您好，我們似乎會好起來的。

281
00:15:34,000 --> 00:15:37,000
讓我嘗試稍長，你好。

282
00:15:37,000 --> 00:15:42,000
好吧，讓我們不打招呼，你今天怎麼，Enter鍵。

283
00:15:42,000 --> 00:15:54,000
在這裡獲得一種幸運，讓我們說，你好，你怎麼樣。

284
00:15:54,000 --> 00:15:56,000
該死的。

285
00:15:56,000 --> 00:16:03,000
好了，我們是幸運的。讓我們來看看，如果我們能夠解決這個問題。

286
00:16:03,000 --> 00:16:06,000
不，它不會讓我抄。

287
00:16:06,000 --> 00:16:09,000
讓我們再試一次。

288
00:16:09,000 --> 00:16:12,000
所有權利。

289
00:16:12,000 --> 00:16:20,000
我們會看到，我可以假裝多久焦點，而這樣做。

290
00:16:20,000 --> 00:16:23,000
該死的。這是相當合適的，其實。

291
00:16:23,000 --> 00:16:26,000
我們走吧。

292
00:16:26,000 --> 00:16:30,000
點而成。

293
00:16:30,000 --> 00:16:34,000
>> ，尷尬的，但它也是，它也是引起極大的混亂的來源之一

294
00:16:34,000 --> 00:16:38,000
編寫程序時有錯誤的，因為他們表現自己

295
00:16:38,000 --> 00:16:40,000
有時在一段時間內只有一次。

296
00:16:40,000 --> 00:16:43,000
現實的情況是，即使你的代碼被徹底打破，

297
00:16:43,000 --> 00:16:46,000
它可能只被徹底打破了曾經在一段時間內

298
00:16:46,000 --> 00:16:49,000
因為有時候，基本上會發生什麼是操作系統分配

299
00:16:49,000 --> 00:16:52,000
一點點更多的內存比你實際需要的不管是什麼原因，

300
00:16:52,000 --> 00:16:57,000
所以沒有其他人使用的內存塊的16個字符，

301
00:16:57,000 --> 00:17:01,000
所以，如果你去17，18，19，不論如何，這不是什麼大不了的。

302
00:17:01,000 --> 00:17:04,000
現在，計算機，即使在這一點上，不崩潰

303
00:17:04,000 --> 00:17:09,000
其他的東西，可能最終使用的字節數17或18或19，

304
00:17:09,000 --> 00:17:14,000
在這一點，你把你的數據有，但過長，

305
00:17:14,000 --> 00:17:18,000
要覆蓋潛在的一些其他功能。

306
00:17:18,000 --> 00:17:21,000
它不一定是要保持不變，

307
00:17:21,000 --> 00:17:23,000
但不一定會導致段故障。

308
00:17:23,000 --> 00:17:26,000
但是，在這種情況下，我終於提供了足夠的字符

309
00:17:26,000 --> 00:17:29,000
，我基本上是超出了我的內存段，咣當，

310
00:17:29,000 --> 00:17:33,000
操作系統的說：“對不起，這是沒有好，分割故障。”

311
00:17:33,000 --> 00:17:38,000
>> 讓我們來看看，如果現在仍然在我的目錄

312
00:17:38,000 --> 00:17:40,000
請注意，我這裡有這個文件，核心。

313
00:17:40,000 --> 00:17:42,000
請注意，這是再次呼籲一個核心轉儲。

314
00:17:42,000 --> 00:17:46,000
它本質上是一個文件，其中包含你的程序的內存中的內容

315
00:17:46,000 --> 00:17:48,000
在點，它墜毀，

316
00:17:48,000 --> 00:17:51,000
只是為了嘗試一個簡單的例子：在這裡讓我去

317
00:17:51,000 --> 00:17:57,000
和運行gdb上scanf3的，然後指定了第三個參數，稱為核心，

318
00:17:57,000 --> 00:18:01,000
並注意在這裡，如果我列出的代碼，

319
00:18:01,000 --> 00:18:06,000
像往常一樣，我們就可以用gdb開始步行通過這個節目，

320
00:18:06,000 --> 00:18:10,000
我可以運行它，並盡快為我打的步驟，在gdb的命令

321
00:18:10,000 --> 00:18:13,000
只要我打了潛在的車線後鍵入一個巨大的字符串，

322
00:18:13,000 --> 00:18:16,000
我將能夠識別在這裡。

323
00:18:16,000 --> 00:18:19,000
更多關於這一點，雖然，在部分核心轉儲

324
00:18:19,000 --> 00:18:22,000
等，讓您可以閒逛內將核心轉儲

325
00:18:22,000 --> 00:18:27,000
看到在哪一行的計劃失敗。

326
00:18:27,000 --> 00:18:32,000
然後在指針和地址的任何問題？

327
00:18:32,000 --> 00:18:36,000
因為今天開始，我們要開始考慮是理所當然的，這些東西存在

328
00:18:36,000 --> 00:18:40,000
我們知道究竟是什麼。

329
00:18:40,000 --> 00:18:42,000
是。

330
00:18:42,000 --> 00:18:46,000
>> [學生]：為什麼你沒有把符號的部分

331
00:18:46,000 --> 00:18:48,000
這個問題問得好。

332
00:18:48,000 --> 00:18:51,000
為什麼我沒有把一個符號的字符數組，因為我以前的

333
00:18:51,000 --> 00:18:53,000
我們的例子嗎？

334
00:18:53,000 --> 00:18:55,000
簡短的回答是數組是有點特別。

335
00:18:55,000 --> 00:18:59,000
你幾乎可以認為一個緩衝區實際上是一個地址，

336
00:18:59,000 --> 00:19:03,000
它只是發生的情況下，方括號表示法

337
00:19:03,000 --> 00:19:06,000
是一個方便的，這樣我們就可以進入支架，支架1，

338
00:19:06,000 --> 00:19:10,000
托架2，而無需使用*符號。

339
00:19:10,000 --> 00:19:13,000
這是一個有點善意的謊言，因為數組和指針

340
00:19:13,000 --> 00:19:17,000
，其實是有點不同，但他們往往但並不總是可以互換使用。

341
00:19:17,000 --> 00:19:21,000
總之，當一個函數需要一個指針，指向一個內存塊，

342
00:19:21,000 --> 00:19:24,000
您可以通過malloc返回的地址，

343
00:19:24,000 --> 00:19:29,000
，我們將看到的malloc再過不了多久，你可以通過它的名稱的數組。

344
00:19:29,000 --> 00:19:32,000
你不必做符號的數組，因為他們已經

345
00:19:32,000 --> 00:19:34,000
基本上和地址。

346
00:19:34,000 --> 00:19:36,000
這是一個例外。

347
00:19:36,000 --> 00:19:39,000
讓他們特別的方括號。

348
00:19:39,000 --> 00:19:41,000
>> 你可以把一個符號旁邊的緩衝區？

349
00:19:41,000 --> 00:19:43,000
不能在這種情況下。

350
00:19:43,000 --> 00:19:46,000
這是行不通的，因為這個角落的情況下，

351
00:19:46,000 --> 00:19:49,000
數組是不太實際的地址。

352
00:19:49,000 --> 00:19:54,000
但是，我們也許會回來，不久與其他的例子。

353
00:19:54,000 --> 00:19:56,000
讓我們嘗試在這裡解決的一個問題。

354
00:19:56,000 --> 00:20:00,000
我們有一個數據結構，我們已經使用了一段時間被稱為數組。

355
00:20:00,000 --> 00:20:02,000
典型的例子，這就是我們剛。

356
00:20:02,000 --> 00:20:04,000
但數組有一定的積極以及不利的缺點。

357
00:20:04,000 --> 00:20:06,000
數組是不錯的，為什麼呢？

358
00:20:06,000 --> 00:20:11,000
什麼是一件事，你喜歡你喜歡的陣列有關數組的範圍內嗎？

359
00:20:11,000 --> 00:20:13,000
方便他們什麼？引人注目的是什麼？

360
00:20:13,000 --> 00:20:18,000
為什麼我們向他們介紹擺在首位？

361
00:20:18,000 --> 00:20:20,000
是啊。

362
00:20:20,000 --> 00:20:27,000
[學生]：他們可以存儲大量的數據，你不必使用整個的事情。

363
00:20:27,000 --> 00:20:29,000
您可以使用一節。

364
00:20:29,000 --> 00:20:32,000
好，一個陣列，可以存儲大量的數據，

365
00:20:32,000 --> 00:20:35,000
你不一定必須使用它的所有，所以你可以overallocate，

366
00:20:35,000 --> 00:20:39,000
這可能是方便的，如果你事先不知道有多少的期望。

367
00:20:39,000 --> 00:20:41,000
>> GetString的是一個完美的例子。

368
00:20:41,000 --> 00:20:44,000
GetString時，我們寫的，不知道多少個字符，

369
00:20:44,000 --> 00:20:48,000
所以事實上，我們可以分配的連續內存塊還是不錯的。

370
00:20:48,000 --> 00:20:51,000
數組也解決一個問題，我們現在看到幾個星期前

371
00:20:51,000 --> 00:20:54,000
您的代碼開始下放一些非常糟糕的設計。

372
00:20:54,000 --> 00:20:57,000
回想一下，我創建了一個叫大衛的學生結構，

373
00:20:57,000 --> 00:21:00,000
然後這實際上是一種替代方法，雖然

374
00:21:00,000 --> 00:21:04,000
有一個名為name的變量與另一個變量，我認為，房子，

375
00:21:04,000 --> 00:21:08,000
和另一個變量稱為ID，因為在這個故事中，我想介紹一些其他

376
00:21:08,000 --> 00:21:11,000
像Rob到程序中，所以後來我決定等待一分鐘，

377
00:21:11,000 --> 00:21:13,000
我要重命名這些變量。

378
00:21:13,000 --> 00:21:16,000
讓我們把我的NAME1，ID1，house1。

379
00:21:16,000 --> 00:21:20,000
讓我們把搶奪的名稱2，house2，ID2。

380
00:21:20,000 --> 00:21:22,000
但是，然後等待一分鐘，湯米？

381
00:21:22,000 --> 00:21:24,000
然後，我們有三個變量。

382
00:21:24,000 --> 00:21:27,000
我們引進了別人，四組變量。

383
00:21:27,000 --> 00:21:30,000
世界開始變得混亂非常迅速，

384
00:21:30,000 --> 00:21:33,000
所以我們引入了結構，什麼是引人注目的一個結構？

385
00:21:33,000 --> 00:21:39,000
什麼是一個C結構讓你這樣做嗎？

386
00:21:39,000 --> 00:21:42,000
這是今天真的很尷尬。

387
00:21:42,000 --> 00:21:44,000
什麼？>> [聽不見的學生反應]

388
00:21:44,000 --> 00:21:47,000
是啊，特別是上，typedef可以讓你創建一個新的數據類型，

389
00:21:47,000 --> 00:21:51,000
結構，struct關鍵字，讓你封裝

390
00:21:51,000 --> 00:21:54,000
概念上相關的數據塊

391
00:21:54,000 --> 00:21:56,000
此後他們類似的學生。

392
00:21:56,000 --> 00:21:58,000
>> 這是很好的，因為現在我們可以模擬

393
00:21:58,000 --> 00:22:03,000
更排序的概念相一致的概念，一個學生在一個變量

394
00:22:03,000 --> 00:22:07,000
而不是任意具有一個為一個字符串，一個用於一個ID，等等。

395
00:22:07,000 --> 00:22:10,000
數組是不錯的，因為他們讓我們開始清理我們的代碼。

396
00:22:10,000 --> 00:22:13,000
但現在是一個缺點的數組？

397
00:22:13,000 --> 00:22:15,000
你能不能做？是啊。

398
00:22:15,000 --> 00:22:17,000
[學生]：你要知道它有多大。

399
00:22:17,000 --> 00:22:19,000
你要知道它有多大，所以它是一種痛苦。

400
00:22:19,000 --> 00:22:21,000
那些具有編程經驗知道，在很多語言中，

401
00:22:21,000 --> 00:22:24,000
如Java，你可以問一個內存塊，特別是一個數組，

402
00:22:24,000 --> 00:22:28,000
究竟有多大，其長，財產，可以這麼說，這是真的很方便。

403
00:22:28,000 --> 00:22:32,000
在C語言中，你甚至可以不調用strlen一般的數組

404
00:22:32,000 --> 00:22:35,000
由於strlen，因為這個詞所暗示的，是唯一的字符串，

405
00:22:35,000 --> 00:22:39,000
你可以計算出字符串的長度，因為這個人的慣例

406
00:22:39,000 --> 00:22:43,000
有一個\ 0，而是一個數組，更一般地，僅僅是一塊內存。

407
00:22:43,000 --> 00:22:46,000
如果它是一個整型數組，不會有一些特殊的字符

408
00:22:46,000 --> 00:22:48,000
在結束等著你。

409
00:22:48,000 --> 00:22:50,000
你要記住一個數組的長度。

410
00:22:50,000 --> 00:22:54,000
數組的另一個缺點抬頭的GetString本身。

411
00:22:54,000 --> 00:22:59,000
數組的另一個缺點什麼？

412
00:22:59,000 --> 00:23:01,000
主席先生，只有你和我。

413
00:23:01,000 --> 00:23:04,000
[聽不見的學生反應] >>這是什麼？

414
00:23:04,000 --> 00:23:06,000
它的聲明在堆棧中。

415
00:23:06,000 --> 00:23:09,000
好了，在堆棧上聲明。你為什麼不這樣呢？

416
00:23:09,000 --> 00:23:13,000
[學生]：因為它得到重用。

417
00:23:13,000 --> 00:23:15,000
它得到重用。

418
00:23:15,000 --> 00:23:18,000
好吧，如果你使用一個數組分配內存，

419
00:23:18,000 --> 00:23:21,000
例如，你不能返回它，因為它是在棧上。

420
00:23:21,000 --> 00:23:23,000
好吧，這是一個缺點。

421
00:23:23,000 --> 00:23:25,000
怎麼樣的數組？

422
00:23:25,000 --> 00:23:28,000
一旦你分配它，你種旋，如果你需要更多的空間

423
00:23:28,000 --> 00:23:30,000
比陣列。

424
00:23:30,000 --> 00:23:34,000
>> 然後，我們介紹，召回時，malloc，這給了我們動態分配內存的能力。

425
00:23:34,000 --> 00:23:37,000
但是，如果我們嘗試了完全不同的世界？

426
00:23:37,000 --> 00:23:40,000
如果我們想解決這些問題，一對夫婦的

427
00:23:40,000 --> 00:23:45,000
我們，而不是我的筆已經睡著了，在這裡，

428
00:23:45,000 --> 00:23:51,000
如果我們不是想實質上是創建了世界上不再像嗎？

429
00:23:51,000 --> 00:23:56,000
這是一個數組，當然，這種惡化，一旦我們打到最後的數組，

430
00:23:56,000 --> 00:24:00,000
我現在不再有另一個整數或其它字符的空間。

431
00:24:00,000 --> 00:24:03,000
如果我們什麼樣的先發製人說好了，為什麼我們不能放鬆

432
00:24:03,000 --> 00:24:07,000
這個要求是，所有這些內存塊是連續的背靠背，

433
00:24:07,000 --> 00:24:10,000
為什麼不，當我需要一個int或一個字符，

434
00:24:10,000 --> 00:24:12,000
只要給我空間，其中之一嗎？

435
00:24:12,000 --> 00:24:14,000
當我需要，給我另一個空間，

436
00:24:14,000 --> 00:24:16,000
當我需要，給我一個空間。

437
00:24:16,000 --> 00:24:19,000
優勢是，如果別人

438
00:24:19,000 --> 00:24:21,000
在這裡，佔用內存沒什麼大不了的。

439
00:24:21,000 --> 00:24:25,000
我會承擔這額外的內存塊，那麼這個人。

440
00:24:25,000 --> 00:24:28,000
>> 現在，唯一的缺點是，幾乎感覺就像我有

441
00:24:28,000 --> 00:24:30,000
一大堆不同的變量。

442
00:24:30,000 --> 00:24:33,000
這感覺就像是5個不同的變量潛在的。

443
00:24:33,000 --> 00:24:36,000
但是，如果我們偷的想法字符串

444
00:24:36,000 --> 00:24:41,000
據此，我們以某種方式連接這些東西放在一起從理論上講，和什麼如果我這樣做嗎？

445
00:24:41,000 --> 00:24:44,000
這是我很差繪製的箭頭。

446
00:24:44,000 --> 00:24:46,000
但是，假如這些內存塊

447
00:24:46,000 --> 00:24:52,000
指出的，這傢伙，誰沒有兄弟姐妹在他的右邊，

448
00:24:52,000 --> 00:24:54,000
有沒有這樣的箭頭。

449
00:24:54,000 --> 00:24:56,000
其實，這是什麼所謂的鏈接列表。

450
00:24:56,000 --> 00:25:00,000
這是一個新的數據結構，使我們能夠分配的內存塊，

451
00:25:00,000 --> 00:25:03,000
然後又一次，另一個，然後再在任何時候，我們要

452
00:25:03,000 --> 00:25:07,000
在一個程序，我們還記得，他們都以某種方式相關的

453
00:25:07,000 --> 00:25:11,000
從字面上鏈接在一起，我們這樣做，形象地在這裡有一個箭頭。

454
00:25:11,000 --> 00:25:15,000
但是，在代碼中，會是什麼機制，通過它，你可以以某種方式連接，

455
00:25:15,000 --> 00:25:20,000
幾乎一樣從頭開始，另一塊塊？

456
00:25:20,000 --> 00:25:22,000
我們可以用一個指針，對不對？

457
00:25:22,000 --> 00:25:25,000
因為真正的箭頭，從左上角的正方形，

458
00:25:25,000 --> 00:25:31,000
這傢伙在這裡，這其中，包含在這個廣場

459
00:25:31,000 --> 00:25:34,000
不只是一些整數，不只是一些字符，但如果我真的分配

460
00:25:34,000 --> 00:25:37,000
一點點額外的空間，所以，現在，

461
00:25:37,000 --> 00:25:41,000
我的每一個內存塊，即使這要花費我，

462
00:25:41,000 --> 00:25:45,000
其中之一的內存塊，現在看起來多了幾分矩形

463
00:25:45,000 --> 00:25:47,000
被用於一個數字，如數字1，

464
00:25:47,000 --> 00:25:50,000
如果這個傢伙，然後存儲數字2，

465
00:25:50,000 --> 00:25:52,000
這其他的內存塊，用於箭頭，

466
00:25:52,000 --> 00:25:54,000
或者更具體而言，一個指針。

467
00:25:54,000 --> 00:25:59,000
並想我存儲在這裡，我使用它來指向那個傢伙，

468
00:25:59,000 --> 00:26:02,000
現在這傢伙，讓我們假設我只需要三個這樣的內存塊。

469
00:26:02,000 --> 00:26:05,000
我會畫一條線，表明空。

470
00:26:05,000 --> 00:26:07,000
有沒有額外的字符。

471
00:26:07,000 --> 00:26:10,000
>> 事實上，這是我們如何去執行

472
00:26:10,000 --> 00:26:12,000
而這就是所謂的一個鍊錶。

473
00:26:12,000 --> 00:26:18,000
鍊錶是一種新的數據結構，它是一個敲門磚

474
00:26:18,000 --> 00:26:21,000
票友數據結構著手解決問題

475
00:26:21,000 --> 00:26:23,000
沿線Facebook的類型的問題，谷歌型的問題

476
00:26:23,000 --> 00:26:26,000
你有巨大的數據集，它不再削減

477
00:26:26,000 --> 00:26:29,000
連續存儲一切，並使用類似線性搜索

478
00:26:29,000 --> 00:26:31,000
甚至一些像二進制搜索。

479
00:26:31,000 --> 00:26:33,000
你想更好的運行時間。

480
00:26:33,000 --> 00:26:37,000
事實上，人們的聖杯，我們將討論在本週晚些時候或明年

481
00:26:37,000 --> 00:26:41,000
是一種算法，其運行時間是恆定的。

482
00:26:41,000 --> 00:26:44,000
換句話說，它總是以相同的時間量無論

483
00:26:44,000 --> 00:26:47,000
有多大的投入，這確實是引人注目的，

484
00:26:47,000 --> 00:26:49,000
甚至更多的東西比數。

485
00:26:49,000 --> 00:26:51,000
這是什麼在屏幕上呢？

486
00:26:51,000 --> 00:26:55,000
每個矩形正是我剛才畫的手。

487
00:26:55,000 --> 00:26:59,000
但事情的方式在左邊是一個特殊的變量。

488
00:26:59,000 --> 00:27:02,000
這將是一個單一的指針，因為有一個問題

489
00:27:02,000 --> 00:27:04,000
一個鍊錶，因為這些東西被稱為，

490
00:27:04,000 --> 00:27:09,000
是，你必須掛到鍊錶的一端。

491
00:27:09,000 --> 00:27:13,000
>> 就像一個字符串，你必須知道的第一個字符的地址。

492
00:27:13,000 --> 00:27:15,000
同樣的處理鍊錶。

493
00:27:15,000 --> 00:27:19,000
你必須知道的第一個內存塊的地址

494
00:27:19,000 --> 00:27:25,000
因為從那裡，你可以達到每一個。

495
00:27:25,000 --> 00:27:27,000
不利的一面。

496
00:27:27,000 --> 00:27:30,000
我們付出什麼樣的價格，這種多功能的具有動態

497
00:27:30,000 --> 00:27:34,000
相當大的數據結構，如果我們需要更多的內存，做工精細，

498
00:27:34,000 --> 00:27:37,000
只是分配一個塊，並畫一個指針

499
00:27:37,000 --> 00:27:39,000
舊到新的尾的列表嗎？

500
00:27:39,000 --> 00:27:41,000
是啊。

501
00:27:41,000 --> 00:27:43,000
[學生]：這需要約兩倍的空間。

502
00:27:43,000 --> 00:27:45,000
它需要兩倍的空間，所以這絕對是一個缺點，我們已經看到了這

503
00:27:45,000 --> 00:27:48,000
時間，空間和靈活性之間的權衡前

504
00:27:48,000 --> 00:27:51,000
現在，我們需要的不是這些數值分別為32位。

505
00:27:51,000 --> 00:27:57,000
我們真正需要的數字64，32和32，用於將指針。

506
00:27:57,000 --> 00:27:59,000
但是，嘿，我有2 GB的RAM。

507
00:27:59,000 --> 00:28:02,000
添加另外32位在這裡和這裡似乎並不認為大不了的。

508
00:28:02,000 --> 00:28:05,000
但對於大型數據集，它肯定加起來到字面上的兩倍多。

509
00:28:05,000 --> 00:28:09,000
的另一個缺點什麼，或什麼功能，我們放棄了，

510
00:28:09,000 --> 00:28:12,000
如果我們是代表一個鍊錶，而不是一個數組列表的東西，？

511
00:28:12,000 --> 00:28:14,000
[學生]：您可以向後遍歷。

512
00:28:14,000 --> 00:28:16,000
您可以向後遍歷，所以你種擰如果你走

513
00:28:16,000 --> 00:28:19,000
從左至右使用for循環或while循環

514
00:28:19,000 --> 00:28:21,000
然後你會意識到，“哦，我想回到開始的名單。”

515
00:28:21,000 --> 00:28:26,000
你不能因為這些指針只由左到右的箭頭表示。

516
00:28:26,000 --> 00:28:29,000
>> 現在，你可以記住列表的開始與另一個變量，

517
00:28:29,000 --> 00:28:31,000
但要記住，這是一個複雜的。

518
00:28:31,000 --> 00:28:35,000
一個數組，不管你走多遠，你總是可以做減，減，減，減

519
00:28:35,000 --> 00:28:37,000
回到來處。

520
00:28:37,000 --> 00:28:40,000
另一個缺點是什麼？是啊。

521
00:28:40,000 --> 00:28:43,000
[聽不見的學生問題]

522
00:28:43,000 --> 00:28:47,000
，所以你可以你實際上只是提出了一個雙向鍊錶數據結構，

523
00:28:47,000 --> 00:28:50,000
而事實上，你會增加這些矩形的另一個指針

524
00:28:50,000 --> 00:28:53,000
“其他方向，上攻

525
00:28:53,000 --> 00:28:55,000
現在你就可以遍歷來回，

526
00:28:55,000 --> 00:28:59,000
的缺點是，現在你正在使用三次盡可能多的內存，我們使用

527
00:28:59,000 --> 00:29:04,000
並且還加入複雜的代碼，你寫得到它的權利。

528
00:29:04,000 --> 00:29:08,000
但這些都可能是非常合理的折衷，，如果反轉更重要的是。

529
00:29:08,000 --> 00:29:10,000
是啊。

530
00:29:10,000 --> 00:29:12,000
[學生]：你也不能有一個2D鏈接列表。

531
00:29:12,000 --> 00:29:16,000
好，你可以不真的有一個二維鍊錶。

532
00:29:16,000 --> 00:29:18,000
你可以。這不是那麼容易達到的陣列。

533
00:29:18,000 --> 00:29:21,000
與數組一樣，你做開放式的支架，封閉的支架，打開支架，封閉支架，

534
00:29:21,000 --> 00:29:23,000
，你會得到一些的二維結構。

535
00:29:23,000 --> 00:29:26,000
你可以實現一個2維鍊錶

536
00:29:26,000 --> 00:29:29,000
如果你這樣做附加你提出的第三個指針，這些東西，

537
00:29:29,000 --> 00:29:34,000
如果你認為你的另一個列表3D風格

538
00:29:34,000 --> 00:29:40,000
從屏幕到我們所有人來說，這僅僅是某種形式的另一個產業鏈。

539
00:29:40,000 --> 00:29:45,000
我們能做到這一點，但它不是簡單，只要鍵入開括號，方括號。是啊。

540
00:29:45,000 --> 00:29:48,000
[聽不見的學生問題]

541
00:29:48,000 --> 00:29:50,000
好，所以這是一個真正的踢球者。

542
00:29:50,000 --> 00:29:54,000
>> 這些已經消瘦了，我們喜歡哦，二進制搜索算法，

543
00:29:54,000 --> 00:29:57,000
您可以搜索陣列上的數字板

544
00:29:57,000 --> 00:30:01,000
或電話簿，以便更迅速，如果您使用分而治之

545
00:30:01,000 --> 00:30:05,000
二進制搜索算法，，但二進制搜索需要兩個假設。

546
00:30:05,000 --> 00:30:09,000
其中，該數據被排序。

547
00:30:09,000 --> 00:30:11,000
現在，我們可以推測這個排序，

548
00:30:11,000 --> 00:30:14,000
所以也許這不是一個問題，但還承擔二進制搜索

549
00:30:14,000 --> 00:30:18,000
你有隨機存取的號碼列表，

550
00:30:18,000 --> 00:30:21,000
陣列允許您進行隨機存取，隨機存取，

551
00:30:21,000 --> 00:30:24,000
我的意思是，如果你是一個數組，你需要多少時間

552
00:30:24,000 --> 00:30:26,000
支架0？

553
00:30:26,000 --> 00:30:29,000
一人操作，你只需要使用[0]和你說得對。

554
00:30:29,000 --> 00:30:33,000
沒有考慮到位置10多少步？

555
00:30:33,000 --> 00:30:36,000
一步，你只是去[10]你的存在。

556
00:30:36,000 --> 00:30:40,000
相比之下，你怎麼在一個鍊錶到第10的整數？

557
00:30:40,000 --> 00:30:42,000
因為你只記得，你必須從頭開始

558
00:30:42,000 --> 00:30:45,000
一個鍊錶的開始，就像一個字符串被記住

559
00:30:45,000 --> 00:30:48,000
它的第一個字符的地址，並發現第10整數

560
00:30:48,000 --> 00:30:53,000
或10字符串中的字符，你必須搜索整個該死的東西。

561
00:30:53,000 --> 00:30:55,000
>> 同樣，我們還沒有解決所有的問題。

562
00:30:55,000 --> 00:31:00,000
我們正在推出新的，但它實際上取決於你想要什麼設計。

563
00:31:00,000 --> 00:31:04,000
在實施方面，我們可以借用一個想法，學生結構。

564
00:31:04,000 --> 00:31:07,000
它的語法很相似，但現在的想法是多了幾分抽象

565
00:31:07,000 --> 00:31:09,000
比房子，名稱和ID。

566
00:31:09,000 --> 00:31:13,000
不過，我建議，我們可以有一個數據結構的C

567
00:31:13,000 --> 00:31:17,000
被稱為節點，在幻燈片上顯示的最後一個字，

568
00:31:17,000 --> 00:31:21,000
裡面一個節點，一個節點是在計算機科學只是一個普通的容器。

569
00:31:21,000 --> 00:31:25,000
它通常畫成一個圓或正方形或長方形，因為我們已經做了。

570
00:31:25,000 --> 00:31:27,000
這個數據結構中，我們有一個int，N，

571
00:31:27,000 --> 00:31:29,000
所以這是我想存儲的號碼。

572
00:31:29,000 --> 00:31:36,000
但是，這是什麼第二線，結構節點下的嗎？

573
00:31:36,000 --> 00:31:40,000
為什麼這是正確的，這個東西發揮什麼樣的作用，

574
00:31:40,000 --> 00:31:42,000
即使這是一個有點神秘的第一眼？

575
00:31:42,000 --> 00:31:44,000
是啊。

576
00:31:44,000 --> 00:31:46,000
[聽不見的學生反應]

577
00:31:46,000 --> 00:31:50,000
沒錯，*排序的戰利品，這是某種類型的指針。

578
00:31:50,000 --> 00:31:53,000
這個指針的名字是任意下，

579
00:31:53,000 --> 00:32:00,000
但我們可以把它叫做我們想要的東西，但什麼該指針指向？

580
00:32:00,000 --> 00:32:03,000
[學生]：另一個節點。>>沒錯，它指向到另外一個這樣的節點。

581
00:32:03,000 --> 00:32:05,000
>> 現在，這是排序的好奇心，C.

582
00:32:05,000 --> 00:32:09,000
回想一下，C被讀取由編譯器從上到下，從左到右，

583
00:32:09,000 --> 00:32:13,000
這意味著，如果 - 這是一個有點不同，從我們所做的與學生。

584
00:32:13,000 --> 00:32:16,000
當我們定義一個學生，我們實際上沒有一個字。

585
00:32:16,000 --> 00:32:18,000
剛才說的typedef。

586
00:32:18,000 --> 00:32:20,000
然後，我們必須int的ID，字符串名稱，字符串的房子，

587
00:32:20,000 --> 00:32:23,000
然後學生在底部的結構。

588
00:32:23,000 --> 00:32:26,000
此聲明是一個有點不同，因為，

589
00:32:26,000 --> 00:32:28,000
再次，C編譯器是一個有點啞。

590
00:32:28,000 --> 00:32:30,000
這只是要讀從上到下，

591
00:32:30,000 --> 00:32:33,000
因此，如果到達2號線

592
00:32:33,000 --> 00:32:37,000
下一個被聲明，它認為，哦，這裡有一個變量稱為下。

593
00:32:37,000 --> 00:32:39,000
這是一個指針，指向一個結構節點。

594
00:32:39,000 --> 00:32:42,000
編譯器就是要實現一個結構節點是什麼？

595
00:32:42,000 --> 00:32:44,000
我從來沒有聽說過這件事之前，

596
00:32:44,000 --> 00:32:47,000
因為這個詞節點，否則可能不會出現

597
00:32:47,000 --> 00:32:49,000
直到底部，所以有這樣的冗餘。

598
00:32:49,000 --> 00:32:53,000
你說結構節點，然後你就可以縮短以後

599
00:32:53,000 --> 00:32:56,000
於typedef在這裡，這是因為

600
00:32:56,000 --> 00:33:02,000
我們所引用的結構本身的內部結構。

601
00:33:02,000 --> 00:33:05,000
這是一個疑難雜症有。

602
00:33:05,000 --> 00:33:07,000
>> 一些有趣的問題出現。

603
00:33:07,000 --> 00:33:09,000
我們已經有了一個數字列表。我們怎麼插入？

604
00:33:09,000 --> 00:33:11,000
我們如何搜索呢？我們如何刪除它？

605
00:33:11,000 --> 00:33:13,000
尤其是現在，我們必須管理所有這些指針。

606
00:33:13,000 --> 00:33:15,000
你以為指針有點令人費解

607
00:33:15,000 --> 00:33:17,000
當你有一個，他們只是想讀取一個int。

608
00:33:17,000 --> 00:33:20,000
現在我們就來操縱整個列表的價值。

609
00:33:20,000 --> 00:33:22,000
為什麼我們不把我們的5分鐘的休息時間，在這裡，然後我們會帶

610
00:33:22,000 --> 00:33:34,000
一些人在舞台上這樣做。

611
00:33:34,000 --> 00:33:36,000
>> C是更多的樂趣時，它的行動了。

612
00:33:36,000 --> 00:33:39,000
哪些人會從字面上是第一嗎？

613
00:33:39,000 --> 00:33:41,000
好了，就行了。你是第一個。

614
00:33:41,000 --> 00:33:44,000
誰願意為9？好吧，9。

615
00:33:44,000 --> 00:33:46,000
9怎麼樣？ 17？

616
00:33:46,000 --> 00:33:51,000
這裡一個小團體。 22和26，前排。

617
00:33:51,000 --> 00:33:53,000
然後怎麼樣的人在那裡被指出。

618
00:33:53,000 --> 00:33:57,000
你有34個。好吧，34就行了。

619
00:33:57,000 --> 00:33:59,000
首先是在那裡。好了，你們四個。

620
00:33:59,000 --> 00:34:01,000
我們誰也說9？

621
00:34:01,000 --> 00:34:04,000
誰是我們的9？

622
00:34:04,000 --> 00:34:07,000
誰真正想要的是9？好吧，來吧，是9。

623
00:34:07,000 --> 00:34:10,000
在這裡，我們走了。

624
00:34:10,000 --> 00:34:13,000
34，我們將滿足你在那裡。

625
00:34:13,000 --> 00:34:17,000
第一部分是使自己看起來像他一樣。

626
00:34:17,000 --> 00:34:21,000
26，22，17，良好的。

627
00:34:21,000 --> 00:34:25,000
如果你能站到一邊，因為我們要malloc你在某一時刻。

628
00:34:25,000 --> 00:34:29,000
>> 好，好。

629
00:34:29,000 --> 00:34:32,000
好，很好，所以讓我們在這裡問幾個問題。

630
00:34:32,000 --> 00:34:34,000
實際上，什麼是你的名字嗎？“梅艷芳。

631
00:34:34,000 --> 00:34:37,000
梅艷芳，沒關係，在這裡。

632
00:34:37,000 --> 00:34:41,000
梅艷芳樣的幫助我們解決了一個相當簡單的問題，第一，

633
00:34:41,000 --> 00:34:44,000
你是怎麼做的，而不是一個值是否在列表中呢？

634
00:34:44,000 --> 00:34:48,000
現在，請注意，第一，這裡所代表的盧卡斯，

635
00:34:48,000 --> 00:34:52,000
是有點不同的，所以他的一張紙是故意側身

636
00:34:52,000 --> 00:34:55,000
因為它不是相當高，不佔用多少位，

637
00:34:55,000 --> 00:34:58,000
即使在技術上他有相同尺寸的紙張，只是旋轉。

638
00:34:58,000 --> 00:35:01,000
但他是一個有點不同，他只有32位的指針，

639
00:35:01,000 --> 00:35:05,000
所有這些傢伙都是64位，其中一半是多少，其中一半是指針。

640
00:35:05,000 --> 00:35:08,000
但指針沒有描述的，所以如果你們能有點笨拙

641
00:35:08,000 --> 00:35:12,000
用左手指向旁邊的人給你。

642
00:35:12,000 --> 00:35:14,000
你是34號。你叫什麼名字？

643
00:35:14,000 --> 00:35:16,000
阿里。

644
00:35:16,000 --> 00:35:19,000
阿里，所以實際上，保存的文件在你的右手，左手向下的直線。

645
00:35:19,000 --> 00:35:21,000
表示空的左側。

646
00:35:21,000 --> 00:35:24,000
>> 現在我們的人的照片是非常一致的。

647
00:35:24,000 --> 00:35:26,000
這實際上是指針的工作方式。

648
00:35:26,000 --> 00:35:29,000
如果你能一點點堆砌方式，所以我不是在用自己的方式。

649
00:35:29,000 --> 00:35:34,000
梅艷芳在這裡，找到我的22號，

650
00:35:34,000 --> 00:35:40,000
但假設一個約束的不是人拿著紙片，

651
00:35:40,000 --> 00:35:43,000
但是這是一個列表，你只需要盧卡斯開始

652
00:35:43,000 --> 00:35:46,000
因為他是名符其實的第一個指針。

653
00:35:46,000 --> 00:35:51,000
假設你自己是一個指針，所以你也有能力指向的東西。

654
00:35:51,000 --> 00:35:56,000
你為什麼不首先指向的正是盧卡斯指著嗎？

655
00:35:56,000 --> 00:35:58,000
好，讓我在這裡制定了這一點。

656
00:35:58,000 --> 00:36:04,000
為了討論的方便，讓我拉了一個空白頁。

657
00:36:04,000 --> 00:36:06,000
你怎麼拼寫你的名字嗎？“梅艷芳。

658
00:36:06,000 --> 00:36:08,000
好了，梅艷芳。

659
00:36:08,000 --> 00:36:18,000
比方說節點*阿尼塔·盧卡斯。

660
00:36:18,000 --> 00:36:22,000
好了，我們不應該給你打電話盧卡斯。我們應該先打電話給你。

661
00:36:22,000 --> 00:36:25,000
這是為什麼，其實與現實在這裡？

662
00:36:25,000 --> 00:36:27,000
其中，第一個已經存在。

663
00:36:27,000 --> 00:36:30,000
大概是首先被分配在這裡的某個地方。

664
00:36:30,000 --> 00:36:35,000
節點*首先，它被分配的名單不知何故。

665
00:36:35,000 --> 00:36:37,000
我不知道這是怎麼發生的。這發生在上課前開始。

666
00:36:37,000 --> 00:36:40,000
這個鍊錶人類已創建。

667
00:36:40,000 --> 00:36:44,000
在這一點上的故事，這是所有在Facebook上顯然後

668
00:36:44,000 --> 00:36:49,000
在這一點上的故事，梅艷芳已被初始化為等於第一，

669
00:36:49,000 --> 00:36:51,000
這並不意味著在盧卡斯，梅艷芳點。

670
00:36:51,000 --> 00:36:53,000
相反，她指著他指出在

671
00:36:53,000 --> 00:36:57,000
因為相同的地址裡面的Lucas的32位 -  1，2，3  - 

672
00:36:57,000 --> 00:37:01,000
現在也Anita的32位 -  1，2，3的內側。

673
00:37:01,000 --> 00:37:05,000
>> 找到22。你將如何去這樣做呢？

674
00:37:05,000 --> 00:37:07,000
那是什麼？>>指向任何。

675
00:37:07,000 --> 00:37:11,000
點什麼，所以，儘管它作為最好的，你可以在這裡行動。

676
00:37:11,000 --> 00:37:15,000
好，好，現在你指著你叫什麼名字22？

677
00:37:15,000 --> 00:37:18,000
“拉蒙，拉蒙。，所以拉蒙同比增長22。

678
00:37:18,000 --> 00:37:20,000
現在，您已經做了檢查。

679
00:37:20,000 --> 00:37:24,000
拉蒙== 22，如果是的話，例如，我們可以返回true。

680
00:37:24,000 --> 00:37:26,000
讓我，而這些人站在這裡，有點笨拙

681
00:37:26,000 --> 00:37:32,000
讓我做的東西像Bool快速找到。

682
00:37:32,000 --> 00:37:37,000
我要繼續前進，並說（節點列表，詮釋n）。

683
00:37:37,000 --> 00:37:39,000
跟你說，我馬上就回來。我只需要編寫一些代碼。

684
00:37:39,000 --> 00:37:45,000
現在我要繼續前進，並做到這一點，節點梅艷芳=列表。

685
00:37:45,000 --> 00:37:51,000
我要繼續前進，並指出，雖然（袁詠儀！= NULL）。

686
00:37:51,000 --> 00:37:57,000
>> 這裡的比喻還是有點捉襟見肘，但（袁詠儀！= NULL），我想這樣做嗎？

687
00:37:57,000 --> 00:38:03,000
我需要一些方法的引用

688
00:38:03,000 --> 00:38:05,000
梅艷芳指向的整數。

689
00:38:05,000 --> 00:38:08,000
在過去，當我們有結構，其中節點是

690
00:38:08,000 --> 00:38:11,000
我們使用點符號，我們會這樣說

691
00:38:11,000 --> 00:38:15,000
anita.n，但這裡的問題是，Anita是不是結構本身。

692
00:38:15,000 --> 00:38:17,000
她是什麼人？

693
00:38:17,000 --> 00:38:21,000
她是一個指針，所以真的，如果我們想用這點表示法

694
00:38:21,000 --> 00:38:23,000
這是怎麼回事看故意有點神秘

695
00:38:23,000 --> 00:38:28,000
我們必須做這樣的事情去任何Anita的左手指向

696
00:38:28,000 --> 00:38:31,000
然後得到該領域稱為n。

697
00:38:31,000 --> 00:38:35,000
Anita是一個指針，但*梅艷芳是什麼？

698
00:38:35,000 --> 00:38:38,000
你覺得什麼，當你去Anita是指什麼？

699
00:38:38,000 --> 00:38:42,000
一個結構，一個節點，一個節點，召回，有一個字段稱為n

700
00:38:42,000 --> 00:38:47,000
因為它，記得，這2場，下和n，

701
00:38:47,000 --> 00:38:50,000
我們剛才也看到了這裡。

702
00:38:50,000 --> 00:38:53,000
>> 為了真正模仿的代碼，

703
00:38:53,000 --> 00:39:02,000
我們可以這樣做，並說，如果（（*梅艷芳）N = N），我在尋找的n。

704
00:39:02,000 --> 00:39:04,000
請注意，該功能是通過我關心的數量。

705
00:39:04,000 --> 00:39:10,000
然後我就可以繼續做類似返回true。

706
00:39:10,000 --> 00:39:12,000
否則，如果不是這樣的情況下，我想這樣做嗎？

707
00:39:12,000 --> 00:39:19,000
我該如何翻譯的代碼有什麼梅艷芳這樣做直觀地走在列表中呢？

708
00:39:19,000 --> 00:39:26,000
我應該怎麼做模擬梅艷芳的左側，採取這樣的步驟，一步到左邊？

709
00:39:26,000 --> 00:39:28,000
[聽不見的學生回應] >>那是什麼？

710
00:39:28,000 --> 00:39:30,000
[聽不見的學生反應]

711
00:39:30,000 --> 00:39:34,000
好，不是一個壞主意，但在過去，當我們已經做到了這一點，我們已經做了梅艷芳+ +

712
00:39:34,000 --> 00:39:37,000
因為這會增加數字1〜梅艷芳，

713
00:39:37,000 --> 00:39:40,000
這通常指向旁邊的人，像拉蒙

714
00:39:40,000 --> 00:39:44,000
旁邊的人，他或他旁邊的人的路線。

715
00:39:44,000 --> 00:39:49,000
但是這還不是相當不錯的，在這裡，因為這是什麼東西在內存中的樣子嗎？

716
00:39:49,000 --> 00:39:54,000
不是這樣的。我們必須禁用。

717
00:39:54,000 --> 00:40:00,000
它看起來像這樣在內存中，即使我已經開了1個和2個和3靠近彼此，

718
00:40:00,000 --> 00:40:03,000
如果我們真的模擬這個可以你的傢伙，而仍指向相同的人，

719
00:40:03,000 --> 00:40:07,000
你們中的一些採取隨機退後一步，一些你一個隨機的一步嗎？

720
00:40:07,000 --> 00:40:10,000
>> 這個爛攤子仍是一個鍊錶，

721
00:40:10,000 --> 00:40:13,000
但這些人可能是在內存中的任何地方，

722
00:40:13,000 --> 00:40:15,000
阿尼塔+ +沒有去上班，為什麼呢？

723
00:40:15,000 --> 00:40:19,000
什麼位置梅艷芳+ +？

724
00:40:19,000 --> 00:40:21,000
誰知道。

725
00:40:21,000 --> 00:40:24,000
這是一些其他的價值，只是恰巧被插

726
00:40:24,000 --> 00:40:28,000
在所有的這些節點的機會，因為我們不使用一個數組。

727
00:40:28,000 --> 00:40:30,000
我們分配每個節點。

728
00:40:30,000 --> 00:40:32,000
好吧，如果你們可以清理自己回來了。

729
00:40:32,000 --> 00:40:37,000
最後，我提議，而不是梅艷芳+ +，而不是做梅艷芳得到

730
00:40:37,000 --> 00:40:42,000
好，為什麼我們不走任何Anita是指向，然後做下？

731
00:40:42,000 --> 00:40:45,000
換句話說，我們去拉蒙，他的22號，

732
00:40:45,000 --> 00:40:51,000
然後，接下來就是雖然梅艷芳模仿他的左手指針。

733
00:40:51,000 --> 00:40:54,000
但她不會走的更遠，因為我們比拉蒙發現有22。

734
00:40:54,000 --> 00:40:56,000
但是，這將是這個想法。現在，這是一個神爛攤子。

735
00:40:56,000 --> 00:40:59,000
說實話，沒有人會永遠記住這個語法，幸運的是，

736
00:40:59,000 --> 00:41:04,000
它實際上是有點故意的，哦，你沒有實際看到我寫的是什麼。

737
00:41:04,000 --> 00:41:08,000
如果可以的話，這將是更具吸引力的。瞧！

738
00:41:08,000 --> 00:41:10,000
>> 在幕後，我解決這樣的問題。

739
00:41:10,000 --> 00:41:14,000
阿妮塔，採取這一步驟的左側，

740
00:41:14,000 --> 00:41:18,000
首先，我們去的地址，Anita是指向

741
00:41:18,000 --> 00:41:23,000
和在那裡她會發現不只有N，我們只是檢查比較的緣故，

742
00:41:23,000 --> 00:41:25,000
但你也將尋找下一個 - 在這種情況下，

743
00:41:25,000 --> 00:41:28,000
拉曼左手指著在列表中的下一個節點。

744
00:41:28,000 --> 00:41:32,000
但是，這是我前面提到的神的爛攤子，

745
00:41:32,000 --> 00:41:34,000
但事實證明，輸出C讓我們簡化了這一點。

746
00:41:34,000 --> 00:41:40,000
而不是寫（梅艷芳），我們可以改為只寫梅艷芳 - > N，

747
00:41:40,000 --> 00:41:45,000
和它的功能完全一樣的東西，但它是一個更直觀的，

748
00:41:45,000 --> 00:41:48,000
這是一個很大的圖片更符合我們一直畫

749
00:41:48,000 --> 00:41:50,000
這一切的時候使用箭頭。

750
00:41:50,000 --> 00:41:57,000
>> 最後，在課程結束後，我們需要做的嗎？

751
00:41:57,000 --> 00:42:00,000
還有一個剩餘的代碼行。

752
00:42:00,000 --> 00:42:02,000
回報是什麼？

753
00:42:02,000 --> 00:42:05,000
假的，因為如果我們通過整個循環

754
00:42:05,000 --> 00:42:10,000
Anita是，事實上，空，這意味著她千里迢迢到列表末尾

755
00:42:10,000 --> 00:42:12,000
她指著你叫什麼名字呢？

756
00:42:12,000 --> 00:42:15,000
阿里。>>阿里的左手，這是空的。

757
00:42:15,000 --> 00:42:18,000
現在，Anita是空的，我意識到你只是站在這裡，笨拙的地獄

758
00:42:18,000 --> 00:42:21,000
因為我要去獨白，

759
00:42:21,000 --> 00:42:23,000
但我們會涉及到你在短短的時刻。

760
00:42:23,000 --> 00:42:27,000
Anita是空的故事，在這一點上，因此while循環結束，

761
00:42:27,000 --> 00:42:30,000
我們必須返回false，因為如果她得到了Ari的空指針的方式來

762
00:42:30,000 --> 00:42:34,000
再有就是沒有，她試圖在列表中的號碼。

763
00:42:34,000 --> 00:42:39,000
我們可以清潔過，但是這是一個很好的實現，那麼

764
00:42:39,000 --> 00:42:43,000
遍歷函數，一個鏈接列表的功能。

765
00:42:43,000 --> 00:42:48,000
它仍然是線性搜索，但它不是簡單+ +指針

766
00:42:48,000 --> 00:42:52,000
+ +變量i，因為現在我們不能猜

767
00:42:52,000 --> 00:42:54,000
這些節點，其中每個都在存儲器中。

768
00:42:54,000 --> 00:42:57,000
我們有字面上跟隨麵包屑的踪跡，或者更具體地說，

769
00:42:57,000 --> 00:43:00,000
指針，從一個節點到另一個。

770
00:43:00,000 --> 00:43:02,000
>> 現在，讓我們嘗試另一種。安妮塔，你要回來嗎？

771
00:43:02,000 --> 00:43:06,000
我們為什麼不繼續分配從觀眾的另外一個人嗎？

772
00:43:06,000 --> 00:43:08,000
malloc的，你叫什麼名字？“麗貝卡。

773
00:43:08,000 --> 00:43:10,000
麗貝卡。 Rebecca一直malloced，從觀眾，

774
00:43:10,000 --> 00:43:13,000
她現在存儲55號。

775
00:43:13,000 --> 00:43:17,000
現在在手的目標是梅艷芳插入

776
00:43:17,000 --> 00:43:22,000
麗貝卡到鍊錶，在合適的地方。

777
00:43:22,000 --> 00:43:24,000
到這兒來了一會兒。

778
00:43:24,000 --> 00:43:28,000
我已經做了這樣的事情。

779
00:43:28,000 --> 00:43:32,000
我已經做了節點*。你叫什麼名字呢？

780
00:43:32,000 --> 00:43:34,000
瑞貝卡，瑞貝卡。>>還好。

781
00:43:34,000 --> 00:43:41,000
麗貝卡得到的malloc（如sizeof（節點））。

782
00:43:41,000 --> 00:43:44,000
就像我們在過去的分配學生和諸如此類的事情，比如，

783
00:43:44,000 --> 00:43:46,000
我們需要的大小的節點，所以現在瑞貝卡

784
00:43:46,000 --> 00:43:49,000
是指什麼？

785
00:43:49,000 --> 00:43:52,000
麗貝卡她的內部具有兩個字段，其中之一是55。

786
00:43:52,000 --> 00:43:55,000
讓我們做什麼，麗貝卡 - > = 55。

787
00:43:55,000 --> 00:44:00,000
但後​​來麗貝卡 - >未來應像現在，她的手是怎麼樣的，誰知道？

788
00:44:00,000 --> 00:44:03,000
它指向一些垃圾的價值，那麼，為什麼不為好措施

789
00:44:03,000 --> 00:44:07,000
我們至少要做到這一點，使左手在她的身邊。

790
00:44:07,000 --> 00:44:09,000
現在，梅艷芳，把它從這裡開始。

791
00:44:09,000 --> 00:44:11,000
你有瑞貝卡已被分配。

792
00:44:11,000 --> 00:44:20,000
繼續前進，發現我們應該把麗貝卡。

793
00:44:20,000 --> 00:44:25,000
好，非常好。

794
00:44:25,000 --> 00:44:28,000
好了，好了，現在我們需要你提供一點方向，

795
00:44:28,000 --> 00:44:30,000
所以你已經達到了阿里。

796
00:44:30,000 --> 00:44:33,000
他的左手是空的，但麗貝卡顯然屬於正確的，

797
00:44:33,000 --> 00:44:36,000
讓我們怎麼改變這個鍊錶

798
00:44:36,000 --> 00:44:38,000
為了插入到適當的位置麗貝卡？

799
00:44:38,000 --> 00:44:42,000
如果你可以從字面上將根據需要周圍人的左手，

800
00:44:42,000 --> 00:44:48,000
我們會解決這個問題的方式。

801
00:44:48,000 --> 00:44:52,000
好，好，同時，麗貝卡的左手在她的身邊。

802
00:44:52,000 --> 00:44:54,000
>> 這是太容易了。

803
00:44:54,000 --> 00:44:57,000
讓我們嘗試分配的 - 我們做得差不多了，20。

804
00:44:57,000 --> 00:44:59,000
好了，就行了。

805
00:44:59,000 --> 00:45:04,000
20已分配的，所以讓我去，說在這裡再次

806
00:45:04,000 --> 00:45:07,000
我們剛剛做了的節點*薩德。

807
00:45:07,000 --> 00:45:11,000
我們擁有的malloc（如sizeof（節點））。

808
00:45:11,000 --> 00:45:16,000
然後，我們做完全相同的語法，因為我們做了前20，

809
00:45:16,000 --> 00:45:20,000
我會盡下= NULL，現在是Anita的

810
00:45:20,000 --> 00:45:23,000
插入到鍊錶中，如果你能玩，相同的作用。

811
00:45:23,000 --> 00:45:30,000
執行。

812
00:45:30,000 --> 00:45:32,000
好，好。

813
00:45:32,000 --> 00:45:38,000
現在仔細想想，然後再開始移動周圍的左手。

814
00:45:38,000 --> 00:45:46,000
您的今天得到了最尷尬的角色。

815
00:45:46,000 --> 00:45:59,000
誰的手應先移走？

816
00:45:59,000 --> 00:46:02,000
好了，等等，我聽到一些​​不。

817
00:46:02,000 --> 00:46:07,000
如果有些人會禮貌地幫助解決一個尷尬的境地。

818
00:46:07,000 --> 00:46:11,000
誰的左手也許應該首先更新嗎？是啊。

819
00:46:11,000 --> 00:46:13,000
[學生]薩阿德。

820
00:46:13,000 --> 00:46:15,000
好了，薩阿德的，為什麼有關係嗎？

821
00:46:15,000 --> 00:46:17,000
[聽不見的學生反應]

822
00:46:17,000 --> 00:46:19,000
好，因為如果我們把你叫什麼名字？>>馬歇爾。

823
00:46:19,000 --> 00:46:22,000
馬歇爾，如果我們先動了手，空，

824
00:46:22,000 --> 00:46:25,000
現在，我們已經從字面上孤立在此列表中的四個人

825
00:46:25,000 --> 00:46:29,000
因為他是唯一指向拉蒙和每個人的左，

826
00:46:29,000 --> 00:46:31,000
所以更新該指針是壞的。

827
00:46:31,000 --> 00:46:33,000
我們的撤消。

828
00:46:33,000 --> 00:46:37,000
好，現在繼續前進，將適當的左手指向拉蒙。

829
00:46:37,000 --> 00:46:39,000
這感覺有點多餘。

830
00:46:39,000 --> 00:46:41,000
現在有兩個人指著拉蒙，但

831
00:46:41,000 --> 00:46:43,000
因為現在我們怎麼更新列表？

832
00:46:43,000 --> 00:46:48,000
另一方面，移動嗎？

833
00:46:48,000 --> 00:46:53,000
好極了，現在我們失去了任何記憶了嗎？

834
00:46:53,000 --> 00:46:57,000
沒有那麼好，讓我們來看看，如果我們不能打破這一次。

835
00:46:57,000 --> 00:47:00,000
>> Mallocing最後一次，5號。

836
00:47:00,000 --> 00:47:04,000
在後面，一路下來吧。

837
00:47:04,000 --> 00:47:08,000
這是非常令人興奮的。

838
00:47:08,000 --> 00:47:15,000
[掌聲]

839
00:47:15,000 --> 00:47:17,000
你叫什麼名字？“羅恩。

840
00:47:17,000 --> 00:47:19,000
羅恩，好吧，你是malloced 5號。

841
00:47:19,000 --> 00:47:23,000
我們剛剛執行的代碼幾乎相同，這些

842
00:47:23,000 --> 00:47:26,000
只用一個不同的名字。

843
00:47:26,000 --> 00:47:28,000
優秀。

844
00:47:28,000 --> 00:47:38,000
現在，梅艷芳，運氣好的話插入到列表中的5號。

845
00:47:38,000 --> 00:47:43,000
好，？

846
00:47:43,000 --> 00:47:47,000
好極了，所以這是真正的三個案件總數的三分之一。

847
00:47:47,000 --> 00:47:49,000
我們第一次有人結束時，麗貝卡。

848
00:47:49,000 --> 00:47:51,000
然後，我們在中間的人。

849
00:47:51,000 --> 00:47:53,000
現在我們在開始時，並且在該示例中，已經有人

850
00:47:53,000 --> 00:47:56,000
我們現在有更新盧卡斯的第一次

851
00:47:56,000 --> 00:48:00,000
因為現在在列表中的第一個元素指向一個新的節點，

852
00:48:00,000 --> 00:48:03,000
誰，依次指向在節點號9。

853
00:48:03,000 --> 00:48:06,000
>> 這是一個巨大的尷尬的示範，我敢肯定，

854
00:48:06,000 --> 00:48:08,000
所以這些傢伙又大又圓的掌聲，如果你能。

855
00:48:08,000 --> 00:48:11,000
很好地完成。

856
00:48:11,000 --> 00:48:17,000
這就是全部。作為一個小的內存，您可以保留您的紙片。

857
00:48:17,000 --> 00:48:22,000
事實證明，這樣做的代碼

858
00:48:22,000 --> 00:48:26,000
是不是很簡單，只是動動手左右

859
00:48:26,000 --> 00:48:28,000
和指向指針的不同的東西。

860
00:48:28,000 --> 00:48:31,000
但意識到，當它來的時候實現的東西，如

861
00:48:31,000 --> 00:48:34,000
一個鍊錶或它的一個變種，如果你專注於真正

862
00:48:34,000 --> 00:48:38,000
這些基本因素，一口大小的問題，我必須弄清楚，

863
00:48:38,000 --> 00:48:43,000
是這只手，這手，否則，什麼是一個相當複雜的程序

864
00:48:43,000 --> 00:48:47,000
可以，其實這樣相當簡單的積木。

865
00:48:47,000 --> 00:48:51,000
>> 讓我們把事情仍然在一個更複雜的方向。

866
00:48:51,000 --> 00:48:53,000
我們現在有鍊錶的概念。

867
00:48:53,000 --> 00:48:57,000
我們也有感謝的建議有一個雙向鍊錶，

868
00:48:57,000 --> 00:49:01,000
這看起來幾乎是一樣的，但現在我們有兩個內部指針的結構

869
00:49:01,000 --> 00:49:05,000
，而不是一個，我們也許可以調用這些指針的前面和後面的

870
00:49:05,000 --> 00:49:08,000
或左或右，但我們做的，其實，需要其中的兩個。

871
00:49:08,000 --> 00:49:10,000
代碼將是更複雜一點。

872
00:49:10,000 --> 00:49:12,000
梅艷芳將不得不做更多的工作在這裡的舞台上。

873
00:49:12,000 --> 00:49:15,000
但是，我們可以肯定實現該種結構。

874
00:49:15,000 --> 00:49:19,000
但是，在運行時間方面，將運行時間

875
00:49:19,000 --> 00:49:24,000
梅艷芳一個鍊錶中找到一個數n？

876
00:49:24,000 --> 00:49:27,000
還是大O n的，所以它是沒有更好的線性搜索。

877
00:49:27,000 --> 00:49:29,000
不過，我們不能做二進制搜索。

878
00:49:29,000 --> 00:49:34,000
為什麼會這樣呢？你不能跳來跳去。

879
00:49:34,000 --> 00:49:36,000
儘管我們很明顯的看到在舞台上的所有人類，

880
00:49:36,000 --> 00:49:39,000
和Anita目測它說，“這裡是中間的列表中。”

881
00:49:39,000 --> 00:49:42,000
她不知道，如果她的計算機程序

882
00:49:42,000 --> 00:49:47,000
因為她唯一鎖存到的情況下開始

883
00:49:47,000 --> 00:49:50,000
盧卡斯，誰是第一個指針。

884
00:49:50,000 --> 00:49:53,000
她一定要遵循這些鏈接，

885
00:49:53,000 --> 00:49:56,000
數她，直到她找到大致的中間，

886
00:49:56,000 --> 00:49:58,000
即使如此，她不知道，當她到達中間

887
00:49:58,000 --> 00:50:01,000
除非她去所有的方式結束弄清楚有多少，

888
00:50:01,000 --> 00:50:05,000
然後回溯，而且也將是很難的，除非你有

889
00:50:05,000 --> 00:50:07,000
某種形式的雙向鍊錶。

890
00:50:07,000 --> 00:50:10,000
>> 解決一些問題，但介紹他人。

891
00:50:10,000 --> 00:50:12,000
約一個完全不同的數據結構呢？

892
00:50:12,000 --> 00:50:15,000
這是一個照片的托盤Mather中樓，

893
00:50:15,000 --> 00:50:19,000
在這種情況下，我們有一個數據結構，我們也種已經在談論。

894
00:50:19,000 --> 00:50:22,000
我們談論中的堆棧內存的情況下，

895
00:50:22,000 --> 00:50:26,000
而這樣的刻意命名，是因為堆棧在內存方面

896
00:50:26,000 --> 00:50:31,000
實際上是一個數據結構，有越來越多的東西，在它的上面分層。

897
00:50:31,000 --> 00:50:35,000
但有趣的事情堆棧，因為在現實的情況下，

898
00:50:35,000 --> 00:50:38,000
是，它是一種特殊的數據結構。

899
00:50:38,000 --> 00:50:42,000
它是一個數據結構，從而使第一元件

900
00:50:42,000 --> 00:50:46,000
是的最後一個元素。

901
00:50:46,000 --> 00:50:50,000
如果你是第一個托盤入堆棧，

902
00:50:50,000 --> 00:50:53,000
你要不幸的是，最後一個托盤從堆棧中，

903
00:50:53,000 --> 00:50:55,000
而這並不一定是件好事。

904
00:50:55,000 --> 00:50:58,000
相反，你可以考慮一下周圍的其他方法，

905
00:50:58,000 --> 00:51:02,000
最後是第一個出來的。

906
00:51:02,000 --> 00:51:05,000
>> 現在，你的任何方案，浮現在腦海中有一個堆棧

907
00:51:05,000 --> 00:51:08,000
數據結構，具有該屬性

908
00:51:08,000 --> 00:51:13,000
中的最後一個，第一個出來的，實際上是吸引力？

909
00:51:13,000 --> 00:51:16,000
這是一件好事嗎？這是一件壞事嗎？

910
00:51:16,000 --> 00:51:19,000
這絕對是一件壞事，如果托盤不盡相同

911
00:51:19,000 --> 00:51:21,000
他們都是不同的顏色或諸如此類的東西，

912
00:51:21,000 --> 00:51:24,000
你想要的顏色是所有的方式在底部。

913
00:51:24,000 --> 00:51:26,000
當然，你不能，不花大力氣。

914
00:51:26,000 --> 00:51:28,000
你必須從頂部開始，一路下滑。

915
00:51:28,000 --> 00:51:31,000
同樣，如果你​​是其中之一，這些風扇男孩

916
00:51:31,000 --> 00:51:34,000
試圖讓iPhone和排隊等待了一夜的人

917
00:51:34,000 --> 00:51:36,000
在這樣的地方嗎？

918
00:51:36,000 --> 00:51:40,000
那豈不是很好，如果蘋果專賣店

919
00:51:40,000 --> 00:51:42,000
一個堆棧的數據結構嗎？

920
00:51:42,000 --> 00:51:44,000
耶？不僅如此嗎？

921
00:51:44,000 --> 00:51:47,000
這只是良好的人顯示在最後一分鐘

922
00:51:47,000 --> 00:51:50,000
，然後被拔了隊列。

923
00:51:50,000 --> 00:51:52,000
而事實上，這樣的傾向的事實，我說隊列

924
00:51:52,000 --> 00:51:56,000
實際上是一致的，我們所說的這種數據結構，

925
00:51:56,000 --> 00:51:59,000
在現實中的順序很重要，

926
00:51:59,000 --> 00:52:02,000
你想中的第一個，是第一個

927
00:52:02,000 --> 00:52:04,000
如果僅僅是為了人類的公平。

928
00:52:04,000 --> 00:52:07,000
一般情況下，我們將調用一個隊列的數據結構。

929
00:52:07,000 --> 00:52:11,000
>> 事實證明，除了鍊錶，我們就可以開始使用這些相同的基本思路

930
00:52:11,000 --> 00:52:15,000
開始創建新的，不同類型的解決方案的問題。

931
00:52:15,000 --> 00:52:19,000
例如，在堆棧的箱子中，我們可以表示一個堆棧

932
00:52:19,000 --> 00:52:22,000
使用的數據結構是這樣的，我會提出。

933
00:52:22,000 --> 00:52:26,000
在這種情況下，我宣布一個結構，我已經說過了這種結構的內部

934
00:52:26,000 --> 00:52:30,000
是一個數字數組變量的大小，

935
00:52:30,000 --> 00:52:33,000
我會打電話給這件事情一個堆棧。

936
00:52:33,000 --> 00:52:35,000
現在，為什麼會發生這種實際工作？

937
00:52:35,000 --> 00:52:43,000
在堆棧的情況下，我可以得出這樣有效地在屏幕上為一個數組。

938
00:52:43,000 --> 00:52:47,000
這裡是我的籌碼。這是我的號碼。

939
00:52:47,000 --> 00:52:50,000
我們將吸引他們，因為這，這，這，這，這。

940
00:52:50,000 --> 00:52:53,000
然後，我這裡有一些其他的數據成員，

941
00:52:53,000 --> 00:52:58,000
被稱為大小，所以這是大小，這是數字，

942
00:52:58,000 --> 00:53:02,000
集體，在這裡代表整個iPad的一個堆棧結構。

943
00:53:02,000 --> 00:53:07,000
現在，默認情況下，大小大概已經有被初始化為0，

944
00:53:07,000 --> 00:53:11,000
裡面有什麼數字陣列最初

945
00:53:11,000 --> 00:53:14,000
當我第一次分配的數組？

946
00:53:14,000 --> 00:53:16,000
垃圾。誰知道？它實際上並不重要。

947
00:53:16,000 --> 00:53:20,000
它並不重要，如果這是1，2，3，4，5，完全隨機

948
00:53:20,000 --> 00:53:25,000
我的結構中存儲的運氣不好，因為只要我知道的堆棧大小

949
00:53:25,000 --> 00:53:29,000
為0，則我知道編程方式，不看任何數組中的元素。

950
00:53:29,000 --> 00:53:31,000
不要緊，那裡有什麼。

951
00:53:31,000 --> 00:53:34,000
不要看他們，將一個大小為0的含義。

952
00:53:34,000 --> 00:53:38,000
>> 但是，假設現在我先走，然後插入到堆棧中的東西。

953
00:53:38,000 --> 00:53:42,000
我想插入數字5，所以我把這裡的5號，

954
00:53:42,000 --> 00:53:45,000
，然後我放下嗎？

955
00:53:45,000 --> 00:53:48,000
現在我想放下的大小，

956
00:53:48,000 --> 00:53:50,000
現在的堆棧大小為1。

957
00:53:50,000 --> 00:53:53,000
如果我繼續前進，插入數字，讓我們說，7下嗎？

958
00:53:53,000 --> 00:53:57,000
，然後被更新為2，然後我們會做9，

959
00:53:57,000 --> 00:54:02,000
然後這被更新為3。

960
00:54:02,000 --> 00:54:05,000
但有趣的功能，現在該堆棧的是，

961
00:54:05,000 --> 00:54:09,000
如果我想彈出，我應該刪除哪一個元素

962
00:54:09,000 --> 00:54:12,000
的堆棧的東西，可以這麼說嗎？

963
00:54:12,000 --> 00:54:14,000
9將是去的第一件事情。

964
00:54:14,000 --> 00:54:18,000
應該如何改變圖片，如果我想從棧中彈出一個元素，

965
00:54:18,000 --> 00:54:20,000
很像一個托盤Mather中？

966
00:54:20,000 --> 00:54:22,000
是的。>> [學生]：設置大小為2。

967
00:54:22,000 --> 00:54:27,000
沒錯，我做的是設置大小為2，和與陣列我該怎麼辦？

968
00:54:27,000 --> 00:54:29,000
我沒有做任何事情。

969
00:54:29,000 --> 00:54:32,000
我可以，只是肛門，把一個0或-1的東西來表示

970
00:54:32,000 --> 00:54:34,000
這是不是一個合法的值，但它並不重要，因為

971
00:54:34,000 --> 00:54:37,000
我可以記錄以外的數組本身它有多長

972
00:54:37,000 --> 00:54:41,000
所以，我知道，只有在此數組中的前兩個元素。

973
00:54:41,000 --> 00:54:47,000
現在，如果我去了，8號添加到這個數組中，如何改變圖片嗎？

974
00:54:47,000 --> 00:54:50,000
這將成為8，而且這變成3。

975
00:54:50,000 --> 00:54:52,000
我在這裡省幾個小錢。

976
00:54:52,000 --> 00:54:56,000
現在，我們有5個，7，8，和我們回來了大小為3。

977
00:54:56,000 --> 00:54:58,000
這是非常簡單的實現，

978
00:54:58,000 --> 00:55:06,000
但我們什麼時候這樣的設計決策感到後悔嗎？

979
00:55:06,000 --> 00:55:09,000
什麼時候的事情開始去非常，非常錯誤嗎？是啊。

980
00:55:09,000 --> 00:55:11,000
[聽不見的學生反應]

981
00:55:11,000 --> 00:55:13,000
當你想回去拿你的第一個元素進去，

982
00:55:13,000 --> 00:55:18,000
>> 原來，在這裡即使堆棧引擎蓋下的是一個數組，

983
00:55:18,000 --> 00:55:21,000
這些數據結構，我們已經開始談論一般也被稱為

984
00:55:21,000 --> 00:55:25,000
抽象的數據結構，他們是如何實現的

985
00:55:25,000 --> 00:55:27,000
完全是除了點。

986
00:55:27,000 --> 00:55:31,000
就像一個堆棧的數據結構應該是添加支持

987
00:55:31,000 --> 00:55:35,000
操作上推，一個托盤推入堆棧，

988
00:55:35,000 --> 00:55:39,000
和流行音樂，從堆棧中刪除一個元素，那就是它。

989
00:55:39,000 --> 00:55:43,000
如果你是下載別人的代碼已經實施

990
00:55:43,000 --> 00:55:46,000
這個東西叫做堆棧，這個人會寫

991
00:55:46,000 --> 00:55:49,000
只有兩個函數，你push和pop，在生活中，其唯一目的

992
00:55:49,000 --> 00:55:51,000
將這樣做。

993
00:55:51,000 --> 00:55:54,000
你或他或她是誰實施該計劃

994
00:55:54,000 --> 00:55:58,000
本來完全是一個決定如何實現

995
00:55:58,000 --> 00:56:00,000
引擎蓋下方的壓入和彈出的語義

996
00:56:00,000 --> 00:56:03,000
入棧和出棧的功能。

997
00:56:03,000 --> 00:56:07,000
我已經在這裡做了一個有點短視的決定

998
00:56:07,000 --> 00:56:10,000
通過實施這個簡單的數據結構，為什麼我的籌碼呢？

999
00:56:10,000 --> 00:56:12,000
當這個數據結構的突破？

1000
00:56:12,000 --> 00:56:18,000
在什麼情況下我必須返回一個錯誤，當用戶調用push，例如？

1001
00:56:18,000 --> 00:56:20,000
[學生]：如果沒有更多的空間。

1002
00:56:20,000 --> 00:56:23,000
沒錯，如果沒有更多的空間，如果我超過容量，

1003
00:56:23,000 --> 00:56:27,000
這是全部大寫的，因為它表明它是某種全局常量。

1004
00:56:27,000 --> 00:56:30,000
好吧，那麼我只是將不得不說，“對不起，我不能把另一個值

1005
00:56:30,000 --> 00:56:32,000
到堆棧上，“就像在奧美。

1006
00:56:32,000 --> 00:56:36,000
>> 在某些時候，他們會打那個小櫃的頂部。

1007
00:56:36,000 --> 00:56:39,000
在堆棧中沒有更多的空間或能力，在這一點有某種錯誤。

1008
00:56:39,000 --> 00:56:42,000
他們必須把元素的其他地方，其他地方的盤，

1009
00:56:42,000 --> 00:56:44,000
或無處。

1010
00:56:44,000 --> 00:56:47,000
現在，我們的隊列，可以實現略有不同。

1011
00:56:47,000 --> 00:56:50,000
隊列是有一點不同，引擎蓋下的，它可以實現

1012
00:56:50,000 --> 00:56:54,000
作為一個數組，但為什麼，在這種情況下，我建議

1013
00:56:54,000 --> 00:56:59,000
也有一個頭元素的列表頭，

1014
00:56:59,000 --> 00:57:06,000
前面的列表，線的第一人，在蘋果商店，除了大小？

1015
00:57:06,000 --> 00:57:14,000
為什麼我需要一個額外的數據嗎？

1016
00:57:14,000 --> 00:57:16,000
回想一下號碼是什麼

1017
00:57:16,000 --> 00:57:18,000
如果我畫如下。

1018
00:57:18,000 --> 00:57:21,000
現在假設這是一個隊列，而不是一個棧，

1019
00:57:21,000 --> 00:57:24,000
是一樣的蘋果專賣店排隊的差異是公平的。

1020
00:57:24,000 --> 00:57:27,000
在列表中的開始，在這種情況下，5號線中的第一個人

1021
00:57:27,000 --> 00:57:30,000
他或她將要被讓進店的第一。

1022
00:57:30,000 --> 00:57:32,000
讓我們做到這一點。

1023
00:57:32,000 --> 00:57:35,000
假設，這是我的隊列的狀態，在這一刻的時候，和現在的蘋果專賣店

1024
00:57:35,000 --> 00:57:39,000
打開的第一人，5號，是導致進店。

1025
00:57:39,000 --> 00:57:43,000
如何更改我的圖片，我去排隊第一人

1026
00:57:43,000 --> 00:57:47,000
在前面的行？

1027
00:57:47,000 --> 00:57:50,000
那是什麼？>> [學生]：更改隊列。

1028
00:57:50,000 --> 00:57:52,000
改變頭，所以就消失了。

1029
00:57:52,000 --> 00:57:56,000
在現實中，它彷彿如何做到這一點？

1030
00:57:56,000 --> 00:58:00,000
在現實中，雖然這傢伙消失。

1031
00:58:00,000 --> 00:58:03,000
7號做什麼實際的店嗎？

1032
00:58:03,000 --> 00:58:05,000
他們將向前邁出一大步。

1033
00:58:05,000 --> 00:58:08,000
>> 但我們體會到，當涉及到陣列

1034
00:58:08,000 --> 00:58:10,000
移動周圍的事物嗎？

1035
00:58:10,000 --> 00:58:12,000
這是一種浪費你的時間了，對不對？

1036
00:58:12,000 --> 00:58:16,000
為什麼你要那麼肛門有第一人

1037
00:58:16,000 --> 00:58:21,000
行開始的，在物理上的內存塊的開始？

1038
00:58:21,000 --> 00:58:23,000
這是完全不必要的。為什麼呢？

1039
00:58:23,000 --> 00:58:26,000
我只記得什麼呢？>> [聽不見的學生反應]

1040
00:58:26,000 --> 00:58:30,000
沒錯，我只記得這個額外的數據成員頭

1041
00:58:30,000 --> 00:58:34,000
現在的列表頭的不再是0，它是剛才。

1042
00:58:34,000 --> 00:58:39,000
現在，它實際上是數字1。就這樣，我得到了輕微的優化。

1043
00:58:39,000 --> 00:58:44,000
只是因為我去排隊的人從行的行開始在蘋果專賣店

1044
00:58:44,000 --> 00:58:47,000
但這並不意味著每個人都有轉移，召回是線性的操作。

1045
00:58:47,000 --> 00:58:50,000
相反，我可以只花費固定的時間

1046
00:58:50,000 --> 00:58:53,000
然後實現更快的響應。

1047
00:58:53,000 --> 00:58:56,000
但我付出的價格是獲得額外的性能

1048
00:58:56,000 --> 00:58:58,000
而不是轉移大家的嗎？

1049
00:58:58,000 --> 00:59:01,000
是啊。>> [聽不見的學生反應]

1050
00:59:01,000 --> 00:59:04,000
可以添加更多的人，好了，這個問題是正交

1051
00:59:04,000 --> 00:59:07,000
的事實，我們周圍的人不轉移。

1052
00:59:07,000 --> 00:59:11,000
它仍然是一個數組，所以我們是否轉移大家或不

1053
00:59:11,000 --> 00:59:13,000
哦，我明白你的意思，好吧。

1054
00:59:13,000 --> 00:59:16,000
其實，我同意你在說什麼的，因為它幾乎就像

1055
00:59:16,000 --> 00:59:19,000
現在，我們永遠不會使用這個數組開始了

1056
00:59:19,000 --> 00:59:22,000
因為，如果我刪除，然後刪除7。

1057
00:59:22,000 --> 00:59:24,000
但我只把人民的權利。

1058
00:59:24,000 --> 00:59:28,000
>> 我感覺就像是在浪費空間，最後，我的隊列分解成什麼都沒有，

1059
00:59:28,000 --> 00:59:31,000
因此，我們可能只是人們概括的，

1060
00:59:31,000 --> 00:59:35,000
我們可以認為這個數組真的為某種圓形結構，

1061
00:59:35,000 --> 00:59:38,000
但我們用C做什麼運營商在那種環繞嗎？

1062
00:59:38,000 --> 00:59:40,000
[聽不見的學生回應] >>模運算符。

1063
00:59:40,000 --> 00:59:43,000
這將是一個有點惱人認為，你是怎麼做到的環繞，

1064
00:59:43,000 --> 00:59:46,000
，但我們可以做到這一點，我們就可以開始把人民的利益，在曾經被認為是該行的前面，

1065
00:59:46,000 --> 00:59:52,000
但我們只記得誰是實際的行頭其實是與這頭變量。

1066
00:59:52,000 --> 00:59:57,000
什麼，如果不是，最終，我們的目標是，

1067
00:59:57,000 --> 01:00:00,000
看數字，我們在這裡所做過的舞台上與梅艷芳，

1068
01:00:00,000 --> 01:00:02,000
但我們希望所有這些世界最好的嗎？

1069
01:00:02,000 --> 01:00:05,000
我們希望有更多的複雜性比數組

1070
01:00:05,000 --> 01:00:09,000
因為我們希望能夠動態增長的數據結構。

1071
01:00:09,000 --> 01:00:12,000
但是，我們不希望擁有的東西，我們指出

1072
01:00:12,000 --> 01:00:15,000
在第一堂課是不是一個最佳的算法，

1073
01:00:15,000 --> 01:00:17,000
線性搜索。

1074
01:00:17,000 --> 01:00:21,000
事實證明，就可以了，事實上，實現

1075
01:00:21,000 --> 01:00:24,000
或至少​​接近恆定的時間，有人喜歡梅艷芳，

1076
01:00:24,000 --> 01:00:27,000
她的數據結構配置，如果她是一個鍊錶，

1077
01:00:27,000 --> 01:00:30,000
不是一個堆棧，而不是一個隊列中，可以，在事實上，

1078
01:00:30,000 --> 01:00:33,000
拿出一個數據結構，允許她看的東西，

1079
01:00:33,000 --> 01:00:37,000
什字，不只是數字，我們會打電話給固定的時間。

1080
01:00:37,000 --> 01:00:40,000
>> 而事實上，展望未來，在這個類中的一個pset時幾乎總是

1081
01:00:40,000 --> 01:00:43,000
一個拼寫檢查的實施，據此，

1082
01:00:43,000 --> 01:00:46,000
我們給你再次約15萬英文單詞，我們的目標是

1083
01:00:46,000 --> 01:00:51,000
加載到內存中，並迅速成為能夠回答問題的形式

1084
01:00:51,000 --> 01:00:54,000
這個詞是拼寫是否正確？

1085
01:00:54,000 --> 01:00:58,000
那真是糟透了，如果你不得不遍歷所有15萬字來回答這個問題。

1086
01:00:58,000 --> 01:01:02,000
但是，事實上，我們會看到，我們可以在非常非常快的時間內做到這一點。

1087
01:01:02,000 --> 01:01:06,000
這將涉及執行一些所謂的哈希表，

1088
01:01:06,000 --> 01:01:09,000
即使乍看之下這件事情被稱為哈希表是怎麼回事

1089
01:01:09,000 --> 01:01:12,000
讓我們實現這些超快速的響應時間，

1090
01:01:12,000 --> 01:01:18,000
事實證明，其實也有一個問題。

1091
01:01:18,000 --> 01:01:23,000
當談到時間來執行這件事情，再次，我老毛病又犯了。

1092
01:01:23,000 --> 01:01:25,000
我是唯一一個在這裡。

1093
01:01:25,000 --> 01:01:28,000
當談到時間落實這件事情被稱為哈希表，

1094
01:01:28,000 --> 01:01:30,000
我們將不得不做出決定。

1095
01:01:30,000 --> 01:01:32,000
這件事情應該多大究竟是什麼？

1096
01:01:32,000 --> 01:01:36,000
當我們開始這個哈希表中插入數字，

1097
01:01:36,000 --> 01:01:38,000
我們如何將它們存儲在這樣一種方式

1098
01:01:38,000 --> 01:01:42,000
，我們可以得到他們回來了，很快我們得到了他們？

1099
01:01:42,000 --> 01:01:45,000
但是，我們會看到不久這個問題的

1100
01:01:45,000 --> 01:01:48,000
當每個人的生日是在課堂上是相當有密切關係。

1101
01:01:48,000 --> 01:01:51,000
事實證明，在這個房間裡，我們已經有了幾百人，

1102
01:01:51,000 --> 01:01:56,000
這樣的可能性，我們兩個人有相同的生日可能是相當高的。

1103
01:01:56,000 --> 01:01:58,000
如果只有40，我們在這個房間裡嗎？

1104
01:01:58,000 --> 01:02:02,000
什麼是賠率的兩個人具有相同的生日嗎？

1105
01:02:02,000 --> 01:02:04,000
[學生]超過50％。

1106
01:02:04,000 --> 01:02:06,000
是啊，超過50％。事實上，我什至帶來了一個圖表。

1107
01:02:06,000 --> 01:02:08,000
事實證明，這是真的只是一個預演

1108
01:02:08,000 --> 01:02:12,000
如果只有58我們在這個房間裡，我們的概率為2

1109
01:02:12,000 --> 01:02:16,000
具有相同的生日是巨大的，幾乎100％，

1110
01:02:16,000 --> 01:02:20,000
而這會為我們造成的傷害一大堆週三。

1111
01:02:20,000 --> 01:02:24,000
>> 隨著中說，讓我們休會這裡。上週三，我們會看到你。

1112
01:02:24,000 --> 01:02:28,000
[掌聲]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]