1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> DAVIDマラン：すべての権利。

3
00:00:12,250 --> 00:00:13,860
CS50におかえりなさい。

4
00:00:13,860 --> 00:00:16,190
これは8週の始まりです。

5
00:00:16,190 --> 00:00:21,320
そして問題は終わった5を設定することを思い出す
挑戦の少しと。

6
00:00:21,320 --> 00:00:25,210
だから、あなたのすべてを回収したと仮定して
教育フェローとCAの写真

7
00:00:25,210 --> 00:00:30,480
card.rawファイルには、対象となります
今、それらの人々のすべてを見つけることにし、

8
00:00:30,480 --> 00:00:34,510
1の幸運な勝者は1と一緒に家に歩いていく
これらのものの、うるう運動

9
00:00:34,510 --> 00:00:37,450
あなたが最終的に使用できるデバイス
インスタンスのためのプロジェクト、。

10
00:00:37,450 --> 00:00:39,860
>> これは、毎年、につながる
creepinessのビット。

11
00:00:39,860 --> 00:00:43,480
そして私は私がやるだろうと思っていたことは共有です
あなたと一緒に持っているノートの一部

12
00:00:43,480 --> 00:00:47,370
上の前後に行っ
後半のスタッフ一覧。

13
00:00:47,370 --> 00:00:51,110
例えば、ただ昨晩、引用
スタッフの一人からの引用終わり、

14
00:00:51,110 --> 00:00:55,000
メンバーは、 "私はちょうど学生ノックしていた
私のドアに私と一緒に写真を撮るために。

15
00:00:55,000 --> 00:00:59,020
ストーカーは、私はあなたを教えてください。 "オフ開始
我々は移動した後、かなり説明的

16
00:00:59,020 --> 00:01:02,830
へと、時間かそこら後、 "私が持っていた
セクションの後に私を待っている学生

17
00:01:02,830 --> 00:01:06,080
そして、彼は私たちの名前と写真のすべてを持っていた
紙の一部シートに。 "すべての権利。

18
00:01:06,080 --> 00:01:09,230
だから組織化ではなく、
まだすべてが不気味。

19
00:01:09,230 --> 00:01:12,520
>> その後、 "私はこの週末は、町外であった
と私が帰ってきたときに、いずれかであった

20
00:01:12,520 --> 00:01:12,630
私の

21
00:01:12,630 --> 00:01:16,740
寝室。 "[笑い]

22
00:01:16,740 --> 00:01:20,410
DAVIDマラン：スタッフから次の引用
メンバーが、 "学生で私の家に来た

23
00:01:20,410 --> 00:01:25,330
4でサマービルは今朝AM。 "次
スタッフは、 "私はサンに私のホテルに着いた

24
00:01:25,330 --> 00:01:30,016
サンフランシスコと学生が待っていた
3デジタル一眼レフカメラとのロビーで私を。 "

25
00:01:30,016 --> 00:01:31,510
カメラのタイプ。

26
00:01:31,510 --> 00:01:34,980
"私は、スタッフのこの学期でさえないんだけど
しかし、学生が私の家にこれを破った

27
00:01:34,980 --> 00:01:40,480
全部を記録した朝と
。グーグルグラスを持つ "そして最後に、

28
00:01:40,480 --> 00:01:43,650
"少なくとも12人は熱心だった
私は外に着いたとき、私のため待って

29
00:01:43,650 --> 00:01:44,800
リムジン、そして私

30
00:01:44,800 --> 00:01:46,970
目が覚めた。 "すべての権利。

31
00:01:46,970 --> 00:01:57,690
だから、写真の中で、あなたは可能性がある
リコールは、ここでこの仲間、あなたです

32
00:01:57,690 --> 00:02:01,850
住んでミロバナナ、として知っているかもしれません
ローレンカルバリョ、私たちの頭の

33
00:02:01,850 --> 00:02:02,905
フェローを教える。

34
00:02:02,905 --> 00:02:05,170
ミロ、ミロは、ここで少年に来る。

35
00:02:05,170 --> 00:02:06,320
ミロ。

36
00:02:06,320 --> 00:02:08,650
ミロ。

37
00:02:08,650 --> 00:02:12,230
そう、彼はGoogleのガラスを身に着けている、あなたの心
私たちはあなたにこのすべてをした後に紹介しま​​す。

38
00:02:12,230 --> 00:02:16,190
あなたがしたい場合ので、これはミロです
その後彼と一緒に写真を撮る。

39
00:02:16,190 --> 00:02:18,240
あなたが出て見えるしたい場合
そこに観客で。

40
00:02:18,240 --> 00:02:19,430
OK。

41
00:02:19,430 --> 00:02:20,200
それは良い映像だ。

42
00:02:20,200 --> 00:02:22,556
まあ、ミロバナナ。

43
00:02:22,556 --> 00:02:23,941
ああ、それをしない。

44
00:02:23,941 --> 00:02:29,020
>> [笑い]

45
00:02:29,020 --> 00:02:29,470
>> OK。

46
00:02:29,470 --> 00:02:34,550
先にあるもので、その後の単語だから、
我々は移行を始めるとなぜなら、

47
00:02:34,550 --> 00:02:38,410
今週具体的には、Cから
PHPのコマンドライン環境と

48
00:02:38,410 --> 00:02:42,720
JavaScriptとSQLとHTMLとCSSの
Webベースの環境では、我々はできるでしょう

49
00:02:42,720 --> 00:02:44,490
すべてであなたを装備
ためのより多くの知識

50
00:02:44,490 --> 00:02:46,010
潜在的な最終的なプロジェクト。

51
00:02:46,010 --> 00:02:49,240
そのために、コースは持って
その開催セミナーの伝統

52
00:02:49,240 --> 00:02:50,950
接線のトピックにある
コー​​スに。

53
00:02:50,950 --> 00:02:54,330
非常にプログラミングとの関連
アプリの開発などが、

54
00:02:54,330 --> 00:02:57,010
必ずしもで探検しない
もちろん独自のシラバス。

55
00:02:57,010 --> 00:03:00,250
>> 1つに興味があるかもしれませんので、もし
今年のセミナーの以上、

56
00:03:00,250 --> 00:03:02,530
cs50.net/seminarで登録。

57
00:03:02,530 --> 00:03:06,170
年上のセミナーがあります
cs50.net/seminarsで。

58
00:03:06,170 --> 00:03:10,620
そして今年のこれまでの名簿上の
ルビーとア​​メージングのWebアプリにある

59
00:03:10,620 --> 00:03:13,580
代替手段ですレール、
PHPの言語。

60
00:03:13,580 --> 00:03:14,900
計算言語学。

61
00:03:14,900 --> 00:03:18,710
であるiOSの、入門
iPhoneとのために使われているプラ​​ットフォーム

62
00:03:18,710 --> 00:03:19,850
iPadの開発。

63
00:03:19,850 --> 00:03:22,890
JavaScriptはウェブアプリのために、我々は説明します
それが、このセミナーでは、あなたが行くよ

64
00:03:22,890 --> 00:03:24,070
詳細へ。

65
00:03:24,070 --> 00:03:27,390
>> モーションリープので、実際にいくつかを持っているよ
リープモーションからの我々の友人の、

66
00:03:27,390 --> 00:03:29,160
会社自体は、私たちに参加。

67
00:03:29,160 --> 00:03:31,800
提供するために、明日、実際には、
ハンズオンセミナー、もし

68
00:03:31,800 --> 00:03:33,320
あなたに関心の。

69
00:03:33,320 --> 00:03:38,770
Meteor.js、ための代替技術
、ブラウザでJavaScriptを使用していない

70
00:03:38,770 --> 00:03:39,970
しかし、サーバー上の。

71
00:03:39,970 --> 00:03:42,110
非常によく似ていますNode.jsの、
その静脈だけでなく。

72
00:03:42,110 --> 00:03:43,650
なめらかなAndroidのデザイン。

73
00:03:43,650 --> 00:03:46,990
Androidは非常に人気の代替であること
iOSとWindowsの携帯電話へ

74
00:03:46,990 --> 00:03:48,790
やその他のモバイルプラットフォーム。

75
00:03:48,790 --> 00:03:51,180
およびWebセキュリティアクティブディフェンス。

76
00:03:51,180 --> 00:03:54,590
>> だから実際には、あなたがご希望の場合
これに従事する、私を聞かせて

77
00:03:54,590 --> 00:03:55,840
これをメモしておきます。

78
00:03:55,840 --> 00:03:57,790
我々は、と言うことは非常に満足している
リープで私たちの友人

79
00:03:57,790 --> 00:03:59,140
スタートアップで動き、 - 

80
00:03:59,140 --> 00:04:01,300
このデバイスは、実際には来
数ヶ月前から - 

81
00:04:01,300 --> 00:04:05,960
優雅に30このようなデバイスを寄贈しました
など、多くの学生のためのクラス、場合に

82
00:04:05,960 --> 00:04:08,670
あなたは、ハードウェアを借りたいのですが
学期の終わりに向かってとのためにそれを使用

83
00:04:08,670 --> 00:04:10,390
実際の最終的なプロジェクト。

84
00:04:10,390 --> 00:04:11,890
彼らは、多くの言語をサポートしています。

85
00:04:11,890 --> 00:04:16,040
それらのどれもないようにC、それらのどれもPHP、
実現するこれらのセミナーの一つ以上の

86
00:04:16,040 --> 00:04:16,899
関心の証明するかもしれない。

87
00:04:16,899 --> 00:04:19,730
それらのすべてはで撮影されます
あなたができないことをイベント

88
00:04:19,730 --> 00:04:21,380
本人が出席する。

89
00:04:21,380 --> 00:04:25,000
スケジュールは経由して発表される
私たちは部屋を固めるようにメールしてください。

90
00:04:25,000 --> 00:04:28,460
>> そして最後に、あなたがに行けば
projects.cs.50.net、これはウェブサイトです

91
00:04:28,460 --> 00:04:31,450
我々は招待する毎年維持
コミュニティからの人々、教職員、

92
00:04:31,450 --> 00:04:36,420
部門、スタッフ、両方
CS50への外で

93
00:04:36,420 --> 00:04:37,730
プロジェクトのアイデアを提案する。

94
00:04:37,730 --> 00:04:39,050
学生グループに興味のあるもの。

95
00:04:39,050 --> 00:04:40,600
部門に興味のあるもの。

96
00:04:40,600 --> 00:04:43,990
あなたが苦労している場合、そうそこに回すか
何かの不確実性

97
00:04:43,990 --> 00:04:46,700
自分で取り組むことを望む。

98
00:04:46,700 --> 00:04:51,760
>> 我々は間違いなく導入されたので、最後の時間
より複雑なデータ構造我々が思いより

99
00:04:51,760 --> 00:04:53,300
過去数週間で見られる。

100
00:04:53,300 --> 00:04:56,550
我々は、かなりの配列を使用していたい
もし喜んとして有用

101
00:04:56,550 --> 00:04:58,160
単純なデータ構造。

102
00:04:58,160 --> 00:05:00,570
次に我々は、これらを導入している
もちろんリストをリンクされています。

103
00:05:00,570 --> 00:05:05,470
と動機の一つだったもの
このデータ構造を導入？

104
00:05:05,470 --> 00:05:06,930
うん？

105
00:05:06,930 --> 00:05:07,250
何それ？

106
00:05:07,250 --> 00:05:08,080
>> 聴衆：ダイナミックサイズ。

107
00:05:08,080 --> 00:05:09,040
>> DAVIDマラン：ダイナミックサイズ。

108
00:05:09,040 --> 00:05:11,890
配列のに対しだから、あなたがする必要があります
場合は、事前にその大きさを知る

109
00:05:11,890 --> 00:05:12,740
あなたはそれを割り当てる。

110
00:05:12,740 --> 00:05:14,380
リンクされたリストで、あなたはしないでください
ことを知っている必要があります。

111
00:05:14,380 --> 00:05:17,610
あなたは、より一般的に単にmalloc関数、または、することができます
追加を割り当てる

112
00:05:17,610 --> 00:05:20,720
ノード、いわば、あなたはいつでも
より多くのデータを挿入したい。

113
00:05:20,720 --> 00:05:22,670
そして、ノードは所定の意味を持ちません。

114
00:05:22,670 --> 00:05:25,580
それはちょうど記述総称です
私たちがしていることをコンテナのいくつかの種類

115
00:05:25,580 --> 00:05:29,610
保存するには、弊社のデータ構造での使用
この中で興味のあるいくつかの項目、その

116
00:05:29,610 --> 00:05:31,750
ケースは整数であることが起こる。

117
00:05:31,750 --> 00:05:33,160
>> しかし、トレードオフが常にある。

118
00:05:33,160 --> 00:05:38,070
そこで、データの動的なサイズを取得する
構造が、我々はどのような価格を支払うのですか？

119
00:05:38,070 --> 00:05:40,040
リンクリストの欠点は何ですか？

120
00:05:40,040 --> 00:05:41,006
うん？

121
00:05:41,006 --> 00:05:41,980
>> 観客は：多くのメモリが必要です。

122
00:05:41,980 --> 00:05:44,240
>> DAVIDマラン：それはより多くを必要とする
メモリ、どのように正確？

123
00:05:44,240 --> 00:05:46,440
>> 読者：[聞こえない]。

124
00:05:46,440 --> 00:05:47,050
>> DAVIDマラン：その通り。

125
00:05:47,050 --> 00:05:50,460
だから今我々は、ポインタを取っている
私たちは以前にその増設メモリ

126
00:05:50,460 --> 00:05:53,040
利点ので、必要はありませんでした
アレイもちろん、すなわち

127
00:05:53,040 --> 00:05:54,860
すべてが連続し、帰ってきた
背面にバックアップするには、どの

128
00:05:54,860 --> 00:05:56,380
あなたにランダムアクセスを提供します。

129
00:05:56,380 --> 00:06:00,710
なぜなら単に角括弧を使用することにより
表記法、あるいはそれ以上の技術的にポインタ

130
00:06:00,710 --> 00:06:03,580
算術、非常に単純に加え、
何かにアクセスすることができます

131
00:06:03,580 --> 00:06:05,700
一定時間内の要素。

132
00:06:05,700 --> 00:06:08,975
実際に、それはを示唆のようなものだ
我々が払っていることを別の価格

133
00:06:08,975 --> 00:06:09,760
リンクリスト。

