1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> 扬声器1：好吧，所以这是
CS50这是五个星期结束。

3
00:00:15,860 --> 00:00:19,220
而记得我们最后一次
开始寻找在票友数据

4
00:00:19,220 --> 00:00:22,310
即开始解决结构
问题，即开始引入

5
00:00:22,310 --> 00:00:25,640
新的问题，但关键就在这
是线程的排序，我们

6
00:00:25,640 --> 00:00:27,940
开始做从节点到节点。

7
00:00:27,940 --> 00:00:30,085
因此，这当然是
一个单向链表。

8
00:00:30,085 --> 00:00:31,960
而由单链表，
我的意思是只有一个

9
00:00:31,960 --> 00:00:33,380
每个这些节点之间线程。

10
00:00:33,380 --> 00:00:35,890
原来，你可以做票友
像双向链表

11
00:00:35,890 --> 00:00:38,470
因此，你有一个箭头
要在两个方向上，这

12
00:00:38,470 --> 00:00:40,320
可以帮助具有一定的效率。

13
00:00:40,320 --> 00:00:42,000
但这个问题是否解决？

14
00:00:42,000 --> 00:00:43,500
有什么问题没有解决这个？

15
00:00:43,500 --> 00:00:46,620
为什么我们关心在星期一？

16
00:00:46,620 --> 00:00:49,820
为什么在理论上，我们没在意周一？

17
00:00:49,820 --> 00:00:50,630
它做什么？

18
00:00:50,630 --> 00:00:51,950
>> 听众：我们可以动态地调整它的大小。

19
00:00:51,950 --> 00:00:53,740
>> 扬声器1：OK，所以我们可以
动态地调整其大小。

20
00:00:53,740 --> 00:00:54,710
干得好你们俩。

21
00:00:54,710 --> 00:00:57,560
所以，你可以动态调整这个
数据结构，而阵列，

22
00:00:57,560 --> 00:01:00,760
回想一下，你必须知道
先验多少空间你想

23
00:01:00,760 --> 00:01:03,870
如果你需要更多一点的
空间，你是那种运气。

24
00:01:03,870 --> 00:01:05,560
你必须创建一个全新的阵列。

25
00:01:05,560 --> 00:01:07,893
你必须将所有的
从一个到另一个数据，

26
00:01:07,893 --> 00:01:10,600
最终释放旧阵列
如果可以的话，然后继续。

27
00:01:10,600 --> 00:01:13,891
这只是感觉非常昂贵，非常
效率低，而且确实可以。

28
00:01:13,891 --> 00:01:14,890
但是，这是不是所有的好。

29
00:01:14,890 --> 00:01:18,180
我们付出的代价，究竟是什么1
较为明显的价格上涨，我们

30
00:01:18,180 --> 00:01:20,550
通过使用链表买单？

31
00:01:20,550 --> 00:01:22,825
>> 听众：我们必须使用
为每一个双层空间。

32
00:01:22,825 --> 00:01:25,200
扬声器1：是啊，所以我们需要
至少两倍的空间。

33
00:01:25,200 --> 00:01:27,700
事实上，我意识到这张照片的
甚至有点误导，

34
00:01:27,700 --> 00:01:32,200
因为在许多现代的CS50 IDE
计算机，一个指针或地址

35
00:01:32,200 --> 00:01:33,700
事实上并非四个字节。

36
00:01:33,700 --> 00:01:36,090
这是很多时候，这些
天8字节，这

37
00:01:36,090 --> 00:01:38,530
装置的底部最
在现实中的矩形有

38
00:01:38,530 --> 00:01:40,900
是那种两倍
大如我所绘制的，

39
00:01:40,900 --> 00:01:44,409
您正在使用三倍的手段
多的空间，我们可能有其他方式。

40
00:01:44,409 --> 00:01:46,700
现在，在同一时间，我们
还在说话字节，对不对？

41
00:01:46,700 --> 00:01:49,140
我们不一定讲
MB或GB，

42
00:01:49,140 --> 00:01:51,000
除非这些数据结构变大。

43
00:01:51,000 --> 00:01:54,510
>> 所以，今天我们开始考虑
我们可以如何发掘数据

44
00:01:54,510 --> 00:01:57,310
更有效地如果
事实上，数据变得更大。

45
00:01:57,310 --> 00:02:00,360
但是，让我们试着规范化
操作第一

46
00:02:00,360 --> 00:02:02,460
你可以在这些干什么
种数据结构。

47
00:02:02,460 --> 00:02:04,790
因此，像一个链接
清单普遍支持

48
00:02:04,790 --> 00:02:07,514
操作像删除，
插入，和搜索。

49
00:02:07,514 --> 00:02:08,639
什么做我的意思？

50
00:02:08,639 --> 00:02:11,222
这只是意味着，通常情况下，
如果人们使用链表，

51
00:02:11,222 --> 00:02:14,287
他们或者其他人实施
如删除，插入功能，

52
00:02:14,287 --> 00:02:16,120
和搜索，这样你就可以
确实做了什么

53
00:02:16,120 --> 00:02:18,030
有用的数据结构。

54
00:02:18,030 --> 00:02:20,760
因此，让我们快速浏览一下
我们如何可能实现

55
00:02:20,760 --> 00:02:24,530
一些代码，一个链表如下。

56
00:02:24,530 --> 00:02:27,885
>> 所以，这只是一些C代码，
甚至没有一个完整的程序

57
00:02:27,885 --> 00:02:29,260
我真的很快刮起了一阵。

58
00:02:29,260 --> 00:02:32,300
这不是在网上分销
码，因为它不会实际运行。

59
00:02:32,300 --> 00:02:33,790
但是请注意，我只是
有评论说，

60
00:02:33,790 --> 00:02:36,130
点点点，有什么东西
在那里，点点点，东西在那里。

61
00:02:36,130 --> 00:02:38,410
而且，我们只是看看
什么多汁的部件。

62
00:02:38,410 --> 00:02:40,790
因此，在三线，
记得，这是现在

63
00:02:40,790 --> 00:02:45,960
我们提出声明最后一个节点
时间，这些矩形物体中的一个。

64
00:02:45,960 --> 00:02:48,790
它具有我们称之为为N的INT，
但我们可以把它叫做什么，

65
00:02:48,790 --> 00:02:51,920
再一个结构节点明星叫旁边。

66
00:02:51,920 --> 00:02:55,520
而仅仅是明确的，即第二
线，对线6条，那是什么？

67
00:02:55,520 --> 00:02:57,930
它是什么做的我们呢？

68
00:02:57,930 --> 00:03:01,044
因为它确实看起来更
神秘的比我们平常的变量。

69
00:03:01,044 --> 00:03:02,740
>> 听众：这使得它搬过来的。

70
00:03:02,740 --> 00:03:04,650
>> 扬声器1：这使得它搬过来的。

71
00:03:04,650 --> 00:03:08,580
和更精确，
它将存储的地址

72
00:03:08,580 --> 00:03:11,582
这意味着是该节点的
语义旁边，对不对？

73
00:03:11,582 --> 00:03:13,540
所以它不会
不一定移动任何东西。

74
00:03:13,540 --> 00:03:15,290
它只是要
存储一个值，这是

75
00:03:15,290 --> 00:03:17,170
将是地址
一些其他节点的，

76
00:03:17,170 --> 00:03:20,810
这就是为什么我们说结构
节点明星，明星表示

77
00:03:20,810 --> 00:03:22,370
的指针或地址。

78
00:03:22,370 --> 00:03:26,390
好了，现在，如果你认为我们有
这款N提供给我们，让我们

79
00:03:26,390 --> 00:03:29,490
假设别人有
插入一大堆整数

80
00:03:29,490 --> 00:03:30,400
成一个链表。

81
00:03:30,400 --> 00:03:35,640
并且链表是
一些点指向

82
00:03:35,640 --> 00:03:39,040
一个变量调用列表的
在这里作为参数传递，

83
00:03:39,040 --> 00:03:43,120
我怎么去行
14实现搜索？

84
00:03:43,120 --> 00:03:45,990
换句话说，如果我实现
功能，其目的在生活中

85
00:03:45,990 --> 00:03:48,889
是采取一个int，然后
开始的链表，

86
00:03:48,889 --> 00:03:50,430
这是一个指向该链接的表。

87
00:03:50,430 --> 00:03:52,992
像第一，谁我认为大卫
是我们的志愿者在周一，

88
00:03:52,992 --> 00:03:54,700
他指着
整个链表，

89
00:03:54,700 --> 00:03:57,820
就好像我们传递
大卫在这里我们的论点。

90
00:03:57,820 --> 00:03:59,990
我们如何去遍历这个名单？

91
00:03:59,990 --> 00:04:04,640
嗯，事实证明，即使
指针是比较新的，现在对我们来说，

92
00:04:04,640 --> 00:04:07,010
我们可以相对做到这一点
直截了当。

93
00:04:07,010 --> 00:04:09,500
>> 我要继续前进，
声明临时变量

94
00:04:09,500 --> 00:04:12,364
按照惯例，只是走
被称为指针或PTR，

95
00:04:12,364 --> 00:04:14,030
但你可以把它称为任何你想要的。

96
00:04:14,030 --> 00:04:16,470
而且我要初始化
它到列表的开头。

97
00:04:16,470 --> 00:04:20,050
所以，你可以种想到这
作为我的老师有一天，

98
00:04:20,050 --> 00:04:23,580
那种指着别人
在我们人类作为志愿者。

99
00:04:23,580 --> 00:04:26,470
所以，我是一个临时变量，它是
只是指向同一件事

100
00:04:26,470 --> 00:04:31,390
我们不约而同地命名
志愿者大卫也指出。

101
00:04:31,390 --> 00:04:35,440
现在，当指针
不为空，因为召回

102
00:04:35,440 --> 00:04:40,350
那空是一些特殊的标记值
所述标定列表的末尾，

103
00:04:40,350 --> 00:04:44,280
因此，虽然我不指着
地面像我们过去的志愿者

104
00:04:44,280 --> 00:04:47,190
是，让我们继续
并做到以下几点。

105
00:04:47,190 --> 00:04:51,820
如果pointer--和那种我现在想
做我们的学生做了

106
00:04:51,820 --> 00:04:57,410
结构 - 如果指针点下一个
equals--相反，如果指针点N等于

107
00:04:57,410 --> 00:05:02,290
等于变量N，所述
这就是被传入的说法，

108
00:05:02,290 --> 00:05:05,370
那么我想继续
说返回true。

109
00:05:05,370 --> 00:05:11,020
我已经发现了内部数N
我的一个链表节点。

110
00:05:11,020 --> 00:05:13,500
但点不再
工作在这样的背景下，

111
00:05:13,500 --> 00:05:17,260
因为指针，PTR，是
确实是一个指针，地址，

112
00:05:17,260 --> 00:05:20,632
我们实际上可以精彩
使用最后一张语法

113
00:05:20,632 --> 00:05:22,590
那种品牌：
直观感觉，实际上

114
00:05:22,590 --> 00:05:27,870
用一个箭头这里，这意味着从去
该地址中的整数那里。

115
00:05:27,870 --> 00:05:30,160
所以这是非常相似
精神点运算符，

116
00:05:30,160 --> 00:05:33,860
但因为指针不是指针
而不是实际的结构本身，

117
00:05:33,860 --> 00:05:35,380
我们只是用箭头。

118
00:05:35,380 --> 00:05:40,620
>> 因此，如果当前节点是我的
临时变量，我指着

119
00:05:40,620 --> 00:05:43,060
是不是N，我该怎么想干什么？

120
00:05:43,060 --> 00:05:45,910
好了，我的志愿者
我们曾在这里的一天，

121
00:05:45,910 --> 00:05:49,710
如果我的第一个人是不是一个我
想，也许第二个人是不是

122
00:05:49,710 --> 00:05:52,660
一个我想要的，第三，我
需要保持身体移动。

123
00:05:52,660 --> 00:05:54,690
像我怎么通过列表步骤？

124
00:05:54,690 --> 00:05:57,470
当我们有一个数组，你
只是不喜欢我加再加。

125
00:05:57,470 --> 00:06:03,660
但在这种情况下，它足以
做指针，获取，指针，下一个。

126
00:06:03,660 --> 00:06:07,580
换句话说，下一个字段
就像所有的左手

127
00:06:07,580 --> 00:06:10,880
我们在周一志愿者
分别使用以指向某些其它节点。

128
00:06:10,880 --> 00:06:12,890
那是他们的下一个邻居。

129
00:06:12,890 --> 00:06:17,060
>> 所以，如果我想一步，通过这个名单，
我不能只是做我加再加了，

130
00:06:17,060 --> 00:06:20,120
我反而不得不说
我，指针，是怎么回事

131
00:06:20,120 --> 00:06:24,650
等于任何下一个字段是
下一字段，下一个字段是

132
00:06:24,650 --> 00:06:28,350
下面所有这些左手
我们有在舞台上指点

133
00:06:28,350 --> 00:06:30,000
一些后续值。

134
00:06:30,000 --> 00:06:32,590
如果我打通
那整个循环，

135
00:06:32,590 --> 00:06:39,330
最后，我打空没有
发现ñ然而，我刚刚返回false。

136
00:06:39,330 --> 00:06:44,100
如此反复，所有我们在这里做，
按照刚才的图片，

137
00:06:44,100 --> 00:06:47,840
开始通过指向
开头的名单大概。

138
00:06:47,840 --> 00:06:50,970
然后我检查，是价值
我在寻找等于九？

139
00:06:50,970 --> 00:06:52,650
如果是的话，我还真和我完成了。

140
00:06:52,650 --> 00:06:56,450
如果没有，我更新了我的手，
AKA指针，指向

141
00:06:56,450 --> 00:06:59,540
下一个箭头的位置，
那么下一个箭头的位置，

142
00:06:59,540 --> 00:07:00,480
和下一个。

143
00:07:00,480 --> 00:07:03,770
我只是在这个数组中行走。

144
00:07:03,770 --> 00:07:06,010
>> 如此反复，谁在乎呢？

145
00:07:06,010 --> 00:07:07,861
什么样的事情，这是一种成分呢？

146
00:07:07,861 --> 00:07:10,360
嗯，记得我们介绍
栈的概念，这

147
00:07:10,360 --> 00:07:15,400
是一个抽象数据类型的范围内，因为它是
不是C的东西，它不是一个CS50的事情，

