1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD：所以在CS50，我们已经介绍
大量不同的数据结构，

3
00:00:08,300 --> 00:00:09,180
对？

4
00:00:09,180 --> 00:00:11,420
我们已经看到阵列和链接
列表和哈希表，

5
00:00:11,420 --> 00:00:15,210
和尝试，堆栈和队列。

6
00:00:15,210 --> 00:00:17,579
我们还学了一点
关于树和堆，

7
00:00:17,579 --> 00:00:20,120
但实际上这些都只是结束
了是变化的一个主题。

8
00:00:20,120 --> 00:00:22,840
真的有这些
样的四个基本思路

9
00:00:22,840 --> 00:00:25,190
这一切可以归结为。

10
00:00:25,190 --> 00:00:28,150
数组，链表，
哈希表，和尝试。

11
00:00:28,150 --> 00:00:30,720
就像我说的，有
一些变化在他们身上，

12
00:00:30,720 --> 00:00:32,720
但是这是非常
多去总结

13
00:00:32,720 --> 00:00:38,140
一切，我们要谈
有关本类C的条件

14
00:00:38,140 --> 00:00:40,140
>> 但如何做这些所有的措施了，对不对？

15
00:00:40,140 --> 00:00:44,265
我们已经讨论过的利弊
每对他们单独的视频中，

16
00:00:44,265 --> 00:00:46,390
但有很多数字
越来越抛来抛去。

17
00:00:46,390 --> 00:00:48,723
有很多的一般
想法得到抛来抛去。

18
00:00:48,723 --> 00:00:51,950
让我们尝试和巩固
它变成一个地方。

19
00:00:51,950 --> 00:00:55,507
让我们权衡利弊反对
的利弊，并考虑

20
00:00:55,507 --> 00:00:57,340
该数据结构
可能是正确的数据

21
00:00:57,340 --> 00:01:01,440
结构特定的情形，
什么样的数据要存储。

22
00:01:01,440 --> 00:01:06,625
你不一定总是需要
使用超快速插入，删除，

23
00:01:06,625 --> 00:01:10,761
和查找一个线索的，如果你真的
不在乎插入和删除

24
00:01:10,761 --> 00:01:11,260
太多。

25
00:01:11,260 --> 00:01:13,968
如果你只需要快速随机
访问，也许一个数组更好。

26
00:01:13,968 --> 00:01:15,340
因此，让我们提炼出。

27
00:01:15,340 --> 00:01:18,530
让我们来谈谈四个的
主要类型的数据结构的

28
00:01:18,530 --> 00:01:21,720
我们已经谈到，和
刚看的时候，他们可能是很好的，

29
00:01:21,720 --> 00:01:23,340
当他们也许不会这么好。

30
00:01:23,340 --> 00:01:24,610
所以，让我们开始阵列。

31
00:01:24,610 --> 00:01:27,300
所以插入，这是一种不好的。

32
00:01:27,300 --> 00:01:31,350
>> 在插入数组的结束是确定的，
如果我们建立一个数组，因为我们去。

33
00:01:31,350 --> 00:01:33,570
但是，如果我们需要插入
元素融入到中间，

34
00:01:33,570 --> 00:01:35,550
回想起插入
排序，有很多

35
00:01:35,550 --> 00:01:37,510
中移动在那里，以适应一个元素。

36
00:01:37,510 --> 00:01:41,170
所以，如果我们要插入
任何地方，但一个数组的末尾，

37
00:01:41,170 --> 00:01:43,590
这可能不是那么大。

38
00:01:43,590 --> 00:01:46,710
>> 同样，删除，除非我们
删除从阵列的端部，

39
00:01:46,710 --> 00:01:49,810
恐怕也没有那么大，如果
我们不想留出空白的差距，

40
00:01:49,810 --> 00:01:50,790
通常我们不知道。

41
00:01:50,790 --> 00:01:54,700
我们要删除的元素，
那么几分使其再次贴身。

42
00:01:54,700 --> 00:01:57,670
因此删除从要素
一个数组，也没有那么大。

43
00:01:57,670 --> 00:01:58,820
>> 查找，虽然是很大的。

44
00:01:58,820 --> 00:02:00,920
我们有随机访问，
恒定的时间查找。

45
00:02:00,920 --> 00:02:03,800
我们只是说有七个，我们走
阵列搬迁七人。

46
00:02:03,800 --> 00:02:05,907
我们说20，与进入
阵列搬迁20。

47
00:02:05,907 --> 00:02:07,240
我们没有迭代的对面。

48
00:02:07,240 --> 00:02:08,630
这是相当不错的。

49
00:02:08,630 --> 00:02:11,020
>> 阵列也比较容易进行排序。

50
00:02:11,020 --> 00:02:14,040
我们谈了排序每次
算法，如选择排序​​，

