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

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

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

4
00:00:08,000 --> 00:00:12,000
>> Detta är CS50, och detta är början av vecka 6,

5
00:00:12,000 --> 00:00:16,000
så ett par nya verktyg finns nu tillgängliga för dig att dra nytta av,

6
00:00:16,000 --> 00:00:19,000
Den första som kallas CS50 Style.

7
00:00:19,000 --> 00:00:22,000
Oddsen är om du är som mig eller någon av de pedagogiska stipendiater,

8
00:00:22,000 --> 00:00:26,000
Du har säkert sett ett program vars stil ser lite ut ungefär så här.

9
00:00:26,000 --> 00:00:30,000
Kanske du börjar skära vissa hörn sent på kvällen, eller du kommer att ta itu med det senare,

10
00:00:30,000 --> 00:00:32,000
och sedan en TF eller CA kommer över under kontorstid.

11
00:00:32,000 --> 00:00:34,000
Då är det svårt för oss att läsa.

12
00:00:34,000 --> 00:00:38,000
Nåväl, detta är koden syntaktiskt korrekt, och det kommer att sammanställa, och det kommer faktiskt köra.

13
00:00:38,000 --> 00:00:40,000
Men det är definitivt inte en 5 för stil.

14
00:00:40,000 --> 00:00:45,000
>> Men nu, när vi går in i den här katalogen här-

15
00:00:45,000 --> 00:00:48,000
och märker att jag har conditions2.c-

16
00:00:48,000 --> 00:00:55,000
och jag kör det här nya kommandot, style50 på denna fil conditions2.c, Enter,

17
00:00:55,000 --> 00:00:57,000
märker att det är informerat mig om att det har varit stiliserade.

18
00:00:57,000 --> 00:01:00,000
Gedit märkte att filen har ändrats på disk,

19
00:01:00,000 --> 00:01:08,000
och om jag klickar på ladda, alla dina problem nu automatiseras.

20
00:01:08,000 --> 00:01:15,000
[Applåder]

21
00:01:15,000 --> 00:01:17,000
Det är en av de saker vi gjorde i helgen.

22
00:01:17,000 --> 00:01:20,000
Inse att det är bristfälligt eftersom det finns lite kod

23
00:01:20,000 --> 00:01:23,000
att det helt enkelt inte att kunna stilisera perfekt,

24
00:01:23,000 --> 00:01:26,000
men inser att detta är nu ett verktyg som du kan dra nytta av

25
00:01:26,000 --> 00:01:33,000
om så bara för att städa upp några av de mer errantly placerade klammerparenteser och liknande.

26
00:01:33,000 --> 00:01:36,000
>> Men mer övertygande är nu CS50 Sök.

27
00:01:36,000 --> 00:01:39,000
Med CS50 Check kan du utföra faktiskt samma korrekthet tester

28
00:01:39,000 --> 00:01:42,000
på din egen kod att undervisningen stipendiater kan.

29
00:01:42,000 --> 00:01:44,000
Detta är en kommandorad verktyg som kommer nu i apparaten

30
00:01:44,000 --> 00:01:46,000
så fort du gör en update50 enligt

31
00:01:46,000 --> 00:01:49,000
Pset 4 specifikationer, och du använder det i huvudsak så här.

32
00:01:49,000 --> 00:01:51,000
Du kör kommandot check50.

33
00:01:51,000 --> 00:01:56,000
Då du passerar på ett argument, eller mer allmänt känd som en switch eller en flagga.

34
00:01:56,000 --> 00:01:58,000
Generellt är saker som har bindestreck kallas en switch

35
00:01:58,000 --> 00:02:02,000
till en kommandorad program anger så-C

36
00:02:02,000 --> 00:02:04,000
de kontroller som du vill köra.

37
00:02:04,000 --> 00:02:07,000
>> De tester som du vill köra identifieras unikt av denna sträng,

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

39
00:02:10,000 --> 00:02:13,000
Med andra ord, det är bara en godtycklig men unik sträng

40
00:02:13,000 --> 00:02:18,000
som vi använder för att identifiera pset 4 är korrekthet tester.

41
00:02:18,000 --> 00:02:21,000
Och sedan anger ett utrymme separerat lista över de filer som du vill ladda upp

42
00:02:21,000 --> 00:02:24,000
till CS50 Sök för analys.

43
00:02:24,000 --> 00:02:29,000
Till exempel, om jag går in i min lösning här resize.c-

44
00:02:29,000 --> 00:02:31,000
Låt mig öppna upp en större terminalfönster-

45
00:02:31,000 --> 00:02:42,000
och jag gå vidare och köra låt oss säga check50-C 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
och då går jag vidare och ange namnen på de filer,

47
00:02:46,000 --> 00:02:49,000
resize.c, och sedan trycka Enter, det komprimerar,

48
00:02:49,000 --> 00:02:53,000
det uppladdningar, kontrollerar det, och jag bara misslyckats en massa tester.

49
00:02:53,000 --> 00:02:59,000
Den i rött uppe till vänster säger att resize.c och bmp finns.

50
00:02:59,000 --> 00:03:01,000
Det var testet. Det var den fråga vi ställde.

51
00:03:01,000 --> 00:03:04,000
Och det är olycklig eftersom svaret var falskt.

52
00:03:04,000 --> 00:03:08,000
Den vita texten nedan står det förväntade bmp.h att existera, och det är helt enkelt mitt fel.

53
00:03:08,000 --> 00:03:11,000
Jag glömde att ladda upp den, så jag måste ladda upp båda filerna,

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

55
00:03:14,000 --> 00:03:17,000
Men nu märker alla andra tester i gult, eftersom de inte har kört,

56
00:03:17,000 --> 00:03:21,000
och så smiley är vertikal eftersom han är varken glad eller ledsen,

57
00:03:21,000 --> 00:03:25,000
men vi måste rätta att fråga i rött innan de andra kontroller körs.

58
00:03:25,000 --> 00:03:27,000
>> Jag löser det här.

59
00:03:27,000 --> 00:03:30,000
Låt mig zooma ut och köra detta, denna gång med bmp.h också

60
00:03:30,000 --> 00:03:34,000
på kommandoraden, Enter, och nu om allt går väl,

61
00:03:34,000 --> 00:03:38,000
det kommer att kontrollera och sedan returnera ett resultat av-hålla andan-

62
00:03:38,000 --> 00:03:42,000
alla gröna, vilket betyder att jag gör riktigt bra på pset 4 hittills.

63
00:03:42,000 --> 00:03:44,000
Du kan se och utläsa den beskrivande texten här

64
00:03:44,000 --> 00:03:47,000
exakt vad det är vi testat.

65
00:03:47,000 --> 00:03:49,000
Vi testade först göra filerna finns?

66
00:03:49,000 --> 00:03:51,000
Vi testade sedan gör resize.c sammanställa?

67
00:03:51,000 --> 00:03:58,000
Sedan testade vi det inte ändra storlek på ett 1x1 pixlar BMP när n, ändra storlek faktorn är 1.

68
00:03:58,000 --> 00:04:01,000
Nu, om du har ingen aning om vad n är, kommer du när du dyka in pset 4,

69
00:04:01,000 --> 00:04:04,000
men det är helt enkelt en sanity kontrollera att se till att du inte ändrar storlek

70
00:04:04,000 --> 00:04:08,000
en bild alls om resize faktorn är 1.

71
00:04:08,000 --> 00:04:14,000
Om däremot ändrar storlek det 1x1 pixel till en 1x1 pixel BMP till 2x2 korrekt

72
00:04:14,000 --> 00:04:19,000
när n är 2, då liknande, bildar min därefter.

73
00:04:19,000 --> 00:04:22,000
>> Kort sagt, detta tänkt att, en, ta korsar fingrarna

74
00:04:22,000 --> 00:04:25,000
ur ekvationen rätt innan du skickar din pset.

75
00:04:25,000 --> 00:04:28,000
Du kommer att veta exakt vad din TF snart kommer att veta

76
00:04:28,000 --> 00:04:30,000
när du går om hur du skickar några av dessa problem uppsättningar,

77
00:04:30,000 --> 00:04:34,000
och även pedagogiska motivationen är verkligen att sätta

78
00:04:34,000 --> 00:04:37,000
möjlighet framför dig så att när du vet på förhand

79
00:04:37,000 --> 00:04:39,000
att det finns fel i din kod och tester som inte blir godkända,

80
00:04:39,000 --> 00:04:43,000
du kan sätta i mer effektiv tid up front för att lösa dessa problem

81
00:04:43,000 --> 00:04:45,000
snarare än att förlora poäng, få feedback från din TF,

82
00:04:45,000 --> 00:04:48,000
och sedan gå, "Ahh," som jag borde ha listat ut.

83
00:04:48,000 --> 00:04:50,000
Nu åtminstone finns ett verktyg som hjälper dig att hitta det.

84
00:04:50,000 --> 00:04:52,000
Det kommer inte att peka ut var felet är, men det kommer att berätta

85
00:04:52,000 --> 00:04:54,000
vad är symptomatisk för det.

86
00:04:54,000 --> 00:04:57,000
>> Nu inser tester är inte nödvändigtvis uttömmande.

87
00:04:57,000 --> 00:04:59,000
Bara för att du får en skärm full av gröna smiley ansikten

88
00:04:59,000 --> 00:05:02,000
betyder inte din kod är perfekt, men det betyder

89
00:05:02,000 --> 00:05:06,000
att det har gått vissa tester som föreskrivs av spec.

90
00:05:06,000 --> 00:05:08,000
Ibland kommer vi inte att släppa kontrollen.

91
00:05:08,000 --> 00:05:10,000
Till exempel deckare, en av de aspekter av pset 4,

92
00:05:10,000 --> 00:05:15,000
är typ av en besvikelse om vi ger dig

93
00:05:15,000 --> 00:05:18,000
Svaret på vad det är, och det finns ett antal olika sätt att avslöja

94
00:05:18,000 --> 00:05:21,000
vem personen är i det röda buller.

95
00:05:21,000 --> 00:05:24,000
Spec kommer alltid ange i framtiden för pset 5 framåt

96
00:05:24,000 --> 00:05:26,000
vilka kontroller finns för dig.

97
00:05:26,000 --> 00:05:28,000
Du kommer att märka att det är det här vita webbadress längst ner.

98
00:05:28,000 --> 00:05:30,000
För nu är det bara diagnostiska utgång.

99
00:05:30,000 --> 00:05:33,000
Om du besöker denna webbadress får du en massa galna, kryptiska meddelanden

100
00:05:33,000 --> 00:05:36,000
att du är välkommen att titta igenom, men det är mest för personalen

101
00:05:36,000 --> 00:05:41,000
så att vi kan diagnostisera och felsöka buggar i check50 sig.

102
00:05:41,000 --> 00:05:46,000
>> Utan väsen, låt oss gå vidare till där vi slutade.

103
00:05:46,000 --> 00:05:48,000
CS50 bibliotek vi tog för givet under några veckor,

104
00:05:48,000 --> 00:05:52,000
men än förra veckan började vi riva en av de lager av det.

105
00:05:52,000 --> 00:05:55,000
Vi började lägga undan sträng till förmån för vad i stället?

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

107
00:05:57,000 --> 00:05:59,000
Char *, som har varit en char * hela tiden,

108
00:05:59,000 --> 00:06:03,000
men nu har vi inte låtsas att det är en verklig datatypen sträng.

109
00:06:03,000 --> 00:06:06,000
Snarare har det varit en synonym slags för char *,

110
00:06:06,000 --> 00:06:09,000
och en sträng är en sekvens av tecken,

111
00:06:09,000 --> 00:06:14,000
så varför gör det meningsfullt att representera strängar som char * s?

112
00:06:14,000 --> 00:06:20,000
Vad representerar en char * i samband med detta koncept i en sträng?

113
00:06:20,000 --> 00:06:23,000
Ja. >> [Student] Det första tecknet.

114
00:06:23,000 --> 00:06:25,000
Bra, det första tecknet, men inte riktigt det första tecknet.

115
00:06:25,000 --> 00:06:27,000
Det är de-[Studenter] Adress.

116
00:06:27,000 --> 00:06:29,000
Bra, adressen till den första tecknet.

117
00:06:29,000 --> 00:06:33,000
Allt som är nödvändigt för att representera en sträng i en dators minne

118
00:06:33,000 --> 00:06:36,000
är bara den unika adressen för den första bitgruppen.

119
00:06:36,000 --> 00:06:38,000
Du behöver inte ens veta hur lång tid det är

120
00:06:38,000 --> 00:06:42,000
eftersom hur kan du räkna ut dynamiskt?

121
00:06:42,000 --> 00:06:44,000
[Student] Sträng längd.

122
00:06:44,000 --> 00:06:48,000
Du kan ringa stränglängd, utmärkt, men hur fungerar stränglängd?

123
00:06:48,000 --> 00:06:50,000
Vad gör det? Ja.

124
00:06:50,000 --> 00:06:52,000
[Student] Fortsätt tills du får noll karaktär.

125
00:06:52,000 --> 00:06:54,000
Ja, exakt, itererar bara med en for-slinga, medan slinga,

126
00:06:54,000 --> 00:06:57,000
vad från * till slutet, och slutet är representerad

127
00:06:57,000 --> 00:07:01,000
av \ 0, den så kallade nul karaktär, NUL,

128
00:07:01,000 --> 00:07:05,000
inte att förväxla med null, vilket är en pekare,

129
00:07:05,000 --> 00:07:07,000
som kommer upp i konversationen igen idag.

130
00:07:07,000 --> 00:07:11,000
>> Vi skalade tillbaka ett lager av getInt, och sedan tog vi en titt på GetString,

131
00:07:11,000 --> 00:07:14,000
och minns att båda dessa funktioner, eller egentligen,

132
00:07:14,000 --> 00:07:18,000
GetString var med en viss funktion

133
00:07:18,000 --> 00:07:21,000
att faktiskt tolka, är att läsa eller analysera användarens input.

134
00:07:21,000 --> 00:07:25,000
Och vad var det ny funktion?

135
00:07:25,000 --> 00:07:27,000
Scanf eller sscanf. Det kommer faktiskt i några olika smaker.

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

137
00:07:31,000 --> 00:07:35,000
För nu, men låt oss fokusera på det som mest lätt illustreras,

138
00:07:35,000 --> 00:07:38,000
och låt mig gå vidare och öppna upp i apparaten

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

140
00:07:41,000 --> 00:07:43,000
Detta är en super enkelt program,

141
00:07:43,000 --> 00:07:46,000
men som gör något som vi aldrig gjort

142
00:07:46,000 --> 00:07:48,000
utan hjälp av CS50 biblioteket.

