1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Afsnit 6: Mindre Comfortable]

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 afsnit 6.

5
00:00:11,840 --> 00:00:14,690
I denne uge vil vi tale om datastrukturer i snit,

6
00:00:14,690 --> 00:00:19,780
primært fordi denne uges problem indstillet på spellr

7
00:00:19,780 --> 00:00:24,410
gør en hel masse forskellige datastruktur udforskning.

8
00:00:24,410 --> 00:00:26,520
Der er en masse forskellige måder, du kan gå med problemet sæt,

9
00:00:26,520 --> 00:00:31,570
og jo flere datastrukturer du kender, jo mere seje ting, du kan gøre.

10
00:00:31,570 --> 00:00:34,990
>> Så lad os komme i gang. Først vil vi snakke om stakke,

11
00:00:34,990 --> 00:00:37,530
stakken og kø datastrukturer, som vi kommer til at snakke om.

12
00:00:37,530 --> 00:00:40,560
Stakke og køer er virkelig nyttige, når vi begynder at tale om grafer,

13
00:00:40,560 --> 00:00:44,390
som vi ikke kommer til at gøre så meget af lige nu.

14
00:00:44,390 --> 00:00:52,820
Men de er rigtig gode til at forstå en af ​​de store fundamentale datastrukturer i CS.

15
00:00:52,820 --> 00:00:54,880
Beskrivelsen i det problem indstillede specifikation,

16
00:00:54,880 --> 00:00:59,260
hvis du trækker den op, fortæller om stacks som beslægtet med

17
00:00:59,260 --> 00:01:05,239
bunken af ​​spisning bakker, som du har i cafeteriet ved spisesale

18
00:01:05,239 --> 00:01:09,680
hvor når spise personale kommer og sætter de spise bakker ud, efter at de har renset dem,

19
00:01:09,680 --> 00:01:12,000
De stable dem oven på hinanden.

20
00:01:12,000 --> 00:01:15,050
Og så når børnene kommer i at få mad,

21
00:01:15,050 --> 00:01:19,490
de trække bakkerne ud, først den øverste, så den ene under den, så den ene under dette.

22
00:01:19,490 --> 00:01:25,190
Så i realiteten er den første bakke, spise personale lagde sidste, der bliver taget.

23
00:01:25,190 --> 00:01:32,330
Den sidste at spise personale sat på er det første, der bliver taget ud til middag.

24
00:01:32,330 --> 00:01:38,100
I det problem apparatets spec, du som kan hente, hvis du ikke allerede har gjort det,

25
00:01:38,100 --> 00:01:46,730
vi taler om at modellere en stak data stucture bruge denne form for struct.

26
00:01:46,730 --> 00:01:51,070
>> Så hvad vi har her, det svarer til, hvad der blev præsenteret i foredrag,

27
00:01:51,070 --> 00:01:58,120
undtagen i foredrag vi forelagde dette med int'er i modsætning til char * s.

28
00:01:58,120 --> 00:02:06,250
Dette vil være en stak, der gemmer hvad?

29
00:02:06,250 --> 00:02:09,009
Daniel? Hvad skal vi opbevare i denne stak?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Vi gemmer strenge i denne stak, præcis.

31
00:02:15,260 --> 00:02:20,950
Alt hvad du behøver at have for at skabe en stak er et array

32
00:02:20,950 --> 00:02:23,920
af en bestemt egenskab, som i dette tilfælde

33
00:02:23,920 --> 00:02:28,020
kapacitet vil være i alle caps, fordi det er en konstant.

34
00:02:28,020 --> 00:02:36,340
Og derefter ud over arrayet, er alt hvad vi nødt til at spore den aktuelle størrelse af matrixen.

35
00:02:36,340 --> 00:02:38,980
Én ting at bemærke her, at er lidt cool

36
00:02:38,980 --> 00:02:47,060
er, at vi skaber den stablede datastruktur oven på en anden datastruktur, arrayet.

37
00:02:47,060 --> 00:02:50,110
Der er forskellige måder at gennemføre stakke.

38
00:02:50,110 --> 00:02:54,250
Vi vil ikke gøre det helt endnu, men forhåbentlig efter at gøre den sammenkædede-list problemer,

39
00:02:54,250 --> 00:03:00,520
du vil se, hvordan du nemt kan implementere en stak på toppen af ​​en linket liste så godt.

40
00:03:00,520 --> 00:03:02,640
Men for nu, vil vi holde os til arrays.

41
00:03:02,640 --> 00:03:06,350
Så igen, alt hvad vi behøver er en matrix, og vi bare nødt til at spore størrelsen af ​​array.

42
00:03:06,350 --> 00:03:09,850
[Sam] Beklager, hvorfor er det, at du sagde stakken er på toppen af ​​strengene?

43
00:03:09,850 --> 00:03:13,440
For mig ser det ud som strengene ligger inden for stakken.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Vi skaber, vi tager vores array datastruktur -

45
00:03:16,790 --> 00:03:22,130
Det er et godt spørgsmål. Så spørgsmålet er, hvorfor, for de mennesker, der ser dette online,

46
00:03:22,130 --> 00:03:24,140
hvorfor siger vi, at stakken er på toppen af ​​strengene,

47
00:03:24,140 --> 00:03:27,990
fordi her ser det ud til strengene er inde i stakken?

48
00:03:27,990 --> 00:03:31,050
Som er helt tilfældet.

49
00:03:31,050 --> 00:03:34,660
Hvad jeg henviste til, var, at vi har fået et array datastruktur.

50
00:03:34,660 --> 00:03:39,290
Vi har fået en række char * s, denne vifte af strenge,

51
00:03:39,290 --> 00:03:45,300
og vi vil tilføje til, at for at skabe den stablede datastruktur.

52
00:03:45,300 --> 00:03:48,620
>> Så en stak er lidt mere kompliceret end et array.

53
00:03:48,620 --> 00:03:51,890
Vi kan bruge et array til at bygge en skorsten.

54
00:03:51,890 --> 00:03:55,810
Så det er, hvor vi siger, at stakken er bygget oven på et array.

55
00:03:55,810 --> 00:04:02,510
Ligeledes, som jeg sagde tidligere, kan vi bygge en stak på toppen af ​​en linket liste.

56
00:04:02,510 --> 00:04:04,960
I stedet for at bruge et array til at holde vores elementer,

57
00:04:04,960 --> 00:04:10,070
vi kunne bruge en sammenkædet liste til at holde vores elementer og bygge stakken omkring det.

58
00:04:10,070 --> 00:04:12,420
Lad os gennemgå et par eksempler, se på noget kode,

59
00:04:12,420 --> 00:04:14,960
for at se, hvad der rent faktisk sker her.

60
00:04:14,960 --> 00:04:23,400
Til venstre, har jeg smidt ned, hvad der stak struct ville se ud i hukommelsen

61
00:04:23,400 --> 00:04:28,330
hvis kapaciteten # blev defineret til at være fire.

62
00:04:28,330 --> 00:04:33,490
Vi har vores fire-element char * array.

