1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> 扬声器1：对，所以我们又回来了。

3
00:00:13,120 --> 00:00:14,480
欢迎CS50。

4
00:00:14,480 --> 00:00:16,510
是星期七月底。

5
00:00:16,510 --> 00:00:20,200
所以记得，最后一次，我们开始
稍微复杂的看

6
00:00:20,200 --> 00:00:21,100
的数据结构。

7
00:00:21,100 --> 00:00:25,110
由于到现在为止，我们真的
在我们的处置是这样的，一个数组。

8
00:00:25,110 --> 00:00:29,340
>> 但在此之前我们不会丢弃数组
所有有趣的，这的确

9
00:00:29,340 --> 00:00:33,570
实际上，是一些什么
加上这个简单的数据

10
00:00:33,570 --> 00:00:34,560
结构，从而有多远？

11
00:00:34,560 --> 00:00:36,110
什么是它擅长的？

12
00:00:36,110 --> 00:00:39,450
到目前为止，我们已经看到？

13
00:00:39,450 --> 00:00:42,540
你得到了什么？

14
00:00:42,540 --> 00:00:44,028
什么也没有。

15
00:00:44,028 --> 00:00:45,020
>> 学生：[听不清]。

16
00:00:45,020 --> 00:00:45,395
>> 扬声器1：那是什么？

17
00:00:45,395 --> 00:00:46,410
>> 学生：[听不清]。

18
00:00:46,410 --> 00:00:47,000
>> 扬声器1：固定尺寸。

19
00:00:47,000 --> 00:00:51,260
OK，那么，为什么是固定大小的好，虽然？

20
00:00:51,260 --> 00:00:53,180
>> 学生：[听不清]。

21
00:00:53,180 --> 00:00:56,240
>> 扬声器1：确定的，所以它的效率
这个意义上，你可以分配一个

22
00:00:56,240 --> 00:01:00,070
固定大小的空间，希望
恰恰是尽可能多

23
00:01:00,070 --> 00:01:01,180
空间，只要你想。

24
00:01:01,180 --> 00:01:02,720
所以这可能是一个绝对加分。

25
00:01:02,720 --> 00:01:06,530
>> 一个数组的另一侧什么？

26
00:01:06,530 --> 00:01:07,610
是吗？

27
00:01:07,610 --> 00:01:08,750
>> 学生：[听不清]。

28
00:01:08,750 --> 00:01:09,550
>> 扬声器1：所有的 - 对不起？

29
00:01:09,550 --> 00:01:11,270
>> 学生：[听不清]。

30
00:01:11,270 --> 00:01:13,620
>> 扬声器1：在内存中的所有箱子
或给对方。

31
00:01:13,620 --> 00:01:15,220
这是有帮助的 - 为什么？

32
00:01:15,220 --> 00:01:15,970
这是相当正确的。

33
00:01:15,970 --> 00:01:18,611
但如何才能利用这一真理吗？

34
00:01:18,611 --> 00:01:21,500
>> 学生：[听不清]。

35
00:01:21,500 --> 00:01:24,490
>> 扬声器1：没错，我们可以跟踪
一切都只是知道

36
00:01:24,490 --> 00:01:28,560
一个地址，即地址
该内存块的第一个字节。

37
00:01:28,560 --> 00:01:30,420
或字符串的情况下，
地址的第一个

38
00:01:30,420 --> 00:01:31,460
在该字符串中的字符。

39
00:01:31,460 --> 00:01:33,330
并从那里，我们可以找到
结束的字符串。

40
00:01:33,330 --> 00:01:35,710
我们可以找到的第二个元素，
第三个元素，依此类推。

41
00:01:35,710 --> 00:01:38,740
>> 等花俏的手法描述，
特点是阵列给我们

42
00:01:38,740 --> 00:01:40,020
随机访问。

43
00:01:40,020 --> 00:01:44,330
只需使用方括号
符号和数字，你可以跳

44
00:01:44,330 --> 00:01:48,070
一个特定的数组中的元素
在固定时间内，大O

45
00:01:48,070 --> 00:01:49,810
之一，可以这么说。

46
00:01:49,810 --> 00:01:51,080
>> 但也有一些缺点。

47
00:01:51,080 --> 00:01:53,110
数组不是很容易做吗？

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
什么不擅长什么？

50
00:01:57,170 --> 00:01:58,810
>> 学生：[听不清]。

51
00:01:58,810 --> 00:01:59,860
>> 扬声器1：那是什么？

52
00:01:59,860 --> 00:02:00,530
>> 学生：[听不清]。

53
00:02:00,530 --> 00:02:01,460
>> 扬声器1：在规模扩大。

54
00:02:01,460 --> 00:02:04,800
所以的缺点数组是
正好相反的是什么

55
00:02:04,800 --> 00:02:05,540
一面是。

56
00:02:05,540 --> 00:02:07,610
所以，一个缺点是
，这是一个固定大小的。

57
00:02:07,610 --> 00:02:09,400
所以你不能真正成长。

58
00:02:09,400 --> 00:02:13,510
您可以重新分配更大的大块
内存中，然后将旧的元素

59
00:02:13,510 --> 00:02:14,460
到新的数组。

60
00:02:14,460 --> 00:02:18,060
然后释放旧的阵列，
例如，通过用malloc或类似的

61
00:02:18,060 --> 00:02:21,180
函数调用realloc的，
重新分配内存。

62
00:02:21,180 --> 00:02:25,490
>> REALLOC，顺便说一句，试图给你
内存阵列旁边

63
00:02:25,490 --> 00:02:26,610
你已经有了。

64
00:02:26,610 --> 00:02:28,740
但它也可能移动的东西
周围完全。

65
00:02:28,740 --> 00:02:30,710
但总之，这是昂贵的，对不对？

66
00:02:30,710 --> 00:02:33,440
因为如果你有一大块的内存
这个长度，但是你真的想要一个

67
00:02:33,440 --> 00:02:36,710
这种规模，你要保留
你有原创要素，

68
00:02:36,710 --> 00:02:40,510
大致的线性时间复制过程
需要发生

69
00:02:40,510 --> 00:02:41,900
新的旧的阵列。

70
00:02:41,900 --> 00:02:44,630
和现实要求的经营
系统一而再，再而

71
00:02:44,630 --> 00:02:48,340
再大的内存块，就可以开始
花费你一些时间。

72
00:02:48,340 --> 00:02:52,250
因此，它既是祝福和诅咒
伪装，但事实上，这些阵列

73
00:02:52,250 --> 00:02:53,860
固定大小。

74
00:02:53,860 --> 00:02:56,790
但是，如果我们引入，而不是东西
这样，我们称为联

75
00:02:56,790 --> 00:03:00,580
列表中，我们得到了一些积极和
几个缺点在这里。

76
00:03:00,580 --> 00:03:05,780
>> 所以一个链表是一个简单的数据
结构由C结构

77
00:03:05,780 --> 00:03:09,850
情况下，当一个struct，召回，只是
用容器的一个或多个特定

78
00:03:09,850 --> 00:03:11,100
类型的变量。

79
00:03:11,100 --> 00:03:16,110
在这种情况下，什么数据类型
似乎是里面的结构，

80
00:03:16,110 --> 00:03:17,600
我们最后一次称为一个节点？

81
00:03:17,600 --> 00:03:19,380
这些矩形中的每一个是一个节点。

82
00:03:19,380 --> 00:03:22,660
并且每个小矩形
里面它是一种数据类型。

83
00:03:22,660 --> 00:03:25,300
什么样的类型，我们说
他们在周一？

84
00:03:25,300 --> 00:03:26,478
是吗？

85
00:03:26,478 --> 00:03:27,870
>> 学生：[听不清]。

86
00:03:27,870 --> 00:03:30,721
>> 扬声器1：变量和指针，或
更具体地说，一个int，对n，

87
00:03:30,721 --> 00:03:32,180
和指针底部。

88
00:03:32,180 --> 00:03:35,360
两个那些碰巧是32位，在
至少在电脑上像这样CS50

89
00:03:35,360 --> 00:03:37,980
电器，所以他们
得出同样的大小。

90
00:03:37,980 --> 00:03:42,260
>> 那么，什么是使用指针
但显然？

91
00:03:42,260 --> 00:03:47,690
为什么现在这个箭头数组时
这么漂亮，干净和简单的？

92
00:03:47,690 --> 00:03:50,460
指针是什么做的
我们在这些节点中的每个节点？

93
00:03:50,460 --> 00:03:52,160
>> 学生：[听不清]。

94
00:03:52,160 --> 00:03:52,465
>> 扬声器1：没错。

95
00:03:52,465 --> 00:03:54,120
它告诉你在哪里
下一个是。

96
00:03:54,120 --> 00:03:57,350
所以我使用的比喻
使用一个线程来排序

97
00:03:57,350 --> 00:03:59,180
线程这些节点连接在一起。

98
00:03:59,180 --> 00:04:01,760
这正是我们正在做的
指针，因为每个这些

99
00:04:01,760 --> 00:04:06,360
内存块可能会或可能不会
连续回背靠背

100
00:04:06,360 --> 00:04:09,500
内部RAM，因为你每次
调用malloc说，给我足够的

101
00:04:09,500 --> 00:04:12,510
字节一个新的节点，它可能
在这里，或者它可能是在这里。

102
00:04:12,510 --> 00:04:13,120
这可能是在这里。

103
00:04:13,120 --> 00:04:13,730
这可能是在这里。

104
00:04:13,730 --> 00:04:14,640
你只是不知道。

105
00:04:14,640 --> 00:04:17,880
>> 但是，使用指针的地址
这些节点，你可以拼接

106
00:04:17,880 --> 00:04:22,370
一起在视觉上看起来的方式
即使这些东西都像一个列表

107
00:04:22,370 --> 00:04:26,770
传遍你的一个或
你的两个或4 GB的RAM

108
00:04:26,770 --> 00:04:28,760
自己的电脑里面。

109
00:04:28,760 --> 00:04:33,230
>> 所以下行，那么，
链表是什么？

110
00:04:33,230 --> 00:04:34,670
什么是我们的价格
显然支付？

111
00:04:34,670 --> 00:04:36,010
>> 学生：[听不清]。

112
00:04:36,010 --> 00:04:36,920
>> 扬声器1：更多的空间，对不对？

113
00:04:36,920 --> 00:04:39,340
在这种情况下，我们已经增加了一倍
空间，因为我们已经走了

114
00:04:39,340 --> 00:04:43,500
从32位的每个节点，每个
INT，所以现在64位的，因为我们有

115
00:04:43,500 --> 00:04:45,050
保持周围的指针。

116
00:04:45,050 --> 00:04:48,860
你得到更多的效率，如果你的结构
是大于这个简单的事情。

117
00:04:48,860 --> 00:04:52,020
如果你确实有一个学生里面
这是一对夫妇的字符串

118
00:04:52,020 --> 00:04:55,430
名称和房子，也许是一个ID号，
也许其他一些领域完全。

119
00:04:55,430 --> 00:04:59,000
>> 所以，如果你有一个足够大的结构，
那么也许成本的指针

120
00:04:59,000 --> 00:05:00,010
没有什么大不了的。

121
00:05:00,010 --> 00:05:03,570
这是一个位在一个角落的情况下
我们存储这样一个简单的原始

122
00:05:03,570 --> 00:05:04,760
内的链接的列表。

123
00:05:04,760 --> 00:05:05,790
但问题是相同的。

124
00:05:05,790 --> 00:05:08,230
你肯定花更多
内存，但你得到

125
00:05:08,230 --> 00:05:08,990
的灵活性。

126
00:05:08,990 --> 00:05:12,280
因为现在如果我想添加一个元素
在此列表的开头，

127
00:05:12,280 --> 00:05:14,340
我必须分配一个新的节点。

128
00:05:14,340 --> 00:05:17,180
我有只更新那些
不知何故只是移动箭头

129
00:05:17,180 --> 00:05:17,980
周围一些指针。

130
00:05:17,980 --> 00:05:20,580
>> 如果我要插入到的东西
中间的列表，我不必

131
00:05:20,580 --> 00:05:24,410
抛开众人推像我们一样
周过去与我们的志愿者

132
00:05:24,410 --> 00:05:25,700
表示一个数组。

133
00:05:25,700 --> 00:05:29,470
我可以只分配一个新的节点，
然后就点中的箭头

134
00:05:29,470 --> 00:05:32,290
不同的方向，因为它不
必须保持以实际的

135
00:05:32,290 --> 00:05:35,670
内存一个真正像我画的线
这里的屏幕上。

136
00:05:35,670 --> 00:05:38,400
>> 最后，如​​果你想插入
在列表末尾的东西，这是

137
00:05:38,400 --> 00:05:39,210
更容易。

138
00:05:39,210 --> 00:05:43,320
这是任意符号，
但34的指针，以此来猜测。

139
00:05:43,320 --> 00:05:46,710
其指针的价值是什么
可能拉有点像一个老

140
00:05:46,710 --> 00:05:47,700
有学校天线？

141
00:05:47,700 --> 00:05:48,920
>> 学生：[听不清]。

142
00:05:48,920 --> 00:05:49,900
>> 扬声器1：这可能是空的。

143
00:05:49,900 --> 00:05:52,710
事实上，这是一个作者的
表示空。

