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

2
00:00:00,500 --> 00:00:05,120
[音乐播放]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
扬声器1：好吧。

5
00:00:12,900 --> 00:00:14,600
每个人都欢迎回款。

6
00:00:14,600 --> 00:00:18,660
我希望大家都成功
从你的测验回收

7
00:00:18,660 --> 00:00:19,510
从上周。

8
00:00:19,510 --> 00:00:22,564
我知道这是一个有点疯狂的时候。

9
00:00:22,564 --> 00:00:25,230
正如我之前说，如果你是
的标准偏差之内，

10
00:00:25,230 --> 00:00:28,188
真的不担心，尤其是
一个不太舒适的部分。

11
00:00:28,188 --> 00:00:30,230
这是什么地方，你应该的。

12
00:00:30,230 --> 00:00:32,850
>> 如果你做得很好，那么真棒。

13
00:00:32,850 --> 00:00:33,650
荣誉给你。

14
00:00:33,650 --> 00:00:36,149
如果你觉得你需要
多一点点的帮助，请

15
00:00:36,149 --> 00:00:38,140
随时到达
出任何的转录因子。

16
00:00:38,140 --> 00:00:40,030
我们都在这里帮忙。

17
00:00:40,030 --> 00:00:40,960
>> 这就是为什么我们教。

18
00:00:40,960 --> 00:00:44,550
这就是为什么我在这里每周一为你
球员和在办公时间星期四休息。

19
00:00:44,550 --> 00:00:48,130
因此，请随时让我知道
如果你担心什么

20
00:00:48,130 --> 00:00:52,450
或者，如果有对任何竞猜
你真的想解决的问题。

21
00:00:52,450 --> 00:00:56,940
>> 因此，对于今天的议程
所有关于数据结构。

22
00:00:56,940 --> 00:01:01,520
其中一些只是要公正
为了让你熟悉这些。

23
00:01:01,520 --> 00:01:04,870
你可能永远不会实现
他们在这个类中。

24
00:01:04,870 --> 00:01:08,690
有些人你会的，
像你的拼写PSET。

25
00:01:08,690 --> 00:01:11,380
>> 你有你的选择
哈希表和尝试的。

26
00:01:11,380 --> 00:01:13,680
所以我们一定会去在那些。

27
00:01:13,680 --> 00:01:18,690
这将是肯定更有种
高电平部分的今天，虽然

28
00:01:18,690 --> 00:01:22,630
因为有很多人，如果
我们进入的实施细则

29
00:01:22,630 --> 00:01:26,490
所有这些，我们不会
甚至可以通过链接列表

30
00:01:26,490 --> 00:01:28,520
也许哈希表的一点点。

31
00:01:28,520 --> 00:01:31,200
>> 所以多多包涵。

32
00:01:31,200 --> 00:01:33,530
我们不打算做
尽可能多的编码这个时候。

33
00:01:33,530 --> 00:01:36,870
如果您有任何关于它的问题
或者你想看到它实现的

34
00:01:36,870 --> 00:01:39,260
还是自己试试看，
我绝对推荐

35
00:01:39,260 --> 00:01:44,250
要study.cs50.net，这
具有所有的这些例子。

36
00:01:44,250 --> 00:01:46,400
这将有我的学习认证
用音符，我们

37
00:01:46,400 --> 00:01:50,860
倾向于使用以及一些编程
练习，特别是对事

38
00:01:50,860 --> 00:01:55,250
如链表和二进制
树木堆栈和线索。

39
00:01:55,250 --> 00:01:59,590
这么少的较高水平，这
也许是很好的你们。

40
00:01:59,590 --> 00:02:01,320
>> 所以这样，我们就开始吧。

41
00:02:01,320 --> 00:02:03,060
而且，yes--测验。

42
00:02:03,060 --> 00:02:06,550
我想绝大多数人谁是
我的部分有你的测验，

43
00:02:06,550 --> 00:02:12,060
但任何人进来，或某种原因，你
不这样做，他们就在这里，在前面。

44
00:02:12,060 --> 00:02:12,740
>> 所以链表。

45
00:02:12,740 --> 00:02:15,650
我知道这种云
您的测验前备份。

46
00:02:15,650 --> 00:02:17,940
这是一周前
我们了解了这一点。

47
00:02:17,940 --> 00:02:21,040
但是，在这种情况下，我们只
走多一点点深入。

48
00:02:21,040 --> 00:02:25,900
>> 那么，为什么我们会选择一个
链表一个数组？

49
00:02:25,900 --> 00:02:27,130
有什么区别呢？

50
00:02:27,130 --> 00:02:27,630
是吗？

51
00:02:27,630 --> 00:02:30,464
>> 听众：您还可以扩大一个链接
列出与数组的固定大小。

52
00:02:30,464 --> 00:02:31,171
扬声器1：没错。

53
00:02:31,171 --> 00:02:33,970
数组有固定的大小，而一
链表具有可变的大小。

54
00:02:33,970 --> 00:02:36,970
因此，如果我们不知道如何
我们多么希望存储，

55
00:02:36,970 --> 00:02:39,880
链表给我们带来了很大的
办法做到这一点，因为我们可以只

56
00:02:39,880 --> 00:02:43,730
添加另一个节点上，并添加上
另一个节点，并添加另一个节点上。

57
00:02:43,730 --> 00:02:45,750
但可能是一个权衡？

58
00:02:45,750 --> 00:02:49,521
有谁还记得权衡
数组和链表之间？

59
00:02:49,521 --> 00:02:50,020
Mmhmm​​？

60
00:02:50,020 --> 00:02:51,460
>> 听众：你必须
经过一路

61
00:02:51,460 --> 00:02:53,738
通过该链接的表
发现列表中的一个元素。

62
00:02:53,738 --> 00:02:55,570
在一个阵列，可以
只要找到一个元素。

63
00:02:55,570 --> 00:02:56,278
>> 扬声器1：没错。

64
00:02:56,278 --> 00:02:57,120
因此，与arrays--

65
00:02:57,120 --> 00:02:58,500
>> 听众：[听不清]。

66
00:02:58,500 --> 00:03:01,090
>> 扬声器1：数组，我们有
什么叫做随机访问。

67
00:03:01,090 --> 00:03:04,820
也就是说，如果我们要的是
有史以来第五点名单

68
00:03:04,820 --> 00:03:07,230
或第五点是我们
数组，我们只要抓住它。

69
00:03:07,230 --> 00:03:10,440
如果它是一个链表，我们有
遍历，对不对？

70
00:03:10,440 --> 00:03:14,020
所以，在访问一个元素
一个阵列是恒定时间，

71
00:03:14,020 --> 00:03:19,530
而用一个链表的那样
最有可能是线性的时间，因为也许

72
00:03:19,530 --> 00:03:21,370
我们的元件是一路在末端。

73
00:03:21,370 --> 00:03:23,446
我们有过的一切进行搜索。

74
00:03:23,446 --> 00:03:25,320
因此，所有这些数据
我们要去结构

75
00:03:25,320 --> 00:03:29,330
要在花多一点的时间，
哪些长处和底片。

76
00:03:29,330 --> 00:03:31,480
什么时候我们可能要
使用一个比其他？

77
00:03:31,480 --> 00:03:34,970
这就是种的
更大的东西拿走。

78
00:03:34,970 --> 00:03:40,140
>> 因此，我们必须在这里
定义一个节点。

79
00:03:40,140 --> 00:03:43,040
这就像在一个元素
我们的链表，对不对？

80
00:03:43,040 --> 00:03:46,180
所以，我们都很熟悉
我们的typedef结构，

81
00:03:46,180 --> 00:03:47,980
我们走过去，在回顾过去的时候。

82
00:03:47,980 --> 00:03:53,180
它基本上只是创造
我们可以使用另一种数据类型。

83
00:03:53,180 --> 00:03:57,930
>> 在这种情况下，它的一些节点
这将在一定整数。

84
00:03:57,930 --> 00:04:00,210
然后什么是第二部分在这里？

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
任何人吗？

87
00:04:05,677 --> 00:04:06,680
>> 听众：[听不清]。

88
00:04:06,680 --> 00:04:07,020
>> 扬声器1：是啊。

89
00:04:07,020 --> 00:04:08,400
这是一个指向下一个节点。

90
00:04:08,400 --> 00:04:12,610
因此，这实际上应该是在这里。

91
00:04:12,610 --> 00:04:18,790
这类型的指针
节点到下一件事情。

92
00:04:18,790 --> 00:04:22,410
而这正是他们
包括我们的节点。

93
00:04:22,410 --> 00:04:24,060
凉爽。

94
00:04:24,060 --> 00:04:29,390
>> 好吧，所以用搜索，因为我们
只是说前手，如果你

95
00:04:29,390 --> 00:04:31,840
要通过搜索，
你必须真正迭代

96
00:04:31,840 --> 00:04:33,660
通过您的链接列表。

97
00:04:33,660 --> 00:04:38,530
因此，如果我们要寻找的数量
9，我们将开始在我们的头上

98
00:04:38,530 --> 00:04:41,520
并指向我们开始
我们的链表，对不对？

99
00:04:41,520 --> 00:04:44,600
我们说好，这是否
节点包含数字9？

100
00:04:44,600 --> 00:04:45,690
不是吗？

101
00:04:45,690 --> 00:04:47,500
>> 好吧，去下一个。

102
00:04:47,500 --> 00:04:48,312
遵循它。

103
00:04:48,312 --> 00:04:49,520
它包含数字9？

104
00:04:49,520 --> 00:04:50,570
号

105
00:04:50,570 --> 00:04:51,550
按照下一个。

106
00:04:51,550 --> 00:04:55,490
>> 因此，我们必须以实际循环
通过我们的链接列表。

107
00:04:55,490 --> 00:05:00,070
我们不能只是去直接到9。

108
00:05:00,070 --> 00:05:05,860
如果你们真的想
看到一些伪代码在那里。

109
00:05:05,860 --> 00:05:10,420
在这里，我们有一些搜索功能
这需要in--需要做些什么呢？

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
你有什么感想？

112
00:05:14,320 --> 00:05:15,960
那么容易的。

113
00:05:15,960 --> 00:05:17,784
这是什么？

114
00:05:17,784 --> 00:05:18,700
听众：[听不清]。

115
00:05:18,700 --> 00:05:20,366
扬声器1：我们正在寻找的数量。

116
00:05:20,366 --> 00:05:20,980
对不对？

117
00:05:20,980 --> 00:05:22,875
什么会这样对应？

118
00:05:22,875 --> 00:05:25,020
这是一个指针？

119
00:05:25,020 --> 00:05:26,000
>> 听众：一个节点。

120
00:05:26,000 --> 00:05:28,980
>> 扬声器1：节点列表
我们正在寻找的，对不对？

121
00:05:28,980 --> 00:05:33,700
因此，我们有一些节点的指针位置。

122
00:05:33,700 --> 00:05:37,240
这是一个点，那将
通过我们的名单实际上迭代。

123
00:05:37,240 --> 00:05:39,630
我们设置它等于列表
因为这只是

124
00:05:39,630 --> 00:05:44,380
设置它等于
开始我们的链表。

125
00:05:44,380 --> 00:05:50,660
>> 虽然它不为NULL，而
我们还有东西在我们的列表中，

126
00:05:50,660 --> 00:05:55,580
检查，看看是否有节点
我们正在寻找的数字。

127
00:05:55,580 --> 00:05:57,740
返回true。

128
00:05:57,740 --> 00:06:01,070
否则，更新它，对不对？

129
00:06:01,070 --> 00:06:04,870
>> 如果为NULL，我们退出我们
while循环并返回false

130
00:06:04,870 --> 00:06:08,340
因为这意味着我们还没有找到它。

131
00:06:08,340 --> 00:06:11,048
每个人都得到如何工作的？

132
00:06:11,048 --> 00:06:11,548
行。

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> 因此，与插入，你
有三种不同的方式。

135
00:06:20,260 --> 00:06:25,250
您可以预先准备，可以追加
你可以插入到什。

136
00:06:25,250 --> 00:06:28,215
在这种情况下，我们
打算做一个预先准备。

137
00:06:28,215 --> 00:06:33,380
有谁知道这些
3案件可能会有所不同？

138
00:06:33,380 --> 00:06:36,920
>> 所以在前面加上意味着你把
它在列表的前面。

139
00:06:36,920 --> 00:06:39,770
因此，这将意味着，不管
你的节点，无论

140
00:06:39,770 --> 00:06:43,160
价值是什么，你要
把它放在这里在前面，好不好？

141
00:06:43,160 --> 00:06:45,160
这将成为第一
元素在列表中。

142
00:06:45,160 --> 00:06:49,510
>> 如果您添加它，它是怎么回事
去你的列表的后面。

143
00:06:49,510 --> 00:06:54,010
并插入到什意味着你
打算把实际进入的地方

144
00:06:54,010 --> 00:06:57,700
它让你的链接列表进行排序。

