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

2
00:00:00,500 --> 00:00:11,137
[音楽再生]

3
00:00:11,137 --> 00:00:12,220
DAVID J.マラン：すべての権利。

4
00:00:12,220 --> 00:00:13,950
これはCS50である。

5
00:00:13,950 --> 00:00:18,560
これは継続的な週5であり、私達
いくつかの良いニュースと悪いニュースがあります。

6
00:00:18,560 --> 00:00:21,140
だから、良いニュースは、そのCS50です
今週の金曜日が起動します。

7
00:00:21,140 --> 00:00:24,430
あなたは私たちに参加したい場合は、
ここで通常のURLに向かう。

8
00:00:24,430 --> 00:00:28,670
さらに良いニュース、無講義
今度の月曜日13日。

9
00:00:28,670 --> 00:00:31,970
やや少ないより良いニュース、
クイズゼロは次の水曜日です。

10
00:00:31,970 --> 00:00:33,840
詳細はことができます
ここで、次のURLで確認。

11
00:00:33,840 --> 00:00:36,340
そして、次の数日にわたる
私たちは、ブランクを埋めることでしょう

12
00:00:36,340 --> 00:00:39,234
部屋に関しては
私たちが予約しているであろう。

13
00:00:39,234 --> 00:00:41,400
よりよいニュースがあるということです
もちろん全体の評価である

14
00:00:41,400 --> 00:00:43,570
セッションは、この来る
夕方には月曜日。

15
00:00:43,570 --> 00:00:46,270
もちろんのにご注目
場所や詳細についてはウェブサイト。

16
00:00:46,270 --> 00:00:49,290
それにもかかわらずセクション
休日、また、同様に会う予定だ。

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
最高のニュースは、次の金曜日講義。

19
00:00:52,940 --> 00:00:56,220
だから、これは伝統の私たちです
シラバスに従って、持っている。

20
00:00:56,220 --> 00:00:58,100
それは素晴らしいことになるだろうJust--。

21
00:00:58,100 --> 00:01:02,510
あなたは、のようなものが表示されます
一定時間のデータ構造

22
00:01:02,510 --> 00:01:04,730
ハッシュテーブルと木と試みる。

23
00:01:04,730 --> 00:01:07,150
そして、私たちは誕生日の問題について話します。

24
00:01:07,150 --> 00:01:09,440
ものの全体の束
次の金曜日お待ちしています。

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
[OK]をクリックします。

27
00:01:12,200 --> 00:01:13,190
いずれにせよ。

28
00:01:13,190 --> 00:01:17,080
>> だから、私たちがしてきたことを思い出して
何、この絵に注力

29
00:01:17,080 --> 00:01:18,980
私たちのコンピュータのメモリの内部。

30
00:01:18,980 --> 00:01:22,875
だから、メモリやRAMはどこのプログラムです
あなたがそれらを実行している間に存在する。

31
00:01:22,875 --> 00:01:25,215
あなたはダブルクリックすると
いくつかのプログラムを実行するためのアイコン

32
00:01:25,215 --> 00:01:27,520
またはダブルクリック
いくつかのファイルを開くには、アイコンを、

33
00:01:27,520 --> 00:01:30,430
それはあなたのハードからロードされる
ドライブまたはソリッド·ステート·ドライブ

34
00:01:30,430 --> 00:01:34,190
RAM、ランダムアクセスメモリ内へ
電源がオフになるまで、それは、住んでいる

35
00:01:34,190 --> 00:01:36,700
ラップトップの蓋が閉じ
または、プログラムを終了します。

36
00:01:36,700 --> 00:01:38,960
>> 今では、メモリの
これは、おそらく持っている

37
00:01:38,960 --> 00:01:41,950
1ギガバイトこれらの日、2
ギガバイト、あるいははるかに、

38
00:01:41,950 --> 00:01:44,420
一般的にレイアウトされている
与えられたプログラムのための

39
00:01:44,420 --> 00:01:47,170
長方形のこの種の中で
概念モデル

40
00:01:47,170 --> 00:01:50,860
私たちは一番下のスタックを持っていることにより、
そして上部に他の原料の束。

41
00:01:50,860 --> 00:01:53,140
非常に上部にあるもの
私たちはこの絵で見てきた

42
00:01:53,140 --> 00:01:55,670
前決して語ら
いわゆるテキストセグメントである。

43
00:01:55,670 --> 00:01:58,419
テキストセグメントは変わった方法である
0と1を言うと

44
00:01:58,419 --> 00:02:01,150
実際のコンパイルされたプログラムを構成している。

45
00:02:01,150 --> 00:02:03,910
>> だから、ダブルクリックしたとき
お使いのMacまたはPC上のMicrosoft Word、

46
00:02:03,910 --> 00:02:08,030
あなたは、ドットを実行したときに、または上のマリオを大幅に削減
端末ウィンドウで、Linuxコンピュータ、

47
00:02:08,030 --> 00:02:12,460
構成する0と1
Wordやマリオが一時的に格納される

48
00:02:12,460 --> 00:02:16,610
いわゆるにおけるコンピュータのRAMに
特定のプログラムのためのテキストセグメント。

49
00:02:16,610 --> 00:02:19,080
その下には、初期化行く
および初期化されていないデータ。

50
00:02:19,080 --> 00:02:22,655
これは、グローバル変数のようなもので、
私たちはの多くを使用していないところで、

51
00:02:22,655 --> 00:02:24,910
しかし機会に私たちはき
グローバル変数を持っていた

52
00:02:24,910 --> 00:02:28,819
または静的に文字列を定義した
ハード "こんにちは"のような言葉を符号化されている

53
00:02:28,819 --> 00:02:31,860
ユーザーから取り込まれない
それはあなたのプログラムにハードコードされている。

54
00:02:31,860 --> 00:02:34,230
>> さて、下に下部に、私たち
いわゆるスタックを持っている。

55
00:02:34,230 --> 00:02:37,665
そしてスタックは、これまで、私たちはしてきた
目的のものを種類のご利用ですか？

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
のために使用されてスタックとは何ですか？

58
00:02:40,997 --> 00:02:41,160
うん？

59
00:02:41,160 --> 00:02:42,070
>> 聴衆：関数。

60
00:02:42,070 --> 00:02:43,320
>> DAVID J.マラン：関数については？

61
00:02:43,320 --> 00:02:44,980
機能のためにどのような意味で？

62
00:02:44,980 --> 00:02:48,660
>> 聴衆：あなたは関数を呼び出し、
引数はスタックにコピーされます。

63
00:02:48,660 --> 00:02:49,660
>> DAVID J.マラン：その通りです。

64
00:02:49,660 --> 00:02:52,650
あなたは、関数を呼び出すと、その
引数はスタックにコピーされます。

65
00:02:52,650 --> 00:02:56,330
だから、どんなのXまたはYのまたはAさんやBさんの
あなたが関数に渡していることを

66
00:02:56,330 --> 00:02:58,680
一時的に置かれる
いわゆるスタック、

67
00:02:58,680 --> 00:03:02,000
ただアネンバーグのような
食堂トレイ、また物事

68
00:03:02,000 --> 00:03:03,190
ローカル変数のように。

69
00:03:03,190 --> 00:03:06,290
もし、あなたのfoo関数またはスワップ
この関数はローカル変数を持っている、

70
00:03:06,290 --> 00:03:08,602
一時のように、これら二つの
スタックになってしまう。

71
00:03:08,602 --> 00:03:11,560
今、私たちは、についてはあまり話すことはありません
それらが、これらの環境変数

72
00:03:11,560 --> 00:03:15,690
一番下に私たちはしばらく前に見たとき、
私は1日にキーボードをいじくった

73
00:03:15,690 --> 00:03:20,050
と私は物事をアクセス開始
argvは100のargv千のような、

74
00:03:20,050 --> 00:03:22,320
ちょうど私が忘れてelements--
numbers--それ

75
00:03:22,320 --> 00:03:24,330
私がアクセスすることを想定していなかった。

76
00:03:24,330 --> 00:03:26,581
私たちは、いくつかのを見て始めた
画面上のファンキーなシンボル。

77
00:03:26,581 --> 00:03:28,330
これらは、いわゆるでした
環境変数

78
00:03:28,330 --> 00:03:32,390
のグローバル設定のような私
プログラムまたは自分のコンピュータのために、ではない

79
00:03:32,390 --> 00:03:37,090
最近に関係のない
私たちが議論したバグ、

80
00:03:37,090 --> 00:03:39,670
シェルショック、それはされています
かなりの数のコンピュータを苦しめる。

81
00:03:39,670 --> 00:03:42,960
>> さて最後に、今日の焦点が合って
私たちは最終的にはヒープ上になるでしょう。

82
00:03:42,960 --> 00:03:44,864
これは、メモリの別の塊です。

83
00:03:44,864 --> 00:03:47,030
そして、基本的にすべてこの
メモリは同じものです。

84
00:03:47,030 --> 00:03:48,040
これは、同じハードウェアだ。

85
00:03:48,040 --> 00:03:49,956
私達はちょうど一種のだ
異なるクラスタの治療

86
00:03:49,956 --> 00:03:51,460
異なる目的のためにバイト。

87
00:03:51,460 --> 00:03:56,540
ヒープはまた、どこになるだろう
あなたが要求した変数とメモリ

88
00:03:56,540 --> 00:03:58,810
オペレーティングシステムから
一時的に記憶される。

89
00:03:58,810 --> 00:04:01,890
>> しかし、問題の種類があります
ここでは、絵のように示唆している。

90
00:04:01,890 --> 00:04:05,261
私たちは、ソートのうちの2つを持っている
衝突しようとして出荷されます。

91
00:04:05,261 --> 00:04:08,010
あなたはより多くのを使用しているためのように
スタックの、そして私たちが今日見るように

92
00:04:08,010 --> 00:04:11,800
以降、あなたはより多くのを使用したよう
ヒープ、​​確かに悪いことが起こる可能性があります。

93
00:04:11,800 --> 00:04:15,054
実際には、それを誘導することができる
意図的または意図せず。

94
00:04:15,054 --> 00:04:16,970
最後のクリフハンガーだから
時間は、このプログラムでした、

95
00:04:16,970 --> 00:04:20,570
任意の機能を提供しなかった
実証する以外の目的

96
00:04:20,570 --> 00:04:24,750
どのように悪い男として、実際に取ることができます
誰かのプログラムのバグの利点

97
00:04:24,750 --> 00:04:28,460
プログラムあるいは引き継ぐ
コンピュータシステム全体またはサーバ。

98
00:04:28,460 --> 00:04:31,660
だから一見に簡単に、あなたは
一番下には、メインに気付く

99
00:04:31,660 --> 00:04:34,510
コマンドラインで取り
ARGVに従って引数。

100
00:04:34,510 --> 00:04:38,480
そして、関数fへの呼び出しを有し、
基本的に無名関数が呼び出さ

101
00:04:38,480 --> 00:04:40,250
F、それが[1]のargvを渡しています。

102
00:04:40,250 --> 00:04:43,960
>> だから、どのような言葉で、ユーザーの種類
このプログラムの名前の後にプロンプ​​ト、

103
00:04:43,960 --> 00:04:49,310
そして、この任意の関数まで
トップ、fは、文字列を取り込み、AKAのはchar *、

104
00:04:49,310 --> 00:04:51,720
私たちが議論し始めてきたように、
そしてそれだけで「バー」と呼んでいます

105
00:04:51,720 --> 00:04:53,310
しかし、私たちは何もそれを呼び出すことができます。

106
00:04:53,310 --> 00:04:57,470
そして、それは内部の宣言
F、文字の配列の

107
00:04:57,470 --> 00:04:59,930
12そのような文字C--呼んだ。

108
00:04:59,930 --> 00:05:03,580
>> 今、私は言っていた話による
先ほど、ここで、メモリ内の

109
00:05:03,580 --> 00:05:06,720
cは、またはそれらの12である
結局つもり文字？

110
00:05:06,720 --> 00:05:07,570
ただ明確にする。

111
00:05:07,570 --> 00:05:08,070
うん？

112
00:05:08,070 --> 00:05:08,590
>> 聴衆：スタック上。

113
00:05:08,590 --> 00:05:09,420
>> DAVID J.マラン：スタック上。

114
00:05:09,420 --> 00:05:10,720
だからcがローカル変数です。

115
00:05:10,720 --> 00:05:14,079
私たちは、12文字または12バイトを求めている。

116
00:05:14,079 --> 00:05:16,120
これらは結局しようとしている
いわゆるスタック上。

117
00:05:16,120 --> 00:05:18,530
今、最終的にこの他の関数である
それは、実際にはかなり便利だ

118
00:05:18,530 --> 00:05:20,571
私たちは、実際に使用されていませんでした
それ自身、strncopy。

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
これは、文字列のコピーを意味するが、
n個の文字、n文字だけ。

121
00:05:25,200 --> 00:05:31,990
だから、n文字は次のようになります。
Cにバーからコピー。

122
00:05:31,990 --> 00:05:32,980
そして、どのように多くの？

123
00:05:32,980 --> 00:05:34,110
バーの長さ。

124
00:05:34,110 --> 00:05:36,330
つまり、言い換えれば、そのように
一行、strncopy、

125
00:05:36,330 --> 00:05:39,500
コピーしようとしている
効果的にCへのバー。

126
00:05:39,500 --> 00:05:42,340
>> さて、だけの種類の予測する
この話の教訓、

127
00:05:42,340 --> 00:05:44,750
ここに潜在的に問題は何ですか？

128
00:05:44,750 --> 00:05:49,710
私たちは、長さをチェックしているにもかかわらず
バーとstrncopyにそれを渡し、

129
00:05:49,710 --> 00:05:53,145
あなたの腸はあなたに言って何をされている
まだこのプログラムについて壊れ？

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
うん？

132
00:05:55,220 --> 00:05:57,491
>> 聴衆：含まれていません
ヌル文字のための部屋。

133
00:05:57,491 --> 00:05:59,990
DAVID J.マラン：含まれていません
ヌル文字のための部屋。

134
00:05:59,990 --> 00:06:02,073
潜在的に、とは異なり
過去の練習私たちもしません

135
00:06:02,073 --> 00:06:04,810
持っているプラ​​ス1となるように多くの
そのヌル文字に対応しています。

136
00:06:04,810 --> 00:06:06,649
しかし、それはそれよりもさらに悪いです。

137
00:06:06,649 --> 00:06:07,940
他に何私たちは何を失敗している？

138
00:06:07,940 --> 00:06:08,432
うん？

139
00:06:08,432 --> 00:06:09,307
>> 聴衆：[聞き取れない]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J.マラン：パーフェクト。

142
00:06:16,440 --> 00:06:18,490
私たちは、ハードはかなり任意に12をコード化しました。

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
それはそんなにありません
問題が、実は

