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

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

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

4
00:00:08,720 --> 00:00:12,970
這是CS50，這是第6週結束。

5
00:00:12,970 --> 00:00:17,970
所以CS50x，哈佛大學的第一EDX主動參與課程

6
00:00:17,970 --> 00:00:20,590
確實在過去的這個星期一推出。

7
00:00:20,590 --> 00:00:23,460
如果你想別人在互聯網上窺見一斑

8
00:00:23,460 --> 00:00:27,180
現在跟隨著，您可以前往x.cs50.net的。

9
00:00:27,180 --> 00:00:30,350
這將您重定向到適當的位置上edx.org，

10
00:00:30,350 --> 00:00:34,160
這是和其他來自麻省理工學院和伯克利的課程，現在住。

11
00:00:34,160 --> 00:00:38,140
你必須註冊一個帳戶，你會發現，該材料是大致相同的

12
00:00:38,140 --> 00:00:42,170
你這學期，雖然幾個星期延遲，為我們做好一切準備。

13
00:00:42,170 --> 00:00:46,930
但現在學生在CS50x將看到的是一個接口，像這個一樣。

14
00:00:46,930 --> 00:00:50,040
這一點，例如，Zamyla問題集0領先的演練。

15
00:00:50,040 --> 00:00:54,230
在登錄到edx.org，一個CS50x學生看到了各種各樣的事情

16
00:00:54,230 --> 00:00:57,170
你希望看到的一門課程：在週一的演講，

17
00:00:57,170 --> 00:01:01,650
週三，各種短褲，習題的演練，PDF文件的講座。

18
00:01:01,650 --> 00:01:04,459
此外，你在這裡看到，機器翻譯

19
00:01:04,459 --> 00:01:08,390
中文，日語，西班牙語，意大利語，英語成績單，

20
00:01:08,390 --> 00:01:12,810
和一大堆其他的語言，肯定會是不完美的

21
00:01:12,810 --> 00:01:15,840
我們推出了所謂的API以編程方式使用，

22
00:01:15,840 --> 00:01:18,360
或應用程序編程接口，從谷歌

23
00:01:18,360 --> 00:01:21,360
，使我們能夠轉換成其他語言英語。

24
00:01:21,360 --> 00:01:24,100
但由於精彩的一百多名志願者精神，

25
00:01:24,100 --> 00:01:26,940
隨機的人在互聯網上獲悉的參與

26
00:01:26,940 --> 00:01:30,180
在這個項目中，我們將逐步得到改善這些翻譯的質量

27
00:01:30,180 --> 00:01:35,790
的人，我們的計算機已經糾正錯誤。

28
00:01:35,790 --> 00:01:42,330
>> 事實證明了，我們有一些更多的學生顯示週一最高上比我們最初的預期。

29
00:01:42,330 --> 00:01:48,980
事實上，現在CS50x的有100,000人在家裡。

30
00:01:48,980 --> 00:01:54,430
因此，知道你是所有的一部分，這使本課程在計算機科學的就職類的

31
00:01:54,430 --> 00:01:57,370
更為廣泛的教育，更廣泛地訪問。

32
00:01:57,370 --> 00:02:00,130
而現在的現實是，這些大量的網上課程，

33
00:02:00,130 --> 00:02:04,070
他們一開始都是非常高的數字，我們似乎已經在這裡完成。

34
00:02:04,070 --> 00:02:08,759
但這個目標，最終，CS50x是真正的終點線可能獲得盡可能多的人。

35
00:02:08,759 --> 00:02:12,000
在設計上，CS50x將要提供從過去的這個星期一

36
00:02:12,000 --> 00:02:17,430
所有2013年4月15日通過的方式，讓學校的人誰也承擔其他地方，

37
00:02:17,430 --> 00:02:20,990
工作，家庭，其他衝突一樣，有了更多的靈活性

38
00:02:20,990 --> 00:02:23,640
潛入這門課程，其中，可以肯定地說，

39
00:02:23,640 --> 00:02:30,540
相當雄心勃勃地做，如果僅在短短3個月期間，通常學期的課程。

40
00:02:30,540 --> 00:02:34,190
但是，這些學生將被處​​理同樣的問題集，觀看相同的內容，

41
00:02:34,190 --> 00:02:36,350
具有相同的短褲和訪問。

42
00:02:36,350 --> 00:02:38,990
因此，認識到我們都是真的，在此一併。

43
00:02:38,990 --> 00:02:42,360
的CS50x的最終目標之一是不只是為了讓盡可能多的人

44
00:02:42,360 --> 00:02:45,720
終點線，給他們新發現的計算機科學的理解

45
00:02:45,720 --> 00:02:49,000
和編程，但也讓他們有這樣的經驗共享。

46
00:02:49,000 --> 00:02:52,010
50在校園的定義特徵之一，我們希望，

47
00:02:52,010 --> 00:02:56,260
這種共同體驗，是好還是壞，有時，

48
00:02:56,260 --> 00:02:59,480
但具有這些人打開到左邊和右邊，

49
00:02:59,480 --> 00:03:01,830
和辦公時間的黑客馬拉松和公平。

50
00:03:01,830 --> 00:03:04,560
這一點做起來難，在網上與人的人，

51
00:03:04,560 --> 00:03:10,580
但CS50x有史以來第一次CS50世博會，將於4月結束

52
00:03:10,580 --> 00:03:13,630
這將是我們的想法的網游改編的公平

53
00:03:13,630 --> 00:03:18,250
這些成千上萬的學生都將被邀請提交1  -  2分鐘的視頻，

54
00:03:18,250 --> 00:03:22,480
無論是他們最後的項目或視頻截屏揮手打招呼

55
00:03:22,480 --> 00:03:24,490
談論他們的項目和演示，

56
00:03:24,490 --> 00:03:27,610
很像你的前任在這裡做在校園內的公平，

57
00:03:27,610 --> 00:03:31,400
所以，到學期結束，是希望能夠有一個全球性的展覽

58
00:03:31,400 --> 00:03:37,080
的的CS50x學生的最終項目，就像等待著你這個月在這裡的校園生活。

59
00:03:37,080 --> 00:03:39,680
所以，在未來幾個月內。

60
00:03:39,680 --> 00:03:43,640
>> 10萬名學生，不過，隨著而來的，是需要一些更多的CA。

61
00:03:43,640 --> 00:03:47,590
既然你們正在開闢的線索，並採取CS50

62
00:03:47,590 --> 00:03:51,630
數週提前EDX的人對這種物質的釋放，

63
00:03:51,630 --> 00:03:55,330
實現我們很樂意涉及許多我們自己的學生盡可能的這一舉措，

64
00:03:55,330 --> 00:03:58,720
在學期期間以及今年冬天和今年春天。

65
00:03:58,720 --> 00:04:01,620
所以，如果你想參與CS50x的，

66
00:04:01,620 --> 00:04:07,450
特別參加上的EDX CS50x討論，版本的CS50討論的，

67
00:04:07,450 --> 00:04:10,140
你們中許多人已經在校園內使用，網上公告板，

68
00:04:10,140 --> 00:04:13,040
請做頭，URL，讓我們知道你是誰，

69
00:04:13,040 --> 00:04:16,450
因為我們很樂意建立一個團隊的學生和工作人員和教師的一致好評

70
00:04:16,450 --> 00:04:19,630
在校園簡單地打順和幫助。

71
00:04:19,630 --> 00:04:21,720
當他們看到一個問題，這是他們熟悉的，

72
00:04:21,720 --> 00:04:25,320
你聽到學生報告一些錯誤的地方，在一些國家，在互聯網上，

73
00:04:25,320 --> 00:04:27,450
而且鈴響了，因為你也有同樣的問題

74
00:04:27,450 --> 00:04:32,620
希望在D廳前一段時間，那麼你可以附和和分享自己的經驗。

75
00:04:32,620 --> 00:04:37,300
所以，請不要參加，如果你想。

76
00:04:37,300 --> 00:04:39,360
>> 計算機科學課程在哈佛有一個傳統的位，

77
00:04:39,360 --> 00:04:44,730
CS50其中，有一些服裝，有些衣服，你可以自豪地穿

78
00:04:44,730 --> 00:04:49,090
在學期結束，頗為自豪地說，你完成CS50

79
00:04:49,090 --> 00:04:51,830
並把CS50之類的，我們一直在努力讓學生參與

80
00:04:51,830 --> 00:04:54,540
在這個過程中盡可能多，因此我們邀請，

81
00:04:54,540 --> 00:04:56,900
在這段時間的學期，學生提交設計

82
00:04:56,900 --> 00:04:59,330
使用Photoshop或任何工具，選擇你想使用

83
00:04:59,330 --> 00:05:02,330
如果你是一個設計師，提交設計T-卹和運動衫

84
00:05:02,330 --> 00:05:06,100
和太陽傘和小頭巾的狗，我們現在等。

85
00:05:06,100 --> 00:05:09,370
一切是那麼的 - 獎每年展出

86
00:05:09,370 --> 00:05:12,700
過程的網站store.cs50.net。

87
00:05:12,700 --> 00:05:15,790
一切都按成本有銷售，但該網站只運行

88
00:05:15,790 --> 00:05:18,330
並允許人們選擇自己喜歡的顏色和設計。

89
00:05:18,330 --> 00:05:20,420
所以，我想我們只是分享一些去年的設計

90
00:05:20,420 --> 00:05:25,130
在網站上，除了這一個在這裡，它是每年的傳統。

91
00:05:25,130 --> 00:05:29,410
“每一天我在賽格Faultn的”是去年的意見書，

92
00:05:29,410 --> 00:05:32,290
這仍然是校友。

93
00:05:32,290 --> 00:05:35,820
我們在這其中，“CS50，成立於1989年。”

94
00:05:35,820 --> 00:05:39,010
Bowdens，羅布，是去年非常流行。

95
00:05:39,010 --> 00:05:43,480
“鮑登隊”誕生了，這個設計提交，當中最暢銷的。

96
00:05:43,480 --> 00:05:49,040
由於這一個在這裡。很多人有“鮑登發燒”的銷售日誌。

97
00:05:49,040 --> 00:05:52,650
實現，這可能是你的設計，在互聯網上。

98
00:05:52,650 --> 00:05:57,510
在這個問題上的下一個問題的更多細節設置來。

99
00:05:57,510 --> 00:06:00,330
>> 工具：你已經有一些風險，並希望現在

100
00:06:00,330 --> 00:06:02,350
與GDB的一些實踐經驗，

101
00:06:02,350 --> 00:06:04,570
這是，當然，一個調試器，讓您操作

102
00:06:04,570 --> 00:06:09,500
你的程序在一個相當低的水平，做什麼樣的事情呢？

103
00:06:09,500 --> 00:06:13,030
GDB讓你做什麼呢？

104
00:06:13,030 --> 00:06:15,030
是嗎？給我的東西。 [學生回答，不知所云]

105
00:06:15,030 --> 00:06:18,120
好。步入功能，讓你不只是要鍵入run

106
00:06:18,120 --> 00:06:22,310
並有計劃通過其整體的打擊，打印出來的東西輸出到標準輸出。

107
00:06:22,310 --> 00:06:25,190
相反，你可以通過線的步驟，方法是鍵入下一個

108
00:06:25,190 --> 00:06:30,300
走行線或步驟潛入功能，通常是你寫的。

109
00:06:30,300 --> 00:06:35,240
什麼GDB讓你這樣做嗎？是嗎？ [學生回答，不知所云]

110
00:06:35,240 --> 00:06:38,100
打印變量。所以，如果你想你的程序裡面做了一點反省

111
00:06:38,100 --> 00:06:41,500
而不必訴諸printf語句寫入所有的地方，

112
00:06:41,500 --> 00:06:44,600
你可以只打印一個變量或顯示一個變量。

113
00:06:44,600 --> 00:06:46,710
像GDB調試器，你還能做什麼呢？

114
00:06:46,710 --> 00:06:49,170
[學生回答，不知所云]

115
00:06:49,170 --> 00:06:52,080
沒錯。您可以設置斷點，你可以說破的執行

116
00:06:52,080 --> 00:06:54,020
在主要功能或函數foo。

117
00:06:54,020 --> 00:06:56,800
你可以說123線中斷執行。

118
00:06:56,800 --> 00:06:58,950
斷點是一個真正強大的技術

119
00:06:58,950 --> 00:07:01,110
因為如果你有一個一般意義上的你的問題所在

120
00:07:01,110 --> 00:07:05,360
可能的是，你不浪費時間的程序全部通過加強。

121
00:07:05,360 --> 00:07:08,250
基本上，您可以在那裡跳，然後開始打字 - 

122
00:07:08,250 --> 00:07:10,970
步進通過它與步驟或下一個或等。

123
00:07:10,970 --> 00:07:14,340
但類似GDB勾的是，它可以幫助你的人，

124
00:07:14,340 --> 00:07:16,940
找到你的問題，並找出你的錯誤。

125
00:07:16,940 --> 00:07:19,470
它並不一定能找到他們這麼大的給你。

126
00:07:19,470 --> 00:07:23,070
>> 因此，我們推出了一天style50，這是一個簡短的命令行工具

127
00:07:23,070 --> 00:07:27,500
嘗試的樣式代碼比你多一點點乾淨的人，可能會做的事。

128
00:07:27,500 --> 00:07:29,530
但是，也真的是只是一個審美的東西。

129
00:07:29,530 --> 00:07:34,110
但事實證明，有這樣的工具，稱為Valgrind的是多了幾分神秘的使用。

130
00:07:34,110 --> 00:07:36,860
乍看之下，它的輸出是十惡不赦神秘的。

131
00:07:36,860 --> 00:07:39,420
但它的奇妙有用的，特別是現在，我們在這個詞的一部分，

132
00:07:39,420 --> 00:07:43,080
在你開始使用malloc和動態內存分配。

133
00:07:43,080 --> 00:07:45,420
事情都可能很快真的，真的錯了。

134
00:07:45,420 --> 00:07:49,320
因為如果你忘記釋放你的記憶，你解引用NULL指針，

135
00:07:49,320 --> 00:07:55,770
或者你解引用一些垃圾的指針，什麼是典型的症狀，結果呢？

136
00:07:55,770 --> 00:07:59,470
賽格故障。這個核心，你會得到一定數目的字節或兆字節的文件

137
00:07:59,470 --> 00:08:02,990
表示該程序的內存狀態時墜毀，

138
00:08:02,990 --> 00:08:05,730
但你的程序，最終段故障，分割故障，

139
00:08:05,730 --> 00:08:08,450
這意味著什麼糟糕的事情發生幾乎總是與

140
00:08:08,450 --> 00:08:11,750
記憶體相關的錯誤，你的某個地方制定。

141
00:08:11,750 --> 00:08:14,100
因此，Valgrind的幫助你找到這樣的事情。

142
00:08:14,100 --> 00:08:17,720
這是一個工具，你運行，如GDB，你編譯你的程序後，

