1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Sekcio 6: Malpli Komfortaj]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Universitato Harvard]

3
00:00:05,040 --> 00:00:07,320
[Jen CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Bone. Bonvenon sekcio 6.

5
00:00:11,840 --> 00:00:14,690
Ĉi tiu semajno, ni tuj parolos pri datumstrukturoj en transeco,

6
00:00:14,690 --> 00:00:19,780
ĉefe ĉar ĉi tiu semajno problemo surtabligis spellr

7
00:00:19,780 --> 00:00:24,410
faras tutan faskon da malsamaj datumstrukturo tuŝo.

8
00:00:24,410 --> 00:00:26,520
Ekzistas multajn malsamajn manierojn vi povas iri per la problemon aro,

9
00:00:26,520 --> 00:00:31,570
kaj la pli datumstrukturoj vi scias pri la pli malvarmeta aĵoj vi povas fari.

10
00:00:31,570 --> 00:00:34,990
>> Do ni komenci. Unue ni iras por paroli pri piloj,

11
00:00:34,990 --> 00:00:37,530
la pilo kaj vosto datumstrukturoj, ke ni tuj paroli.

12
00:00:37,530 --> 00:00:40,560
Provizejon kaj vostoj estas vere utila, kiam ni komencis paroli pri grafikaĵoj,

13
00:00:40,560 --> 00:00:44,390
kiuj ni ne tuj faros tiel de nun.

14
00:00:44,390 --> 00:00:52,820
Sed ili estas vere bona por kompreni unu el la grandaj fundamentaj datumstrukturoj de CS.

15
00:00:52,820 --> 00:00:54,880
La priskribo de la problemo aro specifo,

16
00:00:54,880 --> 00:00:59,260
se vi tiri ĝin, ĝi raportas piloj kiel simila al

17
00:00:59,260 --> 00:01:05,239
la amaso de manĝoĉambro pletoj, ke vi havas en la kafejo ĉe la manĝ salonoj

18
00:01:05,239 --> 00:01:09,680
kie al la manĝ personaro venos kaj metas la manĝ pletoj kuris post ili jam purigis ilin,

19
00:01:09,680 --> 00:01:12,000
ili pilo ili unu super la alia.

20
00:01:12,000 --> 00:01:15,050
Kaj poste, kiam la infanoj venis por ricevi manĝon,

21
00:01:15,050 --> 00:01:19,490
ili tiri la pletoj ekstere, unue la plej supra, tiam la sub ĝi, tiam la sub tio.

22
00:01:19,490 --> 00:01:25,190
Do, en efekto, la unua pleto ke la manĝ bastonon sufoki estas la lasta kiu prenas demetis.

23
00:01:25,190 --> 00:01:32,330
La lasta kiu la manĝ bastonon surmetis estas la unua kiu prenas demetis por vespermanĝo.

24
00:01:32,330 --> 00:01:38,100
En la problemon aro de spec, kiujn vi povas elŝuti, se vi ne havas jam,

25
00:01:38,100 --> 00:01:46,730
ni parolas pri modeli pilo datumoj stucture uzante tian struct.

26
00:01:46,730 --> 00:01:51,070
>> Do kion ni havas ĉi tie, ĉi tiu estas simila al kio estis prezentita en konferenco,

27
00:01:51,070 --> 00:01:58,120
krom en prelego ni prezentas ĉi kun ints kontraste char * s.

28
00:01:58,120 --> 00:02:06,250
Ĉi tuj estos pilo kiu stokas kio?

29
00:02:06,250 --> 00:02:09,009
Daniel? Kion ni stokante en ĉi pilo?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Ĉenoj? >> Ni stokante kordoj en ĉi pilo, precize.

31
00:02:15,260 --> 00:02:20,950
Vi bezonas havi por krei pilo estas tabelo

32
00:02:20,950 --> 00:02:23,920
de aparta kapablo, kiu en ĉi tiu kazo,

33
00:02:23,920 --> 00:02:28,020
kapablo tuj estos en ĉiuj kaskedoj ĉar ĝi estas konstanto.

34
00:02:28,020 --> 00:02:36,340
Kaj tiam krom la tabelo, ĉiuj ni devas spuri estas la aktuala grandeco de la tabelo.

35
00:02:36,340 --> 00:02:38,980
Unu afero noti tie jen speco de malvarmeta

36
00:02:38,980 --> 00:02:47,060
estas ke ni kreas la plata datumstrukturo sur alia datumstrukturo, la tabelo.

37
00:02:47,060 --> 00:02:50,110
Estas malsamaj manieroj por apliki piloj.

38
00:02:50,110 --> 00:02:54,250
Ni ne faros ĝin sufiĉe ankoraŭ, sed espereble post fari la kunligita-listo problemoj,

39
00:02:54,250 --> 00:03:00,520
vi vidos, kiel vi povas facile apliki en pilo sur supro de ligitaj listo tiel.

40
00:03:00,520 --> 00:03:02,640
Sed nuntempe, ni batos la tabeloj.

41
00:03:02,640 --> 00:03:06,350
Do denove, ni nur bezonas estas tabelo kaj ni nur devas sekvi la grandeco de la tabelo.

42
00:03:06,350 --> 00:03:09,850
[Sam] Pardonu, kial do vi diris la pilo estas sur la kordoj?

43
00:03:09,850 --> 00:03:13,440
Al mi ĝi ŝajnas kiel la kordoj estas ene de la pilo.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Ni kreas, ni prenas niajn tabelo datumstrukturo -

45
00:03:16,790 --> 00:03:22,130
ke estas granda demando. Do la demando estas kial, cxar la homo kiu rigardas tiun linio,

46
00:03:22,130 --> 00:03:24,140
kial ni diras ke la pilo estas ĉe la kordoj,

47
00:03:24,140 --> 00:03:27,990
ĉar tie ĝi aspektas kiel la kordoj estas ene de la pilo?

48
00:03:27,990 --> 00:03:31,050
Kiu estas plene la kazo.

49
00:03:31,050 --> 00:03:34,660
Kion mi aludis al estis ke ni havas aron datumstrukturo.

50
00:03:34,660 --> 00:03:39,290
Ni havas aron da char * s, ĉi tabelo de kordoj,

51
00:03:39,290 --> 00:03:45,300
kaj tuj aldoni al tiu por krei la plata datumstrukturo.

52
00:03:45,300 --> 00:03:48,620
>> Do pilo estas iomete pli kompleksa ol tabelo.

53
00:03:48,620 --> 00:03:51,890
Ni povas uzi tabelo por konstrui pilo.

54
00:03:51,890 --> 00:03:55,810
Do tie estas kie ni diras, ke la pilo estas konstruita sur supro de tabelo.

55
00:03:55,810 --> 00:04:02,510
Same, kiel mi diris antaŭe, ni povas konstrui stako sur supro de ligitaj listo.

56
00:04:02,510 --> 00:04:04,960
Anstataŭ uzi tabelo por teni nian elementoj,

57
00:04:04,960 --> 00:04:10,070
ni povus uzi ligillisto teni nian elementoj kaj konstruu la pilo ĉirkaŭ tiu.

58
00:04:10,070 --> 00:04:12,420
Ni marŝas tra kelkaj ekzemploj, rigardante iom da kodo,

59
00:04:12,420 --> 00:04:14,960
por vidi kio reale okazas tie.

60
00:04:14,960 --> 00:04:23,400
Sur la maldekstra, mi dejxetita kion tiu pilo struct devus aspekti en memoro

61
00:04:23,400 --> 00:04:28,330
se kapablo estis # difinita al esti kvar.

62
00:04:28,330 --> 00:04:33,490
Ni havas nian kvar-era char * tabelo.

63
00:04:33,490 --> 00:04:38,110
Ni havas kordoj [0], kordoj [1], kordoj [2], kordoj [3],

64
00:04:38,110 --> 00:04:43,800
kaj poste tiu lasta spaco por niaj grandeco entjero.

65
00:04:43,800 --> 00:04:46,270
Ĉu ĉi sencon? Okay.

66
00:04:46,270 --> 00:04:48,790
Jen kio okazas, se kion mi faras sur la dekstra,

67
00:04:48,790 --> 00:04:55,790
kiu estos mia kodon, estas simple deklari struct, a plata struct nomita s.

68
00:04:55,790 --> 00:05:01,270
Ĉi tio estas kion ni ricevas. Ĝi demetas tiun spuron en memoro.

69
00:05:01,270 --> 00:05:05,590
La unua demando estas kio estas la enhavo de ĉi tiu pilo struct?

70
00:05:05,590 --> 00:05:09,250
Nun ili estas nenio, sed ili estas ne plene nenion.

71
00:05:09,250 --> 00:05:13,300
Ili estas ĉi tiu speco de rubo. Ni ne havas ideon kio estas en ili.

72
00:05:13,300 --> 00:05:17,000
Kiam ni deklaras pilo j, ni simple ĵeti ke sur supro de memoro.

73
00:05:17,000 --> 00:05:19,840
Estas ia kiel deklari int i kaj ne inicializar ĝin.

74
00:05:19,840 --> 00:05:21,730
Vi ne scias kio estas en tie. Vi povas legi kio estas en tie,

75
00:05:21,730 --> 00:05:27,690
sed eble ne super helpema.

76
00:05:27,690 --> 00:05:32,680
Unu aferon vi volas ĉiam memoras fari estas pravalorizi ajn bezonas por esti inicializado.

77
00:05:32,680 --> 00:05:35,820
En ĉi tiu kazo, ni iras al pravalorizi la grandecon al esti nulo,

78
00:05:35,820 --> 00:05:39,960
ĉar tio tuj turni ekster al esti tre grava por ni.

79
00:05:39,960 --> 00:05:43,450
Ni povus antaŭeniri kaj pravalorizi ĉiuj punteros, ĉiuj char * s,

80
00:05:43,450 --> 00:05:49,670
esti iu komprenebla valoro, probable nula.

81
00:05:49,670 --> 00:05:58,270
Sed ne estas plene necesa ke ni faras tion.

82
00:05:58,270 --> 00:06:04,200
>> Nun, la du ĉefaj operacioj sur piloj estas?

83
00:06:04,200 --> 00:06:07,610
Neniu memoras de prelego kion vi faras kun piloj? Jes?

84
00:06:07,610 --> 00:06:09,700
[Stella] Pushing kaj krevi? >> Ekzakte.

85
00:06:09,700 --> 00:06:13,810
Pelante kaj krevi estas la du ĉefaj operacioj sur piloj.

86
00:06:13,810 --> 00:06:17,060
Kaj kion tio puŝo fari? >> Ĝi metas ion sur la supro

87
00:06:17,060 --> 00:06:19,300
de la pilo, kaj tiam krevi prenas ĝin.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Ekzakte. Do puŝas puŝas iun sur supro de la stako.

89
00:06:23,150 --> 00:06:27,700
Estas kiel la manĝ bastonon metante manĝoĉambro pleto sur la vendotablo.

90
00:06:27,700 --> 00:06:33,630
Kaj krevi prenas manĝoĉambro pleto off de la stako.

91
00:06:33,630 --> 00:06:36,460
Ni marŝas tra kelkaj ekzemploj de tio, kio okazas

92
00:06:36,460 --> 00:06:39,720
kiam ni puŝi aĵoj en la stako.

93
00:06:39,720 --> 00:06:45,110
Se ni devis puŝi la ĉenon 'saluton' sur nia stako,

94
00:06:45,110 --> 00:06:49,760
ĉi tio estas kion la diagramo devus aspekti nun.

95
00:06:49,760 --> 00:06:53,410
Vidu kio okazas?

96
00:06:53,410 --> 00:06:56,530
Ni puŝis en la unua elemento de nia kordoj tabelo

97
00:06:56,530 --> 00:07:01,420
kaj ni upped nia grandeco grafo esti 1.

98
00:07:01,420 --> 00:07:05,340
Do, se ni rigardas la diferencon inter la du diapozitivoj, jen 0, jen antaŭ la puŝo.

99
00:07:05,340 --> 00:07:08,690
Jen post la puŝo.

100
00:07:08,690 --> 00:07:13,460
Antaŭ la puŝo, post la puŝo.

101
00:07:13,460 --> 00:07:16,860
Kaj nun ni havas unu elemento en nia stako.

102
00:07:16,860 --> 00:07:20,970
Ĝi estas la ĉeno "saluton", kaj tio estas ĝi.

103
00:07:20,970 --> 00:07:24,440
Ĉio alia en la tabelo, en nia kordoj tabelo, estas ankoraŭ rubo.

104
00:07:24,440 --> 00:07:27,070
Ni ne inicializado ĝin.

105
00:07:27,070 --> 00:07:29,410
Supozu ke ni puŝi alia ĉeno sur nia stako.

106
00:07:29,410 --> 00:07:32,210
Ni tuj peli "mondo" en ĉi tiu tempo.

107
00:07:32,210 --> 00:07:35,160
Do vi povas vidi "mondo" tie iras sur "saluton",

108
00:07:35,160 --> 00:07:40,040
kaj la grandeco grafo iras al 2.

109
00:07:40,040 --> 00:07:44,520
Nun ni povas puŝi "CS50", kaj kiu iros sur denove.

110
00:07:44,520 --> 00:07:51,110
Se ni reiru, vi povas vidi kiel ni puŝas aĵoj sur la stako.

111
00:07:51,110 --> 00:07:53,320
Kaj nun ni atingos popo.

112
00:07:53,320 --> 00:07:58,910
Kiam ni pusxis io ekstere de la pilo, kio okazis?

113
00:07:58,910 --> 00:08:01,540
Neniu vidas la diferencon? Estas bela subtila.

114
00:08:01,540 --> 00:08:05,810
[Studenta] La grandeco. >> Jes, la grandeco ŝanĝis.

115
00:08:05,810 --> 00:08:09,040
>> Kion alian vi estus atendita ŝanĝi?

116
00:08:09,040 --> 00:08:14,280
[Studenta] La kordoj, ankaŭ. >> Ĝuste. La kordoj ankaŭ.

117
00:08:14,280 --> 00:08:17,110
Rezultas, ke kiam vi faras ĝin tiamaniere,

118
00:08:17,110 --> 00:08:21,960
ĉar ni ne kopiante la elementoj en nian pilo,

119
00:08:21,960 --> 00:08:24,670
ni efektive ne devas fari ion, ni povas simple uzi la grandeco

120
00:08:24,670 --> 00:08:28,630
teni spuro de la nombro de aĵoj en nia tabelo

121
00:08:28,630 --> 00:08:33,780
por ke, kiam ni popo denove, denove ni simple dekremento nia grandeco suben al 1.

122
00:08:33,780 --> 00:08:39,440
Ne necesas efektive iros kaj anstatauxigas nenion.

123
00:08:39,440 --> 00:08:41,710
Speco de funky.

124
00:08:41,710 --> 00:08:46,520
Ĝi rezultas ke ni tipe nur lasi aferojn sole ĉar estas malpli da laboro por ni fari.

125
00:08:46,520 --> 00:08:50,060
Se ni ne devas reiri kaj anstatauxigas ion, tiam kial fari ĝin?

126
00:08:50,060 --> 00:08:54,150
Do kiam ni popo dufoje for de la pilo, cxiuj faras estas dekremento la grandeco kelkajn fojojn.

127
00:08:54,150 --> 00:08:59,120
Kaj denove, ĉi tiu estas nur ĉar ni ne kopii aferojn en nian pilo.

128
00:08:59,120 --> 00:09:01,320
Jes? Iru antaŭen.

129
00:09:01,320 --> 00:09:04,460
[Studento, nekomprenebla] >> Kaj poste kio okazas kiam vi puŝi ion denove?

130
00:09:04,460 --> 00:09:08,570
Kiam vi puŝi ion pli, kie ĝi iras?

131
00:09:08,570 --> 00:09:12,390
Kie ĝi iras, Bazilo? >> Into kordoj [1]? >> Ĝuste.

132
00:09:12,390 --> 00:09:14,530
Kial ne iru en kordoj [3]?

133
00:09:14,530 --> 00:09:19,410
[Bazilo] Ĉar ĝi forgesis ke estas io en kordoj [1] kaj [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Ekzakte. Nia pilo, esence, "forgesis" kiu tenis al io

135
00:09:24,040 --> 00:09:29,480
en kordoj [1] aŭ kordoj [2], do, kiam ni peli "woot",

136
00:09:29,480 --> 00:09:36,670
ĝi simple metas ke en la elemento en kordoj [1].

137
00:09:36,670 --> 00:09:41,590
Ĉu estas demandoj pri kiel tio funkcias, al baza nivelo?

138
00:09:41,590 --> 00:09:45,160
[Sam] Do tiu estas ne dinamika en ajna maniero, en terminoj de kvanto

139
00:09:45,160 --> 00:09:47,620
aŭ en terminoj de la grandeco de la pilo?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Ekzakte. Tio estas - la punkto estis, ke tiu ne estis dinamike growning pilo.

141
00:09:56,750 --> 00:10:02,850
Tio ĉi estas stako kiu povas teni, maksimume, kvar char * s, maksimume kvar aĵoj.

142
00:10:02,850 --> 00:10:07,580
Se ni devis provi kaj puŝi kvina afero, kion vi opinias devus okazi?

143
00:10:07,580 --> 00:10:11,870
[Studentoj, nekomprenebla]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Ekzakte. Estas nombro de aĵoj kiuj povus okazi.

145
00:10:14,600 --> 00:10:19,330
Ĝi povus seg kulpo, depende de kion ni estis -

146
00:10:19,330 --> 00:10:22,530
kiel ekzakte ni realiganta la dorso-fino.

147
00:10:22,530 --> 00:10:31,740
Ĝi povus anstataŭigi. Ĝi povus esti ke buffer overflow ke ni raportis en klaso.

148
00:10:31,740 --> 00:10:35,240
Kio estus la plej evidenta afero, ke eblus anstataŭigi

149
00:10:35,240 --> 00:10:42,370
se ni provis peli ekstra afero en nia stako?

150
00:10:42,370 --> 00:10:44,550
Do vi menciis buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Kio povus esti la afero kiu get skribita super aŭ stomped sur

152
00:10:47,870 --> 00:10:52,320
se ni superfluis hazarde por provi puŝi ekstra afero?

153
00:10:52,320 --> 00:10:54,730
[Daniel, nekomprenebla] >> Eblaj.

154
00:10:54,730 --> 00:10:58,440
Sed komence, kio povus okazi? Kio se ni provis peli kvaran aferon?

155
00:10:58,440 --> 00:11:06,220
Eble anstataŭigi la grandeco, almenaŭ kun ĉi tiu memoro diagramo kiu ni havas.

156
00:11:06,220 --> 00:11:10,880
>> En la problemon aro specifo, kiu estas kion ni tuj estos apliki hodiaŭ,

157
00:11:10,880 --> 00:11:16,030
kion ni volas fari estas simple reveni falsaj.

158
00:11:16,030 --> 00:11:20,030
Nia puŝo metodo tuj revenos bulea valoro,

159
00:11:20,030 --> 00:11:22,920
kaj ke bulea valoro estos vera se la antaŭenpuŝo sukcesos

160
00:11:22,920 --> 00:11:29,730
kaj malvera se ni ne povas puŝi ion pli ĉar la pilo estas plena.

161
00:11:29,730 --> 00:11:33,620
Ni marŝas tra iom de tiu kodo nun.

162
00:11:33,620 --> 00:11:36,400
Jen nia puŝo funkcio.

163
00:11:36,400 --> 00:11:40,380
Nia puŝo funkcio por pilo tuj prenos en la ĉeno por meti sur la stako.

164
00:11:40,380 --> 00:11:45,820
Oni tuj revenos vera se la kordo sukcese puŝis

165
00:11:45,820 --> 00:11:51,820
sur la pilo kaj falsaj alie.

166
00:11:51,820 --> 00:11:59,740
Ajna sugestojn sur kio povus esti bona unua afero por fari tie?

167
00:11:59,740 --> 00:12:20,630
[Sam] Se grandeco egalas kapablon tiam revenu falsa?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Bela laboro.

169
00:12:23,320 --> 00:12:26,310
Se la grandeco estas la kapablo, ni tuj revenos falsaj.

170
00:12:26,310 --> 00:12:29,270
Ni ne povas meti ion pli en nia stako.

171
00:12:29,270 --> 00:12:36,900
Alie, ni volas meti iun sur la supro de la stako.

172
00:12:36,900 --> 00:12:41,670
Kio estas "la supro de la pilo," komence?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Grandeco 0? >> Grando 0.

174
00:12:43,650 --> 00:12:49,990
Kio estas la pinto de la pilo post ekzistas unu afero en la pilo? Missy, ĉu vi scias?

175
00:12:49,990 --> 00:12:52,720
[Missy] Unu. >> Grando estas unu, precize. Vi observos aldonante al la grandeco,

176
00:12:52,720 --> 00:13:01,690
kaj ĉiufoje vi metante en la nova elemento en la indekso grandeco en la tabelo.

177
00:13:01,690 --> 00:13:05,470
Ni povas fari ĝin kun tiu speco de unu-Liner, se tiu havas sencon.

178
00:13:05,470 --> 00:13:11,910
Do ni havas nian kordoj tabelo, ni tuj aliri gxin cxe la grandeco indico,

179
00:13:11,910 --> 00:13:14,780
kaj ni ĵus tuj stoki niajn char * en tie.

180
00:13:14,780 --> 00:13:19,340
Rimarku kiel ne estas ŝnuro kopiado okazas en ĉi tie,

181
00:13:19,340 --> 00:13:29,680
neniu dinamika atribuo de memoro?

182
00:13:29,680 --> 00:13:34,440
Kaj tiam Missy alportis tion, kion ni nun devas fari,

183
00:13:34,440 --> 00:13:40,570
ĉar ni stokis la ĉenon en la taŭgan lokon en la tabelo,

184
00:13:40,570 --> 00:13:49,230
kaj sxi diris ke ni devis pliigo de la grandeco de unu por ke ni estas pretaj por la sekvanta puŝo.

185
00:13:49,230 --> 00:13:53,950
Do ni povas fari tion kun s.size + +.

186
00:13:53,950 --> 00:13:59,330
Je ĉi tiu punkto, ni pelis en niajn tabelo. Kio estas la lasta afero, kiun ni devas fari?

187
00:13:59,330 --> 00:14:10,110
[Studenta] Reveno vera. >> Return vera.

188
00:14:10,110 --> 00:14:14,690
Do ĝi estas bela simpla, bela simpla kodo. Ne tro multe.

189
00:14:14,690 --> 00:14:17,070
Kiam vi envolvis via kapo ĉirkaŭ kiel la pilo funkcias,

190
00:14:17,070 --> 00:14:21,910
ĉi tiu estas sufiĉe simpla por apliki.

191
00:14:21,910 --> 00:14:26,390
>> Nun, la sekvanta parto de ĉi tiu estas krevi ĉenon off de la stako.

192
00:14:26,390 --> 00:14:29,410
Mi tuj donos al vi infanoj tempon por labori pri tiu iomete.

193
00:14:29,410 --> 00:14:34,320
Estas preskaŭ esence la dorsflanko de kion ni faris ĉi tie en sakon.

194
00:14:34,320 --> 00:14:38,510
Kion mi faris fakte - oops.

195
00:14:38,510 --> 00:14:48,160
Mi booted aperigis aparaton super ĉi tie, kaj en la aparaton,

196
00:14:48,160 --> 00:14:53,600
Mi tiris supren la problemo starigis 5 specifo.

197
00:14:53,600 --> 00:15:02,560
Se ni zomi tie, ni povas vidi min ĉe cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Ĉu vi infanoj elŝutebla ĉi kodo ke tio situas tie, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Bone. Se vi ne faris tion, faru ke ĝuste nun, vere rapide.

200
00:15:15,030 --> 00:15:22,130
Mi faros ĝin en mia fina fenestro.

201
00:15:22,130 --> 00:15:25,090
Mi vere faris ĝin ĉi tie. Yeah.

202
00:15:25,090 --> 00:15:34,730
Jes, Sam? >> Mi havas demandon pri kial vi diras s.string-ejon krampoj de amplekso = str?

203
00:15:34,730 --> 00:15:42,910
Kio estas str? Estas ke difinita ie antaŭe, aŭ - ho, en la char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Jes, ĝuste. Tio estis la argumento. >> Ho, bone. Pardonu.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Ni preciziganta la kordo peli in

206
00:15:49,470 --> 00:15:55,220
La alia demando kiu povus antaŭvidi ke ni ne vere parolas pri ĉi tie estis

207
00:15:55,220 --> 00:15:58,810
ni prenis koncedis, ke ni havis tiun variablon nomita s

208
00:15:58,810 --> 00:16:02,710
kiu estis en atingo kaj alirebla al ni.

209
00:16:02,710 --> 00:16:06,960
Ni prenis por koncedis ke s estis ĉi pilo struct.

210
00:16:06,960 --> 00:16:08,930
Do rigardante malantaŭen en ĉi tiu puŝo kodo,

211
00:16:08,930 --> 00:16:13,450
vi povas vidi, ke ni faras aĵojn kun ĉi ĉeno kiu got pasis en

212
00:16:13,450 --> 00:16:19,210
sed tiam subite, ni aliru s.size, kiel, kien s venis?

213
00:16:19,210 --> 00:16:23,020
En la kodo kiun ni iras por rigardi en la sekcio arkivo

214
00:16:23,020 --> 00:16:27,100
kaj tiam la aĵoj kiujn vi povas fari en via problemo aroj,

215
00:16:27,100 --> 00:16:32,440
ni faris nian pilo struct tutmonda variablo

216
00:16:32,440 --> 00:16:36,380
tiel ke ni povas havi aliron al ĝi en ĉiuj niaj malsamaj funkcioj

217
00:16:36,380 --> 00:16:40,630
sen devi permane pasi ĝin ĉirkaŭ kaj fordoni ilin por referenco,

218
00:16:40,630 --> 00:16:44,870
faru cxion tian materialon al ĝi.

219
00:16:44,870 --> 00:16:52,280
Ni nur cheating iomete, se vi volas, fari aĵoj pli bela.

220
00:16:52,280 --> 00:16:57,430
Kaj tio estas io ni faras ĉi tie, ĉar tio estas nur por amuzo, pli facilas.

221
00:16:57,430 --> 00:17:02,800
Ofte, vi vidos homojn fari tion se ili havas unu grandan datumstrukturo

222
00:17:02,800 --> 00:17:07,750
ke tio esti operaciita ene de sia programo.

223
00:17:07,750 --> 00:17:09,560
>> Ni iru reen super la aparaton.

224
00:17:09,560 --> 00:17:15,240
Ĉu ĉiuj sukcese akiri la section6.zip?

225
00:17:15,240 --> 00:17:20,440
Ĉiuj maldensigi ĝin uzante maldensigi section6.zip?

226
00:17:20,440 --> 00:17:27,200
Se vi iras en la sekcio 6 directory -

227
00:17:27,200 --> 00:17:29,220
Aah, la tuta loko -

228
00:17:29,220 --> 00:17:32,840
kaj vi listigi kio estas en tie, vi vidas, ke oni devas tri malsamaj. c dosierojn.

229
00:17:32,840 --> 00:17:38,350
Vi havas voston, oni SLL, kiu estas unuope-ligillisto, kaj pilo.

230
00:17:38,350 --> 00:17:44,600
Se vi malfermas stack.c,

231
00:17:44,600 --> 00:17:47,330
vi povas vidi, ke ni havas ĉi struct difinita por ni,

232
00:17:47,330 --> 00:17:51,330
la ĝusta struct ke ni nur parolis pri la diapozitivoj.

233
00:17:51,330 --> 00:17:56,340
Ni havas nian tutmondan variablo por la pilo,

234
00:17:56,340 --> 00:18:00,110
ni havas nian puŝo funkcio,

235
00:18:00,110 --> 00:18:04,230
kaj tiam ni havas niajn popo funkcio.

236
00:18:04,230 --> 00:18:08,320
Mi metis la kodon por peli reen sur la glito tie,

237
00:18:08,320 --> 00:18:10,660
sed kion mi ŝatus you guys fari estas, al la plej bonaj de via kapableco,

238
00:18:10,660 --> 00:18:13,790
iru kaj efektivigu la popo funkcio.

239
00:18:13,790 --> 00:18:18,480
Kiam vi implementado ĝin, vi povas kompili tiun kun fari pilo,

240
00:18:18,480 --> 00:18:22,540
kaj poste ruli la rezulta pilo ruleblan,

241
00:18:22,540 --> 00:18:28,390
kaj kiu kuros ĉio ĉi testo kodo cxi tie ke estas en ĉefaj.

242
00:18:28,390 --> 00:18:31,060
Kaj ĉefa prizorgas fakte farante la puŝo kaj pop alvokoj

243
00:18:31,060 --> 00:18:33,220
kaj certigi ke ĉiu iras tra ĉiuj pravas.

244
00:18:33,220 --> 00:18:36,820
Ĝi ankaŭ inicializa la pilo grandeco ĉi tie

245
00:18:36,820 --> 00:18:39,780
tial vi ne devas zorgi pri inicializar tio.

246
00:18:39,780 --> 00:18:42,310
Vi povas supozi, ke ĝi estas estis gxuste inicializado

247
00:18:42,310 --> 00:18:48,000
por la tempo kiun vi konsenti li en la populara funkcio.

248
00:18:48,000 --> 00:18:53,530
Ĉu tio havas sencon?

249
00:18:53,530 --> 00:19:00,100
Do jen ni iru. Jen la antaŭenpuŝo kodo.

250
00:19:00,100 --> 00:19:13,210
Mi donos al vi infanoj 5 aŭ 10 minutoj.

251
00:19:13,210 --> 00:19:15,690
Kaj se vi havas demandojn en la provizora dum vi kodigo,

252
00:19:15,690 --> 00:19:17,710
bonvolu peti ilin laŭte.

253
00:19:17,710 --> 00:19:23,080
Do, se vi ricevas al batas punkto, nur demandi.

254
00:19:23,080 --> 00:19:26,030
Lasu min scii, lasu ĉiuj aliaj scias.

255
00:19:26,030 --> 00:19:28,160
Labori kun via najbaro ankaŭ.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Ni nur apliki popo nun? >> Nur popo.

257
00:19:30,360 --> 00:19:34,200
Kvankam vi povas kopii la efektivigo de puŝo se vi ŝatus

258
00:19:34,200 --> 00:19:37,780
por ke la provado funkcios.

259
00:19:37,780 --> 00:19:41,940
Ĉar ĝi estas malfacile kontroli tion atingi en -

260
00:19:41,940 --> 00:19:49,030
aŭ, estas malfacile kontroli krevi aĵoj el stako se estas nenio en la pilo por komenci.

261
00:19:49,030 --> 00:19:55,250
>> Kio estas popo supozis esti reveni? La elemento de la supro de la stako.

262
00:19:55,250 --> 00:20:01,260
Oni supozis akiri la elemento ekstere de la pinto de la stako

263
00:20:01,260 --> 00:20:05,780
kaj tiam dekremento de la grandeco de la pilo,

264
00:20:05,780 --> 00:20:07,810
kaj nun vi perdis la elemento sur la supro.

265
00:20:07,810 --> 00:20:11,420
Kaj tiam vi revenos al la elemento sur la supro.

266
00:20:11,420 --> 00:20:20,080
[Studento, nekomprenebla]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Do kio okazas se vi faros tion? [Studento, nekomprenebla]

268
00:20:28,810 --> 00:20:34,000
Kio finas okazas estas ke vi probable alirante ĉu

269
00:20:34,000 --> 00:20:37,350
ero kiu ne estis inicializado tamen, do, via kalkulo

270
00:20:37,350 --> 00:20:39,990
de kie la lasta elemento estas estas malŝaltita.

271
00:20:39,990 --> 00:20:46,260
Do jen, se vi rimarkos, en puŝo, ni aliru kordoj ĉe la s.size elemento

272
00:20:46,260 --> 00:20:48,560
ĉar ĝi estas nova indekso.

273
00:20:48,560 --> 00:20:51,460
Ĝi estas la nova supera parto de la pilo.

274
00:20:51,460 --> 00:21:01,100
Dum en la popo, s.size tuj estos la venonta spaco,

275
00:21:01,100 --> 00:21:05,210
la spaco kiu estas sur la supro de ĉiuj elementoj en via pilo.

276
00:21:05,210 --> 00:21:10,050
Do la supre-pli elemento estas ne s.size,

277
00:21:10,050 --> 00:21:14,930
sed prefere, estas sub tio.

278
00:21:14,930 --> 00:21:19,640
>> La alia afero por fari, kiam vi - en popmuziko,

279
00:21:19,640 --> 00:21:22,030
estas vi devas dekremento la grandeco.

280
00:21:22,030 --> 00:21:28,750
Se vi memoras reen al nia eta figuro dekstre tie,

281
00:21:28,750 --> 00:21:30,980
vere, la sola afero ke ni vidis okazas kiam ni nomas popo

282
00:21:30,980 --> 00:21:36,150
estis, ke ĉi tiu grandeco faligis, unue al 2, tiam al 1.

283
00:21:36,150 --> 00:21:42,620
Tiam, kiam ni pelis nova elemento en, estus iri en konvenaj makulo.

284
00:21:42,620 --> 00:21:49,610
[Bazilo] Se la s.size estas 2, tiam ne estis al elemento 2,

285
00:21:49,610 --> 00:21:54,400
kaj tiam vi volas volas popo tiu elemento ekstere?

286
00:21:54,400 --> 00:21:59,510
Do, se ni iris al - >> Do ni rigardu tiun alian fojon.

287
00:21:59,510 --> 00:22:07,730
Se ĉi tiu estas nia stako ĉe ĉi tiu punkto

288
00:22:07,730 --> 00:22:12,130
kaj ni nomas popo,

289
00:22:12,130 --> 00:22:16,150
je kiu indico estas la supre-pli elemento?

290
00:22:16,150 --> 00:22:19,300
[Bazilo] Al 2, sed tuj popo 3. >> Ĝuste.

291
00:22:19,300 --> 00:22:24,220
Do tie estas kie nia grandeco estas 3, sed ni volas popo la elemento en indekso 2.

292
00:22:24,220 --> 00:22:29,900
Ĝi estas tiu tipa speco de off por kiu vi havas kun la nulo-indeksado de tabeloj.

293
00:22:29,900 --> 00:22:36,430
Do vi volas popo la tria elemento, sed la tria elemento estas ne indekso 3.

294
00:22:36,430 --> 00:22:39,430
Kaj la kialo ni ne devas fari tion minus 1 kiam ni puŝas

295
00:22:39,430 --> 00:22:44,120
estas ĉar ĝuste nun, vi rimarkos ke la supre-pli elemento,

296
00:22:44,120 --> 00:22:47,600
se ni devis puŝi ion alian sur la stako ĉe ĉi tiu punkto,

297
00:22:47,600 --> 00:22:50,360
ni volus peli ĝin en indekso 3.

298
00:22:50,360 --> 00:23:03,550
Kaj ĝuste tial okazas, ke la grandeco kaj la indicoj laŭliniigi kiam vi premas.

299
00:23:03,550 --> 00:23:06,960
>> Kiu havas laborante pilo efektivigo?

300
00:23:06,960 --> 00:23:09,690
Vi havas funkciantan pilo unu. Ĉu vi popo laboras ankoraŭ?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Jes. Mi kredas tiel.

302
00:23:11,890 --> 00:23:14,610
>> Programo kuras kaj ne seg faulting, ĝi estas presi el?

303
00:23:14,610 --> 00:23:17,520
Ĉu ĝi presi "sukceso" kiam vi kuros ĝin?

304
00:23:17,520 --> 00:23:22,630
Yeah. Faru pilo, ruli ĝin, se ĝi presas el "sukceso" kaj ne iras eksplodo,

305
00:23:22,630 --> 00:23:26,000
tiam ĉiuj estas bonaj.

306
00:23:26,000 --> 00:23:34,070
Bone. Ni transiru al la aparaton vere rapide,

307
00:23:34,070 --> 00:23:46,100
kaj ni trairu ĉi.

308
00:23:46,100 --> 00:23:51,110
Se ni rigardas kio okazas ĉi tie kun popo,

309
00:23:51,110 --> 00:23:55,220
Daniel, kio estis la unua afero, kiun vi faris?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Se s.size estas pli granda ol 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. Kaj kial vi faris tion?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Por certigi ke io interne de la stako.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Ĝuste. Vi volas provi certigi ke s.size estas pli granda ol 0;

314
00:24:10,950 --> 00:24:13,280
alie, kion vi volas esti okazos?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Reveno nula? >> Reiri nula, precize.

316
00:24:16,630 --> 00:24:20,740
Do se s.size estas pli granda ol 0. Do kion ni tuj fari?

317
00:24:20,740 --> 00:24:25,890
Kion ni faru se la pilo ne estas malplena?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vi dekremento la grandeco? >> Vi dekremento la grandecon, okay.

319
00:24:31,210 --> 00:24:34,440
Do kiel vi faris tion? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Granda. Kaj poste kion vi faris?

321
00:24:37,030 --> 00:24:44,140
[Stella] Kaj poste mi diris reveno s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Granda.

323
00:24:48,560 --> 00:24:51,940
Alie vi revenos nula. Jes, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Kial ĝi ne bezonas esti s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Jes. >> Got ĝin.

326
00:24:58,430 --> 00:25:00,980
[Sam] Mi pensis ke vi prenas 1 out,

327
00:25:00,980 --> 00:25:04,290
tiam vi tuj estos reveni ne kiu ili petis.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Kaj jen ĝuste kion ni parolis pri kun ĉi tiu tuta afero de 0 indeksoj.

329
00:25:09,400 --> 00:25:11,380
Do, se ni zoom reen super tie.

330
00:25:11,380 --> 00:25:15,650
Se ni rigardas this guy ĉi tie, vi povas vidi, ke kiam ni popo,

331
00:25:15,650 --> 00:25:19,340
ni krevi la elemento en indekso 2.

332
00:25:19,340 --> 00:25:25,200
>> Do ni malpliigi niajn grandeco unua, tiam nia grandeco kongruas nia indekso.

333
00:25:25,200 --> 00:25:39,650
Se ni ne dekremento la grandeco unua, tiam ni devas fari grandeco -1 kaj tiam dekremento.

334
00:25:39,650 --> 00:25:45,270
Granda. Ĉiuj bonaj?

335
00:25:45,270 --> 00:25:47,530
Demandojn pri tiu?

336
00:25:47,530 --> 00:25:54,050
Estas nombro de malsamaj manieroj por skribi ĉi tiel.

337
00:25:54,050 --> 00:26:03,290
Fakte, ni povas fari iun eĉ - ni povas fari unu-Liner.

338
00:26:03,290 --> 00:26:05,770
Ni povas fari unu-linio reveno.

339
00:26:05,770 --> 00:26:12,980
Do ni povas reale dekremento antaŭ ol ni reveni por fari tion.

340
00:26:12,980 --> 00:26:18,320
Do meti la - antaŭ la s.size.

341
00:26:18,320 --> 00:26:22,060
Tio faras la linio vere densa.

342
00:26:22,060 --> 00:26:30,940
Kie la diferenco inter la - s. Grandeco kaj s.size--

343
00:26:30,940 --> 00:26:40,130
estas ke ĉi postfix - ili nomas ĝin postfix ĉar la - venas post la s.size--

344
00:26:40,130 --> 00:26:47,430
signifas ke s.size estas taksita la celo trovi la indekso

345
00:26:47,430 --> 00:26:50,410
kiel estas nuntempe kiam ĉi tiu linio estas plenumata,

346
00:26:50,410 --> 00:26:54,290
kaj tiam ĉi - okazas post la linio gets ekzekutita.

347
00:26:54,290 --> 00:27:00,340
Post la elemento en indekso s.size aliras.

348
00:27:00,340 --> 00:27:07,260
Kaj tio ne estas kion ni volas, ĉar ni deziras la dekremento okazi unue.

349
00:27:07,260 --> 00:27:10,990
Othewise, ni tuj estos alirante la tabelo, efektive, el baroj.

350
00:27:10,990 --> 00:27:16,850
Ni tuj estos alirante la elemento super kiu ni efektive volas aliri.

351
00:27:16,850 --> 00:27:23,840
Yeah, Sam? >> Ĉu estas pli rapida aŭ uzu malpli RAM fari en unu linio aŭ ne?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Honeste, vere dependas.

353
00:27:29,620 --> 00:27:34,220
[Sam, nekomprenebla] >> Jes, tio dependas. Vi povas fari tradukilon lertaĵoj

354
00:27:34,220 --> 00:27:41,580
por ricevi la tradukilo por rekoni ke, kutime, mi imagas.

355
00:27:41,580 --> 00:27:44,840
>> Do ni menciis iomete pri tiu tradukilo optimumigo stuff

356
00:27:44,840 --> 00:27:47,400
ke vi povas fari en kompili,

357
00:27:47,400 --> 00:27:50,580
kaj tio estas la speco de afero kiun tradukilo povus kapabli eltrovi,

358
00:27:50,580 --> 00:27:54,710
kiel ho hey, eble mi povas fari ĉi ĉiujn en unu operacio,

359
00:27:54,710 --> 00:27:59,420
kiel kontraŭ ŝarĝante la grandeco variablo en el RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing ĝin, stokante ĝin eksteren, kaj poste ŝarĝas ĝin en alia fojo

361
00:28:03,770 --> 00:28:08,000
por procesi la resto de ĉi tiu operacio.

362
00:28:08,000 --> 00:28:10,710
Sed tipe, ne, tio ne estas la speco de afero

363
00:28:10,710 --> 00:28:20,770
ke tuj faros vian programon signife pli rapide.

364
00:28:20,770 --> 00:28:26,000
Plu demandojn sur piloj?

365
00:28:26,000 --> 00:28:31,360
>> Do puŝas kaj krevi. Se vi infanoj volas provi la hacker eldono,

366
00:28:31,360 --> 00:28:33,660
kion ni faris en la hacker eldono estas efektive foriris

367
00:28:33,660 --> 00:28:37,670
kaj ili faris tiun pilo kreski dinamike.

368
00:28:37,670 --> 00:28:43,190
La defio estas unuavice ĝis tie en la antaŭenpuŝo funkcio,

369
00:28:43,190 --> 00:28:48,820
elŝeligi kiel fari, ke tabelo kreski

370
00:28:48,820 --> 00:28:52,450
kiel vi observu pelante pli kaj pli elementoj sur la stako.

371
00:28:52,450 --> 00:28:56,000
Ĝi fakte ne estas tro da aldonaj kodo.

372
00:28:56,000 --> 00:29:00,080
Nur alvokon al - vi devas memori por ricevi la alvokoj al malloc tien konvene,

373
00:29:00,080 --> 00:29:03,310
kaj poste eltrovi, kiam vi iras por voki realloc.

374
00:29:03,310 --> 00:29:06,090
Tio estas amuza defio se vi estas interesata.

375
00:29:06,090 --> 00:29:11,550
>> Sed provizore, ni movi plu, kaj ni parolos pri vostoj.

376
00:29:11,550 --> 00:29:15,680
Rulumu tra tie.

377
00:29:15,680 --> 00:29:19,340
La vosto estas proksima frato de la pilo.

378
00:29:19,340 --> 00:29:25,380
Do, en la pilo, aĵoj kiuj estis metitaj en la lasta

379
00:29:25,380 --> 00:29:28,810
estis la unuaj aferoj tiam esti konsultita.

380
00:29:28,810 --> 00:29:33,600
Ni havas ĉi lasta en, unua el, aŭ LIFO, ordigi.

381
00:29:33,600 --> 00:29:38,390
Dum en la vosto, kiel vi atendus de kiam vi staris en linio,

382
00:29:38,390 --> 00:29:41,980
la unua persono por ricevi en linio, la unua afero por eniri en la vosto,

383
00:29:41,980 --> 00:29:47,630
estas la unua aĵo kiun gets rekuperita de la vico.

384
00:29:47,630 --> 00:29:51,490
Vostoj estas ankaŭ ofte uzata kiam ni pritraktas grafikaĵoj,

385
00:29:51,490 --> 00:29:55,560
kiel ni parolis pri mallonge kun piloj,

386
00:29:55,560 --> 00:30:00,260
kaj vostoj estas ankaŭ utila por multaj aliaj aĵoj.

387
00:30:00,260 --> 00:30:06,180
Unu afero kiu venas supren ofte provas subteni, ekzemple,

388
00:30:06,180 --> 00:30:12,310
a ordo listo de eroj.

389
00:30:12,310 --> 00:30:17,650
Kaj vi povas fari tion kun tabelo. Vi povas subteni ordo listo de aferoj en tabelo,

390
00:30:17,650 --> 00:30:20,650
sed kie kiu alvenas malfacila estas tiam vi ĉiam devas trovi

391
00:30:20,650 --> 00:30:26,160
la taŭga loko por enmeti lin proksima.

392
00:30:26,160 --> 00:30:28,250
Do se vi havas tabelo de nombroj, 1 ĝis 10,

393
00:30:28,250 --> 00:30:31,630
kaj tiam vi volas pligrandigi ke ĉiuj nombroj 1 ĝis 100,

394
00:30:31,630 --> 00:30:33,670
kaj vi estas duumaj tiuj nombroj en hazarda ordo kaj provas teni ĉio

395
00:30:33,670 --> 00:30:40,650
ordo kiel vi iros tra vi finos devi fari multajn movo.

396
00:30:40,650 --> 00:30:43,910
Kun certaj tipoj de vostoj kaj iuj tipoj de suba datumstrukturoj,

397
00:30:43,910 --> 00:30:46,670
vi povas fakte teni ĝin sufiĉe simpla.

398
00:30:46,670 --> 00:30:50,640
Vi ne devas aldoni ion, kaj poste reshuffle la tuta afero ĉiufoje.

399
00:30:50,640 --> 00:30:56,770
Nek vi devas fari multajn movo de la internaj elementoj ĉirkaŭe.

400
00:30:56,770 --> 00:31:02,990
Kiam ni rigardas queue, vi vidos ke - same en queue.c en la sekcio kodo -

401
00:31:02,990 --> 00:31:10,950
la struct ke ni donis al vi estas vere simila al la struct ke ni donis al vi por pilo.

402
00:31:10,950 --> 00:31:13,770
>> Estas unu escepto al ĉi tio, kaj ke unu escepto

403
00:31:13,770 --> 00:31:21,700
estas ke ni havas cxi tiun plian entjero nomata la kapo,

404
00:31:21,700 --> 00:31:28,120
kaj la kapo tie estas por konservanta trako de la kapo de la vosto,

405
00:31:28,120 --> 00:31:32,160
aŭ la unua elemento en la vico.

406
00:31:32,160 --> 00:31:37,470
Kun pilo, ni povis konservi trako de la elemento, ke ni estis por elsxuti,

407
00:31:37,470 --> 00:31:40,800
aŭ la supro de la pilo, uzante nur la grandeco,

408
00:31:40,800 --> 00:31:44,220
dum kun vosto, ni devi trakti ekstremaj kontraŭaj.

409
00:31:44,220 --> 00:31:49,000
Ni provas Tack aĵoj sur fine, sed tiam revenu tion for de fronto.

410
00:31:49,000 --> 00:31:54,640
Do efektive, kun la kapo, ni havas la indekso de la komenco de la vosto,

411
00:31:54,640 --> 00:31:58,920
kaj la grandeco donas al ni la indekso de la fino de la vosto

412
00:31:58,920 --> 00:32:03,730
tiel ke ni povas elsxuti tion de la kapo kaj aldoni aferojn al la vosto.

413
00:32:03,730 --> 00:32:06,890
Dum kun la pilo, ni estis nur iam pritraktanta la supro de la stako.

414
00:32:06,890 --> 00:32:08,900
Ni neniam devis aliri al la fundo de la stako.

415
00:32:08,900 --> 00:32:12,220
Ni nur aldonis tion al la supro kaj prenis tion for de la supro

416
00:32:12,220 --> 00:32:17,470
do ni ne bezonas tiun ekstran kampo ene de nia struct.

417
00:32:17,470 --> 00:32:20,590
Ĉu tio ĝenerale havas sencon?

418
00:32:20,590 --> 00:32:27,670
Bone. Jes, Charlotte? [Charlotte, nekomprenebla]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Tio estas granda demando, kaj kiu estis unu, kiu aperis en prelego.

420
00:32:32,660 --> 00:32:36,290
Eble promenante tra kelkaj ekzemploj estos ilustri kial

421
00:32:36,290 --> 00:32:41,400
ni ne volas uzi kordoj [0] kiel la estro de la vico.

422
00:32:41,400 --> 00:32:46,770
>> Do imagu, ke ni havas niajn queue, ni tuj nomas ĝin vosto.

423
00:32:46,770 --> 00:32:49,210
Komence, kiam ni ĵus instantiated ĝin,

424
00:32:49,210 --> 00:32:53,330
kiam ni nur deklaris ĝin, ni ne inicializado nenion.

425
00:32:53,330 --> 00:32:56,790
Estas ĉio rubo. Do kompreneble ni volas certigi, ke ni pravalorizi

426
00:32:56,790 --> 00:33:00,950
ambaŭ la grandeco kaj la kapo kampoj al esti 0, iu racia.

427
00:33:00,950 --> 00:33:05,770
Ni povus ankaŭ antaŭeniri kaj nula el la eroj en nia vico.

428
00:33:05,770 --> 00:33:09,930
Kaj fari tiun diagramon konvena, rimarki ke nun nia vico nur teni tri elementoj;

429
00:33:09,930 --> 00:33:13,150
dum nia stako povis teni kvar, nia vosto povas nur teni tri.

430
00:33:13,150 --> 00:33:18,680
Kaj tio estas nur por fari la diagramo indas.

431
00:33:18,680 --> 00:33:26,150
La unua afero kiu okazas ĉi tie estas ni enqueue la ĉeno "hi".

432
00:33:26,150 --> 00:33:30,380
Kaj ĝuste kiel ni faris kun la pilo, nenio terure malsamajn tie,

433
00:33:30,380 --> 00:33:39,230
ni ĵeti la ŝnuron en ĉe kordoj [0] kaj pliigo nia grandeco per 1.

434
00:33:39,230 --> 00:33:42,720
Ni enqueue "bye", ĝi prenas surmetis.

435
00:33:42,720 --> 00:33:45,870
Do ĉi aspektas kiel stako plejparte.

436
00:33:45,870 --> 00:33:53,230
Ni komencas ekstere tie, nova elemento, nova elemento, grandeco subtenas suprenirantaj.

437
00:33:53,230 --> 00:33:56,330
Kio okazas ĉe ĉi tiu punkto, kiam ni volas dequeue ion?

438
00:33:56,330 --> 00:34:01,280
Kiam ni volas dequeue, kiu estas la elemento kiu ni volas dequeue?

439
00:34:01,280 --> 00:34:04,110
[Bazilo] Ĉenoj [0]. >> Nulo. Ĝuste pravas, Bazilo.

440
00:34:04,110 --> 00:34:10,960
Ni volas forigi la unua kordo, ĉi tiu, "hi".

441
00:34:10,960 --> 00:34:13,170
Do kio estas la alia afero kiu ŝanĝis?

442
00:34:13,170 --> 00:34:17,010
Rimarku, kiam ni pusxis io ekstere de la pilo, ni ĵus ŝanĝis la grandecon,

443
00:34:17,010 --> 00:34:22,080
sed ĉi tie, ni havas kelkajn aĵojn kiuj ŝanĝon.

444
00:34:22,080 --> 00:34:27,440
Ne nur faras la grandecon ŝanĝo, sed la kapon ŝanĝojn.

445
00:34:27,440 --> 00:34:31,020
Tiu tuj reen al Carlota punkto antaŭa:

446
00:34:31,020 --> 00:34:38,699
kial ni havas ĉi kapon tiel?

447
00:34:38,699 --> 00:34:42,110
Ĉu havas sencon nun, Charlotte? >> Speco de.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Speco de? Do kio okazis kiam ni dequeued?

449
00:34:47,500 --> 00:34:54,340
Kion la kapo fari tion nun estas interesaj?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Ho, ĉar ĝi ŝanĝis - okay. Mi vidas.

451
00:34:56,449 --> 00:35:02,090
Ĉar la kapo - kie la kapo indikante ŝanĝoj en terminoj de la loko.

452
00:35:02,090 --> 00:35:07,200
Ĝi ne plu ĉiam la nulo indekso unu. >> Jes, ĝuste.

453
00:35:07,200 --> 00:35:17,660
Kio okazis estis se dequeueing la alta elemento

454
00:35:17,660 --> 00:35:20,590
estis farita kaj ni ne havas tiun kapon kampo

455
00:35:20,590 --> 00:35:26,880
ĉar ni ĉiam nomante tiun ĉenon ĉe 0 indekso la kapo de nia vosto,

456
00:35:26,880 --> 00:35:30,170
tiam ni devus ŝanĝi la resto de la vosto sube.

457
00:35:30,170 --> 00:35:36,010
Necesus ŝanĝi "bye" el de kordoj [1] al la kordoj [0].

458
00:35:36,010 --> 00:35:38,760
Kaj ŝnuro [2] malsupren al kordoj [1].

459
00:35:38,760 --> 00:35:43,050
Kaj ni devus fari tion por la tuta listo de elementoj,

460
00:35:43,050 --> 00:35:45,110
en la tuta tabelo de elementoj.

461
00:35:45,110 --> 00:35:50,490
Kaj kiam ni faras tion kun tabelo, kiu alvenas vere peniga.

462
00:35:50,490 --> 00:35:53,340
Do jen, ne granda interkonsento. Ni nur havas tri elementoj en nia tabelo.

463
00:35:53,340 --> 00:35:57,230
Sed se ni havis voston el mil eroj aŭ miliono elementoj,

464
00:35:57,230 --> 00:36:00,060
kaj tiam subite, ni komencos fari aron da dequeue nomas ĉiujn en buklo,

465
00:36:00,060 --> 00:36:03,930
aĵoj vere tuj bremsi kiel ŝanĝas ĉiun malsupren senĉese.

466
00:36:03,930 --> 00:36:07,320
Vi scias, ŝanĝi per 1, shift per 1, shift per 1, shift per 1.

467
00:36:07,320 --> 00:36:13,650
Anstataŭe, ni uzas ĉi kapo, ni nomas ĝin "pointer" kvankam ĝi ne estas vere puntero

468
00:36:13,650 --> 00:36:16,430
en la strikta senco, temas ne puntero tipo.

469
00:36:16,430 --> 00:36:19,410
Ne estas int * aŭ char * aŭ io kiel tio.

470
00:36:19,410 --> 00:36:28,930
Sed gxi montras aŭ indikante la kapo de nia vico. Yeah?

471
00:36:28,930 --> 00:36:38,800
>> [Studenta] Kiel dequeue scias ĝuste popo ekstere kio ajn en la kapon?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Kiel dequeue scias popo ekstere ajn estas en la kapo? >> Ĝuste, jes.

473
00:36:43,620 --> 00:36:49,050
>> Kio ĝi estas rigardanta estas ĝuste kion la kapo kampo estas agordita por.

474
00:36:49,050 --> 00:36:52,710
Do en tiu unua kazo, se ni rigardas ĝuste tie,

475
00:36:52,710 --> 00:36:55,690
nia kapo estas 0, indico 0. >> Ĝuste.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Do nur diras bone, bone, la elemento en indekso 0, la ĉeno "hi",

477
00:37:00,500 --> 00:37:03,050
estas la elemento al la kapo de nia vico.

478
00:37:03,050 --> 00:37:05,570
Do ni tuj dequeue ke ulo.

479
00:37:05,570 --> 00:37:09,800
Kaj tio estos la elemento kiu prenas revenis al la telefonanto.

480
00:37:09,800 --> 00:37:14,540
Jes, Saad? >> Do la kapo esence fiksas la - kie vi tuj indekso ĝin?

481
00:37:14,540 --> 00:37:17,750
Tio estas la komenco de ĝi? >> Jes. >> Bone.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Tio igas la nova komenco por niaj tabelo.

483
00:37:22,900 --> 00:37:28,930
Do kiam vi dequeue io, ĉio vi devas fari estas atingi la elemento en indekso q.head,

484
00:37:28,930 --> 00:37:32,240
kaj tio estos la elemento kiu vi volas dequeue.

485
00:37:32,240 --> 00:37:34,930
Vi ankaŭ devas dekremento la grandeco.

486
00:37:34,930 --> 00:37:39,430
Ni vidos en iom kie aĵoj iom malfacila per ĉi.

487
00:37:39,430 --> 00:37:46,520
Ni dequeue, kaj nun, se ni enqueue denove,

488
00:37:46,520 --> 00:37:51,300
kie ni enqueue?

489
00:37:51,300 --> 00:37:55,000
Kie la sekvanta elemento iri en nia vosto?

490
00:37:55,000 --> 00:37:57,980
Ke ni volas enqueue la ĉeno "CS".

491
00:37:57,980 --> 00:38:02,240
En kiun indekso ĉu ĝi iru? [Studentoj] Ĉenoj [2]. >> Du.

492
00:38:02,240 --> 00:38:04,980
Kial 2 kaj ne 0?

493
00:38:04,980 --> 00:38:13,570
[Bazilo] Ĉar nun la kapo estas 1, tiel ke estas kiel la komenco de la listo?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Ĝuste. Kaj kion signifas la finon de la listo?

495
00:38:21,220 --> 00:38:23,290
Kion ni uzas por indiki la finon de nia vosto?

496
00:38:23,290 --> 00:38:25,970
La kapo estas la kapo de nia vosto, la komenco de nia vico.

497
00:38:25,970 --> 00:38:29,530
Kio estas la fino de nia vosto? [Studentoj] Grandeco. >> Grando, precize.

498
00:38:29,530 --> 00:38:36,360
Tiel niaj novaj elementoj iru ĉe grandeco, kaj la elementoj, ke ni demetas elspezas en kapo.

499
00:38:36,360 --> 00:38:45,390
Kiam ni enqueue la sekvanta elemento, ni metas ĝin en je grandeco.

500
00:38:45,390 --> 00:38:48,530
[Studenta] Antaŭ ol vi metis tiun en kvankam, grandeco estis 1, right?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Ĝuste. Do ne sufiĉe je grandeco. Grandeco +, ne +1, sed + kapo.

502
00:38:55,690 --> 00:38:59,990
Ĉar ni ŝanĝis ĉiun por la kapo kvanto.

503
00:38:59,990 --> 00:39:14,270
Do jen, nun ni havas vosto de amplekso 1 kiu komenciĝas je indekso 1.

504
00:39:14,270 --> 00:39:20,730
La vosto estas indekso 2. Jes?

505
00:39:20,730 --> 00:39:25,780
>> [Studenta] Kio okazas kiam vi dequeue kordoj [0], kaj la ŝnuroj 'fendoj en memoro

506
00:39:25,780 --> 00:39:29,420
nur get malplenigis, esence, aŭ nur forgesis la pasvorton?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. Tiusence, ni simple forgesas ilin.

508
00:39:34,700 --> 00:39:42,640
Se ni stokante kopiojn de ili por -

509
00:39:42,640 --> 00:39:46,310
multaj datumstrukturoj ofte stoki sia kopiojn de la elementoj

510
00:39:46,310 --> 00:39:51,760
por ke la persono administri la datumojn strukturo ne devas maltrankviligi

511
00:39:51,760 --> 00:39:53,650
pri kie ĉiuj tiuj punteros iras.

512
00:39:53,650 --> 00:39:56,000
La datumstrukturo tenas al ĉiu, tenas en la tuta kopioj,

513
00:39:56,000 --> 00:39:59,580
certigi ke ĉiu persistas taŭge.

514
00:39:59,580 --> 00:40:03,140
Tamen, en ĉi tiu kazo, tiuj datumstrukturoj justa, por simpleco,

515
00:40:03,140 --> 00:40:05,580
ne farante kopiojn de io, kio ni stokante en ili.

516
00:40:05,580 --> 00:40:08,630
[Studenta] Tia estas ĉi tiu kontinua tabelo de -? >> Jes.

517
00:40:08,630 --> 00:40:14,350
Se ni retrorigardas al kio la difino estis de ĉi tiu strukturo, ĝi estas.

518
00:40:14,350 --> 00:40:19,110
Estas nur normo tabelo kiel vi vidis,

519
00:40:19,110 --> 00:40:24,280
tabelo de char * s.

520
00:40:24,280 --> 00:40:26,340
Ĉu tio -? >> Jes, mi ĵus demandis

521
00:40:26,340 --> 00:40:29,130
se vi eventuale elĉerpas de memoro, en iu punkto,

522
00:40:29,130 --> 00:40:32,330
se vi havas ĉiujn tiujn malplenajn makuloj en via tabelo?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Jes, tio estas bona punkto.

524
00:40:36,390 --> 00:40:41,530
>> Se ni rigardas kio okazis nun en ĉi tiu punkto,

525
00:40:41,530 --> 00:40:46,350
ni plenigis niajn vosto, ĝi aspektas.

526
00:40:46,350 --> 00:40:50,390
Sed ni ne vere plenigis niajn vosto

527
00:40:50,390 --> 00:40:57,710
ĉar ni havas voston jen grandeco 2, sed komenciĝas je indico 1,

528
00:40:57,710 --> 00:41:02,160
ĉar tie estas kie nia kapo pointer is.

529
00:41:02,160 --> 00:41:08,400
Kiel vi diris, ke elemento en kordoj [0], ĉe indeksa 0, estas ne vere ekzistas.

530
00:41:08,400 --> 00:41:10,450
Ne en nia vosto plu.

531
00:41:10,450 --> 00:41:16,460
Ni simple ne tedis iri en kaj anstatauxigas ĝin kiam ni dequeued ĝin.

532
00:41:16,460 --> 00:41:18,700
Do kvankam ĝi aspektas kiel ni ne plu havas memoron, ni vere ne havas.

533
00:41:18,700 --> 00:41:23,270
Tiu loko estas havebla por ni uzas.

534
00:41:23,270 --> 00:41:29,310
La taŭga konduto, se ni devis provi kaj unua dequeue ion

535
00:41:29,310 --> 00:41:34,420
kiel "bye", kiu estus popo bye malproksime.

536
00:41:34,420 --> 00:41:38,460
Nun nia queue komencas indekso 2 kaj estas de amplekso 1.

537
00:41:38,460 --> 00:41:42,240
Kaj nun se ni provas kaj enqueue io pli, diras 50,

538
00:41:42,240 --> 00:41:47,880
50 iru en ĉi loko en indekso 0

539
00:41:47,880 --> 00:41:51,270
ĉar ĝi estas ankoraŭ disponebla por ni. Jes, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Does kiuj okazas aŭtomate?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Ĝi ne okazas tute aŭtomate. Vi devas fari la math

542
00:41:56,150 --> 00:42:00,380
fari ĝin funkcii, sed esence kion ni faris estas ni nur envolvis ĉirkaŭe.

543
00:42:00,380 --> 00:42:04,070
[Saad] Kaj ĉu bone se tiu havas truon en la mezo de gxi?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ĝi estas se ni povas fari la math ellabori konvene.

545
00:42:08,720 --> 00:42:15,470
>> Kaj ĝi rezultas ke tiu fakte ne estas tiel malfacila por fari kun la mod operatoro.

546
00:42:15,470 --> 00:42:20,040
Do same kiel ni faris kun Cezaro kaj la kripto stuff,

547
00:42:20,040 --> 00:42:25,190
uzante mod, ni povos atingi tion por envolver ĉirkaŭe kaj observu tuj

548
00:42:25,190 --> 00:42:28,090
ĉirkaŭ kaj ĉirkaŭ kaj ĉirkaŭ kun niaj vosto,

549
00:42:28,090 --> 00:42:32,180
subtenante ke kapo puntero movi ĉirkaŭe.

550
00:42:32,180 --> 00:42:38,840
Rimarku ke grandeco ĉiam respektante la nombro de eroj vere ene de la vosto.

551
00:42:38,840 --> 00:42:43,110
Kaj estas simple la kapo puntero kiu subtenas biciklado tra.

552
00:42:43,110 --> 00:42:49,660
Se ni rigardas kio okazis cxi tie, se ni reiros al la komenco,

553
00:42:49,660 --> 00:42:55,020
kaj vi simple rigardi kio okazas al la kapo

554
00:42:55,020 --> 00:42:58,240
kiam ni enqueue io, nenio okazis al la kapo.

555
00:42:58,240 --> 00:43:00,970
Kiam ni enqueued io alia, nenio okazis al la kapo.

556
00:43:00,970 --> 00:43:04,130
Tuj kiam ni dequeued io, la estro iras al oni.

557
00:43:04,130 --> 00:43:06,600
Ni enqueued io, nenio okazas en la kapo.

558
00:43:06,600 --> 00:43:11,060
Kiam ni dequeue ion, subite la kapon gets incremented.

559
00:43:11,060 --> 00:43:14,660
Kiam ni enqueue io, nenio okazas en la kapo.

560
00:43:14,660 --> 00:43:20,240
>> Kio okazus en ĉi tiu punkto se ni devis dequeue io denove?

561
00:43:20,240 --> 00:43:23,240
Ajna pensoj? Kio okazus al la kapo?

562
00:43:23,240 --> 00:43:27,190
Kion okazas al la kapo

563
00:43:27,190 --> 00:43:32,990
se ni devis dequeue ion alian?

564
00:43:32,990 --> 00:43:35,400
La kapo nun estas je indekso 2,

565
00:43:35,400 --> 00:43:38,920
kio signifas, ke la kapo de la vosto estas kordoj [2].

566
00:43:38,920 --> 00:43:44,280
[Studenta] Kiu redonas 0? >> Ĝi devus reveni al 0. Ĝi devus kovri reen ĉirkaŭe, precize.

567
00:43:44,280 --> 00:43:48,440
Ĝis nun, ĉiufoje kiam ni nomas dequeue, ni estis aldono al la kapo,

568
00:43:48,440 --> 00:43:50,960
aldoni al la kapo, ili aldonas al la kapo, ili aldonas al la kapo.

569
00:43:50,960 --> 00:43:58,400
Tuj kiam tiu kapo puntero alvenas al la lasta indekso en nia tabelo,

570
00:43:58,400 --> 00:44:05,650
tiam ni devas kovri ĝin ĉirkaŭ la komenco, reiru al 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Kio determinas la kapablo de la vosto en pilo?

572
00:44:09,900 --> 00:44:13,120
[Hardison] En ĉi tiu kazo, ni ĵus uzante # difinita konstanto. >> Bone.

573
00:44:13,120 --> 00:44:19,590
[Hardison] En la reala. C dosiero, vi povas iri en kaj Muck per ĝi iomete

574
00:44:19,590 --> 00:44:21,710
kaj fari ĝin tiel granda aŭ tiel malgranda kiel vi volas.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Do kiam vi faras ĝin vosto, kiel vi faras la komputilo scias

576
00:44:25,310 --> 00:44:29,120
kiel granda vi volas ke la pilo esti?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Tio estas granda demando.

578
00:44:31,700 --> 00:44:34,800
Ekzistas kelkaj manieroj. Unu estas simple difini ĝin fronto

579
00:44:34,800 --> 00:44:42,050
kaj diru ĉi tiu tuj estos vosto kiu havas 4 eroj aŭ 50 eroj aŭ 10.000.

580
00:44:42,050 --> 00:44:45,430
La alia maniero estas fari kion la hacker eldono uloj faras

581
00:44:45,430 --> 00:44:52,310
kaj krei funkcioj havi vian voston kreski dinamike kiel pli aĵoj get aldonis in

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Do iru kun la unua eblo, kion sintakso vi uzas

583
00:44:54,740 --> 00:44:57,830
por diri al la programo, kio estas la grandeco de la vosto?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Do ni eskapos de ĉi.

585
00:45:04,780 --> 00:45:12,650
Mi estas ankoraŭ en stack.c tie, do mi simple tuj rulumu supren al la supro tie.

586
00:45:12,650 --> 00:45:17,920
Ĉu vi povas vidi ĉi tie ĉi? Ĉi tiu estas la # difini kapablo 10.

587
00:45:17,920 --> 00:45:24,600
Kaj jen estas preskaŭ la ĝusta sama sintakso ke ni havas por vico.

588
00:45:24,600 --> 00:45:28,390
Krom en vosto, ni havas ke ekstra struct kampo en ĉi tie.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Ho, mi pensis, ke la kapablo signifis la kapablo por la kordo.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Tio estas la maksimuma longeco de la vorto. >> Got ĝin.

591
00:45:36,770 --> 00:45:41,180
Yeah. La kapablo tie - jen granda punkto.

592
00:45:41,180 --> 00:45:44,000
Kaj jen estas iu kiu estas malfacila

593
00:45:44,000 --> 00:45:49,480
ĉar kion ni deklaras jen tabelo de char * s.

594
00:45:49,480 --> 00:45:52,770
Tabelo de punteros.

595
00:45:52,770 --> 00:45:56,690
Jen tabelo de signoj.

596
00:45:56,690 --> 00:46:01,690
Tio estas verŝajne tio, kion vi vidis, kiam vi estis deklari vian buffers por dosiero / S,

597
00:46:01,690 --> 00:46:06,840
kiam vi estis kreante kordoj permane sur la stako.

598
00:46:06,840 --> 00:46:09,090
Tamen, kion ni havas ĉi tie estas tabelo de char * s.

599
00:46:09,090 --> 00:46:13,400
Do ĝi estas tabelo de punteros.

600
00:46:13,400 --> 00:46:18,350
Efektive, se ni zoom reen eksteren kaj ni rigardas kio okazas ĉi tie

601
00:46:18,350 --> 00:46:23,140
en la prezento, vi vidas ke la reala elementoj, la karaktero datumoj

602
00:46:23,140 --> 00:46:26,180
ne stokas ene de la tabelo mem.

603
00:46:26,180 --> 00:46:42,690
Kio stokitaj en nia tabelo jen punteros al la karaktero datumoj.

604
00:46:42,690 --> 00:46:52,560
Okay. Do ni vidas kiel la grandeco de la vosto estas nur kiel kun la pilo,

605
00:46:52,560 --> 00:46:58,670
la grandeco ĉiam respektas la nombro de eroj nuntempe en la vico.

606
00:46:58,670 --> 00:47:02,720
Post fari 2 enqueues, la grandeco estas 2.

607
00:47:02,720 --> 00:47:07,110
Post fari dequeue la grandeco estas nun 1.

608
00:47:07,110 --> 00:47:09,330
Post fari alian enqueue la grandeco estas reen ĝis 2.

609
00:47:09,330 --> 00:47:12,340
Do la grandeco definitive respektas la nombro de elementoj en la vosto,

610
00:47:12,340 --> 00:47:15,580
kaj tiam la kapo nur subtenas biciklado.

611
00:47:15,580 --> 00:47:20,210
Ĝi iras de 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Kaj ĉiufoje ni nomas dequeue, la estro puntero gets incremented al la sekvanta indekso.

613
00:47:25,620 --> 00:47:29,930
Kaj se la kapo estas por transiri, ĝi cikloj reen ĉirkaŭ al 0.

614
00:47:29,930 --> 00:47:34,870
Do kun tio, ni povas skribi la dequeue funkcio.

615
00:47:34,870 --> 00:47:40,200
Kaj ni tuj forlasi la enqueue funkcio por vi infanoj apliki anstataŭe.

616
00:47:40,200 --> 00:47:45,880
>> Kiam ni dequeue ero el niaj vosto,

617
00:47:45,880 --> 00:47:55,490
kio estis la unua kiu Daniel faris kiam ni komencis skribi la popo funkcio por piloj?

618
00:47:55,490 --> 00:48:00,490
Lasu min aŭdi de iu kiu ne parolis ankoraŭ.

619
00:48:00,490 --> 00:48:06,710
Ni vidas, Saad, ĉu vi memoras, kion Daniel faris, kiel la unua horo, kiam li skribis popo?

620
00:48:06,710 --> 00:48:08,860
[Saad] Ne estis, estis - >> Li provis ion.

621
00:48:08,860 --> 00:48:12,140
[Saad] Se grandeco estas pli granda ol 0. >> Ekzakte.

622
00:48:12,140 --> 00:48:14,390
Kaj kio estis tiu provoj por?

623
00:48:14,390 --> 00:48:19,090
[Saad] Tio estis provante vidi se estas io interne de la tabelo.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Ekzakte. Do vi ne povas popo ion el la stako se estas malplena.

625
00:48:23,210 --> 00:48:26,510
Tiel same, vi ne povas dequeue ion el vosto se estas malplena.

626
00:48:26,510 --> 00:48:30,420
Kio estas la unua aĵo kiun ni devas fari en nia dequeue funkcio ĉi tie, ĉu vi opinias?

627
00:48:30,420 --> 00:48:33,860
[Saad] Se grandeco estas pli granda ol 0? >> Jes.

628
00:48:33,860 --> 00:48:37,710
En ĉi tiu kazo, mi fakte nur provis vidi se ĝi estas 0.

629
00:48:37,710 --> 00:48:42,240
Se ĝi estas 0, ni povas reveni nula.

630
00:48:42,240 --> 00:48:45,280
Sed ĝusta sama logiko.

631
00:48:45,280 --> 00:48:49,110
Kaj ni daŭrigas kun ĉi.

632
00:48:49,110 --> 00:48:54,600
Se la grandeco estas ne 0, kie estas la elemento kiun ni deziras dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Al la kapo? >> Ekzakte.

634
00:48:58,550 --> 00:49:01,720
Ni povas nur eltiri la unua elemento de nia vosto

635
00:49:01,720 --> 00:49:07,040
alirante la elemento en la kapo.

636
00:49:07,040 --> 00:49:14,630
Nenio freneza.

637
00:49:14,630 --> 00:49:19,620
Post tio, kion ni faru? Kio devas okazi?

638
00:49:19,620 --> 00:49:23,740
Kio estis la alia afero, ke ni raportis en dequeue?

639
00:49:23,740 --> 00:49:28,130
Du aferoj devas okazi, ĉar nia queue ŝanĝis.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Redukti la grandeco. >> Ni devas redukti la grandecon, kaj plimultigos la kapo? Ekzakte.

641
00:49:35,640 --> 00:49:40,600
Pliigi la kapon, ni ne povas simple blinde pliigi la kapo, memoru.

642
00:49:40,600 --> 00:49:45,080
Ni ne povas nur fari queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Ni devas ankaŭ inkluzivi ĉi mod de la kapacito.

644
00:49:51,630 --> 00:49:54,740
Kaj kial ni mod per la kapablo, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Ĉar ĝi devas kovri ĉirkaŭe. >> Ekzakte.

646
00:49:58,680 --> 00:50:04,750
Ni mod de la kapablo ĉar ĝi havas por envolver reen ĉirkaŭ al 0.

647
00:50:04,750 --> 00:50:07,400
Do nun, je ĉi tiu punkto, ni povas fari kion Daniel diris.

648
00:50:07,400 --> 00:50:12,700
Ni povas dekremento la grandeco.

649
00:50:12,700 --> 00:50:29,170
Kaj tiam ni povas nur redonas la elemento kiu estis sur la supro de la vico.

650
00:50:29,170 --> 00:50:34,000
Ĝi aspektas ia gnarly en komenco. Vi eble havas demandon. Pardonu?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Kial estas unue en la supro de la vosto? Kie kiuj iras?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ĝi venas de la kvara linio de sube.

653
00:50:42,480 --> 00:50:46,060
Post kiam ni provi certigi ke nia vosto estas ne malplena,

654
00:50:46,060 --> 00:50:54,100
ni eltiri char * unue, ni eltiri la elemento kiu sidas ĉe la kapo indekso

655
00:50:54,100 --> 00:50:58,680
de nia tabelo, de nia kordoj tabelo, >> kaj alvoko tiu unua?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Kaj ni nomas ĝin unue. Yeah.

657
00:51:04,500 --> 00:51:09,850
Nur sekvi sur tio, kial vi pensas, ke ni devis fari tion?

658
00:51:09,850 --> 00:51:18,270
[Sam] Ĉiu unua estas simple reveni q.strings [q.head]? >> Jes.

659
00:51:18,270 --> 00:51:23,830
>> Ĉar ni faras ĉi ŝanĝiĝanta de la q.head kun la mod funkcio,

660
00:51:23,830 --> 00:51:27,810
kaj tie estas neniu maniero fari tion ene reveno linio ankaŭ.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Ekzakte. Vi estas makulo sur. Sam tute rimarki plu.

662
00:51:31,640 --> 00:51:36,800
La kialo ni devis eltiri la unua elemento de nia vosto kaj stoki ĝin en variablo

663
00:51:36,800 --> 00:51:43,030
estas ĉar tiu linio kie ni ĵus q.head,

664
00:51:43,030 --> 00:51:47,030
tie estas la mod operatoro en tie ne estas iu kiu povas fari

665
00:51:47,030 --> 00:51:51,230
kaj ĝi efektiviĝos en la kapo sen - en unu linio.

666
00:51:51,230 --> 00:51:54,480
Do ni vere devas eltiri la unua elemento, tiam ĝustigi la kapon,

667
00:51:54,480 --> 00:52:00,430
ĝustigi la grandecon, kaj tiam revenu la elemento kiu ni tiris eksteren.

668
00:52:00,430 --> 00:52:02,680
Kaj jen estas iu kiu ni vidas supreniru poste kun

669
00:52:02,680 --> 00:52:04,920
ligitaj listoj, kiel ni ludas tie kun ili.

670
00:52:04,920 --> 00:52:08,410
Ofte kiam vi liberigas aŭ disponi de ligitaj listoj

671
00:52:08,410 --> 00:52:13,500
Vi devas memori la sekva elemento, la sekvanta puntero de ligitaj listo

672
00:52:13,500 --> 00:52:16,330
antaŭ disponi de la aktuala.

673
00:52:16,330 --> 00:52:23,580
Ĉar alie vi forĵetu la informoj de kio restas en la listo.

674
00:52:23,580 --> 00:52:34,160
Nun, se vi iros al viaj aparaton, vi malfermas queue.c--x el ĉi.

675
00:52:34,160 --> 00:52:39,390
Do, se mi malfermos queue.c, lasu min zoom en ĉi tie,

676
00:52:39,390 --> 00:52:44,970
vi vidos, ke vi havas similan aspekto dosiero.

677
00:52:44,970 --> 00:52:49,200
Similaj-aspekta dosieron kion ni havis antaŭe kun stack.c.

678
00:52:49,200 --> 00:52:54,690
Ni havas nian struct por queue difinita ĝuste kiel ni vidis en la diapozitivoj.

679
00:52:54,690 --> 00:52:59,870
>> Ni havas nian enqueue funkcio kiu estas por vi fari.

680
00:52:59,870 --> 00:53:04,340
Kaj ni havas la dequeue funkcio ĉi tie.

681
00:53:04,340 --> 00:53:06,870
La dequeue funkcio en la dosiero estas unimplemented,

682
00:53:06,870 --> 00:53:13,230
sed mi remetis ĝin sur la PowerPoint por ke vi povas tajpi ĝin, se vi volas.

683
00:53:13,230 --> 00:53:16,690
Do dum la sekvaj 5 minutoj aŭ tiel, vi infanoj laboras en enqueue

684
00:53:16,690 --> 00:53:22,570
kiu estas preskaŭ ĝuste la malo de dequeue.

685
00:53:22,570 --> 00:53:29,560
Vi ne devas ĝustigi kapon kiam vi enqueueing, sed kion vi havas por ĝustigi?

686
00:53:29,560 --> 00:53:38,920
Grandeco. Do kiam vi enqueue, la kapo restas netuŝita, la grandeco gets ŝanĝis.

687
00:53:38,920 --> 00:53:46,920
Sed ĝi prenos iom el - vi devos ludi tie kun tiu mod

688
00:53:46,920 --> 00:53:57,560
elŝeligi precize kion indekso la nova elemento devas esti aldonitaj en.

689
00:53:57,560 --> 00:54:03,080
Do mi donos al vi infanoj iom, ŝovis dequeue reen sur la glito,

690
00:54:03,080 --> 00:54:05,200
kaj kiel vi infanoj havas demandojn, krii ilin tiel ke ni povas

691
00:54:05,200 --> 00:54:09,220
ĉiuj parolas pri ili kiel grupo.

692
00:54:09,220 --> 00:54:13,960
Ankaŭ, kun la grandeco vi ne batu - kiam vi ĝustigi la grandecon, vi povas ĉiam nur -

693
00:54:13,960 --> 00:54:18,720
vi devas mod la grandeco iam? [Daniel] No >> Vi ne devas mod la grandecon, dekstre.

694
00:54:18,720 --> 00:54:24,260
Ĉar la grandeco estos ĉiam, se you're - supozante ke vi administri aferojn taŭge,

695
00:54:24,260 --> 00:54:30,840
la grandeco ĉiam estos inter 0 kaj 3.

696
00:54:30,840 --> 00:54:38,680
Kie vi devas mod kiam vi faras enqueue?

697
00:54:38,680 --> 00:54:41,060
[Studenta] Nur por la kapo. >> Nur por la kapo, ĝuste.

698
00:54:41,060 --> 00:54:44,620
Kaj kial vi devas mod ajn en enqueue?

699
00:54:44,620 --> 00:54:48,830
Kiam estas situacio en kiu vi devus mod?

700
00:54:48,830 --> 00:54:53,630
[Studenta] Se vi havas frandajxojn cxe spacoj, kiel en spacoj 1 kaj 2,

701
00:54:53,630 --> 00:54:55,950
kaj tiam vi bezonis aldoni ion je 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Jes, ĝuste. Do, se via kapo puntero estas ke je la fino,

703
00:55:02,570 --> 00:55:14,210
aŭ se via grandeco plus via kapo estas granda, aŭ pli ĝuste, tuj envolver ĉirkaŭ la vosto.

704
00:55:14,210 --> 00:55:17,830
>> Do en tiu situacio, ke ni havas ĉi tie sur la glito ĝuste nun,

705
00:55:17,830 --> 00:55:24,370
se mi volas enqueue ion nun,

706
00:55:24,370 --> 00:55:31,110
ni volas enqueue io en indekso 0.

707
00:55:31,110 --> 00:55:35,450
Do, se vi rigardas al kie la 50 iras, kaj mi nomas enqueue 50,

708
00:55:35,450 --> 00:55:40,840
ĝi iras tien je la fundo. Ĝi iras en indekso 0.

709
00:55:40,840 --> 00:55:44,160
Ĝi anstataŭas la 'hi' kiu jam dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Cxu vi ne atentas, ke en dequeue jam?

711
00:55:46,210 --> 00:55:50,550
Kial gxi faras nenion kun la kapo en enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ho, do vi ne modifante la kapo, sorry.

713
00:55:55,770 --> 00:56:02,310
Sed vi devas uzi la mod operatoro kiam vi konsentas

714
00:56:02,310 --> 00:56:04,250
la elemento kiu vi volas enqueue kiam vi konsentas

715
00:56:04,250 --> 00:56:06,960
la sekvanta elemento en via vico.

716
00:56:06,960 --> 00:56:10,960
[Bazilo] Mi ne faris tion, kaj mi atingis "sukceso" de tie.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Ho, mi komprenas kion vi diras.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Do vi didn't - vi ĵus faris ĉe q.size?

719
00:56:16,240 --> 00:56:20,670
[Bazilo] Yeah. Mi nur ŝanĝis flankoj, mi faris nenion kun la kapo.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Vi ne vere devas nuligi la kapon esti io,

721
00:56:24,300 --> 00:56:31,650
sed kiam vi indekson en la kordoj tabelo,

722
00:56:31,650 --> 00:56:39,500
vi fakte devas iri antaŭen kaj kalkuli kie la sekva elemento estas,

723
00:56:39,500 --> 00:56:44,230
ĉar withe la pilo, la sekva elemento en via pilo estis ĉiam

724
00:56:44,230 --> 00:56:48,740
ĉe la indico responda al la grandeco.

725
00:56:48,740 --> 00:56:55,850
Se ni retrorigardas ĉe nia stako puŝo funkcio,

726
00:56:55,850 --> 00:57:03,100
ni povis ĉiam plunk en nia nova elemento ĝuste en indeksa amplekso.

727
00:57:03,100 --> 00:57:06,710
Dum kun la vosto, ni ne povas fari tion

728
00:57:06,710 --> 00:57:10,340
ĉar se ni estas en ĉi tiu situacio,

729
00:57:10,340 --> 00:57:18,130
se ni enqueued 50 nian novan ĉenon irus dekstren ĉe kordoj [1]

730
00:57:18,130 --> 00:57:20,540
kion ni ne volas fari.

731
00:57:20,540 --> 00:57:41,200
Ni volas havi la novan ĉenon iru ĉe indeksa 0.

732
00:57:41,200 --> 00:57:44,320
>> Ĉu neniu - jes? [Studenta] Mi havas demandon sed ne vere rilataj.

733
00:57:44,320 --> 00:57:48,160
Kion tio signifas kiam iu simple nomas iun kiel pred puntero?

734
00:57:48,160 --> 00:57:51,260
Kio estas tiu nomo mallongigo? Mi scias ke estas nur nomo.

735
00:57:51,260 --> 00:57:59,110
[Hardison] pred puntero? Ni vidu. En kio kunteksto?

736
00:57:59,110 --> 00:58:01,790
[Studenta] Ĝi estis por la insert. Mi povas demandi vin poste se vi volas

737
00:58:01,790 --> 00:58:03,920
ĉar ĝi ne estas vere rilataj, sed mi nur -

738
00:58:03,920 --> 00:58:07,300
[Hardison] De David insert kodo de prelego?

739
00:58:07,300 --> 00:58:10,860
Ni povas tiri ke tien kaj paroli pri tio.

740
00:58:10,860 --> 00:58:15,550
Ni parolos pri tio baldaŭ, iam ni atingos ligitaj listoj.

741
00:58:15,550 --> 00:58:21,440
>> Do ni vere rapide rigardi, kion la enqueue funkcio similas.

742
00:58:21,440 --> 00:58:26,530
Kio estis la unua kiu homoj provis fari en via enqueue linio? En tiun vosto?

743
00:58:26,530 --> 00:58:29,960
Simila al tio, kion vi faris por pilo pelante.

744
00:58:29,960 --> 00:58:32,080
Kion vi faris, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nekomprenebla]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Ekzakte. If (q.size == kapablo) -

747
00:58:45,700 --> 00:58:54,720
Mi bezonas meti mian streĉaj en la ĝusta loko - reveni falsaj.

748
00:58:54,720 --> 00:59:01,370
Zoom en iomete. Okay.

749
00:59:01,370 --> 00:59:03,800
Nun kio estas la sekvanta afero kiun ni devis fari?

750
00:59:03,800 --> 00:59:11,370
Ĝuste kiel kun la pilo, kaj insertos en la ĝusta loko.

751
00:59:11,370 --> 00:59:16,010
Kaj tiel, kio estas la ĝusta loko por enmeti tion?

752
00:59:16,010 --> 00:59:23,170
Kun la pilo estis indekso grandeco, kun ĉi tio ne estas sufiĉe ke.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Mi havas q.head--aŭ - >> q.strings? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod kapablo]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Ni probable volas meti krampojn ĉirkaŭ ĉi

