1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [セクション6：あまり快適]

2
00:00:02,730 --> 00:00:05,040
[ネイトHardison] [ハーバード大学]

3
00:00:05,040 --> 00:00:07,320
[これはCS50です。] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
かしこまりました。第6節へようこそ。

5
00:00:11,840 --> 00:00:14,690
今週、私たちは、セクション内のデータ構造の話をすることになるだろう

6
00:00:14,690 --> 00:00:19,780
今週の問題はspellrで設定主な理由

7
00:00:19,780 --> 00:00:24,410
異なるデータ構造の調査の全体の束がありません。

8
00:00:24,410 --> 00:00:26,520
あなたは問題セットで行くことができるさまざまな方法の束がありますが、

9
00:00:26,520 --> 00:00:31,570
あなたが知っているとより多くのデータ構造は、次の操作を行うことができ、よりクールなもの。

10
00:00:31,570 --> 00:00:34,990
>> それでは始めましょう。まず、スタックの話をするつもりだ

11
00:00:34,990 --> 00:00:37,530
我々が話をしようとしているスタックとキューのデータ構造。

12
00:00:37,530 --> 00:00:40,560
我々はグラフについて話し始めるときに、スタックやキューは、本当に便利だ

13
00:00:40,560 --> 00:00:44,390
その我々が今のように多くのことをするつもりはない。

14
00:00:44,390 --> 00:00:52,820
しかし、彼らは本当にCSの大きな根本的なデータ構造の一つを理解してもいいです。

15
00:00:52,820 --> 00:00:54,880
問題セットの明細書の記載、

16
00:00:54,880 --> 00:00:59,260
と同類のようにスタックに関する、あなたがそれを引っ張り上げて、協議

17
00:00:59,260 --> 00:01:05,239
あなたは食堂で食堂に持っているダイニングトレーの山

18
00:01:05,239 --> 00:01:09,680
ダイニングのスタッフが来て、彼らがそれらを掃除した後、食事のトレイを出したときにどこに

19
00:01:09,680 --> 00:01:12,000
彼らは彼らに他の上に1を積み重ねる。

20
00:01:12,000 --> 00:01:15,050
そして、子供たちは食べ物を得るために来たときに、

21
00:01:15,050 --> 00:01:19,490
彼らはその後、最初のトップ1、その下1、その下1、トレイをやってのける。

22
00:01:19,490 --> 00:01:25,190
だから、実質的には、ダイニングのスタッフは下に置くことを第一トレイが取り出される最後のものである。

23
00:01:25,190 --> 00:01:32,330
ダイニングスタッフが保留にした最後のものが夕食のために離陸される最初のものです。

24
00:01:32,330 --> 00:01:38,100
あなたがすでに持っていない場合は、ダウンロードすることができ、問題のセットの仕様では、

25
00:01:38,100 --> 00:01:46,730
我々は、この種の構造体を使用してスタックデータstuctureのモデリングの話。

26
00:01:46,730 --> 00:01:51,070
>> だから我々はここに持っているもの、これは、講演で発表されたものと似ています

27
00:01:51,070 --> 00:01:58,120
講義を除いて、我々は、char * sのとは対照的に、int型がこれを発表した。

28
00:01:58,120 --> 00:02:06,250
これは、その店に何をスタックになるだろうか？

29
00:02:06,250 --> 00:02:09,009
ダニエル？我々は、このスタックに何を保存している？

30
00:02:09,009 --> 00:02:15,260
[ダニエル]文字列？ >>我々はまさに、このスタック内の文字列を格納している。

31
00:02:15,260 --> 00:02:20,950
スタックを作成するために持っている必要があるすべての配列です

32
00:02:20,950 --> 00:02:23,920
特定の容量の、この場合であって、

33
00:02:23,920 --> 00:02:28,020
容量は、それが一定だからすべて大文字であることを行っている。

34
00:02:28,020 --> 00:02:36,340
そして、配列に加えて、我々は追跡する必要があるすべては、配列の現在のサイズです。

35
00:02:36,340 --> 00:02:38,980
それはクールなものだここで注意すべきことの一つ

36
00:02:38,980 --> 00:02:47,060
我々は、別のデータ構造、配列の上に積み重ねられたデータ構造を作成しているということです。

37
00:02:47,060 --> 00:02:50,110
スタックを実装するさまざまな方法があります。

38
00:02:50,110 --> 00:02:54,250
我々は、うまくいけば、リンクリストの問題をやった後、非常にまだそれを行うことはありません

39
00:02:54,250 --> 00:03:00,520
あなたは簡単にだけでなく、リンクされたリストの上にスタックを実装することができる方法を見ていきます。

40
00:03:00,520 --> 00:03:02,640
しかし、今の私たちは、配列で我慢しましょう​​。

41
00:03:02,640 --> 00:03:06,350
だからもう一度、私たちが必要とするすべては配列であり、我々は単に配列のサイズを追跡する必要があります。

42
00:03:06,350 --> 00:03:09,850
[サム]申し訳ありませんが、なぜそれが、スタックは、文字列の上だと述べているということです？

43
00:03:09,850 --> 00:03:13,440
文字列がスタック内にあるように僕には思える。

44
00:03:13,440 --> 00:03:16,790
[Hardison]うん。我々は我々の配列データ構造を取っている、作成している - 

45
00:03:16,790 --> 00:03:22,130
それは素晴らしい質問ですね。そこで質問は、このオンラインを見ている人々のために、なぜ

46
00:03:22,130 --> 00:03:24,140
なぜ我々は、スタックは、文字列の上にあると言っている

47
00:03:24,140 --> 00:03:27,990
ここでは、文字列がスタック内にあるように見えますか？ので

48
00:03:27,990 --> 00:03:31,050
これは完全にケースです。

49
00:03:31,050 --> 00:03:34,660
私が言及していた、我々は、配列のデータ構造を持っているということでした。

50
00:03:34,660 --> 00:03:39,290
我々は、char *の配列、文字列のこの配列を、持っている

51
00:03:39,290 --> 00:03:45,300
そして我々は積み重ねられたデータ構造を作成するためにそれに追加しようとしている。

52
00:03:45,300 --> 00:03:48,620
>> だからスタックは配列よりも若干複雑です。

53
00:03:48,620 --> 00:03:51,890
我々は、スタックを構築するために配列を使用することができます。

54
00:03:51,890 --> 00:03:55,810
我々はスタックは配列の上に構築されていると言うところだからです。

55
00:03:55,810 --> 00:04:02,510
同様に、私が以前言ったように、我々はリンクリストの一番上にスタックを構築することができます。

56
00:04:02,510 --> 00:04:04,960
代わりに我々の要素を保持する配列を使用しての、

57
00:04:04,960 --> 00:04:10,070
私達は私達の要素を保持し、その周りにスタックを構築するためにリンクされたリストを使用することができます。

58
00:04:10,070 --> 00:04:12,420
、いくつかのコードを見て、いくつかの例を歩くましょう

59
00:04:12,420 --> 00:04:14,960
ここで実際に何が起こっているかを確認します。

60
00:04:14,960 --> 00:04:23,400
左側には、私はそのスタック構造体がメモリにどのように見えるか下に投げてきた

61
00:04:23,400 --> 00:04:28,330
容量は＃4になるように定義された場合。

62
00:04:28,330 --> 00:04:33,490
我々は4つの要素char *配列を持っている。

63
00:04:33,490 --> 00:04:38,110
私たちは、文字列[0]は、文字列[1]は、文字列[2]文字列[3]を持っている

64
00:04:38,110 --> 00:04:43,800
私達のサイズの整数の後、その最後のスペース。

65
00:04:43,800 --> 00:04:46,270
これは理にかなっていますか？オーケー。

66
00:04:46,270 --> 00:04:48,790
これは、私が右に何をすべきかとどうなるかです

67
00:04:48,790 --> 00:04:55,790
私のコードになるでしょう、これだけのstr​​uct、sと呼ばれる積み重ねられた構造体を宣言することです。

68
00:04:55,790 --> 00:05:01,270
これは、我々が得るものです。これは、メモリ内のこのフットプリントを定めています。

69
00:05:01,270 --> 00:05:05,590
ここで最初の質問は、このスタック構造体の内容は何ですか？

70
00:05:05,590 --> 00:05:09,250
今の彼らは何もしているが、彼らは全く何もわからないん。

71
00:05:09,250 --> 00:05:13,300
彼らはゴミのこの種だ。我々は考え、その中に何もありません。

72
00:05:13,300 --> 00:05:17,000
我々はスタックsを宣言するとき、我々は単にメモリの上にそれをダウンして投げている。

73
00:05:17,000 --> 00:05:19,840
これは、int iを宣言して初期化しないような種類のものだ。

74
00:05:19,840 --> 00:05:21,730
あなたはそこに何があるかわからない。あなたは、そこに何があるかを読み取ることができます

75
00:05:21,730 --> 00:05:27,690
しかしそれは超便利ではないかもしれません。

76
00:05:27,690 --> 00:05:32,680
あなたが常にそうする覚えておきたいことの一つは、初期化する必要がありますどのような初期化です。

77
00:05:32,680 --> 00:05:35,820
この場合において、我々は、ゼロになるようにサイズを初期化しようとしている

78
00:05:35,820 --> 00:05:39,960
それは私達のために非常に重要であることが判明するために起こっているからです。

79
00:05:39,960 --> 00:05:43,450
我々は、すべてのchar * sは、先に行くとポインタのすべてを初期化することができ

80
00:05:43,450 --> 00:05:49,670
おそらく、いくつかのヌル値になるように理解できる。

81
00:05:49,670 --> 00:05:58,270
しかし、それは我々がそれを行うことが全く必要ありません。

82
00:05:58,270 --> 00:06:04,200
>> さて、スタック上の2つの主な操作はありますか？

83
00:06:04,200 --> 00:06:07,610
誰もがあなたがスタックで何をすべきか講義から覚えていますか？はい？

84
00:06:07,610 --> 00:06:09,700
[ステラ]を押すと飛び出る？まさに>>。

85
00:06:09,700 --> 00:06:13,810
プッシュとポップすると、スタック上の2つの主な操作です。

86
00:06:13,810 --> 00:06:17,060
とプッシュが何をするのでしょうか？ >>それは上に何かを置く

87
00:06:17,060 --> 00:06:19,300
スタックの、その後飛び出るそれを脱ぐ。

88
00:06:19,300 --> 00:06:23,150
[Hardison]その通りです。だからプッシュは、スタックの一番上に何かをプッシュします。

89
00:06:23,150 --> 00:06:27,700
それは、ダイニングスタッフがカウンターの上にダイニングトレイを下に置くようなものだ。

90
00:06:27,700 --> 00:06:33,630
と飛び出るは、スタックのダイニング·トレイの電源を取っている。

91
00:06:33,630 --> 00:06:36,460
Let 'sは、何が起こるかの例をいくつか通って歩く

92
00:06:36,460 --> 00:06:39,720
我々は、スタックに何かを押したとき。

93
00:06:39,720 --> 00:06:45,110
私達は私達のスタックに文字列 'Hello'をプッシュした場合、

94
00:06:45,110 --> 00:06:49,760
これは私たちの図が今どのように見えるかです。

95
00:06:49,760 --> 00:06:53,410
何が起こるかを参照してください？

96
00:06:53,410 --> 00:06:56,530
私たちは、文字列配列の最初の要素に押し込ま

97
00:06:56,530 --> 00:07:01,420
そして私達は私達のサイズは1にカウント引き上げた。

98
00:07:01,420 --> 00:07:05,340
我々は2つ​​のスライド間の違いを見ればそう、ここ、ここ、プッシュ前に0だた。

99
00:07:05,340 --> 00:07:08,690
ここでプッシュした後です。

100
00:07:08,690 --> 00:07:13,460
プッシュ前に、プッシュした後。

101
00:07:13,460 --> 00:07:16,860
そして今、我々は我々のスタック内で1つの要素を持っています。

102
00:07:16,860 --> 00:07:20,970
これは、文字列 "hello"のだし、それはそれだ。

103
00:07:20,970 --> 00:07:24,440
アレイ内の他のすべては、私たちの文字列配列に、まだゴミです。

104
00:07:24,440 --> 00:07:27,070
我々は、それを初期化していない。

105
00:07:27,070 --> 00:07:29,410
Let 'sは、私たちがスタック上に別の文字列をプッシュすると言う。

106
00:07:29,410 --> 00:07:32,210
我々は、この時間に "世界"をプッシュするつもりだ。

107
00:07:32,210 --> 00:07:35,160
それで、あなたは、 "世界は"ここでは "hello"の上に行くことができます参照してください。

108
00:07:35,160 --> 00:07:40,040
とサイズのカウントが2に上がります。

109
00:07:40,040 --> 00:07:44,520
今、私たちは、 "CS50"をプッシュすることができ、それが再びトップに行くよ。

110
00:07:44,520 --> 00:07:51,110
我々は戻ってしまったら、あなたは私たちがスタックの一番上に物事を推進しているかを見ることができます。

111
00:07:51,110 --> 00:07:53,320
そして今、我々はポップに取得します。

112
00:07:53,320 --> 00:07:58,910
我々は、スタックの何かオフを取り出したときに、何が起こったのか？

113
00:07:58,910 --> 00:08:01,540
誰もが違いを参照してください？それはかなり微妙です。

114
00:08:01,540 --> 00:08:05,810
[学生]サイズ。 >>うん、サイズが変更されました。

115
00:08:05,810 --> 00:08:09,040
>> あなたは他の何に変更すると予想しているだろうか？

116
00:08:09,040 --> 00:08:14,280
あまりに[学生]文字列。 >>は右。あまりにも文字列。

117
00:08:14,280 --> 00:08:17,110
それは、あなたがこの方法でそれをやっているときが判明

118
00:08:17,110 --> 00:08:21,960
私達は私達のスタックに要素をコピーしていないので、

119
00:08:21,960 --> 00:08:24,670
私たちは実際に何もする必要はありません、我々はちょうどサイズを使用することができます