148
00:07:15,400 --> 00:07:19,430
这是一个抽象的概念，在这一理念
堆叠的东西上彼此之上

149
00:07:19,430 --> 00:07:21,820
可以在实施
不同的方式束。

150
00:07:21,820 --> 00:07:25,600
我们提出了一种方法是用
阵列，或具有一个链表。

151
00:07:25,600 --> 00:07:29,570
而事实证明，规范地，一
栈支持至少两个操作。

152
00:07:29,570 --> 00:07:32,320
而时髦的话是推，以
推动东西压入堆栈，

153
00:07:32,320 --> 00:07:34,770
像在一个新的盘
食堂，或流行，

154
00:07:34,770 --> 00:07:39,000
这意味着以除去最上层
从堆栈中的餐盘

155
00:07:39,000 --> 00:07:41,500
大厅里，然后也许有些
其他操作为好。

156
00:07:41,500 --> 00:07:45,770
那么，如何可能，我们定义结构
我们现在调用堆栈？

157
00:07:45,770 --> 00:07:50,020
>> 好了，我们有所有必要的
语法我们所掌握的C.我说，

158
00:07:50,020 --> 00:07:53,830
给我一个类型定义
一摞内部的结构，

159
00:07:53,830 --> 00:07:58,030
我要说的是一个数组，
一大堆的数字，然后大小。

160
00:07:58,030 --> 00:08:00,930
因此，换句话说，如果我想
在代码来实现这一点，

161
00:08:00,930 --> 00:08:03,830
让我去那种公正，
画什么，这是说。

162
00:08:03,830 --> 00:08:06,317
因此，这是说，给我一个
那一定阵列结构，

163
00:08:06,317 --> 00:08:09,400
我不知道是什么能力，
这显然​​有些不变，我已经

164
00:08:09,400 --> 00:08:10,858
其他地方定义，这很好。

165
00:08:10,858 --> 00:08:15,260
但是，假如这只是之一，
二，三，四，五。

166
00:08:15,260 --> 00:08:16,700
所以容量为5。

167
00:08:16,700 --> 00:08:21,730
里面这个元素我
结构将被称为数字。

168
00:08:21,730 --> 00:08:24,020
然后，我需要
其他变量明显

169
00:08:24,020 --> 00:08:27,814
最初我打算叫大小
到规定初始化为零。

170
00:08:27,814 --> 00:08:29,730
如果有什么的
堆栈，大小是零，

171
00:08:29,730 --> 00:08:31,420
而且它在数量上的垃圾值。

172
00:08:31,420 --> 00:08:33,450
我不知道里面有什么了，只是还没有。

173
00:08:33,450 --> 00:08:36,059
>> 所以，如果我要推
东西压入堆栈，

174
00:08:36,059 --> 00:08:40,780
假设我调用函数推，并
我说推50，喜欢50号，

175
00:08:40,780 --> 00:08:44,090
在这里，你会建议
我画它在这个数组？

176
00:08:44,090 --> 00:08:47,124
有五种不同的可能的答案。

177
00:08:47,124 --> 00:08:48,790
你想去哪里推的50号？

178
00:08:48,790 --> 00:08:51,899
如果这里的目标，再次拨打
功能推，传递一个参数

179
00:08:51,899 --> 00:08:52,940
50，我在哪里放呢？

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
五possible-- 20％的几率
的猜测正确。

182
00:08:59,052 --> 00:08:59,896
是吗？

183
00:08:59,896 --> 00:09:00,740
>> 听众：最右。

184
00:09:00,740 --> 00:09:01,990
>> 扬声器1：最右。

185
00:09:01,990 --> 00:09:08,359
现在有25％的几率
的猜测正确。

186
00:09:08,359 --> 00:09:09,650
所以这实际上是罚款。

187
00:09:09,650 --> 00:09:12,770
按照惯例，我会说一个数组，
我们一般将开始在左边，

188
00:09:12,770 --> 00:09:14,519
但我们可以肯定
开始在合适的。

189
00:09:14,519 --> 00:09:17,478
因此，这里的扰流板会是我
可能将其绘制在左边，

190
00:09:17,478 --> 00:09:20,060
就像在一个正常的数组，其中
我开始从左到右。

191
00:09:20,060 --> 00:09:21,780
但是，如果你可以翻转
算术，罚款。

192
00:09:21,780 --> 00:09:23,060
这只是不是常规的。

193
00:09:23,060 --> 00:09:24,880
好吧，我需要做一个
更多的变化，虽然。

194
00:09:24,880 --> 00:09:27,710
现在，我已经把东西
压入堆栈，接下来会发生什么？

195
00:09:27,710 --> 00:09:29,400
>> 好吧，我得增加尺寸。

196
00:09:29,400 --> 00:09:32,600
因此，让我继续前进，只是
更新这，这是零。

197
00:09:32,600 --> 00:09:35,950
而不是现在，我要去
放中的值之一。

198
00:09:35,950 --> 00:09:39,460
现在假设我推另一
数压入堆栈，如51。

199
00:09:39,460 --> 00:09:42,680
好了，我一定要多一个
变化，这是向上的大小两种。

200
00:09:42,680 --> 00:09:46,100
再假设我推多了一个
数入堆栈像61，

201
00:09:46,100 --> 00:09:52,530
现在我需要更新的大小多一个
时间，并获得值3作为大小。

202
00:09:52,530 --> 00:09:54,690
现在假设我叫流行。

203
00:09:54,690 --> 00:09:57,250
现在流行，按照惯例，
不带参数。

204
00:09:57,250 --> 00:10:00,430
用栈，整
点盘隐喻

205
00:10:00,430 --> 00:10:03,450
是你没有自由裁量权
去得到那个盘子，你所能做的

206
00:10:03,450 --> 00:10:06,330
是流行最上面的
堆栈，只是因为。

207
00:10:06,330 --> 00:10:08,010
这就是这个数据结构一样。

208
00:10:08,010 --> 00:10:12,250
>> 因此，通过这种逻辑，如果我
要说流行，会发生什么了吗？

209
00:10:12,250 --> 00:10:13,080
所以61。

210
00:10:13,080 --> 00:10:15,402
那么，什么是真正的计算机
打算做的内存？

211
00:10:15,402 --> 00:10:16,610
什么是我的代码有什么关系？

212
00:10:16,610 --> 00:10:20,330
你会建议
我们改变在屏幕上？

213
00:10:20,330 --> 00:10:23,410
应该怎么改？

214
00:10:23,410 --> 00:10:24,960
对不起？

215
00:10:24,960 --> 00:10:26,334
所以我们摆脱61。

216
00:10:26,334 --> 00:10:27,500
所以，我绝对可以做到这一点。

217
00:10:27,500 --> 00:10:28,640
我可以摆脱61。

218
00:10:28,640 --> 00:10:30,980
然后还有什么其他
改变需要发生？

219
00:10:30,980 --> 00:10:33,160
尺寸可能有回去两种。

220
00:10:33,160 --> 00:10:34,210
所以，这很好。

221
00:10:34,210 --> 00:10:36,690
但是且慢，大小
刚才是三。

222
00:10:36,690 --> 00:10:38,240
让我们做一个快速的完整性检查。

223
00:10:38,240 --> 00:10:41,810
我们是怎么知道我们
想摆脱的61？

224
00:10:41,810 --> 00:10:42,760
因为我们大跌眼镜。

225
00:10:42,760 --> 00:10:46,450
所以我有第二个属性的大小。

226
00:10:46,450 --> 00:10:48,470
>> 等一下，我
回想起2周

227
00:10:48,470 --> 00:10:51,660
当我们开始谈论
阵列，在这位置为零，

228
00:10:51,660 --> 00:10:55,920
这是位置之一，这是位置
二，这是位置三个，四个，

229
00:10:55,920 --> 00:10:58,460
它看起来像
大小之间的关系

230
00:10:58,460 --> 00:11:02,780
而我想要的元素删除
从阵列似乎只是什么？

231
00:11:02,780 --> 00:11:05,120
尺寸减一。

232
00:11:05,120 --> 00:11:07,786
所以，这就是如何为人类
我们知道61是第一位的。

233
00:11:07,786 --> 00:11:09,160
怎么样的电脑会知道？

234
00:11:09,160 --> 00:11:11,701
当你的代码，你很可能
想做大小减一，

235
00:11:11,701 --> 00:11:14,950
所以三减一为两个，并且
意味着我们要摆脱61。

236
00:11:14,950 --> 00:11:18,000
然后，我们的确可以更新
这样大小的体积，现在

237
00:11:18,000 --> 00:11:20,300
进入三到只有两个。

238
00:11:20,300 --> 00:11:24,520
而刚需迂腐，我要去
提议我做的，对不对？

239
00:11:24,520 --> 00:11:27,660
你直观地提出
正确我应该摆脱61。

240
00:11:27,660 --> 00:11:30,700
但是，有一种没有我
那种摆脱了61？

241
00:11:30,700 --> 00:11:33,790
我已经有效地忘记
它的实际存在。

242
00:11:33,790 --> 00:11:37,680
而回想起PSET4，如果你读过
有关取证的文章中，PDF

243
00:11:37,680 --> 00:11:40,780
我们有你们看，或者你
将读取本周PSET4。

244
00:11:40,780 --> 00:11:44,300
回想一下，这其实是有密切关系的
计算机取证的整体思路。

245
00:11:44,300 --> 00:11:47,820
什么是电脑一般不为
它只是忘记在那里的东西是，

246
00:11:47,820 --> 00:11:51,300
但它并没有去和像
试着刮出来或重写

247
00:11:51,300 --> 00:11:54,560
这些位与零和一
或一些其它的随机图案

248
00:11:54,560 --> 00:11:56,690
除非你自己这样做的故意。

249
00:11:56,690 --> 00:11:58,930
所以，你的直觉是
好吧，让我们摆脱61。

250
00:11:58,930 --> 00:12:00,650
但在现实中，我们没有理会。

251
00:12:00,650 --> 00:12:04,040
我们只需要忘记，
它的存在，通过改变我们的规模。

252
00:12:04,040 --> 00:12:05,662
>> 现在有这个堆栈的一个问题。

253
00:12:05,662 --> 00:12:07,620
如果我继续推动东西
压入堆栈，什么是

254
00:12:07,620 --> 00:12:11,167
显然不会发生
在短短的几分钟时间？

255
00:12:11,167 --> 00:12:12,500
我们将用尽空间。

256
00:12:12,500 --> 00:12:13,580
而我们该怎么办？

257
00:12:13,580 --> 00:12:14,680
那种我们搞砸了。

258
00:12:14,680 --> 00:12:19,000
此实现不让
我们调整阵列，因为使用

259
00:12:19,000 --> 00:12:21,240
这个语法，如果你
回想起每周二，

260
00:12:21,240 --> 00:12:23,520
一旦你已经声明
阵列的大小，

261
00:12:23,520 --> 00:12:26,780
我们还没有看到一个机制，但在这里
可以改变阵列的大小。

262
00:12:26,780 --> 00:12:29,020
事实上C没有这个功能。

263
00:12:29,020 --> 00:12:32,524
如果你说给我五
国道主干线，称他们的数字，

264
00:12:32,524 --> 00:12:33,940
这就是你要得到它。

265
00:12:33,940 --> 00:12:38,790
所以我们现在要做的是周一，有
表达一个解决方案的能力

266
00:12:38,790 --> 00:12:42,480
虽然，我们只需要调整
我们的叠层的定义

267
00:12:42,480 --> 00:12:46,840
不要被一些硬编码的数组，
但只是以存储一个地址。

268
00:12:46,840 --> 00:12:47,890
>> 现在，这是为什么？

269
00:12:47,890 --> 00:12:51,690
现在，我们只需要坦然面对
事实证明我的程序运行时，

270
00:12:51,690 --> 00:12:53,730
我大概会
要问的人，

271
00:12:53,730 --> 00:12:55,110
多少个号码，你想存储？

272
00:12:55,110 --> 00:12:56,776
因此，输入有来自某处。

273
00:12:56,776 --> 00:12:59,140
但是，一旦我知道，
号码，然后我可以

274
00:12:59,140 --> 00:13:02,470
使用什么功能给
我的内存块？

275
00:13:02,470 --> 00:13:03,580
我可以用malloc。

276
00:13:03,580 --> 00:13:06,710
我可以说，任何数量的
字节，我想回去了这些国道主干线。

277
00:13:06,710 --> 00:13:10,910
而且我必须存储在数字
可变这里这个结构里面

278
00:13:10,910 --> 00:13:13,480
应该是什么？

279
00:13:13,480 --> 00:13:18,440
究竟进入
在这种情况下的数字？

280
00:13:18,440 --> 00:13:21,300
是啊，一个指向第一
该内存块的字节，

281
00:13:21,300 --> 00:13:24,940
或更具体地，地址
第一这些字节。

282
00:13:24,940 --> 00:13:27,300
如果它是一个不事
字节或十亿字节，

283
00:13:27,300 --> 00:13:28,890
我只需要关心的第一个。

284
00:13:28,890 --> 00:13:31,530
因为什么样的malloc担保，
我的操作系统担保，

285
00:13:31,530 --> 00:13:34,170
是，存储器I组块
得到的，这将是连续的。

286
00:13:34,170 --> 00:13:35,378
还有的不会是空白。

287
00:13:35,378 --> 00:13:38,576
所以，如果我问50
字节或1000个字节，

288
00:13:38,576 --> 00:13:40,450
他们都将是
背靠背回来。

289
00:13:40,450 --> 00:13:44,500
而只要我还记得有多大，怎么
很多我要求，我所需要知道的

290
00:13:44,500 --> 00:13:46,230
是第一个这样的地址。

291
00:13:46,230 --> 00:13:48,660
>> 所以，现在我们已经在代码的能力。

292
00:13:48,660 --> 00:13:51,280
虽然，这将带我们
更多的时间来写这件事，

293
00:13:51,280 --> 00:13:55,900
我们现在可以通过重新分配内存
只是存储不同的地址有

294
00:13:55,900 --> 00:13:59,060
如果我们想要一个更大的，甚至
较小的组块的存储器。

295
00:13:59,060 --> 00:14:00,170
因此，在这里一个权衡。

