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

2
00:00:00,500 --> 00:00:11,137
[音乐播放]

3
00:00:11,137 --> 00:00:12,220
戴维·J·马兰：好吧。

4
00:00:12,220 --> 00:00:13,950
这是CS50。

5
00:00:13,950 --> 00:00:18,560
这是本周五继续进行，我们
有一些好消息和一些坏消息。

6
00:00:18,560 --> 00:00:21,140
好消息是，CS50
推出这个星期五。

7
00:00:21,140 --> 00:00:24,430
如果您想加入我们的行列，
前往这里平时的网址。

8
00:00:24,430 --> 00:00:28,670
更好的消息，没有演讲
下星期一13日。

9
00:00:28,670 --> 00:00:31,970
略显不足更好的消息，
测验零点下周三。

10
00:00:31,970 --> 00:00:33,840
更多细节可
在这个网址找到这里。

11
00:00:33,840 --> 00:00:36,340
而在接下来的几天
我们将填补空白

12
00:00:36,340 --> 00:00:39,234
与问候房间
我们将有保留。

13
00:00:39,234 --> 00:00:41,400
更好的消息是，有将
是一个过程性的检讨

14
00:00:41,400 --> 00:00:43,570
会议即将来临
周一晚上。

15
00:00:43,570 --> 00:00:46,270
敬请关注过程的
网站的定位和细节。

16
00:00:46,270 --> 00:00:49,290
部分，即使它是一个
假期，也将满足为好。

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
最好的消息，讲课下周五。

19
00:00:52,940 --> 00:00:56,220
因此，这是一个传统，我们
有，按照教学大纲。

20
00:00:56,220 --> 00:00:58,100
只是 - 这将是惊人的。

21
00:00:58,100 --> 00:01:02,510
你会看到类似的东西
固定时间的数据结构

22
00:01:02,510 --> 00:01:04,730
和哈希表和树和尝试。

23
00:01:04,730 --> 00:01:07,150
我们将谈论的生日问题。

24
00:01:07,150 --> 00:01:09,440
一大堆的东西
等待下周五。

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
行。

27
00:01:12,200 --> 00:01:13,190
总之。

28
00:01:13,190 --> 00:01:17,080
>> 所以，记得，我们已经
重点是这幅画的是什么

29
00:01:17,080 --> 00:01:18,980
我们内部的计算机内存。

30
00:01:18,980 --> 00:01:22,875
这样存储器或RAM是其中的程序
你正在运行他们，而存在的。

31
00:01:22,875 --> 00:01:25,215
如果你双击一个
图标来运行一些程序

32
00:01:25,215 --> 00:01:27,520
或双击
图标打开某些文件，

33
00:01:27,520 --> 00:01:30,430
它是从硬盘加载
驱动器或固态驱动器

34
00:01:30,430 --> 00:01:34,190
到RAM中，随机存取存储器，其中
它生活，直到电源关闭，

35
00:01:34,190 --> 00:01:36,700
笔记本电脑的盖子关闭，
或者你退出程序。

36
00:01:36,700 --> 00:01:38,960
>> 现在，记忆，
你可能有

37
00:01:38,960 --> 00:01:41,950
1 GB的这些天，2
千兆字节，甚至更多，

38
00:01:41,950 --> 00:01:44,420
一般布局
对于一个给定的程序

39
00:01:44,420 --> 00:01:47,170
在这种长方形的
概念模型

40
00:01:47,170 --> 00:01:50,860
由此我们有堆叠在底部
并在顶部一堆其他的东西。

41
00:01:50,860 --> 00:01:53,140
在最高层的事
我们已经看到这个画面

42
00:01:53,140 --> 00:01:55,670
之前，但从来没有说过
是所谓的文本段。

43
00:01:55,670 --> 00:01:58,419
文段仅仅是一个奇特的方式
的话说，零和一的

44
00:01:58,419 --> 00:02:01,150
撰写您的实际编译的程序。

45
00:02:01,150 --> 00:02:03,910
>> 所以，当你双击
微软的Word在您的Mac或PC，

46
00:02:03,910 --> 00:02:08,030
或者当您运行点斜线马里奥在
Linux计算机在终端窗口中，

47
00:02:08,030 --> 00:02:12,460
构成该零和一
字或马里奥被暂时存储

48
00:02:12,460 --> 00:02:16,610
在所谓的计算机的RAM
文本段对特定的程序。

49
00:02:16,610 --> 00:02:19,080
下面说去初始化
和未初始化的数据。

50
00:02:19,080 --> 00:02:22,655
这东西像全局变量，
我们已经不能用了许多，

51
00:02:22,655 --> 00:02:24,910
但有时，我们已经
有全局变量

52
00:02:24,910 --> 00:02:28,819
或静态定义的字符串
是硬编码，如“你好”的话

53
00:02:28,819 --> 00:02:31,860
未从用户采取
被硬编码到程序中。

54
00:02:31,860 --> 00:02:34,230
>> 现在，倒在底部我们
有所谓的堆栈。

55
00:02:34,230 --> 00:02:37,665
和栈，迄今为止，我们已经
采用了什么样的目的？

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
什么是栈被用来做什么？

58
00:02:40,997 --> 00:02:41,160
是吗？

59
00:02:41,160 --> 00:02:42,070
>> 听众：功能。

60
00:02:42,070 --> 00:02:43,320
>> 戴维·J·马兰：功能？

61
00:02:43,320 --> 00:02:44,980
在什么意义上的功能呢？

62
00:02:44,980 --> 00:02:48,660
>> 听众：当你调用一个函数时，
参数复制到堆栈中。

63
00:02:48,660 --> 00:02:49,660
>> 戴维·J·马兰：没错。

64
00:02:49,660 --> 00:02:52,650
当你调用一个函数，它的
参数复制到堆栈中。

65
00:02:52,650 --> 00:02:56,330
因此，某X的或Y的或A或B的
那你传递给函数

66
00:02:56,330 --> 00:02:58,680
暂时放在
所谓堆栈，

67
00:02:58,680 --> 00:03:02,000
就像安尼伯格之一
食堂托盘，也事

68
00:03:02,000 --> 00:03:03,190
如局部变量。

69
00:03:03,190 --> 00:03:06,290
如果你的富功能或您的交换
函数有局部变量，

70
00:03:06,290 --> 00:03:08,602
如温度，这两个
最终在堆栈中。

71
00:03:08,602 --> 00:03:11,560
现在，我们不会过多谈论
他们，但这些环境变量

72
00:03:11,560 --> 00:03:15,690
在底部，我们看到前一段时间，当
我把玩在键盘1天

73
00:03:15,690 --> 00:03:20,050
我开始访问事
像argv的100 ARGV 1,000

74
00:03:20,050 --> 00:03:22,320
只是elements--我忘了
在numbers--但

75
00:03:22,320 --> 00:03:24,330
不应该由我来访问。

76
00:03:24,330 --> 00:03:26,581
我们开始看到一些
时髦的符号在屏幕上。

77
00:03:26,581 --> 00:03:28,330
这些都是所谓的
环境变量

78
00:03:28,330 --> 00:03:32,390
像全局设置我的
程序或我的电脑，而不是

79
00:03:32,390 --> 00:03:37,090
无关的最近
错误，我们所讨论的，

80
00:03:37,090 --> 00:03:39,670
Shellshock，这一直
困扰着不少电脑。

81
00:03:39,670 --> 00:03:42,960
>> 现在，最后，在今天的重点
我们最终会在堆中。

82
00:03:42,960 --> 00:03:44,864
这是记忆另一个块。

83
00:03:44,864 --> 00:03:47,030
从根本上这一切
内存是同样的东西。

84
00:03:47,030 --> 00:03:48,040
这是同样的硬件。

85
00:03:48,040 --> 00:03:49,956
我们只是有点
对待不同的集群

86
00:03:49,956 --> 00:03:51,460
的字节用于不同的目的。

87
00:03:51,460 --> 00:03:56,540
堆也将会是在哪里
您请求的变量和内存

88
00:03:56,540 --> 00:03:58,810
从操作系统
被暂时存储。

89
00:03:58,810 --> 00:04:01,890
>> 但有样的问题
这里，作为图像暗示。

90
00:04:01,890 --> 00:04:05,261
我们的排序有两个
关于船舶碰撞。

91
00:04:05,261 --> 00:04:08,010
因为当你使用越来越多
堆栈，并作为我们今天看到的

92
00:04:08,010 --> 00:04:11,800
以后，当你使用更多的多
堆，肯定不好的事情可能会发生。

93
00:04:11,800 --> 00:04:15,054
事实上，我们可以归纳出
有意或无意的。

94
00:04:15,054 --> 00:04:16,970
所以最后扣人心弦
时间是这个程序，

95
00:04:16,970 --> 00:04:20,570
这并没有起到任何功能
目的除了展示

96
00:04:20,570 --> 00:04:24,750
如何为坏家伙竟然可以
利用漏洞在别人的程序

97
00:04:24,750 --> 00:04:28,460
并接管程序，甚至是
整个计算机系统或服务器。

98
00:04:28,460 --> 00:04:31,660
所以只是简单地一瞥，你
请注意，主底部

99
00:04:31,660 --> 00:04:34,510
需要在命令行
参数，按ARGV。

100
00:04:34,510 --> 00:04:38,480
它有一个调用一个函数f，
基本上叫做匿名函数

101
00:04:38,480 --> 00:04:40,250
f和它传递的argv [1]。

102
00:04:40,250 --> 00:04:43,960
>> 因此，在任何字的用户类型
这个节目的名字后，在提示，

103
00:04:43,960 --> 00:04:49,310
然后这个任意函数了
顶，F，需要一个字符串，又名char *的，

104
00:04:49,310 --> 00:04:51,720
因为我们已经开始讨论，
它只是将其称为“巴”。

105
00:04:51,720 --> 00:04:53,310
但我们可以把它叫做什么。

106
00:04:53,310 --> 00:04:57,470
然后它声明，里面
楼字符数组的

107
00:04:57,470 --> 00:04:59,930
所谓C-- 12这样的人物。

108
00:04:59,930 --> 00:05:03,580
>> 现在，这个故事我告诉
刚才，在内存

109
00:05:03,580 --> 00:05:06,720
为c，或者是那些12
字符要结束了？

110
00:05:06,720 --> 00:05:07,570
只是要清楚。

111
00:05:07,570 --> 00:05:08,070
是吗？

112
00:05:08,070 --> 00:05:08,590
>> 听众：在堆栈中。

113
00:05:08,590 --> 00:05:09,420
>> 戴维·J·马兰：在堆栈中。

114
00:05:09,420 --> 00:05:10,720
所以C是一个局部变量。

115
00:05:10,720 --> 00:05:14,079
我们要求12个字符或12个字节。

116
00:05:14,079 --> 00:05:16,120
那些将要结束了
在所谓的堆栈。

117
00:05:16,120 --> 00:05:18,530
现在终于这等功能
这实际上是相当有用的，

118
00:05:18,530 --> 00:05:20,571
但我们还没有真正使用
它自己，strncopy。

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
这意味着字符串拷贝，但
n只有字母，n个字符。

121
00:05:25,200 --> 00:05:31,990
因此，n个字符会
从酒吧复制成C。

122
00:05:31,990 --> 00:05:32,980
又有多少呢？

123
00:05:32,980 --> 00:05:34,110
条的长度。

124
00:05:34,110 --> 00:05:36,330
因此，换句话说，即
一条线，strncopy，

125
00:05:36,330 --> 00:05:39,500
将要复制
在有效的禁止到c。

126
00:05:39,500 --> 00:05:42,340
>> 现在，只是一种预测
这个故事的寓意，

127
00:05:42,340 --> 00:05:44,750
什么是潜在的问题在这里吗？

128
00:05:44,750 --> 00:05:49,710
尽管我们正在检查的长度
酒吧，并向其传递到strncopy，

129
00:05:49,710 --> 00:05:53,145
什么是你的直觉告诉你的是
还是打破这个计划？

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
是吗？

132
00:05:55,220 --> 00:05:57,491
>> 听众：不包括
房间空字符。

133
00:05:57,491 --> 00:05:59,990
戴维·J·马兰：不包括
房间空字符。

134
00:05:59,990 --> 00:06:02,073
潜在地，不像在
过去的实践中，我们甚至不

135
00:06:02,073 --> 00:06:04,810
有这么多的加1
容纳空字符。

136
00:06:04,810 --> 00:06:06,649
但比这更糟糕。

137
00:06:06,649 --> 00:06:07,940
还有什么是我们不能做什么？

138
00:06:07,940 --> 00:06:08,432
是吗？

139
00:06:08,432 --> 00:06:09,307
>> 听众：[听不清]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
戴维·J·马兰：完美。

142
00:06:16,440 --> 00:06:18,490
我们已经硬编码的12相当随意。

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
这是没有这么多的
的问题，但事实

