1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [6. szakasz: Kevesebb Comfortable]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard Egyetem]

3
00:00:05,040 --> 00:00:07,320
[Ez a CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Rendben van. Üdvözöljük a 6. szakasz.

5
00:00:11,840 --> 00:00:14,690
Ezen a héten, mi lesz beszélni adatszerkezetek szakaszban,

6
00:00:14,690 --> 00:00:19,780
elsősorban azért, mert az e heti problémája beállított spellr

7
00:00:19,780 --> 00:00:24,410
nem egy csomó különböző adatszerkezet feltárása.

8
00:00:24,410 --> 00:00:26,520
Van egy csomó különböző módon lehet menni a probléma halmaz,

9
00:00:26,520 --> 00:00:31,570
és minél több adatszerkezetek tudsz, annál több jó dolog, amit tehetünk.

10
00:00:31,570 --> 00:00:34,990
>> Tehát kezdjük. Először fogunk beszélni halom,

11
00:00:34,990 --> 00:00:37,530
a köteget, és sorban adatszerkezetek hogy fogunk beszélni.

12
00:00:37,530 --> 00:00:40,560
Stacks és a sorok nagyon hasznos, amikor elkezdünk beszélni grafikonok,

13
00:00:40,560 --> 00:00:44,390
amely nem fogunk csinálni annyi most.

14
00:00:44,390 --> 00:00:52,820
De ők nagyon jó, hogy megértsék az egyik nagy alapvető adatszerkezeteket a CS.

15
00:00:52,820 --> 00:00:54,880
A leírás a probléma set specifikáció,

16
00:00:54,880 --> 00:00:59,260
ha húzza fel, arról beszél, halom, mint rokon

17
00:00:59,260 --> 00:01:05,239
a halom étkezési tálcák, hogy van a kávézóban a étkező

18
00:01:05,239 --> 00:01:09,680
amennyiben ha az étkezési staff jön, és hozza az étkező tálcák után ők már tisztítani őket,

19
00:01:09,680 --> 00:01:12,000
ők verem őket egymás tetejére a többi.

20
00:01:12,000 --> 00:01:15,050
És akkor, amikor a gyerekek jönnek, hogy az élelmiszer,

21
00:01:15,050 --> 00:01:19,490
hogy húzza ki a tálca le, először a felső 1, akkor az egyik alatta, akkor az egyik alá.

22
00:01:19,490 --> 00:01:25,190
Tehát, valójában az első tálcát, hogy az étkező személyzete letette az utolsó, hogy lesz levették.

23
00:01:25,190 --> 00:01:32,330
Az utolsó, hogy az étkező személyzete hozott az első, hogy lesz levették vacsorára.

24
00:01:32,330 --> 00:01:38,100
A probléma meg a spec, ami letölthető, ha még nem tette meg,

25
00:01:38,100 --> 00:01:46,730
beszélünk modellezve egy halom adat struktúrájának használja ezt a fajta struktúra.

26
00:01:46,730 --> 00:01:51,070
>> Szóval, mi van itt, ez hasonló ahhoz, amit bemutatott előadás,

27
00:01:51,070 --> 00:01:58,120
kivéve az előadásban bemutatta ezt ints szemben char * s.

28
00:01:58,120 --> 00:02:06,250
Ez lesz a verem, hogy tárolja mi?

29
00:02:06,250 --> 00:02:09,009
Daniel? Mit tárolja a stack?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Mi tárolja húrok ebben stack, pontosan.

31
00:02:15,260 --> 00:02:20,950
Minden, amire szüksége van annak érdekében, hogy a verem egy tömb

32
00:02:20,950 --> 00:02:23,920
egy adott kapacitás, ami ebben az esetben,

33
00:02:23,920 --> 00:02:28,020
kapacitás lesz minden sapkák, mert ez egy állandó.

34
00:02:28,020 --> 00:02:36,340
És amellett, hogy a tömb minden, amit meg kell követni az aktuális méret a tömb.

35
00:02:36,340 --> 00:02:38,980
Egy dolog megjegyezni, hogy ez a fajta jó

36
00:02:38,980 --> 00:02:47,060
az, hogy mi hozzuk létre az halmozott adatstruktúrája tetejére másik adatszerkezet, a tömb.

37
00:02:47,060 --> 00:02:50,110
Vannak különböző módon végrehajtani stack.

38
00:02:50,110 --> 00:02:54,250
Mi nem is elég még, de remélhetőleg elvégzése után a linkelt lista problémák,

39
00:02:54,250 --> 00:03:00,520
látni fogja, hogyan lehet könnyen végre egy halom tetején egy láncolt lista is.

40
00:03:00,520 --> 00:03:02,640
De most, akkor ragaszkodj a tömbök.

41
00:03:02,640 --> 00:03:06,350
Tehát újra, minden van szükségünk egy tömb, és csak meg kell követni a méret a tömb.

42
00:03:06,350 --> 00:03:09,850
[Sam] Bocs, hogy miért van az, hogy azt mondta, ez a halom tetején a húrok?

43
00:03:09,850 --> 00:03:13,440
Számomra úgy tűnik, mintha a húrok belül a köteget.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Igen. Mi létre, mi vesz a tömb adatszerkezetet -

45
00:03:16,790 --> 00:03:22,130
ez egy nagy kérdés. Tehát a kérdés, hogy miért, mert az emberek, akik figyelnek az online,

46
00:03:22,130 --> 00:03:24,140
miért vagyunk azzal, hogy a verem tetején a húrok,

47
00:03:24,140 --> 00:03:27,990
mert itt úgy néz ki, mint a húrok belül vannak a stack?

48
00:03:27,990 --> 00:03:31,050
Ami teljesen a helyzet.

49
00:03:31,050 --> 00:03:34,660
Amit utaltam az volt, hogy már van egy tömb adatszerkezet.

50
00:03:34,660 --> 00:03:39,290
Van egy sor char * s ez a tömb vonósok,

51
00:03:39,290 --> 00:03:45,300
és mi lesz hozzá, hogy annak érdekében, hogy megteremtse a halmozott adatok szerkezetét.

52
00:03:45,300 --> 00:03:48,620
>> Tehát egy stack valamivel bonyolultabb, mint egy tömb.

53
00:03:48,620 --> 00:03:51,890
Tudjuk használni egy tömböt, hogy építsenek egy verem.

54
00:03:51,890 --> 00:03:55,810
Szóval, ez az, ahol azt mondjuk, hogy a kémény épült a tetején egy tömb.

55
00:03:55,810 --> 00:04:02,510
Hasonlóképpen, mint korábban mondtam, tudunk építeni egy halom tetején egy láncolt lista.

56
00:04:02,510 --> 00:04:04,960
Ahelyett, hogy egy tömb, hogy tartsa meg a elemet,

57
00:04:04,960 --> 00:04:10,070
tudtuk használni a láncolt lista, hogy tartsa meg a elemek és építeni a verem körül, hogy.

58
00:04:10,070 --> 00:04:12,420
Sétáljunk át néhány példát, látszó néhány kód,

59
00:04:12,420 --> 00:04:14,960
hogy lássa, mi történik itt valójában.

60
00:04:14,960 --> 00:04:23,400
A bal oldalon, amit dobott le, hogy mi struct stack nézne ki a memóriában

61
00:04:23,400 --> 00:04:28,330
Ha a kapacitást # definiáljuk négy.

62
00:04:28,330 --> 00:04:33,490
Megvan a négy elem char * tömb.

63
00:04:33,490 --> 00:04:38,110
Van strings [0], strings [1], strings [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
majd, hogy az utolsó helyet a méret egész.

65
00:04:43,800 --> 00:04:46,270
Van ennek értelme? Oké.

66
00:04:46,270 --> 00:04:48,790
Ez történik, ha az, amit csinálok a jobb oldalon,

67
00:04:48,790 --> 00:04:55,790
melyik lesz a kód, hogy csak nyilvánítson egy struct, a halmozott struct nevű s.

68
00:04:55,790 --> 00:05:01,270
Ez az, amit kap. Megállapítja a lábnyom a memóriában.

69
00:05:01,270 --> 00:05:05,590
Az első kérdés az, mi a tartalma struct stack?

70
00:05:05,590 --> 00:05:09,250
Most ők semmit, de ők nem teljesen semmit.

71
00:05:09,250 --> 00:05:13,300
Ők ezt a fajta szemetet. Fogalmunk sincs, mi van velük.

72
00:05:13,300 --> 00:05:17,000
Amikor állapítsa stack s, mi csak dobott, hogy le a tetején memória.

73
00:05:17,000 --> 00:05:19,840
Ez olyan, mint nyilvánító int i, és nem inicializálása meg.

74
00:05:19,840 --> 00:05:21,730
Nem tudod, mi van benne. Tudod olvasni, mi van ott,

75
00:05:21,730 --> 00:05:27,690
de lehet, hogy nem lesz szuper hasznos.

76
00:05:27,690 --> 00:05:32,680
Az egyik dolog, amit szeretnénk, hogy mindig emlékezni kell tennie inicializálni amit inicializálni kell.

77
00:05:32,680 --> 00:05:35,820
Ebben az esetben fogjuk inicializálni a méret nulla,

78
00:05:35,820 --> 00:05:39,960
mert ez fog kiderülhet, hogy nagyon fontos a számunkra.

79
00:05:39,960 --> 00:05:43,450
Mi is megy előre, és inicializálja az összes mutató, az összes char * s,

80
00:05:43,450 --> 00:05:49,670
érthető, hogy néhány érték, valószínűleg null.

81
00:05:49,670 --> 00:05:58,270
De ez nem teljesen szükséges, hogy ezt tesszük.

82
00:05:58,270 --> 00:06:04,200
>> Most, a két fő műveletek stack?

83
00:06:04,200 --> 00:06:07,610
Mindenki emlékszik az előadás, amit csinálni stack? Igen?

84
00:06:07,610 --> 00:06:09,700
[Stella] megnyomásával és popping? >> Pontosan.

85
00:06:09,700 --> 00:06:13,810
Pushing és popping a két fő műveletek stack.

86
00:06:13,810 --> 00:06:17,060
És mit nyomógomb csinálni? >> A helyezi valamit rá a felső

87
00:06:17,060 --> 00:06:19,300
A verem, majd pukkanó veszi le.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Pontosan. Így nyomja tolja valamit a köteg tetején.

89
00:06:23,150 --> 00:06:27,700
Ez olyan, mint az étkező személyzete üzembe étkező tálcát a pultra.

90
00:06:27,700 --> 00:06:33,630
És popping vesz egy étkező tálca le a verem.

91
00:06:33,630 --> 00:06:36,460
Sétáljunk át néhány példát, hogy mi történik

92
00:06:36,460 --> 00:06:39,720
amikor nyomja a dolgokat a verem.

93
00:06:39,720 --> 00:06:45,110
Ha volt, hogy nyomja a húr "hello"-ra a verem,

94
00:06:45,110 --> 00:06:49,760
ez az, amit mi diagram nézne most.

95
00:06:49,760 --> 00:06:53,410
Nézze meg, mi történik?

96
00:06:53,410 --> 00:06:56,530
Mi tolta az első eleme a húrok array

97
00:06:56,530 --> 00:07:01,420
és mi növelte a méret számít, hogy 1.

98
00:07:01,420 --> 00:07:05,340
Tehát, ha megnézzük a különbséget a két diák, itt 0 volt, itt, mielőtt a push.

99
00:07:05,340 --> 00:07:08,690
Itt van azután a push.

100
00:07:08,690 --> 00:07:13,460
Mielőtt a push, miután a push.

101
00:07:13,460 --> 00:07:16,860
És most van egy eleme a verem.

102
00:07:16,860 --> 00:07:20,970
Ez a string "hello", és ennyi.

103
00:07:20,970 --> 00:07:24,440
Minden más a tömbben, a mi húrok tömb, még szemét.

104
00:07:24,440 --> 00:07:27,070
Még nem inicializált meg.

105
00:07:27,070 --> 00:07:29,410
Mondjuk tolja egy húr rá a stack.

106
00:07:29,410 --> 00:07:32,210
Megyünk, hogy álljon "világ" erre az időre.

107
00:07:32,210 --> 00:07:35,160
Így lásd a "világ" itt megy a tetején "hello",

108
00:07:35,160 --> 00:07:40,040
és a méret gróf felmegy 2-re.

109
00:07:40,040 --> 00:07:44,520
Most nyomja meg a "CS50", és hogy megyek a tetején újra.

110
00:07:44,520 --> 00:07:51,110
Ha visszamegyünk, akkor láthatja, hogy mi nyomja a dolgokat a tetején a verem.

111
00:07:51,110 --> 00:07:53,320
És most kap a pop.

112
00:07:53,320 --> 00:07:58,910
Amikor valami bukkant ki a köteg, mi történt?

113
00:07:58,910 --> 00:08:01,540
Látta valaki a különbséget? Elég finom.

114
00:08:01,540 --> 00:08:05,810
[Student] A méretét. >> Ja, a méret változott.

115
00:08:05,810 --> 00:08:09,040
>> Mi mást kíván volna várható, hogy változni?

116
00:08:09,040 --> 00:08:14,280
[Student] A vonósok is. >> Rendben. A vonósok is.

117
00:08:14,280 --> 00:08:17,110
Kiderült, hogy amikor csinálod ezt így,

118
00:08:17,110 --> 00:08:21,960
mert mi nem másol az elemek a mi verem,

119
00:08:21,960 --> 00:08:24,670
valójában nem kell tennie semmit, akkor csak használja a méret

120
00:08:24,670 --> 00:08:28,630
nyomon követni, hogy hány dolog a tömbben

121
00:08:28,630 --> 00:08:33,780
annak érdekében, hogy amikor újra felbukkan, megint csak csökkentse a méretét le 1-re.

122
00:08:33,780 --> 00:08:39,440
Nem kell, hogy ténylegesen megy, és felülírja semmit.

123
00:08:39,440 --> 00:08:41,710
Fajta funky.

124
00:08:41,710 --> 00:08:46,520
Kiderült, hogy általában csak hagyjuk a dolgokat csak azért, mert ez kevesebb munkát nekünk csinálni.

125
00:08:46,520 --> 00:08:50,060
Ha nem kell, hogy menjen vissza, és felülírja valami, akkor miért csináljuk?

126
00:08:50,060 --> 00:08:54,150
Így, amikor a pop kétszer le a stack, minden, ami nem is csökkentjük a mérete egy-két alkalommal.

127
00:08:54,150 --> 00:08:59,120
És megint, ez csak azért, mert nem vagyunk másolás dolgokat a stack.

128
00:08:59,120 --> 00:09:01,320
Igen? Rajta.

129
00:09:01,320 --> 00:09:04,460
[Diák, érthetetlen] >> És akkor mi történik, ha valami nyomja meg újra?

130
00:09:04,460 --> 00:09:08,570
Ha valami nyomja meg újra, ha nem megy?

131
00:09:08,570 --> 00:09:12,390
Ha nem is megy, Basil? >> Into strings [1]? >> Rendben.

132
00:09:12,390 --> 00:09:14,530
Miért nem megy strings [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Mert elfelejtettem, hogy volt bármi strings [1] és [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Pontosan. A verem, lényegében "megfeledkezett", hogy a kezében tartott be semmit

135
00:09:24,040 --> 00:09:29,480
A strings [1] vagy strings [2], így mikor nyomja meg a "woot"

136
00:09:29,480 --> 00:09:36,670
ez csak hozza, hogy az elem a strings [1].

137
00:09:36,670 --> 00:09:41,590
Van bármilyen kérdése, hogy hogyan is működik ez, egy alap szinten?

138
00:09:41,590 --> 00:09:45,160
[Sam] Tehát ez nem dinamikus semmilyen módon, tekintve összeg

139
00:09:45,160 --> 00:09:47,620
, vagy jelentősen a méretét a stack?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Pontosan. Ez - a lényeg az volt, hogy ez nem volt egy dinamikusan growning verem.

141
00:09:56,750 --> 00:10:02,850
Ez egy olyan verem, hogy fér, legfeljebb 4 char * s, legfeljebb négy dolog.

142
00:10:02,850 --> 00:10:07,580
Ha volt, hogy megpróbálja, és nyomja meg 1/5 dolog, mit gondolsz, meg kell történnie?

143
00:10:07,580 --> 00:10:11,870
[Diákok, érthetetlen]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Pontosan. Van néhány dolog, ami történhet.

145
00:10:14,600 --> 00:10:19,330
Ez esetleg seg hiba, attól függően, mi volt -

146
00:10:19,330 --> 00:10:22,530
pontosan hogyan voltunk végrehajtására back-end.

147
00:10:22,530 --> 00:10:31,740
Ez lehet felülírni. Volna, hogy a buffer overflow, hogy beszélgettünk az osztályban.

148
00:10:31,740 --> 00:10:35,240
Mi lenne a legkézenfekvőbb dolog, hogy lehet felülírni

149
00:10:35,240 --> 00:10:42,370
ha megpróbálták betolni egy extra dolog, a mi stack?

150
00:10:42,370 --> 00:10:44,550
Szóval említette puffer túlcsordulást.

151
00:10:44,550 --> 00:10:47,870
Mi lehet az a dolog, ami kap felülírni vagy taposták a

152
00:10:47,870 --> 00:10:52,320
ha túlcsordult véletlenül próbálják nyomni egy extra dolog?

153
00:10:52,320 --> 00:10:54,730
[Daniel, érthetetlen] >> Lehetséges.

154
00:10:54,730 --> 00:10:58,440
De kezdetben, mi fog történni? Mi lenne, ha megpróbálta, hogy álljon egy negyedik dolog?

155
00:10:58,440 --> 00:11:06,220
Lehet, hogy felülírják a méret, legalábbis ez a memória diagram hogy megvan.

156
00:11:06,220 --> 00:11:10,880
>> A probléma set előírás, amit mi fogunk végrehajtó ma,

157
00:11:10,880 --> 00:11:16,030
amit akarok csinálni éppen visszatér hamis.

158
00:11:16,030 --> 00:11:20,030
A gombnyomásos módszer megy vissza boolean érték,

159
00:11:20,030 --> 00:11:22,920
és hogy a logikai érték lesz, igaz, ha a push sikerül

160
00:11:22,920 --> 00:11:29,730
és hamis, ha nem tudunk semmit, nyomja inkább, mivel a verem megtelt.

161
00:11:29,730 --> 00:11:33,620
Sétáljunk egy kicsit, hogy a kód most.

162
00:11:33,620 --> 00:11:36,400
Itt a push-funkció.

163
00:11:36,400 --> 00:11:40,380
A Push funkció egy halom fog tartani a húr, hogy terjesszen a verem.

164
00:11:40,380 --> 00:11:45,820
Ez lesz return true ha a string sikeresen tolta

165
00:11:45,820 --> 00:11:51,820
A stack és hamis egyébként.

166
00:11:51,820 --> 00:11:59,740
Minden arra vonatkozóan, hogyan lehet egy jó első dolog itt?

167
00:11:59,740 --> 00:12:20,630
[Sam] Ha a méret megegyezik kapacitás majd vissza hamis?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Szép munka.

169
00:12:23,320 --> 00:12:26,310
Ha a méret a kapacitás, megyünk vissza hamis.

170
00:12:26,310 --> 00:12:29,270
Nem tudunk tenni semmit többet a verem.

171
00:12:29,270 --> 00:12:36,900
Egyébként, szeretnénk tenni valamit a tetején a verem.

172
00:12:36,900 --> 00:12:41,670
Mit jelent a "a tetején a verem," az elején?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Méret 0? >> Size 0.

174
00:12:43,650 --> 00:12:49,990
Mi a legjobb a verem után van egy dolog, a stack? Missy, tudod?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Size egy, pontosan. Tartsd hozzátéve, hogy a méret,

176
00:12:52,720 --> 00:13:01,690
és minden alkalommal, amikor üzembe az új elemet az index méretét a tömbben.

177
00:13:01,690 --> 00:13:05,470
Meg tudjuk csinálni azt a fajta egysoros, ha van értelme.

178
00:13:05,470 --> 00:13:11,910
Szóval megvan a húrok tömb fogjuk elérni azt a méret index,

179
00:13:11,910 --> 00:13:14,780
és mi csak úgy, hogy tárolja a char * ott.

180
00:13:14,780 --> 00:13:19,340
Figyeljük meg, hogy nincs szöveg másolás folyik itt,

181
00:13:19,340 --> 00:13:29,680
nincs dinamikus elosztása a memória?

182
00:13:29,680 --> 00:13:34,440
Aztán Missy nevelkedett, amit most csinálni,

183
00:13:34,440 --> 00:13:40,570
mert már tárolt a húr a megfelelő helyre a tömbben,

184
00:13:40,570 --> 00:13:49,230
, és azt mondta, hogy meg kellett növelni a méretét az egyik, hogy készen állunk a következő push.

185
00:13:49,230 --> 00:13:53,950
Így nem tehetünk, hogy a s.size + +.

186
00:13:53,950 --> 00:13:59,330
Ezen a ponton, már szorult a tömb. Mi az utolsó dolog, amit meg kell tennünk?

187
00:13:59,330 --> 00:14:10,110
[Student] Vissza igaz. >> Vissza igaz.

188
00:14:10,110 --> 00:14:14,690
Szóval ez elég egyszerű, egy nagyon egyszerű kódot. Nem túl sok.

189
00:14:14,690 --> 00:14:17,070
Miután tekert a feje köré, hogy a kémény működik,

190
00:14:17,070 --> 00:14:21,910
ez elég könnyen megvalósítható.

191
00:14:21,910 --> 00:14:26,390
>> Most, a következő része ez popping egy sor le a verem.

192
00:14:26,390 --> 00:14:29,410
Fogok adni nektek egy kis időt, hogy a munka ezen egy kicsit.

193
00:14:29,410 --> 00:14:34,320
Ez majdnem olyan, alapvetően a fordítottja, mit tettünk itt push.

194
00:14:34,320 --> 00:14:38,510
Amit tettem valójában - oops.

195
00:14:38,510 --> 00:14:48,160
Már elindult ki a készüléket ide, és a készüléket,

196
00:14:48,160 --> 00:14:53,600
Már húzta fel a problémát készlet 5 előírás.

197
00:14:53,600 --> 00:15:02,560
Ha Nagyításhoz itt látjuk vagyok cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Már srácok le ezt a kódot, ami itt található, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Rendben van. Ha még nem tette meg, hogy csinálni most, nagyon gyorsan.

200
00:15:15,030 --> 00:15:22,130
Megcsinálom az én terminál ablakban.

201
00:15:22,130 --> 00:15:25,090
Igazából tettem fel ide. Igen.

202
00:15:25,090 --> 00:15:34,730
Igen, Sam? >> Lenne egy kérdésem, hogy miért mondtad s.string 's zárójelben size = str?

203
00:15:34,730 --> 00:15:42,910
Mi az str? Az, hogy a megadott valahol, vagy - ó, a char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Igen, pontosan. Ez volt az az érv. >> Ó, oké. Bocsánat.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Mi meghatározza a húr, hogy álljon be

206
00:15:49,470 --> 00:15:55,220
A másik kérdés, hogy jöhet ki, hogy nem igazán beszél itt volt

207
00:15:55,220 --> 00:15:58,810
vettünk értetődőnek tekinti, hogy mi volt ez a változó nevű s

208
00:15:58,810 --> 00:16:02,710
volt hatályát és hozzáférhető számunkra.

209
00:16:02,710 --> 00:16:06,960
Vettünk értetődőnek tekinti, hogy s volt ez a struct stack.

210
00:16:06,960 --> 00:16:08,930
Így nézett vissza most ezt a push-kódot,

211
00:16:08,930 --> 00:16:13,450
láthatod, hogy csinálunk dolgokat, hogy ennek az, hogy a kapott karakterlánc ben elfogadott

212
00:16:13,450 --> 00:16:19,210
de aztán hirtelen, mi hozzáférés s.size, mint, hol s származik?

213
00:16:19,210 --> 00:16:23,020
A kódot fogunk nézni a következő részben archívumban

214
00:16:23,020 --> 00:16:27,100
majd a dolog, hogy akkor csinál a probléma készletek,

215
00:16:27,100 --> 00:16:32,440
tettük a struct stack egy globális változót

216
00:16:32,440 --> 00:16:36,380
hogy mi férhet hozzá minden különböző funkciók

217
00:16:36,380 --> 00:16:40,630
anélkül, hogy kézzel adja át a környéken, és adja át a hivatkozással,

218
00:16:40,630 --> 00:16:44,870
tegyenek meg mindent, hogy ilyen dolgokat is.

219
00:16:44,870 --> 00:16:52,280
Mi csak csaló egy kicsit, ha úgy tetszik, hogy a dolgok szebb.

220
00:16:52,280 --> 00:16:57,430
És ez az, amit csinálunk itt, mert ez a móka kedvéért, ez könnyebb.

221
00:16:57,430 --> 00:17:02,800
Gyakran látni fogod ember ezt, ha van egy nagy adatstruktúra

222
00:17:02,800 --> 00:17:07,750
ez alatt üzemeltetett saját program.

223
00:17:07,750 --> 00:17:09,560
>> Menjünk vissza a készüléket.

224
00:17:09,560 --> 00:17:15,240
Vajon mindenki sikeresen kap a section6.zip?

225
00:17:15,240 --> 00:17:20,440
Mindenki csomagolja ki a unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Ha bemegy a 6. szakasz könyvtár -

227
00:17:27,200 --> 00:17:29,220
Ááá, az egész hely -

228
00:17:29,220 --> 00:17:32,840
és felsorolja, hogy mi van itt, látod, hogy van három különböző. c fájlokat.

229
00:17:32,840 --> 00:17:38,350
Van egy sorban, egy sll, amely egyszeres linkelt listát, és a verem.

230
00:17:38,350 --> 00:17:44,600
Ha nyit stack.c,

231
00:17:44,600 --> 00:17:47,330
láthatod, hogy megvan ez a struktúra meghatározott számunkra,

232
00:17:47,330 --> 00:17:51,330
a pontos struct, hogy mi csak beszélgettünk a diákat.

233
00:17:51,330 --> 00:17:56,340
Megvan a globális változó a stack,

234
00:17:56,340 --> 00:18:00,110
megvan a push-funkció,

235
00:18:00,110 --> 00:18:04,230
és akkor megvan a pop funkciót.

236
00:18:04,230 --> 00:18:08,320
Beteszem a kódot nyomja vissza a dián itt,

237
00:18:08,320 --> 00:18:10,660
de amit szeretnék nektek kell tennie, hogy a legjobb az a képesség,

238
00:18:10,660 --> 00:18:13,790
megy, és hajtsák végre a pop funkciót.

239
00:18:13,790 --> 00:18:18,480
Miután végre, akkor lehet fordítani ezt teszi verem,

240
00:18:18,480 --> 00:18:22,540
majd futtassa a kapott stack futtatható,

241
00:18:22,540 --> 00:18:28,390
és hogy futni fog mindez teszt kód ide, hogy ez a fő.

242
00:18:28,390 --> 00:18:31,060
És a fő gondoskodik ténylegesen hogy a push és pop hívások

243
00:18:31,060 --> 00:18:33,220
és gondoskodjanak arról, hogy minden megy keresztül minden rendben.

244
00:18:33,220 --> 00:18:36,820
Azt is inicializálja a stack mérete itt

245
00:18:36,820 --> 00:18:39,780
így nem kell aggódni, hogy inicializálása.

246
00:18:39,780 --> 00:18:42,310
Azt feltételezhetjük, hogy ez már megfelelően inicializálva

247
00:18:42,310 --> 00:18:48,000
az az idő, hogy érheti azt a pop funkciót.

248
00:18:48,000 --> 00:18:53,530
Van ennek értelme?

249
00:18:53,530 --> 00:19:00,100
Szóval itt vagyunk. Ott van a push-kódot.

250
00:19:00,100 --> 00:19:13,210
Adok nektek 5 vagy 10 perc.

251
00:19:13,210 --> 00:19:15,690
És ha bármilyen kérdése van az időközi közben kódolás,

252
00:19:15,690 --> 00:19:17,710
kérd meg őket, hangosan.

253
00:19:17,710 --> 00:19:23,080
Tehát, ha kap egy szúrás, csak kérdez.

254
00:19:23,080 --> 00:19:26,030
Hadd tudja, hadd mindenki tudja.

255
00:19:26,030 --> 00:19:28,160
Dolgozz a szomszéd is.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Épp végrehajtási pop most? >> Just pop.

257
00:19:30,360 --> 00:19:34,200
Bár tudja másolni végrehajtását push ha szeretné

258
00:19:34,200 --> 00:19:37,780
annak érdekében, hogy a vizsgálat fog működni.

259
00:19:37,780 --> 00:19:41,940
Mert nehéz tesztelni a dolgokat bekerülni -

260
00:19:41,940 --> 00:19:49,030
vagy nehéz tesztelni felbukkanó dolgokat egy köteg, ha nincs semmi a stack kezdeni.

261
00:19:49,030 --> 00:19:55,250
>> Mit pop kellene vissza? Az elem a tetején a verem.

262
00:19:55,250 --> 00:20:01,260
Állítólag, hogy az elem le a tetején a verem

263
00:20:01,260 --> 00:20:05,780
és majd csökkentjük a méret a verem,

264
00:20:05,780 --> 00:20:07,810
és most már elvesztette az elem a tetején.

265
00:20:07,810 --> 00:20:11,420
És akkor vissza az elem a tetején.

266
00:20:11,420 --> 00:20:20,080
[Diák, érthetetlen]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Szóval, mi történik, ha nem ezt? [Diák, érthetetlen]

268
00:20:28,810 --> 00:20:34,000
Mi végül is történik akkor valószínűleg elérésével sem

269
00:20:34,000 --> 00:20:37,350
olyan elem, amely nem került még inicializálva, így a számítás

270
00:20:37,350 --> 00:20:39,990
Az, ahol az utolsó elem ki van kapcsolva.

271
00:20:39,990 --> 00:20:46,260
Tehát itt, ha azt veszi észre, hogy push, vagyunk hozzáférés húrok a s.size elem

272
00:20:46,260 --> 00:20:48,560
mert ez egy új index.

273
00:20:48,560 --> 00:20:51,460
Ez az új tetején a verem.

274
00:20:51,460 --> 00:21:01,100
Mivel a pop, s.size lesz a következő hely,

275
00:21:01,100 --> 00:21:05,210
a tér, ami a tetején az összes elemet a verem.

276
00:21:05,210 --> 00:21:10,050
Tehát a legfelső elem nem s.size,

277
00:21:10,050 --> 00:21:14,930
hanem ez alatta.

278
00:21:14,930 --> 00:21:19,640
>> A másik dolog, ha - a pop,

279
00:21:19,640 --> 00:21:22,030
van akkor kell csökkentse a méretet.

280
00:21:22,030 --> 00:21:28,750
Ha emlékszel vissza a mi kis diagram itt,

281
00:21:28,750 --> 00:21:30,980
valóban, az egyetlen dolog, amit láttam történik, amikor az úgynevezett pop

282
00:21:30,980 --> 00:21:36,150
volt, hogy ez a méret csökkent, először 2, akkor 1-re.

283
00:21:36,150 --> 00:21:42,620
Aztán amikor tolt egy új elemet, akkor megy a megfelelő helyre.

284
00:21:42,620 --> 00:21:49,610
[Basil] Ha a s.size 2, akkor nem lenne menni elem 2,

285
00:21:49,610 --> 00:21:54,400
és akkor azt szeretné, hogy a pop ez az elem le?

286
00:21:54,400 --> 00:21:59,510
Tehát, ha mentünk - >> Akkor nézzük meg újra.

287
00:21:59,510 --> 00:22:07,730
Ha ez a mi stack ezen a ponton

288
00:22:07,730 --> 00:22:12,130
és felhívjuk pop,

289
00:22:12,130 --> 00:22:16,150
ahol index a legfelső elem?

290
00:22:16,150 --> 00:22:19,300
[Basil] A 2, de ez lesz a pop 3. >> Rendben.

291
00:22:19,300 --> 00:22:24,220
Szóval ez az, ahol a mérete 3, de azt szeretnénk, hogy a pop az elemet az index 2.

292
00:22:24,220 --> 00:22:29,900
Ez az a tipikus fajta le az egyik, hogy van a zéró indexelésének tömbök.

293
00:22:29,900 --> 00:22:36,430
Szóval nem szeretné, hogy a pop a harmadik elem, de a harmadik elem nem index 3.

294
00:22:36,430 --> 00:22:39,430
És az ok, amiért nem kell tennie, hogy a mínusz 1, ha mi nyomja

295
00:22:39,430 --> 00:22:44,120
azért van, mert most azt tapasztalja, hogy a legfelső elem,

296
00:22:44,120 --> 00:22:47,600
ha mi voltunk, hogy álljon ki valami mást a verembe ezen a ponton,

297
00:22:47,600 --> 00:22:50,360
mi lenne akarja nyomni azt index 3.

298
00:22:50,360 --> 00:23:03,550
És ez csak azért történik, hogy a méret és az indexek sorban, ha éppen nyomva.

299
00:23:03,550 --> 00:23:06,960
>> Kinek van egy működő stack végrehajtását?

300
00:23:06,960 --> 00:23:09,690
Van egy működő stack egyet. Van pop dolgozik még?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Igen. Azt hiszem, igen.

302
00:23:11,890 --> 00:23:14,610
>> Program fut, és nem seg Hibás, ez kinyomtatott?

303
00:23:14,610 --> 00:23:17,520
Vajon ki kell nyomtatni a "siker", amikor elindul?

304
00:23:17,520 --> 00:23:22,630
Igen. Győződjön verem, futtassa, ha kinyomtatja a "siker", és nem megy boom,

305
00:23:22,630 --> 00:23:26,000
akkor minden jó.

306
00:23:26,000 --> 00:23:34,070
Rendben van. Menjünk át a készülék nagyon gyorsan,

307
00:23:34,070 --> 00:23:46,100
és megyünk keresztül.

308
00:23:46,100 --> 00:23:51,110
Ha megnézzük, hogy mi folyik itt, pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, mi volt az első dolog, amit tett?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Ha s.size nagyobb, mint 0-ra.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Oké. És miért csináltad ezt?

312
00:24:03,120 --> 00:24:05,610
[Daniel] A győződjön meg arról, hogy van valami benne a papírköteget.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Rendben. Azt akarod, hogy teszteljék, hogy győződjön meg arról, hogy s.size nagyobb, mint 0;

314
00:24:10,950 --> 00:24:13,280
egyébként, mit akarsz, hogy megtörténjen?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Return null, pontosan.

316
00:24:16,630 --> 00:24:20,740
Tehát, ha s.size nagyobb, mint 0-ra. Akkor mit fogunk csinálni?

317
00:24:20,740 --> 00:24:25,890
Mit tegyünk, ha a verem nem üres?

318
00:24:25,890 --> 00:24:31,210
[Stella] You csökkentse a méret? >> A csökkentjük a méretet, oké.

319
00:24:31,210 --> 00:24:34,440
Hogy csináltad ezt? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Nagy. És akkor mit csináltál?

321
00:24:37,030 --> 00:24:44,140
[Stella] És akkor azt mondtam vissza s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Nagy.

323
00:24:48,560 --> 00:24:51,940
Ellenkező esetben vissza null. Igen, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Miért nem kell s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Igen. >> Megvan.

326
00:24:58,430 --> 00:25:00,980
[Sam] Azt hittem, azért, mert szedi 1 kimenet,

327
00:25:00,980 --> 00:25:04,290
akkor leszel vissza nem az egyik, hogy kértek.

328
00:25:04,290 --> 00:25:09,400
[Hardison] És ez volt az, mit beszéltünk ezzel az egész kérdéssel 0-indexek.

329
00:25:09,400 --> 00:25:11,380
Tehát ha Nagyításhoz vissza ide.

330
00:25:11,380 --> 00:25:15,650
Ha megnézzük ezt a fickót itt látható, hogy amikor a pop,

331
00:25:15,650 --> 00:25:19,340
mi popping az elemmel index 2.

332
00:25:19,340 --> 00:25:25,200
>> Így csökken a méret az első, akkor a mérete egyezik az index.

333
00:25:25,200 --> 00:25:39,650
Ha nem csökkentjük a méret az első, majd meg kell tennünk Méret -1 és majd csökkentő.

334
00:25:39,650 --> 00:25:45,270
Remek. Minden jó?

335
00:25:45,270 --> 00:25:47,530
Van még kérdése ezzel kapcsolatban?

336
00:25:47,530 --> 00:25:54,050
Van számos különböző módon írja ezt is.

337
00:25:54,050 --> 00:26:03,290
Tény, hogy tehetünk valamit, akár - tehetünk egy bélés.

338
00:26:03,290 --> 00:26:05,770
Tehetünk egy-line vissza.

339
00:26:05,770 --> 00:26:12,980
Tehát ténylegesen csökkentse, mielőtt vissza az csinálja.

340
00:26:12,980 --> 00:26:18,320
Így helyezi a - előtt s.size.

341
00:26:18,320 --> 00:26:22,060
Ez teszi a vonal nagyon sűrű.

342
00:26:22,060 --> 00:26:30,940
Amennyiben a közötti különbség - s. Méret és s.size--

343
00:26:30,940 --> 00:26:40,130
hogy ez a postfix - hívják postfix, mert az - után jön a s.size--

344
00:26:40,130 --> 00:26:47,430
azt jelenti, hogy s.size értékelése céljából a megállapítás az index

345
00:26:47,430 --> 00:26:50,410
mivel ez jelenleg amikor ez a vonal végrehajtásra kerül,

346
00:26:50,410 --> 00:26:54,290
majd ezt - történik a vonal lesz végrehajtva.

347
00:26:54,290 --> 00:27:00,340
Miután az elemét index s.size hozzáférni.

348
00:27:00,340 --> 00:27:07,260
És ez nem az, amit mi akarunk, mert azt akarjuk, hogy megtörténjen a Csökkentés először.

349
00:27:07,260 --> 00:27:10,990
Othewise, fogunk férni a tömb, hatékonyan, a határokat.

350
00:27:10,990 --> 00:27:16,850
Fogunk férni az elem felett az egyik, hogy mi valóban szeretnénk elérni.

351
00:27:16,850 --> 00:27:23,840
Igen, Sam? >> Van gyorsabban vagy kevesebb RAM van abban, hogy egy sorban, vagy sem?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Őszintén szólva, ez tényleg attól függ.

353
00:27:29,620 --> 00:27:34,220
[Sam, érthetetlen] >> Igen, ez attól függ. Meg tudod csinálni compiler trükkök

354
00:27:34,220 --> 00:27:41,580
, hogy a fordító, hogy ismerje el, hogy általában, gondolom.

355
00:27:41,580 --> 00:27:44,840
>> Így már említettük egy kicsit erről a fordítóprogram optimalizálás stuff

356
00:27:44,840 --> 00:27:47,400
hogy meg tudod csinálni összeállításában,

357
00:27:47,400 --> 00:27:50,580
és ez a fajta dolog, hogy a fordító képes lehet kitalálni,

358
00:27:50,580 --> 00:27:54,710
mint oh, hé, talán meg tudom csinálni ezt minden egy műveletben

359
00:27:54,710 --> 00:27:59,420
szemben betöltése mérete változó RAM-ból,

360
00:27:59,420 --> 00:28:03,770
csökkenő azt, tárolására vissza ki, majd berakodás vissza újra

361
00:28:03,770 --> 00:28:08,000
feldolgozni a többi ezt művelet.

362
00:28:08,000 --> 00:28:10,710
De általában, nem, ez nem az a fajta dolog

363
00:28:10,710 --> 00:28:20,770
ez megy, hogy a program lényegesen gyorsabb.

364
00:28:20,770 --> 00:28:26,000
Minden további kérdésre stack?

365
00:28:26,000 --> 00:28:31,360
>> Szóval toló és popping. Ha akartok, hogy próbálja ki a hacker kiadás,

366
00:28:31,360 --> 00:28:33,660
mit tettünk a hacker kiadás valójában emelkedett

367
00:28:33,660 --> 00:28:37,670
és tette ezt a stack dinamikusan növekszik.

368
00:28:37,670 --> 00:28:43,190
A kihívás abban áll elsősorban itt, a push funkció

369
00:28:43,190 --> 00:28:48,820
, hogy kitaláljuk, hogyan lehet, hogy a tömb nő

370
00:28:48,820 --> 00:28:52,450
ahogy folyamatosan nyomva több és több elemet a veremből.

371
00:28:52,450 --> 00:28:56,000
Ez valójában nem túl sok kiegészítő kódot.

372
00:28:56,000 --> 00:29:00,080
Csak egy hívás - meg kell emlékezni, hogy a hívások malloc ott megfelelően,

373
00:29:00,080 --> 00:29:03,310
majd kitaláljuk, mikor fogsz hívni realloc.

374
00:29:03,310 --> 00:29:06,090
Ez egy szórakoztató kihívás, ha érdekel.

375
00:29:06,090 --> 00:29:11,550
>> De egyelőre, menjünk tovább, és beszéljünk sorok.

376
00:29:11,550 --> 00:29:15,680
Lapozzunk végig itt.

377
00:29:15,680 --> 00:29:19,340
A sorban a közeli testvére a verem.

378
00:29:19,340 --> 00:29:25,380
Így a stack, dolgok kerültek utolsó

379
00:29:25,380 --> 00:29:28,810
volt az első dolog, akkor lehet lekérni.

380
00:29:28,810 --> 00:29:33,600
Van ez az utolsó, először ki, vagy LIFO, megrendelés.

381
00:29:33,600 --> 00:29:38,390
Mivel a sorban, ahogy elvárható, amikor sorban állás,

382
00:29:38,390 --> 00:29:41,980
az első, aki kap a sorban, az első dolog, hogy bekerüljön a sorba,

383
00:29:41,980 --> 00:29:47,630
az első dolog, hogy lesz található a sorból.

384
00:29:47,630 --> 00:29:51,490
Sorok is gyakran használják, ha van dolgunk grafikonok,

385
00:29:51,490 --> 00:29:55,560
mint beszéltünk röviden stack,

386
00:29:55,560 --> 00:30:00,260
és sorok is hasznos egy csomó más dolog.

387
00:30:00,260 --> 00:30:06,180
Egy dolog, hogy jön fel gyakran próbál fenntartani, például

388
00:30:06,180 --> 00:30:12,310
rendezett lista elemeit.

389
00:30:12,310 --> 00:30:17,650
És akkor ezt egy tömb. Ha tud fenntartani egy rendezett listát azokról a dolgokról egy tömb,

390
00:30:17,650 --> 00:30:20,650
de ha ez lesz trükkös van, akkor mindig meg kell találni

391
00:30:20,650 --> 00:30:26,160
a megfelelő hely, hogy helyezze be a következő dolog.

392
00:30:26,160 --> 00:30:28,250
Tehát, ha van egy sor számok 1 és 10 között,

393
00:30:28,250 --> 00:30:31,630
majd bővíteni szeretné, hogy az összes a számokat 1-től 100,

394
00:30:31,630 --> 00:30:33,670
és te, hogy ezeket a számokat véletlen sorrendben, és próbálják tartani mindent

395
00:30:33,670 --> 00:30:40,650
rendezve, ahogy megy át, akkor a végén kelljen sokat változik.

396
00:30:40,650 --> 00:30:43,910
Bizonyos típusú sorok és bizonyos típusú alapul szolgáló adatstruktúrák,

397
00:30:43,910 --> 00:30:46,670
akkor valóban tartani meglehetősen egyszerű.

398
00:30:46,670 --> 00:30:50,640
Nem kell, hogy adjunk valamit, majd átszervezés az egész dolog minden egyes alkalommal.

399
00:30:50,640 --> 00:30:56,770
Nem kell neked sokat változó, a belső elemek körül.

400
00:30:56,770 --> 00:31:02,990
Ha megnézzük a sorban, akkor láthatjuk, hogy - szintén queue.c fejezetében kód -

401
00:31:02,990 --> 00:31:10,950
A struct, hogy már adott Önnek valóban hasonló a struct, hogy adott neked egy verem.

402
00:31:10,950 --> 00:31:13,770
>> Van egy kivétel ez alól, és egy kivételével

403
00:31:13,770 --> 00:31:21,700
hogy van e kiegészítő integer fejnek nevezett

404
00:31:21,700 --> 00:31:28,120
és a fej itt a nyomon követése a fejét a sorban,

405
00:31:28,120 --> 00:31:32,160
vagy az első elem a sorban.

406
00:31:32,160 --> 00:31:37,470
A verem, tudtuk nyomon követni az elem, amely voltunk letölteni,

407
00:31:37,470 --> 00:31:40,800
vagy a felső a verem, a csak a méret,

408
00:31:40,800 --> 00:31:44,220
mivel a sorban, mi kelljen foglalkozni ellentétes végei.

409
00:31:44,220 --> 00:31:49,000
Próbálunk tack dolgokat a végén, de aztán vissza a dolgokat a fronton.

410
00:31:49,000 --> 00:31:54,640
Így hatékonyan, a fej, már az index elején a sorban,

411
00:31:54,640 --> 00:31:58,920
és a méret ad az index a végén a sor

412
00:31:58,920 --> 00:32:03,730
hogy mi lehet letölteni dolgokat a fejét, és add a dolgokat, hogy a farok.

413
00:32:03,730 --> 00:32:06,890
Mivel a stack voltunk, mindig csak foglalkozik a tetején a verem.

414
00:32:06,890 --> 00:32:08,900
Sosem volt hozzáférni az alján a verem.

415
00:32:08,900 --> 00:32:12,220
Csak hozzá dolgokat a felső és vette a dolgokat le a felső

416
00:32:12,220 --> 00:32:17,470
így nem volt szükség, hogy az extra terület belsejében a struct.

417
00:32:17,470 --> 00:32:20,590
Van, hogy általában van értelme?

418
00:32:20,590 --> 00:32:27,670
Rendben van. Igen, Charlotte? [Charlotte, érthetetlen]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Ez egy nagy kérdés, és ez volt az egyik, hogy jött fel előadás.

420
00:32:32,660 --> 00:32:36,290
Lehet, séta néhány példa jól szemlélteti, miért

421
00:32:36,290 --> 00:32:41,400
nem akarjuk használni strings [0], mint a feje a sorból.

422
00:32:41,400 --> 00:32:46,770
>> Tehát elképzelhető, hogy már a sorban, fogjuk nevezni sorban.

423
00:32:46,770 --> 00:32:49,210
Az elején, amikor már csak példányosított azt,

424
00:32:49,210 --> 00:32:53,330
amikor már csak úgy ítélte meg, még nem inicializált semmit.

425
00:32:53,330 --> 00:32:56,790
Ez az egész szemetet. Így természetesen szeretnénk, hogy győződjön meg arról, hogy mi inicializálása

426
00:32:56,790 --> 00:33:00,950
mind a méret és a fej mezőket értéke 0, valami ésszerű.

427
00:33:00,950 --> 00:33:05,770
Azt is megy előre, és null ki az elemeket a sorban.

428
00:33:05,770 --> 00:33:09,930
És hogy ez a diagram megfelelő, észreveheti, hogy most a várólista csak tartani három elem;

429
00:33:09,930 --> 00:33:13,150
mivel a stack tarthatna négy, a várólista csak tartani három.

430
00:33:13,150 --> 00:33:18,680
És ez csak az, hogy a diagram illeszkedést.

431
00:33:18,680 --> 00:33:26,150
Az első dolog, ami történik, itt is sorba állításához a string "szia".

432
00:33:26,150 --> 00:33:30,380
És ahogy tettük a verem, semmi szörnyen más itt,

433
00:33:30,380 --> 00:33:39,230
dobjuk a húr bekapcsolva strings [0] és növelni a méretét 1-gyel.

434
00:33:39,230 --> 00:33:42,720
Mi sorba állításához "bye", nem lesz hozott.

435
00:33:42,720 --> 00:33:45,870
Szóval ez úgy néz ki, mint egy verem a legtöbb.

436
00:33:45,870 --> 00:33:53,230
Kezdtük el itt, az új elem, új elem, mérete folyamatosan megy fel.

437
00:33:53,230 --> 00:33:56,330
Mi történik ezen a ponton, ha azt akarjuk, hogy dequeue valamit?

438
00:33:56,330 --> 00:34:01,280
Ha azt akarjuk, hogy dequeue, amely az elem, hogy szeretnénk dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Pontosan jobbra, Basil.

440
00:34:04,110 --> 00:34:10,960
Szeretnénk megszabadulni az első string, ez egy, "szia".

441
00:34:10,960 --> 00:34:13,170
Szóval, mi volt a másik dolog, ami változott?

442
00:34:13,170 --> 00:34:17,010
Figyeljük meg, amikor beugrott valami le a verem, csak változott a méret,

443
00:34:17,010 --> 00:34:22,080
de itt van egy pár dolgot, hogy a változás.

444
00:34:22,080 --> 00:34:27,440
Nem csak a méret megváltoztatását, de a feje változásokat.

445
00:34:27,440 --> 00:34:31,020
Ez megy vissza Charlotte szempontjából korábban:

446
00:34:31,020 --> 00:34:38,699
miért van ez a fej is?

447
00:34:38,699 --> 00:34:42,110
Van-e értelme most, Charlotte? >> Fajtája.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Fajta? Szóval, mi történt, amikor dequeued?

449
00:34:47,500 --> 00:34:54,340
Mit tett a feje tenni most érdekes?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, mert megváltozott - rendben. Értem.

451
00:34:56,449 --> 00:35:02,090
Mivel a fej -, ahol a fej mutat változások szempontjából a helyét.

452
00:35:02,090 --> 00:35:07,200
Ez nem mindig a nulla index 1. >> Igen, pontosan.

453
00:35:07,200 --> 00:35:17,660
Mi történt, ha dequeueing a nagy elem

454
00:35:17,660 --> 00:35:20,590
történt, és mi nem ezt a fejet a területen

455
00:35:20,590 --> 00:35:26,880
mert mi mindig hívja ezt a fonalat és 0 index élén a sorban,

456
00:35:26,880 --> 00:35:30,170
akkor volna váltani a többi sorban lefelé.

457
00:35:30,170 --> 00:35:36,010
Meg kéne váltani "bye"-ból származó strings [1], hogy a húrok [0].

458
00:35:36,010 --> 00:35:38,760
És strings [2] le strings [1].

459
00:35:38,760 --> 00:35:43,050
És mi volna, hogy ezt a teljes lista elemek,

460
00:35:43,050 --> 00:35:45,110
az egész tömb elemei.

461
00:35:45,110 --> 00:35:50,490
És amikor mi ezt egy tömböt, hogy lesz igazán költséges.

462
00:35:50,490 --> 00:35:53,340
Tehát itt, ez nem egy nagy dolog. Csak három elem a tömbben.

463
00:35:53,340 --> 00:35:57,230
De ha volt egy sorban ezer elemek vagy egy millió elemet,

464
00:35:57,230 --> 00:36:00,060
majd hirtelen, kezdjük, hogy egy csomó dequeue hívásokat egy hurok,

465
00:36:00,060 --> 00:36:03,930
a dolgok igazán fog lassulni, mivel eltolódások mindent le folyamatosan.

466
00:36:03,930 --> 00:36:07,320
Tudod, a váltott műszakban 1, műszak 1-jéig, a váltott műszakban 1, műszak 1-gyel.

467
00:36:07,320 --> 00:36:13,650
Ehelyett használja ezt a fejet, hívjuk a "pointer", bár ez nem igazán egy mutató

468
00:36:13,650 --> 00:36:16,430
a szigorúan vett, ez nem egy mutató típus.

469
00:36:16,430 --> 00:36:19,410
Ez nem egy int * vagy a char *, vagy ilyesmi.

470
00:36:19,410 --> 00:36:28,930
De ez mutat, illetve jelzi a feje a sorban. Igen?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Hogyan dequeue tudja, hogy csak elsül függetlenül áll a feje?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hogyan dequeue tudja, hogyan kell elsül bármi van a fejed? >> Igaz, igen.

473
00:36:43,620 --> 00:36:49,050
>> Mi ez nézi most csak amit a fej mező beállítása.

474
00:36:49,050 --> 00:36:52,710
Tehát ebben az első esetben, ha megnézzük itt,

475
00:36:52,710 --> 00:36:55,690
fejünk 0, index 0. >> Rendben.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Szóval csak azt mondja rendben, nos, az elem az index 0, akkor a string "hi"

477
00:37:00,500 --> 00:37:03,050
az elem élén a sorban.

478
00:37:03,050 --> 00:37:05,570
Így fogunk dequeue azt a fickót.

479
00:37:05,570 --> 00:37:09,800
És ez lesz az az elem, hogy adja vissza a hívónak.

480
00:37:09,800 --> 00:37:14,540
Igen, Saad? >> Tehát a fej alapvetően határozza meg -, hová megy az index meg?

481
00:37:14,540 --> 00:37:17,750
Ez a kezdete ez? >> Igen. >> Oké.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Ez lett az új kezdetet a tömb.

483
00:37:22,900 --> 00:37:28,930
Tehát, ha dequeue valamit, csak annyit kell tennie, hogy hozzáférhet a elemét index q.head,

484
00:37:28,930 --> 00:37:32,240
és ez lesz az elem kívánt dequeue.

485
00:37:32,240 --> 00:37:34,930
Azt is, hogy csökkentse a méretet.

486
00:37:34,930 --> 00:37:39,430
Meglátjuk egy kicsit, amikor a dolgok egy kicsit trükkös ezzel.

487
00:37:39,430 --> 00:37:46,520
Mi dequeue, és most, ha sorba állításához ismét

488
00:37:46,520 --> 00:37:51,300
hol sorba állításához?

489
00:37:51,300 --> 00:37:55,000
Ha ez a következő elem menni a sorban?

490
00:37:55,000 --> 00:37:57,980
Mondja el akarjuk sorba állításához a húr "CS".

491
00:37:57,980 --> 00:38:02,240
Into amely index fog menni? [Diákok] Strings [2]. >> Kettő.

492
00:38:02,240 --> 00:38:04,980
Miért 2 és nem 0-ra?

493
00:38:04,980 --> 00:38:13,570
[Basil] Mert most a fej 1, annak érdekében, hogy olyan, mint a kezdete a listát?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Rendben. És mi jelöli a lista végére?

495
00:38:21,220 --> 00:38:23,290
Miről is használja jelölésére végéig a sorban?

496
00:38:23,290 --> 00:38:25,970
A fej a feje a sorban, az elején a mi sorban.

497
00:38:25,970 --> 00:38:29,530
Mi a vége a mi sorban? [Diákok] Méret. >> Size, pontosan.

498
00:38:29,530 --> 00:38:36,360
Tehát az új elemeket megy a méret és az elemeket, hogy a felszállás jön le a fejét.

499
00:38:36,360 --> 00:38:45,390
Amikor sorba állításához a következő elem, mi üzembe azt a méretben.

500
00:38:45,390 --> 00:38:48,530
[Student] Mielőtt fel, hogy bár mérete 1. volt, ugye?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Rendben. Tehát nem elég a mérete. Size + nem +1, hanem + fej.

502
00:38:55,690 --> 00:38:59,990
Mert tolódott mindent a feje összeget.

503
00:38:59,990 --> 00:39:14,270
Szóval itt, most már van egy sorban méret 1, hogy kezdődik index 1.

504
00:39:14,270 --> 00:39:20,730
A farok index 2. Igen?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Mi történik, ha dequeue strings [0] és a húrok "nyílások memória

506
00:39:25,780 --> 00:39:29,420
csak kap kiürült, alapjában véve, vagy csak elfelejtetted?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Igen. Ebben az értelemben, mi csak elfelejtik őket.

508
00:39:34,700 --> 00:39:42,640
Ha arra tárolására másolatát őket -

509
00:39:42,640 --> 00:39:46,310
Sok adatstruktúrák gyakran tárolja a saját példányát az elemek

510
00:39:46,310 --> 00:39:51,760
úgy hogy a vezető személy az adatszerkezet nem kell aggódnia

511
00:39:51,760 --> 00:39:53,650
arról, hogy hol valamennyi mutató megy.

512
00:39:53,650 --> 00:39:56,000
Az adatszerkezet tartja be mindent, kapaszkodik az összes példány,

513
00:39:56,000 --> 00:39:59,580
, hogy győződjön meg arról, hogy minden továbbra is fennáll megfelelően.

514
00:39:59,580 --> 00:40:03,140
Azonban, ebben az esetben, ezek az adatok csak struktúrákat, az egyszerűség kedvéért,

515
00:40:03,140 --> 00:40:05,580
nem készít másolatokat semmit, hogy mi tárolja őket.

516
00:40:05,580 --> 00:40:08,630
[Student] Tehát ez egy folyamatos tömb -? >> Igen.

517
00:40:08,630 --> 00:40:14,350
Ha visszatekintünk, mit meghatározása volt ez a szerkezet, ez az.

518
00:40:14,350 --> 00:40:19,110
Ez csak egy standard tömb, mint láttad,

519
00:40:19,110 --> 00:40:24,280
tömb char * s.

520
00:40:24,280 --> 00:40:26,340
Van, hogy a -? >> Igen, csak gondoltam,

521
00:40:26,340 --> 00:40:29,130
ha akkor végül elfogy a memória, bizonyos mértékig,

522
00:40:29,130 --> 00:40:32,330
Ha mindezen üres foltok a tömb?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Igen, ez egy jó pont.

524
00:40:36,390 --> 00:40:41,530
>> Ha megnézzük, hogy mi történt ma ezen a ponton,

525
00:40:41,530 --> 00:40:46,350
most már megtelt a sort, úgy néz ki.

526
00:40:46,350 --> 00:40:50,390
De nem igazán töltötte fel a sort

527
00:40:50,390 --> 00:40:57,710
mert van egy sorban, ami 2-es méret, de kezdődik index 1,

528
00:40:57,710 --> 00:41:02,160
mert ez az, ahol a feje mutató.

529
00:41:02,160 --> 00:41:08,400
Ahogy mondták, ez az elem a strings [0], a mutató értéke 0, nem igazán van.

530
00:41:08,400 --> 00:41:10,450
Ez nem a mi sorban többé.

531
00:41:10,450 --> 00:41:16,460
Csak nem zavarta, hogy menjen, és írja át, amikor dequeued azt.

532
00:41:16,460 --> 00:41:18,700
Így annak ellenére, hogy úgy néz ki, mintha már elfogyott a memória, tényleg nem.

533
00:41:18,700 --> 00:41:23,270
Ez a hely nem elérhető a számunkra, hogy használja.

534
00:41:23,270 --> 00:41:29,310
A megfelelő viselkedés, ha mi voltunk, hogy megpróbálja, és az első dequeue valamit

535
00:41:29,310 --> 00:41:34,420
mint a "bye", amely pop bye ki.

536
00:41:34,420 --> 00:41:38,460
Most sorban kezdődik index 2 és úgy 1-es méretű.

537
00:41:38,460 --> 00:41:42,240
És most, ha megpróbáljuk sorba állításához, és valami újra, mondjuk 50,

538
00:41:42,240 --> 00:41:47,880
50 kell menni ezen a helyszínen index 0

539
00:41:47,880 --> 00:41:51,270
mert még mindig elérhető számunkra. Igen, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Ez azt automatikusan történik?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Ez nem történik meg teljesen automatikusan. Meg kell csinálni a matek

542
00:41:56,150 --> 00:42:00,380
hogy ez a munka, de lényegében az, amit tettünk az imént köré.

543
00:42:00,380 --> 00:42:04,070
[Saad] És ez baj, ha ez egy lyuk a közepén?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Ez, ha tudjuk, hogy a matematikai dolgozzanak ki megfelelően.

545
00:42:08,720 --> 00:42:15,470
>> És kiderül, hogy ez valójában nem olyan nehéz, hogy köze van a mod operátor.

546
00:42:15,470 --> 00:42:20,040
Szóval, ahogy tettük Caesar és a crypto stuff,

547
00:42:20,040 --> 00:42:25,190
használatával mod, akkor a dolgokat, hogy lezárja a környéken, és folyamatosan megy

548
00:42:25,190 --> 00:42:28,090
körbe-körbe-körbe a mi sorban,

549
00:42:28,090 --> 00:42:32,180
tartani, hogy a fej mutató körül mozog.

550
00:42:32,180 --> 00:42:38,840
Figyeljük meg, hogy a méret mindig tiszteletben tartva az elemek száma ténylegesen a sorban.

551
00:42:38,840 --> 00:42:43,110
És ez még csak a feje pointer, hogy megtartja a kerékpározás keresztül.

552
00:42:43,110 --> 00:42:49,660
Ha megnézzük, hogy mi történt itt, ha visszamegyünk a kezdetekhez,

553
00:42:49,660 --> 00:42:55,020
és csak nézni, hogy mi történik a fej

554
00:42:55,020 --> 00:42:58,240
amikor sorba állításához valamit, semmi sem történt a fejét.

555
00:42:58,240 --> 00:43:00,970
Amikor enqueued valami mást, nem történt semmi a fejét.

556
00:43:00,970 --> 00:43:04,130
Amint dequeued valamit, a fej felmegy egy.

557
00:43:04,130 --> 00:43:06,600
Mi enqueued valamit, semmi sem történik a fejét.

558
00:43:06,600 --> 00:43:11,060
Amikor dequeue valamit, hirtelen a fej lesz eggyel.

559
00:43:11,060 --> 00:43:14,660
Amikor sorba állításához valamit, semmi sem történik a fejét.

560
00:43:14,660 --> 00:43:20,240
>> Mi lenne, ha ezen a ponton voltunk, hogy dequeue valami újra?

561
00:43:20,240 --> 00:43:23,240
Minden gondolat? Mi történne a fejed?

562
00:43:23,240 --> 00:43:27,190
Mi történne a fej

563
00:43:27,190 --> 00:43:32,990
ha volt, hogy dequeue valami mást?

564
00:43:32,990 --> 00:43:35,400
A fej most van index 2,

565
00:43:35,400 --> 00:43:38,920
ami azt jelenti, hogy a fej a sorban strings [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Melyik értéke 0? Meg kell >> vissza 0-ra. Meg kell tekerje vissza körül, pontosan.

567
00:43:44,280 --> 00:43:48,440
Eddig minden alkalommal hívtuk dequeue, mi már hozzá egyet a fej,

568
00:43:48,440 --> 00:43:50,960
hozzá egy a fejét, adjunk hozzá egy a fejét, hozzá egy a fejét.

569
00:43:50,960 --> 00:43:58,400
Amint a fejet mutató lesz az utolsó index a tömbben,

570
00:43:58,400 --> 00:44:05,650
akkor meg kell tekerje vissza körül az elején, menj vissza 0-ra.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Mi határozza meg a kapacitás a várólista a stack?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Ebben az esetben, már most is használnak a # definiált konstans. >> Oké.

573
00:44:13,120 --> 00:44:19,590
[Hardison] A tényleges. C file, akkor megy és piszok vele egy kicsit

574
00:44:19,590 --> 00:44:21,710
és ez olyan nagy, vagy kicsi, amennyit csak akar.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Tehát, ha te így sorban, hogyan, hogy a számítógép tudja

576
00:44:25,310 --> 00:44:29,120
mekkora szeretné, hogy a stack lenni?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Ez egy jó kérdés.

578
00:44:31,700 --> 00:44:34,800
Van egy pár módon. Az egyik, hogy csak definiálja elöl

579
00:44:34,800 --> 00:44:42,050
és azt mondják, ez lesz a sorban, amely a 4 elem, vagy 50 elemek vagy 10.000.

580
00:44:42,050 --> 00:44:45,430
A másik módszer az, hogy amit a hacker verzió emberek csinálnak

581
00:44:45,430 --> 00:44:52,310
és hozzon létre funkciókat, hogy a sorban növekszik dinamikusan látna dolgok adunk be

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Szóval, hogy menjen el az első lehetőség, milyen szintaxist használsz

583
00:44:54,740 --> 00:44:57,830
megmondani a program mekkora a sor?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Akkor menjünk ki ebből.

585
00:45:04,780 --> 00:45:12,650
Én mindig stack.c itt, így én csak megy felfelé a csúcsra itt.

586
00:45:12,650 --> 00:45:17,920
Látod ezt itt? Ez a # define befogadóképessége 10.

587
00:45:17,920 --> 00:45:24,600
És ez majdnem pontosan ugyanazt a szintaxist, hogy van a sorban.

588
00:45:24,600 --> 00:45:28,390
Kivéve sorban, megvan az extra struct területen van.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Ó, azt hittem, a kapacitás jelentette kapacitását a húr.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Hogy ez a maximális hossza a szó. >> Megvan.

591
00:45:36,770 --> 00:45:41,180
Igen. A kapacitás itt - ez egy jó pont.

592
00:45:41,180 --> 00:45:44,000
És ez egy olyan dolog, ami bonyolult

593
00:45:44,000 --> 00:45:49,480
mert amit mi már bejelentett itt egy tömb char * s.

594
00:45:49,480 --> 00:45:52,770
Egy sor mutató.

595
00:45:52,770 --> 00:45:56,690
Ez egy sor karakter.

596
00:45:56,690 --> 00:46:01,690
Ez valószínűleg mit láttál, amikor már nyilvánításáról a pufferek a fájl I / O,

597
00:46:01,690 --> 00:46:06,840
ha már létre húrok kézzel a köteget.

598
00:46:06,840 --> 00:46:09,090
Azonban, mi van itt egy tömb char * s.

599
00:46:09,090 --> 00:46:13,400
Szóval ez egy sor mutató.

600
00:46:13,400 --> 00:46:18,350
Igazából, ha zoom vissza, és nézzük meg, mi folyik itt

601
00:46:18,350 --> 00:46:23,140
a bemutató, akkor láthatjuk, hogy az aktuális elemek, a karakteres adat

602
00:46:23,140 --> 00:46:26,180
nem tárolódik a tömb is.

603
00:46:26,180 --> 00:46:42,690
Mi tároljuk a mi tömb itt rámutatnak a karakteres adat.

604
00:46:42,690 --> 00:46:52,560
Oké. Tehát láttuk, hogy mekkora a várólista olyan, mint a verem,

605
00:46:52,560 --> 00:46:58,670
a méret mindig tiszteletben tartja az elemek száma jelenleg a sorban.

606
00:46:58,670 --> 00:47:02,720
Miután 2 enqueues, a mérete 2.

607
00:47:02,720 --> 00:47:07,110
Miután a dequeue mérete jelenleg 1.

608
00:47:07,110 --> 00:47:09,330
Miután egy másik sorba állítása a méret vissza 2-re.

609
00:47:09,330 --> 00:47:12,340
Tehát a méret határozottan tiszteletben tartja az elemek száma a sorban,

610
00:47:12,340 --> 00:47:15,580
majd a fejét, csak folyamatosan kerékpározás.

611
00:47:15,580 --> 00:47:20,210
Ez megy 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
És minden alkalommal hívjuk dequeue, a fej mutató kerül növekszik a következő index.

613
00:47:25,620 --> 00:47:29,930
És ha a fej arról szól, hogy menjen át, hogy hurkokat vissza mintegy 0-ra.

614
00:47:29,930 --> 00:47:34,870
Tehát azt tudjuk írni a dequeue funkciót.

615
00:47:34,870 --> 00:47:40,200
És mi lesz, hogy elhagyja a sorba állítása funkció srácok végrehajtása helyett.

616
00:47:40,200 --> 00:47:45,880
>> Amikor dequeue eleme a mi sorban,

617
00:47:45,880 --> 00:47:55,490
mi volt az első dolog, hogy Daniel volt, amikor elkezdtük írni a pop funkció stack?

618
00:47:55,490 --> 00:48:00,490
Hadd hallani valakit, aki még nem beszélt még.

619
00:48:00,490 --> 00:48:06,710
Lássuk, Saad, emlékszel, mit Daniel úgy tett, ahogy az első dolog, amikor azt írta, pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Ott volt, ez volt - >> Ő vizsgálni valamit.

621
00:48:08,860 --> 00:48:12,140
[Saad] Ha a mérete nagyobb, mint 0-ra. >> Pontosan.

622
00:48:12,140 --> 00:48:14,390
És mi volt, hogy a vizsgálatra?

623
00:48:14,390 --> 00:48:19,090
[Saad] Ez volt tesztelés, hátha van valami benne a tömbben.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Igen. Pontosan. Tehát nem lehet pop semmit a verem, ha ez üres.

625
00:48:23,210 --> 00:48:26,510
Hasonlóképpen, nem tudsz dequeue semmit a sorból, ha ez üres.

626
00:48:26,510 --> 00:48:30,420
Mi az első dolog, amit meg kell tennünk a mi dequeue funkció itt, mit gondolsz?

627
00:48:30,420 --> 00:48:33,860
[Saad] Ha a méret nagyobb, mint 0? >> Igen.

628
00:48:33,860 --> 00:48:37,710
Ebben az esetben, amit valójában csak tesztelt, hogy ha ez a 0-ra.

629
00:48:37,710 --> 00:48:42,240
Ha az értéke 0, akkor vissza null.

630
00:48:42,240 --> 00:48:45,280
De pontosan ugyanaz a logika.

631
00:48:45,280 --> 00:48:49,110
És hadd folytassa ezt.

632
00:48:49,110 --> 00:48:54,600
Ha a méret nem 0, hol van az elem, hogy szeretnénk dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] A fej? >> Pontosan.

634
00:48:58,550 --> 00:49:01,720
Mi is csak húzza ki az első eleme a sorban

635
00:49:01,720 --> 00:49:07,040
elérésével az elem a fejét.

636
00:49:07,040 --> 00:49:14,630
Semmi őrült.

637
00:49:14,630 --> 00:49:19,620
Után, mit tegyünk? Mi kell történnie?

638
00:49:19,620 --> 00:49:23,740
Mi volt a másik dolog, hogy beszélgettünk dequeue?

639
00:49:23,740 --> 00:49:28,130
Két dolog is történik, mert a várólista megváltozott.

640
00:49:28,130 --> 00:49:35,640
[Daniel] méretének csökkentése. >> Meg kell csökkenteni a méretét, és növeli a fej? Pontosan.

641
00:49:35,640 --> 00:49:40,600
Ha növelni szeretné a fejét, hogy nem lehet csak vakon növeli a fej, emlékszem.

642
00:49:40,600 --> 00:49:45,080
Nem csak tedd queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Meg kell még ezt a mod a kapacitást.

644
00:49:51,630 --> 00:49:54,740
És miért mod a kapacitás, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Mert kell köré. >> Pontosan.

646
00:49:58,680 --> 00:50:04,750
Mi a mod a képesség, mert, hogy lezárja vissza mintegy 0-ra.

647
00:50:04,750 --> 00:50:07,400
Tehát most, ezen a ponton, azt tehet, amit Daniel mondott.

648
00:50:07,400 --> 00:50:12,700
Mi lehet csökkentjük a méretet.

649
00:50:12,700 --> 00:50:29,170
És akkor is csak vissza az elemet, hogy volt a tetején a sorban.

650
00:50:29,170 --> 00:50:34,000
Úgy néz ki, a fajta csomós elején. Lehet, hogy a kérdést. Tessék?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Miért van először a felső sorban? Hova vezet ez megy?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Jön a negyedik sort az alján.

653
00:50:42,480 --> 00:50:46,060
Miután tesztelni, hogy győződjön meg arról, hogy a várólista nem üres,

654
00:50:46,060 --> 00:50:54,100
húzzuk ki char * először húzzuk ki az elemet, hogy ül az élén index

655
00:50:54,100 --> 00:50:58,680
a mi tömb, a mi vonósok tömb, >> és a hívás az első?

656
00:50:58,680 --> 00:51:04,500
[Hardison] És hívjuk először. Igen.

657
00:51:04,500 --> 00:51:09,850
Csak, hogy kövesse nyomon, hogy miért gondolom, hogy meg kellett csinálni?

658
00:51:09,850 --> 00:51:18,270
[Sam] Minden elsőt csak visszatér q.strings [q.head]? >> Igen.

659
00:51:18,270 --> 00:51:23,830
>> Mert mi ezt változó a q.head a mod funkcióval,

660
00:51:23,830 --> 00:51:27,810
és nincs módja, hogy a visszatérő ág is.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Pontosan. Te helyszínen. Sam teljesen folt.

662
00:51:31,640 --> 00:51:36,800
Ennek az az oka kellett, hogy húzza ki az első eleme a sorban, és tárolja azt egy változó

663
00:51:36,800 --> 00:51:43,030
azért van, mert ez a vonal, ahol az imént q.head,

664
00:51:43,030 --> 00:51:47,030
ott van a mod operátor nincs valami, amit tehetünk

665
00:51:47,030 --> 00:51:51,230
és azt lép hatályba, a fej nélkül - egy sorban.

666
00:51:51,230 --> 00:51:54,480
Tehát valójában, hogy húzza ki az első elemet, majd állítsa be a fejét,

667
00:51:54,480 --> 00:52:00,430
állítsa be a méretet, majd vissza az elemet, amit kihúzott.

668
00:52:00,430 --> 00:52:02,680
És ez egy olyan dolog, hogy majd meglátjuk, jön később

669
00:52:02,680 --> 00:52:04,920
kapcsolódó listák, ahogy játszunk körül őket.

670
00:52:04,920 --> 00:52:08,410
Gyakran, amikor felszabadítása vagy ártalmatlanítása kapcsolt listák

671
00:52:08,410 --> 00:52:13,500
meg kell emlékezni a következő elem, a következő mutató egy láncolt lista

672
00:52:13,500 --> 00:52:16,330
kidobása előtt a jelenlegi.

673
00:52:16,330 --> 00:52:23,580
Mert különben dobja az információt, hogy mi maradt a listán.

674
00:52:23,580 --> 00:52:34,160
Most, ha megy a készülék, akkor nyissa meg queue.c--x ki ebből.

675
00:52:34,160 --> 00:52:39,390
Szóval, ha én nyit queue.c, hadd zoom itt,

676
00:52:39,390 --> 00:52:44,970
látni fogja, hogy van egy hasonló kinézetű fájlt.

677
00:52:44,970 --> 00:52:49,200
Hasonló kinézetű fájlt mi volt korábban stack.c.

678
00:52:49,200 --> 00:52:54,690
Megvan a struct a queue meghatározott ahogy láttuk a diákat.

679
00:52:54,690 --> 00:52:59,870
>> Megvan a sorba állítása funkció, ami az Ön számára csinálni.

680
00:52:59,870 --> 00:53:04,340
És mi van a dequeue funkciója van.

681
00:53:04,340 --> 00:53:06,870
A dequeue funkciót a fájl nem implementált,

682
00:53:06,870 --> 00:53:13,230
de majd helyezze vissza a PowerPoint, így írja azt, ha szeretné.

683
00:53:13,230 --> 00:53:16,690
Így a következő 5 percig, vagy úgy, srácok dolgozni sorba állítása

684
00:53:16,690 --> 00:53:22,570
amely majdnem éppen az ellenkezője dequeue.

685
00:53:22,570 --> 00:53:29,560
Nem kell beállítani head amikor enqueueing, de mit kell beállítani?

686
00:53:29,560 --> 00:53:38,920
Méret. Tehát, ha sorba állítása, a fej marad érintetlen, a mérete lesz megváltozott.

687
00:53:38,920 --> 00:53:46,920
De ez nem vesz egy kicsit - akkor a játék körül, hogy a mod

688
00:53:46,920 --> 00:53:57,560
hogy kitaláljuk, pontosan mi az index új elem kell beilleszteni.

689
00:53:57,560 --> 00:54:03,080
Szóval Adok nektek egy kicsit, tedd dequeue vissza a dián,

690
00:54:03,080 --> 00:54:05,200
és ahogy ti kérdései vannak, kiabálni őket, hogy mi lehet

691
00:54:05,200 --> 00:54:09,220
minden beszélni velük, mint egy csoport.

692
00:54:09,220 --> 00:54:13,960
Továbbá, a méret nem - amikor állítsuk be a méretét, akkor mindig csak -

693
00:54:13,960 --> 00:54:18,720
Mit kell mod mérete valaha? [Daniel] Nem >> Nem kell mod mérete, jobbra.

694
00:54:18,720 --> 00:54:24,260
Mivel a méret mindig, ha készen is - feltéve, te irányító dolgokat megfelelően,

695
00:54:24,260 --> 00:54:30,840
a méret mindig 0 és 3 közé.

696
00:54:30,840 --> 00:54:38,680
Hol kell mod ha csinálsz sorba állítása?

697
00:54:38,680 --> 00:54:41,060
[Student] Csak a fejét. >> Csak a fejét, pontosan.

698
00:54:41,060 --> 00:54:44,620
És miért kell mod egyáltalán sorba állítása?

699
00:54:44,620 --> 00:54:48,830
Ha egy olyan helyzet, amelyben azt kellett mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Ha cucc terek, mint a terek 1 és 2,

701
00:54:53,630 --> 00:54:55,950
és akkor van szükség, hogy adjunk valamit 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Igen, pontosan. Tehát, ha a fejed mutató a legvégén,

703
00:55:02,570 --> 00:55:14,210
vagy ha a méret és a fej nagyobb, vagy inkább fog köré a sorban.

704
00:55:14,210 --> 00:55:17,830
>> Tehát ebben a helyzetben, hogy mi van ide a dián most,

705
00:55:17,830 --> 00:55:24,370
ha akarok sorba állításához valamit most,

706
00:55:24,370 --> 00:55:31,110
azt akarjuk, hogy sorba állításához valamit index 0-ra.

707
00:55:31,110 --> 00:55:35,450
Tehát, ha megnézzük, ha az 50 megy, és arra kérem sorba állítása 50,

708
00:55:35,450 --> 00:55:40,840
megy ott alul. Magától index 0.

709
00:55:40,840 --> 00:55:44,160
Ez helyettesíti a "hi", hogy már dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Ne vigyázni, hogy a dequeue már?

711
00:55:46,210 --> 00:55:50,550
Miért csinál semmit a fejét sorba állítása?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, szóval nem módosítja a fejét, sajnálom.

713
00:55:55,770 --> 00:56:02,310
De meg kell, hogy használja a mod operátor amikor eléréséhez

714
00:56:02,310 --> 00:56:04,250
az elem kívánt sorba állításához, amikor eléréséhez

715
00:56:04,250 --> 00:56:06,960
A következő elem a sorban.

716
00:56:06,960 --> 00:56:10,960
[Basil] nem tettem ezt, és kaptam "siker" ott.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Ó, értem, amit mondasz.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Szóval Nem mondta - csak tette q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Igen. Én csak átállt, én nem csináltam semmit a fejét.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Te valójában nem kell állítani a fejét, hogy bármi lehet,

721
00:56:24,300 --> 00:56:31,650
de ha index a húrok tömb,

722
00:56:31,650 --> 00:56:39,500
valóban el kell menni előre, és kiszámítja, ahol a következő elem,

723
00:56:39,500 --> 00:56:44,230
mert withe a verem, a következő elem a verem mindig

724
00:56:44,230 --> 00:56:48,740
-nél az index megfelelő méretűre.

725
00:56:48,740 --> 00:56:55,850
Ha megnézzük vissza a mi stack push-funkció,

726
00:56:55,850 --> 00:57:03,100
tudtunk mindig pengetés a mi új elem jobbra index méretét.

727
00:57:03,100 --> 00:57:06,710
Mivel a sorban, nem tehetjük, hogy a

728
00:57:06,710 --> 00:57:10,340
mert ha már itt vagyunk ezen a helyzeten,

729
00:57:10,340 --> 00:57:18,130
ha enqueued 50 új karakterlánc menne jobbra strings [1]

730
00:57:18,130 --> 00:57:20,540
amit nem akarok.

731
00:57:20,540 --> 00:57:41,200
Azt szeretnénk, hogy az új szöveg megy az index 0-ra.

732
00:57:41,200 --> 00:57:44,320
>> Van valaki - igen? [Diák] Nekem van egy kérdés, de ez nem igazán kapcsolódik.

733
00:57:44,320 --> 00:57:48,160
Mit jelent az, ha valaki csak felhívja ilyesmi pred pointer?

734
00:57:48,160 --> 00:57:51,260
Mi az, hogy a név rövid? Tudom, hogy ez csak egy név.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pointer? Lássuk. Milyen összefüggésben?

736
00:57:59,110 --> 00:58:01,790
[Student] Ez volt a betét. Megkérdezhetem később, ha szeretné

737
00:58:01,790 --> 00:58:03,920
mert ez nem igazán kapcsolódik, de én csak -

738
00:58:03,920 --> 00:58:07,300
[Hardison] A Dávid betét kódot előadás?

739
00:58:07,300 --> 00:58:10,860
Mi lehet húzni, hogy az, és beszélni.

740
00:58:10,860 --> 00:58:15,550
Megbeszéljük, hogy legközelebb, ha egyszer eljutunk linkelt listákat.

741
00:58:15,550 --> 00:58:21,440
>> Szóval nagyon gyorsan nézd meg mi a sorba állítása funkció néz ki.

742
00:58:21,440 --> 00:58:26,530
Mi volt az első dolog, hogy az emberek próbálkozott a sorba állítása sorban? Ebbe a sorba?

743
00:58:26,530 --> 00:58:29,960
Hasonló a mit tettél verem rámenős.

744
00:58:29,960 --> 00:58:32,080
Mit csináltál, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, érthetetlen]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Pontosan. Ha a (q.size == kapacitás) -

747
00:58:45,700 --> 00:58:54,720
Meg kell tenni a zárójelek a megfelelő helyen - return false.

748
00:58:54,720 --> 00:59:01,370
Nagyítás egy kicsit. Oké.

749
00:59:01,370 --> 00:59:03,800
Most mi lesz a következő dolog, amit meg kellett tennie?

750
00:59:03,800 --> 00:59:11,370
Csakúgy, mint a verem, és ki a legjobb helyen.

751
00:59:11,370 --> 00:59:16,010
És mi volt a jó helyen beszúrni ezt?

752
00:59:16,010 --> 00:59:23,170
A verem volt index méretét, ezzel ez nem ennyire.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Van q.head--vagy - >> q.strings? >> Igen.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPACITÁS]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Valószínűleg szeretnénk, hogy ez a zárójelek

756
00:59:42,740 --> 00:59:48,830
hogy mi vagyunk egyre a megfelelő elsőbbséget, és hogy ez cleart mindenkinek.

757
00:59:48,830 --> 00:59:55,800
És állítsa be, hogy egyenlő? >> To str? >> To str. Remek.

758
00:59:55,800 --> 01:00:00,160
És most mi az utolsó dolog, amit meg kell csinálni?

759
01:00:00,160 --> 01:00:06,780
Csakúgy, mint tettük a veremben. >> Lépésköz a méret? >> Lépésköz a méretet.

760
01:00:06,780 --> 01:00:13,830
Boom. És aztán, mivel az indító kódot csak vissza false alapértelmezés szerint,

761
01:00:13,830 --> 01:00:27,460
szeretnénk megváltoztatni ezt true ha minden megy keresztül, és minden jól megy.

762
01:00:27,460 --> 01:00:33,050
Rendben van. Ez rengeteg információ részben.

763
01:00:33,050 --> 01:00:39,480
Nem vagyunk teljesen vége. Azt akarjuk, hogy beszélni nagyon gyorsan mintegy egyszeres linkelt listákat.

764
01:00:39,480 --> 01:00:44,010
Majd, hogy ezt ki, így mehetünk vissza később.

765
01:00:44,010 --> 01:00:50,850
De menjünk vissza a bemutatót, mindössze néhány diák.

766
01:00:50,850 --> 01:00:53,790
Tehát sorba állítása a TODO, most megcsináltuk.

767
01:00:53,790 --> 01:00:57,430
>> Most vessünk egy pillantást egyszeres linkelt listákat.

768
01:00:57,430 --> 01:01:00,040
Beszéltünk ezekről egy kicsit több előadás.

769
01:01:00,040 --> 01:01:02,540
Hányan vagytok látta, hogy a demo, ahol volt az emberek

770
01:01:02,540 --> 01:01:08,220
félszegen mutat egymással és gazdaság számokat? >> Voltam ebben.

771
01:01:08,220 --> 01:01:16,620
>> Mit gondoltok, srácok? Vajon, hogy remélhetőleg demisztifikálják ezek egy kicsit?

772
01:01:16,620 --> 01:01:25,990
A listát, kiderül, hogy kezeljük az ilyen típusú, hogy fogunk hívni egy csomópont.

773
01:01:25,990 --> 01:01:32,520
Mivel a sorban, és a verem volt struktúrákat, hogy mi lenne szükséges sorban verem,

774
01:01:32,520 --> 01:01:34,860
mi volt ezen új sorban stack típusú,

775
01:01:34,860 --> 01:01:39,240
itt egy lista tényleg csak épül fel egy csomó csomópont.

776
01:01:39,240 --> 01:01:45,920
Ugyanilyen módon, hogy a húrok csak egy csomó karakter összes sorakoznak egymás mellett.

777
01:01:45,920 --> 01:01:50,650
A láncolt lista csak egy csomópont egy másik csomópont és egy másik csomópont és egy másik csomópont.

778
01:01:50,650 --> 01:01:55,080
És ahelyett, szétzúzva az összes csomópont össze, és tárolja őket összefüggően

779
01:01:55,080 --> 01:01:58,090
rendben egymás mellett a memóriában,

780
01:01:58,090 --> 01:02:04,470
tekintettel a következő mutató lehetővé teszi számunkra, hogy tárolja a csomópontok bárhol, véletlenszerűen.

781
01:02:04,470 --> 01:02:10,500
És akkor milyen huzal őket össze, hogy pont az egyik a másikra.

782
01:02:10,500 --> 01:02:15,850
>> És mi volt az a nagy előnye, hogy ez már több mint egy tömb?

783
01:02:15,850 --> 01:02:21,680
Over tároló minden összefüggően csak megragadt egymás mellett?

784
01:02:21,680 --> 01:02:24,190
Emlékszel? Igen? >> Dinamikus memória kiosztás?

785
01:02:24,190 --> 01:02:27,220
>> Dinamikus memória kiosztás milyen értelemben?

786
01:02:27,220 --> 01:02:31,780
[Student] Az, hogy tudja, hogy ez nagyobb és nem kell mozgatni az egész tömb?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Pontosan. Tehát egy sor, ha azt szeretné, hogy egy új elem a közepén,

788
01:02:40,940 --> 01:02:45,320
meg kell váltani mindent, hogy helyet.

789
01:02:45,320 --> 01:02:47,880
És ahogy beszélgettünk a sorban,

790
01:02:47,880 --> 01:02:50,080
ezért tartjuk, hogy a fej mutató,

791
01:02:50,080 --> 01:02:52,050
úgy, hogy nem vagyunk állandóan változó dolgokat.

792
01:02:52,050 --> 01:02:54,520
Mert ez lesz drága, ha van egy nagy tömb

793
01:02:54,520 --> 01:02:57,130
és te állandóan csinál ilyen véletlen beszúrások.

794
01:02:57,130 --> 01:03:00,820
Mivel a listáját, mindössze annyit kell tennie, hogy dobja azt egy új csomópontot,

795
01:03:00,820 --> 01:03:06,330
állítsa be a mutató, és kész.

796
01:03:06,330 --> 01:03:10,940
Mi a szar van ezzel?

797
01:03:10,940 --> 01:03:16,830
Eltekintve attól a ténytől, hogy ez nem olyan könnyű vele dolgozni, mint egy tömb? Igen?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nos, azt hiszem, hogy ez sokkal nehezebb elérni egy adott elem a láncolt lista?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Nem lehet csak ugrani egy tetszőleges elem a közepén a láncolt lista.

800
01:03:30,470 --> 01:03:33,800
Hogyan kell csinálni helyette? >> Meg kell lépni az egész dolog.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Igen. Meg kell, hogy menjen át egy olyan időpontban, az egyik egy időben.

802
01:03:35,660 --> 01:03:38,480
Ez egy hatalmas - ez a fájdalom.

803
01:03:38,480 --> 01:03:41,550
Mi a másik - van még egy bukás e.

804
01:03:41,550 --> 01:03:45,340
[Basil] Nem mehetsz előre és hátra? El kell menni egy irányba?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Igen. Szóval hogyan lehet megoldani, hogy néha?

806
01:03:48,570 --> 01:03:53,370
[Basil] Kétszer kapcsolt listák? >> Pontosan. Vannak kétszeresen láncolt listák.

807
01:03:53,370 --> 01:03:55,540
Vannak - Tessék?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Ez ugyanaz, mint a pred dolog, hogy -

809
01:03:57,620 --> 01:04:01,090
Csak eszembe jutott, nem az, hogy mi a pred dolog?

810
01:04:01,090 --> 01:04:05,850
Hát nem között kétszeresen és egyedül?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Nézzük meg, mit csinál.

812
01:04:10,020 --> 01:04:15,760
Szóval itt vagyunk. Itt a lista kódot.

813
01:04:15,760 --> 01:04:25,620
Itt van predptr, itt. Ez mit beszélsz?

814
01:04:25,620 --> 01:04:30,750
Szóval ez volt - ő felszabadítja a listát, és ő próbál tárolni egy mutatót is.

815
01:04:30,750 --> 01:04:35,000
Ez nem a kétszeresen, egyenként kapcsolt listák.

816
01:04:35,000 --> 01:04:40,090
Beszélhetünk többet erről később, mivel ez beszél felszabadítja a lista

817
01:04:40,090 --> 01:04:42,900
és én meg akarom mutatni néhány más dolgot először.

818
01:04:42,900 --> 01:04:51,480
de ez csak - ez emlékezés értékét ptr

819
01:04:51,480 --> 01:04:54,170
[Student] Ó, ez elõzõ mutató? >> Igen.

820
01:04:54,170 --> 01:05:04,070
Ahhoz, hogy meg tudjuk majd növelni ptr magát, mielőtt majd ingyen, mi predptr van.

821
01:05:04,070 --> 01:05:09,130
Mert nem tudunk szabad ptr majd hívja ptr = ptr következő, ugye?

822
01:05:09,130 --> 01:05:11,260
Ez rossz lenne.

823
01:05:11,260 --> 01:05:20,940
Tehát lássuk, vissza ezt a fickót.

824
01:05:20,940 --> 01:05:23,900
>> A másik rossz dolog listákat, hogy míg egy sor

825
01:05:23,900 --> 01:05:26,520
már csak mind maguk az elemek halmozott egymás mellett,

826
01:05:26,520 --> 01:05:29,050
Itt mi is bevezette ezt a mutatót.

827
01:05:29,050 --> 01:05:34,060
Szóval van egy újabb darab a memória, hogy mi, hogy használja

828
01:05:34,060 --> 01:05:37,910
minden eleme, hogy mi tárolja a listában.

829
01:05:37,910 --> 01:05:40,030
Kapunk rugalmasságot, de jön áron.

830
01:05:40,030 --> 01:05:42,230
Jön ezúttal költséget,

831
01:05:42,230 --> 01:05:45,270
és jön-val ezt a memóriát költséget is.

832
01:05:45,270 --> 01:05:47,800
Az idő abban az értelemben, hogy most megy keresztül minden elem a tömbben

833
01:05:47,800 --> 01:05:58,670
hogy megtalálja az egyik az index 10, vagy lett volna index 10 egy tömbben.

834
01:05:58,670 --> 01:06:01,230
>> Csak nagyon gyorsan, amikor diagram ki ezeket a listákat,

835
01:06:01,230 --> 01:06:05,980
tipikusan tartjuk be a fejét a lista vagy az első mutató a lista

836
01:06:05,980 --> 01:06:08,010
és vegye figyelembe, hogy ez egy igazi mutató.

837
01:06:08,010 --> 01:06:11,100
Ez csak 4 byte. Ez nem a tényleges csomópont is.

838
01:06:11,100 --> 01:06:17,120
Így látod, hogy nem int értékkel benne, nincs jövő pointer benne.

839
01:06:17,120 --> 01:06:20,790
Ez szó szerint csak egy mutató.

840
01:06:20,790 --> 01:06:23,550
Meg fog mutatni valamit, ami a tényleges csomópont struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] A mutató az úgynevezett csomópont? >> Ez - no. Ez a mutató valamit típusú csomópont.

842
01:06:28,480 --> 01:06:32,540
Ez a mutató egy node struct. >> Ó, oké.

843
01:06:32,540 --> 01:06:36,870
Diagram a bal oldalon, kód a jobb oldalon.

844
01:06:36,870 --> 01:06:42,190
Mi meg azt, hogy null, ami egy jó módja annak, hogy kezdeni.

845
01:06:42,190 --> 01:06:49,850
Ha a diagram, akkor sem írni, mint nulla, vagy teszel egy sort rajta tetszik.

846
01:06:49,850 --> 01:06:53,910
>> Az egyik legegyszerűbb módja, hogy dolgozni listákat,

847
01:06:53,910 --> 01:06:57,430
és kérünk még mind a előtag és hozzáfűzni, hogy a különbség a kettő között,

848
01:06:57,430 --> 01:07:01,320
de elé rakva határozottan könnyebb.

849
01:07:01,320 --> 01:07:05,790
Ha a neve elé, ez az, ahol - ha előtag (7),

850
01:07:05,790 --> 01:07:10,050
megy, és hozza létre a node struct

851
01:07:10,050 --> 01:07:13,870
és állítsa először mutasson rá, mert most, hiszen fűz azt,

852
01:07:13,870 --> 01:07:17,240
ez lesz az a lista elején.

853
01:07:17,240 --> 01:07:22,540
Ha előtag (3), hogy létrehoz egy másik csomópont, de most 3 jön 7-e előtt.

854
01:07:22,540 --> 01:07:31,130
Szóval lényegében toló dolgokat rá a listára.

855
01:07:31,130 --> 01:07:34,720
Most láthatjuk, hogy előtag, néha az emberek hívják push,

856
01:07:34,720 --> 01:07:39,600
mert te rámenős új elem rá a listára.

857
01:07:39,600 --> 01:07:43,270
Ez is könnyen törölheti elején egy listát.

858
01:07:43,270 --> 01:07:45,650
Így az emberek gyakran hívják, hogy a pop.

859
01:07:45,650 --> 01:07:52,200
És ily módon, akkor emulálni egy köteg segítségével láncolt lista.

860
01:07:52,200 --> 01:07:57,880
Hoppá. Sajnáljuk, de most mi bekerülni append. Tehát itt fűz (7), most előtag (3).

861
01:07:57,880 --> 01:08:02,600
Ha fűz valami mást fel ezt a listát, ha fűz (4),

862
01:08:02,600 --> 01:08:06,540
akkor volna 4, majd 3, majd 7.

863
01:08:06,540 --> 01:08:14,220
Akkor tudnánk pop és távolítsa el a 4-eltávolítás 3, 7 eltávolítás.

864
01:08:14,220 --> 01:08:16,500
Gyakran inkább intuitív módon gondolni ezt a hozzáfűző.

865
01:08:16,500 --> 01:08:20,310
Szóval ábrázolt ki, milyen lenne kinézni a hozzáfűzni itt.

866
01:08:20,310 --> 01:08:23,380
Itt mellékelt (7) nem néz másképp

867
01:08:23,380 --> 01:08:25,160
mert csak egy elem a listában.

868
01:08:25,160 --> 01:08:28,620
És hozzáfűző (3) mondja a végén.

869
01:08:28,620 --> 01:08:31,020
Talán láthatjuk most a trükköt append

870
01:08:31,020 --> 01:08:36,600
az, hogy mivel csak annyit tudunk, ha a lista elején van,

871
01:08:36,600 --> 01:08:39,450
hozzáfűzni egy listát kell járni végig a listán

872
01:08:39,450 --> 01:08:46,500
hogy a végére, megáll, majd építeni a csomópontot és pengetés le mindent.

873
01:08:46,500 --> 01:08:50,590
Kösse be az összes dolgot fel.

874
01:08:50,590 --> 01:08:55,170
Tehát előtag, mint mi csak szakadt ezen keresztül nagyon gyorsan,

875
01:08:55,170 --> 01:08:58,170
ha neve elé egy listát, ez elég egyszerű.

876
01:08:58,170 --> 01:09:02,960
>> Azt, hogy az új csomópont, magában néhány dinamikus memória kiosztás.

877
01:09:02,960 --> 01:09:09,830
Tehát itt vagyunk, hogy egy csomópont struct használatával malloc.

878
01:09:09,830 --> 01:09:14,710
Szóval malloc mi használ, mert ez lesz félretett memória nekünk a későbbi

879
01:09:14,710 --> 01:09:20,350
mert nem akarjuk, hogy ez - azt szeretné, hogy ez memóriát fennmaradhatnak hosszú ideig.

880
01:09:20,350 --> 01:09:25,350
És kapunk egy mutatót a helyet a memóriában, hogy csak különítettek el.

881
01:09:25,350 --> 01:09:29,260
Az általunk használt méretű csomópont nem összeadja a mezőket.

882
01:09:29,260 --> 01:09:31,899
Nem kézzel létre a byte-ok száma,

883
01:09:31,899 --> 01:09:39,750
ehelyett használjuk sizeof, hogy tudjuk, mi rá a megfelelő számú bájt.

884
01:09:39,750 --> 01:09:43,660
Gondoskodunk arról, hogy tesztelje, hogy a malloc hívás sikerült.

885
01:09:43,660 --> 01:09:47,939
Ez az, amit akarsz általában.

886
01:09:47,939 --> 01:09:52,590
A modern gépek, kifogy a memória nem valami könnyű

887
01:09:52,590 --> 01:09:56,610
hacsak nem kiosztása egy csomó dolgot, és így egy hatalmas lista,

888
01:09:56,610 --> 01:10:02,220
de ha építünk dolgokat, mondjuk, mint egy iPhone vagy Android,

889
01:10:02,220 --> 01:10:05,230
Önnek korlátozott memória-erőforrásokat, különösen, ha csinálsz valamit intenzív.

890
01:10:05,230 --> 01:10:08,300
Szóval ez jó, hogy a gyakorlatban.

891
01:10:08,300 --> 01:10:10,510
>> Figyeljük meg, hogy én is használtam egy pár különböző funkciók ide

892
01:10:10,510 --> 01:10:12,880
, amit láttam, hogy a fajta új.

893
01:10:12,880 --> 01:10:15,870
Szóval fprintf olyan, mint printf

894
01:10:15,870 --> 01:10:21,320
kivéve az első argumentum a patak, amelyre át szeretnénk nyomtatni.

895
01:10:21,320 --> 01:10:23,900
Ebben az esetben szeretnénk nyomtatni a standard hiba húr

896
01:10:23,900 --> 01:10:29,410
amely eltér a szabványos outstream.

897
01:10:29,410 --> 01:10:31,620
Alapértelmezés szerint ez azt mutatja fel, ugyanazon a helyen.

898
01:10:31,620 --> 01:10:34,600
Azt is kiírja a terminál, de akkor -

899
01:10:34,600 --> 01:10:38,790
használja ezeket a parancsokat értesült, az átirányítás technikák

900
01:10:38,790 --> 01:10:42,290
Ön értesült a Tommy videót a problémája készlet 4, tudod irányítani

901
01:10:42,290 --> 01:10:47,900
különböző területeit, majd kilép, itt, kilép a program.

902
01:10:47,900 --> 01:10:50,440
Ez lényegében, mint a visszatérő fő,

903
01:10:50,440 --> 01:10:53,600
kivéve az általunk használt exit mert itt visszatérés nem fog csinálni semmit.

904
01:10:53,600 --> 01:10:57,140
Nem vagyunk a fő, így a visszatérés nem jön ki a program, mint szeretnénk.

905
01:10:57,140 --> 01:11:03,020
Ezért használjuk a kilépés funkciót és adja meg a hibakódot.

906
01:11:03,020 --> 01:11:11,890
Akkor itt mi meg az új csomópont értékét területén, annak i mező megegyezik i, és aztán kösse fel.

907
01:11:11,890 --> 01:11:15,530
Mi meg az új csomópont mellett mutatót pont az első,

908
01:11:15,530 --> 01:11:20,460
majd az első lesz most mutatnak az új csomópontot.

909
01:11:20,460 --> 01:11:25,120
Ezek az első sornyi kódot, mi valójában építése az új csomópontot.

910
01:11:25,120 --> 01:11:27,280
Nem az utolsó két sor a funkció, hanem az első is.

911
01:11:27,280 --> 01:11:30,290
Tudod valójában húzza ki egy funkciót, egy segítő funkció.

912
01:11:30,290 --> 01:11:32,560
Ez gyakran, amit csinálok, azt húzza ki egy funkciót,

913
01:11:32,560 --> 01:11:36,040
Úgy hívom valami ilyesmit épít csomópont,

914
01:11:36,040 --> 01:11:40,410
és hogy tartja a előtag funkció elég kicsi, csak 3 sor majd.

915
01:11:40,410 --> 01:11:48,710
Azt, hogy a hívás az én épít csomópont funkciót, aztán drót mindent.

916
01:11:48,710 --> 01:11:51,970
>> Az utolsó dolog, amit szeretnék megmutatni neked,

917
01:11:51,970 --> 01:11:54,030
és én hagyom, hogy ezt append és minden, ami a saját,

918
01:11:54,030 --> 01:11:57,500
hogy hogyan navigálhat egy listát.

919
01:11:57,500 --> 01:12:00,780
Van egy csomó különböző módon navigálhat egy listát.

920
01:12:00,780 --> 01:12:03,140
Ebben az esetben fogjuk találni a hosszú lista.

921
01:12:03,140 --> 01:12:06,570
Szóval kezdjük hossz = 0.

922
01:12:06,570 --> 01:12:11,580
Ez nagyon hasonlít az írásban strlen egy string.

923
01:12:11,580 --> 01:12:17,780
Ez az, amit akarok mutatni neked, ez a for ciklus itt.

924
01:12:17,780 --> 01:12:23,530
Úgy néz ki, kicsit funky, ez nem a szokásos int i = 0, i <függetlenül, i + +.

925
01:12:23,530 --> 01:12:34,920
Ehelyett ez inicializálja a változót n, hogy az elején a listán.

926
01:12:34,920 --> 01:12:40,620
És míg a iterator változó nem nulla, akkor folytasd.

927
01:12:40,620 --> 01:12:46,340
Ennek oka, hogy megegyezés, a végén a mi lista null lesz.

928
01:12:46,340 --> 01:12:48,770
És akkor a növekmény helyett csinál + +,

929
01:12:48,770 --> 01:12:57,010
A láncolt lista megfelelője + + n = n-> next.

930
01:12:57,010 --> 01:13:00,410
>> Elárulok töltse ki a hézagokat itt, mert kifogytunk az időből.

931
01:13:00,410 --> 01:13:09,300
De ezt tartsd szem előtt, ahogy dolgozik a spellr psets.

932
01:13:09,300 --> 01:13:11,650
Csatolt listák, ha végrehajtása hash tábla,

933
01:13:11,650 --> 01:13:14,010
biztosan jön nagyon praktikus.

934
01:13:14,010 --> 01:13:21,780
És miután ezt a kifejezést a ciklusok alatt a dolgok, hogy az élet sokkal könnyebb, remélhetőleg.

935
01:13:21,780 --> 01:13:25,910
Bármilyen kérdése van, gyorsan?

936
01:13:25,910 --> 01:13:28,920
[Sam] Fogsz küldje el a kitöltött sll és sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Igen. Küldök ki kitöltött diák és befejezett sll stack és queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]