1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Secció 6: menys còmode]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Aquesta és CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Està bé. Benvinguts a la secció 6.

5
00:00:11,840 --> 00:00:14,690
Aquesta setmana, estarem parlant d'estructures de dades a la secció,

6
00:00:14,690 --> 00:00:19,780
sobretot perquè el problema d'aquesta setmana estableix spellr

7
00:00:19,780 --> 00:00:24,410
fa un munt d'exploració estructures de dades.

8
00:00:24,410 --> 00:00:26,520
Hi ha un munt de maneres diferents que vostè pot anar amb el conjunt de problemes,

9
00:00:26,520 --> 00:00:31,570
i les estructures de dades més el coneixem, les coses més interessants que pots fer.

10
00:00:31,570 --> 00:00:34,990
>> Així que anem a començar. En primer lloc parlarem de les piles,

11
00:00:34,990 --> 00:00:37,530
les dades de la pila i la cua d'estructures que parlarem.

12
00:00:37,530 --> 00:00:40,560
Les piles i les cues són realment útils quan vam començar a parlar dels gràfics,

13
00:00:40,560 --> 00:00:44,390
que no farem molt d'aquests moments.

14
00:00:44,390 --> 00:00:52,820
Però són molt bons per entendre una de les grans estructures de dades fonamentals de la CS.

15
00:00:52,820 --> 00:00:54,880
La descripció de l'especificació conjunt de problemes,

16
00:00:54,880 --> 00:00:59,260
si estirar-lo cap amunt, parla de les piles com afí a

17
00:00:59,260 --> 00:01:05,239
la pila de safates de menjars que vostè té a la cafeteria als menjadors

18
00:01:05,239 --> 00:01:09,680
on quan el personal del menjador ve i posa les safates de sortir a sopar després d'haver-los netejat,

19
00:01:09,680 --> 00:01:12,000
que apilar un sobre l'altre.

20
00:01:12,000 --> 00:01:15,050
I després, quan els nens vénen a buscar menjar,

21
00:01:15,050 --> 00:01:19,490
tiren les safates de sortida, primer l'un i després la de baix, i després la de baix d'això.

22
00:01:19,490 --> 00:01:25,190
Així que, en efecte, la primera safata que el personal del menjador posar és l'últim que s'ha enlairat.

23
00:01:25,190 --> 00:01:32,330
L'últim que el personal del menjador posar és el primer que l'hi porten fora per al sopar.

24
00:01:32,330 --> 00:01:38,100
En el conjunt d'especificacions problema, que es pot descarregar si no ho ha fet,

25
00:01:38,100 --> 00:01:46,730
parlem de modelatge d'una pila stucture dades utilitzant aquest tipus d'estructura.

26
00:01:46,730 --> 00:01:51,070
>> Així que el que tenim aquí, això és similar al que es va presentar a la conferència,

27
00:01:51,070 --> 00:01:58,120
excepte en la conferència es van presentar amb aquest sencers en lloc de char * s.

28
00:01:58,120 --> 00:02:06,250
Això serà una pila que emmagatzema què?

29
00:02:06,250 --> 00:02:09,009
Daniel? Què estem emmagatzemant en aquesta pila?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Estem emmagatzemar les cadenes en aquesta pila, exactament.

31
00:02:15,260 --> 00:02:20,950
Tot el que ha de tenir per a crear una pila és una matriu

32
00:02:20,950 --> 00:02:23,920
d'una capacitat particular, que en aquest cas,

33
00:02:23,920 --> 00:02:28,020
capacitat serà tot en majúscules perquè és una constant.

34
00:02:28,020 --> 00:02:36,340
I a continuació, a més de la matriu, tot el que necessita per seguir és la mida actual de la matriu.

35
00:02:36,340 --> 00:02:38,980
Una cosa per notar aquí que és una espècie de fresc

36
00:02:38,980 --> 00:02:47,060
és que estem creant l'estructura de dades apilades una damunt d'una altra estructura de dades, la matriu.

37
00:02:47,060 --> 00:02:50,110
Hi ha diferents maneres d'implementar piles.

38
00:02:50,110 --> 00:02:54,250
No ho farem encara, però espero que després de fer els problemes de llista vinculada,

39
00:02:54,250 --> 00:03:00,520
veuràs el fàcil que és implementar una pila a la part superior d'una llista enllaçada també.

40
00:03:00,520 --> 00:03:02,640
Però per ara, anem a atenir-nos a les matrius.

41
00:03:02,640 --> 00:03:06,350
Així que de nou, tot el que necessitem és una matriu i només hem de seguir la mida de la matriu.

42
00:03:06,350 --> 00:03:09,850
[Sam] Em sap greu, com és que vostè va dir que la pila està per sobre de les cordes?

43
00:03:09,850 --> 00:03:13,440
A mi em sembla que les cadenes estan dins de la pila.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Estem creant, estem donant la nostra àmplia estructura de dades -

45
00:03:16,790 --> 00:03:22,130
aquesta és una gran pregunta. Llavors la pregunta és per què, per les persones que estan veient aquesta línia,

46
00:03:22,130 --> 00:03:24,140
Per què estem dient que la pila està per sobre de les cordes,

47
00:03:24,140 --> 00:03:27,990
perquè aquí sembla que les cordes estan a l'interior de la pila?

48
00:03:27,990 --> 00:03:31,050
La qual cosa és totalment el cas.

49
00:03:31,050 --> 00:03:34,660
El que em referia és que tenim una estructura de dades array.

50
00:03:34,660 --> 00:03:39,290
Tenim una matriu de char * s, aquesta matriu de cadenes,

51
00:03:39,290 --> 00:03:45,300
i que es va a afegir a la que per tal de crear l'estructura de dades apilats.

52
00:03:45,300 --> 00:03:48,620
>> Així que una pila és una mica més complex que una matriu.

53
00:03:48,620 --> 00:03:51,890
Podem utilitzar una matriu per construir una pila.

54
00:03:51,890 --> 00:03:55,810
Així que aquí és on diem que la pila es construeix a la part superior d'una matriu.

55
00:03:55,810 --> 00:04:02,510
De la mateixa manera, com he dit abans, podem construir una pila a la part superior d'una llista enllaçada.

56
00:04:02,510 --> 00:04:04,960
En lloc d'utilitzar una matriu per mantenir els nostres elements,

57
00:04:04,960 --> 00:04:10,070
podem utilitzar una llista enllaçada per mantenir els nostres elements i construir la pila del voltant d'això.

58
00:04:10,070 --> 00:04:12,420
Anem a veure un parell d'exemples, mirant una mica de codi,

59
00:04:12,420 --> 00:04:14,960
per veure el que realment està passant aquí.

60
00:04:14,960 --> 00:04:23,400
A l'esquerra, he tirat el que struct pila es veuria en la memòria

61
00:04:23,400 --> 00:04:28,330
si la capacitat es van definir # per ser quatre.

62
00:04:28,330 --> 00:04:33,490
Tenim els nostres quatre elements de matriu char *.

63
00:04:33,490 --> 00:04:38,110
Tenim cadenes [0], les cadenes [1], les cadenes [2], cadenes [3],

64
00:04:38,110 --> 00:04:43,800
i després de que l'espai per al nostre passat sencer mida.

65
00:04:43,800 --> 00:04:46,270
Té això sentit? Bé.

66
00:04:46,270 --> 00:04:48,790
Això és el que passa si el que faig a la dreta,

67
00:04:48,790 --> 00:04:55,790
que serà el meu codi, és declarar només una estructura, una estructura apilades anomenat s.

68
00:04:55,790 --> 00:05:01,270
Això és el que tenim. Estableix aquesta empremta en la memòria.

69
00:05:01,270 --> 00:05:05,590
La primera pregunta aquí és: quins són els continguts d'aquesta estructura de pila?

70
00:05:05,590 --> 00:05:09,250
Ara mateix no són res, però no són totalment res.

71
00:05:09,250 --> 00:05:13,300
Són aquest tipus d'escombraries. No tenim idea del que hi ha en ells.

72
00:05:13,300 --> 00:05:17,000
Quan declarem s de pila, només estem tirant a baix que a la part superior de la memòria.

73
00:05:17,000 --> 00:05:19,840
És com declarar int i, i no ho inicialitza.

74
00:05:19,840 --> 00:05:21,730
No sap el que hi ha. Vostè pot llegir el que hi ha allà,

75
00:05:21,730 --> 00:05:27,690
però potser no és molt servicial.

76
00:05:27,690 --> 00:05:32,680
Una de les coses que vol recordar sempre de fer és inicialitzar el que necessita ser inicialitzat.

77
00:05:32,680 --> 00:05:35,820
En aquest cas, anem a inicialitzar la mida sigui zero,

78
00:05:35,820 --> 00:05:39,960
perquè això arribarà a ser molt important per a nosaltres.

79
00:05:39,960 --> 00:05:43,450
Podríem seguir endavant i iniciar tots els punters, tot el s * char,

80
00:05:43,450 --> 00:05:49,670
a ser algun valor comprensible, probablement nul.

81
00:05:49,670 --> 00:05:58,270
Però no és del tot necessari que fem això.

82
00:05:58,270 --> 00:06:04,200
>> Ara, les dues operacions principals sobre les piles de veritat?

83
00:06:04,200 --> 00:06:07,610
Algú es recorda de la conferència que el que vostè fa amb les piles? Sí?

84
00:06:07,610 --> 00:06:09,700
[Stella] Empenyent i fent esclatar? >> Exactament.

85
00:06:09,700 --> 00:06:13,810
Empenyent i fent esclatar són les dues operacions principals de piles.

86
00:06:13,810 --> 00:06:17,060
I què empenta fer? >> Es posa alguna cosa a la part superior

87
00:06:17,060 --> 00:06:19,300
de la pila, i després salten el treu.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exactament. Així empenyent empeny una mica a la part superior de la pila.

89
00:06:23,150 --> 00:06:27,700
És com el personal del menjador posant una safata de menjar al taulell.

90
00:06:27,700 --> 00:06:33,630
I fer esclatar està prenent una safata de sopar de la pila.

91
00:06:33,630 --> 00:06:36,460
Anem a veure un parell d'exemples del que succeeix

92
00:06:36,460 --> 00:06:39,720
quan empenyem les coses a la pila.

93
00:06:39,720 --> 00:06:45,110
Si anéssim a empènyer la cadena 'hola' al nostre stack,

94
00:06:45,110 --> 00:06:49,760
això és el que el nostre diagrama es veuria ara.

95
00:06:49,760 --> 00:06:53,410
Mireu el que passa?

96
00:06:53,410 --> 00:06:56,530
Ens introdueix en el primer element de la nostra àmplia cordes

97
00:06:56,530 --> 00:07:01,420
i ens va pujar el nostre recompte mida és 1.

98
00:07:01,420 --> 00:07:05,340
Així que si ens fixem en la diferència entre les dues corredisses, aquí va ser de 0, és a dir abans de la inserció.

99
00:07:05,340 --> 00:07:08,690
Aquí està després de la inserció.

100
00:07:08,690 --> 00:07:13,460
Abans de la inserció, després de la inserció.

101
00:07:13,460 --> 00:07:16,860
I ara tenim un element de la nostra pila.

102
00:07:16,860 --> 00:07:20,970
És la cadena "hola", i això és tot.

103
00:07:20,970 --> 00:07:24,440
Tota la resta a la matriu, en el nostre array de cadenes, segueix sent escombraries.

104
00:07:24,440 --> 00:07:27,070
No ho hem inicialitzat.

105
00:07:27,070 --> 00:07:29,410
Diguem que empènyer altra cadena al nostre stack.

106
00:07:29,410 --> 00:07:32,210
Anem a empènyer "món" en aquest moment.

107
00:07:32,210 --> 00:07:35,160
Així que vostè pot veure "món" aquí va sobre de "hola",

108
00:07:35,160 --> 00:07:40,040
i el recompte de mida puja a 2.

109
00:07:40,040 --> 00:07:44,520
Ara podem empènyer "CS50", i que anirà a la part superior de nou.

110
00:07:44,520 --> 00:07:51,110
Si retrocedim, es pot veure com estem portant les coses a la part superior de la pila.

111
00:07:51,110 --> 00:07:53,320
I ara arribem al pop.

112
00:07:53,320 --> 00:07:58,910
Quan ens vam anar una mica fora de la pila, què va passar?

113
00:07:58,910 --> 00:08:01,540
Algú veu la diferència? És molt subtil.

114
00:08:01,540 --> 00:08:05,810
[Estudiant] La mida. >> Sí, la mida canviat.

115
00:08:05,810 --> 00:08:09,040
>> Què més es pot esperar per al canvi?

116
00:08:09,040 --> 00:08:14,280
[Estudiants] Les cordes, també. >> Dret. Les cordes també.