143
00:07:48,000 --> 00:07:51,000
Detta får en int från en användare. Hur fungerar det?

144
00:07:51,000 --> 00:07:53,000
Tja, i linje 16 där,

145
00:07:53,000 --> 00:07:56,000
märker att vi förklarar en int som kallas X, och på denna punkt i berättelsen,

146
00:07:56,000 --> 00:07:58,000
vad är värdet av x?

147
00:07:58,000 --> 00:08:00,000
[Ohörbart elev svar]

148
00:08:00,000 --> 00:08:02,000
[David M.] Höger, vem vet, vissa skräp värde potentiellt, så i 17, säger vi bara användaren

149
00:08:02,000 --> 00:08:06,000
ge mig ett nummer, och steg 18 är där det blir intressant.

150
00:08:06,000 --> 00:08:11,000
Scanf verkar låna en idé från printf att det använder dessa format koder inom citationstecken.

151
00:08:11,000 --> 00:08:13,000
% D är naturligtvis ett decimaltal.

152
00:08:13,000 --> 00:08:21,000
Men varför jag passerar i & X istället för bara x?

153
00:08:21,000 --> 00:08:24,000
Den förstnämnda är korrekt. Ja.

154
00:08:24,000 --> 00:08:26,000
[Ohörbart elev svar]

155
00:08:26,000 --> 00:08:31,000
Exakt, om målet med detta program, liksom funktionen getInt själv,

156
00:08:31,000 --> 00:08:34,000
är att få en int från användaren jag kan passera funktioner

157
00:08:34,000 --> 00:08:38,000
alla variabler jag vill, men om jag inte klarar dem genom hänvisning

158
00:08:38,000 --> 00:08:41,000
eller efter adress eller efter pekare, alla synonymt för dagens ändamål,

159
00:08:41,000 --> 00:08:46,000
då denna funktion inte har någon möjlighet att ändra innehållet i den variabeln.

160
00:08:46,000 --> 00:08:49,000
Detta skulle passera i en kopia precis som den buggig version av swap

161
00:08:49,000 --> 00:08:51,000
att vi har pratat om ett par gånger nu.

162
00:08:51,000 --> 00:08:54,000
>> Men istället, genom att göra & X, jag passerar bokstavligen i vad?

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

164
00:08:57,000 --> 00:09:01,000
Det är som att rita en karta för den funktion som heter scanf och säger här,

165
00:09:01,000 --> 00:09:04,000
dessa är vägbeskrivning till en bit av minne i datorn

166
00:09:04,000 --> 00:09:07,000
att du kan gå lagra viss heltal i.

167
00:09:07,000 --> 00:09:10,000
För att sscanf att nu göra det

168
00:09:10,000 --> 00:09:13,000
vilken operatör, vad är del av syntax det kommer att behöva använda

169
00:09:13,000 --> 00:09:19,000
även om vi inte kan se det eftersom någon annan skrev denna funktion?

170
00:09:19,000 --> 00:09:21,000
Med andra ord - vad är det?

171
00:09:21,000 --> 00:09:23,000
[Student] X läsa.

172
00:09:23,000 --> 00:09:27,000
Det kommer att bli lite läsning, men bara när det gäller X här.

173
00:09:27,000 --> 00:09:30,000
Om scanf håller passerat adressen av x,

174
00:09:30,000 --> 00:09:35,000
syntaktiskt, vad operatören skyldig att existera någonstans

175
00:09:35,000 --> 00:09:38,000
insidan av scanf genomförande så att scanf

176
00:09:38,000 --> 00:09:42,000
kan faktiskt skriva ett nummer 2 till den adressen?

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

178
00:09:44,000 --> 00:09:47,000
Minns att * är vår dereference aktör och som i huvudsak innebär att gå dit.

179
00:09:47,000 --> 00:09:50,000
>> När du har gått i arv en adress, vilket är fallet här,

180
00:09:50,000 --> 00:09:53,000
scanf är förmodligen-om vi såg faktiskt runt sin källkod-

181
00:09:53,000 --> 00:09:59,000
gör * x eller motsvarande att faktiskt gå till den adressen och sätta något värde där.

182
00:09:59,000 --> 00:10:02,000
Nu, som för hur scanf får input från tangentbordet,

183
00:10:02,000 --> 00:10:04,000
vi vifta våra händer ute för idag.

184
00:10:04,000 --> 00:10:07,000
Bara anta att operativsystemet tillåter sscanf att prata

185
00:10:07,000 --> 00:10:11,000
till användarens tangentbord, men vid denna punkt nu i linje 19,

186
00:10:11,000 --> 00:10:14,000
när vi helt enkelt skriva ut X, det verkar vara fallet

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

188
00:10:17,000 --> 00:10:19,000
Det är precis hur scanf fungerar och hämta förra veckan

189
00:10:19,000 --> 00:10:25,000
det är exakt hur GetString och getInt och dess andra familjen av funktioner

190
00:10:25,000 --> 00:10:28,000
slutändan fungerar, om än med liten avvikelse som sscanf,

191
00:10:28,000 --> 00:10:31,000
vilket innebär skanna en sträng i stället för tangentbordet.

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

193
00:10:33,000 --> 00:10:37,000
Under scanf2, skruvas jag faktiskt upp.

194
00:10:37,000 --> 00:10:42,000
Vad är fel, och jag gömmer den kommentar som förklarar så mycket,

195
00:10:42,000 --> 00:10:47,000
vad som är fel med det här programmet, version 2?

196
00:10:47,000 --> 00:10:55,000
Var så teknisk som möjligt den här gången.

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

198
00:10:57,000 --> 00:11:03,000
Det är snyggt indragen, men-

199
00:11:03,000 --> 00:11:07,000
okej, vad sägs om vi beskär ner till kortare frågor?

200
00:11:07,000 --> 00:11:17,000
Linje 16. Vad är linjen 16 gör i exakt men teknisk engelska?

201
00:11:17,000 --> 00:11:20,000
Att få lite pinsamt. Ja, Michael.

202
00:11:20,000 --> 00:11:25,000
[Student] Det pekar på första bokstaven i en sträng.

203
00:11:25,000 --> 00:11:27,000
>> Okej, nära. Låt mig tweak att lite.

204
00:11:27,000 --> 00:11:33,000
Pekar på första bokstaven i en sträng, du deklarera en variabel som heter buffert

205
00:11:33,000 --> 00:11:36,000
som pekar på den första adressen av en sträng,

206
00:11:36,000 --> 00:11:39,000
eller snarare kommer att peka mera specifikt till en char.

207
00:11:39,000 --> 00:11:42,000
Notera det faktiskt inte peka någonstans eftersom det inte finns någon uppgift operatör.

208
00:11:42,000 --> 00:11:46,000
Det finns inga likhetstecken, så allt vi gör är att fördela variabel kallad buffert.

209
00:11:46,000 --> 00:11:49,000
Det råkar vara 32 bitar eftersom det är en pekare,

210
00:11:49,000 --> 00:11:52,000
och innehållet i buffert antagligen småningom

211
00:11:52,000 --> 00:11:57,000
kommer att innehålla en adress till en röding, men nu, vad buffert innehålla?

212
00:11:57,000 --> 00:11:59,000
Bara några falska, vem vet, vissa skräp värde,

213
00:11:59,000 --> 00:12:03,000
eftersom vi inte har uttryckligen initierats det, så vi bör inte ta något.

214
00:12:03,000 --> 00:12:06,000
Okej, så nu linje 17 är-vad gör linjen 17 gör?

215
00:12:06,000 --> 00:12:08,000
Kanske det kommer att värma upp detta.

216
00:12:08,000 --> 00:12:10,000
Den skriver en sträng, eller hur?

217
00:12:10,000 --> 00:12:12,000
Den skriver String tack.

218
00:12:12,000 --> 00:12:15,000
>> Linje 18 är typ av bekant nu i att vi bara såg en varians detta

219
00:12:15,000 --> 00:12:18,000
men med ett annat format kod, så i linje 18,

220
00:12:18,000 --> 00:12:23,000
vi säger scanf här är adressen till en bit av minne.

221
00:12:23,000 --> 00:12:27,000
Jag vill att du ska ringa i en sträng, vilket antyds av% s,

222
00:12:27,000 --> 00:12:32,000
men problemet är att vi inte har gjort ett par saker här.

223
00:12:32,000 --> 00:12:35,000
Vad är ett av problemen?

224
00:12:35,000 --> 00:12:38,000
[Student] Den försöker dereference en null-pekare.

225
00:12:38,000 --> 00:12:41,000
Bra, null eller bara annars okända pekare.

226
00:12:41,000 --> 00:12:45,000
Du lämnar scanf en adress, men du sa bara för en stund sedan

227
00:12:45,000 --> 00:12:49,000
att den adressen är något skräp värde eftersom vi faktiskt inte tilldela den till något,

228
00:12:49,000 --> 00:12:53,000
och så du säger scanf effektivt gå sätta en sträng här,

229
00:12:53,000 --> 00:12:56,000
men vi vet inte var här ännu är,

230
00:12:56,000 --> 00:12:59,000
så vi har faktiskt inte allokerat minne för buffert.

231
00:12:59,000 --> 00:13:03,000
Dessutom, vad är du inte heller ens berätta scanf?

232
00:13:03,000 --> 00:13:06,000
Antar att detta var en bit av minnet, och det var inte ett skräp värde,

233
00:13:06,000 --> 00:13:09,000
men du är fortfarande inte berätta scanf något viktigt.

234
00:13:09,000 --> 00:13:12,000
[Student] Om det faktiskt är, et-tecknet.

235
00:13:12,000 --> 00:13:15,000
Ampersand, så i detta fall, det är okej.

236
00:13:15,000 --> 00:13:18,000
Eftersom buffert redan förklarat som en pekare

237
00:13:18,000 --> 00:13:22,000
med * bit syntax, behöver vi inte använda et-tecken

238
00:13:22,000 --> 00:13:25,000
eftersom det är redan en adress, men jag tror att jag hörde det här.

239
00:13:25,000 --> 00:13:27,000
[Student] Hur stort är det?

240
00:13:27,000 --> 00:13:29,000
Bra, vi berättar inte scanf hur stor denna buffert är,

241
00:13:29,000 --> 00:13:32,000
vilket innebär att även om bufferten var en pekare,

242
00:13:32,000 --> 00:13:35,000
vi säger scanf, sätta en sträng här,

243
00:13:35,000 --> 00:13:38,000
men här kan vara 2 byte, kan det vara 10 byte, kan det vara en megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf har ingen aning, och eftersom detta är en bit av minne

245
00:13:41,000 --> 00:13:43,000
förmodligen är det inte en sträng ännu.

246
00:13:43,000 --> 00:13:48,000
Det är bara en sträng när du skriver tecken och en \ 0 som bit av minnet.

247
00:13:48,000 --> 00:13:51,000
Nu är det bara några bit av minnet.

248
00:13:51,000 --> 00:13:55,000
Scanf inte vet när du ska sluta skriva till den adressen.

249
00:13:55,000 --> 00:13:59,000
>> Om ni minns några exempel i det förflutna där jag slumpmässigt skrivit på tangentbordet

250
00:13:59,000 --> 00:14:03,000
försöker spilla en buffert, och vi pratade på fredag ​​om just detta.

251
00:14:03,000 --> 00:14:07,000
Om en motståndare injicerar något i ditt program en mycket större ord

252
00:14:07,000 --> 00:14:10,000
eller mening eller fras då du väntade dig kan överskridande

253
00:14:10,000 --> 00:14:13,000
en bit av minnet, vilket kan få dåliga konsekvenser,

254
00:14:13,000 --> 00:14:15,000
som att ta över hela programmet själv.

255
00:14:15,000 --> 00:14:17,000
Vi måste fixa det här på något sätt.

256
00:14:17,000 --> 00:14:20,000
Låt mig zooma ut och gå in version 3 av programmet.

257
00:14:20,000 --> 00:14:22,000
Det är lite bättre.

258
00:14:22,000 --> 00:14:24,000
I denna version märker skillnaden.

259
00:14:24,000 --> 00:14:27,000
I linje 16, jag förklara igen en variabel som heter buffert,

260
00:14:27,000 --> 00:14:29,000
men vad är det nu?

261
00:14:29,000 --> 00:14:33,000
Det är en samling av 16 tecken.

262
00:14:33,000 --> 00:14:36,000
Detta är bra eftersom det betyder att jag nu kan berätta scanf

263
00:14:36,000 --> 00:14:39,000
här är en verklig bit av minnet.

264
00:14:39,000 --> 00:14:42,000
Du kan nästan tänka arrayer som pekare nu,

265
00:14:42,000 --> 00:14:44,000
även om de är faktiskt inte likvärdiga.

266
00:14:44,000 --> 00:14:47,000
De kommer bete sig på olika sätt i olika sammanhang.

267
00:14:47,000 --> 00:14:50,000
Men det är verkligen så att bufferten refererar

268
00:14:50,000 --> 00:14:53,000
16 sammanhängande tecken eftersom det är vad en matris är

269
00:14:53,000 --> 00:14:55,000
och har varit i några veckor nu.

270
00:14:55,000 --> 00:14:59,000
>> Här säger jag scanf här är en bit av minne.

271
00:14:59,000 --> 00:15:01,000
Den här gången är det faktiskt en bit av minne,

272
00:15:01,000 --> 00:15:07,000
men varför är det här programmet fortfarande utnyttjas?

273
00:15:07,000 --> 00:15:11,000
Vad är det för fel ännu?

274
00:15:11,000 --> 00:15:14,000
Jag har sagt ge mig 16 byte, men-

275
00:15:14,000 --> 00:15:16,000
[Student] Vad händer om man skriver in mer än 16?

276
00:15:16,000 --> 00:15:20,000
Exakt, vad händer om användaren skriver i 17 tecken eller tecken 1700?

277
00:15:20,000 --> 00:15:23,000
I själva verket, låt oss se om vi inte kan snubbla över detta misstag nu.

278
00:15:23,000 --> 00:15:25,000
Det är bättre men inte perfekt.

279
00:15:25,000 --> 00:15:28,000
Låt mig gå vidare och kör make scanf3 att sammanställa detta program.

280
00:15:28,000 --> 00:15:34,000
Låt mig köra scanf3, String snälla: hej, och vi verkar vara okej.

281
00:15:34,000 --> 00:15:37,000
Låt mig försöka lite längre en, hello there.

282
00:15:37,000 --> 00:15:42,000
Okej, låt oss göra hello there hur mår du idag, Enter.

283
00:15:42,000 --> 00:15:54,000
Att få typ av tur här, låt oss säga hello there hur mår du.

