1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Oddelek 6: Manj udobno]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[To je CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
V redu. Dobrodošli v oddelku 6.

5
00:00:11,840 --> 00:00:14,690
Ta teden bomo lahko govorili o podatkovnih struktur v oddelku,

6
00:00:14,690 --> 00:00:19,780
predvsem zato, ker ta teden problem, nastavljeno na spellr

7
00:00:19,780 --> 00:00:24,410
pa cel kup različnih podatkov raziskovanja strukture.

8
00:00:24,410 --> 00:00:26,520
Obstaja kup različnih načinov, kako lahko gredo s problemskega sklopa,

9
00:00:26,520 --> 00:00:31,570
in več kot podatkovne strukture poznate, bolj kul stvari, ki jih lahko storite.

10
00:00:31,570 --> 00:00:34,990
>> Torej, začnimo. Najprej bomo govorili o skladih,

11
00:00:34,990 --> 00:00:37,530
Sveženj in vrsta podatkovne strukture, da bomo govorili o.

12
00:00:37,530 --> 00:00:40,560
Skladovnice in vrste so res v pomoč, ko bomo začeli govoriti o grafih,

13
00:00:40,560 --> 00:00:44,390
ki nismo naredili toliko prav zdaj.

14
00:00:44,390 --> 00:00:52,820
Ampak oni so res dobro razumeti enega od velikih temeljnih podatkovnih struktur CS.

15
00:00:52,820 --> 00:00:54,880
Opis v opredelitvi težave set,

16
00:00:54,880 --> 00:00:59,260
če ga dvigni, govori o skladih so podobna

17
00:00:59,260 --> 00:01:05,239
Kup jedilnico pladnjev, da imate v kavarni na jedilnih dvorane

18
00:01:05,239 --> 00:01:09,680
če, ko je osebje prihaja jedilnico in restavracij postavlja pladnje od dneva, ko ste jih očisti,

19
00:01:09,680 --> 00:01:12,000
so jim nalagajo eden na drugega.

20
00:01:12,000 --> 00:01:15,050
In potem, ko otroci pridejo, da bi dobili hrano,

21
00:01:15,050 --> 00:01:19,490
vlečejo pladnje off, prvi vrh 1, potem tisti pod njim, potem pa tisti, ki v nadaljevanju.

22
00:01:19,490 --> 00:01:25,190
Torej, v bistvu, prvi pladenj, da je osebje, jedilnica odložil je zadnja, ki dobi vzletelo.

23
00:01:25,190 --> 00:01:32,330
Zadnji je, da je jedilnica zaposlene delavce in je prva, ki dobi vzletelo za večerjo.

24
00:01:32,330 --> 00:01:38,100
V določilu je problem podloga, ki jo lahko prenesete, če tega še niste storili,

25
00:01:38,100 --> 00:01:46,730
govorimo o modeliranje stucture žetonov podatkov z uporabo te vrste struct.

26
00:01:46,730 --> 00:01:51,070
>> Torej, kaj imamo tukaj, to je podoben temu, kar je bilo predstavljeno v predavanju

27
00:01:51,070 --> 00:01:58,120
razen v predavanju smo predstavili to z ints v nasprotju z char * s.

28
00:01:58,120 --> 00:02:06,250
To se bo sveženj, ki shranjuje kaj?

29
00:02:06,250 --> 00:02:09,009
Daniel? Kaj pa shranjevanje v tem kupu?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Smo shranjevanje nize v tem kupu, točno.

31
00:02:15,260 --> 00:02:20,950
Vse, kar morate imeti, da bi ustvarili sveženj je matrika

32
00:02:20,950 --> 00:02:23,920
določene zmogljivosti, ki je v tem primeru,

33
00:02:23,920 --> 00:02:28,020
Zmogljivost se bo v vseh kape, ker je konstantna.

34
00:02:28,020 --> 00:02:36,340
In potem poleg matrike, vse, kar potrebujete za sledenje je sedanja velikost matrike.

35
00:02:36,340 --> 00:02:38,980
Ena stvar, ki sem seznanjen, da je nekako kul

36
00:02:38,980 --> 00:02:47,060
je, da smo ustvariti podatkovno strukturo zložene na vrhu druge strukture podatkov, array.

37
00:02:47,060 --> 00:02:50,110
Obstajajo različni načini za izvajanje nizov.

38
00:02:50,110 --> 00:02:54,250
Tega ne bo naredil še čisto, vendar upam, da po tem, ko delaš povezanost seznam težav,

39
00:02:54,250 --> 00:03:00,520
boste videli, kako lahko enostavno izvajati sveženj na vrhu seznama povezan tudi.

40
00:03:00,520 --> 00:03:02,640
Ampak za zdaj se bomo lotili z nizi.

41
00:03:02,640 --> 00:03:06,350
Torej, še enkrat, vse, kar potrebujete, je polje in smo morali slediti velikost matrike.

42
00:03:06,350 --> 00:03:09,850
[Sam] Žal mi je, kako to, da ste rekli, da je sklad na vrhu strune?

43
00:03:09,850 --> 00:03:13,440
To se mi zdi kot niza sta v dimnik.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ja. Ustvarjamo, smo ob naši strukturo niza podatkov -

45
00:03:16,790 --> 00:03:22,130
To je veliko vprašanje. Torej, vprašanje je, zakaj je za ljudi, ki so gledali to na spletu,

46
00:03:22,130 --> 00:03:24,140
Zato smo pravi, da je sveženj na vrhu nizov,

47
00:03:24,140 --> 00:03:27,990
ker tukaj izgleda niza sta v notranjosti kup?

48
00:03:27,990 --> 00:03:31,050
Kar je popolnoma res.

49
00:03:31,050 --> 00:03:34,660
Kaj sem mislil, da je bila, da smo dobili strukturo niza podatkov.

50
00:03:34,660 --> 00:03:39,290
Imamo celo vrsto char * s, ta polja nizov,

51
00:03:39,290 --> 00:03:45,300
in se bomo dodati, da je za ustvarjanje zložene podatkovno strukturo.

52
00:03:45,300 --> 00:03:48,620
>> Torej sklad je nekoliko bolj zapletena, kot matriko.

53
00:03:48,620 --> 00:03:51,890
Mi lahko uporabite niz za izgradnjo dimnika.

54
00:03:51,890 --> 00:03:55,810
Torej, to je, če rečemo, da je sklad, zgrajena na vrhu matrike.

55
00:03:55,810 --> 00:04:02,510
Prav tako, kot sem že dejal, smo lahko zgradili kup na vrhu seznama povezan.

56
00:04:02,510 --> 00:04:04,960
Namesto s paleto, da imajo naše elemente,

57
00:04:04,960 --> 00:04:10,070
da bi nam povezan seznam, da imajo svoje elemente in graditi dimnika okoli tega.

58
00:04:10,070 --> 00:04:12,420
Sprehodimo se skozi nekaj primerov, ki si ogleduje nekatere oznake,

59
00:04:12,420 --> 00:04:14,960
videli, kaj se dejansko dogaja tukaj.

60
00:04:14,960 --> 00:04:23,400
Na levi strani, sem vrgel dol, kaj bi to kup struct videti v spomin

61
00:04:23,400 --> 00:04:28,330
če bi bila kapaciteta # opredeljen kot štiri.

62
00:04:28,330 --> 00:04:33,490
Imamo svojo 4-element char * niz.

63
00:04:33,490 --> 00:04:38,110
Imamo strune [0] strune [1], strune [2], strune [3]

64
00:04:38,110 --> 00:04:43,800
in potem zadnji prostor za našo velikost celo število.

65
00:04:43,800 --> 00:04:46,270
Ali je to smiselno? Ok.

66
00:04:46,270 --> 00:04:48,790
To je tisto, kar se zgodi, če kaj naredim na desni strani,

67
00:04:48,790 --> 00:04:55,790
ki bo moja koda, je le razglasi struct, zložene struct imenovan s.

68
00:04:55,790 --> 00:05:01,270
To je tisto, kar smo dobili. Določa to sled v spominu.

69
00:05:01,270 --> 00:05:05,590
Prvo vprašanje je, kaj je vsebina tega dimnika struct?

70
00:05:05,590 --> 00:05:09,250
Zdaj oni nič, ampak oni niso popolnoma nič.

71
00:05:09,250 --> 00:05:13,300
Oni te vrste smeti. Nimamo pojma, kaj je v njih.

72
00:05:13,300 --> 00:05:17,000
Ko smo se ugotovi dimnih s, smo šele metanje navzdol, da na vrhu pomnilnika.

73
00:05:17,000 --> 00:05:19,840
To je nekako tako kot razglasitvi int i in ne inicializira.

74
00:05:19,840 --> 00:05:21,730
Saj ne vem, kaj je notri. Si lahko preberete, kaj je notri,

75
00:05:21,730 --> 00:05:27,690
a ne bi bilo super pomoč.

76
00:05:27,690 --> 00:05:32,680
Ena stvar, ki jo želite, da se vedno spomnim na to, kar je inicializirati treba inicializirati.

77
00:05:32,680 --> 00:05:35,820
V tem primeru bomo za inicializacijo velikosti nič,

78
00:05:35,820 --> 00:05:39,960
ker to se bo izkazalo, da je za nas zelo pomembno.

79
00:05:39,960 --> 00:05:43,450
Mi lahko gredo naprej in inicializacijo vse napotke, vse char * i,

80
00:05:43,450 --> 00:05:49,670
da so nekateri razumljivo vrednost, verjetno ničen.

81
00:05:49,670 --> 00:05:58,270
Ampak to ni povsem nujno, da to storimo.

82
00:05:58,270 --> 00:06:04,200
>> Zdaj, dve glavni dejavnosti na kupih so?

83
00:06:04,200 --> 00:06:07,610
Vsakdo spomnite iz predavanja, kaj storiti s nizov? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Potiskanje in živahen? >> Točno tako.

85
00:06:09,700 --> 00:06:13,810
Potiskanje in živahen sta dve glavni dejavnosti na dimnikih.

86
00:06:13,810 --> 00:06:17,060
In kaj storiti, pritisk? >> Postavlja nekaj na vrhu

87
00:06:17,060 --> 00:06:19,300
iz dimnika, nato pa popping ga sname.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Točno tako. Torej pritiskom potisne nekaj na vrhu dimnika.

89
00:06:23,150 --> 00:06:27,700
To je kot dajanje osebja jedilnico jedilni pladenj na pultu.

90
00:06:27,700 --> 00:06:33,630
In živahen je ob jedilni pladenj off dimnika.

91
00:06:33,630 --> 00:06:36,460
Sprehodimo se skozi nekaj primerov, kaj se bo zgodilo

92
00:06:36,460 --> 00:06:39,720
ko smo potisnite stvari v sklad.

93
00:06:39,720 --> 00:06:45,110
Če bi push niz "zdravo" na naši dimnika,

94
00:06:45,110 --> 00:06:49,760
To je tisto, kar bi naša slika izgleda kot zdaj.

95
00:06:49,760 --> 00:06:53,410
Oglejte si, kaj se zgodi?

96
00:06:53,410 --> 00:06:56,530
Prizadevali smo si v prvem elementu matrike našega godala

97
00:06:56,530 --> 00:07:01,420
in smo upped naše večje število za 1.

98
00:07:01,420 --> 00:07:05,340
Torej, če pogledamo razliko med stranmi, tu je bil 0, tu je pred pritiskom.

99
00:07:05,340 --> 00:07:08,690
Tu je po pritisku.

100
00:07:08,690 --> 00:07:13,460
Pred pritiskom, po pritisku.

101
00:07:13,460 --> 00:07:16,860
In zdaj imamo samo en element v našem dimnika.

102
00:07:16,860 --> 00:07:20,970
To je niz "zdravo", in to je to.

103
00:07:20,970 --> 00:07:24,440
Vse ostalo v polju, v naši paleto godala, je še vedno smeti.

104
00:07:24,440 --> 00:07:27,070
Nismo ga inicializirati.

105
00:07:27,070 --> 00:07:29,410
Recimo, potiskanje drugega niza na naši dimnika.

106
00:07:29,410 --> 00:07:32,210
Bomo push "svet" na tem času.

107
00:07:32,210 --> 00:07:35,160
Tako lahko vidite, "svet" tu gre na vrhu "zdravo",

108
00:07:35,160 --> 00:07:40,040
Število in velikost gre do 2.

109
00:07:40,040 --> 00:07:44,520
Sedaj lahko push "CS50", in da bom šel na vrhu.

110
00:07:44,520 --> 00:07:51,110
Če se vrnemo, lahko vidite, kako smo potiskajo stvari na vrhu dimnika.

111
00:07:51,110 --> 00:07:53,320
In zdaj pridemo do pop.

112
00:07:53,320 --> 00:07:58,910
Ko smo izstrelil nekaj off na kupu, kaj se je zgodilo?

113
00:07:58,910 --> 00:08:01,540
Je kdo videl razliko? To je zelo subtilna.

114
00:08:01,540 --> 00:08:05,810
[Študent] velikost. >> Ja, velikost spremenila.

115
00:08:05,810 --> 00:08:09,040
>> Kaj pa bi ti bodo spremenili?

116
00:08:09,040 --> 00:08:14,280
[Študent] Strune, preveč. >> Desno. Strune preveč.

117
00:08:14,280 --> 00:08:17,110
Izkazalo se je, da če delaš na ta način,

118
00:08:17,110 --> 00:08:21,960
saj nismo kopiranje elementov v našem odvodnik,

119
00:08:21,960 --> 00:08:24,670
smo dejansko ne bi bilo treba storiti ničesar, lahko samo uporabo velikost

120
00:08:24,670 --> 00:08:28,630
spremljati števila stvari v naši matriki

121
00:08:28,630 --> 00:08:33,780
tako da, ko smo pop znova, spet sva padanje naše velikosti do 1.

122
00:08:33,780 --> 00:08:39,440
Nobene potrebe ni, da bi dejansko šel in prepisati ničesar.

123
00:08:39,440 --> 00:08:41,710
Nekako funky.

124
00:08:41,710 --> 00:08:46,520
Izkazalo se je, da smo običajno pusti stvari pri miru, ker je manj dela za nas.

125
00:08:46,520 --> 00:08:50,060
Če nam ne bi bilo treba iti nazaj in prepisati nekaj, zakaj potem to?

126
00:08:50,060 --> 00:08:54,150
Torej, ko smo dvakrat pop off dimnika, vse, kar počne, je padanje da velikost nekajkrat.

127
00:08:54,150 --> 00:08:59,120
In spet je to samo zato, ker nismo kopiranje stvari v našem dimnika.

128
00:08:59,120 --> 00:09:01,320
Ja? Pojdi.

129
00:09:01,320 --> 00:09:04,460
[Študent, nerazumljiv] >> In kaj se zgodi, ko boste pritisnili kaj spet?

130
00:09:04,460 --> 00:09:08,570
Ko pritisnete nekaj več, če ne gre?

131
00:09:08,570 --> 00:09:12,390
Če ne gre, Basil? >> Into strune [1]? >> Desno.

132
00:09:12,390 --> 00:09:14,530
Zakaj ne gre v nizih [3]?

133
00:09:14,530 --> 00:09:19,410
[Bazilika] Ker je pozabil, da je bilo kaj v nizih [1] in [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Točno tako. Naš sklad, v bistvu "pozabil", da je bilo gospodarstvo na nič

135
00:09:24,040 --> 00:09:29,480
v nizih [1] in godala [2], tako da, ko smo push "woot",

136
00:09:29,480 --> 00:09:36,670
to šele postavlja, da v elementu na strune [1].

137
00:09:36,670 --> 00:09:41,590
Ali obstaja kakršna koli vprašanja o tem, kako to deluje, na osnovni ravni?

138
00:09:41,590 --> 00:09:45,160
[Sam] Torej to ni dinamično na kakršen koli način, v smislu količine

139
00:09:45,160 --> 00:09:47,620
ali glede na velikost kup?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Točno tako. To je - točka je bila, da to ni bil dinamično growning sklad.

141
00:09:56,750 --> 00:10:02,850
To je sveženj, ki lahko imajo, kvečjemu 4 * char s, največ štiri stvari.

142
00:10:02,850 --> 00:10:07,580
Če bi poskusil in iztisnite 1/5 stvar, kaj misliš, da naj bi se zgodilo?

143
00:10:07,580 --> 00:10:11,870
[Študenti, nerazumljivi]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Točno tako. Obstaja več stvari, ki bi se lahko zgodilo.

145
00:10:14,600 --> 00:10:19,330
To bi lahko seg napako, odvisno od tega, kaj smo -

146
00:10:19,330 --> 00:10:22,530
kako točno smo izvajanje back-end.

147
00:10:22,530 --> 00:10:31,740
To bi lahko prepisali. To bi lahko imelo to buffer overflow, da sva se pogovarjala v razredu.

148
00:10:31,740 --> 00:10:35,240
Kaj bi bilo najbolj očitno stvar, ki se lahko prepišejo

149
00:10:35,240 --> 00:10:42,370
če bomo poskušali push dodatno stvar na našem kup?

150
00:10:42,370 --> 00:10:44,550
Torej ste omenili buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Kaj je lahko stvar, ki se bo prepisati ali stomped na

152
00:10:47,870 --> 00:10:52,320
če je prekoračil po naključju trudili, da bi dodatno stvar?

153
00:10:52,320 --> 00:10:54,730
[Daniel, nerazumljiv] >> mogoče.

154
00:10:54,730 --> 00:10:58,440
Ampak najprej bi lahko kaj zgodi? Kaj če bi poskušali push 1/4 stvar?

155
00:10:58,440 --> 00:11:06,220
Morda bi prepišite velikost, vsaj s tem, da je spomin diagram imamo.

156
00:11:06,220 --> 00:11:10,880
>> V opredelitvi težave množico, ki je tisto, kar bomo izvedbeni danes,

157
00:11:10,880 --> 00:11:16,030
kaj si želimo narediti je, da vrne false.

158
00:11:16,030 --> 00:11:20,030
Naša potisni način vrača boolean vrednost,

159
00:11:20,030 --> 00:11:22,920
in da bo logična vrednost true, če potisni uspe

160
00:11:22,920 --> 00:11:29,730
in lažno, če ne more vsiliti ničesar več, ker sklad je poln.

161
00:11:29,730 --> 00:11:33,620
Sprehodimo se skozi malo tega zakonika zdaj.

162
00:11:33,620 --> 00:11:36,400
Tukaj je naša funkcija potisne.

163
00:11:36,400 --> 00:11:40,380
Naša funkcija za zagon kup bo trajalo v nizu, da dajo na kup.

164
00:11:40,380 --> 00:11:45,820
To se dogaja, da se vrnete res, če je niz uspešno potisnil

165
00:11:45,820 --> 00:11:51,820
na kup in lažno drugače.

166
00:11:51,820 --> 00:11:59,740
Vse predloge o tem, kaj bi bilo dobro prva stvar, ki sem storil?

167
00:11:59,740 --> 00:12:20,630
[Sam] Če površina je enaka zmogljivost potem vrne false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Lepo opravljeno.

169
00:12:23,320 --> 00:12:26,310
Če je velikost zmogljivosti, bomo vrne false.

170
00:12:26,310 --> 00:12:29,270
Ne moremo dati ničesar več v naši dimnika.

171
00:12:29,270 --> 00:12:36,900
Sicer pa želimo dati nekaj na vrh dimnika.

172
00:12:36,900 --> 00:12:41,670
Kaj je "na vrhu dimnika," na začetku?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Velikost 0? Velikost 0 >>.

174
00:12:43,650 --> 00:12:49,990
Kaj je vrh dimnika po eno stvar na kup? Missy, veš?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Velikost je 1, točno. Kar naprej tako, da se velikost,

176
00:12:52,720 --> 00:13:01,690
in vsakič, ko ste dajanje v novi element v velikosti indeks v matriki.

177
00:13:01,690 --> 00:13:05,470
To lahko storimo s takšnim ene podlage, če je to smiselno.

178
00:13:05,470 --> 00:13:11,910
Tako smo dobili našo paleto strune, da bomo do nje dostopajo na velikost indeksa,

179
00:13:11,910 --> 00:13:14,780
in smo le, da bo za shranjevanje naše char * tam.

180
00:13:14,780 --> 00:13:19,340
Opazuj, kako da ni niz kopiranje tukaj dogaja,

181
00:13:19,340 --> 00:13:29,680
ne dinamično dodeljevanje pomnilnika?

182
00:13:29,680 --> 00:13:34,440
In potem Missy odraščali, kaj moramo zdaj narediti,

183
00:13:34,440 --> 00:13:40,570
ker smo shranili niz v ustreznem mestu v matriki,

184
00:13:40,570 --> 00:13:49,230
in ona je rekla, da smo morali prirastek velikosti enega, tako da smo pripravljeni za naslednjo pritiskom.

185
00:13:49,230 --> 00:13:53,950
Tako bomo lahko storite, da z s.size + +.

186
00:13:53,950 --> 00:13:59,330
Na tej točki smo potisnili v naši matriki. Kaj je zadnja stvar, moramo storiti?

187
00:13:59,330 --> 00:14:10,110
[Študent] Vrnitev res. Vrnitev >> res.

188
00:14:10,110 --> 00:14:14,690
Torej, to je zelo preprosta, zelo preprosto kodo. Ne preveč.

189
00:14:14,690 --> 00:14:17,070
Ko ste oviti okrog glave, kako deluje sklad,

190
00:14:17,070 --> 00:14:21,910
to je zelo preprosta za uporabo.

191
00:14:21,910 --> 00:14:26,390
>> Zdaj, naslednji del tega je živahen niz off dimnika.

192
00:14:26,390 --> 00:14:29,410
Jaz bom dal vidva nekaj časa za delo na tem malo.

193
00:14:29,410 --> 00:14:34,320
To je skoraj v bistvu nasprotno, kar smo storili tukaj pritiskom.

194
00:14:34,320 --> 00:14:38,510
Kar sem naredil, je pravzaprav - ojej.

195
00:14:38,510 --> 00:14:48,160
Sem zažene z naprave tukaj in naprave,

196
00:14:48,160 --> 00:14:53,600
Sem potegnil problem iz 5 specifikacijo.

197
00:14:53,600 --> 00:15:02,560
Če bomo povečali tukaj, lahko vidimo, da sem v cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Ste vi prenesli to kodo, ki se tu nahajajo, section6.zip?

199
00:15:08,590 --> 00:15:15,030
V redu. Če tega še niste storili, stori to zdaj, res hitro.

200
00:15:15,030 --> 00:15:22,130
Jaz bom to naredil v moji terminalskem oknu.

201
00:15:22,130 --> 00:15:25,090
Pravzaprav sem to naredil tukaj. Ja.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Imam vprašanje o tem, zakaj ste rekli s.string s razredih velikosti = str?

203
00:15:34,730 --> 00:15:42,910
Kaj je str? Ali je to opredeljeno nekje videl, ali - oh, v char * Str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Da, točno tako. To je bil argument. >> V redu. Žal mi je.

205
00:15:47,160 --> 00:15:49,470
[Hardison] smo podrobno niz za uveljavitev noter

206
00:15:49,470 --> 00:15:55,220
Drugo vprašanje, ki bi lahko prišli do, da v resnici ne govori o tem je bil

207
00:15:55,220 --> 00:15:58,810
smo za samoumevno, da smo imeli to spremenljivko, imenovano s

208
00:15:58,810 --> 00:16:02,710
da je bila po obsegu in dostopen za nas.

209
00:16:02,710 --> 00:16:06,960
Mi je samoumevno, da je bil ta sklad struct.

210
00:16:06,960 --> 00:16:08,930
Tako se ozremo nazaj na to potisni kodo

211
00:16:08,930 --> 00:16:13,450
boste videli, da delamo stvari, s tem, da imam niz, sprejeto leta

212
00:16:13,450 --> 00:16:19,210
potem pa kar naenkrat, bomo dostop s.size, kot so, kje je prišel?

213
00:16:19,210 --> 00:16:23,020
V kodi, ki ga bomo pogledati v oddelku arhiv

214
00:16:23,020 --> 00:16:27,100
in potem stvari, ki jih boste opravljali na vašo težavo določa,

215
00:16:27,100 --> 00:16:32,440
smo naredili naš sklad struct globalno spremenljivko

216
00:16:32,440 --> 00:16:36,380
tako da bomo imeli dostop do njega v vseh naših različnih funkcijah

217
00:16:36,380 --> 00:16:40,630
ne da bi ročno prenesti okoli in ga prenesti s sklicevanjem,

218
00:16:40,630 --> 00:16:44,870
storiti vse, da se vrste stvari z njim.

219
00:16:44,870 --> 00:16:52,280
Saj se samo malo goljufali, če hočete, da bi stvari lepše.

220
00:16:52,280 --> 00:16:57,430
In to je nekaj, kar smo tukaj zato, ker je za zabavo, je lažje.

221
00:16:57,430 --> 00:17:02,800
Pogosto boste videli, ljudje to, če imajo eno veliko podatkovno strukturo

222
00:17:02,800 --> 00:17:07,750
da se je operirana v svojem programu.

223
00:17:07,750 --> 00:17:09,560
>> Vrnimo se prenesejo v napravo.

224
00:17:09,560 --> 00:17:15,240
Ali so vsi uspešno dobil section6.zip?

225
00:17:15,240 --> 00:17:20,440
Vsi razširite z unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Če greste v oddelku 6 imenik -

227
00:17:27,200 --> 00:17:29,220
aah, po vsem mestu -

228
00:17:29,220 --> 00:17:32,840
in si seznam, kaj je notri, boste videli, da imaš tri različne datoteke. c.

229
00:17:32,840 --> 00:17:38,350
Imaš čakalno vrsto, SLL, ki je vezana na posamezno seznam, in kup.

230
00:17:38,350 --> 00:17:44,600
Če odpreš stack.c,

231
00:17:44,600 --> 00:17:47,330
boste videli, da imamo to opredeljeno struct za nas,

232
00:17:47,330 --> 00:17:51,330
točno struct, da smo pravkar govorili v diapozitivih.

233
00:17:51,330 --> 00:17:56,340
Imamo našo globalno spremenljivko za sklad,

234
00:17:56,340 --> 00:18:00,110
imamo našo naročeno funkcijo,

235
00:18:00,110 --> 00:18:04,230
in potem imamo našo pop funkcijo.

236
00:18:04,230 --> 00:18:08,320
Jaz bom dal kodo za potiskanje nazaj na diapozitivu tukaj,

237
00:18:08,320 --> 00:18:10,660
ampak kaj bi rad vi storiti, je, da svojih najboljših močeh,

238
00:18:10,660 --> 00:18:13,790
pojdi in izvajanje pop funkcijo.

239
00:18:13,790 --> 00:18:18,480
Ko ste jo uporabili, jo lahko prevedete to s ti dimnika,

240
00:18:18,480 --> 00:18:22,540
in nato zaženite posledičnega izvedljivo žetonov,

241
00:18:22,540 --> 00:18:28,390
in da bo teči vse te oznake preskusa dol, da je v glavnem.

242
00:18:28,390 --> 00:18:31,060
In glavno skrbi za dejansko izdelavo push in pop klicev

243
00:18:31,060 --> 00:18:33,220
in zagotoviti, da bo šlo vse skozi vso pravico.

244
00:18:33,220 --> 00:18:36,820
Prav tako inicializira stack velikosti tukaj

245
00:18:36,820 --> 00:18:39,780
tako da vam ni treba skrbeti, da inicializacijo.

246
00:18:39,780 --> 00:18:42,310
Lahko domnevamo, da je bilo pravilno inicializiran

247
00:18:42,310 --> 00:18:48,000
s časom, ki ga imate dostop v pop funkcije.

248
00:18:48,000 --> 00:18:53,530
Ima to smisel?

249
00:18:53,530 --> 00:19:00,100
Torej, gremo. Tukaj je pritisk kodo.

250
00:19:00,100 --> 00:19:13,210
Dam ti fantje 5 ali 10 minut.

251
00:19:13,210 --> 00:19:15,690
In če imate kakršno koli vprašanje v vmesnem času, ko ste kodiranje,

252
00:19:15,690 --> 00:19:17,710
prosite naglas.

253
00:19:17,710 --> 00:19:23,080
Torej, če prideš do vbodne rane, kar vprašaj.

254
00:19:23,080 --> 00:19:26,030
Naj vedo, kaj vsi ostali vedo.

255
00:19:26,030 --> 00:19:28,160
Delo s svojim bližnjim preveč.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Midva samo izvedbo pop prav zdaj? >> Samo pop.

257
00:19:30,360 --> 00:19:34,200
Čeprav lahko kopirate izvajanje pritiskom, če želite

258
00:19:34,200 --> 00:19:37,780
tako da bo testiranje delovalo.

259
00:19:37,780 --> 00:19:41,940
Ker je težko preizkusiti stvari dobili v -

260
00:19:41,940 --> 00:19:49,030
ali, da je težko preveriti živahen stvari iz dimnika, če ni nič v sklad za začetek.

261
00:19:49,030 --> 00:19:55,250
>> Kaj je pop naj bi se vrnil? Element od vrha dimnika.

262
00:19:55,250 --> 00:20:01,260
To naj bi se element off vrhu dimnika

263
00:20:01,260 --> 00:20:05,780
in potem padanje velikost dimnika,

264
00:20:05,780 --> 00:20:07,810
in zdaj ste izgubili element na vrhu.

265
00:20:07,810 --> 00:20:11,420
In potem se vrne element na vrhu.

266
00:20:11,420 --> 00:20:20,080
[Študent, nerazumljiv]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Torej, kaj se zgodi, če si to naredil? [Študent, nerazumljiv]

268
00:20:28,810 --> 00:20:34,000
Kaj se dogaja konča, je, da ste verjetno dostop bodisi

269
00:20:34,000 --> 00:20:37,350
element, ki ni bil inicializiran še, da vaš izračun

270
00:20:37,350 --> 00:20:39,990
od katerih je zadnji element je izklopljen.

271
00:20:39,990 --> 00:20:46,260
Torej tukaj, če opazite, pri pritisku, smo dostop do nizov na s.size elementa

272
00:20:46,260 --> 00:20:48,560
ker je novi indeks.

273
00:20:48,560 --> 00:20:51,460
To je nova vrh dimnika.

274
00:20:51,460 --> 00:21:01,100
Ker v pop, s.size se bo naslednji prostor,

275
00:21:01,100 --> 00:21:05,210
prostor, ki je na vrhu vseh elementov v vaših žetonov.

276
00:21:05,210 --> 00:21:10,050
Torej top-najbolj element sploh ni s.size,

277
00:21:10,050 --> 00:21:14,930
ampak, to je pod njo.

278
00:21:14,930 --> 00:21:19,640
>> Druga stvar, ki jo storite, ko ste - v pop,

279
00:21:19,640 --> 00:21:22,030
se imate za zmanjšaj velikost.

280
00:21:22,030 --> 00:21:28,750
Če se spomnite nazaj na našo malo diagram tukaj,

281
00:21:28,750 --> 00:21:30,980
Res je edina stvar, ki smo jih videli dogaja, ko smo poklicali pop

282
00:21:30,980 --> 00:21:36,150
je bilo, da je ta velikost padel, najprej 2, nato 1.

283
00:21:36,150 --> 00:21:42,620
Potem, ko smo potisnil nov element na bi šlo za na ustrezno mesto.

284
00:21:42,620 --> 00:21:49,610
[Bazilika] Če s.size je 2, potem ne bi šel v elementu 2,

285
00:21:49,610 --> 00:21:54,400
in potem bi radi, da pop ta element off?

286
00:21:54,400 --> 00:21:59,510
Torej, če smo šli v - >> Torej, poglejmo še enkrat.

287
00:21:59,510 --> 00:22:07,730
Če je to naš dimnik na tej točki

288
00:22:07,730 --> 00:22:12,130
in rečemo pop,

289
00:22:12,130 --> 00:22:16,150
na katerih indeks je najbolj top-element?

290
00:22:16,150 --> 00:22:19,300
[Bazilika] Na 2, vendar pa se bo pop 3. >> Desno.

291
00:22:19,300 --> 00:22:24,220
Tako da je, kjer je naš znaša 3, vendar želimo, da pop element na indeksu 2.

292
00:22:24,220 --> 00:22:29,900
To je značilno, da je nekako off za tistega, ki ga imajo z ničelno indeksiranje polj.

293
00:22:29,900 --> 00:22:36,430
Torej, če res želite, da pop tretji element, ampak tretji element ni v indeksu 3.

294
00:22:36,430 --> 00:22:39,430
In razlog, nimamo narediti to minus 1, ko smo potiskanje

295
00:22:39,430 --> 00:22:44,120
ker je zdaj, boste opazili, da je večina od zgoraj element,

296
00:22:44,120 --> 00:22:47,600
če smo bili pritisniti na nekaj drugega svežnja na tej točki,

297
00:22:47,600 --> 00:22:50,360
mi bi želeli, da ga potisnite v indeksu 3.

298
00:22:50,360 --> 00:23:03,550
In prav tako se zgodi, da velikost in indeksi line up, ko ste potiskanje.

299
00:23:03,550 --> 00:23:06,960
>> Kdo ima delovno žetonov izvajanja?

300
00:23:06,960 --> 00:23:09,690
Imaš delovno sklad 1. Ali ste pop dela še?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Da. Mislim, da.

302
00:23:11,890 --> 00:23:14,610
>> Program teče in ne seg izjalovljen, to je tiskanje?

303
00:23:14,610 --> 00:23:17,520
Ali natisniti "uspeh", ko ga zaženete?

304
00:23:17,520 --> 00:23:22,630
Ja. Naredite kup, ga zaženite, če se izpiše "uspeh", in ne presega razcvet,

305
00:23:22,630 --> 00:23:26,000
potem je vse v redu.

306
00:23:26,000 --> 00:23:34,070
V redu. Greva na aparat res hitro,

307
00:23:34,070 --> 00:23:46,100
in bomo sprehod skozi to.

308
00:23:46,100 --> 00:23:51,110
Če pogledamo, kaj se dogaja z pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, kaj je bila prva stvar, ki si naredila?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Če je s.size večji od 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Ok. In zakaj ste to storili?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Če se želite prepričati, da je nekaj notri dimnika.

313
00:24:05,610 --> 00:24:10,950
[Hardison] desno. Če želite preizkusiti, se prepričajte, da je s.size večje od 0;

314
00:24:10,950 --> 00:24:13,280
drugače, kaj želiš, da se zgodi?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? Nazaj >> null, točno.

316
00:24:16,630 --> 00:24:20,740
Torej, če s.size večji od 0. Torej, kaj bomo storili?

317
00:24:20,740 --> 00:24:25,890
Kaj bomo naredili, če sklad ni prazen?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vi vzroka velikost? Vi >> padanje višine, v redu.

319
00:24:31,210 --> 00:24:34,440
Torej, kako si to naredil? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Čudovito. In potem, kaj si naredil?

321
00:24:37,030 --> 00:24:44,140
[Stella] In potem sem rekel donos s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Čudovito.

323
00:24:48,560 --> 00:24:51,940
V nasprotnem primeru se vrne null. Ja, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Zakaj ni treba s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ja. >> Razumem.

326
00:24:58,430 --> 00:25:00,980
[Sam] Mislil sem, ker ste prevzeli 1 out,

327
00:25:00,980 --> 00:25:04,290
potem boste, da se ne bo vrnil tistega, ki so zaprosile.

328
00:25:04,290 --> 00:25:09,400
[Hardison] In to je samo tisto, kar smo govorili z vsem tem vprašanjem 0 indeksov.

329
00:25:09,400 --> 00:25:11,380
Torej, če želimo povečati nazaj sem.

330
00:25:11,380 --> 00:25:15,650
Če pogledamo ta tip tukaj, lahko vidite, da ko smo pop,

331
00:25:15,650 --> 00:25:19,340
smo živahen element na indeksu 2.

332
00:25:19,340 --> 00:25:25,200
>> Tako smo zmanjšali našo velikost, potem naša velikost ustreza naši indeks.

333
00:25:25,200 --> 00:25:39,650
Če ne bomo zmanjšaj velikost, potem moramo velikost -1 in nato padanje.

334
00:25:39,650 --> 00:25:45,270
Čudovito. Vse v redu?

335
00:25:45,270 --> 00:25:47,530
Vsa vprašanja o tem?

336
00:25:47,530 --> 00:25:54,050
Obstaja več različnih načinov, da bi napisal, da je to dobro.

337
00:25:54,050 --> 00:26:03,290
V bistvu, lahko naredimo še nekaj - kar lahko naredimo na enem plast.

338
00:26:03,290 --> 00:26:05,770
Mi lahko naredimo eno vrstico donos.

339
00:26:05,770 --> 00:26:12,980
Torej si lahko dejansko upade, preden se vrnemo s tem.

340
00:26:12,980 --> 00:26:18,320
Tako dajanje - pred s.size.

341
00:26:18,320 --> 00:26:22,060
To naredi linija res gosto.

342
00:26:22,060 --> 00:26:30,940
Če je razlika med. - Velikost in s.size, -

343
00:26:30,940 --> 00:26:40,130
je, da to postfix - pravijo, da zato, ker postfix - prihaja po s.size, -

344
00:26:40,130 --> 00:26:47,430
pomeni, da se s.size ocenili za ugotavljanje indeksa

345
00:26:47,430 --> 00:26:50,410
kot je zdaj, ko se izvaja ta linija,

346
00:26:50,410 --> 00:26:54,290
in potem je to - se zgodi, ko postane izvajajo line.

347
00:26:54,290 --> 00:27:00,340
Ko je naložena element pri s.size indeksa.

348
00:27:00,340 --> 00:27:07,260
In to ni tisto, kar želimo, ker hočemo, da padanje najprej zgodilo.

349
00:27:07,260 --> 00:27:10,990
Othewise, da bomo lahko dostop do matriko, učinkovito izven igrišča.

350
00:27:10,990 --> 00:27:16,850
Mi bomo za dostop do elementa nad tisto, ki ga dejansko želijo dostopati.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Je hitreje in porabi manj pomnilnika, da bi v eni vrstici, ali ne?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Odkrito povedano, res je odvisno.

353
00:27:29,620 --> 00:27:34,220
[Sam, nerazumljiv] >> Ja, to je odvisno. To lahko storite prevajalnikov trike

354
00:27:34,220 --> 00:27:41,580
da se prevajalnik zavedati, da običajno, mislim.

355
00:27:41,580 --> 00:27:44,840
>> Tako smo omenili nekaj o tej stvari prevajalnik za optimizacijo

356
00:27:44,840 --> 00:27:47,400
, ki jih lahko naredite v pripravi,

357
00:27:47,400 --> 00:27:50,580
in to je vrsta stvari, ki bi prevajalnik lahko ugotovimo,

358
00:27:50,580 --> 00:27:54,710
kot oh, hej, morda lahko naredim to vse v eni operaciji,

359
00:27:54,710 --> 00:27:59,420
v nasprotju z nalaganjem večje spremenljivko iz RAM-a,

360
00:27:59,420 --> 00:28:03,770
to nižanje, jo shranite nazaj in ga nato nazaj na prvotno mesto nakladanja

361
00:28:03,770 --> 00:28:08,000
obdelati preostanek te operacije.

362
00:28:08,000 --> 00:28:10,710
Ampak ponavadi, ne, to ni reč

363
00:28:10,710 --> 00:28:20,770
da se dogaja, da se vaš program bistveno hitreje.

364
00:28:20,770 --> 00:28:26,000
Vse več vprašanj o skladih?

365
00:28:26,000 --> 00:28:31,360
>> Torej, potiskanje in živahen. Če vi želite, da preizkusite hacker izdaja,

366
00:28:31,360 --> 00:28:33,660
kaj smo naredili v hacker različico je dejansko šlo

367
00:28:33,660 --> 00:28:37,670
in je ta kup raste dinamično.

368
00:28:37,670 --> 00:28:43,190
Izziv je predvsem tukaj v potisni funkciji,

369
00:28:43,190 --> 00:28:48,820
da ugotovimo, kako narediti, da zaporedje narašča

370
00:28:48,820 --> 00:28:52,450
kot vi vztrajati potiska vse več elemente na kupu.

371
00:28:52,450 --> 00:28:56,000
Pravzaprav ni preveč dodatna oznaka.

372
00:28:56,000 --> 00:29:00,080
Samo klic - moraš vedeti, da bi dobili pozive za knjižnične funkcije malloc tam pravilno,

373
00:29:00,080 --> 00:29:03,310
in nato ugotovimo, kdaj boš poklical realloc.

374
00:29:03,310 --> 00:29:06,090
To je zabavno, izziv, če ste zainteresirani.

375
00:29:06,090 --> 00:29:11,550
>> Ampak za zdaj, gremo naprej, in kaj je govoril o čakalnih vrst.

376
00:29:11,550 --> 00:29:15,680
Pomikajte se tukaj.

377
00:29:15,680 --> 00:29:19,340
Čakalna vrsta je blizu sibling od dimnika.

378
00:29:19,340 --> 00:29:25,380
Torej, v plasteh, so stvari, ki naj v zadnji

379
00:29:25,380 --> 00:29:28,810
so bile prve stvari, ki bi jih morale nato umakniti.

380
00:29:28,810 --> 00:29:33,600
Imamo ta zadnji noter, prvi ven, ali LIFO, naročanje.

381
00:29:33,600 --> 00:29:38,390
Ker je v čakalni vrsti, kot ste pričakovali od takrat, ko stojiš v vrsti,

382
00:29:38,390 --> 00:29:41,980
prva oseba, ki se v skladu, je prva stvar, da se v čakalni vrsti,

383
00:29:41,980 --> 00:29:47,630
je prva stvar, ki jo dobi pridobljeni iz čakalne vrste.

384
00:29:47,630 --> 00:29:51,490
Čakalne vrste se pogosto uporabljajo tudi, kadar imamo opravka z grafi,

385
00:29:51,490 --> 00:29:55,560
kot sva se pogovarjala na kratko s policami

386
00:29:55,560 --> 00:30:00,260
in čakalne vrste so tudi priročen za kup drugih stvari.

387
00:30:00,260 --> 00:30:06,180
Ena stvar, ki pride pogosto poskuša ohraniti, na primer,

388
00:30:06,180 --> 00:30:12,310
razporejene seznam elementov.

389
00:30:12,310 --> 00:30:17,650
In lahko to storite z matriko. Lahko vzdrževati urejen seznam stvari, ki v matriki,

390
00:30:17,650 --> 00:30:20,650
vendar je ta postane težavno je potem moraš vedno najti

391
00:30:20,650 --> 00:30:26,160
primerno mesto, da vstavite naslednjo stvar.

392
00:30:26,160 --> 00:30:28,250
Torej, če imate niz številk, 1 do 10,

393
00:30:28,250 --> 00:30:31,630
in potem želite razširiti, da vse številke od 1 do 100,

394
00:30:31,630 --> 00:30:33,670
in ste dobili te številke v naključnem vrstnem redu, in poskuša obdržati vse

395
00:30:33,670 --> 00:30:40,650
razvrščenih kot greš skozi, boste na koncu morali storiti veliko premika.

396
00:30:40,650 --> 00:30:43,910
Pri nekaterih vrstah čakalnih vrst in nekatere vrste osnovnih podatkovnih struktur,

397
00:30:43,910 --> 00:30:46,670
lahko dejansko ostane dokaj preprost.

398
00:30:46,670 --> 00:30:50,640
Nimaš kaj dodati in nato prerazporedi celotno stvar vsak čas.

399
00:30:50,640 --> 00:30:56,770
Prav tako ne boste morali storiti veliko premika notranjih elementov okrog.

400
00:30:56,770 --> 00:31:02,990
Ko se ozremo na vrsti, boste videli, da je - tudi v queue.c v oddelku kode -

401
00:31:02,990 --> 00:31:10,950
struct, ki smo vam ga je dal, je res podoben struct, ki si jo dobila za dimnik.

402
00:31:10,950 --> 00:31:13,770
>> Obstaja ena izjema, in da je ena izjema

403
00:31:13,770 --> 00:31:21,700
je, da imamo te dodatne celo število, ki se imenuje glava,

404
00:31:21,700 --> 00:31:28,120
in tu je glava sledenja vodje čakalni vrsti,

405
00:31:28,120 --> 00:31:32,160
ali prvi element v vrsti.

406
00:31:32,160 --> 00:31:37,470
Z dimnika, smo lahko spremljali element, ki smo bili na tem pridobiti,

407
00:31:37,470 --> 00:31:40,800
ali zgornji del dimnika, z uporabo samo na velikost,

408
00:31:40,800 --> 00:31:44,220
ker je s čakalno vrsto, bomo morali ukvarjati z nasprotnih koncih.

409
00:31:44,220 --> 00:31:49,000
Poskušamo tack stvari na koncu, potem pa se vrne stvari od spredaj.

410
00:31:49,000 --> 00:31:54,640
Tako učinkovito, z glavo, imamo indeks začetku čakalne vrste,

411
00:31:54,640 --> 00:31:58,920
in velikost nam daje indeks koncu čakalne vrste

412
00:31:58,920 --> 00:32:03,730
tako da bomo lahko naložite stvari iz glave in dodali stvari na repu.

413
00:32:03,730 --> 00:32:06,890
Ker v plasteh, smo bili vedno samo ukvarjajo z vrha dimnika.

414
00:32:06,890 --> 00:32:08,900
Nikoli nismo imeli dostop do dna dimnika.

415
00:32:08,900 --> 00:32:12,220
Mi samo dodal stvari na vrh in vzel stvari off vrhu

416
00:32:12,220 --> 00:32:17,470
tako da mi ni bilo treba, da se dodatno polje znotraj našega struct.

417
00:32:17,470 --> 00:32:20,590
Ali to splošno smisel?

418
00:32:20,590 --> 00:32:27,670
V redu. Da, Charlotte? [Charlotte, nerazumljiv]

419
00:32:27,670 --> 00:32:32,660
[Hardison] To je veliko vprašanje, in to je bil tisti, ki je prišel v predavanju.

420
00:32:32,660 --> 00:32:36,290
Mogoče bo sprehod skozi nekaj primerov ponazarjajo, zakaj

421
00:32:36,290 --> 00:32:41,400
ne želimo uporabljati strings [0] kot vodja čakalne vrste.

422
00:32:41,400 --> 00:32:46,770
>> Tako si predstavljam, da imamo vrsto, bomo rekli čakalne vrste.

423
00:32:46,770 --> 00:32:49,210
Na začetku, ko smo šele zaženejo,

424
00:32:49,210 --> 00:32:53,330
Ko smo ravno jo je razglasila, da nismo ničesar inicializiran.

425
00:32:53,330 --> 00:32:56,790
To je vse smeti. Torej, seveda želimo zagotoviti, da bomo inicializirati

426
00:32:56,790 --> 00:33:00,950
tako velikost in glavo polja na 0, kar razumen.

427
00:33:00,950 --> 00:33:05,770
Lahko bi tudi šel naprej in null določeni elementi v naši vrsti.

428
00:33:05,770 --> 00:33:09,930
In da bi to diagram prileganje, opazite, da se zdaj lahko naša vrsta ima samo tri elemente;

429
00:33:09,930 --> 00:33:13,150
ker se lahko naše sklad ima 4, lahko naša vrsta ima samo tri.

430
00:33:13,150 --> 00:33:18,680
In to je samo, da je diagram fit.

431
00:33:18,680 --> 00:33:26,150
Prva stvar, ki se dogaja, je, da smo enqueue niz "hi".

432
00:33:26,150 --> 00:33:30,380
In tako kot smo z kup, nič strašno drugačna tukaj,

433
00:33:30,380 --> 00:33:39,230
vržemo vrvico na strune na [0] in prirastek naše velikosti do 1.

434
00:33:39,230 --> 00:33:42,720
Mi enqueue "adijo", dobi je dana.

435
00:33:42,720 --> 00:33:45,870
Torej, to je videti kot kup za večino del.

436
00:33:45,870 --> 00:33:53,230
Začeli smo tukaj, novost, nov element, velikost ohranja gredo gor.

437
00:33:53,230 --> 00:33:56,330
Kaj se dogaja v tem trenutku, ko želimo dequeue kaj?

438
00:33:56,330 --> 00:34:01,280
Ko smo želeli dequeue, ki je element, ki ga želimo dequeue?

439
00:34:01,280 --> 00:34:04,110
[Bazilika] Strings [0]. >> Zero. Točno, Basil.

440
00:34:04,110 --> 00:34:10,960
Želimo, da se znebite prvega niza, je ta, "živjo".

441
00:34:10,960 --> 00:34:13,170
Torej, kaj je druga stvar, ki je spremenil?

442
00:34:13,170 --> 00:34:17,010
Obvestilo, ko je izstrelil nekaj off na kupu, smo samo spremenili velikost,

443
00:34:17,010 --> 00:34:22,080
ampak tukaj, imamo nekaj stvari, ki se spremenijo.

444
00:34:22,080 --> 00:34:27,440
Ne samo spremembo velikosti, vendar mora ravnatelj spremembe.

445
00:34:27,440 --> 00:34:31,020
To sega nazaj do točke Charlotte je prej:

446
00:34:31,020 --> 00:34:38,699
Zakaj imamo to glavo, pa tudi?

447
00:34:38,699 --> 00:34:42,110
Ali je smiselno zdaj, Charlotte? >> Nekako.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Nekako? Torej, kaj se je zgodilo, ko smo dequeued?

449
00:34:47,500 --> 00:34:54,340
Kaj je vodja to, da je zdaj zanimivo?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, saj je spremenilo - v redu. Vidim.

451
00:34:56,449 --> 00:35:02,090
Ker je glava - če je glava kaže na spremembe v smislu lokacije.

452
00:35:02,090 --> 00:35:07,200
To ni več vedno nič kazalo 1. >> Ja, točno tako.

453
00:35:07,200 --> 00:35:17,660
Kaj se je zgodilo, če dequeueing visoko element

454
00:35:17,660 --> 00:35:20,590
je bilo storjeno, in nismo imeli te glave polje

455
00:35:20,590 --> 00:35:26,880
ker smo bili vedno kliče ta niz na 0 indeksa vodja našega vrsti,

456
00:35:26,880 --> 00:35:30,170
potem bi morali preusmeriti preostalo vrsti navzdol.

457
00:35:30,170 --> 00:35:36,010
Morali bi premik "adijo" od od nizov [1], da se strune [0].

458
00:35:36,010 --> 00:35:38,760
In godala [2] določa, da strune [1].

459
00:35:38,760 --> 00:35:43,050
In bi kar moramo storiti, je to za celoten seznam elementov,

460
00:35:43,050 --> 00:35:45,110
celoten nabor elementov.

461
00:35:45,110 --> 00:35:50,490
In ko to počnemo z vrsto, da postane zelo drago.

462
00:35:50,490 --> 00:35:53,340
Torej, tukaj, to ni nič takega. Pravkar smo imeli tri elemente v naši matriki.

463
00:35:53,340 --> 00:35:57,230
Ampak, če bomo imeli čakalno vrsto za tisoč elementov ali milijon elementov,

464
00:35:57,230 --> 00:36:00,060
in potem kar naenkrat smo začeli delati cel kup dequeue poziva vse v zanki

465
00:36:00,060 --> 00:36:03,930
stvari se res dogaja, da bi to upočasnilo, saj prenaša vse navzdol stalno.

466
00:36:03,930 --> 00:36:07,320
Veš, premik za 1, premik za 1, premik z 1, premik do 1.

467
00:36:07,320 --> 00:36:13,650
Namesto tega uporabite glavo, ga imenujemo "kazalec", čeprav v resnici ni kazalec

468
00:36:13,650 --> 00:36:16,430
v ožjem smislu, to ni kazalec tipa.

469
00:36:16,430 --> 00:36:19,410
To ni int * ali char * ali kaj podobnega.

470
00:36:19,410 --> 00:36:28,930
Ampak to kaže ali prikazuje glavo naši vrsti. Ja?

471
00:36:28,930 --> 00:36:38,800
>> [Študent] Kako dequeue vem, da samo pop off vse, kar je v glavi?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Kako dequeue vem, kako pop off vse, kar je v glavi? >> Ja, ja.

473
00:36:43,620 --> 00:36:49,050
>> Kaj to gleda le glede na glavo polje nastavljeno na.

474
00:36:49,050 --> 00:36:52,710
Torej, v tem prvem primeru, če gledamo tukaj,

475
00:36:52,710 --> 00:36:55,690
Naša glava je 0, 0 indeks. >> Desno.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Torej je samo pravi redu, dobro, je element na indeksu 0, niz "hi"

477
00:37:00,500 --> 00:37:03,050
je element, na čelu naše vrste.

478
00:37:03,050 --> 00:37:05,570
Torej bomo dequeue tega tipa.

479
00:37:05,570 --> 00:37:09,800
In to bo tisti element, ki dobi vrnjen klicatelja.

480
00:37:09,800 --> 00:37:14,540
Da, Saad? >> Torej v bistvu glava nastavi - če boš to kazalo?

481
00:37:14,540 --> 00:37:17,750
To je začetek tega? >> Ja. >> Redu.

482
00:37:17,750 --> 00:37:22,900
[Hardison] To je postal nov začetek za našo matriko.

483
00:37:22,900 --> 00:37:28,930
Torej, ko dequeue nekaj, vse, kar morate storiti, je dostop do elementa na indeks q.head,

484
00:37:28,930 --> 00:37:32,240
in bo to element, ki ga želite dequeue.

485
00:37:32,240 --> 00:37:34,930
Imate tudi padanje višine.

486
00:37:34,930 --> 00:37:39,430
Bomo videli v nekaj, kjer se stvari malce težavno s tem.

487
00:37:39,430 --> 00:37:46,520
Mi dequeue, in zdaj, če bomo spet enqueue,

488
00:37:46,520 --> 00:37:51,300
kje smo enqueue?

489
00:37:51,300 --> 00:37:55,000
Kam je šel naslednji element v naši vrsti?

490
00:37:55,000 --> 00:37:57,980
Povejte želimo enqueue niz "CS".

491
00:37:57,980 --> 00:38:02,240
V katerega indeks bo šlo? [Dijaki] Strings [2]. >> Dva.

492
00:38:02,240 --> 00:38:04,980
Zakaj 2 in ne 0?

493
00:38:04,980 --> 00:38:13,570
[Bazilika] Ker zdaj je glava 1, tako da je kot na začetku seznama?

494
00:38:13,570 --> 00:38:21,220
[Hardison] desno. In kaj pomeni konec seznama?

495
00:38:21,220 --> 00:38:23,290
Kaj smo z uporabo, ki označuje konec našega čakalne vrste?

496
00:38:23,290 --> 00:38:25,970
Glava je vodja naše čakalno vrsto, začetek naše vrste.

497
00:38:25,970 --> 00:38:29,530
Kaj je konec naše čakalne vrste? [Dijaki] Velikost. Velikost >> točno.

498
00:38:29,530 --> 00:38:36,360
Torej, naši novi elementi iti na velikost, in elemente, ki jih bomo sprejeli off sname na glavo.

499
00:38:36,360 --> 00:38:45,390
Ko smo enqueue naslednji element, mi ga je dala ob velikosti.

500
00:38:45,390 --> 00:38:48,530
[Študent] Preden vložite, da, čeprav, je bila velikost 1, kajne?

501
00:38:48,530 --> 00:38:55,690
[Hardison] desno. Torej ni čisto pri velikosti. Velikost +, ne 1, vendar + glava.

502
00:38:55,690 --> 00:38:59,990
Ker smo vse, kar je premaknilo z glavo zneska.

503
00:38:59,990 --> 00:39:14,270
Torej, tukaj, zdaj imamo čakalne vrste za velikosti 1, ki se začne pri indeksu 1.

504
00:39:14,270 --> 00:39:20,730
Rep je indeks 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Študent] Kaj se zgodi, ko ste dequeue strings [0], in strune "reže v spomin

506
00:39:25,780 --> 00:39:29,420
Samo se izpraznijo, v bistvu, ali pa pozabil?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ja. V tem smislu smo jih kar pozabili.

508
00:39:34,700 --> 00:39:42,640
Če smo bili shranjevanje kopij njimi -

509
00:39:42,640 --> 00:39:46,310
veliko podatkovne strukture se pogosto shranjujejo svoje kopije elementov

510
00:39:46,310 --> 00:39:51,760
tako, da oseba, ki upravlja podatkovno strukturo ni treba skrbeti

511
00:39:51,760 --> 00:39:53,650
o tem, kje so vsi ti kazalci se dogaja.

512
00:39:53,650 --> 00:39:56,000
Struktura podatkov drži za vse, ima na vseh izvodih,

513
00:39:56,000 --> 00:39:59,580
zagotoviti, da vse ostaja ustrezno.

514
00:39:59,580 --> 00:40:03,140
Vendar je v tem primeru te podatkovne strukture le zaradi enostavnosti,

515
00:40:03,140 --> 00:40:05,580
niso izdelavo kopije vsega, kar smo shranjevanje v njih.

516
00:40:05,580 --> 00:40:08,630
[Študent] Torej je to stalen nabor -? >> Da.

517
00:40:08,630 --> 00:40:14,350
Če pogledamo nazaj, kaj je definicija te strukture je.

518
00:40:14,350 --> 00:40:19,110
To je samo standardni niz, kot ste videli,

519
00:40:19,110 --> 00:40:24,280
niz char * s.

520
00:40:24,280 --> 00:40:26,340
Ali to -? >> Ja, jaz sem samo spraševala

521
00:40:26,340 --> 00:40:29,130
Če boste na koncu zmanjkalo spomina, do neke mere,

522
00:40:29,130 --> 00:40:32,330
če imate vse te prazne lise v vašem array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, to je dobro izhodišče.

524
00:40:36,390 --> 00:40:41,530
>> Če pogledamo, kaj se dogaja sedaj na tem mestu,

525
00:40:41,530 --> 00:40:46,350
smo napolnili našo vrsto, kot je videti.

526
00:40:46,350 --> 00:40:50,390
Vendar pa smo v resnici ne napolni naše čakalne vrste

527
00:40:50,390 --> 00:40:57,710
saj imamo čakalno vrsto, ki je velikost 2, vendar pa se začne pri indeksu 1,

528
00:40:57,710 --> 00:41:02,160
kajti tam naš vodja kazalec.

529
00:41:02,160 --> 00:41:08,400
Kot ste rekli, da je ta element na strune [0], v indeksu 0, je v resnici ni.

530
00:41:08,400 --> 00:41:10,450
To ni v naši vrsti več.

531
00:41:10,450 --> 00:41:16,460
Samo ni motilo, da gredo v in prepisati, ko smo ga dequeued.

532
00:41:16,460 --> 00:41:18,700
Torej, čeprav izgleda, da smo zmanjka pomnilnika, res ne.

533
00:41:18,700 --> 00:41:23,270
To mesto je na voljo za nas, za uporabo.

534
00:41:23,270 --> 00:41:29,310
Primerno vedenje, če bi poskusil kaj 1. dequeue

535
00:41:29,310 --> 00:41:34,420
kot so "adijo", da bi se poslovil pop off.

536
00:41:34,420 --> 00:41:38,460
Zdaj naša vrsta se začne pri indeksu 2 in velikosti 1.

537
00:41:38,460 --> 00:41:42,240
In zdaj, če poskušamo enqueue nekaj več, recimo 50,

538
00:41:42,240 --> 00:41:47,880
50 mora iti v to mesto na indeksu 0

539
00:41:47,880 --> 00:41:51,270
ker je še vedno na voljo za nas. Da, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Ali je to zgodilo samodejno?

541
00:41:53,630 --> 00:41:56,150
[Hardison] To se ne zgodi kar samodejno. Kar morate storiti math

542
00:41:56,150 --> 00:42:00,380
da bi bilo delo, ampak predvsem tisto, kar smo naredili, je, da smo le ovije okrog.

543
00:42:00,380 --> 00:42:04,070
[Saad] In to je v redu, če ima to luknjo v sredini tega?

544
00:42:04,070 --> 00:42:08,720
[Hardison] To je, če lahko naredimo math deluje pravilno.

545
00:42:08,720 --> 00:42:15,470
>> In izkazalo se je, da je to pravzaprav ni tako težko storiti z mod operaterja.

546
00:42:15,470 --> 00:42:20,040
Tako kot sva s Cezarjem in šifriranega stvari,

547
00:42:20,040 --> 00:42:25,190
s mod, lahko pridemo stvari do ovijte okoli in nadaljuj

548
00:42:25,190 --> 00:42:28,090
okoli in okoli in okoli z našo vrsto,

549
00:42:28,090 --> 00:42:32,180
vodenje, da glava kazalec premika.

550
00:42:32,180 --> 00:42:38,840
Obvestilo, da je velikost vedno spoštuje število elementov dejansko v čakalni vrsti.

551
00:42:38,840 --> 00:42:43,110
In to je samo za glavo kazalec, ki ohranja kolesarjenje skozi.

552
00:42:43,110 --> 00:42:49,660
Če pogledamo, kaj se je tu zgodilo, če se vrnemo na začetek,

553
00:42:49,660 --> 00:42:55,020
in si ogledate, kaj se zgodi v glavi

554
00:42:55,020 --> 00:42:58,240
ko smo enqueue kaj, nič se ni zgodilo v glavo.

555
00:42:58,240 --> 00:43:00,970
Ko smo enqueued nekaj drugega, nič se ni zgodilo v glavo.

556
00:43:00,970 --> 00:43:04,130
Takoj ko smo dequeued nekaj, glava se dvigne za eno.

557
00:43:04,130 --> 00:43:06,600
Mi enqueued kaj ne zgodi nič v glavo.

558
00:43:06,600 --> 00:43:11,060
Ko smo dequeue nekaj, kar naenkrat postane poveča za glavo.

559
00:43:11,060 --> 00:43:14,660
Ko smo enqueue kaj ne zgodi nič v glavo.

560
00:43:14,660 --> 00:43:20,240
>> Kaj bi se zgodilo v tem trenutku, če bi dequeue kaj spet?

561
00:43:20,240 --> 00:43:23,240
Vsak misli? Kaj bi se zgodilo z glavo?

562
00:43:23,240 --> 00:43:27,190
Kaj bi se zgodilo z glavo

563
00:43:27,190 --> 00:43:32,990
če bi dequeue kaj drugega?

564
00:43:32,990 --> 00:43:35,400
Glava sedaj je na indeksu 2,

565
00:43:35,400 --> 00:43:38,920
kar pomeni, da je vodja vrsti je strings [2].

566
00:43:38,920 --> 00:43:44,280
[Študent], ki vrne 0? >> Treba je vrniti na 0. Morala bi zaviti nazaj okoli, tako je.

567
00:43:44,280 --> 00:43:48,440
Do sedaj, vsakič, ko smo poklicali dequeue, smo se doda 1 v glavo,

568
00:43:48,440 --> 00:43:50,960
dodate na glavo, dodamo eno v glavo, dodamo eno v glavo.

569
00:43:50,960 --> 00:43:58,400
Takoj, ko glavo, da kazalec pride do zadnjega indeksa v naši matriki,

570
00:43:58,400 --> 00:44:05,650
potem moramo ga ovijte okoli nazaj na začetek, pojdi nazaj na 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Kaj določa storilnost čakalni vrsti na kup?

572
00:44:09,900 --> 00:44:13,120
[Hardison] V tem primeru, smo ravnokar z # opredeljena konstantna. >> Redu.

573
00:44:13,120 --> 00:44:19,590
[Hardison] V dejanski datoteke. C, lahko greš v muck in z njo tudi nekaj

574
00:44:19,590 --> 00:44:21,710
in da bo tako velika ali malo, kot želite.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Torej, ko delaš to vrsto, kako bo računalnik vedel

576
00:44:25,310 --> 00:44:29,120
kako velik želite sklad je?

577
00:44:29,120 --> 00:44:31,700
[Hardison] To je odlično vprašanje.

578
00:44:31,700 --> 00:44:34,800
Obstaja nekaj načinov. Eden od njih je, da šele določiti vnaprej

579
00:44:34,800 --> 00:44:42,050
in reči, to se bo čakalna vrsta, ki ima 4 elemente ali elemente 50 ali 10.000.

580
00:44:42,050 --> 00:44:45,430
Drugi način je, da to, kaj ljudje počnejo izdaja hekerjev

581
00:44:45,430 --> 00:44:52,310
in ustvariti funkcije imajo svoje čakalne vrste rastejo kot dinamično dobili več stvari dodal noter

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Torej iti s prvo možnostjo, kaj skladnja ne uporabljate

583
00:44:54,740 --> 00:44:57,830
povedati program, kaj je velikost čakalne vrste?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Torej gremo ven iz tega.

585
00:45:04,780 --> 00:45:12,650
Še vedno sem v stack.c tukaj, tako da sem šele tekoč, da se pomaknete do vrha tukaj.

586
00:45:12,650 --> 00:45:17,920
Ali lahko vidite to tukaj? To je # define zmogljivosti 10.

587
00:45:17,920 --> 00:45:24,600
In to je skoraj popolnoma enaka sintaksa, da imamo v čakalni vrsti.

588
00:45:24,600 --> 00:45:28,390
Razen v vrsti, smo dobili, da ekstra struct polje tukaj.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Mislil sem, da je zmogljivost pomenilo zmogljivosti za niz.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> To je največja dolžina besede. >> Razumem.

591
00:45:36,770 --> 00:45:41,180
Ja. Zmogljivost tukaj - to je odlična točka.

592
00:45:41,180 --> 00:45:44,000
In to je nekaj, kar je zapleteno

593
00:45:44,000 --> 00:45:49,480
ker tisto, kar smo tukaj prijavljeni niz char * s.

594
00:45:49,480 --> 00:45:52,770
Paleto kazalcev.

595
00:45:52,770 --> 00:45:56,690
To je niz znakov.

596
00:45:56,690 --> 00:46:01,690
To je verjetno tisto, kar ste videli, ko ste bili razglasitvi svoje rezerve za datoteko I / O,

597
00:46:01,690 --> 00:46:06,840
Ko sem bil ustvarjanje niza ročno na kupu.

598
00:46:06,840 --> 00:46:09,090
Toda tisto, kar smo dobili, je tu niz char * s.

599
00:46:09,090 --> 00:46:13,400
Torej, to je niz kazalcev.

600
00:46:13,400 --> 00:46:18,350
Pravzaprav, če smo povečali nazaj in pogledamo, kaj se dogaja

601
00:46:18,350 --> 00:46:23,140
v predstavitvi, boste videli, da so dejanske elemente, znakovni podatki

602
00:46:23,140 --> 00:46:26,180
niso shranjeni v matriki same.

603
00:46:26,180 --> 00:46:42,690
Kaj je shranjen v naši matriki tukaj so kazalci na znakovnih podatkov.

604
00:46:42,690 --> 00:46:52,560
Ok. Tako smo videli, kako je velikost čakalne vrste je tako kot v plasteh,

605
00:46:52,560 --> 00:46:58,670
velikost vedno upošteva število elementov, ki so trenutno v čakalni vrsti.

606
00:46:58,670 --> 00:47:02,720
Po tem, ko enqueues 2, velikost je 2.

607
00:47:02,720 --> 00:47:07,110
Po izdelavi dequeue velikost je trenutno 1.

608
00:47:07,110 --> 00:47:09,330
Po tem, ko še enqueue velikost je nazaj do 2.

609
00:47:09,330 --> 00:47:12,340
Torej je velikost vsekakor upošteva število elementov v vrsti,

610
00:47:12,340 --> 00:47:15,580
nato pa glavo samo ohranja kolesarjenja.

611
00:47:15,580 --> 00:47:20,210
To gre z 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
In vsakič, ko pravimo dequeue, postane vodja kazalec poveča na naslednjo indeks.

613
00:47:25,620 --> 00:47:29,930
In če je glava je približno iti čez, da zanke nazaj okoli 0.

614
00:47:29,930 --> 00:47:34,870
Torej s tem, lahko zapišemo dequeue funkcijo.

615
00:47:34,870 --> 00:47:40,200
In bomo zapustili enqueue funkcijo za fantje namesto izvajati.

616
00:47:40,200 --> 00:47:45,880
>> Ko smo dequeue element iz naše vrsti,

617
00:47:45,880 --> 00:47:55,490
Kaj je bila prva stvar, ki Daniel naredili, ko smo začeli pisati pop funkcijo skladih?

618
00:47:55,490 --> 00:48:00,490
Naj slišim od nekoga, ki je še ne govori.

619
00:48:00,490 --> 00:48:06,710
Poglejmo, Saad, se spomniš, kaj si Daniel, kot prvo stvar, ko jo je napisal pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] je bil, da je - >> Preizkusil je za nekaj.

