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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1：すべてが正しいので、我々は戻ってきた。

3
00:00:13,120 --> 00:00:14,480
CS50へようこそ。

4
00:00:14,480 --> 00:00:16,510
これは、週7の終わりです。

5
00:00:16,510 --> 00:00:20,200
だから、最後の時間を思い出す、私たちは開始
もう少し洗練された見

6
00:00:20,200 --> 00:00:21,100
データ構造。

7
00:00:21,100 --> 00:00:25,110
今までなので、すべての私たちは本当にいた
私達の処分で、この配列であった。

8
00:00:25,110 --> 00:00:29,340
>> しかし、我々は配列を破棄しないように前に
確かにすべてのことを面白い、、それ

9
00:00:29,340 --> 00:00:33,570
実際にいくつかのは何か、である
この単純なデータのプラス

10
00:00:33,570 --> 00:00:34,560
これまでの構造？

11
00:00:34,560 --> 00:00:36,110
それが得意とは何ですか？

12
00:00:36,110 --> 00:00:39,450
これまでのところ、我々は見てきたように？

13
00:00:39,450 --> 00:00:42,540
あなたは何を得たのですか？

14
00:00:42,540 --> 00:00:44,028
何もない。

15
00:00:44,028 --> 00:00:45,020
>> 学生：[聞こえない]。

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1：あれは、何ですか。

17
00:00:45,395 --> 00:00:46,410
>> 学生：[聞こえない]。

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1：固定サイズ。

19
00:00:47,000 --> 00:00:51,260
[OK]を、なぜ固定サイズはしかし良いです？

20
00:00:51,260 --> 00:00:53,180
>> 学生：[聞こえない]。

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1：OK、そう、それは中に効率的です
あなたが割り当てることができるという意味

22
00:00:56,240 --> 00:01:00,070
スペースの一定量、うまくいけば
正確には同じくらいです。

23
00:01:00,070 --> 00:01:01,180
あなたが望むようなスペース。

24
00:01:01,180 --> 00:01:02,720
だから絶対にプラスになる可能性があります。

25
00:01:02,720 --> 00:01:06,530
>> アレイの別のアップ側は何ですか？

26
00:01:06,530 --> 00:01:07,610
うん？

27
00:01:07,610 --> 00:01:08,750
>> 学生：[聞こえない]。

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1：すべて - ごめん？

29
00:01:09,550 --> 00:01:11,270
>> 学生：[聞こえない]。

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1：メモリ内のすべてのボックス
又は互いに隣接。

31
00:01:13,620 --> 00:01:15,220
そして、それは便利です - なぜですか？

32
00:01:15,220 --> 00:01:15,970
それはかなり本当だ。

33
00:01:15,970 --> 00:01:18,611
しかし、どのように我々はその真実性を利用することができますか？

34
00:01:18,611 --> 00:01:21,500
>> 学生：[聞こえない]。

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1：その通り、私たちはトラックを保つことができる
すべてが知っているだけである

36
00:01:24,490 --> 00:01:28,560
すなわち一つのアドレスのアドレス
メモリのチャンクの最初のバイト。

37
00:01:28,560 --> 00:01:30,420
または文字列の場合には、
最初のアドレス

38
00:01:30,420 --> 00:01:31,460
その文字列のchar。

39
00:01:31,460 --> 00:01:33,330
そこから、我々は見つけることができます
文字列の終わり。

40
00:01:33,330 --> 00:01:35,710
私たちは、二番目の要素、見つけることができます
第三元素などが挙げられる。

41
00:01:35,710 --> 00:01:38,740
>> そして、その記述のように派手な方法
機能では、配列は私たちを与えるということです

42
00:01:38,740 --> 00:01:40,020
ランダムアクセス。

43
00:01:40,020 --> 00:01:44,330
ただ、角括弧を使用することにより
表記と番号、あなたはにジャンプすることができます

44
00:01:44,330 --> 00:01:48,070
配列内の特定の要素
一定時間、ビッグOで

45
00:01:48,070 --> 00:01:49,810
いわば一つの。

46
00:01:49,810 --> 00:01:51,080
>> しかし、いくつかの欠点がありまして。

47
00:01:51,080 --> 00:01:53,110
配列は非常に簡単に何をしませんか？

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
それは何が得意ではないのですか？

50
00:01:57,170 --> 00:01:58,810
>> 学生：[聞こえない]。

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1：あれは、何ですか。

52
00:01:59,860 --> 00:02:00,530
>> 学生：[聞こえない]。

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER：1サイズで展開。

54
00:02:01,460 --> 00:02:04,800
配列の欠点があるので、
ものの正確に反対

55
00:02:04,800 --> 00:02:05,540
五分五分です。

56
00:02:05,540 --> 00:02:07,610
だから、欠点の1つは
それは固定サイズだ。

57
00:02:07,610 --> 00:02:09,400
だから、あなたは本当にそれを成長することはできません。

58
00:02:09,400 --> 00:02:13,510
次の要素をbiggerチャンク割り当て直すことができ
メモリ、および、古い要素を移動

59
00:02:13,510 --> 00:02:14,460
新しい配列に変換します。

60
00:02:14,460 --> 00:02:18,060
のためのそして自由に古い配列、
malloc関数または同様のを使用してインスタンス、

61
00:02:18,060 --> 00:02:21,180
reallocを呼び出した関数、その
再割り当てメモリ。

62
00:02:21,180 --> 00:02:25,490
>> reallocのは、余談として、あなたを与えるしよう
アレイの横のメモリー

63
00:02:25,490 --> 00:02:26,610
あなたはすでに持っていること。

64
00:02:26,610 --> 00:02:28,740
しかし、それは物事を動かすかもしれない
完全に周り。

65
00:02:28,740 --> 00:02:30,710
しかし、要するに、それは右、高価なのですか？

66
00:02:30,710 --> 00:02:33,440
なぜならあなたは、メモリの塊を持っている場合
このサイズが、あなたは本当にいずれかをしたい

67
00:02:33,440 --> 00:02:36,710
このサイズの、あなたが保存したい
あなたが持っているオリジナルの要素、

68
00:02:36,710 --> 00:02:40,510
ほぼ線形時間コピー処理
から起こる必要があること

69
00:02:40,510 --> 00:02:41,900
新たに古い配列。

70
00:02:41,900 --> 00:02:44,630
そして現実はオペレーティングシステムを求めている
何度も何度も、システムと

71
00:02:44,630 --> 00:02:48,340
再びメモリの大きな塊を開始するために
同様にあなたにいくつかの時間を要します。

72
00:02:48,340 --> 00:02:52,250
だから、祝福と呪いで両方だ
変装、これらの配列その事実

73
00:02:52,250 --> 00:02:53,860
固定サイズである。

74
00:02:53,860 --> 00:02:56,790
しかし、我々は、代わりに何かをご紹介している場合
このように、我々はリンクと呼ばれる

75
00:02:56,790 --> 00:03:00,580
リストは、我々はいくつかの五分五分を取得し、
同様にここではいくつかの欠点。

76
00:03:00,580 --> 00:03:05,780
>> リンクされたリストは、単にデータですので、
構造体は、この中のCの構造体で構成されて

77
00:03:05,780 --> 00:03:09,850
構造体、リコールは、単にある場合、
1のコンテナ以上の特定

78
00:03:09,850 --> 00:03:11,100
変数の型。

79
00:03:11,100 --> 00:03:16,110
この場合には、どのようなデータ型を行う
構造体の内部にそのように見える

80
00:03:16,110 --> 00:03:17,600
最後の時間は、我々は、ノードと呼ばれる？

81
00:03:17,600 --> 00:03:19,380
これらの各四角形は、ノードです。

82
00:03:19,380 --> 00:03:22,660
小さい長方形の各
その中には、データ型である。

83
00:03:22,660 --> 00:03:25,300
私たちは何種類言った
彼らは月曜日でしたか？

84
00:03:25,300 --> 00:03:26,478
うん？

85
00:03:26,478 --> 00:03:27,870
>> 学生：[聞こえない]。

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER：1変数とポインタ、または
より具体的には、nのint型、、

87
00:03:30,721 --> 00:03:32,180
そして下部にポインタ。

88
00:03:32,180 --> 00:03:35,360
それらの両方がで、32ビットであることが起こる
このCS50のようなコンピュータ上に少なくとも

89
00:03:35,360 --> 00:03:37,980
アプライアンス、彼らがしているので、
サイズが均等に描かれた。

90
00:03:37,980 --> 00:03:42,260
>> だから、ポインタを使用している
明らかにするためでも？

91
00:03:42,260 --> 00:03:47,690
配列があったときに、なぜ今、この矢印を追加
とてもきれいでシンプルな？

92
00:03:47,690 --> 00:03:50,460
ポインタは何をやっている
私たちこれらの各ノードで？

93
00:03:50,460 --> 00:03:52,160
>> 学生：[聞こえない]。

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1：その通り。

95
00:03:52,465 --> 00:03:54,120
それはどこに言っている
次のいずれかです。

96
00:03:54,120 --> 00:03:57,350
だから私は、ソートののアナロジーを使う
一種のためにスレッドを使用して

97
00:03:57,350 --> 00:03:59,180
一緒にこれらのノードを通します。

98
00:03:59,180 --> 00:04:01,760
そして、それは我々がやっていることがまさにそれだ
これらのそれぞれのためのポインタ

99
00:04:01,760 --> 00:04:06,360
メモリの塊があってもなくてもよいか
連続して、背中合わせにバックアップする

100
00:04:06,360 --> 00:04:09,500
RAMの内側、なぜならたび
十分に私を与える、と言って、mallocを呼び出す

101
00:04:09,500 --> 00:04:12,510
新しいノードのバイト、それかもしれない
ここにあるか、それがここにあるかもしれない。

102
00:04:12,510 --> 00:04:13,120
それはここにあるかもしれない。

103
00:04:13,120 --> 00:04:13,730
それはここにあるかもしれない。

104
00:04:13,730 --> 00:04:14,640
あなただけ知らない。

105
00:04:14,640 --> 00:04:17,880
>> しかしのアドレスにポインタを使用
これらのノードには、ステッチが、それらをすることができ

106
00:04:17,880 --> 00:04:22,370
一緒に視覚的に見えるように
これらの事がある場合でも、リストのような

107
00:04:22,370 --> 00:04:26,770
すべてのあなたの1または全体に広がる
あなたの二つ以上のRAMをあなたの4ギガバイト

108
00:04:26,770 --> 00:04:28,760
自分のコンピュータの内側。

109
00:04:28,760 --> 00:04:33,230
>> の、その後、欠点は、そう
リンクリストは何ですか？

110
00:04:33,230 --> 00:04:34,670
我々はしている価格は何ですか
どうやら払って？

111
00:04:34,670 --> 00:04:36,010
>> 学生：[聞こえない]。

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1：もっとスペース、右？

113
00:04:36,920 --> 00:04:39,340
我々は、この場合には、量が倍増した
スペースを我々は行ってきたので、

114
00:04:39,340 --> 00:04:43,500
それぞれのノードごとに、32ビットから
int型なので、今では64ビットで、私たちがする必要があるため

115
00:04:43,500 --> 00:04:45,050
だけでなく、ポインタの周りを保つ。

116
00:04:45,050 --> 00:04:48,860
あなたの構造場合は、より多くの効率を得る
このシンプルなものよりも大きいです。

117
00:04:48,860 --> 00:04:52,020
実際には内部の学生を持っている場合
の文字列のカップルとなっている

118
00:04:52,020 --> 00:04:55,430
名前と家、多分ID番号、
完全にかもしれないいくつかの他のフィールド。

119
00:04:55,430 --> 00:04:59,000
>> ですから、十分な大きさの構造体を持っている場合、
多分ポインタのコストは

120
00:04:59,000 --> 00:05:00,010
しないような大したこと。

121
00:05:00,010 --> 00:05:03,570
これは、その中にコーナーケースのビットです
我々はこのような単純なプリミティブを格納している

122
00:05:03,570 --> 00:05:04,760
リンクリストの内側。

123
00:05:04,760 --> 00:05:05,790
しかし、ポイントは同じです。

124
00:05:05,790 --> 00:05:08,230
あなたは間違いなく多くを費やしている
メモリが、あなたは取得している

125
00:05:08,230 --> 00:05:08,990
柔軟性。

126
00:05:08,990 --> 00:05:12,280
今私は、要素を追加したい場合なので
このリストの先頭に、

127
00:05:12,280 --> 00:05:14,340
私は、新しいノードを割り当てる必要があります。

128
00:05:14,340 --> 00:05:17,180
そして私はちょうどそれらを更新する必要が
ただ移動することで何とか矢印

129
00:05:17,180 --> 00:05:17,980
周りにいくつかのポインタ。

130
00:05:17,980 --> 00:05:20,580
>> 私に何かを挿入したい場合は
リストの途中、私はする必要はありません

131
00:05:20,580 --> 00:05:24,410
我々が行ったように脇に誰をプッシュ
私たちのボランティアと週間の過去誰

132
00:05:24,410 --> 00:05:25,700
配列を表す。

133
00:05:25,700 --> 00:05:29,470
私はちょうど新しいノードを割り当てることができますし、
その後だけに矢印を指す

134
00:05:29,470 --> 00:05:32,290
異なる方向ではないので
実際に残ってする必要があります

135
00:05:32,290 --> 00:05:35,670
私が描いたようなメモリは真行
ここで画面上のそれ。

136
00:05:35,670 --> 00:05:38,400
>> そして最後に、挿入したい場合
リストの最後に何か、それはだ

137
00:05:38,400 --> 00:05:39,210
さらに簡単。

138
00:05:39,210 --> 00:05:43,320
これは、任意の表記法の一種である
しかし34のポインタは、推測を取る。

139
00:05:43,320 --> 00:05:46,710
最もそのポインタの値とは何ですか
昔のようなのありそうな描かソート

140
00:05:46,710 --> 00:05:47,700
そこに学校のアンテナ？

141
00:05:47,700 --> 00:05:48,920
>> 学生：[聞こえない]。

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1：それはおそらくヌルです。

143
00:05:49,900 --> 00:05:52,710
そして、確かにそれはある1著者の
ヌルの表現。

144
00:05:52,710 --> 00:05:56,310
なぜならあなたは絶対に、それはヌルです
知っておく必要がどこにリンクされているの終わり

145
00:05:56,310 --> 00:06:00,050
リストでは、次を維持しないように、である
これらの矢印に従い、以下

146
00:06:00,050 --> 00:06:01,170
いくつかのゴミ値に。

147
00:06:01,170 --> 00:06:06,230
だからヌルはありませんことを意味しません
番号34の右側に複数のノード、

148
00:06:06,230 --> 00:06:07,200
このような場合である。