145
00:06:21,330 --> 00:06:25,630
私たちも、どうかをチェックしていないこと
バーの長さは、12未満である

146
00:06:25,630 --> 00:06:28,530
その場合、それはなるだろう
メモリに入れても安全

147
00:06:28,530 --> 00:06:30,260
私たちが割り当てられてきたというC。

148
00:06:30,260 --> 00:06:32,960
確かに、バーが似ている場合
20文字の長さ、

149
00:06:32,960 --> 00:06:39,010
この関数は、コピーされるようである
Cへのバーから20文字、それによって

150
00:06:39,010 --> 00:06:41,310
少なくとも8バイトを取る
それがあってはならないこと。

151
00:06:41,310 --> 00:06:42,690
それはここに意味です。

152
00:06:42,690 --> 00:06:44,347
>> ショート、壊れたプログラムでそう。

153
00:06:44,347 --> 00:06:45,180
大したことなどはありません。

154
00:06:45,180 --> 00:06:46,360
たぶん、あなたはセグメンテーションフォールトを取得します。

155
00:06:46,360 --> 00:06:47,651
私たちは、すべてのプログラムのバグを持っていた。

156
00:06:47,651 --> 00:06:50,196
私達はすべてのバグがあるかもしれません
今のプログラムで。

157
00:06:50,196 --> 00:06:51,320
しかし、意味するところは何ですか？

158
00:06:51,320 --> 00:06:54,390
さて、ここでのズームインされたバージョンです
私のコンピュータのメモリのその写真。

159
00:06:54,390 --> 00:06:56,230
これは私のスタックの最下部である。

160
00:06:56,230 --> 00:06:59,644
そして実際、一番下のものです
と呼ばれる親ルーチンのスタック、ファンシーな方法

161
00:06:59,644 --> 00:07:00,560
それがメインだと言っている。

162
00:07:00,560 --> 00:07:03,772
誰が関数を呼び出したように、
私たちが話をしているF。

163
00:07:03,772 --> 00:07:05,230
これは、スタックの最下部である。

164
00:07:05,230 --> 00:07:06,640
リターンアドレスは新しい何かである。

165
00:07:06,640 --> 00:07:08,810
それは常に、そこにあっただ
常にその絵にあった。

166
00:07:08,810 --> 00:07:10,440
私達はちょうどそれに注意を呼び出されることはありません。

167
00:07:10,440 --> 00:07:15,290
結局のところのでcが動作する方法です
1関数が別のを呼び出すときに、

168
00:07:15,290 --> 00:07:18,780
それだけでなく、引数を行う
関数がスタックにプッシュされます、

169
00:07:18,780 --> 00:07:22,470
だけではなく、関数のローカルを行う
変数はスタックにプッシュされます、

170
00:07:22,470 --> 00:07:26,820
リターンアドレスと呼ばれるもの
また、スタックに置かれます。

171
00:07:26,820 --> 00:07:33,330
具体的には、主通話がfooた場合、メインの
メモリ内の自分のアドレス、牛何か、

172
00:07:33,330 --> 00:07:38,240
効果的にスタックに置かれます
なるようにfはそれを実行して実行されたとき

173
00:07:38,240 --> 00:07:43,630
本文中にジャンプする場所を知っている
実行を継続するためには、セグメント。

174
00:07:43,630 --> 00:07:47,760
>> 私たちは、概念的にここにいるのであれば、
主に、それからfが呼び出されます。

175
00:07:47,760 --> 00:07:50,200
fは知ってどのように人
バックハンドコントロールへ？

176
00:07:50,200 --> 00:07:52,020
さて、この小さな
ここに赤でブレッドクラム、

177
00:07:52,020 --> 00:07:54,978
それだけで、リターンアドレスと呼ばれる
チェックし、そのリターンアドレスは何ですか？

178
00:07:54,978 --> 00:07:57,039
ああ、私はここに戻って主にジャンプしてみましょう。

179
00:07:57,039 --> 00:07:59,080
そして、それは少しだ
単純化の、

180
00:07:59,080 --> 00:08:00,750
0と1のため
主のために技術的にである

181
00:08:00,750 --> 00:08:01,967
ここではハイテク部門のアップ。

182
00:08:01,967 --> 00:08:03,800
しかし、それはアイデアだ。 F
ただ何を知っている必要があります

183
00:08:03,800 --> 00:08:06,680
コントロールが最終的に戻ってどこに行くに。

184
00:08:06,680 --> 00:08:09,790
>> しかしやり方コンピュータ
長いものを打ち出してきた

185
00:08:09,790 --> 00:08:12,320
ローカル変数のようにして
引数は、このようなものです。

186
00:08:12,320 --> 00:08:17,180
だから、この絵の上部の内
青いので、すべて、fに対するスタックフレームです

187
00:08:17,180 --> 00:08:19,630
メモリはf
特に使用しています。

188
00:08:19,630 --> 00:08:22,990
だからそれに応じて、ことに気づく
バーはこの絵にあります。

189
00:08:22,990 --> 00:08:23,980
バーでは、その引数だった。

190
00:08:23,980 --> 00:08:27,240
そして、私たちは主張し、引数にその
関数がスタックにプッシュされます。

191
00:08:27,240 --> 00:08:29,910
cは、もちろん、ある
また、この写真の。

192
00:08:29,910 --> 00:08:33,520
>> そして、ちょうど表記の目的のために、
左上隅に気付く

193
00:08:33,520 --> 00:08:37,020
Cブラケット0になるものであり、
その後、わずかに右にダウン

194
00:08:37,020 --> 00:08:38,220
C型ブラケット11である。

195
00:08:38,220 --> 00:08:41,240
換言すれば、あなたが想像することができます
バイトのグリッドがあること

196
00:08:41,240 --> 00:08:44,380
そこであり、そのうちの最初の
左上の底

197
00:08:44,380 --> 00:08:48,360
これらの12バイトの最後である。

198
00:08:48,360 --> 00:08:49,930
>> しかし、今早送りしてみてください。

199
00:08:49,930 --> 00:08:55,580
私たちは合格したらどうしようとは何ですか
cより長い文字列のバーにある？

200
00:08:55,580 --> 00:08:59,130
そして、私たちはどうかをチェックしていない
それは確かに長い12よりもだ。

201
00:08:59,130 --> 00:09:03,146
この写真のどの部分をしようとしている
バイト0、1、2、3で上書きされる、

202
00:09:03,146 --> 00:09:07,890
ドットドットドット、11、その後、
悪い、12、19を経て13？

203
00:09:07,890 --> 00:09:11,820
ここで何が起こるだろう、
あなたが発注から推測した場合

204
00:09:11,820 --> 00:09:14,790
そのCブラケット0が一番上にある
そしてcブラケット11は、ソー​​トのダウンしている

205
00:09:14,790 --> 00:09:15,812
右に？

206
00:09:15,812 --> 00:09:16,796
うん？

207
00:09:16,796 --> 00:09:19,260
>> 聴衆：まあ、それは起こっている
はchar *バーを上書きします。

208
00:09:19,260 --> 00:09:22,260
>> DAVID J.マラン：ええ、それがどのように見える
あなたは、char *バーを上書きするつもりだ。

209
00:09:22,260 --> 00:09:26,245
さらに悪いことには、本当に長いに送信する場合
文字列、あなたも何を上書きする可能性がありますか？

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
リターンアドレス。

212
00:09:28,570 --> 00:09:31,380
どの場合も、同じようにある
どこにプログラムに指示するためのブレッドクラム

213
00:09:31,380 --> 00:09:34,060
時Fに戻ります
呼び出されて実行されます。

214
00:09:34,060 --> 00:09:37,140
>> だから、悪者は一般的に何をすべきか
彼らはプログラムに遭遇した場合です。

215
00:09:37,140 --> 00:09:41,290
彼らはあるかどうか興味があること
そのような方法で悪用可能な、バギー

216
00:09:41,290 --> 00:09:43,550
彼または彼女は取ることができること
そのバグの利点、

217
00:09:43,550 --> 00:09:45,720
一般的に、彼らは得ることはありません
この権利は初めて。

218
00:09:45,720 --> 00:09:48,590
彼らはただ、たとえば、送信を開始し、
あなたのプログラムへのランダム文字列、

219
00:09:48,590 --> 00:09:50,260
キーボードであるかどうかにかかわらず、
または率直に彼らはおそらく

220
00:09:50,260 --> 00:09:52,740
小さなプログラムを書き込むだけで
自動的に文字列を生成、

221
00:09:52,740 --> 00:09:55,430
として、プログラムを叩い開始
異なる入力のロットで送る

222
00:09:55,430 --> 00:09:56,340
異なる長さで。

223
00:09:56,340 --> 00:09:58,990
>> とすぐにプログラムがクラッシュとして、
それは驚くべきことだ。

224
00:09:58,990 --> 00:10:01,020
それは彼が意味しているので
または彼女が発見した

225
00:10:01,020 --> 00:10:02,660
何が実際にはおそらくバグです。

226
00:10:02,660 --> 00:10:05,830
そして、彼らはより巧妙な取得することができます
そしてより狭く焦点を開始

227
00:10:05,830 --> 00:10:07,420
そのバグを悪用する方法について。

228
00:10:07,420 --> 00:10:11,480
特に、どのような彼または彼女がかもしれない
何こんにちは、最良の場合には、送信される。

229
00:10:11,480 --> 00:10:12,210
大したことはありません。

230
00:10:12,210 --> 00:10:14,750
それは十分に短いです文字列です。

231
00:10:14,750 --> 00:10:18,100
しかし彼または彼女が送信した場合、
私たちは、それを一般化するようにします

232
00:10:18,100 --> 00:10:20,890
攻撃はそのようにゼロをcode--
そして物事を行うものは

233
00:10:20,890 --> 00:10:25,150
RM-RFのように、すべてのものを削除し、その
ハードドライブから、またはスパムを送信

234
00:10:25,150 --> 00:10:27,000
または何らかの方法でマシンを攻撃？

235
00:10:27,000 --> 00:10:29,570
>> これらの各もしそうであれば
文字Aはちょうど表し

236
00:10:29,570 --> 00:10:32,380
概念的には、攻撃、攻撃、
攻撃、攻撃、いくつかの悪いコード

237
00:10:32,380 --> 00:10:36,410
他の誰かが書いたことが、
その人は十分にスマートである場合

238
00:10:36,410 --> 00:10:40,790
全て含めるだけでなく、
これらのRM-RFのではなく、

239
00:10:40,790 --> 00:10:46,100
彼または彼女の最後の数バイトを持っている
対応する番号であること

240
00:10:46,100 --> 00:10:50,540
彼のアドレスに
自身の攻撃コード

241
00:10:50,540 --> 00:10:53,820
彼または彼女はちょうどに合格したことを
プロンプトを提供することによって、

242
00:10:53,820 --> 00:10:58,760
あなたが効果的にコンピュータをだましことができます
fを実行して完了したときに気付いへ、

243
00:10:58,760 --> 00:11:02,400
ああ、それは私がジャンプするための時間です
バック赤いリターンアドレスへ。

244
00:11:02,400 --> 00:11:06,070
しかし、彼または彼女は何とか持っているので
そのリターンアドレスを重複し

245
00:11:06,070 --> 00:11:09,602
自分の番号を持つ、
彼らは十分にスマートだ

246
00:11:09,602 --> 00:11:11,560
ことを設定しているために
あなたのように、参照するための番号

247
00:11:11,560 --> 00:11:13,740
スーパートップに表示
そこ左隅、

248
00:11:13,740 --> 00:11:18,020
コンピュータの中に実際のアドレス
彼らの攻撃コードのいくつかのメモリ、

249
00:11:18,020 --> 00:11:21,740
悪者は、コンピュータをだましことができ
彼または彼女自身のコードを実行中に。

250
00:11:21,740 --> 00:11:23,700
>> そして、そのコードは、再び、何もすることができます。

251
00:11:23,700 --> 00:11:26,120
これは、一般的に呼ばれています
ただでシェルコード、

252
00:11:26,120 --> 00:11:29,030
そうでないと言っての道
一般的にRM-RFのような単純なもの。

253
00:11:29,030 --> 00:11:32,340
これは、実際にはBashのようなものだ、
または実際のプログラムは彼を与えること

254
00:11:32,340 --> 00:11:37,230
または彼女のプログラム制御に実行する
彼らがしたいことを何か他のもの。

255
00:11:37,230 --> 00:11:40,210
だから要するに、このすべて
単純な事実から派生

256
00:11:40,210 --> 00:11:44,490
関係するこのバグはチェックしていないこと
ご使用のアレイの境界。

257
00:11:44,490 --> 00:11:47,250
そして、方法が原因
コンピュータの仕事は、彼らということです

258
00:11:47,250 --> 00:11:49,430
からスタックを使用
効果的に、概念的には、

259
00:11:49,430 --> 00:11:54,830
アップの一番下のが、その後の要素
あなたは、トップダウンで育てるスタックにプッシュする

260
00:11:54,830 --> 00:11:56,624
これは信じられないほど問題がある。

261
00:11:56,624 --> 00:11:58,290
さて、この問題を回避する方法があります。

262
00:11:58,290 --> 00:12:00,800
そして、率直に言って、言語があります
これでこの問題を回避します。

263
00:12:00,800 --> 00:12:03,100
Javaは、例えば、免疫がある
この特定の問題に。

264
00:12:03,100 --> 00:12:04,110
彼らはあなたのポインターを与えていないからです。

265
00:12:04,110 --> 00:12:05,943
彼らはあなたを与えていない
ダイレクト·メモリ·アドレス。

266
00:12:05,943 --> 00:12:08,560
私たちが持っているこの力を持つので、
メモリには何も触れ

267
00:12:08,560 --> 00:12:11,580
私たちは確かに、大きなリスク、来たいと思います。

268
00:12:11,580 --> 00:12:12,430
>> だから目を光らせる。

269
00:12:12,430 --> 00:12:14,596
ヶ月で、率直に言って、もし
または今後数年間は、いつでも

270
00:12:14,596 --> 00:12:17,740
あなたは、いくつかの搾取について読む
プログラムやサーバーの、

271
00:12:17,740 --> 00:12:22,370
あなたは今まで何かのヒントを表示された場合
バッファオーバーフロー攻撃のように、

272
00:12:22,370 --> 00:12:25,390
またはスタックオーバーフローは、別のタイプです
攻撃の、基本的に変わるところ、

273
00:12:25,390 --> 00:12:28,770
ウェブサイトのを鼓舞とほとんど
あなたがそれを知っていれば、名前を付け、

274
00:12:28,770 --> 00:12:33,170
それはすべてただの話だ
いくつかの文字のサイズをオーバーフロー