63
00:04:33,490 --> 00:04:38,110
Vi har strings [0], strings [1], strings [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
og så det sidste plads til vores størrelse heltal.

65
00:04:43,800 --> 00:04:46,270
Giver det mening? Okay.

66
00:04:46,270 --> 00:04:48,790
Dette er, hvad der sker, hvis det, jeg gør til højre,

67
00:04:48,790 --> 00:04:55,790
som vil være min kode, er at bare erklære en struct, en stablet struct kaldet s.

68
00:04:55,790 --> 00:05:01,270
Det er, hvad vi får. Det fastlægger dette fodaftryk i hukommelsen.

69
00:05:01,270 --> 00:05:05,590
Det første spørgsmål her er, hvad er indholdet af denne stak struct?

70
00:05:05,590 --> 00:05:09,250
Lige nu er de ingenting, men de er ikke helt ingenting.

71
00:05:09,250 --> 00:05:13,300
De er denne form for skrald. Vi har ingen idé om, hvad der er i dem.

72
00:05:13,300 --> 00:05:17,000
Når vi erklærer stack s, er vi bare at smide det ned på toppen af ​​hukommelsen.

73
00:05:17,000 --> 00:05:19,840
Det er lidt ligesom at erklære int i og ikke initialisere det.

74
00:05:19,840 --> 00:05:21,730
Du ved ikke, hvad der er derinde. Du kan læse, hvad der er derinde,

75
00:05:21,730 --> 00:05:27,690
men det kan ikke være super nyttige.

76
00:05:27,690 --> 00:05:32,680
Én ting du vil altid huske at gøre, er initialisere hvad der skal initialiseres.

77
00:05:32,680 --> 00:05:35,820
I dette tilfælde vil vi initialisere størrelse at være nul,

78
00:05:35,820 --> 00:05:39,960
fordi det kommer til at vise sig at være meget vigtigt for os.

79
00:05:39,960 --> 00:05:43,450
Vi kunne gå videre og initialisere alle pegepinde, alle char * s,

80
00:05:43,450 --> 00:05:49,670
at være nogle forståelige værdi, sandsynligvis null.

81
00:05:49,670 --> 00:05:58,270
Men det er ikke helt nødvendigt, at vi gør det.

82
00:05:58,270 --> 00:06:04,200
>> Nu er de to vigtigste operationer på stakke er?

83
00:06:04,200 --> 00:06:07,610
Nogen husker fra foredrag hvad du gør med stakke? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Skubbe og popping? >> Præcis.

85
00:06:09,700 --> 00:06:13,810
Pushing og popping er de to vigtigste operationer på stakke.

86
00:06:13,810 --> 00:06:17,060
Og hvad betyder skub gøre? >> Det sætter noget på toppen

87
00:06:17,060 --> 00:06:19,300
af stakken, og derefter popping tager det ud.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Præcis. Så skubber skubber noget på toppen af ​​stakken.

89
00:06:23,150 --> 00:06:27,700
Det er ligesom spise personale sætte en spisestue bakke ned på tælleren.

90
00:06:27,700 --> 00:06:33,630
Og popping tager en spise bakke ud af stakken.

91
00:06:33,630 --> 00:06:36,460
Lad os gå gennem et par eksempler på, hvad der sker

92
00:06:36,460 --> 00:06:39,720
når vi presser tingene ned i stakken.

93
00:06:39,720 --> 00:06:45,110
Hvis vi skulle til at skubbe strengen 'hello' på vores stack,

94
00:06:45,110 --> 00:06:49,760
dette er, hvad vores diagram ville se ud nu.

95
00:06:49,760 --> 00:06:53,410
Se hvad der sker?

96
00:06:53,410 --> 00:06:56,530
Vi pressede ind i den første del af vores strenge opstilling

97
00:06:56,530 --> 00:07:01,420
og vi forøgede vores størrelse tæller at være 1.

98
00:07:01,420 --> 00:07:05,340
Så hvis vi ser på forskellen mellem de to dias, her var 0, her er før push.

99
00:07:05,340 --> 00:07:08,690
Her er efter push.

100
00:07:08,690 --> 00:07:13,460
Før push,. Efter push

101
00:07:13,460 --> 00:07:16,860
Og nu har vi et element i vores stak.

102
00:07:16,860 --> 00:07:20,970
Det er strengen "hello", og det er det.

103
00:07:20,970 --> 00:07:24,440
Alt andet i arrayet, i vores strings matrix, stadig er skrald.

104
00:07:24,440 --> 00:07:27,070
Vi har ikke initialiseret det.

105
00:07:27,070 --> 00:07:29,410
Lad os sige, at vi skubber en anden streng på vores stack.

106
00:07:29,410 --> 00:07:32,210
Vi kommer til at skubbe "verden" på dette tidspunkt.

107
00:07:32,210 --> 00:07:35,160
Så du kan se "verden" her går på toppen af ​​"hello",

108
00:07:35,160 --> 00:07:40,040
og størrelsen tæller går op til 2.

109
00:07:40,040 --> 00:07:44,520
Nu kan vi skubbe "CS50", og der vil gå på toppen igen.

110
00:07:44,520 --> 00:07:51,110
Hvis vi går tilbage, kan du se, hvordan vi skubbe ting på toppen af ​​stakken.

111
00:07:51,110 --> 00:07:53,320
Og nu får vi at pop.

112
00:07:53,320 --> 00:07:58,910
Når vi dukkede noget ud af stakken, hvad skete der?

113
00:07:58,910 --> 00:08:01,540
Nogen se forskellen? Det er temmelig subtil.

114
00:08:01,540 --> 00:08:05,810
[Student] Størrelsen. >> Ja, størrelsen ændret.

115
00:08:05,810 --> 00:08:09,040
>> Hvad ville du have forventet at ændre?

116
00:08:09,040 --> 00:08:14,280
[Student] De strenge, også. >> Højre. Strengene også.

117
00:08:14,280 --> 00:08:17,110
Det viser sig, at når du gør det på denne måde,

118
00:08:17,110 --> 00:08:21,960
fordi vi ikke kopiering af elementerne i vores stak,

119
00:08:21,960 --> 00:08:24,670
vi faktisk ikke behøver at gøre noget, og vi kan bare bruge den størrelse

120
00:08:24,670 --> 00:08:28,630
at holde styr på antallet af ting i vores array

121
00:08:28,630 --> 00:08:33,780
så når vi pop igen, igen vi bare formindske vores størrelse ned til 1.

122
00:08:33,780 --> 00:08:39,440
Der er ingen grund til rent faktisk at gå ind og overskrive noget.

123
00:08:39,440 --> 00:08:41,710
Kind of funky.

124
00:08:41,710 --> 00:08:46,520
Det viser sig, at vi typisk bare lade tingene alene, fordi det er mindre arbejde for os at gøre.

125
00:08:46,520 --> 00:08:50,060
Hvis vi ikke behøver at gå tilbage og overskrive noget, så hvorfor gøre det?

126
00:08:50,060 --> 00:08:54,150
Så når vi pop to gange ud af stakken, alt det gør, er at formindske størrelsen et par gange.

127
00:08:54,150 --> 00:08:59,120
Og igen, det er kun fordi vi ikke kopiere ting i vores stack.

128
00:08:59,120 --> 00:09:01,320
Ja? Værsgo.

129
00:09:01,320 --> 00:09:04,460
[Studerende, uforståelig] >> Og hvad sker der, når du skubber noget igen?

130
00:09:04,460 --> 00:09:08,570
Når du trykker på noget igen, hvor er det hen?

131
00:09:08,570 --> 00:09:12,390
Hvor går det hen, Basil? >> Into strings [1]? >> Højre.

132
00:09:12,390 --> 00:09:14,530
Hvorfor det ikke gå ind strings [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Fordi det glemte, at der var noget i strings [1] og [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Præcis. Vores stack væsentlige, "glemte" at det var at holde fast i noget som helst

135
00:09:24,040 --> 00:09:29,480
i strings [1] eller strings [2], så når vi skubber "woot",

136
00:09:29,480 --> 00:09:36,670
det bare sætter den ind i elementet ved strings [1].

137
00:09:36,670 --> 00:09:41,590
Er der nogen spørgsmål om, hvordan det fungerer, på et grundlæggende niveau?

138
00:09:41,590 --> 00:09:45,160
[Sam] Så det er ikke dynamisk på nogen måde, i beløb

139
00:09:45,160 --> 00:09:47,620
eller i form af størrelsen af ​​stakken?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Præcis. Dette er - det punkt var, at dette ikke var en dynamisk growning stak.

141
00:09:56,750 --> 00:10:02,850
Dette er en stak, der kan holde på de fleste, fire char * s, højst fire ting.

142
00:10:02,850 --> 00:10:07,580
Hvis vi skulle forsøge at skubbe en femte ting, hvad tror du der skal ske?

143
00:10:07,580 --> 00:10:11,870
[Studerende, uforståelige]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Præcis. Der er en række ting, der kunne ske.

145
00:10:14,600 --> 00:10:19,330
Det kunne muligvis seg fejl, afhængigt af, hvad vi var -

146
00:10:19,330 --> 00:10:22,530
præcis hvordan vi gennemføre back-end.

147
00:10:22,530 --> 00:10:31,740
Det kunne overskrive. Det kunne have denne buffer overflow, som vi talte om i klassen.

148
00:10:31,740 --> 00:10:35,240
Hvad ville være det mest oplagte ting, der kan blive overskrevet

149
00:10:35,240 --> 00:10:42,370
hvis vi forsøgte at presse en ekstra ting på vores stak?

150
00:10:42,370 --> 00:10:44,550
Så du nævnte en buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Hvad kan være ting, der ville få skrevet over eller trampet på

152
00:10:47,870 --> 00:10:52,320
hvis vi overløb uheld ved at forsøge at skubbe en ekstra ting?

153
00:10:52,320 --> 00:10:54,730
[Daniel, uforståelig] >> Muligt.

154
00:10:54,730 --> 00:10:58,440
Men i første omgang kan der ske? Hvad hvis vi forsøgte at skubbe en fjerde ting?

155
00:10:58,440 --> 00:11:06,220
Det kan overskrive den størrelse, i hvert fald med denne hukommelse diagram, som vi har.

156
00:11:06,220 --> 00:11:10,880
>> I det problem indstillede specifikation, er der hvad vi kommer til at gennemføre i dag,

157
00:11:10,880 --> 00:11:16,030
hvad vi ønsker at gøre, er bare returnere falsk.

158
00:11:16,030 --> 00:11:20,030
Vores pushmetoden vil returnere en boolesk værdi,

159
00:11:20,030 --> 00:11:22,920
og at boolean værdi vil være tilfældet, hvis push lykkes

160
00:11:22,920 --> 00:11:29,730
og falsk, hvis vi ikke kan skubbe noget mere, fordi stakken er fuld.

161
00:11:29,730 --> 00:11:33,620
Lad os gå gennem en lille smule af denne kodeks lige nu.

162
00:11:33,620 --> 00:11:36,400
Her er vores push-funktion.

163
00:11:36,400 --> 00:11:40,380
Vores push-funktion til en stak vil tage i strengen til at sætte på stakken.

164
00:11:40,380 --> 00:11:45,820
Det kommer til at returnere true hvis strengen held blev skubbet

165
00:11:45,820 --> 00:11:51,820
på stakken og falsk ellers.

166
00:11:51,820 --> 00:11:59,740
Nogen forslag til hvad der kunne være en god første ting at gøre her?

167
00:11:59,740 --> 00:12:20,630
[Sam] Hvis størrelse er lig med kapaciteten derefter vende tilbage falsk?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice job.

169
00:12:23,320 --> 00:12:26,310
Hvis størrelsen er den kapacitet, vi kommer til at returnere falsk.

170
00:12:26,310 --> 00:12:29,270
Vi kan ikke sætte noget mere i vores stak.

171
00:12:29,270 --> 00:12:36,900
Ellers ønsker vi at sætte noget på toppen af ​​stakken.

172
00:12:36,900 --> 00:12:41,670
Hvad er "toppen af ​​stakken," i første omgang?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Størrelse 0? >> Size 0.

174
00:12:43,650 --> 00:12:49,990
Hvad er toppen af ​​stakken efter der er én ting i stakken? Missy, kender du?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Size er én, præcis. Du holde tilføje til den størrelse,

176
00:12:52,720 --> 00:13:01,690
og hver gang du putter i det nye element til indeks størrelse i array.

177
00:13:01,690 --> 00:13:05,470
Vi kan gøre det med den slags one-liner, hvis det giver mening.

178
00:13:05,470 --> 00:13:11,910
Så vi har fået vores strenge array, vi kommer til at få adgang til det på den størrelse indeks,

179
00:13:11,910 --> 00:13:14,780
og vi vil bare gemme vores char * derinde.

180
00:13:14,780 --> 00:13:19,340
Bemærk at der er ingen snor kopiering foregår i her,

181
00:13:19,340 --> 00:13:29,680
ingen dynamisk allokering af hukommelse?

182
00:13:29,680 --> 00:13:34,440
Og så Missy opdraget hvad vi nu skal gøre,

183
00:13:34,440 --> 00:13:40,570
fordi vi har gemt snoren på et passende sted i arrayet,

184
00:13:40,570 --> 00:13:49,230
og hun sagde, at vi var nødt til at forøge størrelsen af ​​en, så vi er klar til det næste tryk.

185
00:13:49,230 --> 00:13:53,950
Så vi kan gøre det med s.size + +.

186
00:13:53,950 --> 00:13:59,330
På dette tidspunkt har vi skubbet ind i vores array. Hvad er det sidste, vi skal gøre?

187
00:13:59,330 --> 00:14:10,110
[Student] Tilbage sandt. >> Returnere sandt.

188
00:14:10,110 --> 00:14:14,690
Så det er ret simpelt, en temmelig simpel kode. Ikke for meget.

189
00:14:14,690 --> 00:14:17,070
Når du har pakket dit hoved omkring hvordan stakken virker,

190
00:14:17,070 --> 00:14:21,910
dette er temmelig enkel at anvende.

191
00:14:21,910 --> 00:14:26,390
>> Nu er den næste del af denne popping en streng ud af stablen.

192
00:14:26,390 --> 00:14:29,410
Jeg har tænkt mig at give jer lidt tid til at arbejde på dette en lille smule.

193
00:14:29,410 --> 00:14:34,320
Det er næsten grundlæggende det modsatte af, hvad vi har gjort her i push.

194
00:14:34,320 --> 00:14:38,510
Hvad jeg har gjort, er faktisk - oops.

195
00:14:38,510 --> 00:14:48,160
Jeg er startet op på et apparat herovre, og i apparatet,

196
00:14:48,160 --> 00:14:53,600
Jeg har trukket op på problemet sæt 5-specifikationen.

197
00:14:53,600 --> 00:15:02,560
Hvis vi zoomer ind her, kan vi se, at jeg er ved cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Har du fyre downloadet denne kode, der er placeret her, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Ok. Hvis du ikke har gjort det, gøre det lige nu, virkelig hurtigt.

200
00:15:15,030 --> 00:15:22,130
Jeg vil gøre det i min terminal vindue.

201
00:15:22,130 --> 00:15:25,090
Jeg faktisk gjorde det op her. Yeah.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Jeg har et spørgsmål om, hvorfor sagde du s.string 's parentes af størrelse = str?

203
00:15:34,730 --> 00:15:42,910
Hvad er str? Er den, der et eller andet sted før, eller - oh, i den char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ja, præcis. Det var argumentet. >> Åh, okay. Undskyld.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Vi angiver strengen til at skubbe i.

206
00:15:49,470 --> 00:15:55,220
Det andet spørgsmål, der kan komme op at vi ikke virkelig tale om her var

207
00:15:55,220 --> 00:15:58,810
vi tog for givet, at vi havde denne variabel kaldet s

208
00:15:58,810 --> 00:16:02,710
der var i omfang og tilgængelige for os.

209
00:16:02,710 --> 00:16:06,960
Vi tog for givet, at s var denne stak struct.

210
00:16:06,960 --> 00:16:08,930
Så ser tilbage på denne push-kode,

211
00:16:08,930 --> 00:16:13,450
du kan se, at vi gør ting med denne streng, der fik vedtaget i

212
00:16:13,450 --> 00:16:19,210
men så lige pludselig, vi adgang s.size, ligesom, hvor kom s komme fra?

213
00:16:19,210 --> 00:16:23,020
I den kode, vi kommer til at se på, i afsnittet arkiv

214
00:16:23,020 --> 00:16:27,100
og så de ting, du vil gøre i dit problem sætter,

215
00:16:27,100 --> 00:16:32,440
vi har lavet vores stak konstruere en global variabel

216
00:16:32,440 --> 00:16:36,380
så vi kan få adgang til den i alle vores forskellige funktioner

217
00:16:36,380 --> 00:16:40,630
uden at skulle manuelt passere den rundt og videregive det som reference,

218
00:16:40,630 --> 00:16:44,870
gøre alt den slags ting til det.

219
00:16:44,870 --> 00:16:52,280
Vi er bare snyder en lille smule, hvis du vil, for at gøre tingene pænere.

220
00:16:52,280 --> 00:16:57,430
Og det er noget, vi laver her, fordi det er for sjov, er det lettere.

221
00:16:57,430 --> 00:17:02,800
Ofte vil du se folk gøre dette, hvis de har en stor datastruktur

222
00:17:02,800 --> 00:17:07,750
, der bliver opereret i løbet af deres program.

223
00:17:07,750 --> 00:17:09,560
>> Lad os gå tilbage over til apparatet.

224
00:17:09,560 --> 00:17:15,240
Havde alle held få section6.zip?

225
00:17:15,240 --> 00:17:20,440
Alle unzip det ved hjælp lyne section6.zip?

226
00:17:20,440 --> 00:17:27,200
Hvis du går ind i sektion 6 bibliotek -

227
00:17:27,200 --> 00:17:29,220
aah, over det hele -

228
00:17:29,220 --> 00:17:32,840
og du liste hvad der er i her, kan du se at du har fået tre forskellige. C-filer.

229
00:17:32,840 --> 00:17:38,350
Du har en kø, en SLL, der er enkeltvis-linkede liste, og en stak.

230
00:17:38,350 --> 00:17:44,600
Hvis du åbner op stack.c,

231
00:17:44,600 --> 00:17:47,330
du kan se, at vi har fået denne struct defineret for os,

232
00:17:47,330 --> 00:17:51,330
den nøjagtige struct som vi lige har talt om i dias.

233
00:17:51,330 --> 00:17:56,340
Vi har vores globale variabel for stakken,

234
00:17:56,340 --> 00:18:00,110
vi har fået vores push-funktion,

235
00:18:00,110 --> 00:18:04,230
og så har vi vores pop funktion.

236
00:18:04,230 --> 00:18:08,320
Jeg vil sætte koden for skubbe op på objektglasset her,

237
00:18:08,320 --> 00:18:10,660
men hvad jeg gerne vil have jer til at gøre, er, at det bedste af dine evner,

238
00:18:10,660 --> 00:18:13,790
gå og gennemføre pop-funktionen.

239
00:18:13,790 --> 00:18:18,480
Når du har gennemført det, kan du samle dette med make stack,

240
00:18:18,480 --> 00:18:22,540
og derefter køre den resulterende stak eksekverbare,

241
00:18:22,540 --> 00:18:28,390
og der vil køre hele denne test-kode hernede, der er i main.

242
00:18:28,390 --> 00:18:31,060
Og main tager sig af rent faktisk at gøre det push og pop opkald

243
00:18:31,060 --> 00:18:33,220
og sikre, at alt går igennem okay.

244
00:18:33,220 --> 00:18:36,820
Det er også initialiserer stakstørrelsen lige her

245
00:18:36,820 --> 00:18:39,780
så du ikke behøver at bekymre dig om at initialisere det.

246
00:18:39,780 --> 00:18:42,310
Du kan antage, at det har været korrekt initialiseret

247
00:18:42,310 --> 00:18:48,000
af den tid, du har adgang til den i pop-funktionen.

248
00:18:48,000 --> 00:18:53,530
Giver det mening?

249
00:18:53,530 --> 00:19:00,100
Så her går vi. Der er push-koden.

250
00:19:00,100 --> 00:19:13,210
Jeg vil give jer 5 eller 10 minutter.

251
00:19:13,210 --> 00:19:15,690
Og hvis du har spørgsmål i mellemtiden, mens du kodning,

252
00:19:15,690 --> 00:19:17,710
kan du bede dem højt.

253
00:19:17,710 --> 00:19:23,080
Så hvis du kommer til et springende punkt, bare spørg.

254
00:19:23,080 --> 00:19:26,030
Lad mig vide, lad alle andre vide.

255
00:19:26,030 --> 00:19:28,160
Arbejd med din nabo også.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Vi er lige gennemføre pop lige nu? >> Bare pop.

257
00:19:30,360 --> 00:19:34,200
Selvom du kan kopiere gennemførelsen af ​​push, hvis du vil

258
00:19:34,200 --> 00:19:37,780
således at testen vil arbejde.

259
00:19:37,780 --> 00:19:41,940
Fordi det er svært at teste tingene komme ind -

260
00:19:41,940 --> 00:19:49,030
eller, det er svært at teste affyret ting ud af en stak, hvis der ikke er noget i stakken til at begynde med.

261
00:19:49,030 --> 00:19:55,250
>> Hvad er pop formodes at være tilbage? Elementet fra toppen af ​​stakken.

262
00:19:55,250 --> 00:20:01,260
Det er meningen at få elementet væk fra toppen af ​​stakken

263
00:20:01,260 --> 00:20:05,780
og derefter dekrementere størrelsen af ​​stakken,

264
00:20:05,780 --> 00:20:07,810
og nu har du mistet element på toppen.

265
00:20:07,810 --> 00:20:11,420
Og så skal du returnere element på toppen.

266
00:20:11,420 --> 00:20:20,080
[Studerende, uforståelig]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Så hvad sker der, hvis du gør det? [Studerende, uforståelig]

268
00:20:28,810 --> 00:20:34,000
Hvad ender sker, er du sandsynligvis få adgang til enten

269
00:20:34,000 --> 00:20:37,350
et element, der ikke er blevet initialiseret endnu, så din beregning

270
00:20:37,350 --> 00:20:39,990
hvor det sidste element er er slukket.

271
00:20:39,990 --> 00:20:46,260
Så her, hvis du bemærker, i tryk, vi adgang strenge på s.size element

272
00:20:46,260 --> 00:20:48,560
fordi det er et nyt indeks.

273
00:20:48,560 --> 00:20:51,460
Det er den nye toppen af ​​stakken.

274
00:20:51,460 --> 00:21:01,100
Betragtninger i pop, er s.size vil være den næste plads,

275
00:21:01,100 --> 00:21:05,210
den plads, der er på toppen af ​​alle elementer i din stack.

276
00:21:05,210 --> 00:21:10,050
Så den øverste element er ikke s.size,

277
00:21:10,050 --> 00:21:14,930
men snarere, det er under den.

278
00:21:14,930 --> 00:21:19,640
>> Den anden ting at gøre, når du - i pop,

279
00:21:19,640 --> 00:21:22,030
er du nødt til at formindske størrelsen.

280
00:21:22,030 --> 00:21:28,750
Hvis du kan huske tilbage til vores lille diagram lige her,

281
00:21:28,750 --> 00:21:30,980
virkelig, det eneste, vi så ske når vi kaldes pop

282
00:21:30,980 --> 00:21:36,150
var, at denne størrelse faldt først til 2, derefter til 1.

283
00:21:36,150 --> 00:21:42,620
Så når vi pressede et nyt element på, ville det gå på på det rigtige sted.

284
00:21:42,620 --> 00:21:49,610
[Basil] Hvis s.size er 2, så ville det ikke gå til element 2,

285
00:21:49,610 --> 00:21:54,400
og så ville du ønsker at pop dette element fra?

286
00:21:54,400 --> 00:21:59,510
Så hvis vi gik til - >> Så lad os se på det igen.

287
00:21:59,510 --> 00:22:07,730
Hvis dette er vores stak på dette tidspunkt

288
00:22:07,730 --> 00:22:12,130
og vi kalder pop,

289
00:22:12,130 --> 00:22:16,150
på hvilket indeks er det øverste element?

290
00:22:16,150 --> 00:22:19,300
[Basil] På 2, men det kommer til at poppe 3. >> Højre.

291
00:22:19,300 --> 00:22:24,220
Så det er, hvor vores størrelse er 3, men vi ønsker at pop elementet i indeks 2.

292
00:22:24,220 --> 00:22:29,900
Det er den typiske form for off med en, som du har med nul-indeksering af arrays.

293
00:22:29,900 --> 00:22:36,430
Så du ønsker at pop det tredje element, men det tredje element er ikke i indeks 3.

294
00:22:36,430 --> 00:22:39,430
Og grunden til at vi ikke behøver at gøre det minus 1 når vi skubber

295
00:22:39,430 --> 00:22:44,120
er fordi lige nu, bemærker du, at det øverste element,

296
00:22:44,120 --> 00:22:47,600
hvis vi presse noget andet på stakken ved dette punkt,

297
00:22:47,600 --> 00:22:50,360
vi ønsker at skubbe det på indeks 3.

298
00:22:50,360 --> 00:23:03,550
Og det bare så sker det, at størrelsen og indeksene linje op, når du presser.

299
00:23:03,550 --> 00:23:06,960
>> Hvem har en arbejdsgruppe stak gennemførelse?

300
00:23:06,960 --> 00:23:09,690
Du har fået en arbejdsgruppe stak en. Har du pop arbejder endnu?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ja. Det tror jeg.

302
00:23:11,890 --> 00:23:14,610
>> Programmet kører og ikke seg forkastning, det udskrivning ud?

303
00:23:14,610 --> 00:23:17,520
Betyder det udskrive "succes", når du kører det?

304
00:23:17,520 --> 00:23:22,630
Yeah. Gør stable, kør det, hvis den udskriver "succes" og ikke går boom,

305
00:23:22,630 --> 00:23:26,000
så alt er godt.

306
00:23:26,000 --> 00:23:34,070
Ok. Lad os gå over til apparatet virkelig hurtigt,

307
00:23:34,070 --> 00:23:46,100
og vi vil gå igennem dette.

308
00:23:46,100 --> 00:23:51,110
Hvis vi ser på, hvad der sker her med pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, hvad der var den første ting, du gjorde?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Hvis s.size er større end 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 at sikre at der var noget inde i stakken.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Right. Du ønsker at teste for at sikre, at s.size er større end 0;

314
00:24:10,950 --> 00:24:13,280
ellers, hvad vil du have ske?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Return null, præcis.

316
00:24:16,630 --> 00:24:20,740
Så hvis s.size er større end 0. Så hvad skal vi gøre?

317
00:24:20,740 --> 00:24:25,890
Hvad gør vi, hvis stakken ikke er tom?

318
00:24:25,890 --> 00:24:31,210
[Stella] Du dekrementere størrelse? >> Du dekrementere størrelse, okay.

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 hvad gjorde du?

321
00:24:37,030 --> 00:24:44,140
[Stella] Og så sagde jeg tilbage 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 behøver det ikke at være s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Yeah. >> Fik det.

326
00:24:58,430 --> 00:25:00,980
[Sam] Jeg tænkte, fordi du tager 1 ud,

327
00:25:00,980 --> 00:25:04,290
så du kommer til at vende tilbage ikke den, som de bad om.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Og det var netop, hvad vi talte om med hele spørgsmålet om 0 indeks.

329
00:25:09,400 --> 00:25:11,380
Så hvis vi ind herovre.

330
00:25:11,380 --> 00:25:15,650
Hvis vi ser på den fyr her kan du se, at når vi pop,

331
00:25:15,650 --> 00:25:19,340
vi popping element ved indeks 2.

332
00:25:19,340 --> 00:25:25,200
>> Så vi reducere vores størrelse først, derefter vores størrelse matcher vores indeks.

333
00:25:25,200 --> 00:25:39,650
Hvis vi ikke formindske størrelsen først, så er vi nødt til at gøre størrelse -1 og derefter Decrement.

334
00:25:39,650 --> 00:25:45,270
Great. All good?

335
00:25:45,270 --> 00:25:47,530
Eventuelle spørgsmål om dette?

336
00:25:47,530 --> 00:25:54,050
Der er en række forskellige måder til at skrive dette.

337
00:25:54,050 --> 00:26:03,290
Faktisk kan vi gøre noget selv - vi kan gøre en one-liner.

338
00:26:03,290 --> 00:26:05,770
Vi kan gøre en one-line afkast.

339
00:26:05,770 --> 00:26:12,980
Så vi kan faktisk formindske før vi tilbage ved at gøre det.

340
00:26:12,980 --> 00:26:18,320
Så sætte - før s.size.

341
00:26:18,320 --> 00:26:22,060
Det gør linjen virkelig tæt.

342
00:26:22,060 --> 00:26:30,940
Hvis forskellen mellem den -. Størrelse og s.size--

343
00:26:30,940 --> 00:26:40,130
er, at denne postfix - de kalder det postfix fordi - kommer efter s.size--

344
00:26:40,130 --> 00:26:47,430
betyder, at s.size evalueres med henblik på at finde indekset

345
00:26:47,430 --> 00:26:50,410
ligesom det er, når denne linie udført,

346
00:26:50,410 --> 00:26:54,290
og derefter dette - sker efter linjen bliver henrettet.

347
00:26:54,290 --> 00:27:00,340
Efter elementet ved indeks s.size tilgås.

348
00:27:00,340 --> 00:27:07,260
Og det er ikke det, vi vil, fordi vi ønsker, at decrement at ske først.

349
00:27:07,260 --> 00:27:10,990
Othewise, vi kommer til at få adgang til array, effektivt, out of bounds.

350
00:27:10,990 --> 00:27:16,850
Vi kommer til at få adgang til elementet oven den, vi faktisk ønsker at få adgang til.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Er det hurtigere eller bruger mindre RAM at gøre i én linje eller ej?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Helt ærligt, det er virkelig afhængig.

353
00:27:29,620 --> 00:27:34,220
[Sam, uforståelig] >> Ja, det afhænger af. Du kan gøre compiler tricks

354
00:27:34,220 --> 00:27:41,580
at få compileren til at erkende, at som regel, jeg kan forestille mig.

355
00:27:41,580 --> 00:27:44,840
>> Så vi har nævnt en lille smule om denne compiler optimering stuff

356
00:27:44,840 --> 00:27:47,400
at du kan gøre ved udarbejdelsen,

357
00:27:47,400 --> 00:27:50,580
og det er den slags ting, at en compiler kan være i stand til at regne ud,

358
00:27:50,580 --> 00:27:54,710
ligesom oh,, hey måske jeg kan gøre det hele i én arbejdsgang,

359
00:27:54,710 --> 00:27:59,420
i modsætning til ilægning af størrelsen variabel i fra RAM,

360
00:27:59,420 --> 00:28:03,770
dekrementere det, gemme det ud igen, og derefter lægger det tilbage i igen

361
00:28:03,770 --> 00:28:08,000
at behandle resten af ​​denne operation.

362
00:28:08,000 --> 00:28:10,710
Men typisk, nej, det er ikke den slags ting

363
00:28:10,710 --> 00:28:20,770
der kommer til at gøre dit program betydeligt hurtigere.

364
00:28:20,770 --> 00:28:26,000
Har du flere spørgsmål om stakke?

365
00:28:26,000 --> 00:28:31,360
>> Så skubber og popping. Hvis du fyre vil prøve hacker udgave,

366
00:28:31,360 --> 00:28:33,660
hvad vi har gjort i hacker-udgaven er faktisk gået

367
00:28:33,660 --> 00:28:37,670
og gjorde denne stak vokse dynamisk.

368
00:28:37,670 --> 00:28:43,190
Udfordringen er først og fremmest op her i push-funktion,

369
00:28:43,190 --> 00:28:48,820
at finde ud af, hvordan man laver den opstilling vokse

370
00:28:48,820 --> 00:28:52,450
som du holde skubbe flere og flere elementer på til stakken.

371
00:28:52,450 --> 00:28:56,000
Det er faktisk ikke for meget ekstra kode.

372
00:28:56,000 --> 00:29:00,080
Blot en opfordring til - du er nødt til at huske at få de opfordringer til malloc derinde korrekt,

373
00:29:00,080 --> 00:29:03,310
og derefter finde ud af, når du kommer til at kalde realloc.

374
00:29:03,310 --> 00:29:06,090
Det er en sjov udfordring, hvis du er interesseret.

375
00:29:06,090 --> 00:29:11,550
>> Men for øjeblikket, lad os komme videre, og lad os tale om køer.

376
00:29:11,550 --> 00:29:15,680
Rul igennem her.

377
00:29:15,680 --> 00:29:19,340
Køen er en tæt søskende af stakken.

378
00:29:19,340 --> 00:29:25,380
Så i stakken, var ting, der sættes i sidste

379
00:29:25,380 --> 00:29:28,810
var de første ting for derefter at blive hentet.

380
00:29:28,810 --> 00:29:33,600
Vi har fået denne sidste ind, først ud, eller LIFO, bestilling.

381
00:29:33,600 --> 00:29:38,390
Betragtninger i køen, som du ville forvente fra når du står i kø

382
00:29:38,390 --> 00:29:41,980
den første person til at komme på linje, den første ting at komme ind i køen,

383
00:29:41,980 --> 00:29:47,630
er den første ting, der bliver hentet fra køen.

384
00:29:47,630 --> 00:29:51,490
Køer er også ofte bruges, når vi har at gøre med grafer,

385
00:29:51,490 --> 00:29:55,560
ligesom vi talte om kort med stakke,

386
00:29:55,560 --> 00:30:00,260
og køer er også praktisk for en masse andre ting.

387
00:30:00,260 --> 00:30:06,180
Én ting, der kommer op ofte forsøger at opretholde, for eksempel,

388
00:30:06,180 --> 00:30:12,310
en sorteret liste af elementer.

389
00:30:12,310 --> 00:30:17,650
Og du kan gøre det med et array. Du kan vedligeholde en sorteret liste over ting i et array,

390
00:30:17,650 --> 00:30:20,650
men hvor det bliver tricky er så du altid nødt til at finde

391
00:30:20,650 --> 00:30:26,160
det rette sted at indsætte den næste ting.

392
00:30:26,160 --> 00:30:28,250
Så hvis du har en bred vifte af numre, 1 til 10,

393
00:30:28,250 --> 00:30:31,630
og du derefter ønsker at udvide det til alle de numre 1 til 100,

394
00:30:31,630 --> 00:30:33,670
og du får disse numre i tilfældig rækkefølge og forsøger at holde alt

395
00:30:33,670 --> 00:30:40,650
sorteret som du går igennem, du ender med at skulle gøre en masse gearskift.

396
00:30:40,650 --> 00:30:43,910
Med visse typer af køer og visse typer af underliggende datastrukturer,

397
00:30:43,910 --> 00:30:46,670
du kan faktisk holde det forholdsvis enkelt.

398
00:30:46,670 --> 00:30:50,640
Du behøver ikke at tilføje noget, og derefter bytte rundt det hele hver gang.

399
00:30:50,640 --> 00:30:56,770
Heller ikke du skal gøre en masse forskydning af interne elementer omkring.

400
00:30:56,770 --> 00:31:02,990
Når vi ser på en kø, du se, at - også i queue.c i afsnittet kode -

401
00:31:02,990 --> 00:31:10,950
den struct, som vi har givet dig er virkelig ligner den struct at vi gav dig for en stak.

402
00:31:10,950 --> 00:31:13,770
>> Der er én undtagelse til dette, og at en enkelt undtagelse

403
00:31:13,770 --> 00:31:21,700
er, at vi har denne ekstra heltal kaldet hovedet,

404
00:31:21,700 --> 00:31:28,120
og hovedet her er til at holde styr på forrest i køen,

405
00:31:28,120 --> 00:31:32,160
eller det første element i køen.

406
00:31:32,160 --> 00:31:37,470
Med en stak, var vi i stand til at holde styr på det element, vi var ved at hente,

407
00:31:37,470 --> 00:31:40,800
eller toppen af ​​stakken, ved blot størrelse,

408
00:31:40,800 --> 00:31:44,220
hvorimod med en kø, vi skulle beskæftige sig med modsatte ender.

409
00:31:44,220 --> 00:31:49,000
Vi forsøger at tack ting på i slutningen, men derefter vende tilbage tingene forfra.

410
00:31:49,000 --> 00:31:54,640
Så effektivt, med hovedet har vi indekset for begyndelsen af ​​køen,

411
00:31:54,640 --> 00:31:58,920
og størrelsen giver os indekset for enden af ​​køen

412
00:31:58,920 --> 00:32:03,730
således at vi kan hente ting fra hovedet og tilføje ting til halen.

413
00:32:03,730 --> 00:32:06,890
Henviser til stablen, var vi altid kun beskæftiger sig med toppen af ​​stack'en.

414
00:32:06,890 --> 00:32:08,900
Vi havde aldrig at få adgang til bunden af ​​stakken.

415
00:32:08,900 --> 00:32:12,220
Vi har kun tilføjet ting til toppen og tog ting ud af toppen

416
00:32:12,220 --> 00:32:17,470
så vi ikke brug for den ekstra felt inde i vores struct.

417
00:32:17,470 --> 00:32:20,590
Betyder det generelt mening?

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ørgsmål, og det var en, der kom op i forelæsning.

420
00:32:32,660 --> 00:32:36,290
Måske gå gennem et par eksempler vil illustrere hvorfor

421
00:32:36,290 --> 00:32:41,400
Vi ønsker ikke at bruge strings [0] som leder af køen.

422
00:32:41,400 --> 00:32:46,770
>> Så forestille sig, at vi har vores kø, vi vil kalde det kø.

423
00:32:46,770 --> 00:32:49,210
I begyndelsen, når vi lige har instantieres det

424
00:32:49,210 --> 00:32:53,330
når vi har netop erklæret det, har vi ikke initialiseret noget.

425
00:32:53,330 --> 00:32:56,790
Det er alt skraldet. Så selvfølgelig vil vi gerne sikre, at vi initialisere

426
00:32:56,790 --> 00:33:00,950
både størrelse og hovedet felterne til at være 0, noget fornuftigt.

427
00:33:00,950 --> 00:33:05,770
Vi kunne også gå videre og null de elementer i vores kø.

428
00:33:05,770 --> 00:33:09,930
Og for at gøre dette diagram fit, bemærke, at nu er vores kø kan kun holde tre elementer;

429
00:33:09,930 --> 00:33:13,150
hvorimod vores stak kunne rumme fire, kan vores kø kun holde tre.

430
00:33:13,150 --> 00:33:18,680
Og det er bare for at gøre diagrammet pasform.

431
00:33:18,680 --> 00:33:26,150
Det første, der sker her, er vi sætte mellemlager strengen "hej".

432
00:33:26,150 --> 00:33:30,380
Og ligesom vi gjorde med stakken, noget forfærdeligt anderledes her,

433
00:33:30,380 --> 00:33:39,230
vi smider strengen på på strings [0] og øg vores størrelse med 1.

434
00:33:39,230 --> 00:33:42,720
Vi sætte mellemlager "bye", det bliver sat på.

435
00:33:42,720 --> 00:33:45,870
Så det ligner en stak for det meste.

436
00:33:45,870 --> 00:33:53,230
Vi startede her, nyt element, nyt element, størrelse holder går op.

437
00:33:53,230 --> 00:33:56,330
Hvad sker der på dette punkt, når vi ønsker at dequeue noget?

438
00:33:56,330 --> 00:34:01,280
Når vi ønsker at dequeue, som er det element, vi ønsker at dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Helt rigtigt, Basil.

440
00:34:04,110 --> 00:34:10,960
Vi ønsker at slippe af med den første streng, denne ene, "hi".

441
00:34:10,960 --> 00:34:13,170
Så hvad var den anden ting, der ændrede?

442
00:34:13,170 --> 00:34:17,010
Læg mærke til, når vi dukkede noget ud af stakken, vi bare ændret størrelse,

443
00:34:17,010 --> 00:34:22,080
men her har vi et par ting at forandring.

444
00:34:22,080 --> 00:34:27,440
Ikke alene deling, men hovedet ændringer.

445
00:34:27,440 --> 00:34:31,020
Det går tilbage til Charlotte synspunkt tidligere:

446
00:34:31,020 --> 00:34:38,699
hvorfor har vi denne hoved så godt?

447
00:34:38,699 --> 00:34:42,110
Giver det mening nu, Charlotte? >> Kind of.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Kind of? Så hvad der skete, da vi dequeued?

449
00:34:47,500 --> 00:34:54,340
Hvad gjorde hovedet gøre det nu er interessant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Åh, fordi det ændret - okay. Jeg er med.

451
00:34:56,449 --> 00:35:02,090
Fordi hovedet - hvor hovedet peger på ændringer med hensyn til placeringen.

452
00:35:02,090 --> 00:35:07,200
Det er ikke længere altid nul indeks én. >> Ja, præcis.

453
00:35:07,200 --> 00:35:17,660
Hvad der skete var, hvis dequeueing den høje element

454
00:35:17,660 --> 00:35:20,590
blev gjort, og vi havde ikke dette hoved felt

455
00:35:20,590 --> 00:35:26,880
fordi vi altid kaldte denne streng ved 0 indeks i spidsen for vores kø,

456
00:35:26,880 --> 00:35:30,170
så vi er nødt til at flytte resten af ​​køen ned.

457
00:35:30,170 --> 00:35:36,010
Vi er nødt til at flytte "bye" fra strings [1] til strings [0].

458
00:35:36,010 --> 00:35:38,760
Og strings [2] ned til strings [1].

459
00:35:38,760 --> 00:35:43,050
Og vi er nødt til at gøre det for hele listen af ​​elementer,

460
00:35:43,050 --> 00:35:45,110
hele systemet af elementer.

461
00:35:45,110 --> 00:35:50,490
Og når vi gør det med et array, der bliver virkelig dyrt.

462
00:35:50,490 --> 00:35:53,340
Så her, det er ikke en big deal. Vi har bare tre elementer i vores array.

463
00:35:53,340 --> 00:35:57,230
Men hvis vi havde en kø på tusind elementer eller en million elementer,

464
00:35:57,230 --> 00:36:00,060
og så lige pludselig, vi begynde at lave en masse dequeue kalder alle i en løkke,

465
00:36:00,060 --> 00:36:03,930
tingene virkelig kommer til at sætte farten ned, da det skifter alt ned konstant.

466
00:36:03,930 --> 00:36:07,320
Du ved, skifte med 1, skift med 1, skift med 1, skift af 1.

467
00:36:07,320 --> 00:36:13,650
I stedet skal vi bruge dette hoved, vi kalder det en "pointer", selvom det er egentlig ikke en pointer

468
00:36:13,650 --> 00:36:16,430
i egentlig forstand, det er ikke en pointer type.

469
00:36:16,430 --> 00:36:19,410
Det er ikke en int * eller en char * eller sådan noget.

470
00:36:19,410 --> 00:36:28,930
Men det peger eller angiver lederen af ​​vores kø. Ja?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Hvordan dequeue vide at bare pop off uanset er i spidsen?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hvordan dequeue vide, hvordan man pop off hvad er i spidsen? >> Right, ja.

473
00:36:43,620 --> 00:36:49,050
>> Hvad det er at se på, er bare hvad hovedet er indstillet til.

474
00:36:49,050 --> 00:36:52,710
Så i denne første sag, hvis vi ser lige her,

475
00:36:52,710 --> 00:36:55,690
vores hoved er 0, index 0. >> Højre.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Så det bare siger okay, godt, elementet ved indeks 0, strengen "hej",

477
00:37:00,500 --> 00:37:03,050
er det element i spidsen for vores kø.

478
00:37:03,050 --> 00:37:05,570
Så vi kommer til at dequeue den fyr.

479
00:37:05,570 --> 00:37:09,800
Og det vil være det element, der bliver returneret til den, der ringer.

480
00:37:09,800 --> 00:37:14,540
Ja, Saad? >> Så hovedet dybest set sætter - hvor du kommer til at indeksere det?

481
00:37:14,540 --> 00:37:17,750
Det er starten på det? >> Yeah. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Det er ved at blive den nye start for vores array.

483
00:37:22,900 --> 00:37:28,930
Så når du dequeue noget, alt hvad du skal gøre, er at få adgang til elementet ved indeks q.head,

484
00:37:28,930 --> 00:37:32,240
og det vil være det element, du vil dequeue.

485
00:37:32,240 --> 00:37:34,930
Du skal også formindske størrelsen.

486
00:37:34,930 --> 00:37:39,430
Vi vil se på en lidt hvor tingene bliver lidt tricky med dette.

487
00:37:39,430 --> 00:37:46,520
Vi dequeue, og nu, hvis vi sætte mellemlager igen,

488
00:37:46,520 --> 00:37:51,300
hvor skal vi sætte mellemlager?

489
00:37:51,300 --> 00:37:55,000
Hvor kommer det næste element gå i vores kø?

490
00:37:55,000 --> 00:37:57,980
Sige at vi vil sætte mellemlager strengen "CS".

491
00:37:57,980 --> 00:38:02,240
Into hvilken indeks vil det gå? [Studerende] 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 nu hovedet er 1, så det er ligesom starten af ​​listen?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Right. Og hvad betegner slutningen af ​​listen?

495
00:38:21,220 --> 00:38:23,290
Hvad vi bruger til at betegne afslutningen på vores kø?

496
00:38:23,290 --> 00:38:25,970
Hovedet er leder af vores kø, i begyndelsen af ​​vores kø.

497
00:38:25,970 --> 00:38:29,530
Hvad er afslutningen på vores kø? [Studerende] størrelse. >> Størrelse, præcis.

498
00:38:29,530 --> 00:38:36,360
Så vores nye elementer går ind på størrelse, og de elementer, som vi tager off komme ud på hovedet.

499
00:38:36,360 --> 00:38:45,390
Når vi sætte mellemlager det næste element, vi sætter det i stedet på størrelse.

500
00:38:45,390 --> 00:38:48,530
[Student] Før du lægger det i selv, størrelse var 1, right?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Right. Så ikke helt på størrelse. Size +, ikke +1, men + hoved.

502
00:38:55,690 --> 00:38:59,990
Fordi vi flyttet alt ved hoved beløb.

503
00:38:59,990 --> 00:39:14,270
Så her, nu har vi fået en kø af størrelse 1, der begynder ved indeks 1.

504
00:39:14,270 --> 00:39:20,730
Halen er indeks 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Hvad sker der, når du dequeue strings [0], og de strings 'slots i hukommelsen

506
00:39:25,780 --> 00:39:29,420
bare få tømt, dybest set, eller bare glemt?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. I den forstand er vi bare glemme dem.

508
00:39:34,700 --> 00:39:42,640
Hvis vi opbevare kopier af dem for -

509
00:39:42,640 --> 00:39:46,310
mange datastrukturer vil ofte gemme deres egne eksemplarer af de elementer,

510
00:39:46,310 --> 00:39:51,760
således at den person styre datastrukturen ikke behøver at bekymre

511
00:39:51,760 --> 00:39:53,650
om, hvor alle disse pegepinde går.

512
00:39:53,650 --> 00:39:56,000
Datastrukturen holder fast i alt, holder på alle de kopier,

513
00:39:56,000 --> 00:39:59,580
for at sikre, at alt fortsætter korrekt.

514
00:39:59,580 --> 00:40:03,140
Men i dette tilfælde disse datastrukturer kun for nemheds skyld,

515
00:40:03,140 --> 00:40:05,580
ikke lave kopier af noget, som vi opbevarer i dem.

516
00:40:05,580 --> 00:40:08,630
[Student] Så er dette en kontinuerlig række af -? >> Ja.

517
00:40:08,630 --> 00:40:14,350
Hvis vi ser tilbage på, hvad definitionen var af denne struktur, det er.

518
00:40:14,350 --> 00:40:19,110
Det er bare en standard array som du har set,

519
00:40:19,110 --> 00:40:24,280
et array af char * s.

520
00:40:24,280 --> 00:40:26,340
Betyder det -? >> Ja, jeg var bare undrende

521
00:40:26,340 --> 00:40:29,130
hvis du i sidste ende vil løbe tør for hukommelse, til en vis grad,

522
00:40:29,130 --> 00:40:32,330
hvis du har alle disse tomme pletter i dit array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, det er en god pointe.

524
00:40:36,390 --> 00:40:41,530
>> Hvis vi ser på hvad der er sket nu på dette tidspunkt,

525
00:40:41,530 --> 00:40:46,350
vi har fyldt op vores kø, det ligner.

526
00:40:46,350 --> 00:40:50,390
Men vi har ikke rigtig fyldt op vores kø

527
00:40:50,390 --> 00:40:57,710
fordi vi har en kø, der er str. 2, men det begynder ved indeks 1,

528
00:40:57,710 --> 00:41:02,160
fordi det er der vores hoved pointer er.

529
00:41:02,160 --> 00:41:08,400
Ligesom du sagde, at element i strings [0], ved indeks 0, ikke er der i virkeligheden.

530
00:41:08,400 --> 00:41:10,450
Det er ikke i vores kø længere.

531
00:41:10,450 --> 00:41:16,460
Vi vidste bare ikke gider at gå ind og overskrive det, når vi dequeued det.

532
00:41:16,460 --> 00:41:18,700
Så selvom det ser ud som om vi har kørt tør for hukommelse, vi virkelig ikke.

533
00:41:18,700 --> 00:41:23,270
Denne spot er tilgængelige for os at bruge.

534
00:41:23,270 --> 00:41:29,310
Den passende opførsel, hvis vi skulle forsøge og første dequeue noget

535
00:41:29,310 --> 00:41:34,420
gerne "bye", der ville pop bye off.

536
00:41:34,420 --> 00:41:38,460
Nu er vores kø begynder ved indeks 2 og er af størrelse 1.

537
00:41:38,460 --> 00:41:42,240
Og nu, hvis vi prøver og sætte mellemlager noget igen, siger 50,

538
00:41:42,240 --> 00:41:47,880
50 bør gå i denne plet ved indeks 0

539
00:41:47,880 --> 00:41:51,270
fordi det er stadig til rådighed for os. Ja, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Sker det automatisk?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Det sker ikke helt automatisk. Du er nødt til at gøre det math

542
00:41:56,150 --> 00:42:00,380
at gøre det arbejde, men væsentligt, hvad vi har gjort, er at vi lige har viklet rundt.

543
00:42:00,380 --> 00:42:04,070
[Saad] Og er det okay, hvis dette har et hul i midten af ​​det?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Det er, hvis vi kan gøre det math træne ordentligt.

545
00:42:08,720 --> 00:42:15,470
>> Og det viser sig, at det er faktisk ikke så svært at gøre med mod operatøren.

546
00:42:15,470 --> 00:42:20,040
Så ligesom vi gjorde med Cæsar og krypto stuff,

547
00:42:20,040 --> 00:42:25,190
hjælp mod, kan vi få tingene til at vikle rundt og holde i gang

548
00:42:25,190 --> 00:42:28,090
rundt og rundt og rundt med vores kø,

549
00:42:28,090 --> 00:42:32,180
holde det hoved pointer bevæge sig rundt.

550
00:42:32,180 --> 00:42:38,840
Bemærk, at størrelse er altid respektere antallet af elementer, der faktisk i køen.

551
00:42:38,840 --> 00:42:43,110
Og det er bare hovedet pointer, der holder cykle igennem.

552
00:42:43,110 --> 00:42:49,660
Hvis vi ser på, hvad der skete her, hvis vi går tilbage til begyndelsen,

553
00:42:49,660 --> 00:42:55,020
og du bare se hvad der sker til hovedet

554
00:42:55,020 --> 00:42:58,240
når vi sætte mellemlager noget, der skete ikke noget til hovedet.

555
00:42:58,240 --> 00:43:00,970
Når vi enqueued noget andet, der skete ikke noget til hovedet.

556
00:43:00,970 --> 00:43:04,130
Snart vi dequeued noget, hovedet går op for én.

557
00:43:04,130 --> 00:43:06,600
Vi enqueued noget, sker der ingenting til hovedet.

558
00:43:06,600 --> 00:43:11,060
Når vi dequeue noget, alle af en pludselig hovedet bliver øges.

559
00:43:11,060 --> 00:43:14,660
Når vi sætte mellemlager noget, sker der ingenting til hovedet.

560
00:43:14,660 --> 00:43:20,240
>> Hvad ville der ske på dette tidspunkt, hvis vi skulle dequeue noget igen?

561
00:43:20,240 --> 00:43:23,240
Nogen tanker? Hvad ville der ske med hovedet?

562
00:43:23,240 --> 00:43:27,190
Hvad skal der ske med hovedet

563
00:43:27,190 --> 00:43:32,990
hvis vi skulle dequeue noget andet?

564
00:43:32,990 --> 00:43:35,400
Hovedet lige nu ligger på indeks 2,

565
00:43:35,400 --> 00:43:38,920
hvilket betyder, at lederen af ​​køen er strings [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Hvilket returnerer 0? >> Det burde vende tilbage til 0. Det skal vikles tilbage omkring, nøjagtigt.

567
00:43:44,280 --> 00:43:48,440
Indtil videre hver gang vi kaldte dequeue, har vi været at tilføje en til hovedet,

568
00:43:48,440 --> 00:43:50,960
føje en til hovedet, tilsættes en til hovedet, tilsættes en til hovedet.

569
00:43:50,960 --> 00:43:58,400
Så snart det hoved pointer kommer til det sidste indeks i vores array,

570
00:43:58,400 --> 00:44:05,650
så er vi nødt til at pakke den tilbage omkring til begyndelsen, gå tilbage til 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Hvad bestemmer kapaciteten i køen i en stak?

572
00:44:09,900 --> 00:44:13,120
[Hardison] I dette tilfælde har vi lige brugt en # defineret konstant. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] I det faktiske. C. fil, kan du gå ind og rode med det lidt

574
00:44:19,590 --> 00:44:21,710
og gøre det så stor eller så lidt som du ønsker.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Så når du gør det til en kø, hvordan kan du gøre computeren vide

576
00:44:25,310 --> 00:44:29,120
hvor stor du vil have stakken for at være?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Det er et godt spørgsmål.

578
00:44:31,700 --> 00:44:34,800
Der er et par forskellige måder. Den ene er at bare definere det op foran

579
00:44:34,800 --> 00:44:42,050
og sige dette vil være en kø, der har 4 elementer eller 50 elementer eller 10.000.

580
00:44:42,050 --> 00:44:45,430
Den anden måde er at gøre, hvad de hacker udgave folk gør

581
00:44:45,430 --> 00:44:52,310
og skabe funktioner til at have din kø vokse dynamisk som flere ting bliver tilføjet i.

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Så for at gå med den første mulighed, hvad syntaks du bruger

583
00:44:54,740 --> 00:44:57,830
at fortælle programmet hvad er størrelsen af ​​køen?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Så lad os komme ud af dette.

585
00:45:04,780 --> 00:45:12,650
Jeg er stadig i stack.c her, så jeg vil bare at rulle op til toppen her.

586
00:45:12,650 --> 00:45:17,920
Kan du se denne her? Dette er den # define kapacitet 10.

587
00:45:17,920 --> 00:45:24,600
Og det er næsten nøjagtig samme syntaks, som vi har til kø.

588
00:45:24,600 --> 00:45:28,390
Undtagen i kø, så har vi det ekstra struct felt i her.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Åh, jeg troede den kapacitet betød evnen til strengen.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> At det er den maksimale længde af ordet. >> Fik det.

591
00:45:36,770 --> 00:45:41,180
Yeah. Kapaciteten her - det er en stor punkt.

592
00:45:41,180 --> 00:45:44,000
Og det er noget, der er tricky

593
00:45:44,000 --> 00:45:49,480
fordi det, vi har erklæret her er et array af char * s.

594
00:45:49,480 --> 00:45:52,770
En vifte af pegepinde.

595
00:45:52,770 --> 00:45:56,690
Dette er et array af tegn.

596
00:45:56,690 --> 00:46:01,690
Det er sandsynligvis, hvad du har set, når du har været at erklære dine buffere for fil I / O,

597
00:46:01,690 --> 00:46:06,840
når du har været at skabe strenge manuelt på stakken.

598
00:46:06,840 --> 00:46:09,090
Men det, vi har her, er en vifte af char * s.

599
00:46:09,090 --> 00:46:13,400
Så det er en vifte af pegepinde.

600
00:46:13,400 --> 00:46:18,350
Faktisk, hvis vi zoome ud igen, og vi ser på, hvad der sker her

601
00:46:18,350 --> 00:46:23,140
i præsentationen, kan du se, at den faktiske elementer, karakter data

602
00:46:23,140 --> 00:46:26,180
bliver ikke gemt i arrayet selv.

603
00:46:26,180 --> 00:46:42,690
Hvad er lagret i vores array her er henvisninger til de tegndata.

604
00:46:42,690 --> 00:46:52,560
Okay. Så vi har set, hvordan størrelsen af ​​køen er ligesom med stakken,

605
00:46:52,560 --> 00:46:58,670
størrelsen altid overholder antallet af elementer, der i øjeblikket er i køen.

606
00:46:58,670 --> 00:47:02,720
Efter at gøre 2 enqueues, er størrelsen 2.

607
00:47:02,720 --> 00:47:07,110
Efter at have foretaget en dequeue størrelsen er nu 1.

608
00:47:07,110 --> 00:47:09,330
Når du har foretaget en anden enqueue størrelsen er tilbage op til 2.

609
00:47:09,330 --> 00:47:12,340
Så den størrelse afgjort overholder antallet af elementer i køen,

610
00:47:12,340 --> 00:47:15,580
og derefter hovedet bare holder cykling.

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 kalder dequeue, bliver hovedet pointer inkrementeres til næste indeks.

613
00:47:25,620 --> 00:47:29,930
Og hvis hovedet er ved at gå over, det sløjfer tilbage omkring til 0.

614
00:47:29,930 --> 00:47:34,870
Så med det, kan vi skrive det dequeue funktion.

615
00:47:34,870 --> 00:47:40,200
Og vi vil forlade enqueue funktion for jer at gennemføre i stedet.

616
00:47:40,200 --> 00:47:45,880
>> Når vi dequeue et element ud af vores kø,

617
00:47:45,880 --> 00:47:55,490
hvad var den første ting, Daniel gjorde, da vi startede med at skrive pop funktion for stakke?

618
00:47:55,490 --> 00:48:00,490
Lad mig høre fra nogen, der ikke har talt endnu.

619
00:48:00,490 --> 00:48:06,710
Lad os se, Saad, kan du huske, hvad Daniel gjorde som den første ting, da han skrev pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Der var, var det - >> Han testet for noget.

621
00:48:08,860 --> 00:48:12,140
[Saad] Hvis størrelsen er større end 0. >> Præcis.

622
00:48:12,140 --> 00:48:14,390
Og hvad var det testning for?

623
00:48:14,390 --> 00:48:19,090
[Saad] Det var test for at se om der er noget inde i array.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Præcis. Så du kan ikke pop noget ud af stablen, hvis den er tom.

625
00:48:23,210 --> 00:48:26,510
På samme måde kan du ikke dequeue noget fra en kø, hvis den er tom.

626
00:48:26,510 --> 00:48:30,420
Hvad er det første, vi skal gøre i vores dequeue funktion her, tror du?

627
00:48:30,420 --> 00:48:33,860
[Saad] Hvis størrelsen er større end 0? >> Yeah.

628
00:48:33,860 --> 00:48:37,710
I dette tilfælde har jeg faktisk lige prøvet at se om det er 0.

629
00:48:37,710 --> 00:48:42,240
Hvis det er 0, kan vi vende tilbage null.

630
00:48:42,240 --> 00:48:45,280
Men nøjagtig samme logik.

631
00:48:45,280 --> 00:48:49,110
Og lad os fortsætte med dette.

632
00:48:49,110 --> 00:48:54,600
Hvis størrelsen ikke er 0, hvor er det element, vi ønsker at dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] På hovedet? >> Præcis.

634
00:48:58,550 --> 00:49:01,720
Vi kan bare trække sig ud det første element i vores kø

635
00:49:01,720 --> 00:49:07,040
ved at åbne elementet i spidsen.

636
00:49:07,040 --> 00:49:14,630
Intet crazy.

637
00:49:14,630 --> 00:49:19,620
Efter dette, hvad skal vi gøre? Hvad skal der ske?

638
00:49:19,620 --> 00:49:23,740
Hvad var den anden ting, som vi talte om i dequeue?

639
00:49:23,740 --> 00:49:28,130
To ting er nødt til at ske, fordi vores kø er ændret.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reducer størrelsen. >> Vi er nødt til at reducere størrelsen og øge hovedet? Præcis.

641
00:49:35,640 --> 00:49:40,600
For at øge hovedet, kan vi ikke bare blindt at øge hovedet, husk det.

642
00:49:40,600 --> 00:49:45,080
Vi kan ikke bare gøre queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Vi er nødt til også at omfatte denne mod af kapaciteten.

644
00:49:51,630 --> 00:49:54,740
Og hvorfor har vi at moder af kapaciteten, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Fordi det har at vikle rundt. >> Præcis.

646
00:49:58,680 --> 00:50:04,750
Vi mod den kapacitet, fordi det skal vikles tilbage omkring til 0.

647
00:50:04,750 --> 00:50:07,400
Så nu, på dette tidspunkt, kan vi gøre det, sagde Daniel.

648
00:50:07,400 --> 00:50:12,700
Vi kan formindske størrelsen.

649
00:50:12,700 --> 00:50:29,170
Og så kan vi bare returnere det element, der var på toppen af ​​køen.

650
00:50:29,170 --> 00:50:34,000
Det ser lidt gnarly i første omgang. Du har måske et spørgsmål. Undskyld?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Hvorfor er først på toppen af ​​køen? Hvor går det hen?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Det kommer fra den fjerde linje fra bunden.

653
00:50:42,480 --> 00:50:46,060
Efter at vi tester for at sikre, at vores køen ikke er tom,

654
00:50:46,060 --> 00:50:54,100
vi trække sig ud char * først, vi trække det element, der sidder i spidsen indeks

655
00:50:54,100 --> 00:50:58,680
af vores array, af vores strings array, >> og opkald, først?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Og vi kalder det først. Yeah.

657
00:51:04,500 --> 00:51:09,850
Blot for at følge op på det, hvorfor du mener, at vi var nødt til at gøre det?

658
00:51:09,850 --> 00:51:18,270
[Sam] Hver første er bare tilbage q.strings [q.head]? >> Yeah.

659
00:51:18,270 --> 00:51:23,830
>> Fordi vi laver denne forandring af q.head med MOD-funktionen,

660
00:51:23,830 --> 00:51:27,810
og der er ingen måde at gøre det inden for returledningen også.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Præcis. Du er staffagefarve på. Sams helt staffagefarve på.

662
00:51:31,640 --> 00:51:36,800
Årsagen til at vi var nødt til at trække sig ud det første element i vores kø og gemme det i en variabel

663
00:51:36,800 --> 00:51:43,030
er fordi denne linje, hvor vi lige havde q.head,

664
00:51:43,030 --> 00:51:47,030
der er den mod operatøren der er ikke noget, vi kan gøre

665
00:51:47,030 --> 00:51:51,230
og har det virkning på hovedet uden - på én linje.

666
00:51:51,230 --> 00:51:54,480
Så vi faktisk nødt til at trække sig ud det første element, og derefter justere hovedet,

667
00:51:54,480 --> 00:52:00,430
justere størrelsen, og derefter returnere elementet, som vi trækkes ud.

668
00:52:00,430 --> 00:52:02,680
Og det er noget, vi vil se komme op senere med

669
00:52:02,680 --> 00:52:04,920
hægtede lister, som vi lege med dem.

670
00:52:04,920 --> 00:52:08,410
Ofte når du frigøre eller bortskaffelse af hægtede lister

671
00:52:08,410 --> 00:52:13,500
du skal huske det næste element, den næste pointer af en linket liste

672
00:52:13,500 --> 00:52:16,330
før bortskaffelse af den nuværende.

673
00:52:16,330 --> 00:52:23,580
Fordi ellers du smider de oplysninger af hvad der er tilbage på listen.

674
00:52:23,580 --> 00:52:34,160
Nu, hvis du går til dit apparat, du åbner op queue.c--x ud af dette.

675
00:52:34,160 --> 00:52:39,390
Så hvis jeg åbner queue.c, lad mig zoome ind her,

676
00:52:39,390 --> 00:52:44,970
vil du se, at du har et lignende udseende fil.

677
00:52:44,970 --> 00:52:49,200
Tilsvarende udseende fil til, hvad vi havde tidligere med stack.c.

678
00:52:49,200 --> 00:52:54,690
Vi har fået vores struct for kø defineret ligesom vi så på dias.

679
00:52:54,690 --> 00:52:59,870
>> Vi har vores enqueue funktion, som er for dig at gøre.

680
00:52:59,870 --> 00:53:04,340
Og vi har den dequeue funktion her.

681
00:53:04,340 --> 00:53:06,870
Den dequeue funktion i filen ikke er blevet gennemført,

682
00:53:06,870 --> 00:53:13,230
men jeg vil sætte den op igen på den PowerPoint, så du kan skrive det i, hvis du vil have.

683
00:53:13,230 --> 00:53:16,690
Så for de næste 5 minutter eller deromkring, arbejde gutter på enqueue

684
00:53:16,690 --> 00:53:22,570
som er næsten lige det modsatte af dequeue.

685
00:53:22,570 --> 00:53:29,560
Du behøver ikke at justere hoved, når du enqueueing, men hvad har du at justere?

686
00:53:29,560 --> 00:53:38,920
Størrelse. Så når du enqueue, hovedet forbliver uberørt, bliver størrelsen ændret.

687
00:53:38,920 --> 00:53:46,920
Men det tager en lille smule af - du bliver nødt til at lege med det mod

688
00:53:46,920 --> 00:53:57,560
at finde ud af præcis, hvad indeks Det nye element skal indsættes på.

689
00:53:57,560 --> 00:54:03,080
Så jeg vil give jer en lille smule, sætte dequeue tilbage op på diasset,

690
00:54:03,080 --> 00:54:05,200
Og som du fyre har spørgsmål, råbe dem ud, så vi kan

691
00:54:05,200 --> 00:54:09,220
taler alle om dem som en gruppe.

692
00:54:09,220 --> 00:54:13,960
Også med den størrelse, du lad være - når du justere størrelsen, kan du altid bare -

693
00:54:13,960 --> 00:54:18,720
har du at mod den størrelse nogensinde? [Daniel] Nej >> Du behøver ikke at mod den størrelse, højre.

694
00:54:18,720 --> 00:54:24,260
Fordi størrelse altid vil, hvis Du er - forudsat du administrerer tingene korrekt,

695
00:54:24,260 --> 00:54:30,840
størrelsen vil altid være mellem 0 og 3.

696
00:54:30,840 --> 00:54:38,680
Hvor har du at mod, når du laver enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Kun for hovedet. >> Kun for hovedet, præcis.

698
00:54:41,060 --> 00:54:44,620
Og hvorfor har du at mod overhovedet i enqueue?

699
00:54:44,620 --> 00:54:48,830
Hvornår er en situation, hvor du er nødt til mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Hvis du har ting på plads, gerne på rum 1 og 2,

701
00:54:53,630 --> 00:54:55,950
og derefter du behov for at tilføje noget til 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ja, præcis. Så hvis dit hoved pointer er til allersidst,

703
00:55:02,570 --> 00:55:14,210
eller hvis din størrelse plus dit hoved er større, eller rettere, vil ombryde omkring køen.

704
00:55:14,210 --> 00:55:17,830
>> Så i denne situation, at vi har fået op her på objektglasset lige nu,

705
00:55:17,830 --> 00:55:24,370
hvis jeg ønsker at sætte mellemlager noget lige nu,

706
00:55:24,370 --> 00:55:31,110
vi ønsker at sætte mellemlager noget ved indeks 0.

707
00:55:31,110 --> 00:55:35,450
Så hvis man ser på hvor de 50 går, og jeg kalder enqueue 50,

708
00:55:35,450 --> 00:55:40,840
den går ned der i bunden. Det går i indeks 0.

709
00:55:40,840 --> 00:55:44,160
Den erstatter den "hi", der allerede var dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Kan du ikke tage dig af det i dequeue allerede?

711
00:55:46,210 --> 00:55:50,550
Hvorfor gør den noget med hovedet i enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Åh, så du ikke ændrer hovedet, undskyld.

713
00:55:55,770 --> 00:56:02,310
Men du er nødt til at bruge mod operatøren, når du får adgang til

714
00:56:02,310 --> 00:56:04,250
det element, du ønsker at sætte mellemlager når du får adgang til

715
00:56:04,250 --> 00:56:06,960
det næste element i din kø.

716
00:56:06,960 --> 00:56:10,960
[Basil] jeg ikke gøre det, og jeg fik "succes" på der.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Åh, jeg forstår, hvad du siger.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Så du didn't - du bare gjorde q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Jeg har lige skiftet side, havde jeg ikke gøre noget med hovedet.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Du behøver faktisk ikke at nulstille hovedet at være noget,

721
00:56:24,300 --> 00:56:31,650
men når du indekset i strengene array,

722
00:56:31,650 --> 00:56:39,500
du rent faktisk nødt til at gå videre og beregne, hvor den næste element er,

723
00:56:39,500 --> 00:56:44,230
fordi komitéens stakken, det næste element i din stack var altid

724
00:56:44,230 --> 00:56:48,740
ved indekset svarende til størrelsen.

725
00:56:48,740 --> 00:56:55,850
Hvis vi ser tilbage på vores stack push-funktion,

726
00:56:55,850 --> 00:57:03,100
Vi kunne altid knipse i vores nye element til højre på indeks størrelse.

727
00:57:03,100 --> 00:57:06,710
Betragtninger med køen, kan vi ikke gøre det

728
00:57:06,710 --> 00:57:10,340
fordi hvis vi er i denne situation,

729
00:57:10,340 --> 00:57:18,130
hvis vi enqueued 50 vores nye streng ville gå til højre ved strings [1]

730
00:57:18,130 --> 00:57:20,540
som vi ikke ønsker at gøre.

731
00:57:20,540 --> 00:57:41,200
Vi ønsker at have den nye streng gå på indeks 0.

732
00:57:41,200 --> 00:57:44,320
>> Er der nogen - ja? [Student] Jeg har et spørgsmål, men det er egentlig ikke relateret.

733
00:57:44,320 --> 00:57:48,160
Hvad betyder det, når nogen bare kalder noget PRED pointer?

734
00:57:48,160 --> 00:57:51,260
Hvad er det navn en forkortelse af? Jeg ved, det er bare et navn.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pointer? Lad os se. I hvilken sammenhæng?

736
00:57:59,110 --> 00:58:01,790
[Student] Det var for indsatsen. Jeg kan spørge dig senere, hvis du ønsker

737
00:58:01,790 --> 00:58:03,920
fordi det ikke er virkelig relateret, men jeg bare -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Fra Davids insert kode fra foredrag?

739
00:58:07,300 --> 00:58:10,860
Vi kan trække det op og tale om det.

740
00:58:10,860 --> 00:58:15,550
Vi taler om det næste, når vi kommer til hægtede lister.

741
00:58:15,550 --> 00:58:21,440
>> Så lad os virkelig hurtigt se på, hvad det enqueue funktionen ser ud.

742
00:58:21,440 --> 00:58:26,530
Hvad var den første ting, folk har forsøgt at gøre i din enqueue linje? Ind i denne kø?

743
00:58:26,530 --> 00:58:29,960
Svarende til, hvad du gjorde for stakken skubbe.

744
00:58:29,960 --> 00:58:32,080
Hvad 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] Præcis. Hvis (q.size == KAPACITET) -

747
00:58:45,700 --> 00:58:54,720
Jeg har brug for at sætte mine seler på rette sted - returnere falsk.

748
00:58:54,720 --> 00:59:01,370
Zoom ind en lille smule. Okay.

749
00:59:01,370 --> 00:59:03,800
Nu hvad er det næste, at vi skulle gøre?

750
00:59:03,800 --> 00:59:11,370
Ligesom med stakken, og indsat på det rigtige sted.

751
00:59:11,370 --> 00:59:16,010
Og så hvad var det rigtige sted at indsætte det?

752
00:59:16,010 --> 00:59:23,170
Med stakken var det indeks 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? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod KAPACITET]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Vi sandsynligvis ønsker at sætte parentes omkring dette

756
00:59:42,740 --> 00:59:48,830
så vi får den rette forrang og så det er cleart for alle.

757
00:59:48,830 --> 00:59:55,800
Og sæt, lige? >> Til str? >> Til str. Great.

758
00:59:55,800 --> 01:00:00,160
Og nu, hvad er det sidste, vi skal gøre?

759
01:00:00,160 --> 01:00:06,780
Ligesom vi gjorde i stakken. >> Forøg størrelsen? >> Forøg størrelsen.

760
01:00:06,780 --> 01:00:13,830
Boom. Og så, da starteren kode netop vendt tilbage falsk som standard,

761
01:00:13,830 --> 01:00:27,460
Vi ønsker at ændre dette til sand hvis alt går igennem og alt går godt.

762
01:00:27,460 --> 01:00:33,050
Ok. Det er en masse information om sektion.

763
01:00:33,050 --> 01:00:39,480
Vi er ikke helt over. Vi ønsker at tale virkelig hurtigt om enkeltvis-hægtede lister.

764
01:00:39,480 --> 01:00:44,010
Jeg vil sætte dette op, så vi kan gå tilbage til det senere.

765
01:00:44,010 --> 01:00:50,850
Men lad os gå tilbage til vores præsentation for blot et par flere dias.

766
01:00:50,850 --> 01:00:53,790
Så enqueue er TODO, nu vi har gjort det.

767
01:00:53,790 --> 01:00:57,430
>> Lad os nu tage et kig på enkeltvis-hægtede lister.

768
01:00:57,430 --> 01:01:00,040
Vi talte om disse lidt mere i foredrag.

769
01:01:00,040 --> 01:01:02,540
Hvor mange af jer så demo, hvor vi havde folk

770
01:01:02,540 --> 01:01:08,220
akavet peger på hinanden og bedriften numre? >> Jeg var i det.

771
01:01:08,220 --> 01:01:16,620
>> Hvad gjorde du fyre tror? Gjorde det, forhåbentlig afmystificere disse en lille smule?

772
01:01:16,620 --> 01:01:25,990
Med en liste, viser det sig, at vi beskæftiger os med denne type, som vi kommer til at kalde en node.

773
01:01:25,990 --> 01:01:32,520
Betragtninger med køen og stakken vi havde struct, at vi ville kalde kø i stakken,

774
01:01:32,520 --> 01:01:34,860
Vi havde disse nye kø i stack typer,

775
01:01:34,860 --> 01:01:39,240
her en liste egentlig bare består af en flok noder.

776
01:01:39,240 --> 01:01:45,920
På samme måde som strenge er bare en masse chars alle linet op ved siden af ​​hinanden.

777
01:01:45,920 --> 01:01:50,650
En linket liste er bare en knude og en anden node og en anden node og en anden node.

778
01:01:50,650 --> 01:01:55,080
Og i stedet for at smadre alle de noder sammen og lagre dem tilstødende

779
01:01:55,080 --> 01:01:58,090
alt lige ved siden af ​​hinanden i hukommelsen,

780
01:01:58,090 --> 01:02:04,470
har denne næste pointer giver os mulighed for at gemme noder i alle tilfælde, tilfældigt.

781
01:02:04,470 --> 01:02:10,500
Og derefter slags tråd dem sammen til punkt fra den ene til den næste.

782
01:02:10,500 --> 01:02:15,850
>> Og hvad var den store fordel, at det havde over et array?

783
01:02:15,850 --> 01:02:21,680
Over lagring alt tilstødende bare fast ved siden af ​​hinanden?

784
01:02:21,680 --> 01:02:24,190
Kan du huske? Ja? >> Dynamisk allokering af hukommelse?

785
01:02:24,190 --> 01:02:27,220
>> Dynamisk allokering af hukommelse i hvilken forstand?

786
01:02:27,220 --> 01:02:31,780
[Student] I, at du kan holde gøre det større og du behøver ikke at flytte hele din array?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Præcis. Så med et array, når du ønsker at sætte et nyt element ind i midten af ​​det

788
01:02:40,940 --> 01:02:45,320
du nødt til at flytte alt for at gøre plads.

789
01:02:45,320 --> 01:02:47,880
Og ligesom vi talte om med køen,

790
01:02:47,880 --> 01:02:50,080
det er derfor vi holder det hoved pointer,

791
01:02:50,080 --> 01:02:52,050
så vi ikke konstant skiftende ting.

792
01:02:52,050 --> 01:02:54,520
Fordi det bliver dyrt, hvis du har en stor vifte

793
01:02:54,520 --> 01:02:57,130
og du er konstant gør disse tilfældige indrykninger.

794
01:02:57,130 --> 01:03:00,820
Betragtninger med en liste, er alt du skal gøre smide det på en ny node,

795
01:03:00,820 --> 01:03:06,330
justere pegepinde, og du er færdig.

796
01:03:06,330 --> 01:03:10,940
Hvad stinker om dette?

797
01:03:10,940 --> 01:03:16,830
Bortset fra det faktum, at det ikke er så let at arbejde med som en matrix? Ja?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Nå, jeg tror det er meget sværere at få adgang til et bestemt element i den linkede liste?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Du kan ikke bare hoppe til en vilkårlig element i midten af ​​din linkede liste.

800
01:03:30,470 --> 01:03:33,800
Hvordan du skal gøre det i stedet? >> Du er nødt til at gå gennem hele ting.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. De skal igennem en ad gangen, en ad gangen.

802
01:03:35,660 --> 01:03:38,480
Det er en enorm - det er en smerte.

803
01:03:38,480 --> 01:03:41,550
Hvad er den anden - der er en anden undergang til dette.

804
01:03:41,550 --> 01:03:45,340
[Basil] Du kan ikke gå frem og tilbage? Du er nødt til at gå én retning?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Så hvordan løser vi det nogle gange?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dobbelt-bundet lister? >> Præcis. Der er dobbelt-hægtede lister.

807
01:03:53,370 --> 01:03:55,540
Der er også - undskyld?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Er det det samme som at bruge PRED ting, -

809
01:03:57,620 --> 01:04:01,090
Jeg kom lige i tanke, er det ikke hvad det PRED ting er?

810
01:04:01,090 --> 01:04:05,850
Er det ikke i mellem dobbelt og enkeltvis?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Lad os se på, hvad han gjorde.

812
01:04:10,020 --> 01:04:15,760
Så her går vi. Her er listen kode.

813
01:04:15,760 --> 01:04:25,620
Her har vi predptr, herinde. Er det hvad du talte om?

814
01:04:25,620 --> 01:04:30,750
Så det var - han befri en liste, og han forsøger at gemme en pegepind til det.

815
01:04:30,750 --> 01:04:35,000
Dette er ikke den dobbelt, enkeltvis forbundet-lister.

816
01:04:35,000 --> 01:04:40,090
Vi kan tale mere om dette senere, da dette taler om frigørelse af listen

817
01:04:40,090 --> 01:04:42,900
og jeg vil gerne vise nogle andre ting først.

818
01:04:42,900 --> 01:04:51,480
men det er bare - det er at huske værdien af ​​PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Åh, det er foregående pointer? >> Yeah.

820
01:04:54,170 --> 01:05:04,070
For at vi kan derefter inkrementere ptr selv, før vi så fri, hvad predptr er.

821
01:05:04,070 --> 01:05:09,130
Fordi vi ikke kan gratis ptr og derefter kalde ptr = PTR næste, right?

822
01:05:09,130 --> 01:05:11,260
Det ville være skidt.

823
01:05:11,260 --> 01:05:20,940
Så lad os se, tilbage til denne fyr.

824
01:05:20,940 --> 01:05:23,900
>> Den anden dårlige ting om lister er, at mens med et array

825
01:05:23,900 --> 01:05:26,520
vi netop har alle de elementer, selv stablede siden af ​​hinanden,

826
01:05:26,520 --> 01:05:29,050
her har vi også indført denne pointer.

827
01:05:29,050 --> 01:05:34,060
Så der er en ekstra bid af hukommelse, som vi skulle bruge

828
01:05:34,060 --> 01:05:37,910
for ethvert element, at vi lagring i vores 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 leveres med denne gang omkostninger,

831
01:05:42,230 --> 01:05:45,270
og det kommer med denne hukommelse omkostning også.

832
01:05:45,270 --> 01:05:47,800
Tiden i den forstand, at vi nu er nødt til at gå gennem hvert element i arrayet

833
01:05:47,800 --> 01:05:58,670
at finde en på indeks 10, eller som ville have været indeks 10 i et array.

834
01:05:58,670 --> 01:06:01,230
>> Bare virkelig hurtigt, når vi diagram af disse lister,

835
01:06:01,230 --> 01:06:05,980
vi typisk holde på hovedet af listen eller den første pointer af listen

836
01:06:05,980 --> 01:06:08,010
og bemærk at dette er en sand pointer.

837
01:06:08,010 --> 01:06:11,100
Det er kun 4 bytes. Det er ikke en egentlig knude selv.

838
01:06:11,100 --> 01:06:17,120
Så du se, at det ikke har nogen int værdi i det, ingen næste pointer i det.

839
01:06:17,120 --> 01:06:20,790
Det er bogstaveligt talt bare en pegepind.

840
01:06:20,790 --> 01:06:23,550
Det kommer til at pege på noget, som er et virkeligt knudepunkt struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] En pegepind kaldet node? >> Dette er - nej. Dette er en pointer til noget af typen node.