145
00:06:21,330 --> 00:06:25,630
我们甚至不检查，如果
条的长度是小于12，

146
00:06:25,630 --> 00:06:28,530
在这种情况下，这将是
安全地把它放入内存

147
00:06:28,530 --> 00:06:30,260
我们已经分配名为c。

148
00:06:30,260 --> 00:06:32,960
事实上，如果酒吧是像
20个字符长，

149
00:06:32,960 --> 00:06:39,010
这个功能似乎被复制
从酒吧到C，使20个字符

150
00:06:39,010 --> 00:06:41,310
服用至少8个字节
它不应该。

151
00:06:41,310 --> 00:06:42,690
这是这里的含义。

152
00:06:42,690 --> 00:06:44,347
>> 因此，在短期，断程序。

153
00:06:44,347 --> 00:06:45,180
没有什么大不了的。

154
00:06:45,180 --> 00:06:46,360
也许你会得到一个段错误。

155
00:06:46,360 --> 00:06:47,651
我们都有过在程序中的bug。

156
00:06:47,651 --> 00:06:50,196
我们都可能有缺陷
在节目现在。

157
00:06:50,196 --> 00:06:51,320
但是，有什么寓意？

158
00:06:51,320 --> 00:06:54,390
嗯，这里是一个放大版本
那张照片是我的电脑的内存中。

159
00:06:54,390 --> 00:06:56,230
这是我的堆栈的底部。

160
00:06:56,230 --> 00:06:59,644
事实上，在最底层是什么
所谓的母常规堆栈，奇特的方式

161
00:06:59,644 --> 00:07:00,560
的话说，就是主。

162
00:07:00,560 --> 00:07:03,772
所以，无论谁调用的函数
˚F，我们正在谈论的。

163
00:07:03,772 --> 00:07:05,230
所以这是堆栈的底部。

164
00:07:05,230 --> 00:07:06,640
返回地址是新的东西。

165
00:07:06,640 --> 00:07:08,810
这是一直存在的，
一直在图片。

166
00:07:08,810 --> 00:07:10,440
我们只是从来没有所谓的重视。

167
00:07:10,440 --> 00:07:15,290
因为事实证明，C工作的方式是
当一个函数调用另一个，

168
00:07:15,290 --> 00:07:18,780
不仅做到了参数的
功能得到压入堆栈，

169
00:07:18,780 --> 00:07:22,470
不仅做到了功能的地方
得到的变量压入堆栈，

170
00:07:22,470 --> 00:07:26,820
一些所谓的返回地址
也被放到堆栈。

171
00:07:26,820 --> 00:07:33,330
特别是，如果主调用f​​oo，主要的
自己的地址在内存中，牛事，

172
00:07:33,330 --> 00:07:38,240
有效地被放置到堆栈
这样，当f为完成执行它

173
00:07:38,240 --> 00:07:43,630
知道在哪里可以跳回到文本
段，以继续执行。

174
00:07:43,630 --> 00:07:47,760
>> 所以，如果我们在这里概念，
在主，则f被调用。

175
00:07:47,760 --> 00:07:50,200
如何˚F知道是谁
以手控回来？

176
00:07:50,200 --> 00:07:52,020
好了，这个小
面包屑红色在这里，

177
00:07:52,020 --> 00:07:54,978
所谓的返回地址，这只是
支票，那是什么的返回地址？

178
00:07:54,978 --> 00:07:57,039
哦，让我跳回到主这里。

179
00:07:57,039 --> 00:07:59,080
这就是一点点
过于简单化的，

180
00:07:59,080 --> 00:08:00,750
因为在零和一
主在技术上

181
00:08:00,750 --> 00:08:01,967
在这里，在高科技领域。

182
00:08:01,967 --> 00:08:03,800
但是，这是这个想法。 ˚F
只是必须知道什么

183
00:08:03,800 --> 00:08:06,680
到控制，最终又回到。

184
00:08:06,680 --> 00:08:09,790
>> 但是，电脑的方式
早就奠定了东西

185
00:08:09,790 --> 00:08:12,320
如局部变量和
论点是这样的。

186
00:08:12,320 --> 00:08:17,180
所以，在这张照片中名列前茅
蓝色是在f的栈帧，因此所有

187
00:08:17,180 --> 00:08:19,630
存储器的使f
特别是使用。

188
00:08:19,630 --> 00:08:22,990
所以因此，请注意
酒吧是在这张照片。

189
00:08:22,990 --> 00:08:23,980
酒吧是它的参数。

190
00:08:23,980 --> 00:08:27,240
我们宣称的参数
功能得到压入堆栈。

191
00:08:27,240 --> 00:08:29,910
和c，当然是
同时在这张照片。

192
00:08:29,910 --> 00:08:33,520
>> 而就在符号上的目的，
注意在顶部左上角

193
00:08:33,520 --> 00:08:37,020
是会什么C支架0
随后小幅回落向右

194
00:08:37,020 --> 00:08:38,220
为c支架11。

195
00:08:38,220 --> 00:08:41,240
所以，换句话说，你可以想像
这有一个字节格

196
00:08:41,240 --> 00:08:44,380
还有，第一个是
左上角，底部其中

197
00:08:44,380 --> 00:08:48,360
是最后的这12个字节。

198
00:08:48,360 --> 00:08:49,930
>> 但现在尽量快进。

199
00:08:49,930 --> 00:08:55,580
什么是即将发生，如果我们通过
在一个字符串中的酒吧，是比C更久？

200
00:08:55,580 --> 00:08:59,130
而且我们不是，如果检查
这的确是超过12。

201
00:08:59,130 --> 00:09:03,146
此图片的一部分是要
得到由字节0，1，2，3覆盖，

202
00:09:03,146 --> 00:09:07,890
点点点，11，然后
糟糕，12，13至19？

203
00:09:07,890 --> 00:09:11,820
什么会发生在这里，
如果从订货推断

204
00:09:11,820 --> 00:09:14,790
将c支架0顶部
和c支架11是有点下降

205
00:09:14,790 --> 00:09:15,812
对吧？

206
00:09:15,812 --> 00:09:16,796
是吗？

207
00:09:16,796 --> 00:09:19,260
>> 听众：嗯，这是怎么回事
覆盖char *的吧。

208
00:09:19,260 --> 00:09:22,260
>> 戴维·J·马兰：是的，它看起来像
你要覆盖char *的吧。

209
00:09:22,260 --> 00:09:26,245
更糟糕的是，如果你发送一个很长的
字符串，你甚至可以覆盖哪些？

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
返回地址。

212
00:09:28,570 --> 00:09:31,380
这再次，就像是
面包屑告诉程序在哪里

213
00:09:31,380 --> 00:09:34,060
在f回去
完成被调用。

214
00:09:34,060 --> 00:09:37,140
>> 那么，什么坏人通常做
是，如果他们遇到一个程序

215
00:09:37,140 --> 00:09:41,290
他们很好奇是否
利用，越野车以这样的方式

216
00:09:41,290 --> 00:09:43,550
他或她可以利用
优点是错误的，

217
00:09:43,550 --> 00:09:45,720
一般他们没有得到
这种权利的第一次。

218
00:09:45,720 --> 00:09:48,590
他们刚开始发送，例如，
随机字符串到你的程序，

219
00:09:48,590 --> 00:09:50,260
是否在键盘
或者坦白地说，他们可能

220
00:09:50,260 --> 00:09:52,740
写一个小程序只是
自动生成的字符串，

221
00:09:52,740 --> 00:09:55,430
并开始通过敲打你的程序
派遣在许多不同的输入

222
00:09:55,430 --> 00:09:56,340
在不同的长度。

223
00:09:56,340 --> 00:09:58,990
>> 只要你的程序崩溃，
这是一个了不起的事情。

224
00:09:58,990 --> 00:10:01,020
因为这意味着他
或她已经发现

225
00:10:01,020 --> 00:10:02,660
什么是可能的确是一个错误。

226
00:10:02,660 --> 00:10:05,830
然后，他们可以得到更聪明
并开始关注更窄

227
00:10:05,830 --> 00:10:07,420
如何利用这个bug。

228
00:10:07,420 --> 00:10:11,480
特别是，他或她可能
要做的就是发送，在最好的情况下，你好。

229
00:10:11,480 --> 00:10:12,210
没什么大不了的。

230
00:10:12,210 --> 00:10:14,750
这是一个字符串，它是足够短。

231
00:10:14,750 --> 00:10:18,100
但是，如果他或她送什么，
我们将其概括为，

232
00:10:18,100 --> 00:10:20,890
攻击代码 - 让零
而那些做的事情

233
00:10:20,890 --> 00:10:25,150
如RM-RF，即去除一切
从硬盘驱动器或发送垃圾邮件

234
00:10:25,150 --> 00:10:27,000
或以某种方式攻击机？

235
00:10:27,000 --> 00:10:29,570
>> 因此，如果每个这些
字母A代表公正，

236
00:10:29,570 --> 00:10:32,380
从概念上讲，攻击，攻击，
攻击，攻击，一些不好的代码

237
00:10:32,380 --> 00:10:36,410
别人写的，但
如果那人是足够聪明

238
00:10:36,410 --> 00:10:40,790
不仅包括所有
那些RM-RFS的，但也

239
00:10:40,790 --> 00:10:46,100
有他或她的最后几个字节
是一个数字，对应

240
00:10:46,100 --> 00:10:50,540
到的地址他
或她自己的攻击代码

241
00:10:50,540 --> 00:10:53,820
他（或她）在刚刚过去的
在提示符下提供的，

242
00:10:53,820 --> 00:10:58,760
可以有效地欺骗电脑
为在f执行完毕注意到，

243
00:10:58,760 --> 00:11:02,400
哦，是时候让我跳
回红返回地址。

244
00:11:02,400 --> 00:11:06,070
但是，因为他或她有莫名其妙
重叠的返回地址

245
00:11:06,070 --> 00:11:09,602
用自己的号码，
而且他们足够聪明

246
00:11:09,602 --> 00:11:11,560
已配置的
数量是指，当你

247
00:11:11,560 --> 00:11:13,740
看到超级顶
左上角有，

248
00:11:13,740 --> 00:11:18,020
在计算机的实际地址
他们的一些攻击代码的内存，

249
00:11:18,020 --> 00:11:21,740
坏人可以欺骗计算机
为执行他或她自己的代码。

250
00:11:21,740 --> 00:11:23,700
>> 而这些代码，再次可以是任何东西。

251
00:11:23,700 --> 00:11:26,120
它通常被称为
shell代码，这仅仅是

252
00:11:26,120 --> 00:11:29,030
的话说，这不是一个办法
通常一些简单的RM-RF。

253
00:11:29,030 --> 00:11:32,340
它实际上是这样猛砸，
或实际的方案，让他

254
00:11:32,340 --> 00:11:37,230
或她的程序控制执行
别的，他们想要。

255
00:11:37,230 --> 00:11:40,210
因此，在短期，这一切
从一个简单的事实推导出

256
00:11:40,210 --> 00:11:44,490
这个错误不涉及检查
阵列的界限。

257
00:11:44,490 --> 00:11:47,250
而由于道路
计算机工作，他们

258
00:11:47,250 --> 00:11:49,430
使用堆栈
有效的，在概念上，

259
00:11:49,430 --> 00:11:54,830
底上了，但随后的元素
你推入堆栈增长自上而下，

260
00:11:54,830 --> 00:11:56,624
这是令人难以置信的问题。

261
00:11:56,624 --> 00:11:58,290
现在，有方法可以解决这个问题。

262
00:11:58,290 --> 00:12:00,800
坦率地说，有语言
与合作解决这个问题。

263
00:12:00,800 --> 00:12:03,100
Java是免疫，例如
这个特定问题。

264
00:12:03,100 --> 00:12:04,110
因为他们不给你指点。

265
00:12:04,110 --> 00:12:05,943
他们不给你
直接内存地址。

266
00:12:05,943 --> 00:12:08,560
因此，与这种力量，我们有
在内存按兵不动

267
00:12:08,560 --> 00:12:11,580
我们要来了，诚然，巨大的风险。

268
00:12:11,580 --> 00:12:12,430
>> 所以留意。

269
00:12:12,430 --> 00:12:14,596
如果坦率地说，在未来数月
或几年来，随时

270
00:12:14,596 --> 00:12:17,740
你读一些开发
中，一个程序或服务器

271
00:12:17,740 --> 00:12:22,370
如果你曾经看到的东西的提示
就像一个缓冲区溢出攻击，

272
00:12:22,370 --> 00:12:25,390
或堆栈溢出是另一种类型
攻击中，在精神上同样，

273
00:12:25,390 --> 00:12:28,770
就像激发网站的
名字，如果你知道的话，

274
00:12:28,770 --> 00:12:33,170
这一切都在谈论刚刚
满溢一些字符的大小

275
00:12:33,170 --> 00:12:36,200
数组或数组中更普遍。

