1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Část 6: Méně 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á. Vítejte v sekci 6.

5
00:00:11,840 --> 00:00:14,690
Tento týden, budeme mluvit o datových struktur v sekci,

6
00:00:14,690 --> 00:00:19,780
především proto, že tento týden je problém nastavit na spellr

7
00:00:19,780 --> 00:00:24,410
se celá parta jinou datovou strukturu průzkumu.

8
00:00:24,410 --> 00:00:26,520
Existuje spoustu různých způsobů, jak můžete jít s tímto problémem set,

9
00:00:26,520 --> 00:00:31,570
a čím více datových struktur víte o, tím více cool věcí, které můžete udělat.

10
00:00:31,570 --> 00:00:34,990
>> Tak pojďme začít. Nejprve budeme mluvit o komíny,

11
00:00:34,990 --> 00:00:37,530
zásobníku a fronty datové struktury, které budeme mluvit o.

12
00:00:37,530 --> 00:00:40,560
Komíny a fronty jsou opravdu užitečné, když začneme mluvit o grafy,

13
00:00:40,560 --> 00:00:44,390
které nebudeme dělat tolik teď.

14
00:00:44,390 --> 00:00:52,820
Ale jsou opravdu dobré pochopit jednu z velkých základních datových struktur CS.

15
00:00:52,820 --> 00:00:54,880
Popis ve specifikaci problému set,

16
00:00:54,880 --> 00:00:59,260
pokud jste vytáhněte ji nahoru, hovoří o tom, komíny jako blízký

17
00:00:59,260 --> 00:01:05,239
hromada jídelních podnosů, že máte v jídelně v jídelnách

18
00:01:05,239 --> 00:01:09,680
kde, kdy jídelna zaměstnanců přijde a dá si jídelní podnosy z poté, co jsem vyčistit je,

19
00:01:09,680 --> 00:01:12,000
oni vyrovnají jim jeden na druhého.

20
00:01:12,000 --> 00:01:15,050
A pak, když děti přijdou do dostat jídlo,

21
00:01:15,050 --> 00:01:19,490
vytahují zásobníky mimo nejprve vrchní, pak jeden pod ním, pak jeden dole, že.

22
00:01:19,490 --> 00:01:25,190
Takže ve skutečnosti, první zásobník, který jídelní personál položil je poslední, který se vzlétlo.

23
00:01:25,190 --> 00:01:32,330
Ten poslední, že jídelna zaměstnanci kladen na je první, který se vzlétlo k večeři.

24
00:01:32,330 --> 00:01:38,100
V problému setu je spec, které si můžete stáhnout, pokud jste tak již neučinili,

25
00:01:38,100 --> 00:01:46,730
Hovoříme-li o modelování zásobníku dat STRUKTURA pomocí tohoto druhu struct.

26
00:01:46,730 --> 00:01:51,070
>> Takže to, co jsme se sem dostali, je to podobné tomu, co bylo uvedeno v přednášce,

27
00:01:51,070 --> 00:01:58,120
výjimkou v přednášce jsme se prezentovali to s ints jako protiklad k char * s.

28
00:01:58,120 --> 00:02:06,250
To bude zásobník, který ukládá, co?

29
00:02:06,250 --> 00:02:09,009
Daniel? Co jsme uchovávání v tomto zásobníku?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Jsme ukládání řetězce v tomto zásobníku, přesně.

31
00:02:15,260 --> 00:02:20,950
Vše je třeba mít k vytvoření zásobníku je pole

32
00:02:20,950 --> 00:02:23,920
určité kapacity, která je v tomto případě,

33
00:02:23,920 --> 00:02:28,020
kapacita bude ve všech velkých písmenech, protože je to konstanta.

34
00:02:28,020 --> 00:02:36,340
A pak navíc k poli, vše musíme sledovat je aktuální velikost pole.

35
00:02:36,340 --> 00:02:38,980
Jedna věc k poznámce, že je to docela fajn

36
00:02:38,980 --> 00:02:47,060
je to, že jsme vytvoření skládaného datovou strukturu na vrcholu jiné struktury dat, pole.

37
00:02:47,060 --> 00:02:50,110
Existují různé způsoby, jak implementovat stohy.

38
00:02:50,110 --> 00:02:54,250
Budeme to dělat ještě dost, ale doufejme, že poté, co dělal na odkazovaných seznam problémů,

39
00:02:54,250 --> 00:03:00,520
uvidíte, jak si můžete snadno implementovat balík na vrcholu propojeného seznamu stejně.

40
00:03:00,520 --> 00:03:02,640
Ale teď, budeme držet pole.

41
00:03:02,640 --> 00:03:06,350
Takže znovu, vše, co potřebujete, je pole a my stačí sledovat velikost pole.

42
00:03:06,350 --> 00:03:09,850
[Sam] Omlouvám se, proč je to, že jste říkal, že stack je na vrchol řetězců?

43
00:03:09,850 --> 00:03:13,440
Pro mě se zdá, že řetězce jsou v zásobníku.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Jo. Jsme vytváření, bereme naše pole datové struktury -

45
00:03:16,790 --> 00:03:22,130
To je velká otázka. Takže otázka je, proč, pro lidi, kteří sledují tento on-line,

46
00:03:22,130 --> 00:03:24,140
proč říkáme, že zásobník je na vrcholu řetězce,

47
00:03:24,140 --> 00:03:27,990
protože tady to vypadá, jako jsou řetězce uvnitř zásobníku?

48
00:03:27,990 --> 00:03:31,050
Což je naprosto případ.

49
00:03:31,050 --> 00:03:34,660
To, co jsem měl na mysli, že máme maticový datovou strukturu.

50
00:03:34,660 --> 00:03:39,290
Máme celou řadu char * s, toto pole řetězců,

51
00:03:39,290 --> 00:03:45,300
a budeme přidávat k tomu, aby k vytvoření skládaný datovou strukturu.

52
00:03:45,300 --> 00:03:48,620
>> Takže stack je poněkud složitější než pole.

53
00:03:48,620 --> 00:03:51,890
Můžeme použít pole postavit stack.

54
00:03:51,890 --> 00:03:55,810
Tak to je, kde můžeme říci, že zásobník je postaven na vrcholu pole.

55
00:03:55,810 --> 00:04:02,510
Stejně tak, jak jsem řekl dříve, můžeme vybudovat zásobník na vrcholu propojeného seznamu.

56
00:04:02,510 --> 00:04:04,960
Místo toho, aby pomocí pole držet naše prvky,

57
00:04:04,960 --> 00:04:10,070
bychom mohli použít propojeného seznamu držet naše prvky a vytvořit stoh kolem toho.

58
00:04:10,070 --> 00:04:12,420
Pojďme projít pár příkladů, při pohledu na nějaký kód,

59
00:04:12,420 --> 00:04:14,960
vidět, co se vlastně děje.

60
00:04:14,960 --> 00:04:23,400
Na levé straně, jsem hodil dolů, co to stack struct bude vypadat v paměti

61
00:04:23,400 --> 00:04:28,330
pokud kapacita byla # definován být čtyři.

62
00:04:28,330 --> 00:04:33,490
Máme naše čtyři prvek char * pole.

63
00:04:33,490 --> 00:04:38,110
Máme řetězce [0], struny [1], struny [2], struny [3],

64
00:04:38,110 --> 00:04:43,800
a pak, že poslední prostor pro naši velikost celé číslo.

65
00:04:43,800 --> 00:04:46,270
Má to smysl? Dobře.

66
00:04:46,270 --> 00:04:48,790
To je to, co se stane, když to, co mám dělat, na pravé straně,

67
00:04:48,790 --> 00:04:55,790
který bude můj kód, je jen vyhlásit struct, skládaný struct volal s.

68
00:04:55,790 --> 00:05:01,270
To je to, co dostaneme. Stanoví tento stopu v paměti.

69
00:05:01,270 --> 00:05:05,590
První otázka je, co je obsahem tohoto zásobníku struct?

70
00:05:05,590 --> 00:05:09,250
Právě teď nejsme nic, ale nejsou úplně nic.

71
00:05:09,250 --> 00:05:13,300
Jsou tento druh odpadu. Nemáme tušení, co je v nich.

72
00:05:13,300 --> 00:05:17,000
Když jsme prohlásit zásobník s, jsme jen házení, že se na vrcholu paměti.

73
00:05:17,000 --> 00:05:19,840
Je to něco jako vyhlášení int i, a ne jeho inicializaci.

74
00:05:19,840 --> 00:05:21,730
Ty nevíš, co je to tam. Můžete si přečíst, co je tam,

75
00:05:21,730 --> 00:05:27,690
ale to nemusí být super užitečné.

76
00:05:27,690 --> 00:05:32,680
Jedna věc, kterou chcete, aby se vždy pamatujte na to, je inicializovat, co je třeba inicializovat.

77
00:05:32,680 --> 00:05:35,820
V tomto případě, budeme inicializovat velikost nula,

78
00:05:35,820 --> 00:05:39,960
protože je to dopadne jako pro nás velmi důležité.

79
00:05:39,960 --> 00:05:43,450
Mohli bychom pokračovat a inicializaci všech ukazatelů, všechny char * s,

80
00:05:43,450 --> 00:05:49,670
se, že některé pochopitelné hodnota, pravděpodobně null.

81
00:05:49,670 --> 00:05:58,270
Ale není to úplně nutné, uděláme to.

82
00:05:58,270 --> 00:06:04,200
>> Nyní, dva hlavní operace komíny jsou?

83
00:06:04,200 --> 00:06:07,610
Kdokoliv pamatuju z přednášky, co dělat s komíny? Ano?

84
00:06:07,610 --> 00:06:09,700
[Stella] Stiskem a praskání? Přesně >>.

85
00:06:09,700 --> 00:06:13,810
Tlačení a praskání jsou dvě hlavní operace na komíny.

86
00:06:13,810 --> 00:06:17,060
A co tlačit dělat? >> Klade něco na vrcholu

87
00:06:17,060 --> 00:06:19,300
ze zásobníku, a pak praskla vezme ho.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Přesně tak. Takže tlačí tlačí něco na vrcholu zásobníku.

89
00:06:23,150 --> 00:06:27,700
Je to jako v jídelně zaměstnanců uvedení jídelní podnos na pult.

90
00:06:27,700 --> 00:06:33,630
A objevovat bere jídelní podnos pryč zásobníku.

91
00:06:33,630 --> 00:06:36,460
Pojďme projít pár příkladů toho, co se stane

92
00:06:36,460 --> 00:06:39,720
když jsme se tlačit věci do zásobníku.

93
00:06:39,720 --> 00:06:45,110
Pokud bychom měli tlačit na řetězec "ahoj" na naše zásobníku,

94
00:06:45,110 --> 00:06:49,760
To je to, co naše schéma by vypadat jako teď.

95
00:06:49,760 --> 00:06:53,410
Podívejte se, co se stane?

96
00:06:53,410 --> 00:06:56,530
Usilovali jsme do prvního prvku naší řetězce pole

97
00:06:56,530 --> 00:07:01,420
a my zvýšil naše velikost počet na 1.

98
00:07:01,420 --> 00:07:05,340
Takže pokud se podíváme na rozdíl mezi dvěma skluzavkami, zde byla 0, tady je před stisknutím.

99
00:07:05,340 --> 00:07:08,690
Zde je po stisku.

100
00:07:08,690 --> 00:07:13,460
Před push, po stisknutí.

101
00:07:13,460 --> 00:07:16,860
A teď máme jeden prvek v našem zásobníku.

102
00:07:16,860 --> 00:07:20,970
Je to řetězec "ahoj", a to je vše.

103
00:07:20,970 --> 00:07:24,440
Všechno ostatní v poli, v našem řetězcích poli, je stále odpadky.

104
00:07:24,440 --> 00:07:27,070
Jsme není inicializována to.

105
00:07:27,070 --> 00:07:29,410
Řekněme, že jsme se tlačit další řetězec do našeho zásobníku.

106
00:07:29,410 --> 00:07:32,210
Budeme tlačit "svět" v této době.

107
00:07:32,210 --> 00:07:35,160
Takže vidíte, "world" tady je na vrcholu "hello",

108
00:07:35,160 --> 00:07:40,040
a velikosti znaků sahá až do 2.

109
00:07:40,040 --> 00:07:44,520
Nyní můžeme tlačit "CS50", a že to jít na vrcholu znovu.

110
00:07:44,520 --> 00:07:51,110
Když se vrátíme, můžete vidět, jak se tlačí věci na vrcholu zásobníku.

111
00:07:51,110 --> 00:07:53,320
A teď se dostáváme k popu.

112
00:07:53,320 --> 00:07:58,910
Když jsme vyskočila něco z fronty, co se stalo?

113
00:07:58,910 --> 00:08:01,540
Každý Vidíte ten rozdíl? Je to docela jemné.