756
00:59:42,740 --> 00:59:48,830
por ke ni ricevas la taŭga prioritaton do jen cleart al ĉiuj.

757
00:59:48,830 --> 00:59:55,800
Kaj starigis kiu egala? >> To str? >> To str. Granda.

758
00:59:55,800 --> 01:00:00,160
Kaj nun kio estas la lasta afero kiun ni devas fari?

759
01:00:00,160 --> 01:00:06,780
Samkiel ni faris en la stako. >> Pliigo de la grandeco? >> Pliigo la grandeco.

760
01:00:06,780 --> 01:00:13,830
Eksplodo. Kaj poste, ekde la malfermilo kodo ĵus revenis falsa implicite,

761
01:00:13,830 --> 01:00:27,460
ni volas ŝanĝi ĉi tion al vera se ĉiu iras tra kaj ĉiuj iras bone.

762
01:00:27,460 --> 01:00:33,050
Bone. Tio estas multe da informo por sekcio.

763
01:00:33,050 --> 01:00:39,480
Ni ne tute finita. Ni volas paroli vere rapide pri unuope-ligitaj listoj.

764
01:00:39,480 --> 01:00:44,010
Mi metis tiun supren do ni povas reiri al ĝi poste.

765
01:00:44,010 --> 01:00:50,850
Sed ni reiru al nia prezento por nur kelkaj pli diapozitivoj.

