1
00:00:00,000 --> 00:00:03,423
>> [音乐播放]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI鹏：欢迎来到第6个星期

4
00:00:08,210 --> 00:00:11,620
我们从标准的偏离
周二部分时间

5
00:00:11,620 --> 00:00:14,130
下午这个可爱的星期天早晨。

6
00:00:14,130 --> 00:00:17,330
谢谢大家了
加入我的今天，但严重的是，

7
00:00:17,330 --> 00:00:18,170
掌声雷动。

8
00:00:18,170 --> 00:00:20,600
>> 这是一个相当大的努力。

9
00:00:20,600 --> 00:00:23,600
我几乎没有，甚至使它
在时间，但它是确定。

10
00:00:23,600 --> 00:00:27,520
所以，我知道所有的你，
刚刚去到测验。

11
00:00:27,520 --> 00:00:30,370
首先，欢迎
另一面的那个。

12
00:00:30,370 --> 00:00:32,917
>> 其次，我们会谈论它。

13
00:00:32,917 --> 00:00:34,000
我们将讨论的测验。

14
00:00:34,000 --> 00:00:35,700
我们将谈论如何
你正在做的类。

15
00:00:35,700 --> 00:00:36,550
你会没事的。

16
00:00:36,550 --> 00:00:39,080
我有你的测验为
你在这里结束，

17
00:00:39,080 --> 00:00:42,120
所以如果你们想带
看看吧，完全罚款。

18
00:00:42,120 --> 00:00:46,590
>> 所以很快我们开始的前
今天的议程如下。

19
00:00:46,590 --> 00:00:48,430
正如你所看到的，我们是
基本上速射

20
00:00:48,430 --> 00:00:52,120
通过一大堆数据结构
真的，真的，真的很快。

21
00:00:52,120 --> 00:00:54,380
如此，因此，它不会被
超级互动的今天。

22
00:00:54,380 --> 00:00:59,620
这将只是我的一种喊
事情是你，如果我迷惑你，

23
00:00:59,620 --> 00:01:02,680
如果我走得太快，让我知道。

24
00:01:02,680 --> 00:01:05,200
他们只是各种数据
结构，并作为部分

25
00:01:05,200 --> 00:01:07,070
您pset获取如此
即将到来的一周，你会

26
00:01:07,070 --> 00:01:10,340
被要求执行其中的一个，
两人或许them--他们两个

27
00:01:10,340 --> 00:01:12,319
在你的pset中。

28
00:01:12,319 --> 00:01:14,610
好了，我只是要
开始与一些公告。

29
00:01:14,610 --> 00:01:19,070
我们一起去了栈和队列的更多的
深度比我们的测验以前那样。

30
00:01:19,070 --> 00:01:20,990
我们一起去了挂
再次，再次列出，

31
00:01:20,990 --> 00:01:23,899
更深入的比
我们在测验前了。

32
00:01:23,899 --> 00:01:26,440
然后我们来谈谈哈希
表，树和尝试，这

33
00:01:26,440 --> 00:01:28,890
都是很必要的PSET。

34
00:01:28,890 --> 00:01:32,925
然后我们将介绍一些
有用的技巧pset5。

35
00:01:32,925 --> 00:01:37,360
>> 好了，测验0。

36
00:01:37,360 --> 00:01:41,090
平均为58％。

37
00:01:41,090 --> 00:01:45,370
这是非常低的，所以你们所有
按照表现非常，非常好

38
00:01:45,370 --> 00:01:46,510
接着就，随即。

39
00:01:46,510 --> 00:01:49,970
>> 好看多了，经验法则是，如果你是
内的平均值的标准偏差

40
00:01:49,970 --> 00:01:52,990
特别是因为我们正处在一个较小
舒适的部分，你完全罚款。

41
00:01:52,990 --> 00:01:54,120
你的轨道上。

42
00:01:54,120 --> 00:01:55,190
生活很好。

43
00:01:55,190 --> 00:01:58,952
>> 我知道它的可怕认为
我喜欢这个测验40％。

44
00:01:58,952 --> 00:02:00,160
我要失败，这个类。

45
00:02:00,160 --> 00:02:02,243
我答应你，你不
要失败的类。

46
00:02:02,243 --> 00:02:03,680
你完全罚款。

47
00:02:03,680 --> 00:02:06,850
>> 对于那些你们谁得到了
平均，令人印象深刻的，令人印象深刻，

48
00:02:06,850 --> 00:02:08,780
像，认真做得很好。

49
00:02:08,780 --> 00:02:09,689
我让他们和我在一起。

50
00:02:09,689 --> 00:02:11,730
随时来让他们
在段的末端。

51
00:02:11,730 --> 00:02:14,520
我们如果您有任何我知道，
问题，与他们的问题。

52
00:02:14,520 --> 00:02:17,204
如果我们增加了你的分数
错了，让我们知道。

53
00:02:17,204 --> 00:02:21,240
>> 好了，pset5，这是一个非常
奇怪的一周耶鲁大学的意义

54
00:02:21,240 --> 00:02:24,240
我们的PSET是由于
周三中午，包括

55
00:02:24,240 --> 00:02:27,317
晚一天，所以它实际上
在周二中午理论上所致。

56
00:02:27,317 --> 00:02:29,150
大概没有人完成
在周二中午。

57
00:02:29,150 --> 00:02:30,830
这是完全正常。

58
00:02:30,830 --> 00:02:33,700
我们将有办公时间
今晚以及周一晚上。

59
00:02:33,700 --> 00:02:36,810
和所有的部分将于本周
实际上变成车间，

60
00:02:36,810 --> 00:02:38,800
您可以随意弹出的
你想要的任何部分，

61
00:02:38,800 --> 00:02:42,810
他们会是怎样的迷你PSET
讲习班上的帮助。

62
00:02:42,810 --> 00:02:45,620
因此，作为这样的，这是唯一的部
在这里我们教材。

63
00:02:45,620 --> 00:02:49,220
所有其他部分将集中
专门对pset的帮助。

64
00:02:49,220 --> 00:02:50,146
是吗？

65
00:02:50,146 --> 00:02:52,000
>> 听众：在哪里上班时间？

66
00:02:52,000 --> 00:02:56,120
>> ANDI彭：办公时间
tonight--哦，很好的问题。

67
00:02:56,120 --> 00:03:00,580
我想今晚办公时间
在蒂尔或共享。

68
00:03:00,580 --> 00:03:02,984
如果你在网上查询CS50
你去办公时间，

69
00:03:02,984 --> 00:03:05,650
应该有一个时间表
告诉您所有的人都。

70
00:03:05,650 --> 00:03:07,954
>> 我知道，无论是今晚
或者明天是水鸭，

71
00:03:07,954 --> 00:03:10,120
我想我们可以有
公地的晚上。

72
00:03:10,120 --> 00:03:11,020
我不确定。

73
00:03:11,020 --> 00:03:11,700
好问题。

74
00:03:11,700 --> 00:03:14,430
检查CS50。

75
00:03:14,430 --> 00:03:18,780
>> 酷，任何有关的问题
计划在未来像三个日子吗？

76
00:03:18,780 --> 00:03:21,690
我保证你们喜欢大卫
说，这是在山顶上。

77
00:03:21,690 --> 00:03:23,050
你们是几乎没有。

78
00:03:23,050 --> 00:03:24,644
仅仅三天。

79
00:03:24,644 --> 00:03:26,310
到达那里，然后我们都来了。

80
00:03:26,310 --> 00:03:28,114
我们将有一个很好的CS-免费休息。

81
00:03:28,114 --> 00:03:28,780
欢迎回来。

82
00:03:28,780 --> 00:03:30,779
我们将深入到网络
编程与开发，

83
00:03:30,779 --> 00:03:35,150
事情是非常有趣的对比
一些其他的pset的。

84
00:03:35,150 --> 00:03:37,974
而这将是凄凉，
我们有很多的乐趣。

85
00:03:37,974 --> 00:03:38,890
我们将有更多的糖果。

86
00:03:38,890 --> 00:03:39,730
对不起，糖果。

87
00:03:39,730 --> 00:03:40,945
我忘了糖果。

88
00:03:40,945 --> 00:03:43,310
这是一个粗糙的早晨。

89
00:03:43,310 --> 00:03:46,340
所以，你们是几乎没有，
而且我非常自豪的你们的。

90
00:03:46,340 --> 00:03:49,570
>> 好了，栈。

91
00:03:49,570 --> 00:03:53,331
谁爱杰克的问题
和他的衣服上的测验？

92
00:03:53,331 --> 00:03:53,830
没人？

93
00:03:53,830 --> 00:03:56,500
好吧。

94
00:03:56,500 --> 00:04:00,200
>> 所以基本上，你可以
图片杰克，这个家伙在这里，

95
00:04:00,200 --> 00:04:03,350
喜欢拿衣服
出栈的顶部，

96
00:04:03,350 --> 00:04:05,750
他把它放回
之后，他在堆栈的完成。

97
00:04:05,750 --> 00:04:07,600
因此以这种方式，他从未
似乎越来越

98
00:04:07,600 --> 00:04:10,090
到的底部
堆在他的衣服。

99
00:04:10,090 --> 00:04:12,600
所以，这样的描述
基本的数据结构

100
00:04:12,600 --> 00:04:16,610
一个堆栈是如何实现的。

101
00:04:16,610 --> 00:04:20,060
>> 从本质上讲，想想
协议栈的任何栈对象

102
00:04:20,060 --> 00:04:24,900
你把东西到顶部，
那么你从顶部弹出出来。

103
00:04:24,900 --> 00:04:28,600
因此，后进先出法是我们喜欢的缩写
以use--后进先出。

104
00:04:28,600 --> 00:04:32,480
所以，最后到的顶部
栈是第一个出来。

105
00:04:32,480 --> 00:04:34,260
这样一来，两个词
我们喜欢联想

106
00:04:34,260 --> 00:04:36,190
与被称为push和pop。

107
00:04:36,190 --> 00:04:39,790
当你把一些东西到
堆栈和你的流行回来了。

108
00:04:39,790 --> 00:04:43,422
>> 所以我想这是种
抽象的概念，对于那些你

109
00:04:43,422 --> 00:04:45,630
谁希望看到像
这实际执行

110
00:04:45,630 --> 00:04:46,740
在现实世界中。

111
00:04:46,740 --> 00:04:50,170
你们有多少人写了一篇文章，
也许就像一个小时之前，这是由于，

112
00:04:50,170 --> 00:04:54,510
你不小心删除了一个巨大的
大块的它，就像不小心？

113
00:04:54,510 --> 00:04:58,560
然后呢控制做
我们用它来把它放回去？

114
00:04:58,560 --> 00:05:00,030
控制-Z，是吗？

115
00:05:00,030 --> 00:05:03,640
控制-Z，所以倍量
控制-Z已经救了我的命，

116
00:05:03,640 --> 00:05:08,820
救了我的屁股，每次
该真实通过烟囱实现。

117
00:05:08,820 --> 00:05:13,020
>> 基本上所有的信息
这是您的Word文档，

118
00:05:13,020 --> 00:05:15,080
它被压入和弹出的意愿。

119
00:05:15,080 --> 00:05:19,460
所以基本上每当你
删除任何东西，你的流行回来了。

120
00:05:19,460 --> 00:05:22,820
然后，如果你需要它回来，你
推，这是控制-C一样。

121
00:05:22,820 --> 00:05:26,770
所以，现实世界中的功能
多么简单的数据结构

122
00:05:26,770 --> 00:05:28,690
可以帮助你的日常生活。

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> 因此，一个结构的方式，
我们实际上创建一个堆。

125
00:05:40,150 --> 00:05:44,720
我们定义类型结构，然后
我们把它在底部堆。

126
00:05:44,720 --> 00:05:47,440
和栈内，
我们有两个参数

127
00:05:47,440 --> 00:05:51,580
我们基本上可以操纵，
所以我们有字符的字符串星能力。

128
00:05:51,580 --> 00:05:55,150
>> 所有这一切是做
正在创建一个数组

129
00:05:55,150 --> 00:05:58,835
我们可以存储任何你想要的
我们可以判断其能力。

130
00:05:58,835 --> 00:06:01,990
能力是刚刚最大金额
项目我们可以把这个数组。

131
00:06:01,990 --> 00:06:05,660
INT大小是保持计数器
跟踪有多少项目是目前

132
00:06:05,660 --> 00:06:07,850
在栈。

133
00:06:07,850 --> 00:06:11,860
所以后来我们就可以跟踪，A，
无论有多大的实际堆栈，

134
00:06:11,860 --> 00:06:14,850
和，B多少该堆栈的
我们充满因为我们不希望

135
00:06:14,850 --> 00:06:18,800
溢出超过了我们的能力。

136
00:06:18,800 --> 00:06:24,340
>> 因此，例如，这个可爱的
问题是你的测验。

137
00:06:24,340 --> 00:06:28,160
从本质上讲，我们如何推动
到堆栈的顶部。

138
00:06:28,160 --> 00:06:28,830
很简单。

139
00:06:28,830 --> 00:06:30,621
如果你看看吧，
我们将穿行于此。

140
00:06:30,621 --> 00:06:32,640
如果[听不清] size--
请记住，当你

141
00:06:32,640 --> 00:06:35,300
要访问任何
一个结构内的参数，

142
00:06:35,300 --> 00:06:40,320
你做struct.parameter的名称。

143
00:06:40,320 --> 00:06:42,720
>> 在这种情况下，s是
我们的叠层的名称。

144
00:06:42,720 --> 00:06:46,230
我们要访问的大小
这一点，所以我们做s.size。

145
00:06:46,230 --> 00:06:50,280
所以只要尺寸不
等于能力，长

146
00:06:50,280 --> 00:06:52,940
因为它是低于产能，
要么就在这里工作。

147
00:06:52,940 --> 00:06:57,180
>> 你想访问内
你的筹码，所以s.strings，

148
00:06:57,180 --> 00:07:00,790
你打算把新号码
要插入到那里。

149
00:07:00,790 --> 00:07:05,030
远的不说，我们将要
插入INTñ压入堆栈，

150
00:07:05,030 --> 00:07:08,905
我们可以做s.strings，
括号，s.size等于ñ。

151
00:07:08,905 --> 00:07:11,030
由于尺寸是我们
当前有在堆栈

152
00:07:11,030 --> 00:07:14,590
如果我们要推动
它，我们刚刚访问

153
00:07:14,590 --> 00:07:17,370
无论大小，则
叠层的当前饱胀，

154
00:07:17,370 --> 00:07:21,729
我们推INTñ到它。

155
00:07:21,729 --> 00:07:24,770
然后我们要确保
我们也递增了n个大小，

156
00:07:24,770 --> 00:07:27,436
所以我们可以跟踪我们已经
增加了一个额外的东西到堆栈中。

157
00:07:27,436 --> 00:07:29,660
现在我们有一个更大的尺寸。

