1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [第6週、続く]

2
00:00:02,520 --> 00:00:04,160
[デビッド·J·マラン] [ハーバード大学]

3
00:00:04,160 --> 00:00:08,720
[これはCS50です。] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
これはCS50であり、これは第6週の終わりです。

5
00:00:12,970 --> 00:00:17,970
だからCS50x、EDXイニシアチブに関与ハーバード初のコースのひとつ

6
00:00:17,970 --> 00:00:20,590
確かに、この過去の月曜日にデビューしました。

7
00:00:20,590 --> 00:00:23,460
あなたは、インターネット上で何他人を垣間見ることがしたい場合

8
00:00:23,460 --> 00:00:27,180
今と一緒にフォローしている、あなたはx.cs50.netに向かうことができる。

9
00:00:27,180 --> 00:00:30,350
edx.org上の適切な場所にリダイレクトされますつまり、

10
00:00:30,350 --> 00:00:34,160
どの本とMITとバークレーから他のコースが今住んでいるところだった。

11
00:00:34,160 --> 00:00:38,140
あなたのアカウントにサインアップする必要があります、あなたは、材料はほぼ同じであることがわかります

12
00:00:38,140 --> 00:00:42,170
私達はいろいろと準備をするようには、数週間遅れとはいえ、この学期を持っていたとして。

13
00:00:42,170 --> 00:00:46,930
しかし、何CS50xの学生が今見ますと、非常にこのようなインターフェイスです。

14
00:00:46,930 --> 00:00:50,040
これは、例えば、問題セット0のチュートリアルをリードZamylaです。

15
00:00:50,040 --> 00:00:54,230
edx.orgへのログイン時に、CS50x学生は物事の種類を見ている

16
00:00:54,230 --> 00:00:57,170
、月曜日の講義を：あなたは、コースに見られるような、

17
00:00:57,170 --> 00:01:01,650
水曜日、さまざまなショートパンツ、問題セット、チュートリアル、PDFの講義。

18
00:01:01,650 --> 00:01:04,459
加えて、ここで見たように、機械翻訳

19
00:01:04,459 --> 00:01:08,390
、イタリア語、スペイン語、日本語、中国語に英語の成績証明書の

20
00:01:08,390 --> 00:01:12,810
確かに不完全になり、他の言語との全体の束

21
00:01:12,810 --> 00:01:15,840
我々は、プログラムのAPIと呼ばれるものを使用してそれらをロールアウトするように、

22
00:01:15,840 --> 00:01:18,360
Googleから、またはアプリケーション·プログラミング·インターフェース、

23
00:01:18,360 --> 00:01:21,360
それは、私たちは、これらの他の言語に英語に変換することができます。

24
00:01:21,360 --> 00:01:24,100
しかし、いくつかの百プラスボランティアの素晴らしい精神のおかげで、

25
00:01:24,100 --> 00:01:26,940
親切に巻き込まれることを申し出ているインターネット上のランダムな人々

26
00:01:26,940 --> 00:01:30,180
このプロジェクトでは、我々は徐々にそれらの翻訳の品質を向上させることでしょう

27
00:01:30,180 --> 00:01:35,790
人間は私たちのコンピュータが作っていることの間違いを修正させることによって。

28
00:01:35,790 --> 00:01:42,330
>> だから、我々はいくつかのより多くを持っていた20人の生徒は、我々が当初予想よりも月曜日に表示に変わります。

29
00:01:42,330 --> 00:01:48,980
実際には、今CS50xは自宅で一緒に以下の10万人を持っています。

30
00:01:48,980 --> 00:01:54,430
ですから、コンピュータサイエンスのこのコースを作るこの期生のすべての部分です実現

31
00:01:54,430 --> 00:01:57,370
教育より一般的には、もっと広く言えば、アクセスできます。

32
00:01:57,370 --> 00:02:00,130
そして現実には、これらの大規模なオンラインコースのいくつかと、今ある

33
00:02:00,130 --> 00:02:04,070
それらはすべて我々がここで行っているように見えるように、これらの非常に高い数字で始まる。

34
00:02:04,070 --> 00:02:08,759
しかし、目標は、最終的に、CS50xためできるだけフィニッシュラインをできるだけ多くの人々を得るために本当にです。

35
00:02:08,759 --> 00:02:12,000
設計により、CS50xこの過去月曜日から提供されようとしている

36
00:02:12,000 --> 00:02:17,430
人々は他の場所で学校のコミットメントを持っているように、2013年4月15日を介してすべての道、

37
00:02:17,430 --> 00:02:20,990
仕事、家族、他の競合など、もう少し柔軟性を持っている

38
00:02:20,990 --> 00:02:23,640
このコースに飛び込むことになる、これは、、それが言えば十分

39
00:02:23,640 --> 00:02:30,540
通常の学期中、わずか3ヶ月に渡っている場合にのみ、非常に意欲的に行われます。

40
00:02:30,540 --> 00:02:34,190
しかし、これらの生徒は、同じコンテンツを視聴し、同じ問題セットに取り組むことになる

41
00:02:34,190 --> 00:02:36,350
同じショートパンツなどへのアクセスを有する。

42
00:02:36,350 --> 00:02:38,990
だから我々はこの一緒にすべて実際にあることを認識しています。

43
00:02:38,990 --> 00:02:42,360
とCS50xの終わりの目標の一つは、同じように多くの人々を得ることではありません

44
00:02:42,360 --> 00:02:45,720
フィニッシュラインにし、それらにコンピュータサイエンスのこの新たな理解を与える

45
00:02:45,720 --> 00:02:49,000
とプログラミングだけでなく、彼らは、この共有経験を持っている持っている。

46
00:02:49,000 --> 00:02:52,010
キャンパス内の50の特​​徴の1つは、我々は願っています、

47
00:02:52,010 --> 00:02:56,260
、時々、良くも悪くも、共同の経験のこの種であった

48
00:02:56,260 --> 00:02:59,480
しかし、これらの人々に左右にターンすること、

49
00:02:59,480 --> 00:03:01,830
とオフィスアワーとhackathonかつ公正。

50
00:03:01,830 --> 00:03:04,560
それは、オンラインの人々と個人的にそれを行うには少し難しくなっている

51
00:03:04,560 --> 00:03:10,580
しかしCS50xは、初CS50エキスポ4月に締結する

52
00:03:10,580 --> 00:03:13,630
公正の私たちのアイデアのオンライン適応される

53
00:03:13,630 --> 00:03:18,250
学生のこれらの数千はすべて1を提出するよう要請される場所 -  2分間のビデオに、

54
00:03:18,250 --> 00:03:22,480
それらの彼らの最終的なプロジェクトやビデオのスクリーンキャストは、hello振っどちら

55
00:03:22,480 --> 00:03:24,490
とそのプロジェクトについて話して、それをデモ、

56
00:03:24,490 --> 00:03:27,610
ずっとあなたの前任者のようには、公正でキャンパスでここに行っている

57
00:03:27,610 --> 00:03:31,400
学期の終わりまでに、希望はグローバルな展示会を持つようになるように

58
00:03:31,400 --> 00:03:37,080
キャンパスでここにこの12月あなたを待ってずっとそのようなCS50x学生の最終的なプロジェクトの。

59
00:03:37,080 --> 00:03:39,680
これから数ヶ月で、その上で非常に多くの。

60
00:03:39,680 --> 00:03:43,640
>> 10万人で、しかし、いくつかのより多くのCAの必要性を付属しています。

61
00:03:43,640 --> 00:03:47,590
君たちはここで新機軸を開くとCS50を取っていることを考えると

62
00:03:47,590 --> 00:03:51,630
EDX上の人々にこの材料のリリースに先立って数週間、

63
00:03:51,630 --> 00:03:55,330
我々はこの構想に、できるだけ私たち自身の学生の多くが関与するのが大好きだ実現する、

64
00:03:55,330 --> 00:03:58,720
学期と同様に、今年の冬と今年春に両方。

65
00:03:58,720 --> 00:04:01,620
ですからCS50xに巻き込まれたい場合は、

66
00:04:01,620 --> 00:04:07,450
特にCS50x議論し、CS50論議のEDXバージョン、上に参加

67
00:04:07,450 --> 00:04:10,140
あなたがたの多くは、キャンパス内で使用されている、オンラインの掲示板、

68
00:04:10,140 --> 00:04:13,040
そのURLへの頭をしてください、私たちはあなたが誰であるかを知らせる

69
00:04:13,040 --> 00:04:16,450
私たちは、学生やスタッフのチームと教員を構築してみたいので

70
00:04:16,450 --> 00:04:19,630
キャンパス内に単にに沿って演奏し、手伝っている人。

71
00:04:19,630 --> 00:04:21,720
そして、彼らはそれらになじみの質問を見たとき、

72
00:04:21,720 --> 00:04:25,320
あなたは、インターネット上のいくつかの国でそこにどこかにいくつかのバグを報告する学生を聞く

73
00:04:25,320 --> 00:04:27,450
あなたも、同じ問題を持っていたので、ベルを鳴らしている

74
00:04:27,450 --> 00:04:32,620
あなたのD-ホールでいくつかの時間前に、うまくいけば、あなたは相づちを打つと自分の経験を共有することができます。

75
00:04:32,620 --> 00:04:37,300
ですから、もし、ご希望分かち合うようにしてください。

76
00:04:37,300 --> 00:04:39,360
>> ハーバード大学でコンピュータサイエンスのコースは、伝統のビットを持っている

77
00:04:39,360 --> 00:04:44,730
いくつかの服装を持っていることのそれらの間のCS50、あなたが自信を持って着ることができるいくつかの服、

78
00:04:44,730 --> 00:04:49,090
学期の終わりに、あなたはCS50を終了したことを非常に誇らしげに言って

79
00:04:49,090 --> 00:04:51,830
とCS50などを取って、我々は常に学生を関与しよう

80
00:04:51,830 --> 00:04:54,540
この過程で、可能な限り、それによって私たちが招待

81
00:04:54,540 --> 00:04:56,900
学期のこの時期には、学生がデザインを提出する

82
00:04:56,900 --> 00:04:59,330
選択肢のPhotoshopを使って、あるいはどのようなツールでも使用したいのですが

83
00:04:59,330 --> 00:05:02,330
あなたは、Tシャツやスウェットシャツのデザインを提出し、デザイナーなら

84
00:05:02,330 --> 00:05:06,100
と犬のための傘と小さなバンダナは、我々は今持っているなどが挙げられる。

85
00:05:06,100 --> 00:05:09,370
そして、すべてはその後です - 受賞者は毎年、その後展示されています

86
00:05:09,370 --> 00:05:12,700
store.cs50.netでコースのウェブサイトで。

87
00:05:12,700 --> 00:05:15,790
すべてはそこにコストで販売しますが、ウェブサイトでは、単にそれ自身が実行され

88
00:05:15,790 --> 00:05:18,330
そして人々は、彼らが好きな色やデザインを選ぶことができます。

89
00:05:18,330 --> 00:05:20,420
だから私たちはちょうど昨年の設計のいくつかを共有したいと思った

90
00:05:20,420 --> 00:05:25,130
それは毎年の伝統であるここでは、この1以外のウェブサイトにあった。

91
00:05:25,130 --> 00:05:29,410
"私はFaultnをワンセグてる毎日は"昨年提出の一つであった、

92
00:05:29,410 --> 00:05:32,290
これは、卒業生のためにそこにまだ使用可能です。

93
00:05:32,290 --> 00:05:35,820
我々は、このいずれかを持っていた、 "CS50は、1989年に設立。"

94
00:05:35,820 --> 00:05:39,010
当社Bowdensの一つ、ロブは、昨年とても人気があった。

95
00:05:39,010 --> 00:05:43,480
"チーム·ボーデンは"生まれた、このデザインは、トップ売り手の間、提出された。

96
00:05:43,480 --> 00:05:49,040
として、この1つはここにあった。多くの人々が販売ログによると、 "ボーデンフィーバー"を持っていた。

97
00:05:49,040 --> 00:05:52,650
それは今までインターネット上で、そこにあなたのデザインかもしれないことを認識しています。

98
00:05:52,650 --> 00:05:57,510
次の問題でこれについての詳細は、来るように設定します。

99
00:05:57,510 --> 00:06:00,330
>> もう1つのツール：あなたが今うまくいけば、いくつかのエクスポージャーを有していたとき

100
00:06:00,330 --> 00:06:02,350
GDBでいくつかの実地体験、

101
00:06:02,350 --> 00:06:04,570
これは、もちろん、デバッガであり、あなたが操作することができます

102
00:06:04,570 --> 00:06:09,500
かなり低いレベルでのプログラムは、どのような種類のものをやって？

103
00:06:09,500 --> 00:06:13,030
GDBは、あなたが何をできるのですか？

104
00:06:13,030 --> 00:06:15,030
うん？私に何かを与える。 [学生の答えは、不明朗]

105
00:06:15,030 --> 00:06:18,120
グッド。関数にステップインするので、あなただけの実行を入力する必要はありません

106
00:06:18,120 --> 00:06:22,310
と標準出力に物事をプリントアウトし、その全体を通して、プログラムの一撃を持っています。

107
00:06:22,310 --> 00:06:25,190
むしろ、次のいずれかの横に入力し、それを介して行ずつステップ実行することができます

108
00:06:25,190 --> 00:06:30,300
あなたが書いた典型的には、関数に飛び込むラインや工程によって行ずつ移動する1。

109
00:06:30,300 --> 00:06:35,240
GDBは、あなたが行う他に何ができるのですか？うん？ [学生の答えは、不明朗]

110
00:06:35,240 --> 00:06:38,100
変数を印刷します。あなたのプログラムの中に少しのイントロスペクションを行いたいのであれば

111
00:06:38,100 --> 00:06:41,500
あらゆる場所にprintf文を書くことに頼ることなく、

112
00:06:41,500 --> 00:06:44,600
あなただけの変数を印刷したり、変数を表示することができます。

113
00:06:44,600 --> 00:06:46,710
あなたは、GDBのようなデバッガで他に何ができる？

114
00:06:46,710 --> 00:06:49,170
[学生の答えは、不明朗]

115
00:06:49,170 --> 00:06:52,080
その通りです。あなたは、ブレークポイントを設定でき、ブレーク実行を言うことができます

116
00:06:52,080 --> 00:06:54,020
main関数またはfoo関数で。

117
00:06:54,020 --> 00:06:56,800
あなたは、123行目でブレーク実行を言うことができます。

118
00:06:56,800 --> 00:06:58,950
とブレークポイントは本当に強力な技術である

119
00:06:58,950 --> 00:07:01,110
なぜならあなたはどこにあなたの問題の一般的な意味を持っている場合

120
00:07:01,110 --> 00:07:05,360
おそらく、あなたは、プログラムの全体をステップ実行時間を無駄にする必要はありませんされています。

121
00:07:05,360 --> 00:07:08,250
あなたは本質的にそこにジャンプしてから入力を開始することができます - 

122
00:07:08,250 --> 00:07:10,970
stepやnextなどでそれをステップ。

123
00:07:10,970 --> 00:07:14,340
しかし、GDBのようなものでキャッチは、それは、人間に役立つことです

124
00:07:14,340 --> 00:07:16,940
あなたの問題を見つけ、あなたのバグを見つける。

125
00:07:16,940 --> 00:07:19,470
それは必ずしもあなたのために多くのそれらを見つけることができません。

126
00:07:19,470 --> 00:07:23,070
>> だから我々は短いコマンドラインツールです先日style50を導入

127
00:07:23,070 --> 00:07:27,500
よりきれいにあなたよりもあなたのコードを少しはめるしようとしている、人間が行っている可能性があります。

128
00:07:27,500 --> 00:07:29,530
しかし、それは、あまりにも、本当にただ美的なものです。

129
00:07:29,530 --> 00:07:34,110
使用するのはもう少し難解ですValgrindのと呼ばれるこの他のツールがあるのOUTしかし、それは変わります。

130
00:07:34,110 --> 00:07:36,860
その出力は一見atrociously謎めいています。

131
00:07:36,860 --> 00:07:39,420
しかし、それは特に今、私たちは、用語の一部にいることを、素晴らしく便利です

132
00:07:39,420 --> 00:07:43,080
どこでmallocと動的なメモリ割り当てを使用し始めている。

133
00:07:43,080 --> 00:07:45,420
物事が迅速に、本当に、本当に間違って行くことができます。

134
00:07:45,420 --> 00:07:49,320
なぜならあなたのメモリを解放するのを忘れたり、あなたには、いくつかのNULLポインタを間接参照する場合、

135
00:07:49,320 --> 00:07:55,770
または、いくつかのゴミポインタを間接参照する、一般的にその結果の症状は何ですか？

136
00:07:55,770 --> 00:07:59,470
seg ​​faultを。そして、あなたは、キロバイトまたはメガバイトのいくつかの数のこのコアファイルを取得する

137
00:07:59,470 --> 00:08:02,990
それがクラッシュしたとき、それは、あなたのプログラムのメモリの状態を表す