275
00:12:33,170 --> 00:12:36,200
配列や、より一般的にいくつかの配列。

276
00:12:36,200 --> 00:12:38,822
これについて、次にご質問、、？

277
00:12:38,822 --> 00:12:39,780
自宅でこれをしようとしないでください。

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> かしこまりました。

280
00:12:42,300 --> 00:12:47,270
これまでの私たちの新しいそれでmalloc関数であった
その中で友人たちはメモリを割り当てることができます

281
00:12:47,270 --> 00:12:50,540
私たちは、必ずしも中知らないこと
私たちが持っていないので、することを進める

282
00:12:50,540 --> 00:12:52,920
私たちの中にハードコードする
12のようなプログラム番号。

283
00:12:52,920 --> 00:12:55,550
ユーザーは、どのくらいのを教えてくれるたら
彼または彼女が入力したいデータ、

284
00:12:55,550 --> 00:12:58,000
私たちは、その多くのメモリをmallocをすることができます。

285
00:12:58,000 --> 00:13:01,484
>> だから、malloc関数にはに、判明
私たちはそれを使用してきた程度は、

286
00:13:01,484 --> 00:13:03,900
明示的に最後の時間、その後、
あなたたちはそれを使用している

287
00:13:03,900 --> 00:13:08,160
のために無意識のうちにgetString用
数週間、malloc関数のメモリのすべて

288
00:13:08,160 --> 00:13:09,820
いわゆるヒープから来ている。

289
00:13:09,820 --> 00:13:13,852
そして、これは、たとえば、なぜのgetStringです
動的にメモリを割り当てることができます

290
00:13:13,852 --> 00:13:16,060
あなたがしているかを知らなくても
事前に入力しようとして、

291
00:13:16,060 --> 00:13:21,520
手あなたに戻っそのメモリへのポインタ、
そのメモリは、まだあなたのものに保つことである、

292
00:13:21,520 --> 00:13:24,080
でもリターンをのgetStringた。

293
00:13:24,080 --> 00:13:27,450
そのため、リコール後にすべてのこと
スタックは常に、上下に起こっている

294
00:13:27,450 --> 00:13:27,950
上下に。

295
00:13:27,950 --> 00:13:30,230
そして、すぐにそれが行くように
ダウン、それは任意のメモリを意味し、

296
00:13:30,230 --> 00:13:33,030
使用されるこの機能はず
他人が使用することはできませ。

297
00:13:33,030 --> 00:13:34,570
現在では、ごみ値です。

298
00:13:34,570 --> 00:13:36,120
>> しかし、ヒープがここにある。

299
00:13:36,120 --> 00:13:39,360
そして、何のmallocの良いのはということです
malloc関数は、ここでメモリを割り当てる場合、

300
00:13:39,360 --> 00:13:42,070
それがために、影響を受けないです
スタックによる大部分は、。

301
00:13:42,070 --> 00:13:46,000
だから任意の関数にアクセスすることができます
mallocされていますメモリ、

302
00:13:46,000 --> 00:13:49,120
さえのgetStringなどの機能により、
た後でも、それが返されます。

303
00:13:49,120 --> 00:13:51,700
>> さて、malloc関数の逆は無料です。

304
00:13:51,700 --> 00:13:53,900
そして実際、ルールあなた
採用開始する必要があります

305
00:13:53,900 --> 00:13:58,950
いずれかの、いずれかの、あなたはmalloc関数を使用するすべての時間がある
あなた自身は、最終的には、無料で使用する必要があります

306
00:13:58,950 --> 00:14:00,280
その同じポインタについて。

307
00:14:00,280 --> 00:14:03,289
私たちが書いているこのすべての時間
多くの理由のためのバギー、バギーコード、。

308
00:14:03,289 --> 00:14:05,580
しかしの一つであった
CS50ライブラリを使用して、どの

309
00:14:05,580 --> 00:14:09,010
自身が意図的である
バギーは、メモリリークが発生します。

310
00:14:09,010 --> 00:14:11,410
あなたはgetStringメソッドと呼んでいるときはいつでも
過去数週間で

311
00:14:11,410 --> 00:14:13,870
私たちは、動作を求めている
メモリのためのシステム、Linuxでは、。

312
00:14:13,870 --> 00:14:15,780
そして、あなたは、一度戻ってそれを与えたことがありません。

313
00:14:15,780 --> 00:14:17,730
そして、これはで、ではありません
実際、良いこと。

314
00:14:17,730 --> 00:14:20,330
>> そして、Valgrindの、一
のPset 4で導入ツール、

315
00:14:20,330 --> 00:14:22,900
すべてのあなたを助けることについてです
今そのようなバグを見つける。

316
00:14:22,900 --> 00:14:27,060
しかし、ありがたいことのPset 4のためにあなたがする必要はありません
CS50ライブラリまたはにgetStringを使用します。

317
00:14:27,060 --> 00:14:31,220
だから、メモリに関連するバグがある
最終的には自分自身のことになるだろう。

318
00:14:31,220 --> 00:14:34,060
>> だから、malloc関数は単なる以上のものです
この目的のために便利。

319
00:14:34,060 --> 00:14:37,420
私たちは、実際には現在、解決することができます
根本的に異なる問題、

320
00:14:37,420 --> 00:14:41,640
そして基本的に多くの問題を解決
効果的に、0週目の約束に従って。

321
00:14:41,640 --> 00:14:44,720
これまでのところ、これは最もセクシーです
私たちが持っていたデータ構造。

322
00:14:44,720 --> 00:14:47,804
そして、データ構造によって私はちょうど意味
概念化メモリの道

323
00:14:47,804 --> 00:14:50,720
ただ言っ超えた形で、
これは、これはchar型で、intです。

324
00:14:50,720 --> 00:14:52,930
私たちは、物事を一緒にクラスタ化を開始することができます。

325
00:14:52,930 --> 00:14:54,460
>> だから、配列はこのように見えた。

326
00:14:54,460 --> 00:14:57,270
約における重要なものだった
アレイは、それはあなたを与えるということです

327
00:14:57,270 --> 00:14:59,724
バック·トゥ·バックの塊
メモリ、これらのそれぞれ

328
00:14:59,724 --> 00:15:02,765
同じタイプのものであることを行っている、int型、
int型、int型、int型、またはchar、char型、char型、

329
00:15:02,765 --> 00:15:03,330
チャー。

330
00:15:03,330 --> 00:15:04,496
しかし、いくつか欠点があります。

331
00:15:04,496 --> 00:15:06,570
これは、例えば、ある
サイズ6の配列。

332
00:15:06,570 --> 00:15:10,650
あなたが6で、この配列を埋めるとします
数字その後、何らかの理由で、

333
00:15:10,650 --> 00:15:13,187
ユーザーは、提供したいと考えて
あなた七番号。

334
00:15:13,187 --> 00:15:14,020
あなたはそれをどこに置けばいいの？

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> あなたが持っている場合解決策は何だ
スタック上の配列を作成し、

337
00:15:18,990 --> 00:15:22,030
例えば、ちょうど一週間で
私たちが導入された2つの表記法、

338
00:15:22,030 --> 00:15:23,730
内部番号の角括弧の？

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
さて、あなたは6を持っている
これらのボックス内の番号。

341
00:15:27,260 --> 00:15:28,530
あなたの本能は何でしょうか？

342
00:15:28,530 --> 00:15:29,973
どこにそれを置くしたいですか？

343
00:15:29,973 --> 00:15:30,860
>> 聴衆：[聞き取れない]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J.マラン：申し訳ありません？

345
00:15:31,315 --> 00:15:32,380
>> ユーザ：エンド​​の上に置きます。

346
00:15:32,380 --> 00:15:33,796
>> DAVID J.マラン：最後にそれを入れてください。

347
00:15:33,796 --> 00:15:35,880
だから上の右に、
この箱の外側。

348
00:15:35,880 --> 00:15:38,710
どのいいだろうが、それ
あなたがそれを行うことはできませんが判明した。

349
00:15:38,710 --> 00:15:41,350
あなたが尋ねていないてしまった場合のため
このメモリチャンクの、

350
00:15:41,350 --> 00:15:44,490
それはこのことを偶然かもしれない
いくつかの他の変数によって使用されている

351
00:15:44,490 --> 00:15:45,030
完全に。

352
00:15:45,030 --> 00:15:49,210
私たちが置かれたときに一週間かそこらバックだと思う
Zamylaとデーヴィンアウトとゲイブの名称

353
00:15:49,210 --> 00:15:49,930
メモリ内の。

354
00:15:49,930 --> 00:15:51,638
彼らは文字通りだった
背中合わせにバックアップします。

355
00:15:51,638 --> 00:15:53,550
だから私たちは必ずしもできない
その何でものを信頼

356
00:15:53,550 --> 00:15:55,800
私が使用するためにここの上で利用可能です。

357
00:15:55,800 --> 00:15:56,990
>> だから、他に何をするかもしれない？

358
00:15:56,990 --> 00:16:00,282
さて、一度あなたを実現
サイズ7の配列を必要とする、

359
00:16:00,282 --> 00:16:02,490
あなただけの作成することができます
サイズ7の配列は、次に使用する

360
00:16:02,490 --> 00:16:05,950
ループまたはwhileループの、
新しい配列にコピーし、

361
00:16:05,950 --> 00:16:09,680
した後、何とかちょうど取り除く
この配列は、またはそれを使用して停止します。

362
00:16:09,680 --> 00:16:12,130
しかし、それは、特に効率的ではありません。

363
00:16:12,130 --> 00:16:15,340
要するに、配列はさせてください
あなたが動的にサイズを変更します。

364
00:16:15,340 --> 00:16:17,900
>> だから一方ではあなたが得る
すごいランダムアクセス、。

365
00:16:17,900 --> 00:16:20,108
それは、私たちは物事を行うことができますので
分割統治のような、

366
00:16:20,108 --> 00:16:23,100
私たちがしたそのすべてが二分探索、
ここで画面上にについて話しました。

367
00:16:23,100 --> 00:16:24,950
しかし、あなたは隅に自分を描く。

368
00:16:24,950 --> 00:16:27,810
とすぐにヒットとして
あなたの配列の末尾、

369
00:16:27,810 --> 00:16:29,980
あなたは非常にをしなければならない
高価な操作

370
00:16:29,980 --> 00:16:33,910
またはコードの全体の束を書く
今その問題に対処する。

371
00:16:33,910 --> 00:16:36,680
>> だからではなく、あれば私たちは持っていたもの
何かがリストと呼ばれる

372
00:16:36,680 --> 00:16:38,820
または特にリンクリスト？

373
00:16:38,820 --> 00:16:41,930
どのような場合の代わりになる
矩形は、バックアップするバックアップするバックアップ

374
00:16:41,930 --> 00:16:45,730
私たちは少し離れる長方形を持つ
それらの間での余地のビット？

375
00:16:45,730 --> 00:16:49,670
そして、私はこれを描いたにも関わらず、
画像またはこの写真を適応

376
00:16:49,670 --> 00:16:54,696
テキストのいずれかからここに戻ってのためであると
後ろ現実には、非常に整然としたバックアップする、

377
00:16:54,696 --> 00:16:56,820
これらの長方形の1
ここまでメモリ内である可能性があります。

378
00:16:56,820 --> 00:16:58,028
そのうちの一つはここにある可能性があります。

379
00:16:58,028 --> 00:17:00,420
そのうちの一つは、ここまでとすることができ、
こっちなどが挙げられる。

380
00:17:00,420 --> 00:17:02,910
>> しかし、私たちが描いた場合、
この場合、矢印

381
00:17:02,910 --> 00:17:05,650
それは何とかこれらをリンク
四角形一緒に？

382
00:17:05,650 --> 00:17:08,170
確かに、私たちは技術的に見てきました
矢印の化身。

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
私たちは、最近に使用されている
、そのフードの下に日、

385
00:17:13,710 --> 00:17:15,210
矢印の代表である？

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
ポインタ、右か？

388
00:17:17,349 --> 00:17:19,780
>> それではもし、代わりに
数字だけを格納し、

389
00:17:19,780 --> 00:17:23,130
様9、17、22、26、34、
私たちではありません格納されている場合は、

390
00:17:23,130 --> 00:17:27,079
数が、ポインタのみ
このような各番号の横に？

391
00:17:27,079 --> 00:17:30,690
だから、ずっとあなたがスレッドになるように
生地の全体の束を通して針、

392
00:17:30,690 --> 00:17:32,950
何とか同点物事
一緒に、同じようにすることができます

393
00:17:32,950 --> 00:17:35,550
ポインタを持つ私たちは、として
ここに矢印で転生、

394
00:17:35,550 --> 00:17:38,550
一緒に織りの種類
これらの個別の矩形

395
00:17:38,550 --> 00:17:41,780
効果的に、ポインタを使用して
その各番号の横に

396
00:17:41,780 --> 00:17:46,065
そのいくつかの次の番号を指し、
ポイントには、順番に、いくつかの次の番号？

397
00:17:46,065 --> 00:17:47,940
そのように、換言すれば、どのような
私たちは実際たい場合

398
00:17:47,940 --> 00:17:49,820
このような何かを実装するには？

399
00:17:49,820 --> 00:17:53,610
さて、残念ながら、これらは長方形、
9との少なくとも一方、17、22において、

400
00:17:53,610 --> 00:17:57,040
など、これらはもはやありません
単一番号で素敵な正方形。

401
00:17:57,040 --> 00:17:59,960
ボトム、四角形
9以下、例えば、

402
00:17:59,960 --> 00:18:04,330
どうあるべきかを表す
32ビットのポインタである。

403
00:18:04,330 --> 00:18:09,460
今、私はまだ、任意のデータ型を認識していないよ
C言語でそれはあなただけでなく、int型を提供します

404
00:18:09,460 --> 00:18:11,630
しかしポインタ完全に。

405
00:18:11,630 --> 00:18:15,020
>> だから、私たちが望む場合は、解決策は何ですか
これに対する私たち自身の答えを発明するには？

406
00:18:15,020 --> 00:18:15,760
うん？

407
00:18:15,760 --> 00:18:16,640
>> 聴衆：[聞き取れない]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J.マラン：それは何ですか？

409
00:18:17,360 --> 00:18:17,880
>> 聴衆：新構造。

410
00:18:17,880 --> 00:18:19,590
>> DAVID J.マラン：ええ、なぜ
私たちは、新しい構造を作成しないでください

411
00:18:19,590 --> 00:18:20,920
またはC言語で、構造体？

412
00:18:20,920 --> 00:18:25,990
私たちは、もし簡単に、前に構造体を見てきました
私たちは学生の構造を扱っ場所

413
00:18:25,990 --> 00:18:27,780
このように、名前と家を持っていた人。