276
00:12:36,200 --> 00:12:38,822
有任何疑问的话，在这？

277
00:12:38,822 --> 00:12:39,780
不要在家里尝试。

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> 好吧。

280
00:12:42,300 --> 00:12:47,270
所以malloc的迄今，我们的新
朋友，我们可以分配内存

281
00:12:47,270 --> 00:12:50,540
我们不一定知道在
前进，我们希望让我们没有

282
00:12:50,540 --> 00:12:52,920
硬编码到我们的
程序号像12。

283
00:12:52,920 --> 00:12:55,550
一旦用户告诉我们有多少
数据他或她想要输入

284
00:12:55,550 --> 00:12:58,000
我们的malloc那么多的记忆。

285
00:12:58,000 --> 00:13:01,484
>> 所以malloc的事实证明，在
程度上，我们一直在使用它，

286
00:13:01,484 --> 00:13:03,900
明确地一次，然后
你们一直在使用它

287
00:13:03,900 --> 00:13:08,160
为的GetString在不知不觉中进行
数周后，所有的malloc的内存的

288
00:13:08,160 --> 00:13:09,820
来自于所谓的堆。

289
00:13:09,820 --> 00:13:13,852
这就是为什么GetString的，例如
可以动态地分配内存

290
00:13:13,852 --> 00:13:16,060
不知道你在做什么
将预先输入，

291
00:13:16,060 --> 00:13:21,520
交给你回一个指向内存中，
而且内存还是你留着，

292
00:13:21,520 --> 00:13:24,080
即使在形式返回。

293
00:13:24,080 --> 00:13:27,450
由于召回毕竟该
堆栈是不断上升和下降，

294
00:13:27,450 --> 00:13:27,950
向上和向下。

295
00:13:27,950 --> 00:13:30,230
而一旦它进入
下，这意味着任何存储器

296
00:13:30,230 --> 00:13:33,030
这个功能应该使用
不被其他人使用。

297
00:13:33,030 --> 00:13:34,570
这是垃圾值了。

298
00:13:34,570 --> 00:13:36,120
>> 不过，堆在这里。

299
00:13:36,120 --> 00:13:39,360
这有什么好看的malloc左右是
当这里的malloc分配内存时，

300
00:13:39,360 --> 00:13:42,070
它没有影响，对
大多数情况下，由堆栈。

301
00:13:42,070 --> 00:13:46,000
所以任何函数都可以访问
内存已malloc分配，

302
00:13:46,000 --> 00:13:49,120
甚至像的GetString函数，
即使在它被返回。

303
00:13:49,120 --> 00:13:51,700
>> 现在，的malloc的逆是免费的。

304
00:13:51,700 --> 00:13:53,900
事实上，规则你
需要开始采用

305
00:13:53,900 --> 00:13:58,950
就是有，有，你用malloc任何时间
你必须自己使用免费的，最终，

306
00:13:58,950 --> 00:14:00,280
在同样的指针。

307
00:14:00,280 --> 00:14:03,289
这段时间我们一直在写
越野车，越野车的代码，有很多原因。

308
00:14:03,289 --> 00:14:05,580
但其中一个已
使用CS50库，

309
00:14:05,580 --> 00:14:09,010
本身是故意
越野车，它的内存泄漏。

310
00:14:09,010 --> 00:14:11,410
任何你打电话的GetString时间
在过去的几个星期

311
00:14:11,410 --> 00:14:13,870
我们问工作
系统，Linux的内存。

312
00:14:13,870 --> 00:14:15,780
而你从来没有一次给它回来。

313
00:14:15,780 --> 00:14:17,730
这不，在
练，是一件好事。

314
00:14:17,730 --> 00:14:20,330
>> 和Valgrind的，所述一个
在Pset的4引入的工具，

315
00:14:20,330 --> 00:14:22,900
是所有关于帮助您
现在发现这样的错误。

316
00:14:22,900 --> 00:14:27,060
不过，值得庆幸的是在Pset的4你不需要
使用CS50库或GetString的。

317
00:14:27,060 --> 00:14:31,220
所以涉及到内存中的任何错误都
最终将是你自己。

318
00:14:31,220 --> 00:14:34,060
>> 所以malloc的不仅仅是
方便的用于此目的。

319
00:14:34,060 --> 00:14:37,420
我们其实可以现在解决
从根本上不同的问题，

320
00:14:37,420 --> 00:14:41,640
从根本上解决问题，更
有效地为每周为零的承诺。

321
00:14:41,640 --> 00:14:44,720
到目前为止，这是最性感
数据结构，我们已经有。

322
00:14:44,720 --> 00:14:47,804
并通过数据结构我的意思
概念化记忆的一种方式

323
00:14:47,804 --> 00:14:50,720
在超越只是说一种方法，
这是一个int，这是一个字符。

324
00:14:50,720 --> 00:14:52,930
我们可以开始集群的东西放在一起。

325
00:14:52,930 --> 00:14:54,460
>> 所以数组是这样的。

326
00:14:54,460 --> 00:14:57,270
什么是对的关键
数组是可以让你

327
00:14:57,270 --> 00:14:59,724
备份到后端的块
存储器，其中每个

328
00:14:59,724 --> 00:15:02,765
将是相同的类型，整型，
整型，整型，整型，或CHAR，CHAR，CHAR，

329
00:15:02,765 --> 00:15:03,330
字符。

330
00:15:03,330 --> 00:15:04,496
但是有几个缺点。

331
00:15:04,496 --> 00:15:06,570
此，例如，是
大小6的阵列。

332
00:15:06,570 --> 00:15:10,650
假设你填充这个数组六
数字，然后，不管是什么原因，

333
00:15:10,650 --> 00:15:13,187
您的用户想要得到
你第七号。

334
00:15:13,187 --> 00:15:14,020
你在哪里放呢？

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> 有什么解决办法，如果你有
在堆栈上创建一个数组，

337
00:15:18,990 --> 00:15:22,030
例如，刚与周
2符号，我们介绍了，

338
00:15:22,030 --> 00:15:23,730
方括号与多家里面？

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
好了，你已经有了6
在这些框中的数字。

341
00:15:27,260 --> 00:15:28,530
什么你的直觉是什么？

342
00:15:28,530 --> 00:15:29,973
在那里你会想要把它？

343
00:15:29,973 --> 00:15:30,860
>> 听众：[听不清]

344
00:15:30,860 --> 00:15:31,315
>> 戴维·J·马兰：对不起？

345
00:15:31,315 --> 00:15:32,380
>> 听众：把它放在最后。

346
00:15:32,380 --> 00:15:33,796
>> 戴维·J·马兰：把它放在最后。

347
00:15:33,796 --> 00:15:35,880
所以才过来的吧，
这个盒子的外面。

348
00:15:35,880 --> 00:15:38,710
这将是很好的，但它
事实证明，你不能这样做。

349
00:15:38,710 --> 00:15:41,350
因为如果你没有问
此块的存储器，

350
00:15:41,350 --> 00:15:44,490
这可能是巧合，这
正在使用的一些其它变量

351
00:15:44,490 --> 00:15:45,030
干脆。

352
00:15:45,030 --> 00:15:49,210
回想一个星期左右的时候，我们奠定
出Zamyla和达文和Gabe的名字

353
00:15:49,210 --> 00:15:49,930
在存储器中。

354
00:15:49,930 --> 00:15:51,638
他们从字面上
回背靠背。

355
00:15:51,638 --> 00:15:53,550
所以我们可以不必
相信凡是

356
00:15:53,550 --> 00:15:55,800
在这里是供我使用。

357
00:15:55,800 --> 00:15:56,990
>> 所以，你还有什么可以做？

358
00:15:56,990 --> 00:16:00,282
那么，一旦你实现
要7号的数组，

359
00:16:00,282 --> 00:16:02,490
你可以只创建一个
尺寸7的阵列，然后使用

360
00:16:02,490 --> 00:16:05,950
for循环或while循环，
将其复制到新的数组，

361
00:16:05,950 --> 00:16:09,680
然后不知何故刚刚摆脱
这个阵列或只是停止使用。

362
00:16:09,680 --> 00:16:12,130
但是，这不是特别有效。

363
00:16:12,130 --> 00:16:15,340
总之，阵列别让
您动态调整。

364
00:16:15,340 --> 00:16:17,900
>> 因此，一方面你
随机访问，这是惊人的。

365
00:16:17,900 --> 00:16:20,108
因为它让我们做的事情
如分而治之，

366
00:16:20,108 --> 00:16:23,100
二进制搜索，所有这些我们已经
就在屏幕上谈到。

367
00:16:23,100 --> 00:16:24,950
但是你画自己陷入了困境。

368
00:16:24,950 --> 00:16:27,810
只要你打
您的阵列的结尾，

369
00:16:27,810 --> 00:16:29,980
你要做的很
昂贵的操作

370
00:16:29,980 --> 00:16:33,910
或写一大堆代码
到现在处理这个问题。

371
00:16:33,910 --> 00:16:36,680
>> 所以，如果不是我们有什么
一些所谓的名单，

372
00:16:36,680 --> 00:16:38,820
或链表特别？

373
00:16:38,820 --> 00:16:41,930
有如果，而不是
矩形回背靠背，

374
00:16:41,930 --> 00:16:45,730
我们有长方形的留下一点
回旋余地在他们之间有点？

375
00:16:45,730 --> 00:16:49,670
而且即使我画这个
图片或改编此图片

376
00:16:49,670 --> 00:16:54,696
从文本之一在这里要回
背对背的非常有序，在现实中，

377
00:16:54,696 --> 00:16:56,820
这些矩形之一
可以在这里在存储器中。

378
00:16:56,820 --> 00:16:58,028
其中一人可能是在这里。

379
00:16:58,028 --> 00:17:00,420
其中一人可能是在这里，
在这里，等等。

380
00:17:00,420 --> 00:17:02,910
>> 但是，如果我们画了，
在这种情况下，箭头

381
00:17:02,910 --> 00:17:05,650
不知怎的，这些链接
矩形组合在一起？

382
00:17:05,650 --> 00:17:08,170
事实上，我们已经看到了技术
化身箭头。

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
你有没有看到最近使用
天那，引擎盖底下，

385
00:17:13,710 --> 00:17:15,210
是代表一个箭头的？

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
一个指针，对不对？

388
00:17:17,349 --> 00:17:19,780
>> 那么，如果，而不是
只存储该号码

389
00:17:19,780 --> 00:17:23,130
像9，17，22，26，34，
如果我们不保存

390
00:17:23,130 --> 00:17:27,079
只有一些，但指针
相邻的数目？

391
00:17:27,079 --> 00:17:30,690
所以这就像你会跟帖
针穿过一大堆面料，

392
00:17:30,690 --> 00:17:32,950
不知何故搭售的东西
同时，同样可以

393
00:17:32,950 --> 00:17:35,550
我们使用指针，作为
这里用箭头体现，

394
00:17:35,550 --> 00:17:38,550
种编织在一起
这些单个矩形

395
00:17:38,550 --> 00:17:41,780
通过有效地使用指针
旁边的每个数

396
00:17:41,780 --> 00:17:46,065
指出了一些下一个号码，即
指向，反过来，一些未来数？

397
00:17:46,065 --> 00:17:47,940
因此，换句话说，什么
如果我们真正想要的

398
00:17:47,940 --> 00:17:49,820
实行这样的事情？

399
00:17:49,820 --> 00:17:53,610
好可惜，这些矩形，
至少一个与9，17，22，

400
00:17:53,610 --> 00:17:57,040
等等，这些都不再
漂亮的广场单号。

401
00:17:57,040 --> 00:17:59,960
底部，矩形
以下如图9所示，例如，

402
00:17:59,960 --> 00:18:04,330
代表什么应该
是一个指针，32位。

403
00:18:04,330 --> 00:18:09,460
现在，我还不知道任何数据类型
在C中，让你不仅是一个整数

404
00:18:09,460 --> 00:18:11,630
但指针干脆。

405
00:18:11,630 --> 00:18:15,020
>> 那么，有什么解决方案，如果我们想要
去创造我们自己的答案呢？

406
00:18:15,020 --> 00:18:15,760
是吗？

407
00:18:15,760 --> 00:18:16,640
>> 听众：[听不清]

408
00:18:16,640 --> 00:18:17,360
>> 戴维·J·马兰：这是什么？

409
00:18:17,360 --> 00:18:17,880
>> 对象：新的结构。

410
00:18:17,880 --> 00:18:19,590
>> 戴维·J·马兰：是啊，为什么
我们不创建一个新的结构，

411
00:18:19,590 --> 00:18:20,920
或在C中，一个结构？

412
00:18:20,920 --> 00:18:25,990
我们已经看到结构之前，如果简单地说，
我们处理了一个学生结构

413
00:18:25,990 --> 00:18:27,780
这样，谁的名称和一所房子。