621
00:48:08,860 --> 00:48:12,140
[Saad] Če je velikost večja od 0. >> Točno tako.

622
00:48:12,140 --> 00:48:14,390
In kaj je bilo to testiranje?

623
00:48:14,390 --> 00:48:19,090
[Saad] To je bilo testiranje, da vidim, če je kaj notri polje.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ja. Točno tako. Torej, ne morete pop bo kaj kupu, če je prazna.

625
00:48:23,210 --> 00:48:26,510
Prav tako ne morete ničesar dequeue iz čakalne vrste, če je prazna.

626
00:48:26,510 --> 00:48:30,420
Kaj je prva stvar, moramo storiti v naši dequeue funkcije tukaj, ti misliš?

627
00:48:30,420 --> 00:48:33,860
[Saad] Če je velikost večja od 0? >> Ja.

628
00:48:33,860 --> 00:48:37,710
V tem primeru, sem dejansko samo preskušene, da vidim, če je 0.

629
00:48:37,710 --> 00:48:42,240
Če je 0, se lahko vrnemo null.

630
00:48:42,240 --> 00:48:45,280
Ampak točno ista logika.

631
00:48:45,280 --> 00:48:49,110
In kaj je še s tem.

632
00:48:49,110 --> 00:48:54,600
Če velikost ni 0, če je element, ki ga želimo dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Na čelu? >> Točno tako.

