1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[音乐播放]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID马兰：这是CS50。

5
00:00:14,010 --> 00:00:18,090
这是二者的开始和
end--像literally--差不多结束

6
00:00:18,090 --> 00:00:18,825
六个星期。

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> 我想我会分享
一个有趣的事实点点。

9
00:00:22,640 --> 00:00:25,370
我从一本拉到了
过去学期的数据集。

10
00:00:25,370 --> 00:00:29,710
你可能还记得，我们要求你在每个
P组的形式，如果你已经在网上看过

11
00:00:29,710 --> 00:00:31,580
或者，如果你已经亲自出席。

12
00:00:31,580 --> 00:00:33,020
这里是数据。

13
00:00:33,020 --> 00:00:34,710
所以今天是非常可预测性。

14
00:00:34,710 --> 00:00:37,126
但是，我们想花一点
然而时间与您联系。

15
00:00:37,126 --> 00:00:40,599
有人想猜测为什么这个
图中是那么的锯齿，上下，上下，

16
00:00:40,599 --> 00:00:41,265
所以一贯？

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
做什么每个峰
和波谷代表什么？

19
00:00:45,130 --> 00:00:46,005
>> 听众：[听不清]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID马兰：确实是这样。

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
而更有趣的是，上帝保佑，
我们举行一次讲座上周五

24
00:00:55,480 --> 00:00:58,960
在学期的开始，
这就是我们看到发生了什么。

25
00:00:58,960 --> 00:01:03,430
所以今天，我们参加了位
更多关于数据结构。

26
00:01:03,430 --> 00:01:06,660
并给你更多的是固体
对问题的思维模式五，

27
00:01:06,660 --> 00:01:07,450
这就是现在了。

28
00:01:07,450 --> 00:01:10,817
拼写错误，其中，我们将
交给你一个文本文件，大约10万

29
00:01:10,817 --> 00:01:12,650
再加上英语单词，
你将有

30
00:01:12,650 --> 00:01:17,770
弄清楚如何巧妙地加载它们
入存储器，到RAM中，使用一些数据

31
00:01:17,770 --> 00:01:19,330
您所选择的结构。

32
00:01:19,330 --> 00:01:22,470
>> 现在，这样的一个数据结构可以
是，但可能不应该，

33
00:01:22,470 --> 00:01:25,630
在相当简单的链表，
这是我们去年推出的时间。

34
00:01:25,630 --> 00:01:29,220
和一个链表至少有
1优势的阵列。

35
00:01:29,220 --> 00:01:32,096
什么是一个优点
链表可以说是？

36
00:01:32,096 --> 00:01:32,950
>> 听众：插入。

37
00:01:32,950 --> 00:01:33,908
>> DAVID马兰：插入。

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
你是什​​么意思？

40
00:01:35,196 --> 00:01:37,872
>> 听众：任何位置
名单[听不清]。

41
00:01:37,872 --> 00:01:38,770
>> DAVID马兰：好。

42
00:01:38,770 --> 00:01:42,090
所以，你可以插入一个元素的地方
要在列表的中间

43
00:01:42,090 --> 00:01:45,490
无需洗牌什么，
我们得出的结论，在我们的分类

44
00:01:45,490 --> 00:01:47,630
讨论，是不是
一定是好事，

45
00:01:47,630 --> 00:01:51,200
因为它需要时间来实际移动
所有这些人的左边或右边。

46
00:01:51,200 --> 00:01:55,540
所以用一个链表，你可以
刚分配使用malloc，一个新的节点，

47
00:01:55,540 --> 00:01:58,385
然后更新了几个
pointers--二，三次手术max--

48
00:01:58,385 --> 00:02:01,480
而我们能够插槽人
中的任意位置成一个列表。

49
00:02:01,480 --> 00:02:03,550
>> 还有什么是有利的
关于链表？

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
是吗？

52
00:02:05,659 --> 00:02:06,534
>> 听众：[听不清]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID马兰：完美。

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
完美的。

57
00:02:11,090 --> 00:02:12,070
这真是动力。

58
00:02:12,070 --> 00:02:15,100
和你没有犯，
事先，以一些固定的大小

59
00:02:15,100 --> 00:02:18,750
内存块，就像你会
用一个数组，则上行其中

60
00:02:18,750 --> 00:02:22,455
是，你只能分配上的节点
需求从而只用尽可能多的空间

61
00:02:22,455 --> 00:02:23,330
当你真正需要的。

62
00:02:23,330 --> 00:02:26,830
通过与数组相反，你可能会
一不小心分配太少。

63
00:02:26,830 --> 00:02:28,871
然后它只是去
是在颈部疼痛

64
00:02:28,871 --> 00:02:32,440
重新分配一个新的更大的阵列中，复制
一切都结束了，释放旧阵列，

65
00:02:32,440 --> 00:02:33,990
然后将您的业务。

66
00:02:33,990 --> 00:02:37,479
或者更糟的是，你可能会分配方式
更多的内存比实际需要，

67
00:02:37,479 --> 00:02:40,520
所以你将有一个非常
人烟稀少的阵列，可以这么说。

68
00:02:40,520 --> 00:02:44,350
>> 因此，一个链表为您提供了这些
活力和灵活性的优势

69
00:02:44,350 --> 00:02:46,080
与插入和缺失。

70
00:02:46,080 --> 00:02:48,000
但肯定要有付出了代价。

71
00:02:48,000 --> 00:02:50,000
其实，一个主题
探索对测验为零

72
00:02:50,000 --> 00:02:52,430
一对夫妇的取舍
我们已经看到迄今。

73
00:02:52,430 --> 00:02:56,161
那么，什么是付出了代价或
下行的链接列表？

74
00:02:56,161 --> 00:02:56,660
是啊。

75
00:02:56,660 --> 00:02:57,560
>> 听众：没有随机访问。

76
00:02:57,560 --> 00:02:58,809
>> DAVID马兰：没有随机访问。

77
00:02:58,809 --> 00:02:59,540
但谁在乎呢？

78
00:02:59,540 --> 00:03:01,546
随机存取听起来并不引人注目。

79
00:03:01,546 --> 00:03:02,421
>> 听众：[听不清]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID马兰：没错。

82
00:03:05,740 --> 00:03:07,580
如果你想有
一定的算法 - 

83
00:03:07,580 --> 00:03:10,170
让我真正提出
在特定的二进制搜索，这

84
00:03:10,170 --> 00:03:12,600
是我们使用相当bit--
如果你没有随机访问，

85
00:03:12,600 --> 00:03:15,516
你不能这样做简单的算术题
找到喜欢的中间元件的

86
00:03:15,516 --> 00:03:16,530
和跳跃的权利吧。

87
00:03:16,530 --> 00:03:20,239
你代替不得不开始在所述第一
元素，并从左边线搜索

88
00:03:20,239 --> 00:03:22,780
向右如果你想找到
中间的或任何其他元件。

89
00:03:22,780 --> 00:03:24,410
>> 听众：它可能需要更多的内存。

90
00:03:24,410 --> 00:03:25,040
>> DAVID马兰：需要更多的内存。

91
00:03:25,040 --> 00:03:27,464
哪里是额外的
成本从内存中来？

92
00:03:27,464 --> 00:03:28,339
>> 听众：[听不清]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID马兰：没错。

95
00:03:33,440 --> 00:03:35,679
在这里这种情况下，我们有
链表为整数，

96
00:03:35,679 --> 00:03:37,470
但我们正在加倍
的内存量

97
00:03:37,470 --> 00:03:39,680
我们需要同时存储这些指针。

98
00:03:39,680 --> 00:03:42,090
现在少了一个大问题，因为
您的结构得到较大

99
00:03:42,090 --> 00:03:45,320
与你存储不是一个数字，但
也许学生或其他物体。

100
00:03:45,320 --> 00:03:46,880
但有一点毫无疑问依然存在。

101
00:03:46,880 --> 00:03:49,421
等数的操作的
上链表被称为

102
00:03:49,421 --> 00:03:50,570
是N--线性的大O。

103
00:03:50,570 --> 00:03:54,730
之类的东西插入或搜索
或缺失的情况下的元素

104
00:03:54,730 --> 00:03:57,720
正好是在最末端
无论是排序或不列表。

105
00:03:57,720 --> 00:04:01,167
>> 有时候，你可能会得到幸运和
这些操作使下界

106
00:04:01,167 --> 00:04:04,250
也可能是恒定的时间，如果你
一直在寻找的第一个元素，

107
00:04:04,250 --> 00:04:05,070
例如。

108
00:04:05,070 --> 00:04:09,360
但最终，我们承诺
实现了制胜法宝

109
00:04:09,360 --> 00:04:12,630
数据结构，或
一些近似物，

110
00:04:12,630 --> 00:04:14,290
通过固定时间的方式。

111
00:04:14,290 --> 00:04:17,579
我们可以发现元素或添加元素
或删除列表中的元素？

112
00:04:17,579 --> 00:04:19,059
我们将很很快就会看到。

113
00:04:19,059 --> 00:04:21,100
而事实证明，一个
我们的机制

114
00:04:21,100 --> 00:04:23,464
要开始用至今，
在P年利用设置5，

115
00:04:23,464 --> 00:04:24,630
实际上是非常熟悉的。

116
00:04:24,630 --> 00:04:27,430
例如，如果这是一串
考试图书，其中每一个

117
00:04:27,430 --> 00:04:29,660
有一个学生的第一
它的名字和姓氏，

118
00:04:29,660 --> 00:04:31,820
我去接他们从
在考试结束后，

119
00:04:31,820 --> 00:04:33,746
而且他们都非常
多以随机的顺序，

120
00:04:33,746 --> 00:04:36,370
我们要着手整理
这些考试，因此一旦分级

121
00:04:36,370 --> 00:04:38,661
它只是一个极大的方便，
快交出他们回来了

122
00:04:38,661 --> 00:04:40,030
学生按字母顺序排列。