149
00:06:07,200 --> 00:06:10,270
>> だから我々は我々が実装できることを提案
コー​​ド内でこのノード。

150
00:06:10,270 --> 00:06:12,130
そして我々はこの種を見てきました
構文の前に。

151
00:06:12,130 --> 00:06:15,090
typedefのはただのための新しいタイプを定義
私たちは、のように私たちに同義語を与え

152
00:06:15,090 --> 00:06:17,100
文字列は、char *のためだった。

153
00:06:17,100 --> 00:06:21,030
この場合、それは私達を与えるために起こっている
短縮表記となるよう構造ノード

154
00:06:21,030 --> 00:06:24,010
だけではなく、のように書くことができる。
ロットクリーナーであるノード。

155
00:06:24,010 --> 00:06:25,360
それははるかに少ない冗長です。

156
00:06:25,360 --> 00:06:30,080
>> ノードの内部が明らかにintで
と呼ばれるnと、次に構造体ノード*

157
00:06:30,080 --> 00:06:34,670
これは、私たちが望んで正確に何を意味する
を意味する矢印、別の体へのポインタ

158
00:06:34,670 --> 00:06:36,940
まったく同じデータタイプのノード。

159
00:06:36,940 --> 00:06:40,300
と私は、我々が実装できることを提案
このような検索機能、で

160
00:06:40,300 --> 00:06:41,890
一見は思えるかもしれない
少し複雑。

161
00:06:41,890 --> 00:06:43,330
しかし、それは文脈で見てみましょう。

162
00:06:43,330 --> 00:06:45,480
>> 私はここでアプライアンスにフェールオーバ行こう。

163
00:06:45,480 --> 00:06:48,460
私はと呼ばれるファイルを開くみよう
リストゼロドットH。

164
00:06:48,460 --> 00:06:53,950
そして、それは唯一の定義を我々が含まれています
ただこのデータの瞬間前に見ました

165
00:06:53,950 --> 00:06:55,390
タイプは、ノードと呼ばれる。

166
00:06:55,390 --> 00:06:57,350
だから我々は、そのドットhファイルに入れました。

167
00:06:57,350 --> 00:07:01,430
>> そして余談ですが、これでもかのよう
あなたが見たい程度だというプログラムです

168
00:07:01,430 --> 00:07:05,410
すべてではない、複雑な、それは確かだ
にプログラムを書き込む大会

169
00:07:05,410 --> 00:07:10,270
引っ張って、データ型のようなものを置く
時には、あなたの内部の定数

170
00:07:10,270 --> 00:07:13,210
ヘッダーファイルとは限らないで
確かにあなたのCファイル、ときに

171
00:07:13,210 --> 00:07:17,370
プログラムは、大きく、大きくなるので、
の両方を検索する場所をあなたは知っている

172
00:07:17,370 --> 00:07:20,840
いくつかのケースでドキュメント、または
このような基本的な、ために

173
00:07:20,840 --> 00:07:22,360
いくつかの型の定義。

174
00:07:22,360 --> 00:07:25,680
>> 私は今、リストゼロドットを開く場合
Cは、いくつかのことを気づく。

175
00:07:25,680 --> 00:07:29,090
これは、いくつかのヘッダファイルは、ほとんどが含まれています
そのうち我々は前に見てきました。

176
00:07:29,090 --> 00:07:31,980
これは、独自のヘッダファイルを含む。

177
00:07:31,980 --> 00:07:35,200
>> そして余談として、その理由は、二重だ
ここで引用符として角度に反対

178
00:07:35,200 --> 00:07:38,340
ライン上の括弧その
私はそこ強調してきた？

179
00:07:38,340 --> 00:07:39,180
>> 学生：[聞こえない]。

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1：うんので、ローカルファイルです。

181
00:07:40,460 --> 00:07:44,300
もしそうなら、それはここにあなた自身のローカルファイルだ
例えば、15行目で、使用

182
00:07:44,300 --> 00:07:46,570
二重引用符代わりに
山括弧の。

183
00:07:46,570 --> 00:07:48,270
>> さて、これは面白いの一種である。

184
00:07:48,270 --> 00:07:51,830
私はグローバルに宣言したことに注意してください
18行目で、このプログラムの変数

185
00:07:51,830 --> 00:07:55,910
最初に呼び出され、このことアイデアがある
最初へのポインタになるだろう

186
00:07:55,910 --> 00:07:59,190
私のリンクリスト内のノード、そして私がしました
私がきたので、それはnullに初期化

187
00:07:59,190 --> 00:08:02,310
任意の実際の割り当てられていない
ただまだノード。

188
00:08:02,310 --> 00:08:07,570
>> だから、これは何を我々は、画像で表し、
画像に一瞬前に見たように

189
00:08:07,570 --> 00:08:10,090
そのはるか上のポインタ
左側。

190
00:08:10,090 --> 00:08:12,260
だから今は、そのポインタ
矢印を持っていない。

191
00:08:12,260 --> 00:08:14,590
それだけではなくnullになります。

192
00:08:14,590 --> 00:08:17,880
しかし、それはどうなるかを表している
最初に実際のアドレス

193
00:08:17,880 --> 00:08:19,480
このリスト内のノード。

194
00:08:19,480 --> 00:08:22,120
だから私は、それがグローバルで実装しました
あなたはわかりますように、なぜなら、すべてこの

195
00:08:22,120 --> 00:08:25,310
プログラムでは、生活の中で実装されません
私のためのリンクリスト。

196
00:08:25,310 --> 00:08:27,050
>> 今私はここにいくつかのプロトタイプを持っている。

197
00:08:27,050 --> 00:08:31,190
私のような機能を実装することを決定
欠失、挿入、検索、および

198
00:08:31,190 --> 00:08:31,740
トラバーサル - 

199
00:08:31,740 --> 00:08:35,210
最後はただ歩いて渡ること
リスト、その要素をプリントアウト。

200
00:08:35,210 --> 00:08:36,750
そして今、ここに私のメインルーチンです。

201
00:08:36,750 --> 00:08:39,890
そして、我々にあまりにも多くの時間を費やすことはありません
これがうまくいけば、一種であるので、これらの

202
00:08:39,890 --> 00:08:41,780
今では古い帽子。

203
00:08:41,780 --> 00:08:45,370
>> 私は、次の操作を実行するつもりです
ユーザーが協力しながら。

204
00:08:45,370 --> 00:08:47,300
1だから、私は印刷するつもりです
このメニューから。

205
00:08:47,300 --> 00:08:49,420
そして、私はそれのようにフォーマットしました
きれいに私ができるように。

206
00:08:49,420 --> 00:08:52,240
意味1で、ユーザーがタイプ、その場合
彼らは何かを削除したい。

207
00:08:52,240 --> 00:08:54,560
二つに、ユーザがタイプした場合、そのことを意味し
彼らは何かを挿入したい。

208
00:08:54,560 --> 00:08:55,930
など。

209
00:08:55,930 --> 00:08:58,270
私はその後、要求するつもり
次にコマンドの。

210
00:08:58,270 --> 00:08:59,300
そして私は場合、getIntを使用するつもりです。

211
00:08:59,300 --> 00:09:02,790
>> だから、これは本当に簡単メニュー操作です
あなただけ入力する必要がインタフェース

212
00:09:02,790 --> 00:09:05,270
1の数字へのマッピング
これらのコマンドの。

213
00:09:05,270 --> 00:09:08,730
そして今、私は良いクリーンなスイッチがあり
に切り替えることが起こっている声明

214
00:09:08,730 --> 00:09:10,090
ユーザーが入力したログインどんな

215
00:09:10,090 --> 00:09:12,180
それらが1つを入力した場合と、私はよ
削除呼び出すと壊れる。

216
00:09:12,180 --> 00:09:14,380
彼らは2を入力した場合、私はよ
挿入呼び出すと壊れる。

217
00:09:14,380 --> 00:09:16,490
>> そして今、私はそれぞれの置かれているに気づく
これらの同じライン上の。

218
00:09:16,490 --> 00:09:18,360
これは単なる文体の決定です。

219
00:09:18,360 --> 00:09:20,210
一般的に我々は何かを見てきました
このように。

220
00:09:20,210 --> 00:09:23,260
しかし、私はただ、率直に言って、私のプログラムを決定した
読みやすく見えたので、

221
00:09:23,260 --> 00:09:25,980
それは唯一の4例であった
ちょうどこのようにそれを示します。

222
00:09:25,980 --> 00:09:28,360
スタイルの完全に合法的な使用。

223
00:09:28,360 --> 00:09:31,480
そして、私はこれがそう長くするつもりです
ユーザがゼロに入力されておらず、そのI

224
00:09:31,480 --> 00:09:33,910
それらが終了したいことを意味しますことを決めた。

225
00:09:33,910 --> 00:09:36,630
>> だから今、私は何に気づく
ここで何をするつもり。

226
00:09:36,630 --> 00:09:38,650
私は明らかにリストを解放するつもりです。

227
00:09:38,650 --> 00:09:40,230
一瞬でその上で、より多くの。

228
00:09:40,230 --> 00:09:41,640
最初にこのプログラムを実行してみましょう。

229
00:09:41,640 --> 00:09:45,250
だから私は大きなターミナルを作ろう
窓、ドットスラッシュリスト0。

230
00:09:45,250 --> 00:09:49,510
私が先に行くとによって挿入するつもりです
タイピング2、今では50のような数、および

231
00:09:49,510 --> 00:09:51,590
あなたは、リストは今50ですがわかります。

232
00:09:51,590 --> 00:09:53,380
そして、私のテキストは少しだけ上にスクロール。

233
00:09:53,380 --> 00:09:55,940
だから今はリストに含まれて気づく
番号50。

234
00:09:55,940 --> 00:09:58,220
>> 2を取ることによって、別の挿入を行うましょう。

235
00:09:58,220 --> 00:10:01,630
1のように番号を入力してみましょう。

236
00:10:01,630 --> 00:10:03,940
リストは現在50に続く一つです。

237
00:10:03,940 --> 00:10:06,020
だからこれは単なるテキスト表現です
リストの。

238
00:10:06,020 --> 00:10:10,550
などもう一つの番号を挿入てみましょう
うまくいけば、ある番号42、

239
00:10:10,550 --> 00:10:14,620
ので、途中で終わるつもり
特定の種類の中で、このプログラムはそれ

240
00:10:14,620 --> 00:10:16,320
それを挿入してなどの要素。

241
00:10:16,320 --> 00:10:17,220
だから、そこに我々はそれを持っている。

242
00:10:17,220 --> 00:10:20,730
できたスーパー簡単なプログラム
絶対に配列を使用しましたが、私た

243
00:10:20,730 --> 00:10:23,280
リンクリストを使用することが起こる
ちょうどので、私は動的にすることができます

244
00:10:23,280 --> 00:10:24,610
成長し、それを縮小。

245
00:10:24,610 --> 00:10:28,470
>> 私場合それでは、検索のためのを見てみましょう
コマンド3を実行し、私が検索したい

246
00:10:28,470 --> 00:10:31,040
数43、言う、のために。

247
00:10:31,040 --> 00:10:34,190
そして、何も明らかに認められなかった、
私は戻っても応答を得ないので。

248
00:10:34,190 --> 00:10:35,010
それでは、再びこれを行うことができます。

249
00:10:35,010 --> 00:10:35,690
検索。

250
00:10:35,690 --> 00:10:39,520
レッツ50の検索、またはむしろ検索
42のために、それは素敵なを持っている

251
00:10:39,520 --> 00:10:40,850
少し微妙な意味。

252
00:10:40,850 --> 00:10:42,610
そして、私はそこに人生の意味を発見した。

253
00:10:42,610 --> 00:10:44,990
あなたがわからない場合は数42、
参照は、それをGoogleに。

254
00:10:44,990 --> 00:10:45,350
わかりました。

255
00:10:45,350 --> 00:10:47,130
それでは、私のためにこのプログラムを行っている？

256
00:10:47,130 --> 00:10:50,660
それはちょうど私は、このように挿入することができている
遠くと要素を検索します。

257
00:10:50,660 --> 00:10:53,650
>> に、その後、早送りしてみましょう
私たちは、ちらっと見たその関数

258
00:10:53,650 --> 00:10:55,360
ティーザーとして月曜日に。

259
00:10:55,360 --> 00:10:59,620
この関数は、だから、私は主張し、検索のため
最初で、リスト内の要素

260
00:10:59,620 --> 00:11:03,830
1、ユーザーにプロンプ​​トを表示してから、呼び出し
実際のint型を取得する場合、getInt

261
00:11:03,830 --> 00:11:05,060
あなたが検索したい。

262
00:11:05,060 --> 00:11:06,460
>> 次に、このに気づく。

263
00:11:06,460 --> 00:11:10,690
私は一時的な変数を作成するつもりです
ライン188でポインタと呼ばれる - 

264
00:11:10,690 --> 00:11:11,270
PTR  - 

265
00:11:11,270 --> 00:11:12,440
それに何と言ったかもしれない。

266
00:11:12,440 --> 00:11:16,140
そしてそれは、ノードへのポインタだ
私はそこに、ノード*と言ったので。

267
00:11:16,140 --> 00:11:19,900
そして、私はそれが等しくなるように初期化しています
最初に私は効果的に持っているというのが私の

268
00:11:19,900 --> 00:11:22,860
非常に指、いわば、
リストの最初の要素。

269
00:11:22,860 --> 00:11:27,460
ここに私の右手はPTR私があるのであれば
同じものを指して、最初

270
00:11:27,460 --> 00:11:28,670
を指している。

271
00:11:28,670 --> 00:11:31,430
>> だから今バックコードで、
何が次に起こる - 

272
00:11:31,430 --> 00:11:35,070
反復するとき、これは一般的なパラダイムである
のような構造上の

273
00:11:35,070 --> 00:11:35,970
リンクリスト。

274
00:11:35,970 --> 00:11:40,410
私はしばらくの間、次の操作を行うつもりだ
ポインタが一方だからnullに等しくない

275
00:11:40,410 --> 00:11:47,530
私の指には、いくつかのヌルを指していません
値は、矢印ポインタnがnと等しい場合。

276
00:11:47,530 --> 00:11:52,290
我々はnが何であることを最初に気づくでしょう
当たりGetIntsで入力したユーザーは、ここで呼び出す。

277
00:11:52,290 --> 00:11:54,280
>> とポインタ矢印nが何を意味？

278
00:11:54,280 --> 00:11:59,020
さて、我々はここで絵に戻った場合、
私は指を指している場合

279
00:11:59,020 --> 00:12:02,960
9、含むその最初のノード
矢印は、基本的にそれに行くことを意味し

280
00:12:02,960 --> 00:12:08,860
ノードと、位置nにおける値をつかむ
この場合には、n個のデータ·フィールドと呼ばれる。