414
00:18:27,780 --> 00:18:31,980
在Pset的3分场您使用了全
一堆structs-- GRect和GOvals的

415
00:18:31,980 --> 00:18:34,810
在斯坦福大学创建的
集群信息一起。

416
00:18:34,810 --> 00:18:38,580
那么，如果我们采取同样的想法
关键字“类型定义”和“结构”

417
00:18:38,580 --> 00:18:42,890
然后一些学生具体的东西，
并演变成以下这样的：

418
00:18:42,890 --> 00:18:46,210
typedef结构node--和节点
只是一个很普通的计算机科学

419
00:18:46,210 --> 00:18:49,980
长期的东西，在数据结构中，
容器中的数据结构。

420
00:18:49,980 --> 00:18:53,900
一个节点我要求都将有
一个整数N，完全明了，

421
00:18:53,900 --> 00:18:58,810
然后多一点隐晦，
这第二条线，结构节点*旁边。

422
00:18:58,810 --> 00:19:01,300
但在更短的技术术语，
什么是第二行

423
00:19:01,300 --> 00:19:02,980
的花括号内的代码？

424
00:19:02,980 --> 00:19:03,737
是吗？

425
00:19:03,737 --> 00:19:04,851
>> 听众：[听不清]

426
00:19:04,851 --> 00:19:06,600
戴维·J·马兰：一
指针到另一个节点。

427
00:19:06,600 --> 00:19:09,910
所以不可否认，语法有点神秘。

428
00:19:09,910 --> 00:19:13,250
但是，如果你从字面上看它，
接下来是一个变量的名称。

429
00:19:13,250 --> 00:19:14,410
什么是它的数据类型？

430
00:19:14,410 --> 00:19:18,206
这是一个有点冗长这个时候，
但它的类型结构节点*。

431
00:19:18,206 --> 00:19:22,960
任何我们已经看到一些明星的时候，也
意味着它是一个指针，它指向的数据类型。

432
00:19:22,960 --> 00:19:26,810
因此，下显然是一个
指针指向一个结构节点。

433
00:19:26,810 --> 00:19:28,310
>> 现在，是一个结构的节点？

434
00:19:28,310 --> 00:19:31,044
好了，请注意您看到的那些
同样的话，在右上角。

435
00:19:31,044 --> 00:19:33,960
事实上，你也看到这个词
“节点”在这儿，在左下角。

436
00:19:33,960 --> 00:19:35,640
这其实只是一个方便。

437
00:19:35,640 --> 00:19:39,930
请注意，在我们学生的定义
有单词“学生”只有一次。

438
00:19:39,930 --> 00:19:42,510
那是因为学生
对象不是自我指涉。

439
00:19:42,510 --> 00:19:45,340
没有什么是学生的内部
需要指向另一名学生，

440
00:19:45,340 --> 00:19:45,610
PerSay的。

441
00:19:45,610 --> 00:19:47,630
这将是某种
怪异在现实世界中。

442
00:19:47,630 --> 00:19:50,880
>> 但在一个节点链接
列表中，我们希望有一个节点

443
00:19:50,880 --> 00:19:53,970
是参考了类似的对象。

444
00:19:53,970 --> 00:19:57,900
等注意到这里的变化是不
只是什么花括号内。

445
00:19:57,900 --> 00:20:00,800
但是我们加上“节点”
在顶部，以及

446
00:20:00,800 --> 00:20:02,930
将其添加至底部
代替“学生”。

447
00:20:02,930 --> 00:20:06,000
而这仅仅是一个技术细节
这样一来，同样，你的数据结构

448
00:20:06,000 --> 00:20:11,380
可自行参照，让
节点可以指向另一个这样的节点。

449
00:20:11,380 --> 00:20:13,840
>> 那么，这是什么最终
将意味着我们呢？

450
00:20:13,840 --> 00:20:17,560
嗯，一，这里面的东西
是我们的节点的内容。

451
00:20:17,560 --> 00:20:19,360
这东西在这里，
右上方，就是这么

452
00:20:19,360 --> 00:20:20,860
即，再次，大家可以参考一下自己。

453
00:20:20,860 --> 00:20:23,401
然后最外面的东西，
即使节点是一个新名词，

454
00:20:23,401 --> 00:20:25,500
也许，它仍然是
一样的学生，什么

455
00:20:25,500 --> 00:20:27,520
在SPL引擎盖下面。

456
00:20:27,520 --> 00:20:31,095
>> 因此，如果我们现在要开始
实施本链表，

457
00:20:31,095 --> 00:20:33,220
怎么可能，我们翻译
像这样的代码？

458
00:20:33,220 --> 00:20:35,350
好吧，让我们看到一个
例如一个程序的

459
00:20:35,350 --> 00:20:36,840
实际使用链表。

460
00:20:36,840 --> 00:20:40,870
在今天的分销代码
是一个名为List零计划。

461
00:20:40,870 --> 00:20:44,980
如果我运行这个，我创建了一个超
简单的图形用户界面，图形用户界面，

462
00:20:44,980 --> 00:20:46,460
但它真的只是printf的。

463
00:20:46,460 --> 00:20:50,930
现在我已经给自己几个菜单
选项​​ - 删除，插入，检索，

464
00:20:50,930 --> 00:20:51,750
和导线。

465
00:20:51,750 --> 00:20:52,630
并退出。

466
00:20:52,630 --> 00:20:55,970
这是一个公正的常用操作
被称为链接列表数据结构。

467
00:20:55,970 --> 00:20:58,409
>> 现在，删除是要
删除了一些从列表中。

468
00:20:58,409 --> 00:21:00,200
插入件的要加
数到列表中。

469
00:21:00,200 --> 00:21:02,181
搜索是要去看看
对于列表中的号码。

470
00:21:02,181 --> 00:21:04,930
和遍历仅仅是一个奇特的方式
的说法，漫步列表，

471
00:21:04,930 --> 00:21:06,245
它打印出来，但仅此而已。

472
00:21:06,245 --> 00:21:07,720
不要以任何方式改变它。

473
00:21:07,720 --> 00:21:08,570
>> 因此，让我们试试这个。

474
00:21:08,570 --> 00:21:10,160
让我们继续前进，2型。

475
00:21:10,160 --> 00:21:12,710
然后我要去
插入的数目，表示9。

476
00:21:12,710 --> 00:21:13,620
输入。

477
00:21:13,620 --> 00:21:17,480
现在我的计划就是
编程来说，列表是现在9。

478
00:21:17,480 --> 00:21:20,190
现在，如果我继续前进，
不要再插入，让

479
00:21:20,190 --> 00:21:23,680
我继续前进，缩小并输入17。

480
00:21:23,680 --> 00:21:25,770
现在我的名单是9，那么17。

481
00:21:25,770 --> 00:21:27,750
如果我做再次插入，让我们跳过之一。

482
00:21:27,750 --> 00:21:32,400
相反22，按照图片中我们已经
一直在看这里，让我跳跃前进

483
00:21:32,400 --> 00:21:34,630
并插入26下一页。

484
00:21:34,630 --> 00:21:36,230
所以，我要输入26。

485
00:21:36,230 --> 00:21:37,755
这份名单是我所期望的。

486
00:21:37,755 --> 00:21:40,630
但现在，只是如果这个代码见
将是灵活的，现在让我

487
00:21:40,630 --> 00:21:43,520
型22，其中至少有
从概念上讲，如果我们

488
00:21:43,520 --> 00:21:46,520
保持此排序，这确实是
将是另一个目标，现在，

489
00:21:46,520 --> 00:21:48,690
17和26之间应该在。

490
00:21:48,690 --> 00:21:50,270
所以我敲回车。

491
00:21:50,270 --> 00:21:51,380
事实上，工作的。

492
00:21:51,380 --> 00:21:54,950
所以现在让我插入
最后，每个图片，34。

493
00:21:54,950 --> 00:21:55,450
>> 好吧。

494
00:21:55,450 --> 00:21:58,980
所以现在让我规定
删除和遍历和搜索做的，

495
00:21:58,980 --> 00:21:59,760
其实，工作。

496
00:21:59,760 --> 00:22:04,180
事实上，如果我不执行搜索，让我们
搜索次数22，回车。

497
00:22:04,180 --> 00:22:05,010
研究发现22。

498
00:22:05,010 --> 00:22:07,580
所以这就是这个
程序清单零呢。

499
00:22:07,580 --> 00:22:10,230
>> 但实际上会
在实现这一点？

500
00:22:10,230 --> 00:22:14,530
嗯，首先我可能有，确实
我有一个文件名为list0.h。

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
而在某个地方有这样的
行，类型定义，结构节点，

503
00:22:20,690 --> 00:22:24,850
然后，我有我的花括号，诠释n和
然后struct--究竟是什么定义？

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
结构节点旁边。

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
因此，我们需要的明星。

508
00:22:31,045 --> 00:22:33,420
现在，技术上我们进入
在这里画的习惯。

509
00:22:33,420 --> 00:22:35,670
你可能会看到课本和
网上参考做那里。

510
00:22:35,670 --> 00:22:36,660
它的功能相当的。

511
00:22:36,660 --> 00:22:37,980
其实，这是一个小更典型。

512
00:22:37,980 --> 00:22:40,563
但我会用什么样一致
我们做了最后的时间，做到这一点。

513
00:22:40,563 --> 00:22:42,350
然后最后，我要做到这一点。

514
00:22:42,350 --> 00:22:45,550
>> 因此，在头文件
某处，在list0.h

515
00:22:45,550 --> 00:22:49,200
今天是这个结构的定义，
也许一些其他的东西。

516
00:22:49,200 --> 00:22:52,580
与此同时，在list0c有
将是一个几件事情。

517
00:22:52,580 --> 00:22:54,740
但是，我们要公正
开始，而不是结束了。

518
00:22:54,740 --> 00:22:59,690
List0.h是我想要的文件
包括在我的C文件。

519
00:22:59,690 --> 00:23:03,910
然后在某个时候，我
将有整型，主要的，无效的。

520
00:23:03,910 --> 00:23:06,530
然后我要去
有一些待办事项在这里。

521
00:23:06,530 --> 00:23:10,620
我也将有一个
原型，如虚空，搜索，INT，

522
00:23:10,620 --> 00:23:13,610
N，在生活中，其目的是
要搜索的元素。

523
00:23:13,610 --> 00:23:18,310
再往下这里我要求在
今天的码，无效搜索，INT，N，

524
00:23:18,310 --> 00:23:21,020
别无分号，但开放的花括号。

525
00:23:21,020 --> 00:23:25,049
现在我想以某种方式查询
对于该列表中的一个元素。

526
00:23:25,049 --> 00:23:27,340
但是，我们没有足够的
但在屏幕上的信息。

527
00:23:27,340 --> 00:23:29,800
我没有实际
表示该清单自身。

528
00:23:29,800 --> 00:23:33,070
所以一个方法，我们可以实现
链表的程序

529
00:23:33,070 --> 00:23:37,520
一种是我想要做的事
如声明成链表在这里。

530
00:23:37,520 --> 00:23:40,520
为简单起见，我将做出
这一全球性的，尽管一般我们

531
00:23:40,520 --> 00:23:41,645
不应该这样做太过分了。

532
00:23:41,645 --> 00:23:43,260
但它可以简化这个例子。

533
00:23:43,260 --> 00:23:45,890
所以，我想声明
链表在这里。

534
00:23:45,890 --> 00:23:47,010
现在，我怎么可能这样做呢？

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> 这里有一个链接列表的画面。

537
00:23:50,750 --> 00:23:53,030
我真的不
知道此刻如何

538
00:23:53,030 --> 00:23:56,710
我打算去代表
只用一个这么多东西

539
00:23:56,710 --> 00:23:58,040
变量在内存中。

540
00:23:58,040 --> 00:23:59,160
但回想一下。

541
00:23:59,160 --> 00:24:00,830
这一切的时候，我们已经有
字符串，我们再

542
00:24:00,830 --> 00:24:02,913
发现是数组
字符，然后我们

543
00:24:02,913 --> 00:24:05,740
显露只是一个指针
到的第一个字符

544
00:24:05,740 --> 00:24:08,890
在字符数组
这是空终止。

545
00:24:08,890 --> 00:24:13,530
所以通过该逻辑，以及与此
图像种类播种的想法，

546
00:24:13,530 --> 00:24:17,964
有什么需要我们在实际编写我们
代码来表示链表？

547
00:24:17,964 --> 00:24:21,130
如何对这些信息多我们需要
捕捉到的C代码，你会说什么？

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
是吗？

550
00:24:23,154 --> 00:24:24,738
>> 听众：我们需要一个指向一个节点。

551
00:24:24,738 --> 00:24:26,237
戴维·J·马兰：一个指针，指向一个节点。

552
00:24:26,237 --> 00:24:29,320
特别是，该节点将您的
本能是要保持一个指针？