145
00:06:57,700 --> 00:07:00,810
同样，你如何使用
这些，当你使用

146
00:07:00,810 --> 00:07:02,530
他们会根据你的情况而有所不同。

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
如果不需要
进行排序，在前面加上趋于

149
00:07:07,750 --> 00:07:10,460
是大多数人
使用，因为你不知道

150
00:07:10,460 --> 00:07:15,680
要经过整个列表
寻找到底添加它，对不对？

151
00:07:15,680 --> 00:07:17,720
你可以把它贴对世权。

152
00:07:17,720 --> 00:07:21,930
>> 因此，我们将通过一个
插入1现在。

153
00:07:21,930 --> 00:07:26,360
这么一件事，我要去
强烈建议在此PSET

154
00:07:26,360 --> 00:07:29,820
是画出来的东西，一如既往。

155
00:07:29,820 --> 00:07:35,130
这是你更新是非常重要的
以正确的顺序你的指针

156
00:07:35,130 --> 00:07:38,620
因为如果你更新它们
稍微乱序，

157
00:07:38,620 --> 00:07:42,210
你要结束了
失去你的列表的一部分。

158
00:07:42,210 --> 00:07:49,680
>> 因此，例如，在这种情况下，我们
告诉头只点1。

159
00:07:49,680 --> 00:07:56,070
如果我们只是做了
不保存这个1，

160
00:07:56,070 --> 00:07:58,570
我们不知道是什么
1应指向现在

161
00:07:58,570 --> 00:08:02,490
因为我们已经失去了什么
该负责人指出。

162
00:08:02,490 --> 00:08:05,530
所以，有一点要记住
当你做了预先准备

163
00:08:05,530 --> 00:08:09,630
是拯救什么
头分排名第一，

164
00:08:09,630 --> 00:08:15,210
然后重新分配它，然后更新
你的新节点应该指向。

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
在这种情况下，这是为了做到这一点的方法之一。

167
00:08:22,560 --> 00:08:25,440
>> 因此，如果我们做了这种方式
在这里我们只是重新分配头，

168
00:08:25,440 --> 00:08:30,320
我们失去了我们的基本
整个列表，对不对？

169
00:08:30,320 --> 00:08:38,000
做到这一点的方法之一是有1个点
接下来，再有头点1。

170
00:08:38,000 --> 00:08:42,650
或者，你可以种不喜欢的
临时存储，这是我所津津乐道。

171
00:08:42,650 --> 00:08:45,670
>> 但是，重新分配你的
以正确的顺序指针

172
00:08:45,670 --> 00:08:48,750
将是非常，非常
重要的是这个PSET。

173
00:08:48,750 --> 00:08:53,140
否则，你将有一个哈希
表或一个尝试，这只是将要

174
00:08:53,140 --> 00:08:56,014
的话只有部分是你
想要再you're-- mmhmm？

175
00:08:56,014 --> 00:08:58,930
听众：什么是临时
存储的东西你在说什么？

176
00:08:58,930 --> 00:09:00,305
扬声器1：临时存储。

177
00:09:00,305 --> 00:09:02,760
所以基本上另一
这样你可以这样做

178
00:09:02,760 --> 00:09:07,650
是存放东西的脑袋，像
存放临时变量。

179
00:09:07,650 --> 00:09:11,250
其分配到1
然后更新1点

180
00:09:11,250 --> 00:09:13,830
以什么头用来指向。

181
00:09:13,830 --> 00:09:16,920
这种方式显然是
因为你更优雅

182
00:09:16,920 --> 00:09:20,770
不需要一个临时值，但
只是提供了另一种方式来做到这一点。

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
而我们实际上做有
一些代码这一点。

185
00:09:25,790 --> 00:09:28,080
所以对于链表，我们
实际上有一些代码。

186
00:09:28,080 --> 00:09:31,930
所以在此处插入，这是预先考虑。

187
00:09:31,930 --> 00:09:34,290
所以这个进入它的头。

188
00:09:34,290 --> 00:09:38,820
>> 所以第一件事情，你需要
当然，创造你的新节点，

189
00:09:38,820 --> 00:09:40,790
并检查是否为NULL。

190
00:09:40,790 --> 00:09:43,250
总是好的。

191
00:09:43,250 --> 00:09:47,840
然后你需要指定的值。

192
00:09:47,840 --> 00:09:51,260
当你创建一个新的节点，你
不知道它的指向下一个，

193
00:09:51,260 --> 00:09:54,560
所以你想要初始化为NULL。

194
00:09:54,560 --> 00:09:58,760
如果它最终指向事
否则，它就会被重新分配，它的罚款。

195
00:09:58,760 --> 00:10:00,740
如果这是第一件事情
在列表中，则需要

196
00:10:00,740 --> 00:10:04,270
指向null，因为
这是该列表的末尾。

197
00:10:04,270 --> 00:10:12,410
>> 所以后来插入的话，我们在这里看到我们
被分配了节点的下一个值

198
00:10:12,410 --> 00:10:17,380
是什么头，
这就是我们不得不在这里。

199
00:10:17,380 --> 00:10:19,930
这就是我们只是做了。

200
00:10:19,930 --> 00:10:25,820
然后我们分配头点
我们的新节点，因为要记住，

201
00:10:25,820 --> 00:10:31,090
新是一些指针到一个节点，
而这正是头是什么。

202
00:10:31,090 --> 00:10:34,370
这就是为什么我们
有这个箭头访问。

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
很酷吧？

205
00:10:37,530 --> 00:10:38,130
Mmhmm​​？

206
00:10:38,130 --> 00:10:41,100
>> 听众：我们得
初始化新的下一位第一为NULL，

207
00:10:41,100 --> 00:10:44,240
或者我们只是把它初始化为头？

208
00:10:44,240 --> 00:10:48,210
>> 扬声器1：新下一个
需要为NULL启动

209
00:10:48,210 --> 00:10:53,760
因为你不知道
那里将是。

210
00:10:53,760 --> 00:10:56,100
此外，这是怎么样的
就像一个范例。

211
00:10:56,100 --> 00:10:59,900
你将其设置为NULL只是为了
确保你所有的基地都覆盖

212
00:10:59,900 --> 00:11:04,070
你这样做，任何重新分配前
你总是保证它会

213
00:11:04,070 --> 00:11:08,880
被指向的特定值
与像一个垃圾值。

214
00:11:08,880 --> 00:11:12,210
因为，是的，我们分配
新的自动接下来，

215
00:11:12,210 --> 00:11:15,420
但它更多的只是像
好的做法进行初始化

216
00:11:15,420 --> 00:11:19,270
以这种方式，并重新分配。

217
00:11:19,270 --> 00:11:23,420
>> 好了，现在双链表。

218
00:11:23,420 --> 00:11:24,601
我们怎么想的？

219
00:11:24,601 --> 00:11:26,350
有什么不同
双向链表？

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> 所以在我们的链表，我们可以
只朝一个方向，对不对？

222
00:11:34,300 --> 00:11:35,270
我们只有下一个。

223
00:11:35,270 --> 00:11:36,760
我们只能往前走。

224
00:11:36,760 --> 00:11:40,300
>> 用一个双向链表，
我们还可以向后移动。

225
00:11:40,300 --> 00:11:44,810
因此，我们不仅
我们要存储号码，

226
00:11:44,810 --> 00:11:50,110
我们有它指向下一个
当我们刚刚从。

227
00:11:50,110 --> 00:11:52,865
所以这允许
一些更好的遍历。

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> 因此，双向链表节点，
非常相似的，对不对？

230
00:12:01,240 --> 00:12:05,000
唯一不同的是，现在我们
有下一个和前一个。

231
00:12:05,000 --> 00:12:06,235
这是唯一的区别。

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> 所以，如果我们要在前面或append--我们
没有任何代码此向上这里 - 

234
00:12:14,790 --> 00:12:17,830
但如果你要尝试
插入，最重要的事情

235
00:12:17,830 --> 00:12:19,980
就是你需要
确保你分配

236
00:12:19,980 --> 00:12:23,360
无论你以前和你
下一个指针正常。

237
00:12:23,360 --> 00:12:29,010
因此，在这种情况下，你会
不仅初始化旁边，

238
00:12:29,010 --> 00:12:31,820
在初始化以前。

239
00:12:31,820 --> 00:12:36,960
如果我们在列表的头部，我们
不但使头部等于新，

240
00:12:36,960 --> 00:12:41,750
但我们的新的前应
点了头，对吧？

241
00:12:41,750 --> 00:12:43,380
>> 这是唯一的区别。

242
00:12:43,380 --> 00:12:47,200
如果你想有更多的实践
这些用链表，用插入，

243
00:12:47,200 --> 00:12:49,900
与删除，插入带
成什锦列表，

244
00:12:49,900 --> 00:12:52,670
请查看study.cs50.net。

245
00:12:52,670 --> 00:12:54,870
有一群伟大的演习。

246
00:12:54,870 --> 00:12:55,870
我极力推荐他们。

247
00:12:55,870 --> 00:12:59,210
我希望我们有时间去通过他们
但有很多数据结构

248
00:12:59,210 --> 00:13:01,530
打通。

249
00:13:01,530 --> 00:13:02,650
>> 好了，哈希表。

250
00:13:02,650 --> 00:13:07,070
这可能是最
您PSET有用位

251
00:13:07,070 --> 00:13:11,090
在这里，因为你将要
执行其中的一个或一试。

252
00:13:11,090 --> 00:13:12,200
我真的很喜欢哈希表。

253
00:13:12,200 --> 00:13:13,110
他们很酷。

254
00:13:13,110 --> 00:13:17,080
>> 所以基本上什么
发生的情况是一个哈希表

255
00:13:17,080 --> 00:13:22,050
当我们真正需要迅速
插入，删除和查找。

256
00:13:22,050 --> 00:13:25,010
这些都是东西，我们
在哈希表中优先考虑。

257
00:13:25,010 --> 00:13:29,500
他们可以得到相当大的，
但我们会尝试用看，

258
00:13:29,500 --> 00:13:33,040
有些事情是要大得多。

259
00:13:33,040 --> 00:13:38,330
>> 但基本上，所有的散列
表是散列函数

260
00:13:38,330 --> 00:13:47,215
告诉你哪个桶把每
您的数据，每一个在你的元素。

261
00:13:47,215 --> 00:13:51,140
一个简单的方法去思考一个哈希表
是它的事情只是水桶，

262
00:13:51,140 --> 00:13:51,770
对不对？

263
00:13:51,770 --> 00:13:59,720
所以，当你被排序的东西
就像他们的名字的第一个字母，

264
00:13:59,720 --> 00:14:01,820
这有点像一个哈希表。

265
00:14:01,820 --> 00:14:06,180
>> 所以，如果我是组你们是
到谁的名字开始组

266
00:14:06,180 --> 00:14:11,670
用A看过来，或者谁的生日
在一月，二月，三月，

267
00:14:11,670 --> 00:14:15,220
什么，那就是有效
创建哈希表。

268
00:14:15,220 --> 00:14:18,120
它只是创造了水桶
你的元素进行排序成

269
00:14:18,120 --> 00:14:19,520
这样您就可以找到他们更容易。

270
00:14:19,520 --> 00:14:22,300
所以这样一来，当我需要
找一个你，

271
00:14:22,300 --> 00:14:24,680
我没有搜索
通过您的每一个名字。

272
00:14:24,680 --> 00:14:29,490
我可以想，哦，我知道，
丹妮的生日是in--

273
00:14:29,490 --> 00:14:30,240
听众：--April。

274
00:14:30,240 --> 00:14:30,948
扬声器1：四月。

275
00:14:30,948 --> 00:14:33,120
所以，我期待在我的四月
斗，与任何运气，

276
00:14:33,120 --> 00:14:38,270
她会在那里唯一的一个，
我的时间是在这个意义上不变，

277
00:14:38,270 --> 00:14:41,230
而如果我要看看
通过一大堆的人，

278
00:14:41,230 --> 00:14:43,090
这将花费更长的时间。

279
00:14:43,090 --> 00:14:45,830
因此，哈希表是真的只是水桶。

280
00:14:45,830 --> 00:14:48,630
简单的方法，他们的看法。

281
00:14:48,630 --> 00:14:52,930
>> 因此，关于一个很重要的事情
哈希表是一个散列函数。

282
00:14:52,930 --> 00:14:58,140
所以事情我刚才讲的，像
您的名字的第一个字母

283
00:14:58,140 --> 00:15:01,450
或者你的生日月，
这些想法，

284
00:15:01,450 --> 00:15:03,070
真关联到哈希函数。

285
00:15:03,070 --> 00:15:08,900
这是确定的只是一个方式，也
斗你是元素进入，OK？

286
00:15:08,900 --> 00:15:14,850
因此，对于这pset中，你可以看一下
几乎任何你想要的哈希函数。

287
00:15:14,850 --> 00:15:16,030
>> 并不一定是你自己。

