1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [§ 6: Mindre Komfortabel]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Dette er CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
OK. Velkommen til § 6.

5
00:00:11,840 --> 00:00:14,690
Denne uken skal vi snakke om datastrukturer i snitt,

6
00:00:14,690 --> 00:00:19,780
først og fremst fordi denne ukens problem satt på spellr

7
00:00:19,780 --> 00:00:24,410
gjør en hel haug med forskjellige data struktur leting.

8
00:00:24,410 --> 00:00:26,520
Det er en haug med forskjellige måter du kan gå med problemet sett,

9
00:00:26,520 --> 00:00:31,570
og jo flere datastrukturer du vet om, de mer kule ting du kan gjøre.

10
00:00:31,570 --> 00:00:34,990
>> Så la oss komme i gang. Først skal vi snakke om stabler,

11
00:00:34,990 --> 00:00:37,530
bunken og kø datastrukturer som vi kommer til å snakke om.

12
00:00:37,530 --> 00:00:40,560
Stabler og køer er virkelig nyttig når vi begynner å snakke om grafer,

13
00:00:40,560 --> 00:00:44,390
som vi ikke kommer til å gjøre så mye av akkurat nå.

14
00:00:44,390 --> 00:00:52,820
Men de er veldig bra å forstå en av de store fundamentale datastrukturer i CS.

15
00:00:52,820 --> 00:00:54,880
Beskrivelsen i oppgavesettet spesifikasjonen,

16
00:00:54,880 --> 00:00:59,260
Hvis du drar den opp, snakker om stabler beslektet med

17
00:00:59,260 --> 00:01:05,239
bunken av spisesteder skuffer som du har i kantina på spisesalene

18
00:01:05,239 --> 00:01:09,680
der når dining personalet kommer og setter dining skuffer ut etter at de har renset dem,

19
00:01:09,680 --> 00:01:12,000
de stable dem oppå hverandre.

20
00:01:12,000 --> 00:01:15,050
Og så når barna kommer i å få mat,

21
00:01:15,050 --> 00:01:19,490
de trekker skuffene ut, først den øverste, så den under det, deretter en under det.

22
00:01:19,490 --> 00:01:25,190
Så, i kraft, er den første skuffen som dining personalet legger ned den siste som blir tatt av.

23
00:01:25,190 --> 00:01:32,330
Den siste som dining personalet satt på er den første som blir tatt av til middag.

24
00:01:32,330 --> 00:01:38,100
I oppgavesettet er spec, som du kan laste ned hvis du ikke allerede har gjort,

25
00:01:38,100 --> 00:01:46,730
vi snakker om modellering en stabel data stucture bruker denne typen struct.

26
00:01:46,730 --> 00:01:51,070
>> Så det vi har her, er dette likt det som ble presentert i foredraget,

27
00:01:51,070 --> 00:01:58,120
bortsett fra i foredraget presenterte vi dette med ints i motsetning til char * s.

28
00:01:58,120 --> 00:02:06,250
Dette kommer til å bli en stabel som lagrer hva?

29
00:02:06,250 --> 00:02:09,009
Daniel? Hva er vi lagrer i denne bunken?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Vi lagrer strenger i denne bunken, akkurat.

31
00:02:15,260 --> 00:02:20,950
Alt du trenger å ha for å skape en stabel er en matrise

32
00:02:20,950 --> 00:02:23,920
av en bestemt kapasitet, som i dette tilfellet,

33
00:02:23,920 --> 00:02:28,020
Kapasiteten skal være i store bokstaver fordi det er en konstant.

34
00:02:28,020 --> 00:02:36,340
Og da i tillegg til matrisen, alt vi trenger å spore gjeldende størrelsen på matrisen.

35
00:02:36,340 --> 00:02:38,980
En ting å merke seg her som er litt kult

36
00:02:38,980 --> 00:02:47,060
er at vi skaper den stablet datastrukturen på toppen av en annen datastruktur, matrisen.

37
00:02:47,060 --> 00:02:50,110
Det er forskjellige måter å implementere stabler.

38
00:02:50,110 --> 00:02:54,250
Vi vil ikke gjøre det helt ennå, men forhåpentligvis etter å gjøre den koblede-liste problemer,

39
00:02:54,250 --> 00:03:00,520
vil du se hvordan du enkelt kan implementere en bunke på toppen av en lenket liste også.

40
00:03:00,520 --> 00:03:02,640
Men for nå, vil vi holde oss til arrays.

41
00:03:02,640 --> 00:03:06,350
Så igjen, er alt vi trenger en matrise og vi trenger bare å spore størrelsen på tabellen.

42
00:03:06,350 --> 00:03:09,850
[Sam] Beklager, hvorfor er det at du sa bunken er på toppen av strengene?

43
00:03:09,850 --> 00:03:13,440
For meg virker det som strengene er i stabelen.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Vi skaper, vi tar vårt utvalg datastruktur -

45
00:03:16,790 --> 00:03:22,130
det er et stort spørsmål. Så spørsmålet er hvorfor, for folk som ser dette på nettet,

46
00:03:22,130 --> 00:03:24,140
hvorfor vi sier at bunken er på toppen av strengene,

47
00:03:24,140 --> 00:03:27,990
fordi her ser det ut som strengene er inne i bunken?

48
00:03:27,990 --> 00:03:31,050
Som er helt tilfelle.

49
00:03:31,050 --> 00:03:34,660
Hva jeg siktet til var at vi har fått en rekke data struktur.

50
00:03:34,660 --> 00:03:39,290
Vi har fått en rekke char * s, denne rekke strenger,

51
00:03:39,290 --> 00:03:45,300
og vi kommer til å legge til at for å skape den stablet datastruktur.

52
00:03:45,300 --> 00:03:48,620
>> Så en stabel er litt mer komplisert enn en matrise.

53
00:03:48,620 --> 00:03:51,890
Vi kan bruke en matrise for å bygge en stabel.

54
00:03:51,890 --> 00:03:55,810
Så det er der vi sier at bunken er bygget på toppen av en matrise.

55
00:03:55,810 --> 00:04:02,510
Likeledes, som jeg sa tidligere, kan vi bygge en stabel på toppen av en lenket liste.

56
00:04:02,510 --> 00:04:04,960
Istedenfor å bruke en matrise for å holde våre elementer,

57
00:04:04,960 --> 00:04:10,070
vi kunne bruke en lenket liste for å holde våre elementer og bygge stabelen rundt det.

58
00:04:10,070 --> 00:04:12,420
La oss gå gjennom et par eksempler, se på noen kode,

59
00:04:12,420 --> 00:04:14,960
å se hva som faktisk skjer her.

60
00:04:14,960 --> 00:04:23,400
På venstre side, har jeg kastet ned hva som stakk struct ville se ut i minnet

61
00:04:23,400 --> 00:04:28,330
hvis kapasiteten ble # definert å være fire.

62
00:04:28,330 --> 00:04:33,490
Vi har våre fire-element char * array.

63
00:04:33,490 --> 00:04:38,110
Vi har strenger [0], strenger [1], strenger [2], strenger [3],

64
00:04:38,110 --> 00:04:43,800
og deretter den siste plassen for vår størrelse heltall.

65
00:04:43,800 --> 00:04:46,270
Betyr dette fornuftig? Okay.

66
00:04:46,270 --> 00:04:48,790
Dette er hva som skjer hvis det jeg gjør på høyre side,

67
00:04:48,790 --> 00:04:55,790
som vil være min kode, er å bare erklære en struct, et stablet struct heter s.

68
00:04:55,790 --> 00:05:01,270
Dette er hva vi får. Den legger ned denne fotavtrykk i minnet.

69
00:05:01,270 --> 00:05:05,590
Det første spørsmålet her er hva som er innholdet i denne bunken struct?

70
00:05:05,590 --> 00:05:09,250
Akkurat nå er de ingenting, men de er ikke helt ingenting.

71
00:05:09,250 --> 00:05:13,300
De er denne slags søppel. Vi har ingen anelse om hva som er i dem.

72
00:05:13,300 --> 00:05:17,000
Når vi erklærer stable s, vi bare kaster det ned på toppen av minne.

73
00:05:17,000 --> 00:05:19,840
Det er typen som å erklære int i og ikke initialisere den.

74
00:05:19,840 --> 00:05:21,730
Du vet ikke hva som er der. Du kan lese hva som er der,

75
00:05:21,730 --> 00:05:27,690
men det kan ikke være super nyttig.

76
00:05:27,690 --> 00:05:32,680
En ting du ønsker å alltid huske å gjøre er initialisere hva må initialiseres.

77
00:05:32,680 --> 00:05:35,820
I dette tilfellet skal vi initialisere størrelsen til å være null,

78
00:05:35,820 --> 00:05:39,960
fordi det kommer til å vise seg å være svært viktig for oss.

79
00:05:39,960 --> 00:05:43,450
Vi kunne gå videre og starte alle pekere, alle char * s,

80
00:05:43,450 --> 00:05:49,670
å være noen forståelig verdi, sannsynligvis null.

81
00:05:49,670 --> 00:05:58,270
Men det er ikke helt nødvendig at vi gjør det.

82
00:05:58,270 --> 00:06:04,200
>> Nå, de to viktigste operasjoner på stabler er?

83
00:06:04,200 --> 00:06:07,610
Noen som husker fra foredraget hva du gjør med stabler? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Pushing og spratt? >> Nettopp.

85
00:06:09,700 --> 00:06:13,810
Skyve og spratt er de to viktigste operasjoner på stabler.

86
00:06:13,810 --> 00:06:17,060
Og hva gjør push? >> Det setter noe på toppen

87
00:06:17,060 --> 00:06:19,300
av stabelen, og deretter dukker det tar av.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Nettopp. Så presser presser noe på toppen av bunken.

89
00:06:23,150 --> 00:06:27,700
Det er som servering personalet å sette en spisestue skuff ned på disken.

90
00:06:27,700 --> 00:06:33,630
Og spratt tar en spisestue skuff ut av bunken.

91
00:06:33,630 --> 00:06:36,460
La oss gå gjennom et par eksempler på hva som skjer

92
00:06:36,460 --> 00:06:39,720
når vi skyver ting inn i bunken.

93
00:06:39,720 --> 00:06:45,110
Hvis vi skulle presse strengen 'Hei' på stacken,

94
00:06:45,110 --> 00:06:49,760
Dette er hva vår diagram ville se ut nå.

95
00:06:49,760 --> 00:06:53,410
Se hva som skjer?

96
00:06:53,410 --> 00:06:56,530
Vi presset inn i det første element i strenger matrise

97
00:06:56,530 --> 00:07:01,420
og vi upped vår størrelse teller for å være en.

98
00:07:01,420 --> 00:07:05,340
Så hvis vi ser på forskjellen mellom de to lysbilder, her var 0, her før push.

99
00:07:05,340 --> 00:07:08,690
Her er etter push.

100
00:07:08,690 --> 00:07:13,460
Før push, etter push.

101
00:07:13,460 --> 00:07:16,860
Og nå har vi ett element i stacken.

102
00:07:16,860 --> 00:07:20,970
Det er strengen "hallo", og det er det.

103
00:07:20,970 --> 00:07:24,440
Alt annet i rekken, i vår strenger array, er fortsatt søppel.

104
00:07:24,440 --> 00:07:27,070
Vi har ikke initialisert den.

105
00:07:27,070 --> 00:07:29,410
La oss si at vi skyver en annen streng på stacken.

106
00:07:29,410 --> 00:07:32,210
Vi kommer til å presse "verden" på dette tidspunktet.

107
00:07:32,210 --> 00:07:35,160
Så du kan se "verden" her går på toppen av "Hallo",

108
00:07:35,160 --> 00:07:40,040
og størrelsen teller går opp til 2.

109
00:07:40,040 --> 00:07:44,520
Nå kan vi presse "CS50", og det vil gå på toppen igjen.

110
00:07:44,520 --> 00:07:51,110
Hvis vi går tilbake, kan du se hvordan vi presser ting på toppen av bunken.

111
00:07:51,110 --> 00:07:53,320
Og nå får vi til pop.

112
00:07:53,320 --> 00:07:58,910
Når vi popped noe ut av bunken, skjedde det?

113
00:07:58,910 --> 00:08:01,540
Noen se forskjellen? Det er ganske subtil.

114
00:08:01,540 --> 00:08:05,810
[Student] Størrelsen. >> Ja, endret størrelse.

115
00:08:05,810 --> 00:08:09,040
>> Hva annet vil du ha forventet å endre?

116
00:08:09,040 --> 00:08:14,280
[Student] Strengene, også. >> Høyre. Strengene også.