117
00:08:14,280 --> 00:08:17,110
Resulta que quan ho fas d'aquesta manera,

118
00:08:17,110 --> 00:08:21,960
perquè no estem copiant els elements al nostre stack,

119
00:08:21,960 --> 00:08:24,670
que en realitat no ha de fer res, només podem utilitzar la mida

120
00:08:24,670 --> 00:08:28,630
fer un seguiment de la quantitat de coses en la nostra àmplia

121
00:08:28,630 --> 00:08:33,780
perquè quan aparegui de nou, de nou només disminuir el nostre mida a 1.

122
00:08:33,780 --> 00:08:39,440
No cal anar en realitat en i sobreescriure qualsevol cosa.

123
00:08:39,440 --> 00:08:41,710
Una mica funky.

124
00:08:41,710 --> 00:08:46,520
Resulta que solem deixar les coses només perquè és menys treball per a nosaltres.

125
00:08:46,520 --> 00:08:50,060
Si no hem de tornar enrere i sobreescriure alguna cosa, llavors per què fer-ho?

126
00:08:50,060 --> 00:08:54,150
Així, quan aparegui el doble de la pila, l'únic que fa és disminuir la mida d'un parell de vegades.

127
00:08:54,150 --> 00:08:59,120
I un cop més, això és només perquè no estem copiant coses al nostre stack.

128
00:08:59,120 --> 00:09:01,320
Sí? Endavant.

129
00:09:01,320 --> 00:09:04,460
[Estudiant, inintel · ligible] >> I llavors, què passa quan vostè empeny alguna cosa nova?

130
00:09:04,460 --> 00:09:08,570
Quan es prem alguna cosa nova, on va?

131
00:09:08,570 --> 00:09:12,390
On va, Basil? En cadenes >> [1]? >> Dret.

