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

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

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

4
00:00:08,720 --> 00:00:12,970
Dette er CS50 og dette er slutten av uke 6.

5
00:00:12,970 --> 00:00:17,970
Så CS50x, en av Harvards første kurs involvert i EDX initiativ

6
00:00:17,970 --> 00:00:20,590
faktisk debuterte denne siste mandag.

7
00:00:20,590 --> 00:00:23,460
Hvis du ønsker å få et glimt av hva andre på Internett

8
00:00:23,460 --> 00:00:27,180
følger nå sammen med, kan du ta turen til x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Det vil omdirigere deg til riktig sted på edx.org,

10
00:00:30,350 --> 00:00:34,160
som var der denne og andre kurs fra MIT og Berkeley nå bor.

11
00:00:34,160 --> 00:00:38,140
Du må registrere deg for en konto, vil du finne at materialet er stort sett det samme

12
00:00:38,140 --> 00:00:42,170
som du har hatt dette semesteret, riktignok et par uker forsinket, så vi får alt klart.

13
00:00:42,170 --> 00:00:46,930
Men hva elevene i CS50x vil nå se er et grensesnitt helt som denne.

14
00:00:46,930 --> 00:00:50,040
Dette, for eksempel, er Zamyla leder walkthrough for oppgavesettet 0.

15
00:00:50,040 --> 00:00:54,230
Ved å logge deg på edx.org, ser en CS50x student slags ting

16
00:00:54,230 --> 00:00:57,170
du forventer å se i en bane: forelesningen for den Mandag,

17
00:00:57,170 --> 00:01:01,650
foredrag for onsdag, ulike shorts, problemet sett, de walkthroughs, PDF-filer.

18
00:01:01,650 --> 00:01:04,459
I tillegg, som du ser her, maskinoversettelser

19
00:01:04,459 --> 00:01:08,390
av engelske karakterutskrifter til kinesisk, japansk, spansk, italiensk,

20
00:01:08,390 --> 00:01:12,810
og en hel haug med andre språk som vil sikkert være ufullkommen

21
00:01:12,810 --> 00:01:15,840
som vi kastet dem ut programmatisk ved hjelp av noe som kalles en API,

22
00:01:15,840 --> 00:01:18,360
eller programmeringsgrensesnitt fra Google

23
00:01:18,360 --> 00:01:21,360
som tillater oss å konvertere engelsk til disse andre språk.

24
00:01:21,360 --> 00:01:24,100
Men takket være den fantastiske ånden av noen hundre pluss frivillige,

25
00:01:24,100 --> 00:01:26,940
tilfeldige folk på internett som har vennlig tilbudt å bli involvert

26
00:01:26,940 --> 00:01:30,180
i dette prosjektet, vil vi gradvis forbedre kvaliteten på disse oversettelsene

27
00:01:30,180 --> 00:01:35,790
ved å ha mennesker korrigere feilene som våre datamaskiner har gjort.

28
00:01:35,790 --> 00:01:42,330
>> Så det viser seg at vi hadde noen flere elever dukker opp på mandag enn vi opprinnelig forventet.

29
00:01:42,330 --> 00:01:48,980
Faktisk, nå CS50x har 100.000 mennesker følger sammen hjemme.

30
00:01:48,980 --> 00:01:54,430
Så skjønner dere er alle en del av dette første klasse for å gjøre dette kurset i informatikk

31
00:01:54,430 --> 00:01:57,370
utdanning mer generelt, i videre forstand, tilgjengelig.

32
00:01:57,370 --> 00:02:00,130
Og realiteten er nå, med noen av disse massive online kurs,

33
00:02:00,130 --> 00:02:04,070
de alle begynner med disse svært høye tall, som vi synes å ha gjort her.

34
00:02:04,070 --> 00:02:08,759
Men målet, til slutt, for CS50x er virkelig å få så mange mennesker til mållinjen som mulig.

35
00:02:08,759 --> 00:02:12,000
Av design, er CS50x kommer til å bli tilbudt fra dette siste mandag

36
00:02:12,000 --> 00:02:17,430
hele veien gjennom 15 April, 2013, slik at folk som har forpliktelser på skolen andre steder,

37
00:02:17,430 --> 00:02:20,990
arbeid, familie, andre konflikter og lignende, har en litt mer fleksibilitet

38
00:02:20,990 --> 00:02:23,640
som å dykke inn dette kurset, som nok det å si,

39
00:02:23,640 --> 00:02:30,540
er ganske ambisiøst gjort hvis bare i løpet av bare tre måneder i løpet av en vanlig semester.

40
00:02:30,540 --> 00:02:34,190
Men disse studentene vil bli takle det samme problemet sett, ser det samme innholdet,

41
00:02:34,190 --> 00:02:36,350
å ha tilgang til de samme shorts og lignende.

42
00:02:36,350 --> 00:02:38,990
Så innser at vi alle er virkelig i dette sammen.

43
00:02:38,990 --> 00:02:42,360
Og en av slutten mål CS50x er ikke bare å få så mange folk

44
00:02:42,360 --> 00:02:45,720
til mållinjen og gi dem denne nyvunne forståelsen av datateknologi

45
00:02:45,720 --> 00:02:49,000
og programmering, men også å ha dem har denne erfaringen.

46
00:02:49,000 --> 00:02:52,010
En av de definerende karakteristikkene av 50 på campus, håper vi,

47
00:02:52,010 --> 00:02:56,260
har vært denne slags felles opplevelse, for bedre eller verre, noen ganger,

48
00:02:56,260 --> 00:02:59,480
men å ha disse menneskene til å vende seg til til venstre og til høyre,

49
00:02:59,480 --> 00:03:01,830
og kontortid og hackathon og virkelig.

50
00:03:01,830 --> 00:03:04,560
Det er litt vanskeligere å gjøre det i person med folk på nettet,

51
00:03:04,560 --> 00:03:10,580
men CS50x vil konkludere i april med den aller første CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
som vil være en online tilpasning av vår idé av virkelig

53
00:03:13,630 --> 00:03:18,250
hvor disse tusenvis av studenter vil alle bli invitert til å sende inn en 1 - til 2-minutters video,

54
00:03:18,250 --> 00:03:22,480
enten en screencast av deres siste prosjekt eller video av dem vinke hallo

55
00:03:22,480 --> 00:03:24,490
og snakker om sitt prosjekt og demoing det,

56
00:03:24,490 --> 00:03:27,610
mye som dine forgjengere har gjort her på campus i messen,

57
00:03:27,610 --> 00:03:31,400
slik at ved semester slutt, er det håp å ha et globalt utstilling

58
00:03:31,400 --> 00:03:37,080
av CS50x studentenes endelige prosjektene, mye som det som venter deg i desember her på campus.

59
00:03:37,080 --> 00:03:39,680
Så mer om det i månedene som kommer.

60
00:03:39,680 --> 00:03:43,640
>> Med 100.000 studenter, men kommer et behov for noen flere sertifiseringsinstanser.

61
00:03:43,640 --> 00:03:47,590
Gitt at dere er flammende stien her og tar CS50

62
00:03:47,590 --> 00:03:51,630
flere uker i forkant av dette materialet ble utgitt til folk på EDX,

63
00:03:51,630 --> 00:03:55,330
innser vi ville elske å involvere så mange av våre egne studenter som mulig i dette initiativet,

64
00:03:55,330 --> 00:03:58,720
både i løpet av semesteret, samt denne vinteren og våren.

65
00:03:58,720 --> 00:04:01,620
Så hvis du ønsker å bli involvert i CS50x,

66
00:04:01,620 --> 00:04:07,450
spesielt bli med på CS50x Diskuter den EDX versjonen av CS50 Diskuter,

67
00:04:07,450 --> 00:04:10,140
som mange av dere har brukt på campus, den elektroniske oppslagstavle,

68
00:04:10,140 --> 00:04:13,040
vennligst hodet til den URL'en, la oss få vite hvem du er,

69
00:04:13,040 --> 00:04:16,450
fordi vi vil gjerne bygge opp et team av studenter og ansatte, og fakultetet både

70
00:04:16,450 --> 00:04:19,630
på campus som er rett og slett spille sammen og hjelpe ut.

71
00:04:19,630 --> 00:04:21,720
Og når de ser et spørsmål som er kjent for dem,

72
00:04:21,720 --> 00:04:25,320
du hører en student rapporterer noen feil sted der ute i noen land på Internett,

73
00:04:25,320 --> 00:04:27,450
og at ringer en bjelle fordi du også hadde det samme problemet

74
00:04:27,450 --> 00:04:32,620
i d-hallen for en tid siden, forhåpentligvis så kan du kiming i og dele din egen erfaring.

75
00:04:32,620 --> 00:04:37,300
Så vennligst ta del hvis du ønsker.

76
00:04:37,300 --> 00:04:39,360
>> Informatikk kurs ved Harvard har litt av en tradisjon,

77
00:04:39,360 --> 00:04:44,730
CS50 blant dem, for å ha noen klær, noen klær, som du kan bære med stolthet

78
00:04:44,730 --> 00:04:49,090
på semesters slutt, sier ganske stolt at du er ferdig CS50

79
00:04:49,090 --> 00:04:51,830
og tok CS50 og lignende, og vi prøver alltid å involvere elevene

80
00:04:51,830 --> 00:04:54,540
i denne prosessen så mye som mulig, hvorved vi inviterer,

81
00:04:54,540 --> 00:04:56,900
rundt denne tiden av semesteret, til studenter levere design

82
00:04:56,900 --> 00:04:59,330
ved hjelp av Photoshop, eller hva verktøy av valget du ønsker å bruke

83
00:04:59,330 --> 00:05:02,330
hvis du er en designer, til å levere design for T-skjorter og gensere

84
00:05:02,330 --> 00:05:06,100
og paraplyer og små bandanas for hunder vi har nå og lignende.

85
00:05:06,100 --> 00:05:09,370
Og alt er så - vinnerne hvert år blir deretter utstilt

86
00:05:09,370 --> 00:05:12,700
på kurset hjemmeside store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Alt er solgt til kostpris der, men nettstedet bare styrer seg selv

88
00:05:15,790 --> 00:05:18,330
og tillater folk å velge farger og design som de liker.

89
00:05:18,330 --> 00:05:20,420
Så jeg trodde vi ville bare dele noen av fjorårets design

90
00:05:20,420 --> 00:05:25,130
som var på nettsiden i tillegg til dette en her, som er en årlig tradisjon.

91
00:05:25,130 --> 00:05:29,410
"Hver dag jeg Seg Faultn" var en av de anførsler i fjor,

92
00:05:29,410 --> 00:05:32,290
som fortsatt er tilgjengelig der for alumni.

93
00:05:32,290 --> 00:05:35,820
Vi hadde denne, "CS50, Etablert 1989."

94
00:05:35,820 --> 00:05:39,010
En av våre Bowdens, Rob, var svært populær i fjor.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" ble født, ble dette designet fremlagt, blant de beste selgerne.

96
00:05:43,480 --> 00:05:49,040
Som var denne her. Mange folk hadde "Bowden Fever" i henhold til salg loggene.

97
00:05:49,040 --> 00:05:52,650
Innse at det kan nå være din design der, opp på internett.

98
00:05:52,650 --> 00:05:57,510
Flere detaljer om dette i neste problemet setter framover.

99
00:05:57,510 --> 00:06:00,330
>> Et ekstra verktøy: du har hatt noen eksponering og forhåpentligvis nå

100
00:06:00,330 --> 00:06:02,350
noen hands-on erfaring med GDB,

101
00:06:02,350 --> 00:06:04,570
som er, selvfølgelig, en debugger, og lar deg manipulere

102
00:06:04,570 --> 00:06:09,500
programmet på et relativt lavt nivå, gjør hva slags ting?

103
00:06:09,500 --> 00:06:13,030
Hva lar GDB du gjøre?

104
00:06:13,030 --> 00:06:15,030
Ja? Gi meg noe. [Student svar, uforståelig]

105
00:06:15,030 --> 00:06:18,120
Bra. Step into funksjon, slik at du ikke bare å skrive kjøre

106
00:06:18,120 --> 00:06:22,310
og har programmet blåse gjennom sin helhet, skrive ut ting til standard ut.

107
00:06:22,310 --> 00:06:25,190
Snarere, kan du gå gjennom den linje for linje, enten skrive neste

108
00:06:25,190 --> 00:06:30,300
å gå linje for linje for linje eller trinn å dykke inn i en funksjon, typisk en som du skrev.

109
00:06:30,300 --> 00:06:35,240
Hva annet lar GDB du gjøre? Ja? [Student svar, uforståelig]

110
00:06:35,240 --> 00:06:38,100
Skriv ut variabler. Så hvis du ønsker å gjøre litt introspeksjon innsiden av programmet

111
00:06:38,100 --> 00:06:41,500
uten å måtte ty til å skrive printf uttalelser over alt,

112
00:06:41,500 --> 00:06:44,600
du kan bare skrive ut en variabel eller vise en variabel.

113
00:06:44,600 --> 00:06:46,710
Hva annet kan du gjøre med en debugger som GDB?

114
00:06:46,710 --> 00:06:49,170
[Student svar, uforståelig]

115
00:06:49,170 --> 00:06:52,080
Akkurat. Du kan angi stoppunkt, du kan si pause kjøring

116
00:06:52,080 --> 00:06:54,020
på de viktigste funksjon eller foo funksjonen.

117
00:06:54,020 --> 00:06:56,800
Du kan si pause kjøring på linje 123.

118
00:06:56,800 --> 00:06:58,950
Og stoppunkter er en virkelig kraftig teknikk

119
00:06:58,950 --> 00:07:01,110
fordi hvis du har en generell følelse av hvor problemet

120
00:07:01,110 --> 00:07:05,360
sannsynligvis er, trenger du ikke å kaste bort tid stepping gjennom programmet sin helhet.

121
00:07:05,360 --> 00:07:08,250
Du kan faktisk hoppe rett der og deretter begynne å skrive -

122
00:07:08,250 --> 00:07:10,970
stepping gjennom den med trinn eller neste eller lignende.

123
00:07:10,970 --> 00:07:14,340
Men fangsten med noe sånt GDB er at det hjelper deg, det menneskelige,

124
00:07:14,340 --> 00:07:16,940
finne dine problemer og finne bugs.

125
00:07:16,940 --> 00:07:19,470
Det betyr ikke nødvendigvis finne dem så mye for deg.

126
00:07:19,470 --> 00:07:23,070
>> Så vi introduserte den andre dagen style50, som er en kort kommandolinjeverktøy

127
00:07:23,070 --> 00:07:27,500
som prøver å stilisere koden litt mer renslig enn deg, menneske, kan ha gjort.

128
00:07:27,500 --> 00:07:29,530
Men det også, er egentlig bare en estetisk ting.

129
00:07:29,530 --> 00:07:34,110
Men det viser seg at det er denne andre verktøy kalt Valgrind som er litt mer uforståelige å bruke.

130
00:07:34,110 --> 00:07:36,860
Produksjonen er atrociously kryptisk ved første øyekast.

131
00:07:36,860 --> 00:07:39,420
Men det er fantastisk nyttig, spesielt nå som vi er på den delen av begrepet

132
00:07:39,420 --> 00:07:43,080
hvor du begynner å bruke malloc og dynamisk minne allokering.

133
00:07:43,080 --> 00:07:45,420
Ting kan gå veldig, veldig galt raskt.

134
00:07:45,420 --> 00:07:49,320
Fordi hvis du glemmer å frigjøre minne, eller dereferanse du noen NULL-peker,

135
00:07:49,320 --> 00:07:55,770
eller du dereferanse noen søppel pekeren, hva er typisk symptom som resulterer?

136
00:07:55,770 --> 00:07:59,470
Seg feil. Og du får denne kildefilen av et antall kilobyte eller megabyte

137
00:07:59,470 --> 00:08:02,990
som representerer staten programmet minne når det krasjet,

138
00:08:02,990 --> 00:08:05,730
men programmet til slutt SEG feil, segmentering feil,

139
00:08:05,730 --> 00:08:08,450
som betyr noe dårlig skjedde nesten alltid relatert

140
00:08:08,450 --> 00:08:11,750
til et minne-relatert feil at du har gjort et eller annet sted.