158
00:07:29,660 --> 00:07:33,196
这是否在这里是有意义的
大家，如何在逻辑上是否可行？

159
00:07:33,196 --> 00:07:34,160
这是一种快捷。

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
听众：你可以走了
在s.stringss.strings [s.size]了吗？

162
00:07:42,160 --> 00:07:45,808
ANDI彭：当然，有什么呢
s.size目前给我们？

163
00:07:45,808 --> 00:07:47,440
听众：这是当前大小。

164
00:07:47,440 --> 00:07:50,890
ANDI鹏：没错，所以
目前的指数，我们的规模是，

165
00:07:50,890 --> 00:07:57,780
所以我们希望把新的整数
我们要插入s.size。

166
00:07:57,780 --> 00:07:58,760
那有意义吗？

167
00:07:58,760 --> 00:08:01,110
因为s.strings，所有的
是是阵列的名称。

168
00:08:01,110 --> 00:08:03,510
所有这是访问
我们的结构内的数组，

169
00:08:03,510 --> 00:08:06,030
因此，如果我们想
将正成指数，

170
00:08:06,030 --> 00:08:09,651
我们可以只访问
使用括号s.size。

171
00:08:09,651 --> 00:08:10,150
凉。

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> 好吧，流行，我伪出来
为你们这些家伙，但类似的概念。

174
00:08:18,916 --> 00:08:19,790
那有意义吗？

175
00:08:19,790 --> 00:08:22,310
如果尺寸大于
大于零，则

176
00:08:22,310 --> 00:08:25,350
知道你想要拿东西
出，因为如果尺寸不

177
00:08:25,350 --> 00:08:27,620
大于零，则
有没有在堆栈中。

178
00:08:27,620 --> 00:08:29,840
>> 所以，你只需要执行
这段代码，它只能

179
00:08:29,840 --> 00:08:32,320
弹出如果有什么流行。

180
00:08:32,320 --> 00:08:35,830
所以如果尺寸更大
大于0，我们减去大小。

181
00:08:35,830 --> 00:08:40,020
我们减小大小，然后返回
无论是内部的，因为

182
00:08:40,020 --> 00:08:42,710
通过弹出，我们要
无论是存储的访问

183
00:08:42,710 --> 00:08:45,694
在堆栈的顶部的索引。

184
00:08:45,694 --> 00:08:46,610
一切有意义吗？

185
00:08:46,610 --> 00:08:49,693
如果我让你们写了这一点，
将你们能写出来？

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK，你们可以玩它。

188
00:08:53,570 --> 00:08:55,252
不用担心，如果你不明白这一点。

189
00:08:55,252 --> 00:08:57,460
我们没有时间去编写
它今天因为我们

190
00:08:57,460 --> 00:08:59,959
得到了很多这些结构
穿过去，但本质

191
00:08:59,959 --> 00:09:02,214
伪代码，非常，非常相似推。

192
00:09:02,214 --> 00:09:03,380
只要跟着逻辑。

193
00:09:03,380 --> 00:09:06,092
请确保你所访问的所有
你的结构功能正常。

194
00:09:06,092 --> 00:09:06,574
是吗？

195
00:09:06,574 --> 00:09:09,282
>> 听众：请问这些幻灯片和
这整个事情高达今天十岁上下的？

196
00:09:09,282 --> 00:09:11,586
ANDI彭：始终，是的。

197
00:09:11,586 --> 00:09:13,710
我会尽量把
这像一个小时后。

198
00:09:13,710 --> 00:09:16,626
我会通过电子邮件大卫，大卫将尝试
把它像在此之后一个小时。

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> 好了，接下来我们进入这个其他
可爱的数据结构称为队列。

201
00:09:25,470 --> 00:09:30,140
正如你们所看到的，一
队列，对于我们中间英国，

202
00:09:30,140 --> 00:09:32,010
所有这是一条线。

203
00:09:32,010 --> 00:09:34,680
那么相反的是
你觉得一个堆栈，

204
00:09:34,680 --> 00:09:37,750
队列是什么
在逻辑上，你认为它是。

205
00:09:37,750 --> 00:09:41,914
它保持由FIFO的规则，
这是先入先出。

206
00:09:41,914 --> 00:09:43,705
如果你是第一个
一个在行，你

207
00:09:43,705 --> 00:09:46,230
第一个
出来的线。

208
00:09:46,230 --> 00:09:49,680
>> 所以，我们喜欢把这种
在出队，并排入队列。

209
00:09:49,680 --> 00:09:52,380
如果我们想要添加的东西
我们的队列中，我们入队。

210
00:09:52,380 --> 00:09:55,690
如果我们要离队，或采取
一些东西，我们出队。

211
00:09:55,690 --> 00:10:03,350
>> 因此，同样的道理，我们是那种
创建固定大小的元素，我们

212
00:10:03,350 --> 00:10:06,500
可以存储一定的
的事情，但是我们也可以

213
00:10:06,500 --> 00:10:10,100
改变我们正在把
他们的内部参数

214
00:10:10,100 --> 00:10:13,140
基于什么类型
功能我们想要的。

215
00:10:13,140 --> 00:10:16,700
所以栈，我们希望最后
酮，N是第一个出来。

216
00:10:16,700 --> 00:10:19,800
排队是我们要的第一件事情
在成为第一件事出去。

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> 因此，结构型
定义，你可以看到，

219
00:10:26,710 --> 00:10:29,470
这是一个有点不同
从什么堆栈是

220
00:10:29,470 --> 00:10:33,120
因为我们不仅要保持
轨道的其中该尺寸是目前，

221
00:10:33,120 --> 00:10:37,420
我们也想跟踪头
以及我们当前有。

222
00:10:37,420 --> 00:10:39,580
所以我觉得它更容易
如果我画这件事。

223
00:10:39,580 --> 00:10:53,270
因此，让我们想象一下，我们已经有了一个队列，
所以我们说，头就在这里。

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
该行的负责人，让我们
只是说这是目前在那里，

226
00:10:58,310 --> 00:11:01,809
我们要插入
事到队列。

227
00:11:01,809 --> 00:11:04,350
我要去基本上调用大小
是同样的事情，尾，

228
00:11:04,350 --> 00:11:06,314
哪里的队列的末尾。

229
00:11:06,314 --> 00:11:07,730
远的不说大小就在这里。

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> 那么，如何切实
东西插入到队列中？

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
什么样的指标，我们要放置
在这里我们要插入。

234
00:11:24,130 --> 00:11:29,320
如果这是开头的
排队，这是它的结束

235
00:11:29,320 --> 00:11:31,860
或者它的大小，我们在哪里
要添加的下一个对象？

236
00:11:31,860 --> 00:11:32,920
>> 听众：[听不清]

237
00:11:32,920 --> 00:11:35,920
ANDI鹏：没错，你想添加
它取决于你写的。

238
00:11:35,920 --> 00:11:37,840
这要么是空白，或为空。

239
00:11:37,840 --> 00:11:42,630
所以，你想可能添加
在这里，因为如果大小is--

240
00:11:42,630 --> 00:11:50,540
如果这些都满了，你想
将其添加在这里，对不对？

241
00:11:50,540 --> 00:11:57,150
>> 所以这就是，虽然非常非常
简单，不太总是正确的

242
00:11:57,150 --> 00:12:00,690
因为主要的区别
队列和堆之间

243
00:12:00,690 --> 00:12:04,350
是，队列可以
实际上被操纵

244
00:12:04,350 --> 00:12:06,980
使头部的变化
这取决于你想上哪儿

245
00:12:06,980 --> 00:12:08,650
您的线索年初启动。

246
00:12:08,650 --> 00:12:11,900
其结果，你的尾巴
也不会改变。

247
00:12:11,900 --> 00:12:14,770
所以看看
此代码现在。

248
00:12:14,770 --> 00:12:18,620
正如你们也被要求
写出来的测验，入队。

249
00:12:18,620 --> 00:12:22,580
也许我们会聊过为什么
答案是什么。

250
00:12:22,580 --> 00:12:26,790
>> 在一个我不太适合这一行，
但本质上这一段代码

251
00:12:26,790 --> 00:12:29,030
应该是在一行上。

252
00:12:29,030 --> 00:12:30,140
花想30秒。

253
00:12:30,140 --> 00:12:33,000
看看，看看为什么
这是，它是这样的。

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> 非常，非常相似的结构，非常，非常
类似的结构与前面

256
00:12:55,420 --> 00:12:58,090
堆叠除了可能
一行代码。

257
00:12:58,090 --> 00:13:01,190
而这一行代码
确定的功能。

258
00:13:01,190 --> 00:13:03,900
它真的与众不同
从一摞一个队列。

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> 任何人想采取刺
在解释为什么你

261
00:13:22,010 --> 00:13:24,980
拿到这里这个复杂的事情？

262
00:13:24,980 --> 00:13:27,845
我们看到的回报我们
美妙的朋友模量。

263
00:13:27,845 --> 00:13:31,020
正如你们很快就会到来
在编程认识到，

264
00:13:31,020 --> 00:13:34,910
几乎任何时候，你需要的东西
环绕什么，

265
00:13:34,910 --> 00:13:36,850
模将是这样做的方式。

266
00:13:36,850 --> 00:13:40,510
因此，了解的是，没有人想
尝试解释该行代码？

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
是的，所有的答案都
接受和欢迎。

269
00:13:47,507 --> 00:13:48,840
听众：你是在跟我说话？

270
00:13:48,840 --> 00:13:49,506
ANDI彭：是的。

271
00:13:49,506 --> 00:13:56,200
听众：哦，不后悔。

272
00:13:56,200 --> 00:14:00,250
ANDI彭：好，让我们
穿行此代码。

273
00:14:00,250 --> 00:14:03,642
所以，当你想
添加的东西到一个队列，

274
00:14:03,642 --> 00:14:08,510
在可爱的情况下头部发生
是在这里，这很容易让我们

275
00:14:08,510 --> 00:14:10,960
刚走到最后
插入的东西，对不对？

276
00:14:10,960 --> 00:14:14,690
但是队列的整点
头部实际上可以动态地

277
00:14:14,690 --> 00:14:17,280
不同的地方改变我们
希望我们的Q的开始是，

278
00:14:17,280 --> 00:14:19,880
正因为如此，在尾
也不会改变。

279
00:14:19,880 --> 00:14:31,100
>> 所以，想象一下，这是不是
排队，而是这是队列。

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
比方说，头就在这里。

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
比方说，我们的队列看上去像这样。

284
00:14:56,980 --> 00:15:00,190
如果我们想转向哪里
该行的开始是，

285
00:15:00,190 --> 00:15:03,400
假设我们转向头
这种方式和尺寸在这里。

286
00:15:03,400 --> 00:15:07,100
>> 现在我们要添加一些
此队列，但你们可以看到，

287
00:15:07,100 --> 00:15:11,150
它不是那么简单，只是
添加任何的尺寸后，

288
00:15:11,150 --> 00:15:13,630
因为那样的话，我们用完
我们的实际数组的边界。

289
00:15:13,630 --> 00:15:16,190
当我们要真正增加在这里。

290
00:15:16,190 --> 00:15:18,610
这是一个队列的美
是我们的，视觉上

291
00:15:18,610 --> 00:15:22,380
看起来像行是这样的，
但是，当存储在数据结构中，

292
00:15:22,380 --> 00:15:29,370
他们给它像一个循环。

293
00:15:29,370 --> 00:15:32,360
它种环绕
到前以同样的方式

294
00:15:32,360 --> 00:15:34,780
该行也可以换
各地根据地方你

295
00:15:34,780 --> 00:15:36,279
希望该行的开头是。

296
00:15:36,279 --> 00:15:38,630
因此，如果我们拿
往下看这里，让我们

297
00:15:38,630 --> 00:15:40,880
说我们想创造一个
函数调用排队。

298
00:15:40,880 --> 00:15:43,980
我们希望加INT n为进的Q值。

299
00:15:43,980 --> 00:15:49,250
如果q.size q--我们会打电话给我们的数据
结构 - 如果我们的queue.size不

300
00:15:49,250 --> 00:15:52,520
等于能力，或者
这是不到容量，

301
00:15:52,520 --> 00:15:55,120
q.strings是我们q内的阵列。

302
00:15:55,120 --> 00:15:58,380
我们要设置
这等于q.heads，

303
00:15:58,380 --> 00:16:02,730
这是在这里，再加上q.size
模量由容量，这

304
00:16:02,730 --> 00:16:04,290
包裹我们回在这里。

305
00:16:04,290 --> 00:16:08,040
>> 所以在这个例子中，索引
头是1，对吧？

306
00:16:08,040 --> 00:16:11,480
大小的指数为0，1，2，3，4。

307
00:16:11,480 --> 00:16:19,500
因此，我们可以做到1加4模
我们的产能是5。

308
00:16:19,500 --> 00:16:20,920
是什么给我们？

309
00:16:20,920 --> 00:16:23,270
什么是索引
这样来的？

310
00:16:23,270 --> 00:16:24,080
>> 听众：0。

311
00:16:24,080 --> 00:16:27,870
>> ANDI彭：0，
恰好就在这里，

312
00:16:27,870 --> 00:16:30,640
所以我们希望能够
插入到这里。

313
00:16:30,640 --> 00:16:34,730
所以这个公式在这里种
仅适用于任何数字

314
00:16:34,730 --> 00:16:36,750
不同的地方你
头部和你的尺寸是。

315
00:16:36,750 --> 00:16:38,541
如果你知道这些
事情是，你知道

316
00:16:38,541 --> 00:16:43,170
正是您要插入
您的队列后，无论是。

317
00:16:43,170 --> 00:16:44,640
这是否有意义给大家？

318
00:16:44,640 --> 00:16:48,560
>> 我知道怎样的一个大脑
传情特别是因为这

319
00:16:48,560 --> 00:16:50,512
排在你竞猜的善后工作。

320
00:16:50,512 --> 00:16:52,220
但希望大家
现在可以理解

321
00:16:52,220 --> 00:16:57,800
为什么这个解决方案或本
功能是，它是这样的。

322
00:16:57,800 --> 00:16:59,840
任何人都有点不清楚的是什么？

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
好。

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> 所以现在，如果你
要离队，这

327
00:17:09,970 --> 00:17:15,240
是我们的头会转向
因为如果我们要出列，

328
00:17:15,240 --> 00:17:17,030
我们不取下q的末端。

329
00:17:17,030 --> 00:17:19,130
我们要起飞的头，对不对？

330
00:17:19,130 --> 00:17:24,260
因此，作为结果，磁头会改变，
这就是为什么当你入队，

331
00:17:24,260 --> 00:17:26,800
你必须保持跟踪
在这里你的头，你的尺寸

332
00:17:26,800 --> 00:17:29,450
是能够插入
到正确的位置。

333
00:17:29,450 --> 00:17:32,740
>> 所以，当你出列，
我还伪出来。

334
00:17:32,740 --> 00:17:35,480
随意，如果你想
尝试编码了这一点。