766
01:00:50,850 --> 01:00:53,790
Do enqueue estas Tōdō, nun ni jam faris.

767
01:00:53,790 --> 01:00:57,430
>> Nun ni rigardu unuope-ligitaj listoj.

768
01:00:57,430 --> 01:01:00,040
Ni parolis pri tiuj iom pli en prelego.

769
01:01:00,040 --> 01:01:02,540
Kiel multaj el vi infanoj vidis la demo kie ni havis popolo

770
01:01:02,540 --> 01:01:08,220
mallerte montrante al ĉiu alia kaj okazigon nombroj? >> Mi estis en tio.

771
01:01:08,220 --> 01:01:16,620
>> Kion vi pensas infanoj? Ĉu tio, mi esperas desmitificar tiuj iomete?

772
01:01:16,620 --> 01:01:25,990
Kun listo, rezultas ke ni trakti tiun tipon, ke ni tuj voki nodo.

773
01:01:25,990 --> 01:01:32,520
Dum kun la vosto kaj la stako ni havis structs ke ni volonte nomas vosto en pilo,

774
01:01:32,520 --> 01:01:34,860
ni havis tiujn novajn vosto en pilo tipoj,

775
01:01:34,860 --> 01:01:39,240
tie listo estas vere nur konsistas el aro da nodoj.