553
00:24:29,320 --> 00:24:30,026
>> 听众：第一节点。

554
00:24:30,026 --> 00:24:31,942
>> 戴维·J·马兰：是啊，
可能只是第一个。

555
00:24:31,942 --> 00:24:34,030
并注意，第一
节点是不同的形状。

556
00:24:34,030 --> 00:24:37,690
它的结构只有一半的大小，
因为它确实只是一个指针。

557
00:24:37,690 --> 00:24:44,650
那么，你的确可以做的就是声明
链表是类型的节点*。

558
00:24:44,650 --> 00:24:47,780
而且，我们只是先称它为
并把它初始化为null。

559
00:24:47,780 --> 00:24:49,910
所以空，再次，是未来
到这里的画面。

560
00:24:49,910 --> 00:24:53,620
不仅是空作为像一种特殊的
搞什么的GetString返回值

561
00:24:53,620 --> 00:24:57,770
和malloc，空也是零
指针，缺乏一个指针，

562
00:24:57,770 --> 00:24:58,430
如果你愿意。

563
00:24:58,430 --> 00:25:00,309
它只是意味着什么又是在这里。

564
00:25:00,309 --> 00:25:02,100
现在开始，我会一直
所谓的事。

565
00:25:02,100 --> 00:25:04,200
我可以把它叫做“名单”
或任何数目的其他事情。

566
00:25:04,200 --> 00:25:06,960
但我把它称为“第一”，使
这行了这幅画。

567
00:25:06,960 --> 00:25:10,280
所以就像一个字符串可以表示
其第一个字节的地址，

568
00:25:10,280 --> 00:25:11,280
所以可以一个链表。

569
00:25:11,280 --> 00:25:13,480
我们会看到其他数据
结构式来表示

570
00:25:13,480 --> 00:25:16,700
只有一个指针，
一个32位的箭头，指向

571
00:25:16,700 --> 00:25:18,740
在该结构中的第一个节点。

572
00:25:18,740 --> 00:25:20,340
>> 但现在，让我们期待一个问题。

573
00:25:20,340 --> 00:25:23,230
如果我只记得
在我的程序中的地址

574
00:25:23,230 --> 00:25:27,220
第一节点，所述第一
矩形在此数据结构中，

575
00:25:27,220 --> 00:25:31,760
什么最好是对的情况下，
实现我的名单的其余部分？

576
00:25:31,760 --> 00:25:35,820
那是什么回事的关键细节
为确保这一点的实际工作？

577
00:25:35,820 --> 00:25:39,250
并通过“实际工作”我
意思是说，就像一个字符串，

578
00:25:39,250 --> 00:25:42,180
让我们从第一个字符去
在达文的名称，以第二，

579
00:25:42,180 --> 00:25:44,755
到第三，对
第四，到了最后，

580
00:25:44,755 --> 00:25:47,880
我们怎么知道，当我们在最后
链表，看起来像这样？

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
当它为空。

583
00:25:50,660 --> 00:25:53,640
我已经表示这样的作为
像电​​气工程师可能，

584
00:25:53,640 --> 00:25:56,420
与小接地
各种各样的符号。

585
00:25:56,420 --> 00:25:58,246
但是，这只是意味着在这种情况下空。

586
00:25:58,246 --> 00:26:00,370
您可以绘制任意数量
的方法，但笔者

587
00:26:00,370 --> 00:26:02,800
发生在这里使用这个标志。

588
00:26:02,800 --> 00:26:06,260
>> 只要我们穿线
所有这些节点一起

589
00:26:06,260 --> 00:26:08,600
只记得在哪里
第一个是，只要

590
00:26:08,600 --> 00:26:11,760
当我们把一个特殊符号，在
在列表中的最后节点，

591
00:26:11,760 --> 00:26:15,130
我们将使用空，因为这是
我们必须提供给我们，

592
00:26:15,130 --> 00:26:16,480
该列表已完成。

593
00:26:16,480 --> 00:26:20,190
即使我只给你一个指针
第一个元素，你，程序员，

594
00:26:20,190 --> 00:26:22,486
当然可以访问它的其余部分。

595
00:26:22,486 --> 00:26:24,360
但是，让我们让你的头脑
游荡了一点点，

596
00:26:24,360 --> 00:26:26,140
如果他们不是已经
很wandered--什么

597
00:26:26,140 --> 00:26:28,723
将要的运行时间
发现在这个名单什么？

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
该死，这n个大O，
这是不坏，在公平性。

600
00:26:33,470 --> 00:26:34,800
但它是线性的。

601
00:26:34,800 --> 00:26:37,980
我们已经放弃了什么功能
阵列通过移动更多

602
00:26:37,980 --> 00:26:43,130
对这张照片的动态
交织在一起或链接的节点？

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
我们已经放弃了随机访问。

605
00:26:46,687 --> 00:26:48,770
数组是不错的，因为
数学上的一切

606
00:26:48,770 --> 00:26:50,340
是背靠背背靠背。

607
00:26:50,340 --> 00:26:52,370
尽管这幅画
看起来很漂亮，甚至

608
00:26:52,370 --> 00:26:55,830
虽然它看起来像这些节点
是很好的分开，在现实中

609
00:26:55,830 --> 00:26:56,830
他们可以在任何地方。

610
00:26:56,830 --> 00:27:01,590
OX1，OX50，Ox123，Ox99，这些
节点可以在任何地方。

611
00:27:01,590 --> 00:27:05,960
因为做的malloc分配内存
离堆，但在任何地方堆。

612
00:27:05,960 --> 00:27:09,080
你不一定知道它的
将是背靠背回来。

613
00:27:09,080 --> 00:27:12,460
所以这幅画在现实中的
不会是今天这样漂亮。

614
00:27:12,460 --> 00:27:16,140
>> 因此，这将需要一些
努力实现这个功能。

615
00:27:16,140 --> 00:27:17,880
现在让我们实现搜索。

616
00:27:17,880 --> 00:27:20,250
我们将看到种类的
这样做的聪明的方式。

617
00:27:20,250 --> 00:27:24,660
所以，如果我是一个搜索功能和
我给一个变量，整数n

618
00:27:24,660 --> 00:27:28,490
寻找，我需要知道的
在里面寻找新的语法

619
00:27:28,490 --> 00:27:32,400
一个结构，是的
指出，为求n。

620
00:27:32,400 --> 00:27:33,210
因此，让我们做到这一点。

621
00:27:33,210 --> 00:27:36,030
>> 所以，首先我会去
未来，并宣布一个节点*。

622
00:27:36,030 --> 00:27:39,400
我要去把它称为
指针，只是约定。

623
00:27:39,400 --> 00:27:41,710
我要去把它初始化为先。

624
00:27:41,710 --> 00:27:43,770
现在我可以做到这一点
在许多方面。

625
00:27:43,770 --> 00:27:45,436
不过，我要采取的共同办法。

626
00:27:45,436 --> 00:27:50,180
而指针不等于
空，这是有效的语法。

627
00:27:50,180 --> 00:27:54,550
它只是意味着做到以下几点，那么
只要你不指着什么。

628
00:27:54,550 --> 00:27:55,800
我该怎么想呢？

629
00:27:55,800 --> 00:28:01,939
>> 如果指针点N，让我回来
到，equals--等于什么？

630
00:28:01,939 --> 00:28:03,105
我在寻找什么样的价值？

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
这是通过在实际ñ。

633
00:28:06,590 --> 00:28:09,020
因此，这里的另一特色
对C和许多语言。

634
00:28:09,020 --> 00:28:13,705
即使所谓的结构节点
有一个n值，完全合法

635
00:28:13,705 --> 00:28:17,530
也有当地的说法
或者叫变量n。

636
00:28:17,530 --> 00:28:20,085
因为即使我们有
人眼可以分辨

637
00:28:20,085 --> 00:28:22,087
这n是推测
不同于该n。

638
00:28:22,087 --> 00:28:23,420
因为语法是不同的。

639
00:28:23,420 --> 00:28:26,211
你有一个点和一个指针，
而这其中有没有这样的事情。

640
00:28:26,211 --> 00:28:27,290
因此，这是确定。

641
00:28:27,290 --> 00:28:29,120
这是确定的打电话给他们同样的事情。

642
00:28:29,120 --> 00:28:32,380
>> 如果我发现你这个，我是
会想要做的事

643
00:28:32,380 --> 00:28:35,000
像大家宣布，我们发现Ñ。

644
00:28:35,000 --> 00:28:37,930
我们会离开，作为一个
发表评论或伪代码。

645
00:28:37,930 --> 00:28:40,190
否则，和这里的
有趣的部分，是什么

646
00:28:40,190 --> 00:28:47,320
做我想做的事情，如果当前节点
不包含n个我在乎？

647
00:28:47,320 --> 00:28:50,700
我如何实现以下？

648
00:28:50,700 --> 00:28:53,710
如果我的手指在
此刻是PTR，它的

649
00:28:53,710 --> 00:28:55,920
指着什么
第一是指向，

650
00:28:55,920 --> 00:28:59,290
如何将我的手指
在代码中的下一个节点？

651
00:28:59,290 --> 00:29:01,915
那么，什么是我们的面包屑
要在这种情况下，遵循？

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
听众：[听不清]。

654
00:29:04,380 --> 00:29:05,630
戴维·J·马兰：是啊，所以下一步。

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
所以，如果我回到我的
这里的代码，事实上，我

657
00:29:09,824 --> 00:29:12,990
要继续前进，说的指针，这
只是一个暂时的变量 - 这是

658
00:29:12,990 --> 00:29:15,320
一个奇怪的名字，PTR，但
它就像temp--

659
00:29:15,320 --> 00:29:19,234
我要设置指针
等于任何指针is--

660
00:29:19,234 --> 00:29:22,150
又一次，这将是一个
小马车的moment--点下一步。

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
换句话说，我要去把我的
指的是指向该节点

663
00:29:26,550 --> 00:29:31,247
在这里，我想说，你知道
什么，看看下一个字段

664
00:29:31,247 --> 00:29:33,330
移动你的手指
不管它的指向。

665
00:29:33,330 --> 00:29:35,163
并且这将
重复，重复，重复。

666
00:29:35,163 --> 00:29:37,630
但是，什么时候我的手指
停止做了什么呢？

667
00:29:37,630 --> 00:29:40,095
只要什么码踢行？

668
00:29:40,095 --> 00:29:40,970
听众：[听不清]

669
00:29:40,970 --> 00:29:43,060
戴维·J·马兰：如果同时点
指针不等于空。

670
00:29:43,060 --> 00:29:44,900
在某些时候，我的手指的
将要指向空

671
00:29:44,900 --> 00:29:47,070
我要去实现
这是该列表的末尾。

672
00:29:47,070 --> 00:29:48,910
现在，这是一个小
善意的谎言的简单性。

673
00:29:48,910 --> 00:29:51,580
事实证明，即使我们
刚刚得知这个点符号

674
00:29:51,580 --> 00:29:55,220
对于结构，指针不是一个结构。

675
00:29:55,220 --> 00:29:56,580
PTR是什么？

676
00:29:56,580 --> 00:29:58,350
只是要更挑剔。

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
这是一个指针，指向一个节点。

679
00:30:01,360 --> 00:30:03,120
这不是一个节点本身。

680
00:30:03,120 --> 00:30:06,650
如果我在这里没有明星，指针
absolutely--它是一个节点。

681
00:30:06,650 --> 00:30:08,650
这就好比一个星期
变量声明，

682
00:30:08,650 --> 00:30:10,120
即使单词“节点”是新的。

683
00:30:10,120 --> 00:30:13,860
>> 但只要我们引入了
明星，它现在是一个指针，指向一个节点。

684
00:30:13,860 --> 00:30:17,960
但不幸的是你不能使用
点号的一个指针。

685
00:30:17,960 --> 00:30:21,070
你必须使用箭头
符号，其中，引人注目的是，

686
00:30:21,070 --> 00:30:23,470
是第一次的任何一块
语法看起来直观。

687
00:30:23,470 --> 00:30:25,245
这从字面上看起来像一个箭头。

688
00:30:25,245 --> 00:30:26,370
因此，这是一件好事。

689
00:30:26,370 --> 00:30:28,995
而到这里字面上
看起来像一个箭头。

690
00:30:28,995 --> 00:30:31,870
所以，我认为这是la--我不
想我过犯这里 - ì

691
00:30:31,870 --> 00:30:34,120
认为这是最后的新作品
语法我们要看到的。

692
00:30:34,120 --> 00:30:36,500
而幸运的是，这是真的
多一点直观。

693
00:30:36,500 --> 00:30:40,090
>> 现在，对于那些你们谁
可能更喜欢旧的方式，

694
00:30:40,090 --> 00:30:42,550
你仍然可以使用点号。

695
00:30:42,550 --> 00:30:45,380
但由于每星期一
谈话中，我们首先

