1
00:00:00,000 --> 00:00:03,423
>> [音楽再生]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG：セクションの週6へようこそ。

4
00:00:08,210 --> 00:00:11,620
私たちは、標準から外れました
火曜日の区間時間

5
00:00:11,620 --> 00:00:14,130
この素敵な日曜日の朝に午後。

6
00:00:14,130 --> 00:00:17,330
その誰もしていただきありがとうございます
真剣に、今日私に参加しましたが、

7
00:00:17,330 --> 00:00:18,170
拍手。

8
00:00:18,170 --> 00:00:20,600
>> これはかなり大きな努力です。

9
00:00:20,600 --> 00:00:23,600
私はほとんども、それをしませんでした
時間のアップが、それはOKでした。

10
00:00:23,600 --> 00:00:27,520
だから私はあなたのすべてを知っています
ただクイズにそれを作りました。

11
00:00:27,520 --> 00:00:30,370
まず第一に、へようこそ
そのの裏返し。

12
00:00:30,370 --> 00:00:32,917
>> 第二に、我々はそれについて話しましょう​​。

13
00:00:32,917 --> 00:00:34,000
私たちは、クイズについて話しましょう​​。

14
00:00:34,000 --> 00:00:35,700
私たちはどのようにについて話しましょう
あなたはクラスでやっています。

15
00:00:35,700 --> 00:00:36,550
あなたは大丈夫です。

16
00:00:36,550 --> 00:00:39,080
私はあなたのためのクイズを持っています
ここの最後にあなた、

17
00:00:39,080 --> 00:00:42,120
だから君たちは取りたい場合
完全に罰金それを見、。

18
00:00:42,120 --> 00:00:46,590
>> だから、すぐに私たちは始める前に、
次のように今日の議題です。

19
00:00:46,590 --> 00:00:48,430
あなたが見ることができるように、私たちはしています
基本的に迅速な発射

20
00:00:48,430 --> 00:00:52,120
データ構造の全体の束を通って
本当に、本当に、本当にすぐ。

21
00:00:52,120 --> 00:00:54,380
以下のようなので、それができなくなります
今日スーパーインタラクティブ。

22
00:00:54,380 --> 00:00:59,620
それはちょうど私が一種の叫びになるだろう
物事あなた、そして私はあなたを混同している場合、

23
00:00:59,620 --> 00:01:02,680
私は速すぎるつもりならば、私に知らせてください。

24
00:01:02,680 --> 00:01:05,200
彼らはただ、様々なデータです
構造、および一部として

25
00:01:05,200 --> 00:01:07,070
このため、あなたのPSETの
来週、あなたはよ

26
00:01:07,070 --> 00:01:10,340
それらのいずれかを実施するよう求められ、
おそらく、それらの2つthem-- 2の

27
00:01:10,340 --> 00:01:12,319
あなたのpsetインチ

28
00:01:12,319 --> 00:01:14,610
[OK]をので、私はちょうどに行きますよ
いくつかの発表で始まります。

29
00:01:14,610 --> 00:01:19,070
我々は、より多くのでスタックとキューの上に行きますよ
私たちはクイズの前に何をしたかよりも深さ。

30
00:01:19,070 --> 00:01:20,990
我々は、リンクの上に行きますよ
、もう一度、もう一度リスト

31
00:01:20,990 --> 00:01:23,899
何よりも深さより
私たちは、クイズの前に持っていました。

32
00:01:23,899 --> 00:01:26,440
そして、我々は、ハッシュについて話しましょう
テーブル、木や試行、どの

33
00:01:26,440 --> 00:01:28,890
すべてのあなたのpsetのためにかなり必要です。

34
00:01:28,890 --> 00:01:32,925
そして、我々はいくつかの上に行きますよ
pset5に役立つヒント。

35
00:01:32,925 --> 00:01:37,360
>> [OK]を、ので、クイズ0。

36
00:01:37,360 --> 00:01:41,090
平均は58％でした。

37
00:01:41,090 --> 00:01:45,370
それは非常に低く、従って皆​​さんすべて
合わせて、非常に、非常によくやりました

38
00:01:45,370 --> 00:01:46,510
それと。

39
00:01:46,510 --> 00:01:49,970
>> あなたがしている場合、かなり、親指のルールがあります
平均値の標準偏差内

40
00:01:49,970 --> 00:01:52,990
我々は少ないにしている、特に以来
快適なセクション、あなたは完全に罰金です。

41
00:01:52,990 --> 00:01:54,120
あなたが軌道に乗っています。

42
00:01:54,120 --> 00:01:55,190
人生は良いです。

43
00:01:55,190 --> 00:01:58,952
>> 私はそれがことを考えると怖いです知っています
私はこのクイズには40％のようになりました。

44
00:01:58,952 --> 00:02:00,160
私はこのクラスを失敗するつもりです。

45
00:02:00,160 --> 00:02:02,243
私はあなたを約束、あなたがいないなら
クラスを失敗するだろう。

46
00:02:02,243 --> 00:02:03,680
あなたは完全に罰金です。

47
00:02:03,680 --> 00:02:06,850
>> 乗り越え人のために
平均、印象的な、印象的な、

48
00:02:06,850 --> 00:02:08,780
以下のように、真剣によくやりました。

49
00:02:08,780 --> 00:02:09,689
私は私と一緒にそれらを持っています。

50
00:02:09,689 --> 00:02:11,730
それらを得るお気軽に
セクションの最後に。

51
00:02:11,730 --> 00:02:14,520
あなたがいずれかを持っているなら、私に教えてください
問題、彼らとの質問。

52
00:02:14,520 --> 00:02:17,204
私たちはあなたのスコアを追加した場合
間違って、私たちに知らせてください。

53
00:02:17,204 --> 00:02:21,240
>> [OK]を、pset5ので、これは本当にあります
意味でのエールのための奇妙な週

54
00:02:21,240 --> 00:02:24,240
私たちのPSETが原因であること
含む正午水曜日

55
00:02:24,240 --> 00:02:27,317
ので、それは実際に遅く日です
正午火曜日理論的に起因します。

56
00:02:27,317 --> 00:02:29,150
おそらく誰もが終わっていません
正午火曜日に。

57
00:02:29,150 --> 00:02:30,830
それは完全に罰金です。

58
00:02:30,830 --> 00:02:33,700
私たちは、オフィスの時間を持っているとしています
今夜だけでなく、月曜の夜。

59
00:02:33,700 --> 00:02:36,810
そして、すべてのセクション、今週はなります
実際にワークショップに変えられます、

60
00:02:36,810 --> 00:02:38,800
そうでポップ気軽に
あなたが望む任意のセクション、

61
00:02:38,800 --> 00:02:42,810
彼らは一種のミニPSETになるだろう
その上で助けをワークショップ。

62
00:02:42,810 --> 00:02:45,620
そうのような、これが唯一の部分であります
ここで、我々は材料を教えています。

63
00:02:45,620 --> 00:02:49,220
他のすべてのセクションは、フォーカシングされます
もっぱらのpsetのヘルプに。

64
00:02:49,220 --> 00:02:50,146
うん？

65
00:02:50,146 --> 00:02:52,000
>> 対象：営業時間はありますか？

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG：オフィス・アワー
ああtonight--、良い質問。

67
00:02:56,120 --> 00:03:00,580
私は思うの営業時間今夜
ティールまたはコモンズです。

68
00:03:00,580 --> 00:03:02,984
あなたがオンラインCS50をチェックします
あなたは、オフィスの時間に行きます

69
00:03:02,984 --> 00:03:05,650
そのスケジュールがあるはずです
それらのすべてがどこにあるかがわかります。

70
00:03:05,650 --> 00:03:07,954
>> 私は今夜​​のいずれかを知っています
または明日はティールです、

71
00:03:07,954 --> 00:03:10,120
私は、我々が持っているかもしれないと思います
他の夜のためのコモン。

72
00:03:10,120 --> 00:03:11,020
よく分かりません。

73
00:03:11,020 --> 00:03:11,700
良い質問。

74
00:03:11,700 --> 00:03:14,430
CS50に確認してください。

75
00:03:14,430 --> 00:03:18,780
>> クール、ご質問
三日のように、次のスケジュール？

76
00:03:18,780 --> 00:03:21,690
私はデビッドのような君たちを約束
これは丘の上である、と述べました。

77
00:03:21,690 --> 00:03:23,050
君たちはほとんどあります。

78
00:03:23,050 --> 00:03:24,644
わずか3日以上。

79
00:03:24,644 --> 00:03:26,310
そこに取得し、我々はすべて降りてくるでしょう。

80
00:03:26,310 --> 00:03:28,114
私たちは素敵なCS-無料休憩があるでしょう。

81
00:03:28,114 --> 00:03:28,780
お帰りなさい。

82
00:03:28,780 --> 00:03:30,779
私たちはウェブに飛び込みますよ
プログラミングと開発、

83
00:03:30,779 --> 00:03:35,150
比較して非常に楽しいですもの
他のpsetの一部に。

84
00:03:35,150 --> 00:03:37,974
そして、それは寒さもあり、よ
私たちはたくさんの楽しみがあるでしょう。

85
00:03:37,974 --> 00:03:38,890
我々は、より多くのキャンディがあるでしょう。

86
00:03:38,890 --> 00:03:39,730
キャンディのため申し訳ありません。

87
00:03:39,730 --> 00:03:40,945
私はお菓子を忘れてしまいました。

88
00:03:40,945 --> 00:03:43,310
それは荒い朝でした。

89
00:03:43,310 --> 00:03:46,340
だから、あなたたちは、ほとんどがあります
私はあなたたちの本当に誇りに思っています。

90
00:03:46,340 --> 00:03:49,570
>> [OK]を、ので、スタック。

91
00:03:49,570 --> 00:03:53,331
誰がジャックについての質問を追加しました
クイズの彼の服？

92
00:03:53,331 --> 00:03:53,830
誰も？

93
00:03:53,830 --> 00:03:56,500
[OK]を、それは大丈夫です。

94
00:03:56,500 --> 00:04:00,200
>> だから、基本的にすることができますように
絵ジャック、ここでこの男、

95
00:04:00,200 --> 00:04:03,350
服を取るのが大好き
スタックのトップのうち、

96
00:04:03,350 --> 00:04:05,750
彼は上に戻ってそれを置きます
彼の後にスタックが行われています。

97
00:04:05,750 --> 00:04:07,600
だから、このように、彼は決してありません
なっているように見えます

98
00:04:07,600 --> 00:04:10,090
の下に
彼の衣服にスタック。

99
00:04:10,090 --> 00:04:12,600
だから、これは一種の説明します
基本的なデータ構造

100
00:04:12,600 --> 00:04:16,610
スタックがどのように実装されるかの。

101
00:04:16,610 --> 00:04:20,060
>> 基本的に、考えます
オブジェクトの任意のスタックとして積み重ね

102
00:04:20,060 --> 00:04:24,900
あなたが一番上に物を置くと、どこ
あなたは上からそれらを飛び出し。

103
00:04:24,900 --> 00:04:28,600
だからLIFOは、私たちが好きな頭字語であります
最後には、まずアウトuse--します。

104
00:04:28,600 --> 00:04:32,480
だからの上部に続きます
スタックが出てくる最初のものです。

105
00:04:32,480 --> 00:04:34,260
それで二つの用語
我々は関連付けるのが好き

106
00:04:34,260 --> 00:04:36,190
それにプッシュとポップと呼ばれています。

107
00:04:36,190 --> 00:04:39,790
あなたは上に何かを押すと
スタック、あなたはバックアップそれをポップ。

108
00:04:39,790 --> 00:04:43,422
>> だから私は、これは一種のだと思います
あなたのそれらのための抽象的な概念

109
00:04:43,422 --> 00:04:45,630
誰のように見てみたいです
これの実際の実装

110
00:04:45,630 --> 00:04:46,740
現実の世界です。

111
00:04:46,740 --> 00:04:50,170
どのように多くのあなたのエッセイを書かれています
多分それが原因だったの1時間前のように、

112
00:04:50,170 --> 00:04:54,510
あなたが誤って巨大な削除しました
偶然のようなそれの塊、？

113
00:04:54,510 --> 00:04:58,560
そして、どのような制御を行います
我々はそれを戻すために使用できますか？

114
00:04:58,560 --> 00:05:00,030
コントロール-Z、ええ？

115
00:05:00,030 --> 00:05:03,640
コントロール-Zので、倍の量
コントロール-Zは私の命を救ったこと、

116
00:05:03,640 --> 00:05:08,820
、毎回私のお尻を保存しています
それは、スタックを介して実装です。

117
00:05:08,820 --> 00:05:13,020
>> 基本的にすべての情報
それは、Word文書上にあります

118
00:05:13,020 --> 00:05:15,080
それは意志でプッシュし、ポップされます。

119
00:05:15,080 --> 00:05:19,460
だから基本的にいつでもあなた
何かを削除、あなたはそれをバックポップ。

120
00:05:19,460 --> 00:05:22,820
そして、あなたは背中にそれを必要とする場合、あなた
Control-Cをが何をしている、それを押してください。

121
00:05:22,820 --> 00:05:26,770
だから現実世界の機能
どのように単純なデータ構造の

122
00:05:26,770 --> 00:05:28,690
あなたの日常生活を支援することができます。

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> だから、構造体はそのようです
私たちは実際にスタックを作成します。

125
00:05:40,150 --> 00:05:44,720
それから、構造体を定義し入力し、
私たちは、一番下にあるスタックを呼び出します。

126
00:05:44,720 --> 00:05:47,440
そして、スタック内の、
我々は2つ​​のパラメータを持っています

127
00:05:47,440 --> 00:05:51,580
私たちは基本的に操作することができ、
私たちは、charスター文字列能力を持っています。

128
00:05:51,580 --> 00:05:55,150
>> それはやっているすべてのこと
配列を作成しています

129
00:05:55,150 --> 00:05:58,835
私たちは、あなたが好きな格納できます
これは私たちがその能力を決定することができます。

130
00:05:58,835 --> 00:06:01,990
容量は、単に最大量であり、
アイテムは、我々はこの配列に入れることができます。

131
00:06:01,990 --> 00:06:05,660
int型のサイズが保持するカウンタであります
現在どのように多くの項目のトラック

132
00:06:05,660 --> 00:06:07,850
スタックインチ

133
00:06:07,850 --> 00:06:11,860
それでは、私たちは、A、を追跡することができます
両方の実際のスタックがどのように大規模な、

134
00:06:11,860 --> 00:06:14,850
そして、B、どのくらいそのスタックの
我々はしたくないので、私たちは満たさ

135
00:06:14,850 --> 00:06:18,800
私たちの能力が何であるかを超えるオーバーフローします。

136
00:06:18,800 --> 00:06:24,340
>> 例えば、この素敵なそう
質問はクイズにありました。

137
00:06:24,340 --> 00:06:28,160
基本的に私たちはプッシュしない方法
スタックの一番上に。

138
00:06:28,160 --> 00:06:28,830
非常にシンプル。

139
00:06:28,830 --> 00:06:30,621
あなたがそれを見れば、
我々はこの中を歩きますよ。

140
00:06:30,621 --> 00:06:32,640
[聞こえない]場合size--
覚えて、いつでもあなた

141
00:06:32,640 --> 00:06:35,300
いずれにもアクセスしたいです
構造内のパラメータ、

142
00:06:35,300 --> 00:06:40,320
あなたはstruct.parameterの名前を行います。

143
00:06:40,320 --> 00:06:42,720
>> この場合、sは
私たちのスタックの名前。

144
00:06:42,720 --> 00:06:46,230
我々は、サイズにアクセスしたいです
それを、私たちはs.sizeありません。

145
00:06:46,230 --> 00:06:50,280
サイズがないようであれば、
容量に等しいか、または限り

146
00:06:50,280 --> 00:06:52,940
それは容量以下だとして、
ここでも動作します。

147
00:06:52,940 --> 00:06:57,180
>> あなたは内部にアクセスしたいです
あなたのスタックの、s.stringsので、

148
00:06:57,180 --> 00:07:00,790
あなたはその新しい番号を置くつもりです
あなたはそこに挿入すること。

149
00:07:00,790 --> 00:07:05,030
ちょうど私たちがしたいと言ってみましょう
スタックにint型のnを挿入し、

150
00:07:05,030 --> 00:07:08,905
我々はs.stringsを行うことができ、
ブラケット、s.sizeは、nに等しいです。

151
00:07:08,905 --> 00:07:11,030
どこサイズがあるので
現在スタックにあります

152
00:07:11,030 --> 00:07:14,590
我々は、プッシュするつもりなら
その上に、私たちだけでアクセス

153
00:07:14,590 --> 00:07:17,370
どこサイズであります
スタックの現在の膨満感、

154
00:07:17,370 --> 00:07:21,729
我々はそれにint型のnを押してください。

155
00:07:21,729 --> 00:07:24,770
そして、我々はことを確認します
我々はまた、n個のサイズをインクリメントしています

156
00:07:24,770 --> 00:07:27,436
私たちはきた私たちを追跡することができます
スタックに余分なものを追加しました。

157
00:07:27,436 --> 00:07:29,660
今、私たちはより大きなサイズを有します。

158
00:07:29,660 --> 00:07:33,196
これは、ここに意味がありますか
それがどのように動作するか、論理的に皆、？