51
00:02:14,040 --> 00:02:18,820
插入排序，冒泡排序，合并
排序，我们总是用数组来做到这一点，

52
00:02:18,820 --> 00:02:21,860
因为数组是很容易
排序，相对于所述的数据结构

53
00:02:21,860 --> 00:02:22,970
我们已经看到了这么远。

54
00:02:22,970 --> 00:02:24,320
>> 他们也比较小。

55
00:02:24,320 --> 00:02:25,695
这里没有很多额外的空间。

56
00:02:25,695 --> 00:02:29,210
你只留出完全一样多的
因为你需要把你的数据，

57
00:02:29,210 --> 00:02:30,320
而这几乎是它。

58
00:02:30,320 --> 00:02:33,180
因此，他们是非常小
而高效的方式。

59
00:02:33,180 --> 00:02:36,000
但另一个缺点，不过，
是，它们被固定在尺寸。

60
00:02:36,000 --> 00:02:38,630
我们必须明确的声明如何
大，我们希望我们的阵是，

61
00:02:38,630 --> 00:02:39,940
我们只有一次机会吧。

62
00:02:39,940 --> 00:02:41,280
我们不能增大和缩小它。

63
00:02:41,280 --> 00:02:44,582
>> 如果我们需要扩大或缩小它，我们
需要声明一个全新的阵列，

64
00:02:44,582 --> 00:02:47,750
复制所有的元素
第一阵列到第二阵列。

65
00:02:47,750 --> 00:02:51,410
如果我们失算了
的时候，我们需要再次做到这一点。

66
00:02:51,410 --> 00:02:52,760
没有那么大。

67
00:02:52,760 --> 00:02:58,750
所以数组不给我们的灵活性
有元素的变量的号码。

68
00:02:58,750 --> 00:03:01,320
>> 用一个链表，
插入是很容易的。

69
00:03:01,320 --> 00:03:03,290
我们只是钉到前。

70
00:03:03,290 --> 00:03:04,892
删除也非常的方便。

71
00:03:04,892 --> 00:03:06,100
我们必须找到的元素。

72
00:03:06,100 --> 00:03:07,270
这涉及到一些搜索。

73
00:03:07,270 --> 00:03:10,270
>> 但是，一旦你找到了元
你要找的，所有你需要做的

74
00:03:10,270 --> 00:03:12,830
是改变一个指针，
可能是两个，如果你有

75
00:03:12,830 --> 00:03:15,151
链接列表中 - 一个双
链表，rather--

76
00:03:15,151 --> 00:03:16,650
然后你可以自由的节点。

77
00:03:16,650 --> 00:03:18,399
你没有转移
周围的一切。

78
00:03:18,399 --> 00:03:22,090
你只需要改变两个指针，
所以这是相当快。

79
00:03:22,090 --> 00:03:23,470
>> 查找不好，虽然，对不对？

80
00:03:23,470 --> 00:03:26,280
为了让我们能够找到一个
在一个链表中的元素，

81
00:03:26,280 --> 00:03:29,154
无论是单独或双重链接，
我们必须线性搜索。

82
00:03:29,154 --> 00:03:32,320
我们必须开始在开始和
移动端，或开始在年底招

83
00:03:32,320 --> 00:03:33,860
到开始处。

84
00:03:33,860 --> 00:03:35,474
我们没有随机访问了。

85
00:03:35,474 --> 00:03:37,265
因此，如果我们做一个
大量的搜索，也许

86
00:03:37,265 --> 00:03:39,830
链表是不
对我们这么好。

87
00:03:39,830 --> 00:03:43,750
>> 他们也很
难以理清，对不对？

88
00:03:43,750 --> 00:03:45,666
只有这样，你可以
真正排序链表

89
00:03:45,666 --> 00:03:47,870
是排序为你构建它。

90
00:03:47,870 --> 00:03:50,497
但是，如果你解决它，你
构造它，你不再

91
00:03:50,497 --> 00:03:51,830
进行快速插入了。

92
00:03:51,830 --> 00:03:53,746
你不只是套结
东西到前。

93
00:03:53,746 --> 00:03:55,710
你必须找到
合适的地方把它，

94
00:03:55,710 --> 00:03:57,820
然后你插
变得几乎一样糟糕

95
00:03:57,820 --> 00:03:59,390
作为插入到一个数组。

96
00:03:59,390 --> 00:04:03,130
所以链表不
因此非常适合对数据进行排序。

97
00:04:03,130 --> 00:04:05,830
>> 他们还非常小，大小明智的。

98
00:04:05,830 --> 00:04:08,496
双链表略
比单链表较大，

99
00:04:08,496 --> 00:04:10,620
这是稍大
比阵列，但它不是

100
00:04:10,620 --> 00:04:13,330
大量的空间浪费。

