1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Časť 6: Menej pohodlné]

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
Dobrá. Vitajte v sekcii 6.

5
00:00:11,840 --> 00:00:14,690
Tento týždeň, budeme hovoriť o dátových štruktúr v sekcii,

6
00:00:14,690 --> 00:00:19,780
predovšetkým preto, že tento týždeň je problém nastaviť na spellr

7
00:00:19,780 --> 00:00:24,410
sa celá partia inú dátovú štruktúru prieskumu.

8
00:00:24,410 --> 00:00:26,520
Existuje veľa rôznych spôsobov, ako môžete ísť s týmto problémom set,

9
00:00:26,520 --> 00:00:31,570
a čím viac dátových štruktúr viete o, tým viac cool vecí, ktoré môžete urobiť.

10
00:00:31,570 --> 00:00:34,990
>> Tak poďme začať. Najprv budeme hovoriť o komíny,

11
00:00:34,990 --> 00:00:37,530
zásobníka a fronty dátové štruktúry, ktoré budeme hovoriť o

12
00:00:37,530 --> 00:00:40,560
Komíny a fronty sú naozaj užitočné, keď začneme hovoriť o grafy,

13
00:00:40,560 --> 00:00:44,390
ktoré nebudeme robiť toľko teraz.

14
00:00:44,390 --> 00:00:52,820
Ale sú naozaj dobré pochopiť jednu z veľkých základných dátových štruktúr SK.

15
00:00:52,820 --> 00:00:54,880
Popis v špecifikácii problému set,

16
00:00:54,880 --> 00:00:59,260
ak ste vytiahnite ju hore, hovorí o tom, komíny ako blízky

17
00:00:59,260 --> 00:01:05,239
hromada jedálnych podnosov, že máte v jedálni v jedálňach

18
00:01:05,239 --> 00:01:09,680
kde, kedy jedáleň zamestnancov príde a dá si jedálenský podnosy z potom, čo som vyčistiť je,

19
00:01:09,680 --> 00:01:12,000
oni vyrovnajú im jeden na druhého.

20
00:01:12,000 --> 00:01:15,050
A potom, keď deti prídu do dostať jedlo,

21
00:01:15,050 --> 00:01:19,490
vyťahujú zásobníky off, prvý vrchol jeden, potom jeden pod ním, potom jeden pod tým.

22
00:01:19,490 --> 00:01:25,190
Takže v skutočnosti, prvý zásobník, ktorý jedálenský personál položil je posledný, ktorý sa vzlietlo.

23
00:01:25,190 --> 00:01:32,330
Ten posledný, že jedáleň zamestnanci kladený na je prvý, ktorý sa vzlietlo na večeru.

24
00:01:32,330 --> 00:01:38,100
V problému setu je spec, ktoré si môžete stiahnuť, ak ste tak už neurobili,

25
00:01:38,100 --> 00:01:46,730
Ak hovoríme o modelovanie zásobníka dát ŠTRUKTÚRA pomocou tohto druhu struct.

26
00:01:46,730 --> 00:01:51,070
>> Takže to, čo sme sa sem dostali, je to podobné tomu, čo bolo uvedené v prednáške,

27
00:01:51,070 --> 00:01:58,120
výnimkou v prednáške sme sa prezentovali to s ints ako protiklad k char * s

28
00:01:58,120 --> 00:02:06,250
To bude zásobník, ktorý ukladá, čo?

29
00:02:06,250 --> 00:02:09,009
Daniel? Čo sme uchovávanie v tomto zásobníku?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Sme ukladanie reťazca v tomto zásobníku, presne.

31
00:02:15,260 --> 00:02:20,950
Všetko, čo je potrebné, aby sa za účelom vytvorenia zásobníka je pole

32
00:02:20,950 --> 00:02:23,920
určitej kapacity, ktorá je v tomto prípade,

33
00:02:23,920 --> 00:02:28,020
kapacita bude vo všetkých veľkých písmenách, pretože je to konštanta.

34
00:02:28,020 --> 00:02:36,340
A potom okrem poľa, všetko musíme sledovať je aktuálna veľkosť poľa.

35
00:02:36,340 --> 00:02:38,980
Jedna vec k poznámke, že je to celkom fajn

36
00:02:38,980 --> 00:02:47,060
je to, že sme vytvorenie skladaného dátovú štruktúru na vrchole iné štruktúry dát, polia.

37
00:02:47,060 --> 00:02:50,110
Existujú rôzne spôsoby, ako implementovať stohy.

38
00:02:50,110 --> 00:02:54,250
Budeme to robiť ešte dosť, ale dúfajme, že potom, čo robil na odkazovaných zoznam problémov,

39
00:02:54,250 --> 00:03:00,520
uvidíte, ako si môžete ľahko implementovať balík na vrchole prepojeného zoznamu rovnako.

40
00:03:00,520 --> 00:03:02,640
Ale teraz, budeme držať poľa.

41
00:03:02,640 --> 00:03:06,350
Takže znova, všetko, čo potrebujete, je pole a my stačí sledovať veľkosť poľa.

42
00:03:06,350 --> 00:03:09,850
[Sam] Ospravedlňujem sa, prečo je to, že ste hovoril, že stack je na vrchol reťazcov?

43
00:03:09,850 --> 00:03:13,440
Pre mňa sa zdá, že reťazce sú v zásobníku.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Jo. Sme vytváranie, berieme naše pole dátové štruktúry -

45
00:03:16,790 --> 00:03:22,130
To je veľká otázka. Takže otázka je, prečo, pre ľudí, ktorí sledujú tento on-line,

46
00:03:22,130 --> 00:03:24,140
prečo hovoríme, že zásobník je na vrchole reťazca,

47
00:03:24,140 --> 00:03:27,990
pretože tu to vyzerá, ako sú reťazce vo vnútri zásobníka?

48
00:03:27,990 --> 00:03:31,050
Čo je úplne prípad.

49
00:03:31,050 --> 00:03:34,660
To, čo som mal na mysli, že máme maticový dátovú štruktúru.

50
00:03:34,660 --> 00:03:39,290
Máme celý rad char * s, toto pole reťazcov,

51
00:03:39,290 --> 00:03:45,300
a budeme pridať do, že za účelom vytvorenia skladaný dátové štruktúry.

52
00:03:45,300 --> 00:03:48,620
>> Takže stack je trochu zložitejšie ako pole.

53
00:03:48,620 --> 00:03:51,890
Môžeme použiť pole postaviť stack.

54
00:03:51,890 --> 00:03:55,810
Tak to je, kde môžeme povedať, že zásobník je postavený na vrchole poľa.

55
00:03:55,810 --> 00:04:02,510
Rovnako tak, ako som povedal predtým, môžeme vybudovať zásobník na vrchole prepojeného zoznamu.

56
00:04:02,510 --> 00:04:04,960
Namiesto toho, aby pomocou poľa držať naše prvky,

57
00:04:04,960 --> 00:04:10,070
by sme mohli použiť prepojeného zoznamu držať naše prvky a vytvoriť stoh okolo toho.

58
00:04:10,070 --> 00:04:12,420
Poďme prejsť pár príkladov, pri pohľade na nejaký kód,

59
00:04:12,420 --> 00:04:14,960
vidieť, čo sa vlastne deje.

60
00:04:14,960 --> 00:04:23,400
Na ľavej strane, som hodil dolu, čo to stack struct bude vyzerať v pamäti

61
00:04:23,400 --> 00:04:28,330
ak kapacita bola # definovaný byť štyri.

62
00:04:28,330 --> 00:04:33,490
Máme naše štyri prvok char * pole.

63
00:04:33,490 --> 00:04:38,110
Máme reťazca [0], struny [1], struny [2], struny [3],

64
00:04:38,110 --> 00:04:43,800
a potom, že posledný priestor pre našu veľkosť celé číslo.

65
00:04:43,800 --> 00:04:46,270
Má to zmysel? Dobre.

66
00:04:46,270 --> 00:04:48,790
To je to, čo sa stane, keď to, čo mám robiť, na pravej strane,

67
00:04:48,790 --> 00:04:55,790
ktorý bude môj kód, je len vyhlásiť struct, skladaný struct volal s

68
00:04:55,790 --> 00:05:01,270
To je to, čo dostaneme. Stanovuje tento stopu v pamäti.

69
00:05:01,270 --> 00:05:05,590
Prvá otázka je, čo je obsahom tohto zásobníka struct?

70
00:05:05,590 --> 00:05:09,250
Práve teraz nie sme nič, ale nie sú úplne nič.

71
00:05:09,250 --> 00:05:13,300
Sú tento druh odpadu. Nemáme tušenie, čo je v nich.

72
00:05:13,300 --> 00:05:17,000
Keď sme vyhlásiť zásobník s, sme len hádzanie, že sa na vrchole pamäte.

73
00:05:17,000 --> 00:05:19,840
Je to niečo ako vyhlásenie int i, a nie jeho inicializácii.

74
00:05:19,840 --> 00:05:21,730
Ty nevieš, čo je to tam. Môžete si prečítať, čo je tam,

75
00:05:21,730 --> 00:05:27,690
ale to nemusí byť super užitočné.

76
00:05:27,690 --> 00:05:32,680
Jedna vec, ktorú chcete, aby sa vždy pamätajte na to, je inicializovať, čo je potrebné inicializovať.

77
00:05:32,680 --> 00:05:35,820
V tomto prípade, budeme inicializovať veľkosť nula,

78
00:05:35,820 --> 00:05:39,960
pretože je to dopadne ako pre nás veľmi dôležité.

79
00:05:39,960 --> 00:05:43,450
Mohli by sme pokračovať a inicializácii všetkých ukazovateľov, všetky char * s,

80
00:05:43,450 --> 00:05:49,670
sa, že niektoré pochopiteľné hodnota, pravdepodobne null.

81
00:05:49,670 --> 00:05:58,270
Ale nie je to úplne nevyhnutné, urobíme to.

82
00:05:58,270 --> 00:06:04,200
>> Teraz, dva hlavné operácie komíny sú?

83
00:06:04,200 --> 00:06:07,610
Ktokoľvek pamätám z prednášky, čo robiť s komíny? Áno?

84
00:06:07,610 --> 00:06:09,700
[Stella] Stlačením a praskanie? Presne >>.

85
00:06:09,700 --> 00:06:13,810
Tlačenie a praskanie sú dve hlavné operácie na komíny.

86
00:06:13,810 --> 00:06:17,060
A čo tlačiť robiť? >> Kladie niečo na vrchole

87
00:06:17,060 --> 00:06:19,300
zo zásobníka, a potom praskla vezme ho.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Presne tak. Takže tlačí tlačí niečo na vrchole zásobníka.

89
00:06:23,150 --> 00:06:27,700
Je to ako v jedálni zamestnancov uvedenie jedálenský podnos na pult.

90
00:06:27,700 --> 00:06:33,630
A objavovať berie jedálenský podnos preč zásobníka.

91
00:06:33,630 --> 00:06:36,460
Poďme prejsť pár príkladov toho, čo sa stane

92
00:06:36,460 --> 00:06:39,720
keď sme sa tlačiť veci do zásobníka.

93
00:06:39,720 --> 00:06:45,110
Ak by sme mali tlačiť na reťazec "ahoj" na naše zásobníka,

94
00:06:45,110 --> 00:06:49,760
To je to, čo naša schéma by vyzerať ako teraz.

95
00:06:49,760 --> 00:06:53,410
Pozrite sa, čo sa stane?

96
00:06:53,410 --> 00:06:56,530
Usilovali sme do prvého prvku našej reťazca pole

97
00:06:56,530 --> 00:07:01,420
a my zvýšil naše veľkosť počet na 1.

98
00:07:01,420 --> 00:07:05,340
Takže ak sa pozrieme na rozdiel medzi dvoma šmykľavkami, tu bola 0, tu je pred stlačením.

99
00:07:05,340 --> 00:07:08,690
Tu je po stlačení.

100
00:07:08,690 --> 00:07:13,460
Pred push, po stlačení.

101
00:07:13,460 --> 00:07:16,860
A teraz máme jeden prvok v našom zásobníku.

102
00:07:16,860 --> 00:07:20,970
Je to reťazec "ahoj", a to je všetko.

103
00:07:20,970 --> 00:07:24,440
Všetko ostatné v poli, v našom reťazcoch poli, je stále odpadky.

104
00:07:24,440 --> 00:07:27,070
Sme nie je inicializovaná to.

105
00:07:27,070 --> 00:07:29,410
Povedzme, že sme sa tlačiť ďalšie reťazec do nášho zásobníka.

106
00:07:29,410 --> 00:07:32,210
Budeme tlačiť "svet" v tejto dobe.

107
00:07:32,210 --> 00:07:35,160
Takže vidíte, "world" tu je na vrchole "hello",

108
00:07:35,160 --> 00:07:40,040
a veľkosti znakov siaha až do 2.

109
00:07:40,040 --> 00:07:44,520
Teraz môžeme tlačiť "CS50", a že to ísť na vrchole znova.

110
00:07:44,520 --> 00:07:51,110
Keď sa vrátime, môžete vidieť, ako sa tlačí veci na vrchole zásobníka.

111
00:07:51,110 --> 00:07:53,320
A teraz sa dostávame k popu.

112
00:07:53,320 --> 00:07:58,910
Keď sme vyskočila niečo z frontu, čo sa stalo?

113
00:07:58,910 --> 00:08:01,540
Každý Vidíte ten rozdiel? Je to celkom jemné.

114
00:08:01,540 --> 00:08:05,810
[Študent] veľkosť. >> Jo, jej veľkosť.