634
00:48:58,550 --> 00:49:01,720
Mi lahko samo potegnite prvi element v naši vrsti

635
00:49:01,720 --> 00:49:07,040
z dostopom do elementa na glavi.

636
00:49:07,040 --> 00:49:14,630
Nič noro.

637
00:49:14,630 --> 00:49:19,620
Po tem, kaj naj storimo? Kaj se je zgodilo?

638
00:49:19,620 --> 00:49:23,740
Kaj je bila druga stvar, ki smo govorili v dequeue?

639
00:49:23,740 --> 00:49:28,130
Dve stvari, da se zgodi, ker se je naša vrsta spremenilo.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Zmanjšanje velikosti. >> Moramo zmanjšati velikost in povečati glavo? Točno tako.

641
00:49:35,640 --> 00:49:40,600
Za povečanje glavo, ne moremo kar slepo poveča glavo, se spomnite.

642
00:49:40,600 --> 00:49:45,080
Ne moremo narediti queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Moramo tudi to mod po zmogljivosti.

644
00:49:51,630 --> 00:49:54,740
In zakaj mod z zmogljivostjo, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Ker je ovijte okoli. >> Točno tako.

646
00:49:58,680 --> 00:50:04,750
Mi mod z zmogljivostjo, saj ima za zavijanje nazaj okoli 0.