123
00:04:40,030 --> 00:04:42,770
什么你的直觉会
一摞这样的考试？

124
00:04:42,770 --> 00:04:45,019
>> 好吧，如果你像我一样，你
可以看出这是米，

125
00:04:45,019 --> 00:04:48,505
所以我要那种把这个成，
如果这是我的表或我的楼，

126
00:04:48,505 --> 00:04:50,650
我的东西蔓延
out--或我的数组really--

127
00:04:50,650 --> 00:04:52,210
我可以把所有的小姐在那里。

128
00:04:52,210 --> 00:04:52,710
呵呵。

129
00:04:52,710 --> 00:04:55,020
这里有一个答，所以我可能
把作为过来。

130
00:04:55,020 --> 00:04:55,520
呵呵。

131
00:04:55,520 --> 00:04:57,980
这里的另一个A.我要去
把该在这里。

132
00:04:57,980 --> 00:05:02,490
这里有一个Z.这里是另一个M.所以
我可能会开始做桩这样的。

133
00:05:02,490 --> 00:05:06,620
然后，也许我以后会​​去
样的，非常挑剔-LY排序

134
00:05:06,620 --> 00:05:07,710
个别桩。

135
00:05:07,710 --> 00:05:11,300
但问题是，我想看看
那个我手输入

136
00:05:11,300 --> 00:05:14,016
我会做一些计算
基于该输入决定。

137
00:05:14,016 --> 00:05:15,640
如果以A开头，把它放在那边。

138
00:05:15,640 --> 00:05:18,980
如果它以Z开头，把它放在
在那里，一切都在两者之间。

139
00:05:18,980 --> 00:05:22,730
>> 因此，这是一种技术，是
一般被称为hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
这通常意味着要为
输入，并使用该输入来计算

141
00:05:26,550 --> 00:05:30,940
的值，通常是一个数字，那
号为索引到一个存储

142
00:05:30,940 --> 00:05:32,260
容器，如一个数组。

143
00:05:32,260 --> 00:05:35,490
所以，换句话说，我可能有一个
散列函数，像我一样在我的脑海，

144
00:05:35,490 --> 00:05:37,940
如果我看到有人的
谁的名字开始与A，

145
00:05:37,940 --> 00:05:40,190
我要去映射
零在我的脑海。

146
00:05:40,190 --> 00:05:44,160
如果我看到有人用Z，我
要映射至25日在我头上

147
00:05:44,160 --> 00:05:46,220
然后它放入
最后最桩。

148
00:05:46,220 --> 00:05:50,990
>> 现在，如果你觉得不是我的大脑
但一个C程序，有什么数字可能

149
00:05:50,990 --> 00:05:53,170
你靠什么来实现同样的结果呢？

150
00:05:53,170 --> 00:05:55,594
换句话说，如果
有ASCII字符A，

151
00:05:55,594 --> 00:05:57,510
你如何确定
什么桶把它呢？

152
00:05:57,510 --> 00:05:59,801
你可能不希望
把它放进水桶65，这

153
00:05:59,801 --> 00:06:01,840
会像那边
没有很好的理由。

154
00:06:01,840 --> 00:06:04,320
你在哪里要放
在它的ASCII值是多少？

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
你想去哪里做的ASCII
值拿出一个更聪明的水桶

157
00:06:08,920 --> 00:06:09,480
把它呢？

158
00:06:09,480 --> 00:06:10,206
>> 听众：负A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID马兰：是啊。

160
00:06:10,956 --> 00:06:13,190
因此，减去或减
特别是65，如果是

161
00:06:13,190 --> 00:06:18,240
资本A.或98，如果
这是一个小写。

162
00:06:18,240 --> 00:06:21,300
所以这将允许我们，很
简单，非常算术，

163
00:06:21,300 --> 00:06:23,260
把东西放到这样一个水桶。

164
00:06:23,260 --> 00:06:26,010
所以，事实证明，我们实际上做
这个问题，以及即使有测验。

165
00:06:26,010 --> 00:06:29,051
>> 所以，你可能还记得你的盘旋
封面上的教学老乡的名字。

166
00:06:29,051 --> 00:06:32,270
而TF的名字被组织
到这些列的字母顺序，

167
00:06:32,270 --> 00:06:34,400
好了，不管你信不信，
当所有80加上我们

168
00:06:34,400 --> 00:06:37,800
聚在一起的那天晚上等级，
在我们的分级过程中的最后一步

169
00:06:37,800 --> 00:06:41,830
是散列测验变成了大
地板在[听不清]空间

170
00:06:41,830 --> 00:06:45,110
并奠定了大家的测验出来
在他们TF的确切顺序

171
00:06:45,110 --> 00:06:47,700
在盖的名称，因为
那么它对于我们来说容易得多

172
00:06:47,700 --> 00:06:51,290
通过使用线性搜索
搜索或某种聪明

173
00:06:51,290 --> 00:06:54,050
对于TF找到他或
她的学生的测验。

174
00:06:54,050 --> 00:06:56,060
>> 所以这个想法散列
你将看到的是

175
00:06:56,060 --> 00:07:00,520
功能相当强大实际上是非常
司空见惯，非常直观，

176
00:07:00,520 --> 00:07:03,000
很像也许是分而
征服是零一周。

177
00:07:03,000 --> 00:07:05,250
我快进到黑客马拉松
几年前。

178
00:07:05,250 --> 00:07:08,040
这是Zamyla和一对夫妇的
其他工作人员的问候学生

179
00:07:08,040 --> 00:07:09,030
因为他们进来了。

180
00:07:09,030 --> 00:07:12,680
我们有一大堆折叠
表中有与名称标签。

181
00:07:12,680 --> 00:07:15,380
我们有名称标签组织
有喜欢当那边

182
00:07:15,380 --> 00:07:16,690
和ZS的那边。

183
00:07:16,690 --> 00:07:20,350
这样一来，课题组的一个非常巧妙
写这个的说明

184
00:07:20,350 --> 00:07:21,030
为天。

185
00:07:21,030 --> 00:07:24,480
而在本学期的第12周
所有的非常有意义，每个人都

186
00:07:24,480 --> 00:07:25,310
知道该怎么做。

187
00:07:25,310 --> 00:07:27,900
但是，任何时候，你已经
排队以同样的方式，

188
00:07:27,900 --> 00:07:30,272
你实现
散列相同的概念。

189
00:07:30,272 --> 00:07:31,730
因此，让我们正式那么一点点。

190
00:07:31,730 --> 00:07:32,890
这里是一个数组。

191
00:07:32,890 --> 00:07:36,820
它绘制的是一个小
宽只是描绘，直观，

192
00:07:36,820 --> 00:07:38,920
我们不妨把字符串
在这样的事情。

193
00:07:38,920 --> 00:07:41,970
这阵
显然是大小共26件。

194
00:07:41,970 --> 00:07:43,935
而且东西被称为
表随意。

195
00:07:43,935 --> 00:07:48,930
但是，这仅仅是一个艺术家的再现
什么样的哈希表可能。

196
00:07:48,930 --> 00:07:52,799
>> 这样一个哈希表现在将要
是一个更高层次的数据结构。

197
00:07:52,799 --> 00:07:54,840
在一天结束时
我们即将看到你

198
00:07:54,840 --> 00:07:58,700
可以实现一个哈希表，该表
很像登机

199
00:07:58,700 --> 00:08:02,059
在黑客马拉松就像这样
表用于排序的考试书籍。

200
00:08:02,059 --> 00:08:03,850
但一个哈希表
这个排序高水平的

201
00:08:03,850 --> 00:08:08,250
概念，可以使用一个数组
在底层实现它，

202
00:08:08,250 --> 00:08:11,890
或者它可以使用一个长列表，或者甚至
也许一些其他的数据结构。

203
00:08:11,890 --> 00:08:15,590
而现在这就是theme--回吐
一些基本的成分

204
00:08:15,590 --> 00:08:18,310
就像一个数组，这个建筑
现在阻止长名单

205
00:08:18,310 --> 00:08:21,740
，看到什么，我们可以建立
关于这些的顶端，像成分

206
00:08:21,740 --> 00:08:26,550
成一个配方，使得越来越多的
有趣的和有用的最终结果。

207
00:08:26,550 --> 00:08:28,680
>> 所以用哈希表
我们可以实现它

208
00:08:28,680 --> 00:08:32,540
在内存中形象地这样，但
怎么可能它实际上被编码吗？

209
00:08:32,540 --> 00:08:33,789
好吧，也许因为简单地说就是这个。

210
00:08:33,789 --> 00:08:38,270
如果产能全部大写，只是
一些constant--比如26，

211
00:08:38,270 --> 00:08:42,030
为alphabet--的26个字母
我可以叫我的变量表，

212
00:08:42,030 --> 00:08:45,630
我也许会说，我要去
把炭明星在那里，或字符串。

213
00:08:45,630 --> 00:08:49,880
因此，它是如此简单，如果你
要实现一个哈希表。

214
00:08:49,880 --> 00:08:51,490
然而，这真的只是一个数组。

215
00:08:51,490 --> 00:08:53,198
但同样，一个散列
表是现在我们所会

216
00:08:53,198 --> 00:08:57,470
调用一个抽象数据类型，这只是
排序在最前面的概念分层

217
00:08:57,470 --> 00:09:00,780
东西更现实
现在喜欢一个数组。

218
00:09:00,780 --> 00:09:02,960
>> 现在，该怎么办才好
关于解决问题？

219
00:09:02,960 --> 00:09:06,980
嗯，刚才我已经奢侈
这里有足够的表空间

220
00:09:06,980 --> 00:09:09,460
这样我就可以把
测验的任何地方我想要的。

221
00:09:09,460 --> 00:09:10,620
这样可能会去这里。

222
00:09:10,620 --> 00:09:12,100
ZS可能会去这里。

223
00:09:12,100 --> 00:09:13,230
小姐可能会去这里。