138
00:08:02,990 --> 00:08:05,730
しかし、あなたのプログラムが最終的にセグメント障害、セグメンテーションフォルト、

139
00:08:05,730 --> 00:08:08,450
これは何か悪いことがほとんど常に関連起こっ意味

140
00:08:08,450 --> 00:08:11,750
あなたがどこかで作ったメモリ関連のミス。

141
00:08:11,750 --> 00:08:14,100
だから、Valgrindはあなたがこのようなものを見つけることができます。

142
00:08:14,100 --> 00:08:17,720
あなたのプログラムをコンパイルした後には、GDBのように、あなたが実行するツールです

143
00:08:17,720 --> 00:08:20,330
しかし、直接ではなく、プログラムを実行する際には、Valgrindは実行

144
00:08:20,330 --> 00:08:23,960
とあなたはGDBとまったく同じように、あなたのプログラムに渡す。

145
00:08:23,960 --> 00:08:26,220
さて、使い方は、最高出力の種類を取得する

146
00:08:26,220 --> 00:08:30,410
画面の上になる権利がある、少し長いですあなたはValgrindの-vを参照してくださいよ。

147
00:08:30,410 --> 00:08:35,350
あなたがLinuxコンピュータ上でプログラムを使用しているときは、 "-v"ほぼ普遍的に冗長なことを意味します。

148
00:08:35,350 --> 00:08:38,770
だから、あなたは、デフォルトではかもしれないより多くのデータを吐き出すことを意味します。

149
00:08:38,770 --> 00:08:45,510
" -  =完全に漏れを確認してください。"これは単に、すべての可能なメモリリークのチェックを言っている

150
00:08:45,510 --> 00:08:49,430
私が作ったかもしれないというミス。これも、Linuxのプログラムと共通パラダイムです。

151
00:08:49,430 --> 00:08:52,710
一般的に、 "スイッチ"のコマンドライン引数を使用している場合、

152
00:08:52,710 --> 00:08:55,830
そのプログラムの動作を変更することになって、それがただ一つの手紙だのは、

153
00:08:55,830 --> 00:09:00,310
それが切り替わっている場合、それは、単にプログラマの設計によっては、-vですが、

154
00:09:00,310 --> 00:09:05,150
単語の完全な単語または一連のですが、コマンドラインの引数で始まる - 。

155
00:09:05,150 --> 00:09:08,190
これらは、ちょうど人間の慣習ですが、あなたはますますそれらが表示されます。

156
00:09:08,190 --> 00:09:12,410
そして、最後に、 "a.outは"この特定の例では、プログラムの任意の名前です。

157
00:09:12,410 --> 00:09:14,640
そして、ここでは、いくつかの代表的な出力です。

158
00:09:14,640 --> 00:09:22,890
>> 我々はそれが意味するかもしれないものを見て前に、私はこっちのコードスニペットに渡って行こう。

159
00:09:22,890 --> 00:09:26,390
そして、すぐに来て、私は道のこれを移動することができ

160
00:09:26,390 --> 00:09:32,120
とのヒアこの短い例ですmemory.cの、見てみましょう。

161
00:09:32,120 --> 00:09:36,290
したがって、このプログラムでは、私は関数や質問にズームインしてみましょう。

162
00:09:36,290 --> 00:09:39,430
我々は、F関数を呼び出すmain関数を持っている

163
00:09:39,430 --> 00:09:45,590
その後何fは少し技術的な英語で、何に進みますか？

164
00:09:45,590 --> 00:09:49,760
fは何を進めるのですか？

165
00:09:49,760 --> 00:09:53,680
どうです、私は20行目から始めましょう、と星の位置は重要ではありません、

166
00:09:53,680 --> 00:09:56,720
だけど、最後の講義と一緒にここに一貫しているでしょう。

167
00:09:56,720 --> 00:09:59,910
20行目では、私たちのために何をするのか？左手側にあります。我々は、さらに壊してやる。

168
00:09:59,910 --> 00:10:02,410
int型* X：それは何をするのでしょうか？

169
00:10:02,410 --> 00:10:04,940
オーケー。これは、ポインタを宣言し、今のはもっと技術的なことしてみましょう。

170
00:10:04,940 --> 00:10:10,230
それはポインタを宣言するために、非常に具体的には、どういう意味ですか？他の誰か？

171
00:10:10,230 --> 00:10:15,050
うん？ [学生の答え、理解不能]遠すぎる。

172
00:10:15,050 --> 00:10:17,060
だからあなたは、等号の右側に読んでいる。

173
00:10:17,060 --> 00:10:20,290
ただのint * xに、ちょうど左のは、注目しましょう​​。

174
00:10:20,290 --> 00:10:24,700
これは、ポインタを "宣言"が、今、その定義に深くでレッツダイビングん。

175
00:10:24,700 --> 00:10:28,330
それは具体的には、技術的にはどういう意味ですか？うん？

176
00:10:28,330 --> 00:10:31,940
[学生の答えは、不明朗]

177
00:10:31,940 --> 00:10:35,090
オーケー。これは、メモリ内のアドレスを保存するために準備を進めている。

178
00:10:35,090 --> 00:10:40,680
グッド。とのこの一歩進めてみましょう、それは、32ビットの変数xを宣言している。

179
00:10:40,680 --> 00:10:44,440
そして、私はそれがために32ビットであることを知っている - ？

180
00:10:44,440 --> 00:10:47,390
それがこの場合のポインタだからそれは、int型だからそうではありません。

181
00:10:47,390 --> 00:10:49,650
それはint型を持つものと同じだという偶然、

182
00:10:49,650 --> 00:10:51,970
しかし、星があるという事実は、これはポインタであるそこに意味

183
00:10:51,970 --> 00:10:57,300
とアプライアンスでは、多くのコンピュータと同様に、すべてではありませんが、ポインタは32ビットです。

184
00:10:57,300 --> 00:11:01,850
最新のMacは、最新のPCと同様に、より現代的なハードウェア上では、64ビット·ポインタを持っているかもしれませんが、

185
00:11:01,850 --> 00:11:04,160
が、アプライアンスでは、これらのものは32ビットです。

186
00:11:04,160 --> 00:11:08,380
だから我々はそれを標準化します。具体的には、物語は次のようになる：

187
00:11:08,380 --> 00:11:10,820
私たちは、ポインタを "宣言"、それはどういう意味ですか？

188
00:11:10,820 --> 00:11:12,810
我々は、メモリアドレスを格納するための準備をします。

189
00:11:12,810 --> 00:11:15,530
どういう意味ですか？

190
00:11:15,530 --> 00:11:19,810
我々は、32ビットを占有しますと呼ばれる変数xを作成

191
00:11:19,810 --> 00:11:23,810
それはすぐに整数のアドレスを格納します。

192
00:11:23,810 --> 00:11:26,470
そして、それはおそらく我々が得ることができると同じくらい正確なのです。

193
00:11:26,470 --> 00:11:31,810
それは、世界を単純化し、ちょうどxというポインタを宣言したとする前進大丈夫です。

194
00:11:31,810 --> 00:11:35,380
ポインタを宣言しますが、実際に何が起こっているのを認識し、理解する

195
00:11:35,380 --> 00:11:38,490
だけでも、それらのいくつかの文字インチ

196
00:11:38,490 --> 00:11:42,040
>> さて、この1つは、それが長い式は言っても、ほとんど少し簡単です。

197
00:11:42,040 --> 00:11:48,160
だから、これは現在ハイライトされていること、何をやっている "のmalloc（10 * sizeof（int））を、"ええ？

198
00:11:48,160 --> 00:11:52,350
[学生の答えは、不明朗]

199
00:11:52,350 --> 00:11:58,250
グッド。そして、私はそこにそれを取るよ。これは、10個の整数のためのメモリチャンクを割り当てている。

200
00:11:58,250 --> 00:12:02,190
そして今、少し深くでダイビングしましょう​​、それは10個の整数のために大量のメモリーを割り当てている。

201
00:12:02,190 --> 00:12:05,390
malloc関数その後復帰とは何ですか？

202
00:12:05,390 --> 00:12:10,390
そのチャンクのアドレス、または、より具体的には、そのチャンクの最初のバイトのアドレス。

203
00:12:10,390 --> 00:12:14,080
どのようにしてどこにメモリの端の、そのチャンク私は、プログラマが、知っているのですか？

204
00:12:14,080 --> 00:12:18,340
私はそれが連続したことを知っている。 malloc関数は、定義により、あなたのメモリの連続した​​チャンクを与えるだろう。

205
00:12:18,340 --> 00:12:21,240
それにギャップはありません。あなたは、そのチャンク内の全てのデータへのアクセス権を持っている

206
00:12:21,240 --> 00:12:26,760
背中合わせに戻ることではなく、このメモリチャンクの終わりがどこにあるか、どのように私は知っていますか？

207
00:12:26,760 --> 00:12:28,850
あなたは、mallocを使用するときは？ [学生の答え、理解不能]グッド。

208
00:12:28,850 --> 00:12:30,670
あなたはしないでください。あなたが覚えておく必要があります。

209
00:12:30,670 --> 00:12:35,960
私は値10を使用したことを覚えておく必要があり、私もそれここでやったとは思えません。

210
00:12:35,960 --> 00:12:41,000
しかし、責任は私に完全にある。我々が文字列のためにわずかに依存するようになってきたstrlenは、

211
00:12:41,000 --> 00:12:45,860
なぜなら\ 0を持つこの大会の作品だけ

212
00:12:45,860 --> 00:12:48,840
文字列の末尾にNULかこの特別NUL文字、、。

213
00:12:48,840 --> 00:12:51,740
これはメモリのちょうど任意のチャンクに保持していません。

214
00:12:51,740 --> 00:12:58,590
それはあなた次第です。だから、20行目は、その後、メモリのチャンクを割り当て

215
00:12:58,590 --> 00:13:02,590
それは10個の整数を格納することができ、そしてそれは最初のバイトのアドレスを格納

216
00:13:02,590 --> 00:13:05,610
と呼ばれる変数xのメモリのチャンクの。

217
00:13:05,610 --> 00:13:11,140
ポインタであるエルゴ、。だから、21行目は、残念なことに、間違いだった。

218
00:13:11,140 --> 00:13:16,110
しかし、最初に、それは何をやっている？それは、場所10、インデックス0の店を言っている

219
00:13:16,110 --> 00:13:19,480
メモリのチャンクの値を0 xという。

220
00:13:19,480 --> 00:13:21,510
>> だから物事のカップルが起こっているがわかります。

221
00:13:21,510 --> 00:13:25,420
xがポインタであっても、数週間前からリコール

222
00:13:25,420 --> 00:13:29,440
あなたはまだ配列形式の角括弧記法を使用することができます。

223
00:13:29,440 --> 00:13:36,180
それは実際にはもっと不可解に見えるポインタ演算に対する簡略表記だから。

224
00:13:36,180 --> 00:13:40,320
我々はこのような何かをする場所：アドレスxを取り、上に10箇所を移動

225
00:13:40,320 --> 00:13:44,550
その後、その場所に格納されたアドレスに進みます。

226
00:13:44,550 --> 00:13:48,090
しかし、率直に言って、これは読んで慣れるためだけに凶悪です。

227
00:13:48,090 --> 00:13:52,900
だから世界は、典型的には、読むことをそんなに、より人間にやさしいという理由だけ角括弧を使用しています。

228
00:13:52,900 --> 00:13:55,140
しかし、それは本当にフードの下で何が起こっているかです;

229
00:13:55,140 --> 00:13:58,190
xはアドレスではなく、配列自体です。

230
00:13:58,190 --> 00:14:02,410
だから、これは、xの位置10に0を格納しています。

231
00:14:02,410 --> 00:14:06,120
なぜこれが悪いのか？うん？

232
00:14:06,120 --> 00:14:17,370
[学生の答え、理解不能]その通りです。

233
00:14:17,370 --> 00:14:21,100
、我々は唯一の10個のint値を割り当てられますが、C言語でプログラミングするとき、我々は0から数える

234
00:14:21,100 --> 00:14:25,690
ので、0 1 2 3 4 5 6 7 8 9ではなく、10へのアクセスを持っています。

235
00:14:25,690 --> 00:14:30,270
だから、どちらかのプログラムがセグメントフォルトに起こっているか、そうではありません。

236
00:14:30,270 --> 00:14:32,900
しかし、我々は本当に知りませんが、これは非決定的な振る舞いのようなものです。

237
00:14:32,900 --> 00:14:35,600
それは本当に我々が幸運を得るかどうかに依存します。

238
00:14:35,600 --> 00:14:40,650
それは私がその余分なバイトを使用する場合は、オペレーティングシステムには気にしないことが判明した場合、

239
00:14:40,650 --> 00:14:43,360
それは私にそれを与えていないにもかかわらず、私のプログラムがクラッシュしない場合があります。

240
00:14:43,360 --> 00:14:46,780
、それはバグだらけだ、生ですが、あなたはその症状が表示されない場合があり

241
00:14:46,780 --> 00:14:48,960
またはあなたはしばらくの間に一度だけそれを見るかもしれません。

242
00:14:48,960 --> 00:14:51,230
しかし、現実にはバグがあり、実際にはあるということです。

243
00:14:51,230 --> 00:14:54,320
あなたが正しいことをするプログラムを書いたことがあるのなら、それは、本当に問題だ

244
00:14:54,320 --> 00:14:58,840
あなたは人々がすべてのがたまにクラッシュすることが、使用しているプログラムを販売してきた

245
00:14:58,840 --> 00:15:02,450
なぜなら、もちろん、これは良くありません。実際には、あなたのAndroid携帯電話やiPhoneを持っている場合

246
00:15:02,450 --> 00:15:05,550
そして、あなたは、これらの日のアプリをダウンロードあなたが今まで持っていた場合にアプリが終了するだけ

247
00:15:05,550 --> 00:15:10,040
ほとんどの場合、いくつかのメモリ関連の問題の結果だとそれが消える突然、

248
00:15:10,040 --> 00:15:12,830
プログラマは、ポインタを台無しにし、それによって間接参照

249
00:15:12,830 --> 00:15:18,670
彼または彼女は持つべきではない、とiOSやAndroidの結果は、単に完全にプログラムを強制終了することを

250
00:15:18,670 --> 00:15:23,080
むしろリスク未定義の動作またはセキュリティ侵害のいくつかの種類より。

251
00:15:23,080 --> 00:15:25,950
>> これ以外にも、このプログラムのもう一つのバグがあります。

252
00:15:25,950 --> 00:15:30,180
私はこのプログラムに他に何を台無しにしている？

253
00:15:30,180 --> 00:15:32,740
私が説教したものを実践していませんでした。うん？

254
00:15:32,740 --> 00:15:34,760
[学生の答え、理解不能]グッド。

255
00:15:34,760 --> 00:15:36,880
私はメモリを解放していない。だから今は経験則

256
00:15:36,880 --> 00:15:43,150
あなたは、malloc（）を呼び出すいつにする必要があり、そのメモリを使用して設定が終了したら、自由に呼び出す必要があります。

257
00:15:43,150 --> 00:15:45,610
さて、ときに私はこのメモリを解放したいのでしょうか？

258
00:15:45,610 --> 00:15:49,780
おそらく、この最初の行は正しかったと仮定して、私はここでそれをやってみたいと思います。

259
00:15:49,780 --> 00:15:55,710
ので、私は、例えば、ここでそれを行うことができませんでした。なぜですか？

260
00:15:55,710 --> 00:15:57,860
ただスコープ外。だから我々は、ポインタの話をしているにもかかわらず、

261
00:15:57,860 --> 00:16:04,830
これは、xは、それが宣言された中括弧内のスコープである週2または3の問題である。

262
00:16:04,830 --> 00:16:11,000
だから、あなたは間違いなくそこにそれを解放することはできません。それを解放するために私の唯一のチャンスは、大体21行目の後である。

263
00:16:11,000 --> 00:16:15,170
これはかなり単純なプログラムである、あなたは一種のあなたの心を包んでしまえば、かなり簡単だった

264
00:16:15,170 --> 00:16:17,870
間違いがあった場合にどのような周りのプログラムは、やっている。

265
00:16:17,870 --> 00:16:20,500
そして、あなたが最初にそれを見なかったとしても、うまくいけば、今は少しは明らかだ

266
00:16:20,500 --> 00:16:23,870
これらの間違いはかなり簡単に解決すると簡単に作られている。

267
00:16:23,870 --> 00:16:28,720
しかし、プログラムが12以上の行の長さである場合には、100行の長い、長い50行だ

268
00:16:28,720 --> 00:16:31,150
論理的にそれを考えて、線であなたのコード行を歩いて、

269
00:16:31,150 --> 00:16:35,110
、常にバグを探して、可能性はなく、やることは特に楽しいです

270
00:16:35,110 --> 00:16:38,340
そしてそれを行うことも困難だし、Valgrindのようなツールが存在する理由です。