776
01:01:39,240 --> 01:01:45,920
En la sama maniero kiu kordoj estas nur aro da signoj ĉiuj vicigitaj apud la alia.

777
01:01:45,920 --> 01:01:50,650
Al ligitaj listo estas nur nodo kaj alia nodo kaj alia nodo kaj alia nodo.

778
01:01:50,650 --> 01:01:55,080
Kaj anstataŭ rompante ĉiuj nodoj kune kaj stokante ilin contiguously

779
01:01:55,080 --> 01:01:58,090
ĉiuj dekstra flanko de la alia en la memoro,

780
01:01:58,090 --> 01:02:04,470
havante ĉi sekva puntero nin permesas konservi la nodoj kien, al la hazardo.

781
01:02:04,470 --> 01:02:10,500
Kaj tiam ia draton ili ĉiuj kune noti de unu al alia.

782
01:02:10,500 --> 01:02:15,850
>> Kaj kio estis la granda avantaĝo ke ĉi havis super tabelo?

783
01:02:15,850 --> 01:02:21,680
Super provizon ĉio contiguously gluiĝis apud la alia?

784
01:02:21,680 --> 01:02:24,190
Vi memoras? Yeah? >> Dinamika memoro atribuo?

785
01:02:24,190 --> 01:02:27,220
>> Dinamika memoro atribuo en kiu senco?

