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