101
00:04:13,330 --> 00:04:18,730
因此，如果空间是非常宝贵的，但
不是一个真正的激烈的溢价，

102
00:04:18,730 --> 00:04:22,180
这可能是正确的道路要走。

103
00:04:22,180 --> 00:04:23,330
>> 哈希表。

104
00:04:23,330 --> 00:04:25,850
插入到哈希表
是相当简单的。

105
00:04:25,850 --> 00:04:26,980
它是一个两步过程。

106
00:04:26,980 --> 00:04:30,700
首先，我们需要通过运行自己的数据
散列函数以获得散列码，

107
00:04:30,700 --> 00:04:37,550
然后我们插入元素插入
哈希表在这个哈希码位置。

108
00:04:37,550 --> 00:04:40,879
>> 缺失，类似于链表，
很容易，一旦你找到的元素。

109
00:04:40,879 --> 00:04:43,170
你必须先找到它，
但是当你删除它，

110
00:04:43,170 --> 00:04:45,128
你只需要更换
一对夫妇的指针，

111
00:04:45,128 --> 00:04:47,250
如果你使用的是单独的链接。

112
00:04:47,250 --> 00:04:49,942
如果你使用的探测，
或者如果你不

113
00:04:49,942 --> 00:04:51,650
使用链接在所有
在哈希表，

114
00:04:51,650 --> 00:04:53,040
缺失其实是很容易的。

115
00:04:53,040 --> 00:04:57,134
所有你需要做的是哈希
数据，然后去那个位置。

116
00:04:57,134 --> 00:04:58,925
假设你不
有任何冲突，

117
00:04:58,925 --> 00:05:01,650
你就可以很快删除。

118
00:05:01,650 --> 00:05:04,930
>> 现在，查找是那里的东西
变得有点复杂。

119
00:05:04,930 --> 00:05:06,910
它是在平均水平
比链表。

120
00:05:06,910 --> 00:05:09,560
如果您使用的是链接，
你还有一个链表，

121
00:05:09,560 --> 00:05:13,170
这意味着你仍然有
搜索有损链表。

122
00:05:13,170 --> 00:05:18,390
但是，因为你把你的链接
列表，将其分割在100或1000

123
00:05:18,390 --> 00:05:25,380
或N在哈希表的元素，你
链表都是一个第n的大小。

124
00:05:25,380 --> 00:05:27,650
他们都小得多。

125
00:05:27,650 --> 00:05:32,080
您有n个链接列表，而不是
大小n的一个链表。

126
00:05:32,080 --> 00:05:34,960
>> 所以这个真实世界的不变
因素，一般我们

127
00:05:34,960 --> 00:05:39,730
不要谈论时间的复杂性，
没有真正发挥作用在这里。

128
00:05:39,730 --> 00:05:43,020
所以查找仍然是线性的
如果你使用的链接进行搜索，

129
00:05:43,020 --> 00:05:46,780
但该列表的长度
您正在搜索通过

130
00:05:46,780 --> 00:05:50,080
很相比之下很短。

131
00:05:50,080 --> 00:05:52,995
再次，如果排序是你的
目标这里，哈希表的

132
00:05:52,995 --> 00:05:54,370
可能不是正确的道路要走。

133
00:05:54,370 --> 00:05:56,830
只需使用一个数组，如果排序
对你真的很重要。

134
00:05:56,830 --> 00:05:58,590
>> 他们可以运行大小的色域。

135
00:05:58,590 --> 00:06:01,640
这是很难说是否
哈希表是大或小，

136
00:06:01,640 --> 00:06:04,110
因为它实际上取决于
你有多大的哈希表。

137
00:06:04,110 --> 00:06:07,340
如果你只打算将存储
在哈希表五行，

138
00:06:07,340 --> 00:06:10,620
和你有一个哈希表
在这10,000个元素，

139
00:06:10,620 --> 00:06:12,614
你可能会浪费了很多空间。

140
00:06:12,614 --> 00:06:15,030
作为对比，你也可以
具有非常紧凑的哈希表，

141
00:06:15,030 --> 00:06:18,720
但较小的哈希表得到，
每个那些链表的长

142
00:06:18,720 --> 00:06:19,220
得到。

143
00:06:19,220 --> 00:06:22,607
所以真的没有办法定义
完全是一个哈希表的大小，

144
00:06:22,607 --> 00:06:24,440
但它可能是安全的
说这是一般

145
00:06:24,440 --> 00:06:27,990
将是大于链接的
列表存储相同的数据，

146
00:06:27,990 --> 00:06:30,400
但是比线索更小。

147
00:06:30,400 --> 00:06:32,720
>> 并试图列第四
这些结构的

148
00:06:32,720 --> 00:06:34,070
我们一直在谈论。