224
00:09:13,230 --> 00:09:14,740
然后我有一些额外的空间。

225
00:09:14,740 --> 00:09:18,740
但是，这是一个有点作弊权
因为现在这个表，如果我真的

226
00:09:18,740 --> 00:09:22,720
想到这是一个数组，只是
一些将要固定的尺寸。

227
00:09:22,720 --> 00:09:25,380
>> 所以，从技术上说，如果我拉
了另一名学生的测验

228
00:09:25,380 --> 00:09:28,490
看看，哦，这个人的
名称与A开始过，

229
00:09:28,490 --> 00:09:30,980
我有点想要把它放在那里。

230
00:09:30,980 --> 00:09:34,740
但是，当我把它放在那里，如果
这个表确实表示一个数组，

231
00:09:34,740 --> 00:09:37,840
我会被覆盖或重挫
谁该学生的测验是。

232
00:09:37,840 --> 00:09:38,340
对不对？

233
00:09:38,340 --> 00:09:41,972
如果这是一个数组，只有一件事可以
走在这些细胞或元件。

234
00:09:41,972 --> 00:09:43,680
所以，我种有
挑选。

235
00:09:43,680 --> 00:09:45,735
>> 刚才那种下面我
被骗了，做这个还是我

236
00:09:45,735 --> 00:09:47,526
只是一种堆叠
他们在彼此之上。

237
00:09:47,526 --> 00:09:49,170
但是，这并不是要在代码中飞翔。

238
00:09:49,170 --> 00:09:52,260
那么，我能放
第二个学生的名字

239
00:09:52,260 --> 00:09:54,964
是A，如果所有我是这样的
可用的表空间？

240
00:09:54,964 --> 00:09:57,880
而且我用三个插槽，它
貌似有只是少数人。

241
00:09:57,880 --> 00:09:58,959
你该怎么办？

242
00:09:58,959 --> 00:09:59,834
听众：[听不清]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID马兰：是啊。

245
00:10:01,315 --> 00:10:02,370
也许我们只是保持简单。

246
00:10:02,370 --> 00:10:02,660
对不对？

247
00:10:02,660 --> 00:10:04,243
它不适合在这里我想把它。

248
00:10:04,243 --> 00:10:07,450
所以我打算把它放在
技术上，其中A，B会去。

249
00:10:07,450 --> 00:10:09,932
当然，现在，我开始
画自己陷入了困境。

250
00:10:09,932 --> 00:10:11,890
如果我去一个学生
他的名字实际上是B，

251
00:10:11,890 --> 00:10:14,840
现在乙将要被移动一点点
未来，为可能发生的事情，是的，

252
00:10:14,840 --> 00:10:17,530
如果这是一个B中，现在它已去这里。

253
00:10:17,530 --> 00:10:20,180
>> 所以这非常迅速
可能成为问题，

254
00:10:20,180 --> 00:10:23,850
但它是一个技术，实际上是
被称为线性探测，

255
00:10:23,850 --> 00:10:26,650
因此你只要考虑你
阵列是沿着线。

256
00:10:26,650 --> 00:10:29,680
正中下怀，你探头或
检查每个可用的元素

257
00:10:29,680 --> 00:10:31,360
寻找一个备有现货。

258
00:10:31,360 --> 00:10:34,010
而且只要你找到
1，你在那里将其删除。

259
00:10:34,010 --> 00:10:38,390
>> 现在，这个价格现在正在支付
这个解决方案是什么？

260
00:10:38,390 --> 00:10:41,300
我们有一个固定大小的数组，
当我插入的名字

261
00:10:41,300 --> 00:10:44,059
进去，至少在最初阶段，有什么
插入的运行时间

262
00:10:44,059 --> 00:10:46,350
为把学生
在右边的桶测验？

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
什么大O？

265
00:10:50,002 --> 00:10:51,147
>> 听众：N。

266
00:10:51,147 --> 00:10:52,480
DAVID马兰：我听说的n大O。

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
事实并非如此。

269
00:10:54,300 --> 00:10:56,490
但我们将梳理出
为什么在短短的一瞬间。

270
00:10:56,490 --> 00:10:57,702
还有什么会是什么？

271
00:10:57,702 --> 00:10:58,755
>> 听众：[听不清]

272
00:10:58,755 --> 00:11:00,380
DAVID马兰：让我做视觉。

273
00:11:00,380 --> 00:11:04,720
因此，假设这是字母S.

274
00:11:04,720 --> 00:11:05,604
>> 听众：这是之一。

275
00:11:05,604 --> 00:11:06,520
DAVID马兰：这是之一。

276
00:11:06,520 --> 00:11:06,710
对不对？

277
00:11:06,710 --> 00:11:08,950
这是一个数组，它
意味着我们有随机访问。

278
00:11:08,950 --> 00:11:11,790
如果我们认为这
零，这为25，

279
00:11:11,790 --> 00:11:13,800
我们认识到，
哦，这是我的输入S，

280
00:11:13,800 --> 00:11:16,350
我当然可以转换
S，一个ASCII字符，

281
00:11:16,350 --> 00:11:18,540
到一个相应的数字
零到25之间

282
00:11:18,540 --> 00:11:20,910
然后立即
把它原来的位置。

283
00:11:20,910 --> 00:11:26,120
>> 但当然，当我到达
第二个人谁的名字是A或B或C

284
00:11:26,120 --> 00:11:29,300
最后，如​​果我用了
线性探测作为我的解决方案，

285
00:11:29,300 --> 00:11:31,360
的运行时间
插入在最坏的情况下

286
00:11:31,360 --> 00:11:33,120
实际上是要下放成什么样？

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
我也听到了这里
正确的早期。

289
00:11:36,045 --> 00:11:36,920
听众：[听不清]

290
00:11:36,920 --> 00:11:41,620
DAVID马兰：所以这是正确一次
有一个足够大的数据集。

291
00:11:41,620 --> 00:11:44,410
这样，一方面，如果
阵列足够大

292
00:11:44,410 --> 00:11:48,287
和你的数据是稀疏的话，你
得到这个美丽的固定时间。

293
00:11:48,287 --> 00:11:50,620
但只要你开始
越来越多的元素，

294
00:11:50,620 --> 00:11:53,200
而只是统计上你
更多的人信

295
00:11:53,200 --> 00:11:56,030
A作为自己的名称或字母
B时，它可能潜在

296
00:11:56,030 --> 00:11:57,900
下放成更线性的。

297
00:11:57,900 --> 00:11:59,640
所以，不是很完美。

298
00:11:59,640 --> 00:12:00,690
所以，我们可以做的更好？

299
00:12:00,690 --> 00:12:03,210
>> 那么，什么是我们的
之前的解决方案时，我们

300
00:12:03,210 --> 00:12:06,820
希望有更多的比活力
像一个数组允许的？

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
听众：[听不清]

303
00:12:08,960 --> 00:12:10,030
DAVID马兰：没有介绍什么？

304
00:12:10,030 --> 00:12:10,530
是啊。

305
00:12:10,530 --> 00:12:11,430
这样一个链表。

306
00:12:11,430 --> 00:12:14,430
好吧，让我们看看一个链接
清单可能对我们不是做的。

307
00:12:14,430 --> 00:12:17,630
那么，让我建议大家
画图如下。

308
00:12:17,630 --> 00:12:19,620
现在这是一个不同的
从例图

309
00:12:19,620 --> 00:12:24,750
从不同的文本，实际上，这
实际上是用粒度31的阵列。

310
00:12:24,750 --> 00:12:28,220
而笔者简单
决定散列字符串

311
00:12:28,220 --> 00:12:32,430
不基于该人的姓名，
但基于其生日。

312
00:12:32,430 --> 00:12:35,680
不论该月，他们得出
如果你在第一次一个月的正在诞生

313
00:12:35,680 --> 00:12:39,580
或一个月的31日，笔者
基于该值会出现乱码，

314
00:12:39,580 --> 00:12:44,154
从而被散布的名字出一个位
不仅仅是26点可能会允许。

315
00:12:44,154 --> 00:12:47,320
也许这是一个小更均匀
比用字母去，

316
00:12:47,320 --> 00:12:50,236
当然，因为有可能
更多的人在世界上的名字

317
00:12:50,236 --> 00:12:54,020
开始的被肯定比
其他一些英文字母。

318
00:12:54,020 --> 00:12:56,380
所以，也许这是一个小
更均匀，假定

319
00:12:56,380 --> 00:12:58,640
均匀分布
的婴儿跨越了一个月。

320
00:12:58,640 --> 00:12:59,990
>> 但是，当然，这仍然是不完美的。

321
00:12:59,990 --> 00:13:00,370
对不对？

322
00:13:00,370 --> 00:13:01,370
我们有冲突。

323
00:13:01,370 --> 00:13:04,680
多人在这
数据结构仍然

324
00:13:04,680 --> 00:13:08,432
具有相同的出生日期的至少
你不论一个月。

325
00:13:08,432 --> 00:13:09,640
但什么笔者做了什么？

326
00:13:09,640 --> 00:13:13,427
好吧，看来我们有一个数组
在左侧的垂直绘制，

327
00:13:13,427 --> 00:13:15,010
但是这只是一个艺术家的再现。

328
00:13:15,010 --> 00:13:18,009
不要紧，什么方向，你
画一个数组，它仍然是一个数组。

329
00:13:18,009 --> 00:13:20,225
这是什么的显然是一个数组？

330
00:13:20,225 --> 00:13:21,500
>> 听众：链表。

331
00:13:21,500 --> 00:13:21,650
>> DAVID马兰：是啊。

332
00:13:21,650 --> 00:13:23,490
它看起来像它的一个
阵列的链表。

333
00:13:23,490 --> 00:13:26,490
如此反复，这点排序
利用这些数据结构现在的

334
00:13:26,490 --> 00:13:28,550
作为成分更多
有趣的解决方案，

335
00:13:28,550 --> 00:13:30,862
你完全可以采取
基本一样的阵列，

