1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [Avsnitt 6] [Mer Bekväm]

2
00:00:01,000 --> 00:00:04,000
[Rob Bowden] [Harvard University]

3
00:00:04,000 --> 00:00:09,000
[Detta är CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> Vi kan gå till vår sektion med frågor.

5
00:00:11,000 --> 00:00:17,000
Jag skickade URL för utrymmet innan.

6
00:00:17,000 --> 00:00:22,000
Början av den del av frågorna säga-

7
00:00:22,000 --> 00:00:26,000
tydligen är jag inte helt unsick-är en mycket enkel fråga

8
00:00:26,000 --> 00:00:28,000
om precis vad som valgrind?

9
00:00:28,000 --> 00:00:30,000
Vad gör Valgrind?

10
00:00:30,000 --> 00:00:34,000
Någon som vill säga vad Valgrind gör?

11
00:00:34,000 --> 00:00:36,000
[Student] Kontroller minnesläckor.

12
00:00:36,000 --> 00:00:41,000
Ja, det är Valgrind en allmän minne bricka.

13
00:00:41,000 --> 00:00:44,000
Det, i slutändan, säger om du har några minnesläckor,

14
00:00:44,000 --> 00:00:49,000
som oftast vad vi använder det för att om du vill

15
00:00:49,000 --> 00:00:54,000
göra bra i problemet apparaten eller om du vill

16
00:00:54,000 --> 00:00:59,000
få på den stora styrelsen, måste du ha någon minnesläckor som helst,

17
00:00:59,000 --> 00:01:01,000
och om du har en minnesläcka som du inte kan hitta,

18
00:01:01,000 --> 00:01:04,000
också ihåg att när du öppnar en fil

19
00:01:04,000 --> 00:01:07,000
och om du inte stänga den, det är en minnesläcka.

20
00:01:07,000 --> 00:01:10,000
>> Många människor söker efter någon nod som de inte befria

21
00:01:10,000 --> 00:01:15,000
när det verkligen, de stänger inte i ordlistan i det allra första steget.

22
00:01:15,000 --> 00:01:19,000
Den berättar också om du har några ogiltiga läser eller skriver,

23
00:01:19,000 --> 00:01:22,000
vilket innebär att om du försöker och ange ett värde

24
00:01:22,000 --> 00:01:26,000
det är bortom slutet på högen, och det händer inte på seg fel

25
00:01:26,000 --> 00:01:30,000
men Valgrind fångar den, eftersom du egentligen inte borde skriva det,

26
00:01:30,000 --> 00:01:33,000
och så du definitivt inte ha någon av dem heller.

27
00:01:33,000 --> 00:01:38,000
Hur använder du valgrind?

28
00:01:38,000 --> 00:01:42,000
Hur använder du valgrind?

29
00:01:42,000 --> 00:01:45,000
>> Det är en allmän fråga om

30
00:01:45,000 --> 00:01:49,000
typ av kör det och titta på utgången.

31
00:01:49,000 --> 00:01:51,000
Utgången är överväldigande många gånger.

32
00:01:51,000 --> 00:01:54,000
Det finns också roliga fel där om du har några fruktansvärt fel sak

33
00:01:54,000 --> 00:01:59,000
händer i en slinga, så kommer det så småningom att säga, "Sätt för många fel.

34
00:01:59,000 --> 00:02:03,000
Jag ska sluta räkna nu. "

35
00:02:03,000 --> 00:02:08,000
Det är i princip textuell utgång som du har att tolka.

36
00:02:08,000 --> 00:02:13,000
I slutändan kommer det att berätta någon minnesläckor som du har,

37
00:02:13,000 --> 00:02:16,000
hur många block, som kan vara användbart eftersom

38
00:02:16,000 --> 00:02:20,000
om det är ett kvarter unfreed, då är det oftast lättare att hitta

39
00:02:20,000 --> 00:02:23,000
än 1.000 block unfreed.

40
00:02:23,000 --> 00:02:26,000
1.000 block unfreed betyder förmodligen att du inte frigöra

41
00:02:26,000 --> 00:02:30,000
dina länkade listor lämpligt sätt eller något.

42
00:02:30,000 --> 00:02:32,000
Det är valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Nu har vi vår del av frågor,

44
00:02:35,000 --> 00:02:38,000
som du inte behöver ladda ner.

45
00:02:38,000 --> 00:02:41,000
Du kan klicka på mitt namn och dra upp dem i rymden.

46
00:02:41,000 --> 00:02:44,000
Klicka nu på mig.

47
00:02:44,000 --> 00:02:46,000
Revidering 1 blir stack, som vi gör först.

48
00:02:46,000 --> 00:02:55,000
Revision 2 kommer att vara kö, och Revision 3 kommer att vara den enskilt länkade listan.

49
00:02:55,000 --> 00:02:58,000
Det började med vår stack.

50
00:02:58,000 --> 00:03:02,000
Som det står här, är en bunt en av de mest grundläggande,

51
00:03:02,000 --> 00:03:07,000
grundläggande datastrukturer datavetenskap.

52
00:03:07,000 --> 00:03:11,000
Den mycket prototypiska exemplet är

53
00:03:11,000 --> 00:03:13,000
bunten av brickor i matsalen.

54
00:03:13,000 --> 00:03:16,000
Det är i grunden när du håller på att introduceras till en skorsten,

55
00:03:16,000 --> 00:03:20,000
någon kommer att säga, "Åh, som en stapel av brickor."

56
00:03:20,000 --> 00:03:22,000
Du stapla brickorna upp.

57
00:03:22,000 --> 00:03:24,000
Sen när du går att dra en bricka,

58
00:03:24,000 --> 00:03:31,000
det första facket som är få dras är den sista som sattes på stacken.

59
00:03:31,000 --> 00:03:34,000
Bunten också, som det står här-

60
00:03:34,000 --> 00:03:37,000
vi har segmentet av minnet kallas stapeln.

61
00:03:37,000 --> 00:03:40,000
Och varför kallas det stapeln?

62
00:03:40,000 --> 00:03:42,000
>> Eftersom som en stack datastruktur,

63
00:03:42,000 --> 00:03:46,000
den pressar och poppar stack ramar på stacken,

64
00:03:46,000 --> 00:03:53,000
där stack ramar är som en särskild inbjudan av en funktion.

65
00:03:53,000 --> 00:03:57,000
Och som en stapel, kommer du alltid att återvända

66
00:03:57,000 --> 00:04:03,000
från ett funktionsanrop innan du kan komma ner till lägre stack ramar igen.

67
00:04:03,000 --> 00:04:08,000
Du kan inte ha stora samtal foo samtal bar och bar tillbaka till huvud direkt.

68
00:04:08,000 --> 00:04:14,000
Det har alltid fått följa rätt stacken trycka och popping.

69
00:04:14,000 --> 00:04:18,000
De två operationer, som jag sa, är push och pop.

70
00:04:18,000 --> 00:04:20,000
De är universella termer.

71
00:04:20,000 --> 00:04:26,000
Du bör känna till tryck och pop i form av staplar oavsett vad.

72
00:04:26,000 --> 00:04:28,000
Vi får se köer är typ av olika.

73
00:04:28,000 --> 00:04:32,000
Det har egentligen en universell term, men push och pop är universella för stackar.

74
00:04:32,000 --> 00:04:34,000
Push är bara sätta på stacken.

75
00:04:34,000 --> 00:04:37,000
Pop är ta av stapeln.

76
00:04:37,000 --> 00:04:43,000
Och vi ser här har vi vår typedef struct stack,

77
00:04:43,000 --> 00:04:46,000
så vi har röding ** strängar.

78
00:04:46,000 --> 00:04:51,000
Bli inte rädd av några **.

79
00:04:51,000 --> 00:04:54,000
Detta kommer att hamna en array med strängar

80
00:04:54,000 --> 00:04:58,000
eller en uppsättning pekare till tecken, där

81
00:04:58,000 --> 00:05:00,000
pekare till tecken tenderar att vara strängar.

82
00:05:00,000 --> 00:05:05,000
Det behöver inte vara strängar, men här kommer de att bli strängar.

83
00:05:05,000 --> 00:05:08,000
>> Vi har en array med strängar.

84
00:05:08,000 --> 00:05:14,000
Vi har en storlek, som representerar hur många element är närvarande på stacken,

85
00:05:14,000 --> 00:05:19,000
och då vi har kapacitet, vilket är hur många element kan vara på stacken.

86
00:05:19,000 --> 00:05:22,000
Kapaciteten ska börja som något större än 1,

87
00:05:22,000 --> 00:05:27,000
men storleken kommer att börja som 0.

88
00:05:27,000 --> 00:05:36,000
Nu finns det i princip tre olika sätt du kan tänka dig en bunt.

89
00:05:36,000 --> 00:05:39,000
Nåväl, det finns förmodligen fler, men de två huvudsakliga sätt är

90
00:05:39,000 --> 00:05:43,000
du kan genomföra den med en array, eller så kan du genomföra det med hjälp av en länkad lista.

91
00:05:43,000 --> 00:05:48,000
Länkade listor är typ av trivialt att göra travar från.

92
00:05:48,000 --> 00:05:51,000
Det är mycket lätt att göra en stapel med länkade listor,

93
00:05:51,000 --> 00:05:55,000
så här ska vi göra en stack med arrayer,

94
00:05:55,000 --> 00:05:59,000
och sedan använda arrayer, det finns också två sätt du kan tänka på det.

95
00:05:59,000 --> 00:06:01,000
Förut när jag sa att vi har en kapacitet för stacken,

96
00:06:01,000 --> 00:06:04,000
så att vi kan anpassa ett element på stacken.

97
00:06:04,000 --> 00:06:09,000
>> Det enda sättet det kan ske är när du träffar 10 element, då du är klar.

98
00:06:09,000 --> 00:06:13,000
Du kanske vet att det finns en övre gräns på 10 saker i världen

99
00:06:13,000 --> 00:06:16,000
att du aldrig kommer att ha mer än 10 saker på din stack,

100
00:06:16,000 --> 00:06:20,000
i vilket fall du kan ha en övre gräns på storleken på din stack.

101
00:06:20,000 --> 00:06:23,000
Eller du kan ha din stack vara obegränsad,

102
00:06:23,000 --> 00:06:27,000
men om du gör en array, innebär att varje gång du träffar 10 element,

103
00:06:27,000 --> 00:06:29,000
då du kommer att behöva växa till 20 element, och när du träffar 20 element,

104
00:06:29,000 --> 00:06:33,000
du kommer att behöva öka din array för att 30 element eller 40 element.

105
00:06:33,000 --> 00:06:37,000
Du kommer att behöva öka kapaciteten, vilket är vad vi ska göra här.

106
00:06:37,000 --> 00:06:40,000
Varje enskild tid vi når den maximala storleken på vår stack,

107
00:06:40,000 --> 00:06:46,000
När vi trycker något annat på, vi kommer att behöva öka kapaciteten.

108
00:06:46,000 --> 00:06:50,000
Här har vi förklarat tryck som bool tryck (char * str).

109
00:06:50,000 --> 00:06:54,000
Char * str är strängen som vi driver på stacken,

110
00:06:54,000 --> 00:06:58,000
och bool säger bara om vi lyckades eller misslyckades.

111
00:06:58,000 --> 00:07:00,000
>> Hur kan vi misslyckas?

112
00:07:00,000 --> 00:07:04,000
Vad är det enda omständighet som du kan tänka på

113
00:07:04,000 --> 00:07:07,000
där vi skulle behöva returnera false?

114
00:07:07,000 --> 00:07:09,000
Ja.

115
00:07:09,000 --> 00:07:12,000
[Student] Om det är fullt och vi använder en begränsad implementering.

116
00:07:12,000 --> 00:07:17,000
Ja, så hur definierar, han vi besvarat

117
00:07:17,000 --> 00:07:23,000
om det är fullt och vi använder en begränsad implementering.

118
00:07:23,000 --> 00:07:26,000
Då kommer vi definitivt att returnera false.

119
00:07:26,000 --> 00:07:31,000
Så snart vi träffar 10 saker i arrayen, kan vi inte passar 11, så vi returnera false.

120
00:07:31,000 --> 00:07:32,000
Tänk om det är obegränsad? Ja.

121
00:07:32,000 --> 00:07:38,000
Om du inte kan expandera arrayen av någon anledning.

122
00:07:38,000 --> 00:07:43,000
Ja, det är så minne en begränsad resurs,

123
00:07:43,000 --> 00:07:51,000
och så småningom, om vi fortsätter trycka saker på stacken om och om igen,

124
00:07:51,000 --> 00:07:54,000
vi ska försöka fördela en större mängd för att passa

125
00:07:54,000 --> 00:07:59,000
den större kapacitet och malloc eller vad vi använder kommer att returnera false.

126
00:07:59,000 --> 00:08:02,000
Tja, kommer malloc returnera null.

127
00:08:02,000 --> 00:08:05,000
>> Kom ihåg att varje gång du någonsin ringa malloc, bör du kontrollera om det

128
00:08:05,000 --> 00:08:12,000
returnerar null eller annat som är en korrekt avdrag.

129
00:08:12,000 --> 00:08:17,000
Eftersom vi vill ha en obegränsad stack,

130
00:08:17,000 --> 00:08:21,000
det enda fall vi kommer att vara tillbaka falska är om vi försöker

131
00:08:21,000 --> 00:08:26,000
öka kapaciteten och malloc eller vad returnerar false.

132
00:08:26,000 --> 00:08:30,000
Sedan pop tar inga argument,

133
00:08:30,000 --> 00:08:37,000
och det returnerar strängen som är på toppen av stacken.

134
00:08:37,000 --> 00:08:41,000
Oavsett var senast tryckte på stacken är vad pop återvänder,

135
00:08:41,000 --> 00:08:44,000
och det tar också bort det från stapeln.

136
00:08:44,000 --> 00:08:50,000
Och märker att det returnerar null om det inte finns något på stacken.

137
00:08:50,000 --> 00:08:53,000
Det är alltid möjligt att stacken är tom.

138
00:08:53,000 --> 00:08:55,000
I Java, om du är van vid det, eller andra språk,

139
00:08:55,000 --> 00:09:01,000
försöker pop från en tom stack kan orsaka ett undantag eller något.

140
00:09:01,000 --> 00:09:09,000
>> Men i C, null slags många av de fall hur vi hanterar dessa problem.

141
00:09:09,000 --> 00:09:13,000
Återvänder null är hur vi ska betyda att stacken var tom.

142
00:09:13,000 --> 00:09:16,000
Vi ger kod som kommer att testa din stack funktionalitet,

143
00:09:16,000 --> 00:09:19,000
genomföra skjuta och pop.

144
00:09:19,000 --> 00:09:23,000
Detta kommer inte att finnas en hel del kod.

145
00:09:23,000 --> 00:09:40,000
Jag kommer-faktiskt, innan vi gör det, tips, tips,

146
00:09:40,000 --> 00:09:44,000
Om du inte har sett det, är malloc inte den enda funktionen

147
00:09:44,000 --> 00:09:47,000
som fördelar minne på heap för dig.

148
00:09:47,000 --> 00:09:51,000
Det finns en familj av Alloc funktioner.

149
00:09:51,000 --> 00:09:53,000
Den första är malloc, som du är van vid.

150
00:09:53,000 --> 00:09:56,000
Sedan finns calloc, som gör samma sak som malloc,

151
00:09:56,000 --> 00:09:59,000
men det kommer noll allting för dig.

152
00:09:59,000 --> 00:10:04,000
Om du någonsin velat ställa allt till null efter mallocing något

153
00:10:04,000 --> 00:10:06,000
Du bör bara använt calloc i första hand istället för att skriva

154
00:10:06,000 --> 00:10:09,000
en for-slinga för att nollställa hela block av minne.

155
00:10:09,000 --> 00:10:15,000
>> Realloc är som malloc och har en hel del speciella fall,

156
00:10:15,000 --> 00:10:19,000
men i stort sett vad realloc gör är

157
00:10:19,000 --> 00:10:24,000
det tar en pekare som redan hade tilldelats.

158
00:10:24,000 --> 00:10:27,000
Realloc är den funktion som du vill ska uppmärksamma här.

159
00:10:27,000 --> 00:10:31,000
Det tar en pekare som redan återvänt från malloc.

160
00:10:31,000 --> 00:10:35,000
Låt oss säga att du begär från malloc en pekare på 10 byte.

161
00:10:35,000 --> 00:10:38,000
Senare inser du att du ville 20 byte,

162
00:10:38,000 --> 00:10:42,000
så du kallar realloc på den pekare med 20 byte,

163
00:10:42,000 --> 00:10:47,000
och realloc kommer automatiskt kopiera över allt för dig.

164
00:10:47,000 --> 00:10:51,000
Om du ringde bara malloc igen, som jag har ett block med 10 byte.

165
00:10:51,000 --> 00:10:53,000
Nu behöver jag ett block med 20 byte,

166
00:10:53,000 --> 00:10:58,000
så om jag malloc 20 byte, då måste jag manuellt kopiera över de 10 byte från första

167
00:10:58,000 --> 00:11:01,000
i den andra sak och sedan fri det första.

168
00:11:01,000 --> 00:11:04,000
Realloc kommer att hantera det åt dig.

169
00:11:04,000 --> 00:11:11,000
>> Lägg märke till signaturen kommer att vara ogiltiga *

170
00:11:11,000 --> 00:11:15,000
som just returnerar en pekare till blocket av minnet,

171
00:11:15,000 --> 00:11:17,000
sedan void * ptr.

172
00:11:17,000 --> 00:11:22,000
Du kan tänka på void * som en generisk pekare.

173
00:11:22,000 --> 00:11:27,000
Generellt hanterar du aldrig med void *,

174
00:11:27,000 --> 00:11:30,000
men malloc återvänder ett tomrum *, och sedan är det bara används som

175
00:11:30,000 --> 00:11:34,000
Detta är faktiskt kommer att bli en char *.

176
00:11:34,000 --> 00:11:37,000
Den tidigare void * som hade återvänt från malloc

177
00:11:37,000 --> 00:11:41,000
kommer nu att föras till realloc och sedan storlek

178
00:11:41,000 --> 00:11:49,000
är det nya antalet byte som du vill tilldela, så att din nya kapacitet.

179
00:11:49,000 --> 00:11:57,000
Jag ska ge er ett par minuter, och göra det i vårt utrymme.

180
00:11:57,000 --> 00:12:02,000
Börja med Revision 1.

181
00:12:16,000 --> 00:12:21,000
Jag ska sluta dig efter förhoppningsvis om tillräckligt med tid att genomföra push,

182
00:12:21,000 --> 00:12:24,000
och sedan ska jag ge er ett annat paus för att göra pop.

183
00:12:24,000 --> 00:12:27,000
Men det är verkligen inte så mycket kod alls.

184
00:12:27,000 --> 00:12:35,000
Den mest koden är förmodligen den expanderande grejer, utöka kapaciteten.

185
00:12:35,000 --> 00:12:39,000
Okej, ingen press att vara helt klar,

186
00:12:39,000 --> 00:12:47,000
men så länge du känner att du är på rätt väg, det är bra.

187
00:12:47,000 --> 00:12:53,000
>> Har någon någon kod som de känner sig bekväma med mig att dra upp?

188
00:12:53,000 --> 00:12:59,000
Ja, det ska jag, men någon har någon kod jag kan dra upp?

189
00:12:59,000 --> 00:13:05,000
Okej, kan du starta, spara den, vad är det?

190
00:13:05,000 --> 00:13:09,000
Jag glömmer alltid det steget.

191
00:13:09,000 --> 00:13:15,000
Okej, titta på push,

192
00:13:15,000 --> 00:13:18,000
vill du förklara din kod?

193
00:13:18,000 --> 00:13:24,000
[Student] Först av allt, ökade jag storleken.

194
00:13:24,000 --> 00:13:28,000
Jag antar kanske jag borde ha det, hur som helst, ökade jag storleken,

195
00:13:28,000 --> 00:13:31,000
och jag se om det är mindre än kapaciteten.

196
00:13:31,000 --> 00:13:36,000
Och om det är mindre än kapaciteten, lägger jag till array som vi redan har.

197
00:13:36,000 --> 00:13:42,000
Och om det inte är, multiplicera jag kapaciteten med 2,

198
00:13:42,000 --> 00:13:50,000
och jag omfördela strängar array för att något med en större kapacitet storlek nu.

199
00:13:50,000 --> 00:13:55,000
Och sedan om det misslyckas, säger jag användaren och returnera false,

200
00:13:55,000 --> 00:14:04,000
och om det är bra, då jag satte strängen i den nya platsen.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] också märke till att vi använde en fin bitvis här

