1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [第6周]

2
00:00:02,000 --> 00:00:04,000
[戴维·J·马兰] [哈佛大学]

3
00:00:04,000 --> 00:00:08,000
这是CS50。[CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> 这是CS50，这是第6周开始，

5
00:00:12,000 --> 00:00:16,000
这样一对夫妇的新工具现在可供您利用，

6
00:00:16,000 --> 00:00:19,000
其中第一个被称为CS50风格。

7
00:00:19,000 --> 00:00:22,000
奇怪的是，如果你是像我这样的教学研究员，

8
00:00:22,000 --> 00:00:26,000
你可能已经看到了一个程序，其风格看起来有点像这样。

9
00:00:26,000 --> 00:00:30,000
也许你开始削减一些角落深夜，否则你会稍后处理，

10
00:00:30,000 --> 00:00:32,000
然后一个TF或CA在办公时间内。

11
00:00:32,000 --> 00:00:34,000
然后，我们很难读。

12
00:00:34,000 --> 00:00:38,000
，此代码在语法上是正确的，它会编译，它实际上运行。

13
00:00:38,000 --> 00:00:40,000
但它绝对不是一个风格的5。

14
00:00:40,000 --> 00:00:45,000
>> 但是现在，如果我们去到这个目录

15
00:00:45,000 --> 00:00:48,000
并请注意，我有conditions2.c

16
00:00:48,000 --> 00:00:55,000
我运行这个新的命令，style50，在这个文件conditions2.c，输入，

17
00:00:55,000 --> 00:00:57,000
注意，它告诉我，它已经程式化。

18
00:00:57,000 --> 00:01:00,000
Gedit的注意到，该文件已经在磁盘上更改，

19
00:01:00,000 --> 00:01:08,000
如果我点击重新加载，你所有的问题，现在实现自动化。

20
00:01:08,000 --> 00:01:15,000
[掌声]

21
00:01:15,000 --> 00:01:17,000
这是我们做这个周末的事情之一。

22
00:01:17,000 --> 00:01:20,000
要认识到，它是不完善的，因为有一些代码，

23
00:01:20,000 --> 00:01:23,000
，那根本不会是完美的样式，

24
00:01:23,000 --> 00:01:26,000
但现在意识到这是一个工具，你可以利用

25
00:01:26,000 --> 00:01:33,000
如果仅仅是为了收拾一些更errantly放在花括号等。

26
00:01:33,000 --> 00:01:36,000
>> 但更引人注目的是CS50检查。

27
00:01:36,000 --> 00:01:39,000
CS50检查，你其实可以执行相同的正确性测试

28
00:01:39,000 --> 00:01:42,000
对自己的代码，教学研究员能。

29
00:01:42,000 --> 00:01:44,000
这是一个命令行实用程序，现在在家电

30
00:01:44,000 --> 00:01:46,000
只要你做按update50

31
00:01:46,000 --> 00:01:49,000
pset的4种规格，并使用它基本上是这样的。

32
00:01:49,000 --> 00:01:51,000
运行该命令check50。

33
00:01:51,000 --> 00:01:56,000
然后，你将在一个命令行参数，或更普遍地被称为一个开关或标志。

34
00:01:56,000 --> 00:01:58,000
一般情况下，有连字符的事情，被称为一个开关

35
00:01:58,000 --> 00:02:02,000
一个命令行程序，-c指定

36
00:02:02,000 --> 00:02:04,000
你要运行的检查。

37
00:02:04,000 --> 00:02:07,000
>> 要运行的测试，你唯一标识此字符串，

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize。

39
00:02:10,000 --> 00:02:13,000
换句话说，这只是一个任意的，但唯一的字符串

40
00:02:13,000 --> 00:02:18,000
我们用来唯一识别的pset 4的正确性测试。

41
00:02:18,000 --> 00:02:21,000
然后指定一个空间分隔的列表中的文件要上传

42
00:02:21,000 --> 00:02:24,000
CS50检查分析。

43
00:02:24,000 --> 00:02:29,000
举例来说，如果我进入我的解决方案为resize.c这里

44
00:02:29,000 --> 00:02:31,000
让我打开了一个更大的终端窗口

45
00:02:31,000 --> 00:02:42,000
和我继续运行让我们check50-C 2012/pset4/resize说的，

46
00:02:42,000 --> 00:02:46,000
然后我继续前进，指定的文件名，

47
00:02:46,000 --> 00:02:49,000
resize.c，然后按Enter键，它会压缩，

48
00:02:49,000 --> 00:02:53,000
它上传时，它会检查，我只是一大堆的测试失败。

49
00:02:53,000 --> 00:02:59,000
在左上角的一个红说，resize.c和B​​MP存在。

50
00:02:59,000 --> 00:03:01,000
这是测试。这是我们的问题。

51
00:03:01,000 --> 00:03:04,000
它的不开心，因为得到的答案是假的。

52
00:03:04,000 --> 00:03:08,000
白色它下面的文本说，预计bmp.h存在的，而这仅仅是我的错。

53
00:03:08,000 --> 00:03:11,000
我忘了把它上传，所以我需要这两个文件上传，

54
00:03:11,000 --> 00:03:14,000
resize.c和bmp.h.

55
00:03:14,000 --> 00:03:17,000
但现在发现所有其他测试是黄色的，因为他们还没有遇到，

56
00:03:17,000 --> 00:03:21,000
等的笑脸是垂直的，因为他既不快乐也不悲伤，

57
00:03:21,000 --> 00:03:25,000
但我们必须纠正这个问题，在红色之前的其他检查运行。

58
00:03:25,000 --> 00:03:27,000
>> 让我来解决这个问题。

59
00:03:27,000 --> 00:03:30,000
让我放大并重新运行此，这一次bmp.h

60
00:03:30,000 --> 00:03:34,000
在命令行上，输入，现在如果一切顺利的话，

61
00:03:34,000 --> 00:03:38,000
要检查，然后返回一个结果，屏住呼吸，

62
00:03:38,000 --> 00:03:42,000
所有的绿色，这意味着我做的真的很好的pset 4。

63
00:03:42,000 --> 00:03:44,000
你可以看到和推断的描述性文字在这里

64
00:03:44,000 --> 00:03:47,000
它到底是什么，我们测试。

65
00:03:47,000 --> 00:03:49,000
我们测试了第一个不存在的文件吗？

66
00:03:49,000 --> 00:03:51,000
然后，我们测试的不resize.c编译吗？

67
00:03:51,000 --> 00:03:58,000
然后，我们测试它不能调整一个1x1像素的BMP，调整大小的因素，当n为1。

68
00:03:58,000 --> 00:04:01,000
现在，如果你不知道n是什么，你会当你潜入的pset 4，

69
00:04:01,000 --> 00:04:04,000
但是，仅仅是进行仔细的检查，以确保你不调整大小

70
00:04:04,000 --> 00:04:08,000
图像，如果在所有的大小调整系数为1。

71
00:04:08,000 --> 00:04:14,000
如果相反，它会调整到2x2正确的1x1像素的1x1像素的BMP

72
00:04:14,000 --> 00:04:19,000
当n是2，则同样地，矿形成相应。

73
00:04:19,000 --> 00:04:22,000
>> 总之，这是，一，采取交叉手指

74
00:04:22,000 --> 00:04:25,000
的等式就在你提交你的pset。

75
00:04:25,000 --> 00:04:28,000
你会确切地知道你的TF很快就会知道

76
00:04:28,000 --> 00:04:30,000
当你去提交一些这些问题集，

77
00:04:30,000 --> 00:04:34,000
也是教学的动机是真的把

78
00:04:34,000 --> 00:04:37,000
这样的机会在你面前，当你知道一个先验

79
00:04:37,000 --> 00:04:39,000
有代码中的错误，并没有被通过的测试，

80
00:04:39,000 --> 00:04:43,000
你可以把前面的更有效的时间来解决这些问题

81
00:04:43,000 --> 00:04:45,000
而不是失分，从你的TF，得到的反馈

82
00:04:45,000 --> 00:04:48,000
，然后走了，“啊，”我应该已经猜到了。

83
00:04:48,000 --> 00:04:50,000
现在，至少有一个工具，以帮助您找到。

84
00:04:50,000 --> 00:04:52,000
这不是要指出其中的错误，但它会告诉你

85
00:04:52,000 --> 00:04:54,000
什么是它的症状。

86
00:04:54,000 --> 00:04:57,000
>> 现在，实现不一定详尽的测试。

87
00:04:57,000 --> 00:04:59,000
只是因为你得到满屏幕的绿色笑脸

88
00:04:59,000 --> 00:05:02,000
并不意味着你的代码是完美的，但它确实意味着

89
00:05:02,000 --> 00:05:06,000
已通过一定的测试规范所规定的。

90
00:05:06,000 --> 00:05:08,000
有时候，我们将不会公布检查。

91
00:05:08,000 --> 00:05:10,000
比如，侦探小说，一个方面的pset 4，

92
00:05:10,000 --> 00:05:15,000
是一种令人失望的，如果我们给你

93
00:05:15,000 --> 00:05:18,000
的答案，因为它是什么，而且也透露了一些方法来

94
00:05:18,000 --> 00:05:21,000
谁的人是在这红色的噪音。

95
00:05:21,000 --> 00:05:24,000
该规范将在未来的指定pset的5起

96
00:05:24,000 --> 00:05:26,000
什么检查为你存在。

97
00:05:26,000 --> 00:05:28,000
你会发现底部有这个白色的URL。

98
00:05:28,000 --> 00:05:30,000
就目前而言，这仅仅是诊断输出。

99
00:05:30,000 --> 00:05:33,000
如果您访问该URL时，你会得到一大堆疯狂的，神秘的消息

100
00:05:33,000 --> 00:05:36,000
，欢迎您翻阅，但它主要是为工作人员

101
00:05:36,000 --> 00:05:41,000
这样我们就可以诊断和调试check50本身的错误。

102
00:05:41,000 --> 00:05:46,000
>> 没有废话不多说，让我们继续前进，到我们离开的地方。

103
00:05:46,000 --> 00:05:48,000
CS50库我们想当然的几个星期，

104
00:05:48,000 --> 00:05:52,000
但上周，我们开始脱皮层之一。

105
00:05:52,000 --> 00:05:55,000
我们开始搁置赞成什么，而不是字符串吗？

106
00:05:55,000 --> 00:05:57,000
[学生]字符。

107
00:05:57,000 --> 00:05:59,000
CHAR *，这一直是一个char *，

108
00:05:59,000 --> 00:06:03,000
但现在我们不必假装它是一个真正的数据类型的字符串。

109
00:06:03,000 --> 00:06:06,000
相反，它一直为char *各种各样的代名词，

110
00:06:06,000 --> 00:06:09,000
字符串是一个字符序列，

111
00:06:09,000 --> 00:06:14,000
那么，为什么它的意义表示为char *的字符串？

112
00:06:14,000 --> 00:06:20,000
什么是一个char *的背景下，这个概念的一个字符串表示？

113
00:06:20,000 --> 00:06:23,000
是的。>> [学生]：第一个字符。

114
00:06:23,000 --> 00:06:25,000
好，第一个字符，但不完全的第一个字符。

115
00:06:25,000 --> 00:06:27,000
[学生]。

116
00:06:27,000 --> 00:06:29,000
好，第一个字符的地址。

117
00:06:29,000 --> 00:06:33,000
这是需要在计算机的内存中表示字符串

118
00:06:33,000 --> 00:06:36,000
只是其第一个字节的唯一地址。

119
00:06:36,000 --> 00:06:38,000
你甚至不知道它有多长

120
00:06:38,000 --> 00:06:42,000
因为你的身影，动态吗？

121
00:06:42,000 --> 00:06:44,000
[学生]：字符串长度。

122
00:06:44,000 --> 00:06:48,000
您可以调用字符串的长度，优秀的，但如何字符串的长度？

123
00:06:48,000 --> 00:06:50,000
它有什么作用呢？是啊。

124
00:06:50,000 --> 00:06:52,000
[学生]：保持下去，直到你得到的空字符。

125
00:06:52,000 --> 00:06:54,000
是的，没错，它只是遍历一个for循环，while循环，

126
00:06:54,000 --> 00:06:57,000
表示无论从*到结束，并结束

127
00:06:57,000 --> 00:07:01,000
\ 0，所谓的空字符，NUL，

128
00:07:01,000 --> 00:07:05,000
不要混淆为null，这是一个指针，

129
00:07:05,000 --> 00:07:07,000
会在谈话中再次。

130
00:07:07,000 --> 00:07:11,000
>> 我们剥开一层调用getInt，然后在GetString的，我们接过来一看，

131
00:07:11,000 --> 00:07:14,000
和调用这些功能，还是真的，

132
00:07:14,000 --> 00:07:18,000
GetString时，使用一定的函数

133
00:07:18,000 --> 00:07:21,000
实际解析，是读或分析用户的输入。

134
00:07:21,000 --> 00:07:25,000
那是什么新功能？

135
00:07:25,000 --> 00:07:27,000
scanf或sscanf的。它实际上是在几个不同的口味。

136
00:07:27,000 --> 00:07:31,000
的scanf，sscanf的，有fscanf。

137
00:07:31,000 --> 00:07:35,000
现在，虽然，让我们专注于最容易说明的，

138
00:07:35,000 --> 00:07:38,000
让我去进取，不断开拓的家电

139
00:07:38,000 --> 00:07:41,000
这样的文件，scanf1.c。

140
00:07:41,000 --> 00:07:43,000
这是一个超级简单的程序，

141
00:07:43,000 --> 00:07:46,000
但是，做一些事情，我们从来没有做过

142
00:07:46,000 --> 00:07:48,000
没有帮助的CS50库。

143
00:07:48,000 --> 00:07:51,000
这从用户得到一个int。它是如何工作的呢？

144
00:07:51,000 --> 00:07:53,000
那么，在那里的第16行中，

145
00:07:53,000 --> 00:07:56,000
注意到，我们声明一个int称为x，在这一点上的故事，

146
00:07:56,000 --> 00:07:58,000
x的值是什么？

147
00:07:58,000 --> 00:08:00,000
[听不见的学生反应]

148
00:08:00,000 --> 00:08:02,000
大卫M.]右，谁知道，一些垃圾的价值可能在17，我们只是告诉用户