336
00:13:30,862 --> 00:13:33,320
然后拿更多的东西
有趣像一个链表

337
00:13:33,320 --> 00:13:36,660
甚至将它们组合成一个更
更有趣的数据结构。

338
00:13:36,660 --> 00:13:39,630
事实上，这也将
被称为哈希表

339
00:13:39,630 --> 00:13:42,610
由此，阵列是
真哈希表，

340
00:13:42,610 --> 00:13:45,600
但是哈希表中有
链，可以这么说，

341
00:13:45,600 --> 00:13:50,220
可增大或缩小基础上，
你想要的元素的数量插入。

342
00:13:50,220 --> 00:13:52,990
>> 现在，因此，什么是
在运行的时候吗？

343
00:13:52,990 --> 00:13:58,030
如果我要插入人
他的生日是10月31日

344
00:13:58,030 --> 00:13:59,040
在那里他或她去吗？

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
行。

347
00:14:01,030 --> 00:14:02,819
在最底层的地方说31。

348
00:14:02,819 --> 00:14:03,610
这就是完美的。

349
00:14:03,610 --> 00:14:05,060
那是一定的时间。

350
00:14:05,060 --> 00:14:08,760
但是，如果我们发现了什么别人
他的生日，让我们来看看，

351
00:14:08,760 --> 00:14:10,950
十月，十一月，12月31日？

352
00:14:10,950 --> 00:14:12,790
哪里是他或她会去吗？

353
00:14:12,790 --> 00:14:13,290
同样的事情。

354
00:14:13,290 --> 00:14:13,970
两步虽然。

355
00:14:13,970 --> 00:14:15,303
这是恒定的，虽然不是吗？

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
行。

358
00:14:16,860 --> 00:14:17,840
目前，它是。

359
00:14:17,840 --> 00:14:20,570
但在一般情况下，
越来越多的人加入我们，

360
00:14:20,570 --> 00:14:23,790
概率，我们要
得到越来越多的碰撞。

361
00:14:23,790 --> 00:14:26,820
>> 现在，这是一个小
更好，因为在技术上

362
00:14:26,820 --> 00:14:34,580
现在我的连锁店可以在
在最坏的情况下多久？

363
00:14:34,580 --> 00:14:38,890
如果我插入N多人进入这个多
复杂的数据结构，N多人，

364
00:14:38,890 --> 00:14:41,080
在最坏的情况下，它会为n。

365
00:14:41,080 --> 00:14:41,815
为什么呢？

366
00:14:41,815 --> 00:14:43,332
>> 听众：因为如果每个人都
有相同的生日，

367
00:14:43,332 --> 00:14:44,545
他们将成为一条线。

368
00:14:44,545 --> 00:14:45,420
DAVID马兰：完美。

369
00:14:45,420 --> 00:14:47,480
这可能是一个有点做作，
但真正在最坏的情况下，

370
00:14:47,480 --> 00:14:50,117
如果每个人都拥有相同的生日，
给你的投入，

371
00:14:50,117 --> 00:14:51,950
你将有一个
大量的长链。

372
00:14:51,950 --> 00:14:54,241
所以，你可以把它称为一个
哈希表，但实际上它是

373
00:14:54,241 --> 00:14:56,810
只是一个大规模的链表
一大堆浪费的空间。

374
00:14:56,810 --> 00:15:00,460
但在一般情况下，如果我们假定
至少生日是uniform--

375
00:15:00,460 --> 00:15:01,750
它可能不是。

376
00:15:01,750 --> 00:15:02,587
我正在做这件事。

377
00:15:02,587 --> 00:15:04,420
但是，如果我们假定，对于
就事论事

378
00:15:04,420 --> 00:15:07,717
它们是，那么在理论上，如果
这是垂直的表示

379
00:15:07,717 --> 00:15:11,050
数组的，那么希望你
将得到的是，你知道链，

380
00:15:11,050 --> 00:15:15,880
大致相同的长度，其中每个
这些代表月中的某一天。

381
00:15:15,880 --> 00:15:19,930
>> 现在，如果有31天的月份，
这意味着我的运行时间真的

382
00:15:19,930 --> 00:15:25,230
为n超过31大O，这
感觉比线性好。

383
00:15:25,230 --> 00:15:27,950
但是，什么是我们的一个
承诺一两个星期

384
00:15:27,950 --> 00:15:31,145
以前，每当它来表达
一个算法的运行时间？

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
刚刚只看高次项。

387
00:15:35,190 --> 00:15:35,690
对不对？

388
00:15:35,690 --> 00:15:37,400
31绝对是有帮助的。

389
00:15:37,400 --> 00:15:39,610
但是，这仍然是n个大O。

390
00:15:39,610 --> 00:15:41,730
但主题之一
问题设置5

391
00:15:41,730 --> 00:15:43,950
将是对
承认绝对的，

392
00:15:43,950 --> 00:15:47,320
渐近，理论上
这种数据结构

393
00:15:47,320 --> 00:15:50,470
没有比刚刚好
一台庞大的链表。

394
00:15:50,470 --> 00:15:53,550
而事实上，在最坏的情况下，这
哈希表可能下放成。

395
00:15:53,550 --> 00:15:57,620
>> 但在现实世界中，我们人类
那自己的Mac或PC或其他

396
00:15:57,620 --> 00:16:01,240
而正在运行真实世界
软件在真实世界中的数据，

397
00:16:01,240 --> 00:16:03,260
该算法你要选哪个？

398
00:16:03,260 --> 00:16:09,180
而其中，需要结束步骤或
一种采用N以31级分

399
00:16:09,180 --> 00:16:12,900
找一些数据块或
找了一些资料？

400
00:16:12,900 --> 00:16:16,580
我的意思是，绝对是31品牌
在现实世界中的差。

401
00:16:16,580 --> 00:16:18,540
这是快31倍。

402
00:16:18,540 --> 00:16:20,880
而我们人类是肯定
要明白这一点。

403
00:16:20,880 --> 00:16:23,004
>> 因此，实现二分法
之间居然有

404
00:16:23,004 --> 00:16:25,920
说起理论上的东西
和渐近这无疑

405
00:16:25,920 --> 00:16:28,760
具有价值，因为我们已经看到，
但在现实世界中，

406
00:16:28,760 --> 00:16:32,930
如果你关心只是使
人类对幸福的通用输入，

407
00:16:32,930 --> 00:16:36,010
你很可能要接受
事实证明，是的，这是线性的，

408
00:16:36,010 --> 00:16:38,360
但它的速度更快31倍
比线性可能。

409
00:16:38,360 --> 00:16:41,610
而且更重要的是，我们不只是要
做一些乱像一个生日，

410
00:16:41,610 --> 00:16:44,030
我们可以花一点
更多的时间和聪明

411
00:16:44,030 --> 00:16:47,140
想想我们可能会做，
定一个人的名字，也许

412
00:16:47,140 --> 00:16:50,130
他们的出生日期相结合的
成分搞清楚的东西

413
00:16:50,130 --> 00:16:52,720
这是真正的多
均匀，少锯齿，

414
00:16:52,720 --> 00:16:56,250
这么说不是这幅画
目前表明它可能是。

415
00:16:56,250 --> 00:16:57,750
在代码中，我们如何才能实现呢？

416
00:16:57,750 --> 00:17:00,280
那么，让我建议大家
只是借用一些语法，我们已经

417
00:17:00,280 --> 00:17:01,799
使用几次迄今。

418
00:17:01,799 --> 00:17:03,590
我要去定义
一节点，该节点再次

419
00:17:03,590 --> 00:17:06,812
是一个通用术语，只是一些
容器为一些数据结构。

420
00:17:06,812 --> 00:17:09,020
我要建议
字符串会在那里。

421
00:17:09,020 --> 00:17:11,369
但是，我们要开始服用
这些培训轮子掉了。

422
00:17:11,369 --> 00:17:13,230
>> 没有更多的CS50库
真的，除非你想

423
00:17:13,230 --> 00:17:15,230
将其用于您的最终
项目，这是好的，

424
00:17:15,230 --> 00:17:18,569
但现在我们要拉回来了
窗帘，说这只是一个char明星。

425
00:17:18,569 --> 00:17:22,069
所以这个词有将是
有问题的人的名字。

426
00:17:22,069 --> 00:17:25,079
现在我有一个链接
这里下一个节点

427
00:17:25,079 --> 00:17:28,170
使这些代表
每个节点

428
00:17:28,170 --> 00:17:30,950
在链中，潜在地，
的一个链表。

429
00:17:30,950 --> 00:17:34,090
>> 现在该怎么办，我宣布
哈希表本身？

430
00:17:34,090 --> 00:17:36,660
我如何申报这整个结构？

431
00:17:36,660 --> 00:17:40,960
好了，说真的，就像我用一个指针
以列表的只是第一元件

432
00:17:40,960 --> 00:17:44,510
之前，同样我能说
我只需要一堆指针

433
00:17:44,510 --> 00:17:46,270
实现这整个哈希表。

434
00:17:46,270 --> 00:17:49,484
我将有一个数组
所谓表为哈希表。

435
00:17:49,484 --> 00:17:50,900
这将是规模生产能力。

436
00:17:50,900 --> 00:17:52,525
这就是很多元素可以适应它。

437
00:17:52,525 --> 00:17:56,180
并且每个在此这些元素的
阵列将是一个节点的明星。

438
00:17:56,180 --> 00:17:56,810
为什么呢？

439
00:17:56,810 --> 00:18:00,160
那么，每个这张照片，就是我
执行哈希表作为

440
00:18:00,160 --> 00:18:04,330
有效地在一开始仅仅是
这个数组，我们已经垂直绘制，

441
00:18:04,330 --> 00:18:06,820
其每个的平方
代表一个指针。

442
00:18:06,820 --> 00:18:09,170
那那些有斜杠
通过他们只是空。

443
00:18:09,170 --> 00:18:11,410
和那些有
箭头要正确