159
00:07:33,196 --> 00:07:34,160
それは一種の速かったです。

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
聴衆：あなたはオーバー行くことができます
s.stringss.strings【s.size]再び？

162
00:07:42,160 --> 00:07:45,808
ANDI PENG：確かに、そう何がします
s.size現在私たちを与えますか？

163
00:07:45,808 --> 00:07:47,440
観客：それは現在のサイズです。

164
00:07:47,440 --> 00:07:50,890
ANDI PENG：その通りなので、
私たちのサイズがである​​現在のインデックス、

165
00:07:50,890 --> 00:07:57,780
そのため、私たちは新たな整数を配置します
我々はs.sizeに挿入すること。

166
00:07:57,780 --> 00:07:58,760
それは理にかなっていますか？

167
00:07:58,760 --> 00:08:01,110
s.stringsため、すべてのこと
配列の名前です。

168
00:08:01,110 --> 00:08:03,510
それはすべてがアクセスしています
私たちの構造内の配列、

169
00:08:03,510 --> 00:08:06,030
そして私たちがしたい場合は
そのインデックスにn個を配置し、

170
00:08:06,030 --> 00:08:09,651
我々はそれにアクセスすることができます
使用してブラケットをs.size。

171
00:08:09,651 --> 00:08:10,150
クール。

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> すべての権利、ポップ、私はそれを擬似コード
あなたたちが、同様のコンセプトのため。

174
00:08:18,916 --> 00:08:19,790
それは理にかなっていますか？

175
00:08:19,790 --> 00:08:22,310
サイズが大きい場合
ゼロよりも、あなた

176
00:08:22,310 --> 00:08:25,350
あなたが何かをしたいことを知っています
サイズがない場合は理由アウト

177
00:08:25,350 --> 00:08:27,620
ゼロより大きく、そしてあなた
スタックには何もありません。

178
00:08:27,620 --> 00:08:29,840
>> だから、あなただけ実行したいです
このコード、それができるだけで

179
00:08:29,840 --> 00:08:32,320
ポップするものがある場合にポップ。

180
00:08:32,320 --> 00:08:35,830
そのようにサイズが大きい場合
0よりも、私たちマイナスサイズ。

181
00:08:35,830 --> 00:08:40,020
我々は大きさを減分してから戻ります
それのために内部で何でもあります

182
00:08:40,020 --> 00:08:42,710
ポップし、私たちがしたいです
保存されているものは何でもアクセス

183
00:08:42,710 --> 00:08:45,694
スタックの先頭のインデックスです。

184
00:08:45,694 --> 00:08:46,610
すべてが理にかなって？

185
00:08:46,610 --> 00:08:49,693
私が作った場合、あなたたちは、これを書き出します
あなたたちはそれを書くことができるでしょうか？

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
[OK]を、あなたたちはそれで遊ぶことができます。

188
00:08:53,570 --> 00:08:55,252
あなたはそれを取得しない場合、心配はありません。

189
00:08:55,252 --> 00:08:57,460
私たちは、コーディングする時間を持っていません
それアウト今日我々がきたので、

190
00:08:57,460 --> 00:08:59,959
これらの構造の多くを持っ
基本的に通過するが、これに

191
00:08:59,959 --> 00:09:02,214
擬似コード、非常に、非常に似てプッシュします。

192
00:09:02,214 --> 00:09:03,380
ただ、ロジックに沿って従ってください。

193
00:09:03,380 --> 00:09:06,092
あなたはすべてのアクセスしていることを確認してください
正しく構造体の特徴。

194
00:09:06,092 --> 00:09:06,574
うん？

195
00:09:06,574 --> 00:09:09,282
>> 聴衆：ウィルこれらのスライドと
この全体のことは今日までっぽいこと？

196
00:09:09,282 --> 00:09:11,586
ANDI PENG：常に、うん。

197
00:09:11,586 --> 00:09:13,710
私が配置しようとするつもりです
このアップ後の時間のように。

198
00:09:13,710 --> 00:09:16,626
私はデビッド、ダビデはしようとしますメールでお知らせいたします
この後の時間のようにそれを置きます。

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> [OK]を、ので、我々は、この他に移動します
素敵なデータ構造は、キューと呼ばれます。

201
00:09:25,470 --> 00:09:30,140
あなたたちはここで見ることができるように、
私たちの中で、英国のキュー、

202
00:09:30,140 --> 00:09:32,010
それはすべての行です。

203
00:09:32,010 --> 00:09:34,680
何に反してそう
あなたはスタックがあると思いますが、

204
00:09:34,680 --> 00:09:37,750
キューは、正確に何であります
論理的に、あなたはそれだと思います。

205
00:09:37,750 --> 00:09:41,914
これは、FIFOのルールが保持しています
これはファーストイン、ファーストアウトです。

206
00:09:41,914 --> 00:09:43,705
あなたが最初にしている場合
ライン内の1つ、あなたがしています

207
00:09:43,705 --> 00:09:46,230
最初のもの
ラインから出てきます。

208
00:09:46,230 --> 00:09:49,680
>> だから我々はこれを呼び出すために好きなもの
デキューとエンキューされます。

209
00:09:49,680 --> 00:09:52,380
私たちは何かを追加したい場合
私たちのキューに、私たちはエンキュー。

210
00:09:52,380 --> 00:09:55,690
我々はデキュー、または利用したい場合
何かが離れて、​​我々はデキュー。

211
00:09:55,690 --> 00:10:03,350
>> 我々は一種のだそう同じ感覚
我々の固定サイズの要素を作成します

212
00:10:03,350 --> 00:10:06,500
特定の保存することができます
物事が、我々はこともできます

213
00:10:06,500 --> 00:10:10,100
我々が配置している変更
それらの内部パラメータ

214
00:10:10,100 --> 00:10:13,140
の種類に基づいて、
機能我々が欲しいです。

215
00:10:13,140 --> 00:10:16,700
だから、最後のを望んでいた、スタック
1、N個の第1の1した可能性があります。

216
00:10:16,700 --> 00:10:19,800
キューは、我々は最初のものをしたいです
で出て最初にすることができます。

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> だから、構造型
あなたが見ることができるように、定義され、

219
00:10:26,710 --> 00:10:29,470
それは少し違います
スタックがあったものから

220
00:10:29,470 --> 00:10:33,120
ためだけでなく、我々は維持する必要があります
サイズが現在どこのトラック、

221
00:10:33,120 --> 00:10:37,420
我々はまた、ヘッドのトラックを維持したいです
だけでなく、どこに我々は現在。

222
00:10:37,420 --> 00:10:39,580
だから私はそれが簡単だと思います
私はこれを描きます。

223
00:10:39,580 --> 00:10:53,270
それでは、私たちはキューを持って想像してみましょう、
それでは、ヘッドが右ここにあるとしましょう​​。

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
行の先頭には、してみましょう
ただ、それが現在だと言います

226
00:10:58,310 --> 00:11:01,809
我々は挿入したいです
キューに何か。

227
00:11:01,809 --> 00:11:04,350
私は基本的にサイズを呼ぶつもりです
尾と同じものであり、

228
00:11:04,350 --> 00:11:06,314
あなたのキューがあるどこの終わり。

229
00:11:06,314 --> 00:11:07,730
ちょうどサイズはここで言ってみましょう。

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> それでは、どのよう1都合良くはありません
キューに何かを挿入しますか？

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
どのような指標我々が配置したいです
我々は挿入する場所。

234
00:11:24,130 --> 00:11:29,320
これはあなたの始まりである場合
キューに入れ、これはそれの終わりです

235
00:11:29,320 --> 00:11:31,860
我々がそれを行うのか、大きさ、
次のオブジェクトを追加したいですか？

236
00:11:31,860 --> 00:11:32,920
>> 聴衆：[聞こえません]

237
00:11:32,920 --> 00:11:35,920
ANDI鵬：まさに、あなたが追加したいです
それはあなたがそれを書かれているに応じて。

238
00:11:35,920 --> 00:11:37,840
このいずれかが空白であるか、それが空白になっています。

239
00:11:37,840 --> 00:11:42,630
だから、おそらくそれを追加したいです
こちらのサイズis--場合

240
00:11:42,630 --> 00:11:50,540
これらはすべて完全であれば、あなたがしたいです
右、右ここでそれを追加するには？

241
00:11:50,540 --> 00:11:57,150
>> 非常に、非常にしながら、そしてそうそれは、です
シンプルではなく、かなり常に正しいです

242
00:11:57,150 --> 00:12:00,690
主な違いのため
キューとスタックの間

243
00:12:00,690 --> 00:12:04,350
キューができるということです
実際に操作することが

244
00:12:04,350 --> 00:12:06,980
そのように頭の変更
希望する場所に応じて

245
00:12:06,980 --> 00:12:08,650
あなたのキューの先頭が開始します。

246
00:12:08,650 --> 00:12:11,900
その結果、あなたの尾
また、変更する予定です。

247
00:12:11,900 --> 00:12:14,770
だから見てみましょう
今、このコード。

248
00:12:14,770 --> 00:12:18,620
君たちもするように求めていたように
エンキュー、クイズに書き出します。

249
00:12:18,620 --> 00:12:22,580
多分私達はなぜを通して話しましょう
答えはそれが何であったかでした。

250
00:12:22,580 --> 00:12:26,790
>> 私はかなり、1にこのラインに合うことができませんでした
コー​​ドの本質的にこ​​の作品

251
00:12:26,790 --> 00:12:29,030
1行でなければなりません。

252
00:12:29,030 --> 00:12:30,140
30秒のようにお過ごしください。

253
00:12:30,140 --> 00:12:33,000
見てください、とその理由を参照してください。
これは、ある方法です。

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> 非常に、非常によく似た構造体に、非常に、非常に
前回と同様の構造

256
00:12:55,420 --> 00:12:58,090
おそらく以外のスタック
1行のコード。

257
00:12:58,090 --> 00:13:01,190
そして、1行のコードこと
機能性を決定します。

258
00:13:01,190 --> 00:13:03,900
そして、それは本当に差別化
スタックからキュー。

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> 誰もが刺しを取りたいです
あなたがきた理由を説明する時

261
00:13:22,010 --> 00:13:24,980
ここでは、この複雑なものがあるの？

262
00:13:24,980 --> 00:13:27,845
私たちは、のリターンを見ます
素晴らしい友人モジュラス。

263
00:13:27,845 --> 00:13:31,020
あなたたちはすぐに来るように
プログラミングに認識するためには、

264
00:13:31,020 --> 00:13:34,910
ほとんどいつでもあなたが何かを必要とします
何を包み込むように、

265
00:13:34,910 --> 00:13:36,850
弾性率は、それを行うための方法になるだろう。

266
00:13:36,850 --> 00:13:40,510
だから、それを知っている、誰もが欲しいん
コー​​ド行を説明してみてくださいするには？

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
うん、すべての答えがあります
一般に認められたと歓迎。

269
00:13:47,507 --> 00:13:48,840
観客は：あなたは私に話していますか？

270
00:13:48,840 --> 00:13:49,506
ANDI PENG：うん。

271
00:13:49,506 --> 00:13:56,200
聴衆：ああ、ない申し訳ありません。

272
00:13:56,200 --> 00:14:00,250
ANDI PENG：OK、そうしましょう
このコードを歩きます。

273
00:14:00,250 --> 00:14:03,642
あなたがしようとしているとき
キューに何かを追加、

274
00:14:03,642 --> 00:14:08,510
ヘッドが発生した場合には美しいです
右ここに、それは私たちのために非常に簡単です

275
00:14:08,510 --> 00:14:10,960
ただ最後に移動します
右の何かを挿入？

276
00:14:10,960 --> 00:14:14,690
しかし、キューの全体のポイントは、
ヘッドが実際に動的にできること

277
00:14:14,690 --> 00:14:17,280
どこに応じて変化します
私たちのqのスタートになりたいです、

278
00:14:17,280 --> 00:14:19,880
そのように、尾
また、変更する予定です。

279
00:14:19,880 --> 00:14:31,100
>> だから、これはなかったことを想像します
キューむしろこれは、キューがありました。

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
ヘッドが右ここにあるとしましょう​​。

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
私たちのキューがこのように見えたとしましょう​​。

284
00:14:56,980 --> 00:15:00,190
我々はどこにシフトしたい場合
行の先頭であり、

285
00:15:00,190 --> 00:15:03,400
我々は頭をずらしましょう
この方法ここサイズ。

286
00:15:03,400 --> 00:15:07,100
>> 今、私たちはに何かを追加したいです
このキューが、あなたたちが見ることができるよう、

287
00:15:07,100 --> 00:15:11,150
それだけのように単純ではありません
サイズの後にあるものは何でも追加

288
00:15:11,150 --> 00:15:13,630
その後、私たちは外に実行されるため
当社の実際の配列の境界。

289
00:15:13,630 --> 00:15:16,190
私たちは本当に追加したい場合はここにあります。

290
00:15:16,190 --> 00:15:18,610
それはキューの美しさです
それはそれは、視覚的に、私たちにあります

291
00:15:18,610 --> 00:15:22,380
行はこのように書きますように見えます、
しかし、データ構造に格納されているとき、

292
00:15:22,380 --> 00:15:29,370
彼らはサイクルなどを与えます。

293
00:15:29,370 --> 00:15:32,360
それは一種のラップアラウンド
前と同じように

294
00:15:32,360 --> 00:15:34,780
ラインもラップすることができていること
どこに応じて周り

295
00:15:34,780 --> 00:15:36,279
なるように行の先頭にしたいです。

296
00:15:36,279 --> 00:15:38,630
そして、私たちが取る場合
ここで下を向いて、してみましょう

297
00:15:38,630 --> 00:15:40,880
私たちが作成したいと言います
関数はエンキューと呼ばれます。

298
00:15:40,880 --> 00:15:43,980
我々は、Qへのint nを追加したいです。

299
00:15:43,980 --> 00:15:49,250
もしq.size q--我々は我々のデータ呼ぶことにします
私たちのqueue.sizeがない場合structure--

300
00:15:49,250 --> 00:15:52,520
容量の場合、または同等
それは容量よりも少ないですが、

301
00:15:52,520 --> 00:15:55,120
q.stringsは、当社のQ内の配列です。

302
00:15:55,120 --> 00:15:58,380
私たちは、設定しようとしています
そのq.headsに等しく、

303
00:15:58,380 --> 00:16:02,730
これは右ここにあり、プラスq.size
容量によって弾性率、これ

304
00:16:02,730 --> 00:16:04,290
この辺り私たちをバックラップします。

305
00:16:04,290 --> 00:16:08,040
>> したがって、この例では、インデックス
頭の右側、1ですか？

306
00:16:08,040 --> 00:16:11,480
サイズのインデックスは0、1、2、3、4です。

307
00:16:11,480 --> 00:16:19,500
だから我々は1プラス4モジュラスを行うことができます
5である私たちの能力によって。

308
00:16:19,500 --> 00:16:20,920
それは、私たちに何を与えるのでしょうか？

309
00:16:20,920 --> 00:16:23,270
そのインデックスとは何ですか
このから出てきますか？

310
00:16:23,270 --> 00:16:24,080
>> 聴衆：0。

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG：0、どの
右ここにあることを起こります、

312
00:16:27,870 --> 00:16:30,640
そのため、我々はできるようにしたいです
右ここに挿入します。

313
00:16:30,640 --> 00:16:34,730
ので、ここで、この式は、種
ただの数字で動作します

314
00:16:34,730 --> 00:16:36,750
場所に応じてあなたの
頭とあなたのサイズがあります。

315
00:16:36,750 --> 00:16:38,541
あなたはどのようなものを知っていれば
物事はあなたが知っている、あります

316
00:16:38,541 --> 00:16:43,170
あなたが挿入したい場所を正確に
何があなたのキューの後です。

317
00:16:43,170 --> 00:16:44,640
それは誰にでも意味がありますか？

318
00:16:44,640 --> 00:16:48,560
>> 私は、脳のようなものを知っています
特にこの以来のティーザー

319
00:16:48,560 --> 00:16:50,512
あなたのクイズの余波​​で来ました。

320
00:16:50,512 --> 00:16:52,220
しかし、うまくいけば、誰も
今理解することができます

321
00:16:52,220 --> 00:16:57,800
なぜこの溶液またはこの
関数は、それがあることの方法です。

322
00:16:57,800 --> 00:16:59,840
その上のビットは不明で誰ですか？

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK。

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> そして今、あなたの場合
この、デキューしたかったです

327
00:17:09,970 --> 00:17:15,240
私たちの頭がシフトされることになる場所です
我々はデキューした場合ので、

328
00:17:15,240 --> 00:17:17,030
我々はqの端を取ることはありません。

329
00:17:17,030 --> 00:17:19,130
私たちは頭を取りたいですよね？

330
00:17:19,130 --> 00:17:24,260
その結果、ヘッドが変更しようとしています、
あなたはエンキュー時に、なぜ、それは、あります

331
00:17:24,260 --> 00:17:26,800
あなたはを追跡するために持っています
どこにあなたの頭とあなたのサイズ

332
00:17:26,800 --> 00:17:29,450
挿入することができるようになっています
正しい位置に挿入します。

333
00:17:29,450 --> 00:17:32,740
>> だからあなたがデキュー時に、
私もそれを擬似コード。

334
00:17:32,740 --> 00:17:35,480
あなたがしたい場合にお気軽に
これをコード化しようとしています。