149
00:08:02,000 --> 00:08:06,000
给我一个号码，请步和第18步是它得到有趣的。

150
00:08:06,000 --> 00:08:11,000
scanf函数似乎借用一个想法从printf的，因为它在引号中使用这些格式代码。

151
00:08:11,000 --> 00:08:13,000
％d是一个十进制数。

152
00:08:13,000 --> 00:08:21,000
但是，为什么我通过在＆X是x？

153
00:08:21,000 --> 00:08:24,000
前者是正确的。是啊。

154
00:08:24,000 --> 00:08:26,000
[听不见的学生反应]

155
00:08:26,000 --> 00:08:31,000
没错，如果这项计划的目标，如的函数调用getInt本身，

156
00:08:31,000 --> 00:08:34,000
是一个int的用户，我可以通过功能

157
00:08:34,000 --> 00:08:38,000
所有的变量，但我想，如果我不通过引用传递

158
00:08:38,000 --> 00:08:41,000
或地址或指针，所有的目的的代名词，

159
00:08:41,000 --> 00:08:46,000
那么这个函数有没有能力改变这个变量的内容。

160
00:08:46,000 --> 00:08:49,000
这将通过在副本一样的马车版本的Swap

161
00:08:49,000 --> 00:08:51,000
我们已经谈到了几次。

162
00:08:51,000 --> 00:08:54,000
>> 但是，这样＆X，我从字面上传递什么？

163
00:08:54,000 --> 00:08:57,000
[学生]的地址。>> x的地址。

164
00:08:57,000 --> 00:09:01,000
这就像scanf函数调用的函数绘制地图，并在这里说，

165
00:09:01,000 --> 00:09:04,000
这些都是在计算机的内存块的方向

166
00:09:04,000 --> 00:09:07,000
，你可以去存储一些整数中。

167
00:09:07,000 --> 00:09:10,000
为了sscanf的，现在做的，

168
00:09:10,000 --> 00:09:13,000
什么样的运营商，什么样的语法是要使用

169
00:09:13,000 --> 00:09:19,000
即使我们不能看到它，因为别人写了这个功能吗？

170
00:09:19,000 --> 00:09:21,000
换句话说 - 那是什么？

171
00:09:21,000 --> 00:09:23,000
[学生]：X读。

172
00:09:23,000 --> 00:09:27,000
还有的将是一些阅读，但只有考虑到这里的x。

173
00:09:27,000 --> 00:09:30,000
，如果scanf函数是通过x的地址，

174
00:09:30,000 --> 00:09:35,000
语法，什么样的运营商是必然存在的地方

175
00:09:35,000 --> 00:09:38,000
内部，使scanf函数scanf函数的实现

176
00:09:38,000 --> 00:09:42,000
其实可以写一个2号线到该地址吗？

177
00:09:42,000 --> 00:09:44,000
是啊，所以*。

178
00:09:44,000 --> 00:09:47,000
回想一下，*是我们的反引用运算符，这实际上意味着去那里。

179
00:09:47,000 --> 00:09:50,000
>> 一旦你已经交给一个地址，是这里的情况，

180
00:09:50,000 --> 00:09:53,000
scanf的可能是，如果我们环顾四周，它的源代码

181
00:09:53,000 --> 00:09:59,000
* x或相当于真正去到该地址，并把一定的价值。

182
00:09:59,000 --> 00:10:02,000
现在，scanf是如何从键盘输入的，

183
00:10:02,000 --> 00:10:04,000
我们会挥动我们手中的今天。

184
00:10:04,000 --> 00:10:07,000
只是假设操作系统允许sscanf的谈

185
00:10:07,000 --> 00:10:11,000
用户的键盘，但在这一点上，现在在第19行中，

186
00:10:11,000 --> 00:10:14,000
当我们简单地打印出x，它似乎是

187
00:10:14,000 --> 00:10:17,000
scanf函数把一个int x中。

188
00:10:17,000 --> 00:10:19,000
这正是scanf是如何工作的，记得上周

189
00:10:19,000 --> 00:10:25,000
这也正是GetString和调用getInt和其他家庭的功能

190
00:10:25,000 --> 00:10:28,000
最终的作品，尽管略有差异，如sscanf的，

191
00:10:28,000 --> 00:10:31,000
这意味着一个字符串，而不是扫描的键盘。

192
00:10:31,000 --> 00:10:33,000
但是，让我们来看看在这一点差异。

193
00:10:33,000 --> 00:10:37,000
在scanf2，其实我搞砸了。

194
00:10:37,000 --> 00:10:42,000
什么是错的，我会隐藏的评论来解释尽可能多的

195
00:10:42,000 --> 00:10:47,000
这个程序有什么不妥，第2版？

196
00:10:47,000 --> 00:10:55,000
技术可能。

197
00:10:55,000 --> 00:10:57,000
它看起来不错。

198
00:10:57,000 --> 00:11:03,000
它很好地缩进，但

199
00:11:03,000 --> 00:11:07,000
好了，怎么样让我们修剪下来，以更短的问题吗？

200
00:11:07,000 --> 00:11:17,000
第16行。第16行做精确，但技术的英语是什么？

201
00:11:17,000 --> 00:11:20,000
开始有点尴尬。是的，迈克尔。

202
00:11:20,000 --> 00:11:25,000
[学生]：它指向一个字符串的第一个字母。

203
00:11:25,000 --> 00:11:27,000
>> 好了，很近的。让我有一点点进行调整。

204
00:11:27,000 --> 00:11:33,000
指向一个字符串的第一个字母，你声明一个变量叫做缓冲

205
00:11:33,000 --> 00:11:36,000
都将指向一个字符串的首地址，

206
00:11:36,000 --> 00:11:39,000
或者更确切地说，将指向更具体的一个字符。

207
00:11:39,000 --> 00:11:42,000
请注意，它实际上没有指向任何地方，因为没有任何赋值操作符。

208
00:11:42,000 --> 00:11:46,000
有没有等号，所以我们正在做的是所谓的缓冲区分配变量。

209
00:11:46,000 --> 00:11:49,000
它正好是32位的，因为它是一个指针，

210
00:11:49,000 --> 00:11:52,000
和缓冲区的内容想必最终

211
00:11:52,000 --> 00:11:57,000
将包含一个字符的地址，但现在，缓冲包含什么？

212
00:11:57,000 --> 00:11:59,000
只是一些假的，谁知道，一些垃圾的价值，

213
00:11:59,000 --> 00:12:03,000
因为我们并没有显式初始化，所以，我们不应该做任何假设。

214
00:12:03,000 --> 00:12:06,000
好了，现在17行，什么17行办呢？

215
00:12:06,000 --> 00:12:08,000
也许这将温暖起来。

216
00:12:08,000 --> 00:12:10,000
它打印一个字符串，对不对？

217
00:12:10,000 --> 00:12:12,000
它打印出字符串请。

218
00:12:12,000 --> 00:12:15,000
>> 第18行是一种熟悉的，现在在我们刚刚看到的方差

219
00:12:15,000 --> 00:12:18,000
但具有不同的格式代码，所以在第18行中，

220
00:12:18,000 --> 00:12:23,000
我们在这里告诉scanf函数是一个内存块的地址。

221
00:12:23,000 --> 00:12:27,000
我希望你能响在一个字符串中，暗示的％s的，

222
00:12:27,000 --> 00:12:32,000
但问题是，我们并没有在这里做了几件事情。

223
00:12:32,000 --> 00:12:35,000
的问题之一是什么呢？

224
00:12:35,000 --> 00:12:38,000
[学生]：它试图取消引用一个空指针。

225
00:12:38,000 --> 00:12:41,000
好，空，否则未知的指针。

226
00:12:41,000 --> 00:12:45,000
你交给scanf函数的地址，但你刚才说刚才

227
00:12:45,000 --> 00:12:49,000
该地址是一些垃圾的价值，因为我们没有实际分配任何东西，

228
00:12:49,000 --> 00:12:53,000
所以你告诉scanf函数有效地去把一个字符串，

229
00:12:53,000 --> 00:12:56,000
但我们不知道这里还

230
00:12:56,000 --> 00:12:59,000
所以我们并没有实际分配的内存的缓冲区。

231
00:12:59,000 --> 00:13:03,000
此外，你甚至也没有告诉scanf函数吗？

232
00:13:03,000 --> 00:13:06,000
假设这是一个内存块，它是不是垃圾的价值，

233
00:13:06,000 --> 00:13:09,000
但你还是没有告诉scanf的一些重要的东西。

234
00:13:09,000 --> 00:13:12,000
[学生]：它实际上是符号。

235
00:13:12,000 --> 00:13:15,000
与符号，所以在这种情况下，它没关系。

236
00:13:15,000 --> 00:13:18,000
因为缓冲区已经被声明为一个指针

237
00:13:18,000 --> 00:13:22,000
*的语法，我们并不需要使用符号

238
00:13:22,000 --> 00:13:25,000
，因为它是一个地址，但我想我听到了这里。

239
00:13:25,000 --> 00:13:27,000
[学生]：它有多大？

240
00:13:27,000 --> 00:13:29,000
好，我们没有告诉scanf函数有多大，这个缓冲区，

241
00:13:29,000 --> 00:13:32,000
这意味着即使缓冲区的指针，

242
00:13:32,000 --> 00:13:35,000
我们说scanf函数，把一个字符串在这里，

243
00:13:35,000 --> 00:13:38,000
但在这里，可能是2个字节，也可能是10个字节，它可能是一个兆字节。

244
00:13:38,000 --> 00:13:41,000
scanf函数不知道，因为这是一个内存块

245
00:13:41,000 --> 00:13:43,000
据推测，它不是一个字符串还。

246
00:13:43,000 --> 00:13:48,000
这只是一个字符串，一旦你写个字符，\ 0到该内存块。

247
00:13:48,000 --> 00:13:51,000
现在，它只是一些的内存块。

248
00:13:51,000 --> 00:13:55,000
scanf函数不知道什么时候停止写入到该地址。

249
00:13:55,000 --> 00:13:59,000
>> 如果你还记得我随意在键盘上键入一些例子，在过去的

250
00:13:59,000 --> 00:14:03,000
尝试缓冲区溢出，正是和我们聊上周五。

251
00:14:03,000 --> 00:14:07,000
如果攻击者以某种方式注入到你的程序中一个更大的字

252
00:14:07,000 --> 00:14:10,000
或句子或短语，那么你，希望你可以溢出

253
00:14:10,000 --> 00:14:13,000
一个内存块，它可以有不良后果，

254
00:14:13,000 --> 00:14:15,000
如在整个程序本身。

255
00:14:15,000 --> 00:14:17,000
我们需要以某种方式解决这个问题。

256
00:14:17,000 --> 00:14:20,000
让我缩小，进入第3版的这个方案。

257
00:14:20,000 --> 00:14:22,000
这是一个稍微好一点。

258
00:14:22,000 --> 00:14:24,000
在这个版本中，发现其中的差别。

259
00:14:24,000 --> 00:14:27,000
在第16行，我再次声明一个变量叫做缓冲，

260
00:14:27,000 --> 00:14:29,000
但究竟是什么呢？

261
00:14:29,000 --> 00:14:33,000
这是一个数组的16个字符。

262
00:14:33,000 --> 00:14:36,000
这是一件好事，因为这意味着我现在可以告诉scanf函数

263
00:14:36,000 --> 00:14:39,000
这里是一个实际的内存块。

264
00:14:39,000 --> 00:14:42,000
现在为指针的数组，你几乎可以认为，

265
00:14:42,000 --> 00:14:44,000
即使他们不是实际上是等效的。

266
00:14:44,000 --> 00:14:47,000
他们会在不同的上下文中有不同的表现。

267
00:14:47,000 --> 00:14:50,000
但它肯定是缓冲区被引用的情况下，

268
00:14:50,000 --> 00:14:53,000
16个连续的字符，因为这是一个数组是

269
00:14:53,000 --> 00:14:55,000
和现在已经有好几个星期。

270
00:14:55,000 --> 00:14:59,000
>> 在这里，我说的，scanf是这里的一大块的内存。

271
00:14:59,000 --> 00:15:01,000
这一次，它实际上是一个内存块，

272
00:15:01,000 --> 00:15:07,000
但为什么这个程序仍然可利用的呢？

273
00:15:07,000 --> 00:15:11,000
什么仍然是错的？

274
00:15:11,000 --> 00:15:14,000
我说给我16个字节，但是，

275
00:15:14,000 --> 00:15:16,000
[学生]：如果输入超过16？

276
00:15:16,000 --> 00:15:20,000
没错，如果用户键入17个字符或1700个字符是什么？

277
00:15:20,000 --> 00:15:23,000
事实上，让我们看看如果我们不能现在绊倒这个错误。

278
00:15:23,000 --> 00:15:25,000
这是更好，但并不完美。

279
00:15:25,000 --> 00:15:28,000
让，我继续运行编译这个程序，使scanf3的。

280
00:15:28,000 --> 00:15:34,000
让我跑scanf3，字符串，请：您好，我们似乎会好起来的。

281
00:15:34,000 --> 00:15:37,000
让我尝试稍长，你好。