296
00:14:00,170 --> 00:14:01,360
现在，我们得到的活力。

297
00:14:01,360 --> 00:14:03,350
我们仍然有
contiguousness我自称。

298
00:14:03,350 --> 00:14:05,881
因为malloc的给我们
一个连续的内存块。

299
00:14:05,881 --> 00:14:08,630
但是，这将是一个痛苦
脖子对我们来说，程序员，

300
00:14:08,630 --> 00:14:09,770
实际代码了。

301
00:14:09,770 --> 00:14:10,730
这只是更多的工作。

302
00:14:10,730 --> 00:14:13,930
我们需要的代码类似于我是什么
刚才撞了。

303
00:14:13,930 --> 00:14:16,120
非常可行，但增加了复杂性。

304
00:14:16,120 --> 00:14:19,520
因此开发时，程序员
时间是另一个资源

305
00:14:19,520 --> 00:14:22,520
我们可能需要花
一段时间来获得新的功能。

306
00:14:22,520 --> 00:14:24,020
然后当然还有一个队列。

307
00:14:24,020 --> 00:14:26,227
我们不会进入这个
之一，很多细节。

308
00:14:26,227 --> 00:14:27,560
但它在精神上非常相似。

309
00:14:27,560 --> 00:14:31,220
我可以实现一个队列，
其相应的操作，

310
00:14:31,220 --> 00:14:35,660
入队或出队，像添加或删除，
它是说这只是一个华丽的方式，

311
00:14:35,660 --> 00:14:38,100
入队或出队，如下。

312
00:14:38,100 --> 00:14:41,170
我只能给自己一个结构
一遍的数的阵列，

313
00:14:41,170 --> 00:14:44,000
一遍的尺寸，
但为什么我现在需要

314
00:14:44,000 --> 00:14:46,940
跟踪一个队列的前面的？

315
00:14:46,940 --> 00:14:50,630
我并不需要知道
前面我堆栈。

316
00:14:50,630 --> 00:14:53,570
好吧，如果我再一
queue--就让我们很难

317
00:14:53,570 --> 00:14:57,870
它编码具有到五
整数这里可能。

318
00:14:57,870 --> 00:15:00,940
因此，这是零，一，二，三，四。

319
00:15:00,940 --> 00:15:03,430
这将是
拨打的号码了。

320
00:15:03,430 --> 00:15:06,940
而这将是所谓的大小。

321
00:15:06,940 --> 00:15:10,056
>> 为什么不充分
以刚才的大小？

322
00:15:10,056 --> 00:15:11,680
好吧，让我们推动这些相同的数字。

323
00:15:11,680 --> 00:15:14,220
所以我pushed--我入队，或推。

324
00:15:14,220 --> 00:15:20,150
现在，我将排队50，然后
51，然后61，和点点点。

325
00:15:20,150 --> 00:15:21,070
所以这是入队。

326
00:15:21,070 --> 00:15:23,176
我入队的50，然后51，然后61。

327
00:15:23,176 --> 00:15:25,050
这看起来相同
到烟囱迄今

328
00:15:25,050 --> 00:15:27,190
但我确实需要做出一个改变。

329
00:15:27,190 --> 00:15:33,680
我需要更新这个尺寸，所以我去
从零到一到两到三现在。

330
00:15:33,680 --> 00:15:35,760
我如何出列？

331
00:15:35,760 --> 00:15:36,890
与出队会发生什么？

332
00:15:36,890 --> 00:15:41,950
谁应该打这个名单第一
如果是该行的苹果专卖店？

333
00:15:41,950 --> 00:15:42,780
所以50。

334
00:15:42,780 --> 00:15:44,700
因此，它是有点棘手这个时候。

335
00:15:44,700 --> 00:15:47,880
而上一次是超级
易只是做大小减一，

336
00:15:47,880 --> 00:15:51,440
我得到我的数组的末尾有效
其中数字是，它消除61。

337
00:15:51,440 --> 00:15:52,920
但我不希望删除61。

338
00:15:52,920 --> 00:15:55,030
我想利用50，谁
在那里，在上午5:00

339
00:15:55,030 --> 00:15:56,790
排队的
新的iPhone或诸如此类的东西。

340
00:15:56,790 --> 00:16:01,200
所以，要摆脱50，我
不能仅仅做到这一点，对不对？

341
00:16:01,200 --> 00:16:02,547
我可以划掉50。

342
00:16:02,547 --> 00:16:04,380
但是，我们刚才说了，我们
不必如此肛门

343
00:16:04,380 --> 00:16:06,330
以划掉或隐藏数据。

344
00:16:06,330 --> 00:16:08,090
我们可以忘记它在哪里。

345
00:16:08,090 --> 00:16:12,330
>> 但是，如果我现在改变我的尺寸，
二，这是足够的信息

346
00:16:12,330 --> 00:16:15,711
知道什么是我的排队怎么回事？

347
00:16:15,711 --> 00:16:16,680
并不是的。

348
00:16:16,680 --> 00:16:19,830
就像我的尺寸是两个，而是
哪里排队开始，

349
00:16:19,830 --> 00:16:22,980
尤其是如果我仍然有
那些相同的标号在存储器中。

350
00:16:22,980 --> 00:16:24,260
50，51，61。

351
00:16:24,260 --> 00:16:27,090
所以，我需要记住
现在所在的前面。

352
00:16:27,090 --> 00:16:29,630
所以，我提出了
在那里，我们将刚才叫

353
00:16:29,630 --> 00:16:33,729
第N次前，其初始
价值应该是什么呢？

354
00:16:33,729 --> 00:16:35,270
零，列表仅仅是个开始。

355
00:16:35,270 --> 00:16:40,876
但现在除了递减
规模，我们只是增加了前面。

356
00:16:40,876 --> 00:16:42,000
现在，这里是另外一个问题。

357
00:16:42,000 --> 00:16:43,030
所以一旦我继续前进。

358
00:16:43,030 --> 00:16:47,520
假设这是数
像121，124，然后，该死，

359
00:16:47,520 --> 00:16:48,610
我的空间。

360
00:16:48,610 --> 00:16:50,390
但是且慢，我不是。

361
00:16:50,390 --> 00:16:55,630
所以在这一点中的故事，
假设尺寸是一，二，

362
00:16:55,630 --> 00:17:00,370
三个，四个，所以假设
大小为4，前一个，

363
00:17:00,370 --> 00:17:01,621
所以51是在前面。

364
00:17:01,621 --> 00:17:04,329
我想提出另一个号码在这里，
但是，该死，我出了空间。

365
00:17:04,329 --> 00:17:06,710
但我不是真的，对不对？

366
00:17:06,710 --> 00:17:11,192
我在哪里可以把一些
附加价值，如171？

367
00:17:11,192 --> 00:17:13,400
是的，我能正中下怀
回去那边了吧？

368
00:17:13,400 --> 00:17:18,161
然后过了50，或
只是简单地覆盖它与171。

369
00:17:18,161 --> 00:17:20,410
如果你想知道为什么
我们的数字变得如此随意，

370
00:17:20,410 --> 00:17:24,150
这些通常采取计算机
科学课程在哈佛CS50之后。

371
00:17:24,150 --> 00:17:27,510
但是，这是一个很好的优化，
因为现在我没有浪费的空间。

372
00:17:27,510 --> 00:17:30,750
我还是要记住
有多大这个东西是总。

373
00:17:30,750 --> 00:17:31,500
它共有五次总。

374
00:17:31,500 --> 00:17:33,375
因为我不希望
开始覆盖51。

375
00:17:33,375 --> 00:17:36,260
所以，我现在还在外面的空间，
从而前同样的问题。

376
00:17:36,260 --> 00:17:39,140
但是你可以看到现在
在你的代码，你可能

377
00:17:39,140 --> 00:17:41,910
有一点写更多
复杂性来实现这一目标。

378
00:17:41,910 --> 00:17:44,510
而事实上，运营商所
C语言可能让

379
00:17:44,510 --> 00:17:48,110
你神奇地做到这一点的圆？

380
00:17:48,110 --> 00:17:50,160
是的模运算符，
百分号。

381
00:17:50,160 --> 00:17:53,160
那么，有什么样的酷的队列，
尽管我们不断吸引数组

382
00:17:53,160 --> 00:17:56,520
因为这些象直线，如果
那种认为关于这个问题，弯曲

383
00:17:56,520 --> 00:18:00,341
作为周围一圈，然后就
一种直觉它的工作精神

384
00:18:00,341 --> 00:18:01,590
我觉得有点更干净。

385
00:18:01,590 --> 00:18:05,190
你仍然必须执行
在代码中的心智模式。

386
00:18:05,190 --> 00:18:07,550
所以并不难，
最终，实施，

387
00:18:07,550 --> 00:18:12,430
但我们还是失去了size--相当，
能力来调整，除非我们做到这一点。

388
00:18:12,430 --> 00:18:15,310
>> 我们必须摆脱的数组，我们
它与单个指针替换，

389
00:18:15,310 --> 00:18:20,010
然后地方在我的代码我有
一个叫什么函数来实际创建

390
00:18:20,010 --> 00:18:23,720
数组拨打的号码？

391
00:18:23,720 --> 00:18:26,190
malloc或一些类似
功能，没错。

392
00:18:26,190 --> 00:18:30,481
在栈或队列的任何问题。

393
00:18:30,481 --> 00:18:30,980
是吗？

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
好问题。

396
00:18:34,240 --> 00:18:35,830
你会用什么在这里模。

397
00:18:35,830 --> 00:18:38,520
所以一般地，在使用
MOD，你会做

398
00:18:38,520 --> 00:18:40,620
同的大小
整体的数据结构。

399
00:18:40,620 --> 00:18:44,120
因此，像五容量，如果
这是不变的，可能是参与。

400
00:18:44,120 --> 00:18:47,100
但只是在做模数5
可能是不足够的，

401
00:18:47,100 --> 00:18:51,380
因为我们需要知道我们是否
环绕在这里或在这里或在这里。

402
00:18:51,380 --> 00:18:54,160
所以，你可能还
将要涉及到

403
00:18:54,160 --> 00:18:57,220
事物的大小，或
前面的变量也是如此。

404
00:18:57,220 --> 00:19:00,140
所以，它只是这个比较
简单的算术表达式，

405
00:19:00,140 --> 00:19:02,000
但模将是关键因素。

406
00:19:02,000 --> 00:19:03,330
>> 所以，短片，如果你会的。

407
00:19:03,330 --> 00:19:05,780
一个动画，一些
人们在另一所大学

408
00:19:05,780 --> 00:19:08,060
放在一起，我们已经
适用于本次讨论。

409
00:19:08,060 --> 00:19:12,630
它涉及杰克学习
有关队列和统计数据的事实。

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> 电影：曾几何时，
有一个叫杰克的家伙。

412
00:19:21,890 --> 00:19:25,330
当它来交朋友，
杰克没有一个诀窍。

413
00:19:25,330 --> 00:19:28,220
于是杰克就去找了
最流行的家伙，他知道。

414
00:19:28,220 --> 00:19:30,920
他到楼，问道，我该怎么办？

415
00:19:30,920 --> 00:19:33,400
娄看到他的朋友
真的很心疼。

416
00:19:33,400 --> 00:19:36,050
好了，他开始，就
看你如何打扮。

417
00:19:36,050 --> 00:19:38,680
你没有任何的衣服
以不同的面貌？

418
00:19:38,680 --> 00:19:39,660
是的，杰克说。

419
00:19:39,660 --> 00:19:40,840
我当然有。

420
00:19:40,840 --> 00:19:43,320
来我家，
我会告诉他们你。

421
00:19:43,320 --> 00:19:44,550
于是他们去了杰克的。

422
00:19:44,550 --> 00:19:47,520
和杰克表明娄盒
在那里他保持他的所有衬衫，

423
00:19:47,520 --> 00:19:49,260
和他的裤子，他的袜子。

424
00:19:49,260 --> 00:19:52,290
楼继伟说，我看你有没有
你的衣服在一堆。

425
00:19:52,290 --> 00:19:54,870
你为什么不穿些
其他人曾经在一段时间？

426
00:19:54,870 --> 00:19:58,020
>> 杰克说，好吧，当我
脱去衣服和袜子，

427
00:19:58,020 --> 00:20:00,780
我把它们洗干净，并把
他们走在框中。

428
00:20:00,780 --> 00:20:03,210
然后是下一个
早晨，起来我一跳。

429
00:20:03,210 --> 00:20:06,380
我去的箱子，并得到
我的衣服上。

430
00:20:06,380 --> 00:20:09,070
娄很快就意识到
这个问题与杰克。

431
00:20:09,070 --> 00:20:12,080
他不停的衣服，光盘，
并且堆叠的书籍。

432
00:20:12,080 --> 00:20:14,420
当他伸手
一些阅读或磨损，

433
00:20:14,420 --> 00:20:17,100
他会选择顶部的书或内衣。

434
00:20:17,100 --> 00:20:19,500
然后，当他完成，他
会把它的右后卫。

435
00:20:19,500 --> 00:20:21,970
回到它会去，在堆栈的顶部。

436
00:20:21,970 --> 00:20:24,460
我知道解决的办法，
说胜利响亮。

437
00:20:24,460 --> 00:20:27,090
你需要学习
开始使用一个队列。

438
00:20:27,090 --> 00:20:29,870
娄花了杰克的衣服，
他们挂在衣柜里。

439
00:20:29,870 --> 00:20:32,710
而当他已经清空
盒子，他只是扔。

440
00:20:32,710 --> 00:20:36,500
>> 然后他说，现在的杰克，在年底
当天，穿上你的衣服左边

441
00:20:36,500 --> 00:20:37,990
当你把他们带走。

442
00:20:37,990 --> 00:20:41,300
然后明天早上，当你
看到阳光，让你的衣服

443
00:20:41,300 --> 00:20:43,440
在右边，从行的末端。

444
00:20:43,440 --> 00:20:44,880
你难道不明白吗？说楼。

445
00:20:44,880 --> 00:20:46,370
这将是那么好。

446
00:20:46,370 --> 00:20:49,770
你会冲刷一切的一次
你穿的东西之前两次。

447
00:20:49,770 --> 00:20:52,670
而随着一切都在排队
在他的衣柜和书架，

448
00:20:52,670 --> 00:20:55,160
杰克开始感觉
十分肯定自己。