117
00:08:14,280 --> 00:08:17,110
Det viser seg at når du gjør det på denne måten,

118
00:08:17,110 --> 00:08:21,960
fordi vi ikke kopiere elementer i stacken,

119
00:08:21,960 --> 00:08:24,670
vi faktisk ikke trenger å gjøre noe, vi kan bare bruke størrelse

120
00:08:24,670 --> 00:08:28,630
å holde oversikt over hvor mange ting i matrisen vår

121
00:08:28,630 --> 00:08:33,780
slik at når vi pop igjen, igjen vi bare minske vår størrelse ned til 1.

122
00:08:33,780 --> 00:08:39,440
Det er ingen grunn til å faktisk gå inn og overskrive noe.

123
00:08:39,440 --> 00:08:41,710
Slags funky.

124
00:08:41,710 --> 00:08:46,520
Det viser seg at vi vanligvis bare la ting alene fordi det er mindre arbeid for oss å gjøre.

125
00:08:46,520 --> 00:08:50,060
Hvis vi ikke trenger å gå tilbake og overskrive noe, så hvorfor gjøre det?

126
00:08:50,060 --> 00:08:54,150
Så når vi pop dobbelt ut av bunken, er alt som betyr minske størrelsen et par ganger.

127
00:08:54,150 --> 00:08:59,120
Og igjen, dette er bare fordi vi ikke kopiere ting i stacken.

128
00:08:59,120 --> 00:09:01,320
Ja? Gå fremover.

129
00:09:01,320 --> 00:09:04,460
[Student, uforståelig] >> Og hva skjer når du trykker noe igjen?

130
00:09:04,460 --> 00:09:08,570
Når du trykker på noe nytt, ikke hvor det gå?

131
00:09:08,570 --> 00:09:12,390
Hvor går det, Basil? >> Into strenger [1]? >> Høyre.