132
00:09:12,390 --> 00:09:14,530
Per què no anar a cadenes [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] A causa que es va oblidar que havia alguna cosa en les cadenes [1] i [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exactament. La nostra pila, en essència, "es va oblidar" que s'aferra a qualsevol cosa

135
00:09:24,040 --> 00:09:29,480
a les cadenes [1] o cadenes [2], així que quan ens empenyen "woot"

136
00:09:29,480 --> 00:09:36,670
només posa això en l'element en cadenes [1].

137
00:09:36,670 --> 00:09:41,590
Hi ha alguna pregunta sobre com funciona això, a un nivell bàsic?

138
00:09:41,590 --> 00:09:45,160
[Sam] Així que això no és de cap manera dinàmica, en termes de quantitat

139
00:09:45,160 --> 00:09:47,620
o en termes de la mida de la pila?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exactament. Això és - el punt era que no es tractava d'una pila dinàmica growning.

141
00:09:56,750 --> 00:10:02,850
Aquesta és una pila que pot contenir, com a màxim, quatre char * s, en la majoria de quatre coses.

142
00:10:02,850 --> 00:10:07,580
Si fóssim a tractar d'empènyer 1/5 cosa, què creu vostè que hauria de passar?

143
00:10:07,580 --> 00:10:11,870
[Els estudiants], inintel · ligibles

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exactament. Hi ha una sèrie de coses que podrien succeir.

145
00:10:14,600 --> 00:10:19,330
Possiblement podria seg culpa, depenent del que eren -

146
00:10:19,330 --> 00:10:22,530
Com és exactament el que estaven executant el back-end.

147
00:10:22,530 --> 00:10:31,740
Pot sobreescriure. Podria haver de desbordament de memòria intermèdia que parlem a classe.

148
00:10:31,740 --> 00:10:35,240
Quina seria la cosa més òbvia que pot ser sobrescriptura

149
00:10:35,240 --> 00:10:42,370
si tractem d'empènyer alguna cosa extra en la nostra pila?

150
00:10:42,370 --> 00:10:44,550
Així que vostè ha esmentat un desbordament de memòria intermèdia.

151
00:10:44,550 --> 00:10:47,870
Quina podria ser la cosa que s'escriuen sobre o trepitjar

152
00:10:47,870 --> 00:10:52,320
si ens va desbordar accidentalment en tractar d'empènyer una cosa extra?

153
00:10:52,320 --> 00:10:54,730
[Daniel, inintel · ligible] >> Possible.

154
00:10:54,730 --> 00:10:58,440
Però inicialment, el que podria passar? Què passa si tractem d'empènyer 1/4 cosa?

155
00:10:58,440 --> 00:11:06,220
Pot sobreescriure la mida, si més no amb aquest esquema de memòria que tenim.

156
00:11:06,220 --> 00:11:10,880
>> En l'especificació conjunt de problemes, que és el que estarem implementant avui en dia,

157
00:11:10,880 --> 00:11:16,030
el que vull fer és tornar false.

158
00:11:16,030 --> 00:11:20,030
El nostre mètode d'empenta es va a tornar un valor booleà,

159
00:11:20,030 --> 00:11:22,920
i que el valor booleà serà vertadera si l'empenta èxit

160
00:11:22,920 --> 00:11:29,730
i fals si no podem empènyer més res perquè la pila està plena.

161
00:11:29,730 --> 00:11:33,620
Anem a veure una mica d'aquest codi en aquests moments.

162
00:11:33,620 --> 00:11:36,400
Aquesta és la nostra funció push.

163
00:11:36,400 --> 00:11:40,380
La nostra funció push per una pila es prendrà en la cadena per posar a la pila.

164
00:11:40,380 --> 00:11:45,820
Es tornarà true si la cadena va ser empès amb èxit

165
00:11:45,820 --> 00:11:51,820
d'una altra manera a la pila i la falsedat.

166
00:11:51,820 --> 00:11:59,740
Alguna suggeriment sobre el que podria ser una bona cosa primer que hem de fer aquí?

167
00:11:59,740 --> 00:12:20,630
[Sam] Si la mida és igual a la capacitat de retornar false llavors?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Bon treball.

169
00:12:23,320 --> 00:12:26,310
Si la mida és la capacitat, tornarem false.

170
00:12:26,310 --> 00:12:29,270
No podem posar res més en la nostra pila.

171
00:12:29,270 --> 00:12:36,900
En cas contrari, volem posar alguna cosa a la part superior de la pila.

172
00:12:36,900 --> 00:12:41,670
Què és "la part superior de la pila," inicialment?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Mida 0? Mida >> 0.

174
00:12:43,650 --> 00:12:49,990
Quina és la part superior de la pila després hi ha una cosa a la pila? Missy, saps?

175
00:12:49,990 --> 00:12:52,720
[Missy] Una. Mida >> és un, exactament. Vostè mantenir l'addició a la mida,

176
00:12:52,720 --> 00:13:01,690
i cada vegada que s'està posant en el nou element en la mida de l'índex en la matriu.

177
00:13:01,690 --> 00:13:05,470
Ho podem fer amb aquest tipus d'una sola línia, si això té sentit.

178
00:13:05,470 --> 00:13:11,910
Així que tenim la nostra matriu de cadenes, anem a accedir-hi en l'índex de mida,

179
00:13:11,910 --> 00:13:14,780
i només anem a guardar el nostre char * en aquest país.

180
00:13:14,780 --> 00:13:19,340
Cal notar com hi ha cap còpia corda passant aquí,

181
00:13:19,340 --> 00:13:29,680
no assignació dinàmica de la memòria?

182
00:13:29,680 --> 00:13:34,440
I després Missy criat el que ara hem de fer,

183
00:13:34,440 --> 00:13:40,570
perquè hem guardat la cadena al lloc apropiat en la matriu,

184
00:13:40,570 --> 00:13:49,230
i ella em va dir que calia augmentar la mida d'una manera que estem preparats per la següent pulsació.

185
00:13:49,230 --> 00:13:53,950
Així que podem fer això amb s.size + +.

186
00:13:53,950 --> 00:13:59,330
En aquest punt, hem empès a la nostra matriu. Què és l'últim que hem de fer?

187
00:13:59,330 --> 00:14:10,110
[Estudiant] Retorna true. >> Tornar veritat.

188
00:14:10,110 --> 00:14:14,690
Per tant és simple, un codi bastant simple. No massa.

189
00:14:14,690 --> 00:14:17,070
Una vegada que ha embolicat el cap al voltant de com funciona la pila,

190
00:14:17,070 --> 00:14:21,910
això és bastant senzill d'implementar.

191
00:14:21,910 --> 00:14:26,390
>> Ara, la següent part d'aquesta està apareixent una cadena de la pila.

192
00:14:26,390 --> 00:14:29,410
Vaig a donar vostès una mica de temps per treballar en això una mica.

193
00:14:29,410 --> 00:14:34,320
És gairebé essencialment el contrari del que hem fet aquí en empenta.

194
00:14:34,320 --> 00:14:38,510
El que he fet és en realitat - oops.

195
00:14:38,510 --> 00:14:48,160
He arrencat un aparell per aquí, i en l'aparell,

196
00:14:48,160 --> 00:14:53,600
He tirat el problema conjunt 5 especificació.

197
00:14:53,600 --> 00:15:02,560
Si el zoom aquí, podem veure que estic en cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Han descarregat el codi que es troba aquí, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Està bé. Si vostè no ha fet això, fes allò en aquest moment, molt ràpid.

200
00:15:15,030 --> 00:15:22,130
Ho faré en la meva finestra de terminal.

201
00:15:22,130 --> 00:15:25,090
De fet, m'ho va fer aquí. Si.

202
00:15:25,090 --> 00:15:34,730
Sí, Sam? >> Tinc una pregunta sobre per què li vas dir s.string 's suports de mida = str?

203
00:15:34,730 --> 00:15:42,910
Quin és str? És el definit abans en algun lloc, o - oh, en la xerrada * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Sí, exactament. Aquest va ser l'argument. >> Oh, està bé. Em sap greu.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Estem especificar la cadena d'empènyer polz

206
00:15:49,470 --> 00:15:55,220
L'altra qüestió que pugui sorgir que realment no parlar d'aquí va ser

207
00:15:55,220 --> 00:15:58,810
es donava per fet que vam tenir aquesta variable anomenada s

208
00:15:58,810 --> 00:16:02,710
que era en el seu abast i accessible per a nosaltres.

209
00:16:02,710 --> 00:16:06,960
Ens van donar per fet que era aquest es struct pila.

210
00:16:06,960 --> 00:16:08,930
Així que mirant cap enrere en el codi d'inserció,

211
00:16:08,930 --> 00:16:13,450
es pot veure que estem fent coses amb aquesta cadena que va quedar aprovada en

212
00:16:13,450 --> 00:16:19,210
però després, de sobte, estem accedint s.size, com, d'on provenen de s?

213
00:16:19,210 --> 00:16:23,020
En el codi que veurem a l'arxiu de la secció

214
00:16:23,020 --> 00:16:27,100
i llavors les coses que vostè farà en el seu problema es posa,

215
00:16:27,100 --> 00:16:32,440
hem fet la nostra pila struct una variable global

216
00:16:32,440 --> 00:16:36,380
perquè puguem tenir accés a totes les nostres funcions diferents

217
00:16:36,380 --> 00:16:40,630
sense haver de passar manualment voltant i passar-ho per referència,

218
00:16:40,630 --> 00:16:44,870
fer tot aquest tipus de coses a ella.

219
00:16:44,870 --> 00:16:52,280
Només estem enganyant una mica, si es vol, per fer les coses millor.

220
00:16:52,280 --> 00:16:57,430
I això és una cosa que estem fent aquí perquè és per diversió, és més fàcil.

221
00:16:57,430 --> 00:17:02,800
Sovint, vostè veurà la gent fa això si tenen una estructura de dades gran

222
00:17:02,800 --> 00:17:07,750
que està sent operat dins del seu programa.

223
00:17:07,750 --> 00:17:09,560
>> Anem a anar de nou cap a l'aparell.

224
00:17:09,560 --> 00:17:15,240
Tots amb èxit obtenir el section6.zip?

225
00:17:15,240 --> 00:17:20,440
Tothom ho descomprimeixi utilitzant section6.zip descomprimir?

226
00:17:20,440 --> 00:17:27,200
Si entra a la secció 6 del directori -

227
00:17:27,200 --> 00:17:29,220
aah, per tot el lloc -

228
00:17:29,220 --> 00:17:32,840
i una llista del que hi ha aquí, es veu que tens tres arxius diferents. c.

229
00:17:32,840 --> 00:17:38,350
Vostè té una cua, una sll, que és la llista simplement enllaçada, i una pila.

230
00:17:38,350 --> 00:17:44,600
Si obre stack.c,

231
00:17:44,600 --> 00:17:47,330
es pot veure que tenim aquesta estructura definida per nosaltres,

232
00:17:47,330 --> 00:17:51,330
l'estructura exacta que acabem de parlar en les diapositives.

233
00:17:51,330 --> 00:17:56,340
Tenim la nostra variable global de la pila,

234
00:17:56,340 --> 00:18:00,110
tenim la nostra funció push,

235
00:18:00,110 --> 00:18:04,230
i després tenim la nostra funció pop.

236
00:18:04,230 --> 00:18:08,320
Vaig a posar el codi per fer retrocedir a la diapositiva aquí,

237
00:18:08,320 --> 00:18:10,660
però el que m'agradaria que vostès fan és, potser de la seva capacitat,

238
00:18:10,660 --> 00:18:13,790
anar i posar en pràctica la funció pop.

239
00:18:13,790 --> 00:18:18,480
Quan hagueu posat en pràctica, pot compilar amb make aquesta pila,

240
00:18:18,480 --> 00:18:22,540
a continuació, executeu el fitxer executable pila resultant,

241
00:18:22,540 --> 00:18:28,390
i que s'estendrà tot aquest codi de prova aquí que està en principal.

242
00:18:28,390 --> 00:18:31,060
I principal s'encarrega realment de fer el push i pop trucades

243
00:18:31,060 --> 00:18:33,220
i assegurar-se que tot va a través de tot dret.

244
00:18:33,220 --> 00:18:36,820
També s'inicialitza la mida de la pila aquí

245
00:18:36,820 --> 00:18:39,780
per la qual cosa no ha de preocupar-se que la inicialització.

246
00:18:39,780 --> 00:18:42,310
Es pot suposar que ha estat correctament inicialitzat

247
00:18:42,310 --> 00:18:48,000
en el moment en què s'accedeix a la funció pop.

248
00:18:48,000 --> 00:18:53,530
Això té sentit?

249
00:18:53,530 --> 00:19:00,100
Així que aquí anem. Aquí està el codi d'inserció.

250
00:19:00,100 --> 00:19:13,210
Vaig a donar-vos 5 o 10 minuts.

251
00:19:13,210 --> 00:19:15,690
I si vostè té alguna pregunta en el interí mentre estàs codificació,

252
00:19:15,690 --> 00:19:17,710
si us plau pregunteu en veu alta.

253
00:19:17,710 --> 00:19:23,080
Així que si s'arriba a un punt d'estancament, només pregunti.

254
00:19:23,080 --> 00:19:26,030
Deixa saber, que tothom sap.

255
00:19:26,030 --> 00:19:28,160
Treballi amb el seu veí també.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Estem implementació pop en aquest moment? >> Just pop.

257
00:19:30,360 --> 00:19:34,200
Encara que vostè pot copiar l'aplicació d'empenta si voleu

258
00:19:34,200 --> 00:19:37,780
de manera que la prova funcionarà.

259
00:19:37,780 --> 00:19:41,940
Com que és difícil provar que les coses es a -

260
00:19:41,940 --> 00:19:49,030
o, és difícil de provar coses que fan esclatar fora d'una pila si no hi ha res a la pila, per començar.

261
00:19:49,030 --> 00:19:55,250
>> Què és el pop suposa que es repeteixin? L'element de la part superior de la pila.

262
00:19:55,250 --> 00:20:01,260
Se suposa que per obtenir l'element fora de la part superior de la pila

263
00:20:01,260 --> 00:20:05,780
i després disminuir la mida de la pila,

264
00:20:05,780 --> 00:20:07,810
i ara que ha perdut l'element en la part superior.

265
00:20:07,810 --> 00:20:11,420
I tan bon punt torni l'element en la part superior.

266
00:20:11,420 --> 00:20:20,080
[Estudiant, inintel · ligible]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Llavors, què passa si es fa això? [Estudiant, inintel · ligible]

268
00:20:28,810 --> 00:20:34,000
El que acaba passant és que estàs probablement per accedir a qualsevol dels dos

269
00:20:34,000 --> 00:20:37,350
un element que no s'ha inicialitzat encara, de manera que el seu càlcul

270
00:20:37,350 --> 00:20:39,990
d'on l'últim element és està apagat.

271
00:20:39,990 --> 00:20:46,260
Així que aquí, si et fixes, en l'impuls, estem accedint cadenes en l'element s.size

272
00:20:46,260 --> 00:20:48,560
perquè es tracta d'un nou índex.

273
00:20:48,560 --> 00:20:51,460
És el nou límit de la pila.

274
00:20:51,460 --> 00:21:01,100
Mentre que en el pop, s.size serà el següent espai,

275
00:21:01,100 --> 00:21:05,210
L'espai que hi ha a la part superior de tots els elements de la pila.

276
00:21:05,210 --> 00:21:10,050
De manera que l'element de més amunt no és s.size,

277
00:21:10,050 --> 00:21:14,930
sinó més aviat, que està sota.

278
00:21:14,930 --> 00:21:19,640
>> L'altra cosa que fer quan - en el pop,

279
00:21:19,640 --> 00:21:22,030
se li ha de disminuir la mida.

280
00:21:22,030 --> 00:21:28,750
Si vostè recorda de nou al nostre petit diagrama aquí,

281
00:21:28,750 --> 00:21:30,980
en realitat, l'únic que vam veure passant quan diem pop

282
00:21:30,980 --> 00:21:36,150
era que aquesta mida disminuït, primer a 2, i després a 1.

283
00:21:36,150 --> 00:21:42,620
Després, quan va empènyer un nou element en endavant, seguiria al lloc adequat.

284
00:21:42,620 --> 00:21:49,610
[Basil] Si el s.size és 2, llavors no seria anar a l'element 2,

285
00:21:49,610 --> 00:21:54,400
i després que t'agradaria fer esclatar aquest element fora?

286
00:21:54,400 --> 00:21:59,510
Així que si ens vam anar a - >> Així que donem una ullada a això de nou.

287
00:21:59,510 --> 00:22:07,730
Si aquesta és la nostra pila en aquest punt

288
00:22:07,730 --> 00:22:12,130
i anomenem pop,

289
00:22:12,130 --> 00:22:16,150
en què índex és l'element de més amunt?

290
00:22:16,150 --> 00:22:19,300
[Basil] Als 2, però apareixerà 3. >> Dret.

291
00:22:19,300 --> 00:22:24,220
Així que aquí és on el nostre mida és 3, però volem fer esclatar l'element en l'índex 2.

292
00:22:24,220 --> 00:22:29,900
És aquest tipus típic d'apagat per una que vostè té amb el zero de la indexació d'arrays.

293
00:22:29,900 --> 00:22:36,430
Així que vostè vol ficar el tercer element, però el tercer element no està en l'índex 3.

294
00:22:36,430 --> 00:22:39,430
I la raó per la qual no has de fer això menys 1 quan estem empenyent

295
00:22:39,430 --> 00:22:44,120
és perquè ara mateix, t'adones que l'element de més amunt,

296
00:22:44,120 --> 00:22:47,600
si eren per empènyer una mica més a la pila en aquest punt,

297
00:22:47,600 --> 00:22:50,360
ens agradaria que empènyer en l'índex 3.

298
00:22:50,360 --> 00:23:03,550
I dóna la casualitat que la mida i els índexs alineats quan vostè està empenyent.

299
00:23:03,550 --> 00:23:06,960
>> Qui té una implementació de la pila de treball?

300
00:23:06,960 --> 00:23:09,690
Tens un munt de treball un. Té pop treballant encara?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Sí Crec que sí.

302
00:23:11,890 --> 00:23:14,610
Programa >> està corrent i no segons fallamiento, s'imprimeixi?

303
00:23:14,610 --> 00:23:17,520
¿S'imprimirà l '"èxit" quan s'executa?

304
00:23:17,520 --> 00:23:22,630
Si. Fer apilar, executar, si imprimeix el "èxit" i no va boom,

305
00:23:22,630 --> 00:23:26,000
llavors tot està bé.

306
00:23:26,000 --> 00:23:34,070
Està bé. Anem a repassar l'aparell molt ràpid,

307
00:23:34,070 --> 00:23:46,100
i anem a caminar a través d'aquest.

308
00:23:46,100 --> 00:23:51,110
Si ens fixem en el que està passant aquí amb el pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, què va ser el primer que vas fer?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Si s.size és més gran que 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Bé. I per què has fet això?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Per assegurar que hi havia alguna cosa dins de la pila.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Dret. Vols posar a prova per assegurar-se que s.size és més gran que 0;

314
00:24:10,950 --> 00:24:13,280
en cas contrari, què vols que passi?

315
00:24:13,280 --> 00:24:16,630
[Daniel] null retorn? Nul >> Retorn, exactament.

316
00:24:16,630 --> 00:24:20,740
Així que si s.size és més gran que 0. Llavors, què farem?

317
00:24:20,740 --> 00:24:25,890
Què fem si la pila no és buida?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vostè disminuir la mida? >> Vostè disminuir la mida, està bé.

319
00:24:31,210 --> 00:24:34,440
Llavors, com has fet això? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. I llavors, què vas fer?

321
00:24:37,030 --> 00:24:44,140
[Stella] I llavors em va dir que el retorn s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
En cas contrari, retorna null. Sí, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Per què no ho necessita per ser s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Sí >>. >> Ho tinc.

326
00:24:58,430 --> 00:25:00,980
[Sam] vaig pensar perquè vostè pren amb 1,

327
00:25:00,980 --> 00:25:04,290
llavors vostè va a tornar no és el que ells van demanar.

328
00:25:04,290 --> 00:25:09,400
[Hardison] I això era just el que estàvem parlant amb tot aquest tema de 0 índexs.

329
00:25:09,400 --> 00:25:11,380
Així que si amplia aquí.

330
00:25:11,380 --> 00:25:15,650
Si ens fixem en aquest tipus aquí, es pot veure que quan el pop,

331
00:25:15,650 --> 00:25:19,340
estem fent esclatar l'element d'índex 2.

332
00:25:19,340 --> 00:25:25,200
>> Per tant, disminuir la grandària de la nostra primera, llavors el nostre mida coincideix amb el nostre índex.

333
00:25:25,200 --> 00:25:39,650
Si no disminuir la mida de la primera, llavors hem de veure mida -1 i decrement.

334
00:25:39,650 --> 00:25:45,270
Gran. ¿Tot bé?

335
00:25:45,270 --> 00:25:47,530
Teniu alguna pregunta respecte això?

336
00:25:47,530 --> 00:25:54,050
Hi ha un nombre de formes diferents d'escriure això.

337
00:25:54,050 --> 00:26:03,290
De fet, podem fer alguna cosa encara - podem fer una sola línia.

338
00:26:03,290 --> 00:26:05,770
Podem fer una declaració d'una línia.

339
00:26:05,770 --> 00:26:12,980
Així que en realitat pot disminuir abans que tornem a fer-ho.

340
00:26:12,980 --> 00:26:18,320
Així que posar el - abans de la s.size.

341
00:26:18,320 --> 00:26:22,060
Això fa que la línia realment dens.

342
00:26:22,060 --> 00:26:30,940
Quan la diferència entre el -. S mida i s.size--

343
00:26:30,940 --> 00:26:40,130
és que aquest sufix - en diuen perquè el sufix - ve després de la s.size--

344
00:26:40,130 --> 00:26:47,430
significa que s.size s'avalua als efectes de trobar l'índex

345
00:26:47,430 --> 00:26:50,410
com ho és en l'actualitat quan s'executa aquesta línia,

346
00:26:50,410 --> 00:26:54,290
i després això - que succeeix després de la línia s'executa.

347
00:26:54,290 --> 00:27:00,340
Després que l'element en s.size índex s'accedeix.

348
00:27:00,340 --> 00:27:07,260
I això no és el que volem, perquè volem que el decrement que succeeixi primer.

349
00:27:07,260 --> 00:27:10,990
Othewise, estarem accedint a la matriu, efectivament, fora del camp.

350
00:27:10,990 --> 00:27:16,850
Estarem accedint a l'element superior a la que realment vol accedir.

351
00:27:16,850 --> 00:27:23,840
Sí, Sam? >> És més ràpid i utilitza menys memòria RAM per fer en una sola línia o no?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Honestament, realment depèn.

353
00:27:29,620 --> 00:27:34,220
[Sam, inintel · ligible] >> Sí, depèn. Vostè pot fer trucs de compilació

354
00:27:34,220 --> 00:27:41,580
per obtenir el compilador de reconèixer que, en general, m'imagino.

355
00:27:41,580 --> 00:27:44,840
>> Per això hem esmentat una mica sobre aquestes coses optimització del compilador

356
00:27:44,840 --> 00:27:47,400
que es pot fer en la recopilació,

357
00:27:47,400 --> 00:27:50,580
i aquest és el tipus de cosa que un compilador pot ser capaç d'entendre,

358
00:27:50,580 --> 00:27:54,710
com oh, hey, potser pugui fer tot això en una sola operació,

359
00:27:54,710 --> 00:27:59,420
en oposició a la càrrega de la variable en grandària de RAM,

360
00:27:59,420 --> 00:28:03,770
decreixent, emmagatzemant a sortir, i després torneu a carregar

361
00:28:03,770 --> 00:28:08,000
per processar la resta d'aquesta operació.

362
00:28:08,000 --> 00:28:10,710
Però en general, no, aquest no és el tipus de coses

363
00:28:10,710 --> 00:28:20,770
que farà el seu programa molt més ràpid.

364
00:28:20,770 --> 00:28:26,000
Alguna pregunta més sobre les piles?

365
00:28:26,000 --> 00:28:31,360
>> Així que empènyer i fer esclatar. Si vostès volen provar l'edició pirata informàtic,

366
00:28:31,360 --> 00:28:33,660
el que hem fet en l'edició pirata és en realitat anat

367
00:28:33,660 --> 00:28:37,670
i van fer d'aquesta pila de créixer de forma dinàmica.

368
00:28:37,670 --> 00:28:43,190
El repte no és principalment aquí a la funció push,

369
00:28:43,190 --> 00:28:48,820
per trobar la manera de fer créixer aquesta matriu

370
00:28:48,820 --> 00:28:52,450
a mesura de seguir empenyent més i més elements a la pila.

371
00:28:52,450 --> 00:28:56,000
En realitat no és un codi addicional en excés.

372
00:28:56,000 --> 00:29:00,080
Només una crida a - vostè ha de recordar per aconseguir les trucades a malloc aquí correctament,

373
00:29:00,080 --> 00:29:03,310
i després esbrinar quan dirà realloc.

374
00:29:03,310 --> 00:29:06,090
Això és un repte divertit si t'interessa.

375
00:29:06,090 --> 00:29:11,550
>> Però de moment, seguirem endavant, i parlarem de les cues.

376
00:29:11,550 --> 00:29:15,680
Desplaceu-vos per aquí.

377
00:29:15,680 --> 00:29:19,340
La cua és un germà prop de la pila.

378
00:29:19,340 --> 00:29:25,380
Així que a la pila, les coses que es van posar en última

379
00:29:25,380 --> 00:29:28,810
van ser les primeres coses per després ser recuperats.

380
00:29:28,810 --> 00:29:33,600
Tenim aquest últim a entrar, primer en sortir, o UEPS, fer la comanda.

381
00:29:33,600 --> 00:29:38,390
Mentre que a la cua, com era d'esperar a partir de quan s'està de peu a la fila,

382
00:29:38,390 --> 00:29:41,980
la primera persona que entra a la línia, el primer que ha d'entrar en la cua,

383
00:29:41,980 --> 00:29:47,630
és el primer que es recupera de la cua.

384
00:29:47,630 --> 00:29:51,490
Les cues també s'utilitza sovint quan estem tractant amb gràfics,

385
00:29:51,490 --> 00:29:55,560
com hem parlat breument amb piles,

386
00:29:55,560 --> 00:30:00,260
i les cues també són útils per a un munt d'altres coses.

387
00:30:00,260 --> 00:30:06,180
Una cosa que sorgeix sovint està tractant de mantenir, per exemple,

388
00:30:06,180 --> 00:30:12,310
una llista ordenada d'elements.

389
00:30:12,310 --> 00:30:17,650
I vostè pot fer això amb una matriu. Pot mantenir una llista ordenada de les coses en una matriu,

390
00:30:17,650 --> 00:30:20,650
però en els que es complica és llavors sempre cal trobar

391
00:30:20,650 --> 00:30:26,160
el lloc adequat per a inserir la cosa.

392
00:30:26,160 --> 00:30:28,250
Així que si vostè té una matriu de nombres, de l'1 al 10,

393
00:30:28,250 --> 00:30:31,630
i després vol ampliar això a tots els números d'1 a 100,

394
00:30:31,630 --> 00:30:33,670
i que està rebent aquests números en ordre aleatori i tractant de mantenir tot

395
00:30:33,670 --> 00:30:40,650
ordenats a mesura que avança, vostè acaba damunt d'haver de fer un munt de canvi.

396
00:30:40,650 --> 00:30:43,910
Amb certs tipus de cues i certs tipus d'estructures de dades subjacents,

397
00:30:43,910 --> 00:30:46,670
en realitat es pot mantenir bastant simple.

398
00:30:46,670 --> 00:30:50,640
No ha d'afegir alguna cosa i després estudiar la cosa sencera cada vegada.

399
00:30:50,640 --> 00:30:56,770
Tampoc cal fer un munt de desplaçament dels elements interns a la rodona.

400
00:30:56,770 --> 00:31:02,990
Quan ens fixem en una cua, es veu que - també en queue.c en el codi de secció -

401
00:31:02,990 --> 00:31:10,950
l'estructura que li hem donat és molt similar a l'estructura que li va donar per a una pila.

402
00:31:10,950 --> 00:31:13,770
>> Hi ha una excepció a això, i que una excepció

403
00:31:13,770 --> 00:31:21,700
és que tenim aquest sencer addicional diu el cap,

404
00:31:21,700 --> 00:31:28,120
i el cap aquí és per fer el seguiment del cap de la cua,

405
00:31:28,120 --> 00:31:32,160
o el primer element a la cua.

406
00:31:32,160 --> 00:31:37,470
Amb una pila, hem estat capaços de fer un seguiment dels elements que estàvem a punt de recuperar,

407
00:31:37,470 --> 00:31:40,800
o la part superior de la pila, utilitzant només la mida,

408
00:31:40,800 --> 00:31:44,220
mentre que amb una cua, haurem de bregar amb els extrems oposats.

409
00:31:44,220 --> 00:31:49,000
Estem tractant de virar les coses en al final, però després tornen les coses de front.

410
00:31:49,000 --> 00:31:54,640
Així que efectivament, amb el cap, que té l'índex del principi de la cua,

411
00:31:54,640 --> 00:31:58,920
i la mida ens dóna l'índex del final de la cua

412
00:31:58,920 --> 00:32:03,730
perquè puguem recuperar les coses del cap i afegir coses a la cua.

413
00:32:03,730 --> 00:32:06,890
Mentre que amb la pila, només estàvem mai tractar amb la part superior de la pila.

414
00:32:06,890 --> 00:32:08,900
Mai vam haver accedir a la part inferior de la pila.

415
00:32:08,900 --> 00:32:12,220
Només afegeix coses al cim i va prendre les coses fora de la part superior

416
00:32:12,220 --> 00:32:17,470
així que no necessito aquest camp addicional a l'interior del nostre struct.

417
00:32:17,470 --> 00:32:20,590
Això generalment té sentit?

418
00:32:20,590 --> 00:32:27,670
Està bé. Sí, Charlotte? [Charlotte, inintel · ligible]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Això és una gran pregunta, i que va ser el que va ocórrer en la conferència.

420
00:32:32,660 --> 00:32:36,290
Potser caminant a través d'alguns exemples que il · lustren per què

421
00:32:36,290 --> 00:32:41,400
no volem utilitzar cadenes [0] com el cap de la cua.

422
00:32:41,400 --> 00:32:46,770
>> Així que imaginin que tenim la nostra cua, anem a dir-cua.

423
00:32:46,770 --> 00:32:49,210
Al principi, quan acabo d'instància,

424
00:32:49,210 --> 00:32:53,330
quan acabem del declarat, no hem inicialitzat res.

425
00:32:53,330 --> 00:32:56,790
És tot escombraries. Així que, per descomptat, volem estar segurs que inicialitzar

426
00:32:56,790 --> 00:33:00,950
tant la mida i els camps de cap a ser 0, alguna cosa raonable.

427
00:33:00,950 --> 00:33:05,770
També podríem seguir endavant i nuls els elements en la nostra cua.

428
00:33:05,770 --> 00:33:09,930
I per fer aquest ajust diagrama, noti que ara la nostra cua només pot contenir tres elements;

429
00:33:09,930 --> 00:33:13,150
mentre que la nostra pila podria tenir quatre, la nostra cua només pot tenir tres.

430
00:33:13,150 --> 00:33:18,680
I això és només per fer l'ajust diagrama.

431
00:33:18,680 --> 00:33:26,150
El primer que passa aquí és que encolar la cadena "hola".

432
00:33:26,150 --> 00:33:30,380
I de la mateixa manera que vam fer amb la pila, res terriblement diferent aquí,

433
00:33:30,380 --> 00:33:39,230
tirem la corda de les cordes [0] i augmentar el nostre grandària en 1.

434
00:33:39,230 --> 00:33:42,720
Ens encolar "bye", aconsegueix posar.

435
00:33:42,720 --> 00:33:45,870
Per tant això s'assembla a una pila en la seva major part.

436
00:33:45,870 --> 00:33:53,230
Comencem aquí, nou element, l'element nou, la mida segueix pujant.

437
00:33:53,230 --> 00:33:56,330
Què passa en aquest moment en què volem treure de la cua alguna cosa?

438
00:33:56,330 --> 00:34:01,280
Quan volem treure de la cua, que és l'element que volem treure de la cua?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Exactament, Basil.

440
00:34:04,110 --> 00:34:10,960
Volem desfer de la primera cadena, aquest "hola".

441
00:34:10,960 --> 00:34:13,170
Llavors, ¿quina era l'altra cosa que ha canviat?

442
00:34:13,170 --> 00:34:17,010
Avís quan ens vam anar una mica fora de la pila, que acaba de canviar la mida,

443
00:34:17,010 --> 00:34:22,080
però en aquest cas, tenim un parell de coses que canvien.

444
00:34:22,080 --> 00:34:27,440
No només el canvi de mida, però els canvis de cap.

445
00:34:27,440 --> 00:34:31,020
Això va de nou a punt de Charlotte abans:

446
00:34:31,020 --> 00:34:38,699
Per què tenim aquest cap també?

447
00:34:38,699 --> 00:34:42,110
Té sentit ara, Charlotte? Tipus d'>>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Alguna cosa així? I què va passar quan ens treu de la cua?

449
00:34:47,500 --> 00:34:54,340
Què va fer el cap fer això ara és interessant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, perquè va canviar - està bé. Ja veig.

451
00:34:56,449 --> 00:35:02,090
A causa de que el cap - on el cap apunta als canvis en termes de la ubicació.

452
00:35:02,090 --> 00:35:07,200
Ja no és sempre l'índex zero. >> Sí, exactament.

453
00:35:07,200 --> 00:35:17,660
El que va succeir va ser desencolatge si l'element d'alta

454
00:35:17,660 --> 00:35:20,590
es va fer i no teníem aquest camp del cap

455
00:35:20,590 --> 00:35:26,880
perquè sempre estàvem trucant a aquesta cadena a 0 Índex del cap de la nostra cua,

456
00:35:26,880 --> 00:35:30,170
llavors hauríem de passar la resta de la cua cap avall.

457
00:35:30,170 --> 00:35:36,010
Hauríem de canviar "bye" del cadenes [1] per les cadenes [0].

458
00:35:36,010 --> 00:35:38,760
I les cadenes [2] fins a arribar a les cadenes [1].

459
00:35:38,760 --> 00:35:43,050
I hauríem de fer això per tota la llista d'elements,

460
00:35:43,050 --> 00:35:45,110
tot el conjunt d'elements.

461
00:35:45,110 --> 00:35:50,490
I quan fem això amb una matriu, que es posa molt costós.

462
00:35:50,490 --> 00:35:53,340
Així que aquí, no és una gran cosa. Només tenim tres elements de la nostra matriu.

463
00:35:53,340 --> 00:35:57,230
Però si tinguéssim una cua d'un miler d'elements o un milió d'elements,

464
00:35:57,230 --> 00:36:00,060
i després, de sobte, vam començar a fer un munt de treure de la cua crida a tots en un bucle,

465
00:36:00,060 --> 00:36:03,930
les coses realment van a disminuir a mesura que es desplaça per tot constantment.

466
00:36:03,930 --> 00:36:07,320
Ja saps, canviar per 1, per un canvi, canvi per 1, canvi en 1.

467
00:36:07,320 --> 00:36:13,650
En el seu lloc, s'utilitza aquest cap, l'anomenem un "punter", encara que en realitat no és un punter

468
00:36:13,650 --> 00:36:16,430
en sentit estricte, no és un tipus de punter.

469
00:36:16,430 --> 00:36:19,410
No és un * int o char * ni res d'això.

470
00:36:19,410 --> 00:36:28,930
Però s'assenyala o indica el cap de la nostra cua. Sí?

471
00:36:28,930 --> 00:36:38,800
>> [Estudiant] Com treure de la cua saber fer esclatar just al costat del que està al capdavant?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Com treure de la cua saber com fer esclatar tot el que està al cap? Dret >>, si.

473
00:36:43,620 --> 00:36:49,050
>> El que veieu és simplement sigui quin sigui el camp de capçalera s'estableix en.

474
00:36:49,050 --> 00:36:52,710
Així que en aquest primer cas, si mirem aquí mateix,

475
00:36:52,710 --> 00:36:55,690
nostre cap és 0, 0 índex. >> Dret.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Només diu bé, bé, l'element en l'índex 0, la cadena "hola",

477
00:37:00,500 --> 00:37:03,050
És l'element al capdavant de la nostra cua.

478
00:37:03,050 --> 00:37:05,570
Així que anem a treure de la cua d'aquest tipus.

479
00:37:05,570 --> 00:37:09,800
I això serà l'element que es retorna al llamador.

480
00:37:09,800 --> 00:37:14,540
Sí, Saad? >> Així que el cap, bàsicament, estableix la - a on vas a índex?

481
00:37:14,540 --> 00:37:17,750
Aquest és el començament de la mateixa? Sí >>. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Això és esdevenir el nou començament de la nostra matriu.

483
00:37:22,900 --> 00:37:28,930
Així que quan vostè treure de la cua alguna cosa, tot el que has de fer és accedir a l'element en l'índex q.head,

484
00:37:28,930 --> 00:37:32,240
i que serà l'element que voleu treure de la cua.

485
00:37:32,240 --> 00:37:34,930
Vostè també ha de disminuir la mida.

486
00:37:34,930 --> 00:37:39,430
Anem a veure una mica on les coses es posen una mica difícil amb això.

487
00:37:39,430 --> 00:37:46,520
Ens treure de la cua, i ara, si ens encolar novament,

488
00:37:46,520 --> 00:37:51,300
On encolar?

489
00:37:51,300 --> 00:37:55,000
D'on ve l'element següent anar a la nostra col?

490
00:37:55,000 --> 00:37:57,980
Diguem que volem posar en cua la cadena "CS".

491
00:37:57,980 --> 00:38:02,240
En què índex s'ha anat? [Els estudiants] Strings [2]. >> Dos.

492
00:38:02,240 --> 00:38:04,980
Per què no 2 i 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Perquè ara el cap és 1, pel que és com l'inici de la llista?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Dret. I el que indica el final de la llista?

495
00:38:21,220 --> 00:38:23,290
De què feiem servir per indicar el final de la nostra col?

496
00:38:23,290 --> 00:38:25,970
El cap és el cap de la nostra cua, el principi de la nostra cua.

497
00:38:25,970 --> 00:38:29,530
Quin és el fi de la nostra col? [Els estudiants] mida. >> Mida, exactament.

498
00:38:29,530 --> 00:38:36,360
Així que els nostres nous elements a anar en grandària, i els elements que prenem de sortir al capdavant.

499
00:38:36,360 --> 00:38:45,390
En posar en cua el següent element, l'estem posant a mida.

500
00:38:45,390 --> 00:38:48,530
[Estudiant] Abans de posar això en si, la mida era d'1, no?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Dret. Així que no prou en grandària. Grandària + no, +1, però el cap +.

502
00:38:55,690 --> 00:38:59,990
Com que va canviar tot per la quantitat cap.

503
00:38:59,990 --> 00:39:14,270
Així que aquí, ara tenim una cua de mida 1 que comença en l'índex 1.

504
00:39:14,270 --> 00:39:20,730
La cua és d'índex 2. Sí?

505
00:39:20,730 --> 00:39:25,780
>> [Estudiant] Què passa quan vostè dequeue cadenes [0], i les ranures de les cordes en la memòria

506
00:39:25,780 --> 00:39:29,420
només es buiden, en el fons, o simplement oblidat?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. En aquest sentit, ens estem oblidant.

508
00:39:34,700 --> 00:39:42,640
Si estiguéssim emmagatzemar còpies d'ells -

509
00:39:42,640 --> 00:39:46,310
moltes estructures de dades sovint s'emmagatzemen les seves pròpies còpies dels elements

510
00:39:46,310 --> 00:39:51,760
de manera que la persona que gestiona l'estructura de dades no ha de preocupar

511
00:39:51,760 --> 00:39:53,650
sobre el qual tots els punters es dirigeix.

512
00:39:53,650 --> 00:39:56,000
L'estructura de dades s'aferra a tot, s'aferra a totes les còpies,

513
00:39:56,000 --> 00:39:59,580
per assegurar-se que tot el que persisteix adequadament.

514
00:39:59,580 --> 00:40:03,140
No obstant això, en aquest cas, aquestes estructures de dades només, per simplicitat,

515
00:40:03,140 --> 00:40:05,580
no estan fent còpies de tot el que estem emmagatzemant en ells.

516
00:40:05,580 --> 00:40:08,630
[Estudiant] Per tant es tracta d'una sèrie contínua de -? Sí >>.

517
00:40:08,630 --> 00:40:14,350
Si mirem cap enrere en el que va ser la definició d'aquesta estructura, ho és.

518
00:40:14,350 --> 00:40:19,110
És només un conjunt estàndard com s'ha vist,

519
00:40:19,110 --> 00:40:24,280
una matriu de char * s.

520
00:40:24,280 --> 00:40:26,340
Això - >> Sí, m'estava preguntant

521
00:40:26,340 --> 00:40:29,130
si finalment es quedarà sense memòria, fins a cert punt,

522
00:40:29,130 --> 00:40:32,330
si vostè té tots aquests llocs buits a la matriu?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Sí, això és un bon punt.

524
00:40:36,390 --> 00:40:41,530
>> Si ens fixem en el que ha passat ara en aquest moment,

525
00:40:41,530 --> 00:40:46,350
hem omplert la nostra cua, com es veu.

526
00:40:46,350 --> 00:40:50,390
Però en realitat no hem omplert la nostra col

527
00:40:50,390 --> 00:40:57,710
perquè tenim una cua que és talla 2, però comença en l'índex 1,

528
00:40:57,710 --> 00:41:02,160
perquè aquí és on el nostre punter cap.

529
00:41:02,160 --> 00:41:08,400
Com vostè deia, aquest element en cadenes [0], en l'índex 0, no està realment allà.

530
00:41:08,400 --> 00:41:10,450
No està en la nostra cua més.

531
00:41:10,450 --> 00:41:16,460
Simplement no es va molestar a entrar i escriure sobre ella quan ho tregui de la cua.

532
00:41:16,460 --> 00:41:18,700
Així que, encara que sembla que ens hem quedat sense memòria, que realment no tenen.

533
00:41:18,700 --> 00:41:23,270
Aquest lloc està disponible per al nostre ús.

534
00:41:23,270 --> 00:41:29,310
El comportament apropiat, si fóssim a tractar de treure de la cua i la primera cosa

535
00:41:29,310 --> 00:41:34,420
com "adéu", que hauria de sortir comiat fora.

536
00:41:34,420 --> 00:41:38,460
Ara el nostre col comença en l'índex 2 i és de mida 1.

537
00:41:38,460 --> 00:41:42,240
I ara, si tractem de posar en cua una mica més, diguem 50,

538
00:41:42,240 --> 00:41:47,880
50 anys han d'anar en aquest punt en l'índex 0

539
00:41:47,880 --> 00:41:51,270
perquè encara disponible. Sí, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] açò es farà de forma automàtica?