842
01:06:28,480 --> 01:06:32,540
Det er en pointer til en knude struct. >> Åh, okay.

843
01:06:32,540 --> 01:06:36,870
Diagrammet til venstre, kode til højre.

844
01:06:36,870 --> 01:06:42,190
Vi kan indstille den til null, der er en god måde at starte.

845
01:06:42,190 --> 01:06:49,850
Når du diagram det, du enten skrive det som null eller hvis du lægger en linje gennem det på den måde.

846
01:06:49,850 --> 01:06:53,910
>> En af de nemmeste måder at arbejde med lister

847
01:06:53,910 --> 01:06:57,430
og vi beder jer ikke både prepend og tilføje at se forskellene mellem de to,

848
01:06:57,430 --> 01:07:01,320
men forudstille er absolut nemmere.

849
01:07:01,320 --> 01:07:05,790
Når du tilføjes i begyndelsen, det er her du - når du prepend (7),

850
01:07:05,790 --> 01:07:10,050
du går og skabe node struct

851
01:07:10,050 --> 01:07:13,870
og du først indstilles til at pege på det, fordi nu, da vi foranstillet det,

852
01:07:13,870 --> 01:07:17,240
det vil være i begyndelsen af ​​listen.

853
01:07:17,240 --> 01:07:22,540
Hvis vi prepend (3), der skaber en anden node, men nu 3 kommer før 7.