132
00:09:12,390 --> 00:09:14,530
Hvorfor går det ikke inn strenger [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Fordi det glemte at det var noe i strenger [1] og [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Nettopp. Vår stabelen, i hovedsak, "glemte" at det var å holde på til noe

135
00:09:24,040 --> 00:09:29,480
i strenger [1] eller strenger [2], så når vi skyver "woot",

136
00:09:29,480 --> 00:09:36,670
det setter bare det inn elementet på strenger [1].

137
00:09:36,670 --> 00:09:41,590
Er det noen spørsmål om hvordan dette fungerer, på et grunnleggende nivå?

138
00:09:41,590 --> 00:09:45,160
[Sam] Så dette er ikke dynamisk på noen måte, i forhold til mengden

139
00:09:45,160 --> 00:09:47,620
eller i form av størrelsen på bunken?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Nettopp. Dette er - poenget var at dette ikke var en dynamisk growning stack.

141
00:09:56,750 --> 00:10:02,850
Dette er en stabel som kan holde, på det meste, fire char * s, på de fleste fire ting.

142
00:10:02,850 --> 00:10:07,580
Hvis vi skulle prøve og presse en femte tingen, hva tror du bør skje?

143
00:10:07,580 --> 00:10:11,870
[Studenter, uforståelige]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Nettopp. Det finnes en rekke ting som kan skje.

145
00:10:14,600 --> 00:10:19,330
Det kan muligens SEG feil, avhengig av hva vi var -

146
00:10:19,330 --> 00:10:22,530
hvordan akkurat vi implementere back-end.

147
00:10:22,530 --> 00:10:31,740
Det kan overskrive. Det kunne ha som buffer overflow som vi snakket om i klassen.

148
00:10:31,740 --> 00:10:35,240
Hva ville være den mest åpenbare ting som kan overskrives

149
00:10:35,240 --> 00:10:42,370
hvis vi prøvde å presse en ekstra ting på stacken?

150
00:10:42,370 --> 00:10:44,550
Så du nevnte en buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Hva kan være ting som ville bli skrevet over eller tråkket på

152
00:10:47,870 --> 00:10:52,320
hvis vi overflyt uhell ved å prøve å presse en ekstra ting?

153
00:10:52,320 --> 00:10:54,730
[Daniel, uforståelig] >> mulig.

154
00:10:54,730 --> 00:10:58,440
Men i utgangspunktet, hva kan skje? Hva om vi prøvde å presse en fjerde ting?

155
00:10:58,440 --> 00:11:06,220
Det kan overskrive størrelse, minst med dette minnet diagram som vi har.

156
00:11:06,220 --> 00:11:10,880
>> I oppgavesettet spesifikasjonen, som er hva vi kommer til å gjennomføre i dag,

157
00:11:10,880 --> 00:11:16,030
hva vi ønsker å gjøre er å returnere bare falsk.

158
00:11:16,030 --> 00:11:20,030
Vår trykk metoden kommer til å returnere en boolsk verdi,

159
00:11:20,030 --> 00:11:22,920
og at boolean verdi vil være sant hvis push lykkes

160
00:11:22,920 --> 00:11:29,730
og usann hvis vi ikke kan skyve noe mer fordi bunken er full.

161
00:11:29,730 --> 00:11:33,620
La oss gå gjennom en liten bit av den koden akkurat nå.

162
00:11:33,620 --> 00:11:36,400
Her er vår push-funksjon.

163
00:11:36,400 --> 00:11:40,380
Vår trykk-funksjon for en stabel kommer til å ta i strengen til å sette på stakken.

164
00:11:40,380 --> 00:11:45,820
Det kommer til å returnere true hvis strengen var vellykket presset

165
00:11:45,820 --> 00:11:51,820
på stabelen og falske ellers.

166
00:11:51,820 --> 00:11:59,740
Noen forslag på hva som kan være en god første tingen å gjøre her?

167
00:11:59,740 --> 00:12:20,630
[Sam] Hvis størrelsen er lik kapasiteten, return false?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Fin jobb.

169
00:12:23,320 --> 00:12:26,310
Hvis størrelsen er kapasiteten, vi kommer til å returnere falsk.

170
00:12:26,310 --> 00:12:29,270
Vi kan ikke sette noe mer i stacken.

171
00:12:29,270 --> 00:12:36,900
Ellers ønsker vi å sette noe på toppen av bunken.

172
00:12:36,900 --> 00:12:41,670
Hva er "toppen av bunken," i utgangspunktet?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Størrelse 0? >> Størrelse 0.

174
00:12:43,650 --> 00:12:49,990
Hva er toppen av stabelen etter at det er én ting i bunken? Missy, vet du det?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Størrelsen er én, akkurat. Du holde legge til størrelse,

176
00:12:52,720 --> 00:13:01,690
og hver gang du setter i den nye element på indeksen størrelsen på tabellen.

177
00:13:01,690 --> 00:13:05,470
Vi kan gjøre det med den slags one-liner, hvis det er fornuftig.

178
00:13:05,470 --> 00:13:11,910
Så vi har fått vår strenger array, vi kommer til å få tilgang til den på størrelsen indeksen,

179
00:13:11,910 --> 00:13:14,780
og vi bare kommer til å lagre våre char * der.

180
00:13:14,780 --> 00:13:19,340
Legg merke til hvordan det har ingen streng kopiering skjer i her,

181
00:13:19,340 --> 00:13:29,680
ingen dynamisk tildeling av minne?

182
00:13:29,680 --> 00:13:34,440
Og så Missy brakt opp det vi nå har å gjøre,

183
00:13:34,440 --> 00:13:40,570
fordi vi har lagret strengen på riktig sted i tabellen,

184
00:13:40,570 --> 00:13:49,230
og hun sa at vi måtte øke størrelsen ved en slik at vi er klare for neste push.

185
00:13:49,230 --> 00:13:53,950
Så vi kan gjøre det med s.size + +.

186
00:13:53,950 --> 00:13:59,330
På dette punktet har vi presset inn i matrisen vår. Hva er det siste vi trenger å gjøre?

187
00:13:59,330 --> 00:14:10,110
[Student] Tilbake sant. >> Tilbake sant.

188
00:14:10,110 --> 00:14:14,690
Så det er ganske enkelt, en ganske enkel kode. Ikke for mye.

189
00:14:14,690 --> 00:14:17,070
Når du har pakket hodet rundt hvordan stabelen fungerer,

190
00:14:17,070 --> 00:14:21,910
dette er ganske enkel å implementere.

191
00:14:21,910 --> 00:14:26,390
>> Nå er neste del av denne spratt en streng ut av bunken.

192
00:14:26,390 --> 00:14:29,410
Jeg kommer til å gi dere litt tid til å jobbe med dette litt.

193
00:14:29,410 --> 00:14:34,320
Det er nesten essensielt det motsatte av hva vi har gjort her i push.

194
00:14:34,320 --> 00:14:38,510
Hva jeg har gjort er faktisk - oops.

195
00:14:38,510 --> 00:14:48,160
Jeg har startet opp et apparat over her, og i apparatet,

196
00:14:48,160 --> 00:14:53,600
Jeg har trukket opp problemet satt 5-spesifikasjonen.

197
00:14:53,600 --> 00:15:02,560
Hvis vi zoome inn her, kan vi se jeg er på cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Har dere lastet ned denne koden som er plassert her, section6.zip?

199
00:15:08,590 --> 00:15:15,030
OK. Hvis du ikke har gjort det, gjøre det akkurat nå, veldig raskt.

200
00:15:15,030 --> 00:15:22,130
Jeg skal gjøre det i mitt terminal vindu.

201
00:15:22,130 --> 00:15:25,090
Jeg faktisk gjorde det her oppe. Ja.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Jeg har et spørsmål om hvorfor sa du s.string 's parentes av size = str?

203
00:15:34,730 --> 00:15:42,910
Hva er str? Er det definert et sted før, eller - oh, i char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ja, akkurat. Det var argumentet. >> Å, greit. Unnskyld.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Vi spesifiserer strengen å presse i.

206
00:15:49,470 --> 00:15:55,220
Det andre spørsmålet som kan komme opp at vi ikke egentlig snakke om her var

207
00:15:55,220 --> 00:15:58,810
vi tok for gitt at vi hadde denne variabelen kalt s

208
00:15:58,810 --> 00:16:02,710
som var i omfang og tilgjengelig for oss.

209
00:16:02,710 --> 00:16:06,960
Vi tok for gitt at s var denne bunken struct.

210
00:16:06,960 --> 00:16:08,930
Så ser tilbake på dette push-kode,

211
00:16:08,930 --> 00:16:13,450
du kan se at vi gjør ting med denne strengen som ble vedtatt i

212
00:16:13,450 --> 00:16:19,210
men da plutselig, vi tilgang s.size, som, hvor kom s kommer fra?

213
00:16:19,210 --> 00:16:23,020
I koden som vi kommer til å se på i avsnittet arkivet

214
00:16:23,020 --> 00:16:27,100
og deretter ting som du skal gjøre i ditt problem setter,

215
00:16:27,100 --> 00:16:32,440
vi har gjort vår stabelen struct en global variabel

216
00:16:32,440 --> 00:16:36,380
slik at vi kan ha tilgang til den i alle våre ulike funksjoner

217
00:16:36,380 --> 00:16:40,630
uten å måtte manuelt passerer det rundt og gi det ved henvisning,

218
00:16:40,630 --> 00:16:44,870
gjøre alt den slags ting til det.

219
00:16:44,870 --> 00:16:52,280
Vi bare juks litt, om du vil, for å gjøre ting bedre.

220
00:16:52,280 --> 00:16:57,430
Og det er noe vi gjør her fordi det er for moro, er det lettere.

221
00:16:57,430 --> 00:17:02,800
Ofte vil du se folk gjøre dette hvis de har en stor datastruktur

222
00:17:02,800 --> 00:17:07,750
som blir operert på i sitt program.

223
00:17:07,750 --> 00:17:09,560
>> La oss gå tilbake over til apparatet.

224
00:17:09,560 --> 00:17:15,240
Fikk alle med hell få section6.zip?

225
00:17:15,240 --> 00:17:20,440
Alle pakk den med unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Hvis du går inn i § 6 katalog -

227
00:17:27,200 --> 00:17:29,220
aah, over alt -

228
00:17:29,220 --> 00:17:32,840
og du liste over hva som er her, ser du at du har tre forskjellige. c-filer.

229
00:17:32,840 --> 00:17:38,350
Du har en kø, en sll, som er enkeltvis-lenket liste, og en stabel.

230
00:17:38,350 --> 00:17:44,600
Hvis du åpner opp stack.c,

231
00:17:44,600 --> 00:17:47,330
du kan se at vi har fått denne struct definert for oss,

232
00:17:47,330 --> 00:17:51,330
den eksakte struct at vi bare snakket om i lysbildene.

233
00:17:51,330 --> 00:17:56,340
Vi har fått vår globale variable for stabelen,

234
00:17:56,340 --> 00:18:00,110
vi har fått vår push-funksjon,

235
00:18:00,110 --> 00:18:04,230
og så har vi vår pop-funksjon.

236
00:18:04,230 --> 00:18:08,320
Jeg skal sette inn koden for skyver opp på lysbildet her,

237
00:18:08,320 --> 00:18:10,660
men det jeg ønsker dere å gjøre er, etter beste evne,

238
00:18:10,660 --> 00:18:13,790
gå og gjennomføre pop-funksjonen.

239
00:18:13,790 --> 00:18:18,480
Når du har installert den, kan du kompilere dette med at bunken,

240
00:18:18,480 --> 00:18:22,540
og deretter kjøre den resulterende stabelen kjørbar,

241
00:18:22,540 --> 00:18:28,390
og som vil kjøre alle denne testen koden her nede som er i main.

242
00:18:28,390 --> 00:18:31,060
Og viktigste tar seg av faktisk gjør push og pop samtaler

243
00:18:31,060 --> 00:18:33,220
og sørge for at alt går gjennom all right.

244
00:18:33,220 --> 00:18:36,820
Det initialiserer også stakkstørrelsen her

245
00:18:36,820 --> 00:18:39,780
slik at du ikke trenger å bekymre deg initialisering det.

246
00:18:39,780 --> 00:18:42,310
Du kan anta at det har vært riktig initialisert

247
00:18:42,310 --> 00:18:48,000
av den tiden du tilgang til den i pop-funksjonen.

248
00:18:48,000 --> 00:18:53,530
Gjør det fornuftig?

249
00:18:53,530 --> 00:19:00,100
Så her går vi. Det er push-koden.

250
00:19:00,100 --> 00:19:13,210
Jeg skal gi dere 5 eller 10 minutter.

251
00:19:13,210 --> 00:19:15,690
Og hvis du har noen spørsmål i mellomtiden mens du koder,

252
00:19:15,690 --> 00:19:17,710
kan du be dem høyt.

253
00:19:17,710 --> 00:19:23,080
Så hvis du kommer til et fast punkt, bare spør.

254
00:19:23,080 --> 00:19:26,030
Gi meg beskjed, la alle andre vet.

255
00:19:26,030 --> 00:19:28,160
Arbeid med din nabo også.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Vi bare implementere pop akkurat nå? >> Bare pop.

257
00:19:30,360 --> 00:19:34,200
Selv om du kan kopiere gjennomføringen av push hvis du ønsker

258
00:19:34,200 --> 00:19:37,780
slik at testing vil fungere.

259
00:19:37,780 --> 00:19:41,940
Fordi det er vanskelig å teste ting å komme inn -

260
00:19:41,940 --> 00:19:49,030
eller, er det vanskelig å teste spratt ting ut av en stabel hvis det ikke er noe i bunken til å begynne med.

261
00:19:49,030 --> 00:19:55,250
>> Hva er pop ment å være tilbake? Elementet fra toppen av stabelen.

262
00:19:55,250 --> 00:20:01,260
Det er ment å få elementet ut av toppen av stabelen

263
00:20:01,260 --> 00:20:05,780
og deretter minske størrelsen av stabelen,

264
00:20:05,780 --> 00:20:07,810
og nå har du mistet elementet på toppen.

265
00:20:07,810 --> 00:20:11,420
Og så kan du returnere element på toppen.

266
00:20:11,420 --> 00:20:20,080
[Student, uforståelig]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Så hva skjer hvis du gjør det? [Student, uforståelig]

268
00:20:28,810 --> 00:20:34,000
Hva ender opp som skjer er du sannsynligvis få tilgang enten

269
00:20:34,000 --> 00:20:37,350
et element som ikke har blitt initialisert ennå, slik at beregningen

270
00:20:37,350 --> 00:20:39,990
hvor det siste elementet er er av.

271
00:20:39,990 --> 00:20:46,260
Så her hvis du merker, i push, vi tilgang strenger på s.size element

272
00:20:46,260 --> 00:20:48,560
fordi det er en ny indeks.

273
00:20:48,560 --> 00:20:51,460
Det er den nye toppen av bunken.

274
00:20:51,460 --> 00:21:01,100
Mens det i pop, er s.size kommer til å bli den neste plassen,

275
00:21:01,100 --> 00:21:05,210
plassen som er på toppen av alle elementene i stabelen din.

276
00:21:05,210 --> 00:21:10,050
Så den øverste elementet er ikke på s.size,

277
00:21:10,050 --> 00:21:14,930
men heller, det under den.

278
00:21:14,930 --> 00:21:19,640
>> Den andre tingen å gjøre når du - i pop,

279
00:21:19,640 --> 00:21:22,030
er du nødt til å minske størrelsen.

280
00:21:22,030 --> 00:21:28,750
Hvis du husker tilbake til vår lille diagrammet akkurat her,

281
00:21:28,750 --> 00:21:30,980
egentlig, det eneste som vi så skjer når vi kalte pop

282
00:21:30,980 --> 00:21:36,150
var at denne størrelsen droppet, først til 2, og deretter til en.

283
00:21:36,150 --> 00:21:42,620
Så når vi presset et nytt element på, ville det gå på på riktig sted.

284
00:21:42,620 --> 00:21:49,610
[Basil] Hvis s.size er to, så ville det ikke gå til element 2,

285
00:21:49,610 --> 00:21:54,400
og deretter du ønsker å pop som element av?

286
00:21:54,400 --> 00:21:59,510
Så hvis vi gikk til - >> Så la oss se på dette på nytt.

287
00:21:59,510 --> 00:22:07,730
Hvis dette er vårt stabelen på dette punktet

288
00:22:07,730 --> 00:22:12,130
og vi kaller pop,

289
00:22:12,130 --> 00:22:16,150
hvor indeksen er den øverste element?

290
00:22:16,150 --> 00:22:19,300
[Basil] På 2, men det kommer til å dukke 3. >> Høyre.

291
00:22:19,300 --> 00:22:24,220
Så det er der vår størrelse er 3, men vi ønsker å komme elementet på indeks 2.

292
00:22:24,220 --> 00:22:29,900
Det er den typiske slags av av en som du har med null-indeksering av arrays.

293
00:22:29,900 --> 00:22:36,430
Så du ønsker å pop tredje elementet, men det tredje elementet er ikke på indeksen 3.

294
00:22:36,430 --> 00:22:39,430
Og grunnen til at vi ikke trenger å gjøre det minus 1 når vi presser

295
00:22:39,430 --> 00:22:44,120
er fordi akkurat nå, merker du at den øverste element,

296
00:22:44,120 --> 00:22:47,600
hvis vi skulle presse noe annet på bunken på dette punktet,

297
00:22:47,600 --> 00:22:50,360
vi ønsker å presse det på indeksen 3.

298
00:22:50,360 --> 00:23:03,550
Og det bare skjer, slik at størrelsen og indeksene stille opp når du presser.

299
00:23:03,550 --> 00:23:06,960
>> Hvem har en fungerende stack gjennomføringen?

300
00:23:06,960 --> 00:23:09,690
Du har en fungerende stabel ett. Har du pop fungerer ennå?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ja. Jeg tror det.

302
00:23:11,890 --> 00:23:14,610
>> Program kjører og ikke SEG forkastninger, det skriver ut?

303
00:23:14,610 --> 00:23:17,520
Betyr skrive det ut "suksess" når du kjører det?

304
00:23:17,520 --> 00:23:22,630
Ja. Gjør stable kjøre den, hvis det skrives ut "suksess" og ikke går bom,

305
00:23:22,630 --> 00:23:26,000
så alt er bra.

306
00:23:26,000 --> 00:23:34,070
OK. La oss gå over til apparatet veldig raskt,

307
00:23:34,070 --> 00:23:46,100
og vi vil gå gjennom dette.

308
00:23:46,100 --> 00:23:51,110
Hvis vi ser på hva som skjer her med pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, hva var det første du gjorde?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Hvis s.size er større enn 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. Og hvorfor gjorde du det?

312
00:24:03,120 --> 00:24:05,610
[Daniel] For å være sikker på at det var noe inni bunken.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Høyre. Du ønsker å teste for å være sikker på at s.size er større enn 0;

314
00:24:10,950 --> 00:24:13,280
ellers, hva du ønsker å ha skje?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Return null, akkurat.

316
00:24:16,630 --> 00:24:20,740
Så hvis s.size er større enn 0. Så hva skal vi gjøre?

317
00:24:20,740 --> 00:24:25,890
Hva gjør vi hvis bunken ikke er tom?

318
00:24:25,890 --> 00:24:31,210
[Stella] Du minske størrelsen? Minske Du >> størrelse, greit.

319
00:24:31,210 --> 00:24:34,440
Så hvordan gjorde du det? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. Og hva gjorde du?

321
00:24:37,030 --> 00:24:44,140
[Stella] Og så sa jeg tilbake s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
Ellers kan du returnere null. Ja, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Hvorfor det ikke trenger å være s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ja. >> Fikk det.

326
00:24:58,430 --> 00:25:00,980
[Sam] Jeg trodde fordi du tar en ut,

327
00:25:00,980 --> 00:25:04,290
så du kommer til å komme tilbake ikke den som de ba om.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Og dette var akkurat hva vi snakket om med hele denne saken av 0 indeksene.

329
00:25:09,400 --> 00:25:11,380
Så hvis vi zoome tilbake over her.

330
00:25:11,380 --> 00:25:15,650
Hvis vi ser på denne fyren her, kan du se at når vi pop,

331
00:25:15,650 --> 00:25:19,340
vi dukker elementet på indeks 2.

332
00:25:19,340 --> 00:25:25,200
>> Så vi redusere vår størrelse først, og deretter vår størrelse passer vår indeks.

333
00:25:25,200 --> 00:25:39,650
Hvis vi ikke minske størrelsen først, så må vi gjøre størrelsen -1 og deretter minking.

334
00:25:39,650 --> 00:25:45,270
Flott. All good?

335
00:25:45,270 --> 00:25:47,530
Eventuelle spørsmål om dette?

336
00:25:47,530 --> 00:25:54,050
Det finnes en rekke forskjellige måter for å skrive dette også.

337
00:25:54,050 --> 00:26:03,290
Faktisk kan vi gjøre noe selv - vi kan gjøre en one-liner.

338
00:26:03,290 --> 00:26:05,770
Vi kan gjøre en en-linje retur.

339
00:26:05,770 --> 00:26:12,980
Så vi kan faktisk minske før vi kommer tilbake ved å gjøre det.

340
00:26:12,980 --> 00:26:18,320
Så setter - før s.size.

341
00:26:18,320 --> 00:26:22,060
Det gjør linjen virkelig tett.

342
00:26:22,060 --> 00:26:30,940
Hvor forskjellen mellom den -. S størrelse og s.size--

343
00:26:30,940 --> 00:26:40,130
er at dette postfix - de kaller det postfix fordi - kommer etter s.size--

344
00:26:40,130 --> 00:26:47,430
betyr at s.size vurderes i forbindelse med å finne indeksen

345
00:26:47,430 --> 00:26:50,410
som det er tiden når denne linjen er utført,

346
00:26:50,410 --> 00:26:54,290
og deretter dette - skjer etter linjen blir henrettet.

347
00:26:54,290 --> 00:27:00,340
Etter elementet på indeksen s.size åpnes.

348
00:27:00,340 --> 00:27:07,260
Og det er ikke det vi ønsker, fordi vi ønsker reduksjonen skal skje først.

349
00:27:07,260 --> 00:27:10,990
Othewise, vi kommer til å være tilgang til array, effektivt, ut over grensene.

350
00:27:10,990 --> 00:27:16,850
Vi kommer til å være tilgang til elementet over den som vi faktisk ønsker å få tilgang til.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Er det raskere eller bruke mindre RAM å gjøre på én linje eller ikke?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Ærlig talt, det avhenger egentlig.

353
00:27:29,620 --> 00:27:34,220
[Sam, uforståelig] >> Ja, det kommer an. Du kan gjøre kompilatoren triks

354
00:27:34,220 --> 00:27:41,580
å få kompilatoren til å erkjenne at, vanligvis, tenker jeg.

355
00:27:41,580 --> 00:27:44,840
>> Så vi har nevnt litt om dette kompilatoren optimalisering ting

356
00:27:44,840 --> 00:27:47,400
at du kan gjøre i kompilering,

357
00:27:47,400 --> 00:27:50,580
og det er den type ting som en kompilator kan være i stand til å finne ut,

358
00:27:50,580 --> 00:27:54,710
som oh, hei, kanskje jeg kan gjøre alt dette i én operasjon,

359
00:27:54,710 --> 00:27:59,420
i motsetning til lasting størrelsen variabel i fra RAM,

360
00:27:59,420 --> 00:28:03,770
decrementing det, lagre den ut igjen, og deretter legger det inn igjen

361
00:28:03,770 --> 00:28:08,000
å behandle resten av denne operasjonen.

362
00:28:08,000 --> 00:28:10,710
Men typisk, nei, dette er ikke den slags ting

363
00:28:10,710 --> 00:28:20,770
som kommer til å gjøre programmet betydelig raskere.

364
00:28:20,770 --> 00:28:26,000
Eventuelle flere spørsmål om stabler?

365
00:28:26,000 --> 00:28:31,360
>> Så presser og spratt. Hvis dere ønsker å prøve ut hacker utgave,

366
00:28:31,360 --> 00:28:33,660
hva vi har gjort i hacker utgaven er faktisk borte

367
00:28:33,660 --> 00:28:37,670
og gjort denne bunken vokse dynamisk.

368
00:28:37,670 --> 00:28:43,190
Utfordringen er først og fremst her oppe i push-funksjonen,

369
00:28:43,190 --> 00:28:48,820
å finne ut hvordan du gjør denne matrisen vokse

370
00:28:48,820 --> 00:28:52,450
som du holde skyve flere og flere elementer på siden av stabelen.

371
00:28:52,450 --> 00:28:56,000
Det er faktisk ikke så mye ekstra kode.

372
00:28:56,000 --> 00:29:00,080
Bare en oppfordring til - du må huske å få samtaler til malloc der riktig,

373
00:29:00,080 --> 00:29:03,310
og deretter finne ut når du skal ringe RealLOC.

374
00:29:03,310 --> 00:29:06,090
Det er en morsom utfordring hvis du er interessert.

375
00:29:06,090 --> 00:29:11,550
>> Men for tiden, la oss gå videre, og la oss snakke om køer.

376
00:29:11,550 --> 00:29:15,680
Bla gjennom her.

377
00:29:15,680 --> 00:29:19,340
Køen er en nær søsken av stabelen.

378
00:29:19,340 --> 00:29:25,380
Så i bunken, var ting som satt i sist

379
00:29:25,380 --> 00:29:28,810
var de første tingene å deretter bli hentet.

380
00:29:28,810 --> 00:29:33,600
Vi har fått denne sist inn, først ut, eller LIFO, bestilling.

381
00:29:33,600 --> 00:29:38,390
Mens i køen, som du forventer fra når du står i kø,

382
00:29:38,390 --> 00:29:41,980
den første personen til å komme på linje, den første tingen å komme inn i køen,

383
00:29:41,980 --> 00:29:47,630
er det første som blir hentet fra køen.

384
00:29:47,630 --> 00:29:51,490
Køer er også ofte brukt når vi arbeider med grafer,

385
00:29:51,490 --> 00:29:55,560
som vi snakket om kort med stabler,

386
00:29:55,560 --> 00:30:00,260
og køene er også praktisk for en haug med andre ting.

387
00:30:00,260 --> 00:30:06,180
En ting som kommer opp ofte forsøker å opprettholde f.eks

388
00:30:06,180 --> 00:30:12,310
en sortert liste over elementer.

389
00:30:12,310 --> 00:30:17,650
Og du kan gjøre dette med en matrise. Du kan opprettholde en sortert liste over ting i en matrise,

390
00:30:17,650 --> 00:30:20,650
men der det blir vanskelig da du alltid må finne

391
00:30:20,650 --> 00:30:26,160
riktig sted å sette den neste tingen.

392
00:30:26,160 --> 00:30:28,250
Så hvis du har en rekke tall, fra 1 til 10,

393
00:30:28,250 --> 00:30:31,630
og så du vil utvide det til alle tallene 1 til 100,

394
00:30:31,630 --> 00:30:33,670
og du får disse tallene i tilfeldig rekkefølge og prøver å holde alt

395
00:30:33,670 --> 00:30:40,650
sorteres som du går gjennom, vil du ende opp med å gjøre mye giring.

396
00:30:40,650 --> 00:30:43,910
Med visse typer køer og enkelte typer underliggende datastrukturer,

397
00:30:43,910 --> 00:30:46,670
du kan faktisk holde det ganske enkelt.

398
00:30:46,670 --> 00:30:50,640
Du trenger ikke å legge noe og deretter stokke hele greia hver gang.

399
00:30:50,640 --> 00:30:56,770
Heller ikke har du å gjøre mye giring av de interne elementene rundt.

400
00:30:56,770 --> 00:31:02,990
Når vi ser på en kø, ser du at - også i queue.c i delkoden -

401
00:31:02,990 --> 00:31:10,950
struct som vi har gitt deg er veldig lik den struct at vi ga deg for en stabel.

402
00:31:10,950 --> 00:31:13,770
>> Det er ett unntak til dette, og at ett unntak

403
00:31:13,770 --> 00:31:21,700
er at vi har denne ekstra heltall kalles hodet,

404
00:31:21,700 --> 00:31:28,120
og hodet her er for å holde orden på hodet av køen,

405
00:31:28,120 --> 00:31:32,160
eller det første elementet i køen.

406
00:31:32,160 --> 00:31:37,470
Med en stabel, var vi i stand til å holde orden på element som vi var i ferd med å hente,

407
00:31:37,470 --> 00:31:40,800
eller toppen av bunken, med bare størrelsen,

408
00:31:40,800 --> 00:31:44,220
mens med en kø, vi måtte håndtere motsatte ender.

409
00:31:44,220 --> 00:31:49,000
Vi prøver å tråkle ting på på slutten, men da returnere ting fra forsiden.

410
00:31:49,000 --> 00:31:54,640
Så effektivt, med hodet, har vi indeksen av begynnelsen på køen,

411
00:31:54,640 --> 00:31:58,920
og størrelsen gir oss indeksen av slutten av køen

412
00:31:58,920 --> 00:32:03,730
slik at vi kan hente ting fra hodet og legge ting til halen.

413
00:32:03,730 --> 00:32:06,890
Mens med bunken, var vi kun har å gjøre med toppen av bunken.

414
00:32:06,890 --> 00:32:08,900
Vi har aldri hatt tilgang til bunnen av bunken.

415
00:32:08,900 --> 00:32:12,220
Vi bare lagt ting til toppen og tok ting ut av toppen

416
00:32:12,220 --> 00:32:17,470
slik at vi ikke trenger den ekstra felt inne struct vår.

417
00:32:17,470 --> 00:32:20,590
Betyr det generelt fornuftig?

418
00:32:20,590 --> 00:32:27,670
OK. Ja, Charlotte? [Charlotte, uforståelig]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Det er et stort spørsmål, og det var en som kom opp i foredraget.

420
00:32:32,660 --> 00:32:36,290
Kanskje vandre gjennom noen eksempler vil illustrere hvorfor

421
00:32:36,290 --> 00:32:41,400
Vi ønsker ikke å bruke strenger [0] som leder av køen.

422
00:32:41,400 --> 00:32:46,770
>> Så forestille seg at vi har vår kø, skal vi kalle det kø.

423
00:32:46,770 --> 00:32:49,210
I begynnelsen, når vi nettopp har instansiert det,

424
00:32:49,210 --> 00:32:53,330
når vi har nettopp erklært det, har vi ikke initialisert noe.

425
00:32:53,330 --> 00:32:56,790
Det er alt søppel. Så selvfølgelig ønsker vi å sørge for at vi initialisere

426
00:32:56,790 --> 00:33:00,950
både størrelsen og hodet feltene å være 0, noe fornuftig.

427
00:33:00,950 --> 00:33:05,770
Vi kan også gå videre og null ut elementene i kø vår.

428
00:33:05,770 --> 00:33:09,930
Og for å gjøre dette diagrammet passform, legge merke til at nå er vår køen kan bare holde tre elementer;

429
00:33:09,930 --> 00:33:13,150
mens vår stabelen kunne holde fire, kan vår køen bare holde tre.

430
00:33:13,150 --> 00:33:18,680
Og det er bare å gjøre diagrammet passform.

431
00:33:18,680 --> 00:33:26,150
Det første som skjer her er vi Enqueue strengen "Hei".

432
00:33:26,150 --> 00:33:30,380
Og akkurat som vi gjorde med bunken, noe veldig annerledes her,

433
00:33:30,380 --> 00:33:39,230
vi kaster strengen på på strenger [0] og øke vår størrelse med en.

434
00:33:39,230 --> 00:33:42,720
Vi Enqueue "bye", blir det satt på.

435
00:33:42,720 --> 00:33:45,870
Så dette ser ut som en stabel for det meste.

436
00:33:45,870 --> 00:33:53,230
Vi startet her, nytt element, nytt element, holder størrelsen går opp.

437
00:33:53,230 --> 00:33:56,330
Hva skjer på dette punktet når vi ønsker å dequeue noe?

438
00:33:56,330 --> 00:34:01,280
Når vi ønsker å dequeue, som er den delen som vi ønsker å dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Helt riktig, Basil.

440
00:34:04,110 --> 00:34:10,960
Vi ønsker å bli kvitt den første strengen, denne, "Hei".

441
00:34:10,960 --> 00:34:13,170
Så hva var den andre tingen som endret?

442
00:34:13,170 --> 00:34:17,010
Legger merke til når vi popped noe ut av bunken, vi bare endret størrelse,

443
00:34:17,010 --> 00:34:22,080
men her har vi et par ting som endring.

444
00:34:22,080 --> 00:34:27,440
Ikke bare størrelsen endres, men hodet endringer.

445
00:34:27,440 --> 00:34:31,020
Dette kommer tilbake til Charlottes punkt tidligere:

446
00:34:31,020 --> 00:34:38,699
hvorfor har vi dette hodet også?

447
00:34:38,699 --> 00:34:42,110
Betyr det fornuftig nå, Charlotte? >> Kind of.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Kind of? Så hva som skjedde da vi dequeued?

449
00:34:47,500 --> 00:34:54,340
Hva gjorde hodet gjøre det nå er interessant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, fordi det endret - OK. Jeg skjønner.

451
00:34:56,449 --> 00:35:02,090
Fordi hodet - der hodet peker til endringer i forhold til plasseringen.

452
00:35:02,090 --> 00:35:07,200
Det er ikke lenger alltid null indeksen ett. >> Ja, akkurat.

453
00:35:07,200 --> 00:35:17,660
Det som skjedde var om dequeueing høy element

454
00:35:17,660 --> 00:35:20,590
ble gjort og vi har ikke dette hodet feltet

455
00:35:20,590 --> 00:35:26,880
fordi vi var alltid ringer denne strengen på 0-indeksen leder av køen vår,

456
00:35:26,880 --> 00:35:30,170
da ville vi nødt til å skifte resten av køen ned.

457
00:35:30,170 --> 00:35:36,010
Vi måtte skifte "bye" fra strenger [1] til strengene [0].

458
00:35:36,010 --> 00:35:38,760
Og strenger [2] ned til strenger [1].

459
00:35:38,760 --> 00:35:43,050
Og vi måtte gjøre dette for hele listen over elementer,

460
00:35:43,050 --> 00:35:45,110
hele matrisen av elementer.

461
00:35:45,110 --> 00:35:50,490
Og når vi gjør dette med en matrise, blir det virkelig dyrt.

462
00:35:50,490 --> 00:35:53,340
Så her er det ikke en stor avtale. Vi har tre elementer i matrisen vår.

463
00:35:53,340 --> 00:35:57,230
Men hvis vi hadde en kø av tusen elementer eller en million elementer,

464
00:35:57,230 --> 00:36:00,060
og deretter plutselig, begynner vi å lage en haug med dequeue kaller alt i en loop,

465
00:36:00,060 --> 00:36:03,930
ting virkelig kommer til å avta når det skifter alt ned hele tiden.

466
00:36:03,930 --> 00:36:07,320
Du vet, skifte av 1, skift med 1, skift med 1, skift av en.

467
00:36:07,320 --> 00:36:13,650
I stedet bruker vi dette hodet, vi kaller det en "peker" selv om det er egentlig ikke en peker

468
00:36:13,650 --> 00:36:16,430
i streng forstand, det er ikke en peker type.

469
00:36:16,430 --> 00:36:19,410
Det er ikke en int * eller en char * eller noe sånt.

470
00:36:19,410 --> 00:36:28,930
Men den peker eller viser hodet av køen vår. Ja?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Hvordan vet dequeue å bare stikke av alt som er på hodet?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hvordan vet dequeue hvordan å løsne alt som er på hodet? >> Høyre, ja.

473
00:36:43,620 --> 00:36:49,050
>> Hva det er å se på er akkurat hva hodet feltet er satt til.

474
00:36:49,050 --> 00:36:52,710
Så i dette første tilfellet, hvis vi ser her,

475
00:36:52,710 --> 00:36:55,690
vårt hode er 0, indeks 0. >> Høyre.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Så det bare sier greit, vel, elementet på indeks 0, strengen "hei",

477
00:37:00,500 --> 00:37:03,050
er elementet på hodet av køen vår.

478
00:37:03,050 --> 00:37:05,570
Så vi kommer til å dequeue den fyren.

479
00:37:05,570 --> 00:37:09,800
Og det vil være element som blir returnert til den som ringer.

480
00:37:09,800 --> 00:37:14,540
Ja, Saad? >> Så hodet setter i utgangspunktet den - der du kommer til å indeksere den?

481
00:37:14,540 --> 00:37:17,750
Det er starten på det? >> Ja. >> Ok.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Det er å bli den nye starten for array vår.

483
00:37:22,900 --> 00:37:28,930
Så når du dequeue noe, er alt du trenger å gjøre tilgang til elementet på indeks q.head,

484
00:37:28,930 --> 00:37:32,240
og som vil være element som du vil dequeue.

485
00:37:32,240 --> 00:37:34,930
Du må også minske størrelsen.

486
00:37:34,930 --> 00:37:39,430
Vi får se i litt der ting blir litt vanskelig med dette.

487
00:37:39,430 --> 00:37:46,520
Vi dequeue, og nå, hvis vi Enqueue igjen,

488
00:37:46,520 --> 00:37:51,300
hvor Enqueue vi?

489
00:37:51,300 --> 00:37:55,000
Hvor går neste element i køen vårt?

490
00:37:55,000 --> 00:37:57,980
Si at vi ønsker å Enqueue strengen "CS".

491
00:37:57,980 --> 00:38:02,240
Der indeksen vil det gå? [Studenter] Strings [2]. >> Two.

492
00:38:02,240 --> 00:38:04,980
Hvorfor 2 og ikke 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Fordi nå hodet er 1, så det er som starten på listen?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Høyre. Og hva betegner slutten av listen?

495
00:38:21,220 --> 00:38:23,290
Hva skulle vi bruke for å betegne slutten av køen vårt?

496
00:38:23,290 --> 00:38:25,970
Hodet er leder av køen vår, begynnelsen av køen vår.

497
00:38:25,970 --> 00:38:29,530
Hva er slutten på køen vårt? [Studenter] størrelse. >> Størrelse, akkurat.

498
00:38:29,530 --> 00:38:36,360
Så våre nye elementer gå inn på størrelsen, og de elementene som vi tar av kommer av på hodet.

499
00:38:36,360 --> 00:38:45,390
Når vi Enqueue det neste elementet, vi setter det på størrelsen.

500
00:38:45,390 --> 00:38:48,530
[Student] Før sette deg at i skjønt, størrelse var 1, ikke sant?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Høyre. Så ikke helt på størrelse. Størrelse +, ikke en, men + hodet.

502
00:38:55,690 --> 00:38:59,990
Fordi vi flyttet alt av hodet beløp.

503
00:38:59,990 --> 00:39:14,270
Så her, nå har vi fått en kø av størrelse 1 som begynner på indeks 1.

504
00:39:14,270 --> 00:39:20,730
Halen er indeksen 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Hva skjer når du dequeue strenger [0], og strengene 'sporene i minnet

506
00:39:25,780 --> 00:39:29,420
bare bli tømt, i utgangspunktet, eller bare glemt?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. I denne forstand, vi bare glemme dem.

508
00:39:34,700 --> 00:39:42,640
Hvis vi lagret kopier av dem for -

509
00:39:42,640 --> 00:39:46,310
mange datastrukturer vil ofte lagrer sine egne kopier av elementene

510
00:39:46,310 --> 00:39:51,760
slik at personen som administrerer datastrukturen ikke trenger å bekymre deg

511
00:39:51,760 --> 00:39:53,650
om hvor alle disse pekere går.

512
00:39:53,650 --> 00:39:56,000
Datastrukturen holder på alt, holder på til alle kopiene,

513
00:39:56,000 --> 00:39:59,580
å sørge for at alt fortsetter på riktig måte.

514
00:39:59,580 --> 00:40:03,140
Imidlertid, i dette tilfellet, disse datastrukturer bare, for enkelhet,

515
00:40:03,140 --> 00:40:05,580
er ikke å lage kopier av noe som vi lagrer i dem.

516
00:40:05,580 --> 00:40:08,630
[Student] Så er dette en kontinuerlig rekke -? >> Ja.

517
00:40:08,630 --> 00:40:14,350
Hvis vi ser tilbake på hva definisjonen var av denne strukturen, er det.

518
00:40:14,350 --> 00:40:19,110
Det er bare en standard utvalg som du har sett,

519
00:40:19,110 --> 00:40:24,280
en matrise av char * s.

520
00:40:24,280 --> 00:40:26,340
Betyr det -? >> Ja, jeg bare lurte

521
00:40:26,340 --> 00:40:29,130
Hvis du vil til slutt gå tom for minne, til en viss grad,

522
00:40:29,130 --> 00:40:32,330
Hvis du har alle disse tomme flekker i arrayet?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, det er et godt poeng.

524
00:40:36,390 --> 00:40:41,530
>> Hvis vi ser på hva som har skjedd nå på dette punktet,

525
00:40:41,530 --> 00:40:46,350
Vi har fylt opp vår kø, ser det ut som.

526
00:40:46,350 --> 00:40:50,390
Men vi har egentlig ikke fylt opp vår køen

527
00:40:50,390 --> 00:40:57,710
fordi vi har en kø som er størrelse 2, men det begynner på indeks 1,

528
00:40:57,710 --> 00:41:02,160
fordi det er der vårt hode pekeren er.

529
00:41:02,160 --> 00:41:08,400
Som du sa, at element ved strenger [0], på indeks 0, er egentlig ikke det.

530
00:41:08,400 --> 00:41:10,450
Det er ikke i kø vår lenger.

531
00:41:10,450 --> 00:41:16,460
Vi bare ikke bry å gå inn og overskrive det når vi dequeued det.

532
00:41:16,460 --> 00:41:18,700
Så selv om det ser ut som vi har kjørt ut av minnet, har vi virkelig ikke.

533
00:41:18,700 --> 00:41:23,270
At stedet er tilgjengelig for oss å bruke.

534
00:41:23,270 --> 00:41:29,310
Den aktuelle atferd, hvis vi skulle prøve og første dequeue noe

535
00:41:29,310 --> 00:41:34,420
som "bye", som ville pop bye av.

536
00:41:34,420 --> 00:41:38,460
Nå vår køen begynner på indeksen 2 og er av størrelse 1.

537
00:41:38,460 --> 00:41:42,240
Og nå hvis vi prøver og Enqueue noe nytt, sier 50,

538
00:41:42,240 --> 00:41:47,880
50 bør gå i denne sted på indeks 0

539
00:41:47,880 --> 00:41:51,270
fordi det er fremdeles tilgjengelig for oss. Ja, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Skjer det automatisk?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Det skjer ikke helt automatisk. Du må gjøre regnestykket

542
00:41:56,150 --> 00:42:00,380
å gjøre det arbeidet, men i hovedsak hva vi har gjort er at vi har akkurat pakket rundt.

543
00:42:00,380 --> 00:42:04,070
[Saad] Og er det greit hvis dette har et hull i midten av det?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Det er hvis vi kan gjøre regnestykket trene riktig.

545
00:42:08,720 --> 00:42:15,470
>> Og det viser seg at det er faktisk ikke så vanskelig å gjøre med mod operatør.

546
00:42:15,470 --> 00:42:20,040
Så akkurat som vi gjorde med Caesar og krypto ting,

547
00:42:20,040 --> 00:42:25,190
bruker mod, kan vi få ting til å vikle rundt og holde det gående

548
00:42:25,190 --> 00:42:28,090
rundt og rundt og rundt med kø vår,

549
00:42:28,090 --> 00:42:32,180
holde at hodet peker flytte rundt.

550
00:42:32,180 --> 00:42:38,840
Legg merke til at størrelsen er alltid respektere antall elementer inne i selve køen.

551
00:42:38,840 --> 00:42:43,110
Og det er bare hodet peker som holder sykling gjennom.

552
00:42:43,110 --> 00:42:49,660
Hvis vi ser på hva som skjedde her, hvis vi går tilbake til begynnelsen,

553
00:42:49,660 --> 00:42:55,020
og du bare se hva som skjer med hodet

554
00:42:55,020 --> 00:42:58,240
når vi Enqueue noe, skjedde det ingenting i hodet.

555
00:42:58,240 --> 00:43:00,970
Når vi enqueued noe annet, skjedde det ingenting i hodet.

556
00:43:00,970 --> 00:43:04,130
Snart vi dequeued noe, går hodet opp med én.

557
00:43:04,130 --> 00:43:06,600
Vi enqueued noe, skjer det ingenting mot hodet.

558
00:43:06,600 --> 00:43:11,060
Når vi dequeue noe, plutselig hodet blir økes.

559
00:43:11,060 --> 00:43:14,660
Når vi Enqueue noe, skjer det ingenting mot hodet.

560
00:43:14,660 --> 00:43:20,240
>> Hva ville skje på dette punktet hvis vi skulle dequeue noe igjen?

561
00:43:20,240 --> 00:43:23,240
Noen tanker? Hva ville skje med hodet?

562
00:43:23,240 --> 00:43:27,190
Hva bør skje med hodet

563
00:43:27,190 --> 00:43:32,990
hvis vi skulle dequeue noe annet?

564
00:43:32,990 --> 00:43:35,400
Hodet akkurat nå er på indeksen 2,

565
00:43:35,400 --> 00:43:38,920
som betyr at hodet av køen er strenger [2].

566
00:43:38,920 --> 00:43:44,280
[Student] som returnerer 0? >> Det bør gå tilbake til 0. Det bør vikle tilbake rundt, akkurat.

567
00:43:44,280 --> 00:43:48,440
Så langt, hver gang vi kalte dequeue, har vi vært å legge en til hodet,

568
00:43:48,440 --> 00:43:50,960
legg til en i hodet, legge en til hodet, legge en til hodet.

569
00:43:50,960 --> 00:43:58,400
Så snart det hodet peker får den siste indeksen i array vår,

570
00:43:58,400 --> 00:44:05,650
da må vi bryte den tilbake rundt til begynnelsen, gå tilbake til 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Hva bestemmer kapasiteten køen i en stabel?

572
00:44:09,900 --> 00:44:13,120
[Hardison] I dette tilfellet har vi bare brukt en # definert konstant. >> Ok.

573
00:44:13,120 --> 00:44:19,590
[Hardison] I den faktiske. C-fil, kan du gå inn og møkk med den litt

574
00:44:19,590 --> 00:44:21,710
og gjøre den så stor eller så lite som du ønsker.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Så når du gjør det en kø, hvordan du gjør datamaskinen vet

576
00:44:25,310 --> 00:44:29,120
hvor stor du vil bunken for å være?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Det er et stort spørsmål.

578
00:44:31,700 --> 00:44:34,800
Det er et par måter. Det ene er å bare definere det opp foran

579
00:44:34,800 --> 00:44:42,050
og si dette kommer til å være en kø som har 4 elementer eller 50 elementer eller 10.000.

580
00:44:42,050 --> 00:44:45,430
Den andre måten er å gjøre hva hacker utgave folk gjør

581
00:44:45,430 --> 00:44:52,310
og lage funksjoner for å ha din køen vokser dynamisk etter hvert som flere ting bli lagt i.

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Så å gå med det første alternativet, hva syntaks du bruker

583
00:44:54,740 --> 00:44:57,830
å fortelle programmet hva er størrelsen av køen?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Så la oss komme oss ut av dette.

585
00:45:04,780 --> 00:45:12,650
Jeg er fortsatt i stack.c her, så jeg skal bare rulle opp til toppen her.

586
00:45:12,650 --> 00:45:17,920
Kan du se dette her? Dette er den # define kapasitet 10.

587
00:45:17,920 --> 00:45:24,600
Og dette er nesten nøyaktig samme syntaks som vi har for køen.

588
00:45:24,600 --> 00:45:28,390
Bortsett fra i kø, har vi det ekstra struct feltet her.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, jeg trodde kapasiteten mente kapasiteten for strengen.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> At det er den maksimale lengden på ordet. >> Fikk det.

591
00:45:36,770 --> 00:45:41,180
Ja. Kapasiteten her - det er et stort poeng.

592
00:45:41,180 --> 00:45:44,000
Og dette er noe som er vanskelig

593
00:45:44,000 --> 00:45:49,480
fordi det vi har erklært her er en rekke char * s.

594
00:45:49,480 --> 00:45:52,770
En rekke pekere.

595
00:45:52,770 --> 00:45:56,690
Dette er en rekke tegn.

596
00:45:56,690 --> 00:46:01,690
Dette er sannsynligvis det du har sett når du har vært å erklære dine buffere for fil I / O,

597
00:46:01,690 --> 00:46:06,840
når du har vært å skape strenger manuelt på stakken.

598
00:46:06,840 --> 00:46:09,090
Men hva vi har her er en rekke char * s.

599
00:46:09,090 --> 00:46:13,400
Så det er en rekke pekere.

600
00:46:13,400 --> 00:46:18,350
Egentlig, hvis vi zoome ut igjen, og vi ser på hva som skjer her

601
00:46:18,350 --> 00:46:23,140
i presentasjonen, ser du at den faktiske elementer, tegnet data

602
00:46:23,140 --> 00:46:26,180
lagres ikke i matrisen selv.

603
00:46:26,180 --> 00:46:42,690
Hva som er lagret i matrisen vår her er pekere til de tegndata.

604
00:46:42,690 --> 00:46:52,560
Okay. Så vi har sett hvordan størrelsen på køen er akkurat med bunken,

605
00:46:52,560 --> 00:46:58,670
størrelsen respekterer alltid antall elementer som ligger i køen.

606
00:46:58,670 --> 00:47:02,720
Etter at to enqueues, er størrelsen 2.

607
00:47:02,720 --> 00:47:07,110
Etter at en dequeue størrelsen er nå en.

608
00:47:07,110 --> 00:47:09,330
Etter at en annen Enqueue størrelsen er tilbake opptil 2.

609
00:47:09,330 --> 00:47:12,340
Slik at størrelsen respekterer definitivt antall elementer i køen,

610
00:47:12,340 --> 00:47:15,580
og deretter hodet holder bare sykling.

611
00:47:15,580 --> 00:47:20,210
Det går fra 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Og hver gang vi kaller dequeue, blir hodet pekeren økes til neste indeksen.

613
00:47:25,620 --> 00:47:29,930
Og hvis hodet er i ferd med å gå over, looper den tilbake rundt til 0.

614
00:47:29,930 --> 00:47:34,870
Så med det, kan vi skrive dequeue funksjonen.

615
00:47:34,870 --> 00:47:40,200
Og vi kommer til å forlate Enqueue funksjon for dere å gjennomføre i stedet.

616
00:47:40,200 --> 00:47:45,880
>> Når vi dequeue et element ut av køen vår,

617
00:47:45,880 --> 00:47:55,490
hva var det første som Daniel gjorde da vi begynte å skrive pop-funksjonen for stabler?

618
00:47:55,490 --> 00:48:00,490
La meg høre fra noen som ikke har snakket ennå.

619
00:48:00,490 --> 00:48:06,710
La oss se, Saad, husker du hva Daniel gjorde som det første da han skrev pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Det var, var det - >> Han testet for noe.

621
00:48:08,860 --> 00:48:12,140
[Saad] Hvis størrelsen er større enn 0. >> Nettopp.

622
00:48:12,140 --> 00:48:14,390
Og hva var det testing for?

623
00:48:14,390 --> 00:48:19,090
[Saad] Det var testing for å se om det er noe inni tabellen.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Akkurat. Så du kan ikke komme noe ut av bunken hvis det er tomt.

625
00:48:23,210 --> 00:48:26,510
På samme måte kan du ikke dequeue noe fra en kø hvis det er tomt.

626
00:48:26,510 --> 00:48:30,420
Hva er det første vi bør gjøre i vår dequeue funksjon her, tror du?

627
00:48:30,420 --> 00:48:33,860
[Saad] Hvis størrelsen er større enn 0? >> Ja.

628
00:48:33,860 --> 00:48:37,710
I dette tilfellet har jeg faktisk bare testet for å se om det er 0.

629
00:48:37,710 --> 00:48:42,240
Hvis det er 0, kan vi returnere null.

630
00:48:42,240 --> 00:48:45,280
Men nøyaktig samme logikk.

631
00:48:45,280 --> 00:48:49,110
Og la oss fortsette med dette.

632
00:48:49,110 --> 00:48:54,600
Hvis størrelsen ikke er 0, der er element som vi ønsker å dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] På hodet? >> Nettopp.

634
00:48:58,550 --> 00:49:01,720
Vi kan bare trekke ut det første elementet i køen vår

635
00:49:01,720 --> 00:49:07,040
ved å gå elementet på hodet.

636
00:49:07,040 --> 00:49:14,630
Ingenting gale.

637
00:49:14,630 --> 00:49:19,620
Etter det, hva skal vi gjøre? Hva må skje?

638
00:49:19,620 --> 00:49:23,740
Hva var det andre ting som vi snakket om i dequeue?

639
00:49:23,740 --> 00:49:28,130
To ting må skje, fordi vår køen har endret seg.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reduser størrelsen. >> Vi må redusere størrelsen, og øke hodet? Akkurat.

641
00:49:35,640 --> 00:49:40,600
Å øke hodet, kan vi ikke bare blindt øke hodet, husker.

642
00:49:40,600 --> 00:49:45,080
Vi kan ikke bare gjøre queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Vi må også ta med denne mod av kapasiteten.

644
00:49:51,630 --> 00:49:54,740
Og hvorfor mod vi med kapasiteten, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Fordi det har å vikle rundt. >> Nettopp.

646
00:49:58,680 --> 00:50:04,750
Vi mod av kapasiteten fordi den har å vikle tilbake rundt til 0.

647
00:50:04,750 --> 00:50:07,400
Så nå, på dette punktet, kan vi gjøre det Daniel sa.

648
00:50:07,400 --> 00:50:12,700
Vi kan minske størrelsen.

649
00:50:12,700 --> 00:50:29,170
Og så kan vi bare returnere det elementet som var på toppen av køen.

650
00:50:29,170 --> 00:50:34,000
Det ser slags gnarly først. Du har kanskje et spørsmål. Beklager?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Hvorfor er først på toppen av køen? Hvor går det?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Det kommer fra den fjerde linje fra bunnen.

653
00:50:42,480 --> 00:50:46,060
Etter at vi teste for å være sikker på at vår køen ikke er tom,

654
00:50:46,060 --> 00:50:54,100
Vi trekker ut char * først, trekker vi ut elementet som sitter på hodet indeksen

655
00:50:54,100 --> 00:50:58,680
array vår, vår strenger array, >> og samtale som først?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Og vi kaller det første. Ja.

657
00:51:04,500 --> 00:51:09,850
Bare for å følge opp at hvorfor tror du vi måtte gjøre det?

658
00:51:09,850 --> 00:51:18,270
[Sam] Hver første er bare tilbake q.strings [q.head]? >> Ja.

659
00:51:18,270 --> 00:51:23,830
>> Fordi vi gjør dette endring av q.head med mod-funksjonen,

660
00:51:23,830 --> 00:51:27,810
og det er ingen måte å gjøre det innenfor returledning også.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Nettopp. Du er spot on. Sam er øye helt på.

662
00:51:31,640 --> 00:51:36,800
Grunnen til at vi måtte trekke ut det første elementet i køen vår og lagre det i en variabel

663
00:51:36,800 --> 00:51:43,030
er fordi denne linjen der vi bare hadde q.head,

664
00:51:43,030 --> 00:51:47,030
Det er mod operatør i det ikke er noe som vi kan gjøre

665
00:51:47,030 --> 00:51:51,230
og ta det ha effekt på hodet uten - på én linje.

666
00:51:51,230 --> 00:51:54,480
Slik at vi faktisk nødt til å trekke ut det første elementet, og deretter justere hodet,

667
00:51:54,480 --> 00:52:00,430
justere størrelsen, og deretter returnere element som vi dro ut.

668
00:52:00,430 --> 00:52:02,680
Og dette er noe som vi vil se komme opp senere med

669
00:52:02,680 --> 00:52:04,920
knyttet lister, som vi spiller rundt med dem.

670
00:52:04,920 --> 00:52:08,410
Ofte når du frigjør eller avhending av koblede lister

671
00:52:08,410 --> 00:52:13,500
du trenger å huske det neste elementet, neste pekeren over en lenket liste

672
00:52:13,500 --> 00:52:16,330
før du kaster den nåværende.

673
00:52:16,330 --> 00:52:23,580
Fordi ellers du kaster bort informasjon om hva som er igjen på listen.

674
00:52:23,580 --> 00:52:34,160
Nå, hvis du går til apparatet, åpner du opp queue.c--x ut av dette.

675
00:52:34,160 --> 00:52:39,390
Så hvis jeg åpner opp queue.c, la meg zoome inn her,

676
00:52:39,390 --> 00:52:44,970
vil du se at du har en lignende utseende fil.

677
00:52:44,970 --> 00:52:49,200
Lignende utseende fil til hva vi hadde tidligere med stack.c.

678
00:52:49,200 --> 00:52:54,690
Vi har fått vår struct for kø som bare er definert som vi så på lysbildene.

679
00:52:54,690 --> 00:52:59,870
>> Vi har vår Enqueue funksjon som er for deg å gjøre.

680
00:52:59,870 --> 00:53:04,340
Og vi har dequeue funksjon her.

681
00:53:04,340 --> 00:53:06,870
Den dequeue funksjon i filen unimplemented,

682
00:53:06,870 --> 00:53:13,230
men jeg skal sette den opp igjen på PowerPoint, slik at du kan skrive det inn, hvis du ønsker.

683
00:53:13,230 --> 00:53:16,690
Så for de neste 5 minutter eller så, dere jobber på Enqueue

684
00:53:16,690 --> 00:53:22,570
som er nesten akkurat det motsatte av dequeue.

685
00:53:22,570 --> 00:53:29,560
Du trenger ikke å justere hodet når du enqueueing, men hva har du å justere?

686
00:53:29,560 --> 00:53:38,920
Størrelse. Så når du Enqueue, forblir hodet urørt, blir størrelsen endres.

687
00:53:38,920 --> 00:53:46,920
Men det tar litt - du må spille rundt med den mod

688
00:53:46,920 --> 00:53:57,560
å finne ut nøyaktig hva indeksen det nye elementet skal settes inn på.

689
00:53:57,560 --> 00:54:03,080
Så jeg skal gi dere en liten bit, sette dequeue opp på lysbildet,

690
00:54:03,080 --> 00:54:05,200
og som dere har spørsmål, rope dem ut slik at vi kan

691
00:54:05,200 --> 00:54:09,220
alt snakk om dem som en gruppe.

692
00:54:09,220 --> 00:54:13,960
Også med den størrelsen du må få med - når du justere størrelsen, kan du alltid bare -

693
00:54:13,960 --> 00:54:18,720
har du å mod størrelsen noensinne? [Daniel] Nei >> Du trenger ikke å mod størrelsen, ikke sant.

694
00:54:18,720 --> 00:54:24,260
Fordi størrelsen vil alltid, hvis du har kommet - forutsatt at du administrere ting riktig,

695
00:54:24,260 --> 00:54:30,840
størrelsen vil alltid ligge mellom 0 og 3.

696
00:54:30,840 --> 00:54:38,680
Hvor har du å mod når du gjør Enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Bare for hodet. >> Bare for hodet, akkurat.

698
00:54:41,060 --> 00:54:44,620
Og hvorfor har du å mod det hele tatt i Enqueue?

699
00:54:44,620 --> 00:54:48,830
Når er en situasjon hvor du måtte mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Hvis du har ting på områder, som på områder 1 og 2,

701
00:54:53,630 --> 00:54:55,950
og deretter måtte legge noe på 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Nettopp. Så hvis hodet pekeren er helt i enden,

703
00:55:02,570 --> 00:55:14,210
eller hvis størrelse pluss hodet er større, eller rettere sagt, kommer til å vikle rundt køen.

704
00:55:14,210 --> 00:55:17,830
>> Så i denne situasjonen at vi har her oppe på lysbildet akkurat nå,

705
00:55:17,830 --> 00:55:24,370
hvis jeg ønsker å Enqueue noe akkurat nå,

706
00:55:24,370 --> 00:55:31,110
vi ønsker å Enqueue noe på indeks 0.

707
00:55:31,110 --> 00:55:35,450
Så hvis du ser på hvor de 50 går, og jeg kaller Enqueue 50,

708
00:55:35,450 --> 00:55:40,840
det går der nede på bunnen. Det går i indeksen 0.

709
00:55:40,840 --> 00:55:44,160
Det erstatter 'Hei' som allerede var dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Tror ikke du tar vare på det i dequeue allerede?

711
00:55:46,210 --> 00:55:50,550
Hvorfor gjør det noe med hodet i Enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, slik at du ikke endrer hodet, beklager.

713
00:55:55,770 --> 00:56:02,310
Men du må bruke mod operatør når du åpner

714
00:56:02,310 --> 00:56:04,250
elementet du vil Enqueue når du åpner

715
00:56:04,250 --> 00:56:06,960
neste element i køen.

716
00:56:06,960 --> 00:56:10,960
[Basil] Jeg gjorde ikke det, og jeg fikk "suksess" på det.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, jeg forstår hva du sier.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Så du didn't - du nettopp gjorde på q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Jeg bare byttet side, det gjorde jeg ikke gjøre noe med hodet.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Du trenger ikke egentlig trenger å tilbakestille hodet å være noe,

721
00:56:24,300 --> 00:56:31,650
men når du indeksen i strenger array,

722
00:56:31,650 --> 00:56:39,500
du faktisk nødt til å gå videre og beregne hvor neste element er,

723
00:56:39,500 --> 00:56:44,230
fordi withe stabelen, var det neste elementet i stabelen din alltid

724
00:56:44,230 --> 00:56:48,740
mot referansepunktet tilsvarende størrelsen.

725
00:56:48,740 --> 00:56:55,850
Hvis vi ser tilbake opp på vår stabelen trykk-funksjon,

726
00:56:55,850 --> 00:57:03,100
vi kan alltid plunk i vår nye element rett på indeksen størrelse.

727
00:57:03,100 --> 00:57:06,710
Mens med køen, kan vi ikke gjøre det

728
00:57:06,710 --> 00:57:10,340
fordi hvis vi er på denne situasjonen,

729
00:57:10,340 --> 00:57:18,130
hvis vi enqueued 50 vårt nye streng ville gå rett på strenger [1]

730
00:57:18,130 --> 00:57:20,540
som vi ikke ønsker å gjøre.

731
00:57:20,540 --> 00:57:41,200
Vi ønsker å ha den nye strengen gå på indeks 0.

732
00:57:41,200 --> 00:57:44,320
>> Er det noen som - ja? [Student] Jeg har et spørsmål, men det er egentlig ikke i slekt.

733
00:57:44,320 --> 00:57:48,160
Hva betyr det når noen bare kaller noe sånt Pred pekeren?

734
00:57:48,160 --> 00:57:51,260
Hva er det navnet en forkortelse for? Jeg vet det er bare et navn.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pekeren? La oss se. I hvilken sammenheng?

736
00:57:59,110 --> 00:58:01,790
[Student] Det var for innsatsen. Jeg kan spørre deg senere hvis du vil

737
00:58:01,790 --> 00:58:03,920
fordi det er egentlig ikke relatert, men jeg bare -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Fra Davids Sett inn kode fra forelesning?

739
00:58:07,300 --> 00:58:10,860
Vi kan trekke det opp og snakke om det.

740
00:58:10,860 --> 00:58:15,550
Vi skal snakke om det neste, når vi kommer til koplede listene.

741
00:58:15,550 --> 00:58:21,440
>> Så la oss veldig raskt se på hva Enqueue funksjonen ser ut.

742
00:58:21,440 --> 00:58:26,530
Hva var det første som folk prøvde å gjøre i din Enqueue linje? Inn i denne køen?

743
00:58:26,530 --> 00:58:29,960
I likhet med hva du gjorde for stack presser.

744
00:58:29,960 --> 00:58:32,080
Hva gjorde du, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, uforståelig]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Nettopp. If (q.size == KAPASITET) -