444
00:18:11,410 --> 00:18:16,140
在实际指向实际的节点，
人体工程学的链接列表的开始。

445
00:18:16,140 --> 00:18:19,050
>> 所以在这里的话，我们怎么可能
实现一个哈希表，该表

446
00:18:19,050 --> 00:18:21,580
实现独立的链接。

447
00:18:21,580 --> 00:18:22,840
现在，我们可以做的更好？

448
00:18:22,840 --> 00:18:25,632
好吧，我答应最后一次
我们可以实现一定的时间。

449
00:18:25,632 --> 00:18:27,381
我种了你
固定的时间在这里，

450
00:18:27,381 --> 00:18:29,850
但后来说不是真的
固定的时间，因为它仍

451
00:18:29,850 --> 00:18:31,890
依赖于总上
元件的数目

452
00:18:31,890 --> 00:18:34,500
你输入到
的数据结构。

453
00:18:34,500 --> 00:18:35,980
但是，假如我们这样做。

454
00:18:35,980 --> 00:18:39,550
让我回到屏幕在这里。

455
00:18:39,550 --> 00:18:44,520
也让我在这里预测这件事，清楚
在屏幕上，并且假设我这样做。

456
00:18:44,520 --> 00:18:49,300
假设我想插入的名字
Daven在为我的数据结构。

457
00:18:49,300 --> 00:18:52,100
>> 所以我想插入一个字符串
Daven成的数据结构。

458
00:18:52,100 --> 00:18:54,370
如果我不使用什么
哈希表，但我用

459
00:18:54,370 --> 00:18:56,980
一些更树状
就像一个家族树，其中

460
00:18:56,980 --> 00:18:59,670
你有一些根本的
顶部，然后节点和叶

461
00:18:59,670 --> 00:19:01,440
那去向下和向外。

462
00:19:01,440 --> 00:19:04,450
假设这时，我才
要插入Daven的

463
00:19:04,450 --> 00:19:06,430
到什么是当前一个空列表。

464
00:19:06,430 --> 00:19:09,780
我要做到以下几点：我
要在这个家庭创建节点

465
00:19:09,780 --> 00:19:15,170
树状数据结构，它看起来
有点像这样的，其中每一个

466
00:19:15,170 --> 00:19:19,640
矩形有，比方说，
现在26在里面的元素。

467
00:19:19,640 --> 00:19:21,650
和每个小区的
在这阵是怎么回事

468
00:19:21,650 --> 00:19:23,470
代表字母表的字母。

469
00:19:23,470 --> 00:19:28,190
>> 具体来说，我要去治疗
这是A，那么B，然后是C，则D，

470
00:19:28,190 --> 00:19:29,310
这一个在这里。

471
00:19:29,310 --> 00:19:32,940
所以这将有效地
代表字母D.

472
00:19:32,940 --> 00:19:36,040
但插入所有Daven年代
名字我需要做多一点。

473
00:19:36,040 --> 00:19:37,840
所以我首先要散列，可以这么说。

474
00:19:37,840 --> 00:19:41,049
我要去看看第一个字母
在Daven的这显然是一个D，

475
00:19:41,049 --> 00:19:42,840
我要去分配
看起来一个节点

476
00:19:42,840 --> 00:19:45,570
像this--一个大的矩形大
够以适应整个字母表。

477
00:19:45,570 --> 00:19:47,140
>> 现在D被完成。

478
00:19:47,140 --> 00:19:49,720
现在A. D-A-V-E-N是目标。

479
00:19:49,720 --> 00:19:51,220
所以，现在我什么都做的就是这一点。

480
00:19:51,220 --> 00:19:54,027
当我开始D的通知
没有指针那里。

481
00:19:54,027 --> 00:19:56,860
这是垃圾值的那一刻，
或者我可以把它初始化为空。

482
00:19:56,860 --> 00:19:59,630
不过，让我赶上去
这个想法建立一个树。

483
00:19:59,630 --> 00:20:04,260
让我分配一个又一个的这些
节点中有26个元素。

484
00:20:04,260 --> 00:20:05,150
>> 你知道吗？

485
00:20:05,150 --> 00:20:09,130
如果这仅仅是在存储器中的节点
我使用malloc创建，用一个struct

486
00:20:09,130 --> 00:20:11,240
因为我们很快就会看到，
我该怎么办this--

487
00:20:11,240 --> 00:20:14,450
我会从画一个箭头
这代表的D-下来的东西

488
00:20:14,450 --> 00:20:15,860
该新节点。

489
00:20:15,860 --> 00:20:19,240
而现在，第一个下一个
信Daven的名字，

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V--我要继续前进
并得出另一个节点是这样，

491
00:20:24,150 --> 00:20:30,150
由此，此处的V族元素，其
我们将绘制的instance--哎呦。

492
00:20:30,150 --> 00:20:31,020
我们不会画在那里。

493
00:20:31,020 --> 00:20:31,936
它会去这里。

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> 然后，我们要
认为这是V.

496
00:20:35,712 --> 00:20:44,920
再往下在这里我们要索引
下来从V到我们会考虑E.

497
00:20:44,920 --> 00:20:50,100
然后从这里，我们要
去这里有这些节点之一。

498
00:20:50,100 --> 00:20:52,930
现在我们有一个问题来回答。

499
00:20:52,930 --> 00:20:57,840
我需要以某种方式表明，
我们在字符串Daven的结束。

500
00:20:57,840 --> 00:20:59,490
所以，我可以把它空。

501
00:20:59,490 --> 00:21:02,670
>> 但是，如果我们有Daven的
全名也，其

502
00:21:02,670 --> 00:21:04,280
是，正如我们已经说过，达文波特？

503
00:21:04,280 --> 00:21:06,970
所以，如果Daven是什么
实际上是一个子串，

504
00:21:06,970 --> 00:21:08,960
一个更长的字符串的前缀？

505
00:21:08,960 --> 00:21:11,450
我们不能仅仅永久
什么也不说是怎么回事

506
00:21:11,450 --> 00:21:14,410
去那里，因为我们可以
切勿将像达文波特一个字

507
00:21:14,410 --> 00:21:15,840
入该数据结构

508
00:21:15,840 --> 00:21:19,560
>> 所以，我们可以做的是
把这些元素

509
00:21:19,560 --> 00:21:22,170
因为也许有两个
他们中的元素。

510
00:21:22,170 --> 00:21:24,810
一个是一个指针，的确，
因为我一直在做。

511
00:21:24,810 --> 00:21:27,100
所以每个这些框
不只是一个小区。

512
00:21:27,100 --> 00:21:29,855
但是，如果顶部
埃德蒙顿底部一个人的

513
00:21:29,855 --> 00:21:32,230
要为null，因为
有没有达文波特，只是还没有。

514
00:21:32,230 --> 00:21:34,197
如果那顶一个
为一些特殊的价值？

515
00:21:34,197 --> 00:21:36,530
而这将是一个小
很难得出它这种规模。

516
00:21:36,530 --> 00:21:38,130
但是，假如它只是一个复选标记。

517
00:21:38,130 --> 00:21:38,920
检查。

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N是一个字符串
在此数据结构中。

519
00:21:44,230 --> 00:21:48,350
>> 同时，如果我有更多的空间
在这里，我所能做的P-O-R-T，

520
00:21:48,350 --> 00:21:52,650
我可以把检查的节点
有字母T在最后。

521
00:21:52,650 --> 00:21:55,460
因此，这是一个大规模
复杂的外观的数据结构。

522
00:21:55,460 --> 00:21:57,210
和我的笔迹
肯定没有帮助。

523
00:21:57,210 --> 00:22:00,043
但是，如果我想插入的东西
否则，考虑一下我们会怎么做。

524
00:22:00,043 --> 00:22:03,370
如果我们希望把大卫，
我们会遵循同样的逻辑，D-A-V，

525
00:22:03,370 --> 00:22:08,802
但现在我想指出，在未来
元素不是从E，但是从我到D.

526
00:22:08,802 --> 00:22:10,760
因此，有将是
在这棵树多个节点。

527
00:22:10,760 --> 00:22:12,325
我们将不得不调用malloc更多。

528
00:22:12,325 --> 00:22:14,700
但是，我不想做一个
这幅画的一塌糊涂。

529
00:22:14,700 --> 00:22:17,710
所以让我们来看看1
一个已经预先制定

530
00:22:17,710 --> 00:22:21,810
像这样与不点，点，
点，但只是略阵列。

531
00:22:21,810 --> 00:22:23,950
但每个节点
在这棵树在这里

532
00:22:23,950 --> 00:22:26,700
表示同一件事 - 
数组的大小26雷。

533
00:22:26,700 --> 00:22:28,860
>> 或者，如果我们想成为
现在真的很合适，有什么

534
00:22:28,860 --> 00:22:30,790
如果某人的名字
一个撇号，让我们

535
00:22:30,790 --> 00:22:35,560
假设每个节点实际上具有
像27指数在里面，不只是26。

536
00:22:35,560 --> 00:22:42,020
所以这个现在将是一个数据
结构称为trie-- T-R-I-E。

537
00:22:42,020 --> 00:22:46,120
一个线索，这是假想
历史上的一棵树一个聪明的名字

538
00:22:46,120 --> 00:22:49,040
这对优化
当然，检索，其中，

539
00:22:49,040 --> 00:22:50,870
拼写与I-E所以它的线索。

540
00:22:50,870 --> 00:22:52,710
但是，这是对线索的历史。

541
00:22:52,710 --> 00:22:55,860
>> 因此，一个线索是这样的树状数据
就像一个家庭树结构

542
00:22:55,860 --> 00:22:57,510
最终表现那样。

543
00:22:57,510 --> 00:23:00,890
这里是一个又一个的例子
一大堆别人的名字。

544
00:23:00,890 --> 00:23:03,540
但现在的问题
手头有什么