141
00:08:11,750 --> 00:08:14,100
Så Valgrind hjelper deg å finne ting som dette.

142
00:08:14,100 --> 00:08:17,720
Det er et verktøy som du kjører, som GDB, etter at du har samlet programmet,

143
00:08:17,720 --> 00:08:20,330
men i stedet for å kjøre programmet direkte, kjører du Valgrind

144
00:08:20,330 --> 00:08:23,960
og du passerer til det programmet, akkurat som du gjør med GDB.

145
00:08:23,960 --> 00:08:26,220
Nå bruken, for å få den beste form for produksjon,

146
00:08:26,220 --> 00:08:30,410
er litt lang, så der oppå av skjermen vil du se Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" nesten universelt betyr verbose når du bruker programmer på en Linux-datamaskin.

148
00:08:35,350 --> 00:08:38,770
Så det betyr spytte ut flere data enn du kanskje som standard.

149
00:08:38,770 --> 00:08:45,510
"- Lekkasje-sjekk = full." Dette er bare å si sjekk for alle mulige minnelekkasjer,

150
00:08:45,510 --> 00:08:49,430
feil som jeg kunne ha gjort. Også dette er en vanlig paradigme med Linux-programmer.

151
00:08:49,430 --> 00:08:52,710
Vanligvis, hvis du har en kommandolinje argument som er en "bryter",

152
00:08:52,710 --> 00:08:55,830
som er ment å endre programmets oppførsel, og det er en enkelt bokstav,

153
00:08:55,830 --> 00:09:00,310
det er-v, men hvis det er slått, bare ved utforming av programmerer,

154
00:09:00,310 --> 00:09:05,150
er et helt ord eller serie av ord, begynner Kommandolinjeargumentet med -.

155
00:09:05,150 --> 00:09:08,190
Dette er bare menneskelige konvensjoner, men du vil se dem stadig.

156
00:09:08,190 --> 00:09:12,410
Og så, til slutt, "a.out" er tilfeldig navn for programmet i dette eksempelet.

157
00:09:12,410 --> 00:09:14,640
Og her er noen representative utgang.

158
00:09:14,640 --> 00:09:22,890
>> Før vi ser på hva det kan bety, la meg gå over til en kodebit over her.

159
00:09:22,890 --> 00:09:26,390
Og la meg flytte dette ut av veien, kommer snart,

160
00:09:26,390 --> 00:09:32,120
og la oss ta en titt på memory.c, som er denne korte eksempel her.

161
00:09:32,120 --> 00:09:36,290
Så i dette programmet, la meg zoome inn på de funksjoner og spørsmål.

162
00:09:36,290 --> 00:09:39,430
Vi har en funksjon hoved som kaller en funksjon, f,

163
00:09:39,430 --> 00:09:45,590
og hva går videre f å gjøre, i litt teknisk engelsk?

164
00:09:45,590 --> 00:09:49,760
Hva fortsette f å gjøre?

165
00:09:49,760 --> 00:09:53,680
Hva om jeg skal begynne med linje 20, og stjernens sted spiller ingen rolle,

166
00:09:53,680 --> 00:09:56,720
men jeg vil bare være konsekvent her med siste forelesning.

167
00:09:56,720 --> 00:09:59,910
Hva er linje 20 gjør for oss? På den venstre side. Vi vil bryte det ned ytterligere.

168
00:09:59,910 --> 00:10:02,410
Int * x: hva gjør det?

169
00:10:02,410 --> 00:10:04,940
Okay. Det erklærer en peker, og la oss nå være enda mer teknisk.

170
00:10:04,940 --> 00:10:10,230
Hva betyr det, veldig konkret, for å erklære en peker? Noen andre?

171
00:10:10,230 --> 00:10:15,050
Ja? [Student svar, uforståelig] For langt.

172
00:10:15,050 --> 00:10:17,060
Så du leser til høyre side av likhetstegnet.

173
00:10:17,060 --> 00:10:20,290
La oss fokusere bare på venstre, bare på int * x.

174
00:10:20,290 --> 00:10:24,700
Dette betyr "erklærer" en peker, men nå la oss dykke dypere til denne definisjonen.

175
00:10:24,700 --> 00:10:28,330
Hva betyr det konkret, teknisk bety? Ja?

176
00:10:28,330 --> 00:10:31,940
[Student svar, uforståelig]

177
00:10:31,940 --> 00:10:35,090
Okay. Det er forbereder å lagre en adresse i minnet.

178
00:10:35,090 --> 00:10:40,680
Bra. Og la oss ta dette et skritt videre, det er å erklære en variabel, x, som er 32 biter.

179
00:10:40,680 --> 00:10:44,440
Og jeg vet det er 32 bits fordi -?

180
00:10:44,440 --> 00:10:47,390
Det er ikke fordi det er en int, fordi det er en peker i dette tilfellet.

181
00:10:47,390 --> 00:10:49,650
Tilfeldighet at det er ett og det samme med en int,

182
00:10:49,650 --> 00:10:51,970
men det faktum at det er stjernen det betyr at dette er en peker

183
00:10:51,970 --> 00:10:57,300
og i apparatet, som med mange datamaskiner, men ikke alle, pekere er 32 biter.

184
00:10:57,300 --> 00:11:01,850
På mer moderne maskinvare som den nyeste Mac, de nyeste PC-er, kan du ha 64-bit pekere,

185
00:11:01,850 --> 00:11:04,160
men i apparatet, disse tingene er 32 bits.

186
00:11:04,160 --> 00:11:08,380
Så vi vil standardisere på det. Mer konkret går historien som følger:

187
00:11:08,380 --> 00:11:10,820
Vi "erklærer" en peker, hva betyr det?

188
00:11:10,820 --> 00:11:12,810
Vi forbereder å lagre et minne adresse.

189
00:11:12,810 --> 00:11:15,530
Hva betyr det?

190
00:11:15,530 --> 00:11:19,810
Vi skaper en variabel kalt x som tar opp 32 biter

191
00:11:19,810 --> 00:11:23,810
som snart lagre adressen for et heltall.

192
00:11:23,810 --> 00:11:26,470
Og det er sannsynligvis omtrent like presis som vi kan få.

193
00:11:26,470 --> 00:11:31,810
Det er greit fremover for å forenkle verden og bare si erklære en peker som heter x.

194
00:11:31,810 --> 00:11:35,380
Erklærer en peker, men skjønner og forstår hva som faktisk skjer

195
00:11:35,380 --> 00:11:38,490
selv i bare disse tegnene.

196
00:11:38,490 --> 00:11:42,040
>> Nå er dette en nesten litt lettere, selv om det er en lengre uttrykk.

197
00:11:42,040 --> 00:11:48,160
Så hva er dette å gjøre, det er markert nå: "malloc (10 * sizeof (int));" Yeah?

198
00:11:48,160 --> 00:11:52,350
[Student svar, uforståelig]

199
00:11:52,350 --> 00:11:58,250
Bra. Og jeg vil ta det der. Det er tildeling av en del av minnet for ti heltall.

200
00:11:58,250 --> 00:12:02,190
Og la oss nå dykke i litt dypere, det er tildeling av en del av minnet for ti heltall.

201
00:12:02,190 --> 00:12:05,390
Hva er malloc deretter retur?

202
00:12:05,390 --> 00:12:10,390
Adressen til del, eller mer konkret, adressen til den første byte som del.

203
00:12:10,390 --> 00:12:14,080
Hvordan blir jeg, programmerer, for å vite hvor det blings av minne ender?

204
00:12:14,080 --> 00:12:18,340
Jeg vet at det er sammenhengende. Malloc, per definisjon, vil gi deg en sammenhengende del av minnet.

205
00:12:18,340 --> 00:12:21,240
Ingen hull i den. Du har tilgang til hver byte i det blings,

206
00:12:21,240 --> 00:12:26,760
rygg mot rygg til rygg, men hvordan vet jeg hvor slutten av denne del av minnet er?

207
00:12:26,760 --> 00:12:28,850
Når du bruker malloc? [Student svar, uforståelig] Bra.

208
00:12:28,850 --> 00:12:30,670
Du gjør ikke det. Du må huske.

209
00:12:30,670 --> 00:12:35,960
Jeg må huske at jeg brukte verdien 10, og jeg vet ikke engang synes å ha gjort det her.

210
00:12:35,960 --> 00:12:41,000
Men onus er helt på meg. Strlen, som vi har blitt litt avhengig av for strykere,

211
00:12:41,000 --> 00:12:45,860
fungerer bare på grunn av denne konvensjonen til å ha \ 0

212
00:12:45,860 --> 00:12:48,840
eller denne spesielle nul karakter, NUL, på slutten av en streng.

213
00:12:48,840 --> 00:12:51,740
Det holder ikke for bare vilkårlige mengder minne.

214
00:12:51,740 --> 00:12:58,590
Det er opp til deg. Så linje 20, så tildeler en del av minnet

215
00:12:58,590 --> 00:13:02,590
som kan lagre ti heltall, og den lagrer adressen til den første byte

216
00:13:02,590 --> 00:13:05,610
av at del av minnet i variabelen x.

217
00:13:05,610 --> 00:13:11,140
Ergo, som er en peker. Så line 21, dessverre var en feil.

218
00:13:11,140 --> 00:13:16,110
Men først, hva er det du gjør? Det sier butikken på 10 plassering, 0 indeksert,

219
00:13:16,110 --> 00:13:19,480
av del av minnet som kalles x verdien 0.

220
00:13:19,480 --> 00:13:21,510
>> Så merke til et par ting skjer.

221
00:13:21,510 --> 00:13:25,420
Selv om x er en peker, husker fra et par uker siden

222
00:13:25,420 --> 00:13:29,440
at du kan fortsatt bruke array-stil hakeparentes notasjon.

223
00:13:29,440 --> 00:13:36,180
Fordi det er faktisk kort hånd notasjon for mer kryptiske utseende pekeren aritmetikk.

224
00:13:36,180 --> 00:13:40,320
der vi ville gjøre noe som dette: Ta adresse x, flytte 10 punkter over,

225
00:13:40,320 --> 00:13:44,550
så går det til hva adressen lagres på denne plasseringen.

226
00:13:44,550 --> 00:13:48,090
Men ærlig, dette er bare fryktelig å lese og bli komfortabel med.

227
00:13:48,090 --> 00:13:52,900
Så verden bruker vanligvis klammeparentesene bare fordi det er så mye mer human-vennlig å lese.

228
00:13:52,900 --> 00:13:55,140
Men det er det som egentlig skjer under panseret;

229
00:13:55,140 --> 00:13:58,190
x er en adresse, ikke en matrise, per se.

230
00:13:58,190 --> 00:14:02,410
Så dette er lagring 0 på stedet 10 i x.

231
00:14:02,410 --> 00:14:06,120
Hvorfor er dette dårlig? Ja?

232
00:14:06,120 --> 00:14:17,370
[Student svar, uforståelig] Nettopp.

233
00:14:17,370 --> 00:14:21,100
Vi bare tildelt ti ints, men vi telle fra 0 når programmering i C,

234
00:14:21,100 --> 00:14:25,690
slik at du har tilgang til 0 1 2 3 4 5 6 7 8 9, men ikke 10.

235
00:14:25,690 --> 00:14:30,270
Så enten programmet skal SEG feil eller er det ikke.

236
00:14:30,270 --> 00:14:32,900
Men vi vet egentlig ikke, dette er liksom en nondeterministic atferd.

237
00:14:32,900 --> 00:14:35,600
Det er egentlig avhengig av om vi får heldig.

238
00:14:35,600 --> 00:14:40,650
Hvis det viser seg at operativsystemet ikke tankene hvis jeg bruker det ekstra byte,

239
00:14:40,650 --> 00:14:43,360
selv om det ikke har gitt det til meg, kanskje mitt program ikke krasje.

240
00:14:43,360 --> 00:14:46,780
Det er rått, det er buggy, men du kan ikke se at symptom,

241
00:14:46,780 --> 00:14:48,960
eller du kan bare se den en gang i blant.

242
00:14:48,960 --> 00:14:51,230
Men realiteten er at feilen er, faktisk, det.

243
00:14:51,230 --> 00:14:54,320
Og det er virkelig problematisk hvis du har skrevet et program som du ønsker å være riktig,

244
00:14:54,320 --> 00:14:58,840
at du har solgt programmet som folk bruker at hver gang en stund krasjer

245
00:14:58,840 --> 00:15:02,450
fordi, selvfølgelig, dette er ikke bra. Faktisk, hvis du har en Android-telefon eller en iPhone

246
00:15:02,450 --> 00:15:05,550
og du laster ned apps i disse dager, hvis du noen gang har hatt en app bare slutte,

247
00:15:05,550 --> 00:15:10,040
plutselig forsvinner, er det nesten alltid et resultat av noen minne-relatert problem,

248
00:15:10,040 --> 00:15:12,830
der programmerer skrudd opp og derefereres en peker

249
00:15:12,830 --> 00:15:18,670
at han eller hun ikke skal ha, og resultatet av iOS eller Android, er å bare drepe programmet helt

250
00:15:18,670 --> 00:15:23,080
heller enn å risikere udefinert atferd eller noen form for sikkerhet kompromiss.

251
00:15:23,080 --> 00:15:25,950
>> Det er en annen bug i dette programmet foruten denne.

252
00:15:25,950 --> 00:15:30,180
Hva annet har jeg skrudd opp i dette programmet?

253
00:15:30,180 --> 00:15:32,740
Jeg har ikke praktisert det jeg har forkynt. Ja?

254
00:15:32,740 --> 00:15:34,760
[Student svar, uforståelig] Bra.

255
00:15:34,760 --> 00:15:36,880
Jeg har ikke frigjort minnet. Så tommelfingerregel nå

256
00:15:36,880 --> 00:15:43,150
må være når du kaller malloc, må du ringe gratis når du er ferdig med å bruke dette minnet.

257
00:15:43,150 --> 00:15:45,610
Nå vil når jeg vil frigjøre dette minnet?

258
00:15:45,610 --> 00:15:49,780
Sannsynligvis, antar dette første linjen var riktig, ville jeg ønsker å gjøre det her.

259
00:15:49,780 --> 00:15:55,710
Fordi jeg ikke kunne, for eksempel, gjør det her nede. Hvorfor?

260
00:15:55,710 --> 00:15:57,860
Bare ut av omfanget. Så selv om vi snakker om pekere,

261
00:15:57,860 --> 00:16:04,830
dette er en uke to eller 3 utgave, der x er kun i omfang innsiden av klammeparentes der det ble erklært.

262
00:16:04,830 --> 00:16:11,000
Så du definitivt ikke kan frigjøre den der. Min eneste sjanse til å frigjøre det er omtrent etter linje 21.

263
00:16:11,000 --> 00:16:15,170
Dette er en ganske enkel program, det var ganske lett når du slags innpakket tankene

264
00:16:15,170 --> 00:16:17,870
rundt hva programmet gjør, hvor feilene var.

265
00:16:17,870 --> 00:16:20,500
Og selv om du ikke ser den først, forhåpentligvis er det litt opplagt nå

266
00:16:20,500 --> 00:16:23,870
at disse feilene er ganske lett løses og enkelt gjort.

267
00:16:23,870 --> 00:16:28,720
Men når et program er mer enn 12 linjer lang, er det 50 linjer lang, 100 linjer lang,

268
00:16:28,720 --> 00:16:31,150
vandre gjennom koden linje for linje, tenke gjennom det logisk,

269
00:16:31,150 --> 00:16:35,110
er mulig, men ikke særlig morsomt å gjøre, stadig på jakt etter feil,

270
00:16:35,110 --> 00:16:38,340
og det er også vanskelig å gjøre, og det er derfor et verktøy som Valgrind eksisterer.

271
00:16:38,340 --> 00:16:40,900
La meg gå videre og gjøre dette: la meg åpne min terminal-vinduet,

272
00:16:40,900 --> 00:16:45,400
og la meg ikke bare kjøre minne, fordi minnet synes å være i orden.

273
00:16:45,400 --> 00:16:49,180
Jeg får heldig. Gå til at ekstra byte ved slutten av tabellen

274
00:16:49,180 --> 00:16:51,060
synes ikke å være for problematisk.