271
00:16:38,340 --> 00:16:40,900
私が先に行くとこれをやってみましょう：私は私の端末ウィンドウを開いてみましょう、

272
00:16:40,900 --> 00:16:45,400
とメモリは大丈夫だと思われるので、私はただ、メモリを実行しないようにしましょう​​。

273
00:16:45,400 --> 00:16:49,180
私は幸運取得しています。配列の最後に追加のバイトに行く

274
00:16:49,180 --> 00:16:51,060
あまりにも問題があるようには思えない。

275
00:16:51,060 --> 00:16:56,370
しかし、単に確認を行うことを意味健全性チェックを行い、それにもかかわらず、私を聞かせて

276
00:16:56,370 --> 00:16:58,320
これは実際に正しいかどうか。

277
00:16:58,320 --> 00:17:04,690
>> だからvalgrindの-vを実行してみましょう - リークチェック=フル、

278
00:17:04,690 --> 00:17:07,520
し、この場合のプログラムの名前は、メモリではなく、a.outです。

279
00:17:07,520 --> 00:17:10,760
だから私は先に行くとこれを行うことができます。 ENTERキーを押してください。

280
00:17:10,760 --> 00:17:14,109
親愛なる神。これは、その出力され、これは私が以前に言及したものです。

281
00:17:14,109 --> 00:17:17,550
しかし、あなたはここにナンセンスのすべてを読むことを学ぶ場合には、

282
00:17:17,550 --> 00:17:20,760
これのほとんどが面白くないというだけの診断が出力されます。

283
00:17:20,760 --> 00:17:24,829
何があなたの目が本当に探して欲しいとすると、エラーまたは無効のいずれかの言及である。

284
00:17:24,829 --> 00:17:26,800
問題を示唆する言葉。

285
00:17:26,800 --> 00:17:29,340
そして実際、ダウンここで間違って何が起こっているのか見てみましょう。

286
00:17:29,340 --> 00:17:35,230
私はいくつかの並べ替えの概要、持っている "出口で使用されている：1ブロック内の40バイトを"

287
00:17:35,230 --> 00:17:38,750
私はまだ実際にブロックが何であるかわからないんだけど、40バイト

288
00:17:38,750 --> 00:17:41,260
それはから来てどこに私が把握できるように、実際に感じている。

289
00:17:41,260 --> 00:17:45,030
40バイト。なぜ出口で使用されている40バイトは何ですか？

290
00:17:45,030 --> 00:17:48,780
より具体的には、我々がここで下にスクロールした場合、

291
00:17:48,780 --> 00:17:54,520
なぜ私は間違いなく40バイトを失っているか？うん？

292
00:17:54,520 --> 00:17:59,520
[学生の答え、理解不能]パーフェクト。ええ、その通りです。

293
00:17:59,520 --> 00:18:03,540
、そこに10個の整数があって、それらの各々は、2,4、または32ビットの大きさである

294
00:18:03,540 --> 00:18:08,300
あなたが提案したように、私は自由に呼び出していない、ので、ので、私は正確に40バイトを失ってしまった。

295
00:18:08,300 --> 00:18:13,460
それは、一つのバグだし、今のさらに少し下に見て、この隣に見てみましょう

296
00:18:13,460 --> 00:18:16,900
"無効なサイズ4の書いている。"さて、これは何ですか？

297
00:18:16,900 --> 00:18:21,150
このアドレスは、明らかに、何ベースの記法を表すのでしょうか？

298
00:18:21,150 --> 00:18:23,640
これは、16進数であり、あなたが0xで始まる番号を参照してくださいいつでも

299
00:18:23,640 --> 00:18:29,410
それは、我々は戻っての質問は、私が思うに、PSET 0のセクションのやり方をやっている、16進数を意味します

300
00:18:29,410 --> 00:18:34,090
これは、バイナリ、16進小数に変換するなど、ウォームアップエクササイズを行うだけであった。

301
00:18:34,090 --> 00:18:39,220
進、ちょうど人間の慣例により、通常のポインタを表すために使用され

302
00:18:39,220 --> 00:18:41,570
または、より一般的には、対処しています。それは、単に慣習的なやり方です

303
00:18:41,570 --> 00:18:45,340
それは読んで少し楽だから、それは、小数のようなものよりも少しコンパクトだ

304
00:18:45,340 --> 00:18:47,720
ほとんどの人間が使用するために、バイナリは無意味です。

305
00:18:47,720 --> 00:18:50,840
だから今、これはどういう意味ですか？無効な書き込みがあるようにまあ、それは見える

306
00:18:50,840 --> 00:18:54,480
memory.cのの21行目の大きさ4。

307
00:18:54,480 --> 00:18:59,180
それでは、21行目に戻りましょう、そして実際に、ここでその無効な書き込みです。

308
00:18:59,180 --> 00:19:02,640
だから、Valgrindは完全に私の手を握ると修正が何であるかを教えするつもりはないが、

309
00:19:02,640 --> 00:19:05,520
それは私が無効な書き込みをやっていることを検出しています。

310
00:19:05,520 --> 00:19:08,800
私はすべきではないことを4バイトに触れている、と明らかにそれは、からだ

311
00:19:08,800 --> 00:19:13,960
あなたが指摘したように、私の代わりに、[9] [10]をやって最大限に

312
00:19:13,960 --> 00:19:16,660
または[0]または間に何か。

313
00:19:16,660 --> 00:19:19,690
Valgrindので、あなたが今、プログラムを書いている任意の時間を実現

314
00:19:19,690 --> 00:19:24,190
ポインタを使用し、メモリを使用し、mallocをより具体的には、その

315
00:19:24,190 --> 00:19:27,080
間違いなくこの長いを実行する習慣を身につける

316
00:19:27,080 --> 00:19:30,890
しかし、非常に簡単にValgrindののコマンドをコピー＆ペースト

317
00:19:30,890 --> 00:19:32,650
そこにいくつかのエラーがあるかどうかを確認する。

318
00:19:32,650 --> 00:19:34,820
そしてそれは、あなたが出力を見るたびに圧倒されることでしょう

319
00:19:34,820 --> 00:19:39,430
しかし、ただ視覚的にすべての出力を解析し、エラーの言及を参照してくださいかどうかを確認

320
00:19:39,430 --> 00:19:43,190
または警告または無効であるか、または失われた。

321
00:19:43,190 --> 00:19:46,200
あなたのような音がどこかでしくじったことをどんな言葉。

322
00:19:46,200 --> 00:19:48,580
だからあなたのツールキットで、新しいツールだということを悟る。

323
00:19:48,580 --> 00:19:51,270
>> 今すぐ月曜日に、私たちはここに来る人々の全体の束を持っていた

324
00:19:51,270 --> 00:19:53,150
と連結リストの概念を表しています。

325
00:19:53,150 --> 00:20:00,970
そして、我々はどのような問題の解決策としてリンクリストを導入しました？

326
00:20:00,970 --> 00:20:04,590
うん？ [学生の答え、理解不能]グッド。

327
00:20:04,590 --> 00:20:06,530
配列はメモリがそれらに追加することはできません。

328
00:20:06,530 --> 00:20:09,440
あなたはすべてのあなたが得るのサイズ10の配列を割り当てる場合。

329
00:20:09,440 --> 00:20:13,690
あなたが最初にmallocを呼び出した場合は、reallocのような関数を呼び出すことができ、

330
00:20:13,690 --> 00:20:17,580
それはそれの終わりに向かってスペースがある場合は、配列を成長しようとすることができます

331
00:20:17,580 --> 00:20:21,610
誰も使っていないし、そこではない場合、それだけでどこかにあなたに大きな塊を見つけること。

332
00:20:21,610 --> 00:20:25,040
しかし、それは新しい配列にそれらのバイトのすべてをコピーします。

333
00:20:25,040 --> 00:20:28,310
これは非常に正しい解決策のように聞こえる。

334
00:20:28,310 --> 00:20:34,790
なぜこのような魅力的ではない？

335
00:20:34,790 --> 00:20:36,940
私はそれが動作するわけで、人間はこの問題を解決している。

336
00:20:36,940 --> 00:20:40,710
なぜ我々は、リンクリスト、月曜日にそれを解決しなければならなかったのか？うん？

337
00:20:40,710 --> 00:20:44,060
[学生の答えは、不明朗な]それは長い時間がかかることがあります。

338
00:20:44,060 --> 00:20:49,260
まだ別の1つですあなたは、mallocやrealloc又はcalloc関数を呼び出して、実際には、いつでも、

339
00:20:49,260 --> 00:20:52,470
いつでもあなたは、プログラムは、オペレーティング·システムと接続している

340
00:20:52,470 --> 00:20:54,310
あなたは、プログラムが遅くなってしまう。

341
00:20:54,310 --> 00:20:57,470
あなたがループ内で物事のこれらの種類をやっていると、あなたは本当に物事を遅くしている。

342
00:20:57,470 --> 00:21:00,740
あなたは、 "hello world"のタイプのプログラムの最も簡単のためにこれを気付くするつもりはない

343
00:21:00,740 --> 00:21:04,300
しかし、はるかに大規模なプログラムでは、メモリのために何度も何度も、オペレーティング·システムを求めて

344
00:21:04,300 --> 00:21:07,520
または何度も何度もそれを還元することは良いことしない傾向にある。

345
00:21:07,520 --> 00:21:11,210
プラス、それは単に知的なものだ - それは時間の無駄だ。

346
00:21:11,210 --> 00:21:16,490
新しい配列にすべてをコピーして、より多くのメモリを割り当てることがなぜ、リスク、

347
00:21:16,490 --> 00:21:21,980
あなたが実際に必要なだけのように多くのメモリを割り当てることができ、代替がある場合は？

348
00:21:21,980 --> 00:21:24,130
だからここでプラスとマイナスがあります。

349
00:21:24,130 --> 00:21:26,730
長所の一つは、今我々が活力を持っているということです。

350
00:21:26,730 --> 00:21:29,100
メモリのチャンクが自由であることである場合は関係ありません、

351
00:21:29,100 --> 00:21:32,070
私はただのポインタを介してこれらのパン粉を作るの並べ替えることができます

352
00:21:32,070 --> 00:21:34,470
一緒に私の全体のリンクリストを文字列に変換します。

353
00:21:34,470 --> 00:21:36,470
しかし、私は、少なくとも一つの料金を払っています。

354
00:21:36,470 --> 00:21:40,060
>> 私は、リンクされたリストを得ることにあきらめなければならないのですか？

355
00:21:40,060 --> 00:21:42,470
うん？ [学生の答え、理解不能]グッド。

356
00:21:42,470 --> 00:21:45,650
あなたがより多くのメモリを必要としています。今私は、これらのポインタのためのスペースが必要

357
00:21:45,650 --> 00:21:47,900
そして、この超単純なリンクリストの場合には

358
00:21:47,900 --> 00:21:51,410
わずか4バイトの整数を格納しようとしていることを、私たちは言い続ける

359
00:21:51,410 --> 00:21:54,240
よく、ポインタは4バイトなので、今私は文字通り倍増しました

360
00:21:54,240 --> 00:21:57,290
私はちょうどこのリストを保存するために必要なメモリの量。

361
00:21:57,290 --> 00:21:59,680
しかし、再び、これはコンピュータサイエンスの一定のトレードオフです

362
00:21:59,680 --> 00:22:03,440
時間と空間と開発の間、労力、およびその他のリソース。

363
00:22:03,440 --> 00:22:06,630
リンクリストを使用して別の欠点は何ですか？うん？

364
00:22:06,630 --> 00:22:10,150
[学生の答えは、不明朗]

365
00:22:10,150 --> 00:22:12,600
グッド。アクセスするのは容易ではない。我々は、もはや活用でき

366
00:22:12,600 --> 00:22:15,530
分割統治のような週は0原則。

367
00:22:15,530 --> 00:22:18,220
より具体的には、二分探索。そのためにもかかわらず、私たち人間

368
00:22:18,220 --> 00:22:20,400
このリストの真ん中がどこにあるか大体見ることができ、

369
00:22:20,400 --> 00:22:25,840
コンピュータは、このリンクリストは、最初に呼び出されたアドレスで開始したことを知っています。

370
00:22:25,840 --> 00:22:28,250
そして、それが0x123またはそのような何かです。

371
00:22:28,250 --> 00:22:30,990
とプログラムの唯一の方法は、中央の要素を見つけることができます

372
00:22:30,990 --> 00:22:33,350
実際に全体のリストを検索することです。

373
00:22:33,350 --> 00:22:35,500
そしてその時でさえ、それは文字通り全体のリストを検索する必要があるため、

374
00:22:35,500 --> 00:22:38,950
でも、一度は、ポインタを辿ることによって、中間要素に到達

375
00:22:38,950 --> 00:22:42,380
あなたは、プログラムは、潜在的には、このリストがどれくらい長いか見当がつかない

376
00:22:42,380 --> 00:22:45,250
あなたはそれの端を押すと、あなたはどのようにプログラムで知ってまで、

377
00:22:45,250 --> 00:22:48,600
あなたがリンクリストの末尾だということ？

378
00:22:48,600 --> 00:22:51,120
特別なNULLポインタので、再度、規則があります。

379
00:22:51,120 --> 00:22:53,870
このポインタを使用するのではなく、我々は間違いなく、それがいくつかのゴミ値になりたくない

380
00:22:53,870 --> 00:22:57,750
どこかでステージを降り、ポインティング、我々はそれがNULLハンドダウンになりたい、

381
00:22:57,750 --> 00:23:01,530
それが終わるところ我々が知っているように、我々は、このデータ構造では、この末端を持つように。

382
00:23:01,530 --> 00:23:03,410
>> 我々はこれを操作したい場合はどうなりますか？

383
00:23:03,410 --> 00:23:05,980
我々は、この視覚のほとんどを行なったし、人間と

384
00:23:05,980 --> 00:23:07,630
しかし、私たちが挿入を行いたい場合はどうなりますか？

385
00:23:07,630 --> 00:23:12,360
だから、元のリストは9、17、20、22、29、34であった。

386
00:23:12,360 --> 00:23:16,730
我々はその後、数55、それのためのノードのためにmalloc関数空間にしたかった場合はどうすればよい

387
00:23:16,730 --> 00:23:20,730
その後私たちは月曜日に行ったのと同様にリストに55を挿入したいですか？

388
00:23:20,730 --> 00:23:23,690
どのように我々はこれを行うのですか？まあ、アニタが来て、彼女は基本的にリストを歩いた。

389
00:23:23,690 --> 00:23:27,500
彼女は次、次、次、次、次の後、最初の要素から開始しました。

390
00:23:27,500 --> 00:23:29,500
最後に左側のすべての方法ダウンを打つ

391
00:23:29,500 --> 00:23:34,480
とまあ、これがNULLだと気づいた。ポインター操作が行われるために必要なだから何？

392
00:23:34,480 --> 00:23:37,980
端にあった者が、番号34は、彼の左手を上げに必要な

393
00:23:37,980 --> 00:23:46,220
55を指すように、55は新しいNULL終端であることが下を向いて自分の左腕を必要としていた。完了しました。

394
00:23:46,220 --> 00:23:49,540
ソートされたリストに55を挿入することは非常に簡単。

395
00:23:49,540 --> 00:23:51,800
そしてこれはどのように見えるかもしれません？

396
00:23:51,800 --> 00:23:55,690
>> 私が先に行くと、ここでいくつかのコード例を開いてみましょう。

397
00:23:55,690 --> 00:23:58,120
私はgeditを開くと、私は最初の2つのファイルを開いてもらおう。

398
00:23:58,120 --> 00:24:02,050
一つはlist1.hであり、私はちょうどこのコードの塊であったことを思い出させる

399
00:24:02,050 --> 00:24:04,920
我々はノードを表すために使用すること。

400
00:24:04,920 --> 00:24:13,040
ノードは、リスト内の次の事を指すのみその次のいわゆるNと呼ばれるintとポインタの両方を持っています。

401
00:24:13,040 --> 00:24:15,450
つまり、hファイルに今ある。なぜですか？

402
00:24:15,450 --> 00:24:19,090
、そこにこの大会だし、我々は、この膨大な量の自分自身を利用していない

403
00:24:19,090 --> 00:24:22,220
printf関数と他の関数を書いたが、人

404
00:24:22,220 --> 00:24:27,150
stdio.hという名前のファイルを作成することによって、世界への贈り物として、これらの機能のすべてを与えた。

405
00:24:27,150 --> 00:24:30,950
その後string.hであり、その後map.hはあり、これらのすべてのhファイルはあり

406
00:24:30,950 --> 00:24:34,410
あなたが他の人によって書かれた期間中に見られるか、または使用された可能性がある。

407
00:24:34,410 --> 00:24:38,470
通常、これらのインチhファイルのtypedefのような唯一のものです

408
00:24:38,470 --> 00:24:42,310
またはカスタム型や定数の宣言の宣言。

409
00:24:42,310 --> 00:24:47,890
あなたは、ヘッダファイルで関数の実装を入れてはいけません。