335
00:17:35,480 --> 00:17:36,980
要移动头部，对不对？

336
00:17:36,980 --> 00:17:39,320
如果我想离队，我
将移动头以上。

337
00:17:39,320 --> 00:17:40,800
这将是头部。

338
00:17:40,800 --> 00:17:45,617
>> 而我们目前的规模会
减去因为我们不再

339
00:17:45,617 --> 00:17:46,950
在阵列中四个元素。

340
00:17:46,950 --> 00:17:51,370
我们只有三个，然后我们要
返回不管里面储存

341
00:17:51,370 --> 00:17:56,260
头部，因为我们希望借此
值出所以非常相似的栈。

342
00:17:56,260 --> 00:17:58,010
只要你参加
来自不同的地方，

343
00:17:58,010 --> 00:18:01,770
你必须重新分配指针
不同的地方作为一个结果。

344
00:18:01,770 --> 00:18:03,890
从逻辑上讲，每个人都遵循？

345
00:18:03,890 --> 00:18:05,690
大。

346
00:18:05,690 --> 00:18:10,156
>> 好了，我们要商量了一下
更深入的了解链表

347
00:18:10,156 --> 00:18:13,280
因为他们将是非常，非常有价值
您在本周的过程

348
00:18:13,280 --> 00:18:14,964
pset中。

349
00:18:14,964 --> 00:18:17,130
链表，因为你们
能记住，一切又都

350
00:18:17,130 --> 00:18:22,570
是有一定的节点节点
两者的值和一个指针值

351
00:18:22,570 --> 00:18:26,290
连接在一起的
通过这些指针。

352
00:18:26,290 --> 00:18:29,880
因此如何在结构
我们在这里创建一个节点，我们

353
00:18:29,880 --> 00:18:33,569
是int n，这个是什么
在商店或字符串值n

354
00:18:33,569 --> 00:18:35,610
或者任何你想
调用它，焦炭星ñ。

355
00:18:35,610 --> 00:18:41,482
结构节点星，这是指针
要在每个节点上，

356
00:18:41,482 --> 00:18:43,690
你将有
对下一个指针点。

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
你得头
链表那

359
00:18:50,040 --> 00:18:53,140
要指出的其余部分
等等，等等的值

360
00:18:53,140 --> 00:18:55,290
直到你最终到达终点。

361
00:18:55,290 --> 00:18:58,040
而这最后一个节点仅仅是
要没有一个指针。

362
00:18:58,040 --> 00:18:59,952
这将指向
空，这就是当

363
00:18:59,952 --> 00:19:01,910
你知道你已经打了
您的链接列表的末尾

364
00:19:01,910 --> 00:19:04,076
就是当你的最后一个指针
不指向任何东西。

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> 因此，我们要去多一点的
关于深入怎么一会可能

367
00:19:10,990 --> 00:19:12,400
搜索一个链表。

368
00:19:12,400 --> 00:19:15,460
记住是一些
该链表的缺点

369
00:19:15,460 --> 00:19:19,340
诗句关于搜索的阵列。

370
00:19:19,340 --> 00:19:22,565
数组可以二进制搜索，但
你为什么不能做，在一个链表？

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> 听众：因为他们都是互相联系在一起，
但你不太知道在哪里

373
00:19:30,320 --> 00:19:31,330
[听不清]。

374
00:19:31,330 --> 00:19:34,600
>> ANDI彭：是的，正是这样记
一个数组的辉煌

375
00:19:34,600 --> 00:19:37,190
是事实，我们有
随机存取存储器，其中

376
00:19:37,190 --> 00:19:41,580
如果我想从指数值
六，我可以说，指数六，

377
00:19:41,580 --> 00:19:42,407
给我的价值。

378
00:19:42,407 --> 00:19:45,240
那是因为数组排序
在一个连续的内存空间

379
00:19:45,240 --> 00:19:48,020
在一个地方，而
一种链表

380
00:19:48,020 --> 00:19:52,820
是随机散布各地，
而只有这样，你可以找到一个

381
00:19:52,820 --> 00:19:56,890
是通过指针，告诉你
的，其中该下一个节点是地址。

382
00:19:56,890 --> 00:20:00,290
>> 所以作为结果，只有这样
通过一个链接列表来搜索

383
00:20:00,290 --> 00:20:01,560
是线性搜索。

384
00:20:01,560 --> 00:20:05,890
因为我完全不知道在哪里
在该链接的表的第12值是，

385
00:20:05,890 --> 00:20:08,780
我必须遍历全部
那链接列表中的一个

386
00:20:08,780 --> 00:20:12,450
由一个从头部到第一节点，
到第二个节点，到第三节点，

387
00:20:12,450 --> 00:20:17,690
一路下来，直到我终于搞定
到这个节点，我要找的是。

388
00:20:17,690 --> 00:20:22,110
因此在这个意义上说，搜索
上链表总是n。

389
00:20:22,110 --> 00:20:23,040
它总是ñ。

390
00:20:23,040 --> 00:20:25,690
它总是以线性时间。

391
00:20:25,690 --> 00:20:28,470
>> 这样一来，代码中
我们实现这一点，而这

392
00:20:28,470 --> 00:20:32,620
有点新的你们，因为你们
人还没有真正谈过或曾经

393
00:20:32,620 --> 00:20:35,000
在如何看到指针
通过搜索指针，

394
00:20:35,000 --> 00:20:37,670
因此，我们将演练
这个非常，非常缓慢。

395
00:20:37,670 --> 00:20:40,200
所以布尔检索，权，
让我们想象一下，我们希望

396
00:20:40,200 --> 00:20:42,820
创建一个名为函数
搜索返回true

397
00:20:42,820 --> 00:20:46,820
如果您发现里面的链接的价值
列表，并将否则返回false。

398
00:20:46,820 --> 00:20:50,030
节点明星名单
目前只是指针

399
00:20:50,030 --> 00:20:52,960
在你的链接列表中的第一项。

400
00:20:52,960 --> 00:20:56,700
INT N是你的价值
搜寻在该列表中。

401
00:20:56,700 --> 00:20:58,770
>> 因此，节点星指针等于名单。

402
00:20:58,770 --> 00:21:00,970
这意味着我们正在设置
和创建的指针

403
00:21:00,970 --> 00:21:03,592
到列表的内部该第一个节点。

404
00:21:03,592 --> 00:21:04,300
每个人都和我在一起？

405
00:21:04,300 --> 00:21:06,530
因此，如果我们当中去
回到这里，我会

406
00:21:06,530 --> 00:21:13,850
初始化指针指向
无论头部的名单。

407
00:21:13,850 --> 00:21:18,600
>> 然后，一旦你到这里，
同时指针不等于空，

408
00:21:18,600 --> 00:21:22,160
所以这是我们在其中循环
将要随后遍历

409
00:21:22,160 --> 00:21:25,940
我们因为什么列表的其余部分
发生在指针等于null？

410
00:21:25,940 --> 00:21:27,550
我们知道，我们have--

411
00:21:27,550 --> 00:21:28,450
>> 听众：[听不清]

412
00:21:28,450 --> 00:21:31,491
>> ANDI鹏：没错，所以我们知道，
我们已经达到列表的末尾，对不对？

413
00:21:31,491 --> 00:21:34,470
如果你回到这里，每个节点
应指向另一节点

414
00:21:34,470 --> 00:21:36,550
等等等等
直到你打最后

415
00:21:36,550 --> 00:21:41,589
您链表的尾部，
它具有一个指针，只是

416
00:21:41,589 --> 00:21:43,130
不点不是没有其他任何地方。

417
00:21:43,130 --> 00:21:47,510
所以你基本上知道
你的名单仍然有上升

418
00:21:47,510 --> 00:21:50,900
直到指针不等于
null，因为一旦它等于空，

419
00:21:50,900 --> 00:21:53,310
你知道，有没有更多的东西。

420
00:21:53,310 --> 00:21:56,930
>> 所以这是循环，其中我们
将有实际的搜索。

421
00:21:56,930 --> 00:22:01,690
而如果pointer--你看
那种箭功能那里？

422
00:22:01,690 --> 00:22:06,930
因此，如果指针指向为n，如果
在n等于等于n个指针，

423
00:22:06,930 --> 00:22:09,180
因此，这意味着，如果
你是指针

424
00:22:09,180 --> 00:22:13,420
在每个结束搜索
节点实际上等于值

425
00:22:13,420 --> 00:22:15,990
你要找的话
要返回true。

426
00:22:15,990 --> 00:22:19,280
所以基本上，如果你在一个节点
有你正在寻找的价值，

427
00:22:19,280 --> 00:22:23,550
你知道你已经
能够成功地搜索。

428
00:22:23,550 --> 00:22:27,150
>> 否则，你要设置
指针到下一个节点。

429
00:22:27,150 --> 00:22:28,850
这就是这条线在这里做。

430
00:22:28,850 --> 00:22:31,750
指针等于下一个指针。

431
00:22:31,750 --> 00:22:33,360
每个人都看到了的工作？

432
00:22:33,360 --> 00:22:36,580
>> 而且基本上你要只
遍历列表的全部，

433
00:22:36,580 --> 00:22:41,920
重置每一次，直到你的指针
你最终击中列表的末尾。

434
00:22:41,920 --> 00:22:45,030
你知道有没有
更多的节点进行搜索，

435
00:22:45,030 --> 00:22:47,999
然后你就可以返回false
因为你知道，哦，好吧，

436
00:22:47,999 --> 00:22:50,540
如果我已经能够搜索
通过列表的全部。

437
00:22:50,540 --> 00:22:54,530
如果在这个例子中，如果我想
寻找值10，

438
00:22:54,530 --> 00:22:57,250
我开始在头，
我搜索一路下跌，

439
00:22:57,250 --> 00:23:00,550
而我最终得到了这一点，这
一个指针指向空，

440
00:23:00,550 --> 00:23:04,415
我知道，废话，我想10不
这个名单是因为我找不到它。

441
00:23:04,415 --> 00:23:06,520
而我在列表的末尾。

442
00:23:06,520 --> 00:23:11,040
而在这种情况下，你知道
我将返回false。

443
00:23:11,040 --> 00:23:12,900
>> 让那浸泡在一点点。

444
00:23:12,900 --> 00:23:17,350
这将是非常
重要的是你的pset中。

445
00:23:17,350 --> 00:23:21,140
它的逻辑很简单，也许
语法只是实现它。

446
00:23:21,140 --> 00:23:23,365
你们想使
确保你理解。

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
凉。

449
00:23:27,650 --> 00:23:32,560
>> 好了，我们怎么会
插入节点，右，

450
00:23:32,560 --> 00:23:35,380
到列表中，因为记住
是什么的有什么好处，

451
00:23:35,380 --> 00:23:39,230
具有的链接列表与
在存储方面的阵列？

452
00:23:39,230 --> 00:23:41,110
>> 听众：这是动态的，
所以它更容易用于：

453
00:23:41,110 --> 00:23:43,180
>> ANDI鹏：没错，
所以它是动态的，

454
00:23:43,180 --> 00:23:46,880
意味着它可以扩大和缩小
取决于用户的需要。

455
00:23:46,880 --> 00:23:56,570
因此，在这个意义上，我们并不需要
浪费不必要的内存，因为我

456
00:23:56,570 --> 00:24:00,850
如果我不知道有多少值要
存储，它没有任何意义，我

457
00:24:00,850 --> 00:24:04,310
创建因为数组
如果我想存储10个值

458
00:24:04,310 --> 00:24:08,380
我创建的1000阵列，这是
大量浪费的内存，配发。

459
00:24:08,380 --> 00:24:11,180
这就是为什么我们要使用一个链接
列表能够动态

460
00:24:11,180 --> 00:24:13,860
改变或缩小我们的规模。

461
00:24:13,860 --> 00:24:17,040
>> 而这样就使得插入
有点复杂。

462
00:24:17,040 --> 00:24:20,810
既然我们不能随意访问元素
将我们的数组的方式。

463
00:24:20,810 --> 00:24:24,270
如果我想插入元素
进入第七个指标，

464
00:24:24,270 --> 00:24:26,930
我只是将它插入
进入第七个指标。

465
00:24:26,930 --> 00:24:30,020
上一个链表，它不
很容易地工作，

466
00:24:30,020 --> 00:24:34,947
所以如果我们想插入
这里一个在该链接的表，

467
00:24:34,947 --> 00:24:36,280
在视觉上，它很容易看到。

468
00:24:36,280 --> 00:24:39,363
我们只是希望将其插入那里，
就在列表的开头，

469
00:24:39,363 --> 00:24:40,840
后头部右侧。

470
00:24:40,840 --> 00:24:44,579
>> 但在其中，我们有方式重新分配
指针是不是有点绕口

471
00:24:44,579 --> 00:24:47,620
或者，从逻辑上讲，这是有道理的，但
你要确保你拥有了它

472
00:24:47,620 --> 00:24:50,250
完全下来，因为
你想的最后一件事

473
00:24:50,250 --> 00:24:52,990
是重新分配的指针的
我们在这里做的方式。

474
00:24:52,990 --> 00:24:58,170
如果取消引用
从头指针为1，

475
00:24:58,170 --> 00:25:01,086
然后突然的的
您的链接列表的其余部分

476
00:25:01,086 --> 00:25:04,680
是丢失，因为你还没有真正
创建的临时任何东西。

477
00:25:04,680 --> 00:25:06,220
这是指着2。

478
00:25:06,220 --> 00:25:10,080
如果重新分配的指针，那么
列表的其余部分完全丧失。

479
00:25:10,080 --> 00:25:13,310
所以，你想成为
非常非常小心这里

480
00:25:13,310 --> 00:25:17,010
先分配
无论从任何你指针

481
00:25:17,010 --> 00:25:20,150
要插入到哪里
你想，然后你

482
00:25:20,150 --> 00:25:22,710
可以取消引用列表的其余部分。

483
00:25:22,710 --> 00:25:25,250
>> 因此，这适用于任何地方
你想插入。

484
00:25:25,250 --> 00:25:27,520
如果要插入的
头，如果你想在这里回答，

485
00:25:27,520 --> 00:25:29,455
如果要插入的
最后，好了，我到底

486
00:25:29,455 --> 00:25:30,910
猜你只想
有没有指针，但你

487
00:25:30,910 --> 00:25:33,830
要确保你不
失去你的列表的其余部分。

488
00:25:33,830 --> 00:25:36,640
你总是要确保
你的新节点指向

489
00:25:36,640 --> 00:25:39,330
对任何你
要插入，

490
00:25:39,330 --> 00:25:42,170
然后您可以添加链接上。

491
00:25:42,170 --> 00:25:43,330
大家都清楚了吗？

492
00:25:43,330 --> 00:25:45,427
>> 这将是
一个真正的问题。

493
00:25:45,427 --> 00:25:48,010
其中一个最重要的问题
你要对你的pset

494
00:25:48,010 --> 00:25:51,340
是，你要尝试创建
链表和插入件事情