854
01:07:22,540 --> 01:07:31,130
Så vi er væsentligt at skubbe tingene på vores liste.

855
01:07:31,130 --> 01:07:34,720
Nu kan du se, at prepend, nogle gange folk kalder det skubbe,

856
01:07:34,720 --> 01:07:39,600
fordi du presser et nyt element på din liste.

857
01:07:39,600 --> 01:07:43,270
Det er også nemt at slette på forsiden af ​​en liste.

858
01:07:43,270 --> 01:07:45,650
Så folk vil ofte kalde det pop.

859
01:07:45,650 --> 01:07:52,200
Og på den måde, kan du emulere en stak ved hjælp af en sammenkædet liste.

860
01:07:52,200 --> 01:07:57,880
Ups. Beklager, nu skal vi komme ind append. Så her er vi foranstillet (7), nu vi prepend (3).

861
01:07:57,880 --> 01:08:02,600
Hvis vi foranstillet noget andet på denne liste, hvis vi foranstillet (4),

862
01:08:02,600 --> 01:08:06,540
så ville vi have 4 og derefter 3 og derefter 7.

863
01:08:06,540 --> 01:08:14,220
Så vi kunne pop og fjerne 4, fjern 3, fjerne 7.

864
01:08:14,220 --> 01:08:16,500
Ofte mere intuitiv måde at tænke om dette er med append.