115
00:08:05,810 --> 00:08:09,040
>> Čo iné by ste očakávali zmeniť?

116
00:08:09,040 --> 00:08:14,280
[Študent] Reťazce, taky. Právo >>. Reťazce taky.

117
00:08:14,280 --> 00:08:17,110
Ukazuje sa, že keď robíte to takto,

118
00:08:17,110 --> 00:08:21,960
pretože nie sme kopírovanie prvkov do nášho zásobníka,

119
00:08:21,960 --> 00:08:24,670
sme vlastne nemusíme robiť nič, my môžeme len použiť veľkosť

120
00:08:24,670 --> 00:08:28,630
sledovať počtu vecí v našom poli

121
00:08:28,630 --> 00:08:33,780
takže keď sme pop, znovu sme práve decrement svoju veľkosť až 1.

122
00:08:33,780 --> 00:08:39,440
Nie je potrebné, aby skutočne ísť a prepísať čokoľvek.

123
00:08:39,440 --> 00:08:41,710
Druh funky.

124
00:08:41,710 --> 00:08:46,520
Ukazuje sa, že sme zvyčajne len nechať veci sám, pretože je to menej práce pre nás urobiť.

125
00:08:46,520 --> 00:08:50,060
Ak nemáme ísť späť a prepísať niečo, tak prečo to?

126
00:08:50,060 --> 00:08:54,150
Takže keď sme sa pop dvakrát preč zásobníka, všetko, čo robí, je decrement do veľkosti niekoľkokrát.

127
00:08:54,150 --> 00:08:59,120
A opäť, je to len preto, že nie sme kopírovanie veci do nášho stacku.

128
00:08:59,120 --> 00:09:01,320
Áno? Hovorte.

129
00:09:01,320 --> 00:09:04,460
[Študent, nezrozumiteľné] >> A čo sa stane potom, keď budete tlačiť zase niečo?

130
00:09:04,460 --> 00:09:08,570
Keď stlačíte zase niečo, kde to ide?

131
00:09:08,570 --> 00:09:12,390
Ak to pôjde, Basile? Do >> reťazcov [1]? Právo >>.

