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