281
00:12:08,860 --> 00:12:14,120
>> 余談ですが - と我々はこのカップルを見た
週間前に誰かが尋ねられたとき - 

282
00:12:14,120 --> 00:12:18,840
この構文は新しいですが、それはしません
私たちに力を与えることを我々

283
00:12:18,840 --> 00:12:20,040
既に持っていませんでした。

284
00:12:20,040 --> 00:12:25,325
使用するのと同じこのフレーズは何だったの
ドット表記とスターカップル

285
00:12:25,325 --> 00:12:29,490
週間前、我々は戻って皮をむいたとき
少し早まってこの層？

286
00:12:29,490 --> 00:12:31,780
>> 学生：[聞こえない]。

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1：その通り、それがスターだった、と
それはと、スタードットNだった

288
00:12:38,880 --> 00:12:41,930
ルックスここで括弧、、
率直に言って、私は多くのことを考える

289
00:12:41,930 --> 00:12:43,320
読みより不可解。

290
00:12:43,320 --> 00:12:46,270
しかし、星のポインター、いつものように、
手段がそこに行く。

291
00:12:46,270 --> 00:12:49,090
そして、一度はそこにいる、どのようなデータ
フィールドには、アクセスしたいのですか？

292
00:12:49,090 --> 00:12:52,730
さてあなたはアクセスするためにドット表記法を使用し
構造体のデータ·フィールド、およびI

293
00:12:52,730 --> 00:12:54,140
特にnが欲しい。

294
00:12:54,140 --> 00:12:56,240
>> 率直に言って、私はこれを主張するだろう
読むためだけに困難です。

295
00:12:56,240 --> 00:12:58,080
それはどこで覚えておくことが難しくなっている
括弧は、行くのですか

296
00:12:58,080 --> 00:12:59,030
星とすべてのこと。

297
00:12:59,030 --> 00:13:02,150
だから、世界はいくつかの構文を採用した
砂糖、いわば。

298
00:13:02,150 --> 00:13:04,740
言うだけのセクシーな方法、
これは等価であり、

299
00:13:04,740 --> 00:13:05,970
おそらくもっと直感的。

300
00:13:05,970 --> 00:13:09,600
ポインタが実際にポインタである場合、
矢印表記手段がそこに行くと見つける

301
00:13:09,600 --> 00:13:11,890
この場合のフィールドは、nと呼ばれる。

302
00:13:11,890 --> 00:13:13,660
>> 私はそれを見つけるのであれば、私は何をすべきかに気づく。

303
00:13:13,660 --> 00:13:17,430
私は単に、私がパーセント私を発見し、プリントアウト
そのint型の値をプラグイン。

304
00:13:17,430 --> 00:13:20,730
私は種類にただ1秒間スリープ呼び出す
に画面上で一時停止の事

305
00:13:20,730 --> 00:13:22,900
ユーザに吸収する第二を与える
何が起こったばかり。

306
00:13:22,900 --> 00:13:24,290
そして私は破る。

307
00:13:24,290 --> 00:13:26,330
そうでなければ、私は何をしますか？

308
00:13:26,330 --> 00:13:30,960
私は平等へのポインタを更新
次のポインタ矢印。

309
00:13:30,960 --> 00:13:35,840
>> だから明確にすること、これは行く意味
そこに、私の古い学校の表記を使用して。

310
00:13:35,840 --> 00:13:39,580
だから、これは単に何に行くことを意味します
あなたは非常には、そのを指している

311
00:13:39,580 --> 00:13:43,660
最初のケースは、私が指していますです
その中に9と構造体。

312
00:13:43,660 --> 00:13:44,510
だから私はそこに行ってきた。

313
00:13:44,510 --> 00:13:47,880
そして、ドット表記を意味し、
次の時の値を取得します。

314
00:13:47,880 --> 00:13:50,470
>> しかし価値は、それが描かれているにもかかわらず
狭いように、ただの数字です。

315
00:13:50,470 --> 00:13:51,720
それは数値アドレスです。

316
00:13:51,720 --> 00:13:55,670
どうか、この1行のコードでは、そう
このように書かれ、多くの不可解な

317
00:13:55,670 --> 00:14:00,190
方法、またはこのような、もう少し
直感的な方法は、ちょうど私の手を動かすことを意味

318
00:14:00,190 --> 00:14:03,460
最初のノードから次のいずれかに、
その後、次のいずれか、その後

319
00:14:03,460 --> 00:14:05,320
など1次、と。

320
00:14:05,320 --> 00:14:09,920
>> だから私たちは、他にこだわることはありません
挿入、削除の実装

321
00:14:09,920 --> 00:14:14,030
とトラバーサル、最初の2つの
そのかなり関与している。

322
00:14:14,030 --> 00:14:17,010
そして、私はそれを得るために非常に簡単だと思う
口頭でそれをやったときに失った。

323
00:14:17,010 --> 00:14:19,890
しかし、私たちはここで行うことができますです
方法を決定しようとする

324
00:14:19,890 --> 00:14:21,640
視覚的にこれを行うことが最善。

325
00:14:21,640 --> 00:14:24,800
私が提案するので、もし我々
これに要素を挿入したい

326
00:14:24,800 --> 00:14:26,680
既存のリスト、その
五行を持っています - 

327
00:14:26,680 --> 00:14:29,530
9、17、22、26、および33  - 

328
00:14:29,530 --> 00:14:33,300
私は、これを実装しようとしていた場合
コー​​ドは、私が移動する方法を検討する必要があります

329
00:14:33,300 --> 00:14:34,160
これを行うことについて。

330
00:14:34,160 --> 00:14:37,720
>> と私は、赤ちゃんの手順を取って提案する
それによって、このケースでは、私は意味が何であるか

331
00:14:37,720 --> 00:14:41,090
その我々の可能なシナリオ
一般的に発生する可能性がある？

332
00:14:41,090 --> 00:14:44,120
リンクされたの挿入を実装する場合
リストは、これは単なるであることを起こる

333
00:14:44,120 --> 00:14:46,090
サイズ5の具体例を示す。

334
00:14:46,090 --> 00:14:50,420
さてあなたは番号を挿入したい場合は、
ナンバーワンと言うように、と

335
00:14:50,420 --> 00:14:53,380
どこに、ソートされた順序を維持
明らかに1がする必要がある数はありません

336
00:14:53,380 --> 00:14:55,686
この特定の例で行く？

337
00:14:55,686 --> 00:14:56,840
冒頭で好き。

338
00:14:56,840 --> 00:15:00,030
>> しかし興味深い何それはそこにある
この中に1を挿入したい場合

339
00:15:00,030 --> 00:15:04,100
リスト、どのような特別なポインタのニーズ
明らかに更新される？

340
00:15:04,100 --> 00:15:04,610
最初。

341
00:15:04,610 --> 00:15:07,830
だから私は、これが最初のケースである、と主張するだろう
我々は、検討する必要がありますことを

342
00:15:07,830 --> 00:15:11,140
で挿入を含むシナリオ
リストの先頭。

343
00:15:11,140 --> 00:15:15,400
>> のも同様に簡単または多分オフ摘み取るう
容易な場合、相対的に言って。

344
00:15:15,400 --> 00:15:18,110
私が挿入したいとしましょう
ソートされた順序で番号35。

345
00:15:18,110 --> 00:15:20,600
それは明らかにあそこ属する。

346
00:15:20,600 --> 00:15:25,320
だから、明らかにポインタがに何が起こっているか
そのシナリオで更新される必要がありますか？

347
00:15:25,320 --> 00:15:30,060
34のポインタがnullではないとなって
しかし、構造体のアドレス

348
00:15:30,060 --> 00:15:31,800
番号35を含んでいる。

349
00:15:31,800 --> 00:15:32,750
だからケース2です。

350
00:15:32,750 --> 00:15:36,190
だからもう、私は、量子化のようなものだ
いくら私がここでしなければならない仕事。

351
00:15:36,190 --> 00:15:39,880
>> そして最後に、明らかな中間ケースである
確かに、途中で、私がしたい場合は

352
00:15:39,880 --> 00:15:45,870
行くと言う23、のようなものを挿入する
23と26の間に、しかし、

353
00:15:45,870 --> 00:15:48,680
今、物事はもう少し得る
何のために関与

354
00:15:48,680 --> 00:15:52,800
ポインタを変更する必要が？

355
00:15:52,800 --> 00:15:56,680
22は明らかに変更する必要があるので、
彼はもう26を指すことはできませんので。

356
00:15:56,680 --> 00:16:00,320
彼は新しいノードを指す必要があること
私が呼び出して割り当てる必要があります

357
00:16:00,320 --> 00:16:01,770
malloc関数または一部同等。

358
00:16:01,770 --> 00:16:05,990
>> しかし、私はまた、新しいノード、23が必要
この場合には、そのポインタを持っている

359
00:16:05,990 --> 00:16:07,870
誰を指す？

360
00:16:07,870 --> 00:16:08,560
26。

361
00:16:08,560 --> 00:16:10,380
とがあるように起こっている
ここでは操作の順序。

362
00:16:10,380 --> 00:16:13,410
私は愚かにも、これを行う場合があるため、私
インスタンスの開始時に始動用

363
00:16:13,410 --> 00:16:16,040
リスト、および私の目標は23を挿入することです。

364
00:16:16,040 --> 00:16:18,610
そして、私は確認して、それが属していません
ここでは、9の近く？

365
00:16:18,610 --> 00:16:18,950
いいえ。

366
00:16:18,950 --> 00:16:20,670
それは17の隣に、ここに属していますか？

367
00:16:20,670 --> 00:16:20,940
いいえ。

368
00:16:20,940 --> 00:16:22,530
それは22の隣にここに属していますか？

369
00:16:22,530 --> 00:16:23,300
はい。

370
00:16:23,300 --> 00:16:26,400
>> 今私はここに愚かだ、とされていない場合
私は、これを可能性を通して考える

371
00:16:26,400 --> 00:16:28,320
23のための私の新しいノードを割り当てる。

372
00:16:28,320 --> 00:16:32,080
私はからポインタを更新するかもしれません
ノードは、ポインティング、22と呼ばれる

373
00:16:32,080 --> 00:16:33,080
新しいノードでのそれ。

374
00:16:33,080 --> 00:16:36,140
そして私は更新する何がありますか
新しいノードのポインタでなければするには？

375
00:16:36,140 --> 00:16:38,120
>> 学生：[聞こえない]。

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1：その通り。

377
00:16:38,385 --> 00:16:39,710
26でポインティング。

378
00:16:39,710 --> 00:16:45,590
しかし、私はすでに更新されなかった場合くそ
この男を指すように22のポインタ、および

379
00:16:45,590 --> 00:16:48,260
今私は孤児、残りを持っている
リストでは、いわば。

380
00:16:48,260 --> 00:16:52,140
ここでの操作だから順
重要になるだろう。

381
00:16:52,140 --> 00:16:55,100
>> これを行うには私は、盗むことができる
、6人のボランティアと言う。

382
00:16:55,100 --> 00:16:57,650
そして、我々はこれを行うことができないかどうかを確認してみましょう
視覚の代わりにコードが賢明。

383
00:16:57,650 --> 00:16:59,330
そして、私たちはいくつかの素敵なストレスを持っている
今日はあなたのためのボール。

384
00:16:59,330 --> 00:17:02,510
[OK]を、どのように約1、2、
バック - そこの端に。

385
00:17:02,510 --> 00:17:04,530
3つ、4つ、あなたの両方
最後にみんな。

386
00:17:04,530 --> 00:17:05,579
と5、6。

387
00:17:05,579 --> 00:17:05,839
かしこまりました。

388
00:17:05,839 --> 00:17:06,450
五六。

389
00:17:06,450 --> 00:17:08,390
すべての権利と私たちは来る
次回君たちへ。

390
00:17:08,390 --> 00:17:09,640
すべての権利は​​、アップに来る。

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> すべての権利は​​、ここで最初にしているので、
あなたは、ぎこちなく1になりたい

393
00:17:14,819 --> 00:17:16,119
ここでGoogleのグラスで？

394
00:17:16,119 --> 00:17:19,075
すべての権利なので、[OK]を、ガラス、
ビデオを録画。

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
[OK]を、あなたが行ってもいいです。

397
00:17:24,589 --> 00:17:27,950
>> すべての権利なので、皆さんは上に来ることができる場合
ここで、私が事前に用意しています

398
00:17:27,950 --> 00:17:30,110
いくつかの数字。

399
00:17:30,110 --> 00:17:31,240
すべての権利、こっちに来る。

400
00:17:31,240 --> 00:17:33,440
そして、なぜあなたは少しに行かない
さらにそのように。

401
00:17:33,440 --> 00:17:35,520
そして、あなたの名前は何だ、見てみましょう
Googleのガラスと？

402
00:17:35,520 --> 00:17:35,910
>> 学生：ベン。

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1：ベン？

404
00:17:36,230 --> 00:17:38,380
OK、ベン、あなたは文字通り、初めてとなる。

405
00:17:38,380 --> 00:17:40,580
だから我々はあなたを送信するつもりだ
ステージの最後に。

406
00:17:40,580 --> 00:17:41,670
すべての権利、そしてあなたの名前は？

407
00:17:41,670 --> 00:17:41,990
>> 学生：ジェイソン。

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1：ジェイソン、OKはよ
ナンバーナインなる。

409
00:17:44,530 --> 00:17:46,700
あなたはベンそのようにフォローしたいのであれば。

410
00:17:46,700 --> 00:17:47,010
>> 学生：ジル。

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1：ジルは、ことになるだろう
私はこれ以上行われたい場合17、

412
00:17:49,630 --> 00:17:51,260
インテリジェントに、私が持っているでしょう
もう一方の端に開始。

413
00:17:51,260 --> 00:17:52,370
あなたは、その道を行く。

414
00:17:52,370 --> 00:17:53,030
22。

415
00:17:53,030 --> 00:17:53,670
あなたですか？

416
00:17:53,670 --> 00:17:53,980
>> 学生：メアリー。

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1：メアリーは、22になります。

418
00:17:56,130 --> 00:17:58,420
あなたのお名前は？

419
00:17:58,420 --> 00:17:58,810
>> 学生：クリス。

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1：クリス、あなたは26になります。

421
00:18:00,100 --> 00:18:00,740
そして最後に。

422
00:18:00,740 --> 00:18:01,400
>> 学生：ダイアナ。

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1：ダイアナ、あなたは34になります。

424
00:18:02,670 --> 00:18:03,920
だから、こっちに来る。

425
00:18:03,920 --> 00:18:06,360
>> すべての権利なので、並べ替え完成
すでにオーダー。

426
00:18:06,360 --> 00:18:09,600
とのは、先に行くと、これをやらせる
 - ので、私たちは本当にできること

