1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Avsnitt 6: mindre bekväm]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Detta är CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Okej. Välkommen till avsnitt 6.

5
00:00:11,840 --> 00:00:14,690
Den här veckan kommer vi att tala om datastrukturer i snitt,

6
00:00:14,690 --> 00:00:19,780
främst eftersom denna veckas problem inställt på spellr

7
00:00:19,780 --> 00:00:24,410
gör en hel massa olika datastruktur prospektering.

8
00:00:24,410 --> 00:00:26,520
Det finns en massa olika sätt du kan gå med problemet som,

9
00:00:26,520 --> 00:00:31,570
och ju fler datastrukturer du känner, desto mer coola saker du kan göra.

10
00:00:31,570 --> 00:00:34,990
>> Så låt oss komma igång. Först ska vi prata om stackar,

11
00:00:34,990 --> 00:00:37,530
stapeln och kö datastrukturer som vi kommer att prata om.

12
00:00:37,530 --> 00:00:40,560
Stackar och köer är verkligen hjälpsam när vi börjar prata om grafer,

13
00:00:40,560 --> 00:00:44,390
som vi inte kommer att göra så mycket av just nu.

14
00:00:44,390 --> 00:00:52,820
Men de är riktigt bra för att förstå en av de stora fundamentala datastrukturer CS.

15
00:00:52,820 --> 00:00:54,880
Beskrivningen i problemet inställda specifikation,

16
00:00:54,880 --> 00:00:59,260
om du drar upp det, talar om högar som liknar

17
00:00:59,260 --> 00:01:05,239
högen av restauranger fack som du har i cafeterian på matsalar

18
00:01:05,239 --> 00:01:09,680
där när restauranger personal kommer och sätter matsal brickor ut efter att de har rengjorts dem,

19
00:01:09,680 --> 00:01:12,000
de stapla dem ovanpå varandra.

20
00:01:12,000 --> 00:01:15,050
Och sedan när barnen kommer in för att få mat,

21
00:01:15,050 --> 00:01:19,490
de drar facken bort först den översta en, sedan en under det, då en under den.

22
00:01:19,490 --> 00:01:25,190
Så i själva verket är det första facket som matsal personalen sätta ner den sista som får tas bort.

23
00:01:25,190 --> 00:01:32,330
Den sista som matsal personalen sätta på är den första som får tas ut för middag.

24
00:01:32,330 --> 00:01:38,100
I problemet apparatens spec, som du kan hämta om du inte redan har,

25
00:01:38,100 --> 00:01:46,730
Vi talar om modellering en stucture stack data med hjälp denna typ av struktur.

26
00:01:46,730 --> 00:01:51,070
>> Så vad vi har här, är det liknar det som presenterades i föreläsning,

27
00:01:51,070 --> 00:01:58,120
utom i föreläsning vi presenterade detta med Ints i motsats till char * s.

28
00:01:58,120 --> 00:02:06,250
Detta kommer att vara en bunt som lagrar vad?

29
00:02:06,250 --> 00:02:09,009
Daniel? Vad är det vi lagrar i denna stack?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strängar? >> Vi lagrar strängar i denna stack, exakt.

31
00:02:15,260 --> 00:02:20,950
Allt du behöver ha för att skapa en stapel är en matris

32
00:02:20,950 --> 00:02:23,920
av en viss kapacitet, som i detta fall,

33
00:02:23,920 --> 00:02:28,020
kapaciteten kommer att vara i stora bokstäver eftersom det är en konstant.

34
00:02:28,020 --> 00:02:36,340
Och sedan utöver arrayen är allt vi behöver för att spåra den nuvarande storleken på matrisen.

35
00:02:36,340 --> 00:02:38,980
En sak att notera här att det är ganska coolt

36
00:02:38,980 --> 00:02:47,060
är att vi skapar den staplade datastrukturen ovanpå en annan datastruktur, matrisen.

37
00:02:47,060 --> 00:02:50,110
Det finns olika sätt att genomföra stackar.

38
00:02:50,110 --> 00:02:54,250
Vi kommer inte att göra det riktigt än, men förhoppningsvis efter gör de länkade-listan problem,

39
00:02:54,250 --> 00:03:00,520
ser du hur du enkelt kan genomföra en bunt på toppen av en länkad lista också.

40
00:03:00,520 --> 00:03:02,640
Men nu kommer vi hålla oss till uppsättningarna.

41
00:03:02,640 --> 00:03:06,350
Så återigen, är allt vi behöver en matris och vi behöver bara följa storleken på matrisen.

42
00:03:06,350 --> 00:03:09,850
[Sam] Tyvärr, varför är det att du sa stapeln är på toppen av strängarna?

43
00:03:09,850 --> 00:03:13,440
För mig verkar det som strängarna är inom stacken.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ja. Vi skapar, vi tar vår array datastruktur -

45
00:03:16,790 --> 00:03:22,130
Det är en bra fråga. Så frågan är varför, för de människor som tittar på detta online,

46
00:03:22,130 --> 00:03:24,140
varför säger vi att stapeln är på toppen av strängarna,

47
00:03:24,140 --> 00:03:27,990
för här ser det ut som strängarna är inne i stacken?

48
00:03:27,990 --> 00:03:31,050
Som är helt fallet.

49
00:03:31,050 --> 00:03:34,660
Vad jag syftade på var att vi har en struktur array data.

50
00:03:34,660 --> 00:03:39,290
Vi har en rad char * s, denna array med strängar,

51
00:03:39,290 --> 00:03:45,300
och vi kommer att lägga till den för att skapa den staplade datastrukturen.

52
00:03:45,300 --> 00:03:48,620
>> Så en stapel är något mer komplicerad än en array.

53
00:03:48,620 --> 00:03:51,890
Vi kan använda en matris för att bygga en stapel.

54
00:03:51,890 --> 00:03:55,810
Så det är där vi säger att stapeln är byggd ovanpå en matris.

55
00:03:55,810 --> 00:04:02,510
Likaså som jag sa tidigare, kan vi bygga en stapel ovanpå en länkad lista.

56
00:04:02,510 --> 00:04:04,960
Istället för att använda en array för att hålla våra element,

57
00:04:04,960 --> 00:04:10,070
vi skulle kunna använda en länkad lista för att hålla våra element och bygga stacken runt det.

58
00:04:10,070 --> 00:04:12,420
Låt oss gå igenom ett par exempel, titta på några kod,

59
00:04:12,420 --> 00:04:14,960
att se vad som faktiskt händer här.

60
00:04:14,960 --> 00:04:23,400
Till vänster har jag kastat ner vad som stack struct skulle se ut i minnet

61
00:04:23,400 --> 00:04:28,330
Om kapaciteten skulle # definieras som fyra.

62
00:04:28,330 --> 00:04:33,490
Vi har våra fyra element char * array.

63
00:04:33,490 --> 00:04:38,110
Vi har strängar [0], stråkar [1], strängar [2], strängar [3],

64
00:04:38,110 --> 00:04:43,800
och sedan den sista plats för vår storlek heltal.

65
00:04:43,800 --> 00:04:46,270
Verkar denna mening? Okej.

66
00:04:46,270 --> 00:04:48,790
Detta är vad som händer om det jag gör till höger,

67
00:04:48,790 --> 00:04:55,790
som kommer att vara min kod, är att bara förklara en struct, ett staplat struct som kallas talet.

68
00:04:55,790 --> 00:05:01,270
Detta är vad vi får. Det fastställer denna fotavtryck i minnet.

69
00:05:01,270 --> 00:05:05,590
Den första frågan här är vad är innehållet i denna stack struct?

70
00:05:05,590 --> 00:05:09,250
Just nu är de ingenting, men de är inte helt ingenting.

71
00:05:09,250 --> 00:05:13,300
De är denna typ av skräp. Vi har ingen aning om vad som finns i dem.

72
00:05:13,300 --> 00:05:17,000
När vi förklarar stack s, vi kastar bara ner det på toppen av minnet.

73
00:05:17,000 --> 00:05:19,840
Det är ungefär som att förklara int i och inte initiera det.

74
00:05:19,840 --> 00:05:21,730
Du vet inte vad som finns där inne. Du kan läsa vad som finns där inne,

75
00:05:21,730 --> 00:05:27,690
men det kanske inte super bra.

76
00:05:27,690 --> 00:05:32,680
En sak som du vill alltid komma ihåg att göra är initiera vad måste initieras.

77
00:05:32,680 --> 00:05:35,820
I det här fallet kommer vi att initiera storleken vara noll,

78
00:05:35,820 --> 00:05:39,960
eftersom det kommer att visa sig vara mycket viktig för oss.

79
00:05:39,960 --> 00:05:43,450
Vi skulle kunna gå vidare och initiera alla pekare, alla char * s,

80
00:05:43,450 --> 00:05:49,670
vara några förståeligt värde, troligen null.

81
00:05:49,670 --> 00:05:58,270
Men det är inte helt nödvändigt att vi gör det.

82
00:05:58,270 --> 00:06:04,200
>> Nu är de två huvudsakliga operationer på staplar är?

83
00:06:04,200 --> 00:06:07,610
Någon minns från föreläsning vad du gör med högar? Ja?

84
00:06:07,610 --> 00:06:09,700
[Stella] Pushing och popping? >> Exakt.

85
00:06:09,700 --> 00:06:13,810
Trycka och popping är de två huvudsakliga verksamhet på staplar.

86
00:06:13,810 --> 00:06:17,060
Och vad gör tryck? >> Det sätter något på toppen

87
00:06:17,060 --> 00:06:19,300
av stapeln, och sedan poppande tar bort det.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exakt. Så trycka skjuter något på toppen av stacken.

89
00:06:23,150 --> 00:06:27,700
Det är som matsal personal att sätta en matsal ner förpackningen på disken.

90
00:06:27,700 --> 00:06:33,630
Och poppar tar en matplats fack bort från stapeln.

91
00:06:33,630 --> 00:06:36,460
Låt oss gå igenom ett par exempel på vad som händer

92
00:06:36,460 --> 00:06:39,720
När vi driva saker till stacken.

93
00:06:39,720 --> 00:06:45,110
Om vi ​​skulle driva strängen "Hej" på vår stack,

94
00:06:45,110 --> 00:06:49,760
Detta är vad vår diagrammet skulle se ut nu.

95
00:06:49,760 --> 00:06:53,410
Se vad som händer?

96
00:06:53,410 --> 00:06:56,530
Vi drev i den första delen av vår strängar array

97
00:06:56,530 --> 00:07:01,420
och vi folkomröstade vår storlek räkna till 1.

98
00:07:01,420 --> 00:07:05,340
Så om vi ser på skillnaden mellan de två bilderna, här var 0, här innan tryck.

99
00:07:05,340 --> 00:07:08,690
Här är efter tryck.

100
00:07:08,690 --> 00:07:13,460
Innan push, efter tryck.

101
00:07:13,460 --> 00:07:16,860
Och nu har vi en del av vår stack.

102
00:07:16,860 --> 00:07:20,970
Det är strängen "hello", och det är det.

103
00:07:20,970 --> 00:07:24,440
Allt annat i arrayen, i våra strängar array fortfarande skräp.

104
00:07:24,440 --> 00:07:27,070
Vi har inte initierats det.

105
00:07:27,070 --> 00:07:29,410
Låt oss säga att vi trycker en annan sträng på vår stack.

106
00:07:29,410 --> 00:07:32,210
Vi kommer att driva "världen" på den här tiden.

107
00:07:32,210 --> 00:07:35,160
Så du kan se "världen" här går på toppen av "hej",

108
00:07:35,160 --> 00:07:40,040
och storleken räkna går upp till 2.

109
00:07:40,040 --> 00:07:44,520
Nu kan vi trycka "CS50" och som kommer att gå på toppen igen.

110
00:07:44,520 --> 00:07:51,110
Om vi ​​går tillbaka, kan du se hur vi driver saker på toppen av stacken.

111
00:07:51,110 --> 00:07:53,320
Och nu får vi pop.

112
00:07:53,320 --> 00:07:58,910
När vi dök något från i stapeln, hände vad?

113
00:07:58,910 --> 00:08:01,540
Någon se skillnaden? Det är ganska subtila.