647
00:50:04,750 --> 00:50:07,400
Torej, zdaj, v tem trenutku lahko naredimo tisto, Daniel je rekel.

648
00:50:07,400 --> 00:50:12,700
Mi lahko padanje višine.

649
00:50:12,700 --> 00:50:29,170
In potem bomo lahko samo vrne element, ki je bil na vrhu čakalne vrste.

650
00:50:29,170 --> 00:50:34,000
To izgleda nekako Čvornovat na prvi. Morda imate vprašanje. Prosim?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Zakaj je prvi na vrhu čakalne vrste? Če ne gre?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Izhaja iz četrti vrstici od spodaj.

653
00:50:42,480 --> 00:50:46,060
Ko smo test, da se prepriča, da je naša vrsta ni prazna,

654
00:50:46,060 --> 00:50:54,100
smo izvlecite char * prvi, smo izvlekli element, ki je sedel na sedežu indeksa

655
00:50:54,100 --> 00:50:58,680
naše polje, naše godala diod, in zahtevajo, da >> 1.?

656
00:50:58,680 --> 00:51:04,500
[Hardison] In smo rekli prej. Ja.

657
00:51:04,500 --> 00:51:09,850
Samo, da spremlja, da, zakaj misliš, da bi moral to storiti?

658
00:51:09,850 --> 00:51:18,270
[Sam] Vsak, ki je prvo pravkar vrnil q.strings [q.head]? >> Ja.