427
00:18:09,600 --> 00:18:11,720
ベンは、見ているだけのようなものだ
そこにどこに出て。

428
00:18:11,720 --> 00:18:15,670
OK、それでは、先に行くと、これを描いてみましょう
私がいた同じように、腕を使って、正確に、

429
00:18:15,670 --> 00:18:16,250
何が起こっている。

430
00:18:16,250 --> 00:18:19,540
だから先に行くと自分自身を与える
足や自分の間に2つ。

431
00:18:19,540 --> 00:18:22,900
そして、もう一つの手にと先に行くとポイント
誰でもあなたを指してされるべきである

432
00:18:22,900 --> 00:18:23,470
これに基づいて。

433
00:18:23,470 --> 00:18:25,890
あなたがnullなら、ただ指す
まっすぐ床に。

434
00:18:25,890 --> 00:18:27,690
OK、とても良い。

435
00:18:27,690 --> 00:18:32,290
>> だから今我々は、リンクされたリストを持っている、と私を聞かせて
私はの役割を果たすだろうことを提案

436
00:18:32,290 --> 00:18:35,110
PTRので、私は気にしないでしょう
これを持ち運び。

437
00:18:35,110 --> 00:18:37,830
そして - 誰か愚か大会 - 
あなたが欲しい、この何を呼び出すことができます - 

438
00:18:37,830 --> 00:18:39,800
前身ポインタ、PREDポインタ - 

439
00:18:39,800 --> 00:18:43,930
それはちょうど我々が与えたニックネームだ
私の左手に、当社のサンプルコード。

440
00:18:43,930 --> 00:18:47,240
維持されようとしている一方、
で誰が誰であるかを追跡

441
00:18:47,240 --> 00:18:48,400
次のシナリオ。

442
00:18:48,400 --> 00:18:52,390
>> だから最初に、私はオフ摘み取るしたい、とします
挿入のその最初の例は、言う

443
00:18:52,390 --> 00:18:54,330
20、リストに。

444
00:18:54,330 --> 00:18:57,160
だから私はに誰かを必要とするつもりだ
私たちのために20番を体現。

445
00:18:57,160 --> 00:18:58,950
だから私は、malloc関数の誰かに必要
聴衆から。

446
00:18:58,950 --> 00:18:59,380
までさあ。

447
00:18:59,380 --> 00:19:00,340
あなたの名前は？

448
00:19:00,340 --> 00:19:01,300
>> 学生：ブライアン。

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1：ブライアン、大丈夫なので、
20を含むノードでなければならない。

450
00:19:05,270 --> 00:19:06,810
すべての権利、こっちに来る。

451
00:19:06,810 --> 00:19:10,025
そして明らかに、どこ
ブライアンは属していない？

452
00:19:10,025 --> 00:19:12,190
だから、の途中で - 実際に、
ちょっと待ってください。

453
00:19:12,190 --> 00:19:13,420
私達は順序のこれをやっている。

454
00:19:13,420 --> 00:19:17,170
私たちは、多くの困難にこれを作っている
それは最初に必要以上。

455
00:19:17,170 --> 00:19:21,210
[OK]を、我々は自由ブライアンするつもりだ
5として、またreallocのブライアン。

456
00:19:21,210 --> 00:19:23,680
>> [OK]を、ので、今私たちは、挿入したい
5としてブライアン。

457
00:19:23,680 --> 00:19:25,960
だから隣にこっちに来て
ちょっとベン。

458
00:19:25,960 --> 00:19:28,250
そして、あなたはおそらく言うことができます
この物語がどこへ行くのか。

459
00:19:28,250 --> 00:19:30,500
しかしみましょうについて慎重に検討
操作の順序。

460
00:19:30,500 --> 00:19:32,880
そしてそれはまさにこの視覚的な
並べるために起こっていること

461
00:19:32,880 --> 00:19:34,080
そのサンプルコード付き。

462
00:19:34,080 --> 00:19:40,120
だからここに私は、PTRは最初指しています
ベン、それ自体ではなく、どのような時ではない

463
00:19:40,120 --> 00:19:43,245
彼は、含まれているその値は、この場合の
です - あなたの名前は再び何ですか？

464
00:19:43,245 --> 00:19:43,670
>> 学生：ジェイソン。

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1：ジェイソン、ベンと私の両方があるので、
この瞬間にジェイソンを指す。

466
00:19:47,350 --> 00:19:49,700
だから今、私は決定する必要があり、
ブライアンはどこに属しているのでしょうか？

467
00:19:49,700 --> 00:19:53,500
唯一だから私はへのアクセス権を持って
今は彼のn個のデータ項目である。

468
00:19:53,500 --> 00:19:58,280
だから私は、チェックすることですつもりだ
ジェイソン未満ブライアン？

469
00:19:58,280 --> 00:19:59,770
答えは本当です。

470
00:19:59,770 --> 00:20:03,680
>> だから今が起こる必要があるか、
正しい順序で？

471
00:20:03,680 --> 00:20:07,120
私はどのように多くのポインタを更新する必要があります
この物語の中で合計で？

472
00:20:07,120 --> 00:20:10,720
私の手はまだで指している場所
ジェイソン、そしてあなたの手 - あなたがしたい場合

473
00:20:10,720 --> 00:20:12,930
私は、一種の、ようにあなたの手を置く
、疑問符を知らない。

474
00:20:12,930 --> 00:20:14,070
OK、いい。

475
00:20:14,070 --> 00:20:15,670
>> 大丈夫、あなたが持っているので、
いくつかの候補者。

476
00:20:15,670 --> 00:20:20,500
ベンまたはIまたはブライアンまたはジェイソンどちら
または皆、どの

477
00:20:20,500 --> 00:20:21,370
ポインタは、変更する必要がありますか？

478
00:20:21,370 --> 00:20:23,260
どのように合計で多くの？

479
00:20:23,260 --> 00:20:24,080
>> [OK]を、ので、2つの。

480
00:20:24,080 --> 00:20:27,090
私のポインターは本当にもう問題ではありません
私はただ一時的だから。

481
00:20:27,090 --> 00:20:31,370
だから、おそらく、これらの二人だ
ベンとブライアンの両方。

482
00:20:31,370 --> 00:20:34,410
だから我々は更新することを私は提案してみましょう
ベンは、以来、彼が最初だ。

483
00:20:34,410 --> 00:20:36,350
このリストの最初の要素
今ブライアンになるだろう。

484
00:20:36,350 --> 00:20:38,070
ブライアンでとてもベンポイント。

485
00:20:38,070 --> 00:20:39,320
[OK]を、今何？

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> 誰が誰に指摘される？

488
00:20:43,460 --> 00:20:44,710
>> 学生：[聞こえない]。

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1：OKブライアンが持っているので、
ジェイソンを指すように。

490
00:20:46,180 --> 00:20:48,360
しかし、私はそのポインタのトラックを失っている？

491
00:20:48,360 --> 00:20:49,980
ジェイソンがどこにあるか私は知っていますか？

492
00:20:49,980 --> 00:20:50,790
>> 学生：[聞こえない]。

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1：私は以来、私は、やる
一時的なポインタです。

494
00:20:52,620 --> 00:20:55,110
そしておそらく、私は変わっていない
新しいノードを指すように。

495
00:20:55,110 --> 00:20:58,300
だから我々は、単にブライアン·ポイントを持つことができます
誰に私を指しています。

496
00:20:58,300 --> 00:20:59,000
そして我々は完了です。

497
00:20:59,000 --> 00:21:01,890
だからケース1、で挿入
リストの先頭。

498
00:21:01,890 --> 00:21:02,950
2つの主要なステップがありました。

499
00:21:02,950 --> 00:21:06,750
その後一、我々はベンを更新する必要があり、
我々はまた、ブライアンを更新する必要があります。

500
00:21:06,750 --> 00:21:09,230
そして私は気にする必要はありません
の残りの部分を通してtraipsing

501
00:21:09,230 --> 00:21:12,680
我々はすでに彼を発見したので、リスト、
彼はに属しているため場所、

502
00:21:12,680 --> 00:21:14,080
最初の要素の左。

503
00:21:14,080 --> 00:21:15,400
>> すべての権利なので、かなり簡単。

504
00:21:15,400 --> 00:21:18,110
我々は、ほとんどしているように実際には、感じている
これはあまりにも複雑になっています。

505
00:21:18,110 --> 00:21:20,240
だから今終わりをオフに摘むてみましょう
リストの、どこを参照してください

506
00:21:20,240 --> 00:21:21,380
複雑さが始まります。

507
00:21:21,380 --> 00:21:24,560
聴衆からのだから今なら、私はalloc命令。

508
00:21:24,560 --> 00:21:25,540
誰もが55をプレイしたいですか？

509
00:21:25,540 --> 00:21:26,700
すべての権利、私が最初にあなたの手を見た。

510
00:21:26,700 --> 00:21:29,620
までさあ。

511
00:21:29,620 --> 00:21:30,030
うん。

512
00:21:30,030 --> 00:21:31,177
あなたの名前は？

513
00:21:31,177 --> 00:21:32,310
>> 学生：[聞こえない]。

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1：Habata。

515
00:21:33,240 --> 00:21:33,890
[OK]を、アップで来る。

516
00:21:33,890 --> 00:21:35,730
あなたは、番号55になります。

517
00:21:35,730 --> 00:21:37,820
だから、もちろん、所属する
リストの最後。

518
00:21:37,820 --> 00:21:41,850
それでは、私と一緒にシミュレーションを再生してみましょう
ちょっとPTRである。

519
00:21:41,850 --> 00:21:44,050
だから私は最初を指すつもり
どんなベンを指している。

520
00:21:44,050 --> 00:21:45,900
我々は今、ブライアンで指している両方。

521
00:21:45,900 --> 00:21:48,420
だから55が5個未満ではありません。

522
00:21:48,420 --> 00:21:52,510
だから私はで自分自身を更新するつもりです
誰が、ブライアンの次のポインタを指す

523
00:21:52,510 --> 00:21:54,450
今は、もちろんジェイソンである。

524
00:21:54,450 --> 00:21:57,310
55はそう、9未満でない
私はPTRを更新するつもりです。

525
00:21:57,310 --> 00:21:58,890
私はPTRを更新するつもりです。

526
00:21:58,890 --> 00:22:02,290
私はPTRを更新するつもりです
私はPTRを更新するつもり。

527
00:22:02,290 --> 00:22:05,060
そして、私はするつもりです - うーん、何
あなたの名前を再び？

528
00:22:05,060 --> 00:22:05,560
>> 学生：ダイアナ。

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER：1ダイアナが指している、もちろん、
彼女の左手でヌルで。

530
00:22:09,190 --> 00:22:13,030
だからここで実際にHabataん
明らかに属しているのか？

531
00:22:13,030 --> 00:22:15,050
ここで、左に。

532
00:22:15,050 --> 00:22:19,460
だから私はここで彼女を置く方法を知っていますか
私がめちゃくちゃしたと思う。

533
00:22:19,460 --> 00:22:22,420
PTR芸術とは何かがあるため
時間のこの瞬間？

534
00:22:22,420 --> 00:22:23,240
ヌル。

535
00:22:23,240 --> 00:22:25,580
そうであっても、視覚的に、我々はできる
明らかに、これらのすべてを見る

536
00:22:25,580 --> 00:22:26,610
ここでステージ上のみんな。

537
00:22:26,610 --> 00:22:29,680
私は、以前の記録を維持していませんでした
リスト内の人。

538
00:22:29,680 --> 00:22:33,210
私は、指摘指を持っていない
この場合、ノード番号34。

539
00:22:33,210 --> 00:22:34,760
>> それでは、実際にこれを最初からやり直すことができます。

540
00:22:34,760 --> 00:22:37,560
だから今私は実際に必要なのですか
第2のローカル変数。

541
00:22:37,560 --> 00:22:40,980
そして、これはあなたが表示されますものです
として私は行く実際のサンプルCコード、、

542
00:22:40,980 --> 00:22:45,860
私はポイントに私の右手を更新するとき
ジェイソンは、それによって、私が、背後にブライアンを離れる

543
00:22:45,860 --> 00:22:51,440
良い私の左手への使用を開始
私がいたところ、私が行くようになるように、更新

544
00:22:51,440 --> 00:22:52,700
このリストを - 

545
00:22:52,700 --> 00:22:55,040
もっとぎこちなく私が意図したより
今ここに視覚的に - 

546
00:22:55,040 --> 00:22:56,740
私を取得するつもりだ
リストの最後。

547
00:22:56,740 --> 00:23:00,020
>> この手はかなりある、まだnullです
示すこと以外、役に立たない

548
00:23:00,020 --> 00:23:02,980
私は、リストの最後に明らかによ
しかし、今では少なくとも私はこれを持っている

549
00:23:02,980 --> 00:23:08,270
前身ポインタはそう、ここで指す
今何手渡し、どのポインタが必要

550
00:23:08,270 --> 00:23:10,150
更新する？

551
00:23:10,150 --> 00:23:13,214
誰の手にあなたが選択してください
最初に再構成する？

552
00:23:13,214 --> 00:23:15,190
>> 学生：[聞こえない]。

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1：OK、ダイアナのよう。

554
00:23:16,220 --> 00:23:21,110
どこで指すようにしたいですか
でダイアナの左ポインタ？

555
00:23:21,110 --> 00:23:23,620
55で、おそらく、そのよう
我々はそこに挿入した。

556
00:23:23,620 --> 00:23:25,560
どこで55ポインタが行くべき？

557
00:23:25,560 --> 00:23:27,000
ダウンして、ヌルを表す。

558
00:23:27,000 --> 00:23:28,890
そして、私の手は、この時点では、しないでください
彼らはただだったので問題では

559
00:23:28,890 --> 00:23:30,070
一時変数。

560
00:23:30,070 --> 00:23:31,030
だから今我々は完了です。

561
00:23:31,030 --> 00:23:34,650
>> だから、そこに追加の複雑さ - と
それは、実装することは難しいことではありません

562
00:23:34,650 --> 00:23:38,660
しかし、我々は作るために二次的な変数が必要
前に私は私の右に移動することを確認

563
00:23:38,660 --> 00:23:42,140
一方、私は左の値を更新
手、PREDこの場合はポインタなので、

564
00:23:42,140 --> 00:23:45,860
私は末尾のポインタを持っていることを
私がいた場所を追跡する。

565
00:23:45,860 --> 00:23:49,360
さて余談として、あなたがこれを考えている場合
それはのように経由して、これは感じている

566
00:23:49,360 --> 00:23:51,490
続けなければならないことが少しうるさい
この左手のトラック。

567
00:23:51,490 --> 00:23:54,015
>> 何が別の解決策は、だろう
この問題に行ったことがある？