865
01:08:16,500 --> 01:08:20,310
Så jeg har diagrammet ud af, hvad det ville se ud med vedhæfte her.

866
01:08:20,310 --> 01:08:23,380
Her vedlagt (7), ikke ser noget anderledes

867
01:08:23,380 --> 01:08:25,160
fordi der kun er ét element i listen.

868
01:08:25,160 --> 01:08:28,620
Og tilføje (3) stiller den til ende.

869
01:08:28,620 --> 01:08:31,020
Måske du kan se lige nu trick med append

870
01:08:31,020 --> 01:08:36,600
er, at da vi kun ved, hvor starten af ​​listen er,

871
01:08:36,600 --> 01:08:39,450
skal føjes til en liste, du er nødt til at gå hele vejen gennem listen

872
01:08:39,450 --> 01:08:46,500
at komme til ende, stoppe, og derefter bygge dit node og klimpre alt ned.

873
01:08:46,500 --> 01:08:50,590
Tilslut alle de ting op.

874
01:08:50,590 --> 01:08:55,170
Så med prepend, som vi netop har rippet gennem dette virkelig hurtigt,

875
01:08:55,170 --> 01:08:58,170
når du tilføjes i begyndelsen af ​​en liste, er det forholdsvis enkelt.

876
01:08:58,170 --> 01:09:02,960
>> Du laver din nye node, inddrage nogle dynamisk allokering af hukommelse.

