1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [6 §: vähemmän mukavaksi]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvardin yliopisto]

3
00:00:05,040 --> 00:00:07,320
[Tämä on CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Selvä. Tervetuloa 6 §.

5
00:00:11,840 --> 00:00:14,690
Tällä viikolla aiomme puhua tietorakenteita kohdassa,

6
00:00:14,690 --> 00:00:19,780
pääasiassa koska tällä viikolla ongelman asetettu spellr

7
00:00:19,780 --> 00:00:24,410
tekee koko joukko erilaisia ​​tietorakenteen etsintä.

8
00:00:24,410 --> 00:00:26,520
On olemassa joukko erilaisia ​​tapoja voit mennä ongelman asetettu,

9
00:00:26,520 --> 00:00:31,570
ja enemmän tietorakenteet tiedät, enemmän hienoja asioita voit tehdä.

10
00:00:31,570 --> 00:00:34,990
>> Joten aloita. Ensin aiomme puhua pinoja,

11
00:00:34,990 --> 00:00:37,530
pino ja jono tietorakenteita että aiomme puhua.

12
00:00:37,530 --> 00:00:40,560
Pinot ja jonot ovat todella hyödyllisiä, kun alamme puhua kuvaajia,

13
00:00:40,560 --> 00:00:44,390
joita emme aio tehdä niin paljon juuri nyt.

14
00:00:44,390 --> 00:00:52,820
Mutta he todella hyvä ymmärtää yksi iso perustavanlaatuinen tietorakenteita CS.

15
00:00:52,820 --> 00:00:54,880
Kuvaus ongelmasta asetettu spesifikaatio,

16
00:00:54,880 --> 00:00:59,260
jos vedät sen ylös, kertoo pinot kuin sukua

17
00:00:59,260 --> 00:01:05,239
kasa dining tarjottimia, että sinulla on kahvilassa ruokasalia

18
00:01:05,239 --> 00:01:09,680
missä milloin ruokailu henkilökunta tulee ja tuo ruokailu lokerot jälkeen he siivonnut niitä,

19
00:01:09,680 --> 00:01:12,000
he pinoa ne päällekkäin muiden.

20
00:01:12,000 --> 00:01:15,050
Ja sitten kun lapset tulevat saamaan ruokaa,

21
00:01:15,050 --> 00:01:19,490
ne vetää tarjottimet pois ensin alkuun yksi, sitten yksi alla, sitten yksi alle.

22
00:01:19,490 --> 00:01:25,190
Eli käytännössä ensimmäinen lokero, ruokailu henkilökunta laittaa alas on viimeinen, joka saa ottaa pois.

23
00:01:25,190 --> 00:01:32,330
Viimeinen että ruokailu henkilökunta laittaa on ensimmäinen, joka saa ottaa pois päivälliselle.

24
00:01:32,330 --> 00:01:38,100
Vuonna ongelma setin spec, jonka voit ladata, jos et ole jo,

25
00:01:38,100 --> 00:01:46,730
puhumme mallintaa pino data stucture käyttämästä tällaista struct.

26
00:01:46,730 --> 00:01:51,070
>> Joten mitä meillä täällä, tämä on samanlainen kuin mitä oli esitetty luento,

27
00:01:51,070 --> 00:01:58,120
paitsi luento esitimme tätä ints eikä char * s.

28
00:01:58,120 --> 00:02:06,250
Tämä tulee olemaan pino, joka tallentaa mitä?

29
00:02:06,250 --> 00:02:09,009
Daniel? Mitä me säilytykseen tässä pinossa?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Olemme tallentamiseen merkkijonoja tässä pinossa, tarkalleen.

31
00:02:15,260 --> 00:02:20,950
Kaikki mitä tarvitset, jotta voidaan luoda pino on matriisi

32
00:02:20,950 --> 00:02:23,920
tietyn kapasiteetin, joka tässä tapauksessa,

33
00:02:23,920 --> 00:02:28,020
kapasiteetti tulee olemaan kaikissa lakit, koska se on jatkuvaa.

34
00:02:28,020 --> 00:02:36,340
Ja sitten lisäksi jono, meidän ei tarvitse seurata on nykyistä taulukon koko.

35
00:02:36,340 --> 00:02:38,980
Yksi asia huomata tässä, että on tavallaan viileä

36
00:02:38,980 --> 00:02:47,060
on, että olemme perustetaan pinottu tietorakenne päälle toisen datarakenteen, jono.

37
00:02:47,060 --> 00:02:50,110
On olemassa erilaisia ​​tapoja toteuttaa pinoja.

38
00:02:50,110 --> 00:02:54,250
Emme tee sitä ihan vielä, mutta toivottavasti kun tekee linkitetyn-listan ongelmista,

39
00:02:54,250 --> 00:03:00,520
näet kuinka voit helposti toteuttaa pinon päälle linkitetty lista samoin.

40
00:03:00,520 --> 00:03:02,640
Mutta nyt, me kiinni ryhmät.

41
00:03:02,640 --> 00:03:06,350
Joten jälleen kaikki tarvitsemme erilaisia ​​ja meidän täytyy vain seurata taulukon koko.

42
00:03:06,350 --> 00:03:09,850
[Sam] Sorry, miksi se, että sanoit piipun päälle jouset?

43
00:03:09,850 --> 00:03:13,440
Minusta se tuntuu jouset ovat pinossa.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Joo. Luomme, viemme array tietorakenne -

45
00:03:16,790 --> 00:03:22,130
se on hyvä kysymys. Joten kysymys kuuluu, miksi ihmisiä, jotka katsovat tätä verkossa,

46
00:03:22,130 --> 00:03:24,140
Miksi me sanoa, että pino on päällä jouset,

47
00:03:24,140 --> 00:03:27,990
koska täällä se näyttää jouset ovat sisällä pino?

48
00:03:27,990 --> 00:03:31,050
Joka on täysin tapauksessa.

49
00:03:31,050 --> 00:03:34,660
Mitä viittasin oli että meillä array tietorakennetta.

50
00:03:34,660 --> 00:03:39,290
Meillä joukko char * s, tämä joukko merkkijonoja,

51
00:03:39,290 --> 00:03:45,300
ja aiomme lisätä että luodakseen pinottu tietorakennetta.

52
00:03:45,300 --> 00:03:48,620
>> Joten pino on hieman monimutkaisempi kuin array.

53
00:03:48,620 --> 00:03:51,890
Voimme käyttää array rakentaa pinon.

54
00:03:51,890 --> 00:03:55,810
Niin, että jos sanomme, että pino on rakennettu päälle array.

55
00:03:55,810 --> 00:04:02,510
Samoin kuten sanoin aiemmin, voimme rakentaa pino päälle linkitetty lista.

56
00:04:02,510 --> 00:04:04,960
Sen sijaan käyttää array pitää meidän elementtejä,

57
00:04:04,960 --> 00:04:10,070
voisimme käyttää linkitetty lista pitää meidän elementtejä ja rakentaa pino kiertää.

58
00:04:10,070 --> 00:04:12,420
Kävellään läpi pari esimerkkiä, katsomalla jotain koodia,

59
00:04:12,420 --> 00:04:14,960
nähdä, mitä todella tapahtuu täällä.

60
00:04:14,960 --> 00:04:23,400
Vasemmalla olen heittänyt mitä se pino struct näyttäisi muistissa

61
00:04:23,400 --> 00:04:28,330
jos kapasiteettia # määritelty olevan neljä.

62
00:04:28,330 --> 00:04:33,490
Meillä myös neljän elementin char * array.

63
00:04:33,490 --> 00:04:38,110
Meillä strings [0], merkkijonot [1], merkkijonot [2], merkkijonot [3],

64
00:04:38,110 --> 00:04:43,800
ja sitten se viimeinen tilaa meidän koko kokonaisluku.

65
00:04:43,800 --> 00:04:46,270
Onko tämä järkevää? Okei.

66
00:04:46,270 --> 00:04:48,790
Tämä on mitä tapahtuu, jos mitä teen oikealla,

67
00:04:48,790 --> 00:04:55,790
joka on minun koodi, on vain julistaa struct, pinottu struct nimeltään s.

68
00:04:55,790 --> 00:05:01,270
Tämä on mitä saamme. Siinä vahvistetaan tämä jalanjälki muistiin.

69
00:05:01,270 --> 00:05:05,590
Ensimmäinen kysymys on, mitä ovat sisältö pino struct?

70
00:05:05,590 --> 00:05:09,250
Juuri nyt he mitään, mutta he eivät täysin mitään.

71
00:05:09,250 --> 00:05:13,300
He tällaista roskaa. Meillä ei ole aavistustakaan mitä niissä.

72
00:05:13,300 --> 00:05:17,000
Kun me julistamme pino s, me vain heittää että alaspäin päälle muistin.

73
00:05:17,000 --> 00:05:19,840
Se on tavallaan kuin julistaa int i eikä alustamatta.

74
00:05:19,840 --> 00:05:21,730
Et tiedä mitä siellä. Voit lukea mitä siellä,

75
00:05:21,730 --> 00:05:27,690
mutta se ei ehkä erittäin hyödyllistä.

76
00:05:27,690 --> 00:05:32,680
Yksi asia, jonka haluat aina muistaa tehdä, on alustaa mitä täytyy alustaa.

77
00:05:32,680 --> 00:05:35,820
Tässä tapauksessa aiomme alustaa koon nollaksi,

78
00:05:35,820 --> 00:05:39,960
koska tulee osoittautua erittäin tärkeää meille.

79
00:05:39,960 --> 00:05:43,450
Voisimme mennä eteenpäin ja alustaa kaikki osoittimet, kaikki char * s,

80
00:05:43,450 --> 00:05:49,670
olevan joitakin ymmärrettäviä arvo todennäköisesti null.

81
00:05:49,670 --> 00:05:58,270
Mutta se ei ole täysin välttämätöntä, että teemme niin.

82
00:05:58,270 --> 00:06:04,200
>> Nyt, kaksi operaatiot pinot ovat?

83
00:06:04,200 --> 00:06:07,610
Joku muistan luento mitä tehdä pinot? Kyllä?

84
00:06:07,610 --> 00:06:09,700
[Stella] Pushing ja popping? >> Aivan.

85
00:06:09,700 --> 00:06:13,810
Pushing ja popping ovat kaksi tärkeintä toimintansa pinot.

86
00:06:13,810 --> 00:06:17,060
Ja mitä push tehdä? >> Siinä jotain päälle alkuun

87
00:06:17,060 --> 00:06:19,300
pinon, ja sitten huikeassa ottaa sen pois.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Aivan. Joten työntää työntää jotain päälle pinon.

89
00:06:23,150 --> 00:06:27,700
Se on kuin dining henkilökunnan käyttöön ruokailu lokero alas laskuri.

90
00:06:27,700 --> 00:06:33,630
Ja popping vie ruokailu lokero pois pinosta.

91
00:06:33,630 --> 00:06:36,460
Kävellään läpi pari esimerkkiä siitä, mitä tapahtuu

92
00:06:36,460 --> 00:06:39,720
kun ajaa asioita pinoon.

93
00:06:39,720 --> 00:06:45,110
Jos me ajaa merkkijono "Hello" päälle meidän pinoon,

94
00:06:45,110 --> 00:06:49,760
Tämä on mitä kaavio näyttäisi nyt.

95
00:06:49,760 --> 00:06:53,410
Katso mitä tapahtuu?

96
00:06:53,410 --> 00:06:56,530
Me työnnetään ensimmäinen osa meidän merkkijonojen joukko

97
00:06:56,530 --> 00:07:01,420
ja me kasvattaneet meidän koko määrä on 1.

98
00:07:01,420 --> 00:07:05,340
Joten jos katsomme ero dioja, täällä oli 0, tässä ennen push.

99
00:07:05,340 --> 00:07:08,690
Tässä on jälkeen push.

100
00:07:08,690 --> 00:07:13,460
Ennen push jälkeen push.

101
00:07:13,460 --> 00:07:16,860
Ja nyt meillä on yksi osa meidän pinoon.

102
00:07:16,860 --> 00:07:20,970
Se on merkkijono "hello", ja se on siinä.

103
00:07:20,970 --> 00:07:24,440
Kaikki muu on array, meidän strings array, on edelleen roskaa.

104
00:07:24,440 --> 00:07:27,070
Emme ole alustettu sitä.

105
00:07:27,070 --> 00:07:29,410
Sanotaan työntää toisella merkkijonolla kiinni meidän pinoon.

106
00:07:29,410 --> 00:07:32,210
Aiomme paina "world" tällä kertaa.

107
00:07:32,210 --> 00:07:35,160
Joten voit nähdä "maailma" tässä menee päälle "Hei",

108
00:07:35,160 --> 00:07:40,040
ja koko määrä nousee 2.

109
00:07:40,040 --> 00:07:44,520
Nyt voimme työntää "CS50" ja että menemme päälle uudestaan.

110
00:07:44,520 --> 00:07:51,110
Jos menemme takaisin, voit nähdä, kuinka olemme kiire päälle pinon.

111
00:07:51,110 --> 00:07:53,320
Ja nyt saamme pop.

112
00:07:53,320 --> 00:07:58,910
Kun me piipahti jotain pois pinosta, mitä tapahtui?

113
00:07:58,910 --> 00:08:01,540
Kukaan näe eroa? Se on melko hienovarainen.

114
00:08:01,540 --> 00:08:05,810
[Opiskelija] koko. >> Joo, koko muuttui.

115
00:08:05,810 --> 00:08:09,040
>> Mitä muuta olisit odotetaan muuttuvan?

116
00:08:09,040 --> 00:08:14,280
[Opiskelija] jouset, too. >> Oikea. Strings liikaa.

117
00:08:14,280 --> 00:08:17,110
On käynyt ilmi, että kun teet näin,

118
00:08:17,110 --> 00:08:21,960
koska emme kopioimalla elementit meidän pinoon,

119
00:08:21,960 --> 00:08:24,670
me itse ei tarvitse tehdä mitään, me voimme vain käyttää kokoa

120
00:08:24,670 --> 00:08:28,630
seurata useita asioita meidän array

121
00:08:28,630 --> 00:08:33,780
niin että kun me pop uudestaan, uudestaan ​​me vain vähentääksesi meidän koko alas 1.

122
00:08:33,780 --> 00:08:39,440
Ei tarvitse itse mennä ja korvata mitään.

123
00:08:39,440 --> 00:08:41,710
Kind of funky.

124
00:08:41,710 --> 00:08:46,520
On käynyt ilmi, että me yleensä vain jättää asioita yksin, koska se on vähemmän työtä meidän tekevän.

125
00:08:46,520 --> 00:08:50,060
Jos meillä ei tarvitse mennä takaisin ja korvata jotain, niin miksi tehdä se?

126
00:08:50,060 --> 00:08:54,150
Joten kun pop kahdesti pois pinosta, tämä vain vähentääksesi kokoa pari kertaa.

127
00:08:54,150 --> 00:08:59,120
Ja vielä, tämä on vain siksi emme kopiointi asioita meidän pinoon.

128
00:08:59,120 --> 00:09:01,320
Kyllä? Menkää.

129
00:09:01,320 --> 00:09:04,460
[Student, käsittämätön] >> Ja mitä sitten tapahtuu, kun painat jotain taas?

130
00:09:04,460 --> 00:09:08,570
Kun painat jotain uudelleen, mihin se menee?

131
00:09:08,570 --> 00:09:12,390
Jos se menee, Basil? >> Merkkijonoiksi [1]? >> Oikea.

132
00:09:12,390 --> 00:09:14,530
Miksi ei mennä merkkijonot [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Koska unohdin, että oli mitään strings [1] ja [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Aivan. Meidän pino, lähinnä "unohti", että se oli tilalla mitään

135
00:09:24,040 --> 00:09:29,480
in strings [1] tai merkkijonot [2], joten kun me push "woot"

136
00:09:29,480 --> 00:09:36,670
se vain tuo sen osaksi elementin jouset [1].

137
00:09:36,670 --> 00:09:41,590
Onko kysymyksiä siitä, miten tämä toimii, perustasolla?

138
00:09:41,590 --> 00:09:45,160
[Sam] Joten tämä ei ole dynaaminen millään tavalla mitattuna määrä

139
00:09:45,160 --> 00:09:47,620
tai kannalta pinon koon?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Aivan. Tämä on - kohta oli se, että tämä ei ollut dynaamisesti growning pino.

141
00:09:56,750 --> 00:10:02,850
Tämä on pino joka mahtuu enimmillään neljä char * s, enintään neljä asiaa.

142
00:10:02,850 --> 00:10:07,580
Jos olisimme yrittää työntää viidesosa juttu, mitä luulet pitäisi tapahtua?

143
00:10:07,580 --> 00:10:11,870
[Opiskelijat, käsittämättömällä]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Aivan. On olemassa monia asioita, jotka voisi tapahtua.

145
00:10:14,600 --> 00:10:19,330
Se voisi seg vika, riippuen siitä mitä olimme -

146
00:10:19,330 --> 00:10:22,530
miten tarkalleen olimme täytäntöön back-end.

147
00:10:22,530 --> 00:10:31,740
Se voi korvata. Se voisi olla, että puskurin ylivuoto että puhuimme luokassa.

148
00:10:31,740 --> 00:10:35,240
Mikä olisi ilmeisin asia, joka saattaa olla päälle

149
00:10:35,240 --> 00:10:42,370
jos yritimme työntää ylimääräistä asia meidän pino?

150
00:10:42,370 --> 00:10:44,550
Joten te mainitsitte puskurin ylivuoto.

151
00:10:44,550 --> 00:10:47,870
Mikä voisi olla asia, joka saisi kirjoittanut yli tai polki

152
00:10:47,870 --> 00:10:52,320
jos me overflowed vahingossa yrittää työntää ylimääräinen juttu?

153
00:10:52,320 --> 00:10:54,730
[Daniel, käsittämätön] >> mahdollista.

154
00:10:54,730 --> 00:10:58,440
Mutta aluksi, mitä voisi tapahtua? Mitä jos me yritettiin neljäsosaa juttu?

155
00:10:58,440 --> 00:11:06,220
Se voi korvata koko, ainakin tällä muistilla kaavion että meillä.

156
00:11:06,220 --> 00:11:10,880
>> Vuonna Harjoitus eritelmä, joka on mitä aiomme olla täytäntöönpanon tänään,

157
00:11:10,880 --> 00:11:16,030
mitä haluamme tehdä, on vain palauttaa false.

158
00:11:16,030 --> 00:11:20,030
Meidän painalluksella tulee palauttaa boolean arvon,

159
00:11:20,030 --> 00:11:22,920
ja että boolean arvo on tosi, jos push onnistuu

160
00:11:22,920 --> 00:11:29,730
ja epätosi, jos emme voi työntää mitään muuta, koska pino on täynnä.

161
00:11:29,730 --> 00:11:33,620
Kävellään läpi vähän että koodia nyt.

162
00:11:33,620 --> 00:11:36,400
Tässä meidän push-toiminto.

163
00:11:36,400 --> 00:11:40,380
Meidän push toiminto pino aikoo ryhtyä merkkijono laittaa pinoon.

164
00:11:40,380 --> 00:11:45,820
Se tulee palauttaa true jos merkkijonon onnistuneesti ajanut

165
00:11:45,820 --> 00:11:51,820
pinoon ja vääriä toisin.

166
00:11:51,820 --> 00:11:59,740
Kaikki ehdotukset, mitä voisi olla hyvä ensimmäinen asia tehdä täällä?

167
00:11:59,740 --> 00:12:20,630
[Sam] Jos koko vastaa kapasiteetin palaa väärä?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Hyvää työtä.

169
00:12:23,320 --> 00:12:26,310
Jos koko on kapasiteettia, aiomme palauttaa false.

170
00:12:26,310 --> 00:12:29,270
Emme voi laittaa mitään muuta meidän pinoon.

171
00:12:29,270 --> 00:12:36,900
Muuten, haluamme laittaa jotain pinon päälle.

172
00:12:36,900 --> 00:12:41,670
Mikä on "päällimmäinen" aluksi?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Koko 0? >> Size 0.

174
00:12:43,650 --> 00:12:49,990
Mikä on päällimmäinen jälkeen on olemassa yksi asia pino? Missy, tiedätkö?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Koko on yksi, täsmälleen. Sinun pitää lisätä kokoa,

176
00:12:52,720 --> 00:13:01,690
ja joka kerta olet ottamassa uuden elementin indeksin koko jono.

177
00:13:01,690 --> 00:13:05,470
Voimme tehdä sen, että sellainen sutkaus, jos se on järkevää.

178
00:13:05,470 --> 00:13:11,910
Joten meillä meidän jouset array, aiomme käyttää sitä koko indeksin

179
00:13:11,910 --> 00:13:14,780
ja olemme juuri menossa tallentaa myös char * siellä.

180
00:13:14,780 --> 00:13:19,340
Huomaa kuinka Ei ole merkkijono kopiointi meneillään täällä,

181
00:13:19,340 --> 00:13:29,680
no dynaaminen jakaminen muistia?

182
00:13:29,680 --> 00:13:34,440
Ja sitten Missy esille mitä meidän on nyt tehtävä,

183
00:13:34,440 --> 00:13:40,570
koska olemme tallennettu merkkijono sopiva paikka array,

184
00:13:40,570 --> 00:13:49,230
ja hän sanoi, että meidän oli kasvattaa kokoa yhteen niin, että olemme valmiita seuraavaan push.

185
00:13:49,230 --> 00:13:53,950
Joten voimme tehdä sen s.size + +.

186
00:13:53,950 --> 00:13:59,330
Tässä vaiheessa olemme työnnetään meidän array. Mikä on viimeinen asia, meidän täytyy tehdä?

187
00:13:59,330 --> 00:14:10,110
[Student] return true. >> Return true.

188
00:14:10,110 --> 00:14:14,690
Joten se on melko yksinkertainen, melko yksinkertainen koodi. Ei liikaa.

189
00:14:14,690 --> 00:14:17,070
Kun olet kääritty pään ympärille miten pino toimii,

190
00:14:17,070 --> 00:14:21,910
Tämä on melko yksinkertainen toteuttaa.

191
00:14:21,910 --> 00:14:26,390
>> Nyt seuraava osa on popping merkkijono pois pinosta.

192
00:14:26,390 --> 00:14:29,410
Aion antaa te aikaa työstää tätä hieman.

193
00:14:29,410 --> 00:14:34,320
Se on melkein lähinnä päinvastainen mitä olemme tehneet täällä push.

194
00:14:34,320 --> 00:14:38,510
Mitä olen tehnyt on oikeastaan ​​- oho.

195
00:14:38,510 --> 00:14:48,160
Olen käynnistetty laite tänne, ja laite,

196
00:14:48,160 --> 00:14:53,600
Olen revitä ongelmaan asetettu 5 erittely.

197
00:14:53,600 --> 00:15:02,560
Jos me zoomata täällä, näemme olen klo cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Oletteko ladannut tämän koodin, joka sijaitsee täällä, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Selvä. Jos et ole tehnyt sitä, tee se nyt, todella nopeasti.

200
00:15:15,030 --> 00:15:22,130
Teen sen minun pääteikkunassa.

201
00:15:22,130 --> 00:15:25,090
Olen itse tehnyt sen tänne. Joo.

202
00:15:25,090 --> 00:15:34,730
Kyllä, Sam? >> Minulla on kysymys siitä, miksi sanoit s.string n suluissa size = str?

203
00:15:34,730 --> 00:15:42,910
Mikä on str? Onko se määritelty jossain aiemmin, tai - oh, in char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Kyllä, täsmälleen. Se oli argumentti. >> Ai, okei. Anteeksi.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Olemme täsmennetään merkkijono työntää sisään

206
00:15:49,470 --> 00:15:55,220
Toinen kysymys, joka voisi keksiä, että emme todellakaan puhu täällä oli

207
00:15:55,220 --> 00:15:58,810
otimme itsestäänselvyytenä, että meillä oli tämä muuttuja nimeltä s

208
00:15:58,810 --> 00:16:02,710
joka oli laajuudeltaan ja helposti meille.

209
00:16:02,710 --> 00:16:06,960
Otimme selvänä, että s oli tämä pino struct.

210
00:16:06,960 --> 00:16:08,930
Joten katson taaksepäin tätä push koodia,

211
00:16:08,930 --> 00:16:13,450
voit nähdä, että teemme juttuja tällä merkkijonolla että sai hyväksyttiin

212
00:16:13,450 --> 00:16:19,210
mutta sitten yhtäkkiä, me päästä s.size, kuten, jos ei s kotoisin?

213
00:16:19,210 --> 00:16:23,020
Vuonna koodin että olemme menossa katsomaan jaksossa arkisto

214
00:16:23,020 --> 00:16:27,100
ja sitten kamaa, että voit tehdä oman ongelman asettaa,

215
00:16:27,100 --> 00:16:32,440
teimme pino rakenteeseen sisältyvää globaaliin muuttujaan

216
00:16:32,440 --> 00:16:36,380
jotta voimme saada sitä meidän kaikkien eri toimintojen

217
00:16:36,380 --> 00:16:40,630
ilman käsin siirtää se ympäri ja kulkevat sen viittaus,

218
00:16:40,630 --> 00:16:44,870
tehdä kaikki tällaista tavaraa siihen.

219
00:16:44,870 --> 00:16:52,280
Olemme vain huijaa vähän, jos haluatte, tehdä asioita mukavampaa.

220
00:16:52,280 --> 00:16:57,430
Ja se on jotain teemme täällä, koska se on hauskaa, se on helpompaa.

221
00:16:57,430 --> 00:17:02,800
Usein näet ihmiset tekevät tätä, jos heillä on yksi suuri tietorakenne

222
00:17:02,800 --> 00:17:07,750
joka on parhaillaan liikennöi niiden ohjelmasta.

223
00:17:07,750 --> 00:17:09,560
>> Mennään takaisin päälle laitteeseen.

224
00:17:09,560 --> 00:17:15,240
Oliko kaikki onnistuneesti saada section6.zip?

225
00:17:15,240 --> 00:17:20,440
Kaikki pura se käyttäen unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Jos menet 6 § hakemisto -

227
00:17:27,200 --> 00:17:29,220
aah, koko paikka -

228
00:17:29,220 --> 00:17:32,840
ja sinä luetella, mitä on täällä, näet, että sinulla kolme. C-tiedostoja.

229
00:17:32,840 --> 00:17:38,350
Sinulla jono, SLL, joka on yksin-linkitetyn listan, ja pino.

230
00:17:38,350 --> 00:17:44,600
Jos avaat stack.c,

231
00:17:44,600 --> 00:17:47,330
voit nähdä, että meillä on tämä struct määritellyt meille,

232
00:17:47,330 --> 00:17:51,330
tarkka struct että me juuri puhuttu dioja.

233
00:17:51,330 --> 00:17:56,340
Meillä globaalia muuttujaa pinon,

234
00:17:56,340 --> 00:18:00,110
meillä myös push-toiminto,

235
00:18:00,110 --> 00:18:04,230
ja sitten meillä meidän pop-toiminto.

236
00:18:04,230 --> 00:18:08,320
Laitan koodin työntää takaisin ylös dian täällä,

237
00:18:08,320 --> 00:18:10,660
mutta mitä haluaisin te tehdä on, parhaan kykysi,

238
00:18:10,660 --> 00:18:13,790
mene ja toteuttaa pop-toiminto.

239
00:18:13,790 --> 00:18:18,480
Kun olet toteuttanut sen, voit kääntää tämän kanssa tehdä pino,

240
00:18:18,480 --> 00:18:22,540
ja sitten ajaa tuloksena pinon executable,

241
00:18:22,540 --> 00:18:28,390
ja joka jatkuu koko tämän testin koodin tänne se on pääasiassa.

242
00:18:28,390 --> 00:18:31,060
Ja tärkein huolehtii todella tehdä push ja pop puhelut

243
00:18:31,060 --> 00:18:33,220
ja varmistaa, että kaikki menee läpi kunnossa.

244
00:18:33,220 --> 00:18:36,820
Se myös alustaa pinon kokoa täällä

245
00:18:36,820 --> 00:18:39,780
joten sinun ei tarvitse huolehtia alustetaan se.

246
00:18:39,780 --> 00:18:42,310
Voit olettaa, että se on oikein alustettu

247
00:18:42,310 --> 00:18:48,000
mennessä kerran avaat sen pop-toiminto.

248
00:18:48,000 --> 00:18:53,530
Onko siinä järkeä?

249
00:18:53,530 --> 00:19:00,100
Joten tässä sitä mennään. On push koodin.

250
00:19:00,100 --> 00:19:13,210
Annan teille kaverit 5 tai 10 minuuttia.

251
00:19:13,210 --> 00:19:15,690
Ja jos sinulla on kysyttävää välivaiheen kun olet koodaus,

252
00:19:15,690 --> 00:19:17,710
kysy niitä ääneen.

253
00:19:17,710 --> 00:19:23,080
Joten jos saat kompastuskivi, kysykää.

254
00:19:23,080 --> 00:19:26,030
Haluaisin tietää, anna kaikki muutkin tietävät.

255
00:19:26,030 --> 00:19:28,160
Työ lähimmäistäsi liikaa.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Olemme juuri täytäntöön pop juuri nyt? >> Sujauta.

257
00:19:30,360 --> 00:19:34,200
Vaikka voit kopioida täytäntöönpanoa push jos haluat

258
00:19:34,200 --> 00:19:37,780
niin että testaus toimii.

259
00:19:37,780 --> 00:19:41,940
Koska se on vaikea testata asioita joutumassa -

260
00:19:41,940 --> 00:19:49,030
tai se on vaikea testata popping asioita ulos pino jos ei ole mitään pino aluksi.

261
00:19:49,030 --> 00:19:55,250
>> Mikä on pop tarkoitus palata? Elementti pinon päälle.

262
00:19:55,250 --> 00:20:01,260
Se pitäisi saada osa pois pinon

263
00:20:01,260 --> 00:20:05,780
ja sitten dekrementoidaan pinon koon,

264
00:20:05,780 --> 00:20:07,810
ja nyt olet menettänyt elementin päällä.

265
00:20:07,810 --> 00:20:11,420
Ja sitten palaat elementin päällä.

266
00:20:11,420 --> 00:20:20,080
[Student, käsittämättömällä]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Mitä tapahtuu, jos teet sen? [Student, käsittämättömällä]

268
00:20:28,810 --> 00:20:34,000
Mitä päätyy tapahtumassa on olet todennäköisesti päästä joko

269
00:20:34,000 --> 00:20:37,350
elementti, joka ei ole alustettu vielä, joten laskenta

270
00:20:37,350 --> 00:20:39,990
ja, jossa viimeinen elementti on pois päältä.

271
00:20:39,990 --> 00:20:46,260
Joten tässä, jos huomaat, push, me päästä jouset s.size elementti

272
00:20:46,260 --> 00:20:48,560
koska se on uusi hakemisto.

273
00:20:48,560 --> 00:20:51,460
Se on uusi pinon.

274
00:20:51,460 --> 00:21:01,100
Taas pop, s.size tulee olemaan seuraava tilaa,

275
00:21:01,100 --> 00:21:05,210
tila, joka on päälle kaikki elementit pino.

276
00:21:05,210 --> 00:21:10,050
Niin ylimmäinen elementti ei tällä s.size,

277
00:21:10,050 --> 00:21:14,930
vaan se on sen alle.

278
00:21:14,930 --> 00:21:19,640
>> Toinen asia tehdä, kun - pop,

279
00:21:19,640 --> 00:21:22,030
on sinulla on vähentääksesi kokoon.

280
00:21:22,030 --> 00:21:28,750
Jos muistat takaisin pikku kaavio täällä,

281
00:21:28,750 --> 00:21:30,980
oikeastaan ​​ainoa asia, että näimme tapahtuu kun soitimme pop

282
00:21:30,980 --> 00:21:36,150
oli se, että tämä koko putoaa, ensin 2, sitten 1.

283
00:21:36,150 --> 00:21:42,620
Sitten kun me työnnetään uusi elementti, se menisi oikeaan paikkaan.

284
00:21:42,620 --> 00:21:49,610
[Basil] Jos s.size on 2, niin eikö mennä elementin 2,

285
00:21:49,610 --> 00:21:54,400
ja sitten et haluaisi pop että elementti pois?

286
00:21:54,400 --> 00:21:59,510
Joten jos menimme - >> Joten katsokaamme asiaa uudelleen.

287
00:21:59,510 --> 00:22:07,730
Jos tämä on pino tässä vaiheessa

288
00:22:07,730 --> 00:22:12,130
ja kutsumme pop,

289
00:22:12,130 --> 00:22:16,150
jossa indeksi on Ylimmässä elementti?

290
00:22:16,150 --> 00:22:19,300
[Basil] 2, mutta se tulee pop 3. >> Oikea.

291
00:22:19,300 --> 00:22:24,220
Niin, että jos meidän koko on 3, mutta haluamme pop elementin indeksin 2.

292
00:22:24,220 --> 00:22:29,900
Se on niin tyypillistä sellainen pois joka teillä on nolla-indeksointi matriiseja.

293
00:22:29,900 --> 00:22:36,430
Joten et halua pop kolmas elementti, mutta kolmas osa ei tällä indeksi 3.

294
00:22:36,430 --> 00:22:39,430
Ja syystä emme tarvitse tehdä miinus 1, kun olemme työntää

295
00:22:39,430 --> 00:22:44,120
on sillä nyt, huomaat että Ylimmässä elementti,

296
00:22:44,120 --> 00:22:47,600
jos me työntää jotain muuta pinoon tässä vaiheessa,

297
00:22:47,600 --> 00:22:50,360
haluaisimme ajaa sitä indeksi 3.

298
00:22:50,360 --> 00:23:03,550
Ja se vain niin, että koko ja indeksit riviin kun olet työntää.

299
00:23:03,550 --> 00:23:06,960
>> Kenellä työskentelee pino täytäntöönpanon?

300
00:23:06,960 --> 00:23:09,690
Sinulla työskentelee pinota. Onko sinulla pop toimi vielä?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Kyllä. Luulen niin.

302
00:23:11,890 --> 00:23:14,610
>> Ohjelman käynnissä eikä seg Virhesovellus, se tulostetaan ulos?

303
00:23:14,610 --> 00:23:17,520
Onko se tulostaa "menestys", kun suoritat sen?

304
00:23:17,520 --> 00:23:22,630
Joo. Tee pino, ajaa, jos se tulostuu "menestys" ja ei mene puomi,

305
00:23:22,630 --> 00:23:26,000
Sitten kaikki on hyvää.

306
00:23:26,000 --> 00:23:34,070
Selvä. Mennään yli laite todella nopeasti,

307
00:23:34,070 --> 00:23:46,100
ja käydään läpi tätä.

308
00:23:46,100 --> 00:23:51,110
Jos katsomme mitä tapahtuu täällä pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, mikä oli ensimmäinen asia, että teit?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Jos s.size on suurempi kuin 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okei. Ja miksi teit sen?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Varmista, että siellä oli jotain sisällä pino.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Oikea. Haluat testata varmistaa, että s.size on suurempi kuin 0;

314
00:24:10,950 --> 00:24:13,280
muuten, mitä haluat on tapahtunut?

315
00:24:13,280 --> 00:24:16,630
[Daniel] return? >> Return null, tarkalleen.

316
00:24:16,630 --> 00:24:20,740
Joten jos s.size on suurempi kuin 0. Sitten mitä me teemme?

317
00:24:20,740 --> 00:24:25,890
Mitä teemme, jos pino ei ole tyhjä?

318
00:24:25,890 --> 00:24:31,210
[Stella] Olet vähentääksesi koko? >> Voit vähentääksesi kokoa, okei.

319
00:24:31,210 --> 00:24:34,440
Joten miten teit sen? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Suuri. Ja mitä sitten teit?

321
00:24:37,030 --> 00:24:44,140
[Stella] Ja sitten minä sanoin paluun s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Suuri.

323
00:24:48,560 --> 00:24:51,940
Muuten palaat null. Kyllä, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Miksi se ei tarvitse olla s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Joo. >> Selvä.

326
00:24:58,430 --> 00:25:00,980
[Sam] Ajattelin koska olet ottaen 1 lähtö,

327
00:25:00,980 --> 00:25:04,290
sitten olet menossa olevan palaamassa ole se, että he pyysivät.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Ja tämä oli juuri sitä mitä me puhuimme tämän koko kysymystä 0 indeksit.

329
00:25:09,400 --> 00:25:11,380
Joten jos me zoomata takaisin tänne.

330
00:25:11,380 --> 00:25:15,650
Jos katsomme tämä kaveri täällä, voit nähdä, että kun me pop,

331
00:25:15,650 --> 00:25:19,340
olemme popping elementin indeksin 2.

332
00:25:19,340 --> 00:25:25,200
>> Joten me pienentää myös koko ensimmäinen, sitten meidän koko vastaa meidän indeksiin.

333
00:25:25,200 --> 00:25:39,650
Jos emme vähentääksesi kokoa ensin, sitten meidän täytyy tehdä koko -1 ja sitten vähennys.

334
00:25:39,650 --> 00:25:45,270
Suuri. Kaikki hyvin?

335
00:25:45,270 --> 00:25:47,530
Kysyttävää tästä?

336
00:25:47,530 --> 00:25:54,050
On olemassa useita eri tapoja kirjoittaa tämän hyvin.

337
00:25:54,050 --> 00:26:03,290
Itse voimme tehdä jotain jopa - voimme tehdä sutkaus.

338
00:26:03,290 --> 00:26:05,770
Voimme tehdä yhden rivin tuottoa.

339
00:26:05,770 --> 00:26:12,980
Joten voimme todella vähentääksesi ennen palaamme tekemällä niin.

340
00:26:12,980 --> 00:26:18,320
Joten laskemisesta - ennen s.size.

341
00:26:18,320 --> 00:26:22,060
Se tekee linjan todella tiheä.

342
00:26:22,060 --> 00:26:30,940
Jos ero - s. Koko ja s.size--

343
00:26:30,940 --> 00:26:40,130
että tämä postfix - he kutsuvat sitä postfix koska - tulee sen jälkeen s.size--

344
00:26:40,130 --> 00:26:47,430
tarkoittaa sitä, että s.size arvioidaan varten löytää indeksin

345
00:26:47,430 --> 00:26:50,410
koska se on tällä hetkellä, kun tätä linjaa on suoritettu,

346
00:26:50,410 --> 00:26:54,290
ja sitten tämä - tapahtuu sen jälkeen linja saa suorittaa.

347
00:26:54,290 --> 00:27:00,340
Kun elementti indeksi s.size päästään.

348
00:27:00,340 --> 00:27:07,260
Ja se ei ole, mitä haluamme, koska haluamme vähennys tapahtuu ensin.

349
00:27:07,260 --> 00:27:10,990
Othewise, aiomme olla pääsy array, tehokkaasti, out of bounds.

350
00:27:10,990 --> 00:27:16,850
Aiomme olla pääsy elementin yläpuolella, joka todella haluamme päästä.

351
00:27:16,850 --> 00:27:23,840
Niin, Sam? >> Onko nopeammin tai käyttää vähemmän RAM tehdä yhdellä rivillä vai ei?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Oikeasti, se riippuu oikeastaan.

353
00:27:29,620 --> 00:27:34,220
[Sam, käsittämätön] >> Joo, se riippuu. Voit tehdä kääntäjä temppuja

354
00:27:34,220 --> 00:27:41,580
saada kääntäjä tunnistaa, että yleensä, uskoisin.

355
00:27:41,580 --> 00:27:44,840
>> Joten olemme maininneet hieman tästä kääntäjä optimointi kamaa

356
00:27:44,840 --> 00:27:47,400
että voit tehdä kokoamisessa,

357
00:27:47,400 --> 00:27:50,580
ja se on sellainen asia, että kääntäjä voisi selvittää,

358
00:27:50,580 --> 00:27:54,710
kuten Hei, ehkä voin tehdä tämän kaiken yhdellä kertaa,

359
00:27:54,710 --> 00:27:59,420
toisin kuin lastaus koko muuttujan RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing se, tallentamalla sen takaisin ulos, ja sitten lastaus se takaisin

361
00:28:03,770 --> 00:28:08,000
käsitellä loput tämän operaation.

362
00:28:08,000 --> 00:28:10,710
Mutta tyypillisesti, ei, tämä ei ole sellainen asia

363
00:28:10,710 --> 00:28:20,770
että menee tekemään ohjelmaa huomattavasti nopeammin.

364
00:28:20,770 --> 00:28:26,000
Enempää kysymyksiä pinot?

365
00:28:26,000 --> 00:28:31,360
>> Joten työntää ja paukkuu. Jos kaverit haluavat kokeilla hakkeri painos,

366
00:28:31,360 --> 00:28:33,660
mitä olemme tehneet hakkeri painos on todella mennyt

367
00:28:33,660 --> 00:28:37,670
ja teki tämän pino kasvaa dynaamisesti.

368
00:28:37,670 --> 00:28:43,190
Haasteena on ensisijaisesti täällä push-toiminto,

369
00:28:43,190 --> 00:28:48,820
selvittää, miten tehdä, että joukko kasvaa

370
00:28:48,820 --> 00:28:52,450
kun pitää työntää enemmän ja enemmän elementtejä pinoon.

371
00:28:52,450 --> 00:28:56,000
Se on oikeastaan ​​ole liikaa lisäkoodi.

372
00:28:56,000 --> 00:29:00,080
Vain puhelun - täytyy muistaa saada puhelut malloc siellä oikein,

373
00:29:00,080 --> 00:29:03,310
ja sitten selvittää, kun aiot soittaa realloc.

374
00:29:03,310 --> 00:29:06,090
Se on hauska haaste, jos olet kiinnostunut.

375
00:29:06,090 --> 00:29:11,550
>> Mutta toistaiseksi mennään eteenpäin, ja puhutaanpa jonoja.

376
00:29:11,550 --> 00:29:15,680
Selaa täältä.

377
00:29:15,680 --> 00:29:19,340
Jono on tiivis sisarus pinon.

378
00:29:19,340 --> 00:29:25,380
Joten pino, asioita, jotka otettiin viime

379
00:29:25,380 --> 00:29:28,810
olivat ensimmäisiä asioita sitten hakea.

380
00:29:28,810 --> 00:29:33,600
Meillä tätä last in, first out tai LIFO, tilaaminen.

381
00:29:33,600 --> 00:29:38,390
Taas jonossa, niin voit odottaa kun seisot jonossa,

382
00:29:38,390 --> 00:29:41,980
ensimmäinen henkilö saada linjassa, ensimmäinen asia päästä jonoon,

383
00:29:41,980 --> 00:29:47,630
on ensimmäinen asia, joka saa hakea jonosta.

384
00:29:47,630 --> 00:29:51,490
Jonot ovat myös usein käytetään kun olemme tekemisissä kuvaajia,

385
00:29:51,490 --> 00:29:55,560
kuten puhuimme lyhyesti pinot,

386
00:29:55,560 --> 00:30:00,260
ja jonot ovat myös kätevä joukko muita asioita.

387
00:30:00,260 --> 00:30:06,180
Eräs asia, joka tulee esiin usein yrittää säilyttää, esimerkiksi

388
00:30:06,180 --> 00:30:12,310
lajiteltu luettelo elementtejä.

389
00:30:12,310 --> 00:30:17,650
Ja voit tehdä tämän array. Voit säilyttää lajitella luetteloa asioita array,

390
00:30:17,650 --> 00:30:20,650
mutta jos se saa hankala on sinun aina löytää

391
00:30:20,650 --> 00:30:26,160
sopiva paikka lisätä seuraava asia.

392
00:30:26,160 --> 00:30:28,250
Joten jos sinulla on joukko numeroita, 1: stä 10,

393
00:30:28,250 --> 00:30:31,630
ja sitten haluat laajentaa että kaikki numerot 1 100,

394
00:30:31,630 --> 00:30:33,670
ja olet saada nämä numerot satunnaisessa järjestyksessä ja yrittää pitää kaiken

395
00:30:33,670 --> 00:30:40,650
lajiteltu kuten mennä läpi, voit päätyä tarvitse tehdä paljon siirtää.

396
00:30:40,650 --> 00:30:43,910
, Joilla on tiettyjä jonoja ja tiettyjen taustalla tietorakenteita,

397
00:30:43,910 --> 00:30:46,670
voit itse pitää sitä melko yksinkertainen.

398
00:30:46,670 --> 00:30:50,640
Sinun ei tarvitse lisätä jotain ja sitten remontti koko juttu joka kerta.

399
00:30:50,640 --> 00:30:56,770
Eikä sinun tarvitse tehdä paljon siirtyminen sisäisten elementtien ympärille.

400
00:30:56,770 --> 00:31:02,990
Kun katsomme jonoon, huomaat että - myös queue.c jaksossa koodi -

401
00:31:02,990 --> 00:31:10,950
struct että olemme antaneet sinulle on todella samanlainen struct että annoimme sinulle pinon.

402
00:31:10,950 --> 00:31:13,770
>> On yksi poikkeus, ja että yksi poikkeus

403
00:31:13,770 --> 00:31:21,700
on, että meillä on tämä ylimääräinen kokonaisluku kutsutaan pää-

404
00:31:21,700 --> 00:31:28,120
ja pää tässä on pitää kirjaa jonon,

405
00:31:28,120 --> 00:31:32,160
tai ensimmäinen elementti jonossa.

406
00:31:32,160 --> 00:31:37,470
Jossa pino, pystyimme pitämään kirjaa elementin, että olimme aikeissa hakea,

407
00:31:37,470 --> 00:31:40,800
tai pinon, käyttäen vain kokoa,

408
00:31:40,800 --> 00:31:44,220
kun taas jonon, olemme ottaa käsitellä vastakkaisiin päihin.

409
00:31:44,220 --> 00:31:49,000
Yritämme tack asioita lopussa, mutta palaavat sitten asioita edestä.

410
00:31:49,000 --> 00:31:54,640
Niin tehokkaasti, pää, meillä on indeksi alussa jonoon,

411
00:31:54,640 --> 00:31:58,920
ja koko antaa meille indeksi lopussa jonon

412
00:31:58,920 --> 00:32:03,730
jotta voimme hakea asioita pään ja lisätä asioita ja häntää.

413
00:32:03,730 --> 00:32:06,890
Kun taas pinon, olimme aina vain käsittelee pinon päälle.

414
00:32:06,890 --> 00:32:08,900
Emme koskaan tarvinnut käyttää pinon pohjalle.

415
00:32:08,900 --> 00:32:12,220
Me vain lisätty asioita ylös ja otti asiat pois alkuun

416
00:32:12,220 --> 00:32:17,470
joten emme tarvitse tuota ylimääräistä kentän sisällä meidän struct.

417
00:32:17,470 --> 00:32:20,590
Onko se yleensä järkeä?

418
00:32:20,590 --> 00:32:27,670
Selvä. Kyllä, Charlotte? [Charlotte, käsittämättömällä]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Se on hyvä kysymys, ja se oli yksi esille tulleet luento.

420
00:32:32,660 --> 00:32:36,290
Ehkä kävely läpi muutamia esimerkit havainnollistavat miksi

421
00:32:36,290 --> 00:32:41,400
emme halua käyttää merkkijonojen [0] kuin jonon.

422
00:32:41,400 --> 00:32:46,770
>> Joten kuvitella, että meillä on jonossa, aiomme kutsua sitä jonoon.

423
00:32:46,770 --> 00:32:49,210
Alussa, kun olemme juuri instantiated sitä,

424
00:32:49,210 --> 00:32:53,330
kun olemme juuri ilmoittanut sen, emme ole alustettu mitään.

425
00:32:53,330 --> 00:32:56,790
Se kaikki roskat. Niinpä tietenkin haluamme varmistaa, että meillä alustat

426
00:32:56,790 --> 00:33:00,950
Sekä koon ja pään kentät olla 0, jotain järkevää.

427
00:33:00,950 --> 00:33:05,770
Voisimme myös mennä eteenpäin ja null ulos elementtejä meidän jonoon.

428
00:33:05,770 --> 00:33:09,930
Ja jotta tämä kaavio sopivaksi, huomaat, että nyt meidän jono voi olla vain kolme tekijää;

429
00:33:09,930 --> 00:33:13,150
taas meidän pino mahtui neljä meidän jono voi olla vain kolme.

430
00:33:13,150 --> 00:33:18,680
Ja tämä on vain tehdä kaavion sovi.

431
00:33:18,680 --> 00:33:26,150
Ensimmäinen asia, joka tapahtuu tässä on meidän jonoon merkkijono "HI".

432
00:33:26,150 --> 00:33:30,380
Ja aivan kuten teimme pino, ei mitään kauhean erilaista täällä,

433
00:33:30,380 --> 00:33:39,230
heitämme string klo jouset [0] ja kasvattaa meidän kokoa 1.

434
00:33:39,230 --> 00:33:42,720
Me jonoon "heippa", se saa laittaa.

435
00:33:42,720 --> 00:33:45,870
Joten tämä näyttää pino suurimmaksi osaksi.

436
00:33:45,870 --> 00:33:53,230
Aloitimme täällä, uusi elementti, uusi elementti, koko pitää menossa ylös.

437
00:33:53,230 --> 00:33:56,330
Mitä tapahtuu tässä vaiheessa, kun haluamme dequeue jotain?

438
00:33:56,330 --> 00:34:01,280
Kun haluamme dequeue, joka on elementti, että me haluamme dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Kielet [0]. >> Zero. Täsmälleen oikea, Basil.

440
00:34:04,110 --> 00:34:10,960
Haluamme päästä eroon ensimmäinen merkkijono, tämä "hei".

441
00:34:10,960 --> 00:34:13,170
Joten mikä oli toinen asia, joka muutti?

442
00:34:13,170 --> 00:34:17,010
Huomaa kun piipahti jotain pois pinosta, me juuri muuttanut koko,

443
00:34:17,010 --> 00:34:22,080
mutta täällä meillä pari asiaa, jotka muuttuvat.

444
00:34:22,080 --> 00:34:27,440
Ei ainoastaan ​​koon muuttaminen, mutta pää muuttuu.

445
00:34:27,440 --> 00:34:31,020
Tämä menee takaisin Charlotte näkökulmasta aiemmin:

446
00:34:31,020 --> 00:34:38,699
miksi meillä on tämä pää samoin?

447
00:34:38,699 --> 00:34:42,110
Onko mitään järkeä nyt, Charlotte? >> Tavallaan.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Kind of? Joten mitä tapahtui, kun me dequeued?

449
00:34:47,500 --> 00:34:54,340
Mitä päätä tehdä sitä nyt on mielenkiintoista?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Voi, koska se muutti - okei. Ymmärrän.

451
00:34:56,449 --> 00:35:02,090
Koska pää - jossa pää on osoittaa muutoksia kannalta sijainnin.

452
00:35:02,090 --> 00:35:07,200
Se ei ole enää aina nolla indeksin yksi. >> Aivan.

453
00:35:07,200 --> 00:35:17,660
Mitä tapahtui oli jos dequeueing suuri osa

454
00:35:17,660 --> 00:35:20,590
tehtiin ja meillä ei ole tätä päätä alalla

455
00:35:20,590 --> 00:35:26,880
koska olimme aina vaatineet tämän merkkijonon 0 indeksi pään meidän jono,

456
00:35:26,880 --> 00:35:30,170
Sitten meillä olisi siirtää loput jonon alas.

457
00:35:30,170 --> 00:35:36,010
Meidän täytyisi siirtää "hei" mistä alkaen jouset [1] merkkijonot [0].

458
00:35:36,010 --> 00:35:38,760
Ja jousille [2] alas strings [1].

459
00:35:38,760 --> 00:35:43,050
Ja olisimme täytyy tehdä tämä koko luettelo tekijöistä,

460
00:35:43,050 --> 00:35:45,110
koko joukko elementtejä.

461
00:35:45,110 --> 00:35:50,490
Ja kun teemme tätä array, että saa todella kallista.

462
00:35:50,490 --> 00:35:53,340
Joten tässä, se ei ole iso juttu. Meillä on vain kolme tekijää meidän array.

463
00:35:53,340 --> 00:35:57,230
Mutta jos meillä oli jonossa tuhat elementtejä tai miljoona elementtejä,

464
00:35:57,230 --> 00:36:00,060
ja sitten yhtäkkiä, alamme tehdä kasan dequeue kutsuu kaikki silmukka,

465
00:36:00,060 --> 00:36:03,930
asiat ovat todella hiljenee sillä se siirtää kaiken alas jatkuvasti.

466
00:36:03,930 --> 00:36:07,320
Tiedätkö, siirtyvän 1, muutos 1, muutos 1, muutos 1.

467
00:36:07,320 --> 00:36:13,650
Sen sijaan käytämme tämän pään, me kutsumme sitä "osoitin", vaikka se ei oikeastaan ​​osoitin

468
00:36:13,650 --> 00:36:16,430
suppeassa merkityksessä, se ei ole osoitin tyyppiä.

469
00:36:16,430 --> 00:36:19,410
Se ei ole int * tai char * tai mitään sellaista.

470
00:36:19,410 --> 00:36:28,930
Mutta se osoittaa tai ilmoitetaan pää meidän jonoon. Niin?

471
00:36:28,930 --> 00:36:38,800
>> [Opiskelija] Kuinka dequeue tietää vain pop pois mitä on pään?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Kuinka dequeue osaa kupsahtaa mitä on kärjessä? >> Aivan, joo.

473
00:36:43,620 --> 00:36:49,050
>> Mitä se katselee vain mitä päähän kentän asetetaan.

474
00:36:49,050 --> 00:36:52,710
Joten tässä ensimmäisessä asiassa, jos katsomme täällä,

475
00:36:52,710 --> 00:36:55,690
päämme on 0, indeksi 0. >> Oikea.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Niin se vain sanoo kunnossa, hyvin, elementti indeksi 0, merkkijono "hi"

477
00:37:00,500 --> 00:37:03,050
on elementti kärjessä meidän jonoon.

478
00:37:03,050 --> 00:37:05,570
Joten menemme dequeue että kaveri.

479
00:37:05,570 --> 00:37:09,800
Ja että on elementti, joka saa takaisin soittajalle.

480
00:37:09,800 --> 00:37:14,540
Kyllä, Saad? >> Joten pään periaatteessa asettaa - jos olet menossa indeksoida sitä?

481
00:37:14,540 --> 00:37:17,750
Se alku se? >> Joo. >> Okei.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Tuo tulossa uutta alkua meidän array.

483
00:37:22,900 --> 00:37:28,930
Joten kun dequeue jotain, kaikki sinun tarvitsee vain käyttää elementin indeksin q.head,

484
00:37:28,930 --> 00:37:32,240
ja että on elementti, jonka haluat dequeue.

485
00:37:32,240 --> 00:37:34,930
Sinulla on myös vähentääksesi kokoon.

486
00:37:34,930 --> 00:37:39,430
Tulemme näkemään vähän missä asiat saavat hieman hankala tätä.

487
00:37:39,430 --> 00:37:46,520
Me dequeue, ja nyt, jos me jonoon uudelleen,

488
00:37:46,520 --> 00:37:51,300
missä me jonoon?

489
00:37:51,300 --> 00:37:55,000
Mistä seuraava osa mennä meidän jonossa?

490
00:37:55,000 --> 00:37:57,980
Sano haluamme jonoon merkkijono "CS".

491
00:37:57,980 --> 00:38:02,240
Johon indeksi sen mennä? [Opiskelijat] Kielet [2]. >> Kaksi.

492
00:38:02,240 --> 00:38:04,980
Miksi 2 eikä 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Koska nyt pää on 1, niin että on kuin alun listan?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Oikea. Ja mitä tarkoittaa listan loppuun?

495
00:38:21,220 --> 00:38:23,290
Mitä käytämme kuvaamaan loppuun meidän jonoon?

496
00:38:23,290 --> 00:38:25,970
Pää on pää meidän jonon alku meidän jonoon.

497
00:38:25,970 --> 00:38:29,530
Mikä on lopussa meidän jonoon? [Opiskelijat] Koko. >> Size, tarkalleen.

498
00:38:29,530 --> 00:38:36,360
Joten meidän uusia elementtejä mennä klo koon, ja tekijät, jotka otamme pois irrota pään.

499
00:38:36,360 --> 00:38:45,390
Kun jonoon seuraavan elementin, me laitamme sen osoitteessa kokoa.

500
00:38:45,390 --> 00:38:48,530
[Opiskelija] Ennen kuin laitat että vaikka koko oli 1, eikö?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Oikea. Joten ole aivan koko. Koko +, ei +1, mutta + pää.

502
00:38:55,690 --> 00:38:59,990
Koska muutimme kaiken pään määrällä.

503
00:38:59,990 --> 00:39:14,270
Joten tässä, nyt meillä jono koko 1, joka alkaa klo indeksi 1.

504
00:39:14,270 --> 00:39:20,730
Häntä on indeksi 2. Kyllä?

505
00:39:20,730 --> 00:39:25,780
>> [Opiskelija] Mitä tapahtuu kun dequeue merkkijonot [0] ja jousien lähtö muistiin

506
00:39:25,780 --> 00:39:29,420
vain saada tyhjennetty, pohjimmiltaan, tai vain unohtanut?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Joo. Tässä mielessä me vain unohtaa ne.

508
00:39:34,700 --> 00:39:42,640
Jos me tallentamalla niiden jäljennökset -

509
00:39:42,640 --> 00:39:46,310
monet tietorakenteet usein tallentaa omia kopioita elementtien

510
00:39:46,310 --> 00:39:51,760
niin, että henkilö hallintaan tietorakenne ei tarvitse huolehtia

511
00:39:51,760 --> 00:39:53,650
mistä kaikki osoittimet ovat menossa.

512
00:39:53,650 --> 00:39:56,000
Tietorakenne pitää kiinni kaikesta, pitää kiinni kaikista kopiot,

513
00:39:56,000 --> 00:39:59,580
varmista, että kaikki jatkuu asianmukaisesti.

514
00:39:59,580 --> 00:40:03,140
Kuitenkin tässä tapauksessa nämä tietorakenteita vain, yksinkertaisuuden vuoksi,

515
00:40:03,140 --> 00:40:05,580
ei tehdä kopioita mitään, että olemme tallentamalla niihin.

516
00:40:05,580 --> 00:40:08,630
[Opiskelija] Eli tämä jatkuva joukko -? >> Kyllä.

517
00:40:08,630 --> 00:40:14,350
Jos me katsomme taaksepäin, mikä määritelmän oli tämän rakenteen, se on.

518
00:40:14,350 --> 00:40:19,110
Se on vain tavallinen array kuten olet nähnyt,

519
00:40:19,110 --> 00:40:24,280
joukko char * s.

520
00:40:24,280 --> 00:40:26,340
Onko se -? >> Joo, olin juuri mietin

521
00:40:26,340 --> 00:40:29,130
jos sinun lopulta loppuu muisti, jossain määrin,

522
00:40:29,130 --> 00:40:32,330
Jos sinulla on kaikki nämä tyhjät kohdat sinun array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Joo, hyvä pointti.

524
00:40:36,390 --> 00:40:41,530
>> Jos katsomme, mitä on tapahtunut nyt tässä vaiheessa,

525
00:40:41,530 --> 00:40:46,350
olemme täynnä meidän jonoon, se näyttää.

526
00:40:46,350 --> 00:40:50,390
Mutta emme ole oikeastaan ​​täynnä meidän jonossa

527
00:40:50,390 --> 00:40:57,710
koska meillä on jonon, joka on koko 2, mutta se alkaa indeksi 1,

528
00:40:57,710 --> 00:41:02,160
koska sieltä meidän pään osoitin on.

529
00:41:02,160 --> 00:41:08,400
Kuten sanoit, että elementin jouset [0], on indeksi 0, ei oikeastaan ​​ole olemassa.

530
00:41:08,400 --> 00:41:10,450
Se ei ole meidän jonoon enää.

531
00:41:10,450 --> 00:41:16,460
Me vain ei viitsinyt mennä ja korvata sen, kun me dequeued sitä.

532
00:41:16,460 --> 00:41:18,700
Joten vaikka se näyttää olemme loppuu muisti, emme todellakaan ole.

533
00:41:18,700 --> 00:41:23,270
Tämä piste on meille käyttöä.

534
00:41:23,270 --> 00:41:29,310
Asianmukaista käyttäytymistä, jos olisimme yrittää ja ensimmäisen dequeue jotain

535
00:41:29,310 --> 00:41:34,420
kuten "hei", joka pop hei pois.

536
00:41:34,420 --> 00:41:38,460
Nyt meidän jono alkaa indeksin 2 ja on kooltaan 1.

537
00:41:38,460 --> 00:41:42,240
Ja nyt jos yrittää laittaa jonoon jotain uudestaan, vaikkapa 50,

538
00:41:42,240 --> 00:41:47,880
50 pitäisi mennä tällä paikalla klo indeksi 0

539
00:41:47,880 --> 00:41:51,270
koska se on vielä saatavilla meille. Kyllä, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] se tapahtuu automaattisesti?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Se ei tapahdu aivan automaattisesti. Sinun täytyy tehdä matematiikka

542
00:41:56,150 --> 00:42:00,380
tehdä työtä, mutta lähinnä mitä olemme tehneet, on meillä vain kiedottu.

543
00:42:00,380 --> 00:42:04,070
[Saad] Ja se on ok, jos tämä on reikä keskellä se?

544
00:42:04,070 --> 00:42:08,720
[Hardison] On, jos voimme tehdä matematiikka treenata kunnolla.

545
00:42:08,720 --> 00:42:15,470
>> Ja näyttää siltä, ​​että se on oikeastaan ​​ole niin vaikea tehdä mod operaattorin.

546
00:42:15,470 --> 00:42:20,040
Eli aivan kuten teimme Caesar ja crypto tavaraa,

547
00:42:20,040 --> 00:42:25,190
käyttäen mod, voimme saada asioita Ulottumamitan ja jatka

548
00:42:25,190 --> 00:42:28,090
ympäri ja ympäri ja ympäri meidän jono,

549
00:42:28,090 --> 00:42:32,180
pitää, että pää osoitin liikkuu.

550
00:42:32,180 --> 00:42:38,840
Huomaa, että koko on aina kunnioittaa alkioiden lukumäärä tosiasiallisesti sisällä jonoon.

551
00:42:38,840 --> 00:42:43,110
Ja se on vain esiosoitinta joka pitää pyöräilyn kautta.

552
00:42:43,110 --> 00:42:49,660
Jos katsomme, mitä täällä tapahtui, jos menemme takaisin alkuun,

553
00:42:49,660 --> 00:42:55,020
ja juuri katsella mitä tapahtuu pään

554
00:42:55,020 --> 00:42:58,240
kun jonoon jotain, mitään ei tapahtunut päähän.

555
00:42:58,240 --> 00:43:00,970
Kun me enqueued jotain muuta, mitään ei tapahtunut päähän.

556
00:43:00,970 --> 00:43:04,130
Heti kun me dequeued jotain, pää nousee yhdellä.

557
00:43:04,130 --> 00:43:06,600
Me enqueued jotakin, mitään ei tapahdu päähän.

558
00:43:06,600 --> 00:43:11,060
Kun me dequeue jotain, yhtäkkiä pää saa kasvatetaan.

559
00:43:11,060 --> 00:43:14,660
Kun me jonoon jotakin, mitään ei tapahdu päähän.

560
00:43:14,660 --> 00:43:20,240
>> Mitä tapahtuisi tässä vaiheessa, jos me dequeue jotain uudelleen?

561
00:43:20,240 --> 00:43:23,240
Mitään ajatuksia? Mitä tapahtuisi päähän?

562
00:43:23,240 --> 00:43:27,190
Mitä pitäisi tapahtua päähän

563
00:43:27,190 --> 00:43:32,990
jos me dequeue jotain muuta?

564
00:43:32,990 --> 00:43:35,400
Pää nyt on indeksi 2,

565
00:43:35,400 --> 00:43:38,920
mikä tarkoittaa sitä, että jonon on jouset [2].

566
00:43:38,920 --> 00:43:44,280
[Student], joka palauttaa 0? >> Olisi palata 0. Sen pitäisi kääri takaisin noin, täsmälleen.

567
00:43:44,280 --> 00:43:48,440
Toistaiseksi aina vaadimme dequeue, olemme lisäämällä yksi pää,

568
00:43:48,440 --> 00:43:50,960
lisätä yhden pään, lisää yksi pää, lisätään yksi päähän.

569
00:43:50,960 --> 00:43:58,400
Heti kun tämä esiosoittimen saa viimeinen indeksi meidän array,

570
00:43:58,400 --> 00:44:05,650
Sitten meidän on kääriä se takaisin noin alkuun, mene takaisin 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Mikä määrittää kapasiteetin jono pino?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Tässä tapauksessa olemme juuri käyttämällä # määritellyn vakio. >> Okei.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Varsinaisessa. C-tiedoston, voit mennä ja sonta sen kanssa hieman

574
00:44:19,590 --> 00:44:21,710
ja tehdä se niin suuri tai pieni kuin haluat.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Joten kun teet sen jonon, miten teet tietokoneen tietävät

576
00:44:25,310 --> 00:44:29,120
kuinka iso haluat pino olla?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Se on hyvä kysymys.

578
00:44:31,700 --> 00:44:34,800
On olemassa pari tapaa. Yksi on vain määritellä se edessä

579
00:44:34,800 --> 00:44:42,050
ja sanoa tämä tulee olemaan jonoon, joka on 4 elementtiä tai 50 osia tai 10000.

580
00:44:42,050 --> 00:44:45,430
Toinen tapa on tehdä mitä hakkeri painos ihmiset tekevät

581
00:44:45,430 --> 00:44:52,310
ja luoda toimintoja on teidän jono kasvaa dynaamisesti enemmän asioita saa lisätä tuumaa

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Joten mennä ensimmäinen vaihtoehto, mitä syntaksia käytät

583
00:44:54,740 --> 00:44:57,830
kertoa ohjelman, mikä on koko jonon?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Joten ulos tästä.

585
00:45:04,780 --> 00:45:12,650
Olen edelleen stack.c täällä, joten olen juuri menossa vierittää ylös tänne.

586
00:45:12,650 --> 00:45:17,920
Näetkö tämän täällä? Tämä on # define kapasiteetti 10.

587
00:45:17,920 --> 00:45:24,600
Ja tämä on melkein täsmälleen samaa syntaksia meillä on jonossa.

588
00:45:24,600 --> 00:45:28,390
Paitsi jonossa, meillä että ylimääräistä struct kenttä täällä.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Voi, luulin kapasiteetin vuoksi kapasiteetin merkkijono.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Että se on maksimipituus sanan. >> Selvä.

591
00:45:36,770 --> 00:45:41,180
Joo. Kapasiteetti täällä - se on hyvä piste.

592
00:45:41,180 --> 00:45:44,000
Ja tämä on jotain, joka on hankala

593
00:45:44,000 --> 00:45:49,480
sillä mitä olemme julisti täällä on joukko char * s.

594
00:45:49,480 --> 00:45:52,770
Joukko osoittimia.

595
00:45:52,770 --> 00:45:56,690
Tämä on matriisi merkkiä.

596
00:45:56,690 --> 00:46:01,690
Tämä on luultavasti mitä olet nähnyt, kun olet ollut julistaa sinun puskurit tiedoston I / O,

597
00:46:01,690 --> 00:46:06,840
kun olet ollut luomassa jouset manuaalisesti pinoon.

598
00:46:06,840 --> 00:46:09,090
Mutta se, mitä meillä täällä on joukko char * s.

599
00:46:09,090 --> 00:46:13,400
Joten se joukko osoittimia.

600
00:46:13,400 --> 00:46:18,350
Oikeastaan, jos me zoomata takaisin ulos ja katsomme mitä tapahtuu täällä

601
00:46:18,350 --> 00:46:23,140
esityksen, näet että todelliset tekijät, merkin tietoja

602
00:46:23,140 --> 00:46:26,180
ei ole tallennettu matriisin sisällä itse.

603
00:46:26,180 --> 00:46:42,690
Mikä on talletettu joukko täällä ovat osoittimia merkin tietoihin.

604
00:46:42,690 --> 00:46:52,560
Okei. Joten olemme nähneet, kuinka koko jono aivan kuten pinon

605
00:46:52,560 --> 00:46:58,670
koko kunnioittaa aina elementtien lukumäärä tällä hetkellä jonossa.

606
00:46:58,670 --> 00:47:02,720
Tehtyään 2 enqueues, koko on 2.

607
00:47:02,720 --> 00:47:07,110
Tehtyään dequeue koko on nyt 1.

608
00:47:07,110 --> 00:47:09,330
Tehtyään toisen Aseta jonoon koko on takaisin enintään 2.

609
00:47:09,330 --> 00:47:12,340
Joten koko ehdottomasti noudattaa elementtien määrä jonossa,

610
00:47:12,340 --> 00:47:15,580
ja sitten pää vain pitää pyöräily.

611
00:47:15,580 --> 00:47:20,210
Se menee 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Ja joka kerta me kutsumme dequeue, esiosoitinta saa kasvaa seuraavaan indeksiin.

613
00:47:25,620 --> 00:47:29,930
Ja jos pää on aikeissa mennä yli, se palaa takaisin noin 0.

614
00:47:29,930 --> 00:47:34,870
Niin, että voimme kirjoittaa dequeue toimintoa.

615
00:47:34,870 --> 00:47:40,200
Ja me aiomme lähteä Aseta jonoon toiminto te toteuttaa sijaan.

616
00:47:40,200 --> 00:47:45,880
>> Kun me dequeue osa ulos meidän jono,

617
00:47:45,880 --> 00:47:55,490
Mikä oli ensimmäinen asia, että Daniel teki, kun aloimme kirjallisesti pop toiminto pinot?

618
00:47:55,490 --> 00:48:00,490
Saanen kuulla jonkun, joka ei ole puhunut vielä.

619
00:48:00,490 --> 00:48:06,710
Katsotaanpa, Saad, muistatko mitä Daniel teki niin ensimmäinen asia, kun hän kirjoitti pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Siellä oli, se oli - >> Hän testasi jotain.

621
00:48:08,860 --> 00:48:12,140
[Saad] Jos koko on suurempi kuin 0. >> Aivan.

622
00:48:12,140 --> 00:48:14,390
Ja mikä oli se testaus?

623
00:48:14,390 --> 00:48:19,090
[Saad] Tämä oli testata, onko siellä mitään sisällä array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Joo. Aivan. Joten et voi pop mitään pois pinosta, jos se on tyhjä.

625
00:48:23,210 --> 00:48:26,510
Samoin, et voi dequeue mitään jonoon, jos se on tyhjä.

626
00:48:26,510 --> 00:48:30,420
Mikä on ensimmäinen asia, joka meidän pitäisi tehdä meidän dequeue toiminto täällä, luulet?

627
00:48:30,420 --> 00:48:33,860
[Saad] Jos koko on suurempi kuin 0? >> Joo.

628
00:48:33,860 --> 00:48:37,710
Tässä tapauksessa olen oikeastaan ​​juuri testattu nähdä, jos se on 0.

629
00:48:37,710 --> 00:48:42,240
Jos se on 0, voimme palata null.

630
00:48:42,240 --> 00:48:45,280
Mutta täsmälleen samaa logiikkaa.

631
00:48:45,280 --> 00:48:49,110
Ja jatkakaamme tätä.

632
00:48:49,110 --> 00:48:54,600
Jos koko ei ole 0, missä on elementti, että me haluamme dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] Kärjessä? >> Aivan.

634
00:48:58,550 --> 00:49:01,720
Voimme vain vetää ulos ensimmäinen elementti meidän jonossa

635
00:49:01,720 --> 00:49:07,040
avaamalla elementin päähän.

636
00:49:07,040 --> 00:49:14,630
Mikään hullu.

637
00:49:14,630 --> 00:49:19,620
Sen jälkeen, mitä meidän pitäisi tehdä? Mitä on tapahtunut?

638
00:49:19,620 --> 00:49:23,740
Mikä oli toinen asia, että puhuimme dequeue?

639
00:49:23,740 --> 00:49:28,130
Kaksi asiaa täytyy tapahtua, koska meidän jono on muuttunut.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Pienennä kokoa. >> Meillä pienentää ja kasvattaa pää? Aivan.

641
00:49:35,640 --> 00:49:40,600
Voit lisätä pään, emme voi sokeasti lisätä pään, muistan.

642
00:49:40,600 --> 00:49:45,080
Emme voi vain tehdä queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Meidän on myös tähän mod mennessä kapasiteettia.

644
00:49:51,630 --> 00:49:54,740
Ja miksi me mod jonka kapasiteettia, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Koska se on kietoa. >> Aivan.

646
00:49:58,680 --> 00:50:04,750
Me mod n kapasiteetti, koska se on kääriä takaisin noin 0.

647
00:50:04,750 --> 00:50:07,400
Joten nyt tässä vaiheessa, voimme tehdä mitä Daniel sanoi.

648
00:50:07,400 --> 00:50:12,700
Me voi vähentää kokoa.

649
00:50:12,700 --> 00:50:29,170
Ja sitten voimme vain palata elementin, joka oli yläosassa jonon.

650
00:50:29,170 --> 00:50:34,000
Se näyttää sellaista gnarly aluksi. Saatat olla kysymys. Anteeksi?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Miksi on ensin yläosassa jonossa? Minne se meni?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Se tulee neljäs rivi alhaalta.

653
00:50:42,480 --> 00:50:46,060
Kun testaamme varmistaa, että jono ei ole tyhjä,

654
00:50:46,060 --> 00:50:54,100
me vedä char * Ensinnäkin, me vedä elementti, joka istuu päähän indeksi

655
00:50:54,100 --> 00:50:58,680
meidän valikoima, meidän merkkijonojen joukko, >> ja soita se ensimmäinen?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Ja me kutsumme sitä ensin. Joo.

657
00:51:04,500 --> 00:51:09,850
Vain seurata, että miksi luulet meidän piti tehdä se?

658
00:51:09,850 --> 00:51:18,270
[Sam] Kukin ensimmäinen on juuri palaamassa q.strings [q.head]? >> Joo.

659
00:51:18,270 --> 00:51:23,830
>> Koska teemme tätä muuttaminen q.head kanssa mod-toiminto,

660
00:51:23,830 --> 00:51:27,810
ja ei ole tapa tehdä se sisällä paluulinjaan myös.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Aivan. Olet paikalla. Samin täysin kohdalleen.

662
00:51:31,640 --> 00:51:36,800
Siksi meidän piti vetäytyä ensimmäinen elementti meidän jonoon ja tallentaa sen muuttujaan

663
00:51:36,800 --> 00:51:43,030
johtuu tämä rivi jossa olimme juuri q.head,

664
00:51:43,030 --> 00:51:47,030
siellä mod toimija ei ole jotain, mitä voimme tehdä

665
00:51:47,030 --> 00:51:51,230
ja ovat sen voimaan päähän ilman - yhdellä rivillä.

666
00:51:51,230 --> 00:51:54,480
Joten meillä on todellakin vetää ulos ensimmäinen osa, säädä pää-

667
00:51:54,480 --> 00:52:00,430
Säädä kokoa ja palauta elementti, että me vedetään ulos.

668
00:52:00,430 --> 00:52:02,680
Ja tämä on jotain, että näemme keksiä myöhemmin

669
00:52:02,680 --> 00:52:04,920
linkitettyjä listoja, kuten leikkiä heidän kanssaan.

670
00:52:04,920 --> 00:52:08,410
Usein kun olet vapauttaa tai hävittämistä linkitettyjä listoja

671
00:52:08,410 --> 00:52:13,500
sinun täytyy muistaa seuraavan elementin, seuraava osoitin linkitetyn listan

672
00:52:13,500 --> 00:52:16,330
ennen hävittämistä nykyinen.

673
00:52:16,330 --> 00:52:23,580
Koska muuten heität pois tietoa siitä, mitä on jäljellä luettelossa.

674
00:52:23,580 --> 00:52:34,160
Nyt, jos menet laitteesi, voit avata queue.c--x pois tästä.

675
00:52:34,160 --> 00:52:39,390
Joten jos olen avata queue.c, haluan zoom täällä,

676
00:52:39,390 --> 00:52:44,970
huomaat, että sinulla on samanlainen näköinen tiedosto.

677
00:52:44,970 --> 00:52:49,200
Samanlaisia ​​näköisiä tiedosto mitä meillä oli aiemmin stack.c.

678
00:52:49,200 --> 00:52:54,690
Meillä myös struct varten jonon määritellään kuten näimme dioja.

679
00:52:54,690 --> 00:52:59,870
>> Meillä Aseta jonoon toiminto, joka on sinua tekemään.

680
00:52:59,870 --> 00:53:04,340
Ja meillä on dequeue toimintoa täällä.

681
00:53:04,340 --> 00:53:06,870
Dequeue toiminto tiedoston toteutumatta,

682
00:53:06,870 --> 00:53:13,230
mutta laitan sen takaisin ylös PowerPoint jotta voit kirjoittaa sen, jos haluat.

683
00:53:13,230 --> 00:53:16,690
Joten seuraavan 5 minuuttia tai niin, te työtä Aseta jonoon

684
00:53:16,690 --> 00:53:22,570
mikä on lähes aivan vastakohta dequeue.

685
00:53:22,570 --> 00:53:29,560
Sinun ei tarvitse säätää pään kun olet enqueueing, mutta mitä sinun täytyy säätää?

686
00:53:29,560 --> 00:53:38,920
Size. Joten kun Aseta jonoon, pää pysyy koskemattomana, kokoa saa muuttaa.

687
00:53:38,920 --> 00:53:46,920
Mutta se vie vähän - joudut leikkiä että mod

688
00:53:46,920 --> 00:53:57,560
selvittää, mitä indeksi uutuutta Lisätään.

689
00:53:57,560 --> 00:54:03,080
Joten annan teitä vähän, laita dequeue takaisin ylös dian,

690
00:54:03,080 --> 00:54:05,200
ja koska teillä kysymyksiä, huutaa ne pois, jotta voimme

691
00:54:05,200 --> 00:54:09,220
kaikki puhuvat niitä ryhmässä.

692
00:54:09,220 --> 00:54:13,960
Lisäksi, kokoa älä - kun säädät kokoa, voit aina juuri -

693
00:54:13,960 --> 00:54:18,720
sinulla mod kokoon koskaan? [Daniel] No >> Sinun ei tarvitse mod kokoon, oikea.

694
00:54:18,720 --> 00:54:24,260
Koska koko aina, jos Sinä - olettaen olet hallinnassa asioita asianmukaisesti,

695
00:54:24,260 --> 00:54:30,840
koko on aina välillä 0 ja 3.

696
00:54:30,840 --> 00:54:38,680
Missä teillä on mod kun teet Aseta jonoon?

697
00:54:38,680 --> 00:54:41,060
[Student] Vain päähän. >> Vain päähän, täsmälleen.

698
00:54:41,060 --> 00:54:44,620
Ja miksi olet mod lainkaan Aseta jonoon?

699
00:54:44,620 --> 00:54:48,830
Kun on tilanne, jossa sinun täytyy mod?

700
00:54:48,830 --> 00:54:53,630
[Opiskelija] Jos tavaraa tilat, kuten välien 1 ja 2,

701
00:54:53,630 --> 00:54:55,950
ja sitten sinun piti lisätä jotain 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Joo, aivan. Joten jos päätäsi osoitin on aivan lopussa,

703
00:55:02,570 --> 00:55:14,210
tai jos kokoa plus pää on isompi, tai pikemminkin on menossa kietoa jonoon.

704
00:55:14,210 --> 00:55:17,830
>> Joten tässä tilanteessa, että meillä täällä diassa juuri nyt,

705
00:55:17,830 --> 00:55:24,370
jos haluan jonoon jotain juuri nyt,

706
00:55:24,370 --> 00:55:31,110
haluamme jonoon jotain index 0.

707
00:55:31,110 --> 00:55:35,450
Joten jos tarkastellaan missä 50 menee, ja kehotan Aseta jonoon 50,

708
00:55:35,450 --> 00:55:40,840
se menee alas siellä alareunassa. Se menee indeksi 0.

709
00:55:40,840 --> 00:55:44,160
Se korvaa "hi", joka oli jo dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Älä hoidat että dequeue jo?

711
00:55:46,210 --> 00:55:50,550
Miksi se tee mitään pää Aseta jonoon?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ai, niin et ole muuttaa pään, anteeksi.

713
00:55:55,770 --> 00:56:02,310
Mutta sinun täytyy käyttää mod operaattori kun olet siirtymässä

714
00:56:02,310 --> 00:56:04,250
elementti, jonka haluat laittaa jonoon kun olet siirtymässä

715
00:56:04,250 --> 00:56:06,960
Seuraava osa jonoon.

716
00:56:06,960 --> 00:56:10,960
[Basil] En tee sitä, ja sain "menestys" on siellä.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, ymmärrän mitä sanot.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Joten didn't - teit kello q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Joo. Olen juuri vaihtanut puolia en tee mitään päähän.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Sinun ei oikeastaan ​​tarvitse palauttaa pään olla mitään,

721
00:56:24,300 --> 00:56:31,650
mutta kun indeksinä jouset array,

722
00:56:31,650 --> 00:56:39,500
sinun todella täytyy mennä eteenpäin ja laskea missä seuraava elementti on,

723
00:56:39,500 --> 00:56:44,230
koska withe pino, seuraava osa pino oli aina

724
00:56:44,230 --> 00:56:48,740
on indeksi, joka vastaa kokoa.

725
00:56:48,740 --> 00:56:55,850
Jos katsomme taaksepäin ylös meidän pino push-toiminto,

726
00:56:55,850 --> 00:57:03,100
voisimme aina jysäyttää meidän uusi elementti aivan indeksin kokoa.

727
00:57:03,100 --> 00:57:06,710
Kun taas jono, emme voi tehdä sitä

728
00:57:06,710 --> 00:57:10,340
sillä jos me olemme tässä tilanteessa,

729
00:57:10,340 --> 00:57:18,130
jos me enqueued 50 uuden merkkijonon menisi aivan merkkijonot [1]

730
00:57:18,130 --> 00:57:20,540
jotka emme halua tehdä.

731
00:57:20,540 --> 00:57:41,200
Haluamme olla uusi merkkijono mennä indeksi 0.

732
00:57:41,200 --> 00:57:44,320
>> Onko kukaan - kyllä? [Opiskelija] Minulla on kysymys, mutta se ei varsinaisesti liity.

733
00:57:44,320 --> 00:57:48,160
Mitä se tarkoittaa, kun joku vain pyytää jotain pred osoitin?

734
00:57:48,160 --> 00:57:51,260
Mikä on se nimi lyhenne? Tiedän, että se on vain nimi.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred osoitin? Katsotaanpa. Missä yhteydessä?

736
00:57:59,110 --> 00:58:01,790
[Student] Se oli insertti. Voin kysyä myöhemmin, jos haluat

737
00:58:01,790 --> 00:58:03,920
koska se ei varsinaisesti liity, mutta minä vain -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Daavidin insertti koodin luento?

739
00:58:07,300 --> 00:58:10,860
Voimme vetää, että ylös ja puhua siitä.

740
00:58:10,860 --> 00:58:15,550
Puhumme siitä ensi kerran saamme linkitettyjä listoja.

741
00:58:15,550 --> 00:58:21,440
>> Joten todella nopeasti katsoa, ​​mitä Aseta jonoon toiminto näyttää.

742
00:58:21,440 --> 00:58:26,530
Mikä oli ensimmäinen asia, että ihmiset yrittivät tehdä oman Aseta jonoon linja? Tähän jonoon?

743
00:58:26,530 --> 00:58:29,960
Samanlaisia ​​mitä teit pinon työntää.

744
00:58:29,960 --> 00:58:32,080
Mitä teit, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, käsittämättömällä]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Aivan. Jos (q.size == kapasiteetti) -