114
00:08:01,540 --> 00:08:05,810
[Student] velikost. >> Jo, její velikost.

115
00:08:05,810 --> 00:08:09,040
>> Co jiného by jste očekávali změnit?

116
00:08:09,040 --> 00:08:14,280
[Student] Řetězce, taky. Právo >>. Řetězce taky.

117
00:08:14,280 --> 00:08:17,110
Ukazuje se, že když děláte to takhle,

118
00:08:17,110 --> 00:08:21,960
protože nejsme kopírování prvků do našeho zásobníku,

119
00:08:21,960 --> 00:08:24,670
jsme vlastně nemusíme dělat nic, my můžeme jen použít velikost

120
00:08:24,670 --> 00:08:28,630
sledovat počtu věcí v našem poli

121
00:08:28,630 --> 00:08:33,780
takže když jsme pop, znovu jsme právě decrement svoji velikost až 1.

122
00:08:33,780 --> 00:08:39,440
Není potřeba, aby skutečně jít a přepsat cokoliv.

123
00:08:39,440 --> 00:08:41,710
Druh funky.

124
00:08:41,710 --> 00:08:46,520
Ukazuje se, že jsme obvykle jen nechat věci sám, protože je to méně práce pro nás udělat.

125
00:08:46,520 --> 00:08:50,060
Pokud nemáme jít zpět a přepsat něco, tak proč to?

126
00:08:50,060 --> 00:08:54,150
Takže když jsme se pop dvakrát pryč zásobníku, vše, co dělá, je decrement do velikosti několikrát.

127
00:08:54,150 --> 00:08:59,120
A opět, je to jen proto, že nejsme kopírování věci do našeho stacku.

128
00:08:59,120 --> 00:09:01,320
Ano? Mluvte.

129
00:09:01,320 --> 00:09:04,460
[Student, nesrozumitelné] >> A co se stane pak, když budete tlačit zase něco?

130
00:09:04,460 --> 00:09:08,570
Když stisknete zase něco, kde to jde?

131
00:09:08,570 --> 00:09:12,390
Pokud to půjde, Basile? Do >> řetězců [1]? Právo >>.