275
00:16:51,060 --> 00:16:56,370
Men la meg likevel, gjør en mental helse sjekk, som bare betyr å sjekke

276
00:16:56,370 --> 00:16:58,320
hvorvidt dette er faktisk riktig.

277
00:16:58,320 --> 00:17:04,690
>> Så la oss gjøre Valgrind-v - lekkasje-sjekk = full,

278
00:17:04,690 --> 00:17:07,520
og deretter navnet på programmet i dette tilfellet er minne, ikke a.out.

279
00:17:07,520 --> 00:17:10,760
Så la meg gå videre og gjøre dette. Trykk Enter.

280
00:17:10,760 --> 00:17:14,109
Kjære Gud. Dette er dens utgang, og dette er hva jeg antydet tidligere.

281
00:17:14,109 --> 00:17:17,550
Men, hvis du lærer å lese gjennom alle de tull her,

282
00:17:17,550 --> 00:17:20,760
meste av dette er bare diagnostisk resultat som ikke er så interessant.

283
00:17:20,760 --> 00:17:24,829
Hva øyet virkelig ønsker å være på jakt etter er noen omtale av feil eller ugyldig.

284
00:17:24,829 --> 00:17:26,800
Ord som tyder problemer.

285
00:17:26,800 --> 00:17:29,340
Og ja, la oss se hva som går galt her nede.

286
00:17:29,340 --> 00:17:35,230
Jeg har en oppsummering av noe slag, "i bruk ved avkjørsel:. 40 bytes i en blokker"

287
00:17:35,230 --> 00:17:38,750
Jeg er ikke helt sikker på hva en blokk er ennå, men 40 bytes

288
00:17:38,750 --> 00:17:41,260
faktisk føles som om jeg kunne finne ut hvor det kommer fra.

289
00:17:41,260 --> 00:17:45,030
40 byte. Hvorfor er 40 byte i bruk ved avkjørsel?

290
00:17:45,030 --> 00:17:48,780
Og mer spesifikt, hvis vi bla nedover her,

291
00:17:48,780 --> 00:17:54,520
hvorfor har jeg definitivt mistet 40 bytes? Ja?

292
00:17:54,520 --> 00:17:59,520
[Student svar, uforståelig] Perfect. Ja, akkurat.

293
00:17:59,520 --> 00:18:03,540
Det var ti heltall, og hver av dem er størrelsen på fire, eller 32 biter,

294
00:18:03,540 --> 00:18:08,300
så jeg har mistet nøyaktig 40 bytes fordi, som du foreslo, jeg har ikke kalles gratis.

295
00:18:08,300 --> 00:18:13,460
Det er en bug, og nå la oss se litt nedover og se ved siden av dette,

296
00:18:13,460 --> 00:18:16,900
"Ugyldig skrive av størrelse 4". Nå hva er dette?

297
00:18:16,900 --> 00:18:21,150
Denne adressen er uttrykt hva basen notasjon, tilsynelatende?

298
00:18:21,150 --> 00:18:23,640
Dette er heksadesimal, og hver gang du ser en som starter med 0x,

299
00:18:23,640 --> 00:18:29,410
det betyr heksadesimal, som vi gjorde helt tilbake i, tror jeg, pset 0-delen av spørsmål,

300
00:18:29,410 --> 00:18:34,090
som var bare for å gjøre en warmup trening, konvertere desimal til hex til binær og så videre.

301
00:18:34,090 --> 00:18:39,220
Heksadesimal, bare av menneskelig konvensjonen, er vanligvis brukes til å representere pekere

302
00:18:39,220 --> 00:18:41,570
eller, mer generelt, adresser. Det er bare en konvensjon,

303
00:18:41,570 --> 00:18:45,340
fordi det er litt lettere å lese, er det litt mer kompakt enn noe sånt som desimal,

304
00:18:45,340 --> 00:18:47,720
og binære er ubrukelig for de fleste mennesker å bruke.

305
00:18:47,720 --> 00:18:50,840
Så nå hva betyr dette? Vel, det ser ut som om det er en ugyldig skrive

306
00:18:50,840 --> 00:18:54,480
av størrelse 4 på linje 21 av memory.c.

307
00:18:54,480 --> 00:18:59,180
Så la oss gå tilbake til linje 21, og ja, her er det ugyldig skrive.

308
00:18:59,180 --> 00:19:02,640
Så Valgrind ikke kommer til å helt holde meg i hånden og fortelle meg hva reparasjonen er,

309
00:19:02,640 --> 00:19:05,520
men det er å oppdage at jeg gjør en ugyldig skrive.

310
00:19:05,520 --> 00:19:08,800
Jeg berøre 4 byte at jeg ikke skulle være, og tilsynelatende det er fordi,

311
00:19:08,800 --> 00:19:13,960
som du påpekte, jeg gjør [10] i stedet for [9] maksimalt

312
00:19:13,960 --> 00:19:16,660
eller [0] eller noe midt i mellom.

313
00:19:16,660 --> 00:19:19,690
Med Valgrind, innser helst du nå skriver et program

314
00:19:19,690 --> 00:19:24,190
som bruker pekere og bruker minne og malloc mer spesifikt,

315
00:19:24,190 --> 00:19:27,080
definitivt komme inn i vanen med å kjøre denne lange

316
00:19:27,080 --> 00:19:30,890
men veldig lett kopieres og limes inn kommandoen over Valgrind

317
00:19:30,890 --> 00:19:32,650
for å se om det er noen feil i det.

318
00:19:32,650 --> 00:19:34,820
Og det vil være overveldende hver gang du ser resultatet,

319
00:19:34,820 --> 00:19:39,430
men bare analysere gjennom visuelt all produksjon og se om du ser nevner av feil

320
00:19:39,430 --> 00:19:43,190
eller advarsler eller ugyldig eller tapt.

321
00:19:43,190 --> 00:19:46,200
Noen ord som høres ut som du skrudd opp et sted.

322
00:19:46,200 --> 00:19:48,580
Så skjønner det er et nytt verktøy i verktøykassen din.

323
00:19:48,580 --> 00:19:51,270
>> Nå på mandag, hadde vi en hel haug med folk kommer opp hit

324
00:19:51,270 --> 00:19:53,150
og representerer oppfatningen av en lenket liste.

325
00:19:53,150 --> 00:20:00,970
Og vi introduserte lenket liste som en løsning på hva problemet?

326
00:20:00,970 --> 00:20:04,590
Ja? [Student svar, uforståelig] Bra.

327
00:20:04,590 --> 00:20:06,530
Arrays kan ikke ha minnet som er lagt til dem.

328
00:20:06,530 --> 00:20:09,440
Hvis du tildeler en rekke størrelse 10, det er alt du får.

329
00:20:09,440 --> 00:20:13,690
Du kan kalle en funksjon som RealLOC hvis du opprinnelig kalt malloc,

330
00:20:13,690 --> 00:20:17,580
og som kan prøve å vokse tabellen hvis det er plass mot slutten av det

331
00:20:17,580 --> 00:20:21,610
at ingen andre bruker, og hvis det ikke er det, vil det bare finne deg en større del et annet sted.

332
00:20:21,610 --> 00:20:25,040
Men så det vil kopiere alle disse byte inn i det nye utvalget.

333
00:20:25,040 --> 00:20:28,310
Dette høres ut som en veldig riktig løsning.

334
00:20:28,310 --> 00:20:34,790
Hvorfor er dette unattractive?

335
00:20:34,790 --> 00:20:36,940
Jeg mener det fungerer, har mennesker løst dette problemet.

336
00:20:36,940 --> 00:20:40,710
Hvorfor gjorde vi trenger å løse det på mandag med koblede lister? Ja?

337
00:20:40,710 --> 00:20:44,060
[Student svar, uforståelig] Det kan ta lang tid.

338
00:20:44,060 --> 00:20:49,260
Faktisk, når som helst du ringer malloc eller RealLOC eller calloc, som er enda en,

339
00:20:49,260 --> 00:20:52,470
hver gang du, programmet, snakker med operativsystemet,

340
00:20:52,470 --> 00:20:54,310
du har en tendens til å bremse programmet ned.

341
00:20:54,310 --> 00:20:57,470
Og hvis du gjør slike ting i looper, er du virkelig bremse ting ned.

342
00:20:57,470 --> 00:21:00,740
Du kommer ikke til å legge merke til dette for den enkleste av "Hello World" type programmer,

343
00:21:00,740 --> 00:21:04,300
men i mye større programmer, spør operativsystemet igjen og igjen for minne

344
00:21:04,300 --> 00:21:07,520
eller gi den tilbake igjen og igjen har en tendens til ikke å være en god ting.

345
00:21:07,520 --> 00:21:11,210
Dessuten er det bare en slags intellektuelt - det er en fullstendig bortkastet tid.

346
00:21:11,210 --> 00:21:16,490
Hvorfor bevilge mer og mer minne, risiko kopiering alt inn i den nye matrisen,

347
00:21:16,490 --> 00:21:21,980
hvis du har et alternativ som lar deg tildele bare så mye minne som du faktisk trenger?

348
00:21:21,980 --> 00:21:24,130
Så det er plusser og minuser i her.

349
00:21:24,130 --> 00:21:26,730
En av de positive nå er at vi har dynamikk.

350
00:21:26,730 --> 00:21:29,100
Spiller ingen rolle hvor biter av minnet er er at gratis,

351
00:21:29,100 --> 00:21:32,070
Jeg kan bare liksom lage disse brødsmuler via pekere

352
00:21:32,070 --> 00:21:34,470
å henge hele mitt lenket liste sammen.

353
00:21:34,470 --> 00:21:36,470
Men jeg betaler minst én pris.

354
00:21:36,470 --> 00:21:40,060
>> Hva må jeg gjøre for å gi opp i å få koblet lister?

355
00:21:40,060 --> 00:21:42,470
Ja? [Student svar, uforståelig] Bra.

356
00:21:42,470 --> 00:21:45,650
Du trenger mer minne. Nå trenger jeg plass til disse pekerne,

357
00:21:45,650 --> 00:21:47,900
og i tilfelle av denne super enkle lenket liste

358
00:21:47,900 --> 00:21:51,410
som bare prøver å lagre heltall, som er 4 byte, holder vi si

359
00:21:51,410 --> 00:21:54,240
vel, er en peker fire bytes, så nå har jeg bokstavelig talt doblet

360
00:21:54,240 --> 00:21:57,290
hvor mye minne trenger jeg bare å lagre denne listen.

361
00:21:57,290 --> 00:21:59,680
Men igjen, dette er en konstant tradeoff i informatikk

362
00:21:59,680 --> 00:22:03,440
mellom tid og rom og utvikling, innsats og andre ressurser.

363
00:22:03,440 --> 00:22:06,630
Hva er en annen ulempe med å bruke en lenket liste? Ja?

364
00:22:06,630 --> 00:22:10,150
[Student svar, uforståelig]

365
00:22:10,150 --> 00:22:12,600
Bra. Ikke så lett å få tilgang. Vi kan ikke lenger utnytte

366
00:22:12,600 --> 00:22:15,530
uke 0 prinsipper som splitt og hersk.

367
00:22:15,530 --> 00:22:18,220
Og mer spesifikt, binær søk. For selv om vi mennesker

368
00:22:18,220 --> 00:22:20,400
kan se omtrent hvor midten av denne listen er,

369
00:22:20,400 --> 00:22:25,840
maskinen vet bare at dette lenket liste starter på adresse som kalles først.

370
00:22:25,840 --> 00:22:28,250
Og det er 0x123 eller noe sånt.

371
00:22:28,250 --> 00:22:30,990
Og den eneste måten programmet kan finne midten element

372
00:22:30,990 --> 00:22:33,350
er å faktisk søke på hele listen.

373
00:22:33,350 --> 00:22:35,500
Og selv da har det bokstavelig talt å søke på hele listen fordi

374
00:22:35,500 --> 00:22:38,950
selv når du har nådd midten element ved å følge pekere,

375
00:22:38,950 --> 00:22:42,380
deg, programmet, har ingen anelse om hvor lenge denne listen er, potensielt,

376
00:22:42,380 --> 00:22:45,250
før du treffer slutten av det, og hvordan vet du programmatisk

377
00:22:45,250 --> 00:22:48,600
at du er på slutten av en lenket liste?

378
00:22:48,600 --> 00:22:51,120
Det er en spesiell NULL-peker, så igjen, en konvensjon.

379
00:22:51,120 --> 00:22:53,870
Snarere enn å bruke denne pekeren, vi definitivt ikke ønsker at det skal være noen søppel verdi

380
00:22:53,870 --> 00:22:57,750
peker av scenen et sted, vi ønsker den skal være hånden ned, NULL,

381
00:22:57,750 --> 00:23:01,530
slik at vi har denne endestasjonen i denne datastruktur slik at vi vet hvor det ender.

382
00:23:01,530 --> 00:23:03,410
>> Hva hvis vi ønsker å manipulere dette?

383
00:23:03,410 --> 00:23:05,980
Vi gjorde det meste av dette visuelt, og med mennesker,

384
00:23:05,980 --> 00:23:07,630
men hva om vi ønsker å gjøre en innsetting?

385
00:23:07,630 --> 00:23:12,360
Så den opprinnelige listen var 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Hva hvis vi da ønsket å malloc plass til nummer 55, en node for det,

387
00:23:16,730 --> 00:23:20,730
og vi vil sette 55 inn på listen akkurat som vi gjorde på mandag?

388
00:23:20,730 --> 00:23:23,690
Hvordan gjør vi dette? Vel, kom Anita og hun egentlig gikk listen.

389
00:23:23,690 --> 00:23:27,500
Hun startet på det første elementet, så neste, neste, neste, neste, neste.

390
00:23:27,500 --> 00:23:29,500
Endelig traff venstre hele veien ned

391
00:23:29,500 --> 00:23:34,480
og realisert oh, dette er NULL. Så hva pekeren manipulasjon måtte gjøres?

392
00:23:34,480 --> 00:23:37,980
Personen som var på slutten, nummer 34, trengte hans venstre hånd hevet

393
00:23:37,980 --> 00:23:46,220
å peke på 55, trengte 55 sin venstre arm peker ned for å bli den nye NULL terminator. Ferdig.

394
00:23:46,220 --> 00:23:49,540
Ganske enkelt å sette 55 i en sortert liste.

395
00:23:49,540 --> 00:23:51,800
Og hvordan kan dette se ut?

396
00:23:51,800 --> 00:23:55,690
>> La meg gå videre og åpne opp noen kode eksempel her.

397
00:23:55,690 --> 00:23:58,120
Jeg vil åpne opp gedit, og la meg åpne opp to filer først.

398
00:23:58,120 --> 00:24:02,050
En er list1.h, og la meg bare minne om at dette var del av koden

399
00:24:02,050 --> 00:24:04,920
som vi brukte til å representere en node.

400
00:24:04,920 --> 00:24:13,040
En node har både en int kalt n og en peker som heter neste som bare peker til neste ting på listen.

401
00:24:13,040 --> 00:24:15,450
Det er nå i en. H fil. Hvorfor?

402
00:24:15,450 --> 00:24:19,090
Det er denne konvensjonen, og vi har ikke tatt fordel av dette et stort beløp oss selv,

403
00:24:19,090 --> 00:24:22,220
men personen som skrev printf og andre funksjoner

404
00:24:22,220 --> 00:24:27,150
ga som gave til verden alle disse funksjonene ved å skrive en fil som heter stdio.h.

405
00:24:27,150 --> 00:24:30,950
Og så er det string.h, og så er det map.h, og det er alle disse h-filene

406
00:24:30,950 --> 00:24:34,410
som du kanskje har sett eller brukt under begrepet skrevet av andre mennesker.

407
00:24:34,410 --> 00:24:38,470
Typisk i disse. H-filer er bare ting som typedefs

408
00:24:38,470 --> 00:24:42,310
eller erklæringer av tilpassede typer eller erklæringer av konstanter.

409
00:24:42,310 --> 00:24:47,890
Du trenger ikke sette funksjoner 'implementeringer i header-filer.

410
00:24:47,890 --> 00:24:50,570
Du setter i stedet, bare sine prototyper.

411
00:24:50,570 --> 00:24:53,050
Du setter ting du ønsker å dele med verden hva de trenger