568
00:23:54,015 --> 00:23:56,500
してデータを再設計するようになった場合
我々は話をしている構造

569
00:23:56,500 --> 00:23:59,630
今スルー？

570
00:23:59,630 --> 00:24:02,690
これだけの種類のは少しを感じた場合
、のように、二つのポインタを持っている迷惑

571
00:24:02,690 --> 00:24:08,430
リストを通過する、誰か他の可能性
、理想的な世界では、維持している

572
00:24:08,430 --> 00:24:10,160
私たちが必要とする情報？

573
00:24:10,160 --> 00:24:11,360
うん？

574
00:24:11,360 --> 00:24:12,610
>> 学生：[聞こえない]。

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1：その通り。

577
00:24:16,150 --> 00:24:19,130
右のように興味深いのは、実際にあり
アイデアの胚芽。

578
00:24:19,130 --> 00:24:22,470
と以前のポインタのこのアイデア、
前の要素を指す。

579
00:24:22,470 --> 00:24:25,580
私はちょうどそれを具現化したらどう
リスト自体の内側？

580
00:24:25,580 --> 00:24:27,810
そしてそれは視覚化するのは難しいことになるだろう
このすべての用紙なし

581
00:24:27,810 --> 00:24:28,830
床に落下。

582
00:24:28,830 --> 00:24:31,860
しかし、これらの人は両方を使用したことを仮定し
彼らの手の前のを持っている

583
00:24:31,860 --> 00:24:35,950
それによって、ポインタ、および次のポインタ、
我々は二重に呼ぶことにします何を実装

584
00:24:35,950 --> 00:24:36,830
リンクリスト。

585
00:24:36,830 --> 00:24:41,090
つまり、私は巻き戻しを並べ替えることができるようになる
はるかに容易に私なし、

586
00:24:41,090 --> 00:24:43,800
プログラマ、維持すること
手動で追跡する - 

587
00:24:43,800 --> 00:24:44,980
本当に手動で - 

588
00:24:44,980 --> 00:24:47,280
私が以前にあった場所に
リストに表示されます。

589
00:24:47,280 --> 00:24:48,110
だから我々はそれを行うことはありません。

590
00:24:48,110 --> 00:24:50,950
それだから我々は、それをシンプルに保つよ
価格で来ることを行って、二倍

591
00:24:50,950 --> 00:24:53,450
ポインタのために多くのスペース、
2番目のいずれかをしたい場合。

592
00:24:53,450 --> 00:24:55,760
しかし、それは確かに一般的です
と呼ばれるデータ構造

593
00:24:55,760 --> 00:24:57,410
二重リンクリスト。

594
00:24:57,410 --> 00:25:01,310
>> ここで最後の例を実行し、置いてみましょう
彼らの不幸のうち、これらの人。

595
00:25:01,310 --> 00:25:03,270
mallocの20だから。

596
00:25:03,270 --> 00:25:05,320
そこ通路から上がってさあ。

597
00:25:05,320 --> 00:25:06,280
大丈夫、あなたの名前は何ですか？

598
00:25:06,280 --> 00:25:07,440
>> 学生：[聞こえない]。

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1：申し訳ありません？

600
00:25:07,855 --> 00:25:08,480
>> 学生：[聞こえない]。

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER：1 Demeron？

602
00:25:09,410 --> 00:25:10,230
OKまでに来る。

603
00:25:10,230 --> 00:25:11,910
あなたが20でなければならない。

604
00:25:11,910 --> 00:25:14,720
あなたは明らかにしようとしている
17と22の間に属しています。

605
00:25:14,720 --> 00:25:16,150
だから私は私の教訓を学ぶことができます。

606
00:25:16,150 --> 00:25:18,150
私はポインタを開始するつもりだ
ブライアンを指す。

607
00:25:18,150 --> 00:25:21,190
そして私は私の左手を持っているつもりです
私は移動するだけブライアンへのアップデート

608
00:25:21,190 --> 00:25:23,600
ジェイソン、チェックは9より20少ないのか？

609
00:25:23,600 --> 00:25:24,060
いいえ。

610
00:25:24,060 --> 00:25:25,430
17以上20未満でありますか？

611
00:25:25,430 --> 00:25:25,880
いいえ。

612
00:25:25,880 --> 00:25:27,450
22以上20未満でありますか？

613
00:25:27,450 --> 00:25:28,440
はい。

614
00:25:28,440 --> 00:25:34,070
それでは、ポインタまたは手が変更する必要があります
彼らは今指している場所？

615
00:25:34,070 --> 00:25:37,070
>> だから我々は20を指して17を行うことができます。

616
00:25:37,070 --> 00:25:37,860
だから大丈夫です。

617
00:25:37,860 --> 00:25:40,080
どこに指すようにしたいですか
今あなたのポインタ？

618
00:25:40,080 --> 00:25:41,330
22時。

619
00:25:41,330 --> 00:25:45,410
22がどこにあるか、我々は再び、感謝を知っている
私の一時的なポインタへ。

620
00:25:45,410 --> 00:25:46,760
だから私たちはそこにOKです。

621
00:25:46,760 --> 00:25:49,440
そうこのため一時記憶
私は誰もがどこにあるかを追跡し守ってきた。

622
00:25:49,440 --> 00:25:55,055
そして今、あなたは、視覚的にどこに行くことができます
あなたが所属し、今、私たちは、1、2、3、必要

623
00:25:55,055 --> 00:25:58,410
4、5、6、7、8、9ストレスボール、
とのために拍手

624
00:25:58,410 --> 00:25:59,770
これらの人は、我々はできれば。

625
00:25:59,770 --> 00:26:00,410
うまく行って。

626
00:26:00,410 --> 00:26:05,320
>> [拍手]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1：すべての権利。

628
00:26:06,330 --> 00:26:09,860
そして、あなたは作品を保つかもしれない
記念品としての紙。

629
00:26:09,860 --> 00:26:15,930
>> すべての権利なので、それは多くの私を信頼
容易にその中を歩くために

630
00:26:15,930 --> 00:26:17,680
それは実際のコードであるよりも、人間。

631
00:26:17,680 --> 00:26:22,690
しかし、あなたは一瞬で見つけるのか
今、その同じです - ああ、ありがとうございます。

632
00:26:22,690 --> 00:26:23,630
ありがとう - 

633
00:26:23,630 --> 00:26:29,360
あなたはその同じデータを見つけることです
構造、リンクされたリストは、実際にすることができます

634
00:26:29,360 --> 00:26:33,200
より一層のビルディングブロックとして使用すること
洗練されたデータ構造。

635
00:26:33,200 --> 00:26:37,620
>> そして、ここであまりにもテーマを実現することです
我々は絶対にそれ以上を導入しました

636
00:26:37,620 --> 00:26:40,060
実装に複雑
このアルゴリズムである。

637
00:26:40,060 --> 00:26:43,940
挿入、そして我々はそれを通り抜けた場合、
削除と検索は、少しです

638
00:26:43,940 --> 00:26:46,660
それよりも複雑
配列していました。

639
00:26:46,660 --> 00:26:48,040
しかし、我々はいくつかのダイナミズムを得る。

640
00:26:48,040 --> 00:26:50,180
我々は、適応データ構造を取得します。

641
00:26:50,180 --> 00:26:54,010
>> しかし、再び、私たちはいくつかを持っていることの代償を払う
両方で追加の複雑さ、

642
00:26:54,010 --> 00:26:54,910
それを実装する。

643
00:26:54,910 --> 00:26:56,750
そして我々は、ランダムアクセスをあきらめている。

644
00:26:56,750 --> 00:27:00,450
と正直に言うと、いくつかの素晴らしいではありません
スライドをきれいに私はあなたを与えることができる

645
00:27:00,450 --> 00:27:03,120
なぜリンクされたリストであるここで言う
配列よりも優れています。

646
00:27:03,120 --> 00:27:04,100
そして、その時点でそれを残す。

647
00:27:04,100 --> 00:27:07,520
テーマがあっても、すぐ再発するので
より多くのように今後数週間のうちに、ある

648
00:27:07,520 --> 00:27:10,200
必ずしも存在しないということ
正解。

649
00:27:10,200 --> 00:27:13,830
>> 我々は独立した軸を持っている理由です
問題セットのデザインの。

650
00:27:13,830 --> 00:27:17,700
これは非常に文脈依存になります
このデータを使用するかどうか

651
00:27:17,700 --> 00:27:21,750
構造やその一つであり、それを意志
言葉であなたに重要なものに依存

652
00:27:21,750 --> 00:27:24,620
資源と複雑さ。

653
00:27:24,620 --> 00:27:28,830
>> しかし、私は、その理想的なデータを提案してみましょう
構造、聖杯は、だろう

654
00:27:28,830 --> 00:27:32,200
定数時間だ何か、
かかわらず、多くのものがどの程度の

655
00:27:32,200 --> 00:27:36,940
その中に、それは素晴らしいではない場合
データ構造は、中に答えを返す

656
00:27:36,940 --> 00:27:37,920
時定数。

657
00:27:37,920 --> 00:27:38,330
はい。

658
00:27:38,330 --> 00:27:40,110
この言葉はあなたの巨大な辞書である。

659
00:27:40,110 --> 00:27:41,550
またはNO、この言葉ではありません。

660
00:27:41,550 --> 00:27:43,270
またはそこにそのような問題がある。

661
00:27:43,270 --> 00:27:46,360
我々は、少なくともできない場合まあ見てみましょう
それに向かって一歩を踏み出す。

662
00:27:46,360 --> 00:27:50,190
>> 私は新しいデータ構造を提案させている
、別のもののために使用することができます

663
00:27:50,190 --> 00:27:52,260
このケースではハッシュテーブルと呼ばれる。

664
00:27:52,260 --> 00:27:55,590
そして、我々はかすめるに戻る実際にしている
この場合には配列と、時

665
00:27:55,590 --> 00:28:00,550
幾分任意、私はこれを描いた
一種の持つ配列としてハッシュテーブル

666
00:28:00,550 --> 00:28:02,810
二次元配列 - 

667
00:28:02,810 --> 00:28:05,410
あるいはむしろそれは、2つとしてここに描かれている
次元配列 - しかし、これはただです

668
00:28:05,410 --> 00:28:10,770
このような我々であれば、そのサイズ26の配列、
配列表、表ブラケットを呼び出す

669
00:28:10,770 --> 00:28:12,440
ゼロが一番上に矩形です。

670
00:28:12,440 --> 00:28:15,090
テーブルブラケット25は、長方形です
一番下にある。

671
00:28:15,090 --> 00:28:18,620
そして、これは私がデータを描画する方法です
私が保管する構造

672
00:28:18,620 --> 00:28:19,790
人の名前。

673
00:28:19,790 --> 00:28:24,370
>> だから例えば、私は描くことはありません
私ならオーバーヘッドでここに全部、

674
00:28:24,370 --> 00:28:29,160
私は今に行くよ、この配列を、持っていた
ハッシュテーブルを呼び出し、これは再び

675
00:28:29,160 --> 00:28:31,360
場所ゼロ。

676
00:28:31,360 --> 00:28:34,840
これはここの場所です
など1、と。

677
00:28:34,840 --> 00:28:37,880
私はこのデータを使用することを主張する
議論のために構造、

678
00:28:37,880 --> 00:28:42,600
人の名前を格納するために、アリスとボブ
とチャーリーおよび他のそのような名前。

679
00:28:42,600 --> 00:28:46,110
だから、始まりとして今、この考える
辞書、言う、の

680
00:28:46,110 --> 00:28:47,520
言葉の多くが付いている。

681
00:28:47,520 --> 00:28:49,435
彼らは名前のことが起こる
ここに私たちの例では

682
00:28:49,435 --> 00:28:52,560
そして、これはには、おそらく、あまりにも密接です。
我々のように、スペルチェッカーを実装

683
00:28:52,560 --> 00:28:54,400
問題のために6を設定することもできます。

684
00:28:54,400 --> 00:28:59,300
>> だから我々は全体の大きさ26の配列を持っている場合
これは25日の場所になるように

685
00:28:59,300 --> 00:29:03,390
一番下にある、と私はアリスであることを主張する
の辞書の最初の単語

686
00:29:03,390 --> 00:29:07,260
私はRAMに挿入する名前、
このデータ構造に、どこにいる

687
00:29:07,260 --> 00:29:12,480
あなたを伝える本能そのアリスの
名前は、この配列に行くべきでしょうか？

688
00:29:12,480 --> 00:29:13,510
>> 我々は26のオプションがあります。

689
00:29:13,510 --> 00:29:14,990
私たちは、彼女を入れたい場所は？

690
00:29:14,990 --> 00:29:16,200
我々は、ブラケットゼロで彼女にしたいよね？

691
00:29:16,200 --> 00:29:18,280
アリスのために、のはそのゼロを呼び出してみましょう。

692
00:29:18,280 --> 00:29:20,110
AとBは1になり、そしてCは2となる。

693
00:29:20,110 --> 00:29:22,600
だから私たちは書くつもり
ここでアリスの名前まで。

694
00:29:22,600 --> 00:29:24,890
我々はその後、ボブ、彼のを挿入した場合
名前はここに行きます。

695
00:29:24,890 --> 00:29:27,280
チャーリーはここに行きます。

696
00:29:27,280 --> 00:29:30,500
などを通じてダウン
このデータ構造。

697
00:29:30,500 --> 00:29:32,090
>> これは素晴らしいデータ構造です。

698
00:29:32,090 --> 00:29:32,730
なぜですか？

699
00:29:32,730 --> 00:29:37,460
井戸の実行時間は何ですか
この中に人間の名前を挿入する

700
00:29:37,460 --> 00:29:39,850
今データ構造？

701
00:29:39,850 --> 00:29:43,702
このテーブルが実装されていることを考えると、
本当に、配列として。

702
00:29:43,702 --> 00:29:44,940
まあそれは、一定の時間です。

703
00:29:44,940 --> 00:29:45,800
それは1つの順序だ。

704
00:29:45,800 --> 00:29:46,360
なぜですか？

705
00:29:46,360 --> 00:29:48,630
>> さてどのように決定するか
アリスは所属どこ？

706
00:29:48,630 --> 00:29:51,000
あなたは、その彼女の名前の文字を見て？

707
00:29:51,000 --> 00:29:51,490
最初。

708
00:29:51,490 --> 00:29:54,350
それが文字列である場合、あなたは、そこに着くことができます
単に文字列を見て

709
00:29:54,350 --> 00:29:55,200
ブラケットゼロ。

710
00:29:55,200 --> 00:29:57,110
文字列のゼロ番目の文字がそう。

711
00:29:57,110 --> 00:29:57,610
それは簡単です。

712
00:29:57,610 --> 00:30:00,350
私たちは、暗号であることをしました
代入週間前。

