1
00:00:00,000 --> 00:00:03,000
[Powered by Google Translate] [Recension] [Frågesport 0]

2
00:00:03,000 --> 00:00:05,000
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]

3
00:00:05,000 --> 00:00:08,000
>> [Detta är CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:10,000
>> Hej, alla.

5
00:00:10,000 --> 00:00:15,000
Välkommen till översyn sessionen för Quiz 0, vilket sker på onsdag.

6
00:00:15,000 --> 00:00:19,000
Vad vi ska göra ikväll, jag med 3 andra TF,

7
00:00:19,000 --> 00:00:24,000
och tillsammans ska vi gå igenom en översyn av vad vi har gjort i kursen hittills.

8
00:00:24,000 --> 00:00:27,000
Det kommer inte att vara 100% heltäckande, men det bör ge dig en bättre uppfattning

9
00:00:27,000 --> 00:00:31,000
vad du redan har ner och vad du fortfarande behöver studera innan onsdag.

10
00:00:31,000 --> 00:00:34,000
Och gärna upp handen med frågor som vi kommer tillsammans,

11
00:00:34,000 --> 00:00:38,000
men tänk på att vi också kommer att ha lite tid i slutet,

12
00:00:38,000 --> 00:00:41,000
om vi får igenom med några minuter till godo, för att göra allmänna frågor,

13
00:00:41,000 --> 00:00:47,000
så håll detta i åtanke, och så ska vi börja från början med vecka 0.

14
00:00:47,000 --> 00:00:50,000
>> [Quiz 0 recension!] [Del 0] [Lexi Ross] Men innan vi gör det ska vi prata om

15
00:00:50,000 --> 00:00:53,000
logistiken för testet.

16
00:00:53,000 --> 00:00:55,000
>> [Logistik] [Quiz sker på onsdag 10/10 i stället för föreläsning]

17
00:00:55,000 --> 00:00:57,000
>> [(Se http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf för detaljer)] Det är på onsdag 10 OKTOBER.

18
00:00:57,000 --> 00:01:00,000
>> Det är denna onsdag, och om du går till denna URL här,

19
00:01:00,000 --> 00:01:03,000
som också nås från CS50.net-det finns en länk till den-

20
00:01:03,000 --> 00:01:06,000
Du kan se information om vart man vänder sig utifrån

21
00:01:06,000 --> 00:01:10,000
ditt efternamn eller skola tillhörighet samt

22
00:01:10,000 --> 00:01:14,000
Det berättar om exakt vad testet kommer att täcka och vilka typer av frågor som du kommer att få.

23
00:01:14,000 --> 00:01:19,000
Tänk på att du också kommer att ha en chans att granska för frågesporten i snitt,

24
00:01:19,000 --> 00:01:21,000
så att dina TF bör gå över några praktiska problem,

25
00:01:21,000 --> 00:01:29,000
och det är en annan bra chans att se var du fortfarande behöver studera upp för testet.

26
00:01:29,000 --> 00:01:32,000
Låt oss börja från början med bitar 'n' byte.

27
00:01:32,000 --> 00:01:35,000
Kom ihåg att en bit är bara en 0 eller en 1,

28
00:01:35,000 --> 00:01:38,000
och ett byte är en samling av 8 av dessa bitar.

29
00:01:38,000 --> 00:01:42,000
Låt oss titta på denna samling av bitar här.

30
00:01:42,000 --> 00:01:44,000
Vi borde kunna räkna ut hur många bitar som finns.

31
00:01:44,000 --> 00:01:48,000
Där vi räknar det finns bara 8 av dem, åtta 0 eller 1 enheter.

32
00:01:48,000 --> 00:01:51,000
Och eftersom det finns 8 bitar, det är 1 byte,

33
00:01:51,000 --> 00:01:53,000
och låt oss omvandla den till hexadecimalt.

34
00:01:53,000 --> 00:01:58,000
Hexadecimal är basen 16, och det är ganska enkelt att konvertera

35
00:01:58,000 --> 00:02:01,000
ett tal i binär, vilket är vad det är, till ett nummer i hexadecimalt.

36
00:02:01,000 --> 00:02:04,000
Allt vi gör är att vi tittar på grupper av 4,

37
00:02:04,000 --> 00:02:07,000
och vi konvertera dem till rätt hexadecimala siffran.

38
00:02:07,000 --> 00:02:11,000
Vi börjar med längst till höger grupp 4, så 0011.

39
00:02:11,000 --> 00:02:16,000
Det kommer att bli en 1 och en 2, så tillsammans som gör 3.

40
00:02:16,000 --> 00:02:19,000
Och låt oss titta på det andra blocket av 4.

41
00:02:19,000 --> 00:02:24,000
1101. Det kommer att bli en 1, en 4, och en 8.

42
00:02:24,000 --> 00:02:28,000
Tillsammans som kommer att vara 13, vilket gör D

43
00:02:28,000 --> 00:02:32,000
Och vi kommer ihåg att i hexadecimal vi inte bara gå 0 till 9.

44
00:02:32,000 --> 00:02:36,000
Vi går 0 till F, så efter 9, 10 motsvarar en,

45
00:02:36,000 --> 00:02:40,000
11 till B, et cetera där F är 15.

46
00:02:40,000 --> 00:02:44,000
Här 13 är ett D,

47
00:02:44,000 --> 00:02:49,000
så att omvandla det till decimal allt vi gör är att vi faktiskt

48
00:02:49,000 --> 00:02:52,000
behandla varje position som en effekt av 2.

49
00:02:52,000 --> 00:02:58,000
Det är en 1, en 2, noll 4S, noll 8s, en 16, et cetera,

50
00:02:58,000 --> 00:03:03,000
och det är lite svårt att beräkna i huvudet, men om vi går till nästa bild

51
00:03:03,000 --> 00:03:05,000
kan vi se svaret på den.

52
00:03:05,000 --> 00:03:09,000
>> I huvudsak ska vi över från höger till vänster,

53
00:03:09,000 --> 00:03:14,000
och vi multiplicera varje siffra med motsvarande makt 2.

54
00:03:14,000 --> 00:03:19,000
Och kom ihåg, för hexadecimala vi beteckna dessa siffror med 0x i början

55
00:03:19,000 --> 00:03:23,000
så vi blanda inte ihop det med ett decimaltal.

56
00:03:23,000 --> 00:03:29,000
Fortsätter, är det en ASCII tabell,

57
00:03:29,000 --> 00:03:35,000
och vad vi använder ASCII för är att kartlägga från tecken till numeriska värden.

58
00:03:35,000 --> 00:03:39,000
Tänk på kryptografi pset vi gjort omfattande användning av ASCII tabellen

59
00:03:39,000 --> 00:03:43,000
För att använda olika metoder för kryptografi,

60
00:03:43,000 --> 00:03:47,000
Caesar och Vigenère chiffer, konvertera olika bokstäver

61
00:03:47,000 --> 00:03:52,000
i en sträng enligt nyckeln ges av användaren.

62
00:03:52,000 --> 00:03:56,000
Låt oss titta på lite ASCII matematik.

63
00:03:56,000 --> 00:04:02,000
Titta på "P" + 1, karaktär form som skulle vara Q,

64
00:04:02,000 --> 00:04:07,000
och kom ihåg att '5 '≠ 5.

65
00:04:07,000 --> 00:04:10,000
Och hur exakt skulle vi konvertera mellan dessa 2 formerna?

66
00:04:10,000 --> 00:04:13,000
Det är faktiskt inte så svårt.

67
00:04:13,000 --> 00:04:16,000
För att få 5 vi subtrahera '0 '

68
00:04:16,000 --> 00:04:20,000
eftersom det finns 5 platser mellan '0 'och 5. "

69
00:04:20,000 --> 00:04:23,000
För att gå åt andra hållet vi bara lägga till 0,

70
00:04:23,000 --> 00:04:25,000
så det är ungefär som vanligt aritmetik.

71
00:04:25,000 --> 00:04:29,000
Kom bara ihåg att när något har citattecken runt det är det ett tecken

72
00:04:29,000 --> 00:04:37,000
och således motsvarar ett värde i ASCII-tabellen.

73
00:04:37,000 --> 00:04:40,000
Flytta till mer allmänna ämnen datavetenskap.

74
00:04:40,000 --> 00:04:43,000
Vi lärde mig vad en algoritm är och hur vi använder programmering

75
00:04:43,000 --> 00:04:45,000
att implementera algoritmer.

76
00:04:45,000 --> 00:04:48,000
Några exempel på algoritmer är något riktigt enkelt som

77
00:04:48,000 --> 00:04:51,000
kontrollera huruvida ett antal är jämnt eller udda.

78
00:04:51,000 --> 00:04:54,000
För att minns vi mod antalet med 2 och kontrollera om resultatet är 0.

79
00:04:54,000 --> 00:04:57,000
Om så är fallet, är det ännu. Om inte, är det konstigt.

80
00:04:57,000 --> 00:04:59,000
Och det är ett exempel på en riktigt basic algoritm.

81
00:04:59,000 --> 00:05:02,000
>> En liten bit av en mer engagerade en är binär sökning,

82
00:05:02,000 --> 00:05:05,000
som vi ska gå över senare i recensionen sessionen.

83
00:05:05,000 --> 00:05:09,000
Och programmering är den term vi använder för att ta en algoritm

84
00:05:09,000 --> 00:05:15,000
och omvandla den till koda datorn kan läsa.

85
00:05:15,000 --> 00:05:20,000
2 exempel på programmering är Scratch,

86
00:05:20,000 --> 00:05:22,000
vilket är vad vi gjorde i vecka 0.

87
00:05:22,000 --> 00:05:25,000
Även om vi inte egentligen skriver ut koden är det ett sätt att genomföra

88
00:05:25,000 --> 00:05:29,000
denna algoritm, som skriver siffrorna 1-10,

89
00:05:29,000 --> 00:05:32,000
och här gör vi samma sak i programmeringsspråket C.

90
00:05:32,000 --> 00:05:41,000
Dessa är funktionellt likvärdig, just skrivit på olika språk eller syntax.

91
00:05:41,000 --> 00:05:44,000
Vi lärde då om booleska uttryck,

92
00:05:44,000 --> 00:05:48,000
och ett booleskt är ett värde som är antingen sant eller falskt,

93
00:05:48,000 --> 00:05:51,000
och här ofta booleska uttryck

94
00:05:51,000 --> 00:05:55,000
gå in villkor, så om (x ≤ 5),

95
00:05:55,000 --> 00:06:00,000
bra, satte vi redan x = 5, så att villkoret kommer att utvärderas till sant.

96
00:06:00,000 --> 00:06:03,000
Och om det är sant, är vad koden under villkoret

97
00:06:03,000 --> 00:06:08,000
kommer att utvärderas av datorn, så att strängen ska skrivas

98
00:06:08,000 --> 00:06:12,000
till standard ut, och termen tillstånd

99
00:06:12,000 --> 00:06:16,000
hänvisar till vad som är inom parentes i if.

100
00:06:16,000 --> 00:06:20,000
Tänk alla operatörer.

101
00:06:20,000 --> 00:06:26,000
Kom ihåg att det är && och | | när vi försöker kombinera 2 eller fler villkor,

102
00:06:26,000 --> 00:06:30,000
== Inte = att kontrollera om 2 saker är lika.

103
00:06:30,000 --> 00:06:36,000
Kom ihåg att = är för tilldelning medan == är ett booleskt operatör.

104
00:06:36,000 --> 00:06:41,000
≤, ≥ och sedan sista 2 är självförklarande.

105
00:06:41,000 --> 00:06:45,000
En allmän översyn av boolesk logik här.

106
00:06:45,000 --> 00:06:48,000
Och booleska uttryck är också viktiga i slingor,

107
00:06:48,000 --> 00:06:50,000
som vi ska gå över nu.

108
00:06:50,000 --> 00:06:56,000
Vi lärde oss om 3 typer av slingor hittills i CS50, för, medan och göra medan.

109
00:06:56,000 --> 00:06:59,000
Och det är viktigt att veta att medan de flesta ändamål

110
00:06:59,000 --> 00:07:02,000
Vi kan faktiskt använda någon typ av loop allmänhet

111
00:07:02,000 --> 00:07:06,000
Det finns vissa typer av ändamål eller gemensamma mönster

112
00:07:06,000 --> 00:07:09,000
i programmering som specifikt kräver en av dessa slingor

113
00:07:09,000 --> 00:07:13,000
som gör den till den mest effektiva eller elegant att koda det på det sättet.

114
00:07:13,000 --> 00:07:18,000
Låt oss gå igenom vad var och en av dessa slingor tenderar att användas för oftast.

115
00:07:18,000 --> 00:07:21,000
>> I en for-slinga vi i allmänhet redan vet hur många gånger vi vill iterera.

116
00:07:21,000 --> 00:07:24,000
Det är vad vi lägger i tillståndet.

117
00:07:24,000 --> 00:07:28,000
För i = 0, i <10, till exempel.

118
00:07:28,000 --> 00:07:31,000
Vi vet redan att vi vill göra något 10 gånger.

119
00:07:31,000 --> 00:07:34,000
Nu, för en while-slinga, i allmänhet vi inte nödvändigtvis

120
00:07:34,000 --> 00:07:36,000
vet hur många gånger vi vill att slingan ska köras.

121
00:07:36,000 --> 00:07:39,000
Men vi vet något slags förutsättning att vi vill att det ska

122
00:07:39,000 --> 00:07:41,000
alltid vara sant eller alltid vara falskt.

123
00:07:41,000 --> 00:07:44,000
Exempelvis när inställd.

124
00:07:44,000 --> 00:07:46,000
Låt oss säga att det är en boolesk variabel.

125
00:07:46,000 --> 00:07:48,000
Även om det är sant att vi vill att koden för att utvärdera,

126
00:07:48,000 --> 00:07:52,000
så lite mer töjbart lite mer generell än en for-slinga,

127
00:07:52,000 --> 00:07:55,000
men någon för slingan kan också omvandlas till en while-slinga.

128
00:07:55,000 --> 00:08:00,000
Slutligen göra medan slingor, som kan vara den svåraste att förstå direkt,

129
00:08:00,000 --> 00:08:04,000
används ofta när vi vill utvärdera först koden

130
00:08:04,000 --> 00:08:06,000
före första gången vi kontrollera tillståndet.

131
00:08:06,000 --> 00:08:09,000
En vanlig användning för en göra medan slinga

132
00:08:09,000 --> 00:08:12,000
är när du vill få indata, och du vet att du vill fråga användaren

133
00:08:12,000 --> 00:08:15,000
för inmatning åtminstone en gång, men om de inte ger dig bra ingång direkt

134
00:08:15,000 --> 00:08:18,000
du vill hålla ber dem tills de ger dig goda ingången.

135
00:08:18,000 --> 00:08:21,000
Det är den vanligaste användningen av en gör while-slinga,

136
00:08:21,000 --> 00:08:23,000
och låt oss titta på den konkreta utformningen av dessa slingor.

137
00:08:23,000 --> 00:08:27,000
De oftast alltid tenderar att följa dessa mönster.

138
00:08:27,000 --> 00:08:30,000
>> På for-slingan inuti du har 3 komponenter:

139
00:08:30,000 --> 00:08:35,000
initiering, vanligtvis något som int i = 0 där i är räknaren,

140
00:08:35,000 --> 00:08:40,000
tillstånd, där vi vill säga köra detta för slingan så länge detta tillstånd fortfarande innehar,

141
00:08:40,000 --> 00:08:44,000
som jag <10, och slutligen, uppdatera, vilket är hur vi öka

142
00:08:44,000 --> 00:08:47,000
räknarvariabeln vid varje punkt i slingan.

143
00:08:47,000 --> 00:08:50,000
En vanlig sak att se det är bara jag + +,

144
00:08:50,000 --> 00:08:52,000
vilket innebär öka i med 1 varje gång.

145
00:08:52,000 --> 00:08:55,000
Du kan också göra något som jag + = 2,

146
00:08:55,000 --> 00:08:58,000
vilket innebär tillsätt 2 till I varje gång du går genom öglan.

147
00:08:58,000 --> 00:09:03,000
Och sedan göra detta bara avser varje kod som faktiskt körs som en del av slingan.

148
00:09:03,000 --> 00:09:09,000
Och för en while-slinga, denna gång har vi faktiskt initieringen utanför slingan,

149
00:09:09,000 --> 00:09:12,000
så till exempel, låt oss säga att vi försöker göra samma typ av loop som jag just beskrivit.

150
00:09:12,000 --> 00:09:16,000
Vi skulle säga int i = 0 innan loopen börjar.

151
00:09:16,000 --> 00:09:20,000
Då skulle vi kunna säga medan jag <10 gör detta,

152
00:09:20,000 --> 00:09:22,000
så samma block av kod som tidigare,

153
00:09:22,000 --> 00:09:26,000
och den här gången uppdateringen del av koden, till exempel i + +,

154
00:09:26,000 --> 00:09:29,000
faktiskt går in i slingan.

155
00:09:29,000 --> 00:09:33,000
Och slutligen, för en göra medan, är det liknar while-slingan,

156
00:09:33,000 --> 00:09:36,000
men vi måste komma ihåg att koden kommer att utvärdera en gång

157
00:09:36,000 --> 00:09:40,000
innan tillståndet kontrolleras, så det är mycket mer känsla

158
00:09:40,000 --> 00:09:44,000
om man tittar på det i ordning uppifrån och ned.

159
00:09:44,000 --> 00:09:49,000
I en göra medan slinga koden utvärderar innan du ens titta på medan du kondition,

160
00:09:49,000 --> 00:09:55,000
medan en while-slinga, kontrollerar den först.

161
00:09:55,000 --> 00:09:59,000
Uttalanden och variabler.

162
00:09:59,000 --> 00:10:04,000
När vi vill skapa en ny variabel som vi vill först initiera den.

163
00:10:04,000 --> 00:10:07,000
>> Till exempel initierar int bar den rörliga baren,

164
00:10:07,000 --> 00:10:10,000
men det ger den ett värde, så vad är bar värde nu?

165
00:10:10,000 --> 00:10:12,000
Vi vet inte.

166
00:10:12,000 --> 00:10:14,000
Det kan vara något skräp värde som tidigare lagrats i minnet där,

167
00:10:14,000 --> 00:10:16,000
och vi vill inte använda denna variabel

168
00:10:16,000 --> 00:10:19,000
tills vi ger faktiskt ett värde,

169
00:10:19,000 --> 00:10:21,000
så vi förklara den här.

170
00:10:21,000 --> 00:10:24,000
Då vi initiera det är 42 nedan.

171
00:10:24,000 --> 00:10:28,000
Nu, naturligtvis, vet vi att detta kan ske på en rad, int bar = 42.

172
00:10:28,000 --> 00:10:30,000
Men bara att rensa flera steg som pågår,

173
00:10:30,000 --> 00:10:34,000
deklarationen och initiering händer separat här.

174
00:10:34,000 --> 00:10:38,000
Det händer på ett steg, och nästa, int Baz = bar + 1,

175
00:10:38,000 --> 00:10:44,000
detta uttalande nedan, att steg Baz, så i slutet av denna kodblock

176
00:10:44,000 --> 00:10:48,000
om vi skulle skriva ut värdet av baz skulle det vara 44

177
00:10:48,000 --> 00:10:52,000
eftersom vi förklara och initiera att det 1> bar,

178
00:10:52,000 --> 00:10:58,000
och då vi öka den igen med + +.

179
00:10:58,000 --> 00:11:02,000
Vi gick över denna vackra kort, men det är bra att ha en allmän

180
00:11:02,000 --> 00:11:04,000
förståelse för vad trådar och händelser är.

181
00:11:04,000 --> 00:11:06,000
Vi gjorde främst detta i Scratch,

182
00:11:06,000 --> 00:11:09,000
så du kan tänka på trådar som flera sekvenser av kod

183
00:11:09,000 --> 00:11:11,000
körs samtidigt.

184
00:11:11,000 --> 00:11:14,000
I själva verket är det förmodligen inte är igång samtidigt,

185
00:11:14,000 --> 00:11:17,000
men typ av abstrakt kan vi tänka på det på det sättet.

186
00:11:17,000 --> 00:11:20,000
>> I Scratch, till exempel, hade vi flera sprites.

187
00:11:20,000 --> 00:11:22,000
Det skulle kunna exekvera annan kod på samma gång.

188
00:11:22,000 --> 00:11:26,000
Man kan gå medan den andra säger något

189
00:11:26,000 --> 00:11:29,000
i en annan del av skärmen.

190
00:11:29,000 --> 00:11:34,000
Evenemang är ett annat sätt att separera ut logiken

191
00:11:34,000 --> 00:11:37,000
mellan olika delar av din kod,

192
00:11:37,000 --> 00:11:40,000
och i Scratch kunde vi simulera händelser med Broadcast,

193
00:11:40,000 --> 00:11:43,000
och det är faktiskt när jag får, inte när jag hör,

194
00:11:43,000 --> 00:11:47,000
men i huvudsak är det ett sätt att överföra information

195
00:11:47,000 --> 00:11:49,000
från en sprite till en annan.

196
00:11:49,000 --> 00:11:52,000
Till exempel kanske du vill sända game over,

197
00:11:52,000 --> 00:11:56,000
och när en annan sprite får game over,

198
00:11:56,000 --> 00:11:58,000
den svarar på ett visst sätt.

199
00:11:58,000 --> 00:12:03,000
Det är en viktig modell för att förstå för programmering.

200
00:12:03,000 --> 00:12:07,000
Bara att gå över den grundläggande Vecka 0, vad vi har gått över så långt,

201
00:12:07,000 --> 00:12:10,000
låt oss titta på detta enkla C-program.

202
00:12:10,000 --> 00:12:14,000
Texten kan vara lite små härifrån, men jag ska gå igenom det riktigt snabbt.

203
00:12:14,000 --> 00:12:20,000
Vi inklusive 2 huvudfiler överst, cs50.h och stdio.h.

204
00:12:20,000 --> 00:12:23,000
Vi sedan definiera en konstant kallad gräns till 100.

205
00:12:23,000 --> 00:12:26,000
Vi sedan genomföra vår huvuduppgift.

206
00:12:26,000 --> 00:12:29,000
Eftersom vi inte använder kommandoradsargument här vi måste sätta ogiltig

207
00:12:29,000 --> 00:12:32,000
som argument för stora.

208
00:12:32,000 --> 00:12:38,000
Vi ser int ovan huvud. Det är returtyp, därför återvänder 0 i botten.

209
00:12:38,000 --> 00:12:41,000
Och vi använder CS50 biblioteksfunktion få int

210
00:12:41,000 --> 00:12:45,000
att uppmana användaren för inmatning, och lagrar vi det i denna variabeln x,

211
00:12:45,000 --> 00:12:51,000
så vi förklarar X ovan, och vi initiera den med x = getInt.

212
00:12:51,000 --> 00:12:53,000
>> Vi kontrollerar sedan att se om användaren gav oss bra ingång.

213
00:12:53,000 --> 00:12:59,000
Om det är ≥ begränsar vi vill returnera en felkod av 1 och skriva ut ett felmeddelande.

214
00:12:59,000 --> 00:13:02,000
Och slutligen, om användaren har gett oss bra ingång

215
00:13:02,000 --> 00:13:08,000
vi kommer att förena numret och skriva ut resultatet.

216
00:13:08,000 --> 00:13:11,000
Bara för att se till att de alla hit hem

217
00:13:11,000 --> 00:13:17,000
kan du se märken hos olika delar av koden här.

218
00:13:17,000 --> 00:13:19,000
Jag nämnde konstant, header-filer.

219
00:13:19,000 --> 00:13:21,000
Åh, int x. Se till att komma ihåg att det är en lokal variabel.

220
00:13:21,000 --> 00:13:24,000
Som kontrasterar det från en global variabel som vi pratar om

221
00:13:24,000 --> 00:13:27,000
lite senare i recensionen sessionen,

222
00:13:27,000 --> 00:13:30,000
och vi kallar biblioteket funktionen printf,

223
00:13:30,000 --> 00:13:34,000
så om vi inte hade inkluderat stdio.h sidhuvudfilen

224
00:13:34,000 --> 00:13:37,000
Vi skulle inte kunna ringa printf.

225
00:13:37,000 --> 00:13:42,000
Och jag tror pilen som fick avskurna här pekar på% d,

226
00:13:42,000 --> 00:13:45,000
som är en formatering sträng i printf.

227
00:13:45,000 --> 00:13:52,000
Det säger skriva ut denna variabel som ett tal,% d.

228
00:13:52,000 --> 00:13:58,000
Och det är det för vecka 0.

229
00:13:58,000 --> 00:14:06,000
Nu Lucas kommer att fortsätta.

230
00:14:06,000 --> 00:14:08,000
Hej, grabbar. Mitt namn är Lucas.

231
00:14:08,000 --> 00:14:10,000
Jag är en andraårsstuderande i bästa huset på campus, Mather,

232
00:14:10,000 --> 00:14:14,000
och jag ska prata lite om vecka 1 och 2,1.

233
00:14:14,000 --> 00:14:16,000
[Vecka 1 och 2,1!] [Lucas Freitas]

234
00:14:16,000 --> 00:14:19,000
Som Lexi sa, när vi började översätta koden från Scratch till C

235
00:14:19,000 --> 00:14:23,000
en av de saker som vi märkt är att du kan inte bara

236
00:14:23,000 --> 00:14:26,000
skriv din kod och köra den med en grön flagga längre.

237
00:14:26,000 --> 00:14:30,000
Egentligen måste du använda några steg för att göra din C-program

238
00:14:30,000 --> 00:14:33,000
bli en körbar fil.

239
00:14:33,000 --> 00:14:36,000
I grund och botten vad du gör när du skriver ett program är att

240
00:14:36,000 --> 00:14:40,000
du översätter din idé till ett språk som en kompilator kan förstå,

241
00:14:40,000 --> 00:14:44,000
så när du skriver ett program i C

242
00:14:44,000 --> 00:14:47,000
vad du gör är faktiskt skriva något som din kompilator kommer att förstå,

243
00:14:47,000 --> 00:14:50,000
och därefter kompilatorn kommer att omsätta denna kod

244
00:14:50,000 --> 00:14:53,000
till något som datorn förstår.

245
00:14:53,000 --> 00:14:55,000
>> Och saken är, är din dator faktiskt mycket dum.

246
00:14:55,000 --> 00:14:57,000
Datorn kan bara förstå 0s och 1s,

247
00:14:57,000 --> 00:15:01,000
så faktiskt i de första datorerna folk programmeras vanligtvis

248
00:15:01,000 --> 00:15:04,000
med 0 och 1, men inte längre, tack och lov.

249
00:15:04,000 --> 00:15:07,000
Vi behöver inte memorera sekvenserna för 0 och 1

250
00:15:07,000 --> 00:15:10,000
för en for-slinga eller en while-slinga och så vidare.

251
00:15:10,000 --> 00:15:13,000
Det är därför vi har en kompilator.

252
00:15:13,000 --> 00:15:17,000
Vad en kompilator gör är det i grunden översätter C-kod,

253
00:15:17,000 --> 00:15:21,000
i vårt fall, till ett språk som datorn förstår,

254
00:15:21,000 --> 00:15:25,000
som är föremål kod och kompilatorn att vi använder

255
00:15:25,000 --> 00:15:30,000
heter klang, så detta är verkligen en symbol för klang.

256
00:15:30,000 --> 00:15:33,000
När du har ditt program, måste du göra 2 saker.

257
00:15:33,000 --> 00:15:37,000
Först måste du kompilera ditt program, och då du kommer att köra ditt program.

258
00:15:37,000 --> 00:15:41,000
För att kompilera ditt program har du många alternativ att göra det.

259
00:15:41,000 --> 00:15:44,000
Den första är att göra klang program.c

260
00:15:44,000 --> 00:15:47,000
i vilket program är namnet på ditt program.

261
00:15:47,000 --> 00:15:51,000
I det här fallet kan du se de bara säger "Hej, kompilera mitt program."

262
00:15:51,000 --> 00:15:56,000
Du säger inte "Jag vill ha det här namnet mitt program" eller något.

263
00:15:56,000 --> 00:15:58,000
>> Det andra alternativet är att ge ett namn till ditt program.

264
00:15:58,000 --> 00:16:02,000
Du kan säga klang-o och sedan namnet som du vill

265
00:16:02,000 --> 00:16:06,000
den körbara filen som ska namnges som sedan program.c.

266
00:16:06,000 --> 00:16:11,000
Och du kan också göra att program och se hur de första 2 fall

267
00:16:11,000 --> 00:16:15,000
Jag satte. C, och i den tredje jag har bara program?

268
00:16:15,000 --> 00:16:18,000
Ja, du faktiskt inte ska lägga. C. när du använder gör.

269
00:16:18,000 --> 00:16:22,000
Annars kompilatorn faktiskt kommer att skrika på dig.

270
00:16:22,000 --> 00:16:24,000
Och även jag vet inte om ni minns,

271
00:16:24,000 --> 00:16:29,000
men många gånger vi använt-lcs50 eller-LM.

272
00:16:29,000 --> 00:16:31,000
Det kallas länkning.

273
00:16:31,000 --> 00:16:35,000
Den talar bara kompilatorn att du kommer att använda dessa bibliotek där,

274
00:16:35,000 --> 00:16:39,000
så om du vill använda cs50.h du faktiskt skriva

275
00:16:39,000 --> 00:16:43,000
klang program.c-lcs50.

276
00:16:43,000 --> 00:16:45,000
Om du inte gör det, är kompilatorn kommer inte att veta

277
00:16:45,000 --> 00:16:50,000
att du använder dessa funktioner i cs50.h.

278
00:16:50,000 --> 00:16:52,000
Och när du vill köra ditt program har du 2 alternativ.

279
00:16:52,000 --> 00:16:57,000
Om du gjorde klang program.c du inte namnge ditt program.

280
00:16:57,000 --> 00:17:01,000
Du måste köra det med. / A.out.

281
00:17:01,000 --> 00:17:06,000
A.out är en standard namn som klang ger ditt program om du inte ge den ett namn.

282
00:17:06,000 --> 00:17:11,000
Annars du kommer att göra. / Program om du gav ett namn till ditt program,

283
00:17:11,000 --> 00:17:15,000
och även om du gjorde programmet det namn som ett program kommer att få

284
00:17:15,000 --> 00:17:23,000
redan kommer att programmeras med samma namn som C-fil.

285
00:17:23,000 --> 00:17:26,000
Sen pratade vi om datatyper och data.

286
00:17:26,000 --> 00:17:31,000
>> I grund och botten datatyper är samma sak som små lådor som de använder

287
00:17:31,000 --> 00:17:35,000
att lagra värden, så datatyper är faktiskt precis som Pokemons.

288
00:17:35,000 --> 00:17:39,000
De finns i alla storlekar och typer.

289
00:17:39,000 --> 00:17:43,000
Jag vet inte om det analogi är vettigt.

290
00:17:43,000 --> 00:17:46,000
Uppgifterna storlek beror faktiskt på maskinens arkitektur.

291
00:17:46,000 --> 00:17:49,000
Alla data storlekar som jag kommer att visa här

292
00:17:49,000 --> 00:17:53,000
är faktiskt för en 32-bitars maskin, vilket är fallet med vår apparat,

293
00:17:53,000 --> 00:17:56,000
men om du faktiskt koda din Mac eller Windows också

294
00:17:56,000 --> 00:17:59,000
förmodligen du kommer att ha en 64-bitars maskin,

295
00:17:59,000 --> 00:18:03,000
så kom ihåg att data storlekar som jag kommer att visa här

296
00:18:03,000 --> 00:18:06,000
är för 32-bitars maskin.

297
00:18:06,000 --> 00:18:08,000
Den första som vi såg var en int,

298
00:18:08,000 --> 00:18:10,000
vilket är ganska enkelt.

299
00:18:10,000 --> 00:18:13,000
Du använder int för att lagra ett heltal.

300
00:18:13,000 --> 00:18:16,000
Vi såg också karaktär, röding.

301
00:18:16,000 --> 00:18:20,000
Om du vill använda en bokstav eller en liten symbol som du förmodligen kommer att använda en röding.

302
00:18:20,000 --> 00:18:26,000
En kol har 1 byte, vilket innebär 8 bitar, som Lexi sa.

303
00:18:26,000 --> 00:18:31,000
I grund och botten har vi en ASCII tabell som har 256

304
00:18:31,000 --> 00:18:34,000
möjliga kombinationer av 0 och 1,

305
00:18:34,000 --> 00:18:37,000
och sedan när du skriver en röding det kommer att översätta

306
00:18:37,000 --> 00:18:44,000
det tecken som ingångarna ett nummer som du har i ASCII tabellen, som Lexi sa.

307
00:18:44,000 --> 00:18:48,000
Vi har också flottören, som vi använder för att lagra decimaltal.

308
00:18:48,000 --> 00:18:53,000
Om du vill välja 3,14, till exempel, kommer du att använda en flottör

309
00:18:53,000 --> 00:18:55,000
eller en dubbel som har större precision.

310
00:18:55,000 --> 00:18:57,000
En flottör har 4 byte.

311
00:18:57,000 --> 00:19:01,000
En dubbel har 8 byte, så den enda skillnaden är precisionen.

312
00:19:01,000 --> 00:19:04,000
Vi har också en lång som används för heltal,

313
00:19:04,000 --> 00:19:09,000
och du kan se en 32-bitars maskin en int och en lång har samma storlek,

314
00:19:09,000 --> 00:19:13,000
så det inte verkligen göra meningsfullt att använda en lång i en 32-bitars maskin.

315
00:19:13,000 --> 00:19:17,000
>> Men om du använder en Mac och 64-bitars maskin, faktiskt en länge har storlek 8,

316
00:19:17,000 --> 00:19:19,000
så det beror egentligen på arkitekturen.

317
00:19:19,000 --> 00:19:22,000
För 32-bitars maskin det inte är vettigt att använda en lång verkligen.

318
00:19:22,000 --> 00:19:25,000
Och därefter en lång lång, å andra sidan, har 8 byte,

319
00:19:25,000 --> 00:19:30,000
så det är mycket bra om du vill ha en längre heltal.

320
00:19:30,000 --> 00:19:34,000
Och slutligen har vi sträng, som egentligen är en char *,

321
00:19:34,000 --> 00:19:37,000
vilket är en pekare till en char.

322
00:19:37,000 --> 00:19:40,000
Det är väldigt lätt att tro att storleken på strängen kommer att vara som

323
00:19:40,000 --> 00:19:42,000
antalet tecken som du har där,

324
00:19:42,000 --> 00:19:45,000
men faktiskt char * själva

325
00:19:45,000 --> 00:19:49,000
har storleken på en pekare till en kol, vilket är 4 byte.

326
00:19:49,000 --> 00:19:52,000
Storleken på en char * är 4 byte.

327
00:19:52,000 --> 00:19:56,000
Det spelar ingen roll om du har ett litet ord eller en bokstav eller något.

328
00:19:56,000 --> 00:19:58,000
Det kommer att bli 4 byte.

329
00:19:58,000 --> 00:20:01,000
Vi lärde oss också lite om gjutning,

330
00:20:01,000 --> 00:20:04,000
så du kan se om du har till exempel ett program som säger

331
00:20:04,000 --> 00:20:08,000
int x = 3 och sedan printf ("% d", x / 2)

332
00:20:08,000 --> 00:20:12,000
Vet ni vad det kommer att skrivas ut på skärmen?

333
00:20:12,000 --> 00:20:14,000
>> Någon? >> [Studenter] 2.

334
00:20:14,000 --> 00:20:16,000
1. >> 1, ja.

335
00:20:16,000 --> 00:20:20,000
När du gör 3/2 att det kommer att bli 1,5,

336
00:20:20,000 --> 00:20:24,000
men eftersom vi använder ett heltal det kommer att ignorera decimal delen,

337
00:20:24,000 --> 00:20:26,000
och du kommer att ha 1.

338
00:20:26,000 --> 00:20:29,000
Om du inte vill att det ska hända vad du kan göra, till exempel,

339
00:20:29,000 --> 00:20:33,000
är förklara en flottör y = x.

340
00:20:33,000 --> 00:20:40,000
Då x som brukade vara 3 kommer nu att bli 3,000 i y..

341
00:20:40,000 --> 00:20:44,000
Och sedan kan du skriva y / 2.

342
00:20:44,000 --> 00:20:50,000
Egentligen borde jag ha en 2. borta.

343
00:20:50,000 --> 00:20:55,000
Det kommer att göra 3.00/2.00,

344
00:20:55,000 --> 00:20:58,000
och du kommer att få 1,5.

345
00:20:58,000 --> 00:21:06,000
Och vi har den här .2 f bara för att be om 2 decimaler enheter i decimaldelen.

346
00:21:06,000 --> 00:21:12,000
Om du har 0,3 f det kommer att faktiskt har 1,500.

347
00:21:12,000 --> 00:21:16,000
Om det är 2 kommer det att bli 1,50.

348
00:21:16,000 --> 00:21:18,000
Vi har också det här fallet här.

349
00:21:18,000 --> 00:21:22,000
Om du gör float x = 3,14 och sedan printf X

350
00:21:22,000 --> 00:21:24,000
du kommer att få 3,14.

351
00:21:24,000 --> 00:21:29,000
Och om du gör x = int av x,

352
00:21:29,000 --> 00:21:34,000
vilket innebär behandla x som en int och du skriver ut X nu

353
00:21:34,000 --> 00:21:36,000
du kommer att ha 3,00.

354
00:21:36,000 --> 00:21:38,000
Verkar det vettigt?

355
00:21:38,000 --> 00:21:41,000
Eftersom du först behandla x som ett heltal, så att du ignorerar decimaldelen,

356
00:21:41,000 --> 00:21:45,000
och då du skriver x.

357
00:21:45,000 --> 00:21:47,000
Och slutligen, kan du också göra detta,

358
00:21:47,000 --> 00:21:52,000
int x = 65, och sedan du deklarerar en char c = x,

359
00:21:52,000 --> 00:21:56,000
och sedan om du skriver ut c du faktiskt kommer att få

360
00:21:56,000 --> 00:21:59,000
A, så i princip vad du gör här

361
00:21:59,000 --> 00:22:02,000
är att översätta heltal i karaktären,

362
00:22:02,000 --> 00:22:05,000
precis som ASCII tabellen gör.

363
00:22:05,000 --> 00:22:08,000
Vi pratade också om matematiska operatörer.

364
00:22:08,000 --> 00:22:14,000
De flesta av dem är ganska enkel, så +, -, *, /,

365
00:22:14,000 --> 00:22:20,000
och även vi pratade om mod, som är resten av en division av 2 siffror.

366
00:22:20,000 --> 00:22:23,000
Om du har 10% 3, till exempel,

367
00:22:23,000 --> 00:22:27,000
det betyder dela 10 med 3, och vad är resten?

368
00:22:27,000 --> 00:22:30,000
Det kommer att vara 1, så det är faktiskt mycket användbar för många av programmen.

369
00:22:30,000 --> 00:22:38,000
För Vigenère och Caesar är jag ganska säker på att alla ni använt mod.

370
00:22:38,000 --> 00:22:43,000
Om Math operatörer, vara mycket försiktig när du kombinerar * och /.

371
00:22:43,000 --> 00:22:48,000
>> Till exempel, om du gör (3/2) * 2 vad ska du bli?

372
00:22:48,000 --> 00:22:50,000
[Studenter] 2.

373
00:22:50,000 --> 00:22:54,000
Ja, 2, beror 3/2 kommer att vara 1,5,

374
00:22:54,000 --> 00:22:57,000
men eftersom du gör verksamheten mellan 2 heltal

375
00:22:57,000 --> 00:22:59,000
du faktiskt bara att överväga 1,

376
00:22:59,000 --> 00:23:03,000
och sedan 1 * 2 kommer att bli 2, så mycket, mycket försiktig

377
00:23:03,000 --> 00:23:07,000
när man gör aritmetiska med heltal eftersom

378
00:23:07,000 --> 00:23:12,000
du kan få att 2 = 3, i så fall.

379
00:23:12,000 --> 00:23:14,000
Och också vara mycket försiktig företräde.

380
00:23:14,000 --> 00:23:21,000
Du bör vanligtvis använda parenteser för att vara säker på att du vet vad du gör.

381
00:23:21,000 --> 00:23:27,000
Några användbara genvägar, naturligtvis, är en i + + eller i + = 1

382
00:23:27,000 --> 00:23:30,000
eller med + =.

383
00:23:30,000 --> 00:23:34,000
Det är samma sak som att göra i = i + 1.

384
00:23:34,000 --> 00:23:39,000
Du kan också göra i - eller i - = 1,

385
00:23:39,000 --> 00:23:42,000
vilket är samma sak som i = i -1,

386
00:23:42,000 --> 00:23:46,000
något ni använder mycket i för slingor, åtminstone.

387
00:23:46,000 --> 00:23:52,000
Även för * om du använder * = och om du gör, till exempel,

388
00:23:52,000 --> 00:23:57,000
i * = 2 är samma sak som att säga i = I * 2,

389
00:23:57,000 --> 00:23:59,000
och samma sak för division.

390
00:23:59,000 --> 00:24:08,000
Om du gör jag / = 2 är det samma sak som i = i / 2.

391
00:24:08,000 --> 00:24:10,000
>> Nu om funktioner.

392
00:24:10,000 --> 00:24:13,000
Ni fick veta att funktioner är en mycket bra strategi för att spara kod

393
00:24:13,000 --> 00:24:16,000
medan du programmerar, så om du vill utföra samma uppgift

394
00:24:16,000 --> 00:24:20,000
i kod och om igen, förmodligen du vill använda en funktion

395
00:24:20,000 --> 00:24:25,000
bara så du behöver inte kopiera och klistra in koden om och om igen.

396
00:24:25,000 --> 00:24:28,000
Egentligen är främsta funktion, och när jag visar dig formatet för en funktion

397
00:24:28,000 --> 00:24:32,000
du kommer att se att det är ganska uppenbart.

398
00:24:32,000 --> 00:24:35,000
Vi använder också funktioner från vissa bibliotek,

399
00:24:35,000 --> 00:24:39,000
exempelvis printf, GetIn, vilket är från CS50 biblioteket,

400
00:24:39,000 --> 00:24:43,000
och andra funktioner som toupper.

401
00:24:43,000 --> 00:24:46,000
Alla dessa funktioner faktiskt implementeras i andra bibliotek,

402
00:24:46,000 --> 00:24:49,000
och när du sätter dem begränsningsremmar filer i början av ditt program

403
00:24:49,000 --> 00:24:53,000
du säger kan du ge mig koden för dessa funktioner

404
00:24:53,000 --> 00:24:57,000
så jag behöver inte genomföra dem själv?

405
00:24:57,000 --> 00:25:00,000
Och du kan också skriva egna funktioner, så när du börja programmera

406
00:25:00,000 --> 00:25:04,000
du inser att biblioteken inte har alla de funktioner som du behöver.

407
00:25:04,000 --> 00:25:10,000
För den sista pset, till exempel, skrev vi drar, scramble och lookup,

408
00:25:10,000 --> 00:25:13,000
och det är mycket, mycket viktigt att kunna skriva funktioner

409
00:25:13,000 --> 00:25:17,000
eftersom de är användbara, och vi använder dem hela tiden i programmering,

410
00:25:17,000 --> 00:25:19,000
och det sparar mycket kod.

411
00:25:19,000 --> 00:25:21,000
Formatet för en funktion är här.

412
00:25:21,000 --> 00:25:24,000
Vi har returtyp i början. Vad är returtyp?

413
00:25:24,000 --> 00:25:27,000
Det är bara när funktionen kommer att återvända.

414
00:25:27,000 --> 00:25:29,000
Om du har en funktion, till exempel, faktoriella,

415
00:25:29,000 --> 00:25:31,000
som kommer att beräkna en fakulteten av ett heltal,

416
00:25:31,000 --> 00:25:34,000
förmodligen kommer att återvända ett heltal också.

417
00:25:34,000 --> 00:25:37,000
Sedan returtyp kommer att vara int.

418
00:25:37,000 --> 00:25:41,000
Printf faktiskt har ett tomrum returtyp

419
00:25:41,000 --> 00:25:43,000
eftersom du inte returnera någonting.

420
00:25:43,000 --> 00:25:45,000
Du är bara skriva saker på skärmen

421
00:25:45,000 --> 00:25:48,000
och avsluta funktionen efteråt.

422
00:25:48,000 --> 00:25:51,000
Då har du namnet på den funktion som du kan välja.

423
00:25:51,000 --> 00:25:55,000
Du bör vara lite rimligt, liksom inte välja ett namn som xyz

424
00:25:55,000 --> 00:25:58,000
eller liknande x2f.

425
00:25:58,000 --> 00:26:02,000
Försök att göra upp ett namn som är vettigt.

426
00:26:02,000 --> 00:26:04,000
>> Till exempel, om det är faktoriell, säger fakulteten.

427
00:26:04,000 --> 00:26:08,000
Om det är en funktion som kommer att rita något, namnge den dra.

428
00:26:08,000 --> 00:26:11,000
Och sedan har vi de parametrar, som också kallas argument,

429
00:26:11,000 --> 00:26:14,000
som är som de resurser som din funktion behöver

430
00:26:14,000 --> 00:26:17,000
från din kod för att utföra sitt uppdrag.

431
00:26:17,000 --> 00:26:20,000
Om du vill beräkna fakulteten av ett antal

432
00:26:20,000 --> 00:26:23,000
förmodligen måste du ha ett nummer för att beräkna en faktoriell.

433
00:26:23,000 --> 00:26:27,000
Ett av de argument som du kommer att ha är numret själv.

434
00:26:27,000 --> 00:26:31,000
Och då det kommer att göra något och returnera värdet vid slutet

435
00:26:31,000 --> 00:26:35,000
om det inte är ett tomrum funktion.

436
00:26:35,000 --> 00:26:37,000
Låt oss se ett exempel.

437
00:26:37,000 --> 00:26:40,000
Om jag vill skriva en funktion som summerar alla nummer i en array av heltal,

438
00:26:40,000 --> 00:26:43,000
först och främst är returtyp kommer att vara int

439
00:26:43,000 --> 00:26:46,000
eftersom jag har en mängd av heltal.

440
00:26:46,000 --> 00:26:51,000
Och då ska jag ha funktionen namn som sumArray,

441
00:26:51,000 --> 00:26:54,000
och då det kommer att ta arrayen själv, int nums,

442
00:26:54,000 --> 00:26:58,000
och sedan längden på arrayen så jag vet hur många nummer jag summera.

443
00:26:58,000 --> 00:27:02,000
Då måste jag initiera en variabel som heter summa, till exempel till 0,

444
00:27:02,000 --> 00:27:08,000
och varje gång jag ser ett element i arrayen jag lägga till summan, så jag gjorde en for-slinga.

445
00:27:08,000 --> 00:27:15,000
Precis som Lexi sa, du int i = 0, i <längd och i + +.

446
00:27:15,000 --> 00:27:20,000
Och för varje element i arrayen jag summa + = nums [i],

447
00:27:20,000 --> 00:27:24,000
och sedan jag återvände summan, så det är väldigt enkelt, och det sparar mycket kod

448
00:27:24,000 --> 00:27:28,000
om du använder denna funktion många gånger.

449
00:27:28,000 --> 00:27:32,000
Sedan tog vi en titt på förhållanden.

450
00:27:32,000 --> 00:27:38,000
Vi har om annat, och annan om.

451
00:27:38,000 --> 00:27:42,000
Låt oss se vad är skillnaden mellan dem.

452
00:27:42,000 --> 00:27:45,000
Ta en titt på dessa 2 koder. Vad är skillnaden mellan dem?

453
00:27:45,000 --> 00:27:49,000
Den första har i stort sett endast koderna vill att du ska berätta

454
00:27:49,000 --> 00:27:51,000
Om ett nummer är +, - eller 0.

455
00:27:51,000 --> 00:27:55,000
Den första säger att om det är> 0 så är det positivt.

456
00:27:55,000 --> 00:28:00,000
Om det är = till 0 så är det 0, och om det är <0 så är det negativt.

457
00:28:00,000 --> 00:28:04,000
>> Och den andra är att göra om, annars om, annars.

458
00:28:04,000 --> 00:28:07,000
Skillnaden mellan de två är att detta faktiskt kommer att

459
00:28:07,000 --> 00:28:13,000
kontrollera om> 0, <0 eller = 0 tre gånger,

460
00:28:13,000 --> 00:28:17,000
så om du har numret 2, till exempel, kommer det att komma hit och säga

461
00:28:17,000 --> 00:28:21,000
if (x> 0), och det kommer att säga ja, så jag skriver ut positivt.

462
00:28:21,000 --> 00:28:25,000
Men även om jag vet att det är> 0 och det kommer inte att bli 0 eller <0

463
00:28:25,000 --> 00:28:29,000
Jag fortfarande tänker göra det 0, det är <0,

464
00:28:29,000 --> 00:28:33,000
så jag faktiskt kommer in för IFS att jag inte behövde

465
00:28:33,000 --> 00:28:38,000
eftersom jag redan vet att det inte kommer att tillfredsställa något av dessa villkor.

466
00:28:38,000 --> 00:28:41,000
Jag kan använda om else if, else.

467
00:28:41,000 --> 00:28:45,000
Det säger i princip om x = 0 jag skriver ut det positiva.

468
00:28:45,000 --> 00:28:48,000
Om det inte, jag ska också testa detta.

469
00:28:48,000 --> 00:28:51,000
Om det är 2 inte jag kommer att göra detta.

470
00:28:51,000 --> 00:28:54,000
I grund och botten om jag hade x = 2 du skulle säga

471
00:28:54,000 --> 00:28:57,000
if (x> 0), ja, så skriv ut.

472
00:28:57,000 --> 00:29:00,000
Nu när jag vet att det är> 0 och att den uppfyllt det första om

473
00:29:00,000 --> 00:29:02,000
Jag är inte ens kommer att köra denna kod.

474
00:29:02,000 --> 00:29:09,000
Koden körs snabbare, faktiskt, 3 gånger snabbare om du använder det.

475
00:29:09,000 --> 00:29:11,000
Vi lärde också om och och eller.

476
00:29:11,000 --> 00:29:15,000
Jag tänker inte gå igenom detta eftersom Lexi redan pratat om dem.

477
00:29:15,000 --> 00:29:17,000
Det är bara de && och | | operatör.

478
00:29:17,000 --> 00:29:21,000
>> Det enda jag säger är att vara försiktig när du har 3 villkor.

479
00:29:21,000 --> 00:29:24,000
Använd parenteser eftersom det är mycket förvirrande när du har ett tillstånd

480
00:29:24,000 --> 00:29:27,000
och en annan eller en annan.

481
00:29:27,000 --> 00:29:30,000
Använd parenteser bara för att vara säker på att dina villkor vettigt

482
00:29:30,000 --> 00:29:34,000
eftersom i det fallet till exempel, kan du tänka dig att

483
00:29:34,000 --> 00:29:38,000
det kan vara det första villkoret och den ena eller den andra

484
00:29:38,000 --> 00:29:41,000
eller 2 villkor kombineras i en och

485
00:29:41,000 --> 00:29:45,000
eller den tredje, så bara vara försiktig.

486
00:29:45,000 --> 00:29:48,000
Och slutligen, talade vi om växlar.

487
00:29:48,000 --> 00:29:53,000
En switch är mycket användbart när du har en variabel.

488
00:29:53,000 --> 00:29:55,000
Låt oss säga att du har en variabel som n

489
00:29:55,000 --> 00:29:59,000
som kan vara 0, 1, eller 2, och för varje av dessa fall

490
00:29:59,000 --> 00:30:01,000
du kommer att utföra en uppgift.

491
00:30:01,000 --> 00:30:04,000
Du kan säga byta variabeln, och det tyder på att

492
00:30:04,000 --> 00:30:08,000
Värdet är då som värde1 jag ska göra detta,

493
00:30:08,000 --> 00:30:12,000
och då jag sönder, vilket innebär att jag inte kommer att titta på någon av de andra fallen

494
00:30:12,000 --> 00:30:15,000
eftersom vi nöjda redan det fallet

495
00:30:15,000 --> 00:30:20,000
och sedan värde2 och så vidare, och jag kan också ha en standard brytare.

496
00:30:20,000 --> 00:30:24,000
Det innebär att om det inte uppfyller något av de fall som jag hade

497
00:30:24,000 --> 00:30:29,000
att jag ska göra något annat, men det är valfritt.

498
00:30:29,000 --> 00:30:36,000
Det var allt för mig. Nu ska vi ha Tommy.

499
00:30:36,000 --> 00:30:41,000
Okej, detta kommer att bli vecka 3-ish.

500
00:30:41,000 --> 00:30:45,000
Dessa är några av de ämnen som vi kommer att täcker, crypto, omfattning, matriser, et cetera.

501
00:30:45,000 --> 00:30:49,000
Bara en snabb ord om krypto. Vi kommer inte att hamra detta hem.

502
00:30:49,000 --> 00:30:52,000
>> Vi gjorde detta i pset 2, men för testet att du vet skillnaden

503
00:30:52,000 --> 00:30:54,000
mellan Caesar chiffer och Vigenère chiffer,

504
00:30:54,000 --> 00:30:57,000
hur båda dessa chiffer arbete och hur det är att kryptera

505
00:30:57,000 --> 00:30:59,000
och dekryptera text med dessa 2 chiffer.

506
00:30:59,000 --> 00:31:03,000
Kom ihåg roterar Caesar chiffer helt enkelt varje tecken med samma belopp,

507
00:31:03,000 --> 00:31:06,000
vilket gör att du mod med antalet bokstäver i alfabetet.

508
00:31:06,000 --> 00:31:09,000
Och Vigenère chiffret, å andra sidan, roterar varje tecken

509
00:31:09,000 --> 00:31:12,000
med ett annat belopp, så istället för att säga

510
00:31:12,000 --> 00:31:15,000
Varje tecken roteras 3 Vigenère kommer att rotera varje tecken

511
00:31:15,000 --> 00:31:17,000
med ett annat belopp beror på några sökord

512
00:31:17,000 --> 00:31:20,000
där varje bokstav i sökordet representerar några olika belopp

513
00:31:20,000 --> 00:31:26,000
att rotera klartext genom.

514
00:31:26,000 --> 00:31:28,000
Låt oss först tala om varierande omfattning.

515
00:31:28,000 --> 00:31:30,000
Det finns 2 olika typer av variabler.

516
00:31:30,000 --> 00:31:33,000
Vi har lokala variabler, och dessa kommer att definieras

517
00:31:33,000 --> 00:31:36,000
utanför huvud-eller utanför någon funktion eller block,

518
00:31:36,000 --> 00:31:39,000
och dessa kommer att vara tillgänglig var som helst i ditt program.

519
00:31:39,000 --> 00:31:41,000
Om du har en funktion och den funktionen är en while-slinga

520
00:31:41,000 --> 00:31:44,000
den stora globala variabeln är tillgänglig överallt.

521
00:31:44,000 --> 00:31:48,000
En lokal variabel, å andra sidan, är scoped till den plats där den är definierad.

522
00:31:48,000 --> 00:31:53,000
>> Om du har en funktion här, till exempel, har vi denna funktion g

523
00:31:53,000 --> 00:31:56,000
och insidan av g finns en variabel här kallad y,

524
00:31:56,000 --> 00:31:58,000
och det betyder att det är en lokal variabel.

525
00:31:58,000 --> 00:32:00,000
Även om denna variabel kallas y

526
00:32:00,000 --> 00:32:03,000
och denna variabel kallas y dessa 2 funktioner

527
00:32:03,000 --> 00:32:06,000
har ingen aning om vad varandras lokala variabler.

528
00:32:06,000 --> 00:32:10,000
Å andra sidan, här uppe säger vi int x = 5,

529
00:32:10,000 --> 00:32:12,000
och detta är utanför någon funktion.

530
00:32:12,000 --> 00:32:16,000
Det är utanför viktigaste, så detta är en global variabel.

531
00:32:16,000 --> 00:32:20,000
Det innebär att insidan av dessa 2 funktioner när jag säger x - eller x + +

532
00:32:20,000 --> 00:32:26,000
Jag åtkomst samma x varvid denna y och denna y är olika variabler.

533
00:32:26,000 --> 00:32:30,000
Det är skillnaden mellan en global variabel och en lokal variabel.

534
00:32:30,000 --> 00:32:33,000
När det gäller utformningen är berörda, ibland är det nog en bättre idé

535
00:32:33,000 --> 00:32:37,000
att hålla variabler lokal när du möjligen kan

536
00:32:37,000 --> 00:32:39,000
sedan med ett gäng globala variabler kan bli riktigt förvirrande.

537
00:32:39,000 --> 00:32:42,000
Om du har ett gäng funktioner alla modifiera samma sak

538
00:32:42,000 --> 00:32:45,000
du kan glömma vad om funktionen av misstag ändrar denna globala,

539
00:32:45,000 --> 00:32:47,000
och denna andra funktion inte vet om det,

540
00:32:47,000 --> 00:32:50,000
och det blir ganska förvirrande när du får mer kod.

541
00:32:50,000 --> 00:32:53,000
Hålla variabler lokal när du möjligen kan

542
00:32:53,000 --> 00:32:56,000
är bara bra design.

543
00:32:56,000 --> 00:33:00,000
Arrays, kom ihåg, är helt enkelt listor av element av samma typ.

544
00:33:00,000 --> 00:33:04,000
Inne i CI kan inte ha en lista som 1, 2,0, hej.

545
00:33:04,000 --> 00:33:06,000
Vi kan bara inte göra det.

546
00:33:06,000 --> 00:33:11,000
>> När vi förklarar en array i C alla element måste vara av samma typ.

547
00:33:11,000 --> 00:33:14,000
Här har jag en rad 3 heltal.

548
00:33:14,000 --> 00:33:18,000
Här har jag längden på arrayen, men om jag bara förklara det i denna syntax

549
00:33:18,000 --> 00:33:21,000
där jag ange vilka alla element är jag inte tekniskt behöver detta 3.

550
00:33:21,000 --> 00:33:25,000
Kompilatorn är smart nog att räkna ut hur stor matrisen ska vara.

551
00:33:25,000 --> 00:33:28,000
Nu när jag vill hämta eller ange värdet för en matris

552
00:33:28,000 --> 00:33:30,000
Detta är syntaxen att göra det.

553
00:33:30,000 --> 00:33:33,000
Detta kommer faktiskt att ändra det andra element i arrayen eftersom, kom ihåg,

554
00:33:33,000 --> 00:33:36,000
numreringen börjar vid 0, inte 1.

555
00:33:36,000 --> 00:33:42,000
Om jag vill läsa det värdet kan jag säga något i stil med int x = array [1].

556
00:33:42,000 --> 00:33:44,000
Eller om jag vill ställa in det värde, som jag gör här,

557
00:33:44,000 --> 00:33:47,000
Jag kan säga array [1] = 4.

558
00:33:47,000 --> 00:33:50,000
Den tiden tillgång element av deras index

559
00:33:50,000 --> 00:33:52,000
eller sin ställning eller om de är i arrayen,

560
00:33:52,000 --> 00:33:57,000
och att noteringen inleds på 0.

561
00:33:57,000 --> 00:34:00,000
Vi kan också ha arrayer av arrayer,

562
00:34:00,000 --> 00:34:03,000
och detta kallas en flerdimensionell matris.

563
00:34:03,000 --> 00:34:05,000
När vi har en flerdimensionell array

564
00:34:05,000 --> 00:34:07,000
det innebär att vi kan ha något som rader och kolumner,

565
00:34:07,000 --> 00:34:11,000
och detta är bara ett sätt att visualisera detta eller tänker på det.

566
00:34:11,000 --> 00:34:14,000
När jag har en flerdimensionell array som innebär att jag tänker börja behöver

567
00:34:14,000 --> 00:34:17,000
mer än 1 index eftersom om jag har ett rutnät

568
00:34:17,000 --> 00:34:19,000
bara säga vad rad du är i ger oss inte ett nummer.

569
00:34:19,000 --> 00:34:22,000
Det är verkligen bara kommer att ge oss en lista med tal.

570
00:34:22,000 --> 00:34:25,000
Låt oss säga att jag har denna matris här.

571
00:34:25,000 --> 00:34:30,000
Jag har en array med namnet nätet, och jag säger det är 2 rader och 3 kolumner,

572
00:34:30,000 --> 00:34:32,000
och så detta är ett sätt att visualisera det.

573
00:34:32,000 --> 00:34:37,000
När jag säger att jag vill få elementet vid [1] [2]

574
00:34:37,000 --> 00:34:41,000
det betyder att eftersom dessa är rader först och sedan kolumner

575
00:34:41,000 --> 00:34:44,000
Jag ska hoppa till rad 1 eftersom jag sa 1.

576
00:34:44,000 --> 00:34:49,000
>> Sen ska jag komma hit till kolumn 2, och jag kommer att få värdet 6.

577
00:34:49,000 --> 00:34:51,000
Vettigt?

578
00:34:51,000 --> 00:34:55,000
Flerdimensionella arrayer, kom ihåg, är tekniskt bara en rad matriser.

579
00:34:55,000 --> 00:34:57,000
Vi kan ha arrayer av arrayer av arrayer.

580
00:34:57,000 --> 00:35:00,000
Vi kan fortsätta, men egentligen ett sätt att tänka

581
00:35:00,000 --> 00:35:03,000
hur detta läggs ut och vad som händer är att visualisera det

582
00:35:03,000 --> 00:35:09,000
i ett rutnät som denna.

583
00:35:09,000 --> 00:35:12,000
När vi passerar arrayer till funktioner, kommer de att bete sig

584
00:35:12,000 --> 00:35:16,000
lite annorlunda än när vi passerar regelbundet variabler till funktioner

585
00:35:16,000 --> 00:35:18,000
som passerar en int eller en flottör.

586
00:35:18,000 --> 00:35:21,000
När vi passerar i en int eller char eller något av dessa andra datatyper

587
00:35:21,000 --> 00:35:24,000
Vi tog bara en titt på om funktionen ändrar

588
00:35:24,000 --> 00:35:28,000
värdet på den variabeln att förändring inte kommer att propagera upp

589
00:35:28,000 --> 00:35:32,000
till den anropande funktionen.

590
00:35:32,000 --> 00:35:35,000
Med en matris, på den andra sidan kommer att hända.

591
00:35:35,000 --> 00:35:39,000
Om jag passerar i en matris till någon funktion och att funktionen ändrar några av elementen,

592
00:35:39,000 --> 00:35:43,000
när jag kommer tillbaka till den funktion som kallade det

593
00:35:43,000 --> 00:35:47,000
min grupp kommer nu att vara annorlunda, och ordförråd för att

594
00:35:47,000 --> 00:35:50,000
är arrayer passeras genom hänvisning som vi kommer att se senare.

595
00:35:50,000 --> 00:35:53,000
Detta är relaterat till hur pekare arbete, där dessa grundläggande datatyper,

596
00:35:53,000 --> 00:35:55,000
å andra sidan, är förbi värde.

597
00:35:55,000 --> 00:35:59,000
>> Vi kan tänka oss det som att göra en kopia av något variabel och sedan passerar i kopian.

598
00:35:59,000 --> 00:36:01,000
Det spelar ingen roll vad vi gör med den variabeln.

599
00:36:01,000 --> 00:36:06,000
Anropsfunktionen kommer inte att vara medvetna om att det har ändrats.

600
00:36:06,000 --> 00:36:10,000
Arrayer är bara lite annorlunda i detta avseende.

601
00:36:10,000 --> 00:36:13,000
Till exempel, som vi just sett, är huvudsakliga helt enkelt en funktion

602
00:36:13,000 --> 00:36:15,000
som kan ta i 2 argument.

603
00:36:15,000 --> 00:36:20,000
Det första argumentet till huvudsakliga funktion är argc eller antal argument,

604
00:36:20,000 --> 00:36:23,000
och det andra argumentet kallas argv,

605
00:36:23,000 --> 00:36:27,000
och de är de verkliga värdena för dessa argument.

606
00:36:27,000 --> 00:36:30,000
Låt oss säga att jag har ett program som heter this.c,

607
00:36:30,000 --> 00:36:34,000
och jag säger att detta, och jag kommer att köra detta på kommandoraden.

608
00:36:34,000 --> 00:36:38,000
Nu passerar i vissa argument för mitt program kallade detta,

609
00:36:38,000 --> 00:36:42,000
Jag skulle kunna säga något i stil med. / Det är CS 50.

610
00:36:42,000 --> 00:36:45,000
Detta är vad vi föreställer David för att göra varje dag vid terminalen.

611
00:36:45,000 --> 00:36:48,000
Men nu huvudfunktion insidan av programmet

612
00:36:48,000 --> 00:36:52,000
har dessa värden, så argc är 4.

613
00:36:52,000 --> 00:36:56,000
Det kan vara lite förvirrande eftersom egentligen vi bara passerar i är CS 50.

614
00:36:56,000 --> 00:36:58,000
Det är bara 3.

615
00:36:58,000 --> 00:37:02,000
Men kom ihåg att den första delen av argv eller det första argumentet

616
00:37:02,000 --> 00:37:05,000
är namnet på själva funktionen.

617
00:37:05,000 --> 00:37:07,190
Så det innebär att vi har 4 saker här,

618
00:37:07,190 --> 00:37:10,530
och det första elementet kommer att bli. / det.

619
00:37:10,530 --> 00:37:12,970
Och detta kommer att representeras som en sträng.

620
00:37:12,970 --> 00:37:18,590
Sedan de återstående elementen är vad vi skrev i efter namnet på programmet.

621
00:37:18,590 --> 00:37:22,720
Så precis som en sidoreplik, som vi förmodligen såg i pset 2,

622
00:37:22,720 --> 00:37:28,780
kom ihåg att strängen 50 är ≠ heltalet 50.

623
00:37:28,780 --> 00:37:32,520
Så vi kan inte säga något i stil med 'int x = argv 3. "

624
00:37:32,520 --> 00:37:36,470
>> Det bara inte kommer att vara meningsfullt, eftersom detta är en sträng, och detta är ett heltal.

625
00:37:36,470 --> 00:37:38,510
Så om du vill konvertera mellan 2, kom ihåg, vi ska

626
00:37:38,510 --> 00:37:40,810
har denna magiska funktion som kallas Atoi.

627
00:37:40,810 --> 00:37:46,270
Det tar en sträng och returnerar heltalet representerade inuti den strängen.

628
00:37:46,270 --> 00:37:48,360
Så det är ett enkelt misstag att göra på frågesport,

629
00:37:48,360 --> 00:37:51,590
bara tänka att detta automatiskt blir rätt typ.

630
00:37:51,590 --> 00:37:53,860
Men bara vet att de alltid kommer att vara strängar

631
00:37:53,860 --> 00:38:00,920
även om strängen innehåller endast ett heltal eller ett tecken eller en flottör.

632
00:38:00,920 --> 00:38:03,380
Så nu ska vi prata om körtid.

633
00:38:03,380 --> 00:38:06,700
När vi har alla dessa algoritmer som gör alla dessa galna saker,

634
00:38:06,700 --> 00:38:11,580
blir det verkligen bra att ställa frågan: "Hur länge de tar?"

635
00:38:11,580 --> 00:38:15,500
Vi representerar det med något som kallas asymptotisk notation.

636
00:38:15,500 --> 00:38:18,430
Så detta innebär att - ja, låt oss säga att vi ger vår algoritm

637
00:38:18,430 --> 00:38:20,840
några riktigt, riktigt, riktigt stora ingång.

638
00:38:20,840 --> 00:38:23,840
Vi vill ställa frågan, "Hur länge kommer det att ta?

639
00:38:23,840 --> 00:38:26,370
Hur många steg tar det vår algoritm för att köra

640
00:38:26,370 --> 00:38:29,980
som en funktion av storleken av insignalen? "

641
00:38:29,980 --> 00:38:33,080
Så den första sättet vi kan beskriva drifttid är med stor O.

642
00:38:33,080 --> 00:38:35,380
Och detta är vår värsta gångtid.

643
00:38:35,380 --> 00:38:38,590
Så om vi vill sortera en array, och vi ger vår algoritm en matris

644
00:38:38,590 --> 00:38:41,000
Det är i fallande ordning när det borde vara i stigande ordning,

645
00:38:41,000 --> 00:38:43,130
det kommer att bli det värsta fallet.

646
00:38:43,130 --> 00:38:49,800
Detta är vår övre gräns i den maximala tid vår algoritm kommer att ta.

647
00:38:49,800 --> 00:38:54,740
Å andra sidan är denna Ω kommer att beskriva bästa fall gångtid.

648
00:38:54,740 --> 00:38:58,210
Så om vi ger en redan sorterade arrayen till en sortering algoritm,

649
00:38:58,210 --> 00:39:00,940
Hur lång tid tar det att sortera det?

650
00:39:00,940 --> 00:39:06,610
Och detta då beskriver en nedre gräns på gångtid.

651
00:39:06,610 --> 00:39:10,980
Så här är bara några ord som beskriver några vanliga gångtider.

652
00:39:10,980 --> 00:39:13,120
Dessa är i stigande ordning.

653
00:39:13,120 --> 00:39:16,060
Den snabbaste gångtid har vi kallas konstant.

654
00:39:16,060 --> 00:39:19,800
>> Det innebär oavsett hur många element som vi ger vår algoritm,

655
00:39:19,800 --> 00:39:22,280
oavsett hur stor vår array är, sortering

656
00:39:22,280 --> 00:39:26,510
eller göra vad vi gör på arrayen kommer alltid ta lika lång tid.

657
00:39:26,510 --> 00:39:30,270
Så vi kan representera att bara med en 1, vilket är en konstant.

658
00:39:30,270 --> 00:39:32,410
Vi har också tittat på logaritmisk körning.

659
00:39:32,410 --> 00:39:34,800
Så något liknande binär sökning är logaritmisk,

660
00:39:34,800 --> 00:39:37,140
där vi skär problemet i halv varje gång

661
00:39:37,140 --> 00:39:40,970
och sedan saker får bara högre därifrån.

662
00:39:40,970 --> 00:39:43,580
Och om du någonsin skriver en O någon fakulteten algoritm,

663
00:39:43,580 --> 00:39:47,850
du antagligen inte bör överväga detta som ditt vanliga jobb.

664
00:39:47,850 --> 00:39:53,910
När vi jämför gångtider är det viktigt att komma ihåg dessa saker.

665
00:39:53,910 --> 00:39:57,760
Så om jag har en algoritm som är O (n), och någon annan

666
00:39:57,760 --> 00:40:03,590
har en algoritm av O (2n) dessa är faktiskt asymptotiskt ekvivalenta.

667
00:40:03,590 --> 00:40:06,590
Så om vi föreställer n att vara ett stort antal som eleventy miljarder:

668
00:40:06,590 --> 00:40:13,090
så när vi jämför eleventy miljarder till något liknande eleventy miljarder + 3,

669
00:40:13,090 --> 00:40:17,640
plötsligt att tre inte gör verkligen en stor skillnad längre.

670
00:40:17,640 --> 00:40:20,980
Det är därför vi ska börja överväga dessa saker vara likvärdiga.

671
00:40:20,980 --> 00:40:24,220
Så saker som dessa konstanter här, det finns 2 x detta, eller lägga till en 3,

672
00:40:24,220 --> 00:40:27,180
dessa är bara konstanter, och dessa kommer att falla upp.

673
00:40:27,180 --> 00:40:32,480
Så det är därför alla 3 av dessa kör tider är detsamma som att säga att de är O (n).

674
00:40:32,480 --> 00:40:37,490
Likaså om vi har 2 andra körtider, låt oss säga O (n ³ + 2n ²), kan vi lägga

675
00:40:37,490 --> 00:40:42,070
+ N, + 7, och sedan har vi en annan körning det är bara O (n ³).

676
00:40:42,070 --> 00:40:46,290
Återigen, detta är samma sak eftersom dessa - det är inte samma sak.

677
00:40:46,290 --> 00:40:49,840
Det är samma saker, tyvärr. Så dessa är samma eftersom

678
00:40:49,840 --> 00:40:53,090
Detta N ^ kommer att dominera denna 2n ².

679
00:40:53,090 --> 00:40:59,130
>> Vad är inte samma sak är om vi har kört tider som O (n ³) och O (n ²)

680
00:40:59,130 --> 00:41:02,820
eftersom detta N ^ är mycket större än den här N ^.

681
00:41:02,820 --> 00:41:05,470
Så om vi har exponenter, plötsligt detta börjar roll,

682
00:41:05,470 --> 00:41:08,280
men när vi bara göra med faktorer som vi är här uppe,

683
00:41:08,280 --> 00:41:12,810
då det inte kommer spela någon roll eftersom de bara kommer att falla ut.

684
00:41:12,810 --> 00:41:16,760
Låt oss ta en titt på några av de algoritmer vi har sett hittills

685
00:41:16,760 --> 00:41:19,260
och tala om sin körning.

686
00:41:19,260 --> 00:41:23,850
Det första sättet att leta efter ett nummer i en lista, som vi såg, var linjär sökning.

687
00:41:23,850 --> 00:41:26,950
Och genomförandet av linjär sökning är super enkelt.

688
00:41:26,950 --> 00:41:30,490
Vi har bara en lista, och vi kommer att titta på varje enskilt element i listan

689
00:41:30,490 --> 00:41:34,260
tills vi hittar numret vi letar efter.

690
00:41:34,260 --> 00:41:38,370
Så det betyder att i värsta fall, denna O (n).

691
00:41:38,370 --> 00:41:40,860
Och det värsta fallet här skulle vara om elementet är

692
00:41:40,860 --> 00:41:45,710
det sista elementet, sedan använda linjär sökning vi måste titta på varje enskilt element

693
00:41:45,710 --> 00:41:50,180
tills vi kommer till den sista för att veta att det var faktiskt i listan.

694
00:41:50,180 --> 00:41:52,910
Vi kan inte bara ge upp halvvägs och säger: "Det är nog inte där."

695
00:41:52,910 --> 00:41:55,980
Med linjär sökning måste vi titta på det hela.

696
00:41:55,980 --> 00:41:59,090
Bästa fall gångtid, å andra sidan, är konstant

697
00:41:59,090 --> 00:42:04,200
eftersom det i bästa fall elementet vi letar efter är bara den första i listan.

698
00:42:04,200 --> 00:42:08,930
Så det kommer att ta oss exakt 1 steg, oavsett hur stor listan är

699
00:42:08,930 --> 00:42:12,140
Om vi ​​letar efter det första elementet varje gång.

700
00:42:12,140 --> 00:42:15,390
>> Så när du söker, kom ihåg, behöver den inte att vår lista ska sorteras.

701
00:42:15,390 --> 00:42:19,430
Eftersom vi bara kommer att se över varenda del, och det spelar egentligen ingen roll

702
00:42:19,430 --> 00:42:23,560
vilken ordning dessa delar är i.

703
00:42:23,560 --> 00:42:28,110
En mer intelligent sökalgoritm är något som binär sökning.

704
00:42:28,110 --> 00:42:31,500
Kom ihåg att genomförandet av binär sökning när du ska

705
00:42:31,500 --> 00:42:34,320
hålla ser i mitten av listan.

706
00:42:34,320 --> 00:42:38,000
Och eftersom vi tittar på mitten, kräver vi att listan är sorterad

707
00:42:38,000 --> 00:42:40,580
annars vet vi inte var mitten är, och vi måste se över

708
00:42:40,580 --> 00:42:44,480
hela listan för att hitta den och sedan på den punkten vi bara slösar bort tid.

709
00:42:44,480 --> 00:42:48,480
Så om vi har en sorterad lista och vi hitta mitten, kommer vi att jämföra i mitten

710
00:42:48,480 --> 00:42:51,590
till elementet som vi letar efter.

711
00:42:51,590 --> 00:42:54,640
Om det är för högt, då kan vi glömma den högra halvan

712
00:42:54,640 --> 00:42:57,810
eftersom vi vet att om vi element är redan för hög

713
00:42:57,810 --> 00:43:01,080
och allt till höger om detta element är ännu högre,

714
00:43:01,080 --> 00:43:02,760
vi behöver inte leta där längre.

715
00:43:02,760 --> 00:43:05,430
När å andra sidan, om vi element är för låg,

716
00:43:05,430 --> 00:43:08,700
Vi vet allt till vänster om denna beståndsdel är också för låg,

717
00:43:08,700 --> 00:43:11,390
så det inte verkligen göra meningsfullt att titta där heller.

718
00:43:11,390 --> 00:43:15,760
På detta sätt, med varje steg och varje gång vi tittar på mittpunkten av listan,

719
00:43:15,760 --> 00:43:19,060
vi kommer att minska vår problem i halv eftersom vi plötsligt känner

720
00:43:19,060 --> 00:43:23,040
en hel massa siffror som inte kan den vi letar efter.

721
00:43:23,040 --> 00:43:26,950
>> I pseudokod skulle se ut ungefär så här,

722
00:43:26,950 --> 00:43:30,990
och eftersom vi skär listan i halv varenda gång,

723
00:43:30,990 --> 00:43:34,920
våra värsta fall körtid hoppar från linjär till logaritmisk.

724
00:43:34,920 --> 00:43:39,260
Så plötsligt har vi logga in steg för att finna ett element i en lista.

725
00:43:39,260 --> 00:43:42,460
Det bästa fall gångtid är dock fortfarande konstant

726
00:43:42,460 --> 00:43:45,180
för nu, låt oss bara säga att elementet vi letar efter är

727
00:43:45,180 --> 00:43:48,380
alltid exakt mitten av ursprungliga listan.

728
00:43:48,380 --> 00:43:52,080
Så vi kan växa vår lista så stor som vi vill, men om elementet vi letar efter är i mitten,

729
00:43:52,080 --> 00:43:54,910
då är det bara att ta oss 1 steg.

730
00:43:54,910 --> 00:44:00,920
Så det är därför vi är O (log n) och Ω (1) eller konstant.

731
00:44:00,920 --> 00:44:04,510
Låt oss verkligen köra binär sökning på denna lista.

732
00:44:04,510 --> 00:44:08,020
Så låt oss säga att vi letar efter elementet 164.

733
00:44:08,020 --> 00:44:11,650
Det första vi ska göra är att hitta mittpunkten av denna lista.

734
00:44:11,650 --> 00:44:15,060
Det råkar vara så att mittpunkten kommer att falla mellan dessa 2 siffror,

735
00:44:15,060 --> 00:44:18,960
så låt oss bara godtyckligt säga varje gång mittpunkten ligger mellan 2 tal,

736
00:44:18,960 --> 00:44:21,150
Låt oss bara runda upp.

737
00:44:21,150 --> 00:44:24,330
Vi behöver bara se till att vi gör detta varje steg på vägen.

738
00:44:24,330 --> 00:44:29,040
Så vi kommer att runda upp, och vi kommer att säga att 161 är i mitten av vår lista.

739
00:44:29,040 --> 00:44:34,640
Så 161 <164, och varje element till vänster om 161

740
00:44:34,640 --> 00:44:39,120
är också <164, så vi vet att det inte kommer att hjälpa oss på alla

741
00:44:39,120 --> 00:44:42,690
att börja leta på här eftersom elementet vi letar efter kan inte vara där.

742
00:44:42,690 --> 00:44:47,060
Så vad vi kan göra är att vi bara kan glömma att hela vänstra halvan av listan,

743
00:44:47,060 --> 00:44:51,700
och nu bara tänka på rätt 161 och framåt.

744
00:44:51,700 --> 00:44:54,050
>> Så återigen, detta är mittpunkten, låt oss bara runda upp.

745
00:44:54,050 --> 00:44:56,260
Nu 175 är för stort.

746
00:44:56,260 --> 00:44:59,180
Så vi vet att det inte kommer att hjälpa oss ser här eller här,

747
00:44:59,180 --> 00:45:06,610
så att vi kan bara kasta bort det, och så småningom kommer vi träffa 164.

748
00:45:06,610 --> 00:45:10,560
Eventuella frågor om binärsökning?

749
00:45:10,560 --> 00:45:14,180
Låt oss gå vidare från att söka igenom en redan sorterad lista

750
00:45:14,180 --> 00:45:17,660
att faktiskt ta en lista med tal i valfri ordning

751
00:45:17,660 --> 00:45:20,960
och göra denna förteckning i stigande ordning.

752
00:45:20,960 --> 00:45:24,060
Den första algoritmen som vi tittat på hette bubbla sortera.

753
00:45:24,060 --> 00:45:27,300
Och detta skulle vara enklare om de algoritmer vi såg.

754
00:45:27,300 --> 00:45:32,970
Bubble Sortera säger att när någon 2 element inuti listan är på sin plats,

755
00:45:32,970 --> 00:45:36,500
vilket innebär att det finns ett högre antal till vänster om ett lägre antal,

756
00:45:36,500 --> 00:45:40,190
då ska vi byta dem, eftersom det innebär att listan blir

757
00:45:40,190 --> 00:45:42,860
"Mer sorteras" än det var innan.

758
00:45:42,860 --> 00:45:45,180
Och vi ska bara fortsätta denna process igen och igen och igen

759
00:45:45,180 --> 00:45:52,100
tills slutligen elementen typ av bubbla till rätt plats och vi har en sorterad lista.

760
00:45:52,100 --> 00:45:57,230
>> Körtiden för denna kommer att vara O (n ²). Varför?

761
00:45:57,230 --> 00:46:00,370
Jo, för i värsta fall kommer vi att ta varje element, och

762
00:46:00,370 --> 00:46:04,570
vi kommer att hamna jämföra det med alla andra element i listan.

763
00:46:04,570 --> 00:46:08,030
Men i bästa fall har vi en redan sorterad lista, bubbla sortera är

764
00:46:08,030 --> 00:46:12,230
bara att gå igenom en gång, säger "Nej. Jag gjorde några byten, så jag är klar."

765
00:46:12,230 --> 00:46:17,410
Så vi har en bästa fall gångtid Ω (n).

766
00:46:17,410 --> 00:46:20,680
Låt oss köra bubbla sortera på en lista.

767
00:46:20,680 --> 00:46:23,560
Eller första, låt oss bara titta på några pseudokod verkligen snabbt.

768
00:46:23,560 --> 00:46:28,160
Vi vill säga att vi vill hålla reda på, i varje iteration av slingan,

769
00:46:28,160 --> 00:46:32,190
hålla reda på huruvida vi ändrat några element.

770
00:46:32,190 --> 00:46:37,610
Så anledningen till detta är, vi kommer att sluta när vi inte har bytt några element.

771
00:46:37,610 --> 00:46:41,980
Så i början av vår slinga har vi inte bytt någonting, så vi ska säga att det är falskt.

772
00:46:41,980 --> 00:46:47,170
Nu ska vi gå igenom listan och jämföra inslag i till elementet i + 1

773
00:46:47,170 --> 00:46:50,310
och om det är så att det finns ett större antal till vänster om ett mindre antal,

774
00:46:50,310 --> 00:46:52,310
då vi ska bara byta dem.

775
00:46:52,310 --> 00:46:54,490
>> Och då ska vi komma ihåg att vi bytte ett element.

776
00:46:54,490 --> 00:46:58,900
Det betyder att vi måste gå igenom listan minst 1 gång

777
00:46:58,900 --> 00:47:02,160
eftersom villkoret som vi slutade är när hela listan är redan sorterad,

778
00:47:02,160 --> 00:47:04,890
vilket innebär att vi inte har gjort några swappar.

779
00:47:04,890 --> 00:47:09,960
Så det är därför vårt tillstånd här nere är "samtidigt som vissa delar har bytts."

780
00:47:09,960 --> 00:47:13,720
Så nu ska vi bara titta på detta körs på en lista.

781
00:47:13,720 --> 00:47:16,640
Jag har en lista 5,0,1,6,4.

782
00:47:16,640 --> 00:47:19,850
Bubble Sortera kommer att börja hela vägen till vänster, och det kommer att jämföra

783
00:47:19,850 --> 00:47:24,700
The I elementen, så 0 till i + 1, vilket är elementet 1.

784
00:47:24,700 --> 00:47:29,020
Det kommer att säga, väl 5> 0, men just nu 5 är till vänster,

785
00:47:29,020 --> 00:47:32,500
så jag måste byta 5 och 0.

786
00:47:32,500 --> 00:47:35,470
När jag byta dem, plötsligt får jag denna annorlunda lista.

787
00:47:35,470 --> 00:47:38,260
Nu 5> 1, så vi kommer att byta dem.

788
00:47:38,260 --> 00:47:42,160
5 är inte> 6, så vi behöver inte göra någonting här.

789
00:47:42,160 --> 00:47:46,690
Men 6> 4, så vi måste byta.

790
00:47:46,690 --> 00:47:49,740
Återigen måste vi gå igenom hela listan så småningom upptäcka

791
00:47:49,740 --> 00:47:52,330
att dessa är i ordning, vi byter dem,

792
00:47:52,330 --> 00:47:57,120
och på denna punkt måste vi gå igenom listan 1 gång

793
00:47:57,120 --> 00:48:05,390
att se till att allt är i sin ordning, och på denna punkt bubbla typ är klar.

794
00:48:05,390 --> 00:48:10,720
En annan algoritm för att ta några element och sortera dem är val Sortera.

795
00:48:10,720 --> 00:48:15,740
Tanken bakom val Sortera är att vi ska bygga upp en sorterad del av listan

796
00:48:15,740 --> 00:48:18,150
1 element vid en tidpunkt.

797
00:48:18,150 --> 00:48:23,170
>> Och hur vi ska göra det är genom att bygga upp den vänstra segmentet i listan.

798
00:48:23,170 --> 00:48:27,510
Och i princip varje - på varje steg, vi kommer att ta det minsta elementet vi har kvar

799
00:48:27,510 --> 00:48:32,310
som inte har sorterats ännu, och vi kommer att flytta den till den sorterade segmentet.

800
00:48:32,310 --> 00:48:35,850
Det innebär att vi måste hela tiden hitta den minsta osorterade elementet

801
00:48:35,850 --> 00:48:40,720
och sedan ta det minsta elementet och byta den med vad

802
00:48:40,720 --> 00:48:45,090
vänstra delen som inte är sorterad.

803
00:48:45,090 --> 00:48:50,890
Den kör tid detta kommer att bli O (n ²) eftersom det i värsta fall

804
00:48:50,890 --> 00:48:55,070
vi behöver jämföra varje enskilt element till varje annat element.

805
00:48:55,070 --> 00:48:59,250
Eftersom vi säger att om vi startar på den vänstra halvan av listan, behöver vi

806
00:48:59,250 --> 00:49:02,970
att gå igenom hela högra segmentet att hitta det minsta elementet.

807
00:49:02,970 --> 00:49:05,430
Och sedan återigen måste vi gå över hela högra segmentet och

808
00:49:05,430 --> 00:49:08,210
fortsätta över den om och om och om igen.

809
00:49:08,210 --> 00:49:11,350
Det kommer att vara n ². Vi kommer att behöva en for-slinga inuti en annan för slinga

810
00:49:11,350 --> 00:49:13,350
vilket tyder N ^.

811
00:49:13,350 --> 00:49:16,530
I bästa fall tanken, låt oss säga att vi ger det en redan sorterad lista;

812
00:49:16,530 --> 00:49:19,270
vi faktiskt inte gör något bättre än n ².

813
00:49:19,270 --> 00:49:21,730
Eftersom val sortera har inget sätt att veta att

814
00:49:21,730 --> 00:49:25,540
den minsta delen är bara en jag råkar vara att titta på.

815
00:49:25,540 --> 00:49:28,970
Det behöver fortfarande se till att detta faktiskt är ett minimum.

816
00:49:28,970 --> 00:49:31,670
>> Och det enda sättet att se till att det är minst använda denna algoritm,

817
00:49:31,670 --> 00:49:34,640
är att titta på varje enskilt element igen.

818
00:49:34,640 --> 00:49:38,420
Så egentligen, om du ger det - om du ger val Sortera en redan sorterad lista,

819
00:49:38,420 --> 00:49:42,720
det kommer inte att göra något bättre än att ge det en lista som inte är sorterad ännu.

820
00:49:42,720 --> 00:49:46,320
Förresten, om det råkar vara så att något är O (något)

821
00:49:46,320 --> 00:49:50,640
och omega av något, kan vi bara säga mer koncist att det är θ något.

822
00:49:50,640 --> 00:49:52,760
Så om du ser att komma någonstans, det är vad som just betyder.

823
00:49:52,760 --> 00:49:57,580
>> Om något är theta n ², är det både stora O (n ²) och Ω (n ²).

824
00:49:57,580 --> 00:49:59,790
Så bästa fall och värsta fall gör det inte någon skillnad,

825
00:49:59,790 --> 00:50:04,400
algoritmen kommer att göra samma sak varje gång.

826
00:50:04,400 --> 00:50:06,610
Så detta är vad pseudokod för val Sortera skulle kunna se ut.

827
00:50:06,610 --> 00:50:10,630
Vi i grund och botten kommer att säga att jag vill att iterera över listan

828
00:50:10,630 --> 00:50:15,180
från vänster till höger, och vid varje iteration av slingan, jag ska flytta

829
00:50:15,180 --> 00:50:19,780
minsta elementet i detta sorteras delen av listan.

830
00:50:19,780 --> 00:50:23,260
Och när jag flyttar något där, jag behöver aldrig titta på det elementet igen.

831
00:50:23,260 --> 00:50:28,600
Eftersom så fort jag byter en del i den vänstra segmentet av listan, det sorteras

832
00:50:28,600 --> 00:50:32,600
eftersom vi gör allt i stigande ordning med hjälp av minimum.

833
00:50:32,600 --> 00:50:38,740
Så vi sa okej, vi är i position i, och vi måste titta på alla element

834
00:50:38,740 --> 00:50:42,260
till höger om jag för att finna den minsta.

835
00:50:42,260 --> 00:50:46,150
Så det betyder att vi vill titta på i + 1 till slutet av listan.

836
00:50:46,150 --> 00:50:51,610
Och nu, om elementet som vi för närvarande tittar på är mindre än vår lägsta hittills,

837
00:50:51,610 --> 00:50:54,190
som kom ihåg, vi börjar den minsta av att bara vara

838
00:50:54,190 --> 00:50:57,020
oavsett elementet vi närvarande, jag antar att det är det minsta.

839
00:50:57,020 --> 00:51:00,270
Om jag hittar ett element som är mindre än det, då kommer jag att säga, okej,

840
00:51:00,270 --> 00:51:02,700
Jo, jag har hittat en ny minimum.

841
00:51:02,700 --> 00:51:06,080
Jag ska komma ihåg var den lägsta var.

842
00:51:06,080 --> 00:51:09,560
>> Så nu, när jag har gått igenom denna rätt osorterat segmentet,

843
00:51:09,560 --> 00:51:16,690
Jag kan säga att jag kommer att byta den minsta elementet med element som är på plats i.

844
00:51:16,690 --> 00:51:21,100
Det kommer att bygga upp min lista, min sorterade delen av listan från vänster till höger,

845
00:51:21,100 --> 00:51:25,190
och vi inte någonsin behöver titta på ett element igen när det är i denna del.

846
00:51:25,190 --> 00:51:27,930
När vi har bytt det.

847
00:51:27,930 --> 00:51:30,260
Så låt oss köra val Sortera på denna lista.

848
00:51:30,260 --> 00:51:38,220
Den blå delen här kommer att bli jag, och den röda delen kommer att vara det minsta elementet.

849
00:51:38,220 --> 00:51:41,570
Så jag börjar helt till vänster i listan, så vid 5.

850
00:51:41,570 --> 00:51:44,610
Nu måste vi hitta minsta osorterade elementet.

851
00:51:44,610 --> 00:51:49,480
Så vi säger 0 <5, så 0 är min nya miniminivån.

852
00:51:49,480 --> 00:51:53,820
>> Men jag kan inte stanna där, för även om vi kan erkänna att 0 är den minsta,

853
00:51:53,820 --> 00:51:59,390
vi behöver gå igenom alla andra element i listan för att se.

854
00:51:59,390 --> 00:52:01,760
Så 1 är större, är 6 större, är 4 större.

855
00:52:01,760 --> 00:52:05,850
Det innebär att när du tittar på alla dessa element har jag fastställt 0 är den minsta.

856
00:52:05,850 --> 00:52:09,800
Så jag kommer att byta 5 och 0.

857
00:52:09,800 --> 00:52:15,480
När jag byter det, jag kommer att få en ny lista, och jag vet att jag aldrig behöver titta på det 0 igen

858
00:52:15,480 --> 00:52:19,380
eftersom när jag har bytt det, jag sorteras det och vi är klara.

859
00:52:19,380 --> 00:52:22,730
Nu är det råkar vara så att den blå delen är återigen 5,

860
00:52:22,730 --> 00:52:26,030
och vi måste titta på 1, 6 och 4 för att fastställa att 1

861
00:52:26,030 --> 00:52:31,520
är den minsta minsta elementet, så vi byta 1 och 5.

862
00:52:31,520 --> 00:52:36,890
Återigen måste vi titta på - jämför 5 till 6 och 4,

863
00:52:36,890 --> 00:52:39,830
och vi kommer att byta 4 och 5, och slutligen, jämför

864
00:52:39,830 --> 00:52:45,740
dessa 2 siffror och byta dem tills vi får vår sorterad lista.

865
00:52:45,740 --> 00:52:49,730
Eventuella frågor om val Sortera?

866
00:52:49,730 --> 00:52:56,420
Okej. Låt oss gå till den sista frågan här, och det är rekursion.

867
00:52:56,420 --> 00:52:59,810
>> Rekursion, kom ihåg, detta är verkligen meta sak där en funktion

868
00:52:59,810 --> 00:53:02,740
upprepade gånger kallar sig.

869
00:53:02,740 --> 00:53:05,620
Så någon gång, medan vår fuction upprepade gånger kallar sig,

870
00:53:05,620 --> 00:53:10,100
måste det finnas någon punkt där vi sluta ringa oss.

871
00:53:10,100 --> 00:53:13,670
För om vi inte gör det, då vi bara kommer att fortsätta att göra detta för evigt,

872
00:53:13,670 --> 00:53:16,660
och vårt program är bara inte att avsluta.

873
00:53:16,660 --> 00:53:19,200
Vi kallar detta tillstånd basfallet.

874
00:53:19,200 --> 00:53:22,570
Och basfallet säger, snarare än att ringa en funktion igen,

875
00:53:22,570 --> 00:53:25,330
Jag ska bara returnera något värde.

876
00:53:25,330 --> 00:53:28,080
Så när vi har återvänt till ett värde har vi slutat kalla oss själva,

877
00:53:28,080 --> 00:53:32,550
och resten av de samtal vi har gjort hittills kan också återvända.

878
00:53:32,550 --> 00:53:36,050
Motsatsen till basfallet är den rekursiva fallet.

879
00:53:36,050 --> 00:53:39,050
Och det är när vi vill ringa ett annat samtal till den funktion som vi nu i.

880
00:53:39,050 --> 00:53:44,690
Och vi förmodligen, men inte alltid, vill använda olika argument.

881
00:53:44,690 --> 00:53:48,940
>> Så om vi har en funktion som kallas f och f bara kallas ta 1 argument,

882
00:53:48,940 --> 00:53:52,010
och vi håller bara ringa f (1), f (1), f (1), och det råkar vara så att

883
00:53:52,010 --> 00:53:56,510
argumentet 1 faller in rekursiv fall, vi ändå aldrig kommer att sluta.

884
00:53:56,510 --> 00:54:01,620
Även om vi har en bas fall måste vi se till att så småningom ska vi träffa den basfall.

885
00:54:01,620 --> 00:54:04,250
Vi vill inte bara hålla vistas i denna rekursiva fallet.

886
00:54:04,250 --> 00:54:09,870
Generellt när vi kallar oss, vi kommer förmodligen att ha olika argument varje gång.

887
00:54:09,870 --> 00:54:12,700
Här är en riktigt enkel rekursiv funktion.

888
00:54:12,700 --> 00:54:15,090
Så det här kommer att beräkna fakulteten av ett tal.

889
00:54:15,090 --> 00:54:17,790
Uppe här har vi vår bas fallet.

890
00:54:17,790 --> 00:54:22,330
I det fall att n ≤ 1, vi kommer inte att ringa faktoriell igen.

891
00:54:22,330 --> 00:54:26,490
Vi kommer att sluta, vi ska bara returnera något värde.

892
00:54:26,490 --> 00:54:30,170
Om detta inte är sant, så ska vi träffa vår rekursiva fallet.

893
00:54:30,170 --> 00:54:33,550
Notera här att vi inte bara kallar fakultet (n), eftersom det inte skulle vara till stor hjälp.

894
00:54:33,550 --> 00:54:36,810
Vi kommer att kalla fakulteten av något annat.

895
00:54:36,810 --> 00:54:40,850
>> Och så att du kan se, så småningom om vi passerar en faktoriell (5) eller något,

896
00:54:40,850 --> 00:54:45,900
vi kommer att ringa faktoriell (4) och så vidare, och så småningom kommer vi att träffa Detta basfall.

897
00:54:45,900 --> 00:54:51,730
Så här ser bra ut. Låt oss se vad som händer när vi faktiskt köra.

898
00:54:51,730 --> 00:54:57,840
Detta är stacken, och låt oss säga att främsta kommer att kalla denna funktion med ett argument (4).

899
00:54:57,840 --> 00:55:02,200
Så när faktoriell ser och = 4, kommer fakulteten kalla sig.

900
00:55:02,200 --> 00:55:05,010
Nu, plötsligt har vi faktoriell (3).

901
00:55:05,010 --> 00:55:10,780
Så dessa funktioner kommer att fortsätta växa tills slutligen vi träffar vår basfallet.

902
00:55:10,780 --> 00:55:17,830
Vid denna punkt, är returvärdet av detta avkastningen (nx returvärdet av detta),

903
00:55:17,830 --> 00:55:21,290
returvärdet av detta är nx returvärdet av detta.

904
00:55:21,290 --> 00:55:23,290
Så småningom måste vi träffa några nummer.

905
00:55:23,290 --> 00:55:26,560
På toppen här, säger vi tillbaka 1.

906
00:55:26,560 --> 00:55:30,650
Det innebär att när vi tillbaka det numret kan vi pop detta utanför stapeln.

907
00:55:30,650 --> 00:55:36,570
Så denna fakultet (1) görs.

908
00:55:36,570 --> 00:55:41,190
När 1 återvänder, detta faktorförsök (1) avkastning, denna återgång till 1.

909
00:55:41,190 --> 00:55:46,910
Avkastningen värdet av detta, kom ihåg, var nx returvärdet av detta.

910
00:55:46,910 --> 00:55:50,720
Så plötsligt vet den här killen som jag vill återvända 2.

911
00:55:50,720 --> 00:55:55,910
>> Så kom ihåg, returnera värdet av detta är bara nx returvärdet här uppe.

912
00:55:55,910 --> 00:56:01,160
Så nu kan vi säga 3 x 2, och slutligen, här kan vi säga

913
00:56:01,160 --> 00:56:04,010
detta bara kommer att vara 4 x 3 x 2.

914
00:56:04,010 --> 00:56:09,570
Och när detta avkastning, får vi ner till en enda heltal inuti huvud.

915
00:56:09,570 --> 00:56:15,460
Eventuella frågor om rekursion?

916
00:56:15,460 --> 00:56:17,090
Okej. Så det finns mer tid för frågor i slutet,

917
00:56:17,090 --> 00:56:23,360
men nu Josef kommer att täcka de återstående ämnena.

918
00:56:23,360 --> 00:56:25,590
>> [Joseph Ong] Okej. Så nu när vi har pratat om rekursioner,

919
00:56:25,590 --> 00:56:27,840
Låt oss prata lite om vad samman slag är.

920
00:56:27,840 --> 00:56:31,740
Merge Sortera är i grunden ett annat sätt att sortera en lista med tal.

921
00:56:31,740 --> 00:56:36,430
Och hur det fungerar är, med merge sort du har en lista, och vad vi gör är

922
00:56:36,430 --> 00:56:39,120
vi säger, låt oss dela detta till 2 halvor.

923
00:56:39,120 --> 00:56:42,750
Vi kommer först köra samman Sortera igen på den vänstra halvan,

924
00:56:42,750 --> 00:56:45,040
då skall vi köra ihop Sortera på den högra halvan,

925
00:56:45,040 --> 00:56:50,240
och det ger oss nu 2 halvor som sorteras, och nu ska vi kombinera dessa halvorna.

926
00:56:50,240 --> 00:56:55,010
Det är lite svårt att se utan ett exempel, så går vi igenom hela proceduren och se vad som händer.

927
00:56:55,010 --> 00:56:59,590
Så du börjar med den här listan, vi dela den i 2 halvor.

928
00:56:59,590 --> 00:57:02,300
Vi kör samman Sortera på vänster halv först.

929
00:57:02,300 --> 00:57:06,660
Så det är den vänstra halvan, och nu kör vi dem genom den här listan igen

930
00:57:06,660 --> 00:57:09,800
som får skickas in sammanslagning sortera och vi ser återigen

931
00:57:09,800 --> 00:57:13,270
på vänster sida av denna lista, och vi kör ihop Sortera på den.

932
00:57:13,270 --> 00:57:15,880
Nu får vi ner till en lista med 2 siffror,

933
00:57:15,880 --> 00:57:19,010
och nu den vänstra halvan är bara 1 del långa, och vi kan inte

934
00:57:19,010 --> 00:57:23,380
dela en lista som är endast 1 element i halv, så vi bara säga, när vi har 50,

935
00:57:23,380 --> 00:57:26,400
vilket är bara 1 del, det är redan sorterade.

936
00:57:26,400 --> 00:57:29,860
>> När vi är klara med det, kan vi se att vi kan

937
00:57:29,860 --> 00:57:32,230
gå vidare till den högra halvan av listan,

938
00:57:32,230 --> 00:57:36,480
och 3 är också sorteras och så nu att båda halvorna av denna lista sorteras

939
00:57:36,480 --> 00:57:39,080
Vi kan ansluta sig till dessa siffror tillsammans igen.

940
00:57:39,080 --> 00:57:45,320
Så vi ser på 50 och 3, 3 är mindre än 50, så det går in först och därefter 50 kommer in

941
00:57:45,320 --> 00:57:49,340
Nu är det gjort, vi gå upp till den listan och sortera det är rätt halv.

942
00:57:49,340 --> 00:57:52,440
42 är dess eget nummer, så det är redan sorterade.

943
00:57:52,440 --> 00:57:57,850
Så nu har vi jämföra dessa 2 och 3 är mindre än 42, så får ställas på första,

944
00:57:57,850 --> 00:58:02,340
nu 42 får sätta in, och 50 får sätta in

945
00:58:02,340 --> 00:58:07,220
Nu, det är sorterade går vi hela vägen tillbaka till toppen, 1337 och 15.

946
00:58:07,220 --> 00:58:14,560
Tja, vi ser nu på den vänstra halvan av denna lista, 1337 är i sig så det är sorterade och samma med 15.

947
00:58:14,560 --> 00:58:19,020
Så nu vi kombinera dessa 2 siffror för att sortera den ursprungliga listan, 15 <1337,

948
00:58:19,020 --> 00:58:23,060
så det går i först, sedan 1337 går in

949
00:58:23,060 --> 00:58:26,640
Och nu har vi sorterade båda halvorna av den ursprungliga listan uppe.

950
00:58:26,640 --> 00:58:30,440
Och allt vi behöver göra är att kombinera dessa.

951
00:58:30,440 --> 00:58:36,890
Vi tittar på de första 2 siffrorna i denna förteckning, 3 <15, så det går in i typ arrayen först.

952
00:58:36,890 --> 00:58:44,460
15 <42, så det går i. Nu, 42 <1337, som går in

953
00:58:44,460 --> 00:58:51,010
50 <1337, så det går in och märker att vi bara tog 2 nummer av denna lista.

954
00:58:51,010 --> 00:58:53,640
Så vi är bara växlar mellan de 2 listorna.

955
00:58:53,640 --> 00:58:56,050
Vi söker bara i början, och vi tar elementet

956
00:58:56,050 --> 00:59:00,270
Det är mindre och sedan sätta det i vårt utbud.

957
00:59:00,270 --> 00:59:04,080
Nu har vi samman alla halvor och vi är klara.

958
00:59:04,080 --> 00:59:07,780
>> Har du frågor om samman slag? Ja?

959
00:59:07,780 --> 00:59:14,190
[Student] Om det är att dela in i olika grupper, varför de inte dela bara en gång

960
00:59:14,190 --> 00:59:19,970
och du har 3 och 2 i en grupp? [Övriga frågor obegriplig]

961
00:59:19,970 --> 00:59:24,940
Anledningen - så frågan är, varför kan vi inte bara ihop dem på det första steget efter att vi har dem?

962
00:59:24,940 --> 00:59:29,530
Anledningen till att vi kan göra detta, starta vid den vänstra element på båda sidor,

963
00:59:29,530 --> 00:59:33,040
och sedan ta den mindre och placera den i, är att vi vet att dessa

964
00:59:33,040 --> 00:59:35,290
enskilda listor i sorterade order.

965
00:59:35,290 --> 00:59:37,290
Så om jag tittar på den vänstra delarna av båda halvorna,

966
00:59:37,290 --> 00:59:40,490
Jag vet att de kommer att vara de minsta delarna av dessa listor.

967
00:59:40,490 --> 00:59:43,930
Så jag kan sätta dem i det minsta elementet fläckar av denna stora lista.

968
00:59:43,930 --> 00:59:47,810
Å andra sidan, om jag tittar på de 2 listorna i den andra nivån där borta,

969
00:59:47,810 --> 00:59:51,640
50, 3, 42, 1337 och 15, är de inte sorteras.

970
00:59:51,640 --> 00:59:55,770
Så om jag tittar på 50 och 1337, kommer jag att lägga 50 i min lista först.

971
00:59:55,770 --> 01:00:00,130
Men det gör inte riktigt mening, eftersom 3 är den minsta delen av alla av dem.

972
01:00:00,130 --> 01:00:04,390
Så det enda skälet till att vi kan göra detta kombinerar steg är att våra listor redan är sorterade.

973
01:00:04,390 --> 01:00:07,010
Det är därför vi måste få ner hela vägen till botten

974
01:00:07,010 --> 01:00:09,800
för när vi bara har ett enda nummer, du vet att ett enda nummer

975
01:00:09,800 --> 01:00:14,120
i och för sig är redan en sorterad lista.

976
01:00:14,120 --> 01:00:19,360
>> Några frågor? Nej?

977
01:00:19,360 --> 01:00:24,260
Komplexitet? Tja, kan du se att i varje steg finns end nummer,

978
01:00:24,260 --> 01:00:27,590
och vi kan dela en lista i halva log n gånger,

979
01:00:27,590 --> 01:00:31,700
som är där vi får denna n x log n komplexitet.

980
01:00:31,700 --> 01:00:34,940
Och du kommer att se det bästa fallet för sammanslagning slag är n log n, och det råkar vara så

981
01:00:34,940 --> 01:00:39,340
att det värsta fallet, eller Ω borta, är också n log n.

982
01:00:39,340 --> 01:00:42,480
Något att tänka på.

983
01:00:42,480 --> 01:00:45,750
Går vidare, låt oss gå vidare till några super grundläggande fil-I / O.

984
01:00:45,750 --> 01:00:48,830
Om du tittat på Scramble, kommer du att märka att vi hade någon form av system

985
01:00:48,830 --> 01:00:51,270
där du kan skriva till en loggfil om du läser igenom koden.

986
01:00:51,270 --> 01:00:53,730
Låt oss se hur du kan göra det.

987
01:00:53,730 --> 01:00:57,450
Tja, vi har fprintf, som du kan tänka på som bara printf,

988
01:00:57,450 --> 01:01:01,720
men bara skriver ut till en fil i stället, och därmed f i början.

989
01:01:01,720 --> 01:01:07,570
Denna typ av kod här uppe, vad den gör är, som ni kanske har sett i Scramble,

990
01:01:07,570 --> 01:01:12,310
det går igenom din 2-dimensionell array utskrift av rad för rad vad siffrorna är.

991
01:01:12,310 --> 01:01:17,850
I det här fallet, printf skriver ut till din terminal eller vad vi kallar standard ut av avsnitt.

992
01:01:17,850 --> 01:01:22,170
>> Och nu, i det här fallet är allt vi har att göra ersätta printf med fprintf,

993
01:01:22,170 --> 01:01:26,770
tala om vad fil du vill skriva ut till, och i det här fallet bara skriver ut det till den filen

994
01:01:26,770 --> 01:01:32,230
istället för att skriva ut det till din terminal.

995
01:01:32,230 --> 01:01:36,500
Nå, då väcker frågan: Var ska vi få denna typ av fil från, eller hur?

996
01:01:36,500 --> 01:01:39,840
Vi passerade logga in på denna fprintf fuction men vi hade ingen aning om var den kom ifrån.

997
01:01:39,840 --> 01:01:43,980
Jo, i början av koden, vad vi hade var denna bit av kod här borta,

998
01:01:43,980 --> 01:01:48,340
som i princip säger att öppna filen kallar log.txt.

999
01:01:48,340 --> 01:01:53,220
Vad vi gör när det är vi måste se till att filen faktiskt öppnas framgångsrikt.

1000
01:01:53,220 --> 01:01:57,070
Så det kan misslyckas av flera anledningar, du har inte tillräckligt med utrymme på din dator, till exempel.

1001
01:01:57,070 --> 01:01:59,790
Så det är alltid viktigt innan du gör någon verksamhet med filen

1002
01:01:59,790 --> 01:02:03,300
att vi kontrollera om den filen öppnades framgångsrikt.

1003
01:02:03,300 --> 01:02:09,330
Så vad om att en, det är ett argument till fopen, ja, vi kan öppna en fil på många sätt.

1004
01:02:09,330 --> 01:02:13,510
Vad vi kan göra är, kan vi ge det w, vilket innebär åsidosätta filen om det kommer ut redan,

1005
01:02:13,510 --> 01:02:18,070
Vi kan skicka en en, som de lägga till i slutet av filen i stället för tvingande det,

1006
01:02:18,070 --> 01:02:22,730
eller så kan vi specificera r, vilket betyder, låt oss öppna filen som skrivskyddad.

1007
01:02:22,730 --> 01:02:24,890
Så om programmet försöker göra några ändringar i filen,

1008
01:02:24,890 --> 01:02:30,140
skrika på dem och inte låta dem göra det.

1009
01:02:30,140 --> 01:02:33,320
Slutligen, när vi är klara med filen, gjort gjort operationer på det,

1010
01:02:33,320 --> 01:02:35,860
Vi måste se till att vi stänger filen.

1011
01:02:35,860 --> 01:02:38,830
Och så i slutet av ditt program, du kommer att passera dem igen

1012
01:02:38,830 --> 01:02:42,120
denna fil som du öppnade, och bara stänga den.

1013
01:02:42,120 --> 01:02:44,650
Så detta är något viktigt som du måste se till att du gör det.

1014
01:02:44,650 --> 01:02:47,180
Så kom ihåg att du kan öppna en fil, kan du skriva till filen,

1015
01:02:47,180 --> 01:02:51,270
göra verksamheten i filen, men då måste man stänga filen i slutet.

1016
01:02:51,270 --> 01:02:53,270
>> Eventuella frågor om grundläggande fil-I / O? Ja?

1017
01:02:53,270 --> 01:02:58,050
[Student fråga, obegripligt]

1018
01:02:58,050 --> 01:03:02,480
Just här. Frågan är inte om detta log.txt fil visas?

1019
01:03:02,480 --> 01:03:07,890
Tja, om du bara ger den log.txt skapas den i samma katalog som den körbara.

1020
01:03:07,890 --> 01:03:10,500
Så om Du är - >> [Student fråga, obegripligt]

1021
01:03:10,500 --> 01:03:18,830
Ja. I samma mapp, eller i samma katalog, som du kallar det.

1022
01:03:18,830 --> 01:03:21,400
Nu minne, stack och heap.

1023
01:03:21,400 --> 01:03:23,400
Så hur är minnet som anges i datorn?

1024
01:03:23,400 --> 01:03:26,270
Tja, du kan tänka minne som en slags detta block här.

1025
01:03:26,270 --> 01:03:30,260
Och i minnet har vi vad som kallas högen fastnat borta, och stapeln som är där nere.

1026
01:03:30,260 --> 01:03:34,480
Och högen växer nedåt och stapeln växer uppåt.

1027
01:03:34,480 --> 01:03:38,620
Så som Tommy nämnde - Åh, ja, och vi har dessa andra 4 segment som jag kommer till i en andra -

1028
01:03:38,620 --> 01:03:42,890
Som Tommy sa tidigare, vet du hur hans funktioner kallar sig och ringa varandra?

1029
01:03:42,890 --> 01:03:44,930
De bygger upp denna typ av stack ram.

1030
01:03:44,930 --> 01:03:47,360
Tja, om viktiga samtal foo, blir foo sätta på stacken.

1031
01:03:47,360 --> 01:03:52,430
Foo kallar bar, bar få oss sätta på stacken, och som får sätta på stacken efter.

1032
01:03:52,430 --> 01:03:57,040
Och när de återvänder, var de får tas bort från stacken.

1033
01:03:57,040 --> 01:04:00,140
Vad gör håller alla dessa platser och minne?

1034
01:04:00,140 --> 01:04:03,110
Tja, innehåller den övre, som är den text segmentet själva programmet.

1035
01:04:03,110 --> 01:04:06,390
Så maskinkod, som finns där när du kompilerar programmet.

1036
01:04:06,390 --> 01:04:08,520
Därefter varje initierad globala variabler.

1037
01:04:08,520 --> 01:04:12,660
>> Så du har globala variabler i ditt program, och du säger som en = 5,

1038
01:04:12,660 --> 01:04:15,260
som får placeras i detta segment, och rätt under det,

1039
01:04:15,260 --> 01:04:18,990
du har oinitierade globala data, som just är int a,

1040
01:04:18,990 --> 01:04:20,990
men du säger inte att det är lika med någonting.

1041
01:04:20,990 --> 01:04:23,870
Inse detta är globala variabler, så de är utanför huvud.

1042
01:04:23,870 --> 01:04:28,560
Så detta betyder alla globala variabler som deklarerats men inte initierats.

1043
01:04:28,560 --> 01:04:32,310
Så vad som finns i högen? Minne fördelas med hjälp av malloc, som vi kommer till i en liten bit.

1044
01:04:32,310 --> 01:04:35,990
Och slutligen, med stapeln du har lokala variabler

1045
01:04:35,990 --> 01:04:39,950
och alla funktioner du kan ringa i någon av deras parametrar.

1046
01:04:39,950 --> 01:04:43,720
Det sista, behöver du inte verkligen måste veta vad miljövariabler gör,

1047
01:04:43,720 --> 01:04:46,700
men när du kör programmet, det är något samband, liksom

1048
01:04:46,700 --> 01:04:49,550
Detta är användarnamnet på den person som körde programmet.

1049
01:04:49,550 --> 01:04:51,550
Och det kommer att bli typ av nedtill.

1050
01:04:51,550 --> 01:04:54,540
I termer av minnesadresser, som är hexadecimala värden,

1051
01:04:54,540 --> 01:04:58,170
värdena på toppen start på 0, och de går hela vägen ner till botten.

1052
01:04:58,170 --> 01:05:00,440
I detta fall, om du är på 32-bitars system,

1053
01:05:00,440 --> 01:05:05,390
adressen längst ner kommer att bli 0x följt av af, eftersom det är 32 bitar,

1054
01:05:05,390 --> 01:05:10,890
vilket är 8 bitgrupper, och i detta fall 8 bitgrupper motsvarar 8 hexadecimala siffror.

1055
01:05:10,890 --> 01:05:20,110
Så här nere du kommer att få, liksom, 0xFFFFFF och upp där du kommer att ha 0.

1056
01:05:20,110 --> 01:05:23,660
Så vad är pekare? Några av er kanske inte har täckt detta i avsnittet innan.

1057
01:05:23,660 --> 01:05:26,660
men vi gick över den i föreläsning, så en pekare är bara en datatyp

1058
01:05:26,660 --> 01:05:34,030
vilka butiker, i stället för någon form av värde som 50, lagrar den adressen för en viss plats i minnet.

1059
01:05:34,030 --> 01:05:36,020
Precis som minne [obegripliga].

1060
01:05:36,020 --> 01:05:41,120
Så i det här fallet, det vi har är, har vi en pekare till ett heltal eller en int *,

1061
01:05:41,120 --> 01:05:46,210
och den innehåller det hexadecimala adressen för 0xDEADBEEF.

1062
01:05:46,210 --> 01:05:50,880
>> Så vad vi har är nu, denna pekare pekar på en viss plats i minnet,

1063
01:05:50,880 --> 01:05:56,020
och det är bara en, är värdet 50 på den här minnesplats.

1064
01:05:56,020 --> 01:06:01,810
På vissa 32-bitars system, på alla 32-bitars system, pekare tar upp 32 bitar eller 4 byte.

1065
01:06:01,810 --> 01:06:06,020
Men till exempel på en 64-bitars system, pekare är 64 bitar.

1066
01:06:06,020 --> 01:06:08,040
Så det är något du kommer att vilja ha i åtanke.

1067
01:06:08,040 --> 01:06:12,310
Så på ett ände-bitars system, är en pekare end bitar lång.

1068
01:06:12,310 --> 01:06:17,320
Pekare är typ av svårt att smälta utan extra saker,

1069
01:06:17,320 --> 01:06:20,300
så låt oss gå igenom ett exempel på dynamisk minnesallokering.

1070
01:06:20,300 --> 01:06:25,130
Vilka dynamisk minnesallokering gör för dig, eller vad vi kallar malloc,

1071
01:06:25,130 --> 01:06:29,280
det kan du fördela någon form av data utanför apparaten.

1072
01:06:29,280 --> 01:06:31,830
Så denna data är typ av mer permanent för programmets löptid.

1073
01:06:31,830 --> 01:06:36,430
För som du vet, om du deklarerar X inuti en funktion, och som returnerar funktion,

1074
01:06:36,430 --> 01:06:40,910
du inte längre har tillgång till de data som lagrats i x.

1075
01:06:40,910 --> 01:06:44,420
Vilka pekare låt oss göra är att de låter oss lagra minne eller lagra värden

1076
01:06:44,420 --> 01:06:46,840
i ett annat segment av minnet, nämligen högen.

1077
01:06:46,840 --> 01:06:49,340
Nu när vi återvänder ur funktion, så länge vi har en pekare

1078
01:06:49,340 --> 01:06:54,960
till den platsen i minnet, vad vi kan göra är att vi bara kan titta på de värden där.

1079
01:06:54,960 --> 01:06:58,020
Låt oss titta på ett exempel: Det här är vårt minne layout igen.

1080
01:06:58,020 --> 01:07:00,050
Och vi har denna funktion, huvud.

1081
01:07:00,050 --> 01:07:06,870
Vad den gör är - okej, så enkelt, eller hur -? Int x = 5, det är bara en variabel på stacken i main.

1082
01:07:06,870 --> 01:07:12,450
>> Å andra sidan, nu har vi deklarera en pekare som anropar funktionen giveMeThreeInts.

1083
01:07:12,450 --> 01:07:16,800
Och så nu går vi in ​​i denna funktion och vi skapar en ny bunt ram för den.

1084
01:07:16,800 --> 01:07:20,440
Men i denna stack ram, förklarar vi int * temp,

1085
01:07:20,440 --> 01:07:23,210
som i mallocs 3 heltal för oss.

1086
01:07:23,210 --> 01:07:25,880
Så storleken på int kommer att ge oss hur många byte här int är,

1087
01:07:25,880 --> 01:07:29,620
och malloc ger oss att många byte utrymme på högen.

1088
01:07:29,620 --> 01:07:32,890
Så i det här fallet har vi skapat tillräckligt med utrymme för 3 heltal,

1089
01:07:32,890 --> 01:07:36,830
och högen är vägen upp där, det är därför jag har ritat det högre upp.

1090
01:07:36,830 --> 01:07:42,900
När vi är klara, vi kommer tillbaka hit, behöver du bara 3 Ints tillbaka,

1091
01:07:42,900 --> 01:07:47,000
och den returnerar adressen, i detta fall över var att minnet är.

1092
01:07:47,000 --> 01:07:51,250
Och vi satt pekare = switch och upp där vi har bara en annan pekare.

1093
01:07:51,250 --> 01:07:54,550
Men vad det returnerar funktionen staplas här och försvinner.

1094
01:07:54,550 --> 01:07:59,250
Så temp försvinner, men vi har fortfarande behålla adressen där

1095
01:07:59,250 --> 01:08:01,850
dessa 3 heltal är inuti elnätet.

1096
01:08:01,850 --> 01:08:06,180
Så i denna uppsättning, kommer pekarna är scoped lokalt för staplade ramen,

1097
01:08:06,180 --> 01:08:09,860
men minnet som de avser är i högen.

1098
01:08:09,860 --> 01:08:12,190
>> Verkar det vettigt?

1099
01:08:12,190 --> 01:08:14,960
[Student] Kan du upprepa det? >> [Joseph] Ja.

1100
01:08:14,960 --> 01:08:20,270
Så om jag går tillbaka bara lite, ser du att temp tilldelade

1101
01:08:20,270 --> 01:08:23,500
viss minnet på högen uppe.

1102
01:08:23,500 --> 01:08:28,680
Så när denna funktion giveMeThreeInts returer, detta stack här kommer att försvinna.

1103
01:08:28,680 --> 01:08:35,819
Och med det någon av variablerna, i detta fall, denna pekare som tilldelats i staplade ram.

1104
01:08:35,819 --> 01:08:39,649
Som kommer att försvinna, men eftersom vi återvände temp

1105
01:08:39,649 --> 01:08:46,330
och vi satt pekare = temp, pekare är nu att peka på samma minne av plats som temp var.

1106
01:08:46,330 --> 01:08:50,370
Så nu, även om vi förlorar temp, det lokala pekare,

1107
01:08:50,370 --> 01:08:59,109
Vi har fortfarande kvar minnesadressen vad det pekar på insidan av denna variabel pekare.

1108
01:08:59,109 --> 01:09:03,740
Frågor? Det kan vara lite av en förvirrande ämne om du inte har gått över den i avsnitt.

1109
01:09:03,740 --> 01:09:09,240
Vi kan, kommer din TF definitivt gå över den och naturligtvis kan vi svara på frågor

1110
01:09:09,240 --> 01:09:11,500
I slutet av översynen sessionen för detta.

1111
01:09:11,500 --> 01:09:14,220
Men detta är en slags komplext ämne, och jag har fler exempel som kommer att visa upp

1112
01:09:14,220 --> 01:09:18,790
som hjälper klargöra vad pekare faktiskt är.

1113
01:09:18,790 --> 01:09:22,500
>> I detta fall, pekare motsvarar matriser,

1114
01:09:22,500 --> 01:09:25,229
så jag kan bara använda denna pekare som samma sak som en int array.

1115
01:09:25,229 --> 01:09:29,840
Så jag indexera in 0 och ändra den första heltalet till 1,

1116
01:09:29,840 --> 01:09:39,689
ändra andra heltalet till 2, och den 3: e heltal till 3.

1117
01:09:39,689 --> 01:09:44,210
Så mer på pekare. Tja, minns Binky.

1118
01:09:44,210 --> 01:09:48,319
I det här fallet har vi tilldelas en pekare, eller vi förklarade en pekare,

1119
01:09:48,319 --> 01:09:52,760
men först, när jag bara förklarade en pekare, det pekar inte till någonstans i minnet.

1120
01:09:52,760 --> 01:09:54,930
Det är bara skräp värden i den.

1121
01:09:54,930 --> 01:09:56,470
Så jag har ingen aning om var denna pekare pekar på.

1122
01:09:56,470 --> 01:10:01,630
Den har en adress som bara är fylld med 0 s och 1 s där det ursprungligen deklarerade.

1123
01:10:01,630 --> 01:10:04,810
Jag kan inte göra någonting med det här tills jag kallar malloc på det

1124
01:10:04,810 --> 01:10:08,390
och då det ger mig lite utrymme på högen där jag kan sätta värden på insidan.

1125
01:10:08,390 --> 01:10:11,980
Då igen, jag vet inte vad som finns inuti detta minne.

1126
01:10:11,980 --> 01:10:16,780
Så det första jag måste göra är att kontrollera om systemet hade tillräckligt med minne

1127
01:10:16,780 --> 01:10:20,850
att ge mig tillbaka 1 heltal i första hand, vilket är varför jag gör denna kontroll.

1128
01:10:20,850 --> 01:10:25,020
Om pekaren är noll, innebär det att det inte har tillräckligt med utrymme eller något annat fel uppstod,

1129
01:10:25,020 --> 01:10:26,320
så jag skulle gå ut ur mitt program.

1130
01:10:26,320 --> 01:10:29,400
 Men om det lyckades, nu kan jag använda det pekare

1131
01:10:29,400 --> 01:10:35,020
och vad * pekare gör det följer där adressen är

1132
01:10:35,020 --> 01:10:38,480
där detta värde är, och det sätter det lika med 1.

1133
01:10:38,480 --> 01:10:41,850
Så här borta, vi kontrollerar om minnet fanns.

1134
01:10:41,850 --> 01:10:45,380
>> När du vet det finns, kan du sätta i det

1135
01:10:45,380 --> 01:10:50,460
vilket värde du vill lägga in den, i det här fallet 1.

1136
01:10:50,460 --> 01:10:53,060
När vi är klara med det, måste du frigöra den pekare

1137
01:10:53,060 --> 01:10:57,160
eftersom vi måste gå tillbaka till det system som minne som du bad om i första hand.

1138
01:10:57,160 --> 01:10:59,690
Eftersom datorn inte vet när vi är klara med det.

1139
01:10:59,690 --> 01:11:02,510
I det här fallet är vi uttryckligen säger det, okej, vi gjort med detta minne.

1140
01:11:02,510 --> 01:11:10,780
Om någon annan process behöver det, något annat program behöver det, gärna gå vidare och ta den.

1141
01:11:10,780 --> 01:11:15,110
Vad vi kan också göra är att vi bara kan få adressen till lokala variabler på apparaten.

1142
01:11:15,110 --> 01:11:19,080
Så int x är innanför staplade ramen viktigaste.

1143
01:11:19,080 --> 01:11:23,060
Och när vi använder denna ampersand, detta och operatör, vad den gör är

1144
01:11:23,060 --> 01:11:27,310
det tar x, och x är bara några data i minnet, men det har en adress.

1145
01:11:27,310 --> 01:11:33,790
Det ligger någonstans. Så genom att ringa & X, vad detta innebär är att det ger oss adressen till x.

1146
01:11:33,790 --> 01:11:38,430
Genom att göra detta, vi gör pekare pekar på där x är i minnet.

1147
01:11:38,430 --> 01:11:41,710
Nu har vi bara inte något som * x, vi kommer att få 5 tillbaka.

1148
01:11:41,710 --> 01:11:43,820
Stjärnan heter dereferencing det.

1149
01:11:43,820 --> 01:11:46,640
Du följer adressen och du får värdet av den lagrade där.

1150
01:11:51,000 --> 01:11:53,310
>> Några frågor? Ja?

1151
01:11:53,310 --> 01:11:56,500
[Student] Om du inte gör det 3-spetsiga sak, inte kompilera det fortfarande?

1152
01:11:56,500 --> 01:11:59,490
Ja. Om du inte gör det 3-pekaren sak, det kommer fortfarande att sammanställa,

1153
01:11:59,490 --> 01:12:02,720
men jag ska visa dig vad som händer i en sekund och utan att göra det,

1154
01:12:02,720 --> 01:12:04,860
Det är vad vi kallar en minnesläcka. Du ger inte systemet

1155
01:12:04,860 --> 01:12:07,850
tillbaka sitt minne, så efter ett tag att programmet kommer att ackumulera

1156
01:12:07,850 --> 01:12:10,940
minne att det inte är med, och ingenting annat kan använda den.

1157
01:12:10,940 --> 01:12:15,750
Om du någonsin sett Firefox med 1,5 miljoner kilobyte på datorn,

1158
01:12:15,750 --> 01:12:17,840
i Aktivitetshanteraren, det är vad som händer.

1159
01:12:17,840 --> 01:12:20,760
Du har en minnesläcka i programmet som de inte hanterar.

1160
01:12:23,080 --> 01:12:26,240
Så hur fungerar pekaren aritmetiska arbete?

1161
01:12:26,240 --> 01:12:29,480
Tja, pekare aritmetik ungefär som indexering i en matris.

1162
01:12:29,480 --> 01:12:36,370
I det här fallet har jag en pekare, och vad jag gör är att jag gör pekare pekar på det första elementet

1163
01:12:36,370 --> 01:12:42,100
denna uppsättning av 3 heltal som jag har tilldelats.

1164
01:12:42,100 --> 01:12:46,670
Så nu vad jag gör, ändrar stjärna pekare bara det första elementet i listan.

1165
01:12:46,670 --> 01:12:49,140
Star pointer en poäng här.

1166
01:12:49,140 --> 01:12:53,140
Så pekaren är över här, pekaren en hit, är pekaren 2 här.

1167
01:12:53,140 --> 01:12:56,610
>> Så bara lägga 1 är samma sak som att flytta längs denna rad.

1168
01:12:56,610 --> 01:12:59,880
Vad vi gör är att när vi gör pekaren en får du adressen hit,

1169
01:12:59,880 --> 01:13:04,180
och för att få värdet i här sätter du en stjärna i från hela uttrycket

1170
01:13:04,180 --> 01:13:05,990
att avreferera det.

1171
01:13:05,990 --> 01:13:09,940
Så i det här fallet, jag sätta den första platsen i denna matris till 1,

1172
01:13:09,940 --> 01:13:13,970
andra plats till 2, och den tredje plats till 3.

1173
01:13:13,970 --> 01:13:18,180
Sen vad jag gör här borta är jag skriver vår pekare +1,

1174
01:13:18,180 --> 01:13:19,970
vilket ger mig bara 2.

1175
01:13:19,970 --> 01:13:23,650
Nu är jag inkrementera pekare, så pekare lika pekare +1,

1176
01:13:23,650 --> 01:13:26,780
som flyttar den framåt.

1177
01:13:26,780 --> 01:13:30,810
Och så nu om jag skriver ut pekare +1, är pekare ett nu 3,

1178
01:13:30,810 --> 01:13:33,990
som i detta fall skriver ut 3.

1179
01:13:33,990 --> 01:13:36,560
Och för att fritt någonting, pekaren att jag ger det

1180
01:13:36,560 --> 01:13:40,540
måste peka i början av kedjan som jag kom tillbaka från malloc.

1181
01:13:40,540 --> 01:13:43,430
Så i det här fallet, om jag skulle ringa 3 här, skulle detta inte vara rätt,

1182
01:13:43,430 --> 01:13:45,070
eftersom det är i mitten av matrisen.

1183
01:13:45,070 --> 01:13:48,820
Jag måste subtrahera för att komma till den ursprungliga platsen

1184
01:13:48,820 --> 01:13:50,420
den initiala första plats innan jag kan befria det.

1185
01:13:56,300 --> 01:13:58,450
Så, här är en mer engagerad exempel.

1186
01:13:58,450 --> 01:14:03,360
I det här fallet, vi fördela 7 tecken i en karaktär array.

1187
01:14:03,360 --> 01:14:06,480
>> Och i detta fall vad vi gör är att vi looping över de första 6 av dem,

1188
01:14:06,480 --> 01:14:09,900
och vi sätta dem till Z.

1189
01:14:09,900 --> 01:14:13,350
Så, för int i = 0, i> 6, i + +,

1190
01:14:13,350 --> 01:14:16,220
Så, pekare + jag kommer bara ge oss, i detta fall,

1191
01:14:16,220 --> 01:14:20,860
pekare, +1 pekare, +2 pekare, pekare +3 och så vidare och så vidare i slingan.

1192
01:14:20,860 --> 01:14:24,040
Vad det kommer att göra är att det blir den adressen, dereferences den för att få värdet,

1193
01:14:24,040 --> 01:14:27,440
och förändringar som värde till ett Z.

1194
01:14:27,440 --> 01:14:30,350
Sedan i slutet ihåg detta är en sträng, eller hur?

1195
01:14:30,350 --> 01:14:33,560
Alla strängar måste sluta med noll avslutande karaktär.

1196
01:14:33,560 --> 01:14:38,620
Så vad jag gör är i pekare 6 Jag lade null terminator tecknet i.

1197
01:14:38,620 --> 01:14:43,980
Och nu vad jag i grund och botten ska göra hit genomför printf efter en sträng, eller hur?

1198
01:14:43,980 --> 01:14:46,190
>> Så, när printf nu när det är nått slutet av en sträng?

1199
01:14:46,190 --> 01:14:48,230
När den träffar noll avslutande karaktär.

1200
01:14:48,230 --> 01:14:52,030
Så i detta fall min ursprungliga pekaren pekar på början av denna uppsättning.

1201
01:14:52,030 --> 01:14:56,410
Jag skriver ut det första tecknet ut. Jag flyttar den över en.

1202
01:14:56,410 --> 01:14:58,420
Jag skriver ut det tecknet ut. Jag flyttar den över.

1203
01:14:58,420 --> 01:15:02,180
Och jag fortsätter att göra det tills jag kommer till slutet.

1204
01:15:02,180 --> 01:15:07,750
Och nu i slutet * pekaren dereference detta och få noll avslutande tecknet tillbaka.

1205
01:15:07,750 --> 01:15:11,780
Och så min while-slinga körs endast när värdet inte är null avslutande tecken.

1206
01:15:11,780 --> 01:15:13,770
Så nu har jag avslutar ur denna slinga.

1207
01:15:18,780 --> 01:15:21,180
Och så om jag subtraherar 6 från denna pekare,

1208
01:15:21,180 --> 01:15:22,860
Jag går tillbaka ända till början.

1209
01:15:22,860 --> 01:15:27,880
Kom ihåg, jag gör det här för att jag måste gå till början för att frigöra det.

1210
01:15:27,880 --> 01:15:30,270
>> Så, jag vet att det var en hel del. Finns det några frågor?

1211
01:15:30,270 --> 01:15:31,870
Snälla, ja?

1212
01:15:31,870 --> 01:15:36,610
[Student fråga obegriplig]

1213
01:15:36,610 --> 01:15:38,190
Kan du säga det högre? Ursäkta.

1214
01:15:38,190 --> 01:15:44,140
[Student] På den sista bilden till höger innan du befriade pekaren,

1215
01:15:44,140 --> 01:15:47,300
var var du ändrar faktiskt värdet av pekaren?

1216
01:15:47,300 --> 01:15:50,370
[Josef] Så här. >> [Student] Åh, okej.

1217
01:15:50,370 --> 01:15:51,890
[Josef] Så jag har en pekare minus minus, höger,

1218
01:15:51,890 --> 01:15:54,140
som flyttar sak tillbaka en, och sedan jag befria det,

1219
01:15:54,140 --> 01:15:57,000
eftersom denna pekare måste pekade på början av arrayen.

1220
01:15:57,000 --> 01:16:00,420
[Student] Men det skulle behövas hade du slutade efter den linjen.

1221
01:16:00,420 --> 01:16:03,130
[Josef] Så om jag hade slutat efter detta skulle detta betraktas som en minnesläcka,

1222
01:16:03,130 --> 01:16:04,810
eftersom jag inte kör gratis.

1223
01:16:04,810 --> 01:16:11,290
[Student] I [obegripliga] efter de första tre raderna där du hade pekare en [obegripliga].

1224
01:16:11,290 --> 01:16:13,140
[Joseph] Uh-huh. Så, vad är frågan där?

1225
01:16:13,140 --> 01:16:14,780
Ursäkta. Nej, nej. Gå, gå, snälla.

1226
01:16:14,780 --> 01:16:16,870
[Student] Så ändrar du inte värdet av pekare.

1227
01:16:16,870 --> 01:16:19,130
Du skulle inte ha behövt göra pekare minus minus.

1228
01:16:19,130 --> 01:16:19,730
[Josef] Ja, exakt.

1229
01:16:19,730 --> 01:16:21,890
Så när jag gör pekare +1 och pekare 2,

1230
01:16:21,890 --> 01:16:24,410
Jag gör pekare lika pekare +1.

1231
01:16:24,410 --> 01:16:27,260
Så pekaren bara förblir pekar på början av arrayen.

1232
01:16:27,260 --> 01:16:31,460
Det är bara när jag gör plus plus att det sätter värdet tillbaka in pekaren,

1233
01:16:31,460 --> 01:16:33,550
att det rör sig faktiskt detta tillsammans.

1234
01:16:36,860 --> 01:16:37,780
Okej.

1235
01:16:40,550 --> 01:16:42,030
Fler frågor?

1236
01:16:44,680 --> 01:16:47,790
>> Återigen, om detta är typ av överväldigande, kommer detta att behandlas i sessionen.

1237
01:16:47,790 --> 01:16:50,710
Fråga din undervisning karl om det, och vi kan svara på frågor i slutet.

1238
01:16:53,510 --> 01:16:56,600
Och brukar vi gillar inte att göra det minus sak.

1239
01:16:56,600 --> 01:16:59,760
Detta måste tvinga mig att hålla koll på hur mycket jag har offset i arrayen.

1240
01:16:59,760 --> 01:17:04,520
Så i allmänhet, detta är bara för att förklara hur fungerar pekaren aritmetiska.

1241
01:17:04,520 --> 01:17:07,970
Men vad vi brukar vilja göra är att vi vill skapa en kopia av pekaren,

1242
01:17:07,970 --> 01:17:11,640
och sedan kommer vi att använda kopian när vi ska flytta runt i strängen.

1243
01:17:11,640 --> 01:17:14,660
Så i dessa fall du använder kopian för att skriva ut hela strängen,

1244
01:17:14,660 --> 01:17:19,040
men vi behöver inte göra som pekare minus 6 eller hålla koll på hur mycket vi flyttade detta,

1245
01:17:19,040 --> 01:17:22,700
bara för att vi vet att vår ursprungliga punkten fortfarande pekar på början av listan

1246
01:17:22,700 --> 01:17:25,340
och allt som vi ändrade var denna kopia.

1247
01:17:25,340 --> 01:17:28,250
Så i allmänhet, ändra kopior av din ursprungliga pekaren.

1248
01:17:28,250 --> 01:17:32,350
Försök inte att sortera av liknande - inte ändra original.

1249
01:17:32,350 --> 01:17:35,290
Försöker ändra bara kopior av originalet.

1250
01:17:41,540 --> 01:17:44,870
Så märker du när vi passerar strängen i printf

1251
01:17:44,870 --> 01:17:48,990
du behöver inte sätta en stjärna framför det som vi gjorde med alla andra dereferences, eller hur?

1252
01:17:48,990 --> 01:17:54,180
Så, om du skriver ut hela strängen% s förväntar är en adress,

1253
01:17:54,180 --> 01:17:57,610
och i detta fall en pekare eller i detta fall som en uppsättning tecken.

1254
01:17:57,610 --> 01:18:00,330
>> Tecken, char * s, och arrayer är samma sak.

1255
01:18:00,330 --> 01:18:03,690
Pointer är att tecken och tecken arrayer är samma sak.

1256
01:18:03,690 --> 01:18:05,720
Och så är klara allt vi behöver göra i pekaren.

1257
01:18:05,720 --> 01:18:08,150
Vi behöver inte gå in som * pekare eller något liknande.

1258
01:18:13,110 --> 01:18:14,930
Så arrayer och pekare är samma sak.

1259
01:18:14,930 --> 01:18:19,160
När du gör något som x [y] hit för en matris,

1260
01:18:19,160 --> 01:18:21,960
vad den gör under huven är det säger, okej, det är ett tecken array,

1261
01:18:21,960 --> 01:18:23,690
så det är en pekare.

1262
01:18:23,690 --> 01:18:26,510
Och så x är samma sak,

1263
01:18:26,510 --> 01:18:28,650
och så vad den gör är det tillför y till x,

1264
01:18:28,650 --> 01:18:31,820
vilket är samma sak som att flytta framåt i minnet så mycket.

1265
01:18:31,820 --> 01:18:34,930
Och nu x + y ger oss någon form av adress,

1266
01:18:34,930 --> 01:18:37,570
och vi dereference adressen eller följ pilen

1267
01:18:37,570 --> 01:18:41,640
där den platsen i minnet är och vi får det värde ur den platsen i minnet.

1268
01:18:41,640 --> 01:18:43,720
Så, så dessa två är exakt samma sak.

1269
01:18:43,720 --> 01:18:45,840
Det är bara en syntaktisk socker.

1270
01:18:45,840 --> 01:18:48,090
De gör samma sak. De är bara olika syntactics för varandra.

1271
01:18:51,500 --> 01:18:57,590
>> Så, vad kan gå fel med pekare? Liksom, en hel del. Okej. Så dåliga saker.

1272
01:18:57,590 --> 01:19:02,410
Vissa dåliga saker du kan göra är att inte kontrollera om din malloc samtal returnerar null, eller hur?

1273
01:19:02,410 --> 01:19:06,560
I det här fallet, jag ber systemet att ge mig - vad är det numret?

1274
01:19:06,560 --> 01:19:11,200
Som 2 miljarder gånger 4, eftersom storleken på ett heltal är 4 byte.

1275
01:19:11,200 --> 01:19:13,810
Jag ber den för som 8 miljarder byte.

1276
01:19:13,810 --> 01:19:17,270
Naturligtvis min dator inte kommer att kunna ge mig så mycket minne tillbaka.

1277
01:19:17,270 --> 01:19:20,960
Och vi inte kontrollera om det är null, så när vi försöker dereference det där -

1278
01:19:20,960 --> 01:19:24,270
Följ pilen till där det kommer att - vi har inte det minnet.

1279
01:19:24,270 --> 01:19:27,150
Detta är vad vi kallar dereferencing en null-pekare.

1280
01:19:27,150 --> 01:19:29,710
Och detta orsakar i huvudsak att du segmenteringsfel.

1281
01:19:29,710 --> 01:19:31,790
Detta är ett av de sätt du kan segmenteringsfel.

1282
01:19:34,090 --> 01:19:38,090
Andra dåliga saker du kan göra - jaha.

1283
01:19:38,090 --> 01:19:40,650
Det var dereferencing en null-pekare. Okej.

1284
01:19:40,650 --> 01:19:45,160
Andra dåliga saker - ja, att fixa att du bara sätta en kontroll i det

1285
01:19:45,160 --> 01:19:46,980
som kontrollerar om pekaren är null

1286
01:19:46,980 --> 01:19:51,000
och avsluta ur programmet om det händer att malloc returnerar en null-pekare.

1287
01:19:55,110 --> 01:19:59,850
Det är xkcd komiska. Folk förstår det nu. Sortera på.

1288
01:20:06,120 --> 01:20:09,350
>> Så, minne. Och jag gick över detta.

1289
01:20:09,350 --> 01:20:12,000
Vi kallar malloc i en slinga, men varje gång vi kallar malloc

1290
01:20:12,000 --> 01:20:14,370
vi förlorar reda på var denna pekare pekar på,

1291
01:20:14,370 --> 01:20:15,750
eftersom vi dunkardags det.

1292
01:20:15,750 --> 01:20:18,410
Så ger det första samtalet till malloc mig minnet hit.

1293
01:20:18,410 --> 01:20:19,990
Min pekaren pekare till detta.

1294
01:20:19,990 --> 01:20:23,020
Nu har jag inte frigöra det, så nu kallar jag malloc igen.

1295
01:20:23,020 --> 01:20:26,070
Nu pekar hit. Nu mitt minne pekar hit.

1296
01:20:26,070 --> 01:20:27,640
Pekar hit. Pekar hit.

1297
01:20:27,640 --> 01:20:31,820
Men jag har förlorat kontakten med adresserna till allt minne hit som jag tilldelats.

1298
01:20:31,820 --> 01:20:35,100
Och så nu har jag inte någon hänvisning till dem längre.

1299
01:20:35,100 --> 01:20:37,230
Så kan jag befria dem inte utanför denna slinga.

1300
01:20:37,230 --> 01:20:39,390
Och så för att fixa något sådant,

1301
01:20:39,390 --> 01:20:42,250
om du glömmer att frigöra minne och du får denna minnesläcka,

1302
01:20:42,250 --> 01:20:45,810
Du måste frigöra minne inuti denna slinga när du är klar med det.

1303
01:20:45,810 --> 01:20:51,400
Tja, detta är vad som händer. Jag vet massor av du hatar det här.

1304
01:20:51,400 --> 01:20:55,270
Men nu - yay! Du får som 44.000 kilobyte.

1305
01:20:55,270 --> 01:20:57,110
Så befria dig det i slutet av slingan,

1306
01:20:57,110 --> 01:20:59,770
och det kommer att bara frigöra minne varje gång.

1307
01:20:59,770 --> 01:21:03,620
I huvudsak har programmet inte en minnesläcka längre.

1308
01:21:03,620 --> 01:21:08,150
>> Och nu något annat du kan göra är frigöra minne som du har bett om två gånger.

1309
01:21:08,150 --> 01:21:11,060
I det här fallet kan du malloc något, ändrar du dess värde.

1310
01:21:11,060 --> 01:21:13,140
Du frigöra det en gång för att du sa att du var klar med den.

1311
01:21:13,140 --> 01:21:14,940
Men sedan vi befriade det igen.

1312
01:21:14,940 --> 01:21:16,730
Detta är något som är ganska dålig.

1313
01:21:16,730 --> 01:21:18,820
Det kommer inte att initialt segmenteringsfel,

1314
01:21:18,820 --> 01:21:23,350
men efter ett tag Vad detta innebär är dubbelt frigör detta korrumperar din hög struktur,

1315
01:21:23,350 --> 01:21:27,200
och du får lära dig lite mer om detta om du väljer att ta en klass som CS61.

1316
01:21:27,200 --> 01:21:30,000
Men i huvudsak efter ett tag din dator kommer att bli förvirrad

1317
01:21:30,000 --> 01:21:33,010
om vilka minnesplatser är där och var den finns -

1318
01:21:33,010 --> 01:21:34,800
där data lagras i minnet.

1319
01:21:34,800 --> 01:21:38,080
Och så frigör en pekare två gånger är en dålig sak som du inte vill göra.

1320
01:21:38,080 --> 01:21:41,600
>> Andra saker som kan gå fel är att inte använda sizeof.

1321
01:21:41,600 --> 01:21:44,460
Så i detta fall du malloc 8 byte,

1322
01:21:44,460 --> 01:21:46,700
och det är samma sak som två heltal, eller hur?

1323
01:21:46,700 --> 01:21:49,580
Så, det är helt säkert, men är det?

1324
01:21:49,580 --> 01:21:52,160
Tja, som Lucas talade om på olika arkitekturer,

1325
01:21:52,160 --> 01:21:54,220
heltal är av olika längder.

1326
01:21:54,220 --> 01:21:57,970
Så, på den apparat som du använder, heltal är ca 4 byte,

1327
01:21:57,970 --> 01:22:02,370
men på något annat system de kan vara 8 byte eller de kan vara 16 byte.

1328
01:22:02,370 --> 01:22:05,680
Så om jag bara använder detta nummer här,

1329
01:22:05,680 --> 01:22:07,310
detta program kan fungera på apparaten,

1330
01:22:07,310 --> 01:22:10,360
men det kommer inte att fördela tillräckligt med minne på något annat system.

1331
01:22:10,360 --> 01:22:14,020
I det här fallet är det vad sizeof operatören används till.

1332
01:22:14,020 --> 01:22:16,880
När vi kallar sizeof (int), vad detta innebär är

1333
01:22:16,880 --> 01:22:21,910
 det ger oss stor ett heltal på systemet som programmet körs.

1334
01:22:21,910 --> 01:22:25,490
Så i detta fall kommer sizeof (int) returnera 4 på något som apparaten,

1335
01:22:25,490 --> 01:22:29,980
och nu denna vilja 4 * 2, vilket är 8,

1336
01:22:29,980 --> 01:22:32,330
vilket är precis den mängd utrymme som krävs för två heltal.

1337
01:22:32,330 --> 01:22:36,710
På ett annat system, om en int är som 16 byte eller 8 byte,

1338
01:22:36,710 --> 01:22:39,380
det är bara att gå tillbaka tillräckligt byte för att lagra detta belopp.

1339
01:22:41,830 --> 01:22:45,310
>> Och slutligen, structs.

1340
01:22:45,310 --> 01:22:48,340
Så om du ville spara en sudoku styrelse i minnet, hur kan vi göra detta?

1341
01:22:48,340 --> 01:22:51,570
Du kanske tänker på som en variabel för det första,

1342
01:22:51,570 --> 01:22:53,820
en variabel för andra sak, en variabel för den tredje sak,

1343
01:22:53,820 --> 01:22:56,420
en variabel för det fjärde sak - dåligt, eller hur?

1344
01:22:56,420 --> 01:23:00,750
Så, en förbättring kan du göra på toppen av detta för att göra en 9 x 9 matris.

1345
01:23:00,750 --> 01:23:04,480
Det är bra, men vad händer om du ville att andra saker med sudoku styrelse

1346
01:23:04,480 --> 01:23:06,490
gillar vad svårigheten i styrelsen är,

1347
01:23:06,490 --> 01:23:11,740
eller, till exempel, vad din poäng är, eller hur mycket tid det har tagit dig att lösa detta forum?

1348
01:23:11,740 --> 01:23:14,970
Tja, vad du kan göra är att du kan skapa en struktur.

1349
01:23:14,970 --> 01:23:18,910
Vad jag i grunden säger är att jag definierar denna struktur här,

1350
01:23:18,910 --> 01:23:23,230
och jag definierar en sudoku styrelse som består av en styrelse som är 9 x 9.

1351
01:23:23,230 --> 01:23:26,650
>> Och vad den har den har pekare till namnet på nivån.

1352
01:23:26,650 --> 01:23:30,730
Det har också x och y, som är koordinaterna för där jag är just nu.

1353
01:23:30,730 --> 01:23:35,980
Det har också tid [obegriplig], och det har det totala antalet drag som jag har registrerats hittills.

1354
01:23:35,980 --> 01:23:40,010
Och så i det här fallet kan jag gruppera en massa data i endast en struktur

1355
01:23:40,010 --> 01:23:42,790
istället för att ha det som flyger runt i likhet olika variabler

1356
01:23:42,790 --> 01:23:44,540
att jag inte kan riktigt hålla reda på.

1357
01:23:44,540 --> 01:23:49,720
Och det låter oss har bara trevligt syntax för slags hänvisningar olika saker inuti denna struct.

1358
01:23:49,720 --> 01:23:53,430
Jag kan bara göra board.board, och jag får sudoku styrelsen tillbaka.

1359
01:23:53,430 --> 01:23:56,320
Board.level får jag hur svårt det är.

1360
01:23:56,320 --> 01:24:00,540
Board.x och board.y ge mig koordinaterna för där jag kan vara i styrelsen.

1361
01:24:00,540 --> 01:24:04,730
Och så jag åt det vi kallar fält i struct.

1362
01:24:04,730 --> 01:24:08,840
Detta definierar sudokuBoard, som är en typ som jag har.

1363
01:24:08,840 --> 01:24:14,800
Och nu är vi här. Jag har en variabel som heter "board" av typen sudokuBoard.

1364
01:24:14,800 --> 01:24:18,820
Och så nu jag kan komma åt alla fält som utgör denna struktur här.

1365
01:24:20,830 --> 01:24:22,450
>> Har du frågor om structs? Ja?

1366
01:24:22,450 --> 01:24:25,890
[Student] För int x, y, förklarade ni båda på en rad? >> [Joseph] Uh-huh.

1367
01:24:25,890 --> 01:24:27,400
[Student] Så kan du göra just det med alla?

1368
01:24:27,400 --> 01:24:31,200
Liksom i x, y kommatecken gånger totalt?

1369
01:24:31,200 --> 01:24:34,460
[Josef] Ja, kan du definitivt göra det, men anledningen till att jag satte x och y på samma rad -

1370
01:24:34,460 --> 01:24:36,330
och frågan är varför kan vi bara göra det på samma linje?

1371
01:24:36,330 --> 01:24:38,600
Varför inte vi bara sätta alla dessa på samma linje är

1372
01:24:38,600 --> 01:24:42,090
x och y är relaterade till varandra,

1373
01:24:42,090 --> 01:24:44,780
och detta är bara stilistiskt mer korrekt, i en mening,

1374
01:24:44,780 --> 01:24:46,600
eftersom det är gruppering två saker på samma linje

1375
01:24:46,600 --> 01:24:49,340
som gillar typ av rör samma sak.

1376
01:24:49,340 --> 01:24:51,440
Och jag dela just dessa isär. Det är bara en stil sak.

1377
01:24:51,440 --> 01:24:53,720
Det gör funktionellt ingen skillnad alls.

1378
01:24:58,150 --> 01:24:59,270
Alla andra frågor om structs?

1379
01:25:03,030 --> 01:25:06,620
Du kan definiera en Pokédex med struct.

1380
01:25:06,620 --> 01:25:11,720
En Pokémon har ett nummer och det har ett brev, en ägare, en typ.

1381
01:25:11,720 --> 01:25:16,990
Och sedan om du har en mängd Pokémon, kan du göra en Pokédex, eller hur?

1382
01:25:16,990 --> 01:25:20,810
Okej, coolt. Så frågor om structs. Det är relaterade till structs.

1383
01:25:20,810 --> 01:25:25,270
>> Slutligen, GDB. Vad låter GDB du göra? Det låter dig felsöka ditt program.

1384
01:25:25,270 --> 01:25:27,650
Och om du inte har använt GDB, skulle jag rekommenderar att titta på korta

1385
01:25:27,650 --> 01:25:31,250
och bara gå över vad GDB är, hur du arbetar med det, hur du kan använda den,

1386
01:25:31,250 --> 01:25:32,900
och testa den på ett program.

1387
01:25:32,900 --> 01:25:37,400
Och så vad GDB kan du göra det låter pausa [obegripliga] upp ditt program

1388
01:25:37,400 --> 01:25:38,920
och en praktisk linje.

1389
01:25:38,920 --> 01:25:42,600
Till exempel vill jag pausa utförande på som linje 3 i mitt program,

1390
01:25:42,600 --> 01:25:46,010
och medan jag är på linje 3 Jag kan skriva ut alla värden som finns där.

1391
01:25:46,010 --> 01:25:49,710
Och så vad vi kallar som pausa i en linje

1392
01:25:49,710 --> 01:25:52,350
är kallar vi detta sätta en brytpunkt på den linjen

1393
01:25:52,350 --> 01:25:55,920
och då kan vi skriva ut variabler på tillståndet i programmet vid den tiden.

1394
01:25:55,920 --> 01:25:58,990
>> Vi kan sedan därifrån gå igenom programmet rad för rad.

1395
01:25:58,990 --> 01:26:03,200
Och då kan vi titta på tillståndet i stacken på tiden.

1396
01:26:03,200 --> 01:26:08,600
Och så för att kunna använda GDB, vad vi gör är att vi kallar klang på C-filen,

1397
01:26:08,600 --> 01:26:11,290
men vi måste passera den-ggdb flaggan.

1398
01:26:11,290 --> 01:26:15,850
Och när vi är klara med att vi bara köra gdb på den resulterande utdatafilen.

1399
01:26:15,850 --> 01:26:18,810
Och så får du lite liknande massa text som denna,

1400
01:26:18,810 --> 01:26:21,990
men egentligen allt du behöver göra är att skriva in kommandon i början.

1401
01:26:21,990 --> 01:26:24,250
Break sätter en brytpunkt på huvud.

1402
01:26:24,250 --> 01:26:28,470
Lista 400 listar kodrader runt linjen 400.

1403
01:26:28,470 --> 01:26:31,410
Och så i det här fallet kan du bara titta runt och säga, Åh,

1404
01:26:31,410 --> 01:26:34,360
Jag vill ställa en brytpunkt på rad 397, vilket är denna linje,

1405
01:26:34,360 --> 01:26:37,170
och sedan ditt program körs i det steget och det kommer att bryta.

1406
01:26:37,170 --> 01:26:41,120
Det kommer att pausa det, och du kan skriva ut, till exempel värdet av låg eller hög.

1407
01:26:41,120 --> 01:26:46,410
Och så finns det en massa kommandon du behöver veta,

1408
01:26:46,410 --> 01:26:48,660
och det här bildspelet kommer att gå upp på hemsidan,

1409
01:26:48,660 --> 01:26:54,000
så om du bara vill referera dessa eller liknande sätta dem på din fuska lakan, gärna.

1410
01:26:54,000 --> 01:27:00,650
>> Cool. Det var Quiz Recension 0, och vi kommer stanna kvar om du har några frågor.

1411
01:27:00,650 --> 01:27:03,850
Okej.

1412
01:27:03,850 --> 01:27:09,030
>>  [Applåder]

1413
01:27:09,030 --> 01:27:13,000
>> [CS50.TV]