747
00:58:45,700 --> 00:58:54,720
Jeg trenger å sette mine tannregulering på rett sted - return false.

748
00:58:54,720 --> 00:59:01,370
Zoome inn litt. Okay.

749
00:59:01,370 --> 00:59:03,800
Nå hva er neste ting som vi måtte gjøre?

750
00:59:03,800 --> 00:59:11,370
Akkurat som med bunken, og satt på rett sted.

751
00:59:11,370 --> 00:59:16,010
Og så hva var det rette stedet å sette inn det?

752
00:59:16,010 --> 00:59:23,170
Med bunken var det indeksen størrelse, med dette er det ikke helt det.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Jeg har q.head--eller - >> q.strings? >> Ja.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPASITET]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Vi sannsynligvis ønsker å sette parentes rundt dette

756
00:59:42,740 --> 00:59:48,830
slik at vi får riktig prioritet og slik at det er cleart for alle.

757
00:59:48,830 --> 00:59:55,800
Og sett at lik? >> For å str? >> Til str. Flott.

758
00:59:55,800 --> 01:00:00,160
Og nå hva er det siste at vi har å gjøre?

759
01:00:00,160 --> 01:00:06,780
Akkurat som vi gjorde i bunken. >> Øk størrelsen? >> Inkrementere størrelsen.