412
00:24:53,050 --> 00:24:55,640
for å kompilere koden sin. Så bare for å komme inn i denne vanen,

413
00:24:55,640 --> 00:24:59,110
vi besluttet å gjøre det samme. Det er ikke mye i list1.h,

414
00:24:59,110 --> 00:25:02,070
men vi har satt noe som kan være av interesse for folk i hele verden

415
00:25:02,070 --> 00:25:05,030
som ønsker å bruke våre lenket liste gjennomføring.

416
00:25:05,030 --> 00:25:08,040
Nå, i list1.c, jeg vil ikke gå gjennom hele denne greia

417
00:25:08,040 --> 00:25:11,390
fordi det er litt lang, dette programmet, men la oss kjøre det virkelige raskt ved ledeteksten.

418
00:25:11,390 --> 00:25:15,720
La meg kompilere liste1, la meg deretter kjøre liste1, og hva du vil se er

419
00:25:15,720 --> 00:25:18,070
vi har simulert en enkel liten programmet her

420
00:25:18,070 --> 00:25:20,990
som kommer til å tillate meg å legge til og fjerne numre i en liste.

421
00:25:20,990 --> 00:25:24,310
Så la meg gå videre og skrive 3 for menyvalget 3.

422
00:25:24,310 --> 00:25:27,880
Jeg ønsker å sette inn nummer - la oss gjøre det første tallet, som var 9,

423
00:25:27,880 --> 00:25:30,550
og nå er jeg fortalt listen er nå 9.

424
00:25:30,550 --> 00:25:33,760
La meg gå videre og gjøre en annen innsetting, så jeg traff menyvalget 3.

425
00:25:33,760 --> 00:25:36,760
Hvilket nummer ønsker jeg å sette? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Og jeg vil gjøre bare én.

427
00:25:39,220 --> 00:25:41,720
La meg sette nummer 22.

428
00:25:41,720 --> 00:25:45,850
Så vi har begynnelse av lenket liste som vi hadde i lysbilde skjema for et øyeblikk siden.

429
00:25:45,850 --> 00:25:48,740
Hvordan er dette innsetting faktisk skjer?

430
00:25:48,740 --> 00:25:52,000
Faktisk, er 22 nå ved slutten av listen.

431
00:25:52,000 --> 00:25:55,050
Så den historien vi fortalte på scenen på mandag og recapped akkurat nå

432
00:25:55,050 --> 00:25:57,460
må faktisk skje i koden.

433
00:25:57,460 --> 00:25:59,700
La oss ta en titt. La meg bla nedover i denne filen.

434
00:25:59,700 --> 00:26:01,720
Vi vil glatte over noen av funksjonene,

435
00:26:01,720 --> 00:26:05,630
men vi vil gå ned til, si, innsatsen funksjonen.

436
00:26:05,630 --> 00:26:11,720
>> La oss se hvordan vi går om å sette inn en ny node i denne lenket liste.

437
00:26:11,720 --> 00:26:14,550
Hvor er listen erklært? Vel, la oss rulle hele veien opp på toppen,

438
00:26:14,550 --> 00:26:19,970
og legge merke til at min lenket liste er egentlig erklært som en enkelt peker som er utgangspunktet NULL.

439
00:26:19,970 --> 00:26:23,180
Så jeg bruker en global variabel her, som generelt har vi forkynt mot

440
00:26:23,180 --> 00:26:25,280
fordi det gjør koden litt rotete å vedlikeholde,

441
00:26:25,280 --> 00:26:29,080
Det er liksom lat, vanligvis, men det er ikke lat, og det er ikke galt, og det er ikke dårlig

442
00:26:29,080 --> 00:26:33,660
hvis programmet eneste mål i livet er å simulere en lenket liste.

443
00:26:33,660 --> 00:26:35,460
Som er akkurat hva vi gjør.

444
00:26:35,460 --> 00:26:39,100
Så i stedet for å erklære dette i main og deretter måtte gi det til hver funksjon

445
00:26:39,100 --> 00:26:42,640
vi har skrevet i dette programmet, vi i stedet innse oh, la oss bare gjøre det globale

446
00:26:42,640 --> 00:26:47,060
fordi hele hensikten med dette programmet er å demonstrere én og bare én lenket liste.

447
00:26:47,060 --> 00:26:50,700
Så det føles greit. Her er mine prototyper, og vi vil ikke gå gjennom alle disse,

448
00:26:50,700 --> 00:26:55,800
men jeg skrev en slett-funksjon, en finne funksjon, et innstikk funksjon, og en travers funksjon.

449
00:26:55,800 --> 00:26:59,080
Men la oss nå gå tilbake til innsatsen funksjonen

450
00:26:59,080 --> 00:27:01,490
og se hvordan dette fungerer her.

451
00:27:01,490 --> 00:27:09,940
Innsatsen er på linje - here we go.

452
00:27:09,940 --> 00:27:12,850
Sett inn. Slik at den ikke tar noen argumenter, fordi vi kommer til å be

453
00:27:12,850 --> 00:27:15,930
brukeren innsiden av denne funksjonen for antall de ønsker å sette inn.

454
00:27:15,930 --> 00:27:19,410
Men først, forbereder vi å gi dem litt plass.

455
00:27:19,410 --> 00:27:22,050
Dette er liksom kopiere og lime inn fra den andre eksempel.

456
00:27:22,050 --> 00:27:25,110
I så fall var vi fordele en int, denne gangen vi fordele en node.

457
00:27:25,110 --> 00:27:27,910
Jeg vet egentlig ikke huske hvor mange byte en node er, men det er fint.

458
00:27:27,910 --> 00:27:30,460
Sizeof kan finne det ut for meg.

459
00:27:30,460 --> 00:27:33,340
Og hvorfor er jeg sjekker for NULL i linje 120?

460
00:27:33,340 --> 00:27:37,530
Hva kan gå galt i tråd 119? Ja?

461
00:27:37,530 --> 00:27:40,530
[Student svar, uforståelig]

462
00:27:40,530 --> 00:27:43,440
Bra. Bare kunne være tilfelle at jeg har bedt om for mye minne

463
00:27:43,440 --> 00:27:47,020
eller noe er galt og operativsystemet ikke har nok byte til å gi meg,

464
00:27:47,020 --> 00:27:50,640
så det signaliserer så mye ved retur NULL, og hvis jeg ikke se etter at

465
00:27:50,640 --> 00:27:54,710
og jeg bare blindt fortsette å bruke adressen tilbake, kan det være NULL.

466
00:27:54,710 --> 00:27:58,400
Det kan være noen ukjent verdi, ikke en god ting med mindre jeg -

467
00:27:58,400 --> 00:28:00,590
faktisk vil ikke være en ukjent verdi. Det kan være NULL, så jeg ønsker ikke

468
00:28:00,590 --> 00:28:02,550
å misbruke det og risikere dereferencing det.

469
00:28:02,550 --> 00:28:07,410
Hvis det skjer, jeg bare gå tilbake og vi vil late som om jeg ikke får tilbake noe minne i det hele tatt.

470
00:28:07,410 --> 00:28:12,270
>> Ellers har jeg fortelle brukeren gi meg et nummer for å sette inn, kaller jeg vår gamle venn GetInt,

471
00:28:12,270 --> 00:28:15,530
og så dette var den nye syntaksen vi introdusert på mandag.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' betyr å ta den adressen du fikk av malloc

473
00:28:20,320 --> 00:28:23,490
som representerer den første byte av en ny node objekt,

474
00:28:23,490 --> 00:28:26,860
og deretter gå til feltet som heter n.

475
00:28:26,860 --> 00:28:35,270
Litt trivia spørsmål: Dette tilsvarer hva mer kryptisk kodelinje?

476
00:28:35,270 --> 00:28:38,110
Hvordan ellers kunne jeg ha skrevet dette? Ønsker du å ta et stikk?

477
00:28:38,110 --> 00:28:41,480
[Student svar, uforståelig]

478
00:28:41,480 --> 00:28:44,870
Bra. Bruke. N, men det er ikke fullt så enkelt som dette.

479
00:28:44,870 --> 00:28:47,090
Hva gjør jeg først må gjøre? [Student svar, uforståelig]

480
00:28:47,090 --> 00:28:52,730
Bra. Jeg trenger å gjøre * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Så dette sier ny pekeren er åpenbart en adresse. Hvorfor?

482
00:28:55,610 --> 00:28:59,520
Fordi det ble returnert av malloc. Den * newptr sier "gå dit"

483
00:28:59,520 --> 00:29:02,970
og deretter en gang du er der, så kan du bruke mer kjent. n,

484
00:29:02,970 --> 00:29:05,730
men dette ser bare litt stygg, spesielt hvis vi mennesker kommer til å

485
00:29:05,730 --> 00:29:10,360
tegne pekere med piler hele tiden, verden har standardisert på denne pilen notasjon,

486
00:29:10,360 --> 00:29:12,320
som gjør akkurat det samme.

487
00:29:12,320 --> 00:29:16,070
Så du bare bruke -> notasjon når ting på venstre er en peker.

488
00:29:16,070 --> 00:29:18,790
Ellers, hvis det er en faktisk struct, bruker. N.

489
00:29:18,790 --> 00:29:25,800
Og så dette: Hvorfor initialisere jeg newptr-> neste til NULL?

490
00:29:25,800 --> 00:29:28,610
Vi ønsker ikke en dinglende venstre hånd ut av slutten av etappen.

491
00:29:28,610 --> 00:29:31,630
Vi ønsker at det peker rett ned, noe som betyr slutten på denne listen

492
00:29:31,630 --> 00:29:34,980
kan potensielt være på denne noden, slik at vi bedre sørge for at det er NULL.

493
00:29:34,980 --> 00:29:38,460
Og generelt, initialiseres variabler eller dine data medlemmer og structs

494
00:29:38,460 --> 00:29:40,470
til noe er bare god praksis.

495
00:29:40,470 --> 00:29:45,170
Bare la søppel eksisterer og fortsetter å eksistere generelt får deg i trøbbel

496
00:29:45,170 --> 00:29:48,650
Hvis du glemmer å gjøre noe senere.

497
00:29:48,650 --> 00:29:51,590
>> Her er noen få tilfeller. Dette, igjen, er innsatsen funksjonen,

498
00:29:51,590 --> 00:29:54,930
og det første jeg se etter er om variabel kalt først,

499
00:29:54,930 --> 00:29:58,240
at global variabel er NULL, betyr at det er ingen lenket liste.

500
00:29:58,240 --> 00:30:02,460
Vi har ikke satt noen tall, så det er trivielt å sette denne aktuelle nummeret

501
00:30:02,460 --> 00:30:05,240
inn på listen, fordi den tilhører bare ved starten av listen.

502
00:30:05,240 --> 00:30:08,100
Så dette var da Anita ble bare stående her oppe alene, late

503
00:30:08,100 --> 00:30:11,390
ingen andre var her oppe på scenen før vi tildelt en node,

504
00:30:11,390 --> 00:30:13,940
så hun kunne løfte hånden for første gang,

505
00:30:13,940 --> 00:30:17,420
hvis alle andre hadde kommet opp på scenen etter henne på mandag.

506
00:30:17,420 --> 00:30:22,900
Nå her, dette er en liten sjekk hvor jeg har å si om den nye nodens verdi av n

507
00:30:22,900 --> 00:30:27,370
er <verdien av n i gjeldende første noden,

508
00:30:27,370 --> 00:30:29,930
det betyr at det er en lenket liste som er begynt.

509
00:30:29,930 --> 00:30:32,330
Det er minst én node i listen, men denne nye fyren

510
00:30:32,330 --> 00:30:37,230
hører før det, så vi trenger å flytte ting rundt.

511
00:30:37,230 --> 00:30:43,450
Med andre ord, hvis listen har startet med bare, la oss si,

512
00:30:43,450 --> 00:30:48,100
bare nummer 17, som er den - faktisk, kan vi gjøre dette mer tydelig.

513
00:30:48,100 --> 00:30:56,010
Hvis vi starter vår historie med en peker her kalt først,

514
00:30:56,010 --> 00:30:59,870
og i utgangspunktet er det NULL, og vi setter inn tallet 9,

515
00:30:59,870 --> 00:31:02,510
tallet 9 tilhører tydelig ved starten av listen.

516
00:31:02,510 --> 00:31:07,400
Så la oss late som vi bare malloced adressen eller tallet 9 og sette den her.

517
00:31:07,400 --> 00:31:13,170
Hvis første er 9 som standard, betyr det første scenariet vi diskuterte bare la oss poeng denne fyren her,

518
00:31:13,170 --> 00:31:15,790
la dette som NULL, nå har vi nummer 9.

519
00:31:15,790 --> 00:31:18,280
Neste nummer vil vi sette inn er 17..

520
00:31:18,280 --> 00:31:22,420
17 tilhører over her, så vi er nødt til å gjøre noen logisk stepping gjennom dette.

521
00:31:22,420 --> 00:31:26,060
Så la oss i stedet, før vi gjør det, la oss late som vi ønsket å sette inn nummer åtte.

522
00:31:26,060 --> 00:31:28,650
>> Så bare for enkelhets skyld, jeg kommer til å trekke her.

523
00:31:28,650 --> 00:31:30,760
Men husk, kan malloc sette den de fleste steder.

524
00:31:30,760 --> 00:31:33,460
Men for tegning skyld, vil jeg si det her.

525
00:31:33,460 --> 00:31:38,440
Så late som jeg har nettopp tildelt en node for nummer 8, og dette er NULL som standard.

526
00:31:38,440 --> 00:31:42,800
Hva må nå skje? Et par ting.

527
00:31:42,800 --> 00:31:47,090
Vi har gjort dette feil på scenen på mandag hvor vi oppdatert en peker som dette,

528
00:31:47,090 --> 00:31:51,890
Deretter gjorde dette, og da vi hevdet - vi foreldreløse alle andre på scenen.

529
00:31:51,890 --> 00:31:54,350
Fordi du L ° vernes - rekkefølgen av operasjoner her er viktig,

530
00:31:54,350 --> 00:31:58,760
fordi nå har vi mistet denne noden 9 som er bare slags flyter i verdensrommet.

531
00:31:58,760 --> 00:32:01,150
Så dette var ikke den rette tilnærmingen på mandag.

532
00:32:01,150 --> 00:32:03,330
Vi først må gjøre noe annet.

533
00:32:03,330 --> 00:32:06,280
Delstaten verden ser slik ut. Utgangspunktet, 8 er blitt tildelt.

534
00:32:06,280 --> 00:32:10,550
Hva ville være en bedre måte å sette 8?

535
00:32:10,550 --> 00:32:14,720
Stedet for å oppdatere denne pekeren første, bare oppdatere denne her i stedet.

536
00:32:14,720 --> 00:32:17,720
Så vi trenger en linje med kode som kommer til å snu denne NULL karakter

537
00:32:17,720 --> 00:32:22,020
til en faktisk peker som er peker på node 9,

538
00:32:22,020 --> 00:32:27,970
og da kan vi trygt endre først å peke på denne fyren her.

539
00:32:27,970 --> 00:32:31,330
Nå har vi en liste, en lenket liste, av to elementer.

540
00:32:31,330 --> 00:32:33,580
Og hva betyr dette egentlig ser ut her?

541
00:32:33,580 --> 00:32:36,900
Hvis vi ser på koden, merker at jeg har gjort akkurat det.

542
00:32:36,900 --> 00:32:41,970
Jeg har sagt newptr, og i denne historien, ble newptr peker på denne fyren.

543
00:32:41,970 --> 00:32:45,520
>> Så la meg trekke en ting, og jeg burde ha igjen litt mer rom for dette.

544
00:32:45,520 --> 00:32:48,540
Så tilgi bitte liten tegning.

545
00:32:48,540 --> 00:32:52,140
Denne fyren heter newptr.

546
00:32:52,140 --> 00:32:57,940
Det er variabelen vi erklært noen linjer tidligere, i tråd - like over 25.

547
00:32:57,940 --> 00:33:03,430
Og den peker til 8. Så når jeg sier newptr-> neste, som betyr å gå til struct

548
00:33:03,430 --> 00:33:07,910
som blir pekt på av newptr, så her er vi, gå dit.

549
00:33:07,910 --> 00:33:13,990
Da pilen sier få det neste feltet, og deretter = sier sette hvilken verdi det?