120
00:08:24,670 --> 00:08:28,630
私たちの配列で物事の数を追跡する

121
00:08:28,630 --> 00:08:33,780
ように、我々は再びポップするとき、再び我々はちょうど1に私たちのサイズをダウンして増減します。

122
00:08:33,780 --> 00:08:39,440
実際に行くと何かを上書きする必要はありません。

123
00:08:39,440 --> 00:08:41,710
ファンキーの一種。

124
00:08:41,710 --> 00:08:46,520
それは私たちが行うためには、それが少ない仕事だから、我々は一般的に言葉だけで物事を残すことが判明した。

125
00:08:46,520 --> 00:08:50,060
我々は戻って、何かを上書きする必要がないならば、なぜそれを行う？

126
00:08:50,060 --> 00:08:54,150
だから我々はスタックからポップしたときに二回、ないことをすべてのサイズが数回デクリメントされています。

127
00:08:54,150 --> 00:08:59,120
そして再び、これは我々が我々のスタックに物事をコピーしていないという理由だけです。

128
00:08:59,120 --> 00:09:01,320
はい？どうぞ召しあがれ。

129
00:09:01,320 --> 00:09:04,460
[学生、不明朗] >>そして、あなたは再び何かを押したときに何が起こるか？

130
00:09:04,460 --> 00:09:08,570
あなたは再び何かを押すと、それはどこに行くのですか？

131
00:09:08,570 --> 00:09:12,390
それはどこに、バジルへ行くのでしょうか？文字列へ>> [1]？ >>は右。

132
00:09:12,390 --> 00:09:14,530
なぜそれが文字列[3]に入らない？

133
00:09:14,530 --> 00:09:19,410
[バジル]それは何かが文字列であったことを忘れていたため[1]と[2]？

134
00:09:19,410 --> 00:09:24,040
[Hardison]その通りです。私たちのスタックは、本質的に、それが何かにつかまっていたことを "忘れて"

135
00:09:24,040 --> 00:09:29,480
文字列内の[1]または文字列[2]ので、ときに我々は "やった"を押して、

136
00:09:29,480 --> 00:09:36,670
それは単なる文字列で、その要素に[1]を入れます。

137
00:09:36,670 --> 00:09:41,590
基本的なレベルで、どのようにこの作品に何か質問はありますか？

138
00:09:41,590 --> 00:09:45,160
[SAM]だから、これは量の面で、どのような方法で動的ではありません

139
00:09:45,160 --> 00:09:47,620
またはスタックのサイズの点で？

140
00:09:47,620 --> 00:09:56,750
[Hardison]その通りです。これは、 - ポイントは、これが動的にgrowningスタックではないということだった。

141
00:09:56,750 --> 00:10:02,850
これは、ほとんどの四つで、最も、4のchar * sで、保持できるスタックです。

142
00:10:02,850 --> 00:10:07,580
我々は第五の事をしようとプッシュしていた場合は、どうすべきかと思いますか？

143
00:10:07,580 --> 00:10:11,870
[学生、不明朗]

144
00:10:11,870 --> 00:10:14,600
[Hardison]その通りです。起こりうる事柄がいくつかあります。

145
00:10:14,600 --> 00:10:19,330
それはおそらく我々が何であったかに応じて、seg faultを可能性 - 

146
00:10:19,330 --> 00:10:22,530
正確にどのように我々は、バックエンドを実装しました。

147
00:10:22,530 --> 00:10:31,740
それは上書きする可能性があります。それは我々はクラスで話をそのバッファオーバーフローを及ぼす可能性があります。

148
00:10:31,740 --> 00:10:35,240
何が上書きされる可能性が最も明白なものになるだろう

149
00:10:35,240 --> 00:10:42,370
我々は、スタック上の余分なものを押し付けようとした場合はどうなりますか？

150
00:10:42,370 --> 00:10:44,550
だからあなたは、バッファオーバーフローを述べた。

151
00:10:44,550 --> 00:10:47,870
何が上書きまたは踏みにじられるであろうことかもしれない

152
00:10:47,870 --> 00:10:52,320
私たちは余分なものをプッシュしようとすることで誤ってオーバーフローした場合はどうなりますか？

153
00:10:52,320 --> 00:10:54,730
[ダニエル、不明朗] >>考えられる。

154
00:10:54,730 --> 00:10:58,440
しかし、当初は、何が起こるのでしょうか？我々は第四の事をプッシュしようとしたら？

155
00:10:58,440 --> 00:11:06,220
それは、少なくとも我々が持っているこのメモリ·ダイアグラムで、サイズを上書きすることがあります。

156
00:11:06,220 --> 00:11:10,880
>> 今日我々が実装されようとしているものであるという問題点セット仕様においては、

157
00:11:10,880 --> 00:11:16,030
私たちが何をしたいかは、単にfalseを返しています。

158
00:11:16,030 --> 00:11:20,030
私たちのpushメソッドはブール値を返すために起こっている、

159
00:11:20,030 --> 00:11:22,920
プッシュが成功した場合、そのブール値はtrueになります

160
00:11:22,920 --> 00:11:29,730
とスタックがいっぱいになったため、我々はより多くの何かをプッシュすることはできません場合にはfalseを返します。

161
00:11:29,730 --> 00:11:33,620
今は、そのコードを少しいきましょう。

162
00:11:33,620 --> 00:11:36,400
ここに私たちのプッシュ機能です。

163
00:11:36,400 --> 00:11:40,380
スタックのための私達のプッシュ機能は、スタック上に置くために文字列にかかるとしている。

164
00:11:40,380 --> 00:11:45,820
それは、文字列が正常にプッシュされた場合はtrueを返すようになるだろう

165
00:11:45,820 --> 00:11:51,820
スタック上で、それ以外の場合はfalse。

166
00:11:51,820 --> 00:11:59,740
ここで行うには良い最初のものになるかもしれないもの上の任意の提案ですか？

167
00:11:59,740 --> 00:12:20,630
サイズは容量に等しい場合に[サム]がfalseを返す？

168
00:12:20,630 --> 00:12:23,320
[Hardison]ビンゴ。いい仕事。

169
00:12:23,320 --> 00:12:26,310
サイズは容量であれば、我々は、falseを返すつもりだ。

170
00:12:26,310 --> 00:12:29,270
私たちは、スタック内のより多くの何かを置くことはできません。

171
00:12:29,270 --> 00:12:36,900
そうでなければ、我々はスタックの一番上に何かを載せていきたいと思います。

172
00:12:36,900 --> 00:12:41,670
最初は、 "スタックの先頭"とは何ですか？

173
00:12:41,670 --> 00:12:43,650
[ダニエル]サイズ0？ >>サイズ0。

174
00:12:43,650 --> 00:12:49,990
スタック内の1つの事がある後のスタックのトップは何ですか？ミッシー、あなたは知っていますか？

175
00:12:49,990 --> 00:12:52,720
[ミッシー]ワン。 >>サイズは、厳密に1つ、である。あなたは、サイズに追加し続ける

176
00:12:52,720 --> 00:13:01,690
あなたは配列内のインデックスのサイズで新しい要素を入れていると毎回。

177
00:13:01,690 --> 00:13:05,470
それが理にかなっている場合我々は、ワンライナーのようなものでそれを行うことができます。

178
00:13:05,470 --> 00:13:11,910
我々は文字列の配列を持っているので、我々は、サイズインデックスでアクセスするつもりだ

179
00:13:11,910 --> 00:13:14,780
そして我々はそこに私たちのchar *を保存するつもりです。

180
00:13:14,780 --> 00:13:19,340
ここで起こってない文字列のコピーがない方法に注目して、

181
00:13:19,340 --> 00:13:29,680
メモリーの動的割り当て？

182
00:13:29,680 --> 00:13:34,440
そして、ミッシーは、私たちが今何をして育て

183
00:13:34,440 --> 00:13:40,570
我々は、配列内の適切な場所に文字列が保存されているので、

184
00:13:40,570 --> 00:13:49,230
そして彼女は、我々は次のプッシュのための準備が整いましたように、いずれかのサイズを増加しなければならなかったことを言った。

185
00:13:49,230 --> 00:13:53,950
だから我々はs.size使用して行うことができます+ +。

186
00:13:53,950 --> 00:13:59,330
この時点で、我々は我々の配列にプッシュした。私たちがしなければならない最後のことは何ですか？

187
00:13:59,330 --> 00:14:10,110
[学生]は、trueを返します。 >>は、trueを返します。

188
00:14:10,110 --> 00:14:14,690
だから、かなり単純なコードは非常に簡単です。あまりない。

189
00:14:14,690 --> 00:14:17,070
それがわかれば、スタックがどのように動作するかの周りにあなたの頭をラップして

190
00:14:17,070 --> 00:14:21,910
これを実装するのは非常に単純です。

191
00:14:21,910 --> 00:14:26,390
>> さて、これの次の部分では、スタックから文字列を飛び出しています。

192
00:14:26,390 --> 00:14:29,410
私はあなたたちにこの少し上で動作するようにいくつかの時間を与えるつもりだ。

193
00:14:29,410 --> 00:14:34,320
それはほとんど本質的に我々がここでプッシュでやったことの逆です。

194
00:14:34,320 --> 00:14:38,510
私がやったことは、実際には - おっと。

195
00:14:38,510 --> 00:14:48,160
私は、こっちに、アプライアンスにアプライアンスをブートすれ

196
00:14:48,160 --> 00:14:53,600
私はこの問題は、5の仕様を設定してプルアップされてきました。

197
00:14:53,600 --> 00:15:02,560
我々がここでズームインした場合、我々は、私はcdn.cs50.net/2012/fall/psets/pset5.pdfにいる見ることができます。

198
00:15:02,560 --> 00:15:08,590
君たちは、ここsection6.zipに位置しているこのコードをダウンロードしたことがありますか？

199
00:15:08,590 --> 00:15:15,030
かしこまりました。あなたがそれを行っていない場合は、本当にすぐに、すぐにその権利を行う。

200
00:15:15,030 --> 00:15:22,130
私は、ターミナルウィンドウでそれをやる。

201
00:15:22,130 --> 00:15:25,090
私は実際にそれをここにUPしました。うん。

202
00:15:25,090 --> 00:15:34,730
はい、サム？ >>私はあなたのサイズ= strのs.stringのブラケットを言っていた理由について質問がありますか？

203
00:15:34,730 --> 00:15:42,910
strは何ですか？その前にどこかで定義された、またはされている - ああ、char *文字列str内の？

204
00:15:42,910 --> 00:15:47,160
[Hardison]はい、その通りです。それが根拠となった。 >>ああ、大丈夫。申し訳ありません。

205
00:15:47,160 --> 00:15:49,470
[Hardison]我々はインチプッシュする文字列を指定している

206
00:15:49,470 --> 00:15:55,220
私たちは本当にここの話をしなかったことを思いつくかもしれない他の質問があった

207
00:15:55,220 --> 00:15:58,810
我々はsと呼ばれるこの変数を持っていたことを当然のことと取った

208
00:15:58,810 --> 00:16:02,710
その範囲と私たちにアクセス可能であった。

209
00:16:02,710 --> 00:16:06,960
我々は、sはこのスタック構造であったことを当然の取った。

210
00:16:06,960 --> 00:16:08,930
だから、このプッシュコードを振り返る

211
00:16:08,930 --> 00:16:13,450
あなたは私たちが渡してしまった、この文字列でものをやっていることがわかります

212
00:16:13,450 --> 00:16:19,210
突然のすべてが、その後、私たちはs.size、好きだから来たのにアクセスしている？

213
00:16:19,210 --> 00:16:23,020
私たちはセクションアーカイブに見しようとしているコードで

214
00:16:23,020 --> 00:16:27,100
あなたの問題のセットでやっているだろうことが、その後のもの、

215
00:16:27,100 --> 00:16:32,440
私達は私達のスタックがグローバル変数を構造体作った

216
00:16:32,440 --> 00:16:36,380
我々はすべて私たちのさまざまな機能でそれへのアクセスを持つことができるように

217
00:16:36,380 --> 00:16:40,630
手動で参照することによって、それを周りに渡すと、それを渡すことなく、

218
00:16:40,630 --> 00:16:44,870
それにもののすべてのようなものをやる。

219
00:16:44,870 --> 00:16:52,280
私達はちょうどよりよいものを作るために、可能ならば、少し浮気している。

220
00:16:52,280 --> 00:16:57,430
そして、それはそれは楽しみのためですので、私たちがここでやっているものだ、それは簡単です。

221
00:16:57,430 --> 00:17:02,800
彼らは一つの大きなデータ構造を持っている場合、多くの場合、あなたは人々がこれを行うに表示されます

222
00:17:02,800 --> 00:17:07,750
それは、そのプログラム内で運用されている。

223
00:17:07,750 --> 00:17:09,560
>> のは、アプライアンスにフェールオーバ戻りましょう。

224
00:17:09,560 --> 00:17:15,240
皆は正常section6.zipを得たのですか？

225
00:17:15,240 --> 00:17:20,440
みんな解凍section6.zipを使用してそれを解凍？

226
00:17:20,440 --> 00:17:27,200
あなたは、セクション6のディレクトリに行く場合 - 

227
00:17:27,200 --> 00:17:29,220
アーッ、あらゆる場所に - 

228
00:17:29,220 --> 00:17:32,840
と、ここに何があるかをリストし、あなたが3異なる。cファイルを持っていることがわかります。

229
00:17:32,840 --> 00:17:38,350
あなたは、片方向リンクリストであるキュー、SLL、およびスタックを持っている。

230
00:17:38,350 --> 00:17:44,600
あなたはstack.cを開くと、

231
00:17:44,600 --> 00:17:47,330
あなたは、私たちが私たちのために定義されているこの構造を持っていることがわかります

232
00:17:47,330 --> 00:17:51,330
先ほどスライドで話している正確な構造体。

233
00:17:51,330 --> 00:17:56,340
我々は、スタックのための私達のグローバル変数を持っている