877
01:09:02,960 --> 01:09:09,830
Så her vi laver en node struct med malloc.

878
01:09:09,830 --> 01:09:14,710
Så malloc vi bruger, fordi der vil afsætte hukommelse for os for senere

879
01:09:14,710 --> 01:09:20,350
fordi vi ikke ønsker dette - vi ønsker denne hukommelse til at vare ved i lang tid.

880
01:09:20,350 --> 01:09:25,350
Og vi får en pointer til den plads i hukommelsen, som vi netop tildelt.

881
01:09:25,350 --> 01:09:29,260
Vi bruger størrelse knude, vi ikke summere felterne.

882
01:09:29,260 --> 01:09:31,899
Vi ikke manuelt genererer antallet af bytes,

883
01:09:31,899 --> 01:09:39,750
i stedet bruger vi sizeof, så vi ved, at vi får et passende antal bytes.

884
01:09:39,750 --> 01:09:43,660
Vi sørger for at teste, at vores malloc opkald lykkedes.

885
01:09:43,660 --> 01:09:47,939
Dette er noget du ønsker at gøre i almindelighed.

886
01:09:47,939 --> 01:09:52,590
På moderne maskiner, er ved at løbe tør for hukommelse ikke noget, der er let

887
01:09:52,590 --> 01:09:56,610
medmindre du afsætte et væld af ting og gøre en enorm liste,