134
00:06:09,760 --> 00:06:13,890
>> 何の実行時間に起こる
検索のようなもの、私がしたい場合

135
00:06:13,890 --> 00:06:17,270
いくつかの値と内部を見つける
リンクリストの？

136
00:06:17,270 --> 00:06:20,290
私の実行時間はどうなるのでしょうか？

137
00:06:20,290 --> 00:06:21,560
nはビッグオー。

138
00:06:21,560 --> 00:06:24,060
それに替えられている場合は？

139
00:06:24,060 --> 00:06:25,440
データ構造がソートいたら？

140
00:06:25,440 --> 00:06:28,640
私はビッグよりも良い行うことができます
検索するためのnのO？

141
00:06:28,640 --> 00:06:31,700
いや、最悪の場合、それは可能性があるため
非常によく並べ、その数れる

142
00:06:31,700 --> 00:06:32,950
あなたが探していることは、大きな可能性があります。

143
00:06:32,950 --> 00:06:35,370
これは、どの番号100、かもしれない
すべてのことが起こるかもしれません

144
00:06:35,370 --> 00:06:36,410
末尾の方法。

145
00:06:36,410 --> 00:06:39,950
そして、あなたは唯一のリンクにアクセスすることができますので、
することにより、この実装ではリスト

146
00:06:39,950 --> 00:06:42,690
その最初のノードのように、あなたはしている
まだ運のようなもののうち、。

147
00:06:42,690 --> 00:06:47,450
あなたは、全体を横断する必要があります
最初から見つけるために最後まで

148
00:06:47,450 --> 00:06:49,150
100のようにその大きな価値。

149
00:06:49,150 --> 00:06:51,350
それともそれはかどうかを判断するために
なくてもそこに。

150
00:06:51,350 --> 00:06:55,960
>> だから私たちは、データのどのアルゴリズムで行うことはできません
このように見える構造は？

151
00:06:55,960 --> 00:06:59,460
ので、私たちは、バイナリ検索を行うことができません
我々が持っていたことが必要とバイナリサーチ

152
00:06:59,460 --> 00:07:00,740
ランダムアクセス。

153
00:07:00,740 --> 00:07:04,500
私たちはただの場所から飛躍でした
フォローしなくても場所

154
00:07:04,500 --> 00:07:07,080
フォームでこれらのパン粉
すべてのこれらのポインタ。

155
00:07:07,080 --> 00:07:08,300
>> さて、どのように我々はこれを実装したのですか？

156
00:07:08,300 --> 00:07:12,830
まあ、我々はここで画面に行けば、もし
我々はすぐに、このデータを再実装することができます

157
00:07:12,830 --> 00:07:13,440
構造 - 

158
00:07:13,440 --> 00:07:15,670
私の筆跡は、すべてのことではありません
ここで素晴らしい、しかし我々は試してみます。

159
00:07:15,670 --> 00:07:22,030
だからます。typedef struct、と私がした
この事をここに呼び出すしたいですか？

160
00:07:22,030 --> 00:07:22,960
ノード。

161
00:07:22,960 --> 00:07:24,580
だから私は、私たちが始められるでしょう。

162
00:07:24,580 --> 00:07:27,860
そして今、内部のように必要なもの
その単独でのデータ構造

163
00:07:27,860 --> 00:07:28,430
リンクリスト？

164
00:07:28,430 --> 00:07:29,950
どのように多くの分野？

165
00:07:29,950 --> 00:07:30,450
>> 2だから。

166
00:07:30,450 --> 00:07:31,570
一つは、非常に簡単です。

167
00:07:31,570 --> 00:07:33,050
nにint型。

168
00:07:33,050 --> 00:07:35,930
そして、私たちは、私たちが望むnの何を呼び出すことができます
我々は、ならそれがint型でなければなりません

169
00:07:35,930 --> 00:07:37,660
int型のためのリンクリストを実装する。

170
00:07:37,660 --> 00:07:41,920
そして今、第二に何をするか
フィールドがあることがありますか？

171
00:07:41,920 --> 00:07:43,460
構造ノード*。

172
00:07:43,460 --> 00:07:50,570
だから私は、構造体ノード*、そして私をすれば
また、私はやりたい、これを呼び出すことができ、

173
00:07:50,570 --> 00:07:53,510
しかし、ちょうど私が電話するよ明確にする
私たちが行ってきたとして、それを次の。

174
00:07:53,510 --> 00:07:55,270
そして私は私の中括弧を閉じます。

175
00:07:55,270 --> 00:08:00,700
>> そして今、最後の時間のように、
私はここで、ノードを置く。

176
00:08:00,700 --> 00:08:03,830
しかし、私はこれを宣言しているかのようである
ノード、なぜ私はそうされてわざわざでし

177
00:08:03,830 --> 00:08:07,320
ここで構造体を宣言するに冗長
ノードは、*次に、反対した

178
00:08:07,320 --> 00:08:09,210
次のノードだけ*に？

179
00:08:09,210 --> 00:08:09,904
うん？

180
00:08:09,904 --> 00:08:12,810
>> 読者：[聞こえない]。

181
00:08:12,810 --> 00:08:14,050
>> DAVIDマラン：その通り。

182
00:08:14,050 --> 00:08:14,530
まさに。

183
00:08:14,530 --> 00:08:18,320
Cは本当にあなたを文字通りかかるためと
唯一のノードの定義を見て

184
00:08:18,320 --> 00:08:21,230
ここでダウン方法、することはできません
ここでそれまで参照してください。

185
00:08:21,230 --> 00:08:24,760
だから我々は先制のこの種を持っている
確かにここで宣言され、

186
00:08:24,760 --> 00:08:25,390
より冗長。

187
00:08:25,390 --> 00:08:27,810
構造体ノードは、その手段
我々は今それをアクセスすることができます

188
00:08:27,810 --> 00:08:29,760
データ構造の内部。

189
00:08:29,760 --> 00:08:33,370
>> そして、これがあるので、脇など
、今ではもう少し主観的になってき

190
00:08:33,370 --> 00:08:36,230
星は技術的にここに行くことができ、
それはここに行くことができ、それができ

191
00:08:36,230 --> 00:08:37,179
でも、真ん中に行く。

192
00:08:37,179 --> 00:08:39,890
我々のスタイルガイドでは、採択されまし​​た
もちろん、パッティングの大会

193
00:08:39,890 --> 00:08:42,299
右隣のデータにつ
そのこの場合はタイプ、、

194
00:08:42,299 --> 00:08:43,460
構造のノードになります。

195
00:08:43,460 --> 00:08:46,620
しかし、教科書の多くで実現し、
オンラインリファレンス、あなたは確かかもしれない

196
00:08:46,620 --> 00:08:48,450
反対側にそれを参照してください。

197
00:08:48,450 --> 00:08:52,200
しかし、単に双方が実際にすることを実現する
仕事とは、単純であるべき

198
00:08:52,200 --> 00:08:52,970
一貫性のある。

199
00:08:52,970 --> 00:08:53,580
>> わかりました。

200
00:08:53,580 --> 00:08:55,630
だから私たちの宣言だった
構造ノードの。

201
00:08:55,630 --> 00:08:59,430
しかし、その後、我々はより多くを始め
洗練されたもの。

202
00:08:59,430 --> 00:09:03,410
例えば、我々が導入を決定
ハッシュテーブルのようなもの。

203
00:09:03,410 --> 00:09:08,160
だからここにサイズnのハッシュテーブルがあり、
nの左上に0からインデックス

204
00:09:08,160 --> 00:09:09,690
マイナス底面の1を残しました。

205
00:09:09,690 --> 00:09:11,640
これは、ハッシュ可能性があり
何のためのテーブル。

206
00:09:11,640 --> 00:09:15,340
しかし、我々は物事の種類を話したのか
のハッシュテーブルを使用してはどうでしょうか？

207
00:09:15,340 --> 00:09:18,370
何を保存する？

208
00:09:18,370 --> 00:09:18,800
>> 名称。

209
00:09:18,800 --> 00:09:20,870
我々のような名前を行うことができ
我々は最後の時間でした。

210
00:09:20,870 --> 00:09:22,200
そして実際に、あなたは何を保存することができます。

211
00:09:22,200 --> 00:09:24,640
そして、我々は再びこれを見るだろう
PHPとJavaScriptである。

212
00:09:24,640 --> 00:09:28,550
ハッシュテーブルは、スイスの素敵なものです
あなたが保存することができアーミーナイフ

213
00:09:28,550 --> 00:09:33,690
ほとんどあなたの中の好きな
値を持つキーを関連付けることによって、それ。

214
00:09:33,690 --> 00:09:34,770
値を持つキー。

215
00:09:34,770 --> 00:09:37,800
>> 今、このような単純なケースでは、我々の
キーは数字だけです。

216
00:09:37,800 --> 00:09:40,380
私たちは、ハッシュを実装している
配列としてテーブル。

217
00:09:40,380 --> 00:09:43,500
そしてキーは0であり、
1,2、等が挙げられる。

218
00:09:43,500 --> 00:09:47,200
そして我々は、人間として、最後の決め
あなたは私たちがしている場合はどうでしょう、知っている週

219
00:09:47,200 --> 00:09:50,410
ストア名に行く、みましょうだけ
任意ですが、かなり合理的に、

220
00:09:50,410 --> 00:09:54,680
仮定アリス、名前、
ただ0に索引付けされます。

221
00:09:54,680 --> 00:09:58,030
とボブ、B名前は、索引付けされます
1に、等が挙げられる。

222
00:09:58,030 --> 00:10:02,490
だから我々は、入力間のマッピングを持っていた
これは文字列で、ハッシュ

223
00:10:02,490 --> 00:10:04,560
数字である場所。

224
00:10:04,560 --> 00:10:07,740
>> だから方法は、一般として知られている
ハッシュ関数、あなたは本当にすることができます

225
00:10:07,740 --> 00:10:09,130
コー​​ドでそれを実装する。

226
00:10:09,130 --> 00:10:12,080
私は、ハッシュ関数を実装したい場合
まさに我々ないこと

227
00:10:12,080 --> 00:10:17,070
ただ私は、前回からかもしれない説明
として、取る関数を宣言する

228
00:10:17,070 --> 00:10:18,330
例えば入力 - 

229
00:10:18,330 --> 00:10:22,190
とみましょうこの上でこれを行う
こっち画面。

230
00:10:22,190 --> 00:10:26,180
私はハッシュを実装したい場合
この関数は、私が言うかもしれない

231
00:10:26,180 --> 00:10:27,410
このような何か。

232
00:10:27,410 --> 00:10:29,030
>> これは、int型を返すことが起こっている。

233
00:10:29,030 --> 00:10:33,600
これは、ハッシュと呼ばれるようになるだろう、そしてそれはだ
引数として受け入れるつもり

234
00:10:33,600 --> 00:10:38,920
文字列、または私達は、今ではより適切なことができます
と、char *を言う、我々はそれの電話するよ。

235
00:10:38,920 --> 00:10:43,840
そして、このすべての機能が、関係しています
最終的には、int型を返すことです。

236
00:10:43,840 --> 00:10:45,990
さて、どのようにそれがないことかもしれない
それほど明確ではない。

237
00:10:45,990 --> 00:10:49,510
私はせずにこれを実装するつもりです
今エラーチェックの形。

238
00:10:49,510 --> 00:10:55,740
私はただやみくもに戻る、と言うつもりです
Sブラケット0、マイナスであるものは何でも

239
00:10:55,740 --> 00:10:58,850
首都セミコロン、のは言わせて。

240
00:10:58,850 --> 00:10:59,960
>> 完全に壊れた。

241
00:10:59,960 --> 00:11:02,620
それは完璧ではないので、
1、sがnullの場合は何？

242
00:11:02,620 --> 00:11:04,000
悪いことが起こるとしている。

243
00:11:04,000 --> 00:11:07,940
二、これが何の最初の文字であれば
名前は、大文字ではないでしょうか？

244
00:11:07,940 --> 00:11:09,860
有効にするつもりはないことを
外にうまくどちら。

245
00:11:09,860 --> 00:11:11,970
それは小文字かもしれない
またはまったく手紙。

246
00:11:11,970 --> 00:11:15,520
ここに改善のためのだから全く部屋、
しかし、これは基本的な考え方です。

247
00:11:15,520 --> 00:11:19,010
>> 我々として口頭先週記述したもの
にアリスをマッピングするだけのプロセス

248
00:11:19,010 --> 00:11:23,360
1から0へとボブを表すことができる。
確かにも​​っとformulaically Cなど

249
00:11:23,360 --> 00:11:24,320
ここで機能します。

250
00:11:24,320 --> 00:11:28,630
として文字列を受け取り、ハッシュ再び呼び出さ
入力してから、何とか何かを

251
00:11:28,630 --> 00:11:31,020
出力を生成するために、その入力である。

252
00:11:31,020 --> 00:11:34,130
はなく、私たちのブラックボックスの説明とは異なり、
我々は長い間やっていること。

253
00:11:34,130 --> 00:11:36,550
私はこれがあるかもしれないのか分からない
ボンネットの下に取り組んでいます。

254
00:11:36,550 --> 00:11:40,120
>> 問題セット6、課題のいずれかの
何を決定するためのものです

255
00:11:40,120 --> 00:11:41,920
あなたのハッシュ関数は次のようになります？

256
00:11:41,920 --> 00:11:45,760
その黒の内側になるだろう何が
ボックス、およびおそらく、それができるでしょう

257
00:11:45,760 --> 00:11:50,380
これより少し面白い、と
エラーが間違いやすい

258
00:11:50,380 --> 00:11:53,180
この特定よりチェック
実装。

259
00:11:53,180 --> 00:11:54,580
>> しかし、問題は右、発生する可能性があります？

260
00:11:54,580 --> 00:11:57,760
我々は、このようなデータ構造を持っている場合
問題の一つ何1、

261
00:11:57,760 --> 00:12:01,600
あなたは挿入のように時間をかけてに実行することができます
に、より多くの名前

262
00:12:01,600 --> 00:12:02,880
ハッシュテーブル？

263
00:12:02,880 --> 00:12:04,630
あなたは正しい、衝突を得る？

264
00:12:04,630 --> 00:12:07,560
あなたはアリスとアロンを、何を持っている場合
名前が起こった2人

265
00:12:07,560 --> 00:12:08,190
で開始するには？

266
00:12:08,190 --> 00:12:11,660
それはどこに、質問を頼む
第二のような名前を入れて？