449
00:20:55,160 --> 00:20:59,720
娄所有的感谢和
他精彩的队列。

450
00:20:59,720 --> 00:21:01,220
扬声器1：好吧，这是可爱的。

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
那么，什么是怎么回事
在现在的引擎盖下？

453
00:21:10,080 --> 00:21:12,370
我们有三分球，
我们拥有的malloc，

454
00:21:12,370 --> 00:21:15,680
我们有能力创造
内存占为己有块

455
00:21:15,680 --> 00:21:16,344
动态。

456
00:21:16,344 --> 00:21:18,510
所以这是一个图片我们
瞥见就在几天前。

457
00:21:18,510 --> 00:21:21,180
我们真的不纠缠
就可以了，但这张照片

458
00:21:21,180 --> 00:21:24,180
已经持续下
现在引擎盖几个星期。

459
00:21:24,180 --> 00:21:27,050
所以这代表，只是
我们已经绘制一个矩形，

460
00:21:27,050 --> 00:21:28,180
您的计算机的内存。

461
00:21:28,180 --> 00:21:31,850
也许你的电脑，或者CS50
ID，具有存储器或RAM一个千兆字节

462
00:21:31,850 --> 00:21:33,050
两个千兆字节或四个。

463
00:21:33,050 --> 00:21:34,450
这其实并不重要。

464
00:21:34,450 --> 00:21:37,240
您的操作系统
Windows或Mac OS或Linux，

465
00:21:37,240 --> 00:21:41,120
基本上可以让你的程序
认为它能够访问

466
00:21:41,120 --> 00:21:42,982
到的全部
您的计算机的内存，

467
00:21:42,982 --> 00:21:45,440
即使你可能正在运行
多程序同时应用。

468
00:21:45,440 --> 00:21:46,990
因此，在现实中，没有真正发挥作用。

469
00:21:46,990 --> 00:21:49,448
但它是一种一种假象
给所有的程序。

470
00:21:49,448 --> 00:21:53,110
所以，如果你有内存2音乐会，这
是怎样的计算机可能会想到它。

471
00:21:53,110 --> 00:21:57,110
>> 现在，巧合的是，其中一个
事，内存这些领域之一，

472
00:21:57,110 --> 00:21:58,350
被称为堆。

473
00:21:58,350 --> 00:22:01,680
实际上，任何时候
迄今在编写代码

474
00:22:01,680 --> 00:22:05,900
你已经被称为
功能，比如主。

475
00:22:05,900 --> 00:22:08,410
回想一下，任何时候我已经
得出计算机的内存，

476
00:22:08,410 --> 00:22:10,640
我总是吸引排序
一半的矩形的这里

477
00:22:10,640 --> 00:22:12,520
也懒得说话
关于什么的上面。

478
00:22:12,520 --> 00:22:15,980
因为当主被调用时，我要求
你得到这个条子的记忆

479
00:22:15,980 --> 00:22:16,970
该下降这里。

480
00:22:16,970 --> 00:22:20,650
如果主称为函数
像掉期，以及交换到这里。

481
00:22:20,650 --> 00:22:23,720
而事实证明，这是
其中，它的结束了。

482
00:22:23,720 --> 00:22:26,277
在被称为堆的东西
在你的计算机的内存中。

483
00:22:26,277 --> 00:22:28,360
现在在一天结束时，
这仅仅是解决了。

484
00:22:28,360 --> 00:22:30,680
这就像一个字节零，
字节之一字节2十亿。

485
00:22:30,680 --> 00:22:33,130
但是，如果你仔细想想
因为这样的矩形对象，

486
00:22:33,130 --> 00:22:35,130
我们所做的每一个
一次，我们调用一个函数

487
00:22:35,130 --> 00:22:37,180
分层存储新的切片。

488
00:22:37,180 --> 00:22:41,700
我们给这个函数片
自身的存储器的工作。

489
00:22:41,700 --> 00:22:44,490
>> 现在回忆起来，这是非常重要的。

490
00:22:44,490 --> 00:22:46,400
因为如果我们确实有
类似的交换

491
00:22:46,400 --> 00:22:51,610
像A和B两个局部变量
我们改变这些值从一个和两个

492
00:22:51,610 --> 00:22:55,130
两个和一个，召回
当交换返回，

493
00:22:55,130 --> 00:22:58,330
这是因为虽然这片
内存只是走了。

494
00:22:58,330 --> 00:23:00,080
在现实中，它仍然
有取证。

495
00:23:00,080 --> 00:23:01,940
而一些仍然居然有。

496
00:23:01,940 --> 00:23:05,410
但在概念上，这是因为
虽然它完全消失了。

497
00:23:05,410 --> 00:23:10,910
所以主不知道任何工作
这是在交换功能完成后，

498
00:23:10,910 --> 00:23:14,890
除非它实际上是通过这些
通过指针或引用参数。

499
00:23:14,890 --> 00:23:17,790
现在，从根本上解决
该问题与交换

500
00:23:17,790 --> 00:23:19,970
通过地址传递的东西研究。

501
00:23:19,970 --> 00:23:23,250
但事实证明也是如此，什么是
已经持续了上面那一部分

502
00:23:23,250 --> 00:23:26,330
矩形的这段时间是
但有更多的内存在那里。

503
00:23:26,330 --> 00:23:28,790
动态当你
分配内存，

504
00:23:28,790 --> 00:23:32,020
无论是GetString的，里面的这
我们在CS50已经为你做

505
00:23:32,020 --> 00:23:34,710
图书馆，或者，如果你们
调用malloc和要求

506
00:23:34,710 --> 00:23:37,950
对于一大块的操作系统
存储器，它不是来自堆栈。

507
00:23:37,950 --> 00:23:40,960
它来自另一个地方
在您的计算机的内存

508
00:23:40,960 --> 00:23:42,220
这就是所谓的堆。

509
00:23:42,220 --> 00:23:43,430
而这没有什么不同。

510
00:23:43,430 --> 00:23:44,285
这是相同的RAM。

511
00:23:44,285 --> 00:23:45,160
这是同样的内存。

512
00:23:45,160 --> 00:23:49,080
这只是在RAM那达
那里，而不是到这里。

513
00:23:49,080 --> 00:23:50,750
>> 所以，这是什么意思？

514
00:23:50,750 --> 00:23:53,650
好吧，如果你的电脑有
的存储器量有限

515
00:23:53,650 --> 00:23:57,450
与堆栈长大，所以
说话，堆，根据

516
00:23:57,450 --> 00:23:59,349
这一箭，越来越大了。

517
00:23:59,349 --> 00:24:01,140
换句话说，每
一次调用malloc，

518
00:24:01,140 --> 00:24:03,430
你被赋予了片
的存储器从上方

519
00:24:03,430 --> 00:24:06,630
那么也许更低一点，然后一点点
低，每次调用malloc的时候，

520
00:24:06,630 --> 00:24:10,100
堆，它的使用情况，
是一种成长，

521
00:24:10,100 --> 00:24:11,950
日益密切的是什么？

522
00:24:11,950 --> 00:24:13,382
堆栈。

523
00:24:13,382 --> 00:24:14,840
那么，这似乎是一个好主意吗？

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
我的意思是，它并不真正清楚
如果你只可以做什么

526
00:24:22,140 --> 00:24:23,910
具有存储器的有限数量。

527
00:24:23,910 --> 00:24:25,200
但是，这肯定是不好的。

528
00:24:25,200 --> 00:24:27,920
这两个箭头都在一个
当然崩溃彼此。

529
00:24:27,920 --> 00:24:31,930
>> 而事实证明，坏家伙，人们谁
与节目特别好，

530
00:24:31,930 --> 00:24:36,140
并试图侵入电脑，
可以利用这个现实。

531
00:24:36,140 --> 00:24:38,290
事实上，我们考虑
一个小片段。

532
00:24:38,290 --> 00:24:41,350
因此，这是你可以阅读的一个例子
关于维基百科上的更详细。

533
00:24:41,350 --> 00:24:43,100
我们将向您在
文章，如果好奇。

534
00:24:43,100 --> 00:24:45,650
但是有一般的攻击
被称为缓冲区溢出的

535
00:24:45,650 --> 00:24:49,570
只要已经存在了作为人类
不得不操纵能力

536
00:24:49,570 --> 00:24:53,120
计算机的内存，尤其是在C中
所以这是一个非常随意的程序，

537
00:24:53,120 --> 00:24:55,130
但让我们从下往上看。

538
00:24:55,130 --> 00:24:57,650
主要为焦炭ARGC ARGV明星。

539
00:24:57,650 --> 00:24:59,830
所以这是一个程序，它
命令行参数。

540
00:24:59,830 --> 00:25:03,620
和所有主要的也显然是通话
一个函数，调用它F代表简单。

541
00:25:03,620 --> 00:25:04,610
它在传递什么？

542
00:25:04,610 --> 00:25:05,490
ARGV之一。

543
00:25:05,490 --> 00:25:09,320
因此，它传递到f中的任何
的话，就是用户键入

544
00:25:09,320 --> 00:25:11,500
在之后的提示
节目的名字都没有。

545
00:25:11,500 --> 00:25:15,730
那么像撒或的Vigenere，这
你可能还记得与ARGV做。

546
00:25:15,730 --> 00:25:16,680
>> 那么，什么是F？

547
00:25:16,680 --> 00:25:19,760
˚F接受一个字符串
作为其唯一的参数，

548
00:25:19,760 --> 00:25:22,100
AKA一个char明星，同
首先，作为一个字符串。

549
00:25:22,100 --> 00:25:24,920
而这就是所谓的任意
禁止在这个例子。

550
00:25:24,920 --> 00:25:27,710
然后焦炭C 12，
只是外行人的话说，

551
00:25:27,710 --> 00:25:31,750
什么是CHARÇ支架12做的我们呢？

552
00:25:31,750 --> 00:25:33,440
它是什么呢？

553
00:25:33,440 --> 00:25:36,490
分配内存，专
12个字节为12个字符。

554
00:25:36,490 --> 00:25:36,990
没错。

555
00:25:36,990 --> 00:25:40,000
然后最后一行，搅拌，
副本，你可能没见过。

556
00:25:40,000 --> 00:25:43,360
这是一个字符串拷贝
功能，其目的在生活中

557
00:25:43,360 --> 00:25:48,160
是复制它的第二个参数
到了第一个参数，

558
00:25:48,160 --> 00:25:51,190
但只达到一个
一定数量的字节。

559
00:25:51,190 --> 00:25:53,860
所以第三个参数说：
你应该有多少个字节复制？

560
00:25:53,860 --> 00:25:56,720
条的长度，
无论用户键入。

561
00:25:56,720 --> 00:25:59,320
及内容
酒吧，该字符串，是

562
00:25:59,320 --> 00:26:02,330
拷贝到存储指向在C.

563
00:26:02,330 --> 00:26:04,060
>> 因此，这似乎是一种愚蠢的，它是。

564
00:26:04,060 --> 00:26:06,300
这是一个人为的例子，
但它代表

565
00:26:06,300 --> 00:26:10,100
一类攻击向量的，
一种方式攻击的程序。

566
00:26:10,100 --> 00:26:15,050
一切都很好，好，如果用户
在一个字那是11个字符类型

567
00:26:15,050 --> 00:26:18,040
或更少，加上反斜杠零。

568
00:26:18,040 --> 00:26:22,830
如果在用户键入超过什么
11或12或20或50个字符？

569
00:26:22,830 --> 00:26:25,090
这是什么程序该怎么办？

570
00:26:25,090 --> 00:26:29,360
潜在的赛格故障。这是怎么回事
要盲目照搬一切都在酒吧起来

571
00:26:29,360 --> 00:26:31,750
其长度，这是
从字面上的一切吧，

572
00:26:31,750 --> 00:26:36,307
到地址指向C.但Ç
只抢先给出12个字节。

573
00:26:36,307 --> 00:26:37,640
但是，没有任何额外的检查。

574
00:26:37,640 --> 00:26:38,700
有没有，如果条件。

575
00:26:38,700 --> 00:26:40,580
有没有错误检查在这里。

576
00:26:40,580 --> 00:26:43,270
>> 所以这个计划是什么
要做的只是一味的

577
00:26:43,270 --> 00:26:45,750
一件事复制到其他。

578
00:26:45,750 --> 00:26:47,880
所以，如果我们得出这样的
作为一个图片，这里的

579
00:26:47,880 --> 00:26:49,860
内存空间只是一个条子。

580
00:26:49,860 --> 00:26:53,470
所以，注意在底部，我们
有局部变量吧。

581
00:26:53,470 --> 00:26:57,330
这样的指针，那将store--
而当地的论点，即是

582
00:26:57,330 --> 00:26:58,672
将存储字符串吧。

583
00:26:58,672 --> 00:27:00,380
然后请注意只是
它在一组的上方，

584
00:27:00,380 --> 00:27:02,505
因为每次你问的时间
为存储器的栈上，

585
00:27:02,505 --> 00:27:04,310
它会一点点
它形象地上面，

586
00:27:04,310 --> 00:27:06,270
我们已经得到了12个字节有通知。

587
00:27:06,270 --> 00:27:10,690
顶部左边的一个是C支架为零，
底部正确的是C支架11。

588
00:27:10,690 --> 00:27:12,870
这是多么的电脑
要打好它。

589
00:27:12,870 --> 00:27:18,300
因此，只要凭直觉，如果酒吧有更多的
超过12个字符共包括

590
00:27:18,300 --> 00:27:25,790
反斜杠零，在哪里
12的C支架12要去？

591
00:27:25,790 --> 00:27:28,440
或者说在这里是第12个
字符或13个字符，

592
00:27:28,440 --> 00:27:30,900
第一百字去
结束了在图片？

593
00:27:30,900 --> 00:27:33,400
高于或低于？

594
00:27:33,400 --> 00:27:36,300
>> 对，因为即使
栈本身是向上增长，

595
00:27:36,300 --> 00:27:39,590
一旦你把东西在
它，它的设计的原因，

596
00:27:39,590 --> 00:27:41,294
放存储器从上到下。

597
00:27:41,294 --> 00:27:44,460
所以，如果你有超过12个字节，
你将开始覆盖吧。

598
00:27:44,460 --> 00:27:47,280
现在，这是一个错误，但它的
不是一个真正的大问题。