747
00:58:45,700 --> 00:58:54,720
Minun täytyy laittaa henkselit oikeassa paikassa - palauttaa false.

748
00:58:54,720 --> 00:59:01,370
Lähennä hieman. Okei.

749
00:59:01,370 --> 00:59:03,800
Nyt mitä seuraava asia, että meidän piti tehdä?

750
00:59:03,800 --> 00:59:11,370
Aivan kuten pino, ja lisätään oikeaan paikkaan.

751
00:59:11,370 --> 00:59:16,010
Ja niin mikä oli oikea paikka lisätä, että?

752
00:59:16,010 --> 00:59:23,170
Kanssa pino oli indeksin kokoa, tämä se ei ole aivan niin.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Olen q.head--tai - >> q.strings? >> Joo.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPASITEETTI]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Me varmaan laittaa sulkeet ympärillä

756
00:59:42,740 --> 00:59:48,830
jotta saamme tarvittavat edelle ja niin se cleart kaikille.

757
00:59:48,830 --> 00:59:55,800
Ja asetetaan se tasa-arvoisia? >> STR? >> STR. Suuri.

758
00:59:55,800 --> 01:00:00,160
Ja nyt, mitä on viimeinen asia, että meidän täytyy tehdä?

759
01:00:00,160 --> 01:00:06,780
Aivan kuten teimme pinossa. >> Increment koko? >> Increment kokoa.