267
00:12:11,660 --> 00:12:15,050
>> さて、あなたは単純にそれを置くかもしれない
ボブが属する場所が、その後ボブです

268
00:12:15,050 --> 00:12:17,300
あなたがしようとする一種のねじ込み
次の彼の名前を挿入し、

269
00:12:17,300 --> 00:12:18,240
彼の余地はありません。

270
00:12:18,240 --> 00:12:21,400
だから、チャーリーはボブを置くかもしれない
そして、あなたは非常に迅速にこれを想像することができます

271
00:12:21,400 --> 00:12:23,020
混乱のビットに委譲。

272
00:12:23,020 --> 00:12:25,600
最後の直線何か、あなた
ただ全体を検索する必要が

273
00:12:25,600 --> 00:12:28,190
アリスやボブを探して
またはアーロンまたはチャーリー。

274
00:12:28,190 --> 00:12:33,230
>> だからではなく、我々だけで提案し、代わりに
直線的にオープンスペースのためのプロービング

275
00:12:33,230 --> 00:12:36,450
そして我々は、そこに名前をplopping
手の込んだ手法を提案した。

276
00:12:36,450 --> 00:12:41,740
とまだ実装ハッシュテーブル
インデックスの配列が、データ型の

277
00:12:41,740 --> 00:12:44,500
これらの指標は現在のポインタだった。

278
00:12:44,500 --> 00:12:47,360
何へのポインタ？

279
00:12:47,360 --> 00:12:48,730
リンクされたリストへのポインタ。

280
00:12:48,730 --> 00:12:53,330
>> リンクリストであることがあるためリコール
本当にただノードへのポインタ、および

281
00:12:53,330 --> 00:12:57,110
ノードは、次のフィールドを有し、そのノード
次のフィールドを有し、などが挙げられる。

282
00:12:57,110 --> 00:13:00,690
だから、今のこの配列を考えることができます
ハッシュテーブルとしての左側

283
00:13:00,690 --> 00:13:01,820
リンクリストにつながる。

284
00:13:01,820 --> 00:13:07,000
あなたが得る場合の利点は、
アリスとアーロンの衝突、

285
00:13:07,000 --> 00:13:09,300
あなたは、で何を行うのですか
第二のような人ですか？

286
00:13:09,300 --> 00:13:14,150
あなただけに彼を添付したり、彼女の
終わり、あるいは始まり

287
00:13:14,150 --> 00:13:15,490
リンクされたリストの。

288
00:13:15,490 --> 00:13:17,340
>> そして実際に、スルーだけ麺みましょう
そのただ秒間。

289
00:13:17,340 --> 00:13:18,640
どこが最も理にかなって？

290
00:13:18,640 --> 00:13:22,060
私はアリスを挿入して、彼女は見上げ終了した場合
最初の場所は、その後、私がしよう

291
00:13:22,060 --> 00:13:25,310
アーロンの名前を挿入し、そこ
明らかに衝突、私は置くべき

292
00:13:25,310 --> 00:13:27,400
彼を初めに
リンクリストの？

293
00:13:27,400 --> 00:13:30,944
その最初の場所でそれだ、
または末尾に？

294
00:13:30,944 --> 00:13:31,440
>> 読者：[聞こえない]。

295
00:13:31,440 --> 00:13:31,990
>> DAVIDマラン：OK。

296
00:13:31,990 --> 00:13:32,490
私が始めて聞いた。

297
00:13:32,490 --> 00:13:33,903
なぜ初めに？

298
00:13:33,903 --> 00:13:34,750
>> 読者：[聞こえない]。

299
00:13:34,750 --> 00:13:34,940
>> DAVIDマラン：OK。

300
00:13:34,940 --> 00:13:36,520
それは素晴らしいですので、アルファベット順です。

301
00:13:36,520 --> 00:13:37,330
それは良い財産だ。

302
00:13:37,330 --> 00:13:39,335
それは潜在的に私にいくつかの時間を節約できます。

303
00:13:39,335 --> 00:13:43,290
それは私がバイナリ検索をさせますが、私はありません
少なくとも、抜け出すことができるかもしれない

304
00:13:43,290 --> 00:13:47,340
私が気付いた場合、ループの、まあ、私は方法だ
過去あったアーロンはこれになるでしょう

305
00:13:47,340 --> 00:13:48,310
リンクされたリストを並べ替え。

306
00:13:48,310 --> 00:13:50,360
私が探して私の時間を無駄にする必要はありません
最後にすべての方法。

307
00:13:50,360 --> 00:13:51,530
だから合理的だ。

308
00:13:51,530 --> 00:13:54,710
なぜ他には、挿入したいかもしれません
で衝突名前

309
00:13:54,710 --> 00:13:56,660
リストの先頭に？

310
00:13:56,660 --> 00:13:57,397
何それ？

311
00:13:57,397 --> 00:13:58,680
>> 読者：[聞こえない]。

312
00:13:58,680 --> 00:14:00,820
>> DAVIDマラン：それは長い時間がかかることがあり
リストの最後に到達する。

313
00:14:00,820 --> 00:14:02,490
そして実際に、どんどん長く。

314
00:14:02,490 --> 00:14:04,920
あなたがそれを挿入して複数の名前
、長いことで始まる

315
00:14:04,920 --> 00:14:06,280
チェーンが取得する予定です。

316
00:14:06,280 --> 00:14:07,890
リンクされているより長いこと
リストが取得する予定です。

317
00:14:07,890 --> 00:14:09,420
だからあなたは本当にしている
あなたの時間を無駄に。

318
00:14:09,420 --> 00:14:14,070
たぶん、あなたは維持する方がいいでしょう
定数挿入時間、1のビッグO、

319
00:14:14,070 --> 00:14:18,470
常にで衝突名前を置くことによって、
リンクリストの先頭に、

320
00:14:18,470 --> 00:14:21,230
と同じくらい気にしない
ソートについて。

321
00:14:21,230 --> 00:14:22,600
>> 最良の答えは何ですか？

322
00:14:22,600 --> 00:14:23,320
それは不明だ。

323
00:14:23,320 --> 00:14:26,140
それは一種のは何に依存
ディストリビューションは、パターンとは何か、です。

324
00:14:26,140 --> 00:14:27,850
あなたが挿入されている名前の。

325
00:14:27,850 --> 00:14:29,430
それは必ずしもありません
明白な答え。

326
00:14:29,430 --> 00:14:33,100
しかし、ここには、再び、です
デザインの機会。

327
00:14:33,100 --> 00:14:37,220
>> だから我々は、その後、この事を見ている
本当に他の大きな機会です

328
00:14:37,220 --> 00:14:38,180
Pセット6。

329
00:14:38,180 --> 00:14:41,770
そして、あなたが既に持っていなければ、実現する
これらの両方にZamylaダイブ、ハッシュ

330
00:14:41,770 --> 00:14:43,260
テーブルとより詳細にしよう。

331
00:14:43,260 --> 00:14:45,630
とビデオチュートリアルです
Pセット仕様に包埋した。

332
00:14:45,630 --> 00:14:46,590
これはトライだった - 

333
00:14:46,590 --> 00:14:51,670
T-R-I-E。とについての興味深いものだっ
これは、実行中の時間だった

334
00:14:51,670 --> 00:14:59,510
マクスウェルのように、名前を検索する
最後の時間は、何のビッグOでしたか？

335
00:14:59,510 --> 00:15:01,040
何それ？

336
00:15:01,040 --> 00:15:01,920
>> 読者：文字数。

337
00:15:01,920 --> 00:15:02,550
>> DAVIDマラン：文字の数。

338
00:15:02,550 --> 00:15:03,210
私は二つのことを聞いた。

339
00:15:03,210 --> 00:15:04,630
手紙や時定数の数。

340
00:15:04,630 --> 00:15:05,540
それでは、最初に手放す。

341
00:15:05,540 --> 00:15:06,410
文字数。

342
00:15:06,410 --> 00:15:10,195
さて、このデータ構造は、リコールは、ある
木、家系、それぞれが好き

343
00:15:10,195 --> 00:15:12,860
そのノードが配列で構成されています。

344
00:15:12,860 --> 00:15:16,300
そして、それらの配列はへのポインタである
他のこのようなノード、または他の

345
00:15:16,300 --> 00:15:17,670
ツリー内の配列。

346
00:15:17,670 --> 00:15:22,890
>> 我々はその後、決定したいのであれば
マクスウェルがここにあるかどうか、私が行くかもしれない

347
00:15:22,890 --> 00:15:26,890
の最上部にある最初の配列に
木、いわゆる根の上部

348
00:15:26,890 --> 00:15:30,521
その後トライ、およびmポインタをたどる、
次に、ポインタ、xは、

349
00:15:30,521 --> 00:15:31,710
W、E、L、L。

350
00:15:31,710 --> 00:15:34,910
そして私は、いくつかの特殊記号が表示されたとき
三角形としてここに表記。

351
00:15:34,910 --> 00:15:38,480
コー​​ドでは、私たちはあなたのことを提案わかります
ただはい言って、ブールとして実装

352
00:15:38,480 --> 00:15:40,540
あるいはまったく、言葉はここに停止します。

353
00:15:40,540 --> 00:15:45,270
>> まあ、かつて我々は、M-A-X-W-E-L-Lに行ってきた、
多分、7のように感じている

354
00:15:45,270 --> 00:15:48,910
8我々はそれ過去1、8に行く場合
マクスウェルを見つけるための手順。

355
00:15:48,910 --> 00:15:53,050
またはみましょうそれK.呼び出すしかし最後のリコール
時間は、私ががあればと主張

356
00:15:53,050 --> 00:15:57,540
で現実的に最大長
40いくつかの奇数の文字、のような言葉、

357
00:15:57,540 --> 00:16:00,810
最大の長さを意味します
定数値。

358
00:16:00,810 --> 00:16:05,770
だから本当に、はい、それは技術的には大きなOだ
しかし、8または7、またはKの本当に大きなOの

359
00:16:05,770 --> 00:16:09,420
何上の有限キャップがあれば
Kは可能性があり、それは一定です。

360
00:16:09,420 --> 00:16:12,080
そしてそれはで1のビッグOです
一日の終わり。

361
00:16:12,080 --> 00:16:13,040
>> ではない現実の世界である。

362
00:16:13,040 --> 00:16:15,960
あなたが実際に見て起動しないとき
プログラムの実行など、あなたの時計。

363
00:16:15,960 --> 00:16:20,690
それは絶対に少しになるだろう
真に定数よりも遅く

364
00:16:20,690 --> 00:16:21,840
一歩との時間。

365
00:16:21,840 --> 00:16:25,540
それは、7または8つのステップになるだろう
それでも、それは、はるかに多くの方が良いでしょう

366
00:16:25,540 --> 00:16:30,080
そのn個のビッグOのようなアルゴリズムより
に何があるかのサイズに依存

367
00:16:30,080 --> 00:16:31,220
データ構造。

368
00:16:31,220 --> 00:16:34,970
>> ここで逆さまに気付く我々は挿入することができますです
これに万人以上の名前

369
00:16:34,970 --> 00:16:38,170
データ構造が、どのように多くの手順
それを見つけるために私たちを取るために起こっている

370
00:16:38,170 --> 00:16:40,480
その場合のマクスウェル？

371
00:16:40,480 --> 00:16:40,780
なし。

372
00:16:40,780 --> 00:16:41,820
彼が影響を受けないです。

373
00:16:41,820 --> 00:16:45,480
そして今日まで、私たちは見てきたとは思わない
データ構造の一例又は

374
00:16:45,480 --> 00:16:48,560
完全にあったアルゴリズム
外部の影響を受けない

375
00:16:48,560 --> 00:16:50,040
そのような行動。

376
00:16:50,040 --> 00:16:51,160
しかし、これは驚くべきことはできません。

377
00:16:51,160 --> 00:16:52,900
これが唯一の解決策になることができません
P-setの

378
00:16:52,900 --> 00:16:53,570
>> とそうではありません。

379
00:16:53,570 --> 00:16:55,980
これは、データとは限りません
あなたに引き寄せられるべき構造、

380
00:16:55,980 --> 00:16:58,220
トレードオフは、ハッシュテーブルのようなので。

381
00:16:58,220 --> 00:17:00,500
ここで支払う価格は何ですか？

382
00:17:00,500 --> 00:17:00,940
メモリ。

383
00:17:00,940 --> 00:17:02,890
私が意味する、これはひどいです
メモリの量。

384
00:17:02,890 --> 00:17:05,569
そして、あなたは非常にここでそれを見ることができないので、
この絵の作者

385
00:17:05,569 --> 00:17:09,420
明らかに、配列のすべてを切り捨て
私たちはのをたくさん見ていない

386
00:17:09,420 --> 00:17:12,700
BのとCとQのとYの
とZのこれらの配列である。

387
00:17:12,700 --> 00:17:13,630
しかし、彼らはそこにいる。

388
00:17:13,630 --> 00:17:17,660
>> これらの各ノードは、全体の配列です
いくつかの26バイト以上、それぞれの

389
00:17:17,660 --> 00:17:19,170
これは、文字を表します。

390
00:17:19,170 --> 00:17:22,920
我々がサポートできるように、我々の場合は27、
問題セットでアポストロフィ。

391
00:17:22,920 --> 00:17:27,030
、本当にこのデータ構造は、そう
本当に緻密で広い。

392
00:17:27,030 --> 00:17:30,880
そして、それだけでは減速終わるかもしれない
物事ダウン、または少なくともあなたの原価計算

393
00:17:30,880 --> 00:17:32,240
より多くのスペース。

394
00:17:32,240 --> 00:17:34,020
しかし、再び、私たちは描くことができます
ここで比較。

395
00:17:34,020 --> 00:17:39,190
>> しばらく前を思い出して、我々は多くを達成
選別でよりエキサイティングな実行時間

396
00:17:39,190 --> 00:17:42,880
私たちは、マージソートが、価格を使用するとき
我々は、マージのためにn個を達成nをログするために支払わ

397
00:17:42,880 --> 00:17:46,930
ソートは、我々が過ごすことが必要
もっと何リソース？

398
00:17:46,930 --> 00:17:47,690
より多くのスペース。

399
00:17:47,690 --> 00:17:50,530
私たちは、続発する配列を必要としてい
同じように、人にコピー

400
00:17:50,530 --> 00:17:51,620
私たちは、ステージ上でここにしました。