202
00:14:07,000 --> 00:14:09,000
att multiplicera med 2.

203
00:14:09,000 --> 00:14:11,000
Kom ihåg att vänster skift kommer alltid att multipliceras med 2.

204
00:14:11,000 --> 00:14:15,000
Högerskift divideras med 2, så länge du kommer ihåg att det betyder

205
00:14:15,000 --> 00:14:18,000
dividera med 2 såsom i ett heltal delat med 2.

206
00:14:18,000 --> 00:14:20,000
Det kan trunkera en 1 här eller där.

207
00:14:20,000 --> 00:14:26,000
Men skift kvar av 1 kommer alltid att multipliceras med 2,

208
00:14:26,000 --> 00:14:32,000
om du inte svämma över gränserna för heltal och då det inte kommer att bli.

209
00:14:32,000 --> 00:14:34,000
En sida kommentar.

210
00:14:34,000 --> 00:14:39,000
Jag tycker om att göra, det kommer inte att ändra kodningen något sätt,

211
00:14:39,000 --> 00:14:48,000
men jag gillar att göra något sånt här.

212
00:14:48,000 --> 00:14:51,000
Det faktiskt kommer att göra det lite längre.

213
00:15:04,000 --> 00:15:08,000
Kanske är detta inte den perfekta fallet för att visa detta,