284
00:15:54,000 --> 00:15:56,000
Fan också.

285
00:15:56,000 --> 00:16:03,000
Okej, så vi hade tur. Låt oss se om vi inte kan fixa det här.

286
00:16:03,000 --> 00:16:06,000
Nej, det kommer inte att låta mig kopiera.

287
00:16:06,000 --> 00:16:09,000
Låt oss prova det här igen.

288
00:16:09,000 --> 00:16:12,000
Okej, stand by.

289
00:16:12,000 --> 00:16:20,000
Vi får se hur länge jag kan låtsas att fokusera samtidigt gör detta.

290
00:16:20,000 --> 00:16:23,000
Fan också. Det är ganska passande, faktiskt.

291
00:16:23,000 --> 00:16:26,000
Där kör vi.

292
00:16:26,000 --> 00:16:30,000
Punkt gjort.

293
00:16:30,000 --> 00:16:34,000
>> Detta pinsamt men det är också, det är också en av orsakerna till stor förvirring

294
00:16:34,000 --> 00:16:38,000
när du skriver program som har fel eftersom de visar sig

295
00:16:38,000 --> 00:16:40,000
endast en gång på ett tag ibland.

296
00:16:40,000 --> 00:16:43,000
Verkligheten är att även om din kod är helt bruten,

297
00:16:43,000 --> 00:16:46,000
det kan bara vara helt brytas då och då

298
00:16:46,000 --> 00:16:49,000
eftersom det ibland, i huvudsak vad som händer är operativsystemet allokerar

299
00:16:49,000 --> 00:16:52,000
lite mer minne än du behöver faktiskt av någon anledning,

300
00:16:52,000 --> 00:16:57,000
och så att ingen annan använder minnet direkt efter bit av 16 tecken,

301
00:16:57,000 --> 00:17:01,000
så om du går till 17, 18, 19, vad som helst, det är inte så stor roll.

302
00:17:01,000 --> 00:17:04,000
Nu, datorn, även om det inte kraschar vid den punkten,

303
00:17:04,000 --> 00:17:09,000
kan så småningom användas byte nummer 17 eller 18 eller 19 för något annat,

304
00:17:09,000 --> 00:17:14,000
vid vilken punkt dina data som du lagt där, om än alltför lång,

305
00:17:14,000 --> 00:17:18,000
kommer att få skrivas över potentiellt av någon annan funktion.

306
00:17:18,000 --> 00:17:21,000
Det är inte nödvändigtvis kommer att förbli intakt,

307
00:17:21,000 --> 00:17:23,000
men det kommer inte nödvändigtvis orsaka en seg fel.

308
00:17:23,000 --> 00:17:26,000
Men i detta fall, förutsatt att jag äntligen tillräckligt många tecken

309
00:17:26,000 --> 00:17:29,000
att jag överskridit huvudsak mitt segment av minne och bam,

310
00:17:29,000 --> 00:17:33,000
operativsystemet sa: "Tyvärr, det är inte bra, segmenteringsfel."

311
00:17:33,000 --> 00:17:38,000
>> Och låt oss se nu om det som återstår här i min katalog-

312
00:17:38,000 --> 00:17:40,000
märker att jag har den här filen här, kärna.

313
00:17:40,000 --> 00:17:42,000
Observera att detta återigen kallas minnesutskriftsfil.

314
00:17:42,000 --> 00:17:46,000
Det är i huvudsak en fil som innehåller innehållet i programmets minne

315
00:17:46,000 --> 00:17:48,000
vid den punkt där det kraschade,

316
00:17:48,000 --> 00:17:51,000
och bara för att prova lite exempel här Låt mig gå in här

317
00:17:51,000 --> 00:17:57,000
och kör gdb på scanf3 och sedan ange en tredje argument som kallas kärna,

318
00:17:57,000 --> 00:18:01,000
och märker här att om jag lista koden

319
00:18:01,000 --> 00:18:06,000
Vi kommer att kunna som vanligt med gdb för att börja gå igenom detta program,

320
00:18:06,000 --> 00:18:10,000
och jag kan köra den och så fort jag hit-som med steg kommandot i gdb-

321
00:18:10,000 --> 00:18:13,000
så fort jag slog potentiellt buggig rad efter att skriva i en stor sträng,

322
00:18:13,000 --> 00:18:16,000
Jag kommer att kunna verkligen identifiera den här.

323
00:18:16,000 --> 00:18:19,000
Mer om detta, men i snitt i termer av grundläggande dumpar

324
00:18:19,000 --> 00:18:22,000
och liknande så att du faktiskt kan rota runt inne i kärnan dumpa

325
00:18:22,000 --> 00:18:27,000
och se på vilken linje programmet misslyckades dig.

326
00:18:27,000 --> 00:18:32,000
Har du frågor så om pekare och adresser?

327
00:18:32,000 --> 00:18:36,000
Eftersom idag på, kommer vi att börja ta för givet att dessa saker existerar

328
00:18:36,000 --> 00:18:40,000
och vi vet exakt vad de är.

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

330
00:18:42,000 --> 00:18:46,000
>> [Student] Hur kommer du inte måste sätta ett et-tecken bredvid den del-

331
00:18:46,000 --> 00:18:48,000
Bra fråga.

332
00:18:48,000 --> 00:18:51,000
Hur kommer jag inte behövde sätta ett et-tecken bredvid tecknet array som jag gjorde tidigare

333
00:18:51,000 --> 00:18:53,000
med de flesta av våra exempel?

334
00:18:53,000 --> 00:18:55,000
Det korta svaret är arrayer är lite speciell.

335
00:18:55,000 --> 00:18:59,000
Du kan nästan tänka en buffert som faktiskt är en adress,

336
00:18:59,000 --> 00:19:03,000
och det bara så råkar vara så att den fyrkantiga fästet notation

337
00:19:03,000 --> 00:19:06,000
är en bekvämlighet så att vi kan gå in hållaren 0, fäste 1,

338
00:19:06,000 --> 00:19:10,000
fäste 2, utan att behöva använda * notation.

339
00:19:10,000 --> 00:19:13,000
Det är lite av en vit lögn eftersom arrayer och pekare

340
00:19:13,000 --> 00:19:17,000
är i själva verket lite annorlunda, men de kan ofta men inte alltid användas omväxlande.

341
00:19:17,000 --> 00:19:21,000
Kort sagt, när en funktion förväntar en pekare till en bit av minne,

342
00:19:21,000 --> 00:19:24,000
kan du antingen ge det en adress som returneras av malloc,

343
00:19:24,000 --> 00:19:29,000
och vi får se malloc igen snart, eller så kan du ge det namnet på en matris.

344
00:19:29,000 --> 00:19:32,000
Du behöver inte göra ampersand med arrayer eftersom de redan

345
00:19:32,000 --> 00:19:34,000
väsentligen liknande adresser.

346
00:19:34,000 --> 00:19:36,000
Det är det enda undantaget.

347
00:19:36,000 --> 00:19:39,000
Hakparenteserna gör dem speciella.

348
00:19:39,000 --> 00:19:41,000
>> Kan du sätta ett et-tecken bredvid bufferten?

349
00:19:41,000 --> 00:19:43,000
Inte i detta fall.

350
00:19:43,000 --> 00:19:46,000
Det skulle inte fungera eftersom, återigen, detta hörn fall

351
00:19:46,000 --> 00:19:49,000
där arrayer är inte riktigt faktiskt adresser.

352
00:19:49,000 --> 00:19:54,000
Men vi ska kanske återkomma till detta inom kort med andra exempel.

353
00:19:54,000 --> 00:19:56,000
Låt oss försöka att lösa ett problem här.

354
00:19:56,000 --> 00:20:00,000
Vi har en datastruktur som vi har använt under en tid känd som en matris.

355
00:20:00,000 --> 00:20:02,000
Ett typexempel, det är vad vi just haft.

356
00:20:02,000 --> 00:20:04,000
Men arrayer har några upsides och nackdelar.

357
00:20:04,000 --> 00:20:06,000
Arrayer är trevliga varför?

358
00:20:06,000 --> 00:20:11,000
Vad är en sak som du gillar, i den mån du vill arrayer-om arrayer?

359
00:20:11,000 --> 00:20:13,000
Vad är bekvämt om dem? Vad är övertygande?

360
00:20:13,000 --> 00:20:18,000
Varför har vi introducerar dem i första hand?

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

362
00:20:20,000 --> 00:20:27,000
[Student] De kan lagra mycket data, och du behöver inte använda en hel sak.

363
00:20:27,000 --> 00:20:29,000
Du kan använda ett avsnitt.

364
00:20:29,000 --> 00:20:32,000
Bra, med en rad kan du lagra mycket data,

365
00:20:32,000 --> 00:20:35,000
och du behöver inte nödvändigtvis använda alla det, så att du kan overallocate,

366
00:20:35,000 --> 00:20:39,000
vilket kan vara praktiskt om du inte vet i förväg hur många av något att förvänta sig.

367
00:20:39,000 --> 00:20:41,000
>> GetString är ett perfekt exempel.

368
00:20:41,000 --> 00:20:44,000
GetString, skriven av oss har ingen aning om hur många tecken att förvänta sig,

369
00:20:44,000 --> 00:20:48,000
så att vi kan fördela bitar av sammanhängande minne är bra.

370
00:20:48,000 --> 00:20:51,000
Arrayer löser också ett problem som vi såg för ett par veckor sedan nu

371
00:20:51,000 --> 00:20:54,000
där din kod börjar att överlåta till något mycket dåligt utformade.

372
00:20:54,000 --> 00:20:57,000
Minns att jag skapade en student struktur som kallas David,

373
00:20:57,000 --> 00:21:00,000
och sedan det var faktiskt ett alternativ, men

374
00:21:00,000 --> 00:21:04,000
att ha en variabel som heter namn och en annan variabel som heter, tror jag, hus,

375
00:21:04,000 --> 00:21:08,000
och en annan variabel som heter ID eftersom den historien jag sedan ville införa något annat

376
00:21:08,000 --> 00:21:11,000
gillar Rob i programmet, så då bestämde jag mig vänta en minut,

377
00:21:11,000 --> 00:21:13,000
Jag behöver byta namn på dessa variabler.

378
00:21:13,000 --> 00:21:16,000
Låt oss kalla min NAME1, ID1, House1.

379
00:21:16,000 --> 00:21:20,000
Låt oss kalla Rob namn2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Men sedan vänta en minut, hur Tommy?

381
00:21:22,000 --> 00:21:24,000
Sedan hade vi tre variabler.

382
00:21:24,000 --> 00:21:27,000
Vi introducerade någon annan, fyra uppsättningar variabler.

383
00:21:27,000 --> 00:21:30,000
Världen började bli rörigt väldigt snabbt,

384
00:21:30,000 --> 00:21:33,000
så vi introducerade structs, och vad som är övertygande om en struct?

385
00:21:33,000 --> 00:21:39,000
Vad låter en C struct du göra?

386
00:21:39,000 --> 00:21:42,000
Det är verkligen pinsamt idag.

387
00:21:42,000 --> 00:21:44,000
Vad? >> [Ohörbart elev svar]

388
00:21:44,000 --> 00:21:47,000
Ja, speciellt kan typedef du skapa en ny datatyp,

389
00:21:47,000 --> 00:21:51,000
och struct, det struct sökord kan du kapsla

390
00:21:51,000 --> 00:21:54,000
konceptuellt relaterade delar av data tillsammans

391
00:21:54,000 --> 00:21:56,000
och därefter kalla dem något som liknar en elev.

392
00:21:56,000 --> 00:21:58,000
>> Det var bra eftersom vi nu kan modellera

393
00:21:58,000 --> 00:22:03,000
mycket mer sorts konceptuellt konsekvent begreppet elev i en variabel

394
00:22:03,000 --> 00:22:07,000
snarare än godtyckligt har en för en sträng, en för ett ID, och så vidare.

395
00:22:07,000 --> 00:22:10,000
Arrayer är bra eftersom de tillåter oss att börja städa upp vår kod.

396
00:22:10,000 --> 00:22:13,000
Men vad är en nackdel nu av en matris?

397
00:22:13,000 --> 00:22:15,000
Vad kan du göra det? Ja.

398
00:22:15,000 --> 00:22:17,000
[Student] Du måste veta hur stort det är.

399
00:22:17,000 --> 00:22:19,000
Du måste veta hur stort det är, så det är lite av en smärta.

400
00:22:19,000 --> 00:22:21,000
De av er med tidigare erfarenhet av programmering vet att i många språk,

401
00:22:21,000 --> 00:22:24,000
som Java, kan du be en bit av minne, speciellt en array,

402
00:22:24,000 --> 00:22:28,000
hur stor är du, med en längd, egendom, så att säga, och det är verkligen bekvämt.

403
00:22:28,000 --> 00:22:32,000
I C kan du inte heller ringa strlen på en generisk rad

404
00:22:32,000 --> 00:22:35,000
eftersom strlen, som ordet antyder, är endast för stråkar,

405
00:22:35,000 --> 00:22:39,000
och du kan räkna ut längden på en sträng på grund av denna mänskliga konvention

406
00:22:39,000 --> 00:22:43,000
att ha en \ 0, men en array, mer allmänt, är bara en bit av minne.

407
00:22:43,000 --> 00:22:46,000
Om det är en rad Ints, är det inte kommer att bli några specialtecken

408
00:22:46,000 --> 00:22:48,000
i slutet väntar på dig.

409
00:22:48,000 --> 00:22:50,000
Man måste komma ihåg längden på en array.

410
00:22:50,000 --> 00:22:54,000
En annan nackdel med en matris fötts huvudet i getString sig.

411
00:22:54,000 --> 00:22:59,000
Vad är en annan nackdel av en matris?

412
00:22:59,000 --> 00:23:01,000
Sir, bara du och jag idag.

413
00:23:01,000 --> 00:23:04,000
[Ohörbart elev svar] >> Det är vad?

414
00:23:04,000 --> 00:23:06,000
Det uttalade på stacken.

415
00:23:06,000 --> 00:23:09,000
Okej, förklarade på stacken. Varför inte du det?

416
00:23:09,000 --> 00:23:13,000
[Student] eftersom det blir återanvändas.

417
00:23:13,000 --> 00:23:15,000
Det blir återanvändas.

418
00:23:15,000 --> 00:23:18,000
Okej, om du använder en matris för att allokera minne,

419
00:23:18,000 --> 00:23:21,000
Du kan till exempel inte, returnera det eftersom det är på stacken.

420
00:23:21,000 --> 00:23:23,000
Okej, det är en nackdel.

421
00:23:23,000 --> 00:23:25,000
Och vad sägs om en annan med en rad?