114
00:08:01,540 --> 00:08:05,810
[Student] Storleken. >> Ja, ändrade storleken.

115
00:08:05,810 --> 00:08:09,040
>> Vad skulle du ha förväntat sig att förändras?

116
00:08:09,040 --> 00:08:14,280
[Student] De strängar, också. >> Höger. Strängarna också.

117
00:08:14,280 --> 00:08:17,110
Det visar sig att när du gör det här sättet,

118
00:08:17,110 --> 00:08:21,960
eftersom vi inte kopiera element i vår stack,

119
00:08:21,960 --> 00:08:24,670
vi faktiskt inte behöver göra någonting, vi kan bara använda storlek

120
00:08:24,670 --> 00:08:28,630
att hålla reda på hur många saker i vår grupp

121
00:08:28,630 --> 00:08:33,780
så att när vi dyker igen, igen vi dekrementera bara vår storlek ner till 1.

122
00:08:33,780 --> 00:08:39,440
Det finns ingen anledning att faktiskt gå in och skriva något.

123
00:08:39,440 --> 00:08:41,710
Typ av funky.

124
00:08:41,710 --> 00:08:46,520
Det visar sig att vi oftast bara lämna saker ensam eftersom det är mindre arbete för oss att göra.

125
00:08:46,520 --> 00:08:50,060
Om vi ​​inte behöver gå tillbaka och skriva något, så varför göra det?

126
00:08:50,060 --> 00:08:54,150
Så när vi pop dubbelt upp av stapeln, är allt som gör dekrementera storleken ett par gånger.

127
00:08:54,150 --> 00:08:59,120
Och återigen, det är bara för att vi inte kopierar saker i vår stack.

128
00:08:59,120 --> 00:09:01,320
Ja? Varsågod.

129
00:09:01,320 --> 00:09:04,460
[Student, obegripligt] >> Och vad händer när du trycker något igen?

130
00:09:04,460 --> 00:09:08,570
När du trycker något igen, det var den vägen?

131
00:09:08,570 --> 00:09:12,390
Vart tar det vägen, Basil? >> Till strängar [1]? >> Höger.