214
00:15:08,000 --> 00:15:14,000
men jag gillar att dela det i dessa block-

215
00:15:14,000 --> 00:15:17,000
Okej, om detta om händer, då kommer jag att göra något,

216
00:15:17,000 --> 00:15:19,000
och därefter funktionen görs.

217
00:15:19,000 --> 00:15:22,000
Jag behöver inte rulla mina ögon hela vägen ner funktionen

218
00:15:22,000 --> 00:15:25,000
att se vad som händer efter annat.

219
00:15:25,000 --> 00:15:27,000
Det är om detta om händer, då jag återvänder bara.

220
00:15:27,000 --> 00:15:30,000
Det har också den trevliga fördelen av allt utöver detta

221
00:15:30,000 --> 00:15:33,000
Nu flyttas till vänster en gång.

222
00:15:33,000 --> 00:15:40,000
Jag behöver inte längre, om du någonsin nära löjligt långa rader,

223
00:15:40,000 --> 00:15:45,000
då de 4 byte kan hjälpa, och även mer vänster något är,

224
00:15:45,000 --> 00:15:48,000
mindre överväldigade du känna dig om vill-Okej, jag måste komma ihåg

225
00:15:48,000 --> 00:15:53,000
Jag är just nu i en while-slinga inuti en annan inne i en for-slinga.

226
00:15:53,000 --> 00:15:58,000
Var du kan göra detta omedelbart återvända, jag gillar.

227
00:15:58,000 --> 00:16:05,000
Det är helt frivilligt och inte förväntas på något sätt.

228
00:16:05,000 --> 00:16:12,000
>> [Student] Skulle det finnas en storlek - i misslyckas skick?

229
00:16:12,000 --> 00:16:19,000
Den misslyckas villkoret här är att vi inte realloc, så ja.

230
00:16:19,000 --> 00:16:22,000
Lägg märke till hur i misslyckas skick, förmodligen,

231
00:16:22,000 --> 00:16:26,000
om vi gratis saker senare, vi kommer alltid att misslyckas

232
00:16:26,000 --> 00:16:29,000
oavsett hur många gånger vi försöker driva något.

233
00:16:29,000 --> 00:16:32,000
Om vi ​​fortsätter att trycka håller vi uppräkning storlek,

234
00:16:32,000 --> 00:16:36,000
även om vi inte sätter något på stacken.

235
00:16:36,000 --> 00:16:39,000
Vanligtvis vi öka inte storleken förrän

236
00:16:39,000 --> 00:16:43,000
efter att vi har lagt ett framgångsrikt det på stacken.

237
00:16:43,000 --> 00:16:50,000
Vi skulle göra det, säger, antingen här och här.

238
00:16:50,000 --> 00:16:56,000
Och sedan istället för att säga s.size ≤ kapacitet, det är mindre än kapaciteten,

239
00:16:56,000 --> 00:17:01,000
bara för att vi flyttade där allt var.

240
00:17:01,000 --> 00:17:07,000
>> Och kom ihåg, den enda plats som vi kunde eventuellt returnera false

241
00:17:07,000 --> 00:17:14,000
är här, där realloc återvände null,

242
00:17:14,000 --> 00:17:19,000
och om du råkar komma ihåg standardfel,

243
00:17:19,000 --> 00:17:22,000
kanske du kan överväga detta ett fall där du vill skriva ut en standardavvikelse,

244
00:17:22,000 --> 00:17:26,000
så fprintf stderr istället för att bara skriva ut direkt till standard ut.

245
00:17:26,000 --> 00:17:31,000
Återigen, det är inte en förväntan, men om det är ett fel,

246
00:17:31,000 --> 00:17:41,000
typ printf, då kanske du vill göra det ut på standard fel istället för vanlig ut.

247
00:17:41,000 --> 00:17:44,000
>> Någon har något annat att notera? Ja.

248
00:17:44,000 --> 00:17:47,000
[Student] Kan du gå över [ohörbart]?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Ja, det faktiska binariness av det eller bara vad det är?

250
00:17:55,000 --> 00:17:57,000
[Student] Så du multiplicera det med 2?

251
00:17:57,000 --> 00:17:59,000
[Rob B.] Ja, i princip.

252
00:17:59,000 --> 00:18:11,000
I binär mark, har vi alltid vår uppsättning siffror.

253
00:18:11,000 --> 00:18:22,000
Växling denna vänster med 1 princip infogar det här på höger sida.

254
00:18:22,000 --> 00:18:25,000
Tillbaka till detta, bara komma ihåg att allt i binär

255
00:18:25,000 --> 00:18:28,000
är en effekt av 2, så detta är 2 till 0,

256
00:18:28,000 --> 00:18:30,000
Detta 2 till 1, det 2 till 2.

257
00:18:30,000 --> 00:18:33,000
Genom att sätta in en 0 på höger sida nu, flyttar vi bara allt över.

258
00:18:33,000 --> 00:18:38,000
Vad som brukade vara 2 till 0 nu 2 till 1, 2 till 2.

259
00:18:38,000 --> 00:18:41,000
Den högra sidan som vi in

260
00:18:41,000 --> 00:18:44,000
nödvändigtvis kommer att bli 0,

261
00:18:44,000 --> 00:18:46,000
vilket är vettigt.

262
00:18:46,000 --> 00:18:49,000
Om du någonsin multiplicera ett tal med 2, det kommer inte att sluta udda,

263
00:18:49,000 --> 00:18:54,000
så 2 till 0 plats bör vara 0,

264
00:18:54,000 --> 00:18:59,000
och detta är vad jag halv varnade innan är om du råkar flytta

265
00:18:59,000 --> 00:19:01,000
bortom antalet bitar i ett heltal,

266
00:19:01,000 --> 00:19:04,000
då denna 1 kommer att sluta gå ut.

267
00:19:04,000 --> 00:19:10,000
Det är den enda oroa dig om du råkar ha att göra med riktigt stor kapacitet.

268
00:19:10,000 --> 00:19:15,000
Men på den punkten, då du arbetar med en rad miljarder saker,

269
00:19:15,000 --> 00:19:25,000
som kanske inte passar in i minnet ändå.

270
00:19:25,000 --> 00:19:31,000
>> Nu kan vi få till pop, som är ännu enklare.

271
00:19:31,000 --> 00:19:36,000
Du kan göra det som om du råkar pop en massa,

272
00:19:36,000 --> 00:19:38,000
och nu är du på halv kapacitet igen.

273
00:19:38,000 --> 00:19:42,000
Du kunde realloc att krympa hur mycket minne du har,

274
00:19:42,000 --> 00:19:47,000
men du behöver inte oroa dig för det, är så det enda realloc fall kommer att vara

275
00:19:47,000 --> 00:19:50,000
växande minne, aldrig krympande minne,

276
00:19:50,000 --> 00:19:59,000
vilket kommer att göra pop super lätt.

277
00:19:59,000 --> 00:20:02,000
Nu köer, som kommer att vara som staplar,

278
00:20:02,000 --> 00:20:06,000
men den ordning du tar saker är omvänd.

279
00:20:06,000 --> 00:20:10,000
Den prototypiska exemplet på en kö är en linje,

280
00:20:10,000 --> 00:20:12,000
så jag antar att om du var engelska, skulle jag ha sagt

281
00:20:12,000 --> 00:20:17,000
en prototypisk exempel på en kö är en kö.