132
00:09:12,390 --> 00:09:14,530
Prečo to ísť do reťazca [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Vzhľadom k tomu, že zabudol, že tam bolo niečo v reťazci [1] a [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Presne tak. Naše zásobník, v podstate, "zabudol", že to držal na čokoľvek

135
00:09:24,040 --> 00:09:29,480
v reťazci [1] alebo reťazca [2], takže keď sme sa tlačiť "Woot",

136
00:09:29,480 --> 00:09:36,670
to len vezme, že do elementu v reťazci [1].

137
00:09:36,670 --> 00:09:41,590
Sú nejaké otázky, na tom, ako to funguje, na základnej úrovni?

138
00:09:41,590 --> 00:09:45,160
[Sam] Tak to nie je dynamický žiadnym spôsobom, pokiaľ ide o výšku

139
00:09:45,160 --> 00:09:47,620
alebo z hľadiska veľkosti zásobníka?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Presne tak. To je - išlo o to, že to nie je dynamicky growning stack.

141
00:09:56,750 --> 00:10:02,850
To je zásobník, ktorý môže obsahovať, nanajvýš štyri * char s, najviac štyri veci.

142
00:10:02,850 --> 00:10:07,580
Ak by sme mali skúsiť a tlačiť pätiny vec, čo si myslíte, že by sa malo stať?

143
00:10:07,580 --> 00:10:11,870
[Študenti, nezrozumiteľné]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Presne tak. Existuje celá rada vecí, ktoré by sa mohlo stať.

145
00:10:14,600 --> 00:10:19,330
To by mohlo seg poruchy, závislosti na tom, čo sme boli -

146
00:10:19,330 --> 00:10:22,530
ako presne sme realizáciu back-end.

147
00:10:22,530 --> 00:10:31,740
Mohlo by to prepísať. To by mohlo mať, že buffer overflow, že sme hovorili o v triede.

148
00:10:31,740 --> 00:10:35,240
Aký by mal byť najzrejmejšie vec, ktorá by mohla byť prepísané

149
00:10:35,240 --> 00:10:42,370
ak sme sa snažili tlačiť ďalšia vec na našom zásobníku?

150
00:10:42,370 --> 00:10:44,550
Takže vy ste spomenul pretečeniu vyrovnávacej pamäte.

151
00:10:44,550 --> 00:10:47,870
Čo by mohlo byť to, čo by si písal cez alebo dupol na

152
00:10:47,870 --> 00:10:52,320
ak by sme pretiekol náhodou, že sa snaží tlačiť ďalšia vec?

153
00:10:52,320 --> 00:10:54,730
[Daniel, nezrozumiteľné] >> Možno.

154
00:10:54,730 --> 00:10:58,440
Ale spočiatku, môže, čo sa stalo? Čo keď sme sa snažili tlačiť štvrtiny vec?

155
00:10:58,440 --> 00:11:06,220
To by mohlo prepísať veľkosť, aspoň s týmto pamäťovým schémy, ktoré sme dostali.

156
00:11:06,220 --> 00:11:10,880
>> V špecifikácii problému set, čo je to, čo budeme sa vykonáva dnes,

157
00:11:10,880 --> 00:11:16,030
čo chceš urobiť, je len vráti false.

158
00:11:16,030 --> 00:11:20,030
Naša Push metóda bude vracať boolovská,

159
00:11:20,030 --> 00:11:22,920
a že boolean hodnota bude true, ak tlak uspeje

160
00:11:22,920 --> 00:11:29,730
false, ak nemôžeme presadzovať nič viac, pretože zásobník je plný.

161
00:11:29,730 --> 00:11:33,620
Prejdime trochou uvedeného kódexu teraz.

162
00:11:33,620 --> 00:11:36,400
Tu je náš stlačenie funkcie.

163
00:11:36,400 --> 00:11:40,380
Naša tlak funkcia pre sústavu bude trvať v reťazci, aby na zásobníku.

164
00:11:40,380 --> 00:11:45,820
Bude to vráti hodnotu true, ak reťazec bol úspešne tlačil

165
00:11:45,820 --> 00:11:51,820
na stack a false inak.

166
00:11:51,820 --> 00:11:59,740
Nejaké návrhy na to, čo by mohlo byť dobrý prvá vec tu?

167
00:11:59,740 --> 00:12:20,630
[Sam] Ak veľkosť zodpovedá kapacitu potom vráti false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Dobrá práce.

169
00:12:23,320 --> 00:12:26,310
Ak je veľkosť kapacity, budeme sa vrátiť false.

170
00:12:26,310 --> 00:12:29,270
Nemôžeme dať niečo viac v našom zásobníku.

171
00:12:29,270 --> 00:12:36,900
V opačnom prípade budeme chcieť dať niečo na vrchole zásobníka.

172
00:12:36,900 --> 00:12:41,670
Čo je to "vrchol zásobníka," pôvodne?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Veľkosť 0? Veľkosť >> 0.

174
00:12:43,650 --> 00:12:49,990
Čo je vrchol zásobníka po tu jedna vec, ktorú v zásobníku? Missy, vieš?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Veľkosť >> je, presne tak. Tie držať pridanie do veľkosti,

176
00:12:52,720 --> 00:13:01,690
a zakaždým, keď ste uvedení v novom prvku v indexe veľkosť v poli.

177
00:13:01,690 --> 00:13:05,470
Môžeme to urobiť s týmto druhom jednej vložky, pokiaľ to dáva zmysel.

178
00:13:05,470 --> 00:13:11,910
Takže máme naše struny ponuku, budeme pristupovať na veľkosti indexu,

179
00:13:11,910 --> 00:13:14,780
a my sme len tak uložiť naše char * tam.

180
00:13:14,780 --> 00:13:19,340
Všimnite si, ako tam je žiadny reťazec kopírovanie tu deje,

181
00:13:19,340 --> 00:13:29,680
no dynamické prideľovanie pamäti?

182
00:13:29,680 --> 00:13:34,440
A potom Missy priniesol to, čo teraz musíme urobiť,

183
00:13:34,440 --> 00:13:40,570
pretože sme uložili reťazec na príslušnom mieste v poli,

184
00:13:40,570 --> 00:13:49,230
a ona povedala, že sme museli zvýšiť veľkosť jedného tak, že sme pripravení na ďalšie Push.

185
00:13:49,230 --> 00:13:53,950
Takže, čo môžeme urobiť, aby sa s.size + +.

186
00:13:53,950 --> 00:13:59,330
V tomto bode, sme tlačení do nášho poľa. Čo je posledná vec, ktorú musíme urobiť?

187
00:13:59,330 --> 00:14:10,110
[Študent] Vracia true. >> Vracia true.

188
00:14:10,110 --> 00:14:14,690
Takže je to celkom jednoduché, celkom jednoduchý kód. Nie moc.

189
00:14:14,690 --> 00:14:17,070
Akonáhle omotal hlavu okolo, ako stack funguje,

190
00:14:17,070 --> 00:14:21,910
to je docela ľahko implementovať.

191
00:14:21,910 --> 00:14:26,390
>> Teraz, ďalšia časť z toho sa objavovať reťazec preč zásobníka.

192
00:14:26,390 --> 00:14:29,410
Ja ti dám si chalani nejaký čas pracovať na tomto trochu.

193
00:14:29,410 --> 00:14:34,320
Je to skoro podstate opak toho, čo sme urobili tu v Push.

194
00:14:34,320 --> 00:14:38,510
To, čo som urobil, je vlastne - oops.

195
00:14:38,510 --> 00:14:48,160
Som naštartoval až spotrebiče tu, a v spotrebiči,

196
00:14:48,160 --> 00:14:53,600
Ja som vytiahol problém nastaviť 5 špecifikáciu.

197
00:14:53,600 --> 00:15:02,560
Ak by sme priblížite tu, môžeme vidieť som na cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Už ste stiahli tento kód, ktorý je tu umiestnený, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Dobrá. Ak ste tak ešte neurobili, aby to, že práve teraz, naozaj rýchlo.

200
00:15:15,030 --> 00:15:22,130
Urobím to v mojom terminálovom okne.

201
00:15:22,130 --> 00:15:25,090
Vlastne som to urobil tu. Jo.

202
00:15:25,090 --> 00:15:34,730
Áno, Sam? >> Mám otázku o tom, prečo ste hovoril, že s.string 's držiakmi na veľkosti = str?

203
00:15:34,730 --> 00:15:42,910
Čo je to str? Je vymedzený niekde pred, alebo - oh, v char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Áno, presne tak. To bol argument. >> Oh, dobre. Prepáčte.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Sme určujúce reťazec, aby sa zasadila palcov

206
00:15:49,470 --> 00:15:55,220
Ďalšia otázka, ktorá by mohla prísť, že sme sa naozaj hovoriť o tu bola

207
00:15:55,220 --> 00:15:58,810
sme sa za samozrejmé, že sme mali túto premennú s názvom s

208
00:15:58,810 --> 00:16:02,710
, Ktorý bol v rozsahu a prístupné pre nás.

209
00:16:02,710 --> 00:16:06,960
Vzali sme za samozrejmé, že s je tento stack struct.

210
00:16:06,960 --> 00:16:08,930
Takže ohliadnutie za touto Push kód,

211
00:16:08,930 --> 00:16:13,450
môžete vidieť, že robíme veci s týmto reťazcom, ktorý dostal prešiel v

212
00:16:13,450 --> 00:16:19,210
ale potom zrazu, že sme prístup k s.size, rovnako ako tam, kde sa s pochádzajú?

213
00:16:19,210 --> 00:16:23,020
V kóde, ktorý sa budeme pozerať na v sekcii archíve

214
00:16:23,020 --> 00:16:27,100
a potom veci, ktoré budete robiť vo svojom probléme zapadne,

215
00:16:27,100 --> 00:16:32,440
sme urobili náš stack struct globálne premenné

216
00:16:32,440 --> 00:16:36,380
takže môžeme mať k nemu prístup na všetkých našich rôznych funkciách

217
00:16:36,380 --> 00:16:40,630
bez toho aby ste museli ručne prejsť okolo a odovzdať ho odkazom,

218
00:16:40,630 --> 00:16:44,870
robiť všetky tieto veci k nej.

219
00:16:44,870 --> 00:16:52,280
Sme jednoducho podvádza trochu, ak chcete, aby sa veci krajšie.

220
00:16:52,280 --> 00:16:57,430
A to je niečo, čo tu robíme, pretože je to pre zábavu, je to jednoduchšie.

221
00:16:57,430 --> 00:17:02,800
Často, uvidíte ľudia to v prípade, že má jednu veľkú dátovú štruktúru

222
00:17:02,800 --> 00:17:07,750
, Ktorý je prevádzkovaný na v rámci ich programu.

223
00:17:07,750 --> 00:17:09,560
>> Vráťme sa k zariadeniu.

224
00:17:09,560 --> 00:17:15,240
Bolo všetci úspešne získať section6.zip?

225
00:17:15,240 --> 00:17:20,440
Všetci rozbaľte ho pomocou Rozbaľte section6.zip?

226
00:17:20,440 --> 00:17:27,200
Ak pôjdete do sekcie 6 adresára -

227
00:17:27,200 --> 00:17:29,220
Aah, všade možne -

228
00:17:29,220 --> 00:17:32,840
a zoznam toho, čo je tu, vidíte, že máte tri rôzne. C súbory.

229
00:17:32,840 --> 00:17:38,350
Máte front, SLL, čo je single-linked list, a zásobník.

230
00:17:38,350 --> 00:17:44,600
Ak otvoríte stack.c,

231
00:17:44,600 --> 00:17:47,330
môžete vidieť, že máme túto struct definované pre nás,

232
00:17:47,330 --> 00:17:51,330
Presný struct, že sme práve hovorili zo sklíčka.

233
00:17:51,330 --> 00:17:56,340
Máme naše globálne premenné pre zásobník,

234
00:17:56,340 --> 00:18:00,110
sme dostali náš Push funkciu,

235
00:18:00,110 --> 00:18:04,230
a potom sme dostali náš pop funkciu.

236
00:18:04,230 --> 00:18:08,320
Dám kód pre zatlačte späť na snímke tu,

237
00:18:08,320 --> 00:18:10,660
ale to, čo by som chcel vy urobiť, je, ako najlepšie svoje schopnosti,

238
00:18:10,660 --> 00:18:13,790
ísť a robiť pop funkciu.

239
00:18:13,790 --> 00:18:18,480
Akonáhle ste implementovali, môžete kompilovať to s make stoh,

240
00:18:18,480 --> 00:18:22,540
a spustite výsledné zásobníka spustiteľný,

241
00:18:22,540 --> 00:18:28,390
a že pobeží celý tohto skúšobného predpisu tu to je v main.

242
00:18:28,390 --> 00:18:31,060
A hlavné stará skutočne robiť push a pop hovory

243
00:18:31,060 --> 00:18:33,220
a uistite sa, že všetko ide cez všetky práva.

244
00:18:33,220 --> 00:18:36,820
To tiež inicializuje veľkosť zásobníku tu

245
00:18:36,820 --> 00:18:39,780
takže nemusíte mať strach o inicializácii, že.

246
00:18:39,780 --> 00:18:42,310
Môžete predpokladať, že to bolo správne inicializovaný

247
00:18:42,310 --> 00:18:48,000
v okamihu, keď ste k nemu mali prístup do pop funkciu.

248
00:18:48,000 --> 00:18:53,530
Dáva to zmysel?

249
00:18:53,530 --> 00:19:00,100
Tak ideme na to. Tam je tlak kód.

250
00:19:00,100 --> 00:19:13,210
Dám ti chlapci 5 alebo 10 minút.

251
00:19:13,210 --> 00:19:15,690
A ak máte nejaké otázky v medziobdobí, keď ste kódovanie,

252
00:19:15,690 --> 00:19:17,710
Spýtajte sa nahlas.

253
00:19:17,710 --> 00:19:23,080
Takže ak sa dostanete do problematickým bodom, opýtajte sa.

254
00:19:23,080 --> 00:19:26,030
Dajte mi vedieť, nech všetci ostatní vedieť.

255
00:19:26,030 --> 00:19:28,160
Práca so svojím susedom taky.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Zrovna vykonávanie pop teraz? Len >> pop.

257
00:19:30,360 --> 00:19:34,200
Aj keď môžete skopírovať vykonávanie Push, ak chcete

258
00:19:34,200 --> 00:19:37,780
tak, že testovanie bude fungovať.

259
00:19:37,780 --> 00:19:41,940
Vzhľadom k tomu, že je ťažké testovať veci dostať do -

260
00:19:41,940 --> 00:19:49,030
alebo, je ťažké testovať objavovať veci z hromady, ak tam nie je niečo v zásobníku začať.

261
00:19:49,030 --> 00:19:55,250
>> Čo je pop mal byť vracajúci? Prvok z hornej časti zásobníka.

262
00:19:55,250 --> 00:20:01,260
Má to dostať prvok preč hornej časti zásobníka

263
00:20:01,260 --> 00:20:05,780
a potom dekrementace veľkosť zásobníku,

264
00:20:05,780 --> 00:20:07,810
a teraz ste stratili prvok na vrchole.

265
00:20:07,810 --> 00:20:11,420
A potom sa vrátite prvok na vrchole.

266
00:20:11,420 --> 00:20:20,080
[Študent, nezrozumiteľným]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Takže čo sa stane, ak to urobíte? [Študent, nezrozumiteľným]

268
00:20:28,810 --> 00:20:34,000
Čo sa skončí udalosť je budete pravdepodobne prístup buď

269
00:20:34,000 --> 00:20:37,350
prvok, ktorý nebol inicializovaný ešte, takže výpočet

270
00:20:37,350 --> 00:20:39,990
, Kde sa posledný prvok je vypnutý.

271
00:20:39,990 --> 00:20:46,260
Takže tu, ak si všimnete, v Push, sme prístup reťazca na s.size prvku

272
00:20:46,260 --> 00:20:48,560
pretože je to nový index.

273
00:20:48,560 --> 00:20:51,460
Je to nový vrchol zásobníka.

274
00:20:51,460 --> 00:21:01,100
Vzhľadom k tomu, pop, s.size bude budúci priestor,

275
00:21:01,100 --> 00:21:05,210
priestor, ktorý je v hornej časti všetkých prvkov v stohu.

276
00:21:05,210 --> 00:21:10,050
Takže na najvyššej element nie je v s.size,

277
00:21:10,050 --> 00:21:14,930
ale, že je to pod ňou.

278
00:21:14,930 --> 00:21:19,640
>> Ďalšia vec, ktorú urobiť, keď sa - v popu,

279
00:21:19,640 --> 00:21:22,030
je si treba decrement veľkosti.

280
00:21:22,030 --> 00:21:28,750
Ak si pamätáte späť do našej malej diagramu tu,

281
00:21:28,750 --> 00:21:30,980
Naozaj, jediná vec, ktorá sme videli deje, keď my sme volali pop

282
00:21:30,980 --> 00:21:36,150
bolo, že táto veľkosť klesla, prvé 2, potom 1.

283
00:21:36,150 --> 00:21:42,620
Potom, keď sme sa tlačil nový prvok na, by to ísť na na správnom mieste.

284
00:21:42,620 --> 00:21:49,610
[Basil] Ak s.size je 2, potom nie je to ísť na prvku 2,

285
00:21:49,610 --> 00:21:54,400
a potom budeš chcieť pop ten element off?

286
00:21:54,400 --> 00:21:59,510
Takže ak by sme išli do - >> Tak sa poďme pozrieť na to znova.

287
00:21:59,510 --> 00:22:07,730
Pokiaľ je to náš zásobník na tomto mieste

288
00:22:07,730 --> 00:22:12,130
a nazývame pop,

289
00:22:12,130 --> 00:22:16,150
na ktoré index je na najvyššej element?

290
00:22:16,150 --> 00:22:19,300
[Basil] Na 2, ale bude to pop 3. Právo >>.

291
00:22:19,300 --> 00:22:24,220
Tak to je, kde je naša veľkosť 3, ale chceme, aby pop prvok na indexe 2.

292
00:22:24,220 --> 00:22:29,900
Je to tak typické druh off by ten, ktorý máte s nulovou indexovanie polí.

293
00:22:29,900 --> 00:22:36,430
Takže vy chcete pop tretí prvok, ale tretí prvok nie je na indexe 3.

294
00:22:36,430 --> 00:22:39,430
A dôvod, prečo nemáme robiť, že mínus 1, keď sme tlačenie

295
00:22:39,430 --> 00:22:44,120
je, pretože práve teraz, zistíte, že na najvyššej prvok,

296
00:22:44,120 --> 00:22:47,600
ak by sme mali tlačiť niečo iné na stacku v tomto bode,

297
00:22:47,600 --> 00:22:50,360
budeme chcieť tlačiť na indexe 3.

298
00:22:50,360 --> 00:23:03,550
A to len tak sa stane, že veľkosť a indexy zarovnané, keď tlačí.

299
00:23:03,550 --> 00:23:06,960
>> Kto má pracovný zásobníka implementácie?

300
00:23:06,960 --> 00:23:09,690
Máte pracovné stack jeden. Máte pop pracovať ešte?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Áno. Myslím, že áno.

302
00:23:11,890 --> 00:23:14,610
Program >> funguje a nie je seg chyba, je to vytlačiť?

303
00:23:14,610 --> 00:23:17,520
Má to vytlačiť "úspech" pri spustení?

304
00:23:17,520 --> 00:23:22,630
Jo. Urobte zásobník, spustite ho, ak sa vytlačí "úspech" a nejde boom,

305
00:23:22,630 --> 00:23:26,000
potom všetko je dobré.

306
00:23:26,000 --> 00:23:34,070
Dobrá. Poďme k prístroju naozaj rýchlo,

307
00:23:34,070 --> 00:23:46,100
a prejdeme to.

308
00:23:46,100 --> 00:23:51,110
Ak sa pozrieme na to, čo sa tu deje s pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, čo bolo prvá vec, ktorú urobil?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Ak s.size je väčšia ako 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Dobre. A prečo si to urobil, že?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Uistite sa, že tam bolo niečo vo vnútri zásobníka.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Právo. Ak chcete otestovať, aby sa ubezpečil, že s.size je väčšia ako 0;

314
00:24:10,950 --> 00:24:13,280
inak, čo chceš, aby sa stalo?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? Návrat >> null, presne.

316
00:24:16,630 --> 00:24:20,740
Takže ak s.size je väčšia ako 0. Tak čo budeme robiť?

317
00:24:20,740 --> 00:24:25,890
Čo budeme robiť, keď zásobník nie je prázdny?

318
00:24:25,890 --> 00:24:31,210
[Stella] Tu decrement veľkosť? Tie >> decrement veľkosti, v poriadku.

319
00:24:31,210 --> 00:24:34,440
Tak ako si to urobil, že? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. A potom to, čo si urobil?

321
00:24:37,030 --> 00:24:44,140
[Stella] A potom som povedal: return s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
V opačnom prípade sa vrátite null. Áno, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Prečo to nemusí byť s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Jo >>. >> Mám to.

326
00:24:58,430 --> 00:25:00,980
[Sam] Myslel som, že preto, že ste s 1 von,

327
00:25:00,980 --> 00:25:04,290
potom budete vracať nie je ten, že požiadal.

328
00:25:04,290 --> 00:25:09,400
[Hardison] A to bolo presne to, čo sme hovorili o tejto celej problematike 0 indexov.

329
00:25:09,400 --> 00:25:11,380
Takže keď sme približovania tu.

330
00:25:11,380 --> 00:25:15,650
Ak sa pozrieme na toho chlapa tu, môžete vidieť, že keď sme pop,

331
00:25:15,650 --> 00:25:19,340
sme objavovať prvok na indexe 2.

332
00:25:19,340 --> 00:25:25,200
>> Tak sme znížiť svoju veľkosť ako prvý, potom je naša veľkosť zodpovedá náš index.

333
00:25:25,200 --> 00:25:39,650
Ak nemáme decrement veľkosti, potom musíme urobiť veľkosti -1 a potom útlm.

334
00:25:39,650 --> 00:25:45,270
Great. Všetky dobré?

335
00:25:45,270 --> 00:25:47,530
Akékoľvek otázky na to?

336
00:25:47,530 --> 00:25:54,050
Existuje celý rad rôznych spôsobov, ako napísať to rovnako.

337
00:25:54,050 --> 00:26:03,290
V skutočnosti, môžeme urobiť ešte niečo - čo môžeme urobiť, je jednoriadkový.

338
00:26:03,290 --> 00:26:05,770
Môžeme urobiť jeden riadok návrat.

339
00:26:05,770 --> 00:26:12,980
Takže môžeme skutočne decrement predtým, než sme sa vrátiť tým, že.

340
00:26:12,980 --> 00:26:18,320
Takže uvedenie - pred s.size.

341
00:26:18,320 --> 00:26:22,060
To robí linka naozaj hustá.

342
00:26:22,060 --> 00:26:30,940
V prípade, že rozdiel medzi -. S veľkosťou a s.size--

343
00:26:30,940 --> 00:26:40,130
je, že tento postfix - hovoria, že postfix, pretože - prichádza po s.size--

344
00:26:40,130 --> 00:26:47,430
Znamená to, že s.size je vyhodnotená na účely zistenia indexu

345
00:26:47,430 --> 00:26:50,410
ako je to v súčasnej dobe, kedy sa vykonáva tento riadok,

346
00:26:50,410 --> 00:26:54,290
a potom - sa stane po riadku sa vykoná.

347
00:26:54,290 --> 00:27:00,340
Po prvok na s.size indexu je prístupná.

348
00:27:00,340 --> 00:27:07,260
A to nie je to, čo chceme, pretože chceme, aby úbytok sa stane prvý.

349
00:27:07,260 --> 00:27:10,990
Othewise, budeme pristupovať k polia, efektívne, mimo medze.

350
00:27:10,990 --> 00:27:16,850
Budeme pristupovať k prvku nad ten, ktorý sme vlastne chcete otvoriť.

351
00:27:16,850 --> 00:27:23,840
Jo, Sam? >> Je to rýchlejšie, alebo použiť menej RAM, aby sa v jednej rade, alebo nie?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Úprimne povedané, to naozaj záleží.

353
00:27:29,620 --> 00:27:34,220
[Sam, nezrozumiteľné] >> Jo, to záleží na okolnostiach. Môžete to urobiť kompilátora triky

354
00:27:34,220 --> 00:27:41,580
získať kompilátor uznať, že väčšinou, som si predstaviť.

355
00:27:41,580 --> 00:27:44,840
>> Tak sme sa už zmienil niečo málo o tejto veci optimalizácie kompilátora

356
00:27:44,840 --> 00:27:47,400
že si môžete robiť pri zostavovaní,

357
00:27:47,400 --> 00:27:50,580
a to je to vec, ktorá kompilátor mohol zistiť,

358
00:27:50,580 --> 00:27:54,710
ako oh, hey, možno by som mohol urobiť to všetko v jednej operácii,

359
00:27:54,710 --> 00:27:59,420
ako protichodný k načítanie veľkosť premennej od RAM,

360
00:27:59,420 --> 00:28:03,770
dekrementování to, ukladanie späť, a potom sa načítanie je späť

361
00:28:03,770 --> 00:28:08,000
spracovať zvyšok tejto operácie.

362
00:28:08,000 --> 00:28:10,710
Ale zvyčajne, nie, to nie je ten druh veci

363
00:28:10,710 --> 00:28:20,770
, Čo sa deje, aby sa váš program výrazne rýchlejší.

364
00:28:20,770 --> 00:28:26,000
Nejaké ďalšie otázky týkajúce sa sad?

365
00:28:26,000 --> 00:28:31,360
>> Takže tlačenie a praskanie. Ak ste chalani chcú vyskúšať hackerské vydania,

366
00:28:31,360 --> 00:28:33,660
čo sme urobili v hackerské vydanie je skutočne preč

367
00:28:33,660 --> 00:28:37,670
a robil to stack rastie dynamicky.

368
00:28:37,670 --> 00:28:43,190
Úlohou je predovšetkým tu v tlačnej funkciu,

369
00:28:43,190 --> 00:28:48,820
prísť na to, ako urobiť, aby pole rastú

370
00:28:48,820 --> 00:28:52,450
ako si udržať tlačiť viac a viac prvkov na do zásobníka.

371
00:28:52,450 --> 00:28:56,000
Je to vlastne nie je moc doplnkový kód.

372
00:28:56,000 --> 00:29:00,080
Len volanie - musíte mať na pamäti dostať volania malloc tam správne,

373
00:29:00,080 --> 00:29:03,310
a potom zistiť, kedy budete volať realloc.

374
00:29:03,310 --> 00:29:06,090
To je zábavné problém, ak máte záujem.

375
00:29:06,090 --> 00:29:11,550
>> Ale v súčasnej dobe, poďme ďalej, a poďme hovoriť o frontoch.

376
00:29:11,550 --> 00:29:15,680
Prechádzajte tu.

377
00:29:15,680 --> 00:29:19,340
Fronta je blízko súrodenec zásobníka.

378
00:29:19,340 --> 00:29:25,380
Takže v zásobníku, boli veci, ktoré dal v poslednej

379
00:29:25,380 --> 00:29:28,810
boli prvé veci, a potom byť načítaná.

380
00:29:28,810 --> 00:29:33,600
Máme to posledné dovnútra, prvý von, alebo LIFO, objednávanie.

381
00:29:33,600 --> 00:29:38,390
Vzhľadom k tomu, vo fronte, ako by ste očakávali od okamihu, kedy ste stál vo fronte,

382
00:29:38,390 --> 00:29:41,980
prvá osoba, ktorá sa v súlade, prvá vec, dostať sa do fronty,

383
00:29:41,980 --> 00:29:47,630
je prvá vec, ktorá sa dostane načítať z frontu.

384
00:29:47,630 --> 00:29:51,490
Fronty sú tiež často používa, keď máme čo do činenia s grafmi,

385
00:29:51,490 --> 00:29:55,560
ako by sme hovorili o stručne s komíny,

386
00:29:55,560 --> 00:30:00,260
a fronty sú tiež užitočné pre veľa ďalších vecí.

387
00:30:00,260 --> 00:30:06,180
Jedna vec, ktorá príde často sa snaží udržiavať, napríklad,

388
00:30:06,180 --> 00:30:12,310
zoradený zoznam prvkov.

389
00:30:12,310 --> 00:30:17,650
A môžete to urobiť pomocou poľa. Môžete udržiavať zoradený zoznam vecí v matici,

390
00:30:17,650 --> 00:30:20,650
ale tam, kde to dostane zložité je potom budete mať vždy nájsť

391
00:30:20,650 --> 00:30:26,160
vhodné miesto pre vloženie ďalšia vec.

392
00:30:26,160 --> 00:30:28,250
Takže ak máte rad čísel, 1 až 10,

393
00:30:28,250 --> 00:30:31,630
a potom chcete rozšíriť, že na všetky čísla 1 až 100,

394
00:30:31,630 --> 00:30:33,670
a vy ste stále tieto čísla v náhodnom poradí a snaží sa udržať všetko

395
00:30:33,670 --> 00:30:40,650
zoradené, ako si prejsť, môžete skončiť museli urobiť veľa radenie.

396
00:30:40,650 --> 00:30:43,910
U niektorých typov front a niektorých typov podkladových dátových štruktúr,

397
00:30:43,910 --> 00:30:46,670
môžete skutočne udržať pomerne jednoduchý.

398
00:30:46,670 --> 00:30:50,640
Nemáte niečo pridať a potom preorganizovať celá vec zakaždým.

399
00:30:50,640 --> 00:30:56,770
Ani budete musieť urobiť veľa posunutie vnútorných prvkov okolo.

400
00:30:56,770 --> 00:31:02,990
Keď sa pozrieme na fronte, uvidíte, že - aj v queue.c v úseku -

401
00:31:02,990 --> 00:31:10,950
struct, že sme rovnako vám je naozaj podobný struct, že sme vám dal na stack.

402
00:31:10,950 --> 00:31:13,770
>> Je tu ešte jedna výnimka z tohto, a že jedna výnimka

403
00:31:13,770 --> 00:31:21,700
je to, že máme túto dodatočnú integer s názvom hlava,

404
00:31:21,700 --> 00:31:28,120
a hlava je tu pre sledovanie hlavy frontu,

405
00:31:28,120 --> 00:31:32,160
alebo prvý prvok v rade.

406
00:31:32,160 --> 00:31:37,470
S hromadou, sme boli schopní sledovať prvku, ktorý sme mali k načítaniu,

407
00:31:37,470 --> 00:31:40,800
alebo hornej časti zásobníka, používať len veľkosť,

408
00:31:40,800 --> 00:31:44,220
vzhľadom k tomu, s frontu, sme sa museli vysporiadať s opačných koncoch.

409
00:31:44,220 --> 00:31:49,000
Snažíme križovať veci na konci, ale potom sa vrátia veci z prednej strany.

410
00:31:49,000 --> 00:31:54,640
Takže účinne, s hlavou, máme index na začiatku fronty,

411
00:31:54,640 --> 00:31:58,920
a veľkosť nám index na konci fronty

412
00:31:58,920 --> 00:32:03,730
takže môžeme získať veci z hlavy a pridať veci k chvostu.

413
00:32:03,730 --> 00:32:06,890
Vzhľadom k tomu, s komínom, sme boli vždy len zaoberajúca sa v hornej časti zásobníka.

414
00:32:06,890 --> 00:32:08,900
Nikdy sme nemali prístup na dno zásobníka.

415
00:32:08,900 --> 00:32:12,220
My len pridané veci na vrchole a sa veci preč z hornej

416
00:32:12,220 --> 00:32:17,470
takže sme nepotrebovali, že ďalšie pole vnútri našej struct.

417
00:32:17,470 --> 00:32:20,590
Znamená to, že všeobecne zmysel?

418
00:32:20,590 --> 00:32:27,670
Dobrá. Áno, Charlotte? [Charlotte, nezrozumiteľným]

419
00:32:27,670 --> 00:32:32,660
[Hardison] To je veľká otázka, a to ten, ktorý prišiel v prednáške.

420
00:32:32,660 --> 00:32:36,290
Možno prechádzal niekoľkých príkladoch ukážeme, prečo

421
00:32:36,290 --> 00:32:41,400
nechceme používať struny [0] ako hlavu frontu.

422
00:32:41,400 --> 00:32:46,770
>> Tak si predstavte, že máme front, budeme hovoriť, že fronty.

423
00:32:46,770 --> 00:32:49,210
Na začiatku, keď sme práve inštanciu to,

424
00:32:49,210 --> 00:32:53,330
keď sme práve oznamoval, sme nie je inicializovaná nič.

425
00:32:53,330 --> 00:32:56,790
Je to všetko smeti. Takže samozrejme chceme, aby sa ubezpečil, že inicializuje

426
00:32:56,790 --> 00:33:00,950
ako veľkosť a hlavy poľa na 0, niečo rozumné.

427
00:33:00,950 --> 00:33:05,770
Mohli by sme tiež pokračovať a hodnotu null z prvkov v našom fronte.

428
00:33:05,770 --> 00:33:09,930
A aby sa tento diagram fit, zistíte, že sa naše fronty môže mať iba tri prvky;

429
00:33:09,930 --> 00:33:13,150
vzhľadom k tomu, naše stack mohol držať štyri, môže naša frontu len držať tri.

430
00:33:13,150 --> 00:33:18,680
A to len preto, aby sa diagram fit.

431
00:33:18,680 --> 00:33:26,150
Prvá vec, ktorá sa tu deje je, že sme Zaradí reťazec "ahoj".

432
00:33:26,150 --> 00:33:30,380
A rovnako ako sme to urobili s zásobníka, nič hrozne tu iný,

433
00:33:30,380 --> 00:33:39,230
hodíme reťazca na na struny [0] a vložili naše veľkosť o 1.

434
00:33:39,230 --> 00:33:42,720
My Zaradí "bye", dostane sa na seba.

435
00:33:42,720 --> 00:33:45,870
Takže to vyzerá ako hromada z podstatnej časti.

436
00:33:45,870 --> 00:33:53,230
Začali sme tu, nový prvok, nový prvok, veľkosť udržuje ísť hore.

437
00:33:53,230 --> 00:33:56,330
Čo sa stane v tomto okamihu, kedy chceme, aby dequeue niečo?

438
00:33:56,330 --> 00:34:01,280
Ak chceme dequeue, ktorá je prvok, ktorý chceme dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Presne tak, Basil.

440
00:34:04,110 --> 00:34:10,960
Chceme sa zbaviť prvého reťazca, toto jeden, "hi".

441
00:34:10,960 --> 00:34:13,170
Takže to, čo je ďalšia vec, ktorá sa zmenilo?

442
00:34:13,170 --> 00:34:17,010
Všimnite si, keď sme vyskočila niečo z frontu, len sme zmenili veľkosť,

443
00:34:17,010 --> 00:34:22,080
ale tu, máme pár vecí, ktoré sa menia.

444
00:34:22,080 --> 00:34:27,440
Nielen, že sa veľkosť zmeny, ale hlava zmeny.

445
00:34:27,440 --> 00:34:31,020
Toto sa vracia do bodu Charlotte staršie:

446
00:34:31,020 --> 00:34:38,699
prečo máme tento hlavu rovnako?

447
00:34:38,699 --> 00:34:42,110
Má to zmysel teraz, Charlotte? >> Druh.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Druh? Takže to, čo sa stalo, keď sme dequeued?

449
00:34:47,500 --> 00:34:54,340
Čo hlava to, že teraz je zaujímavé?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] No, pretože sa to zmenilo - v poriadku. Aha.

451
00:34:56,449 --> 00:35:02,090
Vzhľadom k tomu, hlava - kde hlava smeruje k zmenám, pokiaľ ide o umiestnenie.

452
00:35:02,090 --> 00:35:07,200
Je to už nie je vždy nula index jeden. >> Jo, presne tak.

453
00:35:07,200 --> 00:35:17,660
Čo sa stalo, ak bolo dequeueing vysokú prvok

454
00:35:17,660 --> 00:35:20,590
bola dokončená a my sme nemali túto hlavu poľa

455
00:35:20,590 --> 00:35:26,880
pretože sme boli vždy volať tento reťazec na 0 indexu hlava našej frontu,

456
00:35:26,880 --> 00:35:30,170
potom by sme museli posunúť zvyšok frontu dole.

457
00:35:30,170 --> 00:35:36,010
Museli by sme sa posunúť "bye" od z reťazca [1] na reťazce [0].

458
00:35:36,010 --> 00:35:38,760
A reťazca [2] sa stanovuje na reťazce [1].

459
00:35:38,760 --> 00:35:43,050
A budeme musieť urobiť pre celý zoznam prvkov,

460
00:35:43,050 --> 00:35:45,110
celý rad prvkov.

461
00:35:45,110 --> 00:35:50,490
A keď to robíme s radom, ktorá sa naozaj nákladné.

462
00:35:50,490 --> 00:35:53,340
Tak tu, to nie je veľký problém. Musíme len tri prvky v našom poli.

463
00:35:53,340 --> 00:35:57,230
Ale keby sme mali front tisíc prvkov alebo milión prvky,

464
00:35:57,230 --> 00:36:00,060
a potom všetci naraz, začneme robiť veľa Dequeue volá všetky v slučke,

465
00:36:00,060 --> 00:36:03,930
veci naozaj spomaliť, pretože presúva všetko dolu neustále.

466
00:36:03,930 --> 00:36:07,320
Viete, posunúť o 1, posun o 1, posun o 1, posun o 1.

467
00:36:07,320 --> 00:36:13,650
Miesto toho, my používame túto hlavu, hovoríme, že "ukazovateľ", aj keď to nie je naozaj ukazovateľ

468
00:36:13,650 --> 00:36:16,430
v pravom slova zmysle, nie je to ukazovateľ typu.

469
00:36:16,430 --> 00:36:19,410
Nie je to int * alebo char * alebo niečo podobné.

470
00:36:19,410 --> 00:36:28,930
Ale je to ukazovať alebo označujúci hlavu našej frontu. Jo?

471
00:36:28,930 --> 00:36:38,800
>> [Študent] Ako Dequeue vedieť len pop off, čo je v čele?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Ako Dequeue vedieť, ako sa pop off, čo je v čele? Právo >> jo.

473
00:36:43,620 --> 00:36:49,050
>> Čo je to pri pohľade na to len, čo hlava pole je nastavený na.

474
00:36:49,050 --> 00:36:52,710
Takže v tomto prvom prípade, keď sa pozrieme tu,

475
00:36:52,710 --> 00:36:55,690
Naša hlava je 0, index 0. Právo >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Tak to len hovorí, že v poriadku, dobre, prvok na indexe 0, reťazec "ahoj",

477
00:37:00,500 --> 00:37:03,050
je prvok v čele našej frontu.

478
00:37:03,050 --> 00:37:05,570
Takže budeme dequeue toho chlapa.

479
00:37:05,570 --> 00:37:09,800
A to bude prvok, ktorý sa vrátil do volajúcemu.

480
00:37:09,800 --> 00:37:14,540
Áno, Saad? Takže >> hlava v podstate nastaví - kde budete indexovať?

481
00:37:14,540 --> 00:37:17,750
To je začiatok toho? Jo >>. Dobre >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] To stáť nový začiatok pre naše pole.