282
00:15:37,000 --> 00:15:42,000
好吧，让我们不打招呼，你今天怎么，Enter键。

283
00:15:42,000 --> 00:15:54,000
在这里获得一种幸运，让我们说，你好，你怎么样。

284
00:15:54,000 --> 00:15:56,000
该死的。

285
00:15:56,000 --> 00:16:03,000
好了，我们是幸运的。让我们来看看，如果我们能够解决这个问题。

286
00:16:03,000 --> 00:16:06,000
不，它不会让我抄。

287
00:16:06,000 --> 00:16:09,000
让我们再试一次。

288
00:16:09,000 --> 00:16:12,000
所有权利。

289
00:16:12,000 --> 00:16:20,000
我们会看到，我可以假装多久焦点，而这样做。

290
00:16:20,000 --> 00:16:23,000
该死的。这是相当合适的，其实。

291
00:16:23,000 --> 00:16:26,000
我们走吧。

292
00:16:26,000 --> 00:16:30,000
点而成。

293
00:16:30,000 --> 00:16:34,000
>> ，尴尬的，但它也是，它也是引起极大的混乱的来源之一

294
00:16:34,000 --> 00:16:38,000
编写程序时有错误的，因为他们表现自己

295
00:16:38,000 --> 00:16:40,000
有时在一段时间内只有一次。

296
00:16:40,000 --> 00:16:43,000
现实的情况是，即使你的代码被彻底打破，

297
00:16:43,000 --> 00:16:46,000
它可能只被彻底打破了曾经在一段时间内

298
00:16:46,000 --> 00:16:49,000
因为有时候，基本上会发生什么是操作系统分配

299
00:16:49,000 --> 00:16:52,000
一点点更多的内存比你实际需要的不管是什么原因，

300
00:16:52,000 --> 00:16:57,000
所以没有其他人使用的内存块的16个字符，

301
00:16:57,000 --> 00:17:01,000
所以，如果你去17，18，19，不论如何，这不是什么大不了的。

302
00:17:01,000 --> 00:17:04,000
现在，计算机，即使在这一点上，不崩溃

303
00:17:04,000 --> 00:17:09,000
其他的东西，可能最终使用的字节数17或18或19，

304
00:17:09,000 --> 00:17:14,000
在这一点，你把你的数据有，但过长，

305
00:17:14,000 --> 00:17:18,000
要覆盖潜在的一些其他功能。

306
00:17:18,000 --> 00:17:21,000
它不一定是要保持不变，

307
00:17:21,000 --> 00:17:23,000
但不一定会导致段故障。

308
00:17:23,000 --> 00:17:26,000
但是，在这种情况下，我终于提供了足够的字符

309
00:17:26,000 --> 00:17:29,000
，我基本上是超出了我的内存段，咣当，

310
00:17:29,000 --> 00:17:33,000
操作系统的说：“对不起，这是没有好，分割故障。”

311
00:17:33,000 --> 00:17:38,000
>> 让我们来看看，如果现在仍然在我的目录

312
00:17:38,000 --> 00:17:40,000
请注意，我这里有这个文件，核心。

313
00:17:40,000 --> 00:17:42,000
请注意，这是再次呼吁一个核心转储。

314
00:17:42,000 --> 00:17:46,000
它本质上是一个文件，其中包含你的程序的内存中的内容

315
00:17:46,000 --> 00:17:48,000
在点，它坠毁，

316
00:17:48,000 --> 00:17:51,000
只是为了尝试一个简单的例子：在这里让我去

317
00:17:51,000 --> 00:17:57,000
和运行gdb上scanf3的，然后指定了第三个参数，称为核心，

318
00:17:57,000 --> 00:18:01,000
并注意在这里，如果我列出的代码，

319
00:18:01,000 --> 00:18:06,000
像往常一样，我们就可以用gdb开始步行通过这个节目，

320
00:18:06,000 --> 00:18:10,000
我可以运行它，并尽快为我打的步骤，在gdb的命令

321
00:18:10,000 --> 00:18:13,000
只要我打了潜在的车线后键入一个巨大的字符串，

322
00:18:13,000 --> 00:18:16,000
我将能够识别在这里。

323
00:18:16,000 --> 00:18:19,000
更多关于这一点，虽然，在部分核心转储

324
00:18:19,000 --> 00:18:22,000
等，让您可以闲逛内将核心转储

325
00:18:22,000 --> 00:18:27,000
看到在哪一行的计划失败。

326
00:18:27,000 --> 00:18:32,000
然后在指针和地址的任何问题？

327
00:18:32,000 --> 00:18:36,000
因为今天开始，我们要开始考虑是理所当然的，这些东西存在

328
00:18:36,000 --> 00:18:40,000
我们知道究竟是什么。

329
00:18:40,000 --> 00:18:42,000
是。

330
00:18:42,000 --> 00:18:46,000
>> [学生]：为什么你没有把符号的部分

331
00:18:46,000 --> 00:18:48,000
这个问题问得好。

332
00:18:48,000 --> 00:18:51,000
为什么我没有把一个符号的字符数组，因为我以前的

333
00:18:51,000 --> 00:18:53,000
我们的例子吗？

334
00:18:53,000 --> 00:18:55,000
简短的回答是数组是有点特别。

335
00:18:55,000 --> 00:18:59,000
你几乎可以认为一个缓冲区实际上是一个地址，

336
00:18:59,000 --> 00:19:03,000
它只是发生的情况下，方括号表示法

337
00:19:03,000 --> 00:19:06,000
是一个方便的，这样我们就可以进入支架，支架1，

338
00:19:06,000 --> 00:19:10,000
托架2，而无需使用*符号。

339
00:19:10,000 --> 00:19:13,000
这是一个有点善意的谎言，因为数组和指针

340
00:19:13,000 --> 00:19:17,000
，其实是有点不同，但他们往往但并不总是可以互换使用。

341
00:19:17,000 --> 00:19:21,000
总之，当一个函数需要一个指针，指向一个内存块，

342
00:19:21,000 --> 00:19:24,000
您可以通过malloc返回的地址，

343
00:19:24,000 --> 00:19:29,000
，我们将看到的malloc再过不了多久，你可以通过它的名称的数组。

344
00:19:29,000 --> 00:19:32,000
你不必做符号的数组，因为他们已经

345
00:19:32,000 --> 00:19:34,000
基本上和地址。

346
00:19:34,000 --> 00:19:36,000
这是一个例外。

347
00:19:36,000 --> 00:19:39,000
让他们特别的方括号。

348
00:19:39,000 --> 00:19:41,000
>> 你可以把一个符号旁边的缓冲区？

349
00:19:41,000 --> 00:19:43,000
不能在这种情况下。

350
00:19:43,000 --> 00:19:46,000
这是行不通的，因为这个角落的情况下，

351
00:19:46,000 --> 00:19:49,000
数组是不太实际的地址。

352
00:19:49,000 --> 00:19:54,000
但是，我们也许会回来，不久与其他的例子。

353
00:19:54,000 --> 00:19:56,000
让我们尝试在这里解决的一个问题。

354
00:19:56,000 --> 00:20:00,000
我们有一个数据结构，我们已经使用了一段时间被称为数组。

355
00:20:00,000 --> 00:20:02,000
典型的例子，这就是我们刚。

356
00:20:02,000 --> 00:20:04,000
但数组有一定的积极以及不利的缺点。

357
00:20:04,000 --> 00:20:06,000
数组是不错的，为什么呢？

358
00:20:06,000 --> 00:20:11,000
什么是一件事，你喜欢你喜欢的阵列有关数组的范围内吗？

359
00:20:11,000 --> 00:20:13,000
方便他们什么？引人注目的是什么？

360
00:20:13,000 --> 00:20:18,000
为什么我们向他们介绍摆在首位？

361
00:20:18,000 --> 00:20:20,000
是啊。

362
00:20:20,000 --> 00:20:27,000
[学生]：他们可以存储大量的数据，你不必使用整个的事情。

363
00:20:27,000 --> 00:20:29,000
您可以使用一节。

364
00:20:29,000 --> 00:20:32,000
好，一个阵列，可以存储大量的数据，

365
00:20:32,000 --> 00:20:35,000
你不一定必须使用它的所有，所以你可以overallocate，

366
00:20:35,000 --> 00:20:39,000
这可能是方便的，如果你事先不知道有多少的期望。

367
00:20:39,000 --> 00:20:41,000
>> GetString的是一个完美的例子。

368
00:20:41,000 --> 00:20:44,000
GetString时，我们写的，不知道多少个字符，

369
00:20:44,000 --> 00:20:48,000
所以事实上，我们可以分配的连续内存块还是不错的。

370
00:20:48,000 --> 00:20:51,000
数组也解决一个问题，我们现在看到几个星期前

371
00:20:51,000 --> 00:20:54,000
您的代码开始下放一些非常糟糕的设计。

372
00:20:54,000 --> 00:20:57,000
回想一下，我创建了一个叫大卫的学生结构，

373
00:20:57,000 --> 00:21:00,000
然后这实际上是一种替代方法，虽然

374
00:21:00,000 --> 00:21:04,000
有一个名为name的变量与另一个变量，我认为，房子，

375
00:21:04,000 --> 00:21:08,000
和另一个变量称为ID，因为在这个故事中，我想介绍一些其他

376
00:21:08,000 --> 00:21:11,000
像Rob到程序中，所以后来我决定等待一分钟，

377
00:21:11,000 --> 00:21:13,000
我要重命名这些变量。

378
00:21:13,000 --> 00:21:16,000
让我们把我的NAME1，ID1，house1。

379
00:21:16,000 --> 00:21:20,000
让我们把抢夺的名称2，house2，ID2。

380
00:21:20,000 --> 00:21:22,000
但是，然后等待一分钟，汤米？

381
00:21:22,000 --> 00:21:24,000
然后，我们有三个变量。

382
00:21:24,000 --> 00:21:27,000
我们引进了别人，四组变量。

383
00:21:27,000 --> 00:21:30,000
世界开始变得混乱非常迅速，

384
00:21:30,000 --> 00:21:33,000
所以我们引入了结构，什么是引人注目的一个结构？

385
00:21:33,000 --> 00:21:39,000
什么是一个C结构让你这样做吗？

386
00:21:39,000 --> 00:21:42,000
这是今天真的很尴尬。

387
00:21:42,000 --> 00:21:44,000
什么？>> [听不见的学生反应]

388
00:21:44,000 --> 00:21:47,000
是啊，特别是上，typedef可以让你创建一个新的数据类型，

389
00:21:47,000 --> 00:21:51,000
结构，struct关键字，让你封装

390
00:21:51,000 --> 00:21:54,000
概念上相关的数据块

391
00:21:54,000 --> 00:21:56,000
此后他们类似的学生。

392
00:21:56,000 --> 00:21:58,000
>> 这是很好的，因为现在我们可以模拟

393
00:21:58,000 --> 00:22:03,000
更排序的概念相一致的概念，一个学生在一个变量

394
00:22:03,000 --> 00:22:07,000
而不是任意具有一个为一个字符串，一个用于一个ID，等等。

395
00:22:07,000 --> 00:22:10,000
数组是不错的，因为他们让我们开始清理我们的代码。

396
00:22:10,000 --> 00:22:13,000
但现在是一个缺点的数组？

397
00:22:13,000 --> 00:22:15,000
你能不能做？是啊。

398
00:22:15,000 --> 00:22:17,000
[学生]：你要知道它有多大。

399
00:22:17,000 --> 00:22:19,000
你要知道它有多大，所以它是一种痛苦。

400
00:22:19,000 --> 00:22:21,000
那些具有编程经验知道，在很多语言中，

401
00:22:21,000 --> 00:22:24,000
如Java，你可以问一个内存块，特别是一个数组，

402
00:22:24,000 --> 00:22:28,000
究竟有多大，其长，财产，可以这么说，这是真的很方便。

403
00:22:28,000 --> 00:22:32,000
在C语言中，你甚至可以不调用strlen一般的数组

404
00:22:32,000 --> 00:22:35,000
由于strlen，因为这个词所暗示的，是唯一的字符串，

405
00:22:35,000 --> 00:22:39,000
你可以计算出字符串的长度，因为这个人的惯例

406
00:22:39,000 --> 00:22:43,000
有一个\ 0，而是一个数组，更一般地，仅仅是一块内存。

407
00:22:43,000 --> 00:22:46,000
如果它是一个整型数组，不会有一些特殊的字符

408
00:22:46,000 --> 00:22:48,000
在结束等着你。

409
00:22:48,000 --> 00:22:50,000
你要记住一个数组的长度。

410
00:22:50,000 --> 00:22:54,000
数组的另一个缺点抬头的GetString本身。

411
00:22:54,000 --> 00:22:59,000
数组的另一个缺点什么？

412
00:22:59,000 --> 00:23:01,000
主席先生，只有你和我。

413
00:23:01,000 --> 00:23:04,000
[听不见的学生反应] >>这是什么？

414
00:23:04,000 --> 00:23:06,000
它的声明在堆栈中。

415
00:23:06,000 --> 00:23:09,000
好了，在堆栈上声明。你为什么不这样呢？

416
00:23:09,000 --> 00:23:13,000
[学生]：因为它得到重用。

417
00:23:13,000 --> 00:23:15,000
它得到重用。

418
00:23:15,000 --> 00:23:18,000
好吧，如果你使用一个数组分配内存，

419
00:23:18,000 --> 00:23:21,000
例如，你不能返回它，因为它是在栈上。

420
00:23:21,000 --> 00:23:23,000
好吧，这是一个缺点。

421
00:23:23,000 --> 00:23:25,000
怎么样的数组？

