1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID：有時候，構建一個時
程序，你可能想利用

3
00:00:10,890 --> 00:00:13,190
稱為字典的數據結構。

4
00:00:13,190 --> 00:00:17,960
字典映射鍵，這是
通常是字符串，將值，整數，

5
00:00:17,960 --> 00:00:21,900
字符，一個指針到某些對象，
任何我們想要的。

6
00:00:21,900 --> 00:00:26,510
這就像普通的字典
那個地圖的話，通過定義。

7
00:00:26,510 --> 00:00:29,440
>> 字典為我們提供了
存儲信息的能力

8
00:00:29,440 --> 00:00:32,750
與相關的東西
後來看看它。

9
00:00:32,750 --> 00:00:36,620
那麼，如何才能真正實現一
字典，比方說，C代碼，我們可以

10
00:00:36,620 --> 00:00:38,460
在我們的計劃之一使用？

11
00:00:38,460 --> 00:00:41,790
嗯，有很多的方式，
我們可以實現一個字典。

12
00:00:41,790 --> 00:00:45,930
>> 首先，我們可以使用一個數組，我們
動態調整大小，或者我們可以使用一個

13
00:00:45,930 --> 00:00:49,150
鍊錶，哈希表
或二叉樹。

14
00:00:49,150 --> 00:00:52,250
但無論我們選擇，我們應該
銘記效率和

15
00:00:52,250 --> 00:00:54,300
實施的績效。

16
00:00:54,300 --> 00:00:57,930
我們應該想想所使用的算法
插入和查找物品進入

17
00:00:57,930 --> 00:00:59,120
我們的數據結構。

18
00:00:59,120 --> 00:01:03,060
>> 現在，讓我們假設我們
要使用字符串作為鍵。

19
00:01:03,060 --> 00:01:07,290
讓我們來談談一種可能性，
一個數據結構，稱為特里。

20
00:01:07,290 --> 00:01:11,210
所以這裡有一個可視化表示
的線索。

21
00:01:11,210 --> 00:01:14,590
>> 作為圖像顯示，一個線索
是一個樹形數據結構與

22
00:01:14,590 --> 00:01:16,050
節點連接在一起。

23
00:01:16,050 --> 00:01:19,420
我們看到，有清楚的根
節點與一些鏈接延伸到

24
00:01:19,420 --> 00:01:20,500
其他節點。

25
00:01:20,500 --> 00:01:23,040
但什麼是每個節點組成的呢？

26
00:01:23,040 --> 00:01:26,700
如果我們假設我們正在存儲密鑰
只有字母字符，並

27
00:01:26,700 --> 00:01:30,150
我們不關心資本化，
這裡有一個節點的定義，

28
00:01:30,150 --> 00:01:31,100
就足夠了。

29
00:01:31,100 --> 00:01:34,130
>> 其類型的對象是結構
節點有兩個部分

30
00:01:34,130 --> 00:01:35,740
所謂的數據和兒童。

31
00:01:35,740 --> 00:01:39,200
我們已經離開了數據部分為註釋
由一個部件來代替

32
00:01:39,200 --> 00:01:43,190
申報時結構節點
在C程序中。

33
00:01:43,190 --> 00:01:47,040
一個節點的數據部分可能是一個
布爾值，表示是否

34
00:01:47,040 --> 00:01:51,160
不是節點為完成
的字典鍵或者它可能是一個

35
00:01:51,160 --> 00:01:54,240
表示定義字符串
在字典中的詞。

36
00:01:54,240 --> 00:01:58,870
>> 我們將使用一個笑臉來表示
當數據存在於一個節點。

37
00:01:58,870 --> 00:02:02,310
有26個元素我們
兒童陣列，一個索引

38
00:02:02,310 --> 00:02:03,690
每個字母字符。

39
00:02:03,690 --> 00:02:06,570
我們將看到的意義
這很快。

40
00:02:06,570 --> 00:02:10,759
>> 讓我們根節點仔細看看
在我們的圖表，它沒有數據

41
00:02:10,759 --> 00:02:14,740
與它相關的，由所指示的
沒有在笑臉的

42
00:02:14,740 --> 00:02:16,110
數據部分。

43
00:02:16,110 --> 00:02:19,910
從該部件延伸的箭頭
孩子們數組表示非節點

44
00:02:19,910 --> 00:02:21,640
指針到其他節點。

45
00:02:21,640 --> 00:02:25,500
例如，箭頭從延伸
兒童的第二元件

46
00:02:25,500 --> 00:02:28,400
代表字母B
在字典鍵。

47
00:02:28,400 --> 00:02:31,920
並且在較大的圖
我們用B。貼上標籤

48
00:02:31,920 --> 00:02:35,810
>> 需要注意的是在更大的框圖，當我們
繪製一個指針到另一個節點，它