422
00:23:25,000 --> 00:23:28,000
När du fördela det, du typ av skruvade om du behöver mer utrymme

423
00:23:28,000 --> 00:23:30,000
än matrisen har.

424
00:23:30,000 --> 00:23:34,000
>> Då vi infört, minns, malloc, som gav oss möjligheten att dynamiskt allokera minne.

425
00:23:34,000 --> 00:23:37,000
Men vad händer om vi försökte en annan värld helt och hållet?

426
00:23:37,000 --> 00:23:40,000
Tänk om vi ville lösa ett par av dessa problem

427
00:23:40,000 --> 00:23:45,000
så vi istället-min penna har somnat här-

428
00:23:45,000 --> 00:23:51,000
tänk om vi istället ville huvudsak skapa en värld som inte längre så här?

429
00:23:51,000 --> 00:23:56,000
Detta är en matris, och, naturligtvis, försämras denna typ av när vi träffar slutet av arrayen,

430
00:23:56,000 --> 00:24:00,000
och jag har nu inte längre har utrymme för en annan heltal eller ett annat tecken.

431
00:24:00,000 --> 00:24:03,000
Tänk om vi sorts förebyggande syfte säga bra, varför inte vi slappna

432
00:24:03,000 --> 00:24:07,000
detta krav att alla dessa bitar av minnet vara angränsande rygg mot rygg,

433
00:24:07,000 --> 00:24:10,000
och varför inte, när jag behöver en int eller en röding,

434
00:24:10,000 --> 00:24:12,000
bara ge mig utrymme för en av dem?

435
00:24:12,000 --> 00:24:14,000
Och när jag behöver en annan, ge mig ett annat rum,

436
00:24:14,000 --> 00:24:16,000
och när jag behöver en, ge mig ett annat rum.

437
00:24:16,000 --> 00:24:19,000
Fördelen med som nu att om någon annan

438
00:24:19,000 --> 00:24:21,000
tar minnet hit, no big deal.

439
00:24:21,000 --> 00:24:25,000
Jag tar denna ytterligare bit av minnet här och sedan här.

440
00:24:25,000 --> 00:24:28,000
>> Nu är den enda fångsten här att detta nästan känns som jag har

441
00:24:28,000 --> 00:24:30,000
en hel massa olika variabler.

442
00:24:30,000 --> 00:24:33,000
Detta känns som fem olika variabler potentiellt.

443
00:24:33,000 --> 00:24:36,000
Men tänk om vi stjäl en idé från strängar

444
00:24:36,000 --> 00:24:41,000
där vi kopplar på något sätt dessa saker tillsammans begreppsmässigt, och tänk om jag gjorde det?

445
00:24:41,000 --> 00:24:44,000
Detta är min mycket dåligt dragen pil.

446
00:24:44,000 --> 00:24:46,000
Men antag att alla dessa bitar av minnet

447
00:24:46,000 --> 00:24:52,000
pekade på andra, och den här killen, som inte har någon syskon till sin rätt,

448
00:24:52,000 --> 00:24:54,000
har ingen sådan pil.

449
00:24:54,000 --> 00:24:56,000
Detta är i själva verket vad som kallas en länkad lista.

450
00:24:56,000 --> 00:25:00,000
Detta är en ny datastruktur som tillåter oss att avsätta en bit av minne,

451
00:25:00,000 --> 00:25:03,000
sedan en annan, sedan en annan, sedan en annan, helst vill vi

452
00:25:03,000 --> 00:25:07,000
under ett program, och vi komma ihåg att de är alla på något sätt relaterade

453
00:25:07,000 --> 00:25:11,000
genom att bokstavligen kedja ihop dem, och vi gjorde det bildmässigt här med en pil.

454
00:25:11,000 --> 00:25:15,000
Men i kod, vad skulle vara den mekanism genom vilken du kan på något sätt ansluta,

455
00:25:15,000 --> 00:25:20,000
nästan som Scratch, en bit till en annan bit?

456
00:25:20,000 --> 00:25:22,000
Vi skulle kunna använda en pekare, eller hur?

457
00:25:22,000 --> 00:25:25,000
Eftersom verkligen pilen som kommer från den övre vänstra torget,

458
00:25:25,000 --> 00:25:31,000
den här killen här här, kan innehålla inuti denna kvadrat

459
00:25:31,000 --> 00:25:34,000
inte bara vissa Ints, inte bara några röding, men vad händer om jag faktiskt tilldelade

460
00:25:34,000 --> 00:25:37,000
lite extra utrymme så att nu,

461
00:25:37,000 --> 00:25:41,000
alla mina bitar av minnet, även om detta kommer att kosta mig,

462
00:25:41,000 --> 00:25:45,000
nu ser lite mer rektangulärt där en av bitarna av minne

463
00:25:45,000 --> 00:25:47,000
används för ett antal, som nummer 1,

464
00:25:47,000 --> 00:25:50,000
och sedan om den här killen lagrar numret 2,

465
00:25:50,000 --> 00:25:52,000
denna andra bit av minnet används för en pil,

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

467
00:25:54,000 --> 00:25:59,000
Och jag antar att lagra numret 3 hit medan jag använder detta för att peka på att killen,

468
00:25:59,000 --> 00:26:02,000
och nu den här killen, låt oss anta att jag bara vill ha tre sådana bitar av minnet.

469
00:26:02,000 --> 00:26:05,000
Jag ska göra en linje genom att ange noll.

470
00:26:05,000 --> 00:26:07,000
Det finns ingen extra karaktär.

471
00:26:07,000 --> 00:26:10,000
>> I själva verket är det så att vi kan gå till väga för att genomföra

472
00:26:10,000 --> 00:26:12,000
något som kallas en länkad lista.

473
00:26:12,000 --> 00:26:18,000
En länkad lista är en ny datastruktur, och det är en språngbräda mot

474
00:26:18,000 --> 00:26:21,000
mycket snyggare datastrukturer som börjar att lösa problem

475
00:26:21,000 --> 00:26:23,000
i linje med Facebook-typ problem och Google-typ problem

476
00:26:23,000 --> 00:26:26,000
där du har stora datamängder, och det inte längre skär den

477
00:26:26,000 --> 00:26:29,000
att lagra allt intill varandra och använda något som linjär sökning

478
00:26:29,000 --> 00:26:31,000
eller ens något liknande binär sökning.

479
00:26:31,000 --> 00:26:33,000
Du vill ännu bättre gångtider.

480
00:26:33,000 --> 00:26:37,000
I själva verket en av de heliga Grails vi pratar om senare i veckan eller nästa

481
00:26:37,000 --> 00:26:41,000
är en algoritm vars speltid är konstant.

482
00:26:41,000 --> 00:26:44,000
Med andra ord tar det alltid samma tid oavsett

483
00:26:44,000 --> 00:26:47,000
hur stor ingången är, och det skulle verkligen vara övertygande,

484
00:26:47,000 --> 00:26:49,000
ännu mer än något logaritmisk.

485
00:26:49,000 --> 00:26:51,000
Vad är det här på skärmen här?

486
00:26:51,000 --> 00:26:55,000
Var och en av rektanglarna är precis vad jag drog för hand.

487
00:26:55,000 --> 00:26:59,000
Men det hela vägen till vänster är en speciell variabel.

488
00:26:59,000 --> 00:27:02,000
Det kommer att vara en enda pekare eftersom en gotcha

489
00:27:02,000 --> 00:27:04,000
med en länkad lista, eftersom dessa saker kallas,

490
00:27:04,000 --> 00:27:09,000
är att du måste hänga på en ände av den länkade listan.

491
00:27:09,000 --> 00:27:13,000
>> Precis som med en sträng, måste du veta adressen till den första röding.

492
00:27:13,000 --> 00:27:15,000
Samma affär för länkade listor.

493
00:27:15,000 --> 00:27:19,000
Du måste veta adressen till den första bit av minnet

494
00:27:19,000 --> 00:27:25,000
eftersom därifrån kan du nå alla andra.

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

496
00:27:27,000 --> 00:27:30,000
Vilket pris betalar vi för denna mångsidighet av att ha en dynamisk

497
00:27:30,000 --> 00:27:34,000
betydande datastruktur som om vi någonsin behöver mer minne, fin,

498
00:27:34,000 --> 00:27:37,000
bara tilldela ett ytterligare stycke och dra en pekare från

499
00:27:37,000 --> 00:27:39,000
det gamla till det nya svansen på listan?

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

501
00:27:41,000 --> 00:27:43,000
[Student] Det tar ungefär dubbelt så mycket utrymme.

502
00:27:43,000 --> 00:27:45,000
Det tar dubbelt så mycket plats, så det är definitivt en nackdel, och vi har sett det här

503
00:27:45,000 --> 00:27:48,000
avvägning innan mellan tid och rum och flexibilitet

504
00:27:48,000 --> 00:27:51,000
där vid det här laget, vi behöver inte 32 bitar för var och en av dessa nummer.

505
00:27:51,000 --> 00:27:57,000
Vi behöver verkligen 64, 32 för antalet och 32 för pekaren.

506
00:27:57,000 --> 00:27:59,000
Men hey, jag har 2 gigabyte RAM-minne.

507
00:27:59,000 --> 00:28:02,000
Lägga till en annan 32 bitar här och här verkar inte som stor grej.

508
00:28:02,000 --> 00:28:05,000
Men för stora datamängder, lägger det definitivt till bokstavligen dubbelt så mycket.

509
00:28:05,000 --> 00:28:09,000
Vad är en annan nackdel nu, eller vad har vi ger upp,

510
00:28:09,000 --> 00:28:12,000
Om vi ​​representerar listor med saker med en länkad lista och inte en array?

511
00:28:12,000 --> 00:28:14,000
[Student] Du kan inte korsa den bakåt.

512
00:28:14,000 --> 00:28:16,000
Du kan inte korsa den bakåt, så du är typ av skruvade om du går

513
00:28:16,000 --> 00:28:19,000
från vänster till höger med en for-slinga eller en while-slinga

514
00:28:19,000 --> 00:28:21,000
och då inser du, "Åh, jag vill gå tillbaka till början av listan."

515
00:28:21,000 --> 00:28:26,000
Du kan inte eftersom dessa tips bara gå från vänster till höger som pilarna visar.

516
00:28:26,000 --> 00:28:29,000
>> Nu kan du komma ihåg början av listan med en annan variabel,

517
00:28:29,000 --> 00:28:31,000
men det är en komplicerad att tänka på.

518
00:28:31,000 --> 00:28:35,000
En array, oavsett hur långt du går, du kan alltid göra minus, minus, minus, minus

519
00:28:35,000 --> 00:28:37,000
och gå tillbaka varifrån du kom.

520
00:28:37,000 --> 00:28:40,000
Vad är en nackdel här? Ja.

521
00:28:40,000 --> 00:28:43,000
[Ohörbart elev fråga]

522
00:28:43,000 --> 00:28:47,000
Du kan, så du har faktiskt just föreslagit en datastruktur som kallas en dubbelt länkad lista,

523
00:28:47,000 --> 00:28:50,000
och faktiskt, skulle du lägga till ytterligare pekare till var och en av dessa rektanglar

524
00:28:50,000 --> 00:28:53,000
som går åt andra hållet, uppsidan som

525
00:28:53,000 --> 00:28:55,000
Nu kan du färdas fram och tillbaka,

526
00:28:55,000 --> 00:28:59,000
Nackdelen som nu du använder tre gånger så mycket minne som vi brukade

527
00:28:59,000 --> 00:29:04,000
och även lägga komplexitet när det gäller den kod du måste skriva för att få det rätt.

528
00:29:04,000 --> 00:29:08,000
Men dessa är alla kanske mycket rimliga kompromisser, om återföring är viktigare.

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

530
00:29:10,000 --> 00:29:12,000
[Student] Du kan inte heller ha en 2D länkad lista.

531
00:29:12,000 --> 00:29:16,000
Bra, kan man inte riktigt har en 2D länkad lista.

532
00:29:16,000 --> 00:29:18,000
Du kunde. Det är inte alls lika lätt som en matris.

533
00:29:18,000 --> 00:29:21,000
Som en array, du öppna konsolen, stängd fäste, öppen hållare, stängda hållare,

534
00:29:21,000 --> 00:29:23,000
och du får några 2-dimensionell struktur.

535
00:29:23,000 --> 00:29:26,000
Man kan genomföra en 2-dimensionell länkad lista

536
00:29:26,000 --> 00:29:29,000
om du gör tillägg som du föreslog-tredjedel pekare till var och en av dessa saker,

537
00:29:29,000 --> 00:29:34,000
och om du tänker på en annan lista kommer på dig 3D stil

538
00:29:34,000 --> 00:29:40,000
från skärmen för oss alla, vilket är bara en annan kedja av något slag.

539
00:29:40,000 --> 00:29:45,000
Vi kan göra det, men det är inte så enkelt som att skriva öppet fäste, hakparentes. Ja.

540
00:29:45,000 --> 00:29:48,000
[Ohörbart elev fråga]

541
00:29:48,000 --> 00:29:50,000
Bra, så detta är en riktig kicker.

542
00:29:50,000 --> 00:29:54,000
>> Dessa algoritmer som vi har pined över, liksom oh, binär sökning,

543
00:29:54,000 --> 00:29:57,000
kan du söka en rad siffror på tavlan

544
00:29:57,000 --> 00:30:01,000
eller en telefonbok så mycket snabbare om du använder söndra och härska

545
00:30:01,000 --> 00:30:05,000
och en binär sökalgoritm, men binärsökning krävs två antaganden.

546
00:30:05,000 --> 00:30:09,000
Ett, att uppgifterna sorterades.

547
00:30:09,000 --> 00:30:11,000
Nu kan vi hålla förmodligen detta sorteras,

548
00:30:11,000 --> 00:30:14,000
så kanske det inte är ett problem, men binär sökning förutsätts också

549
00:30:14,000 --> 00:30:18,000
att du hade direktåtkomst till listan över nummer,

550
00:30:18,000 --> 00:30:21,000
och en rad låter dig ha direktåtkomst och genom direktåtkomst,

551
00:30:21,000 --> 00:30:24,000
Jag menar om du är ges en rad, hur lång tid det tar dig

552
00:30:24,000 --> 00:30:26,000
för att komma till konsolen 0?

553
00:30:26,000 --> 00:30:29,000
En operation, du bara använda [0] och du har rätt där.

554
00:30:29,000 --> 00:30:33,000
Hur många steg tar det att komma till platsen 10?

555
00:30:33,000 --> 00:30:36,000
Ett steg går du bara till [10] och du är där.