422
00:23:25,000 --> 00:23:28,000
一旦你分配它，你种旋，如果你需要更多的空间

423
00:23:28,000 --> 00:23:30,000
比阵列。

424
00:23:30,000 --> 00:23:34,000
>> 然后，我们介绍，召回时，malloc，这给了我们动态分配内存的能力。

425
00:23:34,000 --> 00:23:37,000
但是，如果我们尝试了完全不同的世界？

426
00:23:37,000 --> 00:23:40,000
如果我们想解决这些问题，一对夫妇的

427
00:23:40,000 --> 00:23:45,000
我们，而不是我的笔已经睡着了，在这里，

428
00:23:45,000 --> 00:23:51,000
如果我们不是想实质上是创建了世界上不再像吗？

429
00:23:51,000 --> 00:23:56,000
这是一个数组，当然，这种恶化，一旦我们打到最后的数组，

430
00:23:56,000 --> 00:24:00,000
我现在不再有另一个整数或其它字符的空间。

431
00:24:00,000 --> 00:24:03,000
如果我们什么样的先发制人说好了，为什么我们不能放松

432
00:24:03,000 --> 00:24:07,000
这个要求是，所有这些内存块是连续的背靠背，

433
00:24:07,000 --> 00:24:10,000
为什么不，当我需要一个int或一个字符，

434
00:24:10,000 --> 00:24:12,000
只要给我空间，其中之一吗？

435
00:24:12,000 --> 00:24:14,000
当我需要，给我另一个空间，

436
00:24:14,000 --> 00:24:16,000
当我需要，给我一个空间。

437
00:24:16,000 --> 00:24:19,000
优势是，如果别人

438
00:24:19,000 --> 00:24:21,000
在这里，占用内存没什么大不了的。

439
00:24:21,000 --> 00:24:25,000
我会承担这额外的内存块，那么这个人。

440
00:24:25,000 --> 00:24:28,000
>> 现在，唯一的缺点是，几乎感觉就像我有

441
00:24:28,000 --> 00:24:30,000
一大堆不同的变量。

442
00:24:30,000 --> 00:24:33,000
这感觉就像是5个不同的变量潜在的。

443
00:24:33,000 --> 00:24:36,000
但是，如果我们偷的想法字符串

444
00:24:36,000 --> 00:24:41,000
据此，我们以某种方式连接这些东西放在一起从理论上讲，和什么如果我这样做吗？

445
00:24:41,000 --> 00:24:44,000
这是我很差绘制的箭头。

446
00:24:44,000 --> 00:24:46,000
但是，假如这些内存块

447
00:24:46,000 --> 00:24:52,000
指出的，这家伙，谁没有兄弟姐妹在他的右边，

448
00:24:52,000 --> 00:24:54,000
有没有这样的箭头。

449
00:24:54,000 --> 00:24:56,000
其实，这是什么所谓的链接列表。

450
00:24:56,000 --> 00:25:00,000
这是一个新的数据结构，使我们能够分配的内存块，

451
00:25:00,000 --> 00:25:03,000
然后又一次，另一个，然后再在任何时候，我们要

452
00:25:03,000 --> 00:25:07,000
在一个程序，我们还记得，他们都以某种方式相关的

453
00:25:07,000 --> 00:25:11,000
从字面上链接在一起，我们这样做，形象地在这里有一个箭头。

454
00:25:11,000 --> 00:25:15,000
但是，在代码中，会是什么机制，通过它，你可以以某种方式连接，

455
00:25:15,000 --> 00:25:20,000
几乎一样从头开始，另一块块？

456
00:25:20,000 --> 00:25:22,000
我们可以用一个指针，对不对？

457
00:25:22,000 --> 00:25:25,000
因为真正的箭头，从左上角的正方形，

458
00:25:25,000 --> 00:25:31,000
这家伙在这里，这其中，包含在这个广场

459
00:25:31,000 --> 00:25:34,000
不只是一些整数，不只是一些字符，但如果我真的分配

460
00:25:34,000 --> 00:25:37,000
一点点额外的空间，所以，现在，

461
00:25:37,000 --> 00:25:41,000
我的每一个内存块，即使这要花费我，

462
00:25:41,000 --> 00:25:45,000
其中之一的内存块，现在看起来多了几分矩形

463
00:25:45,000 --> 00:25:47,000
被用于一个数字，如数字1，

464
00:25:47,000 --> 00:25:50,000
如果这个家伙，然后存储数字2，

465
00:25:50,000 --> 00:25:52,000
这其他的内存块，用于箭头，

466
00:25:52,000 --> 00:25:54,000
或者更具体而言，一个指针。

467
00:25:54,000 --> 00:25:59,000
并想我存储在这里，我使用它来指向那个家伙，

468
00:25:59,000 --> 00:26:02,000
现在这家伙，让我们假设我只需要三个这样的内存块。

469
00:26:02,000 --> 00:26:05,000
我会画一条线，表明空。

470
00:26:05,000 --> 00:26:07,000
有没有额外的字符。

471
00:26:07,000 --> 00:26:10,000
>> 事实上，这是我们如何去执行

472
00:26:10,000 --> 00:26:12,000
而这就是所谓的一个链表。

473
00:26:12,000 --> 00:26:18,000
链表是一种新的数据结构，它是一个敲门砖

474
00:26:18,000 --> 00:26:21,000
票友数据结构着手解决问题

475
00:26:21,000 --> 00:26:23,000
沿线Facebook的类型的问题，谷歌型的问题

476
00:26:23,000 --> 00:26:26,000
你有巨大的数据集，它不再削减

477
00:26:26,000 --> 00:26:29,000
连续存储一切，并使用类似线性搜索

478
00:26:29,000 --> 00:26:31,000
甚至一些像二进制搜索。

479
00:26:31,000 --> 00:26:33,000
你想更好的运行时间。

480
00:26:33,000 --> 00:26:37,000
事实上，人们的圣杯，我们将讨论在本周晚些时候或明年

481
00:26:37,000 --> 00:26:41,000
是一种算法，其运行时间是恒定的。

482
00:26:41,000 --> 00:26:44,000
换句话说，它总是以相同的时间量无论

483
00:26:44,000 --> 00:26:47,000
有多大的投入，这确实是引人注目的，

484
00:26:47,000 --> 00:26:49,000
甚至更多的东西比数。

485
00:26:49,000 --> 00:26:51,000
这是什么在屏幕上呢？

486
00:26:51,000 --> 00:26:55,000
每个矩形正是我刚才画的手。

487
00:26:55,000 --> 00:26:59,000
但事情的方式在左边是一个特殊的变量。

488
00:26:59,000 --> 00:27:02,000
这将是一个单一的指针，因为有一个问题

489
00:27:02,000 --> 00:27:04,000
一个链表，因为这些东西被称为，

490
00:27:04,000 --> 00:27:09,000
是，你必须挂到链表的一端。

491
00:27:09,000 --> 00:27:13,000
>> 就像一个字符串，你必须知道的第一个字符的地址。

492
00:27:13,000 --> 00:27:15,000
同样的处理链表。

493
00:27:15,000 --> 00:27:19,000
你必须知道的第一个内存块的地址

494
00:27:19,000 --> 00:27:25,000
因为从那里，你可以达到每一个。

495
00:27:25,000 --> 00:27:27,000
不利的一面。

496
00:27:27,000 --> 00:27:30,000
我们付出什么样的价格，这种多功能的具有动态

497
00:27:30,000 --> 00:27:34,000
相当大的数据结构，如果我们需要更多的内存，做工精细，

498
00:27:34,000 --> 00:27:37,000
只是分配一个块，并画一个指针

499
00:27:37,000 --> 00:27:39,000
旧到新的尾的列表吗？

500
00:27:39,000 --> 00:27:41,000
是啊。

501
00:27:41,000 --> 00:27:43,000
[学生]：这需要约两倍的空间。

502
00:27:43,000 --> 00:27:45,000
它需要两倍的空间，所以这绝对是一个缺点，我们已经看到了这

503
00:27:45,000 --> 00:27:48,000
时间，空间和灵活性之间的权衡前

504
00:27:48,000 --> 00:27:51,000
现在，我们需要的不是这些数值分别为32位。

505
00:27:51,000 --> 00:27:57,000
我们真正需要的数字64，32和32，用于将指针。

506
00:27:57,000 --> 00:27:59,000
但是，嘿，我有2 GB的RAM。

507
00:27:59,000 --> 00:28:02,000
添加另外32位在这里和这里似乎并不认为大不了的。

508
00:28:02,000 --> 00:28:05,000
但对于大型数据集，它肯定加起来到字面上的两倍多。

509
00:28:05,000 --> 00:28:09,000
的另一个缺点什么，或什么功能，我们放弃了，

510
00:28:09,000 --> 00:28:12,000
如果我们是代表一个链表，而不是一个数组列表的东西，？

511
00:28:12,000 --> 00:28:14,000
[学生]：您可以向后遍历。

512
00:28:14,000 --> 00:28:16,000
您可以向后遍历，所以你种拧如果你走

513
00:28:16,000 --> 00:28:19,000
从左至右使用for循环或while循环

514
00:28:19,000 --> 00:28:21,000
然后你会意识到，“哦，我想回到开始的名单。”

515
00:28:21,000 --> 00:28:26,000
你不能因为这些指针只由左到右的箭头表示。

516
00:28:26,000 --> 00:28:29,000
>> 现在，你可以记住列表的开始与另一个变量，

517
00:28:29,000 --> 00:28:31,000
但要记住，这是一个复杂的。

518
00:28:31,000 --> 00:28:35,000
一个数组，不管你走多远，你总是可以做减，减，减，减

519
00:28:35,000 --> 00:28:37,000
回到来处。

520
00:28:37,000 --> 00:28:40,000
另一个缺点是什么？是啊。

521
00:28:40,000 --> 00:28:43,000
[听不见的学生问题]

522
00:28:43,000 --> 00:28:47,000
，所以你可以你实际上只是提出了一个双向链表数据结构，

523
00:28:47,000 --> 00:28:50,000
而事实上，你会增加这些矩形的另一个指针

524
00:28:50,000 --> 00:28:53,000
“其他方向，上攻

525
00:28:53,000 --> 00:28:55,000
现在你就可以遍历来回，

526
00:28:55,000 --> 00:28:59,000
的缺点是，现在你正在使用三次尽可能多的内存，我们使用

527
00:28:59,000 --> 00:29:04,000
并且还加入复杂的代码，你写得到它的权利。

528
00:29:04,000 --> 00:29:08,000
但这些都可能是非常合理的折衷，，如果反转更重要的是。

529
00:29:08,000 --> 00:29:10,000
是啊。

530
00:29:10,000 --> 00:29:12,000
[学生]：你也不能有一个2D链接列表。

531
00:29:12,000 --> 00:29:16,000
好，你可以不真的有一个二维链表。

532
00:29:16,000 --> 00:29:18,000
你可以。这不是那么容易达到的阵列。

533
00:29:18,000 --> 00:29:21,000
与数组一样，你做开放式的支架，封闭的支架，打开支架，封闭支架，

534
00:29:21,000 --> 00:29:23,000
，你会得到一些的二维结构。

535
00:29:23,000 --> 00:29:26,000
你可以实现一个2维链表

536
00:29:26,000 --> 00:29:29,000
如果你这样做附加你提出的第三个指针，这些东西，

537
00:29:29,000 --> 00:29:34,000
如果你认为你的另一个列表3D风格

538
00:29:34,000 --> 00:29:40,000
从屏幕到我们所有人来说，这仅仅是某种形式的另一个产业链。

539
00:29:40,000 --> 00:29:45,000
我们能做到这一点，但它不是简单，只要键入开括号，方括号。是啊。

540
00:29:45,000 --> 00:29:48,000
[听不见的学生问题]

541
00:29:48,000 --> 00:29:50,000
好，所以这是一个真正的踢球者。

542
00:29:50,000 --> 00:29:54,000
>> 这些已经消瘦了，我们喜欢哦，二进制搜索算法，

543
00:29:54,000 --> 00:29:57,000
您可以搜索阵列上的数字板

544
00:29:57,000 --> 00:30:01,000
或电话簿，以便更迅速，如果您使用分而治之

545
00:30:01,000 --> 00:30:05,000
二进制搜索算法，，但二进制搜索需要两个假设。

546
00:30:05,000 --> 00:30:09,000
其中，该数据被排序。

547
00:30:09,000 --> 00:30:11,000
现在，我们可以推测这个排序，

548
00:30:11,000 --> 00:30:14,000
所以也许这不是一个问题，但还承担二进制搜索

549
00:30:14,000 --> 00:30:18,000
你有随机存取的号码列表，

550
00:30:18,000 --> 00:30:21,000
阵列允许您进行随机存取，随机存取，

551
00:30:21,000 --> 00:30:24,000
我的意思是，如果你是一个数组，你需要多少时间

552
00:30:24,000 --> 00:30:26,000
支架0？

553
00:30:26,000 --> 00:30:29,000
一人操作，你只需要使用[0]和你说得对。

554
00:30:29,000 --> 00:30:33,000
没有考虑到位置10多少步？

555
00:30:33,000 --> 00:30:36,000
一步，你只是去[10]你的存在。

556
00:30:36,000 --> 00:30:40,000
相比之下，你怎么在一个链表到第10的整数？

557
00:30:40,000 --> 00:30:42,000
因为你只记得，你必须从头开始

558
00:30:42,000 --> 00:30:45,000
一个链表的开始，就像一个字符串被记住

559
00:30:45,000 --> 00:30:48,000
它的第一个字符的地址，并发现第10整数

560
00:30:48,000 --> 00:30:53,000
或10字符串中的字符，你必须搜索整个该死的东西。