541
00:41:53,630 --> 00:41:56,150
[Hardison] No passa absolutament automàticament. Cal fer els comptes

542
00:41:56,150 --> 00:42:00,380
per fer que funcioni, però en essència el que hem fet és que hem acaba de finalitzar la voltant.

543
00:42:00,380 --> 00:42:04,070
[Saad] I està bé si aquest té un forat al mig d'ella?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ho és si podem fer que les matemàtiques funcionen de manera adequada.

545
00:42:08,720 --> 00:42:15,470
>> I resulta que això no és realment tan difícil de fer amb l'operador mod.

546
00:42:15,470 --> 00:42:20,040
Així que igual que vam fer amb César i el material criptogràfic,

547
00:42:20,040 --> 00:42:25,190
utilitzant mod, podem fer les coses per embolicar i seguir endavant

548
00:42:25,190 --> 00:42:28,090
voltant i voltant i voltant amb la nostra cua,

549
00:42:28,090 --> 00:42:32,180
mantenir aquest punter cap es mou al voltant.

550
00:42:32,180 --> 00:42:38,840
Observeu que la mida està respectant sempre el nombre d'elements en realitat dins de la cua.

551
00:42:38,840 --> 00:42:43,110
I és només el punter de cap que es manté amb bicicleta a través.