599
00:27:47,280 --> 00:27:51,130
但是，这是一个大问题，因为有
更多的东西在内存回事。

600
00:27:51,130 --> 00:27:53,074
因此，这里是我们如何能够
把你好，是明确的。

601
00:27:53,074 --> 00:27:54,490
如果我输入打招呼的提示。

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O反斜杠零，在结束了
这12个字节，而且我们的超级安全。

603
00:27:59,330 --> 00:28:00,330
一切都很好。

604
00:28:00,330 --> 00:28:03,020
但是，如果我输入一些东西
时间越长，可能是

605
00:28:03,020 --> 00:28:05,860
要潜入酒吧空间。

606
00:28:05,860 --> 00:28:08,405
但更糟糕的是，事实证明
出这么长的时间，

607
00:28:08,405 --> 00:28:11,530
即使我们从来没有谈过
它的堆栈用于其他的东西。

608
00:28:11,530 --> 00:28:13,560
这不只是局部变量。

609
00:28:13,560 --> 00:28:15,100
>> C是一个非常低的水平的语言。

610
00:28:15,100 --> 00:28:17,810
排序，并偷偷
使用堆栈也

611
00:28:17,810 --> 00:28:21,260
要记住，当
函数被调用，什么

612
00:28:21,260 --> 00:28:26,040
地址是以前的功能，
因此它可以跳转回该功能。

613
00:28:26,040 --> 00:28:29,980
因此，当主呼叫交换，其中
的事情压入堆栈

614
00:28:29,980 --> 00:28:34,380
不只是交换局部变量，
或者它的参数，还偷偷推

615
00:28:34,380 --> 00:28:37,510
入堆栈为代表
这里由红切片，

616
00:28:37,510 --> 00:28:40,520
是主要的地址物理
在计算机的内存，

617
00:28:40,520 --> 00:28:44,180
这样，当交换完成时，计算机
知道我需要回到主

618
00:28:44,180 --> 00:28:46,760
并完成执行的主要功能。

619
00:28:46,760 --> 00:28:51,960
所以，现在这样是很危险的，因为如果
中公比你好更多的用户类型，

620
00:28:51,960 --> 00:28:57,030
使得用户的输入则会覆盖
或将覆盖红色的部分，

621
00:28:57,030 --> 00:28:59,820
逻辑上，如果计算机的
只是要盲目地承担

622
00:28:59,820 --> 00:29:03,830
在这片红色的字节
地址到它应该返回，

623
00:29:03,830 --> 00:29:09,020
如果对手是足够聪明或
幸运地把字节序列

624
00:29:09,020 --> 00:29:13,450
还有，看起来像一个地址，
但它的代码的地址

625
00:29:13,450 --> 00:29:18,730
他或她想要的计算机
而不是主要的执行？

626
00:29:18,730 --> 00:29:21,670
>> 换句话说，如果什么
用户在提示符下敲入，

627
00:29:21,670 --> 00:29:23,850
不只是一些
无害喜欢你好，

628
00:29:23,850 --> 00:29:28,210
但它实际上代码是等价
删除所有该用户的文件？

629
00:29:28,210 --> 00:29:30,060
或者通过电子邮件发送密码到我吗？

630
00:29:30,060 --> 00:29:31,940
或者，开始记录自己的
按键，对不对？

631
00:29:31,940 --> 00:29:34,920
有一种方法，让我们今天的规定，
他们可以输入不只是打招呼

632
00:29:34,920 --> 00:29:36,711
世界还是他们的名字，
他们可能根本

633
00:29:36,711 --> 00:29:39,570
通过在代码中，零和
的，该计算机

634
00:29:39,570 --> 00:29:43,450
错误的代码和一个地址。

635
00:29:43,450 --> 00:29:48,950
因此，尽管有些抽象，如果
足够的对抗代码用户类型

636
00:29:48,950 --> 00:29:52,330
我们将归纳这里
答：是的攻击或敌对。

637
00:29:52,330 --> 00:29:53,140
所以只要坏的东西。

638
00:29:53,140 --> 00:29:55,306
我们不关心
数字或零或1

639
00:29:55,306 --> 00:29:59,470
今天，这样你最终
覆盖的红色款，

640
00:29:59,470 --> 00:30:01,580
请注意字节的顺序。

641
00:30:01,580 --> 00:30:05,020
Ø835℃零八零。

642
00:30:05,020 --> 00:30:08,960
现在，维基百科的文章在这里
建议，如果你现在居然开始

643
00:30:08,960 --> 00:30:12,460
标签在您的计算机中的字节
内存，维基百科的文章是什么

644
00:30:12,460 --> 00:30:19,060
的提出的是，如果有什么的地址
除此之外左字节为80℃0 3508。

645
00:30:19,060 --> 00:30:22,200
>> 换句话说，如果坏家伙是
与他或她的代码足够聪明

646
00:30:22,200 --> 00:30:26,650
实际上把一些在这里，
对应于编码的地址

647
00:30:26,650 --> 00:30:29,180
他或她注入
插入电脑，你

648
00:30:29,180 --> 00:30:31,050
可以欺骗计算机
为做任何事情。

649
00:30:31,050 --> 00:30:34,140
删除文件，电子邮件
事，嗅探您的流量，

650
00:30:34,140 --> 00:30:36,710
从字面上什么事情都可能会
注入到计算机。

651
00:30:36,710 --> 00:30:39,220
所以缓冲区溢出
进攻的核心

652
00:30:39,220 --> 00:30:43,530
仅仅是一个愚蠢，愚蠢
数组压倒一切的

653
00:30:43,530 --> 00:30:45,840
没有它的边界检查。

654
00:30:45,840 --> 00:30:48,850
这是什么是超级危险
同时超级强大

655
00:30:48,850 --> 00:30:52,560
在C是，我们确实有
访问在存储器的任何位置。

656
00:30:52,560 --> 00:30:55,320
这取决于我们的程序员，
谁写的原代码

657
00:30:55,320 --> 00:30:59,330
检查所有的织补长度
阵列，我们正在操纵。

658
00:30:59,330 --> 00:31:00,750
所以要清楚，有什么解决？

659
00:31:00,750 --> 00:31:03,190
如果我们回滚到该
代码，我不应该只是

660
00:31:03,190 --> 00:31:08,000
改变杆的长度，什么
别的我应该检查？

661
00:31:08,000 --> 00:31:10,620
还有什么我应该做的到
防止这种攻击完全？

662
00:31:10,620 --> 00:31:14,110
我不想只是一味地说
你要复制的字节数

663
00:31:14,110 --> 00:31:16,140
作为是条的长度。

664
00:31:16,140 --> 00:31:18,910
我想说，复制为
许多字节都在酒吧

665
00:31:18,910 --> 00:31:24,090
向上到分配
存储器，或12最大限度。

666
00:31:24,090 --> 00:31:27,450
所以，我需要某种形式的if条件
，做检查吧的长度，

667
00:31:27,450 --> 00:31:32,800
但如果超过12，我们只是硬编码
12的最大可能距离。

668
00:31:32,800 --> 00:31:35,910
否则所谓缓冲
溢出攻击可能发生。

669
00:31:35,910 --> 00:31:38,451
在这些幻灯片的底部，
如果你好奇阅读更多

670
00:31:38,451 --> 00:31:41,200
是真正的原创文章
如果你想看看。

671
00:31:41,200 --> 00:31:44,550
>> 但现在，其中的价格
在这里付出了效率低下。

672
00:31:44,550 --> 00:31:46,680
所以这是一个快速
低水平看看什么

673
00:31:46,680 --> 00:31:49,709
现在出现的问题，我们
有权访问的计算机的存储器中。

674
00:31:49,709 --> 00:31:51,750
但另一个问题，我们
已经迷迷糊糊周一

675
00:31:51,750 --> 00:31:53,800
这仅仅是低效率
的一个链表。

676
00:31:53,800 --> 00:31:56,019
我们又回到了线性时间。

677
00:31:56,019 --> 00:31:57,560
我们不再有一个连续的数组。

678
00:31:57,560 --> 00:31:58,980
我们没有随机访问。

679
00:31:58,980 --> 00:32:00,710
我们不能用方括号。

680
00:32:00,710 --> 00:32:04,590
我们实际上不得不使用whil​​e循环
像我刚才写的。

681
00:32:04,590 --> 00:32:09,740
但在周一，我们宣称我们能
悄悄放回效率的境界

682
00:32:09,740 --> 00:32:13,040
实现东西是
对数也许，或者最好的是，

683
00:32:13,040 --> 00:32:16,120
甚至东西是
所谓一定时间。

684
00:32:16,120 --> 00:32:19,840
那么，如何才能做到这一点通过使用这些新的
工具，这些地址，这些指针，

685
00:32:19,840 --> 00:32:22,210
和线程我们自己的东西呢？

686
00:32:22,210 --> 00:32:23,960
好吧，假设
在这里，这些都是一堆

687
00:32:23,960 --> 00:32:27,170
我们要存储在数字
高效的数据结构和搜索。

688
00:32:27,170 --> 00:32:30,960
我们完全可以后退到周
二，把这些放到一个数组，

689
00:32:30,960 --> 00:32:33,150
并使用二进制搜索寻找他们。

690
00:32:33,150 --> 00:32:34,040
分而治之。

691
00:32:34,040 --> 00:32:37,720
而事实上，你写的
在PSET3二进制搜索，

692
00:32:37,720 --> 00:32:40,100
在那里你实现find程序。

693
00:32:40,100 --> 00:32:40,890
但是你知道吗。

694
00:32:40,890 --> 00:32:45,060
还有一种更
这样做的聪明的方式。

695
00:32:45,060 --> 00:32:47,390
这是一个有点多
成熟，它可能

696
00:32:47,390 --> 00:32:50,830
让我们看到了为什么二进制
搜索是如此之快。

697
00:32:50,830 --> 00:32:52,980
首先，我们来介绍
树的概念。

698
00:32:52,980 --> 00:32:54,730
其中，即使在
样的现实树

699
00:32:54,730 --> 00:32:57,730
成长就是这样，在计算机世界
学他们那种向下生长

700
00:32:57,730 --> 00:33:00,830
就像一个家庭树，在这里你有
你的祖父母或曾祖父母

701
00:33:00,830 --> 00:33:04,580
或者诸如此类的东西在上面，族长和
家族的女家长，只有一个

702
00:33:04,580 --> 00:33:07,930
所谓根，节点，下面
这是它的孩子，

703
00:33:07,930 --> 00:33:11,442
下面这是它的孩子，或
它的后代更普遍。

704
00:33:11,442 --> 00:33:13,400
任何人都挂
家庭的底部

705
00:33:13,400 --> 00:33:16,070
树，除了是
最年轻的家庭，

706
00:33:16,070 --> 00:33:19,520
也可以只是一般
称为树的叶子。

707
00:33:19,520 --> 00:33:21,800
>> 因此，这只是一堆
词和定义

708
00:33:21,800 --> 00:33:25,790
对于一些所谓电脑一棵树
科学，就像一个家庭树。

709
00:33:25,790 --> 00:33:28,770
但是，还有票友变身
的树木，其中之一

710
00:33:28,770 --> 00:33:30,780
被称为一个二分搜索树。

711
00:33:30,780 --> 00:33:34,380
你可以种挑逗
除了这个东西做什么。

712
00:33:34,380 --> 00:33:37,180
那么，它的二进制在什么意义？

713
00:33:37,180 --> 00:33:41,455
哪里二进制从何而来吗？

714
00:33:41,455 --> 00:33:41,955
对不起？

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
这与其说是一个非此即彼的。

717
00:33:47,210 --> 00:33:52,000
它更，每个节点具有无
两个以上的孩子，我们在这里看到。

718
00:33:52,000 --> 00:33:54,990
在一般情况下，一个tree--和
你的父母和祖父母

719
00:33:54,990 --> 00:33:57,640
可以有很多孩子或
孙子，因为他们真正想要的，

720
00:33:57,640 --> 00:34:00,820
所以比如有，我们有三个
关闭该右手节点的孩子，

721
00:34:00,820 --> 00:34:05,480
但在一个二叉树，一个节点具有
零个，一个或两个孩子最大限度。

722
00:34:05,480 --> 00:34:08,496
这是一个很好的属性，
因为如果它的上限由二，

723
00:34:08,496 --> 00:34:10,620
我们将能够
得到一点点的日志基地二期

724
00:34:10,620 --> 00:34:11,975
行动回事大势所趋。

725
00:34:11,975 --> 00:34:13,350
因此，我们有一些东西对数。

726
00:34:13,350 --> 00:34:14,558
但是，更详细的介绍了一下。

727
00:34:14,558 --> 00:34:19,810
搜索树指数是
布置成使得左孩子的

728
00:34:19,810 --> 00:34:22,429
值大于根。

729
00:34:22,429 --> 00:34:26,010
而它的右子是
比根大。

730
00:34:26,010 --> 00:34:29,290
换句话说，如果你把所有的
节点，在这张照片中圈，

731
00:34:29,290 --> 00:34:31,840
并期待在其左
儿童和其右孩子，

732
00:34:31,840 --> 00:34:34,739
第一应小于，
第二应大于。

733
00:34:34,739 --> 00:34:36,159
因此，合理性检查55。

734
00:34:36,159 --> 00:34:37,780
它的左子是33。

735
00:34:37,780 --> 00:34:38,620
它的不足。

736
00:34:38,620 --> 00:34:40,929
55，其右孩子是77。

737
00:34:40,929 --> 00:34:41,783
它是大于。

738
00:34:41,783 --> 00:34:43,199
这是一个递归定义。

739
00:34:43,199 --> 00:34:46,480
我们可以检查每个人的那些
节点和相同的图案将举行。

740
00:34:46,480 --> 00:34:49,389
>> 那么什么是不错的
二叉搜索树，是

741
00:34:49,389 --> 00:34:52,204
这一块，我们可以实现它
有一个结构，就这样。

742
00:34:52,204 --> 00:34:54,620
而且即使我们扔
很多结构在你的，

743
00:34:54,620 --> 00:34:56,560
他们是有点
直观现在有希望。

744
00:34:56,560 --> 00:35:00,570
语法仍然是神秘的肯定，
但一个节点在该内容

745
00:35:00,570 --> 00:35:02,786
context--和我们保持
使用这个词的节点，