132
00:09:12,390 --> 00:09:14,530
Proč to jít do řetězce [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Vzhledem k tomu, že zapomněl, že tam bylo něco v řetězci [1] a [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Přesně tak. Naše zásobník, v podstatě, "zapomněl", že to držel na cokoliv

135
00:09:24,040 --> 00:09:29,480
v řetězci [1] nebo řetězce [2], takže když jsme se tlačit "Woot",

136
00:09:29,480 --> 00:09:36,670
to jen vezme, že do elementu v řetězci [1].

137
00:09:36,670 --> 00:09:41,590
Jsou nějaké otázky, na tom, jak to funguje, na základní úrovni?

138
00:09:41,590 --> 00:09:45,160
[Sam] Tak to není dynamický žádným způsobem, pokud jde o výši

139
00:09:45,160 --> 00:09:47,620
nebo, pokud jde o velikosti zásobníku?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Přesně tak. To je - šlo o to, že to není dynamicky growning stack.

141
00:09:56,750 --> 00:10:02,850
To je zásobník, který může obsahovat, nanejvýš čtyři * char s, nejvýše čtyři věci.

142
00:10:02,850 --> 00:10:07,580
Pokud bychom měli zkusit a tlačit pětiny věc, co si myslíte, že by se mělo stát?

143
00:10:07,580 --> 00:10:11,870
[Studenti, nesrozumitelné]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Přesně tak. Existuje celá řada věcí, které by se mohlo stát.

145
00:10:14,600 --> 00:10:19,330
To by mohlo seg poruchy, závislosti na tom, co jsme byli -

146
00:10:19,330 --> 00:10:22,530
jak přesně jsme realizaci back-end.

147
00:10:22,530 --> 00:10:31,740
Mohlo by to přepsat. To by mohlo mít, že buffer overflow, že jsme mluvili o ve třídě.

148
00:10:31,740 --> 00:10:35,240
Jaký by měl být nejzřejmější věc, která by mohla být přepsána

149
00:10:35,240 --> 00:10:42,370
pokud jsme se snažili tlačit další věc na našem zásobníku?

150
00:10:42,370 --> 00:10:44,550
Takže vy jste zmínil přetečení vyrovnávací paměti.

151
00:10:44,550 --> 00:10:47,870
Co by mohlo být to, co by si psal přes nebo dupl na

152
00:10:47,870 --> 00:10:52,320
pokud bychom přetekl náhodou, že se snaží tlačit další věc?

153
00:10:52,320 --> 00:10:54,730
[Daniel, nesrozumitelné] >> Možná.

154
00:10:54,730 --> 00:10:58,440
Ale zpočátku, může, co se stalo? Co když jsme se snažili tlačit čtvrtiny věc?

155
00:10:58,440 --> 00:11:06,220
To by mohlo přepsat velikost, alespoň s tímto paměťovým schématu, které jsme dostali.

156
00:11:06,220 --> 00:11:10,880
>> Ve specifikaci problému set, což je to, co budeme se provádí dnes,

157
00:11:10,880 --> 00:11:16,030
co chceš udělat, je jen vrátí false.

158
00:11:16,030 --> 00:11:20,030
Naše Push metoda bude vracet booleovskou hodnotu,

159
00:11:20,030 --> 00:11:22,920
a že boolean hodnota bude true, pokud tlak uspěje

160
00:11:22,920 --> 00:11:29,730
false, pokud nemůžeme prosazovat nic víc, protože zásobník je plný.

161
00:11:29,730 --> 00:11:33,620
Projděme trochou uvedeného kodexu teď.

162
00:11:33,620 --> 00:11:36,400
Tady je náš stisk funkce.

163
00:11:36,400 --> 00:11:40,380
Naše tlak funkce pro soustavu bude trvat v řetězci, aby na zásobníku.

164
00:11:40,380 --> 00:11:45,820
Bude to vrátí hodnotu true, pokud řetězec byl úspěšně tlačil

165
00:11:45,820 --> 00:11:51,820
na stack a false jinak.

166
00:11:51,820 --> 00:11:59,740
Nějaké návrhy na to, co by mohlo být dobrý první věc tady?

167
00:11:59,740 --> 00:12:20,630
[Sam] Pokud velikost odpovídá kapacitu pak vrátí false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Dobrá práce.

169
00:12:23,320 --> 00:12:26,310
Pokud je velikost kapacity, budeme se vrátit false.

170
00:12:26,310 --> 00:12:29,270
Nemůžeme dát něco více v našem zásobníku.

171
00:12:29,270 --> 00:12:36,900
V opačném případě budeme chtít dát něco na vrcholu zásobníku.

172
00:12:36,900 --> 00:12:41,670
Co je to "vrchol zásobníku," původně?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Velikost 0? Velikost >> 0.

174
00:12:43,650 --> 00:12:49,990
Co je vrchol zásobníku po tu jedna věc, kterou v zásobníku? Missy, víš?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Velikost >> je, přesně tak. Ty držet přidání do velikosti,

176
00:12:52,720 --> 00:13:01,690
a pokaždé, když jste uvedení v novém prvku v indexu velikost v poli.

177
00:13:01,690 --> 00:13:05,470
Můžeme to udělat s tímto druhem jedné vložky, pokud to dává smysl.

178
00:13:05,470 --> 00:13:11,910
Takže máme naše struny nabídku, budeme přistupovat na velikosti indexu,

179
00:13:11,910 --> 00:13:14,780
a my jsme jen tak uložit naše char * tam.

180
00:13:14,780 --> 00:13:19,340
Všimněte si, jak tam je žádný řetězec kopírování tu děje,

181
00:13:19,340 --> 00:13:29,680
no dynamické přidělování paměti?

182
00:13:29,680 --> 00:13:34,440
A pak Missy přinesl to, co teď musíme udělat,

183
00:13:34,440 --> 00:13:40,570
protože jsme uložili řetězec na příslušném místě v poli,

184
00:13:40,570 --> 00:13:49,230
a ona řekla, že jsme museli zvýšit velikost jednoho tak, že jsme připraveni na další Push.

185
00:13:49,230 --> 00:13:53,950
Takže, co můžeme udělat, aby se s.size + +.

186
00:13:53,950 --> 00:13:59,330
V tomto bodě, jsme tlačeni do našeho pole. Co je poslední věc, kterou musíme udělat?

187
00:13:59,330 --> 00:14:10,110
[Student] Vrací true. >> Vrací true.

188
00:14:10,110 --> 00:14:14,690
Takže je to docela jednoduché, docela jednoduchý kód. Ne moc.

189
00:14:14,690 --> 00:14:17,070
Jakmile omotal hlavu kolem, jak stack funguje,

190
00:14:17,070 --> 00:14:21,910
to je docela snadno implementovat.

191
00:14:21,910 --> 00:14:26,390
>> Nyní, další část z toho se objevovat řetězec pryč zásobníku.

192
00:14:26,390 --> 00:14:29,410
Já ti dám si kluci nějaký čas pracovat na tomto trochu.

193
00:14:29,410 --> 00:14:34,320
Je to skoro podstatě opak toho, co jsme udělali tady v Push.

194
00:14:34,320 --> 00:14:38,510
To, co jsem udělal, je vlastně - oops.

195
00:14:38,510 --> 00:14:48,160
Jsem nastartoval až spotřebiče tady, a ve spotřebiči,

196
00:14:48,160 --> 00:14:53,600
Já jsem vytáhl problém nastavit 5 specifikaci.

197
00:14:53,600 --> 00:15:02,560
Pokud bychom přiblížíte tady, můžeme vidět jsem na cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Už jste stáhli tento kód, který je zde umístěn, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Dobrá. Pokud jste tak dosud neučinily, aby to, že právě teď, opravdu rychle.

200
00:15:15,030 --> 00:15:22,130
Udělám to v mém terminálovém okně.

201
00:15:22,130 --> 00:15:25,090
Vlastně jsem to udělal tady. Jo.

202
00:15:25,090 --> 00:15:34,730
Ano, Sam? >> Mám otázku o tom, proč jste říkal, že s.string 's držáky na velikosti = str?

203
00:15:34,730 --> 00:15:42,910
Co je to str? Je vymezen někde před, nebo - oh, v char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ano, přesně tak. To byl argument. >> Oh, dobře. Promiňte.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Jsme určující řetězec, aby se zasadila palců

206
00:15:49,470 --> 00:15:55,220
Další otázka, která by mohla přijít, že jsme se opravdu mluvit o zde byla

207
00:15:55,220 --> 00:15:58,810
jsme se za samozřejmé, že jsme měli tuto proměnnou s názvem s

208
00:15:58,810 --> 00:16:02,710
, který byl v rozsahu a přístupné pro nás.

209
00:16:02,710 --> 00:16:06,960
Vzali jsme za samozřejmé, že s je tento stack struct.

210
00:16:06,960 --> 00:16:08,930
Takže ohlédnutí za touto Push kód,

211
00:16:08,930 --> 00:16:13,450
můžete vidět, že děláme věci s tímto řetězcem, který dostal prošel v

212
00:16:13,450 --> 00:16:19,210
ale pak najednou, že jsme přístup k s.size, stejně jako tam, kde se s pocházejí?

213
00:16:19,210 --> 00:16:23,020
V kódu, který se budeme dívat na v sekci archivu

214
00:16:23,020 --> 00:16:27,100
a pak věci, které budete dělat ve svém problému zapadne,

215
00:16:27,100 --> 00:16:32,440
jsme udělali náš stack struct globální proměnné

216
00:16:32,440 --> 00:16:36,380
takže můžeme mít k němu přístup na všech našich různých funkcích

217
00:16:36,380 --> 00:16:40,630
aniž byste museli ručně projít kolem a předat jej odkazem,

218
00:16:40,630 --> 00:16:44,870
dělat všechny tyhle věci k ní.

219
00:16:44,870 --> 00:16:52,280
Jsme prostě podvádí trochu, chcete-li, aby se věci hezčí.

220
00:16:52,280 --> 00:16:57,430
A to je něco, co tady děláme, protože je to pro zábavu, je to jednodušší.

221
00:16:57,430 --> 00:17:02,800
Často, uvidíte lidé to v případě, že má jednu velkou datovou strukturu

222
00:17:02,800 --> 00:17:07,750
, který je provozován na v rámci jejich programu.

223
00:17:07,750 --> 00:17:09,560
>> Vraťme se k zařízení.

224
00:17:09,560 --> 00:17:15,240
Bylo všichni úspěšně získat section6.zip?

225
00:17:15,240 --> 00:17:20,440
Všichni rozbalte jej pomocí Rozbalte section6.zip?

226
00:17:20,440 --> 00:17:27,200
Pojedete-li do sekce 6 adresáře -

227
00:17:27,200 --> 00:17:29,220
aah, všude možně -

228
00:17:29,220 --> 00:17:32,840
a seznam toho, co je tady, vidíte, že máte tři různé. C soubory.

229
00:17:32,840 --> 00:17:38,350
Máte frontu, SLL, což je singly-linked list, a zásobník.

230
00:17:38,350 --> 00:17:44,600
Pokud otevřete stack.c,

231
00:17:44,600 --> 00:17:47,330
můžete vidět, že máme tuto struct definované pro nás,

232
00:17:47,330 --> 00:17:51,330
Přesný struct, že jsme právě mluvili ze sklíčka.

233
00:17:51,330 --> 00:17:56,340
Máme naše globální proměnné pro zásobník,

234
00:17:56,340 --> 00:18:00,110
jsme dostali náš Push funkci,

235
00:18:00,110 --> 00:18:04,230
a pak jsme dostali náš pop funkci.

236
00:18:04,230 --> 00:18:08,320
Dám kód pro zatlačte zpátky na snímku zde,

237
00:18:08,320 --> 00:18:10,660
ale to, co bych chtěl vy udělat, je, jak nejlépe své schopnosti,

238
00:18:10,660 --> 00:18:13,790
jít a provádět pop funkci.

239
00:18:13,790 --> 00:18:18,480
Jakmile jste implementovali, můžete kompilovat to s make stoh,

240
00:18:18,480 --> 00:18:22,540
a spusťte výsledné zásobníku spustitelný,

241
00:18:22,540 --> 00:18:28,390
a že poběží celý tohoto zkušebního předpisu tady to je v main.

242
00:18:28,390 --> 00:18:31,060
A hlavní stará skutečně dělat push a pop hovory

243
00:18:31,060 --> 00:18:33,220
a ujistěte se, že všechno jde přes všechny práva.

244
00:18:33,220 --> 00:18:36,820
To také inicializuje velikost zásobníku tady

245
00:18:36,820 --> 00:18:39,780
takže nemusíte mít strach o inicializaci, že.

246
00:18:39,780 --> 00:18:42,310
Můžete předpokládat, že to bylo správně inicializován

247
00:18:42,310 --> 00:18:48,000
v okamžiku, kdy jste k němu měly přístup do pop funkci.

248
00:18:48,000 --> 00:18:53,530
Dává to smysl?

249
00:18:53,530 --> 00:19:00,100
Tak jdeme na to. Tam je tlak kód.

250
00:19:00,100 --> 00:19:13,210
Dám ti kluci 5 nebo 10 minut.

251
00:19:13,210 --> 00:19:15,690
A pokud máte nějaké dotazy v mezidobí, když jste kódování,

252
00:19:15,690 --> 00:19:17,710
zeptejte se nahlas.

253
00:19:17,710 --> 00:19:23,080
Takže pokud se dostanete do problematickým bodem, zeptejte se.

254
00:19:23,080 --> 00:19:26,030
Dejte mi vědět, ať všichni ostatní vědět.

255
00:19:26,030 --> 00:19:28,160
Práce se svým sousedem taky.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Zrovna provádění pop teď? Jen >> pop.

257
00:19:30,360 --> 00:19:34,200
I když můžete zkopírovat provádění Push, pokud chcete

258
00:19:34,200 --> 00:19:37,780
tak, že testování bude fungovat.

259
00:19:37,780 --> 00:19:41,940
Vzhledem k tomu, že je obtížné testovat věci dostat do -

260
00:19:41,940 --> 00:19:49,030
nebo, je obtížné testovat objevovat věci z hromady, pokud tam není něco v zásobníku začít.

261
00:19:49,030 --> 00:19:55,250
>> Co je pop měl být vracející? Prvek z horní části zásobníku.

262
00:19:55,250 --> 00:20:01,260
Má to dostat prvek pryč horní části zásobníku

263
00:20:01,260 --> 00:20:05,780
a pak dekrementace velikost zásobníku,

264
00:20:05,780 --> 00:20:07,810
a teď jste ztratili prvek na vrcholu.

265
00:20:07,810 --> 00:20:11,420
A pak se vrátíte prvek na vrcholu.

266
00:20:11,420 --> 00:20:20,080
[Student, nesrozumitelným]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Takže co se stane, pokud to uděláte? [Student, nesrozumitelným]

268
00:20:28,810 --> 00:20:34,000
Co se skončí událost je budete pravděpodobně přístup buď

269
00:20:34,000 --> 00:20:37,350
prvek, který nebyl inicializován ještě, takže výpočet

270
00:20:37,350 --> 00:20:39,990
, kde se poslední prvek je vypnutý.

271
00:20:39,990 --> 00:20:46,260
Takže tady, pokud si všimnete, v Push, jsme přístup řetězce na s.size prvku

272
00:20:46,260 --> 00:20:48,560
protože je to nový index.

273
00:20:48,560 --> 00:20:51,460
Je to nový vrchol zásobníku.

274
00:20:51,460 --> 00:21:01,100
Vzhledem k tomu, pop, s.size bude příští prostor,

275
00:21:01,100 --> 00:21:05,210
prostor, který je v horní části všech prvků ve stohu.

276
00:21:05,210 --> 00:21:10,050
Takže na nejvyšší element není v s.size,

277
00:21:10,050 --> 00:21:14,930
ale, že je to pod ní.

278
00:21:14,930 --> 00:21:19,640
>> Další věc, kterou udělat, když se - v popu,

279
00:21:19,640 --> 00:21:22,030
je si třeba decrement velikosti.

280
00:21:22,030 --> 00:21:28,750
Pokud si pamatujete zpět do naší malé diagramu tady,

281
00:21:28,750 --> 00:21:30,980
Opravdu, jediná věc, která jsme viděli děje, když my jsme volali pop

282
00:21:30,980 --> 00:21:36,150
bylo, že tato velikost klesla, první 2, pak 1.

283
00:21:36,150 --> 00:21:42,620
Pak, když jsme se tlačil nový prvek na, by to jít na na správném místě.

284
00:21:42,620 --> 00:21:49,610
[Basil] Pokud s.size je 2, pak není to jít na prvku 2,

285
00:21:49,610 --> 00:21:54,400
a pak budeš chtít pop ten element off?

286
00:21:54,400 --> 00:21:59,510
Takže pokud bychom šli do - >> Tak se pojďme podívat na to znovu.

287
00:21:59,510 --> 00:22:07,730
Pokud je to náš zásobník na tomto místě

288
00:22:07,730 --> 00:22:12,130
a nazýváme pop,

289
00:22:12,130 --> 00:22:16,150
na které index je na nejvyšší 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še velikost 3, ale chceme, aby pop prvek na indexu 2.

292
00:22:24,220 --> 00:22:29,900
Je to tak typické druh off by ten, který máte s nulovou indexování polí.

293
00:22:29,900 --> 00:22:36,430
Takže vy chcete pop třetí prvek, ale třetí prvek není na indexu 3.

294
00:22:36,430 --> 00:22:39,430
A důvod, proč nemáme dělat, že mínus 1, když jsme tlačení

295
00:22:39,430 --> 00:22:44,120
je, protože právě teď, zjistíte, že na nejvyšší prvek,

296
00:22:44,120 --> 00:22:47,600
pokud bychom měli tlačit něco jiného na stacku v tomto bodě,

297
00:22:47,600 --> 00:22:50,360
budeme chtít tlačit na indexu 3.

298
00:22:50,360 --> 00:23:03,550
A to jen tak se stane, že velikost a indexy zarovnány, když tlačí.

299
00:23:03,550 --> 00:23:06,960
>> Kdo má pracovní zásobníku implementace?

300
00:23:06,960 --> 00:23:09,690
Máte pracovní stack jeden. Máte pop pracovat ještě?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ano. Myslím, že ano.

302
00:23:11,890 --> 00:23:14,610
Program >> funguje a není seg chybující, je to vytisknout?

303
00:23:14,610 --> 00:23:17,520
Má to vytisknout "úspěch" při spuštění?

304
00:23:17,520 --> 00:23:22,630
Jo. Udělejte zásobník, spusťte jej, pokud se vytiskne "úspěch" a nejde boom,

305
00:23:22,630 --> 00:23:26,000
pak vše je dobré.

306
00:23:26,000 --> 00:23:34,070
Dobrá. Pojďme k přístroji opravdu rychle,

307
00:23:34,070 --> 00:23:46,100
a projdeme to.

308
00:23:46,100 --> 00:23:51,110
Podíváme-li se na to, co se tady děje s pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, co bylo první věc, kterou udělal?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Pokud s.size je větší než 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Dobře. A proč jsi to udělal, že?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Ujistěte se, že tam bylo něco uvnitř zásobníku.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Právo. Chcete-li otestovat, aby se ujistil, že s.size je větší než 0;

314
00:24:10,950 --> 00:24:13,280
jinak, co chceš, aby se stalo?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? Návrat >> null, přesně.

316
00:24:16,630 --> 00:24:20,740
Takže pokud s.size je větší než 0. Tak co budeme dělat?

317
00:24:20,740 --> 00:24:25,890
Co budeme dělat, když zásobník není prázdný?

318
00:24:25,890 --> 00:24:31,210
[Stella] Zde decrement velikost? Ty >> decrement velikosti, v pořádku.

319
00:24:31,210 --> 00:24:34,440
Tak jak jsi to udělal, že? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. A pak to, co jsi udělal?

321
00:24:37,030 --> 00:24:44,140
[Stella] A pak jsem řekl: 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čném případě se vrátíte null. Ano, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Proč to nemusí být 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 jsem, že proto, že jste s 1 ven,

327
00:25:00,980 --> 00:25:04,290
pak budete vracet není ten, že požádal.

328
00:25:04,290 --> 00:25:09,400
[Hardison] A to bylo přesně to, co jsme mluvili o této celé problematice 0 indexů.

329
00:25:09,400 --> 00:25:11,380
Takže když jsme přibližování tady.

330
00:25:11,380 --> 00:25:15,650
Podíváme-li se na toho chlapa tady, můžete vidět, že když jsme pop,

331
00:25:15,650 --> 00:25:19,340
jsme objevovat prvek na indexu 2.

332
00:25:19,340 --> 00:25:25,200
>> Tak jsme snížit svoji velikost jako první, pak je naše velikost odpovídá náš index.

333
00:25:25,200 --> 00:25:39,650
Pokud nemáme decrement velikosti, potom musíme udělat velikosti -1 a pak útlum.

334
00:25:39,650 --> 00:25:45,270
Great. Všechny dobré?

335
00:25:45,270 --> 00:25:47,530
Jakékoliv dotazy na to?

336
00:25:47,530 --> 00:25:54,050
Existuje celá řada různých způsobů, jak napsat to stejně.

337
00:25:54,050 --> 00:26:03,290
Ve skutečnosti, můžeme udělat ještě něco - co můžeme udělat, je jednořádkový.

338
00:26:03,290 --> 00:26:05,770
Můžeme udělat jeden řádek návrat.

339
00:26:05,770 --> 00:26:12,980
Takže můžeme skutečně decrement předtím, než jsme se vrátit tím, že.

340
00:26:12,980 --> 00:26:18,320
Takže uvedení - před s.size.

341
00:26:18,320 --> 00:26:22,060
To dělá linka opravdu hustá.

342
00:26:22,060 --> 00:26:30,940
V případě, že rozdíl mezi -. S velikostí a s.size--

343
00:26:30,940 --> 00:26:40,130
je, že tento postfix - říkají, že postfix, protože - přichází po s.size--

344
00:26:40,130 --> 00:26:47,430
Znamená to, že s.size je vyhodnocena pro účely zjištění indexu

345
00:26:47,430 --> 00:26:50,410
jak je to v současné době, kdy se provádí tento řádek,

346
00:26:50,410 --> 00:26:54,290
a pak - se stane po řádku se provede.

347
00:26:54,290 --> 00:27:00,340
Po prvek na s.size indexu je přístupná.

348
00:27:00,340 --> 00:27:07,260
A to není to, co chceme, protože chceme, aby úbytek se stane první.

349
00:27:07,260 --> 00:27:10,990
Othewise, budeme přistupovat k pole, efektivně, mimo meze.

350
00:27:10,990 --> 00:27:16,850
Budeme přistupovat k prvku nad ten, který jsme vlastně chcete otevřít.

351
00:27:16,850 --> 00:27:23,840
Jo, Sam? >> Je to rychlejší, nebo použít méně RAM, aby se v jedné řadě, nebo ne?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Upřímně řečeno, to opravdu záleží.

353
00:27:29,620 --> 00:27:34,220
[Sam, nesrozumitelné] >> Jo, to záleží na okolnostech. Můžete to udělat kompilátoru triky

354
00:27:34,220 --> 00:27:41,580
získat kompilátor uznat, že většinou, jsem si představit.

355
00:27:41,580 --> 00:27:44,840
>> Tak jsme se již zmínil něco málo o této věci optimalizace kompilátoru

356
00:27:44,840 --> 00:27:47,400
že si můžete dělat při sestavování,

357
00:27:47,400 --> 00:27:50,580
a to je to věc, která kompilátor mohl zjistit,

358
00:27:50,580 --> 00:27:54,710
jako oh, hey, možná bych mohl udělat to všechno v jedné operaci,

359
00:27:54,710 --> 00:27:59,420
jak protichůdný k načítání velikost proměnné od RAM,

360
00:27:59,420 --> 00:28:03,770
dekrementování to, ukládání zpátky, a pak se načítání je zpět

361
00:28:03,770 --> 00:28:08,000
zpracovat zbytek této operace.

362
00:28:08,000 --> 00:28:10,710
Ale obvykle, ne, to není ten druh věci

363
00:28:10,710 --> 00:28:20,770
, co se děje, aby se váš program výrazně rychlejší.

364
00:28:20,770 --> 00:28:26,000
Nějaké další otázky týkající se sad?

365
00:28:26,000 --> 00:28:31,360
>> Takže tlačení a praskání. Pokud jste kluci chtějí vyzkoušet hackerský vydání,

366
00:28:31,360 --> 00:28:33,660
co jsme udělali v hackerské vydání je skutečně pryč

367
00:28:33,660 --> 00:28:37,670
a dělal to stack roste dynamicky.

368
00:28:37,670 --> 00:28:43,190
Úkolem je především tady v tlačné funkci,

369
00:28:43,190 --> 00:28:48,820
přijít na to, jak udělat, aby pole rostou

370
00:28:48,820 --> 00:28:52,450
jak si udržet tlačit více a více prvků na do zásobníku.

371
00:28:52,450 --> 00:28:56,000
Je to vlastně není moc doplňkový kód.

372
00:28:56,000 --> 00:29:00,080
Jen volání - musíte mít na paměti, aby se volání malloc tam správně,

373
00:29:00,080 --> 00:29:03,310
a pak zjistit, kdy budete volat realloc.

374
00:29:03,310 --> 00:29:06,090
To je zábavné problém, pokud máte zájem.

375
00:29:06,090 --> 00:29:11,550
>> Ale v současné době, pojďme dál, a pojďme mluvit o frontách.

376
00:29:11,550 --> 00:29:15,680
Procházejte zde.

377
00:29:15,680 --> 00:29:19,340
Fronta je blízko sourozenec zásobníku.

378
00:29:19,340 --> 00:29:25,380
Takže v zásobníku, byly věci, které dal v poslední

379
00:29:25,380 --> 00:29:28,810
byly první věci, a pak být načtena.

380
00:29:28,810 --> 00:29:33,600
Máme to poslední dovnitř, první ven, nebo LIFO, objednávání.

381
00:29:33,600 --> 00:29:38,390
Vzhledem k tomu, ve frontě, jak byste očekávali od okamžiku, kdy jste stál ve frontě,

382
00:29:38,390 --> 00:29:41,980
první osoba se dostat do souladu, první věc, dostat se do fronty,

383
00:29:41,980 --> 00:29:47,630
je první věc, která se dostane načíst z fronty.

384
00:29:47,630 --> 00:29:51,490
Fronty jsou také často používá, když máme co do činění s grafy,

385
00:29:51,490 --> 00:29:55,560
jako bychom mluvili o stručně s komíny,

386
00:29:55,560 --> 00:30:00,260
a fronty jsou také užitečné pro spoustu dalších věcí.

387
00:30:00,260 --> 00:30:06,180
Jedna věc, která přijde často se snaží udržovat, například,

388
00:30:06,180 --> 00:30:12,310
seřazený seznam prvků.

389
00:30:12,310 --> 00:30:17,650
A můžete to udělat pomocí pole. Můžete udržovat seřazený seznam věcí v matici,

390
00:30:17,650 --> 00:30:20,650
ale tam, kde to dostane složité je pak budete mít vždy najít

391
00:30:20,650 --> 00:30:26,160
vhodné místo pro vložení další věc.

392
00:30:26,160 --> 00:30:28,250
Takže pokud máte řadu čísel, 1 až 10,

393
00:30:28,250 --> 00:30:31,630
a pak chcete rozšířit, že na všechna čísla 1 až 100,

394
00:30:31,630 --> 00:30:33,670
a vy jste stále tato čísla v náhodném pořadí a snaží se udržet vše

395
00:30:33,670 --> 00:30:40,650
seřazeny, jak si projít, můžete skončit museli udělat hodně řazení.

396
00:30:40,650 --> 00:30:43,910
U některých typů front a některých typů podkladových datových struktur,

397
00:30:43,910 --> 00:30:46,670
můžete skutečně udržet poměrně jednoduchý.

398
00:30:46,670 --> 00:30:50,640
Nemáte něco přidat a pak přeorganizovat celá věc pokaždé.

399
00:30:50,640 --> 00:30:56,770
Ani budete muset udělat hodně posunutí vnitřních prvků kolem.

400
00:30:56,770 --> 00:31:02,990
Když se podíváme na frontě, uvidíte, že - také v queue.c v úseku -

401
00:31:02,990 --> 00:31:10,950
struct, že jsme stejně vám je opravdu podobný struct, že jsme vám dal na stack.

402
00:31:10,950 --> 00:31:13,770
>> Je tu ještě jedna výjimka z tohoto, a že jedna výjimka

403
00:31:13,770 --> 00:31:21,700
je to, že máme tuto dodatečnou integer s názvem hlava,

404
00:31:21,700 --> 00:31:28,120
a hlava je zde pro sledování hlavy fronty,

405
00:31:28,120 --> 00:31:32,160
nebo první prvek v řadě.

406
00:31:32,160 --> 00:31:37,470
S hromadou, jsme byli schopni sledovat prvku, který jsme měli k načtení,

407
00:31:37,470 --> 00:31:40,800
nebo horní části zásobníku, používat jen velikost,

408
00:31:40,800 --> 00:31:44,220
vzhledem k tomu, s fronty, jsme se museli vypořádat s opačných koncích.

409
00:31:44,220 --> 00:31:49,000
Snažíme křižovat věci na konci, ale pak se vrátí věci z přední strany.

410
00:31:49,000 --> 00:31:54,640
Takže účinně, s hlavou, máme index na začátku fronty,

411
00:31:54,640 --> 00:31:58,920
a velikost nám dává index konec fronty

412
00:31:58,920 --> 00:32:03,730
takže můžeme získat věci z hlavy a přidat věci k ocasu.

413
00:32:03,730 --> 00:32:06,890
Vzhledem k tomu, s komínem, jsme byli vždy jen se jedná o vrchol zásobníku.

414
00:32:06,890 --> 00:32:08,900
Nikdy jsme neměli přístup na dno zásobníku.

415
00:32:08,900 --> 00:32:12,220
Jsme jen přidal věci nahoru a vzal věci pryč z horní

416
00:32:12,220 --> 00:32:17,470
takže jsme nepotřebovali, že další pole uvnitř naší struct.

417
00:32:17,470 --> 00:32:20,590
Znamená to, že obecně smysl?

418
00:32:20,590 --> 00:32:27,670
Dobrá. Ano, Charlotte? [Charlotte, nesrozumitelným]

419
00:32:27,670 --> 00:32:32,660
[Hardison] To je velká otázka, a to ten, který přišel v přednášce.

420
00:32:32,660 --> 00:32:36,290
Možná procházel několika příkladech ukážeme, proč

421
00:32:36,290 --> 00:32:41,400
nechceme používat struny [0] jako hlavu fronty.

422
00:32:41,400 --> 00:32:46,770
>> Tak si představte, že máme frontu, budeme říkat, že fronty.

423
00:32:46,770 --> 00:32:49,210
Na začátku, když jsme právě instanci to,

424
00:32:49,210 --> 00:32:53,330
když jsme právě oznamoval, jsme není inicializována nic.

425
00:32:53,330 --> 00:32:56,790
Je to všechno smetí. Takže samozřejmě chceme, aby se ujistil, že inicializujeme

426
00:32:56,790 --> 00:33:00,950
jak velikost a hlavy pole na 0, něco rozumné.

427
00:33:00,950 --> 00:33:05,770
Mohli bychom také pokračovat a hodnotu null z prvků v našem frontě.

428
00:33:05,770 --> 00:33:09,930
A aby se tento diagram fit, zjistíte, že se naše fronty může mít pouze tři prvky;

429
00:33:09,930 --> 00:33:13,150
vzhledem k tomu, naše stack mohl držet čtyři, může naše fronty jen držet tři.

430
00:33:13,150 --> 00:33:18,680
A to jen proto, aby se diagram fit.

431
00:33:18,680 --> 00:33:26,150
První věc, která se zde děje je, že jsme Zařadí řetězec "ahoj".

432
00:33:26,150 --> 00:33:30,380
A stejně jako jsme to udělali s zásobníku, nic hrozně tu jiný,

433
00:33:30,380 --> 00:33:39,230
hodíme řetězce na na struny [0] a vložili naše velikost o 1.

434
00:33:39,230 --> 00:33:42,720
My Zařadí "bye", dostane se na sebe.

435
00:33:42,720 --> 00:33:45,870
Takže to vypadá jako hromada z podstatné části.

436
00:33:45,870 --> 00:33:53,230
Začali jsme tady, nový prvek, nový prvek, velikost udržuje jít nahoru.

437
00:33:53,230 --> 00:33:56,330
Co se stane v tomto okamžiku, kdy chceme, aby dequeue něco?

438
00:33:56,330 --> 00:34:01,280
Chceme-li dequeue, která je prvek, který chceme dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Přesně tak, Basil.

440
00:34:04,110 --> 00:34:10,960
Chceme se zbavit prvního řetězce, toto jeden, "hi".

441
00:34:10,960 --> 00:34:13,170
Takže to, co je další věc, která se změnilo?

442
00:34:13,170 --> 00:34:17,010
Všimněte si, když jsme vyskočila něco z fronty, jen jsme změnili velikost,

443
00:34:17,010 --> 00:34:22,080
ale tady, máme pár věcí, které se mění.

444
00:34:22,080 --> 00:34:27,440
Nejen, že se velikost změny, ale hlava změny.

445
00:34:27,440 --> 00:34:31,020
Toto se vrací do bodu Charlotte starší:

446
00:34:31,020 --> 00:34:38,699
proč máme tento hlavu stejně?

447
00:34:38,699 --> 00:34:42,110
Má to smysl teď, Charlotte? >> Druh.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Druh? Takže to, co se stalo, když jsme dequeued?

449
00:34:47,500 --> 00:34:54,340
Co hlava to, že nyní je zajímavé?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] No, protože se to změnilo - v pořádku. Aha.

451
00:34:56,449 --> 00:35:02,090
Vzhledem k tomu, hlava - kde hlava směřuje ke změnám, pokud jde o umístění.

452
00:35:02,090 --> 00:35:07,200
Je to už není vždy nula index jeden. >> Jo, přesně tak.

453
00:35:07,200 --> 00:35:17,660
Co se stalo, bylo-li dequeueing vysokou prvek

454
00:35:17,660 --> 00:35:20,590
byla dokončena a my jsme neměli tuto hlavu pole

455
00:35:20,590 --> 00:35:26,880
protože jsme byli vždy volat tento řetězec na 0 indexu hlava naší fronty,

456
00:35:26,880 --> 00:35:30,170
pak bychom museli posunout zbytek fronty dolů.

457
00:35:30,170 --> 00:35:36,010
Museli bychom se posunout "bye" od z řetězce [1] na řetězce [0].

458
00:35:36,010 --> 00:35:38,760
A řetězce [2] se stanoví na řetězce [1].

459
00:35:38,760 --> 00:35:43,050
A budeme muset udělat pro celý seznam prvků,

460
00:35:43,050 --> 00:35:45,110
celá řada prvků.

461
00:35:45,110 --> 00:35:50,490
A když to děláme s řadou, která se opravdu nákladné.

462
00:35:50,490 --> 00:35:53,340
Tak tady, to není velký problém. Musíme jen tři prvky v našem poli.

463
00:35:53,340 --> 00:35:57,230
Ale kdybychom měli frontu tisíc prvků nebo milion prvky,

464
00:35:57,230 --> 00:36:00,060
a pak všichni najednou, začneme dělat spoustu Dequeue volá všechny ve smyčce,

465
00:36:00,060 --> 00:36:03,930
věci opravdu zpomalit, protože přesouvá všechno dolů neustále.

466
00:36:03,930 --> 00:36:07,320
Víte, posunout o 1, posun o 1, posun o 1, posun o 1.

467
00:36:07,320 --> 00:36:13,650
Místo toho, my používáme tuto hlavu, říkáme, že "ukazatel", i když to není opravdu ukazatel

468
00:36:13,650 --> 00:36:16,430
v pravém slova smyslu, není to ukazatel typu.

469
00:36:16,430 --> 00:36:19,410
Není to int * nebo char * nebo něco podobného.

470
00:36:19,410 --> 00:36:28,930
Ale je to ukazovat nebo označující hlavu naší fronty. Jo?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Jak Dequeue vědět jen pop off, co je v čele?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Jak Dequeue vědět, jak se pop off, co je v čele? Právo >> jo.

473
00:36:43,620 --> 00:36:49,050
>> Co je to při pohledu na to jen, co hlava pole je nastaven na.

474
00:36:49,050 --> 00:36:52,710
Takže v tomto prvním případě, když se podíváme tady,

475
00:36:52,710 --> 00:36:55,690
Naše hlava je 0, index 0. Právo >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Tak to jen říká, že v pořádku, dobře, prvek na indexu 0, řetězec "ahoj",

477
00:37:00,500 --> 00:37:03,050
je prvek v čele naší fronty.

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 prvek, který se vrátil do volajícímu.

480
00:37:09,800 --> 00:37:14,540
Ano, Saad? Takže >> hlava v podstatě nastaví - kde budete indexovat?

481
00:37:14,540 --> 00:37:17,750
To je začátek toho? Jo >>. Dobře >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] To stát nový začátek pro naše pole.