282
00:20:17,000 --> 00:20:22,000
Så som en linje, om du är den första personen i raden,

283
00:20:22,000 --> 00:20:24,000
du förväntar dig att vara den första personen ur linjen.

284
00:20:24,000 --> 00:20:31,000
Om du är den sista personen i linje, du kommer att bli den sista personen på service.

285
00:20:31,000 --> 00:20:35,000
Vi kallar det FIFO mönster, medan stapeln var LIFO mönster.

286
00:20:35,000 --> 00:20:40,000
Dessa ord är ganska universella.

287
00:20:40,000 --> 00:20:46,000
>> Som stackar och till skillnad från arrayer, köer vanligtvis inte tillåter åtkomst till element i mitten.

288
00:20:46,000 --> 00:20:50,000
Här, en stack, har vi push och pop.

289
00:20:50,000 --> 00:20:54,000
Här råkar vi ha kallat dem enqueue och dequeue.

290
00:20:54,000 --> 00:20:58,000
Jag har också hört dem kallas skift och unshift.

291
00:20:58,000 --> 00:21:02,000
Jag har hört folk säga push-och pop även gälla köer.

292
00:21:02,000 --> 00:21:05,000
Jag har hört infoga, ta bort,

293
00:21:05,000 --> 00:21:11,000
så tryck och pop, om du talar om stackar, du trycka och popping.

294
00:21:11,000 --> 00:21:16,000
Om du pratar om köer, kan du välja de ord som du vill använda

295
00:21:16,000 --> 00:21:23,000
för insättning och borttagning, och det finns ingen konsensus om vad den ska heta.

296
00:21:23,000 --> 00:21:27,000
Men här har vi enqueue och dequeue.

297
00:21:27,000 --> 00:21:37,000
Nu ser struct nästan identisk till stapeln struct.

298
00:21:37,000 --> 00:21:40,000
Men vi måste hålla reda på huvudet.

299
00:21:40,000 --> 00:21:44,000
Jag antar att det står här nere, men varför behöver vi huvudet?

300
00:21:53,000 --> 00:21:57,000
Prototyperna är i princip identiska att driva och pop.

301
00:21:57,000 --> 00:21:59,000
Du kan se det som push och pop.

302
00:21:59,000 --> 00:22:08,000
Den enda skillnaden är pop återvänder-istället för sist, det tillbaka den första.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, eller något.

304
00:22:12,000 --> 00:22:14,000
Och här är början.

305
00:22:14,000 --> 00:22:17,000
Vår kö är helt full, så det finns fyra element i den.

306
00:22:17,000 --> 00:22:21,000
I slutet av vår kö är för närvarande 2,

307
00:22:21,000 --> 00:22:24,000
och nu går vi för att infoga något annat.

308
00:22:24,000 --> 00:22:29,000
>> När vi vill infoga det något annat, vad vi gjorde för stapeln versionen

309
00:22:29,000 --> 00:22:36,000
är vi utökat vår block av minne.

310
00:22:36,000 --> 00:22:40,000
Vad är problemet med detta?

311
00:22:40,000 --> 00:22:45,000
[Student] Du flyttar 2.

312
00:22:45,000 --> 00:22:51,000
Vad jag sa tidigare om slutet av kön,

313
00:22:51,000 --> 00:22:57,000
Detta är inte rimligt att vi börjar vid 1,

314
00:22:57,000 --> 00:23:01,000
då vill vi dequeue 1, sedan dequeue 3, sedan dequeue 4,

315
00:23:01,000 --> 00:23:05,000
sedan avköande 2, sedan avköa här.

316
00:23:05,000 --> 00:23:08,000
Vi kan inte använda realloc nu,

317
00:23:08,000 --> 00:23:11,000
eller åtminstone, måste du använda realloc på ett annat sätt.

318
00:23:11,000 --> 00:23:15,000
Men du förmodligen inte bara använda realloc.

319
00:23:15,000 --> 00:23:18,000
Du kommer att behöva manuellt kopiera ditt minne.

320
00:23:18,000 --> 00:23:21,000
>> Det finns två funktioner att kopiera minne.

321
00:23:21,000 --> 00:23:25,000
Det finns memcopy och memmove.

322
00:23:25,000 --> 00:23:29,000
Jag läser just nu de man-sidor för att se vilken du kommer att vilja använda.

323
00:23:29,000 --> 00:23:35,000
Okej, memcopy är skillnaden

324
00:23:35,000 --> 00:23:38,000
att memcopy och memmove, en hanterar ärendet korrekt

325
00:23:38,000 --> 00:23:41,000
där du kopierar in i ett område som råkar överlappa regionen

326
00:23:41,000 --> 00:23:46,000
du kopierar från.

327
00:23:46,000 --> 00:23:50,000
Memcopy hanterar inte det. Memmove gör.

328
00:23:50,000 --> 00:23:59,000
Du kan tänka på problemet som-

329
00:23:59,000 --> 00:24:09,000
låt oss säga att jag vill kopiera den här killen,

330
00:24:09,000 --> 00:24:13,000
Dessa fyra till den här killen över.

331
00:24:13,000 --> 00:24:16,000
I slutändan, vad gruppen bör se ut

332
00:24:16,000 --> 00:24:26,000
Efter kopian är 2, 1, 2, 1, 3, 4, och lite grejer i slutet.

333
00:24:26,000 --> 00:24:29,000
Men detta är beroende på i vilken ordning vi faktiskt kopiera,

334
00:24:29,000 --> 00:24:32,000
eftersom om vi inte anser att regionen vi kopierar in

335
00:24:32,000 --> 00:24:35,000
överlappar en vi kopiera från,

336
00:24:35,000 --> 00:24:46,000
då vi kan göra som start här, kopiera 2 i den plats vi vill gå,

337
00:24:46,000 --> 00:24:52,000
flytta sedan våra pekare framåt.

338
00:24:52,000 --> 00:24:56,000
>> Nu ska vi vara här och här och nu vill vi kopiera

339
00:24:56,000 --> 00:25:04,000
den här killen över den här killen och flytta våra pekare framåt.

340
00:25:04,000 --> 00:25:07,000
Vad vi ska i slutändan får är 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
istället för den lämpliga 2, 1 2,, 1, 3, 4, eftersom

342
00:25:10,000 --> 00:25:15,000
2, 1 överskred den ursprungliga 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove handtag som korrekt.

344
00:25:19,000 --> 00:25:23,000
I det här fallet, i princip bara alltid memmove

345
00:25:23,000 --> 00:25:26,000
eftersom det hanterar det på rätt sätt.

346
00:25:26,000 --> 00:25:29,000
Det i allmänhet inte utför något värre.

347
00:25:29,000 --> 00:25:32,000
Tanken är i stället för att börja från början och kopiera det här sättet

348
00:25:32,000 --> 00:25:35,000
som vi just gjorde här, börjar det från slutet och kopierar in,

349
00:25:35,000 --> 00:25:38,000
och i så fall, kan du aldrig ett problem.

350
00:25:38,000 --> 00:25:40,000
Det finns ingen prestanda förlorad.

351
00:25:40,000 --> 00:25:47,000
Använd alltid memmove. Aldrig oroa memcopy.

352
00:25:47,000 --> 00:25:51,000
Och det är där du kommer att behöva separat memmove

353
00:25:51,000 --> 00:26:01,000
den förpackade runt del av ditt kön.

354
00:26:01,000 --> 00:26:04,000
Inga problem om inte helt klar.

355
00:26:04,000 --> 00:26:10,000
Detta är svårare än stack, push, och pop.

356
00:26:10,000 --> 00:26:15,000
>> Någon har någon kod vi kan arbeta med?

357
00:26:15,000 --> 00:26:21,000
Även om helt ofullständig?

358
00:26:21,000 --> 00:26:23,000
[Student] Ja, det är helt ofullständig, dock.

359
00:26:23,000 --> 00:26:27,000
Helt ofullständig är bra så länge vi-kan du spara översynen?

360
00:26:27,000 --> 00:26:32,000
Jag glömmer att varje gång.

361
00:26:32,000 --> 00:26:39,000
Okej, strunta vad som händer när vi behöver ändra storlek saker.

362
00:26:39,000 --> 00:26:42,000
Helt ignorera ändra storlek.

363
00:26:42,000 --> 00:26:49,000
Förklara denna kod.

364
00:26:49,000 --> 00:26:54,000
Jag kollar först om storleken är mindre än kopian först

365
00:26:54,000 --> 00:27:01,000
och sedan efter det, jag sätter-Jag tar huvud + storlek,

366
00:27:01,000 --> 00:27:05,000
och jag se till att det sveper runt kapacitet arrayen,

367
00:27:05,000 --> 00:27:08,000
och jag sätter den nya strängen i den positionen.

368
00:27:08,000 --> 00:27:12,000
Då jag öka storleken och returnera sant.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B] Detta är definitivt en av de fall där du kommer att vilja använda mod.

370
00:27:22,000 --> 00:27:25,000
Varje typ av fall där du har omslag runt, om du tror omslag runt,

371
00:27:25,000 --> 00:27:29,000
den omedelbara tanken bör vara mod.

372
00:27:29,000 --> 00:27:36,000
Som en snabb optimering / gör din kod en rad kortare,

373
00:27:36,000 --> 00:27:42,000
du märker att raden omedelbart efter detta en

374
00:27:42,000 --> 00:27:53,000
är bara storleken + +, så du kopplar in det i denna linje, storlek + +.

375
00:27:53,000 --> 00:27:58,000
Nu här nere har vi fallet

376
00:27:58,000 --> 00:28:01,000
där vi inte har tillräckligt med minne,

377
00:28:01,000 --> 00:28:05,000
så vi ökar vår kapacitet med 2.

378
00:28:05,000 --> 00:28:09,000
Jag antar att man kan ha samma problem här, men vi kan ignorera det nu,