760
01:00:06,780 --> 01:00:13,830
Boom. Ja sitten, koska käynnistin koodi juuri palannut vääriä oletuksena,

761
01:00:13,830 --> 01:00:27,460
haluamme muuttaa arvoksi true, jos kaikki menee läpi ja kaikki menee hyvin.

762
01:00:27,460 --> 01:00:33,050
Selvä. Se on paljon tietoa osiossa.

763
01:00:33,050 --> 01:00:39,480
Emme ole aivan yli. Haluamme puhua todella nopeasti noin yksin-linkitettyjen listojen.

764
01:00:39,480 --> 01:00:44,010
Laitan tämän niin voimme palata siihen myöhemmin.

765
01:00:44,010 --> 01:00:50,850
Mutta mennään takaisin meidän esityksen vain muutaman dioja.

766
01:00:50,850 --> 01:00:53,790
Joten Aseta jonoon on TODO, nyt olemme tehneet sen.

767
01:00:53,790 --> 01:00:57,430
>> Nyt katsomaan yksin-linkitettyjen listojen.

768
01:00:57,430 --> 01:01:00,040
Puhuimme näistä vähän enemmän luennossa.

769
01:01:00,040 --> 01:01:02,540
Kuinka moni teistä nähnyt demon, jossa meillä oli ihmisiä