483
00:37:22,900 --> 00:37:28,930
Takže keď dequeue niečo, všetko, čo musíte urobiť, je prístup k prvku na indexe q.head,

484
00:37:28,930 --> 00:37:32,240
a že bude prvok, ktorý chcete dequeue.

485
00:37:32,240 --> 00:37:34,930
Máte tiež decrement veľkosti.

486
00:37:34,930 --> 00:37:39,430
Uvidíme sa za chvíľku, kedy sa veci trochu zložitejšie s tým.

487
00:37:39,430 --> 00:37:46,520
My dequeue, a teraz, keď sa Zaradí znova,

488
00:37:46,520 --> 00:37:51,300
kde máme Zaradí?

489
00:37:51,300 --> 00:37:55,000
Ak sa ďalší prvok ísť v našej fronte?

490
00:37:55,000 --> 00:37:57,980
Povedzme, že chceme, aby Zaradí reťazec "SK".

491
00:37:57,980 --> 00:38:02,240
Do ktorého index to pôjde? [Študenti] Reťazce [2]. Dva >>.

492
00:38:02,240 --> 00:38:04,980
Prečo 2 a nie 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Vzhľadom k tomu, teraz hlava je 1, tak, že je ako na začiatku zoznamu?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Právo. A čo označuje koniec zoznamu?