552
00:42:43,110 --> 00:42:49,660
Si ens fixem en el que va succeir aquí, si ens remuntem al principi,

553
00:42:49,660 --> 00:42:55,020
i que acaba de veure el que passa al cap

554
00:42:55,020 --> 00:42:58,240
quan encolar alguna cosa, no va passar res al cap.

555
00:42:58,240 --> 00:43:00,970
Quan en cua una altra cosa, no va passar res al cap.

556
00:43:00,970 --> 00:43:04,130
Així que es treu de la cua alguna cosa, el cap s'incrementa en un.

557
00:43:04,130 --> 00:43:06,600
Tenim alguna cosa en cua, no passa res al cap.

558
00:43:06,600 --> 00:43:11,060
En llevar de la cua una mica, de sobte el cap s'incrementa.

559
00:43:11,060 --> 00:43:14,660
Quan encolar una cosa, no passa res al cap.

560
00:43:14,660 --> 00:43:20,240
>> Què passaria en aquest moment si haguéssim de treure de la cua alguna cosa nova?

561
00:43:20,240 --> 00:43:23,240
Alguna idea? Què li passaria al cap?

562
00:43:23,240 --> 00:43:27,190
Què ha de passar amb el cap

563
00:43:27,190 --> 00:43:32,990
si haguéssim de treure de la cua una mica més?

564
00:43:32,990 --> 00:43:35,400
El cap ara mateix està en l'índex 2,

565
00:43:35,400 --> 00:43:38,920
el que significa que el cap de la cua és strings [2].

566
00:43:38,920 --> 00:43:44,280
[Estudiant] Això retorna 0? >> S'ha de tornar a 0. Cal embolicar la volta, exactament.

567
00:43:44,280 --> 00:43:48,440
Fins ara, cada vegada que es diu treure de la cua, hem estat afegint un a cap,

568
00:43:48,440 --> 00:43:50,960
afegir un al cap, afegir un a la cap, afegir un a cap.

569
00:43:50,960 --> 00:43:58,400
Així que el punter de cap arriba a l'últim índex en la nostra matriu,

570
00:43:58,400 --> 00:44:05,650
llavors hem de concloure la volta al principi, torna a 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Què determina la capacitat de la cua en una pila?

572
00:44:09,900 --> 00:44:13,120
[Hardison] En aquest cas, només hem estat utilitzant una constant # defineix. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] en el fitxer actual. C, es pot anar en fang i amb ell una mica

574
00:44:19,590 --> 00:44:21,710
i fer-ho tan gran o tan petit com vostè vulgui.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Així que quan vostè està fent una cua, com fer que l'equip sap

576
00:44:25,310 --> 00:44:29,120
la mida que vol que la pila sigui?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Això és una gran pregunta.

578
00:44:31,700 --> 00:44:34,800
Hi ha un parell de maneres. Una d'elles és simplement definir per avançat

579
00:44:34,800 --> 00:44:42,050
i dir que això serà una cua que té 4 elements o elements 50 o 10.000.

580
00:44:42,050 --> 00:44:45,430
L'altra manera és fer el que la gent d'edició de hackers estan fent

581
00:44:45,430 --> 00:44:52,310
i crear funcions perquè la seva cua creix dinàmicament a mesura que s'afegeixen més coses polz

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Així que per anar amb la primera opció, el que la sintaxi s'utilitza

583
00:44:54,740 --> 00:44:57,830
per dir-li al programa quin és la mida de la cua?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Així que sortirem d'això.

585
00:45:04,780 --> 00:45:12,650
Encara estic en stack.c aquí, així que només vaig a desplaçar-se fins la part superior aquí.

586
00:45:12,650 --> 00:45:17,920
Pots veure això aquí? Aquest és el # defineix capacitat 10.

587
00:45:17,920 --> 00:45:24,600
I això és gairebé exactament la mateixa sintaxi que tenim per la cua.

588
00:45:24,600 --> 00:45:28,390
Excepte en la cua, hem de struct camp addicional aquí.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, vaig pensar que la capacitat de dir la capacitat de la cadena.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Aquesta és la longitud màxima de la paraula. >> Ho tinc.