713
00:30:00,350 --> 00:30:05,310
そして一度はアリスのことを知っている
手紙は首都である、我々は引くことができます

714
00:30:05,310 --> 00:30:08,160
65または資本自体、オフ
それは私たちにゼロを与えます。

715
00:30:08,160 --> 00:30:10,940
だから我々は今、アリスが属していることを知っている
位置ゼロに。

716
00:30:10,940 --> 00:30:14,240
>> そして、このデータへのポインタを与えられる
ある種の構造は、どのくらいない

717
00:30:14,240 --> 00:30:18,840
それは場所を見つけるために私を取る
配列内のゼロ？

718
00:30:18,840 --> 00:30:22,080
ただ、一歩は、右のそれは一定の時間だ
ランダムアクセスのために我々

719
00:30:22,080 --> 00:30:23,780
提案は、配列の特徴であった。

720
00:30:23,780 --> 00:30:28,570
だから要するに、考え出す何インデックス
アリスの名前の中、ある、ある

721
00:30:28,570 --> 00:30:32,610
この場合は、あるか、みましょうだけで解決する
ゼロに、ここで、Bは一つであり、Cであること

722
00:30:32,610 --> 00:30:34,900
2、それを考え出す
時定数である。

723
00:30:34,900 --> 00:30:38,510
私はちょうど、彼女の最初の文字を見ている
ゼロがどこにあるかを考え出す

724
00:30:38,510 --> 00:30:40,460
配列はまた、時定数である。

725
00:30:40,460 --> 00:30:42,140
だから技術的にあることです
現在、2つのステップのように。

726
00:30:42,140 --> 00:30:43,330
しかし、それはまだ定数です。

727
00:30:43,330 --> 00:30:46,880
そこで我々は1のその大きなOを呼び出すので、き
このテーブルにアリスを挿入

728
00:30:46,880 --> 00:30:48,440
時定数。

729
00:30:48,440 --> 00:30:50,960
>> しかし、もちろん、私はされています
ここで素朴な、右？

730
00:30:50,960 --> 00:30:53,240
どのクラスのアーロンがあったら？

731
00:30:53,240 --> 00:30:53,990
それともアリシア？

732
00:30:53,990 --> 00:30:57,230
または任意の他の名前で始まる
A.どこに置くつもりです

733
00:30:57,230 --> 00:31:00,800
その人は、右？

734
00:31:00,800 --> 00:31:03,420
私が意味する、今3つしかありませ
テーブルの上の人なので、多分私達

735
00:31:03,420 --> 00:31:07,490
場所でアーロンを置くべき
ゼロ1 2 3。

736
00:31:07,490 --> 00:31:09,480
>> 右、私はここに置くことができます。

737
00:31:09,480 --> 00:31:13,350
しかし、その後、我々はにデイビッドを挿入しようとした場合
このリストは、ダビデが行くのでしょうか？

738
00:31:13,350 --> 00:31:15,170
今、私たちのシステムは破壊開始
ダウン、右？

739
00:31:15,170 --> 00:31:19,210
今、ダビデはここで終わりますので、
アーロンはここに実際にある場合。

740
00:31:19,210 --> 00:31:23,060
持つことのそして今、この全体的なアイデア
私たちを与えるクリーンなデータ構造

741
00:31:23,060 --> 00:31:28,010
一定時間の挿入はもはや
私がする必要があるので、時定数、

742
00:31:28,010 --> 00:31:31,240
チェック、ああ、クソ、誰かがすでにだ
アリスの場所で。

743
00:31:31,240 --> 00:31:35,320
>> 私は、この残りのデータを精査しましょう
置くためのスポットを探している構造、

744
00:31:35,320 --> 00:31:37,130
アーロンの名前のような人。

745
00:31:37,130 --> 00:31:39,390
そしてあまりにも開始されている
線形時間を取る。

746
00:31:39,390 --> 00:31:42,710
また、あなたは今、検索したい場合
このデータ構造でアーロン、そしてあなた

747
00:31:42,710 --> 00:31:45,430
チェックして、アーロンの名前はここではありません。

748
00:31:45,430 --> 00:31:47,960
理想的には、あなただけのアーロンのだと思います
ていないデータ構造である。

749
00:31:47,960 --> 00:31:51,530
しかし、あなたがのための部屋を作り始めなければ
Dがあったはずアーロン

750
00:31:51,530 --> 00:31:55,600
またはE、あなた、最悪の場合、チェックする必要があり
全体のデータ構造で

751
00:31:55,600 --> 00:31:59,480
それは何かに委譲された場合
テーブルのサイズの線形。

752
00:31:59,480 --> 00:32:00,920
>> 大丈夫だから、私はこれを修正します。

753
00:32:00,920 --> 00:32:04,200
ここでの問題は、私が持っていたということです
この配列内の26の要素。

754
00:32:04,200 --> 00:32:05,000
私はそれを変更しましょう​​。

755
00:32:05,000 --> 00:32:06,010
おっと。

756
00:32:06,010 --> 00:32:10,600
むしろの幸福そのように私はそれを変更しましょう
合計でサイズ26、ボトムに気付く

757
00:32:10,600 --> 00:32:12,720
インデックスは、nから1を引いた値に変更する予定です。

758
00:32:12,720 --> 00:32:16,610
26は人間のための明らかに小さすぎると
名前、何千ものがあるので、

759
00:32:16,610 --> 00:32:20,830
世界の名は、単に作ってみましょう
100または1,000または10,000。

760
00:32:20,830 --> 00:32:22,960
ただより多くの領域を割り当ててみましょう。

761
00:32:22,960 --> 00:32:27,230
>> まあ必ずしも低下しないこと
我々は、2つを持っていない確率

762
00:32:27,230 --> 00:32:31,510
で始まる、と名前を持つ人々
だから、あなたが配置しようとするつもりだった

763
00:32:31,510 --> 00:32:33,120
まだ場所ゼロで名前。

764
00:32:33,120 --> 00:32:36,850
彼らはまだ、衝突しようとしているどの
我々はまだ配置するソリューションを必要と意味

765
00:32:36,850 --> 00:32:41,020
アリスとアロンとアリシアや他の
他の場所で始まる名前。

766
00:32:41,020 --> 00:32:43,460
しかし、これはどの程度の問題でしょうか？

767
00:32:43,460 --> 00:32:46,870
あなたその確率は何ですか
データの衝突を持っている

768
00:32:46,870 --> 00:32:48,240
このような構造？

769
00:32:48,240 --> 00:32:52,570
>> まあ、私を聞かせて - 私たちは戻ってくる
ここにその質問へ。

770
00:32:52,570 --> 00:32:55,530
そして、どのように我々は可能性があるを見て
最初にそれを解決する。

771
00:32:55,530 --> 00:32:58,480
私はここでこの提案を引き上げてみましょう。

772
00:32:58,480 --> 00:33:02,020
私たちはただ説明するアルゴリズムであり、
線形と呼ばれるヒューリスティック

773
00:33:02,020 --> 00:33:05,030
を挿入しようとした場合、それによってプロービング
ここで、このデータで何か

774
00:33:05,030 --> 00:33:08,920
ハッシュテーブルと呼ばれる構造で、
と余地あなたは、そこにありません

775
00:33:08,920 --> 00:33:12,000
真のデータ構造を調べる
チェックし、これはありますか？

776
00:33:12,000 --> 00:33:13,430
この利用可能な、この利用可能です？

777
00:33:13,430 --> 00:33:13,980
これはありますか？

778
00:33:13,980 --> 00:33:17,550
そして、それは最終的にあるときは、挿入
あなたが最初に意図した名前

779
00:33:17,550 --> 00:33:19,370
他の場所でその位置で。

780
00:33:19,370 --> 00:33:23,360
しかし、最悪の場合には、唯一のスポット
データの一番下かもしれない

781
00:33:23,360 --> 00:33:25,090
構造、配列の最後の最後。

782
00:33:25,090 --> 00:33:30,130
>> だから線形最悪の場合、プロービング、
線形アルゴリズムどこに委譲

783
00:33:30,130 --> 00:33:34,500
アーロンは、彼が最後に挿入されるように発生した場合
このデータ構造では、彼はかもしれ

784
00:33:34,500 --> 00:33:39,540
この第一の位置と衝突したが、
その後、一番最後に不運で終了。

785
00:33:39,540 --> 00:33:43,940
だから、これは一定ではありません
時間私たちのために聖杯。

786
00:33:43,940 --> 00:33:47,650
挿入する要素のこのアプローチに
データ構造は、ハッシュと呼ばれる

787
00:33:47,650 --> 00:33:52,050
表は、一定時間ではないようです
少なくとも、一般的なケースである。

788
00:33:52,050 --> 00:33:54,000
それは線形なものに委譲することができます。

789
00:33:54,000 --> 00:33:56,970
>> 私たちは、衝突を解決するそれでは場合
多少異なる？

790
00:33:56,970 --> 00:34:00,740
だからここでは、より洗練されただ
まだ何へのアプローチ

791
00:34:00,740 --> 00:34:02,800
ハッシュテーブルと呼ばれる。

792
00:34:02,800 --> 00:34:05,890
とハッシュによって、余談として、何
私は、そのインデックスであることを意味

793
00:34:05,890 --> 00:34:07,070
私は以前に言及した。

794
00:34:07,070 --> 00:34:09,810
できるハッシュ何かに
動詞として考える。

795
00:34:09,810 --> 00:34:13,690
>> あなたハッシュアリスは名前だのであれば、
ハッシュ関数、いわば

796
00:34:13,690 --> 00:34:14,710
数を返す必要があります。

797
00:34:14,710 --> 00:34:18,199
彼女が属している場合で、この場合にはゼロである
彼女はに属していれば場所ゼロ、1つ

798
00:34:18,199 --> 00:34:20,000
位置オン、などが挙げられる。

799
00:34:20,000 --> 00:34:24,360
だから私のハッシュ関数はこれまでされている
だけを見て超簡単、

800
00:34:24,360 --> 00:34:26,159
誰かの名前の最初の文字。

801
00:34:26,159 --> 00:34:29,090
しかし、ハッシュ関数は次のように取り
入力データのいくつかの作品、

802
00:34:29,090 --> 00:34:30,210
文字列、int型、何でも。

803
00:34:30,210 --> 00:34:32,239
そしてそれは、一般的に数値を出してくれる。

804
00:34:32,239 --> 00:34:35,739
そして、その数はここで、そのデータ
要素は、データ構造に属し

805
00:34:35,739 --> 00:34:37,800
ハッシュテーブルとしてここで知られています。

806
00:34:37,800 --> 00:34:41,400
>> だから直感的に、これは
わずかに異なるコンテキスト。

807
00:34:41,400 --> 00:34:44,170
これは、実際の例を参照している
関与誕生日、どこ

808
00:34:44,170 --> 00:34:46,850
できるだけ多くのがあるかもしれない
月の31日。

809
00:34:46,850 --> 00:34:52,239
しかし、この人は何をすることを決定しました
衝突が発生した場合にですか？

810
00:34:52,239 --> 00:34:55,304
コンテキストは、現在の衝突はないという
名前が、誕生日の衝突、

811
00:34:55,304 --> 00:35:00,760
二人で同じ誕生日を持っている場合
例えば、10月2日。

812
00:35:00,760 --> 00:35:02,120
>> 学生：[聞こえない]。

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1：うん、そう、ここで我々は持っている
リンクリストの活用。

814
00:35:05,010 --> 00:35:07,830
だから、少し異なるように見える
よりも我々はそれを以前に描きました。

815
00:35:07,830 --> 00:35:10,790
しかし、我々は配列に持っているように見える
左側に。

816
00:35:10,790 --> 00:35:13,230
それは、1つのインデックスません
特定の理由。

817
00:35:13,230 --> 00:35:14,630
しかし、それはまだ配列です。

818
00:35:14,630 --> 00:35:16,160
これは、ポインタの配列です。

819
00:35:16,160 --> 00:35:20,670
これらの要素のそれぞれの、それぞれの
これらの円またはスラッシュ - スラッシュ

820
00:35:20,670 --> 00:35:23,970
表すヌル - これらの各
ポインタが明らかにを指している

821
00:35:23,970 --> 00:35:25,730
どのようなデータ構造？

822
00:35:25,730 --> 00:35:26,890
リンクリスト。

823
00:35:26,890 --> 00:35:30,530
>> だから今我々は能力を持っている
私たちのプログラムにハードコード

824
00:35:30,530 --> 00:35:32,010
テーブルのサイズ。

825
00:35:32,010 --> 00:35:35,360
このケースでは、我々はそこことはない知っている
月に31日以上。

826
00:35:35,360 --> 00:35:38,480
だから難しいです31のような値をコーディングする
その文脈で妥当。

827
00:35:38,480 --> 00:35:42,700
名前のコンテキストでは、ハードコーディング
26は無理ではありませんそれは人々の

828
00:35:42,700 --> 00:35:46,340
名前だけで、例えば、で始まる
Z.を通じて関与アルファベット

829
00:35:46,340 --> 00:35:50,180
>> 我々は、すべて、そのデータにそれらを詰め込むことができます
我々が得る限り、構造、

830
00:35:50,180 --> 00:35:55,330
衝突、我々はここに名前を入れてはいけません、
我々は、代わりにこれらの細胞を考える

831
00:35:55,330 --> 00:36:00,270
としてではなく文字列を自分自身、しかし、
例えばへのポインタ、アリス。

832
00:36:00,270 --> 00:36:03,660
そしてアリスは別のポインタを持つことができます
で始まる別の名前に

833
00:36:03,660 --> 00:36:06,150
A.そして、ボブは実際にこっちに行く。

834
00:36:06,150 --> 00:36:10,850
>> そして始まる別の名前があ​​る場合
Bで、彼はここにかけて終了します。

835
00:36:10,850 --> 00:36:15,070
そしてそれぞれのこのの要素の
我々は、この設計されていれば表2、

836
00:36:15,070 --> 00:36:17,350
もう少し巧妙に - 

837
00:36:17,350 --> 00:36:18,125
に来る - 

838
00:36:18,125 --> 00:36:22,950
我々はもう少しこれを設計した場合
巧みに、今適応データとなり

839
00:36:22,950 --> 00:36:27,720
ないハードリミットがない構造、
を挿入することができますどのように多くの要素について

840
00:36:27,720 --> 00:36:30,700
そこにあなたがしている場合は、持っているので、
大丈夫です衝突、。

841
00:36:30,700 --> 00:36:34,690
ただ、先に行くと、それを追加
我々はあった少し前に見たもの

842
00:36:34,690 --> 00:36:38,290
リンクリストとして知られています。

843
00:36:38,290 --> 00:36:39,690
>> まあちょっとのポーズしてみましょう。