49
00:02:35,810 --> 00:02:39,100
不要緊其中箭頭
符合該另一節點。

50
00:02:39,100 --> 00:02:43,850
我們的樣本字典包含特里
兩個詞，那和變焦。

51
00:02:43,850 --> 00:02:47,040
讓我們通過一個例子
查找數據的關鍵。

52
00:02:47,040 --> 00:02:50,800
>> 假設我們要查找
為密鑰浴相應值。

53
00:02:50,800 --> 00:02:53,610
我們將開始我們的樣子了
在根節點。

54
00:02:53,610 --> 00:02:57,870
然後，我們將利用我們的第一個字母
鍵，B和找到對應

55
00:02:57,870 --> 00:03:00,020
發現我們的孩子陣列。

56
00:03:00,020 --> 00:03:04,490
請注意，恰好有26點
數組，一個用於每個字母在

57
00:03:04,490 --> 00:03:05,330
字母表。

58
00:03:05,330 --> 00:03:08,800
我們將有斑點代表
字母表中的順序中的字母。

59
00:03:08,800 --> 00:03:13,960
>> 我們來看看第二個索引的話，
索引1，為B。在一般情況下，如果我們

60
00:03:13,960 --> 00:03:17,990
有一些字母字母C我們
可確定相應的點

61
00:03:17,990 --> 00:03:21,520
在使用兒童陣列
計算是這樣的。

62
00:03:21,520 --> 00:03:25,140
我們可以使用一個較大的孩子
如果數組我們希望提供的看看了

63
00:03:25,140 --> 00:03:28,380
具有更廣泛的字符鍵，
如在整個

64
00:03:28,380 --> 00:03:29,880
ASCII字符集。

65
00:03:29,880 --> 00:03:32,630
>> 在這種情況下，指針
在我們的孩子在陣列

66
00:03:32,630 --> 00:03:34,320
指標之一是不為null。

67
00:03:34,320 --> 00:03:36,600
因此，我們將繼續尋找
了關鍵洗澡。

68
00:03:36,600 --> 00:03:40,130
如果我們曾經遇到過一個空指針
在孩子正確點

69
00:03:40,130 --> 00:03:43,230
數組，而我們所走過的節點，
那麼我們將不得不說，我們

70
00:03:43,230 --> 00:03:45,630
找不到任何為關鍵。

71
00:03:45,630 --> 00:03:49,370
>> 現在，我們將採取的第二個字母
我們的關鍵，A，並繼續以下

72
00:03:49,370 --> 00:03:52,400
這樣的指針，直到我們
達到我們的主要的結束。

73
00:03:52,400 --> 00:03:56,530
如果我們達到了關鍵的結束不
擊中任何死角，空指針，

74
00:03:56,530 --> 00:03:59,730
因為是這裡的情況，那麼我們只
必須檢查一件事。

75
00:03:59,730 --> 00:04:02,110
這是真正的關鍵
在字典？

76
00:04:02,110 --> 00:04:07,660
>> 如果是這樣，我們應該找到一個值，以及一個
在我們的圖表笑臉圖標在那裡

77
00:04:07,660 --> 00:04:08,750
這個詞結束。

78
00:04:08,750 --> 00:04:12,270
如果還有別的東西與存儲
的數據，那麼我們就可以返回。

79
00:04:12,270 --> 00:04:16,500
例如，關鍵動物園不在
字典，即使我們可以有

80
00:04:16,500 --> 00:04:19,810
達到了這個關鍵的結束而沒有
打一個空指針，而我們

81
00:04:19,810 --> 00:04:21,089
遍歷線索。

82
00:04:21,089 --> 00:04:25,436
>> 如果我們試圖尋找出關鍵洗澡時，
倒數第二個節點的數組索引，

83
00:04:25,436 --> 00:04:28,750
對應的字母H，將
舉行一個空指針。

84
00:04:28,750 --> 00:04:31,120
所以洗澡是不是在字典中。

85
00:04:31,120 --> 00:04:34,800
和這樣一個線索是獨特的，該密鑰
從來沒有明確地存儲在

86
00:04:34,800 --> 00:04:36,650
的數據結構。

87
00:04:36,650 --> 00:04:38,810
那麼，我們如何將東西
成特里？

88
00:04:38,810 --> 00:04:41,780
>> 讓我們來插入鑰匙
動物園到我們的線索。

89
00:04:41,780 --> 00:04:46,120
請記住，在一個節點一個笑臉
可以在代碼中對應於一個簡單的

90
00:04:46,120 --> 00:04:50,170
Boolean值，表明動物園
在字典中，或者它可以

91
00:04:50,170 --> 00:04:53,710
對應的詳細信息，我們
希望與關鍵動物園相關聯，

92
00:04:53,710 --> 00:04:56,860
類似的定義
字或別的東西。

