1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[音楽再生]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1：すべての権利。

5
00:00:12,900 --> 00:00:14,600
誰もがセクションに戻って歓迎しています。

6
00:00:14,600 --> 00:00:18,660
私はあなたのすべてが正常であることを望む
あなたのクイズから回収

7
00:00:18,660 --> 00:00:19,510
先週から。

8
00:00:19,510 --> 00:00:22,564
私はそれが時には少しクレイジーだ知っている。

9
00:00:22,564 --> 00:00:25,230
あなたがいるなら、私は、前に言っていたように
標準偏差内、

10
00:00:25,230 --> 00:00:28,188
本当に、特に、それについて心配しないでください
あまり快適セクションの。

11
00:00:28,188 --> 00:00:30,230
それはあなたがどこにあるべきかについてです。

12
00:00:30,230 --> 00:00:32,850
>> あなたは素晴らしいやったならば、素晴らしい。

13
00:00:32,850 --> 00:00:33,650
あなたに賛辞。

14
00:00:33,650 --> 00:00:36,149
そして、あなたが必要とするように感じる場合は、
もう少し助け、お願い致します

15
00:00:36,149 --> 00:00:38,140
到達して自由に感じる
TFのいずれかに出。

16
00:00:38,140 --> 00:00:40,030
私達は助けるために、すべてここにある。

17
00:00:40,030 --> 00:00:40,960
>> 私たちは教える理由です。

18
00:00:40,960 --> 00:00:44,550
私はあなたのためにここに毎週月曜日だ理由です
木曜の男とオフィスで時間。

19
00:00:44,550 --> 00:00:48,130
だから、私に知らせて自由に感じなさい
あなたは何を心配しているなら

20
00:00:48,130 --> 00:00:52,450
か何かがクイズであるかどう
ことをあなたは本当に対処したいと思います。

21
00:00:52,450 --> 00:00:56,940
>> だから、今日の議題は、
すべてのデータ構造に関する。

22
00:00:56,940 --> 00:01:01,520
これらのいくつかはちょうどになるだろうしている
あなたはこれらに慣れ取得します。

23
00:01:01,520 --> 00:01:04,870
あなたは今まで実装しない場合があります
このクラスの彼ら。

24
00:01:04,870 --> 00:01:08,690
そのうちのいくつかはあなたが意志、
あなたのスペルチェックのPSET用のような。

25
00:01:08,690 --> 00:01:11,380
>> あなたは、あなたの選択があるでしょう
ハッシュテーブルと試行の間。

26
00:01:11,380 --> 00:01:13,680
だから我々は間違いなく、これらの上に行くことがあります。

27
00:01:13,680 --> 00:01:18,690
それは一種の間違いなく、よりになるだろう
しかしハイレベル区間今日の、

28
00:01:18,690 --> 00:01:22,630
それらの多くがあるので、とIF
我々は実装の詳細に入った

29
00:01:22,630 --> 00:01:26,490
これらのすべてで、私たちはないだろう
でも、リンクされたリストを介して取得

30
00:01:26,490 --> 00:01:28,520
多分ハッシュテーブルの少し。

31
00:01:28,520 --> 00:01:31,200
>> だから、私と一緒に負担する。

32
00:01:31,200 --> 00:01:33,530
私たちはやっているつもりはない
できるだけこの時間をコーディング。

33
00:01:33,530 --> 00:01:36,870
あなたはそれについての質問があれば
またはあなたはそれが実装見たい

34
00:01:36,870 --> 00:01:39,260
または自分自身でそれを試して、
私は間違いなくお勧めします

35
00:01:39,260 --> 00:01:44,250
、study.cs50.netしようとしている
これらの全ての例がある。

36
00:01:44,250 --> 00:01:46,400
それは私のパワーポイントがあるでしょう
我々リアクション

37
00:01:46,400 --> 00:01:50,860
使用する傾向があるだけでなく、いくつかのプログラミング
特に物事のため​​の演習、

38
00:01:50,860 --> 00:01:55,250
リンクリストとバイナリのような
木々スタックと合図。

39
00:01:55,250 --> 00:01:59,590
だから、もう少し高いレベル、どの
君たちのためにいいかもしれません。

40
00:01:59,590 --> 00:02:01,320
>> それとだから、私たちは始めるでしょう。

41
00:02:01,320 --> 00:02:03,060
また、yes--クイズ。

42
00:02:03,060 --> 00:02:06,550
私がしているあなた方のほとんどを考える
私のセクションでは、あなたのクイズを持っている

43
00:02:06,550 --> 00:02:12,060
しかし、誰もが何らかの理由で提供できます
ない、彼らはここの前にいる。

44
00:02:12,060 --> 00:02:12,740
>> だから、リストをリンク。

45
00:02:12,740 --> 00:02:15,650
私はこの種のが行く知っている
あなたのクイズの前にバックアップします。

46
00:02:15,650 --> 00:02:17,940
それは前の一週間でした
私たちはこのことについて学んだ。

47
00:02:17,940 --> 00:02:21,040
しかし、このケースでは、我々だけでよ
深さにもう少し行く。

48
00:02:21,040 --> 00:02:25,900
>> では、なぜ私たちは選ぶかもしれません
アレイの上にリンクリスト？

49
00:02:25,900 --> 00:02:27,130
何が彼らを区別する？

50
00:02:27,130 --> 00:02:27,630
はい？

51
00:02:27,630 --> 00:02:30,464
>> 読者：あなたがリンクさを拡張することができます
配列の固定サイズ対リスト。

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1：右。

53
00:02:31,171 --> 00:02:33,970
アレイは、一方でサイズを固定している
リンクリストは、可変サイズを有する。

54
00:02:33,970 --> 00:02:36,970
だから我々は方法がわからない場合
多くの私たちは、保存したい

55
00:02:36,970 --> 00:02:39,880
リンクリストは私たちに素晴らしいを与える
ので、我々はただできることを行うための方法

56
00:02:39,880 --> 00:02:43,730
別のノードで追加し、アドオン
別のノードとは別のノードに追加します。

57
00:02:43,730 --> 00:02:45,750
しかし、何がトレードオフのでしょうか？

58
00:02:45,750 --> 00:02:49,521
誰もがトレードオフを覚えていますか
配列やリンクリストの間で？

59
00:02:49,521 --> 00:02:50,020
ビー·マイ·エスケイプ？

60
00:02:50,020 --> 00:02:51,460
>> 読者：あなたがする必要がある
すべての道を通って行く

61
00:02:51,460 --> 00:02:53,738
リンクリストを通じて
リスト内の要素を見つける。

62
00:02:53,738 --> 00:02:55,570
アレイでは、次のことができます
単に要素を見つける。

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1：右。

64
00:02:56,278 --> 00:02:57,120
だからarrays--付き

65
00:02:57,120 --> 00:02:58,500
>> 読者：[聞こえない]。

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1：アレイでは、我々が持っている
ランダムアクセス何と呼ばれています。

67
00:03:01,090 --> 00:03:04,820
私たちが望む場合はどうであることを意味し
リストのこれまで五点

68
00:03:04,820 --> 00:03:07,230
私たちのまたは第5のポイント
アレイは、我々はそれをつかむことができます。

69
00:03:07,230 --> 00:03:10,440
それはリンクリストの場合、我々は持っている
右、を反復処理する？

70
00:03:10,440 --> 00:03:14,020
だから内の要素にアクセスする
アレイは、一定の時間である

71
00:03:14,020 --> 00:03:19,530
それはだろリンクリストと、一方
最も可能性が高いので、多分線形時間であること

72
00:03:19,530 --> 00:03:21,370
私たちの要素は、最後にすべての方法である。

73
00:03:21,370 --> 00:03:23,446
私たちはすべてのものを検索する必要があります。

74
00:03:23,446 --> 00:03:25,320
すべてのこれらのデータとそう
私たちが行っている構造

75
00:03:25,320 --> 00:03:29,330
上もう少し時間を費やすべき、
プラスとネガは何ですか。

76
00:03:29,330 --> 00:03:31,480
我々はしたいかもしれないとき
他の上で1つを使うのか？

77
00:03:31,480 --> 00:03:34,970
そして、それはのようなものだ
大きな事は奪うように。

78
00:03:34,970 --> 00:03:40,140
>> だから我々はここにある
ノードの定義。

79
00:03:40,140 --> 00:03:43,040
それは、1つの要素のようなものだ
私たちのリンクリスト、右？

80
00:03:43,040 --> 00:03:46,180
だから我々はすべて精通している
私たちのtypedef構造体と、

81
00:03:46,180 --> 00:03:47,980
我々は前回のレビューで渡ったもの。

82
00:03:47,980 --> 00:03:53,180
それは、基本的には作成していた
我々が使用することができ、別のデータ·タイプ。

83
00:03:53,180 --> 00:03:57,930
>> そして、この場合には、いくつかのノードの
それはいくつかの整数を保持します。

84
00:03:57,930 --> 00:04:00,210
その後、第2の部分は、ここに何ですか？

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
誰ですか？

87
00:04:05,677 --> 00:04:06,680
>> 読者：[聞こえない]。

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1：うん。

89
00:04:07,020 --> 00:04:08,400
それは、次のノードへのポインタだ。

90
00:04:08,400 --> 00:04:12,610
だから、これは実際にはここにアップする必要があります。

91
00:04:12,610 --> 00:04:18,790
これは型のポインタである
次の事にノード。

92
00:04:18,790 --> 00:04:22,410
そして、それはどのような彼らだ
我々のノードを含む。

93
00:04:22,410 --> 00:04:24,060
涼しい。

94
00:04:24,060 --> 00:04:29,390
>> 我々はあったように、検索したので、すべての権利
あなたがいるならちょうど、手を前に言って

95
00:04:29,390 --> 00:04:31,840
を検索しようとして、
あなたが実際に反復処理する必要があります

96
00:04:31,840 --> 00:04:33,660
あなたのリンクリストを通じて。

97
00:04:33,660 --> 00:04:38,530
だから我々は数を探しているなら
9、私たちは私たちの頭に開始する

98
00:04:38,530 --> 00:04:41,520
それは冒頭で私たちを指して
私達のリンクリストの、右？

99
00:04:41,520 --> 00:04:44,600
そして、我々はOK、これを行い、言う
ノードは、番号9を含むこと？

100
00:04:44,600 --> 00:04:45,690
いいえ？

101
00:04:45,690 --> 00:04:47,500
>> すべての権利、次のいずれかに行く。

102
00:04:47,500 --> 00:04:48,312
それに従ってください。

103
00:04:48,312 --> 00:04:49,520
それは9番が含まれていますか？

104
00:04:49,520 --> 00:04:50,570
いいえ。

105
00:04:50,570 --> 00:04:51,550
次の1に従ってください。

106
00:04:51,550 --> 00:04:55,490
>> だから我々は実際に反復処理する必要があります
私達のリンクリストを通じて。

107
00:04:55,490 --> 00:05:00,070
私達はちょうど9がどこに直接行くことができない。

108
00:05:00,070 --> 00:05:05,860
そしてあなたたちが実際にしたい場合は、
そこにいくつかの擬似コードアップを参照してください。

109
00:05:05,860 --> 00:05:10,420
ここではいくつかの検索機能を持っている
それはそれは何をでかかりますかin--かかる？

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
どう思う？

112
00:05:14,320 --> 00:05:15,960
とても簡単なもの。

113
00:05:15,960 --> 00:05:17,784
これは何ですか？

114
00:05:17,784 --> 00:05:18,700
読者：[聞こえない]。

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1：私たちが探している数。

116
00:05:20,366 --> 00:05:20,980
右？

117
00:05:20,980 --> 00:05:22,875
そして、何、これは対応するのでしょうか？

118
00:05:22,875 --> 00:05:25,020
それは、体へのポインタですか？

119
00:05:25,020 --> 00:05:26,000
>> 聴衆：ノード。

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1：リストへのノード
我々は正しい、見ていることを？

121
00:05:28,980 --> 00:05:33,700
だから我々はいくつかのノードがここにポインタである必要があります。

122
00:05:33,700 --> 00:05:37,240
これがために起こっている点である
実際に私たちのリストを反復処理。

123
00:05:37,240 --> 00:05:39,630
我々は、リストに等しく、それを設定する
それはただだから

124
00:05:39,630 --> 00:05:44,380
へのそれは等しく設定
私達のリンクリストの先頭。

125
00:05:44,380 --> 00:05:50,660
>> そして、それがNULLではありませんが、しばらく
我々はまだ私たちのリストで物事を持っている、

126
00:05:50,660 --> 00:05:55,580
そのノードが持っているかどうかを確認してください
私たちが探している数。

127
00:05:55,580 --> 00:05:57,740
trueを返します。

128
00:05:57,740 --> 00:06:01,070
そうでない場合は、右、それを更新する？

129
00:06:01,070 --> 00:06:04,870
>> それがNULLの場合、私たちは私たちのを終了
whileループとfalseを返す

130
00:06:04,870 --> 00:06:08,340
それが意味するので、我々はそれを見つけていない。

131
00:06:08,340 --> 00:06:11,048
誰もがそれがどのように機能するかを取得していますか？

132
00:06:11,048 --> 00:06:11,548
[OK]をクリックします。

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> あなたは、挿入したので、
3つの異なる方法を持っている。

135
00:06:20,260 --> 00:06:25,250
あなたが追加することができ、先頭に追加することができます
あなたが詰め合わせに挿入できる。

136
00:06:25,250 --> 00:06:28,215
このケースでは、だ
プリペンドをするつもり。

137
00:06:28,215 --> 00:06:33,380
どのようにそれらの人を知っていますか
3例は異なる場合があります？

138
00:06:33,380 --> 00:06:36,920
>> だから、プリペンドはあなたが置くことを意味します
それあなたのリストの先頭に。

139
00:06:36,920 --> 00:06:39,770
だから、意味に関係なく、その
あなたのノードは、どんなに何であるか

140
00:06:39,770 --> 00:06:43,160
値が何であるか、あなたが行っている
[OK]を、前で右のそれをここに置くか？

141
00:06:43,160 --> 00:06:45,160
それは最初になるだろう
あなたのリスト内の要素。

142
00:06:45,160 --> 00:06:49,510
>> あなたがそれを追加した場合は、それが起こっている
あなたのリストの裏に移動します。

143
00:06:49,510 --> 00:06:54,010
そして、あなたがしている各種手段に挿入する
所定の場所に実際に置くつもり

144
00:06:54,010 --> 00:06:57,700
それはあなたのリンクリストがソート保存する場所。