659
00:51:18,270 --> 00:51:23,830
>> Ker delamo to spreminjanja q.head z mod funkcijo,

660
00:51:23,830 --> 00:51:27,810
in ni način za to, da se v povratni vod tudi.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Točno tako. Si spot on. Sam je popolnoma spot on.

662
00:51:31,640 --> 00:51:36,800
Zato smo morali potegniti ven prvi element v naši vrsti in ga shrani v spremenljivko

663
00:51:36,800 --> 00:51:43,030
Kajti to vrstico, kjer smo pravkar q.head,

664
00:51:43,030 --> 00:51:47,030
obstaja mod operater ni nekaj, kar lahko storimo

665
00:51:47,030 --> 00:51:51,230
in se ne začne veljati na glavo, ne da bi - v eni vrstici.

666
00:51:51,230 --> 00:51:54,480
Tako smo dejansko morali potegniti ven prvi del, nato nastavite glavo,

667
00:51:54,480 --> 00:52:00,430
prilagoditi velikost, in nato vrne element, ki ga potegnil ven.

668
00:52:00,430 --> 00:52:02,680
In to je nekaj, kar boste videli bomo prišli kasneje s

669
00:52:02,680 --> 00:52:04,920
povezani seznam, kot smo igral z njimi.

670
00:52:04,920 --> 00:52:08,410
Pogosto, ko ste sprostitve ali odstranjevanje, povezanih seznamov