401
00:17:51,620 --> 00:17:55,880
だからもう一度、明確な勝者、
しかしちょうど主観的設計

402
00:17:55,880 --> 00:17:57,710
決定がなされる。

403
00:17:57,710 --> 00:17:58,060
>> わかりました。

404
00:17:58,060 --> 00:17:59,130
だから、どのようにこれはどうでしょうか？

405
00:17:59,130 --> 00:18:02,050
誰もがそのD-ホールを認識？

406
00:18:02,050 --> 00:18:02,440
OK。

407
00:18:02,440 --> 00:18:03,170
だから私たちの3人はやる。

408
00:18:03,170 --> 00:18:03,750
マザーハウス。

409
00:18:03,750 --> 00:18:05,070
だから、これはマザーのダイニングです。

410
00:18:05,070 --> 00:18:09,650
私はすべてのダイニングホールが持っている賭ける
このようなトレーのスタック。

411
00:18:09,650 --> 00:18:11,950
そして、これは実際に代表である
私たちが何かしたの

412
00:18:11,950 --> 00:18:13,050
明らかにすでに見。

413
00:18:13,050 --> 00:18:14,850
我々は文字通りスタックそれを呼んだ。

414
00:18:14,850 --> 00:18:18,970
あなたの観点とスタック、
コンピュータのメモリは、データがどこに行くかです。

415
00:18:18,970 --> 00:18:20,460
関数が呼び出されている。

416
00:18:20,460 --> 00:18:23,410
>> 例えば、物事の何種類が行く
に関して、スタック上

417
00:18:23,410 --> 00:18:27,420
我々は説明したメモリレイアウト
過去数週間で？

418
00:18:27,420 --> 00:18:28,736
何それ？

419
00:18:28,736 --> 00:18:29,670
>> 読者：関数の呼び出し。

420
00:18:29,670 --> 00:18:30,260
>> DAVIDマラン：ごめんなさい。

421
00:18:30,260 --> 00:18:31,210
>> 読者：関数の呼び出し。

422
00:18:31,210 --> 00:18:33,590
>> DAVIDマラン：関数の呼び出しが、
具体的には、それぞれの内部には何ですか

423
00:18:33,590 --> 00:18:35,340
これらのフレーム？

424
00:18:35,340 --> 00:18:37,220
物事の何種類？

425
00:18:37,220 --> 00:18:37,460
うん。

426
00:18:37,460 --> 00:18:38,500
ローカル変数だから。

427
00:18:38,500 --> 00:18:43,080
いつでも我々は、いくつかのローカルストレージを必要としてい
引数のような、またはint型I、またはint型

428
00:18:43,080 --> 00:18:45,940
一時、または任意のローカル
変数は、我々はしてきている

429
00:18:45,940 --> 00:18:47,210
スタックにそれを置く。

430
00:18:47,210 --> 00:18:49,610
そして、我々はそれを呼び出すためのスタック
そのレイヤーのアイデアの。

431
00:18:49,610 --> 00:18:52,940
現実と一致するだけの種類まで、
そのコンセプト。

432
00:18:52,940 --> 00:18:56,650
>> しかし、それはスタックにもできることが判明した
データ構造として見られ、

433
00:18:56,650 --> 00:19:00,110
配列の代わりに、代替
リンクされたリストに追加します。

434
00:19:00,110 --> 00:19:02,770
概念的にはもっと面白い
まだできること

435
00:19:02,770 --> 00:19:06,030
それらのいずれかを使用して実装
物事は、それは別の種類だ

436
00:19:06,030 --> 00:19:09,140
データ構造は、実際には、支援
2つだけの操作。

437
00:19:09,140 --> 00:19:11,000
しかし、あなたは手の込んだ上で追加することができます
これら以外の機能。

438
00:19:11,000 --> 00:19:12,180
しかし、これらは基本です - 

439
00:19:12,180 --> 00:19:13,510
pushとpop。

440
00:19:13,510 --> 00:19:19,240
>> とスタックとの考えは、私であればということです
アネンバーグの有無にかかわらず、ここにある

441
00:19:19,240 --> 00:19:22,880
、隣からトレイを知る
その上に9番を持つ。

442
00:19:22,880 --> 00:19:23,870
だからint型。

443
00:19:23,870 --> 00:19:26,990
そして、私はデータの上にこれをプッシュする
現在は空である構造。

444
00:19:26,990 --> 00:19:28,790
これをスタックの底を考えてみましょう。

445
00:19:28,790 --> 00:19:33,150
私は上にこの9番を押します
積み重ね、今ではすぐそこです。

446
00:19:33,150 --> 00:19:36,040
>> しかし、スタックに関する興味深い
私は今プッシュする場合ということです

447
00:19:36,040 --> 00:19:40,210
他の値、17のように、と私はプッシュ
このスタックには、私はするつもりです

448
00:19:40,210 --> 00:19:43,290
唯一の直感的なものは、私はちょうど行くよ
右のそれをどこに置くかを私たち人間

449
00:19:43,290 --> 00:19:45,180
上部に、それを置くように傾斜される。

450
00:19:45,180 --> 00:19:48,850
しかし、今は面白いものだ
、どのように私は9で入手できますか？

451
00:19:48,850 --> 00:19:50,670
あなたが知っている、私はいくつかの努力なしにしないでください。

452
00:19:50,670 --> 00:19:54,070
>> それでは、約興​​味深い
スタックは、その仕様です

453
00:19:54,070 --> 00:19:56,330
それは、LIFOのデータ構造です。

454
00:19:56,330 --> 00:19:59,680
記述の愚かな方法
後入れ先出し。

455
00:19:59,680 --> 00:20:03,280
だから、最後の番号で
この時点で17だった。

456
00:20:03,280 --> 00:20:07,540
だから私は何かをオフにポップアップ表示したい場合
スタックは、わずか17とすることができる。

457
00:20:07,540 --> 00:20:11,890
だから必須の順序があり
ここでの操作は、最後の項目

458
00:20:11,890 --> 00:20:14,260
には、最初のうち一つでなければならない。

459
00:20:14,260 --> 00:20:16,440
したがって頭字語、LIFO。

460
00:20:16,440 --> 00:20:19,160
>> では、なぜこれが役に立つかもしれません？

461
00:20:19,160 --> 00:20:22,690
あなたが思いの彼らのコンテキストは
このようなデータ構造をしたいですか？

462
00:20:22,690 --> 00:20:24,810
まあ、それは確かに役立っている
コンピュータの内部。

463
00:20:24,810 --> 00:20:29,050
だから、オペレーティングシステムは明らかにこれを使用
スタックのデータ構造の一種。

464
00:20:29,050 --> 00:20:32,800
また、同じ考えを見ることができます
Webページに来るとき。

465
00:20:32,800 --> 00:20:35,890
だから、今週と来週以降、
あなたがウェブを実装を開始として

466
00:20:35,890 --> 00:20:39,490
HTMLと呼ばれる言語のページ、次のことができます
実際にデータ構造を使うように

467
00:20:39,490 --> 00:20:42,690
このページかどうかを判断する
正しくフォーマットされています。

468
00:20:42,690 --> 00:20:47,170
我々は、表示されますので、すべてのWebページがフォロー
階層の並べ替え、インデント

469
00:20:47,170 --> 00:20:52,030
それは、一日の終わりには、となる
ボンネットの下にツリー構造。

470
00:20:52,030 --> 00:20:53,620
少しだけでその上で非常に多くの。

471
00:20:53,620 --> 00:20:56,560
>> しかし、今のところ、のはのために提案してみましょう
どのように我々は取り掛かることができた瞬間、

472
00:20:56,560 --> 00:20:58,830
スタックは何ですか？表す

473
00:20:58,830 --> 00:21:03,370
我々が実装している私が提案してみましょう
このようなコードを使用してスタック。

474
00:21:03,370 --> 00:21:07,990
だからスタックは、それの内側を持っているために起こっている
二つのことは、配列と呼ばれるトレイ、

475
00:21:07,990 --> 00:21:09,510
ただデモと一致しています。

476
00:21:09,510 --> 00:21:12,660
そして、その配列内の各項目
int型になるだろう。

477
00:21:12,660 --> 00:21:14,740
そして容量はおそらく何ですか？

478
00:21:14,740 --> 00:21:18,796
私は書かれていませんでしたので、
ここに完全な定義。

479
00:21:18,796 --> 00:21:21,535
>> それはおそらく最高だ
配列のサイズ。

480
00:21:21,535 --> 00:21:25,150
そしてそれはおそらくシャープとして宣言された
いくつかのファイルの先頭に定義

481
00:21:25,150 --> 00:21:28,450
によって暗示として一定の種類
単なる大文字。

482
00:21:28,450 --> 00:21:32,250
だからどこかで容量が定義されています
可能な最大サイズとして。

483
00:21:32,250 --> 00:21:35,590
一方、内部のデータ構造の
スタックとして知られているそこに意志

484
00:21:35,590 --> 00:21:38,630
ただ知ら整数でなければ
単にサイズなど。

485
00:21:38,630 --> 00:21:43,400
>> 私は今、これを表現するためにあったのであれば
画像で、のは、そのこのことを仮定してみよう

486
00:21:43,400 --> 00:21:48,070
全体のブラックボックスは私のスタックを表します。

487
00:21:48,070 --> 00:21:50,070
その中は、2つの変数である。

488
00:21:50,070 --> 00:21:54,780
だから私は描くつもりです
サイズとして最初のもの。

489
00:21:54,780 --> 00:21:57,420
そして、私は行くよ一秒
配列として描画する。

490
00:21:57,420 --> 00:22:01,060
>> しかし、単に、物事が整然と維持する
通常、私のような配列を引く

491
00:22:01,060 --> 00:22:04,910
これが、それは一種の素敵なの
我々は現実と一致している場合、または

492
00:22:04,910 --> 00:22:06,230
メンタルモデルと一致している。

493
00:22:06,230 --> 00:22:12,880
だから私は、代わりに配列を描画してみましょう
垂直に、それはただ、再び、

494
00:22:12,880 --> 00:22:13,840
芸術家の演出。

495
00:22:13,840 --> 00:22:16,610
本当に何がそれは問題ではありません
ボンネットの下にある。

496
00:22:16,610 --> 00:22:20,350
そして我々は、デフォルトでは、ことを言うよ
容量は、次の3つになるだろう。

497
00:22:20,350 --> 00:22:23,480
だから、これは位置0、これになります
場所1、これになります

498
00:22:23,480 --> 00:22:25,740
位置2になります。

499
00:22:25,740 --> 00:22:29,330
>> 私はストレスボールで買収した場合、だろう
誰かが出てくると実行したい

500
00:22:29,330 --> 00:22:30,870
ちょっとここでボード？

501
00:22:30,870 --> 00:22:31,960
OK、最初にあなたの手を見た。

502
00:22:31,960 --> 00:22:33,950
までさあ。

503
00:22:33,950 --> 00:22:36,500
わかりました。

504
00:22:36,500 --> 00:22:38,760
だから、私はそれがスティーブンであると考えています。

505
00:22:38,760 --> 00:22:40,035
までさあ。

506
00:22:40,035 --> 00:22:40,770
わかりました。

507
00:22:40,770 --> 00:22:46,760
>> しかし、今我々は初期に巻き戻したとし
世界の状態はどこ

508
00:22:46,760 --> 00:22:52,180
単にスタックを宣言し、それがだた
容量は3であることになるだろう。

509
00:22:52,180 --> 00:22:54,470
しかし、サイズがまだ決定されていない。

510
00:22:54,470 --> 00:22:56,100
トレイは、まだ決定されていない。

511
00:22:56,100 --> 00:22:57,300
最初の質問のカップルだから。

512
00:22:57,300 --> 00:23:01,310
することができますので、私はあなたにマイクを与えてみましょう
これでより積極的に参加する。

513
00:23:01,310 --> 00:23:05,190
>> だからサイズの内部は、この瞬間に何ですか
時間内にすべての私が行っている場合です。

514
00:23:05,190 --> 00:23:09,340
とスタックを宣言
1行のコード？

515
00:23:09,340 --> 00:23:10,100
>> STEVEN：あまりない。

516
00:23:10,100 --> 00:23:12,080
>> DAVIDマラン：OK、あまりない。

517
00:23:12,080 --> 00:23:14,410
我々は、内部の大きさの何を知っていますか
我々は内部の何を知っています

518
00:23:14,410 --> 00:23:16,330
この配列のここに？

519
00:23:16,330 --> 00:23:18,630
>> STEVEN：ちょうどランダムコード、右？

520
00:23:18,630 --> 00:23:20,220
ただ - 

521
00:23:20,220 --> 00:23:23,230
>> DAVIDマラン：ええ、私はするつもりです
そのコードを呼び出すが、ランダム - 

522
00:23:23,230 --> 00:23:23,820
>> STEVEN：物事。

523
00:23:23,820 --> 00:23:28,290
>> DAVIDマラン：ランダムのようなもの

524
00:23:28,290 --> 00:23:28,870
>> STEVEN：ビット。

525
00:23:28,870 --> 00:23:29,530
>> DAVIDマラン：ビット、右？

526
00:23:29,530 --> 00:23:31,190
だからゴミ値、右？

527
00:23:31,190 --> 00:23:33,470
だから、0と1の順列。

528
00:23:33,470 --> 00:23:35,920
以前の用法の残骸
このメモリの。

529
00:23:35,920 --> 00:23:38,150
私たちは本当に何の値かわからない
ですので、我々は一般的に、それらを描く

530
00:23:38,150 --> 00:23:38,930
疑問符として。

531
00:23:38,930 --> 00:23:41,990
>> 我々はおそらくいるので最初のもの
ここでやりたいつもり - 

532
00:23:41,990 --> 00:23:46,630
と私は内部でこのフィールドを与えてみましょう
トレー - そこに名前の。

533
00:23:46,630 --> 00:23:49,540
我々は、おそらく何を初期化する必要があります
サイズは私たちがしたい場合に

534
00:23:49,540 --> 00:23:51,040
このスタックを使用して起動する？

535
00:23:51,040 --> 00:23:53,070
>> STEVEN：トレイはサブ3です。

536
00:23:53,070 --> 00:23:53,910
>> DAVIDマラン：だから、OK。

537
00:23:53,910 --> 00:23:56,710
明確にするために、容量が宣言されています
他の場所で3として。