696
00:30:45,380 --> 00:30:50,530
需要去那里，去那
处理，然后访问字段。

697
00:30:50,530 --> 00:30:51,897
因此，这也是正确的。

698
00:30:51,897 --> 00:30:53,730
坦率地说，这是一个
有点迂腐。

699
00:30:53,730 --> 00:30:56,530
你从字面上说，提领
指针和去那里。

700
00:30:56,530 --> 00:30:59,320
然后抓住.N，现场叫ñ。

701
00:30:59,320 --> 00:31:01,370
但坦率地说，没有人愿意
打字或阅读。

702
00:31:01,370 --> 00:31:03,620
这样一来，发明了世界
箭头符号，其中

703
00:31:03,620 --> 00:31:06,980
是等价的，相同的，
它只是语法糖。

704
00:31:06,980 --> 00:31:10,570
对这个说法如此看中方式
看起来更好，看起来更简单。

705
00:31:10,570 --> 00:31:12,296
>> 所以现在我要做的一件事。

706
00:31:12,296 --> 00:31:15,420
我会说“休息”一旦我
发现它，所以我不继续寻找它。

707
00:31:15,420 --> 00:31:17,620
但是，这是依据
的搜索功能。

708
00:31:17,620 --> 00:31:21,710
但它是一个容易得多，在
最后，不要穿行的代码。

709
00:31:21,710 --> 00:31:25,570
这的确是正式实施
在今天的分销代码搜索。

710
00:31:25,570 --> 00:31:30,530
我敢说，插不
特别有趣的穿行

711
00:31:30,530 --> 00:31:33,180
在视觉上，也不是删除，甚至
虽然在这一天结束时

712
00:31:33,180 --> 00:31:35,460
他们归结为公平
简单的启发式方法。

713
00:31:35,460 --> 00:31:36,330
>> 因此，让我们做到这一点。

714
00:31:36,330 --> 00:31:39,250
如果你会幽默我在这里，我没有
把一堆压力球。

715
00:31:39,250 --> 00:31:40,620
我带了一堆数字。

716
00:31:40,620 --> 00:31:46,562
而我们能得到的只是一些志愿者
代表9，17，20，22，29和34？

717
00:31:46,562 --> 00:31:48,270
所以基本上每个人都
谁是今天。

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
这是一，二，三，
四，五，六人。

720
00:31:52,760 --> 00:31:55,740
我一直在问go--看，没有
一个在后面举手。

721
00:31:55,740 --> 00:32:01,910
好了，一，二，三，四，
five--让我加载balance-- 6。

722
00:32:01,910 --> 00:32:03,051
好了，你六上来吧。

723
00:32:03,051 --> 00:32:04,050
我们需要其他人。

724
00:32:04,050 --> 00:32:05,460
我们带来了额外的压力球。

725
00:32:05,460 --> 00:32:08,200
如果你可以，
只是一瞬间，行

726
00:32:08,200 --> 00:32:10,490
自己刚起来
喜欢这幅画在这里。

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> 好吧。

729
00:32:15,959 --> 00:32:17,125
让我们来看看，你叫什么名字？

730
00:32:17,125 --> 00:32:17,550
>> 听众：安德鲁。

731
00:32:17,550 --> 00:32:18,800
>> 戴维·J·马兰：安德鲁，
你是9号。

732
00:32:18,800 --> 00:32:19,540
很高兴认识你。

733
00:32:19,540 --> 00:32:20,400
干得好。

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
听众：仁。

736
00:32:22,176 --> 00:32:22,662
戴维·J·马兰：仁。

737
00:32:22,662 --> 00:32:23,162
大卫。

738
00:32:23,162 --> 00:32:23,765
号码17。

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
是吗？

741
00:32:25,450 --> 00:32:26,400
>> 听众：我是朱莉娅。

742
00:32:26,400 --> 00:32:26,980
>> 戴维·J·马兰：朱莉娅大卫。

743
00:32:26,980 --> 00:32:27,545
号码20。

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
听众：基督教。

746
00:32:29,340 --> 00:32:30,715
戴维·J·马兰：基督教，大卫。

747
00:32:30,715 --> 00:32:31,541
号码22。

748
00:32:31,541 --> 00:32:32,040
和？

749
00:32:32,040 --> 00:32:32,649
>> 听众：日本。

750
00:32:32,649 --> 00:32:33,440
戴维·J·马兰：日本。

751
00:32:33,440 --> 00:32:34,880
号码29。

752
00:32:34,880 --> 00:32:37,080
所以，尽管获得in--嗯哦。

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
嗯哦。

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
待机。

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20。

759
00:32:42,390 --> 00:32:43,682
有没有人有一个标记？

760
00:32:43,682 --> 00:32:44,890
听众：我有一个夏普。

761
00:32:44,890 --> 00:32:45,660
戴维·J·马兰：你有夏普？

762
00:32:45,660 --> 00:32:46,159
行。

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
并没有任何人有一张纸？

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
保存了讲座。

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
来吧。

769
00:32:55,362 --> 00:32:56,320
听众：我们已经知道了。

770
00:32:56,320 --> 00:32:57,600
戴维·J·马兰：我们得到了它？

771
00:32:57,600 --> 00:32:58,577
好吧，谢谢你。

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
开始了。

774
00:33:02,520 --> 00:33:03,582
从你是这样的？

775
00:33:03,582 --> 00:33:04,540
你刚才化险为夷。

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
所以29。

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
好吧。

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
í拼写错误29，但确定。

782
00:33:14,890 --> 00:33:15,720
前进。

783
00:33:15,720 --> 00:33:18,114
好吧，我给你
你的笔回暂时。

784
00:33:18,114 --> 00:33:19,280
所以我们这些人在这里。

785
00:33:19,280 --> 00:33:20,330
让我们有一个其他的。

786
00:33:20,330 --> 00:33:23,750
加布，你要玩
这里的第一个元素？

787
00:33:23,750 --> 00:33:25,705
我们需要你来点
这些精美的乡亲。

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
所以，9，17，20，22，排序
29，然后34。

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
我们失去了一个人？

792
00:33:33,325 --> 00:33:33,950
我有一个34。

793
00:33:33,950 --> 00:33:36,730
凡did--确定，谁愿意为34？

794
00:33:36,730 --> 00:33:37,605
好了，上来吧，34。

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
好吧，这将是
非常值得的高潮。

797
00:33:41,220 --> 00:33:41,550
你叫什么名字？

798
00:33:41,550 --> 00:33:42,040
>> 听众：彼得。

799
00:33:42,040 --> 00:33:43,456
>> 戴维·J·马兰：彼得，上来吧。

800
00:33:43,456 --> 00:33:46,810
好吧，那么这里有一个
一大堆的节点。

801
00:33:46,810 --> 00:33:49,060
每次你们都代表
其中的一个矩形。

802
00:33:49,060 --> 00:33:51,930
和加布，稍奇
男人出来，表示第一。

803
00:33:51,930 --> 00:33:54,850
所以他的指针是一个小一点
在屏幕上比其他人。

804
00:33:54,850 --> 00:33:58,120
并且在这种情况下，每个你的左
手是怎么回事要么点下去，

805
00:33:58,120 --> 00:34:01,085
从而表示空值，所以
只是没有指针，

806
00:34:01,085 --> 00:34:03,210
或者它会被人指指点点
在你旁边的一个节点。

807
00:34:03,210 --> 00:34:05,440
>> 所以现在，如果你佩戴
喜欢的图片呀

808
00:34:05,440 --> 00:34:07,585
在这里，继续和点
对方，用加布

809
00:34:07,585 --> 00:34:11,030
在特定的指向
编号9表示的列表。

810
00:34:11,030 --> 00:34:14,050
确定，34号，你的左手
应该只指向地面。

811
00:34:14,050 --> 00:34:15,750
>> 好了，这就是链表。

812
00:34:15,750 --> 00:34:17,580
所以，这是该方案的问题。

813
00:34:17,580 --> 00:34:20,210
事实上，这是代表
一类的问题

814
00:34:20,210 --> 00:34:21,929
你可能会试图解决与代码。

815
00:34:21,929 --> 00:34:25,020
你想最终将
一个新的元素到列表中。

816
00:34:25,020 --> 00:34:27,494
在这种情况下，我们要
请尝试将数字55。

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
但是，将是
不同的情况来考虑。

819
00:34:30,860 --> 00:34:34,409
事实上，这将是1
的大画面纪要这里，是，

820
00:34:34,409 --> 00:34:35,659
什么是不同的情况。

821
00:34:35,659 --> 00:34:39,120
什么是如果条件或不同
你的程序可能有分支机构？

822
00:34:39,120 --> 00:34:42,024
>> 嗯，这个数字你要
插入，这是我们现在知道是55，

823
00:34:42,024 --> 00:34:44,650
但如果你不知道
事先，我敢说

824
00:34:44,650 --> 00:34:47,840
落入至少三个
可能出现的情况。

825
00:34:47,840 --> 00:34:49,717
凡可能一个新的元素呢？

826
00:34:49,717 --> 00:34:51,050
听。结束或中间。

827
00:34:51,050 --> 00:34:54,150
戴维·J·马兰：最后，在
的中间，或在开始时。

828
00:34:54,150 --> 00:34:56,650
所以，我要求有至少
我们需要解决三个问题。

829
00:34:56,650 --> 00:34:58,691
让我们选择什么样的可能
可以说是最简单的

830
00:34:58,691 --> 00:35:01,090
之一，其中该新元素
属于开头。

831
00:35:01,090 --> 00:35:04,040
所以我将有相当代码
如搜索，我只是写。

832
00:35:04,040 --> 00:35:07,670
我要去有PTR，这
我在这里代表我的手指，

833
00:35:07,670 --> 00:35:08,370
照常。

834
00:35:08,370 --> 00:35:12,430
>> 请记住，什么样的价值
我们曾初始化PTR什么？

835
00:35:12,430 --> 00:35:15,300
因此，我们初始化为null开始。

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
但后来我们做了一次，我们什么
是我们的搜索功能里？

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
我们设置它等于第一次，
这并不意味着这样做。

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
如果我设置PTR等于一，什么
应我的手真的是指向？

842
00:35:30,570 --> 00:35:31,070
右。

843
00:35:31,070 --> 00:35:33,290
所以，如果加布和我要去
这里是相等的值，

844
00:35:33,290 --> 00:35:34,760
我们需要在两个点在9号。

845
00:35:34,760 --> 00:35:36,420
>> 因此，这是我们的故事的开始。

846
00:35:36,420 --> 00:35:38,700
而现在这仅仅是简单的，
即使语法是新的。

847
00:35:38,700 --> 00:35:40,580
概念上，这只是线性搜索。

848
00:35:40,580 --> 00:35:42,750
是55等于9？

849
00:35:42,750 --> 00:35:45,559
或者说，让我们说不到9。

850
00:35:45,559 --> 00:35:47,600
因为我想
找出放在哪里55。

851
00:35:47,600 --> 00:35:51,270
9以上，小于17，小于
大于20，小于22，小于29，

852
00:35:51,270 --> 00:35:52,510
小于34，没有。

853
00:35:52,510 --> 00:35:55,080
所以，现在我们的情况下
一个上的至少三个。

854
00:35:55,080 --> 00:35:59,910
>> 如果我要插入55在这里，有什么
得到执行的代码需要行？

855
00:35:59,910 --> 00:36:01,890
请问这个图片
人类需要改变吗？

856
00:36:01,890 --> 00:36:03,181
我该怎么办我的左手？

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
这应该是零开始，
因为我在列表的末尾。

859
00:36:07,360 --> 00:36:09,318
什么应该发生
这里彼得，是吗？

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
他显然会指向我。

862
00:36:12,430 --> 00:36:15,580
所以，我要求有至少两条线路
在今天的示例代码代码

863
00:36:15,580 --> 00:36:18,570
这是怎么回事实现这个
方案中加入55的尾巴。

864
00:36:18,570 --> 00:36:20,950
而我能有一个人跳
起来，只是表示55？

865
00:36:20,950 --> 00:36:22,200
好吧，你是新的55。

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> 所以现在，如果下一个
情景出现时，

868
00:36:27,054 --> 00:36:29,720
我们要插入的
开始的时候还是这个列表的头？

869
00:36:29,720 --> 00:36:31,100
而你叫什么名字，号码55？

870
00:36:31,100 --> 00:36:31,420
>> 听众：杰克。

871
00:36:31,420 --> 00:36:32,295
>> 戴维·J·马兰：杰克？

872
00:36:32,295 --> 00:36:33,585
好了，很高兴见到你。

873
00:36:33,585 --> 00:36:34,210
欢迎登机。

874
00:36:34,210 --> 00:36:36,640
所以，现在我们要
插入，比方说，数字5。

875
00:36:36,640 --> 00:36:39,840
这里的第二种情况
3，我们想出了之前。