561
00:30:53,000 --> 00:30:55,000
>> 同样，我们还没有解决所有的问题。

562
00:30:55,000 --> 00:31:00,000
我们正在推出新的，但它实际上取决于你想要什么设计。

563
00:31:00,000 --> 00:31:04,000
在实施方面，我们可以借用一个想法，学生结构。

564
00:31:04,000 --> 00:31:07,000
它的语法很相似，但现在的想法是多了几分抽象

565
00:31:07,000 --> 00:31:09,000
比房子，名称和ID。

566
00:31:09,000 --> 00:31:13,000
不过，我建议，我们可以有一个数据结构的C

567
00:31:13,000 --> 00:31:17,000
被称为节点，在幻灯片上显示的最后一个字，

568
00:31:17,000 --> 00:31:21,000
里面一个节点，一个节点是在计算机科学只是一个普通的容器。

569
00:31:21,000 --> 00:31:25,000
它通常画成一个圆或正方形或长方形，因为我们已经做了。

570
00:31:25,000 --> 00:31:27,000
这个数据结构中，我们有一个int，N，

571
00:31:27,000 --> 00:31:29,000
所以这是我想存储的号码。

572
00:31:29,000 --> 00:31:36,000
但是，这是什么第二线，结构节点下的吗？

573
00:31:36,000 --> 00:31:40,000
为什么这是正确的，这个东西发挥什么样的作用，

574
00:31:40,000 --> 00:31:42,000
即使这是一个有点神秘的第一眼？

575
00:31:42,000 --> 00:31:44,000
是啊。

576
00:31:44,000 --> 00:31:46,000
[听不见的学生反应]

577
00:31:46,000 --> 00:31:50,000
没错，*排序的战利品，这是某种类型的指针。

578
00:31:50,000 --> 00:31:53,000
这个指针的名字是任意下，

579
00:31:53,000 --> 00:32:00,000
但我们可以把它叫做我们想要的东西，但什么该指针指向？

580
00:32:00,000 --> 00:32:03,000
[学生]：另一个节点。>>没错，它指向到另外一个这样的节点。

581
00:32:03,000 --> 00:32:05,000
>> 现在，这是排序的好奇心，C.

582
00:32:05,000 --> 00:32:09,000
回想一下，C被读取由编译器从上到下，从左到右，

583
00:32:09,000 --> 00:32:13,000
这意味着，如果 - 这是一个有点不同，从我们所做的与学生。

584
00:32:13,000 --> 00:32:16,000
当我们定义一个学生，我们实际上没有一个字。

585
00:32:16,000 --> 00:32:18,000
刚才说的typedef。

586
00:32:18,000 --> 00:32:20,000
然后，我们必须int的ID，字符串名称，字符串的房子，

587
00:32:20,000 --> 00:32:23,000
然后学生在底部的结构。

588
00:32:23,000 --> 00:32:26,000
此声明是一个有点不同，因为，

589
00:32:26,000 --> 00:32:28,000
再次，C编译器是一个有点哑。

590
00:32:28,000 --> 00:32:30,000
这只是要读从上到下，

591
00:32:30,000 --> 00:32:33,000
因此，如果到达2号线

592
00:32:33,000 --> 00:32:37,000
下一个被声明，它认为，哦，这里有一个变量称为下。

593
00:32:37,000 --> 00:32:39,000
这是一个指针，指向一个结构节点。

594
00:32:39,000 --> 00:32:42,000
编译器就是要实现一个结构节点是什么？

595
00:32:42,000 --> 00:32:44,000
我从来没有听说过这件事之前，

596
00:32:44,000 --> 00:32:47,000
因为这个词节点，否则可能不会出现

597
00:32:47,000 --> 00:32:49,000
直到底部，所以有这样的冗余。

598
00:32:49,000 --> 00:32:53,000
你说结构节点，然后你就可以缩短以后

599
00:32:53,000 --> 00:32:56,000
于typedef在这里，这是因为

600
00:32:56,000 --> 00:33:02,000
我们所引用的结构本身的内部结构。

601
00:33:02,000 --> 00:33:05,000
这是一个疑难杂症有。

602
00:33:05,000 --> 00:33:07,000
>> 一些有趣的问题出现。

603
00:33:07,000 --> 00:33:09,000
我们已经有了一个数字列表。我们怎么插入？

604
00:33:09,000 --> 00:33:11,000
我们如何搜索呢？我们如何删除它？

605
00:33:11,000 --> 00:33:13,000
尤其是现在，我们必须管理所有这些指针。

606
00:33:13,000 --> 00:33:15,000
你以为指针有点令人费解

607
00:33:15,000 --> 00:33:17,000
当你有一个，他们只是想读取一个int。

608
00:33:17,000 --> 00:33:20,000
现在我们就来操纵整个列表的价值。

609
00:33:20,000 --> 00:33:22,000
为什么我们不把我们的5分钟的休息时间，在这里，然后我们会带

610
00:33:22,000 --> 00:33:34,000
一些人在舞台上这样做。

611
00:33:34,000 --> 00:33:36,000
>> C是更多的乐趣时，它的行动了。

612
00:33:36,000 --> 00:33:39,000
哪些人会从字面上是第一吗？

613
00:33:39,000 --> 00:33:41,000
好了，就行了。你是第一个。

614
00:33:41,000 --> 00:33:44,000
谁愿意为9？好吧，9。

615
00:33:44,000 --> 00:33:46,000
9怎么样？ 17？

616
00:33:46,000 --> 00:33:51,000
这里一个小团体。 22和26，前排。

617
00:33:51,000 --> 00:33:53,000
然后怎么样的人在那里被指出。

618
00:33:53,000 --> 00:33:57,000
你有34个。好吧，34就行了。

619
00:33:57,000 --> 00:33:59,000
首先是在那里。好了，你们四个。

620
00:33:59,000 --> 00:34:01,000
我们谁也说9？

621
00:34:01,000 --> 00:34:04,000
谁是我们的9？

622
00:34:04,000 --> 00:34:07,000
谁真正想要的是9？好吧，来吧，是9。

623
00:34:07,000 --> 00:34:10,000
在这里，我们走了。

624
00:34:10,000 --> 00:34:13,000
34，我们将满足你在那里。

625
00:34:13,000 --> 00:34:17,000
第一部分是使自己看起来像他一样。

626
00:34:17,000 --> 00:34:21,000
26，22，17，良好的。

627
00:34:21,000 --> 00:34:25,000
如果你能站到一边，因为我们要malloc你在某一时刻。

628
00:34:25,000 --> 00:34:29,000
>> 好，好。

629
00:34:29,000 --> 00:34:32,000
好，很好，所以让我们在这里问几个问题。

630
00:34:32,000 --> 00:34:34,000
实际上，什么是你的名字吗？“梅艳芳。

631
00:34:34,000 --> 00:34:37,000
梅艳芳，没关系，在这里。

632
00:34:37,000 --> 00:34:41,000
梅艳芳样的帮助我们解决了一个相当简单的问题，第一，

633
00:34:41,000 --> 00:34:44,000
你是怎么做的，而不是一个值是否在列表中呢？

634
00:34:44,000 --> 00:34:48,000
现在，请注意，第一，这里所代表的卢卡斯，

635
00:34:48,000 --> 00:34:52,000
是有点不同的，所以他的一张纸是故意侧身

636
00:34:52,000 --> 00:34:55,000
因为它不是相当高，不占用多少位，

637
00:34:55,000 --> 00:34:58,000
即使在技术上他有相同尺寸的纸张，只是旋转。

638
00:34:58,000 --> 00:35:01,000
但他是一个有点不同，他只有32位的指针，

639
00:35:01,000 --> 00:35:05,000
所有这些家伙都是64位，其中一半是多少，其中一半是指针。

640
00:35:05,000 --> 00:35:08,000
但指针没有描述的，所以如果你们能有点笨拙

641
00:35:08,000 --> 00:35:12,000
用左手指向旁边的人给你。

642
00:35:12,000 --> 00:35:14,000
你是34号。你叫什么名字？

643
00:35:14,000 --> 00:35:16,000
阿里。

644
00:35:16,000 --> 00:35:19,000
阿里，所以实际上，保存的文件在你的右手，左手向下的直线。

645
00:35:19,000 --> 00:35:21,000
表示空的左侧。

646
00:35:21,000 --> 00:35:24,000
>> 现在我们的人的照片是非常一致的。

647
00:35:24,000 --> 00:35:26,000
这实际上是指针的工作方式。

648
00:35:26,000 --> 00:35:29,000
如果你能一点点堆砌方式，所以我不是在用自己的方式。

649
00:35:29,000 --> 00:35:34,000
梅艳芳在这里，找到我的22号，

650
00:35:34,000 --> 00:35:40,000
但假设一个约束的不是人拿着纸片，

651
00:35:40,000 --> 00:35:43,000
但是这是一个列表，你只需要卢卡斯开始

652
00:35:43,000 --> 00:35:46,000
因为他是名符其实的第一个指针。

653
00:35:46,000 --> 00:35:51,000
假设你自己是一个指针，所以你也有能力指向的东西。

654
00:35:51,000 --> 00:35:56,000
你为什么不首先指向的正是卢卡斯指着吗？

655
00:35:56,000 --> 00:35:58,000
好，让我在这里制定了这一点。

656
00:35:58,000 --> 00:36:04,000
为了讨论的方便，让我拉了一个空白页。

657
00:36:04,000 --> 00:36:06,000
你怎么拼写你的名字吗？“梅艳芳。

658
00:36:06,000 --> 00:36:08,000
好了，梅艳芳。

659
00:36:08,000 --> 00:36:18,000
比方说节点*阿尼塔·卢卡斯。

660
00:36:18,000 --> 00:36:22,000
好了，我们不应该给你打电话卢卡斯。我们应该先打电话给你。

661
00:36:22,000 --> 00:36:25,000
这是为什么，其实与现实在这里？

662
00:36:25,000 --> 00:36:27,000
其中，第一个已经存在。

663
00:36:27,000 --> 00:36:30,000
大概是首先被分配在这里的某个地方。

664
00:36:30,000 --> 00:36:35,000
节点*首先，它被分配的名单不知何故。

665
00:36:35,000 --> 00:36:37,000
我不知道这是怎么发生的。这发生在上课前开始。

666
00:36:37,000 --> 00:36:40,000
这个链表人类已创建。

667
00:36:40,000 --> 00:36:44,000
在这一点上的故事，这是所有在Facebook上显然后

668
00:36:44,000 --> 00:36:49,000
在这一点上的故事，梅艳芳已被初始化为等于第一，

669
00:36:49,000 --> 00:36:51,000
这并不意味着在卢卡斯，梅艳芳点。

670
00:36:51,000 --> 00:36:53,000
相反，她指着他指出在

671
00:36:53,000 --> 00:36:57,000
因为相同的地址里面的Lucas的32位 -  1，2，3  - 

672
00:36:57,000 --> 00:37:01,000
现在也Anita的32位 -  1，2，3的内侧。

673
00:37:01,000 --> 00:37:05,000
>> 找到22。你将如何去这样做呢？

674
00:37:05,000 --> 00:37:07,000
那是什么？>>指向任何。

675
00:37:07,000 --> 00:37:11,000
点什么，所以，尽管它作为最好的，你可以在这里行动。

676
00:37:11,000 --> 00:37:15,000
好，好，现在你指着你叫什么名字22？

677
00:37:15,000 --> 00:37:18,000
“拉蒙，拉蒙。，所以拉蒙同比增长22。

678
00:37:18,000 --> 00:37:20,000
现在，您已经做了检查。

679
00:37:20,000 --> 00:37:24,000
拉蒙== 22，如果是的话，例如，我们可以返回true。

680
00:37:24,000 --> 00:37:26,000
让我，而这些人站在这里，有点笨拙

681
00:37:26,000 --> 00:37:32,000
让我做的东西像Bool快速找到。

682
00:37:32,000 --> 00:37:37,000
我要继续前进，并说（节点列表，诠释n）。

683
00:37:37,000 --> 00:37:39,000
跟你说，我马上就回来。我只需要编写一些代码。

684
00:37:39,000 --> 00:37:45,000
现在我要继续前进，并做到这一点，节点梅艳芳=列表。

685
00:37:45,000 --> 00:37:51,000
我要继续前进，并指出，虽然（袁咏仪！= NULL）。

686
00:37:51,000 --> 00:37:57,000
>> 这里的比喻还是有点捉襟见肘，但（袁咏仪！= NULL），我想这样做吗？

687
00:37:57,000 --> 00:38:03,000
我需要一些方法的引用

688
00:38:03,000 --> 00:38:05,000
梅艳芳指向的整数。

689
00:38:05,000 --> 00:38:08,000
在过去，当我们有结构，其中节点是

690
00:38:08,000 --> 00:38:11,000
我们使用点符号，我们会这样说

691
00:38:11,000 --> 00:38:15,000
anita.n，但这里的问题是，Anita是不是结构本身。

692
00:38:15,000 --> 00:38:17,000
她是什么人？

693
00:38:17,000 --> 00:38:21,000
她是一个指针，所以真的，如果我们想用这点表示法

694
00:38:21,000 --> 00:38:23,000
这是怎么回事看故意有点神秘

695
00:38:23,000 --> 00:38:28,000
我们必须做这样的事情去任何Anita的左手指向

696
00:38:28,000 --> 00:38:31,000
然后得到该领域称为n。

697
00:38:31,000 --> 00:38:35,000
Anita是一个指针，但*梅艳芳是什么？

698
00:38:35,000 --> 00:38:38,000
你觉得什么，当你去Anita是指什么？

699
00:38:38,000 --> 00:38:42,000
一个结构，一个节点，一个节点，召回，有一个字段称为n