550
00:33:13,990 --> 00:33:17,280
Verdien som var i første, hva verdien var i først?

551
00:33:17,280 --> 00:33:21,930
Først var peker på denne noden, så det betyr at dette bør nå peke på denne noden.

552
00:33:21,930 --> 00:33:25,660
Med andre ord, ser det riktignok en latterlig rot med håndskrift min,

553
00:33:25,660 --> 00:33:28,620
hva er en enkel idé om bare å flytte disse pilene rundt

554
00:33:28,620 --> 00:33:31,560
oversettes til kode med bare denne ene liner.

555
00:33:31,560 --> 00:33:38,110
Lagre hva som er i først i det neste feltet og deretter oppdatere hva første faktisk er.

556
00:33:38,110 --> 00:33:40,900
La oss gå videre og spole fremover gjennom noe av dette,

557
00:33:40,900 --> 00:33:44,220
og ser bare på dette halen innsetting for nå.

558
00:33:44,220 --> 00:33:51,210
Anta jeg får til det punktet hvor jeg synes at det neste feltet av noen node er NULL.

559
00:33:51,210 --> 00:33:53,410
Og på dette punktet i historien, en detalj som jeg glatter over

560
00:33:53,410 --> 00:33:58,170
er at jeg har introdusert en annen pekeren opp her i 142 linje, forgjenger pekeren.

561
00:33:58,170 --> 00:34:01,320
Hovedsak, på dette punktet i historien, når listen blir lang,

562
00:34:01,320 --> 00:34:04,800
Jeg slags behov for å gå den med to fingre fordi hvis jeg går for langt,

563
00:34:04,800 --> 00:34:08,219
husk i en enkelt lengde, kan du ikke gå bakover.

564
00:34:08,219 --> 00:34:13,659
Så denne ideen predptr er min venstre finger, og newptr - ikke newptr.

565
00:34:13,659 --> 00:34:17,199
En annen peker som er her er min andre finger, og jeg er bare slags vandre listen.

566
00:34:17,199 --> 00:34:22,179
Det er derfor det finnes. Men la oss bare vurdere en av de enklere sakene her.

567
00:34:22,179 --> 00:34:26,620
Hvis det pekerens neste felt er NULL, hva er den logiske implikasjon?

568
00:34:26,620 --> 00:34:30,840
Hvis du er traversing denne listen og du treffer en NULL-peker?

569
00:34:30,840 --> 00:34:35,780
Du er på slutten av listen, og så koden for å deretter legge dette en ekstra element

570
00:34:35,780 --> 00:34:41,230
er liksom den intuitive vil ta den noden som neste pekeren er NULL,

571
00:34:41,230 --> 00:34:46,120
så dette er tiden NULL, og endre den, men å være adressen til den nye noden.

572
00:34:46,120 --> 00:34:52,260
Så vi bare tegne i koden pilen som vi trakk på scenen ved å heve noens venstre hånd.

573
00:34:52,260 --> 00:34:54,070
>> Og saken som jeg vil vinke hendene mine på for nå,

574
00:34:54,070 --> 00:34:58,020
bare fordi jeg tror det er lett å gå seg vill når vi gjør det i denne typen miljø,

575
00:34:58,020 --> 00:35:00,600
sjekker for innsetting på listens midten.

576
00:35:00,600 --> 00:35:03,220
Men bare intuitivt, hva må skje hvis du ønsker å finne ut

577
00:35:03,220 --> 00:35:06,600
hvor noen nummeret tilhører i midten er du nødt til å gå den

578
00:35:06,600 --> 00:35:09,510
med mer enn én finger, mer enn én pekeren,

579
00:35:09,510 --> 00:35:12,920
finne ut hvor den hører hjemme ved kontroll er element <den nåværende,

580
00:35:12,920 --> 00:35:15,450
> Den nåværende, og når du finner dette stedet,

581
00:35:15,450 --> 00:35:20,400
så må du gjøre denne typen skallet spill hvor du beveger pekere rundt svært nøye.

582
00:35:20,400 --> 00:35:23,850
Og det svaret, hvis du ønsker å resonnere gjennom dette hjemme på egen hånd,

583
00:35:23,850 --> 00:35:28,340
koker ned bare til disse to linjene med kode, men rekkefølgen på disse linjene er super viktig.

584
00:35:28,340 --> 00:35:31,390
Fordi hvis du slipper noens hånd og heve en annens i feil rekkefølge,

585
00:35:31,390 --> 00:35:34,580
igjen, kan du ende opp orphaning listen.

586
00:35:34,580 --> 00:35:39,500
Å oppsummere mer konseptuelt, er innsetting på halen relativt enkelt.

587
00:35:39,500 --> 00:35:42,940
Innsetting på hodet er også relativt enkelt,

588
00:35:42,940 --> 00:35:45,580
men du må oppdatere en ekstra peker denne gangen

589
00:35:45,580 --> 00:35:47,930
å presse nummer 5 i listen her,

590
00:35:47,930 --> 00:35:51,560
og deretter innsetting i midten omfatter enda mer innsats,

591
00:35:51,560 --> 00:35:56,130
til veldig forsiktig sette nummer 20 i sin korrekte sted,

592
00:35:56,130 --> 00:35:58,350
som er mellom 17 og 22.

593
00:35:58,350 --> 00:36:02,700
Så du trenger å gjøre noe som har den nye noden 20 poeng til 22,

594
00:36:02,700 --> 00:36:08,470
og deretter må som nodens pekeren for å bli oppdatert sist?

595
00:36:08,470 --> 00:36:10,630
Det er 17, å faktisk sette det inn.

596
00:36:10,630 --> 00:36:14,080
Så igjen, jeg utsette den faktiske koden for den aktuelle gjennomføring.

597
00:36:14,080 --> 00:36:17,280
>> Ved første øyekast, er det litt overveldende, men det er egentlig bare en uendelig løkke

598
00:36:17,280 --> 00:36:21,770
som er looping, looping, looping, looping, og bryte så snart du treffer NULL-peker,

599
00:36:21,770 --> 00:36:24,590
på hvilket tidspunkt du kan gjøre de nødvendige innsetting.

600
00:36:24,590 --> 00:36:30,960
Dette er altså representativt lenket liste koden for innsetting.

601
00:36:30,960 --> 00:36:34,590
Det var snilt av mye, og det føles som vi har løst et problem,

602
00:36:34,590 --> 00:36:36,940
men vi har innført en helt annen en. Oppriktig, vi har brukt all denne tiden

603
00:36:36,940 --> 00:36:40,540
på stor O og Ω og kjører tid, prøver å løse problemer raskere,

604
00:36:40,540 --> 00:36:43,270
og her tar vi et stort skritt bakover, det føles.

605
00:36:43,270 --> 00:36:45,380
Og likevel, hvis målet er å lagre data,

606
00:36:45,380 --> 00:36:48,010
det føles som den hellige gral, som vi sa på mandag, ville virkelig være

607
00:36:48,010 --> 00:36:50,470
å lagre ting umiddelbart.

608
00:36:50,470 --> 00:36:53,930
>> Faktisk anta at vi gjorde satt til side lenket liste for et øyeblikk

609
00:36:53,930 --> 00:36:56,000
og vi i stedet introduserte begrepet i en tabell.

610
00:36:56,000 --> 00:36:59,110
Og la oss bare tenke på en tabell for et øyeblikk som en matrise.

611
00:36:59,110 --> 00:37:03,790
Denne tabellen og denne saken her har ca 26 elementer, 0 til 25,

612
00:37:03,790 --> 00:37:07,940
og anta at du trengte noen del av lagringsplass for navn:

613
00:37:07,940 --> 00:37:10,350
Alice og Bob og Charlie og lignende.

614
00:37:10,350 --> 00:37:12,880
Og du trenger litt datastruktur for å lagre disse navnene.

615
00:37:12,880 --> 00:37:15,000
Vel, du kan bruke noe sånt som en lenket liste

616
00:37:15,000 --> 00:37:20,260
og du kan gå listen sette Alice før Bob og Charlie etter Bob og så videre.

617
00:37:20,260 --> 00:37:23,850
Og, faktisk, hvis du ønsker å se kode sånn som en side,

618
00:37:23,850 --> 00:37:27,230
vet at i list2.h, gjør vi akkurat det.

619
00:37:27,230 --> 00:37:30,610
Vi vil ikke gå gjennom denne koden, men dette er en variant av det første eksempelet

620
00:37:30,610 --> 00:37:34,640
som introduserer en annen struct vi har sett før kalt student,

621
00:37:34,640 --> 00:37:40,330
og hva det faktisk lagrer i lenket liste er en peker til en student struktur

622
00:37:40,330 --> 00:37:44,520
snarere enn en enkel liten heltall.

623
00:37:44,520 --> 00:37:46,900
Så skjønner det er kode det som involverer faktiske strenger,

624
00:37:46,900 --> 00:37:49,940
men hvis målet på hånden virkelig nå er å ta effektiviteten problem,

625
00:37:49,940 --> 00:37:53,380
ville det ikke vært fint hvis vi får et objekt kalt Alice,

626
00:37:53,380 --> 00:37:56,020
Vi ønsker å sette henne inn på riktig sted i en datastruktur,

627
00:37:56,020 --> 00:37:58,860
det føles som om det ville være veldig hyggelig å bare sette Alice,

628
00:37:58,860 --> 00:38:01,180
med navn som starter med A, i den første plasseringen.

629
00:38:01,180 --> 00:38:05,270
Og Bob, med navn som starter med B, i den andre plasseringen.

630
00:38:05,270 --> 00:38:09,580
Med en matrise, eller la oss begynne å kalle det en tabell, en hash tabell på det,

631
00:38:09,580 --> 00:38:13,650
vi kan gjøre akkurat det. Hvis vi får et navn som Alice,

632
00:38:13,650 --> 00:38:16,700
en streng som Alice, hvor du setter A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Vi trenger en hueristic. Vi trenger en funksjon for å ta noen innspill som Alice

634
00:38:20,540 --> 00:38:24,610
og returnere et svar, "Sett Alice på dette stedet."

635
00:38:24,610 --> 00:38:28,720
Og denne funksjonen, denne svarte boksen, kommer til å bli kalt en hash-funksjon.

636
00:38:28,720 --> 00:38:32,330
>> En hash-funksjon er noe som tar en inngang, som "Alice",

637
00:38:32,330 --> 00:38:38,080
og returnerer til deg, vanligvis den numeriske plasseringen i noen datastruktur der Alice tilhører.

638
00:38:38,080 --> 00:38:40,830
I dette tilfellet, bør vår hash-funksjon være relativt enkel.

639
00:38:40,830 --> 00:38:47,510
Vår hash-funksjon skal si, hvis du får "Alice", som tegn skal jeg bry meg om?

640
00:38:47,510 --> 00:38:55,660
Den første. Så jeg ser på [0], og da sier jeg hvis [0] karakter er A, returnere tallet 0.

641
00:38:55,660 --> 00:39:01,130
Hvis det er B, tilbake 1. Hvis det er C, returnere 2, og så videre.

642
00:39:01,130 --> 00:39:05,940
Alle 0-indeksen, og som ville tillate meg å sette Alice og deretter Bob og deretter Charlie og så videre

643
00:39:05,940 --> 00:39:10,960
inn i denne datastruktur. Men det er et problem.

644
00:39:10,960 --> 00:39:13,060
Hva om Anita kommer sammen igjen?

645
00:39:13,060 --> 00:39:17,510
Hvor plasserer vi Anita? Hennes navn også, begynner med bokstaven A,

646
00:39:17,510 --> 00:39:20,330
og det føles som om vi har gjort en enda større rot av dette problemet.

647
00:39:20,330 --> 00:39:24,380
Vi har nå umiddelbar innsetting, konstant tid innsetting, i en datastruktur

648
00:39:24,380 --> 00:39:27,100
heller enn verre-sak lineær,

649
00:39:27,100 --> 00:39:29,510
men hva kan vi gjøre med Anita i dette tilfellet?

650
00:39:29,510 --> 00:39:34,110
Hva er de to alternativene, egentlig? Ja?

651
00:39:34,110 --> 00:39:37,410
[Student svar, uforståelig] Ok, så vi kunne ha en annen dimensjon.

652
00:39:37,410 --> 00:39:42,320
Det er bra. Så vi kan bygge ting ut i 3D som vi snakket om verbalt på mandag.

653
00:39:42,320 --> 00:39:46,700
Vi kunne legge til en annen tilgang her, men antar at nei, jeg prøver å holde dette enkelt.

654
00:39:46,700 --> 00:39:50,160
Hele målet her er å ha umiddelbar konstant tid tilgang,

655
00:39:50,160 --> 00:39:52,170
slik at det er å legge for mye kompleksitet.

656
00:39:52,170 --> 00:39:55,970
Hva er andre alternativer når du prøver å sette inn Anita inn i denne datastrukturen? Ja?

657
00:39:55,970 --> 00:39:58,610
[Student svar, uforståelig] Bra. Så kunne vi gå alle andre ned,

658
00:39:58,610 --> 00:40:03,040
som Charlie nudge ned Bob og Alice, og deretter setter vi Anita hvor hun virkelig ønsker å være.

659
00:40:03,040 --> 00:40:05,660
>> Selvfølgelig, nå er det en bivirkning av dette.

660
00:40:05,660 --> 00:40:09,000
Dette datastruktur er sikkert nyttig, ikke fordi vi ønsker å sette folk en gang

661
00:40:09,000 --> 00:40:11,250
men fordi vi ønsker å undersøke om de er der senere

662
00:40:11,250 --> 00:40:13,600
hvis vi ønsker å skrive ut alle navnene i datastrukturen.

663
00:40:13,600 --> 00:40:15,850
Vi kommer til å gjøre noe med disse dataene til slutt.

664
00:40:15,850 --> 00:40:20,810
Så nå har vi slags skrudd over Alice, som ikke lenger hvor hun er ment å være.

665
00:40:20,810 --> 00:40:23,880
Det er heller ikke Bob, er heller Charlie.

666
00:40:23,880 --> 00:40:26,060
Så kanskje dette er ikke en så god idé.

667
00:40:26,060 --> 00:40:28,830
Men faktisk er dette ett alternativ. Vi kunne skifte alle ned,

668
00:40:28,830 --> 00:40:32,240
eller pokker, Anita kom sent til spillet, hvorfor ikke vi bare sette Anita

669
00:40:32,240 --> 00:40:35,870
ikke her, ikke her, ikke her, la oss bare sette henne litt ned på listen.

670
00:40:35,870 --> 00:40:38,680
Men da dette problemet begynner å devolve igjen.

671
00:40:38,680 --> 00:40:41,630
Du kan være i stand til å finne Alice umiddelbart, basert på hennes fornavn.

672
00:40:41,630 --> 00:40:44,320
Og Bob umiddelbart, og Charlie. Men da du ser etter Anita,

673
00:40:44,320 --> 00:40:46,360
og du ser, hmm, er Alice i veien.

674
00:40:46,360 --> 00:40:48,770
Vel, la meg sjekke under Alice. Bob er ikke Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie er ikke Anita. Åh, det er Anita.

676
00:40:51,850 --> 00:40:54,720
Og hvis du fortsetter som trener for logikk hele veien,

677
00:40:54,720 --> 00:41:00,690
hva er det verst tenkelige kjøretid på å finne eller sette Anita inn i denne nye datastrukturen?

678
00:41:00,690 --> 00:41:03,280
Det er O (n), ikke sant?

679
00:41:03,280 --> 00:41:06,280
Fordi i verste fall, det er Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
helt ned til noen som heter "Y", så det er bare én plass igjen.

681
00:41:10,150 --> 00:41:13,950
Heldigvis har vi ingen kalt "Z", så vi satt Anita på bunnen.

682
00:41:13,950 --> 00:41:16,040
>> Vi har egentlig ikke løst det problemet.

683
00:41:16,040 --> 00:41:19,890
Så kanskje vi trenger å innføre denne tredje dimensjonen.

684
00:41:19,890 --> 00:41:22,230
Og det viser seg, hvis vi introdusere denne tredje dimensjonen,

685
00:41:22,230 --> 00:41:25,240
vi kan ikke gjøre dette perfekt, men den hellige gral kommer til å være å få