770
01:01:02,540 --> 01:01:08,220
hankalasti osoittavat toisilleen ja hallussapidosta numeroita? >> Olin siinä.

771
01:01:08,220 --> 01:01:16,620
>> Mitä olette mieltä? Oliko se toivottavasti selventäisi nämä vähän?

772
01:01:16,620 --> 01:01:25,990
Kanssa luettelon, käy ilmi, että me käsittelemme tätä tyyppiä aiomme kutsua solmuun.

773
01:01:25,990 --> 01:01:32,520
Kun taas jono ja pino meillä oli tietueet, että olimme kutsumme jono pino,

774
01:01:32,520 --> 01:01:34,860
meillä oli nämä uudet jono pino tyyppejä,

775
01:01:34,860 --> 01:01:39,240
Tässä lista on todella vain koostuu joukko solmuja.

776
01:01:39,240 --> 01:01:45,920
Samalla tavoin, että jouset ovat vain joukko merkkiä kaikki riviin vierekkäin.

777
01:01:45,920 --> 01:01:50,650
Linkitetty lista on vain solmun ja toisen solmun ja toisen solmun ja toisen solmun.

778
01:01:50,650 --> 01:01:55,080
Ja sen sijaan Smashing kaikki solmut yhteen ja tallentamalla ne vierekkäisesti