786
01:02:27,220 --> 01:02:31,780
[Studenta] En kiu vi povas subteni farante ĝin pli granda, kaj vi ne devas movi vian tutan tabelo?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Ekzakte. Do kun tabelo, kiam vi volas meti novan elementon en la mezon de ĝi,

788
01:02:40,940 --> 01:02:45,320
vi devas ŝanĝi ĉio por fari spacon.

789
01:02:45,320 --> 01:02:47,880
Kaj kiel ni parolis pri la vosto,

790
01:02:47,880 --> 01:02:50,080
jen kial ni tenas ke kapo pointer,

791
01:02:50,080 --> 01:02:52,050
por ke ni ne konstante sxangxigxantaj aĵoj.

792
01:02:52,050 --> 01:02:54,520
Ĉar kiu alvenas multekostaj se vi havas grandan tabelo

793
01:02:54,520 --> 01:02:57,130
kaj vi senĉese faras tiuj hazarda inserciones.

794
01:02:57,130 --> 01:03:00,820
Dum kun listo, ĉiuj vi devas fari estas ĵeti ĝin sur nova nodo,

795
01:03:00,820 --> 01:03:06,330
alĝustigi la punteros, kaj vi faris.

796
01:03:06,330 --> 01:03:10,940
Kio sucks pri tio?