538
00:23:56,710 --> 00:23:58,570
そして、それは私が使用したものだ
配列を割り当てます。

539
00:23:58,570 --> 00:24:03,535
サイズを参照するために起こっているどのように多くの
トレイは、スタック上に現在ある。

540
00:24:03,535 --> 00:24:03,880
>> STEVEN：ゼロ。

541
00:24:03,880 --> 00:24:04,460
>> DAVIDマラン：だから、それはゼロでなければなりません。

542
00:24:04,460 --> 00:24:07,760
だから先に行くと、任意の指で、
サイズがゼロを描きます。

543
00:24:07,760 --> 00:24:08,440
わかりました。

544
00:24:08,440 --> 00:24:10,920
だから今、この内何
ここで、我々は知らない。

545
00:24:10,920 --> 00:24:12,160
これらは実際には単なるゴミ値です。

546
00:24:12,160 --> 00:24:14,800
だから我々は、疑問符を描くこともできますが、
今のボードを清潔に保つましょう

547
00:24:14,800 --> 00:24:16,300
それは問題ではありませんので、
そこに何が。

548
00:24:16,300 --> 00:24:19,130
私たちは、配列を初期化する必要はありません
何に、我々はそれを知っていれば理由

549
00:24:19,130 --> 00:24:23,100
スタックのサイズがゼロで、まあ、我々
には何を見てはいけません

550
00:24:23,100 --> 00:24:25,590
とにかく、この配列
この時点での時間である。

551
00:24:25,590 --> 00:24:29,970
>> だから今、私がプッシュすると仮定
スタックに9番。

552
00:24:29,970 --> 00:24:33,750
どのように我々は、データ構造を更新する必要があります
このブラックボックスの内側？

553
00:24:33,750 --> 00:24:35,540
値は変更する必要がありますか？

554
00:24:35,540 --> 00:24:36,200
>> STEVEN：内 - 

555
00:24:36,200 --> 00:24:37,400
サイズは？

556
00:24:37,400 --> 00:24:37,650
>> DAVIDマラン：OK。

557
00:24:37,650 --> 00:24:38,770
サイズは何になるでしょうか？

558
00:24:38,770 --> 00:24:39,580
>> STEVEN：サイズは1になります。

559
00:24:39,580 --> 00:24:39,870
>> DAVIDマラン：OK。

560
00:24:39,870 --> 00:24:41,110
だからサイズは1になるはず。

561
00:24:41,110 --> 00:24:42,540
だから、いくつかの方法でこれを行うことができます。

562
00:24:42,540 --> 00:24:46,920
あなたの今、私はあなたを与えることを許可しなさい
指が消しゴムです。

563
00:24:46,920 --> 00:24:47,260
わかりました。

564
00:24:47,260 --> 00:24:49,960
それから、今あなたの指がブラシです。

565
00:24:49,960 --> 00:24:50,330
わかりました。

566
00:24:50,330 --> 00:24:52,820
そして今、他に何が、変更する必要があり
明らかに、データ構造内？

567
00:24:52,820 --> 00:24:57,060
>> STEVEN：我々からのつもり
9〜ボトムアップ。

568
00:24:57,060 --> 00:24:57,760
>> DAVIDマラン：9。

569
00:24:57,760 --> 00:24:58,420
OK、グッド。

570
00:24:58,420 --> 00:25:01,550
だから、まだATのかは重要ではありません
場所、1つまたは2つの彼らはだから

571
00:25:01,550 --> 00:25:04,520
ゴミ値が、我々は気にしないはず
サイズがあるのでそこを見て

572
00:25:04,520 --> 00:25:07,540
を告げて、その最初の要素のみ
実際には正当なものである。

573
00:25:07,540 --> 00:25:10,400
だから今私は、リストの上に17を押してください。

574
00:25:10,400 --> 00:25:11,830
何がこの写真はどうなりますか？

575
00:25:11,830 --> 00:25:14,720
>> STEVEN：だからサイズが2に行く予定です​​。

576
00:25:14,720 --> 00:25:15,300
>> DAVIDマラン：OK。

577
00:25:15,300 --> 00:25:16,070
あなたは消しゴムだ - 

578
00:25:16,070 --> 00:25:16,810
おっと。

579
00:25:16,810 --> 00:25:18,026
あなたは消しゴムです。

580
00:25:18,026 --> 00:25:18,840
>> STEVEN：消しゴム。

581
00:25:18,840 --> 00:25:19,720
>> DAVIDマラン：あなたがブラシです。

582
00:25:19,720 --> 00:25:20,560
>> STEVEN：ブラシ。

583
00:25:20,560 --> 00:25:20,920
>> DAVIDマラン：OK。

584
00:25:20,920 --> 00:25:21,600
そして、ほかに何か？

585
00:25:21,600 --> 00:25:22,600
>> その後、そして、私たち - ：STEVEN

586
00:25:22,600 --> 00:25:22,915
>> DAVIDマラン：我々は17を押した。

587
00:25:22,915 --> 00:25:24,760
>> STEVEN：私達は、一番上に17を貼る - 

588
00:25:24,760 --> 00:25:25,710
>> DAVIDマラン：OK、良い。

589
00:25:25,710 --> 00:25:27,040
>> STEVEN： - それをドロップダウン。

590
00:25:27,040 --> 00:25:27,530
>> DAVIDマラン：すべての権利。

591
00:25:27,530 --> 00:25:27,940
それは簡単になってきている。

592
00:25:27,940 --> 00:25:29,300
私はあなたにこの時間を支援するつもりはない。

593
00:25:29,300 --> 00:25:30,510
22を押してください。

594
00:25:30,510 --> 00:25:31,720
>> STEVEN：完了。

595
00:25:31,720 --> 00:25:34,870
消しゴムになって。

596
00:25:34,870 --> 00:25:37,340
私はブラシになっています。

597
00:25:37,340 --> 00:25:39,340
そして私は22を入れています。

598
00:25:39,340 --> 00:25:40,100
>> DAVIDマラン：22。

599
00:25:40,100 --> 00:25:40,620
優秀。

600
00:25:40,620 --> 00:25:41,380
したがって、1つより多くの時間。

601
00:25:41,380 --> 00:25:44,280
私は今プッシュするつもりだ
スタック26へ。

602
00:25:44,280 --> 00:25:46,350
>> STEVEN：ああ。

603
00:25:46,350 --> 00:25:50,278
おやっああ。

604
00:25:50,278 --> 00:25:52,520
あなたは本当に油断私を捉えました。

605
00:25:52,520 --> 00:25:53,703
>> DAVIDマラン：あなたがしませんでした
これが来て見？

606
00:25:53,703 --> 00:25:55,930
>> STEVEN：私はこれが来て見ていない。

607
00:25:55,930 --> 00:25:58,756
我々は、再初期容量だろうか？

608
00:25:58,756 --> 00:25:59,790
>> DAVIDマラン：良い質問です。

609
00:25:59,790 --> 00:26:02,360
だから我々は一種の自分自身を描いてきた
ここのコーナーである。

610
00:26:02,360 --> 00:26:06,740
本当にスティーブンのための良い外にはありません
我々はこの配列を割り当てられたので

611
00:26:06,740 --> 00:26:09,130
静的なので、内側に、話すこと
データ構造である。

612
00:26:09,130 --> 00:26:12,170
そして、私たちは本質的にハードコーディングされてきた
それはサイズが3であることが。

613
00:26:12,170 --> 00:26:14,170
だから、私たちは本当にそれを再割り当てすることはできません。

614
00:26:14,170 --> 00:26:20,020
>> 我々は、我々は、に戻って行きましたができれば
トレイはそのポインタに再定義

615
00:26:20,020 --> 00:26:22,300
我々はその後に手メモリにmallocを使用しています。

616
00:26:22,300 --> 00:26:25,050
なぜなら我々はからメモリを得た場合
malloc関数経由ヒープ、我々

617
00:26:25,050 --> 00:26:26,430
それを解放することができます。

618
00:26:26,430 --> 00:26:29,630
しかし、それを解放する前に、我々は可能性
、メモリの大きなチャンクを再割り当て

619
00:26:29,630 --> 00:26:31,330
ポインタを更新する、などが挙げられる。

620
00:26:31,330 --> 00:26:33,500
しかし、今のところ、これは本当にある
我々ができる最善。

621
00:26:33,500 --> 00:26:36,360
pushとpopはおそらく行っている
いくつかのエラーを通知する必要があります。

622
00:26:36,360 --> 00:26:40,270
>> だから例えば、我々の実装
プッシュしたブールを返すことができ

623
00:26:40,270 --> 00:26:42,390
以前に真の、本当の、真の戻った。

624
00:26:42,390 --> 00:26:48,390
しかし四時間、それが持っているために起こっている
例えば、falseが返されます。

625
00:26:48,390 --> 00:26:48,540
わかりました。

626
00:26:48,540 --> 00:26:49,540
非常によくやった。

627
00:26:49,540 --> 00:26:50,060
おめでとうございます。

628
00:26:50,060 --> 00:26:52,160
あなたが今日のあなたのストレスボールを獲得した。

629
00:26:52,160 --> 00:26:53,110
>> [拍手]

630
00:26:53,110 --> 00:26:54,382
>> STEVEN：ありがとうございます。

631
00:26:54,382 --> 00:26:55,680
>> DAVIDマラン：ありがとうございます。

632
00:26:55,680 --> 00:26:59,740
[OK]を、ので、これはあまりないと思われる
一歩前進の、右？

633
00:26:59,740 --> 00:27:01,410
我々は、このデータ構造を説明した。

634
00:27:01,410 --> 00:27:02,320
それは右、説得されている？

635
00:27:02,320 --> 00:27:03,200
それのようなオペレーティングシステム。

636
00:27:03,200 --> 00:27:06,360
明らかにウェブは、これを利用することができ
まだ他のアプリケーション。

637
00:27:06,360 --> 00:27:10,870
しかし、私たちがしていることを愚かな制限
背中週一種の2つの限界に

638
00:27:10,870 --> 00:27:12,880
どこに私たちは、サイズの配列を修正しました。

639
00:27:12,880 --> 00:27:15,010
>> そこらのカップルは確かに存在する
の方法は、我々はこの問題を解決することができます。

640
00:27:15,010 --> 00:27:18,750
我々は動的配列を割り当てることができ
私がきたようで難しい、それをコーディングしない

641
00:27:18,750 --> 00:27:22,600
ここで行われますが、代わりに再宣言
これは、同じように、明確にすること

642
00:27:22,600 --> 00:27:23,830
このような何か。

643
00:27:23,830 --> 00:27:29,040
int型*トレイは、決めていない
まだ容量に。

644
00:27:29,040 --> 00:27:35,460
しかし、私は他の場所でスタックを宣言するとき
私のコードでは、私はその後、malloc関数を呼び出すことができ

645
00:27:35,460 --> 00:27:38,250
の塊のアドレスを取得
メモリ、Iは割り当てることができます

646
00:27:38,250 --> 00:27:39,980
トレイにそのアドレス。

647
00:27:39,980 --> 00:27:43,340
>> そして、それだけの塊だから
メモリ、Iは、正方形継続して使用することができ

648
00:27:43,340 --> 00:27:45,450
通常の方法でブラケット表記。

649
00:27:45,450 --> 00:27:49,020
再び、この種の存在だから
配列の機能的に同等と

650
00:27:49,020 --> 00:27:50,820
来るのメモリチャンク
malloc関数から戻って。

651
00:27:50,820 --> 00:27:53,090
我々は、他のようなものを扱うことができます
ポインタ演算を使用するか、

652
00:27:53,090 --> 00:27:54,440
角括弧表記。

653
00:27:54,440 --> 00:27:55,660
だから一つのアプローチです。

654
00:27:55,660 --> 00:28:00,120
>> しかし、どのように他の我々は、これを実装するかもしれません
同じデータ構造、潜在的に？

655
00:28:00,120 --> 00:28:00,280
右？

656
00:28:00,280 --> 00:28:04,530
私たちはただ、これを解決したように私は感じる
一週間前のような問題。

657
00:28:04,530 --> 00:28:08,860
この問題を解決するには、何だったの
スティーブンに走っていること？

658
00:28:08,860 --> 00:28:10,370
だからリンクリスト、右側。

659
00:28:10,370 --> 00:28:13,410
>> 問題は、我々は塗装していることである場合
割り当てることで、自分自身のコーナーへ

660
00:28:13,410 --> 00:28:17,580
私たちはその事前あまりに少ないメモリで
その後は、まあ、何とか対処しなければならない

661
00:28:17,580 --> 00:28:19,880
理由だけでは避けられない
完全に出す？

662
00:28:19,880 --> 00:28:26,170
理由だけであることがトレイを宣言しない
ノード、エルゴリンクリストへのポインタ

663
00:28:26,170 --> 00:28:30,740
その後、単純に新しいノードを割り当てる
スティーブンがフィットするのに必要なたび

664
00:28:30,740 --> 00:28:32,400
データ構造に番号。

665
00:28:32,400 --> 00:28:34,200
>> だから絵は変更する必要があります。

666
00:28:34,200 --> 00:28:38,220
それはきれいにしてようであることを行っていない
3 intの配列だけのような単純な。

667
00:28:38,220 --> 00:28:42,970
今では体へのポインタになるだろう
構造体、及びその構造体はに起こっている

668
00:28:42,970 --> 00:28:44,830
intおよび次のポインタを持っている。

669
00:28:44,830 --> 00:28:47,670
それは、そのポインタを介してつながるために起こっている
別のこのような構造体への

670
00:28:47,670 --> 00:28:48,600
別のそのような構造体。

671
00:28:48,600 --> 00:28:50,560
だから絵は実際だろ
ビットメシエを得る。

672
00:28:50,560 --> 00:28:52,950
そして、我々の矢印は抱き合わせていると思います
一緒にすべてのもの。

673
00:28:52,950 --> 00:28:55,280
>> しかし、それはので、右、大丈夫です
我々はこれを行う方法を見てきました。

674
00:28:55,280 --> 00:28:58,180
そして、一度は快適得る
リンクされたようなものを実装する

675
00:28:58,180 --> 00:29:01,450
あなたがあれば行う必要があるでしょうリスト、
でハッシュテーブルを実装することを選択

676
00:29:01,450 --> 00:29:05,120
P-6のセット用に別のチェーン、次のことができます
ビルディングブロックとして、またはそれを使用する