132
00:09:12,390 --> 00:09:14,530
Varför inte det gå till strängar [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Eftersom det glömde att det fanns något i strängar [1] och [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exakt. Vår stack i huvudsak "glömde" att det höll på att något

135
00:09:24,040 --> 00:09:29,480
i strängar [1] eller strängar [2], så när vi trycker "woot",

136
00:09:29,480 --> 00:09:36,670
det sätter bara in det elementet vid strängar [1].

137
00:09:36,670 --> 00:09:41,590
Finns det några frågor om hur det fungerar, på en grundläggande nivå?

138
00:09:41,590 --> 00:09:45,160
[Sam] Så detta är inte dynamisk på något sätt, i termer av mängd

139
00:09:45,160 --> 00:09:47,620
eller i termer av storleken på stapeln?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exakt. Detta är - poängen var att detta inte var en dynamiskt growning stack.

141
00:09:56,750 --> 00:10:02,850
Detta är en stapel som kan hålla, som mest, fyra char * s, högst fyra saker.

142
00:10:02,850 --> 00:10:07,580
Om vi ​​skulle försöka driva 1/5 sak, vad tror du ska hända?

143
00:10:07,580 --> 00:10:11,870
[Studenter, obegripliga]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exakt. Det finns ett antal saker som kan hända.

145
00:10:14,600 --> 00:10:19,330
Det kan möjligen seg fel, beroende på vad vi var -

146
00:10:19,330 --> 00:10:22,530
exakt hur vi genomföra back-end.

147
00:10:22,530 --> 00:10:31,740
Det kan skriva. Det kan ha att buffertspill som vi pratade om i klassen.

148
00:10:31,740 --> 00:10:35,240
Vad skulle vara det mest självklara sak som kan skrivas över

149
00:10:35,240 --> 00:10:42,370
om vi försökte driva en extra sak på vår stack?

150
00:10:42,370 --> 00:10:44,550
Så du nämnde ett buffertspill.

151
00:10:44,550 --> 00:10:47,870
Vad kan vara det som skulle få skrivas över eller stampade på

152
00:10:47,870 --> 00:10:52,320
om vi spill misstag genom att försöka driva en extra sak?

153
00:10:52,320 --> 00:10:54,730
[Daniel, obegripligt] >> Möjligt.

154
00:10:54,730 --> 00:10:58,440
Men först, vad kan hända? Tänk om vi försökte driva fjärdedel sak?

155
00:10:58,440 --> 00:11:06,220
Det kan skriva över storleken, åtminstone med detta minne diagram som vi har.

156
00:11:06,220 --> 00:11:10,880
>> I problembild specifikationen, vilket vad vi kommer att genomföra i dag,

157
00:11:10,880 --> 00:11:16,030
vad vi vill göra är att återvända bara falskt.

158
00:11:16,030 --> 00:11:20,030
Vår push-metoden kommer att returnera ett booleskt värde,

159
00:11:20,030 --> 00:11:22,920
och att booleskt värde kommer att vara sant om push lyckas

160
00:11:22,920 --> 00:11:29,730
och falskt om vi inte kan skjuta något mer eftersom stapeln är full.

161
00:11:29,730 --> 00:11:33,620
Låt oss gå igenom lite av den koden just nu.

162
00:11:33,620 --> 00:11:36,400
Här är vår push-funktion.

163
00:11:36,400 --> 00:11:40,380
Vår push-funktion för en stack kommer att ta i strängen att sätta på stacken.

164
00:11:40,380 --> 00:11:45,820
Det kommer att returnera true om strängen framgångsrikt drivit

165
00:11:45,820 --> 00:11:51,820
på stacken och i annat fall false.

166
00:11:51,820 --> 00:11:59,740
Några förslag på vad som kan vara en bra första sak att göra här?

167
00:11:59,740 --> 00:12:20,630
[Sam] Om storleken är lika kapaciteten sedan återvända falska?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Bra jobb.

169
00:12:23,320 --> 00:12:26,310
Om storleken är kapaciteten, kommer vi att returnera false.

170
00:12:26,310 --> 00:12:29,270
Vi kan inte sätta något mer i vår stack.

171
00:12:29,270 --> 00:12:36,900
Annars vill vi sätta något på toppen av stacken.

172
00:12:36,900 --> 00:12:41,670
Vad är "toppen av stacken," början?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Storlek 0? >> Storlek 0.

174
00:12:43,650 --> 00:12:49,990
Vad är toppen av stacken efter det finns en sak i stapeln? Missy, vet du?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. >> Storlek är en, exakt. Du fortsätta att lägga till storleken,

176
00:12:52,720 --> 00:13:01,690
och varje gång du lägger i den nya delen på indexet storlek i arrayen.

177
00:13:01,690 --> 00:13:05,470
Vi kan göra det med den typen av en-liner, om det är vettigt.

178
00:13:05,470 --> 00:13:11,910
Så vi har fått våra strängar array, vi kommer att få tillgång till det på storleken index,

179
00:13:11,910 --> 00:13:14,780
och vi kommer bara att lagra våra char * där.

180
00:13:14,780 --> 00:13:19,340
Lägg märke till hur det finns ingen sträng kopiering pågår här,

181
00:13:19,340 --> 00:13:29,680
ingen dynamisk allokering av minne?

182
00:13:29,680 --> 00:13:34,440
Och sedan Missy tog upp vad vi nu måste göra,

183
00:13:34,440 --> 00:13:40,570
eftersom vi har lagrat strängen på en lämplig plats i arrayen,

184
00:13:40,570 --> 00:13:49,230
och hon sa att vi var tvungna att öka storleken på en så att vi är redo för nästa tryck.

185
00:13:49,230 --> 00:13:53,950
Så vi kan göra det med s.size + +.

186
00:13:53,950 --> 00:13:59,330
Vid denna punkt har vi drivit i vår grupp. Vad är det sista vi behöver göra?

187
00:13:59,330 --> 00:14:10,110
[Student] Tillbaka sant. >> Tillbaka sant.

188
00:14:10,110 --> 00:14:14,690
Så det är ganska enkelt, en ganska enkel kod. Inte för mycket.

189
00:14:14,690 --> 00:14:17,070
När du har lindade huvudet runt hur stapeln fungerar,

190
00:14:17,070 --> 00:14:21,910
Detta är ganska enkel att genomföra.

191
00:14:21,910 --> 00:14:26,390
>> Nu är nästa del av detta poppar en sträng av av stapeln.

192
00:14:26,390 --> 00:14:29,410
Jag ska ge er lite tid att arbeta med detta lite.

193
00:14:29,410 --> 00:14:34,320
Det är nästan huvudsak motsatsen till vad vi har gjort här i tryck.

194
00:14:34,320 --> 00:14:38,510
Vad jag har gjort är faktiskt - oops.

195
00:14:38,510 --> 00:14:48,160
Jag har startat upp en apparat hit, och i apparaten,

196
00:14:48,160 --> 00:14:53,600
Jag har dragit upp problemet som 5 specifikationen.

197
00:14:53,600 --> 00:15:02,560
Om vi ​​zoomar in här, kan vi se jag är på cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Har ni hämtat denna kod som ligger här, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Okej. Om du inte har gjort det, gör det nu, riktigt snabbt.

200
00:15:15,030 --> 00:15:22,130
Jag gör det i min terminalfönster.

201
00:15:22,130 --> 00:15:25,090
Jag gjorde faktiskt det här uppe. Ja.

202
00:15:25,090 --> 00:15:34,730
Ja, Sam? >> Jag har en fråga om varför sa du s.string s konsoler storlek = str?

203
00:15:34,730 --> 00:15:42,910
Vad är str? Är det definierade någonstans innan, eller - åh, i char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ja, exakt. Det var argumentet. >> Åh, okej. Ursäkta.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Vi anger strängen för att skjuta in

206
00:15:49,470 --> 00:15:55,220
Den andra frågan som kan komma upp att vi verkligen inte prata om här var

207
00:15:55,220 --> 00:15:58,810
vi tog för givet att vi hade denna variabel som heter s

208
00:15:58,810 --> 00:16:02,710
som var i omfattning och tillgängliga för oss.

209
00:16:02,710 --> 00:16:06,960
Vi tog för givet att s var stack struct.

210
00:16:06,960 --> 00:16:08,930
Så ser tillbaka på denna push-kod,

211
00:16:08,930 --> 00:16:13,450
kan du se att vi gör saker med den här strängen som fick skickas i

212
00:16:13,450 --> 00:16:19,210
men då helt plötsligt, vi tillgång s.size, som, var kom s ifrån?

213
00:16:19,210 --> 00:16:23,020
I koden som vi kommer att titta på i avsnittet arkiv

214
00:16:23,020 --> 00:16:27,100
och sedan saker som du ska göra i ditt problem sätter,

215
00:16:27,100 --> 00:16:32,440
Vi har gjort vår stack struktur en global variabel

216
00:16:32,440 --> 00:16:36,380
så att vi kan få tillgång till den i alla våra olika funktioner

217
00:16:36,380 --> 00:16:40,630
utan att manuellt behöva föra den runt och förbi den referens,

218
00:16:40,630 --> 00:16:44,870
göra allt sånt till det.

219
00:16:44,870 --> 00:16:52,280
Vi bara fuskar lite, om du vill, för att göra saker trevligare.

220
00:16:52,280 --> 00:16:57,430
Och det är något som vi gör här eftersom det är på skoj, det är lättare.

221
00:16:57,430 --> 00:17:02,800
Ofta ser du människor gör detta om de har en stor datastruktur

222
00:17:02,800 --> 00:17:07,750
som är drivs på inom deras program.

223
00:17:07,750 --> 00:17:09,560
>> Låt oss gå tillbaka över till apparaten.

224
00:17:09,560 --> 00:17:15,240
Fick alla får framgångsrikt section6.zip?

225
00:17:15,240 --> 00:17:20,440
Alla packa upp den med unzip section6.zip?

226
00:17:20,440 --> 00:17:27,200
Om du går in i avsnitt 6 katalogen -

227
00:17:27,200 --> 00:17:29,220
aah, överallt -

228
00:17:29,220 --> 00:17:32,840
och du lista vad som finns här, ser du att du har tre olika. C-filer.

229
00:17:32,840 --> 00:17:38,350
Du har en kö, en SLL, vilket är var för sig-länkad lista, och en skorsten.

230
00:17:38,350 --> 00:17:44,600
Om du öppnar stack.c,

231
00:17:44,600 --> 00:17:47,330
kan du se att vi har denna struct definieras för oss,

232
00:17:47,330 --> 00:17:51,330
den exakta struktur som vi just talade om i bilderna.

233
00:17:51,330 --> 00:17:56,340
Vi har vårt globala variabeln för stapeln,

234
00:17:56,340 --> 00:18:00,110
vi har vår push-funktion,

235
00:18:00,110 --> 00:18:04,230
och sedan har vi vår POP-funktionen.

236
00:18:04,230 --> 00:18:08,320
Jag sätter koden för trycka tillbaka upp på bilden här,

237
00:18:08,320 --> 00:18:10,660
men vad jag skulle vilja att ni ska göra är att efter bästa förmåga,

238
00:18:10,660 --> 00:18:13,790
gå och genomföra pop-funktionen.

239
00:18:13,790 --> 00:18:18,480
När du har genomfört den kan du kompilera detta med att göra stack,

240
00:18:18,480 --> 00:18:22,540
och kör sedan den resulterande stacken körbara,

241
00:18:22,540 --> 00:18:28,390
och som kommer att köra allt detta test kod här nere som är i main.

242
00:18:28,390 --> 00:18:31,060
Och viktigaste sköter faktiskt göra push och pop samtal

243
00:18:31,060 --> 00:18:33,220
och se till att allt går igenom bra.

244
00:18:33,220 --> 00:18:36,820
Den initierar också marker här

245
00:18:36,820 --> 00:18:39,780
så du behöver inte oroa dig för att initiera det.

246
00:18:39,780 --> 00:18:42,310
Du kan anta att den är rätt initierats

247
00:18:42,310 --> 00:18:48,000
med den tid som du kommer åt den i pop-funktionen.

248
00:18:48,000 --> 00:18:53,530
Verkar det vettigt?

249
00:18:53,530 --> 00:19:00,100
Så här går vi. Det finns push-koden.

250
00:19:00,100 --> 00:19:13,210
Jag ska ge er 5 eller 10 minuter.

251
00:19:13,210 --> 00:19:15,690
Och om du har några frågor tiden medan du kodning,

252
00:19:15,690 --> 00:19:17,710
vänd dem högt.

253
00:19:17,710 --> 00:19:23,080
Så om du kommer till en stötestenen, bara att fråga.

254
00:19:23,080 --> 00:19:26,030
Låt mig veta, låt alla andra veta.

255
00:19:26,030 --> 00:19:28,160
Arbeta med din granne också.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Vi är bara genomföra pop just nu? >> Bara pop.

257
00:19:30,360 --> 00:19:34,200
Även om du kan kopiera genomförandet av tryck om du vill

258
00:19:34,200 --> 00:19:37,780
så att testningen kommer att fungera.

259
00:19:37,780 --> 00:19:41,940
Eftersom det är svårt att testa saker hamnar i -

260
00:19:41,940 --> 00:19:49,030
eller är det svårt att testa poppar saker av en stapel om det inte finns något i stacken till att börja med.

261
00:19:49,030 --> 00:19:55,250
>> Vad är pop tänkt att återvända? Elementet från toppen av stacken.

262
00:19:55,250 --> 00:20:01,260
Det är tänkt att få elementet bort från toppen av stacken

263
00:20:01,260 --> 00:20:05,780
och sedan dekrementera storleken av stapeln,

264
00:20:05,780 --> 00:20:07,810
och nu har du förlorat elementet på toppen.

265
00:20:07,810 --> 00:20:11,420
Och sedan tillbaka elementet på toppen.

266
00:20:11,420 --> 00:20:20,080
[Student, obegripligt]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Så vad händer om du gör det? [Student, obegripligt]

268
00:20:28,810 --> 00:20:34,000
Vad hamnar händer är du förmodligen komma antingen

269
00:20:34,000 --> 00:20:37,350
ett element som inte har initierats ännu, så din beräkning

270
00:20:37,350 --> 00:20:39,990
var det sista elementet är avstängd.

271
00:20:39,990 --> 00:20:46,260
Så här, om du märker i tryck, vi åt strängar på s.size elementet

272
00:20:46,260 --> 00:20:48,560
eftersom det är ett nytt index.

273
00:20:48,560 --> 00:20:51,460
Det är den nya toppen av stacken.

274
00:20:51,460 --> 00:21:01,100
Medan i pop är s.size kommer att bli nästa utrymme,

275
00:21:01,100 --> 00:21:05,210
det utrymme som är på toppen av alla element i din stack.

276
00:21:05,210 --> 00:21:10,050
Så den översta delen är inte s.size,

277
00:21:10,050 --> 00:21:14,930
utan snarare är det under den.

278
00:21:14,930 --> 00:21:19,640
>> Den andra sak att göra när du - i pop,

279
00:21:19,640 --> 00:21:22,030
är du behöver för att minska det stora.

280
00:21:22,030 --> 00:21:28,750
Om du minns tillbaka till vår lilla diagrammet här,

281
00:21:28,750 --> 00:21:30,980
egentligen, det enda som vi såg hända när vi kallas pop

282
00:21:30,980 --> 00:21:36,150
var att denna storlek sjunkit, först 2, sedan till 1.

283
00:21:36,150 --> 00:21:42,620
Sedan när vi drivit ett nytt element på, skulle det gå på i rätt plats.

284
00:21:42,620 --> 00:21:49,610
[Basil] Om s.size är 2, skulle det inte gå att elementet 2,

285
00:21:49,610 --> 00:21:54,400
och då du skulle vilja pop det elementet av?

286
00:21:54,400 --> 00:21:59,510
Så om vi gick till - >> Så låt oss titta på detta igen.

287
00:21:59,510 --> 00:22:07,730
Om detta är vår stack på denna punkt

288
00:22:07,730 --> 00:22:12,130
och vi kallar pop,

289
00:22:12,130 --> 00:22:16,150
där index är den översta delen?

290
00:22:16,150 --> 00:22:19,300
[Basil] Som 2 men det kommer att dyka 3. >> Höger.

291
00:22:19,300 --> 00:22:24,220
Så det är där vår storlek är 3, men vi vill att pop elementet vid index 2.

292
00:22:24,220 --> 00:22:29,900
Det är den typiska typen av av av en som du har med noll-indexering av matriser.

293
00:22:29,900 --> 00:22:36,430
Så du vill att pop det tredje elementet, men det tredje elementet är inte på index 3.

294
00:22:36,430 --> 00:22:39,430
Och anledningen till att vi inte behöver göra det minus 1 när vi driver

295
00:22:39,430 --> 00:22:44,120
beror just nu, märker du att den översta delen,

296
00:22:44,120 --> 00:22:47,600
om vi skulle skjuta något annat på stapeln vid denna punkt,

297
00:22:47,600 --> 00:22:50,360
Vi vill driva det på index 3.

298
00:22:50,360 --> 00:23:03,550
Och det råkar vara så att storleken och indexen rada upp när du trycker.

299
00:23:03,550 --> 00:23:06,960
>> Vem har en fungerande skorsten genomförande?

300
00:23:06,960 --> 00:23:09,690
Du har en fungerande skorsten ett. Har du pop arbetar ännu?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Ja. Jag tror det.

302
00:23:11,890 --> 00:23:14,610
>> Programmet körs och inte seg förkastningar, det skrivs ut?

303
00:23:14,610 --> 00:23:17,520
Har skriva ut "framgång" när du kör den?

304
00:23:17,520 --> 00:23:22,630
Ja. Gör stack, kör den om den skriver ut "framgång" och går inte bommen,

305
00:23:22,630 --> 00:23:26,000
då alla är bra.

306
00:23:26,000 --> 00:23:34,070
Okej. Låt oss gå över till apparaten verkligen snabbt,

307
00:23:34,070 --> 00:23:46,100
och vi kommer att gå igenom det här.

308
00:23:46,100 --> 00:23:51,110
Om vi ​​tittar på vad som händer här med pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, vad var det första du gjorde?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Om s.size är större än 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okej. Och varför gjorde du det?

312
00:24:03,120 --> 00:24:05,610
[Daniel] För att säkerställa att det var något inuti stapeln.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Höger. Du vill testa att se till att s.size är större än 0;

314
00:24:10,950 --> 00:24:13,280
annars vad du vill ha hända?

315
00:24:13,280 --> 00:24:16,630
[Daniel] Return null? >> Tillbaka null, exakt.

316
00:24:16,630 --> 00:24:20,740
Så om s.size är större än 0. Vad ska vi göra?

317
00:24:20,740 --> 00:24:25,890
Vad gör vi om stacken inte är tom?

318
00:24:25,890 --> 00:24:31,210
[Stella] Du dekrementera storlek? >> Dekrementera du storlek, okej.

319
00:24:31,210 --> 00:24:34,440
Så hur har du det? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. Och vad gjorde du?

321
00:24:37,030 --> 00:24:44,140
[Stella] Och då sa jag tillbaka s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
Annars kan du returnera null. Ja, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Varför det inte behöver vara s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Ja. >> Uppfattat.

326
00:24:58,430 --> 00:25:00,980
[Sam] Jag trodde att du tar 1 ut,

327
00:25:00,980 --> 00:25:04,290
då du kommer att vara tillbaka inte den som de bad om.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Och det var precis vad vi pratade om med hela denna fråga om 0 index.

329
00:25:09,400 --> 00:25:11,380
Så om vi in ​​igen här.

330
00:25:11,380 --> 00:25:15,650
Om vi ​​tittar på den här killen här, kan du se att när vi pop,

331
00:25:15,650 --> 00:25:19,340
vi poppar elementet vid index 2.

332
00:25:19,340 --> 00:25:25,200
>> Så vi minskar vår storlek först, sedan vår storlek motsvarar vårt index.

333
00:25:25,200 --> 00:25:39,650
Om vi ​​inte stega storlek först, sedan vi måste göra storlek -1 och sedan minskning.

334
00:25:39,650 --> 00:25:45,270
Jättebra. Alla bra?

335
00:25:45,270 --> 00:25:47,530
Har du frågor om detta?

336
00:25:47,530 --> 00:25:54,050
Det finns ett antal olika sätt att skriva detta.

337
00:25:54,050 --> 00:26:03,290
I själva verket kan vi göra något ännu - vi kan göra en one-liner.

338
00:26:03,290 --> 00:26:05,770
Vi kan göra en en-line avkastning.

339
00:26:05,770 --> 00:26:12,980
Så vi kan faktiskt stega innan vi återvänder genom att göra det.

340
00:26:12,980 --> 00:26:18,320
Så sätta - före s.size.

341
00:26:18,320 --> 00:26:22,060
Det gör linjen verkligen tät.

342
00:26:22,060 --> 00:26:30,940
Om skillnaden mellan de -. Storlek och s.size--

343
00:26:30,940 --> 00:26:40,130
är att detta postfix - de kallar det postfix eftersom - kommer efter s.size--

344
00:26:40,130 --> 00:26:47,430
betyder att s.size utvärderas för att finna index

345
00:26:47,430 --> 00:26:50,410
eftersom det är närvarande när denna linje utförs,

346
00:26:50,410 --> 00:26:54,290
och sedan detta - händer efter raden blir avrättas.

347
00:26:54,290 --> 00:27:00,340
Efter elementet vid index s.size nås.

348
00:27:00,340 --> 00:27:07,260
Och det är inte vad vi vill, eftersom vi vill att minskning ska ske först.

349
00:27:07,260 --> 00:27:10,990
Othewise, vi kommer att komma arrayen, effektivt utanför marginalerna.

350
00:27:10,990 --> 00:27:16,850
Vi kommer att komma elementet ovanför det som vi verkligen vill komma åt.

351
00:27:16,850 --> 00:27:23,840
Ja, Sam? >> Är det snabbare eller använda mindre RAM att göra i en rad eller inte?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Ärligt talat, det beror egentligen.

353
00:27:29,620 --> 00:27:34,220
[Sam, obegripligt] >> Ja, det beror. Du kan göra kompilatorn trick

354
00:27:34,220 --> 00:27:41,580
att få kompilatorn att erkänna att, vanligtvis, antar jag.

355
00:27:41,580 --> 00:27:44,840
>> Så vi har nämnt lite om detta kompilator optimering grejer

356
00:27:44,840 --> 00:27:47,400
som du kan göra att sammanställa,

357
00:27:47,400 --> 00:27:50,580
och det är den typ av sak som en kompilator skulle kunna räkna ut,

358
00:27:50,580 --> 00:27:54,710
som oh, hey, jag kanske kan göra allt detta i en operation,

359
00:27:54,710 --> 00:27:59,420
i motsats till laddning av storlek variabeln i från RAM,

360
00:27:59,420 --> 00:28:03,770
nedräkning den, lagra den tillbaka ut, och sedan ladda den igen

361
00:28:03,770 --> 00:28:08,000
att behandla resten av denna operation.

362
00:28:08,000 --> 00:28:10,710
Men typiskt, nej, detta är inte det slags saker

363
00:28:10,710 --> 00:28:20,770
som kommer att göra ditt program betydligt snabbare.

364
00:28:20,770 --> 00:28:26,000
Några fler frågor om stackar?

365
00:28:26,000 --> 00:28:31,360
>> Så trycka och popping. Om ni vill prova hacker upplagan,

366
00:28:31,360 --> 00:28:33,660
vad vi har gjort i hacker upplagan faktiskt borta

367
00:28:33,660 --> 00:28:37,670
och gjorde denna stack växa dynamiskt.

368
00:28:37,670 --> 00:28:43,190
Utmaningen finns främst här uppe i push-funktionen,

369
00:28:43,190 --> 00:28:48,820
att räkna ut hur man gör den arrayen växa

370
00:28:48,820 --> 00:28:52,450
som du håller trycka mer och mer element på till stacken.

371
00:28:52,450 --> 00:28:56,000
Det är faktiskt inte så mycket extra kod.

372
00:28:56,000 --> 00:29:00,080
Bara ett samtal till - du måste komma ihåg att få samtal till malloc där ordentligt,

373
00:29:00,080 --> 00:29:03,310
och sedan räkna ut när du ska ringa realloc.

374
00:29:03,310 --> 00:29:06,090
Det är en rolig utmaning om du är intresserad.

375
00:29:06,090 --> 00:29:11,550
>> Men för närvarande, låt oss gå vidare och låt oss tala om köer.

376
00:29:11,550 --> 00:29:15,680
Bläddra igenom här.

377
00:29:15,680 --> 00:29:19,340
Kön är en nära syskon av stapeln.

378
00:29:19,340 --> 00:29:25,380
Så i stacken, saker som sätter i förra

379
00:29:25,380 --> 00:29:28,810
var de första saker för att sedan hämtas.

380
00:29:28,810 --> 00:29:33,600
Vi har denna sist in, först ut, eller LIFO, beställning.

381
00:29:33,600 --> 00:29:38,390
Medan i kön, som du kan förvänta dig från när du står i linje,

382
00:29:38,390 --> 00:29:41,980
den första personen att komma i linje, den första sak att komma in i kön,

383
00:29:41,980 --> 00:29:47,630
är det första som får hämtas från kön.

384
00:29:47,630 --> 00:29:51,490
Köer är också ofta används när vi har att göra med grafer,

385
00:29:51,490 --> 00:29:55,560
som vi pratade om kort med högar,

386
00:29:55,560 --> 00:30:00,260
och köerna är också praktiskt för en massa andra saker.

387
00:30:00,260 --> 00:30:06,180
En sak som kommer upp ofta försöker upprätthålla, till exempel,

388
00:30:06,180 --> 00:30:12,310
en sorterad lista av element.

389
00:30:12,310 --> 00:30:17,650
Och du kan göra detta med en matris. Du kan ha en sorterad lista över saker i en matris,

390
00:30:17,650 --> 00:30:20,650
men där det blir knepigt är så har du alltid hitta

391
00:30:20,650 --> 00:30:26,160
rätt plats att sätta in nästa sak.

392
00:30:26,160 --> 00:30:28,250
Så om du har en mängd siffror, 1 till 10,

393
00:30:28,250 --> 00:30:31,630
och sedan vill utöka det till alla nummer 1 till 100,

394
00:30:31,630 --> 00:30:33,670
och du får dessa siffror i slumpmässig ordning och försöker hålla allt

395
00:30:33,670 --> 00:30:40,650
sorteras som du går igenom, slut dig att behöva göra en hel del växling.

396
00:30:40,650 --> 00:30:43,910
Med vissa typer av köer och vissa typer av underliggande datastrukturer,

397
00:30:43,910 --> 00:30:46,670
Du kan faktiskt hålla det ganska enkelt.

398
00:30:46,670 --> 00:30:50,640
Du behöver inte lägga till något och sedan blanda det hela varje gång.

399
00:30:50,640 --> 00:30:56,770
Inte heller behöver du göra en hel del förskjutning av de inre delarna runt.

400
00:30:56,770 --> 00:31:02,990
När vi tittar på en kö, ser du att - även i queue.c i avsnittet koden -

401
00:31:02,990 --> 00:31:10,950
den struct som vi har gett dig är verkligen liknar struct att vi gav dig för en stack.

402
00:31:10,950 --> 00:31:13,770
>> Det finns ett undantag till detta, och att ett undantag

403
00:31:13,770 --> 00:31:21,700
är att vi har denna extra heltal kallas huvudet,

404
00:31:21,700 --> 00:31:28,120
och huvudet här är för att hålla koll på huvudet av kön,

405
00:31:28,120 --> 00:31:32,160
eller det första elementet i kön.

406
00:31:32,160 --> 00:31:37,470
Med en stack, kunde vi hålla reda på element som vi skulle hämta,

407
00:31:37,470 --> 00:31:40,800
eller toppen av stacken, med bara storleken,

408
00:31:40,800 --> 00:31:44,220
medan med en kö, vi har att ta itu med motsatta ändar.

409
00:31:44,220 --> 00:31:49,000
Vi försöker please saker på slutet, men sedan tillbaka saker från fronten.

410
00:31:49,000 --> 00:31:54,640
Så effektivt, med huvudet, vi har index i början av kön,

411
00:31:54,640 --> 00:31:58,920
och storleken ger oss indexet i slutet av kön

412
00:31:58,920 --> 00:32:03,730
så att vi kan hämta saker från huvudet och lägga till saker till svansen.

413
00:32:03,730 --> 00:32:06,890
Medan med stapeln, var vi bara behandlar toppen av stacken.

414
00:32:06,890 --> 00:32:08,900
Vi hade aldrig att komma till botten av stapeln.

415
00:32:08,900 --> 00:32:12,220
Vi lade bara saker till toppen och tog saker från toppen

416
00:32:12,220 --> 00:32:17,470
så att vi inte behöver det extra fält inuti våra struct.

417
00:32:17,470 --> 00:32:20,590
Gör som generellt vettigt?

418
00:32:20,590 --> 00:32:27,670
Okej. Ja, Charlotte? [Charlotte, obegripligt]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Det är en bra fråga, och det var en som kom upp i föreläsningen.

420
00:32:32,660 --> 00:32:36,290
Kanske gå igenom några exempel illustrerar varför

421
00:32:36,290 --> 00:32:41,400
vi vill inte använda strängar [0] som chef för kön.

422
00:32:41,400 --> 00:32:46,770
>> Så tänk att vi har vår kö, vi kommer att kalla det kö.

423
00:32:46,770 --> 00:32:49,210
I början, när vi har bara instansieras det,

424
00:32:49,210 --> 00:32:53,330
när vi bara har förklarat det, vi har initierats ingenting.

425
00:32:53,330 --> 00:32:56,790
Det är allt skräp. Så naturligtvis vill vi se till att vi initiera

426
00:32:56,790 --> 00:33:00,950
både storlek och fälten huvudet är 0, något rimligt.

427
00:33:00,950 --> 00:33:05,770
Vi kan också gå vidare och null ut elementen i vår kö.

428
00:33:05,770 --> 00:33:09,930
Och för att göra detta diagram passform, märker att nu vår kö bara kan hålla tre element;

429
00:33:09,930 --> 00:33:13,150
medan vår stack kunde hålla fyra, kan vår kö hålla bara tre.

430
00:33:13,150 --> 00:33:18,680
Och det är bara att göra diagrammet passform.

431
00:33:18,680 --> 00:33:26,150
Det första som händer här är att vi köa strängen "hej".

432
00:33:26,150 --> 00:33:30,380
Och precis som vi gjorde med stacken, inget hemskt annorlunda här,

433
00:33:30,380 --> 00:33:39,230
Vi kastar strängen på vid strängar [0] och öka vår storlek med 1.

434
00:33:39,230 --> 00:33:42,720
Vi köa "bye", blir det sätta på.

435
00:33:42,720 --> 00:33:45,870
Så detta ser ut som en bunt för det mesta.

436
00:33:45,870 --> 00:33:53,230
Vi började här, nytt inslag, nytt element, håller storlek går upp.

437
00:33:53,230 --> 00:33:56,330
Vad händer på denna punkt när vi vill avköa något?

438
00:33:56,330 --> 00:34:01,280
När vi vill avköa, som är den del som vi vill avköa?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Exakt rätt, Basil.

440
00:34:04,110 --> 00:34:10,960
Vi vill bli av med den första strängen, den här, "hej".

441
00:34:10,960 --> 00:34:13,170
Så vad var den andra saken som förändrats?

442
00:34:13,170 --> 00:34:17,010
Märker när vi popped något bort av stapeln, bytte vi bara storleken,

443
00:34:17,010 --> 00:34:22,080
men här har vi ett par saker som förändras.

444
00:34:22,080 --> 00:34:27,440
Inte bara storleken ändras, men förändringarna huvudet.

445
00:34:27,440 --> 00:34:31,020
Det går tillbaka till Charlottes punkt tidigare:

446
00:34:31,020 --> 00:34:38,699
varför har vi denna huvud också?

447
00:34:38,699 --> 00:34:42,110
Är det vettigt nu, Charlotte? >> Typ av.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Typ av? Så vad hände när vi ur kön?

449
00:34:47,500 --> 00:34:54,340
Vad gjorde huvudet göra det nu är intressant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Åh, eftersom det ändrats - okej. Jag förstår.

451
00:34:56,449 --> 00:35:02,090
Eftersom huvudet - där huvudet pekar på förändringar i termer av platsen.

452
00:35:02,090 --> 00:35:07,200
Det är inte längre alltid noll index en. >> Ja, exakt.

453
00:35:07,200 --> 00:35:17,660
Det som hände var om avköande hög elementet

454
00:35:17,660 --> 00:35:20,590
gjordes och vi hade inte detta huvud område

455
00:35:20,590 --> 00:35:26,880
eftersom vi alltid ringa denna sträng på 0-index i spetsen för vår kö,

456
00:35:26,880 --> 00:35:30,170
då vi skulle behöva flytta resten av kön ner.

457
00:35:30,170 --> 00:35:36,010
Vi skulle behöva flytta "bye" från strängar [1] till strängarna [0].

458
00:35:36,010 --> 00:35:38,760
Och strängar [2] ner till strängar [1].

459
00:35:38,760 --> 00:35:43,050
Och vi skulle behöva göra detta för hela listan av element,

460
00:35:43,050 --> 00:35:45,110
hela matrisen av element.

461
00:35:45,110 --> 00:35:50,490
Och när vi gör detta med en matris blir det verkligen dyrt.

462
00:35:50,490 --> 00:35:53,340
Så här är det inte en stor sak. Vi har bara tre element i vår array.

463
00:35:53,340 --> 00:35:57,230
Men om vi hade en kö av tusen element eller en miljon delar,

464
00:35:57,230 --> 00:36:00,060
och sedan helt plötsligt, vi börja göra en massa dequeue kallar alla i en slinga,

465
00:36:00,060 --> 00:36:03,930
saker verkligen kommer att sakta ner eftersom det skiftar ned allt hela tiden.

466
00:36:03,930 --> 00:36:07,320
Du vet, flytta med 1, skift med 1, skift med 1, skift med 1.

467
00:36:07,320 --> 00:36:13,650
Istället använder vi detta huvud, vi kallar det en "pekare" även om det egentligen inte en pekare

468
00:36:13,650 --> 00:36:16,430
i egentlig mening, det är inte en pekare typ.

469
00:36:16,430 --> 00:36:19,410
Det är inte en int * eller char * eller nåt sånt.

470
00:36:19,410 --> 00:36:28,930
Men det pekar eller visar huvudet av vår kö. Ja?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Hur dequeue vet att bara lossna allt som är i spetsen?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Hur dequeue vet hur man lossna allt är på huvudet? >> Just, ja.

473
00:36:43,620 --> 00:36:49,050
>> Vad det tittar på är precis vad huvudet är inställt på.

474
00:36:49,050 --> 00:36:52,710
Så i detta första fall om vi ser här,

475
00:36:52,710 --> 00:36:55,690
vårt huvud är 0, index 0. >> Höger.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Så det bara säger okej, ja, elementet vid index 0, strängen "Hej",

477
00:37:00,500 --> 00:37:03,050
är det element i toppen av vår kö.

478
00:37:03,050 --> 00:37:05,570
Så vi kommer att avköa den killen.

479
00:37:05,570 --> 00:37:09,800
Och det kommer att vara den faktor som får returneras till anroparen.

480
00:37:09,800 --> 00:37:14,540
Ja, Saad? >> Så huvudet sätter grunden - där du kommer att indexera den?

481
00:37:14,540 --> 00:37:17,750
Det är början på den? >> Ja. >> Okej.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Det är att bli den nya start för vår grupp.

483
00:37:22,900 --> 00:37:28,930
Så när du avköa något, allt du behöver göra åt elementet vid index q.head,

484
00:37:28,930 --> 00:37:32,240
och det kommer att vara det element som du vill avköa.

485
00:37:32,240 --> 00:37:34,930
Du måste också för att minska det stora.

486
00:37:34,930 --> 00:37:39,430
Vi får se i lite där det blir lite knepigt med detta.

487
00:37:39,430 --> 00:37:46,520
Vi avköa, och nu, om vi köa igen,

488
00:37:46,520 --> 00:37:51,300
var ska köa vi?

489
00:37:51,300 --> 00:37:55,000
Vart går nästa element i vår kö?

490
00:37:55,000 --> 00:37:57,980
Säg att vi vill köa strängen "CS".

491
00:37:57,980 --> 00:38:02,240
I vilken index kommer det att gå? [Studenter] Strings [2]. >> Två.

492
00:38:02,240 --> 00:38:04,980
Varför 2 och inte 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] För nu huvudet 1, så det är som i början av listan?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Höger. Och vad betyder slutet på listan?

495
00:38:21,220 --> 00:38:23,290
Vad vi använder för att beteckna slutet av vår kö?

496
00:38:23,290 --> 00:38:25,970
Huvudet är chef för vår kö, i början av vår kö.

497
00:38:25,970 --> 00:38:29,530
Vad är slutet på vår kö? [Studenter] storlek. >> Storlek, exakt.

498
00:38:29,530 --> 00:38:36,360
Så våra nya element går in på storlek, och de element som vi tar bort lossna på huvudet.

499
00:38:36,360 --> 00:38:45,390
När vi köa nästa element, vi sätter den på storlek.

500
00:38:45,390 --> 00:38:48,530
[Student] Innan du sätter det i var dock storlek 1, eller hur?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Höger. Så inte riktigt på storlek. Storlek +, inte +1, men + huvud.

502
00:38:55,690 --> 00:38:59,990
Eftersom vi skiftade allt i huvudet belopp.

503
00:38:59,990 --> 00:39:14,270
Så här, nu har vi en kö av storlek 1 som börjar vid index 1.

504
00:39:14,270 --> 00:39:20,730
Svansen är index 2. Ja?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Vad händer när du dequeue strängar [0] och strängar "spåren i minnet

506
00:39:25,780 --> 00:39:29,420
bara få tömmas, i grund och botten, eller bara glömt?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ja. I denna mening, vi glömmer dem bara.

508
00:39:34,700 --> 00:39:42,640
Om vi ​​lagrar kopior av dem för -

509
00:39:42,640 --> 00:39:46,310
många datastrukturer kommer ofta lagra sina egna kopior av de element

510
00:39:46,310 --> 00:39:51,760
så att den person som ledde datastrukturen inte behöver oroa

511
00:39:51,760 --> 00:39:53,650
om var alla dessa pekare är på väg.

512
00:39:53,650 --> 00:39:56,000
Datastrukturen håller på att allt håller på att alla kopior,

513
00:39:56,000 --> 00:39:59,580
att se till att allt kvarstår på lämpligt sätt.

514
00:39:59,580 --> 00:40:03,140
Emellertid, i detta fall, dessa datastrukturer bara, för enkelhets skull,

515
00:40:03,140 --> 00:40:05,580
inte göra kopior av allt som vi lagrar i dem.

516
00:40:05,580 --> 00:40:08,630
[Student] Så är detta en kontinuerlig rad -? >> Ja.

517
00:40:08,630 --> 00:40:14,350
Om vi ​​ser tillbaka på vad definitionen var denna struktur är det.

518
00:40:14,350 --> 00:40:19,110
Det är bara en vanlig array som du har sett,

519
00:40:19,110 --> 00:40:24,280
en array av char * s..

520
00:40:24,280 --> 00:40:26,340
Betyder det -? >> Ja, jag undrar bara

521
00:40:26,340 --> 00:40:29,130
Om du så småningom slut på minne, i viss mån,

522
00:40:29,130 --> 00:40:32,330
Om du har alla dessa tomma platser i din array?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ja, det är en bra sak.

524
00:40:36,390 --> 00:40:41,530
>> Om vi ​​tittar på vad som har hänt nu på denna punkt,

525
00:40:41,530 --> 00:40:46,350
Vi har fyllt upp vår kö, ser det ut som.

526
00:40:46,350 --> 00:40:50,390
Men vi har inte riktigt fyllt upp vår kö

527
00:40:50,390 --> 00:40:57,710
eftersom vi har en kö som är storlek 2, men det börjar på index 1,

528
00:40:57,710 --> 00:41:02,160
eftersom det är där vårt huvud pekare är.

529
00:41:02,160 --> 00:41:08,400
Som du sa, att element vid strängar [0], vid index 0, är ​​inte riktigt där.

530
00:41:08,400 --> 00:41:10,450
Det är inte i vår kö längre.

531
00:41:10,450 --> 00:41:16,460
Vi bara inte brydde sig om att gå in och skriva över den när vi ur kön den.

532
00:41:16,460 --> 00:41:18,700
Så även om det ser ut som vi har slut på minne, har vi verkligen inte.

533
00:41:18,700 --> 00:41:23,270
Den platsen är tillgänglig för oss att använda.

534
00:41:23,270 --> 00:41:29,310
Den lämpligt beteende, om vi skulle försöka och första dequeue något

535
00:41:29,310 --> 00:41:34,420
liknande "bye", som skulle dyka bye av.

536
00:41:34,420 --> 00:41:38,460
Nu vår kö börjar på index 2 och är av storlek 1.

537
00:41:38,460 --> 00:41:42,240
Och nu när vi försöker köa något igen, säger 50,

538
00:41:42,240 --> 00:41:47,880
50 ska gå i denna plats vid index 0

539
00:41:47,880 --> 00:41:51,270
eftersom det är fortfarande tillgänglig för oss. Ja, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Händer som automatiskt?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Det händer inte helt automatiskt. Du måste göra matten

542
00:41:56,150 --> 00:42:00,380
att få det att fungera, men i huvudsak vad vi har gjort är att vi bara har virad runt.

543
00:42:00,380 --> 00:42:04,070
[Saad] Och är det okej om det har ett hål i mitten av det?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Det är om vi kan göra matten träna ordentligt.

545
00:42:08,720 --> 00:42:15,470
>> Och det visar sig att det är faktiskt inte så svårt att göra med mod operatören.

546
00:42:15,470 --> 00:42:20,040
Så precis som vi gjorde med Caesar och krypto grejer,

547
00:42:20,040 --> 00:42:25,190
med mod, kan vi få saker att linda runt och fortsätta

548
00:42:25,190 --> 00:42:28,090
runt och runt och runt med vår kö,

549
00:42:28,090 --> 00:42:32,180
hålla den framvisaren flyttar runt.

550
00:42:32,180 --> 00:42:38,840
Observera att storleken alltid respekterar antalet element faktiskt inom kön.

551
00:42:38,840 --> 00:42:43,110
Och det är bara huvudet pekare som håller cykling genom.

552
00:42:43,110 --> 00:42:49,660
Om vi ​​tittar på vad som hände här, om vi går tillbaka till början,

553
00:42:49,660 --> 00:42:55,020
och du bara titta vad som händer i huvudet

554
00:42:55,020 --> 00:42:58,240
När vi köa något hände ingenting på huvudet.

555
00:42:58,240 --> 00:43:00,970
När vi kö något annat, hände ingenting på huvudet.

556
00:43:00,970 --> 00:43:04,130
Snart vi ur kön något går huvudet med en.

557
00:43:04,130 --> 00:43:06,600
Vi kö något händer ingenting mot huvudet.

558
00:43:06,600 --> 00:43:11,060
När vi avköa något, huvudet plötsligt blir ökas.

559
00:43:11,060 --> 00:43:14,660
När vi köa något händer ingenting mot huvudet.

560
00:43:14,660 --> 00:43:20,240
>> Vad skulle hända på denna punkt om vi skulle avköa något igen?

561
00:43:20,240 --> 00:43:23,240
Några tankar? Vad skulle hända med huvudet?

562
00:43:23,240 --> 00:43:27,190
Vad ska hända med huvudet

563
00:43:27,190 --> 00:43:32,990
om vi skulle avköa något annat?

564
00:43:32,990 --> 00:43:35,400
Huvudet just nu är på index 2,

565
00:43:35,400 --> 00:43:38,920
vilket innebär att chefen för kön är strängar [2].

566
00:43:38,920 --> 00:43:44,280
[Student] som returnerar 0? >> Det borde gå tillbaka till 0. Den bör slå tillbaka runt, exakt.

567
00:43:44,280 --> 00:43:48,440
Hittills varje gång vi kallade dequeue har vi varit att lägga ett till huvudet,

568
00:43:48,440 --> 00:43:50,960
lägga till en till huvudet, lägga till en till huvudet, lägga till en till huvudet.

569
00:43:50,960 --> 00:43:58,400
Så snart den framvisaren kommer till sista index i vår grupp,

570
00:43:58,400 --> 00:44:05,650
då måste vi linda den tillbaka runt till början, gå tillbaka till 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Vad avgör kapacitet kön i en stack?

572
00:44:09,900 --> 00:44:13,120
[Hardison] I det här fallet har vi bara använt en # definierad konstant. >> Okej.

573
00:44:13,120 --> 00:44:19,590
[Hardison] I själva. C. fil kan du gå in och muck med det lite

574
00:44:19,590 --> 00:44:21,710
och göra det så stort eller så lite som du vill.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Så när du gör det till en kö, hur du gör datorn vet

576
00:44:25,310 --> 00:44:29,120
hur stor du vill att stapeln ska vara?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Det är en bra fråga.

578
00:44:31,700 --> 00:44:34,800
Det finns ett par olika sätt. En är att bara definiera det på framsidan

579
00:44:34,800 --> 00:44:42,050
och säga att detta kommer att bli en kö som har 4 element eller 50 element eller 10.000.

580
00:44:42,050 --> 00:44:45,430
Det andra sättet är att göra det som hackare utgåva folk gör

581
00:44:45,430 --> 00:44:52,310
och skapa funktioner för att få ditt kön att växa dynamiskt eftersom fler saker blir lagt in

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Så att gå med det första alternativet, vad syntax du använder

583
00:44:54,740 --> 00:44:57,830
att tala om för programmet vad är storleken på kön?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Så låt oss få ut av detta.

585
00:45:04,780 --> 00:45:12,650
Jag är fortfarande i stack.c här, så jag ska bara rulla upp till toppen här.

586
00:45:12,650 --> 00:45:17,920
Kan du se denna rätt här? Detta är den # define kapacitet 10.

587
00:45:17,920 --> 00:45:24,600
Och detta är nästan exakt samma syntax som vi har för kön.

588
00:45:24,600 --> 00:45:28,390
Utom i kö har vi att extra struct område här.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Åh, jag trodde kapaciteten innebar kapacitet för strängen.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Att det är den maximala längden av ordet. >> Uppfattat.

591
00:45:36,770 --> 00:45:41,180
Ja. Kapaciteten här - det är en stor punkt.

592
00:45:41,180 --> 00:45:44,000
Och detta är något som är svårt

593
00:45:44,000 --> 00:45:49,480
eftersom det vi har förklarat här är en rad char * s.

594
00:45:49,480 --> 00:45:52,770
En array av pekare.

595
00:45:52,770 --> 00:45:56,690
Detta är en uppsättning av tecken.

596
00:45:56,690 --> 00:46:01,690
Detta är förmodligen vad du har sett när du har att förklara dina buffertar för fil-I / O,

597
00:46:01,690 --> 00:46:06,840
när du har skapat strängar manuellt på stacken.

598
00:46:06,840 --> 00:46:09,090
Men vad vi har här är en rad char * s.

599
00:46:09,090 --> 00:46:13,400
Så det är en rad pekare.

600
00:46:13,400 --> 00:46:18,350
Egentligen, om vi zooma ut och vi tittar på vad som händer här

601
00:46:18,350 --> 00:46:23,140
i presentationen ser du att de faktiska element, teckendata

602
00:46:23,140 --> 00:46:26,180
lagras inte i matrisen i sig.

603
00:46:26,180 --> 00:46:42,690
Vad lagras i vår grupp här är pekare till teckendata.

604
00:46:42,690 --> 00:46:52,560
Okej. Så vi har sett hur storleken på kön är precis som med bunten,

605
00:46:52,560 --> 00:46:58,670
storleken respekterar alltid antalet element närvarande i kön.

606
00:46:58,670 --> 00:47:02,720
Efter att ha gjort 2 enqueues är storleken 2.

607
00:47:02,720 --> 00:47:07,110
Efter att ha gjort en dequeue storleken är nu 1.

608
00:47:07,110 --> 00:47:09,330
Efter att ha annan enqueue storleken är tillbaka upp till 2.

609
00:47:09,330 --> 00:47:12,340
Så storleken respekterar definitivt antalet element i kön,

610
00:47:12,340 --> 00:47:15,580
och sedan huvudet blir bara cykling.

611
00:47:15,580 --> 00:47:20,210
Det går från 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Och varje gång vi kallar dequeue, blir framvisaren ökas till nästa index.

613
00:47:25,620 --> 00:47:29,930
Och om huvudet är på väg att gå över, loopar tillbaka runt till 0.

614
00:47:29,930 --> 00:47:34,870
Så med det, kan vi skriva dequeue funktionen.

615
00:47:34,870 --> 00:47:40,200
Och vi kommer att lämna enqueue funktionen för er att genomföra i stället.

616
00:47:40,200 --> 00:47:45,880
>> När vi avköa ett element ur vår kö,

617
00:47:45,880 --> 00:47:55,490
vad var det första som Daniel gjorde när vi började skriva pop funktion för stackar?

618
00:47:55,490 --> 00:48:00,490
Låt mig höra från någon som inte har talat ännu.

619
00:48:00,490 --> 00:48:06,710
Låt oss se, Saad, minns du vad Daniel gjorde som första sak när han skrev pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Det var, var det - >> Han testade för något.

621
00:48:08,860 --> 00:48:12,140
[Saad] Om storleken är större än 0. >> Exakt.

622
00:48:12,140 --> 00:48:14,390
Och vad var det testning för?

623
00:48:14,390 --> 00:48:19,090
[Saad] Det testade för att se om det finns något inuti matrisen.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ja. Exakt. Så du kan inte pop ut något av stapeln om det är tomt.

625
00:48:23,210 --> 00:48:26,510
På samma sätt kan du avköa inte något från en kö om det är tomt.

626
00:48:26,510 --> 00:48:30,420
Vad är det första vi ska göra i vår dequeue funktion här, tror du?

627
00:48:30,420 --> 00:48:33,860
[Saad] Om storleken är större än 0? >> Ja.

628
00:48:33,860 --> 00:48:37,710
I det här fallet har jag faktiskt bara testat att se om det är 0.

629
00:48:37,710 --> 00:48:42,240
Om det är 0, kan vi återvända null.

630
00:48:42,240 --> 00:48:45,280
Men exakt samma logik.

631
00:48:45,280 --> 00:48:49,110
Och låt oss fortsätta med detta.

632
00:48:49,110 --> 00:48:54,600
Om storleken inte är 0, där är det element som vi vill avköa?

633
00:48:54,600 --> 00:48:58,550
[Saad] På huvudet? >> Exakt.

634
00:48:58,550 --> 00:49:01,720
Vi kan bara dra ut det första elementet i vår kö

635
00:49:01,720 --> 00:49:07,040
genom att gå till elementet på huvudet.

636
00:49:07,040 --> 00:49:14,630
Inget galen.

637
00:49:14,630 --> 00:49:19,620
Efter det, vad ska vi göra? Vad måste hända?

638
00:49:19,620 --> 00:49:23,740
Vad var den andra saken som vi talade om i dequeue?

639
00:49:23,740 --> 00:49:28,130
Två saker måste hända, eftersom vår kö har förändrats.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Minska storleken. >> Vi måste minska storleken och öka huvudet? Exakt.

641
00:49:35,640 --> 00:49:40,600
För att öka huvudet, kan vi inte bara blint öka huvudet, minns.

642
00:49:40,600 --> 00:49:45,080
Vi kan inte bara göra queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Vi måste även inkludera denna mod av kapaciteten.

644
00:49:51,630 --> 00:49:54,740
Och varför mod vi av kapaciteten, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Eftersom det har att slå runt. >> Exakt.

646
00:49:58,680 --> 00:50:04,750
Vi mod genom förmågan eftersom det har att svepa tillbaka runt till 0.

647
00:50:04,750 --> 00:50:07,400
Så nu, i det här läget kan vi göra vad Daniel sa.

648
00:50:07,400 --> 00:50:12,700
Vi kan dekrementera storlek.

649
00:50:12,700 --> 00:50:29,170
Och då kan vi bara tillbaka det element som var på toppen av kön.

650
00:50:29,170 --> 00:50:34,000
Det ser typ av gnarly först. Du kanske har en fråga. Ursäkta?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Varför är först vid toppen av kön? Vart går det?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Den kommer från den fjärde raden från botten.

653
00:50:42,480 --> 00:50:46,060
Efter att vi testar att se till att vår kö inte är tom,

654
00:50:46,060 --> 00:50:54,100
Vi drar ut char * först, dra vi ut det element som sitter på huvudet index

655
00:50:54,100 --> 00:50:58,680
vår grupp, vår strängar array, >> och samtal som först?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Och vi kallar det först. Ja.

657
00:51:04,500 --> 00:51:09,850
Bara för att följa upp det, varför tror du att vi var tvungna att göra det?

658
00:51:09,850 --> 00:51:18,270
[Sam] Varje första är bara tillbaka q.strings [q.head]? >> Ja.

659
00:51:18,270 --> 00:51:23,830
>> Eftersom vi gör detta byte av q.head Med MOD-funktionen,

660
00:51:23,830 --> 00:51:27,810
och det finns inget sätt att göra det inom returledningen också.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exakt. Du är plats på. Sam är plats helt på.

662
00:51:31,640 --> 00:51:36,800
Anledningen till att vi var tvungna att dra ut det första elementet i vår kö och lagra den i en variabel

663
00:51:36,800 --> 00:51:43,030
beror denna linje där vi bara hade q.head,

664
00:51:43,030 --> 00:51:47,030
finns det mod operatören i det är inte något som vi kan göra

665
00:51:47,030 --> 00:51:51,230
och har tar det effekt på huvudet utan - på en rad.

666
00:51:51,230 --> 00:51:54,480
Så vi har faktiskt dra ut det första elementet och justera huvudet,

667
00:51:54,480 --> 00:52:00,430
justera storleken och sedan tillbaka det element som vi drog ut.

668
00:52:00,430 --> 00:52:02,680
Och detta är något som vi får se komma senare med

669
00:52:02,680 --> 00:52:04,920
länkade listor, som vi leka med dem.

670
00:52:04,920 --> 00:52:08,410
Ofta när du frigör eller göra sig av länkade listor

671
00:52:08,410 --> 00:52:13,500
du behöver komma ihåg nästa element, nästa pekare för en länkad lista

672
00:52:13,500 --> 00:52:16,330
innan du kasserar den nuvarande.

673
00:52:16,330 --> 00:52:23,580
Eftersom annars kasta bort information om vad som finns kvar i listan.

674
00:52:23,580 --> 00:52:34,160
Nu, om du går till din apparat, öppnar du upp queue.c--x av detta.

675
00:52:34,160 --> 00:52:39,390
Så om jag öppnar queue.c, låt mig zooma in här,

676
00:52:39,390 --> 00:52:44,970
du ser att du har en liknande utseende fil.

677
00:52:44,970 --> 00:52:49,200
Liknande utseende fil till vad vi hade tidigare med stack.c.

678
00:52:49,200 --> 00:52:54,690
Vi har vår struct för kön definieras på samma sätt som vi såg på bilderna.

679
00:52:54,690 --> 00:52:59,870
>> Vi har vår enqueue funktion som är till för dig att göra.

680
00:52:59,870 --> 00:53:04,340
Och vi har dequeue funktion här.

681
00:53:04,340 --> 00:53:06,870
Den dequeue funktion i filen ogenomförda,

682
00:53:06,870 --> 00:53:13,230
men jag ska lägga tillbaka upp på PowerPoint så att du kan skriva in det, om du vill.

683
00:53:13,230 --> 00:53:16,690
Så för de kommande 5 minuter eller så, ni arbeta enqueue

684
00:53:16,690 --> 00:53:22,570
vilket är nästan precis motsatsen till avköande.

685
00:53:22,570 --> 00:53:29,560
Du behöver inte justera huvudet när du enqueueing, men vad du behöva justera?

686
00:53:29,560 --> 00:53:38,920
Storlek. Så när du enqueue förblir huvudet orörda, blir storleken ändras.

687
00:53:38,920 --> 00:53:46,920
Men det tar lite - du måste leka med den mod

688
00:53:46,920 --> 00:53:57,560
att räkna ut exakt vad indexet det nya elementet ska läggas till.

689
00:53:57,560 --> 00:54:03,080
Så jag ska ge er lite, sätta avköa tillbaka upp på bilden,

690
00:54:03,080 --> 00:54:05,200
och eftersom ni har frågor, skriker ut dem så att vi kan

691
00:54:05,200 --> 00:54:09,220
alla talar om dem som en grupp.

692
00:54:09,220 --> 00:54:13,960
Även med den storlek du inte - när du justerar storleken, kan du alltid bara -

693
00:54:13,960 --> 00:54:18,720
behöver du mod storlek någonsin? [Daniel] Nej >> Du behöver inte mod storlek, rätt.

694
00:54:18,720 --> 00:54:24,260
Eftersom storleken alltid, om Du är - förutsatt att du hantera saker på rätt sätt,

695
00:54:24,260 --> 00:54:30,840
storleken kommer alltid att vara mellan 0 och 3.

696
00:54:30,840 --> 00:54:38,680
Vart har du att mod när du gör enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Endast för huvudet. >> Endast för huvudet, precis.

698
00:54:41,060 --> 00:54:44,620
Och varför har du att mod alls enqueue?

699
00:54:44,620 --> 00:54:48,830
När är en situation där du måste mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Om du har grejer på utrymmen, som på utrymmen 1 och 2,

701
00:54:53,630 --> 00:54:55,950
och sedan behöver lägga till något till 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ja, exakt. Så om ditt huvud pekaren är i slutet,

703
00:55:02,570 --> 00:55:14,210
eller om din storlek plus huvudet är större, eller snarare kommer att linda runt kön.

704
00:55:14,210 --> 00:55:17,830
>> Så i denna situation som vi har här uppe på bilden just nu,

705
00:55:17,830 --> 00:55:24,370
om jag vill köa något just nu,

706
00:55:24,370 --> 00:55:31,110
Vi vill köa något på index 0.

707
00:55:31,110 --> 00:55:35,450
Så om du tittar på var 50 går, och jag kallar enqueue 50,

708
00:55:35,450 --> 00:55:40,840
det går ner där på botten. Det går i index 0.

709
00:55:40,840 --> 00:55:44,160
Den ersätter "hej" som redan ur kön.

710
00:55:44,160 --> 00:55:46,210
[Daniel] du inte ta hand om det i dequeue redan?

711
00:55:46,210 --> 00:55:50,550
Varför gör det något med huvudet i enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Åh, så du inte ändrar huvudet, tyvärr.

713
00:55:55,770 --> 00:56:02,310
Men du måste använda mod användaren när du öppnar

714
00:56:02,310 --> 00:56:04,250
det element som du vill köa när du öppnar

715
00:56:04,250 --> 00:56:06,960
nästa element i kön.

716
00:56:06,960 --> 00:56:10,960
[Basil] Jag gjorde inte det, och jag fick "framgång" på det.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Åh, jag förstår vad du säger.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Så du didn't - du gjorde på q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Ja. Jag bytt sida, gjorde jag ingenting med huvudet.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Du egentligen inte behöver återställa huvudet vara något,

721
00:56:24,300 --> 00:56:31,650
men när du index till strängar array,

722
00:56:31,650 --> 00:56:39,500
har du faktiskt gå vidare och beräkna var nästa elementet är,

723
00:56:39,500 --> 00:56:44,230
eftersom withe bunten, var nästa element i din stack alltid

724
00:56:44,230 --> 00:56:48,740
vid indexet som motsvarar storleken.

725
00:56:48,740 --> 00:56:55,850
Om vi ​​ser tillbaka på vårt stack push-funktion,

726
00:56:55,850 --> 00:57:03,100
vi kan alltid plunk i vår nya inslag höger vid index storlek.

727
00:57:03,100 --> 00:57:06,710
Medan med kön, kan vi inte göra det

728
00:57:06,710 --> 00:57:10,340
för om vi är på denna situation,

729
00:57:10,340 --> 00:57:18,130
om vi kö 50 vår nya sträng skulle gå rätt på strängar [1]

730
00:57:18,130 --> 00:57:20,540
som vi inte vill göra.

731
00:57:20,540 --> 00:57:41,200
Vi vill ha den nya strängen går vid index 0.

732
00:57:41,200 --> 00:57:44,320
>> Är det någon - ja? [Student] Jag har en fråga, men det är inte riktigt närstående.

733
00:57:44,320 --> 00:57:48,160
Vad betyder det när någon bara ringer något liknande pred pekare?

734
00:57:48,160 --> 00:57:51,260
Vad är det namnet kort för? Jag vet att det är bara ett namn.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred pekare? Låt oss se. I vilket sammanhang?

736
00:57:59,110 --> 00:58:01,790
[Student] Det var för insatsen. Jag kan fråga dig senare om du vill

737
00:58:01,790 --> 00:58:03,920
eftersom det inte är riktigt relaterade, men jag -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Från Davids insats kod från föreläsning?

739
00:58:07,300 --> 00:58:10,860
Vi kan dra upp det och prata om det.

740
00:58:10,860 --> 00:58:15,550
Vi pratar om det nästa gång vi kommer till länkade listor.

741
00:58:15,550 --> 00:58:21,440
>> Så låt oss verkligen snabbt titta på vad enqueue funktionen ser ut.

742
00:58:21,440 --> 00:58:26,530
Vad var det första som folk försökt göra i ditt enqueue linje? In i denna kö?

743
00:58:26,530 --> 00:58:29,960
Liknar det du gjorde för stack trycka.

744
00:58:29,960 --> 00:58:32,080
Vad gjorde du, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, obegripligt]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exakt. Om (q.size == KAPACITET) -