144
00:05:52,710 --> 00:05:56,310
它是空的，因为你绝对
需要知道在哪里结束的联

145
00:05:56,310 --> 00:06:00,050
名单，免得你保持以下
后，并按照这些箭头

146
00:06:00,050 --> 00:06:01,170
一些垃圾值。

147
00:06:01,170 --> 00:06:06,230
因此，空表示没有任何
更多的节点号为34的右侧，

148
00:06:06,230 --> 00:06:07,200
在这种情况下。

149
00:06:07,200 --> 00:06:10,270
>> 因此，我们提出，我们可以实现
这个节点的代码。

150
00:06:10,270 --> 00:06:12,130
我们已经看到这种
之前的语法。

151
00:06:12,130 --> 00:06:15,090
用typedef定义一个新类型
我们，为我们提供了这样的代名词

152
00:06:15,090 --> 00:06:17,100
对于char *字符串。

153
00:06:17,100 --> 00:06:21,030
在这种情况下，它给我们
速记符号，使结构节点

154
00:06:21,030 --> 00:06:24,010
而是可以被写成
节点，它是干净了很多。

155
00:06:24,010 --> 00:06:25,360
这是少了很多冗长。

156
00:06:25,360 --> 00:06:30,080
>> 节点内显然是一个int
称为n和结构节点*

157
00:06:30,080 --> 00:06:34,670
这意味着正是我们想要的
箭头的意思是，到另一个指针

158
00:06:34,670 --> 00:06:36,940
完全相同的数据类型的节点。

159
00:06:36,940 --> 00:06:40,300
我建议，我们可以实现一个
搜索这样的功能，这在

160
00:06:40,300 --> 00:06:41,890
乍一看似乎
有点复杂。

161
00:06:41,890 --> 00:06:43,330
但是，让我们来看看它在上下文中。

162
00:06:43,330 --> 00:06:45,480
>> 让我去到这里的家电。

163
00:06:45,480 --> 00:06:48,460
让我打开一个名为
列表零点H。

164
00:06:48,460 --> 00:06:53,950
只包含的定义，我们
只是刚才也看到了这些数据

165
00:06:53,950 --> 00:06:55,390
类型称为一个节点。

166
00:06:55,390 --> 00:06:57,350
因此，我们已经把到一个点h文件。

167
00:06:57,350 --> 00:07:01,430
>> 而顺便说一句，尽管这
程序，你将要看到的是

168
00:07:01,430 --> 00:07:05,410
不是所有的，复杂的，它的的确确
当编写一个程序来公约

169
00:07:05,410 --> 00:07:10,270
数据类型一样，把东西拉
有时，在里面你的常量

170
00:07:10,270 --> 00:07:13,210
头文件不一定
你的C文件，当然，当你的

171
00:07:13,210 --> 00:07:17,370
方案变得越来越大，从而使
你知道到哪里寻找既为

172
00:07:17,370 --> 00:07:20,840
在某些情况下，文档或
基本这个样子，

173
00:07:20,840 --> 00:07:22,360
某种类型的定义。

174
00:07:22,360 --> 00:07:25,680
>> 如果我现在打开列表零点
C，注意的几件事情。

175
00:07:25,680 --> 00:07:29,090
它包括了几个头文件，最
我们之前见过。

176
00:07:29,090 --> 00:07:31,980
它包括其自己的头文件。

177
00:07:31,980 --> 00:07:35,200
>> 顺便说一句，这就是为什么双
报价。在这里，相对于角度

178
00:07:35,200 --> 00:07:38,340
括号就行了，
我已经强调了那里？

179
00:07:38,340 --> 00:07:39,180
>> 学生：[听不清]。

180
00:07:39,180 --> 00:07:40,460
>> 扬声器1：是啊，所以它是一个本地文件。

181
00:07:40,460 --> 00:07:44,300
所以，如果你自己在这里的本地文件
第15行，例如，您可以使用

182
00:07:44,300 --> 00:07:46,570
双引号，而不是
的尖括号。

183
00:07:46,570 --> 00:07:48,270
>> 现在，这是一种有趣的。

184
00:07:48,270 --> 00:07:51,830
注意，我已经宣布为全球
这个程序的第18行的变量

185
00:07:51,830 --> 00:07:55,910
被称为第一想法是这是
将是一个指针指向第一个

186
00:07:55,910 --> 00:07:59,190
在我的链表节点，并且我
初始化为null，因为我

187
00:07:59,190 --> 00:08:02,310
没有分配任何实际
节点只是还没有。

188
00:08:02,310 --> 00:08:07,570
>> 因此，这代表1973年，我们
刚才也看到了图片作为

189
00:08:07,570 --> 00:08:10,090
该指针远
左手侧。

190
00:08:10,090 --> 00:08:12,260
所以现在，该指针
不会有一个箭头。

191
00:08:12,260 --> 00:08:14,590
相反，它仅仅是空的。

192
00:08:14,590 --> 00:08:17,880
但它代表的会是怎样的
第一个实际的地址

193
00:08:17,880 --> 00:08:19,480
在此列表中的节点。

194
00:08:19,480 --> 00:08:22,120
所以，我已经实现了它是一个全球
因为，你会看到，这一切

195
00:08:22,120 --> 00:08:25,310
计划并落实在生活中是
一个链表为我。

196
00:08:25,310 --> 00:08:27,050
>> 现在我已经得到了一些原型。

197
00:08:27,050 --> 00:08:31,190
我决定实现的功能，如
缺失，插入，搜索和

198
00:08:31,190 --> 00:08:31,740
穿越 - 

199
00:08:31,740 --> 00:08:35,210
最后只是徒步穿越
列表，打印出它的元素。

200
00:08:35,210 --> 00:08:36,750
而现在，这里是我的主程序。

201
00:08:36,750 --> 00:08:39,890
并且我们不会花太多时间
这些，因为这是那种，希望

202
00:08:39,890 --> 00:08:41,780
现在的旧帽子。

203
00:08:41,780 --> 00:08:45,370
>> 我要做到以下几点：
而用户合作。

204
00:08:45,370 --> 00:08:47,300
所以，我要打印
出此菜单。

205
00:08:47,300 --> 00:08:49,420
我格式化它作为
干净，尽我所能。

206
00:08:49,420 --> 00:08:52,240
如果用户在一个类型，即表示
他们要删除的东西。

207
00:08:52,240 --> 00:08:54,560
如果用户有两种类型，即表示
他们要插入的东西。

208
00:08:54,560 --> 00:08:55,930
等等。

209
00:08:55,930 --> 00:08:58,270
我要提示
然后命令。

210
00:08:58,270 --> 00:08:59,300
然后我要使用调用getInt。

211
00:08:59,300 --> 00:09:02,790
>> 所以这是一个非常简单的menuing
界面，您只需要输入

212
00:09:02,790 --> 00:09:05,270
一些映射到一个
这些命令。

213
00:09:05,270 --> 00:09:08,730
现在我有一个漂亮干净的开关
语句要切换

214
00:09:08,730 --> 00:09:10,090
无论用户输入。

215
00:09:10,090 --> 00:09:12,180
而且，如果他们输入了一个，我会
调用delete和突破。

216
00:09:12,180 --> 00:09:14,380
如果他们输入了两个，我会
调用插入和突破。

217
00:09:14,380 --> 00:09:16,490
>> 现在请注意，我已经把每
这些在同一行上。

218
00:09:16,490 --> 00:09:18,360
这是一种风格上的决定。

219
00:09:18,360 --> 00:09:20,210
通常情况下，我们已经看到的东西
像这样。

220
00:09:20,210 --> 00:09:23,260
但我刚刚决定，坦率地说，我的程序
看上去更具可读性，因为

221
00:09:23,260 --> 00:09:25,980
它只有四个案件
像这样只列出。

222
00:09:25,980 --> 00:09:28,360
完全合法使用样式。

223
00:09:28,360 --> 00:09:31,480
我要做到这一点，只要
用户没有输入零，这是我

224
00:09:31,480 --> 00:09:33,910
决定将意味着他们想戒烟。

225
00:09:33,910 --> 00:09:36,630
>> 所以，现在发现我什么
要在这里做。

226
00:09:36,630 --> 00:09:38,650
我要去显然释放的清单。

227
00:09:38,650 --> 00:09:40,230
但在短短的时刻。

228
00:09:40,230 --> 00:09:41,640
首先，让我们来运行这个程序。

229
00:09:41,640 --> 00:09:45,250
因此，让我一个更大的终端
窗口，点斜线列表0。

230
00:09:45,250 --> 00:09:49,510
我要继续前进并插入
50这样的数字，现在打字两

231
00:09:49,510 --> 00:09:51,590
你会看到列表中现在是50。

232
00:09:51,590 --> 00:09:53,380
我的文字只是滚动了一下。

233
00:09:53,380 --> 00:09:55,940
所以，现在看到列表中包含
数字50。

234
00:09:55,940 --> 00:09:58,220
>> 让我们做另一个采取两个插入。

235
00:09:58,220 --> 00:10:01,630
让我们像一个输入的数量。

236
00:10:01,630 --> 00:10:03,940
列表现在，接着为50。

237
00:10:03,940 --> 00:10:06,020
所以这仅仅是一个文字表述
列表。

238
00:10:06,020 --> 00:10:10,550
我们插入一个像
数字42，这是有希望的

239
00:10:10,550 --> 00:10:14,620
要结束了，因为在中间
特别是各种程序

240
00:10:14,620 --> 00:10:16,320
它插入他们的元素。

241
00:10:16,320 --> 00:10:17,220
因此，我们有它。

242
00:10:17,220 --> 00:10:20,730
超级简单的程序，可以
绝对使用一个数组，但我

243
00:10:20,730 --> 00:10:23,280
碰巧使用一个链表
就这样我就可以动态地

244
00:10:23,280 --> 00:10:24,610
增长和收缩。

245
00:10:24,610 --> 00:10:28,470
>> 因此，让我们来看看搜索，如果我
运行命令三，我想搜索

246
00:10:28,470 --> 00:10:31,040
，也就是说，43号。

247
00:10:31,040 --> 00:10:34,190
显然并没有什么发现，
因为我回来没有反应。

248
00:10:34,190 --> 00:10:35,010
因此，让我们再次做到这一点。

249
00:10:35,010 --> 00:10:35,690
搜索。

250
00:10:35,690 --> 00:10:39,520
50，或者更确切地说，搜索的搜索
42，有一个很好的

251
00:10:39,520 --> 00:10:40,850
有点微妙的含义。

252
00:10:40,850 --> 00:10:42,610
而且我发现有生命的意义。

253
00:10:42,610 --> 00:10:44,990
42，如果你不知道
参考谷歌。

254
00:10:44,990 --> 00:10:45,350
好的。

255
00:10:45,350 --> 00:10:47,130
那么是什么为我做这个程序？

256
00:10:47,130 --> 00:10:50,660
它只是让我插入从而
到目前为止，搜索元素。

257
00:10:50,660 --> 00:10:53,650
>> 让我们快进，那么，
我们瞟了一眼那个函数

258
00:10:53,650 --> 00:10:55,360
周一传情。

259
00:10:55,360 --> 00:10:59,620
所以，我要求这个功能，搜索
第一列表中的一个元素

260
00:10:59,620 --> 00:11:03,830
一，提示用户，然后调用
调用getInt得到一个实际的int

261
00:11:03,830 --> 00:11:05,060
要搜索。

262
00:11:05,060 --> 00:11:06,460
>> 然后注意到这一点。

263
00:11:06,460 --> 00:11:10,690
我要创建一个临时变量
在第188行称为指针 - 

264
00:11:10,690 --> 00:11:11,270
PTR  - 

265
00:11:11,270 --> 00:11:12,440
可以把它叫做什么。

266
00:11:12,440 --> 00:11:16,140
这是一个节点的指针
因为我说有节点*。

267
00:11:16,140 --> 00:11:19,900
我初始化它等于
首先，让我实际上是我的

268
00:11:19,900 --> 00:11:22,860
手指，可以这么说，就非常
列表中的第一个元素。

269
00:11:22,860 --> 00:11:27,460
所以，如果我的右手是PTR我
指向同一件事，第一

270
00:11:27,460 --> 00:11:28,670
是否对准。

271
00:11:28,670 --> 00:11:31,430
>> 现在，我们回到代码中，
接下来会发生什么 - 

272
00:11:31,430 --> 00:11:35,070
迭代时，这是一个共同的范式
像结构

273
00:11:35,070 --> 00:11:35,970
链表。

274
00:11:35,970 --> 00:11:40,410
我要做到以下几点，同时
指针不等于空，因此，

275
00:11:40,410 --> 00:11:47,530
我的手指指着一些空
值，如果指针箭头n等于N。

276
00:11:47,530 --> 00:11:52,290
我们首先会注意到，n是什么
用户输入每GetInts这里打电话。

277
00:11:52,290 --> 00:11:54,280
>> 和指针箭头N意味着什么呢？

278
00:11:54,280 --> 00:11:59,020
好吧，如果我们再回到这里的图片，
如果我有一个手指指着

279
00:11:59,020 --> 00:12:02,960
九，即第一个节点
箭头基本上意味着去那

280
00:12:02,960 --> 00:12:08,860
节点，并抢在位置n的值，
在这种情况下，数据字段称为N。