671
00:52:08,410 --> 00:52:13,500
se morate zavedati, naslednji element, naslednji kazalec na povezanem seznamu

672
00:52:13,500 --> 00:52:16,330
Pred odstranjevanjem sedanjega.

673
00:52:16,330 --> 00:52:23,580
Ker drugače si vrgel proč informacije o tem, kaj je ostalo na seznamu.

674
00:52:23,580 --> 00:52:34,160
Zdaj pa, če greš na vaši napravi, morate odpreti queue.c-X-ven iz tega.

675
00:52:34,160 --> 00:52:39,390
Torej, če sem odprl queue.c, naj povečaj tukaj,

676
00:52:39,390 --> 00:52:44,970
boste videli, da imate podobne usmerjeno datoteko.

677
00:52:44,970 --> 00:52:49,200
Podobno usmerjen datoteka s tem, kar smo imeli prej s stack.c.

678
00:52:49,200 --> 00:52:54,690
Imamo našo struct za določeno vrsto tako, kot smo videli na diapozitivih.

679
00:52:54,690 --> 00:52:59,870
>> Imamo enqueue funkcijo, ki je za vas.

680
00:52:59,870 --> 00:53:04,340
In imamo dequeue funkcijo tukaj.

681
00:53:04,340 --> 00:53:06,870
The dequeue funkcija v datoteki je mrtva črka na papirju,

682
00:53:06,870 --> 00:53:13,230
ampak ga bom dal nazaj gor na PowerPointu, tako da ga lahko vnesete v, če želite.

683
00:53:13,230 --> 00:53:16,690
Torej, za naslednjih 5 minut ali tako, fantje delajo na enqueue

684
00:53:16,690 --> 00:53:22,570
kar je skoraj ravno nasprotno od dequeue.

685
00:53:22,570 --> 00:53:29,560
Če ne bi bilo treba prilagoditi glavo, ko ste enqueueing, ampak kaj imaš prilagoditi?

686
00:53:29,560 --> 00:53:38,920
Velikost. Torej, ko enqueue, ostane nedotaknjeno glavo, dobi spremenili velikost.

687
00:53:38,920 --> 00:53:46,920
Vendar pa se malo - imeli boste igral s tem mod

688
00:53:46,920 --> 00:53:57,560
da ugotovimo, kaj indeks je treba nov element vstavi.

689
00:53:57,560 --> 00:54:03,080
Tako da bom dal vidva malo, dal dequeue nazaj na diapozitivu,

690
00:54:03,080 --> 00:54:05,200
in kot fantje so vprašanja, ki jih zakričal, da bomo lahko

691
00:54:05,200 --> 00:54:09,220
Vsi govorijo o njih kot skupina.

692
00:54:09,220 --> 00:54:13,960
Tudi pri velikosti, Ne - če nastavite velikost, lahko vedno le -

693
00:54:13,960 --> 00:54:18,720
imaš mod velikost kdaj? [Daniel] No >> Nimaš mod velikost, prav.

694
00:54:18,720 --> 00:54:24,260
Ker bo velikost vedno, če Menda - ob predpostavki, da ste vodenje stvari ustrezno,

695
00:54:24,260 --> 00:54:30,840
velikost bo vedno med 0 in 3.

696
00:54:30,840 --> 00:54:38,680
Če imate mod, ko delaš enqueue?

697
00:54:38,680 --> 00:54:41,060
[Študent] Samo za glavo. >> Samo za glavo, točno.

698
00:54:41,060 --> 00:54:44,620
In zakaj moraš mod sploh enqueue?

699
00:54:44,620 --> 00:54:48,830
Ko je situacija, v kateri bi si morali mod?

700
00:54:48,830 --> 00:54:53,630
[Študent] Če imate stvari na prostorih, kot je prostori 1 in 2,

701
00:54:53,630 --> 00:54:55,950
in potem si moral nekaj dodati na 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ja, točno. Torej, če tvoja glava kazalec na samem koncu,

703
00:55:02,570 --> 00:55:14,210
ali, če je vaša velikost plus glavo večji, oziroma, da se bo ovijte okoli čakalne vrste.

704
00:55:14,210 --> 00:55:17,830
>> Torej, v tem primeru, da imava tukaj na diapozitivu prav zdaj,

705
00:55:17,830 --> 00:55:24,370
če želim enqueue nekaj prav zdaj,