288
00:15:16,030 --> 00:15:21,140
有一些很酷的的人了
那里，做各种疯狂的数学。

289
00:15:21,140 --> 00:15:25,170
如果你想使你的
拼写检查超快，

290
00:15:25,170 --> 00:15:27,620
我肯定会
看看其中的一个。

291
00:15:27,620 --> 00:15:32,390
>> 但也有在
简单的，如计算

292
00:15:32,390 --> 00:15:39,010
的话，总和一样
每个字母的数。

293
00:15:39,010 --> 00:15:39,940
计算总和。

294
00:15:39,940 --> 00:15:42,230
用于确定桶。

295
00:15:42,230 --> 00:15:45,430
他们也有难办的
就像所有的A的位置，

296
00:15:45,430 --> 00:15:47,050
所有的B的在这里。

297
00:15:47,050 --> 00:15:48,920
这些中的任何一个。

298
00:15:48,920 --> 00:15:55,770
>> 基本上，它只是告诉你哪个
数组索引你的元素应该进入。

299
00:15:55,770 --> 00:15:58,690
刚刚决定bucket--
这是所有的哈希函数是。

300
00:15:58,690 --> 00:16:04,180
所以在这里，我们有一个例子是
字符串的只是第一信

301
00:16:04,180 --> 00:16:05,900
我只是在谈论。

302
00:16:05,900 --> 00:16:11,900
>> 所以，你有一些散，这仅仅是
您的字符串减去A的第一个字母，

303
00:16:11,900 --> 00:16:16,090
这会给你一些
介于0和25号。

304
00:16:16,090 --> 00:16:20,790
和你想要做的是什么
确保这代表

305
00:16:20,790 --> 00:16:24,110
您的散列的大小table--
多少个水桶也有。

306
00:16:24,110 --> 00:16:25,860
许多这类
散列函数，它们是

307
00:16:25,860 --> 00:16:31,630
将要返回的值可能
要远远高于桶的数量

308
00:16:31,630 --> 00:16:33,610
那你确实有
在哈希表

309
00:16:33,610 --> 00:16:37,240
所以你需要
肯定和那些国防部。

310
00:16:37,240 --> 00:16:42,190
否则，它会说，
哦，应该是在5000桶

311
00:16:42,190 --> 00:16:46,040
但你只有30
水桶中的哈希表。

312
00:16:46,040 --> 00:16:49,360
当然，我们都知道这是
会导致一些疯狂的错误。

313
00:16:49,360 --> 00:16:52,870
所以一定要确保由于MOD
您的哈希表的大小。

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
凉爽。

316
00:16:58,930 --> 00:17:00,506
所以碰撞。

317
00:17:00,506 --> 00:17:02,620
是每个人都好这么远吗？

318
00:17:02,620 --> 00:17:03,120
Mmhmm​​？

319
00:17:03,120 --> 00:17:05,900
>> 听众：为什么会
返回这样一个庞大的价值呢？

320
00:17:05,900 --> 00:17:09,210
>> 扬声器1：根据不同的算法
您的哈希函数使用。

321
00:17:09,210 --> 00:17:12,270
有些人会做
疯狂繁殖。

322
00:17:12,270 --> 00:17:16,270
它的所有有关获取
一个均匀分布，

323
00:17:16,270 --> 00:17:18,490
所以他们做一些真正
有时是疯狂的事情。

324
00:17:18,490 --> 00:17:20,960
就这样。

325
00:17:20,960 --> 00:17:22,140
还要别的吗？

326
00:17:22,140 --> 00:17:22,829
行。

327
00:17:22,829 --> 00:17:24,480
>> 所以碰撞。

328
00:17:24,480 --> 00:17:29,270
基本上，正如我刚才所说，
在最好的情况下，

329
00:17:29,270 --> 00:17:32,040
任何斗我看看是
将有一件事，

330
00:17:32,040 --> 00:17:34,160
所以我没有看全，对不对？

331
00:17:34,160 --> 00:17:37,040
我不是知道它的存在，或者它
不，这是我们真正想要的。

332
00:17:37,040 --> 00:17:43,960
但是，如果我们有数万
数据点和小于号

333
00:17:43,960 --> 00:17:48,700
桶，我们将有
碰撞中，最终的东西

334
00:17:48,700 --> 00:17:54,210
即将要结束了
斗已经有一个元素。

335
00:17:54,210 --> 00:17:57,390
>> 所以，问题是，什么样
我们在这种情况下怎么办？

336
00:17:57,390 --> 00:17:58,480
我们该怎么办？

337
00:17:58,480 --> 00:17:59,300
我们已经有了的东西呢？

338
00:17:59,300 --> 00:18:00,060
难道我们只是把它扔出去？

339
00:18:00,060 --> 00:18:00,700
>> 号

340
00:18:00,700 --> 00:18:01,980
我们必须保持他们两个。

341
00:18:01,980 --> 00:18:06,400
这样的方式，我们
通常做的是什么吗？

342
00:18:06,400 --> 00:18:08,400
是什么数据结构
我们刚才讲？

343
00:18:08,400 --> 00:18:09,316
听众：链表。

344
00:18:09,316 --> 00:18:10,500
扬声器1：链表。

345
00:18:10,500 --> 00:18:16,640
所以，现在的，而不是每个这些
水桶只是有一个元素，

346
00:18:16,640 --> 00:18:24,020
它会包含一个链接列表
这被散列到它的元素。

347
00:18:24,020 --> 00:18:27,588
好了，大家都种得出来的？

348
00:18:27,588 --> 00:18:30,546
因为我们不能有一个数组
因为我们不知道有多少东西

349
00:18:30,546 --> 00:18:31,730
将要在那里。

350
00:18:31,730 --> 00:18:36,540
链表可以让我们
刚刚确切的数字，

351
00:18:36,540 --> 00:18:38,465
被散列成水桶，对不对？

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> 所以线性探测是
基本上这idea--

354
00:18:50,500 --> 00:18:52,300
这是应对碰撞的一种方式。

355
00:18:52,300 --> 00:18:58,010
你可以做的是，如果在这
情况下，浆果被散列到1

356
00:18:58,010 --> 00:19:01,130
我们已经有了
那里的东西，你只要

357
00:19:01,130 --> 00:19:04,840
继续下去，直到
你找到一个空槽。

358
00:19:04,840 --> 00:19:06,370
这是一种方式来处理它。

359
00:19:06,370 --> 00:19:09,020
另一种方式来处理
它是我们刚才

360
00:19:09,020 --> 00:19:12,280
called--链接
列表被称为链接。

361
00:19:12,280 --> 00:19:20,510
>> 所以这个想法，如果工作
您的哈希表，你认为

362
00:19:20,510 --> 00:19:24,150
比大得多
您的数据集，或者如果你

363
00:19:24,150 --> 00:19:28,870
想尝试和减少链接
直到它的绝对必要。

364
00:19:28,870 --> 00:19:34,050
因此，有一点是线性的
探测手段明显

365
00:19:34,050 --> 00:19:37,290
您的散列函数
是不是很实用

366
00:19:37,290 --> 00:19:42,200
因为你要使用到结束
您的散列函数，得到一个点，

367
00:19:42,200 --> 00:19:46,400
你的线阵探头向下
一些地方可用。

368
00:19:46,400 --> 00:19:49,670
但现在，当然，任何事情
别人说结束了那里，

369
00:19:49,670 --> 00:19:52,050
你将不得不
搜索甚至进一步下跌。

370
00:19:52,050 --> 00:19:55,650
>> 而且还有很多更
搜索的费用

371
00:19:55,650 --> 00:19:59,820
进入输入一个元素
在现在的哈希表，对不对？

372
00:19:59,820 --> 00:20:05,640
而现在，当你去尝试和发现
浆果再次，你要凑吧，

373
00:20:05,640 --> 00:20:07,742
而且它会说，
哦，在斗1看，

374
00:20:07,742 --> 00:20:09,700
而且它不会是
在斗1，所以你

375
00:20:09,700 --> 00:20:11,970
将不得不穿越
通过对这些休息。

376
00:20:11,970 --> 00:20:17,720
所以，它有时是有用的，
但在大多数情况下，

377
00:20:17,720 --> 00:20:22,660
我们要指出，
链接是你想做的事。

378
00:20:22,660 --> 00:20:25,520
>> 所以，我们谈到了这点。

379
00:20:25,520 --> 00:20:27,812
我得到了我自己一点点前进。

380
00:20:27,812 --> 00:20:33,560
但链基本上是
在哈希表中的每一桶

381
00:20:33,560 --> 00:20:36,120
仅仅是一个链表。

382
00:20:36,120 --> 00:20:39,660
>> 这样的另一种方式，或更多的技术
这样，想到一个哈希表

383
00:20:39,660 --> 00:20:44,490
是，它只是一个数组
链表，哪

384
00:20:44,490 --> 00:20:49,330
你写你的字典时，
而你试图加载它，

385
00:20:49,330 --> 00:20:52,070
想到它是一个
链表的数组

386
00:20:52,070 --> 00:20:54,390
将使它更容易
为您初始化。

387
00:20:54,390 --> 00:20:57,680
>> 听众：所以哈希表
具有预定的大小，

388
00:20:57,680 --> 00:20:58,980
像水桶的[听不清]？

389
00:20:58,980 --> 00:20:59,220
>> 扬声器1：没错。

390
00:20:59,220 --> 00:21:01,655
所以它有一组数
你determine--桶

391
00:21:01,655 --> 00:21:03,530
这你们应该
随便玩。

392
00:21:03,530 --> 00:21:05,269
它可以是很酷
看看会发生什么

393
00:21:05,269 --> 00:21:06,810
当你改变你的桶数。

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
但是，是的，它有一个
桶的设置数量。

396
00:21:11,510 --> 00:21:15,360
是什么让你满足的
因为你需要很多元素

397
00:21:15,360 --> 00:21:19,350
这是单独的链接，你
已在每个桶链表。

398
00:21:19,350 --> 00:21:22,850
这意味着你的哈希表
会完全大小

399
00:21:22,850 --> 00:21:25,440
你需要它，对不对？

400
00:21:25,440 --> 00:21:27,358
这就是链表的整点。

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
凉爽。

403
00:21:32,480 --> 00:21:38,780
>> 所以每个人都需要帮助吗？

404
00:21:38,780 --> 00:21:39,801
行。

405
00:21:39,801 --> 00:21:40,300
啊。

406
00:21:40,300 --> 00:21:41,860
刚刚发生了什么？

407
00:21:41,860 --> 00:21:42,960
现在真的。

408
00:21:42,960 --> 00:21:45,250
猜猜谁是杀害我。

409
00:21:45,250 --> 00:21:52,060
>> OK，我们要进入
尝试，这是一个有点疯狂。

410
00:21:52,060 --> 00:21:53,140
我喜欢的哈希表。

411
00:21:53,140 --> 00:21:54,460
我觉得他们真的很酷。

412
00:21:54,460 --> 00:21:56,710
尝试凉爽了。

413
00:21:56,710 --> 00:21:59,590
>> 因此，没有人记得一试的是？

414
00:21:59,590 --> 00:22:01,740
你应该已经走了过来
它简要地讲？

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
你还记得那种它是如何工作的？

417
00:22:06,377 --> 00:22:08,460
听众：我只是点头
我们也去了吧。

418
00:22:08,460 --> 00:22:09,626
扬声器1：我们过目一下。

419
00:22:09,626 --> 00:22:13,100
OK，我们真的要去
在它现在是我们在说什么。

420
00:22:13,100 --> 00:22:14,860
>> 听众：这是一个检索树。

421
00:22:14,860 --> 00:22:15,280
>> 扬声器1：是啊。

422
00:22:15,280 --> 00:22:16,196
这是一个检索树。

423
00:22:16,196 --> 00:22:16,960
真棒。

424
00:22:16,960 --> 00:22:23,610
所以，有一点这里要注意的是，我们
正在寻找单个字符

425
00:22:23,610 --> 00:22:24,480
在这里，对不对？

426
00:22:24,480 --> 00:22:29,710
>> 所以在我们的哈希函数，我们
所寻找的单词作为一个整体，

427
00:22:29,710 --> 00:22:32,270
现在我们正在寻找更多的
在人物了吧？

428
00:22:32,270 --> 00:22:38,380
因此，我们有麦克斯韦在这里和孟德尔。

429
00:22:38,380 --> 00:22:47,840
所以基本上一个try--的方式来思考
这个是每个层次在这里

430
00:22:47,840 --> 00:22:49,000
是字母数组。

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
因此，这是你的根结在这里，对不对？

433
00:22:55,790 --> 00:23:01,980
这具有的所有字符
字母的每一个字的开始。

434
00:23:01,980 --> 00:23:06,480
>> 和你想要做的是什么
说好，我们有一些M个字。

435
00:23:06,480 --> 00:23:10,590
我们要寻找麦克斯韦，所以
我们去的M.和M点整