379
00:28:09,000 --> 00:28:13,000
där om du inte öka din förmåga,

380
00:28:13,000 --> 00:28:18,000
då du kommer att vilja minska din förmåga med 2 igen.

381
00:28:18,000 --> 00:28:24,000
En annan kort anmärkning är precis som du kan göra + =,

382
00:28:24,000 --> 00:28:30,000
Du kan också göra << =.

383
00:28:30,000 --> 00:28:43,000
Nästan vad som helst kan gå innan jämlikar, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * ny är vår nya block av minne.

385
00:28:52,000 --> 00:28:55,000
Åh, här borta.

386
00:28:55,000 --> 00:29:02,000
>> Vad tycker folk om vilken typ av vår nya block av minne?

387
00:29:02,000 --> 00:29:06,000
[Student] Det bör vara röding **.

388
00:29:06,000 --> 00:29:12,000
Tänker tillbaka på vår struct här uppe,

389
00:29:12,000 --> 00:29:14,000
strängar är vad vi omfördela.

390
00:29:14,000 --> 00:29:21,000
Vi gör en helt ny dynamisk lagring för elementen i kön.

391
00:29:21,000 --> 00:29:25,000
Vad vi kommer att tilldela dina strängar är vad vi mallocing just nu,

392
00:29:25,000 --> 00:29:30,000
och så nya kommer att bli en röding **.

393
00:29:30,000 --> 00:29:34,000
Det kommer att bli en array med strängar.

394
00:29:34,000 --> 00:29:38,000
Vad som är fallet enligt vilken vi kommer att återvända falska?

395
00:29:38,000 --> 00:29:41,000
[Student] Ska vi göra det char *?

396
00:29:41,000 --> 00:29:44,000
[Rob B.] Ja, bra samtal.

397
00:29:44,000 --> 00:29:46,000
[Student] Vad var det?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Vi ville göra storleken på char * eftersom vi inte längre

399
00:29:49,000 --> 00:29:53,000
Detta skulle faktiskt vara ett mycket stort problem eftersom sizeof (char) skulle vara 1.

400
00:29:53,000 --> 00:29:55,000
Sizeof char * kommer att bli 4,

401
00:29:55,000 --> 00:29:58,000
så många gånger när du arbetar med Ints,

402
00:29:58,000 --> 00:30:01,000
du brukar komma undan med det eftersom storleken på int och storlek int *

403
00:30:01,000 --> 00:30:04,000
på en 32-bitars system kommer att bli samma sak.

404
00:30:04,000 --> 00:30:09,000
Men här, sizeof (char) och sizeof (char *) nu kommer att vara samma sak.

405
00:30:09,000 --> 00:30:15,000
>> Vad är situation då vi returnera false?

406
00:30:15,000 --> 00:30:17,000
[Student] Ny är null.

407
00:30:17,000 --> 00:30:23,000
Ja, om nya är null, återvänder vi falska,

408
00:30:23,000 --> 00:30:34,000
och jag kommer att kasta ner här-

409
00:30:34,000 --> 00:30:37,000
[Student] [ohörbart]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Ja, det här bra.

411
00:30:39,000 --> 00:30:46,000
Du kan antingen göra 2 gånger kapacitet eller kapacitet skift 1 och sedan bara sätter ner här eller vad som helst.

412
00:30:46,000 --> 00:30:52,000
Vi gör det som vi hade det.

413
00:30:52,000 --> 00:30:56,000
Kapacitet >> = 1.

414
00:30:56,000 --> 00:31:08,000
Och du aldrig kommer att behöva oroa sig för att förlora 1 plats

415
00:31:08,000 --> 00:31:12,000
eftersom du lämnade flyttas med 1, så 1 plats är nödvändigtvis en 0,

416
00:31:12,000 --> 00:31:16,000
så rätt förskjutning av 1, du kommer fortfarande vara bra.

417
00:31:16,000 --> 00:31:19,000
[Student] Behöver du göra det innan retur?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Ja, gör detta helt meningslöst.

419
00:31:29,000 --> 00:31:36,000
>> Nu antar vi ska sluta återvänder sant till slutet.

420
00:31:36,000 --> 00:31:39,000
Hur vi ska göra dessa memmoves,

421
00:31:39,000 --> 00:31:45,000
Vi måste vara försiktiga med hur vi gör dem.

422
00:31:45,000 --> 00:31:50,000
Har någon några förslag på hur vi gör dem?

423
00:32:17,000 --> 00:32:21,000
Här är vår början.

424
00:32:21,000 --> 00:32:28,000
Oundvikligen vill vi börja från början igen

425
00:32:28,000 --> 00:32:35,000
och kopiera saker i därifrån, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Hur gör man det?

427
00:32:41,000 --> 00:32:52,000
Först måste jag titta på manualsidan för memmove igen.

428
00:32:52,000 --> 00:32:57,000
Memmove är ordning argument alltid viktigt.

429
00:32:57,000 --> 00:33:01,000
Vi vill att vår destination först, källa andra storlek trea.

430
00:33:01,000 --> 00:33:06,000
Det finns en hel del funktioner som vända källa och destination.

431
00:33:06,000 --> 00:33:11,000
Destination, källa tenderar att vara konsekvent något.

432
00:33:17,000 --> 00:33:21,000
Flytta, vad är det tillbaka?

433
00:33:21,000 --> 00:33:27,000
Den returnerar en pekare till destination, oavsett anledning kanske du vill det.

434
00:33:27,000 --> 00:33:32,000
Jag kan bilden läste det, men vi vill flytta in vår destination.

435
00:33:32,000 --> 00:33:35,000
>> Vad är vårt mål kommer att?

436
00:33:35,000 --> 00:33:37,000
[Student] Ny.

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Ja, och vart är vi på kopiera från?

438
00:33:39,000 --> 00:33:43,000
Det första vi kopierar detta 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
Vad är-det 1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Vad är adressen till detta 1?

441
00:33:55,000 --> 00:33:58,000
Vad är adressen till den 1?

442
00:33:58,000 --> 00:34:01,000
[Student] [ohörbart]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Huvud + adressen till det första elementet.

444
00:34:03,000 --> 00:34:05,000
Hur får vi det första elementet i arrayen?

445
00:34:05,000 --> 00:34:10,000
[Elev] kö.

446
00:34:10,000 --> 00:34:15,000
[Rob B.] Ja, q.strings.

447
00:34:15,000 --> 00:34:20,000
Kom ihåg, här är vår huvud 1.

448
00:34:20,000 --> 00:34:24,000
Banne mej. Jag tycker bara att det är magiskt,

449
00:34:24,000 --> 00:34:29,000
Här är vår huvud 1. Jag ska ändra min färg också.

450
00:34:29,000 --> 00:34:36,000
Och här är strängar.

451
00:34:36,000 --> 00:34:41,000
Detta kan vi skriva antingen det som vi gjorde hit

452
00:34:41,000 --> 00:34:43,000
med huvud + q.strings.

453
00:34:43,000 --> 00:34:51,000
Många människor också skriva det och q.strings [huvud].

454
00:34:51,000 --> 00:34:55,000
Detta är egentligen inte något mindre effektiv.

455
00:34:55,000 --> 00:34:58,000
Du kanske tänker på det som du dereferencing det och sedan få adressen till,

456
00:34:58,000 --> 00:35:04,000
men kompilatorn kommer att översätta det till vad vi hade tidigare i alla fall, q.strings + huvud.

457
00:35:04,000 --> 00:35:06,000
Oavsett vad du vill tänka på det.

458
00:35:06,000 --> 00:35:11,000
>> Och hur många bytes vi vill kopiera?

459
00:35:11,000 --> 00:35:15,000
[Student] Kapacitet - huvud.

460
00:35:15,000 --> 00:35:18,000
Kapacitet - huvud.

461
00:35:18,000 --> 00:35:21,000
Och då kan du alltid skriva ut ett exempel

462
00:35:21,000 --> 00:35:23,000
ta reda på om det är rätt.

463
00:35:23,000 --> 00:35:26,000
[Student] Det måste delas med 2 då.

464
00:35:26,000 --> 00:35:30,000
Ja, så jag antar att vi skulle kunna använda storlek.

465
00:35:30,000 --> 00:35:35,000
Vi har fortfarande storlek är-

466
00:35:35,000 --> 00:35:39,000
använda storlek, har vi storlek lika med 4.

467
00:35:39,000 --> 00:35:42,000
Vår storlek är 4. Vår huvud är 1.

468
00:35:42,000 --> 00:35:46,000
Vi vill kopiera dessa 3 element.

469
00:35:46,000 --> 00:35:54,000
Det är förstånd kontrollera att storlek - huvudet är korrekt 3.

470
00:35:54,000 --> 00:35:58,000
Och komma tillbaka hit, som vi sagt tidigare,

471
00:35:58,000 --> 00:36:00,000
om vi använde kapacitet, så vi skulle behöva dela med 2

472
00:36:00,000 --> 00:36:04,000
eftersom vi har redan vuxit vår kapacitet, så istället, vi kommer att använda storlek.

473
00:36:11,000 --> 00:36:13,000
Att kopior denna del.

474
00:36:13,000 --> 00:36:18,000
Nu behöver vi kopiera den andra delen, den del som är kvar av starten.

475
00:36:18,000 --> 00:36:28,000
>> Det kommer att memmove i vad läge?

476
00:36:28,000 --> 00:36:32,000
[Student] Plus size - huvud.

477
00:36:32,000 --> 00:36:38,000
Ja, så har vi redan kopierat i storlek - huvud byte,

478
00:36:38,000 --> 00:36:43,000
och så var vi vill kopiera de återstående byte är nytt

479
00:36:43,000 --> 00:36:48,000
och sedan storlek minus-ja, det antal byte som vi redan har kopierat in