234
00:17:56,340 --> 00:18:00,110
私達は私達のプッシュ機能を持っている、

235
00:18:00,110 --> 00:18:04,230
それから私達は私達のポップアップ機能を持っている。

236
00:18:04,230 --> 00:18:08,320
私は、ここでスライド上に戻って押し上げるためのコードを置くことにしましょう

237
00:18:08,320 --> 00:18:10,660
しかし、私があなたたちがやりたいことは、あなたの実力を最大限に発揮し、ある

238
00:18:10,660 --> 00:18:13,790
行くとpop関数を実装します。

239
00:18:13,790 --> 00:18:18,480
一度あなたがそれを実装しました、あなたは、スタックを作ると、これをコンパイルすることができます

240
00:18:18,480 --> 00:18:22,540
その後、得られたスタックの実行可能ファイルを実行し、

241
00:18:22,540 --> 00:18:28,390
それがダウンしてここにメインでだとこのテストのすべてのコードを実行されます。

242
00:18:28,390 --> 00:18:31,060
そしてメインは、実際にpushとpopの呼び出しを行うの面倒を見る

243
00:18:31,060 --> 00:18:33,220
そして万事通過することを確認すること。

244
00:18:33,220 --> 00:18:36,820
また、右ここでスタックサイズを初期化する

245
00:18:36,820 --> 00:18:39,780
ので、あなたはそれを初期化することを心配する必要はありません。

246
00:18:39,780 --> 00:18:42,310
あなたはそれが適切に初期化されていると仮定することができます

247
00:18:42,310 --> 00:18:48,000
あなたはポップアップ機能でアクセスしている時間によって。

248
00:18:48,000 --> 00:18:53,530
お分かりでしょうか？

249
00:18:53,530 --> 00:19:00,100
だからここに私達は行く。プッシュコードがあります。

250
00:19:00,100 --> 00:19:13,210
私は君たち5分または10分を与えるでしょう。

251
00:19:13,210 --> 00:19:15,690
そして、あなたがコーディングしているときに、暫定的に質問があれば、

252
00:19:15,690 --> 00:19:17,710
それらを大声で尋ねてください。

253
00:19:17,710 --> 00:19:23,080
あなたはスティッキングポイントに着くそうならば、単に尋ねる。

254
00:19:23,080 --> 00:19:26,030
他のみんなに知らせて、私を知ってみましょう。

255
00:19:26,030 --> 00:19:28,160
あまりにもあなたの隣人と協力してください。

256
00:19:28,160 --> 00:19:30,360
[ダニエル]我々は、ちょうど今ポップアップ実装しようとしている？ただ>>ポップ。

257
00:19:30,360 --> 00:19:34,200
もしそうしたければ、プッシュの実装をコピーすることができますが

258
00:19:34,200 --> 00:19:37,780
テストでは、動作するように。

259
00:19:37,780 --> 00:19:41,940
それが入るものをテストするのは難しいので - 

260
00:19:41,940 --> 00:19:49,030
で始まるに、スタック内の何かが存在しない場合、または、それがスタックからポップなものを試すのは難しい。

261
00:19:49,030 --> 00:19:55,250
>> 返すことになってポップとは何ですか？スタックの先頭から要素。

262
00:19:55,250 --> 00:20:01,260
それはスタックの先頭の要素を降りることになっている

263
00:20:01,260 --> 00:20:05,780
その後、スタックのサイズを減少させる

264
00:20:05,780 --> 00:20:07,810
そして今あなたは上の要素を失ってしまった。

265
00:20:07,810 --> 00:20:11,420
そして、あなたは一番上の要素を返す。

266
00:20:11,420 --> 00:20:20,080
[学生、不明朗]

267
00:20:20,080 --> 00:20:28,810
[Hardison]だからあなたがそれを行うとどうなりますか？ [学生、不明朗]

268
00:20:28,810 --> 00:20:34,000
どうした何が起こって終了すると、おそらくどちらかにアクセスしているです

269
00:20:34,000 --> 00:20:37,350
まだ初期化されていない要素なので、あなたの計算

270
00:20:37,350 --> 00:20:39,990
最後の要素がどこにあるのはオフになっています。

271
00:20:39,990 --> 00:20:46,260
あなたが気づけばだからここで、プッシュでは、我々はs.size要素に文字列にアクセスしている

272
00:20:46,260 --> 00:20:48,560
それは、新しいインデックスだから。

273
00:20:48,560 --> 00:20:51,460
これは、スタックの新しいトップだ。

274
00:20:51,460 --> 00:21:01,100
ポップで、s.sizeは次のスペースであることを行っているのに対し、

275
00:21:01,100 --> 00:21:05,210
あなたのスタック内のすべての要素の上のスペース。

276
00:21:05,210 --> 00:21:10,050
最上位の要素がs.sizeではないので、

277
00:21:10,050 --> 00:21:14,930
むしろ、それはその下だ。

278
00:21:14,930 --> 00:21:19,640
>> もし他に行うべき事 - ポップで、

279
00:21:19,640 --> 00:21:22,030
あなたのサイズを減少させなければならないのさ。

280
00:21:22,030 --> 00:21:28,750
あなたは右ここに私たちの小さなダイアグラムに戻り覚えていれば、

281
00:21:28,750 --> 00:21:30,980
私たちはPOPと呼ばれるときには本当に、我々が見た唯一のことは起こって

282
00:21:30,980 --> 00:21:36,150
このサイズは、1に、最初の2つに、ドロップされたということでした。

283
00:21:36,150 --> 00:21:42,620
その後、我々は上に新しい要素を押したときに、それは適切な場所で上に行くだろう。

284
00:21:42,620 --> 00:21:49,610
[バジル] s.sizeが2であれば、それは、要素2へ行こうとしなかった

285
00:21:49,610 --> 00:21:54,400
次にその要素をポップにしたいと思うだろう？

286
00:21:54,400 --> 00:21:59,510
我々はに行ってきましたので、もし -  >>だから、もう一度これを見てみましょう。

287
00:21:59,510 --> 00:22:07,730
これは、この時点で我々のスタックである場合

288
00:22:07,730 --> 00:22:12,130
そして我々は、ポップアップを呼び出す

289
00:22:12,130 --> 00:22:16,150
位置のインデックスは、最上位の要素ですか？

290
00:22:16,150 --> 00:22:19,300
[バジル] 2で、それは3をポップになるだろう。 >>は右。

291
00:22:19,300 --> 00:22:24,220
それで、我々の大きさが3のところですが、我々はインデックス2にある要素をポップしたいと思います。

292
00:22:24,220 --> 00:22:29,900
それはあなたが配列のゼロインデキシングで持っている1つずれのその典型的なものだ。

293
00:22:29,900 --> 00:22:36,430
だから、第三の要素をポップしたくないが、第三の要素のインデックスは3ではありません。

294
00:22:36,430 --> 00:22:39,430
私たちが推進している我々はそのマイナス1を行う必要はありませんし、理由

295
00:22:39,430 --> 00:22:44,120
今ので、あなたは気付くされている最上位の要素、

296
00:22:44,120 --> 00:22:47,600
我々はこの時点でスタックに何か他のものをプッシュした場合、

297
00:22:47,600 --> 00:22:50,360
私たちは、インデックス3でそれをプッシュしたいと思います。

298
00:22:50,360 --> 00:23:03,550
そして、それはちょうどあなたが推進している時にサイズとインデックスが並ぶように起こります。

299
00:23:03,550 --> 00:23:06,960
>> 稼働中のスタックの実装を持っている誰か？

300
00:23:06,960 --> 00:23:09,690
あなたは、稼働中のスタック1を持っている。あなたはまだ働いてポップを持っていますか？

301
00:23:09,690 --> 00:23:11,890
[ダニエル]はい。そう思います。

302
00:23:11,890 --> 00:23:14,610
>>プログラムが実行されていて、断層ワンセグではない、それはプリントアウトしている？

303
00:23:14,610 --> 00:23:17,520
あなたがそれを実行したとき、それは "成功"をプリントアウトしていますか？

304
00:23:17,520 --> 00:23:22,630
うん。それは "成功"を出力し、ブームを行っていない場合、スタックを確認し、それを実行し、

305
00:23:22,630 --> 00:23:26,000
その後、すべての良いことだ。

306
00:23:26,000 --> 00:23:34,070
かしこまりました。 、のは本当にすぐにアプライアンスに渡ろう

307
00:23:34,070 --> 00:23:46,100
そして、私たちはこの見ていきます。

308
00:23:46,100 --> 00:23:51,110
我々は、ポップと一緒にここで何が起こっているのかを見れば、

309
00:23:51,110 --> 00:23:55,220
ダニエルは、あなたがしたことはまず何でしたか？

310
00:23:55,220 --> 00:23:58,850
[ダニエル] s.sizeが0より大きい場合。

311
00:23:58,850 --> 00:24:03,120
[Hardison]オーケー。そして、あなたはなぜそんなことしたの？

312
00:24:03,120 --> 00:24:05,610
[ダニエル]スタック内部の何かがあったことを確認します。

313
00:24:05,610 --> 00:24:10,950
[Hardison]右。あなたはs.sizeが0より大きいことを確認するためにテストしたい;

314
00:24:10,950 --> 00:24:13,280
そうでなければ、何が起こるしたと何をしたいですか？

315
00:24:13,280 --> 00:24:16,630
[ダニエル]戻りヌル？ >>リターンヌル、正確に。

316
00:24:16,630 --> 00:24:20,740
だからs.sizeが0より大きい場合。その後、我々は何をするつもりですか？

317
00:24:20,740 --> 00:24:25,890
スタックが空でない場合、我々は何をしますか？

318
00:24:25,890 --> 00:24:31,210
[ステラ]あなたはサイズを減少させる？あなたは大丈夫、サイズをデクリメント。>>

319
00:24:31,210 --> 00:24:34,440
ですから、どのようにそれをやったの？ >> s.size- - 。

320
00:24:34,440 --> 00:24:37,030
[Hardison]グレート。そしてあなたは何をしましたか？

321
00:24:37,030 --> 00:24:44,140
[ステラ]そして私がリターンを言っs.string [s.size]。

322
00:24:44,140 --> 00:24:48,560
[Hardison]グレート。

323
00:24:48,560 --> 00:24:51,940
そうでなければnullを返します。はい、サム？

324
00:24:51,940 --> 00:24:55,510
[サム]なぜそれがs.size + 1である必要はありません？

325
00:24:55,510 --> 00:24:58,430
[Hardison]プラス1？ >>うん。 >>はそれを得た。

326
00:24:58,430 --> 00:25:00,980
あなたはうち1つを取っているので、[サム]私は、と思った

327
00:25:00,980 --> 00:25:04,290
その後、あなたは、彼らが求めたものは返すべきではないつもりだ。

328
00:25:04,290 --> 00:25:09,400
[Hardison]そしてこれは我々が0のインデックスのこの全体の問題に話をしていたものばかりだった。

329
00:25:09,400 --> 00:25:11,380
だから我々はこっちにはズームインしている場合。

330
00:25:11,380 --> 00:25:15,650
私たちは右ここにこの男を見れば、あなたは、私たちが飛び出したときに見ることができ

331
00:25:15,650 --> 00:25:19,340
私たちは、インデックス2の要素を炊いてるはずだ。

332
00:25:19,340 --> 00:25:25,200
>> だから我々は大きさが私たちのインデックスと一致した後、最初に私たちのサイズを小さくします。

333
00:25:25,200 --> 00:25:39,650
我々は最初のサイズを減少させていないなら、私たちは-1してからデクリメント大きさをしなければならない。

334
00:25:39,650 --> 00:25:45,270
グレート。すべていいですか？

335
00:25:45,270 --> 00:25:47,530
これについて何か質問はありますか？

336
00:25:47,530 --> 00:25:54,050
同様に、これを書くためのさまざまな方法があります。

337
00:25:54,050 --> 00:26:03,290
実際には、私たちも何かを行うことができます - 私たちはワンライナーを行うことができます。

338
00:26:03,290 --> 00:26:05,770
私たちは、1行の復帰を行うことができます。

339
00:26:05,770 --> 00:26:12,980
我々はそれを実行して、返す前に私たちは実際に増減できます。

340
00:26:12,980 --> 00:26:18,320
だからパッティング -  s.size前。

341
00:26:18,320 --> 00:26:22,060
それはラインが本当に密になります。

342
00:26:22,060 --> 00:26:30,940
どこに違い -  Sサイズとs.size- - 

343
00:26:30,940 --> 00:26:40,130
つまり、この接尾辞 - ので、彼らはそれはpostfix呼び出す - 来る後s.size- - 

344
00:26:40,130 --> 00:26:47,430
s.sizeがインデックスを見つけることの目的のために評価されることを意味

345
00:26:47,430 --> 00:26:50,410
この行が実行されたときには、現在あるように、

346
00:26:50,410 --> 00:26:54,290
そして、これは - の行が実行された後です。

347
00:26:54,290 --> 00:27:00,340
インデックスs.sizeの要素​​がアクセスされた後。

348
00:27:00,340 --> 00:27:07,260
我々が最初に起こるデクリメントしたいので、それは、我々が望むものではありません。

349
00:27:07,260 --> 00:27:10,990
Othewise、我々は境界のうち、効果的に、配列にアクセスすることになるだろう。

350
00:27:10,990 --> 00:27:16,850
我々は、我々が実際にアクセスしたい1上記の要素にアクセスすることになるだろう。

351
00:27:16,850 --> 00:27:23,840
うん、サム？ >>それが速くなったり、1行で、またはしないように以下のRAMを使用しますか？

352
00:27:23,840 --> 00:27:29,620
[Hardison]は正直なところ、それは実際に依存します。

353
00:27:29,620 --> 00:27:34,220
[サムは、判読不能] >>うん、それは異なります。あなたは、コンパイラのトリックを行うことができます

354
00:27:34,220 --> 00:27:41,580
それを認識するようにコンパイラを得るために、通常、私は想像する。