93
00:04:56,860 --> 00:05:00,350
在某些方面，這個過程要插入
事成特里類似於

94
00:05:00,350 --> 00:05:02,060
仰視的東西在特里。

95
00:05:02,060 --> 00:05:05,720
>> 我們先從根節點再次，
對應下面的指針

96
00:05:05,720 --> 00:05:07,990
我們主要的字母。

97
00:05:07,990 --> 00:05:11,310
幸運的是，我們能夠跟隨指針
所有，直到我們到達方式

98
00:05:11,310 --> 00:05:12,770
該鍵的末端。

99
00:05:12,770 --> 00:05:16,480
由於動物園是這個詞的前綴
變焦，這是其中一個成員

100
00:05:16,480 --> 00:05:19,440
字典，我們不需要
分配任何新的節點。

101
00:05:19,440 --> 00:05:23,140
>> 我們可以修改節點，以指示
字符導致的路徑

102
00:05:23,140 --> 00:05:25,360
它代表了我們的字典的一個關鍵。

103
00:05:25,360 --> 00:05:28,630
現在，讓我們嘗試插入
關鍵沐浴到特里。

104
00:05:28,630 --> 00:05:32,260
我們將開始在根節點
並再次跟隨指針。

105
00:05:32,260 --> 00:05:35,620
但在這種情況下，我們打一個死
最終我們能夠到達之前

106
00:05:35,620 --> 00:05:36,940
關鍵的結束。

107
00:05:36,940 --> 00:05:40,980
現在，我們需要分配一些新的
節點需要分配一個新的

108
00:05:40,980 --> 00:05:43,660
節點的每個剩餘
我們的主要的信。

109
00:05:43,660 --> 00:05:46,740
>> 在這種情況下，我們只需要
分配一個新的節點。

110
00:05:46,740 --> 00:05:50,590
然後，我們將需要使H指數
引用該新節點。

111
00:05:50,590 --> 00:05:54,070
再次，我們可以通過修改節點
顯示的字符的路徑

112
00:05:54,070 --> 00:05:57,120
導致它代表一個
關鍵在我們的字典。

113
00:05:57,120 --> 00:06:00,730
讓我們來推理漸近
我們的程序，這些複雜性

114
00:06:00,730 --> 00:06:02,110
兩個操作。

115
00:06:02,110 --> 00:06:06,420
>> 我們注意到，在這兩種情況下的數
步驟我們的算法是拿了

116
00:06:06,420 --> 00:06:09,470
成比例的數量
信中的關鍵字。

117
00:06:09,470 --> 00:06:10,220
這是正確的。

118
00:06:10,220 --> 00:06:13,470
當你想查找的單詞
特里，你只需要遍歷

119
00:06:13,470 --> 00:06:17,100
字母一個接一個，直到您
達到該字的結尾或

120
00:06:17,100 --> 00:06:19,060
在特里打了一個死胡同。

121
00:06:19,060 --> 00:06:22,470
>> 而當你想插入一個關鍵
值對成特里使用

122
00:06:22,470 --> 00:06:26,250
過程中，我們討論了，最壞的情況下
將你分配一個新節點

123
00:06:26,250 --> 00:06:27,550
每個字母。

124
00:06:27,550 --> 00:06:31,290
我們將假設分配
是一個常數時間的操作。

125
00:06:31,290 --> 00:06:35,850
所以，如果我們假設密鑰長度為
由一個固定的常數，二者有界

126
00:06:35,850 --> 00:06:39,400
插入和查找是不變的
運營時間為線索。

127
00:06:39,400 --> 00:06:42,930
>> 如果我們不做出這種假設，
密鑰的長度是由一個固定的範圍內

128
00:06:42,930 --> 00:06:46,650
常數，則插入和查詢，
在最壞的情況下，是線性的

129
00:06:46,650 --> 00:06:48,240
長的關鍵。

130
00:06:48,240 --> 00:06:51,800
請注意，保存的項目數量
在該線索不影響它的外表向上

131
00:06:51,800 --> 00:06:52,820
或插入時間。

132
00:06:52,820 --> 00:06:55,360
它只能由受影響
長的關鍵。

133
00:06:55,360 --> 00:06:59,300
>> 相比之下，添加條目，比方說，
哈希表往往使

134
00:06:59,300 --> 00:07:01,250
未來看起來更慢。

135
00:07:01,250 --> 00:07:04,520
雖然這聽起來吸引人起初，
我們應該記住，一個

136
00:07:04,520 --> 00:07:08,740
有利的漸近複雜性不
意味著在實踐中，數據

137
00:07:08,740 --> 00:07:11,410
結構是必然
無可非議。

138
00:07:11,410 --> 00:07:15,860
我們還必須考慮到存儲
字在字典樹，我們所需要的，在最壞的