686
00:41:25,240 --> 00:41:28,370
konstant tid innsetting og dynamiske innsettinger slik at

687
00:41:28,370 --> 00:41:30,960
Vi trenger ikke å hard-kode en rekke størrelse 26.

688
00:41:30,960 --> 00:41:34,400
Vi kan sette så mange navn som vi ønsker, men la oss ta vår 5-minutters pause her

689
00:41:34,400 --> 00:41:38,790
og deretter gjøre det ordentlig.

690
00:41:38,790 --> 00:41:46,020
OK. Jeg satt historien opp ganske kunstig der

691
00:41:46,020 --> 00:41:48,670
ved å velge Alice og deretter Bob og deretter Charlie og Anita,

692
00:41:48,670 --> 00:41:51,000
hvis navn ble åpenbart kommer til å kollidere med Alice.

693
00:41:51,000 --> 00:41:54,120
Men spørsmålet vi endte på mandag med er bare hvor sannsynlig er det

694
00:41:54,120 --> 00:41:56,370
at du ville få slike kollisjoner? Med andre ord,

695
00:41:56,370 --> 00:42:00,490
hvis vi begynner å bruke denne tabellform struktur, som er egentlig bare en matrise,

696
00:42:00,490 --> 00:42:02,460
i dette tilfellet av 26 steder,

697
00:42:02,460 --> 00:42:05,740
hva om våre innganger er stedet jevnt fordelt?

698
00:42:05,740 --> 00:42:09,620
Det er ikke kunstig Alice og Bob og Charlie og David og så videre alfabetisk,

699
00:42:09,620 --> 00:42:12,380
det er jevnt fordelt over A til Z.

700
00:42:12,380 --> 00:42:15,220
>> Kanskje vi bare få heldige og vi kommer ikke til å ha to A-eller to B

701
00:42:15,220 --> 00:42:17,640
med meget høy sannsynlighet, men som noen påpekt,

702
00:42:17,640 --> 00:42:20,730
hvis vi generalisert dette problemet, og ikke gjøre 0-25

703
00:42:20,730 --> 00:42:26,060
men, si, 0 gjennom 364 eller 65, ofte antall dager i en typisk år,

704
00:42:26,060 --> 00:42:31,170
og spurte spørsmålet: «Hva er sannsynligheten for at to av oss i dette rommet har samme bursdag?"

705
00:42:31,170 --> 00:42:34,600
Sagt på en annen måte, hva er sannsynligheten for at to av oss har et navn som starter med A?

706
00:42:34,600 --> 00:42:37,190
Slags spørsmålet er den samme, men dette adresserom,

707
00:42:37,190 --> 00:42:39,940
dette søket plass, er større i tilfelle av bursdager,

708
00:42:39,940 --> 00:42:42,820
fordi vi har så mange flere dager i året enn bokstaver i alfabetet.

709
00:42:42,820 --> 00:42:44,910
Hva er sannsynligheten for en kollisjon?

710
00:42:44,910 --> 00:42:48,410
Vel, vi kan tenke på dette ved å finne ut regnestykket motsatt vei.

711
00:42:48,410 --> 00:42:50,580
Hva er sannsynligheten for ingen kollisjoner?

712
00:42:50,580 --> 00:42:53,970
Vel, sier dette uttrykket her at det er sannsynligheten

713
00:42:53,970 --> 00:42:58,770
hvis det er bare en person i dette rommet, at de har en unik bursdag?

714
00:42:58,770 --> 00:43:01,190
Det er 100%. Fordi hvis det er bare én person i rommet,

715
00:43:01,190 --> 00:43:03,940
hans eller hennes bursdag kan være noen av de 365 dagene av året.

716
00:43:03,940 --> 00:43:08,650
Så 365/365 opsjoner gir meg en verdi på 1.

717
00:43:08,650 --> 00:43:11,250
Så sannsynligheten aktuelle i øyeblikket er bare ett.

718
00:43:11,250 --> 00:43:13,270
Men hvis det er en annen person i rommet,

719
00:43:13,270 --> 00:43:16,490
hva er sannsynligheten for at deres fødselsdag er annerledes?

720
00:43:16,490 --> 00:43:20,680
Det er bare 364 mulige dager, ignorerer skuddår,

721
00:43:20,680 --> 00:43:23,580
til bursdagen sin for ikke å kollidere med andre personer.

722
00:43:23,580 --> 00:43:31,920
Så 364/365. Hvis en tredje person kommer inn, er det 363/365, og så videre.

723
00:43:31,920 --> 00:43:35,790
Så vi holder multiplisere sammen disse fraksjonene, som blir mindre og mindre,

724
00:43:35,790 --> 00:43:40,720
å finne ut hva er sannsynligheten for at alle av oss har unike bursdager?

725
00:43:40,720 --> 00:43:43,570
Men da kan vi selvfølgelig bare ta det svaret og snu den rundt

726
00:43:43,570 --> 00:43:47,210
og gjøre en minus alt dette, et uttrykk vi vil til slutt få

727
00:43:47,210 --> 00:43:51,250
hvis du husker på baksiden av matematiske bøker, ser det litt noe sånt som dette,

728
00:43:51,250 --> 00:43:54,590
som er mye lettere tolket grafisk.

729
00:43:54,590 --> 00:43:57,820
Og dette grafisk her har på x-aksen antall bursdager,

730
00:43:57,820 --> 00:44:02,030
eller antall personer med bursdager, og på y-aksen er sannsynligheten for en kamp.

731
00:44:02,030 --> 00:44:06,060
Og hva dette sier er at hvis du har, la oss si, selv,

732
00:44:06,060 --> 00:44:10,860
la oss velge noe som 22, 23.

733
00:44:10,860 --> 00:44:13,160
Hvis det er 22 eller 23 personer i rommet,

734
00:44:13,160 --> 00:44:17,100
sannsynligheten for at to av de svært få mennesker kommer til å ha bursdag på samme dag

735
00:44:17,100 --> 00:44:19,560
er faktisk super høy, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% sjanser som i en klasse for kun 22 personer, et seminar, praktisk talt,

737
00:44:23,450 --> 00:44:25,790
2 av dem kommer til å ha bursdag på samme dag.

738
00:44:25,790 --> 00:44:28,520
Fordi det er så mange måter du kan ha samme fødselsdag.

739
00:44:28,520 --> 00:44:31,110
Enda verre, hvis du ser på høyre side av diagrammet,

740
00:44:31,110 --> 00:44:34,040
etter den tid har du en klasse med 58 elever i den,

741
00:44:34,040 --> 00:44:39,270
sannsynligheten for 2 personer har en bursdag er super, super høy, nesten 100%.

742
00:44:39,270 --> 00:44:41,880
Nå, det er liksom en morsom fakta om det virkelige liv.

743
00:44:41,880 --> 00:44:45,850
>> Men konsekvensene nå, for datastrukturer og lagring av informasjon

744
00:44:45,850 --> 00:44:51,100
betyr at bare forutsatt at du har en fin, ren, jevn fordeling av data

745
00:44:51,100 --> 00:44:53,650
og du har en stor nok utvalg til å passe en haug av ting

746
00:44:53,650 --> 00:44:59,360
betyr ikke at du kommer til å få folk i unike omgivelser.

747
00:44:59,360 --> 00:45:03,810
Du kommer til å ha kollisjoner. Så denne oppfatningen av hashing, som det kalles,

748
00:45:03,810 --> 00:45:07,450
tar en inngang som "Alice" og masserer den på noen måte

749
00:45:07,450 --> 00:45:10,190
og deretter komme tilbake et svar som 0 eller 1 eller 2.

750
00:45:10,190 --> 00:45:17,500
Komme tilbake noen utgang fra den funksjonen er plaget av dette sannsynligheten for kollisjon.

751
00:45:17,500 --> 00:45:19,530
Så hvordan kan vi håndtere disse kollisjoner?

752
00:45:19,530 --> 00:45:21,940
Vel, på den ene tilfelle, kan vi ta ideen som ble foreslått.

753
00:45:21,940 --> 00:45:25,100
Vi kan bare skifte alle ned, eller kanskje, litt mer enkelt,

754
00:45:25,100 --> 00:45:29,870
stedet for å flytte alle andre, la oss bare flytte Anita til bunnen av den tilgjengelige plass.

755
00:45:29,870 --> 00:45:32,810
Så hvis Alice er i 0, er Bob i 1, er Charlie i 2,

756
00:45:32,810 --> 00:45:35,260
Vi vil bare sette Anita på stedet tre.

757
00:45:35,260 --> 00:45:38,860
Og dette er en teknikk datastrukturer kalt lineær sondering.

758
00:45:38,860 --> 00:45:41,310
Lineær fordi du bare vandre denne linjen, og du er liksom sondering

759
00:45:41,310 --> 00:45:43,640
for ledige plasser i datastrukturen.

760
00:45:43,640 --> 00:45:46,210
Selvsagt, tilfaller dette inn O (n).

761
00:45:46,210 --> 00:45:49,590
Hvis datastrukturen er virkelig full, det er 25 personer i det allerede,

762
00:45:49,590 --> 00:45:54,120
og deretter Anita kommer sammen, ender hun opp på hva som ville være plassering Z, og det er fint.

763
00:45:54,120 --> 00:45:56,540
Hun passer fremdeles, og vi kan finne henne senere.

764
00:45:56,540 --> 00:46:00,100
>> Men dette var i strid med målet om å påskynde ting opp.

765
00:46:00,100 --> 00:46:02,530
Så hva om vi i stedet introduserte denne tredje dimensjonen?

766
00:46:02,530 --> 00:46:06,400
At teknikken er vanligvis kalles separat kjeding, eller å ha kjettinger.

767
00:46:06,400 --> 00:46:10,030
Og hva en hash table er nå, dette tabellform struktur,

768
00:46:10,030 --> 00:46:13,450
tabellen er bare et utvalg av pekere.

769
00:46:13,450 --> 00:46:18,230
Men hva disse pekere peker på er gjette hva?

770
00:46:18,230 --> 00:46:21,970
En lenket liste. Så hva om vi tar det beste fra begge disse verdenene?

771
00:46:21,970 --> 00:46:26,500
Vi bruker arrays for de første indekser

772
00:46:26,500 --> 00:46:32,070
inn i datastrukturen slik at vi umiddelbart kan gå til [0] [1], [30] eller så videre,

773
00:46:32,070 --> 00:46:36,480
men slik at vi har en viss fleksibilitet, og vi kan passe Anita og Alice og Adam

774
00:46:36,480 --> 00:46:38,630
og en annen A navn,

775
00:46:38,630 --> 00:46:43,470
vi i stedet la den andre aksen vokse vilkårlig.

776
00:46:43,470 --> 00:46:47,340
Og vi endelig, som av mandag, har det uttrykksfulle evne med lenket liste.

777
00:46:47,340 --> 00:46:49,530
Vi kan vokse en datastruktur vilkårlig.

778
00:46:49,530 --> 00:46:52,450
Alternativt kan vi bare gjøre en stor 2-dimensjonal array,

779
00:46:52,450 --> 00:46:57,190
men det kommer til å bli en forferdelig situasjon hvis en av radene i en 2-dimensjonal array

780
00:46:57,190 --> 00:47:01,280
er ikke stor nok for ekstra person hvis navn skjer til å begynne med A.

781
00:47:01,280 --> 00:47:04,200
Gud forby vi må omfordele en stor 2-dimensjonal struktur

782
00:47:04,200 --> 00:47:06,600
bare fordi det er så mange som heter A,

783
00:47:06,600 --> 00:47:09,480
spesielt når det er så få som heter Z noe.

784
00:47:09,480 --> 00:47:12,170
Det er bare kommer til å bli en svært sparsommelig datastruktur.

785
00:47:12,170 --> 00:47:15,400
Så det er ikke perfekt på noen måte, men nå har vi i det minste har muligheten

786
00:47:15,400 --> 00:47:19,090
å kjapt finne ut hvor Alice eller Anita tilhører,

787
00:47:19,090 --> 00:47:21,090
minst i form av den vertikale aksen,

788
00:47:21,090 --> 00:47:25,850
og da må vi bare bestemme hvor du skal plassere Anita eller Alice i dette lenket liste.

789
00:47:25,850 --> 00:47:32,480
Hvis vi ikke bryr seg om sortering ting, hvordan kunne fort vi setter Alice inn i en struktur som dette?

790
00:47:32,480 --> 00:47:35,370
Det er konstant tid. Vi indeksen i [0], og hvis ingen er der,

791
00:47:35,370 --> 00:47:37,550
Alice går på starten av det lenket liste.

792
00:47:37,550 --> 00:47:40,000
Men det er ikke en stor avtale. Fordi hvis Anita kommer deretter langs

793
00:47:40,000 --> 00:47:42,160
noen flere trinn senere, ikke hvor Anita hører?

794
00:47:42,160 --> 00:47:45,140
Vel, [0]. OOP. Alice er allerede i det lenket liste.

795
00:47:45,140 --> 00:47:47,760
>> Men hvis vi ikke bryr seg om sortering disse navnene,

796
00:47:47,760 --> 00:47:53,580
Vi kan bare flytte Alice over, insert Anita, men selv det er konstant tid.

797
00:47:53,580 --> 00:47:57,010
Selv om det er Alice og Adam og alle disse andre A navnene,

798
00:47:57,010 --> 00:47:59,410
det er egentlig ikke skiftende dem fysisk. Hvorfor?

799
00:47:59,410 --> 00:48:04,090
Fordi vi bare gjorde her med lenket liste, hvem vet ble disse nodene er likevel?

800
00:48:04,090 --> 00:48:06,550
Alt du trenger å gjøre er å flytte brødsmuler.

801
00:48:06,550 --> 00:48:10,930
Flytt pilene rundt, du trenger ikke å fysisk flytte data rundt.

802
00:48:10,930 --> 00:48:14,610
Så vi kan sette Anita, i så fall, umiddelbart. Konstant tid.

803
00:48:14,610 --> 00:48:20,250
Så vi har konstant tid oppslag, og konstant gangs installasjon av noen som Anita.

804
00:48:20,250 --> 00:48:22,740
Men slags oversimplifying verden.

805
00:48:22,740 --> 00:48:28,510
Hva om vi senere vil finne Alice?

806
00:48:28,510 --> 00:48:31,050
Hva om vi senere vil finne Alice?

807
00:48:31,050 --> 00:48:35,690
Hvor mange skritt kommer det til å ta?

808
00:48:35,690 --> 00:48:37,850
[Student svar, uforståelig]

809
00:48:37,850 --> 00:48:40,950
Akkurat. Antall personer før Alice i lenket liste.

810
00:48:40,950 --> 00:48:45,420
Så det er ikke helt perfekt, fordi vår datastruktur, igjen, har denne vertikale tilgang

811
00:48:45,420 --> 00:48:50,240
og da må disse koplede listene hengende - faktisk, la oss ikke trekke det en en matrise.

812
00:48:50,240 --> 00:48:56,020
Det har disse koblede lister hengende ut av det som ser litt noe sånt som dette.

813
00:48:56,020 --> 00:48:59,110
Men problemet er hvis Alice og Adam og alle disse andre A navnene

814
00:48:59,110 --> 00:49:01,720
ende opp mer og mer over det,

815
00:49:01,720 --> 00:49:04,810
finne noen kunne ende opp med å ta en haug med trinn,

816
00:49:04,810 --> 00:49:06,670
bcause du må traversere lenket liste,

817
00:49:06,670 --> 00:49:08,090
som er en lineær operasjon.

818
00:49:08,090 --> 00:49:14,270
Så egentlig, da er innsetting tid slutt O (n), der n er antallet av elementer i listen.

819
00:49:14,270 --> 00:49:21,780
Delt på, la oss vilkårlig kalle det m, der m er antall koplede listene

820
00:49:21,780 --> 00:49:24,500
som vi har i denne vertikale aksen.

821
00:49:24,500 --> 00:49:27,180
Med andre ord, hvis vi virkelig anta en jevn fordeling av navn,

822
00:49:27,180 --> 00:49:30,150
helt urealistisk. Det er åpenbart mer av noen bokstaver enn andre.

823
00:49:30,150 --> 00:49:32,580
>> Men hvis vi antar for øyeblikket en jevn fordeling,