355
00:27:41,580 --> 00:27:44,840
>> だから我々は、このコンパイラの最適化のものについて少し言及した

356
00:27:44,840 --> 00:27:47,400
あなたは、コンパイル時に行うことができます

357
00:27:47,400 --> 00:27:50,580
そしてそれは、コンパイラが把握することができるかもしれないという事のようなものだ

358
00:27:50,580 --> 00:27:54,710
オハイオ州のように、ちょっと、多分私は、一回の操作でこのすべてを行うことができます

359
00:27:54,710 --> 00:27:59,420
RAMからのサイズ変数を読み込むとは対照的に、

360
00:27:59,420 --> 00:28:03,770
戻ってそれを記憶し、それをデクリメントしてから、もう一度それを積み戻し

361
00:28:03,770 --> 00:28:08,000
この操作の残りの部分を処理します。

362
00:28:08,000 --> 00:28:10,710
しかし、一般的に、いや、これは一種の事ではありません

363
00:28:10,710 --> 00:28:20,770
それが大幅に高速化してプログラムを作るために起こっている。

364
00:28:20,770 --> 00:28:26,000
スタック上の任意のより多くの質問？

365
00:28:26,000 --> 00:28:31,360
>> だから、プッシュとポップ。君たちはハッカー版を試してみたい場合は、

366
00:28:31,360 --> 00:28:33,660
我々はハッカー版でやったことは実際に行っている

367
00:28:33,660 --> 00:28:37,670
そして、このスタックは動的に拡張しました。

368
00:28:37,670 --> 00:28:43,190
ここまでプッシュ機能で主に存在する課題は、

369
00:28:43,190 --> 00:28:48,820
その配列を成長させる方法を見つけ出すために

370
00:28:48,820 --> 00:28:52,450
あなたは、スタックに上でより多くの要素をプッシュし続けると。

371
00:28:52,450 --> 00:28:56,000
これは、実際にはあまりにも多くの付加的なコードではありません。

372
00:28:56,000 --> 00:29:00,080
へちょうどコール - あなたは正しくそこにmalloc関数への呼び出しを取得するには忘れてはいけない、

373
00:29:00,080 --> 00:29:03,310
あなたはreallocを呼ぶことにしているときに、次に見つけ出す。

374
00:29:03,310 --> 00:29:06,090
もし興味があるならそれは楽しい挑戦です。

375
00:29:06,090 --> 00:29:11,550
>> しかし、当分の間、のは先に進みましょう、とキューについて話してみましょう。

376
00:29:11,550 --> 00:29:15,680
ここにスクロールします。

377
00:29:15,680 --> 00:29:19,340
キューはスタックの近い兄弟です。

378
00:29:19,340 --> 00:29:25,380
だから、スタック内の、最後に入れたもの

379
00:29:25,380 --> 00:29:28,810
次に取得する最初のものであった。

380
00:29:28,810 --> 00:29:33,600
私たちは、注文、これで最後の先入れ先出し、またはLIFOを持っている。

381
00:29:33,600 --> 00:29:38,390
キューのに対し、あなたはラインに立っている時から期待として、

382
00:29:38,390 --> 00:29:41,980
ラインで取得する最初の人には、キューに入るためにまず、

383
00:29:41,980 --> 00:29:47,630
キューから取得される最初のものです。

384
00:29:47,630 --> 00:29:51,490
我々はグラフを扱う場合キューは、多くの場合、使用されている

385
00:29:51,490 --> 00:29:55,560
我々は、スタックで簡単に話を、次のよう

386
00:29:55,560 --> 00:30:00,260
そしてキューは、他のものの束にするのにも便利です。

387
00:30:00,260 --> 00:30:06,180
頻繁に来ることの一つは、例えば、維持しようとしています

388
00:30:06,180 --> 00:30:12,310
要素のソートされたリスト。

389
00:30:12,310 --> 00:30:17,650
そして、あなたは配列でこれを行うことができます。あなたは、アレイ内の物事のソートされたリストを維持することができます

390
00:30:17,650 --> 00:30:20,650
しかしそのトリッキーその後どこにあるか常に見つけなければならない

391
00:30:20,650 --> 00:30:26,160
次のものを挿入するための適切な場所。

392
00:30:26,160 --> 00:30:28,250
だから、10までの数、1の配列を持っている場合、

393
00:30:28,250 --> 00:30:31,630
そしてその後は、100を介してすべての数字を1にそれを展開したい

394
00:30:31,630 --> 00:30:33,670
、あなたがランダムな順序でこれらの番号を取得し、すべてを維持しようとしている

395
00:30:33,670 --> 00:30:40,650
あなたが通過するようにソートすると、シフトの多くを行うことを終了。

396
00:30:40,650 --> 00:30:43,910
キューおよび基礎となるデータ構造の特定の種類の特定の種類の、

397
00:30:43,910 --> 00:30:46,670
あなたは実際にはかなりシンプルに保つことができます。

398
00:30:46,670 --> 00:30:50,640
あなたがするたびに何かを追加してから、全体を改造する必要はありません。

399
00:30:50,640 --> 00:30:56,770
また、あなたの周りの内部要素のシフトの多くを行う必要もありません。

400
00:30:56,770 --> 00:31:02,990
我々は待ち行列を見てみると、あなたはそれを参照してください - またqueue.cのセクションコード内 - 

401
00:31:02,990 --> 00:31:10,950
私たちはあなたを与えてくれたことを構造体には、我々はスタックにあなたを与えた構造体には本当に似ています。

402
00:31:10,950 --> 00:31:13,770
>> これに対する1つの例外を除いて、その1つの例外があります

403
00:31:13,770 --> 00:31:21,700
、我々は、この追加の整数がヘッドと呼ばれていることである

404
00:31:21,700 --> 00:31:28,120
そしてここで頭が、キューの先頭を追跡するためのものです

405
00:31:28,120 --> 00:31:32,160
またはキューの最初の要素。

406
00:31:32,160 --> 00:31:37,470
スタックでは、我々は、我々が取得しようとしていた要素を追跡することができました

407
00:31:37,470 --> 00:31:40,800
サイズだけを使用して、スタックの一番上、または

408
00:31:40,800 --> 00:31:44,220
キューを持つのに対し、我々は、両端に対処するために抱えている。

409
00:31:44,220 --> 00:31:49,000
我々は、タック末尾で物事をしようとしたが、その後正面から物事を返しています。

410
00:31:49,000 --> 00:31:54,640
だから効果的に、頭を、我々は、キューの先頭のインデックスを持っている

411
00:31:54,640 --> 00:31:58,920
とサイズは私達に、キューの最後のインデックスを与える

412
00:31:58,920 --> 00:32:03,730
私たちは頭から物事を取得し、尾に物事を上に追加することができます。

413
00:32:03,730 --> 00:32:06,890
スタックを持つのに対し、我々は唯一のこれまでスタックの最上位に対処した。

414
00:32:06,890 --> 00:32:08,900
我々は、スタックの底にアクセスする必要もなかった。

415
00:32:08,900 --> 00:32:12,220
我々は唯一のトップに物事を追加し、上部のものを脱いだ

416
00:32:12,220 --> 00:32:17,470
だから我々は、構造体内部には、余分なフィールドを必要としなかった。

417
00:32:17,470 --> 00:32:20,590
それは一般的に意味していますか？

418
00:32:20,590 --> 00:32:27,670
かしこまりました。はい、シャーロット？ [シャーロット、不明朗]

419
00:32:27,670 --> 00:32:32,660
[Hardison]それは素晴らしい質問です、それは講義の中で思いついたものだった。

420
00:32:32,660 --> 00:32:36,290
たぶん、いくつかの例を歩くと、なぜ説明します

421
00:32:36,290 --> 00:32:41,400
我々は、文字列をキューの先頭[0]を使用する必要はありません。

422
00:32:41,400 --> 00:32:46,770
>> だから我々は我々のキューを持っていることを想像して、我々はそれをキュー呼ぶつもりです。

423
00:32:46,770 --> 00:32:49,210
初めに、我々はそれをインスタンス化したときに、

424
00:32:49,210 --> 00:32:53,330
私たちはそれを宣言したとき、我々は何を初期化していない。

425
00:32:53,330 --> 00:32:56,790
それはすべてゴミです。だからもちろん、我々は初期化す​​ることを確認したい

426
00:32:56,790 --> 00:33:00,950
0、合理的なものにするための大きさと頭の両方のフィールド。

427
00:33:00,950 --> 00:33:05,770
我々はまた、先に行くと、私たちのキュー内の要素をnullでした。

428
00:33:05,770 --> 00:33:09,930
そして、この図に収まるために、今私たちのキューは3つの要素のみを保持することができることに気づく。

429
00:33:09,930 --> 00:33:13,150
私たちのスタックは4を握ることができるのに対し、我々のキューには3つだけを保持することができます。

430
00:33:13,150 --> 00:33:18,680
そして、それは図のフィット感を作ることだけです。

431
00:33:18,680 --> 00:33:26,150
ここで最初に起こることは、私たちが "こんにちは"という文字列をエンキューです。

432
00:33:26,150 --> 00:33:30,380
そして、ちょうど我々がここでひどく異なったものには、スタックでやっていないような、

433
00:33:30,380 --> 00:33:39,230
我々は、文字列での[0]の文字列を投げると1によって私たちのサイズを増加します。

434
00:33:39,230 --> 00:33:42,720
私たちは、それが上に置くされる、 "bye"とエンキューします。

435
00:33:42,720 --> 00:33:45,870
だから、これはほとんどの部分のためのスタックのように見えます。

436
00:33:45,870 --> 00:33:53,230
我々は、ここに新しい要素、新しい要素を始めました、サイズが上がって保持します。

437
00:33:53,230 --> 00:33:56,330
私たちは何かをデキューするとき、何がこの時点ではどうなりますか？

438
00:33:56,330 --> 00:34:01,280
我々はデキューする要素ですデキューしたいとき？

439
00:34:01,280 --> 00:34:04,110
[バジル]文字列[0]。 >>ゼロ。正確に右、バジル。

440
00:34:04,110 --> 00:34:10,960
我々は最初の文字列は、この1、 "こんにちは"を取り除くためにしたい。

441
00:34:10,960 --> 00:34:13,170
だから変更他の事は何でしたか？

442
00:34:13,170 --> 00:34:17,010
我々は、スタックの何かオフを取り出したときに注意してください、私たちは、サイズを変更

443
00:34:17,010 --> 00:34:22,080
しかしここで、私たちはその変化物事のカップルを持っている。

444
00:34:22,080 --> 00:34:27,440
サイズの変更が、頭の変更を行うだけでなく、。

445
00:34:27,440 --> 00:34:31,020
これは、以前のシャーロットのポイントに戻ってされています。

446
00:34:31,020 --> 00:34:38,699
なぜ我々は、同様にこの頭を持っていますか？

447
00:34:38,699 --> 00:34:42,110
それが、今ではシャーロットを意味していますか？の>>種類。

448
00:34:42,110 --> 00:34:47,500
の[Hardison]種類は？我々はデキュー時に何が起こったのか？

449
00:34:47,500 --> 00:34:54,340
頭部は今は面白いと何をしたのか？

450
00:34:54,340 --> 00:34:56,449
[シャルロット]ああ、それが変更されたため - 大丈夫。そうですか。

451
00:34:56,449 --> 00:35:02,090
なぜなら頭 - 頭が場所の条件の変化を指している。

452
00:35:02,090 --> 00:35:07,200
それはもはや、常にゼロインデックス一つだ。 >>うん、その通りです。

453
00:35:07,200 --> 00:35:17,660
高い要素をデキューしたらどう起こったことだった

454
00:35:17,660 --> 00:35:20,590
行われていたと我々はこのヘッドフィールドを持っていなかった

455
00:35:20,590 --> 00:35:26,880
我々は常に我々のインデックス0されているキューの先頭にこの文字列を呼び出していたので、

456
00:35:26,880 --> 00:35:30,170
次に我々は、キューの残りの部分をシフトダウンする必要があると思います。

457
00:35:30,170 --> 00:35:36,010
我々は、文字列からから "さようなら" [1]シフトするための文字列に[0]を持っていると思います。

458
00:35:36,010 --> 00:35:38,760
と文字列[2]を押し、文字列[1]。

459
00:35:38,760 --> 00:35:43,050
そして、我々は、要素のリスト全体に対してこれを行う必要があるだろう

460
00:35:43,050 --> 00:35:45,110
要素の配列全体。

461
00:35:45,110 --> 00:35:50,490
そして、我々は配列でこれをやっているとき、それは本当に高価な取得します。

462
00:35:50,490 --> 00:35:53,340
だからここに、それは大したことではありません。私達はちょうど私達の配列の3つの要素を持っています。

463
00:35:53,340 --> 00:35:57,230
しかし、我々は、1000個の要素のキューまたは万要素を持っていた場合、

464
00:35:57,230 --> 00:36:00,060
その後突然、我々は、すべてのループでデキュー·コールの束を作り始める

465
00:36:00,060 --> 00:36:03,930
物事は実際にそれが常にすべてのダウンシフトとスローダウンしようとしている。

466
00:36:03,930 --> 00:36:07,320
あなたは、1、1によるシフト、1によるシフト、1によるシフトによるシフトを知っている。

467
00:36:07,320 --> 00:36:13,650
代わりに、我々はこのヘッドを使用し、我々はそれが本当にポインタではないにもかかわらず、それを "ポインタ"と呼ぶ

468
00:36:13,650 --> 00:36:16,430
厳密な意味で、それがポインタ型ではありません。

469
00:36:16,430 --> 00:36:19,410
それは、int *またはchar *またはそのような何かではありません。

470
00:36:19,410 --> 00:36:28,930
しかし、それは我々のキューの先頭を指しているかを示す。うん？

471
00:36:28,930 --> 00:36:38,800
>> [学生]ちょうど頭にあるものからポップする方法デキューは知っていますか？

472
00:36:38,800 --> 00:36:43,620
[Hardison]どのようにデキューが頭に何でもぽんする方法を知っていますか？ >>右、ええ。