706
00:55:24,370 --> 00:55:31,110
želimo enqueue nekaj na indeksu 0.

707
00:55:31,110 --> 00:55:35,450
Torej, če pogledaš na katerih gre 50 in pozivam enqueue 50,

708
00:55:35,450 --> 00:55:40,840
gre tam doli na dnu. To gre v 0 indeksa.

709
00:55:40,840 --> 00:55:44,160
Ta nadomešča "hi", ki je bil že dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Ne boste poskrbeli, da dequeue že?

711
00:55:46,210 --> 00:55:50,550
Zakaj je to naredil z glavo v enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, tako da ne boste spremenili glavo, mi je žal.

713
00:55:55,770 --> 00:56:02,310
Vendar pa boste morali uporabiti mod operaterja, ko boste dostop

714
00:56:02,310 --> 00:56:04,250
element, ki ga želite enqueue, ko boste dostop

715
00:56:04,250 --> 00:56:06,960
Naslednji element v vaši vrsti.

716
00:56:06,960 --> 00:56:10,960
[Bazilika] nisem storil, in sem dobil "uspeh" na tam.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, jaz razumem, kaj govoriš.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Torej Nisi ti - pravkar naredil na q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Ja. Pravkar sem spremenil straneh, nisem storil ničesar z glavo.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Vi ne dejansko imajo ponastaviti glavo, da je karkoli,

721
00:56:24,300 --> 00:56:31,650
ko pa indeks v matriki godala,

722
00:56:31,650 --> 00:56:39,500
ste dejansko imajo, da gredo naprej in izračunati, če je naslednji element,

723
00:56:39,500 --> 00:56:44,230
ker withe sveženj, naslednji element v vaših žetonov je bil vedno

724
00:56:44,230 --> 00:56:48,740
V indeksu, ki ustreza velikosti.

725
00:56:48,740 --> 00:56:55,850
Če se ozremo nazaj na našo funkcijo dimnika pritiskom,

726
00:56:55,850 --> 00:57:03,100
smo lahko vedno Prebirati v naši novi element desno na velikost indeksa.

727
00:57:03,100 --> 00:57:06,710
Ker v čakalni vrsti, ne moremo narediti, da

728
00:57:06,710 --> 00:57:10,340
ker če smo že pri tem primeru,

729
00:57:10,340 --> 00:57:18,130
če bi 50 enqueued naš nov niz desno na strune [1]

730
00:57:18,130 --> 00:57:20,540
ki jih ne želite storiti.

731
00:57:20,540 --> 00:57:41,200
Radi bi imeli nov niz iti na indeksu 0.

732
00:57:41,200 --> 00:57:44,320
>> Ali kdo - ja? [Študent] Imam vprašanje, vendar to ni res povezana.

733
00:57:44,320 --> 00:57:48,160
Kaj pomeni, če nekdo kliče le nekaj podobnega PRED kazalca?

734
00:57:48,160 --> 00:57:51,260
Kaj je to ime kratica za? Vem, da je samo ime.

735
00:57:51,260 --> 00:57:59,110
[Hardison] PRED kazalec? Pa poglejmo. V kakšnem kontekstu?

736
00:57:59,110 --> 00:58:01,790
[Študent], je bil za vložek. Lahko vas kasneje, če hočeš

737
00:58:01,790 --> 00:58:03,920
ker to ni res povezana, vendar sem -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Od kodo vstaviti Davida iz predavanja?

739
00:58:07,300 --> 00:58:10,860
Mi lahko potegnite navzgor in da je govoriti o tem.

740
00:58:10,860 --> 00:58:15,550
O tem bomo govorili, da je poleg, ko bomo prišli do povezanih seznamov.

741
00:58:15,550 --> 00:58:21,440
>> Torej, kaj je res hitro pogledati, kaj enqueue funkcija izgleda.

742
00:58:21,440 --> 00:58:26,530
Kaj je bila prva stvar, da ljudje poskušali narediti v vašem enqueue vrsti? V tej vrsti?

743
00:58:26,530 --> 00:58:29,960
Podobno kot tisto, kar si naredil za potiskanje dimnik.

744
00:58:29,960 --> 00:58:32,080
Kaj si naredil, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nerazumljiv]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Točno tako. Če je (q.size == SPOSOBNOSTI) -

747
00:58:45,700 --> 00:58:54,720
Moram dati svoje naramnice na pravem mestu - vrne false.

748
00:58:54,720 --> 00:59:01,370
Povečaj malo. Ok.

749
00:59:01,370 --> 00:59:03,800
Zdaj, kaj je naslednja stvar, ki smo morali narediti?

750
00:59:03,800 --> 00:59:11,370
Tako kot pri plasteh, in se vstavi na pravem mestu.

751
00:59:11,370 --> 00:59:16,010
In kaj je pravi kraj za vključitev tega?

752
00:59:16,010 --> 00:59:23,170
V svežnju je bil indeks velikost, s tem, da ni čisto tako.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Imam q.head--ali - >> q.strings? >> Ja.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod ZMOGLJIVOSTI]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Verjetno smo želeli postaviti oklepaje okoli tega

756
00:59:42,740 --> 00:59:48,830
tako da smo dobili ustrezno prednost in da je cleart vsem.

757
00:59:48,830 --> 00:59:55,800
In določiti, da je enaka? >> Za Str? >> Za Str. Čudovito.

758
00:59:55,800 --> 01:00:00,160
In zdaj, kaj je zadnja stvar, ki jo moramo narediti?

759
01:00:00,160 --> 01:00:06,780
Tako kot smo to storili v sklad. >> Prirastek velikost? >> Prirastek velikosti.

760
01:00:06,780 --> 01:00:13,830
Boom. In potem, ker je za zagon kode pravkar vrnil false privzeto

761
01:00:13,830 --> 01:00:27,460
želimo spremeniti to res, če bo šlo vse skozi in vse gre dobro.

762
01:00:27,460 --> 01:00:33,050
V redu. To je veliko informacij za oddelek.

763
01:00:33,050 --> 01:00:39,480
Nismo čisto mimo. Želimo govoriti o zelo hitro posamezno povezanih seznamov.

764
01:00:39,480 --> 01:00:44,010
Bom dal to gor, tako da se lahko vrnete na kasneje.

765
01:00:44,010 --> 01:00:50,850
Toda vrnimo k naši predstavitvi za samo nekaj več diapozitivov.

766
01:00:50,850 --> 01:00:53,790
Torej je enqueue TODO, zdaj smo to naredili.

767
01:00:53,790 --> 01:00:57,430
>> Zdaj pa si oglejte na posamezno povezanih seznamov.

768
01:00:57,430 --> 01:01:00,040
Pogovarjala sva se o njih malo bolj v predavanju.

769
01:01:00,040 --> 01:01:02,540
Koliko od vas videl demo, kjer smo imeli ljudi

770
01:01:02,540 --> 01:01:08,220
nerodno obrnjena drug drugega in gospodarstvo številke? >> Bil sem v to.

771
01:01:08,220 --> 01:01:16,620
>> Kaj si vi mislite? Je to, upajmo, da demistificirati te malo?

772
01:01:16,620 --> 01:01:25,990
S seznama, se je izkazalo, da imamo opravka s tem tipom, da bomo lahko pokličete vozlišče.

773
01:01:25,990 --> 01:01:32,520
Ker je s čakalno vrsto in s sklada smo imeli konstrukti, da bi pravimo vrsto v plasteh,

774
01:01:32,520 --> 01:01:34,860
smo imeli te nove vrsto v odvodnikom vrst,

775
01:01:34,860 --> 01:01:39,240
Tukaj je seznam res tako sestavljen iz kup vozlišč.

776
01:01:39,240 --> 01:01:45,920
Na enak način, kot so strune le kup znakov, vse se vrstijo drug poleg drugega.

777
01:01:45,920 --> 01:01:50,650
Povezani seznam je samo vozlišče in drugo vozlišče in drugo vozlišče in drugo vozlišče.

778
01:01:50,650 --> 01:01:55,080
In ne razbije vsa vozlišča med seboj in jih shranite contiguously

779
01:01:55,080 --> 01:01:58,090
Vse je v redu druga ob drugi v spominu,

780
01:01:58,090 --> 01:02:04,470
ob tem poleg kazalec nam omogoča, da shranite vozlišča kadar koli naključno.

781
01:02:04,470 --> 01:02:10,500
In potem nekako žice jih vse skupaj na točko od enega do drugega.

782
01:02:10,500 --> 01:02:15,850
>> In kaj je velika prednost, da je to že več kot matriko?

783
01:02:15,850 --> 01:02:21,680
Več shranjevanje vsega, kar contiguously samo zaljubljen drug poleg drugega?

784
01:02:21,680 --> 01:02:24,190
Se spomniš? Ja? >> Dinamično dodeljevanje pomnilnika?

785
01:02:24,190 --> 01:02:27,220
>> Dinamično dodeljevanje pomnilnika, v kakšnem smislu?

786
01:02:27,220 --> 01:02:31,780
[Študent] V da lahko obdržite tako da je večji in vam ni treba premakniti vaš celoten niz?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Točno tako. Torej, z vrsto, če želite, da bi nov element v sredini,

788
01:02:40,940 --> 01:02:45,320
boste morali preusmeriti vse, da bo prostor.

789
01:02:45,320 --> 01:02:47,880
In kot smo govorili s čakalno vrsto,

790
01:02:47,880 --> 01:02:50,080
zato se držimo za glavo, da kazalec,

791
01:02:50,080 --> 01:02:52,050
tako da ne bomo ves čas premika stvari.

792
01:02:52,050 --> 01:02:54,520
Ker to postane drago, če imaš velik nabor

793
01:02:54,520 --> 01:02:57,130
in ste ves čas počne teh naključnih vstavitve.

794
01:02:57,130 --> 01:03:00,820
Ker s seznamom, vse, kar morate storiti, je vrgel na novo vozlišče,

795
01:03:00,820 --> 01:03:06,330
prilagoditi kazalci, in ste končali.

796
01:03:06,330 --> 01:03:10,940
Kaj je zanič to?

797
01:03:10,940 --> 01:03:16,830
Ne glede na dejstvo, da to ni tako enostavno delati kot matriko? Ja?

798
01:03:16,830 --> 01:03:22,980
[Daniel] No, mislim, da je veliko težje pridejo do določenega elementa v povezanem seznamu?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Ne moreš skočiti na poljuben element v sredini svojega povezanega seznama.

800
01:03:30,470 --> 01:03:33,800
Kako boste morali to storiti namesto tega? >> Moraš stopiti skozi celotno stvar.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ja. Moraš iti skozi enega naenkrat, eno za drugo.

802
01:03:35,660 --> 01:03:38,480
To je ogromna - to je bolečina.

803
01:03:38,480 --> 01:03:41,550
Kaj drugega - tam je še en propad s tem.

804
01:03:41,550 --> 01:03:45,340
[Bazilika] Saj ne more iti naprej in nazaj? Moraš iti v eno smer?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ja. Torej, kako bomo rešili, da je včasih?

806
01:03:48,570 --> 01:03:53,370
[Bazilika] dvojno povezani seznam? >> Točno tako. Obstaja dvojno povezani seznam.

807
01:03:53,370 --> 01:03:55,540
Obstajajo tudi - žal?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Ali je to enako kot z PRED stvar, ki -

809
01:03:57,620 --> 01:04:01,090
Pravkar sem se spomnil, kaj ni to tisto, kar PRED stvar je za?

810
01:04:01,090 --> 01:04:05,850
Ali ni to v času med dvakrat in posamično?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Oglejmo si, kaj točno počne.

812
01:04:10,020 --> 01:04:15,760
Torej, gremo. Tukaj je seznam kodo.

813
01:04:15,760 --> 01:04:25,620
Tukaj imamo predptr, tukaj. Je to tisto, kar si govorila?

814
01:04:25,620 --> 01:04:30,750
Torej, to je - on je sprostilo seznam in hoče za shranjevanje kazalec na njej.

815
01:04:30,750 --> 01:04:35,000
To ni dvakrat, posamično povezani seznami.

816
01:04:35,000 --> 01:04:40,090
Lahko govorimo več o tem kasneje, ker to govorim o sprostitvi seznam

817
01:04:40,090 --> 01:04:42,900
in želim pokazati nekatere druge stvari prvi.

818
01:04:42,900 --> 01:04:51,480
ampak to je samo - to je spomnil na vrednost PTR

819
01:04:51,480 --> 01:04:54,170
[Študent] Oh, to je Prejššnji kazalec? >> Ja.

820
01:04:54,170 --> 01:05:04,070
Tako da bomo lahko nato prirastek PTR sam, preden smo nato brezplačno, kar je predptr.

821
01:05:04,070 --> 01:05:09,130
Ker ne moremo brez ptr in nato razpis ptr = ptr drugega, kajne?

822
01:05:09,130 --> 01:05:11,260
To bi bilo slabo.

823
01:05:11,260 --> 01:05:20,940
Torej, da vidimo, nazaj z njim.

824
01:05:20,940 --> 01:05:23,900
>> Druga slaba stvar je, da medtem seznamov z vrsto

825
01:05:23,900 --> 01:05:26,520
imamo samo vse elemente sami zloženi drug poleg drugega,

826
01:05:26,520 --> 01:05:29,050
Tukaj smo uvedli tudi ta kazalec.