143
00:08:17,720 --> 00:08:20,330
但不是直接運行你的程序，你運行Valgrind的

144
00:08:20,330 --> 00:08:23,960
傳遞給你的程序，只是像你這樣的GDB。

145
00:08:23,960 --> 00:08:26,220
現在，使用，以獲得最佳的輸出類型，

146
00:08:26,220 --> 00:08:30,410
是有點長，所以在屏幕的頂部在那裡你會看到Valgrind的-V。

147
00:08:30,410 --> 00:08:35,350
“-V”幾乎普遍意味著冗長的，當你在Linux計算機上使用程序。

148
00:08:35,350 --> 00:08:38,770
因此，這意味著你可能會比默認情況下，吐出更多的數據。

149
00:08:38,770 --> 00:08:45,510
“ - 洩漏檢查十足。”這只是說檢查所有可能的內存洩漏，

150
00:08:45,510 --> 00:08:49,430
錯誤，我可能會。這一點，也與Linux程序，是一種常見的範例。

151
00:08:49,430 --> 00:08:52,710
一般來說，如果你有一個命令行參數，這是一個“開關”，

152
00:08:52,710 --> 00:08:55,830
這應該改變程序的行為，它是一個單一的字母，

153
00:08:55,830 --> 00:09:00,310
它的-V，但如果這就是切換，只需通過設計的程序員，

154
00:09:00,310 --> 00:09:05,150
是一個完整的字或者一組字，啟動命令行參數 - 。

155
00:09:05,150 --> 00:09:08,190
這些都只是人的慣例，但你會看到他們越來越多地。

156
00:09:08,190 --> 00:09:12,410
然後，最後，“a.out格式”是在這個特定的例子中的程序的任意名稱。

157
00:09:12,410 --> 00:09:14,640
這裡的一些有代表性的輸出。

158
00:09:14,640 --> 00:09:22,890
>> 在我們看這可能意味著什麼，讓我過去在這裡的代碼片段。

159
00:09:22,890 --> 00:09:26,390
讓我感動了這一點的方式，即將推出，

160
00:09:26,390 --> 00:09:32,120
讓我們來看看在memory.c，這是這短短的例子。

161
00:09:32,120 --> 00:09:36,290
因此，在這個程序中，讓我放大的功能和問題。

162
00:09:36,290 --> 00:09:39,430
我們有一個main函數中調用一個函數，F，

163
00:09:39,430 --> 00:09:45,590
然後什麼f進行，稍有技術的英語嗎？

164
00:09:45,590 --> 00:09:49,760
什麼f繼續做嗎？

165
00:09:49,760 --> 00:09:53,680
怎麼樣，我會與第20行開始，恆星的位置並不重要，

166
00:09:53,680 --> 00:09:56,720
，但我會是一致的最後一次演講。

167
00:09:56,720 --> 00:09:59,910
什麼是第20行為我們做什麼？在左手側。我們將打破它進一步下降。

168
00:09:59,910 --> 00:10:02,410
詮釋：什麼是幹什麼的？

169
00:10:02,410 --> 00:10:04,940
好吧。它聲明一個指針，現在讓我們更技術。

170
00:10:04,940 --> 00:10:10,230
是什麼意思，很具體，聲明一個指針呢？別人嗎？