495
00:38:21,220 --> 00:38:23,290
Čo sme pomocou naznačovať koniec našej fronty?

496
00:38:23,290 --> 00:38:25,970
Hlava je hlava našej fronty, začiatok nášho fronty.

497
00:38:25,970 --> 00:38:29,530
Aký je koniec nášho fronty? [Študenti] Veľkosť. Veľkosť >> presne.

498
00:38:29,530 --> 00:38:36,360
Takže naše nové prvky ísť na veľkosti, a prvky, ktoré sa vzlietnuť zložiť na hlavu.

499
00:38:36,360 --> 00:38:45,390
Keď sme Zaradí ďalší prvok, sme dávať ho do veľkosti.

500
00:38:45,390 --> 00:38:48,530
[Študent] Než dáte, že v keď, veľkosť bola 1, nie?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Právo. Tak nie je úplne na veľkosti. Veľkosť +, nie 1, ale + hlava.

502
00:38:55,690 --> 00:38:59,990
Pretože sme posunul všetko za hlavu čiastky.

503
00:38:59,990 --> 00:39:14,270
Tak tu, teraz máme fronty veľkosti 1, ktorá začína na indexe 1.

504
00:39:14,270 --> 00:39:20,730
Chvost je index 2. Áno?

505
00:39:20,730 --> 00:39:25,780
>> [Študent] Čo sa stane, keď sa Dequeue reťazca [0], a sloty Reťazce "v pamäti

506
00:39:25,780 --> 00:39:29,420
Len si vyprázdnila, v podstate, alebo len zabudli?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Jo. V tomto zmysle, my sme len zabudnúť je.

508
00:39:34,700 --> 00:39:42,640
Ak by sme boli ukladanie kópií nich -

509
00:39:42,640 --> 00:39:46,310
veľa dátových štruktúr sa často ukladať svoje vlastné kópie prvkov

510
00:39:46,310 --> 00:39:51,760
tak, že osoba riadiaca dátové štruktúry nemá na starosti

511
00:39:51,760 --> 00:39:53,650
o tom, kde všetky tie ukazovatele budú.

512
00:39:53,650 --> 00:39:56,000
Dátová štruktúra má na všetko, má na všetkých kópií,

513
00:39:56,000 --> 00:39:59,580
aby sa ubezpečil, že všetko trvá primerane.

514
00:39:59,580 --> 00:40:03,140
Avšak v tomto prípade, tieto dátové štruktúry len pre jednoduchosť

515
00:40:03,140 --> 00:40:05,580
nie sú zhotovovanie kópií niečo, čo sme ukladaním v nich.

516
00:40:05,580 --> 00:40:08,630
[Študent] Tak je to kontinuálna pole -? Áno >>.

517
00:40:08,630 --> 00:40:14,350
Ak sa pozrieme späť na to, čo definícia bola tejto štruktúry, je.

518
00:40:14,350 --> 00:40:19,110
Je to len štandardné pole, ako keď ste videli,

519
00:40:19,110 --> 00:40:24,280
poľa * char s

520
00:40:24,280 --> 00:40:26,340
Znamená to, že -? >> Jo, len som premýšľal,

521
00:40:26,340 --> 00:40:29,130
ak budete nakoniec dôjdu pamäte, do určitej miery,

522
00:40:29,130 --> 00:40:32,330
Ak máte všetky tieto prázdne miesta vo vašom poli?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Jo, to je dobrá pripomienka.

524
00:40:36,390 --> 00:40:41,530
>> Ak sa pozrieme na to, čo sa stalo dnes v tomto bode,

525
00:40:41,530 --> 00:40:46,350
sme zaplnila naše frontu, ako to vyzerá.

526
00:40:46,350 --> 00:40:50,390
Ale my sme naozaj naplnená naša fronty

527
00:40:50,390 --> 00:40:57,710
pretože máme front, ktorá má veľkosť 2, ale začína na indexe 1,

528
00:40:57,710 --> 00:41:02,160
pretože to je miesto, kde naša hlava je ukazovateľ.

529
00:41:02,160 --> 00:41:08,400
Rovnako ako si hovoril, že prvok v reťazci [0], na indexe 0, je v skutočnosti neexistuje.

530
00:41:08,400 --> 00:41:10,450
Nie je to v našej fronte už.

531
00:41:10,450 --> 00:41:16,460
Len sme sa neobťažoval ísť a prepísať ho, keď sme dequeued to.

532
00:41:16,460 --> 00:41:18,700
Takže aj keď to vyzerá, že sme k vyčerpaniu pamäte, naozaj nie.

533
00:41:18,700 --> 00:41:23,270
To miesto je k dispozícii pre nás používať.

534
00:41:23,270 --> 00:41:29,310
Vhodné správanie, ak by sme mali vyskúšať a prvý Dequeue niečo

535
00:41:29,310 --> 00:41:34,420
ako "bye", že by sa pop bye off.

536
00:41:34,420 --> 00:41:38,460
Teraz naša fronta začína na indexe 2 a je o veľkosti 1.

537
00:41:38,460 --> 00:41:42,240
A teraz, keď sa snažíme a Zaradí zase niečo, povedzme 50,

538
00:41:42,240 --> 00:41:47,880
50 by mala ísť v tomto mieste v indexe 0

539
00:41:47,880 --> 00:41:51,270
pretože je to stále k dispozícii pre nás. Áno, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Stáva sa to automaticky?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Nestáva sa úplne automaticky. Musíte si to spočítajte

542
00:41:56,150 --> 00:42:00,380
aby to fungovalo, ale v podstate to, čo sme urobili je, že sme práve omotal okolo.

543
00:42:00,380 --> 00:42:04,070
[Saad] A je to v poriadku, ak to má dieru uprostred toho?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ak môžeme matematický fungovať správne.

545
00:42:08,720 --> 00:42:15,470
>> A ukázalo sa, že to vlastne nie je tak ťažké urobiť s mod operátora.

546
00:42:15,470 --> 00:42:20,040
Tak ako sme to urobili s Caesarom a ďalšie veci crypto,

547
00:42:20,040 --> 00:42:25,190
pomocou mod, môžeme robiť veci zabaliť okolo a ísť ďalej

548
00:42:25,190 --> 00:42:28,090
okolo a dokola a dokola s našou fronte,

549
00:42:28,090 --> 00:42:32,180
vedenie, ktoré hlava ukazovateľ pohybuje.

550
00:42:32,180 --> 00:42:38,840
Si všimnúť, že veľkosť je vždy v počte prvkov v skutočnosti v fronty.

551
00:42:38,840 --> 00:42:43,110
A je to len hlava ukazovateľ, ktorý udržuje vystriedať.

552
00:42:43,110 --> 00:42:49,660
Ak sa pozrieme na to, čo sa tu stalo, ak by sme sa vrátiť na začiatok,

553
00:42:49,660 --> 00:42:55,020
a vy sa len pozerať, čo sa deje na hlavu

554
00:42:55,020 --> 00:42:58,240
keď sme Zaradí niečo, nič sa nestalo, aby na hlave.

555
00:42:58,240 --> 00:43:00,970
Keď sme vo fronte niečo iné, nič sa nestalo, aby na hlave.

556
00:43:00,970 --> 00:43:04,130
Hneď ako sme dequeued niečo, hlava sa zdvihne o jednu.

557
00:43:04,130 --> 00:43:06,600
My vo fronte niečo, nič sa nestane do hlavy.

558
00:43:06,600 --> 00:43:11,060
Keď sme dequeue niečo, hlava zrazu dostane zvýšený.

559
00:43:11,060 --> 00:43:14,660
Keď sme Zaradí niečo, nič sa nestane do hlavy.

560
00:43:14,660 --> 00:43:20,240
>> Čo by sa stalo v tomto bode, ak by sme mali dequeue zase niečo?

561
00:43:20,240 --> 00:43:23,240
Akékoľvek myšlienky? Čo by sa stalo do hlavy?

562
00:43:23,240 --> 00:43:27,190
Čo by sa malo stať na hlave

563
00:43:27,190 --> 00:43:32,990
ak by sme mali dequeue niečo iné?

564
00:43:32,990 --> 00:43:35,400
Hlava teraz je na indexe 2,

565
00:43:35,400 --> 00:43:38,920
, Čo znamená, že hlava fronte reťazca [2].

566
00:43:38,920 --> 00:43:44,280
[Študent] Ktorá vracia 0? Je >> by sa mala vrátiť do 0. To by zabaliť späť okolo, presne.

567
00:43:44,280 --> 00:43:48,440
Zatiaľ zakaždým, keď sme hovorili Dequeue, sme boli pridanie jedného do hlavy,

568
00:43:48,440 --> 00:43:50,960
pridať jeden do hlavy, pridať jeden do hlavy, pridať jeden do hlavy.

569
00:43:50,960 --> 00:43:58,400
Akonáhle že hlava ukazovateľ dostane na posledný index v našom poli,

570
00:43:58,400 --> 00:44:05,650
potom musíme zabaliť späť k začiatku, ísť späť do 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Čo určuje kapacitu fronty v zásobníku?

572
00:44:09,900 --> 00:44:13,120
[Hardison] V tomto prípade, práve sme používali # definovaný konštantný. Dobre >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] V aktuálnej. Súboru c, môžete ísť a špina sa to trochu

574
00:44:19,590 --> 00:44:21,710
a urobiť z neho taký veľký, alebo tak málo, ako chcete.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Takže, keď robíte to frontu, ako si urobiť počítač vedieť

576
00:44:25,310 --> 00:44:29,120
aký veľký chcete stack byť?

577
00:44:29,120 --> 00:44:31,700
[Hardison] To je veľká otázka.

578
00:44:31,700 --> 00:44:34,800
Existuje niekoľko spôsobov, ako. Jedným z nich je práve definovať dopredu

579
00:44:34,800 --> 00:44:42,050
a hovoria, že toto bude fronta, ktorá má 4 prvky alebo 50 prvkov alebo 10000.

580
00:44:42,050 --> 00:44:45,430
Druhým spôsobom je robiť to, čo ľudia hackerov vydanie robia

581
00:44:45,430 --> 00:44:52,310
a vytvárať funkcie, aby sa vaše frontu dynamicky rastie, pretože stále viac sa veci znie a

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Tak, aby šiel s prvou možnosťou, čo syntax sa používa

583
00:44:54,740 --> 00:44:57,830
povedať programu, čo je veľkosť fronty?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Takže poďme sa dostať z toho.

585
00:45:04,780 --> 00:45:12,650
Som stále v stack.c tu, tak som len tak prechádzať až na vrchol tu.

586
00:45:12,650 --> 00:45:17,920
Vidíte toto právo tu? To je # define kapacitu 10.

587
00:45:17,920 --> 00:45:24,600
A to je takmer presne rovnaké syntaxe, ktoré máme k fronte.

588
00:45:24,600 --> 00:45:28,390
Okrem vo fronte, máme extra struct poľa tu.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, myslel som, že kapacita znamená kapacitu pre reťazce.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> To, že je to maximálna dĺžka slova. >> Mám to.