747
00:58:45,700 --> 00:58:54,720
Jag måste lägga min tandställning på rätt plats - returnera false.

748
00:58:54,720 --> 00:59:01,370
Zooma in lite. Okej.

749
00:59:01,370 --> 00:59:03,800
Nu vad är nästa sak som vi var tvungna att göra?

750
00:59:03,800 --> 00:59:11,370
Precis som med stacken, och sätts på rätt plats.

751
00:59:11,370 --> 00:59:16,010
Och så vad var det rätt plats att infoga det?

752
00:59:16,010 --> 00:59:23,170
Med stapeln var det index storlek, med detta är det inte riktigt så.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Jag har q.head--eller - >> q.strings? >> Ja.

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 vill nog sätta parentes kring detta

756
00:59:42,740 --> 00:59:48,830
så att vi får rätt prioritet och så det är cleart för alla.

757
00:59:48,830 --> 00:59:55,800
Och ställa det lika? >> Till str? >> Till str. Jättebra.

758
00:59:55,800 --> 01:00:00,160
Och nu vad är det sista som vi måste göra?

759
01:00:00,160 --> 01:00:06,780
Precis som vi gjorde i stacken. >> Inkrementera storlek? >> Inkrementera storlek.

760
01:00:06,780 --> 01:00:13,830
Boom. Och sedan, eftersom startmotorn koden just återvänt falsk som standard,