824
00:49:32,580 --> 00:49:37,350
og vi har n totalt mennesker, og m. Totalt kjeder

825
00:49:37,350 --> 00:49:40,630
tilgjengelig for oss, deretter lengden av hver av disse kjedene

826
00:49:40,630 --> 00:49:44,380
ganske enkelt skal være den totale, n dividert med antall av kjeder.

827
00:49:44,380 --> 00:49:48,900
Så n / m. Men her er hvor vi kan være alt matematisk smart.

828
00:49:48,900 --> 00:49:53,030
m er en konstant, fordi det er et fast antall av disse.

829
00:49:53,030 --> 00:49:54,620
Du kommer til å erklære din matrise i begynnelsen,

830
00:49:54,620 --> 00:49:58,450
og vi er ikke resizing den vertikale aksen. Per definisjon, forblir det fast.

831
00:49:58,450 --> 00:50:01,220
Det er bare den horisontale aksen, så å si, som er i endring.

832
00:50:01,220 --> 00:50:04,760
Så teknisk sett er dette en konstant. Så nå, innsetting tid

833
00:50:04,760 --> 00:50:09,700
er ganske mye O (n).

834
00:50:09,700 --> 00:50:12,410
Så det ikke føles alt så mye bedre.

835
00:50:12,410 --> 00:50:14,940
Men hva er sannheten her? Vel, hele tiden, i flere uker,

836
00:50:14,940 --> 00:50:20,640
Vi har sagt O (n ²). O (n), 2 x n ², - n, delt på to. . . ech.

837
00:50:20,640 --> 00:50:23,580
Det er bare n ². Men nå, i denne delen av semesteret,

838
00:50:23,580 --> 00:50:25,560
Vi kan begynne å snakke om den virkelige verden igjen.

839
00:50:25,560 --> 00:50:31,520
Og n / m er absolutt raskere enn bare n alene.

840
00:50:31,520 --> 00:50:35,170
Hvis du har tusen navn, og du bryter dem opp i flere bøtter

841
00:50:35,170 --> 00:50:37,820
slik at du har bare ti navn i hver av disse kjedene,

842
00:50:37,820 --> 00:50:41,670
absolutt søke ti ting kommer til å være raskere enn tusen ting.

843
00:50:41,670 --> 00:50:43,740
Og så en av de kommende oppgavesett kommer til å utfordre deg

844
00:50:43,740 --> 00:50:46,100
å tenke på akkurat det, selv om, ja,

845
00:50:46,100 --> 00:50:49,520
asymptotisk og matematisk, er dette fortsatt bare lineær,

846
00:50:49,520 --> 00:50:51,700
som suger generelt når du prøver å finne ting.

847
00:50:51,700 --> 00:50:54,530
I virkeligheten, det kommer til å være raskere enn det

848
00:50:54,530 --> 00:50:56,520
på grunn av dette divisor.

849
00:50:56,520 --> 00:50:58,310
Og så det er igjen kommer til å være denne avveiingen

850
00:50:58,310 --> 00:51:01,390
og denne konflikten mellom teori og virkelighet,

851
00:51:01,390 --> 00:51:03,550
og en av knottene vil begynne å dreie på dette punktet i semesteret

852
00:51:03,550 --> 00:51:07,510
er mer av virkeligheten en som vi liksom forberede semster er slutt,

853
00:51:07,510 --> 00:51:09,280
som vi introdusere en verden av web-programmering,

854
00:51:09,280 --> 00:51:11,530
der virkelig, er ytelsen kommer til å telle fordi brukerne skal

855
00:51:11,530 --> 00:51:14,880
begynner å føle og setter dårlig design beslutninger.

856
00:51:14,880 --> 00:51:19,950
>> Så hvordan går du om å implementere en koblet - en hash tabell med 31 elementer?

857
00:51:19,950 --> 00:51:22,600
Og i forrige eksempel var vilkårlig om fødselsdager.

858
00:51:22,600 --> 00:51:26,190
Hvis noen har bursdag 1. januar eller 1. februar vil vi sette dem i denne bøtta.

859
00:51:26,190 --> 00:51:28,960
Hvis det er 2 januar, 2. februar, 2. mars vil vi sette dem i denne bøtta.

860
00:51:28,960 --> 00:51:32,220
Det er derfor det var 31. Hvordan erklærer du en hash table?

861
00:51:32,220 --> 00:51:37,480
Det kan være ganske enkel, node * mitt bord vilkårlig navn for det, [31].

862
00:51:37,480 --> 00:51:42,400
Dette gir meg 31 pekere til noder,

863
00:51:42,400 --> 00:51:45,370
og som tillater meg å ha 31 pekere til lenkede lister

864
00:51:45,370 --> 00:51:48,800
selv om disse kjedene er i utgangspunktet NULL.

865
00:51:48,800 --> 00:51:54,860
Hva ønsker jeg å sette hvis jeg ønsker å lagre "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Vel, vi trenger å pakke disse tingene i en struktur

867
00:51:57,010 --> 00:52:00,530
fordi vi trenger Alice til å peke til Bob, å peke på Charlie, og så videre.

868
00:52:00,530 --> 00:52:04,940
Vi kan ikke bare ha navnene alene, så jeg kunne lage en ny struktur kalt node her.

869
00:52:04,940 --> 00:52:08,310
>> Hva er en faktisk node? Hva er en node i denne nye lenket liste?

870
00:52:08,310 --> 00:52:11,840
Det første, kalt ord, er for personens navn.

871
00:52:11,840 --> 00:52:14,340
LENGDE, formodentlig, knyttet til den maksimale lengden av et menneskes navn,

872
00:52:14,340 --> 00:52:18,210
hva som er, 20, 30, 40 tegn i sprø hjørne tilfeller,

873
00:52:18,210 --> 00:52:22,680
og en er for hva? Det er bare den ekstra NULL karakter, \ 0.

874
00:52:22,680 --> 00:52:27,410
Så denne noden skal brytes "noe" inne i seg selv,

875
00:52:27,410 --> 00:52:29,640
men det erklærer også en peker kalt neste

876
00:52:29,640 --> 00:52:32,580
slik at vi kan kjede Alice til Bob til Charlie og så videre.

877
00:52:32,580 --> 00:52:36,700
Kan være NULL men ikke nødvendigvis trenger å være.

878
00:52:36,700 --> 00:52:40,110
Eventuelle spørsmål om disse hash tabeller? Ja?

879
00:52:40,110 --> 00:52:46,190
[Student spør spørsmål, uforståelig] En rekke - godt spørsmål.

880
00:52:46,190 --> 00:52:50,120
Hvorfor er dette røye ord i en matrise i stedet for bare char *?

881
00:52:50,120 --> 00:52:53,830
I dette noe vilkårlig eksempel, ønsker jeg ikke å måtte ty

882
00:52:53,830 --> 00:52:56,190
til malloc for hver av de opprinnelige navnene.

883
00:52:56,190 --> 00:52:59,530
Jeg ønsket å erklære en maksimal mengde minne for strengen

884
00:52:59,530 --> 00:53:06,020
slik at jeg kunne kopiere inn i strukturen Alice \ 0 og ikke trenger å forholde seg til malloc og gratis og lignende.

885
00:53:06,020 --> 00:53:11,710
Men jeg kunne gjøre det hvis jeg ønsket å være mer bevisst på plass bruk. Godt spørsmål.

886
00:53:11,710 --> 00:53:14,780
Så la oss prøve å generalisere bort fra dette

887
00:53:14,780 --> 00:53:18,350
og fokusere resten av dag på datastrukturer mer generelt

888
00:53:18,350 --> 00:53:21,170
og andre problemer som vi kan løse ved hjelp av de samme grunnleggende

889
00:53:21,170 --> 00:53:24,590
selv om datastrukturer selv kan avvike i sine enkeltheter.

890
00:53:24,590 --> 00:53:27,910
>> Så det viser seg i informatikk, trærne er svært vanlig.

891
00:53:27,910 --> 00:53:29,760
Og du kan tenke på et tre liksom som et slektstre,

892
00:53:29,760 --> 00:53:31,830
hvor det er noen røtter, noen matriark eller patriark,

893
00:53:31,830 --> 00:53:34,540
bestemor eller bestefar eller tidligere tilbake,

894
00:53:34,540 --> 00:53:38,880
under som er mamma og pappa eller ulike søsken eller lignende.

895
00:53:38,880 --> 00:53:42,500
Så en trestruktur har noder og den har barn,

896
00:53:42,500 --> 00:53:45,260
vanligvis 0 eller flere barn for hver node.

897
00:53:45,260 --> 00:53:47,320
Og noen av sjargong som du ser i dette bildet her

898
00:53:47,320 --> 00:53:50,630
er noen av de små barna eller barnebarna på kantene

899
00:53:50,630 --> 00:53:52,330
som ikke har noen piler som kommer fra dem,

900
00:53:52,330 --> 00:53:55,070
de er de såkalte blader, og noen på innsiden

901
00:53:55,070 --> 00:53:58,790
er en indre node, du kan kalle det noe langs disse linjene.

902
00:53:58,790 --> 00:54:01,430
Men denne strukturen er ganske vanlig. Dette er litt tilfeldig.

903
00:54:01,430 --> 00:54:04,930
Vi har ett barn på venstre side, har vi tre barn på høyre,

904
00:54:04,930 --> 00:54:06,830
to barn på nederst til venstre.

905
00:54:06,830 --> 00:54:10,740
Så kan vi ha forskjellige størrelser trær, men hvis vi begynner å standardisere ting,

906
00:54:10,740 --> 00:54:15,330
og du husker kanskje dette fra Patricks video på binære søk fra en tidligere kort

907
00:54:15,330 --> 00:54:19,490
nettet, binært søk, har ikke skal gjennomføres med en matrise

908
00:54:19,490 --> 00:54:21,410
eller biter av papir på en tavle.

909
00:54:21,410 --> 00:54:25,490
Anta at du ønsket å lagre numrene i en mer sofistikert datastruktur.

910
00:54:25,490 --> 00:54:27,680
Du kan lage et tre som dette.

911
00:54:27,680 --> 00:54:35,290
Du kan ha en node erklært i C, og at noden kan ha minst to elementer på innsiden av det.

912
00:54:35,290 --> 00:54:39,470
Den ene er nummeret du vil lagre, og den andre er - vel, vi trenger en til.

913
00:54:39,470 --> 00:54:41,540
Den andre er sine barn.

914
00:54:41,540 --> 00:54:45,150
Så her er et annet datastruktur. Denne gangen er en node definert som lagrer et nummer n

915
00:54:45,150 --> 00:54:49,060
og deretter to pekere, venstre barn og høyre barn.

916
00:54:49,060 --> 00:54:52,100
Og de er ikke tilfeldig. Hva er interessant om dette treet?

917
00:54:52,100 --> 00:55:00,550
>> Hva er mønsteret i hvordan vi har lagt dette ut eller hvordan Patrick lagt den ut i videoen hans?

918
00:55:00,550 --> 00:55:02,790
Det er slags åpenbart at det er noen sortering skjer her,

919
00:55:02,790 --> 00:55:04,460
men hva er den enkle regelen? Ja?

920
00:55:04,460 --> 00:55:08,350
[Student svar, uforståelig]

921
00:55:08,350 --> 00:55:12,040
Perfekt. Hvis du blikk på dette, ser du de små tallene på venstre side,

922
00:55:12,040 --> 00:55:14,690
store tall på venstre side, men det er sant for hver node.

923
00:55:14,690 --> 00:55:20,370
For hver node, dens venstre barn mindre enn den, og dens høyre barnet større enn den.

924
00:55:20,370 --> 00:55:25,210
Hva dette betyr nå er om jeg vil søke denne datastruktur for, si, nummer 44,

925
00:55:25,210 --> 00:55:29,320
Jeg må starte på roten, fordi som med alle disse mer komplekse datastrukturer nå,

926
00:55:29,320 --> 00:55:31,910
vi har bare en peker til én ting, begynnelsen.

927
00:55:31,910 --> 00:55:35,010
Og i dette tilfellet, er begynnelsen roten. Det er ikke den venstre siden,

928
00:55:35,010 --> 00:55:39,530
det er roten av denne strukturen. Så jeg ser her er 55, og jeg leter etter 44.

929
00:55:39,530 --> 00:55:41,430
Hvilken retning jeg ønsker å gå?

930
00:55:41,430 --> 00:55:45,680
Vel, jeg ønsker å gå til venstre, fordi åpenbart er til høyre kommer til å være for stor.

931
00:55:45,680 --> 00:55:49,050
Så merker her, du liksom konseptuelt chopping treet i halvparten

932
00:55:49,050 --> 00:55:51,700
fordi du aldri kommer ned til høyre side.

933
00:55:51,700 --> 00:55:55,410
Så nå går jeg fra 55 til 33. Det er for lite av et nummer.

934
00:55:55,410 --> 00:56:01,590
Jeg leter etter 44, men nå vet jeg om 44 er i dette treet, kan jeg gå selvsagt til høyre.

935
00:56:01,590 --> 00:56:04,460
Så igjen, jeg beskjæring av treet i halvparten.

936
00:56:04,460 --> 00:56:06,780
Det er ganske mye identisk konseptuelt til telefonboken.

937
00:56:06,780 --> 00:56:09,510
Det er identisk med hva vi gjorde med papirene på tavla,

938
00:56:09,510 --> 00:56:13,940
men det er en mer sofistikert struktur som tillater oss å faktisk gjøre

939
00:56:13,940 --> 00:56:16,880
dette splitt og hersk ved utformingen av algoritmen,

940
00:56:16,880 --> 00:56:19,420
og faktisk, traversering en struktur som dette - whoops.

941
00:56:19,420 --> 00:56:22,870
Traversing en struktur som dette, hvor det er bare "gå på denne måten, eller gå den veien,"

942
00:56:22,870 --> 00:56:26,870
betyr all denne koden som bøyd hodet først når implementere den i seksjon

943
00:56:26,870 --> 00:56:31,270
eller vandre gjennom det hjemme, for binære søk med rekursjon eller iterasjon,

944
00:56:31,270 --> 00:56:35,060
det er en smerte i nakken. Finn midten element, så gjør din avrunding opp eller ned.

945
00:56:35,060 --> 00:56:39,230
>> Det er en skjønnhet til dette fordi vi nå kan bruke rekursjon igjen,

946
00:56:39,230 --> 00:56:43,760
men mye mer renslig. Faktisk, hvis du er på nummer 55, og du vil finne 44,

947
00:56:43,760 --> 00:56:48,450
du går igjen i dette tilfellet, så hva gjør du? Du kjører nøyaktig samme algoritme.

948
00:56:48,450 --> 00:56:51,560
Du sjekker verdien av node, så du går til venstre eller høyre.

949
00:56:51,560 --> 00:56:53,670
Så du sjekke verdien av noden, gå til venstre eller høyre.

950
00:56:53,670 --> 00:56:56,710
Dette er perfekt egnet til rekursjon.

951
00:56:56,710 --> 00:57:00,920
Så selv om det i det siste har vi gjort noen ganske vilkårlige eksempler som involverer rekursjon

952
00:57:00,920 --> 00:57:03,430
som ikke trenger å være rekursiv, med data stuctures,

953
00:57:03,430 --> 00:57:07,820
spesielt trær, er det et perfekt anvendelse av denne ideen om å ta et problem,

954
00:57:07,820 --> 00:57:12,920
krymper den og deretter å løse det samme type, men mindre, program.

955
00:57:12,920 --> 00:57:14,590
>> Så det er en annen datastruktur som vi kan presentere.

956
00:57:14,590 --> 00:57:18,760
Dette er laget ved første øyekast å se kryptisk, men dette er utrolig.

957
00:57:18,760 --> 00:57:25,090
Så dette er en datastruktur som kalles en trie, trie, som er arvet fra ordet henting,

958
00:57:25,090 --> 00:57:30,210
som ikke uttales re-prøve-val, men det er det verden kaller disse tingene. Prøver. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Det er en trestruktur av noe slag, men hver av nodene i en Trie

960
00:57:35,190 --> 00:57:41,280
synes å være hva? Og dette er litt misvisende fordi det er slags forkortet.