591
00:45:36,770 --> 00:45:41,180
Si. La capacitat aquí - que és un gran punt.

592
00:45:41,180 --> 00:45:44,000
I això és una cosa que és difícil

593
00:45:44,000 --> 00:45:49,480
perquè el que hem declarat aquí és una matriu de char * s.

594
00:45:49,480 --> 00:45:52,770
Una matriu de punters.

595
00:45:52,770 --> 00:45:56,690
Aquest és un arranjament de caràcters.

596
00:45:56,690 --> 00:46:01,690
Això és probablement el que he vist quan he estat declarant seus buffers per l'arxiu d'E / S,

597
00:46:01,690 --> 00:46:06,840
quan vostè ha estat la creació de cadenes de forma manual a la pila.

598
00:46:06,840 --> 00:46:09,090
No obstant això, el que tenim aquí és una matriu de char * s.

599
00:46:09,090 --> 00:46:13,400
Així que és una matriu de punters.

600
00:46:13,400 --> 00:46:18,350
En realitat, si s'amplia cap a fora i veiem el que està passant aquí

601
00:46:18,350 --> 00:46:23,140
a la presentació, es veu que els elements reals, les dades de caràcter

602
00:46:23,140 --> 00:46:26,180
no s'emmagatzema dins de la pròpia matriu.

603
00:46:26,180 --> 00:46:42,690
Què està emmagatzemada dins la nostra àmplia aquí són punters a les dades de caràcters.

604
00:46:42,690 --> 00:46:52,560
Bé. Així hem vist com la mida de la cua és igual que amb la pila,

605
00:46:52,560 --> 00:46:58,670
la mida respecta sempre el nombre d'elements actualment a la cua.

606
00:46:58,670 --> 00:47:02,720
Després de fer 2 posa en cua, la mida és 2.

607
00:47:02,720 --> 00:47:07,110
Després de fer una dequeue la mida és ara 1.

608
00:47:07,110 --> 00:47:09,330
Després de fer un altre en cua la mida és una còpia de seguretat a 2.

609
00:47:09,330 --> 00:47:12,340
Així, la mida definitivament respecti el nombre d'elements a la cua,

610
00:47:12,340 --> 00:47:15,580
i després el cap només segueix el ciclisme.

611
00:47:15,580 --> 00:47:20,210
Va de 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
I cada vegada que anomenem a treure de la cua, el punter de cap s'incrementa l'índex següent.

613
00:47:25,620 --> 00:47:29,930
I si el cap està a punt de passar, es torna de nou a 0.

614
00:47:29,930 --> 00:47:34,870
Així que amb això, podem escriure la funció de treure de la cua.

615
00:47:34,870 --> 00:47:40,200
I sortirem de la funció de posada en cua per vostès per posar en pràctica en el seu lloc.

616
00:47:40,200 --> 00:47:45,880
>> En llevar de la cua un element de la nostra cua,

617
00:47:45,880 --> 00:47:55,490
¿Què va ser el primer que va fer Daniel quan vam començar a escriure la funció pop per piles?

618
00:47:55,490 --> 00:48:00,490
Vull sentir d'algú que no ha parlat encara.

619
00:48:00,490 --> 00:48:06,710
A veure, Saad, te'n recordes del que Daniel va fer el que la primera cosa quan va escriure pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] No, va ser - >> Va provar per alguna cosa.

621
00:48:08,860 --> 00:48:12,140
[Saad] Si la mida és major que 0. >> Exactament.

622
00:48:12,140 --> 00:48:14,390
I què era que les proves d'?

623
00:48:14,390 --> 00:48:19,090
[Saad] Això estava provant per veure si hi ha alguna cosa a l'interior de la matriu.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Exactament. Pel que no pot fer esclatar qualsevol cosa fora de la pila si està buit.

625
00:48:23,210 --> 00:48:26,510
De la mateixa manera, no es pot treure de la cua des d'una cua si està buit.

626
00:48:26,510 --> 00:48:30,420
Què és el primer que hem de fer en la nostra funció de treure de la cua aquí, et sembla?

627
00:48:30,420 --> 00:48:33,860
[Saad] Si la mida és més gran que 0? Sí >>.

628
00:48:33,860 --> 00:48:37,710
En aquest cas, he fet només una prova per veure si és 0.

629
00:48:37,710 --> 00:48:42,240
Si és 0, es pot tornar null.

630
00:48:42,240 --> 00:48:45,280
Però la lògica mateixa.

631
00:48:45,280 --> 00:48:49,110
I seguirem amb això.

632
00:48:49,110 --> 00:48:54,600
Si la mida no és 0, on és l'element que voleu treure de la cua?

633
00:48:54,600 --> 00:48:58,550
[Saad] Al capdavant? >> Exactament.

634
00:48:58,550 --> 00:49:01,720
Només podem treure el primer element de la nostra cua

635
00:49:01,720 --> 00:49:07,040
mitjançant l'accés a l'element al cap.

636
00:49:07,040 --> 00:49:14,630
Res boig.

637
00:49:14,630 --> 00:49:19,620
Després d'això, què hem de fer? ¿Què ha de passar?

638
00:49:19,620 --> 00:49:23,740
Quina era l'altra cosa que hem parlat en treure de la cua?

639
00:49:23,740 --> 00:49:28,130
Dues coses han de passar, perquè la nostra col ha canviat.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reduir la mida. >> Hem de reduir la mida i augmentar el cap? Exactament.

641
00:49:35,640 --> 00:49:40,600
Per augmentar el cap, no podem simplement a cegues augmenten el cap, recorda.

642
00:49:40,600 --> 00:49:45,080
No podem fer queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Hem de incloure també aquest mod per la capacitat.

644
00:49:51,630 --> 00:49:54,740
I per què mod per la capacitat, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Perquè ha de embolicar. >> Exactament.

646
00:49:58,680 --> 00:50:04,750
Ens mod per la capacitat, ja que ha de embolicar al voltant de nou a 0.

647
00:50:04,750 --> 00:50:07,400
Així que ara, en aquest punt, podem fer el que va dir Daniel.

648
00:50:07,400 --> 00:50:12,700
Podem disminuir la mida.

649
00:50:12,700 --> 00:50:29,170
I llavors només pot tornar l'element que estava a la part superior de la cua.

650
00:50:29,170 --> 00:50:34,000
S'assembla una mica al principi Gnarly. És possible que tingui una pregunta. Com diu?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Per què és primer en la part superior de la cua? D'on ve això?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ve de la quarta línia de la part inferior.

653
00:50:42,480 --> 00:50:46,060
Després de realitzar proves per assegurar-se que la nostra cua no és buida,

654
00:50:46,060 --> 00:50:54,100
ens retirem char * primer, treure l'element que seu en l'índex cap

655
00:50:54,100 --> 00:50:58,680
de la nostra matriu, de la nostra àmplia cordes, anomenada >> i que per primera vegada?

656
00:50:58,680 --> 00:51:04,500
[Hardison] I en diem primer. Si.

657
00:51:04,500 --> 00:51:09,850
Només per donar seguiment a això, per què creus que havíem de fer això?

658
00:51:09,850 --> 00:51:18,270
[Sam] Cada primer s'acaben de tornar q.strings [q.head]? Sí >>.

659
00:51:18,270 --> 00:51:23,830
>> Perquè estem fent aquest canvi de la q.head amb la funció mod,

660
00:51:23,830 --> 00:51:27,810
i no hi ha manera de fer-ho dins de la línia de retorn també.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exactament. Vostè és el clau. Sam està totalment en el clau.

662
00:51:31,640 --> 00:51:36,800
La raó per la qual va haver de retirar-se el primer element de la nostra cua i emmagatzemar en una variable

663
00:51:36,800 --> 00:51:43,030
és perquè aquesta línia on havíem q.head just,

664
00:51:43,030 --> 00:51:47,030
aquí està l'operador mod en què no és una cosa que puguem fer

665
00:51:47,030 --> 00:51:51,230
i que tingui efecte al cap sense - en una sola línia.

666
00:51:51,230 --> 00:51:54,480
Així que en realitat hem de treure el primer element, a continuació, ajust el cap,

667
00:51:54,480 --> 00:52:00,430
ajustar la mida, i després tornar l'element que ens retirem.

668
00:52:00,430 --> 00:52:02,680
I això és una cosa que veurem sorgir més tard amb

669
00:52:02,680 --> 00:52:04,920
llistes enllaçades, com jugar amb ells.

670
00:52:04,920 --> 00:52:08,410
Sovint, quan vostè està alliberant o l'eliminació de les llistes enllaçades

671
00:52:08,410 --> 00:52:13,500
cal recordar el següent element, el punter següent d'una llista enllaçada

672
00:52:13,500 --> 00:52:16,330
abans de disposar de l'actual.

673
00:52:16,330 --> 00:52:23,580
Perquè d'una altra manera de desfer-se de la informació del que queda a la llista.

674
00:52:23,580 --> 00:52:34,160
Ara, si vostè va al seu dispositiu, s'obre queue.c--x d'això.

675
00:52:34,160 --> 00:52:39,390
Així que si obro queue.c, deixa zoom aquí,

676
00:52:39,390 --> 00:52:44,970
veuràs que té un arxiu d'aspecte similar.

677
00:52:44,970 --> 00:52:49,200
D'aspecte similar a l'arxiu del que teníem abans amb stack.c.

678
00:52:49,200 --> 00:52:54,690
Tenim la nostra estructura de col definida tal com vam veure en les diapositives.

679
00:52:54,690 --> 00:52:59,870
>> Tenim la nostra funció en cua que és per tu per fer.

680
00:52:59,870 --> 00:53:04,340
I tenim la funció de treure de la cua aquí.

681
00:53:04,340 --> 00:53:06,870
La funció de treure de la cua a l'arxiu no s'ha implementat,

682
00:53:06,870 --> 00:53:13,230
però ho vaig a posar de nou en el PowerPoint perquè pugui escriure, si ho desitja.

683
00:53:13,230 --> 00:53:16,690
Així que per als propers 5 minuts més o menys, vostès treballen en enqueue

684
00:53:16,690 --> 00:53:22,570
que és gairebé el contrari de treure de la cua.

685
00:53:22,570 --> 00:53:29,560
No ha d'ajustar el cap quan estàs encolem, però què s'ha d'ajustar?

686
00:53:29,560 --> 00:53:38,920
Mida. Així que quan en cua, el cap es manté intacte, la mida es canvia.

687
00:53:38,920 --> 00:53:46,920
Però es necessita una mica de - vostè haurà de jugar amb aquest mod

688
00:53:46,920 --> 00:53:57,560
d'esbrinar exactament el que l'índex de l'element nou ha d'inserir al.

689
00:53:57,560 --> 00:54:03,080
Així que vaig a donar a vostès una mica, posar treure de la cua de nou a la diapositiva,

690
00:54:03,080 --> 00:54:05,200
i com vostès tenen preguntes, els criden perquè puguem

691
00:54:05,200 --> 00:54:09,220
tots parlen d'ells com a grup.

692
00:54:09,220 --> 00:54:13,960
A més, amb la mida que no - en ajustar la mida, sempre pots fer sol -

693
00:54:13,960 --> 00:54:18,720
Què ha de mod la mida cada vegada? [Daniel] >> No No ha de mod de la mida, clar.

694
00:54:18,720 --> 00:54:24,260
Com que la mida sempre, si TEU AQUESTES - assumint que vostè està manejant les coses adequadament,

695
00:54:24,260 --> 00:54:30,840
la mida sempre serà d'entre 0 i 3.

696
00:54:30,840 --> 00:54:38,680
On cal mod quan estàs fent en col?

697
00:54:38,680 --> 00:54:41,060
[Estudiant] Només per al cap. >> Només per al cap, exactament.

698
00:54:41,060 --> 00:54:44,620
I per què has de mod en absolut en enqueue?

699
00:54:44,620 --> 00:54:48,830
Quan es tracta d'una situació en què hauria de mod?

700
00:54:48,830 --> 00:54:53,630
[Estudiant] Si tens coses a espais, com en els espais 1 i 2,

701
00:54:53,630 --> 00:54:55,950
i llavors havia de afegir alguna cosa a 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Sí, exactament. Així que si el seu cap és punter al final,

703
00:55:02,570 --> 00:55:14,210
o si la mida del seu cap és més gran, o més aviat, es va a embolicar al voltant de la cua.

704
00:55:14,210 --> 00:55:17,830
>> Així que en aquesta situació que tenim aquí a la diapositiva en aquest moment,

705
00:55:17,830 --> 00:55:24,370
si vull posar en cua alguna cosa en aquest moment,

706
00:55:24,370 --> 00:55:31,110
volem posar en cua una mica en l'índex 0.