495
00:25:51,340 --> 00:25:53,340
但当时只是失去了
剩下的链表中。

496
00:25:53,340 --> 00:25:54,900
而你要像我
不知道为什么会这样？

497
00:25:54,900 --> 00:25:58,040
而且这是一个痛苦的经历
并搜索所有的指针。

498
00:25:58,040 --> 00:26:02,100
>> 我保证你在这pset中，
书写和绘画这些节点出

499
00:26:02,100 --> 00:26:03,344
将是非常，非常有帮助。

500
00:26:03,344 --> 00:26:06,010
所以，你可以完全跟踪
在那里所有的指针，

501
00:26:06,010 --> 00:26:08,540
什么错，
您所有的节点，

502
00:26:08,540 --> 00:26:12,660
你需要做的访问或
插入或删除，或任何人。

503
00:26:12,660 --> 00:26:14,550
每个人都好有吗？

504
00:26:14,550 --> 00:26:15,050
凉。

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> 因此，如果我们想看看代码？

507
00:26:22,600 --> 00:26:24,470
哦，我不知道，如果我们
可以看到the--好了，

508
00:26:24,470 --> 00:26:27,940
顶部所有它是一个功能
在这里我们要命名插入

509
00:26:27,940 --> 00:26:31,365
插入INT n为进链表。

510
00:26:31,365 --> 00:26:32,740
我们将穿行于此。

511
00:26:32,740 --> 00:26:34,770
这是一个很大的代码，有很多新的语法。

512
00:26:34,770 --> 00:26:36,220
我们会没事的。

513
00:26:36,220 --> 00:26:39,120
>> 所以在顶部，每当
我们要创建什么

514
00:26:39,120 --> 00:26:42,380
什么我们需要做的，特别是如果你
希望它不被存储在栈上

515
00:26:42,380 --> 00:26:43,920
但在堆？

516
00:26:43,920 --> 00:26:45,460
我们去的malloc，对不对？

517
00:26:45,460 --> 00:26:48,240
因此，我们要创建一个指针。

518
00:26:48,240 --> 00:26:52,074
节点，指针，新的平等
MALLOC一个节点的大小

519
00:26:52,074 --> 00:26:53,740
因为我们要创建的节点。

520
00:26:53,740 --> 00:26:56,720
我们想要的量
内存节点占用

521
00:26:56,720 --> 00:26:59,300
将予配发的
创建新的节点。

522
00:26:59,300 --> 00:27:02,270
>> 然后我们要去检查
查看是否有新的equals等于空。

523
00:27:02,270 --> 00:27:03,370
还记得我们说什么？

524
00:27:03,370 --> 00:27:06,470
不管你的malloc，
要做就要你总是做什么？

525
00:27:06,470 --> 00:27:09,490
你必须经常检查，看看
无论是否是空。

526
00:27:09,490 --> 00:27:13,620
>> 例如，如果你的工作
系统完全​​满，

527
00:27:13,620 --> 00:27:17,060
如果你在没有更多的内存
所有你尝试的malloc，

528
00:27:17,060 --> 00:27:18,410
它会返回null为您服务。

529
00:27:18,410 --> 00:27:21,094
所以，如果你尝试使用它
当它指向空，

530
00:27:21,094 --> 00:27:23,260
你不打算能
来访问该信息。

531
00:27:23,260 --> 00:27:27,010
所以，正因为如此，我们希望使
相信只要你mallocing，

532
00:27:27,010 --> 00:27:30,500
你总是检查，如果看到
给你的内存为空。

533
00:27:30,500 --> 00:27:33,670
如果不是，那么我们可以将
与我们的代码的其余部分。

534
00:27:33,670 --> 00:27:36,140
>> 所以，我们要
初始化新节点。

535
00:27:36,140 --> 00:27:39,050
我们要做新的n等于ñ。

536
00:27:39,050 --> 00:27:42,390
然后我们要做的
设置新的新指针

537
00:27:42,390 --> 00:27:46,900
为null，因为现在我们不这样做
想要的任何东西它指向。

538
00:27:46,900 --> 00:27:48,755
我们不知道在哪里
它会放你，

539
00:27:48,755 --> 00:27:50,630
然后，如果我们想
在头部插入，

540
00:27:50,630 --> 00:27:53,820
那么我们就可以重新分配
指针的头部。

541
00:27:53,820 --> 00:27:58,530
每个人都遵循的逻辑
在那里发生的事情？

542
00:27:58,530 --> 00:28:02,502
>> 我们所要做的是创建一个新的
节点，设置指针为空，

543
00:28:02,502 --> 00:28:04,210
然后重新分配
它的头部，如果我们

544
00:28:04,210 --> 00:28:06,320
知道我们要在头部，将其插入。

545
00:28:06,320 --> 00:28:09,420
然后将头是要
指向新的节点。

546
00:28:09,420 --> 00:28:11,060
每个人都与该行吗？

547
00:28:11,060 --> 00:28:12,380
>> 所以这是一个两步过程。

548
00:28:12,380 --> 00:28:14,760
你必须先分配
无论你正在创建。

549
00:28:14,760 --> 00:28:18,260
设置指针到
引用，然后你

550
00:28:18,260 --> 00:28:21,400
能种非关联化
第一个指针

551
00:28:21,400 --> 00:28:22,972
并指出其向新的节点。

552
00:28:22,972 --> 00:28:25,680
不管你想要去插入，
该逻辑要成立。

553
00:28:25,680 --> 00:28:27,530
>> 这有点像分配
临时变量。

554
00:28:27,530 --> 00:28:28,700
请记住，你已经有了
确保你

555
00:28:28,700 --> 00:28:30,346
不要失去跟踪，如果你换了。

556
00:28:30,346 --> 00:28:33,470
你要确保你有一个
那种保持临时变量

557
00:28:33,470 --> 00:28:35,620
轨道，其中那些事儿
存储，让你

558
00:28:35,620 --> 00:28:41,190
不丢失任何价值的过程
像瞎搞吧。

559
00:28:41,190 --> 00:28:42,710
>> OK，这样的代码将出现在这里。

560
00:28:42,710 --> 00:28:45,020
你们采取部分后的样子。

561
00:28:45,020 --> 00:28:48,060
它会在那里。

562
00:28:48,060 --> 00:28:50,280
>> 所以我想如何做
这种差异，如果我们想要

563
00:28:50,280 --> 00:28:52,300
插入到中间或结束？

564
00:28:52,300 --> 00:28:57,892
有没有人有什么想法
伪代码作为逻辑参照

565
00:28:57,892 --> 00:29:00,350
我们将采取如果我们想要
将其插入中间？

566
00:29:00,350 --> 00:29:03,391
因此，如果我们想在将其插入
头，我们所要做的就是创建一个新的节点。

567
00:29:03,391 --> 00:29:06,311
我们设定的指针
新节点的任何头部，

568
00:29:06,311 --> 00:29:08,310
然后我们设置了头
新的节点，对不对？

569
00:29:08,310 --> 00:29:11,560
如果我们想将其插入到中间
名单，你会我们有什么关系？

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> 听众：它仍然
是类似的过程

572
00:29:16,110 --> 00:29:19,114
像分配指针
然后，指派该指针，

573
00:29:19,114 --> 00:29:20,530
但我们必须找到那里。

574
00:29:20,530 --> 00:29:23,560
>> ANDI鹏：没错，所以完全
但你同样的过程

575
00:29:23,560 --> 00:29:27,820
必须找到在什么地方你
希望该新指针进入，

576
00:29:27,820 --> 00:29:44,790
所以如果我要插入到
中间的链接列表中 - 确定，

577
00:29:44,790 --> 00:29:46,370
让我们说这是我们的链表。

578
00:29:46,370 --> 00:29:49,500
如果我们想，就在这里插，
我们要创建一个新的节点。

579
00:29:49,500 --> 00:29:50,520
我们要去的malloc。

580
00:29:50,520 --> 00:29:52,220
我们要创建一个新的节点。

581
00:29:52,220 --> 00:29:55,940
我们将分配
指针在这里这个节点。

582
00:29:55,940 --> 00:29:58,335
>> 但问题是不同
从其中头部是

583
00:29:58,335 --> 00:30:00,490
是，我们确切地知道
其中头。

584
00:30:00,490 --> 00:30:01,930
这是正确的，在第一次，对吗？

585
00:30:01,930 --> 00:30:04,870
但在这里，我们一定要保持跟踪
在那里我们将其插入。

586
00:30:04,870 --> 00:30:07,930
如果我们插入我们
在此节点，我们有

587
00:30:07,930 --> 00:30:12,270
以确保该
一个先前到该节点

588
00:30:12,270 --> 00:30:14,172
是一个重新分配的指针。

589
00:30:14,172 --> 00:30:16,380
所以，那么你必须种
跟踪两件事情。

590
00:30:16,380 --> 00:30:19,420
如果你跟踪，其中这
节点当前的插入。

591
00:30:19,420 --> 00:30:23,280
您还可以跟踪在哪里
那你看前面的节点

592
00:30:23,280 --> 00:30:24,340
也有。

593
00:30:24,340 --> 00:30:25,830
每个人都好有吗？

594
00:30:25,830 --> 00:30:26,500
好。

595
00:30:26,500 --> 00:30:28,000
>> 如何插入结束了吗？

596
00:30:28,000 --> 00:30:34,220
如果我想将其添加这里 - 如果我想
到一个新的节点添加到列表的末尾，

597
00:30:34,220 --> 00:30:37,009
怎么可能我去这样做？

598
00:30:37,009 --> 00:30:39,300
听众：那么目前，
最后一个人指着空。

599
00:30:39,300 --> 00:30:40,960
ANDI彭：是的。

600
00:30:40,960 --> 00:30:43,560
没错，所以这一块
目前指向知道，

601
00:30:43,560 --> 00:30:46,720
所以我想，在这个意义上，它是
很容易添加到列表的末尾。

602
00:30:46,720 --> 00:30:51,810
所有你需要做的是设置
等于空，然后繁荣。

603
00:30:51,810 --> 00:30:53,070
就在那里，很容易。

604
00:30:53,070 --> 00:30:53,960
很简单。

605
00:30:53,960 --> 00:30:56,430
>> 非常相似的
头，但在逻辑上你

606
00:30:56,430 --> 00:30:59,690
想确保该步骤
你迈出做任何的这个，

607
00:30:59,690 --> 00:31:01,500
您关注的沿。

608
00:31:01,500 --> 00:31:04,420
这是很容易的，在中间
你的代码，陷入上，

609
00:31:04,420 --> 00:31:05,671
哦，我有这么多的三分球。

610
00:31:05,671 --> 00:31:07,461
我不知道在哪里
任何指向。

611
00:31:07,461 --> 00:31:09,170
我甚至不知道我在哪个节点。

612
00:31:09,170 --> 00:31:11,490
这是怎么回事？

613
00:31:11,490 --> 00:31:13,620
>> 放松，平静下来，深呼吸。

614
00:31:13,620 --> 00:31:15,530
绘制出你的链接列表。

615
00:31:15,530 --> 00:31:18,800
如果你说，我知道在什么地方
我需要插入到这

616
00:31:18,800 --> 00:31:22,970
我知道如何重新分配我
指针，多，更容易图片

617
00:31:22,970 --> 00:31:27,200
out--多，更容易不
迷失在你的代码的漏洞。

618
00:31:27,200 --> 00:31:29,410
每个人都与该行吗？

619
00:31:29,410 --> 00:31:31,380
好。

620
00:31:31,380 --> 00:31:35,120
>> 所以我想一个概念，我们还没有
真之前谈到现在，

621
00:31:35,120 --> 00:31:38,131
我猜你可能
不会遇到太大yet--

622
00:31:38,131 --> 00:31:40,880
它是一种先进的concept--
是，我们其实有一个数据

623
00:31:40,880 --> 00:31:43,900
结构，称为一个双向链表。

624
00:31:43,900 --> 00:31:46,390
所以当你们看到的，
所有我们正在做的是创造

625
00:31:46,390 --> 00:31:50,400
一个实际值，额外
指针在我们每个节点

626
00:31:50,400 --> 00:31:52,660
也指向前一个节点。

627
00:31:52,660 --> 00:31:58,170
因此，我们不仅有我们的
节点指向下一个。

628
00:31:58,170 --> 00:32:01,430
他们还指出，前一个。

629
00:32:01,430 --> 00:32:04,310
我将忽略这两个现在。

630
00:32:04,310 --> 00:32:06,740
>> 所以，那么你有一个链
可以移动两种方式，

631
00:32:06,740 --> 00:32:09,630
然后它是一个更容易一些
从逻辑上跟随。

632
00:32:09,630 --> 00:32:11,896
喜欢这里，而不是
饲养的，哦轨道，我

633
00:32:11,896 --> 00:32:14,520
要知道，这个节点是
一个，我不得不重新分配，

634
00:32:14,520 --> 00:32:17,532
我可以去这里
只是拉前面的。

635
00:32:17,532 --> 00:32:19,490
后来我知道确切位置
也就是说，然后你

636
00:32:19,490 --> 00:32:21,130
不必遍历
整体链表。

637
00:32:21,130 --> 00:32:22,180
这是一个更容易一些。

638
00:32:22,180 --> 00:32:24,960
>> 但正因为如此，你必须加倍
指针的量，

639
00:32:24,960 --> 00:32:26,960
这是内存的两倍。

640
00:32:26,960 --> 00:32:28,950
这是一个很大的指针跟踪。

641
00:32:28,950 --> 00:32:32,140
这是一个有点复杂，但它的
多一点人性视

642
00:32:32,140 --> 00:32:34,080
你试图完成什么。

643
00:32:34,080 --> 00:32:36,910
>> 所以这种类型的数据
结构完全存在，

644
00:32:36,910 --> 00:32:40,280
和结构是非常非常
简单以外的所有你遇到的，

645
00:32:40,280 --> 00:32:43,850
而不只是一个指向下，
你也有一个指针以前。

646
00:32:43,850 --> 00:32:45,940
这就是差异。

647
00:32:45,940 --> 00:32:47,740
每个人都好有吗？

648
00:32:47,740 --> 00:32:48,240
凉。

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> 好了，所以现在我
要真正花可能

651
00:32:53,280 --> 00:32:56,870
像15至20分钟或散装
在节剩下的时间中

652
00:32:56,870 --> 00:32:58,360
谈论哈希表。

653
00:32:58,360 --> 00:33:02,590
有多少你们的
已经阅读pset5规范呢？

654
00:33:02,590 --> 00:33:03,620
好了，好了。

655
00:33:03,620 --> 00:33:06,160
这比通常的50％以上。

656
00:33:06,160 --> 00:33:07,560
好的。

657
00:33:07,560 --> 00:33:10,345
>> 所以当你们将会看到，
你在pset5挑战

658
00:33:10,345 --> 00:33:16,790
将实施字典
在这里装载了14万字