145
00:06:57,700 --> 00:07:00,810
ここでも、どのように使う
それらとするときに使用

146
00:07:00,810 --> 00:07:02,530
彼らはあなたのケースによって異なります。

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
それはする必要がない場合
ソートされ、先頭に追加の傾向

149
00:07:07,750 --> 00:07:10,460
何ほとんどの人であると
そうしないため、使用する

150
00:07:10,460 --> 00:07:15,680
リスト全体を通過する必要があり
右、それを追加するための終わりを見つけるには？

151
00:07:15,680 --> 00:07:17,720
あなたはちょうど右でそれを固執することができます。

152
00:07:17,720 --> 00:07:21,930
>> だから我々は通過します
挿入1、今。

153
00:07:21,930 --> 00:07:26,360
だから私はするつもりだ一つのことは、
非常にこのPSETにお勧め

154
00:07:26,360 --> 00:07:29,820
いつものように、物事を描画することです。

155
00:07:29,820 --> 00:07:35,130
あなたが更新することを、それは非常に重要です
正しい順序であなたのポインタ

156
00:07:35,130 --> 00:07:38,620
あなたがそれらを更新した場合ので、
ややアウトオブオーダー、

157
00:07:38,620 --> 00:07:42,210
あなたが終わるつもりです
あなたのリストの一部を失う。

158
00:07:42,210 --> 00:07:49,680
>> したがって、たとえば、この場合には、我々はしている
1にちょうどポイントに頭を伝える。

159
00:07:49,680 --> 00:07:56,070
私達はちょうどそれを行う場合
この1を保存せずに、

160
00:07:56,070 --> 00:07:58,570
私たちはどのような見当がつかない
1今を指している必要があります

161
00:07:58,570 --> 00:08:02,490
私たちは何を失ってしまったので、
頭が指摘した。

162
00:08:02,490 --> 00:08:05,530
だから、一つのことは覚えておくべき
あなたがプリペンドをやっているとき

163
00:08:05,530 --> 00:08:09,630
何保存することです
まず、ヘッドポイント

164
00:08:09,630 --> 00:08:15,210
それを再割り当てしてから、更新
何あなたの新しいノードが指している必要があります。

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
この場合、これはそれを行う一つの方法である。

167
00:08:22,560 --> 00:08:25,440
>> だから我々は、このようにそれをやっていれば
どこに私たちはただ、頭を再割り当て

168
00:08:25,440 --> 00:08:30,320
私たちは基本的に失う
リスト全体、右？

169
00:08:30,320 --> 00:08:38,000
これを行う1つの方法は、〜1点を持つことである
次の、その後1頭点を有する。

170
00:08:38,000 --> 00:08:42,650
それとも、一種のように行うことができます
私が話を一時記憶、。

171
00:08:42,650 --> 00:08:45,670
>> しかし、あなたの再割り当て
正しい順序でポインタ

172
00:08:45,670 --> 00:08:48,750
非常に、非常になるだろう
このPSETのために重要。

173
00:08:48,750 --> 00:08:53,140
そうしないと、ハッシュを持っているつもり
テーブルまたはちょうどになるだろう試し

174
00:08:53,140 --> 00:08:56,014
あなたの単語の一部のみ
欲しいその後you're--ビー·マイ·エスケイプ？

175
00:08:56,014 --> 00:08:58,930
聴衆：一時何だった
ストレージの事あなたが話していた？

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1：一時記憶。

177
00:09:00,305 --> 00:09:02,760
そこで、基本的に別の
あなたがこれを行うことができます方法

178
00:09:02,760 --> 00:09:07,650
同じように、何かの頭部を保管されている
それを一時変数に格納します。

179
00:09:07,650 --> 00:09:11,250
1にそれを割り当て、
その後ポイントに1を更新

180
00:09:11,250 --> 00:09:13,830
何でも頭に指すように使用される。

181
00:09:13,830 --> 00:09:16,920
この方法は明らかである
よりエレガントなあなたのため

182
00:09:16,920 --> 00:09:20,770
一時的な値を必要としませんが、
ちょうどそれを行うための別の方法を提供する。

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
そして、我々は実際に持っています
このため、いくつかのコード。

185
00:09:25,790 --> 00:09:28,080
リンクリストのためのだから、私たち
実際にいくつかのコードを持っている。

186
00:09:28,080 --> 00:09:31,930
だから、これが前に付加されて、ここに挿入します。

187
00:09:31,930 --> 00:09:34,290
だから、これは頭でそれを入力する。

188
00:09:34,290 --> 00:09:38,820
>> あなたがする必要があるので、まず最初に、
もちろん、あなたの新しいノードを作成し、

189
00:09:38,820 --> 00:09:40,790
そして、NULLかどうかを確認します。

190
00:09:40,790 --> 00:09:43,250
常に良い。

191
00:09:43,250 --> 00:09:47,840
そして、あなたは値を割り当てる必要があります。

192
00:09:47,840 --> 00:09:51,260
たびに新しいノードを作成するには、
それは次のを指しているのかわからないが、

193
00:09:51,260 --> 00:09:54,560
だから、NULLに初期化したいと思います。

194
00:09:54,560 --> 00:09:58,760
それが何かを指して終わるない場合
他に、それは再割り当てされます、それは大丈夫です。

195
00:09:58,760 --> 00:10:00,740
それは最初のif
リストには、必要

196
00:10:00,740 --> 00:10:04,270
なぜならNULLを指すように
それはリストの最後です。

197
00:10:04,270 --> 00:10:12,410
>> だから、それを挿入するために、我々は、我々はここを参照してください
私たちのノードの次の値を代入している

198
00:10:12,410 --> 00:10:17,380
頭が何であることが、
その私たちがここに持っていたものである。

199
00:10:17,380 --> 00:10:19,930
それは我々だけでやったことだ。

200
00:10:19,930 --> 00:10:25,820
そして、我々はポイントに頭を代入している
私たちの新しいノードに、覚えているので、

201
00:10:25,820 --> 00:10:31,090
新しいノードにいくつかのポインタである、
それは頭が何であるかを正確です。

202
00:10:31,090 --> 00:10:34,370
それはまさに、なぜ我々です
この矢印のアクセサを持っている。

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
クール？

205
00:10:37,530 --> 00:10:38,130
ビー·マイ·エスケイプ？

206
00:10:38,130 --> 00:10:41,100
>> 観客は：私たちがしなければならないの
最初のNULLに新しい次の初期化、

207
00:10:41,100 --> 00:10:44,240
または私達はちょうどそれが頭に初期化することができますか？

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1：次の新
開始するには、NULLである必要がある

209
00:10:48,210 --> 00:10:53,760
あなたが知らない理由
それはどこになるだろう。

210
00:10:53,760 --> 00:10:56,100
また、これは一種のです
ちょうどパラダイムが好きです。

211
00:10:56,100 --> 00:10:59,900
あなただけのためにNULLに等しく、それを設定する
すべての塩基がカバーされていることを確認してください

212
00:10:59,900 --> 00:11:04,070
あなたはそのので、任意の再割り当てを行う前に、
あなたは、常にそれがすることを保証しています

213
00:11:04,070 --> 00:11:08,880
特定の値を指している
ガベージ値のような対。

214
00:11:08,880 --> 00:11:12,210
なぜなら、ええ、私たちは割り当てる
自動的に次の新しい、

215
00:11:12,210 --> 00:11:15,420
それだけのようなより多くの
それを初期化することをお勧め

216
00:11:15,420 --> 00:11:19,270
そのようにし、その後再割り当てします。

217
00:11:19,270 --> 00:11:23,420
>> [OK]を、そのように二重になりましたリストを連動。

218
00:11:23,420 --> 00:11:24,601
私たちはどう思いますか？

219
00:11:24,601 --> 00:11:26,350
何と違う
二重にリンクされたリストを？

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> だから私たちのリンクリストで、我々はできる
右、一方向のみに移動？

222
00:11:34,300 --> 00:11:35,270
我々は唯一の横にあります。

223
00:11:35,270 --> 00:11:36,760
私たちは前進することができます。

224
00:11:36,760 --> 00:11:40,300
>> 二重リンクリストを使用して、
我々はまた、後方に移動することができます。

225
00:11:40,300 --> 00:11:44,810
だから我々は持っているだけでなく、
私たちが保存したい番号、

226
00:11:44,810 --> 00:11:50,110
それは次の指し示すところ、我々は持っている
そして私達はちょうどどこから来たのか。

227
00:11:50,110 --> 00:11:52,865
だから、これは可能にする
いくつかのより良いトラバーサル。

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> だから、二重にリンクされたノード、
非常によく似た、右​​？

230
00:12:01,240 --> 00:12:05,000
唯一の違いは、私たちは今である
次および前のを持っている。

231
00:12:05,000 --> 00:12:06,235
それは、唯一の違いです。

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> だから我々は前に付加した場合、またはappend--たち
here--このため、任意のコードを持っていない

234
00:12:14,790 --> 00:12:17,830
しかし、あなたがしようとした場合
、重要なことをそれを挿入

235
00:12:17,830 --> 00:12:19,980
あなたが作る必要があるある
あなたが代入していることを確認

236
00:12:19,980 --> 00:12:23,360
以前とあなたの両方
正しく次のポインタ。

237
00:12:23,360 --> 00:12:29,010
したがって、この場合には、でしょう
、次の初期化だけでなく、

238
00:12:29,010 --> 00:12:31,820
あなたは以前初期化します。

239
00:12:31,820 --> 00:12:36,960
我々はリストの先頭にいる場合は、私たち
頭等しいが新規になるだろうだけではなく、

240
00:12:36,960 --> 00:12:41,750
しかし、私たちの新しい、以前はすべき
頭をポイントし、右？

241
00:12:41,750 --> 00:12:43,380
>> それは唯一の違いです。

242
00:12:43,380 --> 00:12:47,200
そして、あなたはもっと練習が必要な場合と
挿入とリンクリスト、これらの、

243
00:12:47,200 --> 00:12:49,900
インサート、削除した
各種リストに、

244
00:12:49,900 --> 00:12:52,670
study.cs50.netをチェックしてください。

245
00:12:52,670 --> 00:12:54,870
偉大な演習の束があります。

246
00:12:54,870 --> 00:12:55,870
私は非常にそれらをお勧めします。

247
00:12:55,870 --> 00:12:59,210
私たちはそれらを介して行く時間があればいいのに
しかし、データ構造の多くがあります

248
00:12:59,210 --> 00:13:01,530
を介して取得する。

249
00:13:01,530 --> 00:13:02,650
>> [OK]を、ハッシュテーブルそう。

250
00:13:02,650 --> 00:13:07,070
これはおそらく最もです
あなたのpsetに便利ビット

251
00:13:07,070 --> 00:13:11,090
ここにあなたがするつもりだので、
これらのいずれか、または試みを実施しています。

252
00:13:11,090 --> 00:13:12,200
私は実際にハッシュテーブルのような。

253
00:13:12,200 --> 00:13:13,110
彼らはかなりクールだ。

254
00:13:13,110 --> 00:13:17,080
>> そこで、基本的にどのような
起こるは、ハッシュテーブルである

255
00:13:17,080 --> 00:13:22,050
私たちは本当にスピーディー必要なときである
挿入、削除、および参照。

256
00:13:22,050 --> 00:13:25,010
それらは、私たちがしているものです
ハッシュテーブルに優先順位を付ける。

257
00:13:25,010 --> 00:13:29,500
彼らは、かなり大きな得ることができます
しかし、我々はトライして表示されますよう、

258
00:13:29,500 --> 00:13:33,040
はるかに大きいですものがあります。

259
00:13:33,040 --> 00:13:38,330
>> しかし、基本的には、すべてのハッシュ
テーブルは、ハッシュ関数である

260
00:13:38,330 --> 00:13:47,215
それはそれぞれのを置くためにどのバケットがわかります
あなたのデータの、のあなたの各要素。

261
00:13:47,215 --> 00:13:51,140
ハッシュテーブルを考えるための簡単​​な方法
それだけで物事のバケットであるということです、

262
00:13:51,140 --> 00:13:51,770
右？

263
00:13:51,770 --> 00:13:59,720
だから、あなたがすることによって物事をソートするとき
自分の名前の最初の文字のように、

264
00:13:59,720 --> 00:14:01,820
それは一種のハッシュテーブルのようなものだ。

265
00:14:01,820 --> 00:14:06,180
>> 私はグループに君たちならばそうである
の名前が​​始まる誰のグループに

266
00:14:06,180 --> 00:14:11,670
こっちで、または誕生日は誰だ
、1月、2月、3月である

267
00:14:11,670 --> 00:14:15,220
どのような、それが効果的である
ハッシュテーブルを作成する。

268
00:14:15,220 --> 00:14:18,120
それはちょうどバケットを作成だということ
あなたがにあなたの要素を並べ替える

269
00:14:18,120 --> 00:14:19,520
あなたがそれらを簡単に見つけることができるようにします。

270
00:14:19,520 --> 00:14:22,300
私は必要なので、この方法
あなたのいずれかを見つけるために、

271
00:14:22,300 --> 00:14:24,680
私が検索する必要はありません
あなたの名前のそれぞれを通る。

272
00:14:24,680 --> 00:14:29,490
私は私が知っている、ああ、のようにすることができます
ダニエルの誕生日ですin--

273
00:14:29,490 --> 00:14:30,240
聴衆：--April。

274
00:14:30,240 --> 00:14:30,948
SPEAKER 1：4月。

275
00:14:30,948 --> 00:14:33,120
だから、私は月に見える
バケット、および任意の運と、

276
00:14:33,120 --> 00:14:38,270
彼女はそこに一つだけだろうと
私の時間は、その意味では一定であった

277
00:14:38,270 --> 00:14:41,230
私が見ている場合には、一方
人々の全体の束を経て、

278
00:14:41,230 --> 00:14:43,090
それははるかに長い時間がかかるだろう。

279
00:14:43,090 --> 00:14:45,830
だから、ハッシュテーブルは、本当にただのバケツです。

280
00:14:45,830 --> 00:14:48,630
それらを考えるための簡単​​な方法。

281
00:14:48,630 --> 00:14:52,930
>> だから、非常に重要なことについての
ハッシュテーブルは、ハッシュ関数である。

282
00:14:52,930 --> 00:14:58,140
だから、物事は私はちょうど同じように、の話
あなたの最初の名前の最初の手紙

283
00:14:58,140 --> 00:15:01,450
またはあなたの誕生日の月、
これらは、そのアイデアです

284
00:15:01,450 --> 00:15:03,070
本当にハッシュ関数に相関している。