480
00:36:48,000 --> 00:36:52,000
Och sedan var vi kopiera från?

481
00:36:52,000 --> 00:36:54,000
[Student] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[Rob B.] Ja, q.strings.

483
00:36:56,000 --> 00:37:02,000
Vi kan antingen göra och q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Detta är betydligt mindre vanligt än detta.

485
00:37:05,000 --> 00:37:14,000
Om det bara kommer att bli 0, så kommer du tenderar att se q.strings.

486
00:37:14,000 --> 00:37:16,000
Det är där vi kopiera från.

487
00:37:16,000 --> 00:37:18,000
Hur många bytes har vi kvar att kopiera? >> [Student] 10.

488
00:37:18,000 --> 00:37:20,000
Rätt.

489
00:37:20,000 --> 00:37:25,000
[Student] Har vi multiplicera 5 till 10 gånger större byte eller något?

490
00:37:25,000 --> 00:37:30,000
Ja, så det är där-vad exakt vi kopierar?

491
00:37:30,000 --> 00:37:32,000
[Student] [ohörbart]

492
00:37:32,000 --> 00:37:34,000
Vilken typ av sak vi kopierar?

493
00:37:34,000 --> 00:37:36,000
[Student] [ohörbart]

494
00:37:36,000 --> 00:37:41,000
Ja, så char * s att vi kopierar, vet vi inte var de kommer ifrån.

495
00:37:41,000 --> 00:37:47,000
Jo, där de pekar på, liksom strängarna hamnar vi driver den på kön

496
00:37:47,000 --> 00:37:49,000
eller enqueuing på kön.

497
00:37:49,000 --> 00:37:51,000
Där de kommer ifrån, vi har ingen aning.

498
00:37:51,000 --> 00:37:56,000
Vi behöver bara hålla reda på char * s själva.

499
00:37:56,000 --> 00:38:00,000
Vi vill inte kopiera storlek - huvud byte.

500
00:38:00,000 --> 00:38:03,000
Vi vill kopiera storlek - huvud char * s,

501
00:38:03,000 --> 00:38:11,000
så vi kommer att multiplicera med sizeof (char *).

502
00:38:11,000 --> 00:38:17,000
Samma här nere, chef * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Student] Hur [ohörbart]?

504
00:38:24,000 --> 00:38:26,000
Denna rätt här?

505
00:38:26,000 --> 00:38:28,000
[Student] Nej, under den, storlek - huvudet.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] Denna rätt här?

507
00:38:30,000 --> 00:38:32,000
Pointer aritmetik.

508
00:38:32,000 --> 00:38:35,000
Hur pekare aritmetik kommer att fungera är

509
00:38:35,000 --> 00:38:40,000
den multiplicerar automatiskt av storleken av den typ som vi har att göra med.

510
00:38:40,000 --> 00:38:46,000
Precis som här, ny + (storlek - huvud)

511
00:38:46,000 --> 00:38:56,000
är exakt lika med och nya [storlek - huvud]

512
00:38:56,000 --> 00:39:00,000
tills vi förväntar oss att arbeta på rätt sätt,

513
00:39:00,000 --> 00:39:04,000
eftersom om vi har att göra med en int array, så vi inte index med int-

514
00:39:04,000 --> 00:39:07,000
eller om det är av storlek 5 och du vill den 4: e delen, då vi index till

515
00:39:07,000 --> 00:39:10,000
int array [4].

516
00:39:10,000 --> 00:39:14,000
Du du inte får [4] * storlek int.

517
00:39:14,000 --> 00:39:21,000
Som hanterar det automatiskt, och detta fall

518
00:39:21,000 --> 00:39:29,000
är bokstavligen lika, så fästet syntaxen

519
00:39:29,000 --> 00:39:34,000
är bara kommer att konverteras till detta så snart som du kompilerar.

520
00:39:34,000 --> 00:39:38,000
Det är något du måste vara försiktig med att

521
00:39:38,000 --> 00:39:42,000
När du lägger till storlek - huvud

522
00:39:42,000 --> 00:39:45,000
du lägger inte en byte.

523
00:39:45,000 --> 00:39:53,000
Du lägger en char *, som kan vara en byte eller vad som helst.

524
00:39:53,000 --> 00:39:56,000
>> Övriga frågor?

525
00:39:56,000 --> 00:40:04,000
Okej, dequeue kommer att bli lättare.

526
00:40:04,000 --> 00:40:11,000
Jag ska ge er en minut att genomföra.

527
00:40:11,000 --> 00:40:18,000
Åh, och jag antar att detta är samma situation där

528
00:40:18,000 --> 00:40:21,000
vad enqueue fallet, om vi enqueuing null,

529
00:40:21,000 --> 00:40:24,000
kanske vi vill hantera det, vi kanske inte.

530
00:40:24,000 --> 00:40:27,000
Vi kommer inte att göra det igen här, men samma som vår stack fall.

531
00:40:27,000 --> 00:40:34,000
Om vi ​​köa null, kanske vi vill bortse från det.

532
00:40:34,000 --> 00:40:40,000
Någon har någon kod jag kan dra upp?

533
00:40:40,000 --> 00:40:45,000
[Student] Jag har bara dequeue.

534
00:40:45,000 --> 00:40:56,000
Version 2 är att-okej.

535
00:40:56,000 --> 00:40:59,000
Vill du förklara?

536
00:40:59,000 --> 00:41:01,000
[Student] Först gör du att det finns något i kön

537
00:41:01,000 --> 00:41:07,000
och att storleken går ner med 1.

538
00:41:07,000 --> 00:41:11,000
Du måste göra det, och sedan tillbaka huvudet

539
00:41:11,000 --> 00:41:13,000
och sedan flytta huvudet uppåt 1.

540
00:41:13,000 --> 00:41:19,000
Okej, så det är ett hörn fall måste vi ta hänsyn till. Ja.

541
00:41:19,000 --> 00:41:24,000
[Student] Om ditt huvud är det sista elementet,

542
00:41:24,000 --> 00:41:26,000
då du inte vill huvud peka utanför arrayen.

543
00:41:26,000 --> 00:41:29,000
>> Ja, så snart som chef träffar slutet av vår grupp,

544
00:41:29,000 --> 00:41:35,000
När vi avköa bör vår huvudet modded till 0.

545
00:41:35,000 --> 00:41:40,000
Tyvärr kan vi inte göra det i ett steg.

546
00:41:40,000 --> 00:41:44,000
Jag antar det sätt jag skulle nog fixa det är

547
00:41:44,000 --> 00:41:52,000
Detta kommer att bli en char *, vad vi tillbaka,

548
00:41:52,000 --> 00:41:55,000
oavsett din variabelnamn vill vara.

549
00:41:55,000 --> 00:42:02,000
Sen vill vi mod huvudet av vår kapacitet

550
00:42:02,000 --> 00:42:10,000
och sedan tillbaka ret.

551
00:42:10,000 --> 00:42:14,000
Många människor här de kan göra,

552
00:42:14,000 --> 00:42:19,000
detta är fallet med-du se folk göra om huvudet

553
00:42:19,000 --> 00:42:29,000
är större än kapaciteten, gör huvudet - kapacitet.

554
00:42:29,000 --> 00:42:36,000
Och det är bara att arbeta kring vad mod är.

555
00:42:36,000 --> 00:42:41,000
Chef mod = kapacitet är mycket renare

556
00:42:41,000 --> 00:42:51,000
av ett omslag runt än om huvudet är större än kapaciteten huvud - kapacitet.

557
00:42:51,000 --> 00:42:56,000
>> Frågor?

558
00:42:56,000 --> 00:43:02,000
Okej, är det sista vi har kvar vår länkad lista.

559
00:43:02,000 --> 00:43:07,000
Du skulle kunna användas till några av de länkade listan beteende om du gjorde

560
00:43:07,000 --> 00:43:11,000
länkade listor i dina hashtabeller, om du gjorde en hash-tabell.

561
00:43:11,000 --> 00:43:15,000
Jag rekommenderar starkt att göra en hash-tabell.

562
00:43:15,000 --> 00:43:17,000
Du kanske redan har gjort en trie,

563
00:43:17,000 --> 00:43:23,000
men försök är svårare.

564
00:43:23,000 --> 00:43:27,000
I teorin är de asymptotiskt bättre.

565
00:43:27,000 --> 00:43:30,000
Men titta bara på den stora styrelsen,

566
00:43:30,000 --> 00:43:35,000
och försöker aldrig göra bättre, och de tar upp mer minne.

567
00:43:35,000 --> 00:43:43,000
Allt försöker om slutar som värre för mer arbete.

568
00:43:43,000 --> 00:43:49,000
Det är vad David Malan lösning alltid är

569
00:43:49,000 --> 00:43:56,000
Är han alltid inlägg hans trie lösning, och låt oss se var han för närvarande är.

570
00:43:56,000 --> 00:44:00,000
Vad var han under, David J?

571
00:44:00,000 --> 00:44:06,000
Han är # 18, så det är inte så väldigt dåligt,

572
00:44:06,000 --> 00:44:09,000
och det kommer att bli en av de bästa försöker man kan tänka

573
00:44:09,000 --> 00:44:17,000
eller en av de bästa försök av en trie.

574
00:44:17,000 --> 00:44:23,000
Är det inte ens hans ursprungliga lösning?

575
00:44:23,000 --> 00:44:29,000
Jag känner mig som Trie lösningar tenderar att vara mer i denna serie av RAM-användning.

576
00:44:29,000 --> 00:44:33,000
>> Gå ner till den absoluta toppen, och RAM-användning i de enskilda siffror.

577
00:44:33,000 --> 00:44:36,000
Gå ner mot botten, och sedan börjar se försöker

578
00:44:36,000 --> 00:44:41,000
där du får absolut massiv RAM-användning,

579
00:44:41,000 --> 00:44:45,000
och försöker är svårare.