545
00:23:03,540 --> 00:23:08,070
我们获得了通过引入可以说是一个更
复杂的数据结构，和一，

546
00:23:08,070 --> 00:23:09,870
坦率地说，使用了大量的内存。

547
00:23:09,870 --> 00:23:11,703
>> 因为即使，
此刻，我只

548
00:23:11,703 --> 00:23:15,050
使用D的指针和
A和V和ES和NS，

549
00:23:15,050 --> 00:23:16,700
我在浪费大量的内存赫克。

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
但是，在这里我度过一个资源，
我倾向于不争回另一个。

552
00:23:22,660 --> 00:23:26,020
所以，如果我花了更多的空间，
什么是可能的希望吗？

553
00:23:26,020 --> 00:23:27,407
那我花少了什么？

554
00:23:27,407 --> 00:23:28,240
听众：更少的时间。

555
00:23:28,240 --> 00:23:28,990
DAVID马兰：时间。

556
00:23:28,990 --> 00:23:30,320
现在为什么会这样呢？

557
00:23:30,320 --> 00:23:33,880
那么，什么是插
时间，在目前大O方面，

558
00:23:33,880 --> 00:23:37,660
像Daven一个名字
或者达文波特还是大卫？

559
00:23:37,660 --> 00:23:39,340
好吧，Daven是五个步骤。

560
00:23:39,340 --> 00:23:42,350
达文波特将九个步骤，
所以这将是一个几个步骤。

561
00:23:42,350 --> 00:23:44,250
大卫将五个步骤为好。

562
00:23:44,250 --> 00:23:47,230
因此，这些都是具体的
数字，但肯定有

563
00:23:47,230 --> 00:23:49,550
的上限的
长别人的名字。

564
00:23:49,550 --> 00:23:52,240
而事实上，在该问题
台五规范，

565
00:23:52,240 --> 00:23:54,050
我们要提出
它的东西

566
00:23:54,050 --> 00:23:55,470
这是40-一些多字符。

567
00:23:55,470 --> 00:23:58,180
>> 实际上，没有人有
一个无限长的名字，

568
00:23:58,180 --> 00:24:01,542
这就是说，一个长度
名称或字符串的长度，我们可能

569
00:24:01,542 --> 00:24:03,750
有一定的状态
结构可以说是什么？

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
这是不变的。

572
00:24:06,250 --> 00:24:06,430
对不对？

573
00:24:06,430 --> 00:24:09,310
这可能是一个很大的不变样
40多岁的，但它是恒定的。

574
00:24:09,310 --> 00:24:13,752
它有多少不依赖
其它名称是在该数据结构中。

575
00:24:13,752 --> 00:24:15,460
换句话说，如果我
想现在插入

576
00:24:15,460 --> 00:24:20,540
科尔顿或加布里埃尔或抢或Zamyla或
艾莉森或贝琳达或任何其他名称

577
00:24:20,540 --> 00:24:23,940
从工作人员到该数据
结构，是在运行时间

578
00:24:23,940 --> 00:24:26,750
中插入其他名称
将要在所有受影响的

579
00:24:26,750 --> 00:24:30,220
被多少其他元素
在已经将数据结构？

580
00:24:30,220 --> 00:24:31,040
它不是。

581
00:24:31,040 --> 00:24:31,540
对不对？

582
00:24:31,540 --> 00:24:36,150
由于我们有效地利用
这个多层哈希表。

583
00:24:36,150 --> 00:24:38,280
和运行时间
这些操作

584
00:24:38,280 --> 00:24:41,510
取决于不上的数
这是在数据结构中的元素

585
00:24:41,510 --> 00:24:43,090
或者被最终将
是在数据结构中，

586
00:24:43,090 --> 00:24:44,714
但在什么具体的长度是多少？

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> 该字符串是
插入，这确实让

589
00:24:49,200 --> 00:24:52,580
这种渐进恒
一时间 - 大O。

590
00:24:52,580 --> 00:24:54,720
坦率地说，就在
现实世界中，这

591
00:24:54,720 --> 00:24:58,380
指插入Daven的名字取
像五个步骤，或者达文波特9

592
00:24:58,380 --> 00:25:00,100
步骤或大卫五个步骤。

593
00:25:00,100 --> 00:25:03,071
这是相当不错的小的运行时间。

594
00:25:03,071 --> 00:25:05,320
而且，事实上，这是一个非常
好东西，尤其是当

595
00:25:05,320 --> 00:25:08,126
它不依赖于总量
在那里的元素个数。

596
00:25:08,126 --> 00:25:10,500
那么如何才能实现我们这个
这种结构的代码？

597
00:25:10,500 --> 00:25:12,900
这是一个多一点
复杂，但它仍然是

598
00:25:12,900 --> 00:25:15,050
只是一个应用
基本构建块。

599
00:25:15,050 --> 00:25:17,830
我要重新定义
我们节点如下：

600
00:25:17,830 --> 00:25:21,100
布尔称为word--这
可以被称为什么。

601
00:25:21,100 --> 00:25:23,970
但布尔代表
我画了一个对号。

602
00:25:23,970 --> 00:25:24,490
是的。

603
00:25:24,490 --> 00:25:26,720
这是一个字符串的末尾
在此数据结构中。

604
00:25:26,720 --> 00:25:30,702
>> 并且，当然，节点星
有指儿童。

605
00:25:30,702 --> 00:25:32,410
而且，事实上，就像
一个家谱，你

606
00:25:32,410 --> 00:25:34,370
会考虑节点
被挂

607
00:25:34,370 --> 00:25:36,920
一些家长的底部
元素是儿童。

608
00:25:36,920 --> 00:25:40,510
这样一来，孩子们将要
是27的数组，第27届1

609
00:25:40,510 --> 00:25:41,680
摆明了撇号。

610
00:25:41,680 --> 00:25:43,390
我们要进行排序
的特殊情况。

611
00:25:43,390 --> 00:25:45,400
所以，你可以有一定
名称以撇号。

612
00:25:45,400 --> 00:25:47,399
甚至连字符应
去那里，但你

613
00:25:47,399 --> 00:25:50,330
见P组5，我们只关心
有关信件和单引号。

614
00:25:50,330 --> 00:25:52,990
>> 然后你怎么代表
数据结构本身？

615
00:25:52,990 --> 00:25:56,454
你怎么代表根
这个线索的，可以这么说？

616
00:25:56,454 --> 00:25:59,620
嗯，就像一个链表，你
需要一个指针的第一个元素。

617
00:25:59,620 --> 00:26:04,270
有线索，你只需要1
指向此线索的根。

618
00:26:04,270 --> 00:26:07,290
从那里，你可以散列
你的路陷的越来越深

619
00:26:07,290 --> 00:26:10,460
以在结构中每一个其他节点。

620
00:26:10,460 --> 00:26:13,440
因此，简单地用这个就可以
我们代表的结构。

621
00:26:13,440 --> 00:26:15,877
>> 现在Meanwhile--呵呵，问题。

622
00:26:15,877 --> 00:26:17,220
>> 听众：什么是布尔字？

623
00:26:17,220 --> 00:26:20,490
>> DAVID马兰：BOOL字
只是这款C化身

624
00:26:20,490 --> 00:26:22,920
什么，我描述
在这里，在这个盒子

625
00:26:22,920 --> 00:26:26,000
我开始分裂各
数组的元素分为两部分。

626
00:26:26,000 --> 00:26:27,600
之一是一个指向下一个节点。

627
00:26:27,600 --> 00:26:30,280
其它必须是
类似的复选框

628
00:26:30,280 --> 00:26:33,770
要说的是，有一个
字Daven说到此为止，

629
00:26:33,770 --> 00:26:35,610
因为我们不想要的，
此刻，戴夫。

630
00:26:35,610 --> 00:26:39,320
>> 即使戴夫将是一个
合法的一句话，他不是在特里

631
00:26:39,320 --> 00:26:39,830
还没有。

632
00:26:39,830 --> 00:26:40,950
和D是不发一言。

633
00:26:40,950 --> 00:26:42,770
和D-A是不是一个单词或一个名称。

634
00:26:42,770 --> 00:26:45,020
因此，复选标记
表示只有当你

635
00:26:45,020 --> 00:26:48,190
打这个节点是
字符前面的路

636
00:26:48,190 --> 00:26:50,700
实际上，你已经插入一个字符串。

637
00:26:50,700 --> 00:26:53,660
这就是所有的布尔
那里是做给我们。

638
00:26:53,660 --> 00:26:55,500
>> 在尝试任何其他问题？

639
00:26:55,500 --> 00:26:56,215
是啊。

640
00:26:56,215 --> 00:26:58,035
>> 听众：什么是重叠？

641
00:26:58,035 --> 00:26:59,945
如果你有一个戴夫和Daven？

642
00:26:59,945 --> 00:27:00,820
DAVID马兰：完美。

643
00:27:00,820 --> 00:27:02,580
如果你有一个戴夫和Daven？

644
00:27:02,580 --> 00:27:06,240
所以，如果我们插入，说一个绰号，
对于David-- Dave-- D-A-V-E？

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
其实，这是超级简单。

647
00:27:08,700 --> 00:27:10,325
因此，我们只是要带四个步骤。

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E。和我有什么要
做一次，我打了四节点？

650
00:27:15,847 --> 00:27:16,680
只是去检查。

651
00:27:16,680 --> 00:27:18,000
我们已经好到哪里去。

652
00:27:18,000 --> 00:27:18,840
完成的。

653
00:27:18,840 --> 00:27:19,750
四个步骤。

654
00:27:19,750 --> 00:27:21,590
固定时间渐近。

655
00:27:21,590 --> 00:27:26,300
现在我们已经表明，无论戴夫
和Daven是在结构中的字符串。

656
00:27:26,300 --> 00:27:27,710
所以不存在问题。

657
00:27:27,710 --> 00:27:30,200
并注意存在
Daven的没能

658
00:27:30,200 --> 00:27:34,750
需要更多的时间或更少
时间戴夫，反之亦然。