285
00:15:03,070 --> 00:15:08,900
それはちょうどそれを決定する方法です
バケツあなたが要素だ[OK]を、に入る？

286
00:15:08,900 --> 00:15:14,850
だから、これのpsetのため、あなたが調べることができます
あなたが望むほとんどすべてのハッシュ関数。

287
00:15:14,850 --> 00:15:16,030
>> あなた自身である必要はありません。

288
00:15:16,030 --> 00:15:21,140
いくつかの本当にクールなものがそこにいる
そこに狂気の数学のすべてのソートを行うこと。

289
00:15:21,140 --> 00:15:25,170
そして、あなたはあなたを作りたい場合は、
超高速スペルチェッカ、

290
00:15:25,170 --> 00:15:27,620
私は間違いだろう
それらのいずれかに見える。

291
00:15:27,620 --> 00:15:32,390
>> しかし、またある
計算のような単純なもの、

292
00:15:32,390 --> 00:15:39,010
言葉の和、等
各文字には番号が付いています。

293
00:15:39,010 --> 00:15:39,940
合計を計算します。

294
00:15:39,940 --> 00:15:42,230
つまり、バケットを決定します。

295
00:15:42,230 --> 00:15:45,430
彼らはまた、簡単なものを持っている
ちょうどAのここでのすべてのようなもので、

296
00:15:45,430 --> 00:15:47,050
Bのすべてがここにあるのです。

297
00:15:47,050 --> 00:15:48,920
それらのいずれか。

298
00:15:48,920 --> 00:15:55,770
>> 基本的に、それはちょうどあなたに伝えている
配列インデックスあなたの要素が入るはずです。

299
00:15:55,770 --> 00:15:58,690
ただbucket--を決定
それは、すべてのハッシュ関数であるだ。

300
00:15:58,690 --> 00:16:04,180
そこでここでは、例を持っている
文字列の最初の文字だけ

301
00:16:04,180 --> 00:16:05,900
私はちょうど話していたという。

302
00:16:05,900 --> 00:16:11,900
>> だから、あなただけだいくつかのハッシュを持っている
あなたの文字列を引いAの最初の文字、

303
00:16:11,900 --> 00:16:16,090
あなたにいくつかを与えるもの
0と25の間の数。

304
00:16:16,090 --> 00:16:20,790
そして、何あなたがしたいことはある
これが表すことを確認してください

305
00:16:20,790 --> 00:16:24,110
あなたのハッシュのサイズtable--
どのように多くのバケットがあります。

306
00:16:24,110 --> 00:16:25,860
これらの多くを持つ
ハッシュ機能は、彼らがいる

307
00:16:25,860 --> 00:16:31,630
そのかもしれない値を返すことに行く
遠くバケットの数を超えること

308
00:16:31,630 --> 00:16:33,610
あなたが実際に持っていること
あなたのハッシュテーブル、

309
00:16:33,610 --> 00:16:37,240
だから、確認する必要があり
必ずそれらによるMOD。

310
00:16:37,240 --> 00:16:42,190
それ以外の場合は、言うために起こっている、
ああ、それはバケツ5000にする必要があります

311
00:16:42,190 --> 00:16:46,040
しかし、あなたは唯一の30を持っている
あなたのハッシュテーブル内のバケット。

312
00:16:46,040 --> 00:16:49,360
そしてもちろん、我々はすべてのそれは知っている
いくつかのクレイジーなエラーが発生するだろう。

313
00:16:49,360 --> 00:16:52,870
そうすることによっておよびMODに確認してください
あなたのハッシュテーブルのサイズ。

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
涼しい。

316
00:16:58,930 --> 00:17:00,506
衝突そう。

317
00:17:00,506 --> 00:17:02,620
誰もがこれまでのところは良いですか？

318
00:17:02,620 --> 00:17:03,120
ビー·マイ·エスケイプ？

319
00:17:03,120 --> 00:17:05,900
>> 読者：それはなぜだろう
そのような大規模な値を返す？

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1：アルゴリズムに応じて、
あなたのハッシュ関数を使用する。

321
00:17:09,210 --> 00:17:12,270
それらのいくつかさせていただきます
クレイジー乗算。

322
00:17:12,270 --> 00:17:16,270
そして、それは得ることについてすべてです
均一な分布、

323
00:17:16,270 --> 00:17:18,490
ので、彼らは実際にいくつかの操作を行い
時々狂気の事。

324
00:17:18,490 --> 00:17:20,960
それだけだ。

325
00:17:20,960 --> 00:17:22,140
他には？

326
00:17:22,140 --> 00:17:22,829
[OK]をクリックします。

327
00:17:22,829 --> 00:17:24,480
>> 衝突そう。

328
00:17:24,480 --> 00:17:29,270
基本的に、私が先に言ったように、
最良のシナリオで、

329
00:17:29,270 --> 00:17:32,040
私はに見てどのバケットがある
一つのことを持っているつもり、

330
00:17:32,040 --> 00:17:34,160
私は右、全く見てする必要はありません？

331
00:17:34,160 --> 00:17:37,040
私はどちらかはそれがあると知っているか、それはだ
ではない、それは私たちが本当に欲しいものだ。

332
00:17:37,040 --> 00:17:43,960
しかし、我々は数十万のを持っている場合
データ点およびその数未満

333
00:17:43,960 --> 00:17:48,700
バケットの、我々は持っているつもり
衝突場所最終的に何か

334
00:17:48,700 --> 00:17:54,210
に終わるために持っているとしている
既に要素を持ってバケツ。

335
00:17:54,210 --> 00:17:57,390
>> そこで問題は、何ですか
我々はその場合に行うのですか？

336
00:17:57,390 --> 00:17:58,480
私たちは何をしますか？

337
00:17:58,480 --> 00:17:59,300
我々はすでにそこに何かを持っている？

338
00:17:59,300 --> 00:18:00,060
私達はちょうどそれを捨てるのですか？

339
00:18:00,060 --> 00:18:00,700
>> いいえ。

340
00:18:00,700 --> 00:18:01,980
私たちは、それらの両方を維持する必要があります。

341
00:18:01,980 --> 00:18:06,400
我々だから、道
通常はそれが何であるか？

342
00:18:06,400 --> 00:18:08,400
データ構造は何ですか
私たちはただの話？

343
00:18:08,400 --> 00:18:09,316
読者：リンクリスト。

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1：リンクリスト。

345
00:18:10,500 --> 00:18:16,640
だから今、代わりにこれらのそれぞれの
バケットはちょうど1つの要素を持つ

346
00:18:16,640 --> 00:18:24,020
それはのリンクリストが含まれているために起こっている
それにハッシュされた要素。

347
00:18:24,020 --> 00:18:27,588
[OK]を、誰もが親切なのアイデアを得るのでしょうか？

348
00:18:27,588 --> 00:18:30,546
我々は配列を持っていない可能性があるため、
私たちはどのように多くのことを知らないので、

349
00:18:30,546 --> 00:18:31,730
そこにあることを行っている。

350
00:18:31,730 --> 00:18:36,540
リンクリストは、私たちがすることができます
ただ正確な数字を持っている

351
00:18:36,540 --> 00:18:38,465
右、そのバケットにハッシュされている？

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> プロービングとても直線的である
基本的にこのidea--

354
00:18:50,500 --> 00:18:52,300
それは、衝突に対処する一つの方法です。

355
00:18:52,300 --> 00:18:58,010
あなたは何を行うことができ、この中で、あればある
ケースは、ベリーは1にハッシュされた

356
00:18:58,010 --> 00:19:01,130
そして我々はすでに持っている
何かが、あなただけの

357
00:19:01,130 --> 00:19:04,840
まで押し下げ続ける
あなたは空のスロットを見つける。

358
00:19:04,840 --> 00:19:06,370
つまり、それを処理する一つの方法です。

359
00:19:06,370 --> 00:19:09,020
処理するための他の方法
それはちょうど私たちとです

360
00:19:09,020 --> 00:19:12,280
リンクをcalled--
リストはチェーンと呼ばれています。

361
00:19:12,280 --> 00:19:20,510
>> だから、このアイデアは、以下の場合に動作します
あなたが考えるあなたのハッシュテーブル

362
00:19:20,510 --> 00:19:24,150
よりはるかに大きい
あなたのデータは、設定したり、場合

363
00:19:24,150 --> 00:19:28,870
試してみて、チェーン化最小限にしたい
それは絶対に必要になるまで。

364
00:19:28,870 --> 00:19:34,050
だから、一つのことは、線形である
明らかに意味のプロービング

365
00:19:34,050 --> 00:19:37,290
あなたのハッシュ関数という
それほど有用ではありません

366
00:19:37,290 --> 00:19:42,200
あなたが使用して終了するつもりだので、
あなたのハッシュ関数、ポイントになって、

367
00:19:42,200 --> 00:19:46,400
まであなたリニアプローブ
利用可能であるいくつかの場所。

368
00:19:46,400 --> 00:19:49,670
しかし、今は、もちろん、何でも
、そこに終わるという他

369
00:19:49,670 --> 00:19:52,050
あなたがする必要があるとしている
さらにダウン検索。

370
00:19:52,050 --> 00:19:55,650
>> そしてもっとたくさんあり​​ます
検索費用その

371
00:19:55,650 --> 00:19:59,820
要素を入力することになり
今あなたのハッシュテーブルで、右か？

372
00:19:59,820 --> 00:20:05,640
そして今、あなたが行くと試してみて、見つけたとき
ベリー再び、あなたはそれをハッシュするつもりだ、

373
00:20:05,640 --> 00:20:07,742
そしてそれは、言うために起こっている
ああ、バケット1で見て、

374
00:20:07,742 --> 00:20:09,700
それがあることを行っていない
バケット1に、そうあなたがいる

375
00:20:09,700 --> 00:20:11,970
トラバースする必要があるとして
これらの残りの部分を通して。

376
00:20:11,970 --> 00:20:17,720
だから、時には便利だ
しかし、ほとんどの場合、

377
00:20:17,720 --> 00:20:22,660
我々はそれを言おうとしている
連鎖はあなたが何をしたいです。

378
00:20:22,660 --> 00:20:25,520
>> だから我々はこの先にについて話しました。

379
00:20:25,520 --> 00:20:27,812
私は自分自身の少し先を得た。

380
00:20:27,812 --> 00:20:33,560
しかし、連鎖は基本的にあり
あなたのハッシュテーブル内の各バケット

381
00:20:33,560 --> 00:20:36,120
ちょうどリンクリストです。

382
00:20:36,120 --> 00:20:39,660
>> だから、別の方法、またはそれ以上の技術的
ハッシュテーブルを考えるための方法、

383
00:20:39,660 --> 00:20:44,490
それだけで、配列であるということです
リンクリストの、どの

384
00:20:44,490 --> 00:20:49,330
あなたの辞書を書いているとき
そして、あなたはそれをロードしようとしている、

385
00:20:49,330 --> 00:20:52,070
としてそれを考えて
リンクされたリストの配列

386
00:20:52,070 --> 00:20:54,390
それははるかに容易になります
あなたは初期化す​​るために。

387
00:20:54,390 --> 00:20:57,680
>> 聴衆：だからハッシュテーブル
所定のサイズを有し、

388
00:20:57,680 --> 00:20:58,980
バケットの[聞こえない]のような？

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1：右。

390
00:20:59,220 --> 00:21:01,655
だから、一連の番号を持つ
あなたがdetermine--バケット

391
00:21:01,655 --> 00:21:03,530
その君たちがすべき
と遊ぶこと自由に感じ。

392
00:21:03,530 --> 00:21:05,269
それはかなり涼しいことができます
何が起こるかを見るために

393
00:21:05,269 --> 00:21:06,810
あなたはバケットのあなたの数を変更するように。

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
しかし、ええ、それはあります
バケットの数を設定します。

396
00:21:11,510 --> 00:21:15,360
あなたにフィットすることができますどのような
あなたが必要な多くの要素

397
00:21:15,360 --> 00:21:19,350
あなた、この独立したチェーンです
各バケット内のリストをリンクしています。

398
00:21:19,350 --> 00:21:22,850
それはあなたのハッシュテーブルを意味します
丁度サイズになります

399
00:21:22,850 --> 00:21:25,440
あなたはそれが、右する必要があること？

400
00:21:25,440 --> 00:21:27,358
つまり、リンクリストの全体のポイントだ。

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
涼しい。

403
00:21:32,480 --> 00:21:38,780
>> そこにそのように誰もOK？

404
00:21:38,780 --> 00:21:39,801
わかりました。

405
00:21:39,801 --> 00:21:40,300
ああ。

406
00:21:40,300 --> 00:21:41,860
何が起こった？

407
00:21:41,860 --> 00:21:42,960
本当に今。

408
00:21:42,960 --> 00:21:45,250
誰かが私を殺してだと思う。

409
00:21:45,250 --> 00:21:52,060
>> [OK]を私たちは入るつもりです
少し狂っている試み。

410
00:21:52,060 --> 00:21:53,140
私は、ハッシュテーブルのように。

411
00:21:53,140 --> 00:21:54,460
私は、彼らが本当にクールだと思う。

412
00:21:54,460 --> 00:21:56,710
試行は、あまりにも、かっこいいです。

413
00:21:56,710 --> 00:21:59,590
>> だから、誰もが試しが何であるかを覚えているのでしょうか？

414
00:21:59,590 --> 00:22:01,740
あなたは終わってしまっているはずです
それを簡単にレクチャーで？

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
あなたはそれがどのように動作するかのようなものを覚えていますか？

417
00:22:06,377 --> 00:22:08,460
読者：私はちょうどうなずいてる
我々はそれを乗り越えたこと。

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1：我々は、その上に行くのですか。

419
00:22:09,626 --> 00:22:13,100
[OK]を、私たちは本当に行くつもりです
その上に、今私たちが言っているものです。

420
00:22:13,100 --> 00:22:14,860
>> 聴衆：検索ツリーのためだ。

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1：うん。

422
00:22:15,280 --> 00:22:16,196
それは、検索ツリーです。

423
00:22:16,196 --> 00:22:16,960
恐ろしい。

424
00:22:16,960 --> 00:22:23,610
だからここに注意すべき一つのことは、その私たちです
個々の文字を見ている

425
00:22:23,610 --> 00:22:24,480
ここでは、右か？

426
00:22:24,480 --> 00:22:29,710
>> だから私たちのハッシュ関数の前に、私たち
全体としての言葉を見ていた、

427
00:22:29,710 --> 00:22:32,270
そして今、我々はより多くを探している
文字で、右？