580
00:44:45,000 --> 00:44:53,000
Inte helt värt det men en lärorik erfarenhet om du gjorde en.

581
00:44:53,000 --> 00:44:56,000
Det sista är vår länkad lista,

582
00:44:56,000 --> 00:45:04,000
och dessa tre saker, stackar, köer och länkade listor,

583
00:45:04,000 --> 00:45:09,000
framtida sak du någonsin gör i datavetenskap

584
00:45:09,000 --> 00:45:12,000
kommer att anta att du har kännedom om dessa saker.

585
00:45:12,000 --> 00:45:19,000
De är bara så grundläggande för allt.

586
00:45:19,000 --> 00:45:25,000
>> Länkade listor, och här har vi en enskilt länkad lista kommer att bli vårt genomförande.

587
00:45:25,000 --> 00:45:34,000
Vad enskilt kopplade innebär i motsats till dubbelt länkad? Ja.

588
00:45:34,000 --> 00:45:37,000
[Student] Den pekar bara till nästa pekaren istället för pekare,

589
00:45:37,000 --> 00:45:39,000
liknande det som föregick den och den ena efter den.

590
00:45:39,000 --> 00:45:44,000
Ja, så i bildformat, vad jag gör just?

591
00:45:44,000 --> 00:45:48,000
Jag har två saker. Jag har bild och bild.

592
00:45:48,000 --> 00:45:51,000
I bildformat, våra enstaka länkade listor,

593
00:45:51,000 --> 00:45:57,000
oundvikligen har vi någon form av pekare till chefen för vår lista,

594
00:45:57,000 --> 00:46:02,000
och sedan inom vår lista har vi bara pekare,

595
00:46:02,000 --> 00:46:05,000
och kanske tyder detta på null.

596
00:46:05,000 --> 00:46:08,000
Det kommer att vara din typiska ritning av en länkad enskilt lista.

597
00:46:08,000 --> 00:46:14,000
En dubbelt länkad lista, kan du gå bakåt.

598
00:46:14,000 --> 00:46:19,000
Om jag ger dig något nod i listan, kan du nödvändigtvis få till

599
00:46:19,000 --> 00:46:23,000
någon annan nod i listan om den är en dubbelt länkad lista.

600
00:46:23,000 --> 00:46:27,000
Men om jag får du den tredje noden i listan och det är en enstaka länkad lista,

601
00:46:27,000 --> 00:46:30,000
inget sätt du någonsin kommer att få den första och andra noder.

602
00:46:30,000 --> 00:46:34,000
Och det finns fördelar och nackdelar, och en uppenbar en

603
00:46:34,000 --> 00:46:42,000
är att ta dig upp mer storlek och du måste hålla reda på var dessa saker pekar nu.

604
00:46:42,000 --> 00:46:49,000
Men vi bryr sig bara om enstaka länkade.

605
00:46:49,000 --> 00:46:53,000
>> Några saker vi kommer att behöva genomföra.

606
00:46:53,000 --> 00:47:00,000
Din typedef struct nod, int i: struct nod * nästa; nod.

607
00:47:00,000 --> 00:47:09,000
Det typedef bör brännas in i dina sinnen.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 ska vara som ger en typedef av en länkad lista nod,

609
00:47:14,000 --> 00:47:18,000
och du bör omedelbart kunna klottra ner det

610
00:47:18,000 --> 00:47:22,000
utan att ens tänka på det.

611
00:47:22,000 --> 00:47:27,000
Jag antar ett par frågor, varför behöver vi Struct här?

612
00:47:27,000 --> 00:47:32,000
Varför kan vi inte säga nod *?

613
00:47:32,000 --> 00:47:35,000
[Student] [ohörbart]

614
00:47:35,000 --> 00:47:38,000
Ja.

615
00:47:38,000 --> 00:47:44,000
Det enda som definierar en nod som en sak

616
00:47:44,000 --> 00:47:47,000
är den typedef själv.

617
00:47:47,000 --> 00:47:55,000
Men som på denna punkt, när vi är typ av tolkning genom denna struct nod definition,

618
00:47:55,000 --> 00:48:01,000
vi har inte avslutat vår typedef ännu, så då typedef inte är klar,

619
00:48:01,000 --> 00:48:05,000
nod existerar inte.

620
00:48:05,000 --> 00:48:12,000
Men struct nod gör denna nod och här,

621
00:48:12,000 --> 00:48:14,000
Detta skulle också kunna kallas något annat.

622
00:48:14,000 --> 00:48:16,000
Detta skulle kunna kallas N.

623
00:48:16,000 --> 00:48:19,000
Det skulle kunna kallas länkad lista nod.

624
00:48:19,000 --> 00:48:21,000
Det skulle kunna kallas något.

625
00:48:21,000 --> 00:48:26,000
Men denna struct nod måste kallas samma sak som denna struct nod.

626
00:48:26,000 --> 00:48:29,000
Vad du kallar detta måste också vara här,

627
00:48:29,000 --> 00:48:32,000
och så att också ett svar på andra punkten i frågan

628
00:48:32,000 --> 00:48:37,000
vilket är anledningen till-många gånger när du ser structs och typedefs av structs,

629
00:48:37,000 --> 00:48:42,000
ser du anonyma structs där du bara se typedef struct,

630
00:48:42,000 --> 00:48:47,000
genomförandet av struktur, ordbok, eller något annat.

631
00:48:47,000 --> 00:48:51,000
>> Varför här behöver vi säga nod?

632
00:48:51,000 --> 00:48:54,000
Varför kan det inte vara en anonym struktur?

633
00:48:54,000 --> 00:48:56,000
Det är nästan samma svar.

634
00:48:56,000 --> 00:48:58,000
[Student] Du måste hänvisa till den inom struct.

635
00:48:58,000 --> 00:49:04,000
Ja, inom struct måste du referera till struct själv.

636
00:49:04,000 --> 00:49:10,000
Om du inte ger struct ett namn, om det är en anonym struct kan du inte hänvisa till den.

637
00:49:10,000 --> 00:49:17,000
Och sist men inte minst bör dessa alla vara något enkelt,

638
00:49:17,000 --> 00:49:20,000
och de bör hjälpa dig att inse om du skriver ner det

639
00:49:20,000 --> 00:49:24,000
att du gör något fel om dessa typer av saker inte vettigt.

640
00:49:24,000 --> 00:49:28,000
Sist men inte minst, varför det måste vara struct nod *?

641
00:49:28,000 --> 00:49:34,000
Varför kan det inte bara vara struct nod härnäst?

642
00:49:34,000 --> 00:49:37,000
[Student] Pekare till nästa struct.

643
00:49:37,000 --> 00:49:39,000
Det är oundvikligen vad vi vill.

644
00:49:39,000 --> 00:49:42,000
Varför kunde det aldrig struct nod härnäst?

645
00:49:42,000 --> 00:49:50,000
Varför måste det vara struct nod * nästa? Ja.

646
00:49:50,000 --> 00:49:53,000
[Student] Det är som en oändlig slinga.

647
00:49:53,000 --> 00:49:55,000
Ja.

648
00:49:55,000 --> 00:49:57,000
[Student] Det skulle alla vara i en.

649
00:49:57,000 --> 00:50:02,000
Ja, tänk bara på hur vi skulle göra storlek eller något.

650
00:50:02,000 --> 00:50:08,000
Storleken på en struktur är i grunden + eller - någon mönster här eller där.

651
00:50:08,000 --> 00:50:15,000
Det är i princip kommer att vara summan av storleken på saker i struct.

652
00:50:15,000 --> 00:50:18,000
Denna rätt här, utan att ändra något, är storleken kommer att bli lätt.

653
00:50:18,000 --> 00:50:24,000
Storlek på struct nod kommer att vara storleken på i + storlek nästa.

654
00:50:24,000 --> 00:50:27,000
Storlek I kommer att bli 4. Storlek på nästa kommer att bli 4.

655
00:50:27,000 --> 00:50:30,000
Storlek på struct nod kommer att bli 8.

656
00:50:30,000 --> 00:50:34,000
Om vi ​​inte har *, tänker på sizeof,

657
00:50:34,000 --> 00:50:37,000
sedan sizeof (i) kommer att vara 4.

658
00:50:37,000 --> 00:50:43,000
Storlek på struct nod nästa kommer att vara storleken på i + storlek struct nod nästa

659
00:50:43,000 --> 00:50:46,000
+ Storlek i + storlek struct nod nästa.

660
00:50:46,000 --> 00:50:55,000
Det skulle vara en oändlig rekursion av noder.

661
00:50:55,000 --> 00:51:00,000
Det är därför det är så det måste vara.

662
00:51:00,000 --> 00:51:03,000
>> Återigen, definitivt memorera det,

663
00:51:03,000 --> 00:51:06,000
eller åtminstone förstå det nog att du kan ha möjlighet att

664
00:51:06,000 --> 00:51:12,000
Därför igenom vad den ska se ut.

665
00:51:12,000 --> 00:51:14,000
De saker vi kommer att vilja genomföra.

666
00:51:14,000 --> 00:51:18,000
Om längden av listan-

667
00:51:18,000 --> 00:51:21,000
du kunde fuska och hålla runt en

668
00:51:21,000 --> 00:51:24,000
globala längd eller något, men vi kommer inte att göra det.

669
00:51:24,000 --> 00:51:28,000
Vi kommer att räkna längden på listan.

670
00:51:28,000 --> 00:51:34,000
Vi har innehåller, så det är i princip som en sökning,

671
00:51:34,000 --> 00:51:41,000
så vi har en länkad lista av heltal för att se om detta är heltal i den länkade listan.

672
00:51:41,000 --> 00:51:44,000
Prepend kommer att infoga i början av listan.

673
00:51:44,000 --> 00:51:46,000
Append kommer att infoga i slutet.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted kommer att infoga i den sorterade position i listan.