700
00:38:42,000 --> 00:38:47,000
因为它，记得，这2场，下和n，

701
00:38:47,000 --> 00:38:50,000
我们刚才也看到了这里。

702
00:38:50,000 --> 00:38:53,000
>> 为了真正模仿的代码，

703
00:38:53,000 --> 00:39:02,000
我们可以这样做，并说，如果（（*梅艳芳）N = N），我在寻找的n。

704
00:39:02,000 --> 00:39:04,000
请注意，该功能是通过我关心的数量。

705
00:39:04,000 --> 00:39:10,000
然后我就可以继续做类似返回true。

706
00:39:10,000 --> 00:39:12,000
否则，如果不是这样的情况下，我想这样做吗？

707
00:39:12,000 --> 00:39:19,000
我该如何翻译的代码有什么梅艳芳这样做直观地走在列表中呢？

708
00:39:19,000 --> 00:39:26,000
我应该怎么做模拟梅艳芳的左侧，采取这样的步骤，一步到左边？

709
00:39:26,000 --> 00:39:28,000
[听不见的学生回应] >>那是什么？

710
00:39:28,000 --> 00:39:30,000
[听不见的学生反应]

711
00:39:30,000 --> 00:39:34,000
好，不是一个坏主意，但在过去，当我们已经做到了这一点，我们已经做了梅艳芳+ +

712
00:39:34,000 --> 00:39:37,000
因为这会增加数字1〜梅艳芳，

713
00:39:37,000 --> 00:39:40,000
这通常指向旁边的人，像拉蒙

714
00:39:40,000 --> 00:39:44,000
旁边的人，他或他旁边的人的路线。

715
00:39:44,000 --> 00:39:49,000
但是这还不是相当不错的，在这里，因为这是什么东西在内存中的样子吗？

716
00:39:49,000 --> 00:39:54,000
不是这样的。我们必须禁用。

717
00:39:54,000 --> 00:40:00,000
它看起来像这样在内存中，即使我已经开了1个和2个和3靠近彼此，

718
00:40:00,000 --> 00:40:03,000
如果我们真的模拟这个可以你的家伙，而仍指向相同的人，

719
00:40:03,000 --> 00:40:07,000
你们中的一些采取随机退后一步，一些你一个随机的一步吗？

720
00:40:07,000 --> 00:40:10,000
>> 这个烂摊子仍是一个链表，

721
00:40:10,000 --> 00:40:13,000
但这些人可能是在内存中的任何地方，

722
00:40:13,000 --> 00:40:15,000
阿尼塔+ +没有去上班，为什么呢？

723
00:40:15,000 --> 00:40:19,000
什么位置梅艳芳+ +？

724
00:40:19,000 --> 00:40:21,000
谁知道。

725
00:40:21,000 --> 00:40:24,000
这是一些其他的价值，只是恰巧被插

726
00:40:24,000 --> 00:40:28,000
在所有的这些节点的机会，因为我们不使用一个数组。

727
00:40:28,000 --> 00:40:30,000
我们分配每个节点。

728
00:40:30,000 --> 00:40:32,000
好吧，如果你们可以清理自己回来了。

729
00:40:32,000 --> 00:40:37,000
最后，我提议，而不是梅艳芳+ +，而不是做梅艳芳得到

730
00:40:37,000 --> 00:40:42,000
好，为什么我们不走任何Anita是指向，然后做下？

731
00:40:42,000 --> 00:40:45,000
换句话说，我们去拉蒙，他的22号，

732
00:40:45,000 --> 00:40:51,000
然后，接下来就是虽然梅艳芳模仿他的左手指针。

733
00:40:51,000 --> 00:40:54,000
但她不会走的更远，因为我们比拉蒙发现有22。

734
00:40:54,000 --> 00:40:56,000
但是，这将是这个想法。现在，这是一个神烂摊子。

735
00:40:56,000 --> 00:40:59,000
说实话，没有人会永远记住这个语法，幸运的是，

736
00:40:59,000 --> 00:41:04,000
它实际上是有点故意的，哦，你没有实际看到我写的是什么。

737
00:41:04,000 --> 00:41:08,000
如果可以的话，这将是更具吸引力的。瞧！

738
00:41:08,000 --> 00:41:10,000
>> 在幕后，我解决这样的问题。

739
00:41:10,000 --> 00:41:14,000
阿妮塔，采取这一步骤的左侧，

740
00:41:14,000 --> 00:41:18,000
首先，我们去的地址，Anita是指向

741
00:41:18,000 --> 00:41:23,000
和在那里她会发现不只有N，我们只是检查比较的缘故，

742
00:41:23,000 --> 00:41:25,000
但你也将寻找下一个 - 在这种情况下，

743
00:41:25,000 --> 00:41:28,000
拉曼左手指着在列表中的下一个节点。

744
00:41:28,000 --> 00:41:32,000
但是，这是我前面提到的神的烂摊子，

745
00:41:32,000 --> 00:41:34,000
但事实证明，输出C让我们简化了这一点。

746
00:41:34,000 --> 00:41:40,000
而不是写（梅艳芳），我们可以改为只写梅艳芳 - > N，

747
00:41:40,000 --> 00:41:45,000
和它的功能完全一样的东西，但它是一个更直观的，

748
00:41:45,000 --> 00:41:48,000
这是一个很大的图片更符合我们一直画

749
00:41:48,000 --> 00:41:50,000
这一切的时候使用箭头。

750
00:41:50,000 --> 00:41:57,000
>> 最后，在课程结束后，我们需要做的吗？

751
00:41:57,000 --> 00:42:00,000
还有一个剩余的代码行。

752
00:42:00,000 --> 00:42:02,000
回报是什么？

753
00:42:02,000 --> 00:42:05,000
假的，因为如果我们通过整个循环

754
00:42:05,000 --> 00:42:10,000
Anita是，事实上，空，这意味着她千里迢迢到列表末尾

755
00:42:10,000 --> 00:42:12,000
她指着你叫什么名字呢？

756
00:42:12,000 --> 00:42:15,000
阿里。>>阿里的左手，这是空的。

757
00:42:15,000 --> 00:42:18,000
现在，Anita是空的，我意识到你只是站在这里，笨拙的地狱

758
00:42:18,000 --> 00:42:21,000
因为我要去独白，

759
00:42:21,000 --> 00:42:23,000
但我们会涉及到你在短短的时刻。

760
00:42:23,000 --> 00:42:27,000
Anita是空的故事，在这一点上，因此while循环结束，

761
00:42:27,000 --> 00:42:30,000
我们必须返回false，因为如果她得到了Ari的空指针的方式来

762
00:42:30,000 --> 00:42:34,000
再有就是没有，她试图在列表中的号码。

763
00:42:34,000 --> 00:42:39,000
我们可以清洁过，但是这是一个很好的实现，那么

764
00:42:39,000 --> 00:42:43,000
遍历函数，一个链接列表的功能。

765
00:42:43,000 --> 00:42:48,000
它仍然是线性搜索，但它不是简单+ +指针

766
00:42:48,000 --> 00:42:52,000
+ +变量i，因为现在我们不能猜

767
00:42:52,000 --> 00:42:54,000
这些节点，其中每个都在存储器中。

768
00:42:54,000 --> 00:42:57,000
我们有字面上跟随面包屑的踪迹，或者更具体地说，

769
00:42:57,000 --> 00:43:00,000
指针，从一个节点到另一个。

770
00:43:00,000 --> 00:43:02,000
>> 现在，让我们尝试另一种。安妮塔，你要回来吗？

771
00:43:02,000 --> 00:43:06,000
我们为什么不继续分配从观众的另外一个人吗？

772
00:43:06,000 --> 00:43:08,000
malloc的，你叫什么名字？“丽贝卡。

773
00:43:08,000 --> 00:43:10,000
丽贝卡。 Rebecca一直malloced，从观众，

774
00:43:10,000 --> 00:43:13,000
她现在存储55号。

775
00:43:13,000 --> 00:43:17,000
现在在手的目标是梅艳芳插入

776
00:43:17,000 --> 00:43:22,000
丽贝卡到链表，在合适的地方。

777
00:43:22,000 --> 00:43:24,000
到这儿来了一会儿。

778
00:43:24,000 --> 00:43:28,000
我已经做了这样的事情。

779
00:43:28,000 --> 00:43:32,000
我已经做了节点*。你叫什么名字呢？

780
00:43:32,000 --> 00:43:34,000
瑞贝卡，瑞贝卡。>>还好。

781
00:43:34,000 --> 00:43:41,000
丽贝卡得到的malloc（如sizeof（节点））。

782
00:43:41,000 --> 00:43:44,000
就像我们在过去的分配学生和诸如此类的事情，比如，

783
00:43:44,000 --> 00:43:46,000
我们需要的大小的节点，所以现在瑞贝卡

784
00:43:46,000 --> 00:43:49,000
是指什么？

785
00:43:49,000 --> 00:43:52,000
丽贝卡她的内部具有两个字段，其中之一是55。

786
00:43:52,000 --> 00:43:55,000
让我们做什么，丽贝卡 - > = 55。

787
00:43:55,000 --> 00:44:00,000
但后来丽贝卡 - >未来应像现在，她的手是怎么样的，谁知道？

788
00:44:00,000 --> 00:44:03,000
它指向一些垃圾的价值，那么，为什么不为好措施

789
00:44:03,000 --> 00:44:07,000
我们至少要做到这一点，使左手在她的身边。

790
00:44:07,000 --> 00:44:09,000
现在，梅艳芳，把它从这里开始。

791
00:44:09,000 --> 00:44:11,000
你有瑞贝卡已被分配。

792
00:44:11,000 --> 00:44:20,000
继续前进，发现我们应该把丽贝卡。

793
00:44:20,000 --> 00:44:25,000
好，非常好。

794
00:44:25,000 --> 00:44:28,000
好了，好了，现在我们需要你提供一点方向，

795
00:44:28,000 --> 00:44:30,000
所以你已经达到了阿里。

796
00:44:30,000 --> 00:44:33,000
他的左手是空的，但丽贝卡显然属于正确的，

797
00:44:33,000 --> 00:44:36,000
让我们怎么改变这个链表

798
00:44:36,000 --> 00:44:38,000
为了插入到适当的位置丽贝卡？

799
00:44:38,000 --> 00:44:42,000
如果你可以从字面上将根据需要周围人的左手，

800
00:44:42,000 --> 00:44:48,000
我们会解决这个问题的方式。

801
00:44:48,000 --> 00:44:52,000
好，好，同时，丽贝卡的左手在她的身边。

802
00:44:52,000 --> 00:44:54,000
>> 这是太容易了。

803
00:44:54,000 --> 00:44:57,000
让我们尝试分配的 - 我们做得差不多了，20。

804
00:44:57,000 --> 00:44:59,000
好了，就行了。

805
00:44:59,000 --> 00:45:04,000
20已分配的，所以让我去，说在这里再次

806
00:45:04,000 --> 00:45:07,000
我们刚刚做了的节点*萨德。

807
00:45:07,000 --> 00:45:11,000
我们拥有的malloc（如sizeof（节点））。

808
00:45:11,000 --> 00:45:16,000
然后，我们做完全相同的语法，因为我们做了前20，

809
00:45:16,000 --> 00:45:20,000
我会尽下= NULL，现在是Anita的

810
00:45:20,000 --> 00:45:23,000
插入到链表中，如果你能玩，相同的作用。

811
00:45:23,000 --> 00:45:30,000
执行。

812
00:45:30,000 --> 00:45:32,000
好，好。

813
00:45:32,000 --> 00:45:38,000
现在仔细想想，然后再开始移动周围的左手。

814
00:45:38,000 --> 00:45:46,000
您的今天得到了最尴尬的角色。

815
00:45:46,000 --> 00:45:59,000
谁的手应先移走？

816
00:45:59,000 --> 00:46:02,000
好了，等等，我听到一些不。

817
00:46:02,000 --> 00:46:07,000
如果有些人会礼貌地帮助解决一个尴尬的境地。

818
00:46:07,000 --> 00:46:11,000
谁的左手也许应该首先更新吗？是啊。

819
00:46:11,000 --> 00:46:13,000
[学生]萨阿德。

820
00:46:13,000 --> 00:46:15,000
好了，萨阿德的，为什么有关系吗？

821
00:46:15,000 --> 00:46:17,000
[听不见的学生反应]

822
00:46:17,000 --> 00:46:19,000
好，因为如果我们把你叫什么名字？>>马歇尔。

823
00:46:19,000 --> 00:46:22,000
马歇尔，如果我们先动了手，空，

824
00:46:22,000 --> 00:46:25,000
现在，我们已经从字面上孤立在此列表中的四个人

825
00:46:25,000 --> 00:46:29,000
因为他是唯一指向拉蒙和每个人的左，

826
00:46:29,000 --> 00:46:31,000
所以更新该指针是坏的。

827
00:46:31,000 --> 00:46:33,000
我们的撤消。

828
00:46:33,000 --> 00:46:37,000
好，现在继续前进，将适当的左手指向拉蒙。

829
00:46:37,000 --> 00:46:39,000
这感觉有点多余。

830
00:46:39,000 --> 00:46:41,000
现在有两个人指着拉蒙，但

831
00:46:41,000 --> 00:46:43,000
因为现在我们怎么更新列表？

832
00:46:43,000 --> 00:46:48,000
另一方面，移动吗？

833
00:46:48,000 --> 00:46:53,000
好极了，现在我们失去了任何记忆了吗？

834
00:46:53,000 --> 00:46:57,000
没有那么好，让我们来看看，如果我们不能打破这一次。

835
00:46:57,000 --> 00:47:00,000
>> Mallocing最后一次，5号。

836
00:47:00,000 --> 00:47:04,000
在后面，一路下来吧。