760
01:00:06,780 --> 01:00:13,830
Boom. Og da, siden starteren koden nettopp returnert falsk som standard,

761
01:00:13,830 --> 01:00:27,460
vi ønsker å endre dette til true hvis alt går gjennom og alt går bra.

762
01:00:27,460 --> 01:00:33,050
OK. Det er mye informasjon for seksjonen.

763
01:00:33,050 --> 01:00:39,480
Vi er ikke helt over. Vi ønsker å snakke veldig raskt om enkeltvis-koplede listene.

764
01:00:39,480 --> 01:00:44,010
Jeg skal sette opp dette slik at vi kan gå tilbake til det senere.

765
01:00:44,010 --> 01:00:50,850
Men la oss gå tilbake til presentasjonen vår for bare noen få flere lysbilder.

766
01:00:50,850 --> 01:00:53,790
Så Enqueue er TODO, nå har vi gjort det.

767
01:00:53,790 --> 01:00:57,430
>> La oss nå ta en titt på enkeltvis-koplede listene.

768
01:00:57,430 --> 01:01:00,040
Vi snakket om disse litt mer i foredraget.

769
01:01:00,040 --> 01:01:02,540
Hvor mange av dere så demo der vi hadde folk

770
01:01:02,540 --> 01:01:08,220
awkwardly peker til hverandre og holder tall? >> Jeg var i det.

