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
のは、4つのそれぞれについてお話しましょう
データ構造の主な種類

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
>> 配列の最後に挿入はOKですが、
私たちが行くように、私たちは、アレイを構築している場合。

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
私達はちょうど7言うと、私達は行きます
・アレイ再配置7へ。

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
私たちはそれだけで1ショットを取得。

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
ポインタを変更され、
おそらく2あなたが持っている場合

75
00:03:12,830 --> 00:03:15,151
二重list--リンク
リンクリスト、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
あなたはちょうど2つのポインタを変更し、
そのためには、かなり速いです。

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
それは、2段階のプロセスです。

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または1,000以上、それを分割

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の1リンクリストの。

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
あなただけ保存するつもりなら
あなたのハッシュテーブルの5つの要素、

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
NULLポインタに遭遇すること、の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
だからあなたのすべてのデータがある場合
5文字の文字列、

166
00:07:19,924 --> 00:07:22,590
たとえば、5を保存しています
あなたのトライの文字列、

167
00:07:22,590 --> 00:07:25,439
それが唯一の5つのステップを取ります
あなたが探しているものを見つけます。

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