761
01:00:13,830 --> 01:00:27,460
Vi vill ändra detta till true om allt går igenom och allt går bra.

762
01:00:27,460 --> 01:00:33,050
Okej. Det är en hel del information för avsnitt.

763
01:00:33,050 --> 01:00:39,480
Vi är inte riktigt över. Vi vill prata verkligen snabbt om enstaka-länkade listor.

764
01:00:39,480 --> 01:00:44,010
Jag lägger upp detta så att vi kan gå tillbaka till det senare.

765
01:00:44,010 --> 01:00:50,850
Men låt oss gå tillbaka till vår presentation för några fler bilder.

766
01:00:50,850 --> 01:00:53,790
Så enqueue är TODO, nu har vi gjort det.

767
01:00:53,790 --> 01:00:57,430
>> Nu ska vi ta en titt på enstaka-länkade listor.

768
01:00:57,430 --> 01:01:00,040
Vi pratade om dessa lite mer i föreläsningen.

769
01:01:00,040 --> 01:01:02,540
Hur många av er såg demonstrationen där vi hade folk

770
01:01:02,540 --> 01:01:08,220
tafatt pekar på varandra och hålla tal? >> Jag var i den.

771
01:01:08,220 --> 01:01:16,620
>> Vad ni tycker? Gjorde det, förhoppningsvis avmystifiera dessa lite?