149
00:06:34,070 --> 00:06:36,450
插入到一个线索是复杂的。

150
00:06:36,450 --> 00:06:38,400
有很多动态
存储器分配，

151
00:06:38,400 --> 00:06:40,780
尤其是在开始时，
因为你开始建立。

152
00:06:40,780 --> 00:06:43,700
但它的恒定时间。

153
00:06:43,700 --> 00:06:47,690
这只是人为因素
在这里，可以很棘手。

154
00:06:47,690 --> 00:06:53,250
说完就遇到空指针，的malloc
空间，去那里，可能的malloc空间

155
00:06:53,250 --> 00:06:54,490
从那里了。

156
00:06:54,490 --> 00:06:58,880
的威胁因子排序
在动态内存分配指针

157
00:06:58,880 --> 00:07:00,130
是的障碍清除。

158
00:07:00,130 --> 00:07:04,550
但是，一旦你清除它，插入
其实说到很简单，

159
00:07:04,550 --> 00:07:06,810
而且可以肯定的是恒定的时间。

160
00:07:06,810 --> 00:07:07,680
>> 删除很容易。

161
00:07:07,680 --> 00:07:11,330
所有你需要做的就是导航下来
夫妇指针和自由节点，

162
00:07:11,330 --> 00:07:12,420
所以这是相当不错的。

163
00:07:12,420 --> 00:07:13,930
查找也非常快。

164
00:07:13,930 --> 00:07:16,780
它只是基于
长度的数据。

165
00:07:16,780 --> 00:07:19,924
所以，如果您的所有数据是
五个字符的字符串，

166
00:07:19,924 --> 00:07:22,590
例如，你存储5
在线索字符串，

167
00:07:22,590 --> 00:07:25,439
只需要五个步骤
找到你要找的东西。

168
00:07:25,439 --> 00:07:28,480
五是只是一个常数因子，因此
再次，插入，缺失，和查找

169
00:07:28,480 --> 00:07:31,670
这里都是固定的时间，有效。

170
00:07:31,670 --> 00:07:34,880
>> 另一件事是，你的线索是
其实那种已经排序，对吧？

171
00:07:34,880 --> 00:07:36,800
凭借我们如何是
插入元素，

172
00:07:36,800 --> 00:07:40,060
由信去信
键，或数字通过钥匙位，

173
00:07:40,060 --> 00:07:45,084
通常情况下，你的线索最终被
种排序为您打造它。

174
00:07:45,084 --> 00:07:47,250
它并没有真正使
有意义的思考整理

175
00:07:47,250 --> 00:07:49,874
以同样的方式，我们考虑
它使用数组或链表，

176
00:07:49,874 --> 00:07:51,070
或哈希表。

177
00:07:51,070 --> 00:07:54,780
但在某种意义上，你
当您去线索进行排序。

178
00:07:54,780 --> 00:07:58,630
>> 当然，不利的一面，是
一个线索迅速变得巨大。

179
00:07:58,630 --> 00:08:02,970
从每一个结点，你可能
have--如果你的密钥由数字，

180
00:08:02,970 --> 00:08:04,880
你有其他10个
地方可以去，哪些

181
00:08:04,880 --> 00:08:07,490
意味着每个节点
包含的信息

182
00:08:07,490 --> 00:08:11,440
有关数据要存储
在该节点处，加10的指针。

183
00:08:11,440 --> 00:08:14,430
其中，在CS50的IDE，为80个字节。

184
00:08:14,430 --> 00:08:17,220
所以这是至少80个字节
您创建的每个节点，

185
00:08:17,220 --> 00:08:19,240
而这还没有算上数据。

186
00:08:19,240 --> 00:08:24,950
如果你的节点
字母代替数字，

187
00:08:24,950 --> 00:08:27,825
现在你有26球
从每一个位置。

188
00:08:27,825 --> 00:08:32,007
而26倍8大概是200
字节，或者类似的东西。

189
00:08:32,007 --> 00:08:33,840
你有资本
和lowercase--可以

190
00:08:33,840 --> 00:08:35,381
看到我要与这一点，对不对？

191
00:08:35,381 --> 00:08:37,500
您的节点​​可以得到真正
大，所以线索

192
00:08:37,500 --> 00:08:40,470
本身，总体而言，可以
得到真正的大了。

193
00:08:40,470 --> 00:08:42,630
因此，如果空间是在一个较高的
您的系统上的溢价，

194
00:08:42,630 --> 00:08:45,830
一个线索可能不是正确的方式
走，即使它的其他好处

195
00:08:45,830 --> 00:08:47,780
开始发挥作用。

196
00:08:47,780 --> 00:08:48,710
我是道格·劳埃德。

197
00:08:48,710 --> 00:08:50,740
这是CS50。

198
00:08:50,740 --> 00:08:52,316