677
00:29:05,120 --> 00:29:08,870
成分、またはスクラッチで話す、
手順、あなたは、あなたを置くことを何か

678
00:29:08,870 --> 00:29:12,560
あなた自身のパズルのピースを作成しました
あなたはその後再利用できる。

679
00:29:12,560 --> 00:29:17,090
だからトレードオフですが、潜在的な解決策
我々は実際に前に見たこと。

680
00:29:17,090 --> 00:29:20,560
>> だからかなり頻繁に、このごとを参照してください
Appleはリリース1年か2年

681
00:29:20,560 --> 00:29:23,060
何か新しいこと、およびすべての狂った人
アップルの外線まで

682
00:29:23,060 --> 00:29:27,050
彼らの限界を買うために保存
ハードウェア上でアップグレードします。

683
00:29:27,050 --> 00:29:30,420
ので、私は、それはOKですが、これを言う
私はそれらの人々の一人です。

684
00:29:30,420 --> 00:29:35,140
だから、どのようなデータ構造の
この現実を表すのでしょうか？

685
00:29:35,140 --> 00:29:36,980
>> まあ、のはそれをキュー、ラインと呼ぶことにしましょう​​。

686
00:29:36,980 --> 00:29:40,270
だから英国は、それが一般的に呼ぶだろう
キューがとにかくので、それはいい名前だ。

687
00:29:40,270 --> 00:29:44,960
そして、そのキュー二つの操作
我々はエンキューを呼ぶことにしますサポートしなければならない

688
00:29:44,960 --> 00:29:48,900
操作とデキュー操作、
に類似している

689
00:29:48,900 --> 00:29:50,120
pushとpopする精神。

690
00:29:50,120 --> 00:29:54,060
それだけで別のものだ
大会、私たちがこれらを呼んでいる。

691
00:29:54,060 --> 00:29:57,680
しかし、何かをキューに追加することを意味します
またはデータ構造に挿入する。

692
00:29:57,680 --> 00:29:59,570
デキューするには、それを削除することを意味します。

693
00:29:59,570 --> 00:30:05,170
しかし、スタックはLIFOのデータだったのに対し、
構造は、キューは、最初にある

694
00:30:05,170 --> 00:30:06,740
データ構造先入れ先出し。

695
00:30:06,740 --> 00:30:10,050
>> あなたは、行の最初の人であれば、
あなたを取得する最初の人になります

696
00:30:10,050 --> 00:30:12,420
ラインの外にして、新しいデバイスを購入する。

697
00:30:12,420 --> 00:30:18,070
これらの人々がどのように動揺だろう想像してみて
Appleは代わりにスタックを使用した場合、用

698
00:30:18,070 --> 00:30:21,250
ピッキングを実装するインスタンス、
あなたの新しいおもちゃのアップ。

699
00:30:21,250 --> 00:30:24,310
だからキューは確かに、意味をなさない、と
我々はあらゆる種類のものと考えることができ

700
00:30:24,310 --> 00:30:27,480
キューのアプリケーション、おそらく、、
あなたは公平にしたい場合は特に。

701
00:30:27,480 --> 00:30:30,040
それでは、どのように我々は、これらを実装するかもしれません
データ構造として？

702
00:30:30,040 --> 00:30:33,680
>> まあ、私は、我々は可能性があることを提案
このようにそれを行う必要があります。

703
00:30:33,680 --> 00:30:35,225
だから私は今、数字を持っているつもりです。

704
00:30:35,225 --> 00:30:38,190
だから我々は、それが簡単でな​​いでおこう
必ずしもトレイの観点で話す。

705
00:30:38,190 --> 00:30:40,220
の人々が得ているだけの数字。

706
00:30:40,220 --> 00:30:43,760
容量は再び、に起こっている、修正
にすることができ、人々の総数は

707
00:30:43,760 --> 00:30:46,900
このライン、3として、または
他のどのような値。

708
00:30:46,900 --> 00:30:50,760
>> しかし、私は追跡する必要があることを提案する
の大きさだけでなく、

709
00:30:50,760 --> 00:30:52,370
キューは、その中にどのように多くのものです。

710
00:30:52,370 --> 00:30:56,310
だからサイズが現在のサイズ、容量は
最大サイズです。

711
00:30:56,310 --> 00:30:58,540
もう一度、命名
慣例により。

712
00:30:58,540 --> 00:31:03,680
なぜ私は内側に追加のint型が必要なのでしょうか
中の人を追跡するためのキューの

713
00:31:03,680 --> 00:31:05,365
ラインの前？

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
なぜ私は、この場合にこれを行う必要がありますか？

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> さて、どのようにこの絵です
変更するつもり？

718
00:31:16,190 --> 00:31:19,280
私はおそらく最も再利用することができます
この写真の。

719
00:31:19,280 --> 00:31:21,480
私が先に行くと、ここで何を消去しましょう​​。

720
00:31:21,480 --> 00:31:24,580
我々はこれを少しをしてあげる
ここでは別の名前まで。

721
00:31:24,580 --> 00:31:28,930
17を取り除くましょう、みましょう取り除く
9に、3を取り除くみましょう。

722
00:31:28,930 --> 00:31:30,410
そしてもうひとつ追加してみましょう。

723
00:31:30,410 --> 00:31:34,710
私はを追跡する必要があることを提案
ただ、リストの前、

724
00:31:34,710 --> 00:31:35,570
同様にint型になるだろう。

725
00:31:35,570 --> 00:31:36,550
そして、我々はそれをシンプルに保つつもりです。

726
00:31:36,550 --> 00:31:37,740
今のところリンクリストはありません。

727
00:31:37,740 --> 00:31:40,900
>> 我々は我々が行っていることを認めるよ
この制限に上げる。

728
00:31:40,900 --> 00:31:43,720
しかし、私は見て何をしたいですか
今回が起こる？

729
00:31:43,720 --> 00:31:47,240
だから私は先に行くと、最初の仮定
人が並んで登場し、

730
00:31:47,240 --> 00:31:48,560
それは9番だ。

731
00:31:48,560 --> 00:31:49,680
私たちは、ストレスボールを持っている。

732
00:31:49,680 --> 00:31:51,330
私は、言う、2〜3人を盗むことはできますか？

733
00:31:51,330 --> 00:31:52,690
一つ、二つ、三つ？

734
00:31:52,690 --> 00:31:53,120
までさあ。

735
00:31:53,120 --> 00:31:56,022
正面から右、なぜなら
我々はこの1つは迅速作ってあげる。

736
00:31:56,022 --> 00:31:59,415
>> あなたのそれぞれは今であることを行っている
アップルのライン内のファンの少年。

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
あなたは、Appleのハードウェアを受信されることはありません
これでもの終わりに。

739
00:32:06,210 --> 00:32:06,500
わかりました。

740
00:32:06,500 --> 00:32:09,430
だから、あなたは、9番だね
番号17、番号22。

741
00:32:09,430 --> 00:32:12,130
これらは以下のように、任意の数字
学生IDやその他もろもろ。

742
00:32:12,130 --> 00:32:14,550
そして、ちょうどその瞬間に、始めましょう
物事の追加を開始します。

743
00:32:14,550 --> 00:32:16,000
そして、私はここに、この時間をボードを実行することになるでしょう。

744
00:32:16,000 --> 00:32:19,570
>> したがって、この場合には、私が初期化しました
なるようにフロント - 

745
00:32:19,570 --> 00:32:22,380
私は実際には本当に気にしないのか
サイズがゼロであるため、正面である。

746
00:32:22,380 --> 00:32:24,480
だから、これは同様にだけかもしれない
疑問符である。

747
00:32:24,480 --> 00:32:26,170
これらはすべてクエスチョンマークです。

748
00:32:26,170 --> 00:32:29,880
だから今我々は、実際にいくつかを見ることから始めましょう
人々は店で並んで。

749
00:32:29,880 --> 00:32:33,320
>> 9番であれば、あなたは最初のものだ
そこに午前5時、先に行くと並んで、

750
00:32:33,320 --> 00:32:34,210
または前の夜。

751
00:32:34,210 --> 00:32:34,580
OK。

752
00:32:34,580 --> 00:32:35,940
だから今9はここにある。

753
00:32:35,940 --> 00:32:37,940
そう9は、リストの先頭にある。

754
00:32:37,940 --> 00:32:41,440
だから私は先に行くと更新するつもりです
この電流データのサイズ

755
00:32:41,440 --> 00:32:44,740
もう0にしないように構造、
しかし、1とする。

756
00:32:44,740 --> 00:32:47,630
私はで9を置くつもりです
リストの先頭。

757
00:32:47,630 --> 00:32:51,020
私が先に行くと、画面を切り替えてみましょう
ので、ここで私たちの過去を見ることができます。

758
00:32:51,020 --> 00:32:53,220
>> そして今、私は何をしたいですか
前面に置くか？

759
00:32:53,220 --> 00:32:56,240
私が追跡するつもりだ
今キューの先頭

760
00:32:56,240 --> 00:32:58,570
位置0にあります。

761
00:32:58,570 --> 00:33:00,510
次に何が起ころうとしているので？

762
00:33:00,510 --> 00:33:03,000
まあ、私はエンキュー今仮定
17同様に。

763
00:33:03,000 --> 00:33:04,510
だから、そこに並んでホップ。

764
00:33:04,510 --> 00:33:07,060
そして再び、ドアのようなものに
店はここになるだろう。

765
00:33:07,060 --> 00:33:08,700
だから今、私は17を追加しました。

766
00:33:08,700 --> 00:33:10,810
そして、これらの人はブロックしているにもかかわらず
OKの画面、、

767
00:33:10,810 --> 00:33:12,300
我々はここでそれを見ることができるので。

768
00:33:12,300 --> 00:33:12,910
申し訳ありません。

769
00:33:12,910 --> 00:33:13,810
>> 聴衆：我々は、移動することができます - 

770
00:33:13,810 --> 00:33:14,660
>> DAVIDマラン：いいえ、大丈夫です。

771
00:33:14,660 --> 00:33:16,000
それはそこまで巨大だ。

772
00:33:16,000 --> 00:33:18,580
だから17は現在、キューの中にある。

773
00:33:18,580 --> 00:33:21,332
私はどのを更新する必要があります
しかし今のフィールド？

774
00:33:21,332 --> 00:33:23,210
OK、確かにサイズ。

775
00:33:23,210 --> 00:33:26,430
そして、どのようにフロントはどうでしょうか？

776
00:33:26,430 --> 00:33:27,040
いや、OK。

777
00:33:27,040 --> 00:33:30,200
フロントには、変更すべきではありませんので、
スタックとは異なり、我々

778
00:33:30,200 --> 00:33:31,370
公平性を維持したい。

779
00:33:31,370 --> 00:33:35,150
9が最初に来たのであれば、我々は9が欲しい
行の最初にすること

780
00:33:35,150 --> 00:33:36,420
とストアに。

781
00:33:36,420 --> 00:33:37,220
>> 実際には、その見てみましょう。

782
00:33:37,220 --> 00:33:42,235
我々は22を挿入する前に、してみましょう
先に行くとデキュー9。

783
00:33:42,235 --> 00:33:42,970
あなたの名前は何です再び？

784
00:33:42,970 --> 00:33:43,680
>> 読者：ジェイク。

785
00:33:43,680 --> 00:33:45,440
>> DAVIDマラン：ジェイクが起こっている
今デキューする。

786
00:33:45,440 --> 00:33:48,050
だから、店に歩いてもらう。

787
00:33:48,050 --> 00:33:49,880
とふり、そのストア
あそこです。

788
00:33:49,880 --> 00:33:51,970
だから今必要なもの -  DIT-DIT-DIT！

789
00:33:51,970 --> 00:33:53,400
何が今起こる必要ですか？

790
00:33:53,400 --> 00:33:54,490
デザイン決定。

791
00:33:54,490 --> 00:33:56,825
だから悪くない本能が、 - 
あなたの名前は何ですか再び？

792
00:33:56,825 --> 00:33:57,090
>> 読者：デビッド。

793
00:33:57,090 --> 00:33:57,500
>> DAVIDマラン：デビッド。

794
00:33:57,500 --> 00:33:58,810
ダビデは何をしたのですか？

795
00:33:58,810 --> 00:34:02,590
彼は固定のデータをソートしようとしていた
彼の場所から構造および移動

796
00:34:02,590 --> 00:34:04,100
ジェイクの元の場所に。

797
00:34:04,100 --> 00:34:06,740
そして、我々は喜んでいる場合、それは大丈夫です
としてそれを受け入れるように

798
00:34:06,740 --> 00:34:08,199
実装の詳細。

799
00:34:08,199 --> 00:34:11,100
しかし、最初のデータを更新してみましょう
我々はそれを行う前に、構造。

800
00:34:11,100 --> 00:34:14,139
私はすべてのアイデアを好きではないだから
人々がこの行にシフト。

801
00:34:14,139 --> 00:34:17,360
>> ダビデはそれをしない場合、それは大したことない
一歩ですが、再び、に戻ると思います

802
00:34:17,360 --> 00:34:20,360
我々は上の8人のボランティアを持っていたとき
ステージと我々は挿入のようやった

803
00:34:20,360 --> 00:34:22,600
我々はスタートしなければならなかったソート、
周りの人を動かす。

804
00:34:22,600 --> 00:34:23,790
それは右、高価だ？

805
00:34:23,790 --> 00:34:28,330
ビッグOについて私はうんざりなること
n個のnの大きなOが再び乗。

806
00:34:28,330 --> 00:34:30,650
それはのように感じていない
理想的な結果。

807
00:34:30,650 --> 00:34:32,080
>> だから、これを更新してみましょう。

808
00:34:32,080 --> 00:34:35,120
だからキューのサイズ
もはや2ではありません。

809
00:34:35,120 --> 00:34:37,090
これは、今では単に1だ。

810
00:34:37,090 --> 00:34:40,360
しかし、私は今、何かを更新することができます
私は前に更新されませんでした、

811
00:34:40,360 --> 00:34:41,130
リストの先頭。

812
00:34:41,130 --> 00:34:45,420
私はちょうどその場所1である、と言うことができる？

813
00:34:45,420 --> 00:34:49,770
だから今我々は、ここにゴミ値を持つ
ゴミここで値、でデイビッド

814
00:34:49,770 --> 00:34:51,469
このゴミの真ん中。

815
00:34:51,469 --> 00:34:54,980
しかし、データ構造
まだそのままである。