483
00:37:22,900 --> 00:37:28,930
Takže když dequeue něco, vše, co musíte udělat, je přístup k prvku na indexu q.head,

484
00:37:28,930 --> 00:37:32,240
a že bude prvek, který chcete dequeue.

485
00:37:32,240 --> 00:37:34,930
Máte také decrement velikosti.

486
00:37:34,930 --> 00:37:39,430
Uvidíme se za chvilku, kdy se věci trochu složitější s tím.

487
00:37:39,430 --> 00:37:46,520
My dequeue, a teď, když se Zařadí znovu,

488
00:37:46,520 --> 00:37:51,300
kde máme Zařadí?

489
00:37:51,300 --> 00:37:55,000
Pokud se další prvek jít v naší frontě?

490
00:37:55,000 --> 00:37:57,980
Řekněme, že chceme Zařadí řetězec "CS".

491
00:37:57,980 --> 00:38:02,240
Do kterého index to půjde? [Studenti] Řetězce [2]. Dva >>.

492
00:38:02,240 --> 00:38:04,980
Proč 2 a ne 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Vzhledem k tomu, nyní hlava je 1, tak, že je jako na začátku seznamu?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Právo. A co označuje konec seznamu?

495
00:38:21,220 --> 00:38:23,290
Co jsme pomocí naznačovat konec naší fronty?