556
00:30:36,000 --> 00:30:40,000
Däremot, hur du kommer till den 10: e heltal i en länkad lista?

557
00:30:40,000 --> 00:30:42,000
Du måste börja från början eftersom du bara komma ihåg

558
00:30:42,000 --> 00:30:45,000
början på en länkad lista, precis som en sträng bli ihågkommen

559
00:30:45,000 --> 00:30:48,000
av adressen dess första röding, och upptäcker att 10:e int

560
00:30:48,000 --> 00:30:53,000
eller att 10. tecken i en sträng, måste du söka i hela jävla sak.

561
00:30:53,000 --> 00:30:55,000
>> Återigen, vi löser inte alla våra problem.

562
00:30:55,000 --> 00:31:00,000
Vi inför nya, men det är beroende på vad du försöker att designa för.

563
00:31:00,000 --> 00:31:04,000
När det gäller genomförandet av detta kan vi låna en idé från den studerandes struktur.

564
00:31:04,000 --> 00:31:07,000
Syntaxen är mycket likt, förutom nu är tanken lite mer abstrakt

565
00:31:07,000 --> 00:31:09,000
än hus och namn och ID.

566
00:31:09,000 --> 00:31:13,000
Men jag föreslår att vi skulle kunna ha en datastruktur i C

567
00:31:13,000 --> 00:31:17,000
som kallas nod, som sista ordet på bilden antyder,

568
00:31:17,000 --> 00:31:21,000
inne i en nod och en nod är bara en generisk behållare i datavetenskap.

569
00:31:21,000 --> 00:31:25,000
Det är oftast ritas som en cirkel eller en kvadrat eller rektangel som vi har gjort.

570
00:31:25,000 --> 00:31:27,000
Och i denna datastruktur har vi en int, n,

571
00:31:27,000 --> 00:31:29,000
så det är numret jag vill lagra.

572
00:31:29,000 --> 00:31:36,000
Men vad är detta andra raden, struct nod * nästa?

573
00:31:36,000 --> 00:31:40,000
Varför är detta korrekt, eller vilken roll gör det här spelet,

574
00:31:40,000 --> 00:31:42,000
även om det är lite kryptisk vid första anblicken?

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

576
00:31:44,000 --> 00:31:46,000
[Ohörbart elev svar]

577
00:31:46,000 --> 00:31:50,000
Exakt, så * slags byte att det är en pekare av något slag.

578
00:31:50,000 --> 00:31:53,000
Namnet på denna pekare är godtyckligt nästa,

579
00:31:53,000 --> 00:32:00,000
men vi kunde ha kallat det något vi vill ha, men vad har detta pekare pekar på?

580
00:32:00,000 --> 00:32:03,000
[Student] En annan nod. >> Exakt, pekar den på en annan sådan nod.

581
00:32:03,000 --> 00:32:05,000
>> Nu är denna typ av en nyfikenhet av C.

582
00:32:05,000 --> 00:32:09,000
Minns att C läses av en kompilator uppifrån och ned, vänster till höger,

583
00:32:09,000 --> 00:32:13,000
vilket innebär att om-detta är lite annorlunda från vad vi gjorde med den studerande.

584
00:32:13,000 --> 00:32:16,000
När vi definierat en student, vi faktiskt inte lagt ett ord där.

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

586
00:32:18,000 --> 00:32:20,000
Sedan hade vi int id, string namn, string hus,

587
00:32:20,000 --> 00:32:23,000
och därefter student vid botten av struct.

588
00:32:23,000 --> 00:32:26,000
Denna förklaring är lite annorlunda eftersom,

589
00:32:26,000 --> 00:32:28,000
återigen är C-kompilator lite dum.

590
00:32:28,000 --> 00:32:30,000
Det är bara att gå att läsa uppifrån och ned,

591
00:32:30,000 --> 00:32:33,000
så om det når 2nd line här

592
00:32:33,000 --> 00:32:37,000
där nästa deklareras och det ser, oh, här är en variabel som heter nästa.

593
00:32:37,000 --> 00:32:39,000
Det är en pekare till en struct nod.

594
00:32:39,000 --> 00:32:42,000
Kompilatorn kommer att inse vad som är en struct nod?

595
00:32:42,000 --> 00:32:44,000
Jag har aldrig hört talas om denna sak innan,

596
00:32:44,000 --> 00:32:47,000
eftersom ordet nod inte annars visas

597
00:32:47,000 --> 00:32:49,000
tills botten, så det är denna redundans.

598
00:32:49,000 --> 00:32:53,000
Du måste säga struct nod här, som du sedan kan förkorta senare

599
00:32:53,000 --> 00:32:56,000
tack vare typedef här nere, men det beror

600
00:32:56,000 --> 00:33:02,000
Vi refererar till själva strukturen inuti strukturen.

601
00:33:02,000 --> 00:33:05,000
Det är en gotcha där.

602
00:33:05,000 --> 00:33:07,000
>> Några intressanta problem kommer att uppstå.

603
00:33:07,000 --> 00:33:09,000
Vi har en lista med tal. Hur sätter vi in ​​det?

604
00:33:09,000 --> 00:33:11,000
Hur söker vi det? Hur tar vi av det?

605
00:33:11,000 --> 00:33:13,000
Speciellt nu när vi har att hantera alla dessa tips.

606
00:33:13,000 --> 00:33:15,000
Du trodde pekare var typ av kluriga

607
00:33:15,000 --> 00:33:17,000
när du hade en av dem försöker bara läsa en int till det.

608
00:33:17,000 --> 00:33:20,000
Nu måste vi manipulera en hel lista är värt.

609
00:33:20,000 --> 00:33:22,000
Varför tar vi inte vårt 5-minuters paus här, och sedan kommer vi att

610
00:33:22,000 --> 00:33:34,000
Vissa folk upp på scenen för att göra just detta.

611
00:33:34,000 --> 00:33:36,000
>> C är mycket roligare när det är agerade ut.

612
00:33:36,000 --> 00:33:39,000
Vem skulle bokstavligen vilja vara först?

613
00:33:39,000 --> 00:33:41,000
Okej, kom upp. Du är först.

614
00:33:41,000 --> 00:33:44,000
Vem vill vara 9? Okej, 9.

615
00:33:44,000 --> 00:33:46,000
Vad sägs om 9? 17?

616
00:33:46,000 --> 00:33:51,000
Lite klicken här. 22 och 26 i den främre raden.

617
00:33:51,000 --> 00:33:53,000
Och sedan hur om någon där borta som pekade på.

618
00:33:53,000 --> 00:33:57,000
Du är 34. Okej, 34, kom upp.

619
00:33:57,000 --> 00:33:59,000
Först är borta. Okej, alla fyra av er.

620
00:33:59,000 --> 00:34:01,000
Och vem har vi säga 9?

621
00:34:01,000 --> 00:34:04,000
Vem är vår 9?

622
00:34:04,000 --> 00:34:07,000
Vem vill egentligen bli 9? Okej, kom igen, vara 9.

623
00:34:07,000 --> 00:34:10,000
Nu kör vi.

624
00:34:10,000 --> 00:34:13,000
34, vi träffas där.

625
00:34:13,000 --> 00:34:17,000
Den första delen är att göra er ser ut så.

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

627
00:34:21,000 --> 00:34:25,000
Om du kan stå åt sidan, eftersom vi kommer att minnesallokera dig om en stund.

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

629
00:34:29,000 --> 00:34:32,000
Okej, utmärkt, så låt oss ställa ett par frågor här.

630
00:34:32,000 --> 00:34:34,000
Och faktiskt, vad heter du? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, okej, kom hit.

632
00:34:37,000 --> 00:34:41,000
Anita kommer att hjälpa oss slags lösa ett ganska enkel fråga i första,

633
00:34:41,000 --> 00:34:44,000
vilket är hur du hittar om en värde i listan?

634
00:34:44,000 --> 00:34:48,000
Nu märker att först representeras här av Lucas,

635
00:34:48,000 --> 00:34:52,000
är lite annorlunda, och så hans papper är medvetet sidled

636
00:34:52,000 --> 00:34:55,000
eftersom det inte är riktigt lika lång och tar inte upp så många bitar,

637
00:34:55,000 --> 00:34:58,000
även om tekniskt han har samma pappersformat bara roteras.

638
00:34:58,000 --> 00:35:01,000
Men han är lite annorlunda eftersom han är bara 32 bitar för en pekare,

639
00:35:01,000 --> 00:35:05,000
och alla dessa killar är 64 bitar, varav hälften är antalet, varav hälften är en pekare.

640
00:35:05,000 --> 00:35:08,000
Men pekaren inte visas, så om ni kunde något tafatt

641
00:35:08,000 --> 00:35:12,000
använda din vänstra hand för att peka på personen bredvid dig.

642
00:35:12,000 --> 00:35:14,000
Och du är nummer 34. Vad heter du?

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

644
00:35:16,000 --> 00:35:19,000
Ari, så egentligen håller papperet i höger hand och vänster hand går rakt ner.

645
00:35:19,000 --> 00:35:21,000
Du representerar null till vänster.

646
00:35:21,000 --> 00:35:24,000
>> Nu vår mänskliga bilden är mycket konsekvent.

647
00:35:24,000 --> 00:35:26,000
Detta är faktiskt hur pekare fungerar.

648
00:35:26,000 --> 00:35:29,000
Och om du kan krama lite här sättet så jag är inte i vägen.

649
00:35:29,000 --> 00:35:34,000
Anita här, hitta mig numret 22,

650
00:35:34,000 --> 00:35:40,000
men antar en begränsning av att inte människor håller upp bitar av papper,

651
00:35:40,000 --> 00:35:43,000
men detta är en lista, och du har bara Lucas att börja med

652
00:35:43,000 --> 00:35:46,000
eftersom han är bokstavligen den första pekaren.

653
00:35:46,000 --> 00:35:51,000
Anta att du själv är en pekare, och så du också har möjlighet att peka på något.

654
00:35:51,000 --> 00:35:56,000
Varför inte du börja med att peka på exakt vad Lucas pekar på?

655
00:35:56,000 --> 00:35:58,000
Bra, och låt mig att göra den här ut över här.

656
00:35:58,000 --> 00:36:04,000
Bara för diskussionens skull, låt mig dra upp en tom sida här.

657
00:36:04,000 --> 00:36:06,000
Hur stavar du ditt namn? >> Anita.

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

659
00:36:08,000 --> 00:36:18,000
Låt oss säga nod * anita = Lucas.

660
00:36:18,000 --> 00:36:22,000
Tja, ska vi kalla dig inte Lucas. Vi borde ringa dig först.

661
00:36:22,000 --> 00:36:25,000
Varför är det i själva verket överensstämmer med verkligheten här?

662
00:36:25,000 --> 00:36:27,000
En första redan existerar.

663
00:36:27,000 --> 00:36:30,000
Först har tilldelats förmodligen någonstans här uppe.

664
00:36:30,000 --> 00:36:35,000
Nod * först, och det har tilldelats en lista på något sätt.

665
00:36:35,000 --> 00:36:37,000
Jag vet inte hur det hände. Det hände innan klassen började.

666
00:36:37,000 --> 00:36:40,000
Denna länkade lista av människor har skapats.

667
00:36:40,000 --> 00:36:44,000
Och nu vid denna punkt i berättelsen, det är allt som händer Facebook tydligen senare

668
00:36:44,000 --> 00:36:49,000
vid denna punkt i berättelsen, har Anita initierats vara lika med första,

669
00:36:49,000 --> 00:36:51,000
vilket inte betyder att Anita pekar på Lucas.

670
00:36:51,000 --> 00:36:53,000
Snarare pekar hon på vad han pekar på

671
00:36:53,000 --> 00:36:57,000
eftersom samma adress som är inne i Lucas 32 bitar - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
är nu också inne i Anitas 32 bitar - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Nu hitta 22. Hur skulle du gå om att göra detta?

674
00:37:05,000 --> 00:37:07,000
Vad är det? >> Peka på vad som helst.

675
00:37:07,000 --> 00:37:11,000
Peka på vad som helst, så gå vidare och agera ut det så gott du kan här.

676
00:37:11,000 --> 00:37:15,000
Bra, bra, och nu är du pekar på, vad heter du med 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, så Ramon håller upp 22.

678
00:37:18,000 --> 00:37:20,000
Du har nu gjort en check.

679
00:37:20,000 --> 00:37:24,000
Har Ramon == 22, och i så fall till exempel kan vi återvända sant.

680
00:37:24,000 --> 00:37:26,000
Låt mig-när dessa killar står här något tafatt-

681
00:37:26,000 --> 00:37:32,000
Låt mig göra något snabbt som bool hitta.

682
00:37:32,000 --> 00:37:37,000
Jag ska gå vidare och säga (nod * lista, int n).

683
00:37:37,000 --> 00:37:39,000
Jag kommer strax tillbaka med er. Jag måste bara skriva lite kod.

684
00:37:39,000 --> 00:37:45,000
Och nu ska jag gå vidare och göra det nod * anita = lista.

685
00:37:45,000 --> 00:37:51,000
Och jag kommer att gå vidare och säga medan (Anita! = Null).

686
00:37:51,000 --> 00:37:57,000
>> Metaforen här blir lite utsträckt, men medan (Anita! = Null), vad jag vill göra?

687
00:37:57,000 --> 00:38:03,000
Jag behöver något sätt referera

688
00:38:03,000 --> 00:38:05,000
heltalet som Anita pekar på.

689
00:38:05,000 --> 00:38:08,000
I det förflutna, när vi hade strukturer som en nod är,

690
00:38:08,000 --> 00:38:11,000
Vi använde punktnotation, och vi skulle säga något i stil med

691
00:38:11,000 --> 00:38:15,000
anita.n, men problemet här är att Anita är inte en struktur i sig.

692
00:38:15,000 --> 00:38:17,000
Vad är hon?

693
00:38:17,000 --> 00:38:21,000
Hon är en pekare, så egentligen, om vi vill använda denna punktnotation-

694
00:38:21,000 --> 00:38:23,000
och detta kommer att se medvetet lite kryptiskt-

695
00:38:23,000 --> 00:38:28,000
vi måste göra något liknande gå till valfri Anitas vänstra hand pekar på

696
00:38:28,000 --> 00:38:31,000
och sedan få fältet kallas n.

697
00:38:31,000 --> 00:38:35,000
Anita är en pekare, men vad är * Anita?

698
00:38:35,000 --> 00:38:38,000
Vad tycker du när du går till vad Anita pekar på?

699
00:38:38,000 --> 00:38:42,000
En struct, en nod och en nod, återkallande, har ett fält som heter N

