1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Uke 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard University]

3
00:00:04,000 --> 00:00:08,000
[Dette er CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Dette er CS50, og dette er begynnelsen av uke 6,

5
00:00:12,000 --> 00:00:16,000
så et par nye verktøy er nå tilgjengelig for deg å dra nytte av,

6
00:00:16,000 --> 00:00:19,000
hvorav den første heter CS50 Style.

7
00:00:19,000 --> 00:00:22,000
Odds er hvis du er som meg eller noen av de pedagogiske fellows,

8
00:00:22,000 --> 00:00:26,000
du har sikkert sett et program der stilen ser litt noe sånt som dette.

9
00:00:26,000 --> 00:00:30,000
Kanskje du begynner å kutte noen hjørner sent på kvelden, eller du vil takle det senere,

10
00:00:30,000 --> 00:00:32,000
og deretter en TF eller CA kommer over i kontortiden.

11
00:00:32,000 --> 00:00:34,000
Da er det vanskelig for oss å lese.

12
00:00:34,000 --> 00:00:38,000
Vel, er denne koden syntaktisk korrekt, og det vil kompilere, og det vil faktisk kjøre.

13
00:00:38,000 --> 00:00:40,000
Men det er definitivt ikke en 5 for stil.

14
00:00:40,000 --> 00:00:45,000
>> Men nå, hvis vi går inn i denne katalogen her-

15
00:00:45,000 --> 00:00:48,000
og merker at jeg har conditions2.c-

16
00:00:48,000 --> 00:00:55,000
og jeg kjører denne nye kommandoen, style50, på denne filen conditions2.c, Enter,

17
00:00:55,000 --> 00:00:57,000
legge merke til at det er informert meg om at det har vært stilisert.

18
00:00:57,000 --> 00:01:00,000
Gedit merke til at filen er blitt endret på disk,

19
00:01:00,000 --> 00:01:08,000
og hvis jeg klikker laste, er alle dine problemer nå automatisert.

20
00:01:08,000 --> 00:01:15,000
[Applaus]

21
00:01:15,000 --> 00:01:17,000
Det er en av de tingene vi gjorde denne helgen.

22
00:01:17,000 --> 00:01:20,000
Innse at det er ufullkommen fordi det er noen kode

23
00:01:20,000 --> 00:01:23,000
at det ganske enkelt ikke vil være i stand til å stylize perfekt,

24
00:01:23,000 --> 00:01:26,000
men innser at dette er nå et verktøy du kan dra nytte av

25
00:01:26,000 --> 00:01:33,000
hvis bare å rydde opp noen av de mer errantly plassert klammeparentes og lignende.

26
00:01:33,000 --> 00:01:36,000
>> Men mer oppsiktsvekkende er nå CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Med CS50 sjekk, kan du faktisk utføre de samme korrekthet tester

28
00:01:39,000 --> 00:01:42,000
på din egen kode som de pedagogiske stipendiatene er i stand til.

29
00:01:42,000 --> 00:01:44,000
Dette er et kommandolinjeverktøy som kommer nå i apparatet

30
00:01:44,000 --> 00:01:46,000
så snart du gjør en update50 som per

31
00:01:46,000 --> 00:01:49,000
pset 4 spesifikasjoner, og du bruker det i hovedsak som dette.

32
00:01:49,000 --> 00:01:51,000
Du kjører kommandoen check50.

33
00:01:51,000 --> 00:01:56,000
Så du passerer i en kommandolinje argument, eller mer generelt kjent som en bryter eller et flagg.

34
00:01:56,000 --> 00:01:58,000
Vanligvis er ting som har bindestrek kalles en switch

35
00:01:58,000 --> 00:02:02,000
til en kommandolinje program, spesifiserer så-c

36
00:02:02,000 --> 00:02:04,000
kontrollene som du ønsker å kjøre.

37
00:02:04,000 --> 00:02:07,000
>> De testene du vil kjøre identifiseres unikt ved denne strengen,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Med andre ord, det er bare en tilfeldig, men unike streng

40
00:02:13,000 --> 00:02:18,000
som vi bruker for å identifisere pset 4 er korrekthet tester.

41
00:02:18,000 --> 00:02:21,000
Og så du angir et mellomrom separert liste over filene du vil laste opp

42
00:02:21,000 --> 00:02:24,000
til CS50 Sjekk for analyse.

43
00:02:24,000 --> 00:02:29,000
For eksempel, hvis jeg går inn løsningen min her for resize.c-

44
00:02:29,000 --> 00:02:31,000
la meg åpne opp et større terminal vindu-

45
00:02:31,000 --> 00:02:42,000
og jeg går videre og kjøre la oss si check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
og da jeg går videre og angi navn på filene,

47
00:02:46,000 --> 00:02:49,000
resize.c, og trykk Enter, det komprimerer,

48
00:02:49,000 --> 00:02:53,000
han laster opp, sjekker det, og jeg bare ikke klarte en hel haug med tester.

49
00:02:53,000 --> 00:02:59,000
Den i rødt øverst til venstre sier at resize.c og bmp eksisterer.

50
00:02:59,000 --> 00:03:01,000
Som var testen. Det var spørsmålet vi spurte.

51
00:03:01,000 --> 00:03:04,000
Og det er ulykkelig fordi svaret var falsk.

52
00:03:04,000 --> 00:03:08,000
Den hvite teksten nedenfor står det forventes bmp.h å eksistere, og det er bare min feil.

53
00:03:08,000 --> 00:03:11,000
Jeg glemte å laste den opp, så jeg trenger å laste opp begge filene,

54
00:03:11,000 --> 00:03:14,000
resize.c og bmp.h.

55
00:03:14,000 --> 00:03:17,000
Men nå merke alle de andre testene er i gul fordi de ikke har kjørt,

56
00:03:17,000 --> 00:03:21,000
og så smilefjes er loddrett fordi han er verken glad eller trist,

57
00:03:21,000 --> 00:03:25,000
men vi må oppreisning at problemet i rødt før de andre kontroller vil kjøre.

58
00:03:25,000 --> 00:03:27,000
>> La meg fikse dette.

59
00:03:27,000 --> 00:03:30,000
La meg zoome ut og kjøre denne, denne gangen med bmp.h også

60
00:03:30,000 --> 00:03:34,000
på kommandolinjen, Enter, og nå hvis alt går bra,

61
00:03:34,000 --> 00:03:38,000
det kommer til å sjekke og deretter returnere et resultat av-hold pusten-

62
00:03:38,000 --> 00:03:42,000
alle grønne, som betyr at jeg gjør det veldig bra på pset 4 så langt.

63
00:03:42,000 --> 00:03:44,000
Du kan se og slutte fra den beskrivende teksten her

64
00:03:44,000 --> 00:03:47,000
nøyaktig hva det er vi testet.

65
00:03:47,000 --> 00:03:49,000
Vi testet først gjøre filene eksisterer?

66
00:03:49,000 --> 00:03:51,000
Vi testet gjør resize.c kompilere?

67
00:03:51,000 --> 00:03:58,000
Da vi testet den ikke endre størrelsen på et 1x1-pixel BMP når n, endre størrelse faktor, er en.

68
00:03:58,000 --> 00:04:01,000
Nå, hvis du ikke har noen anelse om hva n er, vil du når du dykke inn pset 4,

69
00:04:01,000 --> 00:04:04,000
men det er rett og slett en mental helse sjekk for å være sikker på at du ikke er resizing

70
00:04:04,000 --> 00:04:08,000
et bilde i det hele tatt hvis resize faktoren er en.

71
00:04:08,000 --> 00:04:14,000
Hvis derimot, endrer det en 1x1 pixel til en 1x1 piksel BMP til 2x2 riktig

72
00:04:14,000 --> 00:04:19,000
når n er 2, da tilsvarende danner gruven tilsvarende.

73
00:04:19,000 --> 00:04:22,000
>> Kort sagt, er dette ment å, en, ta krysset fingrene

74
00:04:22,000 --> 00:04:25,000
ut av ligningen rett før du sender inn pset.

75
00:04:25,000 --> 00:04:28,000
Vil du vite nøyaktig hva TF vil snart vite

76
00:04:28,000 --> 00:04:30,000
når du går om å sende inn noen av disse oppgavesett,

77
00:04:30,000 --> 00:04:34,000
og også den pedagogiske motivasjonen er virkelig å sette

78
00:04:34,000 --> 00:04:37,000
muligheten foran deg, slik at når du vet a priori

79
00:04:37,000 --> 00:04:39,000
at det er feil i koden din og tester som ikke blir bestått,

80
00:04:39,000 --> 00:04:43,000
du kan putte i mer effektiv tid foran for å løse disse problemene

81
00:04:43,000 --> 00:04:45,000
snarere enn å miste poeng, få tilbakemeldinger fra TF din,

82
00:04:45,000 --> 00:04:48,000
og deretter gå, "Ahh," som jeg skulle ha funnet det ut.

83
00:04:48,000 --> 00:04:50,000
Nå minst er det et verktøy som hjelper deg med å finne det.

84
00:04:50,000 --> 00:04:52,000
Det er ikke til å påpeke hvor feilen er, men det vil fortelle deg

85
00:04:52,000 --> 00:04:54,000
hva er symptomatisk for den.

86
00:04:54,000 --> 00:04:57,000
>> Nå innser testene er ikke nødvendigvis uttømmende.

87
00:04:57,000 --> 00:04:59,000
Bare fordi du får en skjerm full av grønne smilefjes

88
00:04:59,000 --> 00:05:02,000
betyr ikke det at koden er perfekt, men det betyr

89
00:05:02,000 --> 00:05:06,000
at det har gått visse tester foreskrevet av spec.

90
00:05:06,000 --> 00:05:08,000
Noen ganger er vi ikke slipper sjekker.

91
00:05:08,000 --> 00:05:10,000
For eksempel, whodunit, en av de aspektene av pset 4,

92
00:05:10,000 --> 00:05:15,000
er litt skuffende hvis vi gir deg

93
00:05:15,000 --> 00:05:18,000
svaret på hva det er, og det er en rekke måter å avsløre

94
00:05:18,000 --> 00:05:21,000
hvem personen er i det røde støy.

95
00:05:21,000 --> 00:05:24,000
Spec vil alltid spesifisere i fremtiden for pset 5 videre

96
00:05:24,000 --> 00:05:26,000
hva sjekker finnes for deg.

97
00:05:26,000 --> 00:05:28,000
Du vil merke det er denne hvite nettadressen nederst.

98
00:05:28,000 --> 00:05:30,000
For nå, dette er bare diagnostisk utgang.

99
00:05:30,000 --> 00:05:33,000
Hvis du besøker denne webadressen, vil du få en hel haug med gale, kryptiske meldinger

100
00:05:33,000 --> 00:05:36,000
at du er velkommen til å se gjennom, men det er mest for de ansatte

101
00:05:36,000 --> 00:05:41,000
slik at vi kan diagnostisere og feilsøke bugs i check50 selv.

102
00:05:41,000 --> 00:05:46,000
>> Uten ado, la oss gå videre til der vi slapp.

103
00:05:46,000 --> 00:05:48,000
CS50 bibliotek vi tok for gitt for noen uker,

104
00:05:48,000 --> 00:05:52,000
men deretter siste uke, startet vi peeling tilbake en av lagene i den.

105
00:05:52,000 --> 00:05:55,000
Vi begynte å sette til side streng i favør av hva stedet?

106
00:05:55,000 --> 00:05:57,000
[Studenter] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, som har vært en char * all denne tiden,

108
00:05:59,000 --> 00:06:03,000
men nå har vi ikke trenger å late som det er en faktisk datatype streng.

109
00:06:03,000 --> 00:06:06,000
Snarere har det vært et synonym slags for char *,

110
00:06:06,000 --> 00:06:09,000
og en streng er en sekvens av tegn,

111
00:06:09,000 --> 00:06:14,000
så hvorfor gjør det fornuftig å representere strenger som char * s?

112
00:06:14,000 --> 00:06:20,000
Hva representerer en char * i sammenheng med dette konseptet av en streng?

113
00:06:20,000 --> 00:06:23,000
Ja. >> [Student] Det første tegnet.

114
00:06:23,000 --> 00:06:25,000
Bra, det første tegnet, men ikke helt det første tegnet.

115
00:06:25,000 --> 00:06:27,000
Det er de-[Studenter] Adresse.

116
00:06:27,000 --> 00:06:29,000
Bra, adressen til den første tegnet.

117
00:06:29,000 --> 00:06:33,000
Alt som er nødvendig for å representere en streng i datamaskinens minne

118
00:06:33,000 --> 00:06:36,000
er bare den unike adressen sin aller første byte.

119
00:06:36,000 --> 00:06:38,000
Du trenger ikke engang å vite hvor lenge det er

120
00:06:38,000 --> 00:06:42,000
fordi hvordan kan du finne det ut dynamisk?

121
00:06:42,000 --> 00:06:44,000
[Student] String lengde.

122
00:06:44,000 --> 00:06:48,000
Du kan ringe hyssinglengde, utmerket, men hvordan streng lengde arbeid?

123
00:06:48,000 --> 00:06:50,000
Hva gjør den? Ja.

124
00:06:50,000 --> 00:06:52,000
[Student] Fortsett til du får null karakter.

125
00:06:52,000 --> 00:06:54,000
Ja, akkurat, gjentar det bare med en for løkke, mens loop,

126
00:06:54,000 --> 00:06:57,000
uansett fra * til slutten, og slutten er representert

127
00:06:57,000 --> 00:07:01,000
av \ 0, den såkalte nul karakter, nul,

128
00:07:01,000 --> 00:07:05,000
ikke å forveksles med null, som er en peker,

129
00:07:05,000 --> 00:07:07,000
som vil komme opp i samtalen igjen i dag.

130
00:07:07,000 --> 00:07:11,000
>> Vi skrelles tilbake et lag av GetInt, og vi tok en titt på GetString,

131
00:07:11,000 --> 00:07:14,000
og huske at begge disse funksjonene, eller egentlig,

132
00:07:14,000 --> 00:07:18,000
GetString, var å bruke en bestemt funksjon

133
00:07:18,000 --> 00:07:21,000
å faktisk analysere, er at, lese eller analysere, brukerens input.

134
00:07:21,000 --> 00:07:25,000
Og hva var det ny funksjon?

135
00:07:25,000 --> 00:07:27,000
Scanf eller sscanf. Den kommer faktisk i et par forskjellige smaker.

136
00:07:27,000 --> 00:07:31,000
Det er scanf, det er sscanf, det er fscanf.

137
00:07:31,000 --> 00:07:35,000
For nå, men la oss fokusere på den ene lettest illustrert,

138
00:07:35,000 --> 00:07:38,000
og la meg gå videre og åpne opp i apparatet

139
00:07:38,000 --> 00:07:41,000
en fil som dette, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Dette er en super enkelt program,

141
00:07:43,000 --> 00:07:46,000
men som gjør noe som vi aldri har gjort

142
00:07:46,000 --> 00:07:48,000
uten hjelp av CS50 biblioteket.

143
00:07:48,000 --> 00:07:51,000
Dette får en int fra en bruker. Hvordan virker det?

144
00:07:51,000 --> 00:07:53,000
Vel, i linje 16 der,

145
00:07:53,000 --> 00:07:56,000
legge merke til at vi erklærer en int kalt x, og på dette punktet i historien,

146
00:07:56,000 --> 00:07:58,000
hva er verdien av x?

147
00:07:58,000 --> 00:08:00,000
[Uhørlig student respons]

148
00:08:00,000 --> 00:08:02,000
[David M.] Høyre, hvem vet, noen søppel verdi potensielt, så i 17, vi bare fortelle brukeren

149
00:08:02,000 --> 00:08:06,000
gi meg et nummer, takk, og trinn 18 er der det blir interessant.

150
00:08:06,000 --> 00:08:11,000
Scanf synes å låne en idé fra printf i at den bruker disse formatkoder i anførselstegn.

151
00:08:11,000 --> 00:08:13,000
% D er selvfølgelig et desimaltall.

152
00:08:13,000 --> 00:08:21,000
Men hvorfor jeg passerer og x i stedet for bare x?

153
00:08:21,000 --> 00:08:24,000
Den tidligere er riktig. Ja.

154
00:08:24,000 --> 00:08:26,000
[Uhørlig student respons]

155
00:08:26,000 --> 00:08:31,000
Akkurat, hvis målet med dette programmet, som funksjon GetInt selv,

156
00:08:31,000 --> 00:08:34,000
er å få en int fra brukeren jeg kan passere funksjoner

157
00:08:34,000 --> 00:08:38,000
alle variablene jeg vil, men hvis jeg ikke passere dem ved henvisning

158
00:08:38,000 --> 00:08:41,000
eller ved adresse eller etter pekeren, alle synonymt for dagens formål,

159
00:08:41,000 --> 00:08:46,000
da funksjonen har ingen mulighet til å endre innholdet i den variabelen.

160
00:08:46,000 --> 00:08:49,000
Dette ville passere en kopi akkurat som buggy versjonen av swap

161
00:08:49,000 --> 00:08:51,000
som vi har snakket om et par ganger nå.

162
00:08:51,000 --> 00:08:54,000
>> Men i stedet, ved å gjøre og x, jeg bokstavelig talt passerer i hva?

163
00:08:54,000 --> 00:08:57,000
[Student] Adressen. >> Adressen til x.

164
00:08:57,000 --> 00:09:01,000
Det er som å tegne et kart for funksjonen kalles scanf og sier her,

165
00:09:01,000 --> 00:09:04,000
disse er veibeskrivelse til en del av minnet i datamaskinen

166
00:09:04,000 --> 00:09:07,000
at du kan gå lagre noe heltall i.

167
00:09:07,000 --> 00:09:10,000
For at sscanf å nå gjøre det

168
00:09:10,000 --> 00:09:13,000
hva operatør, er hva stykke syntaks det nødt til å bruke

169
00:09:13,000 --> 00:09:19,000
selv om vi ikke kan se det fordi noen andre skrev denne funksjonen?

170
00:09:19,000 --> 00:09:21,000
Med andre ord - hva er det?

171
00:09:21,000 --> 00:09:23,000
[Student] X lest.

172
00:09:23,000 --> 00:09:27,000
Det kommer til å bli litt lesing, men bare med hensyn til x her.

173
00:09:27,000 --> 00:09:30,000
Hvis scanf blir passert adressen x,

174
00:09:30,000 --> 00:09:35,000
syntaktisk, hva operatøren bundet til å eksistere et sted

175
00:09:35,000 --> 00:09:38,000
innsiden av scanf implementering slik at scanf

176
00:09:38,000 --> 00:09:42,000
kan faktisk skrive en nummer 2 til denne adressen?

177
00:09:42,000 --> 00:09:44,000
Ja, så *.

178
00:09:44,000 --> 00:09:47,000
Husker at den * er vår dereferanse operatør, noe som betyr gå dit.

179
00:09:47,000 --> 00:09:50,000
>> Når du har blitt overlevert en adresse, slik tilfellet er her,

180
00:09:50,000 --> 00:09:53,000
scanf er trolig-hvis vi faktisk sett rundt sin kildekode-

181
00:09:53,000 --> 00:09:59,000
gjør * x eller tilsvarende til å faktisk gå til denne adressen og sette noen verdi der.

182
00:09:59,000 --> 00:10:02,000
Nå, som for hvordan scanf får inndata fra tastatur,

183
00:10:02,000 --> 00:10:04,000
vi vil bølge våre hender ut for i dag.

184
00:10:04,000 --> 00:10:07,000
Bare anta at operativsystemet lar sscanf å snakke

185
00:10:07,000 --> 00:10:11,000
til brukerens tastaturet, men på dette punktet nå i linje 19,

186
00:10:11,000 --> 00:10:14,000
når vi bare skrive ut x, synes det å være tilfelle

187
00:10:14,000 --> 00:10:17,000
at scanf har satt en int i x.

188
00:10:17,000 --> 00:10:19,000
Det er nøyaktig hvordan scanf fungerer, og husker forrige uke

189
00:10:19,000 --> 00:10:25,000
det er akkurat hvordan GetString og GetInt og andre familie av funksjoner

190
00:10:25,000 --> 00:10:28,000
slutt fungerer, om enn med litt variasjon som sscanf,

191
00:10:28,000 --> 00:10:31,000
som betyr skanne en streng i stedet for tastaturet.

192
00:10:31,000 --> 00:10:33,000
Men la oss ta en titt på en liten varians dette.

193
00:10:33,000 --> 00:10:37,000
I scanf2 jeg faktisk skrudd opp.

194
00:10:37,000 --> 00:10:42,000
Hva er galt og jeg vil skjule kommentar som forklarer så mye

195
00:10:42,000 --> 00:10:47,000
hva er galt med dette programmet, versjon 2?

196
00:10:47,000 --> 00:10:55,000
Vær så teknisk som mulig denne gangen.

197
00:10:55,000 --> 00:10:57,000
Det ser ganske bra.

198
00:10:57,000 --> 00:11:03,000
Det er pent innrykket, men-

199
00:11:03,000 --> 00:11:07,000
okay, hva med la oss beskjære det ned til kortere spørsmål?

200
00:11:07,000 --> 00:11:17,000
Linje 16. Hva er linje 16 gjør i presis, men teknisk engelsk?

201
00:11:17,000 --> 00:11:20,000
Får en litt klosset. Ja, Michael.

202
00:11:20,000 --> 00:11:25,000
[Student] Det er peker til den første bokstaven i en streng.

203
00:11:25,000 --> 00:11:27,000
>> Ok, nær. La meg tweak som en liten bit.

204
00:11:27,000 --> 00:11:33,000
Peker til den første bokstaven i en streng, er du erklære en variabel kalt buffer

205
00:11:33,000 --> 00:11:36,000
som vil peke til den første adressen til en streng,

206
00:11:36,000 --> 00:11:39,000
eller rettere sagt, vil det peke mer spesifikt til en røye.

207
00:11:39,000 --> 00:11:42,000
Legg merke til det er faktisk ikke peker noe sted fordi det er ingen oppdrag operatør.

208
00:11:42,000 --> 00:11:46,000
Det er ingen likhetstegn, så alt vi gjør er å fordele variabel kalt buffer.

209
00:11:46,000 --> 00:11:49,000
Det skjer for å være 32 bits fordi det er en peker,

210
00:11:49,000 --> 00:11:52,000
og innholdet av buffer formodentlig slutt

211
00:11:52,000 --> 00:11:57,000
vil inneholde adressen til en røye, men for nå, hva buffer inneholde?

212
00:11:57,000 --> 00:11:59,000
Bare noen falsk, hvem vet, noen søppel verdi,

213
00:11:59,000 --> 00:12:03,000
fordi vi ikke har eksplisitt initialisert den, så vi skal ikke anta noe.

214
00:12:03,000 --> 00:12:06,000
Ok, så nå linje 17 er-hva linje 17 gjøre?

215
00:12:06,000 --> 00:12:08,000
Kanskje som vil varme opp dette.

216
00:12:08,000 --> 00:12:10,000
Det skriver en streng, ikke sant?

217
00:12:10,000 --> 00:12:12,000
Det skriver String please.

218
00:12:12,000 --> 00:12:15,000
>> Linje 18 er slags kjent nå i at vi bare så en variasjon av dette

219
00:12:15,000 --> 00:12:18,000
men med et annet format kode, så i linje 18,

220
00:12:18,000 --> 00:12:23,000
vi forteller scanf her er adressen til en del av minnet.

221
00:12:23,000 --> 00:12:27,000
Jeg vil at du skal ringe i en streng, som underforstått av% s,

222
00:12:27,000 --> 00:12:32,000
men problemet er at vi ikke har gjort et par ting her.

223
00:12:32,000 --> 00:12:35,000
Hva er ett av problemene?

224
00:12:35,000 --> 00:12:38,000
[Student] Det prøver å dereference en nullpeker.

225
00:12:38,000 --> 00:12:41,000
God, null eller bare ellers ukjent pekere.

226
00:12:41,000 --> 00:12:45,000
Du overlate scanf en adresse, men du sa for et øyeblikk siden

227
00:12:45,000 --> 00:12:49,000
at den adressen er noen søppel verdi fordi vi ikke egentlig tilordne den til noe,

228
00:12:49,000 --> 00:12:53,000
og så forteller du scanf effektivt gå sette en streng her,

229
00:12:53,000 --> 00:12:56,000
men vi vet ikke hvor her ennå er,

230
00:12:56,000 --> 00:12:59,000
så vi har faktisk ikke allokert minne for buffer.

231
00:12:59,000 --> 00:13:03,000
Dessuten, hva er du heller ikke selv forteller scanf?

232
00:13:03,000 --> 00:13:06,000
Antar at dette var en del av minnet, og det var ikke en søppel verdi,

233
00:13:06,000 --> 00:13:09,000
men du fortsatt ikke fortelle scanf noe viktig.

234
00:13:09,000 --> 00:13:12,000
[Student] Hvor det faktisk er, tegnet.

235
00:13:12,000 --> 00:13:15,000
-Tegn, så i dette tilfellet, er det greit.

236
00:13:15,000 --> 00:13:18,000
Fordi bufferen er allerede erklært som en peker

237
00:13:18,000 --> 00:13:22,000
med * stykke syntaks, trenger vi ikke å bruke ampersand

238
00:13:22,000 --> 00:13:25,000
fordi det er allerede en adresse, men jeg tror jeg hørte det her.

239
00:13:25,000 --> 00:13:27,000
[Student] Hvor stort er det?

240
00:13:27,000 --> 00:13:29,000
Bra, vi ikke fortelle scanf hvor stor denne bufferen er,

241
00:13:29,000 --> 00:13:32,000
noe som betyr at selv om buffer var en peker,

242
00:13:32,000 --> 00:13:35,000
vi sier scanf, sette en streng her,

243
00:13:35,000 --> 00:13:38,000
men her kan være to bytes, kan det være 10 bytes, kan det være en megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf har ingen anelse, og fordi dette er en del av minnet

245
00:13:41,000 --> 00:13:43,000
formodentlig, det er ikke en streng ennå.

246
00:13:43,000 --> 00:13:48,000
Det er bare en streng når du skriver tegn og et \ 0 til at del av minnet.

247
00:13:48,000 --> 00:13:51,000
Nå er det bare noen del av minnet.

248
00:13:51,000 --> 00:13:55,000
Scanf vil ikke vite når du skal slutte å skrive til denne adressen.

249
00:13:55,000 --> 00:13:59,000
>> Hvis du husker noen eksempler i det siste hvor jeg tilfeldig skrevet på tastaturet

250
00:13:59,000 --> 00:14:03,000
prøver å overflow en buffer, og vi snakket på fredag ​​om akkurat det.

251
00:14:03,000 --> 00:14:07,000
Hvis en motstander injiserer liksom inn i programmet en mye større ord

252
00:14:07,000 --> 00:14:10,000
eller setningsoppbygning så du ventet du kan overkjørt

253
00:14:10,000 --> 00:14:13,000
en del av minne, som kan ha dårlige konsekvenser,

254
00:14:13,000 --> 00:14:15,000
som å ta over hele programmet selv.

255
00:14:15,000 --> 00:14:17,000
Vi trenger å fikse dette liksom.

256
00:14:17,000 --> 00:14:20,000
La meg zoome ut og gå inn versjon 3 av dette programmet.

257
00:14:20,000 --> 00:14:22,000
Det er litt bedre.

258
00:14:22,000 --> 00:14:24,000
I denne versjonen, merke forskjellen.

259
00:14:24,000 --> 00:14:27,000
I linje 16, jeg igjen erklære en variabel kalt buffer,

260
00:14:27,000 --> 00:14:29,000
men hva er det nå?

261
00:14:29,000 --> 00:14:33,000
Det er en rekke av 16 tegn.

262
00:14:33,000 --> 00:14:36,000
Dette er bra fordi dette betyr at jeg nå kan fortelle scanf

263
00:14:36,000 --> 00:14:39,000
her er en faktisk del av minnet.

264
00:14:39,000 --> 00:14:42,000
Du kan nesten tenke på arrays som pekere nå,

265
00:14:42,000 --> 00:14:44,000
selv om de er faktisk ikke tilsvarende.

266
00:14:44,000 --> 00:14:47,000
De vil oppføre seg forskjellig i ulike sammenhenger.

267
00:14:47,000 --> 00:14:50,000
Men det er sikkert slik at bufferen refererer

268
00:14:50,000 --> 00:14:53,000
16 sammenhengende tegn fordi det er hva en matrise er

269
00:14:53,000 --> 00:14:55,000
og har vært i noen uker nå.

270
00:14:55,000 --> 00:14:59,000
>> Her forteller jeg scanf her er en del av minnet.

271
00:14:59,000 --> 00:15:01,000
Denne gangen er det faktisk en del av minnet,

272
00:15:01,000 --> 00:15:07,000
men hvorfor er dette programmet fortsatt utnyttes?

273
00:15:07,000 --> 00:15:11,000
Hva er galt likevel?

274
00:15:11,000 --> 00:15:14,000
Jeg har sagt gi meg 16 bytes, men-

275
00:15:14,000 --> 00:15:16,000
[Student] Hva om de skriver i mer enn 16 år?

276
00:15:16,000 --> 00:15:20,000
Akkurat, hva om brukeren skriver i 17 tegn eller 1700 tegn?

277
00:15:20,000 --> 00:15:23,000
Faktisk, la oss se om vi ikke kan snuble i denne feilen nå.

278
00:15:23,000 --> 00:15:25,000
Det er bedre, men ikke perfekt.

279
00:15:25,000 --> 00:15:28,000
La meg gå videre og kjør make scanf3 å kompilere dette programmet.

280
00:15:28,000 --> 00:15:34,000
La meg kjøre scanf3, String takk: Hei, og vi synes å være i orden.

281
00:15:34,000 --> 00:15:37,000
La meg prøve en litt lengre, hello there.

282
00:15:37,000 --> 00:15:42,000
Ok, la oss gjøre hello there hvordan er du i dag, Enter.

283
00:15:42,000 --> 00:15:54,000
Komme slags heldige her, la oss si hello there hvordan du er.

284
00:15:54,000 --> 00:15:56,000
Pokker.

285
00:15:56,000 --> 00:16:03,000
Ok, så vi hadde flaks. La oss se om vi ikke kan fikse dette.

286
00:16:03,000 --> 00:16:06,000
Nei, det er ikke til å la meg kopiere.

287
00:16:06,000 --> 00:16:09,000
La oss prøve dette igjen.

288
00:16:09,000 --> 00:16:12,000
Greit, stå ved.

289
00:16:12,000 --> 00:16:20,000
Vi får se hvor lenge jeg kan late til å fokusere mens du fremdeles gjør dette.

290
00:16:20,000 --> 00:16:23,000
Pokker. Det er heller hensiktsmessig, faktisk.

291
00:16:23,000 --> 00:16:26,000
Det vi går.

292
00:16:26,000 --> 00:16:30,000
Punktet laget.

293
00:16:30,000 --> 00:16:34,000
>> Dette, pinlig selv om det også er, er det også en av kildene til stor forvirring

294
00:16:34,000 --> 00:16:38,000
når du skriver programmer som har feil fordi de manifesterer seg

295
00:16:38,000 --> 00:16:40,000
bare én gang på en stund noen ganger.

296
00:16:40,000 --> 00:16:43,000
Realiteten er at selv om koden er fullstendig ødelagt,

297
00:16:43,000 --> 00:16:46,000
det kan bare være helt brutt gang på en stund

298
00:16:46,000 --> 00:16:49,000
fordi noen ganger, i hovedsak hva som skjer er operativsystemet tildeler

299
00:16:49,000 --> 00:16:52,000
litt mer minne enn du faktisk trenger uansett grunn,

300
00:16:52,000 --> 00:16:57,000
og slik at ingen andre bruker minnet rett etter at del av 16 tegn,

301
00:16:57,000 --> 00:17:01,000
så hvis du går til 17, 18, 19, uansett, det er ikke en så stor avtale.

302
00:17:01,000 --> 00:17:04,000
Nå, datamaskinen, selv om det ikke krasjer på det tidspunktet,

303
00:17:04,000 --> 00:17:09,000
kan til slutt bruke byte nummer 17 eller 18 eller 19 for noe annet,

304
00:17:09,000 --> 00:17:14,000
noe som medførte dine data som du setter der, om enn svært lange,

305
00:17:14,000 --> 00:17:18,000
kommer til å bli overskrevet potensielt av en annen funksjon.

306
00:17:18,000 --> 00:17:21,000
Det er ikke nødvendigvis kommer til å forbli intakt,

307
00:17:21,000 --> 00:17:23,000
men det vil ikke nødvendigvis føre til en SEG feil.

308
00:17:23,000 --> 00:17:26,000
Men i dette tilfellet, jeg endelig gitt nok tegn

309
00:17:26,000 --> 00:17:29,000
at jeg egentlig overskredet min del av minnet, og bam,

310
00:17:29,000 --> 00:17:33,000
operativsystemet sa: "Beklager, det er ikke bra, segmentering feil."

311
00:17:33,000 --> 00:17:38,000
>> Og la oss se nå om det fortsatt her i min katalog-

312
00:17:38,000 --> 00:17:40,000
merker at jeg har denne filen her, kjerne.

313
00:17:40,000 --> 00:17:42,000
Legg merke til at dette er igjen kalt en kjerne dump.

314
00:17:42,000 --> 00:17:46,000
Det er egentlig en fil som inneholder innholdet i programmet minne

315
00:17:46,000 --> 00:17:48,000
på det punktet der det krasjet,

316
00:17:48,000 --> 00:17:51,000
og bare for å prøve et lite eksempel her la meg gå inn her

317
00:17:51,000 --> 00:17:57,000
og kjøre gdb på scanf3 og deretter angi en tredje argumentet kalles kjernen,

318
00:17:57,000 --> 00:18:01,000
og legge merke til her at hvis jeg liste koden,

319
00:18:01,000 --> 00:18:06,000
vi vil være i stand som vanlig med gdb å begynne å gå gjennom dette programmet,

320
00:18:06,000 --> 00:18:10,000
og jeg kan kjøre den, og så snart jeg hit-som med trinn-kommandoen i gdb-

321
00:18:10,000 --> 00:18:13,000
så snart jeg traff potensielt buggy linje etter å skrive i en stor streng,

322
00:18:13,000 --> 00:18:16,000
Jeg vil være i stand til å faktisk identifisere det her.

323
00:18:16,000 --> 00:18:19,000
Mer om dette, men i snitt i form av kjernen dumper

324
00:18:19,000 --> 00:18:22,000
og lignende, slik at du faktisk kan rote rundt inne i kjernen dump

325
00:18:22,000 --> 00:18:27,000
og se på hvilken linje programmet sviktet deg.

326
00:18:27,000 --> 00:18:32,000
Eventuelle spørsmål deretter på pekere og adresser?

327
00:18:32,000 --> 00:18:36,000
Fordi i dag igjen, vi kommer til å begynne å ta for gitt at disse tingene eksisterer

328
00:18:36,000 --> 00:18:40,000
og vi vet nøyaktig hva de er.

329
00:18:40,000 --> 00:18:42,000
Ja.

330
00:18:42,000 --> 00:18:46,000
>> [Student] Hvordan kommer du ikke trenger å sette en ampersand ved siden av del-

331
00:18:46,000 --> 00:18:48,000
Godt spørsmål.

332
00:18:48,000 --> 00:18:51,000
Hvordan kommer jeg ikke måtte sette en ampersand ved siden av tegn array som jeg gjorde tidligere

333
00:18:51,000 --> 00:18:53,000
med de fleste av våre eksempler?

334
00:18:53,000 --> 00:18:55,000
Det korte svaret er arrays er litt spesiell.

335
00:18:55,000 --> 00:18:59,000
Du kan nesten tenke en buffer som faktisk er en adresse,

336
00:18:59,000 --> 00:19:03,000
og det bare så skjer for å være tilfelle at hakeparentes notasjon

337
00:19:03,000 --> 00:19:06,000
er en praktisk, slik at vi kan gå inn 0 brakett, brakett 1,

338
00:19:06,000 --> 00:19:10,000
2 brakett, uten å måtte bruke * notasjon.

339
00:19:10,000 --> 00:19:13,000
Det er litt av en hvit løgn, fordi arrays og pekere

340
00:19:13,000 --> 00:19:17,000
er faktisk litt annerledes, men de kan ofte, men ikke alltid brukes om hverandre.

341
00:19:17,000 --> 00:19:21,000
Kort sagt, når en funksjon er ventet en peker til en del av minnet,

342
00:19:21,000 --> 00:19:24,000
du kan enten sende det en adresse som ble returnert av malloc,

343
00:19:24,000 --> 00:19:29,000
og vi vil se malloc igjen før lenge, eller du kan sende det navnet på en matrise.

344
00:19:29,000 --> 00:19:32,000
Du trenger ikke å gjøre ampersand med matriser fordi de allerede er

345
00:19:32,000 --> 00:19:34,000
hovedsak liker adresser.

346
00:19:34,000 --> 00:19:36,000
Det er ett unntak.

347
00:19:36,000 --> 00:19:39,000
Klammeparentesene gjør dem spesielle.

348
00:19:39,000 --> 00:19:41,000
>> Kan du sette en ampersand ved siden av buffer?

349
00:19:41,000 --> 00:19:43,000
Ikke i dette tilfellet.

350
00:19:43,000 --> 00:19:46,000
Det ville ikke fungere fordi, igjen, av denne hjørne saken

351
00:19:46,000 --> 00:19:49,000
hvor arrays er ikke helt faktisk adresser.

352
00:19:49,000 --> 00:19:54,000
Men vi vil kanskje komme tilbake til før lenge med andre eksempler.

353
00:19:54,000 --> 00:19:56,000
La oss prøve å løse et problem her.

354
00:19:56,000 --> 00:20:00,000
Vi har en datastruktur som vi har brukt på en stund kjent som en matrise.

355
00:20:00,000 --> 00:20:02,000
Case in point, det er det vi nettopp hadde.

356
00:20:02,000 --> 00:20:04,000
Men arrays har noen oppsider og ulemper.

357
00:20:04,000 --> 00:20:06,000
Arrays er fine hvorfor?

358
00:20:06,000 --> 00:20:11,000
Hva er en ting som du liker til den grad du liker arrays-om arrays?

359
00:20:11,000 --> 00:20:13,000
Hva er praktisk om dem? Hva er attraktiv?

360
00:20:13,000 --> 00:20:18,000
Hvorfor gjorde vi introdusere dem i første omgang?

361
00:20:18,000 --> 00:20:20,000
Ja.

362
00:20:20,000 --> 00:20:27,000
[Student] De kan lagre mye data, og du trenger ikke å bruke en hel ting.

363
00:20:27,000 --> 00:20:29,000
Du kan bruke en del.

364
00:20:29,000 --> 00:20:32,000
Bra, med en rekke du kan lagre mye data,

365
00:20:32,000 --> 00:20:35,000
og du trenger ikke nødvendigvis å bruke alt sammen, slik at du kan overallocate,

366
00:20:35,000 --> 00:20:39,000
som kan være praktisk hvis du ikke vet på forhånd hvor mange av noe du kan forvente.

367
00:20:39,000 --> 00:20:41,000
>> GetString er et perfekt eksempel.

368
00:20:41,000 --> 00:20:44,000
GetString, skrevet av oss, har ingen anelse om hvor mange tegn du kan forvente,

369
00:20:44,000 --> 00:20:48,000
så det faktum at vi kan fordele biter av sammenhengende minne er bra.

370
00:20:48,000 --> 00:20:51,000
Arrays også løse et problem vi så et par uker siden nå

371
00:20:51,000 --> 00:20:54,000
hvor koden begynner å devolve til noe svært dårlig utformet.

372
00:20:54,000 --> 00:20:57,000
Husker at jeg opprettet en student struktur kalt David,

373
00:20:57,000 --> 00:21:00,000
og da det var faktisk et alternativ, skjønt,

374
00:21:00,000 --> 00:21:04,000
til å ha en variabel kalt navn og en annen variabel kalt, tror jeg, huset,

375
00:21:04,000 --> 00:21:08,000
og en annen variabel kalt ID fordi i den historien da jeg ønsket å introdusere noe annet

376
00:21:08,000 --> 00:21:11,000
liker Rob inn i programmet, så da bestemte jeg meg vente et øyeblikk,

377
00:21:11,000 --> 00:21:13,000
Jeg trenger å endre navn på disse variablene.

378
00:21:13,000 --> 00:21:16,000
La oss kalle meg navn1, ID1, House1.

379
00:21:16,000 --> 00:21:20,000
La oss kalle Rob navn2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Men så vent litt, hva om Tommy?

381
00:21:22,000 --> 00:21:24,000
Da hadde vi tre variabler.

382
00:21:24,000 --> 00:21:27,000
Vi introduserte noen andre, fire sett med variabler.

383
00:21:27,000 --> 00:21:30,000
Verden begynte å bli rotete svært raskt,

384
00:21:30,000 --> 00:21:33,000
så vi introduserte structs, og hva som er overbevisende om en struct?

385
00:21:33,000 --> 00:21:39,000
Hva lar en C struct du gjøre?

386
00:21:39,000 --> 00:21:42,000
Det er virkelig pinlig i dag.

387
00:21:42,000 --> 00:21:44,000
Hva? >> [Uhørlig student respons]

388
00:21:44,000 --> 00:21:47,000
Ja, spesielt, kan typedef du opprette en ny datatype,

389
00:21:47,000 --> 00:21:51,000
og struct, struct søkeord, kan du kapsle

390
00:21:51,000 --> 00:21:54,000
konseptuelt knyttet biter av data sammen

391
00:21:54,000 --> 00:21:56,000
og deretter ringe dem noe sånt som en student.

392
00:21:56,000 --> 00:21:58,000
>> Det var bra fordi vi nå kan modellere

393
00:21:58,000 --> 00:22:03,000
mye mer slags begrepsmessig konsekvent begrepet om en student i en variabel

394
00:22:03,000 --> 00:22:07,000
snarere enn å ha en vilkårlig for en streng, en for en ID, og ​​så videre.

395
00:22:07,000 --> 00:22:10,000
Arrays er fint fordi de tillater oss å begynne å rydde opp vår kode.

396
00:22:10,000 --> 00:22:13,000
Men hva er en ulemper nå av en array?

397
00:22:13,000 --> 00:22:15,000
Hva kan du ikke gjøre? Ja.

398
00:22:15,000 --> 00:22:17,000
[Student] Du må vite hvor stort det er.

399
00:22:17,000 --> 00:22:19,000
Du må vite hvor stort det er, så det er litt vondt.

400
00:22:19,000 --> 00:22:21,000
De av dere med tidligere erfaring med programmering vet at i en rekke språk,

401
00:22:21,000 --> 00:22:24,000
som Java, kan du be en del av minnet, spesielt en matrise,

402
00:22:24,000 --> 00:22:28,000
hvor stor du er, med en lengde, eiendom, så å si, og det er veldig praktisk.

403
00:22:28,000 --> 00:22:32,000
I C, kan du ikke engang kalle strlen på en generisk utvalg

404
00:22:32,000 --> 00:22:35,000
fordi strlen, som ordet antyder, er bare for strykere,

405
00:22:35,000 --> 00:22:39,000
og du kan finne ut lengden på en streng på grunn av denne menneskelige konvensjonen

406
00:22:39,000 --> 00:22:43,000
av å ha en \ 0, men en rekke, mer generelt, er bare en del av minnet.

407
00:22:43,000 --> 00:22:46,000
Hvis det er en rekke ints, er det ikke kommer til å være noen spesiell karakter

408
00:22:46,000 --> 00:22:48,000
på slutten venter på deg.

409
00:22:48,000 --> 00:22:50,000
Du må huske lengden på en matrise.

410
00:22:50,000 --> 00:22:54,000
En annen ulemper av en rekke reared hodet i GetString seg selv.

411
00:22:54,000 --> 00:22:59,000
Hva er en annen ulempe i en matrise?

412
00:22:59,000 --> 00:23:01,000
Sir, bare du og meg i dag.

413
00:23:01,000 --> 00:23:04,000
[Uhørlig student respons] >> Det er hva?

414
00:23:04,000 --> 00:23:06,000
Det er erklært på stakken.

415
00:23:06,000 --> 00:23:09,000
Ok, erklærte på stakken. Hvorfor liker du ikke det?

416
00:23:09,000 --> 00:23:13,000
[Student] Fordi det blir gjenbrukt.

417
00:23:13,000 --> 00:23:15,000
Det blir gjenbrukt.

418
00:23:15,000 --> 00:23:18,000
Ok, hvis du bruker en matrise for å allokere minne,

419
00:23:18,000 --> 00:23:21,000
du kan ikke for eksempel returnere det fordi det er på stakken.

420
00:23:21,000 --> 00:23:23,000
Ok, det er en ulempe.

421
00:23:23,000 --> 00:23:25,000
Og hva med en annen med en rekke?

422
00:23:25,000 --> 00:23:28,000
Når du tildeler det, er du slags skrudd hvis du trenger mer plass

423
00:23:28,000 --> 00:23:30,000
enn denne matrisen har.

424
00:23:30,000 --> 00:23:34,000
>> Da vi introduserte, tilbakekalling, malloc, som ga oss muligheten til å dynamisk allokere minne.

425
00:23:34,000 --> 00:23:37,000
Men hva om vi prøvde en annen verden helt?

426
00:23:37,000 --> 00:23:40,000
Hva hvis vi ønsket å løse et par av disse problemene

427
00:23:40,000 --> 00:23:45,000
så vi i stedet-min penn har sovnet her-

428
00:23:45,000 --> 00:23:51,000
hva om vi i stedet ønsket å hovedsak skape en verden som ikke lenger som dette?

429
00:23:51,000 --> 00:23:56,000
Dette er en matrise, og, selvfølgelig, forringes denne typen når vi treffer enden av matrisen,

430
00:23:56,000 --> 00:24:00,000
og jeg nå ikke lenger har plass til et annet heltall eller en annen karakter.

431
00:24:00,000 --> 00:24:03,000
Hva om vi liksom preemptively si vel, hvorfor ikke vi slappe

432
00:24:03,000 --> 00:24:07,000
dette kravet at alle disse biter av minnet være sammenhengende rygg mot rygg,

433
00:24:07,000 --> 00:24:10,000
og hvorfor ikke, når jeg trenger en int eller røye,

434
00:24:10,000 --> 00:24:12,000
bare gi meg plass til en av dem?

435
00:24:12,000 --> 00:24:14,000
Og når jeg trenger en annen, gi meg en annen plass,

436
00:24:14,000 --> 00:24:16,000
og når jeg trenger en annen, gi meg en annen plass.

437
00:24:16,000 --> 00:24:19,000
Fordelen som er nå at hvis noen andre

438
00:24:19,000 --> 00:24:21,000
tar minnet over her, ikke så farlig.

439
00:24:21,000 --> 00:24:25,000
Jeg tar denne ekstra mengde minne her og deretter denne.

440
00:24:25,000 --> 00:24:28,000
>> Nå er den eneste fangsten her at dette nesten føles som om jeg har

441
00:24:28,000 --> 00:24:30,000
en hel haug med forskjellige variabler.

442
00:24:30,000 --> 00:24:33,000
Dette føles som fem ulike variabler potensielt.

443
00:24:33,000 --> 00:24:36,000
Men hva om vi stjele en idé fra strenger

444
00:24:36,000 --> 00:24:41,000
hvor vi liksom koble disse tingene sammen konseptuelt, og hva om jeg gjorde dette?

445
00:24:41,000 --> 00:24:44,000
Dette er min aller dårlig tegnet pilen.

446
00:24:44,000 --> 00:24:46,000
Men anta at hver av disse biter av minne

447
00:24:46,000 --> 00:24:52,000
pekte til den andre, og denne fyren, som ikke har noen søsken til sin rett,

448
00:24:52,000 --> 00:24:54,000
har ingen slik pil.

449
00:24:54,000 --> 00:24:56,000
Dette er faktisk det som kalles en lenket liste.

450
00:24:56,000 --> 00:25:00,000
Dette er en ny datastruktur som tillater oss å fordele en del av minnet,

451
00:25:00,000 --> 00:25:03,000
deretter en annen, og deretter en annen, og deretter en annen, helst vi ønsker

452
00:25:03,000 --> 00:25:07,000
løpet av et program, og vi husker at de er alle en eller annen måte relatert

453
00:25:07,000 --> 00:25:11,000
ved bokstavelig talt chaining dem sammen, og vi gjorde det billedlig her med en pil.

454
00:25:11,000 --> 00:25:15,000
Men i koden, hva ville være den mekanismen via hvor du kunne liksom koble til,

455
00:25:15,000 --> 00:25:20,000
nesten som Scratch, en del til en annen del?

456
00:25:20,000 --> 00:25:22,000
Vi kunne bruke en peker, ikke sant?

457
00:25:22,000 --> 00:25:25,000
Fordi virkelig pilen som kommer fra øvre venstre torget,

458
00:25:25,000 --> 00:25:31,000
denne fyren her til denne, kan inneholde innsiden av denne plassen

459
00:25:31,000 --> 00:25:34,000
ikke bare noen ints, ikke bare noen røye, men hva hvis jeg faktisk tildelt

460
00:25:34,000 --> 00:25:37,000
litt ekstra plass slik at nå,

461
00:25:37,000 --> 00:25:41,000
hver av mine biter av minnet, selv om dette kommer til å koste meg,

462
00:25:41,000 --> 00:25:45,000
nå ser litt mer rektangulær hvor ett av biter av minne

463
00:25:45,000 --> 00:25:47,000
brukes for en rekke, som nummer 1,

464
00:25:47,000 --> 00:25:50,000
og hvis denne fyren lagrer nummer 2,

465
00:25:50,000 --> 00:25:52,000
denne andre del av minnet brukes til en pil,

466
00:25:52,000 --> 00:25:54,000
eller mer konkret, en peker.

467
00:25:54,000 --> 00:25:59,000
Og jeg antar lagre nummeret 3 over her mens jeg bruke dette til å peke på den fyren,

468
00:25:59,000 --> 00:26:02,000
og nå denne fyren, la oss anta jeg vil bare tre slike mengder minne.

469
00:26:02,000 --> 00:26:05,000
Jeg vil trekke en linje gjennom det, indikerer null.

470
00:26:05,000 --> 00:26:07,000
Er det ingen ekstra tegn.

471
00:26:07,000 --> 00:26:10,000
>> Faktisk er dette hvordan vi kan gå om å implementere

472
00:26:10,000 --> 00:26:12,000
noe som kalles en lenket liste.

473
00:26:12,000 --> 00:26:18,000
En lenket liste er en ny datastruktur, og det er et springbrett mot

474
00:26:18,000 --> 00:26:21,000
mye mer avansert datastrukturer som begynner å løse problemer

475
00:26:21,000 --> 00:26:23,000
langs linjene av Facebook-type problemer og Google-type problemer

476
00:26:23,000 --> 00:26:26,000
der du har store datasett, og det ikke lenger skjærer det

477
00:26:26,000 --> 00:26:29,000
til å lagre alt contiguously og bruke noe som lineær søk

478
00:26:29,000 --> 00:26:31,000
eller noe sånt binært søk.

479
00:26:31,000 --> 00:26:33,000
Du vil ha enda bedre kjører ganger.

480
00:26:33,000 --> 00:26:37,000
Faktisk en av de hellige gral vi snakke om senere denne uken eller neste

481
00:26:37,000 --> 00:26:41,000
er en algoritme som kjøretid er konstant.

482
00:26:41,000 --> 00:26:44,000
Med andre ord, tar det alltid den samme mengde av tid uansett

483
00:26:44,000 --> 00:26:47,000
hvor stor inngangen er, og det ville faktisk være overbevisende,

484
00:26:47,000 --> 00:26:49,000
enda mer enn noe logaritmisk.

485
00:26:49,000 --> 00:26:51,000
Hva er dette på skjermen her?

486
00:26:51,000 --> 00:26:55,000
Hver av rektangler er akkurat hva jeg bare trakk hånd.

487
00:26:55,000 --> 00:26:59,000
Men ting helt til venstre er en spesiell variabel.

488
00:26:59,000 --> 00:27:02,000
Det kommer til å være et enkelt peker fordi den ene fikser

489
00:27:02,000 --> 00:27:04,000
med en lenket liste, da disse tingene er kalt,

490
00:27:04,000 --> 00:27:09,000
er at du må henge på den ene enden av lenket liste.

491
00:27:09,000 --> 00:27:13,000
>> Akkurat som med en streng, må du vite adressen til den første røye.

492
00:27:13,000 --> 00:27:15,000
Samme avtale for koplede listene.

493
00:27:15,000 --> 00:27:19,000
Du må vite adressen til den første del av minnet

494
00:27:19,000 --> 00:27:25,000
fordi derfra, kan du nå alle andre.

495
00:27:25,000 --> 00:27:27,000
Ulemper.

496
00:27:27,000 --> 00:27:30,000
Hvilken pris vi betaler for denne allsidigheten av å ha en dynamisk

497
00:27:30,000 --> 00:27:34,000
sizable datastruktur som om vi skulle trenge mer minne, fine,

498
00:27:34,000 --> 00:27:37,000
bare tilordne en mer blings og trekke en peker fra

499
00:27:37,000 --> 00:27:39,000
den gamle til den nye halen av listen?

500
00:27:39,000 --> 00:27:41,000
Ja.

501
00:27:41,000 --> 00:27:43,000
[Student] Det tar omtrent dobbelt så mye plass.

502
00:27:43,000 --> 00:27:45,000
Det tar dobbelt så mye plass, så det er definitivt en ulemper, og vi har sett dette

503
00:27:45,000 --> 00:27:48,000
tradeoff før mellom tid og rom og fleksibilitet

504
00:27:48,000 --> 00:27:51,000
hvor nå, trenger vi ikke 32 bits for hver av disse tallene.

505
00:27:51,000 --> 00:27:57,000
Vi trenger virkelig 64, 32 for antall og 32 for pekeren.

506
00:27:57,000 --> 00:27:59,000
Men hei, jeg har 2 gigabyte RAM.

507
00:27:59,000 --> 00:28:02,000
Legge til en annen 32 biter her og her synes ikke så stor av en avtale.

508
00:28:02,000 --> 00:28:05,000
Men for store datasett, legger det definitivt opp til bokstavelig talt dobbelt så mye.

509
00:28:05,000 --> 00:28:09,000
Hva er en annen ulempe nå, eller hva funksjonen gir vi opp,

510
00:28:09,000 --> 00:28:12,000
hvis vi representerer lister over ting med en lenket liste og ikke en array?

511
00:28:12,000 --> 00:28:14,000
[Student] Du kan ikke krysse den bakover.

512
00:28:14,000 --> 00:28:16,000
Du kan ikke krysse den bakover, slik at du er typen skrudd hvis du vandre

513
00:28:16,000 --> 00:28:19,000
fra venstre til høyre ved hjelp av en for løkke eller en stund loop

514
00:28:19,000 --> 00:28:21,000
og du skjønner, "Å, jeg ønsker å gå tilbake til begynnelsen av listen."

515
00:28:21,000 --> 00:28:26,000
Du kan ikke fordi disse pekerne bare gå fra venstre til høyre som pilene viser.

516
00:28:26,000 --> 00:28:29,000
>> Nå kan du huske starten av listen med en annen variabel,

517
00:28:29,000 --> 00:28:31,000
men det er en kompleksitet å huske på.

518
00:28:31,000 --> 00:28:35,000
En matrise, uansett hvor langt du går, kan du alltid gjøre minus, minus, minus, minus

519
00:28:35,000 --> 00:28:37,000
og gå tilbake hvor dere kom fra.

520
00:28:37,000 --> 00:28:40,000
Hva er en annen ulempe her? Ja.

521
00:28:40,000 --> 00:28:43,000
[Uhørlig student spørsmål]

522
00:28:43,000 --> 00:28:47,000
Du kan, slik at du har faktisk bare foreslått en datastruktur som kalles en dobbelt lenket liste,

523
00:28:47,000 --> 00:28:50,000
og ja, ville du legge til en annen pekeren til hver av disse rektangler

524
00:28:50,000 --> 00:28:53,000
som går den andre retningen, oppsiden hvorav

525
00:28:53,000 --> 00:28:55,000
er nå kan du krysse fram og tilbake,

526
00:28:55,000 --> 00:28:59,000
nedsiden av som nå du bruker tre ganger så mye minne som vi pleide å

527
00:28:59,000 --> 00:29:04,000
og også legge kompleksitet i form av koden må du skrive for å få det riktig.

528
00:29:04,000 --> 00:29:08,000
Men disse er alle kanskje svært rimelige avveininger, dersom reverseringen er viktigere.

529
00:29:08,000 --> 00:29:10,000
Ja.

530
00:29:10,000 --> 00:29:12,000
[Student] Du kan heller ikke ha en 2D lenket liste.

531
00:29:12,000 --> 00:29:16,000
Bra, kan du egentlig ikke har en 2D lenket liste.

532
00:29:16,000 --> 00:29:18,000
Du kunne. Det er ikke på langt nær så lett som en matrise.

533
00:29:18,000 --> 00:29:21,000
Som en matrise, gjør du åpen brakett, lukket brakett, åpen brakett, lukket brakett,

534
00:29:21,000 --> 00:29:23,000
og du får noen 2-dimensjonal struktur.

535
00:29:23,000 --> 00:29:26,000
Du kan gjennomføre en 2-dimensjonal lenket liste

536
00:29:26,000 --> 00:29:29,000
hvis du gjør tillegget som du foreslo-tredjedeler peker til hver av disse tingene,

537
00:29:29,000 --> 00:29:34,000
og hvis du tenker på en annen liste som kommer mot deg 3D-stil

538
00:29:34,000 --> 00:29:40,000
fra skjermen for oss alle, som er bare en annen kjede av noe slag.

539
00:29:40,000 --> 00:29:45,000
Vi kunne gjøre det, men det er ikke så enkelt som å skrive åpen brakett, hakeparentes. Ja.

540
00:29:45,000 --> 00:29:48,000
[Uhørlig student spørsmål]

541
00:29:48,000 --> 00:29:50,000
Bra, så dette er en virkelig kicker.

542
00:29:50,000 --> 00:29:54,000
>> Disse algoritmene som vi har pined over, som oh, binær søk,

543
00:29:54,000 --> 00:29:57,000
du kan søke en rekke tall på bordet

544
00:29:57,000 --> 00:30:01,000
eller en telefonbok så mye raskere hvis du bruker splitt og hersk

545
00:30:01,000 --> 00:30:05,000
og et binært søk algoritmen, men binære søk kreves to forutsetninger.

546
00:30:05,000 --> 00:30:09,000
En, at dataene ble sortert.

547
00:30:09,000 --> 00:30:11,000
Nå kan vi antagelig holde dette sortert,

548
00:30:11,000 --> 00:30:14,000
så kanskje det er ikke en bekymring, men binære søk også antatt

549
00:30:14,000 --> 00:30:18,000
at du hadde direkte tilgang til listen over numre,

550
00:30:18,000 --> 00:30:21,000
og en rekke lar deg ha direkte tilgang, og ved direkte tilgang,

551
00:30:21,000 --> 00:30:24,000
Jeg mener hvis du får en rekke, hvor mye tid det tar deg

552
00:30:24,000 --> 00:30:26,000
å komme til braketten 0?

553
00:30:26,000 --> 00:30:29,000
En operasjon, du bare bruke [0] og du har rett der.

554
00:30:29,000 --> 00:30:33,000
Hvor mange skritt tar det å komme til plassering 10?

555
00:30:33,000 --> 00:30:36,000
Ett skritt, du bare gå til [10], og du er der.

556
00:30:36,000 --> 00:30:40,000
Derimot, hvordan får du til det 10. heltall i en lenket liste?

557
00:30:40,000 --> 00:30:42,000
Du må starte på begynnelsen fordi du bare huske

558
00:30:42,000 --> 00:30:45,000
begynnelsen på en lenket liste, akkurat som en streng blir husket

559
00:30:45,000 --> 00:30:48,000
av adressen sin første røye, til og finner ut at 10nde int

560
00:30:48,000 --> 00:30:53,000
eller at 10nde tegnet i en streng, må du søke på hele greia.

561
00:30:53,000 --> 00:30:55,000
>> Igjen, vi ikke løse alle våre problemer.

562
00:30:55,000 --> 00:31:00,000
Vi introduserer nye, men det er egentlig avhengig av hva du prøver å designe for.

563
00:31:00,000 --> 00:31:04,000
I form av å implementere dette, kan vi låne en idé fra at studenten struktur.

564
00:31:04,000 --> 00:31:07,000
Syntaksen er svært lik, bortsett fra nå, er ideen litt mer abstrakt

565
00:31:07,000 --> 00:31:09,000
enn hus og navn og ID.

566
00:31:09,000 --> 00:31:13,000
Men jeg foreslår at vi kunne ha en datastruktur i C

567
00:31:13,000 --> 00:31:17,000
som kalles node, som det siste ordet på lysbildet antyder,

568
00:31:17,000 --> 00:31:21,000
innsiden av en node, og en node er bare en generisk container i informatikk.

569
00:31:21,000 --> 00:31:25,000
Det er vanligvis tegnet som en sirkel eller et kvadrat eller rektangel som vi har gjort.

570
00:31:25,000 --> 00:31:27,000
Og i denne datastrukturen, har vi en int, n,

571
00:31:27,000 --> 00:31:29,000
så det er nummeret jeg ønsker å lagre.

572
00:31:29,000 --> 00:31:36,000
Men hva er dette andre linjen, struct node * neste?

573
00:31:36,000 --> 00:31:40,000
Hvorfor er dette riktig, eller hvilken rolle denne tingen spille,

574
00:31:40,000 --> 00:31:42,000
selv om det er litt kryptisk ved første øyekast?

575
00:31:42,000 --> 00:31:44,000
Ja.

576
00:31:44,000 --> 00:31:46,000
[Uhørlig student respons]

577
00:31:46,000 --> 00:31:50,000
Nøyaktig, slik at * slags krigsbytte at det er en peker av noe slag.

578
00:31:50,000 --> 00:31:53,000
Navnet på denne pekeren er vilkårlig neste,

579
00:31:53,000 --> 00:32:00,000
men vi kunne ha kalt det noe vi ønsker, men hva gjør denne pekeren peker på?

580
00:32:00,000 --> 00:32:03,000
[Student] En annen node. >> Akkurat, det peker til en annen slik node.

581
00:32:03,000 --> 00:32:05,000
>> Nå er denne typen av en kuriositet av C.

582
00:32:05,000 --> 00:32:09,000
Husker at C blir lest av en kompilator topp til bunn, fra venstre mot høyre,

583
00:32:09,000 --> 00:32:13,000
som betyr at hvis-dette er litt forskjellig fra hva vi gjorde med studenten.

584
00:32:13,000 --> 00:32:16,000
Når vi definert en student, vi faktisk ikke sette et ord der.

585
00:32:16,000 --> 00:32:18,000
Det sa typedef.

586
00:32:18,000 --> 00:32:20,000
Da vi hadde int id, string navn, string hus,

587
00:32:20,000 --> 00:32:23,000
og deretter student nederst struct.

588
00:32:23,000 --> 00:32:26,000
Denne erklæringen er litt annerledes fordi,

589
00:32:26,000 --> 00:32:28,000
igjen, er C-kompilator litt dum.

590
00:32:28,000 --> 00:32:30,000
Det er bare kommer til å lese topp til bunn,

591
00:32:30,000 --> 00:32:33,000
så hvis den når andre linje her

592
00:32:33,000 --> 00:32:37,000
hvor neste er erklært og det ser, oh, her er en variabel kalt neste.

593
00:32:37,000 --> 00:32:39,000
Det er en peker til en struct node.

594
00:32:39,000 --> 00:32:42,000
Kompilatoren kommer til å innse hva som er en struct node?

595
00:32:42,000 --> 00:32:44,000
Jeg har aldri hørt om denne tingen før,

596
00:32:44,000 --> 00:32:47,000
fordi ordet node ellers kanskje ikke ville synes

597
00:32:47,000 --> 00:32:49,000
til bunnen, så det er dette redundans.

598
00:32:49,000 --> 00:32:53,000
Du har å si struct node her, som du deretter kan forkorte senere

599
00:32:53,000 --> 00:32:56,000
takket være typedef her nede, men dette er fordi

600
00:32:56,000 --> 00:33:02,000
vi refererer selve strukturen innsiden av strukturen.

601
00:33:02,000 --> 00:33:05,000
Det er den fikser det.

602
00:33:05,000 --> 00:33:07,000
>> Noen interessante problemstillinger kommer til å oppstå.

603
00:33:07,000 --> 00:33:09,000
Vi har en liste med tall. Hvordan setter vi inn i det?

604
00:33:09,000 --> 00:33:11,000
Hvordan søker vi det? Hvordan sletter vi av det?

605
00:33:11,000 --> 00:33:13,000
Spesielt nå som vi har til å administrere alle disse pekerne.

606
00:33:13,000 --> 00:33:15,000
Du trodde pekere var liksom mind-bending

607
00:33:15,000 --> 00:33:17,000
når du hadde en av dem prøver bare å lese en int til det.

608
00:33:17,000 --> 00:33:20,000
Nå må vi manipulere en hel liste er verdt.

609
00:33:20,000 --> 00:33:22,000
Hvorfor ikke vi ta vår 5-minutters pause her, og så får vi ta

610
00:33:22,000 --> 00:33:34,000
noen folk opp på scenen for å gjøre akkurat det.

611
00:33:34,000 --> 00:33:36,000
>> C er mye mer moro når det er handlet ut.

612
00:33:36,000 --> 00:33:39,000
Hvem ville bokstavelig talt liker å være først?

613
00:33:39,000 --> 00:33:41,000
Ok, kom igjen opp. Du er først.

614
00:33:41,000 --> 00:33:44,000
Hvem ønsker å være 9? Ok, 9.

615
00:33:44,000 --> 00:33:46,000
Hva med 9? 17?

616
00:33:46,000 --> 00:33:51,000
En liten klikken her. 22 og 26 i den første rad.

617
00:33:51,000 --> 00:33:53,000
Og deretter hvordan om noen der å peke på.

618
00:33:53,000 --> 00:33:57,000
Du er 34. Ok, 34, kom igjen opp.

619
00:33:57,000 --> 00:33:59,000
Først er der borte. Ok, alle fire av dere.

620
00:33:59,000 --> 00:34:01,000
Og hvem sa vi for 9?

621
00:34:01,000 --> 00:34:04,000
Hvem er våre 9?

622
00:34:04,000 --> 00:34:07,000
Hvem ønsker egentlig å være 9? Greit, kom igjen, være 9.

623
00:34:07,000 --> 00:34:10,000
Here we go.

624
00:34:10,000 --> 00:34:13,000
34, vil vi møte deg der borte.

625
00:34:13,000 --> 00:34:17,000
Den første delen er å gjøre dere se slik ut.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, god.

627
00:34:21,000 --> 00:34:25,000
Hvis du kan stå ut til siden, fordi vi kommer til å malloc et øyeblikk.

628
00:34:25,000 --> 00:34:29,000
>> Bra, bra.

629
00:34:29,000 --> 00:34:32,000
Ok, utmerket, så la oss spørre et par spørsmål her.

630
00:34:32,000 --> 00:34:34,000
Og faktisk, hva heter du? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, okay, kom over her.

632
00:34:37,000 --> 00:34:41,000
Anita kommer til å hjelpe oss med å sortere av løse et ganske enkelt spørsmål i første,

633
00:34:41,000 --> 00:34:44,000
som er hvordan finner du hvorvidt en verdi i listen?

634
00:34:44,000 --> 00:34:48,000
Nå merke til at første, her representert ved Lucas,

635
00:34:48,000 --> 00:34:52,000
er litt annerledes, og så hans stykke papir er bevisst sidelengs

636
00:34:52,000 --> 00:34:55,000
fordi det er ikke fullt så høy og tar ikke opp så mange biter,

637
00:34:55,000 --> 00:34:58,000
selv om teknisk han har samme størrelse på papiret bare rotert.

638
00:34:58,000 --> 00:35:01,000
Men han er litt annerledes ved at han er bare 32 bits for en peker,

639
00:35:01,000 --> 00:35:05,000
og alle disse gutta er 64 bits, hvorav halvparten er antall, hvorav halvparten er en peker.

640
00:35:05,000 --> 00:35:08,000
Men pekeren ikke er avbildet, så hvis dere kunne noe klønete

641
00:35:08,000 --> 00:35:12,000
bruke venstre hånd til å peke på den personen ved siden av deg.

642
00:35:12,000 --> 00:35:14,000
Og du er nummer 34. Hva heter du?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, så egentlig, holder papiret i høyre hånd, og venstre hånd går rett ned.

645
00:35:19,000 --> 00:35:21,000
Du representerer null til venstre.

646
00:35:21,000 --> 00:35:24,000
>> Nå er vår menneskelige bildet er veldig konsekvent.

647
00:35:24,000 --> 00:35:26,000
Dette er faktisk hvordan pekere fungerer.

648
00:35:26,000 --> 00:35:29,000
Og hvis du kan knuse litt på denne måten, så jeg er ikke i veien.

649
00:35:29,000 --> 00:35:34,000
Anita her finner meg nummer 22,

650
00:35:34,000 --> 00:35:40,000
men antar en begrensning av ikke mennesker holder opp biter av papir,

651
00:35:40,000 --> 00:35:43,000
men dette er en liste, og du bare har Lucas til å begynne med

652
00:35:43,000 --> 00:35:46,000
fordi han er bokstavelig talt den første pekeren.

653
00:35:46,000 --> 00:35:51,000
Tenk deg at du er deg selv en peker, og slik at du også har muligheten til å peke på noe.

654
00:35:51,000 --> 00:35:56,000
Hvorfor ikke begynne med å peke på nøyaktig hva Lucas peker på?

655
00:35:56,000 --> 00:35:58,000
Bra, og la meg vedta dette ut over her.

656
00:35:58,000 --> 00:36:04,000
Bare for moro skyld diskusjonen, la meg trekke opp en blank side her.

657
00:36:04,000 --> 00:36:06,000
Hvordan staver du navnet ditt? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Ok, Anita.

659
00:36:08,000 --> 00:36:18,000
La oss si node * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Vel, vi burde ikke kalle deg lucas. Vi burde ringe deg først.

661
00:36:22,000 --> 00:36:25,000
Hvorfor er dette faktisk forenlig med virkeligheten her?

662
00:36:25,000 --> 00:36:27,000
En, først eksisterer allerede.

663
00:36:27,000 --> 00:36:30,000
Først har fått tildelt antagelig et sted her oppe.

664
00:36:30,000 --> 00:36:35,000
Node * først, og det er blitt tildelt en liste eller annen måte.

665
00:36:35,000 --> 00:36:37,000
Jeg vet ikke hvordan det skjedde. Det skjedde før klassen startet.

666
00:36:37,000 --> 00:36:40,000
Dette lenket liste av mennesker har blitt opprettet.

667
00:36:40,000 --> 00:36:44,000
Og nå på dette punktet i historien-dette er alt som skjer Facebook tilsynelatende senere-

668
00:36:44,000 --> 00:36:49,000
på dette punktet i historien, har Anita blitt initialisert å være lik første,

669
00:36:49,000 --> 00:36:51,000
som ikke betyr at Anita poeng i Lucas.

670
00:36:51,000 --> 00:36:53,000
Snarere peker hun på hva han peker på

671
00:36:53,000 --> 00:36:57,000
fordi den samme adressen som er på innsiden av Lucas 32 biter - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
er nå også inne i Anitas 32 biter - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Nå finne 22. Hvordan vil du gå om du gjør dette?

674
00:37:05,000 --> 00:37:07,000
Hva er det? >> Pek på uansett.

675
00:37:07,000 --> 00:37:11,000
Peke på noe, så gå videre og handle det ut som best du kan her.

676
00:37:11,000 --> 00:37:15,000
Bra, bra, og nå er du peker på-hva er ditt navn med 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, så Ramon holder opp 22.

678
00:37:18,000 --> 00:37:20,000
Du har nå gjort en sjekk.

679
00:37:20,000 --> 00:37:24,000
Har Ramon == 22, og hvis så, for eksempel, kan vi returnere true.

680
00:37:24,000 --> 00:37:26,000
La meg-mens disse gutta står her litt klønete-

681
00:37:26,000 --> 00:37:32,000
la meg gjøre noe raskt som bool finne.

682
00:37:32,000 --> 00:37:37,000
Jeg kommer til å gå foran og si (node ​​* liste, int n).

683
00:37:37,000 --> 00:37:39,000
Jeg kommer straks tilbake med dere. Jeg må bare skrive noe kode.

684
00:37:39,000 --> 00:37:45,000
Og nå skal jeg gå videre og gjøre dette, node * anita = liste.

685
00:37:45,000 --> 00:37:51,000
Og jeg kommer til å gå foran og si mens (anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> Metaforen her blir litt strukket, men mens (anita! = NULL), hva jeg ønsker å gjøre?

687
00:37:57,000 --> 00:38:03,000
Jeg trenger noen måte å referere

688
00:38:03,000 --> 00:38:05,000
heltallet at Anita peker på.

689
00:38:05,000 --> 00:38:08,000
I det siste, da vi hadde strukturer, som en node er,

690
00:38:08,000 --> 00:38:11,000
vi brukte dot notasjon, og vi vil si noe sånt

691
00:38:11,000 --> 00:38:15,000
anita.n, men problemet her er at Anita ikke er en struct per se.

692
00:38:15,000 --> 00:38:17,000
Hva er hun?

693
00:38:17,000 --> 00:38:21,000
Hun er en peker, så egentlig, hvis vi ønsker å bruke denne dot notasjon-

694
00:38:21,000 --> 00:38:23,000
og dette kommer til å se bevisst litt kryptisk-

695
00:38:23,000 --> 00:38:28,000
vi må gjøre noe sånt gå til hva Anita venstre hånd peker på

696
00:38:28,000 --> 00:38:31,000
og deretter få felt kalt n.

697
00:38:31,000 --> 00:38:35,000
Anita er en peker, men hva er * anita?

698
00:38:35,000 --> 00:38:38,000
Hva synes du når du går til hva Anita peker på?

699
00:38:38,000 --> 00:38:42,000
En struct, en node, og en node, tilbakekalling, har et felt som heter n

700
00:38:42,000 --> 00:38:47,000
fordi det har husker, disse to feltene, neste og n,

701
00:38:47,000 --> 00:38:50,000
at vi så et øyeblikk siden her.

702
00:38:50,000 --> 00:38:53,000
>> Å faktisk imitere dette i kode,

703
00:38:53,000 --> 00:39:02,000
vi kunne gjøre dette, og sier at hvis ((* anita). n == n), n som jeg leter etter.

704
00:39:02,000 --> 00:39:04,000
Legg merke til at funksjonen ble vedtatt i antall jeg bryr meg om.

705
00:39:04,000 --> 00:39:10,000
Da kan jeg gå videre og gjøre noe sånt return true.

706
00:39:10,000 --> 00:39:12,000
Annet, hvis det ikke er tilfelle, hva jeg ønsker å gjøre?

707
00:39:12,000 --> 00:39:19,000
Hvordan oversetter jeg å kode hva Anita gjorde det intuitivt ved å vandre gjennom listen?

708
00:39:19,000 --> 00:39:26,000
Hva bør jeg gjøre her oppe for å simulere Anita tar det skrittet til venstre, som steg til venstre?

709
00:39:26,000 --> 00:39:28,000
[Uhørlig student respons] >> Hva er det?

710
00:39:28,000 --> 00:39:30,000
[Uhørlig student respons]

711
00:39:30,000 --> 00:39:34,000
Bra, ikke en dårlig idé, men i det siste, når vi har gjort dette, har vi gjort anita + +

712
00:39:34,000 --> 00:39:37,000
fordi det ville legge til nummer 1 til Anita,

713
00:39:37,000 --> 00:39:40,000
som vanligvis ville peke på den neste personen, som Ramon,

714
00:39:40,000 --> 00:39:44,000
eller personen ved siden av ham, eller ved siden av ham person ned linjen.

715
00:39:44,000 --> 00:39:49,000
Men det er ikke helt bra her fordi det ser denne tingen som i minnet?

716
00:39:49,000 --> 00:39:54,000
Ikke det. Vi må deaktivere det.

717
00:39:54,000 --> 00:40:00,000
Det ser ut som dette i minnet, og selv om jeg har trukket 1 og 2 og 3 nær hverandre,

718
00:40:00,000 --> 00:40:03,000
hvis vi virkelig simulere dette-kan dere, samtidig peker på de samme menneskene,

719
00:40:03,000 --> 00:40:07,000
kan noen av dere ta en tilfeldig skritt tilbake, noen av dere en tilfeldig skritt fremover?

720
00:40:07,000 --> 00:40:10,000
>> Dette rotet er fortsatt en lenket liste,

721
00:40:10,000 --> 00:40:13,000
men disse gutta kan være hvor som helst i minnet,

722
00:40:13,000 --> 00:40:15,000
så anita + + ikke kommer til å jobbe hvorfor?

723
00:40:15,000 --> 00:40:19,000
Hva er på stedet anita + +?

724
00:40:19,000 --> 00:40:21,000
Hvem vet.

725
00:40:21,000 --> 00:40:24,000
Det er en annen verdi som bare så skjer for å være innlagt

726
00:40:24,000 --> 00:40:28,000
blant alle disse nodene ved en tilfeldighet fordi vi ikke bruker en matrise.

727
00:40:28,000 --> 00:40:30,000
Vi tildelt hver av disse nodene individuelt.

728
00:40:30,000 --> 00:40:32,000
Ok, hvis dere kan rydde dere opp igjen.

729
00:40:32,000 --> 00:40:37,000
La meg foreslå at i stedet for anita + +, vi i stedet gjør anita får-

730
00:40:37,000 --> 00:40:42,000
vel, hvorfor ikke vi gå til det Anita peker på, og deretter gjøre. neste?

731
00:40:42,000 --> 00:40:45,000
Med andre ord, vi går til Ramon, som er rangert som nummer 22,

732
00:40:45,000 --> 00:40:51,000
og da. neste er som om Anita skulle kopiere sin venstre hånd peker.

733
00:40:51,000 --> 00:40:54,000
Men hun ville ikke gå lenger enn Ramon fordi vi fant 22.

734
00:40:54,000 --> 00:40:56,000
Men det ville være ideen. Nå, dette er en gud-forferdelig søl.

735
00:40:56,000 --> 00:40:59,000
Ærlig, vil ingen noensinne huske denne syntaksen, og så heldigvis,

736
00:40:59,000 --> 00:41:04,000
det er faktisk litt bevisst-oh, gjorde du faktisk ikke se hva jeg skrev.

737
00:41:04,000 --> 00:41:08,000
Dette ville være mer overbevisende hvis du kunne. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Bak kulissene, ble jeg løse problemet på denne måten.

739
00:41:10,000 --> 00:41:14,000
Anita, for å ta det skrittet til venstre,

740
00:41:14,000 --> 00:41:18,000
først, skal vi gå til den adressen som Anita peker på

741
00:41:18,000 --> 00:41:23,000
og hvor hun vil finne ikke bare n, som vi bare sjekket for sammenligning skyld,

742
00:41:23,000 --> 00:41:25,000
men du vil også finne neste - i dette tilfellet,

743
00:41:25,000 --> 00:41:28,000
Ramons venstre hånd peker til neste node i listen.

744
00:41:28,000 --> 00:41:32,000
Men dette er gud-forferdelig søl som jeg refererte tidligere,

745
00:41:32,000 --> 00:41:34,000
men det viser seg C lar oss forenkle dette.

746
00:41:34,000 --> 00:41:40,000
I stedet for å skrive (* anita), kan vi i stedet bare skrive anita-> n,

747
00:41:40,000 --> 00:41:45,000
og det er akkurat det samme funksjonelt, men det er mye mer intuitivt,

748
00:41:45,000 --> 00:41:48,000
og det er mye mer i samsvar med det bildet som vi har vært å tegne

749
00:41:48,000 --> 00:41:50,000
hele denne tiden ved hjelp av piler.

750
00:41:50,000 --> 00:41:57,000
>> Til slutt, hva vi trenger å gjøre på slutten av dette programmet?

751
00:41:57,000 --> 00:42:00,000
Det er en linje med kode som gjenstår.

752
00:42:00,000 --> 00:42:02,000
Returnere det?

753
00:42:02,000 --> 00:42:05,000
Usant, fordi hvis vi får gjennom hele mens loop

754
00:42:05,000 --> 00:42:10,000
og Anita er faktisk null, betyr at hun gikk helt til slutten av listen

755
00:42:10,000 --> 00:42:12,000
hvor hun pekte på-hva heter du igjen?

756
00:42:12,000 --> 00:42:15,000
Ari. >> Ari venstre hånd, som er null.

757
00:42:15,000 --> 00:42:18,000
Anita er nå null, og jeg skjønner du bare står her awkwardly i limbo

758
00:42:18,000 --> 00:42:21,000
fordi jeg skal ut på en monolog her,

759
00:42:21,000 --> 00:42:23,000
men vi vil involvere deg igjen i løpet av et øyeblikk.

760
00:42:23,000 --> 00:42:27,000
Anita er null på det punktet i historien, så mens loop opphører,

761
00:42:27,000 --> 00:42:30,000
og vi må tilbake false fordi hvis hun fikk hele veien til Ari nullpeker

762
00:42:30,000 --> 00:42:34,000
så var det ingen tall som hun søkte på listen.

763
00:42:34,000 --> 00:42:39,000
Vi kan rydde opp også, men dette er en ganske god gjennomføring og

764
00:42:39,000 --> 00:42:43,000
av en traversering funksjon, en finne funksjon for en lenket liste.

765
00:42:43,000 --> 00:42:48,000
Det er fortsatt lineær søk, men det er ikke så enkelt som + + en peker

766
00:42:48,000 --> 00:42:52,000
eller + + en i variabel fordi nå kan vi ikke gjette

767
00:42:52,000 --> 00:42:54,000
der hver av disse nodene er i minnet.

768
00:42:54,000 --> 00:42:57,000
Vi må bokstavelig talt følge sporet av brødsmuler, eller mer spesifikt,

769
00:42:57,000 --> 00:43:00,000
pekere, for å komme fra en node til en annen.

770
00:43:00,000 --> 00:43:02,000
>> Nå la oss prøve en annen. Anita, vil du komme tilbake hit?

771
00:43:02,000 --> 00:43:06,000
Hvorfor ikke vi gå videre og tildele en annen person fra publikum?

772
00:43:06,000 --> 00:43:08,000
Malloc-hva heter du? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca er malloced fra publikum,

774
00:43:10,000 --> 00:43:13,000
og hun er nå lagrer nummer 55.

775
00:43:13,000 --> 00:43:17,000
Og målet for hånden er nå for Anita å sette

776
00:43:17,000 --> 00:43:22,000
Rebecca i lenket liste her i dens passende sted.

777
00:43:22,000 --> 00:43:24,000
Kom bort hit for et øyeblikk.

778
00:43:24,000 --> 00:43:28,000
Jeg har gjort noe som dette.

779
00:43:28,000 --> 00:43:32,000
Jeg har gjort node *. Og hva heter du igjen?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, ok.

781
00:43:34,000 --> 00:43:41,000
Rebecca får malloc (sizeof (node)).

782
00:43:41,000 --> 00:43:44,000
Akkurat som vi har tildelt ting som studenter og whatnot i det siste,

783
00:43:44,000 --> 00:43:46,000
vi trenger størrelsen på noden, så nå Rebecca

784
00:43:46,000 --> 00:43:49,000
peker på hva?

785
00:43:49,000 --> 00:43:52,000
Rebecca har to felt inne i henne, hvorav ett er 55 år.

786
00:43:52,000 --> 00:43:55,000
La oss gjøre hva, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Men så rebecca-> neste bør-lignende akkurat nå, er hennes hånd slags hvem vet?

788
00:44:00,000 --> 00:44:03,000
Den peker på noen søppel verdi, så hvorfor ikke for godt mål

789
00:44:03,000 --> 00:44:07,000
vi i det minste gjøre dette slik at venstre hånd er nå på hennes side.

790
00:44:07,000 --> 00:44:09,000
Nå Anita, ta det herfra.

791
00:44:09,000 --> 00:44:11,000
Du har Rebecca har blitt tildelt.

792
00:44:11,000 --> 00:44:20,000
Gå videre og finne ut hvor vi bør sette Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bra, veldig bra.

794
00:44:25,000 --> 00:44:28,000
Ok, bra, og nå trenger vi deg til å gi litt av retning,

795
00:44:28,000 --> 00:44:30,000
slik at du har nådd Ari.

796
00:44:30,000 --> 00:44:33,000
Hans venstre hånd er null, men Rebecca tydelig tilhører høyre,

797
00:44:33,000 --> 00:44:36,000
så hvordan har vi å endre dette lenket liste

798
00:44:36,000 --> 00:44:38,000
for å sette Rebecca i riktig sted?

799
00:44:38,000 --> 00:44:42,000
Hvis du kan bokstavelig talt flytte folks venstre hånd rundt etter behov,

800
00:44:42,000 --> 00:44:48,000
vi vil fikse problemet på den måten.

801
00:44:48,000 --> 00:44:52,000
Ok, bra, og i mellomtiden, er Rebecca venstre hånd nå ved hennes side.

802
00:44:52,000 --> 00:44:54,000
>> Det var for enkelt.

803
00:44:54,000 --> 00:44:57,000
La oss prøve tildeling-vi nesten ferdig, 20.

804
00:44:57,000 --> 00:44:59,000
Ok, kom igjen opp.

805
00:44:59,000 --> 00:45:04,000
20 har fått tildelt, så la meg gå videre og si igjen her

806
00:45:04,000 --> 00:45:07,000
Vi har nettopp gjort node * Saad.

807
00:45:07,000 --> 00:45:11,000
Vi har malloc (sizeof (node)).

808
00:45:11,000 --> 00:45:16,000
Vi gjør de samme syntaks som vi gjorde før i 20,

809
00:45:16,000 --> 00:45:20,000
og jeg vil gjøre neste = NULL, og nå er det opp til Anita

810
00:45:20,000 --> 00:45:23,000
å sette deg inn i lenket liste, hvis du kunne spille den samme rollen.

811
00:45:23,000 --> 00:45:30,000
Execute.

812
00:45:30,000 --> 00:45:32,000
Ok, bra.

813
00:45:32,000 --> 00:45:38,000
Nå tenker nøye før du begynner å bevege venstre hånd rundt.

814
00:45:38,000 --> 00:45:46,000
Du langt fått mest pinlige rolle i dag.

815
00:45:46,000 --> 00:45:59,000
Hvis hånd bør flyttes først?

816
00:45:59,000 --> 00:46:02,000
Ok, vent, jeg hører noen ikke-tallet.

817
00:46:02,000 --> 00:46:07,000
Hvis noen folk ville høflig liker å bidra til å løse en vanskelig situasjon her.

818
00:46:07,000 --> 00:46:11,000
Som venstre hånd må oppdateres først kanskje? Ja.

819
00:46:11,000 --> 00:46:13,000
[Student] Saad-tallet.

820
00:46:13,000 --> 00:46:15,000
Ok, Saad-tallet, hvorfor, skjønt?

821
00:46:15,000 --> 00:46:17,000
[Uhørlig student respons]

822
00:46:17,000 --> 00:46:19,000
Bra, fordi hvis vi flytter-hva heter du? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, hvis vi flytter sin hånd først ned til null,

824
00:46:22,000 --> 00:46:25,000
nå har vi bokstavelig talt foreldreløs fire personer i denne listen

825
00:46:25,000 --> 00:46:29,000
fordi han var den eneste som peker på Ramon og alle til venstre,

826
00:46:29,000 --> 00:46:31,000
så oppdaterer at pekeren første var dårlig.

827
00:46:31,000 --> 00:46:33,000
La oss angre det.

828
00:46:33,000 --> 00:46:37,000
God, og nå gå videre og flytte den aktuelle venstre peker på Ramon.

829
00:46:37,000 --> 00:46:39,000
Dette føles litt overflødig.

830
00:46:39,000 --> 00:46:41,000
Nå er det to personer som peker på Ramon, men det er fint

831
00:46:41,000 --> 00:46:43,000
fordi nå hvordan andre oppdaterer vi listen?

832
00:46:43,000 --> 00:46:48,000
Hva derimot må flytte?

833
00:46:48,000 --> 00:46:53,000
Utmerket, nå har vi mistet noen minne?

834
00:46:53,000 --> 00:46:57,000
Nei, så bra, la oss se om vi ikke kan bryte denne gang.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing en siste gang, nummer 5.

836
00:47:00,000 --> 00:47:04,000
Hele veien i ryggen, kom ned.

837
00:47:04,000 --> 00:47:08,000
Det er veldig spennende.

838
00:47:08,000 --> 00:47:15,000
[Applaus]

839
00:47:15,000 --> 00:47:17,000
Hva heter du? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, ok, du malloced som nummer fem.

841
00:47:19,000 --> 00:47:23,000
Vi har nettopp gjennomført kode som er nesten identisk med disse

842
00:47:23,000 --> 00:47:26,000
med bare et annet navn.

843
00:47:26,000 --> 00:47:28,000
Utmerket.

844
00:47:28,000 --> 00:47:38,000
Nå, Anita, lykke sette nummer 5 i listen nå.

845
00:47:38,000 --> 00:47:43,000
God, og?

846
00:47:43,000 --> 00:47:47,000
Utmerket, så dette er virkelig den tredje av tre totalt tilfeller.

847
00:47:47,000 --> 00:47:49,000
Først hadde vi noen på slutten, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Vi hadde noen i midten.

849
00:47:51,000 --> 00:47:53,000
Nå har vi noen i begynnelsen, og i dette eksempelet,

850
00:47:53,000 --> 00:47:56,000
vi nå måtte oppdatere Lucas for første gang

851
00:47:56,000 --> 00:48:00,000
fordi det første element i listen nå har til å peke på en ny node,

852
00:48:00,000 --> 00:48:03,000
som i sin tur peker på node nummer 9.

853
00:48:03,000 --> 00:48:06,000
>> Dette var en enormt vanskelig demonstrasjon, jeg er sikker på,

854
00:48:06,000 --> 00:48:08,000
så en stor applaus for disse gutta hvis du kunne.

855
00:48:08,000 --> 00:48:11,000
Pent gjort.

856
00:48:11,000 --> 00:48:17,000
Det er alt. Du kan holde papirlapper som et lite minne.

857
00:48:17,000 --> 00:48:22,000
Det viser seg at du gjør dette i koden

858
00:48:22,000 --> 00:48:26,000
er ikke fullt så enkelt som bare å flytte hendene rundt

859
00:48:26,000 --> 00:48:28,000
og peker pekere til forskjellige ting.

860
00:48:28,000 --> 00:48:31,000
Men innser at når det gjelder tid til å gjennomføre noe sånt

861
00:48:31,000 --> 00:48:34,000
en lenket liste eller en variant av det hvis du fokuserer på virkelig

862
00:48:34,000 --> 00:48:38,000
disse grunnleggende fundamentale forhold, de bite-size problemer jeg må finne ut,

863
00:48:38,000 --> 00:48:43,000
er det denne hånden eller denne hånden, skjønner at det som ellers er en ganske kompleks program

864
00:48:43,000 --> 00:48:47,000
kan faktisk reduseres til forholdsvis enkle byggesteiner som dette.

865
00:48:47,000 --> 00:48:51,000
>> La oss ta ting i en mer sofistikert retning likevel.

866
00:48:51,000 --> 00:48:53,000
Vi har nå forestillingen om den lenket liste.

867
00:48:53,000 --> 00:48:57,000
Vi har også, takket være forslaget tilbake dit-en dobbelt lenket liste,

868
00:48:57,000 --> 00:49:01,000
som ser nesten det samme, men nå har vi to pekere innsiden av struct

869
00:49:01,000 --> 00:49:05,000
i stedet for én, og vi kunne sannsynligvis kalle disse pekere forrige og neste

870
00:49:05,000 --> 00:49:08,000
eller til venstre eller høyre, men vi gjør det, faktisk, trenger to av dem.

871
00:49:08,000 --> 00:49:10,000
Koden vil være litt mer involvert.

872
00:49:10,000 --> 00:49:12,000
Anita ville ha hatt å gjøre mer arbeid her på scenen.

873
00:49:12,000 --> 00:49:15,000
Men vi kan sikkert gjennomføre den slags struktur.

874
00:49:15,000 --> 00:49:19,000
I form av løpende tid, men hva ville være kjøretiden

875
00:49:19,000 --> 00:49:24,000
for Anita å finne et tall n i en lenket liste nå?

876
00:49:24,000 --> 00:49:27,000
Fortsatt stor O av n, så det er ikke noe bedre enn lineær søk.

877
00:49:27,000 --> 00:49:29,000
Vi kan ikke gjøre binære søk, men, igjen.

878
00:49:29,000 --> 00:49:34,000
Hvorfor var det slik? Du kan ikke hoppe rundt.

879
00:49:34,000 --> 00:49:36,000
Selv om vi selvsagt se alle menneskene på scenen,

880
00:49:36,000 --> 00:49:39,000
og Anita kunne ha eyeballed det og sa: «Her er midt på listen,"

881
00:49:39,000 --> 00:49:42,000
Hun ville ikke vite at hvis hun var dataprogrammet

882
00:49:42,000 --> 00:49:47,000
fordi det eneste hun hadde å klinke til på begynnelsen av scenariet

883
00:49:47,000 --> 00:49:50,000
var Lucas, som var den første pekeren.

884
00:49:50,000 --> 00:49:53,000
Hun ville nødvendigvis må følge disse koblingene,

885
00:49:53,000 --> 00:49:56,000
telle hennes måte før hun fant omtrent på midten,

886
00:49:56,000 --> 00:49:58,000
og selv da, hun kommer ikke til å vite når hun har nådd midten

887
00:49:58,000 --> 00:50:01,000
med mindre hun går hele veien til enden for å finne ut hvor mange det er,

888
00:50:01,000 --> 00:50:05,000
Deretter backtracks, og som også vil være vanskelig med mindre du hadde

889
00:50:05,000 --> 00:50:07,000
en dobbelt lenket liste av noe slag.

890
00:50:07,000 --> 00:50:10,000
>> Løse noen problemer i dag, men å innføre andre.

891
00:50:10,000 --> 00:50:12,000
Hva om en annen datastruktur helt?

892
00:50:12,000 --> 00:50:15,000
Dette er et fotografi av skuffene i Mather House,

893
00:50:15,000 --> 00:50:19,000
og i dette tilfellet har vi en datastruktur vi har også slags allerede blitt snakket om.

894
00:50:19,000 --> 00:50:22,000
Vi snakket om en stabel i sammenheng med minne,

895
00:50:22,000 --> 00:50:26,000
og det er liksom bevisst kalt fordi en stabel i form av minne

896
00:50:26,000 --> 00:50:31,000
er effektivt en datastruktur som har mer og mer ting lagvis oppå den.

897
00:50:31,000 --> 00:50:35,000
Men det interessante ting om en stabel, slik tilfellet er i virkeligheten,

898
00:50:35,000 --> 00:50:38,000
er at det er en spesiell type datastruktur.

899
00:50:38,000 --> 00:50:42,000
Det er en datastruktur hvorved det første elementet i

900
00:50:42,000 --> 00:50:46,000
er det siste elementet ut.

901
00:50:46,000 --> 00:50:50,000
Hvis du er den første skuffen for å bli satt på stakken,

902
00:50:50,000 --> 00:50:53,000
du kommer til å være dessverre den siste skuffen for å bli tatt av stabelen,

903
00:50:53,000 --> 00:50:55,000
og som ikke er nødvendigvis en god ting.

904
00:50:55,000 --> 00:50:58,000
Omvendt kan du tenke på det den andre veien rundt,

905
00:50:58,000 --> 00:51:02,000
den siste i den første ut.

906
00:51:02,000 --> 00:51:05,000
>> Nå, noen scenarier kommer til tankene der har en stabel

907
00:51:05,000 --> 00:51:08,000
datastruktur hvor du har den egenskapen

908
00:51:08,000 --> 00:51:13,000
av sist inn, først ut, er faktisk overbevisende?

909
00:51:13,000 --> 00:51:16,000
Er det en god ting? Er det en dårlig ting?

910
00:51:16,000 --> 00:51:19,000
Det er definitivt en dårlig ting hvis magasinene var ikke alle identiske

911
00:51:19,000 --> 00:51:21,000
og de var alle spesielle forskjellige farger eller whatnot,

912
00:51:21,000 --> 00:51:24,000
og den fargen du ønsker er helt nederst.

913
00:51:24,000 --> 00:51:26,000
Selvfølgelig kan du ikke få det uten store anstrengelser.

914
00:51:26,000 --> 00:51:28,000
Du må starte fra toppen og jobb deg nedover.

915
00:51:28,000 --> 00:51:31,000
Tilsvarende, hva om du var en av disse fan gutter

916
00:51:31,000 --> 00:51:34,000
som venter oppe hele natten prøver å få en iPhone og linjer opp

917
00:51:34,000 --> 00:51:36,000
på et sted som dette?

918
00:51:36,000 --> 00:51:40,000
Ville det ikke vært fint hvis Apple Store

919
00:51:40,000 --> 00:51:42,000
var en stabel datastruktur?

920
00:51:42,000 --> 00:51:44,000
Yay? Nei?

921
00:51:44,000 --> 00:51:47,000
Det er bare bra for folk som dukker opp på den siste mulige øyeblikk

922
00:51:47,000 --> 00:51:50,000
og deretter få revet av køen.

923
00:51:50,000 --> 00:51:52,000
Og faktisk, det faktum at jeg var så tilbøyelig si kø

924
00:51:52,000 --> 00:51:56,000
er faktisk i tråd med det vi vil kalle denne typen data struktur,

925
00:51:56,000 --> 00:51:59,000
en i virkeligheten der rekkefølgen spiller ingen rolle,

926
00:51:59,000 --> 00:52:02,000
og du vil den første i å være den første ut

927
00:52:02,000 --> 00:52:04,000
hvis bare for moro skyld menneskelig rettferdighet.

928
00:52:04,000 --> 00:52:07,000
Vi vil generelt kalle det en kø datastruktur.

929
00:52:07,000 --> 00:52:11,000
>> Det viser seg dessuten knyttet listene, kan vi begynne å bruke de samme grunnleggende ideer

930
00:52:11,000 --> 00:52:15,000
og begynne å lage nye og ulike typer løsninger på problemer.

931
00:52:15,000 --> 00:52:19,000
For eksempel, i tilfelle av en stabel, kan vi representerer en stabel

932
00:52:19,000 --> 00:52:22,000
ved hjelp av en datastruktur som dette, ville jeg foreslå.

933
00:52:22,000 --> 00:52:26,000
I dette tilfellet har jeg erklært en struct, og jeg har sagt innsiden av denne strukturen

934
00:52:26,000 --> 00:52:30,000
er en matrise av tall, og deretter en variabel kalt størrelse,

935
00:52:30,000 --> 00:52:33,000
og jeg kommer til å kalle denne tingen en stabel.

936
00:52:33,000 --> 00:52:35,000
Nå, hvorfor dette faktisk fungerer?

937
00:52:35,000 --> 00:52:43,000
I tilfelle av en stabel, kan jeg trekke dette effektivt på skjermen som en matrise.

938
00:52:43,000 --> 00:52:47,000
Her er mitt stabelen. De er mine tall.

939
00:52:47,000 --> 00:52:50,000
Og vi vil trekke dem som dette, dette, dette, dette, dette.

940
00:52:50,000 --> 00:52:53,000
Og så har jeg noen andre data medlem her,

941
00:52:53,000 --> 00:52:58,000
som kalles størrelse, så dette er størrelsen, og dette er tall,

942
00:52:58,000 --> 00:53:02,000
og kollektivt representerer hele iPad her en stabel struktur.

943
00:53:02,000 --> 00:53:07,000
Nå, som standard, har størrelsen antagelig fått til å være initialisert til 0,

944
00:53:07,000 --> 00:53:11,000
og hva er inni rekken av tall i utgangspunktet

945
00:53:11,000 --> 00:53:14,000
når jeg først tildele en array?

946
00:53:14,000 --> 00:53:16,000
Søppel. Hvem vet? Og det spiller ingen rolle egentlig.

947
00:53:16,000 --> 00:53:20,000
Det spiller ingen rolle om det er 1, 2, 3, 4, 5, helt tilfeldig

948
00:53:20,000 --> 00:53:25,000
av uflaks lagret i strukturen min fordi så lenge jeg vet at størrelsen av stabelen

949
00:53:25,000 --> 00:53:29,000
er 0, så jeg vet programmatisk, ikke se på noen av elementene i matrisen.

950
00:53:29,000 --> 00:53:31,000
Det spiller ingen rolle hva som er der.

951
00:53:31,000 --> 00:53:34,000
Ikke se på dem, som ville være konsekvensen av en slik størrelse fra 0.

952
00:53:34,000 --> 00:53:38,000
>> Men antar nå jeg gå videre og sette noe inn i bunken.

953
00:53:38,000 --> 00:53:42,000
Jeg vil sette inn nummer 5, så jeg satte nummer 5 her,

954
00:53:42,000 --> 00:53:45,000
og hva setter jeg her nede?

955
00:53:45,000 --> 00:53:48,000
Nå vil jeg faktisk sette ned en for størrelsen,

956
00:53:48,000 --> 00:53:50,000
og nå bunken er av størrelse 1.

957
00:53:50,000 --> 00:53:53,000
Hva hvis jeg går videre og sette inn nummeret, la oss si, 7 neste?

958
00:53:53,000 --> 00:53:57,000
Dette blir deretter oppdatert til 2, og så får vi gjøre 9,

959
00:53:57,000 --> 00:54:02,000
og så dette blir oppdatert til 3.

960
00:54:02,000 --> 00:54:05,000
Men det interessante funksjonen nå i denne stabelen er at

961
00:54:05,000 --> 00:54:09,000
Jeg skal fjerne hvilket element hvis jeg ønsker å komme

962
00:54:09,000 --> 00:54:12,000
noe ut av bunken, så å si?

963
00:54:12,000 --> 00:54:14,000
9 ville være den første tingen å gå.

964
00:54:14,000 --> 00:54:18,000
Hvordan skal bildet endres hvis jeg ønsker å komme et element av stabelen,

965
00:54:18,000 --> 00:54:20,000
mye som en skuff i Mather?

966
00:54:20,000 --> 00:54:22,000
Ja. >> [Student] Set størrelse til 2.

967
00:54:22,000 --> 00:54:27,000
Akkurat, er alt jeg gjør satt størrelsen til 2, og hva gjør jeg med array?

968
00:54:27,000 --> 00:54:29,000
Jeg trenger ikke å gjøre noe.

969
00:54:29,000 --> 00:54:32,000
Jeg kunne, bare for å være anal, sette en 0 der eller en -1 eller noe å betegne

970
00:54:32,000 --> 00:54:34,000
at dette ikke er en legit verdi, men det spiller ingen rolle fordi

971
00:54:34,000 --> 00:54:37,000
Jeg kan spille utenfor matrisen selv hvor lenge det er

972
00:54:37,000 --> 00:54:41,000
slik at jeg vet bare se på de to første elementene i denne matrisen.

973
00:54:41,000 --> 00:54:47,000
Nå, hvis jeg går og legger til nummer 8 til denne tabellen, hvordan bildet endres neste?

974
00:54:47,000 --> 00:54:50,000
Dette blir 8, og dette blir 3.

975
00:54:50,000 --> 00:54:52,000
Jeg kutter noen hjørner her.

976
00:54:52,000 --> 00:54:56,000
Nå har vi 5, 7, 8, og er vi tilbake til en størrelse på 3.

977
00:54:56,000 --> 00:54:58,000
Dette er ganske enkelt å implementere,

978
00:54:58,000 --> 00:55:06,000
men når vi kommer til å angre på dette utformingsavgjørelsen?

979
00:55:06,000 --> 00:55:09,000
Når begynner ting du å gå veldig, veldig galt? Ja.

980
00:55:09,000 --> 00:55:11,000
[Uhørlig student respons]

981
00:55:11,000 --> 00:55:13,000
Når du ønsker å gå tilbake og få det første elementet du setter inn

982
00:55:13,000 --> 00:55:18,000
>> Det viser seg her, selv om en stabel er en rekke under panseret,

983
00:55:18,000 --> 00:55:21,000
disse datastrukturer vi har begynt å snakke om er også allment kjent som

984
00:55:21,000 --> 00:55:25,000
abstrakte datastrukturer der hvor de er implementert

985
00:55:25,000 --> 00:55:27,000
er helt foruten poenget.

986
00:55:27,000 --> 00:55:31,000
En datastruktur som en stabel er ment å legge til støtte

987
00:55:31,000 --> 00:55:35,000
operasjoner som push, som presser en skuff på stakken,

988
00:55:35,000 --> 00:55:39,000
og pop, som fjerner et element fra bunken, og det er det.

989
00:55:39,000 --> 00:55:43,000
Hvis du var å laste ned andres kode som allerede iverksatt

990
00:55:43,000 --> 00:55:46,000
dette som kalles en stabel, ville vedkommende har skrevet

991
00:55:46,000 --> 00:55:49,000
bare to funksjoner for deg, trykk og pop, hvis eneste mål i livet

992
00:55:49,000 --> 00:55:51,000
ville være å gjøre akkurat det.

993
00:55:51,000 --> 00:55:54,000
Du eller ham eller henne som gjennomføres det programmet

994
00:55:54,000 --> 00:55:58,000
ville ha vært helt en å bestemme hvordan de skal gjennomføre

995
00:55:58,000 --> 00:56:00,000
semantikk presser og spratt under panseret

996
00:56:00,000 --> 00:56:03,000
eller funksjonaliteten til å skyve og spratt.

997
00:56:03,000 --> 00:56:07,000
Og jeg har gjort en noe kortsiktig avgjørelse her

998
00:56:07,000 --> 00:56:10,000
ved å implementere min stabel med denne enkle datastruktur hvorfor?

999
00:56:10,000 --> 00:56:12,000
Når gjør dette datastruktur pause?

1000
00:56:12,000 --> 00:56:18,000
På hvilket punkt må jeg returnere en feil når brukeren ringer push, for eksempel?

1001
00:56:18,000 --> 00:56:20,000
[Student] Hvis det ikke mer plass.

1002
00:56:20,000 --> 00:56:23,000
Akkurat, hvis det er ikke mer plass, hvis jeg har overskredet kapasitet,

1003
00:56:23,000 --> 00:56:27,000
som er alle caps fordi det antyder at det er en slags global konstant.

1004
00:56:27,000 --> 00:56:30,000
Vel, da er jeg bare nødt til å si: "Beklager, jeg kan ikke presse en annen verdi

1005
00:56:30,000 --> 00:56:32,000
på bunken, "mye som i Mather.

1006
00:56:32,000 --> 00:56:36,000
>> På et tidspunkt, de kommer til å treffe den øverste delen av den lille kabinettet.

1007
00:56:36,000 --> 00:56:39,000
Det er ikke mer plass eller kapasitet i bunken, og da er det noen form for feil.

1008
00:56:39,000 --> 00:56:42,000
De må sette elementet et annet sted, skuffen et annet sted,

1009
00:56:42,000 --> 00:56:44,000
eller ingen steder.

1010
00:56:44,000 --> 00:56:47,000
Nå, med en kø, kunne vi gjennomføre det litt annerledes.

1011
00:56:47,000 --> 00:56:50,000
En kø er litt annerledes ved at under panseret, kan det settes i verk

1012
00:56:50,000 --> 00:56:54,000
som en matrise, men hvorfor, i dette tilfellet, er jeg foreslår

1013
00:56:54,000 --> 00:56:59,000
å også ha et hode element representerer hodet av listen,

1014
00:56:59,000 --> 00:57:06,000
fronten av listen, den første personen i linje på Apple butikken, i tillegg til størrelse?

1015
00:57:06,000 --> 00:57:14,000
Hvorfor trenger jeg en ekstra stykke data her?

1016
00:57:14,000 --> 00:57:16,000
Tenk tilbake til hva tallene er

1017
00:57:16,000 --> 00:57:18,000
hvis jeg har trukket den som følger.

1018
00:57:18,000 --> 00:57:21,000
Antar at dette er nå en kø i stedet for en stabel,

1019
00:57:21,000 --> 00:57:24,000
forskjellen blir, akkurat som Apple Store-køen er rettferdig.

1020
00:57:24,000 --> 00:57:27,000
Den første personen i linje ved starten av listen, nummer 5 i dette tilfellet,

1021
00:57:27,000 --> 00:57:30,000
han eller hun kommer til å bli sluppet inn i butikken først.

1022
00:57:30,000 --> 00:57:32,000
La oss gjøre det.

1023
00:57:32,000 --> 00:57:35,000
Anta at dette er staten køen min på dette tidspunkt, og nå Apple Store

1024
00:57:35,000 --> 00:57:39,000
åpner og den første personen, nummer 5, ledes inn i butikken.

1025
00:57:39,000 --> 00:57:43,000
Hvordan endrer jeg bildet nå som jeg har DE-kø den første personen

1026
00:57:43,000 --> 00:57:47,000
på forsiden av linjen?

1027
00:57:47,000 --> 00:57:50,000
Hva er det? >> [Student] Endre køen.

1028
00:57:50,000 --> 00:57:52,000
Endre hodet, så 5 forsvinner.

1029
00:57:52,000 --> 00:57:56,000
I virkeligheten er det som om-hvordan best å gjøre dette?

1030
00:57:56,000 --> 00:58:00,000
I virkeligheten er det som om denne fyren forsvinner.

1031
00:58:00,000 --> 00:58:03,000
Hva ville nummer 7 gjøre i en faktisk butikk?

1032
00:58:03,000 --> 00:58:05,000
De ville ta et stort skritt fremover.

1033
00:58:05,000 --> 00:58:08,000
>> Men hva har vi kommet til å verdsette når det kommer til arrays

1034
00:58:08,000 --> 00:58:10,000
og flytte ting rundt?

1035
00:58:10,000 --> 00:58:12,000
Det er litt av en sløsing med tid, ikke sant?

1036
00:58:12,000 --> 00:58:16,000
Hvorfor har du å være så anal som å ha den første personen

1037
00:58:16,000 --> 00:58:21,000
ved starten av linjen ved fysisk starten av mengde minne?

1038
00:58:21,000 --> 00:58:23,000
Det er helt unødvendig. Hvorfor?

1039
00:58:23,000 --> 00:58:26,000
Hva kan jeg bare huske stedet? >> [Uhørlig student respons]

1040
00:58:26,000 --> 00:58:30,000
Akkurat, jeg kunne bare huske med denne ekstra data medlem hodet

1041
00:58:30,000 --> 00:58:34,000
som nå leder av listen er ikke lenger 0, som det var for et øyeblikk siden.

1042
00:58:34,000 --> 00:58:39,000
Nå er det faktisk nummer 1. På denne måten får jeg en liten optimalisering.

1043
00:58:39,000 --> 00:58:44,000
Bare fordi jeg har de-kø noen fra linjen ved starten av linjen på Apple Store

1044
00:58:44,000 --> 00:58:47,000
betyr ikke at alle har til å skifte, som tilbakekallingen er en lineær operasjon.

1045
00:58:47,000 --> 00:58:50,000
Jeg kan i stedet bruke konstant tid bare

1046
00:58:50,000 --> 00:58:53,000
og oppnå så mye raskere respons.

1047
00:58:53,000 --> 00:58:56,000
Men prisen jeg betaler er hva du får som ekstra ytelse

1048
00:58:56,000 --> 00:58:58,000
og ikke trenger å skifte alle?

1049
00:58:58,000 --> 00:59:01,000
Ja. >> [Uhørlig student respons]

1050
00:59:01,000 --> 00:59:04,000
Kan legge til flere mennesker, vel, er det problemet ortogonale

1051
00:59:04,000 --> 00:59:07,000
til det faktum at vi ikke er skiftende folk rundt.

1052
00:59:07,000 --> 00:59:11,000
Det er fortsatt en matrise, så om vi flytter alle eller ikke-

1053
00:59:11,000 --> 00:59:13,000
oh, jeg ser hva du mener, ok.

1054
00:59:13,000 --> 00:59:16,000
Egentlig, jeg er enig med det du sier i at det er nesten som om

1055
00:59:16,000 --> 00:59:19,000
Vi overvåker nå aldri kommer til å bruke starten av denne tabellen lenger

1056
00:59:19,000 --> 00:59:22,000
fordi hvis jeg fjerner 5, så jeg fjerne 7.

1057
00:59:22,000 --> 00:59:24,000
Men jeg bare sette folk til høyre.

1058
00:59:24,000 --> 00:59:28,000
>> Det føles som om jeg kaster bort plass, og til slutt min køen disintegrates inn noe i det hele tatt,

1059
00:59:28,000 --> 00:59:31,000
slik at vi kunne bare ha folk wraparound,

1060
00:59:31,000 --> 00:59:35,000
og vi kunne tenke på denne tabellen egentlig som en slags sirkulær struktur,

1061
00:59:35,000 --> 00:59:38,000
men vi bruker det operatøren i C for å gjøre den slags wraparound?

1062
00:59:38,000 --> 00:59:40,000
[Uhørlig student respons] >> Den modulo operatør.

1063
00:59:40,000 --> 00:59:43,000
Det ville være litt irriterende å tenke gjennom hvordan du gjør wraparound,

1064
00:59:43,000 --> 00:59:46,000
men vi kunne gjøre det, og vi kunne begynne å sette folk på det pleide å være på forsiden av linjen,

1065
00:59:46,000 --> 00:59:52,000
men vi bare huske med dette hodet variabelen som selve hodet av linjen faktisk er.

1066
00:59:52,000 --> 00:59:57,000
Hva om, i stedet, vårt mål til slutt, skjønt,

1067
00:59:57,000 --> 01:00:00,000
var å slå opp numre, som vi gjorde her på scenen med Anita,

1068
01:00:00,000 --> 01:00:02,000
men vi virkelig ønsker det beste av alle disse verdener?

1069
01:00:02,000 --> 01:00:05,000
Vi ønsker mer raffinement enn matrise kan

1070
01:00:05,000 --> 01:00:09,000
fordi vi ønsker muligheten til dynamisk vokse datastrukturen.

1071
01:00:09,000 --> 01:00:12,000
Men vi ønsker ikke å måtte ty til noe som vi påpekte

1072
01:00:12,000 --> 01:00:15,000
i den første forelesningen var ikke en optimal algoritme,

1073
01:00:15,000 --> 01:00:17,000
at av lineær søk.

1074
01:00:17,000 --> 01:00:21,000
Det viser seg at du kan faktisk oppnå

1075
01:00:21,000 --> 01:00:24,000
eller i det minste nær konstant tid, hvorved en som Anita,

1076
01:00:24,000 --> 01:00:27,000
hvis hun konfigurerer sin datastruktur ikke å være en lenket liste,

1077
01:00:27,000 --> 01:00:30,000
ikke å være en stabel, for ikke å være en kø, kunne faktisk

1078
01:00:30,000 --> 01:00:33,000
komme opp med en datastruktur som gjør henne til å slå opp ting,

1079
01:00:33,000 --> 01:00:37,000
selv ord, ikke bare tall, i det vi kaller konstant tid.

1080
01:00:37,000 --> 01:00:40,000
>> Og faktisk, ser fremover, er en av de i denne klassen psets nesten alltid

1081
01:00:40,000 --> 01:00:43,000
en implementering av en stavekontroll, der

1082
01:00:43,000 --> 01:00:46,000
gir vi deg igjen noen 150000 engelske ord og målet er å

1083
01:00:46,000 --> 01:00:51,000
laste dem inn i minnet og raskt kunne svare på spørsmål i skjemaet

1084
01:00:51,000 --> 01:00:54,000
er dette ordet stavet riktig?

1085
01:00:54,000 --> 01:00:58,000
Og det ville virkelig suge hvis du måtte iterate gjennom alle 150000 ord for å svare på det.

1086
01:00:58,000 --> 01:01:02,000
Men, faktisk, vil vi se at vi kan gjøre det i veldig, veldig rask tid.

1087
01:01:02,000 --> 01:01:06,000
Og det kommer til å innebære å implementere noe som kalles en hash table,

1088
01:01:06,000 --> 01:01:09,000
og selv om ved første øyekast dette som kalles en hash table kommer til å

1089
01:01:09,000 --> 01:01:12,000
la oss få disse super rask responstid

1090
01:01:12,000 --> 01:01:18,000
det viser seg at det er faktisk et problem.

1091
01:01:18,000 --> 01:01:23,000
Når det gjelder tid til å implementere dette som kalles-igjen, jeg gjør det igjen.

1092
01:01:23,000 --> 01:01:25,000
Jeg er den eneste her.

1093
01:01:25,000 --> 01:01:28,000
Når det gjelder tid til å implementere dette som kalles en hash table,

1094
01:01:28,000 --> 01:01:30,000
vi nødt til å ta en beslutning.

1095
01:01:30,000 --> 01:01:32,000
Hvor stor bør denne tingen egentlig være?

1096
01:01:32,000 --> 01:01:36,000
Og når vi begynner å sette inn tallene i denne hash table,

1097
01:01:36,000 --> 01:01:38,000
hvordan skal vi lagre dem på en slik måte

1098
01:01:38,000 --> 01:01:42,000
at vi kan få dem ut igjen så raskt som vi fikk dem inn?

1099
01:01:42,000 --> 01:01:45,000
Men vi får se før lenge at dette spørsmålet

1100
01:01:45,000 --> 01:01:48,000
når alles bursdag i klassen vil være ganske germane.

1101
01:01:48,000 --> 01:01:51,000
Det viser seg at i dette rommet, har vi et par hundre mennesker,

1102
01:01:51,000 --> 01:01:56,000
så oddsen for at to av oss har samme bursdag er trolig ganske høy.

1103
01:01:56,000 --> 01:01:58,000
Hva hvis det var bare 40 av oss i dette rommet?

1104
01:01:58,000 --> 01:02:02,000
Hva er oddsen for to personer med samme bursdag?

1105
01:02:02,000 --> 01:02:04,000
[Studenter] Over 50%.

1106
01:02:04,000 --> 01:02:06,000
Ja, over 50%. Faktisk, jeg selv tok et diagram.

1107
01:02:06,000 --> 01:02:08,000
Det viser seg, og dette er egentlig bare en smakebit-

1108
01:02:08,000 --> 01:02:12,000
hvis det er bare 58 av oss i dette rommet, er sannsynligheten for 2 av oss

1109
01:02:12,000 --> 01:02:16,000
har samme bursdag er enormt høy, nesten 100%,

1110
01:02:16,000 --> 01:02:20,000
og det kommer til å føre til en hel haug med skade for oss på onsdag.

1111
01:02:20,000 --> 01:02:24,000
>> Med det sagt, la oss utsette her. Vi vil se deg på onsdag.

1112
01:02:24,000 --> 01:02:28,000
[Applaus]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]