335
00:17:35,480 --> 00:17:36,980
あなたは正しい、ヘッドを移動したいですか？

336
00:17:36,980 --> 00:17:39,320
私はデキューしたい場合は、私
頭の上に移動します。

337
00:17:39,320 --> 00:17:40,800
これは頭​​になります。

338
00:17:40,800 --> 00:17:45,617
>> そして、私たちの現在のサイズを希望
引くために私たちは、もはや

339
00:17:45,617 --> 00:17:46,950
配列の4つの要素があります。

340
00:17:46,950 --> 00:17:51,370
我々は3つだけを持っている、と我々はしたいです
内部に格納されていたものは何でも返します

341
00:17:51,370 --> 00:17:56,260
頭の我々はこれを利用したいので、
スタックに非常に非常によく似た値アウト。

342
00:17:56,260 --> 00:17:58,010
ちょうどあなたが取っています
別の場所から、

343
00:17:58,010 --> 00:18:01,770
あなたはあなたのポインタを再割り当てする必要があります
結果として、別の場所へ。

344
00:18:01,770 --> 00:18:03,890
論理的には、誰もが従いますか？

345
00:18:03,890 --> 00:18:05,690
グレート。

346
00:18:05,690 --> 00:18:10,156
>> [OK]を、私たちは少し話をするつもりです
リンクされたリストについての深さより

347
00:18:10,156 --> 00:18:13,280
彼らは非常に、非常に価値があるだろうから
今週の過程であなたのために

348
00:18:13,280 --> 00:18:14,964
pset。

349
00:18:14,964 --> 00:18:17,130
あなたたちのようにリンクされたリスト、
、彼らはすべてを覚えています

350
00:18:17,130 --> 00:18:22,570
特定のノードであるノードがあります
値とポインタの両方の値

351
00:18:22,570 --> 00:18:26,290
それは、一緒にリンクされています
これらのポインタによって。

352
00:18:26,290 --> 00:18:29,880
そしてそう構造方法について
ここでは、ノードを作成し、私たちです

353
00:18:29,880 --> 00:18:33,569
である、int型nを持っているものは何でも
店舗や文字列のnの値

354
00:18:33,569 --> 00:18:35,610
またはあなたがしたいものは何でも
char型のスターnは、それを呼び出します。

355
00:18:35,610 --> 00:18:41,482
ポインタである構造体のノード星、
あなたは、各ノードで持つようにしたいことを、

356
00:18:41,482 --> 00:18:43,690
あなたはそれを持っているつもりです
次の方へのポインタポイント。

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
あなたは頭を持っています
だリンクリストの

359
00:18:50,040 --> 00:18:53,140
残りを指すように行きます
ようになどの値

360
00:18:53,140 --> 00:18:55,290
あなたは、最終的に最後に到達するまで。

361
00:18:55,290 --> 00:18:58,040
そして、この最後のノードだけです
ポインタを持っていないつもり。

362
00:18:58,040 --> 00:18:59,952
それはを指すように起こっています
nullの場合、それはときです

363
00:18:59,952 --> 00:19:01,910
あなたがヒットしました知っています
あなたのリンクリストの末尾

364
00:19:01,910 --> 00:19:04,076
あるとき、あなたの最後のポインタ
何を指していません。

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> だから我々は、より多くのビットを行くつもりです
方法1はおそらくだろうに関する深さ

367
00:19:10,990 --> 00:19:12,400
リンクリストを検索します。

368
00:19:12,400 --> 00:19:15,460
のいくつかは何を覚えておいてください
リンクリストの欠点

369
00:19:15,460 --> 00:19:19,340
検索に関する配列を詩。

370
00:19:19,340 --> 00:19:22,565
配列することができますバイナリ検索が、
なぜあなたはリンクリストでそれを行うことができないのですか？

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> 聴衆：彼らはすべての接続されているので、
しかし、あなたは非常にどこかわかりません

373
00:19:30,320 --> 00:19:31,330
[聞こえません]。

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG：うん、まさにそう覚えています
その配列の輝き

375
00:19:34,600 --> 00:19:37,190
私達が持っていたという事実がありました
ランダム・アクセス・メモリ場所

376
00:19:37,190 --> 00:19:41,580
私は、インデックスから値を望んでいた場合
6、私はインデックス6を言うことができます、

377
00:19:41,580 --> 00:19:42,407
私はその値を与えます。

378
00:19:42,407 --> 00:19:45,240
配列がソートされているので、それはです
メモリの連続した​​領域で

379
00:19:45,240 --> 00:19:48,020
一つの場所で、一方、
リンクリストのようなもの

380
00:19:48,020 --> 00:19:52,820
ランダムにすべての周りに散在しています、
あなたがものを見つけることができる唯一の​​方法

381
00:19:52,820 --> 00:19:56,890
示していますポインタを介して行われ
その次のノードがどこにあるのアドレス。

382
00:19:56,890 --> 00:20:00,290
>> そして、その結果、唯一の方法
リンクリストを検索します

383
00:20:00,290 --> 00:20:01,560
線形検索があります。

384
00:20:01,560 --> 00:20:05,890
私は場所を正確に知っているわけではないので
リンクされたリスト内の12番目の値であります

385
00:20:05,890 --> 00:20:08,780
私は、全体を横断する必要があります
そのリンクリスト1の

386
00:20:08,780 --> 00:20:12,450
最初のノードに頭から一つ、
第2のノードに、第3のノードに、

387
00:20:12,450 --> 00:20:17,690
私は最終的に到達するまでダウンすべての方法
私が探しているそのノードがどこにあるの。

388
00:20:17,690 --> 00:20:22,110
だからこの意味で、検索
リンクリストに常にnです。

389
00:20:22,110 --> 00:20:23,040
それは、常にn個です。

390
00:20:23,040 --> 00:20:25,690
これは、線形時間で常にです。

391
00:20:25,690 --> 00:20:28,470
>> だからコードするで
私たちはこれを実装し、この

392
00:20:28,470 --> 00:20:32,620
あなた以来、あなたたちのために少し新しいです
男は本当にについて話しましたか今までになかったです

393
00:20:32,620 --> 00:20:35,000
にどのように見られるのポインタ
ポインタを検索、

394
00:20:35,000 --> 00:20:37,670
私たちは歩きますよ
この非常に、非常にゆっくりと。

395
00:20:37,670 --> 00:20:40,200
だからブール検索、右、
我々が欲しいのは想像してみましょう

396
00:20:40,200 --> 00:20:42,820
関数を作成するには
trueを返す検索

397
00:20:42,820 --> 00:20:46,820
あなたは、リンク内の値を発見した場合
リスト、それがそうでない場合はfalseを返します。

398
00:20:46,820 --> 00:20:50,030
ノードスターリストです
現在だけでポインタ

399
00:20:50,030 --> 00:20:52,960
あなたのリンクリストの最初の項目へ。

400
00:20:52,960 --> 00:20:56,700
int型nは、あなたがしている値であり、
そのリスト内を検索します。

401
00:20:56,700 --> 00:20:58,770
>> だから、ノードスターポインタがリストに等しいです。

402
00:20:58,770 --> 00:21:00,970
それは我々が設定していることを意味します
ポインタを作成します

403
00:21:00,970 --> 00:21:03,592
リストの内側にその最初のノードに。

404
00:21:03,592 --> 00:21:04,300
私と一緒にみんな？

405
00:21:04,300 --> 00:21:06,530
だから、私達は行くした場合
ここに戻って、私が持っているだろう

406
00:21:06,530 --> 00:21:13,850
を指すポインタを初期化します
何でもそのリストの先頭です。

407
00:21:13,850 --> 00:21:18,600
>> そして、あなたは、ここで降りたら、
ポインタが等しくないヌルを行いながら、

408
00:21:18,600 --> 00:21:22,160
だから、私たちはここでループがあります
その後に横断することになるだろう

409
00:21:22,160 --> 00:21:25,940
何のため私たちのリストの残りの部分
ポインタがNULLに等しいときどうなりますか？

410
00:21:25,940 --> 00:21:27,550
我々はhave--ことを知っています

411
00:21:27,550 --> 00:21:28,450
>> 聴衆：[聞こえません]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG：まさに、私たちが知っていること
我々は、右側のリストの最後に到達しましたか！

413
00:21:31,491 --> 00:21:34,470
あなたがここに戻ると、各ノード
別のノードに指している必要があり

414
00:21:34,470 --> 00:21:36,550
などなど
あなたは最終的にヒットするまで、

415
00:21:36,550 --> 00:21:41,589
あなたのリンクリストの末尾、
これはちょうどそのポインタを持っています

416
00:21:41,589 --> 00:21:43,130
なし以外の場所を指していません。

417
00:21:43,130 --> 00:21:47,510
だから、あなたは基本的にはそれを知っています
あなたのリストには、まだそこにアップしています

418
00:21:47,510 --> 00:21:50,900
ポインタが等しくないまで
ヌルがnullに等しいいったんので、

419
00:21:50,900 --> 00:21:53,310
あなたはそれ以上のものがないことを知っています。

420
00:21:53,310 --> 00:21:56,930
>> だから、私たちがしているというループです
実際の検索を持つことになります。

421
00:21:56,930 --> 00:22:01,690
pointer--を行う場合、あなたはを参照してください。
そこに矢印機能のようなもの？

422
00:22:01,690 --> 00:22:06,930
そこで、n個のポインタを指している場合であれば
nのポインタは、nに等しい等しく、

423
00:22:06,930 --> 00:22:09,180
そのためには、場合ことを意味し
あなたがしているポインタ

424
00:22:09,180 --> 00:22:13,420
各の終わりにを検索
ノードが値に実際に等しいです

425
00:22:13,420 --> 00:22:15,990
あなたがして、探しています
あなたはtrueを返したいです。

426
00:22:15,990 --> 00:22:19,280
したがって、基本的に、あなたがそのノードにいる場合
あなたが探している値を持っています、

427
00:22:19,280 --> 00:22:23,550
あなたがしてきたことを知っています
正常に検索できるように。

428
00:22:23,550 --> 00:22:27,150
>> そうしないと、設定したいです
次のノードへのポインタ。

429
00:22:27,150 --> 00:22:28,850
それはここでその行が何をしているかです。

430
00:22:28,850 --> 00:22:31,750
ポインタは、次のポインタに等しいです。

431
00:22:31,750 --> 00:22:33,360
誰もがそれが働いているかを確認？

432
00:22:33,360 --> 00:22:36,580
>> そして、基本的に、あなただけのつもり
、リスト全体を横切ります

433
00:22:36,580 --> 00:22:41,920
毎回までポインタをリセットします
あなたは最終的にはリストの最後にヒット。

434
00:22:41,920 --> 00:22:45,030
そして、あなたは何があることを知っています
複数のノードは、を検索します

435
00:22:45,030 --> 00:22:47,999
そして、あなたはfalseを返すことができます
あなたが知っているので、それだけでなく、ああ、

436
00:22:47,999 --> 00:22:50,540
私は検索することができました場合
リスト全体を通じ。

437
00:22:50,540 --> 00:22:54,530
この例の場合、私が望んでいた場合
10の値を探すために、

438
00:22:54,530 --> 00:22:57,250
私は頭に開始し、
私は、ダウンすべての方法を検索

439
00:22:57,250 --> 00:23:00,550
私は最終的には、これに持っています
nullに指し示すポインタ、

440
00:23:00,550 --> 00:23:04,415
私はしていない、がらくた、私は10を推測することを知っています
このリスト私はそれを見つけることができなかったので。

441
00:23:04,415 --> 00:23:06,520
そして、私は、リストの末尾です。

442
00:23:06,520 --> 00:23:11,040
そして、その場合には、あなたが知っています
私はfalseを返すつもりです。

443
00:23:11,040 --> 00:23:12,900
>> それは少しのためで浸してみましょう。

444
00:23:12,900 --> 00:23:17,350
これはかなりになります
あなたのpsetのために重要。

445
00:23:17,350 --> 00:23:21,140
そのロジックは、おそらく、非常に簡単です
構文的にそれを実現しています。

446
00:23:21,140 --> 00:23:23,365
君たちは作りたいです
あなたが理解していることを確認してください。

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
クール。

449
00:23:27,650 --> 00:23:32,560
>> [OK]を、私たちはどのようになります
右、ノードを挿入し、

450
00:23:32,560 --> 00:23:35,380
リストにあるため覚えています
利益の何がどのようなもの

451
00:23:35,380 --> 00:23:39,230
対リンクリストを持っていることの
ストレージの点で配列？

452
00:23:39,230 --> 00:23:41,110
>> 観客：それはダイナミックですが、
それは簡単ですto--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG：その通り、
それは、どのダイナミックです

454
00:23:43,180 --> 00:23:46,880
それが拡大し、縮小することができることを意味します
ユーザのニーズに応じ。

455
00:23:46,880 --> 00:23:56,570
だから、そういう意味では、我々は必要はありません
私ので、不要なメモリを無駄にします

456
00:23:56,570 --> 00:24:00,850
私は私が望むどのように多くの値がわからない場合
保存するために、それは私のために意味がありません

457
00:24:00,850 --> 00:24:04,310
ため、配列を作成します
私は10個の値を格納する場合

458
00:24:04,310 --> 00:24:08,380
私は千の配列が、それはだ作成します
無駄なメモリの多くは、割り当てられました。

459
00:24:08,380 --> 00:24:11,180
我々はリンクを使用したい理由です
動的にすることができるようにリスト

460
00:24:11,180 --> 00:24:13,860
変更または当社のサイズを縮小します。

461
00:24:13,860 --> 00:24:17,040
>> そして、そのためには、挿入を作ります
ビットは、より複雑。

462
00:24:17,040 --> 00:24:20,810
我々は、ランダム要素にアクセスすることはできませんので、
私たちは、アレイのような方法。

463
00:24:20,810 --> 00:24:24,270
私は、要素を挿入する場合
第七インデックスに、

464
00:24:24,270 --> 00:24:26,930
私はちょうどそれを挿入することができます
第七インデックスに。

465
00:24:26,930 --> 00:24:30,020
リンクされたリストでは、それはしていません
全く同じように簡単に動作し、

466
00:24:30,020 --> 00:24:34,947
そのため、我々は挿入したい場合
ここにリンクされたリスト内の1つ、

467
00:24:34,947 --> 00:24:36,280
視覚的に、それは見ることは非常に簡単です。

468
00:24:36,280 --> 00:24:39,363
私達はちょうどそこにそれを挿入します、
右側のリストの先頭に、

469
00:24:39,363 --> 00:24:40,840
頭の後に右。

470
00:24:40,840 --> 00:24:44,579
>> しかし、私たちが持っている方法は、再割り当てします
ポインタは少し複雑です

471
00:24:44,579 --> 00:24:47,620
または、論理的に、それは理にかなっているが、
あなたはそれを持っていることを確認します

472
00:24:47,620 --> 00:24:50,250
完全にダウンしているため
あなたがしたい最後のこと

473
00:24:50,250 --> 00:24:52,990
ポインタを再割り当てすることです
私たちがここでやっている方法です。

474
00:24:52,990 --> 00:24:58,170
あなたの場合、間接参照
1頭からポインタ、

475
00:24:58,170 --> 00:25:01,086
その後、突然インクルードのすべて
あなたのリンクリストの残りの部分

476
00:25:01,086 --> 00:25:04,680
あなたが実際に持っていないため、失われます
一時的なものを作成しました。

477
00:25:04,680 --> 00:25:06,220
それは2を指摘しています。

478
00:25:06,220 --> 00:25:10,080
あなたはポインタを再割り当てする場合は、
あなたのリストの残りの部分は完全に失われます。

479
00:25:10,080 --> 00:25:13,310
だから、になりたいです
ここでは非常に、非常に慎重

480
00:25:13,310 --> 00:25:17,010
最初に割り当てます
何でもあなたからのポインタ

481
00:25:17,010 --> 00:25:20,150
どこに挿入します
あなたがしたいし、その後

482
00:25:20,150 --> 00:25:22,710
あなたのリストの残りの部分を逆参照することができます。

483
00:25:22,710 --> 00:25:25,250
>> だから、これはどこに適用されます
あなたが挿入しようとしています。

484
00:25:25,250 --> 00:25:27,520
あなたがで挿入したい場合は
頭部、あなたがここに答えるようにしたい場合は、

485
00:25:27,520 --> 00:25:29,455
あなたがで挿入する場合
終わり、よく、最後のI

486
00:25:29,455 --> 00:25:30,910
あなただけでしょうね
あなたは何のポインタを持っていませんが、

487
00:25:30,910 --> 00:25:33,830
あなたがいないことを確認します
あなたのリストの残りの部分を失います。

488
00:25:33,830 --> 00:25:36,640
あなたは、常に確認します
新しいノードが指しています

489
00:25:36,640 --> 00:25:39,330
何でも向かって
挿入します、

490
00:25:39,330 --> 00:25:42,170
そして、あなたはチェーンを上に追加することができます。

491
00:25:42,170 --> 00:25:43,330
誰も明確な？

492
00:25:43,330 --> 00:25:45,427
>> これは、になるだろう
現実の課題の一つ。

493
00:25:45,427 --> 00:25:48,010
ほとんどの主要な問題の一つ
あなたのpsetに必要があるとしています

494
00:25:48,010 --> 00:25:51,340
あなたが作成しようとしているということです
リンクリストとインサートもの