428
00:22:32,270 --> 00:22:38,380
だから我々はこことメンデルの上にマクスウェルを持っている。

429
00:22:38,380 --> 00:22:47,840
そこで、基本的に考える方法をtry--
このことについて、そのすべてのレベルはここにある

430
00:22:47,840 --> 00:22:49,000
文字の配列である。

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
だから、これはあなたのルートノードは右、ここですか？

433
00:22:55,790 --> 00:23:01,980
これは、すべての文字が含まれている
すべての単語の開始のためのアルファベット。

434
00:23:01,980 --> 00:23:06,480
>> そして、何あなたがしたいことはある
たとえば、[OK]を、我々はいくつかのMワードを持っている。

435
00:23:06,480 --> 00:23:10,590
私たちはそのように、マクスウェルを探すつもりだ
我々は全体に、MとMのポイントに行く

436
00:23:10,590 --> 00:23:14,800
他のアレイ場所ごとに
限り、そこに単語、

437
00:23:14,800 --> 00:23:17,044
持っワードです
第二の手紙のように、

438
00:23:17,044 --> 00:23:19,460
限り単語があることありますように
第二の手紙のようにBを有し、

439
00:23:19,460 --> 00:23:24,630
それは、ポインタを持つことになります
いくつかの次のアレイに行く。

440
00:23:24,630 --> 00:23:29,290
>> おそらくそこにはありません
単語のMP何か、

441
00:23:29,290 --> 00:23:32,980
この中でP位置でそう
アレイは、それだけではNULLになります。

442
00:23:32,980 --> 00:23:38,840
これは、[OK]を、全く言葉がありません、と言うでしょう
それはMはOK、Pに続いたのか？

443
00:23:38,840 --> 00:23:43,100
だから我々はそれについて考える場合には、各
これらの小さいものの一つ

444
00:23:43,100 --> 00:23:47,990
実際にこれらの一つである
AからZまで、大きな配列

445
00:23:47,990 --> 00:23:55,064
それでは、ものの一つかもしれません
それは、tryの欠点の一種である？

446
00:23:55,064 --> 00:23:56,500
>> 読者：多くのメモリ。

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1：それは右、メモリのトンですか？

448
00:23:59,940 --> 00:24:08,750
ここで、これらのブロックの各々は
26スペース、26素子アレイを表す。

449
00:24:08,750 --> 00:24:13,680
だから、試みは信じられないほどのスペース重いを取得します。

450
00:24:13,680 --> 00:24:17,100
>> しかし、彼らは非常に高速です。

451
00:24:17,100 --> 00:24:22,540
信じられないほど高速だが
本当にスペース効率の悪い。

452
00:24:22,540 --> 00:24:24,810
種類の把握する必要があります
どちらからあなたが欲しい。

453
00:24:24,810 --> 00:24:29,470
これらはあなたのpsetのために本当にクールである、
しかし、彼らは多くのメモリを占有しません、

454
00:24:29,470 --> 00:24:30,290
だから、トレードオフ。

455
00:24:30,290 --> 00:24:31,480
うん？

456
00:24:31,480 --> 00:24:34,300
>> 読者：それは可能でしょう
そのtryを設定し、する

457
00:24:34,300 --> 00:24:37,967
あなたはすべて持っている一度
あなたがneed--ことをその中にデータ

458
00:24:37,967 --> 00:24:39,550
それは理にかなっているかどうかは知りません。

459
00:24:39,550 --> 00:24:42,200
私はすべてを退治した
NULL文字が、その後、

460
00:24:42,200 --> 00:24:42,910
あなたは、インデックスthem--することができないだろ

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1：あなたはまだそれらを必要としています。

462
00:24:43,275 --> 00:24:44,854
>> 読者： - 同じように毎回。

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1：うん。

464
00:24:45,520 --> 00:24:50,460
あなたができるように、NULL文字が必要
単語がそこにはない場合、あなたが知っている。

465
00:24:50,460 --> 00:24:52,040
ベンは、あなたが欲しいものを持っていた？

466
00:24:52,040 --> 00:24:52,540
[OK]をクリックします。

467
00:24:52,540 --> 00:24:54,581
すべての権利、私たちはなるだろう
もう少し行く

468
00:24:54,581 --> 00:24:58,920
背後にある技術的な詳細へ
試してみて、例を介して動作。

469
00:24:58,920 --> 00:25:01,490
>> [OK]を、これは同じものです。

470
00:25:01,490 --> 00:25:06,290
リンクリストで、私たちの主なのに対し、
？種類of--私が欲しい言葉は何ですか - 

471
00:25:06,290 --> 00:25:08,350
ブロックを構築するようなノードだった。

472
00:25:08,350 --> 00:25:12,280
トライでは、我々はまた、ノードを持っている
しかしそれは異なって定義だ。

473
00:25:12,280 --> 00:25:17,000
>> だから我々はいくつかのブール値を持っている
実際に単語かどうかを表します

474
00:25:17,000 --> 00:25:23,530
この場所に存在し、その後
私たちは、here--またはむしろ、いくつかの配列を持っている

475
00:25:23,530 --> 00:25:27,840
これはへのポインタである
27文字の配列。

476
00:25:27,840 --> 00:25:33,339
これは、この場合には、このある
27--私はあなたのすべてが似ていると確信している、待って

477
00:25:33,339 --> 00:25:34,880
アルファベットの26文字があります。

478
00:25:34,880 --> 00:25:36,010
なぜ我々は27を持っていますか？

479
00:25:36,010 --> 00:25:37,870
>> だから、依存
あなたはこれを実装する方法、

480
00:25:37,870 --> 00:25:43,240
これは、プロセッサセットからのものである
アポストロフィを可能にした。

481
00:25:43,240 --> 00:25:46,010
だから、なぜ、余分な一つだ。

482
00:25:46,010 --> 00:25:50,500
あなたは、いくつかの中にもあるでしょう
例ヌルターミネータ

483
00:25:50,500 --> 00:25:53,230
の一つとして含まれています
それがあることを許可のキャラクター、

484
00:25:53,230 --> 00:25:56,120
それは彼らがチェックする方法です
それは単語の終わりだかどうかを確認します。

485
00:25:56,120 --> 00:26:01,340
あなたが興味を持っている場合、チェックアウトする
study.cs50上のケビンさんのビデオ、

486
00:26:01,340 --> 00:26:04,790
同様にウィキペディアがあります
そこにいくつかの良いリソース。

487
00:26:04,790 --> 00:26:09,000
>> しかし、我々はただ一種を通過するつもりだ
あなたは、tryを介して動作する方法の

488
00:26:09,000 --> 00:26:11,010
あなたは1を与えられている場合。

489
00:26:11,010 --> 00:26:16,230
だから我々はここでその超簡単1を持っている
それらの単語「コウモリ」と「ズーム」を持っています。

490
00:26:16,230 --> 00:26:18,920
そして、我々はここに見るように、
ここで、この小さなスペース

491
00:26:18,920 --> 00:26:22,560
我々のブール値を表す
はい、これは言葉である、と言います。

492
00:26:22,560 --> 00:26:27,060
そして、これは私たちを持って
文字の配列、右？

493
00:26:27,060 --> 00:26:33,480
>> だから我々は通過しようとしている
この試みを「バット」を見つける。

494
00:26:33,480 --> 00:26:38,340
だから、右、上から始まり？

495
00:26:38,340 --> 00:26:46,290
そして我々は、bはに対応することを知っている
第二のインデックス、第二の要素

496
00:26:46,290 --> 00:26:47,840
このアレイでは、aとbのため。

497
00:26:47,840 --> 00:26:51,340
だから、およそ秒1。

498
00:26:51,340 --> 00:26:58,820
>> そして、それはOK、クール、にその従ってください、と言う
次のアレイ、私たちは覚えていればいるため、

499
00:26:58,820 --> 00:27:02,160
それはこれらの各ことではありません
実際に要素が含まれています。

500
00:27:02,160 --> 00:27:07,110
これらの配列の各々は
右、ポインタを含む？

501
00:27:07,110 --> 00:27:10,030
それは作るべき重要な区別です。

502
00:27:10,030 --> 00:27:13,450
>> 私は、これは試行をbe--しようとしているされている知っている
初めてに乗るために本当に一生懸命、

503
00:27:13,450 --> 00:27:15,241
従って、この場合であっても
第二または第三の時間

504
00:27:15,241 --> 00:27:18,370
そしてそれはまだのようなものだ
困難な見せかけの、

505
00:27:18,370 --> 00:27:21,199
あなたが時計を行けば私は約束
明日再び短い、

506
00:27:21,199 --> 00:27:22,740
それはおそらく、多くの方が理にかなっているでしょう。

507
00:27:22,740 --> 00:27:23,890
それは消化するかかる。

508
00:27:23,890 --> 00:27:27,800
私は今でも時々午前
のように、待って、試しては何ですか？

509
00:27:27,800 --> 00:27:29,080
私はこれをどのように使うのですか？

510
00:27:29,080 --> 00:27:33,880
>> だから我々は、この場合のBきた
その私たちの第二のインデックスです。

511
00:27:33,880 --> 00:27:40,240
我々が持っていた場合は、たとえば、cまたは
dまたは他の任意の文字、

512
00:27:40,240 --> 00:27:45,810
私たちは、インデックスにその背中をマップする必要が
それが対応するという我々のアレイ。

513
00:27:45,810 --> 00:27:56,930
だから我々はrcharのように取ると、ちょうど私たち
0から25までにそれをマップするためにオフに引く。

514
00:27:56,930 --> 00:27:58,728
どのように我々の良い皆
私たちの文字をマッピング？

515
00:27:58,728 --> 00:28:00,440
[OK]をクリックします。

516
00:28:00,440 --> 00:28:05,980
>> だから我々は第二の1、私たちに行く
はい、それはNULLにはない、ことがわかります。

517
00:28:05,980 --> 00:28:07,780
我々は、この次のアレイに移動することができます。

518
00:28:07,780 --> 00:28:12,300
だから我々はここに、この次のアレイに進みます。

519
00:28:12,300 --> 00:28:15,500
>> そして、我々は我々は今、[OK]を、言う
ここにあるかどうかを確認する必要があります。

520
00:28:15,500 --> 00:28:18,590
nullであるか、それをしない
実際に前進？

521
00:28:18,590 --> 00:28:21,880
だから、実際に動く
この配列に転送します。

522
00:28:21,880 --> 00:28:24,570
そして、我々はOK、tは私たちの最後の手紙である、と言う。

523
00:28:24,570 --> 00:28:27,580
だから我々は、インデックスでトンに行く。

524
00:28:27,580 --> 00:28:30,120
そして、我々は前進する
もう一つはそこだから。

525
00:28:30,120 --> 00:28:38,340
この1つは、はい、基本的にはそれを言う
その単語があることを言うhere--

526
00:28:38,340 --> 00:28:41,750
あなたがこれをたどる場合に
パスは、あなたが到着した

527
00:28:41,750 --> 00:28:43,210
私たちが知っている単語、で「コウモリ」です。

528
00:28:43,210 --> 00:28:43,800
はい？

529
00:28:43,800 --> 00:28:46,770
>> 読者：それは標準のものを持つことである
その後インデックス0として1での並べ替えを持って

530
00:28:46,770 --> 00:28:47,660
または終了時に持っている？

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1：いいえ。

532
00:28:48,243 --> 00:28:55,360
だから我々は戻って私たちを見れば
ここに宣言、それはブール値ですが、

533
00:28:55,360 --> 00:28:59,490
そう、それはあなたのノードに独自の要素です。

534
00:28:59,490 --> 00:29:03,331
だから、アレイの一部ではありません。

535
00:29:03,331 --> 00:29:03,830
涼しい。

536
00:29:03,830 --> 00:29:08,370
だから私たちは私たちの言葉を終え、私たちがいるとき
この配列では、我々は何をしたいのか

537
00:29:08,370 --> 00:29:12,807
これが単語であるためチェックを行うです。

538
00:29:12,807 --> 00:29:14,390
そして、この場合には、そう返す。

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> だから、そのノートに、私たちはその「動物園」を知っている - 
私たちは、「動物園」は単語であることを人間として知って

541
00:29:24,090 --> 00:29:24,820
右？

542
00:29:24,820 --> 00:29:28,990
しかし、ここだろう試している
いや、それはない、と言う。

543
00:29:28,990 --> 00:29:33,980
そして、それはと言うでしょう、私たちのため
ここで単語としてそれを指定されていません。

544
00:29:33,980 --> 00:29:40,440
私たちは横断できるにもかかわらず
この配列に至るまで、

545
00:29:40,440 --> 00:29:43,890
この試みは、いや、それを言うだろう
動物園は、あなたの辞書にはない

546
00:29:43,890 --> 00:29:47,070
我々はそうではありませんので、
そのように指定された。

547
00:29:47,070 --> 00:29:52,870
>> that--やることが一つの方法
ああ、申し訳ありませんが、この1。

548
00:29:52,870 --> 00:29:59,450
したがって、この場合には、「動物園」ではない
言葉が、それは私たちの試みである。

549
00:29:59,450 --> 00:30:05,690
しかし、このいずれかで、我々はそれをしたいと言う
「お風呂は、「何が起こるの言葉を紹介する

550
00:30:05,690 --> 00:30:08,260
我々はthrough-- B、Tに従っています。

551
00:30:08,260 --> 00:30:11,820
我々は、この配列内だし、
我々は時間を検索するために行く。

552
00:30:11,820 --> 00:30:15,220
>> この場合には、ときに我々
hにポインタを見て、

553
00:30:15,220 --> 00:30:17,890
それは[OK]を、NULLを指すのですか？

554
00:30:17,890 --> 00:30:20,780
だから、明示的でない限り
別の配列を指して、

555
00:30:20,780 --> 00:30:25,000
あなたはすべてのポインタと仮定
この配列にはnullを指している。

556
00:30:25,000 --> 00:30:28,270
したがって、この場合には、hが指している
nullに私たちは何もできない、

557
00:30:28,270 --> 00:30:31,540
そう、それはまた戻ってくる
偽の、「お風呂」は、ここでではありません。

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
だから今、私たちは、実際にしている
経由行くつもり

560
00:30:35,810 --> 00:30:39,790
私たちは実際にどのように言うでしょう
「動物園」は私達の試みである。

561
00:30:39,790 --> 00:30:42,920
どのように私たちは試しに "動物園"を挿入しますか？

562
00:30:42,920 --> 00:30:47,810
使い始めたのと同じ方法でそう
私たちのリンクリスト、我々はルートから始まる。

563
00:30:47,810 --> 00:30:50,600
疑わしい場合に、で開始
これらの事のルート。