591
00:45:36,770 --> 00:45:41,180
Jo. Kapacita tu - to je skvelý bod.

592
00:45:41,180 --> 00:45:44,000
A to je niečo, čo je zložité

593
00:45:44,000 --> 00:45:49,480
pretože to, čo sme vykazovať tu je rada * char s

594
00:45:49,480 --> 00:45:52,770
Pole ukazovateľov.

595
00:45:52,770 --> 00:45:56,690
To je pole znakov.

596
00:45:56,690 --> 00:46:01,690
To je asi to, čo ste videli, keď ste vyhlásil svoje vyrovnávacej pamäte pre súbor I / O,

597
00:46:01,690 --> 00:46:06,840
keď ste boli vytvorenie reťazca ručne na zásobníku.

598
00:46:06,840 --> 00:46:09,090
Avšak to, čo tu máme, je rad char * s

599
00:46:09,090 --> 00:46:13,400
Takže je to pole ukazovateľov.

600
00:46:13,400 --> 00:46:18,350
Vlastne, keď sa priblížite von a pozrieme sa na to, čo sa tu deje

601
00:46:18,350 --> 00:46:23,140
v prezentácii, môžete vidieť, že skutočné prvky, posunková dáta

602
00:46:23,140 --> 00:46:26,180
nie je uložený v matici sám.

603
00:46:26,180 --> 00:46:42,690
Čo je uložená v našom poli tu sú odkazy k charakteru dát.

604
00:46:42,690 --> 00:46:52,560
Dobre. Takže sme videli, ako veľkosť frontu je rovnako ako u zásobníka,

605
00:46:52,560 --> 00:46:58,670
veľkosť vždy dodrží počet prvkov v súčasnej dobe v rade.

606
00:46:58,670 --> 00:47:02,720
Po vykonaní 2 enqueues, veľkosť je 2.

607
00:47:02,720 --> 00:47:07,110
Po vykonaní Dequeue veľkosť je teraz 1.

608
00:47:07,110 --> 00:47:09,330
Po vykonaní ďalšie Zaradí veľkosť späť na 2.

609
00:47:09,330 --> 00:47:12,340
Takže veľkosť rozhodne dodrží počet prvkov vo fronte,

610
00:47:12,340 --> 00:47:15,580
a potom sa hlava len udržuje na bicykli.

611
00:47:15,580 --> 00:47:20,210
To ide od 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
A zakaždým, keď hovoríme Dequeue, dostane hlava ukazovateľ zvýšil na ďalšie index.

613
00:47:25,620 --> 00:47:29,930
A ak hlava je asi ísť cez, to tvorí späť okolo 0.

614
00:47:29,930 --> 00:47:34,870
Takže s tým, my môžeme písať Dequeue funkciu.

615
00:47:34,870 --> 00:47:40,200
A budeme opustiť Zaradí funkciu pre vy realizovať miesto.

616
00:47:40,200 --> 00:47:45,880
>> Keď sme dequeue prvok z našej frontu,

617
00:47:45,880 --> 00:47:55,490
Čo bola prvá vec, ktorá Daniel urobil, keď sme začali písať pop funkciu pre komíny?

618
00:47:55,490 --> 00:48:00,490
Nechaj ma počuť od niekoho, kto sa nehovorí ešte.

619
00:48:00,490 --> 00:48:06,710
Poďme sa pozrieť, Saad, pamätáš si, čo Daniel urobil ako prvú vec, keď on písal pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Tam bol, bolo to - >> Skúsil niečo.

621
00:48:08,860 --> 00:48:12,140
[Saad] Ak je veľkosť väčšia ako 0. Presne >>.

622
00:48:12,140 --> 00:48:14,390
A čo to bolo testovanie?

623
00:48:14,390 --> 00:48:19,090
[Saad] To bolo testovanie, či tam je niečo vnútri poľa.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Jo. Presne tak. Takže nemôžete pop nič z fronty, ak je prázdna.

625
00:48:23,210 --> 00:48:26,510
Rovnako tak, nemôžete dequeue nič z fronty, ak je prázdna.

626
00:48:26,510 --> 00:48:30,420
Čo je prvá vec, ktorú by sme mali urobiť v našej Dequeue funkciu tu, myslíš?

627
00:48:30,420 --> 00:48:33,860
[Saad] Ak veľkosť je väčšia ako 0? Jo >>.

628
00:48:33,860 --> 00:48:37,710
V tomto prípade, som vlastne len testované, či je 0.

629
00:48:37,710 --> 00:48:42,240
Ak je 0, môžeme sa vrátiť null.

630
00:48:42,240 --> 00:48:45,280
Ale presne rovnaká logika.

631
00:48:45,280 --> 00:48:49,110
A budeme pokračovať s tým.

632
00:48:49,110 --> 00:48:54,600
Ak je veľkosť nie je 0, kde je prvok, ktorý chceme dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] V čele? Presne >>.

634
00:48:58,550 --> 00:49:01,720
Môžeme len vytiahnuť prvý prvok v našej fronte

635
00:49:01,720 --> 00:49:07,040
prístupom prvok v čele.

636
00:49:07,040 --> 00:49:14,630
Nič blázon.

637
00:49:14,630 --> 00:49:19,620
Po tom, čo by sme mali urobiť? Čo sa musí stať?

638
00:49:19,620 --> 00:49:23,740
Aká bola ďalšia vec, ktorá sme sa rozprávali o v Dequeue?

639
00:49:23,740 --> 00:49:28,130
Dve veci sa stalo, pretože naše fronta zmenila.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Zmenšenie veľkosti. >> Máme pre zníženie veľkosti, a zvýšiť hlavu? Presne tak.

641
00:49:35,640 --> 00:49:40,600
Pre zvýšenie hlavu, nemôžeme slepo zvýšiť hlavu, zapamätať.

642
00:49:40,600 --> 00:49:45,080
Nemôžeme jednoducho queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Musíme tiež tento mod od kapacity.

644
00:49:51,630 --> 00:49:54,740
A prečo mod o kapacitu, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Vzhľadom k tomu, že má obtekať okolo. Presne >>.

646
00:49:58,680 --> 00:50:04,750
My mod o kapacitu, pretože má zabaliť späť k 0.

647
00:50:04,750 --> 00:50:07,400
Takže teraz, v tomto okamihu, môžeme urobiť to, čo povedal Daniel.

648
00:50:07,400 --> 00:50:12,700
Môžeme decrement veľkosť.

649
00:50:12,700 --> 00:50:29,170
A potom môžeme len vrátiť prvok, ktorý bol v hornej časti frontu.

650
00:50:29,170 --> 00:50:34,000
Vyzerá to trochu drsný na prvom mieste. Môžete mať otázku. Je nám ľúto?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Prečo to najprv na začiatok fronty? Pokiaľ to ide?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Pochádza zo štvrtej série na dne.

653
00:50:42,480 --> 00:50:46,060
Potom, čo sme testovať, aby sa ubezpečil, že naša fronta nie je prázdna,

654
00:50:46,060 --> 00:50:54,100
sme vytiahnuť char * Najskôr sme vytiahnite prvok, ktorý sedí v čele indexu

655
00:50:54,100 --> 00:50:58,680
nášho poľa, z nášho reťazca poľa, >> a volať, že prvý?

656
00:50:58,680 --> 00:51:04,500
[Hardison] A hovoríme, že ako prvý. Jo.

657
00:51:04,500 --> 00:51:09,850
Stačí nadviazať na to, že dôvod, prečo si myslíte, že sme to museli urobiť, že?

658
00:51:09,850 --> 00:51:18,270
[Sam] Každý prvý práve vracia q.strings [q.head]? Jo >>.

659
00:51:18,270 --> 00:51:23,830
Vzhľadom k tomu, >> robíme táto výmena q.head s mod funkcií,

660
00:51:23,830 --> 00:51:27,810
a neexistuje žiadny spôsob, ako to urobiť, aby v rámci spätného line tiež.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Presne tak. Ste na mieste. Sam úplne na mieste.

662
00:51:31,640 --> 00:51:36,800
Dôvod, prečo sme museli vytiahnuť prvý prvok v našom fronte a uložiť ho do premennej

663
00:51:36,800 --> 00:51:43,030
Je tomu tak preto tento riadok, kde sme práve q.head,

664
00:51:43,030 --> 00:51:47,030
je tu mod prevádzkovateľ tam nie je niečo, čo môžeme urobiť,

665
00:51:47,030 --> 00:51:51,230
a sú to prejaví na hlave bez - v jednej línii.

666
00:51:51,230 --> 00:51:54,480
Takže sme vlastne musieť vytiahnuť prvý prvok, potom nastavte hlavu,

667
00:51:54,480 --> 00:52:00,430
upraviť veľkosť, a potom sa vrátiť na prvok, ktorý sme vytiahnuté.

668
00:52:00,430 --> 00:52:02,680
A to je niečo, čo uvidíme prísť neskôr

669
00:52:02,680 --> 00:52:04,920
spojené zoznamy, ako hráme si s nimi.

670
00:52:04,920 --> 00:52:08,410
Často, keď ste uvoľnenie alebo odstránenie prepojených zoznamov

671
00:52:08,410 --> 00:52:13,500
musíte mať na pamäti ďalší prvok, ďalšie ukazovateľ prepojeného zoznamu

672
00:52:13,500 --> 00:52:16,330
Pred likvidáciou tej súčasnej.

673
00:52:16,330 --> 00:52:23,580
Pretože inak by ste zahodiť informácie o tom, čo zostalo v zozname.

674
00:52:23,580 --> 00:52:34,160
Teraz, keď idete do svojho zariadenia, môžete otvoriť queue.c--x z toho.

675
00:52:34,160 --> 00:52:39,390
Takže keď som otvoriť queue.c, dovoľte mi, aby som zoom sem,

676
00:52:39,390 --> 00:52:44,970
uvidíte, že máte podobne vyzerajúci súbor.

677
00:52:44,970 --> 00:52:49,200
Podobné vyzerajúci súbor na to, čo sme mali predtým s stack.c.

678
00:52:49,200 --> 00:52:54,690
Máme naše struct pre front definovanú rovnako ako sme videli na snímkach.

679
00:52:54,690 --> 00:52:59,870
>> Máme Zaradí funkciu, ktorá je pre vás urobiť.

680
00:52:59,870 --> 00:53:04,340
A máme Dequeue funkciu tu.

681
00:53:04,340 --> 00:53:06,870
Dequeue funkcie v súbore je implementované,

682
00:53:06,870 --> 00:53:13,230
ale ja ju späť až na PowerPoint, takže môžete zadať do, ak budete chcieť.

683
00:53:13,230 --> 00:53:16,690
Takže pre ďalších 5 minút alebo tak, vy pracovať na Zaradí

684
00:53:16,690 --> 00:53:22,570
čo je takmer pravým opakom Dequeue.

685
00:53:22,570 --> 00:53:29,560
Nemusíte upraviť hlavu, keď ste enqueueing, ale to, čo máte nastaviť?

686
00:53:29,560 --> 00:53:38,920
Veľkosť. Takže keď enqueue, hlava zostáva nedotknutý, dostane zmení veľkosť.

687
00:53:38,920 --> 00:53:46,920
Ale to sa trochu - budete musieť pohrať s tou mod

688
00:53:46,920 --> 00:53:57,560
prísť na to, čo presne index nový prvok by mal byť vložený na.

689
00:53:57,560 --> 00:54:03,080
Takže ti dám si chalani trochu, dal dequeue späť na snímke,

690
00:54:03,080 --> 00:54:05,200
a ako vy máte otázky, kričať von tak, že môžeme

691
00:54:05,200 --> 00:54:09,220
všetci hovoria o nich ako o skupine.

692
00:54:09,220 --> 00:54:13,960
Tiež, s veľkosťou nie - keď upravíte veľkosť, môžete vždy len -

693
00:54:13,960 --> 00:54:18,720
máte k mod veľkosť vôbec? [Daniel] No >> Nemusíte sa mod veľkosti, vpravo.

694
00:54:18,720 --> 00:54:24,260
Vzhľadom k tomu, veľkosť bude vždy, ak Si - za predpokladu, že ste správu vecí správne,

695
00:54:24,260 --> 00:54:30,840
veľkosť bude vždy medzi 0 a 3.

696
00:54:30,840 --> 00:54:38,680
Kde máte na mod, keď robíte Zaradí?

697
00:54:38,680 --> 00:54:41,060
[Študent] Iba pre hlavu. Iba >> pre hlavu, presne.

698
00:54:41,060 --> 00:54:44,620
A prečo máte na mod vôbec Zaradí?

699
00:54:44,620 --> 00:54:48,830
Ak je situácia, v ktorej budete musieť mod?

700
00:54:48,830 --> 00:54:53,630
[Študent] Ak máte veci v medzerách, ako na priestor 1 a 2,

701
00:54:53,630 --> 00:54:55,950
a potom treba pridať niečo na 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Jo, presne tak. Takže ak vaša hlava je ukazovateľ na samom konci,

703
00:55:02,570 --> 00:55:14,210
alebo ak je vaša veľkosť a vaša hlava je väčšia, alebo skôr, bude obtekať okolo frontu.

704
00:55:14,210 --> 00:55:17,830
>> Takže v tejto situácii, že sme dostali tu na snímke práve teraz,

705
00:55:17,830 --> 00:55:24,370
keď chcem Zaradí niečo hneď teraz,

706
00:55:24,370 --> 00:55:31,110
chceme Zaradí niečo na indexe 0.