779
01:01:55,080 --> 01:01:58,090
kaikki aivan toistensa muistiin,

780
01:01:58,090 --> 01:02:04,470
ottaa tämä seuraava osoitin antaa meille mahdollisuuden tallentaa solmut missä, satunnaisesti.

781
01:02:04,470 --> 01:02:10,500
Ja sitten sellainen lanka ne kaikki yhteen kohtaan yhdestä seuraavaan.

782
01:02:10,500 --> 01:02:15,850
>> Ja mikä oli suuri etu, että tämä oli yli array?

783
01:02:15,850 --> 01:02:21,680
Yli varastointi kaiken vierekkäin aivan kiinni vierekkäin?

784
01:02:21,680 --> 01:02:24,190
Muistatko? Niin? >> Dynaaminen muisti jako?

785
01:02:24,190 --> 01:02:27,220
>> Dynaaminen muisti jako missä mielessä?

786
01:02:27,220 --> 01:02:31,780
[Student] Tässä voit pitää tehdä se isompi ja sinun ei tarvitse siirtää koko array?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Aivan. Joten array, kun haluat laittaa uuden elementin keskellä,

788
01:02:40,940 --> 01:02:45,320
sinun täytyy siirtää kaiken tehdä tilaa.

789
01:02:45,320 --> 01:02:47,880
Ja kuten puhuimme kanssa jonoon,