495
00:25:51,340 --> 00:25:53,340
しかしその後、ちょうど失います
あなたのリンクリストの残りの部分。

496
00:25:53,340 --> 00:25:54,900
そして、あなたは私のようなことになるだろう
なぜこれが起こっているかわかりませんか？

497
00:25:54,900 --> 00:25:58,040
そして、それは通過する痛みです
あなたのポインタのすべてを検索します。

498
00:25:58,040 --> 00:26:02,100
>> そして、私はこのPSETであなたを保証します、
これらのノードを書き出すと描画

499
00:26:02,100 --> 00:26:03,344
非常に、非常に参考になります。

500
00:26:03,344 --> 00:26:06,010
だから、完全に追跡することができます
すべてのポインタがどこにいるの、

501
00:26:06,010 --> 00:26:08,540
何が間違って起こっています、
すべてのノードがある場合は、

502
00:26:08,540 --> 00:26:12,660
あなたがアクセスするために何をする必要があるか、または
挿入または削除したり、それらのいずれか。

503
00:26:12,660 --> 00:26:14,550
それで良い誰？

504
00:26:14,550 --> 00:26:15,050
クール。

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> 私たちはコードを見てみたかったのであれば？

507
00:26:22,600 --> 00:26:24,470
ああ、私は知っていない場合は、我々
そう、the-- OK]を見ることができます

508
00:26:24,470 --> 00:26:27,940
一番上にそれはすべての関数であります
私たちが望むという名前の挿入

509
00:26:27,940 --> 00:26:31,365
リンクリストへのint nを挿入します。

510
00:26:31,365 --> 00:26:32,740
我々は、このウォークスルーするつもりです。

511
00:26:32,740 --> 00:26:34,770
それは、多くのコード、新しい構文がたくさんです。

512
00:26:34,770 --> 00:26:36,220
我々はOKになるだろう。

513
00:26:36,220 --> 00:26:39,120
>> だから、一番上のアップ、いつでも
私たちは何かを作成したいです

514
00:26:39,120 --> 00:26:42,380
我々は、特にあなたならば、何をすべきかが必要です
それはスタック上に保存されないようにしたいです

515
00:26:42,380 --> 00:26:43,920
しかし、ヒープ内の？

516
00:26:43,920 --> 00:26:45,460
我々は、右のmallocに行きますか？

517
00:26:45,460 --> 00:26:48,240
だから我々は、ポインタを作成しようとしています。

518
00:26:48,240 --> 00:26:52,074
ノード、ポインタ、新しい等号
ノードのサイズををmalloc

519
00:26:52,074 --> 00:26:53,740
私たちがしたいので、そのノードを作成します。

520
00:26:53,740 --> 00:26:56,720
我々は量をしたいです
ノードが占めるメモリ

521
00:26:56,720 --> 00:26:59,300
割り当てられたことにします
新しいノードを作成します。

522
00:26:59,300 --> 00:27:02,270
>> そして、我々は、にチェックするつもりです
新しい等号がnullに等しいかどうかを確認します。

523
00:27:02,270 --> 00:27:03,370
我々が言ったことを覚えていますか？

524
00:27:03,370 --> 00:27:06,470
どのようなあなたはmalloc関数、
あなたはいつも何をしなければなりませんか？

525
00:27:06,470 --> 00:27:09,490
あなたはいつも見にチェックする必要があります
かどうか、それはnullです。

526
00:27:09,490 --> 00:27:13,620
>> たとえば、オペレーティング
このシステムは、完全に満ちていました

527
00:27:13,620 --> 00:27:17,060
あなたがでこれ以上のメモリを持っていた場合
すべてのあなたはmalloc関数にしてみてください、

528
00:27:17,060 --> 00:27:18,410
それはあなたのためにnullを返します。

529
00:27:18,410 --> 00:27:21,094
そして、あなたはそれを使用しようとした場合
それがnullに指していたとき、

530
00:27:21,094 --> 00:27:23,260
あなたができるするつもりはありません
その情報にアクセスします。

531
00:27:23,260 --> 00:27:27,010
そしてそうのような、我々が作りたかったです
いつでもあなたがmallocingしていることを確認し、

532
00:27:27,010 --> 00:27:30,500
あなたは、常にかどうかを確認するためにチェックしています
あなたに与えられたそのメモリはnullです。

533
00:27:30,500 --> 00:27:33,670
そうでないなら、我々は移動することができます
我々のコードの残りの部分とに。

534
00:27:33,670 --> 00:27:36,140
>> だから我々はするつもりです
新しいノードを初期化します。

535
00:27:36,140 --> 00:27:39,050
私たちは、新しいnがNに等しいやろうとしています。

536
00:27:39,050 --> 00:27:42,390
そして、我々がやろうとしています
新しい上に新しいポインタを設定

537
00:27:42,390 --> 00:27:46,900
nullに、今、私たちにはありませんので、
それが指すようにするために何かをしたいです。

538
00:27:46,900 --> 00:27:48,755
私たちはどこ見当がつかない
それは、あなたを置くために起こっています

539
00:27:48,755 --> 00:27:50,630
し、我々がしたい場合は
頭でそれを挿入し、

540
00:27:50,630 --> 00:27:53,820
その後、私たちは再割り当てすることができます
先頭へのポインタ。

541
00:27:53,820 --> 00:27:58,530
誰もがロジックに従っています
それが起こっているどこの？

542
00:27:58,530 --> 00:28:02,502
>> 私たちがやっているすべては、新たに作成しています
ノード、nullにポインタを設定し、

543
00:28:02,502 --> 00:28:04,210
して、再割り当て
その頭に、私たちの場合

544
00:28:04,210 --> 00:28:06,320
私たちは頭でそれを挿入したい知っています。

545
00:28:06,320 --> 00:28:09,420
そして、ヘッドがしようとしています
その新しいノードに向かって指しています。

546
00:28:09,420 --> 00:28:11,060
それでOK誰？

547
00:28:11,060 --> 00:28:12,380
>> だから、二段階のプロセスです。

548
00:28:12,380 --> 00:28:14,760
最初に割り当てるために持っています
あなたが作成しているものは何でも。

549
00:28:14,760 --> 00:28:18,260
へのポインタを設定します。
あなたを参照してから、

550
00:28:18,260 --> 00:28:21,400
間接参照の種類のことができ
最初のポインタ

551
00:28:21,400 --> 00:28:22,972
新規ノードに向かって指しています。

552
00:28:22,972 --> 00:28:25,680
あなたはそれを挿入したい場合はいつでも、
その論理が成り立つとしています。

553
00:28:25,680 --> 00:28:27,530
>> それは一種の割り当てのようなものです
一時変数。

554
00:28:27,530 --> 00:28:28,700
あなたが持っている、覚えておいてください
必ずことを確認します

555
00:28:28,700 --> 00:28:30,346
あなたがスワッピングしている場合のトラックを失うことはありません。

556
00:28:30,346 --> 00:28:33,470
あなたが持っていることを確認します
種類の保持一時変数

557
00:28:33,470 --> 00:28:35,620
どこにそのことのトラック
あなたがそのように保存されています

558
00:28:35,620 --> 00:28:41,190
コー​​ス内の任意の値を失うことはありません
それいじりようなの。

559
00:28:41,190 --> 00:28:42,710
>> [OK]を、ので、コードはここになります。

560
00:28:42,710 --> 00:28:45,020
君たちはセクションの後を見てみましょう。

561
00:28:45,020 --> 00:28:48,060
それはあるでしょう。

562
00:28:48,060 --> 00:28:50,280
>> だから私はどうするかと思います
我々が望んでいた場合、これが異なります

563
00:28:50,280 --> 00:28:52,300
途中または最後に挿入するには？

564
00:28:52,300 --> 00:28:57,892
誰だかのアイデアを持っています
論理的な基準と擬似コード

565
00:28:57,892 --> 00:29:00,350
我々が望んでいた場合、我々はかかるだろうと
途中に挿入するには？

566
00:29:00,350 --> 00:29:03,391
だから我々はでそれを挿入したい場合
ヘッドは、我々が行うすべては、新しいノードを作成することです。

567
00:29:03,391 --> 00:29:06,311
私たちは、そのポインタを設定
何でも頭に新しいノード、

568
00:29:06,311 --> 00:29:08,310
し、我々は、ヘッドセット
新しいノードに、右？

569
00:29:08,310 --> 00:29:11,560
私たちは途中でそれを挿入したい場合
リストで、私たちがしなければならないのでしょうか？

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> 観客：それはまだだろう
同様のプロセスであります

572
00:29:16,110 --> 00:29:19,114
ポインタを割り当てるなど
そのポインタを割り当て、

573
00:29:19,114 --> 00:29:20,530
しかし、我々はそこに見つけなければならないでしょう。

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG：その通り、まさにそう
あなたを除いて同じプロセス

575
00:29:23,560 --> 00:29:27,820
場所を正​​確に見つける必要があります
その新しいポインタがに行きたいです、

576
00:29:27,820 --> 00:29:44,790
私は挿入したい場合は
OK list--リンクの真ん中、

577
00:29:44,790 --> 00:29:46,370
のは、それが私たちのリンクリストだとしましょう​​。

578
00:29:46,370 --> 00:29:49,500
我々は右のそれをここに挿入したい場合は、
私たちは、新しいノードを作成しようとしています。

579
00:29:49,500 --> 00:29:50,520
私たちは、malloc関数になるだろう。

580
00:29:50,520 --> 00:29:52,220
私たちは、新しいノードを作成しようとしています。

581
00:29:52,220 --> 00:29:55,940
私たちは、割り当てするつもりです
ここでは、このノードのポインタ。

582
00:29:55,940 --> 00:29:58,335
>> しかし、問題はそれが異なります
ヘッドがどこにあるの

583
00:29:58,335 --> 00:30:00,490
我々は正確に知っていたということです
ここで、ヘッドがあります。

584
00:30:00,490 --> 00:30:01,930
それは右、最初は右でしたか？

585
00:30:01,930 --> 00:30:04,870
しかし、ここで私たちはトラックを保つために持っています
我々は中にそれを挿入している場所の。

586
00:30:04,870 --> 00:30:07,930
我々は我々を挿入する場合
ここでノードは、我々が持っています

587
00:30:07,930 --> 00:30:12,270
ていることを確認します
このノードの前の1

588
00:30:12,270 --> 00:30:14,172
ポインタを再割り当てするものです。

589
00:30:14,172 --> 00:30:16,380
だから、あなたはへの種類の持っています
二つのことを追跡します。

590
00:30:16,380 --> 00:30:19,420
あなたはどこにこのを追跡する場合
ノードは、現在に挿入されます。

591
00:30:19,420 --> 00:30:23,280
また、を追跡する必要があります
あなたが見ている前のノード

592
00:30:23,280 --> 00:30:24,340
そこにもありました。

593
00:30:24,340 --> 00:30:25,830
それで良い誰？

594
00:30:25,830 --> 00:30:26,500
OK。

595
00:30:26,500 --> 00:30:28,000
>> どのように最後に挿入するでしょうか？

596
00:30:28,000 --> 00:30:34,220
私が望んでいた場合、私はhere--それを追加したい場合
リストの末尾に新しいノードを追加するには、

597
00:30:34,220 --> 00:30:37,009
どのように私はそれをやって行くのでしょうか？

598
00:30:37,009 --> 00:30:39,300
聴衆：だから、現在、
最後のヌルを指摘しました。

599
00:30:39,300 --> 00:30:40,960
ANDI PENG：うん。

600
00:30:40,960 --> 00:30:43,560
ちょうどので、この1
現在知ることが指摘され、

601
00:30:43,560 --> 00:30:46,720
ので、私はそれがだ、この意味では、と思います
リストの最後に追加することは非常に簡単。

602
00:30:46,720 --> 00:30:51,810
あなたがしなければならないすべてはそれを設定されています
ヌルして、ブームに等しいです。

603
00:30:51,810 --> 00:30:53,070
右そこに、非常に簡単。

604
00:30:53,070 --> 00:30:53,960
非常にシンプル。

605
00:30:53,960 --> 00:30:56,430
>> と非常に似て
あなたの頭が、論理的に

606
00:30:56,430 --> 00:30:59,690
手順はそれを確認します
あなたは、こののいずれかを実行に向けて取ります

607
00:30:59,690 --> 00:31:01,500
あなたに沿って従っています。

608
00:31:01,500 --> 00:31:04,420
それは途中で、と非常に簡単です
あなたのコードの、に巻き込まれる

609
00:31:04,420 --> 00:31:05,671
ああ、私は非常に多くのポインタを持っています。

610
00:31:05,671 --> 00:31:07,461
私がどこかわかりません
何を指しています。

611
00:31:07,461 --> 00:31:09,170
私も、私は上だどのノードがわかりません。

612
00:31:09,170 --> 00:31:11,490
どうしたの？

613
00:31:11,490 --> 00:31:13,620
>> 深呼吸をし、落ち着いて、リラックスすることができます。

614
00:31:13,620 --> 00:31:15,530
あなたのリンクリストを描画します。

615
00:31:15,530 --> 00:31:18,800
あなたが言うなら、私は場所を正確に知っています
私はにこれを挿入する必要があります

616
00:31:18,800 --> 00:31:22,970
そして、私は再割り当てする方法を正確に知っています
ポインタは、はるかに、はるかに簡単に画像に

617
00:31:22,970 --> 00:31:27,200
out--はるかに、はるかに容易にありません
あなたのコードのバグで迷子に。

618
00:31:27,200 --> 00:31:29,410
それでOK誰？

619
00:31:29,410 --> 00:31:31,380
OK。

620
00:31:31,380 --> 00:31:35,120
>> だから私たちは持っていない概念を推測します
本当に、今の前にについて話しました

621
00:31:35,120 --> 00:31:38,131
そして私はおそらくあなたを推測します
多くのyet--が発生することはありません

622
00:31:38,131 --> 00:31:40,880
それは、高度なconcept--のようなものです
私たちは実際にデータを持っているということです

623
00:31:40,880 --> 00:31:43,900
構造は、二重リンクリストと呼ばれます。

624
00:31:43,900 --> 00:31:46,390
だからみんなが見ることができるように、
私たちがやっているすべては作成されています

625
00:31:46,390 --> 00:31:50,400
実際の値は、余分な
私たちの各ノード上のポインタ

626
00:31:50,400 --> 00:31:52,660
それはまた、前のノードを指しています。

627
00:31:52,660 --> 00:31:58,170
だからだけでなく、私たちはがありますか
ノードは、次のいずれかにポイントします。

628
00:31:58,170 --> 00:32:01,430
彼らはまた、前のものを指します。

629
00:32:01,430 --> 00:32:04,310
私は今、これらの2を無視するつもりです。

630
00:32:04,310 --> 00:32:06,740
>> だから、あなたは鎖を有していて
それは両方の方法を移動することができ、

631
00:32:06,740 --> 00:32:09,630
そして、それは少し簡単です
論理的に沿って追従します。

632
00:32:09,630 --> 00:32:11,896
ここでのように、代わりに
私は、ああ、の追跡

633
00:32:11,896 --> 00:32:14,520
このノードがあることを知っている必要があります
私は再割り当てする必要があります1、

634
00:32:14,520 --> 00:32:17,532
私はここに行くことができ、
ただ、前を引きます。

635
00:32:17,532 --> 00:32:19,490
それから私は、場所を正確に知っています
つまり、その後

636
00:32:19,490 --> 00:32:21,130
横断する必要はありません
リンクリストの全体。

637
00:32:21,130 --> 00:32:22,180
それは少し簡単です。

638
00:32:22,180 --> 00:32:24,960
>> しかし、このようなように、あなたが二重に持っています
ポインタの量は、

639
00:32:24,960 --> 00:32:26,960
それは二重のメモリの量です。

640
00:32:26,960 --> 00:32:28,950
これは、を追跡するためのポインタがたくさんです。

641
00:32:28,950 --> 00:32:32,140
これは少し複雑ですが、それはです
もう少しユーザーフレンドリー応じ

642
00:32:32,140 --> 00:32:34,080
あなたが達成しようとしているものに。

643
00:32:34,080 --> 00:32:36,910
>> そのようにこのタイプのデータ
構造は全く存在して、

644
00:32:36,910 --> 00:32:40,280
そして、するための構造は、非常に、非常にあります
あなたが持っているすべてを除いて単純です、

645
00:32:40,280 --> 00:32:43,850
代わりに、次へのポインタだけの、
あなたはまた、前へのポインタを持っています。

646
00:32:43,850 --> 00:32:45,940
それはすべての違いだったのです。

647
00:32:45,940 --> 00:32:47,740
それで良い誰？

648
00:32:47,740 --> 00:32:48,240
クール。

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> すべての権利、今私は
本当におそらく過ごすために

651
00:32:53,280 --> 00:32:56,870
15〜20分またはバルクのような
セクションの残りの時間の

652
00:32:56,870 --> 00:32:58,360
ハッシュテーブルの話。

653
00:32:58,360 --> 00:33:02,590
どのようにあなたたちの多く
pset5仕様を読んでいますか？

654
00:33:02,590 --> 00:33:03,620
すべての権利、良いです。

655
00:33:03,620 --> 00:33:06,160
それは、通常の50％よりも高いです。

656
00:33:06,160 --> 00:33:07,560
大丈夫です。