414
00:18:27,780 --> 00:18:31,980
のPset 3ブレイクアウトでは、全体の使用
structs-- GRectとGOvalsの束

415
00:18:31,980 --> 00:18:34,810
スタンフォードは、作成していること
一緒にクラスタ情報。

416
00:18:34,810 --> 00:18:38,580
それでは、私たちはこれと同じ考え方を取る場合
キーワード「型定義」と「構造体」

417
00:18:38,580 --> 00:18:42,890
した後、一部の学生に固有のもの、
そして、次にこれを進化さ：

418
00:18:42,890 --> 00:18:46,210
されている構造体node--とノードのtypedef
ただ、非常に汎用的なコンピュータサイエンス

419
00:18:46,210 --> 00:18:49,980
データ構造内の何かのための用語、
データ構造内のコンテナ。

420
00:18:49,980 --> 00:18:53,900
私が主張するノードが持っているとしている
全く単純なint型のnを、

421
00:18:53,900 --> 00:18:58,810
した後、もう少しひそかに、
この二行目は、次の構造体ノード*。

422
00:18:58,810 --> 00:19:01,300
しかし、あまり技術的な観点から、
その二行目は何ですか

423
00:19:01,300 --> 00:19:02,980
中括弧内のコードの？

424
00:19:02,980 --> 00:19:03,737
うん？

425
00:19:03,737 --> 00:19:04,851
>> 聴衆：[聞き取れない]

426
00:19:04,851 --> 00:19:06,600
DAVID J.マラン：
別のノードへのポインタ。

427
00:19:06,600 --> 00:19:09,910
だから確かに、少し不可解な構文。

428
00:19:09,910 --> 00:19:13,250
しかし、あなたは文字通り、それを読めば、
次の変数の名前です。

429
00:19:13,250 --> 00:19:14,410
そのデータ型は何ですか？

430
00:19:14,410 --> 00:19:18,206
それは、今回は少し冗長だ
それは*型の構造体ノードのだ。

431
00:19:18,206 --> 00:19:22,960
私たちは、何かの星を見てきたときはいつでも、その
それは、そのデータ型へのポインタであることを意味します。

432
00:19:22,960 --> 00:19:26,810
だから次は明らかである
構造ノードへのポインタ。

433
00:19:26,810 --> 00:19:28,310
>> ここで、構造体のノードは何ですか？

434
00:19:28,310 --> 00:19:31,044
さて、あなたはそれらを参照してください気付く
右上の同じ言葉。

435
00:19:31,044 --> 00:19:33,960
そして実際、あなたはまた、単語を参照してください。
ダウンここで左下にある「ノード」。

436
00:19:33,960 --> 00:19:35,640
そして、これは実際には便利です。

437
00:19:35,640 --> 00:19:39,930
私たちの学生の定義の中のことに注意してください
一度だけ単語 "学生"はあります。

438
00:19:39,930 --> 00:19:42,510
そして、それは学生ためだ
オブジェクトは、自己参照はありませんでした。

439
00:19:42,510 --> 00:19:45,340
学生の内側は何もありません
それはまた別の生徒をポイントする必要があり、

440
00:19:45,340 --> 00:19:45,610
persay。

441
00:19:45,610 --> 00:19:47,630
それは一種のだろう
現実の世界で奇妙な。

442
00:19:47,630 --> 00:19:50,880
>> しかし、内のノードとリンク
リストは、ノードをしたいですか

443
00:19:50,880 --> 00:19:53,970
類似のオブジェクトへの参照であると。

444
00:19:53,970 --> 00:19:57,900
だから、ここで変更はありません気づく
中括弧の内側だけで何だ。

445
00:19:57,900 --> 00:20:00,800
しかし、私たちは「ノード」という言葉を追加
一番上にあるだけでなく、

446
00:20:00,800 --> 00:20:02,930
一番下に追加する
の代わりに "学生。"

447
00:20:02,930 --> 00:20:06,000
そして、これは唯一の技術的な詳細です
データ構造は、再び、そのよう

448
00:20:06,000 --> 00:20:11,380
、自己参照することができるように
ノードは、別のそのようなノードを指すことができます。

449
00:20:11,380 --> 00:20:13,840
>> だから、これは最終的には何ですか
私たちのために意味するつもり？

450
00:20:13,840 --> 00:20:17,560
さて、1、このようなものの内側
私達のノードの内容である。

451
00:20:17,560 --> 00:20:19,360
ここまでこの事、
右上、ちょうどそうです

452
00:20:19,360 --> 00:20:20,860
それは、再び、私たちは自分自身を参照することができます。

453
00:20:20,860 --> 00:20:23,401
そして最も外側のもの、
ノードは、新しい用語であるにもかかわらず、

454
00:20:23,401 --> 00:20:25,500
多分、それはまだだ
学生とものと同じ

455
00:20:25,500 --> 00:20:27,520
SPLでのフードの下にあった。

456
00:20:27,520 --> 00:20:31,095
>> だから私たちは今を開始したい場合
このリンクリストを実装し、

457
00:20:31,095 --> 00:20:33,220
どのように翻訳することがあります
コー​​ドにこのような何か？

458
00:20:33,220 --> 00:20:35,350
さて、ちょうど見てみましょう
そのプログラムの一例

459
00:20:35,350 --> 00:20:36,840
実際にリンクされたリストを使用しています。

460
00:20:36,840 --> 00:20:40,870
今日の流通コードのうち、
リストゼロと呼ばれるプログラムです。

461
00:20:40,870 --> 00:20:44,980
私はこれを実行する場合、私は、スーパーを作成
シンプルなGUI、グラフィカル·ユーザー·インターフェース、

462
00:20:44,980 --> 00:20:46,460
それは本当にただのprintfです。

463
00:20:46,460 --> 00:20:50,930
そして今、私は自分自身にいくつかのメニューを与えてくれた
options--削​​除、挿入、検索、

464
00:20:50,930 --> 00:20:51,750
とトラバース。

465
00:20:51,750 --> 00:20:52,630
そして、終了します。

466
00:20:52,630 --> 00:20:55,970
これらは、上だけで一般的な操作である
リンクリストとして知られているデータ構造。

467
00:20:55,970 --> 00:20:58,409
>> 今、しようとしているの削除
リストから番号を削除します。

468
00:20:58,409 --> 00:21:00,200
インサートを追加しようとしています
リストへの番号。

469
00:21:00,200 --> 00:21:02,181
Searchは見に行くされている
リスト内の番号の。

470
00:21:02,181 --> 00:21:04,930
トラバースは変わった方法である
というのは、リストの中を歩く、

471
00:21:04,930 --> 00:21:06,245
それをプリントアウトするが、それはそれだ。

472
00:21:06,245 --> 00:21:07,720
どのような方法でそれを変更しないでください。

473
00:21:07,720 --> 00:21:08,570
>> それでは、これを試してみましょう。

474
00:21:08,570 --> 00:21:10,160
それでは先に行くと2を入力してみましょう。

475
00:21:10,160 --> 00:21:12,710
そして私はするつもりだ
番号を挿入する、9は言う。

476
00:21:12,710 --> 00:21:13,620
入力してください。

477
00:21:13,620 --> 00:21:17,480
そして今、私のプログラムはただです
と言うようにプログラムされ、リストが9である。

478
00:21:17,480 --> 00:21:20,190
今、私は先に行く場合には
、再び挿入してみましょうか

479
00:21:20,190 --> 00:21:23,680
私は先に行くと、ズームアウトして17を入力します。

480
00:21:23,680 --> 00:21:25,770
今私のリストは、17 9です。

481
00:21:25,770 --> 00:21:27,750
私は再び挿入して行うと、のいずれかを飛ばしてみましょう。

482
00:21:27,750 --> 00:21:32,400
代わりに、私たちがした絵に従って22の
ここを見てされて、私は先にジャンプしてみましょう

483
00:21:32,400 --> 00:21:34,630
そして、次の26を挿入します。

484
00:21:34,630 --> 00:21:36,230
だから私は、26を入力するつもりです。

485
00:21:36,230 --> 00:21:37,755
私が期待するようにリストである。

486
00:21:37,755 --> 00:21:40,630
しかし、今、ちょうどこのコードかどうかを確認します
柔軟であることを行っている、今私をしましょう

487
00:21:40,630 --> 00:21:43,520
少なくともタイプ22、
概念的に、私たちはなら

488
00:21:43,520 --> 00:21:46,520
確かにある、ソートされ、これを維持する
今は別の目標になるだろう、

489
00:21:46,520 --> 00:21:48,690
17と26の間に行く必要があります。

490
00:21:48,690 --> 00:21:50,270
だから私はEnterキーを押します。

491
00:21:50,270 --> 00:21:51,380
確かに、それが動作します。

492
00:21:51,380 --> 00:21:54,950
だから今私は挿入せ
最後、絵、34あたり。

493
00:21:54,950 --> 00:21:55,450
>> かしこまりました。

494
00:21:55,450 --> 00:21:58,980
だから、今の私にはそれを明記しましょう
削除し、トラバースして検索が行う、

495
00:21:58,980 --> 00:21:59,760
実際には、働いています。

496
00:21:59,760 --> 00:22:04,180
私が検索を実行しないと実際には、、してみましょう
番号22を検索し、入力します。

497
00:22:04,180 --> 00:22:05,010
それは22を発見した。

498
00:22:05,010 --> 00:22:07,580
だから、何これです
プログラムリストゼロません。

499
00:22:07,580 --> 00:22:10,230
>> しかし、何が実際に起こっている
その上で、これは実装して？

500
00:22:10,230 --> 00:22:14,530
さて、最初に私が持っている、と確かに可能性があります
私は、list0.hというファイルを持っています。

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
そして、これがあるとどこかで
行、typedefは、構造ノード、

503
00:22:20,690 --> 00:22:24,850
その後私は、私の中括弧、int型nを持ち、
その後、定義したものをstruct--？

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
次の構造体ノード。

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
だから私たちは星を必要としています。

508
00:22:31,045 --> 00:22:33,420
今、技術的に私たちは入る
ここでそれを描くのが習慣。

509
00:22:33,420 --> 00:22:35,670
あなたは教科書を参照してください可能性があり、
オンラインの参照があり、それを行う。

510
00:22:35,670 --> 00:22:36,660
それは機能的に同等です。

511
00:22:36,660 --> 00:22:37,980
実際には、これは、もう少し一般的である。

512
00:22:37,980 --> 00:22:40,563
しかし、私は何と一致しているだろう
私たちは前回を行なったし、これを行う。

513
00:22:40,563 --> 00:22:42,350
そして最後に、私はこれを行うつもりです。

514
00:22:42,350 --> 00:22:45,550
>> ヘッダファイル中のSO
list0.hのどこか、

515
00:22:45,550 --> 00:22:49,200
本日、この構造体の定義である、
そしておそらくいくつかの他のもの。

516
00:22:49,200 --> 00:22:52,580
一方list0cにあります
いくつかのことになるだろう。

517
00:22:52,580 --> 00:22:54,740
しかし、私たちはただになるだろう
開始し、これを終了しない。

518
00:22:54,740 --> 00:22:59,690
List0.hは私が欲しいファイルである
私のCファイルに含める。

519
00:22:59,690 --> 00:23:03,910
そして、いくつかの点で私は今
無効メインint型を、持っているつもり。

520
00:23:03,910 --> 00:23:06,530
そして私はするつもりだ
しなければならないこと、いくつかはここにあります。

521
00:23:06,530 --> 00:23:10,620
私も持っているつもりです
プロトタイプ、ボイド、検索、int型のように、

522
00:23:10,620 --> 00:23:13,610
その目的は生活の中ではn、
要素を検索します。

523
00:23:13,610 --> 00:23:18,310
そして、ダウンここに私が主張
今日のコード、空所、検索、int型、nは、

524
00:23:18,310 --> 00:23:21,020
セミコロンないが、オープン中括弧。

525
00:23:21,020 --> 00:23:25,049
そして今、私は何とか検索したい
このリスト内の要素の。

526
00:23:25,049 --> 00:23:27,340
しかし、私たちは十分に持っていない
まだ画面の情報。

527
00:23:27,340 --> 00:23:29,800
私は実際に持っていない
リスト自体を表していた。

528
00:23:29,800 --> 00:23:33,070
私たちが実装できるので、1つの方法
プログラム内のリンクリスト

529
00:23:33,070 --> 00:23:37,520
私はこの種の何かをしたいている
宣言のようにここにリストがリンクアップ。

530
00:23:37,520 --> 00:23:40,520
簡単にするために、私はするつもりだ
このグローバル、たとえ一般われわれ中

531
00:23:40,520 --> 00:23:41,645
このあまりすべきではない。

532
00:23:41,645 --> 00:23:43,260
しかし、それはこの例を単純化します。

533
00:23:43,260 --> 00:23:45,890
だから私は宣言したい
ここにリンクされたリストアップ。

534
00:23:45,890 --> 00:23:47,010
今、私はそれをどのように行うのでしょうか？

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> ここにリンクされたリストの写真です。

537
00:23:50,750 --> 00:23:53,030
そして、私は本当にない
どの瞬間に知っている

538
00:23:53,030 --> 00:23:56,710
私が代表に取り掛かるつもりだ
ひとつでたくさんのこと

539
00:23:56,710 --> 00:23:58,040
メモリ内の変数。

540
00:23:58,040 --> 00:23:59,160
しかし、背中の瞬間だと思います。

541
00:23:59,160 --> 00:24:00,830
私たちが持っていたこのすべての時間
私たちは、その後、文字列、

542
00:24:00,830 --> 00:24:02,913
の配列であることが明らかに
文字、その、私たち

543
00:24:02,913 --> 00:24:05,740
ただポインタであることが明らかに
最初の文字へ

544
00:24:05,740 --> 00:24:08,890
文字の配列内の
それがnullで終了だ。

545
00:24:08,890 --> 00:24:13,530
そのロジックによると、これにそう
自分の考えを播種のピクチャ種類、

546
00:24:13,530 --> 00:24:17,964
私たちは実際に私たちに何を書き込む必要が
リンクリストを表現するためのコード？

547
00:24:17,964 --> 00:24:21,130
どのくらいこの情報の私たちが必要なのです
Cコードでキャプチャするには、次のように言うでしょうか？

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
うん？

550
00:24:23,154 --> 00:24:24,738
>> 聴衆：私たちは、ノードへのポインタを必要としています。

551
00:24:24,738 --> 00:24:26,237
DAVID J.マラン：ノードへのポインタ。

552
00:24:26,237 --> 00:24:29,320
具体的には、どのノードがあなたのだろう
本能はへのポインタを保持すること？

553
00:24:29,320 --> 00:24:30,026
>> 聴衆：最初のノード。