790
01:02:47,880 --> 01:02:50,080
Siksi pidämme että pää osoitin,

791
01:02:50,080 --> 01:02:52,050
jotta emme jatkuvasti muuttuvia asioita.

792
01:02:52,050 --> 01:02:54,520
Koska se saa kallista, jos sinulla on iso joukko

793
01:02:54,520 --> 01:02:57,130
ja olet jatkuvasti tekee näitä satunnaisia ​​lisäyksiä.

794
01:02:57,130 --> 01:03:00,820
Kun taas listan, sinun tarvitsee vain heittää se uusi solmu,

795
01:03:00,820 --> 01:03:06,330
Säädä osoittimet, ja olet valmis.

796
01:03:06,330 --> 01:03:10,940
Mitä imee tästä?

797
01:03:10,940 --> 01:03:16,830
Paitsi että se ei ole niin helppoa työstää kuin array? Niin?

798
01:03:16,830 --> 01:03:22,980
[Daniel] No, kai se on paljon vaikeampaa saada erityinen elementti linkitetty lista?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Et voi vain hypätä mielivaltainen elementti keskellä sinun linkitetty lista.

800
01:03:30,470 --> 01:03:33,800
Miten sinun täytyy tehdä sen sijaan? >> Sinun täytyy selata koko juttu.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Joo. Sinun täytyy käydä läpi yksi kerrallaan, yksi kerrallaan.