659
00:33:16,790 --> 00:33:20,610
我们给你和拼写检查
这对所有的文字。

660
00:33:20,610 --> 00:33:22,580
我们会给你随机
文学作品的。

661
00:33:22,580 --> 00:33:23,520
我们会给你奥德赛。

662
00:33:23,520 --> 00:33:24,561
我们会给你伊利亚特。

663
00:33:24,561 --> 00:33:26,350
我们会给你王牌大贱谍。

664
00:33:26,350 --> 00:33:28,220
>> 而你的挑战
将是拼写检查

665
00:33:28,220 --> 00:33:31,760
在所有的每一个字
这些字典

666
00:33:31,760 --> 00:33:34,960
本质上与我们的拼写检查器。

667
00:33:34,960 --> 00:33:38,620
所以有几部分组成
创建这个PSET的，

668
00:33:38,620 --> 00:33:41,970
首先你想成为
能够实际加载

669
00:33:41,970 --> 00:33:43,970
所有的话到您的
字典，然后你

670
00:33:43,970 --> 00:33:45,530
希望能够
拼写检查所有的人。

671
00:33:45,530 --> 00:33:48,780
所以，正因为如此，你将需要
一个数据结构可以做到这一点快

672
00:33:48,780 --> 00:33:50,790
并有效地和动态。

673
00:33:50,790 --> 00:33:52,900
>> 所以我想最简单的
办法做到这一点，你

674
00:33:52,900 --> 00:33:55,010
可能会创建一个数组，对不对？

675
00:33:55,010 --> 00:33:58,910
存储的最简单的方法就是你
可以创造14万字的数组

676
00:33:58,910 --> 00:34:03,400
而只是把它们都在那里和
然后通过二进制搜索遍历他们

677
00:34:03,400 --> 00:34:06,780
或者通过选择或不是 - 
遗憾的是真实的排序。

678
00:34:06,780 --> 00:34:10,729
你可以对它们进行排序，然后遍历它们
由二进制搜索或者只是线性搜索

679
00:34:10,729 --> 00:34:13,730
和公正的最后的话，但
需要大量的内存，

680
00:34:13,730 --> 00:34:15,190
这不是很有效。

681
00:34:15,190 --> 00:34:18,350
>> 因此，我们要开始
说起制作方法

682
00:34:18,350 --> 00:34:20,110
我们的运行时间更有效。

683
00:34:20,110 --> 00:34:23,190
而我们的目标是获得
定时间，其中

684
00:34:23,190 --> 00:34:25,810
这几乎就像阵列，其中
你有即时访问。

685
00:34:25,810 --> 00:34:28,560
如果我想搜索什么，
我希望能够公正，

686
00:34:28,560 --> 00:34:30,810
热潮，发现它完全，并将其拉出。

687
00:34:30,810 --> 00:34:34,100
等的结构，其中
我们将变得非常接近

688
00:34:34,100 --> 00:34:37,569
到能够访问恒定
当时，这圣杯

689
00:34:37,569 --> 00:34:41,370
在恒编程
时间被称为哈希表。

690
00:34:41,370 --> 00:34:45,370
于是大卫前面提到的
[听不清]在演讲一点点，

691
00:34:45,370 --> 00:34:49,100
但我们要真正
下潜深，本周

692
00:34:49,100 --> 00:34:51,780
对多数民众赞成有关一片
如何哈希表的工作原理。

693
00:34:51,780 --> 00:34:53,949
>> 这样的方式，一个散列
表作品，例如，

694
00:34:53,949 --> 00:35:00,230
如果我想存储一堆话，一
一堆英文单词的，

695
00:35:00,230 --> 00:35:02,940
我可以在理论上把
香蕉，苹果，猕猴桃，芒果，对，

696
00:35:02,940 --> 00:35:04,980
和哈密瓜所有的只是一个数组。

697
00:35:04,980 --> 00:35:07,044
他们都可以融入其中，并且被找到。

698
00:35:07,044 --> 00:35:09,210
这将会是一种痛苦来
通过搜索和访问，

699
00:35:09,210 --> 00:35:12,920
但这样做的更简单的方法是
我们实际上可以建立一个结构

700
00:35:12,920 --> 00:35:15,680
所谓的哈希表，其中我们的哈希值。

701
00:35:15,680 --> 00:35:19,880
我们通过运行所有的钥匙
散列函数，一个方程，

702
00:35:19,880 --> 00:35:22,600
这将它们全部纳入
某种形式的值

703
00:35:22,600 --> 00:35:28,740
那我们就可以存储到
链表基本上阵列。

704
00:35:28,740 --> 00:35:32,570
>> 所以在这里，如果我们想
存储英文单词，

705
00:35:32,570 --> 00:35:37,250
我们可能潜在只是，我不知道
知道了，把所有的第一个字母

706
00:35:37,250 --> 00:35:39,630
成某种形式的数目。

707
00:35:39,630 --> 00:35:43,140
因此，例如，如果我想
一个是同义词apple--

708
00:35:43,140 --> 00:35:47,460
或为0的索引，和
乙的同义词1，

709
00:35:47,460 --> 00:35:51,030
我们可以有26项
可以只是存储

710
00:35:51,030 --> 00:35:53,610
所有的字母
字母表，我们将开始。

711
00:35:53,610 --> 00:35:56,130
然后我们就可以有
苹果0的指数。

712
00:35:56,130 --> 00:35:59,160
我们的指数有香蕉
1，哈密瓜2的指数，

713
00:35:59,160 --> 00:36:00,540
等，等等。

714
00:36:00,540 --> 00:36:04,460
就这样，如果我想搜索
我的哈希表和访问苹果，

715
00:36:04,460 --> 00:36:07,560
我知道苹果开始
一个A，我确切地知道

716
00:36:07,560 --> 00:36:10,860
它必须是和散列
表索引0，因为

717
00:36:10,860 --> 00:36:13,620
函数的先前分配。

718
00:36:13,620 --> 00:36:16,572
>> 所以，我不知道，我们是
用户程序在哪里

719
00:36:16,572 --> 00:36:18,780
你将被控
arbitrarily--不要随意，

720
00:36:18,780 --> 00:36:22,530
与试图若有所思
想好方程

721
00:36:22,530 --> 00:36:25,460
要能传播
你所有的价值观

722
00:36:25,460 --> 00:36:29,370
在某种程度上，他们可以轻松地访问
后来在与像一个公式

723
00:36:29,370 --> 00:36:31,130
你，你自己，知道了。

724
00:36:31,130 --> 00:36:35,210
所以，在这个意义上，如果我想去
芒果，我知道，哦，它以M开头。

725
00:36:35,210 --> 00:36:37,134
它必须是12的索引处。

726
00:36:37,134 --> 00:36:38,800
我没有通过任何搜索。

727
00:36:38,800 --> 00:36:42,080
我知道exactly--我可以只去
12和指数拉出了这一点。

728
00:36:42,080 --> 00:36:45,520
>> 每个人都清楚如何
哈希表的功能的工作？

729
00:36:45,520 --> 00:36:48,380
这是一种只是一个更复杂的阵列。

730
00:36:48,380 --> 00:36:50,010
这就是它。

731
00:36:50,010 --> 00:36:51,630
好。

732
00:36:51,630 --> 00:36:57,690
>> 所以我想，我们碰到
这个问题是什么

733
00:36:57,690 --> 00:37:06,390
发生，如果您有多个事
这给你同样的指数？

734
00:37:06,390 --> 00:37:10,570
所以说我们的功能，所有这
做的是采取的第一个字母

735
00:37:10,570 --> 00:37:14,490
并把它转换成一个
相应的0至25指数。

736
00:37:14,490 --> 00:37:17,137
这是完全正常，如果
你只有每个之一。

737
00:37:17,137 --> 00:37:18,970
但第二启动
有更多的，你

738
00:37:18,970 --> 00:37:20,910
将有什么所谓的冲突。

739
00:37:20,910 --> 00:37:25,580
>> 所以，如果我尝试插入埋到一个哈希
表中已经有香蕉就可以了，

740
00:37:25,580 --> 00:37:27,870
有什么事情发生时，
您尝试插入呢？

741
00:37:27,870 --> 00:37:30,930
坏事情，因为香蕉
在索引中已存在

742
00:37:30,930 --> 00:37:33,800
您希望将其存储研究。

743
00:37:33,800 --> 00:37:35,560
种浆果是喜欢啊，我该怎么办？

744
00:37:35,560 --> 00:37:37,080
我不知道哪里去了。

745
00:37:37,080 --> 00:37:38,410
我该如何解决呢？

746
00:37:38,410 --> 00:37:41,150
>> 等会有种你们
看到我们做这个棘手的事情

747
00:37:41,150 --> 00:37:44,810
在这里，我们实际上可以种
创建链接的列表中我们的阵列。

748
00:37:44,810 --> 00:37:46,840
这样一来，最简单的方法
思考这个问题，

749
00:37:46,840 --> 00:37:50,830
所有的哈希表是一个
数组链表。

750
00:37:50,830 --> 00:37:55,670
因此，在这个意义上说，必须
这个美丽的指针数组，

751
00:37:55,670 --> 00:37:58,740
然后在每个指针
该值，在该索引，

752
00:37:58,740 --> 00:38:00,740
可实际却指向其他的东西。

753
00:38:00,740 --> 00:38:05,720
所以你把所有这些不同的
链条脱落一个大阵。

754
00:38:05,720 --> 00:38:07,960
>> 所以在这里，如果我
要插入浆果，

755
00:38:07,960 --> 00:38:11,220
我知道，行，我要输入
它通过我的哈希函数。

756
00:38:11,220 --> 00:38:15,070
我将结束与指数
1，然后我将能够有

757
00:38:15,070 --> 00:38:20,410
此只是一小的子集
巨大的14万字的字典。

758
00:38:20,410 --> 00:38:24,220
然后，我来找找看
通过该1/26。

759
00:38:24,220 --> 00:38:27,910
>> 而这样的话我可以插入
之前或之后香蕉浆果

760
00:38:27,910 --> 00:38:28,820
在这种情况下？

761
00:38:28,820 --> 00:38:29,700
之后，对不对？

762
00:38:29,700 --> 00:38:33,920
所以，你会想
香蕉之后插入这个节点，

763
00:38:33,920 --> 00:38:36,667
所以你要插入
在该链接列表的尾部。

764
00:38:36,667 --> 00:38:38,500
我要回去
这一张幻灯片，

765
00:38:38,500 --> 00:38:40,680
所以你们可以看到
哈希函数的工作。

766
00:38:40,680 --> 00:38:43,980
>> 所以散列函数是这样的方程
你正在运行的一种输入

767
00:38:43,980 --> 00:38:46,940
通过获得任何指数
你希望它朝着分配。

768
00:38:46,940 --> 00:38:51,130
因此，在这个例子中，所有我们想要
做的是采取的第一个字母，

769
00:38:51,130 --> 00:38:55,890
把它转换成一个指数，那么我们
可以存储我们的散列函数在。

770
00:38:55,890 --> 00:39:00,160
所有我们在这里所做的是我们
转换的第一个字母。

771
00:39:00,160 --> 00:39:04,770
所以keykey [0]只是第​​一个字母
我们遇到的任何字符串，

772
00:39:04,770 --> 00:39:05,720
我们通过研究。

773
00:39:05,720 --> 00:39:09,740
我们要转换，要上，和
我们用大写字母A减去，

774
00:39:09,740 --> 00:39:11,740
因此，所有的做
给我们提供了一些

775
00:39:11,740 --> 00:39:13,670
在其中我们可以散列我们的价值观上。

776
00:39:13,670 --> 00:39:16,550
>> 然后，我们将
返回哈希模量的大小。

777
00:39:16,550 --> 00:39:19,340
要非常，非常小心
因为，从理论上说，在这里

778
00:39:19,340 --> 00:39:21,870
您的哈希值可以是无穷大。

779
00:39:21,870 --> 00:39:23,660
它可能只是去和和。

780
00:39:23,660 --> 00:39:26,080
这可能是一些非常，
真正大的价值，

781
00:39:26,080 --> 00:39:29,849
但因为你的哈希表
你已经创建只有26指数，

782
00:39:29,849 --> 00:39:31,890
你要确保你的
modulusing让你

783
00:39:31,890 --> 00:39:33,848
不run--它是相同的
为您的queue--事

784
00:39:33,848 --> 00:39:36,320
这样你就不会跑出
您的散列函数的底部。

785
00:39:36,320 --> 00:39:39,210
>> 你想换回来各地
在[听不清]时相同的方式

786
00:39:39,210 --> 00:39:41,750
你必须像一个非常，
非常大的信，你

787
00:39:41,750 --> 00:39:43,740
不想，要
刚跑出结束。

788
00:39:43,740 --> 00:39:46,948
这里同样的事情，你要确保
它不流失年底通过包装

789
00:39:46,948 --> 00:39:48,330
周围的表的顶部。

790
00:39:48,330 --> 00:39:50,530
所以，这只是一个很
简单的哈希函数。

791
00:39:50,530 --> 00:39:56,570
所有这一切确实是拿第一
不管我们输入的字母是

792
00:39:56,570 --> 00:40:01,660
并把它转换成一个索引
我们可以把我们的哈希表。

793
00:40:01,660 --> 00:40:05,450
>> 是啊，所以我之前说的，
我们解决冲突的方式

794
00:40:05,450 --> 00:40:09,330
在我们的哈希表有，
我们所说的，链接。

795
00:40:09,330 --> 00:40:13,860
所以，如果你试图插入多
字开头同样的事情，

796
00:40:13,860 --> 00:40:16,145
你将有一个哈希值。

797
00:40:16,145 --> 00:40:18,770
鳄梨和苹果，如果你
通过我们的散列函数运行它，

798
00:40:18,770 --> 00:40:21,450
将会给你
数相同，为0的数目。

799
00:40:21,450 --> 00:40:24,550
这样一来，我们的方式解决是
样的，我们实际上可以将它们链接

800
00:40:24,550 --> 00:40:27,010
通过链表在一起。

801
00:40:27,010 --> 00:40:29,600
>> 因此在这个意义上，
你们可以看样

802
00:40:29,600 --> 00:40:32,640
如何数据结构
我们已经预先设定

803
00:40:32,640 --> 00:40:35,870
像葡萄干链表样
可走到连成一片。

804
00:40:35,870 --> 00:40:38,860
然后你就可以创建远
更有效的数据结构

805
00:40:38,860 --> 00:40:43,350
可以处理更大的量
数据，动态调整不同

806
00:40:43,350 --> 00:40:44,870
您的需要。

807
00:40:44,870 --> 00:40:45,620
大家都清楚了吗？

808
00:40:45,620 --> 00:40:47,580
大家一种明确
在这里会发生什么？

809
00:40:47,580 --> 00:40:52,110
>> 如果我想insert--什么是
水果有，我不知道开始，

810
00:40:52,110 --> 00:40:54,726
B，比其他浆果，香蕉。