888
01:09:56,610 --> 01:10:02,220
men hvis du bygger ting for, siger, som en iPhone eller en Android,

889
01:10:02,220 --> 01:10:05,230
du har begrænset hukommelse ressourcer, især hvis du laver noget intens.

890
01:10:05,230 --> 01:10:08,300
Så det er godt at få i praksis.

891
01:10:08,300 --> 01:10:10,510
>> Bemærk, at jeg har brugt et par forskellige funktioner her

892
01:10:10,510 --> 01:10:12,880
at du har set den er lidt nyt.

893
01:10:12,880 --> 01:10:15,870
Så fprintf er ligesom printf

894
01:10:15,870 --> 01:10:21,320
undtagen det første argument er den strøm, som du ønsker at udskrive.

895
01:10:21,320 --> 01:10:23,900
I dette tilfælde vil vi udskrive til den standard fejlstreng

896
01:10:23,900 --> 01:10:29,410
som er forskellig fra den normale outstream.

897
01:10:29,410 --> 01:10:31,620
Som standard er det dukker op på samme sted.

898
01:10:31,620 --> 01:10:34,600
Det udskriver også ud til terminalen, men du kan -

899
01:10:34,600 --> 01:10:38,790
bruge disse kommandoer, du har lært om de omdirigering teknikker