746
00:35:02,786 --> 00:35:04,910
无论是一个矩形
屏幕或圆上，

747
00:35:04,910 --> 00:35:08,970
它只是一些通用的容器，
在这种情况下，一棵树的，像一个

748
00:35:08,970 --> 00:35:11,780
我们看到，我们需要一个整数。
在每个节点

749
00:35:11,780 --> 00:35:15,460
然后我需要两个指点指点
到左子和右子，

750
00:35:15,460 --> 00:35:16,590
分别。

751
00:35:16,590 --> 00:35:20,730
所以这就是我们如何
实现在一个结构。

752
00:35:20,730 --> 00:35:22,315
怎么可能我在代码中实现它？

753
00:35:22,315 --> 00:35:26,730
好吧，让我们快速浏览
看看这个小小的例子。

754
00:35:26,730 --> 00:35:29,820
这不是功能，但我已经
复制并粘贴该结构。

755
00:35:29,820 --> 00:35:33,510
如果我的函数的二进制
搜索树被称为搜索，

756
00:35:33,510 --> 00:35:36,980
而这需要两个参数，
整数N和一个指针

757
00:35:36,980 --> 00:35:41,400
到一个节点，以便一个指向树
或一个指向树的根，

758
00:35:41,400 --> 00:35:43,482
我该如何去寻找N +

759
00:35:43,482 --> 00:35:45,440
嗯，首先，因为我
处理球，

760
00:35:45,440 --> 00:35:46,750
我会做一个全面的检查。

761
00:35:46,750 --> 00:35:54,279
如果树等于等于空，是N
在这棵树还是没有这棵树？

762
00:35:54,279 --> 00:35:55,070
这是不可能的，对不对？

763
00:35:55,070 --> 00:35:56,870
如果我过去的空，
有什么也没有。

764
00:35:56,870 --> 00:35:59,230
我干脆
一味地说，返回false。

765
00:35:59,230 --> 00:36:04,050
如果你给我什么，我当然不能
找到任何数量N.那么还有什么可能我

766
00:36:04,050 --> 00:36:04,750
现在检查？

767
00:36:04,750 --> 00:36:12,830
我会说好东西如果N
小于任何位于树节点

768
00:36:12,830 --> 00:36:16,300
我一直在流传N值。

769
00:36:16,300 --> 00:36:20,270
换句话说，如果数字我
寻找，N，小于节点

770
00:36:20,270 --> 00:36:21,340
那我看。

771
00:36:21,340 --> 00:36:23,190
和节点我期待
在被称为树，

772
00:36:23,190 --> 00:36:26,370
和前面的例子召回
得到的价值指针，

773
00:36:26,370 --> 00:36:28,310
我用的是箭头符号。

774
00:36:28,310 --> 00:36:35,960
因此，如果N小于树箭头
N，我想概念去左边。

775
00:36:35,960 --> 00:36:38,590
我如何搜索明示离开？

776
00:36:38,590 --> 00:36:41,560
需要明确的是，如果这是
图片中的问题，

777
00:36:41,560 --> 00:36:44,612
我已经过了那个最上面
箭头指针下降。

778
00:36:44,612 --> 00:36:45,570
这是我的树指针。

779
00:36:45,570 --> 00:36:48,060
我指着树的根。

780
00:36:48,060 --> 00:36:52,100
我期待说，对于
数44，随意。

781
00:36:52,100 --> 00:36:55,300
比44少或
超过55显然更大？

782
00:36:55,300 --> 00:36:56,360
所以这是不到。

783
00:36:56,360 --> 00:36:58,760
所以这一点，如果条件适用。

784
00:36:58,760 --> 00:37:03,981
所以概念上，我该怎么想
搜索下一个，如果我在寻找44？

785
00:37:03,981 --> 00:37:04,480
是吗？

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> 没错，我想
搜索左子，

788
00:37:11,100 --> 00:37:12,789
或该图象的左侧的子树。

789
00:37:12,789 --> 00:37:14,830
而事实上，让我通过
图片到这里

790
00:37:14,830 --> 00:37:17,770
就一下，因为
我也不会划伤了这一点。

791
00:37:17,770 --> 00:37:21,150
如果我从这里开始在55，和
我知道，值44

792
00:37:21,150 --> 00:37:23,180
我在寻找是
左边的，它是一种

793
00:37:23,180 --> 00:37:26,010
像撕开电话簿
一半或撕裂树的一半。

794
00:37:26,010 --> 00:37:29,660
我不再去在乎
这整个树的一半。

795
00:37:29,660 --> 00:37:33,270
然而，奇怪的是在条款
结构，这件事情在这里

796
00:37:33,270 --> 00:37:36,682
始于33，这本身
是二叉查找树。

797
00:37:36,682 --> 00:37:39,890
我之前说的，因为这个词递归
的确这是一个数据结构，它

798
00:37:39,890 --> 00:37:41,707
顾名思义就是递归。

799
00:37:41,707 --> 00:37:44,540
你可能有一个树是这个
大，但它的每一个孩子

800
00:37:44,540 --> 00:37:46,870
代表一棵树只是有点小。

801
00:37:46,870 --> 00:37:50,910
而不是它是爷爷
或奶奶，现在它只是妈妈

802
00:37:50,910 --> 00:37:54,300
or--我不能say--没有妈妈
或爸爸，那将是不可思议。

803
00:37:54,300 --> 00:37:59,000
相反，两个孩子有
会像兄弟和姐妹。

804
00:37:59,000 --> 00:38:01,120
新一代的家族树。

805
00:38:01,120 --> 00:38:02,900
但在结构上，这是同样的想法。

806
00:38:02,900 --> 00:38:06,790
而事实证明，我有一个函数
与我可以搜索二进制搜索

807
00:38:06,790 --> 00:38:07,290
树。

808
00:38:07,290 --> 00:38:08,680
这就是所谓的搜索。

809
00:38:08,680 --> 00:38:17,870
我在树的箭头左边搜索对于N
否则，如果N大于该值

810
00:38:17,870 --> 00:38:18,870
我目前在。

811
00:38:18,870 --> 00:38:20,800
55中的故事刚才。

812
00:38:20,800 --> 00:38:23,780
我有一个调用的函数
搜索，我可以只

813
00:38:23,780 --> 00:38:29,660
通过N本和递归搜索
子树和刚刚回归

814
00:38:29,660 --> 00:38:30,620
不管这个答案。

815
00:38:30,620 --> 00:38:33,530
否则我这里有一些最后的基本情况。

816
00:38:33,530 --> 00:38:35,310
>> 是什么最终的情况？

817
00:38:35,310 --> 00:38:36,570
树为null。

818
00:38:36,570 --> 00:38:39,980
我现在不是在寻找的价值
比小于它或更大

819
00:38:39,980 --> 00:38:42,610
或等于它。

820
00:38:42,610 --> 00:38:44,750
而且我可以说等于
相等，但在逻辑上是

821
00:38:44,750 --> 00:38:46,500
相当于只是说人在这里。

822
00:38:46,500 --> 00:38:49,150
所以，真正的是我找到的东西。

823
00:38:49,150 --> 00:38:51,710
因此，希望这是一个
更引人注目的例子

824
00:38:51,710 --> 00:38:54,900
比愚蠢的西格玛功能
我们做了一些讲课回来，

825
00:38:54,900 --> 00:38:58,360
其中，使用循环是一样简单
计算了从一个所有的数字

826
00:38:58,360 --> 00:39:02,390
为N.这里用的数据结构
这本身就是递归

827
00:39:02,390 --> 00:39:07,050
定义和递归拉，现在我们
要表达自己的能力

828
00:39:07,050 --> 00:39:09,780
在代码本身是递归的。

829
00:39:09,780 --> 00:39:12,580
因此，这是这里的完全相同的代码。

830
00:39:12,580 --> 00:39:14,400
>> 所以，我们能解决什么其他的问题？

831
00:39:14,400 --> 00:39:18,160
因此，一个快人一步远离
树木只是一瞬间。

832
00:39:18,160 --> 00:39:20,130
这里，说，德国国旗。

833
00:39:20,130 --> 00:39:22,020
还有的显然是一个
模式这个标志。

834
00:39:22,020 --> 00:39:23,811
而且还有很多的
在世界上的标志是

835
00:39:23,811 --> 00:39:27,560
是这么简单的条件
它们的颜色和图案。

836
00:39:27,560 --> 00:39:31,930
但是，假如这个存储为
.gif或JPEG格式，或位图或平，

837
00:39:31,930 --> 00:39:34,240
任何图形文件格式
与你熟悉，

838
00:39:34,240 --> 00:39:36,460
其中一些我们
在PSET4玩。

839
00:39:36,460 --> 00:39:41,550
这似乎并不值得保存
黑色像素，黑色像素，黑像素，

840
00:39:41,550 --> 00:39:44,790
点，点，点，一大堆
黑色像素的第一扫描线，

841
00:39:44,790 --> 00:39:47,430
或行，然后一大堆
同样的，然后一大堆

842
00:39:47,430 --> 00:39:49,530
的相同，然后一个
一大堆的红色像素，

843
00:39:49,530 --> 00:39:53,020
红像素，红色像素，然后整体
一束黄色的像素，黄色的，对不对？

844
00:39:53,020 --> 00:39:55,050
>> 有这样的效率在这里。

845
00:39:55,050 --> 00:39:59,040
你将如何直观地
压缩德国国旗

846
00:39:59,040 --> 00:40:01,320
如果其实现为一个文件？

847
00:40:01,320 --> 00:40:04,940
像什么信息能不
懒得为了存储在磁盘上

848
00:40:04,940 --> 00:40:08,040
从喜欢减少我们的文件大小
一兆字节到千字节，东西

849
00:40:08,040 --> 00:40:09,430
小？

850
00:40:09,430 --> 00:40:13,130
其中位于冗余
这里要清楚？

851
00:40:13,130 --> 00:40:13,880
你该怎么办？

852
00:40:13,880 --> 00:40:14,380
是吗？

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
没错。

855
00:40:21,970 --> 00:40:24,550
为什么不，而不是记住
每一次缝补像素的颜色

856
00:40:24,550 --> 00:40:28,200
就像你做的PSET4
与位图文件格式，

857
00:40:28,200 --> 00:40:32,060
你为什么不只是代表
像素的最左边的列，例如

858
00:40:32,060 --> 00:40:35,370
一堆黑色像素，一串
红，和一堆黄色，

859
00:40:35,370 --> 00:40:39,210
然后不知怎么竟编码
重复这个想法100倍

860
00:40:39,210 --> 00:40:41,020
或者重复这个1000倍？

861
00:40:41,020 --> 00:40:43,430
其中100或者1000是
只是一个整数，所以你

862
00:40:43,430 --> 00:40:47,290
可以逃脱只是一个单一的数字
而不是数百或数千

863
00:40:47,290 --> 00:40:48,270
的追加像素。

864
00:40:48,270 --> 00:40:50,990
事实上，这就是我们如何
可以压缩的德国国旗。

865
00:40:50,990 --> 00:40:51,490
和

866
00:40:51,490 --> 00:40:53,470
现在来谈谈法国国旗？

867
00:40:53,470 --> 00:40:58,930
还有一点某种
脑力锻炼，这标志

868
00:40:58,930 --> 00:41:01,040
可以压缩更多的磁盘上？

869
00:41:01,040 --> 00:41:05,720
德国国旗或法国的
标志，如果我们采取这种做法？

870
00:41:05,720 --> 00:41:08,490
德国国旗，因为有
更水平的冗余。

871
00:41:08,490 --> 00:41:12,190
而在设计上，许多图形文件
格式确实工作作为扫描线

872
00:41:12,190 --> 00:41:12,830
水平。

873
00:41:12,830 --> 00:41:14,674
他们可以工作
垂直，只是人类

874
00:41:14,674 --> 00:41:17,090
决定多年前，我们会
一般认为事情排

875
00:41:17,090 --> 00:41:18,880
由行，而不是逐列。

876
00:41:18,880 --> 00:41:20,820
所以，事实上，如果你是
看文件

877
00:41:20,820 --> 00:41:24,670
德国国旗和法国的大小
标志，只要分辨率

878
00:41:24,670 --> 00:41:27,530
相同的，相同的宽度
和高度，这其中

879
00:41:27,530 --> 00:41:31,580
这里将是更大，因为你
不得不重复自己的三倍。

880
00:41:31,580 --> 00:41:35,570
你必须指定蓝色，重复
自己，白，重复自己，红色，

881
00:41:35,570 --> 00:41:36,740
重复自己。

882
00:41:36,740 --> 00:41:39,000
你不能只是全力以赴
的方式向右边。

883
00:41:39,000 --> 00:41:41,200
和作为一旁，以使
清除压缩

884
00:41:41,200 --> 00:41:43,910
无处不在，如果这些
从video--四个帧您

885
00:41:43,910 --> 00:41:45,890
可能还记得，影片
或视频一般是

886
00:41:45,890 --> 00:41:47,286
就像每秒29或30帧。

887
00:41:47,286 --> 00:41:50,410
这就像一个小翻转书，你
只是看到图像，图像，图像，图像，

888
00:41:50,410 --> 00:41:54,410
图像只是超级快，所以它看起来像
屏幕上的演员们动人。

889
00:41:54,410 --> 00:41:57,130
这里有一个大黄蜂
一束花的顶部。

890
00:41:57,130 --> 00:41:59,790
虽然它可能是一种
很难看到的第一眼，

891
00:41:59,790 --> 00:42:04,020
唯一移动
这部电影是蜜蜂。

892
00:42:04,020 --> 00:42:06,880
>> 什么是愚蠢的有关存储
视频解压缩？

893
00:42:06,880 --> 00:42:11,420
这是一种浪费存储视频
四个几乎相同的图像，

894
00:42:11,420 --> 00:42:13,670
不同仅仅是因为那里的蜂。

895
00:42:13,670 --> 00:42:16,280
你可以扔掉最
该信息

896
00:42:16,280 --> 00:42:20,190
只记得，例如，
第一帧和最后一帧，

897
00:42:20,190 --> 00:42:22,180
如果你的关键帧
听说过这个词，

898
00:42:22,180 --> 00:42:24,337
而只是存储在
中间那里的蜂。

899
00:42:24,337 --> 00:42:26,170
而你也不必
存储所有的粉红色，