657
00:33:07,560 --> 00:33:10,345
>> だからみんなが見るように、
あなたはpset5に挑戦しています

658
00:33:10,345 --> 00:33:16,790
辞書を実装することになります
どこに14万の単語を読み込みます

659
00:33:16,790 --> 00:33:20,610
私たちはあなたとスペルチェックを与えること
すべてのテキストに対して、それ。

660
00:33:20,610 --> 00:33:22,580
私たちはあなたのランダムをあげます
文学の作品。

661
00:33:22,580 --> 00:33:23,520
私たちはあなたのオデッセイを与えるでしょう。

662
00:33:23,520 --> 00:33:24,561
私たちはあなたのイリアスを与えるでしょう。

663
00:33:24,561 --> 00:33:26,350
私たちはあなたのオースティンパワーズを与えるでしょう。

664
00:33:26,350 --> 00:33:28,220
>> そして、あなたの挑戦
スペルチェックをすることになります

665
00:33:28,220 --> 00:33:31,760
すべてのすべての単一の単語
これらの辞書の

666
00:33:31,760 --> 00:33:34,960
基本的に私たちのスペルチェッカーと。

667
00:33:34,960 --> 00:33:38,620
だから、いくつかの部品があります
このPSETを作成するのではなく、

668
00:33:38,620 --> 00:33:41,970
まずあなたがなりたいです
実際にロードできます

669
00:33:41,970 --> 00:33:43,970
あなたにすべての単語
辞書、その後

670
00:33:43,970 --> 00:33:45,530
にできるようにしたいです
それらのすべてをスペルチェック。

671
00:33:45,530 --> 00:33:48,780
それでなど、あなたが必要とするつもりです
この高速を行うことができますデータ構造

672
00:33:48,780 --> 00:33:50,790
効率的かつ動的。

673
00:33:50,790 --> 00:33:52,900
>> だから私は、最も簡単なと仮定します
これを行う方法は、

674
00:33:52,900 --> 00:33:55,010
おそらく正しい、配列を作成しますか？

675
00:33:55,010 --> 00:33:58,910
ストレージの最も簡単な方法は、あなたです
14万単語の配列を作成することができます

676
00:33:58,910 --> 00:34:03,400
ちょうどそこにそれらのすべてを配置し、
その後、バイナリ検索によってそれらを横断します

677
00:34:03,400 --> 00:34:06,780
または選択しますか、not--
残念それは並べ替えています。

678
00:34:06,780 --> 00:34:10,729
あなたはそれらをソートし、それらを横断することができます
二分探索あるいは単に線形探索によって

679
00:34:10,729 --> 00:34:13,730
ちょうど最後の言葉が、その
メモリの膨大な量をとり、

680
00:34:13,730 --> 00:34:15,190
それは非常に効率的ではありません。

681
00:34:15,190 --> 00:34:18,350
>> そして、私たちは開始するつもりです
作りの方法について話

682
00:34:18,350 --> 00:34:20,110
私たちの実行時間が、より効率的。

683
00:34:20,110 --> 00:34:23,190
そして、私たちの目標は得ることです
一定時間どこ

684
00:34:23,190 --> 00:34:25,810
それはほとんどの配列、のようなものです
あなたは瞬時にアクセスできます。

685
00:34:25,810 --> 00:34:28,560
私は何を検索したい場合は、
私は、ちょうどにできるようにしたいです

686
00:34:28,560 --> 00:34:30,810
ブームは、まさにそれを見つけて、それを引き出します。

687
00:34:30,810 --> 00:34:34,100
だからその構造中
我々は非常に近くなりつつありますよ

688
00:34:34,100 --> 00:34:37,569
一定アクセスできるようにします
時間、この聖杯

689
00:34:37,569 --> 00:34:41,370
一定のプログラミングで
時間は、ハッシュテーブルと呼ばれています。

690
00:34:41,370 --> 00:34:45,370
それでダビデは、前述
[聞こえない]講義で少し、

691
00:34:45,370 --> 00:34:49,100
しかし、私たちは本当にするつもりです
深い今週中にダイブ

692
00:34:49,100 --> 00:34:51,780
駒に
どのようにハッシュテーブルが動作します。

693
00:34:51,780 --> 00:34:53,949
>> そのようにそうハッシュ
テーブルの動作、例えば、

694
00:34:53,949 --> 00:35:00,230
私は言葉の束を保存したい場合、A
英語の単語の束、

695
00:35:00,230 --> 00:35:02,940
私は理論的に入れることができます
バナナ、リンゴ、キウイ、マンゴー、ペア、

696
00:35:02,940 --> 00:35:04,980
ちょうどアレイ上のマスクメロンすべて。

697
00:35:04,980 --> 00:35:07,044
彼らはすべての中で合うことができると見つけること。

698
00:35:07,044 --> 00:35:09,210
これは、痛みのようなものになるだろう
アクセスを検索、

699
00:35:09,210 --> 00:35:12,920
しかし、これを行うための簡単​​な方法があります
私たちは実際に構造を作成することができます

700
00:35:12,920 --> 00:35:15,680
我々はハッシュハッシュテーブルと呼ばれます。

701
00:35:15,680 --> 00:35:19,880
我々はを通じて当社のすべてのキーを実行します
ハッシュ関数、式、

702
00:35:19,880 --> 00:35:22,600
それはにそれらすべてを回します
値のいくつかの並べ替え

703
00:35:22,600 --> 00:35:28,740
その後、我々は上に保存することができ
リンクリストの基本的配列。

704
00:35:28,740 --> 00:35:32,570
>> だからここで、私たちは望んでいた場合
英語の単語を格納します、

705
00:35:32,570 --> 00:35:37,250
我々は、潜在的にだけ、私はしません行うことができます
知っている、すべての最初の文字を回します

706
00:35:37,250 --> 00:35:39,630
数のいくつかの並べ替えに。

707
00:35:39,630 --> 00:35:43,140
だから、私が欲しかったたとえば、
apple--と同義であることを

708
00:35:43,140 --> 00:35:47,460
または0のインデックスとし、
Bは、1と同義であることを

709
00:35:47,460 --> 00:35:51,030
私たちは26のエントリを持つことができます
それはただ保存することができます

710
00:35:51,030 --> 00:35:53,610
のすべての文字
私たちは始めましょうアルファベット。

711
00:35:53,610 --> 00:35:56,130
そして、我々は持つことができます
0のインデックスにリンゴ。

712
00:35:56,130 --> 00:35:59,160
私たちは、のインデックスでバナナを持つことができます
1、2の指数でマスクメロン、

713
00:35:59,160 --> 00:36:00,540
などなど。

714
00:36:00,540 --> 00:36:04,460
こうして私は、検索したい場合
私のハッシュテーブルとアクセスリンゴ、

715
00:36:04,460 --> 00:36:07,560
私はリンゴで始まる知っています
A、と私は正確に知っています

716
00:36:07,560 --> 00:36:10,860
それは、ハッシュであるとしなければならないこと
インデックス0のテーブル理由

717
00:36:10,860 --> 00:36:13,620
以前に割り当てられた機能の。

718
00:36:13,620 --> 00:36:16,572
>> だから私たちは、知りません
ユーザプログラム場所

719
00:36:16,572 --> 00:36:18,780
あなたが課金されます
任意ではありませんarbitrarily--、

720
00:36:18,780 --> 00:36:22,530
思慮深くしようとしていると
良い方程式を考えます

721
00:36:22,530 --> 00:36:25,460
広がることができるようにします
自分の価値観のすべてのアウト

722
00:36:25,460 --> 00:36:29,370
彼らは簡単にアクセスできるようにして
それ以降の上での式のように

723
00:36:29,370 --> 00:36:31,130
あなた、自分で、知っています。

724
00:36:31,130 --> 00:36:35,210
だから、ある意味で、私はに行きたい場合
マンゴーは、私が知っている、ああ、それはメートルで始まります。

725
00:36:35,210 --> 00:36:37,134
それは12のインデックスである必要があります。

726
00:36:37,134 --> 00:36:38,800
私は何を検索する必要はありません。

727
00:36:38,800 --> 00:36:42,080
私はちょうどに行くことができるexactly--私が知っています
12のインデックスとそれを引き出します。

728
00:36:42,080 --> 00:36:45,520
>> どのように誰も明確な
ハッシュテーブルの機能が動作しますか？

729
00:36:45,520 --> 00:36:48,380
それはちょうどより複雑な配列のようなものです。

730
00:36:48,380 --> 00:36:50,010
それはそれはすべてです。

731
00:36:50,010 --> 00:36:51,630
OK。

732
00:36:51,630 --> 00:36:57,690
>> だから私たちはに実行推測します
何のこの問題

733
00:36:57,690 --> 00:37:06,390
あなたは複数のものを持っている場合はどうなります
それはあなたに同じインデックスを与えますか？

734
00:37:06,390 --> 00:37:10,570
だから、私たちの関数は、すべてのこと、言います
その最初の文字だったかかりました

735
00:37:10,570 --> 00:37:14,490
とにそれを回します
それぞれの25のインデックス0〜。

736
00:37:14,490 --> 00:37:17,137
場合には全く問題ありません
あなたは、それぞれ1つだけ持っています。

737
00:37:17,137 --> 00:37:18,970
しかし、第二は、あなたが開始します
以上を有する、あなたがしています

738
00:37:18,970 --> 00:37:20,910
衝突と呼ばれるものを持っているつもり。

739
00:37:20,910 --> 00:37:25,580
>> だから私は、ハッシュに埋める挿入しようとする場合
すでにその上にバナナを持っているテーブル、

740
00:37:25,580 --> 00:37:27,870
何がときに起こるだろう
あなたはそれを挿入しようと？

741
00:37:27,870 --> 00:37:30,930
バナナため悪いこと
インデックス内にすでに存在しています

742
00:37:30,930 --> 00:37:33,800
あなたはそれを保存すること。

743
00:37:33,800 --> 00:37:35,560
ベリーは、種の私が何をする、ああ、のようなものですか？

744
00:37:35,560 --> 00:37:37,080
私はどこへ行くかわかりません。

745
00:37:37,080 --> 00:37:38,410
私はこれをどのように解決するのですか？

746
00:37:38,410 --> 00:37:41,150
>> だから君たちは一種の意志
私たちはこのトリッキーなことを行う参照してください。

747
00:37:41,150 --> 00:37:44,810
ここで、我々は一種の実際にすることができます
私たちの列にリンクされたリストを作成します。

748
00:37:44,810 --> 00:37:46,840
それで最も簡単な方法
これについて考えるために、

749
00:37:46,840 --> 00:37:50,830
すべてのハッシュテーブルであります
リンクされたリストの配列。

750
00:37:50,830 --> 00:37:55,670
ですから、その意味では、あなたが持っています
ポインタのこの美しい配列、

751
00:37:55,670 --> 00:37:58,740
し、各ポインタで
その値は、そのインデックスで、

752
00:37:58,740 --> 00:38:00,740
実際に他のものを指すことができます。

753
00:38:00,740 --> 00:38:05,720
だから、あなたはすべてのこれらの別々のを持っています
一つの大きな配列の抜けチェーン。

754
00:38:05,720 --> 00:38:07,960
>> だからここで、私の場合
ベリーを挿入したかったです、

755
00:38:07,960 --> 00:38:11,220
私は[OK]を、私は入力するつもりだ、知っています
それ私のハッシュ関数を通じて。

756
00:38:11,220 --> 00:38:15,070
私はのインデックスで終わるつもりです
1、その後、私が持ってできるようにするつもりです

757
00:38:15,070 --> 00:38:20,410
これだけ小さいサブセット
巨大14万語辞書。

758
00:38:20,410 --> 00:38:24,220
そして私はちょうど見ることができます
その1/26を通じ。

759
00:38:24,220 --> 00:38:27,910
>> だから、私はただ挿入することができます
バナナの前または後のいずれかにベリー

760
00:38:27,910 --> 00:38:28,820
この場合？

761
00:38:28,820 --> 00:38:29,700
後、右か？

762
00:38:29,700 --> 00:38:33,920
だから、あなたがしたいとしています
バナナの後に、このノードを挿入し、

763
00:38:33,920 --> 00:38:36,667
ので、あなたが挿入しようとしています
そのリンクリストの末尾。

764
00:38:36,667 --> 00:38:38,500
私は戻って行くつもりです
この前のスライドに、

765
00:38:38,500 --> 00:38:40,680
だからあなたたちはどのように見ることができます
ハッシュ関数が動作します。

766
00:38:40,680 --> 00:38:43,980
>> だから、ハッシュ関数は、この方程式であります
あなたの入力の種類を実行していること

767
00:38:43,980 --> 00:38:46,940
どのようなインデックスを取得するために通過
あなたはそれに向かってを割り当てます。

768
00:38:46,940 --> 00:38:51,130
我々が望んでいたので、この例では、すべての
行うには、最初の文字を取りました

769
00:38:51,130 --> 00:38:55,890
我々はその後、インデックスにそれを回します
私たちのハッシュ関数のそれを保存することができます。

770
00:38:55,890 --> 00:39:00,160
私たちがここでやっているすべては私たちがしているです
最初の文字を変換します。

771
00:39:00,160 --> 00:39:04,770
だからkeykey [0]であるだけで最初の文字
どのような文字列で、私たちは持っています、

772
00:39:04,770 --> 00:39:05,720
我々は渡しています。

773
00:39:05,720 --> 00:39:09,740
我々は上にそれを変換し、しています
我々は、大文字のAで引いています

774
00:39:09,740 --> 00:39:11,740
やっているように、すべての
私たちに番号を与えています

775
00:39:11,740 --> 00:39:13,670
ここで私たちは私たちの上に値をハッシュすることができます。

776
00:39:13,670 --> 00:39:16,550
>> そして、我々はするつもりです
ハッシュ係数サイズを返します。

777
00:39:16,550 --> 00:39:19,340
非常に、非常に注意してください
なぜなら、理論的には、ここで

778
00:39:19,340 --> 00:39:21,870
あなたのハッシュ値は無限大である可能性があります。

779
00:39:21,870 --> 00:39:23,660
それはちょうど上と上に行くことができます。

780
00:39:23,660 --> 00:39:26,080
それは実際にいくつかの可能性があり、
本当に大きな値、

781
00:39:26,080 --> 00:39:29,849
しかし、あなたのハッシュテーブルのため、その
あなたが作成しただけで26のインデックスを持っています、

782
00:39:29,849 --> 00:39:31,890
あなたは確認します
あなたようにmodulusing

783
00:39:31,890 --> 00:39:33,848
それは同じだrun--はありません
あなたのqueue--ようなもの

784
00:39:33,848 --> 00:39:36,320
あなたはオフに実行されないように、
あなたのハッシュ関数の底。

785
00:39:36,320 --> 00:39:39,210
>> あなたの周りにそれをバックラップしたいです
[聞こえない]で同じよう

786
00:39:39,210 --> 00:39:41,750
あなたは非常に持っていたように、
非常に大規模な文字、あなた

787
00:39:41,750 --> 00:39:43,740
にそれをしたくありませんでした
ちょうど端を実行します。

788
00:39:43,740 --> 00:39:46,948
ここで同じことが、あなたは確認します
それは、ラッピングによって終わりをオフに実行されません

789
00:39:46,948 --> 00:39:48,330
周りのテーブルの上に。

790
00:39:48,330 --> 00:39:50,530
だから、これは非常にだけです
単純なハッシュ関数。

791
00:39:50,530 --> 00:39:56,570
やったことすべてが取る最初でした
どのような私たちの入力の手紙がありました

792
00:39:56,570 --> 00:40:01,660
そのインデックスにそれを回します
私たちはハッシュテーブルに入れることができます。

793
00:40:01,660 --> 00:40:05,450
>> うん、と私は前に言ったように、
我々は衝突を解決する方法

794
00:40:05,450 --> 00:40:09,330
当社のハッシュテーブルが持っています、
我々は連鎖、何を呼び出します。

795
00:40:09,330 --> 00:40:13,860
ですから、複数を挿入しようとした場合
同じことで始まる単語、

796
00:40:13,860 --> 00:40:16,145
あなたは1つのハッシュ値を持っているつもりです。

797
00:40:16,145 --> 00:40:18,770
アボカドとリンゴ、あなたがしている場合
私たちのハッシュ関数を介して実行、

798
00:40:18,770 --> 00:40:21,450
あなたを与えるとしています
同じ数、0の数。

799
00:40:21,450 --> 00:40:24,550
そして、私たちはそれを解決する方法があります
私たちは実際に種類のそれらをリンクすることができます

800
00:40:24,550 --> 00:40:27,010
一緒にリンクされたリストを経由して。

801
00:40:27,010 --> 00:40:29,600
>> だからこの意味で、
あなたたちは親切見ることができます

802
00:40:29,600 --> 00:40:32,640
どのようなデータ構造のこと
我々は以前に設定されてきました

803
00:40:32,640 --> 00:40:35,870
レーズンリンクリストのようなもののような
いずれかに一緒に来ることができます。

804
00:40:35,870 --> 00:40:38,860
そして、あなたはこれまで作成することができます
より効率的なデータ構造

805
00:40:38,860 --> 00:40:43,350
それは、より多くの量を処理することができます
データ、すなわち、動的によってリサイズ

806
00:40:43,350 --> 00:40:44,870
あなたのニーズに。

807
00:40:44,870 --> 00:40:45,620
誰も明確な？