844
00:36:39,690 --> 00:36:42,570
衝突の確率は何ですか
最初の場所で？

845
00:36:42,570 --> 00:36:45,480
右、多分私は上多分、と思ってい
私は、この問題をエンジニアリング上のよ

846
00:36:45,480 --> 00:36:46,370
あなたは何を知っているので？

847
00:36:46,370 --> 00:36:49,070
はい、私は、任意のを考え出すことができる
のような私の頭の上から例

848
00:36:49,070 --> 00:36:52,870
アリソンとアーロンが、現実には、
の均一な分布所与

849
00:36:52,870 --> 00:36:56,990
入力は、いくつかのランダムな挿入です
データ構造に、本当に何ですか

850
00:36:56,990 --> 00:36:58,580
衝突確率？

851
00:36:58,580 --> 00:37:01,670
まあ結局、それは実際の
超高。

852
00:37:01,670 --> 00:37:03,850
私はこれを一般化しましょう
問題は、このようになります。

853
00:37:03,850 --> 00:37:08,890
>> だから、nの部屋でCS50学生、何
確率は少なくとも

854
00:37:08,890 --> 00:37:11,010
部屋の中で二人の学生
同じ誕生日がありますか？

855
00:37:11,010 --> 00:37:13,346
だから何があるのです。少数フント - 

856
00:37:13,346 --> 00:37:16,790
ここで、いくつかの200、300人
今日は自宅で百人。

857
00:37:16,790 --> 00:37:20,670
あなたは何自問したかったのであれば
二人の確率

858
00:37:20,670 --> 00:37:23,930
同じ誕生日を持つこの部屋で、
我々はこれを理解することができます。

859
00:37:23,930 --> 00:37:26,250
そして、私は2のある実際に主張する
同じ誕生日を持つ人々。

860
00:37:26,250 --> 00:37:29,560
>> 例えば、誰もいない
今日は誕生日を持っている？

861
00:37:29,560 --> 00:37:31,340
昨日？

862
00:37:31,340 --> 00:37:32,590
明日？

863
00:37:32,590 --> 00:37:35,980
私はつもりのように全ての権利は​​、ので、それは感じている
もっとこの363かそこらをしなければならないために

864
00:37:35,980 --> 00:37:39,500
時間は実際に把握する
我々がしなければ、衝突を持っている。

865
00:37:39,500 --> 00:37:42,350
または私達は単に数学的にこれを行うことが
よりもむしろうんざりするほど

866
00:37:42,350 --> 00:37:43,200
これを行う。

867
00:37:43,200 --> 00:37:44,500
そして次のことを提案する。

868
00:37:44,500 --> 00:37:48,740
>> だから私は、我々がモデル化できることを提案する
有する二人の確率

869
00:37:48,740 --> 00:37:55,320
1の確率と同じ誕生日
持つ誰のマイナス確率

870
00:37:55,320 --> 00:37:56,290
同じ誕生日。

871
00:37:56,290 --> 00:37:59,960
だから、これを取得するために、これはただです
ために、これを書いての派手な方法

872
00:37:59,960 --> 00:38:03,090
部屋の中で最初の人は、彼または彼女
可能性のいずれかを持つことができ

873
00:38:03,090 --> 00:38:07,370
誕生日は、年に365日と仮定して
を持つ人への謝罪と

874
00:38:07,370 --> 00:38:08,760
2月29日誕生日。

875
00:38:08,760 --> 00:38:13,470
>> だからこの部屋の最初の人は無料です
誕生日、任意の数を有すること

876
00:38:13,470 --> 00:38:18,280
出れるように365の可能性
我々は、365で365を割ったことをやる

877
00:38:18,280 --> 00:38:18,990
これは、一つです。

878
00:38:18,990 --> 00:38:22,700
部屋の中で次の人、もし目標
衝突を回避することである、唯一の缶

879
00:38:22,700 --> 00:38:26,460
どのように彼または彼女の誕生日を持っている
多くの異なる可能な日？

880
00:38:26,460 --> 00:38:27,610
364。

881
00:38:27,610 --> 00:38:31,430
したがって、この式の第二項である
本質的に私たちのためにその数学をやって

882
00:38:31,430 --> 00:38:33,460
一つの可能​​な休み減算することによって。

883
00:38:33,460 --> 00:38:36,390
そして次の日、次の日、
ダウン総数翌日

884
00:38:36,390 --> 00:38:38,100
部屋の中の人。

885
00:38:38,100 --> 00:38:41,290
>> そして我々はそれから考えれば、その後は何です
ていないこと誰も確率

886
00:38:41,290 --> 00:38:45,265
ユニークな誕生日が、再び1マイナス
、私たちが得ることは表現であること

887
00:38:45,265 --> 00:38:47,810
それはとてもすてきなことができます
このように見える。

888
00:38:47,810 --> 00:38:50,330
しかし、それはもっと面白い
視覚的に見ています。

889
00:38:50,330 --> 00:38:55,120
これは、x軸上でチャートである
部屋の中で人々の数は、

890
00:38:55,120 --> 00:38:56,180
誕生日の数。

891
00:38:56,180 --> 00:38:59,840
y軸上の確率である
衝突、2人

892
00:38:59,840 --> 00:39:01,230
同じ誕生日を持つ。

893
00:39:01,230 --> 00:39:05,020
>> そして、この曲線から持ち帰りです
とすぐに40を好きになるように

894
00:39:05,020 --> 00:39:11,110
学生は、あなたが90％の確率で上昇している
combinatorically 2の

895
00:39:11,110 --> 00:39:13,550
人以上持つ
同じ誕生日。

896
00:39:13,550 --> 00:39:18,600
そして、一度は、それが58人を好きになる
チャンス2のほぼ100％

897
00:39:18,600 --> 00:39:21,310
部屋の中の人々が持ってしようとしている
そこにもかかわらず、同じ誕生日、

898
00:39:21,310 --> 00:39:26,650
365または366可能バケット、および
部屋の中で唯一の58人。

899
00:39:26,650 --> 00:39:29,900
ただ、統計的には、になりそうだ
、衝突を取得している要するに

900
00:39:29,900 --> 00:39:31,810
この議論の動機。

901
00:39:31,810 --> 00:39:35,890
我々はここで空想取得し、たとえている
これらの鎖を有する開始、我々はまだだ

902
00:39:35,890 --> 00:39:36,950
衝突を持っているつもり。

903
00:39:36,950 --> 00:39:42,710
>> 質問を頼むように、何ですか
挿入と削除を行うための費用

904
00:39:42,710 --> 00:39:44,850
このようなデータ構造に？

905
00:39:44,850 --> 00:39:46,630
まあ私が提案してみましょう - 

906
00:39:46,630 --> 00:39:51,570
と私は上の画面に戻りましょう
ここで - 私たちは、の要素をn個した場合

907
00:39:51,570 --> 00:39:56,330
我々は、挿入しようとしているそうだとすればリスト、
n個の要素、そして我々は持っている

908
00:39:56,330 --> 00:39:58,050
どのように多くの合計バケット？

909
00:39:58,050 --> 00:40:03,450
31合計バケットを言ってみましょう
誕生日の場合には

910
00:40:03,450 --> 00:40:09,240
1の最大の長さは何ですか
潜在的にこれらの鎖の？

911
00:40:09,240 --> 00:40:12,670
>> 再び可能31がある場合
与えられた月の誕生日。

912
00:40:12,670 --> 00:40:14,580
そして、私たちはただみんなに凝集している - 

913
00:40:14,580 --> 00:40:15,580
実際には、愚かな例です。

914
00:40:15,580 --> 00:40:16,960
代わりに26をしてみましょう。

915
00:40:16,960 --> 00:40:20,890
実際に名前が人々を持っているのであれば
それによって与え、AからZで始まる

916
00:40:20,890 --> 00:40:22,780
当方26の可能性。

917
00:40:22,780 --> 00:40:25,920
そして、我々のようなデータ構造を使用している
我々は持っているそれによって我々はただ見て1、

918
00:40:25,920 --> 00:40:30,210
それぞれのポインタの配列、
リンクされたリストを指す

919
00:40:30,210 --> 00:40:32,360
最初のリストは誰です
名前アリスと。

920
00:40:32,360 --> 00:40:35,770
番目のリストは、すべてを使用することです
始まる、始まる名前

921
00:40:35,770 --> 00:40:36,980
Bと、などが挙げられる。

922
00:40:36,980 --> 00:40:41,020
>> それぞれの可能性が高い長さは何ですか
これらのリスト我々は良いクリーンを想定した場合

923
00:40:41,020 --> 00:40:45,410
AからZまでの名前の分布
全体のデータ構造全体で？

924
00:40:45,410 --> 00:40:50,210
データ構造におけるnの人々があります
彼らはうまくなら、26で割った値

925
00:40:50,210 --> 00:40:52,110
全体に広がる
データ構造。

926
00:40:52,110 --> 00:40:54,970
そこで、これらのそれぞれの長さ
チェーンは26で割ってnです。

927
00:40:54,970 --> 00:40:57,380
しかし、ビッグO記法で、それは何ですか？

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
本当にそれは何ですか？

930
00:41:02,440 --> 00:41:04,150
だから、右、本当にただNの？

931
00:41:04,150 --> 00:41:06,620
我々は過去に言ってきたので、
ぐふあなたは26で割ること。

932
00:41:06,620 --> 00:41:08,710
はい、現実には高速です。

933
00:41:08,710 --> 00:41:12,720
しかし、理論的には、それは基本的ではない
すべてが速くなります。

934
00:41:12,720 --> 00:41:16,040
>> だから我々はすべてそれほどしないと思われる
近いこの聖杯へ。

935
00:41:16,040 --> 00:41:17,750
実際には、これは単に線形時間である。

936
00:41:17,750 --> 00:41:20,790
てか、この時点では、なぜ我々はしないでください
ただ一つの巨大なリンクされたリストを使用するのか？

937
00:41:20,790 --> 00:41:23,510
なぜ我々は単に巨大なものを使用していない
の名前を格納する配列

938
00:41:23,510 --> 00:41:25,010
部屋に誰も？

939
00:41:25,010 --> 00:41:28,280
まあ、何かがまだある
ハッシュテーブルに関する説得力のある？

940
00:41:28,280 --> 00:41:30,810
説得力のある何かがまだある
データ構造について

941
00:41:30,810 --> 00:41:33,940
これのように見える？

942
00:41:33,940 --> 00:41:35,182
これ。

943
00:41:35,182 --> 00:41:37,050
>> 学生：[聞こえない]。

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1：それだけの権利、そして再び場合
線形時間アルゴリズム、および

945
00:41:39,840 --> 00:41:42,780
線形時間のデータ構造、なぜ私にはありません
ただビッグに全員の名前を格納し

946
00:41:42,780 --> 00:41:44,210
配列、または大きなリンクリストに？

947
00:41:44,210 --> 00:41:47,010
とCSはそんなに難しく停止
それは必要以上に？

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
でも、このことについて説得力のある何です
私はそれを傷付けず？

950
00:41:53,190 --> 00:41:54,930
>> 学生：[聞こえない]。

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1：挿入は、ないですか？

952
00:41:57,040 --> 00:41:58,140
もう高価。

953
00:41:58,140 --> 00:42:03,390
だから挿入は、潜在的にはまだ可能性
でも、あなたのデータがあれば、一定の時間が

954
00:42:03,390 --> 00:42:07,910
構造は、このような配列に見える
を指している、それぞれのポインタ、

955
00:42:07,910 --> 00:42:09,550
潜在的にリンクされたリスト。

956
00:42:09,550 --> 00:42:15,220
どのようにして定数を達成することができ
名前の時間挿入？

957
00:42:15,220 --> 00:42:16,280
右、前にそれを貼り付け？

958
00:42:16,280 --> 00:42:19,290
>> 我々はから設計目標を犠牲にする場合
以前、我々は維持したいところ

959
00:42:19,290 --> 00:42:22,650
例えば、みんなの名前、並べ替え、
やステージ上の数字のすべてが、並べ替え

960
00:42:22,650 --> 00:42:25,020
我々が持っていると仮定
ソートされていないリンクリスト。

961
00:42:25,020 --> 00:42:29,960
それだけ、私たちに1つまたは2つの手順がかかります
ベンとブライアンの場合​​のように

962
00:42:29,960 --> 00:42:32,750
以前、ある要素を挿入する
リストの先頭。

963
00:42:32,750 --> 00:42:36,090
我々はすべてのソートを気にしないのであれば
で始まる名前の、またはすべての

964
00:42:36,090 --> 00:42:39,660
Bで始まる名前は、我々はまだすることができます
一定時間の挿入を実現しています。

965
00:42:39,660 --> 00:42:43,900
今、アリスやボブまたは任意の名前をルックアップする
より一般的にはまだ何ですか？

966
00:42:43,900 --> 00:42:48,100
それは中に26で割った、nのビッグO、だ
皆が一様だ理想的なケース

967
00:42:48,100 --> 00:42:51,190
配布し、できるだけ多くののあるところ
Zの、おそらくであるがありますように

968
00:42:51,190 --> 00:42:52,220
非現実的。

969
00:42:52,220 --> 00:42:53,880
しかし、それはまだ直線です。

970
00:42:53,880 --> 00:42:57,120
>> しかし、ここで、我々はポイントに戻ってくる
という漸近表記

971
00:42:57,120 --> 00:42:58,600
理論的には真。

972
00:42:58,600 --> 00:43:02,960
しかし、現実の世界では、私はそれを主張する場合
私のプログラムでは、26回何かを行うことができます

973
00:43:02,960 --> 00:43:06,210
そのプログラムは、あなたよりも速く
あなたが使用して好むするつもりですか？

974
00:43:06,210 --> 00:43:09,660
ユアーズや鉱山、その
26倍の速さですか。

975
00:43:09,660 --> 00:43:14,320
現実的には、その人は26です
倍の速さも、理論的にはなら

976
00:43:14,320 --> 00:43:18,790
我々のアルゴリズムは同じで実行
漸近的な実行時間。

977
00:43:18,790 --> 00:43:20,940
>> 私は別のを提案してみましょう
完全に解決。

978
00:43:20,940 --> 00:43:24,380
そして、これはあなたの心を爆破していない場合、
私たちは、データ構造の外出。

979
00:43:24,380 --> 00:43:27,420
だから、これは、それはトライです - 

980
00:43:27,420 --> 00:43:28,520
愚かな名前の一種。

981
00:43:28,520 --> 00:43:32,880
それはリトリーバル、ワードから来ている
ためのトライ、T-R-I-eが綴られ

982
00:43:32,880 --> 00:43:34,450
コー​​スの検索はトライのように聞こえる。

983
00:43:34,450 --> 00:43:36,580
しかし、それは歴史だ
ワードトライの。