700
00:38:42,000 --> 00:38:47,000
eftersom det har, minns dessa 2 områden, Nästa och n,

701
00:38:47,000 --> 00:38:50,000
att vi såg för en stund sedan här.

702
00:38:50,000 --> 00:38:53,000
>> För att verkligen efterlikna detta i kod,

703
00:38:53,000 --> 00:39:02,000
vi kunde göra detta och säga om ((* anita). n == n), n som jag letar efter.

704
00:39:02,000 --> 00:39:04,000
Observera att funktionen antogs i antalet jag bryr mig om.

705
00:39:04,000 --> 00:39:10,000
Då kan jag gå vidare och göra något liknande avkastning sant.

706
00:39:10,000 --> 00:39:12,000
Annars, om det inte är fallet, vad jag vill göra?

707
00:39:12,000 --> 00:39:19,000
Hur översätter jag att koda vad Anita gjorde så intuitivt genom att gå igenom listan?

708
00:39:19,000 --> 00:39:26,000
Vad ska jag göra här uppe för att simulera Anita ta det steget till vänster, som steg till vänster?

709
00:39:26,000 --> 00:39:28,000
[Ohörbart elev svar] >> Vad är det?

710
00:39:28,000 --> 00:39:30,000
[Ohörbart elev svar]

711
00:39:30,000 --> 00:39:34,000
Bra, inte en dålig idé, men i det förflutna, när vi har gjort detta, har vi gjort anita + +

712
00:39:34,000 --> 00:39:37,000
eftersom det skulle lägga till numret 1 till Anita,

713
00:39:37,000 --> 00:39:40,000
som normalt skulle peka på nästa person, som Ramon,

714
00:39:40,000 --> 00:39:44,000
eller den person bredvid honom, eller bredvid honom personen ner linjen.

715
00:39:44,000 --> 00:39:49,000
Men det är inte riktigt bra här eftersom vad den här saken ser ut i minnet?

716
00:39:49,000 --> 00:39:54,000
Inte det. Vi måste inaktivera det.

717
00:39:54,000 --> 00:40:00,000
Det ser ut så här i minnet, och även om jag har ritat 1 och 2 och 3 nära varandra,

718
00:40:00,000 --> 00:40:03,000
om vi verkligen simulera detta-Kan ni, samtidigt pekar på samma människor,

719
00:40:03,000 --> 00:40:07,000
kan några av er tar en slumpmässig steg tillbaka, vissa av er en slumpmässig steg framåt?

720
00:40:07,000 --> 00:40:10,000
>> Denna röran är fortfarande en länkad lista,

721
00:40:10,000 --> 00:40:13,000
men dessa killar kunde vara var som helst i minnet,

722
00:40:13,000 --> 00:40:15,000
så anita + + inte kommer att fungera varför?

723
00:40:15,000 --> 00:40:19,000
Vad är på plats anita + +?

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

725
00:40:21,000 --> 00:40:24,000
Det är något annat värde som bara så råkar vara placerad

726
00:40:24,000 --> 00:40:28,000
bland alla dessa noder av en slump eftersom vi inte använder en matris.

727
00:40:28,000 --> 00:40:30,000
Vi tilldelades en av dessa noder individuellt.

728
00:40:30,000 --> 00:40:32,000
Okej, om ni kan rensa er tillbaka.

729
00:40:32,000 --> 00:40:37,000
Låt mig föreslå att istället för anita + +, vi istället gör anita får-

730
00:40:37,000 --> 00:40:42,000
Tja, varför inte vi gå till vad Anita pekar på och sedan göra. härnäst?

731
00:40:42,000 --> 00:40:45,000
Med andra ord går vi till Ramon, vem håller numret 22,

732
00:40:45,000 --> 00:40:51,000
och då. nästa är som om Anita skulle kopiera sin vänstra hand pekare.

733
00:40:51,000 --> 00:40:54,000
Men hon skulle inte gå längre än Ramon eftersom vi hittade 22.

734
00:40:54,000 --> 00:40:56,000
Men det skulle vara idén. Nu är detta en god-awful röra.

735
00:40:56,000 --> 00:40:59,000
Ärligt talat, ingen kommer ihåg någonsin här syntaxen, och så tack och lov,

736
00:40:59,000 --> 00:41:04,000
Det är faktiskt lite medvetet-Åh, har du faktiskt inte se vad jag skrev.

737
00:41:04,000 --> 00:41:08,000
Detta skulle vara mer övertygande om du kunde. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Bakom kulisserna, jag lösa problemet på detta sätt.

739
00:41:10,000 --> 00:41:14,000
Anita, att ta detta steg till vänster,

740
00:41:14,000 --> 00:41:18,000
Först går vi till den adress som Anita pekar på

741
00:41:18,000 --> 00:41:23,000
och där hon kommer att hitta inte bara n, som vi bara kontrolleras för jämförelse skull,

742
00:41:23,000 --> 00:41:25,000
men du hittar också nästa - i detta fall,

743
00:41:25,000 --> 00:41:28,000
Ramons vänstra hand pekar till nästa nod i listan.

744
00:41:28,000 --> 00:41:32,000
Men detta är den god-awful röra som jag hänvisade till tidigare,

745
00:41:32,000 --> 00:41:34,000
men det visar sig C låter oss förenkla detta.

746
00:41:34,000 --> 00:41:40,000
Istället för att skriva (* anita), kan vi istället bara skriva anita-> n,

747
00:41:40,000 --> 00:41:45,000
och det är exakt samma sak funktionellt, men det är mycket mer intuitivt,

748
00:41:45,000 --> 00:41:48,000
och det är mycket mer överens med den bild som vi har ritning

749
00:41:48,000 --> 00:41:50,000
all denna tid med pilar.

750
00:41:50,000 --> 00:41:57,000
>> Slutligen, vad vi behöver göra i slutet av detta program?

751
00:41:57,000 --> 00:42:00,000
Det finns en rad kod kvar.

752
00:42:00,000 --> 00:42:02,000
Återgå vad?

753
00:42:02,000 --> 00:42:05,000
Falskt, för om vi får igenom hela while-slingan

754
00:42:05,000 --> 00:42:10,000
och Anita är i själva verket noll betyder att hon gick hela vägen till slutet av listan

755
00:42:10,000 --> 00:42:12,000
där hon pekar på, vad heter du nu igen?

756
00:42:12,000 --> 00:42:15,000
Ari. >> Aris vänster hand, vilket är null.

757
00:42:15,000 --> 00:42:18,000
Anita är nu noll, och jag inser du bara står här tafatt i limbo

758
00:42:18,000 --> 00:42:21,000
eftersom jag ska iväg på en monolog här,

759
00:42:21,000 --> 00:42:23,000
men vi engagera dig igen på bara ett ögonblick.

760
00:42:23,000 --> 00:42:27,000
Anita är noll vid denna punkt i berättelsen, så while-slingan avslutas,

761
00:42:27,000 --> 00:42:30,000
och vi måste returnera false för om hon fick hela vägen till Aris null-pekare

762
00:42:30,000 --> 00:42:34,000
då fanns det ingen nummer som hon sökte i listan.

763
00:42:34,000 --> 00:42:39,000
Vi kan städa upp det här också, men det är en ganska bra genomförande sedan

764
00:42:39,000 --> 00:42:43,000
en traversering funktion en sökning funktion för en länkad lista.

765
00:42:43,000 --> 00:42:48,000
Det är fortfarande linjär sökning, men det är inte så enkelt som + + en pekare

766
00:42:48,000 --> 00:42:52,000
eller + + en i variabel för nu kan vi inte gissa

767
00:42:52,000 --> 00:42:54,000
där var och en av dessa noder är i minnet.

768
00:42:54,000 --> 00:42:57,000
Vi måste bokstavligen följa spår av brödsmulor eller, mer specifikt,

769
00:42:57,000 --> 00:43:00,000
pekare, att ta sig från en nod till en annan.

770
00:43:00,000 --> 00:43:02,000
>> Nu ska vi prova en annan. Anita, vill du komma tillbaka hit?

771
00:43:02,000 --> 00:43:06,000
Varför inte vi gå vidare och fördela en annan person från publiken?

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

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca har malloced från publiken,

774
00:43:10,000 --> 00:43:13,000
och hon nu lagra antalet 55.

775
00:43:13,000 --> 00:43:17,000
Och målet till hands är nu Anita att infoga

776
00:43:17,000 --> 00:43:22,000
Rebecca in den länkade listan här i sitt rätta ställe.

777
00:43:22,000 --> 00:43:24,000
Kom hit för en stund.

778
00:43:24,000 --> 00:43:28,000
Jag har gjort något liknande.

779
00:43:28,000 --> 00:43:32,000
Jag har gjort nod *. Och vad heter du nu igen?

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

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

782
00:43:41,000 --> 00:43:44,000
Precis som vi har tilldelats saker som studenter och allt i det förflutna,

783
00:43:44,000 --> 00:43:46,000
Vi behöver storleken på noden, så nu Rebecca

784
00:43:46,000 --> 00:43:49,000
pekar på vad?

785
00:43:49,000 --> 00:43:52,000
Rebecca har två fält inuti henne, varav en är 55.

786
00:43:52,000 --> 00:43:55,000
Låt oss göra vad, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Men sedan rebecca-> nästa bör-liknande just nu, är hennes hand slags vem vet?

788
00:44:00,000 --> 00:44:03,000
Det pekar på några sopor värde, så varför inte för bra åtgärd

789
00:44:03,000 --> 00:44:07,000
vi åtminstone gör detta så att vänster hand är nu vid hennes sida.

790
00:44:07,000 --> 00:44:09,000
Nu Anita, ta det härifrån.

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

792
00:44:11,000 --> 00:44:20,000
Gå vidare och hitta där vi ska lägga Rebecca.

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

794
00:44:25,000 --> 00:44:28,000
Okej, bra, och nu behöver vi dig att lämna lite riktning,

795
00:44:28,000 --> 00:44:30,000
så du har nått Ari.

796
00:44:30,000 --> 00:44:33,000
Hans vänstra arm är null, men Rebecca klart tillhör höger,

797
00:44:33,000 --> 00:44:36,000
så hur har vi att ändra detta länkad lista

798
00:44:36,000 --> 00:44:38,000
För att sätta Rebecca i lämpligt ställe?

799
00:44:38,000 --> 00:44:42,000
Om du kunde bokstavligen flytta folks vänster hand runt efter behov,

800
00:44:42,000 --> 00:44:48,000
vi åtgärda problemet på det sättet.

801
00:44:48,000 --> 00:44:52,000
Okej, bra, och under tiden är Rebecca vänstra hand nu vid hennes sida.

802
00:44:52,000 --> 00:44:54,000
>> Det var för lätt.

803
00:44:54,000 --> 00:44:57,000
Låt oss försöka fördela-Vi nästan klar, 20.

804
00:44:57,000 --> 00:44:59,000
Okej, kom upp.

805
00:44:59,000 --> 00:45:04,000
20 har tilldelats, så låt mig gå vidare och säga igen här

806
00:45:04,000 --> 00:45:07,000
Vi har precis gjort Saad nod *.

807
00:45:07,000 --> 00:45:11,000
Vi har malloc (sizeof (nod)).

808
00:45:11,000 --> 00:45:16,000
Vi gör då exakt samma syntax som vi gjorde tidigare under 20,

809
00:45:16,000 --> 00:45:20,000
och jag ska göra härnäst = NULL, och nu är det upp till Anita

810
00:45:20,000 --> 00:45:23,000
att infoga dig i den länkade listan, om du kunde spela exakt samma roll.

811
00:45:23,000 --> 00:45:30,000
Utför.

812
00:45:30,000 --> 00:45:32,000
Okej, bra.

813
00:45:32,000 --> 00:45:38,000
Nu tänker noga innan du börjar flytta vänster hand runt.

814
00:45:38,000 --> 00:45:46,000
Du särklass fick mest obekväma rollen idag.

815
00:45:46,000 --> 00:45:59,000
Vems handen bör flyttas 1:a?

816
00:45:59,000 --> 00:46:02,000
Okej, vänta, jag hör lite nej-talet.

817
00:46:02,000 --> 00:46:07,000
Om vissa människor skulle artigt vilja hjälpa till att lösa en besvärlig situation här.

818
00:46:07,000 --> 00:46:11,000
Vems vänster bör uppdateras 1. Kanske? Ja.

819
00:46:11,000 --> 00:46:13,000
[Student] Saad s.

820
00:46:13,000 --> 00:46:15,000
Okej, Saad-talet, varför då?

821
00:46:15,000 --> 00:46:17,000
[Ohörbart elev svar]

822
00:46:17,000 --> 00:46:19,000
Bra, för om vi flyttar-Vad heter du? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, om vi flyttar sin hand först ner till noll,

824
00:46:22,000 --> 00:46:25,000
nu har vi bokstavligen föräldralösa fyra personer i den här listan

825
00:46:25,000 --> 00:46:29,000
eftersom han var den enda som pekar på Ramon och alla till vänster,

826
00:46:29,000 --> 00:46:31,000
så uppdaterar att pekaren första var dåligt.

827
00:46:31,000 --> 00:46:33,000
Låt oss ångra det.

828
00:46:33,000 --> 00:46:37,000
Bra, och nu gå vidare och flytta lämpliga vänstra pekar på Ramon.

829
00:46:37,000 --> 00:46:39,000
Detta känns lite överflödigt.

830
00:46:39,000 --> 00:46:41,000
Nu finns det två personer som pekar på Ramon, men det är bra

831
00:46:41,000 --> 00:46:43,000
för nu hur annars ska uppdaterar vi listan?

832
00:46:43,000 --> 00:46:48,000
Vilka andra sidan måste flytta?

833
00:46:48,000 --> 00:46:53,000
Utmärkt, nu har vi förlorat något minne?

834
00:46:53,000 --> 00:46:57,000
Nej, så bra, låt oss se om vi inte kan bryta denna gång.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing en sista gång, nummer 5.

836
00:47:00,000 --> 00:47:04,000
Hela vägen i ryggen, kom ner.

837
00:47:04,000 --> 00:47:08,000
Det är väldigt spännande.

838
00:47:08,000 --> 00:47:15,000
[Applåder]

839
00:47:15,000 --> 00:47:17,000
Vad heter du? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, okej, du malloced som nummer 5.

841
00:47:19,000 --> 00:47:23,000
Vi har precis avrättades kod som är nästan identiska med dem

842
00:47:23,000 --> 00:47:26,000
med bara ett annat namn.

843
00:47:26,000 --> 00:47:28,000
Utmärkt.

844
00:47:28,000 --> 00:47:38,000
Nu, Anita, lycka sätta nummer 5 i listan nu.