808
00:40:45,620 --> 00:40:47,580
明確なのみんなの種類
ここで何が起こるかの？

809
00:40:47,580 --> 00:40:52,110
>> 私は何insert--したい場合
始まる果物は、私は知りません、

810
00:40:52,110 --> 00:40:54,726
ベリー以外のB、バナナ。

811
00:40:54,726 --> 00:40:55,710
>> 聴衆：ブラックベリー。

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG：ブラックベリー、ブラックベリー。

813
00:40:57,910 --> 00:41:00,530
どこでブラックベリーは、ここに行くのですか？

814
00:41:00,530 --> 00:41:04,251
さて、私たちは実際にソートされていません
このまだ、しかし、理論的に

815
00:41:04,251 --> 00:41:06,250
我々はこれを持っているしたい場合
アルファベット順に、

816
00:41:06,250 --> 00:41:07,944
どこに行くのブラックベリーべきですか？

817
00:41:07,944 --> 00:41:09,210
>> 聴衆：[聞こえません]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG：その通り、ここの後、右か？

819
00:41:11,100 --> 00:41:14,950
しかし、それはすることが非常に困難だから
reorder--私はそれは君たち次第だと思います。

820
00:41:14,950 --> 00:41:17,920
君たちは完全にすることができます
あなたが好きな実装。

821
00:41:17,920 --> 00:41:20,730
より効率的な方法
おそらくこれを行います

822
00:41:20,730 --> 00:41:24,570
あなたのリンクを並べ替えることであろう
アルファベット順に一覧表示し、

823
00:41:24,570 --> 00:41:26,520
ので、あなたがいるとき
物事を挿入する、あなたがしたいです

824
00:41:26,520 --> 00:41:28,632
それらを挿入してくださいします
アルファベット順に

825
00:41:28,632 --> 00:41:30,590
そのため、あなたがいるとき
それらを検索しようとすると、

826
00:41:30,590 --> 00:41:32,410
あなたはすべてを横断する必要はありません。

827
00:41:32,410 --> 00:41:35,290
あなたが知っている場所を正確に
それは、それが簡単です。

828
00:41:35,290 --> 00:41:39,100
>> しかし、あなたは親切なのがあれば
物事は、ランダムに散在します

829
00:41:39,100 --> 00:41:41,420
あなたはまだ必要があるとしています
とにかくそれを横断します。

830
00:41:41,420 --> 00:41:44,990
だから私はちょうどしたい場合
ブラックベリーここに挿入

831
00:41:44,990 --> 00:41:47,470
私はを検索したいです
それ、私が知っている、ああ、ブラックベリー

832
00:41:47,470 --> 00:41:52,012
1のインデックスで始まるので、私必要があります
瞬時にちょうど1で検索を知っています。

833
00:41:52,012 --> 00:41:53,970
そして、私はこの種のことができます
リンクリストをトラバース

834
00:41:53,970 --> 00:41:56,120
私はブラックベリーに到達するまで、
とええthen--？

835
00:41:56,120 --> 00:41:59,550
>> 聴衆：あなたはcreate--しようとしている場合
これは非常に単純なハッシュであるように私は推測します

836
00:41:59,550 --> 00:42:00,050
機能。

837
00:42:00,050 --> 00:42:02,835
そして、私たちがやってみたかった場合
そのような複数の層、

838
00:42:02,835 --> 00:42:05,870
[OK]を、私たちは、に分離したいです
すべてのアルファベットのような

839
00:42:05,870 --> 00:42:09,040
し、再度別のセットを好きに
その内のアルファベットの、

840
00:42:09,040 --> 00:42:11,715
我々は、ハッシュのように入れています
ハッシュテーブル内のテーブル、

841
00:42:11,715 --> 00:42:13,256
または関数内の関数のような？

842
00:42:13,256 --> 00:42:14,880
それともthat--です

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG：だからあなたのハッシュ
あなたのハッシュテーブルをfunction--

844
00:42:17,510 --> 00:42:19,360
あなたはそれが好きな大きくすることができます。

845
00:42:19,360 --> 00:42:21,930
したがって、この意味では、私は思いました
それは非常に、非常に簡単でした

846
00:42:21,930 --> 00:42:25,320
ちょうどソートベースのために私のために簡単な
最初の単語の文字に。

847
00:42:25,320 --> 00:42:28,690
そして、これだけ26のオプションがあります。

848
00:42:28,690 --> 00:42:32,650
私は26からオプションを取得することができます
0彼らは唯一の可能性があるため25に

849
00:42:32,650 --> 00:42:36,510
AからZに開始しかし、あなたが望んでいた場合
おそらく、より多くの複雑さを追加します

850
00:42:36,510 --> 00:42:39,260
あなたの実行時間以上の速度
ハッシュテーブル、絶対に

851
00:42:39,260 --> 00:42:40,760
物事のすべてのソートを行うことができます。

852
00:42:40,760 --> 00:42:43,330
あなた自身作ることができます
あなたを与える式

853
00:42:43,330 --> 00:42:48,000
あなたの中に複数の配布
言葉は、あなたが検索し、

854
00:42:48,000 --> 00:42:49,300
それは速くなるだろう。

855
00:42:49,300 --> 00:42:52,100
>> それは完全にあなたたち次第です
どのようにあなたはそれを実装したいです。

856
00:42:52,100 --> 00:42:55,140
ちょうどバケツと考えてください。

857
00:42:55,140 --> 00:42:57,376
私が持っているしたい場合
26バケツ、私は行きますよ

858
00:42:57,376 --> 00:42:59,420
これらのバケットに物事をソートします。

859
00:42:59,420 --> 00:43:02,980
しかし、私はたくさんを持っているつもりです
各バケット内のものの、

860
00:43:02,980 --> 00:43:05,890
だから、あなたがそれをしたい場合
より速く、より効率的、

861
00:43:05,890 --> 00:43:07,190
私は百バケツを持ってみましょう。

862
00:43:07,190 --> 00:43:09,290
>> しかし、あなたは把握する必要があり
彼らはそのようなものをソートする方法

863
00:43:09,290 --> 00:43:11,040
正しいバケツに彼らがでなければなりません。

864
00:43:11,040 --> 00:43:13,331
しかし、ときに実際に
そのバケットを見てみたいです、

865
00:43:13,331 --> 00:43:16,410
ありますので、それははるかに高速です
各バケットが少ないもの。

866
00:43:16,410 --> 00:43:20,250
だから、ええ、それは実際にはです
pset5で君たちのためのトリック

867
00:43:20,250 --> 00:43:22,360
あなたはなるだろうということです
ちょうど作成に挑戦

868
00:43:22,360 --> 00:43:26,170
最も効率的であるものは何でも
であることをあなたが考えることができる機能

869
00:43:26,170 --> 00:43:28,520
これらの値を保存し、確認することができます。

870
00:43:28,520 --> 00:43:30,840
>> 完全にあなたたちまで
しかし、あなたはそれをやってみたいです、

871
00:43:30,840 --> 00:43:32,229
それは本当に良い点です。

872
00:43:32,229 --> 00:43:34,520
そのロジックの一種ます
考え始めるしたいです

873
00:43:34,520 --> 00:43:37,236
よく、なぜ私はより多くのバケツをしない、です。

874
00:43:37,236 --> 00:43:39,527
そして、私が検索する必要が
以下のもの、次に多分私

875
00:43:39,527 --> 00:43:41,640
異なるハッシュ関数を持っています。

876
00:43:41,640 --> 00:43:45,500
>> うん、これを行うための方法はたくさんあり​​ます
PSET、一部は他よりも高速です。

877
00:43:45,500 --> 00:43:50,630
私は完全にどれだけ見に行きますよ
速い最速君たちがしますました

878
00:43:50,630 --> 00:43:55,170
あなたの関数が動作するように取得することができます。

879
00:43:55,170 --> 00:43:58,176
良いで[OK]をクリックし、すべての人
チェーンとハッシュテーブル？

880
00:43:58,176 --> 00:44:00,800
これは非常に単純なように、実際のです
あなたが考えてみれば概念。

881
00:44:00,800 --> 00:44:05,160
それがすべてでは何でも分離されます
あなたの入力はバケットにあり、

882
00:44:05,160 --> 00:44:10,670
それらをソートし、次に検索
そこには、関連付けられていることを示しています。

883
00:44:10,670 --> 00:44:11,852
>> クール。

884
00:44:11,852 --> 00:44:18,160
すべての権利、今、私たちは別の種類を持っています
木と呼ばれるデータ構造の。

885
00:44:18,160 --> 00:44:20,850
それでは、上に行くと試行についてお話しましょう
これは明らかに異なっており、

886
00:44:20,850 --> 00:44:22,330
同じカテゴリインチ

887
00:44:22,330 --> 00:44:29,010
基本的に、すべての木は代わりにあります
線形方法でデータを整理します

888
00:44:29,010 --> 00:44:32,560
ハッシュテーブルはあなたをdoes--こと
知っている、それは、上部と下部を持っています

889
00:44:32,560 --> 00:44:37,900
そして、あなたは一種のit--のオフリンク
ツリーは、あなたが根を呼び出すトップを持っています

890
00:44:37,900 --> 00:44:40,220
そしてそれはすべてその周りの葉を持っています。

891
00:44:40,220 --> 00:44:42,390
>> だから、すべてあなたがここにあります
ただ最上位ノードであります

892
00:44:42,390 --> 00:44:45,980
それが指していることを、他のノードを指します
複数のノードへ、などなど。

893
00:44:45,980 --> 00:44:48,130
だから、あなただけの分割枝を持っています。

894
00:44:48,130 --> 00:44:53,255
これは、整理のちょうど別の方法です
データ、そして我々はそれツリーを呼び出すので、

895
00:44:53,255 --> 00:44:56,270
あなたたちはそれだけですjust--
木のように見えるように出てモデル化しました。

896
00:44:56,270 --> 00:44:57,670
私たちは木と呼んでいます。

897
00:44:57,670 --> 00:44:59,370
>> ハッシュテーブルには、テーブルのように見えます。

898
00:44:59,370 --> 00:45:01,310
ツリーは、ちょうど木のように見えます。

899
00:45:01,310 --> 00:45:03,300
それはすべてが分離されています
ノードを整理する方法

900
00:45:03,300 --> 00:45:06,020
あなたのニーズが何であるかによって異なります。

901
00:45:06,020 --> 00:45:11,810
>> だから、ルートを持っており、
あなたは葉を持っています。

902
00:45:11,810 --> 00:45:15,380
その私たちは特にすることができる方法
それについて考えるバイナリツリーです、

903
00:45:15,380 --> 00:45:18,150
バイナリツリーはただであります
ツリーの特定のタイプ

904
00:45:18,150 --> 00:45:22,450
ここで、各ノードは唯一のポイント
最大で、他の2つのノード。

905
00:45:22,450 --> 00:45:25,434
だからここでは、個別の持っています
あなたのツリー内の対称性

906
00:45:25,434 --> 00:45:28,600
それは一種の見て、それが容易になります
値何であなたは、あなたですので、

907
00:45:28,600 --> 00:45:30,150
常に左または右を持っています。

908
00:45:30,150 --> 00:45:33,150
左から第三のような存在ことはありません
左または左から4番目。

909
00:45:33,150 --> 00:45:36,358
それはあなたが左右を持っているだけです
あなたはこれら二つのどちらかを検索することができます。

910
00:45:36,358 --> 00:45:38,980
そして、なぜこれが便利なのですか？

911
00:45:38,980 --> 00:45:40,980
このことを方法
あなたが探している場合に便利です

912
00:45:40,980 --> 00:45:42,890
右、値を検索するには？

913
00:45:42,890 --> 00:45:45,640
むしろバイナリを実行するよりも
エラー配列内の検索、

914
00:45:45,640 --> 00:45:49,260
あなたは、ノードを挿入できるようにしたい場合
また意志でノードを奪うと、

915
00:45:49,260 --> 00:45:52,185
検索を保存します
二分探索の容量。

916
00:45:52,185 --> 00:45:54,560
だから、このように、我々は一種のです
ときに我々覚えtricking--

917
00:45:54,560 --> 00:45:56,530
リンクされたリストは、バイナリ検索することはできません言いましたか？

918
00:45:56,530 --> 00:46:01,700
私たちは、この種のデータ構造を作成しています
トリックは、作業にそのことを。

919
00:46:01,700 --> 00:46:05,034
>> だからリンクされたリストは、直線状であるため、
彼らは次々にリンクします。

920
00:46:05,034 --> 00:46:06,950
私たちは、この種のことができます
ポインタの別の種類

921
00:46:06,950 --> 00:46:09,408
別のノードにそのポイント
それは、検索で私たちを助けることができます。

922
00:46:09,408 --> 00:46:12,590
だからここで、私がしたい場合
二分探索木を有します

923
00:46:12,590 --> 00:46:14,090
55場合、私はその私の真ん中を知っています。

924
00:46:14,090 --> 00:46:18,280
私はちょうどそれを作成するつもりです
私の真ん中のように、私のルートとして、

925
00:46:18,280 --> 00:46:20,770
そして私は持っているつもりです
値は、それのスピンオフ。

926
00:46:20,770 --> 00:46:25,610
>> だからここに、私がを検索するつもりだ場合
66の値は、私は55で開始することができます。

927
00:46:25,610 --> 00:46:27,310
これは、55より66大きいのか？

928
00:46:27,310 --> 00:46:30,970
はい、そうですので、私は私が知っている検索MUS
I Nこのツリーの右ポインタ。

929
00:46:30,970 --> 00:46:32,440
私は77に行きます。

930
00:46:32,440 --> 00:46:35,367
[OK]を、66未満または77より大きい？

931
00:46:35,367 --> 00:46:37,950
ああ、それはより少ないですので、あなたが知っています、
それは、左ノードにする必要があります。

932
00:46:37,950 --> 00:46:41,410
>> だからここでは、種の維持しています
アレイに関する素晴らしいことのすべて、

933
00:46:41,410 --> 00:46:44,420
そう動的なサイズ変更のような
あるオブジェクトの

934
00:46:44,420 --> 00:46:49,530
自由に挿入し、削除することができ、
固定を心配することなく、

935
00:46:49,530 --> 00:46:50,370
スペースの量。

936
00:46:50,370 --> 00:46:52,820
我々はまだすべてを保存します
これらの素晴らしいもの

937
00:46:52,820 --> 00:46:57,140
また、保存することを可能としながら、
バイナリサーチの時間を記録し、検索

938
00:46:57,140 --> 00:47:00,450
我々は以前にあったこと
フレーズを取得することができます。

939
00:47:00,450 --> 00:47:06,310
>> クールなデータ構造、種類の
複合体は、ノードを実装します。

940
00:47:06,310 --> 00:47:08,311
あなたは、それをすべて見ることができるように
ノードの構造体であり、

941
00:47:08,311 --> 00:47:10,143
あなたは左を持っているということです
右のポインタ。

942
00:47:10,143 --> 00:47:11,044
それはそれはすべてです。

943
00:47:11,044 --> 00:47:12,960
だからだけではなく
xまたは以前を持ちます。

944
00:47:12,960 --> 00:47:15,920
あなたは、左または右を持っており、
あなたはこの種のそれらを一緒にリンクすることができます

945
00:47:15,920 --> 00:47:16,836
しかし、あなたがそう選択します。

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> [OK]を、私たちは実際に行っています
わずか数分かかります。

948
00:47:24,270 --> 00:47:25,790
だから我々はここに戻って行くつもりです。

949
00:47:25,790 --> 00:47:28,270
私が以前言ったように、
私は種類の説明しました

950
00:47:28,270 --> 00:47:31,520
どのように我々の背後にあるロジック
このを検索します。

951
00:47:31,520 --> 00:47:33,860
我々は試してみるつもりです
見るためにこれをpseudocoding

952
00:47:33,860 --> 00:47:38,000
私たちは、この種の適用できるかどうか
バイナリサーチの同じロジック

953
00:47:38,000 --> 00:47:40,055
データ構造の異なるタイプ。

954
00:47:40,055 --> 00:47:45,049
あなたたちはカップルのように利用したい場合
ただこれについて考えるために分。

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK。

957
00:48:46,925 --> 00:48:51,407
すべての権利、私はするつもりです
実際にちょうどあなたがノーthe--与えます、

958
00:48:51,407 --> 00:48:52,990
我々は最初の擬似コードについて話しましょう​​。

959
00:48:52,990 --> 00:48:56,580
だから、誰もが欲しいん
何で刺しを与えるために

960
00:48:56,580 --> 00:49:02,100
あなたはときに何をしたい最初のこと
あなたは、検索が出始めていますか？

961
00:49:02,100 --> 00:49:04,460
私たちは、探している場合
66の値が、何

962
00:49:04,460 --> 00:49:07,940
我々があればやりたい最初のこと
私たちはこの木二分探索してみませんか？

963
00:49:07,940 --> 00:49:10,760
>> 聴衆：あなたは、右を見てみたいです
そして、[聞こえない]を左見て、参照してください。

964
00:49:10,760 --> 00:49:11,230
より多くの数。

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG：うん、まさに。

966
00:49:12,271 --> 00:49:15,350
つまり、あなたのルートを見ていきます。

967
00:49:15,350 --> 00:49:18,180
あなたが呼び出すことができる方法はたくさんあり​​ます
それは、あなたの親ノードの人々は言います。