564
00:30:50,600 --> 00:30:53,330
>> そして、我々は、z、[OK]を、と言うでしょう。

565
00:30:53,330 --> 00:30:55,650
zがこの中に存在し、それはありません。

566
00:30:55,650 --> 00:30:58,370
だから、上に移動している
あなたの次のアレイ、OK？

567
00:30:58,370 --> 00:31:01,482
した後、次のいずれかで、
我々はOK、oは存在しない、と言う？

568
00:31:01,482 --> 00:31:03,000
それはありません。

569
00:31:03,000 --> 00:31:04,330
この再び。

570
00:31:04,330 --> 00:31:08,670
>> そしてそう私たちの次のいずれかに、我々は、言ってきた
[OK]を、「動物園」はすでにここに存在します。

571
00:31:08,670 --> 00:31:12,440
私たちがやらなければならないことは、これは等しく設定される
trueに、そこに単語が存在すること。

572
00:31:12,440 --> 00:31:15,260
あなたはすべてを追っていた場合
そのポイントの前まで、

573
00:31:15,260 --> 00:31:17,030
それは言葉だけなので、
このように等しく、それを設定してください。

574
00:31:17,030 --> 00:31:17,530
はい？

575
00:31:17,530 --> 00:31:22,550
>> 聴衆：それではことを行います
「BA」も単語であることを意味ですか？

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1：いいえ。

577
00:31:24,120 --> 00:31:28,870
したがって、この場合、「BA」に私たちはなるだろう
ここで、我々は、それが単語であると言うでしょう

578
00:31:28,870 --> 00:31:31,590
それはまだ全くないであろう。

579
00:31:31,590 --> 00:31:32,822
OK？

580
00:31:32,822 --> 00:31:33,740
ビー·マイ·エスケイプ？

581
00:31:33,740 --> 00:31:36,360
>> 読者：だから、それしたら
単語とあなたがそれそれから、イエスと言う

582
00:31:36,360 --> 00:31:38,380
mまで行くことが含まれます？

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1：これは関係しています
with--あなたはこれを読み込んでいる。

584
00:31:42,260 --> 00:31:43,640
あなたは、「動物園」は単語であると言う。

585
00:31:43,640 --> 00:31:47,020
あなたがcheck--に行くとき
のような、あなたが言いたいと言う、

586
00:31:47,020 --> 00:31:49,400
「動物園」は、この辞書には存在していますか？

587
00:31:49,400 --> 00:31:54,200
あなただけの「動物園」を検索するつもりだ
そしてそれは、Wordのかどうかを確認してください。

588
00:31:54,200 --> 00:31:57,291
あなたが移動するつもりはありませんしている
mまでを通してそれがありませんので、

589
00:31:57,291 --> 00:31:58,290
あなたが探しているもの。

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> だから我々は、実際にしたい場合
この試みに「風呂」を追加し、

592
00:32:08,070 --> 00:32:11,390
我々は同じことをするだろう
我々が行ったように、「動物園」、

593
00:32:11,390 --> 00:32:15,380
ときに我々我々はそれを見ることを除いて
試してみて、時間を取得、それは存在しません。

594
00:32:15,380 --> 00:32:20,090
だから、しようと考えることができ
リンクされたリストに新しいノードを追加するには、

595
00:32:20,090 --> 00:32:27,210
私たちは別のものを追加する必要があります
そうように、これらのアレイの1つ、。

596
00:32:27,210 --> 00:32:35,670
そして、我々はただ時間を設定されている私たちは何をすべきか
これに指してこの配列の要素。

597
00:32:35,670 --> 00:32:39,430
>> そして、我々はここで何をすべきかをしたいですか？

598
00:32:39,430 --> 00:32:43,110
trueに等しいことを追加します。
なぜならそれは言葉だ。

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
涼しい。

601
00:32:48,150 --> 00:32:48,700
私は知っている。

602
00:32:48,700 --> 00:32:51,170
試行は、最もエキサイティングではありません。

603
00:32:51,170 --> 00:32:54,250
私が知っている、私を信頼しています。

604
00:32:54,250 --> 00:32:58,040
>> 試行で実現するので、一つのこと、
私は、彼らは非常に効率的だ、と述べた。

605
00:32:58,040 --> 00:33:00,080
だから我々は彼らを見てきました
スペースのトンを取る。

606
00:33:00,080 --> 00:33:01,370
彼らは一種の混乱している。

607
00:33:01,370 --> 00:33:03,367
では、なぜ私たちはこれまでにこれらを使用するのでしょうか？

608
00:33:03,367 --> 00:33:05,450
彼らがしているので、私たちはこれらのを使用
信じられないほど効率的。

609
00:33:05,450 --> 00:33:08,130
>> だから、あなたが今まで探しているなら
単語まで、あなただけです

610
00:33:08,130 --> 00:33:10,450
単語の長さによって制限。

611
00:33:10,450 --> 00:33:15,210
ので、もしあなたが探している
長さ5である言葉、

612
00:33:15,210 --> 00:33:20,940
あなたは今までに持っているつもり
[OK]を、最大でも5比較を行う？

613
00:33:20,940 --> 00:33:25,780
だから、それは基本的に一定になります。

614
00:33:25,780 --> 00:33:29,150
挿入とルックアップのような
基本的には一定の時間である。

615
00:33:29,150 --> 00:33:33,750
>> だから、あなたがこれまで得ることができるかどうか
一定時間内に何か、

616
00:33:33,750 --> 00:33:35,150
それは恋愛小説家だ。

617
00:33:35,150 --> 00:33:37,990
あなたがより良くなることはできません
これらの事のために一定の時間。

618
00:33:37,990 --> 00:33:43,150
だからの一つです
試行の巨大なプラス。

619
00:33:43,150 --> 00:33:46,780
>> しかし、それは多くのスペースです。

620
00:33:46,780 --> 00:33:50,380
だから、一種の決定する必要があります
何があなたにとってより重要だ。

621
00:33:50,380 --> 00:33:54,700
今日のコンピュータ上で、
トライがかかる場合がありますスペース

622
00:33:54,700 --> 00:33:57,740
多分に影響しません
それだけあなたが、多分

623
00:33:57,740 --> 00:34:01,350
あなたが何かを扱っている
それは、はるかに、はるかに多くのものを持っています

624
00:34:01,350 --> 00:34:02,810
と試してはただ合理的ではありません。

625
00:34:02,810 --> 00:34:03,000
はい？

626
00:34:03,000 --> 00:34:05,610
>> 聴衆：待って、そうあなたは26を持っている
すべての単一の1の文字？

627
00:34:05,610 --> 00:34:07,440
>> SPEAKER 1：ビー·マイ·エスケイプ。

628
00:34:07,440 --> 00:34:08,570
ええ、あなたは26を持っている。

629
00:34:08,570 --> 00:34:16,984
あなたは、いくつかは、その後の単語マーカーであり、持っている
あなたは一人一人で26のポインタを持っている。

630
00:34:16,984 --> 00:34:17,775
そして、彼らはpoint--いる

631
00:34:17,775 --> 00:34:20,280
>> 聴衆：そしてすべての26、
彼らはそれぞれ、26を持っていますか？

632
00:34:20,280 --> 00:34:21,500
>> SPEAKER 1：はい。

633
00:34:21,500 --> 00:34:27,460
することができますようにそしてそれは、なぜだ
それは非常に急速に拡大し、参照してください。

634
00:34:27,460 --> 00:34:28,130
わかりました。

635
00:34:28,130 --> 00:34:32,524
だから我々は、木に取得するつもりだどの
おそらく簡単に、意志であるような気がする

636
00:34:32,524 --> 00:34:36,150
ちょっといい猶予も
そこからトライ。

637
00:34:36,150 --> 00:34:39,620
だから、うまくいけばあなたのほとんど
前のツリーを見てきました。

638
00:34:39,620 --> 00:34:41,820
かなりのようではない
外のものを、どのI

639
00:34:41,820 --> 00:34:44,340
誰かどうかわからない
最近屋外で行きました。

640
00:34:44,340 --> 00:34:49,230
私はこの週末を選ぶリンゴに行きました、
そしておやっ私のああ、それは美しかった。

641
00:34:49,230 --> 00:34:52,250
私は葉を知りませんでした
そのかなり見ることができる。

642
00:34:52,250 --> 00:34:53,610
>> だから、これは右、ちょうど木です？

643
00:34:53,610 --> 00:34:56,790
それはちょうど、いくつかのノードだし、それ
他のノードの束を指す。

644
00:34:56,790 --> 00:34:59,570
ここで見るように、これはある
繰り返されるテーマの一種。

645
00:34:59,570 --> 00:35:03,720
ノードを指しているノードは、一種のである
多くのデータ構造の本質。

646
00:35:03,720 --> 00:35:06,670
それはちょうど、我々方法によって異なります
それらが互いに指してい

647
00:35:06,670 --> 00:35:08,600
そしてどのように我々はトラバース
それらを通して、どのように我々

648
00:35:08,600 --> 00:35:14,500
決定物事を挿入
彼らの異なる特性。

649
00:35:14,500 --> 00:35:17,600
>> だからいくつかの用語で、
その私が前に使っています。

650
00:35:17,600 --> 00:35:20,010
だから、根は非常に一番上には何でもある。

651
00:35:20,010 --> 00:35:21,200
私たちは常に起動それはどこだ。

652
00:35:21,200 --> 00:35:23,610
また、頭部と考えることができます。

653
00:35:23,610 --> 00:35:28,750
しかし、樹木のために、私たちはする傾向
ルートとしてそれを参照してください。

654
00:35:28,750 --> 00:35:32,820
>> 下部には何もhere--
非常に、非常にbottom--で

655
00:35:32,820 --> 00:35:34,500
葉と考えられている。

656
00:35:34,500 --> 00:35:37,210
だから、一緒に行く
ツリー全体の事、右？

657
00:35:37,210 --> 00:35:39,860
葉はあなたの木の縁である。

658
00:35:39,860 --> 00:35:45,820
>> そして、我々はまたのカップルを持っている
関係内のノードについて話をする用語

659
00:35:45,820 --> 00:35:46,680
互い。

660
00:35:46,680 --> 00:35:49,700
だから我々は、親を持つ
子供、兄弟姉妹。

661
00:35:49,700 --> 00:35:56,260
したがって、この場合には、3である
5,6、および7の親。

662
00:35:56,260 --> 00:36:00,370
だから、親が何であれです
あなたがしている何でも上記の一歩

663
00:36:00,370 --> 00:36:02,940
を参照すると、これだけ
家系図のような。

664
00:36:02,940 --> 00:36:07,090
うまくいけば、これはすべて少しある
ビットトライよりも直感的。

665
00:36:07,090 --> 00:36:10,970
>> 兄弟が持っている任意のものである
同じ親、右？

666
00:36:10,970 --> 00:36:13,470
彼らはここで同じレベルにしている。

667
00:36:13,470 --> 00:36:16,960
そして私は、あったように
と言って、子供たちはちょうどです

668
00:36:16,960 --> 00:36:22,630
下の一歩は何でもある
問題のノード、OK？

669
00:36:22,630 --> 00:36:23,470
涼しい。

670
00:36:23,470 --> 00:36:25,610
だから、バイナリツリー。

671
00:36:25,610 --> 00:36:31,450
誰もが一つに推測ハザードことができます
バイナリツリーの特性？

672
00:36:31,450 --> 00:36:32,770
>> 読者：マックス2葉。

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1：右。

674
00:36:33,478 --> 00:36:34,640
だから、2葉の最大。

675
00:36:34,640 --> 00:36:39,730
だから前に、このいずれかで、私たちはこの1つを持っていた
それは3を持っていましたが、バイナリツリーで、

676
00:36:39,730 --> 00:36:45,000
次の2つの最大を持っている
親ごと子どもたち、右？

677
00:36:45,000 --> 00:36:46,970
もう一つがあります
興味深い特徴。

678
00:36:46,970 --> 00:36:51,550
誰もがそれを知っていますか？

679
00:36:51,550 --> 00:36:52,620
バイナリツリー。

680
00:36:52,620 --> 00:37:00,350
>> だから、バイナリツリーは、すべてのものを持つことになります
the--上でこの1はsorted--ではありません

681
00:37:00,350 --> 00:37:05,320
しかしソートバイナリツリーで、
右の上のすべて

682
00:37:05,320 --> 00:37:08,530
親よりも大きい
左側のすべてのもの

683
00:37:08,530 --> 00:37:10,035
親よりも小さい。

684
00:37:10,035 --> 00:37:15,690
そして、それはクイズでした
知っておくととても良い前に質問、。

685
00:37:15,690 --> 00:37:19,500
だから我々はこれを定義する方法、
再び、私たちは別のノードを持っている。

686
00:37:19,500 --> 00:37:21,880
これは何と非常によく似ています？

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
二重に

689
00:37:28,836 --> 00:37:29,320
>> 聴衆：リンクリスト

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1：二重リンクリスト、右？

691
00:37:31,100 --> 00:37:33,690
だから我々はこれを交換した場合
前と次と、

692
00:37:33,690 --> 00:37:35,670
これは二重にリンクされたリストになります。

693
00:37:35,670 --> 00:37:40,125
しかし、この場合、我々は実際に
左右と、それはそれだしている。

694
00:37:40,125 --> 00:37:41,500
それ以外の場合は、全く同じだ。

695
00:37:41,500 --> 00:37:43,374
我々はまだ要素を持っている
あなたが探している、

696
00:37:43,374 --> 00:37:45,988
あなたがちょうど2つのポインタを持っている
次は何に行く。

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
うん、そう二分探索木。

699
00:37:51,870 --> 00:37:57,665
我々は上の、すべてのものに気づいた場合
右ここthan--大きい

700
00:37:57,665 --> 00:37:59,850
またはすべてをすぐに
ここで右に

701
00:37:59,850 --> 00:38:02,840
すべてのものよりも大きい
ここで以下である。

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> だから我々は、それを介して検索した場合
バイナリ検索に非常に近いはず

704
00:38:14,000 --> 00:38:14,910
ここでは、右か？

705
00:38:14,910 --> 00:38:17,640
代わりに探して除く
半分の配列で、

706
00:38:17,640 --> 00:38:21,720
私達はちょうど左のどちらかを見ている
側またはツリーの右側。

707
00:38:21,720 --> 00:38:24,850
それは少しシンプル取得するので、私は思います。

708
00:38:24,850 --> 00:38:29,300
>> だからあなたのルートがNULLの場合、
明らかにそれはちょうど偽です。