876
00:36:39,840 --> 00:36:43,050
因此，如果5属于之初，
让我们来看看我们是如何发现这一点。

877
00:36:43,050 --> 00:36:46,310
í初始化我的PTR
指针再次号码9。

878
00:36:46,310 --> 00:36:49,140
我意识到，哦，5小于9。

879
00:36:49,140 --> 00:36:50,880
因此，解决这个问题的图片我们。

880
00:36:50,880 --> 00:36:54,820
谁的手里，Gabe的还是大卫
or--什么是数字9的名字？

881
00:36:54,820 --> 00:36:55,740
>> 听众：仁。

882
00:36:55,740 --> 00:36:58,406
>> 戴维·J·马兰：仁的hands--
其中，我们的手需要改变吗？

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
好了，加布指着现在该怎么办？

885
00:37:00,970 --> 00:37:01,640
看着我。

886
00:37:01,640 --> 00:37:02,750
我的新节点。

887
00:37:02,750 --> 00:37:04,870
所以我就种做法
这里直观地看到它。

888
00:37:04,870 --> 00:37:06,435
而与此同时我该怎么点呢？

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
还在那里我指指点点。

891
00:37:09,020 --> 00:37:10,000
所以，就是这样。

892
00:37:10,000 --> 00:37:13,717
所以真的很需要一行代码修复
这个问题上，似乎。

893
00:37:13,717 --> 00:37:14,800
好了，所以这是很好的。

894
00:37:14,800 --> 00:37:17,580
而也有人是一个占位符，5？

895
00:37:17,580 --> 00:37:18,080
上来吧。

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
我们将让您下一次。

898
00:37:21,320 --> 00:37:24,280
>> 好吧，让now--和
顺便说一句，该名

899
00:37:24,280 --> 00:37:28,510
我不是做明确提及的权利
现在，PRED指针，指针的前身

900
00:37:28,510 --> 00:37:31,260
而新的指针，这是
只是名字定

901
00:37:31,260 --> 00:37:35,280
在示例代码的指针或
我的手说的那种指着身边。

902
00:37:35,280 --> 00:37:36,060
你叫什么名字？

903
00:37:36,060 --> 00:37:36,700
>> 听众：恭。

904
00:37:36,700 --> 00:37:37,100
>> 戴维·J·马兰：恭。

905
00:37:37,100 --> 00:37:38,090
欢迎登机。

906
00:37:38,090 --> 00:37:42,180
好吧，让我们现在来考虑
一个稍微更恼人的情况，

907
00:37:42,180 --> 00:37:46,350
由此我想插入
像26到这一点。

908
00:37:46,350 --> 00:37:47,090
20？

909
00:37:47,090 --> 00:37:47,590
什么？

910
00:37:47,590 --> 00:37:50,510
这些are--好事，我们有这样的笔。

911
00:37:50,510 --> 00:37:51,955
好吧，20。

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
如果有人能得到另一块
纸准备好了，就在case--所有权利。

914
00:37:57,570 --> 00:37:58,370
呵呵，有意思。

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
嗯，这是一个例子
的讲座错误。

917
00:38:02,390 --> 00:38:03,894
行，所以你叫什么名字来着？

918
00:38:03,894 --> 00:38:04,560
听众：朱莉娅。

919
00:38:04,560 --> 00:38:07,559
戴维·J·马兰：朱莉娅，你可以弹出
出来，假装你从未在那里？

920
00:38:07,559 --> 00:38:09,040
OK，这从来没有发生过。

921
00:38:09,040 --> 00:38:09,680
谢谢。

922
00:38:09,680 --> 00:38:12,180
因此，假设我们要插入
朱成这个链表。

923
00:38:12,180 --> 00:38:13,780
她是20号。

924
00:38:13,780 --> 00:38:15,530
当然，她的
将属于在

925
00:38:15,530 --> 00:38:17,521
begin--不要在任何地步。

926
00:38:17,521 --> 00:38:20,020
种那么你的手可
倒空或一些垃圾值。

927
00:38:20,020 --> 00:38:21,210
让我们告诉了快速的故事。

928
00:38:21,210 --> 00:38:22,980
我指着5号这段时间。

929
00:38:22,980 --> 00:38:23,880
然后我检查9。

930
00:38:23,880 --> 00:38:25,130
然后我检查17。

931
00:38:25,130 --> 00:38:26,247
然后我检查22。

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
我意识到，哦，朱莉娅
需要22日前去。

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
因此，需要做些什么？

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
谁的手里需要改变吗？

938
00:38:36,910 --> 00:38:38,360
Julia的，我的，or--
你叫什么名字来着？

939
00:38:38,360 --> 00:38:39,230
>> 听众：基督教。

940
00:38:39,230 --> 00:38:40,060
>> 戴维·J·马兰：基督教还是？

941
00:38:40,060 --> 00:38:40,560
>> 听众：安迪。

942
00:38:40,560 --> 00:38:40,905
>> 戴维·J·马兰：安迪。

943
00:38:40,905 --> 00:38:41,654
基督教或安迪？

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
安迪需要指向？

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
朱莉娅。

948
00:38:47,341 --> 00:38:47,840
好吧。

949
00:38:47,840 --> 00:38:48,960
所以安迪，你想点的朱莉娅？

950
00:38:48,960 --> 00:38:50,120
但是且慢。

951
00:38:50,120 --> 00:38:53,260
在故事迄今
我是一个排序

952
00:38:53,260 --> 00:38:56,800
在电荷，在这个意义上，
指针的东西，是

953
00:38:56,800 --> 00:38:57,850
在列表中移动。

954
00:38:57,850 --> 00:39:00,800
我们可能对刘德华的名称，但
有没有所谓的可变安迪。

955
00:39:00,800 --> 00:39:04,320
我们唯一的其他变量
第一，谁是由加布表示。

956
00:39:04,320 --> 00:39:07,690
>> 因此，这实际上是这样，为什么
到目前为止，我们已经没有必要了。

957
00:39:07,690 --> 00:39:10,846
但现在在屏幕上有
预计值的指针再提起。

958
00:39:10,846 --> 00:39:11,970
因此，让我更明确。

959
00:39:11,970 --> 00:39:14,820
如果这是指针，我最好
得到一个小更智能

960
00:39:14,820 --> 00:39:15,950
我的迭代。

961
00:39:15,950 --> 00:39:19,580
如果你不介意我的经历在这里
再次，指指点点，指指点点。

962
00:39:19,580 --> 00:39:22,500
不过，让我有一个预计值的指针，
前任的指针，这是

963
00:39:22,500 --> 00:39:24,740
种指着
元我就在。

964
00:39:24,740 --> 00:39:27,330
所以，当我去这里，现在
我的左手更新。

965
00:39:27,330 --> 00:39:29,370
当我走在这里我的左手更新。

966
00:39:29,370 --> 00:39:33,090
现在我不仅是一个指针
朱莉娅之后去的元素，

967
00:39:33,090 --> 00:39:36,300
我仍然有一个指针
安迪，之前的元素。

968
00:39:36,300 --> 00:39:39,430
所以，你有机会，基本上，
面包屑，如果你愿意，

969
00:39:39,430 --> 00:39:41,500
到所有必要的指针。

970
00:39:41,500 --> 00:39:43,710
>> 所以，如果我指着
安迪和我还指着

971
00:39:43,710 --> 00:39:47,105
在基督教，他的手
现在应该在别处指出？

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
所以安迪现在可以指向朱莉娅。

974
00:39:51,960 --> 00:39:54,460
朱莉娅现在可以指向基督徒。

975
00:39:54,460 --> 00:39:56,950
因为她能复制我的
右手的指针。

976
00:39:56,950 --> 00:40:00,044
并能有效地使你
回到这里这个地方。

977
00:40:00,044 --> 00:40:02,460
所以，总之，即使此
正在美国种永

978
00:40:02,460 --> 00:40:04,510
实际更新
链表，实现

979
00:40:04,510 --> 00:40:06,580
该操作
是相对简单的。

980
00:40:06,580 --> 00:40:10,030
它是一个，两个，三个
行代码最终。

981
00:40:10,030 --> 00:40:12,780
但缠的
行的代码大概

982
00:40:12,780 --> 00:40:16,350
有点逻辑，有效地
问这个问题，我们在哪里？

983
00:40:16,350 --> 00:40:18,970
难道我们在一开始，
中间还是结束了吗？

984
00:40:18,970 --> 00:40:21,890
>> 现在，当然也有一些其他的
操作我们有可能实现的。

985
00:40:21,890 --> 00:40:24,880
而这些图片在这里只是描述
我们刚刚与人类一样。

986
00:40:24,880 --> 00:40:26,080
怎么样去除？

987
00:40:26,080 --> 00:40:30,650
如果我想，例如，
删除号码34或55，

988
00:40:30,650 --> 00:40:34,680
我可能有同样的代码，
但我会需要一个或两个步骤。

989
00:40:34,680 --> 00:40:36,110
因为什么是新的？

990
00:40:36,110 --> 00:40:40,460
如果我删除某人的尽头，
像一些55后34，

991
00:40:40,460 --> 00:40:42,995
什么也有改变，因为我做到这一点？

992
00:40:42,995 --> 00:40:44,870
我不evict--
你叫什么名字来着？

993
00:40:44,870 --> 00:40:45,380
>> 听众：杰克。

994
00:40:45,380 --> 00:40:46,255
>> 戴维·J·马兰：杰克。

995
00:40:46,255 --> 00:40:49,770
我不仅evict--免费杰克，
所以从字面上拨打免费杰克，或者至少

996
00:40:49,770 --> 00:40:53,530
指针有过，但现在
有什么需要改变与彼得？

997
00:40:53,530 --> 00:40:55,510
他的手好开始朝下。

998
00:40:55,510 --> 00:40:59,300
因为只要我一打电话免费
杰克，如果彼得还指着杰克

999
00:40:59,300 --> 00:41:02,530
因此我继续穿越
列表和访问这个指针，

1000
00:41:02,530 --> 00:41:05,650
这时候我们的老朋友分割
故障实际上可能一命呜呼

1001
00:41:05,650 --> 00:41:07,860
因为我们已经给了
记忆回到杰克。

1002
00:41:07,860 --> 00:41:10,760
>> 你可以呆在那里
笨拙的只是一瞬间。

1003
00:41:10,760 --> 00:41:13,410
因为我们只是一对夫妇
最终的操作考虑。

1004
00:41:13,410 --> 00:41:15,600
删除列表的头部，
或beginning--而这一次的

1005
00:41:15,600 --> 00:41:16,349
有点讨厌。

1006
00:41:16,349 --> 00:41:19,640
因为我们要知道，加布
是一种特殊的这一计划。

1007
00:41:19,640 --> 00:41:21,440
因为事实上，他有自己的指针。

1008
00:41:21,440 --> 00:41:24,860
他不只是被指向，
因为几乎所有的人在这里。

1009
00:41:24,860 --> 00:41:28,112
>> 所以当表的标头是
拆除，谁的手里现在需要改变吗？

1010
00:41:28,112 --> 00:41:29,070
你叫什么名字来着？

1011
00:41:29,070 --> 00:41:29,450
>> 听众：恭。

1012
00:41:29,450 --> 00:41:31,408
>> 戴维·J·马兰：我是可怕的
在名称，显然。

1013
00:41:31,408 --> 00:41:34,011
因此，Christine和加布，
谁的手里需要改变

1014
00:41:34,011 --> 00:41:36,510
当我们试图删除恭，
5号，从图片？

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
好了，让我们做加布。

1017
00:41:38,820 --> 00:41:40,950
Gabe的去点，
据推测，在9号。

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
但是，接下来应该发生？

1020
00:41:44,642 --> 00:41:46,600
听众：恭应
为null [听不清]。

1021
00:41:46,600 --> 00:41:50,244
戴维·J·马兰：好，我们也许应该
make--听到“空”的地方。

1022
00:41:50,244 --> 00:41:51,410
听众：空和她的自由。

1023
00:41:51,410 --> 00:41:51,855
戴维·J·马兰：NULL是什么？

1024
00:41:51,855 --> 00:41:53,074
听众：空和她的自由。

1025
00:41:53,074 --> 00:41:54,490
戴维·J·马兰：空和她的自由。

1026
00:41:54,490 --> 00:41:55,422
因此，这是很容易的。

1027
00:41:55,422 --> 00:41:58,380
它是完美的，你现在已经排序
站在那里，没有归属感。

1028
00:41:58,380 --> 00:42:00,430
因为你已经
从列表中去耦。

1029
00:42:00,430 --> 00:42:02,820
你一直有效
从列表中孤立。

1030
00:42:02,820 --> 00:42:07,770
因此，我们最好称之为自由现在
恭让的记忆回来了。

1031
00:42:07,770 --> 00:42:10,240
否则，每次我们
从列表中删除一个节点

1032
00:42:10,240 --> 00:42:14,230
我们可能会犯名单
短，但实际上不降低