554
00:24:30,026 --> 00:24:31,942
>> DAVID J.マラン：ええ、
たぶん最初。

555
00:24:31,942 --> 00:24:34,030
そして、第1に気付く
ノードは、異なる形状である。

556
00:24:34,030 --> 00:24:37,690
これは、構造体の唯一の半分の大きさですが、
ので、それは確かにポインタだけだ。

557
00:24:37,690 --> 00:24:44,650
だから、実際に何ができるかを宣言です
型ノードであるとリンクリスト*。

558
00:24:44,650 --> 00:24:47,780
そして、ちょうど最初にそれを呼ぶことにしましょう
ヌルに初期化。

559
00:24:47,780 --> 00:24:49,910
だからヌル、もう一度、来ている
ここに絵に。

560
00:24:49,910 --> 00:24:53,620
ヌル特殊な等として使用されるだけでなく、
のgetStringのようなものの戻り値

561
00:24:53,620 --> 00:24:57,770
とmalloc関数は、nullもゼロである
ポインタは、ポインタの欠如、

562
00:24:57,770 --> 00:24:58,430
可能ならば。

563
00:24:58,430 --> 00:25:00,309
それはちょうど何もまだここにないことを意味します。

564
00:25:00,309 --> 00:25:02,100
さて、最初に私がいたかもしれない
これは何と呼ばれる。

565
00:25:02,100 --> 00:25:04,200
私は、「リスト」と呼んでいる可能性が
または他のものの任意の数。

566
00:25:04,200 --> 00:25:06,960
しかし、私はそのように「最初」と呼んでいます
この絵でそれラインアップ。

567
00:25:06,960 --> 00:25:10,280
だから文字列のように表すことができ、
その最初のバイトのアドレスと、

568
00:25:10,280 --> 00:25:11,280
そうリンクリストができます。

569
00:25:11,280 --> 00:25:13,480
そして、私たちは、他のデータが表示されます
構造が表現され

570
00:25:13,480 --> 00:25:16,700
ちょうど1ポインタで、
32ビットの矢印、ポインティング

571
00:25:16,700 --> 00:25:18,740
構造的には非常に最初のノードで。

572
00:25:18,740 --> 00:25:20,340
>> しかし、今のは、問題を予測してみましょう。

573
00:25:20,340 --> 00:25:23,230
私は覚えていた場合
私のプログラム内のアドレス

574
00:25:23,230 --> 00:25:27,220
最初のノードの、最初の
このデータ構造矩形、

575
00:25:27,220 --> 00:25:31,760
何が良いの約ケースでいた
私のリストの残りの部分の実装？

576
00:25:31,760 --> 00:25:35,820
起こっているキー詳細は何ですか
これは実際に動作することを確認するには？

577
00:25:35,820 --> 00:25:39,250
そして、私は「実際に動作する」ことで
多くの文字列のように、意味、

578
00:25:39,250 --> 00:25:42,180
私たちは最初の文字から行くことができます
第二にデーヴィンの名前に、

579
00:25:42,180 --> 00:25:44,755
第三に、へ
最後の最後に、第四、

580
00:25:44,755 --> 00:25:47,880
私たちは最後にいるとき、どのように知っていますか
このようになりますリンクリストの？

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
た場合は、nullです。

583
00:25:50,660 --> 00:25:53,640
そして、私は、この種の表現だ
電気技師のかもしれないよう、

584
00:25:53,640 --> 00:25:56,420
少しアース付き
ある種のシンボル、。

585
00:25:56,420 --> 00:25:58,246
しかし、それはただ、この場合にはnullを意味します。

586
00:25:58,246 --> 00:26:00,370
あなたはそれを任意の数を描くことができます
いくつかの方法が、この作者

587
00:26:00,370 --> 00:26:02,800
ここにこのシンボルを使用するように起こった。

588
00:26:02,800 --> 00:26:06,260
>> 私たちは糸引きしているものであれば
これらのノードのすべて一緒に、

589
00:26:06,260 --> 00:26:08,600
場所だけ覚えて
最初のものは、とても長いです

590
00:26:08,600 --> 00:26:11,760
私たちは時に特殊記号を置くように
リスト内の最後のノードが、

591
00:26:11,760 --> 00:26:15,130
それだから、私たちは、ヌルを使用します
私たちは私たちが利用できる持っているもの、

592
00:26:15,130 --> 00:26:16,480
このリストは完全である。

593
00:26:16,480 --> 00:26:20,190
そして、私は唯一にあなたのポインタを与える場合でも、
最初の要素、あなた、プログラマ、

594
00:26:20,190 --> 00:26:22,486
確かにそれの残りの部分にアクセスすることができます。

595
00:26:22,486 --> 00:26:24,360
しかし、ここであなたの心を聞かせてみましょう
少しさまよい、

596
00:26:24,360 --> 00:26:26,140
彼らはすでにいないのであれば
かなり何wandered--

597
00:26:26,140 --> 00:26:28,723
の実行時間になるだろう
このリストには何も見つけられませんか？

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
それくそー、それは、nの大きなOはだ、
これは、公平で、悪いことではありません。

600
00:26:33,470 --> 00:26:34,800
しかし、それは線形である。

601
00:26:34,800 --> 00:26:37,980
私たちは、どのような機能をあきらめた
よりを移動させることにより、配列の

602
00:26:37,980 --> 00:26:43,130
動的にこの絵に向かって
一緒に織られたまたはリンクされたノードの？

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
私たちは、ラン​​ダムアクセスを与えてくれた。

605
00:26:46,687 --> 00:26:48,770
配列が原因いいです
数学的にすべてのもの

606
00:26:48,770 --> 00:26:50,340
背面にバックアップする背中合わせにある。

607
00:26:50,340 --> 00:26:52,370
でも、この絵も
きれいに見える、とさえ

608
00:26:52,370 --> 00:26:55,830
それはこれらのノードのように見えますが
うまく実際には、離間している

609
00:26:55,830 --> 00:26:56,830
彼らはどこにでもある可能性があります。

610
00:26:56,830 --> 00:27:01,590
OX1、OX50、Ox123、Ox99、これらの
ノードは、どこにでもある可能性があります。

611
00:27:01,590 --> 00:27:05,960
malloc関数はメモリを割り当てないため、
ヒープから、どこにでもヒープに。

612
00:27:05,960 --> 00:27:09,080
あなたは、必ずしもそれがだと知らない
背面に背中合わせになるだろう。

613
00:27:09,080 --> 00:27:12,460
そして、現実の中でそのようにこの絵
かなりこれはかなりあることを行っていない。

614
00:27:12,460 --> 00:27:16,140
>> だから、少しを取るつもりだ
この機能を実装するために働く。

615
00:27:16,140 --> 00:27:17,880
それでは、今の検索を実装してみましょう。

616
00:27:17,880 --> 00:27:20,250
そして、私たちはのようなものを表示されます
これを行うための巧妙な方法。

617
00:27:20,250 --> 00:27:24,660
私は、検索機能ですので、もしと
I変数、整数nを与えられている

618
00:27:24,660 --> 00:27:28,490
を探すために、私が知っている必要があります
内部検索するための新しい構文

619
00:27:28,490 --> 00:27:32,400
だ構造の
n個を見つけるために、と指摘した。

620
00:27:32,400 --> 00:27:33,210
それでは、これを実行しましょう​​。

621
00:27:33,210 --> 00:27:36,030
>> だから最初に私は行くつもりです
先にノードを宣言*。

622
00:27:36,030 --> 00:27:39,400
そして、私はそれを呼び出すつもりだ
ただ、慣例により、ポインタ、。

623
00:27:39,400 --> 00:27:41,710
そして、私は最初にそれを初期化するつもりです。

624
00:27:41,710 --> 00:27:43,770
そして今、私はこれを行うことができます
いくつかの方法で。

625
00:27:43,770 --> 00:27:45,436
しかし、私は一般的なアプローチを取るつもりです。

626
00:27:45,436 --> 00:27:50,180
ポインタが等しくないですが
ヌル、それは有効な構文です。

627
00:27:50,180 --> 00:27:54,550
そして、それはちょうどので、次の操作を行いますことを意味
限り、あなたは何を指していないよう。

628
00:27:54,550 --> 00:27:55,800
私は何をしたいですか？

629
00:27:55,800 --> 00:28:01,939
>> ポインタドットnの場合は、私が戻って来るように
そのため、equals--は何に等しい？

630
00:28:01,939 --> 00:28:03,105
どのような値私を探しています？

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
渡された実際のn。

633
00:28:06,590 --> 00:28:09,020
だからここにもう一つの特徴です
Cと多くの言語の。

634
00:28:09,020 --> 00:28:13,705
構造は、ノードと呼ばれるにもかかわらず
値nを有する、完全に正当な

635
00:28:13,705 --> 00:28:17,530
また、地元の引数を持っている
または変数は、nと呼ばれる。

636
00:28:17,530 --> 00:28:20,085
でも私たちは、とあるので
人間の目には、区別することができます

637
00:28:20,085 --> 00:28:22,087
このnがおそらくあることを
このnは異なる。

638
00:28:22,087 --> 00:28:23,420
構文は異なっているからです。

639
00:28:23,420 --> 00:28:26,211
あなたは、ドットとポインタを持っている、
これに対し、そのようなものを持っていません。

640
00:28:26,211 --> 00:28:27,290
だから、これはOKです。

641
00:28:27,290 --> 00:28:29,120
つまり、同じこと、それらを呼び出すためにOKです。

642
00:28:29,120 --> 00:28:32,380
>> 私はあなたがこれを見つけるしなければ、私は今
何かをしたいとして

643
00:28:32,380 --> 00:28:35,000
のような私たちは、nを見つけたことを発表。

644
00:28:35,000 --> 00:28:37,930
そして、私たちは、それを残しておきます
コメントや擬似コードコード。

645
00:28:37,930 --> 00:28:40,190
そうでなければ、そしてここにある
興味深い部分、何

646
00:28:40,190 --> 00:28:47,320
現在のノードかどうかはやってみたいん
私が気にn個を含有しないのですか？

647
00:28:47,320 --> 00:28:50,700
どのように私は次のことを実現するのですか？

648
00:28:50,700 --> 00:28:53,710
で私の指の場合
瞬間はPTRであり、それはだ

649
00:28:53,710 --> 00:28:55,920
何を指して
最初は、を指している

650
00:28:55,920 --> 00:28:59,290
どのように私は私の指を動かすん
コー​​ド内の次のノードに？

651
00:28:59,290 --> 00:29:01,915
さて、私たちがしているブレッドクラムは何ですか
この場合には従うつもり？

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
聴衆：[聞こえない]。

654
00:29:04,380 --> 00:29:05,630
DAVID J.マラン：うん、そう隣。

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
だから私は戻って私に行けば
ここでは、コード、確かに、私は

657
00:29:09,824 --> 00:29:12,990
、ポインタを先に行くと言おうとしている
それはだ単に一時的なvariable--です

658
00:29:12,990 --> 00:29:15,320
変な名前、PTRが、
それだけでtemp--ようなものだ

659
00:29:15,320 --> 00:29:19,234
私はポインタを設定するつもりだ
どのようなポインタに等しくis--

660
00:29:19,234 --> 00:29:22,150
そして、再び、これがあることを行っている
次moment--ドットのために少しバギー。

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
言い換えれば、私は私のを取るつもりだ
このノードを指しての指

663
00:29:26,550 --> 00:29:31,247
ここに私はあなたが知っている、と言うつもりです
何を、次のフィールドを見てみましょう

664
00:29:31,247 --> 00:29:33,330
とに指を動かす
それがで指して何でも。

665
00:29:33,330 --> 00:29:35,163
そして、これはしようとしている
繰り返し、繰り返し、繰り返し。

666
00:29:35,163 --> 00:29:37,630
しかし、ときに私の指を行います
まったく何をやって止める？

667
00:29:37,630 --> 00:29:40,095
とすぐにどのようなコードキックのラインのように？

668
00:29:40,095 --> 00:29:40,970
聴衆：[聞き取れない]

669
00:29:40,970 --> 00:29:43,060
DAVID J.マラン：もしポイントながら
ポインタはnullに等しいではありません。

670
00:29:43,060 --> 00:29:44,900
ある時点で私の指の
ヌルを指してするつもり

671
00:29:44,900 --> 00:29:47,070
と私は実現するつもりだ
それは、このリストの最後です。

672
00:29:47,070 --> 00:29:48,910
さて、これは少ない
簡単のために罪のない嘘。

673
00:29:48,910 --> 00:29:51,580
それも、私たちにもかかわらずことが判明
ちょうどこのドット表記法を学んだ

674
00:29:51,580 --> 00:29:55,220
構造に対して、ポインタ、構造体ではありません。

675
00:29:55,220 --> 00:29:56,580
PTRは何ですか？

676
00:29:56,580 --> 00:29:58,350
ただもっとせこいことです。

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
これは、ノードへのポインタです。

679
00:30:01,360 --> 00:30:03,120
これは、ノード自体ではありません。

680
00:30:03,120 --> 00:30:06,650
私はここには星がなかった場合は、ポインタ
それはノードのabsolutely--。

681
00:30:06,650 --> 00:30:08,650
これは週1のようなものです
変数の宣言、

682
00:30:08,650 --> 00:30:10,120
言葉「ノード」は新しく追加されていても。

683
00:30:10,120 --> 00:30:13,860
>> しかし、すぐに私たちが紹介するように
星は、今ノードへのポインタです。

684
00:30:13,860 --> 00:30:17,960
そして、残念ながらあなたが使用することはできません
ポインタのドット表記法。

685
00:30:17,960 --> 00:30:21,070
あなたは、矢印を使用する必要が
表記法、際立っている、、

686
00:30:21,070 --> 00:30:23,470
初めては、どの作品です
構文の直感的に見えます。

687
00:30:23,470 --> 00:30:25,245
これは文字通り、矢印のように見えます。

688
00:30:25,245 --> 00:30:26,370
だからそれは良いことだ。

689
00:30:26,370 --> 00:30:28,995
そして、ここでダウン、文字通り
矢印のように見えます。

690
00:30:28,995 --> 00:30:31,870
だから私はそれは私にはないla--だと思う
私はオーバーコミット私はhere--だと思う

691
00:30:31,870 --> 00:30:34,120
それは最後の新しい作品だと思う
構文の私たちは見ることになるだろう。

692
00:30:34,120 --> 00:30:36,500
そしてありがたいことに、それは確かだ
もう少し直感的。

693
00:30:36,500 --> 00:30:40,090
>> さて、あなたのそれらのために誰が
古い方法を好むかもしれないが、

694
00:30:40,090 --> 00:30:42,550
あなたはまだドット表記を使用することができます。