837
00:47:04,000 --> 00:47:08,000
这是非常令人兴奋的。

838
00:47:08,000 --> 00:47:15,000
[掌声]

839
00:47:15,000 --> 00:47:17,000
你叫什么名字？“罗恩。

840
00:47:17,000 --> 00:47:19,000
罗恩，好吧，你是malloced 5号。

841
00:47:19,000 --> 00:47:23,000
我们刚刚执行的代码几乎相同，这些

842
00:47:23,000 --> 00:47:26,000
只用一个不同的名字。

843
00:47:26,000 --> 00:47:28,000
优秀。

844
00:47:28,000 --> 00:47:38,000
现在，梅艳芳，运气好的话插入到列表中的5号。

845
00:47:38,000 --> 00:47:43,000
好，？

846
00:47:43,000 --> 00:47:47,000
好极了，所以这是真正的三个案件总数的三分之一。

847
00:47:47,000 --> 00:47:49,000
我们第一次有人结束时，丽贝卡。

848
00:47:49,000 --> 00:47:51,000
然后，我们在中间的人。

849
00:47:51,000 --> 00:47:53,000
现在我们在开始时，并且在该示例中，已经有人

850
00:47:53,000 --> 00:47:56,000
我们现在有更新卢卡斯的第一次

851
00:47:56,000 --> 00:48:00,000
因为现在在列表中的第一个元素指向一个新的节点，

852
00:48:00,000 --> 00:48:03,000
谁，依次指向在节点号9。

853
00:48:03,000 --> 00:48:06,000
>> 这是一个巨大的尴尬的示范，我敢肯定，

854
00:48:06,000 --> 00:48:08,000
所以这些家伙又大又圆的掌声，如果你能。

855
00:48:08,000 --> 00:48:11,000
很好地完成。

856
00:48:11,000 --> 00:48:17,000
这就是全部。作为一个小的内存，您可以保留您的纸片。

857
00:48:17,000 --> 00:48:22,000
事实证明，这样做的代码

858
00:48:22,000 --> 00:48:26,000
是不是很简单，只是动动手左右

859
00:48:26,000 --> 00:48:28,000
和指向指针的不同的东西。

860
00:48:28,000 --> 00:48:31,000
但意识到，当它来的时候实现的东西，如

861
00:48:31,000 --> 00:48:34,000
一个链表或它的一个变种，如果你专注于真正

862
00:48:34,000 --> 00:48:38,000
这些基本因素，一口大小的问题，我必须弄清楚，

863
00:48:38,000 --> 00:48:43,000
是这只手，这手，否则，什么是一个相当复杂的程序

864
00:48:43,000 --> 00:48:47,000
可以，其实这样相当简单的积木。

865
00:48:47,000 --> 00:48:51,000
>> 让我们把事情仍然在一个更复杂的方向。

866
00:48:51,000 --> 00:48:53,000
我们现在有链表的概念。

867
00:48:53,000 --> 00:48:57,000
我们也有感谢的建议有一个双向链表，

868
00:48:57,000 --> 00:49:01,000
这看起来几乎是一样的，但现在我们有两个内部指针的结构

869
00:49:01,000 --> 00:49:05,000
，而不是一个，我们也许可以调用这些指针的前面和后面的

870
00:49:05,000 --> 00:49:08,000
或左或右，但我们做的，其实，需要其中的两个。

871
00:49:08,000 --> 00:49:10,000
代码将是更复杂一点。

872
00:49:10,000 --> 00:49:12,000
梅艳芳将不得不做更多的工作在这里的舞台上。

873
00:49:12,000 --> 00:49:15,000
但是，我们可以肯定实现该种结构。

874
00:49:15,000 --> 00:49:19,000
但是，在运行时间方面，将运行时间

875
00:49:19,000 --> 00:49:24,000
梅艳芳一个链表中找到一个数n？

876
00:49:24,000 --> 00:49:27,000
还是大O n的，所以它是没有更好的线性搜索。

877
00:49:27,000 --> 00:49:29,000
不过，我们不能做二进制搜索。

878
00:49:29,000 --> 00:49:34,000
为什么会这样呢？你不能跳来跳去。

879
00:49:34,000 --> 00:49:36,000
尽管我们很明显的看到在舞台上的所有人类，

880
00:49:36,000 --> 00:49:39,000
和Anita目测它说，“这里是中间的列表中。”

881
00:49:39,000 --> 00:49:42,000
她不知道，如果她的计算机程序

882
00:49:42,000 --> 00:49:47,000
因为她唯一锁存到的情况下开始

883
00:49:47,000 --> 00:49:50,000
卢卡斯，谁是第一个指针。

884
00:49:50,000 --> 00:49:53,000
她一定要遵循这些链接，

885
00:49:53,000 --> 00:49:56,000
数她，直到她找到大致的中间，

886
00:49:56,000 --> 00:49:58,000
即使如此，她不知道，当她到达中间

887
00:49:58,000 --> 00:50:01,000
除非她去所有的方式结束弄清楚有多少，

888
00:50:01,000 --> 00:50:05,000
然后回溯，而且也将是很难的，除非你有

889
00:50:05,000 --> 00:50:07,000
某种形式的双向链表。

890
00:50:07,000 --> 00:50:10,000
>> 解决一些问题，但介绍他人。

891
00:50:10,000 --> 00:50:12,000
约一个完全不同的数据结构呢？

892
00:50:12,000 --> 00:50:15,000
这是一个照片的托盘Mather中楼，

893
00:50:15,000 --> 00:50:19,000
在这种情况下，我们有一个数据结构，我们也种已经在谈论。

894
00:50:19,000 --> 00:50:22,000
我们谈论中的堆栈内存的情况下，

895
00:50:22,000 --> 00:50:26,000
而这样的刻意命名，是因为堆栈在内存方面

896
00:50:26,000 --> 00:50:31,000
实际上是一个数据结构，有越来越多的东西，在它的上面分层。

897
00:50:31,000 --> 00:50:35,000
但有趣的事情堆栈，因为在现实的情况下，

898
00:50:35,000 --> 00:50:38,000
是，它是一种特殊的数据结构。

899
00:50:38,000 --> 00:50:42,000
它是一个数据结构，从而使第一元件

900
00:50:42,000 --> 00:50:46,000
是的最后一个元素。

901
00:50:46,000 --> 00:50:50,000
如果你是第一个托盘入堆栈，

902
00:50:50,000 --> 00:50:53,000
你要不幸的是，最后一个托盘从堆栈中，

903
00:50:53,000 --> 00:50:55,000
而这并不一定是件好事。

904
00:50:55,000 --> 00:50:58,000
相反，你可以考虑一下周围的其他方法，

905
00:50:58,000 --> 00:51:02,000
最后是第一个出来的。

906
00:51:02,000 --> 00:51:05,000
>> 现在，你的任何方案，浮现在脑海中有一个堆栈

907
00:51:05,000 --> 00:51:08,000
数据结构，具有该属性

908
00:51:08,000 --> 00:51:13,000
中的最后一个，第一个出来的，实际上是吸引力？

909
00:51:13,000 --> 00:51:16,000
这是一件好事吗？这是一件坏事吗？

910
00:51:16,000 --> 00:51:19,000
这绝对是一件坏事，如果托盘不尽相同

911
00:51:19,000 --> 00:51:21,000
他们都是不同的颜色或诸如此类的东西，

912
00:51:21,000 --> 00:51:24,000
你想要的颜色是所有的方式在底部。

913
00:51:24,000 --> 00:51:26,000
当然，你不能，不花大力气。

914
00:51:26,000 --> 00:51:28,000
你必须从顶部开始，一路下滑。

915
00:51:28,000 --> 00:51:31,000
同样，如果你是其中之一，这些风扇男孩

916
00:51:31,000 --> 00:51:34,000
试图让iPhone和排队等待了一夜的人

917
00:51:34,000 --> 00:51:36,000
在这样的地方吗？

918
00:51:36,000 --> 00:51:40,000
那岂不是很好，如果苹果专卖店

919
00:51:40,000 --> 00:51:42,000
一个堆栈的数据结构吗？

920
00:51:42,000 --> 00:51:44,000
耶？不仅如此吗？

921
00:51:44,000 --> 00:51:47,000
这只是良好的人显示在最后一分钟

922
00:51:47,000 --> 00:51:50,000
，然后被拔了队列。

923
00:51:50,000 --> 00:51:52,000
而事实上，这样的倾向的事实，我说队列

924
00:51:52,000 --> 00:51:56,000
实际上是一致的，我们所说的这种数据结构，

925
00:51:56,000 --> 00:51:59,000
在现实中的顺序很重要，

926
00:51:59,000 --> 00:52:02,000
你想中的第一个，是第一个

927
00:52:02,000 --> 00:52:04,000
如果仅仅是为了人类的公平。

928
00:52:04,000 --> 00:52:07,000
一般情况下，我们将调用一个队列的数据结构。

929
00:52:07,000 --> 00:52:11,000
>> 事实证明，除了链表，我们就可以开始使用这些相同的基本思路

930
00:52:11,000 --> 00:52:15,000
开始创建新的，不同类型的解决方案的问题。

931
00:52:15,000 --> 00:52:19,000
例如，在堆栈的箱子中，我们可以表示一个堆栈

932
00:52:19,000 --> 00:52:22,000
使用的数据结构是这样的，我会提出。

933
00:52:22,000 --> 00:52:26,000
在这种情况下，我宣布一个结构，我已经说过了这种结构的内部

934
00:52:26,000 --> 00:52:30,000
是一个数字数组变量的大小，

935
00:52:30,000 --> 00:52:33,000
我会打电话给这件事情一个堆栈。

936
00:52:33,000 --> 00:52:35,000
现在，为什么会发生这种实际工作？

937
00:52:35,000 --> 00:52:43,000
在堆栈的情况下，我可以得出这样有效地在屏幕上为一个数组。

938
00:52:43,000 --> 00:52:47,000
这里是我的筹码。这是我的号码。

939
00:52:47,000 --> 00:52:50,000
我们将吸引他们，因为这，这，这，这，这。

940
00:52:50,000 --> 00:52:53,000
然后，我这里有一些其他的数据成员，

941
00:52:53,000 --> 00:52:58,000
被称为大小，所以这是大小，这是数字，

942
00:52:58,000 --> 00:53:02,000
集体，在这里代表整个iPad的一个堆栈结构。

943
00:53:02,000 --> 00:53:07,000
现在，默认情况下，大小大概已经有被初始化为0，

944
00:53:07,000 --> 00:53:11,000
里面有什么数字阵列最初

945
00:53:11,000 --> 00:53:14,000
当我第一次分配的数组？

946
00:53:14,000 --> 00:53:16,000
垃圾。谁知道？它实际上并不重要。

947
00:53:16,000 --> 00:53:20,000
它并不重要，如果这是1，2，3，4，5，完全随机

948
00:53:20,000 --> 00:53:25,000
我的结构中存储的运气不好，因为只要我知道的堆栈大小

949
00:53:25,000 --> 00:53:29,000
为0，则我知道编程方式，不看任何数组中的元素。

950
00:53:29,000 --> 00:53:31,000
不要紧，那里有什么。

951
00:53:31,000 --> 00:53:34,000
不要看他们，将一个大小为0的含义。

952
00:53:34,000 --> 00:53:38,000
>> 但是，假设现在我先走，然后插入到堆栈中的东西。

953
00:53:38,000 --> 00:53:42,000
我想插入数字5，所以我把这里的5号，

954
00:53:42,000 --> 00:53:45,000
，然后我放下吗？

955
00:53:45,000 --> 00:53:48,000
现在我想放下的大小，

956
00:53:48,000 --> 00:53:50,000
现在的堆栈大小为1。

957
00:53:50,000 --> 00:53:53,000
如果我继续前进，插入数字，让我们说，7下吗？

958
00:53:53,000 --> 00:53:57,000
，然后被更新为2，然后我们会做9，

959
00:53:57,000 --> 00:54:02,000
然后这被更新为3。

960
00:54:02,000 --> 00:54:05,000
但有趣的功能，现在该堆栈的是，

961
00:54:05,000 --> 00:54:09,000
如果我想弹出，我应该删除哪一个元素

962
00:54:09,000 --> 00:54:12,000
的堆栈的东西，可以这么说吗？

963
00:54:12,000 --> 00:54:14,000
9将是去的第一件事情。

964
00:54:14,000 --> 00:54:18,000
应该如何改变图片，如果我想从栈中弹出一个元素，

965
00:54:18,000 --> 00:54:20,000
很像一个托盘Mather中？

966
00:54:20,000 --> 00:54:22,000
是的。>> [学生]：设置大小为2。

967
00:54:22,000 --> 00:54:27,000
没错，我做的是设置大小为2，和与阵列我该怎么办？

968
00:54:27,000 --> 00:54:29,000
我没有做任何事情。

969
00:54:29,000 --> 00:54:32,000
我可以，只是肛门，把一个0或-1的东西来表示

970
00:54:32,000 --> 00:54:34,000
这是不是一个合法的值，但它并不重要，因为

971
00:54:34,000 --> 00:54:37,000
我可以记录以外的数组本身它有多长

972
00:54:37,000 --> 00:54:41,000
所以，我知道，只有在此数组中的前两个元素。

973
00:54:41,000 --> 00:54:47,000
现在，如果我去了，8号添加到这个数组中，如何改变图片吗？

974
00:54:47,000 --> 00:54:50,000
这将成为8，而且这变成3。

975
00:54:50,000 --> 00:54:52,000
我在这里省几个小钱。

976
00:54:52,000 --> 00:54:56,000
现在，我们有5个，7，8，和我们回来了大小为3。