436
00:23:10,590 --> 00:23:14,800
另外一个数组，其中每
总之，只要存在

437
00:23:14,800 --> 00:23:17,044
是一个具有一个字
作为第二个字母，

438
00:23:17,044 --> 00:23:19,460
只要有一个字
有B作为第二个字母，

439
00:23:19,460 --> 00:23:24,630
它将有一个指针
去一些旁边的数组。

440
00:23:24,630 --> 00:23:29,290
>> 有可能不是一个
词MP的东西，

441
00:23:29,290 --> 00:23:32,980
所以在此P位置
数组，它只是为NULL。

442
00:23:32,980 --> 00:23:38,840
它会说，OK，没有字
即有m个后跟一个P，好不好？

443
00:23:38,840 --> 00:23:43,100
因此，如果我们仔细想想，每个
这些较小的事情之一

444
00:23:43,100 --> 00:23:47,990
实际上是其中之一
到Z大阵列从A

445
00:23:47,990 --> 00:23:55,064
那么，什么可能的事情之一
这是怎样的一个尝试的缺点呢？

446
00:23:55,064 --> 00:23:56,500
>> 听众：大量的内存。

447
00:23:56,500 --> 00:23:59,940
>> 扬声器1：这是一吨的记忆，不是吗？

448
00:23:59,940 --> 00:24:08,750
每一个这些块在这里
代表26位，26个元素的数组。

449
00:24:08,750 --> 00:24:13,680
因此，试图获得令人难以置信的太空沉重。

450
00:24:13,680 --> 00:24:17,100
>> 但他们都非常快。

451
00:24:17,100 --> 00:24:22,540
如此令人难以置信的速度快，但
真是浪费空间。

452
00:24:22,540 --> 00:24:24,810
那种有图
哪一个你想要的。

453
00:24:24,810 --> 00:24:29,470
这是真的很酷您PSET，
但他们占用了大量的内存，

454
00:24:29,470 --> 00:24:30,290
所以你权衡。

455
00:24:30,290 --> 00:24:31,480
是吗？

456
00:24:31,480 --> 00:24:34,300
>> 听众：有没有可能
建立一个尝试，然后

457
00:24:34,300 --> 00:24:37,967
一旦你把所有的
你need--在它的数据

458
00:24:37,967 --> 00:24:39,550
我不知道这是否会是有意义的。

459
00:24:39,550 --> 00:24:42,200
我摆脱所有
NULL字符，但随后

460
00:24:42,200 --> 00:24:42,910
你就不能够索引them--

461
00:24:42,910 --> 00:24:43,275
>> 扬声器1：您仍然需要他们。

462
00:24:43,275 --> 00:24:44,854
>> 听众： - 每次以相同的方式。

463
00:24:44,854 --> 00:24:45,520
扬声器1：是啊。

464
00:24:45,520 --> 00:24:50,460
您需要NULL字符来让
你知道，如果有没有一个字出现。

465
00:24:50,460 --> 00:24:52,040
奔你有什么，你想要什么？

466
00:24:52,040 --> 00:24:52,540
行。

467
00:24:52,540 --> 00:24:54,581
好了，所以我们要
去多一点点

468
00:24:54,581 --> 00:24:58,920
进入技术细节的背后
一试，并通过一个实例运行。

469
00:24:58,920 --> 00:25:01,490
>> 好了，这是同样的事情。

470
00:25:01,490 --> 00:25:06,290
而在一个链表，我们的主要
那种of--什么是我想要的字？ - 

471
00:25:06,290 --> 00:25:08,350
像积木是一个节点。

472
00:25:08,350 --> 00:25:12,280
在一个尝试，我们也有一个节点，
但它的定义不同。

473
00:25:12,280 --> 00:25:17,000
>> 因此，我们有一些布尔值，
代表实际上无论是词

474
00:25:17,000 --> 00:25:23,530
存在于这个位置，然后
我们有一些阵这里 - 或者更确切地说，

475
00:25:23,530 --> 00:25:27,840
这是一个指向
阵列的27个字符。

476
00:25:27,840 --> 00:25:33,339
这是因为，在这种情况下，这
27--我相信在座的各位都是这样，等待，

477
00:25:33,339 --> 00:25:34,880
有字母表中的26个字母。

478
00:25:34,880 --> 00:25:36,010
为什么我们有27？

479
00:25:36,010 --> 00:25:37,870
>> 这样根据不同的
要实现这种方式，

480
00:25:37,870 --> 00:25:43,240
这是从一个pset中那
允许撇号。

481
00:25:43,240 --> 00:25:46,010
所以这就是为什么额外的之一。

482
00:25:46,010 --> 00:25:50,500
您还可以有一些
情况下，空终止

483
00:25:50,500 --> 00:25:53,230
被包含的所述一个
即它允许为字符，

484
00:25:53,230 --> 00:25:56,120
这就是他们如何检查
看它是否是该字的结束。

485
00:25:56,120 --> 00:26:01,340
如果您有兴趣，请查看
凯文的视频study.cs50，

486
00:26:01,340 --> 00:26:04,790
以及维基百科
一些很好的资源在那里。

487
00:26:04,790 --> 00:26:09,000
>> 但是，我们要通过正中下怀
您可能如何工作，通过一试

488
00:26:09,000 --> 00:26:11,010
如果你正在考虑之一。

489
00:26:11,010 --> 00:26:16,230
因此，我们有一个超级简单的在这里，
有句话“蝙蝠”和“缩放”在其中。

490
00:26:16,230 --> 00:26:18,920
正如我们看到的在这里，
在这里这个小空间

491
00:26:18,920 --> 00:26:22,560
代表了我们的布尔值，
说，是的，这是一个字。

492
00:26:22,560 --> 00:26:27,060
然后这有我们
字符数组，对不对？

493
00:26:27,060 --> 00:26:33,480
>> 所以，我们要通过
发现在这个尝试“蝙蝠”。

494
00:26:33,480 --> 00:26:38,340
所以，从高层开始，对不对？

495
00:26:38,340 --> 00:26:46,290
我们知道，B对应
第二索引，所述第二元件

496
00:26:46,290 --> 00:26:47,840
在这个阵列中，因为a和b。

497
00:26:47,840 --> 00:26:51,340
所以大约第二个。

498
00:26:51,340 --> 00:26:58,820
>> 它说，OK，冷静，按照成
下一个阵列，因为如果我们记得，

499
00:26:58,820 --> 00:27:02,160
这并不是说所有这些
实际上包含元件。

500
00:27:02,160 --> 00:27:07,110
这些阵列中的每一个
包含一个指针，对不对？

501
00:27:07,110 --> 00:27:10,030
这是做一个重要的区别。

502
00:27:10,030 --> 00:27:13,450
>> 我知道这是要be--尝试的
真的很难得上是第一次，

503
00:27:13,450 --> 00:27:15,241
所以，即使是这样的
第二次或第三次

504
00:27:15,241 --> 00:27:18,370
而且它仍然是一种
看似很难的，

505
00:27:18,370 --> 00:27:21,199
我保证，如果你去观看
短期再度明天

506
00:27:21,199 --> 00:27:22,740
这可能会使得很多更有意义。

507
00:27:22,740 --> 00:27:23,890
这需要大量的消化。

508
00:27:23,890 --> 00:27:27,800
我有时仍然很
象，等等，什么是一试？

509
00:27:27,800 --> 00:27:29,080
我该如何使用呢？

510
00:27:29,080 --> 00:27:33,880
>> 所以我们B在这种情况下，
这是我们的第二个索引。

511
00:27:33,880 --> 00:27:40,240
如果我们有，比方说，C或
d或任何其他字母，

512
00:27:40,240 --> 00:27:45,810
我们需要映射回索引
我们的数组的对应。

513
00:27:45,810 --> 00:27:56,930
因此，我们将采取类似rchar，我们只是
减去掀起了将其映射到0〜25。

514
00:27:56,930 --> 00:27:58,728
大家好，我们怎么样
地图我们的角色？

515
00:27:58,728 --> 00:28:00,440
行。

516
00:28:00,440 --> 00:28:05,980
>> 所以我们去的第二个和我们
看，是的，它不是为NULL。

517
00:28:05,980 --> 00:28:07,780
我们可以继续在下一个数组。

518
00:28:07,780 --> 00:28:12,300
所以我们去到这一个阵列在这里。

519
00:28:12,300 --> 00:28:15,500
>> 和我们说，好了，现在我们
需要看到，如果是在这里。

520
00:28:15,500 --> 00:28:18,590
为空或做它
其实往前走？

521
00:28:18,590 --> 00:28:21,880
所以实际上移动
转发此数组中。

522
00:28:21,880 --> 00:28:24,570
我们说好，t是我们的最后一个字母。

523
00:28:24,570 --> 00:28:27,580
所以我们去到T的索引。

524
00:28:27,580 --> 00:28:30,120
然后我们继续前进
因为有另一个。

525
00:28:30,120 --> 00:28:38,340
而这一次，基本上说，是的，
它说，有一句话这里 - 

526
00:28:38,340 --> 00:28:41,750
如果你遵循这一点，
路径，你已经到了

527
00:28:41,750 --> 00:28:43,210
在一个字，这是我们所知道的是“蝙蝠”。

528
00:28:43,210 --> 00:28:43,800
是吗？

529
00:28:43,800 --> 00:28:46,770
>> 听众：是不是标准有
为索引0，然后有一个排序的1

530
00:28:46,770 --> 00:28:47,660
或有在结束了吗？

531
00:28:47,660 --> 00:28:48,243
>> 扬声器1：第

532
00:28:48,243 --> 00:28:55,360
因此，如果我们回头看我们的
在这里声明，这是一个布尔值，

533
00:28:55,360 --> 00:28:59,490
所以它在你的节点自身的元素。

534
00:28:59,490 --> 00:29:03,331
所以它不是数组的一部分。

535
00:29:03,331 --> 00:29:03,830
凉爽。

536
00:29:03,830 --> 00:29:08,370
所以，当我们完成我们的话，我们很
在这个数组，我们想要做的

537
00:29:08,370 --> 00:29:12,807
是做一个检查，这是一个单词。

538
00:29:12,807 --> 00:29:14,390
在这种情况下，它会返回是。

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> 所以，关于这一点，我们知道“动物园” - 
我们知道，作为人类的“动物园”是一个词，

541
00:29:24,090 --> 00:29:24,820
对不对？

542
00:29:24,820 --> 00:29:28,990
但尽量会在这里
说，不，它不是。

543
00:29:28,990 --> 00:29:33,980
它会说，因为我们
没有指定它作为这里一个字。

544
00:29:33,980 --> 00:29:40,440
尽管我们可以遍历
通过对这个阵列中，

545
00:29:40,440 --> 00:29:43,890
这种尝试会说，不，
动物园是不是在你的字典

546
00:29:43,890 --> 00:29:47,070
因为我们还没有
指定它是这样。

547
00:29:47,070 --> 00:29:52,870
>> 因此从另一个角度做that--
哦，对不起，这一项。

548
00:29:52,870 --> 00:29:59,450
所以在这种情况下，“动物园”是不
一个字，但它是在我们的尝试。

549
00:29:59,450 --> 00:30:05,690
但在这其中，说我们想让它
介绍词“洗澡”，会发生什么

550
00:30:05,690 --> 00:30:08,260
是我们遵循through-- B，A，T。

551
00:30:08,260 --> 00:30:11,820
我们在这个数组中，
我们去寻找小时。

552
00:30:11,820 --> 00:30:15,220
>> 在这种情况下，当我们
看指针小时，

553
00:30:15,220 --> 00:30:17,890
它指向NULL，好不好？

554
00:30:17,890 --> 00:30:20,780
所以，除非它是明确的
指着另一个数组，

555
00:30:20,780 --> 00:30:25,000
你以为所有的指针
在这个阵列指向空。

556
00:30:25,000 --> 00:30:28,270
所以在这种情况中，h是指向
为null，所以我们不能做任何事情，

557
00:30:28,270 --> 00:30:31,540
因此它也将返回
假的，“洗澡”是不是在这里。

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
所以，现在我们实际上
要经过

560
00:30:35,810 --> 00:30:39,790
怎么会，我们实际上说
该“动物园”是我们的尝试。

561
00:30:39,790 --> 00:30:42,920
我们如何将“动物园”到我们试试？

562
00:30:42,920 --> 00:30:47,810
所以在我们开始以相同的方式
我们的链表，我们从根开始。

563
00:30:47,810 --> 00:30:50,600
如有疑问，开始
这些东西的根源。

564
00:30:50,600 --> 00:30:53,330
>> 我们会说，OK，Z。

565
00:30:53,330 --> 00:30:55,650
ž存在于此，并且它的作用。

566
00:30:55,650 --> 00:30:58,370
所以你移动到
你的下一个阵列，好不好？

567
00:30:58,370 --> 00:31:01,482
然后就下单，
我们说好，不Ø存在吗？