797
01:03:10,940 --> 01:03:16,830
Aparte de la fakto ke ĝi ne estas tiel facila por labori kun tiel tablo? Yeah?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nu, mi supozas ke estas multe pli malfacile atingi specifan elemento en la ligitaj listo?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Oni ne povas simple salti al ajna elemento en la mezo de via ligitaj listo.

800
01:03:30,470 --> 01:03:33,800
Kiel vi devas fari ĝin anstataŭe? >> Vi devas treti tra la tuta afero.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Vi devas iri tra unuope, unu post la alia.

802
01:03:35,660 --> 01:03:38,480
Ĝi estas grandega - temas pri doloro.

803
01:03:38,480 --> 01:03:41,550
Kio estas la alia - estas alia falita al ĉi tio.

804
01:03:41,550 --> 01:03:45,340
[Bazilo] Vi ne povas iri antaŭen kaj malantaŭen? Vi devas iri unu direkto?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Nu do kiel ni solvi tiun, kelkfoje?

806
01:03:48,570 --> 01:03:53,370
[Bazilo] duoble-ligitaj listoj? >> Ekzakte. Estas duoble-ligitaj listoj.

807
01:03:53,370 --> 01:03:55,540
Ekzistas ankaŭ - sorry?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Is that la sama kiel uzanta la pred kiu -