900
00:42:26,170 --> 00:42:28,330
和蓝色，并在该
绿色价值观为好。

901
00:42:28,330 --> 00:42:31,200
因此，这是只说
压缩是无处不在。

902
00:42:31,200 --> 00:42:34,900
这是一个技术，我们经常使用
或者认为理所当然，这些天。

903
00:42:34,900 --> 00:42:38,750
>> 但是你如何压缩文本？

904
00:42:38,750 --> 00:42:40,450
你怎么去压缩的文本？

905
00:42:40,450 --> 00:42:45,410
那么，每一个人物的
ascii的是一个字节或八个比特。

906
00:42:45,410 --> 00:42:47,360
这就是那种愚蠢的，对不对？

907
00:42:47,360 --> 00:42:51,160
因为你可能A型
而E和I和O和U很多

908
00:42:51,160 --> 00:42:55,270
往往比像W或Q或Z，
根据所用的语言

909
00:42:55,270 --> 00:42:56,610
你写的肯定。

910
00:42:56,610 --> 00:42:59,600
所以我们为什么要使用
八位的每一个字母，

911
00:42:59,600 --> 00:43:02,040
包括最不
流行的信，对不对？

912
00:43:02,040 --> 00:43:05,300
为什么不使用较少的位
超人气的信件，

913
00:43:05,300 --> 00:43:07,760
像E，你猜的东西
首先在命运之轮，

914
00:43:07,760 --> 00:43:10,450
并使用更多的比特用于
冷门信吗？

915
00:43:10,450 --> 00:43:10,950
为什么呢？

916
00:43:10,950 --> 00:43:13,130
因为我们只是要
使用这些较不频繁。

917
00:43:13,130 --> 00:43:15,838
>> 嗯，事实证明，有有
已经提出这样做​​的尝试。

918
00:43:15,838 --> 00:43:18,630
如果你的等级召回
学校或高中，莫尔斯电码。

919
00:43:18,630 --> 00:43:20,400
莫尔斯电码具有点
和破折号，可以

920
00:43:20,400 --> 00:43:24,270
沿导线作为发送
声音或某种信号。

921
00:43:24,270 --> 00:43:25,930
但摩尔斯电码是一个超级干净。

922
00:43:25,930 --> 00:43:29,010
这是怎样的一个双星系统中
你必须点或破折号。

923
00:43:29,010 --> 00:43:30,977
但是，如果你看到，例如，两个点。

924
00:43:30,977 --> 00:43:33,810
或者，如果你想给操作
谁是这样嘟，嘟，嘟，

925
00:43:33,810 --> 00:43:36,760
蜂鸣声，创下了小触发
该发送信号，

926
00:43:36,760 --> 00:43:40,360
如果，接收方，接收两个
点，你有没有收到什么样的信息？

927
00:43:40,360 --> 00:43:43,490
完全是任意的。

928
00:43:43,490 --> 00:43:44,450
>> 一世？

929
00:43:44,450 --> 00:43:45,060
一世？

930
00:43:45,060 --> 00:43:47,500
还是什么about--还是我？

931
00:43:47,500 --> 00:43:49,570
也许这只是二号E的吧？

932
00:43:49,570 --> 00:43:52,480
因此，有这个问题
可解码与莫尔斯

933
00:43:52,480 --> 00:43:54,890
代码，从而除非
人向您发送消息

934
00:43:54,890 --> 00:43:59,510
实际上暂停，因此您可以排序的
看到或听到的字母之间的差距，

935
00:43:59,510 --> 00:44:02,990
这是不够的只是
送的零和一的流，

936
00:44:02,990 --> 00:44:05,610
或者点和线，
因为有歧义。

937
00:44:05,610 --> 00:44:08,640
E是一个点，因此，如果您
看到两个点或听到两个点，

938
00:44:08,640 --> 00:44:11,254
也许这两架E的或者它的One I.

939
00:44:11,254 --> 00:44:13,670
因此，我们需要一个系统，是一个
小比这更聪明。

940
00:44:13,670 --> 00:44:16,851
所以叫一个人霍夫曼年
前想出正是这一点。

941
00:44:16,851 --> 00:44:18,600
因此，我们只是要
采取快速浏览

942
00:44:18,600 --> 00:44:20,114
如何树是有密切关系这一点。

943
00:44:20,114 --> 00:44:22,530
假设这是一些
要发送愚蠢的消息，

944
00:44:22,530 --> 00:44:26,342
只是A，B组成，C的D'和E的，
但有很多冗余这里。

945
00:44:26,342 --> 00:44:27,550
这并不意味着是英语。

946
00:44:27,550 --> 00:44:28,341
这不是加密的。

947
00:44:28,341 --> 00:44:30,540
这只是一个愚蠢的消息
有很多重复。

948
00:44:30,540 --> 00:44:34,010
所以，如果你真的算出来的所有
A的，B公司，C公司，D的，和E的，这里的

949
00:44:34,010 --> 00:44:34,890
频率。

950
00:44:34,890 --> 00:44:37,800
字母的20％是
A的，字母的45％

951
00:44:37,800 --> 00:44:39,660
为E的，和其他三个频率。

952
00:44:39,660 --> 00:44:41,960
我们人手点算在那里
而只是做数学。

953
00:44:41,960 --> 00:44:44,579
>> 所以，事实证明，
霍夫曼，前一段时间，

954
00:44:44,579 --> 00:44:46,620
意识到这一点，你知道
什么，如果我开建

955
00:44:46,620 --> 00:44:51,172
一棵树，或森林的树木，如果你愿意，
如下所示，我可以做以下。

956
00:44:51,172 --> 00:44:53,880
我想给一个节点到每个
我关心的字母

957
00:44:53,880 --> 00:44:55,530
我要去存储
该节点的内

958
00:44:55,530 --> 00:44:58,610
频率作为一个浮点
值，或者你可以使用它的N，也

959
00:44:58,610 --> 00:45:00,210
但是我们只用一个浮点数在这里。

960
00:45:00,210 --> 00:45:03,100
而算法
他提出的是你

961
00:45:03,100 --> 00:45:07,210
借此森林单个节点
树木，所以超短树，

962
00:45:07,210 --> 00:45:11,920
你开始与连接它们
新的群体，新的父母，如果你愿意。

963
00:45:11,920 --> 00:45:16,150
而你做到这一点，选择
两个最小频率的时间。

964
00:45:16,150 --> 00:45:18,110
于是，我花了10％和10％。

965
00:45:18,110 --> 00:45:19,090
我创建了一个新的节点。

966
00:45:19,090 --> 00:45:20,910
而我所说的新节点20％。

967
00:45:20,910 --> 00:45:22,750
>> 这两个节点结合我下？

968
00:45:22,750 --> 00:45:23,810
这是一个有点暧昧。

969
00:45:23,810 --> 00:45:26,643
因此，有一些角落情况下
考虑，而是让事情变得漂亮，

970
00:45:26,643 --> 00:45:29,300
我会选择20％ - 
我现在忽略了孩子。

971
00:45:29,300 --> 00:45:33,640
我会选择20％
15％和绘制两条新边。

972
00:45:33,640 --> 00:45:35,624
而现在这两个节点
我逻辑组合？

973
00:45:35,624 --> 00:45:38,540
忽略所有的孩子，所有的
孙子，只看根

974
00:45:38,540 --> 00:45:39,070
现在。

975
00:45:39,070 --> 00:45:42,220
这两个节点我绑在一起？

976
00:45:42,220 --> 00:45:44,530
第二点和0.35。

977
00:45:44,530 --> 00:45:45,890
因此，让我得出两个新的边缘。

978
00:45:45,890 --> 00:45:47,570
然后，我只有一个了。

979
00:45:47,570 --> 00:45:48,650
因此，这里的一棵树。

980
00:45:48,650 --> 00:45:51,160
而且它被画刻意
看那种漂亮，

981
00:45:51,160 --> 00:45:55,870
但是请注意，边缘有
也被贴上零和一。

982
00:45:55,870 --> 00:45:59,510
因此，所有的左边缘都为零
随意，但始终。

983
00:45:59,510 --> 00:46:01,170
所有的右侧边缘的那些。

984
00:46:01,170 --> 00:46:05,070
>> 还等什么霍夫曼提出，
如果要表示B，

985
00:46:05,070 --> 00:46:10,080
而不是表示数字66作为
一个ascii其长度为八个整位，

986
00:46:10,080 --> 00:46:13,360
你知道吗，刚刚店
图案零，零，零，

987
00:46:13,360 --> 00:46:17,030
零，因为这是路径
从我的树，霍夫曼先生的树，

988
00:46:17,030 --> 00:46:18,600
从根叶。

989
00:46:18,600 --> 00:46:20,970
如果你想存储
E，相比之下，不

990
00:46:20,970 --> 00:46:26,290
发送代表E.八位
相反，派位的是什么模式？

991
00:46:26,290 --> 00:46:26,890
一。

992
00:46:26,890 --> 00:46:30,410
什么是好的关于这
E是最流行的字母，

993
00:46:30,410 --> 00:46:32,340
而你正在使用的
最短的代码吧。

994
00:46:32,340 --> 00:46:34,090
接下来最流行
信看起来

995
00:46:34,090 --> 00:46:37,380
是A.所以，有多少位
他才建议用是什么？

996
00:46:37,380 --> 00:46:38,270
零点一。

997
00:46:38,270 --> 00:46:41,060
>> 而且因为它的实现
因为这棵树，现在

998
00:46:41,060 --> 00:46:43,350
让我规定有
无歧义的莫尔斯

999
00:46:43,350 --> 00:46:46,090
码，因为所有的
你关心的信

1000
00:46:46,090 --> 00:46:48,780
是在这些边缘的末端。

1001
00:46:48,780 --> 00:46:50,580
所以，这只是一个
应用一棵树。

1002
00:46:50,580 --> 00:46:52,538
这is--我会波
我的手在这你如何

1003
00:46:52,538 --> 00:46:55,570
有可能实现这是一个C结构。

1004
00:46:55,570 --> 00:46:58,260
我们只需要结合
一个符号，就像一个char，

1005
00:46:58,260 --> 00:46:59,910
和在频率左右。

1006
00:46:59,910 --> 00:47:02,510
但是，让我们看两个
最后的例子，你会

1007
00:47:02,510 --> 00:47:06,070
得到相当熟悉后，
测验零习题集五位。

1008
00:47:06,070 --> 00:47:09,210
>> 因此，有该数据结构
称为哈希表。

1009
00:47:09,210 --> 00:47:12,247
而一个哈希表是怎么样的
冷却在于它具有水桶。

1010
00:47:12,247 --> 00:47:14,830
假设有四个桶
在这里，只有四个空格。

1011
00:47:14,830 --> 00:47:20,830
下面是一副扑克牌，并在这里被
俱乐部，铁锹，俱乐部，钻石，俱乐部，

1012
00:47:20,830 --> 00:47:25,960
钻石，俱乐部，钻石，
clubs--所以这是随机的。

1013
00:47:25,960 --> 00:47:30,330
心，hearts--所以我
bucketizing所有输入这里。

1014
00:47:30,330 --> 00:47:32,430
而一个哈希表的需求
看你的输入​​，

1015
00:47:32,430 --> 00:47:34,850
然后把它放在一个特定的
基于你所看到的地方。

1016
00:47:34,850 --> 00:47:35,600
这是一个算法。

1017
00:47:35,600 --> 00:47:37,980
而我使用的是超
简单的视觉算法。

1018
00:47:37,980 --> 00:47:40,030
其中最困难的部分是
记住哪些图片是。

1019
00:47:40,030 --> 00:47:41,590
再有就是总共四个东西。

1020
00:47:41,590 --> 00:47:45,440
>> 现在堆栈的长势，这
是故意设计的东西在这里。

1021
00:47:45,440 --> 00:47:46,540
还有什么我可以做什么？

1022
00:47:46,540 --> 00:47:49,080
所以实际上我们在这里有一个
一群老同学考试用书。

1023
00:47:49,080 --> 00:47:51,240
假设一堆
学生的名字都在这里。

1024
00:47:51,240 --> 00:47:52,570
这里有一个更大的哈希表。

1025
00:47:52,570 --> 00:47:54,867
而不是四个桶，
我有，比方说26。

1026
00:47:54,867 --> 00:47:57,950
我们不想去借钱26
从外面[事情？安嫩伯格？]，所以

1027
00:47:57,950 --> 00:48:00,289
这里共有五次代表
A到Z.如果我

1028
00:48:00,289 --> 00:48:03,580
看到学生的名称以A，
我打算把他或她的测验那里。

1029
00:48:03,580 --> 00:48:08,850
如果有人以C开头，在那里，
A--实际上，并不想这样做。

1030
00:48:08,850 --> 00:48:10,060
B进入到这里。

1031
00:48:10,060 --> 00:48:13,390
所以，我有A和B和C和
现在这里的另一个学生。

1032
00:48:13,390 --> 00:48:16,212
但是，如果这个散列表是
以与阵列实现，

1033
00:48:16,212 --> 00:48:17,920
我有点拧
在这一点上，对不对？

1034
00:48:17,920 --> 00:48:19,510
那种我需要把这个地方。

1035
00:48:19,510 --> 00:48:24,380
>> 因此，我可以解决这个问题的一个方法是，所有的
没错，A占线，B忙，C忙。

1036
00:48:24,380 --> 00:48:28,880
我打算把他D.因此，在
首先，我有随机即时访问

1037
00:48:28,880 --> 00:48:31,064
每个桶的学生。

1038
00:48:31,064 --> 00:48:33,230
但是，现在这是一种下放
弄成线性的，

1039
00:48:33,230 --> 00:48:36,750
因为如果我要寻找的人
其名称开头，我点击这里。

1040
00:48:36,750 --> 00:48:38,854
但如果不是这种甲
学生，我正在寻找，

1041
00:48:38,854 --> 00:48:41,520
那种我要开始检查
水桶，因为我做了什么

1042
00:48:41,520 --> 00:48:44,530
是那种线性
探测数据结构。

1043
00:48:44,530 --> 00:48:47,710
一个说笨方法只是看
第一个可用的开放，

1044
00:48:47,710 --> 00:48:51,850
并把作为一个B计划，可以这么说，
或者在这种情况下的计划D，则值

1045
00:48:51,850 --> 00:48:53,340
在该位置代替。