496
00:38:23,290 --> 00:38:25,970
Hlava je hlava naší fronty, začátek našeho fronty.

497
00:38:25,970 --> 00:38:29,530
Jaký je konec našeho fronty? [Studenti] Velikost. Velikost >> přesně.

498
00:38:29,530 --> 00:38:36,360
Takže naše nové prvky jít na velikosti, a prvky, které se vzlétnout sundat na hlavu.

499
00:38:36,360 --> 00:38:45,390
Když jsme Zařadí další prvek, jsme dávat jej do velikosti.

500
00:38:45,390 --> 00:38:48,530
[Student] Než dáte, že v když, velikost byla 1, ne?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Právo. Tak není zcela na velikosti. Velikost +, ne 1, ale + hlava.

502
00:38:55,690 --> 00:38:59,990
Protože jsme posunul všechno za hlavu částky.

503
00:38:59,990 --> 00:39:14,270
Tak tady, teď máme fronty velikosti 1, která začíná na indexu 1.

504
00:39:14,270 --> 00:39:20,730
Ocas je index 2. Ano?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Co se stane, když se Dequeue řetězce [0], a sloty Řetězce "v paměti

506
00:39:25,780 --> 00:39:29,420
Jen si vyprázdnila, v podstatě, nebo jen zapomněli?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Jo. V tomto smyslu, my jsme jen zapomenout je.

508
00:39:34,700 --> 00:39:42,640
Pokud bychom byli ukládání kopií nich -

509
00:39:42,640 --> 00:39:46,310
mnoho datových struktur se často ukládat své vlastní kopie prvků

510
00:39:46,310 --> 00:39:51,760
tak, že osoba řídící datové struktury nemá na starosti

511
00:39:51,760 --> 00:39:53,650
o tom, kde všechny ty ukazatele budou.

512
00:39:53,650 --> 00:39:56,000
Datová struktura má na všechno, má na všech kopií,

513
00:39:56,000 --> 00:39:59,580
aby se ujistil, že vše trvá přiměřeně.

514
00:39:59,580 --> 00:40:03,140
Nicméně v tomto případě, tyto datové struktury jen pro jednoduchost

515
00:40:03,140 --> 00:40:05,580
nejsou zhotovování kopií něco, co jsme ukládáním v nich.

516
00:40:05,580 --> 00:40:08,630
[Student] Tak je to kontinuální pole -? Ano >>.

517
00:40:08,630 --> 00:40:14,350
Pokud se podíváme zpět na to, co definice byla této struktury, je.

518
00:40:14,350 --> 00:40:19,110
Je to jen standardní pole, jako když jste viděli,

519
00:40:19,110 --> 00:40:24,280
pole * char s.

520
00:40:24,280 --> 00:40:26,340
Znamená to, že -? >> Jo, jen jsem přemýšlel,

521
00:40:26,340 --> 00:40:29,130
pokud budete nakonec dojdou paměti, do určité míry,

522
00:40:29,130 --> 00:40:32,330
Máte-li všechny tyto prázdné místa ve vašem poli?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Jo, to je dobrá připomínka.

524
00:40:36,390 --> 00:40:41,530
>> Podíváme-li se na to, co se stalo dnes v tomto bodě,

525
00:40:41,530 --> 00:40:46,350
jsme zaplnila naše fronty, jak to vypadá.

526
00:40:46,350 --> 00:40:50,390
Ale my jsme opravdu naplněna naše fronty

527
00:40:50,390 --> 00:40:57,710
protože máme frontu, která má velikost 2, ale začíná na indexu 1,

528
00:40:57,710 --> 00:41:02,160
protože to je místo, kde naše hlava je ukazatel.

529
00:41:02,160 --> 00:41:08,400
Stejně jako jsi říkal, že prvek v řetězci [0], na indexu 0, je ve skutečnosti neexistuje.

530
00:41:08,400 --> 00:41:10,450
Není to v naší frontě už.

531
00:41:10,450 --> 00:41:16,460
Jen jsme se neobtěžoval jít a přepsat ho, když jsme dequeued to.

532
00:41:16,460 --> 00:41:18,700
Takže i když to vypadá, že jsme k vyčerpání paměti, opravdu ne.

533
00:41:18,700 --> 00:41:23,270
To místo je k dispozici pro nás používat.

534
00:41:23,270 --> 00:41:29,310
Vhodné chování, pokud bychom měli vyzkoušet a první Dequeue něco

535
00:41:29,310 --> 00:41:34,420
jako "bye", že by se pop bye off.

536
00:41:34,420 --> 00:41:38,460
Nyní naše fronta začíná na indexu 2 a je o velikosti 1.

537
00:41:38,460 --> 00:41:42,240
A teď, když se snažíme a Zařadí zase něco, řekněme 50,

538
00:41:42,240 --> 00:41:47,880
50 by měla jít v tomto místě v indexu 0

539
00:41:47,880 --> 00:41:51,270
protože je to stále k dispozici pro nás. Ano, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Stává se to automaticky?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Nestává se zcela automaticky. Musíte si to spočítejte

542
00:41:56,150 --> 00:42:00,380
aby to fungovalo, ale v podstatě to, co jsme udělali je, že jsme právě omotal kolem.

543
00:42:00,380 --> 00:42:04,070
[Saad] A je to v pořádku, pokud to má díru uprostřed toho?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Je-li můžeme matematický fungovat správně.

545
00:42:08,720 --> 00:42:15,470
>> A ukázalo se, že to vlastně není tak těžké udělat s mod operátora.

546
00:42:15,470 --> 00:42:20,040
Tak jako jsme to udělali s Caesarem a další věci crypto,

547
00:42:20,040 --> 00:42:25,190
pomocí mod, můžeme dělat věci zabalit kolem a jít dál

548
00:42:25,190 --> 00:42:28,090
kolem a dokola a dokola s naší frontě,

549
00:42:28,090 --> 00:42:32,180
vedení, které hlava ukazatel pohybuje.

550
00:42:32,180 --> 00:42:38,840
Si všimnout, že velikost je vždy v počtu prvků ve skutečnosti v fronty.

551
00:42:38,840 --> 00:42:43,110
A je to jen hlava ukazatel, který udržuje vystřídat.

552
00:42:43,110 --> 00:42:49,660
Podíváme-li se na to, co se tady stalo, pokud bychom se vrátit na začátek,

553
00:42:49,660 --> 00:42:55,020
a vy se jen dívat, co se děje na hlavu

554
00:42:55,020 --> 00:42:58,240
když jsme Zařadí něco, nic se nestalo, aby na hlavě.

555
00:42:58,240 --> 00:43:00,970
Když jsme ve frontě něco jiného, ​​nic se nestalo, aby na hlavě.

556
00:43:00,970 --> 00:43:04,130
Hned jak jsme dequeued něco, hlava se zvedne o jednu.

557
00:43:04,130 --> 00:43:06,600
My ve frontě něco, nic se nestane do hlavy.

558
00:43:06,600 --> 00:43:11,060
Když jsme dequeue něco, hlava najednou dostane zvýšen.

559
00:43:11,060 --> 00:43:14,660
Když jsme Zařadí něco, nic se nestane do hlavy.

560
00:43:14,660 --> 00:43:20,240
>> Co by se stalo v tomto bodě, pokud bychom měli dequeue zase něco?

561
00:43:20,240 --> 00:43:23,240
Jakékoliv myšlenky? Co by se stalo do hlavy?

562
00:43:23,240 --> 00:43:27,190
Co by se mělo stát na hlavě

563
00:43:27,190 --> 00:43:32,990
pokud bychom měli dequeue něco jiného?

564
00:43:32,990 --> 00:43:35,400
Hlava teď je na indexu 2,