707
00:55:31,110 --> 00:55:35,450
Takže, keď sa pozriete na miesto, kde 50 ide, a ja hovorím Zaradí 50,

708
00:55:35,450 --> 00:55:40,840
to ide tam na dne. Ide v indexe 0.

709
00:55:40,840 --> 00:55:44,160
To nahradí 'ahoj', ktorá už bola dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Copak o to postará v Dequeue už?

711
00:55:46,210 --> 00:55:50,550
Prečo to robiť niečo s hlavou v Zaradí?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, takže nie ste modifikovať hlavu, ospravedlňujem sa.

713
00:55:55,770 --> 00:56:02,310
Ale musíte použiť operátor modulo, keď ste prístupu

714
00:56:02,310 --> 00:56:04,250
prvok, ktorý chcete Zaradí keď ste prístupu

715
00:56:04,250 --> 00:56:06,960
ďalší prvok vo vašom fronte.

716
00:56:06,960 --> 00:56:10,960
[Basil] Ja som to neurobil, a ja som dostal "úspech" na tam.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, som pochopil, čo hovoríte.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Takže didn'ti - ste práve urobil na q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Jo. Práve som zmenil strany, neurobil som nič s hlavou.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Nemusíte vlastne musieť resetovať hlavu za niečo,

721
00:56:24,300 --> 00:56:31,650
ale keď sa index do reťazca poľa,

722
00:56:31,650 --> 00:56:39,500
máte skutočne ísť dopredu a vypočítať, kde ďalší prvok je,

723
00:56:39,500 --> 00:56:44,230
pretože prútia zásobníka, ďalší prvok vo vašom zásobníka bol vždy

724
00:56:44,230 --> 00:56:48,740
na indexe zodpovedajúcej veľkosti.

725
00:56:48,740 --> 00:56:55,850
Ak sa pozrieme späť na našej funkciu zásobníka tlačidlom,

726
00:56:55,850 --> 00:57:03,100
môžeme vždy plonk v našom novom prvku priamo na indexe veľkosti.

727
00:57:03,100 --> 00:57:06,710
Vzhľadom k tomu, s fronty, to nemôžeme urobiť, že

728
00:57:06,710 --> 00:57:10,340
pretože ak sme na túto situáciu,

729
00:57:10,340 --> 00:57:18,130
ak budeme vo fronte 50 naša nová reťazec by ísť priamo na struny [1]

730
00:57:18,130 --> 00:57:20,540
ktoré nechceme robiť.

731
00:57:20,540 --> 00:57:41,200
Chceme mať nový reťazec ísť na indexe 0.

732
00:57:41,200 --> 00:57:44,320
>> Má niekto - áno? [Študent] Mám otázku, ale to naozaj nie je príbuzný.

733
00:57:44,320 --> 00:57:48,160
Čo to znamená, keď niekto jednoducho zavolá niečo ako Pred ukazovateľ?

734
00:57:48,160 --> 00:57:51,260
Čo je to za meno skratka pre? Viem, že je to len meno.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred ukazovateľ? Poďme sa pozrieť,. V akej súvislosti?

736
00:57:59,110 --> 00:58:01,790
[Študent] To bolo pre vložku. Môžem vás požiadať neskôr, ak budete chcieť

737
00:58:01,790 --> 00:58:03,920
pretože to nie je naozaj súvisí, ale ja som jednoducho -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Od vložiť kód Davida z prednášky?

739
00:58:07,300 --> 00:58:10,860
Môžeme vytiahnuť, že a hovoriť o tom.

740
00:58:10,860 --> 00:58:15,550
Budeme o tom hovoriť ďalej, akonáhle sa dostaneme do prepojených zoznamov.

741
00:58:15,550 --> 00:58:21,440
>> Takže to naozaj rýchlo pozrieť na to, čo enqueue funkcie vyzerá.

742
00:58:21,440 --> 00:58:26,530
Aká bola prvá vec, že ​​ľudia sa snažil urobiť v Zaradí rade? Do tejto fronty?

743
00:58:26,530 --> 00:58:29,960
Podobne ako to, čo ste urobil pre zásobníka tlačí.

744
00:58:29,960 --> 00:58:32,080
Čo si urobil, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nezrozumiteľným]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Presne tak. Ak (q.size == kapacita) -

747
00:58:45,700 --> 00:58:54,720
Musím dať svoje zátvorky na správnom mieste - vráti false.

748
00:58:54,720 --> 00:59:01,370
Zväčšiť trochu. Dobre.

749
00:59:01,370 --> 00:59:03,800
Teraz, čo je ďalšia vec, ktorú by sme mali urobiť?

750
00:59:03,800 --> 00:59:11,370
Rovnako ako u zásobníka, a vloží na správnom mieste.

751
00:59:11,370 --> 00:59:16,010
A tak to, čo bolo tým pravým miestom pre vloženie že?

752
00:59:16,010 --> 00:59:23,170
S zásobníka bolo index veľkosti, s tým, že to nie je tak.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Mám q.head--alebo - >> q.strings? >> Jo.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPACITA]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] sme pravdepodobne chcieť, aby zátvoriek tento

756
00:59:42,740 --> 00:59:48,830
tak, že sme získali príslušnú prednosť, a tak to cleart všetkým.

757
00:59:48,830 --> 00:59:55,800
A nastaviť, aby rovnaké? Ak chcete >> str? Ak chcete >> str Great.

758
00:59:55,800 --> 01:00:00,160
A teraz, čo je to posledná vec, ktorú musíme urobiť?

759
01:00:00,160 --> 01:00:06,780
Rovnako ako sme to robili v zásobníku. Prírastok >> veľkosť? Prírastok >> veľkosti.

760
01:00:06,780 --> 01:00:13,830
Boom. A potom, pretože štartovací kódu sa práve vrátil false v predvolenom nastavení,

761
01:00:13,830 --> 01:00:27,460
chceme zmeniť na hodnotu true, ak všetko pôjde až do konca a je všetko v poriadku.

762
01:00:27,460 --> 01:00:33,050
Dobrá. To je veľa informácií o oddielu.

763
01:00:33,050 --> 01:00:39,480
Nie sme úplne na konci. Chceme hovoriť naozaj rýchlo o single prepojených zoznamov.

764
01:00:39,480 --> 01:00:44,010
Dám to tak môžeme vrátiť sa k nemu neskôr.

765
01:00:44,010 --> 01:00:50,850
Ale poďme späť k našej prezentácii za pár viac snímok.

766
01:00:50,850 --> 01:00:53,790
Takže enqueue je TODO, teraz sme to.

767
01:00:53,790 --> 01:00:57,430
>> Teraz sa poďme pozrieť na singly prepojených zoznamov.

768
01:00:57,430 --> 01:01:00,040
Hovorili sme o nich trochu viac v prednáške.

769
01:01:00,040 --> 01:01:02,540
Koľko z vás videl demo, kde sme mali ľudí

770
01:01:02,540 --> 01:01:08,220
neobratne ukázal na seba a držanie čísla? >> Bol som v tom.

771
01:01:08,220 --> 01:01:16,620
>> Čo vy na to? Bolo to, dúfajme, že demystifikovať tieto trochu?

772
01:01:16,620 --> 01:01:25,990
S zoznamu, sa ukazuje, že sa zaoberáme tohto typu, ktorý budeme nazývať uzol.

773
01:01:25,990 --> 01:01:32,520
Vzhľadom k tomu, s fronty a zásobníka sme mali structs, že by sme hovorovú front v zásobníku,

774
01:01:32,520 --> 01:01:34,860
sme mali tieto nové fronty v zásobníku typov,

775
01:01:34,860 --> 01:01:39,240
Tu je zoznam naozaj len skladá banda uzlov.

776
01:01:39,240 --> 01:01:45,920
Rovnakým spôsobom, že reťazce sú rovnako banda znakov všetkých zoradených vedľa seba.

777
01:01:45,920 --> 01:01:50,650
Spájať zoznam je len uzol a ďalšie uzol a ďalšie uzol a iný uzol.

778
01:01:50,650 --> 01:01:55,080
A skôr než rozbíjať všetky uzly dohromady a ich uloženie súvisle

779
01:01:55,080 --> 01:01:58,090
všetky priamo vedľa seba v pamäti,

780
01:01:58,090 --> 01:02:04,470
má túto ďalší ukazovateľ nám umožňuje ukladať uzly Kedykoľvek je to, v náhodnom poradí.

781
01:02:04,470 --> 01:02:10,500
A potom druh drôtu je všetky dohromady bodu od jedného k druhému.

782
01:02:10,500 --> 01:02:15,850
>> A čo bolo veľkou výhodou, že to malo cez pole?

783
01:02:15,850 --> 01:02:21,680
Cez ukladanie všetkého súvisle len prilepené vedľa seba?

784
01:02:21,680 --> 01:02:24,190
Pamätáš si? Jo? >> Dynamické prideľovanie pamäti?

785
01:02:24,190 --> 01:02:27,220
>> Dynamické prideľovanie pamäte, v akom zmysle?

786
01:02:27,220 --> 01:02:31,780
[Študent] V tomto môžete mať takže je väčšia a nemusíte sa pohybovať celý rad?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Presne tak. Takže s poľa, ak chcete, aby nový prvok do stredu,

788
01:02:40,940 --> 01:02:45,320
budete musieť presunúť všetko preto, aby priestor.

789
01:02:45,320 --> 01:02:47,880
A ako sme sa rozprávala s frontu,

790
01:02:47,880 --> 01:02:50,080
to je dôvod, prečo sme udržať, že hlava ukazovateľ,

791
01:02:50,080 --> 01:02:52,050
tak, že nie sme neustále mení veci.

792
01:02:52,050 --> 01:02:54,520
Vzhľadom k tomu, že sa dostane drahé, ak máte veľkú poľa

793
01:02:54,520 --> 01:02:57,130
a ste neustále robiť tieto náhodné vloženie.

794
01:02:57,130 --> 01:03:00,820
Vzhľadom k tomu, s prehľadom, všetko, čo musíte urobiť, je hodiť to na nový uzol,

795
01:03:00,820 --> 01:03:06,330
nastaviť ukazovatele, a máte hotovo.

796
01:03:06,330 --> 01:03:10,940
Čo naštve o to?

797
01:03:10,940 --> 01:03:16,830
Okrem skutočnosti, že je to nie je tak jednoduché pracovať ako s poľom? Jo?

798
01:03:16,830 --> 01:03:22,980
[Daniel] No, myslím, že je to oveľa ťažšie prístup špecifický prvok v pripojenom zozname?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Nemôžeš len tak skočiť do ľubovoľného prvku v polovici svojho prepojeného zoznamu.

800
01:03:30,470 --> 01:03:33,800
Ako sa vám to musieť urobiť miesto? >> Musíte krok celú vec.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Jo. Musíte prejsť jeden po druhom, jeden po druhom.

802
01:03:35,660 --> 01:03:38,480
Je to obrovská - to je bolesť.

803
01:03:38,480 --> 01:03:41,550
Čo je to druhé - je tu ďalší pád na to.

804
01:03:41,550 --> 01:03:45,340
[Basil] Nemôžete ísť dopredu a dozadu? Musíte ísť jedným smerom?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Jo. Tak ako to budeme riešiť, že niekedy?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dvakrát-prepojených zoznamov? Presne >>. K dispozícii sú dvojnásobne prepojené zoznamy.

807
01:03:53,370 --> 01:03:55,540
Tam sú tiež - sorry?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Je to rovnaké ako s použitím PRED vec, že ​​-

809
01:03:57,620 --> 01:04:01,090
Práve som si spomenula, nie je to, čo pred vec je?

810
01:04:01,090 --> 01:04:05,850
Nie je to medzi dvojnásobne a single?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Poďme sa pozrieť na to, čo presne robí.

812
01:04:10,020 --> 01:04:15,760
Tak ideme na to. Tu je zoznam kódu.

813
01:04:15,760 --> 01:04:25,620
Tu máme predptr, tu. Je to to, čo si hovoril?

814
01:04:25,620 --> 01:04:30,750
Takže to bol - on oslobodenie zoznam a snaží sa uložiť ukazovateľ na ňu.

815
01:04:30,750 --> 01:04:35,000
To nie je o dvojnásobne, jednotlivo prepojené-listy.

816
01:04:35,000 --> 01:04:40,090
Môžeme hovoriť viac o tom neskôr, pretože to sa hovorí o uvoľnení zoznam

817
01:04:40,090 --> 01:04:42,900
a chcem ukázať niektoré ďalšie veci ako prvý.

818
01:04:42,900 --> 01:04:51,480
ale je to len - je to pamätať hodnotu PTR

819
01:04:51,480 --> 01:04:54,170
[Študent] Oh, to je predchádzajúcich ukazovateľ? Jo >>.

820
01:04:54,170 --> 01:05:04,070
Takže potom môžeme zvýšiť PTR sám predtým, než sme potom zadarmo to, čo predptr je.

821
01:05:04,070 --> 01:05:09,130
Pretože nemôžeme bez ptr a potom volať ptr = ptr ďalšie, nie?

822
01:05:09,130 --> 01:05:11,260
To by bolo zlé.

823
01:05:11,260 --> 01:05:20,940
Tak uvidíme, späť na toho chlapa.

824
01:05:20,940 --> 01:05:23,900
>> Ďalšie zlá vec, o zoznamoch je, že vzhľadom na to, s radom

825
01:05:23,900 --> 01:05:26,520
budeme musieť všetky prvky samy o sebe naskladané vedľa seba,