695
00:30:42,550 --> 00:30:45,380
しかし、月曜日のあたりなど
会話、まず

696
00:30:45,380 --> 00:30:50,530
それに行く、そこに行く必要がある
アドレスを入力し、[フィールドにアクセス。

697
00:30:50,530 --> 00:30:51,897
これはまた正しい。

698
00:30:51,897 --> 00:30:53,730
そして、率直に言って、これは
もう少し知識をひけらかす。

699
00:30:53,730 --> 00:30:56,530
あなたは文字通り言っている、間接参照
ポインタとそこに行く。

700
00:30:56,530 --> 00:30:59,320
その後.Nつかむ、フィールドは、nと呼ばれる。

701
00:30:59,320 --> 00:31:01,370
しかし、率直に言って、誰も望んでいない
入力するか、これを読んでいる。

702
00:31:01,370 --> 00:31:03,620
それで世界が発明した
矢印記法、これ

703
00:31:03,620 --> 00:31:06,980
同一の、同等であり、
それだけでシンタックスシュガーです。

704
00:31:06,980 --> 00:31:10,570
これを言ってはそう空想の方法
良く見える、またはより単純に見えます。

705
00:31:10,570 --> 00:31:12,296
>> だから今私は1つの他のことをするつもりです。

706
00:31:12,296 --> 00:31:15,420
私がしたら、「休憩」と言うつもりです
それので、私はそれを探して保管しないで発見した。

707
00:31:15,420 --> 00:31:17,620
しかし、これは要旨である
検索機能の。

708
00:31:17,620 --> 00:31:21,710
でしかし、それは、はるかに簡単です
最後に、コードをウォークスルーしない。

709
00:31:21,710 --> 00:31:25,570
これは確かに正式な実装である
今日の流通コードの検索の。

710
00:31:25,570 --> 00:31:30,530
私は挿入がないことをあえて言う
中を歩くのが特に楽しい

711
00:31:30,530 --> 00:31:33,180
視覚的に、またしても、削除
一日の終わりにも

712
00:31:33,180 --> 00:31:35,460
彼らはかなりまで煮詰める
シンプルなヒューリスティック。

713
00:31:35,460 --> 00:31:36,330
>> それでは、これを実行しましょう​​。

714
00:31:36,330 --> 00:31:39,250
あなたはここでユーモアに私を、私がやっただろう場合
ストレスボールの束を持って来る。

715
00:31:39,250 --> 00:31:40,620
私は数字の束を持って来た。

716
00:31:40,620 --> 00:31:46,562
そして、私たちは、わずか数人のボランティアを得ることができる
9、17、20、22、29、および34を表すため？

717
00:31:46,562 --> 00:31:48,270
だから、基本的に誰もが
誰が今日ここだ。

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
すなわち、一つ、二つ、三つだった
4、5、6人。

720
00:31:52,760 --> 00:31:55,740
そして、私はいや、見ることgo--するように求めてきた
後ろの1は彼らの手を発生させます。

721
00:31:55,740 --> 00:32:01,910
OK、一つ、二つ、三つ、四つ
five--私は6をbalance--ロードしましょう​​。

722
00:32:01,910 --> 00:32:03,051
[OK]を、あなた6アップ点灯。

723
00:32:03,051 --> 00:32:04,050
私たちは他の人が必要になります。

724
00:32:04,050 --> 00:32:05,460
私たちは余分なストレスボールを持って来た。

725
00:32:05,460 --> 00:32:08,200
そして、あなたができれば、のために
一瞬、ライン

726
00:32:08,200 --> 00:32:10,490
ただ自分アップ
ここで、この絵のように。

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> かしこまりました。

729
00:32:15,959 --> 00:32:17,125
あなたの名前は何、見てみましょう？

730
00:32:17,125 --> 00:32:17,550
>> 聴衆：アンドリュー。

731
00:32:17,550 --> 00:32:18,800
>> DAVID J.マラン：アンドリュー、
あなたは9番である。

732
00:32:18,800 --> 00:32:19,540
よろしくね。

733
00:32:19,540 --> 00:32:20,400
ほら

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
聴衆：ジェン。

736
00:32:22,176 --> 00:32:22,662
DAVID J.マラン：ジェン。

737
00:32:22,662 --> 00:32:23,162
デビッド。

738
00:32:23,162 --> 00:32:23,765
ナンバー17。

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
はい？

741
00:32:25,450 --> 00:32:26,400
>> 聴衆：私はジュリアです。

742
00:32:26,400 --> 00:32:26,980
>> DAVID J.マラン：ジュリア、デビッド。

743
00:32:26,980 --> 00:32:27,545
ナンバー20。

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
聴衆：クリスチャン。

746
00:32:29,340 --> 00:32:30,715
DAVID J.マラン：クリスチャン、デビッド。

747
00:32:30,715 --> 00:32:31,541
ナンバー22。

748
00:32:31,541 --> 00:32:32,040
と？

749
00:32:32,040 --> 00:32:32,649
>> 聴衆：JP。

750
00:32:32,649 --> 00:32:33,440
DAVID J.マラン：JP。

751
00:32:33,440 --> 00:32:34,880
ナンバー29。

752
00:32:34,880 --> 00:32:37,080
だから先に行くとああええとin--取得。

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uhオハイオ州。

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
スタンバイ。

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20。

759
00:32:42,390 --> 00:32:43,682
誰もが、マーカーを持っていますか？

760
00:32:43,682 --> 00:32:44,890
聴衆：私はシャーピーを持っている。

761
00:32:44,890 --> 00:32:45,660
DAVID J.マラン：あなたはシャーピーを得たか。

762
00:32:45,660 --> 00:32:46,159
[OK]をクリックします。

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
そして、誰もが一枚の紙がありますか？

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
講義を保存します。

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
さあ。

769
00:32:55,362 --> 00:32:56,320
聴衆：私たちはそれを持っている。

770
00:32:56,320 --> 00:32:57,600
DAVID J.マラン：私たちはそれを得た？

771
00:32:57,600 --> 00:32:58,577
すべての権利、ありがとうございました。

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
ここで私達は行く。

774
00:33:02,520 --> 00:33:03,582
これはあなたからでしたか？

775
00:33:03,582 --> 00:33:04,540
あなただけの一日保存した。

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
だから29。

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
かしこまりました。

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
私は29のスペルを間違えたが、[OK]をクリックします。

782
00:33:14,890 --> 00:33:15,720
どうぞ召しあがれ。

783
00:33:15,720 --> 00:33:18,114
すべての権利、私はあなたをあげる
バック一瞬ペン。

784
00:33:18,114 --> 00:33:19,280
だから私たちはここで、これらの人々を持っている。

785
00:33:19,280 --> 00:33:20,330
それでは、他のものを持ってみましょう。

786
00:33:20,330 --> 00:33:23,750
ゲイブは、あなたがプレイしたいですか
ここで最初の要素？

787
00:33:23,750 --> 00:33:25,705
私たちは、ポイントするように、あなたが必要です
これらの細かい人たちで。

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
したがって、9、17、20、22、ソート
29、次に34。

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
私たちは誰かを失うしましたか？

792
00:33:33,325 --> 00:33:33,950
私は34を持っている。

793
00:33:33,950 --> 00:33:36,730
34になりたい場合はdid-- OK、？

794
00:33:36,730 --> 00:33:37,605
[OK]を、34、アップ時に来る。

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
すべての権利、これは次のようになります。
クライマックス価値は十分。

797
00:33:41,220 --> 00:33:41,550
あなたの名前は？

798
00:33:41,550 --> 00:33:42,040
>> 聴衆：ピーター。

799
00:33:42,040 --> 00:33:43,456
>> DAVID J.マラン：ピーターは、アップ時に来る。

800
00:33:43,456 --> 00:33:46,810
すべての権利、とてもここにある
ノードの全体の束。

801
00:33:46,810 --> 00:33:49,060
あなたたちは、それぞれ表している
これらの四角形の一つ。

802
00:33:49,060 --> 00:33:51,930
そしてゲイブ、少し奇妙な
男アウトは、最初に表しています。

803
00:33:51,930 --> 00:33:54,850
だから、彼のポインタが少し小さくなっている
他のみんなよりも画面上で。

804
00:33:54,850 --> 00:33:58,120
この場合には、あなたのそれぞれは、左
手が、ダウン指すようにどちらかが起こっている

805
00:33:58,120 --> 00:34:01,085
それによって、そのように、nullを表す
単にポインタが存​​在しない場合、

806
00:34:01,085 --> 00:34:03,210
またはそれは指しているために起こっている
あなたの隣にノード。

807
00:34:03,210 --> 00:34:05,440
>> だから、今、あなたが飾る場合には
絵のような自分

808
00:34:05,440 --> 00:34:07,585
ここでは、先に行くとポイント
ゲイブと、お互いに

809
00:34:07,585 --> 00:34:11,030
における特定のポインティング中
リストを表現するための番号9。

810
00:34:11,030 --> 00:34:14,050
[OK]をクリックし、数34、左手
ただ床を指している必要があります。

811
00:34:14,050 --> 00:34:15,750
>> [OK]を、これはリンクされたリストである。

812
00:34:15,750 --> 00:34:17,580
これは、問題のシナリオがある。

813
00:34:17,580 --> 00:34:20,210
実際、これは、代表的
問題のクラスの

814
00:34:20,210 --> 00:34:21,929
あなたがコードで解決しようとする可能性がある。

815
00:34:21,929 --> 00:34:25,020
あなたが最終的に挿入したい
リストに新しい要素。

816
00:34:25,020 --> 00:34:27,494
この場合、私たちはするつもりだ
番号55を挿入してみてください。

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
しかし、あるように起こっている
考慮すべき別のケース。

819
00:34:30,860 --> 00:34:34,409
そして実際、これは1つになるだろう
全体像がここに持ち帰りの、ある、

820
00:34:34,409 --> 00:34:35,659
異なるケースは何ですか。

821
00:34:35,659 --> 00:34:39,120
もし異なる条件はどのようなものがありますか
あなたのプログラムが持っているかもしれない支店？

822
00:34:39,120 --> 00:34:42,024
>> さて、その数はあなたがしようとしている
私たちは55であることを今知って、挿入、

823
00:34:42,024 --> 00:34:44,650
しかし、あなたは知らなかった場合は、
事前に、私はあえて

824
00:34:44,650 --> 00:34:47,840
少なくとも三つに分類さ
考えられる状況。

825
00:34:47,840 --> 00:34:49,717
新しい要素はどこでしょうか？

826
00:34:49,717 --> 00:34:51,050
聴衆：そして最後または中間。

827
00:34:51,050 --> 00:34:54,150
DAVID J.マラン：最後に、中
中間、または冒頭に。

828
00:34:54,150 --> 00:34:56,650
だから私は、少なくともそこの主張
3つの問題が、私たちは、解決する必要があります。

829
00:34:56,650 --> 00:34:58,691
のは、おそらく何を選択しましょう
間違いなく最も簡単な

830
00:34:58,691 --> 00:35:01,090
1、どこに新しい要素を
初めに属します。

831
00:35:01,090 --> 00:35:04,040
だから私は非常にコードを持っているつもりです
私は書いた検索、などである。

832
00:35:04,040 --> 00:35:07,670
そして、私は、これPTRを持っているつもりです
私は私の指でここに表します

833
00:35:07,670 --> 00:35:08,370
いつものように。

834
00:35:08,370 --> 00:35:12,430
>> そして、どのような値を覚えている
私達はにptrを初期化したのですか？

835
00:35:12,430 --> 00:35:15,300
だから私たちは、最初はnullに初期化されました。

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
しかし、私たちは、かつて何をした
Googleの検索関数内でしたか？

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
私たちは、最初にそれが等しくなるように設定
これを行うことを意味しな​​い。

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
私が最初に等しくptrが設定されている場合、どのような
私の手は本当に指し示すすべきですか？

842
00:35:30,570 --> 00:35:31,070
右。

843
00:35:31,070 --> 00:35:33,290
ゲイブと私がしようとしているのであれば
ここに等しい値とすることで、

844
00:35:33,290 --> 00:35:34,760
私たちは数9の両方でポイントにする必要があります。

845
00:35:34,760 --> 00:35:36,420
>> だから、これは私たちの物語の始まりだった。

846
00:35:36,420 --> 00:35:38,700
そして今、これはただ単純である、
にもかかわらず、構文は新しく追加されました。

847
00:35:38,700 --> 00:35:40,580
概念的には、これは単なる線形探索である。

848
00:35:40,580 --> 00:35:42,750
9に等しい55ですか？

849
00:35:42,750 --> 00:35:45,559
というか、のは9よりも小さいとしましょう​​。

850
00:35:45,559 --> 00:35:47,600
私がしようとしているため、
55を配置する場所を見つけ出す。

851
00:35:47,600 --> 00:35:51,270
9未満、17未満、より少ない
20未満、22未満、29未満、

852
00:35:51,270 --> 00:35:52,510
未満34、ない。

853
00:35:52,510 --> 00:35:55,080
だから今、私たちは、大文字にしている
少なくとも三つの一つ。

854
00:35:55,080 --> 00:35:59,910
>> 私はここの上に55を挿入したい場合、どのような
コー​​ドの行が実行される必要がありますか？

855
00:35:59,910 --> 00:36:01,890
どのようにこの写真を行います
人間は変更する必要がありますか？

856
00:36:01,890 --> 00:36:03,181
私は私の左手で何をしますか？

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
これは、最初はnullでなければなりません
私はリストの最後に来ているので。

859
00:36:07,360 --> 00:36:09,318
そして、何をどうすべき
ここでは、ピーターと、それがあった？

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
彼は明らかに私を指すようになるだろう。

862
00:36:12,430 --> 00:36:15,580
だから私は、少なくとも2行があります主張
本日からのサンプルコード内のコードの

863
00:36:15,580 --> 00:36:18,570
それがこれを実装するために起こっている
末尾55を追加したシナリオ。

864
00:36:18,570 --> 00:36:20,950
そして、私は誰かのホップを持つことができ
上下わずか55を表す？

865
00:36:20,950 --> 00:36:22,200
すべての権利は​​、新しい55です。

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> だから今何次かの
シナリオは、やって来る

868
00:36:27,054 --> 00:36:29,720
私たちは時に挿入したい
始まるか、このリストの先頭？

869
00:36:29,720 --> 00:36:31,100
そして、あなたの名前、番号55は何ですか？

870
00:36:31,100 --> 00:36:31,420
>> 聴衆：ジャック。

871
00:36:31,420 --> 00:36:32,295
>> DAVID J.マラン：ジャック？

872
00:36:32,295 --> 00:36:33,585
OK、はじめまして。

873
00:36:33,585 --> 00:36:34,210
ご搭乗ありがとうございます。

874
00:36:34,210 --> 00:36:36,640
だから今、私たちはするつもりだ
、たとえば、5番を挿入します。

875
00:36:36,640 --> 00:36:39,840
ここでの第二のケースです
3私たちは前に思い付いた。

876
00:36:39,840 --> 00:36:43,050
だから5が先頭に属している場合、
それでは私たちはそれを見つける方法を見てみましょう。

877
00:36:43,050 --> 00:36:46,310
私は私のPTRを初期化
再び9番へのポインタ。

878
00:36:46,310 --> 00:36:49,140
そして、私は、ああ、5が9未満であり、実現した。

879
00:36:49,140 --> 00:36:50,880
だから、私たちのためにこの絵を修正。

880
00:36:50,880 --> 00:36:54,820
誰の手、ゲイブさんやダビデの
or-- 9番の名前は何ですか？

881
00:36:54,820 --> 00:36:55,740
>> 聴衆：ジェン。

882
00:36:55,740 --> 00:36:58,406
>> DAVID J.マラン：ジェンのhands--
私たちの手のどの変更する必要がある？

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
そう、ゲイブは今何を指して？

885
00:37:00,970 --> 00:37:01,640
私を。

886
00:37:01,640 --> 00:37:02,750
私は、新しいノードです。

887
00:37:02,750 --> 00:37:04,870
だから私は移動だけの種類よ
ここで、視覚的にそれを見ることができます。

888
00:37:04,870 --> 00:37:06,435
そして、その間何を私はそれを指すのですか？

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
それでも私はどこを指しています。

891
00:37:09,020 --> 00:37:10,000
だから、それはそれだ。

892
00:37:10,000 --> 00:37:13,717
コー​​ド修正のだから本当に一行
この特定の問題は、それが思われる。

893
00:37:13,717 --> 00:37:14,800
すべての権利、その結果は良いことだ。

894
00:37:14,800 --> 00:37:17,580
そして、誰かが5のプレースホルダことができますか？

895
00:37:17,580 --> 00:37:18,080
アップさあ。

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
私たちはあなたの次の時間を取得します。

898
00:37:21,320 --> 00:37:24,280
>> そうnow--すべての権利、および
余談ですが、名前など

899
00:37:24,280 --> 00:37:28,510
私は権利の明示的な言及をしていないよ
今、predがポインタ、前身ポインタ

900
00:37:28,510 --> 00:37:31,260
そして新しいポインタ、それはだ
指定された名前だけ

901
00:37:31,260 --> 00:37:35,280
ポインタへのサンプルコードで、または
周りのポインティングのようなものだ私の手。

902
00:37:35,280 --> 00:37:36,060
あなたの名前は？

903
00:37:36,060 --> 00:37:36,700
>> 聴衆：クリスティン。

904
00:37:36,700 --> 00:37:37,100
>> DAVID J.マラン：クリスティン。

905
00:37:37,100 --> 00:37:38,090
ご搭乗ありがとうございます。

906
00:37:38,090 --> 00:37:42,180
すべての権利なので、今度は、考えてみましょう
少し厄介なシナリオでは、

907
00:37:42,180 --> 00:37:46,350
私が挿入したいとなる
この中に26のようなもの。

908
00:37:46,350 --> 00:37:47,090
20？

909
00:37:47,090 --> 00:37:47,590
なに？

910
00:37:47,590 --> 00:37:50,510
これらは、私たちはこのペンを持って良いことをare--。

911
00:37:50,510 --> 00:37:51,955
すべての権利、20。

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
誰かがの別の部分を得ることができれば
紙だけで大丈夫case--にお​​いて、準備ができて。

914
00:37:57,570 --> 00:37:58,370
ああ、面白い。

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
さて、これは一例です
講義のバグ。

917
00:38:02,390 --> 00:38:03,894
[OK]をので、あなたの名前が再び何ですか？

918
00:38:03,894 --> 00:38:04,560
聴衆：ジュリア。

919
00:38:04,560 --> 00:38:07,559
DAVID J.マラン：ジュリア、あなたが開くことができます
アウトとあなたがそこに決してなかったふり？

920
00:38:07,559 --> 00:38:09,040
[OK]を、これは決して起こらなかった。

921
00:38:09,040 --> 00:38:09,680
ありがとう。

922
00:38:09,680 --> 00:38:12,180
だから私たちは挿入​​するとします
このリンクリストにジュリア。

923
00:38:12,180 --> 00:38:13,780
彼女は20番です。

924
00:38:13,780 --> 00:38:15,530
そしてもちろん、彼女はだ
に属しているつもり

925
00:38:15,530 --> 00:38:17,521
begin--まだ何を指していません。

926
00:38:17,521 --> 00:38:20,020
だからあなたの手が種類のものであってもよい
nullまたは一部のごみ値ダウン。

927
00:38:20,020 --> 00:38:21,210
のクイック話をしてみましょう。

928
00:38:21,210 --> 00:38:22,980
私は5番で、この時間を指しています。

929
00:38:22,980 --> 00:38:23,880
それから私は9をご確認ください。

930
00:38:23,880 --> 00:38:25,130
それから私は、17をご確認ください。

931
00:38:25,130 --> 00:38:26,247
それから私は、22をご確認ください。

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
そして、私は、oohの、ジュリアを実現
22の前に行く必要がある。

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
だから何が起こる必要がある？

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
誰の手に変更する必要がありますか？

938
00:38:36,910 --> 00:38:38,360
ジュリアさん、鉱山、or--
もう一度お名前は何ですか？

939
00:38:38,360 --> 00:38:39,230
>> 聴衆：クリスチャン。

940
00:38:39,230 --> 00:38:40,060
>> DAVID J.マラン：キリスト教や？

941
00:38:40,060 --> 00:38:40,560
>> 聴衆：アンディ。

942
00:38:40,560 --> 00:38:40,905
>> DAVID J.マラン：アンディ。

943
00:38:40,905 --> 00:38:41,654
クリスチャンやアンディ？

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
アンディはを指すように必要ですか？

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
ジュリア。

948
00:38:47,341 --> 00:38:47,840
かしこまりました。

949
00:38:47,840 --> 00:38:48,960
だからアンディ、あなたはジュリアを指すようにしたいですか？

950
00:38:48,960 --> 00:38:50,120
しかし、ちょっと待って。

951
00:38:50,120 --> 00:38:53,260
これまでの話では、
私は1つのようなものだ

952
00:38:53,260 --> 00:38:56,800
担当は、その意味で
ポインタのですものです

953
00:38:56,800 --> 00:38:57,850
リストを移動する。

954
00:38:57,850 --> 00:39:00,800
私たちは、アンディの名前を持っているかもしれませんが
アンディと呼ばない変数がありません。

955
00:39:00,800 --> 00:39:04,320
私たちが持っている唯一の他の変数です
まず、ゲイブで表さだ人。

956
00:39:04,320 --> 00:39:07,690
>> だから、これは、なぜこのように実際に
ここまでは、これを必要に応じていませんでした。

957
00:39:07,690 --> 00:39:10,846
しかし、今、画面にあります
PREDのポインタ再び言及。

958
00:39:10,846 --> 00:39:11,970
だから私はより明確になるであろう。

959
00:39:11,970 --> 00:39:14,820
これがポインタである場合、私はより良い持っていた
もう少しインテリジェント取得

960
00:39:14,820 --> 00:39:15,950
私の反復に関する。

961
00:39:15,950 --> 00:39:19,580
あなたは私がここを通過する気にしない場合
もう一度、ここで指して、ここに指摘した。

962
00:39:19,580 --> 00:39:22,500
しかし、私はPREDポインタを持ってみましょう
前身ポインタは、それはだ

963
00:39:22,500 --> 00:39:24,740
を指し示すの種類
要素私はちょうどにあった。

964
00:39:24,740 --> 00:39:27,330
だから私は今、ここに行くとき
私の左手の更新。

965
00:39:27,330 --> 00:39:29,370
私はここに私の左手の更新を行ったとき。

966
00:39:29,370 --> 00:39:33,090
そして今、私はへのポインタだけでなく、を持っている
ジュリアの後に行く要素、

967
00:39:33,090 --> 00:39:36,300
私はまだへのポインタを持っている
アンディ、前の要素。

968
00:39:36,300 --> 00:39:39,430
だから、基本的に、アクセス権を持って
パン粉、可能ならば、

969
00:39:39,430 --> 00:39:41,500
必要なポインタのすべてに。

970
00:39:41,500 --> 00:39:43,710
>> 私が指差しているのであれば
アンディと私も向いています

971
00:39:43,710 --> 00:39:47,105
その手のクリスチャン、で
今別の場所で指摘しておかなければならない？

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
アンディだから今ジュリアで指すことができます。

974
00:39:51,960 --> 00:39:54,460
ジュリアは今クリスチャンで指すことができます。

975
00:39:54,460 --> 00:39:56,950
彼女は私をコピーすることができますので、
右手のポインタ。

976
00:39:56,950 --> 00:40:00,044
そして、それは効果的にあなたを置きます
ここに戻ってこの場所へ。

977
00:40:00,044 --> 00:40:02,460
だから要するに、これでもかの
永遠の種類の私たちを取っている

978
00:40:02,460 --> 00:40:04,510
実際に更新する
リストをリンクし、実現

979
00:40:04,510 --> 00:40:06,580
操作すること
比較的簡単である。

980
00:40:06,580 --> 00:40:10,030
これは、一つ、二つ、三つのだ
最終的にはコードの行。

981
00:40:10,030 --> 00:40:12,780
しかし、それらの周りに巻か
おそらくコードの行

982
00:40:12,780 --> 00:40:16,350
ロジックのビットは、その効果的です。
私たちは質問を、尋ねる？

983
00:40:16,350 --> 00:40:18,970
私たちが先頭にいる、
中間、または末尾？

984
00:40:18,970 --> 00:40:21,890
>> さて、いくつかの他は確かにありま​​す
私たちが実装する場合があり操作。

985
00:40:21,890 --> 00:40:24,880
そして、ここでこれらの写真はただ描く
私たちはただ人間でやった。

986
00:40:24,880 --> 00:40:26,080
どのような除去はどうですか？

987
00:40:26,080 --> 00:40:30,650
私がしたい場合は、例えば、
番号を削除する34または55、

988
00:40:30,650 --> 00:40:34,680
私は、同じ種類のコードを持っているかもしれません
しかし、私は、1つまたは2つのステップを必要とするつもりです。

989
00:40:34,680 --> 00:40:36,110
新しいものだから？

990
00:40:36,110 --> 00:40:40,460
私が最後に誰かを削除した場合、
番号のような55、次に34、

991
00:40:40,460 --> 00:40:42,995
何も、私はそれを行うように変更することがあります？

992
00:40:42,995 --> 00:40:44,870
私はevict--しないように持っている
もう一度お名前は何ですか？

993
00:40:44,870 --> 00:40:45,380
>> 聴衆：ジャック。

994
00:40:45,380 --> 00:40:46,255
>> DAVID J.マラン：ジャック。

995
00:40:46,255 --> 00:40:49,770
私は、evict--無料ジャックだけでなく、する必要が
そう、文字通り自由なジャックに電話するか、少なくとも

996
00:40:49,770 --> 00:40:53,530
そこにポインタすぎたが、今
何がピーターに変更する必要がある？

997
00:40:53,530 --> 00:40:55,510
彼の手が、より下向き始める。

998
00:40:55,510 --> 00:40:59,300
とすぐに私は無料の呼び出しとしてあるため
ジャックは、ピーターのは、まだジャックを指している場合

999
00:40:59,300 --> 00:41:02,530
そして私はそのため横断続ける
リストおよびアクセスこのポインタ、

1000
00:41:02,530 --> 00:41:05,650
それは時に私たちの古くからの友人のセグメンテーションだ
障害が実際に蹴ることがあります。

1001
00:41:05,650 --> 00:41:07,860
私たちが与えてくれたので
ジャックへのメモリバック。

1002
00:41:07,860 --> 00:41:10,760
>> あなたはそこに滞在することができます
ぎこちなくただ一瞬。

1003
00:41:10,760 --> 00:41:13,410
私たちはいくつかありますので
考慮すべき最後の操作。

1004
00:41:13,410 --> 00:41:15,600
リストの先頭を削除する、
またはbeginning--、この1つの

1005
00:41:15,600 --> 00:41:16,349
少し迷惑。

1006
00:41:16,349 --> 00:41:19,640
私達はあることを知っている必要があるのでゲイブ
このプログラムでは一種の特別なものです。

1007
00:41:19,640 --> 00:41:21,440
確かに、彼は彼自身のポインタを有しているからである。

1008
00:41:21,440 --> 00:41:24,860
彼はただ、指し示されてないです
として、ここで他のほとんどの人がある。

1009
00:41:24,860 --> 00:41:28,112
>> だから、リストの先頭であるとき
その手の今変更する必要がある、削除？

1010
00:41:28,112 --> 00:41:29,070
もう一度お名前は何ですか？

1011
00:41:29,070 --> 00:41:29,450
>> 聴衆：クリスティン。

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J.マラン：私はひどいよ
名で、明らかに。

1013
00:41:31,408 --> 00:41:34,011
だから、クリスティンとゲイブ、
その手に変更する必要があり

1014
00:41:34,011 --> 00:41:36,510
私たちはクリスティーヌを削除しようとすると、
画像からナンバー5、？

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK、それでは、ゲイブをやらせる。

1017
00:41:38,820 --> 00:41:40,950
ゲイブが指すようになるだろう、
おそらく、9番で。

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
しかし、次は何が起こるのでしょうか？

1020
00:41:44,642 --> 00:41:46,600
聴衆：クリスティンべき
[聞き取れない] nullになる。

1021
00:41:46,600 --> 00:41:50,244
DAVID J.マラン：OK、私たちはおそらくべき
make--私はどこかに「ヌル」を聞いた。

1022
00:41:50,244 --> 00:41:51,410
聴衆：ヌルと彼女の自由。

1023
00:41:51,410 --> 00:41:51,855
DAVID J.マラン：ヌル何？

1024
00:41:51,855 --> 00:41:53,074
聴衆：ヌルと彼女の自由。

1025
00:41:53,074 --> 00:41:54,490
DAVID J.マラン：ヌルと彼女の自由。

1026
00:41:54,490 --> 00:41:55,422
だから、これは非常に簡単です。

1027
00:41:55,422 --> 00:41:58,380
そして、それはあなたが今、ソートしていることを完璧だ
そこに立っての、属していない。

1028
00:41:58,380 --> 00:42:00,430
あなたがしてきたので
リストから切り離さ。

1029
00:42:00,430 --> 00:42:02,820
あなたが効果的にしてきた
リストから孤立した。

1030
00:42:02,820 --> 00:42:07,770
だから私たちはより良い今の空き呼び出していた
クリスティーヌは、その記憶をお返しします。

1031
00:42:07,770 --> 00:42:10,240
それ以外の場合は毎回、私たち
リストからノードを削除

1032
00:42:10,240 --> 00:42:14,230
私たちは、リストを作るかもしれない
短いが、実際には減少していない

1033
00:42:14,230 --> 00:42:15,096
メモリ内のサイズ。

1034
00:42:15,096 --> 00:42:17,720
だから私たちは追加し続ける場合
リストに物事を追加、追加、

1035
00:42:17,720 --> 00:42:19,280
私のコンピュータは遅い得るかもしれない
遅い遅い、

1036
00:42:19,280 --> 00:42:21,740
私は外に実行しているので、
私は実際にいないよ場合でも、メモリ、

1037
00:42:21,740 --> 00:42:25,580
クリスティンのバイトを使用して
メモリのもう。

1038
00:42:25,580 --> 00:42:28,500
>> だから、最終的には他の存在
course--除去のシナリオ、

1039
00:42:28,500 --> 00:42:30,640
途中で、除去
私達が見たように、最後に。

1040
00:42:30,640 --> 00:42:32,348
しかし、より興味深いの
現在の課題はある

1041
00:42:32,348 --> 00:42:34,770
正確に考慮することになるだろう
実行時間は何ですか。

1042
00:42:34,770 --> 00:42:36,640
つまり、あなたの保つことができるだけでなく、
紙片、ゲイブ、もし、

1043
00:42:36,640 --> 00:42:38,640
あなたが与えて気にしないだろう
誰もがストレスボール。

1044
00:42:38,640 --> 00:42:42,100
私達のリンクリストにどうもありがとうございます
あなたができれば、ここにボランティアの。

1045
00:42:42,100 --> 00:42:45,320
>> [拍手]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J.マラン：すべての権利。

1047
00:42:46,700 --> 00:42:51,110
分析のだからカップル
その後の質問、私はできれば。

1048
00:42:51,110 --> 00:42:59,670
私たちは、以前にこの表記を見てきました、
ビッグOとオメガ、上限

1049
00:42:59,670 --> 00:43:02,520
上と下限
いくつかのアルゴリズムの実行時間。

1050
00:43:02,520 --> 00:43:04,950
それでは、ただ考えてみましょう
質問のカップル。

1051
00:43:04,950 --> 00:43:07,090
>> 一、私たちはそれを言った
前、ランニングは何ですか

1052
00:43:07,090 --> 00:43:10,647
のための検索時
ビッグOの点でリスト？

1053
00:43:10,647 --> 00:43:13,480
ランニングの上限は何ですか
リンクリストを検索する時

1054
00:43:13,480 --> 00:43:16,340
ここに私たちのボランティアによって実施されるように？

1055
00:43:16,340 --> 00:43:17,820
これは、n個の大O、線形です。

1056
00:43:17,820 --> 00:43:20,630
最悪の場合にはあるので、
55のような要素、

1057
00:43:20,630 --> 00:43:23,830
私たちが探しているかもしれないと、どこに可能性があります
ジャックは、最後にすべての方法でした。

1058
00:43:23,830 --> 00:43:28,250
そして残念ながら、配列とは異なり、
私たちは、この時間は空想取得することはできません。

1059
00:43:28,250 --> 00:43:31,820
私たち人間のすべてであったにもかかわらず、
小さな要素、5から選別、

1060
00:43:31,820 --> 00:43:35,900
大きな要素までのすべての方法、
55、それは通常は良い​​ことだ。

1061
00:43:35,900 --> 00:43:38,815
しかし、その仮定を何
もはや私たちが行うことができない？

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
聴衆：[聞き取れない]

1064
00:43:40,650 --> 00:43:40,920
DAVID J.マランは：もう一度言って？

1065
00:43:40,920 --> 00:43:41,800
聴衆：ランダムアクセス。

1066
00:43:41,800 --> 00:43:43,049
DAVID J.マラン：ランダムアクセス。

1067
00:43:43,049 --> 00:43:46,330
そして、今度はそれがありません私たちができることを意味します
長く、弱いゼロ、直感を使う

1068
00:43:46,330 --> 00:43:49,365
バイナリを使用すると自明性
検索し、分割統治。

1069
00:43:49,365 --> 00:43:51,240
たとえあるため、私たち
人間は明らかにできた

1070
00:43:51,240 --> 00:43:54,610
アンディまたはクリスチャンであったことがわかります
大体、リストの途中で、

1071
00:43:54,610 --> 00:43:57,670
私たちは、としてそれを知っている
リストをスキミングすることにより、コンピュータ

1072
00:43:57,670 --> 00:43:59,029
当初から。

1073
00:43:59,029 --> 00:44:00,570
だから私たちは、ラン​​ダムアクセスを与えてくれた。

1074
00:44:00,570 --> 00:44:04,380
>> だから、nの大きなOが今アッパーです
Googleの検索時に結合した。

1075
00:44:04,380 --> 00:44:07,920
どのようなGoogleの検索のオメガはどうですか？

1076
00:44:07,920 --> 00:44:11,535
下界検索についての周辺情報
このリスト内のいくつかの数の？

1077
00:44:11,535 --> 00:44:12,410
聴衆：[聞き取れない]

1078
00:44:12,410 --> 00:44:13,040
DAVID J.マランは：もう一度言って？

1079
00:44:13,040 --> 00:44:13,420
聴衆：One。

1080
00:44:13,420 --> 00:44:13,800
DAVID J.マラン：One。

1081
00:44:13,800 --> 00:44:14,760
だから、一定の時間。

1082
00:44:14,760 --> 00:44:17,020
最良のケースでは、クリスティーンは、
確かに、リストの先頭に。

1083
00:44:17,020 --> 00:44:19,020
そして、私たちは探している
5番は、私たちは彼女を見つけた。

1084
00:44:19,020 --> 00:44:19,787
だから大したことない。

1085
00:44:19,787 --> 00:44:22,370
しかし、彼女は時があるはずだ
この場合、リストの先頭。

1086
00:44:22,370 --> 00:44:23,745
どのような削除のようなものでしょうか？

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
あなたは要素を削除したい場合は？

1089
00:44:26,300 --> 00:44:29,200
何が上限と下限の
リンクされたから何かを削除について

1090
00:44:29,200 --> 00:44:29,699
リスト？

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
聴衆：[聞き取れない]

1093
00:44:36,070 --> 00:44:36,420
DAVID J.マランは：もう一度言って？

1094
00:44:36,420 --> 00:44:37,067
聴衆：nである。

1095
00:44:37,067 --> 00:44:38,900
DAVID J.マラン：nは
確かに上限を。

1096
00:44:38,900 --> 00:44:41,700
最悪の場合、私たちは試しているので
先ほど行ったよう、ジャックを削除します。

1097
00:44:41,700 --> 00:44:43,050
彼は最後に、すべての方法です。

1098
00:44:43,050 --> 00:44:45,419
永遠に私たちを取りますか、
彼を見つけるためにn個のステップ。

1099
00:44:45,419 --> 00:44:46,460
だから上限です。

1100
00:44:46,460 --> 00:44:47,430
つまり、必ず、線形です。

1101
00:44:47,430 --> 00:44:50,970
そして、最高のケースは、実行時間、または
最良の場合下限

1102
00:44:50,970 --> 00:44:51,975
一定の時間になります。

1103
00:44:51,975 --> 00:44:54,600
多分私達は、削除しようとしているため
クリスティン、そして私たちは幸運を得る

1104
00:44:54,600 --> 00:44:55,558
彼女が初めにあります。

1105
00:44:55,558 --> 00:44:56,350
今ちょっと待って。

1106
00:44:56,350 --> 00:44:59,370
ゲイブは、冒頭でもありました
そして私たちもゲイブを更新する必要がありました。

1107
00:44:59,370 --> 00:45:01,150
だから、あと一歩ではありませんでした。

1108
00:45:01,150 --> 00:45:04,210
だから、確かに一定であり、
時間、最良の場合には、

1109
00:45:04,210 --> 00:45:06,345
最小の要素を削除するには？

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
それは、2つである場合でも、である、
コー​​ドの3、またはさらには100ライン、

1112
00:45:10,960 --> 00:45:14,000
それは、同じ数の場合は、
ラインではなく、いくつかのループ内で、

1113
00:45:14,000 --> 00:45:16,577
とサイズに依存しない
リストの、絶対に。

1114
00:45:16,577 --> 00:45:18,660
にある要素を削除する
リストの先頭に、

1115
00:45:18,660 --> 00:45:21,940
私達はに対処する必要があっても、
ゲイブは、まだ一定の時間である。

1116
00:45:21,940 --> 00:45:24,220
>> だから、これはのように思える
後方に巨大なステップ。

1117
00:45:24,220 --> 00:45:27,000
そして、時間のもったいない
週1週中に、もし

1118
00:45:27,000 --> 00:45:30,250
私たちだけではなく、持っていたゼロ
擬似コードコードが、実際のコード

1119
00:45:30,250 --> 00:45:35,780
ログの何かを実装する
ベースnは、またはログ、むしろ、nは、ベース2、

1120
00:45:35,780 --> 00:45:37,150
その実行時間の点で。

1121
00:45:37,150 --> 00:45:40,710
それでいったい私たちは開始したいと思う理由
リンクリストのようなものを使用して？

1122
00:45:40,710 --> 00:45:41,517
うん。

1123
00:45:41,517 --> 00:45:44,022
>> 聴衆：だからあなたが追加することができます
配列に要素。

1124
00:45:44,022 --> 00:45:46,230
DAVID J.マラン：だからあなたができる
配列に要素を追加します。

1125
00:45:46,230 --> 00:45:47,550
そして、これはあまりにもテーマのある。

1126
00:45:47,550 --> 00:45:49,740
そして、私たちは表示され続けるだろう
この、このトレードオフ、多くの

1127
00:45:49,740 --> 00:45:51,573
のような私たちが見てきた
マージソートとトレードオフ。

1128
00:45:51,573 --> 00:45:54,606
私たちは本当にスピードアップできた
むしろ、検索または並べ替え、

1129
00:45:54,606 --> 00:45:57,480
私たちはもう少しスペースを費やす場合には
メモリの追加のチャンクを持っている

1130
00:45:57,480 --> 00:45:58,760
またはマージソートのための配列。

1131
00:45:58,760 --> 00:46:01,270
しかし、私たちはより多くを過ごす
スペースが、私たちは時間を節約できます。

1132
00:46:01,270 --> 00:46:04,820
このケースでは、だ
時間をあきらめるが、私たちがしている

1133
00:46:04,820 --> 00:46:08,170
柔軟性を増し、
ダイナミズム可能ならば、

1134
00:46:08,170 --> 00:46:10,280
これは間違いなくポジティブな機能です。

1135
00:46:10,280 --> 00:46:11,520
>> また、スペースを費やしている。

1136
00:46:11,520 --> 00:46:13,710
どのような意味ではリンクされている
より高価一覧表示

1137
00:46:13,710 --> 00:46:15,700
配列以外のスペースの面で？

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
どこに余分なスペースがから来ている？

1140
00:46:19,920 --> 00:46:20,460
うん？

1141
00:46:20,460 --> 00:46:21,800
>> 聴衆：[聞こえない]ポインタ。

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J.マラン：ええ、私たち
また、ポインタを持っている。

1143
00:46:23,310 --> 00:46:25,560
だから、これはminorly迷惑です
そのもはや午前中

1144
00:46:25,560 --> 00:46:27,780
私はint型を格納
int型を表します。

1145
00:46:27,780 --> 00:46:30,990
私はint型であり、aを格納しています
また32ビットであるポインタ。

1146
00:46:30,990 --> 00:46:33,470
だから私は、文字通り倍増してい
スペースの量は、含まれる。

1147
00:46:33,470 --> 00:46:36,040
だから、トレードオフだが、
それがint型の場合にはあります。

1148
00:46:36,040 --> 00:46:39,580
あなたはint型を格納していないと仮定し、
これらの各矩形を想定

1149
00:46:39,580 --> 00:46:43,290
またはこれらの人間のそれぞれが表すた
単語、英語の単語こと

1150
00:46:43,290 --> 00:46:46,430
5文字、10かもしれない
文字、多分もっと。

1151
00:46:46,430 --> 00:46:49,940
それからちょうど32以上のビットを追加する
大したことの少ない可能性があります。

1152
00:46:49,940 --> 00:46:52,160
>> どのような学生のそれぞれの場合
デモ中

1153
00:46:52,160 --> 00:46:55,107
文字通り、その生徒の構造体であった
多分名前と住宅やを持っている

1154
00:46:55,107 --> 00:46:57,065
電話番号やツイッター
ハンドル等が挙げられる。

1155
00:46:57,065 --> 00:46:59,564
だから、すべてのフィールドの私達が開始
先日の話、

1156
00:46:59,564 --> 00:47:02,410
など大したことのはるかに少ない
私達のノードがより面白くなる

1157
00:47:02,410 --> 00:47:05,972
追加と過ごすことが大きい、ええ、
ポインタは、単にそれらを一緒にリンクします。

1158
00:47:05,972 --> 00:47:07,180
しかし、確かに、それはトレードオフです。

1159
00:47:07,180 --> 00:47:09,560
そして実際、コードは
あなたとわかるように、より複雑な

1160
00:47:09,560 --> 00:47:11,770
を通してスキミングによる参照
その特定の例。

1161
00:47:11,770 --> 00:47:14,302
しかし、何があった場合
ここでいくつかの聖杯。

1162
00:47:14,302 --> 00:47:17,010
私たちが一歩を踏み出すないとどう
後方が、巨大な一歩

1163
00:47:17,010 --> 00:47:19,180
およびデータを実装する
私たちは経由構造

1164
00:47:19,180 --> 00:47:22,870
ジャックなどの要素を見つけることができます
クリスティンまたはその他の要素

1165
00:47:22,870 --> 00:47:25,870
真の定数時間でこの配列内の？

1166
00:47:25,870 --> 00:47:26,920
検索は一定である。

1167
00:47:26,920 --> 00:47:28,320
削除は定数である。

1168
00:47:28,320 --> 00:47:29,570
挿入は一定である。

1169
00:47:29,570 --> 00:47:32,260
これらの操作の全ては一定である。

1170
00:47:32,260 --> 00:47:33,750
それが私たちの聖杯になります。

1171
00:47:33,750 --> 00:47:36,690
そしてそれはどこに私たち
次回をピックアップします。

1172
00:47:36,690 --> 00:47:38,600
その後お会いしましょう​​。

1173
00:47:38,600 --> 00:47:39,371