772
01:01:16,620 --> 01:01:25,990
Med en lista, visar det sig att vi tar itu med den här typen som vi kommer att kalla en nod.

773
01:01:25,990 --> 01:01:32,520
Medan med kön och stapeln hade vi structs att vi skulle kalla kö i stacken,

774
01:01:32,520 --> 01:01:34,860
Vi hade dessa nya kö i stack typer,

775
01:01:34,860 --> 01:01:39,240
Här en lista egentligen bara består av ett gäng noder.

776
01:01:39,240 --> 01:01:45,920
På samma sätt som strängar är bara en massa tecken alla uppradade bredvid varandra.

777
01:01:45,920 --> 01:01:50,650
En länkad lista är bara en nod och en annan nod och en annan nod och en annan nod.

778
01:01:50,650 --> 01:01:55,080
Och snarare än att krossa alla noder tillsammans och lagra dem intill varandra

779
01:01:55,080 --> 01:01:58,090
allt intill varandra i minnet,

780
01:01:58,090 --> 01:02:04,470
ha detta nästa pekare tillåter oss att lagra noderna var som helst, på måfå.

781
01:02:04,470 --> 01:02:10,500
Och sedan typ av tråd dem alla tillsammans för att peka från en till nästa.

782
01:02:10,500 --> 01:02:15,850
>> Och vad var den stora fördelen att det hade över en array?