281
00:12:08,860 --> 00:12:14,120
>> 顺便说一句 - 我们看到一对夫妇
星期前，当有人问 - 

282
00:12:14,120 --> 00:12:18,840
这个语法是新的，但它不
给我们的权力，我们

283
00:12:18,840 --> 00:12:20,040
没有已经有了。

284
00:12:20,040 --> 00:12:25,325
这句话是什么相当于使用
点符号和明星夫妇

285
00:12:25,325 --> 00:12:29,490
星期前，当我们剥开
这一层有点过早？

286
00:12:29,490 --> 00:12:31,780
>> 学生：[听不清]。

287
00:12:31,780 --> 00:12:38,880
>> 扬声器1：没错，这是明星，
那么它是星点N，

288
00:12:38,880 --> 00:12:41,930
括号在这里，它看起来，
坦率地说，我想了很多

289
00:12:41,930 --> 00:12:43,320
更神秘的阅读。

290
00:12:43,320 --> 00:12:46,270
但星级指针，一如既往
手段去那里。

291
00:12:46,270 --> 00:12:49,090
而一旦你在那里，什么样的数据
现场你要访问吗？

292
00:12:49,090 --> 00:12:52,730
那么你用点符号访问
一个结构的数据字段，我

293
00:12:52,730 --> 00:12:54,140
特别希望N。

294
00:12:54,140 --> 00:12:56,240
>> 坦率地说，我认为这
只是很难阅读。

295
00:12:56,240 --> 00:12:58,080
这是很难记得在哪里
做括号走，

296
00:12:58,080 --> 00:12:59,030
明星和一切。

297
00:12:59,030 --> 00:13:02,150
因此，世界上采取了一些句法
糖，可以这么说。

298
00:13:02,150 --> 00:13:04,740
只是一个性感的说法，
这是等价的，并且

299
00:13:04,740 --> 00:13:05,970
或许更直观。

300
00:13:05,970 --> 00:13:09,600
如果指针确实是一个指针，
箭头符号手段去那里找

301
00:13:09,600 --> 00:13:11,890
在这种情况下，该领域称为N。

302
00:13:11,890 --> 00:13:13,660
>> 所以，如果我找到它，发现我做什么。

303
00:13:13,660 --> 00:13:17,430
我只是打印出来，我发现我％，
堵在这个int值。

304
00:13:17,430 --> 00:13:20,730
我叫睡一秒钟只是一种
暂停在屏幕上的东西

305
00:13:20,730 --> 00:13:22,900
给用户一个第二吸收
刚刚发生了什么。

306
00:13:22,900 --> 00:13:24,290
然后我就打破。

307
00:13:24,290 --> 00:13:26,330
否则，我该怎么办？

308
00:13:26,330 --> 00:13:30,960
我更新指针等于
指针旁边的箭头。

309
00:13:30,960 --> 00:13:35,840
>> 所以，仅仅是明确的，这意味着去
在那里，我的老学校的符号。

310
00:13:35,840 --> 00:13:39,580
因此，这只是意味着去任何
你指出，这在很

311
00:13:39,580 --> 00:13:43,660
第一种情况是，我指着
结构九。

312
00:13:43,660 --> 00:13:44,510
所以，我去那里。

313
00:13:44,510 --> 00:13:47,880
然后点符号表示，
在未来获得价值。

314
00:13:47,880 --> 00:13:50,470
>> 但该值，即使它的绘制
作为窄，仅仅是一个数字。

315
00:13:50,470 --> 00:13:51,720
这是一个数字地址。

316
00:13:51,720 --> 00:13:55,670
所以这一行代码，无论
这样写，更神秘

317
00:13:55,670 --> 00:14:00,190
的方式，还是这个样子，稍微
直观的方式，只是意味着移动我的手

318
00:14:00,190 --> 00:14:03,460
从第一个节点到下一个，
然后下一个，然后

319
00:14:03,460 --> 00:14:05,320
下一个，等等。

320
00:14:05,320 --> 00:14:09,920
>> 因此，我们不会纠缠于其他
插入和删除的实现

321
00:14:09,920 --> 00:14:14,030
和遍历，前两个
这是相当复杂的。

322
00:14:14,030 --> 00:14:17,010
而且，我认为这是很容易得到
做口头丢失。

323
00:14:17,010 --> 00:14:19,890
但我们可以在这里做什么
尝试，以确定如何

324
00:14:19,890 --> 00:14:21,640
最好做视觉。

325
00:14:21,640 --> 00:14:24,800
因为我会提出，如果我们
要插入元素

326
00:14:24,800 --> 00:14:26,680
现有的名单，其中
有五个要素 - 

327
00:14:26,680 --> 00:14:29,530
9，17，22，26，33  - 

328
00:14:29,530 --> 00:14:33,300
如果我要实现这
代码，我需要考虑如何去

329
00:14:33,300 --> 00:14:34,160
这样做。

330
00:14:34,160 --> 00:14:37,720
>> 我建议采取小步
据此，在这种情况下，我的意思是什么

331
00:14:37,720 --> 00:14:41,090
可能出现的情况，我们
可能遇到的一般？

332
00:14:41,090 --> 00:14:44,120
当执行插入一个链接
名单，这恰好是一个

333
00:14:44,120 --> 00:14:46,090
具体例的大小为5。

334
00:14:46,090 --> 00:14:50,420
好吧，如果你要插入一个数字，
喜欢说的头号

335
00:14:50,420 --> 00:14:53,380
保持排序顺序，其中
显然做一个需要数

336
00:14:53,380 --> 00:14:55,686
走在这个具体的例子吗？

337
00:14:55,686 --> 00:14:56,840
开始时一样。

338
00:14:56,840 --> 00:15:00,030
>> 但有趣的是
如果你要插入到这个

339
00:15:00,030 --> 00:15:04,100
列表中，需要什么特殊的指针
显然要更新？

340
00:15:04,100 --> 00:15:04,610
第一。

341
00:15:04,610 --> 00:15:07,830
所以，我认为，这是第一种情况
我们可能要考虑，

342
00:15:07,830 --> 00:15:11,140
方案涉及于
在列表的开头。

343
00:15:11,140 --> 00:15:15,400
>> 让我们为这事也许容易，甚至
更简单的情况下，相对来说。

344
00:15:15,400 --> 00:15:18,110
假设我要插入
35号排序。

345
00:15:18,110 --> 00:15:20,600
这显然​​属于那边。

346
00:15:20,600 --> 00:15:25,320
那么，什么指针，显然是要
在这种情况下必须进行更新？

347
00:15:25,320 --> 00:15:30,060
34的指针变得不空
但该结构的地址

348
00:15:30,060 --> 00:15:31,800
含有数字35。

349
00:15:31,800 --> 00:15:32,750
因此，案例二。

350
00:15:32,750 --> 00:15:36,190
所以，我已经是量化排序
在这里我必须做多少工作。

351
00:15:36,190 --> 00:15:39,880
>> 最后，明显的中间的情况下是
的确，如果我在中间，要

352
00:15:39,880 --> 00:15:45,870
插入像说23，云
在23和26之间，但

353
00:15:45,870 --> 00:15:48,680
现在事情变得有点更
因为涉及什么

354
00:15:48,680 --> 00:15:52,800
指针需要改变吗？

355
00:15:52,800 --> 00:15:56,680
因此，22显然需要改变
因为他不能点到26了。

356
00:15:56,680 --> 00:16:00,320
他需要，以指向新节点
我将不得不通过调用分配

357
00:16:00,320 --> 00:16:01,770
malloc或一些等价。

358
00:16:01,770 --> 00:16:05,990
>> 但是，我也需要新的节点，23
在这种情况下，有它的指针

359
00:16:05,990 --> 00:16:07,870
指向谁？

360
00:16:07,870 --> 00:16:08,560
26。

361
00:16:08,560 --> 00:16:10,380
而且也将是一个
这里的操作顺序。

362
00:16:10,380 --> 00:16:13,410
因为如果我这样做愚蠢的是，我和
实例的开始处开始

363
00:16:13,410 --> 00:16:16,040
列表中，我的目标是要插入23。

364
00:16:16,040 --> 00:16:18,610
检查，它属于
在这里，近九？

365
00:16:18,610 --> 00:16:18,950
号

366
00:16:18,950 --> 00:16:20,670
它属于这里，未来17？

367
00:16:20,670 --> 00:16:20,940
号

368
00:16:20,940 --> 00:16:22,530
是否属于这里旁边22？

369
00:16:22,530 --> 00:16:23,300
是。

370
00:16:23,300 --> 00:16:26,400
>> 现在，如果我在这里很愚蠢的，而不是
通过思考，我可能

371
00:16:26,400 --> 00:16:28,320
分配我的新节点上为23。

372
00:16:28,320 --> 00:16:32,080
我可能会更新指针
节点称为22，指着

373
00:16:32,080 --> 00:16:33,080
在新的节点。

374
00:16:33,080 --> 00:16:36,140
然后我有什么更新
新节点的指针？

375
00:16:36,140 --> 00:16:38,120
>> 学生：[听不清]。

376
00:16:38,120 --> 00:16:38,385
>> 扬声器1：没错。

377
00:16:38,385 --> 00:16:39,710
指着26。

378
00:16:39,710 --> 00:16:45,590
但是，该死，如果我没有已经更新
22的指针指向这个家伙，

379
00:16:45,590 --> 00:16:48,260
现在我有孤儿，其余
列表，可以这么说。

380
00:16:48,260 --> 00:16:52,140
所以，这里的操作顺序
会是重要的。

381
00:16:52,140 --> 00:16:55,100
>> 要做到这一点，我能偷，
说，六个月志愿者。

382
00:16:55,100 --> 00:16:57,650
让我们来看看，如果我们不能做到这一点
视觉上，而不是代码明智。

383
00:16:57,650 --> 00:16:59,330
我们有一些可爱的压力
今天为你的球。

384
00:16:59,330 --> 00:17:02,510
OK，约一，两个，在
回 - 到底有没有。

385
00:17:02,510 --> 00:17:04,530
三，四，双方你
家伙到底。

386
00:17:04,530 --> 00:17:05,579
及五，六。

387
00:17:05,579 --> 00:17:05,839
当然。

388
00:17:05,839 --> 00:17:06,450
五和六。

389
00:17:06,450 --> 00:17:08,390
好吧，我们还会回来
你们下一次。

390
00:17:08,390 --> 00:17:09,640
好吧，我们就到了。

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> 所有的权利，因为你先在这里
你想成为一个笨拙

393
00:17:14,819 --> 00:17:16,119
在谷歌的玻璃在这里？

394
00:17:16,119 --> 00:17:19,075
好，那么，OK，玻璃，
录制视频。

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK，你去好。

397
00:17:24,589 --> 00:17:27,950
>> 所有的权利，所以如果你们可以过来
在这里，我已经提前做好准备

398
00:17:27,950 --> 00:17:30,110
一些数字。

399
00:17:30,110 --> 00:17:31,240
好吧，我们在这里。

400
00:17:31,240 --> 00:17:33,440
而你为什么不走一点
进一步的方式。

401
00:17:33,440 --> 00:17:35,520
，让我们看看，你叫什么名字，
谷歌玻璃？

402
00:17:35,520 --> 00:17:35,910
>> 学生：本。

403
00:17:35,910 --> 00:17:36,230
>> 扬声器1：本？

404
00:17:36,230 --> 00:17:38,380
OK，奔，你将是第一，从字面上。

405
00:17:38,380 --> 00:17:40,580
因此，我们会向您发送
结束阶段。

406
00:17:40,580 --> 00:17:41,670
所有的权利，和你的名字吗？

407
00:17:41,670 --> 00:17:41,990
>> 学生：贾森。

408
00:17:41,990 --> 00:17:44,530
>> 扬声器1：杰森，OK你
9号。

409
00:17:44,530 --> 00:17:46,700
所以，如果你想遵循本办法。

410
00:17:46,700 --> 00:17:47,010
>> 学生：吉尔。

411
00:17:47,010 --> 00:17:49,630
>> 扬声器1：吉尔，你要去
17，如果我这样做

412
00:17:49,630 --> 00:17:51,260
智能，我将不得不
在其另一端开始。

413
00:17:51,260 --> 00:17:52,370
你走那条路。

414
00:17:52,370 --> 00:17:53,030
22。

415
00:17:53,030 --> 00:17:53,670
你是谁？

416
00:17:53,670 --> 00:17:53,980
>> 学生：玛丽。

417
00:17:53,980 --> 00:17:56,130
>> 扬声器1：玛丽，你会是22。

418
00:17:56,130 --> 00:17:58,420
你的名字是什么？

419
00:17:58,420 --> 00:17:58,810
>> 学生：克里斯。

420
00:17:58,810 --> 00:18:00,100
>> 扬声器1：克里斯，你会是26。

421
00:18:00,100 --> 00:18:00,740
然后最后。

422
00:18:00,740 --> 00:18:01,400
>> 学生：戴安娜。

423
00:18:01,400 --> 00:18:02,670
>> 扬声器1：戴安娜，你会是34。

424
00:18:02,670 --> 00:18:03,920
所以你在这里。

425
00:18:03,920 --> 00:18:06,360
>> 好吧，如此完美排序
已经订购。

426
00:18:06,360 --> 00:18:09,600
，让我们继续前进，为此
这样我们就可以真的 - 