816
00:34:54,980 --> 00:34:58,540
>> 実際に、私もする必要はありません
ジェイクの元数を変更

817
00:34:58,540 --> 00:35:00,460
9、気遣うので。

818
00:35:00,460 --> 00:35:04,470
私は今で十分な情報を持っている
私はそこの一人で知っているサイズ

819
00:35:04,470 --> 00:35:05,030
このキュー。

820
00:35:05,030 --> 00:35:08,340
そして私は知っているその人
場所1、ではない0にあります。

821
00:35:08,340 --> 00:35:09,760
私は数えていないよ。

822
00:35:09,760 --> 00:35:11,300
1だから、同様に。

823
00:35:11,300 --> 00:35:13,410
だから、データ構造はまだOKです。

824
00:35:13,410 --> 00:35:14,330
>> さて、次に何が起こるか？

825
00:35:14,330 --> 00:35:15,010
レッツエンキュー - 

826
00:35:15,010 --> 00:35:15,370
お名前は何ですか？

827
00:35:15,370 --> 00:35:16,160
>> 読者：キャレン。

828
00:35:16,160 --> 00:35:16,580
>> DAVIDマラン：キャレン。

829
00:35:16,580 --> 00:35:20,770
キャレンをエンキューましょう、と
22はキューになりました。

830
00:35:20,770 --> 00:35:22,300
だから今、ここで変更しているか？

831
00:35:22,300 --> 00:35:24,380
フロントに行くされていません
明らかに、変更します。

832
00:35:24,380 --> 00:35:27,160
サイズは再び2と変更する予定です。

833
00:35:27,160 --> 00:35:31,590
22はここで終わる、9は、依然として存在している
それが効果的だ

834
00:35:31,590 --> 00:35:32,600
今ゴミ値。

835
00:35:32,600 --> 00:35:35,910
それはちょうどジェイクの過去の名残だ。

836
00:35:35,910 --> 00:35:39,200
>> だから今何が起こるか
私はデイヴィッドをデキュー？

837
00:35:39,200 --> 00:35:41,560
One最後の操作、デキューデビッド。

838
00:35:41,560 --> 00:35:46,070
我々はシフトする可能性がありますが、私はレッツを提案
できるだけ少ない作業として行う。

839
00:35:46,070 --> 00:35:50,280
今私のデータ構造が行く
2から1へのサイズのバック。

840
00:35:50,280 --> 00:35:53,730
しかし、キューの先頭
今、2になります。

841
00:35:53,730 --> 00:35:56,640
私は、これらの番号を変更する必要はありません
ただまだ、彼らはだから

842
00:35:56,640 --> 00:35:58,230
ただゴミ値。

843
00:35:58,230 --> 00:35:59,720
>> しかし、今は何が起こる？

844
00:35:59,720 --> 00:36:03,280
私は自分自身、26をエンキューと仮定？

845
00:36:03,280 --> 00:36:05,890
私はこっちに属するような気がします。

846
00:36:05,890 --> 00:36:06,890
だから私は、キューに入れられているんだ。

847
00:36:06,890 --> 00:36:08,760
だから私は種類のここに属しています。

848
00:36:08,760 --> 00:36:11,300
そして、あなたは全くないにもかかわらず、
ステージ上で視覚的にこれを感謝し、

849
00:36:11,300 --> 00:36:15,075
我々は部屋がたくさんあるので、私がすべき
ここに立っていることではない、なぜですか？

850
00:36:15,075 --> 00:36:16,290
>> 読者：あなたが範囲外です。

851
00:36:16,290 --> 00:36:16,370
>> DAVIDマラン：右。

852
00:36:16,370 --> 00:36:16,940
私は範囲外です。

853
00:36:16,940 --> 00:36:19,330
私は越えてインデックスを作成しました
この配列の境界。

854
00:36:19,330 --> 00:36:23,420
私は実際のいずれかでなければなりません
3つの可能な場所。

855
00:36:23,420 --> 00:36:25,150
さて、どこへ行くのが最も自然なのですか？

856
00:36:25,150 --> 00:36:27,760
私は我々が活用提案
週に1つのトリック。

857
00:36:27,760 --> 00:36:30,150
Mod演算子、パーセンテージ。

858
00:36:30,150 --> 00:36:36,850
私は技術的に立っているので、
場所3、しかし、私は、3 MOD容量を行う

859
00:36:36,850 --> 00:36:40,250
その3、パーセント記号、3  - 

860
00:36:40,250 --> 00:36:40,970
容量の3。

861
00:36:40,970 --> 00:36:41,720
何それ？

862
00:36:41,720 --> 00:36:43,700
残りは時何
あなたは3点で3を分割？

863
00:36:43,700 --> 00:36:44,070
0。

864
00:36:44,070 --> 00:36:48,140
>> だから私を置くことジェイクは、であった
これは実際には良いです。

865
00:36:48,140 --> 00:36:50,370
だから今は実装
このことのために起こっている

866
00:36:50,370 --> 00:36:51,250
頭痛のビットである。

867
00:36:51,250 --> 00:36:53,740
それは本当に1行だけだ
頭痛のコードの。

868
00:36:53,740 --> 00:36:56,580
しかし、少なくとも今ではゴミはあり
ここで値が、そこの2

869
00:36:56,580 --> 00:36:57,910
ここで正当な整数。

870
00:36:57,910 --> 00:37:04,160
そして、私は今、私たちが行っていると主張
まさに我々がいる限り何をすべきか

871
00:37:04,160 --> 00:37:08,600
私たちは何のジェイクを変更
値が26であることだった。

872
00:37:08,600 --> 00:37:12,110
>> 私たちは、今はまだ十分な情報を持っている
整合性を維持するために

873
00:37:12,110 --> 00:37:13,060
このデータ構造である。

874
00:37:13,060 --> 00:37:17,160
時々我々はまだ運のようなものの外出
合計四つ以上を挿入する

875
00:37:17,160 --> 00:37:20,740
要素が、私は、少なくともかなり作ることができます
この定数の効率的な使用

876
00:37:20,740 --> 00:37:21,740
実際の時間、。

877
00:37:21,740 --> 00:37:27,150
私がシフトを心配する必要はありません
みんな、Davidの傾きがあったように。

878
00:37:27,150 --> 00:37:30,816
>> スタック上のご質問、
またはこのキュー？

879
00:37:30,816 --> 00:37:32,184
>> 読者：理由です
あなたが知っているので、あなたのサイズを必要とする

880
00:37:32,184 --> 00:37:34,010
人を持っているどこに？

881
00:37:34,010 --> 00:37:34,770
>> DAVIDマラン：その通り。

882
00:37:34,770 --> 00:37:38,230
Iは、配列の大きさを知る必要がある
私は正確にどのように知っている必要がありますので、

883
00:37:38,230 --> 00:37:41,940
これらの値の多くは合法的であり、
どこに置くかと私は見つけることができる

884
00:37:41,940 --> 00:37:42,800
次の人。

885
00:37:42,800 --> 00:37:43,300
まさに。

886
00:37:43,300 --> 00:37:44,580
サイズは - 

887
00:37:44,580 --> 00:37:46,360
実際に、我々はまだ、これを更新しませんでした。

888
00:37:46,360 --> 00:37:48,380
私は26で自分自身を追加しました。

889
00:37:48,380 --> 00:37:51,760
サイズが、現在ではない1であるが、2。

890
00:37:51,760 --> 00:37:57,780
だから今、これは確かに私が見つけることができます
リストの先頭には、これは0ではない、ではない

891
00:37:57,780 --> 00:37:59,250
1ですが、2である。

892
00:37:59,250 --> 00:38:01,665
リストの先頭
22番は確かです。

893
00:38:01,665 --> 00:38:05,120
彼は最初に来たので、彼は必要があるため
私の前にストアに許可され、

894
00:38:05,120 --> 00:38:08,780
もかかわらず、視覚的に私が立っている
店に近い。

895
00:38:08,780 --> 00:38:09,220
>> 大丈夫？

896
00:38:09,220 --> 00:38:12,410
これらの人のために拍手
そして我々は彼らをそこから出てもらおう。

897
00:38:12,410 --> 00:38:17,090
>> [拍手]

898
00:38:17,090 --> 00:38:18,150
>> DAVIDマラン：私はさせことができる
あなたは、トレイを保つ。

899
00:38:18,150 --> 00:38:20,760
我々は何が起こるか見ることができました
あなたはしたいが、そうでないかもしれない。

900
00:38:20,760 --> 00:38:21,590
わかりました。

901
00:38:21,590 --> 00:38:25,380
だから今はそれが私たちに何を残すのでしょうか？

902
00:38:25,380 --> 00:38:28,900
まあ、私があることを提案してみましょう
私たちができるいくつかの他のデータ構造

903
00:38:28,900 --> 00:38:33,810
意志たちのツールキットへの追加を開始
として実際には非常に、非常に関連性がある

904
00:38:33,810 --> 00:38:35,270
我々は、Webのものに飛び込む。

905
00:38:35,270 --> 00:38:38,150
どの再び、接続のいくつかの種類を持っている
の形で木に

906
00:38:38,150 --> 00:38:40,550
DOMと呼ばれるものは、文書
オブジェクトモデル。

907
00:38:40,550 --> 00:38:42,370
しかし、我々はより多くを見ることができます
そのずっと前に。

908
00:38:42,370 --> 00:38:46,260
>> 私は我々というdefinitionally提案してみましょう
今、あなたは知っているかもしれないものとして、木を呼び出す

909
00:38:46,260 --> 00:38:48,820
家系、あなたのより多くの
でいくつかの祖先を持っている

910
00:38:48,820 --> 00:38:49,790
木の根。

911
00:38:49,790 --> 00:38:54,480
で家父長または女家長
ツリーの最上部。

912
00:38:54,480 --> 00:38:56,700
配偶者なしで、このような場合である。

913
00:38:56,700 --> 00:39:00,940
しかし、我々は今我々が呼ぶよ何を持っている
ハングノードである子どもたち、

914
00:39:00,940 --> 00:39:05,480
左の子、または右の子オフ、
矢印は、ここに示されている。

915
00:39:05,480 --> 00:39:10,490
>> 換言すれば、ツリーデータ構造で
コンピュータで、ツリーはゼロを持って

916
00:39:10,490 --> 00:39:11,480
以上のノード。

917
00:39:11,480 --> 00:39:13,500
それは少なくとも1つのノードがある場合は、
それは、ルートと呼ばれています。

918
00:39:13,500 --> 00:39:15,700
これは、視覚的にいる事だ
私たちは、一番上に描画します。

919
00:39:15,700 --> 00:39:20,280
そのノードは、他のノードのように、することができます
、0,1、または2つ、または3つを有する

920
00:39:20,280 --> 00:39:23,600
またはしかし多くの子どもたち
データ構造をサポートしています。

921
00:39:23,600 --> 00:39:29,150
この場合、ルートは、記憶
1の値は、2人の子供、2および3を有する

922
00:39:29,150 --> 00:39:33,020
従って我々は一般的に2左を呼び出す
子供と3右の子。

923
00:39:33,020 --> 00:39:36,940
>> そして、我々は5、6に取り掛かるとき、および
7、6は真ん中の子と呼ばれるかもしれない。

924
00:39:36,940 --> 00:39:38,940
あなたには、四人の子供を持っている場合、
それは混乱を取得します。

925
00:39:38,940 --> 00:39:42,260
だから私たちはそのようなものを使用して停止
ショートカットの口頭。

926
00:39:42,260 --> 00:39:44,580
しかし、それは本当に家系だ。

927
00:39:44,580 --> 00:39:48,880
そしてここで葉はそのノードである
自身が子を持たない。

928
00:39:48,880 --> 00:39:52,540
彼らは、ツリーの最下部をオフにハングアップ。

929
00:39:52,540 --> 00:39:56,940
>> では、どのようにその木を実装するかもしれません
最大限にただ二人の子供を持っている？

930
00:39:56,940 --> 00:39:58,410
我々はそれをバイナリツリーと呼ぶことにします。

931
00:39:58,410 --> 00:40:00,960
同性には再びこのでは、2つの意味
バイナリとのような場合、。

932
00:40:00,960 --> 00:40:04,830
そしてそれは、ゼロ、1つを持つことができます
または最大限に二人の子供。

933
00:40:04,830 --> 00:40:08,650
>> 私たちは、ノードを実装することを提案します
int型のnは、その構造のために、

934
00:40:08,650 --> 00:40:11,910
し、2つのポインタと呼ばれる1つの
左、人は右と呼ばれる。

935
00:40:11,910 --> 00:40:14,830
しかし、それらは単にいいです
任意の規則。

936
00:40:14,830 --> 00:40:18,170
そして、あなたは、今では場合は特に素敵な何だ
の種類はと概念的に苦戦

937
00:40:18,170 --> 00:40:21,300
再帰、またはそうでないと思った
何を本当に解決策、

938
00:40:21,300 --> 00:40:23,120
特にあなたができれば
メモリが不足する。

939
00:40:23,120 --> 00:40:26,600
今、我々はデータの話をしていることを
許す構造とアルゴリズム

940
00:40:26,600 --> 00:40:31,030
それらを横断し、操作するために私達に、
再帰に戻ってくることが判明

941
00:40:31,030 --> 00:40:34,240
はるかに説得力のある
美しい方法ではない場合。

942
00:40:34,240 --> 00:40:38,670
>> だから私は提案し、これは実装です
検索機能の。

943
00:40:38,670 --> 00:40:39,870
2つの入力を与え - 

944
00:40:39,870 --> 00:40:41,570
そのブラックボックスと考える。

945
00:40:41,570 --> 00:40:46,560
二つの入力、N、int、および与えられた
木へのポインタへのポインタ

946
00:40:46,560 --> 00:40:50,020
ノード、または実際にツリーのルート、I
この関数が返すことができるという主張

947
00:40:50,020 --> 00:40:53,530
trueまたはfalse、そのnの値
このツリーの内部です。

948
00:40:53,530 --> 00:40:55,210
>> このブラックボックスの中には何ですか？

949
00:40:55,210 --> 00:40:57,440
さて、4枝。

950
00:40:57,440 --> 00:40:58,385
最初だけチェックします。

951
00:40:58,385 --> 00:41:00,490
木がnullの場合は、ただfalseを返す。

952
00:41:00,490 --> 00:41:04,580
どのノードがない場合、nは、ありません
ない番号がありません、ただfalseを返す。