811
00:40:54,726 --> 00:40:55,710
>> 听众：黑莓。

812
00:40:55,710 --> 00:40:57,910
>> ANDI彭：黑莓，黑莓。

813
00:40:57,910 --> 00:41:00,530
哪里黑莓跑到这里？

814
00:41:00,530 --> 00:41:04,251
好了，我们实际上已经没有排序
这还没有，但理论上

815
00:41:04,251 --> 00:41:06,250
如果我们想有这样的
按字母顺序排列，

816
00:41:06,250 --> 00:41:07,944
应该在哪里黑莓何去何从？

817
00:41:07,944 --> 00:41:09,210
>> 听众：[听不清]

818
00:41:09,210 --> 00:41:11,100
>> ANDI鹏：没错，在这里后，对不对？

819
00:41:11,100 --> 00:41:14,950
但因为它是非常困难的
reorder--我想这是给你们。

820
00:41:14,950 --> 00:41:17,920
你们可以完全
实现任何你想要的。

821
00:41:17,920 --> 00:41:20,730
的更有效的方式
对这样做也许

822
00:41:20,730 --> 00:41:24,570
将是您的排序链接
列出按字母顺序，

823
00:41:24,570 --> 00:41:26,520
所以，当你
插入的事情，你想

824
00:41:26,520 --> 00:41:28,632
以确保将其插入
按字母顺序

825
00:41:28,632 --> 00:41:30,590
让那么当你
试图寻找他们，

826
00:41:30,590 --> 00:41:32,410
你不必穿越一切。

827
00:41:32,410 --> 00:41:35,290
你知道确切位置
它是，它更容易。

828
00:41:35,290 --> 00:41:39,100
>> 但是，如果你种得
东西随意穿插，

829
00:41:39,100 --> 00:41:41,420
你仍然会有
到反正遍历。

830
00:41:41,420 --> 00:41:44,990
所以，如果我想只
黑莓在这里插入

831
00:41:44,990 --> 00:41:47,470
我想搜索
它，我知道，哦，黑莓

832
00:41:47,470 --> 00:41:52,012
必须先从1的指数，所以我
认识瞬时只搜索1。

833
00:41:52,012 --> 00:41:53,970
然后，我可以种
遍历链表

834
00:41:53,970 --> 00:41:56,120
直到我到黑莓，
和then--是吗？

835
00:41:56,120 --> 00:41:59,550
>> 听众：如果你想create--
我想这样是一个非常简单的哈希

836
00:41:59,550 --> 00:42:00,050
功能。

837
00:42:00,050 --> 00:42:02,835
如果我们想做的事
多层，像的，

838
00:42:02,835 --> 00:42:05,870
好了，我们要分成
像所有字母文字

839
00:42:05,870 --> 00:42:09,040
然后再次喜欢上另一组
内的字母，

840
00:42:09,040 --> 00:42:11,715
在我们把如哈希
哈希表内的表，

841
00:42:11,715 --> 00:42:13,256
或者像函数中的一个函数？

842
00:42:13,256 --> 00:42:14,880
或者是that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI彭：所以，你的散列
function--你的哈希表

844
00:42:17,510 --> 00:42:19,360
因为你希望它可以大。

845
00:42:19,360 --> 00:42:21,930
因此，在这个意义上，我认为
这是非常容易的，很

846
00:42:21,930 --> 00:42:25,320
简单对我来说，只是排序依据
在第一个单词的字母。

847
00:42:25,320 --> 00:42:28,690
所以有唯一的26选项。

848
00:42:28,690 --> 00:42:32,650
我只能得到26选项
0至25，因为它们只能

849
00:42:32,650 --> 00:42:36,510
开始从A到Z，但如果你想
添加，或者，更复杂

850
00:42:36,510 --> 00:42:39,260
或更快的运行时间，以你的
哈希表，你绝对

851
00:42:39,260 --> 00:42:40,760
可以做各种各样的事情。

852
00:42:40,760 --> 00:42:43,330
你可以让你自己
公式，让你

853
00:42:43,330 --> 00:42:48,000
在更多的分销您
的话，那么当你搜索，

854
00:42:48,000 --> 00:42:49,300
这将更快。

855
00:42:49,300 --> 00:42:52,100
>> 这完全取决于你的家伙
要如何实现这一点。

856
00:42:52,100 --> 00:42:55,140
把它看成仅仅桶。

857
00:42:55,140 --> 00:42:57,376
如果我想有
26桶，我要去

858
00:42:57,376 --> 00:42:59,420
整理东西到这些水桶。

859
00:42:59,420 --> 00:43:02,980
但我将有一大堆
的东西在每个桶，

860
00:43:02,980 --> 00:43:05,890
所以如果你想让它
更快，更高效，

861
00:43:05,890 --> 00:43:07,190
让我有一百桶。

862
00:43:07,190 --> 00:43:09,290
>> 但你必须找出一个
这样的事情进行排序，使他们

863
00:43:09,290 --> 00:43:11,040
在适当的水桶他们应该研究。

864
00:43:11,040 --> 00:43:13,331
但是当你真正
想看看那个桶，

865
00:43:13,331 --> 00:43:16,410
它的速度快了很多，因为有
在每个桶少的东西。

866
00:43:16,410 --> 00:43:20,250
所以，是的，这其实
的伎俩你们在pset5

867
00:43:20,250 --> 00:43:22,360
是，你会
面临的挑战是只创建

868
00:43:22,360 --> 00:43:26,170
什么是最有效的
功能，你能想到的是

869
00:43:26,170 --> 00:43:28,520
能够存储和查询这些值。

870
00:43:28,520 --> 00:43:30,840
>> 完全取决于你们
然而，要做到这一点，

871
00:43:30,840 --> 00:43:32,229
但是这是一个非常好的点。

872
00:43:32,229 --> 00:43:34,520
那什么逻辑你
要开始思考

873
00:43:34,520 --> 00:43:37,236
是，好了，我为什么不赚更多的桶。

874
00:43:37,236 --> 00:43:39,527
然后，我要搜索
更少的东西，然后也许我

875
00:43:39,527 --> 00:43:41,640
有一个不同的哈希函数。

876
00:43:41,640 --> 00:43:45,500
>> 是啊，有很多方法可以做到这一点
PSET，有些人比别人快。

877
00:43:45,500 --> 00:43:50,630
我完全将只是看看
快速是最快你们会

878
00:43:50,630 --> 00:43:55,170
能够得到您的功能才能生效。

879
00:43:55,170 --> 00:43:58,176
OK，每个人都好于
链接和哈希表？

880
00:43:58,176 --> 00:44:00,800
它实际上是一个非常简单的
概念，如果你想想看。

881
00:44:00,800 --> 00:44:05,160
所有这是区分什么
您的输入是成桶，

882
00:44:05,160 --> 00:44:10,670
对它们进行排序，然后搜索
列出了还有的关联。

883
00:44:10,670 --> 00:44:11,852
>> 凉。

884
00:44:11,852 --> 00:44:18,160
好了，现在我们有一个不同的排序
数据结构，这就是所谓的一棵树。

885
00:44:18,160 --> 00:44:20,850
让我们去谈谈尝试
这是明显不同的，

886
00:44:20,850 --> 00:44:22,330
但在同一类别。

887
00:44:22,330 --> 00:44:29,010
从本质上讲，所有的一棵树，而不是
对组织数据以线性方式

888
00:44:29,010 --> 00:44:32,560
一个哈希表does--您
知道的，它有一个顶部和一个底部

889
00:44:32,560 --> 00:44:37,900
然后你有种链接关闭它 - 一对
树有你所说的根上面，

890
00:44:37,900 --> 00:44:40,220
然后它有它周围的叶子。

891
00:44:40,220 --> 00:44:42,390
>> 所以，你在这里
仅仅是顶节点

892
00:44:42,390 --> 00:44:45,980
指向其他节点，该点
到更多的节点，依此类推等等。

893
00:44:45,980 --> 00:44:48,130
所以你就必须拆分分支机构。

894
00:44:48,130 --> 00:44:53,255
这是组织的只是以不同的方式
数据，因为我们把它称为一棵树，

895
00:44:53,255 --> 00:44:56,270
你们just--这只是
模拟出看起来像一棵树。

896
00:44:56,270 --> 00:44:57,670
这就是为什么我们把它叫做树。

897
00:44:57,670 --> 00:44:59,370
>> 哈希表看起来像一个表。

898
00:44:59,370 --> 00:45:01,310
树看起来就像一棵树。

899
00:45:01,310 --> 00:45:03,300
所有这是一个独立的
节点组织方式

900
00:45:03,300 --> 00:45:06,020
根据你的需求是什么。

901
00:45:06,020 --> 00:45:11,810
>> 所以，你有一个根，
那么你有叶子。

902
00:45:11,810 --> 00:45:15,380
该办法，我们可以特别
想想这是一个二叉树，

903
00:45:15,380 --> 00:45:18,150
二叉树只是一个
树的特定类型

904
00:45:18,150 --> 00:45:22,450
其中每个节点仅分
于，在最大，其他两个节点。

905
00:45:22,450 --> 00:45:25,434
所以，在这里你有不同的
对称性在你的树

906
00:45:25,434 --> 00:45:28,600
这使得一种更加便捷地查询
在什么样的价值观，你是因为你

907
00:45:28,600 --> 00:45:30,150
始终左或右。

908
00:45:30,150 --> 00:45:33,150
从未有像从左侧第三
向左或从左侧的第四。

909
00:45:33,150 --> 00:45:36,358
这只是你有左，右
你可以搜索上述两种的。

910
00:45:36,358 --> 00:45:38,980
所以这是为什么有用吗？

911
00:45:38,980 --> 00:45:40,980
的方式，这是
有用的是，如果你正在寻找

912
00:45:40,980 --> 00:45:42,890
通过值来搜索，对不对？

913
00:45:42,890 --> 00:45:45,640
而不是执行二进制
在一个错误数组搜索，

914
00:45:45,640 --> 00:45:49,260
如果你想成为能够插入节点
并带走节点的意愿，也

915
00:45:49,260 --> 00:45:52,185
保存搜索
二进制搜索的能力。

916
00:45:52,185 --> 00:45:54,560
因此，在这种方式中，我们是那种
tricking--记得当时我们

917
00:45:54,560 --> 00:45:56,530
说链表不能二进制搜索？

918
00:45:56,530 --> 00:46:01,700
样的，我们正在创建一个数据结构
该技巧，进入工作。

919
00:46:01,700 --> 00:46:05,034
>> 所以因为链表是线性的，
它们只能链接一前一后。

920
00:46:05,034 --> 00:46:06,950
那种我们可以有
不同类型的指针

921
00:46:06,950 --> 00:46:09,408
该点不同的节点
这可以帮助我们与搜索。

922
00:46:09,408 --> 00:46:12,590
所以在这里，如果我想
有一个二进制搜索树，

923
00:46:12,590 --> 00:46:14,090
我知道，我的中间，如果55。

924
00:46:14,090 --> 00:46:18,280
我只是要创建
因为我的中间，因为我的根，

925
00:46:18,280 --> 00:46:20,770
然后我将有
值剥离它。

926
00:46:20,770 --> 00:46:25,610
>> 所以在这里，如果我要去寻找
66的价值，我可以在55开始。

927
00:46:25,610 --> 00:46:27,310
这比55 66更高？

928
00:46:27,310 --> 00:46:30,970
的确是这样，所以我知道我每亩搜索
I N这棵树的右指针。

929
00:46:30,970 --> 00:46:32,440
我去77。

930
00:46:32,440 --> 00:46:35,367
行，是66小于或大于77？

931
00:46:35,367 --> 00:46:37,950
它的不足，所以你知道，哦，
具有是左节点。

932
00:46:37,950 --> 00:46:41,410
>> 所以，我们在这里种保护
所有有关数组伟大的事情，

933
00:46:41,410 --> 00:46:44,420
所以像动态调整
的对象，是

934
00:46:44,420 --> 00:46:49,530
能够插入和删除随意，
而不必担心固定

935
00:46:49,530 --> 00:46:50,370
量的空间。

936
00:46:50,370 --> 00:46:52,820
我们仍然保留所有的
那些美好的事物

937
00:46:52,820 --> 00:46:57,140
同时还能够保存
登录并搜索二进制搜索的时间

938
00:46:57,140 --> 00:47:00,450
我们只是以前
能够得到一个短语。

939
00:47:00,450 --> 00:47:06,310
>> 酷派数据结构，种
复杂的实现，该节点。

940
00:47:06,310 --> 00:47:08,311
正如你所看到的，它
是节点的结构

941
00:47:08,311 --> 00:47:10,143
是，你有一个左
和一个右指针。

942
00:47:10,143 --> 00:47:11,044
这就是它。

943
00:47:11,044 --> 00:47:12,960
因此，而不是仅仅
具有一个X或先前。

944
00:47:12,960 --> 00:47:15,920
你有一个左或右，然后
有种你可以将它们链接在一起

945
00:47:15,920 --> 00:47:16,836
然而，你选择。

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK，我们实际上会
只需要几分钟的时间。

948
00:47:24,270 --> 00:47:25,790
所以我们要回去这里。

949
00:47:25,790 --> 00:47:28,270
正如我以前说过，
我种解释

950
00:47:28,270 --> 00:47:31,520
后面我们如何逻辑
通过这样做搜索。

951
00:47:31,520 --> 00:47:33,860
我们要尝试
pseudocoding了这一点，看看

952
00:47:33,860 --> 00:47:38,000
样的，如果我们可以应用
二进制搜索的同样的逻辑

953
00:47:38,000 --> 00:47:40,055
到不同类型的数据结构。

954
00:47:40,055 --> 00:47:45,049
如果你们想采取像情侣
分钟，只是想想这一点。

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
好。

957
00:48:46,925 --> 00:48:51,407
好吧，我要去
其实只是给你the--没有，

958
00:48:51,407 --> 00:48:52,990
我们将谈论的伪代码第一位。

959
00:48:52,990 --> 00:48:56,580
因此，没有人想
给刺伤了什么

960
00:48:56,580 --> 00:49:02,100
你想要做的时候第一件事情
你开始搜索？

961
00:49:02,100 --> 00:49:04,460
如果我们正在寻找
66的价值，什么是

962
00:49:04,460 --> 00:49:07,940
我们想要做的，如果第一件事
我们要的二进制搜索这棵树？

963
00:49:07,940 --> 00:49:10,760
>> 听众：你想要看的权利
看看左边，看到[听不清]

964
00:49:10,760 --> 00:49:11,230
更大的数字。

965
00:49:11,230 --> 00:49:12,271
>> ANDI彭：是的，没错。

966
00:49:12,271 --> 00:49:15,350
所以，你要看看你的根。

967
00:49:15,350 --> 00:49:18,180
有很多方法可以调用
它，你的父节点的人说。

968
00:49:18,180 --> 00:49:21,317
我想说的根因
这就像树的根。