1046
00:48:53,340 --> 00:48:56,470
这仅仅是这样，如果你已经
有26个地点，并没有学生

1047
00:48:56,470 --> 00:49:00,600
名为Q或Z或喜欢的事
即，至少你正在使用的空间。

1048
00:49:00,600 --> 00:49:03,140
>> 但是，我们已经看到了更多的
聪明的解决方案，在这里，对不对？

1049
00:49:03,140 --> 00:49:04,870
你会怎么做，而不是
如果你有一个碰撞？

1050
00:49:04,870 --> 00:49:06,670
如果两个人有
该名称的，会是什么

1051
00:49:06,670 --> 00:49:09,160
是一个更聪明或更
直观的解决方案不仅仅是

1052
00:49:09,160 --> 00:49:12,840
把一个其中D应该是？

1053
00:49:12,840 --> 00:49:14,810
为什么不让我走
外[？安嫩伯格？]

1054
00:49:14,810 --> 00:49:19,960
喜欢的malloc，另一个节点，把它
在这里，然后把这里的学生。

1055
00:49:19,960 --> 00:49:22,120
所以，我基本上是有
一些类型的数组，，

1056
00:49:22,120 --> 00:49:25,590
或者更优雅的，因为我们是
开始看到一个链表。

1057
00:49:25,590 --> 00:49:29,520
>> 因此一个哈希表的结构
这可能看起来就像这样，

1058
00:49:29,520 --> 00:49:33,900
但更聪明，你的东西被称为
分离链，从而哈希表

1059
00:49:33,900 --> 00:49:38,340
很简单，是一个数组，每个
其元素不是数字，

1060
00:49:38,340 --> 00:49:40,470
本身是一个链表。

1061
00:49:40,470 --> 00:49:45,080
使您获得超快速访问
决定在哪里你的价值散列到。

1062
00:49:45,080 --> 00:49:48,059
就像用卡的例子，
我做了超级快速决策。

1063
00:49:48,059 --> 00:49:49,600
心放在这里，钻石放在这里。

1064
00:49:49,600 --> 00:49:52,180
同样在这里，一个放在这里，
ð放在这里，B放在这里。

1065
00:49:52,180 --> 00:49:55,740
因此，超快速的查找窗口，如果
你碰巧遇到一个案例

1066
00:49:55,740 --> 00:49:59,429
在这里你有碰撞，二
人具有相同的名称，以及再

1067
00:49:59,429 --> 00:50:00,970
你刚开始把它们连接起来。

1068
00:50:00,970 --> 00:50:03,900
也许你让他们排序
按字母顺序，也许你不知道。

1069
00:50:03,900 --> 00:50:05,900
但至少现在我们有活力。

1070
00:50:05,900 --> 00:50:10,250
因此，一方面，我们有超级快
固定的时间和形式的线性时间

1071
00:50:10,250 --> 00:50:14,110
如果这些链表参与
开始变得有点长。

1072
00:50:14,110 --> 00:50:16,880
>> 因此，这种愚蠢的，
令人讨厌的笑话年前。

1073
00:50:16,880 --> 00:50:19,590
在CS50黑客马拉松，
当学生入住，

1074
00:50:19,590 --> 00:50:22,040
一些TF或CA每年
认为这是有趣忍受

1075
00:50:22,040 --> 00:50:27,772
像这样的一个标志，它只是
也就是说，如果你的名字开始与A，

1076
00:50:27,772 --> 00:50:28,870
走这条路。

1077
00:50:28,870 --> 00:50:31,110
如果你的名字开始
用A，B，去this-- OK，

1078
00:50:31,110 --> 00:50:33,290
这很有趣，也许在以后的学期。

1079
00:50:33,290 --> 00:50:36,420
但是，还有一个
这样，太的方式。

1080
00:50:36,420 --> 00:50:37,410
回过头来的。

1081
00:50:37,410 --> 00:50:38,600
>> 因此，有这种结构。

1082
00:50:38,600 --> 00:50:40,420
这是我们最后一次
结构的今天，

1083
00:50:40,420 --> 00:50:42,400
这是一些所谓的线索。

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E，这对于某些原因是短
检索，但它被称为线索。

1085
00:50:47,140 --> 00:50:51,389
因此，一个线索是另一个有趣
汞合金很多这样的想法。

1086
00:50:51,389 --> 00:50:52,930
这是一棵树，这是我们以前见过。

1087
00:50:52,930 --> 00:50:54,180
这不是一个二叉搜索树。

1088
00:50:54,180 --> 00:50:58,410
这是一个树的任何数量的孩子，
但每一个线索的孩子

1089
00:50:58,410 --> 00:51:00,090
是一个数组。

1090
00:51:00,090 --> 00:51:04,790
大小的数组，说，26或者27
如果你想支持复姓名字

1091
00:51:04,790 --> 00:51:06,790
还是在人的名字撇号。

1092
00:51:06,790 --> 00:51:08,280
>> 所以这是一个数据结构。

1093
00:51:08,280 --> 00:51:10,290
而如果你从上
到底，就像如果你

1094
00:51:10,290 --> 00:51:13,710
顶一下节点有，男，是
指向左边的事情存在，

1095
00:51:13,710 --> 00:51:17,665
然后将其A，X，W，E，L，L。这是
只是一种数据结构，任意地

1096
00:51:17,665 --> 00:51:19,120
是存储人的名字。

1097
00:51:19,120 --> 00:51:25,720
和麦克斯韦是刚刚以下存储
数组的数组阵列的路径。

1098
00:51:25,720 --> 00:51:30,050
但令人惊讶的有关线索是
如此，而一个链表，甚至

1099
00:51:30,050 --> 00:51:34,520
一个数组，我们曾经得到的最好的是
线性时间或对数时间寻找

1100
00:51:34,520 --> 00:51:35,600
有人了。

1101
00:51:35,600 --> 00:51:40,530
在一个线索的此数据结构中，如果
我的数据结构中有一个名字

1102
00:51:40,530 --> 00:51:43,720
而我在寻找麦克斯韦，我
要找到他很快。

1103
00:51:43,720 --> 00:51:47,910
我只是寻找M-A-X-W-E-L-L。是否
此数据结构中，通过对比，

1104
00:51:47,910 --> 00:51:51,830
如果N是一百万，如果有一个
在这种数据结构万个名字，

1105
00:51:51,830 --> 00:51:57,100
麦克斯韦仍然将是
发现刚刚M-A-X-W-E-L-L后

1106
00:51:57,100 --> 00:51:58,090
脚步。

1107
00:51:58,090 --> 00:52:01,276
而David-- D-A-V-I-D的步骤。

1108
00:52:01,276 --> 00:52:03,400
换句话说，通过建立
一种数据结构，是

1109
00:52:03,400 --> 00:52:07,240
得到了所有这些阵列的，所有这些都
本身支持随机访问，

1110
00:52:07,240 --> 00:52:11,090
我可以开始寻找达人的
使用的时候这是一个量的名字

1111
00:52:11,090 --> 00:52:14,340
成比例的数量不限
的东西，在数据结构中，

1112
00:52:14,340 --> 00:52:16,330
像一百万现有名称。

1113
00:52:16,330 --> 00:52:20,135
花费的时间我找的金额
的M-A-X-W-E-L-L的这种数据结构是

1114
00:52:20,135 --> 00:52:22,260
比例不到
的数据结构的大小，

1115
00:52:22,260 --> 00:52:25,930
但对名称的长度。

1116
00:52:25,930 --> 00:52:28,440
而现实的
名字我们仰视

1117
00:52:28,440 --> 00:52:29,970
永远不会长疯了。

1118
00:52:29,970 --> 00:52:32,600
也许有人有10个字符
名，20个字符的名称。

1119
00:52:32,600 --> 00:52:33,900
这当然是有限的，对不对？

1120
00:52:33,900 --> 00:52:37,110
有地球上的人谁
有最长可能的名称，

1121
00:52:37,110 --> 00:52:39,920
但这个名字是一个常数
值长，对不对？

1122
00:52:39,920 --> 00:52:41,980
它并不在任何意义上有所不同。

1123
00:52:41,980 --> 00:52:45,090
因此，在这种方式中，我们
实现了数据结构

1124
00:52:45,090 --> 00:52:47,800
这是恒定的时间查找。

1125
00:52:47,800 --> 00:52:50,670
它采取了一些措施
根据输入的长度，

1126
00:52:50,670 --> 00:52:54,250
的名字，但没有数量
在数据结构中。

1127
00:52:54,250 --> 00:52:58,700
因此，如果我们加倍名的数量
从十亿一二十亿明年，

1128
00:52:58,700 --> 00:53:03,720
发现麦克斯韦是要采取
的七个步骤完全相同的数

1129
00:53:03,720 --> 00:53:04,650
找到他。

1130
00:53:04,650 --> 00:53:08,810
因此，我们似乎已经达到
我们神圣的运行时间的法宝。

1131
00:53:08,810 --> 00:53:10,860
>> 因此，一对夫妇的快速公告。

1132
00:53:10,860 --> 00:53:11,850
测验零快到了。

1133
00:53:11,850 --> 00:53:14,600
更多的是在球场上的网站
在接下来的几天。

1134
00:53:14,600 --> 00:53:17,120
周一的lecture--这是一个节日
你们是哈佛在星期一。

1135
00:53:17,120 --> 00:53:18,850
这不是在纽黑文，
所以我们采取了类

1136
00:53:18,850 --> 00:53:20,310
纽黑文的演讲在星期一。

1137
00:53:20,310 --> 00:53:22,550
一切都将被拍摄下来，
和流现场像往常一样，

1138
00:53:22,550 --> 00:53:24,900
但让今天的结束
用30秒的剪辑

1139
00:53:24,900 --> 00:53:26,910
所谓的“深度思考”
通过Daven法纳姆，这

1140
00:53:26,910 --> 00:53:30,850
在周六的启发，去年
夜直播的“深度思考”

1141
00:53:30,850 --> 00:53:35,700
杰克得心应手，这
现在应该是有意义的。

1142
00:53:35,700 --> 00:53:38,810
>> 电影：现在，“深
思考“由Daven法纳姆。

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
哈希表。

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> 扬声器1：好吧，这就是它了。

1147
00:53:47,660 --> 00:53:48,805
我们会看到你下周。

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> 道格：要看到它在行动。

1150
00:53:56,680 --> 00:53:58,304
所以，让我们来看看这个现在。

1151
00:53:58,304 --> 00:53:59,890
所以在这里，我们有一个排序的数组。

1152
00:53:59,890 --> 00:54:04,860
>> IAN：道格，你能继续前进，重新启动
这只是一秒，请。

1153
00:54:04,860 --> 00:54:08,562
好吧，相机滚动，所以
的动作，当你准备好，道格，好不好？

1154
00:54:08,562 --> 00:54:11,020
道格：好的，所以我们
这里是一个未排序的数组。

1155
00:54:11,020 --> 00:54:13,960
我也有色的所有元素
红色，以表明它是，事实上，

1156
00:54:13,960 --> 00:54:14,460
未分类。

1157
00:54:14,460 --> 00:54:17,960
所以记得的第一件事情，我们做的
是我们排序阵列的左半。

1158
00:54:17,960 --> 00:54:20,630
然后我们排序的权利
一半的阵列。

1159
00:54:20,630 --> 00:54:22,830
雅达，雅，达，雅，达，
我们把它们合并起来。

1160
00:54:22,830 --> 00:54:24,520
我们有一个完全排序的数组。

1161
00:54:24,520 --> 00:54:25,360
所以这是如何归并排序工作。

1162
00:54:25,360 --> 00:54:27,109
>> IAN：哇，哇，哇，
切，切，切，切。

1163
00:54:27,109 --> 00:54:30,130
道格，你不能随便亚达，雅，达，
雅-DA，通过归并排序的方式。

1164
00:54:30,130 --> 00:54:31,970
>> 道格：我只是做了。

1165
00:54:31,970 --> 00:54:32,832
没关系。

1166
00:54:32,832 --> 00:54:33,540
我们是好去。

1167
00:54:33,540 --> 00:54:34,760
我们只是不停地滚动。

1168
00:54:34,760 --> 00:54:35,380
所以无论如何，

1169
00:54:35,380 --> 00:54:37,800
>> 伊恩：你有解释
它比更充分。

1170
00:54:37,800 --> 00:54:39,999
这只是还不够。

1171
00:54:39,999 --> 00:54:41,790
道格：伊恩，我们不
需要回去之一。

1172
00:54:41,790 --> 00:54:42,350
没关系。

1173
00:54:42,350 --> 00:54:45,690
所以无论如何，如果我们继续merge--
伊恩，我们在拍戏的中间。

1174
00:54:45,690 --> 00:54:46,612
>> 伊恩：我知道。

1175
00:54:46,612 --> 00:54:49,320
我们不能只是亚达，雅，达，
雅-DA，通过全过程。

1176
00:54:49,320 --> 00:54:52,200
你必须解释为什么
双方得到合并在一起。

1177
00:54:52,200 --> 00:54:53,570
>> 道格：但我们已经
解释了两个sides--

1178
00:54:53,570 --> 00:54:55,321
>> 伊恩：你刚才表示
他们合并数组。

1179
00:54:55,321 --> 00:54:56,486
道格：他们知道这个过程。

1180
00:54:56,486 --> 00:54:57,172
他们是很好。

1181
00:54:57,172 --> 00:54:58,380
我们已经讨论了10次，

1182
00:54:58,380 --> 00:55:00,330
>> 伊恩：你刚才跳过权权。

1183
00:55:00,330 --> 00:55:03,360
我们要回一个，你
不能你丫达，雅，达权。

1184
00:55:03,360 --> 00:55:05,480
好了，回到之一。

1185
00:55:05,480 --> 00:55:07,833
>> 道格：我要回去
通过所有的幻灯片？

1186
00:55:07,833 --> 00:55:08,332
我的上帝。

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
这就像第六次，伊恩。

1189
00:55:13,004 --> 00:55:13,940
没关系。

1190
00:55:13,940 --> 00:55:15,200
>> 伊恩：好的。

1191
00:55:15,200 --> 00:55:16,590
你准备好了吗？

1192
00:55:16,590 --> 00:55:17,400
太好了。

1193
00:55:17,400 --> 00:55:18,950
动作。