473
00:36:43,620 --> 00:36:49,050
>>それは何を見ていることに設定されているだけでも頭のフィールドです。

474
00:36:49,050 --> 00:36:52,710
だから、この最初のケースでは、我々がここに見れば、

475
00:36:52,710 --> 00:36:55,690
私たちの頭には0、インデックス0です。 >>は右。

476
00:36:55,690 --> 00:37:00,500
[Hardison]は、それだけで大丈夫、まあ、インデックス0の要素は、文字列 "こんにちは"と言うだから

477
00:37:00,500 --> 00:37:03,050
私たちの待ち行列の先頭の要素です。

478
00:37:03,050 --> 00:37:05,570
だから我々はその男をデキューしようとしている。

479
00:37:05,570 --> 00:37:09,800
そして、それは、呼び出し元に返される要素になります。

480
00:37:09,800 --> 00:37:14,540
はい、サアド？ >>だから頭は基本的には設定 - インデックス、それをするつもりだどこ？

481
00:37:14,540 --> 00:37:17,750
それはそれの始まりだ？ >>うん。オーケー。>>

482
00:37:17,750 --> 00:37:22,900
[Hardison]は配列の新たなスタートになってですね。

483
00:37:22,900 --> 00:37:28,930
だから、あなたが何かをデキューするとき、あなたがしなければならないすべては、インデックスq.headにある要素にアクセスされている

484
00:37:28,930 --> 00:37:32,240
そしてそれはあなたがデキューする要素になります。

485
00:37:32,240 --> 00:37:34,930
また、サイズを増減する必要があります。

486
00:37:34,930 --> 00:37:39,430
物事はこれと少しトリッキー取得する場所我々はビットで表示されます。

487
00:37:39,430 --> 00:37:46,520
我々は再びエンキュー場合我々は、現在デキューし、

488
00:37:46,520 --> 00:37:51,300
我々はどこをエンキューしますか？

489
00:37:51,300 --> 00:37:55,000
次の要素は、私たちのキューにどこに行くのでしょうか？

490
00:37:55,000 --> 00:37:57,980
私たちは、 "CS"という文字列をエンキューしてみたいと思います。

491
00:37:57,980 --> 00:38:02,240
それは、どのインデックスに行くのだろうか？ [学生]文字列[2]。 >> 2。

492
00:38:02,240 --> 00:38:04,980
なぜ2と0ではない？

493
00:38:04,980 --> 00:38:13,570
[バジル]今、頭が1であるため、リストの先頭のようなものだそうなんですか？

494
00:38:13,570 --> 00:38:21,220
[Hardison]右。そして、何は、リストの終わりを表す？

495
00:38:21,220 --> 00:38:23,290
私達は私達のキューの終了を示すために何を使っていましたか？

496
00:38:23,290 --> 00:38:25,970
頭は私達のキューの先頭、私達のキューの始まりです。

497
00:38:25,970 --> 00:38:29,530
私達のキューの最後は何ですか？ [学生]サイズ。 >>サイズ、丁度。

498
00:38:29,530 --> 00:38:36,360
それで、我々の新しい要素は大きさでに行くと、私たちが取ることの要素がオフ頭部に外れます。

499
00:38:36,360 --> 00:38:45,390
我々は次の要素をエンキューしたとき、我々は大きさで、それを入れている。

500
00:38:45,390 --> 00:38:48,530
あなたががでていることを置く前に、[学生]は、サイズが右、1でしたか？

501
00:38:48,530 --> 00:38:55,690
[Hardison]右。そうではないかなりのサイズで。サイズ+ 1ではないが、+ヘッド。

502
00:38:55,690 --> 00:38:59,990
私達は頭部量ですべてをシフトしているため。

503
00:38:59,990 --> 00:39:14,270
そこでここでは、今、私たちは、インデックス1から始まり大きさ1のキューを持っている。

504
00:39:14,270 --> 00:39:20,730
尾はインデックス2になります。はい？

505
00:39:20,730 --> 00:39:25,780
>> [学生]をデキュー文字列[0]は、メモリ内の文字列 'のスロットはどうなりますか

506
00:39:25,780 --> 00:39:29,420
ただ基本的には、空になったため、あるいは単に忘れましたか？

507
00:39:29,420 --> 00:39:34,700
[Hardison]うん。この意味で、我々はそれらを忘れている。

508
00:39:34,700 --> 00:39:42,640
私達はのためにそれらのコピーを保存していた場合 - 

509
00:39:42,640 --> 00:39:46,310
多くのデータ構造は、多くの場合、要素の独自のコピーを保存します

510
00:39:46,310 --> 00:39:51,760
データ構造を管理する人は心配しないで済むように

511
00:39:51,760 --> 00:39:53,650
すべてのこれらのポインタが行く場所について。

512
00:39:53,650 --> 00:39:56,000
データ構造は、すべてのコピーに保持し、すべてのものへに保持してい

513
00:39:56,000 --> 00:39:59,580
すべてが適切に解決されないことを確認します。

514
00:39:59,580 --> 00:40:03,140
ただし、この場合には、これらのデータ構造だけで、簡単にするために、

515
00:40:03,140 --> 00:40:05,580
我々は彼らに保存していることを何かのコピーを作成されていません。

516
00:40:05,580 --> 00:40:08,630
[学生]は、だから、これはの連続配列である - ？ >>はい。

517
00:40:08,630 --> 00:40:14,350
我々が定義は、この構造の何だったかを振り返ってみると、それはです。

518
00:40:14,350 --> 00:40:19,110
それは、あなたが見てきたと同じように標準的な配列だ

519
00:40:19,110 --> 00:40:24,280
char *型の配列。

520
00:40:24,280 --> 00:40:26,340
それはしていますか - ？ >>うん、私は思っていた

521
00:40:26,340 --> 00:40:29,130
あなたは最終的にある程度、メモリー不足にあげるなら、

522
00:40:29,130 --> 00:40:32,330
あなたの配列内のすべてのこれらの空のスポットを持っている場合はどうなりますか？

523
00:40:32,330 --> 00:40:36,390
[Hardison]うん、良い点だ。

524
00:40:36,390 --> 00:40:41,530
>> 我々はこの時点では今起こったことを見れば、

525
00:40:41,530 --> 00:40:46,350
私達が私達のキューをいっぱいにしたら、それは次のようになります。

526
00:40:46,350 --> 00:40:50,390
しかし、我々は本当に私たちのキューをいっぱいにしていない

527
00:40:50,390 --> 00:40:57,710
私達はサイズ2のキューを持っていますが、それはインデックス1、で始まっているため、

528
00:40:57,710 --> 00:41:02,160
私たちのヘッドポインタがどこにあるか、それはだから。

529
00:41:02,160 --> 00:41:08,400
あなたが言っていたように、その文字列の要素[0]は、インデックス0に、本当にありません。

530
00:41:08,400 --> 00:41:10,450
それはもう我々のキューではありません。

531
00:41:10,450 --> 00:41:16,460
私達はちょうどに行くと我々はそれをデキューするとき、それを上書きする気にしませんでした。

532
00:41:16,460 --> 00:41:18,700
だから我々はメモリを使い果たしてしまったように見えるにもかかわらず、私たちは本当に持っていない。

533
00:41:18,700 --> 00:41:23,270
私たちが使用するためにその場所を用意しています。

534
00:41:23,270 --> 00:41:29,310
私たちが何かをしようとする最初のデキューした場合に適切な行動、

535
00:41:29,310 --> 00:41:34,420
さようなら寝つくこと、 "バイバイ"が好きです。

536
00:41:34,420 --> 00:41:38,460
今度は私達のキューはインデックス2から始まり、大きさ1である。

537
00:41:38,460 --> 00:41:42,240
そして今、我々がしようとした場合、もう一度何かをエンキュー、50を言う

538
00:41:42,240 --> 00:41:47,880
50はインデックス0にこの場所に行く必要があります

539
00:41:47,880 --> 00:41:51,270
それはまだ私たちのために利用可能だからです。はい、サアド？

540
00:41:51,270 --> 00:41:53,630
[Saadは]それは自動的に発生しますか？

541
00:41:53,630 --> 00:41:56,150
[Hardison]それはかなり自動的には行われません。あなたは数学を行う必要が

542
00:41:56,150 --> 00:42:00,380
それを動作させることが、本質的に、私たちが行ったのは我々だけで巻き付けたされている。

543
00:42:00,380 --> 00:42:04,070
[SAAD]そしてこれはそれの真ん中に穴がある場合、それは大丈夫ですか？

544
00:42:04,070 --> 00:42:08,720
[Hardison]我々は数学が適切に動作させることができればそれはある。

545
00:42:08,720 --> 00:42:15,470
>> そして、それはそれはmod演算子と関係が実際には難しいことではないことが判明した。

546
00:42:15,470 --> 00:42:20,040
だから同じように、我々は、シーザーと暗号のものでやった

547
00:42:20,040 --> 00:42:25,190
MODを使用して、我々は物事が一周して取得し続けることができます

548
00:42:25,190 --> 00:42:28,090
ぐるぐると周りの私達のキューを持つ、

549
00:42:28,090 --> 00:42:32,180
その先頭ポインタが動き回る保つ。

550
00:42:32,180 --> 00:42:38,840
サイズは常にキュー内に実際にある要素の数を尊重していることに注意してください。

551
00:42:38,840 --> 00:42:43,110
それだけを循環保持ヘッドポインタです。

552
00:42:43,110 --> 00:42:49,660
我々は我々が最初に戻った場合は、ここで何が起こったのかを見れば、

553
00:42:49,660 --> 00:42:55,020
そしてあなただけの頭に何が起こるかを見て

554
00:42:55,020 --> 00:42:58,240
私たちは何かをエンキューしたとき、何も頭に起こらなかった。

555
00:42:58,240 --> 00:43:00,970
我々が何かを待ち行列に入れても、何も頭に何が起こっていません。

556
00:43:00,970 --> 00:43:04,130
私たちは何かをデキューするとすぐに、頭が1ずつ上がります。

557
00:43:04,130 --> 00:43:06,600
私たちが何かを待ち行列に入れても、何も頭に起こりません。

558
00:43:06,600 --> 00:43:11,060
私たちが何かをデキューするとき、突然頭にインクリメントされます。

559
00:43:11,060 --> 00:43:14,660
私たちが何かをエンキューしたとき、何も頭に起こりません。

560
00:43:14,660 --> 00:43:20,240
>> 我々は再び何かをデキューした場合、何がこの時点で起こるのでしょうか？

561
00:43:20,240 --> 00:43:23,240
任意の考え？何が頭に起こるでしょうか？

562
00:43:23,240 --> 00:43:27,190
頭に何をすればいいのか

563
00:43:27,190 --> 00:43:32,990
我々は何か他のものをデキューしていた場合はどうなりますか？

564
00:43:32,990 --> 00:43:35,400
頭部は今、インデックス2の位置にある

565
00:43:35,400 --> 00:43:38,920
これは、キューの先頭には文字列[2]であることを意味します。

566
00:43:38,920 --> 00:43:44,280
0を返す[学生]？ >>それは0に戻ります。それはまさに、周りに戻ってラップする必要があります。

567
00:43:44,280 --> 00:43:48,440
これまでのところ、我々は、デキューと呼ばれるたびに、私たちは、頭に1を加えてきた

568
00:43:48,440 --> 00:43:50,960
頭に1を追加して、頭に1を加え、頭に1を追加します。

569
00:43:50,960 --> 00:43:58,400
そのヘッドポインタは、我々の配列の最後のインデックスを取得し、できるだけ早く

570
00:43:58,400 --> 00:44:05,650
それから私達は最初に周りにそれを戻してラップする必要があり、0に戻ります。

571
00:44:05,650 --> 00:44:09,900
[シャーロット]スタックでキューの容量を決定しますか？

572
00:44:09,900 --> 00:44:13,120
[Hardison]このケースでは、我々だけで＃定義された定数を使用してきた。オーケー。>>

573
00:44:13,120 --> 00:44:19,590
[Hardison]は実際のcファイルでは、あなたがそれで少しに行くとマックができます

574
00:44:19,590 --> 00:44:21,710
そしてそれは大きなまたはあなたが望むようにはわずかにします。

575
00:44:21,710 --> 00:44:25,310
[シャーロット]だからあなたはそれを待ち行列を作っているときに、コンピュータが知っているどのように作るのですか

576
00:44:25,310 --> 00:44:29,120
あなたがスタックになりたいどのように大きな？

577
00:44:29,120 --> 00:44:31,700
[Hardison]素晴らしい質問ですね。

578
00:44:31,700 --> 00:44:34,800
いくつかの方法があります。一つは、ちょうど正面にそれを定義することです。

579
00:44:34,800 --> 00:44:42,050
これは4つの要素または要素または50万を持っているキューであることを行っていると言う。

580
00:44:42,050 --> 00:44:45,430
他の方法はハッカー版の人たちがやっていることを行うことです

581
00:44:45,430 --> 00:44:52,310
多くの物事はインチ追加取得としてキューが動的に増加持って関数を作成する

582
00:44:52,310 --> 00:44:54,740
>> [シャルロット]だから最初のオプションで行くことに、あなたはどのような構文を使用しますか

583
00:44:54,740 --> 00:44:57,830
プログラムに通知するために、キューのサイズは何ですか？

584
00:44:57,830 --> 00:45:04,780
[Hardison]ああ。それでは、これから抜け出すことができます。

585
00:45:04,780 --> 00:45:12,650
私はここではまだstack.cので、私はちょうどここに一番上までスクロールするつもりです。

586
00:45:12,650 --> 00:45:17,920
あなたはこの権利をここに見ることができますか？これは＃10容量を定義しています。

587
00:45:17,920 --> 00:45:24,600
そして、これが我々が待ち行列のために持っていることはほぼまったく同じ構文です。

588
00:45:24,600 --> 00:45:28,390
キューを除いて、我々はここで、余分な構造体のフィールドを持っている。