845
00:47:38,000 --> 00:47:43,000
Bra, och?

846
00:47:43,000 --> 00:47:47,000
Utmärkt, så detta är verkligen den tredje av tre totalt fall.

847
00:47:47,000 --> 00:47:49,000
Först hade vi någon på slutet, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Vi hade sedan någon i mitten.

849
00:47:51,000 --> 00:47:53,000
Nu har vi någon början, och i detta exempel,

850
00:47:53,000 --> 00:47:56,000
Vi hade nu för att uppdatera Lucas för första gången

851
00:47:56,000 --> 00:48:00,000
eftersom det första elementet i listan nu att peka på en ny nod,

852
00:48:00,000 --> 00:48:03,000
som, i sin tur, pekar på nodnummer 9.

853
00:48:03,000 --> 00:48:06,000
>> Detta var en enormt pinsamt demonstration, jag är säker,

854
00:48:06,000 --> 00:48:08,000
så en stor applåd för dessa killar om du kunde.

855
00:48:08,000 --> 00:48:11,000
Snyggt gjort.

856
00:48:11,000 --> 00:48:17,000
Det är allt. Du kan hålla dina lappar som en liten minne.

857
00:48:17,000 --> 00:48:22,000
Det visar sig att göra detta i kod

858
00:48:22,000 --> 00:48:26,000
är inte riktigt så enkelt som att bara flytta händerna runt

859
00:48:26,000 --> 00:48:28,000
och pekar pekare på olika saker.

860
00:48:28,000 --> 00:48:31,000
Men inser att när det blir dags att genomföra något liknande

861
00:48:31,000 --> 00:48:34,000
en länkad lista eller en variant av det om du fokuserar på riktigt

862
00:48:34,000 --> 00:48:38,000
dessa grundläggande fundamenta, de lagom stora problem jag har att räkna ut,

863
00:48:38,000 --> 00:48:43,000
Det är denna hand eller denna hand, inse att det är annars ett ganska komplext program

864
00:48:43,000 --> 00:48:47,000
kan i själva verket reduceras till ganska enkla byggstenar som denna.

865
00:48:47,000 --> 00:48:51,000
>> Låt oss ta det i en mer sofistikerad riktning fortfarande.

866
00:48:51,000 --> 00:48:53,000
Vi har nu begreppet den länkade listan.

867
00:48:53,000 --> 00:48:57,000
Vi har också-tack vare förslaget tillbaka dit-en dubbelt länkad lista,

868
00:48:57,000 --> 00:49:01,000
som ser nästan samma, men nu har vi två pekare inuti struct

869
00:49:01,000 --> 00:49:05,000
istället för en, och vi skulle förmodligen kalla dem pekare föregående och nästa

870
00:49:05,000 --> 00:49:08,000
eller till vänster eller höger, men vi i själva verket behöver två av dem.

871
00:49:08,000 --> 00:49:10,000
Koden skulle vara lite mer delaktiga.

872
00:49:10,000 --> 00:49:12,000
Anita skulle ha haft att göra mer arbete här på scenen.

873
00:49:12,000 --> 00:49:15,000
Men vi kan säkert genomföra denna typ av struktur.

874
00:49:15,000 --> 00:49:19,000
När det gäller körtid, men vad skulle vara gångtid

875
00:49:19,000 --> 00:49:24,000
för Anita att hitta ett nummer n i en länkad lista nu?

876
00:49:24,000 --> 00:49:27,000
Fortfarande stora O n, så det är inte bättre än linjär sökning.

877
00:49:27,000 --> 00:49:29,000
Vi kan inte göra binär sökning, men, igen.

878
00:49:29,000 --> 00:49:34,000
Varför var det så? Du kan inte hoppa runt.

879
00:49:34,000 --> 00:49:36,000
Även om vi ser naturligtvis alla människor på scenen,

880
00:49:36,000 --> 00:49:39,000
och Anita kunde ha eyeballed det och sade: "Här är mitt listan"

881
00:49:39,000 --> 00:49:42,000
Hon skulle inte veta att om hon var datorprogrammet

882
00:49:42,000 --> 00:49:47,000
eftersom det enda hon hade att haka på i början av scenariot

883
00:49:47,000 --> 00:49:50,000
var Lucas, som var den första pekaren.

884
00:49:50,000 --> 00:49:53,000
Hon skulle med nödvändighet måste följa dessa länkar,

885
00:49:53,000 --> 00:49:56,000
räkna sig fram tills hon hittade ungefär mitten,

886
00:49:56,000 --> 00:49:58,000
och även då, hon kommer inte att veta när hon nått mitten

887
00:49:58,000 --> 00:50:01,000
om hon inte går hela vägen till slutet för att räkna ut hur många det finns,

888
00:50:01,000 --> 00:50:05,000
sedan Backtracks, och det också skulle vara svårt om du inte hade

889
00:50:05,000 --> 00:50:07,000
en dubbelt länkad lista av något slag.

890
00:50:07,000 --> 00:50:10,000
>> Lösa problem i dag, men inför andra.

891
00:50:10,000 --> 00:50:12,000
Vad sägs om en annorlunda datastruktur helt och hållet?

892
00:50:12,000 --> 00:50:15,000
Detta är ett fotografi av brickorna i Mather House,

893
00:50:15,000 --> 00:50:19,000
och i detta fall har vi en datastruktur vi också typ av redan pratat om.

894
00:50:19,000 --> 00:50:22,000
Vi pratade om en stack i samband med minnet,

895
00:50:22,000 --> 00:50:26,000
och det är typ av avsiktligt namn eftersom en stapel i termer av minne

896
00:50:26,000 --> 00:50:31,000
är effektivt en datastruktur som har mer och mer saker skiktades ovanpå den.

897
00:50:31,000 --> 00:50:35,000
Men det intressanta med en stapel, såsom är fallet i verkligheten,

898
00:50:35,000 --> 00:50:38,000
är att det är en speciell typ av datastruktur.

899
00:50:38,000 --> 00:50:42,000
Det är en datastruktur där det första elementet i

900
00:50:42,000 --> 00:50:46,000
är det sista elementet ut.

901
00:50:46,000 --> 00:50:50,000
Om du är den första brickan sättas på stacken,

902
00:50:50,000 --> 00:50:53,000
du kommer att bli tyvärr den sista brickan tas bort bunten,

903
00:50:53,000 --> 00:50:55,000
och det är inte nödvändigtvis en bra sak.

904
00:50:55,000 --> 00:50:58,000
Omvänt kan man tänka på det tvärtom,

905
00:50:58,000 --> 00:51:02,000
den sista i den första ut.

906
00:51:02,000 --> 00:51:05,000
>> Nu behöver alla scenarier kommer att tänka där med en bunt

907
00:51:05,000 --> 00:51:08,000
datastruktur där du har den egenskapen

908
00:51:08,000 --> 00:51:13,000
den sista in, först ut, är faktiskt övertygande?

909
00:51:13,000 --> 00:51:16,000
Är det bra? Är det en dålig sak?

910
00:51:16,000 --> 00:51:19,000
Det är definitivt en dålig sak om magasinen var inte alla identiska

911
00:51:19,000 --> 00:51:21,000
och de var alla särskilda färger eller whatnot,

912
00:51:21,000 --> 00:51:24,000
och den färg du vill ha hela vägen längst ner.

913
00:51:24,000 --> 00:51:26,000
Naturligtvis kan du inte få det utan stor ansträngning.

914
00:51:26,000 --> 00:51:28,000
Du måste börja från toppen och arbeta dig nedåt.

915
00:51:28,000 --> 00:51:31,000
Likaså, vad händer om du var en av dessa fläkt pojkar

916
00:51:31,000 --> 00:51:34,000
som väntar uppe hela natten att försöka få en iPhone och linjer upp

917
00:51:34,000 --> 00:51:36,000
på en plats som denna?

918
00:51:36,000 --> 00:51:40,000
Skulle det inte vara trevligt om Apple Store

919
00:51:40,000 --> 00:51:42,000
var en stapel datastruktur?

920
00:51:42,000 --> 00:51:44,000
Yay? Nej?

921
00:51:44,000 --> 00:51:47,000
Det är bara bra för de människor som dyker upp i sista möjliga minuten

922
00:51:47,000 --> 00:51:50,000
och sedan få plockas bort kön.

923
00:51:50,000 --> 00:51:52,000
Och i själva verket på att jag var så benägen att säga kö

924
00:51:52,000 --> 00:51:56,000
är faktiskt överens med vad vi skulle kalla den här typen av datastruktur,

925
00:51:56,000 --> 00:51:59,000
en i verkligheten där ordern spelar roll,

926
00:51:59,000 --> 00:52:02,000
och du vill att den första i att vara först ut

927
00:52:02,000 --> 00:52:04,000
om så bara för sakens skull mänskliga rättvisa.

928
00:52:04,000 --> 00:52:07,000
Vi kommer i allmänhet kalla det en kö datastruktur.

929
00:52:07,000 --> 00:52:11,000
>> Det visar sig dessutom länkade listor, kan vi börja använda samma grundläggande idéer

930
00:52:11,000 --> 00:52:15,000
och börja skapa nya och olika typer av lösningar på problem.

931
00:52:15,000 --> 00:52:19,000
Till exempel, i fallet med en stapel, kan vi representera en stapel

932
00:52:19,000 --> 00:52:22,000
med hjälp av en datastruktur som denna, skulle jag föreslå.

933
00:52:22,000 --> 00:52:26,000
I det här fallet har jag deklarerat en struktur, och jag har sagt inuti denna struktur

934
00:52:26,000 --> 00:52:30,000
är en matris med tal, och sedan en variabel som kallas storlek,

935
00:52:30,000 --> 00:52:33,000
och jag kommer att kalla denna sak en skorsten.

936
00:52:33,000 --> 00:52:35,000
Nu, varför det fungerar egentligen?

937
00:52:35,000 --> 00:52:43,000
I fallet med en stapel, kan jag dra detta effektivt på skärmen som en matris.

938
00:52:43,000 --> 00:52:47,000
Här är min stack. De är mina nummer.

939
00:52:47,000 --> 00:52:50,000
Och vi kommer att dra dem som denna, det, detta, detta, detta.

940
00:52:50,000 --> 00:52:53,000
Och så har jag några andra uppgifter medlem här,

941
00:52:53,000 --> 00:52:58,000
som kallas storlek, så detta är storleken, och det är tal,

942
00:52:58,000 --> 00:53:02,000
och kollektivt representerar hela IPAD här en stack struktur.

943
00:53:02,000 --> 00:53:07,000
Nu, som standard, har storlek fick förmodligen att initieras till 0,

944
00:53:07,000 --> 00:53:11,000
och vad är inne i matris med tal initialt

945
00:53:11,000 --> 00:53:14,000
när jag först tilldela en array?

946
00:53:14,000 --> 00:53:16,000
Garbage. Vem vet? Och det spelar ingen roll egentligen.

947
00:53:16,000 --> 00:53:20,000
Det spelar ingen roll om det är 1, 2, 3, 4, 5, helt slumpmässigt

948
00:53:20,000 --> 00:53:25,000
av otur som lagras i min struktur eftersom så länge jag vet att storleken på stacken

949
00:53:25,000 --> 00:53:29,000
är 0, då vet jag programmatiskt, ser inte på någon av elementen i arrayen.

950
00:53:29,000 --> 00:53:31,000
Det spelar ingen roll vad som finns där.

951
00:53:31,000 --> 00:53:34,000
Titta inte på dem, vilket skulle vara innebörden av en storlek på 0.

952
00:53:34,000 --> 00:53:38,000
>> Men antar jag nu gå vidare och sätta något i stacken.

953
00:53:38,000 --> 00:53:42,000
Jag vill infoga numret 5, så jag satte nummer 5 här,

954
00:53:42,000 --> 00:53:45,000
och vad lägger jag här nere?

955
00:53:45,000 --> 00:53:48,000
Nu skulle jag faktiskt lägga ner 1 för storlek,

956
00:53:48,000 --> 00:53:50,000
och nu bunten är storlek 1.

957
00:53:50,000 --> 00:53:53,000
Vad händer om jag går vidare och för in numret, låt oss säga, 7 nästa?

958
00:53:53,000 --> 00:53:57,000
Detta sedan blir uppdaterad till 2, och då ska vi göra 9,

959
00:53:57,000 --> 00:54:02,000
och då detta blir uppdaterad till 3.

960
00:54:02,000 --> 00:54:05,000
Men det intressanta inslag nu av denna stack är att

961
00:54:05,000 --> 00:54:09,000
Jag ska ta bort vilket element om jag vill pop

962
00:54:09,000 --> 00:54:12,000
något från av stapeln, så att säga?

963
00:54:12,000 --> 00:54:14,000
9 skulle vara det första att gå.

964
00:54:14,000 --> 00:54:18,000
Hur ska bilden förändras om jag vill att pop ett element från stacken,

965
00:54:18,000 --> 00:54:20,000
ungefär som en bricka i Mather?

966
00:54:20,000 --> 00:54:22,000
Ja. >> [Student] Ställ in storlek på 2.

967
00:54:22,000 --> 00:54:27,000
Exakt, allt jag gör satt storlek till 2, och vad ska jag göra med kedjan?

968
00:54:27,000 --> 00:54:29,000
Jag behöver inte göra någonting.

969
00:54:29,000 --> 00:54:32,000
Jag skulle bara vara anal, sätta en 0 där eller en -1 eller något att betyda

970
00:54:32,000 --> 00:54:34,000
att detta inte är en legit värde, men det spelar ingen roll eftersom

971
00:54:34,000 --> 00:54:37,000
Jag kan spela utanför uppsättningen själv hur lång tid det är

972
00:54:37,000 --> 00:54:41,000
så att jag vet bara titta på de första två delarna i denna array.

973
00:54:41,000 --> 00:54:47,000
Nu, om jag går och lägger numret 8 till denna array, hur bilden förändras nästa?

974
00:54:47,000 --> 00:54:50,000
Detta blir 8, och detta blir 3.

975
00:54:50,000 --> 00:54:52,000
Jag skär några hörn här.

976
00:54:52,000 --> 00:54:56,000
Nu har vi 5, 7, 8, och vi är tillbaka till en storlek på 3.

977
00:54:56,000 --> 00:54:58,000
Detta är ganska enkelt att implementera,

978
00:54:58,000 --> 00:55:06,000
men när kommer vi att ångra denna design beslut?

979
00:55:06,000 --> 00:55:09,000
När börjar saker att gå mycket, mycket fel? Ja.

980
00:55:09,000 --> 00:55:11,000
[Ohörbart elev svar]