427
00:18:09,600 --> 00:18:11,720
奔你只是寻找一种
到无处存在。

428
00:18:11,720 --> 00:18:15,670
OK，让我们继续前进，并描绘这个
使用武器，就像我，究竟

429
00:18:15,670 --> 00:18:16,250
这是怎么回事。

430
00:18:16,250 --> 00:18:19,540
因此，继续前进，给自己一个
步行或两个自己之间。

431
00:18:19,540 --> 00:18:22,900
继续前进，用一只手点
你应该指向谁

432
00:18:22,900 --> 00:18:23,470
在此基础上。

433
00:18:23,470 --> 00:18:25,890
如果你只是指向空
直下到地板上。

434
00:18:25,890 --> 00:18:27,690
OK，这样很好。

435
00:18:27,690 --> 00:18:32,290
>> 所以现在我们有一个链表，让我
建议，我会发挥的作用

436
00:18:32,290 --> 00:18:35,110
PTR，所以我不会打扰
携带这种左右。

437
00:18:35,110 --> 00:18:37,830
然后 - 有人愚蠢的惯例 - 
你可以调用任何你想要的 - 

438
00:18:37,830 --> 00:18:39,800
前身指针，泼尼松指针 - 

439
00:18:39,800 --> 00:18:43,930
它只是我们给的绰号
我们的示例代码，我的左手。

440
00:18:43,930 --> 00:18:47,240
另一方面，要保持
谁是谁在跟踪

441
00:18:47,240 --> 00:18:48,400
下面的场景。

442
00:18:48,400 --> 00:18:52,390
>> 因此，假设，第一，我要拔掉
，插入第一个例子，说

443
00:18:52,390 --> 00:18:54,330
20，到列表中。

444
00:18:54,330 --> 00:18:57,160
所以我需要有人来
体现我们20号。

445
00:18:57,160 --> 00:18:58,950
所以我需要有人对malloc
从观众。

446
00:18:58,950 --> 00:18:59,380
上来吧。

447
00:18:59,380 --> 00:19:00,340
你叫什么名字？

448
00:19:00,340 --> 00:19:01,300
>> 学生：布莱恩。

449
00:19:01,300 --> 00:19:05,270
>> 扬声器1：布莱恩，所有的权利，所以你
须含20的节点。

450
00:19:05,270 --> 00:19:06,810
好吧，我们在这里。

451
00:19:06,810 --> 00:19:10,025
很显然，
不属于布赖恩？

452
00:19:10,025 --> 00:19:12,190
因此，在中间 - 实际上，
等待一分钟。

453
00:19:12,190 --> 00:19:13,420
我们这样做是为了

454
00:19:13,420 --> 00:19:17,170
我们正在做这个了很多困难
比它需要的是在第一次。

455
00:19:17,170 --> 00:19:21,210
OK，我们要免费布赖恩
和realloc的布赖恩五个。

456
00:19:21,210 --> 00:19:23,680
>> 好了，现在我们要插入
布赖恩五个。

457
00:19:23,680 --> 00:19:25,960
这样一来就在这里
本只是一瞬间。

458
00:19:25,960 --> 00:19:28,250
你大概可以告诉
这个故事是怎么回事。

459
00:19:28,250 --> 00:19:30,500
但是，让我们仔细想想
操作顺序。

460
00:19:30,500 --> 00:19:32,880
和它的正是这种视觉
要排队

461
00:19:32,880 --> 00:19:34,080
与示例代码。

462
00:19:34,080 --> 00:19:40,120
所以，我在这里已经PTR最初指向
不奔，本身的，但在任何

463
00:19:40,120 --> 00:19:43,245
重视他包含在这种情况下
 - 再次你叫什么名字？

464
00:19:43,245 --> 00:19:43,670
>> 学生：贾森。

465
00:19:43,670 --> 00:19:47,350
>> 扬声器1：杰森，所以我和Ben
指着杰森在这一刻。

466
00:19:47,350 --> 00:19:49,700
所以现在我必须确定，
布赖恩属于哪里？

467
00:19:49,700 --> 00:19:53,500
那么唯一，我曾访问
现在是他的n个数据项。

468
00:19:53,500 --> 00:19:58,280
所以我要来检查，
布赖恩小于贾森？

469
00:19:58,280 --> 00:19:59,770
答案是真实的。

470
00:19:59,770 --> 00:20:03,680
>> 那么现在需要什么发生，
以正确的顺序？

471
00:20:03,680 --> 00:20:07,120
我需要更新多少指针
总在这个故事呢？

472
00:20:07,120 --> 00:20:10,720
在哪里，我的手仍指向
杰森，和你的手 - 如果你想

473
00:20:10,720 --> 00:20:12,930
把你的手，有点像，我
不知道，是一个问号。

474
00:20:12,930 --> 00:20:14,070
好，好。

475
00:20:14,070 --> 00:20:15,670
>> 好吧，让你拥有
几个候选人。

476
00:20:15,670 --> 00:20:20,500
奔或I或布赖恩或杰森
或其他人，这

477
00:20:20,500 --> 00:20:21,370
指针需要改变吗？

478
00:20:21,370 --> 00:20:23,260
总共有多少人？

479
00:20:23,260 --> 00:20:24,080
>> OK，所以两个。

480
00:20:24,080 --> 00:20:27,090
我的指针并不真的无所谓了
因为我只是暂时的。

481
00:20:27,090 --> 00:20:31,370
因此，它是这两个家伙，据推测，
Ben和布赖恩。

482
00:20:31,370 --> 00:20:34,410
所以我建议大家更新
奔，因为他是第一。

483
00:20:34,410 --> 00:20:36,350
这个列表的第一个元素
现在将是布莱恩。

484
00:20:36,350 --> 00:20:38,070
因此，本布赖恩点。

485
00:20:38,070 --> 00:20:39,320
OK，现在该怎么办呢？

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> 谁被指出在谁？

488
00:20:43,460 --> 00:20:44,710
>> 学生：[听不清]。

489
00:20:44,710 --> 00:20:46,180
>> 扬声器1：确定Brian拥有
以指向贾森。

490
00:20:46,180 --> 00:20:48,360
但我已经失去了该指针的轨道？

491
00:20:48,360 --> 00:20:49,980
我知道Jason是吗？

492
00:20:49,980 --> 00:20:50,790
>> 学生：[听不清]。

493
00:20:50,790 --> 00:20:52,620
>> 扬声器1：我做的，因为我
暂时指针。

494
00:20:52,620 --> 00:20:55,110
而据推测，我并没有改变
指向新的节点。

495
00:20:55,110 --> 00:20:58,300
所以，我们可以简单地布赖恩点
我指着谁。

496
00:20:58,300 --> 00:20:59,000
我们就大功告成了。

497
00:20:59,000 --> 00:21:01,890
所以，在插入
开始的名单。

498
00:21:01,890 --> 00:21:02,950
有两个关键步骤。

499
00:21:02,950 --> 00:21:06,750
一，我们必须更新奔，然后
我们也有更新布赖恩。

500
00:21:06,750 --> 00:21:09,230
然后我没有打扰
其余的疲惫

501
00:21:09,230 --> 00:21:12,680
名单，因为我们已经找到了自己的
位置，因为他属于

502
00:21:12,680 --> 00:21:14,080
左侧的第一个元素。

503
00:21:14,080 --> 00:21:15,400
>> 所有的权利，所以非常简单。

504
00:21:15,400 --> 00:21:18,110
事实上，感觉就像我们几乎
这太复杂了。

505
00:21:18,110 --> 00:21:20,240
现在让我们为这事结束
列表，看到

506
00:21:20,240 --> 00:21:21,380
开始的复杂性。

507
00:21:21,380 --> 00:21:24,560
因此，如果现在，我的alloc从观众。

508
00:21:24,560 --> 00:21:25,540
任何人想打55？

509
00:21:25,540 --> 00:21:26,700
好吧，我先看到你的手。

510
00:21:26,700 --> 00:21:29,620
上来吧。

511
00:21:29,620 --> 00:21:30,030
嗯。

512
00:21:30,030 --> 00:21:31,177
你叫什么名字？

513
00:21:31,177 --> 00:21:32,310
>> 学生：[听不清]。

514
00:21:32,310 --> 00:21:33,240
>> 扬声器1 Habata。

515
00:21:33,240 --> 00:21:33,890
OK，就到了。

516
00:21:33,890 --> 00:21:35,730
你会是55号。

517
00:21:35,730 --> 00:21:37,820
所以，你，当然，属于
上面的列表末尾。

518
00:21:37,820 --> 00:21:41,850
因此，让我们重播模拟与我
是PTR只是一瞬间。

519
00:21:41,850 --> 00:21:44,050
所以，我首先要指向
无论奔指向。

520
00:21:44,050 --> 00:21:45,900
我们都指向现在在布赖恩。

521
00:21:45,900 --> 00:21:48,420
因此，图55是不小于5。

522
00:21:48,420 --> 00:21:52,510
所以，我要更新自己的
Brian的下一个指针，指向谁

523
00:21:52,510 --> 00:21:54,450
现在当然贾森。

524
00:21:54,450 --> 00:21:57,310
图55是不小于9，所以
我要更新PTR。

525
00:21:57,310 --> 00:21:58,890
我要更新PTR。

526
00:21:58,890 --> 00:22:02,290
我要更新的PTR
我更新的PTR。

527
00:22:02,290 --> 00:22:05,060
我要去 - 嗯，有什么
你的名字吗？

528
00:22:05,060 --> 00:22:05,560
>> 学生：戴安娜。

529
00:22:05,560 --> 00:22:09,190
>> 扬声器1：戴安娜是指指点点，当然，
在null与她的左手。

530
00:22:09,190 --> 00:22:13,030
那么，这实际上Habata
属于清楚吗？

531
00:22:13,030 --> 00:22:15,050
到左边，在这里。

532
00:22:15,050 --> 00:22:19,460
所以，我怎么知道在这里把她
我想我搞砸了。

533
00:22:19,460 --> 00:22:22,420
因为PTR艺术
时间在这一刻？

534
00:22:22,420 --> 00:22:23,240
NULL。

535
00:22:23,240 --> 00:22:25,580
因此，即使，在视觉上，我们就可以
明显看到所有这些

536
00:22:25,580 --> 00:22:26,610
这里的人在舞台上。

537
00:22:26,610 --> 00:22:29,680
我以前没有记录
在列表中的人。

538
00:22:29,680 --> 00:22:33,210
我没有手指指出，
在这种情况下，节点号为34。

539
00:22:33,210 --> 00:22:34,760
>> 因此，让我们真正开始过。

540
00:22:34,760 --> 00:22:37,560
所以，现在我居然需要
一个第二局部变量。

541
00:22:37,560 --> 00:22:40,980
这是什么，你会看到在
实际样品的C代码，在那里，因为我去，

542
00:22:40,980 --> 00:22:45,860
当我更新我的右手指向
杰森，从而留下布赖恩的背后，我

543
00:22:45,860 --> 00:22:51,440
最好开始用我的左手
更新我在哪里，让我去

544
00:22:51,440 --> 00:22:52,700
通过这个名单 - 

545
00:22:52,700 --> 00:22:55,040
比我预期的更笨拙
现在这里视觉 - 

546
00:22:55,040 --> 00:22:56,740
我会去的
列表末尾。

547
00:22:56,740 --> 00:23:00,020
>> 这手仍是空的，这是非常
没用的，其他的比来表示

548
00:23:00,020 --> 00:23:02,980
我很清楚在列表末尾，
但现在至少我有这个

549
00:23:02,980 --> 00:23:08,270
前身指向这里，所以
现在是什么手和指针需要什么

550
00:23:08,270 --> 00:23:10,150
要更新？

551
00:23:10,150 --> 00:23:13,214
你想谁的手
先来重新配置？

552
00:23:13,214 --> 00:23:15,190
>> 学生：[听不清]。

553
00:23:15,190 --> 00:23:16,220
>> 扬声器1：OK，所以戴安娜的。

554
00:23:16,220 --> 00:23:21,110
在哪里你想点
戴安娜的左指针？

555
00:23:21,110 --> 00:23:23,620
在55中，据推测，从而使
我们已经有插入。

556
00:23:23,620 --> 00:23:25,560
55指针应该在哪里去了？

557
00:23:25,560 --> 00:23:27,000
向下，占空。

558
00:23:27,000 --> 00:23:28,890
而我的手，在这一点上，不
不要紧，因为他们只是

559
00:23:28,890 --> 00:23:30,070
临时变量。

560
00:23:30,070 --> 00:23:31,030
所以，现在我们就大功告成了。

561
00:23:31,030 --> 00:23:34,650
>> 所以额外的复杂性 - 
它并不难实现，

562
00:23:34,650 --> 00:23:38,660
但我们需要一个辅助变量
确定之前，我将我的权利

563
00:23:38,660 --> 00:23:42,140
另一方面，我更新我的左值
另一方面，泼尼松指针在这种情况下，因此

564
00:23:42,140 --> 00:23:45,860
我有一个尾随指针
跟踪我在哪里。

565
00:23:45,860 --> 00:23:49,360
顺便说一句，如果你以为这
通过，这种感觉就像是一个

566
00:23:49,360 --> 00:23:51,490
必须保持有点烦
跟踪这个左手。