709
00:38:29,300 --> 00:38:33,470
それがあります場合は、明らかにそれは本当だ。

710
00:38:33,470 --> 00:38:35,320
それはより少ないなら、私たちは左を検索します。

711
00:38:35,320 --> 00:38:37,070
それはより大きいなら、
我々は権利を検索します。

712
00:38:37,070 --> 00:38:39,890
それは、正確にバイナリサーチのようなものだ
わずかに異なるデータ構造

713
00:38:39,890 --> 00:38:40,600
私たちが使用していること。

714
00:38:40,600 --> 00:38:42,790
代わりに、アレイの、
それだけでバイナリツリーです。

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> [OK]を、スタック。

717
00:38:48,090 --> 00:38:51,550
そしてまた、それは我々のように見える
少し時間があるかもしれません。

718
00:38:51,550 --> 00:38:54,460
我々が行う場合、私は行くことがうれしい
このいずれかの何度も繰り返し。

719
00:38:54,460 --> 00:38:56,856
[OK]を、のでスタック。

720
00:38:56,856 --> 00:39:02,695
誰もが何を覚えていますかstacks--
スタックのいずれかの特性？

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> [OK]を、私たちのほとんどので、私が思うに、
ダイニングで食べるhalls--

723
00:39:10,400 --> 00:39:13,100
私たちが好きではない可能性と同じくらい。

724
00:39:13,100 --> 00:39:16,900
しかし、明らかに、あなたはスタックと考えることができます
文字通りトレーのスタックとして

725
00:39:16,900 --> 00:39:18,460
や物事の積み重ね。

726
00:39:18,460 --> 00:39:21,820
そして、何が重要です
実現することがあるということです

727
00:39:21,820 --> 00:39:26,850
特性をsomething--
我々はそれがby--呼び出すことをLIFOです。

728
00:39:26,850 --> 00:39:28,450
誰もがそれが何の略か知っていますか？

729
00:39:28,450 --> 00:39:29,070
ビー·マイ·エスケイプ？

730
00:39:29,070 --> 00:39:30,650
>> 観客は：後入れ先出し。

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1：右、後入れ先出し。

732
00:39:32,250 --> 00:39:36,585
だから我々は知っていれば、私たちは物事をスタッキングしている場合
off--つかむための最も簡単な事、アップ

733
00:39:36,585 --> 00:39:39,570
そしておそらく唯一のことは、私たちはつかむことができる
私たちのスタックが大きくenough--であればオフ

734
00:39:39,570 --> 00:39:40,850
その最上位の要素です。

735
00:39:40,850 --> 00:39:43,460
だから、何でもが上に置くた
私たちはここに見るように、last--

736
00:39:43,460 --> 00:39:46,370
何でも押された
最もrecently--にあり

737
00:39:46,370 --> 00:39:51,160
最初になるだろう
我々はオフにポップなもの、OK？

738
00:39:51,160 --> 00:39:56,324
>> だから私たちはここに持っていることである
別のtypedef構造体。

739
00:39:56,324 --> 00:39:58,740
これは本当にただのようなものです
データ構造内のクラッシュコース

740
00:39:58,740 --> 00:40:01,650
そう君たち投げつけたくさんあり​​ます。

741
00:40:01,650 --> 00:40:02,540
私は知っている。

742
00:40:02,540 --> 00:40:04,970
だから、さらに別の構造体。

743
00:40:04,970 --> 00:40:06,740
構造用のイェーイ。

744
00:40:06,740 --> 00:40:16,660
>> そして、この場合には、いくつかのポインタの
いくつかの容量を持つ配列へ。

745
00:40:16,660 --> 00:40:20,830
だから、これは私たちのスタックを表し
ここでは、私たちの実際の配列のような

746
00:40:20,830 --> 00:40:22,520
それが私たちの要素を保持している。

747
00:40:22,520 --> 00:40:24,850
その後、ここで我々はいくつかのサイズを有する。

748
00:40:24,850 --> 00:40:31,170
>> そして一般的に、あなたが残しておきたい
あなたのスタックがどのように大きなのトラック

749
00:40:31,170 --> 00:40:36,180
それができるように、何が起こっているので、
あなたはサイズがわかっている場合であるためには、

750
00:40:36,180 --> 00:40:39,170
それはあなたが言うことができ、
[OK]を、私は容量でだ？

751
00:40:39,170 --> 00:40:40,570
私はより多くの何かを追加することはできますか？

752
00:40:40,570 --> 00:40:44,650
そして、それはまたあなたに伝えます
どこにあなたのスタックの最上位

753
00:40:44,650 --> 00:40:48,180
だからあなたは何を知っている
実際に離陸することができます。

754
00:40:48,180 --> 00:40:51,760
そして、それは実際に起こっている
ここにもう少し明確にする。

755
00:40:51,760 --> 00:40:57,350
>> だから、プッシュ、一つのことのために、あなたなら
プッシュを実現するために、これまであった

756
00:40:57,350 --> 00:41:01,330
私はちょうどあなたの、言っていたように
スタックは、右、限られた大きさを有している？

757
00:41:01,330 --> 00:41:03,990
私たちのアレイは、いくつかの能力を持っていた。

758
00:41:03,990 --> 00:41:04,910
それは配列です。

759
00:41:04,910 --> 00:41:08,930
それは固定サイズなので、私たちのことを行う必要があり
我々はより多くを入れていないことを確認してください

760
00:41:08,930 --> 00:41:11,950
私たちよりも私たちの配列へ
実際のためのスペースを持っている。

761
00:41:11,950 --> 00:41:16,900
>> だから、プッシュを作成しているとき
この関数は、あなたが最初にすることはOK、と言うである、

762
00:41:16,900 --> 00:41:18,570
私は、スタック内のスペースを持っていますか？

763
00:41:18,570 --> 00:41:23,330
、私がいない場合は、申し訳ありませんので、
私はあなたの要素を格納することはできません。

764
00:41:23,330 --> 00:41:28,980
私が行う場合は、保存したい
スタックの一番上にそれ、右？

765
00:41:28,980 --> 00:41:31,325
>> そして、これは私たちが持っている理由である
我々のサイズを追跡する。

766
00:41:31,325 --> 00:41:35,290
私たちは私たちのサイズを追跡していない場合は、
我々はそれをどこに置くかはわからない。

767
00:41:35,290 --> 00:41:39,035
私たちは、どのように多くのことを知らない
すでに我々のアレイに含まれる。

768
00:41:39,035 --> 00:41:41,410
当然のような方法があります
それ多分あなたはそれを行うことができます。

769
00:41:41,410 --> 00:41:44,610
あなたがNULLにすべてを初期化することができ
その後、最新のNULLをチェックし、

770
00:41:44,610 --> 00:41:47,950
しかしはるかに簡単なことは、ただで
と言って、[OK]を、サイズを追跡する。

771
00:41:47,950 --> 00:41:51,840
私が知っているように私は四つの要素を持っている
私のアレイでは、次のことは、そう

772
00:41:51,840 --> 00:41:55,930
我々は上に置くことを、私たちはしている
インデックス4で保存しようとして。

773
00:41:55,930 --> 00:42:00,940
そして、もちろん、これはことを意味
あなたが何かを正常にプッシュしました

774
00:42:00,940 --> 00:42:03,320
あなたのスタックに、あなた
サイズを増やしたい

775
00:42:03,320 --> 00:42:08,880
あなたが知っているように、あなたはとてもどこ
あなたがより多くのものを上にプッシュすることができます。

776
00:42:08,880 --> 00:42:12,730
>> だから我々はポップしようとしている場合
スタックから何か、

777
00:42:12,730 --> 00:42:16,072
最初のものになるかもしれないもの
我々はチェックしたいこと？

778
00:42:16,072 --> 00:42:18,030
あなたが取るしようとしている
あなたのスタックから何か。

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
あなたは確かありますです
あなたのスタックで何か？

781
00:42:24,781 --> 00:42:25,280
いいえ。

782
00:42:25,280 --> 00:42:26,894
だから何我々はチェックしたいかもしれません？

783
00:42:26,894 --> 00:42:27,810
>> 読者：[聞こえない]。

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1：サイズを​​確認してください？

785
00:42:29,880 --> 00:42:31,840
サイズ。

786
00:42:31,840 --> 00:42:38,520
だから我々はどうかを確認したい
私たちのサイズは[OK]を、0より大きい？

787
00:42:38,520 --> 00:42:44,970
それがある場合には、その後、我々は減少したい
0による私たちの大きさとはそれを返す。

788
00:42:44,970 --> 00:42:45,840
なぜ？

789
00:42:45,840 --> 00:42:49,950
>> 最初の1ではなかった
プッシュ、我々はそれをプッシュ

790
00:42:49,950 --> 00:42:52,460
サイズと、更新サイズへ。

791
00:42:52,460 --> 00:42:57,850
このケースでは、サイズをデクリメントしている
その後、それを摘採、それを脱ぐ

792
00:42:57,850 --> 00:42:58,952
私たちの配列から。

793
00:42:58,952 --> 00:42:59,826
なぜ我々はそれを行うのでしょうか？

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
だから私は私のスタック上に一つのことを持っている場合、
その時点で私のサイズ何でしょう？

796
00:43:11,811 --> 00:43:13,140
1。

797
00:43:13,140 --> 00:43:15,180
>> どこ素子1が格納されている？

798
00:43:15,180 --> 00:43:17,621
何されたインデックスにある？

799
00:43:17,621 --> 00:43:18,120
聴衆：0。

800
00:43:18,120 --> 00:43:19,060
SPEAKER 1：0。

801
00:43:19,060 --> 00:43:22,800
我々は、この場合はそう
常にsure--確認する必要があり

802
00:43:22,800 --> 00:43:27,630
代わりに返す
サイズから1を引いた、私たちのため

803
00:43:27,630 --> 00:43:31,730
我々の要素があることを知っている
1未満で保管される予定

804
00:43:31,730 --> 00:43:34,705
私たちのサイズが何であれ、この
ちょうどそれの世話をする。

805
00:43:34,705 --> 00:43:36,080
それはもう少しエレガントな方法だ。

806
00:43:36,080 --> 00:43:41,220
そして私達はちょうど私たちをデクリメント
サイズと、サイズを返す。

807
00:43:41,220 --> 00:43:42,330
ビー·マイ·エスケイプ？

808
00:43:42,330 --> 00:43:45,300
>> 読者：私はちょうど一般的に推測する、
なぜこのデータ構造はだろ

809
00:43:45,300 --> 00:43:47,800
有益である？

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1：それはあなたのコンテキストに依存します。

811
00:43:50,660 --> 00:43:57,420
理論のいくつかについてそう
[OK]をwith--作業している場合、

812
00:43:57,420 --> 00:44:02,750
有益なものがあるなら、私は見てみましょう
それは外よりに有益である

813
00:44:02,750 --> 00:44:05,420
CSの。

814
00:44:05,420 --> 00:44:15,780
スタック、あなたが必要とする任意の時点で
その何かを追跡する

815
00:44:15,780 --> 00:44:20,456
最も最近に追加されたときである
あなたはスタックを使用するようにするつもりだ。

816
00:44:20,456 --> 00:44:24,770
>> そして、私は良いと思うことはできません
今では右の例。

817
00:44:24,770 --> 00:44:29,955
しかし、いつでも最新の
事があなたにとって最も重要であり、

818
00:44:29,955 --> 00:44:31,705
それは時のスタックだ
便利になるだろう。

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
場合、私は考えるようにしようとしている
このための良いものがあります。

821
00:44:39,330 --> 00:44:43,720
私は次で良い例を考える場合
20分、私は間違いなくあなたを教えてくれます。

822
00:44:43,720 --> 00:44:49,455
>> しかし全体的に、何があるのならば、
私はどこで、最新の、最も言ったように

823
00:44:49,455 --> 00:44:52,470
それは、最も重要なのである
スタックは出番。

824
00:44:52,470 --> 00:44:58,860
キューのに対し、反対の一種である。

825
00:44:58,860 --> 00:44:59,870
そしてすべての小さな犬。

826
00:44:59,870 --> 00:45:00,890
これは正しい、素晴らしいではありませんか？

827
00:45:00,890 --> 00:45:03,299
私は私がすべきように感じる
ただバニーのビデオを持っている

828
00:45:03,299 --> 00:45:05,090
右側の真ん中に
君たちのためのセクション

829
00:45:05,090 --> 00:45:08,870
これは強烈なセクションであるためです。

830
00:45:08,870 --> 00:45:10,480
>> だから、キュー。

831
00:45:10,480 --> 00:45:12,710
基本的にキューはラインのようなものです。

832
00:45:12,710 --> 00:45:15,780
あなた私は確信してこの日常を使うよみんな、
ちょうど私たちのダイニングホールで好きです。

833
00:45:15,780 --> 00:45:18,160
だから我々はに行かなければならない
そして私は、私たちのトレーを取得

834
00:45:18,160 --> 00:45:21,260
あなたは並んで待つために持っていることを確認
スワイプまたはあなたの食糧を得るために。

835
00:45:21,260 --> 00:45:24,650
>> ここでの違いはそう
これは、FIFOであるということです。

836
00:45:24,650 --> 00:45:30,090
だから、LIFOは、まず、内の最後だった場合
アウト、FIFOは先入れ先出し、である。

837
00:45:30,090 --> 00:45:33,400
だから、これはあなたがどこに置いた何でもあり
最初にあなたの最も重要である。

838
00:45:33,400 --> 00:45:35,540
だから、待っていた場合には
line--であなたをすることができ

839
00:45:35,540 --> 00:45:39,130
あなたが行けば想像する
新しいiPhoneを取りに行く

840
00:45:39,130 --> 00:45:42,800
それはスタックがあった場所
行の最後の人は、最初にそれを得た

841
00:45:42,800 --> 00:45:44,160
人々はお互いを殺すだろう。

842
00:45:44,160 --> 00:45:49,800
>> だから、FIFOは、我々はすべての非常に精通している
ここで現実の世界のある、

843
00:45:49,800 --> 00:45:54,930
そしてそれはすべて実際に関係しています
この行全体を再作成するの種類

844
00:45:54,930 --> 00:45:56,900
構造キューイング。

845
00:45:56,900 --> 00:46:02,390
スタックと一方だから、
私たちは、プッシュとポップを持っている。

846
00:46:02,390 --> 00:46:06,440
キューでは、我々は持っている
エンキューおよびデキュー。

847
00:46:06,440 --> 00:46:10,910
そこで、基本的な手段をエンキュー
背中の上にそれを置く、