707
00:55:31,110 --> 00:55:35,450
Així que si ens fixem en que el 50 va i em crida enqueue 50,

708
00:55:35,450 --> 00:55:40,840
i surt allà baix a la part inferior. Va en índex 0.

709
00:55:40,840 --> 00:55:44,160
Substitueix a la 'hola' que va ser llevat de la cua ja.

710
00:55:44,160 --> 00:55:46,210
[Daniel] No es té cura que en treure de la cua ja?

711
00:55:46,210 --> 00:55:50,550
Per què fer alguna cosa amb el cap posat en cua?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, així que no estem modificant el cap, em sap greu.

713
00:55:55,770 --> 00:56:02,310
Però vostè ha d'utilitzar l'operador mod quan s'està accedint

714
00:56:02,310 --> 00:56:04,250
l'element que voleu posar en cua quan s'està accedint

715
00:56:04,250 --> 00:56:06,960
el següent element a la cua.

716
00:56:06,960 --> 00:56:10,960
[Basil] Jo no ho vaig fer, i em van donar l '"èxit" en aquest país.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, entenc el que estàs dient.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Així que didn't - vostè acaba de fer en q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Acabo de canviar costats, jo no vaig fer res amb el cap.

720
00:56:20,670 --> 00:56:24,300
[Hardison] En realitat no ha de restablir el cap per ser qualsevol cosa,

721
00:56:24,300 --> 00:56:31,650
però quan es índex en la matriu cordes,

722
00:56:31,650 --> 00:56:39,500
de fet has de seguir endavant i calcular on l'element següent és,

723
00:56:39,500 --> 00:56:44,230
perquè Withe la pila, el següent de la pila sempre va ser

724
00:56:44,230 --> 00:56:48,740
en l'índex corresponent a la mida.

725
00:56:48,740 --> 00:56:55,850
Si mirem enrere cap a la nostra funció push pila,

726
00:56:55,850 --> 00:57:03,100
sempre podem desemborsar en el nostre element nou a la dreta en la grandària de l'índex.

727
00:57:03,100 --> 00:57:06,710
Mentre que amb la cua, no podem fer això

728
00:57:06,710 --> 00:57:10,340
perquè si estem en aquesta situació,

729
00:57:10,340 --> 00:57:18,130
si tenim en cua 50 nostra cadena de nou a la dreta en cadenes [1]

730
00:57:18,130 --> 00:57:20,540
que no volem fer.

731
00:57:20,540 --> 00:57:41,200
Volem tenir la nova cadena va en l'índex 0.

732
00:57:41,200 --> 00:57:44,320
>> Algú - Sí? [Estudiant] Tinc una pregunta, però no és realment relacionats.

733
00:57:44,320 --> 00:57:48,160
Què significa quan algú es diu alguna cosa així com punter pred?

734
00:57:48,160 --> 00:57:51,260
Quina és l'abreviatura d'aquest nom? Sé que és només un nom.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred punter? Anem a veure. En quin context?

736
00:57:59,110 --> 00:58:01,790
[Estudiant] Era per a la inserció. Et puc preguntar després si vols

737
00:58:01,790 --> 00:58:03,920
perquè no és realment relacionats, però només I -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Des del codi d'inserció de David de conferència?

739
00:58:07,300 --> 00:58:10,860
Podem aconseguir això i parlar-ne.

740
00:58:10,860 --> 00:58:15,550
Parlarem d'això després, un cop arribem a llistes enllaçades.

741
00:58:15,550 --> 00:58:21,440
>> Així que anem molt ràpid cop d'ull al que la funció de posada en cua sembla.

742
00:58:21,440 --> 00:58:26,530
Què va ser el primer que la gent va tractar de fer en la seva línia de posada en cua? En aquesta cua?

743
00:58:26,530 --> 00:58:29,960
Igual que el que vas fer per pila empenyent.

744
00:58:29,960 --> 00:58:32,080
Què vas fer, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, inintel · ligible]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exactament. Si (q.size CAPACITAT ==) -

747
00:58:45,700 --> 00:58:54,720
He de posar les meves claus al lloc correcte - retorna fals.

748
00:58:54,720 --> 00:59:01,370
Apropar una mica. Bé.

749
00:59:01,370 --> 00:59:03,800
Ara, ¿què és el següent que hem de fer?

750
00:59:03,800 --> 00:59:11,370
Igual que amb la pila, i s'insereix en el lloc correcte.

751
00:59:11,370 --> 00:59:16,010
I el que era el lloc adequat per inserir això?

752
00:59:16,010 --> 00:59:23,170
Amb la pila era mida de l'índex, amb això no és exactament això.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Tinc q.head--o - q.strings >>? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [+ q.head q.size mod CAPACITAT]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] És probable que vulgui posar entre parèntesi aquesta

756
00:59:42,740 --> 00:59:48,830
pel que estem rebent l'adequada prioritat i per això és cleart a tothom.

757
00:59:48,830 --> 00:59:55,800
I estableix que la igualtat? >> Per str? >> Per str. Gran.

758
00:59:55,800 --> 01:00:00,160
I ara, què és l'últim que hem de fer?

759
01:00:00,160 --> 01:00:06,780
Igual que vam fer a la pila. >> Incrementar la mida? >> Incrementar la mida.

760
01:00:06,780 --> 01:00:13,830
Boom. I després, ja que el codi d'arrencada només retorna false per defecte,

761
01:00:13,830 --> 01:00:27,460
volem canviar aquesta propietat a true si tot va a través i tot va bé.

762
01:00:27,460 --> 01:00:33,050
Està bé. Això és un munt d'informació per a la secció.

763
01:00:33,050 --> 01:00:39,480
No estem molt a sobre. Volem parlar molt ràpid sobre simplement enllaçada llistes.

764
01:00:39,480 --> 01:00:44,010
Vaig a posar això perquè puguem tornar-hi més tard.

765
01:00:44,010 --> 01:00:50,850
Però tornem a la nostra presentació per uns pocs més diapositives.

766
01:00:50,850 --> 01:00:53,790
Així enqueue és TOT, ara ho hem fet.

767
01:00:53,790 --> 01:00:57,430
>> Ara donem una ullada a simplement enllaçada llistes.

768
01:00:57,430 --> 01:01:00,040
Parlem d'aquests una mica més a classe.

769
01:01:00,040 --> 01:01:02,540
Quants de vostès van veure la demostració en la que hi havia gent

770
01:01:02,540 --> 01:01:08,220
torpemente assenyalant a cada un dels altres nombres i explotació? >> Jo estava en això.

771
01:01:08,220 --> 01:01:16,620
>> Què pensen vostès? Això, espero que desmitificar aquests poc una mica?

772
01:01:16,620 --> 01:01:25,990
Amb una llista, resulta que ens ocupem d'aquest tipus que anomenarem a un node.

773
01:01:25,990 --> 01:01:32,520
Mentre que amb la cua i pila que ens prenem les estructures que ens criden a la cua a la pila,

774
01:01:32,520 --> 01:01:34,860
teníem aquestes nova cua en els tipus de pila,

775
01:01:34,860 --> 01:01:39,240
aquí una llista està realment format per un grup de nodes.

776
01:01:39,240 --> 01:01:45,920
De la mateixa manera que les cadenes són més que un munt de caràcters tots alineats un al costat de l'altre.

777
01:01:45,920 --> 01:01:50,650
Una llista enllaçada és només un node i node a un altre ia un altre node i el node a un altre.

778
01:01:50,650 --> 01:01:55,080
I en lloc de trencar tots els nodes entre si i el seu emmagatzematge contigua

779
01:01:55,080 --> 01:01:58,090
tots un al costat de l'altre en la memòria,

780
01:01:58,090 --> 01:02:04,470
tenint aquest punter següent ens permet emmagatzemar els nodes on sigui, a l'atzar.

781
01:02:04,470 --> 01:02:10,500
I a continuació, tipus de filferro a tots junts per assenyalar d'una a la següent.

782
01:02:10,500 --> 01:02:15,850
>> I quina va ser la gran avantatge que això té sobre una matriu?

783
01:02:15,850 --> 01:02:21,680
Durant tot l'emmagatzematge contigua just enganxat un al costat de l'altre?

784
01:02:21,680 --> 01:02:24,190
Te'n recordes? Sí? Assignació dinàmica de memòria >>?

785
01:02:24,190 --> 01:02:27,220
>> Assignació dinàmica de memòria en quin sentit?

786
01:02:27,220 --> 01:02:31,780
[Estudiant] En que es pot seguir fent més gran i vostè no ha de moure el conjunt complet?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exactament. Així que amb una matriu, quan vostè vol posar un nou element en el medi d'ella,

788
01:02:40,940 --> 01:02:45,320
vostè ha de canviar tot per a fer lloc.

789
01:02:45,320 --> 01:02:47,880
I com parlem amb la cua,

790
01:02:47,880 --> 01:02:50,080
és per això que mantenir aquest punter cap,

791
01:02:50,080 --> 01:02:52,050
pel que no estem canviant constantment les coses.

792
01:02:52,050 --> 01:02:54,520
Com que resulta car si tens una gran varietat

793
01:02:54,520 --> 01:02:57,130
i que està constantment fent aquestes insercions aleatòries.

794
01:02:57,130 --> 01:03:00,820
Mentre que amb una llista, l'únic que has de fer és tirar en un nou node,

795
01:03:00,820 --> 01:03:06,330
ajustar els punters, i ja està.

796
01:03:06,330 --> 01:03:10,940
Què merda sobre això?

797
01:03:10,940 --> 01:03:16,830
A part del fet que no és tan fàcil de treballar com una matriu? Sí?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Bé, crec que és molt més difícil tenir accés a un element específic de la llista enllaçada?

799
01:03:22,980 --> 01:03:30,470
[Hardison] No es pot saltar a un element arbitrari en el medi de la llista enllaçada.

800
01:03:30,470 --> 01:03:33,800
Com s'ha de fer en el seu lloc? >> Vostè ha de recórrer tota la cosa.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Vostè ha d'anar a través d'un en un, un a la vegada.

802
01:03:35,660 --> 01:03:38,480
És un enorme - és un dolor.

803
01:03:38,480 --> 01:03:41,550
Quina és l'altra - no hi ha una altra caiguda a això.

804
01:03:41,550 --> 01:03:45,340
[Basil] No es pot anar cap endavant i cap enrere? Has d'anar a una adreça?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Llavors, ¿com resoldre això, algunes vegades?

806
01:03:48,570 --> 01:03:53,370
[Basil] doblement enllaçada llistes? >> Exactament. Hi ha llistes doblement enllaçades.

807
01:03:53,370 --> 01:03:55,540
Hi ha també - ho sento?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] És això el mateix que utilitzar el que predefinit -

809
01:03:57,620 --> 01:04:01,090
Acabo de recordar, no és el que la cosa pred serveix?

810
01:04:01,090 --> 01:04:05,850
No és en el medi i doblement sols?

811
01:04:05,850 --> 01:04:10,020
Mirada [Hardison] Anem a què és exactament el que estava fent.

812
01:04:10,020 --> 01:04:15,760
Així que aquí anem. Aquí està la llista de codis.

813
01:04:15,760 --> 01:04:25,620
Aquí tenim predptr, aquí. És això el que estaves parlant?

814
01:04:25,620 --> 01:04:30,750
Així que aquesta va ser - que ha alliberant una llista i que està tractant d'emmagatzemar un punter a ell.

815
01:04:30,750 --> 01:04:35,000
Aquesta no és la doblement, lligada simplement llistes.

816
01:04:35,000 --> 01:04:40,090
Podem parlar més sobre això més endavant ja que es parla de l'alliberament de la llista

817
01:04:40,090 --> 01:04:42,900
i vull mostrar algunes altres coses primer.

818
01:04:42,900 --> 01:04:51,480
però és igual - és recordar el valor de ptr

819
01:04:51,480 --> 01:04:54,170
[Estudiant] Oh, és punter precedent? Sí >>.

820
01:04:54,170 --> 01:05:04,070
Així que llavors sí pot incrementar ptr abans de llavors lliure predptr ho és.

821
01:05:04,070 --> 01:05:09,130
Perquè no podem gratis ptr i després trucar a ptr = ptr següent, no?

822
01:05:09,130 --> 01:05:11,260
Això seria dolent.

823
01:05:11,260 --> 01:05:20,940
Així que anem a veure, de nou a aquest home.

824
01:05:20,940 --> 01:05:23,900
>> L'altra cosa dolenta sobre les llistes és que, si bé amb una sèrie

825
01:05:23,900 --> 01:05:26,520
només tenim tots els elements mateixos apilats un al costat a l'altre,

826
01:05:26,520 --> 01:05:29,050
aquí també hem introduït aquest punter.