827
01:05:29,050 --> 01:05:34,060
Torej je dodaten kos pomnilnika, ki ga bomo morali uporabiti

828
01:05:34,060 --> 01:05:37,910
za vsak element, ki smo hranjenje v našem seznamu.

829
01:05:37,910 --> 01:05:40,030
Smo dobili prilagodljivost, vendar pa prihaja v ceno.

830
01:05:40,030 --> 01:05:42,230
Na voljo je s tem obdobju stroške,

831
01:05:42,230 --> 01:05:45,270
in gre s tem spomina stroškov preveč.

832
01:05:45,270 --> 01:05:47,800
Čas, v smislu, da se moramo zdaj iti skozi vsak element v matriki

833
01:05:47,800 --> 01:05:58,670
da bi našli enega na indeksu 10, ali da bi bil indeks 10 v matriko.

834
01:05:58,670 --> 01:06:01,230
>> Samo res hitro, ko smo načrt iz teh seznamov,

835
01:06:01,230 --> 01:06:05,980
Običajno imamo na čelu seznama ali prvi kazalec seznama

836
01:06:05,980 --> 01:06:08,010
in ne pozabite, da je to pravi kazalec.

837
01:06:08,010 --> 01:06:11,100
To je samo 4 bajte. To ni dejanski Vozel sama.

838
01:06:11,100 --> 01:06:17,120
Torej vidite, da nima int vrednost v njem, ne naslednji kazalec v njem.

839
01:06:17,120 --> 01:06:20,790
To je dobesedno le kazalec.

840
01:06:20,790 --> 01:06:23,550
To se dogaja, da kažejo na nekaj, kar je dejansko vozlišče struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] Kazalec se imenuje vozel? >> To je - ne. To je pokazatelj, kaj vozlišča tipa.

842
01:06:28,480 --> 01:06:32,540
To je kazalec na vozlišče struct. >> V redu.

843
01:06:32,540 --> 01:06:36,870
Graf na levi, na desni strani kode.

844
01:06:36,870 --> 01:06:42,190
Lahko jo nastavite na nič, kar je dober način za začetek.

845
01:06:42,190 --> 01:06:49,850
Ko ga diagram, ali boste napisali, da za nično, ali si dal črto skozi to všeč.

846
01:06:49,850 --> 01:06:53,910
>> Eden izmed najlažjih načinov za delo s seznami,

847
01:06:53,910 --> 01:06:57,430
in vas prosimo, ne tako pripnite in dodajte videti razlike med obema,

848
01:06:57,430 --> 01:07:01,320
vendar prepending je vsekakor lažje.

849
01:07:01,320 --> 01:07:05,790
Ko pripnite, to je, če boste - če prepend (7),

850
01:07:05,790 --> 01:07:10,050
greš in ustvariti vozlišča struct

851
01:07:10,050 --> 01:07:13,870
in nastavite najprej opozoriti na to, ker zdaj, saj smo jo pripeta,

852
01:07:13,870 --> 01:07:17,240
to se dogaja, da se na začetku seznama.

853
01:07:17,240 --> 01:07:22,540
Če bomo prepend (3), ki ustvari novo vozlišče, zdaj pa je pred 3 7.

854
01:07:22,540 --> 01:07:31,130
Torej smo v bistvu potiska stvari na našem seznamu.

855
01:07:31,130 --> 01:07:34,720
Sedaj lahko vidite, da prepend, včasih ljudje pravijo potiskanje,

856
01:07:34,720 --> 01:07:39,600
ker si prizadeva za nov element na seznamu.

857
01:07:39,600 --> 01:07:43,270
To je tako enostavno, da se črta na sprednji strani seznama.

858
01:07:43,270 --> 01:07:45,650
Tako bodo ljudje pogosto imenujejo, da pop.

859
01:07:45,650 --> 01:07:52,200
In na ta način, lahko posnemajo sveženj z uporabo povezani seznam.

860
01:07:52,200 --> 01:07:57,880
Ops. Žal mi je, zdaj smo dobili v za dodajanje. Torej, tukaj smo pripeta (7), zdaj smo prepend (3).

861
01:07:57,880 --> 01:08:02,600
Če želimo nekaj drugega, pripeta na tem seznamu, če bomo pripeta (4),

862
01:08:02,600 --> 01:08:06,540
potem bi imeli 4, nato 3, nato 7.

863
01:08:06,540 --> 01:08:14,220
Torej, potem bi lahko pop in odstranite 4, odstrani 3, 7 odstraniti.

864
01:08:14,220 --> 01:08:16,500
Pogosto bolj intuitiven način, da razmišljajo o tem, je z dodati.

865
01:08:16,500 --> 01:08:20,310
Tako sem grafično, kaj bo to videti z dodati tukaj.

866
01:08:20,310 --> 01:08:23,380
Tu priložen (7) ne izgleda nič drugače

867
01:08:23,380 --> 01:08:25,160
zato, ker je samo en element v seznamu.

868
01:08:25,160 --> 01:08:28,620
In dodajo (3) ocenjuje, da je konec.

869
01:08:28,620 --> 01:08:31,020
Mogoče si lahko ogledate sedaj trik z append

870
01:08:31,020 --> 01:08:36,600
je, da ker smo samo vedeti, kje je začetek seznama je

871
01:08:36,600 --> 01:08:39,450
priložiti k seznamu boste morali hoditi vso pot skozi seznam

872
01:08:39,450 --> 01:08:46,500
priti do konca, se ustavite, nato pa graditi svoje vozlišče in Prebirati vse navzdol.

873
01:08:46,500 --> 01:08:50,590
Žice vse stvari gor.

874
01:08:50,590 --> 01:08:55,170
Torej, z prepend, kot smo pravkar ripped skozi to res hitro,

875
01:08:55,170 --> 01:08:58,170
Ko pripnite na seznam, je dokaj preprost.

876
01:08:58,170 --> 01:09:02,960
>> Naredite svojo novo vozlišče, vključuje nekaj dinamično dodeljevanje pomnilnika.

877
01:09:02,960 --> 01:09:09,830
Torej, tukaj delamo vozlišče struct z malloc.

878
01:09:09,830 --> 01:09:14,710
Tako smo z malloc, saj boste, da razveljavi spomin za nas, za kasneje

879
01:09:14,710 --> 01:09:20,350
saj ne želimo, da ta - želimo, da ta spomin prisotna že dolgo časa.

880
01:09:20,350 --> 01:09:25,350
In smo dobili kazalec prostora v pomnilniku, ki smo ga pravkar dodeljena.

881
01:09:25,350 --> 01:09:29,260
Mi uporabljamo velikost vozlišča, ne bomo povzeli polja.

882
01:09:29,260 --> 01:09:31,899
Ne ročno ustvarjanje število bajtov,

883
01:09:31,899 --> 01:09:39,750
namesto tega uporabite sizeof, tako da vemo, da ste dobili ustrezno število bajtov.

884
01:09:39,750 --> 01:09:43,660
Mi se prepričajte, da preizkusite, da je naš klic malloc uspelo.

885
01:09:43,660 --> 01:09:47,939
To je nekaj, kar si želim početi v splošno.

886
01:09:47,939 --> 01:09:52,590
V sodobnih strojev, zmanjkuje pomnilnika ni nekaj, kar je preprosto

887
01:09:52,590 --> 01:09:56,610
razen če ste dodeljevanje tono stvari in kar ogromen seznam,

888
01:09:56,610 --> 01:10:02,220
ampak, če ste izgradnjo stvari za, recimo, kot iPhone ali Android,

889
01:10:02,220 --> 01:10:05,230
ti imajo omejene vire spomin, še posebej, če delaš nekaj hudo.

890
01:10:05,230 --> 01:10:08,300
Zato je dobro, da se v praksi.

891
01:10:08,300 --> 01:10:10,510
>> Obvestilo, da sem uporabljal nekaj različnih funkcij tukaj

892
01:10:10,510 --> 01:10:12,880
ki ste jih videli, da so nekako novo.

893
01:10:12,880 --> 01:10:15,870
Torej ovrednotenj je tako kot printf

894
01:10:15,870 --> 01:10:21,320
razen prvi trditvi je tok, ki ga želite natisniti.

895
01:10:21,320 --> 01:10:23,900
V tem primeru želimo tiskati na standardni niz napak

896
01:10:23,900 --> 01:10:29,410
ki se razlikuje od standardne outstream.

897
01:10:29,410 --> 01:10:31,620
Privzeto se pokaže na istem mestu.

898
01:10:31,620 --> 01:10:34,600
Prav tako natisne na terminal, vendar je to mogoče -

899
01:10:34,600 --> 01:10:38,790
uporabo teh ukazov ste se naučili o tem, preusmeritve tehnike

900
01:10:38,790 --> 01:10:42,290
ste se naučili o Tommy v videu za sklop 4 problem, ga lahko neposredno

901
01:10:42,290 --> 01:10:47,900
na različnih področjih, zaprite, tukaj, zapusti svoj program.

902
01:10:47,900 --> 01:10:50,440
To je v bistvu kot vrnitvi iz glavnega,

903
01:10:50,440 --> 01:10:53,600
razen uporabimo izhod, ker sem vrnitev ne bo naredil ničesar.

904
01:10:53,600 --> 01:10:57,140
Nismo v glavnem, da se ne vračajo zapreti program, kot si želimo.

905
01:10:57,140 --> 01:11:03,020
Zato bomo uporabili za izhod iz funkcije in mu kodo napake.

906
01:11:03,020 --> 01:11:11,890
Potem tukaj smo postavili novega vozlišča vrednost polja, njegov i polje, enaka i, potem pa ga priključite gor.

907
01:11:11,890 --> 01:11:15,530
Postavili smo novega vozlišča poleg kazalec, da kaže na eni strani,

908
01:11:15,530 --> 01:11:20,460
in potem najprej bo zdaj kaže na novo vozlišče.

909
01:11:20,460 --> 01:11:25,120
Te prve vrstice kode, smo dejansko gradnjo novega vozlišča.

910
01:11:25,120 --> 01:11:27,280
Ni zadnji dve vrstici te funkcije, vendar prvimi.

911
01:11:27,280 --> 01:11:30,290
Lahko dejansko potegnite v funkciji, v helper funkcije.

912
01:11:30,290 --> 01:11:32,560
To je pogosto kaj naredim je, da sem jo potegnil ven v funkciji

913
01:11:32,560 --> 01:11:36,040
I call it nekaj takega kot vozlišče gradnje,

914
01:11:36,040 --> 01:11:40,410
in da ohranja prepend funkcija precej majhen, je le 3 vrstice takrat.

915
01:11:40,410 --> 01:11:48,710
Sem klicati na mojo funkcijo vozlišče graditi, potem pa sem vse žice gor.

916
01:11:48,710 --> 01:11:51,970
>> Zadnja stvar, želim, da vam pokaže,

917
01:11:51,970 --> 01:11:54,030
in jaz bom ti dovolil dodajati in vse to na svoje,

918
01:11:54,030 --> 01:11:57,500
Ponovil je, kako v seznam.

919
01:11:57,500 --> 01:12:00,780
Obstaja kup različnih načinov, da izbirate preko seznama.

920
01:12:00,780 --> 01:12:03,140
V tem primeru, bomo našli dolžino seznama.

921
01:12:03,140 --> 01:12:06,570
Tako smo začeli z dolžino = 0.

922
01:12:06,570 --> 01:12:11,580
To je zelo podoben pisanju strlen v nizu.

923
01:12:11,580 --> 01:12:17,780
To je tisto, kar sem hotel pokazati, ta zanka se tukaj.

924
01:12:17,780 --> 01:12:23,530
To izgleda nekako funky, to ni običajna int i = 0, i <karkoli, i + +.

925
01:12:23,530 --> 01:12:34,920
Namesto tega se pri inicializaciji našo spremenljivko n, da je začetek seznama.

926
01:12:34,920 --> 01:12:40,620
In potem ko smo iterator spremenljivka ni nič, bomo naprej.

927
01:12:40,620 --> 01:12:46,340
To je zato, ker je po dogovoru, bo konec našega seznama je nična.

928
01:12:46,340 --> 01:12:48,770
In potem prirastek, namesto da delaš + +,

929
01:12:48,770 --> 01:12:57,010
povezani seznam ekvivalent + + je n = n-> next.

930
01:12:57,010 --> 01:13:00,410
>> Povedal ti bom, zapolniti vrzeli, saj smo tukaj zmanjkalo časa.

931
01:13:00,410 --> 01:13:09,300
Ampak to v mislih, kot delate na vašem spellr psets.

932
01:13:09,300 --> 01:13:11,650
Povezani seznami, če ste izvajanju razpršene tabele,

933
01:13:11,650 --> 01:13:14,010
bo zagotovo prišel zelo prav.

934
01:13:14,010 --> 01:13:21,780
In ob tem govorico za večkratno več stvari narediti življenje veliko lažje, upam.

935
01:13:21,780 --> 01:13:25,910
Vsa vprašanja, hitro?

936
01:13:25,910 --> 01:13:28,920
[Sam] boste poslali izpolnjen SLL in SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ja. Jaz bom poslal izpolnjenih diapozitivov in izpolnjeno SLL sklad in queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]