771
01:01:08,220 --> 01:01:16,620
>> Hva gjorde dere? Gjorde det, forhåpentligvis avmystifisere disse litt?

772
01:01:16,620 --> 01:01:25,990
Med en liste, viser det seg at vi behandler denne typen som vi kommer til å kalle en node.

773
01:01:25,990 --> 01:01:32,520
Mens med køen og stakk hadde vi structs at vi vil kalle kø i bunken,

774
01:01:32,520 --> 01:01:34,860
Vi hadde disse nye kø i stack typer,

775
01:01:34,860 --> 01:01:39,240
her er en liste er egentlig bare består av en haug av noder.

776
01:01:39,240 --> 01:01:45,920
På samme måte som strenger er bare en haug med tegn på rekke og rad ved siden av hverandre.

777
01:01:45,920 --> 01:01:50,650
En lenket liste er bare en node og en annen node og en annen node og en annen node.

778
01:01:50,650 --> 01:01:55,080
Og i stedet for å knuse alle nodene sammen og lagre dem contiguously

779
01:01:55,080 --> 01:01:58,090
alle rett ved siden av hverandre i minnet,

780
01:01:58,090 --> 01:02:04,470
å ha denne neste pekeren tillater oss å lagre nodene hvor som helst, på måfå.

781
01:02:04,470 --> 01:02:10,500
Og deretter slags ledning dem alle sammen for å peke fra den ene til den neste.