410
00:24:47,890 --> 00:24:50,570
あなたは、代わりに、ちょうど彼らのプロトタイプを置く。

411
00:24:50,570 --> 00:24:53,050
あなたは、彼らが必要なものを世界と共有したいものを置く

412
00:24:53,050 --> 00:24:55,640
自分のコードをコンパイルするために。だから、この習慣を身につけるために、

413
00:24:55,640 --> 00:24:59,110
私たちは同じことを行うことを決めた。 、list1.hではあまりなさそうだ

414
00:24:59,110 --> 00:25:02,070
しかし、我々は世界の人々に興味を持ってもらえるかもしれない何かを入れてきた

415
00:25:02,070 --> 00:25:05,030
誰が私たちのリンクリストの実装を使用したい。

416
00:25:05,030 --> 00:25:08,040
さて、list1.cで、私はこの全部を通ることはありません

417
00:25:08,040 --> 00:25:11,390
それは少し長いですので、このプログラムが、のプロンプトですぐにそれが本当の実行してみましょう。

418
00:25:11,390 --> 00:25:15,720
私はその後、list1に実行してみましょう、私は、list1にコンパイルしてみましょう、と何が表示されますです

419
00:25:15,720 --> 00:25:18,070
我々はここでシミュレートされたシンプルで小さなプログラムをしました

420
00:25:18,070 --> 00:25:20,990
それは私がリストに番号を追加したり削除したりできるようになるだろう。

421
00:25:20,990 --> 00:25:24,310
だから私は先に行くと、メニューオプション3に3を入力してみましょう。

422
00:25:24,310 --> 00:25:27,880
私は番号を挿入したい - レッツ9であった最初の数字は、何

423
00:25:27,880 --> 00:25:30,550
そして今、私は、リストは現在9ですと聞いています。

424
00:25:30,550 --> 00:25:33,760
私が先に行くと、別の挿入をやってみましょう、そう私は、メニュー·オプション3を打った。

425
00:25:33,760 --> 00:25:36,760
何番私が挿入したいのですか？ 17。

426
00:25:36,760 --> 00:25:39,220
入力します。そして私はちょうど1つのより多くをするつもりだ。

427
00:25:39,220 --> 00:25:41,720
私は22番を挿入してみましょう。

428
00:25:41,720 --> 00:25:45,850
だから我々は、我々は少し前にスライド形式で持っていたリンクリストの始まりを持っています。

429
00:25:45,850 --> 00:25:48,740
この挿入は、実際にはどのように起きているのか？

430
00:25:48,740 --> 00:25:52,000
確かに、22はリストの最後になりました。

431
00:25:52,000 --> 00:25:55,050
物語のように、我々は月曜日にステージ上で言って、ちょうど今recapped

432
00:25:55,050 --> 00:25:57,460
実際にコードで何が起こっている必要があります。

433
00:25:57,460 --> 00:25:59,700
のは、見てみましょう。私は、このファイル内で下にスクロールしてみましょう。

434
00:25:59,700 --> 00:26:01,720
我々は、いくつかの機能をごまかすよ

435
00:26:01,720 --> 00:26:05,630
しかし、我々は、下に行くと言う、insert関数があります。

436
00:26:05,630 --> 00:26:11,720
>> 我々は、このリンクリストに新しいノードを挿入取り掛かる方法を見てみましょう。

437
00:26:11,720 --> 00:26:14,550
リストはどこで宣言されている？まあ、みましょう、一番上にあるすべての道を上にスクロール

438
00:26:14,550 --> 00:26:19,970
と私のリンクリストは、基本的に初期値がNULLである単一のポインタとして宣言されていることに気づく。

439
00:26:19,970 --> 00:26:23,180
だから私は、一般的に我々は説教に対してきたここにグローバル変数を使用しています

440
00:26:23,180 --> 00:26:25,280
それは維持するためにあなたのコードが少し厄介になるので、

441
00:26:25,280 --> 00:26:29,080
それは怠惰な、通常のようなものだが、それは怠惰ではない、それは間違っていないですし、それは悪くはない

442
00:26:29,080 --> 00:26:33,660
生活の中であなたのプログラムの唯一の目的は、1つのリンクリストをシミュレートすることである場合。

443
00:26:33,660 --> 00:26:35,460
それは我々がやっているかを正確になります。

444
00:26:35,460 --> 00:26:39,100
だからではなく、メインでこれを宣言し、すべての関数に渡すために持っているよりも

445
00:26:39,100 --> 00:26:42,640
我々はこのプログラムに書いた、私たちの代わりに、ああ、ちょうどそれをグローバルに実現してみましょう

446
00:26:42,640 --> 00:26:47,060
このプログラムの全体の目的は、1つだけリンクされたリストを実証することであるので。

447
00:26:47,060 --> 00:26:50,700
だから、それは大丈夫な感じ。ここに私のプロトタイプがあり、我々は、これらのすべてを通ることはありません

448
00:26:50,700 --> 00:26:55,800
しかし、私は削除機能、検索機能、インサート機能、traverse関数を書いた。

449
00:26:55,800 --> 00:26:59,080
しかし、今度は、insert関数に戻ってダウン手放す

450
00:26:59,080 --> 00:27:01,490
、この1つはここに様子を見てください。

451
00:27:01,490 --> 00:27:09,940
インサートは、ライン上にある - ここに私達は行く。

452
00:27:09,940 --> 00:27:12,850
挿入します。私達が頼むつもりのでだから、任意の引数を取りません

453
00:27:12,850 --> 00:27:15,930
彼らは挿入したい数字には、この関数の内部ユーザー。

454
00:27:15,930 --> 00:27:19,410
しかし、最初に、我々は彼らにいくつかのスペースを与えるために準備をします。

455
00:27:19,410 --> 00:27:22,050
これは、他の例からのコピー＆ペーストのようなものです。

456
00:27:22,050 --> 00:27:25,110
その場合、我々はintを割り当てていたが、この時間は、我々はノードを割り当てています。

457
00:27:25,110 --> 00:27:27,910
私は実際にノードがどのように多くのバイトを覚えていないが、それは大丈夫です。

458
00:27:27,910 --> 00:27:30,460
sizeofは私のためにそれを把握することができます。

459
00:27:30,460 --> 00:27:33,340
そして、なぜ私は、ライン120でNULLをチェックするのですか？

460
00:27:33,340 --> 00:27:37,530
119行目で間違って行くことができるか？うん？

461
00:27:37,530 --> 00:27:40,530
[学生の答えは、不明朗]

462
00:27:40,530 --> 00:27:43,440
グッド。ちょうど私はあまりにも多くのメモリを要求してきたそうであるかもしれません

463
00:27:43,440 --> 00:27:47,020
か何かの間違った、オペレーティング·システムは、私を得るために十分なバイトがありません

464
00:27:47,020 --> 00:27:50,640
ので、それはNULLを返すことによって、できるだけ多くの信号を送り、私はそれをチェックしない場合

465
00:27:50,640 --> 00:27:54,710
と私はただやみくもにアドレスが返さ使用に進み、それはNULLである可能性があります。

466
00:27:54,710 --> 00:27:58,400
これは、いくつかの未知の値にすることができ、そうでない限り、私は良いこと - 

467
00:27:58,400 --> 00:28:00,590
実際に未知の値ではありません。それはNULLかもしれないので、私はしたくない

468
00:28:00,590 --> 00:28:02,550
それを乱用し、それを間接参照するリスクへ。

469
00:28:02,550 --> 00:28:07,410
その場合、私はちょうど戻って、私はまったく記憶を取り戻すなかったように私たちはふりをします。

470
00:28:07,410 --> 00:28:12,270
>> そうでなければ、私は、ユーザーが私に挿入するための番号を教えて教えて、私は、私たちの古い友人getIntを呼び出す

471
00:28:12,270 --> 00:28:15,530
そして、これは私たちが月曜日に導入された新しい構文であった。

472
00:28:15,530 --> 00:28:20,320
'NEWPTR-> n'はあなたがmallocで与えられたアドレスを取ることを意味します

473
00:28:20,320 --> 00:28:23,490
これは、新しいノードオブジェクトの最初のバイトを表します

474
00:28:23,490 --> 00:28:26,860
その後、Nという名前のフィールドに移動します。

475
00:28:26,860 --> 00:28:35,270
少しトリビアの質問：これは、コードのどのより不可解なラインと同等ですか？

476
00:28:35,270 --> 00:28:38,110
他にどのように私はこれを書いたのだろうか？刺しを取るしたいですか？

477
00:28:38,110 --> 00:28:41,480
[学生の答えは、不明朗]

478
00:28:41,480 --> 00:28:44,870
グッド。 。nを使用しますが、それはこのように非常に簡単ではない。

479
00:28:44,870 --> 00:28:47,090
私が最初に何をする必要がありますか？ [学生の答えは、不明朗]

480
00:28:47,090 --> 00:28:52,730
グッド。私は* newptr.nを行う必要があります。

481
00:28:52,730 --> 00:28:55,610
だから、これは新しいポインタが明らかにアドレスだと言っています。なぜですか？

482
00:28:55,610 --> 00:28:59,520
ので、それはmallocによって戻されました。 "そこに行く"と言って*のNEWPTR

483
00:28:59,520 --> 00:29:02,970
あなたがそこにいるに一度、その後、あなたは、より身近にnを使用することができます

484
00:29:02,970 --> 00:29:05,730
しかし、これは単に私たち人間がしようとしている場合は特に、少し醜い

485
00:29:05,730 --> 00:29:10,360
矢印付きポインタのすべての時間を描く、世界は、この矢印記法を標準化している、

486
00:29:10,360 --> 00:29:12,320
これは、正確に同じことをします。

487
00:29:12,320 --> 00:29:16,070
左のものはポインタであるときに>表記 - だからあなただけを使用します。

488
00:29:16,070 --> 00:29:18,790
それは実際の構造体の場合、そうでない場合は、、。nを使用します。

489
00:29:18,790 --> 00:29:25,800
そして、この：なぜ私はNULLにNEWPTR->次の初期化するのですか？

490
00:29:25,800 --> 00:29:28,610
私たちは、ステージの最後のダングリング左手オフをしたくない。

491
00:29:28,610 --> 00:29:31,630
我々は、このリストの終わりを意味する、それがまっすぐ下を向いて欲しい

492
00:29:31,630 --> 00:29:34,980
潜在的には、このノードにさらされる可能性がありますので、私たちはより良い、それがNULLであることを確認してください。

493
00:29:34,980 --> 00:29:38,460
そして、一般的には、あなたの変数またはデータメンバと構造体を初期化する

494
00:29:38,460 --> 00:29:40,470
何かにちょうど良い習慣です。

495
00:29:40,470 --> 00:29:45,170
ただゴミが存在し、一般的に存在し続けるさせるとおかしくなるあなたを取得

496
00:29:45,170 --> 00:29:48,650
あなたは、後で何かを忘れてしまった場合。

497
00:29:48,650 --> 00:29:51,590
>> ここでは、いくつかの例です。これは、再び、insert関数であり、

498
00:29:51,590 --> 00:29:54,930
変数が最初に呼び出された場合、私がチェックまず最初に、ある

499
00:29:54,930 --> 00:29:58,240
そのグローバル変数がNULLである場合、それがリンクされたリストがないことを意味します。

500
00:29:58,240 --> 00:30:02,460
我々は、任意の数字を挿入していないので、それはこの現在の番号を挿入するのは簡単なことです

501
00:30:02,460 --> 00:30:05,240
リストには、それだけでリストの先頭に属しているため。

502
00:30:05,240 --> 00:30:08,100
だから、これはアニタはちょうどふりをして、一人でここに立っていたときだった

503
00:30:08,100 --> 00:30:11,390
我々はノードを割り当てまで、誰も、ここでステージに上がってませんでした

504
00:30:11,390 --> 00:30:13,940
それから彼女は、初めて彼女の手を上げることができる

505
00:30:13,940 --> 00:30:17,420
他の皆は月曜日に彼女の後ステージに上がって来ていた場合。

506
00:30:17,420 --> 00:30:22,900
今ここに、これは私が言わなければならない小さなチェックである場合、nの新しいノードの値

507
00:30:22,900 --> 00:30:27,370
、現在の最初のノードのnの値を<されている

508
00:30:27,370 --> 00:30:29,930
それが始まったのリンクリストがあることを意味します。

509
00:30:29,930 --> 00:30:32,330
そこにリスト内の少なくとも1つのノードには、ですが、この新しい男

510
00:30:32,330 --> 00:30:37,230
その前に属しているので、私たちは周りのものを移動する必要があります。

511
00:30:37,230 --> 00:30:43,450
リストが単にで始まっている場合に他の言葉で、としましょう​​、

512
00:30:43,450 --> 00:30:48,100
だ単に番号17は、 - 実際に、我々はより明確にこれを行うことができます。

513
00:30:48,100 --> 00:30:56,010
我々は、最初に呼び出さここポインタ、との話を開始した場合

514
00:30:56,010 --> 00:30:59,870
と最初は、それはNULLだし、我々は9番を挿入

515
00:30:59,870 --> 00:31:02,510
9番は明らかにリストの先頭に属します。

516
00:31:02,510 --> 00:31:07,400
だから我々は単にアドレスや番号9をmallocされ、ここでそれを置くふりをしてみましょう。

517
00:31:07,400 --> 00:31:13,170
第一は、デフォルトでは9である場合は、我々が議論して最初のシナリオはただ、ここにしてみましょうポイントこの男を意味する

518
00:31:13,170 --> 00:31:15,790
NULLとしてこれを残して、今、私たちは9番を持っています。

519
00:31:15,790 --> 00:31:18,280
我々は挿入する次の番号は17です。

520
00:31:18,280 --> 00:31:22,420
17はこっちに属しているので、私たちはこれを通じて、いくつかの論理的なステップを行う必要があるとしている。

521
00:31:22,420 --> 00:31:26,060
我々は、のは、我々は8番を挿入したいと考えてみましょうそれを行う前に、代わりにしてみましょう。

522
00:31:26,060 --> 00:31:28,650
>> だから、便宜上、私はここで描くつもりです。

523
00:31:28,650 --> 00:31:30,760
しかし、覚えて、malloc関数はほとんどどこにでも置くことができます。

524
00:31:30,760 --> 00:31:33,460
しかし、描画のために、私はそれをここに置くことにしましょう​​。

525
00:31:33,460 --> 00:31:38,440
だから、僕は8番のノードを割り当てたふり、これはデフォルトではNULLです。

526
00:31:38,440 --> 00:31:42,800
何が今起こっていますか？物事のカップル。

527
00:31:42,800 --> 00:31:47,090
我々は、我々がこのようなポインタを更新した月​​曜日、ステージ上でこのミスを犯した

528
00:31:47,090 --> 00:31:51,890
次にこれをしなかったし、我々は主張して - 私たちはステージ上で皆を孤立。

529
00:31:51,890 --> 00:31:54,350
あなたはマストアイテムなので - ここで操作の順序は、重要である

530
00:31:54,350 --> 00:31:58,760
今ので、我々は宇宙空間に浮いているの一種であるこのノード9を失ってしまった。

531
00:31:58,760 --> 00:32:01,150
だから、これは月曜日に正しいアプローチではありませんでした。

532
00:32:01,150 --> 00:32:03,330
私たちは最初に何かをしなければならない。

533
00:32:03,330 --> 00:32:06,280
世界の状態は次のようになります。当初、8が割り当てられました。

534
00:32:06,280 --> 00:32:10,550
何が8を挿入するのは良い方法でしょうか？

535
00:32:10,550 --> 00:32:14,720
代わりに、最初にこのポインタを更新するのでは、だけではなく、ここで、このいずれかをアップデートしてください。

536
00:32:14,720 --> 00:32:17,720
だから我々は、このNULL文字を回すために起こっているコード行を必要とする

537
00:32:17,720 --> 00:32:22,020
ノード9で指している実際のポインタに、

538
00:32:22,020 --> 00:32:27,970
それから私達は無事にここにこの男を指すように、最初の変更ができます。

539
00:32:27,970 --> 00:32:31,330
今、私たちは2つの要素を持つリスト、リンクリストを持っています。

540
00:32:31,330 --> 00:32:33,580
そして、これは実際にここに、どんな風に見えますか？

541
00:32:33,580 --> 00:32:36,900
我々はコードを見れば、私はまさにそれをやったことがわかります。

542
00:32:36,900 --> 00:32:41,970
私はNEWPTR言ってきたが、この物語の中で、NEWPTRはこの男を指さした。

543
00:32:41,970 --> 00:32:45,520
>> だから私は、もう一つのことを描いてみましょう、と私はこれのために少しより多くの部屋を残しているはずです。

544
00:32:45,520 --> 00:32:48,540
だから小さな図面をお許しください。

545
00:32:48,540 --> 00:32:52,140
この男はNEWPTRと呼ばれています。