567
00:23:51,490 --> 00:23:54,015
>> 将另一种解决方案
这个问题已被？

568
00:23:54,015 --> 00:23:56,500
如果你得到了重新设计数据
我们正在谈论的结构

569
00:23:56,500 --> 00:23:59,630
通过吧？

570
00:23:59,630 --> 00:24:02,690
如果这只是一种感觉有点
恼人的一样，两个指针

571
00:24:02,690 --> 00:24:08,430
通过列表，谁还能
有，在一个理想的世界中，保持

572
00:24:08,430 --> 00:24:10,160
我们所需要的信息？

573
00:24:10,160 --> 00:24:11,360
是吗？

574
00:24:11,360 --> 00:24:12,610
>> 学生：[听不清]。

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> 扬声器1：没错。

577
00:24:16,150 --> 00:24:19,130
所以实际上是一个有趣的
胚芽的想法。

578
00:24:19,130 --> 00:24:22,470
而前一个指针，这个想法
指向前一个元素。

579
00:24:22,470 --> 00:24:25,580
如果我只是体现
列表本身的内部？

580
00:24:25,580 --> 00:24:27,810
这将是难以想像
没有所有的纸张

581
00:24:27,810 --> 00:24:28,830
掉落到地板上。

582
00:24:28,830 --> 00:24:31,860
但是，假如这些人同时使用
他们手中没有先前

583
00:24:31,860 --> 00:24:35,950
指针，和一个下一个指针，从而
执行什么，我们会打电话给一个双

584
00:24:35,950 --> 00:24:36,830
链表。

585
00:24:36,830 --> 00:24:41,090
这将允许我排序退，
更容易无我有，

586
00:24:41,090 --> 00:24:43,800
程序员，不得不保持
手动跟踪 - 

587
00:24:43,800 --> 00:24:44,980
真正的手动 - 

588
00:24:44,980 --> 00:24:47,280
以前我一直
在列表中。

589
00:24:47,280 --> 00:24:48,110
因此，我们将无法做到这一点。

590
00:24:48,110 --> 00:24:50,950
我们将保持它的简单，因为这是
要来的价格，两倍

591
00:24:50,950 --> 00:24:53,450
多的空间的指针，
如果你想要第二个。

592
00:24:53,450 --> 00:24:55,760
但是，这确实是一个共同的
数据结构被称为一个

593
00:24:55,760 --> 00:24:57,410
双向链表。

594
00:24:57,410 --> 00:25:01,310
>> 让我们在这里做最后的例子把
这些家伙，他们的苦难。

595
00:25:01,310 --> 00:25:03,270
所以malloc的20。

596
00:25:03,270 --> 00:25:05,320
来吧从那里的过道。

597
00:25:05,320 --> 00:25:06,280
好吧，你叫什么名字？

598
00:25:06,280 --> 00:25:07,440
>> 学生：[听不清]。

599
00:25:07,440 --> 00:25:07,855
>> 扬声器1：对不起？

600
00:25:07,855 --> 00:25:08,480
>> 学生：[听不清]。

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1：Demeron的？

602
00:25:09,410 --> 00:25:10,230
确定上来吧。

603
00:25:10,230 --> 00:25:11,910
您应为20。

604
00:25:11,910 --> 00:25:14,720
你显然要
属于17和22之间。

605
00:25:14,720 --> 00:25:16,150
因此，让我吸取我的教训。

606
00:25:16,150 --> 00:25:18,150
我要开始指针
指着布赖恩。

607
00:25:18,150 --> 00:25:21,190
我要我的左手
只更新布莱恩，我谨

608
00:25:21,190 --> 00:25:23,600
杰森，检查少做了20比9？

609
00:25:23,600 --> 00:25:24,060
号

610
00:25:24,060 --> 00:25:25,430
20小于17？

611
00:25:25,430 --> 00:25:25,880
号

612
00:25:25,880 --> 00:25:27,450
20小于22？

613
00:25:27,450 --> 00:25:28,440
是。

614
00:25:28,440 --> 00:25:34,070
那么，什么指针或手需要改变
他们指着呢？

615
00:25:34,070 --> 00:25:37,070
>> 因此，我们可以做的17指向20。

616
00:25:37,070 --> 00:25:37,860
所以这就是罚款。

617
00:25:37,860 --> 00:25:40,080
我们要指出在哪里
你的指针现在？

618
00:25:40,080 --> 00:25:41,330
在22。

619
00:25:41,330 --> 00:25:45,410
我们知道22，再次感谢
我临时指针。

620
00:25:45,410 --> 00:25:46,760
因此，我们有“确定”。

621
00:25:46,760 --> 00:25:49,440
所以在这临时存储
我一直保留着的轨道，每个人都。

622
00:25:49,440 --> 00:25:55,055
现在，你可以直观地去到哪里
属于你，现在我们需要1，2，3，

623
00:25:55,055 --> 00:25:58,410
4，5，6，7，8，9个压力球，
和掌声雷动

624
00:25:58,410 --> 00:25:59,770
这些家伙，如果我们能。

625
00:25:59,770 --> 00:26:00,410
干得漂亮。

626
00:26:00,410 --> 00:26:05,320
>> [掌声]

627
00:26:05,320 --> 00:26:06,330
>> 扬声器1：所有权利。

628
00:26:06,330 --> 00:26:09,860
您可能保持件
纸作为纪念。

629
00:26:09,860 --> 00:26:15,930
>> 好，那么相信我，这是一个很大
更容易穿行

630
00:26:15,930 --> 00:26:17,680
人类比它的实际代码。

631
00:26:17,680 --> 00:26:22,690
但你会发现在短短的时刻
现在，是相同的 - 哦，谢谢你。

632
00:26:22,690 --> 00:26:23,630
谢谢 - 

633
00:26:23,630 --> 00:26:29,360
是，你会发现相同的数据
结构，链表，实际上可以

634
00:26:29,360 --> 00:26:33,200
可以使用作为构建块更
复杂的数据结构。

635
00:26:33,200 --> 00:26:37,620
>> 实现过这里的主题是
我们绝对介绍

636
00:26:37,620 --> 00:26:40,060
进入实施的复杂性
在此算法中。

637
00:26:40,060 --> 00:26:43,940
插入，如果我们通过它去，
删除和搜索，是一个小的

638
00:26:43,940 --> 00:26:46,660
比它更复杂
是一个数组。

639
00:26:46,660 --> 00:26:48,040
但是，我们获得了一些活力。

640
00:26:48,040 --> 00:26:50,180
我们得到一个自适应的数据结构。

641
00:26:50,180 --> 00:26:54,010
>> 但同样，我们付出的代价有一些
额外的复杂性，无论是在

642
00:26:54,010 --> 00:26:54,910
执行它。

643
00:26:54,910 --> 00:26:56,750
我们放弃了随机访问。

644
00:26:56,750 --> 00:27:00,450
而且说实话，有没有一些不错的
干净的玻片，我可以给你，

645
00:27:00,450 --> 00:27:03,120
这里说的是为什么一个链表
优于数组。

646
00:27:03,120 --> 00:27:04,100
离开它。

647
00:27:04,100 --> 00:27:07,520
由于主题现在再次发生，甚至
更何况在未来几周内，

648
00:27:07,520 --> 00:27:10,200
不一定
一个正确的答案。

649
00:27:10,200 --> 00:27:13,830
>> 这就是为什么我们有独立的轴
问题集的设计。

650
00:27:13,830 --> 00:27:17,700
这将是非常敏感的上下文
您是否要使用此数据

651
00:27:17,700 --> 00:27:21,750
结构或那一个，会
取决于什么对你很重要条款

652
00:27:21,750 --> 00:27:24,620
的资源和复杂性。

653
00:27:24,620 --> 00:27:28,830
>> 但是，让我提出，理想的数据
结构，圣杯，将

654
00:27:28,830 --> 00:27:32,200
东西是恒定的时间，
不论多少东西

655
00:27:32,200 --> 00:27:36,940
在它里面，它不会是惊人的，如果一个
返回的数据结构答案

656
00:27:36,940 --> 00:27:37,920
常量时间。

657
00:27:37,920 --> 00:27:38,330
是。

658
00:27:38,330 --> 00:27:40,110
这个词是在巨大的字典。

659
00:27:40,110 --> 00:27:41,550
“或”否“，这个词是没有的。

660
00:27:41,550 --> 00:27:43,270
或任何这样的问题。

661
00:27:43,270 --> 00:27:46,360
那么让我们来看看，如果我们不能至少
走，一步步走向。

662
00:27:46,360 --> 00:27:50,190
>> 让我提出了一个新的数据结构，
可用于不同的事情，

663
00:27:50,190 --> 00:27:52,260
在这种情况下，所谓的哈希表。

664
00:27:52,260 --> 00:27:55,590
所以我们实际上一眼
在一个数组中，在这种情况下，

665
00:27:55,590 --> 00:28:00,550
有些武断，我画这
作为数组排序的哈希表

666
00:28:00,550 --> 00:28:02,810
两维数组 - 

667
00:28:02,810 --> 00:28:05,410
或者更确切地说，它这里描绘为两
维数组 - 但是这仅仅是

668
00:28:05,410 --> 00:28:10,770
大小为26的数组，例如，如果我们
调用数组桌，桌上托架

669
00:28:10,770 --> 00:28:12,440
零是在顶部的矩形。

670
00:28:12,440 --> 00:28:15,090
表托架25是矩形
在底部。

671
00:28:15,090 --> 00:28:18,620
我这是怎么可能画出一个数据
我想存储结构中，

672
00:28:18,620 --> 00:28:19,790
人的名字。

673
00:28:19,790 --> 00:28:24,370
>> 因此，举例来说，我不会画
整个事情上的开销，如果我

674
00:28:24,370 --> 00:28:29,160
该数组，我现在要
调用一个哈希表，这又是

675
00:28:29,160 --> 00:28:31,360
零的位置。

676
00:28:31,360 --> 00:28:34,840
这里是位置
一个，等等。

677
00:28:34,840 --> 00:28:37,880
我要求，我想用这个数据
结构，为了讨论的方便，

678
00:28:37,880 --> 00:28:42,600
存储人的名字，Alice和Bob
查理和其他类似的名称。

679
00:28:42,600 --> 00:28:46,110
所以，现在觉得这个作为起点
，也就是说，一个字典

680
00:28:46,110 --> 00:28:47,520
有很多的话。

681
00:28:47,520 --> 00:28:49,435
他们正好是名
在我们的例子。

682
00:28:49,435 --> 00:28:52,560
这是太有密切关系，也许，
实施一个拼写检查，因为我们

683
00:28:52,560 --> 00:28:54,400
可能问题设置6。

684
00:28:54,400 --> 00:28:59,300
>> 所以，如果我们有一个总规模26阵列
因此，这是第25的位置

685
00:28:59,300 --> 00:29:03,390
在底部，我要求爱丽丝
字典中的第一个字

686
00:29:03,390 --> 00:29:07,260
名，我想插入RAM，
到该数据结构中，其中

687
00:29:07,260 --> 00:29:12,480
爱丽丝的直觉告诉你，
在这个数组名称应该去？

688
00:29:12,480 --> 00:29:13,510
>> 我们有26个选项。

689
00:29:13,510 --> 00:29:14,990
如果我们想要把她吗？

690
00:29:14,990 --> 00:29:16,200
我们希望她在支架为零，对不对？

691
00:29:16,200 --> 00:29:18,280
为爱丽丝，我们称之为零。

692
00:29:18,280 --> 00:29:20,110
和B，和C将有两个。

693
00:29:20,110 --> 00:29:22,600
因此，我们打算写
爱丽丝的名字在这里。

694
00:29:22,600 --> 00:29:24,890
如果我们再插入鲍勃，他
名称会去这里。

695
00:29:24,890 --> 00:29:27,280
查理会去这里。

696
00:29:27,280 --> 00:29:30,500
如此反复向下
这样的数据结构。

697
00:29:30,500 --> 00:29:32,090
>> 这是一个美妙的数据结构。

698
00:29:32,090 --> 00:29:32,730
为什么呢？

699
00:29:32,730 --> 00:29:37,460
那么什么是运行时间
插入成这样的一个人的名字

700
00:29:37,460 --> 00:29:39,850
数据结构的权利吗？

701
00:29:39,850 --> 00:29:43,702
鉴于实施该表，
诚然，作为一个数组。

702
00:29:43,702 --> 00:29:44,940
那么它的恒定时间。

703
00:29:44,940 --> 00:29:45,800
这是一个顺序。

704
00:29:45,800 --> 00:29:46,360
为什么呢？

705
00:29:46,360 --> 00:29:48,630
>> 那么你如何确定
爱丽丝属于？

706
00:29:48,630 --> 00:29:51,000
你看看她的名字的信吗？

707
00:29:51,000 --> 00:29:51,490
第一。

708
00:29:51,490 --> 00:29:54,350
在那里，你可以得到，如果它是一个字符串，
只是看着串

709
00:29:54,350 --> 00:29:55,200
支架零。

710
00:29:55,200 --> 00:29:57,110
因此，第0个字符的字符串。

711
00:29:57,110 --> 00:29:57,610
这是很容易的。

712
00:29:57,610 --> 00:30:00,350
我们已在加密
分配星期前。