565
00:43:35,400 --> 00:43:38,920
, což znamená, že hlava frontě řetězce [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Která vrací 0? Je >> by se měla vrátit do 0. To by zabalit zpět kolem, přesně.

567
00:43:44,280 --> 00:43:48,440
Zatím pokaždé, když jsme říkali Dequeue, jsme byli přidání jednoho do hlavy,

568
00:43:48,440 --> 00:43:50,960
přidat jeden do hlavy, přidat jeden do hlavy, přidat jeden do hlavy.

569
00:43:50,960 --> 00:43:58,400
Jakmile že hlava ukazatel dostane na poslední index v našem poli,

570
00:43:58,400 --> 00:44:05,650
pak musíme zabalit zpět k začátku, jít zpátky do 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Co určuje kapacitu fronty v zásobníku?

572
00:44:09,900 --> 00:44:13,120
[Hardison] V tomto případě, právě jsme používali # definovaný konstantní. Dobře >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] V aktuální. Souboru c, můžete jít a špína se to trochu

574
00:44:19,590 --> 00:44:21,710
a učinit z něj tak velký, nebo tak málo, jak chcete.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Takže, když děláte to fronty, jak si udělat počítač vědět

576
00:44:25,310 --> 00:44:29,120
jak velký chcete stack být?

577
00:44:29,120 --> 00:44:31,700
[Hardison] To je velká otázka.

578
00:44:31,700 --> 00:44:34,800
Existuje několik způsobů, jak. Jedním z nich je právě definovat dopředu

579
00:44:34,800 --> 00:44:42,050
a říkají, že toto bude fronta, která má 4 prvky nebo 50 prvků nebo 10000.

580
00:44:42,050 --> 00:44:45,430
Druhým způsobem je dělat to, co lidé hackerů vydání dělají

581
00:44:45,430 --> 00:44:52,310
a vytvářet funkce, aby se vaše fronty dynamicky roste, protože stále více se věci zní a.

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Tak, aby šel s první možností, co syntaxe se používá

583
00:44:54,740 --> 00:44:57,830
říci programu, co je velikost fronty?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Takže pojďme se dostat z toho.

585
00:45:04,780 --> 00:45:12,650
Jsem stále v stack.c zde, tak jsem jen tak procházet až na vrchol zde.

586
00:45:12,650 --> 00:45:17,920
Vidíte toto právo tady? To je # define kapacitu 10.

587
00:45:17,920 --> 00:45:24,600
A to je téměř přesně stejné syntaxe, které máme k frontě.

588
00:45:24,600 --> 00:45:28,390
Kromě ve frontě, máme extra struct pole zde.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, myslel jsem, že kapacita znamená kapacitu pro řetězce.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> To, že je to maximální délka slova. >> Mám to.

591
00:45:36,770 --> 00:45:41,180
Jo. Kapacita zde - to je skvělý bod.

592
00:45:41,180 --> 00:45:44,000
A to je něco, co je složité

593
00:45:44,000 --> 00:45:49,480
protože to, co jsme vykazovat zde je řada * char s.

594
00:45:49,480 --> 00:45:52,770
Pole ukazatelů.

595
00:45:52,770 --> 00:45:56,690
To je pole znaků.

596
00:45:56,690 --> 00:46:01,690
To je asi to, co jste viděli, když jste prohlásil své vyrovnávací paměti pro soubor I / O,

597
00:46:01,690 --> 00:46:06,840
když jste byli vytvoření řetězce ručně na zásobníku.

598
00:46:06,840 --> 00:46:09,090
Avšak to, co tu máme, je řada char * s.

599
00:46:09,090 --> 00:46:13,400
Takže je to pole ukazatelů.

600
00:46:13,400 --> 00:46:18,350
Vlastně, když se přiblížíte ven a podíváme se na to, co se tady děje

601
00:46:18,350 --> 00:46:23,140
v prezentaci, můžete vidět, že skutečné prvky, znaková data

602
00:46:23,140 --> 00:46:26,180
není uložen v matici sám.

603
00:46:26,180 --> 00:46:42,690
Co je uložena v našem poli zde jsou odkazy k charakteru dat.

604
00:46:42,690 --> 00:46:52,560
Dobře. Takže jsme viděli, jak se velikost fronty je stejně jako u zásobníku,

605
00:46:52,560 --> 00:46:58,670
velikost vždy dodrží počet prvků v současné době v řadě.

606
00:46:58,670 --> 00:47:02,720
Po provedení 2 enqueues, velikost je 2.

607
00:47:02,720 --> 00:47:07,110
Po provedení Dequeue velikost je nyní 1.

608
00:47:07,110 --> 00:47:09,330
Po provedení další Zařadí velikost zpět na 2.

609
00:47:09,330 --> 00:47:12,340
Takže velikost rozhodně dodrží počet prvků ve frontě,

610
00:47:12,340 --> 00:47:15,580
a pak se hlava jen udržuje na kole.

611
00:47:15,580 --> 00:47:20,210
To jde od 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
A pokaždé, když říkáme Dequeue, dostane hlava ukazatel zvýšen na další index.

613
00:47:25,620 --> 00:47:29,930
A v případě, že hlava je asi jít přes, to tvoří zpět kolem 0.

614
00:47:29,930 --> 00:47:34,870
Takže s tím, my můžeme psát Dequeue funkci.

615
00:47:34,870 --> 00:47:40,200
A budeme opustit Zařadí funkci pro vy realizovat místo.

616
00:47:40,200 --> 00:47:45,880
>> Když jsme dequeue prvek z naší fronty,

617
00:47:45,880 --> 00:47:55,490
Co byla první věc, která Daniel udělal, když jsme začali psát pop funkci pro komíny?

618
00:47:55,490 --> 00:48:00,490
Nech mě slyšet od někoho, kdo se nemluví ještě.

619
00:48:00,490 --> 00:48:06,710
Pojďme se podívat, Saad, pamatuješ si, co Daniel udělal jako první věc, když on psal pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Tam byl, bylo to - >> Zkusil něco.

621
00:48:08,860 --> 00:48:12,140
[Saad] Pokud je velikost větší než 0. Přesně >>.

622
00:48:12,140 --> 00:48:14,390
A co to bylo testování?

623
00:48:14,390 --> 00:48:19,090
[Saad] To bylo testování, jestli tam je něco uvnitř pole.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Jo. Přesně tak. Takže nemůžete pop nic z fronty, pokud je prázdná.

625
00:48:23,210 --> 00:48:26,510
Stejně tak, nemůžete dequeue nic z fronty, pokud je prázdná.

626
00:48:26,510 --> 00:48:30,420
Co je první věc, kterou bychom měli udělat v naší Dequeue funkci tady, myslíš?

627
00:48:30,420 --> 00:48:33,860
[Saad] Pokud velikost je větší než 0? Jo >>.

628
00:48:33,860 --> 00:48:37,710
V tomto případě, jsem vlastně jen testovány, zda je 0.

629
00:48:37,710 --> 00:48:42,240
Pokud je 0, můžeme se vrátit null.

630
00:48:42,240 --> 00:48:45,280
Ale přesně stejná logika.

631
00:48:45,280 --> 00:48:49,110
A budeme pokračovat s tím.

632
00:48:49,110 --> 00:48:54,600
Pokud je velikost není 0, kde je prvek, který chceme dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] V čele? Přesně >>.

634
00:48:58,550 --> 00:49:01,720
Můžeme jen vytáhnout první prvek v naší frontě

635
00:49:01,720 --> 00:49:07,040
přístupem prvek v čele.

636
00:49:07,040 --> 00:49:14,630
Nic blázen.

637
00:49:14,630 --> 00:49:19,620
Po tom, co bychom měli udělat? Co se musí stát?

638
00:49:19,620 --> 00:49:23,740
Jaká byla další věc, která jsme si povídali o v Dequeue?

639
00:49:23,740 --> 00:49:28,130
Dvě věci se stalo, protože naše fronta změnila.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Zmenšení velikosti. >> Máme pro snížení velikosti, a zvýšit hlavu? Přesně tak.

641
00:49:35,640 --> 00:49:40,600
Chcete-li zvýšit hlavu, nemůžeme slepě zvýšit hlavu, vzpomenout.

642
00:49:40,600 --> 00:49:45,080
Nemůžeme prostě queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Musíme také tento mod od kapacity.

644
00:49:51,630 --> 00:49:54,740
A proč mod o kapacitu, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Vzhledem k tomu, že má obtékat kolem. Přesně >>.

646
00:49:58,680 --> 00:50:04,750
My mod o kapacitu, protože má zabalit zpět k 0.

647
00:50:04,750 --> 00:50:07,400
Takže teď, v tomto okamžiku, můžeme udělat to, co řekl Daniel.

648
00:50:07,400 --> 00:50:12,700
Můžeme decrement velikost.

649
00:50:12,700 --> 00:50:29,170
A pak můžeme jen vrátit prvek, který byl v horní části fronty.

650
00:50:29,170 --> 00:50:34,000
Vypadá to trochu drsný na prvním místě. Můžete mít otázku. Je nám líto?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Proč to nejprve na začátek fronty? Pokud to jde?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Pochází ze čtvrté řady na dně.

653
00:50:42,480 --> 00:50:46,060
Poté, co jsme testovat, aby se ujistil, že naše fronta není prázdná,

654
00:50:46,060 --> 00:50:54,100
jsme vytáhnout char * Nejdříve jsme vytáhněte prvek, který sedí v čele indexu

655
00:50:54,100 --> 00:50:58,680
našeho pole, z našeho řetězce pole, >> a volat, že první?

656
00:50:58,680 --> 00:51:04,500
[Hardison] A říkáme, že jako první. Jo.

657
00:51:04,500 --> 00:51:09,850
Stačí navázat na to, že důvod, proč si myslíte, že jsme to museli udělat, že?

658
00:51:09,850 --> 00:51:18,270
[Sam] Každý první právě vrací q.strings [q.head]? Jo >>.

659
00:51:18,270 --> 00:51:23,830
Vzhledem k tomu, >> děláme tato výměna q.head s mod funkcí,

660
00:51:23,830 --> 00:51:27,810
a neexistuje žádný způsob, jak to udělat, aby v rámci zpětného line také.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Přesně tak. Jste na místě. Sam zcela na místě.

662
00:51:31,640 --> 00:51:36,800
Důvod, proč jsme museli vytáhnout první prvek v našem frontě a uložit jej do proměnné

663
00:51:36,800 --> 00:51:43,030
Je tomu tak proto tento řádek, kde jsme právě q.head,

664
00:51:43,030 --> 00:51:47,030
je tu mod provozovatel tam není něco, co můžeme udělat,

665
00:51:47,030 --> 00:51:51,230
a jsou to projeví na hlavě bez - v jedné linii.

666
00:51:51,230 --> 00:51:54,480
Takže jsme vlastně muset vytáhnout první prvek, pak nastavte hlavu,

667
00:51:54,480 --> 00:52:00,430
upravit velikost, a pak se vrátit na prvek, který jsme vytaženo.

668
00:52:00,430 --> 00:52:02,680
A to je něco, co uvidíme přijít později

669
00:52:02,680 --> 00:52:04,920
spojené seznamy, jak hrajeme si s nimi.

670
00:52:04,920 --> 00:52:08,410
Často, když jste uvolnění nebo odstranění propojených seznamů

671
00:52:08,410 --> 00:52:13,500
musíte mít na paměti další prvek, další ukazatel propojeného seznamu

672
00:52:13,500 --> 00:52:16,330
Před likvidací té současné.

673
00:52:16,330 --> 00:52:23,580
Protože jinak byste zahodit informace o tom, co zbylo v seznamu.

674
00:52:23,580 --> 00:52:34,160
Nyní, když jdete do svého zařízení, můžete otevřít queue.c--x z toho.

675
00:52:34,160 --> 00:52:39,390
Takže když jsem otevřít queue.c, dovolte mi, abych zoom sem,

676
00:52:39,390 --> 00:52:44,970
uvidíte, že máte podobně vypadající soubor.

677
00:52:44,970 --> 00:52:49,200
Podobné vypadající soubor na to, co jsme měli dříve s stack.c.

678
00:52:49,200 --> 00:52:54,690
Máme naše struct pro frontu definovanou stejně jako jsme viděli na snímcích.

679
00:52:54,690 --> 00:52:59,870
>> Máme Zařadí funkci, která je pro vás udělat.

680
00:52:59,870 --> 00:53:04,340
A máme Dequeue funkci zde.

681
00:53:04,340 --> 00:53:06,870
Dequeue funkce v souboru je implementováno,

682
00:53:06,870 --> 00:53:13,230
ale já ji zpět až na PowerPoint, takže můžete zadat do, pokud budete chtít.

683
00:53:13,230 --> 00:53:16,690
Takže pro dalších 5 minut nebo tak, vy pracovat na Zařadí

684
00:53:16,690 --> 00:53:22,570
což je téměř pravým opakem Dequeue.

685
00:53:22,570 --> 00:53:29,560
Nemusíte upravit hlavu, když jste enqueueing, ale to, co máte nastavit?

686
00:53:29,560 --> 00:53:38,920
Velikost. Takže když enqueue, hlava zůstává nedotčený, dostane změní velikost.

687
00:53:38,920 --> 00:53:46,920
Ale to se trochu - budete muset pohrát s tou mod

688
00:53:46,920 --> 00:53:57,560
přijít na to, co přesně index nový prvek by měl být vložen na.

689
00:53:57,560 --> 00:54:03,080
Takže ti dám si kluci trochu, dal dequeue zpátky na snímku,

690
00:54:03,080 --> 00:54:05,200
a jak vy máte otázky, křičet ven tak, že můžeme

691
00:54:05,200 --> 00:54:09,220
všichni mluví o nich jako o skupině.

692
00:54:09,220 --> 00:54:13,960
Také, s velikosti ne - když upravíte velikost, můžete vždy jen -

693
00:54:13,960 --> 00:54:18,720
máte k mod velikost vůbec? [Daniel] No >> Nemusíte se mod velikosti, vpravo.

694
00:54:18,720 --> 00:54:24,260
Vzhledem k tomu, velikost bude vždy, pokud Jsi - za předpokladu, že jste správu věcí správně,

695
00:54:24,260 --> 00:54:30,840
velikost bude vždy mezi 0 a 3.

696
00:54:30,840 --> 00:54:38,680
Kde máte na mod, když děláte Zařadí?

697
00:54:38,680 --> 00:54:41,060
[Student] Pouze pro hlavu. Pouze >> pro hlavu, přesně.

698
00:54:41,060 --> 00:54:44,620
A proč máte na mod vůbec Zařadí?

699
00:54:44,620 --> 00:54:48,830
Pokud je situace, ve které budete muset mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Pokud máte věci v mezerách, jako na prostor 1 a 2,

701
00:54:53,630 --> 00:54:55,950
a pak třeba přidat něco na 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Jo, přesně tak. Takže pokud vaše hlava je ukazatel na samém konci,

703
00:55:02,570 --> 00:55:14,210
nebo je-li vaše velikost a vaše hlava je větší, nebo spíše, bude obtékat kolem fronty.

704
00:55:14,210 --> 00:55:17,830
>> Takže v této situaci, že jsme dostali tady na snímku právě teď,

705
00:55:17,830 --> 00:55:24,370
když chci Zařadí něco hned teď,

706
00:55:24,370 --> 00:55:31,110
chceme Zařadí něco na indexu 0.