568
00:31:01,482 --> 00:31:03,000
它的作用。

569
00:31:03,000 --> 00:31:04,330
这再次。

570
00:31:04,330 --> 00:31:08,670
>> 等我们下单，我们已经说过了，
OK，“动物园”已经存在这里。

571
00:31:08,670 --> 00:31:12,440
所有我们需要做的是设置此相等
为true时，有一个词出现。

572
00:31:12,440 --> 00:31:15,260
如果你遵循了一切
到该点之前，

573
00:31:15,260 --> 00:31:17,030
这是一个字，所以只
设置它等于这样的。

574
00:31:17,030 --> 00:31:17,530
是吗？

575
00:31:17,530 --> 00:31:22,550
>> 听众：所以后来做了
意思是“巴”是一个字也？

576
00:31:22,550 --> 00:31:24,120
>> 扬声器1：第

577
00:31:24,120 --> 00:31:28,870
因此，在这种情况下，“巴”，我们会得到
在这里，我们想说的是一个字，

578
00:31:28,870 --> 00:31:31,590
并且它仍然是否定的。

579
00:31:31,590 --> 00:31:32,822
行？

580
00:31:32,822 --> 00:31:33,740
Mmhmm​​？

581
00:31:33,740 --> 00:31:36,360
>> 听众：所以一旦你是一个
一句话，你说是，那么它

582
00:31:36,360 --> 00:31:38,380
将包含去米？

583
00:31:38,380 --> 00:31:42,260
>> 扬声器1：所以这个必须做
with--你加载此研究。

584
00:31:42,260 --> 00:31:43,640
你说的“动物园”一词。

585
00:31:43,640 --> 00:31:47,020
当你去check--
喜欢，说你想说的话，

586
00:31:47,020 --> 00:31:49,400
在这个字典里“动物园”的存在？

587
00:31:49,400 --> 00:31:54,200
你只会搜索“动物园”
然后检查，看它是否是一个字。

588
00:31:54,200 --> 00:31:57,291
你永远不会动
通过对米，因为这不是

589
00:31:57,291 --> 00:31:58,290
您要查找的内容。

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> 因此，如果我们真的想
添加“洗澡”这个尝试，

592
00:32:08,070 --> 00:32:11,390
我们会做同样的事情
当我们用做“动物园”

593
00:32:11,390 --> 00:32:15,380
除了我们看到，当我们
尝试，并得到为h，它不存在。

594
00:32:15,380 --> 00:32:20,090
所以，你可以认为这是试图
以添加新节点插入到一个链表，

595
00:32:20,090 --> 00:32:27,210
所以我们需要添加另一个
其中的一个阵列，像这样。

596
00:32:27,210 --> 00:32:35,670
然后我们要做的是，我们刚刚成立的H
这个数组指向这个元素。

597
00:32:35,670 --> 00:32:39,430
>> 然后什么我们要在这里做？

598
00:32:39,430 --> 00:32:43,110
添加它等于true
因为它是一个字。

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
凉爽。

601
00:32:48,150 --> 00:32:48,700
我知道。

602
00:32:48,700 --> 00:32:51,170
尝试都不是最激动人心的。

603
00:32:51,170 --> 00:32:54,250
相信我，我知道。

604
00:32:54,250 --> 00:32:58,040
>> 这么一件事与尝试实现，
我说，他们是非常有效的。

605
00:32:58,040 --> 00:33:00,080
因此，我们已经看到了他们
占用大量的空间。

606
00:33:00,080 --> 00:33:01,370
种他们混淆。

607
00:33:01,370 --> 00:33:03,367
那么，为什么我们曾经使用过这些？

608
00:33:03,367 --> 00:33:05,450
我们使用这些，因为他们是
令人难以置信的高效。

609
00:33:05,450 --> 00:33:08,130
>> 因此，如果你曾经期待
一个字，你是唯一的

610
00:33:08,130 --> 00:33:10,450
由字的长度的限制。

611
00:33:10,450 --> 00:33:15,210
所以，如果你正在寻找一个
字是一个长度为5的，

612
00:33:15,210 --> 00:33:20,940
你永远只能将不得不
让最多5攀比，好不好？

613
00:33:20,940 --> 00:33:25,780
所以它使基本上是一个常数。

614
00:33:25,780 --> 00:33:29,150
就像插入和查询
基本上都是固定的时间。

615
00:33:29,150 --> 00:33:33,750
>> 所以，如果你能永远得到
东西在一定的时间，

616
00:33:33,750 --> 00:33:35,150
这是因为它得到不错的。

617
00:33:35,150 --> 00:33:37,990
你不能得到更好的比
固定时间为这些事情。

618
00:33:37,990 --> 00:33:43,150
以便为所述一个
尝试了巨大的加号。

619
00:33:43,150 --> 00:33:46,780
>> 但它是一个很大的空间。

620
00:33:46,780 --> 00:33:50,380
样的，所以你必须决定
什么对你更重要。

621
00:33:50,380 --> 00:33:54,700
而在今天的电脑，
空间的一个尝试可能最多

622
00:33:54,700 --> 00:33:57,740
也许不影响
你那么多，但也许

623
00:33:57,740 --> 00:34:01,350
你在处理事情
有远远更多的东西，

624
00:34:01,350 --> 00:34:02,810
并尝试恰恰是不合理的。

625
00:34:02,810 --> 00:34:03,000
是吗？

626
00:34:03,000 --> 00:34:05,610
>> 听众：等等，让你有26
在每一个人信吗？

627
00:34:05,610 --> 00:34:07,440
>> 扬声器1：Mmhmm​​。

628
00:34:07,440 --> 00:34:08,570
是啊，你有26。

629
00:34:08,570 --> 00:34:16,984
你有一些是字标记，然后
你有26球在每个人。

630
00:34:16,984 --> 00:34:17,775
他们正在point--

631
00:34:17,775 --> 00:34:20,280
>> 听众：和每一个26，
难道他们各有26？

632
00:34:20,280 --> 00:34:21,500
>> 扬声器1：是的。

633
00:34:21,500 --> 00:34:27,460
这就是为什么，因为你可以
看，它扩展相当迅速。

634
00:34:27,460 --> 00:34:28,130
行。

635
00:34:28,130 --> 00:34:32,524
所以，我们要进入树，
我觉得喜欢的是更简单，大概会

636
00:34:32,524 --> 00:34:36,150
是一个可爱的小死缓
从那里尝试。

637
00:34:36,150 --> 00:34:39,620
所以希望你们中的大多数
以前看过一棵树。

638
00:34:39,620 --> 00:34:41,820
不喜欢漂亮
外面的人，这是我

639
00:34:41,820 --> 00:34:44,340
不知道是否有人
去户外最近。

640
00:34:44,340 --> 00:34:49,230
我去采摘苹果本周末，
哦，我的天哪，这是美丽的。

641
00:34:49,230 --> 00:34:52,250
我不知道叶子
可以看看那个漂亮。

642
00:34:52,250 --> 00:34:53,610
>> 所以这只是一棵树，对不对？

643
00:34:53,610 --> 00:34:56,790
这只是一些节点，并且它
指着一堆其他节点。

644
00:34:56,790 --> 00:34:59,570
正如你在这里看到，这是
样一个反复出现的主题。

645
00:34:59,570 --> 00:35:03,720
节点指向的节点是怎么样的
许多数据结构的本质。

646
00:35:03,720 --> 00:35:06,670
这只是取决于我们如何
让他们指向对方

647
00:35:06,670 --> 00:35:08,600
以及我们如何遍历
通过他们，我们如何

648
00:35:08,600 --> 00:35:14,500
插入的东西，它决定
各自不同的特性。

649
00:35:14,500 --> 00:35:17,600
>> 所以只是一些术语，
我以前使用过。

650
00:35:17,600 --> 00:35:20,010
所以，根本是不管是在最高层。

651
00:35:20,010 --> 00:35:21,200
这就是我们总是开始。

652
00:35:21,200 --> 00:35:23,610
你可以把它作为负责人也。

653
00:35:23,610 --> 00:35:28,750
但对于树木，我们往往
称其为根部。

654
00:35:28,750 --> 00:35:32,820
>> 凡是在底部这里 - 
在非常，非常bottom--

655
00:35:32,820 --> 00:35:34,500
都认为叶。

656
00:35:34,500 --> 00:35:37,210
因此，随之而来的
整棵树的事，对不对？

657
00:35:37,210 --> 00:35:39,860
叶子是在你的树的边缘。

658
00:35:39,860 --> 00:35:45,820
>> 然后我们也有几个
术语谈论有关节点

659
00:35:45,820 --> 00:35:46,680
给对方。

660
00:35:46,680 --> 00:35:49,700
因此，我们有父母，
孩子和兄弟姐妹。

661
00:35:49,700 --> 00:35:56,260
所以在这种情况下，图3是
父的5，6和7。

662
00:35:56,260 --> 00:36:00,370
因此，家长无论是
一步以上不管你是

663
00:36:00,370 --> 00:36:02,940
参照，所以才
就像一个家庭树。

664
00:36:02,940 --> 00:36:07,090
但愿，这是所有有点
位比尝试更直观。

665
00:36:07,090 --> 00:36:10,970
>> 兄弟姐妹是任何有
同样的父母，对不对？

666
00:36:10,970 --> 00:36:13,470
他们在这里的同一水平。

667
00:36:13,470 --> 00:36:16,960
然后，因为我是
他说，孩子们刚

668
00:36:16,960 --> 00:36:22,630
无论是低于一步
有问题的节点，好不好？

669
00:36:22,630 --> 00:36:23,470
凉爽。

670
00:36:23,470 --> 00:36:25,610
这样的二进制树。

671
00:36:25,610 --> 00:36:31,450
任何人都可以猜测的一
二叉树的特点是什么？

672
00:36:31,450 --> 00:36:32,770
>> 听众：最多两片叶子。

673
00:36:32,770 --> 00:36:33,478
>> 扬声器1：没错。

674
00:36:33,478 --> 00:36:34,640
所以，最大的两片叶子。

675
00:36:34,640 --> 00:36:39,730
因此，在这个人之前，我们有这个
这有三个，但在一个二叉树，

676
00:36:39,730 --> 00:36:45,000
你有最多两个
每个父母的孩子，对不对？

677
00:36:45,000 --> 00:36:46,970
还有一个
有趣的特性。

678
00:36:46,970 --> 00:36:51,550
有谁知道？

679
00:36:51,550 --> 00:36:52,620
二叉树。

680
00:36:52,620 --> 00:37:00,350
>> 所以二叉树将拥有一切
在the--这个人是不是sorted--

681
00:37:00,350 --> 00:37:05,320
但在一个排序二叉树，
一切都在正确的

682
00:37:05,320 --> 00:37:08,530
大于父
一切都在左边

683
00:37:08,530 --> 00:37:10,035
小于母体。

684
00:37:10,035 --> 00:37:15,690
并且已经交了白卷
问题之前，那么好就知道了。

685
00:37:15,690 --> 00:37:19,500
因此，我们定义这个方式，
再次，我们有另一个节点。

686
00:37:19,500 --> 00:37:21,880
这看起来非常相似呢？

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
双

689
00:37:28,836 --> 00:37:29,320
>> 听众：链表

690
00:37:29,320 --> 00:37:31,100
>> 扬声器1：双链表，对不对？

691
00:37:31,100 --> 00:37:33,690
因此，如果我们替换此
有一个和下一个，

692
00:37:33,690 --> 00:37:35,670
这将是一个双向链表。

693
00:37:35,670 --> 00:37:40,125
但是，在这种情况下，我们实际上
有左，右，仅此而已。

694
00:37:40,125 --> 00:37:41,500
否则，它是完全相同的。

695
00:37:41,500 --> 00:37:43,374
我们还有元素
你要找的，

696
00:37:43,374 --> 00:37:45,988
而你只需要两个指针
要去什么是下一个。

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
是啊，所以二叉搜索树。

699
00:37:51,870 --> 00:37:57,665
如果我们发现，一切都在
这里是更大than--

700
00:37:57,665 --> 00:37:59,850
或立即的一切
这里的权利

701
00:37:59,850 --> 00:38:02,840
是大于一切
这里是小于。

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> 所以，如果我们通过搜索，它
看起来应该非常接近二分查找

704
00:38:14,000 --> 00:38:14,910
在这里，对不对？

705
00:38:14,910 --> 00:38:17,640
除外，而不是找
在一半的阵列，

706
00:38:17,640 --> 00:38:21,720
我们只是在寻找在任左
侧或右侧的树。

707
00:38:21,720 --> 00:38:24,850
所以就有点简单，我想。

708
00:38:24,850 --> 00:38:29,300
>> 所以，如果你的根是空的，
显然这只是假的。

709
00:38:29,300 --> 00:38:33,470
而如果它的存在，很明显这是真的。

710
00:38:33,470 --> 00:38:35,320
如果是小于，我们寻找的左侧。