802
01:03:35,660 --> 01:03:38,480
Se on valtava - se tuskaa.

803
01:03:38,480 --> 01:03:41,550
Mikä muu - on toinen kaatuminen tähän.

804
01:03:41,550 --> 01:03:45,340
[Basil] Et voi mennä eteenpäin ja taaksepäin? Sinun täytyy mennä yhteen suuntaan?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Joo. Miten siis ratkaista se joskus?

806
01:03:48,570 --> 01:03:53,370
[Basil] Kahdesti-linkitettyjä listoja? >> Aivan. On kaksoislaimennettu linkitettyjä listoja.

807
01:03:53,370 --> 01:03:55,540
Myös - Anteeksi?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Onko se sama kuin käyttämällä pred asia -

809
01:03:57,620 --> 01:04:01,090
Muistin juuri, ei se, mitä pred asia on?

810
01:04:01,090 --> 01:04:05,850
Eikö se välillä kaksinkertaisesti ja yksin?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Katsokaamme mitä hän oli tekemässä.

812
01:04:10,020 --> 01:04:15,760
Joten tässä sitä mennään. Tässä lista koodin.

813
01:04:15,760 --> 01:04:25,620
Täällä meillä on predptr, täällä. Tätäkö puhuit?

814
01:04:25,620 --> 01:04:30,750
Joten tämä oli - hän vapauttaa luettelo ja hän yrittää tallentaa osoittimen siihen.

815
01:04:30,750 --> 01:04:35,000
Tämä ei ole kaksinkertaisesti, yksittäin liitetty-listat.

816
01:04:35,000 --> 01:04:40,090
Voimme puhua tästä myöhemmin lisää, koska tämä puhuu vapauttaa lista

817
01:04:40,090 --> 01:04:42,900
ja haluan näyttää joitakin muita juttuja ensin.

818
01:04:42,900 --> 01:04:51,480
mutta se on vain - se muistaa arvoa PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Voi, se on edeltävän osoitin? >> Joo.

820
01:04:54,170 --> 01:05:04,070
Jotta voimme kasvattaa ptr itsensä ennen kuin sitten vapaa mitä predptr on.

821
01:05:04,070 --> 01:05:09,130
Koska emme voi ilmaiseksi ptr ja soita ptr = ptr seuraavaksi, eikö?

822
01:05:09,130 --> 01:05:11,260
Se olisi huono.

823
01:05:11,260 --> 01:05:20,940
Joten katsotaanpas, takaisin tämä kaveri.

824
01:05:20,940 --> 01:05:23,900
>> Muut huono puoli luetteloista on, että kun taas array

825
01:05:23,900 --> 01:05:26,520
meillä on vain kaikki elementit itse pinottu toistensa vieressä,

826
01:05:26,520 --> 01:05:29,050
Täällä myös ottaneet käyttöön tämän osoitin.