707
00:55:31,110 --> 00:55:35,450
Takže, když se podíváte na místo, kde 50 jde, a já říkám Zařadí 50,

708
00:55:35,450 --> 00:55:40,840
to jde tam na dně. Jde v indexu 0.

709
00:55:40,840 --> 00:55:44,160
To nahradí 'ahoj', která již byla 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
Proč to dělat něco s hlavou v Zařadí?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, takže nejste modifikovat hlavu, omlouvám se.

713
00:55:55,770 --> 00:56:02,310
Ale musíte použít operátor modulo, když jste přístupu

714
00:56:02,310 --> 00:56:04,250
prvek, který chcete Zařadí když jste přístupu

715
00:56:04,250 --> 00:56:06,960
další prvek ve vašem frontě.

716
00:56:06,960 --> 00:56:10,960
[Basil] Já jsem to neudělal, a já jsem dostal "úspěch" na tam.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, jsem pochopil, co říkáte.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Takže didn't - jste právě udělal na q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Jo. Právě jsem změnil strany, neudělal jsem nic s hlavou.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Nemusíte vlastně muset resetovat hlavu za něco,

721
00:56:24,300 --> 00:56:31,650
ale když se index do řetězce pole,

722
00:56:31,650 --> 00:56:39,500
máte skutečně jít dopředu a vypočítat, kde další prvek je,

723
00:56:39,500 --> 00:56:44,230
protože proutí zásobníku, další prvek ve vašem zásobníku byl vždy

724
00:56:44,230 --> 00:56:48,740
na indexu odpovídající velikosti.

725
00:56:48,740 --> 00:56:55,850
Podíváme-li se zpátky na naší funkci zásobníku tlačítkem,

726
00:56:55,850 --> 00:57:03,100
můžeme vždy plonk v našem novém prvku přímo na indexu velikosti.

727
00:57:03,100 --> 00:57:06,710
Vzhledem k tomu, s fronty, to nemůžeme udělat, že

728
00:57:06,710 --> 00:57:10,340
protože pokud jsme na tuto situaci,

729
00:57:10,340 --> 00:57:18,130
pokud budeme ve frontě 50 naše nová řetězec by jít přímo na struny [1]

730
00:57:18,130 --> 00:57:20,540
které nechceme dělat.

731
00:57:20,540 --> 00:57:41,200
Chceme mít nový řetězec jít na indexu 0.

732
00:57:41,200 --> 00:57:44,320
>> Má někdo - ano? [Student] Mám otázku, ale to opravdu není příbuzný.

733
00:57:44,320 --> 00:57:48,160
Co to znamená, když někdo prostě zavolá něco jako Pred ukazatel?

734
00:57:48,160 --> 00:57:51,260
Co je to za jméno zkratka pro? Vím, že je to jen jméno.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred ukazatel? Pojďme se podívat,. V jaké souvislosti?

736
00:57:59,110 --> 00:58:01,790
[Student] To bylo pro vložku. Mohu vás požádat později, pokud budete chtít

737
00:58:01,790 --> 00:58:03,920
protože to není opravdu souvisí, ale já jsem prostě -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Od vlož kód Davida z přednášky?

739
00:58:07,300 --> 00:58:10,860
Můžeme vytáhnout, že a mluvit o tom.

740
00:58:10,860 --> 00:58:15,550
Budeme o tom mluvit dál, jakmile se dostaneme do propojených seznamů.

741
00:58:15,550 --> 00:58:21,440
>> Takže to opravdu rychle podívat na to, co enqueue funkce vypadá.

742
00:58:21,440 --> 00:58:26,530
Jaká byla první věc, že ​​lidé se snažil udělat v Zařadí řadě? Do této fronty?

743
00:58:26,530 --> 00:58:29,960
Podobně jako to, co jste udělal pro zásobníku tlačí.

744
00:58:29,960 --> 00:58:32,080
Co jsi udělal, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, nesrozumitelným]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Přesně tak. Pokud (q.size == KAPACITY) -

747
00:58:45,700 --> 00:58:54,720
Musím dát své závorky na správném místě - vrátí false.

748
00:58:54,720 --> 00:59:01,370
Zvětšit trochu. Dobře.

749
00:59:01,370 --> 00:59:03,800
Teď, co je další věc, že ​​jsme museli udělat?

750
00:59:03,800 --> 00:59:11,370
Stejně jako u zásobníku, a vloží na správném místě.

751
00:59:11,370 --> 00:59:16,010
A tak to, co bylo tím pravým místem pro vložení že?

752
00:59:16,010 --> 00:59:23,170
S zásobníku bylo index velikosti, s tím, že to není tak.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Mám q.head--nebo - >> 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] jsme pravděpodobně chtít, aby závorek tento

756
00:59:42,740 --> 00:59:48,830
tak, že jsme získali příslušnou přednost, a tak to cleart všem.

757
00:59:48,830 --> 00:59:55,800
A nastavit, aby stejné? Chcete-li >> str? Chcete-li >> str. Great.

758
00:59:55,800 --> 01:00:00,160
A teď, co je to poslední věc, kterou musíme udělat?

759
01:00:00,160 --> 01:00:06,780
Stejně jako jsme to dělali v zásobníku. Přírůstek >> velikost? Přírůstek >> velikosti.

760
01:00:06,780 --> 01:00:13,830
Boom. A pak, protože startovací kódu se právě vrátil false ve výchozím nastavení,

761
01:00:13,830 --> 01:00:27,460
chceme změnit na hodnotu true, pokud vše půjde až do konce a je vše v pořádku.

762
01:00:27,460 --> 01:00:33,050
Dobrá. To je hodně informací o oddílu.

763
01:00:33,050 --> 01:00:39,480
Nejsme zcela u konce. Chceme mluvit opravdu rychle o singly propojených seznamů.

764
01:00:39,480 --> 01:00:44,010
Dám to tak můžeme vrátit se k němu později.

765
01:00:44,010 --> 01:00:50,850
Ale pojďme zpět k naší prezentaci za pár více snímků.

766
01:00:50,850 --> 01:00:53,790
Takže enqueue je TODO, teď jsme to.

767
01:00:53,790 --> 01:00:57,430
>> Nyní se pojďme podívat na singly propojených seznamů.

768
01:00:57,430 --> 01:01:00,040
Mluvili jsme o nich trochu víc v přednášce.

769
01:01:00,040 --> 01:01:02,540
Kolik z vás viděl demo, kde jsme měli lidi

770
01:01:02,540 --> 01:01:08,220
neobratně ukázal na sebe a držení čísla? >> Byl jsem v tom.

771
01:01:08,220 --> 01:01:16,620
>> Co vy na to? Bylo to, doufejme, že demystifikovat tyto trochu?

772
01:01:16,620 --> 01:01:25,990
S seznamu, se ukazuje, že se zabýváme tohoto typu, který budeme nazývat uzel.

773
01:01:25,990 --> 01:01:32,520
Vzhledem k tomu, s fronty a zásobníku jsme měli structs, že bychom hovorovou frontu v zásobníku,

774
01:01:32,520 --> 01:01:34,860
jsme měli tyto nové fronty v zásobníku typů,

775
01:01:34,860 --> 01:01:39,240
Zde je seznam opravdu jen skládá banda uzlů.

776
01:01:39,240 --> 01:01:45,920
Stejným způsobem, že řetězce jsou jen banda znaků všech seřazených vedle sebe.

777
01:01:45,920 --> 01:01:50,650
Spojový seznam je jen uzel a další uzel a další uzel a jiný uzel.

778
01:01:50,650 --> 01:01:55,080
A spíše než rozbíjet všechny uzly dohromady a jejich uložení souvisle

779
01:01:55,080 --> 01:01:58,090
všechny přímo vedle sebe v paměti,

780
01:01:58,090 --> 01:02:04,470
má tuto další ukazatel nám umožňuje ukládat uzly Kdykoli je to, v náhodném pořadí.

781
01:02:04,470 --> 01:02:10,500
A pak druh drátu je všechny dohromady bodu od jednoho k druhému.

782
01:02:10,500 --> 01:02:15,850
>> A co bylo velkou výhodou, že to mělo přes pole?

783
01:02:15,850 --> 01:02:21,680
Přes ukládání všeho souvisle jen přilepená vedle sebe?

784
01:02:21,680 --> 01:02:24,190
Pamatuješ si? Jo? >> Dynamické přidělování paměti?

785
01:02:24,190 --> 01:02:27,220
>> Dynamické přidělování paměti, v jakém smyslu?

786
01:02:27,220 --> 01:02:31,780
[Student] V tomto můžete mít takže je větší a nemusíte se pohybovat celou řadu?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Přesně tak. Takže s pole, pokud chcete, aby nový prvek do středu,

788
01:02:40,940 --> 01:02:45,320
budete muset přesunout vše proto, aby prostor.

789
01:02:45,320 --> 01:02:47,880
A jak jsme si povídala s fronty,

790
01:02:47,880 --> 01:02:50,080
to je důvod, proč jsme udržet, že hlava ukazatel,

791
01:02:50,080 --> 01:02:52,050
tak, že nejsme neustále mění věci.

792
01:02:52,050 --> 01:02:54,520
Vzhledem k tomu, že se dostane drahé, pokud máte velkou pole

793
01:02:54,520 --> 01:02:57,130
a jste neustále dělat tyto náhodné vložení.

794
01:02:57,130 --> 01:03:00,820
Vzhledem k tomu, s přehledem, vše, co musíte udělat, je hodit to na nový uzel,

795
01:03:00,820 --> 01:03:06,330
nastavit ukazatele, a máte hotovo.

796
01:03:06,330 --> 01:03:10,940
Co naštve o to?

797
01:03:10,940 --> 01:03:16,830
Kromě skutečnosti, že je to není tak jednoduché pracovat jako s polem? Jo?

798
01:03:16,830 --> 01:03:22,980
[Daniel] No, myslím, že je to mnohem těžší přístup specifický prvek v připojeném seznamu?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Nemůžeš jen tak skočit do libovolného prvku v polovině svého propojeného seznamu.

800
01:03:30,470 --> 01:03:33,800
Jak se vám to muset udělat místo? >> Musíte krok celou věc.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Jo. Musíte projít jeden po druhém, jeden po druhém.

802
01:03:35,660 --> 01:03:38,480
Je to obrovská - to je bolest.

803
01:03:38,480 --> 01:03:41,550
Co je to druhé - je tu další pád na to.

804
01:03:41,550 --> 01:03:45,340
[Basil] Nemůžete jít dopředu a dozadu? Musíte jít jedním směrem?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Jo. Tak jak to budeme řešit, že někdy?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dvakrát-propojených seznamů? Přesně >>. K dispozici jsou dvojnásobně propojené seznamy.

807
01:03:53,370 --> 01:03:55,540
Tam jsou také - sorry?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Je to stejné jako s použitím PRED věc, že ​​-

809
01:03:57,620 --> 01:04:01,090
Právě jsem si vzpomněla, není to, co pred věc je?

810
01:04:01,090 --> 01:04:05,850
Není to mezi dvojnásobně a singly?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Pojďme se podívat na to, co přesně dělá.

812
01:04:10,020 --> 01:04:15,760
Tak jdeme na to. Zde je seznam kódu.

813
01:04:15,760 --> 01:04:25,620
Zde máme predptr, tady. Je to to, co jsi mluvil?

814
01:04:25,620 --> 01:04:30,750
Takže to byl - on osvobození seznam a snaží se uložit ukazatel na ni.

815
01:04:30,750 --> 01:04:35,000
To není o dvojnásob, jednotlivě propojené-listy.

816
01:04:35,000 --> 01:04:40,090
Můžeme mluvit více o tom později, protože to se mluví o uvolnění seznam

817
01:04:40,090 --> 01:04:42,900
a chci ukázat některé další věci jako první.

818
01:04:42,900 --> 01:04:51,480
ale je to jen - je to pamatovat hodnotu PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, to je předcházejících ukazatel? Jo >>.

820
01:04:54,170 --> 01:05:04,070
Takže pak můžeme zvýšit PTR sám předtím, než jsme pak zdarma to, co predptr je.

821
01:05:04,070 --> 01:05:09,130
Protože nemůžeme bez ptr a pak volat ptr = ptr další, ne?

822
01:05:09,130 --> 01:05:11,260
To by bylo špatné.

823
01:05:11,260 --> 01:05:20,940
Tak uvidíme, zpět na toho chlapa.

824
01:05:20,940 --> 01:05:23,900
>> Další špatná věc, o seznamech je, že vzhledem k tomu, s řadou

825
01:05:23,900 --> 01:05:26,520
budeme muset všechny prvky samy o sobě naskládané vedle sebe,

826
01:05:26,520 --> 01:05:29,050
Zde jsme také zavedli tento ukazatel.