968
00:49:18,180 --> 00:49:21,317
私はので、ルートを言いたいです
それは、ツリーのルートのようなものです。

969
00:49:21,317 --> 00:49:23,400
あなたが見てするつもりです
あなたのルートノード、あなたがしています

970
00:49:23,400 --> 00:49:26,940
見に行くと、66大きいです
以下より55。

971
00:49:26,940 --> 00:49:30,360
そして、それはよく、それは、より大きいだ場合
より大きく、どこに我々は見てみたいのですか？

972
00:49:30,360 --> 00:49:32,000
どこに右、今検索したいのですか？

973
00:49:32,000 --> 00:49:34,340
私たちは、検索したいです
このツリーの右半分。

974
00:49:34,340 --> 00:49:38,390
>> だから持って、便利に、
右を指すポインタ。

975
00:49:38,390 --> 00:49:44,325
だから我々は設定することができます
77であるために私たちの新しいルート。

976
00:49:44,325 --> 00:49:46,450
私達はちょうどどこに行くことができます
ポインタが指しています。

977
00:49:46,450 --> 00:49:49,100
まあ、ああ、ここでは開始しています
77であり、私たちはすることができます

978
00:49:49,100 --> 00:49:51,172
再帰的に何度も何度もこれを行います。

979
00:49:51,172 --> 00:49:52,880
このように、あなたの種類
機能を有しています。

980
00:49:52,880 --> 00:49:57,430
あなたがいることを検索する方法を持っています
ただ何度もオーバーを繰り返すことができ、

981
00:49:57,430 --> 00:50:02,720
あなたが見てみたい場所に応じて
あなたは最終的な値に到達するまで

982
00:50:02,720 --> 00:50:04,730
あなたが探しているもの。

983
00:50:04,730 --> 00:50:05,230
理にかなって？

984
00:50:05,230 --> 00:50:07,800
>> 私はあなたに実際に表示されるまでによ
コー​​ド、そしてそれは多くのコードです。

985
00:50:07,800 --> 00:50:08,674
フリークアウトする必要はありません。

986
00:50:08,674 --> 00:50:09,910
私たちは、それを介して話しましょう​​。

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> 実際には、ありません。

989
00:50:14,020 --> 00:50:15,061
それはちょうど擬似コードでした。

990
00:50:15,061 --> 00:50:17,860
[OK]を、それはただの擬似コードは、ありました
これは少し複雑ですが、

991
00:50:17,860 --> 00:50:19,751
しかし、それは完全に罰金です。

992
00:50:19,751 --> 00:50:21,000
誰もがここに沿って、次の？

993
00:50:21,000 --> 00:50:24,260
ルートがnullの場合、復帰
その手段のため偽

994
00:50:24,260 --> 00:50:26,850
あなたも、そこには何もありません。

995
00:50:26,850 --> 00:50:31,376
>> ルートnは、もしそうであれば値である場合、それ
あなたが見ている1であることを起こります、

996
00:50:31,376 --> 00:50:34,000
あなたがtrueを返すつもりです
あなたが知っているので、あなたはそれを見つけました。

997
00:50:34,000 --> 00:50:36,250
しかし、値が小さい場合
n個のルートよりも、あなたがしています

998
00:50:36,250 --> 00:50:38,332
左側の検索に行きます
子供や左葉、

999
00:50:38,332 --> 00:50:39,540
あなたはそれを呼び出すために好きな。

1000
00:50:39,540 --> 00:50:41,750
その値は、ルートよりも大きい場合、
あなたは右の木を検索するつもりです、

1001
00:50:41,750 --> 00:50:44,610
その後、ちょうど関数を実行
検索を通して再び。

1002
00:50:44,610 --> 00:50:48,037
>> そして、ルートは、そのことを、nullの場合
あなたが最後に達したことを意味？

1003
00:50:48,037 --> 00:50:50,120
それはありません、あなたが持っていることを意味します
検索するよりより多くの葉、

1004
00:50:50,120 --> 00:50:52,230
その後、あなたが知っている、ああ、私は
それがここにいないだと思います

1005
00:50:52,230 --> 00:50:55,063
私が通って見てきた後理由
全部、それはここではないですが、

1006
00:50:55,063 --> 00:50:56,930
それはちょうどここではないかもしれません。

1007
00:50:56,930 --> 00:50:58,350
>> それは誰にでも意味がありますか？

1008
00:50:58,350 --> 00:51:03,230
だから、保存バイナリサーチのようなものです
リンクされたリストの機能を提供します。

1009
00:51:03,230 --> 00:51:09,200
クール、そして第2のタイプ
データ構造の君たち

1010
00:51:09,200 --> 00:51:13,180
あなたのpsetに実装しようとすることができ、
あなたは1つの方法だけを選択する必要があります。

1011
00:51:13,180 --> 00:51:19,430
しかし、おそらく別の方法に
ハッシュテーブルは、我々がトライを呼んでいます。

1012
00:51:19,430 --> 00:51:24,080
>> すべてのトライがあります
ツリーの特定のタイプのもの

1013
00:51:24,080 --> 00:51:28,600
他の値に移動値を持ちます。

1014
00:51:28,600 --> 00:51:31,450
だからではなく、バイナリを持ちます
一つだけの意味でのツリー

1015
00:51:31,450 --> 00:51:35,940
事は2を指すことができ、あなたが持つことができます
多くの、多くのものを一つのポイント。

1016
00:51:35,940 --> 00:51:39,450
あなたは、本質的に配列を持っています
そのうちあなたは店内

1017
00:51:39,450 --> 00:51:41,790
他の配列を指すポインタ。

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> だからどのノード
トライを定義します

1020
00:51:49,460 --> 00:51:52,590
私たちは持っていたいです
ブール、Cワード、右？

1021
00:51:52,590 --> 00:51:54,920
だから、ノードはブール値です
trueまたはfalseのように、

1022
00:51:54,920 --> 00:51:58,490
先頭のすべての最初の
その配列は、これは言葉ですか？

1023
00:51:58,490 --> 00:52:03,620
第二に、あなたはポインタを持っていたいです
何にそれらの残りの部分があります。

1024
00:52:03,620 --> 00:52:07,470
少し複雑、ビット抽象が、
私はどのようなすべての手段ということを説明します。

1025
00:52:07,470 --> 00:52:13,800
>> そこでここでは、上部に、あなたの場合
配列がすでに宣言しています、

1026
00:52:13,800 --> 00:52:17,040
あなたがブールを持っているノード
正面に格納された値

1027
00:52:17,040 --> 00:52:19,490
それはあなたが、これは言葉で伝えますか！

1028
00:52:19,490 --> 00:52:20,520
これは言葉ではないですか？

1029
00:52:20,520 --> 00:52:23,240
そして、あなたが持っています
ご使用のアレイの残りこと

1030
00:52:23,240 --> 00:52:26,040
実際にすべて格納
それは何ができるかの可能性。

1031
00:52:26,040 --> 00:52:28,660
だから、例えば、のような
あなたが持っている一番上に

1032
00:52:28,660 --> 00:52:32,140
真かと言う最初の事
偽、yesまたはno、これは言葉です。

1033
00:52:32,140 --> 00:52:38,130
>> それから、あなたは、26を介して0を持っています
あなたが保存することができます文字。

1034
00:52:38,130 --> 00:52:42,790
私はここで検索したい場合
バットのために、私がトップに行きます

1035
00:52:42,790 --> 00:52:49,200
そして、私は私の中でBを見つけるB.探し
アレイと、私は知っている、[OK]を、Bは言葉ですか？

1036
00:52:49,200 --> 00:52:53,010
Bは言葉ではないので、このように
私が探しておく必要があります。

1037
00:52:53,010 --> 00:52:56,410
私は、Bから行く、と私は見に
Bが向かって指すポインタ

1038
00:52:56,410 --> 00:53:00,900
私は、情報の別の配列を参照してください
我々の前にいたのと同じ構造。

1039
00:53:00,900 --> 00:53:05,240
>> とまあhere--、次の
[聞こえない]の文字はAです。

1040
00:53:05,240 --> 00:53:07,210
だから我々はその配列に見えます。

1041
00:53:07,210 --> 00:53:10,860
私たちは、第八値を見つけ、
し、我々は、ああ、見に見えます

1042
00:53:10,860 --> 00:53:12,840
ねえ、ある単語ことを、B-Aは、単語のですか？

1043
00:53:12,840 --> 00:53:13,807
それは言葉ではありません。

1044
00:53:13,807 --> 00:53:14,890
私たちは、探し続けるようになってきました。

1045
00:53:14,890 --> 00:53:17,850
>> だから我々はどこに目を向けます
ポイントのポインタ、

1046
00:53:17,850 --> 00:53:21,130
それは別の方法を指し
これは我々が格納されているより多くの価値を持っています。

1047
00:53:21,130 --> 00:53:24,150
そして最終的に、私たちはを取得
単語であるB-A-T、。

1048
00:53:24,150 --> 00:53:25,970
だから、次回
あなたが見て、あなたが行っています

1049
00:53:25,970 --> 00:53:30,850
はい、のチェックを持っています、
このブール関数はtrueです。

1050
00:53:30,850 --> 00:53:35,450
だからある意味で、私たちは親切です
配列を持つツリーを持ちます。

1051
00:53:35,450 --> 00:53:39,890
>> だから、あなたは一種のダウン検索することができます。

1052
00:53:39,890 --> 00:53:43,650
むしろハッシュ関数よりと
リンクリストによって値を割り当て、

1053
00:53:43,650 --> 00:53:49,190
あなただけ実装することができます
downwords検索トライ。

1054
00:53:49,190 --> 00:53:50,850
本当に、本当にものを複雑。

1055
00:53:50,850 --> 00:53:54,060
私はのようだから考えることは容易ではありません
非常に多くのデータ構造を吐き

1056
00:53:54,060 --> 00:53:58,710
あなたに、しかし種類のみんなを行います
このロジックがどのように機能するかを理解できますか？

1057
00:53:58,710 --> 00:54:01,920
>> うんいいね。

1058
00:54:01,920 --> 00:54:05,600
だから、B-A-T、その後、
あなたは、検索しようとしています。

1059
00:54:05,600 --> 00:54:07,940
あなたが行っている次の時間
確認するために、ああ、ちょっと、それは本当です、

1060
00:54:07,940 --> 00:54:09,273
このように私はこの言葉でなければなりません知っています。

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> 動物園のために同じこと。

1063
00:54:13,770 --> 00:54:17,960
だからここに事があれば、今の私たちです
今、動物園を探索したかったです、

1064
00:54:17,960 --> 00:54:20,780
現在、動物園ではありません
私たちの辞書で単語

1065
00:54:20,780 --> 00:54:25,300
なぜなら、あなたたちが見ることができるよう、
我々がブールを持っている最初の場所

1066
00:54:25,300 --> 00:54:28,590
trueを返すズームの最後にあります。

1067
00:54:28,590 --> 00:54:30,430
我々は、Z-O-O-Mを持っています。

1068
00:54:30,430 --> 00:54:33,900
>> だからここで、我々は実際にはありません
私たちの辞書で単語、動物園、

1069
00:54:33,900 --> 00:54:36,070
このチェックボックスがチェックされていないため。

1070
00:54:36,070 --> 00:54:39,540
だから、コンピュータはしていません
動物園が単語であることを知っています

1071
00:54:39,540 --> 00:54:42,430
なぜなら私たちはきた道
それを保存され、ここでの唯一のズーム

1072
00:54:42,430 --> 00:54:44,920
実際にBoolean値を持っています
それが真になっています。

1073
00:54:44,920 --> 00:54:49,380
だから我々は、挿入したい場合は
単語、動物園、私たちの辞書に、

1074
00:54:49,380 --> 00:54:51,770
どのように我々はそれをやって行くのでしょうか？

1075
00:54:51,770 --> 00:54:55,960
私たちは確認するために行うには何を持っています
コンピュータは、Z-O-Oは、単語があることを知っています

1076
00:54:55,960 --> 00:54:58,130
そして、ではない最初の単語は、Z-O-O-Mのですか？

1077
00:54:58,130 --> 00:54:59,360
>> 聴衆：[聞こえません]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG：まさに、我々
このことを確認します

1079
00:55:01,450 --> 00:55:07,890
ここでは、ブール値であること
それが本当だとオフにチェック。

1080
00:55:07,890 --> 00:55:13,297
Z-O-Oは、その後、我々はそれを確認しようとしています、
私たちはちょっと、動物園は言葉で、正確に知っています。

1081
00:55:13,297 --> 00:55:15,380
私は言うつもりです
それはそう言葉だコンピュータ

1082
00:55:15,380 --> 00:55:18,000
ときにコンピュータをチェックしています、
それは動物園が単語であることを知っています。

1083
00:55:18,000 --> 00:55:21,269
>> すべてのこれらのデータを覚えているので
構造は、それが私たちのために非常に簡単です

1084
00:55:21,269 --> 00:55:22,310
言って、ああ、バットは言葉です。

1085
00:55:22,310 --> 00:55:22,851
動物園は、言葉です。

1086
00:55:22,851 --> 00:55:23,611
ズーム言葉です。

1087
00:55:23,611 --> 00:55:25,860
しかし、あなたはそれを構築しているときに、
コンピュータがない考えを持っています。

1088
00:55:25,860 --> 00:55:28,619
>> だから、正確にそれを指示する必要があります
どの時点で、これは言葉ですか？

1089
00:55:28,619 --> 00:55:29,910
どの時点でそれは言葉ではないのですか？

1090
00:55:29,910 --> 00:55:31,784
そして、何点で私を行います
物事を検索する必要があり、

1091
00:55:31,784 --> 00:55:34,000
どのような点で私は次行く必要があるのですか？

1092
00:55:34,000 --> 00:55:37,010
その明確な誰？

1093
00:55:37,010 --> 00:55:39,540
クール。

1094
00:55:39,540 --> 00:55:42,530
>> そしてそうそれから来ます
どのように我々の問題だろう

1095
00:55:42,530 --> 00:55:45,560
何かを挿入して行きます
それが実際にはありませんか？

1096
00:55:45,560 --> 00:55:49,090
それでは、ちょうど我々が挿入したいとしましょう
単語、お風呂、私たちのトライに。

1097
00:55:49,090 --> 00:55:53,589
あなたたちは、現在のように見ることができるように
我々が今持っているすべては、B-A-Tであります

1098
00:55:53,589 --> 00:55:55,630
この新しいデータ構造
パイントが持っていました

1099
00:55:55,630 --> 00:55:59,740
我々が想定しているためnullに指摘
それは、ああ、何の言葉は、B-A-Tの後にありません

1100
00:55:59,740 --> 00:56:02,530
なぜ私たちは維持する必要があります
そのT.後のものを持ちます

1101
00:56:02,530 --> 00:56:06,581
>> 私たちはあなたを行う場合でも、問題が発生します
後に来る言葉を持ちたいです

1102
00:56:06,581 --> 00:56:07,080
Tの。

1103
00:56:07,080 --> 00:56:09,500
あなたがお風呂を持っている場合、あなたはしています
Hの右をするつもり。

1104
00:56:09,500 --> 00:56:13,290
そして、私たちはそれをやろうとしている方法です
我々は、別のノードを作成しようとしています。

1105
00:56:13,290 --> 00:56:16,840
私たちは、どのような量を割り当てていません
この新しい配列のためのメモリ、

1106
00:56:16,840 --> 00:56:20,720
我々はポインタを再割り当てするつもりです。

1107
00:56:20,720 --> 00:56:22,947
>> 私たちは、割り当てするつもりです
H、まず第一に、このヌル、

1108
00:56:22,947 --> 00:56:24,030
我々は取り除くつもりです。

1109
00:56:24,030 --> 00:56:26,590
我々は、必要があるとしています
Hポイント下向き。

1110
00:56:26,590 --> 00:56:30,600
我々は、Hが表示された場合、我々はそれをしたいです
どこか別の場所に移動します。

1111
00:56:30,600 --> 00:56:33,910
>> ここでは、[はい]をオフにチェックすることができます。

1112
00:56:33,910 --> 00:56:38,170
我々は、Tの後にHを打つ場合は、ああ、
我々は、これは言葉であることを知っています。

1113
00:56:38,170 --> 00:56:41,110
ブール値trueを返すために起こっています。

1114
00:56:41,110 --> 00:56:42,950
それが起こったのかを明確に誰？

1115
00:56:42,950 --> 00:56:45,110
OK。

1116
00:56:45,110 --> 00:56:47,214
>> だから基本的に、すべての
これらのデータ構造

1117
00:56:47,214 --> 00:56:50,130
私たちは今日の上に行ってきたことを、私はしました
本当に、本当にすぐにそれらを乗り越え

1118
00:56:50,130 --> 00:56:52,192
そしてあまりの中
詳細は、それは大丈夫です。

1119
00:56:52,192 --> 00:56:53,900
あなたはいじり始めると
それを、あなたはなるだろう

1120
00:56:53,900 --> 00:56:55,733
どこの追跡
すべてのポインタは、

1121
00:56:55,733 --> 00:56:58,060
何があなたに起こっています
データ構造、エトセトラ。

1122
00:56:58,060 --> 00:56:59,810
彼らは非常に便利になるだろう、
そして、それはあなた次第です