1033
00:42:14,230 --> 00:42:15,096
在存储器的大小。

1034
00:42:15,096 --> 00:42:17,720
所以，如果我们继续增加和
添加，添加的东西的清单，

1035
00:42:17,720 --> 00:42:19,280
我的电脑可能会变慢
和慢，

1036
00:42:19,280 --> 00:42:21,740
因为我跑出来的
内存，即使我没有实际

1037
00:42:21,740 --> 00:42:25,580
用恭的字节
内存了。

1038
00:42:25,580 --> 00:42:28,500
>> 那么，到底还有其他
场景course--去除，

1039
00:42:28,500 --> 00:42:30,640
在中间，除去
到了最后，正如我们所看到。

1040
00:42:30,640 --> 00:42:32,348
但更有趣的
现在的挑战是

1041
00:42:32,348 --> 00:42:34,770
将是准确地考虑
运行时间是什么。

1042
00:42:34,770 --> 00:42:36,640
这样不仅可以让您的
纸片，如果，加布，

1043
00:42:36,640 --> 00:42:38,640
你不会介意
每个人都有压力球。

1044
00:42:38,640 --> 00:42:42,100
非常感谢你对我们的链表
这里的志愿者，如果你能。

1045
00:42:42,100 --> 00:42:45,320
>> [掌声]

1046
00:42:45,320 --> 00:42:46,700
>> 戴维·J·马兰：好吧。

1047
00:42:46,700 --> 00:42:51,110
因此，一对夫妇的分析
问题的话，如果我能。

1048
00:42:51,110 --> 00:42:59,670
我们以前见过这个符号，
大O和欧米茄，上限

1049
00:42:59,670 --> 00:43:02,520
和上下限
运行一些算法的时间。

1050
00:43:02,520 --> 00:43:04,950
所以让我们只考虑
几个问题。

1051
00:43:04,950 --> 00:43:07,090
>> 一，我们说这
之前，有什么运行

1052
00:43:07,090 --> 00:43:10,647
搜索了时间
在大澳条款清单？

1053
00:43:10,647 --> 00:43:13,480
什么是上限运行
搜索链接列表的时间

1054
00:43:13,480 --> 00:43:16,340
通过我们的志愿者在这里实现的？

1055
00:43:16,340 --> 00:43:17,820
这n个大O，线性的。

1056
00:43:17,820 --> 00:43:20,630
由于在最坏的情况下，
元素，如55，

1057
00:43:20,630 --> 00:43:23,830
我们可能会寻找可能的地方
杰克，一路在末端。

1058
00:43:23,830 --> 00:43:28,250
不幸的是，一个数组不同
我们不能看上这个时候。

1059
00:43:28,250 --> 00:43:31,820
虽然我们所有的人都是
排序由小分子，5，

1060
00:43:31,820 --> 00:43:35,900
一路到更大的元素，
55，这通常是一件好事。

1061
00:43:35,900 --> 00:43:38,815
但到底是什么这样的假设
不再允许我们做什么？

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
听众：[听不清]

1064
00:43:40,650 --> 00:43:40,920
戴维·J·马兰：再说一遍吗？

1065
00:43:40,920 --> 00:43:41,800
听众：随机访问。

1066
00:43:41,800 --> 00:43:43,049
戴维·J·马兰：随机访问。

1067
00:43:43,049 --> 00:43:46,330
而反过来，这意味着我们不能
再使用弱零，直觉，

1068
00:43:46,330 --> 00:43:49,365
而显而易见使用二进制的
搜索和分而治之。

1069
00:43:49,365 --> 00:43:51,240
因为即使我们
人类能明显

1070
00:43:51,240 --> 00:43:54,610
看到刘德华或基督徒都
大致在表的中间，

1071
00:43:54,610 --> 00:43:57,670
我们只知道，作为一个
计算机通过略读列表

1072
00:43:57,670 --> 00:43:59,029
从一开始。

1073
00:43:59,029 --> 00:44:00,570
因此，我们已经放弃了随机访问。

1074
00:44:00,570 --> 00:44:04,380
>> n个这么大O，现在是上
必将在我们的搜索时间。

1075
00:44:04,380 --> 00:44:07,920
那么我们的搜索的欧米茄？

1076
00:44:07,920 --> 00:44:11,535
什么是搜索上下限
在此列表中的一些数字？

1077
00:44:11,535 --> 00:44:12,410
听众：[听不清]

1078
00:44:12,410 --> 00:44:13,040
戴维·J·马兰：再说一遍吗？

1079
00:44:13,040 --> 00:44:13,420
听众：一。

1080
00:44:13,420 --> 00:44:13,800
戴维·J·马兰：一。

1081
00:44:13,800 --> 00:44:14,760
因此，一定的时间。

1082
00:44:14,760 --> 00:44:17,020
在最好的情况下，克里斯汀是
的确在列表的开头。

1083
00:44:17,020 --> 00:44:19,020
我们正在寻找
5号，所以我们找到了她。

1084
00:44:19,020 --> 00:44:19,787
所以，没什么大不了的。

1085
00:44:19,787 --> 00:44:22,370
但她一定是在
开始列表在此情况下的。

1086
00:44:22,370 --> 00:44:23,745
那么什么样删除？

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
如果你想删除一个元素？

1089
00:44:26,300 --> 00:44:29,200
什么是上界和下界
有关删除的东西从链接

1090
00:44:29,200 --> 00:44:29,699
上市？

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
听众：[听不清]

1093
00:44:36,070 --> 00:44:36,420
戴维·J·马兰：再说一遍吗？

1094
00:44:36,420 --> 00:44:37,067
听众：不适用。

1095
00:44:37,067 --> 00:44:38,900
戴维·J·马兰：n为
确的上限。

1096
00:44:38,900 --> 00:44:41,700
由于在最坏的情况下，我们尝试
删除杰克，就像我们刚刚做。

1097
00:44:41,700 --> 00:44:43,050
他一路底。

1098
00:44:43,050 --> 00:44:45,419
把我们永远的，或
n步找到他。

1099
00:44:45,419 --> 00:44:46,460
所以这是一个上限。

1100
00:44:46,460 --> 00:44:47,430
这是线性的，肯定的。

1101
00:44:47,430 --> 00:44:50,970
和最好的情况下的运行时间，或
在最好的情况下，下限

1102
00:44:50,970 --> 00:44:51,975
将恒定时间。

1103
00:44:51,975 --> 00:44:54,600
因为也许我们尝试删除
克里斯蒂娜，我们只是很幸运

1104
00:44:54,600 --> 00:44:55,558
她开头。

1105
00:44:55,558 --> 00:44:56,350
现在，等待一分钟。

1106
00:44:56,350 --> 00:44:59,370
加布也之初，
我们也必须更新加布。

1107
00:44:59,370 --> 00:45:01,150
所以这不只是一个步骤。

1108
00:45:01,150 --> 00:45:04,210
那么，这确实是恒定的
时，在最好的情况下，

1109
00:45:04,210 --> 00:45:06,345
去除的最小元素？

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
它，即使它可能是两个，
3，甚至是100行的代码，

1112
00:45:10,960 --> 00:45:14,000
如果它的相同数量的
行，而不是在一些环路，

1113
00:45:14,000 --> 00:45:16,577
和独立的大小
名单的，绝对。

1114
00:45:16,577 --> 00:45:18,660
删除的元素
在列表的开头，

1115
00:45:18,660 --> 00:45:21,940
即使我们要处理
加布，仍然是固定的时间。

1116
00:45:21,940 --> 00:45:24,220
>> 因此，这似乎是一个
巨大的倒退。

1117
00:45:24,220 --> 00:45:27,000
什么时间是浪费
如果，在周1周和

1118
00:45:27,000 --> 00:45:30,250
零，我们不但
伪代码，但实际的代码

1119
00:45:30,250 --> 00:45:35,780
实施东西的日志
基N，或登录，而是n的基地2个，

1120
00:45:35,780 --> 00:45:37,150
在其运行时间条件。

1121
00:45:37,150 --> 00:45:40,710
那么，为什么赫克，我们将要开始
使用类似链表？

1122
00:45:40,710 --> 00:45:41,517
是啊。

1123
00:45:41,517 --> 00:45:44,022
>> 听众：所以，你可以添加
元件的阵列。

1124
00:45:44,022 --> 00:45:46,230
戴维·J·马兰：所以，你可以
元素添加到数组中。

1125
00:45:46,230 --> 00:45:47,550
而这也是主题。

1126
00:45:47,550 --> 00:45:49,740
我们将继续看到
这个，这个权衡，多

1127
00:45:49,740 --> 00:45:51,573
就像我们已经看到了
权衡合并排序。

1128
00:45:51,573 --> 00:45:54,606
我们真的可以加快
搜索或排序，相反，

1129
00:45:54,606 --> 00:45:57,480
如果我们花多一点的空间，
有记忆的附加块

1130
00:45:57,480 --> 00:45:58,760
或数组的归并排序。

1131
00:45:58,760 --> 00:46:01,270
但是，我们花更多
空间，但我们节省时间。

1132
00:46:01,270 --> 00:46:04,820
在这种情况下，我们
放弃时间，但我们

1133
00:46:04,820 --> 00:46:08,170
获得的灵活性，
活力，如果你愿意，

1134
00:46:08,170 --> 00:46:10,280
这无疑是一个积极的功能。

1135
00:46:10,280 --> 00:46:11,520
>> 我们也花了空间。

1136
00:46:11,520 --> 00:46:13,710
在什么意义上是一个链接
列出更贵

1137
00:46:13,710 --> 00:46:15,700
在空间不是一个数组方面？

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
哪里是多余的空间来的呢？

1140
00:46:19,920 --> 00:46:20,460
是吗？

1141
00:46:20,460 --> 00:46:21,800
>> 听众：[听不清]指针。

1142
00:46:21,800 --> 00:46:23,310
>> 戴维·J·马兰：是的，我们
也具有指针。

1143
00:46:23,310 --> 00:46:25,560
因此，这是minorly烦人
在不再是

1144
00:46:25,560 --> 00:46:27,780
存储I只是一个int
表示一个int。

1145
00:46:27,780 --> 00:46:30,990
我存储一个int和
指针，这也是32位。

1146
00:46:30,990 --> 00:46:33,470
所以，我从字面上倍增
所涉及的空间量。

1147
00:46:33,470 --> 00:46:36,040
所以这是一个权衡，但
这是在整数的情况下。

1148
00:46:36,040 --> 00:46:39,580
假设你没有存放整型，
但是假设每个这些矩形

1149
00:46:39,580 --> 00:46:43,290
或者这些人被代表
一个字，一个英语单词

1150
00:46:43,290 --> 00:46:46,430
可能是五个字符，10
人物，更可能。

1151
00:46:46,430 --> 00:46:49,940
然后加入只有32多个位
也许是少了一个大问题。

1152
00:46:49,940 --> 00:46:52,160
>> 如果每个学生什么
在演示

1153
00:46:52,160 --> 00:46:55,107
是字面上的学生结构的
有名字和房子，也许

1154
00:46:55,107 --> 00:46:57,065
电话号码和Twitter
处理等。

1155
00:46:57,065 --> 00:46:59,564
因此，所有的领域，我们开始
说起那天，

1156
00:46:59,564 --> 00:47:02,410
更大不了的
我们的节点变得更加有趣

1157
00:47:02,410 --> 00:47:05,972
和大花，嗯，一个额外的
指针只是将它们连接在一起。

1158
00:47:05,972 --> 00:47:07,180
不过说实在的，这是一个权衡。

1159
00:47:07,180 --> 00:47:09,560
事实上，代码
更复杂的，因为你会

1160
00:47:09,560 --> 00:47:11,770
看到通过略读
这特殊的例子。

1161
00:47:11,770 --> 00:47:14,302
但是，如果有什么
这里的一些制胜法宝。

1162
00:47:14,302 --> 00:47:17,010
如果我们不采取一步
倒退，但一个巨大的进步

1163
00:47:17,010 --> 00:47:19,180
并实现数据
结构，通过它我们

1164
00:47:19,180 --> 00:47:22,870
可以找到像杰克或元素
恭或任何其他元素

1165
00:47:22,870 --> 00:47:25,870
在这个阵列中的真正的固定时间？

1166
00:47:25,870 --> 00:47:26,920
搜索是恒定的。

1167
00:47:26,920 --> 00:47:28,320
删除是恒定的。

1168
00:47:28,320 --> 00:47:29,570
插入件是恒定的。

1169
00:47:29,570 --> 00:47:32,260
所有这些操作都是恒定的。

1170
00:47:32,260 --> 00:47:33,750
这将是我们的制胜法宝。

1171
00:47:33,750 --> 00:47:36,690
而这正是我们
下次还会回升。

1172
00:47:36,690 --> 00:47:38,600
到时候见。

1173
00:47:38,600 --> 00:47:39,371