900
01:10:38,790 --> 01:10:42,290
du lærte om i Tommys video til problemer set 4, kan du rette den

901
01:10:42,290 --> 01:10:47,900
til forskellige områder, og afslut, lige her, afslutter dit program.

902
01:10:47,900 --> 01:10:50,440
Det er essentielt som vender hjem fra main,

903
01:10:50,440 --> 01:10:53,600
medmindre vi bruge exit fordi her afkast ikke vil gøre noget.

904
01:10:53,600 --> 01:10:57,140
Vi er ikke i main, er så returnere ikke afslutte programmet som vi selv ønsker.

905
01:10:57,140 --> 01:11:03,020
Så vi bruger exit funktion og give det en fejlkode.

906
01:11:03,020 --> 01:11:11,890
Så her har vi sat den nye node værdi felt, dets Jeg feltet at være lig med i, og så må vi wire det op.

907
01:11:11,890 --> 01:11:15,530
Vi sætter det nye knudepunkt næste pointer til at pege på først,

908
01:11:15,530 --> 01:11:20,460
og derefter først vil nu pege på den nye node.

909
01:11:20,460 --> 01:11:25,120
Disse første linjer kode, er vi faktisk at bygge den nye node.

910
01:11:25,120 --> 01:11:27,280
Ikke de to sidste linjer i denne funktion, men de første.

911
01:11:27,280 --> 01:11:30,290
Man kan faktisk trækkes ud i en funktion, til en hjælpefunktion.

912
01:11:30,290 --> 01:11:32,560
Det er ofte det, jeg gør, er, jeg trækker det ud i en funktion,

913
01:11:32,560 --> 01:11:36,040
Jeg kalder det noget som build node,

914
01:11:36,040 --> 01:11:40,410
og som holder prepend funktionen temmelig lille, det er kun 3 linier dengang.

915
01:11:40,410 --> 01:11:48,710
Jeg vil foretage et opkald til min build node-funktionen, og så kan jeg wire alting op.

916
01:11:48,710 --> 01:11:51,970
>> Den sidste ting jeg vil vise dig,

917
01:11:51,970 --> 01:11:54,030
og jeg vil lade dig gøre append og alt det på egen hånd,

918
01:11:54,030 --> 01:11:57,500
er, hvordan man gentage over en liste.

919
01:11:57,500 --> 01:12:00,780
Der er en masse forskellige måder at gentage over en liste.

920
01:12:00,780 --> 01:12:03,140
I dette tilfælde vil vi finde længden af ​​en liste.

921
01:12:03,140 --> 01:12:06,570
Så vi starter med længde = 0.

922
01:12:06,570 --> 01:12:11,580
Dette er meget ligesom at skrive strlen for en streng.

923
01:12:11,580 --> 01:12:17,780
Dette er hvad jeg ønsker at vise dig, denne for-løkke lige her.

924
01:12:17,780 --> 01:12:23,530
Det ser lidt funky, det er ikke den sædvanlige int i = 0, i <uanset, i + +.

925
01:12:23,530 --> 01:12:34,920
I stedet er det at initialisere vores variabel n for at være begyndelsen af ​​listen.

926
01:12:34,920 --> 01:12:40,620
Og så mens vores iterator variabel ikke er nul, vi holde ud.

927
01:12:40,620 --> 01:12:46,340
Dette skyldes efter sædvane vil i slutningen af ​​vores liste være null.

928
01:12:46,340 --> 01:12:48,770
Og så for at øge, snarere end at gøre + +,

929
01:12:48,770 --> 01:12:57,010
den sammenkædede liste svarende til + + er n = n-> næste.

930
01:12:57,010 --> 01:13:00,410
>> Jeg vil lade dig udfylde hullerne her, fordi vi er ude af tid.

931
01:13:00,410 --> 01:13:09,300
Men holde dette i tankerne, mens du arbejder på din spellr psets.

932
01:13:09,300 --> 01:13:11,650
Hægtede lister, hvis du gennemføre en hash tabel,

933
01:13:11,650 --> 01:13:14,010
vil helt sikkert komme i meget handy.

934
01:13:14,010 --> 01:13:21,780
Og har denne formsprog til sløjfning over ting vil gøre livet meget lettere, forhåbentlig.

935
01:13:21,780 --> 01:13:25,910
Eventuelle spørgsmål, hurtigt?

936
01:13:25,910 --> 01:13:28,920
[Sam] Vil du sende den udfyldte SLL og sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Jeg sender ud afsluttede dias og afsluttede SLL stack og queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]