659
00:27:34,750 --> 00:27:36,000
>> 那么还有什么可以，现在我们怎么办？

660
00:27:36,000 --> 00:27:40,680
我们以前使用过这个隐喻
托盘代表什么。

661
00:27:40,680 --> 00:27:43,380
但事实证明，一个
托盘堆实际上是

662
00:27:43,380 --> 00:27:47,187
示范的另一个抽象数据
类型 - 一个更高层次的数据结构

663
00:27:47,187 --> 00:27:49,770
这在最后的日子就是
像阵列或链接的列表

664
00:27:49,770 --> 00:27:50,970
什么更现实。

665
00:27:50,970 --> 00:27:53,270
但它是一个更有趣
概念的概念。

666
00:27:53,270 --> 00:27:56,440
堆栈，这样的
托盘在这里马瑟

667
00:27:56,440 --> 00:27:58,750
通常被称为
只是that--堆栈。

668
00:27:58,750 --> 00:28:02,540
>> 并且在这种类型的数据结构
你有两个operations--

669
00:28:02,540 --> 00:28:05,880
你有一个叫推
添加的东西到堆栈，

670
00:28:05,880 --> 00:28:08,320
就像把另一盘
备份在堆栈的顶部。

671
00:28:08,320 --> 00:28:11,350
然后弹出，这意味着你
把最上面的托盘掉。

672
00:28:11,350 --> 00:28:16,210
但是，什么是关键关于堆栈是
它有这种奇怪的特点。

673
00:28:16,210 --> 00:28:19,560
由于食堂工作人员
重新排列的托盘为下一顿饭，

674
00:28:19,560 --> 00:28:21,380
这是怎么回事是
真正了解学生如何

675
00:28:21,380 --> 00:28:22,856
这种数据结构进行交互？

676
00:28:22,856 --> 00:28:24,480
听众：他们将弹出一关。

677
00:28:24,480 --> 00:28:26,550
DAVID马兰：他们要去
弹出一关，希望上面。

678
00:28:26,550 --> 00:28:28,910
否则，它只是一种愚蠢
一路走到底。

679
00:28:28,910 --> 00:28:29,070
对不对？

680
00:28:29,070 --> 00:28:31,620
该数据结构并没有真正允许
你至少要抢底盘

681
00:28:31,620 --> 00:28:32,520
很容易。

682
00:28:32,520 --> 00:28:35,040
因此，有这种奇怪的
属性堆栈

683
00:28:35,040 --> 00:28:39,730
在最后一个项目是
将成为第1列。

684
00:28:39,730 --> 00:28:43,400
和计算机科学家称之为
这LIFO--后进先出。

685
00:28:43,400 --> 00:28:45,540
它实际上确实有
有趣的应用程序。

686
00:28:45,540 --> 00:28:50,090
它并不一定那么明显一些
其他人，但它确实能是有用的，

687
00:28:50,090 --> 00:28:54,040
它确实能实现
在几个不同的方式。

688
00:28:54,040 --> 00:28:58,550
>> 所以一个，实际上，让
我不要潜入了。

689
00:28:58,550 --> 00:28:59,860
让我们这样做吧。

690
00:28:59,860 --> 00:29:03,700
让我们来看看一个几乎在
同样的想法，但它是一个更公平一点。

691
00:29:03,700 --> 00:29:04,200
对不对？

692
00:29:04,200 --> 00:29:07,560
如果你是这些球迷的一个男孩或
女生真的喜欢苹果产品

693
00:29:07,560 --> 00:29:10,130
而你在上午03点00分就醒了
排队在一些商店

694
00:29:10,130 --> 00:29:14,150
获得最新的iPhone，你
可能排队这样的。

695
00:29:14,150 --> 00:29:15,800
>> 现在队列很刻意的名字命名。

696
00:29:15,800 --> 00:29:18,190
这是一条线，因为有
一些公平吧。

697
00:29:18,190 --> 00:29:18,690
对不对？

698
00:29:18,690 --> 00:29:21,690
种它将如果你吸
到了那里在Apple Store第一

699
00:29:21,690 --> 00:29:25,700
但你有效的最底部
托盘是因为苹果公司的员工，然后

700
00:29:25,700 --> 00:29:28,189
流行的最后一个人谁
实际上得到的线。

701
00:29:28,189 --> 00:29:31,230
因此，栈和队列，即使
在功能上，他们是那种same--的

702
00:29:31,230 --> 00:29:33,105
它只是这个集合
资源，这是

703
00:29:33,105 --> 00:29:36,210
要发展和shrink--还有的
这种公平性方面吧，

704
00:29:36,210 --> 00:29:39,634
至少在现实世界中，
其中，操作你锻炼

705
00:29:39,634 --> 00:29:40,800
是根本不同的。

706
00:29:40,800 --> 00:29:43,360
一个stack--队列
rather--据说有

707
00:29:43,360 --> 00:29:45,320
两个操作：N队列和D队列。

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
或者你可以给他们打电话
任何数目的东西。

710
00:29:48,090 --> 00:29:50,770
但是，你只是想捕捉
一个是增加的概念

711
00:29:50,770 --> 00:29:53,230
和一个最终被减去。

712
00:29:53,230 --> 00:29:58,840
>> 现在的发动机罩的下面，两者的堆栈
和队列可以实现怎么样？

713
00:29:58,840 --> 00:30:01,390
我们不会进入代码
这是因为在较高的水平

714
00:30:01,390 --> 00:30:03,387
思想是那种比较明显。

715
00:30:03,387 --> 00:30:04,470
我的意思是，人类该怎么办？

716
00:30:04,470 --> 00:30:07,030
如果我是第一人，在苹果
存储，这是前门，

717
00:30:07,030 --> 00:30:08,130
你知道，我要站在这里。

718
00:30:08,130 --> 00:30:09,750
和旁边的人的
站在这里。

719
00:30:09,750 --> 00:30:11,500
和旁边的人的
站在这里。

720
00:30:11,500 --> 00:30:13,792
那么，什么数据结构
适合于一个队列？

721
00:30:13,792 --> 00:30:14,542
>> 听众：队列。

722
00:30:14,542 --> 00:30:15,667
DAVID马兰：嗯，一个队列。

723
00:30:15,667 --> 00:30:16,390
当然可以。

724
00:30:16,390 --> 00:30:16,920
还有什么？

725
00:30:16,920 --> 00:30:17,600
>> 听众：链表。

726
00:30:17,600 --> 00:30:18,990
>> DAVID马兰：一个链接
列出你可以实现。

727
00:30:18,990 --> 00:30:22,500
和链表是好的，因为这样
而不是可任意长长

728
00:30:22,500 --> 00:30:24,880
具有一些固定的数
人在店里。

729
00:30:24,880 --> 00:30:27,030
但也许一个固定的数
地方是合法的。

730
00:30:27,030 --> 00:30:30,350
因为如果他们只有像20
iPhone手机的第一天，也许

731
00:30:30,350 --> 00:30:33,930
它们只需要尺寸的阵列
20代表该队列，这

732
00:30:33,930 --> 00:30:37,070
只是现在说一旦我们开始讨论
关于这些较高级别的问题，

733
00:30:37,070 --> 00:30:38,890
你可以实现它
在任何数量的方式。

734
00:30:38,890 --> 00:30:42,030
还有的可能只是要
是一个折衷在空间和时间

735
00:30:42,030 --> 00:30:43,950
或只是在自己的代码的复杂性。

736
00:30:43,950 --> 00:30:45,380
>> 那么堆栈？

737
00:30:45,380 --> 00:30:48,190
好了，一个栈，我们已经看到太多
可能仅仅是这些托盘。

738
00:30:48,190 --> 00:30:50,007
而且你可以实现这个数组。

739
00:30:50,007 --> 00:30:53,090
但在某些时候，如果你使用一个数组，
什么事情要发生在托盘

740
00:30:53,090 --> 00:30:54,173
你想放下？

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
行。

743
00:30:55,670 --> 00:30:57,490
你只打算
能走这么高。

744
00:30:57,490 --> 00:31:00,156
我认为，在马瑟他们
实际上凹进的开放。

745
00:31:00,156 --> 00:31:01,950
所以，事实上，它几乎
像奥美使用

746
00:31:01,950 --> 00:31:03,783
固定大小的阵列，
因为你只能

747
00:31:03,783 --> 00:31:08,302
在开放符合这么多托盘
墙壁向下跌破人们的膝盖。

748
00:31:08,302 --> 00:31:10,010
因此，可能是
说是一个数组，

749
00:31:10,010 --> 00:31:14,300
但我们可以肯定的实施
更一般地用一个链表。

750
00:31:14,300 --> 00:31:16,390
>> 那么，关于另一个数据结构？

751
00:31:16,390 --> 00:31:18,760
我拉起另一个视觉这里。

752
00:31:18,760 --> 00:31:24,710
像这个怎么在这里？

753
00:31:24,710 --> 00:31:28,920
为什么会到没有它是有用的
一些花哨的线索，这

754
00:31:28,920 --> 00:31:32,370
我们看到了这些非常宽的节点，
其中每一个是在一个数组中？

755
00:31:32,370 --> 00:31:35,740
但是，如果我们做更多的事情
简单地说，就像一个老同学的家谱，

756
00:31:35,740 --> 00:31:38,110
每一个在这里的节点
只是存储号码。

757
00:31:38,110 --> 00:31:42,180
而不是一个名称或后裔
只是存储了一些类似这样的。

758
00:31:42,180 --> 00:31:45,250
>> 好了，我们行话使用
数据结构是既尝试

759
00:31:45,250 --> 00:31:49,510
和树木，其中一个线索，再次，是
只有一个的节点阵列，

760
00:31:49,510 --> 00:31:51,680
依然是你可能会
从小学使用

761
00:31:51,680 --> 00:31:53,860
当你犯了一个家庭
tree--叶和根