961
00:57:41,280 --> 00:57:45,960
Men det ser ut som hver node i denne trie er faktisk en matrise.

962
00:57:45,960 --> 00:57:48,840
Og selv om forfatteren av dette diagrammet ikke har vist det,

963
00:57:48,840 --> 00:57:54,130
i dette tilfellet, er dette trie en datastruktur som har som formål i livet er å lagre 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
Og på hvilken måte dette data butikker Alice og Bob og Charlie og Anita og så videre

966
00:58:02,480 --> 00:58:06,970
er det bruker en rekke derved å lagre Alice i en trie,

967
00:58:06,970 --> 00:58:09,820
Vi starter på rotnoden som ser ut som en matrise,

968
00:58:09,820 --> 00:58:12,080
og det er blitt skrevet i stenografi notasjon.

969
00:58:12,080 --> 00:58:15,070
Forfatteren utelatt abcdefg fordi det var ingen navn med det.

970
00:58:15,070 --> 00:58:19,150
De bare viste M og P og T, men i dette tilfellet,

971
00:58:19,150 --> 00:58:22,780
la oss gå bort fra Alice og Bob og Charlie til noen navn som er her.

972
00:58:22,780 --> 00:58:25,670
Maxwell er faktisk i dette diagrammet.

973
00:58:25,670 --> 00:58:29,570
Så hvordan gjorde forfatteren butikken M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Han eller hun startet på rotnoden, og gikk til [M], så om lag 13, den 13. beliggenhet i matrisen.

975
00:58:36,990 --> 00:58:40,750
Så derfra, det er en peker.

976
00:58:40,750 --> 00:58:42,760
En peker fører til en annen tabell.

977
00:58:42,760 --> 00:58:47,880
Derfra forfatteren indeksert i denne matrisen på stedet A, som avbildet det øverst til venstre,

978
00:58:47,880 --> 00:58:52,250
og da han eller hun fulgte den peker til en annen matrise,

979
00:58:52,250 --> 00:58:55,460
og gikk til pekeren på stedet X.

980
00:58:55,460 --> 00:58:59,840
Deretter i neste matrise plassering W, E, L, L, og så videre,

981
00:58:59,840 --> 00:59:03,090
og til slutt, la oss faktisk prøver å sette et bilde på dette.

982
00:59:03,090 --> 00:59:05,380
Hva gjør en node se ut i koden?

983
00:59:05,380 --> 00:59:11,820
En node i en trie inneholder en rekke pekere til flere noder.

984
00:59:11,820 --> 00:59:16,090
Men det er også nødt til å være en slags boolsk verdi, i hvert fall i denne implementeringen.

985
00:59:16,090 --> 00:59:18,770
Jeg måtte kalle det is_word. Hvorfor?

986
00:59:18,770 --> 00:59:22,670
Fordi når du setter inn Maxwell, du er ikke sette

987
00:59:22,670 --> 00:59:25,300
noe i denne datastruktur.

988
00:59:25,300 --> 00:59:27,480
Du ikke å skrive M. Du skriver ikke X.

989
00:59:27,480 --> 00:59:30,240
Alt du gjør er å følge pekere.

990
00:59:30,240 --> 00:59:33,360
Pekeren som representerer M, deretter pekeren som representerer A,

991
00:59:33,360 --> 00:59:36,310
deretter pekeren som representerer X, og W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
men hva du trenger å gjøre på slutten er liksom går, sjekk, nådde jeg denne plasseringen.

993
00:59:41,950 --> 00:59:45,560
Det var et ord som ender her i datastrukturen.

994
00:59:45,560 --> 00:59:48,190
>> Så hva en trie er virkelig fylt med og forfatteren valgte å representere

995
00:59:48,190 --> 00:59:51,880
disse terminuses med små trekanter.

996
00:59:51,880 --> 00:59:56,470
Dette betyr bare at det faktum denne trekanten er her, denne boolske verdien av ekte

997
00:59:56,470 --> 00:59:59,200
betyr at hvis du går bakover i treet,

998
00:59:59,200 --> 01:00:02,420
det betyr et ord som heter Maxwell er i denne.

999
01:00:02,420 --> 01:00:04,870
Men ordet foo, for eksempel,

1000
01:00:04,870 --> 01:00:07,970
er ikke i treet, fordi hvis jeg starter på rotnoden opp her på toppen,

1001
01:00:07,970 --> 01:00:14,030
Det er ingen f pekeren, ingen o pekeren, ingen o pekeren. Foo er ikke et navn i denne ordboken.

1002
01:00:14,030 --> 01:00:22,460
Men derimot, Turing, t-u-r-i-n-g. Igjen, det gjorde jeg ikke lagre t eller u eller r eller jeg eller n eller g.

1003
01:00:22,460 --> 01:00:29,820
Men jeg gjorde butikk i denne datastruktur en verdi av sann vei ned her i denne noden - i treet

1004
01:00:29,820 --> 01:00:33,030
ved å sette denne boolean verdi is_word til sann.

1005
01:00:33,030 --> 01:00:35,740
Så en trie er snill av denne svært interessant meta struktur,

1006
01:00:35,740 --> 01:00:39,810
der du egentlig ikke lagring av ordene seg for denne slags ordbok.

1007
01:00:39,810 --> 01:00:45,100
For å være klar, du bare lagrer ja eller nei, det er et ord som slutter her.

1008
01:00:45,100 --> 01:00:46,430
>> Nå hva er konsekvensen?

1009
01:00:46,430 --> 01:00:51,120
Hvis du har 150 000 ord i en ordbok som du prøver å lagre i minnet

1010
01:00:51,120 --> 01:00:53,400
bruke noe sånt som en lenket liste,

1011
01:00:53,400 --> 01:00:56,870
du kommer til å ha 150 000 noder i din lenket liste.

1012
01:00:56,870 --> 01:01:00,250
Og finne en av disse ordene alfabetisk kunne ta O (n) tid.

1013
01:01:00,250 --> 01:01:04,370
Lineær tid. Men i tilfelle her av en trie,

1014
01:01:04,370 --> 01:01:09,210
hva er kjøretiden til å finne et ord?

1015
01:01:09,210 --> 01:01:17,390
Det viser seg skjønnheten her er at selv om du har 149 999 ord allerede i denne ordboken,

1016
01:01:17,390 --> 01:01:20,170
som gjennomføres med dette datastruktur,

1017
01:01:20,170 --> 01:01:25,560
hvor mye tid tar det å finne eller sette en person inn på det, som Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Vel, det er bare 5, kanskje 6 trinnene for etterfølgende tegn.

1019
01:01:30,640 --> 01:01:32,880
Fordi tilstedeværelse av andre navn i strukturen

1020
01:01:32,880 --> 01:01:35,340
ikke kommer i veien for å sette inn Alice.

1021
01:01:35,340 --> 01:01:39,640
Videre finner Alice når det er 150 000 ord i denne ordboken

1022
01:01:39,640 --> 01:01:41,960
ikke kommer i veien for å finne Alice i det hele tatt,

1023
01:01:41,960 --> 01:01:46,880
fordi Alice er. . . . . her, fordi jeg fant en boolsk verdi.

1024
01:01:46,880 --> 01:01:50,920
Og hvis det ikke er boolean sant, så Alice er ikke i denne datastrukturen ord.

1025
01:01:50,920 --> 01:01:56,220
Med andre ord, kjøretiden til å finne ting og sette ting inn i denne nye

1026
01:01:56,220 --> 01:02:01,920
datastruktur av trie er O av - det er ikke n.

1027
01:02:01,920 --> 01:02:05,730
Fordi tilstedeværelse av 150.000 mennesker har ingen effekt på Alice, det virker.

1028
01:02:05,730 --> 01:02:11,560
Så la oss kalle det k, hvor k er den maksimale lengden av et ord på engelsk

1029
01:02:11,560 --> 01:02:14,050
som er typisk ikke mer enn 20-noe tegn.

1030
01:02:14,050 --> 01:02:17,940
Så k er en konstant. Så den hellige gral vi synes å ha funnet nå

1031
01:02:17,940 --> 01:02:26,000
er at av en trie, konstant tid for innstikk, for oppslag, for sletting.

1032
01:02:26,000 --> 01:02:29,170
Fordi antallet av tingene allerede i strukturen,

1033
01:02:29,170 --> 01:02:32,600
som ikke selv fysisk der. Igjen, de bare liksom krysset av, ja eller nei,

1034
01:02:32,600 --> 01:02:35,050
har ingen innvirkning på fremtidig driftstid.

1035
01:02:35,050 --> 01:02:37,940
>> Men det må jo være en fange, ellers ville vi ikke ha kastet bort så mye tid

1036
01:02:37,940 --> 01:02:41,460
på alle disse andre datastrukturer bare for å endelig komme til det hemmelige som er utrolig.

1037
01:02:41,460 --> 01:02:46,410
Så hva prisen vi betaler for å oppnå dette storhet her? Plass.

1038
01:02:46,410 --> 01:02:49,010
Denne saken er massiv. Og grunnen til at forfatteren

1039
01:02:49,010 --> 01:02:52,400
ikke presentere det her, legge merke til at alle disse tingene som ser ut som matriser,

1040
01:02:52,400 --> 01:02:55,400
han ikke trekke resten av treet, resten av trie,

1041
01:02:55,400 --> 01:02:58,060
fordi de er bare ikke relevant for historien.

1042
01:02:58,060 --> 01:03:01,870
Men alle disse nodene er super brede, og hver node i treet opptar

1043
01:03:01,870 --> 01:03:07,780
26 eller faktisk, kan være 27 tegn fordi i dette tilfellet ble jeg inkludert plass for apostrof

1044
01:03:07,780 --> 01:03:09,980
slik at vi kunne ha apostrophized ord.

1045
01:03:09,980 --> 01:03:14,450
I dette tilfellet er disse brede matriser. Så selv om de ikke er picutured,

1046
01:03:14,450 --> 01:03:18,190
dette tar opp en enorm mengde RAM.

1047
01:03:18,190 --> 01:03:20,670
Som kan være fine, especilly i moderne maskinvare,

1048
01:03:20,670 --> 01:03:25,650
men det er tradeoff. Vi får mindre tid ved å bruke mer plass.

1049
01:03:25,650 --> 01:03:28,580
Så hvor er dette alt kommer?

1050
01:03:28,580 --> 01:03:32,640
Vel, la oss gjøre - la oss se her.

1051
01:03:32,640 --> 01:03:39,510
La oss gjøre et hopp til denne fyren her.

1052
01:03:39,510 --> 01:03:43,450
>> Tro det eller ei, så mye gøy som C har vært i noen tid nå,

1053
01:03:43,450 --> 01:03:48,130
vi nådd det punktet i semesteret der det er på tide å gå over til ting mer moderne.

1054
01:03:48,130 --> 01:03:50,950
Ting på et høyere nivå. Og selv om de neste par ukene

1055
01:03:50,950 --> 01:03:54,580
vi vil likevel fortsette å fordype oss i en verden av pekere og minnehåndtering

1056
01:03:54,580 --> 01:03:57,210
å få den trøst som vi kan deretter bygge på,

1057
01:03:57,210 --> 01:04:01,270
slutten spillet er slutt å innføre, ironisk nok, ikke dette språket.

1058
01:04:01,270 --> 01:04:03,330
Vi vil bruke, som 10 minutter å snakke om HTML.

1059
01:04:03,330 --> 01:04:05,950
All HTML er er et kodespråk, og hva en kodespråk er

1060
01:04:05,950 --> 01:04:10,220
er disse seriene av åpne braketter og lukkede braketter som sier "gjøre denne dristige '

1061
01:04:10,220 --> 01:04:12,000
Gjør denne kursiv '' gjør dette sentrert.

1062
01:04:12,000 --> 01:04:14,250
Det er ikke alle som intellektuelt interessant, men det er super nyttig.

1063
01:04:14,250 --> 01:04:16,650
Og det er absolutt allestedsnærværende i disse dager.

1064
01:04:16,650 --> 01:04:19,450
Men hva er kraftig om den verden av HTML, og webprogrammering mer generelt,

1065
01:04:19,450 --> 01:04:25,910
bygger dynamiske ting, skrive kode i språk som PHP eller Python eller Ruby eller Java eller C #.

1066
01:04:25,910 --> 01:04:30,360
Virkelig, uansett språk av valget er, og genererer HTML dynamisk.

1067
01:04:30,360 --> 01:04:32,960
Generere noe som kalles CSS dynamisk.

1068
01:04:32,960 --> 01:04:35,810
Gjennomgripende stilark, som også er om estetikk.

1069
01:04:35,810 --> 01:04:41,360
Og så selv om i dag, hvis jeg går til noen nettside som kjent Google.com,

1070
01:04:41,360 --> 01:04:46,100
og jeg går for å vise, utvikler, vis kilde, som kanskje du har gjort før,

1071
01:04:46,100 --> 01:04:49,800
men kommer til å vise kilde, ser dette ting sannsynligvis ganske kryptisk.

1072
01:04:49,800 --> 01:04:55,320
Men dette er den underliggende koden som implementerer Google.com.

1073
01:04:55,320 --> 01:04:57,940
På fronten. Og faktisk alt dette er luftig estetikk ting.

1074
01:04:57,940 --> 01:05:01,740
Dette er CSS opp her. Hvis jeg holder rulle ned vi får noen fargekodet ting.

1075
01:05:01,740 --> 01:05:06,890
Dette er HTML. Googles kode ser ut som et rot, men hvis jeg faktisk åpne opp et annet vindu,

1076
01:05:06,890 --> 01:05:09,380
Vi kan se noen struktur til dette.

1077
01:05:09,380 --> 01:05:12,640
Hvis jeg åpner dette opp, legge merke til her, er det litt lettere å lese.

1078
01:05:12,640 --> 01:05:16,850
Vi kommer til å se før lenge denne koden, [ord] er en kode,

1079
01:05:16,850 --> 01:05:23,520
HTML, hode, kropp, div, script, tekstområdet, span, sentrert, div.

1080
01:05:23,520 --> 01:05:26,770
Og dette er liksom også kryptisk utseende ved første øyekast,

1081
01:05:26,770 --> 01:05:30,890
men alt dette rotet følger visse mønstre, og repeterbare mønstre,

1082
01:05:30,890 --> 01:05:33,850
slik at når vi får det grunnleggende ned, vil du være i stand til å skrive kode som dette

1083
01:05:33,850 --> 01:05:37,550
og deretter manipulere kode som dette bruker enda et annet språk, kalt JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Og JavaScript er et språk som går inne i en nettleser

1085
01:05:40,440 --> 01:05:44,380
i dag at vi bruker på Harvard kurs, for selvfølgelig shopping verktøy som Google maps bruker

1086
01:05:44,380 --> 01:05:48,660
å gi deg en hel haug med dynamikk, gir Facebook deg å vise instant statusoppdateringer,

1087
01:05:48,660 --> 01:05:51,430
Twitter bruker det til å vise deg tweets umiddelbart.

1088
01:05:51,430 --> 01:05:53,820
Alt dette vil vi begynne å fordype oss i.

1089
01:05:53,820 --> 01:05:57,190
Men for å komme dit, må vi forstå litt noe om Internett.

1090
01:05:57,190 --> 01:06:01,130
Dette klippet her er bare ett minutt lang, og la oss anta for nå er dette faktisk

1091
01:06:01,130 --> 01:06:08,380
hvordan Internett fungerer som en teaser for hva som er i ferd med å komme. Jeg gir deg "Warriors of the Net".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow chorus musikk ♫]

1093
01:06:14,720 --> 01:06:20,450
[Mann fortelleren] Han kom med et budskap.

1094
01:06:20,450 --> 01:06:23,770
Med en protokoll all sin egen.

1095
01:06:23,770 --> 01:06:37,270
[♫ Raskere elektronisk musikk ♫]

1096
01:06:37,270 --> 01:06:41,330
Han kom til en verden av kule brannmurer, uncaring rutere,

1097
01:06:41,330 --> 01:06:45,690
og farer langt verre enn døden.

1098
01:06:45,690 --> 01:06:55,400
Han er rask. Han er sterk. Han er TCP / IP, og han fikk adressen din.

1099
01:06:55,400 --> 01:06:59,250
Warriors of the Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Neste uke, da. Internett. Webprogrammering. Dette er CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]