827
01:05:29,050 --> 01:05:34,060
Takže je tu další kus paměti, že jsme museli použít

828
01:05:34,060 --> 01:05:37,910
pro každý prvek, který jsme uskladnění v našem seznamu.

829
01:05:37,910 --> 01:05:40,030
Dostaneme pružnost, ale to přijde v ceně.

830
01:05:40,030 --> 01:05:42,230
Dodává se s tímto časovým náklady,

831
01:05:42,230 --> 01:05:45,270
a je dodáván s tímto paměťovým náklady příliš.

832
01:05:45,270 --> 01:05:47,800
Čas v tom smyslu, že nyní musíme projít každý prvek v poli

833
01:05:47,800 --> 01:05:58,670
najít ten u indexu 10, nebo že by byli index 10 v poli.

834
01:05:58,670 --> 01:06:01,230
>> Jen opravdu rychle, když jsme diagram z těchto seznamů,

835
01:06:01,230 --> 01:06:05,980
obvykle se držet na hlavě seznamu nebo první ukazatel seznamu

836
01:06:05,980 --> 01:06:08,010
a vědomí, že to je pravda, ukazatel.

837
01:06:08,010 --> 01:06:11,100
Je to jen 4 bajty. Není to skutečný uzel sám.

838
01:06:11,100 --> 01:06:17,120
Takže vidíte, že to nemá žádnou hodnotu int v tom, žádný další ukazatel v něm.

839
01:06:17,120 --> 01:06:20,790
Je to doslova jen ukazatel.

840
01:06:20,790 --> 01:06:23,550
Bude to upozornit na něco, co je skutečné uzel struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] Ukazatel nazývá uzel? >> To je - není. To je ukazatel na něco typu uzlu.

842
01:06:28,480 --> 01:06:32,540
Je ukazatel na uzlu struct. >> Oh, dobře.

843
01:06:32,540 --> 01:06:36,870
Diagram vlevo, kódu napravo.

844
01:06:36,870 --> 01:06:42,190
Můžeme nastavit na null, což je dobrý způsob, jak začít.

845
01:06:42,190 --> 01:06:49,850
Když diagram, ty buď napsat, že za neplatné, nebo si dát čáru přes to takhle.

846
01:06:49,850 --> 01:06:53,910
>> Jedním z nejjednodušších způsobů, jak pracovat se seznamy,

847
01:06:53,910 --> 01:06:57,430
a žádáme vás, že i předřadit a připojit vidět rozdíly mezi těmito dvěma,

848
01:06:57,430 --> 01:07:01,320
ale předřadí je rozhodně jednodušší.

849
01:07:01,320 --> 01:07:05,790
Když začátek řádku, to je místo, kde si - když prepend (7),

850
01:07:05,790 --> 01:07:10,050
jdete a vytvořit uzlu struct

851
01:07:10,050 --> 01:07:13,870
a nastavit první poukázat na to, protože teď, protože jsme prepended to,

852
01:07:13,870 --> 01:07:17,240
to bude na začátku seznamu.

853
01:07:17,240 --> 01:07:22,540
Pokud se předřazeného (3), která vytváří další uzel, ale nyní 3 přichází do 7..

854
01:07:22,540 --> 01:07:31,130
Takže jsme v podstatě tlačí věci do našeho seznamu.

855
01:07:31,130 --> 01:07:34,720
Nyní můžete vidět, že prepend, někdy lidé říkají, že tlačit,

856
01:07:34,720 --> 01:07:39,600
proto, že jste tlačí nový prvek do seznamu.

857
01:07:39,600 --> 01:07:43,270
Je také snadné odstranit v čele seznamu.

858
01:07:43,270 --> 01:07:45,650
Takže lidé budou často volají, že pop.

859
01:07:45,650 --> 01:07:52,200
A tímto způsobem, lze emulovat balík pomocí spojového seznamu.

860
01:07:52,200 --> 01:07:57,880
Jejda. Je nám líto, teď se dostáváme do append. Takže tady máme prepended (7), nyní jsme prepend (3).

861
01:07:57,880 --> 01:08:02,600
Pokud bychom prepended něco jiného na tomto seznamu, pokud bychom prepended (4),

862
01:08:02,600 --> 01:08:06,540
pak budeme mít 4 a pak 3 a pak 7.

863
01:08:06,540 --> 01:08:14,220
Takže pak bychom mohli pop a odstranit 4, odstranit 3, odstraňte 7.

864
01:08:14,220 --> 01:08:16,500
Často více intuitivní způsob, jak přemýšlet o tom to je s append.

865
01:08:16,500 --> 01:08:20,310
Takže jsem diagramu, co by to vypadalo s připojit zde.

866
01:08:20,310 --> 01:08:23,380
Zde připojen (7) nemá vypadat jinak

867
01:08:23,380 --> 01:08:25,160
protože tam je jen jeden prvek v seznamu.

868
01:08:25,160 --> 01:08:28,620
A připojením (3) vloží to na konci.

869
01:08:28,620 --> 01:08:31,020
Možná si můžete prohlédnout hned teď trik s append

870
01:08:31,020 --> 01:08:36,600
je, že od té doby jsme jen vědět, kde na začátku seznamu je,

871
01:08:36,600 --> 01:08:39,450
připojit do seznamu musíte projít celou cestu v seznamu

872
01:08:39,450 --> 01:08:46,500
se dostat do konce, zastavte, a pak budovat svůj uzel a plonk všechno dolů.

873
01:08:46,500 --> 01:08:50,590
Zapojte všechny věci nahoru.

874
01:08:50,590 --> 01:08:55,170
Takže s Prepend, jak jsme právě projela to opravdu rychle,

875
01:08:55,170 --> 01:08:58,170
když předřadit do seznamu, je to poměrně jednoduché.

876
01:08:58,170 --> 01:09:02,960
>> Uděláte si nový uzel, zahrnovat některé dynamické přidělování paměti.

877
01:09:02,960 --> 01:09:09,830
Takže tady děláme uzlu struct pomocí malloc.

878
01:09:09,830 --> 01:09:14,710
Takže malloc jsme použili proto, že to zrušil paměť pro nás pro pozdější

879
01:09:14,710 --> 01:09:20,350
protože nechceme, aby to - chceme, aby tento paměti přetrvávat po dlouhou dobu.

880
01:09:20,350 --> 01:09:25,350
A my jsme si ukazatel na místo v paměti, že jsme právě přidělené.

881
01:09:25,350 --> 01:09:29,260
Používáme velikosti uzlu, nemáme sečíst pole.

882
01:09:29,260 --> 01:09:31,899
Nechceme ručně generovat počet bajtů,

883
01:09:31,899 --> 01:09:39,750
místo toho jsme použít sizeof, takže víme, že získání odpovídající počet bajtů.

884
01:09:39,750 --> 01:09:43,660
Snažíme se o to, aby testování, že naše malloc volání bylo úspěšné.

885
01:09:43,660 --> 01:09:47,939
To je něco, co chcete dělat v obecně.

886
01:09:47,939 --> 01:09:52,590
Na moderních strojích, vyčerpání paměti není něco, co je snadné

887
01:09:52,590 --> 01:09:56,610
pokud jste přidělení spoustu věcí a dělat obrovský seznam,

888
01:09:56,610 --> 01:10:02,220
ale pokud stavíte věci pro, řekněme, jako iPhone nebo Android,

889
01:10:02,220 --> 01:10:05,230
nemáte mají omezené prostředky paměti, zvláště pokud děláte něco intenzivní.

890
01:10:05,230 --> 01:10:08,300
Takže je to dobré se dostat do praxe.

891
01:10:08,300 --> 01:10:10,510
>> Všimněte si, že jsem použil několik různých funkcí zde

892
01:10:10,510 --> 01:10:12,880
, když jste viděli, že jsou trochu nové.

893
01:10:12,880 --> 01:10:15,870
Takže fprintf je stejně jako printf

894
01:10:15,870 --> 01:10:21,320
kromě svého prvního argumentu je potok, který chcete vytisknout.

895
01:10:21,320 --> 01:10:23,900
V tomto případě, že chceme vytisknout na standardní chybový řetězec

896
01:10:23,900 --> 01:10:29,410
, který je odlišný od standardního outstream.

897
01:10:29,410 --> 01:10:31,620
Implicitně se objeví na stejném místě.

898
01:10:31,620 --> 01:10:34,600
To také vytiskne na terminál, ale můžete -

899
01:10:34,600 --> 01:10:38,790
použití těchto příkazů jste se dozvěděli o tom, o přesměrování techniky

900
01:10:38,790 --> 01:10:42,290
jste se dozvěděli o ve videu Tommyho pro problémové sadu 4, můžete nasměrovat ji

901
01:10:42,290 --> 01:10:47,900
do různých oblastí, pak ukončete, tady, ukončí svůj program.

902
01:10:47,900 --> 01:10:50,440
Je to v podstatě jako návrat z hlavní,

903
01:10:50,440 --> 01:10:53,600
kromě používáme výjezd, protože zde návrat nebude dělat nic.

904
01:10:53,600 --> 01:10:57,140
Nejsme v hlavní, tak vrací neukončí program, jako chceme.

905
01:10:57,140 --> 01:11:03,020
Tak jsme se použít funkci ukončení a dát mu chybový kód.

906
01:11:03,020 --> 01:11:11,890
Pak zde máme nastaven nový uzel hodnotového pole, jeho i pole se rovná i, a pak jsme zapojte ho.

907
01:11:11,890 --> 01:11:15,530
Vydali jsme nový uzel je další ukazatel aby ukazoval na první,

908
01:11:15,530 --> 01:11:20,460
a pak první budou nyní na tento nový uzel.

909
01:11:20,460 --> 01:11:25,120
Tyto první řádky kódu, jsme vlastně stavět nový uzel.

910
01:11:25,120 --> 01:11:27,280
Ne poslední dva řádky této funkce, ale ty první.

911
01:11:27,280 --> 01:11:30,290
Můžete si skutečně vytáhnout do funkce, do pomocnou funkci.

912
01:11:30,290 --> 01:11:32,560
To je často to, co dělám je, že jsem ji vytáhnout do funkce,

913
01:11:32,560 --> 01:11:36,040
Říkám to něco jako uzel sestavení,

914
01:11:36,040 --> 01:11:40,410
a že udržuje prepend funkce docela malá, je to jen 3 řádky pak.

915
01:11:40,410 --> 01:11:48,710
I volat na mé funkce uzlu sestavení, a pak jsem drát všechno nahoru.

916
01:11:48,710 --> 01:11:51,970
>> Poslední věc, já vám chci ukázat,

917
01:11:51,970 --> 01:11:54,030
a nechám tě udělat append a to všechno na vlastní pěst,

918
01:11:54,030 --> 01:11:57,500
je, jak iterovat přes seznam.

919
01:11:57,500 --> 01:12:00,780
Existuje spoustu různých způsobů, jak přecházet přes seznam.

920
01:12:00,780 --> 01:12:03,140
V tomto případě se budeme najít délku seznamu.

921
01:12:03,140 --> 01:12:06,570
Takže začneme s délkou = 0.

922
01:12:06,570 --> 01:12:11,580
To je velmi podobné psaní strlen pro řetězec.

923
01:12:11,580 --> 01:12:17,780
To je to, co chci ukázat, to pro smyčku tady.

924
01:12:17,780 --> 01:12:23,530
Vypadá to trochu funky, to není obvyklé int i = 0, i <cokoliv, i + +.

925
01:12:23,530 --> 01:12:34,920
Místo toho je to inicializace naši proměnnou n být začátek seznamu.

926
01:12:34,920 --> 01:12:40,620
A pak, když naše iterator proměnná není null, budeme pokračovat.

927
01:12:40,620 --> 01:12:46,340
To je proto, že podle konvence, bude konec našeho seznamu je null.

928
01:12:46,340 --> 01:12:48,770
A pak přírůstek, spíše než dělat + +,

929
01:12:48,770 --> 01:12:57,010
spojový seznam ekvivalent + + je n = n-> další.

930
01:12:57,010 --> 01:13:00,410
>> Dám vám vyplnit mezery zde, protože jsme mimo čas.

931
01:13:00,410 --> 01:13:09,300
Ale mějte na paměti, až budete pracovat na svých spellr psets.

932
01:13:09,300 --> 01:13:11,650
Propojené seznamy, pokud jste provádění hash tabulky,

933
01:13:11,650 --> 01:13:14,010
určitě přijde velmi vhod.

934
01:13:14,010 --> 01:13:21,780
A má tento idiom pro smyčce nad věcí bude život mnohem jednodušší, snad.

935
01:13:21,780 --> 01:13:25,910
Jakékoliv dotazy, rychle?

936
01:13:25,910 --> 01:13:28,920
[Sam] Budete posílat vyplněný SLL a sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Jo. Budu posílat vyplněné diapozitivů a vyplněný SLL stoh a queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]