546
00:32:52,140 --> 00:32:57,940
ちょうど25の上方に - それは我々が並んで、数行前に宣言された変数です。

547
00:32:57,940 --> 00:33:03,430
そして、それは8を指している。だから私は、構造体に行く意味NEWPTR->次の、と言うとき

548
00:33:03,430 --> 00:33:07,910
NEWPTRによって指されているということなので、ここで我々は、そこに行くされています。

549
00:33:07,910 --> 00:33:13,990
その後、矢印次のフィールドを得ると言っているし、次に=があり、何が値入れて言ってるの？

550
00:33:13,990 --> 00:33:17,280
最初にあったもの値;第一にあった値はありますか？

551
00:33:17,280 --> 00:33:21,930
最初は、これは今では、このノードを指し示すべきであることを意味するように、このノードを指していた。

552
00:33:21,930 --> 00:33:25,660
言い換えれば、何が、私の筆跡とはいえとんでもない混乱に見える

553
00:33:25,660 --> 00:33:28,620
ちょうど周りにこれらの矢印を移動するシンプルなアイデアは何ですか

554
00:33:28,620 --> 00:33:31,560
ちょうどこの1ライナー付きコードへの変換を行います。

555
00:33:31,560 --> 00:33:38,110
次のフィールドの最初にあるものを格納して、その第一が実際に何であるか更新します。

556
00:33:38,110 --> 00:33:40,900
、のはこの一部を進んで、早送りに行こう

557
00:33:40,900 --> 00:33:44,220
そして今のところ、このテール挿入だけを見る。

558
00:33:44,220 --> 00:33:51,210
私はいくつかのノードの次のフィールドがNULLであることを見つけるポイントになると仮定します。

559
00:33:51,210 --> 00:33:53,410
そして物語は、詳細にこの時点で私は終わっていることに光沢

560
00:33:53,410 --> 00:33:58,170
私はライン142、先行ポインタここで別のポインタを紹介してきたということです。

561
00:33:58,170 --> 00:34:01,320
本質的には、物語の中で、この時点で、一度リストが長くなり、

562
00:34:01,320 --> 00:34:04,800
私は一種の2本の指を使って歩く必要がある私は、あまりにも遠くに行く場合があるため、

563
00:34:04,800 --> 00:34:08,219
単一長リストで覚えて、あなたは後方に行くことはできません。

564
00:34:08,219 --> 00:34:13,659
だからpredptrのこの考え方は、私の左指で、NEWPTR  -  NEWPTRません。

565
00:34:13,659 --> 00:34:17,199
ここに別のポインタは、私の他の指である、と私はちょうどリストを歩くようなものだ。

566
00:34:17,199 --> 00:34:22,179
それが存在する理由です。しかし、ここだけ簡単なケースのいずれかを検討してみましょう。

567
00:34:22,179 --> 00:34:26,620
そのポインタの次のフィールドがNULLの場合、論理的な含意は何ですか？

568
00:34:26,620 --> 00:34:30,840
このリストをトラバースしている場合は、NULLポインタを打つ？

569
00:34:30,840 --> 00:34:35,780
あなたは、リストの最後にしている、などのコードは、この一つの追加要素を追加する

570
00:34:35,780 --> 00:34:41,230
直感的な一種のは、その次のポインタがNULLである場合、そのノードを予定されている

571
00:34:41,230 --> 00:34:46,120
ので、これは現在NULLで、新しいノードのアドレスになるように、しかし、それを変更してください。

572
00:34:46,120 --> 00:34:52,260
だから我々は、ちょうど我々が誰かの左手を上げることにより、ステージ上に描いたコード内の矢印を描画している。

573
00:34:52,260 --> 00:34:54,070
>> そして、私は今のところで私の手を振るだろうという場合、

574
00:34:54,070 --> 00:34:58,020
私はそれが我々がこの種類の環境でそれを行うときに迷子になるのは簡単だと思うからといって、

575
00:34:58,020 --> 00:35:00,600
リストの途中に挿入するためにチェックしています。

576
00:35:00,600 --> 00:35:03,220
しかし、単に直感的に、あなたが把握したい場合にどうする必要があるもの

577
00:35:03,220 --> 00:35:06,600
いくつかの番号が真ん中に属する場所あなたがそれを歩かなければならないということです

578
00:35:06,600 --> 00:35:09,510
複数の指を持つ、複数のポインタ、

579
00:35:09,510 --> 00:35:12,920
検査によってそれが属する場所を見つけ出すには、要素<現在の一つです

580
00:35:12,920 --> 00:35:15,450
>現在の1、そして一度は、その場所を見つける

581
00:35:15,450 --> 00:35:20,400
その後、あなたは非常に慎重にポインタを動かしどこシェルゲームのこの種のことを行う必要があります。

582
00:35:20,400 --> 00:35:23,850
そしてその答えは、あなたが自分で自宅でこれを通じて理由をご希望の場合は、

583
00:35:23,850 --> 00:35:28,340
ただ、次の2行のコードに帰着するが、それらの行の順序は超重要です。

584
00:35:28,340 --> 00:35:31,390
あなたが誰かの手をドロップすると、間違った順序で誰か他の人を上げる場合があるため、

585
00:35:31,390 --> 00:35:34,580
もう一度、あなたはリストを孤立化してしまう可能性があります

586
00:35:34,580 --> 00:35:39,500
もっと概念的に要約すると、末尾に挿入は比較的簡単です。

587
00:35:39,500 --> 00:35:42,940
先頭に挿入も比較的簡単である、

588
00:35:42,940 --> 00:35:45,580
しかし、あなたは追加のポインタにこの時間を更新する必要があります

589
00:35:45,580 --> 00:35:47,930
ここにリストに番号5を圧迫する、

590
00:35:47,930 --> 00:35:51,560
その後途中で挿入がより一層の努力を伴う、

591
00:35:51,560 --> 00:35:56,130
非常に慎重に、その正しい場所に番号20を挿入する

592
00:35:56,130 --> 00:35:58,350
これは、17と22の間です。

593
00:35:58,350 --> 00:36:02,700
ですから、22に新しいノード20ポイントを持っているように何かをする必要があり、

594
00:36:02,700 --> 00:36:08,470
その後、ノードのポインタは最後に更新される必要がある？

595
00:36:08,470 --> 00:36:10,630
それは実際にそれを挿入するには、17です。

596
00:36:10,630 --> 00:36:14,080
だからもう一度、私はその特定の実装の実際のコードを延期します。

597
00:36:14,080 --> 00:36:17,280
>> 一見すると、それは少し圧倒的だが、それは本当に無限ループだ

598
00:36:17,280 --> 00:36:21,770
それは、ループループ、ループ、ループ、あなたはNULLポインタを打つとすぐに壊している

599
00:36:21,770 --> 00:36:24,590
その時点で、あなたは必要な挿入を行うことができます。

600
00:36:24,590 --> 00:36:30,960
これは、その後、代表的な連結リストの挿入コードです。

601
00:36:30,960 --> 00:36:34,590
、それは多くのようなものだった、と我々は一つの問題を解決したような気が

602
00:36:34,590 --> 00:36:36,940
しかし、我々は全体の他の1を導入しました。率直に言って、我々はこのすべての時間を費やしてきた

603
00:36:36,940 --> 00:36:40,540
ビッグOとΩ上、より迅速に問題を解決しようと、実行時間、

604
00:36:40,540 --> 00:36:43,270
そしてここで我々は後方に大きな一歩を取っている、それは感じている。

605
00:36:43,270 --> 00:36:45,380
そして、まだ、ゴール、データを格納する場合、

606
00:36:45,380 --> 00:36:48,010
我々は月曜日に言ったようにそれは、聖杯のように感じて、本当になる

607
00:36:48,010 --> 00:36:50,470
瞬時に物事を格納する。

608
00:36:50,470 --> 00:36:53,930
>> 実際には、我々はしばらくの間はさておきリンクリストを作りましたと仮定

609
00:36:53,930 --> 00:36:56,000
そして我々はその代わりに、テーブルの概念を導入しました。

610
00:36:56,000 --> 00:36:59,110
そして、ちょうど配列として一瞬テーブル考えるてみましょう。

611
00:36:59,110 --> 00:37:03,790
この配列は、この場合には、ここでいくつかの26要素、25 0〜を持っています

612
00:37:03,790 --> 00:37:07,940
そしてあなたが名前のストレージの塊を必要としていると仮定します。

613
00:37:07,940 --> 00:37:10,350
アリスとボブとチャーリーなど。

614
00:37:10,350 --> 00:37:12,880
そして、あなたはそれらの名前を格納するためにいくつかのデータ構造を必要としています。

615
00:37:12,880 --> 00:37:15,000
さて、あなたはリンクリストのようなものを使用することができます

616
00:37:15,000 --> 00:37:20,260
そしてあなたは、などの後にボブボブとチャーリーの前にアリスを挿入するリストを歩くと、可能性があります。

617
00:37:20,260 --> 00:37:23,850
そして、実際には、あなたはさておきとして、そのようなコードを見たい場合は、

618
00:37:23,850 --> 00:37:27,230
list2.hでは、我々はまさにそれをやることを知っている。

619
00:37:27,230 --> 00:37:30,610
我々は、このコードを通ることはありませんが、これは最初のサンプルの変形

620
00:37:30,610 --> 00:37:34,640
それは、我々が呼ばれる学生の前に見てきたもう一つの構造を紹介します

621
00:37:34,640 --> 00:37:40,330
その後どのように処理し、実際にリンクされたリストに格納すると、学生の構造体へのポインタである

622
00:37:40,330 --> 00:37:44,520
むしろより単純で小さな整数n。

623
00:37:44,520 --> 00:37:46,900
だから、実際の文字列を含むそこにコードがあり実現

624
00:37:46,900 --> 00:37:49,940
しかし手元にある目標は、本当に今効率の問題を解決するためであれば、

625
00:37:49,940 --> 00:37:53,380
我々はアリスと呼ばれるオブジェクトを与えている場合、それはいいのではないでしょう、

626
00:37:53,380 --> 00:37:56,020
我々は、データ構造内の正しい場所に彼女を入れたい

627
00:37:56,020 --> 00:37:58,860
それだけでアリスを置くために本当にいいだろうと思うようにそれは感じている、

628
00:37:58,860 --> 00:38:01,180
名前は最初の場所で、始まります。

629
00:38:01,180 --> 00:38:05,270
名前は第二の位置では、Bから始まり、ボブ、。

630
00:38:05,270 --> 00:38:09,580
配列を使用して、または、それをテーブルに、その時点でハッシュテーブルを呼び出してみましょう

631
00:38:09,580 --> 00:38:13,650
我々は正確にそれを行うことができます。私たちは、アリスのような名前を与えられた場合、

632
00:38:13,650 --> 00:38:16,700
アリスのような文字列は、-L-I-C-Eを入れますか？

633
00:38:16,700 --> 00:38:20,540
我々はhueristicを必要としています。私たちは、アリスのようないくつかの入力を取得する関数が必要

634
00:38:20,540 --> 00:38:24,610
と答えを返し、 "アリスはこの場所に置いてください。"

635
00:38:24,610 --> 00:38:28,720
そして、この関数は、このブラックボックスは、ハッシュ関数と呼ばれようとしています。

636
00:38:28,720 --> 00:38:32,330
>> ハッシュ関数は、 "アリス"のように、入力を受け取り、何か

637
00:38:32,330 --> 00:38:38,080
一般的にあなたへと戻り、アリスが属するいくつかのデータ構造内の数値場所。

638
00:38:38,080 --> 00:38:40,830
このケースでは、我々のハッシュ関数は比較的簡単であるべきです。

639
00:38:40,830 --> 00:38:47,510
私達のハッシュ関数を使用すると、文字私は気にしなければならない "アリス"を、与えられている場合、と言うべきでしょうか？

640
00:38:47,510 --> 00:38:55,660
最初の1つ。だから私は、[0]を見て、それから私は[0]の文字がある場合は、数字の0を返すと言う。

641
00:38:55,660 --> 00:39:01,130
それはBさんの場合は、1を返します。それはCの場合は、等2を返す、と。

642
00:39:01,130 --> 00:39:05,940
すべて0のインデックス、と私はアリスとボブその後を挿入できるようになるとその後チャーリーなど

643
00:39:05,940 --> 00:39:10,960
このデータ構造に変換します。しかし、問題はそこだ。

644
00:39:10,960 --> 00:39:13,060
アニタが再び一緒に来る場合はどうなりますか？

645
00:39:13,060 --> 00:39:17,510
我々は、アニタはどこに置けばいいの？彼女の名前は、あまりにも、文字で始まる

646
00:39:17,510 --> 00:39:20,330
我々はこの問題のさらに大きな混乱を作ったように、それは感じている。

647
00:39:20,330 --> 00:39:24,380
現在のデータ構造体に即時の挿入、一定時間の挿入を、持っている

648
00:39:24,380 --> 00:39:27,100
むしろワーストケースより線形、

649
00:39:27,100 --> 00:39:29,510
しかし、我々は、このケースではアニタで何ができる？

650
00:39:29,510 --> 00:39:34,110
実際には、2つのオプションは何ですか？うん？

651
00:39:34,110 --> 00:39:37,410
[学生の答え、理解不能]わかりましたので、私たちは別の次元を持つことができます。

652
00:39:37,410 --> 00:39:42,320
それは良いことだ。だから我々は、我々は月曜日に口頭での話のように3Dで物事を構築することができます。

653
00:39:42,320 --> 00:39:46,700
我々はここで別のアクセスを追加しますが、全く、私は、これは単純にしようとしていると仮定することができなかった。

654
00:39:46,700 --> 00:39:50,160
ここで全体の目標は、当面一定時間のアクセスを持つことである

655
00:39:50,160 --> 00:39:52,170
そう、それはあまりにも多くの複雑さを追加しているところ。

656
00:39:52,170 --> 00:39:55,970
このデータ構造にアニタを挿入しようとし、他のオプションは何ですか？うん？

657
00:39:55,970 --> 00:39:58,610
[学生の答え、理解不能]グッド。だから我々は、ダウンしてみんなを動かすことができる

658
00:39:58,610 --> 00:40:03,040
彼女が本当になりたい場所その後チャーリーボブとアリス、ダウングリグリと同じように、我々はアニタを置く。

659
00:40:03,040 --> 00:40:05,660
>> もちろん、今、これの副作用があります。

660
00:40:05,660 --> 00:40:09,000
このデータ構造は、我々はかつて人々を挿入する必要がないので、おそらく便利です

661
00:40:09,000 --> 00:40:11,250
しかし、我々は彼らが後でそこにいるかどうかを確認したいので、

662
00:40:11,250 --> 00:40:13,600
我々はデータ構造のすべての名前をプリントアウトしたい場合。

663
00:40:13,600 --> 00:40:15,850
我々は最終的に、このデータを使って何かをやろうとしている。

664
00:40:15,850 --> 00:40:20,810
だから今我々は一種の彼女がすることになっている場所はもはやませんアリス、上にねじ込まれました。

665
00:40:20,810 --> 00:40:23,880
またボブです、また、チャーリーです。

666
00:40:23,880 --> 00:40:26,060
だから多分これは、このような良いアイデアではありません。

667
00:40:26,060 --> 00:40:28,830
しかし、確かに、これは1つのオプションです。我々は、誰もシフトダウンができる

668
00:40:28,830 --> 00:40:32,240
または一体、アニタがゲームに遅れて来て、なぜ我々はちょうどアニタを入れてはいけません

669
00:40:32,240 --> 00:40:35,870
ここではなく、ここではなく、ここではなく、リストだけで少し低い彼女を入れてみましょう。

670
00:40:35,870 --> 00:40:38,680
しかし、その後、この問題が再び委譲を開始します。

671
00:40:38,680 --> 00:40:41,630
あなたは彼女の最初の名前に基づいて、瞬時にアリスを見つけることができるかもしれない。

672
00:40:41,630 --> 00:40:44,320
と瞬時にボブとチャーリー。しかし、あなたは、アニタ探す

673
00:40:44,320 --> 00:40:46,360
そしてあなたはうーん、見、アリスが邪魔になります。

674
00:40:46,360 --> 00:40:48,770
まあ、私はアリスの下をチェックしましょう​​。ボブはアニタではありません。

675
00:40:48,770 --> 00:40:51,850
チャーリーはアニタではありません。ああ、アニタがあります。

676
00:40:51,850 --> 00:40:54,720
そして、あなたは論理のその列車のすべての方法を継続する場合、

677
00:40:54,720 --> 00:41:00,690
この新しいデータ構造の中に見つけたり、アニタを挿入するの最悪実行時間は何ですか？

678
00:41:00,690 --> 00:41:03,280
それは右、O（n）のですか？

679
00:41:03,280 --> 00:41:06,280
最悪のケースであるため、アリス、ボブ、チャーリーはそこだ。 。 。

680
00:41:06,280 --> 00:41:10,150
ダウンして、 "Y"という名前の人にすべての方法なので、残された唯一つのスポットがあります。