981
00:55:11,000 --> 00:55:13,000
När du vill gå tillbaka och få det första elementet du lägger i.

982
00:55:13,000 --> 00:55:18,000
>> Det visar sig här även om en stapel är en matris under huven,

983
00:55:18,000 --> 00:55:21,000
dessa datastrukturer vi har börjat prata om är också allmänt känd som

984
00:55:21,000 --> 00:55:25,000
abstrakta datastrukturer där hur de genomförs

985
00:55:25,000 --> 00:55:27,000
är helt förutom punkten.

986
00:55:27,000 --> 00:55:31,000
En datastruktur som en stapel är tänkt att ge stöd

987
00:55:31,000 --> 00:55:35,000
operationer som tryck, som driver en bricka på stacken,

988
00:55:35,000 --> 00:55:39,000
och pop, som tar bort ett element från stacken, och det är det.

989
00:55:39,000 --> 00:55:43,000
Om du skulle hämta någon annans kod som redan genomförts

990
00:55:43,000 --> 00:55:46,000
denna sak kallad en skorsten, skulle den personen ha skrivit

991
00:55:46,000 --> 00:55:49,000
endast två funktioner för dig, tryck och pop, vars enda syfte i livet

992
00:55:49,000 --> 00:55:51,000
skulle vara att göra just det.

993
00:55:51,000 --> 00:55:54,000
Du eller honom eller henne som genomförts programmet

994
00:55:54,000 --> 00:55:58,000
skulle ha varit helt och hållet en att bestämma hur man ska genomföra

995
00:55:58,000 --> 00:56:00,000
semantiken för att trycka och poppar under huven

996
00:56:00,000 --> 00:56:03,000
eller funktionalitet trycka och popping.

997
00:56:03,000 --> 00:56:07,000
Och jag har gjort en något kortsiktig beslut här

998
00:56:07,000 --> 00:56:10,000
genom att genomföra min stack med denna enkla datastruktur varför?

999
00:56:10,000 --> 00:56:12,000
När gör detta datastruktur rast?

1000
00:56:12,000 --> 00:56:18,000
Vid vilken punkt har jag returnera ett fel när användaren anropar push, till exempel?

1001
00:56:18,000 --> 00:56:20,000
[Student] Om det inte finns någon mer plats.

1002
00:56:20,000 --> 00:56:23,000
Exakt, om det inte finns mer utrymme, om jag har överskridit kapaciteten,

1003
00:56:23,000 --> 00:56:27,000
vilket är versaler eftersom det antyder att det är någon form av global konstant.

1004
00:56:27,000 --> 00:56:30,000
Nåväl, då jag ska bara säga, "Tyvärr, jag kan inte skjuta ett annat värde

1005
00:56:30,000 --> 00:56:32,000
på stacken, "ungefär som i Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Vid något tillfälle, kommer de att träffa den övre delen av den lilla skåp.

1007
00:56:36,000 --> 00:56:39,000
Det finns ingen mer plats eller kapacitet i högen, då det finns någon typ av fel.

1008
00:56:39,000 --> 00:56:42,000
De måste sätta elementet någon annanstans, facket någon annanstans,

1009
00:56:42,000 --> 00:56:44,000
eller ingenstans alls.

1010
00:56:44,000 --> 00:56:47,000
Nu, med en kö kan vi genomföra det lite annorlunda.

1011
00:56:47,000 --> 00:56:50,000
En kö är lite annorlunda eftersom under huven, kan det genomföras

1012
00:56:50,000 --> 00:56:54,000
som en array, men varför i detta fall föreslår jag

1013
00:56:54,000 --> 00:56:59,000
också ha ett huvudelement representerar huvudet av listan,

1014
00:56:59,000 --> 00:57:06,000
framsidan av listan, den första personen i raden på Apple Store, förutom storlek?

1015
00:57:06,000 --> 00:57:14,000
Varför behöver jag en extra bit data här?

1016
00:57:14,000 --> 00:57:16,000
Tänk tillbaka till vad siffrorna är

1017
00:57:16,000 --> 00:57:18,000
om jag har ritat det följande.

1018
00:57:18,000 --> 00:57:21,000
Antar att detta är nu en kö i stället för en stack,

1019
00:57:21,000 --> 00:57:24,000
Skillnaden är, precis som Apple Store-kö är rättvis.

1020
00:57:24,000 --> 00:57:27,000
Den första personen i raden i början av listan, nummer 5 i detta fall,

1021
00:57:27,000 --> 00:57:30,000
han eller hon kommer att släppa in i butiken först.

1022
00:57:30,000 --> 00:57:32,000
Låt oss göra det.

1023
00:57:32,000 --> 00:57:35,000
Antag att det är det land i min kö på denna tidpunkt, och nu Apple Store

1024
00:57:35,000 --> 00:57:39,000
öppnas och den första personen, nummer 5, leds in i butiken.

1025
00:57:39,000 --> 00:57:43,000
Hur ändrar jag bilden nu när jag har mins-kö den första personen

1026
00:57:43,000 --> 00:57:47,000
på framsidan av linjen?

1027
00:57:47,000 --> 00:57:50,000
Vad är det? >> [Student] Ändra kön.

1028
00:57:50,000 --> 00:57:52,000
Ändra huvudet, så 5 försvinner.

1029
00:57:52,000 --> 00:57:56,000
I verkligheten är det som om-hur man bäst gör detta?

1030
00:57:56,000 --> 00:58:00,000
I verkligheten är det som om den här killen försvinner.

1031
00:58:00,000 --> 00:58:03,000
Vad skulle nummer 7 gör i en verklig butik?

1032
00:58:03,000 --> 00:58:05,000
De skulle ta ett stort steg framåt.

1033
00:58:05,000 --> 00:58:08,000
>> Men vad har vi kommit att uppskatta när det kommer till arrayer

1034
00:58:08,000 --> 00:58:10,000
och flytta runt saker?

1035
00:58:10,000 --> 00:58:12,000
Det är typ av ett slöseri med din tid, eller hur?

1036
00:58:12,000 --> 00:58:16,000
Varför måste man vara så anal att ha den första personen

1037
00:58:16,000 --> 00:58:21,000
i början av raden vid fysiskt i början av bit av minnet?

1038
00:58:21,000 --> 00:58:23,000
Det är helt onödigt. Varför?

1039
00:58:23,000 --> 00:58:26,000
Vad kan jag bara komma ihåg istället? >> [Ohörbart elev svar]

1040
00:58:26,000 --> 00:58:30,000
Exakt, kunde jag minnas bara med mer data ledamot huvud

1041
00:58:30,000 --> 00:58:34,000
att nu chefen för listan är inte längre 0, som det var för en stund sedan.

1042
00:58:34,000 --> 00:58:39,000
Nu är det faktiskt nummer 1. På så sätt får jag en liten optimering.

1043
00:58:39,000 --> 00:58:44,000
Bara för att jag har mins-kö någon från ledningen i början av raden på Apple Store

1044
00:58:44,000 --> 00:58:47,000
betyder inte att alla måste flytta, vilket minns är en linjär operation.

1045
00:58:47,000 --> 00:58:50,000
Jag kan istället ägna konstant tid endast

1046
00:58:50,000 --> 00:58:53,000
och uppnå sedan en mycket snabbare respons.

1047
00:58:53,000 --> 00:58:56,000
Men priset jag betalar är vad för att få det extra prestanda

1048
00:58:56,000 --> 00:58:58,000
och inte behöva flytta alla?

1049
00:58:58,000 --> 00:59:01,000
Ja. >> [Ohörbart elev svar]

1050
00:59:01,000 --> 00:59:04,000
Kan lägga till fler människor, ja, är det problemet ortogonal

1051
00:59:04,000 --> 00:59:07,000
det faktum att vi inte flytta människor runt.

1052
00:59:07,000 --> 00:59:11,000
Det är fortfarande en array, så om vi flytta alla eller inte-

1053
00:59:11,000 --> 00:59:13,000
åh, jag ser vad du menar, okej.

1054
00:59:13,000 --> 00:59:16,000
Egentligen håller jag med vad du säger att det är nästan som om

1055
00:59:16,000 --> 00:59:19,000
Vi bevakar nu aldrig kommer att använda i början av arrayen längre

1056
00:59:19,000 --> 00:59:22,000
för om jag tar bort 5, då jag bort 7.

1057
00:59:22,000 --> 00:59:24,000
Men jag satte bara folk till höger.

1058
00:59:24,000 --> 00:59:28,000
>> Det känns som om jag slösa utrymme, och så småningom min kö sönderfaller till ingenting alls,

1059
00:59:28,000 --> 00:59:31,000
så vi kunde bara få folk wraparound,

1060
00:59:31,000 --> 00:59:35,000
och vi kunde tänka på denna array verkligen som något slags cirkulär struktur,

1061
00:59:35,000 --> 00:59:38,000
men vi använder det operatör i C för att göra den sortens wraparound?

1062
00:59:38,000 --> 00:59:40,000
[Ohörbart elev svar] >> operatorn modulo.

1063
00:59:40,000 --> 00:59:43,000
Det skulle vara lite irriterande att tänka igenom hur du gör wraparound,

1064
00:59:43,000 --> 00:59:46,000
men vi kan göra det, och vi kunde börja sätta människor i vad som brukade vara på framsidan av linjen,

1065
00:59:46,000 --> 00:59:52,000
men vi minns bara med detta huvud variabel som själva huvudet av raden egentligen är.

1066
00:59:52,000 --> 00:59:57,000
Tänk om, istället vårt mål till slut, men

1067
00:59:57,000 --> 01:00:00,000
var att slå upp nummer, som vi gjorde här på scenen med Anita,

1068
01:00:00,000 --> 01:00:02,000
men vi vill verkligen bäst av alla dessa världar?

1069
01:00:02,000 --> 01:00:05,000
Vi vill ha mer sofistikerade än matris tillåter

1070
01:00:05,000 --> 01:00:09,000
eftersom vi vill ha möjlighet att dynamiskt öka datastrukturen.

1071
01:00:09,000 --> 01:00:12,000
Men vi vill inte ta till något som vi påpekade

1072
01:00:12,000 --> 01:00:15,000
i den första föreläsningen var inte en optimal algoritm,

1073
01:00:15,000 --> 01:00:17,000
som linjär sökning.

1074
01:00:17,000 --> 01:00:21,000
Det visar sig att man kan i själva verket få

1075
01:00:21,000 --> 01:00:24,000
eller åtminstone nära konstant tid, där någon som Anita,

1076
01:00:24,000 --> 01:00:27,000
om hon konfigurerar sin datastruktur inte vara en länkad lista,

1077
01:00:27,000 --> 01:00:30,000
inte vara en stapel, att inte vara en kö, skulle i själva verket,

1078
01:00:30,000 --> 01:00:33,000
komma med en datastruktur som tillåter henne att se upp saker,

1079
01:00:33,000 --> 01:00:37,000
även ord, inte bara siffror, i vad vi kallar konstant tid.

1080
01:00:37,000 --> 01:00:40,000
>> Och i själva verket ser framåt, är en av de psets i denna klass nästan alltid

1081
01:00:40,000 --> 01:00:43,000
en implementation av en stavningskontroll, där

1082
01:00:43,000 --> 01:00:46,000
Vi ger dig igen några 150.000 engelska ord och målet är att

1083
01:00:46,000 --> 01:00:51,000
ladda dem i minnet och snabbt kunna svara på frågor i formuläret

1084
01:00:51,000 --> 01:00:54,000
detta ord rättstavat?

1085
01:00:54,000 --> 01:00:58,000
Och det skulle verkligen suga om du var tvungen att iterera igenom alla 150.000 ord att besvara den.

1086
01:00:58,000 --> 01:01:02,000
Men i själva verket kommer vi se att vi kan göra det på mycket, mycket snabb tid.

1087
01:01:02,000 --> 01:01:06,000
Och det kommer att innebära att genomföra något som kallas en hash-tabell,

1088
01:01:06,000 --> 01:01:09,000
och även om vid första anblicken denna sak kallas en hash-tabell ska

1089
01:01:09,000 --> 01:01:12,000
Låt oss uppnå dessa super snabba svarstider,

1090
01:01:12,000 --> 01:01:18,000
Det visar sig att det i själva verket ett problem.

1091
01:01:18,000 --> 01:01:23,000
När det blir dags att genomföra denna sak kallad-igen, jag gör det igen.

1092
01:01:23,000 --> 01:01:25,000
Jag är den enda här.

1093
01:01:25,000 --> 01:01:28,000
När det blir dags att genomföra denna sak kallad en hash-tabell,

1094
01:01:28,000 --> 01:01:30,000
vi kommer att behöva fatta ett beslut.

1095
01:01:30,000 --> 01:01:32,000
Hur stor bör denna sak vara egentligen?

1096
01:01:32,000 --> 01:01:36,000
Och när vi börjar infoga siffror i denna hash tabell,

1097
01:01:36,000 --> 01:01:38,000
Hur ska vi förvara dem på ett sådant sätt

1098
01:01:38,000 --> 01:01:42,000
att vi kan få dem tillbaka så fort som vi fick dem?

1099
01:01:42,000 --> 01:01:45,000
Men vi får se snart att denna fråga om

1100
01:01:45,000 --> 01:01:48,000
när alla fyller år i klassen kommer att vara ganska relevant.

1101
01:01:48,000 --> 01:01:51,000
Det visar sig att i detta rum har vi ett par hundra personer,

1102
01:01:51,000 --> 01:01:56,000
så oddsen att två av oss har samma födelsedag är förmodligen ganska hög.

1103
01:01:56,000 --> 01:01:58,000
Tänk om det fanns bara 40 av oss i det här rummet?

1104
01:01:58,000 --> 01:02:02,000
Vad är oddsen för två personer med samma födelsedag?

1105
01:02:02,000 --> 01:02:04,000
[Studenter] Över 50%.

1106
01:02:04,000 --> 01:02:06,000
Ja, mer än 50%. I själva verket tog jag även ett diagram.

1107
01:02:06,000 --> 01:02:08,000
Det visar sig, och detta är egentligen bara en förhandstitt,

1108
01:02:08,000 --> 01:02:12,000
om det finns bara 58 av oss i detta rum, är sannolikheten för 2 av oss

1109
01:02:12,000 --> 01:02:16,000
med samma födelsedag är enormt hög, nästan 100%,

1110
01:02:16,000 --> 01:02:20,000
och det kommer att orsaka en hel del skada för oss på onsdag.

1111
01:02:20,000 --> 01:02:24,000
>> Med det sagt, låt oss ajournera här. Vi ses på onsdag.

1112
01:02:24,000 --> 01:02:28,000
[Applåder]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]