711
00:38:35,320 --> 00:38:37,070
如果是大于，
我们搜查的权利。

712
00:38:37,070 --> 00:38:39,890
它是完全一样的二进制搜索，
只是一个不同的数据结构

713
00:38:39,890 --> 00:38:40,600
我们使用。

714
00:38:40,600 --> 00:38:42,790
代替数组，
它只是一个二叉树。

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK，栈。

717
00:38:48,090 --> 00:38:51,550
而且，看起来我们
可能有一点点时间。

718
00:38:51,550 --> 00:38:54,460
如果我们这样做，我很高兴去
在任何这一次。

719
00:38:54,460 --> 00:38:56,856
OK，所以栈。

720
00:38:56,856 --> 00:39:02,695
有谁还记得stacks--
一摞任何特点？

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> 好了，我们大多数人，我想，
在餐厅吃饭halls--

723
00:39:10,400 --> 00:39:13,100
就像我们可能不喜欢。

724
00:39:13,100 --> 00:39:16,900
但很明显，你可以把一叠
从字面上就如同一摞托盘

725
00:39:16,900 --> 00:39:18,460
或堆叠的事情。

726
00:39:18,460 --> 00:39:21,820
和什么是重要的
要知道的是，它的

727
00:39:21,820 --> 00:39:26,850
something--特征
我们把它叫做by--是后进先出法。

728
00:39:26,850 --> 00:39:28,450
有谁知道这代表着什么？

729
00:39:28,450 --> 00:39:29,070
Mmhmm​​？

730
00:39:29,070 --> 00:39:30,650
>> 听众：后进先出。

731
00:39:30,650 --> 00:39:32,250
>> 扬声器1：没错，后进先出。

732
00:39:32,250 --> 00:39:36,585
所以，如果我们知道，如果我们的东西堆放
起来，最简单的事情抢off--

733
00:39:36,585 --> 00:39:39,570
也许我们唯一可以抢
关闭如果我们的协议栈是大enough--

734
00:39:39,570 --> 00:39:40,850
是顶级元素。

735
00:39:40,850 --> 00:39:43,460
所以，无论是放在
last--我们在这里看到，

736
00:39:43,460 --> 00:39:46,370
不管是推
在大多数recently--是

737
00:39:46,370 --> 00:39:51,160
将成为第一
我们流行过，东西好不好？

738
00:39:51,160 --> 00:39:56,324
>> 所以，我们在这里是
另一个typedef结构。

739
00:39:56,324 --> 00:39:58,740
这真的只是喜欢
在数据结构速成班，

740
00:39:58,740 --> 00:40:01,650
所以有很多扔向你们。

741
00:40:01,650 --> 00:40:02,540
我知道。

742
00:40:02,540 --> 00:40:04,970
因此，另一种结构。

743
00:40:04,970 --> 00:40:06,740
耶的结构。

744
00:40:06,740 --> 00:40:16,660
>> 在这种情况下，它的一些指针
到具有一定容量的阵列。

745
00:40:16,660 --> 00:40:20,830
因此，这代表了我们的协议栈
在这里，像我们实际的数组

746
00:40:20,830 --> 00:40:22,520
这是我们持有的元素。

747
00:40:22,520 --> 00:40:24,850
然后在这里我们有一些大小。

748
00:40:24,850 --> 00:40:31,170
>> 而通常情况下，你要保持
曲目有多大的堆栈

749
00:40:31,170 --> 00:40:36,180
因为它是怎么回事，让
你要做的就是，如果你知道的大小，

750
00:40:36,180 --> 00:40:39,170
它可以让你说的，
好吧，我是在能力？

751
00:40:39,170 --> 00:40:40,570
我可以添加些什么？

752
00:40:40,570 --> 00:40:44,650
它也告诉你
在您的堆栈的顶部

753
00:40:44,650 --> 00:40:48,180
那么你知道你
其实可以起飞。

754
00:40:48,180 --> 00:40:51,760
而这实际上是要
有一点更清楚这里。

755
00:40:51,760 --> 00:40:57,350
>> 因此，对于推，一件事，如果你
是有史以来实施推，

756
00:40:57,350 --> 00:41:01,330
我只是说，你的
栈的大小有限，对不对？

757
00:41:01,330 --> 00:41:03,990
我们的阵列有一些能力。

758
00:41:03,990 --> 00:41:04,910
这是一个数组。

759
00:41:04,910 --> 00:41:08,930
这是一个固定大小的，所以我们需要
确保我们不会把更多

760
00:41:08,930 --> 00:41:11,950
到我们的数组要比我们
实际上有空间。

761
00:41:11,950 --> 00:41:16,900
>> 所以，当你创建一个推
功能，你做的是说好第一句话，

762
00:41:16,900 --> 00:41:18,570
做我的空间我的筹码？

763
00:41:18,570 --> 00:41:23,330
因为如果我不这样做，对不起，
我不能存储你的元素。

764
00:41:23,330 --> 00:41:28,980
如果我这样做，那么你想存储
它在堆栈的顶部，对不对？

765
00:41:28,980 --> 00:41:31,325
>> 这就是为什么我们有
跟踪我们的规模。

766
00:41:31,325 --> 00:41:35,290
如果我们不保持我们这样规模的轨道，
我们不知道放在哪里。

767
00:41:35,290 --> 00:41:39,035
我们不知道有多少东西
在我们的数组了。

768
00:41:39,035 --> 00:41:41,410
就像明明有方法
也许你可以做到这一点。

769
00:41:41,410 --> 00:41:44,610
你可以初始化所有设置为NULL
然后检查最新NULL，

770
00:41:44,610 --> 00:41:47,950
但一个更容易的事情仅仅是
说，OK，跟踪大小。

771
00:41:47,950 --> 00:41:51,840
就像我知道我有四个要素
在我的数组，所以接下来的事情

772
00:41:51,840 --> 00:41:55,930
我们换上，我们
将存储在索引4。

773
00:41:55,930 --> 00:42:00,940
然后，当然，这意味着
你已经成功地推的东西

774
00:42:00,940 --> 00:42:03,320
到你的筹码，你
要增加大小

775
00:42:03,320 --> 00:42:08,880
让你知道你是如此
那你可以把更多的东西。

776
00:42:08,880 --> 00:42:12,730
>> 所以，如果我们试图弹出
事关栈，

777
00:42:12,730 --> 00:42:16,072
可能是什么的第一件事
我们要检查？

778
00:42:16,072 --> 00:42:18,030
你想采取
事关你的筹码。

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
你肯定有
在堆栈中的东西吗？

781
00:42:24,781 --> 00:42:25,280
号

782
00:42:25,280 --> 00:42:26,894
所以，什么才是我们要检查？

783
00:42:26,894 --> 00:42:27,810
>> 听众：[听不清]。

784
00:42:27,810 --> 00:42:29,880
扬声器1：检查的大小？

785
00:42:29,880 --> 00:42:31,840
尺寸。

786
00:42:31,840 --> 00:42:38,520
因此，我们要检查，如果看
我们的规模是大于0，OK？

787
00:42:38,520 --> 00:42:44,970
如果是，那么我们需要减小
我们的规模由0和返回。

788
00:42:44,970 --> 00:42:45,840
为什么呢？

789
00:42:45,840 --> 00:42:49,950
>> 在第一个我们
推，我们推

790
00:42:49,950 --> 00:42:52,460
上的尺寸，然后更新的大小。

791
00:42:52,460 --> 00:42:57,850
在这种情况下，我们正在递减大小
然后把它关闭，它拔毛

792
00:42:57,850 --> 00:42:58,952
从我们的数组。

793
00:42:58,952 --> 00:42:59,826
为什么会那样做？

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
所以，如果我有一件事对我的筹码，
这将是我的尺寸在这一点？

796
00:43:11,811 --> 00:43:13,140
1。

797
00:43:13,140 --> 00:43:15,180
>> 何为元素1储存在哪里？

798
00:43:15,180 --> 00:43:17,621
什么指标？

799
00:43:17,621 --> 00:43:18,120
听众：0。

800
00:43:18,120 --> 00:43:19,060
扬声器1：0。

801
00:43:19,060 --> 00:43:22,800
所以在这种情况下，我们
总是需要使sure--

802
00:43:22,800 --> 00:43:27,630
而不是返回
大小减去1，因为我们

803
00:43:27,630 --> 00:43:31,730
知道我们的元素是
将要被存储在1以下

804
00:43:31,730 --> 00:43:34,705
无论我们的规模是，这
只需要照顾它。

805
00:43:34,705 --> 00:43:36,080
这是一个稍微更优雅的方式。

806
00:43:36,080 --> 00:43:41,220
我们只是减小了
大小，然后返回大小。

807
00:43:41,220 --> 00:43:42,330
Mmhmm​​？

808
00:43:42,330 --> 00:43:45,300
>> 观众：我想刚才在一般情况下，
为什么会这个数据结构

809
00:43:45,300 --> 00:43:47,800
是有益的？

810
00:43:47,800 --> 00:43:50,660
>> 扬声器1：这取决于你的环境。

811
00:43:50,660 --> 00:43:57,420
因此对于一些理论，
如果你的工作with-- OK，

812
00:43:57,420 --> 00:44:02,750
让我看看，如果有一个有利的1
那就是超过外面有利

813
00:44:02,750 --> 00:44:05,420
的CS。

814
00:44:05,420 --> 00:44:15,780
随着栈，任何时候你需要
跟踪事

815
00:44:15,780 --> 00:44:20,456
是最近添加的是当
你将要使用的堆栈。

816
00:44:20,456 --> 00:44:24,770
>> 我想不出一个好
举例说，现在。

817
00:44:24,770 --> 00:44:29,955
但每当最近
事情是对你最重要，

818
00:44:29,955 --> 00:44:31,705
这是一个堆栈时，
将是有用的。

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
我试图想，如果
有一个很好的这一点。

821
00:44:39,330 --> 00:44:43,720
如果我觉得一个很好的例子，在未来
20分钟后，我一定会告诉你的。

822
00:44:43,720 --> 00:44:49,455
>> 但总体而言，如果有什么事，
就像我说的最多的，其中，最近

823
00:44:49,455 --> 00:44:52,470
最重要的是，这是
其中，一摞用武之地。

824
00:44:52,470 --> 00:44:58,860
而队列是一种相反的。

825
00:44:58,860 --> 00:44:59,870
和所有的小狗狗。

826
00:44:59,870 --> 00:45:00,890
这不是很大的，对不对？

827
00:45:00,890 --> 00:45:03,299
我觉得我应该
只是有一个小兔子的视频

828
00:45:03,299 --> 00:45:05,090
右中的中间
节为你们

829
00:45:05,090 --> 00:45:08,870
因为这是一个强烈的部分。

830
00:45:08,870 --> 00:45:10,480
>> 这样一个队列。

831
00:45:10,480 --> 00:45:12,710
基本上一个队列是像一条线。

832
00:45:12,710 --> 00:45:15,780
你们我敢肯定，使用这种日常生活，
就像在我们的食堂。

833
00:45:15,780 --> 00:45:18,160
因此，我们必须去
并得到我们的托盘，我

834
00:45:18,160 --> 00:45:21,260
确保你有排队等候
刷卡或让你的食物。

835
00:45:21,260 --> 00:45:24,650
>> 因此，区别就在这里
是，这是FIFO中。

836
00:45:24,650 --> 00:45:30,090
所以，如果是后进先出后进，先
出，先进先出是先入先出。

837
00:45:30,090 --> 00:45:33,400
因此，这是不管你把
第一次是你最重要的。

838
00:45:33,400 --> 00:45:35,540
所以，如果你在等待
在line--可以吗

839
00:45:35,540 --> 00:45:39,130
想象一下，如果你去了
去获得新的iPhone

840
00:45:39,130 --> 00:45:42,800
并且它是一个堆栈，其中
最后一个人符合了它​​的第一，

841
00:45:42,800 --> 00:45:44,160
人们会互相残杀。

842
00:45:44,160 --> 00:45:49,800
>> 所以FIFO，我们都很熟悉
在这里，在现实世界中，

843
00:45:49,800 --> 00:45:54,930
而这一切，是因为有实际
种重现这一整条生产线

844
00:45:54,930 --> 00:45:56,900
和排队结构。

845
00:45:56,900 --> 00:46:02,390
如此而用栈，
我们有push和pop。

846
00:46:02,390 --> 00:46:06,440
同一个队列，我们​​有
入队和出队。

847
00:46:06,440 --> 00:46:10,910
所以排队的基本含义
把它放到后面，

848
00:46:10,910 --> 00:46:13,680
和出队采取的手段
断从前面。

849
00:46:13,680 --> 00:46:18,680
因此，我们的数据结构是一
稍微有点复杂。

850
00:46:18,680 --> 00:46:21,060
我们有第二个事情防不胜防。