681
00:41:10,150 --> 00:41:13,950
ありがたいことに、私たちは "Z"と呼ばれる人がいませんので、一番下にアニタを置く。

682
00:41:13,950 --> 00:41:16,040
>> 私たちは本当にその問題を解決していない。

683
00:41:16,040 --> 00:41:19,890
だから多分、我々はこの三次元を導入する必要もありません。

684
00:41:19,890 --> 00:41:22,230
我々はこの三次元を導入しない場合、それは、結局

685
00:41:22,230 --> 00:41:25,240
我々は完全にこれを行うことはできませんが、聖杯は、取得しようとしている

686
00:41:25,240 --> 00:41:28,370
一定時間の挿入と動的挿入するよう

687
00:41:28,370 --> 00:41:30,960
我々は、サイズ26のハードコード配列する必要はありません。

688
00:41:30,960 --> 00:41:34,400
私たちが望むように我々は多くの名前のように挿入することはできますが、みましょうここで我々の5分の休憩を取る

689
00:41:34,400 --> 00:41:38,790
し、適切にそれを行う。

690
00:41:38,790 --> 00:41:46,020
かしこまりました。私はそこにかなり人為的に物語を設定

691
00:41:46,020 --> 00:41:48,670
アリスとボブその後、その後チャーリーその後アニタを選択して

692
00:41:48,670 --> 00:41:51,000
名前は明らかにアリスと衝突するつもりだった。

693
00:41:51,000 --> 00:41:54,120
しかし、我々は月曜日に終了した質問は、それがどれだけ可能性が高いです

694
00:41:54,120 --> 00:41:56,370
あなたは、これらの種類の衝突を得るだろう？言い換えれば、

695
00:41:56,370 --> 00:42:00,490
我々は、この表の構造を使用して起動した場合、それは、実際には単なる配列です。

696
00:42:00,490 --> 00:42:02,460
26ヶ所のこのケースでは、

697
00:42:02,460 --> 00:42:05,740
私たちの入力が代わりに一様に分布している場合はどうでしょうか？

698
00:42:05,740 --> 00:42:09,620
それは、人工的にアリスとボブとチャーリーとDavidはないなどアルファベット順に

699
00:42:09,620 --> 00:42:12,380
それは一様にZまでにわたって配布されている

700
00:42:12,380 --> 00:42:15,220
>> 多分、我々はちょうど幸運を得るだろうし、我々は2つ​​のまたは2つのBのを持っているつもりはない

701
00:42:15,220 --> 00:42:17,640
非常に高い確率で、誰かが指摘したように、

702
00:42:17,640 --> 00:42:20,730
0から25までを行い、我々にこの問題を一般化していない場合

703
00:42:20,730 --> 00:42:26,060
しかし、言う、364または65を介して0、多くの場合、典型的な年の日数、

704
00:42:26,060 --> 00:42:31,170
との質問をし、 "この部屋に私達二人が同じ誕生日を持っている確率は何ですか？"

705
00:42:31,170 --> 00:42:34,600
それを別の言い方をすれば、確率は私たち二人で始まる名前を持っていることは何ですか？

706
00:42:34,600 --> 00:42:37,190
質問のソートは、同じですが、このアドレス空間

707
00:42:37,190 --> 00:42:39,940
このサーチスペース、誕生日の場合には大きく、

708
00:42:39,940 --> 00:42:42,820
我々は、アルファベットの文字よりも年間で非常に多くのより多くの日を持っているからです。

709
00:42:42,820 --> 00:42:44,910
衝突の確率は何ですか？

710
00:42:44,910 --> 00:42:48,410
さて、私たちは数学の反対の方法を考え出すことによってこれを考えることができます。

711
00:42:48,410 --> 00:42:50,580
無衝突の確率は何ですか？

712
00:42:50,580 --> 00:42:53,970
さて、ここで、この式は、何が確率だと言う

713
00:42:53,970 --> 00:42:58,770
彼らはユニークな誕生日を持っているこの部屋に一人だけは、あったら？

714
00:42:58,770 --> 00:43:01,190
それは100％だ。そのため部屋の中で一人だけがある場合、

715
00:43:01,190 --> 00:43:03,940
彼または彼女の誕生日は一年のうち365日のいずれかになります。

716
00:43:03,940 --> 00:43:08,650
365/365だからオプションは私に1の値を与えます。

717
00:43:08,650 --> 00:43:11,250
だから、現時点では問題になっている確率はちょうど1である。

718
00:43:11,250 --> 00:43:13,270
しかし、部屋の中で二人目があったら、

719
00:43:13,270 --> 00:43:16,490
自分の誕生日が異なる確率は何ですか？

720
00:43:16,490 --> 00:43:20,680
のみ364可能日は、うるう年は無視し、そこ

721
00:43:20,680 --> 00:43:23,580
自分の誕生日のために他の人と衝突しないように。

722
00:43:23,580 --> 00:43:31,920
だから、365分の364。第三者が入ってくるなら、それは365分の363だ、など。

723
00:43:31,920 --> 00:43:35,790
だから我々は、ますます小さくなっている、これらの画分を掛け合わ保つ

724
00:43:35,790 --> 00:43:40,720
把握するために私たちのすべてがユニークな誕生日を持っている確率は何ですか？

725
00:43:40,720 --> 00:43:43,570
しかし、その後、私たちは、もちろん、ただその答えを取得し、それを周りに反転することができます

726
00:43:43,570 --> 00:43:47,210
すべてのことを行うとマイナス1、我々は最終的には買ってあげる表現

727
00:43:47,210 --> 00:43:51,250
あなたは数学の本の背中を覚えていれば、それは、このような小さなものになります

728
00:43:51,250 --> 00:43:54,590
それははるかに簡単にグラフィカルに解釈されます。

729
00:43:54,590 --> 00:43:57,820
そしてここでこのグラフィックは、x軸上に誕生日の数を持っています

730
00:43:57,820 --> 00:44:02,030
や誕生日を持つ、とy軸上の人々の数が一致する確率です。

731
00:44:02,030 --> 00:44:06,060
そして、何これは言っていることは、あなたが持っている場合であっても、としましょう​​ということです

732
00:44:06,060 --> 00:44:10,860
22のような何か、23を選択してみましょう。

733
00:44:10,860 --> 00:44:13,160
部屋の中で22または23の人があるとすれば、

734
00:44:13,160 --> 00:44:17,100
これらの非常に少数の人々の2つが同じ誕生日を持っているとしている確率

735
00:44:17,100 --> 00:44:19,560
コンビナトリアルに、実際に超高い。

736
00:44:19,560 --> 00:44:23,450
わずか22人のクラスで、その50％の確率、セミナー、事実上、

737
00:44:23,450 --> 00:44:25,790
それらの人々の2は同じ誕生日を持っているとしている。

738
00:44:25,790 --> 00:44:28,520
ために、同じ誕生日を持つことができるので、多くの方法があります。

739
00:44:28,520 --> 00:44:31,110
さらに悪いことに、あなたはチャートの右側を見れば、

740
00:44:31,110 --> 00:44:34,040
あなたがそれで58の生徒とクラスを持っている時間によって、

741
00:44:34,040 --> 00:44:39,270
2人が誕生日を有する確率は、スーパー、超高、ほぼ100％です。

742
00:44:39,270 --> 00:44:41,880
さて、それは現実の生活に関する面白い事実のようなものだ。

743
00:44:41,880 --> 00:44:45,850
>> データ構造と情報を格納するための今でも影響、

744
00:44:45,850 --> 00:44:51,100
ちょうどあなたがデータの素敵な、きれいで、均一な分布を持っていると仮定することを意味

745
00:44:51,100 --> 00:44:53,650
そしてあなたは、物事の束に合わせて十分な大きさの配列を持っている

746
00:44:53,650 --> 00:44:59,360
あなたはユニークな場所で人々を取得するつもりだという意味ではありません。

747
00:44:59,360 --> 00:45:03,810
あなたは、衝突を持っているつもりです。 、それが呼ばれるように、ハッシュのこの概念は、そう

748
00:45:03,810 --> 00:45:07,450
"アリス"のような入力を取って、それを何らかの方法でマッサージ

749
00:45:07,450 --> 00:45:10,190
その後0または1または2のような答えを取り戻す。

750
00:45:10,190 --> 00:45:17,500
その機能からいくつかの出力を取り戻すが、衝突のこの確率に悩まされています。

751
00:45:17,500 --> 00:45:19,530
それでは、どのように我々はそれらの衝突を扱うことができますか？

752
00:45:19,530 --> 00:45:21,940
まあ、1ケースに、我々は、提案されたアイデアを取ることができます。

753
00:45:21,940 --> 00:45:25,100
私たちはただ、もう少し単純に、多分誰もシフトダウンしたり、することができます

754
00:45:25,100 --> 00:45:29,870
のではなく、みんなを移動させ、ちょうど利用できるスポットの底にアニタを動かしてみましょう。

755
00:45:29,870 --> 00:45:32,810
アリスが0になっているので、もし、ボブが1である、チャーリーは、2である

756
00:45:32,810 --> 00:45:35,260
私達はちょうど場所3でアニタを置くことにしましょう​​。

757
00:45:35,260 --> 00:45:38,860
そして、これはプロービング線形と呼ばれるデータ構造内のテクニックです。

758
00:45:38,860 --> 00:45:41,310
あなただけのこのラインを歩いていると、あなたはソートのプロービングしているので、線形

759
00:45:41,310 --> 00:45:43,640
データ構造で使用可能なスポットに。

760
00:45:43,640 --> 00:45:46,210
もちろん、これはO（n）に委譲。

761
00:45:46,210 --> 00:45:49,590
データ構造が本当にいっぱいある場合、それは25人が、すでにある

762
00:45:49,590 --> 00:45:54,120
その後アニタが登場し、彼女が位置Zがどうなるかで終わる、それは大丈夫です。

763
00:45:54,120 --> 00:45:56,540
彼女はまだフィットし、我々は後に彼女を見つけることができます。

764
00:45:56,540 --> 00:46:00,100
>> しかし、これは物事をスピードアップすることを目的に反していた。

765
00:46:00,100 --> 00:46:02,530
我々はその代わりに、この第三の次元を導入しましたので、どうでしょう？

766
00:46:02,530 --> 00:46:06,400
その技術は、一般的にはセパレートチェーンと呼ばれる、またはチェーンを抱えている。

767
00:46:06,400 --> 00:46:10,030
とハッシュテーブルは、この表の構造は何です、

768
00:46:10,030 --> 00:46:13,450
あなたのテーブルはちょうどポインターの配列です。

769
00:46:13,450 --> 00:46:18,230
しかし、どのようなこれらのポインタが指すことは推測は何ですか？

770
00:46:18,230 --> 00:46:21,970
リンクリスト。我々はこれらの世界の両方の長所を取るので、どうでしょう？

771
00:46:21,970 --> 00:46:26,500
我々は最初のインデックス用配列を使用

772
00:46:26,500 --> 00:46:32,070
データ構造の中に私たちは瞬時に、[1]、[30]またはなど[0]に行くことができます

773
00:46:32,070 --> 00:46:36,480
しかし私たちは、ある程度の柔軟性を持っていると我々はアニタとアリスとアダムを収めることができていること

774
00:46:36,480 --> 00:46:38,630
と他の名前、

775
00:46:38,630 --> 00:46:43,470
我々はその代わりに他の軸を任意に増やせてみましょう。

776
00:46:43,470 --> 00:46:47,340
そして、我々は最終的に、月曜日の時点では、リンクされたリストでその表現力を持っています。

777
00:46:47,340 --> 00:46:49,530
我々は、任意のデータ構造を成長することができます。

778
00:46:49,530 --> 00:46:52,450
代わりに、私達はちょうど、巨大な2次元配列を作ることができる

779
00:46:52,450 --> 00:46:57,190
しかし、それは2次元配列の行のいずれかの場合にひどい状況になるだろう

780
00:46:57,190 --> 00:47:01,280
名前がAで始まるたまたま追加の人のために十分な大きさではない

781
00:47:01,280 --> 00:47:04,200
禁じる神我々は巨大な2次元構造を再割り当てする必要があります

782
00:47:04,200 --> 00:47:06,600
名前のように多くの人々が、そこにという理由だけ

783
00:47:06,600 --> 00:47:09,480
Zの何という名前のように少数の人々がある場合は特に。

784
00:47:09,480 --> 00:47:12,170
それだけで非常に希薄なデータ構造になるだろう。

785
00:47:12,170 --> 00:47:15,400
だからそれは決して完璧ではないが、今、私たちは、少なくとも能力を持っている

786
00:47:15,400 --> 00:47:19,090
アリスやアニタが属するところ瞬時に検索するには、

787
00:47:19,090 --> 00:47:21,090
少なくとも縦軸の観点から、

788
00:47:21,090 --> 00:47:25,850
それから私達はちょうどこのリンクリストにアニタまたはアリスをどこに置くかを決めなければなりません。

789
00:47:25,850 --> 00:47:32,480
我々は物事を分類する気にしないのであれば、どのように迅速に私たちは、このような構造にアリスを挿入することができる？

790
00:47:32,480 --> 00:47:35,370
それは一定の時間です。 WE [0]に、そして誰の存在であれば、へのインデックス

791
00:47:35,370 --> 00:47:37,550
アリスは、そのリンクリストの先頭になります。

792
00:47:37,550 --> 00:47:40,000
しかし、それは大きな問題ではありません。アニタは、その後に沿って来る場合があるため

793
00:47:40,000 --> 00:47:42,160
手順のいくつかの番号以降、アニタはどこに属しますか？

794
00:47:42,160 --> 00:47:45,140
さて、[0]。 OOP。アリスは、そのリンクされたリストに既にある。

795
00:47:45,140 --> 00:47:47,760
>> しかし、我々はこれらの名前を並べ替える気にしない場合、

796
00:47:47,760 --> 00:47:53,580
私達はちょうどアリス以上、挿入アニタを移動できますが、でもそれは時定数である。

797
00:47:53,580 --> 00:47:57,010
アリスとアダムとのすべてのこれらの他の名前は、そこだとしても

798
00:47:57,010 --> 00:47:59,410
それは実際に物理的にそれらをずらしていない。なぜですか？

799
00:47:59,410 --> 00:48:04,090
私達はちょうど知っているリンクリストと一緒にここにいたので、これらのノードはとにかくアールたか？

800
00:48:04,090 --> 00:48:06,550
あなたがしなければならないのは、パン粉を移動することです。

801
00:48:06,550 --> 00:48:10,930
周りに矢印を移動し、あなたは物理的に周囲に任意のデータを移動する必要はありません。

802
00:48:10,930 --> 00:48:14,610
だから我々は即座に、その場合には、アニタを挿入することができます。時定数。

803
00:48:14,610 --> 00:48:20,250
だから我々は一定時間のルックアップ、およびアニタのような誰かの定数時間挿入しています。

804
00:48:20,250 --> 00:48:22,740
しかし、世界し過ぎのようなもの。

805
00:48:22,740 --> 00:48:28,510
我々は後でアリスを見つけたい場合はどうなりますか？

806
00:48:28,510 --> 00:48:31,050
我々は後でアリスを見つけたい場合はどうなりますか？

807
00:48:31,050 --> 00:48:35,690
どのように多くの手順を実行することは取るつもりですか？

808
00:48:35,690 --> 00:48:37,850
[学生の答えは、不明朗]

809
00:48:37,850 --> 00:48:40,950
その通りです。リンクリストの国のアリスの前に人々の数。

810
00:48:40,950 --> 00:48:45,420
我々のデータ構造は、再び、この縦のアクセスを持っているので、だからそれは、非常に完璧ではあり​​ません

811
00:48:45,420 --> 00:48:50,240
そして、それがぶら下がってこれらのリンクされたリストを持っています - 実際には、うまくいくよう配列を描画しないようにしましょう​​。

812
00:48:50,240 --> 00:48:56,020
それは、これらのリンクされたリストは、このような少し何かしているように思えてそれをオフにぶら下がっています。

813
00:48:56,020 --> 00:48:59,110
しかし、問題はあるかアリスとアダムと、これらのすべての他の名前

814
00:48:59,110 --> 00:49:01,720
、あそこにますます終わる

815
00:49:01,720 --> 00:49:04,810
誰かがステップの束を取ってしまう可能性を見つける、

816
00:49:04,810 --> 00:49:06,670
は、リンクリストを横断しなければならないbcause

817
00:49:06,670 --> 00:49:08,090
これは、線形動作です。

818
00:49:08,090 --> 00:49:14,270
だから本当に、その後、挿入時間は、最終的には、nはリスト内の要素の数はO（n）です。

819
00:49:14,270 --> 00:49:21,780
で割って、任意に、mはリンクリストの数がm、呼び出してみましょう

820
00:49:21,780 --> 00:49:24,500
我々は、この縦軸に持っている。

821
00:49:24,500 --> 00:49:27,180
言い換えれば、我々は本当に名前の一様分布を仮定した場合、