675
00:51:53,000 --> 00:52:01,000
Insert_sorted typ av förutsätter att du aldrig använt prefix eller lägga i dåliga sätt.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted när du genomföra insert_sorted-

677
00:52:09,000 --> 00:52:13,000
låt oss säga att vi har vår länkad lista.

678
00:52:13,000 --> 00:52:18,000
Detta är vad det för närvarande ser ut, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Jag vill infoga 3, så länge som själva listan redan sorteras,

680
00:52:24,000 --> 00:52:27,000
det är lätt att hitta där 3 hör.

681
00:52:27,000 --> 00:52:29,000
Jag börjar på 2.

682
00:52:29,000 --> 00:52:32,000
Okej, är 3 större än 2, så jag vill fortsätta.

683
00:52:32,000 --> 00:52:35,000
Åh, 4 för stor, så jag vet 3 kommer att gå mellan 2 och 4,

684
00:52:35,000 --> 00:52:39,000
och jag måste fixa pekare och allt det där.

685
00:52:39,000 --> 00:52:43,000
Men om vi inte strikt använder insert_sorted,

686
00:52:43,000 --> 00:52:50,000
liknande låt oss bara säga jag lägger du 6,

687
00:52:50,000 --> 00:52:55,000
då min länkad lista kommer att bli det.

688
00:52:55,000 --> 00:53:01,000
Det gör nu ingen mening, så för insert_sorted, kan du bara ta

689
00:53:01,000 --> 00:53:04,000
att listan är sorterad, även om verksamheten finns

690
00:53:04,000 --> 00:53:09,000
vilket kan göra att det inte sorteras, och det är det.

691
00:53:09,000 --> 00:53:20,000
Hitta en bra insats, så de är de viktigaste sakerna du kommer att behöva genomföra.

692
00:53:20,000 --> 00:53:24,000
>> För nu, ta en minut att göra längd och innehåller,

693
00:53:24,000 --> 00:53:30,000
och de bör vara relativt snabb.

694
00:53:41,000 --> 00:53:48,000
Nearing stängningstid, så någon har något för längd eller innehåller?

695
00:53:48,000 --> 00:53:50,000
De kommer att vara nästan identiska.

696
00:53:50,000 --> 00:53:57,000
[Elev] Längd.

697
00:53:57,000 --> 00:54:01,000
Låt oss se, ses över.

698
00:54:01,000 --> 00:54:04,000
Okej.

699
00:54:12,000 --> 00:54:15,000
Vill du förklara?

700
00:54:15,000 --> 00:54:21,000
[Student] Jag bara skapa en pekare nod och initiera den till först, vilket är vårt globala variabel,

701
00:54:21,000 --> 00:54:27,000
och då jag kontrollera om det är noll så jag inte får en seg fel och returnerar 0 om så är fallet.

702
00:54:27,000 --> 00:54:34,000
Annars jag genomkoppling, hålla reda på inom heltal

703
00:54:34,000 --> 00:54:38,000
hur många gånger jag har öppnat nästa element i listan

704
00:54:38,000 --> 00:54:43,000
och i samma inkrement verksamheten också komma att den faktiska element,

705
00:54:43,000 --> 00:54:47,000
och då gör jag hela tiden kontrollen för att se om det är noll,

706
00:54:47,000 --> 00:54:56,000
och om det är noll, då avbryter och bara returnerar antalet element jag har åtkomst.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Har någon några synpunkter på något?

708
00:55:01,000 --> 00:55:06,000
Detta ser bra ut korrekthet klokt.

709
00:55:06,000 --> 00:55:10,000
[Student] Jag tror inte du behöver noden == null.

710
00:55:10,000 --> 00:55:13,000
Ja, så om nod == null avkastning 0.

711
00:55:13,000 --> 00:55:18,000
Men om nod == null då detta-Åh, det är en riktig fråga.

712
00:55:18,000 --> 00:55:23,000
Det var bara du tillbaka i, men det är inte i omfattning just nu.

713
00:55:23,000 --> 00:55:30,000
Du behöver bara int i, så jag = 0.

714
00:55:30,000 --> 00:55:34,000
Men om noden är null, så jag är fortfarande kommer att vara 0,

715
00:55:34,000 --> 00:55:39,000
och vi kommer att återvända 0, så det här fallet är identiska.

716
00:55:39,000 --> 00:55:48,000
En annan vanlig sak är att intyget

717
00:55:48,000 --> 00:55:51,000
av nod inuti for-slingan.

718
00:55:51,000 --> 00:55:54,000
Man skulle kunna säga-åh, nej.

719
00:55:54,000 --> 00:55:56,000
Låt oss hålla det som denna.

720
00:55:56,000 --> 00:55:59,000
Jag skulle förmodligen sätta int i = 0 här,

721
00:55:59,000 --> 00:56:05,000
då nod * nod = första här.

722
00:56:05,000 --> 00:56:11,000
Och detta är förmodligen hur-att bli av detta nu.

723
00:56:11,000 --> 00:56:14,000
Detta är förmodligen hur jag skulle ha skrivit den.

724
00:56:14,000 --> 00:56:21,000
Du kan också, titta på det så här.

725
00:56:21,000 --> 00:56:25,000
Detta för öglestruktur här

726
00:56:25,000 --> 00:56:30,000
bör vara nästan lika naturligt för dig som för int i = 0

727
00:56:30,000 --> 00:56:33,000
i är mindre än längden av matris i + +.

728
00:56:33,000 --> 00:56:38,000
Om det är hur du iterera över en array, det är hur du iterera över en länkad lista.

729
00:56:38,000 --> 00:56:45,000
>> Detta bör vara en självklarhet vid något tillfälle.

730
00:56:45,000 --> 00:56:50,000
Med detta i åtanke, detta kommer att bli nästan samma sak.

731
00:56:50,000 --> 00:56:57,000
Du kommer att vilja att iterera över en länkad lista.

732
00:56:57,000 --> 00:57:02,000
Om nod-Jag har ingen aning om vad värdet heter.

733
00:57:02,000 --> 00:57:04,000
Nod i..

734
00:57:04,000 --> 00:57:15,000
Om värdet vid den noden = jag tillbaka sant, och det är det.

735
00:57:15,000 --> 00:57:18,000
Observera att det enda sättet vi någonsin återvända falska

736
00:57:18,000 --> 00:57:23,000
är om vi iterera över den länkade hela listan och aldrig återvända sant,

737
00:57:23,000 --> 00:57:29,000
så det är vad det gör.

738
00:57:29,000 --> 00:57:36,000
Som en sida noterar, vi förmodligen inte kommer att få lägga eller lägger du.

739
00:57:36,000 --> 00:57:39,000
>> Snabb sista anmärkning.

740
00:57:39,000 --> 00:57:52,000
Om du ser nyckelordet static, så låt oss säga static int count = 0,

741
00:57:52,000 --> 00:57:56,000
vi räknas + +, kan du i princip se det som en global variabel,

742
00:57:56,000 --> 00:58:00,000
även om jag sagt just detta är inte hur vi ska genomföra längd.

743
00:58:00,000 --> 00:58:06,000
Jag gör det här, och sedan räkna + +.

744
00:58:06,000 --> 00:58:11,000
Något sätt vi kan ange en nod i vår länkad lista vi uppräkning vår räkning.

745
00:58:11,000 --> 00:58:15,000
Poängen med detta är vad nyckelordet static betyder.

746
00:58:15,000 --> 00:58:20,000
Om jag bara hade int count = 0 som skulle vara en vanlig gammal global variabel.

747
00:58:20,000 --> 00:58:25,000
Vilka static int count betyder att det är en global variabel för denna fil.

748
00:58:25,000 --> 00:58:28,000
Det är omöjligt för någon annan fil,

749
00:58:28,000 --> 00:58:34,000
gillar att tänka på pset 5, om du har börjat.

750
00:58:34,000 --> 00:58:39,000
Du har både speller.c, och du har dictionary.c,

751
00:58:39,000 --> 00:58:42,000
och om du deklarerar bara en sak global, sedan något i speller.c

752
00:58:42,000 --> 00:58:45,000
kan nås i dictionary.c och vice versa.

753
00:58:45,000 --> 00:58:48,000
Globala variabler är tillgängliga för alla. C. fil,

754
00:58:48,000 --> 00:58:54,000
men statiska variabler är endast tillgängliga inifrån själva filen,

755
00:58:54,000 --> 00:59:01,000
så inne i stavningskontroll eller insidan av dictionary.c,

756
00:59:01,000 --> 00:59:06,000
Detta är typ av hur jag skulle förklara min variabel för storleken på min array

757
00:59:06,000 --> 00:59:10,000
eller storleken på min antal ord i ordlistan.

758
00:59:10,000 --> 00:59:15,000
Eftersom jag inte vill att deklarera en global variabel som någon har tillgång till,

759
00:59:15,000 --> 00:59:18,000
Jag verkligen bara bryr sig om det för mina egna syften.

760
00:59:18,000 --> 00:59:21,000
>> Det som är bra med detta är också hela namnet kollision grejer.

761
00:59:21,000 --> 00:59:27,000
Om någon annan fil försöker använda en global variabel som heter räkna, det går mycket, mycket fel,

762
00:59:27,000 --> 00:59:33,000
så detta håller fint saker säkert och bara du kan komma åt den,

763
00:59:33,000 --> 00:59:38,000
och ingen annan kan, och om någon annan deklarerar en global variabel som heter räkna,

764
00:59:38,000 --> 00:59:43,000
då det inte kommer att störa din statisk variabel som kallas räknas.

765
00:59:43,000 --> 00:59:47,000
Det är vad statisk är. Det är en fil global variabel.

766
00:59:47,000 --> 00:59:52,000
>> Frågor om vad som helst?

767
00:59:52,000 --> 00:59:59,000
Allt klart. Hej då.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]