713
00:30:00,350 --> 00:30:05,310
然后，一旦你知道Alice的
字母是大写的A，我们可以减去

714
00:30:05,310 --> 00:30:08,160
关闭65或资本A本身，
这给了我们为零。

715
00:30:08,160 --> 00:30:10,940
因此，我们现在知道，爱丽丝属于
在零的位置。

716
00:30:10,940 --> 00:30:14,240
>> 和给定的一个指针，指向这个数据
某种结构，多久？

717
00:30:14,240 --> 00:30:18,840
它带我找到位置
阵列中的零？

718
00:30:18,840 --> 00:30:22,080
只需一个步骤，这是恒定的时间
由于随机接入中，我们

719
00:30:22,080 --> 00:30:23,780
建议的是一个数组的一个特征。

720
00:30:23,780 --> 00:30:28,570
因此，在短期，搞清楚什么索引
Alice的名字，这是在

721
00:30:28,570 --> 00:30:32,610
这种情况下，是A，或让刚刚解决
为零，其中B是C是

722
00:30:32,610 --> 00:30:34,900
二，计算出
是恒定的时间。

723
00:30:34,900 --> 00:30:38,510
我只是来看看她的第一个字母，
搞清楚其中零为

724
00:30:38,510 --> 00:30:40,460
数组也是恒定的时间。

725
00:30:40,460 --> 00:30:42,140
因此从技术上讲这是
像现在两个步骤。

726
00:30:42,140 --> 00:30:43,330
但是，这仍然不变。

727
00:30:43,330 --> 00:30:46,880
所以，我们称之为一大O，所以我们
爱丽丝插入到这个表中

728
00:30:46,880 --> 00:30:48,440
常量时间。

729
00:30:48,440 --> 00:30:50,960
>> 不过，当然，我
天真在这里，对不对？

730
00:30:50,960 --> 00:30:53,240
如果在课堂上有亚伦？

731
00:30:53,240 --> 00:30:53,990
还是艾丽西亚？

732
00:30:53,990 --> 00:30:57,230
或任何其他的名字开始
A.我们要去哪里放

733
00:30:57,230 --> 00:31:00,800
那人，对不对？

734
00:31:00,800 --> 00:31:03,420
我的意思是，现在只有三个
老百姓餐桌上，所以也许我们

735
00:31:03,420 --> 00:31:07,490
应该把亚伦的位置
零壹两三个。

736
00:31:07,490 --> 00:31:09,480
>> 好吧，我可以在这里把A。

737
00:31:09,480 --> 00:31:13,350
然而，如果我们尝试将大卫
这个名单，大卫去哪里？

738
00:31:13,350 --> 00:31:15,170
现在，我们的系统开始打破
向下，向右？

739
00:31:15,170 --> 00:31:19,210
因为现在，大卫在这里结束了
如果阿龙其实是在这里。

740
00:31:19,210 --> 00:31:23,060
所以现在有一个整体思路
干净的数据结构，让我们

741
00:31:23,060 --> 00:31:28,010
恒定的时间插入不再
恒定的时间，因为我有

742
00:31:28,010 --> 00:31:31,240
检查，哦，该死的，有人已经
在爱丽丝的位置。

743
00:31:31,240 --> 00:31:35,320
>> 让我探究这些数据的其余部分
结构，寻找一个位置把

744
00:31:35,320 --> 00:31:37,130
有人喜欢亚伦的名字。

745
00:31:37,130 --> 00:31:39,390
等也开始
线性时间。

746
00:31:39,390 --> 00:31:42,710
此外，如果你现在想找到
亚伦在此数据结构，你

747
00:31:42,710 --> 00:31:45,430
检查和亚伦的名字是不是在这里。

748
00:31:45,430 --> 00:31:47,960
理想情况下，你只说亚伦
而不是在数据结构中。

749
00:31:47,960 --> 00:31:51,530
但是，如果你开始做空间
亚伦那里应该有一个D

750
00:31:51,530 --> 00:31:55,600
或E，你最坏的情况下，有检查
整个数据结构，在

751
00:31:55,600 --> 00:31:59,480
这种情况下，移交到的东西
表的大小成线性关系。

752
00:31:59,480 --> 00:32:00,920
>> 所以所有的权利，我会解决这个问题。

753
00:32:00,920 --> 00:32:04,200
这里的问题是，我不得不
26此数组中元素。

754
00:32:04,200 --> 00:32:05,000
让我改变它。

755
00:32:05,000 --> 00:32:06,010
哎呀。

756
00:32:06,010 --> 00:32:10,600
让我改变它，因此而幸福
大小26个，发现底部

757
00:32:10,600 --> 00:32:12,720
指数将改变为n减1。

758
00:32:12,720 --> 00:32:16,610
如果26显然是太小了人类的
的名字，因为有成千上万的

759
00:32:16,610 --> 00:32:20,830
世界的名字，让我们使
在100或1000或10000。

760
00:32:20,830 --> 00:32:22,960
让我们只分配更多的空间。

761
00:32:22,960 --> 00:32:27,230
>> 嗯，这并不一定减少
的概率，我们不会有两个

762
00:32:27,230 --> 00:32:31,510
人们起的名字，
所以，你要尝试将

763
00:32:31,510 --> 00:32:33,120
名位置零。

764
00:32:33,120 --> 00:32:36,850
他们还在碰撞，
意味着我们仍然需要一个解决方案，把

765
00:32:36,850 --> 00:32:41,020
爱丽丝亚伦和艾丽西亚和其他
名开始与A别处。

766
00:32:41,020 --> 00:32:43,460
但多少的问题是什么？

767
00:32:43,460 --> 00:32:46,870
什么的概率
有碰撞在一个数据

768
00:32:46,870 --> 00:32:48,240
这样的结构？

769
00:32:48,240 --> 00:32:52,570
>> 好吧，让我 - 我们会回来的
这里这个问题。

770
00:32:52,570 --> 00:32:55,530
看我们如何可能
先解决它。

771
00:32:55,530 --> 00:32:58,480
让我拉起这个建议。

772
00:32:58,480 --> 00:33:02,020
我们刚刚描述的是一种算法，
一个启发式称为线性

773
00:33:02,020 --> 00:33:05,030
探测，即如果你试图插入
这里的东西在此数据

774
00:33:05,030 --> 00:33:08,920
结构，该结构被称为一个哈希表，
而且也没有的房间里，你

775
00:33:08,920 --> 00:33:12,000
真正探测的数据结构
检查，这是可用的？

776
00:33:12,000 --> 00:33:13,430
这是这是可用？

777
00:33:13,430 --> 00:33:13,980
这是？

778
00:33:13,980 --> 00:33:17,550
而当它终于插入
名字，你原本打算

779
00:33:17,550 --> 00:33:19,370
在该位置的其他地方。

780
00:33:19,370 --> 00:33:23,360
但是，在最坏的情况下，唯一的现货
可能是最底层的数据

781
00:33:23,360 --> 00:33:25,090
结构，数组的尽头。

782
00:33:25,090 --> 00:33:30,130
>> 因此，线性探测，在最坏的情况下，
下放成线性算法

783
00:33:30,130 --> 00:33:34,500
亚伦，如果他恰好是最后插入
这个数据结构中，他可能会

784
00:33:34,500 --> 00:33:39,540
碰撞，该第一位置，但
然后结束坏运气的最末尾。

785
00:33:39,540 --> 00:33:43,940
因此，这是不是一个常数
一次圣杯的我们。

786
00:33:43,940 --> 00:33:47,650
这种方法插入元素
一种数据结构，称为散列

787
00:33:47,650 --> 00:33:52,050
表不似乎是恒定的时间
至少不会在一般的情况下。

788
00:33:52,050 --> 00:33:54,000
它可以下放成线性的东西。

789
00:33:54,000 --> 00:33:56,970
>> 那么，如果我们解决冲突
有所不同呢？

790
00:33:56,970 --> 00:34:00,740
因此，这里是一个更复杂
仍然接近

791
00:34:00,740 --> 00:34:02,800
称为哈希表。

792
00:34:02,800 --> 00:34:05,890
哈希，顺便说一句，
我的意思是指数

793
00:34:05,890 --> 00:34:07,070
我前面提到的。

794
00:34:07,070 --> 00:34:09,810
哈希的东西可以
想到作为一个动词。

795
00:34:09,810 --> 00:34:13,690
>> 所以，如果你哈希爱丽丝一个名字，
哈希函数，可以这么说，

796
00:34:13,690 --> 00:34:14,710
应该返回一个数字。

797
00:34:14,710 --> 00:34:18,199
在这种情况下是零，如果她是属于
位置为零，如果她属于

798
00:34:18,199 --> 00:34:20,000
的位置，等等。

799
00:34:20,000 --> 00:34:24,360
所以，我的哈希函数迄今一直
超级简单，只看着

800
00:34:24,360 --> 00:34:26,159
在别人的名字的第一个字母。

801
00:34:26,159 --> 00:34:29,090
但是哈希函数需要
输入某些数据块，

802
00:34:29,090 --> 00:34:30,210
一个整数，字符串，等等。

803
00:34:30,210 --> 00:34:32,239
它吐出一个典型的数字。

804
00:34:32,239 --> 00:34:35,739
而且这个数字是该数据
在数据结构中的元素属于

805
00:34:35,739 --> 00:34:37,800
这里称为哈希表。

806
00:34:37,800 --> 00:34:41,400
>> 所以只是凭直觉，这是一个
略有不同的上下文中。

807
00:34:41,400 --> 00:34:44,170
这实际上是指一个例子
涉及的生日，

808
00:34:44,170 --> 00:34:46,850
可能有多达
31月份中的天。

809
00:34:46,850 --> 00:34:52,239
但是，什么人决定
做在发生碰撞时？

810
00:34:52,239 --> 00:34:55,304
上下文，而不是现在的碰撞
名，生日，而是碰撞

811
00:34:55,304 --> 00:35:00,760
如果两个人有相同的生日
10月2日，例如。

812
00:35:00,760 --> 00:35:02,120
>> 学生：[听不清]。

813
00:35:02,120 --> 00:35:05,010
>> 扬声器1：是啊，所以我们在这里有
利用链表。

814
00:35:05,010 --> 00:35:07,830
因此，它看起来有点不同
把它比我们更早。

815
00:35:07,830 --> 00:35:10,790
但是，我们似乎有一个数组
在左手侧。

816
00:35:10,790 --> 00:35:13,230
这是一个索引，因为没有
特别的原因。

817
00:35:13,230 --> 00:35:14,630
但它仍然是一个数组。

818
00:35:14,630 --> 00:35:16,160
这是一个数组的指针。

819
00:35:16,160 --> 00:35:20,670
每一元素，每个
这些圆圈或斜线 - 斜线

820
00:35:20,670 --> 00:35:23,970
代表空 - 这些
指针显然指向

821
00:35:23,970 --> 00:35:25,730
什么数据结构？

822
00:35:25,730 --> 00:35:26,890
链表。

823
00:35:26,890 --> 00:35:30,530
>> 所以，现在我们有能力
硬到我们的程序代码

824
00:35:30,530 --> 00:35:32,010
表的大小。

825
00:35:32,010 --> 00:35:35,360
在这种情况下，我们知道从未有
在一个月内超过31天。

826
00:35:35,360 --> 00:35:38,480
所以硬编码值，如31
在这种情况下合理。

827
00:35:38,480 --> 00:35:42,700
在名称的上下文中，硬编码
26是不讲理的人

828
00:35:42,700 --> 00:35:46,340
名字才开始，例如，
涉及A到Z的字母

829
00:35:46,340 --> 00:35:50,180
>> 我们可以塞进他们都到数据
只要结构，当我们得到一个

830
00:35:50,180 --> 00:35:55,330
碰撞，我们不把这里的名字，
我们反而认为，这些细胞

831
00:35:55,330 --> 00:36:00,270
不是字符串本身，而是作为
的指针，例如，爱丽丝。

832
00:36:00,270 --> 00:36:03,660
然后爱丽丝可以有另一个指针
另一个名字开始

833
00:36:03,660 --> 00:36:06,150
A.和鲍勃实际上是在这里。

834
00:36:06,150 --> 00:36:10,850
>> 如果有另一个名字开始
B，他结束了在这里。

835
00:36:10,850 --> 00:36:15,070
等各元素与该
表二，如果我们设计一个

836
00:36:15,070 --> 00:36:17,350
更巧妙一点 - 

837
00:36:17,350 --> 00:36:18,125
来吧 - 

838
00:36:18,125 --> 00:36:22,950
如果我们设计了这个多一点
巧妙的，现在变成了一个自适应数据

839
00:36:22,950 --> 00:36:27,720
结构，那里是没有硬性限制
你可以插入多少元素

840
00:36:27,720 --> 00:36:30,700
到它，因为如果你这样做有
碰撞，这很好。

841
00:36:30,700 --> 00:36:34,690
只要继续下去，并将它附加到
我们所看到的有点前

842
00:36:34,690 --> 00:36:38,290
被称为一个链表。

843
00:36:38,290 --> 00:36:39,690
>> 那么让我们来的暂停只是一瞬间。

844
00:36:39,690 --> 00:36:42,570
碰撞的概率是什么
摆在首位？

845
00:36:42,570 --> 00:36:45,480
对的，也许我过思考，也许
我在工程的这个问题，