783
01:02:15,850 --> 01:02:21,680
Under lagring allt intill varandra bara fastnat bredvid varandra?

784
01:02:21,680 --> 01:02:24,190
Du minns? Ja? >> Dynamisk minnesallokering?

785
01:02:24,190 --> 01:02:27,220
>> Dynamisk minnesallokering i vilken mening?

786
01:02:27,220 --> 01:02:31,780
[Student] I att du kan fortsätta att göra det större och du behöver inte flytta hela din uppsättning?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exakt. Så med en array, när du vill sätta ett nytt element i mitten av det,

788
01:02:40,940 --> 01:02:45,320
du måste flytta allt för att göra plats.

789
01:02:45,320 --> 01:02:47,880
Och som vi pratade om med kön,

790
01:02:47,880 --> 01:02:50,080
det är därför vi hålla det framvisaren,

791
01:02:50,080 --> 01:02:52,050
så att vi inte ständigt skiftande saker.

792
01:02:52,050 --> 01:02:54,520
Därför att blir dyrt om du har en stor uppsättning

793
01:02:54,520 --> 01:02:57,130
och du ständigt gör dessa slumpmässiga infogningar.

794
01:02:57,130 --> 01:03:00,820
Medan med en lista, allt du behöver göra kasta det på en ny nod,

795
01:03:00,820 --> 01:03:06,330
justera tips, och du är klar.

796
01:03:06,330 --> 01:03:10,940
Vad suger om det här?

797
01:03:10,940 --> 01:03:16,830
Bortsett från det faktum att det är inte så lätt att arbeta med som en array? Ja?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Tja, jag antar att det är mycket svårare att komma åt ett specifikt element i den länkade listan?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Du kan inte bara hoppa till en godtycklig element i mitten av länkad lista.

800
01:03:30,470 --> 01:03:33,800
Hur har du att göra det i stället? >> Du måste gå igenom hela saken.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ja. Du måste gå igenom en i taget, en i taget.

802
01:03:35,660 --> 01:03:38,480
Det är en enorm - det är en smärta.

803
01:03:38,480 --> 01:03:41,550
Vad är den andra - det finns en annan undergång till detta.

804
01:03:41,550 --> 01:03:45,340
[Basil] Du kan inte gå framåt och bakåt? Du måste gå en riktning?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ja. Så hur löser vi det, ibland?

806
01:03:48,570 --> 01:03:53,370
[Basil] Dubbelt band listor? >> Exakt. Det finns dubbelt länkade listor.

807
01:03:53,370 --> 01:03:55,540
Det finns också - ledsen?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Är det samma som att använda Pred sak som -

809
01:03:57,620 --> 01:04:01,090
Jag tänkte bara, är inte det vad det pred sak är?

810
01:04:01,090 --> 01:04:05,850
Är inte det i mellan dubbelt och var för sig?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Låt oss titta på vad exakt han gjorde.

812
01:04:10,020 --> 01:04:15,760
Så här går vi. Här är listan koden.

813
01:04:15,760 --> 01:04:25,620
Här har vi predptr, här. Är detta vad du pratade om?

814
01:04:25,620 --> 01:04:30,750
Så detta var - han befria en lista och han försöker att lagra en pekare till det.

815
01:04:30,750 --> 01:04:35,000
Detta är inte dubbelt, enstaka länkade-listor.

816
01:04:35,000 --> 01:04:40,090
Vi kan prata mer om detta senare eftersom detta talar om att frigöra listan

817
01:04:40,090 --> 01:04:42,900
och jag vill visa några andra saker först.

818
01:04:42,900 --> 01:04:51,480
men det är bara - det är att komma ihåg värdet av PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, det föregående pekare? >> Ja.

820
01:04:54,170 --> 01:05:04,070
Så att vi sedan kan öka PTR själv innan vi sedan fri vad predptr är.

821
01:05:04,070 --> 01:05:09,130
Eftersom vi inte kan fritt PTR och sedan ringa PTR = PTR nästa, eller hur?

822
01:05:09,130 --> 01:05:11,260
Det skulle vara dåligt.

823
01:05:11,260 --> 01:05:20,940
Så låt oss se, tillbaka till den här killen.

824
01:05:20,940 --> 01:05:23,900
>> Den andra dåliga listor är att medan med en array

825
01:05:23,900 --> 01:05:26,520
Vi har bara alla element själva staplade bredvid varandra,

826
01:05:26,520 --> 01:05:29,050
Här har vi också infört denna pekare.

827
01:05:29,050 --> 01:05:34,060
Så det finns en ytterligare bit av minne som vi behöva använda

