1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Week 6, Vervolg]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvard University]

3
00:00:04,160 --> 00:00:08,720
[Dit is CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Dit is CS50 en dit het einde van week 6.

5
00:00:12,970 --> 00:00:17,970
Dus CS50x, een van de eerste cursussen van Harvard die betrokken zijn bij de EDX-initiatief

6
00:00:17,970 --> 00:00:20,590
inderdaad debuteerde afgelopen maandag.

7
00:00:20,590 --> 00:00:23,460
Als u graag om een ​​glimp van wat anderen te krijgen op het internet

8
00:00:23,460 --> 00:00:27,180
volgen nu samen met, kunt u naar x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Dat leidt u naar de juiste plaats op edx.org,

10
00:00:30,350 --> 00:00:34,160
dat was waar deze en andere cursussen van MIT en Berkeley nu leven.

11
00:00:34,160 --> 00:00:38,140
Je moet aanmelden voor een account, je zult merken dat het materiaal grotendeels hetzelfde is

12
00:00:38,140 --> 00:00:42,170
als je hebt gehad dit semester, zij het een paar weken uitgesteld, als we alles klaar.

13
00:00:42,170 --> 00:00:46,930
Maar wat studenten in CS50x ziet nu een interface vrij als deze.

14
00:00:46,930 --> 00:00:50,040
Dit is bijvoorbeeld Zamyla leidt de walkthrough voor probleem set 0.

15
00:00:50,040 --> 00:00:54,230
Bij het aanmelden bij edx.org, een CS50x student ziet het soort dingen

16
00:00:54,230 --> 00:00:57,170
je zou verwachten te zien in een cursus: de lezing voor maandag,

17
00:00:57,170 --> 00:01:01,650
lezing voor woensdag, diverse borrels, het probleem sets, de walkthroughs, PDF's.

18
00:01:01,650 --> 00:01:04,459
Bovendien, als je hier ziet, machinevertalingen

19
00:01:04,459 --> 00:01:08,390
van het Engels transcripten in het Chinees, Japans, Spaans, Italiaans,

20
00:01:08,390 --> 00:01:12,810
en een hele hoop andere talen die zeker zal zijn onvolmaakt

21
00:01:12,810 --> 00:01:15,840
als rollen we ze uit programmatisch gebruik van iets genaamd een API,

22
00:01:15,840 --> 00:01:18,360
of application programming interface, van Google

23
00:01:18,360 --> 00:01:21,360
die ons in staat stelt om te zetten Engels naar deze andere talen.

24
00:01:21,360 --> 00:01:24,100
Maar dankzij de prachtige geest van zo'n honderd-plus vrijwilligers,

25
00:01:24,100 --> 00:01:26,940
willekeurige mensen op het internet die zo vriendelijk aangeboden hebben om mee te doen

26
00:01:26,940 --> 00:01:30,180
in dit project, zullen we geleidelijk aan het verbeteren van de kwaliteit van deze vertalingen

27
00:01:30,180 --> 00:01:35,790
door het hebben van mensen te corrigeren van de fouten die onze computers hebben gemaakt.

28
00:01:35,790 --> 00:01:42,330
>> Dus het blijkt dat we hadden een paar studenten opdagen op maandag dan we in eerste instantie verwacht.

29
00:01:42,330 --> 00:01:48,980
In feite, nu CS50x heeft 100.000 mensen langs thuis na.

30
00:01:48,980 --> 00:01:54,430
Dus beseffen dat je allemaal deel uit van deze eerste klasse van het maken van deze cursus in de informatica

31
00:01:54,430 --> 00:01:57,370
onderwijs meer in het algemeen, meer in het algemeen, toegankelijk.

32
00:01:57,370 --> 00:02:00,130
En de realiteit is nu, met een aantal van deze massale online cursussen,

33
00:02:00,130 --> 00:02:04,070
ze allemaal beginnen met deze zeer grote aantallen, zoals we lijken hier hebben gedaan.

34
00:02:04,070 --> 00:02:08,759
Maar het doel, uiteindelijk, voor CS50x is echt om zo veel mensen naar de finish als mogelijk.

35
00:02:08,759 --> 00:02:12,000
Door het ontwerp wordt CS50x zal worden aangeboden vanaf afgelopen maandag

36
00:02:12,000 --> 00:02:17,430
helemaal door 15 april 2013, zodat de mensen die de school verplichtingen elders,

37
00:02:17,430 --> 00:02:20,990
werk, gezin, andere conflicten en dergelijke, een beetje meer flexibiliteit

38
00:02:20,990 --> 00:02:23,640
waarmee te duiken in deze cursus, die, volstaat het om te zeggen,

39
00:02:23,640 --> 00:02:30,540
is vrij ambitieus gedaan als alleen in de loop van slechts drie maanden binnen een gebruikelijke semester.

40
00:02:30,540 --> 00:02:34,190
Maar deze studenten wordt de aanpak van hetzelfde probleem sets, het bekijken van dezelfde inhoud,

41
00:02:34,190 --> 00:02:36,350
toegang tot dezelfde shorts en dergelijke.

42
00:02:36,350 --> 00:02:38,990
Dus beseffen dat we allemaal echt in hetzelfde schuitje.

43
00:02:38,990 --> 00:02:42,360
En een van de einddoelen van CS50x is niet alleen om zo veel mensen

44
00:02:42,360 --> 00:02:45,720
naar de finish en geef ze dit pas ontdekte kennis van de informatica

45
00:02:45,720 --> 00:02:49,000
en de programmering, maar ook om ze te laten hebben dit gedeelde ervaring.

46
00:02:49,000 --> 00:02:52,010
Een van de definiërende kenmerken van 50 op de campus, hopen wij,

47
00:02:52,010 --> 00:02:56,260
is dit soort gemeenschappelijke ervaring, ten goede of ten kwade, soms,

48
00:02:56,260 --> 00:02:59,480
maar met deze mensen te schakelen naar links en naar rechts,

49
00:02:59,480 --> 00:03:01,830
en spreekuren en de Hackathon en de beurs.

50
00:03:01,830 --> 00:03:04,560
Het is een beetje moeilijker om dat te doen in persoon met mensen online,

51
00:03:04,560 --> 00:03:10,580
maar CS50x wordt afgesloten in april met de allereerste CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
die zal een online aanpassing van ons idee van de beurs worden

53
00:03:13,630 --> 00:03:18,250
waar deze duizenden studenten zullen allemaal worden uitgenodigd om een ​​1 in te dienen - tot 2-minuten durende video,

54
00:03:18,250 --> 00:03:22,480
ofwel een screencast van hun laatste project of video van hen zwaaien gedag

55
00:03:22,480 --> 00:03:24,490
en praten over hun project en demonstreren van het,

56
00:03:24,490 --> 00:03:27,610
net als uw voorgangers hier hebben gedaan op de campus in de reële,

57
00:03:27,610 --> 00:03:31,400
zodat tegen het einde semester, de hoop is om een ​​globale tentoonstelling

58
00:03:31,400 --> 00:03:37,080
van de CS50x studenten afstudeeropdrachten, net als dat wat wacht u in december hier op de campus.

59
00:03:37,080 --> 00:03:39,680
Dus meer op dat in de komende maanden.

60
00:03:39,680 --> 00:03:43,640
>> Met 100.000 studenten echter is een behoefte aan een paar CA.

61
00:03:43,640 --> 00:03:47,590
Gezien het feit dat jullie zijn het pad hier laaiend en het nemen van CS50

62
00:03:47,590 --> 00:03:51,630
enkele weken van tevoren release van dit materiaal aan de mensen op EDX,

63
00:03:51,630 --> 00:03:55,330
realiseren dat we graag zo veel van onze eigen studenten mogelijk te betrekken bij dit initiatief,

64
00:03:55,330 --> 00:03:58,720
zowel tijdens het semester als deze winter en komend voorjaar.

65
00:03:58,720 --> 00:04:01,620
Dus als je wilt om mee te doen in CS50x,

66
00:04:01,620 --> 00:04:07,450
vooral meedoen op CS50x Discuss, de EDX versie van CS50 te bespreken,

67
00:04:07,450 --> 00:04:10,140
die velen van jullie zijn met behulp van op de campus, de online bulletin board,

68
00:04:10,140 --> 00:04:13,040
doe hoofd naar die URL, laat het ons weten wie je bent,

69
00:04:13,040 --> 00:04:16,450
omdat we graag het opbouwen van een team van studenten en medewerkers en docenten zowel

70
00:04:16,450 --> 00:04:19,630
op de campus die gewoon mee te spelen en de helpende hand.

71
00:04:19,630 --> 00:04:21,720
En als ze zien een vraag die vertrouwd is voor hen,

72
00:04:21,720 --> 00:04:25,320
hoor je een student rapportage enkele bug ergens daar in sommige landen op het internet,

73
00:04:25,320 --> 00:04:27,450
en dat een belletje rinkelen, want je had ook hetzelfde probleem

74
00:04:27,450 --> 00:04:32,620
in uw d-hal enige tijd geleden, hopelijk dan kunt u klokkenspel in en deel uw eigen ervaring.

75
00:04:32,620 --> 00:04:37,300
Dus gelieve deelnemen als je zou willen.

76
00:04:37,300 --> 00:04:39,360
>> Wetenschap van de computer cursussen op Harvard hebben een beetje een traditie,

77
00:04:39,360 --> 00:04:44,730
CS50 onder hen, van het hebben van een aantal kleding, wat kleren, die je kunt trots dragen

78
00:04:44,730 --> 00:04:49,090
aan het einde semester, zeggende heel trots dat je klaar bent met CS50

79
00:04:49,090 --> 00:04:51,830
en nam CS50 en dergelijke, en we altijd proberen om studenten te betrekken

80
00:04:51,830 --> 00:04:54,540
in dit proces zoveel mogelijk waarbij verzoeken wij,

81
00:04:54,540 --> 00:04:56,900
rond deze tijd van het semester, studenten dienen ontwerpen

82
00:04:56,900 --> 00:04:59,330
met behulp van Photoshop, of wat dan ook instrument van keuze die je wilt gebruiken

83
00:04:59,330 --> 00:05:02,330
als je een ontwerper, te ontwerpen voor T-shirts en sweatshirts te dienen

84
00:05:02,330 --> 00:05:06,100
en parasols en weinig Bandanas voor honden die we nu hebben en dergelijke.

85
00:05:06,100 --> 00:05:09,370
En alles is dan - de winnaars elk jaar worden dan tentoongesteld

86
00:05:09,370 --> 00:05:12,700
op de cursus op de website van store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Alles wordt verkocht tegen kostprijs daar, maar de website loopt gewoon zelf

88
00:05:15,790 --> 00:05:18,330
en stelt mensen in staat de keuze van de kleuren en ontwerpen die ze willen.

89
00:05:18,330 --> 00:05:20,420
Dus ik dacht dat we slechts enkele van de ontwerpen van vorig jaar te delen

90
00:05:20,420 --> 00:05:25,130
die op de website naast dit ene hier, dat is een jaarlijkse traditie.

91
00:05:25,130 --> 00:05:29,410
"Every Day Ik Seg Faultn" was een van de inzendingen van vorig jaar,

92
00:05:29,410 --> 00:05:32,290
dat is nog steeds beschikbaar zijn voor alumni.

93
00:05:32,290 --> 00:05:35,820
We hadden deze, "CS50, opgericht 1989."

94
00:05:35,820 --> 00:05:39,010
Een van onze Bowdens, Rob, was erg populair vorig jaar.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" was geboren, werd dit ontwerp ingediend, behoren tot de top verkopers.

96
00:05:43,480 --> 00:05:49,040
Zoals deze hier. Veel mensen hadden "Bowden Fever" volgens de verkoop-logs.

97
00:05:49,040 --> 00:05:52,650
Realiseer je dat dat nu kan er uw ontwerp, op het internet.

98
00:05:52,650 --> 00:05:57,510
Meer informatie hierover in het volgende probleem stelt komen.

99
00:05:57,510 --> 00:06:00,330
>> Nog een hulpmiddel: je hebt gehad wat blootstelling en hopelijk nu

100
00:06:00,330 --> 00:06:02,350
wat hands-on ervaring met GDB,

101
00:06:02,350 --> 00:06:04,570
dat is, natuurlijk, een debugger en stelt u in staat te manipuleren

102
00:06:04,570 --> 00:06:09,500
uw programma op een vrij laag niveau, het doen van wat voor soort dingen?

103
00:06:09,500 --> 00:06:13,030
Wat doet GDB laten doen?

104
00:06:13,030 --> 00:06:15,030
Ja? Geef me iets. [Student antwoord, onverstaanbaar]

105
00:06:15,030 --> 00:06:18,120
Goed. Stap in functie, dus je hoeft niet alleen maar te rennen typen

106
00:06:18,120 --> 00:06:22,310
en hebben het programma blaas door zijn geheel af te drukken dingen naar standaarduitvoer.

107
00:06:22,310 --> 00:06:25,190
In plaats daarvan kunt u door het regel voor regel, te typen volgende

108
00:06:25,190 --> 00:06:30,300
om line te gaan voor regel voor regel of stap te duiken in een functie, meestal een die je hebt geschreven.

109
00:06:30,300 --> 00:06:35,240
Wat doet GDB laten doen? Ja? [Student antwoord, onverstaanbaar]

110
00:06:35,240 --> 00:06:38,100
Print variabelen. Dus als je wilt een beetje introspectie doen binnenkant van uw programma

111
00:06:38,100 --> 00:06:41,500
zonder hun toevlucht nemen tot het schrijven van printf verklaringen all over the place,

112
00:06:41,500 --> 00:06:44,600
je kunt gewoon een variabel of geven een variabele.

113
00:06:44,600 --> 00:06:46,710
Wat kunt u doen met een debugger als GDB?

114
00:06:46,710 --> 00:06:49,170
[Student antwoord, onverstaanbaar]

115
00:06:49,170 --> 00:06:52,080
Precies. U kunt breekpunten, je kunt break uitvoering zeggen

116
00:06:52,080 --> 00:06:54,020
op de belangrijkste functie of de foo-functie.

117
00:06:54,020 --> 00:06:56,800
Je kunt zeggen break uitvoering op lijn 123.

118
00:06:56,800 --> 00:06:58,950
En breekpunten zijn echt een krachtige techniek

119
00:06:58,950 --> 00:07:01,110
want als je een algemeen gevoel van waar uw probleem

120
00:07:01,110 --> 00:07:05,360
waarschijnlijk is, hoeft u geen tijd te verspillen doorlopen geheel van het programma.

121
00:07:05,360 --> 00:07:08,250
U kunt in wezen springen daar en dan beginnen met typen -

122
00:07:08,250 --> 00:07:10,970
het doorlopen van het met stap of naast of iets dergelijks.

123
00:07:10,970 --> 00:07:14,340
Maar de vangst met zoiets als GDB is dat het je helpt, het menselijke,

124
00:07:14,340 --> 00:07:16,940
vind uw problemen en vind uw bugs.

125
00:07:16,940 --> 00:07:19,470
Het hoeft niet per se vinden ze zo veel voor je.

126
00:07:19,470 --> 00:07:23,070
>> Dus introduceerden we de andere dag style50, dat is een korte command-line tool

127
00:07:23,070 --> 00:07:27,500
die probeert om je code te stileren een beetje schoner dan u, de mens, zou kunnen hebben gedaan.

128
00:07:27,500 --> 00:07:29,530
Maar dat is ook eigenlijk gewoon een esthetische ding.

129
00:07:29,530 --> 00:07:34,110
Maar het blijkt dat er die andere tool genaamd Valgrind dat is een beetje meer geheimzinnige te gebruiken.

130
00:07:34,110 --> 00:07:36,860
De output is gruwelijk cryptisch op het eerste gezicht.

131
00:07:36,860 --> 00:07:39,420
Maar het is heerlijk handig, zeker nu we aan de kant van de term

132
00:07:39,420 --> 00:07:43,080
waar je begint te malloc en dynamische geheugentoewijzing te gebruiken.

133
00:07:43,080 --> 00:07:45,420
Dingen kunnen snel gaan echt heel erg verkeerd.

134
00:07:45,420 --> 00:07:49,320
Want als je vergeet om je geheugen vrij te maken, of je dereference enkele NULL pointer,

135
00:07:49,320 --> 00:07:55,770
of je wat afval pointerdereferentie, wat is meestal het symptoom dat de resultaten?

136
00:07:55,770 --> 00:07:59,470
Seg fout. En u krijgt deze kern-bestand van een bepaald aantal kilobytes of megabytes

137
00:07:59,470 --> 00:08:02,990
dat geeft de stand van het geheugen van uw programma toen het neerstortte,

138
00:08:02,990 --> 00:08:05,730
maar het programma uiteindelijk seg fouten, segmentatie fout,

139
00:08:05,730 --> 00:08:08,450
wat betekent dat er iets ergs gebeurd is bijna altijd gerelateerd

140
00:08:08,450 --> 00:08:11,750
naar een geheugenkaart-gerelateerde fout die je ergens gemaakt.

141
00:08:11,750 --> 00:08:14,100
Dus Valgrind helpt u dit soort dingen.

142
00:08:14,100 --> 00:08:17,720
Het is een tool die je, net als GDB, nadat je hebt gecompileerd uw programma,

143
00:08:17,720 --> 00:08:20,330
maar in plaats van direct uit te voeren het programma, loopt u Valgrind

144
00:08:20,330 --> 00:08:23,960
en u door te geven aan het uw programma, net zoals u dat doet met GDB.

145
00:08:23,960 --> 00:08:26,220
Nu, het gebruik, de beste vorm van uitvoer te krijgen,

146
00:08:26,220 --> 00:08:30,410
is een beetje lang, dus daar boven in het scherm zie je Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" bijna universeel betekent verbose wanneer u gebruik maakt van programma's op een Linux-computer.

148
00:08:35,350 --> 00:08:38,770
Het betekent dus spugen meer gegevens dan je misschien standaard.

149
00:08:38,770 --> 00:08:45,510
"- Lek-check = vol." Dit wordt alleen maar zeggen check voor alle mogelijke geheugenlekken,

150
00:08:45,510 --> 00:08:49,430
fouten die ik zou hebben gemaakt. Ook dit is een veel voorkomende paradigma met Linux-programma's.

151
00:08:49,430 --> 00:08:52,710
Over het algemeen, als je een command line argument is dat een "switch",

152
00:08:52,710 --> 00:08:55,830
die verondersteld om het programma het gedrag te veranderen, en het is een enkele letter,

153
00:08:55,830 --> 00:09:00,310
het is-v, maar als dat is ingeschakeld, maar door het ontwerp van de programmeur,

154
00:09:00,310 --> 00:09:05,150
is een volledige woord of reeks woorden, de command line argument begint met -.

155
00:09:05,150 --> 00:09:08,190
Dit zijn slechts menselijke conventies, maar je zult steeds meer zien.

156
00:09:08,190 --> 00:09:12,410
En tenslotte "a.out" is de willekeurige naam van het programma in dit voorbeeld.

157
00:09:12,410 --> 00:09:14,640
En hier is een aantal representatieve output.

158
00:09:14,640 --> 00:09:22,890
>> Voordat we kijken naar wat dat zou kunnen betekenen, laat me over te gaan naar een fragment van de code hier.

159
00:09:22,890 --> 00:09:26,390
En laat mij dit uit te gaan van de weg, binnenkort,

160
00:09:26,390 --> 00:09:32,120
en laten we een kijkje nemen op memory.c, dat is deze korte voorbeeld.

161
00:09:32,120 --> 00:09:36,290
Dus in dit programma, laat me in te zoomen op de functies en vragen.

162
00:09:36,290 --> 00:09:39,430
We hebben de functie de belangrijkste die een functie aanroept, f,

163
00:09:39,430 --> 00:09:45,590
en wat is dan f overgaan tot, doen in een enigszins technisch Engels?

164
00:09:45,590 --> 00:09:49,760
Wat doet f gaan doen?

165
00:09:49,760 --> 00:09:53,680
Hoe zit het Ik zal beginnen met lijn 20, en de ster de locatie doet er niet toe,

166
00:09:53,680 --> 00:09:56,720
maar ik zal gewoon hier in overeenstemming zijn met de laatste lezing.

167
00:09:56,720 --> 00:09:59,910
Wat is lijn 20 voor ons doen? Aan de linkerkant. We breken het naar beneden verder.

168
00:09:59,910 --> 00:10:02,410
Int * x: wat betekent dat?

169
00:10:02,410 --> 00:10:04,940
Okay. Het is waarbij een pointer, en laten we nu nog meer technisch.

170
00:10:04,940 --> 00:10:10,230
Wat betekent het, heel concreet, met een pointer verklaren? Iemand anders?

171
00:10:10,230 --> 00:10:15,050
Ja? [Student antwoord, onverstaanbaar] Te ver.

172
00:10:15,050 --> 00:10:17,060
Dus je leest het rechterkant van het gelijkteken.

173
00:10:17,060 --> 00:10:20,290
Laten we focussen alleen op de linkerkant, net op int * x.

174
00:10:20,290 --> 00:10:24,700
Dit betekent "verklaren" een pointer, maar nu laten we duiken in dieper met die definitie.

175
00:10:24,700 --> 00:10:28,330
Wat betekent dat concreet, technisch bedoel je? Ja?

176
00:10:28,330 --> 00:10:31,940
[Student antwoord, onverstaanbaar]

177
00:10:31,940 --> 00:10:35,090
Okay. Het is klaar om een ​​adres op te slaan in het geheugen.

178
00:10:35,090 --> 00:10:40,680
Goed. En laten we verder nog een stap, het is declaratie van een variabele, x, dat is 32 bits.

179
00:10:40,680 --> 00:10:44,440
En ik weet dat het 32 ​​bits omdat -?

180
00:10:44,440 --> 00:10:47,390
Het is niet omdat het een int, want het is een pointer in dit geval.

181
00:10:47,390 --> 00:10:49,650
Toeval dat het een en het zelfde met een int,

182
00:10:49,650 --> 00:10:51,970
maar het feit dat er de ster er betekent dat het een pointer

183
00:10:51,970 --> 00:10:57,300
en in het apparaat, zoals bij veel computers, maar niet alle pointers zijn 32 bits.

184
00:10:57,300 --> 00:11:01,850
Op meer moderne hardware zoals de nieuwste Macs, de nieuwste pc's, misschien heb je 64-bits pointers,

185
00:11:01,850 --> 00:11:04,160
maar in het apparaat, deze dingen zijn 32 bits.

186
00:11:04,160 --> 00:11:08,380
Dus we zullen standaardiseren op dat. Meer concreet, het verhaal gaat als volgt:

187
00:11:08,380 --> 00:11:10,820
Wij "verklaren" een pointer, wat betekent dat?

188
00:11:10,820 --> 00:11:12,810
We bereiden om een ​​geheugenadres op te slaan.

189
00:11:12,810 --> 00:11:15,530
Wat betekent dat?

190
00:11:15,530 --> 00:11:19,810
Wij creëren een variabele genaamd x dat neemt 32 bits

191
00:11:19,810 --> 00:11:23,810
dat binnenkort slaat het adres van een integer.

192
00:11:23,810 --> 00:11:26,470
En dat is waarschijnlijk ongeveer net zo nauwkeurig als we kunnen krijgen.

193
00:11:26,470 --> 00:11:31,810
Het is fijn vooruit om de wereld te vereenvoudigen en gewoon zeggen dat verklaart een pointer genaamd x.

194
00:11:31,810 --> 00:11:35,380
Declareer een pointer, maar beseffen en begrijpen wat er eigenlijk aan de hand

195
00:11:35,380 --> 00:11:38,490
zelfs in slechts die paar tekens.

196
00:11:38,490 --> 00:11:42,040
>> Nu, dit is bijna een beetje makkelijker, ook al is het een langere uitdrukking.

197
00:11:42,040 --> 00:11:48,160
Dus wat dit doet, dat is nu gemarkeerd: "malloc (10 * sizeof (int));" Ja?

198
00:11:48,160 --> 00:11:52,350
[Student antwoord, onverstaanbaar]

199
00:11:52,350 --> 00:11:58,250
Goed. En ik zal daar nemen. Het is de toewijzing van een deel van het geheugen voor tien integers.

200
00:11:58,250 --> 00:12:02,190
En laten we nu duiken in iets dieper, het is de toewijzing van een deel van het geheugen voor tien integers.

201
00:12:02,190 --> 00:12:05,390
Wat is malloc vervolgens terug te keren?

202
00:12:05,390 --> 00:12:10,390
Het adres van dat stuk, of, meer concreet, het adres van de eerste byte van dat stuk.

203
00:12:10,390 --> 00:12:14,080
Hoe dan ben ik, de programmeur, om te weten waar dat stuk van het geheugen eindigt?

204
00:12:14,080 --> 00:12:18,340
Ik weet dat het aaneengesloten is. Malloc, per definitie, krijgt u een aaneengesloten stuk van het geheugen.

205
00:12:18,340 --> 00:12:21,240
Geen gaten in. U heeft toegang tot elke byte in dat stuk,

206
00:12:21,240 --> 00:12:26,760
rug aan rug aan rug, maar hoe weet ik waar het einde van dit stuk van het geheugen is?

207
00:12:26,760 --> 00:12:28,850
Wanneer u malloc? [Student antwoord, onverstaanbaar] Goed.

208
00:12:28,850 --> 00:12:30,670
Dat doe je niet. Je moet niet vergeten.

209
00:12:30,670 --> 00:12:35,960
Ik moet niet vergeten dat ik de waarde 10 gebruikt, en ik weet niet eens lijken dat hier hebben gedaan.

210
00:12:35,960 --> 00:12:41,000
Maar de verantwoordelijkheid ligt volledig op mij. Strlen, die we hebben enigszins afhankelijk voor strijkers,

211
00:12:41,000 --> 00:12:45,860
werkt alleen als gevolg van deze conventie van het hebben van \ 0

212
00:12:45,860 --> 00:12:48,840
of deze speciale nul karakter NUL aan het einde van de string.

213
00:12:48,840 --> 00:12:51,740
Dat geldt niet voor slechts willekeurige stukken van het geheugen.

214
00:12:51,740 --> 00:12:58,590
Het is aan jou. Dus lijn 20, dan wijst een stuk van het geheugen

215
00:12:58,590 --> 00:13:02,590
dat kan tien integers, en slaat het adres van de eerste byte

216
00:13:02,590 --> 00:13:05,610
van dat deel van het geheugen in de variabele met de naam x.

217
00:13:05,610 --> 00:13:11,140
Ergo, die een pointer. Dus lijn 21, helaas, was een vergissing.

218
00:13:11,140 --> 00:13:16,110
Maar eerst, wat is het nou? Het zegt winkel op locatie 10, geïndexeerd 0,

219
00:13:16,110 --> 00:13:19,480
van het stuk van het geheugen genoemd x de waarde 0.

220
00:13:19,480 --> 00:13:21,510
>> Dus merken een paar dingen gaande zijn.

221
00:13:21,510 --> 00:13:25,420
Hoewel x is een pointer, herinneren van een paar weken geleden

222
00:13:25,420 --> 00:13:29,440
dat u kunt nog steeds gebruik maken van de array-stijl vierkante haken notatie.

223
00:13:29,440 --> 00:13:36,180
Want dat is eigenlijk de korte kant notatie voor de meer cryptische ogende pointers.

224
00:13:36,180 --> 00:13:40,320
waar we zouden zoiets als dit doen: Neem het adres x, u 10 plekken over,

225
00:13:40,320 --> 00:13:44,550
dan is er naar welke adres opgeslagen op die locatie.

226
00:13:44,550 --> 00:13:48,090
Maar eerlijk gezegd, dit is gewoon afschuwelijk om te lezen en comfortabel met te krijgen.

227
00:13:48,090 --> 00:13:52,900
Dus de wereld maakt meestal gebruik van de vierkante haken, alleen maar omdat het zo veel meer mensvriendelijke om te lezen.

228
00:13:52,900 --> 00:13:55,140
Maar dat is wat er werkelijk aan de hand onder de motorkap;

229
00:13:55,140 --> 00:13:58,190
x is een adres, geen array, per se.

230
00:13:58,190 --> 00:14:02,410
Dus dit is het opslaan van 0 op locatie 10 in x.

231
00:14:02,410 --> 00:14:06,120
Waarom is dit slecht? Ja?

232
00:14:06,120 --> 00:14:17,370
[Student antwoord, onverstaanbaar] Precies.

233
00:14:17,370 --> 00:14:21,100
We hebben alleen toegewezen tien ints, maar we rekenen van 0 bij het programmeren in C,

234
00:14:21,100 --> 00:14:25,690
zodat je toegang hebt tot 0 1 2 3 4 5 6 7 8 9, maar niet 10.

235
00:14:25,690 --> 00:14:30,270
Dus of het programma gaat seg fout of is het niet.

236
00:14:30,270 --> 00:14:32,900
Maar we weten niet echt, dit is een soort van een niet-deterministische gedrag.

237
00:14:32,900 --> 00:14:35,600
Het hangt af van het feit of we geluk.

238
00:14:35,600 --> 00:14:40,650
Als blijkt dat het besturingssysteem vindt het niet erg als ik die extra byte,

239
00:14:40,650 --> 00:14:43,360
ook al is niet gegeven aan mij, kan mijn programma niet crashen.

240
00:14:43,360 --> 00:14:46,780
Het is rauw, het is buggy, maar je zou niet zien dat symptoom,

241
00:14:46,780 --> 00:14:48,960
of je zou kunnen zien het maar een keer in de zoveel tijd.

242
00:14:48,960 --> 00:14:51,230
Maar de realiteit is dat de bug is, in feite is er,.

243
00:14:51,230 --> 00:14:54,320
En het is echt problematisch als je een programma geschreven dat u wilt juist,

244
00:14:54,320 --> 00:14:58,840
dat u hebt verkocht het programma dat mensen gebruiken die elke keer in een tijdje crasht

245
00:14:58,840 --> 00:15:02,450
omdat, natuurlijk, dit is niet goed. In feite, als je een Android telefoon of een iPhone

246
00:15:02,450 --> 00:15:05,550
en je apps downloaden deze dagen, als je ooit een app gewoon stoppen,

247
00:15:05,550 --> 00:15:10,040
alle van een plotselinge het verdwijnt, dat is bijna altijd het gevolg van een aantal geheugen-gerelateerde kwestie,

248
00:15:10,040 --> 00:15:12,830
waarbij de programmeur screwed up en dereferentie een pointer

249
00:15:12,830 --> 00:15:18,670
dat hij of zij niet moeten doen, en het resultaat van iOS of Android is om gewoon helemaal te doden het programma

250
00:15:18,670 --> 00:15:23,080
in plaats van het risico onbepaald gedrag of een soort van beveiliging compromis.

251
00:15:23,080 --> 00:15:25,950
>> Er is een andere bug in dit programma naast deze.

252
00:15:25,950 --> 00:15:30,180
Wat heb ik verpest in dit programma?

253
00:15:30,180 --> 00:15:32,740
Ik heb niet geoefend wat ik heb gepredikt. Ja?

254
00:15:32,740 --> 00:15:34,760
[Student antwoord, onverstaanbaar] Goed.

255
00:15:34,760 --> 00:15:36,880
Ik heb niet bevrijd van het geheugen. Dus de vuistregel nu

256
00:15:36,880 --> 00:15:43,150
moet elke keer als u belt malloc, moet u gratis bellen wanneer u klaar bent met behulp van dat geheugen.

257
00:15:43,150 --> 00:15:45,610
Nu, zou wanneer ik wil dit geheugen vrij te maken?

258
00:15:45,610 --> 00:15:49,780
Waarschijnlijk, ervan uitgaande dat deze eerste regel juist was, zou ik hier willen doen.

259
00:15:49,780 --> 00:15:55,710
Omdat ik niet kon, bijvoorbeeld, doe het hier beneden. Waarom?

260
00:15:55,710 --> 00:15:57,860
Net buiten het toepassingsgebied. Dus ook al hebben we het over pointers,

261
00:15:57,860 --> 00:16:04,830
dit is een week 2 of 3 probleem, waarbij x is alleen in omvang binnenkant van de accolades waar het werd verklaard.

262
00:16:04,830 --> 00:16:11,000
Dus je kan zeker niet daar bevrijden. Mijn enige kans om het te bevrijden is ongeveer na regel 21.

263
00:16:11,000 --> 00:16:15,170
Dit is een vrij eenvoudig programma, het was vrij eenvoudig als je eenmaal soort gewikkeld je geest

264
00:16:15,170 --> 00:16:17,870
rond wat het programma doet, waar de fouten waren.

265
00:16:17,870 --> 00:16:20,500
En zelfs als je niet zag op het eerste, hopelijk is het een beetje voor de hand nu

266
00:16:20,500 --> 00:16:23,870
dat deze fouten zijn vrij eenvoudig op te lossen en snel gemaakt.

267
00:16:23,870 --> 00:16:28,720
Maar wanneer een programma is meer dan 12 lijnen lang, het is 50 regels lang, 100 regels lang,

268
00:16:28,720 --> 00:16:31,150
wandelen door de code regel voor regel, denken door het logisch,

269
00:16:31,150 --> 00:16:35,110
is mogelijk, maar niet bijzonder leuk om te doen, voortdurend op zoek naar bugs,

270
00:16:35,110 --> 00:16:38,340
en het is ook moeilijk te doen, en dat is waarom een ​​tool als Valgrind bestaat.

271
00:16:38,340 --> 00:16:40,900
Laat me ga je gang en doe je dit: laat me open mijn terminal venster,

272
00:16:40,900 --> 00:16:45,400
en laat mij niet alleen het geheugen draaien, omdat het geheugen lijkt in orde.

273
00:16:45,400 --> 00:16:49,180
Ik krijg gelukkig. Ga dat extra byte aan het einde van de array

274
00:16:49,180 --> 00:16:51,060
lijkt niet te problematisch.

275
00:16:51,060 --> 00:16:56,370
Maar laat mij, toch, doe een sanity check, wat gewoon betekent controleren

276
00:16:56,370 --> 00:16:58,320
of dit daadwerkelijk correct.

277
00:16:58,320 --> 00:17:04,690
>> Dus laten we het doen valgrind-v - lek-check = vol,

278
00:17:04,690 --> 00:17:07,520
en vervolgens de naam van het programma is in dit geval het geheugen, niet a.out.

279
00:17:07,520 --> 00:17:10,760
Dus laat me ga je gang en doen. Druk op Enter.

280
00:17:10,760 --> 00:17:14,109
Dear God. Dit is de output, en dit is wat ik zinspeelde eerder.

281
00:17:14,109 --> 00:17:17,550
Maar, als je leert om hier te lezen door alle onzin,

282
00:17:17,550 --> 00:17:20,760
de meeste van deze is gewoon diagnostische uitvoer dat is niet zo interessant.

283
00:17:20,760 --> 00:17:24,829
Wat uw oog echt wil op zoek naar is enige vermelding van fout of ongeldig.

284
00:17:24,829 --> 00:17:26,800
Woorden die problemen stellen.

285
00:17:26,800 --> 00:17:29,340
En inderdaad, laten we eens kijken wat er fout gaat hier beneden.

286
00:17:29,340 --> 00:17:35,230
Ik heb een samenvatting van een soort, "in gebruik bij afrit:. 40 bytes in 1 blokken"

287
00:17:35,230 --> 00:17:38,750
Ik ben niet echt zeker wat een blok is nog niet, maar 40 bytes

288
00:17:38,750 --> 00:17:41,260
eigenlijk voelt het alsof ik kon achterhalen waar dat vandaan komt.

289
00:17:41,260 --> 00:17:45,030
40 bytes. Waarom zijn 40 bytes in gebruik bij afslag?

290
00:17:45,030 --> 00:17:48,780
En meer in het bijzonder, als we naar beneden scrollen hier,

291
00:17:48,780 --> 00:17:54,520
waarom heb ik zeker verloren 40 bytes? Ja?

292
00:17:54,520 --> 00:17:59,520
[Student antwoord, onverstaanbaar] Perfect. Ja, precies.

293
00:17:59,520 --> 00:18:03,540
Er waren tien gehele getallen, en elk daarvan is grootte van 4 of 32 bits,

294
00:18:03,540 --> 00:18:08,300
dus ik heb verloren precies 40 bytes, omdat, zoals u voorgesteld, heb ik niet de zogenaamde vrije.

295
00:18:08,300 --> 00:18:13,460
Dat is een bug, en nu laten we eens kijken naar beneden verder een beetje en zien naast dit,

296
00:18:13,460 --> 00:18:16,900
"Ongeldige schrijven van grootte 4." Nu wat is dit?

297
00:18:16,900 --> 00:18:21,150
Dit adres wordt uitgedrukt wat basis notatie, blijkbaar?

298
00:18:21,150 --> 00:18:23,640
Dit is hexadecimaal, en elke keer zie je een nummer beginnend met 0x,

299
00:18:23,640 --> 00:18:29,410
het betekent hexadecimaal, die we al in, denk ik, sectie PSET 0's van vragen deed,

300
00:18:29,410 --> 00:18:34,090
en dat was alleen maar om een ​​warming-up oefening te doen, het omzetten van decimaal naar hex naar binair, enzovoort.

301
00:18:34,090 --> 00:18:39,220
Hexadecimaal, gewoon door menselijke conventie, wordt meestal gebruikt om pointers te vertegenwoordigen

302
00:18:39,220 --> 00:18:41,570
of, meer algemeen, richt. Het is gewoon een conventie,

303
00:18:41,570 --> 00:18:45,340
want het is een beetje makkelijker te lezen is, is het een beetje compacter dan iets als decimaal,

304
00:18:45,340 --> 00:18:47,720
en binaire is nutteloos voor de meeste mensen om te gebruiken.

305
00:18:47,720 --> 00:18:50,840
Dus nu wat betekent dit? Nou, het lijkt erop dat er een ongeldige schrijf

306
00:18:50,840 --> 00:18:54,480
van maat 4 op lijn 21 van memory.c.

307
00:18:54,480 --> 00:18:59,180
Dus laten we terug gaan naar lijn 21, en inderdaad, hier is dat ongeldig schrijven.

308
00:18:59,180 --> 00:19:02,640
Dus Valgrind is niet van plan om volledig m'n hand vasthouden en me vertellen wat de oplossing is,

309
00:19:02,640 --> 00:19:05,520
maar het is het opsporen van dat ik een ongeldige schrijven doen.

310
00:19:05,520 --> 00:19:08,800
Ik raak 4 bytes dat ik niet zou moeten zijn, en blijkbaar dat komt omdat,

311
00:19:08,800 --> 00:19:13,960
zoals u zegt, ik doe [10] in plaats van [9] maximaal

312
00:19:13,960 --> 00:19:16,660
of [0] of iets daar tussenin.

313
00:19:16,660 --> 00:19:19,690
Met Valgrind, realiseert elke keer dat je nu het schrijven van een programma

314
00:19:19,690 --> 00:19:24,190
dat pointers gebruikt en maakt gebruik van het geheugen, en malloc meer in het bijzonder,

315
00:19:24,190 --> 00:19:27,080
zeker krijgen in de gewoonte van het runnen van deze lange

316
00:19:27,080 --> 00:19:30,890
maar heel gemakkelijk gekopieerd en geplakt beheersing van Valgrind

317
00:19:30,890 --> 00:19:32,650
om te zien of er wat fouten in.

318
00:19:32,650 --> 00:19:34,820
En het zal overweldigend zijn elke keer zie je de output,

319
00:19:34,820 --> 00:19:39,430
maar gewoon ontleden door middel van visueel alle output en kijk of je ziet vermeldingen van fouten

320
00:19:39,430 --> 00:19:43,190
of waarschuwingen of ongeldige of verloren.

321
00:19:43,190 --> 00:19:46,200
Ieder woord dat klinkt alsof je genaaid ergens.

322
00:19:46,200 --> 00:19:48,580
Dus beseffen dat is een nieuwe tool in uw toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Nu op maandag hadden we een hele hoop mensen komen hier

324
00:19:51,270 --> 00:19:53,150
en vertegenwoordigen de notie van een gekoppelde lijst.

325
00:19:53,150 --> 00:20:00,970
En introduceerden we de gekoppelde lijst als een oplossing voor welk probleem?

326
00:20:00,970 --> 00:20:04,590
Ja? [Student antwoord, onverstaanbaar] Goed.

327
00:20:04,590 --> 00:20:06,530
Arrays kan niet geheugen toegevoegd.

328
00:20:06,530 --> 00:20:09,440
Als u toewijzen een array van maat 10, dat is alles wat je krijgt.

329
00:20:09,440 --> 00:20:13,690
U kunt bellen naar een functie als realloc als je in eerste instantie genaamd malloc,

330
00:20:13,690 --> 00:20:17,580
en dat kan proberen de array groeien als er ruimte naar het einde van het

331
00:20:17,580 --> 00:20:21,610
dat niemand anders gebruikt, en als er niet, zal het gewoon vinden een groter stuk ergens anders.

332
00:20:21,610 --> 00:20:25,040
Maar dan zal het kopiëren al die bytes in de nieuwe array.

333
00:20:25,040 --> 00:20:28,310
Dit klinkt als een heel correcte oplossing.

334
00:20:28,310 --> 00:20:34,790
Waarom is dit niet aantrekkelijk?

335
00:20:34,790 --> 00:20:36,940
Ik bedoel het werkt, hebben mensen dit probleem opgelost.

336
00:20:36,940 --> 00:20:40,710
Waarom hebben we nodig om het op te lossen op maandag met gelinkte lijsten? Ja?

337
00:20:40,710 --> 00:20:44,060
[Student antwoord, onverstaanbaar] Het kan lang duren.

338
00:20:44,060 --> 00:20:49,260
In feite, elke keer dat je belt malloc of realloc of calloc, die nog is een andere,

339
00:20:49,260 --> 00:20:52,470
elke keer dat je het programma, zijn in gesprek met het besturingssysteem,

340
00:20:52,470 --> 00:20:54,310
je de neiging om het programma te vertragen.

341
00:20:54,310 --> 00:20:57,470
En als je aan het doen bent dit soort dingen in lussen, je bent echt vertragen dingen naar beneden.

342
00:20:57,470 --> 00:21:00,740
Je gaat niet naar deze merken voor de eenvoudigste van "hello world" type programma's,

343
00:21:00,740 --> 00:21:04,300
maar in veel grotere programma's, met de vraag het besturingssysteem opnieuw en opnieuw voor het geheugen

344
00:21:04,300 --> 00:21:07,520
of het geven van het terug opnieuw en opnieuw heeft de neiging om niet een goede zaak.

345
00:21:07,520 --> 00:21:11,210
Plus, het is gewoon soort van intellectueel - het is een complete verspilling van tijd.

346
00:21:11,210 --> 00:21:16,490
Waarom wijzen meer en meer geheugen, risico kopiëren alles in de nieuwe array,

347
00:21:16,490 --> 00:21:21,980
Als u een alternatief waarmee u toewijzen slechts zoveel geheugen als je eigenlijk nodig hebben?

348
00:21:21,980 --> 00:21:24,130
Dus er is plussen en minnen hier.

349
00:21:24,130 --> 00:21:26,730
Een van de pluspunten is nu dat we dynamiek hebben.

350
00:21:26,730 --> 00:21:29,100
Maakt niet uit waar de delen van het geheugen is dat vrij zijn,

351
00:21:29,100 --> 00:21:32,070
Ik kan gewoon soort van het maken van deze broodkruimels via pointers

352
00:21:32,070 --> 00:21:34,470
om mijn hele gelinkte lijst aaneenrijgen.

353
00:21:34,470 --> 00:21:36,470
Maar ik betaal ten minste een prijs.

354
00:21:36,470 --> 00:21:40,060
>> Wat moet ik opgeven bij het verkrijgen van gelinkte lijsten?

355
00:21:40,060 --> 00:21:42,470
Ja? [Student antwoord, onverstaanbaar] Goed.

356
00:21:42,470 --> 00:21:45,650
Je hebt meer geheugen. Nu moet ik ruimte voor deze pointers,

357
00:21:45,650 --> 00:21:47,900
en in het geval van deze super eenvoudige verbonden lijst

358
00:21:47,900 --> 00:21:51,410
dat alleen probeert te integers, die 4 bytes op te slaan, we blijven zeggen

359
00:21:51,410 --> 00:21:54,240
nou ja, een pointer is 4 bytes, dus nu heb ik letterlijk verdubbeld

360
00:21:54,240 --> 00:21:57,290
de hoeveelheid geheugen die ik nodig heb alleen maar om deze lijst op te slaan.

361
00:21:57,290 --> 00:21:59,680
Maar nogmaals, dit is een constante afweging in de informatica

362
00:21:59,680 --> 00:22:03,440
tussen tijd en ruimte en de ontwikkeling, inzet en andere middelen.

363
00:22:03,440 --> 00:22:06,630
Wat is een ander nadeel van het gebruik van een gekoppelde lijst? Ja?

364
00:22:06,630 --> 00:22:10,150
[Student antwoord, onverstaanbaar]

365
00:22:10,150 --> 00:22:12,600
Goed. Niet zo gemakkelijk te bereiken. We kunnen niet langer leverage

366
00:22:12,600 --> 00:22:15,530
week 0 principes als verdeel en heers.

367
00:22:15,530 --> 00:22:18,220
En meer specifiek, binaire zoekopdracht. Want ook al hebben we mensen

368
00:22:18,220 --> 00:22:20,400
kunnen grofweg zien waar het midden van deze lijst is,

369
00:22:20,400 --> 00:22:25,840
de computer weet alleen dat deze gekoppeld lijst begint op het adres genoemd eerste.

370
00:22:25,840 --> 00:22:28,250
En dat is 0x123 of zoiets.

371
00:22:28,250 --> 00:22:30,990
En de enige manier waarop het programma vindt de middelste element

372
00:22:30,990 --> 00:22:33,350
is om daadwerkelijk de hele lijst.

373
00:22:33,350 --> 00:22:35,500
En zelfs dan, het heeft letterlijk de hele lijst, omdat

374
00:22:35,500 --> 00:22:38,950
zelfs als je eenmaal het middelste element door het volgen van de aanwijzingen,

375
00:22:38,950 --> 00:22:42,380
u het programma, hebben geen idee hoe lang deze lijst is, potentieel,

376
00:22:42,380 --> 00:22:45,250
tot je het einde van het, en hoe weet je dat programmatisch

377
00:22:45,250 --> 00:22:48,600
dat je aan het eind van een gekoppelde lijst?

378
00:22:48,600 --> 00:22:51,120
Er is een speciale NULL pointer, dus nogmaals, een conventie.

379
00:22:51,120 --> 00:22:53,870
In plaats van gebruik van deze wijzer, we zeker niet willen dat het wat vuilnis waarde

380
00:22:53,870 --> 00:22:57,750
pointing podium ergens, we willen dat het met de hand naar beneden, NULL,

381
00:22:57,750 --> 00:23:01,530
zodat we dit eindpunt in deze datastructuur zodat we weten waar het eindigt.

382
00:23:01,530 --> 00:23:03,410
>> Wat als we willen dit te manipuleren?

383
00:23:03,410 --> 00:23:05,980
We hebben het grootste deel van deze visueel, en met mensen,

384
00:23:05,980 --> 00:23:07,630
maar wat als we willen een insertie doen?

385
00:23:07,630 --> 00:23:12,360
Zodat de oorspronkelijke lijst was 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Wat als we dan wilden malloc ruimte voor nummer 55, een knooppunt voor het,

387
00:23:16,730 --> 00:23:20,730
en dan willen we tot 55 in te voegen in de lijst net als wij op maandag?

388
00:23:20,730 --> 00:23:23,690
Hoe gaan we dit doen? Nou, Anita kwam en ze in wezen liep de lijst.

389
00:23:23,690 --> 00:23:27,500
Ze begon bij het eerste element, dan de volgende, de volgende, de volgende, de volgende, de volgende.

390
00:23:27,500 --> 00:23:29,500
Tenslotte raakte de linker helemaal naar beneden

391
00:23:29,500 --> 00:23:34,480
en gerealiseerd oh, dit is NULL. Dus wat wijzer manipulatie gedaan moest worden?

392
00:23:34,480 --> 00:23:37,980
De persoon die was op het einde, nummer 34, die nodig zijn linkerhand omhoog

393
00:23:37,980 --> 00:23:46,220
te wijzen op 55, 55 nodig hun linkerarm naar beneden te zijn de nieuwe NULL terminator. Gereed.

394
00:23:46,220 --> 00:23:49,540
Vrij gemakkelijk tot 55 in te voegen in een gesorteerde lijst.

395
00:23:49,540 --> 00:23:51,800
En hoe zou dit eruit?

396
00:23:51,800 --> 00:23:55,690
>> Laat me gaan en open te stellen wat code voorbeeld.

397
00:23:55,690 --> 00:23:58,120
Ik zal open gedit, en laat me open te stellen eerste twee bestanden.

398
00:23:58,120 --> 00:24:02,050
Een daarvan is list1.h, en laat me even aan herinneren dat dit het stuk code

399
00:24:02,050 --> 00:24:04,920
die we gebruikten een knooppunt vertegenwoordigen.

400
00:24:04,920 --> 00:24:13,040
Een knooppunt heeft zowel een int genoemd n en een pointer genaamd volgende die net wijst naar het volgende ding in de lijst.

401
00:24:13,040 --> 00:24:15,450
Dat is nu in een. H bestand. Waarom?

402
00:24:15,450 --> 00:24:19,090
Er is dit verdrag, en we hebben geen gebruik gemaakt van deze een enorme hoeveelheid onszelf,

403
00:24:19,090 --> 00:24:22,220
maar de persoon die schreef printf en andere functies

404
00:24:22,220 --> 00:24:27,150
gaf als een geschenk aan de wereld al die functies door het schrijven van een bestand genaamd stdio.h.

405
00:24:27,150 --> 00:24:30,950
En dan is er nog string.h, en dan is er map.h, en er is al die h bestanden

406
00:24:30,950 --> 00:24:34,410
die u zou kunnen hebben gezien of gebruikt gedurende de looptijd geschreven door andere mensen.

407
00:24:34,410 --> 00:24:38,470
Typisch in die. H bestanden zijn alleen dingen als typedefs

408
00:24:38,470 --> 00:24:42,310
of verklaringen van typen op maat of verklaringen van constanten.

409
00:24:42,310 --> 00:24:47,890
Je hoeft niet gezet functies 'implementaties in header-bestanden.

410
00:24:47,890 --> 00:24:50,570
Je zet in plaats daarvan alleen hun prototypes.

411
00:24:50,570 --> 00:24:53,050
U dingen die je wilt delen met de wereld zetten wat ze nodig hebben

412
00:24:53,050 --> 00:24:55,640
om hun compileren. Dus gewoon om in deze gewoonte,

413
00:24:55,640 --> 00:24:59,110
hebben we besloten om hetzelfde te doen. Er is niet veel in list1.h,

414
00:24:59,110 --> 00:25:02,070
maar we hebben gezet iets dat misschien van belang zijn voor mensen in de wereld

415
00:25:02,070 --> 00:25:05,030
die willen ons gelinkte lijst implementatie gebruiken.

416
00:25:05,030 --> 00:25:08,040
Nu, in list1.c, ik zal niet gaan door dit hele gebeuren

417
00:25:08,040 --> 00:25:11,390
want het is een beetje lang, dit programma, maar laten we snel leeg dat het echt achter de prompt.

418
00:25:11,390 --> 00:25:15,720
Laat me compileren list1, laat me dan list1 rennen, en wat je ziet is

419
00:25:15,720 --> 00:25:18,070
hebben we gesimuleerd een eenvoudig klein programma hier

420
00:25:18,070 --> 00:25:20,990
dat gaat staat u mij toe te voegen en te verwijderen nummers om een ​​lijst.

421
00:25:20,990 --> 00:25:24,310
Dus laat me gaan en typ 3 voor de menu-optie 3.

422
00:25:24,310 --> 00:25:27,880
Ik wil het aantal plaatsen - laten we het eerste nummer, dat is 9,

423
00:25:27,880 --> 00:25:30,550
en nu ik heb gehoord dat de lijst is nu 9.

424
00:25:30,550 --> 00:25:33,760
Laat me ga je gang en doe een ander inbrengen, dus ik sloeg menu-optie 3.

425
00:25:33,760 --> 00:25:36,760
Welk nummer moet ik wilt invoegen? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. En ik doe nog een.

427
00:25:39,220 --> 00:25:41,720
Laat me steek de nummer 22.

428
00:25:41,720 --> 00:25:45,850
Dus hebben we het begin van de gekoppelde lijst die wij hadden in een diavoorstelling vorm een ​​ogenblik geleden.

429
00:25:45,850 --> 00:25:48,740
Hoe wordt deze toevoeging daadwerkelijk gebeurt?

430
00:25:48,740 --> 00:25:52,000
Inderdaad, 22 is nu aan het einde van de lijst.

431
00:25:52,000 --> 00:25:55,050
Dus het verhaal vertelden we op het podium op maandag en vatte juist nu

432
00:25:55,050 --> 00:25:57,460
moet daadwerkelijk gebeuren in de code.

433
00:25:57,460 --> 00:25:59,700
Laten we eens een kijkje nemen. Laat me naar beneden scrollen in dit bestand.

434
00:25:59,700 --> 00:26:01,720
We verdoezelen enkele van de functies,

435
00:26:01,720 --> 00:26:05,630
maar we zullen naar beneden gaan naar, laten we zeggen, de insert-functie.

436
00:26:05,630 --> 00:26:11,720
>> Laten we eens kijken hoe we gaan over het invoegen van een nieuw knooppunt in deze gelinkte lijst.

437
00:26:11,720 --> 00:26:14,550
Waar is de lijst verklaard? Nou, laten we gaat u helemaal op de top,

438
00:26:14,550 --> 00:26:19,970
en merk dat mijn gelinkte lijst in wezen wordt verklaard als een enkele pointer dat is in eerste instantie NULL.

439
00:26:19,970 --> 00:26:23,180
Dus ik ben met behulp van een globale variabele hier, die over het algemeen hebben we gepredikt tegen

440
00:26:23,180 --> 00:26:25,280
want het maakt je code een beetje rommelig te onderhouden,

441
00:26:25,280 --> 00:26:29,080
het is een soort van lui, meestal, maar het is niet lui en het is niet verkeerd en het is niet slecht

442
00:26:29,080 --> 00:26:33,660
Als je programma's enige doel in het leven is om te simuleren een gelinkte lijst.

443
00:26:33,660 --> 00:26:35,460
En dat is precies wat we doen.

444
00:26:35,460 --> 00:26:39,100
Dus in plaats van te verklaren dat in hoofd-en vervolgens door te geven aan elke functie

445
00:26:39,100 --> 00:26:42,640
we hebben geschreven in dit programma, hebben we in plaats daarvan realiseren oh, laten we gewoon maken het globale

446
00:26:42,640 --> 00:26:47,060
omdat het hele doel van dit programma is om aan te tonen een en slechts een gelinkte lijst.

447
00:26:47,060 --> 00:26:50,700
Dus dat voelt goed. Hier zijn mijn prototypes, en we zullen niet gaan door al deze,

448
00:26:50,700 --> 00:26:55,800
maar ik schreef een delete functie, een zoekfunctie, een insert-functie, en een traverse functie.

449
00:26:55,800 --> 00:26:59,080
Maar laten we nu terug naar beneden naar de insert-functie

450
00:26:59,080 --> 00:27:01,490
en zie hoe deze hier werkt.

451
00:27:01,490 --> 00:27:09,940
Insert is on line - hier gaan we.

452
00:27:09,940 --> 00:27:12,850
Invoegen. Dus het neemt geen argumenten, want we gaan om te vragen

453
00:27:12,850 --> 00:27:15,930
de gebruiker binnenkant van deze functie voor het nummer dat ze wilt invoegen.

454
00:27:15,930 --> 00:27:19,410
Maar eerst bereiden we om hen wat ruimte.

455
00:27:19,410 --> 00:27:22,050
Dit is een soort van kopiëren en plakken van de andere voorbeeld.

456
00:27:22,050 --> 00:27:25,110
In dat geval waren we de toerekening van een int, dit keer zijn we het toewijzen van een knooppunt.

457
00:27:25,110 --> 00:27:27,910
Ik heb niet echt herinneren hoeveel bytes een knooppunt is, maar dat is prima.

458
00:27:27,910 --> 00:27:30,460
Sizeof kan cijfer dat uit voor mij.

459
00:27:30,460 --> 00:27:33,340
En waarom krijg ik het controleren op NULL in lijn 120?

460
00:27:33,340 --> 00:27:37,530
Wat kan er mis gaan in de lijn 119? Ja?

461
00:27:37,530 --> 00:27:40,530
[Student antwoord, onverstaanbaar]

462
00:27:40,530 --> 00:27:43,440
Goed. Kon gewoon het geval dat ik heb gevraagd om te veel geheugen te

463
00:27:43,440 --> 00:27:47,020
of er iets mis is en het besturingssysteem niet genoeg bytes aan mij geven,

464
00:27:47,020 --> 00:27:50,640
dus het signaleert zo veel door terug te keren NULL, en als ik niet controleren of dat

465
00:27:50,640 --> 00:27:54,710
en ik blindelings te gaan gebruiken het adres terug, het kan NULL.

466
00:27:54,710 --> 00:27:58,400
Het zou een onbekende waarde, niet een goede zaak, tenzij ik -

467
00:27:58,400 --> 00:28:00,590
daadwerkelijk niet een onbekende waarde. Het zou kunnen zijn NULL, dus ik wil niet

468
00:28:00,590 --> 00:28:02,550
te misbruiken en risico dereferentie het.

469
00:28:02,550 --> 00:28:07,410
Als dat gebeurt, ik heb net terug en we zullen doen alsof ik niet terug enkele herinnering op alle.

470
00:28:07,410 --> 00:28:12,270
>> Anders, ik vertel de gebruiker geef me een nummer in te voegen, roep ik onze oude vriend GetInt,

471
00:28:12,270 --> 00:28:15,530
en dan was dit de nieuwe syntaxis introduceerden we op maandag.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' betekent neem het adres dat u werden gegeven door malloc

473
00:28:20,320 --> 00:28:23,490
overeenkomende met de eerste byte van een nieuw knooppunt object,

474
00:28:23,490 --> 00:28:26,860
en ga dan naar het veld met de naam n.

475
00:28:26,860 --> 00:28:35,270
Een beetje trivia vraag: Dit komt overeen met wat meer cryptische regel code?

476
00:28:35,270 --> 00:28:38,110
Hoe kon ik anders hebben geschreven dit? Wilt u een steek te nemen?

477
00:28:38,110 --> 00:28:41,480
[Student antwoord, onverstaanbaar]

478
00:28:41,480 --> 00:28:44,870
Goed. Met behulp van de. N, maar het is niet zo simpel als dit.

479
00:28:44,870 --> 00:28:47,090
Wat moet ik eerst doen? [Student antwoord, onverstaanbaar]

480
00:28:47,090 --> 00:28:52,730
Goed. Ik moet * newptr.n doen.

481
00:28:52,730 --> 00:28:55,610
Dus dit zegt nieuwe pointer is duidelijk een adres. Waarom?

482
00:28:55,610 --> 00:28:59,520
Omdat het werd teruggestuurd door malloc. De * newptr zeggen "er naartoe te gaan,"

483
00:28:59,520 --> 00:29:02,970
en dan als je eenmaal daar bent, dan kunt u gebruik maken van de meer bekende. n,

484
00:29:02,970 --> 00:29:05,730
maar dit ziet er gewoon een beetje lelijk, vooral als wij mensen gaan

485
00:29:05,730 --> 00:29:10,360
trekken pointers met pijlen de hele tijd, de wereld is gestandaardiseerd op deze pijl notatie,

486
00:29:10,360 --> 00:29:12,320
die doet precies hetzelfde.

487
00:29:12,320 --> 00:29:16,070
Zodat u alleen gebruik maken van de -> notatie als het ding aan de linkerkant is een pointer.

488
00:29:16,070 --> 00:29:18,790
Anders, als het een echte struct, gebruik maken van de. N.

489
00:29:18,790 --> 00:29:25,800
En dan dit: Waarom moet ik initialiseren newptr-> naast NULL?

490
00:29:25,800 --> 00:29:28,610
We willen niet dat een loshangende linkerhand af van het einde van het podium.

491
00:29:28,610 --> 00:29:31,630
We willen het recht naar beneden, wat betekent dat het einde van deze lijst

492
00:29:31,630 --> 00:29:34,980
zou kunnen zijn op dit knooppunt, zodat we beter voor zorgen dat het NULL is.

493
00:29:34,980 --> 00:29:38,460
En, in het algemeen, het initialiseren van uw variabelen of uw gegevens leden en structs

494
00:29:38,460 --> 00:29:40,470
iets is gewoon goede praktijk.

495
00:29:40,470 --> 00:29:45,170
Gewoon laten vuilnis bestaan ​​en blijven over het algemeen bestaan ​​krijgt u in de problemen

496
00:29:45,170 --> 00:29:48,650
als je vergeet om iets te doen later.

497
00:29:48,650 --> 00:29:51,590
>> Hier zijn een paar gevallen. Ook dit is het inzetstuk functie

498
00:29:51,590 --> 00:29:54,930
en het eerste wat ik controleren is als de variabele genaamd eerste,

499
00:29:54,930 --> 00:29:58,240
dat globale variabele NULL is, dat betekent dat er geen gelinkte lijst.

500
00:29:58,240 --> 00:30:02,460
We hebben niet alle nummers geplaatst, dus het is triviaal te voegen dit huidige nummer

501
00:30:02,460 --> 00:30:05,240
in de lijst, aangezien zij tot net aan het begin van de lijst.

502
00:30:05,240 --> 00:30:08,100
Dus dit was toen Anita was gewoon staan ​​hier alleen, alsof

503
00:30:08,100 --> 00:30:11,390
niemand anders was hier op het podium tot we toegewezen een knooppunt,

504
00:30:11,390 --> 00:30:13,940
dan kon ze omhoog haar hand voor de eerste keer,

505
00:30:13,940 --> 00:30:17,420
als iedereen was gekomen op het podium na haar op maandag.

506
00:30:17,420 --> 00:30:22,900
Nu hier, dit is een beetje cheque waar ik moet zeggen dat als het nieuwe knooppunt de waarde van n

507
00:30:22,900 --> 00:30:27,370
is <de waarde van n in de huidige eerste knooppunt

508
00:30:27,370 --> 00:30:29,930
dat betekent dat er een gelinkte lijst die is begonnen.

509
00:30:29,930 --> 00:30:32,330
Er is ten minste een knooppunt in de lijst, maar deze nieuwe man

510
00:30:32,330 --> 00:30:37,230
behoort vóór het, dus we moeten om te bewegen dingen.

511
00:30:37,230 --> 00:30:43,450
Met andere woorden, als de lijst is begonnen met slechts, laten we zeggen,

512
00:30:43,450 --> 00:30:48,100
alleen het nummer 17, dat is het - in feite, kunnen we dit doen duidelijker.

513
00:30:48,100 --> 00:30:56,010
Als we beginnen ons verhaal met een pointer hier de naam eerst,

514
00:30:56,010 --> 00:30:59,870
en in eerste instantie het is NULL, en voegen we de nummer 9,

515
00:30:59,870 --> 00:31:02,510
nummer 9 behoort duidelijk bij het begin van de lijst.

516
00:31:02,510 --> 00:31:07,400
Dus laten we doen alsof we gewoon het adres of het nummer 9 malloced en zet het hier.

517
00:31:07,400 --> 00:31:13,170
Als de eerste is 9 standaard, het eerste scenario hebben we besproken betekent gewoon laten we punt deze man hier,

518
00:31:13,170 --> 00:31:15,790
laat dit als NULL, nu hebben we het getal 9.

519
00:31:15,790 --> 00:31:18,280
Het volgende nummer willen we voegen is 17.

520
00:31:18,280 --> 00:31:22,420
17 behoort hier, dus we gaan te hebben om wat logisch stepping doen door middel van dit.

521
00:31:22,420 --> 00:31:26,060
Dus in plaats Laten we, voordat we dat doen, laten we doen alsof dat we wilden het cijfer 8 in te voegen.

522
00:31:26,060 --> 00:31:28,650
>> Dus gewoon voor het gemak, ik ga hier tekenen.

523
00:31:28,650 --> 00:31:30,760
Maar vergeet niet, kan malloc zet het bijna overal.

524
00:31:30,760 --> 00:31:33,460
Maar ter wille van tekening, zal ik hier gezegd.

525
00:31:33,460 --> 00:31:38,440
Dus doen alsof ik heb net een knooppunt voor het getal 8 toegewezen, dit is NULL standaard.

526
00:31:38,440 --> 00:31:42,800
Wat heeft nu gebeuren? Een paar dingen.

527
00:31:42,800 --> 00:31:47,090
We hebben deze fout op het podium op maandag, waar we bijgewerkt een pointer als deze,

528
00:31:47,090 --> 00:31:51,890
toen deed dit, en dan hebben we beweerd - we verweesde iedereen op het podium.

529
00:31:51,890 --> 00:31:54,350
Omdat je KAN NIET - de volgorde van bewerkingen is hier van belang,

530
00:31:54,350 --> 00:31:58,760
want nu we verloren dit knooppunt 9 dat is gewoon soort van zweven in de ruimte.

531
00:31:58,760 --> 00:32:01,150
Dus dit was niet de juiste aanpak op maandag.

532
00:32:01,150 --> 00:32:03,330
We moeten eerst iets anders te doen.

533
00:32:03,330 --> 00:32:06,280
De toestand van de wereld ziet er zo uit. Aanvankelijk heeft 8 toegewezen.

534
00:32:06,280 --> 00:32:10,550
Wat zou een betere manier van het plaatsen van 8 zijn?

535
00:32:10,550 --> 00:32:14,720
In plaats van het bijwerken van deze pointer eerste, in plaats daarvan gewoon updaten deze hier.

536
00:32:14,720 --> 00:32:17,720
Dus moeten we een regel code dat gaat deze NULL-teken te zetten

537
00:32:17,720 --> 00:32:22,020
in een echte pointer die wijzend op knooppunt 9,

538
00:32:22,020 --> 00:32:27,970
en dan kunnen we veilig veranderen als eerste hier wijzen op deze kerel.

539
00:32:27,970 --> 00:32:31,330
Nu hebben we een lijst, een gelinkte lijst, uit twee elementen.

540
00:32:31,330 --> 00:32:33,580
En wat betekent dit eigenlijk uit hier?

541
00:32:33,580 --> 00:32:36,900
Als we kijken naar de code, merken dat ik heb precies dat gedaan.

542
00:32:36,900 --> 00:32:41,970
Ik heb gezegd newptr, en in dit verhaal, newptr wees naar deze man.

543
00:32:41,970 --> 00:32:45,520
>> Dus laat me trekken nog een ding, en ik zou hebben een beetje meer ruimte voor.

544
00:32:45,520 --> 00:32:48,540
Dus vergeef het piepkleine tekening.

545
00:32:48,540 --> 00:32:52,140
Deze man heet newptr.

546
00:32:52,140 --> 00:32:57,940
Dat is de variabele die we uitgeroepen tot een paar regels eerder, in lijn - net boven de 25.

547
00:32:57,940 --> 00:33:03,430
En het is te wijzen op 8. Dus als ik zeg newptr-> volgende, dat betekent naar de struct

548
00:33:03,430 --> 00:33:07,910
dat wordt gewezen door newptr, hier dus we zijn, er heen gaan.

549
00:33:07,910 --> 00:33:13,990
Vervolgens op de pijl zegt krijg het volgende veld, en vervolgens de = zegt gezet welke waarde er?

550
00:33:13,990 --> 00:33:17,280
De waarde die was in de eerste plaats; welke waarde was in de eerste?

551
00:33:17,280 --> 00:33:21,930
Eerste wees naar dit knooppunt, dus dat betekent dat dit moet nu wijzen op dit knooppunt.

552
00:33:21,930 --> 00:33:25,660
Met andere woorden, wat lijkt zij het een belachelijk Mess With My handschrift,

553
00:33:25,660 --> 00:33:28,620
wat is een eenvoudig idee van slechts het verplaatsen van deze pijlen rond

554
00:33:28,620 --> 00:33:31,560
vertaalt zich naar code met alleen deze one-liner.

555
00:33:31,560 --> 00:33:38,110
Bewaar wat er in eerste in het volgende veld en werk vervolgens wat eerst eigenlijk is.

556
00:33:38,110 --> 00:33:40,900
Laten we vooruit en vooruit gaan door een aantal van deze,

557
00:33:40,900 --> 00:33:44,220
en alleen kijken naar deze staart inbrengen voor nu.

558
00:33:44,220 --> 00:33:51,210
Stel dat ik bij het punt waar ik vind dat het volgende veld van een node NULL is.

559
00:33:51,210 --> 00:33:53,410
En op dit punt in het verhaal, een detail dat ik voorbij te gaan

560
00:33:53,410 --> 00:33:58,170
is dat ik een andere wijzer hier geïntroduceerde in lijn 142, voorganger wijzer.

561
00:33:58,170 --> 00:34:01,320
Wezen op dit punt in het verhaal, als de lijst krijgt lange,

562
00:34:01,320 --> 00:34:04,800
Ik soort van nodig om het te lopen met twee vingers, want als ik te ver gaan,

563
00:34:04,800 --> 00:34:08,219
remember in een enkel-lengte lijst, kunt u niet achteruit gaan.

564
00:34:08,219 --> 00:34:13,659
Dus dit idee van predptr is mijn linker vinger en newptr - niet newptr.

565
00:34:13,659 --> 00:34:17,199
Een andere aanwijzing dat hier is is mijn andere vinger, en ik ben gewoon een soort van het lopen van de lijst.

566
00:34:17,199 --> 00:34:22,179
Dat is waarom die er bestaat. Maar laten we slechts een van de eenvoudiger gevallen hier te overwegen.

567
00:34:22,179 --> 00:34:26,620
Als dat aanwijzer volgende veld NULL is, wat is de logische implicatie?

568
00:34:26,620 --> 00:34:30,840
Als u doorkruisen deze lijst en je raakt een NULL pointer?

569
00:34:30,840 --> 00:34:35,780
Je bent aan het einde van de lijst, en dus de code om dan voeg je dit een extra element

570
00:34:35,780 --> 00:34:41,230
is een soort van de intuïtieve zal dat knooppunt waarvan de volgende pointer NULL is,

571
00:34:41,230 --> 00:34:46,120
dus dit is momenteel NULL, en verander het, hoewel, om het adres van de nieuwe node.

572
00:34:46,120 --> 00:34:52,260
Dus we gewoon tekenen in code op de pijl die we trokken op het podium door het verhogen van iemands linkerhand.

573
00:34:52,260 --> 00:34:54,070
>> En het geval dat ik mijn handen zwaaien voor nu,

574
00:34:54,070 --> 00:34:58,020
gewoon omdat ik denk dat het makkelijk is om te verdwalen als we het doen in dit soort omgeving,

575
00:34:58,020 --> 00:35:00,600
is het controleren op invoegen op midden van de lijst.

576
00:35:00,600 --> 00:35:03,220
Maar net intuïtief, wat er moet gebeuren als je wilt om erachter te komen

577
00:35:03,220 --> 00:35:06,600
waar sommige nummer behoort in het midden is je hoeft niet te te lopen

578
00:35:06,600 --> 00:35:09,510
met meer dan een vinger meerdere pointer,

579
00:35:09,510 --> 00:35:12,920
erachter te komen waar het hoort door controle is het element <de huidige,

580
00:35:12,920 --> 00:35:15,450
> De huidige, en zodra je die plaats,

581
00:35:15,450 --> 00:35:20,400
dan moet je dit soort shell spel te doen wanneer u de aanwijzingen om zeer zorgvuldig.

582
00:35:20,400 --> 00:35:23,850
En dat antwoord, als je wilt om te redeneren graag via dit thuis op uw eigen,

583
00:35:23,850 --> 00:35:28,340
neer alleen maar om deze twee regels code, maar de volgorde van die lijnen is super belangrijk.

584
00:35:28,340 --> 00:35:31,390
Want als je er bij neervalt iemands hand te verhogen en die van iemand anders in de verkeerde volgorde,

585
00:35:31,390 --> 00:35:34,580
weer, kan je uiteindelijk orphaning de lijst.

586
00:35:34,580 --> 00:35:39,500
Samenvattend meer conceptueel, invoering op de staart is betrekkelijk eenvoudig.

587
00:35:39,500 --> 00:35:42,940
Invoering op het hoofd is relatief eenvoudig,

588
00:35:42,940 --> 00:35:45,580
maar je moet een extra pointer updaten tijd

589
00:35:45,580 --> 00:35:47,930
naar nummer 5 hier knijpen in de lijst,

590
00:35:47,930 --> 00:35:51,560
en dan inbrengen in het midden gaat nog meer inspanning,

591
00:35:51,560 --> 00:35:56,130
om het getal 20 zeer zorgvuldig in te voegen in de juiste locatie,

592
00:35:56,130 --> 00:35:58,350
die tussen 17 en 22.

593
00:35:58,350 --> 00:36:02,700
Dus je moet iets doen als de nieuwe node 20 punten tot 22,

594
00:36:02,700 --> 00:36:08,470
en dan, welk knooppunt de wijzer moet worden bijgewerkt mee?

595
00:36:08,470 --> 00:36:10,630
Het is 17, om daadwerkelijk invoegen.

596
00:36:10,630 --> 00:36:14,080
Dus nogmaals, ik uitstellen van de eigenlijke code voor die specifieke toepassing.

597
00:36:14,080 --> 00:36:17,280
>> Op het eerste gezicht is het een beetje overweldigend, maar het is eigenlijk gewoon een oneindige lus

598
00:36:17,280 --> 00:36:21,770
dat is looping, lus, looping, looping, en het breken van zodra je de NULL pointer,

599
00:36:21,770 --> 00:36:24,590
op welk punt je kunt doen de nodige inbrengen.

600
00:36:24,590 --> 00:36:30,960
Dit is dan ook representatief gelinkte lijst code voor het invoegen.

601
00:36:30,960 --> 00:36:34,590
Dat was een soort van een veel, en het voelt alsof we een opgelost probleem,

602
00:36:34,590 --> 00:36:36,940
maar we hebben geïntroduceerd een hele andere. Eerlijk gezegd, we hebben al die tijd

603
00:36:36,940 --> 00:36:40,540
op grote O en Ω en looptijd, in een poging om problemen op te lossen sneller,

604
00:36:40,540 --> 00:36:43,270
en hier nemen we een grote stap terug, het voelt.

605
00:36:43,270 --> 00:36:45,380
En toch, als het doel is om gegevens op te slaan,

606
00:36:45,380 --> 00:36:48,010
het voelt als de Heilige Graal, zoals we al zeiden op maandag, zou echt

607
00:36:48,010 --> 00:36:50,470
om direct op te slaan dingen.

608
00:36:50,470 --> 00:36:53,930
>> In feite, stel dat we opzij zetten gelinkte lijst voor een moment deed

609
00:36:53,930 --> 00:36:56,000
en we in plaats daarvan introduceerde de notie van een tafel.

610
00:36:56,000 --> 00:36:59,110
En gewoon denken aan een tafel te laten voor een moment als een array.

611
00:36:59,110 --> 00:37:03,790
Deze array en dit geval heeft hier ongeveer 26 elementen, 0 tot en met 25,

612
00:37:03,790 --> 00:37:07,940
en stel dat u een aantal brok van opslag die nodig is voor namen:

613
00:37:07,940 --> 00:37:10,350
Alice en Bob en Charlie en dergelijke.

614
00:37:10,350 --> 00:37:12,880
En je moet een aantal gegevens structuur als die namen op te slaan.

615
00:37:12,880 --> 00:37:15,000
Nou, kunt u gebruik maken iets als een gekoppelde lijst

616
00:37:15,000 --> 00:37:20,260
en je kon lopen in de lijst plaatsen van Alice voor Bob en Charlie na Bob enzovoort.

617
00:37:20,260 --> 00:37:23,850
En, in feite, als je wilt code als dat zien als een terzijde,

618
00:37:23,850 --> 00:37:27,230
weet dat in list2.h, we doen precies dat.

619
00:37:27,230 --> 00:37:30,610
We zullen niet door deze code, maar dit is een variant van het eerste voorbeeld

620
00:37:30,610 --> 00:37:34,640
dat introduceert een andere struct we eerder gezien hebben zogenaamde student,

621
00:37:34,640 --> 00:37:40,330
en dan wat het eigenlijk slaat in de gelinkte lijst is een pointer naar een student structuur

622
00:37:40,330 --> 00:37:44,520
in plaats van een klein geheel getal, n.

623
00:37:44,520 --> 00:37:46,900
Dus beseffen dat er daar-code die inhoudt dat het werkelijke strijkers,

624
00:37:46,900 --> 00:37:49,940
maar als het doel bij de hand nu echt is het aanpakken van de efficiëntie probleem,

625
00:37:49,940 --> 00:37:53,380
zou het niet mooi zijn als we krijgen een object met de naam Alice,

626
00:37:53,380 --> 00:37:56,020
We willen haar in het juiste locatie in een datastructuur,

627
00:37:56,020 --> 00:37:58,860
het voelt alsof het zou echt leuk zijn om zomaar Alice,

628
00:37:58,860 --> 00:38:01,180
waarvan de naam begint met A, in de eerste locatie.

629
00:38:01,180 --> 00:38:05,270
En Bob, wiens achternaam begint met B, in de tweede plaats.

630
00:38:05,270 --> 00:38:09,580
Met een array, of laten we beginnen noemde het een tafel, een hash-tabel op dat,

631
00:38:09,580 --> 00:38:13,650
kunnen we precies dat te doen. Als we een naam als Alice,

632
00:38:13,650 --> 00:38:16,700
een string als Alice, waar moet je zet A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
We hebben een hueristic. We hebben een functie om wat input als Alice te nemen

634
00:38:20,540 --> 00:38:24,610
en terug te keren een antwoord: "Zet Alice op deze locatie."

635
00:38:24,610 --> 00:38:28,720
En deze functie, deze zwarte doos, zal worden genoemd een hash-functie.

636
00:38:28,720 --> 00:38:32,330
>> Een hash-functie is iets dat een input neemt, zoals "Alice",

637
00:38:32,330 --> 00:38:38,080
en keert terug naar je, meestal, de numerieke locatie in sommige datastructuur waar Alice behoort.

638
00:38:38,080 --> 00:38:40,830
In dit geval moet onze hashfunctie relatief eenvoudig.

639
00:38:40,830 --> 00:38:47,510
Onze hashfunctie zou zeggen, als je "Alice", welk karakter moet ik de zorg over gegeven?

640
00:38:47,510 --> 00:38:55,660
De eerste. Dus ik kijk naar [0], en dan zeg ik als [0] karakter is A, het getal 0 terug te keren.

641
00:38:55,660 --> 00:39:01,130
Als het B, terug 1. Als het C terug 2, enzovoort.

642
00:39:01,130 --> 00:39:05,940
Alle 0-index, en dat me zou toestaan ​​om Alice en daarna Bob en dan Charlie steek enzovoort

643
00:39:05,940 --> 00:39:10,960
in deze gegevensstructuur. Maar er is een probleem.

644
00:39:10,960 --> 00:39:13,060
Wat als Anita langs komt weer?

645
00:39:13,060 --> 00:39:17,510
Waar komen we Anita? Haar naam ook begint met de letter A,

646
00:39:17,510 --> 00:39:20,330
en het voelt alsof we hebben gemaakt een nog grotere puinhoop van dit probleem.

647
00:39:20,330 --> 00:39:24,380
We hebben nu direct inbrengen, constante tijd inbrengen, in een datastructuur

648
00:39:24,380 --> 00:39:27,100
in plaats van worst-case lineair,

649
00:39:27,100 --> 00:39:29,510
maar wat kunnen we doen met Anita in dit geval?

650
00:39:29,510 --> 00:39:34,110
Wat zijn de twee opties, echt? Ja?

651
00:39:34,110 --> 00:39:37,410
[Student antwoord, onverstaanbaar] Oke, dus we konden een andere dimensie hebben.

652
00:39:37,410 --> 00:39:42,320
Dat is goed. Dus we kunnen dingen bouwen in 3D als we het over gehad verbaal op maandag.

653
00:39:42,320 --> 00:39:46,700
We kunnen toevoegen een ander toegangspunt hier, maar stel dat er geen, ik probeer te houden het simpel.

654
00:39:46,700 --> 00:39:50,160
Het hele doel hier is om direct een constante-time toegang,

655
00:39:50,160 --> 00:39:52,170
dus dat is het toevoegen van te veel complexiteit.

656
00:39:52,170 --> 00:39:55,970
Wat zijn andere opties wanneer het proberen om Anita te voegen in deze gegevens structuur? Ja?

657
00:39:55,970 --> 00:39:58,610
[Student antwoord, onverstaanbaar] Goed. Dus we konden verhuizen iedereen naar beneden,

658
00:39:58,610 --> 00:40:03,040
als Charlie duwtjes naar beneden Bob en Alice, en dan zetten we Anita, waar ze echt wil zijn.

659
00:40:03,040 --> 00:40:05,660
>> Natuurlijk, nu is er een bijwerking van dit.

660
00:40:05,660 --> 00:40:09,000
Deze datastructuur is waarschijnlijk nuttig, niet omdat we mensen willen invoegen keer

661
00:40:09,000 --> 00:40:11,250
maar omdat we willen om te controleren of ze er later

662
00:40:11,250 --> 00:40:13,600
als we willen afdrukken alle namen in de datastructuur.

663
00:40:13,600 --> 00:40:15,850
We gaan iets uiteindelijk doen met deze gegevens.

664
00:40:15,850 --> 00:40:20,810
Dus nu hebben we soort van genaaid Alice, die nu niet meer waar ze hoort te zijn.

665
00:40:20,810 --> 00:40:23,880
Ook is Bob, noch is Charlie.

666
00:40:23,880 --> 00:40:26,060
Dus misschien is dit niet zo'n goed idee.

667
00:40:26,060 --> 00:40:28,830
Maar inderdaad, dit is een optie. We kunnen verschuiven iedereen neer,

668
00:40:28,830 --> 00:40:32,240
of ach, Anita laat kwam om het spel, waarom we niet zomaar Anita

669
00:40:32,240 --> 00:40:35,870
niet hier, niet hier, niet hier, laten we haar er een beetje lager in de lijst.

670
00:40:35,870 --> 00:40:38,680
Maar dan het probleem weer begint te decentraliseren.

671
00:40:38,680 --> 00:40:41,630
Je zou direct in staat zijn om Alice te vinden, op basis van haar voornaam.

672
00:40:41,630 --> 00:40:44,320
En Bob direct, en Charlie. Maar dan moet je op zoek naar Anita,

673
00:40:44,320 --> 00:40:46,360
en je ziet, hmm, Alice in de weg.

674
00:40:46,360 --> 00:40:48,770
Nou, laat me controleren hieronder Alice. Bob is niet Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie is niet Anita. O, er is Anita.

676
00:40:51,850 --> 00:40:54,720
En als je blijft die trein van de logica helemaal,

677
00:40:54,720 --> 00:41:00,690
wat is het worst-case looptijd van het vinden of het inbrengen van Anita in deze nieuwe datastructuur?

678
00:41:00,690 --> 00:41:03,280
Het is O (n), toch?

679
00:41:03,280 --> 00:41:06,280
Omdat in het ergste geval, er is Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
helemaal naar beneden om iemand met de naam "Y", dus er is maar een plek over.

681
00:41:10,150 --> 00:41:13,950
Gelukkig, we hebben geen een zogenaamde "Z", dus we Anita helemaal onderaan.

682
00:41:13,950 --> 00:41:16,040
>> We hebben niet echt dat probleem opgelost.

683
00:41:16,040 --> 00:41:19,890
Dus misschien kunnen we hoeven deze derde dimensie te introduceren.

684
00:41:19,890 --> 00:41:22,230
En het blijkt, als we introduceren deze derde dimensie,

685
00:41:22,230 --> 00:41:25,240
we kunnen niet perfect doen, maar de Heilige Graal zal krijgen

686
00:41:25,240 --> 00:41:28,370
constant-time inbrengen en dynamische inserties zodat

687
00:41:28,370 --> 00:41:30,960
we hoeven niet te hard-code een array van grootte 26.

688
00:41:30,960 --> 00:41:34,400
We kunnen invoegen zoveel namen als we willen, maar laten we hier nemen onze 5-minuten pauze

689
00:41:34,400 --> 00:41:38,790
en doe dat goed.

690
00:41:38,790 --> 00:41:46,020
Oke. Ik het verhaal op vrij kunstmatig er

691
00:41:46,020 --> 00:41:48,670
door te kiezen voor Alice en daarna Bob en dan Charlie en dan Anita,

692
00:41:48,670 --> 00:41:51,000
wiens naam was duidelijk zou botsen met Alice.

693
00:41:51,000 --> 00:41:54,120
Maar de vraag die we op maandag afgesloten met is gewoon hoe waarschijnlijk is het

694
00:41:54,120 --> 00:41:56,370
die u zou krijgen dit soort botsingen? Met andere woorden,

695
00:41:56,370 --> 00:42:00,490
als we beginnen aan deze tabellen structuur te gebruiken, dat is eigenlijk gewoon een array,

696
00:42:00,490 --> 00:42:02,460
in dit geval van 26 locaties,

697
00:42:02,460 --> 00:42:05,740
wat als onze ingangen in plaats daarvan worden gelijkmatig verdeeld?

698
00:42:05,740 --> 00:42:09,620
Het is niet kunstmatig Alice en Bob en Charlie en David enzovoort alfabetisch,

699
00:42:09,620 --> 00:42:12,380
het is gelijkmatig verdeeld over A tot en met Z.

700
00:42:12,380 --> 00:42:15,220
>> Misschien hebben we gewoon geluk en we gaan niet naar twee A's of twee B's hebben

701
00:42:15,220 --> 00:42:17,640
met een zeer hoge waarschijnlijkheid, maar als iemand opgemerkt,

702
00:42:17,640 --> 00:42:20,730
Als we gegeneraliseerde dit probleem niet 0-25

703
00:42:20,730 --> 00:42:26,060
maar, laten we zeggen, 0 tot en met 364 of 65, vaak het aantal dagen in een typisch jaar,

704
00:42:26,060 --> 00:42:31,170
en stelde de vraag: "Wat is de kans dat twee van ons in deze kamer op dezelfde dag jarig zijn?"

705
00:42:31,170 --> 00:42:34,600
Met andere woorden, wat is de kans dat twee van ons een naam beginnend met A hebben?

706
00:42:34,600 --> 00:42:37,190
Het soort vraag is hetzelfde, maar deze adresruimte,

707
00:42:37,190 --> 00:42:39,940
deze zoekruimte, is groter in het geval van verjaardagen,

708
00:42:39,940 --> 00:42:42,820
want we hebben zo veel meer dagen in het jaar dan letters in het alfabet.

709
00:42:42,820 --> 00:42:44,910
Wat is de kans op een botsing?

710
00:42:44,910 --> 00:42:48,410
Nou, we kunnen denken dat dit door het uitzoeken van de wiskunde de tegenovergestelde manier.

711
00:42:48,410 --> 00:42:50,580
Wat is de kans dat er geen botsingen?

712
00:42:50,580 --> 00:42:53,970
Nou, deze uitdrukking hier zegt dat wat is de kans

713
00:42:53,970 --> 00:42:58,770
als er maar een persoon in deze kamer, dat ze een unieke verjaardag hebben?

714
00:42:58,770 --> 00:43:01,190
Het is 100%. Want als er maar een persoon in de kamer,

715
00:43:01,190 --> 00:43:03,940
zijn of haar verjaardag kan elk van de 365 dagen worden uit van het jaar.

716
00:43:03,940 --> 00:43:08,650
Dus 365/365 opties geeft me een waarde van 1.

717
00:43:08,650 --> 00:43:11,250
Dus de kans in kwestie op dit moment is slechts 1.

718
00:43:11,250 --> 00:43:13,270
Maar als er een tweede persoon in de kamer,

719
00:43:13,270 --> 00:43:16,490
wat is de kans dat hun verjaardag anders is?

720
00:43:16,490 --> 00:43:20,680
Er is maar 364 mogelijk dagen, het negeren van schrikkeljaren,

721
00:43:20,680 --> 00:43:23,580
voor hun verjaardag niet te botsen met de andere personen.

722
00:43:23,580 --> 00:43:31,920
Dus 364/365. Indien een derde komt, is 363/365, enzovoort.

723
00:43:31,920 --> 00:43:35,790
Dus we blijven vermenigvuldigen samen deze fracties, die worden steeds kleiner en kleiner,

724
00:43:35,790 --> 00:43:40,720
om erachter te komen wat is de kans dat wij allemaal uniek verjaardagen hebben?

725
00:43:40,720 --> 00:43:43,570
Maar dan kunnen we natuurlijk gewoon dat antwoord en draai het rond

726
00:43:43,570 --> 00:43:47,210
en doe 1 minus dat allemaal, een uitdrukking zullen we uiteindelijk wel

727
00:43:47,210 --> 00:43:51,250
als je nog op de achterkant van je wiskunde boeken, het ziet er een beetje zoiets als dit,

728
00:43:51,250 --> 00:43:54,590
die veel gemakkelijker grafisch uitgelegd.

729
00:43:54,590 --> 00:43:57,820
En deze grafiek heeft hier de x-as het aantal verjaardagen

730
00:43:57,820 --> 00:44:02,030
of aantal mensen met verjaardagen en op de y-as is de kans op een match.

731
00:44:02,030 --> 00:44:06,060
En wat dit zegt is dat als je, laten we zeggen, zelfs,,

732
00:44:06,060 --> 00:44:10,860
laten we kiezen voor iets als 22, 23.

733
00:44:10,860 --> 00:44:13,160
Als er 22 of 23 mensen in de kamer,

734
00:44:13,160 --> 00:44:17,100
de kans dat twee van die heel weinig mensen gaan op dezelfde dag jarig zijn

735
00:44:17,100 --> 00:44:19,560
is eigenlijk super hoog, combinatorieel.

736
00:44:19,560 --> 00:44:23,450
50% kans dat in een klas van slechts 22 mensen, een seminar, praktisch,

737
00:44:23,450 --> 00:44:25,790
2 van die mensen gaan op dezelfde dag jarig zijn.

738
00:44:25,790 --> 00:44:28,520
Omdat er zoveel manieren waarop u kunt op dezelfde dag jarig zijn.

739
00:44:28,520 --> 00:44:31,110
Erger nog, als je kijkt naar de rechterkant van de grafiek,

740
00:44:31,110 --> 00:44:34,040
tegen de tijd dat je een klasse met 58 studenten in het,

741
00:44:34,040 --> 00:44:39,270
de waarschijnlijkheid van 2 mensen die een verjaardag is super, super hoog, bijna 100%.

742
00:44:39,270 --> 00:44:41,880
Nu, dat is een soort van een leuk weetje over het echte leven.

743
00:44:41,880 --> 00:44:45,850
>> Maar de gevolgen, nu, voor datastructuren en het opslaan van informatie

744
00:44:45,850 --> 00:44:51,100
betekent dat gewoon aangenomen dat je een mooie, schone, gelijkmatige verdeling van de gegevens

745
00:44:51,100 --> 00:44:53,650
en je hebt een groot genoeg array een heleboel dingen te passen

746
00:44:53,650 --> 00:44:59,360
betekent niet dat je gaat om mensen op unieke locaties.

747
00:44:59,360 --> 00:45:03,810
Je zult botsingen hebben. Dus dit idee van hashing, zoals dat heet,

748
00:45:03,810 --> 00:45:07,450
het nemen van een ingang als "Alice" en masseren op een bepaalde manier

749
00:45:07,450 --> 00:45:10,190
en dan om terug een antwoord als 0 of 1 of 2.

750
00:45:10,190 --> 00:45:17,500
Om terug de output van die functie wordt geteisterd door deze waarschijnlijkheid van een botsing.

751
00:45:17,500 --> 00:45:19,530
Dus hoe kunnen we omgaan met die botsingen?

752
00:45:19,530 --> 00:45:21,940
Nou, op het ene geval, kunnen we het idee dat werd gesuggereerd.

753
00:45:21,940 --> 00:45:25,100
We kunnen gewoon verschuiven iedereen neer, of misschien, een beetje eenvoudiger,

754
00:45:25,100 --> 00:45:29,870
en niet verder iedereen, laten we Anita naar de onderkant van de beschikbare plek.

755
00:45:29,870 --> 00:45:32,810
Dus als Alice is in 0, Bob is in 1, Charlie is in 2,

756
00:45:32,810 --> 00:45:35,260
we zomaar Anita op locatie 3.

757
00:45:35,260 --> 00:45:38,860
En dit is een techniek in data structuren, genaamd lineaire sonderen.

758
00:45:38,860 --> 00:45:41,310
Lineaire omdat je gewoon wandelen deze lijn, en je bent soort van indringende

759
00:45:41,310 --> 00:45:43,640
beschikbare plaatsen in de datastructuur.

760
00:45:43,640 --> 00:45:46,210
Dit natuurlijk delegeert in O (n).

761
00:45:46,210 --> 00:45:49,590
Als de datastructuur is echt vol, er is 25 mensen in het al,

762
00:45:49,590 --> 00:45:54,120
en dan Anita langs komt, belandt ze op wat zou zijn locatie Z, en dat is prima.

763
00:45:54,120 --> 00:45:56,540
Ze past nog steeds, en we kunnen later haar vinden.

764
00:45:56,540 --> 00:46:00,100
>> Maar dit was in strijd is met het doel van het versnellen dingen.

765
00:46:00,100 --> 00:46:02,530
Dus wat als we in plaats daarvan deze derde dimensie ingevoerd?

766
00:46:02,530 --> 00:46:06,400
Deze techniek wordt in het algemeen de aparte chaining, of met kettingen.

767
00:46:06,400 --> 00:46:10,030
En wat een hash-tabel is nu, deze vlakke structuur,

768
00:46:10,030 --> 00:46:13,450
uw tafel is slechts een array van pointers.

769
00:46:13,450 --> 00:46:18,230
Maar wat die pointers wijzen naar is wat denk je?

770
00:46:18,230 --> 00:46:21,970
Een gelinkte lijst. Dus wat als we het beste van beide werelden?

771
00:46:21,970 --> 00:46:26,500
We gebruiken arrays voor de eerste indexen

772
00:46:26,500 --> 00:46:32,070
in de datastructuur zodat we direct naar [0] [1], [30] enzovoort,

773
00:46:32,070 --> 00:46:36,480
maar zo dat we enige flexibiliteit en wij kunnen passen Anita en Alice en Adam

774
00:46:36,480 --> 00:46:38,630
en andere A naam

775
00:46:38,630 --> 00:46:43,470
we in plaats daarvan laat de andere as willekeurig groeien.

776
00:46:43,470 --> 00:46:47,340
En we eindelijk, vanaf maandag, hebben dat expressieve mogelijkheden met gekoppelde lijst.

777
00:46:47,340 --> 00:46:49,530
We kunnen groeien een datastructuur willekeurig.

778
00:46:49,530 --> 00:46:52,450
Als alternatief kunnen we gewoon een grote 2-dimensionale array,

779
00:46:52,450 --> 00:46:57,190
maar dat gaat een vreselijke situatie zijn als een van de rijen in een 2-dimensionale array

780
00:46:57,190 --> 00:47:01,280
niet groot genoeg voor de extra persoon wiens naam toevallig beginnen A.

781
00:47:01,280 --> 00:47:04,200
God verhoede we een groot 2-dimensionale structuur opnieuw toe te wijzen

782
00:47:04,200 --> 00:47:06,600
gewoon omdat er zo veel mensen met de naam A,

783
00:47:06,600 --> 00:47:09,480
vooral als er zo weinig mensen met de naam Z iets.

784
00:47:09,480 --> 00:47:12,170
Het is gewoon gaat om een ​​zeer schaars datastructuur zijn.

785
00:47:12,170 --> 00:47:15,400
Dus het is niet perfect op enige wijze, maar nu hebben we in ieder geval de mogelijkheid

786
00:47:15,400 --> 00:47:19,090
om direct te vinden waar Alice of Anita behoort,

787
00:47:19,090 --> 00:47:21,090
althans wat de verticale as,

788
00:47:21,090 --> 00:47:25,850
en dan hebben we alleen maar te beslissen waar te Anita of Alice zet in deze gelinkte lijst.

789
00:47:25,850 --> 00:47:32,480
Als we niet de zorg over het sorteren dingen, hoe snel we voegen Alice in een structuur als deze?

790
00:47:32,480 --> 00:47:35,370
Het is constante tijd. We index in [0], en als niemand daar,

791
00:47:35,370 --> 00:47:37,550
Alice gaat aan het begin van dat gekoppelde lijst.

792
00:47:37,550 --> 00:47:40,000
Maar dat is niet een groot probleem. Want als Anita komt dan langs

793
00:47:40,000 --> 00:47:42,160
sommige aantal stappen later, Anita waar komt thuis?

794
00:47:42,160 --> 00:47:45,140
Nou ja, [0]. Oop. Alice is al in die gelinkte lijst.

795
00:47:45,140 --> 00:47:47,760
>> Maar als we niet de zorg over het sorteren van deze namen,

796
00:47:47,760 --> 00:47:53,580
we kunnen gewoon bewegen Alice over, insert Anita, maar zelfs dat is constante tijd.

797
00:47:53,580 --> 00:47:57,010
Zelfs als er Alice en Adam en al die andere A namen,

798
00:47:57,010 --> 00:47:59,410
Het is niet echt verschuiven hen fysiek. Waarom?

799
00:47:59,410 --> 00:48:04,090
Omdat we net gedaan hier met gelinkte lijst, wie weet zijn deze knooppunten zijn eigenlijk?

800
00:48:04,090 --> 00:48:06,550
Het enige wat je hoeft te doen is te bewegen het broodkruim.

801
00:48:06,550 --> 00:48:10,930
Verplaats de pijlen rond, je hoeft niet fysiek te verplaatsen van gegevens.

802
00:48:10,930 --> 00:48:14,610
Zodat we voegen Anita, in dat geval direct. Constante tijd.

803
00:48:14,610 --> 00:48:20,250
Dus we hebben constant-time lookup, en constant-time opname van iemand als Anita.

804
00:48:20,250 --> 00:48:22,740
Maar soort te simpel de wereld.

805
00:48:22,740 --> 00:48:28,510
Wat als we later willen Alice te vinden?

806
00:48:28,510 --> 00:48:31,050
Wat als we later willen Alice te vinden?

807
00:48:31,050 --> 00:48:35,690
Hoeveel stappen is dat nog duren?

808
00:48:35,690 --> 00:48:37,850
[Student antwoord, onverstaanbaar]

809
00:48:37,850 --> 00:48:40,950
Precies. Het aantal mensen dat voor Alice in de gelinkte lijst.

810
00:48:40,950 --> 00:48:45,420
Dus het is niet helemaal perfect, omdat onze data structuur, nogmaals, heeft deze verticale toegang

811
00:48:45,420 --> 00:48:50,240
en dan heeft deze gelinkte lijsten opknoping - in feite, laten we het niet maken het een een array.

812
00:48:50,240 --> 00:48:56,020
Het heeft deze gelinkte lijsten opknoping off van het dat ziet er een beetje iets als dit.

813
00:48:56,020 --> 00:48:59,110
Maar het probleem is als Alice en Adam en al die andere A namen

814
00:48:59,110 --> 00:49:01,720
uiteindelijk meer en meer daar,

815
00:49:01,720 --> 00:49:04,810
het vinden van iemand zou kunnen komen, het nemen van een heleboel stappen,

816
00:49:04,810 --> 00:49:06,670
bcause moet je de gelinkte lijst doorlopen,

817
00:49:06,670 --> 00:49:08,090
die een lineaire bewerking.

818
00:49:08,090 --> 00:49:14,270
Dus echt dan de insertie tijd uiteindelijk O (n), waarbij n het aantal elementen in de lijst.

819
00:49:14,270 --> 00:49:21,780
Gedeeld door, laten we willekeurig noemen m, waarbij m het aantal gekoppelde lijsten

820
00:49:21,780 --> 00:49:24,500
dat wij in deze verticale as.

821
00:49:24,500 --> 00:49:27,180
In andere woorden, als we aannemen werkelijk een gelijkmatige verdeling van namen

822
00:49:27,180 --> 00:49:30,150
totaal onrealistisch. Er is uiteraard meer van een aantal brieven dan anderen.

823
00:49:30,150 --> 00:49:32,580
>> Maar als we aannemen voor het moment een uniforme verdeling,

824
00:49:32,580 --> 00:49:37,350
en we hebben n totale mensen, en m totale ketens

825
00:49:37,350 --> 00:49:40,630
ons beschikbaar, dan is de lengte van elk van deze kettingen

826
00:49:40,630 --> 00:49:44,380
vrij eenvoudig zal het totaal n gedeeld door het aantal ketens zijn.

827
00:49:44,380 --> 00:49:48,900
Dus n / m. Maar hier is waar we zijn allemaal wiskundig slim.

828
00:49:48,900 --> 00:49:53,030
m is een constant, omdat er een vast aantal van deze.

829
00:49:53,030 --> 00:49:54,620
Je gaat uw array declareren aan het begin,

830
00:49:54,620 --> 00:49:58,450
en we zijn niet de grootte van het verticale as. Per definitie, blijft die vast.

831
00:49:58,450 --> 00:50:01,220
Het is alleen de horizontale as, om zo te zeggen, dat is aan het veranderen.

832
00:50:01,220 --> 00:50:04,760
Dus technisch is dit een constant. Dus nu, het inbrengen tijd

833
00:50:04,760 --> 00:50:09,700
is vrij veel O (n).

834
00:50:09,700 --> 00:50:12,410
Dus dat voelt niet zo heel veel beter.

835
00:50:12,410 --> 00:50:14,940
Maar wat is de waarheid hier? Nou, al die tijd, weken,

836
00:50:14,940 --> 00:50:20,640
we hebben gezegd O (n ²). O (n), 2 x n ², - n, gedeeld door 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Het is gewoon n ². Maar nu, in dit deel van het semester,

838
00:50:23,580 --> 00:50:25,560
kunnen we beginnen te praten over de echte wereld weer.

839
00:50:25,560 --> 00:50:31,520
En n / m is geheel sneller dan n alleen.

840
00:50:31,520 --> 00:50:35,170
Als je een duizend namen, en je breekt ze in meerdere emmers

841
00:50:35,170 --> 00:50:37,820
zodat u slechts tien namen in elk van deze ketens,

842
00:50:37,820 --> 00:50:41,670
absoluut zoeken tien dingen gaat worden sneller dan een duizend dingen.

843
00:50:41,670 --> 00:50:43,740
En dus een van de komende probleem sets zal je uitdagen

844
00:50:43,740 --> 00:50:46,100
na te denken over precies dat, ook al, ja,

845
00:50:46,100 --> 00:50:49,520
asymptotisch en wiskundig, dit is nog steeds gewoon lineair,

846
00:50:49,520 --> 00:50:51,700
die zuigt in het algemeen wanneer het proberen om dingen te vinden.

847
00:50:51,700 --> 00:50:54,530
In werkelijkheid gaat het om sneller te zijn dan dat

848
00:50:54,530 --> 00:50:56,520
hierdoor deler.

849
00:50:56,520 --> 00:50:58,310
En op dat moment nog weer gaat deze trade-off worden

850
00:50:58,310 --> 00:51:01,390
en dit conflict tussen theorie en werkelijkheid,

851
00:51:01,390 --> 00:51:03,550
en een van de knoppen zal gaan draaien op dit punt in de semester

852
00:51:03,550 --> 00:51:07,510
is van de werkelijkheid een als we soort voorbereiden end semster's,

853
00:51:07,510 --> 00:51:09,280
zoals we introduceren in de wereld van web programmeren,

854
00:51:09,280 --> 00:51:11,530
waar echt, is de prestaties gaat tellen, omdat uw gebruikers gaan

855
00:51:11,530 --> 00:51:14,880
beginnen te voelen en waarderen slecht ontwerp beslissingen.

856
00:51:14,880 --> 00:51:19,950
>> Dus hoe ga je over het implementeren van een gekoppelde - een hash table met 31 elementen?

857
00:51:19,950 --> 00:51:22,600
En het vorige voorbeeld was willekeurig over verjaardagen.

858
00:51:22,600 --> 00:51:26,190
Als iemand een verjaardag op 1 januari of 1 februari zullen we ze in de lege emmer.

859
00:51:26,190 --> 00:51:28,960
Als het 2 januari 2 februari 2 maart zullen we ze in de lege emmer.

860
00:51:28,960 --> 00:51:32,220
Daarom was het 31. Hoe verklaart u een hash table?

861
00:51:32,220 --> 00:51:37,480
Het kan vrij eenvoudig, knooppunt * tafel is mijn willekeurige naam voor het, [31].

862
00:51:37,480 --> 00:51:42,400
Dit geeft me 31 verwijzingen naar knooppunten,

863
00:51:42,400 --> 00:51:45,370
en dat kan ik hebben 31 verwijzingen naar gelinkte lijsten

864
00:51:45,370 --> 00:51:48,800
zelfs als die ketens zijn in eerste instantie NULL.

865
00:51:48,800 --> 00:51:54,860
Wat wil ik zetten als ik wil opslaan "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Nou, we moeten die dingen verpakken in een structuur

867
00:51:57,010 --> 00:52:00,530
omdat we wijzen op Alice Bob te wijzen op Charlie, enzovoort.

868
00:52:00,530 --> 00:52:04,940
We kunnen gewoon niet de namen alleen al, dus ik zou kunnen leiden tot een nieuwe structuur genaamd knooppunt hier.

869
00:52:04,940 --> 00:52:08,310
>> Wat is een echte knoop? Wat is een knooppunt in deze nieuwe gekoppelde lijst?

870
00:52:08,310 --> 00:52:11,840
Het eerste ding, genaamd woord, is voor de naam van de persoon.

871
00:52:11,840 --> 00:52:14,340
LENGTE, vermoedelijk, heeft betrekking op de maximale lengte van de naam van een mens,

872
00:52:14,340 --> 00:52:18,210
wat dat ook is, 20, 30, 40 tekens in gekke hoek gevallen,

873
00:52:18,210 --> 00:52:22,680
en +1 is voor wat? Het is gewoon de extra NULL karakter \ 0.

874
00:52:22,680 --> 00:52:27,410
Dus dit knooppunt inpakken "iets" in van zichzelf,

875
00:52:27,410 --> 00:52:29,640
maar het verklaart ook een pointer genaamd volgende

876
00:52:29,640 --> 00:52:32,580
zodat we kunnen keten Alice aan Bob om Charlie, enzovoort.

877
00:52:32,580 --> 00:52:36,700
Kan NULL zijn, maar hoeft niet per se zo te zijn.

878
00:52:36,700 --> 00:52:40,110
Eventuele vragen over deze hash tables? Ja?

879
00:52:40,110 --> 00:52:46,190
[Student vraagt ​​vraag, onverstaanbaar] Een array - goede vraag.

880
00:52:46,190 --> 00:52:50,120
Waarom is dit char woord in een array in plaats van alleen char *?

881
00:52:50,120 --> 00:52:53,830
In dit enigszins willekeurig voorbeeld, heb ik niet willen hebben hun toevlucht

882
00:52:53,830 --> 00:52:56,190
om malloc voor elk van de oorspronkelijke namen.

883
00:52:56,190 --> 00:52:59,530
Ik wilde een maximale hoeveelheid geheugen die verklaren voor de string

884
00:52:59,530 --> 00:53:06,020
zodat ik kon kopiëren naar de structuur Alice \ 0 en niet te maken hebben met malloc en free en dergelijke.

885
00:53:06,020 --> 00:53:11,710
Maar ik kon dat doen als ik wilde om meer bewust te zijn van de ruimte gebruik. Goede vraag.

886
00:53:11,710 --> 00:53:14,780
Dus laten we proberen weg te generaliseren van deze

887
00:53:14,780 --> 00:53:18,350
en de focus van de rest van vandaag op datastructuren meer in het algemeen

888
00:53:18,350 --> 00:53:21,170
en andere problemen die we kunnen oplossen met behulp van dezelfde grondbeginselen

889
00:53:21,170 --> 00:53:24,590
hoewel de data structuren zelf kunnen verschillen in hun gegevens.

890
00:53:24,590 --> 00:53:27,910
>> Zo blijkt in de informatica, bomen zijn zeer algemeen.

891
00:53:27,910 --> 00:53:29,760
En u kunt denken aan een boom als een soort stamboom,

892
00:53:29,760 --> 00:53:31,830
waar er een aantal wortels, sommige matriarch of patriarch,

893
00:53:31,830 --> 00:53:34,540
oma of opa of eerder terug,

894
00:53:34,540 --> 00:53:38,880
waar doorheen zijn vader en moeder of verschillende broers en zussen of iets dergelijks.

895
00:53:38,880 --> 00:53:42,500
Dus een boomstructuur heeft knooppunten en heeft kinderen

896
00:53:42,500 --> 00:53:45,260
meestal 0 of meer kinderen voor elk knooppunt.

897
00:53:45,260 --> 00:53:47,320
En sommige van het jargon dat u ziet in dit plaatje hier

898
00:53:47,320 --> 00:53:50,630
is een van de kleine kinderen of kleinkinderen aan de randen

899
00:53:50,630 --> 00:53:52,330
die geen pijlen die uitgaan van hen,

900
00:53:52,330 --> 00:53:55,070
dat zijn de zogenaamde bladeren en ieder aan de binnenzijde

901
00:53:55,070 --> 00:53:58,790
is een innerlijke knoop, je kunt het iets in die richting.

902
00:53:58,790 --> 00:54:01,430
Maar deze structuur is vrij normaal. Deze is een beetje arbitrair.

903
00:54:01,430 --> 00:54:04,930
We hebben een kind aan de linkerkant, we hebben drie kinderen aan de rechterkant,

904
00:54:04,930 --> 00:54:06,830
twee kinderen op de links onderaan.

905
00:54:06,830 --> 00:54:10,740
Dus we kunnen hebben verschillende maten bomen, maar als we beginnen om dingen te standaardiseren,

906
00:54:10,740 --> 00:54:15,330
en je zou kunnen herinneren deze uit video Patrick op binair zoeken van een eerdere korte

907
00:54:15,330 --> 00:54:19,490
online, binary search hoeft niet te worden uitgevoerd met een array

908
00:54:19,490 --> 00:54:21,410
of stukjes papier op een schoolbord.

909
00:54:21,410 --> 00:54:25,490
Stel dat je wilde je nummers op te slaan in een meer geavanceerde datastructuur.

910
00:54:25,490 --> 00:54:27,680
Je zou kunnen leiden tot een boom als deze.

911
00:54:27,680 --> 00:54:35,290
Je kan een knooppunt aangegeven in C en knooppunt dat ten minste twee elementen erin.

912
00:54:35,290 --> 00:54:39,470
Een daarvan is het nummer dat u wilt opslaan, en de andere is - nou ja, we moeten nog een.

913
00:54:39,470 --> 00:54:41,540
De andere is de kinderen.

914
00:54:41,540 --> 00:54:45,150
Dus hier is een andere datastructuur. Deze keer wordt een knooppunt gedefinieerd als opslaan van een aantal n

915
00:54:45,150 --> 00:54:49,060
en dan twee pointers, links en rechts kind kind.

916
00:54:49,060 --> 00:54:52,100
En ze zijn niet willekeurig. Wat is wetenswaardigs over deze boom?

917
00:54:52,100 --> 00:55:00,550
>> Wat is het patroon in de manier waarop we hebben gelegd dit uit of hoe Patrick haar bepaalde voorwaarden in zijn video?

918
00:55:00,550 --> 00:55:02,790
Het is een beetje voor de hand dat er een aantal sortering gebeurt hier,

919
00:55:02,790 --> 00:55:04,460
maar wat is het eenvoudige regel? Ja?

920
00:55:04,460 --> 00:55:08,350
[Student antwoord, onverstaanbaar]

921
00:55:08,350 --> 00:55:12,040
Perfect. Als je een blik werpen op deze, zie je de kleine aantallen aan de linkerkant,

922
00:55:12,040 --> 00:55:14,690
grote getallen aan de linkerkant, maar dat geldt voor elk knooppunt.

923
00:55:14,690 --> 00:55:20,370
Voor elk knooppunt de linker kind kleiner dan, en de rechter kind daarvan bedragen.

924
00:55:20,370 --> 00:55:25,210
Wat dit betekent is nu als ik wil deze datastructuur zoeken naar, laten we zeggen, het aantal 44,

925
00:55:25,210 --> 00:55:29,320
Ik moet om te beginnen bij de wortel, want zoals met al deze meer complexe data structuren nu,

926
00:55:29,320 --> 00:55:31,910
we hebben maar een pointer naar een ding, het begin.

927
00:55:31,910 --> 00:55:35,010
En in dit geval, het begin de wortel. Het is niet het linker uiteinde,

928
00:55:35,010 --> 00:55:39,530
het is de wortel van deze structuur. Dus ik zie hier is 55, en ik ben op zoek naar 44.

929
00:55:39,530 --> 00:55:41,430
Welke richting wil ik heen?

930
00:55:41,430 --> 00:55:45,680
Nou, ik wil naar links, want natuurlijk, het recht zal zijn te groot.

931
00:55:45,680 --> 00:55:49,050
Dus hier zien, je bent soort van conceptueel hakken de boom in de helft

932
00:55:49,050 --> 00:55:51,700
omdat je nooit naar beneden naar de rechterkant.

933
00:55:51,700 --> 00:55:55,410
Dus nu ga ik van de 55 naar de 33. Het is te klein van een getal.

934
00:55:55,410 --> 00:56:01,590
Ik ben op zoek naar 44, maar nu weet ik of 44 is in deze boom, ik kan uiteraard naar rechts.

935
00:56:01,590 --> 00:56:04,460
Dus nogmaals, ik ben het snoeien van de boom in de helft.

936
00:56:04,460 --> 00:56:06,780
Het is vrijwel identiek conceptueel aan het telefoonboek.

937
00:56:06,780 --> 00:56:09,510
Het is identiek aan wat we hebben gedaan met de papieren op het bord,

938
00:56:09,510 --> 00:56:13,940
maar het is een meer geavanceerde structuur die ons in staat stelt om daadwerkelijk te doen

939
00:56:13,940 --> 00:56:16,880
deze verdeel en heers door het ontwerp van het algoritme,

940
00:56:16,880 --> 00:56:19,420
en in feite, het doorkruisen van een structuur als deze - whoops.

941
00:56:19,420 --> 00:56:22,870
Verplaatsen van een structuur als deze, waar het maar "deze kant op of ga op die manier,"

942
00:56:22,870 --> 00:56:26,870
betekent al dat code die je geest gebogen op het eerste bij de uitvoering van het in paragraaf

943
00:56:26,870 --> 00:56:31,270
of wandelen door het thuis, voor binaire zoeken, met behulp van recursie of iteratie,

944
00:56:31,270 --> 00:56:35,060
het is een pijn in de nek. Vind de middelste element, dan doe je boven of beneden afronden.

945
00:56:35,060 --> 00:56:39,230
>> Er is een schoonheid om dit, want we kunnen nu weer gebruik maken van recursie,

946
00:56:39,230 --> 00:56:43,760
maar veel schoner. Sterker nog, als je op het nummer 55 en u wilt tot 44 te vinden,

947
00:56:43,760 --> 00:56:48,450
ga je links in dit geval, wat doe je dan? Je loopt precies hetzelfde algoritme.

948
00:56:48,450 --> 00:56:51,560
U controleert de waarde van het knooppunt, dan ga je naar links of rechts.

949
00:56:51,560 --> 00:56:53,670
Dan moet je controleren de waarde van de knoop, ga links of rechts.

950
00:56:53,670 --> 00:56:56,710
Dit is perfect geschikt voor recursie.

951
00:56:56,710 --> 00:57:00,920
Dus ook al in het verleden hebben we gedaan wat vrij willekeurige voorbeelden waarbij recursie

952
00:57:00,920 --> 00:57:03,430
die niet moeten recursieve, met data Werking,

953
00:57:03,430 --> 00:57:07,820
vooral bomen, het is een perfecte toepassing van dit idee van het nemen van een probleem,

954
00:57:07,820 --> 00:57:12,920
krimpen, en vervolgens oplossen hetzelfde type, maar kleiner programma.

955
00:57:12,920 --> 00:57:14,590
>> Dus er is nog een datastructuur die we kunnen introduceren.

956
00:57:14,590 --> 00:57:18,760
Deze is ontworpen op het eerste gezicht om naar te kijken cryptisch, maar deze is geweldig.

957
00:57:18,760 --> 00:57:25,090
Dus dit is een gegevensstructuur genaamd een trie, trie, die is overgenomen van de woorden vinden,

958
00:57:25,090 --> 00:57:30,210
die niet uitgesproken re-try-val, maar dat is wat de wereld noemt deze dingen. Tries. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Het is een boomstructuur van een soort, maar elk van de knooppunten in een trie

960
00:57:35,190 --> 00:57:41,280
lijkt te zijn wat? En dit is een beetje misleidend, want het is een soort van afgekorte.

961
00:57:41,280 --> 00:57:45,960
Maar het lijkt erop dat elk knooppunt in dit trie eigenlijk een array.

962
00:57:45,960 --> 00:57:48,840
En hoewel de auteur van dit diagram is niet aangetoond dat het,

963
00:57:48,840 --> 00:57:54,130
in dit geval trie een datastructuur tot doel in leven te slaan woorden

964
00:57:54,130 --> 00:57:57,330
als A-l-i-c-e of B-o-b.

965
00:57:57,330 --> 00:58:02,480
En de manier waarop deze data stores Alice en Bob en Charlie en Anita enzovoort

966
00:58:02,480 --> 00:58:06,970
wordt gebruikt om een ​​array waarbij Alice slaan in een Trie,

967
00:58:06,970 --> 00:58:09,820
We beginnen bij de root-node die eruit ziet als een array,

968
00:58:09,820 --> 00:58:12,080
en het is geschreven in steno notatie.

969
00:58:12,080 --> 00:58:15,070
De auteur weggelaten abcdefg omdat er geen namen mee.

970
00:58:15,070 --> 00:58:19,150
Ze toonde alleen M en P en T, maar in dit geval,

971
00:58:19,150 --> 00:58:22,780
Laten we uit de buurt van Alice en Bob en Charlie gaan om enkele namen die hier zijn.

972
00:58:22,780 --> 00:58:25,670
Maxwell is eigenlijk in dit schema.

973
00:58:25,670 --> 00:58:29,570
Dus hoe heeft de auteur winkel M-een-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Hij begon bij het hoofdknooppunt en naar [M], dus ongeveer 13, de 13e plaats in het stelsel.

975
00:58:36,990 --> 00:58:40,750
Dan vanaf daar is er een pointer.

976
00:58:40,750 --> 00:58:42,760
Een pointer die naar een andere array.

977
00:58:42,760 --> 00:58:47,880
Van daar de auteur geïndexeerd in die array op locatie A, want er afgebeeld in de linkerbovenhoek,

978
00:58:47,880 --> 00:58:52,250
en dan is hij of zij gevolgd die pointer naar een andere array,

979
00:58:52,250 --> 00:58:55,460
en ging naar de wijzer op locatie X.

980
00:58:55,460 --> 00:58:59,840
Dan in de volgende matrix locatie W, E, L, L, enzovoort,

981
00:58:59,840 --> 00:59:03,090
en tot slot, laten we eigenlijk proberen om een ​​foto te maken aan deze.

982
00:59:03,090 --> 00:59:05,380
Hoe ziet een knooppunt eruit in de code?

983
00:59:05,380 --> 00:59:11,820
Een knooppunt in een trie bevat een array van pointers naar meer knooppunten.

984
00:59:11,820 --> 00:59:16,090
Maar er ook nog een soort van booleaanse waarde, althans in deze implementatie.

985
00:59:16,090 --> 00:59:18,770
Ik ben toevallig noem het is_word. Waarom?

986
00:59:18,770 --> 00:59:22,670
Want als je Maxwell invoegen, je bent niet invoegen

987
00:59:22,670 --> 00:59:25,300
niets in deze gegevensstructuur.

988
00:59:25,300 --> 00:59:27,480
U bent niet schrijft M. U bent niet X. schrijven

989
00:59:27,480 --> 00:59:30,240
Alles wat je aan het doen bent is na pointers.

990
00:59:30,240 --> 00:59:33,360
De wijzer dat M, dan is de pointer die A vertegenwoordigt vertegenwoordigt,

991
00:59:33,360 --> 00:59:36,310
vervolgens de aanwijzer dat X, dan W, E, L, L vertegenwoordigt,

992
00:59:36,310 --> 00:59:41,950
maar wat je moet doen op het einde is een soort van gaan, controleren, bereikte ik deze locatie.

993
00:59:41,950 --> 00:59:45,560
Er was een woord dat hier eindigt in de datastructuur.

994
00:59:45,560 --> 00:59:48,190
>> Dus wat een trie is echt gevuld met en de auteur koos ervoor om te vertegenwoordigen

995
00:59:48,190 --> 00:59:51,880
deze eindstations met driehoekjes.

996
00:59:51,880 --> 00:59:56,470
Dit betekent alleen dat het feit dat dit driehoek hier is, deze boolean waarde true

997
00:59:56,470 --> 00:59:59,200
betekent dat als je gaat achteruit in de boom,

998
00:59:59,200 --> 01:00:02,420
dat betekent dat een woord met de naam Maxwell is in deze.

999
01:00:02,420 --> 01:00:04,870
Maar het woord foo bijvoorbeeld

1000
01:00:04,870 --> 01:00:07,970
is niet in de boom, want als ik beginnen bij de root node hier boven,

1001
01:00:07,970 --> 01:00:14,030
Er is geen f aanwijzer, geen o wijzer, geen o pointer. Foo is niet een naam in dit woordenboek.

1002
01:00:14,030 --> 01:00:22,460
Maar daarentegen turing, t-u-r-i-n-g. Nogmaals, ik heb niet op te slaan t of u of r of i of n of g.

1003
01:00:22,460 --> 01:00:29,820
Maar ik heb op te slaan in deze datastructuur een waarde van ware weg hier beneden in deze node - in de boom

1004
01:00:29,820 --> 01:00:33,030
door het instellen van deze boolean waarde van is_word op true.

1005
01:00:33,030 --> 01:00:35,740
Dus een trie is een soort van deze zeer interessante meta-structuur,

1006
01:00:35,740 --> 01:00:39,810
waar je niet echt het opslaan van de woorden zelf voor dit soort woordenboek.

1007
01:00:39,810 --> 01:00:45,100
Voor alle duidelijkheid, je bent gewoon opslaan ja of nee, er is een woord dat hier eindigt.

1008
01:00:45,100 --> 01:00:46,430
>> Nu, wat is de implicatie?

1009
01:00:46,430 --> 01:00:51,120
Als je 150.000 woorden in een woordenboek dat u probeert op te slaan in het geheugen

1010
01:00:51,120 --> 01:00:53,400
met behulp van iets als een gekoppelde lijst,

1011
01:00:53,400 --> 01:00:56,870
je gaat tot 150.000 knooppunten in uw gekoppelde lijst hebben.

1012
01:00:56,870 --> 01:01:00,250
En het vinden van een van die woorden alfabetisch kon nemen O (n) tijd.

1013
01:01:00,250 --> 01:01:04,370
Lineaire tijd. Maar in het geval van een trie,

1014
01:01:04,370 --> 01:01:09,210
wat is de looptijd van het vinden van een woord?

1015
01:01:09,210 --> 01:01:17,390
Het blijkt de schoonheid hier is dat zelfs als je 149.999 woorden reeds in dit woordenboek,

1016
01:01:17,390 --> 01:01:20,170
zoals die met deze gegevensstructuur,

1017
01:01:20,170 --> 01:01:25,560
hoeveel tijd is er nodig om te vinden of plaats een persoon meer in dat, net als Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Nou, het is slechts 5, misschien 6 stappen voor de afsluitende karakter.

1019
01:01:30,640 --> 01:01:32,880
Omdat de presense andere namen in de structuur

1020
01:01:32,880 --> 01:01:35,340
niet in de weg van het invoegen van Alice.

1021
01:01:35,340 --> 01:01:39,640
Bovendien, het vinden van Alice zodra er 150.000 woorden in dit woordenboek

1022
01:01:39,640 --> 01:01:41,960
niet in de weg van het vinden van Alice helemaal niet,

1023
01:01:41,960 --> 01:01:46,880
omdat Alice is. . . . . hier, want ik vond een booleaanse waarde.

1024
01:01:46,880 --> 01:01:50,920
En als er geen boolean waar is, dan Alice niet in deze gegevensstructuur van woorden.

1025
01:01:50,920 --> 01:01:56,220
Met andere woorden, de looptijd van het vinden dingen en plaatsen dingen in deze nieuwe

1026
01:01:56,220 --> 01:02:01,920
datastructuur van trie is O van - het is niet n.

1027
01:02:01,920 --> 01:02:05,730
Omdat de presense van 150.000 mensen heeft geen effect op Alice lijkt.

1028
01:02:05,730 --> 01:02:11,560
Dus laten we noemen het k, waarbij k de maximale lengte van een woord in het Engels

1029
01:02:11,560 --> 01:02:14,050
die typisch niet meer dan 20 iets tekens.

1030
01:02:14,050 --> 01:02:17,940
Dus k een constante. Dus de Heilige Graal lijken we nu hebben gevonden

1031
01:02:17,940 --> 01:02:26,000
is dat van een trie, constante tijd voor inserts, voor lookups, voor verwijderingen.

1032
01:02:26,000 --> 01:02:29,170
Omdat het aantal zaken reeds in de structuur,

1033
01:02:29,170 --> 01:02:32,600
die niet eens fysiek aanwezig. Nogmaals, ze zijn gewoon soort van afgevinkt, ja of nee,

1034
01:02:32,600 --> 01:02:35,050
heeft geen invloed op de toekomstige looptijd.

1035
01:02:35,050 --> 01:02:37,940
>> Maar er moet toch een addertje onder het gras, anders zouden we niet hebben zoveel tijd verspild

1036
01:02:37,940 --> 01:02:41,460
op al deze andere gegevens structuren alleen maar om eindelijk het geheim een ​​dat is geweldig.

1037
01:02:41,460 --> 01:02:46,410
Dus welke prijs betalen we dit grootheid hier te bereiken? Ruimte.

1038
01:02:46,410 --> 01:02:49,010
Dit ding is enorm. En de reden dat de auteur

1039
01:02:49,010 --> 01:02:52,400
hier niet aanwezig is, merken dat al deze dingen die eruit zien als arrays,

1040
01:02:52,400 --> 01:02:55,400
hij niet de aandacht van de rest van de boom, de rest van de trie,

1041
01:02:55,400 --> 01:02:58,060
omdat ze gewoon niet relevant voor het verhaal.

1042
01:02:58,060 --> 01:03:01,870
Maar al deze knooppunten zijn super breed, en elke node in de boom neemt

1043
01:03:01,870 --> 01:03:07,780
26 of eigenlijk, kan 27 tekens zijn, omdat in dit geval was ik ook ruimte voor de apostrof

1044
01:03:07,780 --> 01:03:09,980
zodat we konden hebben apostrophized woorden.

1045
01:03:09,980 --> 01:03:14,450
In dit geval zijn grote arrays. Dus ook al zijn ze niet picutured,

1046
01:03:14,450 --> 01:03:18,190
Dit neemt een enorme hoeveelheid RAM-geheugen.

1047
01:03:18,190 --> 01:03:20,670
Welke zou wel goed, especilly in de moderne hardware,

1048
01:03:20,670 --> 01:03:25,650
maar dat is de afweging. We krijgen minder tijd door het uitgeven van meer ruimte.

1049
01:03:25,650 --> 01:03:28,580
Dus waar is dit allemaal?

1050
01:03:28,580 --> 01:03:32,640
Nou, laten we het doen - laten we hier zien.

1051
01:03:32,640 --> 01:03:39,510
Laten we een sprong naar deze man hier.

1052
01:03:39,510 --> 01:03:43,450
>> Geloof het of niet, zo leuk als C is al geruime tijd,

1053
01:03:43,450 --> 01:03:48,130
we het bereiken van het punt in het semester waar is het tijd om de overgang naar dingen meer modern.

1054
01:03:48,130 --> 01:03:50,950
Dingen op een hoger niveau. En hoewel voor de komende paar weken

1055
01:03:50,950 --> 01:03:54,580
we nog steeds om ons onder te dompelen in de wereld van de wijzers en geheugenbeheer

1056
01:03:54,580 --> 01:03:57,210
om dat comfort waarmee we dan bouwen aan de slag,

1057
01:03:57,210 --> 01:04:01,270
het eindspel is uiteindelijk ironisch te introduceren, en niet deze taal.

1058
01:04:01,270 --> 01:04:03,330
We zullen, door te brengen als 10 minuten praten over HTML.

1059
01:04:03,330 --> 01:04:05,950
Alle HTML is een opmaaktaal, en wat een opmaaktaal is

1060
01:04:05,950 --> 01:04:10,220
is deze reeks open beugels en gesloten beugels die zeggen 'maken dit vet'

1061
01:04:10,220 --> 01:04:12,000
'Maken deze cursief', 'maken deze gecentreerd.'

1062
01:04:12,000 --> 01:04:14,250
Het is niet zo intellectueel interessant, maar het is super handig.

1063
01:04:14,250 --> 01:04:16,650
En het is zeker alomtegenwoordig deze dagen.

1064
01:04:16,650 --> 01:04:19,450
Maar is wat krachtig over de wereld van HTML, en web programmeren meer in het algemeen,

1065
01:04:19,450 --> 01:04:25,910
is het bouwen van dynamische dingen, het schrijven van code in talen als PHP of Python of Ruby of Java of C #.

1066
01:04:25,910 --> 01:04:30,360
Echt, wat de taal van uw keuze is, en het genereren van HTML dynamisch.

1067
01:04:30,360 --> 01:04:32,960
Het genereren van iets genaamd CSS dynamisch.

1068
01:04:32,960 --> 01:04:35,810
Cascading style sheets, die ook over esthetiek.

1069
01:04:35,810 --> 01:04:41,360
En dus zelfs al, vandaag, als ik naar sommige website zoals de bekende Google.com,

1070
01:04:41,360 --> 01:04:46,100
en ik ga te bekijken, ontwikkelaar, brontekst bekijken, die misschien heb je eerder gedaan,

1071
01:04:46,100 --> 01:04:49,800
maar gaat om de bron te bekijken, dit spul ziet er waarschijnlijk vrij cryptisch.

1072
01:04:49,800 --> 01:04:55,320
Maar dit is de onderliggende code die Google.com implementeert.

1073
01:04:55,320 --> 01:04:57,940
Aan de voorkant. En eigenlijk alles is pluizige esthetiek spul.

1074
01:04:57,940 --> 01:05:01,740
Dit is CSS hier. Als ik blijf scrollen naar beneden zullen we nog wat gekleurde spul.

1075
01:05:01,740 --> 01:05:06,890
Dit is HTML. Google's code ziet eruit als een puinhoop, maar als ik echt open te stellen een ander venster,

1076
01:05:06,890 --> 01:05:09,380
we zien wat structuur daarvan.

1077
01:05:09,380 --> 01:05:12,640
Als ik open dit op, hier op te merken, is het een beetje beter leesbaar.

1078
01:05:12,640 --> 01:05:16,850
We gaan het duurde niet lang zien deze tag, [woord] is een tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, hoofd, lichaam, div, script, tekstgebied, spanwijdte, gecentreerd, div.

1080
01:05:23,520 --> 01:05:26,770
En dit is ook sorteren van cryptische uitziende op het eerste gezicht,

1081
01:05:26,770 --> 01:05:30,890
maar al deze puinhoop volgt bepaalde patronen, en herhaalbare patronen,

1082
01:05:30,890 --> 01:05:33,850
dus dat als we eenmaal de basis naar beneden, zult u in staat om code zoals dit te schrijven

1083
01:05:33,850 --> 01:05:37,550
en dan manipuleren code zoals deze met behulp van nog een andere taal, genaamd JavaScript.

1084
01:05:37,550 --> 01:05:40,440
En JavaScript is een taal die binnen loopt van een browser

1085
01:05:40,440 --> 01:05:44,380
vandaag aan dat we gebruiken op Harvard cursussen, voor de cursus shopping tool die gebruik maakt van Google maps

1086
01:05:44,380 --> 01:05:48,660
om u een hele hoop van dynamiek, Facebook geeft u te laten zien instant statusupdates,

1087
01:05:48,660 --> 01:05:51,430
Twitter gebruikt het om te laten zien tweets direct.

1088
01:05:51,430 --> 01:05:53,820
Dit alles zullen we beginnen om ons te verdiepen in

1089
01:05:53,820 --> 01:05:57,190
Maar om daar te komen, moeten we een beetje iets over het internet te begrijpen.

1090
01:05:57,190 --> 01:06:01,130
Deze clip is hier slechts een minuut lang, en laten we aannemen dat voor nu is dit, in feite,

1091
01:06:01,130 --> 01:06:08,380
hoe het internet werkt als een teaser voor wat er gaat komen. Ik geef je 'Strijders van het net. "

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow koor muziek ♫]

1093
01:06:14,720 --> 01:06:20,450
[Mannelijk verteller] Hij kwam met een boodschap.

1094
01:06:20,450 --> 01:06:23,770
Met een protocol al zijn eigen.

1095
01:06:23,770 --> 01:06:37,270
[♫ Snellere elektronische muziek ♫]

1096
01:06:37,270 --> 01:06:41,330
Hij kwam naar een wereld van firewalls, routers onverschillig,

1097
01:06:41,330 --> 01:06:45,690
en gevaren veel erger dan de dood.

1098
01:06:45,690 --> 01:06:55,400
Hij is snel. Hij is sterk. Hij is TCP / IP, en hij heeft uw adres.

1099
01:06:55,400 --> 01:06:59,250
Strijders van het Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Volgende week, dan. The Internet. Web programmering. Dit is CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]