953
00:41:04,580 --> 00:41:12,330
しかしもし、nは、あなたが探している値
例えば、ツリー矢印n個未満であり、かつ

954
00:41:12,330 --> 00:41:15,180
ただ明確にするためには、ときに何を意味するのでしょう
私は、ツリーと矢印を書く

955
00:41:15,180 --> 00:41:18,150
表記法、N？

956
00:41:18,150 --> 00:41:18,690
まさに。

957
00:41:18,690 --> 00:41:21,970
これは、間接参照を意味する
ツリーと呼ばれるポインタ。

958
00:41:21,970 --> 00:41:26,750
そこに移動し、その中に入る
ノードとそのフィールドがnと呼ばれ得る。

959
00:41:26,750 --> 00:41:30,810
そしてあった実際のNを比較
それに対する検索に渡され。

960
00:41:30,810 --> 00:41:35,390
>> nはn値未満であれば
ツリーノード自体は、まあ、

961
00:41:35,390 --> 00:41:36,720
それは何を意味するのでしょうか？

962
00:41:36,720 --> 00:41:40,690
それは一目見ただけで何の意味もありません。

963
00:41:40,690 --> 00:41:40,900
右？

964
00:41:40,900 --> 00:41:45,560
あなたの配列を持っているときと同じように
値は、バイナリを適用するかもしれません

965
00:41:45,560 --> 00:41:48,290
分割の形などの検索
と征服。

966
00:41:48,290 --> 00:41:51,790
しかし、どのような仮定すると、我々は確認する必要がありました
すべてで動作するバイナリ検索用

967
00:41:51,790 --> 00:41:54,510
電話帳でと
前述の例？

968
00:41:54,510 --> 00:41:55,530
>> どのようにソートする。

969
00:41:55,530 --> 00:41:59,490
それでは、木の定義を洗練させて
ここですることができるだけでツリー、すべきではない

970
00:41:59,490 --> 00:42:00,880
子供任意の数を有する。

971
00:42:00,880 --> 00:42:04,700
だけではなく、バイナリツリー、そのことができます
0,1、または最大2を有する。

972
00:42:04,700 --> 00:42:09,700
しかし、二分探索木として、またはBST、
これは、ただ言う空想の方法です

973
00:42:09,700 --> 00:42:15,430
バイナリツリーようにすべてのノードの
左の子は、存在する場合、ある

974
00:42:15,430 --> 00:42:16,830
ノード未満。

975
00:42:16,830 --> 00:42:20,170
そして、すべてのノードの右の子、
存在する場合は、大きい

976
00:42:20,170 --> 00:42:21,740
ノード自体より。

977
00:42:21,740 --> 00:42:25,200
>> だから、他の言葉で、あなたが描画した場合
ツリー外に、数字のすべてがある

978
00:42:25,200 --> 00:42:30,620
このように慎重にバランスのとれたようであれば
あなたが行くことができ、ルートとして33〜55を持って

979
00:42:30,620 --> 00:42:33,090
その左には55未満だから。

980
00:42:33,090 --> 00:42:36,430
77は、その右に行くことができます
それは、55よりも大きいです。

981
00:42:36,430 --> 00:42:40,750
しかし、今、同じ定義を気付く
それは、口頭で再帰的な定義だ

982
00:42:40,750 --> 00:42:42,600
33を申請しています。

983
00:42:42,600 --> 00:42:47,610
33の左の子は、それ未満でなければなりません
と33の右の子、44は、でなければなりません

984
00:42:47,610 --> 00:42:48,580
それよりも大きい。

985
00:42:48,580 --> 00:42:51,670
>> だから、これは二分探索木であり、
私の少しを使用して、提案する

986
00:42:51,670 --> 00:42:53,910
再帰は、我々は今、n個を見つけることができます。

987
00:42:53,910 --> 00:42:59,160
nは、の値がnよりも小さいのであれば
現在のノードが、私は行くつもりです

988
00:42:59,160 --> 00:43:04,090
先とパント、いわば、とだけ
答えはである何を返す

989
00:43:04,090 --> 00:43:08,470
nに探し
木の左の子。

990
00:43:08,470 --> 00:43:11,370
再び注目し、この機能だけ
ノード星、期待してい

991
00:43:11,370 --> 00:43:12,780
ノードへのポインタ。

992
00:43:12,780 --> 00:43:17,360
だからきっと私はちょうどツリーを行うことができます
つながる矢印左、

993
00:43:17,360 --> 00:43:18,400
私を別のノードに。

994
00:43:18,400 --> 00:43:19,480
しかし、そのノードは何ですか？

995
00:43:19,480 --> 00:43:22,820
>> さて、この宣言によると、
左がその結果だけでは、単にポインタである

996
00:43:22,820 --> 00:43:27,090
私は検索機能に渡していることを意味し
別のポインタ、すなわち

997
00:43:27,090 --> 00:43:30,750
表す1つの
私の左の子のツリー。

998
00:43:30,750 --> 00:43:36,040
したがって、この場合には、ポインタがあれば、33〜
これがあれば、一方で我々のサンプルの入力です

999
00:43:36,040 --> 00:43:40,740
nは値よりnにおける大きい
ツリー内の現在のノードが、その後私はよ

1000
00:43:40,740 --> 00:43:43,370
他に先に行くとパントに行く
方向とだけ言って、私はしないでください

1001
00:43:43,370 --> 00:43:47,280
この値は、nはツリー内にあるかどうかを知り、
私はそれがあれば、それは私のダウンであることを知っている

1002
00:43:47,280 --> 00:43:49,090
右側のブランチは、いわば。

1003
00:43:49,090 --> 00:43:53,120
だから、私は検索再帰的に呼び出してみましょう
再びNを渡しますが、渡して

1004
00:43:53,120 --> 00:43:54,580
私の右の子へのポインタ。

1005
00:43:54,580 --> 00:44:00,020
>> 言い換えれば、私は現在いたら55時
と私は99を探しています、私が知っている99

1006
00:44:00,020 --> 00:44:04,270
私は引き裂いたので、ちょうど同じように、55より大きい
電話帳週間前に、私たち

1007
00:44:04,270 --> 00:44:07,140
同様に私たちは、まっすぐ飛んでいった
右ここに行くつもり。

1008
00:44:07,140 --> 00:44:11,960
それは私の右側にいた場合、私は知らない
子供は、それはないが、77はありますが、

1009
00:44:11,960 --> 00:44:13,210
私はそれがその方向に知っている。

1010
00:44:13,210 --> 00:44:18,770
だから、私は右の子の検索を呼び出し、
77、検索から把握させ

1011
00:44:18,770 --> 00:44:24,950
そこにあれば、この任意で99
例は実際にある。

1012
00:44:24,950 --> 00:44:26,900
>> そうでなければ、最後のケースは何ですか？

1013
00:44:26,900 --> 00:44:28,620
木がnullの場合は一例です。

1014
00:44:28,620 --> 00:44:31,890
nは、現在のノードの未満である場合
値は、別のケースである。

1015
00:44:31,890 --> 00:44:35,120
nは電流よりも大きい場合
ノードの値は、第三のケースです。

1016
00:44:35,120 --> 00:44:38,250
4番目と最後のケースは何ですか？

1017
00:44:38,250 --> 00:44:39,480
私は、我々は右、例出ていると思う？

1018
00:44:39,480 --> 00:44:44,690
nがであること、それでなければならない
私は上だと現在のノード。

1019
00:44:44,690 --> 00:44:49,640
>> 私はこの時点で55を探しているのであれば
の物語の中で、そのブランチ

1020
00:44:49,640 --> 00:44:51,780
ツリーには、trueを返します。

1021
00:44:51,780 --> 00:44:55,380
それでは、ここで興味深いのは、我々ということです
実際、過去数週間、我々種類は違って

1022
00:44:55,380 --> 00:44:56,740
のは、2つのベースケースを持っている。

1023
00:44:56,740 --> 00:44:58,300
そして、彼らはする必要はありません
上部にあるすべてのこと。

1024
00:44:58,300 --> 00:45:01,390
上部には、ベースケースであるため場合
木がnullの場合、何の関係もありません。

1025
00:45:01,390 --> 00:45:03,410
ただ、ハードコードを返す
値false。

1026
00:45:03,410 --> 00:45:07,400
>> ボトム支店の一種である
我々がチェックした場合、それによってデフォルト、

1027
00:45:07,400 --> 00:45:11,550
、我々はそれがあるべき場合はnullをチェックした
左が、それはすべきではない、我々はしました

1028
00:45:11,550 --> 00:45:14,640
それは右であるべき場合にチェックされますが、それ
すべきではない、明らかにそれがなければならない

1029
00:45:14,640 --> 00:45:15,870
右のどこに私たちはいます。

1030
00:45:15,870 --> 00:45:16,780
それは、ベースケースです。

1031
00:45:16,780 --> 00:45:19,920
ので、2つの再帰的な場合があり
途中でそこに挟まれた。

1032
00:45:19,920 --> 00:45:21,630
しかし、私は書かれている可能性が
任意の順序でこれ。

1033
00:45:21,630 --> 00:45:24,520
私はそれが一種の自然な感じと思った
最初のエラーの可能性をチェックする、

1034
00:45:24,520 --> 00:45:28,340
その後、その後、右確認、左確認
ノードにいることを前提としてい

1035
00:45:28,340 --> 00:45:30,630
あなたが実際に探している。

1036
00:45:30,630 --> 00:45:36,240
>> では、なぜこれが役に立つかもしれません？

1037
00:45:36,240 --> 00:45:37,910
だから、判明 - 

1038
00:45:37,910 --> 00:45:42,110
と私はティーザーにジャンプしてみましょう
ここではウェブにそのだ。

1039
00:45:42,110 --> 00:45:44,920
我々はしない使用を開始するつもりだ
プログラミング最初は言語が、

1040
00:45:44,920 --> 00:45:46,030
マークアップ言語。

1041
00:45:46,030 --> 00:45:48,740
の一つであるマークアップ言語
プログラミングと基本的に変わるところは

1042
00:45:48,740 --> 00:45:51,715
言葉、それはあなたに与えるものではありません
論理的に自分を表現する能力。

1043
00:45:51,715 --> 00:45:55,070
それだけであなたの能力を与える
構造的に自分を表現。

1044
00:45:55,070 --> 00:45:57,960
>> どこに何を入れたいか
ページ上の、ウェブページ？

1045
00:45:57,960 --> 00:45:59,200
あなたはそれを作るために何色をしたいですか？

1046
00:45:59,200 --> 00:46:00,950
どのようなフォントサイズは​​、それを作りたいのですか？

1047
00:46:00,950 --> 00:46:02,970
何の言葉は実際にあなたを行う
Webページにしたいですか？

1048
00:46:02,970 --> 00:46:04,060
だからマークアップ言語です。

1049
00:46:04,060 --> 00:46:07,690
しかし、その後、我々は非常に迅速に紹介しま​​す
本格的なされるJavaScript、

1050
00:46:07,690 --> 00:46:08,560
プログラミング言語。

1051
00:46:08,560 --> 00:46:12,530
構文的に外観が非常に似て
Cに、それはいくつかを持っているよ

1052
00:46:12,530 --> 00:46:15,200
素敵な、より強力な、より多くの
ユーザーフレンドリーな機能。

1053
00:46:15,200 --> 00:46:18,050
>> そして、これで不満の一つ
学期のポイントは、我々がよということです

1054
00:46:18,050 --> 00:46:22,065
すぐにはるかに少ないでスペルチェックを実装
他の言語を使用したコードの行

1055
00:46:22,065 --> 00:46:25,580
C自体は可能ですが、理由のより
我々はすぐに理解できるでしょう。

1056
00:46:25,580 --> 00:46:27,750
これは最初のそのようなWebページになります。

1057
00:46:27,750 --> 00:46:30,120
それは、完全にがっかりされます
私たちが作る最初のもの。

1058
00:46:30,120 --> 00:46:31,400
これは単に世界こんにちは、と言うだろう。

1059
00:46:31,400 --> 00:46:34,010
しかし、あなたはそれを見たことがない場合
前に、これはHTMLです、

1060
00:46:34,010 --> 00:46:35,670
ハイパーテキストマークアップ言語。

1061
00:46:35,670 --> 00:46:39,310
>> あなたは、ある特定のメニューオプションに行く場合
上の任意のWebページ上のほとんどすべてのブラウザ、

1062
00:46:39,310 --> 00:46:43,160
インターネットは、あなたは、HTMLを見ることができます
一部の人々はに書き込んだ

1063
00:46:43,160 --> 00:46:44,400
そのWebページを作成します。

1064
00:46:44,400 --> 00:46:47,850
そして、それはおそらくとして見ていません
短いまたはこれと同じくらいきちんとした。

1065
00:46:47,850 --> 00:46:51,400
しかし、それは、これらのパターンに従います
開いた括弧とスラッシュと

1066
00:46:51,400 --> 00:46:53,660
文字と潜在的数字。

1067
00:46:53,660 --> 00:46:56,770
>> 私はあなたにティーザーを与えるだろうと思って
あなたが行うことができるでしょう何の

1068
00:46:56,770 --> 00:46:57,950
CS50を取った後。

1069
00:46:57,950 --> 00:47:02,620
私はcs.harvard.edu /ロブに行こう、
私たち自身のロブボーデンのホームページ。

1070
00:47:02,620 --> 00:47:06,080
彼は私たちのためにこれを作りました。

1071
00:47:06,080 --> 00:47:07,490
だから、すぐにそれを行うことができるでしょう。

1072
00:47:07,490 --> 00:47:10,660
そしてまた、あなたは何を聞いた
今朝 - 

1073
00:47:10,660 --> 00:47:12,480
あなたは今朝聞いた - 

1074
00:47:12,480 --> 00:47:13,780
>> [ハムスターダンスミュージック]

1075
00:47:13,780 --> 00:47:15,702
>>  -  you'llは、これを作ることができる。

1076
00:47:15,702 --> 00:47:16,790
それは水曜日に私たちを待っています。

1077
00:47:16,790 --> 00:47:17,791
私たちは、あなたが表示されます。

1078
00:47:17,791 --> 00:47:22,950
>> [ハムスターダンスミュージック]

1079
00:47:22,950 --> 00:47:24,300
DAVIDマラン：次のCS50で - 

1080
00:47:24,300 --> 00:47:31,670