589
00:45:28,390 --> 00:45:32,760
[シャルロット]ああ、私は容量が文字列のための容量を意味思った。

590
00:45:32,760 --> 00:45:36,770
[Hardison]ああ。それは言葉の最大の長さだ。>> >>はそれを得た。

591
00:45:36,770 --> 00:45:41,180
うん。ここに容量 - 偉大なポイントだ。

592
00:45:41,180 --> 00:45:44,000
そして、これはトリッキーなものです

593
00:45:44,000 --> 00:45:49,480
私たちはここで宣言したことはchar *型の配列であるためです。

594
00:45:49,480 --> 00:45:52,770
ポインタの配列。

595
00:45:52,770 --> 00:45:56,690
これは文字の配列である。

596
00:45:56,690 --> 00:46:01,690
これは、あなたがファイルI / O用のバッファを宣言してきたときに見てきたものと考えられます

597
00:46:01,690 --> 00:46:06,840
あなたは、スタック上に手動で文字列を作成してきたとき。

598
00:46:06,840 --> 00:46:09,090
しかし、私たちがここに着いたことはchar *型の配列です。

599
00:46:09,090 --> 00:46:13,400
だからそれはポインタの配列です。

600
00:46:13,400 --> 00:46:18,350
実際、我々は戻ってズームアウト、我々はここで何が起こっているかを見れば

601
00:46:18,350 --> 00:46:23,140
プレゼンテーションでは、その実際の要素は、文字データを参照してください。

602
00:46:23,140 --> 00:46:26,180
配列自体に格納されていません。

603
00:46:26,180 --> 00:46:42,690
何がここで我々の配列内に格納されているのは、文字データへのポインタです。

604
00:46:42,690 --> 00:46:52,560
オーケー。だから我々は、キューのサイズがちょうどスタックと同じようにされている方法を見てきました

605
00:46:52,560 --> 00:46:58,670
サイズは、常にキュー内の現在の要素数を尊重しています。

606
00:46:58,670 --> 00:47:02,720
2エンキューを行った後で、サイズは2です。

607
00:47:02,720 --> 00:47:07,110
デキューを行った後のサイズは今1です。

608
00:47:07,110 --> 00:47:09,330
別のエンキューを行った後でサイズが2まで戻っています。

609
00:47:09,330 --> 00:47:12,340
だから大きさは間違いなく、キュー内の要素数を尊重

610
00:47:12,340 --> 00:47:15,580
その後頭がちょうどサイクリングを続けている。

611
00:47:15,580 --> 00:47:20,210
それは0-1-2、0-1-2、0-1-2から行く。

612
00:47:20,210 --> 00:47:25,620
そして、我々はdequeueを呼び出すたびに、ヘッドポインタは、次のインデックスに増加します。

613
00:47:25,620 --> 00:47:29,930
頭が上に行くとしている場合、それは0に周りにループバックします。

614
00:47:29,930 --> 00:47:34,870
だからということで、我々は、デキュー関数を書くことができます。

615
00:47:34,870 --> 00:47:40,200
そして、我々はあなたたちではなく、実装するためエンキュー機能を残すつもりだ。

616
00:47:40,200 --> 00:47:45,880
>> 私達は私達のキューの要素をデキューする場合は、

617
00:47:45,880 --> 00:47:55,490
我々はスタックのポップ機能を書き始めたとき、ダニエルはやった最初のことは何でしたか？

618
00:47:55,490 --> 00:48:00,490
私はまだ語られなかった誰かから聞いてみましょう。

619
00:48:00,490 --> 00:48:06,710
、見サアドましょう、あなたはダニエルは、彼が書いたポップの最初の文として、何をしたか覚えていますか？

620
00:48:06,710 --> 00:48:08,860
[サアド]がありました、それがあった - 彼は何かをテスト。>>

621
00:48:08,860 --> 00:48:12,140
[サアド]サイズが0より大きい場合。まさに>>。

622
00:48:12,140 --> 00:48:14,390
そしてそのためのテストはどうでしたか？

623
00:48:14,390 --> 00:48:19,090
[サアド]配列の中に何があるのか​​どうかを確認するためにテストしていたね。

624
00:48:19,090 --> 00:48:23,210
[Hardison]うん。その通りです。それが空の場合、それで、あなたは、スタックの外に何かをポップすることはできません。

625
00:48:23,210 --> 00:48:26,510
それが空の場合同様に、キューから何かをデキューできません。

626
00:48:26,510 --> 00:48:30,420
我々はここで我々のデキュー関数の中で、まず最初にすべきことは何ですか、あなたは思いますか？

627
00:48:30,420 --> 00:48:33,860
[サアド]サイズが0より大きい場合は？ >>うん。

628
00:48:33,860 --> 00:48:37,710
このケースでは、私は実際にちょうどそれが0であるかどうかを確認するためにテストしてみた。

629
00:48:37,710 --> 00:48:42,240
それが0である場合、我々は、nullを返すことができる。

630
00:48:42,240 --> 00:48:45,280
しかし、まったく同じロジック。

631
00:48:45,280 --> 00:48:49,110
とのこれを続けましょう。

632
00:48:49,110 --> 00:48:54,600
サイズが0でない場合、我々はデキューする要素はどこにあるのでしょうか？

633
00:48:54,600 --> 00:48:58,550
[サアド]頭では？まさに>>。

634
00:48:58,550 --> 00:49:01,720
私達はちょうど私達のキューの最初の要素を引き出すことができる

635
00:49:01,720 --> 00:49:07,040
先頭の要素にアクセスすることにより。

636
00:49:07,040 --> 00:49:14,630
クレイジー何もない。

637
00:49:14,630 --> 00:49:19,620
その後、我々は何をすべきでしょうか？何が起こっている？

638
00:49:19,620 --> 00:49:23,740
我々はデキューでの話他の事は何でしたか？

639
00:49:23,740 --> 00:49:28,130
私たちのキューが変更されているため、二つのことが、起きるべくして起きる。

640
00:49:28,130 --> 00:49:35,640
[ダニエル]サイズを縮小します。 >>我々はサイズを小さくし、ヘッドを増やす必要があるかも？その通りです。

641
00:49:35,640 --> 00:49:40,600
頭を上げるために、私たちはやみくもに覚えて、頭を上げることができない。

642
00:49:40,600 --> 00:49:45,080
我々だけで行うことはできませんqueue.head + +を

643
00:49:45,080 --> 00:49:51,630
我々はまた、能力によってこのmodを含めなければなりません。

644
00:49:51,630 --> 00:49:54,740
そして、なぜ私たちは、ステラ、容量によってMODのでしょうか？

645
00:49:54,740 --> 00:49:58,680
[ステラ]それが一周しているので。まさに>>。

646
00:49:58,680 --> 00:50:04,750
容量によって、我々はmodが0に戻って周りにラップする必要があるため。

647
00:50:04,750 --> 00:50:07,400
だから今、この時点で、我々は、ダニエルが言ったことを行うことができます。

648
00:50:07,400 --> 00:50:12,700
我々は大きさを増減できます。

649
00:50:12,700 --> 00:50:29,170
そして、我々は単にキューの先頭にあった要素を返すことができます。

650
00:50:29,170 --> 00:50:34,000
最初は危ないの種類を探します。あなたが質問を持っているかもしれません。申し訳ありませんが？

651
00:50:34,000 --> 00:50:37,260
>> [サム]なぜキューの先頭にある第一ですか？それはどこへ行くのでしょうか？

652
00:50:37,260 --> 00:50:42,480
[Hardison]それは下から4行目から来ている。

653
00:50:42,480 --> 00:50:46,060
私達は私達のキューが空でないことを確認するためにテストした後、

654
00:50:46,060 --> 00:50:54,100
我々が最初にchar *を引き出し、私たちは頭指数の前に座っている要素を引き出し

655
00:50:54,100 --> 00:50:58,680
私たちの配列の、私たちの文字列の配列、>>およびコールが最初の？

656
00:50:58,680 --> 00:51:04,500
[Hardison]そして我々はそれが最初の呼び出し。うん。

657
00:51:04,500 --> 00:51:09,850
ちょうどそれをフォローアップするために、なぜあなたは私たちがそれをしなければならなかったと思いますか？

658
00:51:09,850 --> 00:51:18,270
[SAM]各第ちょうどq.stringsを返している[q.head]？ >>うん。

659
00:51:18,270 --> 00:51:23,830
>>我々は、MOD関数でq.headのこの変化をやっているので、

660
00:51:23,830 --> 00:51:27,810
また、戻りライン内でそのを行う方法はありません。

661
00:51:27,810 --> 00:51:31,640
[Hardison]その通りです。あなたは上のスポットだ。サムは完全に上のスポットだ。

662
00:51:31,640 --> 00:51:36,800
我々は、キューの最初の要素を取り出して、変数に格納しなければならなかった理由

663
00:51:36,800 --> 00:51:43,030
我々だけでq.headいた場所は、この行からである

664
00:51:43,030 --> 00:51:47,030
mod演算子は、私たちが行うことができるものがないではあり

665
00:51:47,030 --> 00:51:51,230
1行目の - そしてそれがなくても頭の上に有効になりました。

666
00:51:51,230 --> 00:51:54,480
我々は実際には最初の要素を引き出すために持っているので、その後、ヘッドを調整

667
00:51:54,480 --> 00:52:00,430
サイズを調整した後、私たちが引き出されている要素を返します。

668
00:52:00,430 --> 00:52:02,680
そして、これは我々が後で来るのを見るだろうというものです

669
00:52:02,680 --> 00:52:04,920
リンクリスト、我々は彼らと遊んでよう。

670
00:52:04,920 --> 00:52:08,410
頻繁にあなたが解放またはリンクされたリストを廃棄しているとき

671
00:52:08,410 --> 00:52:13,500
あなたは次の要素、リンクリストの次のポインタを覚えておく必要が

672
00:52:13,500 --> 00:52:16,330
現在の1を廃棄する前に。

673
00:52:16,330 --> 00:52:23,580
なぜならそうしないと、リストに残っているものの情報を捨てる。

674
00:52:23,580 --> 00:52:34,160
あなたがアプライアンスに行けば今、あなたはこれについてqueue.c-Xを開く。

675
00:52:34,160 --> 00:52:39,390
私はqueue.c開く場合だから、私はここでズームさせ、

676
00:52:39,390 --> 00:52:44,970
あなたは同じような見栄えのファイルを持っていることがわかります。

677
00:52:44,970 --> 00:52:49,200
我々はstack.cと、以前持っていたものに似て見栄えのファイル。

678
00:52:49,200 --> 00:52:54,690
私達はちょうど私達がスライドで見たように定義されたキューのための私達の構造を持っている。

679
00:52:54,690 --> 00:52:59,870
>> 私たちは、あなたが何をするのです私たちのエンキュー機能を持っています。

680
00:52:59,870 --> 00:53:04,340
そして、我々はここでデキュー機能を持っています。

681
00:53:04,340 --> 00:53:06,870
ファイル内のデキュー関数が実装されていない、

682
00:53:06,870 --> 00:53:13,230
しかし、私はあなたが好きな場合は、それを入力することができるようにPowerPointの上でそれを元に戻します。

683
00:53:13,230 --> 00:53:16,690
そこで、次の5分間かそこらのために、君たちは、エンキューに取り組む

684
00:53:16,690 --> 00:53:22,570
これは、ほとんどデキューのちょうど逆です。

685
00:53:22,570 --> 00:53:29,560
あなたがエンキューしているときに頭を調整する必要はありませんが、あなたは何を調整する必要があるのですか？

686
00:53:29,560 --> 00:53:38,920
サイズ。あなたがエンキューしたとき、頭が手つかずのままですので、サイズが変更されます。

687
00:53:38,920 --> 00:53:46,920
しかし、それは少しの時間がかかりますか - あなたはMODをいじってあります

688
00:53:46,920 --> 00:53:57,560
新しい要素を挿入する位置を正確に把握する指標。

689
00:53:57,560 --> 00:54:03,080
だから私は、スライド上のデキューを戻して、あなたを少し男をあげる、

690
00:54:03,080 --> 00:54:05,200
君たちは疑問を持っていると、私たちができることをそれらを叫ぶ

691
00:54:05,200 --> 00:54:09,220
すべてのグループとしてそれらについて話しています。

692
00:54:09,220 --> 00:54:13,960
また、無関心サイズで - あなたはサイズを調整するときは、常にちょうど缶 - 

693
00:54:13,960 --> 00:54:18,720
あなたは今までサイズをmodにする必要がありますか？ [ダニエル]第>>あなたは、サイズをmodに権利を持っていない。

694
00:54:18,720 --> 00:54:24,260
you're場合サイズは、常になるので - 、あなたは適切なものを管理していると仮定して

695
00:54:24,260 --> 00:54:30,840
サイズは、常に0と3の間になります。

696
00:54:30,840 --> 00:54:38,680
あなたがエンキューをやっているときにmodにどこにありますか？

697
00:54:38,680 --> 00:54:41,060
頭だけのために[学生]。頭だけのために>>、正確に。

698
00:54:41,060 --> 00:54:44,620
そして、なぜあなたは、エンキューでまったくmodにする必要がありますか？

699
00:54:44,620 --> 00:54:48,830
あなたがMODする必要があるだろうという状況はいつですか？

700
00:54:48,830 --> 00:54:53,630
あなたはスペースでものを持っている場合は、スペース1と2のように[学生]

701
00:54:53,630 --> 00:54:55,950
その後あなたは0から何かを追加する必要がありました。

702
00:54:55,950 --> 00:55:02,570
[Hardison]ええ、その通りです。だからあなたのヘッドポインタは非常に最後にある場合は、

703
00:55:02,570 --> 00:55:14,210
またはあなたのサイズに加えてあなたの頭が大きい場合、あるいはむしろ、キュー周りをラップしようとしている。

704
00:55:14,210 --> 00:55:17,830
>> だから我々は今、スライドにここまで持っていること、このような状況で、