828
01:05:34,060 --> 01:05:37,910
för varje element som vi lagrar i vår lista.

829
01:05:37,910 --> 01:05:40,030
Vi får flexibilitet, men det kommer till en kostnad.

830
01:05:40,030 --> 01:05:42,230
Den levereras med denna tid kostnad,

831
01:05:42,230 --> 01:05:45,270
och det kommer med detta minne kostar också.

832
01:05:45,270 --> 01:05:47,800
Tid i den meningen att vi nu måste gå igenom varje element i arrayen

833
01:05:47,800 --> 01:05:58,670
att hitta en på index 10, eller som skulle ha varit index 10 i en array.

834
01:05:58,670 --> 01:06:01,230
>> Bara riktigt snabbt, när vi diagram ut dessa listor,

835
01:06:01,230 --> 01:06:05,980
vanligtvis vi håller fast vid huvudet av listan eller den första pekaren i listan

836
01:06:05,980 --> 01:06:08,010
och notera att detta är en sann pekare.

837
01:06:08,010 --> 01:06:11,100
Det är bara 4 byte. Det är inte en verklig nod själv.

838
01:06:11,100 --> 01:06:17,120
Så du ser att den inte har int värde i det, ingen nästa pekare i den.

839
01:06:17,120 --> 01:06:20,790
Det är bokstavligen bara en pekare.

840
01:06:20,790 --> 01:06:23,550
Det kommer att peka på något som är en verklig nod struct.

841
01:06:23,550 --> 01:06:28,480
[Sam] En pekare som kallas nod? >> Det här är - nej. Detta är en pekare till något av typ nod.

842
01:06:28,480 --> 01:06:32,540
Det är en pekare till en nod struct. >> Åh, okej.

843
01:06:32,540 --> 01:06:36,870
Diagrammet till vänster, kod till höger.

844
01:06:36,870 --> 01:06:42,190
Vi kan ställa in den till noll, vilket är ett bra sätt att börja.

845
01:06:42,190 --> 01:06:49,850
När du diagrammet, skriver du antingen det som null eller du lägger en linje genom det så.

846
01:06:49,850 --> 01:06:53,910
>> Ett av de enklaste sätten att arbeta med listor,

847
01:06:53,910 --> 01:06:57,430
och vi ber er göra både prefix och lägg se skillnaderna mellan de två,

848
01:06:57,430 --> 01:07:01,320
men prepending är definitivt lättare.

849
01:07:01,320 --> 01:07:05,790
När du lägger du, det är här du - när du prepend (7),

850
01:07:05,790 --> 01:07:10,050
du går och skapa noden struct

851
01:07:10,050 --> 01:07:13,870
och du först peka på den, för nu, eftersom vi till före det,

852
01:07:13,870 --> 01:07:17,240
det kommer att bli i början av listan.

853
01:07:17,240 --> 01:07:22,540
Om vi ​​prepend (3), som skapar en annan nod, men nu 3 kommer före 7.

854
01:07:22,540 --> 01:07:31,130
Så vi huvudsakligen driver saker på vår lista.

855
01:07:31,130 --> 01:07:34,720
Nu kan du se att prepend, ibland människor kallar det skjuta,

856
01:07:34,720 --> 01:07:39,600
eftersom du driver ett nytt element på din lista.

857
01:07:39,600 --> 01:07:43,270
Det är också lätt att ta bort på framsidan av en lista.

858
01:07:43,270 --> 01:07:45,650
Så att folk kommer ofta kalla det pop.

859
01:07:45,650 --> 01:07:52,200
Och på det sättet kan du emulera en bunt med en länkad lista.

860
01:07:52,200 --> 01:07:57,880
Hoppsan. Tyvärr, nu vi får in append. Så här har vi till före (7), nu har vi prepend (3).

861
01:07:57,880 --> 01:08:02,600
Om vi ​​till före något annat på denna lista, om vi till före (4),

862
01:08:02,600 --> 01:08:06,540
då skulle vi ha 4 och sedan 3 och sedan 7.

863
01:08:06,540 --> 01:08:14,220
Så vi kunde pop och ta bort 4, ta bort 3, ta bort 7.

864
01:08:14,220 --> 01:08:16,500
Ofta mer intuitivt sätt att tänka på detta är med append.

865
01:08:16,500 --> 01:08:20,310
Så jag har schematiskt vad det skulle se ut med lägga här.

866
01:08:20,310 --> 01:08:23,380
Här bifogas (7) inte ser något annorlunda

867
01:08:23,380 --> 01:08:25,160
eftersom det finns bara ett element i listan.

868
01:08:25,160 --> 01:08:28,620
Och bifoga (3) uttrycker det på slutet.

869
01:08:28,620 --> 01:08:31,020
Kanske kan du se just nu tricket med append

870
01:08:31,020 --> 01:08:36,600
är att eftersom vi bara vet var i början av listan är,

871
01:08:36,600 --> 01:08:39,450
som ska läggas till en lista måste du gå hela vägen igenom listan

872
01:08:39,450 --> 01:08:46,500
för att komma till slutet, stoppa sedan bygga din nod och Plunk allt.

873
01:08:46,500 --> 01:08:50,590
Koppla alla grejer upp.

874
01:08:50,590 --> 01:08:55,170
Så med prepend, som vi slet bara genom detta verkligen snabbt,

875
01:08:55,170 --> 01:08:58,170
när du lägger du till en lista, det är ganska enkelt.

876
01:08:58,170 --> 01:09:02,960
>> Du gör din nya nod innebära några dynamisk minnesallokering.

877
01:09:02,960 --> 01:09:09,830
Så här gör vi en nod struct med malloc.

878
01:09:09,830 --> 01:09:14,710
Så malloc vi använder eftersom det kommer att avsätta minne för oss för senare

879
01:09:14,710 --> 01:09:20,350
eftersom vi inte vill att detta - vi vill detta minne för att bestå under en lång tid.

880
01:09:20,350 --> 01:09:25,350
Och vi får en pekare till utrymme i minnet att vi bara tilldelade.

881
01:09:25,350 --> 01:09:29,260
Vi använder storlek nod blir slutsumman vi inte fälten.

882
01:09:29,260 --> 01:09:31,899
Vi inte manuellt generera antalet byte,

883
01:09:31,899 --> 01:09:39,750
istället använder vi sizeof så att vi vet att vi får rätt antal byte.

884
01:09:39,750 --> 01:09:43,660
Vi ser till att testa att våra malloc samtal lyckades.

885
01:09:43,660 --> 01:09:47,939
Detta är något du vill göra i allmänhet.

886
01:09:47,939 --> 01:09:52,590
På moderna maskiner, slut på minne är inte något som är lätt

887
01:09:52,590 --> 01:09:56,610
om du inte är fördela massor av saker och göra en enorm lista,

888
01:09:56,610 --> 01:10:02,220
men om du bygger saker för, säg, som en iPhone eller en Android,

889
01:10:02,220 --> 01:10:05,230
du har begränsade minnesresurser, speciellt om du gör något intensiv.

890
01:10:05,230 --> 01:10:08,300
Så det är bra att komma i praktiken.

891
01:10:08,300 --> 01:10:10,510
>> Observera att jag använt ett par olika funktioner här

892
01:10:10,510 --> 01:10:12,880
att du har sett som är typ av nya.

893
01:10:12,880 --> 01:10:15,870
Så fprintf är precis printf

894
01:10:15,870 --> 01:10:21,320
utom det första argumentet är den ström som du vill skriva ut.

895
01:10:21,320 --> 01:10:23,900
I det här fallet vill vi skriva ut till standard fel strängen

896
01:10:23,900 --> 01:10:29,410
som skiljer sig från den vanliga outstream.

897
01:10:29,410 --> 01:10:31,620
Som standard visas upp på samma plats.

898
01:10:31,620 --> 01:10:34,600
Den skriver också ut till terminalen, men du kan -

899
01:10:34,600 --> 01:10:38,790
använder dessa kommandon du lärt dig om de omdirigering teknik

900
01:10:38,790 --> 01:10:42,290
du lärt dig om i Tommys video för problembild 4 kan du styra den

901
01:10:42,290 --> 01:10:47,900
till olika områden, och sedan avsluta, just här, avslutar ditt program.

902
01:10:47,900 --> 01:10:50,440
Det är i huvudsak som återvänder från centrala,

903
01:10:50,440 --> 01:10:53,600
utom vi använder exit för här avkastning inte kommer att göra något.

904
01:10:53,600 --> 01:10:57,140
Vi är inte i main, inte avsluta så återvänder inte programmet som vi vill ha.

905
01:10:57,140 --> 01:11:03,020
Så använder vi avfarten funktionen och ge den en felkod.

906
01:11:03,020 --> 01:11:11,890
Så här vi satt den nya noden värde fältet, dess Jag fältet vara lika med i, och vi koppla upp det.

907
01:11:11,890 --> 01:11:15,530
Vi sätter den nya noden nästa pekare att peka på först,

908
01:11:15,530 --> 01:11:20,460
och sedan först kommer nu pekar på den nya noden.

909
01:11:20,460 --> 01:11:25,120
Dessa första rader kod, vi bygger faktiskt den nya noden.

910
01:11:25,120 --> 01:11:27,280
Inte de två sista raderna i denna funktion, men de första.

911
01:11:27,280 --> 01:11:30,290
Du kan faktiskt dra ut i en funktion, till en hjälpare funktion.

912
01:11:30,290 --> 01:11:32,560
Det är ofta det jag gör är, dra jag ut den i en funktion,

913
01:11:32,560 --> 01:11:36,040
Jag kallar det något i stil med bygga nod,

914
01:11:36,040 --> 01:11:40,410
och som håller prefix funktionen ganska små, det är bara 3 rader då.

915
01:11:40,410 --> 01:11:48,710
Jag ringer till min bygga nod-funktion, och sedan jag tråd allting.

916
01:11:48,710 --> 01:11:51,970
>> Det sista jag vill visa dig,

917
01:11:51,970 --> 01:11:54,030
och jag ska låta dig göra append och allt som på egen hand,

918
01:11:54,030 --> 01:11:57,500
är hur man iterera över en lista.

919
01:11:57,500 --> 01:12:00,780
Det finns en massa olika sätt att iterera över en lista.

920
01:12:00,780 --> 01:12:03,140
I det här fallet kommer vi att hitta längden på en lista.

921
01:12:03,140 --> 01:12:06,570
Så vi börjar med längd = 0.

922
01:12:06,570 --> 01:12:11,580
Detta är mycket likt skriva strlen efter en sträng.

923
01:12:11,580 --> 01:12:17,780
Detta är vad jag vill visa dig, detta för slinga här.

924
01:12:17,780 --> 01:12:23,530
Det ser ganska funky, det är inte de vanliga int i = 0, i <vad som helst, i + +.

925
01:12:23,530 --> 01:12:34,920
Istället är initiering vår variabeln n att vara början av listan.

926
01:12:34,920 --> 01:12:40,620
Och sedan när vi iterator variabel inte är null, håller vi igång.

927
01:12:40,620 --> 01:12:46,340
Detta beror, enligt konvention, kommer i slutet av vår lista vara null.

928
01:12:46,340 --> 01:12:48,770
Och sedan att öka, snarare än att göra + +,

929
01:12:48,770 --> 01:12:57,010
den länkade listan motsvarande + + är N = N-> nästa.

930
01:12:57,010 --> 01:13:00,410
>> Jag ska låta dig fylla i luckorna här eftersom vi är för sent.

931
01:13:00,410 --> 01:13:09,300
Men ha detta i åtanke när du arbetar på din spellr psets.

932
01:13:09,300 --> 01:13:11,650
Länkade listor, om du genomföra en hash-tabell,

933
01:13:11,650 --> 01:13:14,010
kommer definitivt komma väl till pass.

934
01:13:14,010 --> 01:13:21,780
Och med detta formspråk för looping över saker kommer att göra livet mycket enklare, förhoppningsvis.

935
01:13:21,780 --> 01:13:25,910
Har du frågor, snabbt?

936
01:13:25,910 --> 01:13:28,920
[Sam] Kommer ni att skicka ut den ifyllda SLL och SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ja. Jag skickar ut färdiga bilder och avslutade SLL stack och queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]