969
00:49:21,317 --> 00:49:23,400
你要看看
你的根节点，而你

970
00:49:23,400 --> 00:49:26,940
要看到的是66更大
大于或小于55。

971
00:49:26,940 --> 00:49:30,360
而如果它是大于，很好，这是
大于，在这里我们想看看吗？

972
00:49:30,360 --> 00:49:32,000
我们在哪里现在要进行搜索，对不对？

973
00:49:32,000 --> 00:49:34,340
我们要搜索
这种树的右半边。

974
00:49:34,340 --> 00:49:38,390
>> 因此，我们有，方便，一
指针指向右侧。

975
00:49:38,390 --> 00:49:44,325
而这样的话，我们可以设置
我们新的根是77。

976
00:49:44,325 --> 00:49:46,450
我们可以去到哪里
指针指向。

977
00:49:46,450 --> 00:49:49,100
嗯，哦，在这里我们开始
77，我们可以只

978
00:49:49,100 --> 00:49:51,172
递归一次又一次做到这一点。

979
00:49:51,172 --> 00:49:52,880
通过这种方式，你有种
的有一个功能。

980
00:49:52,880 --> 00:49:57,430
你有搜索你的一种方式
只需重复一遍又一遍又一遍，

981
00:49:57,430 --> 00:50:02,720
这取决于你想看看
直到你最终得到的值

982
00:50:02,720 --> 00:50:04,730
您正在搜索。

983
00:50:04,730 --> 00:50:05,230
合理？

984
00:50:05,230 --> 00:50:07,800
>> 我要告诉你的实际
代码，这是一个很大的代码。

985
00:50:07,800 --> 00:50:08,674
没有必要惊慌。

986
00:50:08,674 --> 00:50:09,910
我们将讨论通过它。

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> 当然没有。

989
00:50:14,020 --> 00:50:15,061
这只是伪代码。

990
00:50:15,061 --> 00:50:17,860
好了，这仅仅是伪代码，
这是一个有点复杂，

991
00:50:17,860 --> 00:50:19,751
但它完全罚款。

992
00:50:19,751 --> 00:50:21,000
下面大家一起在这里吗？

993
00:50:21,000 --> 00:50:24,260
如果根是空的，回报
假的，因为这意味着

994
00:50:24,260 --> 00:50:26,850
你甚至不用任何那里。

995
00:50:26,850 --> 00:50:31,376
>> 如果根n是价值，因此，如果
恰好是你看一，

996
00:50:31,376 --> 00:50:34,000
那么你要返回true
因为你知道你发现了它。

997
00:50:34,000 --> 00:50:36,250
但如果该值小于
小于n的根，你

998
00:50:36,250 --> 00:50:38,332
要搜索左
子或左叶，

999
00:50:38,332 --> 00:50:39,540
无论你怎么称呼它。

1000
00:50:39,540 --> 00:50:41,750
并且如果该值大于根，
你要寻找合适的树，

1001
00:50:41,750 --> 00:50:44,610
然后只需运行功能
通过搜索一次。

1002
00:50:44,610 --> 00:50:48,037
>> 如果根是空的，这是
意味着你已经走到了尽头？

1003
00:50:48,037 --> 00:50:50,120
这意味着你没有
更多更多的叶子进行搜索，

1004
00:50:50,120 --> 00:50:52,230
那么你知道，哦，我
猜想这是不是在这里

1005
00:50:52,230 --> 00:50:55,063
因为此前我已经通过看
整个事情，它是不是在这里，

1006
00:50:55,063 --> 00:50:56,930
它只是可能不会在这里。

1007
00:50:56,930 --> 00:50:58,350
>> 这是否有意义给大家？

1008
00:50:58,350 --> 00:51:03,230
所以，它就像二进制搜索保存
链表的功能。

1009
00:51:03,230 --> 00:51:09,200
凉，所以第二类型
数据结构，你们的

1010
00:51:09,200 --> 00:51:13,180
可以尝试实现你的PSET，
你只需要选择一种方法。

1011
00:51:13,180 --> 00:51:19,430
但是，也许是一个替代方法
哈希表就是我们所说的一个线索。

1012
00:51:19,430 --> 00:51:24,080
>> 所有的一个线索是一个
树的特定类型

1013
00:51:24,080 --> 00:51:28,600
有一个去其他值的值。

1014
00:51:28,600 --> 00:51:31,450
所以具有代替二进制
树在这个意义上，只有一个

1015
00:51:31,450 --> 00:51:35,940
东西可以指向两个，可以有
一件事情点很多很多的东西。

1016
00:51:35,940 --> 00:51:39,450
本质上，阵列
其中你店内

1017
00:51:39,450 --> 00:51:41,790
指针指向其他阵列。

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> 那么我们如何在节点
将定义一个线索

1020
00:51:49,460 --> 00:51:52,590
就是我们希望有一个
布尔，C字，对吧？

1021
00:51:52,590 --> 00:51:54,920
所以该节点是布尔
像真的还是假的，

1022
00:51:54,920 --> 00:51:58,490
首先在头
该数组，这句话吗？

1023
00:51:58,490 --> 00:52:03,620
其次，你想拥有指针
到任何人，其余都是。

1024
00:52:03,620 --> 00:52:07,470
一个有点复杂，有点抽象，但
我将解释那是什么一切手段。

1025
00:52:07,470 --> 00:52:13,800
>> 因此，这里，在顶部，如果
有一个数组已经声明，

1026
00:52:13,800 --> 00:52:17,040
在这里你有一个布尔节点
存储在前面的值

1027
00:52:17,040 --> 00:52:19,490
告诉你的是这句话吗？

1028
00:52:19,490 --> 00:52:20,520
这难道不是一个字？

1029
00:52:20,520 --> 00:52:23,240
然后你有
阵列的其余部分的

1030
00:52:23,240 --> 00:52:26,040
实际存储所有的
什么可能是可能。

1031
00:52:26,040 --> 00:52:28,660
因此，举例来说，像
顶部有

1032
00:52:28,660 --> 00:52:32,140
的第一件事，说真的还是
假，是或否，这是一个词。

1033
00:52:32,140 --> 00:52:38,130
>> 然后你有0到26
您可以存储的字母。

1034
00:52:38,130 --> 00:52:42,790
如果我想在这里搜索
对于蝙蝠，我去顶

1035
00:52:42,790 --> 00:52:49,200
我找B.我发现中的B我
数组，所以我知道，行，为B字？

1036
00:52:49,200 --> 00:52:53,010
B是不发一语，所以这样
我必须继续寻找。

1037
00:52:53,010 --> 00:52:56,410
我从B和我期待的
指针乙组分朝

1038
00:52:56,410 --> 00:53:00,900
我看到另一个信息阵列，
相同的结构，我们有过的。

1039
00:53:00,900 --> 00:53:05,240
>> 而这里 - 哦，下
信[听不清]是A.

1040
00:53:05,240 --> 00:53:07,210
因此，我们期待在该数组。

1041
00:53:07,210 --> 00:53:10,860
我们发现第八值，
然后我们来看看，看看，哦，

1042
00:53:10,860 --> 00:53:12,840
哎，就是一个字，是B-A字？

1043
00:53:12,840 --> 00:53:13,807
它不是一个字。

1044
00:53:13,807 --> 00:53:14,890
我们一定要继续寻找。

1045
00:53:14,890 --> 00:53:17,850
>> 所以接下来我们来看看哪里
的一个点的指针，

1046
00:53:17,850 --> 00:53:21,130
并且它指向的另一种方式
我们有更多的价值存储。

1047
00:53:21,130 --> 00:53:24,150
而最终，我们得到
B-A-T，它是一个字。

1048
00:53:24,150 --> 00:53:25,970
这样一来，下一次
你看，你会

1049
00:53:25,970 --> 00:53:30,850
有，是的，办理入住手续，
此布尔函数是真实的。

1050
00:53:30,850 --> 00:53:35,450
所以在这个意义上，我们是一种
具有数组的树。

1051
00:53:35,450 --> 00:53:39,890
>> 所以，你可以种向下搜索。

1052
00:53:39,890 --> 00:53:43,650
而不是散列函数，并且
通过链表分配值，

1053
00:53:43,650 --> 00:53:49,190
你可以实现一个
特里，搜索downwords。

1054
00:53:49,190 --> 00:53:50,850
真的，真的复杂的东西。

1055
00:53:50,850 --> 00:53:54,060
不容易想到，因为我很喜欢
随地吐痰，这么多的数据结构进行

1056
00:53:54,060 --> 00:53:58,710
你，但确实有种大家
理解这个逻辑的作品？

1057
00:53:58,710 --> 00:54:01,920
>> 嗯不错。

1058
00:54:01,920 --> 00:54:05,600
因此，B-A-T，然后
你要搜索。

1059
00:54:05,600 --> 00:54:07,940
你要去的下一次
看，哦，嘿嘿，这是真的，

1060
00:54:07,940 --> 00:54:09,273
因此，我知道这一定是一个字。

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> 同样的事情了动物园。

1063
00:54:13,770 --> 00:54:17,960
因此，这里的事情，现在，如果我们
想寻找动物园，现在，

1064
00:54:17,960 --> 00:54:20,780
目前动物园是不是
字我们的字典

1065
00:54:20,780 --> 00:54:25,300
因为，正如你们所看到的，
我们有一个布尔首位

1066
00:54:25,300 --> 00:54:28,590
返回true是在放大的末端。

1067
00:54:28,590 --> 00:54:30,430
我们有Z-O-O-M。

1068
00:54:30,430 --> 00:54:33,900
>> 所以在这里，我们实际上并不具备
这个词，动物园，在我们的字典

1069
00:54:33,900 --> 00:54:36,070
因为此复选框未选中。

1070
00:54:36,070 --> 00:54:39,540
因此，计算机不
知道动物园是一个字

1071
00:54:39,540 --> 00:54:42,430
因为我们已经一路
保存它，只有变焦这里

1072
00:54:42,430 --> 00:54:44,920
实际上有一个布尔值
一个已经变成事实。

1073
00:54:44,920 --> 00:54:49,380
因此，如果我们要插入的
一句话，动物园，为我们的字典，

1074
00:54:49,380 --> 00:54:51,770
我们怎么会去这样做？

1075
00:54:51,770 --> 00:54:55,960
什么是我们必须做的，以确保我们的
计算机知道的是Z-O-O是一个字

1076
00:54:55,960 --> 00:54:58,130
而不是第一个字为Z-O-O-M？

1077
00:54:58,130 --> 00:54:59,360
>> 听众：[听不清]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI鹏：没错，我们
要确保这

1079
00:55:01,450 --> 00:55:07,890
这里，该布尔值是
检查过，这是真的。

1080
00:55:07,890 --> 00:55:13,297
Z-O-O，然后我们要去检查，
因此，我们确切地知道，哎，动物园是一个单词。

1081
00:55:13,297 --> 00:55:15,380
我要告诉
电脑，这是一个词，以便

1082
00:55:15,380 --> 00:55:18,000
计算机检查时，
它知道动物园是一个词。

1083
00:55:18,000 --> 00:55:21,269
>> 因为记住所有这些数据
结构，这很容易让我们

1084
00:55:21,269 --> 00:55:22,310
说，哦，蝙蝠的一个词。

1085
00:55:22,310 --> 00:55:22,851
动物园的一个词。

1086
00:55:22,851 --> 00:55:23,611
Zoom的一个词。

1087
00:55:23,611 --> 00:55:25,860
但是当你构建它，
电脑不知道。

1088
00:55:25,860 --> 00:55:28,619
>> 所以，你必须准确地告诉它
在什么时候，这是一个词？

1089
00:55:28,619 --> 00:55:29,910
在什么时候是它不是一个字？

1090
00:55:29,910 --> 00:55:31,784
而在什么时候做我
需要搜索事情，

1091
00:55:31,784 --> 00:55:34,000
和在什么时候，我需要去下一个？

1092
00:55:34,000 --> 00:55:37,010
每个人都清楚的是什么？

1093
00:55:37,010 --> 00:55:39,540
凉。

1094
00:55:39,540 --> 00:55:42,530
>> 因此然后是
的问题，我们怎么会

1095
00:55:42,530 --> 00:55:45,560
去插入的东西
这实际上不是吗？

1096
00:55:45,560 --> 00:55:49,090
所以，我们只能说，我们要插入
这个词，洗澡，到我们的线索。

1097
00:55:49,090 --> 00:55:53,589
正如你们可以看到像目前
所有我们现在已经是B-A-T，

1098
00:55:53,589 --> 00:55:55,630
和这个新的数据结构
曾有一品脱的

1099
00:55:55,630 --> 00:55:59,740
指着空，因为我们假设
即，哦，还有后B-A-T没有的话，

1100
00:55:59,740 --> 00:56:02,530
为什么我们需要保持
该T之后有东西

1101
00:56:02,530 --> 00:56:06,581
>> 但问题出现了，如果我们做的你
想有来后一个字

1102
00:56:06,581 --> 00:56:07,080
T的。

1103
00:56:07,080 --> 00:56:09,500
如果你有浴缸，你
会想要一个H的权利。

1104
00:56:09,500 --> 00:56:13,290
所以，我们要做到这一点的方法是
我们要创建一个单独的节点。

1105
00:56:13,290 --> 00:56:16,840
我们没有配发任何金额
内存为这个新阵，

1106
00:56:16,840 --> 00:56:20,720
而且我们要重新分配指针。

1107
00:56:20,720 --> 00:56:22,947
>> 我们将分配
H，首先，此空，

1108
00:56:22,947 --> 00:56:24,030
我们要摆脱。

1109
00:56:24,030 --> 00:56:26,590
我们将有
轰点向下。

1110
00:56:26,590 --> 00:56:30,600
如果我们看到一个H，我们希望它
去别的地方。

1111
00:56:30,600 --> 00:56:33,910
>> 在这里，我们可以勾选肯定。

1112
00:56:33,910 --> 00:56:38,170
如果我们的T后击中H，OH，
那么我们知道这是一个词。

1113
00:56:38,170 --> 00:56:41,110
布尔将会返回true。

1114
00:56:41,110 --> 00:56:42,950
每个人都清楚如何发生的？

1115
00:56:42,950 --> 00:56:45,110
好。

1116
00:56:45,110 --> 00:56:47,214
>> 所以基本上，所有的
这些数据结构

1117
00:56:47,214 --> 00:56:50,130
我们已经讨论了今天，我已经
走了过来他们真的，真的快

1118
00:56:50,130 --> 00:56:52,192
而不是在得多
细节，这就是确定。

1119
00:56:52,192 --> 00:56:53,900
一旦你开始搞乱
有了它，你会

1120
00:56:53,900 --> 00:56:55,733
保持在那里的轨道
所有的指针，

1121
00:56:55,733 --> 00:56:58,060
什么在事情你
数据结构，等等。

1122
00:56:58,060 --> 00:56:59,810
他们将是非常有用的，
它是由你