984
00:43:36,580 --> 00:43:40,980
>> だからトライは、確かに木のいくつかの種類です
そしてそれはまた、その単語に遊びだ。

985
00:43:40,980 --> 00:43:46,330
そして、あなたは非常にそれを見ることができないにもかかわらず、
この可視化と、トライです

986
00:43:46,330 --> 00:43:50,790
と家系図のようなツリー構造、
上部とたくさんの一つの祖先

987
00:43:50,790 --> 00:43:54,530
孫やひ孫の
としては底に残します。

988
00:43:54,530 --> 00:43:58,100
しかしトライの各ノードが配列です。

989
00:43:58,100 --> 00:44:00,680
そしてそれは、配列内のだ - としましょう
瞬間のために極端に単純 - それはだ

990
00:44:00,680 --> 00:44:04,600
サイズ26の配列、この場合には、どこ
各ノードは再びサイズの配列です

991
00:44:04,600 --> 00:44:09,000
26、その中でゼロ番目の要素
配列を表し、最後

992
00:44:09,000 --> 00:44:11,810
そのような各要素に
アレイは、Zを表し、

993
00:44:11,810 --> 00:44:15,520
>> だから私は、その後、提案することは、このデータ
トライとして知られている構造は、あり得る

994
00:44:15,520 --> 00:44:17,600
単語を格納するためにも使用する。

995
00:44:17,600 --> 00:44:21,740
我々はどのように格納することができた瞬間前に見ました
言葉、またはこの場合名に、そして我々

996
00:44:21,740 --> 00:44:25,440
、我々は数字を格納することができますどのように前に見た
しかし、我々は名前や文字列に焦点を当てている場合

997
00:44:25,440 --> 00:44:27,460
ここで、興味深い何気づく。

998
00:44:27,460 --> 00:44:32,210
私は名前マクスウェルであることを主張する
このデータ構造の内部。

999
00:44:32,210 --> 00:44:33,730
どこでマクスウェルを見ていますか？

1000
00:44:33,730 --> 00:44:35,140
>> 学生：[聞こえない]。

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1：左側に。

1002
00:44:36,240 --> 00:44:39,910
したがって、このデータで面白いものだ
構造は保存ではなく、ある

1003
00:44:39,910 --> 00:44:46,200
弦M-A-X-W-E-L-Lスラッシュゼロ、すべて
連続して、代わりに何をすべきか

1004
00:44:46,200 --> 00:44:46,890
以下の通りです。

1005
00:44:46,890 --> 00:44:50,510
これは、データ構造のようなトライである場合、
そのノードが再び配列ですそれぞれ、

1006
00:44:50,510 --> 00:44:54,650
そして、あなたはマクスウェルを保存したい、あなたの最初の
インデックスとそこそこrootのノード、

1007
00:44:54,650 --> 00:44:57,810
、最上位のノードを話すことを、
場所M、右、でとても

1008
00:44:57,810 --> 00:44:59,160
ほぼ真ん中に。

1009
00:44:59,160 --> 00:45:03,740
そしてそこから、あなたがフォロー
いわば子ノードへのポインタ。

1010
00:45:03,740 --> 00:45:06,150
だから家系の意味で、
あなたが下方それに従ってください。

1011
00:45:06,150 --> 00:45:09,030
そして、それは別のノードにあなたを導く
ですそこに左、上

1012
00:45:09,030 --> 00:45:10,540
ちょうど別の配列。

1013
00:45:10,540 --> 00:45:14,710
>> そしてあなたはマクスウェルを保存したい場合は、
あなたを表すポインタを見つける

1014
00:45:14,710 --> 00:45:16,430
ここではこの一つである、。

1015
00:45:16,430 --> 00:45:17,840
その後、次のノードに移動します。

1016
00:45:17,840 --> 00:45:20,100
と通知 - これはなぜ絵の
少し欺く - 

1017
00:45:20,100 --> 00:45:21,990
このノードは、小さなスーパーに見える。

1018
00:45:21,990 --> 00:45:26,050
しかし、これの右にYおよびZです
それは、単に著者が切り捨てただ

1019
00:45:26,050 --> 00:45:27,630
そのため、実際に絵
物事を見る。

1020
00:45:27,630 --> 00:45:30,400
そうでない場合、この絵
非常に広いでしょう。

1021
00:45:30,400 --> 00:45:36,180
その後場所Xにだから今は、インデックス、
その後、その後、その後W、その後E、L、L.何

1022
00:45:36,180 --> 00:45:37,380
この好奇心？

1023
00:45:37,380 --> 00:45:41,250
>> さて、私たちは新たなこの種のを使用している場合
文字列を格納する方法を取る

1024
00:45:41,250 --> 00:45:44,500
データ構造、まだする必要が
基本的にデータのチェックをオフ

1025
00:45:44,500 --> 00:45:47,250
言葉はここで終了する構造。

1026
00:45:47,250 --> 00:45:50,830
換言すれば、これらのノードのそれぞれにおいて
何とか我々ことを覚えておく必要があります

1027
00:45:50,830 --> 00:45:53,500
実際にこれらのポインタのすべての指示に従い
と少しを残している

1028
00:45:53,500 --> 00:45:58,370
このここに下部にパン粉
M-A-X-W-E-L-Lを示す構造である

1029
00:45:58,370 --> 00:46:00,230
実際にこのデータ構造である。

1030
00:46:00,230 --> 00:46:02,040
>> だから私たちは次のようにこれを行うことがあります。

1031
00:46:02,040 --> 00:46:06,810
我々だけで画像内の各ノード
鋸れる1個、大きさ27の配列を有している。

1032
00:46:06,810 --> 00:46:10,550
電話で、6を設定しているため、それが、今では27だ
私たちは、実際にあなたにアポストロフィをしてあげる、

1033
00:46:10,550 --> 00:46:13,590
ので、オライリーのような名前を持つことができます
アポストロフィと、その他。

1034
00:46:13,590 --> 00:46:14,820
しかし、同じアイデア。

1035
00:46:14,820 --> 00:46:17,710
のそれらの各要素
構造体の配列を指し

1036
00:46:17,710 --> 00:46:19,320
ノード、これだけノード。

1037
00:46:19,320 --> 00:46:21,430
だから、これは非常に彷彿とさせる
当社の連結リストの。

1038
00:46:21,430 --> 00:46:24,550
>> そして私は、ブールを持っている私はよ
だけであることを行っている単語を、呼び出し

1039
00:46:24,550 --> 00:46:29,120
本当の言葉はこの時点で終了した場合
ツリー内のノード。

1040
00:46:29,120 --> 00:46:32,870
それは効果的に少しを表し
三角形の我々は少し前を見た。

1041
00:46:32,870 --> 00:46:37,190
言葉はでそのノードで終わるのであれば
木、その単語フィールドは、trueになります

1042
00:46:37,190 --> 00:46:41,990
概念的にはオフのチェック、またはされている
私たちは、はいそこに、この三角形を描画している

1043
00:46:41,990 --> 00:46:44,080
ここでの言葉です。

1044
00:46:44,080 --> 00:46:45,120
>> だから、これはトライです。

1045
00:46:45,120 --> 00:46:48,540
そして今の質問は、何ですか
その稼働時間は？

1046
00:46:48,540 --> 00:46:49,930
それは、nのビッグOはありますか？

1047
00:46:49,930 --> 00:46:51,410
それは何か他のものはありますか？

1048
00:46:51,410 --> 00:46:57,330
さて、あなたは、このデータに名前をnとした場合
構造、マクスウェルは、ただ一つである

1049
00:46:57,330 --> 00:47:02,330
それらの実行時間とは何か
挿入またはマクスウェルを見つける？

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
実行時間は何ですか
マクスウェルを挿入する？

1052
00:47:09,050 --> 00:47:11,740
nを他の名前があ​​ったら
すでにテーブルに？

1053
00:47:11,740 --> 00:47:12,507
うん？

1054
00:47:12,507 --> 00:47:15,429
>> 学生：[聞こえない]。

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1：ええ、それは長さだ
名前の、右？

1056
00:47:17,550 --> 00:47:24,420
だからM--X-W-E-L-Lには、このように感じているので、
アルゴリズムは、7の大Oです。

1057
00:47:24,420 --> 00:47:26,580
さて、もちろん、名前
長さが異なります。

1058
00:47:26,580 --> 00:47:27,380
多分それは短い名前です。

1059
00:47:27,380 --> 00:47:28,600
多分それは長い名前です。

1060
00:47:28,600 --> 00:47:33,390
しかし、ここで重要なのは、つまり
それは定数です。

1061
00:47:33,390 --> 00:47:36,810
そして多分それは、実際には一定ではありません
しかし神、現実的であれば、内

1062
00:47:36,810 --> 00:47:41,570
辞書には、いくつかの制限がおそらくあり
の文字の数に

1063
00:47:41,570 --> 00:47:43,820
特定の国の人の名前。

1064
00:47:43,820 --> 00:47:46,940
>> そして我々はそれを引き受けることができ
この値は定数である。

1065
00:47:46,940 --> 00:47:47,750
私はそれが何であるかわからない。

1066
00:47:47,750 --> 00:47:50,440
それはおそらくより大きいです
我々は、それがあると思います。

1067
00:47:50,440 --> 00:47:52,720
いくつかのコーナーは常にあるので、
クレイジー長い名前の場合。

1068
00:47:52,720 --> 00:47:56,360
だからK呼び出してみましょう、それはまだだ
定数おそらく、すべての原因

1069
00:47:56,360 --> 00:48:00,190
少なくとも世界で名前、
特定の国では、その長さまたは

1070
00:48:00,190 --> 00:48:01,780
短いので、それは一定だ。

1071
00:48:01,780 --> 00:48:04,490
しかし、我々は言ってきたときに何かが大きい
定数値のO、何だという

1072
00:48:04,490 --> 00:48:07,760
と本当に同等？

1073
00:48:07,760 --> 00:48:10,420
それは実際には同じことだ
時定数を言うように。

1074
00:48:10,420 --> 00:48:11,530
>> 今我々は、不正行為の一種だよね？

1075
00:48:11,530 --> 00:48:15,340
我々はいくつかの理論を活用しての一種だ
ここでよく、kの順序があることを言うこと

1076
00:48:15,340 --> 00:48:17,450
本当にただ、1の順
そしてそれは時定数です。

1077
00:48:17,450 --> 00:48:18,200
しかし、それは本当にです。

1078
00:48:18,200 --> 00:48:22,550
ここで重要な洞察力であるため、その
我々はこれで既に名前がnしている場合

1079
00:48:22,550 --> 00:48:26,010
データ構造、そして我々はマクスウェルを挿入し、
それが私たちに必要な時間の量です

1080
00:48:26,010 --> 00:48:29,530
影響を受けるすべてでマクスウェルを挿入
どのように多くの他の人々によって

1081
00:48:29,530 --> 00:48:31,100
データ構造にありますか？

1082
00:48:31,100 --> 00:48:31,670
していないようです。

1083
00:48:31,670 --> 00:48:36,280
私はこれに億以上の要素を持っていた場合
次にトライし、マクスウェルを挿入し、ある

1084
00:48:36,280 --> 00:48:38,650
彼はまったく影響を受けた？

1085
00:48:38,650 --> 00:48:39,050
いいえ。

1086
00:48:39,050 --> 00:48:42,950
そして、それはその日のデータを任意のとは違ってい
我々はこれまで見てきた構造が、どこに

1087
00:48:42,950 --> 00:48:46,820
アルゴリズムの実行時間です
どの程度の完全に独立して

1088
00:48:46,820 --> 00:48:51,430
ものがあるか、または存在していない
そのデータ構造である。

1089
00:48:51,430 --> 00:48:54,650
>> そしてこれはあなたが今ある支払うと
その意志Pセット6、のための機会

1090
00:48:54,650 --> 00:48:58,310
もう一度あなた自身を実装伴う
15万で読むスペルチェッカー、

1091
00:48:58,310 --> 00:49:01,050
言葉、最善の方法のことを格納する
必ずしも明白ではありません。

1092
00:49:01,050 --> 00:49:04,030
そして、私は見つけることを熱望してきたのに
聖杯は、私はしないでください

1093
00:49:04,030 --> 00:49:05,330
トライであることを主張する。

1094
00:49:05,330 --> 00:49:09,810
実際には、ハッシュテーブルは非常によくことがあり
はるかに効率的であることを証明する。

1095
00:49:09,810 --> 00:49:10,830
しかし、これらはただです - 

1096
00:49:10,830 --> 00:49:14,620
それは単に設計上の決定の一つだ
あなたは確認する必要があります。

1097
00:49:14,620 --> 00:49:18,920
>> しかし、最後にのがみましょう50かそこら
あるものを覗いて見て下さいする秒

1098
00:49:18,920 --> 00:49:22,190
先に来週、私たち遷移より
このコマンドラインから

1099
00:49:22,190 --> 00:49:26,220
物事のウェブ​​に、Cプログラムであれば世界
基づいており、PHPのような言語と

1100
00:49:26,220 --> 00:49:30,350
JavaScriptとインターネット自体、
あなたがしたHTTPなどのプロトコル、

1101
00:49:30,350 --> 00:49:32,870
何年も当たり前の
今では、すべてのほとんどの型付け

1102
00:49:32,870 --> 00:49:34,440
多分日、または見。

1103
00:49:34,440 --> 00:49:37,420
そして、私たちはピール背中に始めましょう
インターネットとは何かの層。

1104
00:49:37,420 --> 00:49:40,650
とコードは何ですかそれ
根底には、今日のツール。

1105
00:49:40,650 --> 00:49:43,230
ここで、このティーザーの50秒はそう。

1106
00:49:43,230 --> 00:49:46,570
私はネットの戦士たちを与える。

1107
00:49:46,570 --> 00:49:51,370
>> [ビデオの再生]

1108
00:49:51,370 --> 00:49:56,764
>>  - 彼はメッセージで来ました。

1109
00:49:56,764 --> 00:50:00,687
プロトコルはすべて彼自身で。

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
彼は、残酷なファイアウォールの世界に来た
思いやりルータ、および危険遠く

1112
00:50:19,780 --> 00:50:22,600
死よりも悪い。

1113
00:50:22,600 --> 00:50:23,590
彼は高速です。

1114
00:50:23,590 --> 00:50:25,300
彼は強いです。

1115
00:50:25,300 --> 00:50:27,700
彼はTCPIPです。

1116
00:50:27,700 --> 00:50:30,420
そして、彼は、あなたの住所を持っている。

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
ネットの戦士たち。

1119
00:50:34,590 --> 00:50:35,290
>> [ENDビデオ再生]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1：どのようにインターネットで
来週のように動作しなければならない。

1121
00:50:38,070 --> 00:50:40,406