822
00:49:27,180 --> 00:49:30,150
全く非現実的。他の人よりも、いくつかの文字の多くは明らかにありま​​す。

823
00:49:30,150 --> 00:49:32,580
>> しかし、我々は一瞬一様分布と仮定した場合、

824
00:49:32,580 --> 00:49:37,350
そして我々は全人口をN、およびメートル総チェーンた

825
00:49:37,350 --> 00:49:40,630
これらの鎖の各々の長さは、次に私達に利用できる

826
00:49:40,630 --> 00:49:44,380
かなり単純合計は、n鎖の数で割ったものになるだろう。

827
00:49:44,380 --> 00:49:48,900
ので、n / mである。我々はすべて数学的に巧妙なことができますどこでも、ここだ。

828
00:49:48,900 --> 00:49:53,030
これらの固定数があるので、mは定数である。

829
00:49:53,030 --> 00:49:54,620
あなたは、冒頭で配列を宣言するつもりだ

830
00:49:54,620 --> 00:49:58,450
そして我々は、サイズ変更縦軸をしていない。定義によって、それが固定されたままになります。

831
00:49:58,450 --> 00:50:01,220
それは変化だという、いわば、横軸のみです。

832
00:50:01,220 --> 00:50:04,760
したがって、厳密には、これは一定である。だから今は、挿入時間

833
00:50:04,760 --> 00:50:09,700
かなりO（n）である。

834
00:50:09,700 --> 00:50:12,410
だからそれはすべてそのはるかに良い感じがしない。

835
00:50:12,410 --> 00:50:14,940
しかし、真実はここに何ですか？まあ、すべてのこの時間、週間、

836
00:50:14,940 --> 00:50:20,640
私たちは言ってきたはO（n²）である。 O（n）で、2×nの²、 -  nは、2で割った値です。 。 。 ECH。

837
00:50:20,640 --> 00:50:23,580
それはちょうどn個の²のだ。しかし、今、学期のこの部分では、

838
00:50:23,580 --> 00:50:25,560
我々は再び現実の世界の話を始めることができます。

839
00:50:25,560 --> 00:50:31,520
とn / mはちょうどn個だけの場合よりも絶対的に速くなります。

840
00:50:31,520 --> 00:50:35,170
あなたは千の名前を持っていて、複数のバケットにそれらを分割する場合

841
00:50:35,170 --> 00:50:37,820
あなたは、これらの鎖の各々の唯一の10名を持つように

842
00:50:37,820 --> 00:50:41,670
絶対に10の事を検索すると、千の事よりも高速であることを行っている。

843
00:50:41,670 --> 00:50:43,740
それで、今度の問題セットの一つがあなたに挑戦しようとしている

844
00:50:43,740 --> 00:50:46,100
まさにそのことについて考えることにもかかわらず、ええ、

845
00:50:46,100 --> 00:50:49,520
漸近的に、数学的に、これはまだほんの線形であり、

846
00:50:49,520 --> 00:50:51,700
物事を見つけようとするときには、一般的に吸う。

847
00:50:51,700 --> 00:50:54,530
現実には、それよりも速くなるだろう

848
00:50:54,530 --> 00:50:56,520
このため、除数の。

849
00:50:56,520 --> 00:50:58,310
それで、もう一度、このトレードオフがあるように起こっている

850
00:50:58,310 --> 00:51:01,390
理論と現実の間に、この紛争、

851
00:51:01,390 --> 00:51:03,550
とノブの1学期には、この時点で回転を開始します

852
00:51:03,550 --> 00:51:07,510
我々は一種のsemsterの終わりのための準備として、現実1の詳細です

853
00:51:07,510 --> 00:51:09,280
我々は、Webプログラミングの世界を紹介として

854
00:51:09,280 --> 00:51:11,530
本当に、性能、ユーザーがしようとしているので、カウントしようとしている場所

855
00:51:11,530 --> 00:51:14,880
貧弱な設計上の決定を感じ、感謝を開始します。

856
00:51:14,880 --> 00:51:19,950
>> だからあなたは、リンクを実装するにはどうすればいい -  31の要素を持つハッシュテーブル？

857
00:51:19,950 --> 00:51:22,600
前の例では、誕生日について任意であった。

858
00:51:22,600 --> 00:51:26,190
誰かが1月1日または2月1日の誕生日を持っている場合、我々はこのバケツに入れます。

859
00:51:26,190 --> 00:51:28,960
それは1月2日、2月2日、3月2日の場合、我々はこのバケツに入れます。

860
00:51:28,960 --> 00:51:32,220
それは31だったのはそういうわけです。どのようにハッシュテーブルを宣言するのですか？

861
00:51:32,220 --> 00:51:37,480
それは非常に単純なことができ、ノード*テーブルは、[31]それは私の任意の名前です。

862
00:51:37,480 --> 00:51:42,400
これは、ノードにくれ31ポインタを与える

863
00:51:42,400 --> 00:51:45,370
そしてそれは私がリンクリストに31のポインタを持つことができます

864
00:51:45,370 --> 00:51:48,800
これらのチェインは、最初はNULLである場合でも同様です。

865
00:51:48,800 --> 00:51:54,860
私は、 "アリス"、 "ボブ"、 "チャーリー"を格納する場合は、私は入れて何をしたいのですか？

866
00:51:54,860 --> 00:51:57,010
さて、私たちは構造体にそれらの事をラップする必要があります

867
00:51:57,010 --> 00:52:00,530
私たちは、アリスは、ボブを指すようにチャーリーを指すように、など。必要があるため、

868
00:52:00,530 --> 00:52:04,940
我々は、ちょうど名前だけを持つことができないので、ここでノードと呼ばれる新しい構造を作成することができます。

869
00:52:04,940 --> 00:52:08,310
>> 実際のノードとは何ですか？この新しいリンクリスト内のノードとは何ですか？

870
00:52:08,310 --> 00:52:11,840
ワードと呼ばれる最初のものは、人の名前です。

871
00:52:11,840 --> 00:52:14,340
LENGTHは、おそらく、人間の名前の最大の長さに関係する

872
00:52:14,340 --> 00:52:18,210
、20が何であれ、30、クレイジーコーナーケースが40文字、

873
00:52:18,210 --> 00:52:22,680
と1は何のためですか？それだけで余分なNULL文字を、\ 0です。

874
00:52:22,680 --> 00:52:27,410
だから、このノードは、自身の内部に "何か"をラップしている

875
00:52:27,410 --> 00:52:29,640
それはまた次に呼び出さポインタを宣言しています

876
00:52:29,640 --> 00:52:32,580
ので、我々はチャーリーにボブにチェーンアリス缶などという。

877
00:52:32,580 --> 00:52:36,700
NULLを指定することもできますが、必ずしも必要はありません。

878
00:52:36,700 --> 00:52:40,110
これらのハッシュテーブル上で何か質問はありますか？うん？

879
00:52:40,110 --> 00:52:46,190
[質問をする学生、不明朗]配列 - 良い質問。

880
00:52:46,190 --> 00:52:50,120
なぜ、この配列のchar単語だけではなく、char *型は何ですか？

881
00:52:50,120 --> 00:52:53,830
この幾分恣意例では、私は頼らざるをしたくなかった

882
00:52:53,830 --> 00:52:56,190
オリジナル名ごとに、mallocへ。

883
00:52:56,190 --> 00:52:59,530
私は、文字列のためのメモリの最大量を宣言したかった

884
00:52:59,530 --> 00:53:06,020
ので、私は構造アリス\ 0にコピーして、mallocやfreeなどに対処する必要がなかったこと。

885
00:53:06,020 --> 00:53:11,710
しかし、私は宇宙利用をより意識になりたい場合は、それを行うことができます。良い質問です。

886
00:53:11,710 --> 00:53:14,780
だからこれから一般化してみましょう

887
00:53:14,780 --> 00:53:18,350
そしてより一般的にはデータ構造に、今日の残りの部分を集中

888
00:53:18,350 --> 00:53:21,170
と我々は同じファンダメンタルズを使用して解くことができる他の問題

889
00:53:21,170 --> 00:53:24,590
データ構造自体は彼らの細目で異なるかもしれませんが。

890
00:53:24,590 --> 00:53:27,910
>> だから、コンピュータサイエンスで判明し、木は非常に一般的です。

891
00:53:27,910 --> 00:53:29,760
そして、あなたは、家系図のようなツリーの一種と考えることができます

892
00:53:29,760 --> 00:53:31,830
いくつかの根、またはいくつかの女家長家長は、そこここで、

893
00:53:31,830 --> 00:53:34,540
おばあちゃんやおじいちゃんまたはそれ以前のバック、

894
00:53:34,540 --> 00:53:38,880
その下にママとパパ、または様々な兄弟などです。

895
00:53:38,880 --> 00:53:42,500
だから、ツリー構造は、ノードを持っており、それが子供を持っている

896
00:53:42,500 --> 00:53:45,260
各ノードに対して、通常、0個以上の子。

897
00:53:45,260 --> 00:53:47,320
ここでこの画像に表示されている専門用語の一部と

898
00:53:47,320 --> 00:53:50,630
あるエッジに小さな子供や孫のいずれか

899
00:53:50,630 --> 00:53:52,330
誰が、それらから発せなく矢を持っていない

900
00:53:52,330 --> 00:53:55,070
それらは、いわゆる葉であり、内側に誰も

901
00:53:55,070 --> 00:53:58,790
内側のノードであり、あなたはそれをそれらの線に沿って何かを呼び出すことができます。

902
00:53:58,790 --> 00:54:01,430
しかし、この構造はかなり一般的です。この1つは少し任意です。

903
00:54:01,430 --> 00:54:04,930
我々は、我々は右側に三人の子供を持って、左の上の1つの子を持つ

904
00:54:04,930 --> 00:54:06,830
底部の2つの子供が残っています。

905
00:54:06,830 --> 00:54:10,740
そこで、我々は、異なるサイズの木を持つことができますが、我々は物事を標準化するために起動した場合

906
00:54:10,740 --> 00:54:15,330
と、以前短いから二分探索でパトリックビデオからリブログ思い出すかもしれない

907
00:54:15,330 --> 00:54:19,490
オンラインで、バイナリ検索によって、アレイに実装する必要はありません

908
00:54:19,490 --> 00:54:21,410
黒板上の紙または片。

909
00:54:21,410 --> 00:54:25,490
あなたがより洗練されたデータ構造にあなたの番号を格納したいと仮定します。

910
00:54:25,490 --> 00:54:27,680
あなたはこのようなツリーを作成することができます。

911
00:54:27,680 --> 00:54:35,290
あなたがC言語で宣言されたノードを持つことができ、そのノードは、その中に少なくとも2つの要素を持つことができます。

912
00:54:35,290 --> 00:54:39,470
一つは、あなたが保存したい番号であり、他方が - まあ、我々は1つの多くを必要とする。

913
00:54:39,470 --> 00:54:41,540
他のは、その子である。

914
00:54:41,540 --> 00:54:45,150
だからここでは、別のデータ構造です。この時間は、ノードが数nを記憶するものとして定義されています

915
00:54:45,150 --> 00:54:49,060
してから、2つのポインタが、左の子と右の子。

916
00:54:49,060 --> 00:54:52,100
そして、彼らは任意じゃない。この木について興味深い何ですか？

917
00:54:52,100 --> 00:55:00,550
>> 我々はこれを広げてきたか、パトリックは彼のビデオでそれをどのようにレイアウトする方法のパターンとは何ですか？

918
00:55:00,550 --> 00:55:02,790
いくつかの並べ替えがここそこで起こっていることは明らかのようなものだ、

919
00:55:02,790 --> 00:55:04,460
しかし、単純なルールは何ですか？うん？

920
00:55:04,460 --> 00:55:08,350
[学生の答えは、不明朗]

921
00:55:08,350 --> 00:55:12,040
パーフェクト。この一瞥場合は、左側の小さな数字を参照してください

922
00:55:12,040 --> 00:55:14,690
大きな左の数字が、すべてのノードのために本当のことです。

923
00:55:14,690 --> 00:55:20,370
各ノードに対して、それよりも、その左の子より少なく、それよりも大きく、その右の子。

924
00:55:20,370 --> 00:55:25,210
私はこのデータ構造を検索したい場合はどうすればよいこれが今意味する、と言う、44番ですが、

925
00:55:25,210 --> 00:55:29,320
私は今、なぜならこれらのより複雑なデータ構造のすべてと同様に、ルートから起動する必要があります

926
00:55:29,320 --> 00:55:31,910
我々はまだ始まったばかり、一つのことへのポインタを持っている。

927
00:55:31,910 --> 00:55:35,010
この場合には、初めはrootです。それは、左端ではありません

928
00:55:35,010 --> 00:55:39,530
それは、この構造のルートです。だから私はここには55の見て、私は44を探しています。

929
00:55:39,530 --> 00:55:41,430
どの方向に私は行きたいですか？

930
00:55:41,430 --> 00:55:45,680
まあ、私は明らかに、右に大きくなりすぎようとしているので、左に行きたい。

931
00:55:45,680 --> 00:55:49,050
だからここに気付くには、概念的には半分に木をチョッピングの一種だ

932
00:55:49,050 --> 00:55:51,700
あなたは、右手側に下って行くことはありませんしているので。

933
00:55:51,700 --> 00:55:55,410
だから今は55から33に行く。それは、数では小さすぎます。

934
00:55:55,410 --> 00:56:01,590
私は44を探していますが、今は44がこのツリーにある場合は、私は右に明らかに行くことができます知っている。

935
00:56:01,590 --> 00:56:04,460
だからもう一度、私は半分にツリー剪定だ。

936
00:56:04,460 --> 00:56:06,780
これは、電話帳に概念的にほとんど同じです。

937
00:56:06,780 --> 00:56:09,510
それは、私たちが黒板に紙でやったことと同じだ

938
00:56:09,510 --> 00:56:13,940
それは私たちが実際に行うことができ、より洗練された構造だ

939
00:56:13,940 --> 00:56:16,880
これは、分割して、アルゴリズムの設計によって征服

940
00:56:16,880 --> 00:56:19,420
そして実際に、このような構造を横断 - おっと。

941
00:56:19,420 --> 00:56:22,870
それは、 "この道を行くか、その道を行く"だけだ、このような構造を、横断

942
00:56:22,870 --> 00:56:26,870
セクションでそれを実装するときに、最初にあなたの心を曲げすべてのコードを意味します

943
00:56:26,870 --> 00:56:31,270
または、再帰または反復を使用して、二分探索のために、自宅でそれを歩く

944
00:56:31,270 --> 00:56:35,060
それは、首の痛みです。真ん中の要素を検索し、次に上下にあなたの丸めを行う。

945
00:56:35,060 --> 00:56:39,230
>> 我々が今再び再帰を使用することができますので、美しさはこれにあります、

946
00:56:39,230 --> 00:56:43,760
しかし、はるかにきれい。確かに、あなたは数55にいて、あなたが44を検索する場合は、

947
00:56:43,760 --> 00:56:48,450
この場合、左に行く、あなたは何をしますか？あなたは正確に同じアルゴリズムを実行します。

948
00:56:48,450 --> 00:56:51,560
次に、あなたが左または右に移動し、ノードの値を確認します。

949
00:56:51,560 --> 00:56:53,670
次に、左または右に行くと、ノードの値を確認します。

950
00:56:53,670 --> 00:56:56,710
これは完全に再帰に適しています。

951
00:56:56,710 --> 00:57:00,920
過去に我々は、再帰を含むいくつかのかなり恣意的な例をやったので、あっても

952
00:57:00,920 --> 00:57:03,430
それは、データstucturesと、再帰的にする必要はありませんでした

953
00:57:03,430 --> 00:57:07,820
特に木々、それは、問題を取るのこのアイデアの完璧なアプリケーションです

954
00:57:07,820 --> 00:57:12,920
それを縮小してから、同じタイプのが、より小さい、プログラムを解決。

955
00:57:12,920 --> 00:57:14,590
>> だから我々は導入することができ、別のデータ構造があります。

956
00:57:14,590 --> 00:57:18,760
この1は不可解に見えるように一目見ただけで設計されていますが、この1つは驚くべきことださ。

957
00:57:18,760 --> 00:57:25,090
だから、これは、単語の検索から継承されトライ、トライ、と呼ばれるデータ構造である

958
00:57:25,090 --> 00:57:30,210
これは、再試行-valを宣告されていませんが、それは世界がこれらの事を呼んでいるものだ。しようとします。 T-R-I-E。

959
00:57:30,210 --> 00:57:35,190
それはある種のツリー構造ですが、トライの各ノード

960
00:57:35,190 --> 00:57:41,280
どのように見える？略称のようなものだので、これは少し誤解を招くおそれがあります。

961
00:57:41,280 --> 00:57:45,960
しかし、それはこのトライの各ノードが実際には配列であるように見えます。

962
00:57:45,960 --> 00:57:48,840
そして、この図の作者は、それを示していないにもかかわらず、