782
01:02:10,500 --> 01:02:15,850
>> Og hva var den store fordel at dette hadde over en array?

783
01:02:15,850 --> 01:02:21,680
Over lagring alt contiguously bare fast ved siden av hverandre?

784
01:02:21,680 --> 01:02:24,190
Du husker? Ja? >> Dynamisk minne allokering?

785
01:02:24,190 --> 01:02:27,220
>> Dynamisk minne allokering i hvilken forstand?

786
01:02:27,220 --> 01:02:31,780
[Student] I det du kan fortsette å lage det større og du trenger ikke å flytte hele array?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Nettopp. Så med en matrise, når du ønsker å sette et nytt element inn i midten av den,

788
01:02:40,940 --> 01:02:45,320
du må skifte alt for å gjøre plass.

789
01:02:45,320 --> 01:02:47,880
Og som vi snakket om med køen,

790
01:02:47,880 --> 01:02:50,080
det er derfor vi holder det hode peker,

791
01:02:50,080 --> 01:02:52,050
slik at vi ikke stadig skiftende ting.

792
01:02:52,050 --> 01:02:54,520
Fordi det blir dyrt hvis du har en stor matrise

793
01:02:54,520 --> 01:02:57,130
og du stadig gjør disse tilfeldige innsettinger.

794
01:02:57,130 --> 01:03:00,820
Mens med en liste, er alt du trenger å gjøre kaste den på en ny node,

795
01:03:00,820 --> 01:03:06,330
justere pekere, og du er ferdig.

796
01:03:06,330 --> 01:03:10,940
Hva suger om dette?

797
01:03:10,940 --> 01:03:16,830
Bortsett fra det faktum at det er ikke så lett å jobbe med som en matrise? Ja?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Vel, jeg antar det er mye vanskeligere å få tilgang til et bestemt element i lenket liste?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Du kan ikke bare hoppe til en vilkårlig element i midten av lenket liste.

800
01:03:30,470 --> 01:03:33,800
Hvordan har du tenkt å gjøre det i stedet? >> Du må gå gjennom hele greia.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Du må gå gjennom en av gangen, en om gangen.

802
01:03:35,660 --> 01:03:38,480
Det er en stor - det er en smerte.

803
01:03:38,480 --> 01:03:41,550
Hva er den andre - det er en annen fall til dette.

804
01:03:41,550 --> 01:03:45,340
[Basil] Du kan ikke gå fremover og bakover? Du må gå én retning?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Så hvordan løser vi det, noen ganger?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dobbelt-forbundet lister? >> Nettopp. Det er dobbelt-lenkede lister.

807
01:03:53,370 --> 01:03:55,540
Det er også - beklager?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Er det det samme som å bruke Pred ting som -

809
01:03:57,620 --> 01:04:01,090
Jeg bare husket, er ikke det hva Pred ting er?

810
01:04:01,090 --> 01:04:05,850
Er ikke det i mellom dobbelt og enkeltvis?

811
01:04:05,850 --> 01:04:10,020
[Hardison] La oss se på hva han gjorde.

812
01:04:10,020 --> 01:04:15,760
Så her går vi. Her er listen koden.

813
01:04:15,760 --> 01:04:25,620
Her har vi predptr, her. Er det dette du snakket om?

814
01:04:25,620 --> 01:04:30,750
Så dette var - han befri en liste, og han prøver å lagre en peker til den.

815
01:04:30,750 --> 01:04:35,000
Dette er ikke dobbelt, enkeltvis knyttet-lister.

816
01:04:35,000 --> 01:04:40,090
Vi kan snakke mer om dette senere siden dette er snakk om å frigjøre listen

817
01:04:40,090 --> 01:04:42,900
og jeg ønsker å vise noen andre ting først.

818
01:04:42,900 --> 01:04:51,480
men det er bare - det er å huske verdien av ptr

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, det er foregående pekeren? >> Ja.

820
01:04:54,170 --> 01:05:04,070
Slik at vi kan da øke ptr seg før vi deretter gratis hva predptr er.

821
01:05:04,070 --> 01:05:09,130
Fordi vi ikke kan fri ptr og deretter ringe ptr = ptr neste, ikke sant?

822
01:05:09,130 --> 01:05:11,260
Det ville være dårlig.

823
01:05:11,260 --> 01:05:20,940
Så la oss se, tilbake til denne fyren.

824
01:05:20,940 --> 01:05:23,900
>> Den andre dårlige ting om lister, er at mens med en rekke

825
01:05:23,900 --> 01:05:26,520
vi må bare alle elementene selv stablet ved siden av hverandre,