139
00:07:15,860 --> 00:07:19,700
情況下，節點數量成比例
於字本身的長度。

140
00:07:19,700 --> 00:07:21,880
>> 嘗試傾向於使用大量的空間。

141
00:07:21,880 --> 00:07:25,620
這是相對於一個哈希表，
在這裡我們只需要一個新的節點

142
00:07:25,620 --> 00:07:27,940
存儲一些鍵值對。

143
00:07:27,940 --> 00:07:31,370
現在，再從理論上講，空間大
消費似乎並不像一個大

144
00:07:31,370 --> 00:07:34,620
處理，特別是考慮到現代
電腦有千兆字節和

145
00:07:34,620 --> 00:07:36,180
GB的內存。

146
00:07:36,180 --> 00:07:39,200
但事實證明，我們仍然有
不用擔心內存使用和

147
00:07:39,200 --> 00:07:42,540
組織為求
性能，因為現代計算機

148
00:07:42,540 --> 00:07:46,960
有下建立了相關機制
油煙機，以加快內存訪問。

149
00:07:46,960 --> 00:07:51,180
>> 但這些機制最好的工作時
內存訪問是在緊湊的製作

150
00:07:51,180 --> 00:07:52,810
區域或地區。

151
00:07:52,810 --> 00:07:55,910
和特里的節點可以駐留
在堆中的任何地方。

152
00:07:55,910 --> 00:07:58,390
但這些都是權衡
我們必須考慮的問題。

153
00:07:58,390 --> 00:08:01,440
>> 請記住，選擇一個數據時，
結構有一定的任務，我們

154
00:08:01,440 --> 00:08:04,420
應該想想什麼樣的
操作的數據結構需要

155
00:08:04,420 --> 00:08:07,140
支持和多少的性能
這些每個的

156
00:08:07,140 --> 00:08:09,080
操作事項給我們。

157
00:08:09,080 --> 00:08:11,300
這些操作可能連
超越只是

158
00:08:11,300 --> 00:08:13,430
基本外觀和插入。

159
00:08:13,430 --> 00:08:17,010
假設我們要實現一個樣
自動完成功能，多

160
00:08:17,010 --> 00:08:18,890
像谷歌搜索引擎一樣。

161
00:08:18,890 --> 00:08:22,210
也就是說，退還所有鑰匙和
潛在的價值觀，

162
00:08:22,210 --> 00:08:24,130
有一個給定的前綴。

163
00:08:24,130 --> 00:08:27,050
>> 字典樹是唯一有用的
進行此操作。

164
00:08:27,050 --> 00:08:29,890
這是簡單的遍歷
該線索進行的每一個字符

165
00:08:29,890 --> 00:08:30,950
前綴。

166
00:08:30,950 --> 00:08:33,559
就像一個查找操作，
我們可以遵循的指針

167
00:08:33,559 --> 00:08:35,400
逐個字符。

168
00:08:35,400 --> 00:08:38,659
然後，當我們在的底到達
前綴，我們可以遍歷

169
00:08:38,659 --> 00:08:42,049
該數據結構的其餘部分
因為任何按鍵超越

170
00:08:42,049 --> 00:08:43,980
這點有前綴。

171
00:08:43,980 --> 00:08:47,670
>> 它也很容易得到此房產
自中按字母順序

172
00:08:47,670 --> 00:08:50,970
孩子們數組中的元素
按字母順序排序。

173
00:08:50,970 --> 00:08:54,420
所以希望你們能考慮
捐贈試圖一試。

174
00:08:54,420 --> 00:08:56,085
我是凱文·施密德，這是CS50。

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> 啊，這是開始
的下降。

177
00:09:00,790 --> 00:09:01,350
對不起。

178
00:09:01,350 --> 00:09:01,870
抱歉。

179
00:09:01,870 --> 00:09:02,480
抱歉。

180
00:09:02,480 --> 00:09:03,130
抱歉。

181
00:09:03,130 --> 00:09:03,950
>> 罷工四人。

182
00:09:03,950 --> 00:09:04,360
我走了。

183
00:09:04,360 --> 00:09:05,280
抱歉。

184
00:09:05,280 --> 00:09:06,500
抱歉。

185
00:09:06,500 --> 00:09:07,490
抱歉。

186
00:09:07,490 --> 00:09:12,352
對不起，讓誰的人
要編輯這個發瘋。

187
00:09:12,352 --> 00:09:13,280
>> 抱歉。

188
00:09:13,280 --> 00:09:13,880
抱歉。

189
00:09:13,880 --> 00:09:15,080
抱歉。

190
00:09:15,080 --> 00:09:15,680
抱歉。

191
00:09:15,680 --> 00:09:16,280
>> 揚聲器1：幹得好。

192
00:09:16,280 --> 00:09:17,530
這是真的做得很好。

193
00:09:17,530 --> 00:09:18,430