1123
00:56:59,810 --> 00:57:03,890
男は完全にどのように把握します
あなたは物事を実装したいです。

1124
00:57:03,890 --> 00:57:07,650
>> そしてそうpset4の5--ああ、それは間違っています。

1125
00:57:07,650 --> 00:57:10,140
Pset5はスペルミスです。

1126
00:57:10,140 --> 00:57:13,710
私が前に言ったように、一度、するつもりです
再び、私たちからソースコードをダウンロードしてください。

1127
00:57:13,710 --> 00:57:16,210
3主があるように起こっています
物事はあなたがダウンロードされます。

1128
00:57:16,210 --> 00:57:18,470
あなたは、辞書をダウンロードします
KERS、およびテキスト。

1129
00:57:18,470 --> 00:57:21,660
>> これらすべてのものがありますされています
いずれかの単語の辞書

1130
00:57:21,660 --> 00:57:25,190
我々はあなたがチェックしたいこと
または情報のテスト

1131
00:57:25,190 --> 00:57:26,930
私たちは、あなたがチェックをスペルすることを。

1132
00:57:26,930 --> 00:57:29,670
だから辞書
私たちは、あなたが行く与えます

1133
00:57:29,670 --> 00:57:34,870
あなたに私たちが望む実際の言葉を与えるために
あなたはだ方法で何とか保存します

1134
00:57:34,870 --> 00:57:36,530
配列よりも効率的。

1135
00:57:36,530 --> 00:57:38,470
そしてテキストがあります
私たちがしているものになるだろう

1136
00:57:38,470 --> 00:57:43,900
確認するために、スペルチェックするように求め
すべての単語の本当の言葉があります。

1137
00:57:43,900 --> 00:57:47,970
>> だからの3ブロックは、
私たちはあなたを与えるだろうプログラム

1138
00:57:47,970 --> 00:57:51,130
dictionary.cと呼ばれ、
dictionary.h、およびspeller.c。

1139
00:57:51,130 --> 00:57:56,500
それですべてdictionary.cがされません
何を実装するように求められています。

1140
00:57:56,500 --> 00:57:57,880
それは言葉をロードします。

1141
00:57:57,880 --> 00:58:02,000
これは、チェックをしてスペル、それは確認します
そのすべてが正しく挿入されています。

1142
00:58:02,000 --> 00:58:05,180
>> diction.hはただのライブラリファイルです
それはすべてのこれらの機能を宣言します。

1143
00:58:05,180 --> 00:58:07,650
そしてspeller.c、私たちはあなたを与えるつもりです。

1144
00:58:07,650 --> 00:58:09,290
あなたはそれのいずれかを変更する必要はありません。

1145
00:58:09,290 --> 00:58:14,290
speller.cが行うすべてのことを取ることで、
負荷は、それの速度をチェックし、

1146
00:58:14,290 --> 00:58:19,190
どのようなのベンチマークをテスト
すぐにあなたは物事を行うことができるしています。

1147
00:58:19,190 --> 00:58:20,410
>> これは、スペルチェックです。

1148
00:58:20,410 --> 00:58:23,920
ちょうどそれを台無しにしないが、作ります
あなたはそれがやっているか理解してください。

1149
00:58:23,920 --> 00:58:28,090
我々はGETRUSAGEその呼び出された関数を使用します
スペルの性能をテストします

1150
00:58:28,090 --> 00:58:28,590
チェッカー。

1151
00:58:28,590 --> 00:58:32,200
すべてのそれは基本的にテストされてい
辞書内のすべての時間、

1152
00:58:32,200 --> 00:58:33,680
あなたはそれを理解しておいてください。

1153
00:58:33,680 --> 00:58:36,660
それを台無しにしないように注意してくださいまたは
それ以外のものは、正しく動作しません。

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> そして、この課題の大部分はのためであります
君たちは本当にdictionary.cを変更します。

1156
00:58:44,170 --> 00:58:48,526
私たちはあなたを与えるつもりです
辞書内の単語14万。

1157
00:58:48,526 --> 00:58:50,900
私たちはあなたのテキストを与えるつもりです
これらの言葉を持っているファイル、

1158
00:58:50,900 --> 00:58:54,840
そして、我々はあなたが整理できるようにしたいです
ハッシュテーブルまたはトライにそれら

1159
00:58:54,840 --> 00:58:58,140
我々はスペルをお願いするときのため
あなたが呪文なら想像check--

1160
00:58:58,140 --> 00:59:00,690
ホメロスのオデッセイのようにチェック。

1161
00:59:00,690 --> 00:59:03,010
それはこの巨大な、巨大なテストのようなものです。

1162
00:59:03,010 --> 00:59:05,190
>> 一つ一つの場合を想像
言葉あなたが見なければなりませんでした

1163
00:59:05,190 --> 00:59:08,100
14万値の配列を通じ。

1164
00:59:08,100 --> 00:59:10,350
それは永遠にかかるだろう
お使いのマシンを実行するため。

1165
00:59:10,350 --> 00:59:14,490
私たちはを整理したい理由です
より効率的なデータ構造へのデータ

1166
00:59:14,490 --> 00:59:17,270
このようなハッシュテーブルやトライなど。

1167
00:59:17,270 --> 00:59:20,700
そして、あなたたちは親切なことができます
あなたがアクセスを検索したときの

1168
00:59:20,700 --> 00:59:22,570
物事をより簡単に、より迅速に。

1169
00:59:22,570 --> 00:59:24,934
>> そしてそう衝突を解決するように注意してください。

1170
00:59:24,934 --> 00:59:27,350
あなたは束を取得するつもりです
Aとその開始の言葉の

1171
00:59:27,350 --> 00:59:29,957
あなたはたくさんの単語を取得するつもりです
それはあなたまでBで開始します

1172
00:59:29,957 --> 00:59:31,290
あなたはそれを解決する方法をみんな。

1173
00:59:31,290 --> 00:59:34,144
おそらく、もっとあります
効率的なハッシュ関数

1174
00:59:34,144 --> 00:59:36,810
のちょうど最初の文字より
何か、などそれはあなた次第です

1175
00:59:36,810 --> 00:59:38,190
人は種類のあなたがやりたいします。

1176
00:59:38,190 --> 00:59:40,148
>> たぶん、あなたは、追加したいです
一緒にすべての文字。

1177
00:59:40,148 --> 00:59:43,410
たぶん、あなたは奇妙なことを行うが好きにしたいです
文字の数を考慮するために、

1178
00:59:43,410 --> 00:59:43,970
なんでも。

1179
00:59:43,970 --> 00:59:45,386
あなたがしたいかあなたたちまで。

1180
00:59:45,386 --> 00:59:49,262
あなたがあれば、ハッシュテーブルをしたい場合
完全にあなた次第、トライを試してみたいです。

1181
00:59:49,262 --> 00:59:52,470
私は前もって警告が表示されます
トライは、一般的に少しより困難です

1182
00:59:52,470 --> 00:59:54,520
たくさんがありますという理由だけで
を追跡するために、複数のポインタ。

1183
00:59:54,520 --> 00:59:55,645
しかし、完全にあなたたちまで。

1184
00:59:55,645 --> 00:59:58,742
それは、はるかに効率的です
ほとんどの場合です。

1185
00:59:58,742 --> 01:00:01,450
あなたは本当に維持できるようにしたいです
あなたのポインタのすべてのトラック。

1186
01:00:01,450 --> 01:00:03,850
以下のように同じことを行います
私はここでやっていたこと。

1187
01:00:03,850 --> 01:00:06,871
あなたが挿入しようとしているとき
ハッシュテーブルに値または削除、

1188
01:00:06,871 --> 01:00:08,620
あなたがしていることを確認してください
本当にを追跡すること

1189
01:00:08,620 --> 01:00:11,860
すべてがあるためであるの
私は場合のために、それは本当に簡単です

1190
01:00:11,860 --> 01:00:14,727
単語、アンディのように挿入しようとしています。

1191
01:00:14,727 --> 01:00:16,810
ちょうどそれがだとしましょう
本当の単語、単語、アンディ、

1192
01:00:16,810 --> 01:00:19,640
言葉の巨大なリストに。

1193
01:00:19,640 --> 01:00:22,450
>> 私はちょうど再割り当ててしまった場合
間違ったポインタ、おっと、

1194
01:00:22,450 --> 01:00:24,940
全体をそこに行きます
私のリンクリストの残りの部分。

1195
01:00:24,940 --> 01:00:26,897
今だけの単語私
持って今アンディで、

1196
01:00:26,897 --> 01:00:29,230
内の他のすべての単語
辞書が失われています。

1197
01:00:29,230 --> 01:00:31,370
だから、あなたを確認します
あなたのポインタのすべてを追跡します

1198
01:00:31,370 --> 01:00:33,661
あるいはあなたが取得するつもりです
あなたのコード内の巨大な問題。

1199
01:00:33,661 --> 01:00:35,840
ステップバイステップで慎重に物事を描画します。

1200
01:00:35,840 --> 01:00:37,870
それは非常に簡単で考えるようになります。

1201
01:00:37,870 --> 01:00:40,910
>> そして最後に、次のことができるようにしたいです
プログラムのパフォーマンスをテストします

1202
01:00:40,910 --> 01:00:41,618
ビッグボード上。

1203
01:00:41,618 --> 01:00:43,710
あなたたちは取る場合
今CS50を見て、

1204
01:00:43,710 --> 01:00:45,210
私たちは大きなボードと呼ばれるものがあります。

1205
01:00:45,210 --> 01:00:50,200
これは、最速のスコアシートであります
CS50のすべてにわたって回スペルチェック

1206
01:00:50,200 --> 01:00:55,720
今、私は10のようなトップだと思います
回私はそれらの8スタッフだと思います。

1207
01:00:55,720 --> 01:00:57,960
私たちは本当にあなたたちは私たちを打つしたいと思います。

1208
01:00:57,960 --> 01:01:00,870
>> 私たちのすべてが実現しようとしていました
可能な限り最速のコード。

1209
01:01:00,870 --> 01:01:04,880
私たちは、あなたたちは挑戦してみたいです
私たちと私たちのすべてよりも早く実現

1210
01:01:04,880 --> 01:01:05,550
することができます。

1211
01:01:05,550 --> 01:01:07,970
そして、これは実際にあります
私たちがしている初めて

1212
01:01:07,970 --> 01:01:12,680
そのPSETを行うには君たちを求め
あなたは本当にどんな方法で行うことができます

1213
01:01:12,680 --> 01:01:13,760
あなたが欲しいです。

1214
01:01:13,760 --> 01:01:17,730
>> 私はいつも、これは、より類似している、と言います
現実のソリューションには、右？

1215
01:01:17,730 --> 01:01:19,550
私はちょっと、私はあなたがこれを行う必要があり、言います。

1216
01:01:19,550 --> 01:01:21,380
私のためにこれを行い、プログラムをビルドします。

1217
01:01:21,380 --> 01:01:22,630
あなたが欲しいしかし、それを実行してください。

1218
01:01:22,630 --> 01:01:24,271
私はちょうど私が断食したいことを知っています。

1219
01:01:24,271 --> 01:01:25,770
つまり、この週のあなたの挑戦です。

1220
01:01:25,770 --> 01:01:27,531
君たちは、我々が行っています
あなたのタスクを得ました。

1221
01:01:27,531 --> 01:01:29,030
私たちはあなたの挑戦を与えるつもりです。

1222
01:01:29,030 --> 01:01:31,559
そして、それは君たち次第です
完全にちょうど把握します

1223
01:01:31,559 --> 01:01:34,100
最も迅速で何
これを実現する効率的な方法。

1224
01:01:34,100 --> 01:01:34,600
うん？

1225
01:01:34,600 --> 01:01:37,476
>> 観客：我々は場合に許可されています
より高速な方法を研究したかったです

1226
01:01:37,476 --> 01:01:40,821
オンラインハッシュテーブルを行うには、我々が行うことができます
その誰かの他の人のコードを引用？

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG：ええ、完全に罰金。

1228
01:01:42,070 --> 01:01:44,320
だからみんなが読ん場合
スペックは、行あります

1229
01:01:44,320 --> 01:01:48,310
君たちと言う仕様で
ハッシュの検索するには完全に無料です

1230
01:01:48,310 --> 01:01:51,070
何がいくつかの機能
迅速にハッシュ関数の

1231
01:01:51,070 --> 01:01:54,720
などを通じて物事を実行します
あなたがそのコードを引用として長いです。

1232
01:01:54,720 --> 01:01:57,220
だから、何人かの人々がすでに持っています
高速な方法を考え出しました

1233
01:01:57,220 --> 01:02:00,250
スペルチェッカーを行うための、高速の
情報を保存する方法。

1234
01:02:00,250 --> 01:02:02,750
完全にあなたたちまであなたの場合
右、ちょうどそれを取るしたいですか？

1235
01:02:02,750 --> 01:02:04,045
あなたが引用していることを確認します。

1236
01:02:04,045 --> 01:02:06,170
ここでの課題は、実際に
我々は、テストしようとしていること

1237
01:02:06,170 --> 01:02:09,750
あなたが知っていることを確認することさ
ポインタの周りにあなたの方法。

1238
01:02:09,750 --> 01:02:12,700
限りあなたが実現するとして
実際のハッシュ関数

1239
01:02:12,700 --> 01:02:15,070
などを考え出します
数学はそれを行うには、

1240
01:02:15,070 --> 01:02:17,570
君たちは何でも調べることができ
方法はオンライン君たちが欲しいです。

1241
01:02:17,570 --> 01:02:17,996
うん？

1242
01:02:17,996 --> 01:02:19,700
>> 観客：我々だけ挙げることができます
[聞こえない]を使用して？

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG：うん。

1244
01:02:20,120 --> 01:02:22,328
することができますだけで、あなたのコメントで、
あなたは、ああ、のように挙げることができます

1245
01:02:22,328 --> 01:02:26,127
矢田から取られ、矢田、
矢田、ハッシュ関数。

1246
01:02:26,127 --> 01:02:27,210
誰もが任意の質問がありますか？

1247
01:02:27,210 --> 01:02:29,694
私たちは実際にbreezed
今日貫通部。

1248
01:02:29,694 --> 01:02:31,610
私はにここになります
同様の質問に答えます。

1249
01:02:31,610 --> 01:02:36,570
>> また、私が言ったように、オフィス
時間今夜と明日。

1250
01:02:36,570 --> 01:02:40,307
今週は実際にスペック
超簡単、読み超短いです。

1251
01:02:40,307 --> 01:02:43,140
私は、見てみることをお勧め
それの全体をお読みください。

1252
01:02:43,140 --> 01:02:45,730
>> そしてZamylaは実際にあなたを歩きます
機能のそれぞれを介して

1253
01:02:45,730 --> 01:02:49,796
あなたが実装する必要があり、それはです
すべてを行うにはどのように非常に、非常に明確。

1254
01:02:49,796 --> 01:02:51,920
ちょうどあなたがしている作ります
ポインタを追跡します。

1255
01:02:51,920 --> 01:02:53,650
これは非常に困難PSETあります。

1256
01:02:53,650 --> 01:02:56,744
>> 以下のようなので、それは、挑戦的ではありません
ああ、概念はそんなに多くあり

1257
01:02:56,744 --> 01:02:59,160
困難な、またはあなたが学ぶ必要があります
そんなに新しい構文方法

1258
01:02:59,160 --> 01:03:00,650
あなたは最後のpsetのためにしたこと。

1259
01:03:00,650 --> 01:03:03,320
このPSETは困難であるため、
非常に多くのポインタがありますが、

1260
01:03:03,320 --> 01:03:06,980
そしてそれは一度に非常に、非常に簡単です
あなたはあなたのコードにバグがありことができません

1261
01:03:06,980 --> 01:03:08,315
そのバグがどこにあるか見つけるために。

1262
01:03:08,315 --> 01:03:13,200
>> あなたの中にそしてそう全くの信仰
みんなは私たちの[聞こえない]を打つことができるように

1263
01:03:13,200 --> 01:03:13,700
スペル。

1264
01:03:13,700 --> 01:03:16,640
私は実際に書かれた鉱山を持っていません
まだ、私は私を書くことについてです。

1265
01:03:16,640 --> 01:03:19,070
だから、あなたが書いている間
あなたは、私は私を書くことになります。

1266
01:03:19,070 --> 01:03:21,070
私が作ってみるつもりです
速くあなたより私のもの。

1267
01:03:21,070 --> 01:03:23,940
私たちは、最速の1を持っている人を参照してくださいます。

1268
01:03:23,940 --> 01:03:27,340
>> そして、ええ、私はすべてのを見ることができます
ここで火曜日に君たち。

1269
01:03:27,340 --> 01:03:29,510
私はPSETのワークショップのような種類を実行します。

1270
01:03:29,510 --> 01:03:32,640
セクションのすべてのこの
週のpsetのワークショップであり、

1271
01:03:32,640 --> 01:03:36,690
だからあなたたちは機会がたくさんあり​​ます
いつものように助けのため、営業時間、

1272
01:03:36,690 --> 01:03:41,330
私は本当にを楽しみにしています
あなたの男「すべてのコードを読み取ります。

1273
01:03:41,330 --> 01:03:44,160
あなた場合、私はここでクイズを持っています
人はそれらを得る来てほしいです。

1274
01:03:44,160 --> 01:03:45,880
それで全部です。

1275
01:03:45,880 --> 01:03:48,180