826
01:05:26,520 --> 01:05:29,050
Her har vi også innført denne pekeren.

827
01:05:29,050 --> 01:05:34,060
Så det er en ekstra del av minnet som vi måtte bruke

828
01:05:34,060 --> 01:05:37,910
for hvert element som vi lagrer i vår liste.

829
01:05:37,910 --> 01:05:40,030
Vi får fleksibilitet, men det kommer til en pris.

830
01:05:40,030 --> 01:05:42,230
Den kommer med denne gangen kostnader,

831
01:05:42,230 --> 01:05:45,270
og det følger med dette minnet pris for.

832
01:05:45,270 --> 01:05:47,800
Tid i den forstand at vi nå må gå gjennom hvert element i matrisen

833
01:05:47,800 --> 01:05:58,670
å finne en på indeks 10, eller som ville ha vært indeks 10 i en matrise.

834
01:05:58,670 --> 01:06:01,230
>> Bare veldig raskt, når vi diagram ut disse listene,

835
01:06:01,230 --> 01:06:05,980
typisk vi holder på til leder av listen eller den første pekeren på listen

836
01:06:05,980 --> 01:06:08,010
og oppmerksom på at dette er en sann peker.

837
01:06:08,010 --> 01:06:11,100
Det er bare 4 bytes. Det er ikke en faktisk node selv.

838
01:06:11,100 --> 01:06:17,120
Så du ser at det har ingen int verdi i det, ingen neste pekeren i den.

839
01:06:17,120 --> 01:06:20,790
Det er bokstavelig talt bare en peker.

840
01:06:20,790 --> 01:06:23,550
Det kommer til å peke på noe som er en faktisk node struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] En peker kalt node? >> Dette er - nei. Dette er en peker til noe av type node.

842
01:06:28,480 --> 01:06:32,540
Det er en peker til en node struct. >> Å, greit.

843
01:06:32,540 --> 01:06:36,870
Diagrammet til venstre, kode til høyre.

844
01:06:36,870 --> 01:06:42,190
Vi kan sette den til null, som er en god måte å starte.

845
01:06:42,190 --> 01:06:49,850
Når du diagram det, du enten skrive det som null eller du sette en linje gjennom det sånn.

846
01:06:49,850 --> 01:06:53,910
>> En av de enkleste måtene å arbeide med lister,

847
01:06:53,910 --> 01:06:57,430
og vi ber dere både foranstilt og etterstilt å se forskjellene mellom de to,

848
01:06:57,430 --> 01:07:01,320
men prepending er definitivt enklere.

849
01:07:01,320 --> 01:07:05,790
Når du foranstille, dette er hvor du - når du setter du (7),

850
01:07:05,790 --> 01:07:10,050
du går og lage noden struct

851
01:07:10,050 --> 01:07:13,870
og du setter første til å peke på det, fordi nå, siden vi foranstilles det,

852
01:07:13,870 --> 01:07:17,240
det kommer til å være i begynnelsen av listen.

853
01:07:17,240 --> 01:07:22,540
Hvis vi setter du (3), som skaper en annen node, men nå 3 kommer før 7.

854
01:07:22,540 --> 01:07:31,130
Så vi egentlig skyve ting på vår liste.

855
01:07:31,130 --> 01:07:34,720
Nå kan du se at foranstilte, noen ganger folk kaller det push,

856
01:07:34,720 --> 01:07:39,600
fordi du presser et nytt element på listen din.

857
01:07:39,600 --> 01:07:43,270
Det er også lett å slette på forsiden av en liste.

858
01:07:43,270 --> 01:07:45,650
Så folk vil ofte kalle det pop.

859
01:07:45,650 --> 01:07:52,200
Og på den måten kan du etterligne en stabel med en lenket liste.

860
01:07:52,200 --> 01:07:57,880
Whoops. Beklager, nå vi får inn append. Så her er vi foranstilles (7), nå er vi foranstilte (3).

861
01:07:57,880 --> 01:08:02,600
Hvis vi foranstilles noe annet på denne listen, hvis vi foranstilles (4),

862
01:08:02,600 --> 01:08:06,540
da ville vi ha 4 og deretter 3 og deretter 7.

863
01:08:06,540 --> 01:08:14,220
Så vi kan sette og fjerne 4, 3 fjern, fjern 7.

864
01:08:14,220 --> 01:08:16,500
Ofte mer intuitiv måte å tenke på dette er med append.

865
01:08:16,500 --> 01:08:20,310
Så jeg har skjematisk ut hva det ville se ut med føyer her.

866
01:08:20,310 --> 01:08:23,380
Her legges (7) ikke ser noe annerledes

867
01:08:23,380 --> 01:08:25,160
fordi det er bare ett element i listen.

868
01:08:25,160 --> 01:08:28,620
Og legge (3) uttrykker det på slutten.

869
01:08:28,620 --> 01:08:31,020
Kanskje du kan se akkurat nå kunsten med append

870
01:08:31,020 --> 01:08:36,600
er at siden vi bare kjenner hvor begynnelsen av listen er,

871
01:08:36,600 --> 01:08:39,450
å legge til en liste du har å gå hele veien gjennom listen

872
01:08:39,450 --> 01:08:46,500
å komme til slutten, stoppe, og deretter bygge din node og plunk alt ned.

873
01:08:46,500 --> 01:08:50,590
Wire alle ting opp.

874
01:08:50,590 --> 01:08:55,170
Så med foranstilte, som vi bare dratt gjennom dette veldig raskt,

875
01:08:55,170 --> 01:08:58,170
når du foranstille til en liste, er det ganske enkelt.

876
01:08:58,170 --> 01:09:02,960
>> Du gjør ditt nye node, innebære noen dynamisk minne allokering.

877
01:09:02,960 --> 01:09:09,830
Så her vi gjør en node struct hjelp malloc.

878
01:09:09,830 --> 01:09:14,710
Så malloc vi bruker fordi det vil sette minne for oss for senere

879
01:09:14,710 --> 01:09:20,350
fordi vi ikke ønsker dette - vi vil at dette minnet vil vedvare i lang tid.

880
01:09:20,350 --> 01:09:25,350
Og vi får en peker til plass i minnet at vi bare tildelt.

881
01:09:25,350 --> 01:09:29,260
Vi bruker størrelse node, har vi ikke summere feltene.

882
01:09:29,260 --> 01:09:31,899
Vi har ikke manuelt generere antall byte,

883
01:09:31,899 --> 01:09:39,750
i stedet bruker vi sizeof slik at vi vet at vi får riktig antall byte.

884
01:09:39,750 --> 01:09:43,660
Vi sørge for å teste at vår malloc samtale lyktes.

885
01:09:43,660 --> 01:09:47,939
Dette er noe du ønsker å gjøre generelt.

886
01:09:47,939 --> 01:09:52,590
På moderne maskiner, kjører ut av minnet er ikke noe som er lett

887
01:09:52,590 --> 01:09:56,610
med mindre du fordele massevis av ting og gjør en stor liste,

888
01:09:56,610 --> 01:10:02,220
men hvis du bygger ting for, si, som en iPhone eller en Android,

889
01:10:02,220 --> 01:10:05,230
du har begrensede minneressurser, spesielt hvis du gjør noe intens.

890
01:10:05,230 --> 01:10:08,300
Så det er godt å få i praksis.

891
01:10:08,300 --> 01:10:10,510
>> Legg merke til at jeg har brukt et par forskjellige funksjoner her

892
01:10:10,510 --> 01:10:12,880
som du har sett som er slags nye.

893
01:10:12,880 --> 01:10:15,870
Så fprintf er akkurat printf

894
01:10:15,870 --> 01:10:21,320
bortsett fra sin første argumentet er strømmen som du vil skrive ut.

895
01:10:21,320 --> 01:10:23,900
I dette tilfellet ønsker vi å skrive ut til standard feilstreng

896
01:10:23,900 --> 01:10:29,410
som er forskjellig fra standard outstream.

897
01:10:29,410 --> 01:10:31,620
Som standard viser den opp på samme sted.

898
01:10:31,620 --> 01:10:34,600
Den skriver også ut til terminalen, men du kan -

899
01:10:34,600 --> 01:10:38,790
å bruke disse kommandoene du har lært om, omdirigering teknikker

900
01:10:38,790 --> 01:10:42,290
du har lært om i Tommys video for oppgavesettet 4, kan du sende det

901
01:10:42,290 --> 01:10:47,900
til forskjellige områder, og avslutter rett her, avslutter programmet.

902
01:10:47,900 --> 01:10:50,440
Det er hovedsaklig som retur fra main,

903
01:10:50,440 --> 01:10:53,600
bortsett fra vi bruke exit fordi her retur ikke vil gjøre noe.

904
01:10:53,600 --> 01:10:57,140
Vi er ikke i hovedsak ikke så returnere ikke avslutte programmet som vi ønsker.

905
01:10:57,140 --> 01:11:03,020
Så vi bruker exit-funksjonen og gi det en feilkode.

906
01:11:03,020 --> 01:11:11,890
Så her har vi satt nye nodens verdi feltet, dens jeg felt til å være lik i, og vi koble den opp.

907
01:11:11,890 --> 01:11:15,530
Vi setter ny node neste pekeren å peke på først,

908
01:11:15,530 --> 01:11:20,460
og deretter første vil nå peke på den nye noden.

909
01:11:20,460 --> 01:11:25,120
Disse første linjene med kode, vi faktisk bygge den nye noden.

910
01:11:25,120 --> 01:11:27,280
Ikke de to siste linjene i denne funksjonen, men de første.

911
01:11:27,280 --> 01:11:30,290
Du kan faktisk trekke ut i en funksjon, i en hjelper funksjon.

912
01:11:30,290 --> 01:11:32,560
Det er ofte det jeg gjør er, trekker jeg det ut i en funksjon,

913
01:11:32,560 --> 01:11:36,040
Jeg kaller det noe sånt som build node,

914
01:11:36,040 --> 01:11:40,410
og som holder den foranstilte funksjonen ganske liten, er det bare 3 linjer da.

915
01:11:40,410 --> 01:11:48,710
Jeg ringer til min bygge node funksjon, og da jeg ledningen alt opp.

916
01:11:48,710 --> 01:11:51,970
>> Den siste tingen jeg vil vise deg,

917
01:11:51,970 --> 01:11:54,030
og jeg vil la deg gjøre append og alt som på egen hånd,

918
01:11:54,030 --> 01:11:57,500
er hvordan man skal iterere over en liste.

919
01:11:57,500 --> 01:12:00,780
Det er en haug med forskjellige måter å iterere over en liste.

920
01:12:00,780 --> 01:12:03,140
I dette tilfellet skal vi finne lengden på en liste.

921
01:12:03,140 --> 01:12:06,570
Så vi starter med lengde = 0.

922
01:12:06,570 --> 01:12:11,580
Dette er svært likt å skrive strlen for en streng.

923
01:12:11,580 --> 01:12:17,780
Dette er hva jeg ønsker å vise deg, dette for loop her.

924
01:12:17,780 --> 01:12:23,530
Det ser ganske funky, det er ikke vanlig int i = 0, i <uansett, i + +.

925
01:12:23,530 --> 01:12:34,920
I stedet er det initialiseres vår variable n å være begynnelsen av listen.

926
01:12:34,920 --> 01:12:40,620
Og så mens vår iterator variabel ikke er null, holder vi går.

927
01:12:40,620 --> 01:12:46,340
Dette er fordi, etter konvensjonen, vil slutten av vår liste være null.

928
01:12:46,340 --> 01:12:48,770
Og deretter å øke, heller enn å gjøre + +,

929
01:12:48,770 --> 01:12:57,010
den lenket liste tilsvarende + + er n = n-> neste.

930
01:12:57,010 --> 01:13:00,410
>> Jeg skal fortelle deg fylle ut hullene her fordi vi er ute av tiden.

931
01:13:00,410 --> 01:13:09,300
Men ha dette i bakhodet når du arbeider på spellr psets.

932
01:13:09,300 --> 01:13:11,650
Koblede lister, hvis du implementere en hash table,

933
01:13:11,650 --> 01:13:14,010
vil definitivt komme i svært hendig.

934
01:13:14,010 --> 01:13:21,780
Og å ha denne idiom for looping over ting vil gjøre livet mye enklere, forhåpentligvis.

935
01:13:21,780 --> 01:13:25,910
Eventuelle spørsmål, raskt?

936
01:13:25,910 --> 01:13:28,920
[Sam] Vil du sende ut den ferdige sll og fm?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Jeg sender ut fullførte lysbilder og fullførte sll stabelen og queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]