851
00:46:21,060 --> 00:46:25,950
>> 因此，没有了头，这
正是堆栈，对不对？

852
00:46:25,950 --> 00:46:27,900
这是相同的结构的堆叠。

853
00:46:27,900 --> 00:46:32,480
唯一不同的是，现在我们
有这个头，这你怎么看

854
00:46:32,480 --> 00:46:34,272
是要跟踪的？

855
00:46:34,272 --> 00:46:35,510
>> 听众：第一个。

856
00:46:35,510 --> 00:46:38,685
>> 扬声器1：对，
我们把第一件事。

857
00:46:38,685 --> 00:46:41,130
我们的队列的头。

858
00:46:41,130 --> 00:46:42,240
谁是排在第一位。

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
好吧，如果我们做排队。

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
再次，与任何
这些数据结构

863
00:46:55,920 --> 00:46:59,760
因为我们处理的是一个数组，
我们需要检查一下，如果我们有空间。

864
00:46:59,760 --> 00:47:03,290
>> 这有点像我说
你们这些家伙，如果你打开​​一个文件，

865
00:47:03,290 --> 00:47:04,760
你需要检查空。

866
00:47:04,760 --> 00:47:08,330
与任何这些堆栈
和队列，你需要

867
00:47:08,330 --> 00:47:13,420
看看是否有空间，因为我们
处理一个固定尺寸数组，

868
00:47:13,420 --> 00:47:16,030
我们看到这里 -  0，1都达5。

869
00:47:16,030 --> 00:47:20,690
那么，我们在这种情况下是检查
看看我们仍然有空间。

870
00:47:20,690 --> 00:47:23,110
是我们的规模小于容量是多少？

871
00:47:23,110 --> 00:47:28,480
>> 如果是这样，我们需要将其存储在
尾部，我们更新我们的规模。

872
00:47:28,480 --> 00:47:30,250
那么，什么可能的尾巴在这种情况下？

873
00:47:30,250 --> 00:47:32,360
它没有明确地写出来。

874
00:47:32,360 --> 00:47:33,380
我们将如何保存呢？

875
00:47:33,380 --> 00:47:34,928
什么尾巴呢？

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> 因此，让我们步行穿过这个例子。

878
00:47:40,190 --> 00:47:44,590
因此，这是一个大小为6的数组，对不对？

879
00:47:44,590 --> 00:47:49,220
而我们现在所拥有的，我们的规模是5。

880
00:47:49,220 --> 00:47:55,240
而当我们把它放在，这是怎么回事
进入第五个指标，对不对？

881
00:47:55,240 --> 00:47:57,030
因此，存储在尾部。

882
00:47:57,030 --> 00:48:05,600
>> 另一种方式来写尾部也只是
是我们的数组大小的指标，对不对？

883
00:48:05,600 --> 00:48:07,560
这是5号。

884
00:48:07,560 --> 00:48:11,490
接下来的事情将要进入5。

885
00:48:11,490 --> 00:48:12,296
很酷吧？

886
00:48:12,296 --> 00:48:13,290
行。

887
00:48:13,290 --> 00:48:16,350
它变得稍微复杂
当我们开始用头搞乱。

888
00:48:16,350 --> 00:48:17,060
是吗？

889
00:48:17,060 --> 00:48:20,090
>> 听众：这是否意味着我们
会宣布一个数组，

890
00:48:20,090 --> 00:48:23,880
是五行长
那么，我们要添加到它？

891
00:48:23,880 --> 00:48:24,730
>> 扬声器1：第

892
00:48:24,730 --> 00:48:27,560
所以在这种情况下，这是一个堆栈。

893
00:48:27,560 --> 00:48:31,760
这将宣布
作为规模6的数组。

894
00:48:31,760 --> 00:48:37,120
在这种情况下，我们
只有一个剩余空间。

895
00:48:37,120 --> 00:48:42,720
>> 好了，有一件事是在这
情况下，如果我们的头是0，

896
00:48:42,720 --> 00:48:45,270
那么我们就可以在大小添加。

897
00:48:45,270 --> 00:48:51,020
但它变得有点棘手
因为实际上，他们

898
00:48:51,020 --> 00:48:52,840
不具备滑动
对于这一点，所以我要去

899
00:48:52,840 --> 00:48:56,670
画之一，因为它不是
曾经想象中的那么简单，你

900
00:48:56,670 --> 00:48:59,230
开始摆脱的东西。

901
00:48:59,230 --> 00:49:03,920
因此，而用栈
你永远只能有

902
00:49:03,920 --> 00:49:08,920
担心大小是什么
当你添加的东西上，

903
00:49:08,920 --> 00:49:15,710
一个队列，你还需要
确保你的头被占，

904
00:49:15,710 --> 00:49:20,760
由于对队列一件很酷的事情
是，如果你没有能力，

905
00:49:20,760 --> 00:49:23,040
你其实可以把它环绕。

906
00:49:23,040 --> 00:49:28,810
>> OK，所以一件事 - 哦，
这是可怕的粉笔。

907
00:49:28,810 --> 00:49:31,815
有一点要考虑的是这种情况。

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
我们就做五。

910
00:49:37,140 --> 00:49:41,810
好了，我们要
说的头就在这里。

911
00:49:41,810 --> 00:49:46,140
这是0，1，2，3，4。

912
00:49:46,140 --> 00:49:54,210
>> 头的存在，并
请有东西在其中。

913
00:49:54,210 --> 00:49:58,340
我们要添加的东西，对吧？

914
00:49:58,340 --> 00:50:01,170
于是事情，我们需要
知道的是，头总是

915
00:50:01,170 --> 00:50:05,620
要移动这样的，
然后循环回到我的身边，好不好？

916
00:50:05,620 --> 00:50:10,190
>> 所以这个队列有空间的，对不对？

917
00:50:10,190 --> 00:50:13,950
它有空间，在一开始，
那种此相反的。

918
00:50:13,950 --> 00:50:17,920
因此，我们需要做的是我们
需要计算的尾巴。

919
00:50:17,920 --> 00:50:20,530
如果你知道你的
头没有移动，尾巴

920
00:50:20,530 --> 00:50:24,630
只是你的数组
大小的指标。

921
00:50:24,630 --> 00:50:30,000
>> 但在现实中，如果你使用一个队列，
你的脑袋可能是被更新。

922
00:50:30,000 --> 00:50:33,890
所以，你需要做的是
实际计算的尾巴。

923
00:50:33,890 --> 00:50:39,990
所以，我们做的是这个公式
在这里，我打算让你

924
00:50:39,990 --> 00:50:42,680
你们想想，和
然后我们会谈论它。

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
因此，这是能力。

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> 所以这实际上
给你一个办法做到这一点。

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
因为在这种情况下，是什么？

931
00:51:04,330 --> 00:51:09,205
我们的头是1，我们的规模是4。

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
如果我们这国防部5，我们得到0，
这是我们应该输入它。

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> 如此则在下一情况下，
如果要做到这一点，

936
00:51:26,080 --> 00:51:33,390
我们说，好吧，让我们出列的东西。

937
00:51:33,390 --> 00:51:34,390
我们出列了。

938
00:51:34,390 --> 00:51:37,740
我们拿出这个元素，对不对？

939
00:51:37,740 --> 00:51:47,930
>> 现在我们的头指指点点，
我们要在另一件事情补充。

940
00:51:47,930 --> 00:51:52,470
这基本上是
回到我们这行的，对不对？

941
00:51:52,470 --> 00:51:55,450
队列可以在阵列周围包裹。

942
00:51:55,450 --> 00:51:57,310
这是主要区别之一。

943
00:51:57,310 --> 00:51:58,780
堆栈，你不能做到这一点。

944
00:51:58,780 --> 00:52:01,140
>> 随着队列，您可以
因为所有的事项

945
00:52:01,140 --> 00:52:03,940
是，你知道什么
最近被添加。

946
00:52:03,940 --> 00:52:10,650
因为一切都在以复加
此向左方向，在这种情况下，

947
00:52:10,650 --> 00:52:16,480
然后环绕，你可以
继续投入新元素

948
00:52:16,480 --> 00:52:18,830
在阵列的前
因为它不是真的

949
00:52:18,830 --> 00:52:20,640
阵列的前面了。

950
00:52:20,640 --> 00:52:26,320
你能想到的初
数组的地方你的头居然是。

951
00:52:26,320 --> 00:52:29,710
>> 所以这个公式是怎么
你计算你的尾巴。

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
这是否有道理？

954
00:52:35,610 --> 00:52:36,110
行。

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK，出列，然后
你们有10分钟

957
00:52:44,040 --> 00:52:48,840
要问我任何澄清的问题
你想要的，因为我知道这很疯狂。

958
00:52:48,840 --> 00:52:51,980
>> 好吧，所以在相同的方式 - 
我不知道你们注意到了，

959
00:52:51,980 --> 00:52:53,450
但CS是所有关于模式。

960
00:52:53,450 --> 00:52:57,370
东西是相当多的
同样的，只需用很小的调整。

961
00:52:57,370 --> 00:52:58,950
这里这么一回事。

962
00:52:58,950 --> 00:53:04,040
我们需要检查一下，看看我们是否真正
有东西在我们的队列，对不对？

963
00:53:04,040 --> 00:53:05,960
说好，是我们的规模大于0？

964
00:53:05,960 --> 00:53:06,730
凉爽。

965
00:53:06,730 --> 00:53:10,690
>> 如果我们这样做，那么我们把我们的头，这
就是我刚才在这里展示。

966
00:53:10,690 --> 00:53:13,870
我们更新我们的头要多一个。

967
00:53:13,870 --> 00:53:18,390
然后我们减了
尺寸，并返回该元素。

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> 有更具体
在study.cs50.net代码，

970
00:53:26,250 --> 00:53:29,440
我强烈建议你
通过它，如果你有时间，

971
00:53:29,440 --> 00:53:30,980
即使它只是一个伪代码。

972
00:53:30,980 --> 00:53:35,980
如果你们想通过谈话
与我一对一，请让我

973
00:53:35,980 --> 00:53:37,500
知道了。

974
00:53:37,500 --> 00:53:38,770
我很乐意。

975
00:53:38,770 --> 00:53:42,720
数据结构中，如果
你把CS 124，你会

976
00:53:42,720 --> 00:53:47,830
知道数据结构变得非常
乐趣，这是刚刚开始。

977
00:53:47,830 --> 00:53:50,350
>> 所以，我知道这很难。

978
00:53:50,350 --> 00:53:51,300
没关系。

979
00:53:51,300 --> 00:53:52,410
我们奋斗。

980
00:53:52,410 --> 00:53:53,630
我还是做了。

981
00:53:53,630 --> 00:53:56,660
所以不要太担心了。

982
00:53:56,660 --> 00:54:02,390
>> 但是，这基本上是你
在数据结构速成班。

983
00:54:02,390 --> 00:54:03,400
我知道这是一个很大。

984
00:54:03,400 --> 00:54:06,860
还有什么是我们
想去一遍？

985
00:54:06,860 --> 00:54:09,400
任何我们想通过谈话？

986
00:54:09,400 --> 00:54:10,060
是吗？

987
00:54:10,060 --> 00:54:16,525
>> 顾客：这个例子，所以
新尾为0了吗？

988
00:54:16,525 --> 00:54:17,150
扬声器1：是的。

989
00:54:17,150 --> 00:54:18,230
听众：OK。

990
00:54:18,230 --> 00:54:24,220
所以后来经历，
你有1加4 or--

991
00:54:24,220 --> 00:54:27,671
>> 扬声器1：所以你是说，
当我们想要去做到这一点了吗？

992
00:54:27,671 --> 00:54:28,296
听众：是的。

993
00:54:28,296 --> 00:54:38,290
所以，如果你搞清楚out--在哪里
你计算从该尾？

994
00:54:38,290 --> 00:54:44,260
>> 扬声器1：所以尾巴
是in--我改变了这一点。

995
00:54:44,260 --> 00:54:52,010
所以在这里本实施例中，这是
我们正在寻找，确定的数组？

996
00:54:52,010 --> 00:54:54,670
因此，我们必须在1，2，3和4的东西。

997
00:54:54,670 --> 00:55:05,850
因此，我们有我们的头是等于1
这一点，我们的大小等于4

998
00:55:05,850 --> 00:55:07,050
在这一点上，对不对？

999
00:55:07,050 --> 00:55:08,960
>> 大家都同意的话？

1000
00:55:08,960 --> 00:55:14,620
所以我们做头部加上大小，这
给我们5，然后我们用5国防部。

1001
00:55:14,620 --> 00:55:20,690
我们得到0，这告诉我们，0
哪里是我们的尾巴，在那里我们有空间。

1002
00:55:20,690 --> 00:55:22,010
>> 听众：什么是上限？

1003
00:55:22,010 --> 00:55:23,520
>> 扬声器1：容量。

1004
00:55:23,520 --> 00:55:24,020
抱歉。