705
00:55:17,830 --> 00:55:24,370
私は、今すぐ何かをキューに登録する場合

706
00:55:24,370 --> 00:55:31,110
私たちは、インデックス0で何かをエンキューする。

707
00:55:31,110 --> 00:55:35,450
だから、50がどこに行くかを見て、私はエンキュー50を呼び出す場合、

708
00:55:35,450 --> 00:55:40,840
それは一番下にあり下がる。これは、インデックス0になります。

709
00:55:40,840 --> 00:55:44,160
それは、すでにデキューされた 'こんにちは'を置き換えます。

710
00:55:44,160 --> 00:55:46,210
[ダニエル]あなたがすでにデキューでの世話をしないでください？

711
00:55:46,210 --> 00:55:50,550
なぜそれがエンキューで頭を使って何をするのでしょうか？

712
00:55:50,550 --> 00:55:55,770
[Hardison]ああ、そうあなたが頭を変更していない、ごめんなさい。

713
00:55:55,770 --> 00:56:02,310
しかし、あなたがアクセスしているときにmod演算子を使用する必要があります

714
00:56:02,310 --> 00:56:04,250
あなたがアクセスしているときにエンキューする要素

715
00:56:04,250 --> 00:56:06,960
あなたのキュー内の次の要素。

716
00:56:06,960 --> 00:56:10,960
[バジル]私はそれをしなかった、と私はそこに "成功"を得た。

717
00:56:10,960 --> 00:56:13,370
[ダニエル]ああ、私は何を言ってるのか理解しています。

718
00:56:13,370 --> 00:56:16,240
[Hardisonは]だからあなたはdidn't  - あなただけq.sizeでやった？

719
00:56:16,240 --> 00:56:20,670
[バジル]うん。私はちょうどに側面を変え、私の頭で何もしませんでした。

720
00:56:20,670 --> 00:56:24,300
[Hardison]あなたが実際に何かあると頭をリセットする必要はありません、

721
00:56:24,300 --> 00:56:31,650
しかし、文字列の配列に変換するときに、インデックス、

722
00:56:31,650 --> 00:56:39,500
あなたは実際に、先に行くと、次の要素がどこにあるか計算する必要が

723
00:56:39,500 --> 00:56:44,230
スタックを小枝、あなたのスタック内の次の要素が常にあったので、

724
00:56:44,230 --> 00:56:48,740
サイズに対応したインデックス位置にある。

725
00:56:48,740 --> 00:56:55,850
我々は我々のスタックプッシュ機能に戻って見上げると、

726
00:56:55,850 --> 00:57:03,100
我々は常に、インデックスのサイズで私たちの新しい要素を右にポンと置くことができます。

727
00:57:03,100 --> 00:57:06,710
キューを持つのに対し、我々はそれを行うことはできません

728
00:57:06,710 --> 00:57:10,340
我々はこのような状況にいる場合があるため、

729
00:57:10,340 --> 00:57:18,130
我々は待ち行列に入れば、50私たちの新しい文字列には文字列[1]で右に行くだろう

730
00:57:18,130 --> 00:57:20,540
その我々が行うにはしたくない。

731
00:57:20,540 --> 00:57:41,200
私たちは、新しい文字列のインデックスは0で行くようにしたい。

732
00:57:41,200 --> 00:57:44,320
>> はい - 誰かいますか？ [学生]私は疑問を持っているが、それは本当に関係ないです。

733
00:57:44,320 --> 00:57:48,160
誰かがちょうどpredはポインタのようなものを呼び出したときに、それはどういう意味ですか？

734
00:57:48,160 --> 00:57:51,260
そのための短い名前は何ですか？私はそれだけで名前を知っている。

735
00:57:51,260 --> 00:57:59,110
[Hardison] PREDポインタ？見てみましょう。どういう事情で？

736
00:57:59,110 --> 00:58:01,790
[学生]は挿入のことだった。あなたが望むなら私は後でお聞きすることができます

737
00:58:01,790 --> 00:58:03,920
それは実際には関係ありませんが、私からといって - 

738
00:58:03,920 --> 00:58:07,300
[Hardison]講義からDavidの挿入コードから？

739
00:58:07,300 --> 00:58:10,860
我々はそれをプルアップし、そのことについて話すことができます。

740
00:58:10,860 --> 00:58:15,550
我々はその次の話だろう、一度我々は、リンクされたリストを取得する。

741
00:58:15,550 --> 00:58:21,440
>> だから本当にすぐエンキュー関数がどのように見えるかを見てみましょう。

742
00:58:21,440 --> 00:58:26,530
人々があなたのエンキュー行で実行しようとしました最初のことは何でしたか？このキューに？

743
00:58:26,530 --> 00:58:29,960
あなたはスタックがプッシュするためにやったことに似ています。

744
00:58:29,960 --> 00:58:32,080
あなたは何をしたのか、ステラ？

745
00:58:32,080 --> 00:58:35,050
[ステラ、不明朗]

746
00:58:35,050 --> 00:58:45,700
[Hardison]その通りです。 （== CAPACITYをq.size）の場合 - 

747
00:58:45,700 --> 00:58:54,720
私は右の場所に私のブレースを配置する必要があります -  falseを返します。

748
00:58:54,720 --> 00:59:01,370
少し拡大します。オーケー。

749
00:59:01,370 --> 00:59:03,800
今、私たちがしなければならなかった次の事は何ですか？

750
00:59:03,800 --> 00:59:11,370
単にスタックと同じように、適切な場所に挿入されます。

751
00:59:11,370 --> 00:59:16,010
そして挿入する正しい場所はそう何でしたか？

752
00:59:16,010 --> 00:59:23,170
スタックとそれはそれは非常に、というわけではないこれで、インデックスの大きさだった。

753
00:59:23,170 --> 00:59:30,210
[ダニエル]私はq.head  - またはしている -  >> q.strings？ >>うん。

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size MOD容量]？

755
00:59:40,470 --> 00:59:42,740
[Hardison]我々は、おそらくこれを囲むカッコを入れたい

756
00:59:42,740 --> 00:59:48,830
私たちはみんなに適切な優先などのcleartを取得していること。

757
00:59:48,830 --> 00:59:55,800
そして、それと等しく設定？ strに？>> strに。>>グレート。

758
00:59:55,800 --> 01:00:00,160
そして今、我々がしなければならない最後のものは何ですか？

759
01:00:00,160 --> 01:00:06,780
我々はスタックに行ったように。 >>サイズをインクリメント？ >>サイズを増やします。

760
01:00:06,780 --> 01:00:13,830
ブーム。その後、スターターコードは単にデフォルトでfalseが返されたため、

761
01:00:13,830 --> 01:00:27,460
我々はすべてが通過するとすべてがうまくいけば、これをtrueに変更したい。

762
01:00:27,460 --> 01:00:33,050
かしこまりました。それはセクションの情報がたくさんです。

763
01:00:33,050 --> 01:00:39,480
我々は、かなりオーバーしていない。我々は、片方向リンクリストについて本当にすぐお話したいと思います。

764
01:00:39,480 --> 01:00:44,010
私はこれを我慢しますので、後でそれに戻って行くことができます。

765
01:00:44,010 --> 01:00:50,850
しかし、ここではより多くのちょうどいくつかのスライドのために私たちのプレゼンテーションに戻りましょう。

766
01:00:50,850 --> 01:00:53,790
だから、エンキューがTODOですが、今、私たちはそれをやった。

767
01:00:53,790 --> 01:00:57,430
>> 今度は、一重リンクリストを見てみましょう。

768
01:00:57,430 --> 01:01:00,040
私たちは、講義の中で、これらの少し話しました。

769
01:01:00,040 --> 01:01:02,540
我々は人々を持っていた場所をどのようにあなたたちの多くはデモを見た

770
01:01:02,540 --> 01:01:08,220
ぎこちなくお互い保持番号を指す？ >>私はそれにあった。

771
01:01:08,220 --> 01:01:16,620
>>君たちはどう思いましたか？うまくいけば、これらを少し分かりやすく説明することにしましたか？

772
01:01:16,620 --> 01:01:25,990
リストでは、それは我々がノードを呼び出ししようとしているこのタイプを扱うことが判明した。

773
01:01:25,990 --> 01:01:32,520
キューとスタックを持つのに対し、我々は、我々は、スタックでキューを呼び出したいという構造を持っていた

774
01:01:32,520 --> 01:01:34,860
我々は、スタック型で、これらの新しいキューを持っていた

775
01:01:34,860 --> 01:01:39,240
ここにリストが本当にただのノードの束で構成されています。

776
01:01:39,240 --> 01:01:45,920
文字列は文字のちょうど束されるのと同じ方法で、すべてが隣同士に並​​んでいた。

777
01:01:45,920 --> 01:01:50,650
リンクリストは、ただのノードと他のノードと他のノードと他のノードである。

778
01:01:50,650 --> 01:01:55,080
とむしろ一緒に、すべてのノードを壊して、近接してそれらを保存するよりも

779
01:01:55,080 --> 01:01:58,090
右隣同士にメモリ内のすべての、

780
01:01:58,090 --> 01:02:04,470
この次のポインタを持つことは、私たちがランダムに、どこのノードを格納することができます。

781
01:02:04,470 --> 01:02:10,500
そして、ワイヤの種類は、それらすべてを一緒に1から次を指すように設定します。

782
01:02:10,500 --> 01:02:15,850
>> そして、これはアレイ上に持っていたことの大きな利点は、何でしたか？

783
01:02:15,850 --> 01:02:21,680
格納するすべてのものの上に連続的にちょうど隣同士に立ち往生？

784
01:02:21,680 --> 01:02:24,190
あなたは覚えていますか？うん？ >>動的メモリ割り当て？

785
01:02:24,190 --> 01:02:27,220
どのような意味に絞っ動的メモリ割り当て？

786
01:02:27,220 --> 01:02:31,780
あなたはそれが大きく、あなたの全体の配列を移動する必要はありません作り続けることができるという点で[学生]？

787
01:02:31,780 --> 01:02:40,940
[Hardison]その通りです。だから、それの真ん中に新しい要素を入れたい配列を持つ、

788
01:02:40,940 --> 01:02:45,320
あなたは、スペースを作るためにすべてのものをシフトする必要があります。

789
01:02:45,320 --> 01:02:47,880
と同じように、我々は、キューとの話

790
01:02:47,880 --> 01:02:50,080
我々はそのヘッドポインタを保つ理由だと、

791
01:02:50,080 --> 01:02:52,050
我々は常に物事をシフトしていないようにします。

792
01:02:52,050 --> 01:02:54,520
あなたが大きな配列を持っている場合、それは高価な取得するため、

793
01:02:54,520 --> 01:02:57,130
そしてあなたは常にこれらのランダムな挿入をやっている。

794
01:02:57,130 --> 01:03:00,820
リストを持つのに対し、あなたがしなければならないすべては、新しいノードにそれをスローで

795
01:03:00,820 --> 01:03:06,330
ポインタを調整し、作業は完了です。

796
01:03:06,330 --> 01:03:10,940
何がこのことについて吸う？

797
01:03:10,940 --> 01:03:16,830
それを除いては配列としてで動作するように簡単ではないという事実から？うん？

798
01:03:16,830 --> 01:03:22,980
[ダニエル]まあ、私はそれがリンクされたリスト内の特定の要素にアクセスするためにはるかに困難だと思う？

799
01:03:22,980 --> 01:03:30,470
[Hardison]あなたがちょうどあなたのリンクリストの途中で任意の要素にジャンプすることはできません。

800
01:03:30,470 --> 01:03:33,800
どのようにして、代わりにそれをしなければならないのですか？あなたは全体のことをステップ実行する必要があります。>>

801
01:03:33,800 --> 01:03:35,660
[Hardison]うん。あなたは、一度に1つずつ、一つずつ通過する必要があります。

802
01:03:35,660 --> 01:03:38,480
それは巨大だ - それは痛みです。

803
01:03:38,480 --> 01:03:41,550
他のは何ですか - これまで別の没落はそこだ。

804
01:03:41,550 --> 01:03:45,340
[バジル]あなたは前方と後方に行くことができないのですか？あなたは、一つの方向に行かなければならない？

805
01:03:45,340 --> 01:03:48,570
[Hardison]うん。それでは、どのように我々は時々、それを解決するのですか？

806
01:03:48,570 --> 01:03:53,370
[バジル]はリストを二重にリンクされた？まさに>>。二重リンクリストがあります。

807
01:03:53,370 --> 01:03:55,540
もあります - 申し訳ありません？

808
01:03:55,540 --> 01:03:57,620
>> [サム]がそのPREDものを使用するのと同じです - 

809
01:03:57,620 --> 01:04:01,090
私はちょうど思い出した、predは事は何のためであることではありませんか？

810
01:04:01,090 --> 01:04:05,850
ことは、二重の間に、単独ではありませんか？

811
01:04:05,850 --> 01:04:10,020
彼がやっていたまさにで[Hardison]レッツ外観。

812
01:04:10,020 --> 01:04:15,760
だからここに私達は行く。ここにリストコードがあります。

813
01:04:15,760 --> 01:04:25,620
ここで我々はここで、predptrを持っています。あなたが話していたものですか？

814
01:04:25,620 --> 01:04:30,750
だから、これはあった - 彼はリストを解放し、彼はそれへのポインタを格納しようとしている。

815
01:04:30,750 --> 01:04:35,000
これは二重に、単一リンク·リストではありません。

816
01:04:35,000 --> 01:04:40,090
このリストを解放することについて話しているので、我々は、後でこれについての詳細を話すことができる

817
01:04:40,090 --> 01:04:42,900
そして私は、最初のいくつかの他のものを見せたいと思います。

818
01:04:42,900 --> 01:04:51,480
それだけだ - それはptrの値を覚えている

819
01:04:51,480 --> 01:04:54,170
[学生]ああ、それは先行するポインタですか？ >>うん。

820
01:04:54,170 --> 01:05:04,070
我々は、その後predptrが何であるかを我々が自由前にptr自体を増やすことができますように。