809
01:03:57,620 --> 01:04:01,090
Mi nur memoris, ne estas tio kio la pred afero estas por?

810
01:04:01,090 --> 01:04:05,850
Ĉu tio ne inter duoble kaj unuope?

811
01:04:05,850 --> 01:04:10,020
[Hardison] ni rigardu kio precize li faris.

812
01:04:10,020 --> 01:04:15,760
Do jen ni iru. Jen la listo kodo.

813
01:04:15,760 --> 01:04:25,620
Jen ni havas predptr, en ĉi tie. Ĉu ĉi tiu estas kion vi parolis?

814
01:04:25,620 --> 01:04:30,750
Do tio - li liberigante liston kaj li provas gardi puntero al ĝi.

815
01:04:30,750 --> 01:04:35,000
Tiu ne estas la duoble, unuope ligitaj-listoj.

816
01:04:35,000 --> 01:04:40,090
Ni povas paroli pli pri tio poste ekde ĉi parolas pri liberigo de la listo

817
01:04:40,090 --> 01:04:42,900
kaj mi volas montri iu alia materialo unue.

818
01:04:42,900 --> 01:04:51,480
sed estas nur - ĝin memorante la valoro de ptr

819
01:04:51,480 --> 01:04:54,170
[Studenta] Ho, estas preceeding puntero? >> Jes.

820
01:04:54,170 --> 01:05:04,070
Tiel ke ni povas tiam pliigo ptr mem antaŭ ol ni tiam senpaga kio predptr estas.

821
01:05:04,070 --> 01:05:09,130
Ĉar ni ne povas libera ptr kaj tiam nomita ptr = ptr proksima, right?

822
01:05:09,130 --> 01:05:11,260
Tio estus malbona.

823
01:05:11,260 --> 01:05:20,940
Do ni vidas, reen al ĉi tiu viro.

824
01:05:20,940 --> 01:05:23,900
>> La alia malbona afero pri lertaj estas kiu dum kiu kun tabelo