1005
00:55:24,020 --> 00:55:29,640
所以这是你的数组的大小。

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
是吗？

1008
00:55:36,047 --> 00:55:39,210
>> 听众：[听不清]前
我们返回的元素？

1009
00:55:39,210 --> 00:55:46,270
>> 扬声器1：因此，我们将
前往或返回的那一刻？

1010
00:55:46,270 --> 00:55:52,680
因此，如果我们移动一个，减小尺寸是多少？

1011
00:55:52,680 --> 00:55:54,150
坚持，稍等。

1012
00:55:54,150 --> 00:55:55,770
我肯定忘了另外一个。

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
没关系。

1015
00:56:01,990 --> 00:56:04,980
没有另一个公式。

1016
00:56:04,980 --> 00:56:09,980
是的，你会想返回
头，然后将其移回。

1017
00:56:09,980 --> 00:56:13,270
>> 听众：OK，因为在这
点，头是0，

1018
00:56:13,270 --> 00:56:18,452
然后，你要回
指数0，然后使头1？

1019
00:56:18,452 --> 00:56:19,870
>> 扬声器1：没错。

1020
00:56:19,870 --> 00:56:22,820
我认为还有另一种
公式有点像这样。

1021
00:56:22,820 --> 00:56:26,970
我没有在这上面我的头
我不想给你错了。

1022
00:56:26,970 --> 00:56:35,470
但我认为这是完全有效的
比方说，OK，保存该element--什么

1023
00:56:35,470 --> 00:56:40,759
头部的元素is--递减的
大小，移动你的头了，而归

1024
00:56:40,759 --> 00:56:41,800
无论这个元素。

1025
00:56:41,800 --> 00:56:44,760
这是完全有效的。

1026
00:56:44,760 --> 00:56:45,260
行。

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
我觉得这不是
像most--你不

1029
00:56:53,560 --> 00:56:55,740
要走出这里
喜欢，是的，我知道尝试。

1030
00:56:55,740 --> 00:56:56,880
我得到了这一切。

1031
00:56:56,880 --> 00:56:57,670
没关系。

1032
00:56:57,670 --> 00:57:00,200
我保证。

1033
00:57:00,200 --> 00:57:05,240
但是数据结构的东西，
它需要大量的时间来用于获得。

1034
00:57:05,240 --> 00:57:10,010
最难的可能是1
的东西，我认为，在使用过程中。

1035
00:57:10,010 --> 00:57:15,330
>> 因此，它肯定需要
重复和期待at--我

1036
00:57:15,330 --> 00:57:20,050
真的不知道链表
直到我做了太多与他们，

1037
00:57:20,050 --> 00:57:22,550
在同样的方式，我没有
真正了解指针

1038
00:57:22,550 --> 00:57:27,040
直到我已经教了两个
多年来，做自己的pset它。

1039
00:57:27,040 --> 00:57:28,990
这需要大量的重申和时间。

1040
00:57:28,990 --> 00:57:32,600
最终，它会有种点击。

1041
00:57:32,600 --> 00:57:36,320
>> 但在此期间，如果你有实物
的高水平的理解什么

1042
00:57:36,320 --> 00:57:39,321
这些干什么，他们的优点
和cons--这就是

1043
00:57:39,321 --> 00:57:41,820
我们真的倾向于强调，
特别是在介绍过程。

1044
00:57:41,820 --> 00:57:45,511
喜欢，为什么我们使用
试试在一个数组？

1045
00:57:45,511 --> 00:57:48,010
喜欢，什么是阳性
并且其中的每个的底片？

1046
00:57:48,010 --> 00:57:51,610
>> 和理解的取舍
每个这些结构之间

1047
00:57:51,610 --> 00:57:54,910
是什么是更重要的现在。

1048
00:57:54,910 --> 00:57:58,140
可以有一个疯
两个问题那

1049
00:57:58,140 --> 00:58:03,710
要问你实现或推
实施POP或入队和出队。

1050
00:58:03,710 --> 00:58:07,340
但在大多数情况下，具有
更高层次的认识和更

1051
00:58:07,340 --> 00:58:09,710
一个直观的把握是
比实际更重要

1052
00:58:09,710 --> 00:58:11,250
能够实现它。

1053
00:58:11,250 --> 00:58:14,880
>> 这会是真的真棒，如果在座的各位
能够走出去，去实现一个尝试，

1054
00:58:14,880 --> 00:58:19,720
但我们知道它并不一定
最合理的事情，现在。

1055
00:58:19,720 --> 00:58:23,370
但是你可以在你的pset，如果你想
到，然后你会得到实践，

1056
00:58:23,370 --> 00:58:27,200
然后也许你会
真正了解它。

1057
00:58:27,200 --> 00:58:27,940
是吗？

1058
00:58:27,940 --> 00:58:30,440
>> 听众：好，那么哪些是
我们的意思，在pset中使用？

1059
00:58:30,440 --> 00:58:31,916
我是否需要使用其中的一个？

1060
00:58:31,916 --> 00:58:32,540
扬声器1：是的。

1061
00:58:32,540 --> 00:58:34,199
所以，你有你的选择。

1062
00:58:34,199 --> 00:58:36,740
我在这种情况下猜测，我们可以
说说PSET一点点

1063
00:58:36,740 --> 00:58:40,480
因为我跑过这些。

1064
00:58:40,480 --> 00:58:47,779
因此，在你的pset，你有你的
选择尝试或哈希表。

1065
00:58:47,779 --> 00:58:49,570
有些人会尝试
并使用布隆过滤器，

1066
00:58:49,570 --> 00:58:51,840
但这些在技术上是不正确的。

1067
00:58:51,840 --> 00:58:55,804
因为他们的概率性质，
他们给假阳性的时候。

1068
00:58:55,804 --> 00:58:57,095
他们冷静地审视之中，虽然。

1069
00:58:57,095 --> 00:58:59,030
强烈推荐看
在他们最少。

1070
00:58:59,030 --> 00:59:03,260
但是，你有你的选择
一个哈希表，并一试的。

1071
00:59:03,260 --> 00:59:06,660
而这将是哪里
你在你的字典中加载。

1072
00:59:06,660 --> 00:59:09,230
>> 你需要选择
您的散列函数

1073
00:59:09,230 --> 00:59:13,420
你需要选择多少
铲斗有，它会有所不同。

1074
00:59:13,420 --> 00:59:17,440
就像如果你有更多的桶，
也许它会跑得更快。

1075
00:59:17,440 --> 00:59:22,790
但是，也许你就是在浪费一个
很多空间的方式，虽然。

1076
00:59:22,790 --> 00:59:26,320
你必须弄明白。

1077
00:59:26,320 --> 00:59:27,140
Mmhmm​​？

1078
00:59:27,140 --> 00:59:29,875
>> 听众：你之前说
我们可以用其它散列函数

1079
00:59:29,875 --> 00:59:31,750
我们不必
创建一个哈希函数？

1080
00:59:31,750 --> 00:59:32,666
>> 扬声器1：是的，没错。

1081
00:59:32,666 --> 00:59:38,150
因此，从字面上你的哈希函数，
像谷歌“散列函数”

1082
00:59:38,150 --> 00:59:40,770
并寻找一些很酷的人。

1083
00:59:40,770 --> 00:59:43,250
你是不是有望建成
你自己的哈希函数。

1084
00:59:43,250 --> 00:59:46,100
人一生
论文对这些东西。

1085
00:59:46,100 --> 00:59:50,250
>> 所以不用担心构建自己的。

1086
00:59:50,250 --> 00:59:53,350
找到一个网上开始。

1087
00:59:53,350 --> 00:59:56,120
他们中的一些，你必须
操纵一点点

1088
00:59:56,120 --> 00:59:59,430
以确保返回类型匹配
及诸如此类的东西，所以在开始时，

1089
00:59:59,430 --> 01:00:02,420
我会建议使用一些
真的很简单，也许只是

1090
01:00:02,420 --> 01:00:04,680
哈希的第一个字母。

1091
01:00:04,680 --> 01:00:08,760
然后，一旦你有工作，
结合有冷却器的散列函数。

1092
01:00:08,760 --> 01:00:09,260
Mmhmm​​？

1093
01:00:09,260 --> 01:00:13,020
>> 听众：请问一个尝试是或
高效而只是更难，like--

1094
01:00:13,020 --> 01:00:15,880
>> 扬声器1：那么一试，我想，
直觉是难以实现

1095
01:00:15,880 --> 01:00:18,310
但是非常快的。

1096
01:00:18,310 --> 01:00:20,620
但是，占用了更多的空间。

1097
01:00:20,620 --> 01:00:25,270
同样，你可以在优化这两个的
不同的方式和有办法to--

1098
01:00:25,270 --> 01:00:26,770
听众：我们怎样分级的呢？

1099
01:00:26,770 --> 01:00:27,540
它matter--

1100
01:00:27,540 --> 01:00:29,164
>> 扬声器1：所以你正常的分级方式。

1101
01:00:29,164 --> 01:00:31,330
你要对设计进行分级。

1102
01:00:31,330 --> 01:00:36,020
无论你的方式，你要
确保它的优雅，因为它可以

1103
01:00:36,020 --> 01:00:38,610
并作为有效的，因为它可以。

1104
01:00:38,610 --> 01:00:41,950
但是，如果你选择一个试或哈希
表的，只要它工作，

1105
01:00:41,950 --> 01:00:45,350
我们很高兴。

1106
01:00:45,350 --> 01:00:48,370
如果你使用的东西，哈希
第一个字母，这很好，

1107
01:00:48,370 --> 01:00:51,410
如可能喜欢的设计，明智的。

1108
01:00:51,410 --> 01:00:53,410
我们也到达
点这semester--

1109
01:00:53,410 --> 01:00:55,340
我不知道，如果你
球员noticed--如果你

1110
01:00:55,340 --> 01:00:58,780
PSET等级下降一点点
因为设计和诸如此类的东西的，

1111
01:00:58,780 --> 01:00:59,900
这是完全正常的。

1112
01:00:59,900 --> 01:01:02,960
它让到一个地步，你
程序正变得越来越复杂。

1113
01:01:02,960 --> 01:01:04,830
还有更多的地方
你可以改善。

1114
01:01:04,830 --> 01:01:06,370
>> 所以这是完全正常的。

1115
01:01:06,370 --> 01:01:08,810
这并不是说你
您PSET做差。

1116
01:01:08,810 --> 01:01:11,885
这只是我们是很难对你现在。

1117
01:01:11,885 --> 01:01:13,732
所以每个人的感觉吧。

1118
01:01:13,732 --> 01:01:14,940
我只是分级所有pset中。

1119
01:01:14,940 --> 01:01:16,490
我知道每个人都感觉到了。

1120
01:01:16,490 --> 01:01:19,600
>> 所以不用担心。

1121
01:01:19,600 --> 01:01:23,580
如果您有任何问题，
之前的pset或方法可以改善，

1122
01:01:23,580 --> 01:01:27,760
我尝试了具体的意见
的地方，但有时它的后期

1123
01:01:27,760 --> 01:01:30,840
我累了。

1124
01:01:30,840 --> 01:01:34,885
是否有任何其他的东西
关于数据结构？

1125
01:01:34,885 --> 01:01:37,510
我敢肯定，你们真的不
要谈他们了，

1126
01:01:37,510 --> 01:01:42,650
但如果有，我很高兴
走过去了，还有什么

1127
01:01:42,650 --> 01:01:45,580
讲座从过去
上周，上一周。

1128
01:01:45,580 --> 01:01:51,580
>> 我知道，上周所有检讨，
我们可能已经跳过了一些检讨

1129
01:01:51,580 --> 01:01:54,190
从讲座。

1130
01:01:54,190 --> 01:01:58,230
还有没有其他问题我可以回答？

1131
01:01:58,230 --> 01:01:59,350
好了，没事了。

1132
01:01:59,350 --> 01:02:02,400
好了，你们早出去15分钟。

1133
01:02:02,400 --> 01:02:08,370
>> 我希望这至少是半很有帮助，
我会看到你下周的家伙，

1134
01:02:08,370 --> 01:02:12,150
或周四的办公时间。

1135
01:02:12,150 --> 01:02:15,285
是否有小吃请求
下周，它的东西吗？

1136
01:02:15,285 --> 01:02:17,459
因为我忘了今天的糖果。

1137
01:02:17,459 --> 01:02:19,750
我带过去的糖果
上周，但它是哥伦布日，

1138
01:02:19,750 --> 01:02:25,400
所以就像六个人谁
有四袋糖果的自己。

1139
01:02:25,400 --> 01:02:28,820
我可以带星形图案
再次，如果你喜欢。

1140
01:02:28,820 --> 01:02:29,580
星形图案？

1141
01:02:29,580 --> 01:02:32,250
OK，听起来不错。

1142
01:02:32,250 --> 01:02:35,050
有一个伟大的日子，伙计们。

1143
01:02:35,050 --> 01:02:39,510