171
00:10:10,230 --> 00:10:15,050
是嗎？ [學生回答，難以理解太遠。

172
00:10:15,050 --> 00:10:17,060
所以，你正在閱讀的右手邊等號。

173
00:10:17,060 --> 00:10:20,290
讓我們把注意力集中在左側，剛剛於int * X。

174
00:10:20,290 --> 00:10:24,700
“聲明”的指針，但現在我們來看看在更深的這一定義。

175
00:10:24,700 --> 00:10:28,330
這是什麼具體的，技術上是什麼意思？是嗎？

176
00:10:28,330 --> 00:10:31,940
[學生回答，不知所云]

177
00:10:31,940 --> 00:10:35,090
好吧。準備保存內存中的地址。

178
00:10:35,090 --> 00:10:40,680
好。讓我們進一步採取這一步，它聲明了一個變量x，這是32位。

179
00:10:40,680 --> 00:10:44,440
我知道這是32位，因為 - ？

180
00:10:44,440 --> 00:10:47,390
這不是因為它是一個int，因為它是一個指針，在這種情況下。

181
00:10:47,390 --> 00:10:49,650
巧合的是，它是一個和同一個int，

182
00:10:49,650 --> 00:10:51,970
但事實上，有明星，有指這是一個指針

183
00:10:51,970 --> 00:10:57,300
在家電，與許多計算機中，但不是所有的，指針是32位。

184
00:10:57,300 --> 00:11:01,850
在更現代化的硬件，如最新的Mac電腦，最新的電腦，你可能有64位指針，

185
00:11:01,850 --> 00:11:04,160
但在家電，這些東西都是32位的。

186
00:11:04,160 --> 00:11:08,380
因此，我們將標準化這一點。更具體的是，故事的結局如下：

187
00:11:08,380 --> 00:11:10,820
我們的“聲明”指針，這是什麼意思呢？

188
00:11:10,820 --> 00:11:12,810
我們準備存放的內存地址。

189
00:11:12,810 --> 00:11:15,530
這是什麼意思呢？

190
00:11:15,530 --> 00:11:19,810
我們創建了一個變量x 32位

191
00:11:19,810 --> 00:11:23,810
不久將存儲的地址的整數。

192
00:11:23,810 --> 00:11:26,470
這是大概準確的，我們可以得到的。

193
00:11:26,470 --> 00:11:31,810
這是向前邁進簡化了世界，只說聲明一個指向名為x。

194
00:11:31,810 --> 00:11:35,380
聲明一個指針，但認識和理解到底發生了

195
00:11:35,380 --> 00:11:38,490
甚至在短短的幾個字符。

196
00:11:38,490 --> 00:11:42,040
>> 現在，這幾乎是一點點變得更容易，即使它是一個較長的表達式。

197
00:11:42,040 --> 00:11:48,160
那麼，是什麼做的，現在的突出“的malloc（10 *表示sizeof（int））;”是嗎？

198
00:11:48,160 --> 00:11:52,350
[學生回答，不知所云]

199
00:11:52,350 --> 00:11:58,250
好。我要了。它分配的內存塊的十個整數。

200
00:11:58,250 --> 00:12:02,190
現在讓我們略深潛水，它是一大塊的十個整數的內存分配。

201
00:12:02,190 --> 00:12:05,390
什麼是malloc的返回呢？

202
00:12:05,390 --> 00:12:10,390
這個塊的地址，或更具體而言，該塊的第一個字節的地址。

203
00:12:10,390 --> 00:12:14,080
我又如何，程序員，知道在哪裡，內存塊的結束？

204
00:12:14,080 --> 00:12:18,340
我知道，這是連續的。定義的malloc，給你一個連續的內存塊。

205
00:12:18,340 --> 00:12:21,240
無間隙。您可以訪問該塊中的每個字節，

206
00:12:21,240 --> 00:12:26,760
背靠背回來了，但我怎麼知道是這個內存塊的結束嗎？

207
00:12:26,760 --> 00:12:28,850
當你使用malloc嗎？ [學生回答，不知所云]好。

208
00:12:28,850 --> 00:12:30,670
你不知道。你要記住。

209
00:12:30,670 --> 00:12:35,960
我一定要記住，我用的值是10，我什至不似乎都做了，在這裡。

210
00:12:35,960 --> 00:12:41,000
但責任完全在我身上。 STRLEN，我們已經變得稍微依賴於字符串，

211
00:12:41,000 --> 00:12:45,860
不僅是因為本公約的\ 0

212
00:12:45,860 --> 00:12:48,840
這種特殊的空字符，NUL，在字符串的結尾。

213
00:12:48,840 --> 00:12:51,740
這並不持有的只是任意的內存塊。

214
00:12:51,740 --> 00:12:58,590
這是給你的。因此，第20行，然後，分配的內存塊

215
00:12:58,590 --> 00:13:02,590
可以存儲10的整數，並且其存儲的第一個字節的地址

216
00:13:02,590 --> 00:13:05,610
該塊內存中的變量x。

217
00:13:05,610 --> 00:13:11,140
埃爾戈，這是一個指針。所以，不幸的是，第21行是一個錯誤。

218
00:13:11,140 --> 00:13:16,110
但首先，它是什麼做的？說店在位置10，0索引，

219
00:13:16,110 --> 00:13:19,480
名為x的值為0的內存塊。

220
00:13:19,480 --> 00:13:21,510
>> 因此，注意兩件事情是怎麼回事。

221
00:13:21,510 --> 00:13:25,420
即使x是一個指針，記得幾個星期前

222
00:13:25,420 --> 00:13:29,440
你仍然可以使用陣列式方括號。

223
00:13:29,440 --> 00:13:36,180
因為這實際上是簡單的記法更神秘的前瞻性指針的算術運算。

224
00:13:36,180 --> 00:13:40,320
在這裡我們會做這樣的事情：地址x，移動10個點，

225
00:13:40,320 --> 00:13:44,550
然後去那裡的地址存儲在該位置。

226
00:13:44,550 --> 00:13:48,090
但坦率地說，這僅僅是殘酷的，並得到舒適的。

227
00:13:48,090 --> 00:13:52,900
因此，世界上通常使用方括號只是因為它是更人性化的閱讀。

228
00:13:52,900 --> 00:13:55,140
但是，這到底發生了什麼引擎蓋下的;

229
00:13:55,140 --> 00:13:58,190
x是一個地址，而不是一個數組，每本身。

230
00:13:58,190 --> 00:14:02,410
因此，這是存儲0 10英寸x位置。

231
00:14:02,410 --> 00:14:06,120
這是為什麼不好？是嗎？

232
00:14:06,120 --> 00:14:17,370
[學生回答，不知所云]沒錯。

233
00:14:17,370 --> 00:14:21,100
我們只分配了10整數，但我們從0數C語言編程時，

234
00:14:21,100 --> 00:14:25,690
所以你必須為0 1 2 3 4 5 6 7 8 9，但不為10的訪問。

235
00:14:25,690 --> 00:14:30,270
因此，無論是程序要賽格故障或事實並非如此。

236
00:14:30,270 --> 00:14:32,900
但是，我們真的不知道，這是一個不確定的行為。

237
00:14:32,900 --> 00:14:35,600
這真的取決於我們是否得到幸運。

238
00:14:35,600 --> 00:14:40,650
如果原來的操作系統，如果我不介意使用額外的字節，

239
00:14:40,650 --> 00:14:43,360
即使它不給我，我的程序可能不會崩潰。

240
00:14:43,360 --> 00:14:46,780
它的原料，它的馬車，但你可能看不到症狀，

241
00:14:46,780 --> 00:14:48,960
您可能會看到它在一段時間內只有一次。

242
00:14:48,960 --> 00:14:51,230
但現實的情況是，錯誤，其實是有。

243
00:14:51,230 --> 00:14:54,320
它的確是有問題的，如果你寫了一個程序，你想要是正確的，

244
00:14:54,320 --> 00:14:58,840
你賣的程序的人都在用，每一次在一段時間內崩潰

245
00:14:58,840 --> 00:15:02,450
因為，當然，這是不好的。事實上，如果你有一個Android手機或iPhone

246
00:15:02,450 --> 00:15:05,550
你下載的應用程序，這些天，如果你曾經有過一個應用程序退出，

247
00:15:05,550 --> 00:15:10,040
突然消失，幾乎總是一些與內存相關的問題的結果，

248
00:15:10,040 --> 00:15:12,830
程序員搞砸了，並取消引用指針

249
00:15:12,830 --> 00:15:18,670
他或她不應該有，和iOS或Android的結果是完全中止程序

250
00:15:18,670 --> 00:15:23,080
而不是風險不確定的行為或某種安全漏洞。

251
00:15:23,080 --> 00:15:25,950
>> 這個計劃除了這一個，還有另外一個錯誤。

252
00:15:25,950 --> 00:15:30,180
還有什麼我搞砸了這個項目？

253
00:15:30,180 --> 00:15:32,740
我還沒有練什麼我傳福音。是嗎？

254
00:15:32,740 --> 00:15:34,760
[學生回答，不知所云]好。

255
00:15:34,760 --> 00:15:36,880
我還沒有釋放的內存。因此，經驗法則

256
00:15:36,880 --> 00:15:43,150
必須隨時調用malloc，你必須調用完成後，使用該內存。

257
00:15:43,150 --> 00:15:45,610
現在，當我將要釋放內存呢？

258
00:15:45,610 --> 00:15:49,780
也許，我會假設這第一行是正確的，要做到這一點。

259
00:15:49,780 --> 00:15:55,710
例如，因為我不能做到這一點在這裡。為什麼呢？

260
00:15:55,710 --> 00:15:57,860
剛出來的範圍。因此，即使我們談論的指針，

261
00:15:57,860 --> 00:16:04,830
這是一個星期2或3個問題，其中x是僅在範圍內的大括號，它被宣布。

262
00:16:04,830 --> 00:16:11,000
所以，你絕對不能釋放它。我唯一​​的機會，以釋放後，大約是21行。

263
00:16:11,000 --> 00:16:15,170
這是一個相當簡單的程序，它是相當容易，一旦你種你的心包裹

264
00:16:15,170 --> 00:16:17,870
周圍有什麼程序在做，其中的錯誤。

265
00:16:17,870 --> 00:16:20,500
而且，即使你沒有看到它在第一，希望它現在有點明顯

266
00:16:20,500 --> 00:16:23,870
這些錯誤很容易地解決，很容易實現。

267
00:16:23,870 --> 00:16:28,720
但是，當一個程序長超過12行，50行，100行，

268
00:16:28,720 --> 00:16:31,150
步行通過您的代碼行，想通過它在邏輯上，

269
00:16:31,150 --> 00:16:35,110
是可能的，但不是特別有趣的事情，不斷地尋找錯誤，

270
00:16:35,110 --> 00:16:38,340
，它也是很難做到的，這就是為什麼這樣的工具Valgrind的存在。

271
00:16:38,340 --> 00:16:40,900
讓我繼續這樣做：讓我打開我的終端窗口，

272
00:16:40,900 --> 00:16:45,400
讓我不只是運行內存，因為內存似乎是罰款。

273
00:16:45,400 --> 00:16:49,180
我得到幸運。去，額外的字節陣列的結尾

274
00:16:49,180 --> 00:16:51,060
似乎不成為問題太多。

275
00:16:51,060 --> 00:16:56,370
但是，讓我儘管如此，做一個理智的檢查，這只是意味著要檢查

276
00:16:56,370 --> 00:16:58,320
這是否實際上是正確的。

277
00:16:58,320 --> 00:17:04,690
>> 因此，讓我們做的valgrind-V  - 洩漏檢查=完全​​，

278
00:17:04,690 --> 00:17:07,520
然後在這種情況下的程序的名稱是存儲器，而不是a.out的。

279
00:17:07,520 --> 00:17:10,760
所以，讓我繼續這樣做。按下回車鍵。

280
00:17:10,760 --> 00:17:14,109
親愛的上帝。這是它的輸出，這就是我前面提到的。

281
00:17:14,109 --> 00:17:17,550
但是，如果你學習閱讀的廢話，

282
00:17:17,550 --> 00:17:20,760
這是診斷輸出，是不是很有趣。

283
00:17:20,760 --> 00:17:24,829
你的眼睛真正要尋找的是沒有提到的錯誤或無效的。

284
00:17:24,829 --> 00:17:26,800
建議問題的詞。

285
00:17:26,800 --> 00:17:29,340
事實上，讓我們看看會發生什麼錯在這裡。

286
00:17:29,340 --> 00:17:35,230
我有某種形式的一個總結，“在使用中在出口處：1塊40個字節。”

287
00:17:35,230 --> 00:17:38,750
我真的不知道塊還沒有，但40字節

288
00:17:38,750 --> 00:17:41,260
其實感覺我可以找出其中，來自。

289
00:17:41,260 --> 00:17:45,030
40個字節。為什麼是40個字節在出口中使用嗎？

290
00:17:45,030 --> 00:17:48,780
更具體地，如果我們向下滾動這裡，

291
00:17:48,780 --> 00:17:54,520
為什麼我肯定失去了40個字節？是嗎？

292
00:17:54,520 --> 00:17:59,520
[學生回答，不知所云]完美。是的，沒錯。

293
00:17:59,520 --> 00:18:03,540
有10的整數，和每個人是4位或32位的大小，

294
00:18:03,540 --> 00:18:08,300
所以我已經失去了精確的40個字節，因為，你的建議，我並沒有所謂的自由。

295
00:18:08,300 --> 00:18:13,460
這是一個錯誤，現在就讓我們來看看遠一點，看到旁邊，

296
00:18:13,460 --> 00:18:16,900
“無效的寫大小為4。”現在這是什麼？

297
00:18:16,900 --> 00:18:21,150
這裡地址是什麼基準符號，顯然是嗎？

298
00:18:21,150 --> 00:18:23,640
這是十六進制的，任何時候你看到一個數字，以0x開頭，

299
00:18:23,640 --> 00:18:29,410
這意味著我們回來的路上，我想，問題的pset 0的部分，十六進制，

300
00:18:29,410 --> 00:18:34,090
這是剛剛做的熱身運動，十進制轉換為十六進制，二進制等等。

301
00:18:34,090 --> 00:18:39,220
十六進制，只是人的慣例，通常用來表示指針

302
00:18:39,220 --> 00:18:41,570
或者，更普遍的是，地址。這只是一個慣例，

303
00:18:41,570 --> 00:18:45,340
因為這是一個有點更容易閱讀，這是一個小更緊湊，比什麼是小數，

304
00:18:45,340 --> 00:18:47,720
二進制文件是無用的為大多數人類使用。

305
00:18:47,720 --> 00:18:50,840
所以，現在這是什麼意思呢？嗯，它看起來像有一個無效的寫

306
00:18:50,840 --> 00:18:54,480
大小為4的第21行上的memory.c。

307
00:18:54,480 --> 00:18:59,180
所以，讓我們回到第21行，而事實上，這裡是無效的寫。

308
00:18:59,180 --> 00:19:02,640
因此，Valgrind是不會完全握住我的手，告訴我的解決辦法是什麼，

309
00:19:02,640 --> 00:19:05,520
但它是檢測，我做了一個無效的寫。

310
00:19:05,520 --> 00:19:08,800
我接觸的4個字節，我不應該，顯然這是因為，

311
00:19:08,800 --> 00:19:13,960
正如你指出的，我做的[10]而不是[9]最大限度地

312
00:19:13,960 --> 00:19:16,660
或[0]或介於兩者之間。

313
00:19:16,660 --> 00:19:19,690
使用Valgrind，實現任何時間，你現在寫一個程序

314
00:19:19,690 --> 00:19:24,190
使用指針和使用內存，和malloc更具體地說，

315
00:19:24,190 --> 00:19:27,080
肯定的習慣運行此長

316
00:19:27,080 --> 00:19:30,890
但很容易複製和粘貼命令的Valgrind的

317
00:19:30,890 --> 00:19:32,650
看在那裡，如果有一些錯誤。

318
00:19:32,650 --> 00:19:34,820
這將是壓倒性的，每次你看到的輸出，

319
00:19:34,820 --> 00:19:39,430
只是解析視覺上所有的輸出，看看你看到提到的錯誤

320
00:19:39,430 --> 00:19:43,190
或警告無效或丟失。

321
00:19:43,190 --> 00:19:46,200
任何的話聽起來像你搞砸了某個地方。

322
00:19:46,200 --> 00:19:48,580
所以，意識到這是一個新的工具，在您的工具箱。

323
00:19:48,580 --> 00:19:51,270
>> 現在，在週一，我們有一大堆的人來這裡

324
00:19:51,270 --> 00:19:53,150
並代表一個鏈接的列表的概念。

325
00:19:53,150 --> 00:20:00,970
我們介紹了鍊錶作為一個解決什麼問題？

326
00:20:00,970 --> 00:20:04,590
是嗎？ [學生回答，不知所云]好。

327
00:20:04,590 --> 00:20:06,530
數組不能有內存添加到他們。

328
00:20:06,530 --> 00:20:09,440
如果你分配一個大小為10的數組，這就是你所得到的。

329
00:20:09,440 --> 00:20:13,690
你可以調用一個函數，如果你像realloc的最初叫的malloc，

330
00:20:13,690 --> 00:20:17,580
，並且可以試種陣列朝向它的結束，如果有足夠的空間

331
00:20:17,580 --> 00:20:21,610
沒有其他人使用，而且，如果有，它會找到你一個更大的塊其他地方。

332
00:20:21,610 --> 00:20:25,040
然後將所有的這些字節複製到新的數組。

333
00:20:25,040 --> 00:20:28,310
這聽起來像一個非常正確的解決方案。

334
00:20:28,310 --> 00:20:34,790
這是為什麼缺乏吸引力？

335
00:20:34,790 --> 00:20:36,940
我的意思是，人類已經解決了這個問題。

336
00:20:36,940 --> 00:20:40,710
為什麼我們需要週一鍊錶來解決它？是嗎？

337
00:20:40,710 --> 00:20:44,060
[學生回答，不知所云]這可能需要很長的時間。

338
00:20:44,060 --> 00:20:49,260
事實上，在任何時候，當你調用malloc或realloc或calloc，這又是另外一個，

339
00:20:49,260 --> 00:20:52,470
任何時候，你的程序，所談的操作系統，

340
00:20:52,470 --> 00:20:54,310
你會減慢程序速度下降。

341
00:20:54,310 --> 00:20:57,470
如果你正在做這類的東西在循環中，你真的放緩下來的東西。

342
00:20:57,470 --> 00:21:00,740
你不會注意到這一點的最簡單的“Hello World”類型的程序，

343
00:21:00,740 --> 00:21:04,300
但在更大的計劃，要求操作系統一而再，再而內存

344
00:21:04,300 --> 00:21:07,520
或給它一次又一次的往往不是一件好事。

345
00:21:07,520 --> 00:21:11,210
另外，它只是形式的智力 - 這是一個完全是浪費時間。

346
00:21:11,210 --> 00:21:16,490
為什麼越來越多的內存分配，風險將所有內容複製到新的數組，

347
00:21:16,490 --> 00:21:21,980
如果你有一個選擇，讓你真正需要的，你只有盡可能多的內存分配？

348
00:21:21,980 --> 00:21:24,130
所以在這裡的長處和短處。

349
00:21:24,130 --> 00:21:26,730
現在的長處之一是，我們有活力。

350
00:21:26,730 --> 00:21:29,100
無所謂的內存塊，是免費的，

351
00:21:29,100 --> 00:21:32,070
我只是有點創建這些麵包屑通過指針

352
00:21:32,070 --> 00:21:34,470
我的整個鍊錶串在一起。

353
00:21:34,470 --> 00:21:36,470
但我支付至少一價。

354
00:21:36,470 --> 00:21:40,060
>> 我不得不放棄在獲得鍊錶是什麼？

355
00:21:40,060 --> 00:21:42,470
是嗎？ [學生回答，不知所云]好。

356
00:21:42,470 --> 00:21:45,650
你需要更多的內存。現在我需要為這些指針的空間，

357
00:21:45,650 --> 00:21:47,900
的情況下，這個超級簡單的鍊錶

358
00:21:47,900 --> 00:21:51,410
只要存儲4個字節的整數，這是我們一直在說

359
00:21:51,410 --> 00:21:54,240
，指針為4個字節，所以現在我已經一倍

360
00:21:54,240 --> 00:21:57,290
我只需要存儲此列表的內存量。

361
00:21:57,290 --> 00:21:59,680
但是，這是一個不斷權衡計算機科學

362
00:21:59,680 --> 00:22:03,440
在時間和空間和發展，精力和其他資源。

363
00:22:03,440 --> 00:22:06,630
使用鍊錶的另一個缺點什麼？是嗎？

364
00:22:06,630 --> 00:22:10,150
[學生回答，不知所云]

365
00:22:10,150 --> 00:22:12,600
好。不容易獲得。我們不能再利用

366
00:22:12,600 --> 00:22:15,530
0週的原則，如分而治之。

367
00:22:15,530 --> 00:22:18,220
更具體地，二進制搜索。因為即使我們人類

368
00:22:18,220 --> 00:22:20,400
大致可以看到這個列表的中間，

369
00:22:20,400 --> 00:22:25,840
計算機只知道這個鍊錶開始的地址，稱為第一。

370
00:22:25,840 --> 00:22:28,250
這是為0x123或類似的東西。

371
00:22:28,250 --> 00:22:30,990
而唯一的方式，程序可以找到中間的元素

372
00:22:30,990 --> 00:22:33,350
實際上是搜索整個列表。

373
00:22:33,350 --> 00:22:35,500
即使如此，它的字面搜索整個列表，因為

374
00:22:35,500 --> 00:22:38,950
甚至當你達到的中間元素的指針，

375
00:22:38,950 --> 00:22:42,380
你的計劃，這份名單是不知道多久，潛在的，

376
00:22:42,380 --> 00:22:45,250
直到你擊中結束的時候，你怎麼知道編程的

377
00:22:45,250 --> 00:22:48,600
你在一個鍊錶的結束？

378
00:22:48,600 --> 00:22:51,120
有一個特殊的NULL指針，如此反复，一個慣例。

379
00:22:51,120 --> 00:22:53,870
而不是使用這個指針，我們絕對不希望它是一些垃圾的價值

380
00:22:53,870 --> 00:22:57,750
指向階段的地方，我們希望它是手，NULL，

381
00:22:57,750 --> 00:23:01,530
因此，我們有這個總站在這種數據結構，所以我們知道它在哪裡結束。

382
00:23:01,530 --> 00:23:03,410
>> 如果我們要操作的呢？

383
00:23:03,410 --> 00:23:05,980
我們做了最重要的，這在視覺，與人類，

384
00:23:05,980 --> 00:23:07,630
但如果我們想要做的插入，該怎麼辦呢？

385
00:23:07,630 --> 00:23:12,360
因此，原來的名單是9，17，20，22，29，34。

386
00:23:12,360 --> 00:23:16,730
如果我們想的malloc空間為55號，它的節點，

387
00:23:16,730 --> 00:23:20,730
然後我們要插入55到列表中，就像我們上週一？

388
00:23:20,730 --> 00:23:23,690
如何才能做到這一點呢？那麼，梅艷芳走過來，她基本上走的列表。

389
00:23:23,690 --> 00:23:27,500
她的第一個元素，然後開始下，下，下，下，下一個。

390
00:23:27,500 --> 00:23:29,500
終於擊中了左側的一路下滑

391
00:23:29,500 --> 00:23:34,480
並實現了哦，這是NULL。那麼，什麼指針操作需要做的嗎？

392
00:23:34,480 --> 00:23:37,980
誰的人就結束了，34號，需要提高他的左手

393
00:23:37,980 --> 00:23:46,220
在55點，55需要他們的指點下成為新的NULL終止的左手臂。完成。

394
00:23:46,220 --> 00:23:49,540
很容易插入55到排序的列表。

395
00:23:49,540 --> 00:23:51,800
如何看？

396
00:23:51,800 --> 00:23:55,690
>> 讓我去進取，不斷開拓這裡的一些代碼示例。

397
00:23:55,690 --> 00:23:58,120
我會打開gedit的，讓我第一次打開兩個文件。

398
00:23:58,120 --> 00:24:02,050
一個是list1.h，我只想提醒的是，這是代碼塊

399
00:24:02,050 --> 00:24:04,920
我們用來代表一個節點。

400
00:24:04,920 --> 00:24:13,040
節點具有一個int n和一個指針，只是點稱為下一個在列表中的下一件事。

401
00:24:13,040 --> 00:24:15,450
這是現在的。h文件。為什麼呢？

402
00:24:15,450 --> 00:24:19,090
有這樣的約定，和我們沒有優勢，這是一個巨大的量自己，

403
00:24:19,090 --> 00:24:22,220
但人誰寫printf和其他功能

404
00:24:22,220 --> 00:24:27,150
給作為禮物送給世界所有這些功能編寫一個名為stdio.h中。

405
00:24:27,150 --> 00:24:30,950
然後string.h中，然後有map.h，並有所有這些h文件

406
00:24:30,950 --> 00:24:34,410
期內別人寫的，你可能已經看到或使用。

407
00:24:34,410 --> 00:24:38,470
一般來說，在那些h文件是唯一的東西，如類型定義。

408
00:24:38,470 --> 00:24:42,310
或自定義類型或聲明的常量的聲明。

409
00:24:42,310 --> 00:24:47,890
你不把在頭文件中的函數的實現。

410
00:24:47,890 --> 00:24:50,570
你說，而不是，只是他們的原型。

411
00:24:50,570 --> 00:24:53,050
你把你想分享的東西與他們所需要的世界

412
00:24:53,050 --> 00:24:55,640
為了編譯自己的代碼。因此，只要進入這個習慣，

413
00:24:55,640 --> 00:24:59,110
我們決定做同樣的事情。沒有太多的list1.h

414
00:24:59,110 --> 00:25:02,070
但我們已經把人在世界上可能有興趣的東西，

415
00:25:02,070 --> 00:25:05,030
要使用我們的鏈接列表實現。

416
00:25:05,030 --> 00:25:08,040
現在，在list1.c，我不會去通過這整個事情

417
00:25:08,040 --> 00:25:11,390
因為這是一個有點長，這個程序，但讓我們迅速在提示符下運行。

418
00:25:11,390 --> 00:25:15,720
讓我編list1的，讓我運行list1的，你會看到什麼

419
00:25:15,720 --> 00:25:18,070
我們模擬了一個簡單的小程序，在這裡

420
00:25:18,070 --> 00:25:20,990
這是怎麼回事，讓我來添加和刪除號碼的列表。

421
00:25:20,990 --> 00:25:24,310
所以，讓我去進取型和3型的菜單選項3。

422
00:25:24,310 --> 00:25:27,880
我想插入數字 - 讓我們做的第一個數字，這是9，

423
00:25:27,880 --> 00:25:30,550
現在我告訴我說，的列表現在9。

424
00:25:30,550 --> 00:25:33,760
讓我繼續前進，做的是另一套插入，所以我打選項3。

425
00:25:33,760 --> 00:25:36,760
我要插入什麼號碼？ 17。

426
00:25:36,760 --> 00:25:39,220
輸入。我會做更多的只是一個。

427
00:25:39,220 --> 00:25:41,720
讓我插入22號。

428
00:25:41,720 --> 00:25:45,850
因此，我們已經有了一個初步的鏈接列表，我們剛才在幻燈片的形式。

429
00:25:45,850 --> 00:25:48,740
這是怎麼插入實際發生的事情嗎？

430
00:25:48,740 --> 00:25:52,000
事實上，圖22是現在在列表的末尾。

431
00:25:52,000 --> 00:25:55,050
這樣的故事告訴我們在舞台上週一，剛才扼

432
00:25:55,050 --> 00:25:57,460
必須實際發生的代碼。

433
00:25:57,460 --> 00:25:59,700
讓我們一起來看看。讓我在這個文件中，向下滾動。

434
00:25:59,700 --> 00:26:01,720
我們會掩飾一些的功能，

435
00:26:01,720 --> 00:26:05,630
但我們會去，說，插入功能。

436
00:26:05,630 --> 00:26:11,720
>> 讓我們看一下如何去到這個鍊錶中插入一個新的節點。

437
00:26:11,720 --> 00:26:14,550
名單在哪裡申報？好吧，讓我們滾動的方式在最頂端，

438
00:26:14,550 --> 00:26:19,970
注意到，我基本上宣布鍊錶作為一個單一的指針，這是最初NULL。

439
00:26:19,970 --> 00:26:23,180
所以我用一個全局變量，在一般情況下我們所鼓吹反對

440
00:26:23,180 --> 00:26:25,280
因為它使你的代碼有點亂來維持，

441
00:26:25,280 --> 00:26:29,080
這是一種懶惰的，通常，但它不是懶​​惰，這是沒有錯的，它不壞

442
00:26:29,080 --> 00:26:33,660
如果你的程序的唯一目的是模擬一個鏈接列表。

443
00:26:33,660 --> 00:26:35,460
而這正是我們正在做的。

444
00:26:35,460 --> 00:26:39,100
因此，而不是宣布在主，然後將它傳遞給每一個功能

445
00:26:39,100 --> 00:26:42,640
我們已經寫了這個程序，而不是實現哦，讓我們使全球

446
00:26:42,640 --> 00:26:47,060
因為這項計劃的整個目的是展示一個且只有一個鍊錶。

447
00:26:47,060 --> 00:26:50,700
所以，感覺還可以。下面是我的原型，我們不會通過所有這些，

448
00:26:50,700 --> 00:26:55,800
但我寫的刪除功能，查找功能，插入功能，和移動功能。

449
00:26:55,800 --> 00:26:59,080
但現在，讓我們往回走的插入功能

450
00:26:59,080 --> 00:27:01,490
如何在這裡工作。

451
00:27:01,490 --> 00:27:09,940
插入上線 - 在這裡，我們走了。

452
00:27:09,940 --> 00:27:12,850
插入。因此，它不帶任何參數，因為我們要問

453
00:27:12,850 --> 00:27:15,930
他們要插入的數目這個功能的用戶內部。

454
00:27:15,930 --> 00:27:19,410
但首先，我們準備給他們一些空間。

455
00:27:19,410 --> 00:27:22,050
這是複製並粘貼到其他的例子。

456
00:27:22,050 --> 00:27:25,110
在這種情況下，我們被分配一個int，這一次我們分配一個節點。

457
00:27:25,110 --> 00:27:27,910
我真的不記得有多少個字節的節點，但是這很好。

458
00:27:27,910 --> 00:27:30,460
SIZEOF能明白這一點對我來說。

459
00:27:30,460 --> 00:27:33,340
我為什麼要檢查是否為NULL在第120行嗎？

460
00:27:33,340 --> 00:27:37,530
什麼可能會出錯，在第119行嗎？是嗎？

461
00:27:37,530 --> 00:27:40,530
[學生回答，不知所云]

462
00:27:40,530 --> 00:27:43,440
好。只要可能的情況下，我問了太多的內存

463
00:27:43,440 --> 00:27:47,020
什麼錯誤的，操作系統沒有足夠的字節給我，

464
00:27:47,020 --> 00:27:50,640
所以它的信號盡可能多的返回NULL，如果我不檢查

465
00:27:50,640 --> 00:27:54,710
我只是一味地繼續使用返回的地址，也可能是NULL。

466
00:27:54,710 --> 00:27:58,400
這可能是一些未知的值不是一件好事，除非I  - 

467
00:27:58,400 --> 00:28:00,590
其實不會是一個未知的值。這可能是NULL，所以我不希望

468
00:28:00,590 --> 00:28:02,550
濫用它，，風險提領。

469
00:28:02,550 --> 00:28:07,410
如果出現這種情況，我只是返回，我們會假裝就像我沒有得到任何內存在所有。

470
00:28:07,410 --> 00:28:12,270
>> 否則，我告訴用戶給我一些插入，我呼籲我們的老朋友調用getInt，

471
00:28:12,270 --> 00:28:15,530
然後，這是新的語法，我們（星期一）推出。

472
00:28:15,530 --> 00:28:20,320
“newptr-> N”是指你的地址是由malloc

473
00:28:20,320 --> 00:28:23,490
這代表一個新的節點對象的第一個字節，

474
00:28:23,490 --> 00:28:26,860
然後去到外地，稱為n。

475
00:28:26,860 --> 00:28:35,270
一點點小問題：這是相當於什麼更神秘的代碼行嗎？

476
00:28:35,270 --> 00:28:38,110
我還能這樣寫呢？要採取刺？

477
00:28:38,110 --> 00:28:41,480
[學生回答，不知所云]

478
00:28:41,480 --> 00:28:44,870
好。使用N，但它不是一件簡單的事情，因為這。

479
00:28:44,870 --> 00:28:47,090
我首先需要做什麼？ [學生回答，不知所云]

480
00:28:47,090 --> 00:28:52,730
好。我需要做newptr.n。

481
00:28:52,730 --> 00:28:55,610
因此，這是說，顯然是一個新的指針地址。為什麼呢？

482
00:28:55,610 --> 00:28:59,520
因為它是malloc返回的。 * newptr說：“去那裡”，

483
00:28:59,520 --> 00:29:02,970
然後，一旦你有，那麼你可以使用比較熟悉，N，

484
00:29:02,970 --> 00:29:05,730
但這只是看起來有點難看，特別是如果我們人類要

485
00:29:05,730 --> 00:29:10,360
畫箭頭的指針，所有的時間，世界上有該箭頭符號標準化，

486
00:29:10,360 --> 00:29:12,320
這不完全一樣的事情。

487
00:29:12,320 --> 00:29:16,070
所以，你只能使用 - >符號的東西，左邊是一個指針。

488
00:29:16,070 --> 00:29:18,790
否則，如果它是一個真正的結構，使用，N。

489
00:29:18,790 --> 00:29:25,800
那麼這：為什麼我初始化newptr的 - >下一個到NULL？

490
00:29:25,800 --> 00:29:28,610
我們不希望一個懸空的左手的結束階段。

491
00:29:28,610 --> 00:29:31,630
我們要垂直向下，這意味著列表末尾

492
00:29:31,630 --> 00:29:34,980
可能是在這個節點，所以我們最好確保它是NULL。

493
00:29:34,980 --> 00:29:38,460
而且，在一般情況下，初始化的變量或數據成員和結構

494
00:29:38,460 --> 00:29:40,470
的東西是很好的做法。

495
00:29:40,470 --> 00:29:45,170
只要讓垃圾的存在和繼續存在一般，讓你有麻煩

496
00:29:45,170 --> 00:29:48,650
如果你忘了以後做一些事情。

497
00:29:48,650 --> 00:29:51,590
>> 這裡有一個少數情況下。這又是插入功能，

498
00:29:51,590 --> 00:29:54,930
我檢查的第一件事是，如果該變量被稱為第一，

499
00:29:54,930 --> 00:29:58,240
這個全局變量是NULL，這意味著有沒有鍊錶。

500
00:29:58,240 --> 00:30:02,460
我們沒有插入任何數字，所以它是微不足道的插入此數

501
00:30:02,460 --> 00:30:05,240
到列表中，因為它只是屬於在開始該列表。

502
00:30:05,240 --> 00:30:08,100
因此，這是當Anita只是站著一個人在這兒，假裝

503
00:30:08,100 --> 00:30:11,390
舞台上沒有其他人在這裡，直到我們分配了一個節點，

504
00:30:11,390 --> 00:30:13,940
然後她可以提高她的手，第一次，

505
00:30:13,940 --> 00:30:17,420
如果每個人都來了之後，她在舞台上週一。

506
00:30:17,420 --> 00:30:22,900
現在在這裡，我不得不說這是一個小的檢查，如果新節點的n值

507
00:30:22,900 --> 00:30:27,370
<n的值，在當前的第一個節點，

508
00:30:27,370 --> 00:30:29,930
這意味著有一個鍊錶的開始。

509
00:30:29,930 --> 00:30:32,330
在列表中至少有一個節點，但這個新來的傢伙

510
00:30:32,330 --> 00:30:37,230
屬於在它之前，所以我們需要左右移動的東西。

511
00:30:37,230 --> 00:30:43,450
換句話說，如果該列表已經開始，只是讓我們說，

512
00:30:43,450 --> 00:30:48,100
僅僅是17號，這就是 - 實際上，我們可以做到這一點更清楚。

513
00:30:48,100 --> 00:30:56,010
如果我們開始我們的故事指針在這裡被稱為第一，

514
00:30:56,010 --> 00:30:59,870
它最初是NULL，我們插入了9號，

515
00:30:59,870 --> 00:31:02,510
數字9明顯屬於在開始該列表。

516
00:31:02,510 --> 00:31:07,400
因此，讓我們假裝我們只是malloced的地址或9號，並把它放在這裡。

517
00:31:07,400 --> 00:31:13,170
默認情況下，如果第一個是9，第一種情況下，我們討論的只是意味著我們的角度這傢伙在這裡，

518
00:31:13,170 --> 00:31:15,790
離開這個NULL;現在我們的9號。

519
00:31:15,790 --> 00:31:18,280
我們要插入的下一個數字是17。

520
00:31:18,280 --> 00:31:22,420
17屬於這裡，所以我們將不得不做一些邏輯步通過。

521
00:31:22,420 --> 00:31:26,060
因此，讓我們相反，在我們這樣做，讓我們假設，我們想插入數字8。

522
00:31:26,060 --> 00:31:28,650
>> 所以，只是為方便起見，我在這裡要繪製。

523
00:31:28,650 --> 00:31:30,760
但請記住，malloc的可以把它的大多數地方。

524
00:31:30,760 --> 00:31:33,460
但是，對於圖形的緣故，我準備把它放在這裡。

525
00:31:33,460 --> 00:31:38,440
因此，我假裝剛剛分配的節點8號，默認情況下，這是NULL。

526
00:31:38,440 --> 00:31:42,800
現在有什麼發生？一對夫婦的事情。

527
00:31:42,800 --> 00:31:47,090
（星期一）在舞台上犯這樣的錯誤，我們更新了指針這樣的，

528
00:31:47,090 --> 00:31:51,890
這樣做，然後我們要求 - 我們孤立在舞台上的其他人。

529
00:31:51,890 --> 00:31:54,350
因為你不能做到 - 在這裡操作的順序是很重要的，

530
00:31:54,350 --> 00:31:58,760
因為現在我們已經失去了，只是漂浮在太空中的這個節點9。

531
00:31:58,760 --> 00:32:01,150
因此，這是不正確的方法（星期一）。

532
00:32:01,150 --> 00:32:03,330
我們首先必須做其它的事情。

533
00:32:03,330 --> 00:32:06,280
世界的狀態看起來是這樣的。最初，8個已分配。

534
00:32:06,280 --> 00:32:10,550
什麼的插入8將是一個更好的辦法嗎？

535
00:32:10,550 --> 00:32:14,720
而不是先更新這個指針，只需更新，而不是這一個在這裡。

536
00:32:14,720 --> 00:32:17,720
因此，我們需要把這個NULL字符的代碼行的

537
00:32:17,720 --> 00:32:22,020
成實際的指針，該指針指向節點9，

538
00:32:22,020 --> 00:32:27,970
然後我們就可以安全地改變首先指出這傢伙在這裡。

539
00:32:27,970 --> 00:32:31,330
現在，我們有一個列表，鍊錶，兩個元素。

540
00:32:31,330 --> 00:32:33,580
這是什麼實際上看起來像這裡嗎？

541
00:32:33,580 --> 00:32:36,900
如果我們的代碼，請注意，我已經做了。

542
00:32:36,900 --> 00:32:41,970
我已經說過了newptr，在這個故事中，newptr指著這傢伙。

543
00:32:41,970 --> 00:32:45,520
>> 因此，讓我畫一件事，我應該留下多一點空間。

544
00:32:45,520 --> 00:32:48,540
所以請原諒小的小客廳。

545
00:32:48,540 --> 00:32:52,140
這傢伙叫newptr。

546
00:32:52,140 --> 00:32:57,940
這是變量，我們宣布的幾行，行 - 剛剛25歲以上。

547
00:32:57,940 --> 00:33:03,430
和它的指向到8。所以當我說newptr  - >下，這意味著到結構

548
00:33:03,430 --> 00:33:07,910
被指出在的newptr，所以我們在這裡，去那裡。

549
00:33:07,910 --> 00:33:13,990
箭頭說獲得下一個字段，那麼“=”是說把什麼樣的價值？

550
00:33:13,990 --> 00:33:17,280
這是在什麼樣的價值是在第一的價值？

551
00:33:17,280 --> 00:33:21,930
首先是指向這個節點上，這樣就意味著現在應該在這個節點。

552
00:33:21,930 --> 00:33:25,660
換句話說，看起來雖然是一個荒謬的亂用我的筆跡，

553
00:33:25,660 --> 00:33:28,620
什麼是一個簡單的想法，只是將這些箭頭圍

554
00:33:28,620 --> 00:33:31,560
轉化為代碼，僅這一項襯墊。

555
00:33:31,560 --> 00:33:38,110
存儲在第一位的下一個字段，然後更新第一個實際上是什麼樣的。

556
00:33:38,110 --> 00:33:40,900
讓我們繼續前進，快進一些這方面的，

557
00:33:40,900 --> 00:33:44,220
並期待只在這條尾巴插入。

558
00:33:44,220 --> 00:33:51,210
假如我得到的地步，我發現，一些節點的下一個字段是NULL。

559
00:33:51,210 --> 00:33:53,410
而故事中的一個細節，在這一點上，我掩飾

560
00:33:53,410 --> 00:33:58,170
是，我已經介紹了另一種指針在142行，前身指針。

561
00:33:58,170 --> 00:34:01,320
從本質上講，在這一點上的故事，列表後，獲得長期，

562
00:34:01,320 --> 00:34:04,800
我種需要用兩個手指走，因為如果我走的太遠，

563
00:34:04,800 --> 00:34:08,219
記得在一個單一的長列表，你可以不走回頭路。

564
00:34:08,219 --> 00:34:13,659
因此，這個想法predptr是我的左的手指，newptr的 - 而不是newptr。

565
00:34:13,659 --> 00:34:17,199
另一個指針，這裡是我的手指，我只是種走的列表。

566
00:34:17,199 --> 00:34:22,179
這就是為什麼存在。但是，讓我們只考慮一個簡單的情況下在這裡。

567
00:34:22,179 --> 00:34:26,620
如果該指針的下一個字段是空的，什麼是合乎邏輯的含義嗎？

568
00:34:26,620 --> 00:34:30,840
如果你遍歷這個列表，你打一個NULL指針嗎？

569
00:34:30,840 --> 00:34:35,780
你在列表末尾，這樣的代碼，然後追加一個額外的元素

570
00:34:35,780 --> 00:34:41,230
是一種直觀的將採取該節點的指針為NULL，

571
00:34:41,230 --> 00:34:46,120
因此，這是目前NULL，並改變它，但是，要在新的節點的地址。

572
00:34:46,120 --> 00:34:52,260
所以我們僅僅是畫在代碼中的箭頭，，我們提請在舞台上提高一個人的左手。

573
00:34:52,260 --> 00:34:54,070
>> 而且，我會揮揮手，在目前的情況下，

574
00:34:54,070 --> 00:34:58,020
只是因為我認為這是很容易迷失在這樣的環境中，當我們這樣做，

575
00:34:58,020 --> 00:35:00,600
在列表的中間插入檢查。

576
00:35:00,600 --> 00:35:03,220
但是，僅僅憑直覺，需要做些什麼，如果你想弄清楚

577
00:35:03,220 --> 00:35:06,600
其中一些號碼是屬於中間的是你必須走

578
00:35:06,600 --> 00:35:09,510
使用一個以上的手指，多個指針，

579
00:35:09,510 --> 00:35:12,920
揣摩出它所屬的檢查是元素<當前，

580
00:35:12,920 --> 00:35:15,450
>目前，一旦你找到那個地方，

581
00:35:15,450 --> 00:35:20,400
然後，你做這樣的騙局，你周圍移動指針非常仔細。

582
00:35:20,400 --> 00:35:23,850
的答案，如果你想在自己的家裡，原因通過

583
00:35:23,850 --> 00:35:28,340
歸結只是這兩行代碼，但這些生產線的順序是超級重要的。

584
00:35:28,340 --> 00:35:31,390
因為，如果你把別人的手和提高別人的錯誤的順序，

585
00:35:31,390 --> 00:35:34,580
再次，你可能最終成為孤兒的名單。

586
00:35:34,580 --> 00:35:39,500
總結的尾部插入多個概念，是相對簡單的。

587
00:35:39,500 --> 00:35:42,940
在頭插入也比較簡單，

588
00:35:42,940 --> 00:35:45,580
但這個時候，你需要更新一個額外的指針

589
00:35:45,580 --> 00:35:47,930
擠5號到列表中，

590
00:35:47,930 --> 00:35:51,560
然後在中間插入涉及更加努力，

591
00:35:51,560 --> 00:35:56,130
在正確的位置，非常小心地將20號，

592
00:35:56,130 --> 00:35:58,350
這是在17和22之間。

593
00:35:58,350 --> 00:36:02,700
所以，你需要做這樣的事情有新的節點20點到22點，

594
00:36:02,700 --> 00:36:08,470
然後，哪一個節點的指針，因此需要更新最後？

595
00:36:08,470 --> 00:36:10,630
17，要真正將其插入。

596
00:36:10,630 --> 00:36:14,080
所以，再一次，我要推遲，特別是實施的實際代碼。

597
00:36:14,080 --> 00:36:17,280
>> 乍一看，這是一個有點勢不可擋，但它實際上只是一個無限循環

598
00:36:17,280 --> 00:36:21,770
的循環，循環，循環，循環，而打破，只要你打的NULL指針，

599
00:36:21,770 --> 00:36:24,590
在這一點，你可以做必要的插入。

600
00:36:24,590 --> 00:36:30,960
那麼，這是代表鍊錶插入代碼。

601
00:36:30,960 --> 00:36:34,590
這是種了很多，而且感覺就像我們已經解決了一個問題，

602
00:36:34,590 --> 00:36:36,940
但我們已經推出了另一個。坦率地說，我們已經花了所有時間

603
00:36:36,940 --> 00:36:40,540
大O的Ω和運行時間，試圖解決問題更迅速，

604
00:36:40,540 --> 00:36:43,270
在這裡，我們採取的大倒退，感覺。

605
00:36:43,270 --> 00:36:45,380
然而，如果目標是存儲數據，

606
00:36:45,380 --> 00:36:48,010
那感覺就像聖杯，為我們週一表示，是否真的會

607
00:36:48,010 --> 00:36:50,470
即時存儲的東西。

608
00:36:50,470 --> 00:36:53,930
>> 事實上，假設我們確實放下了一會兒鍊錶

609
00:36:53,930 --> 00:36:56,000
我們，而不是推出一個表的概念。

610
00:36:56,000 --> 00:36:59,110
我們只是覺得一個表作為數組的時刻。

611
00:36:59,110 --> 00:37:03,790
這個數組，這種情況下，這裡有26個元素，從0到25，

612
00:37:03,790 --> 00:37:07,940
假設你需要的存儲塊的名稱：

613
00:37:07,940 --> 00:37:10,350
Alice和Bob和Charlie之類的。

614
00:37:10,350 --> 00:37:12,880
你需要一些數據結構來存儲這些名字。

615
00:37:12,880 --> 00:37:15,000
好了，你可以使用的東西像一個鍊錶

616
00:37:15,000 --> 00:37:20,260
，你可以走之前，Bob和Charlie後，鮑勃列表中插入愛麗絲等等。

617
00:37:20,260 --> 00:37:23,850
而且，事實上，如果你想看到這樣的代碼，順便說一句，

618
00:37:23,850 --> 00:37:27,230
我知道，在list2.h，我們做的正是。

619
00:37:27,230 --> 00:37:30,610
我們不會去通過這個代碼，但是這是第一個例子中的一個變種

620
00:37:30,610 --> 00:37:34,640
引入了一個其他的struct我們以前見過的所謂的學生，

621
00:37:34,640 --> 00:37:40,330
再有什麼實際存儲在鍊錶中是一個指針，指向一個學生結構

622
00:37:40,330 --> 00:37:44,520
而不是一個簡單的小整數n。

623
00:37:44,520 --> 00:37:46,900
所以實現的代碼，涉及到實際的字符串，

624
00:37:46,900 --> 00:37:49,940
但如果目標在手，現在確實是要解決效率問題，

625
00:37:49,940 --> 00:37:53,380
不會是很好，如果我們給一個叫愛麗絲的對象，

626
00:37:53,380 --> 00:37:56,020
我們希望把她一個數據結構的正確位置，

627
00:37:56,020 --> 00:37:58,860
感覺它會是非常好的，只是把愛麗絲，

628
00:37:58,860 --> 00:38:01,180
名稱開頭為A，在第一個位置。

629
00:38:01,180 --> 00:38:05,270
和Bob，他的名字開始的B，在第二個位置。

630
00:38:05,270 --> 00:38:09,580
有了一個數組，或讓我們從一張桌子，一個哈希表，

631
00:38:09,580 --> 00:38:13,650
我們可以這樣做。如果我們有一個“愛麗絲夢遊仙境”的名稱，如，

632
00:38:13,650 --> 00:38:16,700
一個字符串，如愛麗絲，你在哪裡放的-l-I-C-E？

633
00:38:16,700 --> 00:38:20,540
我們需要一個hueristic。我們需要一個函數來採取一些“愛麗絲夢遊仙境”的輸入，比如

634
00:38:20,540 --> 00:38:24,610
並返回一個答案，“把愛麗絲在這個位置。”

635
00:38:24,610 --> 00:38:28,720
而這個函數，這個黑盒子，將被稱為散列函數。

636
00:38:28,720 --> 00:38:32,330
>> 散列函數是一些需要輸入，如“愛麗絲”，

637
00:38:32,330 --> 00:38:38,080
，然後返回給你，通常情況下，其中，在一些數據結構中的數字的位置艾麗斯屬於。

638
00:38:38,080 --> 00:38:40,830
在這種情況下，我們的散列函數應該是相對簡單的。

639
00:38:40,830 --> 00:38:47,510
我們的散列函數應該說，如果你是“愛麗絲”，我應該關心哪些字符？

640
00:38:47,510 --> 00:38:55,660
第一個。因此，我期待在[0]，然後我說，如果[0]字符是A，返回0。

641
00:38:55,660 --> 00:39:01,130
如果是B，則返回1。如果它的C，返回2，等等。

642
00:39:01,130 --> 00:39:05,940
共0指數，這將讓我插入Alice和Bob，這樣查理等等

643
00:39:05,940 --> 00:39:10,960
到這樣的數據結構中。但是，有一個問題。

644
00:39:10,960 --> 00:39:13,060
如果梅艷芳嗎？

645
00:39:13,060 --> 00:39:17,510
我們把安妮塔？她的名字也以字母A開頭，

646
00:39:17,510 --> 00:39:20,330
感覺就像我們對這個問題做了一個更大的爛攤子。

647
00:39:20,330 --> 00:39:24,380
現在，我們有直接的插入，插入固定的時間，到一個數據結構

648
00:39:24,380 --> 00:39:27,100
最壞情況下的，而不是線性的，

649
00:39:27,100 --> 00:39:29,510
但與梅艷芳在這種情況下，我們可以做嗎？

650
00:39:29,510 --> 00:39:34,110
這兩個選項是什麼，真的嗎？是嗎？

651
00:39:34,110 --> 00:39:37,410
[學生回答，不知所云]好吧，所以我們可以有另一個維度。

652
00:39:37,410 --> 00:39:42,320
這是很好的。因此，我們可以建立在三維像我們談論口頭上週一。

653
00:39:42,320 --> 00:39:46,700
在這裡我們可以添加另一個訪問，但沒有，我想保持這個簡單的假設。

654
00:39:46,700 --> 00:39:50,160
這裡的目標是立即有固定時間的訪問，

655
00:39:50,160 --> 00:39:52,170
因此，公司增加太多的複雜性。

656
00:39:52,170 --> 00:39:55,970
其他選項時，試圖將這個數據結構梅艷芳是什麼？是嗎？

657
00:39:55,970 --> 00:39:58,610
[學生回答，不知所云]好。因此，我們可以把其他人都下來，

658
00:39:58,610 --> 00:40:03,040
像查理Bob和Alice引起了下來，然後，我們把梅艷芳，她真的想成為。

659
00:40:03,040 --> 00:40:05,660
>> 當然，現在，這有一個副作用。

660
00:40:05,660 --> 00:40:09,000
可能是有用的，不是因為我們要插入的人一旦這個數據結構

661
00:40:09,000 --> 00:40:11,250
但是，因為我們要檢查，如果他們晚

662
00:40:11,250 --> 00:40:13,600
如果我們想打印出所有的數據結構中的名稱。

663
00:40:13,600 --> 00:40:15,850
我們要做的事情，最終與此數據。

664
00:40:15,850 --> 00:40:20,810
所以，現在我們已經搞砸了，誰的愛麗絲不再，她應該是。

665
00:40:20,810 --> 00:40:23,880
也不是鮑勃，也不是查理。

666
00:40:23,880 --> 00:40:26,060
因此，也許這不是一個好主意。

667
00:40:26,060 --> 00:40:28,830
但事實上，這是一種選擇。我們可能會改變每個人都下來，

668
00:40:28,830 --> 00:40:32,240
心裡很不舒服，梅艷芳來晚了的遊戲，為什麼我們不能只是把梅艷芳

669
00:40:32,240 --> 00:40:35,870
不在這裡，不在這裡，而不是在這裡，我們只是把她一點點在列表中上下。

670
00:40:35,870 --> 00:40:38,680
但是，這個問題再次開始下放。

671
00:40:38,680 --> 00:40:41,630
你也許能夠找到愛麗絲瞬間，她的名字。

672
00:40:41,630 --> 00:40:44,320
和Bob瞬間，查理。但是，然後你看梅艷芳，

673
00:40:44,320 --> 00:40:46,360
你看，嗯，愛麗絲的方式。

674
00:40:46,360 --> 00:40:48,770
好了，讓我查一下下面的愛麗絲。鮑勃是不是梅艷芳。

675
00:40:48,770 --> 00:40:51,850
查理是不是梅艷芳。哦，還有梅艷芳。

676
00:40:51,850 --> 00:40:54,720
如果你繼續搭乘火車，邏輯的方式，

677
00:40:54,720 --> 00:41:00,690
什麼是最壞情況下的運行時間發現或插入到這個新的數據結構梅艷芳？

678
00:41:00,690 --> 00:41:03,280
這是O（n）的，對不對？

679
00:41:03,280 --> 00:41:06,280
因為在最壞的情況下，有愛麗絲，鮑勃，查理。 。 。

680
00:41:06,280 --> 00:41:10,150
一路下跌命名為“Y”的人，所以只有一個點離開。

681
00:41:10,150 --> 00:41:13,950
值得慶幸的是，我們有沒有一個叫“Z”，所以我們把梅艷芳在最底層。

682
00:41:13,950 --> 00:41:16,040
>> 我們還沒有真正解決這個問題。

683
00:41:16,040 --> 00:41:19,890
所以，也許我們需要引入第三維。

684
00:41:19,890 --> 00:41:22,230
而事實證明，如果我們不引進這第三個維度，

685
00:41:22,230 --> 00:41:25,240
我們不能這樣做完美，但聖杯得到

686
00:41:25,240 --> 00:41:28,370
固定時間的插入和動態插入，所以

687
00:41:28,370 --> 00:41:30,960
我們沒有進行硬編碼的大小為26的數組。

688
00:41:30,960 --> 00:41:34,400
我們可以將許多名字，因為我們希望，但讓我們在這裡休息5分鐘

689
00:41:34,400 --> 00:41:38,790
然後做正確。

690
00:41:38,790 --> 00:41:46,020
好的。我的故事，漂亮的人為有

691
00:41:46,020 --> 00:41:48,670
通過選擇愛麗絲，然後Bob，然後查理，然後梅艷芳，

692
00:41:48,670 --> 00:41:51,000
他的名字顯然是要碰撞與愛麗絲。

693
00:41:51,000 --> 00:41:54,120
但我們週一結束的問題是它是如何可能的是

694
00:41:54,120 --> 00:41:56,370
你會得到這些種類的衝突？換言之，

695
00:41:56,370 --> 00:42:00,490
如果我們開始使用此表格的結構，這是真的只是一個數組，

696
00:42:00,490 --> 00:42:02,460
在這種情況下，26個地點，

697
00:42:02,460 --> 00:42:05,740
如果我們的輸入，而不是均勻分佈的，怎麼辦？

698
00:42:05,740 --> 00:42:09,620
這不是人為Alice和Bob和Charlie和David等按字母順序，

699
00:42:09,620 --> 00:42:12,380
它均勻地分佈在從A到Z

700
00:42:12,380 --> 00:42:15,220
>> 也許我們會得到幸運的，我們不會有兩個A或B的

701
00:42:15,220 --> 00:42:17,640
具有非常高的概率，但有人指出，

702
00:42:17,640 --> 00:42:20,730
如果我們廣義這個問題，而不是0到25

703
00:42:20,730 --> 00:42:26,060
但是，例如，從0到364或65，往往是一個典型的一年中的天數，

704
00:42:26,060 --> 00:42:31,170
並提出這樣的問題，“什麼是概率在這個房間裡，我們兩個人有相同的生日嗎？”

705
00:42:31,170 --> 00:42:34,600
它的另一種方式，什麼是概率，我們兩個人有一個名字開頭的嗎？

706
00:42:34,600 --> 00:42:37,190
樣的問題是相同的，但這個地址空間，

707
00:42:37,190 --> 00:42:39,940
本次搜索空間的生日是大的情況下，

708
00:42:39,940 --> 00:42:42,820
因為我們有這麼多天，今年比字母在字母表。

709
00:42:42,820 --> 00:42:44,910
的衝突概率是什麼？

710
00:42:44,910 --> 00:42:48,410
好了，我們可以把這個搞清楚數學相反的方向。

711
00:42:48,410 --> 00:42:50,580
沒有碰撞的概率是什麼？

712
00:42:50,580 --> 00:42:53,970
好了，在這裡說，這表達的概率

713
00:42:53,970 --> 00:42:58,770
如果只有一個人在這個房間裡，他們有一個獨特的生日？

714
00:42:58,770 --> 00:43:01,190
這是100％。因為如果只有一個人在房間裡，

715
00:43:01,190 --> 00:43:03,940
他或她的生日可以是任何365天的一年。

716
00:43:03,940 --> 00:43:08,650
因此，三百六十五分之三百六十五選項給了我一個值為1。

717
00:43:08,650 --> 00:43:11,250
所以，此刻的概率問題是只有1。

718
00:43:11,250 --> 00:43:13,270
但是，如果有一個人在房間裡，

719
00:43:13,270 --> 00:43:16,490
什麼是他們的生日的概率是不同的？

720
00:43:16,490 --> 00:43:20,680
只有364天，忽略閏年，

721
00:43:20,680 --> 00:43:23,580
他們的生日沒有碰撞與其他人。

722
00:43:23,580 --> 00:43:31,920
因此，364/365。如果第三人來，它是363/365，並依此類推。

723
00:43:31,920 --> 00:43:35,790
因此，我們將這些分數相乘，這是越來越小，

724
00:43:35,790 --> 00:43:40,720
弄清楚，我們所有的人都有獨特的生日的概率是多少？

725
00:43:40,720 --> 00:43:43,570
但我們可以，當然，只是這個答案和翻轉

726
00:43:43,570 --> 00:43:47,210
和1負所有這一切，我們最終會得到一個表達

727
00:43:47,210 --> 00:43:51,250
如果你還記得你的數學書的背面，它看起來有點像這樣，

728
00:43:51,250 --> 00:43:54,590
這是更容易理解的圖形。

729
00:43:54,590 --> 00:43:57,820
這裡這個圖形的x軸方向上的數量的生日，

730
00:43:57,820 --> 00:44:02,030
或人與生日，和在y軸上的數量是一個匹配的概率。

731
00:44:02,030 --> 00:44:06,060
這是什麼說的是，如果你有，比方說，甚至，

732
00:44:06,060 --> 00:44:10,860
讓我們選擇像22，23。

733
00:44:10,860 --> 00:44:13,160
如果有22或23人在房間裡，

734
00:44:13,160 --> 00:44:17,100
的概率是那些極少數的兩個人有相同的生日

735
00:44:17,100 --> 00:44:19,560
實際上是超級高，組合性。

736
00:44:19,560 --> 00:44:23,450
50％的機率只有22人，研討會，幾乎一類，

737
00:44:23,450 --> 00:44:25,790
2的那些人有相同的生日。

738
00:44:25,790 --> 00:44:28,520
因為有這麼多的方法，讓你可以有相同的生日。

739
00:44:28,520 --> 00:44:31,110
更糟的是，如果你右手邊的圖表，

740
00:44:31,110 --> 00:44:34,040
的時候，你有一個類，它有58名學生，

741
00:44:34,040 --> 00:44:39,270
2人的生日的概率是超級，超級高，幾乎100％。

742
00:44:39,270 --> 00:44:41,880
現在，這是一種現實生活中的一個有趣的事實。

743
00:44:41,880 --> 00:44:45,850
>> 但所帶來的影響，現在，數據結構和存儲信息

744
00:44:45,850 --> 00:44:51,100
也就是說，假設你有一個漂亮，乾淨，均勻分佈的數據

745
00:44:51,100 --> 00:44:53,650
你有一個足夠大的數組，以適應一堆東西

746
00:44:53,650 --> 00:44:59,360
並不意味著你會得到人們的獨特的地方。

747
00:44:59,360 --> 00:45:03,810
你要去有衝突。所以這個散列的概念，因為它是所謂的，

748
00:45:03,810 --> 00:45:07,450
輸入像“愛麗絲”和按摩以某種方式

749
00:45:07,450 --> 00:45:10,190
然後取回如0或1或2的答案。

750
00:45:10,190 --> 00:45:17,500
從該函數獲取一些輸出正困擾著這個碰撞的概率。

751
00:45:17,500 --> 00:45:19,530
那麼，我們如何處理這些衝突？

752
00:45:19,530 --> 00:45:21,940
那麼，在一種情況下，我們可以採取的想法，建議。

753
00:45:21,940 --> 00:45:25,100
我們就可以轉移倒眾人，或也許，多了幾分簡單，

754
00:45:25,100 --> 00:45:29,870
而不是移動所有的人，讓我們只是梅艷芳的底部備有現貨。

755
00:45:29,870 --> 00:45:32,810
因此，如果Alice是0，鮑勃是1，查理是2，

756
00:45:32,810 --> 00:45:35,260
我們只是把梅艷芳在位置3。

757
00:45:35,260 --> 00:45:38,860
這是一個數據結構稱為線性探測技術。

758
00:45:38,860 --> 00:45:41,310
線性的，因為你走這條線，和你有幾分試探

759
00:45:41,310 --> 00:45:43,640
可用的點的數據結構中。

760
00:45:43,640 --> 00:45:46,210
當然，這種不滿轉化為O（n）。

761
00:45:46,210 --> 00:45:49,590
如果數據結構確實充分，已經有25人，

762
00:45:49,590 --> 00:45:54,120
，然後袁詠儀走來，她結束了在什麼位置Z，這很好。

763
00:45:54,120 --> 00:45:56,540
她仍然適用，我們能找到她。

764
00:45:56,540 --> 00:46:00,100
>> 但是，這是相反的目標，加快東西。

765
00:46:00,100 --> 00:46:02,530
那麼，如果我們不是介紹了這第三個維度？

766
00:46:02,530 --> 00:46:06,400
這種技術通常被稱為單獨的鏈接，或鏈。

767
00:46:06,400 --> 00:46:10,030
是怎樣的一個哈希表，這個表結構，

768
00:46:10,030 --> 00:46:13,450
你的表是一個指針數組。

769
00:46:13,450 --> 00:46:18,230
但是，這些指針指向的是你猜怎麼著？

770
00:46:18,230 --> 00:46:21,970
鍊錶。那麼，如果我們把這些世界最好的嗎？

771
00:46:21,970 --> 00:46:26,500
我們使用數組的初始指標

772
00:46:26,500 --> 00:46:32,070
到的數據結構，這樣我們就可以即刻前往[0] [1]，[30]等等，

773
00:46:32,070 --> 00:46:36,480
但是，我們有一定的靈活性，我們可以適合梅艷芳，愛麗絲和亞當

774
00:46:36,480 --> 00:46:38,630
和任何其他的名稱，

775
00:46:38,630 --> 00:46:43,470
我們，而不是讓其他軸增長到任意。

776
00:46:43,470 --> 00:46:47,340
截至週一，我們終於有鏈接列表，表達能力。

777
00:46:47,340 --> 00:46:49,530
我們可以任意增長數據結構。

778
00:46:49,530 --> 00:46:52,450
另外，我們可以只讓一個巨大的二維數組，

779
00:46:52,450 --> 00:46:57,190
一個2維陣列中的行，但是這將是一個可怕的情況，如果一個

780
00:46:57,190 --> 00:47:01,280
不夠大，更多的人，他的名字恰好開始A.

781
00:47:01,280 --> 00:47:04,200
上帝保佑，我們必須重新分配一個巨大的二維結構

782
00:47:04,200 --> 00:47:06,600
正因為有這麼多的人命名為A，

783
00:47:06,600 --> 00:47:09,480
特別是當有所以幾個人命名為Z東西。

784
00:47:09,480 --> 00:47:12,170
這將是一個非常稀疏的數據結構。

785
00:47:12,170 --> 00:47:15,400
因此，它不是完美的，任何手段，但至少現在我們有能力

786
00:47:15,400 --> 00:47:19,090
Alice或梅艷芳屬於立即找到，

787
00:47:19,090 --> 00:47:21,090
至少在縱軸條款，

788
00:47:21,090 --> 00:47:25,850
然後我們只需要決定把梅艷芳或翹在這個鍊錶。

789
00:47:25,850 --> 00:47:32,480
如果我們不關心排序的事情，如何迅速，我們將愛麗絲成這樣的結構嗎？

790
00:47:32,480 --> 00:47:35,370
這是恆定的時間。我們的指數為[0]，如果沒有一個人的存在，

791
00:47:35,370 --> 00:47:37,550
艾麗斯在該鏈接的列表的開始。

792
00:47:37,550 --> 00:47:40,000
但是，這不是一個大問題。因為如果梅艷芳然後是沿

793
00:47:40,000 --> 00:47:42,160
一些步數後，梅艷芳屬於嗎？

794
00:47:42,160 --> 00:47:45,140
那麼，[0]。面向對象編程。愛麗絲已經在該鏈接的列表。

795
00:47:45,140 --> 00:47:47,760
>> 但是，如果我們不關心這些名稱進行排序，

796
00:47:47,760 --> 00:47:53,580
我們就可以將愛麗絲過來，插入梅艷芳，但即使是恆定的時間。

797
00:47:53,580 --> 00:47:57,010
即使有愛麗絲和亞當和所有這些其他的地名，

798
00:47:57,010 --> 00:47:59,410
它不是真正的轉移他們的身體。為什麼呢？

799
00:47:59,410 --> 00:48:04,090
因為我們剛剛在這裡做的與鍊錶，誰知道，這些節點呢？

800
00:48:04,090 --> 00:48:06,550
所有你必須做的是移動的麵包屑。

801
00:48:06,550 --> 00:48:10,930
將周圍的箭頭，你沒有實際移動周圍的任何數據。

802
00:48:10,930 --> 00:48:14,610
因此，我們可以將梅艷芳，在這種情況下，瞬間。固定的時間。

803
00:48:14,610 --> 00:48:20,250
因此，我們有固定時間的查找，插入固定時間的像梅艷芳的人。

804
00:48:20,250 --> 00:48:22,740
但一種過於簡單化的世界。

805
00:48:22,740 --> 00:48:28,510
如果我們以後要找到愛麗絲嗎？

806
00:48:28,510 --> 00:48:31,050
如果我們以後要找到愛麗絲嗎？

807
00:48:31,050 --> 00:48:35,690
多少個步驟是，將要採取的嗎？

808
00:48:35,690 --> 00:48:37,850
[學生回答，不知所云]

809
00:48:37,850 --> 00:48:40,950
沒錯。愛麗絲還沒鍊錶中的人數。

810
00:48:40,950 --> 00:48:45,420
所以它不是很完美，因為我們的數據結構，再有這樣的垂直通道

811
00:48:45,420 --> 00:48:50,240
然後它有這些鍊錶掛 - 實際上，讓我們畫一個數組。

812
00:48:50,240 --> 00:48:56,020
這些鏈接列表，掛它看起來有點像這樣。

813
00:48:56,020 --> 00:48:59,110
但問題是，如果愛麗絲和亞當和所有這些其他的地名

814
00:48:59,110 --> 00:49:01,720
結束了越來越多的那邊，

815
00:49:01,720 --> 00:49:04,810
發現有人可以結束了一堆的步驟，

816
00:49:04,810 --> 00:49:06,670
bcause你必須遍歷鍊錶，

817
00:49:06,670 --> 00:49:08,090
這是一個線性操作。

818
00:49:08,090 --> 00:49:14,270
所以，真的，那麼，最終的插入時間是O（n），其中n是列表中的元素的數量。

819
00:49:14,270 --> 00:49:21,780
除以，讓我們隨意m，其中m是多少鍊錶

820
00:49:21,780 --> 00:49:24,500
，我們已經在此垂直軸。

821
00:49:24,500 --> 00:49:27,180
換句話說，如果我們真正假設均勻分佈的名稱，

822
00:49:27,180 --> 00:49:30,150
完全不現實的。顯然有比別人更多一些字母。

823
00:49:30,150 --> 00:49:32,580
>> 但是，如果我們假定為均勻分佈的那一刻起，

824
00:49:32,580 --> 00:49:37,350
我們有N總的人，和m總鏈

825
00:49:37,350 --> 00:49:40,630
提供給我們，然後每個這些鏈的長度

826
00:49:40,630 --> 00:49:44,380
相當簡單的將是的總量中，n鏈的數目除以。

827
00:49:44,380 --> 00:49:48,900
所以N / M。但在這裡，我們可以將所有數學聰明。

828
00:49:48,900 --> 00:49:53,030
m是一個常數，因為有​​一個固定數量的這些。

829
00:49:53,030 --> 00:49:54,620
你會開始申報您的陣列，

830
00:49:54,620 --> 00:49:58,450
我們不調整的垂直軸。根據定義，即固定不變的。

831
00:49:58,450 --> 00:50:01,220
這是唯一的橫軸，可以這麼說，這改變。

832
00:50:01,220 --> 00:50:04,760
因此從技術上講，這是一個常數。所以，現在，在插入時間

833
00:50:04,760 --> 00:50:09,700
幾乎是O（n）的。

834
00:50:09,700 --> 00:50:12,410
這樣就不會覺得所有的東西更好。

835
00:50:12,410 --> 00:50:14,940
但是，什麼是真相嗎？那麼，這一切的時間，幾個星期，

836
00:50:14,940 --> 00:50:20,640
我們一直在說為O（n²）。 O（N），2×N“， -  N，再除以2。 。 。 ECH。

837
00:50:20,640 --> 00:50:23,580
這是僅僅局限於N²。但現在，這部分的學期，

838
00:50:23,580 --> 00:50:25,560
我們可以開始再次談論真實的世界。

839
00:50:25,560 --> 00:50:31,520
N / M是絕對的速度比僅僅局限於N孤獨。

840
00:50:31,520 --> 00:50:35,170
如果你有一萬餘名，你將它們分解為多個桶

841
00:50:35,170 --> 00:50:37,820
所以，你有這些鏈中只有10名，

842
00:50:37,820 --> 00:50:41,670
絕對搜索的十件事將是快千餘件事情。

843
00:50:41,670 --> 00:50:43,740
因此，即將到來的習題會向你挑戰

844
00:50:43,740 --> 00:50:46,100
即使認為正是，是啊，

845
00:50:46,100 --> 00:50:49,520
漸近和數學，這還只是線性的，

846
00:50:49,520 --> 00:50:51,700
它吸收一般時試圖找東西。

847
00:50:51,700 --> 00:50:54,530
在現實中，它要快於

848
00:50:54,530 --> 00:50:56,520
因為這個除數。

849
00:50:56,520 --> 00:50:58,310
因此，有再一次將是這種權衡

850
00:50:58,310 --> 00:51:01,390
理論和現實之間的衝突，

851
00:51:01,390 --> 00:51:03,550
和一個旋鈕將在本學期開始轉向在這一點上

852
00:51:03,550 --> 00:51:07,510
是更現實的一個，因為我們準備semster的結束，

853
00:51:07,510 --> 00:51:09,280
為大家介紹一下世界的網絡編程，

854
00:51:09,280 --> 00:51:11,530
真的，性能要算，因為你的用戶要

855
00:51:11,530 --> 00:51:14,880
開始感受和欣賞糟糕的設計決策。

856
00:51:14,880 --> 00:51:19,950
>> 那麼，你如何去實施一個鏈接 - 哈希表的31個元素呢​​？

857
00:51:19,950 --> 00:51:22,600
前面的例子中任意生日。

858
00:51:22,600 --> 00:51:26,190
如果有一個人生日1月1日或2月1日，我們將把它們放在這個桶。

859
00:51:26,190 --> 00:51:28,960
如果這是1月2日，2月2日，3月2日，我們將把它們放在這個桶。

860
00:51:28,960 --> 00:51:32,220
這就是為什麼它是31。如何聲明一個哈希表？

861
00:51:32,220 --> 00:51:37,480
它可以是非常簡單的，的節點*表是我的任意名稱，[31]。

862
00:51:37,480 --> 00:51:42,400
這給了我31節點的指針，

863
00:51:42,400 --> 00:51:45,370
，讓我有31個指針鍊錶

864
00:51:45,370 --> 00:51:48,800
即使這些鏈是最初為NULL。

865
00:51:48,800 --> 00:51:54,860
把我想要什麼，如果我想存儲“愛麗絲”，“鮑勃”，“查理”嗎？

866
00:51:54,860 --> 00:51:57,010
好了，我們需要用這些東西在一個結構

867
00:51:57,010 --> 00:52:00,530
因為我們需要愛麗絲來指向給Bob，指向查理，等等。

868
00:52:00,530 --> 00:52:04,940
我們不能只單獨的名字，這樣我就可以創建一個新的結構，稱為節點在這裡。

869
00:52:04,940 --> 00:52:08,310
>> 什麼是實際的節點？在這個新的鍊錶節點是什麼？

870
00:52:08,310 --> 00:52:11,840
第一件事情，叫字，是人的名字。

871
00:52:11,840 --> 00:52:14,340
據推測，LENGTH，涉及一個人的名字的最大長度，

872
00:52:14,340 --> 00:52:18,210
不管它是什麼，20，30，40個字符瘋狂的角落的情況下，

873
00:52:18,210 --> 00:52:22,680
+1是為了什麼？這僅僅是額外的NULL字符，\ 0。

874
00:52:22,680 --> 00:52:27,410
因此，這個節點是包裝內的“東西”本身，

875
00:52:27,410 --> 00:52:29,640
但同時也宣告了一個指針稱為未來

876
00:52:29,640 --> 00:52:32,580
這樣我們就可以鏈Alice給Bob查理等等。

877
00:52:32,580 --> 00:52:36,700
可以為NULL，但不一定必須。

878
00:52:36,700 --> 00:52:40,110
這些哈希表的任何問題嗎？是嗎？

879
00:52:40,110 --> 00:52:46,190
[學生提問，不知所云]數組 - 很好的問題。

880
00:52:46,190 --> 00:52:50,120
字符數組中的字，而不是僅僅的char *這是為什麼？

881
00:52:50,120 --> 00:52:53,830
在這個有點亂的例子，我不想訴諸

882
00:52:53,830 --> 00:52:56,190
對malloc為原來的名稱。

883
00:52:56,190 --> 00:52:59,530
我想聲明的字符串的最大內存量

884
00:52:59,530 --> 00:53:06,020
這樣我就可以複製到結構愛麗絲\ 0，而不必處理malloc和free之類的。

885
00:53:06,020 --> 00:53:11,710
但我能做到這一點，如果我想成為更加自覺地空間使用。這個問題問得好。

886
00:53:11,710 --> 00:53:14,780
因此，讓我們嘗試概括距離

887
00:53:14,780 --> 00:53:18,350
和聚焦今天的其餘部分上的數據結構，更一般

888
00:53:18,350 --> 00:53:21,170
和其他問題，我們能夠解決使用相同的基本面

889
00:53:21,170 --> 00:53:24,590
即使自己的數據結構可能有所不同，在他們的資料。

890
00:53:24,590 --> 00:53:27,910
>> 因此，原來在計算機科學中，樹是非常常見的。

891
00:53:27,910 --> 00:53:29,760
你能想到的樹排序，就像一個家庭樹，

892
00:53:29,760 --> 00:53:31,830
那裡的一些根，有的女家長或族長，

893
00:53:31,830 --> 00:53:34,540
爺爺奶奶或或更早回來，

894
00:53:34,540 --> 00:53:38,880
下面是和爸爸媽媽或各種兄弟姐妹等。

895
00:53:38,880 --> 00:53:42,500
因此，一個樹結構的節點和它的孩子，

896
00:53:42,500 --> 00:53:45,260
通常每個節點的0個或更多的孩子。

897
00:53:45,260 --> 00:53:47,320
還有一些的專用術語，你在這張照片上看到的

898
00:53:47,320 --> 00:53:50,630
任何小的孩子或孫子的邊緣

899
00:53:50,630 --> 00:53:52,330
誰沒有從他們身上發出的箭頭，

900
00:53:52,330 --> 00:53:55,070
這些是所​​謂的葉子，並在裡面的任何人

901
00:53:55,070 --> 00:53:58,790
是一個內部節點，沿著這些線路，你可以把它叫做什麼。

902
00:53:58,790 --> 00:54:01,430
但是，這種結構是很常見的。這其中的任意一點。

903
00:54:01,430 --> 00:54:04,930
我們有一個孩子在左邊，我們有三個孩子的權利，

904
00:54:04,930 --> 00:54:06,830
兩個孩子的左下角。

905
00:54:06,830 --> 00:54:10,740
因此，我們可以有不同大小的樹木，但如果我們開始規範的東西，

906
00:54:10,740 --> 00:54:15,330
您可能還記得二進制從帕特里克的視頻上搜索從以前的短

907
00:54:15,330 --> 00:54:19,490
在線，二進制搜索不具有要實現的一個數組

908
00:54:19,490 --> 00:54:21,410
或紙片在黑板上。

909
00:54:21,410 --> 00:54:25,490
假設你想在一個更複雜的數據結構來存儲您的數字。

910
00:54:25,490 --> 00:54:27,680
你可以創建一個這樣的樹。

911
00:54:27,680 --> 00:54:35,290
你可以有一個在C中聲明的節點，該節點可以有它的內部的至少兩種元素。

912
00:54:35,290 --> 00:54:39,470
一個是你要存儲的號碼，另一個是 - 好了，我們需要一個更。

913
00:54:39,470 --> 00:54:41,540
另一種是它的孩子。

914
00:54:41,540 --> 00:54:45,150
因此，這裡的另一種數據結構。這時候，一個節點被定義為存儲號碼Ň

915
00:54:45,150 --> 00:54:49,060
然後兩個指針;左孩子和右孩子。

916
00:54:49,060 --> 00:54:52,100
他們不是任意的。這棵樹有什麼有趣的嗎？

917
00:54:52,100 --> 00:55:00,550
>> 在已經奠定了這一點，或如何帕特里克奠定了它在他的影片有什麼模式？

918
00:55:00,550 --> 00:55:02,790
這是一種明顯的，有一些排序怎麼回事，

919
00:55:02,790 --> 00:55:04,460
但什麼是簡單的規則嗎？是嗎？

920
00:55:04,460 --> 00:55:08,350
[學生回答，不知所云]

921
00:55:08,350 --> 00:55:12,040
完美的。如果你看一眼這，你會看到在左側的小數字，

922
00:55:12,040 --> 00:55:14,690
大號碼的左側，但為每個節點，這是真的。

923
00:55:14,690 --> 00:55:20,370
對於每個節點，其左子小於，大於它的右子樹。

924
00:55:20,370 --> 00:55:25,210
這意味著什麼，現在是，如果我要搜索這個數據結構，也就是說，44號，

925
00:55:25,210 --> 00:55:29,320
我必須從根開始，因為所有的這些更複雜的數據結構現在，

926
00:55:29,320 --> 00:55:31,910
我們只有一件事，有一個指針開始。

927
00:55:31,910 --> 00:55:35,010
在這種情況下，一開始是根。這不是左端，

928
00:55:35,010 --> 00:55:39,530
它的這種結構的根目錄中。所以我在這裡看到的是55歲，和我期待的44。

929
00:55:39,530 --> 00:55:41,430
我想往哪個方向去？

930
00:55:41,430 --> 00:55:45,680
嗯，我想往左走，因為很明顯，在右邊將是太大了。

931
00:55:45,680 --> 00:55:49,050
所以，注意在這裡，你樣的概念上砍了一半的樹

932
00:55:49,050 --> 00:55:51,700
因為你永遠也不會下降的右手邊。

933
00:55:51,700 --> 00:55:55,410
所以，現在我從55到33。這是過於小了一些。

934
00:55:55,410 --> 00:56:01,590
我在尋找44，但現在我知道，如果44是在這棵樹，我可以去顯然是正確的。

935
00:56:01,590 --> 00:56:04,460
所以，再一次，我修剪樹的一半。

936
00:56:04,460 --> 00:56:06,780
這幾乎是相同的概念上的電話簿。

937
00:56:06,780 --> 00:56:09,510
這是相同的，我們所做的在黑板上的文件，

938
00:56:09,510 --> 00:56:13,940
但它是一個更複雜的結構，使我們能夠真正做到

939
00:56:13,940 --> 00:56:16,880
這種分而治之的算法設計，

940
00:56:16,880 --> 00:56:19,420
而事實上，穿越這樣的結構 - 哎呦。

941
00:56:19,420 --> 00:56:22,870
遍歷這樣的結構，它只是“走這條路還是走那條路。”

942
00:56:22,870 --> 00:56:26,870
意味著所有的代碼，彎曲你的心靈第一次執行時第

943
00:56:26,870 --> 00:56:31,270
在家裡或步行通過，為二進制搜索，使用遞歸或迭代，

944
00:56:31,270 --> 00:56:35,060
這是一個痛苦的脖子上。中間的元素，然後做你的四捨五入向上或向下。

945
00:56:35,060 --> 00:56:39,230
>> 有一個美麗了，因為我們現在可以再次使用遞歸，

946
00:56:39,230 --> 00:56:43,760
但更乾淨。事實上，如果你在55號和您想要尋找44，

947
00:56:43,760 --> 00:56:48,450
在這種情況下，你向左走，然後你會怎麼做？您可以運行相同的算法。

948
00:56:48,450 --> 00:56:51,560
檢查節點的值，然後你去左邊或右邊。

949
00:56:51,560 --> 00:56:53,670
然後檢查節點的值，向左走還是向右。

950
00:56:53,670 --> 00:56:56,710
這是非常適合遞歸。

951
00:56:56,710 --> 00:57:00,920
因此，即使在過去，我們已經做了一些非常隨意的，涉及遞歸的例子

952
00:57:00,920 --> 00:57:03,430
沒有需要的是遞歸的，數據鋼結構，

953
00:57:03,430 --> 00:57:07,820
特別是樹木，這是一個完美的應用這個想法的一個問題，

954
00:57:07,820 --> 00:57:12,920
縮小，然後解決相同類型的，但較小的，程序。

955
00:57:12,920 --> 00:57:14,590
>> 所以，我們可以引進另一種數據結構。

956
00:57:14,590 --> 00:57:18,760
這一個是在第一眼就看神秘的，但是這一次是驚人的。

957
00:57:18,760 --> 00:57:25,090
因此，這是一個數據結構稱為特里，特里，這是繼承的詞檢索，

958
00:57:25,090 --> 00:57:30,210
沒有明顯的重試時間間隔，但是這就是世人所謂的這些東西。嘗試。 T-R-I-E。

959
00:57:30,210 --> 00:57:35,190
它是一個某種形式的樹結構，但在一個Trie樹的每個節點

960
00:57:35,190 --> 00:57:41,280
似乎是什麼？這是一個有點誤導，因為它是一種簡稱。

961
00:57:41,280 --> 00:57:45,960
但它看起來像這trie樹中的每個節點實際上是一個數組。

962
00:57:45,960 --> 00:57:48,840
即使此圖的作者並沒有表現出它，

963
00:57:48,840 --> 00:57:54,130
在這種情況下，這個線索是一種數據結構，其目的在生活中是存儲詞語

964
00:57:54,130 --> 00:57:57,330
A-L-I-C-E或B-O-B等。

965
00:57:57,330 --> 00:58:02,480
的方式，此數據存儲Alice和Bob和Charlie和梅艷芳等等

966
00:58:02,480 --> 00:58:06,970
是使用一個數組來存儲，愛麗絲在特里，

967
00:58:06,970 --> 00:58:09,820
它看起來像一個數組的根節點開始，

968
00:58:09,820 --> 00:58:12,080
它被寫在速記符號。

969
00:58:12,080 --> 00:58:15,070
筆者省略，ABCDEFG，因為有沒有名字。

970
00:58:15,070 --> 00:58:19,150
他們僅表現為M和P和T，但在這種情況下，

971
00:58:19,150 --> 00:58:22,780
讓搬走Alice和Bob和Charlie一些名字在這裡。

972
00:58:22,780 --> 00:58:25,670
麥克斯韋實際上是在此圖中。

973
00:58:25,670 --> 00:58:29,570
那麼，如何做的作者店M-X-W-E-L-L？

974
00:58:29,570 --> 00:58:36,990
他或她的根節點開始，並到[M]，因此，大約13時，13日在數組中的位置。

975
00:58:36,990 --> 00:58:40,750
然後從那裡，有一個指針。

976
00:58:40,750 --> 00:58:42,760
導致另一個數組的指針。

977
00:58:42,760 --> 00:58:47,880
從那裡到該數組的索引位置A，作為描繪在左上角，

978
00:58:47,880 --> 00:58:52,250
那麼他或她跟著到另一個數組，指針，

979
00:58:52,250 --> 00:58:55,460
去的指針位置X.

980
00:58:55,460 --> 00:58:59,840
然後，在下一數組位置W，E，L，L，等等，

981
00:58:59,840 --> 00:59:03,090
最後，讓我們真正嘗試把圖片。

982
00:59:03,090 --> 00:59:05,380
節點看起來像在代碼中做了什麼？

983
00:59:05,380 --> 00:59:11,820
trie樹中的一個節點包含多個節點的指針數組。

984
00:59:11,820 --> 00:59:16,090
但也有，至少在這個實現了某種形式的布爾值。

985
00:59:16,090 --> 00:59:18,770
我碰巧把它稱為is_word。為什麼呢？

986
00:59:18,770 --> 00:59:22,670
因為當你插入麥克斯韋，你不插入

987
00:59:22,670 --> 00:59:25,300
任何東西到這個數據結構。

988
00:59:25,300 --> 00:59:27,480
你不寫M.你不寫X.

989
00:59:27,480 --> 00:59:30,240
你做的是以下指針。

990
00:59:30,240 --> 00:59:33,360
表示M，接著是表示A的指針，該指針的指針，該指針

991
00:59:33,360 --> 00:59:36,310
然後指針，表示X，則W，E，L，L，

992
00:59:36,310 --> 00:59:41,950
但結束時你需要做的是去，檢查排序，我達到了這個位置。

993
00:59:41,950 --> 00:59:45,560
有在數據結構中的一個詞，在這裡結束。

994
00:59:45,560 --> 00:59:48,190
>> 那麼什麼是特里真的是充滿了筆者選擇了代表

995
00:59:48,190 --> 00:59:51,880
這些小三角總站。

996
00:59:51,880 --> 00:59:56,470
這只是意味著這樣一個事實，這個三角形在這裡，這個布爾值true;

997
00:59:56,470 --> 00:59:59,200
也就是說，如果你往後走的樹，

998
00:59:59,200 --> 01:00:02,420
這意味著名為Maxwell是在這一個字。

999
01:00:02,420 --> 01:00:04,870
但這個詞foo的，例如，

1000
01:00:04,870 --> 01:00:07,970
是不是在樹中，因為如果我開始在這裡的根節點在頂部，

1001
01:00:07,970 --> 01:00:14,030
有沒有F指針，無O指針，無O指針。 foo不是在這本字典的名稱。

1002
01:00:14,030 --> 01:00:22,460
但相反的是，圖靈，T-U-R-I-N-G。同樣，我沒有存儲t或u r或i或N或G。

1003
01:00:22,460 --> 01:00:29,820
但我沒有商店這個數據結構中的值的正確的方法，在這裡在此節點 - 樹

1004
01:00:29,820 --> 01:00:33,030
這個布爾值is_word設置為true。

1005
01:00:33,030 --> 01:00:35,740
因此，trie樹是種很有趣的元結構，

1006
01:00:35,740 --> 01:00:39,810
你不是真正的存儲的話自己這種字典。

1007
01:00:39,810 --> 01:00:45,100
要清楚，你只是存儲“是”或“否”，有一個詞在這裡結束。

1008
01:00:45,100 --> 01:00:46,430
>> 現在有什麼含義？

1009
01:00:46,430 --> 01:00:51,120
如果你有15萬字，在字典中，你想存儲在內存中

1010
01:00:51,120 --> 01:00:53,400
使用類似的鏈接列表，

1011
01:00:53,400 --> 01:00:56,870
你將有15節點的鍊錶。

1012
01:00:56,870 --> 01:01:00,250
發現這些詞的字母順序排列，可能需要O（n）的時間。

1013
01:01:00,250 --> 01:01:04,370
線性時間。但是，在這裡的情況下的線索，

1014
01:01:04,370 --> 01:01:09,210
什麼是運行時間找到一個詞？

1015
01:01:09,210 --> 01:01:17,390
原來，這裡的美景，即使你已經在這本字典有149,999個字，

1016
01:01:17,390 --> 01:01:20,170
如使用該數據結構實現，

1017
01:01:20,170 --> 01:01:25,560
找到或插入多一個人進認為，像愛麗絲，愛麗絲需要多少時間？

1018
01:01:25,560 --> 01:01:30,640
嗯，這是只有5個，也許6個步驟的尾隨字符。

1019
01:01:30,640 --> 01:01:32,880
由於結構中的其他名稱presense

1020
01:01:32,880 --> 01:01:35,340
沒有得到中的插入愛麗絲的方式。

1021
01:01:35,340 --> 01:01:39,640
此外，尋找愛麗絲曾經在這本字典有15萬字

1022
01:01:39,640 --> 01:01:41,960
在用自己的方式尋找愛麗絲在沒有得到，

1023
01:01:41,960 --> 01:01:46,880
因為Alice。 。 。 。 。在這裡，因為我發現一個布爾值。

1024
01:01:46,880 --> 01:01:50,920
如果沒有布爾值true，則Alice是不是這個數據結構中的話。

1025
01:01:50,920 --> 01:01:56,220
換言之，找東西和插入到這個新的東西的運行時間

1026
01:01:56,220 --> 01:02:01,920
數據結構的特里是O  - 它不是N。

1027
01:02:01,920 --> 01:02:05,730
因為presense 15萬人沒有“愛麗絲夢遊仙境”的影響，它似乎。

1028
01:02:05,730 --> 01:02:11,560
因此，讓我們把它k，其中k是一個英語單詞的最大長度

1029
01:02:11,560 --> 01:02:14,050
這是通常不超過20的東西字符。

1030
01:02:14,050 --> 01:02:17,940
因此，k是常數。所以我們現在似乎已經找到了聖杯

1031
01:02:17,940 --> 01:02:26,000
是的特里，不變的插入，查找，刪除。

1032
01:02:26,000 --> 01:02:29,170
由於已經在結構的數目的事情，

1033
01:02:29,170 --> 01:02:32,600
這是甚至沒有親臨現場。同樣，他們只是排序的檢查，“是”或“否”，

1034
01:02:32,600 --> 01:02:35,050
沒有影響其未來的運行時間。

1035
01:02:35,050 --> 01:02:37,940
>> 但還有了一個catch，否則我們不會浪費這麼多時間

1036
01:02:37,940 --> 01:02:41,460
在所有這些其他的數據結構，最終得到的秘密是驚人的。

1037
01:02:41,460 --> 01:02:46,410
所以，我們要付出什麼樣的價格在這裡實現這一​​偉大嗎？空間。

1038
01:02:46,410 --> 01:02:49,010
這件事是巨大的。的原因，筆者

1039
01:02:49,010 --> 01:02:52,400
並不會出現在這裡，請注意，所有的這些東西，看起來像陣列，

1040
01:02:52,400 --> 01:02:55,400
他沒有畫出其餘的樹，其餘的特里，

1041
01:02:55,400 --> 01:02:58,060
因為他們只是不相關的故事。

1042
01:02:58,060 --> 01:03:01,870
但是，所有的這些節點是超級寬，樹中的每個節點佔用

1043
01:03:01,870 --> 01:03:07,780
26實際上，可能是27個字符，因為在這種情況下，我包括空間中的所有格符號

1044
01:03:07,780 --> 01:03:09,980
這樣我們就可以有apostrophized的話。

1045
01:03:09,980 --> 01:03:14,450
在這種情況下，這些都是寬陣列。因此，即使他們沒有picutured，

1046
01:03:14,450 --> 01:03:18,190
這佔用了大量的內存。

1047
01:03:18,190 --> 01:03:20,670
這可能是罰款，especilly在現代的硬件，

1048
01:03:20,670 --> 01:03:25,650
但是這是一個折衷。我們得到了更短的時間內，花更多的空間。

1049
01:03:25,650 --> 01:03:28,580
那麼，這是怎麼回事？

1050
01:03:28,580 --> 01:03:32,640
好吧，讓我們做的 - 讓我們在這裡看到的。

1051
01:03:32,640 --> 01:03:39,510
讓我們做一個跳轉到這個傢伙在這裡。

1052
01:03:39,510 --> 01:03:43,450
>> 不管你相信與否，盡可能多的樂趣為C已經有一段時間了，

1053
01:03:43,450 --> 01:03:48,130
我們到達點在本學期的時間過渡到更現代的東西。

1054
01:03:48,130 --> 01:03:50,950
在更高層次上的事情。即使在接下來的幾個星期

1055
01:03:50,950 --> 01:03:54,580
我們仍然會繼續埋頭在世界上的指針和內存管理

1056
01:03:54,580 --> 01:03:57,210
得到安慰，使我們可以再建，

1057
01:03:57,210 --> 01:04:01,270
比賽結束，最終還是引進，具有諷刺意味的是，這不是語言。

1058
01:04:01,270 --> 01:04:03,330
我們會花10分鐘，談論HTML一樣。

1059
01:04:03,330 --> 01:04:05,950
所有的HTML是一種標記語言，一種標記語言是什麼

1060
01:04:05,950 --> 01:04:10,220
這些系列開放式支架和封閉括號，說'這個大膽的“

1061
01:04:10,220 --> 01:04:12,000
“這斜體”，“使這個中心的。”

1062
01:04:12,000 --> 01:04:14,250
這是不是所有的智力有趣的，但它是超級有用的。

1063
01:04:14,250 --> 01:04:16,650
它肯定是無所不在的這些天。

1064
01:04:16,650 --> 01:04:19,450
但是，什麼是功能強大的HTML世界，更普遍的Web編程，

1065
01:04:19,450 --> 01:04:25,910
建立動態的東西的語言，如PHP或Python或Ruby或Java或C＃編寫代碼。

1066
01:04:25,910 --> 01:04:30,360
真的，無論你選擇的語言，並動態地生成HTML。

1067
01:04:30,360 --> 01:04:32,960
被稱為CSS動態生成的東西。

1068
01:04:32,960 --> 01:04:35,810
級聯樣式表，這也是對美學。

1069
01:04:35,810 --> 01:04:41,360
因此，即使今天，如果我去一些喜歡熟悉的Google.com網站，

1070
01:04:41,360 --> 01:04:46,100
我去查看，開發人員，查看源代碼，也許你以前做過，

1071
01:04:46,100 --> 01:04:49,800
但要查看源代碼，這東西可能看起來很神秘的。

1072
01:04:49,800 --> 01:04:55,320
但是，這是基本的代碼，實現Google.com。

1073
01:04:55,320 --> 01:04:57,940
在前端。而實際上這是蓬鬆的美學的東西。

1074
01:04:57,940 --> 01:05:01,740
這是CSS在這裡。如果我繼續向下滾動，我們會得到一些顏色編碼的東西。

1075
01:05:01,740 --> 01:05:06,890
這是HTML。谷歌的代碼看起來像一個爛攤子，但如果我真的打開不同的窗口，

1076
01:05:06,890 --> 01:05:09,380
在此，我們可以看到一些結構。

1077
01:05:09,380 --> 01:05:12,640
如果我打開這件事，請注意，這是一個有點更具可讀性。

1078
01:05:12,640 --> 01:05:16,850
我們不久會看到這個標籤，[字]是一個標籤，

1079
01:05:16,850 --> 01:05:23,520
HTML，頭部，身體，DIV，腳本，文本區，跨度為中心的分區。

1080
01:05:23,520 --> 01:05:26,770
這也有幾分神秘的前瞻性乍看之下，

1081
01:05:26,770 --> 01:05:30,890
但這個爛攤子遵循一定的模式和重複的模式，

1082
01:05:30,890 --> 01:05:33,850
因此，一旦我們得到的基本知識，你就可以寫這樣的代碼

1083
01:05:33,850 --> 01:05:37,550
然後操作使用另一種語言，稱為JavaScript代碼。

1084
01:05:37,550 --> 01:05:40,440
JavaScript是一種語言，運行在瀏覽器

1085
01:05:40,440 --> 01:05:44,380
今天，我們用哈佛的課程，該課程的購物工具，谷歌地圖使用

1086
01:05:44,380 --> 01:05:48,660
給你一大堆的活力，Facebook讓你顯示的即時狀態更新，

1087
01:05:48,660 --> 01:05:51,430
Twitter的使​​用它來顯示你的鳴叫瞬間。

1088
01:05:51,430 --> 01:05:53,820
所有這一切，我們將開始埋頭進來。

1089
01:05:53,820 --> 01:05:57,190
但到了那裡，我們需要了解一些關於互聯網。

1090
01:05:57,190 --> 01:06:01,130
這個夾子在這裡只是一分鐘之久，現在讓我們假設這是，其實，

1091
01:06:01,130 --> 01:06:08,380
如何在互聯網什麼來捉弄人。我給你“勇士的淨。”

1092
01:06:08,380 --> 01:06:14,720
>> [♫合唱音樂的慢♫]

1093
01:06:14,720 --> 01:06:20,450
男解說員，他帶著一個消息。

1094
01:06:20,450 --> 01:06:23,770
隨著自己的協議。

1095
01:06:23,770 --> 01:06:37,270
[♫更快的電子音樂♫]

1096
01:06:37,270 --> 01:06:41,330
他來到一個世界的酷防火牆的，漠不關心的路由器，

1097
01:06:41,330 --> 01:06:45,690
遠遠比死還要痛苦和危險。

1098
01:06:45,690 --> 01:06:55,400
他速度非常快。他的強者。他是TCP / IP，和他有你的地址。

1099
01:06:55,400 --> 01:06:59,250
勇士的淨。

1100
01:06:59,250 --> 01:07:05,290
[馬蘭]下週。互聯網。 Web編程。這是CS50。

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]