963
00:57:48,840 --> 00:57:54,130
この場合には、このトライは、その目的は生活の中で単語を格納するデータ構造です。

964
00:57:54,130 --> 00:57:57,330
-L-I-C-EまたはB-O-Bのような。

965
00:57:57,330 --> 00:58:02,480
などと、このデータを格納し、アリスとボブとチャーリーとアニタ方法と

966
00:58:02,480 --> 00:58:06,970
それは、トライでアリスを格納することにより、配列を使用しています

967
00:58:06,970 --> 00:58:09,820
我々は、配列のように見えるルートノードから開始

968
00:58:09,820 --> 00:58:12,080
そしてそれは簡単な表記法で書かれている。

969
00:58:12,080 --> 00:58:15,070
それとは名前がなかったので著者はabcdefgで省略。

970
00:58:15,070 --> 00:58:19,150
彼らは唯一のMとPとTを示したが、このケースでは、

971
00:58:19,150 --> 00:58:22,780
の現在のいくつかの名前に離れて、アリスとボブとチャーリーから移動することができます。

972
00:58:22,780 --> 00:58:25,670
マクスウェルは、この図に実際にある。

973
00:58:25,670 --> 00:58:29,570
それでは、どの著者ストアのM-X-W-E-L-Lがした？

974
00:58:29,570 --> 00:58:36,990
彼または彼女はルートノードから開始され、ので、大体[M] 13は、アレイ内の13番目の場所に行きました。

975
00:58:36,990 --> 00:58:40,750
そこから、ポインタがあります。

976
00:58:40,750 --> 00:58:42,760
別の配列に至るポインタ。

977
00:58:42,760 --> 00:58:47,880
そこから著者は、左上にそこに描かれているように、場所に、その配列のインデックスを作成

978
00:58:47,880 --> 00:58:52,250
それから彼または彼女は、別の配列にそのポインタを追っ

979
00:58:52,250 --> 00:58:55,460
と場所Xの部分にポインタに行ってきました

980
00:58:55,460 --> 00:58:59,840
その後、次の配列位置W、E、L、Lなど、内

981
00:58:59,840 --> 00:59:03,090
そして最後に、実際にはこれに絵を入れてみてみましょう。

982
00:59:03,090 --> 00:59:05,380
コー​​ド内のノードのような外観とは何でしょうか？

983
00:59:05,380 --> 00:59:11,820
トライのノードは、複数のノードへのポインタの配列が含まれています。

984
00:59:11,820 --> 00:59:16,090
しかし、また、少なくとも、この実装では、ブール値のいくつかの種類があるはずだ。

985
00:59:16,090 --> 00:59:18,770
私はそれis_word呼び出すために起こる。なぜですか？

986
00:59:18,770 --> 00:59:22,670
あなたはマクスウェルを挿入しているときは、挿入していないので

987
00:59:22,670 --> 00:59:25,300
このデータ構造には何も。

988
00:59:25,300 --> 00:59:27,480
あなたがXを書いていないしているMを書いていないしている

989
00:59:27,480 --> 00:59:30,240
あなたのやっていることは、次のポインタです。

990
00:59:30,240 --> 00:59:33,360
その後、M、表すポインタを表すポインタ

991
00:59:33,360 --> 00:59:36,310
その後、その後、X、W、E、L、Lを表すポインタ

992
00:59:36,310 --> 00:59:41,950
しかし、何を終わりに行う必要があることは確認して行くの一種ですが、私はこの場所に到達した。

993
00:59:41,950 --> 00:59:45,560
データ構造の中にここで終了という言葉がありました。

994
00:59:45,560 --> 00:59:48,190
>> それでは、トライは本当にで満たされ、著者は表現することを選んださ

995
00:59:48,190 --> 00:59:51,880
小さな三角形でこれらterminuses。

996
00:59:51,880 --> 00:59:56,470
本当のこれはただの事実は、この三角形はここにあることを意味し、このブール値

997
00:59:56,470 --> 00:59:59,200
あなたは木で後方に行けば、意味

998
00:59:59,200 --> 01:00:02,420
それはマクスウェルはこれであるという言葉です。

999
01:00:02,420 --> 01:00:04,870
例えばだが、単語fooは、

1000
01:00:04,870 --> 01:00:07,970
私は一番上にここにルートノードで起動した場合ので、ツリーに含まれていない

1001
01:00:07,970 --> 01:00:14,030
何fのポインタ、ノーoのポインタ、ないoのポインタがありません。 Fooはこのディクショナリの名前ではありません。

1002
01:00:14,030 --> 01:00:22,460
しかし、対照的に、チューリング、T-U-R-I-N-G。繰り返しますが、私はtまたはuまたはrまたはiまたはn gのいずれかを格納していなかった。

1003
01:00:22,460 --> 01:00:29,820
しかし、私はダウンしてここにこのノードの真の方法の値は、このデータ構造に格納した - ツリーに

1004
01:00:29,820 --> 01:00:33,030
trueにis_wordのこのブール値を設定することによって。

1005
01:00:33,030 --> 01:00:35,740
だからトライは、この非常に興味深いメタ構造の一種である

1006
01:00:35,740 --> 01:00:39,810
どこにあなたは本当に辞書のこの種の単語自体を格納していない。

1007
01:00:39,810 --> 01:00:45,100
明確にするために、あなただけのyesまたはnoを保管していません、ここで終了という言葉があります。

1008
01:00:45,100 --> 01:00:46,430
>> 今すぐ含意は何ですか？

1009
01:00:46,430 --> 01:00:51,120
あなたはメモリに保存しようとしている辞書で15万の単語を持っている場合

1010
01:00:51,120 --> 01:00:53,400
リンクリストのようなものを使用して、

1011
01:00:53,400 --> 01:00:56,870
あなたのリンクリストで15万ノードを持っているとしている。

1012
01:00:56,870 --> 01:01:00,250
アルファベット順にそれらの単語のいずれかを見つけることは、O（n）の時間がかかることがあります。

1013
01:01:00,250 --> 01:01:04,370
線形時間。しかしトライの今回のケースで、

1014
01:01:04,370 --> 01:01:09,210
単語を見つけることの実行時間は何ですか？

1015
01:01:09,210 --> 01:01:17,390
それは、ここの美しさはすでにこの辞書で149999の言葉を持っていてもということであると判明

1016
01:01:17,390 --> 01:01:20,170
このデータ構造を使用して実装として、

1017
01:01:20,170 --> 01:01:25,560
それはアリス、アリスのように、中にもう一人を見つけるか、または挿入することがどのくらいの時間がかかりますか？

1018
01:01:25,560 --> 01:01:30,640
まあ、それは末尾の文字のための唯一の5は、多分6つのステップです。

1019
01:01:30,640 --> 01:01:32,880
構造体の他の名前の存在する理由

1020
01:01:32,880 --> 01:01:35,340
アリスを挿入する方法で取得していません。

1021
01:01:35,340 --> 01:01:39,640
また、アリスを見つけ、この辞書に15万の単語があります一度

1022
01:01:39,640 --> 01:01:41,960
すべてでアリスを見つけるあなたの方法で取得していません

1023
01:01:41,960 --> 01:01:46,880
アリスがあるためです。 。 。 。 。ここで、ので、私はブール値を発見した。

1024
01:01:46,880 --> 01:01:50,920
全くブール値trueがない場合と、アリスは言葉のこのデータ構造ではありません。

1025
01:01:50,920 --> 01:01:56,220
換言すれば、この新しい物事を物事を見つけると挿入の実行時間

1026
01:01:56,220 --> 01:02:01,920
トライのデータ構造は、Oである - それは、nではありません。

1027
01:02:01,920 --> 01:02:05,730
15万人の存在する国のアリスには効果がありませんので、それは思われる。

1028
01:02:05,730 --> 01:02:11,560
だから、kは英語の単語の最大長であるk、呼び出してみましょう

1029
01:02:11,560 --> 01:02:14,050
これは、典型的には20代の文字に過ぎません。

1030
01:02:14,050 --> 01:02:17,940
だから、kは定数である。聖杯ので、我々は今、発見したように見える

1031
01:02:17,940 --> 01:02:26,000
トライのことは、挿入のため、検索のために、削除のた​​めの時定数である。

1032
01:02:26,000 --> 01:02:29,170
すでに構造のものの数があるため、

1033
01:02:29,170 --> 01:02:32,600
どちらも物理的に存在しません。繰り返しますが、彼らはちょうどオフにチェックの並べ替えています、yesまたはno、

1034
01:02:32,600 --> 01:02:35,050
今後の実行時間に影響を与えません。

1035
01:02:35,050 --> 01:02:37,940
>> しかし、漁獲量があるはずだ、そうでなければ我々は、そんなに時間を無駄にしなかっただろう

1036
01:02:37,940 --> 01:02:41,460
すべてのこれらの他のデータ構造についに驚くべき秘密の1を取得します。

1037
01:02:41,460 --> 01:02:46,410
だから我々はここでこの偉業を達成するためにどのような価格払っている？スペース。

1038
01:02:46,410 --> 01:02:49,010
このことは巨大だ。と理由その著者

1039
01:02:49,010 --> 01:02:52,400
ここにそれを提示しなかったが、気付くの配列と同じように見えるこれらの事のすべてが、

1040
01:02:52,400 --> 01:02:55,400
彼は、トライの残りの部分をツリーの残りの部分を描画しませんでした

1041
01:02:55,400 --> 01:02:58,060
彼らはただストーリーには関係ありませんだから。

1042
01:02:58,060 --> 01:03:01,870
しかし、これらのすべてのノードは、超広角であり、ツリー内のすべてのノードが占有

1043
01:03:01,870 --> 01:03:07,780
26または実際に、このケースでは、私はアポストロフィのためのスペースを含めていたため27文字かもしれません

1044
01:03:07,780 --> 01:03:09,980
私たちはapostrophized言葉を持つことができること。

1045
01:03:09,980 --> 01:03:14,450
この場合、これらは広い配列です。それらはpicuturedならないようにもかかわらず、

1046
01:03:14,450 --> 01:03:18,190
これは、RAMを大量に占有します。

1047
01:03:18,190 --> 01:03:20,670
それは、現代のハードウェアでespecilly、細かいかもしれない

1048
01:03:20,670 --> 01:03:25,650
それはトレードオフです。我々はより多くのスペースを費やすことによって少ない時間を取得します。

1049
01:03:25,650 --> 01:03:28,580
だから、これはすべてどこに行くのですか？

1050
01:03:28,580 --> 01:03:32,640
まあ、してみましょう - のがここを見てみましょう。

1051
01:03:32,640 --> 01:03:39,510
ここにこの男へのジャンプを行いましょう。

1052
01:03:39,510 --> 01:03:43,450
>> 信じられないかもしれませんが、Cはいくつかの時間が今のあったように同じくらい楽しい、

1053
01:03:43,450 --> 01:03:48,130
我々はそれがより現代的なものに移行する時が来学期にポイントに到達している。

1054
01:03:48,130 --> 01:03:50,950
より高いレベルで物事。とにもかかわらず、数週間のために

1055
01:03:50,950 --> 01:03:54,580
我々はまだポインタやメ​​モリ管理の世界に身を浸すし続けるだろう

1056
01:03:54,580 --> 01:03:57,210
我々はその後に構築するために使用できるような快適さを得るために、

1057
01:03:57,210 --> 01:04:01,270
終盤は、この言語、皮肉ではなく、最終的に導入することです。

1058
01:04:01,270 --> 01:04:03,330
我々は、HTMLの話を10分のように、過ごします。

1059
01:04:03,330 --> 01:04:05,950
すべてのHTMLマークアップ言語ですが、どのようなマークアップ言語である

1060
01:04:05,950 --> 01:04:10,220
'これは太字に'と言うオープン括弧と閉括弧のこれらのシリーズです

1061
01:04:10,220 --> 01:04:12,000
この中心を作る 'このイタリック作る'。 '

1062
01:04:12,000 --> 01:04:14,250
それはすべてその知的に面白くありませんが、それは便利なスーパーです。

1063
01:04:14,250 --> 01:04:16,650
そしてそれは確かに、これらの日遍在だ。

1064
01:04:16,650 --> 01:04:19,450
しかし、何を、HTMLの世界についての強力だし、Webプログラミング、より一般的には、

1065
01:04:19,450 --> 01:04:25,910
動的なものを構築しています。PHPやPythonやRubyやJavaやC＃のような言語でコードを書く。

1066
01:04:25,910 --> 01:04:30,360
本当に、何でも選択した言語であり、動的にHTMLを生成。

1067
01:04:30,360 --> 01:04:32,960
動的にCSSと呼ばれるものを生成します。

1068
01:04:32,960 --> 01:04:35,810
カスケーディング·スタイル·シート、美学でもあります。

1069
01:04:35,810 --> 01:04:41,360
そしてそうにもかかわらず、今日、私は、おなじみのGoogle.comのようないくつかのウェブサイトに行けば

1070
01:04:41,360 --> 01:04:46,100
と私は、多分あなたが前に行ってきた開発者は、ソースの表示を、表示するために行く

1071
01:04:46,100 --> 01:04:49,800
しかし、ソースを表示しようと、このようなものはおそらくかなり不可解に見える。

1072
01:04:49,800 --> 01:04:55,320
しかし、これはGoogle.comを実装し、基になるコードです。

1073
01:04:55,320 --> 01:04:57,940
フロントエンドで。そして、実際にこのすべてがふわふわ美学のものです。

1074
01:04:57,940 --> 01:05:01,740
これはここにCSSをアップです。私は下にスクロールしておくならば、我々はいくつかの色分けされたものを買ってあげる。

1075
01:05:01,740 --> 01:05:06,890
これはHTMLです。 Googleのコードは混乱のように見えるが、私は実際に別のウィンドウを開く場合

1076
01:05:06,890 --> 01:05:09,380
我々はこれにいくつかの構造を見ることができます。

1077
01:05:09,380 --> 01:05:12,640
私がこれを開くと、ここで気づく、それはもう少し読みやすい。

1078
01:05:12,640 --> 01:05:16,850
我々は、ずっと前にこのタグを見ていくつもりですが、[ワード]タグで、

1079
01:05:16,850 --> 01:05:23,520
HTML、頭、体、div要素、スクリプト、テキスト領域、スパン、中心は、div。

1080
01:05:23,520 --> 01:05:26,770
そして、これはまた、一見不可解に見えるの一種である

1081
01:05:26,770 --> 01:05:30,890
しかしこの混乱のすべては、特定のパターン、および再現性のパターンに従います

1082
01:05:30,890 --> 01:05:33,850
かつて我々は基本を降りるように、このようなコードを書くことができるでしょう

1083
01:05:33,850 --> 01:05:37,550
として、JavaScriptと呼ばれる別の言語を使用して、このようなコードを操作します。

1084
01:05:37,550 --> 01:05:40,440
とJavaScriptは、ブラウザの内部で実行される言語である

1085
01:05:40,440 --> 01:05:44,380
我々はGoogleマップで使用されているコースのショッピングツールでは、ハーバード大学のコースで使用することを本日

1086
01:05:44,380 --> 01:05:48,660
あなたのダイナミズムの全体の束を与えるために、Facebookは、インスタントステータスの更新を表示することができます

1087
01:05:48,660 --> 01:05:51,430
Twitterは瞬時にあなたのつぶやきを表示するためにそれを使用しています。

1088
01:05:51,430 --> 01:05:53,820
これはすべて我々は自分自身をインチ没頭し始めます

1089
01:05:53,820 --> 01:05:57,190
しかし、そこに着くために、我々はインターネットについて少し何かを理解する必要があります。

1090
01:05:57,190 --> 01:06:01,130
ここでこのクリップは長いわずか数分だけですが、今のところ、これは、実際には、あると仮定しましょう

1091
01:06:01,130 --> 01:06:08,380
どのようにインターネットが来るについてです何のためのティーザーとして働いています。私は "ネットの戦士たち"をあなたに与える

1092
01:06:08,380 --> 01:06:14,720
>> [♫スローコーラス音楽♫]

1093
01:06:14,720 --> 01:06:20,450
【男性ナレーター]彼はメッセージが付属しています。

1094
01:06:20,450 --> 01:06:23,770
プロトコルはすべて彼自身である。

1095
01:06:23,770 --> 01:06:37,270
[♫速い電子音楽♫]

1096
01:06:37,270 --> 01:06:41,330
彼は、ルータを思いやり、クールファイアウォールの世界に来た

1097
01:06:41,330 --> 01:06:45,690
死よりもはるかに悪いと危険。

1098
01:06:45,690 --> 01:06:55,400
彼は高速です。彼は強いです。彼は、TCP / IPのだ、と彼はあなたの住所を持っている。

1099
01:06:55,400 --> 01:06:59,250
ネットの戦士たち。

1100
01:06:59,250 --> 01:07:05,290
[マラン]来週、その後。インターネット。 Webプログラミング。これはCS50です。

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]