848
00:46:10,910 --> 00:46:13,680
とデキュー手段は取る
正面からオフ。

849
00:46:13,680 --> 00:46:18,680
だから私たちのデータ構造である
もう少し複雑。

850
00:46:18,680 --> 00:46:21,060
私たちはを追跡するための第2のものを持っている。

851
00:46:21,060 --> 00:46:25,950
>> これは、頭のないので、
右、正確にスタックです？

852
00:46:25,950 --> 00:46:27,900
これにより、スタックと同様の構成である。

853
00:46:27,900 --> 00:46:32,480
別の唯一の事は今ある
あなたはどう思いますか、このヘッドを持っている

854
00:46:32,480 --> 00:46:34,272
を追跡しようとしている？

855
00:46:34,272 --> 00:46:35,510
>> 読者：最初の1。

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1：右、
私たちが入れ最初。

857
00:46:38,685 --> 00:46:41,130
私たちのキューの先頭。

858
00:46:41,130 --> 00:46:42,240
誰でも行の最初です。

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
すべての権利、私たちは、エンキューを行う場合。

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
再び、のいずれか
これらのデータ構造、

863
00:46:55,920 --> 00:46:59,760
私たちは、アレイを扱っているので、
我々はスペースを持っているかどうかを確認する必要があります。

864
00:46:59,760 --> 00:47:03,290
>> これは言ってちょっと私に似ている
あなたたち、あなたがファイルを開いた場合、

865
00:47:03,290 --> 00:47:04,760
あなたがnullかどうかを確認する必要があります。

866
00:47:04,760 --> 00:47:08,330
これらのスタックのいずれか
そしてキューは、次のものが必要です

867
00:47:08,330 --> 00:47:13,420
私たちはだからスペースがあるかどうかを確認します
固定サイズの配列を扱う、

868
00:47:13,420 --> 00:47:16,030
我々はすべての5までhere-- 0、1を参照してくださいよう。

869
00:47:16,030 --> 00:47:20,690
だから我々は、その場合に何をすべきかのチェックがある
我々はまだスペースがあるかどうかを確認します。

870
00:47:20,690 --> 00:47:23,110
私たちのサイズが容量より少ない？

871
00:47:23,110 --> 00:47:28,480
>> もしそうであれば、我々はでそれを保存する必要がある
私たちは私たちのサイズを更新し、尾。

872
00:47:28,480 --> 00:47:30,250
だから、尾は、この場合には何でしょうか？

873
00:47:30,250 --> 00:47:32,360
これは、明示的に書き出されていない。

874
00:47:32,360 --> 00:47:33,380
どのように我々はそれを格納でしょうか？

875
00:47:33,380 --> 00:47:34,928
尾は何でしょう？

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> それでは、この例を見てみましょう。

878
00:47:40,190 --> 00:47:44,590
だから、これは右、サイズ6の配列である？

879
00:47:44,590 --> 00:47:49,220
そして、我々は、今、私たちのサイズは5である必要があります。

880
00:47:49,220 --> 00:47:55,240
我々はそれを入れたときに、それは起こっている
第五のインデックスに行くには、右？

881
00:47:55,240 --> 00:47:57,030
だから、最後尾に格納します。

882
00:47:57,030 --> 00:48:05,600
>> 尾を書くためのもう一つの方法だろうちょうど
サイズのインデックスで私達の配列は、正しいかも？

883
00:48:05,600 --> 00:48:07,560
これはサイズ5である。

884
00:48:07,560 --> 00:48:11,490
次のことは、5に入るだろう。

885
00:48:11,490 --> 00:48:12,296
クール？

886
00:48:12,296 --> 00:48:13,290
[OK]をクリックします。

887
00:48:13,290 --> 00:48:16,350
それは、少し複雑になります
私たちは頭をいじり始めるとき。

888
00:48:16,350 --> 00:48:17,060
はい？

889
00:48:17,060 --> 00:48:20,090
>> 読者：それは、その私たちを意味しています
配列を宣言したであろう

890
00:48:20,090 --> 00:48:23,880
五行長かったと
その後我々はそれに追加している？

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1：いいえ。

892
00:48:24,730 --> 00:48:27,560
したがって、この場合、これはスタックである。

893
00:48:27,560 --> 00:48:31,760
これが宣言されるだろう
サイズ6の配列として。

894
00:48:31,760 --> 00:48:37,120
この場合において、我々
ちょうど1スペース左を持っている。

895
00:48:37,120 --> 00:48:42,720
>> [OK]を、そのように一つのことは、この中にある
場合、私たちの頭が0である場合、

896
00:48:42,720 --> 00:48:45,270
それから私達はちょうどのサイズでそれを追加することができます。

897
00:48:45,270 --> 00:48:51,020
しかし、それは少しトリッキーを取得します
実際にので、それら

898
00:48:51,020 --> 00:48:52,840
スライドを持っていない
このため、私は行くよ

899
00:48:52,840 --> 00:48:56,670
それはではないので1を描画する
あなた一度かなり単純

900
00:48:56,670 --> 00:48:59,230
物事を退治開始。

901
00:48:59,230 --> 00:49:03,920
スタックと一方だから、
あなたは今まで持っている

902
00:49:03,920 --> 00:49:08,920
サイズが何であるかを心配する
あなたは上に何かを追加しているとき、

903
00:49:08,920 --> 00:49:15,710
キューにあなたも確認する必要があり
あなたの頭を占めていることを確認してください、

904
00:49:15,710 --> 00:49:20,760
キューに関するクールな理由
あなたが能力でいないのであればということで、

905
00:49:20,760 --> 00:49:23,040
あなたが実際にそれがラップアラウンドすることができます。

906
00:49:23,040 --> 00:49:28,810
>> [OK]を、ので、1 thing--ああ、
これはひどいチョークです。

907
00:49:28,810 --> 00:49:31,815
考慮すべきことの一つは、ケースです。

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
私達はちょうど5をやる。

910
00:49:37,140 --> 00:49:41,810
[OK]を、私たちはするつもりだ
頭がここにあると言う。

911
00:49:41,810 --> 00:49:46,140
これは、0、1、2、3、4である。

912
00:49:46,140 --> 00:49:54,210
>> 頭はそこだし、
それらの中にものを持ってください。

913
00:49:54,210 --> 00:49:58,340
そして、我々は右、で何かを追加したい？

914
00:49:58,340 --> 00:50:01,170
我々がする必要があるそうだ
知っている頭が常にあるということです

915
00:50:01,170 --> 00:50:05,620
このように動こうと
その後ループバックの周りに、OK？

916
00:50:05,620 --> 00:50:10,190
>> だから、このキューは、右のスペースを持って？

917
00:50:10,190 --> 00:50:13,950
これは非常に最初に空間を有し、
これの反対のようなもの。

918
00:50:13,950 --> 00:50:17,920
だから我々は何をする必要があるか、我々はある
尻尾を計算する必要があります。

919
00:50:17,920 --> 00:50:20,530
あなたはあなたのことがわかっている場合
頭部移動していない、尾

920
00:50:20,530 --> 00:50:24,630
でちょうどあなたの配列です
大きさの指標。

921
00:50:24,630 --> 00:50:30,000
>> しかし、現実には、あなたは、キューを使用している場合、
あなたの頭はおそらく更新されている。

922
00:50:30,000 --> 00:50:33,890
だから、何をする必要があるかである
実際にテールを計算します。

923
00:50:33,890 --> 00:50:39,990
だから、私たちがやっていることは、この式は、
ここで、私はあなたを聞かせするつもりですどの

924
00:50:39,990 --> 00:50:42,680
みんな、について考え、
その後、我々はそれについて話をしましょう​​。

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
だから、これは容量です。

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> だから、これは実際になります
あなたにそれを行うための方法を与える。

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
そのため、この場合、どのような？

931
00:51:04,330 --> 00:51:09,205
私たちの頭は1で、私たちのサイズは4です。

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
我々は5であることを法場合、我々は、0を取得
これはどこに我々はそれを入力すべきである。

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> それでは次のケースでは、
我々はこれを行うした場合、

936
00:51:26,080 --> 00:51:33,390
我々はOK、のが何かをデキューしましょう​​、と言う。

937
00:51:33,390 --> 00:51:34,390
我々はこれをデキュー。

938
00:51:34,390 --> 00:51:37,740
我々は正しい、この要素を取り出す？

939
00:51:37,740 --> 00:51:47,930
>> そして今、私たちの頭には、ここで指している
そして、我々は別のものを追加したいと思います。

940
00:51:47,930 --> 00:51:52,470
これは基本的に
バック私たちのラインの、右？

941
00:51:52,470 --> 00:51:55,450
キューは、アレイの周りにラップすることができます。

942
00:51:55,450 --> 00:51:57,310
つまり、主な違いの一つだ。

943
00:51:57,310 --> 00:51:58,780
スタックは、あなたがこれを行うことはできません。

944
00:51:58,780 --> 00:52:01,140
>> キューに、次のことができます
すべてのことの事項理由

945
00:52:01,140 --> 00:52:03,940
あなたは何を知っているということです
最も最近追加された。

946
00:52:03,940 --> 00:52:10,650
すべてがで追加されようとしているので
この左方向、この場合には、

947
00:52:10,650 --> 00:52:16,480
その後のことができ、ラップアラウンド
新しい要素を入れ続ける

948
00:52:16,480 --> 00:52:18,830
アレイの前で
それは本当にありませんので、

949
00:52:18,830 --> 00:52:20,640
もうアレイの前面。

950
00:52:20,640 --> 00:52:26,320
あなたがの始まりと考えることができます
あなたの頭が実際にある場所として配列。

951
00:52:26,320 --> 00:52:29,710
>> したがって、この式がどのようにある
あなたのしっぽを計算します。

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
それは理にかなっていますか？

954
00:52:35,610 --> 00:52:36,110
[OK]をクリックします。

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
[OK]を、デキュー、および
君たちは、10分を持っている

957
00:52:44,040 --> 00:52:48,840
私にどんな明確な質問をする
私はそれがクレイジーだ知っているので、あなたが、欲しい。

958
00:52:48,840 --> 00:52:51,980
>> すべての権利なので、同じway--中
君たちは気づいたかどうかは知りませんが、

959
00:52:51,980 --> 00:52:53,450
しかし、CSはすべてのパターンについてです。

960
00:52:53,450 --> 00:52:57,370
物事はかなりある
ほんの微調整と、同じ。

961
00:52:57,370 --> 00:52:58,950
ここでそのように同じこと。

962
00:52:58,950 --> 00:53:04,040
私たちは、実際に我々かどうかをチェックする必要があります
私たちのキュー内の何かを持っている、右？

963
00:53:04,040 --> 00:53:05,960
[OK]を、0よりも私たちのサイズも大きい、と言う？

964
00:53:05,960 --> 00:53:06,730
涼しい。

965
00:53:06,730 --> 00:53:10,690
>> 我々が行うなら、私たちは私たちの頭を、移動する
私はちょうどここに実証したものです。

966
00:53:10,690 --> 00:53:13,870
私たちは、1以上であることが私たちの頭を更新します。

967
00:53:13,870 --> 00:53:18,390
そして、我々は我々のをデクリメント
サイズと要素を返す。

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> はるかコンクリートがある
study.cs50.net上のコード、

970
00:53:26,250 --> 00:53:29,440
と私は非常に行くお勧めします
あなたは時間があれば、それを通じて、

971
00:53:29,440 --> 00:53:30,980
それだけの擬似コードであったとしても。

972
00:53:30,980 --> 00:53:35,980
そしてあなたたちはスルー話をしたい場合は、
1上の私と1は、私を教えてください

973
00:53:35,980 --> 00:53:37,500
知っている。

974
00:53:37,500 --> 00:53:38,770
私は幸せになるだろう。

975
00:53:38,770 --> 00:53:42,720
データ構造は、もし
あなたは、CS 124を取る、あなたはよ

976
00:53:42,720 --> 00:53:47,830
データ構造は非常に得ることを知っている
楽しさと、これは始まったばかりである。

977
00:53:47,830 --> 00:53:50,350
>> だから私はそれは難しいと知っている。

978
00:53:50,350 --> 00:53:51,300
それはOKです。

979
00:53:51,300 --> 00:53:52,410
私たちは、苦労しています。

980
00:53:52,410 --> 00:53:53,630
私はまだやる。

981
00:53:53,630 --> 00:53:56,660
だからそれについてはあまり心配しないでください。

982
00:53:56,660 --> 00:54:02,390
>> しかし、それは基本的にあなたのである
データ構造のクラッシュコース。

983
00:54:02,390 --> 00:54:03,400
私はそれがたくさんあることを知っている。

984
00:54:03,400 --> 00:54:06,860
その私たちは何がありますか
何度も何度も行きたいですか？

985
00:54:06,860 --> 00:54:09,400
私たちが通って話をしたい、何？

986
00:54:09,400 --> 00:54:10,060
はい？

987
00:54:10,060 --> 00:54:16,525
>> 読者：そのたとえば、そう
新しい尾は、その上で0になる？

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1：はい。

989
00:54:17,150 --> 00:54:18,230
読者：[OK]をクリックします。

990
00:54:18,230 --> 00:54:24,220
それではを通じて起こって、
あなたは1プラス4 or--があるんだけど

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1：だからあなたが言っていた、
我々は再びこれを行うに行きたいとき？

992
00:54:27,671 --> 00:54:28,296
聴衆：うん。

993
00:54:28,296 --> 00:54:38,290
あなたがゆうパックで考え出すされたかのようにどこにいる
あなたはその中から尾を計算する？

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1：だから尾
私はこれを変更しin--た。

995
00:54:44,260 --> 00:54:52,010
だからここに、この例では、これだった
私たちが見ている配列、OK？

996
00:54:52,010 --> 00:54:54,670
そこで、1、2、3、及び4にものを持っている。

997
00:54:54,670 --> 00:55:05,850
だから私たちは私たちの頭は、少なくとも1に等しい持っている
この点は、私たちの大きさは4に等しい。

998
00:55:05,850 --> 00:55:07,050
この時点で、右？

999
00:55:07,050 --> 00:55:08,960
>> あなたのすべては、そのような場合だ同意する？

1000
00:55:08,960 --> 00:55:14,620
だから我々は、頭プラスのサイズを行うもの
私たちに5を与え、その後、我々は5で国防省。

1001
00:55:14,620 --> 00:55:20,690
我々は0であることを教えてくれるもの、0を取得
我々はスペースを持っている私たちの尾は、場所です。

1002
00:55:20,690 --> 00:55:22,010
>> 読者：キャップは何ですか？

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1：容量。