846
00:36:45,480 --> 00:36:46,370
因为你知道是什么吗？

847
00:36:46,370 --> 00:36:49,070
是的，我可以拿出任意
关闭我的头顶部的例子喜欢

848
00:36:49,070 --> 00:36:52,870
Allison和亚伦，但在现实中，
给定的均匀分布

849
00:36:52,870 --> 00:36:56,990
投入，是一些随机插入
到一个数据结构，什么是真正的

850
00:36:56,990 --> 00:36:58,580
碰撞的概率？

851
00:36:58,580 --> 00:37:01,670
好吧原来，它实际上是
超高。

852
00:37:01,670 --> 00:37:03,850
让我概括
问题是这个。

853
00:37:03,850 --> 00:37:08,890
>> 因此，在一个房间里的n CS50学生，什么是
的概率，至少

854
00:37:08,890 --> 00:37:11,010
两名学生在房间里
有相同的生日吗？

855
00:37:11,010 --> 00:37:13,346
因此，有什么。几个洪德 - 

856
00:37:13,346 --> 00:37:16,790
200，300人在这里和几个
今天在家百余人。

857
00:37:16,790 --> 00:37:20,670
所以，如果你要问自己什么
两个人的概率

858
00:37:20,670 --> 00:37:23,930
在这个房间里有相同的生日，
我们可以弄清楚了这一点。

859
00:37:23,930 --> 00:37:26,250
其实我要求有两个
同一天生日的人。

860
00:37:26,250 --> 00:37:29,560
>> 举例来说，有没有人
今天生日吗？

861
00:37:29,560 --> 00:37:31,340
昨天？

862
00:37:31,340 --> 00:37:32,590
明天？

863
00:37:32,590 --> 00:37:35,980
所有的权利，所以感觉像我要去
不得不做这363左右

864
00:37:35,980 --> 00:37:39,500
次真正弄清楚
如果我们这样做，有碰撞。

865
00:37:39,500 --> 00:37:42,350
或者，我们可以做到这一点数学
而不是繁琐

866
00:37:42,350 --> 00:37:43,200
这样做。

867
00:37:43,200 --> 00:37:44,500
并提出以下建议。

868
00:37:44,500 --> 00:37:48,740
>> 所以，我建议，我们可以模拟
两个人的概率

869
00:37:48,740 --> 00:37:55,320
同一天生日的概率为1
减去的概率没有一个具有

870
00:37:55,320 --> 00:37:56,290
同一天生日。

871
00:37:56,290 --> 00:37:59,960
所以就弄这个，这只是
花哨的编写方式，

872
00:37:59,960 --> 00:38:03,090
在房间里的第一人，他或她
可以有任何其中一个可能的

873
00:38:03,090 --> 00:38:07,370
生日的一年，假设365天
与人道歉

874
00:38:07,370 --> 00:38:08,760
2月29日生日。

875
00:38:08,760 --> 00:38:13,470
>> 因此，在这个房间里的第一人免费
有任意数量的生日

876
00:38:13,470 --> 00:38:18,280
365的可能性，所以，
我们要做的，365除以365，

877
00:38:18,280 --> 00:38:18,990
这是其中之一。

878
00:38:18,990 --> 00:38:22,700
旁边的人在房间里，如果我们的目标
是为了避免碰撞时，也只能

879
00:38:22,700 --> 00:38:26,460
有他或她的生日就如何
许多不同的可能的天？

880
00:38:26,460 --> 00:38:27,610
364。

881
00:38:27,610 --> 00:38:31,430
所以这个表达式中的第二项是
基本上这样做对我们的数学

882
00:38:31,430 --> 00:38:33,460
通过减去一个可能的日子。

883
00:38:33,460 --> 00:38:36,390
然后第二天，第二天，
第二天下来的总数

884
00:38:36,390 --> 00:38:38,100
在房间里的人。

885
00:38:38,100 --> 00:38:41,290
>> 如果我们再考虑，又是什么
的概率不是人人有

886
00:38:41,290 --> 00:38:45,265
独特的生日，但1减去再次
，我们得到了什么是一个表达式

887
00:38:45,265 --> 00:38:47,810
可以很稀奇
这个样子。

888
00:38:47,810 --> 00:38:50,330
但它更有趣
看视觉。

889
00:38:50,330 --> 00:38:55,120
这是一个图表上的x轴
多少人在房间里，

890
00:38:55,120 --> 00:38:56,180
生日数。

891
00:38:56,180 --> 00:38:59,840
在y轴上的概率是
碰撞时，两个人

892
00:38:59,840 --> 00:39:01,230
具有相同的生日。

893
00:39:01,230 --> 00:39:05,020
>> 而从这个曲线是外卖
只要你喜欢40

894
00:39:05,020 --> 00:39:11,110
同学们，你们是在90％的概率
，combinatorically两个

895
00:39:11,110 --> 00:39:13,550
人或以上有
同一天生日。

896
00:39:13,550 --> 00:39:18,600
一旦你得到58人喜欢它的
几乎100％的机会两个

897
00:39:18,600 --> 00:39:21,310
房间里的人将不得不
同一天生日，即使有

898
00:39:21,310 --> 00:39:26,650
365或366个可能的桶，
只有58人在房间里。

899
00:39:26,650 --> 00:39:29,900
只是统计学，你很可能会
得到的碰撞，在短

900
00:39:29,900 --> 00:39:31,810
激励这个讨论。

901
00:39:31,810 --> 00:39:35,890
即使我们得到看中这里，
开始这些连锁，我们还是

902
00:39:35,890 --> 00:39:36,950
将有碰撞。

903
00:39:36,950 --> 00:39:42,710
>> 所以引出了一个问题，什么是
成本做插入和删除

904
00:39:42,710 --> 00:39:44,850
进入这样一个数据结构？

905
00:39:44,850 --> 00:39:46,630
那么让我提出 - 

906
00:39:46,630 --> 00:39:51,570
并让我回到屏幕上对
在这里 - 如果我们有n个元素

907
00:39:51,570 --> 00:39:56,330
列表，所以如果我们试图插入
n个元素，我们有

908
00:39:56,330 --> 00:39:58,050
总共有多少桶？

909
00:39:58,050 --> 00:40:03,450
比方说，共31桶
在的情况下的生日。

910
00:40:03,450 --> 00:40:09,240
什么是最大长度为一个
这些链可能？

911
00:40:09,240 --> 00:40:12,670
>> 如果再有31个可能
在一个给定月份的生日。

912
00:40:12,670 --> 00:40:14,580
我们只是聚集大家 - 

913
00:40:14,580 --> 00:40:15,580
实际上这是一个愚蠢的例子。

914
00:40:15,580 --> 00:40:16,960
让做26代替。

915
00:40:16,960 --> 00:40:20,890
因此，如果实际拥有人名列
从A到Z，从而使

916
00:40:20,890 --> 00:40:22,780
我们26的可能性。

917
00:40:22,780 --> 00:40:25,920
我们使用一个数据结构，如
我们刚才看到的，据此，我们有

918
00:40:25,920 --> 00:40:30,210
一个数组的指针，其中每个
指向一个链表地方的

919
00:40:30,210 --> 00:40:32,360
第一份清单是每个人都
爱丽丝的名字。

920
00:40:32,360 --> 00:40:35,770
第二个名单是每周与
命名开始，

921
00:40:35,770 --> 00:40:36,980
为B，依此类推。

922
00:40:36,980 --> 00:40:41,020
>> 什么可能各有长短
这些列表，如果我们假设一个干净的

923
00:40:41,020 --> 00:40:45,410
从A到Z的名称分配
在整个数据结构？

924
00:40:45,410 --> 00:40:50,210
有n个人的数据结构中
除以26，如果他们很好

925
00:40:50,210 --> 00:40:52,110
摊开在整个
的数据结构。

926
00:40:52,110 --> 00:40:54,970
因此，每个这些的长度
链为n除以26。

927
00:40:54,970 --> 00:40:57,380
但在大O表示法，那是什么？

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
什么是真的？

930
00:41:02,440 --> 00:41:04,150
所以这真的只是N，对不对？

931
00:41:04,150 --> 00:41:06,620
因为我们说，在过去，
唉你除以26。

932
00:41:06,620 --> 00:41:08,710
是的，在现实中，它是速度更快。

933
00:41:08,710 --> 00:41:12,720
但是，从理论上讲，它不能从根本上
所有的更快。

934
00:41:12,720 --> 00:41:16,040
>> 因此，我们不似乎是所有的东西
接近本圣杯。

935
00:41:16,040 --> 00:41:17,750
事实上，这仅仅是线性时间。

936
00:41:17,750 --> 00:41:20,790
哎呀，在这一点上，为什么我们不
只使用一个巨大的链表？

937
00:41:20,790 --> 00:41:23,510
为什么我们不只是用一个巨大的
数组来存储的名称

938
00:41:23,510 --> 00:41:25,010
每个人都在房间里吗？

939
00:41:25,010 --> 00:41:28,280
嗯，还有东西
引人注目的一个哈希表？

940
00:41:28,280 --> 00:41:30,810
还有一些引人注目的
关于数据结构的

941
00:41:30,810 --> 00:41:33,940
看起来像这样吗？

942
00:41:33,940 --> 00:41:35,182
此。

943
00:41:35,182 --> 00:41:37,050
>> 学生：[听不清]。

944
00:41:37,050 --> 00:41:39,840
>> 扬声器1：右键，并再次，如果它只是
一个线性时间算法，并有

945
00:41:39,840 --> 00:41:42,780
线性时间的数据结构，我为什么不
只是在一个大的存储每个人的名字

946
00:41:42,780 --> 00:41:44,210
阵列，或在一个大的链表？

947
00:41:44,210 --> 00:41:47,010
停止CS这么更难
比它需要的吗？

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
什么是引人注目的，甚至
虽然我划出来？

950
00:41:53,190 --> 00:41:54,930
>> 学生：[听不清]。

951
00:41:54,930 --> 00:41:57,040
>> 扬声器1：插入都没有？

952
00:41:57,040 --> 00:41:58,140
昂贵了。

953
00:41:58,140 --> 00:42:03,390
因此，插入可能仍然
时间是恒定的，即使你的数据

954
00:42:03,390 --> 00:42:07,910
结构看起来是这样的，琳琅满目的
指针，其中每个指向

955
00:42:07,910 --> 00:42:09,550
潜在的链表。

956
00:42:09,550 --> 00:42:15,220
你怎么能实现恒
时间插入的名字？

957
00:42:15,220 --> 00:42:16,280
把它贴在了前面，对不对？

958
00:42:16,280 --> 00:42:19,290
>> 如果我们牺牲一个设计目标
所说，我们希望保持

959
00:42:19,290 --> 00:42:22,650
每个人的名字，例如，排序，
舞台上所有的数字排序，

960
00:42:22,650 --> 00:42:25,020
假设我们有一个
未分类的链表。

961
00:42:25,020 --> 00:42:29,960
我们只需花费一个或两个步骤，
像Ben和布莱恩的情况下

962
00:42:29,960 --> 00:42:32,750
早些时候，插入一个元素
在列表的开头。

963
00:42:32,750 --> 00:42:36,090
因此，如果我们不关心排序的所有
开头的名字或全部

964
00:42:36,090 --> 00:42:39,660
以B开头的名字，我们仍然可以
实现恒定的时间插入。

965
00:42:39,660 --> 00:42:43,900
现在回头Alice或Bob或任何名称
更普遍的仍是什么？

966
00:42:43,900 --> 00:42:48,100
大O的n除以26，在
理想情况下，每个人的均匀

967
00:42:48,100 --> 00:42:51,190
分布，其中有尽可能多的
有Z的，这可能是

968
00:42:51,190 --> 00:42:52,220
不现实的。

969
00:42:52,220 --> 00:42:53,880
但是，这仍然是线性的。

970
00:42:53,880 --> 00:42:57,120
>> 但在这里，我们再回过头来点
渐近符号

971
00:42:57,120 --> 00:42:58,600
理论上确实如此。

972
00:42:58,600 --> 00:43:02,960
但在现实世界中，如果我要求
我的程序可以做一些26倍

973
00:43:02,960 --> 00:43:06,210
速度比你的，其程序
你要喜欢使用？

974
00:43:06,210 --> 00:43:09,660
你的还是我，
快26倍？

975
00:43:09,660 --> 00:43:14,320
实际上，人是26
倍的速度，即使在理论上

976
00:43:14,320 --> 00:43:18,790
我们的算法运行在相同的
渐近运行时间。

977
00:43:18,790 --> 00:43:20,940
>> 让我提出一个不同的
完全的解决方案。

978
00:43:20,940 --> 00:43:24,380
如果这不吹你的头脑，
我们的数据结构。

979
00:43:24,380 --> 00:43:27,420
因此，这是特里 - 

980
00:43:27,420 --> 00:43:28,520
样的一个愚蠢的名字。

981
00:43:28,520 --> 00:43:32,880
它来自检索，字
拼写特里，T-R-I-E，因为

982
00:43:32,880 --> 00:43:34,450
当然检索听起来像特里。

983
00:43:34,450 --> 00:43:36,580
但是，这是历史
的特里字。

984
00:43:36,580 --> 00:43:40,980
>> 因此，一个特里确实是某种树，
它也是一上场就那个字。