827
01:05:29,050 --> 01:05:34,060
Així que hi ha una porció addicional de memòria que estem tenint d'utilitzar

828
01:05:34,060 --> 01:05:37,910
per a cada element que s'està emmagatzemant en la nostra llista.

829
01:05:37,910 --> 01:05:40,030
Tenim la flexibilitat, però té un cost.

830
01:05:40,030 --> 01:05:42,230
Ve amb el cost de temps,

831
01:05:42,230 --> 01:05:45,270
i ve amb aquest cost de memòria també.

832
01:05:45,270 --> 01:05:47,800
Temps en el sentit que ara hem d'anar a través de cada element de la matriu

833
01:05:47,800 --> 01:05:58,670
per trobar l'índex d'un a 10, o que hauria estat índex 10 en una matriu.

834
01:05:58,670 --> 01:06:01,230
>> Només molt ràpid, quan ens diagrama terme aquestes llistes,

835
01:06:01,230 --> 01:06:05,980
normalment ens aferrem al capdavant de la llista o el primer indicador de la llista

836
01:06:05,980 --> 01:06:08,010
i compte que aquest és un punter veritable.

837
01:06:08,010 --> 01:06:11,100
És a 4 bytes. No és un node en si.

838
01:06:11,100 --> 01:06:17,120
Així que ja veus que no té cap valor int-hi, cap punter següent en el mateix.

839
01:06:17,120 --> 01:06:20,790
És, literalment, només un punter.

840
01:06:20,790 --> 01:06:23,550
Es va a apuntar a alguna cosa que és una struct node actual.

841
01:06:23,550 --> 01:06:28,480
[Sam] Punter anomenat node? >> Aquesta és - no. Aquest és un punter a una cosa de tipus node.

842
01:06:28,480 --> 01:06:32,540
És un punter a una estructura de node. >> Oh, està bé.

843
01:06:32,540 --> 01:06:36,870
Diagrama sobre el codi de l'esquerra, a la dreta.

844
01:06:36,870 --> 01:06:42,190
Podem posar-ho en null, el que és una bona manera de començar.

845
01:06:42,190 --> 01:06:49,850
Quan ho diagrama, o bé escriure com nul o es posa una línia a través d'ell d'aquesta manera.

846
01:06:49,850 --> 01:06:53,910
>> Una de les maneres més fàcils per treballar amb llistes,

847
01:06:53,910 --> 01:06:57,430
i els demanem fer les dues coses anteposar i annexar a veure les diferències entre els dos,

848
01:06:57,430 --> 01:07:01,320
però anteposant és definitivament més fàcil.

849
01:07:01,320 --> 01:07:05,790
Quan s'anteposa, aquí és on vostè - quan vostè prepend (7),

850
01:07:05,790 --> 01:07:10,050
ves i crear l'estructura de node

851
01:07:10,050 --> 01:07:13,870
i s'estableix primer en assenyalar, perquè ara, ja que s'anteposa,

852
01:07:13,870 --> 01:07:17,240
que estarà al principi de la llista.

853
01:07:17,240 --> 01:07:22,540
Si prepend (3), que crea un altre node, però 3 ara ve abans de les 7.

854
01:07:22,540 --> 01:07:31,130
Així que bàsicament estàs portant les coses a la nostra llista.

855
01:07:31,130 --> 01:07:34,720
Ara, vostè pot veure que anteposar, de vegades en diuen empènyer,

856
01:07:34,720 --> 01:07:39,600
perquè vostè està empenyent un nou element en la seva llista.

857
01:07:39,600 --> 01:07:43,270
També és fàcil d'esborrar a la part davantera d'una llista.

858
01:07:43,270 --> 01:07:45,650
Així que la gent sol anomenar a aquest pop.

859
01:07:45,650 --> 01:07:52,200
I d'aquesta manera, es pot emular una pila utilitzant una llista enllaçada.

860
01:07:52,200 --> 01:07:57,880
Whoops. Em sap greu, ara estem entrant en annexats. Així que aquí estem anteposat (7), ara prepend (3).

861
01:07:57,880 --> 01:08:02,600
Si s'anteposa altra cosa en aquesta llista, si s'anteposa (4),

862
01:08:02,600 --> 01:08:06,540
llavors tindríem 4 i després 3 i després 7.

863
01:08:06,540 --> 01:08:14,220
Llavors podríem pop i treure 4, treure 3, retiri 7.

864
01:08:14,220 --> 01:08:16,500
Sovint, la forma més intuïtiva de pensar en això és amb annexats.

865
01:08:16,500 --> 01:08:20,310
Així que he diagramat el que es veuria amb afegir aquí.

866
01:08:20,310 --> 01:08:23,380
En aquest sentit, afegeix (7) no es veu diferent

867
01:08:23,380 --> 01:08:25,160
perquè només hi ha un element a la llista.

868
01:08:25,160 --> 01:08:28,620
I afegint (3) el posa al final.

869
01:08:28,620 --> 01:08:31,020
Potser vostè pot veure ara el truc amb append

870
01:08:31,020 --> 01:08:36,600
és que des que només sap on és el principi de la llista és,

871
01:08:36,600 --> 01:08:39,450
per annexar a una llista del que has de caminar tot el camí a través de la llista

872
01:08:39,450 --> 01:08:46,500
per arribar a la final, detenir, a continuació, crear el node i tot plunk avall.

873
01:08:46,500 --> 01:08:50,590
Cablejar totes les coses.

874
01:08:50,590 --> 01:08:55,170
Així que amb prefix, com s'acaba de copiar a través d'aquest molt ràpid,

875
01:08:55,170 --> 01:08:58,170
quan s'anteposa a una llista, que és bastant simple.

876
01:08:58,170 --> 01:09:02,960
>> Vostè fa el seu nou node, impliquen alguna assignació de memòria dinàmica.

877
01:09:02,960 --> 01:09:09,830
Així que aquí estem fent un struct node usant malloc.

878
01:09:09,830 --> 01:09:14,710
Així que estem usant malloc, ja que deixarà de banda la memòria per nosaltres per més endavant

879
01:09:14,710 --> 01:09:20,350
perquè no volem que això - volem que aquesta memòria a persistir durant molt de temps.

880
01:09:20,350 --> 01:09:25,350
I tenim un punter a l'espai en la memòria que acaba de ser assignat.

881
01:09:25,350 --> 01:09:29,260
Utilitzem mida del node, no concretem els camps.

882
01:09:29,260 --> 01:09:31,899
No generar manualment el nombre de bytes,

883
01:09:31,899 --> 01:09:39,750
en lloc d'això utilitzar sizeof perquè sapiguem que estem rebent la quantitat adequada de bytes.

884
01:09:39,750 --> 01:09:43,660
Ens assegurem de provar que la nostra crida malloc èxit.

885
01:09:43,660 --> 01:09:47,939
Això és una cosa que vull fer en general.

886
01:09:47,939 --> 01:09:52,590
En les màquines modernes, quedant sense memòria no és una cosa que és fàcil

887
01:09:52,590 --> 01:09:56,610
llevat que l'assignació d'un munt de coses i fer una llista enorme,

888
01:09:56,610 --> 01:10:02,220
però si vostè està construint coses per, per exemple, com un iPhone o Android an,

889
01:10:02,220 --> 01:10:05,230
que tenen recursos limitats de memòria, especialment si vostè està fent alguna cosa intens.

890
01:10:05,230 --> 01:10:08,300
Així que és bo tenir en la pràctica.

891
01:10:08,300 --> 01:10:10,510
>> Tingueu en compte que he fet servir un parell de funcions diferents aquí

892
01:10:10,510 --> 01:10:12,880
que vostè ha vist que són una espècie de nou.

893
01:10:12,880 --> 01:10:15,870
Així fprintf és com printf

894
01:10:15,870 --> 01:10:21,320
excepte el seu primer argument és el corrent a la qual voleu imprimir.

895
01:10:21,320 --> 01:10:23,900
En aquest cas, volem imprimir a la cadena d'error estàndard

896
01:10:23,900 --> 01:10:29,410
que és diferent de la outStream estàndard.

897
01:10:29,410 --> 01:10:31,620
Per defecte es mostra en el mateix lloc.

898
01:10:31,620 --> 01:10:34,600
També imprimeix a la terminal, però es pot -

899
01:10:34,600 --> 01:10:38,790
utilitzant les ordres que ha après sobre les tècniques de redireccionament,

900
01:10:38,790 --> 01:10:42,290
que vam aprendre en vídeo de Tommy com a conjunt de problemes 4, pot dirigir-

901
01:10:42,290 --> 01:10:47,900
a les diferents àrees, a continuació, sortir, aquí, surt del seu programa.

902
01:10:47,900 --> 01:10:50,440
Bàsicament es tracta de com tornar a principal,

903
01:10:50,440 --> 01:10:53,600
excepte que utilitzem sortida perquè aquí retorn no farà res.

904
01:10:53,600 --> 01:10:57,140
No estem en principal, de manera que torna no se surti del programa com nosaltres volem.

905
01:10:57,140 --> 01:11:03,020
Per això, utilitzem la funció de sortida i donar-li un codi d'error.

906
01:11:03,020 --> 01:11:11,890
Llavors aquí ens vam posar camp del nou node de valor, el seu camp i sigui igual a i, i després el cablejar.

907
01:11:11,890 --> 01:11:15,530
Hem establert punter següent del nou node per assenyalar a la primera,

908
01:11:15,530 --> 01:11:20,460
i després 1 ara anirà al nou node.

909
01:11:20,460 --> 01:11:25,120
Aquestes primeres línies de codi, en realitat estem construint el nou node.

910
01:11:25,120 --> 01:11:27,280
No les dues últimes línies d'aquesta funció, però els primers.

911
01:11:27,280 --> 01:11:30,290
En realitat es pot extreure en una funció, en una funció auxiliar.

912
01:11:30,290 --> 01:11:32,560
Això és moltes vegades el que faig és que em tiri en una funció,

913
01:11:32,560 --> 01:11:36,040
Jo en dic alguna cosa com a node de generació,

914
01:11:36,040 --> 01:11:40,410
i que manté la funció prepend bastant petit, és només 3 línies a continuació.

915
01:11:40,410 --> 01:11:48,710
Faig una crida a la meva funció de node de generació, i llavors tot filferro cap amunt.

916
01:11:48,710 --> 01:11:51,970
>> L'última cosa que vull mostrar,

917
01:11:51,970 --> 01:11:54,030
i deixaré que facis append i tot això pel seu compte,

918
01:11:54,030 --> 01:11:57,500
és la forma d'iterar sobre una llista.

919
01:11:57,500 --> 01:12:00,780
Hi ha un munt de maneres diferents per iterar sobre una llista.

920
01:12:00,780 --> 01:12:03,140
En aquest cas, anem a calcular la longitud d'una llista.

921
01:12:03,140 --> 01:12:06,570
Així que vam començar amb longitud = 0.

922
01:12:06,570 --> 01:12:11,580
Això és molt similar a l'escriptura strlen per una cadena.

923
01:12:11,580 --> 01:12:17,780
Això és el que vull mostrar, per aquest circuit aquí.

924
01:12:17,780 --> 01:12:23,530
S'assembla una mica covard, no és el típic int i = 0, i <el que sigui, i + +.

925
01:12:23,530 --> 01:12:34,920
En el seu lloc, hi ha la inicialització de la nostra variable n com el començament de la llista.

926
01:12:34,920 --> 01:12:40,620
I llavors, mentre la variable Iterador no és nul, és seguir endavant.

927
01:12:40,620 --> 01:12:46,340
Això és perquè, per convenció, al final de la llista serà nul.

928
01:12:46,340 --> 01:12:48,770
I a continuació, per incrementar, en lloc de fer + +,

929
01:12:48,770 --> 01:12:57,010
l'equivalent llista vinculada de + + és n = n-> següent.

930
01:12:57,010 --> 01:13:00,410
>> Vaig a deixar d'omplir els buits aquí perquè estem fora de temps.

931
01:13:00,410 --> 01:13:09,300
Però cal tenir això en ment a mesura que treballa en conjunts de processadors teus spellr.

932
01:13:09,300 --> 01:13:11,650
Les llistes enllaçades, si està implementant una taula hash,

933
01:13:11,650 --> 01:13:14,010
sens dubte vindrà en molt pràctic.

934
01:13:14,010 --> 01:13:21,780
I tenir aquest idioma per recórrer les coses faran la vida molt més fàcil, amb sort.

935
01:13:21,780 --> 01:13:25,910
Qualsevol pregunta, ràpidament?

936
01:13:25,910 --> 01:13:28,920
[Sam] Va a enviar el acabat sll i sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Vaig a enviar diapositives acabades i la pila completa sll i queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]