1123
00:56:59,810 --> 00:57:03,890
家伙完全弄清楚如何
你想实现的东西。

1124
00:57:03,890 --> 00:57:07,650
>> 因此pset4，5--哦，那是错误的。

1125
00:57:07,650 --> 00:57:10,140
Pset5是拼写错误。

1126
00:57:10,140 --> 00:57:13,710
正如我之前说的，你要去，一旦
再次，从我们这里下载源代码。

1127
00:57:13,710 --> 00:57:16,210
还有的将是三个主要的
事情你会被下载。

1128
00:57:16,210 --> 00:57:18,470
你会下载字典，
KERS和文本。

1129
00:57:18,470 --> 00:57:21,660
>> 所有这些东西都是有
无论是词词典

1130
00:57:21,660 --> 00:57:25,190
我们希望你检查
或信息测试

1131
00:57:25,190 --> 00:57:26,930
我们希望你能拼写检查。

1132
00:57:26,930 --> 00:57:29,670
这样一来，字典
我们给你准备

1133
00:57:29,670 --> 00:57:34,870
给你，我们要实际的话
你以某种方式存储的方式，是

1134
00:57:34,870 --> 00:57:36,530
比的阵列更有效。

1135
00:57:36,530 --> 00:57:38,470
然后将文本是
会是什么我们是

1136
00:57:38,470 --> 00:57:43,900
要求您进行拼写检查，以确保
所有的话有真实的话。

1137
00:57:43,900 --> 00:57:47,970
>> 对这样一来，三大板块
计划，我们会给你

1138
00:57:47,970 --> 00:57:51,130
被称为dictionary.c，
dictionary.h和speller.c。

1139
00:57:51,130 --> 00:57:56,500
因此所有dictionary.c确实是
你在要求执行。

1140
00:57:56,500 --> 00:57:57,880
它加载的话。

1141
00:57:57,880 --> 00:58:02,000
它拼写检查他们，并确保
一切都正确插入。

1142
00:58:02,000 --> 00:58:05,180
>> diction.h只是一个库文件
声明所有的这些功能​​。

1143
00:58:05,180 --> 00:58:07,650
而speller.c，我们打算给你。

1144
00:58:07,650 --> 00:58:09,290
你不需要修改任何它。

1145
00:58:09,290 --> 00:58:14,290
所有speller.c确实是拿去，
它装载，检查它的速度，

1146
00:58:14,290 --> 00:58:19,190
检验了怎么样的基准
很快你能够做到的事情。

1147
00:58:19,190 --> 00:58:20,410
>> 这是一个拼写检查。

1148
00:58:20,410 --> 00:58:23,920
只要不惹它，但要
确保你明白它在做什么。

1149
00:58:23,920 --> 00:58:28,090
我们用一个函数调用的getrusage的
测试你的法术性能

1150
00:58:28,090 --> 00:58:28,590
检查器。

1151
00:58:28,590 --> 00:58:32,200
它所做的基本测试
一切都在你的字典的时间，

1152
00:58:32,200 --> 00:58:33,680
所以一定要了解它。

1153
00:58:33,680 --> 00:58:36,660
注意不要乱用，或
否则事情将无法正常运行。

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> 而大宗这一挑战的是
你们真的修改dictionary.c。

1156
00:58:44,170 --> 00:58:48,526
我们打​​算给你
14万字的字典中。

1157
00:58:48,526 --> 00:58:50,900
我们将会给你一个文本
文件中有这些话，

1158
00:58:50,900 --> 00:58:54,840
我们希望你能够组织
成一个哈希表或字典树

1159
00:58:54,840 --> 00:58:58,140
因为当我们问你拼
check--想象一下，如果你的法术

1160
00:58:58,140 --> 00:59:00,690
检查像荷马的奥德赛。

1161
00:59:00,690 --> 00:59:03,010
这就像这个巨大的，巨大的考验。

1162
00:59:03,010 --> 00:59:05,190
>> 如果每一个想象
一句话，你不得不看

1163
00:59:05,190 --> 00:59:08,100
通过140,000值的数组。

1164
00:59:08,100 --> 00:59:10,350
这将采取永远
为您的机器上运行。

1165
00:59:10,350 --> 00:59:14,490
这就是为什么我们要组织我们
数据转换成更有效的数据结构

1166
00:59:14,490 --> 00:59:17,270
如哈希表或字典树。

1167
00:59:17,270 --> 00:59:20,700
然后你们可以种
当您搜索的访问

1168
00:59:20,700 --> 00:59:22,570
事情更容易，更快速。

1169
00:59:22,570 --> 00:59:24,934
>> 所以要小心，以解决冲突。

1170
00:59:24,934 --> 00:59:27,350
你会得到一堆
开头A的话

1171
00:59:27,350 --> 00:59:29,957
你会得到一堆话
开头B.由你

1172
00:59:29,957 --> 00:59:31,290
男人要如何解决它。

1173
00:59:31,290 --> 00:59:34,144
或许还有更多
高效的散列函数

1174
00:59:34,144 --> 00:59:36,810
比仅仅是第一信
一些东西，所以这是给你

1175
00:59:36,810 --> 00:59:38,190
样的人做任何你想要的。

1176
00:59:38,190 --> 00:59:40,148
>> 也许你想添加
所有的来信。

1177
00:59:40,148 --> 00:59:43,410
也许你想喜欢做奇怪的事情
到账户的字母数，

1178
00:59:43,410 --> 00:59:43,970
随你。

1179
00:59:43,970 --> 00:59:45,386
截至你们要如何做。

1180
00:59:45,386 --> 00:59:49,262
如果你想要做一个哈希表，如果你
想尝试一个线索，完全取决于你。

1181
00:59:49,262 --> 00:59:52,470
我会提前发出警告的时间的你
线索通常是有点困难

1182
00:59:52,470 --> 00:59:54,520
只是因为有很多
更多的指针来跟踪。

1183
00:59:54,520 --> 00:59:55,645
但是，完全取决于你们。

1184
00:59:55,645 --> 00:59:58,742
这是更有效
在大多数情况下。

1185
00:59:58,742 --> 01:00:01,450
你要真正能够保持
跟踪你所有的指针的。

1186
01:00:01,450 --> 01:00:03,850
像做同样的事情
我在这里做什么。

1187
01:00:03,850 --> 01:00:06,871
当你试图插入
值到一个哈希表或删除，

1188
01:00:06,871 --> 01:00:08,620
请确保你
真的跟踪

1189
01:00:08,620 --> 01:00:11,860
对这里的一切是因为
这是因为，如果我真的很容易

1190
01:00:11,860 --> 01:00:14,727
试图插入之类的词，安迪。

1191
01:00:14,727 --> 01:00:16,810
远的不说，这是一个
真正的字，词，刘德华，

1192
01:00:16,810 --> 01:00:19,640
成的话一个巨大的列表。

1193
01:00:19,640 --> 01:00:22,450
>> 如果我只是碰巧重新分配
指针错误，哎呀，

1194
01:00:22,450 --> 01:00:24,940
有去的全部
我的链接列表的其余部分。

1195
01:00:24,940 --> 01:00:26,897
现在唯一的一句话让我
已经是安迪，现在

1196
01:00:26,897 --> 01:00:29,230
所有的在该换言之
词典已经丢失。

1197
01:00:29,230 --> 01:00:31,370
所以你要确保你
跟踪所有的指针的

1198
01:00:31,370 --> 01:00:33,661
否则，你会得到
巨大的问题，在你的代码。

1199
01:00:33,661 --> 01:00:35,840
画的东西出来仔细一步一步来。

1200
01:00:35,840 --> 01:00:37,870
这使得它更容易想到的。

1201
01:00:37,870 --> 01:00:40,910
>> 最后，要能
测试你的程序的性能

1202
01:00:40,910 --> 01:00:41,618
在大板。

1203
01:00:41,618 --> 01:00:43,710
如果你们拿
看CS50现在，

1204
01:00:43,710 --> 01:00:45,210
我们有什么所谓的大板。

1205
01:00:45,210 --> 01:00:50,200
它是最快的评分表
在所有的CS50的拼写检查倍

1206
01:00:50,200 --> 01:00:55,720
现在，我觉得像10上方
有时，我觉得其中八是工作人员。

1207
01:00:55,720 --> 01:00:57,960
我们真的希望你们击败我们。

1208
01:00:57,960 --> 01:01:00,870
>> 我们所有的人都试图实现
最快的代码成为可能。

1209
01:01:00,870 --> 01:01:04,880
我们希望你们来尝试挑战
我们并实现比我们快

1210
01:01:04,880 --> 01:01:05,550
能够。

1211
01:01:05,550 --> 01:01:07,970
所以这是真的
第一次，我们是

1212
01:01:07,970 --> 01:01:12,680
要求你们做一个PSET的
你真的可以为所欲为方法

1213
01:01:12,680 --> 01:01:13,760
你想。

1214
01:01:13,760 --> 01:01:17,730
>> 我总是说，这是更接近
以现实生活中的解决方案，对吗？

1215
01:01:17,730 --> 01:01:19,550
我说，嘿，我需要你这样做。

1216
01:01:19,550 --> 01:01:21,380
建立一个程序，它为我。

1217
01:01:21,380 --> 01:01:22,630
做到这一点，但是你想要的。

1218
01:01:22,630 --> 01:01:24,271
我只知道，我要快。

1219
01:01:24,271 --> 01:01:25,770
这就是你的挑战，在这个星期。

1220
01:01:25,770 --> 01:01:27,531
你这家伙，我们要
给你一个任务。

1221
01:01:27,531 --> 01:01:29,030
我们将会给你一个挑战。

1222
01:01:29,030 --> 01:01:31,559
然后就看你们
完全只是弄清楚

1223
01:01:31,559 --> 01:01:34,100
什么是最快捷和最
有效的方式来实现这一点。

1224
01:01:34,100 --> 01:01:34,600
是吗？

1225
01:01:34,600 --> 01:01:37,476
>> 听众：我们是否允许，如果
要研究更快的方法

1226
01:01:37,476 --> 01:01:40,821
做哈希表在网上，我们可以做
这一点，引用别人的代码？

1227
01:01:40,821 --> 01:01:42,070
ANDI彭：是的，完全罚款。

1228
01:01:42,070 --> 01:01:44,320
所以，如果你们看
规范，有一条线

1229
01:01:44,320 --> 01:01:48,310
在规范中，说你们
完全自由地研究哈希

1230
01:01:48,310 --> 01:01:51,070
上有哪些功能
的更快的散列函数

1231
01:01:51,070 --> 01:01:54,720
通过为运行的东西
只要你引用的代码。

1232
01:01:54,720 --> 01:01:57,220
因此，一些人已经
想通了快速的方法

1233
01:01:57,220 --> 01:02:00,250
中做快速拼写检查器，
方式存储的信息。

1234
01:02:00,250 --> 01:02:02,750
完全取决于你的家伙，如果你
想只取了吧？

1235
01:02:02,750 --> 01:02:04,045
请确保您引用。

1236
01:02:04,045 --> 01:02:06,170
这里的挑战真的
我们正在试图测试

1237
01:02:06,170 --> 01:02:09,750
是确保你知道
你倒过来指针。

1238
01:02:09,750 --> 01:02:12,700
至于你实现
实际的散列函数

1239
01:02:12,700 --> 01:02:15,070
而未来与像
数学要做到这一点，

1240
01:02:15,070 --> 01:02:17,570
你们可以研究什么
方法在线你们想要的。

1241
01:02:17,570 --> 01:02:17,996
是吗？

1242
01:02:17,996 --> 01:02:19,700
>> 听众：我们能不能​​只举
使用[听不清]？

1243
01:02:19,700 --> 01:02:20,120
>> ANDI彭：是的。

1244
01:02:20,120 --> 01:02:22,328
你可以在你的评论，
你可以举出像，哦，

1245
01:02:22,328 --> 01:02:26,127
从亚达采取亚达，
亚达，哈希函数。

1246
01:02:26,127 --> 01:02:27,210
任何人有任何问题吗？

1247
01:02:27,210 --> 01:02:29,694
实际上，我们轻轻松松
通过板块今日。

1248
01:02:29,694 --> 01:02:31,610
我将在这里为
回答问题也是如此。

1249
01:02:31,610 --> 01:02:36,570
>> 此外，正如我所说，办公室
今晚和明天小时。

1250
01:02:36,570 --> 01:02:40,307
该规范在本周其实是
超级简单和超短期阅读。

1251
01:02:40,307 --> 01:02:43,140
我建议考虑看看，刚
阅读它的全部内容。

1252
01:02:43,140 --> 01:02:45,730
>> 而Zamyla实际上引导您
通过每个功能

1253
01:02:45,730 --> 01:02:49,796
你需要实现，所以它的
非常，非常清楚如何做的一切。

1254
01:02:49,796 --> 01:02:51,920
只是为了确保你
跟踪指针。

1255
01:02:51,920 --> 01:02:53,650
这是一个非常具有挑战性的pset。

1256
01:02:53,650 --> 01:02:56,744
>> 这不是挑战，因为喜欢，
哦，其概念是这么多

1257
01:02:56,744 --> 01:02:59,160
困难，或者你要学会
这么多新的语法方式

1258
01:02:59,160 --> 01:03:00,650
你做的最后PSET。

1259
01:03:00,650 --> 01:03:03,320
这PSET是困难的，因为
有这么多的三分球，

1260
01:03:03,320 --> 01:03:06,980
然后这是非常，非常容易，一旦
你在你的代码中的错误不能

1261
01:03:06,980 --> 01:03:08,315
找到该错误是。

1262
01:03:08,315 --> 01:03:13,200
>> 而如此完整和你绝对信心
家伙能够击败我们的[听不清]

1263
01:03:13,200 --> 01:03:13,700
拼写。

1264
01:03:13,700 --> 01:03:16,640
其实，我没有任何书面矿
然而，但我要写我的。

1265
01:03:16,640 --> 01:03:19,070
你写的，而因此
你，我会写我的。

1266
01:03:19,070 --> 01:03:21,070
我会尽量让
我的比你快。

1267
01:03:21,070 --> 01:03:23,940
我们将看到谁拥有最快的国家之一。

1268
01:03:23,940 --> 01:03:27,340
>> ，是的，我会看到所有的
你们在这里在星期二。

1269
01:03:27,340 --> 01:03:29,510
我将运行就像一个PSET车间一种。

1270
01:03:29,510 --> 01:03:32,640
所有部分的这
本周是PSET车间，

1271
01:03:32,640 --> 01:03:36,690
所以你们有很多机会
求助，办公时间一如既往，

1272
01:03:36,690 --> 01:03:41,330
我真的很期待
看完所有的人“的代码。

1273
01:03:41,330 --> 01:03:44,160
我测验在这里，如果你
你们要来得到这些。

1274
01:03:44,160 --> 01:03:45,880
就这样。

1275
01:03:45,880 --> 01:03:48,180