821
01:05:04,070 --> 01:05:09,130
我々は自由なptrが、その後、右のptr = ptrは次の呼び出しができないので？

822
01:05:09,130 --> 01:05:11,260
それは悪いことだ。

823
01:05:11,260 --> 01:05:20,940
だから、戻ってこの男に、見てみましょう。

824
01:05:20,940 --> 01:05:23,900
>> リストについては、他の悪いことは、その配列を持つ一方である

825
01:05:23,900 --> 01:05:26,520
我々だけで、自身が隣同士に積み重ねられたすべての要素を持っている

826
01:05:26,520 --> 01:05:29,050
ここで我々はまた、このポインタを導入しています。

827
01:05:29,050 --> 01:05:34,060
だから我々は使用しなくしていること、メモリの追加チャンクはあり

828
01:05:34,060 --> 01:05:37,910
私たちは私たちのリストに格納していることのすべての要素について。

829
01:05:37,910 --> 01:05:40,030
我々は柔軟性を得るが、それにはコストがかかります。

830
01:05:40,030 --> 01:05:42,230
それは、今回のコストが付属しています

831
01:05:42,230 --> 01:05:45,270
そしてそれはあまりにも、このメモリのコストが付属しています。

832
01:05:45,270 --> 01:05:47,800
我々は今、配列内のすべての要素を通過する必要があるという意味での時間

833
01:05:47,800 --> 01:05:58,670
インデックス10に1つずつ、またはその配列内のインデックス10だったでしょうを見つけることができます。

834
01:05:58,670 --> 01:06:01,230
>> 本当に素早く、ときに我々は図外にこれらのリストを、

835
01:06:01,230 --> 01:06:05,980
一般的に我々は、リストの先頭またはリストの最初のポインタにしがみつく

836
01:06:05,980 --> 01:06:08,010
そしてこれが本当のポインタであることに注意してください。

837
01:06:08,010 --> 01:06:11,100
それはちょうど4バイトです。それは実際のノード自体ではありません。

838
01:06:11,100 --> 01:06:17,120
だから、それはそれでなくint型の値を持たず、次のポインタを持っていないことがわかります。

839
01:06:17,120 --> 01:06:20,790
それは文字通りただのポインタだ。

840
01:06:20,790 --> 01:06:23,550
これは、実際のノード構造体である何かを指すようになるだろう。

841
01:06:23,550 --> 01:06:28,480
[SAM]ノードと呼ばれるポインタ？ >>これは - ない。これは、データ型ノードの何かへのポインタです。

842
01:06:28,480 --> 01:06:32,540
これは、ノード構造体へのポインタです。 >>ああ、大丈夫。

843
01:06:32,540 --> 01:06:36,870
左の図では、右側のコード。

844
01:06:36,870 --> 01:06:42,190
我々は、開始するには良い方法ですnullに設定することができます。

845
01:06:42,190 --> 01:06:49,850
ときにダイアグラムには、次のいずれかをnullとしてそれを書くか、またはあなたはそれを好きでそれを介して行を置く。

846
01:06:49,850 --> 01:06:53,910
>> リストを操作するための最も簡単な方法の一つは、

847
01:06:53,910 --> 01:06:57,430
そして我々は、両方のprependを行う尋ねると、2つの違いを見るためにアペンド

848
01:06:57,430 --> 01:07:01,320
しかし、先頭に追加は間違いなく簡単です。

849
01:07:01,320 --> 01:07:05,790
あなたが前に付加するとき、あなたはこの事実はどこにある - あなたが前に付加したとき（7）、

850
01:07:05,790 --> 01:07:10,050
あなたは、ノードの構造体を移動して、作成

851
01:07:10,050 --> 01:07:13,870
そしてあなたは、我々はそれを前に付けているので、今ので、それを指すように最初に設定

852
01:07:13,870 --> 01:07:17,240
それは、リストの先頭になるだろう。

853
01:07:17,240 --> 01:07:22,540
我々の別のノードを作成しプリペンド（3）が、今3が7の前に来る場合。

854
01:07:22,540 --> 01:07:31,130
だから我々は本質的に私達のリストの上に物事を推進している。

855
01:07:31,130 --> 01:07:34,720
さて、あなたは、プリペンド、時には人々はそれがプッシュ呼び出すことがわかります

856
01:07:34,720 --> 01:07:39,600
あなたのリストに新しい要素をプッシュしているので。

857
01:07:39,600 --> 01:07:43,270
それは、リストの先頭に削除することも簡単です。

858
01:07:43,270 --> 01:07:45,650
だから人々はしばしば、そのポップアップを呼び出します。

859
01:07:45,650 --> 01:07:52,200
そしてそのように、リンクされたリストを使用してスタックをエミュレートすることができます。

860
01:07:52,200 --> 01:07:57,880
おっと。申し訳ありませんが、今、私たちは、appendに取得している。そこでここでは、（7）が付け、今、私たちは（3）を付けます。

861
01:07:57,880 --> 01:08:02,600
（4）我々は、このリストの上に何か他のものを先頭に付加した場合、我々が前に付加した場合

862
01:08:02,600 --> 01:08:06,540
その後、我々は4、次に3、その後7を持っていると思います。

863
01:08:06,540 --> 01:08:14,220
それでは、私たちがポップして削除3、4を削除することができ、7を削除します。

864
01:08:14,220 --> 01:08:16,500
多くの場合、これを考えるより直感​​的な方法は、appendを使うことです。

865
01:08:16,500 --> 01:08:20,310
だから私はそれがここに追記してどのように見えるかを外に図解しました。

866
01:08:20,310 --> 01:08:23,380
ここでは、添付の（7）何が違うのを見ていません

867
01:08:23,380 --> 01:08:25,160
リスト内の1つの要素だけが存在だからです。

868
01:08:25,160 --> 01:08:28,620
と追加（3）終了時にそれを置きます。

869
01:08:28,620 --> 01:08:31,020
たぶん、あなたは今のappendとのトリックを見ることができます

870
01:08:31,020 --> 01:08:36,600
それは、リストの先頭がどこにあるか私達が知っているだけですので、

871
01:08:36,600 --> 01:08:39,450
あなたがリストを介してすべての道を歩かなければならないリストに追加する

872
01:08:39,450 --> 01:08:46,500
、最後に取得を停止し、その後、ノードとポンと置くすべてのものを構築します。

873
01:08:46,500 --> 01:08:50,590
すべてのものを配線します。

874
01:08:50,590 --> 01:08:55,170
だからプリペンドと、我々としてはただ、本当に迅速にこれを介してリッピング

875
01:08:55,170 --> 01:08:58,170
あなたがリストに付加した場合、それはかなり簡単です。

876
01:08:58,170 --> 01:09:02,960
>> あなたの新しいノードを作成し、いくつかの動的なメモリ割り当てを伴う。

877
01:09:02,960 --> 01:09:09,830
そこでここでは、malloc（）を使用してノードの構造体を作っている。

878
01:09:09,830 --> 01:09:14,710
それは後でのための私達のためのメモリを確保しますので、我々が使っているので、malloc関数

879
01:09:14,710 --> 01:09:20,350
我々はこれをしたくないので - 私たちは、このメモリは長期間持続したいと思います。

880
01:09:20,350 --> 01:09:25,350
そして、我々は我々だけで割り当てたメモリ内の領域へのポインタを取得します。

881
01:09:25,350 --> 01:09:29,260
我々は、ノードのサイズを使用して、我々はフィールドを合計しないでください。

882
01:09:29,260 --> 01:09:31,899
我々は、手動で、バイト数を生成しない

883
01:09:31,899 --> 01:09:39,750
代わりに我々は、我々は適切なバイト数を取得している知っているようにsizeofを使用しています。

884
01:09:39,750 --> 01:09:43,660
私たちは、malloc呼び出しが成功したことをテストしてください。

885
01:09:43,660 --> 01:09:47,939
これは、一般的に何かやりたいことがあります。

886
01:09:47,939 --> 01:09:52,590
最近のマシンでは、メモリが不足することは簡単だものではありません

887
01:09:52,590 --> 01:09:56,610
あなたはもののトンを割り当て、巨大なリストを作っている限り、

888
01:09:56,610 --> 01:10:02,220
しかし、あなたは、iPhoneやAndroidのように、言う、のためのものを構築している場合、

889
01:10:02,220 --> 01:10:05,230
あなたは強烈な何かをやっている場合は特に、限られたメモリリソースを持っている。

890
01:10:05,230 --> 01:10:08,300
だから練習に入るために良いことだ。

891
01:10:08,300 --> 01:10:10,510
>> ここで私はカップルの異なる機能を使用していることに注目してください

892
01:10:10,510 --> 01:10:12,880
あなたは、新しいの一種であることを見てきた。

893
01:10:12,880 --> 01:10:15,870
だから、fprintfはprintfのようになっている。

894
01:10:15,870 --> 01:10:21,320
その最初の引数を除いて、印刷したいストリームです。

895
01:10:21,320 --> 01:10:23,900
この場合において、我々は標準エラー文字列に印刷したい

896
01:10:23,900 --> 01:10:29,410
これは、標準outstreamとは異なります。

897
01:10:29,410 --> 01:10:31,620
デフォルトでは、同じ場所に表示されます。

898
01:10:31,620 --> 01:10:34,600
また、端末に出力しますが、次のことができます - 

899
01:10:34,600 --> 01:10:38,790
これらのコマンドを使用して、あなたについて、リダイレクト技術を学んだ

900
01:10:38,790 --> 01:10:42,290
あなたは問題セット4のトミーのビデオで学んだ、あなたはそれを指示することができます

901
01:10:42,290 --> 01:10:47,900
異なる領域にしてから、終了して、プログラム、右ここで、終了します。

902
01:10:47,900 --> 01:10:50,440
これは、mainから返っような本質的な

903
01:10:50,440 --> 01:10:53,600
ここでリターンは何もしませんので、我々は出口を使用することを除いて。

904
01:10:53,600 --> 01:10:57,140
我々は、主にいないので、戻って、我々が望むようなプログラムは終了しません。

905
01:10:57,140 --> 01:11:03,020
だから我々は、exit関数を使用して、それはエラーコードを与える。

906
01:11:03,020 --> 01:11:11,890
その後、ここで我々は、iに等しくなるように新しいノードのvalueフィールドに、そのIフィールドを設定した後、我々はそれを配線。

907
01:11:11,890 --> 01:11:15,530
我々は、最初に指すように新しいノードの次のポインタを設定

908
01:11:15,530 --> 01:11:20,460
し、最初の時点で、新しいノードを指すようになります。

909
01:11:20,460 --> 01:11:25,120
これらのコードの最初の行は、我々は実際に新しいノードを構築している。

910
01:11:25,120 --> 01:11:27,280
この関数の最後の2行が、最初のものではない。

911
01:11:27,280 --> 01:11:30,290
あなたが実際にヘルパー関数に、関数に引き出すことができます。

912
01:11:30,290 --> 01:11:32,560
頻繁に私は何をすべきかということは、私は、関数にそれを抜く

913
01:11:32,560 --> 01:11:36,040
私はそれをビルドノードのような何か、呼び出し

914
01:11:36,040 --> 01:11:40,410
そしてそれはかなり小さいプリペンド機能を保持し、それは、ちょうど3行です。

915
01:11:40,410 --> 01:11:48,710
自分のビルドノード関数の呼び出しを行ってから、私のワイヤすべてをバックアップ。

916
01:11:48,710 --> 01:11:51,970
>> 私がお見せしたい最終的なもの、

917
01:11:51,970 --> 01:11:54,030
と私は、あなたが自分で追加し、すべてのことをやらせるよ

918
01:11:54,030 --> 01:11:57,500
リストを反復処理する方法です。

919
01:11:57,500 --> 01:12:00,780
リストを反復処理するためのさまざまな方法の束があります。

920
01:12:00,780 --> 01:12:03,140
この場合において、我々はリストの長さを見つけるつもりだ。

921
01:12:03,140 --> 01:12:06,570
だから我々は長さ= 0から始まります。

922
01:12:06,570 --> 01:12:11,580
これは文字列のstrlenを書き込むと非常に似ています。

923
01:12:11,580 --> 01:12:17,780
これは、私は右ここでは、このforループでは、お見せしたいものです。

924
01:12:17,780 --> 01:12:23,530
それはちょっとファンキーに見える、それはいつものではないのint i = 0のときは、i <何でも、i + +は。

925
01:12:23,530 --> 01:12:34,920
代わりに、それはリストの先頭になるように私たちの変数nを初期化している。

926
01:12:34,920 --> 01:12:40,620
私たちのイテレータ変数がnullでないことをしながら、その後、我々は続ける。

927
01:12:40,620 --> 01:12:46,340
慣例により、私達のリストの末尾にはnullになり、ためです。

928
01:12:46,340 --> 01:12:48,770
そして、むしろ+ +を行うよりも、インクリメントする

929
01:12:48,770 --> 01:12:57,010
+のリンクリストに相当する+ N = N->隣にあります。

930
01:12:57,010 --> 01:13:00,410
>> 我々は時間がなくなっているので、私はあなたがここにギャップを埋めることができます。

931
01:13:00,410 --> 01:13:09,300
あなたはspellrのpsetをに取り組むようにしかし、このことを覚えておいて。

932
01:13:09,300 --> 01:13:11,650
リンクリスト、ハッシュテーブルを実装している場合、

933
01:13:11,650 --> 01:13:14,010
間違いなく非常に便利になるだろう。

934
01:13:14,010 --> 01:13:21,780
そして、物事をループするために、このイディオムを持つことは、うまくいけば、ずっと楽に生活していきます。

935
01:13:21,780 --> 01:13:25,910
どの質問でも、迅速に？

936
01:13:25,910 --> 01:13:28,920
[サム]あなたは完成したSLLとscを出すのでしょうか？

937
01:13:28,920 --> 01:13:38,360
[Hardison]うん。私は完成したスライドを送り出すとsllスタックとqueue.csを完了します。

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]