977
00:54:56,000 --> 00:54:58,000
这是非常简单的实现，

978
00:54:58,000 --> 00:55:06,000
但我们什么时候这样的设计决策感到后悔吗？

979
00:55:06,000 --> 00:55:09,000
什么时候的事情开始去非常，非常错误吗？是啊。

980
00:55:09,000 --> 00:55:11,000
[听不见的学生反应]

981
00:55:11,000 --> 00:55:13,000
当你想回去拿你的第一个元素进去，

982
00:55:13,000 --> 00:55:18,000
>> 原来，在这里即使堆栈引擎盖下的是一个数组，

983
00:55:18,000 --> 00:55:21,000
这些数据结构，我们已经开始谈论一般也被称为

984
00:55:21,000 --> 00:55:25,000
抽象的数据结构，他们是如何实现的

985
00:55:25,000 --> 00:55:27,000
完全是除了点。

986
00:55:27,000 --> 00:55:31,000
就像一个堆栈的数据结构应该是添加支持

987
00:55:31,000 --> 00:55:35,000
操作上推，一个托盘推入堆栈，

988
00:55:35,000 --> 00:55:39,000
和流行音乐，从堆栈中删除一个元素，那就是它。

989
00:55:39,000 --> 00:55:43,000
如果你是下载别人的代码已经实施

990
00:55:43,000 --> 00:55:46,000
这个东西叫做堆栈，这个人会写

991
00:55:46,000 --> 00:55:49,000
只有两个函数，你push和pop，在生活中，其唯一目的

992
00:55:49,000 --> 00:55:51,000
将这样做。

993
00:55:51,000 --> 00:55:54,000
你或他或她是谁实施该计划

994
00:55:54,000 --> 00:55:58,000
本来完全是一个决定如何实现

995
00:55:58,000 --> 00:56:00,000
引擎盖下方的压入和弹出的语义

996
00:56:00,000 --> 00:56:03,000
入栈和出栈的功能。

997
00:56:03,000 --> 00:56:07,000
我已经在这里做了一个有点短视的决定

998
00:56:07,000 --> 00:56:10,000
通过实施这个简单的数据结构，为什么我的筹码呢？

999
00:56:10,000 --> 00:56:12,000
当这个数据结构的突破？

1000
00:56:12,000 --> 00:56:18,000
在什么情况下我必须返回一个错误，当用户调用push，例如？

1001
00:56:18,000 --> 00:56:20,000
[学生]：如果没有更多的空间。

1002
00:56:20,000 --> 00:56:23,000
没错，如果没有更多的空间，如果我超过容量，

1003
00:56:23,000 --> 00:56:27,000
这是全部大写的，因为它表明它是某种全局常量。

1004
00:56:27,000 --> 00:56:30,000
好吧，那么我只是将不得不说，“对不起，我不能把另一个值

1005
00:56:30,000 --> 00:56:32,000
到堆栈上，“就像在奥美。

1006
00:56:32,000 --> 00:56:36,000
>> 在某些时候，他们会打那个小柜的顶部。

1007
00:56:36,000 --> 00:56:39,000
在堆栈中没有更多的空间或能力，在这一点有某种错误。

1008
00:56:39,000 --> 00:56:42,000
他们必须把元素的其他地方，其他地方的盘，

1009
00:56:42,000 --> 00:56:44,000
或无处。

1010
00:56:44,000 --> 00:56:47,000
现在，我们的队列，可以实现略有不同。

1011
00:56:47,000 --> 00:56:50,000
队列是有一点不同，引擎盖下的，它可以实现

1012
00:56:50,000 --> 00:56:54,000
作为一个数组，但为什么，在这种情况下，我建议

1013
00:56:54,000 --> 00:56:59,000
也有一个头元素的列表头，

1014
00:56:59,000 --> 00:57:06,000
前面的列表，线的第一人，在苹果商店，除了大小？

1015
00:57:06,000 --> 00:57:14,000
为什么我需要一个额外的数据吗？

1016
00:57:14,000 --> 00:57:16,000
回想一下号码是什么

1017
00:57:16,000 --> 00:57:18,000
如果我画如下。

1018
00:57:18,000 --> 00:57:21,000
现在假设这是一个队列，而不是一个栈，

1019
00:57:21,000 --> 00:57:24,000
是一样的苹果专卖店排队的差异是公平的。

1020
00:57:24,000 --> 00:57:27,000
在列表中的开始，在这种情况下，5号线中的第一个人

1021
00:57:27,000 --> 00:57:30,000
他或她将要被让进店的第一。

1022
00:57:30,000 --> 00:57:32,000
让我们做到这一点。

1023
00:57:32,000 --> 00:57:35,000
假设，这是我的队列的状态，在这一刻的时候，和现在的苹果专卖店

1024
00:57:35,000 --> 00:57:39,000
打开的第一人，5号，是导致进店。

1025
00:57:39,000 --> 00:57:43,000
如何更改我的图片，我去排队第一人

1026
00:57:43,000 --> 00:57:47,000
在前面的行？

1027
00:57:47,000 --> 00:57:50,000
那是什么？>> [学生]：更改队列。

1028
00:57:50,000 --> 00:57:52,000
改变头，所以就消失了。

1029
00:57:52,000 --> 00:57:56,000
在现实中，它仿佛如何做到这一点？

1030
00:57:56,000 --> 00:58:00,000
在现实中，虽然这家伙消失。

1031
00:58:00,000 --> 00:58:03,000
7号做什么实际的店吗？

1032
00:58:03,000 --> 00:58:05,000
他们将向前迈出一大步。

1033
00:58:05,000 --> 00:58:08,000
>> 但我们体会到，当涉及到阵列

1034
00:58:08,000 --> 00:58:10,000
移动周围的事物吗？

1035
00:58:10,000 --> 00:58:12,000
这是一种浪费你的时间了，对不对？

1036
00:58:12,000 --> 00:58:16,000
为什么你要那么肛门有第一人

1037
00:58:16,000 --> 00:58:21,000
行开始的，在物理上的内存块的开始？

1038
00:58:21,000 --> 00:58:23,000
这是完全不必要的。为什么呢？

1039
00:58:23,000 --> 00:58:26,000
我只记得什么呢？>> [听不见的学生反应]

1040
00:58:26,000 --> 00:58:30,000
没错，我只记得这个额外的数据成员头

1041
00:58:30,000 --> 00:58:34,000
现在的列表头的不再是0，它是刚才。

1042
00:58:34,000 --> 00:58:39,000
现在，它实际上是数字1。就这样，我得到了轻微的优化。

1043
00:58:39,000 --> 00:58:44,000
只是因为我去排队的人从行的行开始在苹果专卖店

1044
00:58:44,000 --> 00:58:47,000
但这并不意味着每个人都有转移，召回是线性的操作。

1045
00:58:47,000 --> 00:58:50,000
相反，我可以只花费固定的时间

1046
00:58:50,000 --> 00:58:53,000
然后实现更快的响应。

1047
00:58:53,000 --> 00:58:56,000
但我付出的价格是获得额外的性能

1048
00:58:56,000 --> 00:58:58,000
而不是转移大家的吗？

1049
00:58:58,000 --> 00:59:01,000
是啊。>> [听不见的学生反应]

1050
00:59:01,000 --> 00:59:04,000
可以添加更多的人，好了，这个问题是正交

1051
00:59:04,000 --> 00:59:07,000
的事实，我们周围的人不转移。

1052
00:59:07,000 --> 00:59:11,000
它仍然是一个数组，所以我们是否转移大家或不

1053
00:59:11,000 --> 00:59:13,000
哦，我明白你的意思，好吧。

1054
00:59:13,000 --> 00:59:16,000
其实，我同意你在说什么的，因为它几乎就像

1055
00:59:16,000 --> 00:59:19,000
现在，我们永远不会使用这个数组开始了

1056
00:59:19,000 --> 00:59:22,000
因为，如果我删除，然后删除7。

1057
00:59:22,000 --> 00:59:24,000
但我只把人民的权利。

1058
00:59:24,000 --> 00:59:28,000
>> 我感觉就像是在浪费空间，最后，我的队列分解成什么都没有，

1059
00:59:28,000 --> 00:59:31,000
因此，我们可能只是人们概括的，

1060
00:59:31,000 --> 00:59:35,000
我们可以认为这个数组真的为某种圆形结构，

1061
00:59:35,000 --> 00:59:38,000
但我们用C做什么运营商在那种环绕吗？

1062
00:59:38,000 --> 00:59:40,000
[听不见的学生回应] >>模运算符。

1063
00:59:40,000 --> 00:59:43,000
这将是一个有点恼人认为，你是怎么做到的环绕，

1064
00:59:43,000 --> 00:59:46,000
，但我们可以做到这一点，我们就可以开始把人民的利益，在曾经被认为是该行的前面，

1065
00:59:46,000 --> 00:59:52,000
但我们只记得谁是实际的行头其实是与这头变量。

1066
00:59:52,000 --> 00:59:57,000
什么，如果不是，最终，我们的目标是，

1067
00:59:57,000 --> 01:00:00,000
看数字，我们在这里所做过的舞台上与梅艳芳，

1068
01:00:00,000 --> 01:00:02,000
但我们希望所有这些世界最好的吗？

1069
01:00:02,000 --> 01:00:05,000
我们希望有更多的复杂性比数组

1070
01:00:05,000 --> 01:00:09,000
因为我们希望能够动态增长的数据结构。

1071
01:00:09,000 --> 01:00:12,000
但是，我们不希望拥有的东西，我们指出

1072
01:00:12,000 --> 01:00:15,000
在第一堂课是不是一个最佳的算法，

1073
01:00:15,000 --> 01:00:17,000
线性搜索。

1074
01:00:17,000 --> 01:00:21,000
事实证明，就可以了，事实上，实现

1075
01:00:21,000 --> 01:00:24,000
或至少​​接近恒定的时间，有人喜欢梅艳芳，

1076
01:00:24,000 --> 01:00:27,000
她的数据结构配置，如果她是一个链表，

1077
01:00:27,000 --> 01:00:30,000
不是一个堆栈，而不是一个队列中，可以，在事实上，

1078
01:00:30,000 --> 01:00:33,000
拿出一个数据结构，允许她看的东西，

1079
01:00:33,000 --> 01:00:37,000
什字，不只是数字，我们会打电话给固定的时间。

1080
01:00:37,000 --> 01:00:40,000
>> 而事实上，展望未来，在这个类中的一个pset时几乎总是

1081
01:00:40,000 --> 01:00:43,000
一个拼写检查的实施，据此，

1082
01:00:43,000 --> 01:00:46,000
我们给你再次约15万英文单词，我们的目标是

1083
01:00:46,000 --> 01:00:51,000
加载到内存中，并迅速成为能够回答问题的形式

1084
01:00:51,000 --> 01:00:54,000
这个词是拼写是否正确？

1085
01:00:54,000 --> 01:00:58,000
那真是糟透了，如果你不得不遍历所有15万字来回答这个问题。

1086
01:00:58,000 --> 01:01:02,000
但是，事实上，我们会看到，我们可以在非常非常快的时间内做到这一点。

1087
01:01:02,000 --> 01:01:06,000
这将涉及执行一些所谓的哈希表，

1088
01:01:06,000 --> 01:01:09,000
即使乍看之下这件事情被称为哈希表是怎么回事

1089
01:01:09,000 --> 01:01:12,000
让我们实现这些超快速的响应时间，

1090
01:01:12,000 --> 01:01:18,000
事实证明，其实也有一个问题。

1091
01:01:18,000 --> 01:01:23,000
当谈到时间来执行这件事情，再次，我老毛病又犯了。

1092
01:01:23,000 --> 01:01:25,000
我是唯一一个在这里。

1093
01:01:25,000 --> 01:01:28,000
当谈到时间落实这件事情被称为哈希表，

1094
01:01:28,000 --> 01:01:30,000
我们将不得不做出决定。

1095
01:01:30,000 --> 01:01:32,000
这件事情应该多大究竟是什么？

1096
01:01:32,000 --> 01:01:36,000
当我们开始这个哈希表中插入数字，

1097
01:01:36,000 --> 01:01:38,000
我们如何将它们存储在这样一种方式

1098
01:01:38,000 --> 01:01:42,000
，我们可以得到他们回来了，很快我们得到了他们？

1099
01:01:42,000 --> 01:01:45,000
但是，我们会看到不久这个问题的

1100
01:01:45,000 --> 01:01:48,000
当每个人的生日是在课堂上是相当有密切关系。

1101
01:01:48,000 --> 01:01:51,000
事实证明，在这个房间里，我们已经有了几百人，

1102
01:01:51,000 --> 01:01:56,000
这样的可能性，我们两个人有相同的生日可能是相当高的。

1103
01:01:56,000 --> 01:01:58,000
如果只有40，我们在这个房间里吗？

1104
01:01:58,000 --> 01:02:02,000
什么是赔率的两个人具有相同的生日吗？

1105
01:02:02,000 --> 01:02:04,000
[学生]超过50％。

1106
01:02:04,000 --> 01:02:06,000
是啊，超过50％。事实上，我什至带来了一个图表。

1107
01:02:06,000 --> 01:02:08,000
事实证明，这是真的只是一个预演

1108
01:02:08,000 --> 01:02:12,000
如果只有58我们在这个房间里，我们的概率为2

1109
01:02:12,000 --> 01:02:16,000
具有相同的生日是巨大的，几乎100％，

1110
01:02:16,000 --> 01:02:20,000
而这会为我们造成的伤害一大堆周三。

1111
01:02:20,000 --> 01:02:24,000
>> 随着中说，让我们休会这里。上周三，我们会看到你。

1112
01:02:24,000 --> 01:02:28,000
[掌声]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]