1004
00:55:23,520 --> 00:55:24,020
ごめんなさい。

1005
00:55:24,020 --> 00:55:29,640
だから、あなたの配列のサイズです。

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
はい？

1008
00:55:36,047 --> 00:55:39,210
>> 読者：[聞こえない]の前に
我々は要素を返す？

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1：だから我々は動く
頭やモーメントを返す？

1010
00:55:46,270 --> 00:55:52,680
我々は1を動かすのであれば、サイズをデクリメント？

1011
00:55:52,680 --> 00:55:54,150
ちょっと待って。

1012
00:55:54,150 --> 00:55:55,770
私は間違いなく別のを忘れてしまった。

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
気にしない。

1015
00:56:01,990 --> 00:56:04,980
別の式がありません。

1016
00:56:04,980 --> 00:56:09,980
ええ、あなたは戻りたいだろう
頭とそれを戻す。

1017
00:56:09,980 --> 00:56:13,270
>> 聴衆：OK、このためで、
ポイント、ヘッドは0にあった、

1018
00:56:13,270 --> 00:56:18,452
そして、あなたは戻りたい
インデックス0、次にヘッド1を作る？

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1：右。

1020
00:56:19,870 --> 00:56:22,820
私は別のがあると思う
このようなの数式一種。

1021
00:56:22,820 --> 00:56:26,970
私は、トップに私の頭をそれを持っていない
私はあなたに間違ったものを与えたくない。

1022
00:56:26,970 --> 00:56:35,470
しかし、私はそれが完全に有効だと思う
たとえば、[OK]を、このelement--を保存何でも

1023
00:56:35,470 --> 00:56:40,759
頭の要素があなたのをデクリメントis--
サイズは、あなたの頭の上を移動し、リターン

1024
00:56:40,759 --> 00:56:41,800
どのような要素である。

1025
00:56:41,800 --> 00:56:44,760
それは完全に有効です。

1026
00:56:44,760 --> 00:56:45,260
[OK]をクリックします。

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
これではないような気が
most--のようにあなたがわからない

1029
00:56:53,560 --> 00:56:55,740
ここから歩いて行く
はい、私は試みを知っている、などである。

1030
00:56:55,740 --> 00:56:56,880
私はそれをすべてを得た。

1031
00:56:56,880 --> 00:56:57,670
大丈夫。

1032
00:56:57,670 --> 00:57:00,200
私は約束します。

1033
00:57:00,200 --> 00:57:05,240
しかし、データ構造は何かされていることを
それは慣れるのに時間がかかる。

1034
00:57:05,240 --> 00:57:10,010
最も難しいのはおそらく1
物事は、私は当然で、考える。

1035
00:57:10,010 --> 00:57:15,330
>> だから、それは間違いなくかかります
私at--反復と見て

1036
00:57:15,330 --> 00:57:20,050
本当にリンクされたリストを知りませんでした
私は彼らとあまりにも多くをやったまで、

1037
00:57:20,050 --> 00:57:22,550
同じ方法で、Iはなかった
本当にポインタを理解する

1038
00:57:22,550 --> 00:57:27,040
私は2つのためにそれを教えるために持っていたまで
年はそれで自分ののpsetを行う。

1039
00:57:27,040 --> 00:57:28,990
それは、繰り返しと多くの時間を要する。

1040
00:57:28,990 --> 00:57:32,600
そして最終的に、それは一種のクリックします。

1041
00:57:32,600 --> 00:57:36,320
>> しかし、その間に、あなたは親切があれば
何の高レベルの理解

1042
00:57:36,320 --> 00:57:39,321
これら行い、彼らの長所
何であるcons--

1043
00:57:39,321 --> 00:57:41,820
私たちは本当に強調する傾向が、
特にイントロのコースで。

1044
00:57:41,820 --> 00:57:45,511
同様に、なぜ我々は使います
アレイ全体のtry？

1045
00:57:45,511 --> 00:57:48,010
同様に、陽性は何ですか
それらのそれぞれのネガ？

1046
00:57:48,010 --> 00:57:51,610
>> とトレードオフを理解する
これらの構造のそれぞれの間

1047
00:57:51,610 --> 00:57:54,910
今ははるかに重要だものです。

1048
00:57:54,910 --> 00:57:58,140
狂気の1があるかもしれません
質問または2の

1049
00:57:58,140 --> 00:58:03,710
プッシュを実装するように依頼するつもりか
ポップまたはエンキューおよびデキューを実装します。

1050
00:58:03,710 --> 00:58:07,340
ほとんどの部分は、それを有する
より高いレベルの理解とより

1051
00:58:07,340 --> 00:58:09,710
されている直感的な把握の
実際よりも重要

1052
00:58:09,710 --> 00:58:11,250
それを実装することができる。

1053
00:58:11,250 --> 00:58:14,880
>> あなたのすべての場合、それは本当に素晴らしいことだろう
外に出て、試しを実装行くことができる、

1054
00:58:14,880 --> 00:58:19,720
しかし、我々はそれは必ずしもありません理解する
今、最も合理的なもの。

1055
00:58:19,720 --> 00:58:23,370
しかし、あなたはあなたがしたい場合は、あなたのPSETでできる
にし、次にあなたが練習を得るでしょう、

1056
00:58:23,370 --> 00:58:27,200
その後多分あなたはよ
実際にそれを理解しています。

1057
00:58:27,200 --> 00:58:27,940
はい？

1058
00:58:27,940 --> 00:58:30,440
>> 聴衆：OK、ものがあるので、
我々はPSETで使用するためのもの？

1059
00:58:30,440 --> 00:58:31,916
私はそれらのいずれかを使用する必要がありますか？

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1：はい。

1061
00:58:32,540 --> 00:58:34,199
つまり、あなたの選択肢を持っている。

1062
00:58:34,199 --> 00:58:36,740
私は、私たちができる、この場合には、推測
少しのpsetの話

1063
00:58:36,740 --> 00:58:40,480
私はこれらを走ったので。

1064
00:58:40,480 --> 00:58:47,779
だからあなたのpsetで、あなたを持っている
試行またはハッシュテーブルの選択。

1065
00:58:47,779 --> 00:58:49,570
一部の人々がしようとします
そして、ブルームフィルタを使用

1066
00:58:49,570 --> 00:58:51,840
しかし、それらは技術的には正しくありません。

1067
00:58:51,840 --> 00:58:55,804
彼らの確率的な性質のため、
彼らは時々偽陽性を与える。

1068
00:58:55,804 --> 00:58:57,095
彼らはしかし、中にクールな表情だ。

1069
00:58:57,095 --> 00:58:59,030
非常に見てお勧めします
それらで少なくとも。

1070
00:58:59,030 --> 00:59:03,260
しかし、あなたはあなたの選択を持っている
ハッシュテーブルとの間にトライ。

1071
00:59:03,260 --> 00:59:06,660
そして、それはどこになるだろう
あなたの辞書にロードします。

1072
00:59:06,660 --> 00:59:09,230
>> そして、あなたは選択する必要があります
あなたのハッシュ関数

1073
00:59:09,230 --> 00:59:13,420
どのように多くのあなたが選択する必要があります
バケットはあなたが持っている、それは異なります。

1074
00:59:13,420 --> 00:59:17,440
あなたがより多くのバケツを持っている場合と同様に、
多分それはより速く実行します。

1075
00:59:17,440 --> 00:59:22,790
しかし、多分あなたは無駄にしています
多くのスペースそのように、しかし。

1076
00:59:22,790 --> 00:59:26,320
あなたがそれを把握する必要があります。

1077
00:59:26,320 --> 00:59:27,140
ビー·マイ·エスケイプ？

1078
00:59:27,140 --> 00:59:29,875
>> 読者：あなたは、その前に言った
我々は他のハッシュ関数を使用することができ、

1079
00:59:29,875 --> 00:59:31,750
我々はする必要がないこと
ハッシュ関数を作成しますか？

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1：はい、右。

1081
00:59:32,666 --> 00:59:38,150
だから文字通りハッシュ関数のため、
Googleのような「ハッシュ関数」

1082
00:59:38,150 --> 00:59:40,770
そしていくつかのクールなものを探してください。

1083
00:59:40,770 --> 00:59:43,250
あなたが構築することが期待されていません
独自のハッシュ関数。

1084
00:59:43,250 --> 00:59:46,100
人々は彼らを過ごす
これらの事についての論文。

1085
00:59:46,100 --> 00:59:50,250
>> だから、あなた自身を構築する心配しないでください。

1086
00:59:50,250 --> 00:59:53,350
で開始する1オンラインを検索します。

1087
00:59:53,350 --> 00:59:56,120
そのうちのいくつかはあなたに持っている
少し操作する

1088
00:59:56,120 --> 00:59:59,430
作るために必ず戻り値の型は一致
やその他もろもろ、そう初めに、

1089
00:59:59,430 --> 01:00:02,420
私は何かを使用してお勧めします
多分ちょうどその本当に簡単

1090
01:00:02,420 --> 01:00:04,680
最初の文字でハッシュします。

1091
01:00:04,680 --> 01:00:08,760
そして、あなたはその作業をしたら、
クーラーハッシュ関数を組み込む。

1092
01:00:08,760 --> 01:00:09,260
ビー·マイ·エスケイプ？

1093
01:00:09,260 --> 01:00:13,020
>> 読者：試しかであるか、
効率的なしかし、like--ちょうど困難

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1：だから試し、私が思うに、
実装するために、直感的には難しいです

1095
01:00:15,880 --> 01:00:18,310
しかし非常に高速です。

1096
01:00:18,310 --> 01:00:20,620
しかし、より多くのスペースを占有します。

1097
01:00:20,620 --> 01:00:25,270
ここでも、業者の両方を最適化することができます
異なる方法や方法がありますto--

1098
01:00:25,270 --> 01:00:26,770
聴衆：どのように我々は、この上の等級がありますか？

1099
01:00:26,770 --> 01:00:27,540
それはありませんmatter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1：それで、あなたは、通常の方法を段階的だ。

1101
01:00:29,164 --> 01:00:31,330
あなたは、設計上の等級ことになるだろう。

1102
01:00:31,330 --> 01:00:36,020
あなたは、あなたがしたいですかどちらの方法
それはそれができるようにエレガントだことを確認してください

1103
01:00:36,020 --> 01:00:38,610
そしてそれができるように効率的。

1104
01:00:38,610 --> 01:00:41,950
しかし、あなたは、tryまたはハッシュを選択した場合
テーブル、限りそれが動作するように、

1105
01:00:41,950 --> 01:00:45,350
私たちはそれで満足しています。

1106
01:00:45,350 --> 01:00:48,370
そして、あなたはハッシュ何かを使用している場合
最初の文字で、それはいいのよ、

1107
01:00:48,370 --> 01:00:51,410
多分設計ワイズ様様。

1108
01:00:51,410 --> 01:00:53,410
我々はまた、到達している
このsemester--のポイント

1109
01:00:53,410 --> 01:00:55,340
あなたかどうかは知りません
あなたはならnoticed--男

1110
01:00:55,340 --> 01:00:58,780
PSETグレードは少し断る
デザインやその他もろもろの理由、

1111
01:00:58,780 --> 01:00:59,900
それは完全に罰金です。

1112
01:00:59,900 --> 01:01:02,960
それはどこにあなたのポイントになってきた
プログラムは、より複雑きている。

1113
01:01:02,960 --> 01:01:04,830
より多くの場所があります。
あなたが上で向上させることができます。

1114
01:01:04,830 --> 01:01:06,370
>> だから、完全に正常です。

1115
01:01:06,370 --> 01:01:08,810
それはあなたがしていることではありません
あなたのpsetに悪化しそう。

1116
01:01:08,810 --> 01:01:11,885
それはちょうど私たちが今あなたに難しくさいます。

1117
01:01:11,885 --> 01:01:13,732
だから、誰もがそれを感じています。

1118
01:01:13,732 --> 01:01:14,940
私はちょうどすべてのあなたのpsetを採点。

1119
01:01:14,940 --> 01:01:16,490
私は誰もがそれを感じていることを知っている。

1120
01:01:16,490 --> 01:01:19,600
>> だから気にしないでください。

1121
01:01:19,600 --> 01:01:23,580
そして、あなたはについてのご質問がある場合は
前のpsetまたはあなたが改善することができる方法、

1122
01:01:23,580 --> 01:01:27,760
私が試してみて、特定のコメント
場所が、時にはそれが手遅れ

1123
01:01:27,760 --> 01:01:30,840
と私は疲れる。

1124
01:01:30,840 --> 01:01:34,885
他のものはありますか
約データ構造？

1125
01:01:34,885 --> 01:01:37,510
私は、君たちが本当にないと確信している
もはやそれについて話をしたい、

1126
01:01:37,510 --> 01:01:42,650
がある場合しかし、私はうれしいです
それらの上に行くだけでなく、何でも

1127
01:01:42,650 --> 01:01:45,580
講義からこの過去
週または先週。

1128
01:01:45,580 --> 01:01:51,580
>> 私は、先週は、すべてのレビューでした知っている
我々はいくつかのレビューをスキップしている可能性

1129
01:01:51,580 --> 01:01:54,190
講義から。

1130
01:01:54,190 --> 01:01:58,230
私は答えることができる他の質問？

1131
01:01:58,230 --> 01:01:59,350
OK、大丈夫。

1132
01:01:59,350 --> 01:02:02,400
さて、皆さんは、早期に15分を出す。

1133
01:02:02,400 --> 01:02:08,370
>> 私は、これは少なくとも半有用だった願って、
と私は来週君たちが表示されます、

1134
01:02:08,370 --> 01:02:12,150
または木曜日の営業時間。

1135
01:02:12,150 --> 01:02:15,285
軽食のためにそこに要求されている
来週のために、それはことだ？

1136
01:02:15,285 --> 01:02:17,459
今日はお菓子を忘れてしまったので。

1137
01:02:17,459 --> 01:02:19,750
そして、私は最後のお菓子をもたらした
週が、それは、コロンブスデーだった

1138
01:02:19,750 --> 01:02:25,400
そう誰6人のようにありました
自分自身にキャンディの4袋を持っていた。

1139
01:02:25,400 --> 01:02:28,820
私はスターバーストをもたらすことができます
再びあなたが好きなら。

1140
01:02:28,820 --> 01:02:29,580
スターバースト？

1141
01:02:29,580 --> 01:02:32,250
OK、いいですね。

1142
01:02:32,250 --> 01:02:35,050
、素晴らしい一日みんなを持っている。

1143
01:02:35,050 --> 01:02:39,510