826
01:05:26,520 --> 01:05:29,050
Tu sme tiež zaviedli tento ukazovateľ.

827
01:05:29,050 --> 01:05:34,060
Takže je tu ďalší kus pamäti, že sme museli použiť

828
01:05:34,060 --> 01:05:37,910
pre každý prvok, ktorý sme uskladnenie v našom zozname.

829
01:05:37,910 --> 01:05:40,030
Dostaneme pružnosť, ale to príde v cene.

830
01:05:40,030 --> 01:05:42,230
Dodáva sa s týmto časovým náklady,

831
01:05:42,230 --> 01:05:45,270
a je dodávaný s týmto pamäťovým náklady príliš.

832
01:05:45,270 --> 01:05:47,800
Čas v tom zmysle, že teraz musíme prejsť každý prvok v poli

833
01:05:47,800 --> 01:05:58,670
nájsť ten u indexu 10, alebo že by boli index 10 v poli.

834
01:05:58,670 --> 01:06:01,230
>> Len naozaj rýchlo, keď sme diagram z týchto zoznamov,

835
01:06:01,230 --> 01:06:05,980
zvyčajne sa držať na hlave zoznamu alebo prvý ukazovateľ zoznamu

836
01:06:05,980 --> 01:06:08,010
a vedomie, že to je pravda, ukazovateľ.

837
01:06:08,010 --> 01:06:11,100
Je to len 4 bajty. Nie je to skutočný uzol sám.

838
01:06:11,100 --> 01:06:17,120
Takže vidíte, že to nemá žiadnu hodnotu int v tom, žiadny ďalší ukazovateľ v ňom.

839
01:06:17,120 --> 01:06:20,790
Je to doslova len ukazovateľ.

840
01:06:20,790 --> 01:06:23,550
Bude to upozorniť na niečo, čo je skutočné uzol struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] Ukazovateľ nazýva uzol? >> To je - nie je. To je ukazovateľ na niečo typu uzla.

842
01:06:28,480 --> 01:06:32,540
Je ukazovateľ na uzla struct. >> Oh, dobre.

843
01:06:32,540 --> 01:06:36,870
Diagram vľavo, kódu napravo.

844
01:06:36,870 --> 01:06:42,190
Môžeme nastaviť na null, čo je dobrý spôsob, ako začať.

845
01:06:42,190 --> 01:06:49,850
Keď diagram, ty buď napísať, že za neplatné, alebo si dať čiaru cez to takto.

846
01:06:49,850 --> 01:06:53,910
>> Jedným z najjednoduchších spôsobov, ako pracovať so zoznamami,

847
01:06:53,910 --> 01:06:57,430
a žiadame vás, že aj predradiť a pripojiť vidieť rozdiely medzi týmito dvoma,

848
01:06:57,430 --> 01:07:01,320
ale predradník je rozhodne jednoduchšie.

849
01:07:01,320 --> 01:07:05,790
Keď začiatok riadku, to je miesto, kde si - keď prepend (7),

850
01:07:05,790 --> 01:07:10,050
idete a vytvoriť uzla struct

851
01:07:10,050 --> 01:07:13,870
a nastaviť prvý poukázať na to, pretože teraz, pretože sme prepended to,

852
01:07:13,870 --> 01:07:17,240
to bude na začiatku zoznamu.

853
01:07:17,240 --> 01:07:22,540
Ak sa predradeného (3), ktorá vytvára ďalší uzol, ale teraz 3 prichádza do 7..

854
01:07:22,540 --> 01:07:31,130
Takže sme v podstate tlačí veci do nášho zoznamu.

855
01:07:31,130 --> 01:07:34,720
Teraz môžete vidieť, že prepend, niekedy ľudia hovoria, že tlačiť,

856
01:07:34,720 --> 01:07:39,600
preto, že ste tlačí nový prvok do zoznamu.

857
01:07:39,600 --> 01:07:43,270
Je tiež ľahké odstrániť v čele zoznamu.

858
01:07:43,270 --> 01:07:45,650
Takže ľudia budú často volajú, že pop.

859
01:07:45,650 --> 01:07:52,200
A týmto spôsobom, je možné emulovať balík pomocou spojovaceho zoznamu.

860
01:07:52,200 --> 01:07:57,880
Jejda. Je nám ľúto, teraz sa dostávame do append. Takže tu máme prepended (7), teraz sme prepend (3).

861
01:07:57,880 --> 01:08:02,600
Ak by sme prepended niečo iné na tomto zozname, ak by sme prepended (4),

862
01:08:02,600 --> 01:08:06,540
potom budeme mať 4 a potom 3 a potom 7.

863
01:08:06,540 --> 01:08:14,220
Takže potom by sme mohli pop a odstrániť 4, odstrániť 3, odstráňte 7.

864
01:08:14,220 --> 01:08:16,500
Často viac intuitívne spôsob, ako premýšľať o tom to je s append.

865
01:08:16,500 --> 01:08:20,310
Takže som diagramu, čo by to vyzeralo s pripojiť tu.

866
01:08:20,310 --> 01:08:23,380
Tu pripojený (7) nemá vyzerať inak

867
01:08:23,380 --> 01:08:25,160
pretože tam je len jeden prvok v zozname.

868
01:08:25,160 --> 01:08:28,620
A pripojením (3) vloží to na konci.

869
01:08:28,620 --> 01:08:31,020
Možno si môžete prezrieť hneď teraz trik s append

870
01:08:31,020 --> 01:08:36,600
je, že od tej doby sme len vedieť, kde na začiatku zoznamu je,

871
01:08:36,600 --> 01:08:39,450
pripojiť do zoznamu musíte prejsť celú cestu v zozname

872
01:08:39,450 --> 01:08:46,500
sa dostať do konca, zastavte, a potom budovať svoj uzol a plonk všetko dole.

873
01:08:46,500 --> 01:08:50,590
Zapojte všetky veci hore.

874
01:08:50,590 --> 01:08:55,170
Takže s Prepend, ako sme práve prešla to naozaj rýchlo,

875
01:08:55,170 --> 01:08:58,170
keď predradiť do zoznamu, je to pomerne jednoduché.

876
01:08:58,170 --> 01:09:02,960
>> Urobíte si nový uzol, zahŕňať niektoré dynamické prideľovanie pamäte.

877
01:09:02,960 --> 01:09:09,830
Takže tu robíme uzla struct pomocou malloc.

878
01:09:09,830 --> 01:09:14,710
Takže malloc sme použili preto, že to zrušil pamäť pre nás pre neskoršie

879
01:09:14,710 --> 01:09:20,350
pretože nechceme, aby to - chceme, aby tento pamäti pretrvávať po dlhú dobu.

880
01:09:20,350 --> 01:09:25,350
A my sme si ukazovateľ na miesto v pamäti, že sme práve pridelené.

881
01:09:25,350 --> 01:09:29,260
Používame veľkosti uzla, nemáme sčítať poľa.

882
01:09:29,260 --> 01:09:31,899
Nechceme ručne generovať počet bajtov,

883
01:09:31,899 --> 01:09:39,750
namiesto toho sme použiť sizeof, takže vieme, že získanie zodpovedajúci počet bajtov.

884
01:09:39,750 --> 01:09:43,660
Snažíme sa o to, aby testovanie, že naše malloc volanie bolo úspešné.

885
01:09:43,660 --> 01:09:47,939
To je niečo, čo chcete robiť v všeobecne.

886
01:09:47,939 --> 01:09:52,590
Na moderných strojoch, vyčerpania pamäte nie je niečo, čo je ľahké

887
01:09:52,590 --> 01:09:56,610
ak ste pridelenie veľa vecí a robiť obrovský zoznam,

888
01:09:56,610 --> 01:10:02,220
ale ak staviate veci pre, povedzme, ako iPhone alebo Android,

889
01:10:02,220 --> 01:10:05,230
nemáte majú obmedzené prostriedky pamäti, najmä ak robíte niečo intenzívne.

890
01:10:05,230 --> 01:10:08,300
Takže je to dobré sa dostať do praxe.

891
01:10:08,300 --> 01:10:10,510
>> Všimnite si, že som použil niekoľko rôznych funkcií tu

892
01:10:10,510 --> 01:10:12,880
, Keď ste videli, že sú trochu nové.

893
01:10:12,880 --> 01:10:15,870
Takže fprintf je rovnako ako printf

894
01:10:15,870 --> 01:10:21,320
okrem svojho prvého argumentu je potok, ktorý chcete vytlačiť.

895
01:10:21,320 --> 01:10:23,900
V tomto prípade, že chceme vytlačiť na štandardný chybový reťazec

896
01:10:23,900 --> 01:10:29,410
, Ktorý je odlišný od štandardného outstream.

897
01:10:29,410 --> 01:10:31,620
Implicitne sa objaví na rovnakom mieste.

898
01:10:31,620 --> 01:10:34,600
To tiež vytlačí na terminál, ale môžete -

899
01:10:34,600 --> 01:10:38,790
použitie týchto príkazov ste sa dozvedeli o tom, o presmerovanie techniky

900
01:10:38,790 --> 01:10:42,290
ste sa dozvedeli o vo videu Tommyho pre problémové sadu 4, môžete nasmerovať ju

901
01:10:42,290 --> 01:10:47,900
do rôznych oblastí, potom ukončite, tu, ukončí svoj program.

902
01:10:47,900 --> 01:10:50,440
Je to v podstate ako návrat z hlavnej,

903
01:10:50,440 --> 01:10:53,600
okrem používame výjazd, pretože tu návrat nebude robiť nič.

904
01:10:53,600 --> 01:10:57,140
Nie sme v hlavnej, tak vracia neukončí program, ako chceme.

905
01:10:57,140 --> 01:11:03,020
Tak sme sa použiť funkciu ukončenia a dať mu chybový kód.

906
01:11:03,020 --> 01:11:11,890
Potom tu máme nastavený nový uzol hodnotového poľa, jeho i pole sa rovná aj, a potom sme zapojte ho.

907
01:11:11,890 --> 01:11:15,530
Vydali sme nový uzol je ďalší ukazovateľ aby ukazoval na prvý,

908
01:11:15,530 --> 01:11:20,460
a potom prvý budú teraz na tento nový uzol.

909
01:11:20,460 --> 01:11:25,120
Tieto prvé riadky kódu, sme vlastne stavať nový uzol.

910
01:11:25,120 --> 01:11:27,280
Nie posledné dva riadky tejto funkcie, ale tie prvé.

911
01:11:27,280 --> 01:11:30,290
Môžete si skutočne vytiahnuť do funkcie, do pomocnú funkciu.

912
01:11:30,290 --> 01:11:32,560
To je často to, čo robím je, že som ju vytiahnuť do funkcie,

913
01:11:32,560 --> 01:11:36,040
Hovorím to niečo ako uzol zostavenie,

914
01:11:36,040 --> 01:11:40,410
a že udržiava prepend funkcie celkom malá, je to len 3 riadky potom.

915
01:11:40,410 --> 01:11:48,710
Aj volať na mojej funkcie uzla zostavenie, a potom som drôt všetko hore.

916
01:11:48,710 --> 01:11:51,970
>> Posledná vec, ja vám chcem ukázať,

917
01:11:51,970 --> 01:11:54,030
a nechám ťa urobiť append a to všetko na vlastnú päsť,

918
01:11:54,030 --> 01:11:57,500
je, ako určiť iteráciou cez zoznam.

919
01:11:57,500 --> 01:12:00,780
Existuje veľa rôznych spôsobov, ako prechádzať cez zoznam.

920
01:12:00,780 --> 01:12:03,140
V tomto prípade sa budeme nájsť dĺžku zoznamu.

921
01:12:03,140 --> 01:12:06,570
Takže začneme s dĺžkou = 0.

922
01:12:06,570 --> 01:12:11,580
To je veľmi podobné písanie strlen pre reťazec.

923
01:12:11,580 --> 01:12:17,780
To je to, čo chcem ukázať, to pre slučku tu.

924
01:12:17,780 --> 01:12:23,530
Vyzerá to trochu funky, to nie je obvyklé int i = 0, i <čokoľvek, i + +.

925
01:12:23,530 --> 01:12:34,920
Namiesto toho je to inicializácia našu premennú n byť začiatok zoznamu.

926
01:12:34,920 --> 01:12:40,620
A potom, keď naše Iterator premenná nie je null, budeme pokračovať.

927
01:12:40,620 --> 01:12:46,340
To je preto, že podľa konvencie, bude koniec nášho zoznamu je null.

928
01:12:46,340 --> 01:12:48,770
A potom prírastok, skôr než robiť + +,

929
01:12:48,770 --> 01:12:57,010
spájať zoznam ekvivalent + + je n = n-> ďalšie.

930
01:12:57,010 --> 01:13:00,410
>> Dám vám vyplniť medzery tu, pretože sme mimo čas.

931
01:13:00,410 --> 01:13:09,300
Ale majte na pamäti, až budete pracovať na svojich spellr psets.

932
01:13:09,300 --> 01:13:11,650
Prepojené zoznamy, ak ste vykonávanie hash tabuľky,

933
01:13:11,650 --> 01:13:14,010
určite príde veľmi vhod.

934
01:13:14,010 --> 01:13:21,780
A má tento idiom pre sláčiky nad vecou bude život oveľa jednoduchší, snáď.

935
01:13:21,780 --> 01:13:25,910
Akékoľvek otázky, rýchlo?

936
01:13:25,910 --> 01:13:28,920
[Sam] Budete posielať vyplnený SLL a sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Jo. Budem posielať vyplnené diapozitívov a vyplnený SLL stoh a queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]