827
01:05:29,050 --> 01:05:34,060
Joten siellä lisää kimpale muistia että emme ottaa käyttöön

828
01:05:34,060 --> 01:05:37,910
jokaisen elementin että olemme varastointi listalta.

829
01:05:37,910 --> 01:05:40,030
Saamme joustavuutta, mutta se tulee kalliiksi.

830
01:05:40,030 --> 01:05:42,230
Sen mukana tulee tällä kertaa kustannuksia,

831
01:05:42,230 --> 01:05:45,270
ja se tulee tämän muistin hinta liian.

832
01:05:45,270 --> 01:05:47,800
Aika siinä mielessä, että meidän on nyt käytävä läpi jokainen alkio

833
01:05:47,800 --> 01:05:58,670
löytää yksi indeksi 10, tai että olisi ollut indeksi 10 array.

834
01:05:58,670 --> 01:06:01,230
>> Vain todella nopeasti, kun kaavio nämä luettelot,

835
01:06:01,230 --> 01:06:05,980
tyypillisesti pidämme kiinni pään luettelon tai ensimmäinen osoitin luettelon

836
01:06:05,980 --> 01:06:08,010
ja huomata, että tämä on totta osoitin.

837
01:06:08,010 --> 01:06:11,100
Se on vain 4 tavua. Se ei ole varsinainen solmu itse.

838
01:06:11,100 --> 01:06:17,120
Niin näet, että sillä ei ole int arvoa siinä, ei ensi osoittimen siihen.

839
01:06:17,120 --> 01:06:20,790
Se on kirjaimellisesti vain osoitin.

840
01:06:20,790 --> 01:06:23,550
Se tulee osoittamaan jotain, joka on todellinen solmu struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] osoittimen nimeltään solmu? >> Tämä on - no. Tämä on osoitin jotain tyyppiä solmun.

842
01:06:28,480 --> 01:06:32,540
Se on osoitin solmuun struct. >> Ai, okei.

843
01:06:32,540 --> 01:06:36,870
Kaavio vasemmalla, koodi oikealla.

844
01:06:36,870 --> 01:06:42,190
Voimme asettaa sen null, mikä on hyvä tapa aloittaa.

845
01:06:42,190 --> 01:06:49,850
Kun kaavio on, sinulla on joko kirjoittaa sen nolla tai laittaa linjan läpi tuolla tavalla.

846
01:06:49,850 --> 01:06:53,910
>> Yksi helpoimmista tavoista työskennellä luetteloihin,

847
01:06:53,910 --> 01:06:57,430
ja pyydämme et niin prepend ja liittää nähdä erot kahden,

848
01:06:57,430 --> 01:07:01,320
mutta panemalla on varmasti helpompaa.

849
01:07:01,320 --> 01:07:05,790
Kun alkuun lisättävä, tämä on silloin, kun - kun prepend (7),

850
01:07:05,790 --> 01:07:10,050
mennä ja luoda solmu struct

851
01:07:10,050 --> 01:07:13,870
ja asetat ensin osoitat sitä, koska nyt, koska me etuliitteen sitä,

852
01:07:13,870 --> 01:07:17,240
se tulee olemaan alussa luettelosta.

853
01:07:17,240 --> 01:07:22,540
Jos me prepend (3), joka luo toisen solmun, mutta nyt 3 tulee ennen 7.

854
01:07:22,540 --> 01:07:31,130
Joten olemme pohjimmiltaan kiire päälle listalta.

855
01:07:31,130 --> 01:07:34,720
Nyt voit nähdä, että prepend, joskus ihmiset kutsuvat sitä työntää,

856
01:07:34,720 --> 01:07:39,600
koska olet työntää uuden elementin päälle luettelossa.

857
01:07:39,600 --> 01:07:43,270
Se on myös helppo poistaa edessä luettelon.

858
01:07:43,270 --> 01:07:45,650
Joten ihmiset usein soittaa että pop.

859
01:07:45,650 --> 01:07:52,200
Ja tällä tavalla, voit emuloida pinon avulla linkitetty lista.

860
01:07:52,200 --> 01:07:57,880
Oho. Anteeksi, nyt olemme joutumassa append. Joten tässä me etuliitteen (7), nyt me prepend (3).

861
01:07:57,880 --> 01:08:02,600
Jos me etuliitteen jotakin muuta päälle tähän luetteloon, jos me etuliitteen (4),

862
01:08:02,600 --> 01:08:06,540
Sitten olisimme 4 ja sitten 3 ja sitten 7.

863
01:08:06,540 --> 01:08:14,220
Joten voisimme pop ja poistaa 4, poista 3, poista 7.

864
01:08:14,220 --> 01:08:16,500
Usein enemmän intuitiivinen tapa ajatella tätä on kanssa append.

865
01:08:16,500 --> 01:08:20,310
Joten olen kaaviona mitä se näyttää kanssa liittää tänne.

866
01:08:20,310 --> 01:08:23,380
Tässä liitteenä (7) ei näytä mitään erilaista

867
01:08:23,380 --> 01:08:25,160
koska siellä on vain yksi elementti luettelossa.

868
01:08:25,160 --> 01:08:28,620
Ja liittämällä (3) laittaa sen lopussa.

869
01:08:28,620 --> 01:08:31,020
Ehkä näet nyt temppu append

870
01:08:31,020 --> 01:08:36,600
on, että koska tiedämme vain jos listan alkuun on,

871
01:08:36,600 --> 01:08:39,450
liittämään listan sinun täytyy kävellä koko matkan läpi listan

872
01:08:39,450 --> 01:08:46,500
päästä loppuun, lopeta, sitten rakentaa solmu ja jysäyttää kaiken alas.

873
01:08:46,500 --> 01:08:50,590
Kytke kaikki jutut ylös.

874
01:08:50,590 --> 01:08:55,170
Joten prepend, kuten juuri repi tämän todella nopeasti,

875
01:08:55,170 --> 01:08:58,170
kun alkuun lisättävä luetteloon, se on melko yksinkertainen.

876
01:08:58,170 --> 01:09:02,960
>> Teet uuden solmun, jota jossain dynaamisen muistin jakamista.

877
01:09:02,960 --> 01:09:09,830
Joten tässä Teemme solmun struct käyttäen malloc.

878
01:09:09,830 --> 01:09:14,710
Joten malloc käytämme siksi että saat varattu muisti meille myöhemmin

879
01:09:14,710 --> 01:09:20,350
koska emme halua tätä - haluamme tätä muistia kestävät pitkään.

880
01:09:20,350 --> 01:09:25,350
Ja saamme osoitin muistitilaa että me juuri jaettu.

881
01:09:25,350 --> 01:09:29,260
Käytämme koko solmun, emme Yhteenvetona kentät.

882
01:09:29,260 --> 01:09:31,899
Emme manuaalisesti tuottaa tavujen,

883
01:09:31,899 --> 01:09:39,750
vaan käytämme sizeof jotta tiedämme saamme sopiva määrä tavuja.

884
01:09:39,750 --> 01:09:43,660
Teemme Testaa että malloc puhelu onnistui.

885
01:09:43,660 --> 01:09:47,939
Tämä on jotain haluat tehdä yleensä.

886
01:09:47,939 --> 01:09:52,590
On nykyaikaiset koneet, loppumassa muisti ei ole jotain, joka on helppo

887
01:09:52,590 --> 01:09:56,610
ellet jaetaan tonneittain tavaraa ja tehdä valtava luettelo,

888
01:09:56,610 --> 01:10:02,220
mutta jos olet rakentamassa kamaa, sano, kuten iPhone tai Android-

889
01:10:02,220 --> 01:10:05,230
sinulla on rajoitettu muisti resursseja, varsinkin jos olet tekemässä jotain intensiivistä.

890
01:10:05,230 --> 01:10:08,300
Joten se on hyvä päästä käytäntöön.

891
01:10:08,300 --> 01:10:10,510
>> Huomaa, että olen käyttänyt pari eri toimintoja täällä

892
01:10:10,510 --> 01:10:12,880
että olet nähnyt, jotka ovat tavallaan uusia.

893
01:10:12,880 --> 01:10:15,870
Joten fprintf on aivan kuten printf

894
01:10:15,870 --> 01:10:21,320
paitsi sen ensimmäinen väite on virta, jolle haluat tulostaa.

895
01:10:21,320 --> 01:10:23,900
Tässä tapauksessa haluamme tulostaa keskivirhe merkkijono

896
01:10:23,900 --> 01:10:29,410
joka on erilainen kuin tavallinen outstream.

897
01:10:29,410 --> 01:10:31,620
Oletuksena se näkyy samassa paikassa.

898
01:10:31,620 --> 01:10:34,600
Se myös tulostaa päätteeseen, mutta voit -

899
01:10:34,600 --> 01:10:38,790
käyttäen näitä komentoja opit, uudelleenohjaus tekniikoita

900
01:10:38,790 --> 01:10:42,290
opit vuonna Tommyn video Harjoitus 4, voit ohjata sen

901
01:10:42,290 --> 01:10:47,900
eri alueilla poistu, täällä, poistuu ohjelman.

902
01:10:47,900 --> 01:10:50,440
Se on pohjimmiltaan kuin palaamassa tärkeimmistä,

903
01:10:50,440 --> 01:10:53,600
paitsi käytämme exit koska täällä paluu ei tee mitään.

904
01:10:53,600 --> 01:10:57,140
Emme ole tärkein, joten paluu ei poistu ohjelmaa kuten haluamme.

905
01:10:57,140 --> 01:11:03,020
Niinpä käytämme exit toiminto ja anna se virhekoodi.

906
01:11:03,020 --> 01:11:11,890
Sitten täällä asetamme uuden solmun arvon alalla, sen minä alan olla yhtä i, ja sitten me lanka sen ylös.

907
01:11:11,890 --> 01:11:15,530
Asetimme uuden solmun vieressä osoitin osoittamaan ensinnäkin,

908
01:11:15,530 --> 01:11:20,460
ja sitten ensimmäinen nyt osoittamaan uuteen solmuun.

909
01:11:20,460 --> 01:11:25,120
Nämä ensimmäiset koodiriviä, olemme todella rakentaa uuden solmun.

910
01:11:25,120 --> 01:11:27,280
Ei kaksi viimeistä riviä tätä toimintoa, mutta ensimmäiset.

911
01:11:27,280 --> 01:11:30,290
Voit itse vetää ulos toiminnon tulee auttaja toimintoa.

912
01:11:30,290 --> 01:11:32,560
Tämä on usein mitä teen on, vedän sen ulos funktio,

913
01:11:32,560 --> 01:11:36,040
Kutsun sitä jotain build solmu,

914
01:11:36,040 --> 01:11:40,410
ja että pitää prepend toiminto melko pieni, se on vain 3 riviä sitten.

915
01:11:40,410 --> 01:11:48,710
Olen soittaa minun rakentaa solmuun toiminto, ja sitten minä johdin kaiken ylös.

916
01:11:48,710 --> 01:11:51,970
>> Viimeinen asia haluan näyttää sinulle,

917
01:11:51,970 --> 01:11:54,030
ja annan sinun tehdä append ja kaikki omalla,

918
01:11:54,030 --> 01:11:57,500
on se, miten iteroida yli luettelo.

919
01:11:57,500 --> 01:12:00,780
On olemassa joukko erilaisia ​​tapoja iteroida yli luettelo.

920
01:12:00,780 --> 01:12:03,140
Tässä tapauksessa aiomme löytää pituuden luettelon.

921
01:12:03,140 --> 01:12:06,570
Joten aloitamme pituus = 0.

922
01:12:06,570 --> 01:12:11,580
Tämä on hyvin samanlainen kirjoittamiseen strlen varten merkkijono.

923
01:12:11,580 --> 01:12:17,780
Tämä on mitä haluan näyttää, tämä silmukka täällä.

924
01:12:17,780 --> 01:12:23,530
Se näyttää jotenkin outoja, se ei ole tavallista int i = 0, i <riippumatta, i + +.

925
01:12:23,530 --> 01:12:34,920
Sen sijaan se alustetaan meidän muuttuja n on listan alussa.

926
01:12:34,920 --> 01:12:40,620
Ja sitten kun meidän iteraattori muuttuja ei ole tyhjä, pidämme menossa.

927
01:12:40,620 --> 01:12:46,340
Tämä johtuu siitä, sopimuksen mukaan, lopussa meidän luettelo on tyhjä.

928
01:12:46,340 --> 01:12:48,770
Ja sitten kasvattaa, eikä tee + +,

929
01:12:48,770 --> 01:12:57,010
linkitetty lista ekvivalentti + + on n = n-> seuraava.

930
01:12:57,010 --> 01:13:00,410
>> Kerron täytät aukot täällä, koska olemme myöhässä.

931
01:13:00,410 --> 01:13:09,300
Mutta pitää tämä mielessä, kun työstät spellr psets.

932
01:13:09,300 --> 01:13:11,650
Linkitettyjä listoja, jos olet täytäntöön hash-taulukko,

933
01:13:11,650 --> 01:13:14,010
varmasti tulla hyvin kätevä.

934
01:13:14,010 --> 01:13:21,780
Ja ottaa tämä idiomi kierrättämiseksi yli asioita tekee elämästä paljon helpompaa, toivottavasti.

935
01:13:21,780 --> 01:13:25,910
Kaikki kysymykset, nopeasti?

936
01:13:25,910 --> 01:13:28,920
[Sam] Aiotteko lähettää täytetty SLL ja SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Joo. Lähetän ulos valmiiksi diat ja valmiiksi SLL pino ja queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]