1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Vecka 6, Fortsättning]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[Detta är CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Detta är CS50 och detta är slutet på vecka 6.

5
00:00:12,970 --> 00:00:17,970
Så CS50x, en av Harvards första kurser som ingår i EDX initiativet

6
00:00:17,970 --> 00:00:20,590
verkligen debuterade den gångna måndag.

7
00:00:20,590 --> 00:00:23,460
Om du vill få en glimt av vad andra på Internet

8
00:00:23,460 --> 00:00:27,180
följer nu tillsammans med, kan du bege dig till x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Det kommer att omdirigera dig till rätt plats på edx.org,

10
00:00:30,350 --> 00:00:34,160
som var där detta och andra kurser från MIT och Berkeley lever nu.

11
00:00:34,160 --> 00:00:38,140
Du måste registrera dig för ett konto, hittar du att materialet är i stort sett detsamma

12
00:00:38,140 --> 00:00:42,170
som du har haft denna termin, även om en försenad några veckor, eftersom vi får allt klart.

13
00:00:42,170 --> 00:00:46,930
Men vad elever i CS50x ser nu är ett gränssnitt helt som denna.

14
00:00:46,930 --> 00:00:50,040
Detta, till exempel, är Zamyla leder genomgång för problemet uppsättningen 0.

15
00:00:50,040 --> 00:00:54,230
När du loggar in på edx.org, ser en CS50x studenten möjliga saker

16
00:00:54,230 --> 00:00:57,170
du förväntar dig att se i en kurs: föreläsning för måndag,

17
00:00:57,170 --> 00:01:01,650
föreläsning för onsdag, olika kortfilmer, problemet uppsättningar, de genomgångar, PDF.

18
00:01:01,650 --> 00:01:04,459
Dessutom, som du ser här, maskinöversättning

19
00:01:04,459 --> 00:01:08,390
av engelska avskrifter till kinesiska, japanska, spanska, italienska,

20
00:01:08,390 --> 00:01:12,810
och en hel massa andra språk som säkert kommer att vara ofullständig

21
00:01:12,810 --> 00:01:15,840
när vi rulla ut dem programmatiskt med hjälp av något som kallas en API,

22
00:01:15,840 --> 00:01:18,360
eller application programming interface, från Google

23
00:01:18,360 --> 00:01:21,360
som tillåter oss att konvertera engelska till alla språk.

24
00:01:21,360 --> 00:01:24,100
Men tack vare den underbara anda av några hundra-plus frivilliga

25
00:01:24,100 --> 00:01:26,940
slumpmässiga människor på Internet som vänligt erbjuds att engagera

26
00:01:26,940 --> 00:01:30,180
i detta projekt kommer vi gradvis förbättra dessa översättningar

27
00:01:30,180 --> 00:01:35,790
genom att människor korrigera de misstag som våra datorer har gjort.

28
00:01:35,790 --> 00:01:42,330
>> Så det visar sig att vi hade några fler studenter dyker upp på måndag än vad vi väntat.

29
00:01:42,330 --> 00:01:48,980
Faktum är nu CS50x har 100.000 människor följer tillsammans hemma.

30
00:01:48,980 --> 00:01:54,430
Så inser du är en del av denna inledande klass att göra denna kurs i datalogi

31
00:01:54,430 --> 00:01:57,370
utbildning i allmänhet, mer allmänt, tillgänglig.

32
00:01:57,370 --> 00:02:00,130
Och verkligheten är nu en del av dessa massiva online-kurser,

33
00:02:00,130 --> 00:02:04,070
de börjar alla med dessa mycket höga siffror, som vi tycks ha gjort här.

34
00:02:04,070 --> 00:02:08,759
Men målet i sista hand för CS50x verkligen att få så många människor till mållinjen som möjligt.

35
00:02:08,759 --> 00:02:12,000
Med design, CS50x kommer att erbjudas från det gångna måndag

36
00:02:12,000 --> 00:02:17,430
hela vägen April 15, 2013, så att folk som har skolan åtaganden på annat håll,

37
00:02:17,430 --> 00:02:20,990
arbete, familj, andra konflikter och liknande, har lite mer flexibilitet

38
00:02:20,990 --> 00:02:23,640
som att dyka in i denna kurs, som är det tillräckligt att säga,

39
00:02:23,640 --> 00:02:30,540
är ganska ambitiöst gjort om bara under loppet av bara tre månader under en vanlig termin.

40
00:02:30,540 --> 00:02:34,190
Men dessa elever kommer att ta itu med de samma problem uppsättningar, visar samma innehåll,

41
00:02:34,190 --> 00:02:36,350
ha tillgång till samma shorts och liknande.

42
00:02:36,350 --> 00:02:38,990
Så inse att vi är alla verkligen i samma båt.

43
00:02:38,990 --> 00:02:42,360
Och en av de slutliga målen för CS50x är inte bara att få så många människor

44
00:02:42,360 --> 00:02:45,720
till mållinjen och ge dem denna nyfunna kunskap om datavetenskap

45
00:02:45,720 --> 00:02:49,000
och programmering, men också att få dem har denna gemensamma erfarenhet.

46
00:02:49,000 --> 00:02:52,010
En av de definierande egenskaperna hos 50 på campus, hoppas vi,

47
00:02:52,010 --> 00:02:56,260
har varit denna typ av gemensamma erfarenheter, på gott och ont, ibland,

48
00:02:56,260 --> 00:02:59,480
men med dessa människor att vända sig till till vänster och till höger,

49
00:02:59,480 --> 00:03:01,830
och kontorstid och hackathon och det verkliga.

50
00:03:01,830 --> 00:03:04,560
Det är lite svårare att göra det personligen med folk på nätet,

51
00:03:04,560 --> 00:03:10,580
men CS50x avslutas i april med den allra första CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
som kommer att vara en online anpassning av vår uppfattning om det verkliga

53
00:03:13,630 --> 00:03:18,250
där dessa tusentals studenter kommer alla att uppmanas att lämna in en 1 - till 2-minuters video,

54
00:03:18,250 --> 00:03:22,480
antingen en screencast av deras slutliga projekt eller video av dem vinka hej

55
00:03:22,480 --> 00:03:24,490
och talar om sitt projekt och demonstrerar den,

56
00:03:24,490 --> 00:03:27,610
ungefär som era föregångare har gjort här på campus i mässan,

57
00:03:27,610 --> 00:03:31,400
så att genom termins slut är förhoppningen att få en global utställning

58
00:03:31,400 --> 00:03:37,080
av CS50x studenternas examensarbeten, ungefär som det som väntar dig i december här på campus.

59
00:03:37,080 --> 00:03:39,680
Så mer om detta under de kommande månaderna.

60
00:03:39,680 --> 00:03:43,640
>> Med 100.000 studenter, men kommer ett behov för ett par CA.

61
00:03:43,640 --> 00:03:47,590
Med tanke på att ni har bräschen här och ta CS50

62
00:03:47,590 --> 00:03:51,630
flera veckor i förväg av detta material är utsläpp till folket på EDX,

63
00:03:51,630 --> 00:03:55,330
inser vi skulle älska att engagera så många av våra egna elever som möjligt i detta initiativ,

64
00:03:55,330 --> 00:03:58,720
både under terminen samt denna vinter och den kommande våren.

65
00:03:58,720 --> 00:04:01,620
Så om du vill engagera dig i CS50x,

66
00:04:01,620 --> 00:04:07,450
särskilt gå in på CS50x diskutera, EDX versionen av CS50 diskutera,

67
00:04:07,450 --> 00:04:10,140
som många av er har använt på campus, online anslagstavla,

68
00:04:10,140 --> 00:04:13,040
du göra huvudet till denna URL, låt oss veta vem du är,

69
00:04:13,040 --> 00:04:16,450
eftersom vi vill gärna bygga upp ett team av studenter och personal och lärare både

70
00:04:16,450 --> 00:04:19,630
på campus som helt enkelt spelar med och hjälpa.

71
00:04:19,630 --> 00:04:21,720
Och när de ser en fråga som är bekant för dem,

72
00:04:21,720 --> 00:04:25,320
du hör en student rapporterar vissa programfel någonstans ute i något land på Internet,

73
00:04:25,320 --> 00:04:27,450
och att ringarna en klocka för att du hade för samma fråga

74
00:04:27,450 --> 00:04:32,620
i d-hallen för en tid sedan, förhoppningsvis kan du klämta i och dela dina egna erfarenheter.

75
00:04:32,620 --> 00:04:37,300
Så vänligen ta del om du vill.

76
00:04:37,300 --> 00:04:39,360
>> Datavetenskap kurser vid Harvard har lite av en tradition,

77
00:04:39,360 --> 00:04:44,730
CS50 bland dem, att ha lite kläder, lite kläder, som du kan bära med stolthet

78
00:04:44,730 --> 00:04:49,090
vid termin slut, säger ganska stolt att du klar CS50

79
00:04:49,090 --> 00:04:51,830
och tog CS50 och liknande, och vi försöker alltid att engagera eleverna

80
00:04:51,830 --> 00:04:54,540
i denna process så mycket som möjligt, där vi bjuder in,

81
00:04:54,540 --> 00:04:56,900
här tiden av terminen, studenter lämna konstruktioner

82
00:04:56,900 --> 00:04:59,330
med hjälp av Photoshop, eller vad bästa sättet du vill använda

83
00:04:59,330 --> 00:05:02,330
om du är en designer, lämna mönster för T-shirts och tröjor

84
00:05:02,330 --> 00:05:06,100
och paraplyer och små snusnäsdukar för hundar som vi har nu och liknande.

85
00:05:06,100 --> 00:05:09,370
Och allt är så - vinnarna varje år sedan ut

86
00:05:09,370 --> 00:05:12,700
på kursens hemsida store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Allt säljs till självkostnadspris där, men webbplatsen just sköter sig själv

88
00:05:15,790 --> 00:05:18,330
och tillåter människor att välja färger och mönster som de vill.

89
00:05:18,330 --> 00:05:20,420
Så jag tänkte att vi bara skulle dela några av förra årets design

90
00:05:20,420 --> 00:05:25,130
som var på webbplatsen utöver detta en här, vilket är en årlig tradition.

91
00:05:25,130 --> 00:05:29,410
"Varje dag jag Seg Faultn" var en av de grunder förra året,

92
00:05:29,410 --> 00:05:32,290
som fortfarande finns där för alumner.

93
00:05:32,290 --> 00:05:35,820
Vi hade den här, "CS50, Etablerad 1989."

94
00:05:35,820 --> 00:05:39,010
En av våra Bowdens, Rob, var mycket populär förra året.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" föddes, var denna design in, bland de bästa säljarna.

96
00:05:43,480 --> 00:05:49,040
Som var en hit. Många människor hade "Bowden Fever" enligt försäljningen loggar.

97
00:05:49,040 --> 00:05:52,650
Inse att det nu kunde vara din design där upp på Internet.

98
00:05:52,650 --> 00:05:57,510
Mer information om detta i nästa problem sätter komma.

99
00:05:57,510 --> 00:06:00,330
>> En mer verktyg: du har haft viss exponering och förhoppningsvis nu

100
00:06:00,330 --> 00:06:02,350
några praktisk erfarenhet GDB,

101
00:06:02,350 --> 00:06:04,570
vilket naturligtvis en debugger och låter dig manipulera

102
00:06:04,570 --> 00:06:09,500
ditt program på en ganska låg nivå, gör vad slags saker?

103
00:06:09,500 --> 00:06:13,030
Vad låter GDB du göra?

104
00:06:13,030 --> 00:06:15,030
Ja? Ge mig något. [Student svar, obegripligt]

105
00:06:15,030 --> 00:06:18,120
Bra. Kliv in funktionen så att du inte bara skriva köras

106
00:06:18,120 --> 00:06:22,310
och har programmet slag genom sin helhet skriva ut saker till standard ut.

107
00:06:22,310 --> 00:06:25,190
Snarare kan man stega igenom rad för rad, antingen skriva nästa

108
00:06:25,190 --> 00:06:30,300
att gå rad för rad för rad eller steg för att dyka in i en funktion, vanligtvis en som du skrev.

109
00:06:30,300 --> 00:06:35,240
Vad låter GDB du göra? Ja? [Student svar, obegripligt]

110
00:06:35,240 --> 00:06:38,100
Skriv variabler. Så om du vill göra en liten introspektion inuti ditt program

111
00:06:38,100 --> 00:06:41,500
utan att behöva tillgripa skriva printf uttalanden överallt,

112
00:06:41,500 --> 00:06:44,600
kan du bara skriva ut en variabel eller visa en variabel.

113
00:06:44,600 --> 00:06:46,710
Vad kan du göra med en debugger som GDB?

114
00:06:46,710 --> 00:06:49,170
[Student svar, obegripligt]

115
00:06:49,170 --> 00:06:52,080
Exakt. Du kan ställa in brytpunkter, du kan säga break utförande

116
00:06:52,080 --> 00:06:54,020
vid huvudfunktionen eller foo-funktionen.

117
00:06:54,020 --> 00:06:56,800
Du kan säga paus exekvering på rad 123.

118
00:06:56,800 --> 00:06:58,950
Och brytpunkter är en riktigt kraftfull teknik

119
00:06:58,950 --> 00:07:01,110
för om du har en allmän känsla av var problemet

120
00:07:01,110 --> 00:07:05,360
förmodligen behöver du inte slösa tid stega igenom programmets helhet.

121
00:07:05,360 --> 00:07:08,250
Du kan i princip hoppa just där och då börja skriva -

122
00:07:08,250 --> 00:07:10,970
stega igenom det med steg eller nästa eller liknande.

123
00:07:10,970 --> 00:07:14,340
Men fångsten med något som GDB är att det hjälper dig, människan,

124
00:07:14,340 --> 00:07:16,940
hitta dina problem och hitta dina buggar.

125
00:07:16,940 --> 00:07:19,470
Det behöver inte nödvändigtvis hitta dem så mycket för dig.

126
00:07:19,470 --> 00:07:23,070
>> Så vi introducerade häromdagen style50, som är en kort kommandoradsverktyg

127
00:07:23,070 --> 00:07:27,500
som försöker att stilisera din kod lite renare än du, människa kan ha gjort.

128
00:07:27,500 --> 00:07:29,530
Men det är också egentligen bara en estetisk sak.

129
00:07:29,530 --> 00:07:34,110
Men det visar sig att det är det här andra verktyg som kallas Valgrind som är lite mer svårbegripliga att använda.

130
00:07:34,110 --> 00:07:36,860
Dess produktion är vedervärdigt kryptiska vid första anblicken.

131
00:07:36,860 --> 00:07:39,420
Men det är underbart bra, speciellt nu när vi är på den del av begreppet

132
00:07:39,420 --> 00:07:43,080
där du börjar använda malloc och dynamisk minnesallokering.

133
00:07:43,080 --> 00:07:45,420
Saker kan gå riktigt, riktigt fel snabbt.

134
00:07:45,420 --> 00:07:49,320
För om du glömmer att frigöra ditt minne, eller om du dereference någon NULL-pekare,

135
00:07:49,320 --> 00:07:55,770
eller du dereference något skräp pekare, vad är typiskt symptom som resultat?

136
00:07:55,770 --> 00:07:59,470
Seg fel. Och du får denna kärna fil av ett visst antal kilobyte eller megabyte

137
00:07:59,470 --> 00:08:02,990
som representerar tillståndet i ditt program minne när det kraschade,

138
00:08:02,990 --> 00:08:05,730
men ditt program seg slutändan fel, segmenteringsfel,

139
00:08:05,730 --> 00:08:08,450
vilket betyder något dåligt hände nästan alltid relaterat

140
00:08:08,450 --> 00:08:11,750
till ett minne-relaterade misstag som du har gjort någonstans.

141
00:08:11,750 --> 00:08:14,100
Så Valgrind hjälper dig att hitta saker som detta.

142
00:08:14,100 --> 00:08:17,720
Det är ett verktyg som du kör, liksom GDB, efter att du har sammanställt ditt program,

143
00:08:17,720 --> 00:08:20,330
men i stället köra programmet direkt, kör du Valgrind

144
00:08:20,330 --> 00:08:23,960
och du skickar till den ditt program, precis som du gör med GDB.

145
00:08:23,960 --> 00:08:26,220
Nu, användning, för att få den bästa typ av produktion,

146
00:08:26,220 --> 00:08:30,410
är lite lång, så just där uppe på skärmen ser du Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" nästan överallt betyder detaljerad när du använder program på en Linux-dator.

148
00:08:35,350 --> 00:08:38,770
Så det betyder att spotta ut mer data än du kanske som standard.

149
00:08:38,770 --> 00:08:45,510
"- Läcka-check = full." Detta är bara säga check för alla möjliga minnesläckor,

150
00:08:45,510 --> 00:08:49,430
misstag som jag kan ha gjort. Detta är också en vanlig paradigm med Linux-program.

151
00:08:49,430 --> 00:08:52,710
Generellt, om du har en argumentet kommandorad som är en "switch",

152
00:08:52,710 --> 00:08:55,830
som är tänkt att ändra programmets beteende, och det är en enda bokstav,

153
00:08:55,830 --> 00:09:00,310
Det är-v, men om det är bytt, bara genom utformningen av programmerare,

154
00:09:00,310 --> 00:09:05,150
är en helt ord eller en serie av ord, börjar kommandoraden argument med -.

155
00:09:05,150 --> 00:09:08,190
Dessa är bara mänskliga konventioner, men du kommer att se dem allt.

156
00:09:08,190 --> 00:09:12,410
Och, slutligen, "a.out" är godtyckligt namn för programmet i detta speciella exempel.

157
00:09:12,410 --> 00:09:14,640
Och här är några representativa utgång.

158
00:09:14,640 --> 00:09:22,890
>> Innan vi tittar på vad det kan innebära, låt mig gå över till en kodsträng här.

159
00:09:22,890 --> 00:09:26,390
Och låt mig flytta ur vägen, kommer snart,

160
00:09:26,390 --> 00:09:32,120
och låt oss ta en titt på memory.c, vilket är det korta exemplet här.

161
00:09:32,120 --> 00:09:36,290
Så i det här programmet, låt mig zooma in på de funktioner och frågor.

162
00:09:36,290 --> 00:09:39,430
Vi har en funktion huvud som anropar en funktion, f,

163
00:09:39,430 --> 00:09:45,590
och vad finns anledning f att göra, i något teknisk engelska?

164
00:09:45,590 --> 00:09:49,760
Vad finns anledning f göra?

165
00:09:49,760 --> 00:09:53,680
Vad sägs om jag ska börja med linje 20, och stjärnan läge spelar ingen roll,

166
00:09:53,680 --> 00:09:56,720
men jag ska bara vara konsekvent här med sista föreläsning.

167
00:09:56,720 --> 00:09:59,910
Vad är linjen 20 göra för oss? På vänster sida. Vi ska bryta ner ytterligare.

168
00:09:59,910 --> 00:10:02,410
Int * x: vad betyder det då?

169
00:10:02,410 --> 00:10:04,940
Okej. Det förklarar en pekare, och nu ska vi bli ännu mer teknisk.

170
00:10:04,940 --> 00:10:10,230
Vad betyder det, mycket konkret, att förklara en pekare? Någon annan?

171
00:10:10,230 --> 00:10:15,050
Ja? [Student svar, obegripliga] för långt.

172
00:10:15,050 --> 00:10:17,060
Så du läser den högra sidan av likhetstecknet.

173
00:10:17,060 --> 00:10:20,290
Låt oss fokusera bara på vänster, bara på int * x.

174
00:10:20,290 --> 00:10:24,700
Detta "förklarar" en pekare, men nu låt oss dyka djupare i denna definition.

175
00:10:24,700 --> 00:10:28,330
Vad betyder det konkret, tekniskt menar? Ja?

176
00:10:28,330 --> 00:10:31,940
[Student svar, obegripligt]

177
00:10:31,940 --> 00:10:35,090
Okej. Det förbereder för att spara en adress i minnet.

178
00:10:35,090 --> 00:10:40,680
Bra. Och låt oss ta detta ett steg längre, det är att förklara en variabel, x, det är 32 bitar.

179
00:10:40,680 --> 00:10:44,440
Och jag vet att det är 32 bitar eftersom -?

180
00:10:44,440 --> 00:10:47,390
Det är inte för att det är en int, eftersom det är en pekare i detta fall.

181
00:10:47,390 --> 00:10:49,650
Tillfällighet att det är en och samma sak med en int,

182
00:10:49,650 --> 00:10:51,970
men det faktum att det finns stjärnan finns innebär detta är en pekare

183
00:10:51,970 --> 00:10:57,300
och i apparaten, som med många datorer, men inte alla, pekare är 32 bitar.

184
00:10:57,300 --> 00:11:01,850
På modernare hårdvara som de senaste Mac, de senaste PC, kanske du har 64-bitars pekare,

185
00:11:01,850 --> 00:11:04,160
men i apparaten, dessa saker är 32 bitar.

186
00:11:04,160 --> 00:11:08,380
Så vi ska standardisera på det. Mer konkret går berättelsen som följer:

187
00:11:08,380 --> 00:11:10,820
Vi "förklarar" en pekare, vad betyder det?

188
00:11:10,820 --> 00:11:12,810
Vi förbereder för att lagra en minnesadress.

189
00:11:12,810 --> 00:11:15,530
Vad betyder det?

190
00:11:15,530 --> 00:11:19,810
Vi skapar en variabel kallad X som tar upp 32 bitar

191
00:11:19,810 --> 00:11:23,810
som snart kommer att lagra adressen till ett heltal.

192
00:11:23,810 --> 00:11:26,470
Och det är nog ungefär så exakt som vi kan få.

193
00:11:26,470 --> 00:11:31,810
Det är bra att gå vidare för att förenkla världen och bara säga förklara en pekare som heter X.

194
00:11:31,810 --> 00:11:35,380
Deklarera en pekare, men inse och förstå vad som faktiskt händer

195
00:11:35,380 --> 00:11:38,490
även på bara dessa få tecken.

196
00:11:38,490 --> 00:11:42,040
>> Nu är det här en nästan lite enklare, även om det är en längre uttryck.

197
00:11:42,040 --> 00:11:48,160
Så vad är detta att göra, som är markerad nu: "malloc (10 * sizeof (int));" Ja?

198
00:11:48,160 --> 00:11:52,350
[Student svar, obegripligt]

199
00:11:52,350 --> 00:11:58,250
Bra. Och jag tar det där. Det tilldelning av en bit av minne för tio heltal.

200
00:11:58,250 --> 00:12:02,190
Och nu ska vi dyka i något djupare, det är tilldelning av en bit av minne för tio heltal.

201
00:12:02,190 --> 00:12:05,390
Vad är malloc tillbaka då?

202
00:12:05,390 --> 00:12:10,390
Adressen för denna bit, eller, mer konkret, adressen för den första bitgruppen i denna bit.

203
00:12:10,390 --> 00:12:14,080
Hur då är jag, programmeraren, att veta var den bit av minne slutar?

204
00:12:14,080 --> 00:12:18,340
Jag vet att det är sammanhängande. Malloc, per definition, kommer att ge dig en sammanhängande bit av minnet.

205
00:12:18,340 --> 00:12:21,240
Några luckor i den. Du har tillgång till varje byte i den bit,

206
00:12:21,240 --> 00:12:26,760
rygg mot rygg mot rygg, men hur vet jag var i slutet av denna bit av minnet är?

207
00:12:26,760 --> 00:12:28,850
När du använder malloc? [Student svar, obegripliga] Bra.

208
00:12:28,850 --> 00:12:30,670
Du inte. Du måste komma ihåg.

209
00:12:30,670 --> 00:12:35,960
Jag måste komma ihåg att jag använde värdet 10, och jag tror inte ens verkar ha gjort det här.

210
00:12:35,960 --> 00:12:41,000
Men åligger helt på mig. Strlen, som vi har blivit något beroende för stråkar,

211
00:12:41,000 --> 00:12:45,860
fungerar bara på grund av denna konvention för att ha \ 0

212
00:12:45,860 --> 00:12:48,840
eller denna speciella nul karaktär, NUL, vid slutet av en sträng.

213
00:12:48,840 --> 00:12:51,740
Som inte håller för bara godtyckliga bitar av minnet.

214
00:12:51,740 --> 00:12:58,590
Det är upp till dig. Så ledning 20 då tilldelar en bit av minne

215
00:12:58,590 --> 00:13:02,590
som kan lagra tio heltal, och det lagrar adressen för den första bitgruppen

216
00:13:02,590 --> 00:13:05,610
denna bit av minnet i den variabel som kallas X.

217
00:13:05,610 --> 00:13:11,140
Ergo, vilket är en pekare. Så linje 21, tyvärr var ett misstag.

218
00:13:11,140 --> 00:13:16,110
Men först, vad gör den? Det säger butik på plats 10, 0 indexeras,

219
00:13:16,110 --> 00:13:19,480
av bit av minne som kallas x värdet 0.

220
00:13:19,480 --> 00:13:21,510
>> Så märker ett par saker pågår.

221
00:13:21,510 --> 00:13:25,420
Även om x är en pekare återkalla ett par veckor sedan

222
00:13:25,420 --> 00:13:29,440
att du kan fortfarande använda array-stil notation hakparentes.

223
00:13:29,440 --> 00:13:36,180
Eftersom det är faktiskt kort hand notation för de mer kryptiska utseende pekare aritmetik.

224
00:13:36,180 --> 00:13:40,320
där vi skulle göra något så här: Ta adressen X, flytta 10 platser över,

225
00:13:40,320 --> 00:13:44,550
sedan går det till vad adress lagras på den platsen.

226
00:13:44,550 --> 00:13:48,090
Men ärligt talat, det är bara förfärligt att läsa och bli bekant med.

227
00:13:48,090 --> 00:13:52,900
Så världen använder vanligtvis hakparenteserna bara för att det är så mycket mer mänsklig-vänlig att läsa.

228
00:13:52,900 --> 00:13:55,140
Men det är vad som verkligen händer under huven,

229
00:13:55,140 --> 00:13:58,190
x är en adress, inte en array, i sig.

230
00:13:58,190 --> 00:14:02,410
Så detta lagrar 0 vid läget 10 i x.

231
00:14:02,410 --> 00:14:06,120
Varför är det dåligt? Ja?

232
00:14:06,120 --> 00:14:17,370
[Student svar, obegripliga] Exakt.

233
00:14:17,370 --> 00:14:21,100
Vi tilldelas endast tio Ints, men vi räknar från 0 vid programmering i C,

234
00:14:21,100 --> 00:14:25,690
så du har tillgång till 0 1 2 3 4 5 6 7 8 9 men inte 10.

235
00:14:25,690 --> 00:14:30,270
Så antingen programmet kommer att seg fel eller är det inte.

236
00:14:30,270 --> 00:14:32,900
Men vi vet inte riktigt, det är typ av en nondeterministic beteende.

237
00:14:32,900 --> 00:14:35,600
Det beror egentligen på om vi har tur.

238
00:14:35,600 --> 00:14:40,650
Om det visar sig att operativsystemet inte emot om jag använder det extra byte,

239
00:14:40,650 --> 00:14:43,360
även om det inte har gett det till mig, kanske mitt program krascha inte.

240
00:14:43,360 --> 00:14:46,780
Det är rått, det är buggig, men du kanske inte se att symptom,

241
00:14:46,780 --> 00:14:48,960
eller du kanske ser det bara en gång på ett tag.

242
00:14:48,960 --> 00:14:51,230
Men verkligheten är att felet är i själva verket finns.

243
00:14:51,230 --> 00:14:54,320
Och det är verkligen problematiskt om du har skrivit ett program som du vill vara korrekt,

244
00:14:54,320 --> 00:14:58,840
att du har sålt det program som folk använder den varje gång på ett tag kraschar

245
00:14:58,840 --> 00:15:02,450
eftersom, naturligtvis, är det inte bra. Faktum är att om du har en Android-telefon eller en iPhone

246
00:15:02,450 --> 00:15:05,550
och du hämtar program i dessa dagar, om du någonsin haft en app bara sluta,

247
00:15:05,550 --> 00:15:10,040
plötsligt försvinner, det är nästan alltid resultatet av någon minne-relaterad fråga,

248
00:15:10,040 --> 00:15:12,830
varigenom programmeraren skruvas upp och dereferenced en pekare

249
00:15:12,830 --> 00:15:18,670
att han eller hon bör inte ha, och resultatet av iOS eller Android är att bara döda programmet helt och hållet

250
00:15:18,670 --> 00:15:23,080
hellre än att riskera odefinierat beteende eller någon form av säkerhet kompromiss.

251
00:15:23,080 --> 00:15:25,950
>> Det finns en annan bugg i programmet förutom detta.

252
00:15:25,950 --> 00:15:30,180
Vad har jag skruvas upp i detta program?

253
00:15:30,180 --> 00:15:32,740
Jag har inte tränat som jag har predikat. Ja?

254
00:15:32,740 --> 00:15:34,760
[Student svar, obegripliga] Bra.

255
00:15:34,760 --> 00:15:36,880
Jag har inte befriat minnet. Så tumregel nu

256
00:15:36,880 --> 00:15:43,150
måste vara när du ringer malloc, måste du ringa gratis när du är klar med detta minne.

257
00:15:43,150 --> 00:15:45,610
Nu skulle när jag vill frigöra detta minne?

258
00:15:45,610 --> 00:15:49,780
Förmodligen antar detta första raden var korrekt, skulle jag vilja göra det här.

259
00:15:49,780 --> 00:15:55,710
Eftersom jag inte kunde till exempel göra det här nere. Varför?

260
00:15:55,710 --> 00:15:57,860
Bara av omfattning. Så även om vi pratar om pekare,

261
00:15:57,860 --> 00:16:04,830
Detta är en vecka 2 eller 3 fråga, där x är bara i omfattning insidan av klammerparenteser där den deklareras.

262
00:16:04,830 --> 00:16:11,000
Så du definitivt inte kan befria den där. Min enda chans att frigöra den är ungefär efter linjen 21.

263
00:16:11,000 --> 00:16:15,170
Detta är ett relativt enkelt program, det var ganska lätt när du typ av lindade ditt sinne

264
00:16:15,170 --> 00:16:17,870
runt vad programmet gör, där misstag var.

265
00:16:17,870 --> 00:16:20,500
Och även om du inte ser det först, förhoppningsvis är det lite uppenbart nu

266
00:16:20,500 --> 00:16:23,870
att dessa misstag är ganska lätt att lösa och lätt gjort.

267
00:16:23,870 --> 00:16:28,720
Men när ett program är mer än 12 rader lång, det är 50 rader lång, 100 rader lång,

268
00:16:28,720 --> 00:16:31,150
gå igenom din kod rad för rad, tänka igenom det logiskt,

269
00:16:31,150 --> 00:16:35,110
är möjligt men inte särskilt roligt att göra, ständigt letar efter fel,

270
00:16:35,110 --> 00:16:38,340
och det är också svårt att göra, och det är därför ett verktyg som Valgrind finns.

271
00:16:38,340 --> 00:16:40,900
Låt mig gå vidare och göra detta: Låt mig öppna mitt terminalfönster,

272
00:16:40,900 --> 00:16:45,400
och låt mig inte bara köra minnet, eftersom minnet verkar vara bra.

273
00:16:45,400 --> 00:16:49,180
Jag börjar bli lycklig. Gå till att ytterligare byte i slutet av uppsättningen

274
00:16:49,180 --> 00:16:51,060
verkar inte vara alltför problematisk.

275
00:16:51,060 --> 00:16:56,370
Men låt mig ändå göra en sanity check, vilket betyder bara att kontrollera

276
00:16:56,370 --> 00:16:58,320
huruvida detta verkligen stämmer.

277
00:16:58,320 --> 00:17:04,690
>> Så låt oss göra Valgrind-v - läckage-check = full,

278
00:17:04,690 --> 00:17:07,520
och sedan namnet på programmet i det här fallet är minnet, inte a.out.

279
00:17:07,520 --> 00:17:10,760
Så låt mig gå vidare och göra det. Hit Enter.

280
00:17:10,760 --> 00:17:14,109
Käre Gud. Detta är dess produktion, och det är vad jag hänvisade till tidigare.

281
00:17:14,109 --> 00:17:17,550
Men om du lär dig att läsa igenom hela nonsens här,

282
00:17:17,550 --> 00:17:20,760
det mesta av detta är bara diagnostiska utgång som inte är så intressant.

283
00:17:20,760 --> 00:17:24,829
Vad ögat verkligen vill vara ute efter är något omnämnande av fel eller ogiltig.

284
00:17:24,829 --> 00:17:26,800
Ord som tyder på problem.

285
00:17:26,800 --> 00:17:29,340
Och faktiskt, låt oss se vad som händer fel här nere.

286
00:17:29,340 --> 00:17:35,230
Jag har en sammanfattning av något slag, "används vid avfart:. 40 byte i 1 block"

287
00:17:35,230 --> 00:17:38,750
Jag är inte riktigt säker på vad ett block är ännu, men 40 byte

288
00:17:38,750 --> 00:17:41,260
känns faktiskt som om jag skulle kunna räkna ut var det kommer ifrån.

289
00:17:41,260 --> 00:17:45,030
40 byte. Varför är 40 byte i bruk vid avfart?

290
00:17:45,030 --> 00:17:48,780
Och mer specifikt, om vi rulla ner här,

291
00:17:48,780 --> 00:17:54,520
varför har jag förlorat definitivt 40 byte? Ja?

292
00:17:54,520 --> 00:17:59,520
[Student svar, obegripliga] Perfekt. Ja, exakt.

293
00:17:59,520 --> 00:18:03,540
Det fanns tio heltal, och vart och ett av dessa är storleken på 4, eller 32 bitar,

294
00:18:03,540 --> 00:18:08,300
så jag har förlorat exakt 40 byte eftersom, som ni föreslog, jag har inte kallat fri.

295
00:18:08,300 --> 00:18:13,460
Det är en bugg, och nu ska vi titta ner lite längre och se bredvid detta,

296
00:18:13,460 --> 00:18:16,900
"Ogiltig skriva av storlek 4." Nu vad är detta?

297
00:18:16,900 --> 00:18:21,150
Denna adress uttrycks vad bas notation, tydligen?

298
00:18:21,150 --> 00:18:23,640
Detta är hexadecimalt, och varje gång du ser ett nummer som börjar med 0x,

299
00:18:23,640 --> 00:18:29,410
det betyder hexadecimala, vilket vi gjorde redan på, tror jag, pset 0 avsnitt av frågor,

300
00:18:29,410 --> 00:18:34,090
vilket var bara att göra en uppvärmning övning, konvertera decimal till hex till binärt och så vidare.

301
00:18:34,090 --> 00:18:39,220
Hexadecimala, bara genom mänsklig konvention, används vanligen för att representera pekare

302
00:18:39,220 --> 00:18:41,570
eller, mer allmänt, adresser. Det är bara en konvention,

303
00:18:41,570 --> 00:18:45,340
eftersom det är lite lättare att läsa, det är lite mer kompakt än något som decimal,

304
00:18:45,340 --> 00:18:47,720
och binär är meningslöst för de flesta människor att använda.

305
00:18:47,720 --> 00:18:50,840
Så nu vad betyder det? Det ser ut som det finns en ogiltig skrivning

306
00:18:50,840 --> 00:18:54,480
storlek 4 på linje 21 i memory.c.

307
00:18:54,480 --> 00:18:59,180
Så låt oss gå tillbaka till rad 21, och faktiskt, här är det ogiltigt skriva.

308
00:18:59,180 --> 00:19:02,640
Så Valgrind kommer inte att helt hålla min hand och berätta vad fix är,

309
00:19:02,640 --> 00:19:05,520
men det är att upptäcka att jag gör en ogiltig skrivning.

310
00:19:05,520 --> 00:19:08,800
Jag rör 4 byte som jag inte borde vara, och uppenbarligen det beror,

311
00:19:08,800 --> 00:19:13,960
som ni påpekade, jag gör [10] istället för [9] maximalt

312
00:19:13,960 --> 00:19:16,660
eller [0] eller något däremellan.

313
00:19:16,660 --> 00:19:19,690
Med Valgrind inser när du bevakar nu skriva ett program

314
00:19:19,690 --> 00:19:24,190
som använder pekare och använder minnet, och malloc mer specifikt,

315
00:19:24,190 --> 00:19:27,080
definitivt komma in i vanan att köra denna långa

316
00:19:27,080 --> 00:19:30,890
men mycket lätt kopieras och klistras behärskar Valgrind

317
00:19:30,890 --> 00:19:32,650
för att se om det finns några fel i det.

318
00:19:32,650 --> 00:19:34,820
Och det blir överväldigande varje gång du ser utgången,

319
00:19:34,820 --> 00:19:39,430
men bara tolka igenom visuellt hela produktionen och se om du ser nämner fel

320
00:19:39,430 --> 00:19:43,190
eller varningar eller ogiltiga eller förloras.

321
00:19:43,190 --> 00:19:46,200
Alla ord som låter som om du skruvas upp någonstans.

322
00:19:46,200 --> 00:19:48,580
Så inser att det är ett nytt verktyg i din verktygslåda.

323
00:19:48,580 --> 00:19:51,270
>> Nu på måndag, hade vi en massa folk kommer hit

324
00:19:51,270 --> 00:19:53,150
och representerar begreppet en länkad lista.

325
00:19:53,150 --> 00:20:00,970
Och vi introducerade den länkade listan som en lösning på vilket problem?

326
00:20:00,970 --> 00:20:04,590
Ja? [Student svar, obegripliga] Bra.

327
00:20:04,590 --> 00:20:06,530
Arrayer kan inte ha minne som har lagts till dem.

328
00:20:06,530 --> 00:20:09,440
Om du tilldela en rad storlek 10, det är allt du får.

329
00:20:09,440 --> 00:20:13,690
Du kan ringa en funktion som realloc om du först kallade malloc,

330
00:20:13,690 --> 00:20:17,580
och som kan försöka odla arrayen om det finns utrymme i slutet av det

331
00:20:17,580 --> 00:20:21,610
att ingen annan använder, och om det inte kommer det bara att hitta en större bit någon annanstans.

332
00:20:21,610 --> 00:20:25,040
Men då kommer det att kopiera alla dessa byte till den nya arrayen.

333
00:20:25,040 --> 00:20:28,310
Detta låter som en mycket korrekt lösning.

334
00:20:28,310 --> 00:20:34,790
Varför är det ointressant?

335
00:20:34,790 --> 00:20:36,940
Jag menar det fungerar, har människan löst detta problem.

336
00:20:36,940 --> 00:20:40,710
Varför behövde vi lösa det på måndag med länkade listor? Ja?

337
00:20:40,710 --> 00:20:44,060
[Student svar, obegripliga] Det kan ta lång tid.

338
00:20:44,060 --> 00:20:49,260
Faktum helst du ringer malloc eller realloc eller calloc, vilket är ännu en annan,

339
00:20:49,260 --> 00:20:52,470
varje gång du, programmet talar med operativsystemet,

340
00:20:52,470 --> 00:20:54,310
du tenderar att sakta programmet ner.

341
00:20:54,310 --> 00:20:57,470
Och om du gör den här typen av saker i loopar, du saktar verkligen ner saker.

342
00:20:57,470 --> 00:21:00,740
Du kommer inte att märka detta för den enklaste av "Hello World" typ program,

343
00:21:00,740 --> 00:21:04,300
men i mycket större program, frågar operativsystemet och om igen för minne

344
00:21:04,300 --> 00:21:07,520
eller ge det tillbaka igen och igen brukar inte vara en bra sak.

345
00:21:07,520 --> 00:21:11,210
Dessutom är det bara sorts intellektuellt - det är ett fullständigt slöseri med tid.

346
00:21:11,210 --> 00:21:16,490
Varför avsätta mer och mer minne, riskerar att kopiera allt i den nya arrayen,

347
00:21:16,490 --> 00:21:21,980
Om du har ett alternativ som låter dig tilldela bara så mycket minne som du faktiskt behöver?

348
00:21:21,980 --> 00:21:24,130
Så det finns plus och minus i här.

349
00:21:24,130 --> 00:21:26,730
En av plussidan är nu att vi har dynamik.

350
00:21:26,730 --> 00:21:29,100
Spelar ingen roll om de bitar av minnet är som är gratis,

351
00:21:29,100 --> 00:21:32,070
Jag kan bara sortera om att skapa dessa brödsmulor via pekare

352
00:21:32,070 --> 00:21:34,470
att strängen hela mitt länkad lista tillsammans.

353
00:21:34,470 --> 00:21:36,470
Men jag betala minst en pris.

354
00:21:36,470 --> 00:21:40,060
>> Vad måste jag ge upp att få länkade listor?

355
00:21:40,060 --> 00:21:42,470
Ja? [Student svar, obegripliga] Bra.

356
00:21:42,470 --> 00:21:45,650
Du behöver mer minne. Nu behöver jag utrymme för dessa tips,

357
00:21:45,650 --> 00:21:47,900
och i fallet med denna super länkad enkel lista

358
00:21:47,900 --> 00:21:51,410
som bara försöker lagra heltal, som är 4 byte, håller vi säger

359
00:21:51,410 --> 00:21:54,240
Tja, är en pekare 4 byte, så nu har jag bokstavligen fördubblats

360
00:21:54,240 --> 00:21:57,290
hur mycket minne jag behöver bara lagra den här listan.

361
00:21:57,290 --> 00:21:59,680
Men återigen, detta är en ständig avvägning i datavetenskap

362
00:21:59,680 --> 00:22:03,440
mellan tid och rum och utveckling, arbete och andra resurser.

363
00:22:03,440 --> 00:22:06,630
Vad är en annan nackdel med att använda en länkad lista? Ja?

364
00:22:06,630 --> 00:22:10,150
[Student svar, obegripligt]

365
00:22:10,150 --> 00:22:12,600
Bra. Inte så lätt att komma åt. Vi kan inte längre utnyttja

366
00:22:12,600 --> 00:22:15,530
vecka 0 principer som söndra och härska.

367
00:22:15,530 --> 00:22:18,220
Och mer specifikt, binär sökning. För även om vi människor

368
00:22:18,220 --> 00:22:20,400
kan se ungefär var i mitten av listan är,

369
00:22:20,400 --> 00:22:25,840
datorn vet endast att detta länkade listan börjar vid adress kallade första.

370
00:22:25,840 --> 00:22:28,250
Och det är 0x123 eller något liknande.

371
00:22:28,250 --> 00:22:30,990
Och det enda sättet att programmet kan hitta den mellersta delen

372
00:22:30,990 --> 00:22:33,350
är att faktiskt söka i hela listan.

373
00:22:33,350 --> 00:22:35,500
Och även då måste det bokstavligen att söka hela listan eftersom

374
00:22:35,500 --> 00:22:38,950
även när du når mitten delen genom att följa pekare,

375
00:22:38,950 --> 00:22:42,380
du programmet har ingen aning om hur länge den här listan är potentiellt

376
00:22:42,380 --> 00:22:45,250
tills du träffar i slutet av den, och hur vet du programmatiskt

377
00:22:45,250 --> 00:22:48,600
att du är i slutet av en länkad lista?

378
00:22:48,600 --> 00:22:51,120
Det finns en speciell NULL-pekare, så igen, en konvention.

379
00:22:51,120 --> 00:22:53,870
Hellre än att använda pekare, vi vill definitivt inte att det ska vara något skräp värde

380
00:22:53,870 --> 00:22:57,750
pekar utanför scenen någonstans, vi vill att det ska vara hand ner, NULL,

381
00:22:57,750 --> 00:23:01,530
så att vi har denna ändstation i datastrukturen så vi vet var det slutar.

382
00:23:01,530 --> 00:23:03,410
>> Tänk om vi vill manipulera detta?

383
00:23:03,410 --> 00:23:05,980
Vi gjorde det mesta av detta visuellt och med människor,

384
00:23:05,980 --> 00:23:07,630
men vad händer om vi vill göra en insättning?

385
00:23:07,630 --> 00:23:12,360
Så den ursprungliga listan var 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Tänk om vi ville sedan minnesallokera utrymme för nummer 55, en nod för det,

387
00:23:16,730 --> 00:23:20,730
och då vi vill infoga 55 i listan precis som vi gjorde i måndags?

388
00:23:20,730 --> 00:23:23,690
Hur gör vi det? Tja, kom Anita och hon huvudsakligen gick i listan.

389
00:23:23,690 --> 00:23:27,500
Hon började på det första elementet, sedan nästa, nästa, nästa, nästa, nästa.

390
00:23:27,500 --> 00:23:29,500
Slutligen träffade vänster hela vägen ner

391
00:23:29,500 --> 00:23:34,480
och insåg åh, det här NULL. Så vad pekare manipulation måste göras?

392
00:23:34,480 --> 00:23:37,980
Den person som var på slutet, nummer 34, behövde hans vänstra hand upp

393
00:23:37,980 --> 00:23:46,220
att peka på 55, behövde 55 sin vänstra arm nedåt till ny NULL terminatorn. Klar.

394
00:23:46,220 --> 00:23:49,540
Ganska lätt att sätta 55 i en sorterad lista.

395
00:23:49,540 --> 00:23:51,800
Och hur kan detta se ut?

396
00:23:51,800 --> 00:23:55,690
>> Låt mig gå vidare och öppna upp lite kod exempel här.

397
00:23:55,690 --> 00:23:58,120
Jag öppnar gedit, och låt mig öppna upp två filer först.

398
00:23:58,120 --> 00:24:02,050
En är list1.h, och låt mig bara påminna om att detta var bit av koden

399
00:24:02,050 --> 00:24:04,920
att vi använde för att representera en nod.

400
00:24:04,920 --> 00:24:13,040
En nod har både en int som kallas n och en pekare som kallas nästa som bara pekar på nästa sak på listan.

401
00:24:13,040 --> 00:24:15,450
Som nu är i en. H. fil. Varför?

402
00:24:15,450 --> 00:24:19,090
Det är denna konvention, och vi har inte utnyttjat denna en enorm själva,

403
00:24:19,090 --> 00:24:22,220
men den person som skrev printf och andra funktioner

404
00:24:22,220 --> 00:24:27,150
gav som gåva till världen alla dessa funktioner genom att skriva en fil som heter stdio.h.

405
00:24:27,150 --> 00:24:30,950
Och sedan finns det string.h, och sedan finns det map.h, och det finns alla dessa h-filer

406
00:24:30,950 --> 00:24:34,410
som du kanske har sett eller använt under löptiden skrivna av andra människor.

407
00:24:34,410 --> 00:24:38,470
Vanligtvis i dem. H-filer är bara saker som typedefs

408
00:24:38,470 --> 00:24:42,310
eller förklaringar om anpassade typer eller förklaringar konstanter.

409
00:24:42,310 --> 00:24:47,890
Du lägger inte fungerar "implementeringar i header-filer.

410
00:24:47,890 --> 00:24:50,570
Du sätter i stället bara deras prototyper.

411
00:24:50,570 --> 00:24:53,050
Du sätter saker du vill dela med världen vad de behöver

412
00:24:53,050 --> 00:24:55,640
för att sammanställa sin kod. Så bara för att komma in i denna vana,

413
00:24:55,640 --> 00:24:59,110
vi beslutat att göra samma sak. Det finns inte mycket i list1.h,

414
00:24:59,110 --> 00:25:02,070
men vi har lagt något som kan vara av intresse för människor i världen

415
00:25:02,070 --> 00:25:05,030
som vill använda vår länkad lista genomförande.

416
00:25:05,030 --> 00:25:08,040
Nu, i list1.c kommer jag inte gå igenom allt det här

417
00:25:08,040 --> 00:25:11,390
eftersom det är lite långt, det här programmet, men låt oss köra den riktigt snabbt vid prompten.

418
00:25:11,390 --> 00:25:15,720
Låt mig sammanställa List1, låt mig sedan köra List1, och vad du ser är

419
00:25:15,720 --> 00:25:18,070
vi har simulerat ett enkelt litet program här

420
00:25:18,070 --> 00:25:20,990
det kommer att tillåta mig att lägga till och ta bort nummer i en lista.

421
00:25:20,990 --> 00:25:24,310
Så låt mig gå vidare och typ 3 för menyalternativet 3.

422
00:25:24,310 --> 00:25:27,880
Jag vill infoga numret - låt oss göra det första numret, som var 9,

423
00:25:27,880 --> 00:25:30,550
och nu är jag berättat listan är nu 9.

424
00:25:30,550 --> 00:25:33,760
Låt mig gå vidare och göra en annan insättning, så jag slog menyalternativ 3.

425
00:25:33,760 --> 00:25:36,760
Vilket nummer vill jag infoga? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Och jag ska göra bara en.

427
00:25:39,220 --> 00:25:41,720
Låt mig in numret 22.

428
00:25:41,720 --> 00:25:45,850
Så vi har början till den länkade listan som vi hade i Slidform en stund sedan.

429
00:25:45,850 --> 00:25:48,740
Hur detta införande sker egentligen?

430
00:25:48,740 --> 00:25:52,000
Faktum är 22 nu i slutet av listan.

431
00:25:52,000 --> 00:25:55,050
Så historien vi höra på scenen på måndag och påminde just nu

432
00:25:55,050 --> 00:25:57,460
måste faktiskt händer i koden.

433
00:25:57,460 --> 00:25:59,700
Låt oss ta en titt. Låt mig scrolla ner i denna fil.

434
00:25:59,700 --> 00:26:01,720
Vi kommer släta över några av funktionerna,

435
00:26:01,720 --> 00:26:05,630
men vi gå ner till, säg, Infoga funktion.

436
00:26:05,630 --> 00:26:11,720
>> Låt oss se hur vi går om att infoga en ny nod i denna länkade lista.

437
00:26:11,720 --> 00:26:14,550
Var är listan deklarerade? Nåväl, låt oss rulla hela vägen upp i toppen,

438
00:26:14,550 --> 00:26:19,970
och märker att min länkad lista huvudsak förklaras som en enda pekare som är initialt NULL.

439
00:26:19,970 --> 00:26:23,180
Så jag använder en global variabel här, som i allmänhet har vi predikat mot

440
00:26:23,180 --> 00:26:25,280
eftersom det gör din kod lite rörigt att hålla,

441
00:26:25,280 --> 00:26:29,080
Det är typ av lata, vanligen, men det är inte lat och det är inte fel och det är inte dåligt

442
00:26:29,080 --> 00:26:33,660
Om ditt program enda syfte i livet är att simulera en länkad lista.

443
00:26:33,660 --> 00:26:35,460
Vilket är exakt vad vi gör.

444
00:26:35,460 --> 00:26:39,100
Så snarare än att förklara detta i huvud och sedan måste vidarebefordra den till alla funktioner

445
00:26:39,100 --> 00:26:42,640
Vi har skrivit i detta program, vi istället inse Åh, låt oss bara göra det globala

446
00:26:42,640 --> 00:26:47,060
eftersom hela syftet med detta program är att visa en och endast en länkad lista.

447
00:26:47,060 --> 00:26:50,700
Så det känns okej. Här är mina prototyper, och vi kommer inte att gå igenom alla dessa,

448
00:26:50,700 --> 00:26:55,800
men jag skrev att raderas, ett fynd funktion en insats funktion och en tvärgående funktion.

449
00:26:55,800 --> 00:26:59,080
Men låt oss nu gå tillbaka till Infoga funktion

450
00:26:59,080 --> 00:27:01,490
och se hur det en fungerar här.

451
00:27:01,490 --> 00:27:09,940
Insatsen är på rad - nu kör vi.

452
00:27:09,940 --> 00:27:12,850
Infoga. Så det inte tar några argument, eftersom vi kommer att ställa

453
00:27:12,850 --> 00:27:15,930
användaren insidan av denna funktion för antalet de vill infoga.

454
00:27:15,930 --> 00:27:19,410
Men först, förbereder vi att ge dem lite utrymme.

455
00:27:19,410 --> 00:27:22,050
Detta är en slags kopiera och klistra in från andra exemplet.

456
00:27:22,050 --> 00:27:25,110
I så fall var vi fördela en int, den här gången vi fördela en nod.

457
00:27:25,110 --> 00:27:27,910
Jag vet inte riktigt ihåg hur många byte en nod är, men det är bra.

458
00:27:27,910 --> 00:27:30,460
Sizeof kan räkna ut för mig.

459
00:27:30,460 --> 00:27:33,340
Och varför jag kontroll av NULL i linje 120?

460
00:27:33,340 --> 00:27:37,530
Vad kan gå fel i linje 119? Ja?

461
00:27:37,530 --> 00:27:40,530
[Student svar, obegripligt]

462
00:27:40,530 --> 00:27:43,440
Bra. Bara kunde vara så att jag har bett om för mycket minne

463
00:27:43,440 --> 00:27:47,020
eller något är fel och operativsystemet inte har tillräckligt byte för att ge mig,

464
00:27:47,020 --> 00:27:50,640
så det signalerar lika mycket genom att returnera NULL, och om jag inte kryssar för det

465
00:27:50,640 --> 00:27:54,710
och jag bara blint fortsätta att använda adressen tillbaka, kan det vara NULL.

466
00:27:54,710 --> 00:27:58,400
Det kan vara någon okänd värde, inte bra om jag inte -

467
00:27:58,400 --> 00:28:00,590
faktiskt inte kommer att vara ett okänt värde. Det kan vara NULL, så jag vill inte

468
00:28:00,590 --> 00:28:02,550
att missbruka den och riskera dereferencing det.

469
00:28:02,550 --> 00:28:07,410
Om det händer, återvänder jag och vi ska låtsas som om jag inte fick tillbaka något minne alls.

470
00:28:07,410 --> 00:28:12,270
>> Annars säger jag att användaren ge mig ett nummer att infoga, kallar jag vår gamle vän getInt,

471
00:28:12,270 --> 00:28:15,530
och då detta var den nya syntaxen vi införde på måndagen.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n avses ta den adress du fick av malloc

473
00:28:20,320 --> 00:28:23,490
som representerar den första byten i ett nytt nod objekt,

474
00:28:23,490 --> 00:28:26,860
och sedan gå till fältet som heter n.

475
00:28:26,860 --> 00:28:35,270
Lite trivia fråga: Detta motsvarar vad mer kryptisk kodrad?

476
00:28:35,270 --> 00:28:38,110
Hur skulle jag ha skrivit det här? Vill du ta ett knivhugg?

477
00:28:38,110 --> 00:28:41,480
[Student svar, obegripligt]

478
00:28:41,480 --> 00:28:44,870
Bra. Med hjälp av. N, men det är inte riktigt så enkelt som det.

479
00:28:44,870 --> 00:28:47,090
Vad ska jag först måste göra? [Student svar, obegripligt]

480
00:28:47,090 --> 00:28:52,730
Bra. Jag behöver göra * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Så detta säger nya pekare är uppenbarligen en adress. Varför?

482
00:28:55,610 --> 00:28:59,520
Eftersom det var tillbaka i malloc. Den * newptr säger "gå dit"

483
00:28:59,520 --> 00:29:02,970
och sedan när du är det, kan du använda den mer bekant. N,

484
00:29:02,970 --> 00:29:05,730
men det ser bara lite ful, speciellt om vi människor kommer att

485
00:29:05,730 --> 00:29:10,360
dra pekare med pilar hela tiden, världen har standardiserat på denna pil notation,

486
00:29:10,360 --> 00:29:12,320
som gör exakt samma sak.

487
00:29:12,320 --> 00:29:16,070
Så du bara använda -> notation när saken till vänster är en pekare.

488
00:29:16,070 --> 00:29:18,790
Annars om det är en verklig struktur använder. N..

489
00:29:18,790 --> 00:29:25,800
Och sedan detta: Varför initiera newptr-> bredvid NULL?

490
00:29:25,800 --> 00:29:28,610
Vi vill inte ha en dinglande vänsterhand från slutet av scenen.

491
00:29:28,610 --> 00:29:31,630
Vi vill att den pekar rakt ner, vilket innebär slutet på denna lista

492
00:29:31,630 --> 00:29:34,980
skulle kunna vara på denna nod, så vi bättre att det är NULL.

493
00:29:34,980 --> 00:29:38,460
Och i allmänhet, initierar dina variabler eller dina data medlemmar och structs

494
00:29:38,460 --> 00:29:40,470
något är bara god praxis.

495
00:29:40,470 --> 00:29:45,170
Bara låta sopor finns och fortsätta att existera i allmänhet får du i trubbel

496
00:29:45,170 --> 00:29:48,650
om du glömmer att göra något senare.

497
00:29:48,650 --> 00:29:51,590
>> Här är några fall. Detta, återigen, är insatsen funktionen,

498
00:29:51,590 --> 00:29:54,930
och det första jag kontrollera är om variabeln kallas först,

499
00:29:54,930 --> 00:29:58,240
att den globala variabeln är NULL, betyder att det inte finns någon länkad lista.

500
00:29:58,240 --> 00:30:02,460
Vi har inte satt in några siffror, så det är trivialt att infoga nuvarande antalet

501
00:30:02,460 --> 00:30:05,240
i listan, eftersom det tillhör bara i början av listan.

502
00:30:05,240 --> 00:30:08,100
Så detta var när Anita var bara står upp här ensam, låtsas

503
00:30:08,100 --> 00:30:11,390
ingen annan var här uppe på scenen tills vi tilldelades en nod,

504
00:30:11,390 --> 00:30:13,940
hon kunde höja sin hand för första gången,

505
00:30:13,940 --> 00:30:17,420
Om alla andra hade kommit upp på scenen efter henne på måndag.

506
00:30:17,420 --> 00:30:22,900
Nu här är det lite kontroll där jag har att säga om den nya noden värde på n

507
00:30:22,900 --> 00:30:27,370
är <värdet på n i den aktuella första noden,

508
00:30:27,370 --> 00:30:29,930
som innebär att det finns en länkad lista som har börjat.

509
00:30:29,930 --> 00:30:32,330
Det finns åtminstone en nod i listan, men denna nya killen

510
00:30:32,330 --> 00:30:37,230
hör innan det, så vi måste flytta runt saker.

511
00:30:37,230 --> 00:30:43,450
Med andra ord, om listan har börjat med bara, låt oss säga,

512
00:30:43,450 --> 00:30:48,100
bara antalet 17, det är - faktiskt, kan vi göra detta tydligare.

513
00:30:48,100 --> 00:30:56,010
Om vi ​​börjar vår berättelse med en pekare här kallas första,

514
00:30:56,010 --> 00:30:59,870
och inledningsvis är det NULL, och vi för in numret 9,

515
00:30:59,870 --> 00:31:02,510
numret 9 hör klart i början av listan.

516
00:31:02,510 --> 00:31:07,400
Så låt oss låtsas vi bara malloced adressen eller numret 9 och lägga den här.

517
00:31:07,400 --> 00:31:13,170
Om första är 9 som standard innebär det första scenariot som vi diskuterat bara låta synpunkt här killen här,

518
00:31:13,170 --> 00:31:15,790
lämna detta som NULL, nu har vi nummer 9.

519
00:31:15,790 --> 00:31:18,280
Nästa nummer vill vi infoga är 17.

520
00:31:18,280 --> 00:31:22,420
17 hör hit, så vi kommer att behöva göra några logiska stega igenom detta.

521
00:31:22,420 --> 00:31:26,060
Så låt oss istället, innan vi gör det, låt oss låtsas att vi ville in numret 8.

522
00:31:26,060 --> 00:31:28,650
>> Så bara för bekvämlighets skull, kommer jag att dra här.

523
00:31:28,650 --> 00:31:30,760
Men kom ihåg, kan malloc uttrycka det mest någonstans.

524
00:31:30,760 --> 00:31:33,460
Men för teckning skull, jag lägger det här.

525
00:31:33,460 --> 00:31:38,440
Så låtsas jag bara har tilldelats en nod för antalet 8, vilket är NULL som standard.

526
00:31:38,440 --> 00:31:42,800
Vad har nu hända? Ett par saker.

527
00:31:42,800 --> 00:31:47,090
Vi gjorde detta misstag på scen på måndag där vi uppdaterat en pekare som denna,

528
00:31:47,090 --> 00:31:51,890
sedan gjorde detta, och vi hävdade - vi föräldralösa alla andra på scenen.

529
00:31:51,890 --> 00:31:54,350
Eftersom du Värre - ordningen på verksamheten här är viktigt,

530
00:31:54,350 --> 00:31:58,760
eftersom vi nu har förlorat denna nod 9 som är bara typ av flytande i rymden.

531
00:31:58,760 --> 00:32:01,150
Så detta var inte rätt inställning till måndag.

532
00:32:01,150 --> 00:32:03,330
Vi måste först göra något annat.

533
00:32:03,330 --> 00:32:06,280
Tillståndet för världen ser ut så här. Initialt har 8 tilldelats.

534
00:32:06,280 --> 00:32:10,550
Vad skulle vara ett bättre sätt att sätta 8?

535
00:32:10,550 --> 00:32:14,720
Istället för att uppdatera denna pekare först bara uppdatera denna en här i stället.

536
00:32:14,720 --> 00:32:17,720
Så vi behöver en kodrad som kommer att vända denna NULL tecken

537
00:32:17,720 --> 00:32:22,020
till en verklig pekare som är pekar på noden 9,

538
00:32:22,020 --> 00:32:27,970
och då kan vi säkert ändra först peka på den här killen här.

539
00:32:27,970 --> 00:32:31,330
Nu har vi en lista, en länkad lista, av två element.

540
00:32:31,330 --> 00:32:33,580
Och vad ser det faktiskt som här?

541
00:32:33,580 --> 00:32:36,900
Om vi ​​tittar på koden, märker att jag har gjort just detta.

542
00:32:36,900 --> 00:32:41,970
Jag har sagt newptr, och i denna berättelse, var newptr pekar på den här killen.

543
00:32:41,970 --> 00:32:45,520
>> Så låt mig dra en sak, och jag skulle ha lämnat lite mer utrymme för detta.

544
00:32:45,520 --> 00:32:48,540
Så förlåt den lilla lilla ritning.

545
00:32:48,540 --> 00:32:52,140
Den här killen heter newptr.

546
00:32:52,140 --> 00:32:57,940
Det är den variabel som vi förklarade några rader tidigare, i linje - strax över 25.

547
00:32:57,940 --> 00:33:03,430
Och det pekar på 8. Så när jag säger newptr-> nästa, det betyder att gå till struct

548
00:33:03,430 --> 00:33:07,910
som är som pekas på av newptr, så här är vi, gå dit.

549
00:33:07,910 --> 00:33:13,990
Sedan pilen säger få nästa fält och sedan = säger sätta vilket värde där?

550
00:33:13,990 --> 00:33:17,280
Det värde som var i första, vilket värde var först?

551
00:33:17,280 --> 00:33:21,930
Först pekade på denna nod, så innebär det nu bör peka på denna nod.

552
00:33:21,930 --> 00:33:25,660
Med andra ord ser det än en löjlig röra med min handstil,

553
00:33:25,660 --> 00:33:28,620
vad är en enkel idé att bara flytta dessa pilar runt

554
00:33:28,620 --> 00:33:31,560
översätter till kod med just detta en liner.

555
00:33:31,560 --> 00:33:38,110
Förvara vad som är först i nästa fält och sedan uppdatera vad första faktiskt är.

556
00:33:38,110 --> 00:33:40,900
Låt oss gå vidare och snabbspola genom en del av detta,

557
00:33:40,900 --> 00:33:44,220
och titta bara på denna svans insättning för nu.

558
00:33:44,220 --> 00:33:51,210
Anta att jag kommer till den punkt där jag tycker att nästa fält av någon nod är NULL.

559
00:33:51,210 --> 00:33:53,410
Och vid denna punkt i berättelsen, en detalj som jag släta över

560
00:33:53,410 --> 00:33:58,170
är att jag har infört en pekare upp här i linje 142, föregångaren pekare.

561
00:33:58,170 --> 00:34:01,320
Huvudsak vid denna punkt i berättelsen, när listan blir lång,

562
00:34:01,320 --> 00:34:04,800
Jag slags behöver gå den med två fingrar för om jag går för långt,

563
00:34:04,800 --> 00:34:08,219
minns en enda lång lista kan du inte gå tillbaka.

564
00:34:08,219 --> 00:34:13,659
Så denna idé om predptr är min vänstra finger och newptr - inte newptr.

565
00:34:13,659 --> 00:34:17,199
En annan pekare som är här är min andra finger, och jag är bara typ av promenader i listan.

566
00:34:17,199 --> 00:34:22,179
Det är därför som finns. Men låt oss bara betrakta en av de enklare fallen här.

567
00:34:22,179 --> 00:34:26,620
Om det pekare nästa fält är NULL, vad är den logiska innebörden?

568
00:34:26,620 --> 00:34:30,840
Om du korsar denna lista och du träffar en NULL-pekare?

569
00:34:30,840 --> 00:34:35,780
Du är i slutet av listan, och så koden för att sedan lägga detta en ytterligare element

570
00:34:35,780 --> 00:34:41,230
är typ av den intuitiva tar att nod vars nästa pekare är NULL,

571
00:34:41,230 --> 00:34:46,120
så detta är för närvarande NULL, och ändra det, men för att vara adressen till den nya noden.

572
00:34:46,120 --> 00:34:52,260
Så vi bara dra i kod på pilen som vi drog på scenen genom att höja någons vänstra hand.

573
00:34:52,260 --> 00:34:54,070
>> Och så att jag viftar mina händer på för nu,

574
00:34:54,070 --> 00:34:58,020
bara för att jag tycker det är lätt att gå vilse när vi gör det i denna typ av miljö,

575
00:34:58,020 --> 00:35:00,600
kontrollerar för insättning på listans mitten.

576
00:35:00,600 --> 00:35:03,220
Men bara intuitivt, behöver det hända om du vill räkna ut

577
00:35:03,220 --> 00:35:06,600
där någon numret tillhör i mitten är du har att gå det

578
00:35:06,600 --> 00:35:09,510
med mer än ett finger, mer än en pekare,

579
00:35:09,510 --> 00:35:12,920
räkna ut där den hör hemma i kontroll är elementet <den nuvarande,

580
00:35:12,920 --> 00:35:15,450
> Den nuvarande, och när du hittar denna plats,

581
00:35:15,450 --> 00:35:20,400
då måste man göra denna typ av skal spel där du flyttar visarna runt mycket noggrant.

582
00:35:20,400 --> 00:35:23,850
Och det svaret, om du vill att resonera igenom detta hemma på egen hand,

583
00:35:23,850 --> 00:35:28,340
handlar om bara dessa två rader kod, men ordningen på dessa linjer är super viktigt.

584
00:35:28,340 --> 00:35:31,390
För om du tappar någons hand och höja någon annans i fel ordning,

585
00:35:31,390 --> 00:35:34,580
igen, kan du hamna föräldralösa i listan.

586
00:35:34,580 --> 00:35:39,500
För att sammanfatta mer konceptuellt är införandet på svansen relativt enkelt.

587
00:35:39,500 --> 00:35:42,940
Insättningen vid huvudet är också relativt enkelt,

588
00:35:42,940 --> 00:35:45,580
men du måste uppdatera ytterligare pekare denna gång

589
00:35:45,580 --> 00:35:47,930
att pressa nummer 5 i listan här,

590
00:35:47,930 --> 00:35:51,560
och sedan insättning i mitten innebär ännu mer arbete,

591
00:35:51,560 --> 00:35:56,130
att mycket noga in numret 20 i dess rätta plats,

592
00:35:56,130 --> 00:35:58,350
vilken är mellan 17 och 22.

593
00:35:58,350 --> 00:36:02,700
Så du måste göra något liknande har den nya noden 20 pekar på 22,

594
00:36:02,700 --> 00:36:08,470
och sedan behöver vilken nod är pekare som skall uppdateras senast?

595
00:36:08,470 --> 00:36:10,630
Det är 17, att faktiskt sätta in det.

596
00:36:10,630 --> 00:36:14,080
Så återigen, jag skjuta den faktiska koden för just genomförandet.

597
00:36:14,080 --> 00:36:17,280
>> Vid en första anblick är det lite överväldigande, men det är egentligen bara en oändlig loop

598
00:36:17,280 --> 00:36:21,770
som är looping, looping, looping, looping, och bryta så fort du träffar NULL-pekare,

599
00:36:21,770 --> 00:36:24,590
då du kan göra den nödvändiga insättningen.

600
00:36:24,590 --> 00:36:30,960
Detta är alltså representativ länkad lista insättning kod.

601
00:36:30,960 --> 00:36:34,590
Det var typ av en hel del, och det känns som vi har löst ett problem,

602
00:36:34,590 --> 00:36:36,940
men vi har infört en helt annan en. Ärligt talat, vi har spenderat all denna tid

603
00:36:36,940 --> 00:36:40,540
på stora O och Ω och gångtid, försöka lösa problem snabbare,

604
00:36:40,540 --> 00:36:43,270
och här tar vi ett stort steg bakåt, det känns.

605
00:36:43,270 --> 00:36:45,380
Och ändå, om målet är att lagra data,

606
00:36:45,380 --> 00:36:48,010
det känns som den heliga Graal, som vi sade på måndagen skulle verkligen vara

607
00:36:48,010 --> 00:36:50,470
att lagra saker direkt.

608
00:36:50,470 --> 00:36:53,930
>> I själva verket, anta att vi gjorde avsatt länkad lista för ett ögonblick

609
00:36:53,930 --> 00:36:56,000
och vi introducerade istället begreppet tabell.

610
00:36:56,000 --> 00:36:59,110
Och låt oss bara tänka på ett bord för ett ögonblick som en matris.

611
00:36:59,110 --> 00:37:03,790
Denna matris och detta fall har här några 26 element, 0 till 25,

612
00:37:03,790 --> 00:37:07,940
och antar att du behövde bit av lagring för namn:

613
00:37:07,940 --> 00:37:10,350
Alice och Bob och Charlie och liknande.

614
00:37:10,350 --> 00:37:12,880
Och du behöver datastruktur för att lagra dessa namn.

615
00:37:12,880 --> 00:37:15,000
Tja, kan du använda något som liknar en länkad lista

616
00:37:15,000 --> 00:37:20,260
och du kan gå på listan sätter Alice före Bob och Charlie efter Bob och så vidare.

617
00:37:20,260 --> 00:37:23,850
Och faktum är att om du vill se koden som det i förbigående,

618
00:37:23,850 --> 00:37:27,230
vet att i list2.h vi göra just det.

619
00:37:27,230 --> 00:37:30,610
Vi kommer inte att gå igenom denna kod, men detta är en variant av det första exemplet

620
00:37:30,610 --> 00:37:34,640
som introducerar en annan struktur som vi har sett tidigare kallade student,

621
00:37:34,640 --> 00:37:40,330
och sedan vad det faktiskt lagrar i den länkade listan är en pekare till en student struktur

622
00:37:40,330 --> 00:37:44,520
snarare än en enkel liten heltal, N.

623
00:37:44,520 --> 00:37:46,900
So inser att det finns kod där som innebär faktiska strängar,

624
00:37:46,900 --> 00:37:49,940
men om målet till hands egentligen nu är att ta itu med effektiviteten problemet,

625
00:37:49,940 --> 00:37:53,380
skulle det inte vara trevligt om vi gett ett objekt som heter Alice,

626
00:37:53,380 --> 00:37:56,020
Vi vill sätta henne i rätt läge i en datastruktur,

627
00:37:56,020 --> 00:37:58,860
det känns som att det skulle vara skönt att bara sätta Alice,

628
00:37:58,860 --> 00:38:01,180
vars namn börjar med A i första läget.

629
00:38:01,180 --> 00:38:05,270
Och Bob, vars namn börjar med B, i den andra platsen.

630
00:38:05,270 --> 00:38:09,580
Med en rad, eller låt oss börja kalla det ett bord, en hash bord på det,

631
00:38:09,580 --> 00:38:13,650
vi kan göra just det. Om vi ​​får ett namn som Alice,

632
00:38:13,650 --> 00:38:16,700
en sträng som Alice, var du sätter en-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Vi behöver en hueristic. Vi behöver en funktion för att ta lite input som Alice

634
00:38:20,540 --> 00:38:24,610
och returnera ett svar, "Put Alice på den här platsen."

635
00:38:24,610 --> 00:38:28,720
Och den här funktionen svarta lådan, kommer att kallas en hashfunktion.

636
00:38:28,720 --> 00:38:32,330
>> En hashfunktion är något som tar en ingång, som "Alice",

637
00:38:32,330 --> 00:38:38,080
och återgår till dig, vanligen den numeriska plats i någon datastruktur där Alice hör hemma.

638
00:38:38,080 --> 00:38:40,830
I detta fall bör vi hashfunktion vara relativt enkel.

639
00:38:40,830 --> 00:38:47,510
Vår hashfunktion ska säga, om du får "Alice", vilken karaktär skulle jag bry mig om?

640
00:38:47,510 --> 00:38:55,660
Den första. Så jag ser på [0], och sedan säger jag om [0] karaktär är A returnera antalet 0.

641
00:38:55,660 --> 00:39:01,130
Om det är B, tillbaka 1. Om det är C, återvänder 2, och så vidare.

642
00:39:01,130 --> 00:39:05,940
Alla 0 index, och som skulle tillåta mig att sätta Alice och sedan Bob och sedan Charlie och så vidare

643
00:39:05,940 --> 00:39:10,960
i denna datastruktur. Men det finns ett problem.

644
00:39:10,960 --> 00:39:13,060
Tänk om Anita kommer tillsammans igen?

645
00:39:13,060 --> 00:39:17,510
Var sätter vi Anita? Hennes namn också börjar med bokstaven A,

646
00:39:17,510 --> 00:39:20,330
och det känns som vi har gjort en ännu större röra av detta problem.

647
00:39:20,330 --> 00:39:24,380
Vi har nu omedelbar insättning, konstant tid insättning, i en datastruktur

648
00:39:24,380 --> 00:39:27,100
snarare än värre fall linjär,

649
00:39:27,100 --> 00:39:29,510
men vad kan vi göra med Anita i detta fall?

650
00:39:29,510 --> 00:39:34,110
Vilka är de två alternativen, egentligen? Ja?

651
00:39:34,110 --> 00:39:37,410
[Student svar, obegripligt] Okej, så vi kunde få en annan dimension.

652
00:39:37,410 --> 00:39:42,320
Det är bra. Så vi kan bygga saker i 3D som vi pratade om muntligt på måndag.

653
00:39:42,320 --> 00:39:46,700
Vi kunde lägga till ytterligare tillgång här, men antar att nej, jag försöker hålla det enkelt.

654
00:39:46,700 --> 00:39:50,160
Hela målet här är att ha omedelbar konstant tid tillgång,

655
00:39:50,160 --> 00:39:52,170
så det är att lägga för mycket komplexitet.

656
00:39:52,170 --> 00:39:55,970
Vilka andra alternativ när försöker sätta Anita i denna datastruktur? Ja?

657
00:39:55,970 --> 00:39:58,610
[Student svar, obegripliga] Bra. Så vi kunde flytta alla andra ner,

658
00:39:58,610 --> 00:40:03,040
som Charlie knuffar ned Bob och Alice, och sedan sätter vi Anita där hon verkligen vill vara.

659
00:40:03,040 --> 00:40:05,660
>> Naturligtvis nu, finns det en sidoeffekt av denna.

660
00:40:05,660 --> 00:40:09,000
Detta datastruktur är förmodligen bra inte för att vi vill infoga människor när

661
00:40:09,000 --> 00:40:11,250
men eftersom vi vill kontrollera om de är där senare

662
00:40:11,250 --> 00:40:13,600
om vi vill skriva ut alla namn i datastrukturen.

663
00:40:13,600 --> 00:40:15,850
Vi ska göra något med dessa data så småningom.

664
00:40:15,850 --> 00:40:20,810
Så nu har vi typ av skruvade över Alice, som inte längre var hon ska vara.

665
00:40:20,810 --> 00:40:23,880
Inte heller är Bob, inte heller Charlie.

666
00:40:23,880 --> 00:40:26,060
Så kanske det är inte en så bra idé.

667
00:40:26,060 --> 00:40:28,830
Men i själva verket är detta en möjlighet. Vi kunde skifta alla ned,

668
00:40:28,830 --> 00:40:32,240
eller fan, kom Anita sent till spelet, varför inte vi bara sätta Anita

669
00:40:32,240 --> 00:40:35,870
inte här, inte här, inte här, låt oss bara sätta henne lite lägre i listan.

670
00:40:35,870 --> 00:40:38,680
Men sedan detta problem börjar att överlåta igen.

671
00:40:38,680 --> 00:40:41,630
Du kanske kan hitta Alice direkt, baserat på hennes förnamn.

672
00:40:41,630 --> 00:40:44,320
Och Bob direkt, och Charlie. Men då du letar efter Anita,

673
00:40:44,320 --> 00:40:46,360
och du ser, hmm, är Alice i vägen.

674
00:40:46,360 --> 00:40:48,770
Nåväl, låt mig kolla nedan Alice. Bob är inte Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie är inte Anita. Åh, det är Anita.

676
00:40:51,850 --> 00:40:54,720
Och om du fortsätter att tåget av logik hela vägen,

677
00:40:54,720 --> 00:41:00,690
vad är det värsta gångtid hitta eller sätta Anita i denna nya datastruktur?

678
00:41:00,690 --> 00:41:03,280
Det är O (n), eller hur?

679
00:41:03,280 --> 00:41:06,280
Eftersom det i värsta fall, det finns Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
ända ner till någon som heter "Y", så det finns bara en plats kvar.

681
00:41:10,150 --> 00:41:13,950
Tack och lov har vi ingen kallas "Z", så vi satte Anita längst ner.

682
00:41:13,950 --> 00:41:16,040
>> Vi har inte riktigt löst problemet.

683
00:41:16,040 --> 00:41:19,890
Så kanske vi behöver införa detta tredje dimensionen.

684
00:41:19,890 --> 00:41:22,230
Och det visar sig, om vi inför denna tredje dimension,

685
00:41:22,230 --> 00:41:25,240
Vi kan inte göra det perfekt, men den heliga gralen kommer att få

686
00:41:25,240 --> 00:41:28,370
konstant tid insättning och dynamiska insättningar så att

687
00:41:28,370 --> 00:41:30,960
Vi behöver inte hård-kod en rad storlek 26.

688
00:41:30,960 --> 00:41:34,400
Vi kan infoga så många namn som vi vill, men låt oss ta vår 5-minuters paus här

689
00:41:34,400 --> 00:41:38,790
och sedan göra det ordentligt.

690
00:41:38,790 --> 00:41:46,020
Okej. Jag satt historien upp ganska artificiellt där

691
00:41:46,020 --> 00:41:48,670
genom att välja Alice och sedan Bob och sedan Charlie och sedan Anita,

692
00:41:48,670 --> 00:41:51,000
vars namn var uppenbarligen kommer att kollidera med Alice.

693
00:41:51,000 --> 00:41:54,120
Men frågan vi slutade i måndags med är hur troligt är det

694
00:41:54,120 --> 00:41:56,370
att du skulle få den här typen av kollisioner? Med andra ord,

695
00:41:56,370 --> 00:42:00,490
om vi börjar använda denna tabellform struktur, vilket egentligen bara en array,

696
00:42:00,490 --> 00:42:02,460
i detta fall av 26 platser,

697
00:42:02,460 --> 00:42:05,740
vad händer om våra insatser i stället jämnt fördelade?

698
00:42:05,740 --> 00:42:09,620
Det är inte artificiellt Alice och Bob och Charlie och David och så vidare alfabetiskt,

699
00:42:09,620 --> 00:42:12,380
det är jämnt fördelad över A till Z.

700
00:42:12,380 --> 00:42:15,220
>> Vi kanske bara har tur och vi kommer inte att ha två A: s eller två B: s

701
00:42:15,220 --> 00:42:17,640
med mycket hög sannolikhet, men som någon påpekade,

702
00:42:17,640 --> 00:42:20,730
Om vi ​​generaliserat detta problem och inte göra 0 till 25

703
00:42:20,730 --> 00:42:26,060
men, säg, 0 till 364 eller 65, ofta antalet dagar i en typisk år,

704
00:42:26,060 --> 00:42:31,170
och ställde frågan, "Vad är sannolikheten för att två av oss i detta rum har samma födelsedag?"

705
00:42:31,170 --> 00:42:34,600
Andra ord, vad är sannolikheten att två av oss har ett namn som börjar med A?

706
00:42:34,600 --> 00:42:37,190
Den typ av fråga är densamma, men den här adressen utrymme,

707
00:42:37,190 --> 00:42:39,940
denna sökning utrymme är större när det gäller födelsedagar,

708
00:42:39,940 --> 00:42:42,820
eftersom vi har så många fler dagar på året än bokstäver i alfabetet.

709
00:42:42,820 --> 00:42:44,910
Vad är sannolikheten för en kollision?

710
00:42:44,910 --> 00:42:48,410
Tja, vi kan tänka på detta genom att räkna ut matten på motsatt sätt.

711
00:42:48,410 --> 00:42:50,580
Vad är sannolikheten för inga kollisioner?

712
00:42:50,580 --> 00:42:53,970
Bra, säger detta uttryck här att vad är sannolikheten

713
00:42:53,970 --> 00:42:58,770
om det finns bara en person i detta rum, att de har en unik födelsedag?

714
00:42:58,770 --> 00:43:01,190
Det är 100%. För om det finns bara en person i rummet,

715
00:43:01,190 --> 00:43:03,940
hans eller hennes födelsedag kan vara någon av de 365 dagar av året.

716
00:43:03,940 --> 00:43:08,650
Så 365/365 optioner ger mig ett värde av 1.

717
00:43:08,650 --> 00:43:11,250
Så sannolikheten i fråga just nu är bara 1.

718
00:43:11,250 --> 00:43:13,270
Men om det finns en annan person i rummet,

719
00:43:13,270 --> 00:43:16,490
vad är sannolikheten att deras födelsedag är annorlunda?

720
00:43:16,490 --> 00:43:20,680
Det finns bara 364 möjliga dagar, ignorerar skottår

721
00:43:20,680 --> 00:43:23,580
för deras födelsedag inte kolliderar med andra personer.

722
00:43:23,580 --> 00:43:31,920
Så 364/365. Om en tredje person kommer in, det är 363/365, och så vidare.

723
00:43:31,920 --> 00:43:35,790
Så vi håller multiplicera ihop dessa fraktioner, som blir mindre och mindre,

724
00:43:35,790 --> 00:43:40,720
att räkna ut vad är sannolikheten att vi alla har unika födelsedagar?

725
00:43:40,720 --> 00:43:43,570
Men då kan vi ju bara ta det svaret och vända runt

726
00:43:43,570 --> 00:43:47,210
och gör 1 minus allt detta, ett uttryck som vi kommer så småningom att få

727
00:43:47,210 --> 00:43:51,250
om du kommer ihåg baksidan av din matte böcker, ser det lite ungefär så här,

728
00:43:51,250 --> 00:43:54,590
vilket är mycket mer lättolkad grafiskt.

729
00:43:54,590 --> 00:43:57,820
Och den här bilden här har på x-axeln antalet födelsedagar,

730
00:43:57,820 --> 00:44:02,030
eller antal personer med födelsedagar, och på y-axeln är sannolikheten för en match.

731
00:44:02,030 --> 00:44:06,060
Och vad detta säger är att om du har, låt oss säga, även,

732
00:44:06,060 --> 00:44:10,860
låt oss välja något som 22, 23.

733
00:44:10,860 --> 00:44:13,160
Om det finns 22 eller 23 personer i rummet,

734
00:44:13,160 --> 00:44:17,100
sannolikheten för att två av dessa mycket få människor kommer att ha samma födelsedag

735
00:44:17,100 --> 00:44:19,560
är faktiskt super hög, kombinatoriskt.

736
00:44:19,560 --> 00:44:23,450
50% odds som i en klass för bara 22 personer, ett seminarium, praktiskt,

737
00:44:23,450 --> 00:44:25,790
2 av dessa människor kommer att ha samma födelsedag.

738
00:44:25,790 --> 00:44:28,520
Eftersom det finns så många sätt som du kan ha samma födelsedag.

739
00:44:28,520 --> 00:44:31,110
Ännu värre, om man tittar på den högra sidan av diagrammet,

740
00:44:31,110 --> 00:44:34,040
med den tid du har en klass med 58 elever i den,

741
00:44:34,040 --> 00:44:39,270
sannolikheten för 2 personer med en födelsedag är super, super hög, nästan 100%.

742
00:44:39,270 --> 00:44:41,880
Nu är den sortens en rolig faktum om verkligheten.

743
00:44:41,880 --> 00:44:45,850
>> Men konsekvenserna, nu för datastrukturer och lagra information

744
00:44:45,850 --> 00:44:51,100
innebär att bara förutsatt att du har en fin, ren, jämn fördelning av uppgifter

745
00:44:51,100 --> 00:44:53,650
och du har en tillräckligt stor mängd för att passa en massa saker

746
00:44:53,650 --> 00:44:59,360
betyder inte att du kommer att få människor i unika platser.

747
00:44:59,360 --> 00:45:03,810
Du kommer att få kollisioner. Så denna föreställning om hashning, som det kallas,

748
00:45:03,810 --> 00:45:07,450
ta en ingång som "Alice" och massera det på något sätt

749
00:45:07,450 --> 00:45:10,190
och sedan få tillbaka ett svar som 0 eller 1 eller 2.

750
00:45:10,190 --> 00:45:17,500
Att få tillbaka en del utdata från funktionen plågas av denna sannolikhet för kollision.

751
00:45:17,500 --> 00:45:19,530
Så hur kan vi hantera dessa kollisioner?

752
00:45:19,530 --> 00:45:21,940
Tja, å ena fallet kan vi ta tanken att föreslogs.

753
00:45:21,940 --> 00:45:25,100
Vi kan bara flytta alla ner, eller kanske, lite enklare,

754
00:45:25,100 --> 00:45:29,870
snarare än att flytta alla andra, låt oss bara gå Anita till botten av den tillgängliga platsen.

755
00:45:29,870 --> 00:45:32,810
Så om Alice är 0, är ​​Bob i 1, Charlie i 2,

756
00:45:32,810 --> 00:45:35,260
Vi ska bara sätta Anita på plats 3.

757
00:45:35,260 --> 00:45:38,860
Och detta är en teknik datastrukturer som kallas linjär sondering.

758
00:45:38,860 --> 00:45:41,310
Linjär eftersom du bara gå denna linje, och du är typ av sondering

759
00:45:41,310 --> 00:45:43,640
för tillgängliga platser i datastrukturen.

760
00:45:43,640 --> 00:45:46,210
Naturligtvis tillfaller detta i O (n).

761
00:45:46,210 --> 00:45:49,590
Om datastrukturen är verkligen full, det finns 25 personer i det redan,

762
00:45:49,590 --> 00:45:54,120
och sedan Anita dyker slutar hon upp på vad som skulle vara plats Z, och det är bra.

763
00:45:54,120 --> 00:45:56,540
Hon passar fortfarande, och vi kan hitta henne senare.

764
00:45:56,540 --> 00:46:00,100
>> Men detta var i strid med målet att påskynda saker.

765
00:46:00,100 --> 00:46:02,530
Så vad händer om vi istället introducerade denna tredje dimension?

766
00:46:02,530 --> 00:46:06,400
Denna teknik är i allmänhet kallas separat kedja, eller har kedjor.

767
00:46:06,400 --> 00:46:10,030
Och vad en hash tabell är nu detta tabellform struktur,

768
00:46:10,030 --> 00:46:13,450
ditt bord är bara en rad pekare.

769
00:46:13,450 --> 00:46:18,230
Men vad dessa pekare pekar på är Gissa vad?

770
00:46:18,230 --> 00:46:21,970
En länkad lista. Så vad händer om vi tar det bästa av båda dessa världar?

771
00:46:21,970 --> 00:46:26,500
Vi använder arrayer för de initiala index

772
00:46:26,500 --> 00:46:32,070
i datastrukturen så att vi kan gå direkt till [0] [1], [30] eller så vidare,

773
00:46:32,070 --> 00:46:36,480
men så att vi har en viss flexibilitet och vi kan passa Anita och Alice och Adam

774
00:46:36,480 --> 00:46:38,630
och alla andra Ett namn,

775
00:46:38,630 --> 00:46:43,470
vi låter istället den andra axeln växa godtyckligt.

776
00:46:43,470 --> 00:46:47,340
Och vi äntligen, och med måndag, har den uttrycksfulla kapacitet med länkad lista.

777
00:46:47,340 --> 00:46:49,530
Vi kan växa en datastruktur godtyckligt.

778
00:46:49,530 --> 00:46:52,450
Alternativt kan vi bara göra en stor 2-dimensionell matris,

779
00:46:52,450 --> 00:46:57,190
men det kommer att bli en hemsk situation om en av raderna i en 2-dimensionell array

780
00:46:57,190 --> 00:47:01,280
inte är tillräckligt stort för den extra person vars namn råkar börja med A.

781
00:47:01,280 --> 00:47:04,200
Gud förbjude att vi måste omfördela en stor 2-dimensionell struktur

782
00:47:04,200 --> 00:47:06,600
bara för att det finns så många människor som heter A,

783
00:47:06,600 --> 00:47:09,480
särskilt när det finns så få människor som heter Z något.

784
00:47:09,480 --> 00:47:12,170
Det kommer bara att vara en mycket gles datastruktur.

785
00:47:12,170 --> 00:47:15,400
Så det är inte perfekt på något sätt, men nu har vi åtminstone har förmågan

786
00:47:15,400 --> 00:47:19,090
att omedelbart hitta där Alice eller Anita tillhör,

787
00:47:19,090 --> 00:47:21,090
åtminstone i termer av den vertikala axeln,

788
00:47:21,090 --> 00:47:25,850
och sedan har vi bara bestämma var att sätta Anita eller Alice i länkad lista.

789
00:47:25,850 --> 00:47:32,480
Om vi ​​inte bryr oss om sortering saker, hur snabbt vi sätter Alice i en struktur som denna?

790
00:47:32,480 --> 00:47:35,370
Det är konstant tid. Vi index i [0], och om ingen är där,

791
00:47:35,370 --> 00:47:37,550
Alice går i början av det länkad lista.

792
00:47:37,550 --> 00:47:40,000
Men det är inte en stor affär. För om Anita kommer sedan längs

793
00:47:40,000 --> 00:47:42,160
visst antal steg senare, inte var Anita tillhör?

794
00:47:42,160 --> 00:47:45,140
Tja, [0]. OOP. Alice är redan i det länkade listan.

795
00:47:45,140 --> 00:47:47,760
>> Men om vi inte bryr oss om sortering dessa namn,

796
00:47:47,760 --> 00:47:53,580
Vi kan bara flytta Alice över, insats Anita, men även det är konstant tid.

797
00:47:53,580 --> 00:47:57,010
Även om det finns Alice och Adam och alla dessa andra A namn,

798
00:47:57,010 --> 00:47:59,410
Det är egentligen inte flytta dem fysiskt. Varför?

799
00:47:59,410 --> 00:48:04,090
Eftersom vi just gjorde här med länkad lista, vem vet var dessa noder är egentligen?

800
00:48:04,090 --> 00:48:06,550
Allt du behöver göra är att flytta brödsmulor.

801
00:48:06,550 --> 00:48:10,930
Flytta pilarna runt, du behöver inte fysiskt flytta data runt.

802
00:48:10,930 --> 00:48:14,610
Så vi kan sätta in Anita, i så fall, direkt. Konstant tid.

803
00:48:14,610 --> 00:48:20,250
Så vi har konstant tid lookup, och konstant tid insättning av någon som Anita.

804
00:48:20,250 --> 00:48:22,740
Men typ av övertydlighet världen.

805
00:48:22,740 --> 00:48:28,510
Tänk om vi senare vill hitta Alice?

806
00:48:28,510 --> 00:48:31,050
Tänk om vi senare vill hitta Alice?

807
00:48:31,050 --> 00:48:35,690
Hur många steg är att kommer att ta?

808
00:48:35,690 --> 00:48:37,850
[Student svar, obegripligt]

809
00:48:37,850 --> 00:48:40,950
Exakt. Antalet personer innan Alice i den länkade listan.

810
00:48:40,950 --> 00:48:45,420
Så det är inte helt perfekt, eftersom vår datastruktur, igen, har denna vertikala tillgång

811
00:48:45,420 --> 00:48:50,240
och då har dessa länkade listor hängande - faktiskt, låt oss inte dra det en en matris.

812
00:48:50,240 --> 00:48:56,020
Det har de länkade listor hängande av det som ser lite ut ungefär så här.

813
00:48:56,020 --> 00:48:59,110
Men problemet är om Alice och Adam och alla dessa andra A namn

814
00:48:59,110 --> 00:49:01,720
hamna mer och mer borta,

815
00:49:01,720 --> 00:49:04,810
hitta någon kunde sluta med ett gäng steg,

816
00:49:04,810 --> 00:49:06,670
bcause du korsa den länkade listan,

817
00:49:06,670 --> 00:49:08,090
vilket är en linjär operation.

818
00:49:08,090 --> 00:49:14,270
Så egentligen är då införingen tiden slut O (n), där n är antalet element i listan.

819
00:49:14,270 --> 00:49:21,780
Divided av, låt oss godtyckligt kalla det m, där m är antalet länkade listor

820
00:49:21,780 --> 00:49:24,500
som vi har i denna vertikala axel.

821
00:49:24,500 --> 00:49:27,180
Med andra ord, om vi verkligen tar en jämn fördelning av namn,

822
00:49:27,180 --> 00:49:30,150
helt orealistiskt. Det finns naturligtvis mer av vissa bokstäver än andra.

823
00:49:30,150 --> 00:49:32,580
>> Men om vi antar för tillfället en jämn fördelning,

824
00:49:32,580 --> 00:49:37,350
och vi har n TOTALA människor och m Total kedjor

825
00:49:37,350 --> 00:49:40,630
tillgänglig för oss, sedan längden av vardera av dessa kedjor

826
00:49:40,630 --> 00:49:44,380
ganska enkelt kommer att bli den totala n dividerat med antalet kedjor.

827
00:49:44,380 --> 00:49:48,900
Så n / m. Men här är där vi kan vara allt matematiskt smart.

828
00:49:48,900 --> 00:49:53,030
m är en konstant, eftersom det finns ett fast antal av dessa.

829
00:49:53,030 --> 00:49:54,620
Du kommer att deklarera din array i början,

830
00:49:54,620 --> 00:49:58,450
och vi är inte storleksändring den vertikala axeln. Per definition förblir det fast.

831
00:49:58,450 --> 00:50:01,220
Det är bara den horisontella axeln, så att säga, som är förändras.

832
00:50:01,220 --> 00:50:04,760
Så tekniskt är detta en konstant. Så nu, införandet tiden

833
00:50:04,760 --> 00:50:09,700
är ganska mycket O (n).

834
00:50:09,700 --> 00:50:12,410
Så det inte känns så mycket bättre.

835
00:50:12,410 --> 00:50:14,940
Men vad är sanningen här? Nåväl, hela tiden, i flera veckor,

836
00:50:14,940 --> 00:50:20,640
Vi har sagt O (n ²). O (n), 2 x n ^, - n, dividerat med 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Det är bara n ^. Men nu, i denna del av terminen,

838
00:50:23,580 --> 00:50:25,560
Vi kan börja tala om den verkliga världen igen.

839
00:50:25,560 --> 00:50:31,520
Och n / m är absolut snabbare än bara n ensam.

840
00:50:31,520 --> 00:50:35,170
Om du har tusen namn, och du bryta upp dem i flera hinkar

841
00:50:35,170 --> 00:50:37,820
så att du har bara tio namn i varje av dessa kedjor,

842
00:50:37,820 --> 00:50:41,670
absolut söka tio saker kommer att vara snabbare än tusen saker.

843
00:50:41,670 --> 00:50:43,740
Och så en av de kommande problem uppsättningar kommer att utmana dig

844
00:50:43,740 --> 00:50:46,100
att tänka just att även om, ja,

845
00:50:46,100 --> 00:50:49,520
asymptotiskt och matematiskt, är detta fortfarande bara linjär,

846
00:50:49,520 --> 00:50:51,700
som suger i allmänhet när man försöker hitta saker.

847
00:50:51,700 --> 00:50:54,530
I verkligheten kommer det att vara snabbare än den

848
00:50:54,530 --> 00:50:56,520
på grund av denna divisor.

849
00:50:56,520 --> 00:50:58,310
Och så finns det återigen kommer att bli denna avvägning

850
00:50:58,310 --> 00:51:01,390
och denna konflikt mellan teori och verklighet,

851
00:51:01,390 --> 00:51:03,550
och en av rattarna börjar vända på denna punkt i terminen

852
00:51:03,550 --> 00:51:07,510
är mer av verkligheten en som vi sorts förbereda semster slut,

853
00:51:07,510 --> 00:51:09,280
när vi introducerar en värld av webbprogrammering,

854
00:51:09,280 --> 00:51:11,530
där verkligen är prestandan kommer att räkna eftersom användarna kommer att

855
00:51:11,530 --> 00:51:14,880
börjar känna och uppskatta dåliga designbeslut.

856
00:51:14,880 --> 00:51:19,950
>> Så hur kan du gå om att genomföra en länkad - en hash tabell med 31 element?

857
00:51:19,950 --> 00:51:22,600
Och det tidigare exemplet var godtyckligt om födelsedagar.

858
00:51:22,600 --> 00:51:26,190
Om någon har en födelsedag den 1 januari eller 1 februari kommer vi att sätta dem i detta hink.

859
00:51:26,190 --> 00:51:28,960
Om det är 2 januari, 2 februari, mars 2, vi lägger dem i denna hink.

860
00:51:28,960 --> 00:51:32,220
Det är därför det var 31. Hur förklarar man en hash-tabell?

861
00:51:32,220 --> 00:51:37,480
Det kan vara ganska enkelt, är nod * Tabell mitt godtyckligt namn för det, [31].

862
00:51:37,480 --> 00:51:42,400
Det ger mig 31 pekare till noderna,

863
00:51:42,400 --> 00:51:45,370
och som gör att jag kan ha 31 pekare till länkade listor

864
00:51:45,370 --> 00:51:48,800
även om dessa kedjor är initialt NULL.

865
00:51:48,800 --> 00:51:54,860
Vad vill jag sätta om jag vill lagra "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Tja, vi måste packa dessa saker i en struktur

867
00:51:57,010 --> 00:52:00,530
eftersom vi behöver Alice peka på Bob, peka på Charlie, och så vidare.

868
00:52:00,530 --> 00:52:04,940
Vi kan inte bara ha namnen ensam, så jag kunde skapa en ny struktur som kallas nod här.

869
00:52:04,940 --> 00:52:08,310
>> Vad är en verklig nod? Vad är en nod i samband nya lista?

870
00:52:08,310 --> 00:52:11,840
Det första, som kallas ord, är personens namn.

871
00:52:11,840 --> 00:52:14,340
LÄNGD, förmodligen, avser den maximala längden för en människas namn,

872
00:52:14,340 --> 00:52:18,210
vad det är, 20, 30, 40 tecken i galna hörn fall

873
00:52:18,210 --> 00:52:22,680
och en är för vad? Det är bara den extra NULL karaktär, \ 0.

874
00:52:22,680 --> 00:52:27,410
Så denna nod omslag "något" inne i sig själv,

875
00:52:27,410 --> 00:52:29,640
men det förklarar också en pekare som kallas nästa

876
00:52:29,640 --> 00:52:32,580
så att vi kan kedjan Alice till Bob till Charlie och så vidare.

877
00:52:32,580 --> 00:52:36,700
Kan vara NULL men inte nödvändigtvis vara.

878
00:52:36,700 --> 00:52:40,110
Eventuella frågor om dessa hashtabeller? Ja?

879
00:52:40,110 --> 00:52:46,190
[Student frågar fråga, obegripligt] En array - bra fråga.

880
00:52:46,190 --> 00:52:50,120
Varför är denna char ord i en array i stället för bara char *?

881
00:52:50,120 --> 00:52:53,830
I detta något godtyckliga exempel, jag vill inte behöva tillgripa

882
00:52:53,830 --> 00:52:56,190
till malloc för varje ursprungliga namnen.

883
00:52:56,190 --> 00:52:59,530
Jag ville förklara en maximal mängd minne för strängen

884
00:52:59,530 --> 00:53:06,020
så att jag kunde kopiera i strukturen Alice \ 0 och inte måste ta itu med malloc och fri och liknande.

885
00:53:06,020 --> 00:53:11,710
Men jag kunde göra det om jag ville vara mer medvetna om utrymme användning. Bra fråga.

886
00:53:11,710 --> 00:53:14,780
Så låt oss försöka att generalisera bort från detta

887
00:53:14,780 --> 00:53:18,350
och fokusera resten av idag om datastrukturer mer allmänt

888
00:53:18,350 --> 00:53:21,170
och andra problem som vi kan lösa med hjälp av samma grundläggande

889
00:53:21,170 --> 00:53:24,590
även om datastrukturer själva kan skilja på sina uppgifter.

890
00:53:24,590 --> 00:53:27,910
>> Så det visar sig i datavetenskap, träd är mycket vanliga.

891
00:53:27,910 --> 00:53:29,760
Och du kan tänka på ett träd ungefär som ett släktträd,

892
00:53:29,760 --> 00:53:31,830
där det finns en del rötter, vissa matriark eller patriarken,

893
00:53:31,830 --> 00:53:34,540
mormor eller farfar eller tidigare tillbaka,

894
00:53:34,540 --> 00:53:38,880
under vilka mamma och pappa eller olika syskon eller liknande.

895
00:53:38,880 --> 00:53:42,500
Så en trädstruktur har noder och har barn,

896
00:53:42,500 --> 00:53:45,260
vanligen 0 eller fler barn för varje nod.

897
00:53:45,260 --> 00:53:47,320
Och några av jargongen som du ser på bilden här

898
00:53:47,320 --> 00:53:50,630
är någon av de små barnen eller barnbarn på kanterna

899
00:53:50,630 --> 00:53:52,330
som inte har några pilar som härrör från dem,

900
00:53:52,330 --> 00:53:55,070
de är de så kallade löv, och alla på insidan

901
00:53:55,070 --> 00:53:58,790
är en inre nod, du kan kalla det vad som helst i den riktningen.

902
00:53:58,790 --> 00:54:01,430
Men denna struktur är ganska vanligt. Den här är lite godtycklig.

903
00:54:01,430 --> 00:54:04,930
Vi har ett barn till vänster, har vi tre barn till höger,

904
00:54:04,930 --> 00:54:06,830
två barn på längst ner till vänster.

905
00:54:06,830 --> 00:54:10,740
Så att vi kan ha olika stora träd, men om vi börjar standardisera saker,

906
00:54:10,740 --> 00:54:15,330
och du kanske kommer ihåg detta från Patricks video på binärsökning från en tidigare kort

907
00:54:15,330 --> 00:54:19,490
nätet, binärsökning behöver inte genomföras med en rad

908
00:54:19,490 --> 00:54:21,410
eller lappar på en svart tavla.

909
00:54:21,410 --> 00:54:25,490
Anta att du vill spara dina siffror i en mer sofistikerad datastruktur.

910
00:54:25,490 --> 00:54:27,680
Du kan skapa ett träd som denna.

911
00:54:27,680 --> 00:54:35,290
Du kunde ha en nod deklareras i C, och den noden kan ha minst två element i den.

912
00:54:35,290 --> 00:54:39,470
En är det nummer du vill lagra, och den andra är - ja, vi behöver en till.

913
00:54:39,470 --> 00:54:41,540
Den andra är dess barn.

914
00:54:41,540 --> 00:54:45,150
Så här är en annan datastruktur. Denna gång, är en nod definieras som lagrar ett antal n

915
00:54:45,150 --> 00:54:49,060
och sedan två pekare, vänster barn och höger barn.

916
00:54:49,060 --> 00:54:52,100
Och de är inte godtyckliga. Det intressanta om detta träd?

917
00:54:52,100 --> 00:55:00,550
>> Vad är mönstret i hur vi har lagt ut det här eller hur Patrick lade den i hans video?

918
00:55:00,550 --> 00:55:02,790
Det är typ av uppenbart att det finns en viss sortering pågår här,

919
00:55:02,790 --> 00:55:04,460
men vad är den enkla regeln? Ja?

920
00:55:04,460 --> 00:55:08,350
[Student svar, obegripligt]

921
00:55:08,350 --> 00:55:12,040
Perfekt. Om du blick på detta, ser du de små siffrorna till vänster,

922
00:55:12,040 --> 00:55:14,690
stora siffror till vänster, men det är sant för varje nod.

923
00:55:14,690 --> 00:55:20,370
För varje nod, dess vänstra underordnade mindre än den, och dess högra underordnade större än det.

924
00:55:20,370 --> 00:55:25,210
Vad detta innebär nu är om jag vill söka denna datastruktur för, säg, antalet 44,

925
00:55:25,210 --> 00:55:29,320
Jag måste börja vid roten, för som med alla dessa mer komplexa datastrukturer nu,

926
00:55:29,320 --> 00:55:31,910
Vi har bara en pekare till en sak, början.

927
00:55:31,910 --> 00:55:35,010
Och i detta fall, är början roten. Det är inte den vänstra änden,

928
00:55:35,010 --> 00:55:39,530
Det är roten till denna struktur. Så jag ser här är 55, och jag söker 44.

929
00:55:39,530 --> 00:55:41,430
Vilken riktning jag vill gå?

930
00:55:41,430 --> 00:55:45,680
Tja, jag vill gå till vänster, eftersom uppenbarligen är till höger kommer att bli för stor.

931
00:55:45,680 --> 00:55:49,050
Så märker här, du slags konceptuellt hugga trädet halv

932
00:55:49,050 --> 00:55:51,700
eftersom man aldrig kommer ner till höger.

933
00:55:51,700 --> 00:55:55,410
Så nu går jag från 55 till 33. Det är för litet för ett tal.

934
00:55:55,410 --> 00:56:01,590
Jag letar efter 44, men nu vet jag om 44 är i detta träd, kan jag gå självklart till höger.

935
00:56:01,590 --> 00:56:04,460
Så återigen, jag beskärning trädet i halv.

936
00:56:04,460 --> 00:56:06,780
Det är ganska mycket samma begreppsmässigt i telefonboken.

937
00:56:06,780 --> 00:56:09,510
Det är identiskt med vad vi gjorde med papper på tavlan,

938
00:56:09,510 --> 00:56:13,940
men det är en mer sofistikerad struktur som tillåter oss att faktiskt göra

939
00:56:13,940 --> 00:56:16,880
detta söndra och härska genom konstruktion av algoritmen,

940
00:56:16,880 --> 00:56:19,420
och i själva verket korsar en struktur som denna - hoppsan.

941
00:56:19,420 --> 00:56:22,870
Gå igenom en struktur som denna, där det är bara "gå denna väg eller gå den vägen",

942
00:56:22,870 --> 00:56:26,870
innebär allt som kod som böjde dig först när dess genomförande i avsnitt

943
00:56:26,870 --> 00:56:31,270
eller gå igenom det hemma, för binär sökning, med rekursion eller iteration,

944
00:56:31,270 --> 00:56:35,060
Det är en smärta i nacken. Hitta den mellersta delen, så gör din avrundning uppåt eller nedåt.

945
00:56:35,060 --> 00:56:39,230
>> Det finns en skönhet till detta eftersom vi nu kan använda rekursion igen,

946
00:56:39,230 --> 00:56:43,760
men mycket renare. Faktum är att om du är på numret 55 och du vill hitta 44,

947
00:56:43,760 --> 00:56:48,450
du går kvar i det här fallet, vad gör du? Du kör exakt samma algoritm.

948
00:56:48,450 --> 00:56:51,560
Du kontrollerar värdet för noden, då du går åt höger eller vänster.

949
00:56:51,560 --> 00:56:53,670
Då kan du kontrollera värdet för noden, gå vänster eller höger.

950
00:56:53,670 --> 00:56:56,710
Detta passar perfekt för rekursion.

951
00:56:56,710 --> 00:57:00,920
Så även i det förflutna som vi har gjort några ganska godtyckliga exempel där rekursion

952
00:57:00,920 --> 00:57:03,430
som inte behöver vara rekursiv med uppgifter stuktur,

953
00:57:03,430 --> 00:57:07,820
speciellt träd, det är en perfekt tillämpning av denna idé att ta ett problem,

954
00:57:07,820 --> 00:57:12,920
krymper den och sedan lösa samma typ av, men mindre, programmet.

955
00:57:12,920 --> 00:57:14,590
>> Så det finns en annan datastruktur som vi kan införa.

956
00:57:14,590 --> 00:57:18,760
Den här är konstruerad vid en första anblick att se kryptiska, men den här är fantastiskt.

957
00:57:18,760 --> 00:57:25,090
Så detta är en datastruktur som kallas en trie, trie, som ärvs från ordet hämtning

958
00:57:25,090 --> 00:57:30,210
som inte uttalas försöka igen-val, men det är vad världen kallar dessa saker. Försöker. T-R-I-e.

959
00:57:30,210 --> 00:57:35,190
Det är en trädstruktur av något slag, men var och en av noderna i en trie

960
00:57:35,190 --> 00:57:41,280
verkar vara vad? Och detta är lite missvisande eftersom det är typ av förkortad.

961
00:57:41,280 --> 00:57:45,960
Men det ser ut som varje nod i trie är faktiskt en matris.

962
00:57:45,960 --> 00:57:48,840
Och även om författaren till detta diagram inte har visat det,

963
00:57:48,840 --> 00:57:54,130
I det här fallet är det trie en datastruktur vars syfte i livet är att lagra ord

964
00:57:54,130 --> 00:57:57,330
som A-L-I-C-E eller B-O-b.

965
00:57:57,330 --> 00:58:02,480
Och det sätt på vilket dessa uppgifter lagrar Alice och Bob och Charlie och Anita och så vidare

966
00:58:02,480 --> 00:58:06,970
är den använder en array där att lagra Alice i en trie,

967
00:58:06,970 --> 00:58:09,820
vi börjar vid rotnoden som ser ut som en matris,

968
00:58:09,820 --> 00:58:12,080
och det skrivits i stenografi notation.

969
00:58:12,080 --> 00:58:15,070
Författaren utelämnas abcdefg eftersom det fanns inga namn med det.

970
00:58:15,070 --> 00:58:19,150
De visade endast M och P och T, men i detta fall,

971
00:58:19,150 --> 00:58:22,780
låt oss gå bort från Alice och Bob och Charlie till vissa namn som är här.

972
00:58:22,780 --> 00:58:25,670
Maxwell är faktiskt i detta diagram.

973
00:58:25,670 --> 00:58:29,570
Så hur gjorde författaren butiken M-A-X-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Han eller hon började på rotnoden, och gick till [M], så ungefär 13, den 13: e plats i arrayen.

975
00:58:36,990 --> 00:58:40,750
Sedan därifrån, det finns en pekare.

976
00:58:40,750 --> 00:58:42,760
En pekare som leder till en annan uppsättning.

977
00:58:42,760 --> 00:58:47,880
Därifrån författaren indexeras i matrisen i lokal A, vilket visas där uppe till vänster,

978
00:58:47,880 --> 00:58:52,250
och då han eller hon följde pekare till en annan array,

979
00:58:52,250 --> 00:58:55,460
och gick till pekaren på platsen X.

980
00:58:55,460 --> 00:58:59,840
Sedan i nästa arrayen platsen W, E, L, L, och så vidare,

981
00:58:59,840 --> 00:59:03,090
och slutligen, låt oss faktiskt försöka lägga in en bild på detta.

982
00:59:03,090 --> 00:59:05,380
Hur ser en nod se ut i kod?

983
00:59:05,380 --> 00:59:11,820
En nod i en trie innehåller en array av pekare till fler noder.

984
00:59:11,820 --> 00:59:16,090
Men det finns också fick vara någon form av booleskt värde, åtminstone i detta genomförande.

985
00:59:16,090 --> 00:59:18,770
Jag råkar kalla det is_word. Varför?

986
00:59:18,770 --> 00:59:22,670
För när du sätter Maxwell, du sätter inte

987
00:59:22,670 --> 00:59:25,300
något i detta datastruktur.

988
00:59:25,300 --> 00:59:27,480
Du skriver inte M. Du inte skriver X.

989
00:59:27,480 --> 00:59:30,240
Allt du gör är följande pekare.

990
00:59:30,240 --> 00:59:33,360
Pekaren som representerar M, då pekaren som representerar A,

991
00:59:33,360 --> 00:59:36,310
då pekaren som representerar X, då är W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
men vad du behöver göra i slutet är typ av att gå, kontrollera nådde jag denna plats.

993
00:59:41,950 --> 00:59:45,560
Det var ett ord som slutar här i datastrukturen.

994
00:59:45,560 --> 00:59:48,190
>> Så vad en trie verkligen fylld med och författaren valde att representera

995
00:59:48,190 --> 00:59:51,880
Dessa terminuses med små trianglar.

996
00:59:51,880 --> 00:59:56,470
Det betyder bara att det faktum denna triangel är här, här booleska värdet true

997
00:59:56,470 --> 00:59:59,200
innebär att om du går bakåt i trädet,

998
00:59:59,200 --> 01:00:02,420
det betyder ett ord som heter Maxwell är i denna.

999
01:00:02,420 --> 01:00:04,870
Men ordet foo, till exempel,

1000
01:00:04,870 --> 01:00:07,970
inte i trädet, för om jag börjar på rotnoden här uppe på toppen,

1001
01:00:07,970 --> 01:00:14,030
Det finns ingen f pekare, ingen o pekare, ingen o pekare. Foo är inte ett namn i denna ordbok.

1002
01:00:14,030 --> 01:00:22,460
Utan däremot Turing, t-u-r-i-n-g. Återigen, jag sparar inte t eller u eller r eller i eller n eller g.

1003
01:00:22,460 --> 01:00:29,820
Men jag gjorde butik i denna datastruktur värdet true ner här i nod - i trädet

1004
01:00:29,820 --> 01:00:33,030
genom att sätta denna booleskt värde av is_word till true.

1005
01:00:33,030 --> 01:00:35,740
Så en trie är typ av denna mycket intressanta meta struktur,

1006
01:00:35,740 --> 01:00:39,810
där du inte riktigt lagra ord själva för denna typ av ordbok.

1007
01:00:39,810 --> 01:00:45,100
För att vara tydlig, du bara lagrar ja eller nej, det är ett ord som slutar här.

1008
01:00:45,100 --> 01:00:46,430
>> Nu vad är innebörden?

1009
01:00:46,430 --> 01:00:51,120
Om du har 150.000 ord i en ordbok som du försöker lagra i minnet

1010
01:00:51,120 --> 01:00:53,400
med något som liknar en länkad lista,

1011
01:00:53,400 --> 01:00:56,870
du kommer att ha 150.000 noder i din länkad lista.

1012
01:00:56,870 --> 01:01:00,250
Och hitta en av dessa ord alfabetiskt kunde ta O (n) tid.

1013
01:01:00,250 --> 01:01:04,370
Linjär tid. Men i fallet här en trie,

1014
01:01:04,370 --> 01:01:09,210
vad är gångtiden att hitta ett ord?

1015
01:01:09,210 --> 01:01:17,390
Det visar sig skönheten här är att även om du har 149.999 ord redan i detta lexikon,

1016
01:01:17,390 --> 01:01:20,170
som genomförts med denna datastruktur,

1017
01:01:20,170 --> 01:01:25,560
hur mycket tid tar det att hitta eller sätta en ytterligare person till att som Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Tja, det är bara 5, kanske 6 steg för efterföljande tecken.

1019
01:01:30,640 --> 01:01:32,880
Eftersom presense av andra namn i strukturen

1020
01:01:32,880 --> 01:01:35,340
blir inte i vägen för insättning Alice.

1021
01:01:35,340 --> 01:01:39,640
Dessutom hitta Alice när det finns 150.000 ord i denna ordbok

1022
01:01:39,640 --> 01:01:41,960
blir inte i vägen för att hitta Alice alls,

1023
01:01:41,960 --> 01:01:46,880
eftersom Alice är. . . . . här, eftersom jag hittade ett booleskt värde.

1024
01:01:46,880 --> 01:01:50,920
Och om det inte finns någon boolean true, så Alice är inte i denna datastruktur av ord.

1025
01:01:50,920 --> 01:01:56,220
Med andra ord, speltid för att hitta saker och sätta saker i detta nya

1026
01:01:56,220 --> 01:02:01,920
datastruktur av trie är O - det är inte n.

1027
01:02:01,920 --> 01:02:05,730
Eftersom presense av 150.000 människor har ingen effekt på Alice, verkar det.

1028
01:02:05,730 --> 01:02:11,560
Så låt oss kalla det k, där k är den maximala längden av ett ord på engelska

1029
01:02:11,560 --> 01:02:14,050
vilket är typiskt inte mer än 20-något tecken.

1030
01:02:14,050 --> 01:02:17,940
Så k är en konstant. Så den heliga gralen vi tycks ha funnit nu

1031
01:02:17,940 --> 01:02:26,000
är att en trie konstant tid för insatser för uppslagningar för strykningar.

1032
01:02:26,000 --> 01:02:29,170
Eftersom antalet saker som redan finns i strukturen,

1033
01:02:29,170 --> 01:02:32,600
som inte ens fysiskt där. Återigen, de är bara typ av förprickat, ja eller nej,

1034
01:02:32,600 --> 01:02:35,050
har ingen inverkan på dess framtida gångtid.

1035
01:02:35,050 --> 01:02:37,940
>> Men det mĺste finnas en hake, annars skulle vi inte ha slösat bort så mycket tid

1036
01:02:37,940 --> 01:02:41,460
på alla dessa andra datastrukturer bara för att äntligen komma till den hemliga ett som är fantastiskt.

1037
01:02:41,460 --> 01:02:46,410
Så vad pris betalar vi för att uppnå detta storhet här? Utrymme.

1038
01:02:46,410 --> 01:02:49,010
Denna sak är massiv. Och anledningen till att författaren

1039
01:02:49,010 --> 01:02:52,400
lade inte fram det här, notera att alla dessa saker som ser ut som arrayer,

1040
01:02:52,400 --> 01:02:55,400
han inte dra resten av trädet, resten av trie,

1041
01:02:55,400 --> 01:02:58,060
eftersom de är helt enkelt inte relevant för berättelsen.

1042
01:02:58,060 --> 01:03:01,870
Men alla dessa noder är super bred, och varje nod i trädet tar upp

1043
01:03:01,870 --> 01:03:07,780
26 eller faktiskt, kan vara 27 tecken eftersom i detta fall var jag bland annat utrymme för apostrof

1044
01:03:07,780 --> 01:03:09,980
så att vi kunde få apostrophized ord.

1045
01:03:09,980 --> 01:03:14,450
I detta fall, är dessa stora kedjor. Så även om de inte är picutured,

1046
01:03:14,450 --> 01:03:18,190
detta tar upp en stor mängd RAM-minne.

1047
01:03:18,190 --> 01:03:20,670
Som kan vara bra, especilly i modern hårdvara,

1048
01:03:20,670 --> 01:03:25,650
men det är avvägning. Vi får mindre tid genom att spendera mer utrymme.

1049
01:03:25,650 --> 01:03:28,580
Så var kommer detta allt?

1050
01:03:28,580 --> 01:03:32,640
Nåväl, låt oss göra - låt oss se här.

1051
01:03:32,640 --> 01:03:39,510
Låt oss göra ett hopp till den här killen här.

1052
01:03:39,510 --> 01:03:43,450
>> Tro det eller ej, lika roligt som C har funnits en tid nu,

1053
01:03:43,450 --> 01:03:48,130
vi når den punkt i termin där det är dags att övergå till saker mer moderna.

1054
01:03:48,130 --> 01:03:50,950
Saker på en högre nivå. Och även om för ett par veckor

1055
01:03:50,950 --> 01:03:54,580
vi ändå fortsätta att fördjupa oss i en värld av pekare och minneshantering

1056
01:03:54,580 --> 01:03:57,210
att få det bekvämt som vi sedan kan bygga vidare på,

1057
01:03:57,210 --> 01:04:01,270
slutspelet är ytterst att införa, ironiskt nog, inte detta språk.

1058
01:04:01,270 --> 01:04:03,330
Vi kommer att spendera, som 10 minuter talar om HTML.

1059
01:04:03,330 --> 01:04:05,950
Allt HTML är är ett märkspråk och vad en märkspråk är

1060
01:04:05,950 --> 01:04:10,220
är dessa serier av öppna konsoler och stängda fästen som säger "gör detta djärva"

1061
01:04:10,220 --> 01:04:12,000
"Göra detta kursiv '' gör denna centrerad."

1062
01:04:12,000 --> 01:04:14,250
Det är inte så intellektuellt intressant, men det är super bra.

1063
01:04:14,250 --> 01:04:16,650
Och det är verkligen överallt dessa dagar.

1064
01:04:16,650 --> 01:04:19,450
Men vad är kraftfull om världen av HTML och webbprogrammering mer generellt,

1065
01:04:19,450 --> 01:04:25,910
bygger dynamiska saker, skriva kod i språk som PHP eller Python eller Ruby eller Java eller C #.

1066
01:04:25,910 --> 01:04:30,360
Verkligen, oavsett ditt språk val är, och genererar HTML dynamiskt.

1067
01:04:30,360 --> 01:04:32,960
Generera något som kallas CSS dynamiskt.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, vilket också om estetik.

1069
01:04:35,810 --> 01:04:41,360
Och så även om idag, om jag går till någon hemsida som bekant Google.com,

1070
01:04:41,360 --> 01:04:46,100
och jag går att visa, utvecklare, visa källa, som kanske du har gjort tidigare,

1071
01:04:46,100 --> 01:04:49,800
men kommer att visa källan ser det här förmodligen ganska kryptiskt.

1072
01:04:49,800 --> 01:04:55,320
Men detta är den underliggande koden som implementerar Google.com.

1073
01:04:55,320 --> 01:04:57,940
På den främre änden. Och faktiskt allt detta är fluffigt estetik grejer.

1074
01:04:57,940 --> 01:05:01,740
Detta är CSS här uppe. Om jag håller rulla ner vi kommer få några färgkodade saker.

1075
01:05:01,740 --> 01:05:06,890
Detta är HTML. Googles kod ser ut som en enda röra, men om jag faktiskt öppna upp ett annat fönster

1076
01:05:06,890 --> 01:05:09,380
Vi kan se några struktur till detta.

1077
01:05:09,380 --> 01:05:12,640
Om jag öppnar upp, märker här, det är lite mer lättläst.

1078
01:05:12,640 --> 01:05:16,850
Vi kommer att se snart denna tagg, [ord] är en tagg,

1079
01:05:16,850 --> 01:05:23,520
HTML, huvud, kropp, div, manus, textområdet, span, centrerad, div.

1080
01:05:23,520 --> 01:05:26,770
Och detta är ganska också kryptiska utseende vid första anblicken,

1081
01:05:26,770 --> 01:05:30,890
men allt den här röran följer vissa mönster och repeterbara mönster,

1082
01:05:30,890 --> 01:05:33,850
så att när vi får grunderna ner, kommer du att kunna skriva kod som denna

1083
01:05:33,850 --> 01:05:37,550
och sedan manipulera kod som denna med ytterligare ett annat språk, som kallas JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Och JavaScript är ett språk som körs inuti en webbläsare

1085
01:05:40,440 --> 01:05:44,380
idag som vi använder på Harvard kurser för kursen shoppa verktyg som Google Maps använder

1086
01:05:44,380 --> 01:05:48,660
för att ge dig en massa dynamik ger Facebook dig att visa omedelbar statusuppdateringar,

1087
01:05:48,660 --> 01:05:51,430
Twitter använder den för att visa dig tweets direkt.

1088
01:05:51,430 --> 01:05:53,820
Allt detta kommer vi att börja fördjupa oss i.

1089
01:05:53,820 --> 01:05:57,190
Men för att komma dit måste vi förstå lite om Internet.

1090
01:05:57,190 --> 01:06:01,130
Detta klipp här är bara en minut lång, och låt oss anta för nu är i själva verket

1091
01:06:01,130 --> 01:06:08,380
hur Internet fungerar som en teaser för vad som är på väg att komma. Jag ger dig "Warriors of the Net."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Långsam kör musik ♫]

1093
01:06:14,720 --> 01:06:20,450
[Man berättare] Han kom med ett budskap.

1094
01:06:20,450 --> 01:06:23,770
Med ett protokoll hela sin egen.

1095
01:06:23,770 --> 01:06:37,270
[♫ Snabbare elektronisk musik ♫]

1096
01:06:37,270 --> 01:06:41,330
Han kom till en värld av häftiga brandväggar, likgiltig routrar,

1097
01:06:41,330 --> 01:06:45,690
och faror långt värre än döden.

1098
01:06:45,690 --> 01:06:55,400
Han är snabb. Han är stark. Han är TCP / IP, och han har din adress.

1099
01:06:55,400 --> 01:06:59,250
Krigare av nätet.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Nästa vecka, då. Internet. Webbprogrammering. Detta är CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]