762
00:31:53,860 --> 00:31:57,250
树和儿童
父母和兄弟姐妹物。

763
00:31:57,250 --> 00:32:03,670
我们可以实现一个树，
例如，作为简单的了。

764
00:32:03,670 --> 00:32:07,420
树，如果它作为一个节点，一个
这些圆，其具有数，

765
00:32:07,420 --> 00:32:09,947
它不会有
1指针，而是两个。

766
00:32:09,947 --> 00:32:11,780
而且只要你加入
第二个指针，

767
00:32:11,780 --> 00:32:13,905
实际上现在做排序
的二维数据

768
00:32:13,905 --> 00:32:14,780
结构在存储器中。

769
00:32:14,780 --> 00:32:16,660
很像一个二维
数组，你可以

770
00:32:16,660 --> 00:32:18,904
有种类的二维
链表但那些

771
00:32:18,904 --> 00:32:20,820
下面的模式
那里没有周期。

772
00:32:20,820 --> 00:32:24,487
这是一个真正的有一棵树
了祖父母的方式在这里再

773
00:32:24,487 --> 00:32:27,320
一些家长和孩子
孙子和曾孙。

774
00:32:27,320 --> 00:32:28,370
等等。

775
00:32:28,370 --> 00:32:32,390
>> 但是，什么是真正的整洁对此也
只是逗你一些代码，

776
00:32:32,390 --> 00:32:35,370
从调用递归
一段时间回来，因此

777
00:32:35,370 --> 00:32:38,220
你写一个函数，该函数调用自身。

778
00:32:38,220 --> 00:32:41,140
这是一个美丽的机会
实施东西

779
00:32:41,140 --> 00:32:42,920
像递归，因为考虑这一点。

780
00:32:42,920 --> 00:32:43,860
>> 这是一个树。

781
00:32:43,860 --> 00:32:48,040
我已经有点肛门如何
我把整数到街上。

782
00:32:48,040 --> 00:32:51,020
正因如此，它有一个特殊的
名称 - 二叉查找树。

783
00:32:51,020 --> 00:32:53,460
现在，我们已经听说二进制
搜索，但你能

784
00:32:53,460 --> 00:32:55,180
从这个东西的名字倒着工作？

785
00:32:55,180 --> 00:32:59,280
什么是我如何的格局
插入整数到这棵树？

786
00:32:59,280 --> 00:33:00,696
它不是随意的。

787
00:33:00,696 --> 00:33:01,570
这里也有一些图案。

788
00:33:01,570 --> 00:33:02,090
是啊。

789
00:33:02,090 --> 00:33:03,370
>> 听众：在左边较小的。

790
00:33:03,370 --> 00:33:03,690
>> DAVID马兰：是啊。

791
00:33:03,690 --> 00:33:05,062
较小的是在左侧。

792
00:33:05,062 --> 00:33:06,270
更大的是在右侧。

793
00:33:06,270 --> 00:33:12,940
这样，真正的语句是
家长大于它的左孩子，

794
00:33:12,940 --> 00:33:14,850
但比其右孩子少。

795
00:33:14,850 --> 00:33:17,750
而这仅仅是一个连
递归定义语言

796
00:33:17,750 --> 00:33:20,500
因为你可以应用
相同的逻辑的每一个节点

797
00:33:20,500 --> 00:33:23,080
而且它仅塔底
如果你出去，基本情况

798
00:33:23,080 --> 00:33:25,740
会的，当你打一个
叶子，可以这么说，

799
00:33:25,740 --> 00:33:28,580
凡请假没有孩子更进一步。

800
00:33:28,580 --> 00:33:30,614
>> 现在，你怎么可能找到44号？

801
00:33:30,614 --> 00:33:32,280
你会从根开始，说，嗯。

802
00:33:32,280 --> 00:33:35,690
55不是44，我想去
正确的还是我想往左走？

803
00:33:35,690 --> 00:33:37,190
显然，你想要去左边。

804
00:33:37,190 --> 00:33:40,060
所以它就像手机
在二进制搜索本书实例

805
00:33:40,060 --> 00:33:41,099
更普遍。

806
00:33:41,099 --> 00:33:43,390
但我们实现它
现在多了几分动态

807
00:33:43,390 --> 00:33:45,339
不是一个数组可以允许。

808
00:33:45,339 --> 00:33:48,130
而事实上，如果你想看看
在代码中，第​​一眼肯定。

809
00:33:48,130 --> 00:33:49,671
它看起来像一大堆线。

810
00:33:49,671 --> 00:33:51,220
但它的美丽很简单。

811
00:33:51,220 --> 00:33:54,490
如果你想实现一个功能
所谓的搜索，其目的在生活中

812
00:33:54,490 --> 00:33:57,290
是要搜索的一个值
像N，整数，

813
00:33:57,290 --> 00:34:01,756
和你在一pointer--正在通过
一个指向根的节点，

814
00:34:01,756 --> 00:34:04,380
那棵树的相当，从
您可以访问其他的一切，

815
00:34:04,380 --> 00:34:08,850
注意如何直截了当地
你可以实现的逻辑。

816
00:34:08,850 --> 00:34:10,880
如果树是空，
显然它不存在。

817
00:34:10,880 --> 00:34:11,880
让我们只返回false。

818
00:34:11,880 --> 00:34:12,000
对不对？

819
00:34:12,000 --> 00:34:14,040
如果你把它什么都没有，
有什么也没有。

820
00:34:14,040 --> 00:34:17,900
>> 否则，如果n小于
树箭头N--现在箭头N，

821
00:34:17,900 --> 00:34:20,670
记得我们推出超
短暂的一天，

822
00:34:20,670 --> 00:34:25,100
那只是意味着去参考
指针看看所谓的n个场。

823
00:34:25,100 --> 00:34:27,690
因此，这意味着去那里
看看所谓的n个场。

824
00:34:27,690 --> 00:34:33,810
所以，如果N，你给出的值，小于
比在树木整数的值，

825
00:34:33,810 --> 00:34:35,449
你想去哪儿去了？

826
00:34:35,449 --> 00:34:36,389
向左转。

827
00:34:36,389 --> 00:34:37,780
>> 所以，注意递归。

828
00:34:37,780 --> 00:34:39,860
我returning--不正确的。

829
00:34:39,860 --> 00:34:40,989
不假。

830
00:34:40,989 --> 00:34:45,670
我回来什么的答案
是通过调用自己，路过

831
00:34:45,670 --> 00:34:50,100
的n再次，这是多余的，
但什么是略有不同呢？

832
00:34:50,100 --> 00:34:51,989
我怎么做的问题更小？

833
00:34:51,989 --> 00:34:54,920
我传递的第二个
参数，该树的不根，

834
00:34:54,920 --> 00:34:59,616
但左子在这种情况下。

835
00:34:59,616 --> 00:35:00,990
所以我通过左边的孩子。

836
00:35:00,990 --> 00:35:04,720
>> 同时，如果n是大于
该节点目前，我正在看，

837
00:35:04,720 --> 00:35:06,690
我搜索的右侧。

838
00:35:06,690 --> 00:35:10,880
否则，如果树不为空，而
如果元素不是向左

839
00:35:10,880 --> 00:35:13,240
它并不是正确的，
什么是奇妙的情况？

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
实际上我们发现，节点
的问题，所以我们返回true。

842
00:35:18,440 --> 00:35:21,490
>> 所以我们刚刚触及表面
现在一些数据结构。

843
00:35:21,490 --> 00:35:24,370
在问题设置5，你会
再进一步探讨这些，

844
00:35:24,370 --> 00:35:27,250
你会得到你的设计
选择如何去了解这一点。

845
00:35:27,250 --> 00:35:30,250
我想缔结
仅仅30秒的预告片

846
00:35:30,250 --> 00:35:32,080
下周及以后有什么在等待着。

847
00:35:32,080 --> 00:35:35,390
>> 正如我们begin--谢天谢地你可能
慢慢think--我们的转型

848
00:35:35,390 --> 00:35:38,680
从C和下部的世界
层次的实现细节，

849
00:35:38,680 --> 00:35:42,090
一个世界里，我们可以采取的
理所当然地认为别人终于

850
00:35:42,090 --> 00:35:44,010
实现了这些数据
结构对于我们来说，

851
00:35:44,010 --> 00:35:47,570
我们将开始了解
现实世界是指实施

852
00:35:47,570 --> 00:35:50,560
基于网络的程序和
网站更普遍

853
00:35:50,560 --> 00:35:52,910
并且也很安全
我们只已经影响

854
00:35:52,910 --> 00:35:54,850
开始划伤的表面上。

855
00:35:54,850 --> 00:35:57,320
这是什么等待着我们
在未来的日子里。

856
00:35:57,320 --> 00:36:00,480
>> [视频回放]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>>  - 他想出了一个消息，
有协议的所有他自己的。

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
他来到了残酷的世界
防火墙，路由器漠不关心，

861
00:36:30,894 --> 00:36:33,368
和危险远远比死还要痛苦。

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
他的速度快。

864
00:36:36,236 --> 00:36:37,980
他是强大的。

865
00:36:37,980 --> 00:36:42,830
他是TCP / IP，和他有你的地址。

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
“勇士的网。”

868
00:36:48,074 --> 00:36:49,660
[完视频回放]

869
00:36:49,660 --> 00:36:50,910
DAVID马兰：下周即将。

870
00:36:50,910 --> 00:36:51,880
我们会看到你呢。

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[视频回放]

873
00:36:56,060 --> 00:36:59,240
 - 和现在，“深度思考”
通过Daven法纳姆。

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David总是开始
与讲座，“好吧。”

876
00:37:05,820 --> 00:37:08,750
心动不如行动，“这里的解决方案
本周的问题集“

877
00:37:08,750 --> 00:37:12,180
或者“我们给大家一个A？”

878
00:37:12,180 --> 00:37:13,380
[笑气]

879
00:37:13,380 --> 00:37:15,530
[完视频回放]