825
01:05:23,900 --> 01:05:26,520
ni nur devas ĉiujn elementojn sin plata flanko de la alia,

826
01:05:26,520 --> 01:05:29,050
tie ni ankaŭ enkondukis tiun puntero.

827
01:05:29,050 --> 01:05:34,060
Do ekzistas plia eron de memoro kiu ni devi uzi

828
01:05:34,060 --> 01:05:37,910
por ĉiu elemento kiu ni stokante en nia listo.

829
01:05:37,910 --> 01:05:40,030
Ni preni fleksebleco, sed venas al kosto.

830
01:05:40,030 --> 01:05:42,230
Ĝi venas kun ĉi tiu tempo kosto,

831
01:05:42,230 --> 01:05:45,270
kaj ĝi venas kun ĉi tiu memoro kosto ankaŭ.

832
01:05:45,270 --> 01:05:47,800
Tiam en la senco, ke ni nun devas iri tra ĉiu ero en la tabelo

833
01:05:47,800 --> 01:05:58,670
trovi la unu je indico 10, aŭ kiu estus estinta indekso 10 en tabelo.

834
01:05:58,670 --> 01:06:01,230
>> Nur vere rapide, kiam ni diagramon el tiuj lertaj,

835
01:06:01,230 --> 01:06:05,980
tipe ni tenadi la estro de la listo aŭ la unua montrilo de la listo

836
01:06:05,980 --> 01:06:08,010
kaj rimarku ke ĉi tio estas vera puntero.

837
01:06:08,010 --> 01:06:11,100
Estas nur 4 bitokoj. Ne reala nodo mem.

838
01:06:11,100 --> 01:06:17,120
Do vi vidas, ke ĝi havas nenian valoron int en ĝi, neniu sekva puntero en ĝi.

839
01:06:17,120 --> 01:06:20,790
Estas laŭvorte nur puntero.

840
01:06:20,790 --> 01:06:23,550
Ĝi tuj indikas iun kiu estas efektiva nodo struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] A puntero nomita nodo? >> Jen - ne. Tio ĉi estas puntero al iu el tipo nodo.

842
01:06:28,480 --> 01:06:32,540
Estas puntero al nodo struct. >> Ho, bone.

843
01:06:32,540 --> 01:06:36,870
Diagramo maldekstre kodon en la dekstra.

844
01:06:36,870 --> 01:06:42,190
Ni povas agordi ĝin al nula, kio estas bona maniero por komenci.

845
01:06:42,190 --> 01:06:49,850
Kiam vi diagramon ĝin, vi jam estas skribi ĝin kiel nula aŭ vi metis linion tra ĝi plaĉas.

846
01:06:49,850 --> 01:06:53,910
>> Unu el la plej facilaj manieroj por labori kun lertaj,

847
01:06:53,910 --> 01:06:57,430
kaj ni demandos vi ambaŭ prepend kaj aldonas por vidi la diferencojn inter la du,

848
01:06:57,430 --> 01:07:01,320
sed prepending estas definitive pli facila.

849
01:07:01,320 --> 01:07:05,790
Kiam vi prepend, ĉi tiu estas kie vi - kiam vi prepend (7),

850
01:07:05,790 --> 01:07:10,050
vi iru kaj krei la nodo struct

851
01:07:10,050 --> 01:07:13,870
kaj vi starigis unuan atentigi al tio, ĉar nun, kiel ni prepended ĝin,

852
01:07:13,870 --> 01:07:17,240
ĝi tuj estos al la komenco de la listo.

853
01:07:17,240 --> 01:07:22,540
Se ni prepend (3), kiu kreas alia nodo, sed nun 3 venas antaŭ 7.

854
01:07:22,540 --> 01:07:31,130
Do ni esence pelante aĵoj sur nia listo.

855
01:07:31,130 --> 01:07:34,720
Nun, vi povas vidi ke prepend, foje homoj nomas ĝin puŝi,

856
01:07:34,720 --> 01:07:39,600
ĉar vi puŝas nova elemento sur via lerta.

857
01:07:39,600 --> 01:07:43,270
Estas ankaŭ facile forviŝi ĉe la fronto de listo.

858
01:07:43,270 --> 01:07:45,650
Do homoj ofte nomas tion popo.

859
01:07:45,650 --> 01:07:52,200
Kaj en tiu vojo, vi povas imiti pilo uzante ligitaj listo.

860
01:07:52,200 --> 01:07:57,880
Whoops. Pardonu, nun ni eniru append. Do jen ni prepended (7), nun ni prepend (3).

861
01:07:57,880 --> 01:08:02,600
Se ni prepended ion alian sur tiu listo, se ni prepended (4),

862
01:08:02,600 --> 01:08:06,540
tiam ni havus 4 kaj tiam 3 kaj poste 7.

863
01:08:06,540 --> 01:08:14,220
Tial ni povus popo kaj forigi 4, forigu 3, forpreni 7.

864
01:08:14,220 --> 01:08:16,500
Ofte la pli intuicia maniero pensi pri tiu estas kun append.

865
01:08:16,500 --> 01:08:20,310
Do mi diagrammed el kio ĝi devus aspekti kun aldonas tie.

866
01:08:20,310 --> 01:08:23,380
Ĉi tie, aldonita (7) ne aspektas ajna malsamajn

867
01:08:23,380 --> 01:08:25,160
ĉar tie estas nur unu elemento de la listo.

868
01:08:25,160 --> 01:08:28,620
Kaj appending (3) metas je la fino.

869
01:08:28,620 --> 01:08:31,020
Eble vi povas vidi nun la trukon per append

870
01:08:31,020 --> 01:08:36,600
estas ke ĉar oni nur scias, kie la komenco de la listo estas,

871
01:08:36,600 --> 01:08:39,450
al aldonas al listo vi devas promeni tuta vojo tra la listo

872
01:08:39,450 --> 01:08:46,500
alveni ĝis la fino, halti, tiam konstrui vian nodo kaj plunk ĉio sube.

873
01:08:46,500 --> 01:08:50,590
Telegramon ĉiuj aĵoj supren.

874
01:08:50,590 --> 01:08:55,170
Do kun prepend, kiel ni ĵus disŝiris tra tiu vere rapide,

875
01:08:55,170 --> 01:08:58,170
kiam vi prepend al listo, estas sufiĉe simpla.

876
01:08:58,170 --> 01:09:02,960
>> Vi faras vian novan nodon, engaĝi iu dinamika memoro atribuo.

877
01:09:02,960 --> 01:09:09,830
Do jen ni fari nodon struct uzante malloc.

878
01:09:09,830 --> 01:09:14,710
Do malloc ni uzas ĉar tio estos flankenmetis memoro por ni por posta

879
01:09:14,710 --> 01:09:20,350
ĉar ni ne volas ĉi - ni volas tiun memoron al persisti dum longa tempo.

880
01:09:20,350 --> 01:09:25,350
Kaj ni preni sagon al la spaco en memoro kiujn ni ĵus asignitaj.

881
01:09:25,350 --> 01:09:29,260
Ni uzas grandeco de vertico, ni ne resumi la kampoj.

882
01:09:29,260 --> 01:09:31,899
Ni ne permane generi la nombro de bitokoj,

883
01:09:31,899 --> 01:09:39,750
anstataŭ ni uzas sizeof por ke ni sciu estas duumaj la taŭga nombro da bajtoj.

884
01:09:39,750 --> 01:09:43,660
Ni certigu por testi ke nia malloc alvoko sukcesis.

885
01:09:43,660 --> 01:09:47,939
Tio estas io, kion vi volas fari en ĝenerala.

886
01:09:47,939 --> 01:09:52,590
Sur modernaj maŝinoj, kurante el memoro ne estas iu kiu facile

887
01:09:52,590 --> 01:09:56,610
se vi atribuante barelon da aĵoj kaj farante grandan liston,

888
01:09:56,610 --> 01:10:02,220
sed se vi konstruas ajxojn, ekzemple, kiel iPhone aŭ Android,

889
01:10:02,220 --> 01:10:05,230
vi ja havas limigitan memoro rimedoj, speciale se vi faras ion intensa.

890
01:10:05,230 --> 01:10:08,300
Do ĝi estas bona por eniri en praktiko.

891
01:10:08,300 --> 01:10:10,510
>> Rimarku ke mi uzis paron malsamajn funkciojn tie

892
01:10:10,510 --> 01:10:12,880
ke vi vidis, ke estas ia nova.

893
01:10:12,880 --> 01:10:15,870
Do fprintf estas ĝuste kiel printf

894
01:10:15,870 --> 01:10:21,320
krom lia unua argumento estas la rivereto, en kiu vi volas presi.

895
01:10:21,320 --> 01:10:23,900
En ĉi tiu kazo, ni volas presi al cxeferarigo kordoj

896
01:10:23,900 --> 01:10:29,410
kiu estas malsama de la normo outstream.

897
01:10:29,410 --> 01:10:31,620
Defaŭlte ĝi aperas en la sama loko.

898
01:10:31,620 --> 01:10:34,600
Ĝi ankaŭ presas al la fina stacio, sed vi povas -

899
01:10:34,600 --> 01:10:38,790
uzante tiujn ordonojn vi lernis pri la redirección teknikoj

900
01:10:38,790 --> 01:10:42,290
vi lernis pri en Tommy video problemo aro 4, vi povas direkti ĝin

901
01:10:42,290 --> 01:10:47,900
al malsamaj areoj; tiam eliru, ĉi tie, eliroj via programo.

902
01:10:47,900 --> 01:10:50,440
Estas esence kiel reveni de ĉefaj,

903
01:10:50,440 --> 01:10:53,600
krom ni uzas eliro ĉar tie reveno ne faros nenion.

904
01:10:53,600 --> 01:10:57,140
Ni ne en ĉefaj, tiel redonante ne eliri la programon kiel ni deziras.

905
01:10:57,140 --> 01:11:03,020
Do ni uzu la eliro funkcio kaj donu eraro kodo.

906
01:11:03,020 --> 01:11:11,890
Tiam jen ni starigis la nova nodo valoron kampo, ĝia i kampo al esti egala al i, kaj tiam ni telegramon ĝin.

907
01:11:11,890 --> 01:11:15,530
Ni starigis la nova vertico La sekva puntero atentigi al la unua,

908
01:11:15,530 --> 01:11:20,460
kaj poste unua nun indikas la nova nodo.

909
01:11:20,460 --> 01:11:25,120
Tiuj unuaj linioj de kodo, ni reale konstrui la nova nodo.

910
01:11:25,120 --> 01:11:27,280
Ne la lastaj du linioj de tiu funkcio, sed la unuaj.

911
01:11:27,280 --> 01:11:30,290
Vi povas vere eltiri en funkcio, en helpanto funkcio.

912
01:11:30,290 --> 01:11:32,560
Tio ofte kion mi faras, mi tiri gxin al funkcio,

913
01:11:32,560 --> 01:11:36,040
Mi nomas ĝin iu kiel muntaĵo nodo,

914
01:11:36,040 --> 01:11:40,410
kaj kiu gardas la prepend funkcio bela malgranda, estas nur 3 linioj tiam.

915
01:11:40,410 --> 01:11:48,710
Mi faras alvokon al mia build nodo funkcio, kaj tiam mi drato ĉio supren.

916
01:11:48,710 --> 01:11:51,970
>> La fina afero mi volas montri al vi,

917
01:11:51,970 --> 01:11:54,030
kaj mi ellasos vin fari append kaj cxion, kio en via propra,

918
01:11:54,030 --> 01:11:57,500
estas kiel persisti super listo.

919
01:11:57,500 --> 01:12:00,780
Ekzistas multajn malsamajn manierojn persisti super listo.

920
01:12:00,780 --> 01:12:03,140
En ĉi tiu kazo, ni tuj trovi la longo de listo.

921
01:12:03,140 --> 01:12:06,570
Do ni komencu per longeco = 0.

922
01:12:06,570 --> 01:12:11,580
Ĉi tio estas tre simila al la skribo strlen por linio.

923
01:12:11,580 --> 01:12:17,780
Jen kion mi volas montri al vi, tion por buklo gxuste cxi tie.

924
01:12:17,780 --> 01:12:23,530
Ĝi aspektas kinda funky, temas ne la kutima int i = 0, i <ajn, i + +.

925
01:12:23,530 --> 01:12:34,920
Anstataŭe ĝi estas inicializar nia variablo n al esti la komenco de la listo.

926
01:12:34,920 --> 01:12:40,620
Kaj poste dum nia iterator variablo estas ne nulaj, ni plu iri.

927
01:12:40,620 --> 01:12:46,340
Ĉi tio estas ĉar, per konvencio, la fino de nia listo estos nula.

928
01:12:46,340 --> 01:12:48,770
Kaj tiam al pliigo, anstataŭ fari + +,

929
01:12:48,770 --> 01:12:57,010
la ligitaj listo ekvivalento de + + estas n = n-> proksima.

930
01:12:57,010 --> 01:13:00,410
>> Mi permesos al vi plenigi la truojn tie ĉar ni estas el la tempo.

931
01:13:00,410 --> 01:13:09,300
Sed observu cxi tion kiel vi laboras en via spellr psets.

932
01:13:09,300 --> 01:13:11,650
Ligitaj listoj, se vi implementando hash tablo,

933
01:13:11,650 --> 01:13:14,010
definitive venis en tre oportuna.

934
01:13:14,010 --> 01:13:21,780
Kaj havante ĉi idiomo por looping super aĵoj faros vivo multe pli facila, espereble.

935
01:13:21,780 --> 01:13:25,910
Demandojn, rapide?

936
01:13:25,910 --> 01:13:28,920
[Sam] Cxu vi sendu la kompletigis SLL kaj sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Mi sendas kompletigis diapozitivoj kaj kompletigita SLL pilo kaj queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]