985
00:43:40,980 --> 00:43:46,330
即使你可以不太看到它
这个可视化，特里是一个

986
00:43:46,330 --> 00:43:50,790
树结构，就像一个家庭树
在顶部和意见的一个祖先

987
00:43:50,790 --> 00:43:54,530
孙子和重孙
离开底部。

988
00:43:54,530 --> 00:43:58,100
但特里在每个节点是一个数组。

989
00:43:58,100 --> 00:44:00,680
，它是在一个数组 - 让
过于简单化了一会儿 - 这是一个

990
00:44:00,680 --> 00:44:04,600
阵列，在这种情况下，大小为26，其中
每个节点是数组的大小为

991
00:44:04,600 --> 00:44:09,000
26的方法，其中在第零个元素
数组代表A，最后

992
00:44:09,000 --> 00:44:11,810
在每个这样的元素
数组代表Z。

993
00:44:11,810 --> 00:44:15,520
>> 所以，我建议，那么，这个数据
结构，称为一个特里，可

994
00:44:15,520 --> 00:44:17,600
也用于存储字。

995
00:44:17,600 --> 00:44:21,740
我们刚才也看到了，我们如何能够存储
的话，在这种情况下，名称，这样我们

996
00:44:21,740 --> 00:44:25,440
前面所看到的，我们如何能够存储数字，
但如果我们专注于名或字符串

997
00:44:25,440 --> 00:44:27,460
这里，发现什么有趣的。

998
00:44:27,460 --> 00:44:32,210
我要求麦克斯韦的名字是
内的这样的数据结构。

999
00:44:32,210 --> 00:44:33,730
你在哪里看到麦克斯韦？

1000
00:44:33,730 --> 00:44:35,140
>> 学生：[听不清]。

1001
00:44:35,140 --> 00:44:36,240
>> 扬声器1：在左边。

1002
00:44:36,240 --> 00:44:39,910
那么，有什么有趣的与此数据
而不是存储结构

1003
00:44:39,910 --> 00:44:46,200
串M-à-X-W-E-L-L反斜杠零，所有的
连续，就是你，而不是做

1004
00:44:46,200 --> 00:44:46,890
以下。

1005
00:44:46,890 --> 00:44:50,510
如果这是一个类似的数据结构的线索，
的每个节点又是一个数组，

1006
00:44:50,510 --> 00:44:54,650
，你想，你先存储麦克斯韦
指数和根的节点，所以

1007
00:44:54,650 --> 00:44:57,810
说话，最上面的节点，
右，所以在位置M，

1008
00:44:57,810 --> 00:44:59,160
大致可分为中间。

1009
00:44:59,160 --> 00:45:03,740
然后从那里，你遵循
一个子节点的指针，可以这么说。

1010
00:45:03,740 --> 00:45:06,150
所以家谱感，
你跟着它向下。

1011
00:45:06,150 --> 00:45:09,030
导致你到另一个节点
左边有，这是

1012
00:45:09,030 --> 00:45:10,540
只是另一个数组。

1013
00:45:10,540 --> 00:45:14,710
>> 然后，如果你想存储麦克斯韦，
你找到指针，表示

1014
00:45:14,710 --> 00:45:16,430
A，这是此人在这里。

1015
00:45:16,430 --> 00:45:17,840
然后你去到下一个节点。

1016
00:45:17,840 --> 00:45:20,100
和通知 - 这就是为什么图片的
有点自欺欺人 - 

1017
00:45:20,100 --> 00:45:21,990
这个节点看起来超级微小的。

1018
00:45:21,990 --> 00:45:26,050
但是，这样做的权利是Y和Z。
这只是笔者已截断

1019
00:45:26,050 --> 00:45:27,630
图片，让你实际上
看到的东西。

1020
00:45:27,630 --> 00:45:30,400
否则这幅画
将是巨大的宽。

1021
00:45:30,400 --> 00:45:36,180
所以，现在你的索引位置X，然后
W，然后E，那么L，L，然后有什么

1022
00:45:36,180 --> 00:45:37,380
这种好奇心？

1023
00:45:37,380 --> 00:45:41,250
>> 那么，如果我们正在使用这种新
采取有关如何存储中的字符串

1024
00:45:41,250 --> 00:45:44,500
数据结构，你仍然需要
基本上在数据核对

1025
00:45:44,500 --> 00:45:47,250
结构词语到此为止。

1026
00:45:47,250 --> 00:45:50,830
换句话说，这些节点中的每个节点
不知何故要记住，我们

1027
00:45:50,830 --> 00:45:53,500
后面其实所有这些指针
并留下一点点

1028
00:45:53,500 --> 00:45:58,370
面包屑的底部，在这里对本
结构示意M-à-X-W-E-L-L

1029
00:45:58,370 --> 00:46:00,230
确实这个数据结构中。

1030
00:46:00,230 --> 00:46:02,040
>> 因此，我们可能会做如下。

1031
00:46:02,040 --> 00:46:06,810
我们只是在图片中的每一个节点
锯有一个大小为27的数组。

1032
00:46:06,810 --> 00:46:10,550
它现在27，因为在p设置6个，
实际上，我们就会给你一个撇号，

1033
00:46:10,550 --> 00:46:13,590
所以我们可以有名称，如奥赖利
和其他带撇号。

1034
00:46:13,590 --> 00:46:14,820
但同样的想法。

1035
00:46:14,820 --> 00:46:17,710
在这些元素
阵列指向一个struct

1036
00:46:17,710 --> 00:46:19,320
节点，所以只是一个节点。

1037
00:46:19,320 --> 00:46:21,430
因此，这很容易让人想起
我们的链表。

1038
00:46:21,430 --> 00:46:24,550
>> 然后我有一个布尔值，我将
致电字，这是只是要

1039
00:46:24,550 --> 00:46:29,120
如此，如果一个词结束
树中的节点。

1040
00:46:29,120 --> 00:46:32,870
它有效地代表小
三角形，我们刚才也看到了。

1041
00:46:32,870 --> 00:46:37,190
因此，如果有一个字在该节点处结束
树，那田字是真实的，

1042
00:46:37,190 --> 00:46:41,990
在概念上被检查过，或
我们绘制这个三角形，是有

1043
00:46:41,990 --> 00:46:44,080
这里是一个字。

1044
00:46:44,080 --> 00:46:45,120
>> 所以这是一个特里。

1045
00:46:45,120 --> 00:46:48,540
现在的问题是，什么
是它的运行时间？

1046
00:46:48,540 --> 00:46:49,930
它是大O的n？

1047
00:46:49,930 --> 00:46:51,410
是别的原因呢？

1048
00:46:51,410 --> 00:46:57,330
好吧，如果你有n个名字，在此数据
结构，麦克斯韦只是其中之一

1049
00:46:57,330 --> 00:47:02,330
他们，什么是运行时间
插入或找到马克斯韦尔？

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
什么是运行时间
插入麦克斯韦？

1052
00:47:09,050 --> 00:47:11,740
如果有n其他名称
已经在表中？

1053
00:47:11,740 --> 00:47:12,507
是吗？

1054
00:47:12,507 --> 00:47:15,429
>> 学生：[听不清]。

1055
00:47:15,429 --> 00:47:17,550
>> 扬声器1：是的，它的长度
的名字，对不对？

1056
00:47:17,550 --> 00:47:24,420
所以M-A-X-W-E-L-L，所以这样的感觉
算法是大O七。

1057
00:47:24,420 --> 00:47:26,580
现在，当然，该名称
将长短不一。

1058
00:47:26,580 --> 00:47:27,380
也许这是一个简短的名称。

1059
00:47:27,380 --> 00:47:28,600
也许这是一个较长的名称。

1060
00:47:28,600 --> 00:47:33,390
但这里的关键是，
这是一个常数。

1061
00:47:33,390 --> 00:47:36,810
也许这不是真的不变，
不过神来，如果实事求是，在

1062
00:47:36,810 --> 00:47:41,570
字典里，可能有一些限制
中的字母的数目

1063
00:47:41,570 --> 00:47:43,820
在某个特定国家的人的名字。

1064
00:47:43,820 --> 00:47:46,940
>> 因此，我们可以假设，
值是一个常数。

1065
00:47:46,940 --> 00:47:47,750
我不知道它是什么。

1066
00:47:47,750 --> 00:47:50,440
这也可能是大于
我们认为它是。

1067
00:47:50,440 --> 00:47:52,720
因为总有一些角落
一个疯狂的长名称的情况。

1068
00:47:52,720 --> 00:47:56,360
因此，让我们叫它K表，但它仍然是一个
常数，大概，因为每一个

1069
00:47:56,360 --> 00:48:00,190
命名在世界上，至少在
特定的国家，该长度或

1070
00:48:00,190 --> 00:48:01,780
短，所以它是恒定的。

1071
00:48:01,780 --> 00:48:04,490
但是，当我们已经说了一句大
O的一个恒定值，那是什么

1072
00:48:04,490 --> 00:48:07,760
真的等同吗？

1073
00:48:07,760 --> 00:48:10,420
这真的是同一件事
说恒定的时间。

1074
00:48:10,420 --> 00:48:11,530
>> 现在，我们是一种欺骗，对吧？

1075
00:48:11,530 --> 00:48:15,340
我们利用一些理论
这里要说的是，订单的k

1076
00:48:15,340 --> 00:48:17,450
真的只是为了一个，
和它的持续时间。

1077
00:48:17,450 --> 00:48:18,200
但它确实是。

1078
00:48:18,200 --> 00:48:22,550
因为这里的关键洞察力是
如果我们有n个名字已经在这

1079
00:48:22,550 --> 00:48:26,010
数据结构，我们插入麦克斯韦
是需要我们的时间量

1080
00:48:26,010 --> 00:48:29,530
在所有受影响的插入麦克斯韦
有多少人

1081
00:48:29,530 --> 00:48:31,100
在数据结构中？

1082
00:48:31,100 --> 00:48:31,670
似乎不。

1083
00:48:31,670 --> 00:48:36,280
如果我有一个10亿多元素
特里，然后插入麦克斯韦，

1084
00:48:36,280 --> 00:48:38,650
他在所有受影响？

1085
00:48:38,650 --> 00:48:39,050
号

1086
00:48:39,050 --> 00:48:42,950
而这不同于任何一天的数据
结构到目前为止，我们已经看到，其中

1087
00:48:42,950 --> 00:48:46,820
你的算法的运行时间是
完全独立的多少

1088
00:48:46,820 --> 00:48:51,430
东西已经是或不是
在该数据结构中。

1089
00:48:51,430 --> 00:48:54,650
>> 因此，与这提供了你现在是一个
机会对p六集，这将

1090
00:48:54,650 --> 00:48:58,310
再次涉及实施自己的
拼写检查器，读入150,000

1091
00:48:58,310 --> 00:49:01,050
的话，如何最有效地存储，
不一定是显而易见的。

1092
00:49:01,050 --> 00:49:04,030
虽然我渴望找到
圣杯，我不

1093
00:49:04,030 --> 00:49:05,330
声称，特里。

1094
00:49:05,330 --> 00:49:09,810
事实上，一个哈希表，很可能
被证明是更有效的。

1095
00:49:09,810 --> 00:49:10,830
但那些只是 - 

1096
00:49:10,830 --> 00:49:14,620
这只是一个设计决策
你将不得不作出。

1097
00:49:14,620 --> 00:49:18,920
>> 但在收盘让我们50岁左右
秒采取偷看是什么样的

1098
00:49:18,920 --> 00:49:22,190
下周提前超出了我们的过渡
从这个命令行

1099
00:49:22,190 --> 00:49:26,220
世界上，如果C程序网络的事情
基于语言，如PHP，

1100
00:49:26,220 --> 00:49:30,350
JavaScript和互联网本身，
协议，如HTTP，你

1101
00:49:30,350 --> 00:49:32,870
理所当然的多年
现在，类型最

1102
00:49:32,870 --> 00:49:34,440
一天，也许，或可见一斑。

1103
00:49:34,440 --> 00:49:37,420
我们将开始剥开
层是什么是互联网。

1104
00:49:37,420 --> 00:49:40,650
什么是代码，
今天的基础工具。

1105
00:49:40,650 --> 00:49:43,230
所以，50秒这个传情。

1106
00:49:43,230 --> 00:49:46,570
我给你的净勇士。

1107
00:49:46,570 --> 00:49:51,370
>> [视频回放]

1108
00:49:51,370 --> 00:49:56,764
>> 他带来一个消息。

1109
00:49:56,764 --> 00:50:00,687
有了自己的协议。

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
他来到世界残忍防火墙，
漠不关心的路由器和危险远

1112
00:50:19,780 --> 00:50:22,600
比死亡更糟糕。

1113
00:50:22,600 --> 00:50:23,590
他的速度快。

1114
00:50:23,590 --> 00:50:25,300
他很强壮。

1115
00:50:25,300 --> 00:50:27,700
他的TCPIP。

1116
00:50:27,700 --> 00:50:30,420
他有你的地址。

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
勇士净。

1119
00:50:34,590 --> 00:50:35,290
>> [END视频播放]

1120
00:50:35,290 --> 00:50:38,070
>> 扬声器1：这是如何在互联网上
应下周工作。

1121
00:50:38,070 --> 00:50:40,406