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 Universiteit]

3
00:00:04,160 --> 00:00:08,720
[Hierdie is CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Dit is CS50, en dit is die einde van week 6.

5
00:00:12,970 --> 00:00:17,970
So CS50x, een van Harvard se eerste kursusse wat betrokke is in die EDX inisiatief

6
00:00:17,970 --> 00:00:20,590
inderdaad debut die afgelope Maandag.

7
00:00:20,590 --> 00:00:23,460
As jy wil graag 'n kykie te kry van wat ander op die Internet

8
00:00:23,460 --> 00:00:27,180
nou die volgende saam met, kan jou kop tot x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Dit sal u na die toepaslike plek op edx.org,

10
00:00:30,350 --> 00:00:34,160
wat was waar hierdie en ander kursusse van MIT en Berkeley nou leef.

11
00:00:34,160 --> 00:00:38,140
Jy sal het om aan te meld vir 'n rekening, sal jy vind dat die materiaal grotendeels dieselfde

12
00:00:38,140 --> 00:00:42,170
as jy het hierdie semester, hoewel 'n paar weke vertraag, as ons alles gereed te kry.

13
00:00:42,170 --> 00:00:46,930
Maar wat studente in CS50x sal nou sien is 'n koppelvlak hou van hierdie een.

14
00:00:46,930 --> 00:00:50,040
Dit, byvoorbeeld, is Zamyla die leiding van die walk through vir die gestelde probleem 0.

15
00:00:50,040 --> 00:00:54,230
Aan te meld in te edx.org, 'n CS50x student sien die soort van dinge

16
00:00:54,230 --> 00:00:57,170
jy sou verwag om te sien in 'n kursus: die lesing vir die Maandag,

17
00:00:57,170 --> 00:01:01,650
lesing vir Woensdag, verskeie kortbroek, die probleem stelle, die ipv, PDFs.

18
00:01:01,650 --> 00:01:04,459
Verder, as jy hier sien, masjien vertalings

19
00:01:04,459 --> 00:01:08,390
van die Engelse transkripsies in Sjinees, Japannees, Spaans, Italiaans,

20
00:01:08,390 --> 00:01:12,810
en 'n hele klomp van die ander tale wat sal sekerlik onvolmaakte

21
00:01:12,810 --> 00:01:15,840
soos ons rol dit uit programmaties met iets genoem 'n 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
wat ons toelaat om Engels aan die ander tale te omskep.

24
00:01:21,360 --> 00:01:24,100
Maar te danke aan die wonderlike gees van 'n paar honderd plus vrywilligers,

25
00:01:24,100 --> 00:01:26,940
random mense op die internet wat het vriendelik aangebied om betrokke te raak

26
00:01:26,940 --> 00:01:30,180
in hierdie projek, sal ons geleidelik die verbetering van die gehalte van daardie vertalings

27
00:01:30,180 --> 00:01:35,790
deur mense korrigeer die foute wat ons rekenaars het.

28
00:01:35,790 --> 00:01:42,330
>> So dit blyk uit ons het 'n paar meer studente toon op Maandag as wat ons aanvanklik verwag.

29
00:01:42,330 --> 00:01:48,980
In werklikheid, nou CS50x het 100.000 mense saam by die huis.

30
00:01:48,980 --> 00:01:54,430
So besef jy is alles deel van hierdie eerste klas van die maak van hierdie kursus in rekenaarwetenskap

31
00:01:54,430 --> 00:01:57,370
onderwys meer in die algemeen, meer in die algemeen, toeganklik.

32
00:01:57,370 --> 00:02:00,130
En die werklikheid is nou, met 'n paar van hierdie massiewe online kursusse,

33
00:02:00,130 --> 00:02:04,070
Hulle begin almal met hierdie baie hoë getalle, maar dit lyk asof ons hier gedoen het.

34
00:02:04,070 --> 00:02:08,759
Maar die doel, uiteindelik, vir CS50x is regtig soveel mense as moontlik na die eindstreep te kry.

35
00:02:08,759 --> 00:02:12,000
Deur ontwerp, is CS50x aangebied gaan word van die afgelope Maandag

36
00:02:12,000 --> 00:02:17,430
al die pad deur April 15, 2013, sodat mense wat skool verpligtinge elders,

37
00:02:17,430 --> 00:02:20,990
werk, familie, ander konflikte en dies meer, het 'n bietjie meer buigsaamheid

38
00:02:20,990 --> 00:02:23,640
wat om te duik in hierdie kursus, wat is dit voldoende om te sê,

39
00:02:23,640 --> 00:02:30,540
is baie ambisieus as net oor die verloop van net drie maande in 'n gewone semester gedoen.

40
00:02:30,540 --> 00:02:34,190
Maar hierdie studente sal aanpak dieselfde probleem stelle, die lees van die dieselfde inhoud,

41
00:02:34,190 --> 00:02:36,350
met toegang tot die dieselfde kortbroek en dies meer.

42
00:02:36,350 --> 00:02:38,990
So besef dat ons almal regtig in hierdie saam.

43
00:02:38,990 --> 00:02:42,360
En een van die einde doelwitte van CS50x is nie net soveel mense te kry

44
00:02:42,360 --> 00:02:45,720
na die eindstreep en gee hulle hierdie nuutgevonde begrip van rekenaarwetenskap

45
00:02:45,720 --> 00:02:49,000
en programmering, maar ook vir hulle het hierdie gedeelde ervaring.

46
00:02:49,000 --> 00:02:52,010
Een van die kenmerkende eienskappe van 50 op die kampus, ons hoop,

47
00:02:52,010 --> 00:02:56,260
is hierdie soort van gemeenskaplike ervaring, soms vir 'n beter of vir slegter,

48
00:02:56,260 --> 00:02:59,480
maar met hierdie mense om te draai na links en na regs,

49
00:02:59,480 --> 00:03:01,830
en kantoorure en die hackathon en die billike.

50
00:03:01,830 --> 00:03:04,560
Dit is 'n bietjie moeiliker om dit te doen in persoon met mense aanlyn,

51
00:03:04,560 --> 00:03:10,580
maar CS50x sal sluit in April met die eerste ooit CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
wat sal 'n aanlyn-aanpassing van ons idee van die billike

53
00:03:13,630 --> 00:03:18,250
waar duisende studente sal almal genooi word om te dien 'n 1 - 2-minute video,

54
00:03:18,250 --> 00:03:22,480
óf 'n screencast van hul finale projek of video van hulle waai hallo

55
00:03:22,480 --> 00:03:24,490
en praat oor hul projek en demoing dit,

56
00:03:24,490 --> 00:03:27,610
baie soos jou voorgangers hier gedoen het op die kampus in die billike,

57
00:03:27,610 --> 00:03:31,400
deur semester se einde, sodat die hoop is 'n internasionale tentoonstelling te hê

58
00:03:31,400 --> 00:03:37,080
van die CS50x studente se finale projekte, baie soos dié wat op jou wag hierdie Desember hier op die kampus.

59
00:03:37,080 --> 00:03:39,680
Sodat meer op wat in die komende maande.

60
00:03:39,680 --> 00:03:43,640
>> Met 100,000 studente, al is, kom 'n behoefte vir 'n paar KA.

61
00:03:43,640 --> 00:03:47,590
Gegewe dat julle die roete brandende hier en neem CS50

62
00:03:47,590 --> 00:03:51,630
n paar weke in die hand van hierdie materiaal se vrylating aan die mense op EDX,

63
00:03:51,630 --> 00:03:55,330
besef ons wil graag soveel as moontlik van ons eie studente te betrek by hierdie inisiatief,

64
00:03:55,330 --> 00:03:58,720
beide gedurende die semester sowel as hierdie winter en die komende lente.

65
00:03:58,720 --> 00:04:01,620
So as jy wil om betrokke te raak in CS50x,

66
00:04:01,620 --> 00:04:07,450
veral by in op CS50x Bespreek, die EDX weergawe van CS50 Bespreek,

67
00:04:07,450 --> 00:04:10,140
wat baie van julle het al met behulp op die kampus, die aanlyn-bord,

68
00:04:10,140 --> 00:04:13,040
doen asseblief kop tot die URL, laat ons weet wie jy is,

69
00:04:13,040 --> 00:04:16,450
want ons wil graag op te bou 'n span van studente en personeel en fakulteit sowel

70
00:04:16,450 --> 00:04:19,630
op die kampus wat net speel saam en help.

71
00:04:19,630 --> 00:04:21,720
En wanneer hulle 'n vraag wat aan hulle bekend is,

72
00:04:21,720 --> 00:04:25,320
jy hoor 'n student 'n bug rapporteer iewers daar buite in 'n land op die Internet,

73
00:04:25,320 --> 00:04:27,450
en dat die ringe 'n klokkie omdat jy ook dat dieselfde probleem gehad het

74
00:04:27,450 --> 00:04:32,620
in jou d-saal geruime tyd gelede, hopelik dan kan jy slaan in en deel jou eie ervaring.

75
00:04:32,620 --> 00:04:37,300
So asseblief deel te neem as jy wil doen.

76
00:04:37,300 --> 00:04:39,360
>> Rekenaarwetenskap-kursusse by Harvard het 'n bietjie van 'n tradisie,

77
00:04:39,360 --> 00:04:44,730
CS50 onder hulle, met 'n paar klere, sommige klere, dat jy met trots kan dra

78
00:04:44,730 --> 00:04:49,090
semester se einde, sê baie trots dat jy klaar CS50

79
00:04:49,090 --> 00:04:51,830
en het CS50 en dies meer, en ons het altyd probeer om studente te betrek

80
00:04:51,830 --> 00:04:54,540
in hierdie proses so veel as moontlik, waardeur ons nooi,

81
00:04:54,540 --> 00:04:56,900
rondom hierdie tyd van die semester, studente ontwerpe in te dien

82
00:04:56,900 --> 00:04:59,330
met behulp van Photoshop, of wat ookal instrument van keuse wat jy wil gebruik

83
00:04:59,330 --> 00:05:02,330
as jy 'n ontwerper, ontwerpe vir T-hemde en sweetpakke te dien

84
00:05:02,330 --> 00:05:06,100
en sambrele en klein bandanas vir honde wat ons nou het en die wil.

85
00:05:06,100 --> 00:05:09,370
En alles is dan - die wenners van elke jaar word dan uitgestal

86
00:05:09,370 --> 00:05:12,700
op die kursus se webblad by store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Alles is verkoop teen kosprys daar, maar die webwerf net op homself

88
00:05:15,790 --> 00:05:18,330
en mense in staat stel om die kleure en ontwerpe te kies wat hulle wil.

89
00:05:18,330 --> 00:05:20,420
So het ek gedink ons ​​net wil deel sommige van verlede jaar se ontwerpe

90
00:05:20,420 --> 00:05:25,130
wat op die webwerf behalwe hierdie een hier, wat is 'n jaarlikse tradisie.

91
00:05:25,130 --> 00:05:29,410
"Elke dag is ek ma Faultn" was een van die voorleggings verlede jaar,

92
00:05:29,410 --> 00:05:32,290
wat is nog steeds daar beskikbaar vir alumni.

93
00:05:32,290 --> 00:05:35,820
Ons het hierdie een, "CS50, gestig 1989."

94
00:05:35,820 --> 00:05:39,010
Een van ons Bowdens, Rob, was verlede jaar baie gewild.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" gebore is, was hierdie ontwerp ingedien is, onder die top verkopers.

96
00:05:43,480 --> 00:05:49,040
Soos hierdie een hier. Baie mense het "Bowden Fever" volgens die verkope logs.

97
00:05:49,040 --> 00:05:52,650
Besef dat dit kan nou jou ontwerp op die internet.

98
00:05:52,650 --> 00:05:57,510
Meer besonderhede in die volgende probleem op hierdie stel om te kom.

99
00:05:57,510 --> 00:06:00,330
>> Een meer hulpmiddel: jy het 'n paar blootstelling en hopelik nou

100
00:06:00,330 --> 00:06:02,350
sommige hands-on ervaring met GDB

101
00:06:02,350 --> 00:06:04,570
wat is, natuurlik, 'n debugger en laat jou toe om te manipuleer

102
00:06:04,570 --> 00:06:09,500
jou program op 'n redelik lae vlak, te doen wat soort van dinge?

103
00:06:09,500 --> 00:06:13,030
Wat beteken GDB laat jy dit doen?

104
00:06:13,030 --> 00:06:15,030
Ja? Gee my iets. [Student antwoord, onverstaanbaar]

105
00:06:15,030 --> 00:06:18,120
Goed. Stap in die funksie, sodat jy nie net nie hardloop in te tik

106
00:06:18,120 --> 00:06:22,310
en het die program hou deur middel van sy geheel, uit te druk dinge na standaardafvoer.

107
00:06:22,310 --> 00:06:25,190
Inteendeel, kan jy stap vir stap deur dit in lyn deur die lyn, of tik die volgende

108
00:06:25,190 --> 00:06:30,300
reël om te gaan deur 'n lyn deur die lyn of stap om te duik in 'n funksie, gewoonlik een wat jy geskryf het.

109
00:06:30,300 --> 00:06:35,240
Wat anders het GDB Laat wat jy doen? Ja? [Student antwoord, onverstaanbaar]

110
00:06:35,240 --> 00:06:38,100
Druk veranderlikes. So as jy wil 'n bietjie introspeksie te doen binnekant van jou program

111
00:06:38,100 --> 00:06:41,500
sonder om plek te skryf printf state oor die hele plek,

112
00:06:41,500 --> 00:06:44,600
kan jy net druk van 'n veranderlike of vertoon 'n veranderlike.

113
00:06:44,600 --> 00:06:46,710
Wat anders kan jy doen met 'n debugger soos GDB?

114
00:06:46,710 --> 00:06:49,170
[Student antwoord, onverstaanbaar]

115
00:06:49,170 --> 00:06:52,080
Presies. Jy kan stel inspeksiepunte, jy kan breek uitvoering sê

116
00:06:52,080 --> 00:06:54,020
die belangrikste funksie of die foo-funksie.

117
00:06:54,020 --> 00:06:56,800
Jy kan breek uitvoering sê line 123.

118
00:06:56,800 --> 00:06:58,950
En inspeksiepunte is 'n baie kragtige tegniek

119
00:06:58,950 --> 00:07:01,110
want as jy 'n algemene gevoel van waar jou probleem

120
00:07:01,110 --> 00:07:05,360
waarskynlik is, het jy nie tyd om te mors versterking deur middel van die program se geheel.

121
00:07:05,360 --> 00:07:08,250
Jy kan in wese reg daar spring en begin dan tik -

122
00:07:08,250 --> 00:07:10,970
versterk deur dit met stap of langs of iets dergeliks.

123
00:07:10,970 --> 00:07:14,340
Maar die vangs met iets soos GDB is dat dit help jou, die mens,

124
00:07:14,340 --> 00:07:16,940
vind jou probleme en vind jou foute.

125
00:07:16,940 --> 00:07:19,470
Dit beteken nie noodwendig hulle vind so baie vir jou.

126
00:07:19,470 --> 00:07:23,070
>> So het ons die ander dag style50, wat is 'n kort opdrag lyn instrument

127
00:07:23,070 --> 00:07:27,500
wat probeer om jou kode te 'n bietjie meer skoon as jy stiliseren, die mens, kan gedoen word.

128
00:07:27,500 --> 00:07:29,530
Maar dat dit ook is regtig net 'n estetiese ding.

129
00:07:29,530 --> 00:07:34,110
Maar dit blyk daar is hierdie ander instrument genoem Valgrind wat is 'n bietjie meer arcane om te gebruik.

130
00:07:34,110 --> 00:07:36,860
Sy uitset is afgrijselijk kriptiese met die eerste oogopslag.

131
00:07:36,860 --> 00:07:39,420
Maar dit is wonderlik nuttig wees, veral nou dat ons by die deel van die term

132
00:07:39,420 --> 00:07:43,080
waar jy begin malloc en dinamiese geheuetoekenning te gebruik.

133
00:07:43,080 --> 00:07:45,420
Dinge kan regtig, regtig verkeerd vinnig.

134
00:07:45,420 --> 00:07:49,320
Want as jy vergeet om jou geheue te bevry, of jy dereference n NULL pointer,

135
00:07:49,320 --> 00:07:55,770
of jy dereference sommige vullis wyser, wat is tipies die simptoom wat resultate?

136
00:07:55,770 --> 00:07:59,470
Seg skuld. En jy kry hierdie kern lêer van 'n paar kilogrepe of megagrepe

137
00:07:59,470 --> 00:08:02,990
wat verteenwoordig die toestand van jou program se geheue toe dit neergestort het,

138
00:08:02,990 --> 00:08:05,730
maar jou program uiteindelik seg foute, segmentering skuld,

139
00:08:05,730 --> 00:08:08,450
wat beteken dat iets sleg gebeur byna altyd in verband

140
00:08:08,450 --> 00:08:11,750
na 'n geheue-fout wat jy iewers.

141
00:08:11,750 --> 00:08:14,100
So Valgrind help jy dinge soos hierdie.

142
00:08:14,100 --> 00:08:17,720
Dit is 'n instrument wat jy loop, soos GDB, nadat jy jou program saamgestel is,

143
00:08:17,720 --> 00:08:20,330
maar eerder as loop jou program direk, jy hardloop Valgrind

144
00:08:20,330 --> 00:08:23,960
en jy slaag om dit jou program, net soos jy doen met GDB.

145
00:08:23,960 --> 00:08:26,220
Nou, die gebruik, om die beste soort van afvoer,

146
00:08:26,220 --> 00:08:30,410
is 'n bietjie lank, so reg daar bo van die skerm sal jy sien Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"V" beteken feitlik universeel verbose wanneer jy die gebruik van programme op 'n Linux-rekenaar.

148
00:08:35,350 --> 00:08:38,770
So dit beteken spoeg uit meer data as wat jy dalk by verstek.

149
00:08:38,770 --> 00:08:45,510
"- Lek-check: = vol." Dit is net sê tjek vir alle moontlike geheue lekkasies,

150
00:08:45,510 --> 00:08:49,430
foute wat ek kon gemaak het. Dit is ook 'n algemene paradigma met Linux programme.

151
00:08:49,430 --> 00:08:52,710
In die algemeen, as jy 'n command line argument wat is 'n "switch",

152
00:08:52,710 --> 00:08:55,830
wat veronderstel is om die program se gedrag te verander, en dit is 'n enkele brief,

153
00:08:55,830 --> 00:09:00,310
dit is-v, maar as dit is aangeskakel, net deur die ontwerp van die programmeerder,

154
00:09:00,310 --> 00:09:05,150
is 'n volledige woord of reeks van woorde, die command line argument begin met.

155
00:09:05,150 --> 00:09:08,190
Dit is net menslike konvensies, maar jy sal sien dat hulle al hoe meer.

156
00:09:08,190 --> 00:09:12,410
En dan, uiteindelik, "a.out" is die arbitrêre naam vir die program in hierdie spesifieke voorbeeld.

157
00:09:12,410 --> 00:09:14,640
En hier is 'n paar verteenwoordigende uitset.

158
00:09:14,640 --> 00:09:22,890
>> Voordat ons kyk na wat dit kan beteken, laat my oor te gaan na 'n uittreksel van die kode hier.

159
00:09:22,890 --> 00:09:26,390
En laat my skuif na hierdie uit die pad, kom gou,

160
00:09:26,390 --> 00:09:32,120
en laat ons neem 'n blik op memory.c, wat is hierdie kort voorbeeld hier.

161
00:09:32,120 --> 00:09:36,290
Dus, in hierdie program, laat my zoom in op die funksies en vrae.

162
00:09:36,290 --> 00:09:39,430
Ons het 'n funksie hoof wat noem 'n funksie, f,

163
00:09:39,430 --> 00:09:45,590
en dan wat beteken f voortgaan om te doen, in effens tegniese Engels?

164
00:09:45,590 --> 00:09:49,760
Wat beteken f voortgaan om te doen?

165
00:09:49,760 --> 00:09:53,680
Hoe gaan ek sal begin met lyn 20, en die ster se plek maak nie saak nie,

166
00:09:53,680 --> 00:09:56,720
maar ek sal net konsekwent wees hier by die laaste lesing.

167
00:09:56,720 --> 00:09:59,910
Wat is die lyn 20 vir ons kan doen? Op die linkerkant. Ons sal breek dit af verder.

168
00:09:59,910 --> 00:10:02,410
Int * x: wat beteken dit doen?

169
00:10:02,410 --> 00:10:04,940
Okay. Dit is 'n wyser te verklaar, en nou laat ons selfs meer tegniese.

170
00:10:04,940 --> 00:10:10,230
Wat beteken dit, baie konkreet, 'n wyser om te verklaar? Iemand anders?

171
00:10:10,230 --> 00:10:15,050
Ja? [Student antwoord, onverstaanbare te ver.

172
00:10:15,050 --> 00:10:17,060
So jy lees aan die regterkant van die gelykaanteken.

173
00:10:17,060 --> 00:10:20,290
Kom ons fokus net op die linkerkant, net op int * x.

174
00:10:20,290 --> 00:10:24,700
Dit beteken "verklaar" 'n wyser nie, maar laat ons nou duik in dieper na daardie omskrywing.

175
00:10:24,700 --> 00:10:28,330
Wat beteken konkreet, tegnies beteken dit? Ja?

176
00:10:28,330 --> 00:10:31,940
[Student antwoord, onverstaanbaar]

177
00:10:31,940 --> 00:10:35,090
Okay. Dit is die voorbereiding van 'n adres in die geheue te red.

178
00:10:35,090 --> 00:10:40,680
Goed. En laat ons neem dit 'n stap verder, dit is 'n veranderlike verklaar, x, wat is 32 bisse.

179
00:10:40,680 --> 00:10:44,440
En ek weet dit is 32 bisse omdat?

180
00:10:44,440 --> 00:10:47,390
Dit is nie, want dit is 'n int, want dit is 'n wyser in hierdie geval.

181
00:10:47,390 --> 00:10:49,650
Toeval dat dit is een en dieselfde met 'n int,

182
00:10:49,650 --> 00:10:51,970
maar die feit dat daar is die ster is daar beteken dit is 'n wyser

183
00:10:51,970 --> 00:10:57,300
en in die toestel, soos met baie rekenaars, maar nie almal nie, wysers is 32 bisse.

184
00:10:57,300 --> 00:11:01,850
Moet jy dalk op 'n meer moderne hardeware soos die nuutste Macs, die nuutste PC's, 64-bits-pointers,

185
00:11:01,850 --> 00:11:04,160
maar in die toestel, hierdie dinge is 32 bisse.

186
00:11:04,160 --> 00:11:08,380
So ons sal standaardiseer op daardie. Meer konkreet, die storie gaan as volg:

187
00:11:08,380 --> 00:11:10,820
Ons "verklaar" 'n wyser, wat beteken dit?

188
00:11:10,820 --> 00:11:12,810
Ons berei 'n geheue adres te stoor.

189
00:11:12,810 --> 00:11:15,530
Wat beteken dit?

190
00:11:15,530 --> 00:11:19,810
Ons skep 'n veranderlike genaamd x 32 stukkies

191
00:11:19,810 --> 00:11:23,810
wat sal binnekort die stoor van die adres van 'n heelgetal.

192
00:11:23,810 --> 00:11:26,470
En dit is waarskynlik oor so akkuraat as wat ons kan kry.

193
00:11:26,470 --> 00:11:31,810
Dit is goed om vorentoe te beweeg om die wêreld te vereenvoudig en net sê verklaar 'n wyser genoem x.

194
00:11:31,810 --> 00:11:35,380
Verklaar 'n wyser nie, maar besef en verstaan ​​wat werklik aangaan

195
00:11:35,380 --> 00:11:38,490
selfs in net daardie paar karakters.

196
00:11:38,490 --> 00:11:42,040
>> Nou, hierdie een is amper 'n bietjie makliker te maak, selfs al is dit 'n langer uitdrukking.

197
00:11:42,040 --> 00:11:48,160
So, wat is om dit te doen, wat nou uitgelig: "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 ek sal dit daar. Dit is die toekenning van 'n stuk van die geheue vir tien heelgetalle.

200
00:11:58,250 --> 00:12:02,190
En nou, laat ons duik in effens dieper, dit is die toekenning van 'n stuk van die geheue vir tien heelgetalle.

201
00:12:02,190 --> 00:12:05,390
Wat malloc dan weer terug?

202
00:12:05,390 --> 00:12:10,390
Die adres van daardie stuk, of, meer konkreet, die adres van die eerste byte van daardie stuk.

203
00:12:10,390 --> 00:12:14,080
Hoe is ek dan, die programmeerder, om te weet waar daardie stuk van geheue eindig?

204
00:12:14,080 --> 00:12:18,340
Ek weet dat dit is aangrensend. Malloc, per definisie, sal jy 'n aangrensende stuk van die geheue.

205
00:12:18,340 --> 00:12:21,240
Geen gapings in dit. Jy het toegang tot elke greep in daardie stuk,

206
00:12:21,240 --> 00:12:26,760
terug na Terug na, maar hoe weet ek waar die einde van hierdie stuk van die geheue is?

207
00:12:26,760 --> 00:12:28,850
Wanneer jy gebruik malloc? [Student antwoord, onverstaanbaar] Goed.

208
00:12:28,850 --> 00:12:30,670
Jy doen nie. Jy het om te onthou.

209
00:12:30,670 --> 00:12:35,960
Ek het om te onthou wat ek gebruik om die waarde 10, en ek het nie eens lyk dat hier gedoen.

210
00:12:35,960 --> 00:12:41,000
Maar die onus is geheel en al op my. Strlen, wat ons geword het effens afhanklik van snare,

211
00:12:41,000 --> 00:12:45,860
werk net as gevolg van hierdie Konvensie van \ 0

212
00:12:45,860 --> 00:12:48,840
of hierdie spesiale nul karakter, NUL, aan die einde van 'n string.

213
00:12:48,840 --> 00:12:51,740
Dit hou nie net vir arbitrêre stukke van die geheue.

214
00:12:51,740 --> 00:12:58,590
Dit is aan jou. So line 20, dan 'n stuk van die geheue toeken

215
00:12:58,590 --> 00:13:02,590
wat kan stoor tien heelgetalle, en dit slaan die adres van die eerste byte

216
00:13:02,590 --> 00:13:05,610
van daardie deel van die geheue in die veranderlike genaamd x.

217
00:13:05,610 --> 00:13:11,140
Ergo, wat is 'n wyser. So line 21, ongelukkig, was 'n fout.

218
00:13:11,140 --> 00:13:16,110
Maar eers, wat dit doen? Dit sê winkel op plek 10, 0 geïndekseer,

219
00:13:16,110 --> 00:13:19,480
van die stuk van die geheue genoem x die waarde 0.

220
00:13:19,480 --> 00:13:21,510
>> So let op 'n paar van die dinge wat gaan op.

221
00:13:21,510 --> 00:13:25,420
Selfs al is x is 'n wyser, onthou van 'n paar weke gelede

222
00:13:25,420 --> 00:13:29,440
dat jy kan nog steeds gebruik maak van die skikking-styl vierkante hakienotasie.

223
00:13:29,440 --> 00:13:36,180
Want dit is eintlik kort notasie vir die meer kriptiese-looking pointer rekenkunde.

224
00:13:36,180 --> 00:13:40,320
waar ons iets soos hierdie sou doen: Neem die adres x, beweeg 10 plekke oor,

225
00:13:40,320 --> 00:13:44,550
gaan dan is daar na watter adres gestoor op die plek.

226
00:13:44,550 --> 00:13:48,090
Maar eerlik, dit is net gruwelike te lees en kry gemaklik met.

227
00:13:48,090 --> 00:13:52,900
Sodat die wêreld gebruik gewoonlik die vierkantige hakies net omdat dit is soveel meer mens-vriendelike om te lees.

228
00:13:52,900 --> 00:13:55,140
Maar dit is wat regtig gaan op onder die kap;

229
00:13:55,140 --> 00:13:58,190
x is 'n adres wat nie 'n skikking, per se.

230
00:13:58,190 --> 00:14:02,410
So, dit is die stoor van 0 op plek 10 in x.

231
00:14:02,410 --> 00:14:06,120
Hoekom is dit sleg? Ja?

232
00:14:06,120 --> 00:14:17,370
[Student antwoord, onverstaanbaar] Presies.

233
00:14:17,370 --> 00:14:21,100
Ons het slegs toegeken tien ints, maar ons tel van 0 wanneer programmering in C,

234
00:14:21,100 --> 00:14:25,690
sodat jy het toegang tot 0 1 2 3 4 5 6 7 8 9, maar nie meer as 10.

235
00:14:25,690 --> 00:14:30,270
So óf die program gaan seg skuld of dit is nie.

236
00:14:30,270 --> 00:14:32,900
Maar ons het nie regtig weet nie, dit is 'n soort van 'n deterministiese gedrag.

237
00:14:32,900 --> 00:14:35,600
Dit hang af of kry ons gelukkig is.

238
00:14:35,600 --> 00:14:40,650
As dit blyk dat die bedryfstelsel nie omgee as ek gebruik daardie ekstra byte,

239
00:14:40,650 --> 00:14:43,360
selfs al is dit nie dit wat aan my gegee is, kan my program nie crash.

240
00:14:43,360 --> 00:14:46,780
Dit is rou, dit is buggy, maar jy kan nie sien dat die simptoom,

241
00:14:46,780 --> 00:14:48,960
of jy kan sien dit net een keer in 'n rukkie.

242
00:14:48,960 --> 00:14:51,230
Maar die werklikheid is dat die fout is, in werklikheid, is daar.

243
00:14:51,230 --> 00:14:54,320
En dit is regtig problematies as jy geskryf het 'n program wat jy wil korrek te wees,

244
00:14:54,320 --> 00:14:58,840
dat jy verkoop het die program wat mense gebruik dat elke een keer in 'n rukkie ineenstortings

245
00:14:58,840 --> 00:15:02,450
want, natuurlik, dit is nie goed nie. In werklikheid, as jy 'n Android-selfoon of 'n iPhone

246
00:15:02,450 --> 00:15:05,550
en jy dit aflaai apps hierdie dae, as jy ooit gehad het 'n app net ophou,

247
00:15:05,550 --> 00:15:10,040
almal van 'n skielike dit verdwyn, wat is byna altyd die gevolg van 'n paar geheue probleem,

248
00:15:10,040 --> 00:15:12,830
waardeur die programmeerder verfrommeld en be dereferenced 'n wyser

249
00:15:12,830 --> 00:15:18,670
dat hy of sy moet nie, en die gevolg van IOS of Android is om net die dood van die program heeltemal

250
00:15:18,670 --> 00:15:23,080
eerder as risiko undefined gedrag of 'n soort van veiligheid kompromie.

251
00:15:23,080 --> 00:15:25,950
>> Daar is 'n ander fout in hierdie program behalwe hierdie een.

252
00:15:25,950 --> 00:15:30,180
Wat anders het ek screwed up in hierdie program?

253
00:15:30,180 --> 00:15:32,740
Ek het nie geoefen wat ek gepreek het. Ja?

254
00:15:32,740 --> 00:15:34,760
[Student antwoord, onverstaanbaar] Goed.

255
00:15:34,760 --> 00:15:36,880
Ek het nie die geheue bevry. Sodat die reël van die duim

256
00:15:36,880 --> 00:15:43,150
te wees wanneer jy noem malloc, jy moet bel gratis wanneer jy klaar is die gebruik van daardie geheue.

257
00:15:43,150 --> 00:15:45,610
Nou, wil wanneer ek wil die geheue te bevry?

258
00:15:45,610 --> 00:15:49,780
Waarskynlik, met die veronderstelling dat hierdie eerste reël korrek was, sou ek dit wil hê om hier te doen.

259
00:15:49,780 --> 00:15:55,710
Want ek kon nie, byvoorbeeld, doen dit hier neer. Hoekom?

260
00:15:55,710 --> 00:15:57,860
Net buite die omvang. Dus, selfs al is ons praat oor pointers,

261
00:15:57,860 --> 00:16:04,830
dit is 'n week 2 of 3 kwessie, waar x is slegs in omvang binnekant van die kode tussen krulhakies waar dit verklaar is.

262
00:16:04,830 --> 00:16:11,000
So jy kan beslis nie vry om dit daar. My enigste kans om dit te bevry is rofweg na line 21.

263
00:16:11,000 --> 00:16:15,170
Dit is 'n redelik eenvoudige program, maar dit was redelik maklik, wanneer jy soort van toegedraaide jou gedagtes

264
00:16:15,170 --> 00:16:17,870
rondom wat die program doen, waar die foute was.

265
00:16:17,870 --> 00:16:20,500
En selfs as jy nie sien dit op die eerste, hopelik is dit nou 'n bietjie voor die hand liggend

266
00:16:20,500 --> 00:16:23,870
dat hierdie foute is redelik maklik opgelos en maklik gemaak.

267
00:16:23,870 --> 00:16:28,720
Maar wanneer 'n program is meer as 12 lyne lank, dit is 50 lyne lank, 100 lyne lank,

268
00:16:28,720 --> 00:16:31,150
loop deur jou kode lyn deur die lyn, dink deur dit logies,

269
00:16:31,150 --> 00:16:35,110
is moontlik, maar nie baie pret om te doen, voortdurend op soek na foute,

270
00:16:35,110 --> 00:16:38,340
en dit is ook moeilik om te doen, en dit is die rede waarom 'n instrument soos Valgrind bestaan.

271
00:16:38,340 --> 00:16:40,900
Laat my gaan voort en doen dit: laat my my terminale venster oop,

272
00:16:40,900 --> 00:16:45,400
en laat my net nie hardloop nie geheue, want die geheue blyk te wees boete.

273
00:16:45,400 --> 00:16:49,180
Ek kry gelukkig. Gaan na dat bykomende byte by die einde van die skikking

274
00:16:49,180 --> 00:16:51,060
nie ook problematies blyk te wees.

275
00:16:51,060 --> 00:16:56,370
Maar laat my tog, doen 'n gesonde verstand tjek, wat net beteken om te kontroleer

276
00:16:56,370 --> 00:16:58,320
nie, of dit is eintlik korrek is.

277
00:16:58,320 --> 00:17:04,690
>> So laat doen valgrind-v - lek-check = volle,

278
00:17:04,690 --> 00:17:07,520
en dan die naam van die program in hierdie geval is geheue, nie a.out.

279
00:17:07,520 --> 00:17:10,760
So laat ek gaan voort en doen dit. Druk Enter.

280
00:17:10,760 --> 00:17:14,109
Liewe God. Dit is sy uitset, en dit is wat ek vroeër verwys het.

281
00:17:14,109 --> 00:17:17,550
Maar, as jy leer om te lees deur al die nonsens hier,

282
00:17:17,550 --> 00:17:20,760
Die meeste van hierdie is net diagnostiese opbrengs wat is nie so interessant.

283
00:17:20,760 --> 00:17:24,829
Wat jou oog regtig wil om te kyk vir enige melding van foute of ongeldig.

284
00:17:24,829 --> 00:17:26,800
Woorde wat voorstel dat probleme.

285
00:17:26,800 --> 00:17:29,340
En inderdaad, laat ons sien wat verkeerd gaan hier onder.

286
00:17:29,340 --> 00:17:35,230
Ek het 'n opsomming van 'n soort, "in gebruik by die uitgang:. 40 grepe in 1 blokke"

287
00:17:35,230 --> 00:17:38,750
Ek is nie seker wat 'n blok is nie, maar 40 bytes

288
00:17:38,750 --> 00:17:41,260
eintlik voel soos ek kon uitvind waar dit vandaan kom.

289
00:17:41,260 --> 00:17:45,030
40 grepe. Waarom is 40 grepe in gebruik by die uitgang?

290
00:17:45,030 --> 00:17:48,780
En meer spesifiek, as ons scroll down hier,

291
00:17:48,780 --> 00:17:54,520
die rede waarom ek het beslis 40 bytes verloor? Ja?

292
00:17:54,520 --> 00:17:59,520
[Student antwoord, onverstaanbaar] Perfect. Ja, presies.

293
00:17:59,520 --> 00:18:03,540
Daar was tien heelgetalle, en elkeen van daardie grootte van 4 of 32 bits,

294
00:18:03,540 --> 00:18:08,300
so ek het presies 40 grepe verloor, want soos jy voorgestel het, het ek nie genoem gratis.

295
00:18:08,300 --> 00:18:13,460
Dit is 'n fout, en nou, laat ons kyk 'n bietjie verder en sien langs,

296
00:18:13,460 --> 00:18:16,900
"Ongeldige skryf van grootte 4." Nou wat is dit?

297
00:18:16,900 --> 00:18:21,150
Hierdie adres is uitgedruk watter basis notasie, glo?

298
00:18:21,150 --> 00:18:23,640
Dit is heksadesimaal, en enige tyd wat jy sien 'n aantal wat begin met 0x,

299
00:18:23,640 --> 00:18:29,410
dit beteken heksadesimaal, wat het ons pad terug in, dink ek, pset 0 se afdeling van die vrae,

300
00:18:29,410 --> 00:18:34,090
dit was net 'n warmup oefening te doen, omskakeling desimale hex binêre en so meer.

301
00:18:34,090 --> 00:18:39,220
Heksadesimaal, net deur menslike konvensie, word gewoonlik gebruik om verwysings te verteenwoordig

302
00:18:39,220 --> 00:18:41,570
of, meer in die algemeen, spreek. Dit is net 'n konvensie,

303
00:18:41,570 --> 00:18:45,340
want dit is 'n bietjie makliker om te lees, dit is 'n bietjie meer kompak as iets soos desimale,

304
00:18:45,340 --> 00:18:47,720
en binêre is nutteloos vir die meeste mense te gebruik.

305
00:18:47,720 --> 00:18:50,840
So nou wat beteken dit? Wel, dit lyk asof daar 'n ongeldige skryf

306
00:18:50,840 --> 00:18:54,480
van grootte 4 on line 21 van memory.c.

307
00:18:54,480 --> 00:18:59,180
So laat terug te gaan na reël 21, en inderdaad, hier is dat ongeldige skryf.

308
00:18:59,180 --> 00:19:02,640
So Valgrind is nie van plan om heeltemal te hou my hand en my vertel wat die fix is,

309
00:19:02,640 --> 00:19:05,520
maar dit is die opsporing van dat ek is besig met 'n ongeldige skryf.

310
00:19:05,520 --> 00:19:08,800
Ek raak 4 bytes dat ek nie moet wees nie, en glo dit is omdat,

311
00:19:08,800 --> 00:19:13,960
soos jy sê, doen ek [10] in plaas van [9] maksimaal

312
00:19:13,960 --> 00:19:16,660
of [0] of iets tussen in.

313
00:19:16,660 --> 00:19:19,690
Met Valgrind, besef enige tyd wat jy nou 'n program te skryf

314
00:19:19,690 --> 00:19:24,190
wat gebruik maak van wysers en geheue gebruik, en malloc meer spesifiek,

315
00:19:24,190 --> 00:19:27,080
beslis kry in die gewoonte van die bestuur van hierdie lang

316
00:19:27,080 --> 00:19:30,890
maar baie maklik gekopieer en geplak bevel van Valgrind

317
00:19:30,890 --> 00:19:32,650
om te sien of daar is 'n paar foute in daar.

318
00:19:32,650 --> 00:19:34,820
En dit sal oorweldigend wees elke keer as jy die uitset,

319
00:19:34,820 --> 00:19:39,430
maar net parse deur visueel van die afvoer en sien as jy sien melding van foute

320
00:19:39,430 --> 00:19:43,190
of waarskuwings of ongeldig of verlore.

321
00:19:43,190 --> 00:19:46,200
Enige woorde wat klank soos jy screwed up iewers.

322
00:19:46,200 --> 00:19:48,580
So besef dit is 'n nuwe hulpmiddel in jou toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Nou op Maandag, ons het 'n hele klomp van die mense kom hier

324
00:19:51,270 --> 00:19:53,150
en die idee van 'n geskakelde lys verteenwoordig.

325
00:19:53,150 --> 00:20:00,970
En ons lei die geskakelde lys as 'n oplossing vir die probleem wat?

326
00:20:00,970 --> 00:20:04,590
Ja? [Student antwoord, onverstaanbaar] Goed.

327
00:20:04,590 --> 00:20:06,530
Skikkings geheue kan nie bygevoeg word aan hulle.

328
00:20:06,530 --> 00:20:09,440
As jy toeken 'n verskeidenheid van grootte 10, dit is al wat jy kry.

329
00:20:09,440 --> 00:20:13,690
Jy kan 'n funksie soos realloc bel as jy aanvanklik malloc genoem,

330
00:20:13,690 --> 00:20:17,580
en dit kan probeer om die skikking te groei indien daar is 'n spasie na die einde van

331
00:20:17,580 --> 00:20:21,610
wat niemand anders gebruik, en as daar is nie, dit sal net kry jy 'n groter stuk iewers anders.

332
00:20:21,610 --> 00:20:25,040
Maar dan sal dit kopieer al van daardie bytes in die nuwe skikking.

333
00:20:25,040 --> 00:20:28,310
Dit klink soos 'n baie korrekte oplossing.

334
00:20:28,310 --> 00:20:34,790
Hoekom is dit onaantreklik?

335
00:20:34,790 --> 00:20:36,940
Ek bedoel dit werk, het die mens hierdie probleem opgelos.

336
00:20:36,940 --> 00:20:40,710
Waarom het ons dit nodig het op te los op Maandag met geskakelde lyste? Ja?

337
00:20:40,710 --> 00:20:44,060
[Student antwoord, onverstaanbaar] Dit kan 'n lang tyd neem.

338
00:20:44,060 --> 00:20:49,260
Om die waarheid te sê, enige tyd wat jy vra die die malloc of realloc of calloc, wat nog 'n ander een,

339
00:20:49,260 --> 00:20:52,470
enige tyd wat jy die program, praat met die bedryfstelsel,

340
00:20:52,470 --> 00:20:54,310
jy is geneig om die program te vertraag.

341
00:20:54,310 --> 00:20:57,470
En as jy doen hierdie soort van dinge in die loops, jy werklik verlangsaming dinge af.

342
00:20:57,470 --> 00:21:00,740
Jy gaan dit nie om op te let vir die eenvoudigste van "hello world" tipe programme,

343
00:21:00,740 --> 00:21:04,300
maar in veel groter programme, vra die bedryfstelsel weer en weer vir die geheue

344
00:21:04,300 --> 00:21:07,520
of gee dit weer en weer geneig is om nie na 'n goeie ding wees.

345
00:21:07,520 --> 00:21:11,210
Plus, dit is net soort van intellektueel - dit is 'n volledige vermorsing van tyd.

346
00:21:11,210 --> 00:21:16,490
Waarom meer en meer geheue toeken, risiko kopiëring van alles wat in die nuwe skikking,

347
00:21:16,490 --> 00:21:21,980
as jy 'n alternatief wat kan jy net soveel geheue toeken as wat jy werklik nodig het?

348
00:21:21,980 --> 00:21:24,130
So daar is plus punte en minuses hier.

349
00:21:24,130 --> 00:21:26,730
Een van die plus punte is nou dat ons dinamika.

350
00:21:26,730 --> 00:21:29,100
Maak nie saak waar die stukke van die geheue is wat vry is,

351
00:21:29,100 --> 00:21:32,070
Ek kan net soort van hierdie broodkrummels via pointers

352
00:21:32,070 --> 00:21:34,470
my hele geskakelde lys saam te string.

353
00:21:34,470 --> 00:21:36,470
Maar ek ten minste een prys betaal.

354
00:21:36,470 --> 00:21:40,060
>> Wat moet ek doen om in die verkryging van geskakelde lyste te gee?

355
00:21:40,060 --> 00:21:42,470
Ja? [Student antwoord, onverstaanbaar] Goed.

356
00:21:42,470 --> 00:21:45,650
Jy moet meer geheue. Nou moet ek ruimte vir hierdie pointers,

357
00:21:45,650 --> 00:21:47,900
en in die geval van hierdie super eenvoudige geskakelde lys

358
00:21:47,900 --> 00:21:51,410
wat net probeer om heelgetalle te stoor, wat is 4 grepe, hou ons sê

359
00:21:51,410 --> 00:21:54,240
Wel, 'n wyser is 4 grepe, so nou het ek letterlik verdubbel

360
00:21:54,240 --> 00:21:57,290
die bedrag van die geheue Ek moet net hierdie lys te stoor.

361
00:21:57,290 --> 00:21:59,680
Maar weer, dit is 'n konstante nadeel in rekenaarwetenskap

362
00:21:59,680 --> 00:22:03,440
tussen tyd en ruimte en ontwikkeling, moeite en ander hulpbronne.

363
00:22:03,440 --> 00:22:06,630
Wat is nog 'n nadeel van die gebruik van 'n geskakelde lys? Ja?

364
00:22:06,630 --> 00:22:10,150
[Student antwoord, onverstaanbaar]

365
00:22:10,150 --> 00:22:12,600
Goed. Nie so maklik om toegang te verkry. Ons kan nie langer die hefboom

366
00:22:12,600 --> 00:22:15,530
week 0 beginsels soos verdeel en heers.

367
00:22:15,530 --> 00:22:18,220
En meer spesifiek, binêre soek. Want selfs al het ons mense

368
00:22:18,220 --> 00:22:20,400
kan rofweg sien waar die middel van hierdie lys is,

369
00:22:20,400 --> 00:22:25,840
die rekenaar weet net dat hierdie geskakelde lys begin by die adres genoem 1.

370
00:22:25,840 --> 00:22:28,250
En dit is 0x123 of iets soos dit.

371
00:22:28,250 --> 00:22:30,990
En die enigste manier om die program kan die middelste element

372
00:22:30,990 --> 00:22:33,350
is die hele lys om werklik te soek.

373
00:22:33,350 --> 00:22:35,500
En selfs dan, dit het letterlik die hele lys te soek nie, want

374
00:22:35,500 --> 00:22:38,950
selfs wanneer jy die middelste element bereik deur die wysers,

375
00:22:38,950 --> 00:22:42,380
jy, die program, het geen idee hoe lank die lys is, potensieel,

376
00:22:42,380 --> 00:22:45,250
totdat jy getref die einde van dit, en hoe weet jy programmaties

377
00:22:45,250 --> 00:22:48,600
dat jy aan die einde van 'n geskakelde lys?

378
00:22:48,600 --> 00:22:51,120
Daar is 'n spesiale NULL pointer, dit weer doen, 'n konvensie.

379
00:22:51,120 --> 00:22:53,870
Eerder as om hierdie pointer, het ons beslis nie wil hê om dit te sommige vullis waarde

380
00:22:53,870 --> 00:22:57,750
wys af stadium êrens, maar ons wil dit met die hand af, NULL,

381
00:22:57,750 --> 00:23:01,530
sodat ons hierdie terminus in hierdie data struktuur, sodat ons weet waar dit eindig.

382
00:23:01,530 --> 00:23:03,410
>> Wat gebeur as ons wil om dit te manipuleer?

383
00:23:03,410 --> 00:23:05,980
Ons het die meeste van hierdie visueel, en met die mens,

384
00:23:05,980 --> 00:23:07,630
maar wat as ons wil 'n invoeging te doen?

385
00:23:07,630 --> 00:23:12,360
So die oorspronklike lys was 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Wat as ons dan wou malloc ruimte vir nommer 55, 'n node vir dit,

387
00:23:16,730 --> 00:23:20,730
en dan wil ons 55 net soos in die lys te voeg ons het op Maandag?

388
00:23:20,730 --> 00:23:23,690
Hoe doen ons dit? Wel, Anita het opgestaan ​​en sy wese die lys geloop.

389
00:23:23,690 --> 00:23:27,500
Sy begin by die eerste element, dan is die volgende, die volgende, is die volgende, is die volgende, is die volgende.

390
00:23:27,500 --> 00:23:29,500
Uiteindelik getref die linker-hand al die pad af

391
00:23:29,500 --> 00:23:34,480
en besef oh, dit is NULL. So, wat wyser manipulasie gedoen moet word?

392
00:23:34,480 --> 00:23:37,980
Die persoon wat op die ou end, nommer 34, wat nodig is om sy linkerhand opgewek

393
00:23:37,980 --> 00:23:46,220
te wys op 55, 55 hulle linkerarm pointing down te wees van die nuwe NULL terminator nodig. Gedoen het.

394
00:23:46,220 --> 00:23:49,540
Redelik maklik 55 in te voeg in 'n gesorteerde lys.

395
00:23:49,540 --> 00:23:51,800
En hoe kan dit kyk?

396
00:23:51,800 --> 00:23:55,690
>> Laat my voort te gaan en maak 'n paar kode voorbeeld hier.

397
00:23:55,690 --> 00:23:58,120
Ek sal oopmaak gedit, en laat my eers twee lêers oop te maak.

398
00:23:58,120 --> 00:24:02,050
Een daarvan is list1.h, en laat my net herinner dat dit was die stuk van die kode

399
00:24:02,050 --> 00:24:04,920
wat ons gebruik om 'n node te verteenwoordig.

400
00:24:04,920 --> 00:24:13,040
'N node het beide 'n int N en 'n wyser volgende genoem dat net punte aan die volgende ding wat in die lys.

401
00:24:13,040 --> 00:24:15,450
Dit is nou in 'n H-lêer. Hoekom?

402
00:24:15,450 --> 00:24:19,090
Daar is hierdie Konvensie, en ons het nie die voordeel van 'n groot hoeveelheid onsself,

403
00:24:19,090 --> 00:24:22,220
maar die persoon wat printf en ander funksies geskryf

404
00:24:22,220 --> 00:24:27,150
as 'n geskenk aan die wêreld gegee het al van daardie werksaamhede deur die skryf van 'n lêer genaamd stdio.h.

405
00:24:27,150 --> 00:24:30,950
En dan is daar string.h, en dan is daar map.h, en daar is al hierdie h lêers

406
00:24:30,950 --> 00:24:34,410
dat jy dalk gesien het of wat gebruik word gedurende die termyn wat deur ander mense geskryf is.

407
00:24:34,410 --> 00:24:38,470
Tipies in daardie h lêers is slegs dinge soos typedefs

408
00:24:38,470 --> 00:24:42,310
of verklarings van persoonlike tipes of verklarings van konstantes.

409
00:24:42,310 --> 00:24:47,890
Jy sit nie funksies implementering in die header lêers.

410
00:24:47,890 --> 00:24:50,570
Jy het, in plaas daarvan, net hulle prototipes.

411
00:24:50,570 --> 00:24:53,050
Jy dinge wat jy wil om te deel met die wêreld wat hulle nodig het

412
00:24:53,050 --> 00:24:55,640
ten einde hul kode op te stel. So net om te kry in hierdie gewoonte,

413
00:24:55,640 --> 00:24:59,110
het ons besluit om dieselfde ding te doen. Daar is nie veel in list1.h,

414
00:24:59,110 --> 00:25:02,070
maar ons het iets wat dalk van belang is vir mense in die wêreld

415
00:25:02,070 --> 00:25:05,030
wat wil ons geskakelde lys implementering te gebruik.

416
00:25:05,030 --> 00:25:08,040
Nou, in list1.c, sal ek nie deur hierdie hele ding gaan

417
00:25:08,040 --> 00:25:11,390
want dit is 'n bietjie lank, hierdie program, maar laat ons hardloop dit regtig vinnig op die instruksielyn.

418
00:25:11,390 --> 00:25:15,720
Laat my stel Lys1 laat my dan hardloop Lys1, en wat jy sien is

419
00:25:15,720 --> 00:25:18,070
Ons het gesimuleerde 'n eenvoudige klein program hier

420
00:25:18,070 --> 00:25:20,990
wat gaan om my te voeg en te verwyder getalle op 'n lys.

421
00:25:20,990 --> 00:25:24,310
So laat ek gaan voort en tik 3 vir die kieslys opsie 3.

422
00:25:24,310 --> 00:25:27,880
Ek wil die getal te voeg - Kom ons doen die eerste getal, wat 9,

423
00:25:27,880 --> 00:25:30,550
en nou is ek is vertel dat die lys is nou 9.

424
00:25:30,550 --> 00:25:33,760
Laat my gaan voort en doen ander te voeg, sodat ek getref kieslys opsie 3.

425
00:25:33,760 --> 00:25:36,760
Watter getal wil ek voeg? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. En ek sal net een meer.

427
00:25:39,220 --> 00:25:41,720
Laat my voeg die getal 22.

428
00:25:41,720 --> 00:25:45,850
So ons het die begin van die geskakelde lys dat ons 'n oomblik gelede in slide vorm gehad het.

429
00:25:45,850 --> 00:25:48,740
Hoe om hierdie invoeging is eintlik besig om te gebeur?

430
00:25:48,740 --> 00:25:52,000
Inderdaad, 22 is nou aan die einde van die lys.

431
00:25:52,000 --> 00:25:55,050
So het ons vertel die storie op die verhoog op Maandag en recapped nou net

432
00:25:55,050 --> 00:25:57,460
moet eintlik in die kode.

433
00:25:57,460 --> 00:25:59,700
Kom ons neem 'n blik. Laat my scroll down in hierdie lêer.

434
00:25:59,700 --> 00:26:01,720
Ons sal glans oor sommige van die funksies,

435
00:26:01,720 --> 00:26:05,630
maar ons gaan af na, sê, die insetsel funksie.

436
00:26:05,630 --> 00:26:11,720
>> Kom ons kyk hoe gaan oor die invoeging van 'n nuwe node in hierdie geskakelde lys.

437
00:26:11,720 --> 00:26:14,550
Waar is die lys verklaar? Wel, laat ons scroll al die pad tot by die top,

438
00:26:14,550 --> 00:26:19,970
en let op dat my geskakelde lys is in wese verklaar as 'n enkele wyser wat aanvanklik NULL.

439
00:26:19,970 --> 00:26:23,180
So ek is met behulp van 'n globale veranderlike hier, wat in die algemeen het ons gepreek teen

440
00:26:23,180 --> 00:26:25,280
want dit maak jou kode 'n bietjie slordig om in stand te hou,

441
00:26:25,280 --> 00:26:29,080
dit is soort van lui, gewoonlik, maar dit is nie lui en dit is nie verkeerd nie en dit is nie sleg nie

442
00:26:29,080 --> 00:26:33,660
as jou program se enigste doel in die lewe is een geskakelde lys te simuleer.

443
00:26:33,660 --> 00:26:35,460
Dit is presies wat ons doen.

444
00:26:35,460 --> 00:26:39,100
So eerder as Verkondig dit in hoof-en dan om dit te slaag om elke funksie

445
00:26:39,100 --> 00:26:42,640
ons het in hierdie program geskryf, besef ons plaas oh, kom ons maak dit net globale

446
00:26:42,640 --> 00:26:47,060
want die hele doel van hierdie program is slegs een geskakelde lys te demonstreer.

447
00:26:47,060 --> 00:26:50,700
So dit voel goed. Hier is my prototipes, en ons sal nie gaan nie deur al hierdie,

448
00:26:50,700 --> 00:26:55,800
maar ek geskryf 'n delete funksie, 'n soek funksie, 'n insetsel funksie, en 'n traverse funksie.

449
00:26:55,800 --> 00:26:59,080
Maar laat ons nou terug gaan na die insetsel funksie

450
00:26:59,080 --> 00:27:01,490
en sien hoe hierdie een hier werk.

451
00:27:01,490 --> 00:27:09,940
Insert is op die lyn - hier gaan ons.

452
00:27:09,940 --> 00:27:12,850
Voeg. Sodat dit nie enige argumente, want ons gaan om te vra

453
00:27:12,850 --> 00:27:15,930
die gebruiker binnekant van hierdie funksie vir die aantal wat hulle wil hê om in te voeg.

454
00:27:15,930 --> 00:27:19,410
Maar eers, ons voor te berei hulle ruimte te gee.

455
00:27:19,410 --> 00:27:22,050
Dit is 'n soort van die kopieer en plak van die ander voorbeeld.

456
00:27:22,050 --> 00:27:25,110
In daardie geval, is ons die toekenning van 'n int, hierdie tyd het ons is die toekenning van 'n nodus.

457
00:27:25,110 --> 00:27:27,910
Ek het nie regtig onthou hoeveel bytes 'n node is, maar dit is goed.

458
00:27:27,910 --> 00:27:30,460
Sizeof kan figuur dit uit vir my.

459
00:27:30,460 --> 00:27:33,340
En hoekom ek kontroleer NULL in line 120?

460
00:27:33,340 --> 00:27:37,530
Wat kan verkeerd gaan in lyn 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 net die geval dat ek gevra het vir te veel geheue

463
00:27:43,440 --> 00:27:47,020
of iets is verkeerd en die bedryfstelsel nie genoeg bytes my te gee,

464
00:27:47,020 --> 00:27:50,640
so dit aandui soveel deur die terugkeer NULL, en as ek gaan nie vir daardie

465
00:27:50,640 --> 00:27:54,710
en ek het net blindelings voort te gaan na die adres gebruik teruggekeer, kan dit wees NULL.

466
00:27:54,710 --> 00:27:58,400
Dit kan 'n onbekende waarde wees, nie 'n goeie ding nie, tensy I -

467
00:27:58,400 --> 00:28:00,590
eintlik nie 'n onbekende waarde. Dit kan wees NULL, so ek wil nie

468
00:28:00,590 --> 00:28:02,550
om dit te misbruik en waag ontwysing dit.

469
00:28:02,550 --> 00:28:07,410
As dit gebeur, het ek net terug en ons sal voorgee soos ek nie terug te kry enige geheue.

470
00:28:07,410 --> 00:28:12,270
>> Anders, Ek sê vir die gebruiker gee my 'n nommer wil invoegen, ek roep ons ou vriend getint,

471
00:28:12,270 --> 00:28:15,530
en dan was dit die nuwe sintaks ons ingestel op Maandag.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n beteken die adres wat jy gegee is deur malloc

473
00:28:20,320 --> 00:28:23,490
wat verteenwoordig die eerste byte van 'n nuwe node voorwerp,

474
00:28:23,490 --> 00:28:26,860
en gaan dan na die veld genaamd n.

475
00:28:26,860 --> 00:28:35,270
'N bietjie trivia vraag: Dit is gelykstaande aan wat meer kriptiese lyn van die kode?

476
00:28:35,270 --> 00:28:38,110
Hoe sou Ek anders het dit geskryf? Wil jy 'n steek te neem?

477
00:28:38,110 --> 00:28:41,480
[Student antwoord, onverstaanbaar]

478
00:28:41,480 --> 00:28:44,870
Goed. Deur gebruik te maak van die n, maar dit is nie heeltemal so eenvoudig soos dit.

479
00:28:44,870 --> 00:28:47,090
Wat ek wel eers nodig het om te doen? [Student antwoord, onverstaanbaar]

480
00:28:47,090 --> 00:28:52,730
Goed. Ek moet * newptr.n te doen.

481
00:28:52,730 --> 00:28:55,610
So sê nuwe wyser is natuurlik 'n adres. Hoekom?

482
00:28:55,610 --> 00:28:59,520
Want dit is teruggestuur deur malloc. Die * newptr sê: "daar gaan,"

483
00:28:59,520 --> 00:29:02,970
en dan wanneer jy daar is, dan kan jy gebruik maak van die meer bekende.

484
00:29:02,970 --> 00:29:05,730
maar dit lyk net 'n bietjie lelik, veral as ons mense gaan

485
00:29:05,730 --> 00:29:10,360
pointers teken met pyltjies al die tyd, die wêreld het op die pyltjie om notasie gestandaardiseer,

486
00:29:10,360 --> 00:29:12,320
wat doen presies dieselfde ding.

487
00:29:12,320 --> 00:29:16,070
So gebruik jy net die -> notasie wanneer die ding aan die linkerkant is 'n wyser.

488
00:29:16,070 --> 00:29:18,790
Andersins, indien dit is 'n werklike struct gebruik. N.

489
00:29:18,790 --> 00:29:25,800
En dan is dit: Hoekom moet ek newptr-> Volgende inisialiseer word VRYGEMAAK?

490
00:29:25,800 --> 00:29:28,610
Ons wil nie 'n hangende linkerhand van die einde van die verhoog af.

491
00:29:28,610 --> 00:29:31,630
Ons wil dit wys reguit af, wat beteken dat die einde van hierdie lys

492
00:29:31,630 --> 00:29:34,980
potensieel kan wees op hierdie node, sodat ons beter seker maak dat dit is NULL.

493
00:29:34,980 --> 00:29:38,460
En in die algemeen, die inisialisering van jou veranderlikes of jou data lede en structs

494
00:29:38,460 --> 00:29:40,470
na iets is net goeie praktyk.

495
00:29:40,470 --> 00:29:45,170
Net laat afval bestaan ​​en voortgaan om in die algemeen bestaan, kry jy in die moeilikheid

496
00:29:45,170 --> 00:29:48,650
as jy iets vergeet het om later op te doen.

497
00:29:48,650 --> 00:29:51,590
>> Hier is 'n paar gevalle. Dit, weer, is die insetsel funksie,

498
00:29:51,590 --> 00:29:54,930
en die eerste ding wat ek kyk vir is as die veranderlike genaamd die eerste keer,

499
00:29:54,930 --> 00:29:58,240
dat globale veranderlike is NULL, wat beteken daar is geen geskakelde lys.

500
00:29:58,240 --> 00:30:02,460
Ons het nog nie ingevoeg enige nommers, dus is dit triviaal om die huidige getal te voeg

501
00:30:02,460 --> 00:30:05,240
in die lys, want dit behoort net aan die begin van die lys.

502
00:30:05,240 --> 00:30:08,100
So dit was toe Anita was net staan ​​hier alleen, voorgee

503
00:30:08,100 --> 00:30:11,390
niemand anders was hier op die verhoog totdat ons 'n nodus toegeken,

504
00:30:11,390 --> 00:30:13,940
dan kan sy haar hand opsteek vir die eerste keer,

505
00:30:13,940 --> 00:30:17,420
as almal anders gekom het op die verhoog na haar op Maandag.

506
00:30:17,420 --> 00:30:22,900
Nou hier, dit is 'n bietjie check waar ek het om te sê as die nuwe node se waarde van n

507
00:30:22,900 --> 00:30:27,370
<Die waarde van n in die huidige eerste node,

508
00:30:27,370 --> 00:30:29,930
wat beteken dat daar is 'n geskakelde lys wat begin.

509
00:30:29,930 --> 00:30:32,330
Daar is ten minste een nodus in die lys, maar hierdie nuwe man

510
00:30:32,330 --> 00:30:37,230
behoort voor dit, so ons moet dinge om rond te beweeg.

511
00:30:37,230 --> 00:30:43,450
Met ander woorde, indien die lys begin met net, laat ons sê,

512
00:30:43,450 --> 00:30:48,100
net die getal 17, wat is die werklikheid, kan ons doen dit meer duidelik.

513
00:30:48,100 --> 00:30:56,010
As ons ons storie begin met 'n wyser hier genoem 1,

514
00:30:56,010 --> 00:30:59,870
en dit aanvanklik NULL, en ons voeg die getal 9,

515
00:30:59,870 --> 00:31:02,510
die getal 9 behoort duidelik aan die begin van die lys.

516
00:31:02,510 --> 00:31:07,400
So laat ons net voorgee malloced die adres of die nommer 9 en sit dit hier.

517
00:31:07,400 --> 00:31:13,170
As eerste is 9 by verstek, die eerste scenario wat ons bespreek het beteken net laat se punt hierdie man hier,

518
00:31:13,170 --> 00:31:15,790
laat dit as 'NULL, nou het ons die getal 9.

519
00:31:15,790 --> 00:31:18,280
Die volgende getal wat ons wil voeg, is 17.

520
00:31:18,280 --> 00:31:22,420
17 behoort hier, so ons gaan 'n paar logiese stepping te doen deur middel van hierdie.

521
00:31:22,420 --> 00:31:26,060
So laat in plaas daarvan, voordat ons dit doen, laat ons voorgee dat ons wou die getal 8 in te voeg.

522
00:31:26,060 --> 00:31:28,650
>> So, ek gaan net vir wille van gemak om hier te vestig.

523
00:31:28,650 --> 00:31:30,760
Maar onthou, kan malloc sit dit mees oral.

524
00:31:30,760 --> 00:31:33,460
Maar ter wille van die tekening se, ek sit dit hier.

525
00:31:33,460 --> 00:31:38,440
So asof ek het nou net 'n node vir die getal 8 toegeken, dit is 'n NULL by verstek.

526
00:31:38,440 --> 00:31:42,800
Wat het nou gebeur? 'N Paar van die dinge.

527
00:31:42,800 --> 00:31:47,090
Ons het hierdie fout op die verhoog op Maandag, waar ons by 'n wyser soos hierdie,

528
00:31:47,090 --> 00:31:51,890
dan het dit gedoen, en dan kan ons beweer dat ons wat wees gelaat is almal op die verhoog.

529
00:31:51,890 --> 00:31:54,350
Omdat jy can't - die einde van bedrywighede hier belangrik is,

530
00:31:54,350 --> 00:31:58,760
want nou het ons verloor hierdie node 9 dit is net soort van die swaai in die ruimte.

531
00:31:58,760 --> 00:32:01,150
So dit was nie die regte benadering op Maandag.

532
00:32:01,150 --> 00:32:03,330
Ons moet eers iets anders te doen.

533
00:32:03,330 --> 00:32:06,280
Die toestand van die wêreld lyk soos hierdie. Aanvanklik het 8 toegeken is.

534
00:32:06,280 --> 00:32:10,550
Wat sou 'n beter manier van die invoeging van 8?

535
00:32:10,550 --> 00:32:14,720
In plaas van die opdatering van hierdie pointer, werk net hierdie een hier plaas.

536
00:32:14,720 --> 00:32:17,720
So moet ons 'n reël van die kode wat gaan hierdie NULL karakter om te draai

537
00:32:17,720 --> 00:32:22,020
in 'n werklike pointer wat dui op node 9,

538
00:32:22,020 --> 00:32:27,970
en dan kan ons veilig eers verander om aan hierdie man hier te wys.

539
00:32:27,970 --> 00:32:31,330
Nou het ons 'n lys, 'n geskakelde lys van twee elemente.

540
00:32:31,330 --> 00:32:33,580
En wat dit eintlik lyk soos hier?

541
00:32:33,580 --> 00:32:36,900
As ons kyk na die kode, sien dat Ek het presies dit gedoen.

542
00:32:36,900 --> 00:32:41,970
Ek het gesê newptr, en in hierdie storie, newptr wys op hierdie man.

543
00:32:41,970 --> 00:32:45,520
>> So laat my trek een ding, en ek moet verlaat het om 'n bietjie meer ruimte vir hierdie.

544
00:32:45,520 --> 00:32:48,540
So vergewe die klein tekening.

545
00:32:48,540 --> 00:32:52,140
Hierdie man word genoem newptr.

546
00:32:52,140 --> 00:32:57,940
Dit is die veranderlike wat ons 'n paar lyne verklaar vroeër, in lyn net bo 25.

547
00:32:57,940 --> 00:33:03,430
En dit is wat verwys na 8. So wanneer ek sê newptr-> Volgende, wat beteken dat gaan na die struct

548
00:33:03,430 --> 00:33:07,910
wat daarop deur newptr, so hier is ons, gaan daar.

549
00:33:07,910 --> 00:33:13,990
Toe het die pyl sê die volgende veld te kry, en dan die = gesê het watter waarde daar?

550
00:33:13,990 --> 00:33:17,280
Die waarde wat in die eerste, watter waarde het, was in die eerste?

551
00:33:17,280 --> 00:33:21,930
Vir die eerste keer wys op hierdie node, so dit beteken dat dit nou moet wys op hierdie node.

552
00:33:21,930 --> 00:33:25,660
Met ander woorde, wat lyk al is dit 'n belaglike gemors met my handskrif,

553
00:33:25,660 --> 00:33:28,620
wat is 'n eenvoudige idee van net die beweging van hierdie pyle om

554
00:33:28,620 --> 00:33:31,560
vertaal kode met net hierdie een sak.

555
00:33:31,560 --> 00:33:38,110
Bewaar wat is in die eerste in die volgende veld en dan werk waarmee hulle in eerste werklik is.

556
00:33:38,110 --> 00:33:40,900
Kom ons gaan voort en vinnig vorentoe deur 'n paar van hierdie,

557
00:33:40,900 --> 00:33:44,220
en net kyk na hierdie stert invoeging vir nou.

558
00:33:44,220 --> 00:33:51,210
Veronderstel ek kry tot die punt waar ek vind dat die volgende veld van 'n paar node is NULL.

559
00:33:51,210 --> 00:33:53,410
En op hierdie punt in die verhaal, 'n detail dat ek glossing oor

560
00:33:53,410 --> 00:33:58,170
is dat ek nog 'n wyser het ingestel hier in lyn 142, voorganger wyser.

561
00:33:58,170 --> 00:34:01,320
Wese, op hierdie punt in die verhaal, sodra die lys kry lang,

562
00:34:01,320 --> 00:34:04,800
Ek het soort van dit nodig het om te loop met twee vingers, want as ek te ver gaan,

563
00:34:04,800 --> 00:34:08,219
onthou in 'n enkel-lengte lys, kan jy nie agteruit te gaan.

564
00:34:08,219 --> 00:34:13,659
So hierdie idee van predptr is my linker vinger, en newptr - nie newptr.

565
00:34:13,659 --> 00:34:17,199
Nog 'n wyser wat hier is, is my ander vinger, en ek is net soort van die loop van die lys.

566
00:34:17,199 --> 00:34:22,179
Dit is waarom dit bestaan. Maar laat oorweeg slegs een van die eenvoudiger gevalle hier.

567
00:34:22,179 --> 00:34:26,620
As pointer se volgende veld is NULL, wat is die logiese implikasie?

568
00:34:26,620 --> 00:34:30,840
As jy kameelkoei hierdie lys en jy getref 'n NULL wyser?

569
00:34:30,840 --> 00:34:35,780
Jy is aan die einde van die lys, en so die kode dan aanlas nie hierdie een addisionele element

570
00:34:35,780 --> 00:34:41,230
is 'n soort van die intuïtiewe sal neem dat node waarvan die volgende wyser is NULL,

571
00:34:41,230 --> 00:34:46,120
so dit is tans NULL, en verander dit, al is, aan die adres van die nuwe node.

572
00:34:46,120 --> 00:34:52,260
So trek ons ​​net die pyl in die kode dat ons getrek het op die verhoog deur die verhoging van iemand se linkerhand.

573
00:34:52,260 --> 00:34:54,070
>> En die geval dat ek my hande sal beweeg nou,

574
00:34:54,070 --> 00:34:58,020
net omdat ek dink dit is maklik om verlore te raak wanneer ons dit doen in hierdie soort van die omgewing,

575
00:34:58,020 --> 00:35:00,600
kontrole te voeg by die lys se middel.

576
00:35:00,600 --> 00:35:03,220
Maar net intuïtief, wat moet gebeur as jy wil om uit te vind

577
00:35:03,220 --> 00:35:06,600
waar sommige getal hoort in die middel is wat jy hoef dit nie te loop

578
00:35:06,600 --> 00:35:09,510
met meer as een vinger, meer as een pointer,

579
00:35:09,510 --> 00:35:12,920
uit te vind waar dit behoort deur die nagaan van die element <die huidige een,

580
00:35:12,920 --> 00:35:15,450
> Die huidige een, en as jy vind dat die plek,

581
00:35:15,450 --> 00:35:20,400
dan het jy te doen hierdie soort van die dop spel waar jy beweeg die wysers om baie versigtig.

582
00:35:20,400 --> 00:35:23,850
En dat daardie antwoord, as jy wil om te redeneer deur dit by die huis op jou eie,

583
00:35:23,850 --> 00:35:28,340
kom daarop neer net om hierdie twee lyne van kode, maar die einde van daardie lyne is super belangrik.

584
00:35:28,340 --> 00:35:31,390
Want as jy iemand se hand laat val en iemand anders verhoog is in die verkeerde volgorde,

585
00:35:31,390 --> 00:35:34,580
weer, kan jy uiteindelik die lys orphaning.

586
00:35:34,580 --> 00:35:39,500
Om meer konseptueel te som, die invoeging by die stert is relatief maklik.

587
00:35:39,500 --> 00:35:42,940
Die invoeging by die kop is ook relatief maklik,

588
00:35:42,940 --> 00:35:45,580
maar jy moet 'n addisionele pointer werk hierdie tyd

589
00:35:45,580 --> 00:35:47,930
nommer 5 te druk in die lys hier,

590
00:35:47,930 --> 00:35:51,560
en dan voeg in die middel behels nog meer moeite,

591
00:35:51,560 --> 00:35:56,130
om baie versigtig te voeg die getal 20 in sy regte plek,

592
00:35:56,130 --> 00:35:58,350
wat tussen 17 en 22 is.

593
00:35:58,350 --> 00:36:02,700
Sodat jy nodig het om iets te doen soos die nuwe node 20 punt tot 22,

594
00:36:02,700 --> 00:36:08,470
en dan, wat node se wyser moet word opgedateer laaste?

595
00:36:08,470 --> 00:36:10,630
Dit is 17, om werklik te voeg.

596
00:36:10,630 --> 00:36:14,080
Dit weer doen, sal ek die werklike kode vir daardie spesifieke implementering uitstel.

597
00:36:14,080 --> 00:36:17,280
>> Met die eerste oogopslag, dit is 'n bietjie oorweldigend, maar dit is regtig net 'n oneindige lus

598
00:36:17,280 --> 00:36:21,770
wat herhaling, herhaling, herhaling, herhaling, en breek so gou as wat jy druk op die NULL pointer,

599
00:36:21,770 --> 00:36:24,590
op watter punt jy kan doen om die nodige te voeg.

600
00:36:24,590 --> 00:36:30,960
Dit is dan, is verteenwoordigend geskakelde lys invoeging kode.

601
00:36:30,960 --> 00:36:34,590
Dit was soort van 'n baie, en dit voel soos ons het een probleem opgelos,

602
00:36:34,590 --> 00:36:36,940
maar ons het 'n hele ander een. Om eerlik te wees, het ons al die tyd spandeer

603
00:36:36,940 --> 00:36:40,540
Big O en Ω en hardloop tyd, probeer om probleme op te meer vinnig op te los,

604
00:36:40,540 --> 00:36:43,270
en hier het ons neem 'n groot stap agteruit, dit voel.

605
00:36:43,270 --> 00:36:45,380
En tog, as die doel is om data op te slaan,

606
00:36:45,380 --> 00:36:48,010
dit voel soos die Heilige Graal, as ons sê op Maandag, sou werklik

607
00:36:48,010 --> 00:36:50,470
dinge om onmiddellik slaan.

608
00:36:50,470 --> 00:36:53,930
>> In werklikheid, veronderstel dat ons het ter syde gestel geskakelde lys vir 'n oomblik

609
00:36:53,930 --> 00:36:56,000
en ons plaas lei die idee van 'n tabel.

610
00:36:56,000 --> 00:36:59,110
En laat ons dink net van 'n tabel vir 'n oomblik as 'n skikking.

611
00:36:59,110 --> 00:37:03,790
Hierdie skikking en hierdie geval het hier ongeveer 26 elemente, 0 tot 25,

612
00:37:03,790 --> 00:37:07,940
en veronderstel dat jy nodig het 'n paar stuk van die stoor vir name:

613
00:37:07,940 --> 00:37:10,350
Alice en Bob en Charlie en dies meer.

614
00:37:10,350 --> 00:37:12,880
En wat jy nodig het 'n paar datastruktuur om daardie name te stoor.

615
00:37:12,880 --> 00:37:15,000
Wel, kan jy gebruik om iets soos 'n geskakelde lys

616
00:37:15,000 --> 00:37:20,260
en jy kan die lys invoeging van Alice te wandel voor die aangesig van Bob en Charlie nadat Bob en so meer.

617
00:37:20,260 --> 00:37:23,850
En, in werklikheid, as jy wil-kode soos dit te sien as 'n eenkant,

618
00:37:23,850 --> 00:37:27,230
weet dat in list2.h, ons doen presies dit.

619
00:37:27,230 --> 00:37:30,610
Ons sal nie gaan deur middel van hierdie kode, maar dit is 'n variant van die eerste voorbeeld

620
00:37:30,610 --> 00:37:34,640
wat die leerder bekendstel een ander struct ons voor sogenaamde student gesien het,

621
00:37:34,640 --> 00:37:40,330
en dan wat dit werklik stoor in die geskakelde lys is 'n verwysing na 'n student struktuur

622
00:37:40,330 --> 00:37:44,520
eerder as 'n eenvoudige klein heelgetal, n.

623
00:37:44,520 --> 00:37:46,900
So besef daar is daar kode wat behels werklike snare,

624
00:37:46,900 --> 00:37:49,940
maar as die doel by die hand is nou regtig die doeltreffendheid probleem aan te spreek,

625
00:37:49,940 --> 00:37:53,380
sou dit nie lekker wees as ons 'n voorwerp met die naam Alice,

626
00:37:53,380 --> 00:37:56,020
ons wil hê om haar te sit in die regte plek in 'n datastruktuur,

627
00:37:56,020 --> 00:37:58,860
dit voel soos dit sou wees regtig lekker om net te sit Alice,

628
00:37:58,860 --> 00:38:01,180
wie se naam begin met A, in die eerste plek.

629
00:38:01,180 --> 00:38:05,270
En Bob, wie se naam begin met B, in die tweede plek.

630
00:38:05,270 --> 00:38:09,580
Met 'n skikking, of laat ons begin noem dit 'n tafel, 'n hash tabel op daardie,

631
00:38:09,580 --> 00:38:13,650
ons kan doen presies dit. As ons 'n naam soos Alice,

632
00:38:13,650 --> 00:38:16,700
'n string soos Alice, waar jy A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Ons moet 'n hueristic. Ons benodig 'n funksie om 'n inset te neem soos Alice

634
00:38:20,540 --> 00:38:24,610
en 'n antwoord terug, "Sit Alice by hierdie plek."

635
00:38:24,610 --> 00:38:28,720
En hierdie funksie, hierdie swart kassie, gaan word 'n hash funksie genoem.

636
00:38:28,720 --> 00:38:32,330
>> 'N hash funksie is iets wat 'n inset, soos "Alice",

637
00:38:32,330 --> 00:38:38,080
en keer terug na jou, tipies, die numeriese plek in sommige data struktuur waar Alice behoort.

638
00:38:38,080 --> 00:38:40,830
In hierdie geval, moet ons hash funksie relatief eenvoudig.

639
00:38:40,830 --> 00:38:47,510
Ons hash funksie moet sê, as jy "Alice", watter karakter moet ek omgee?

640
00:38:47,510 --> 00:38:55,660
Die eerste een. So ek kyk op [0], en dan sê ek as [0] karakter is 'n, die aantal terug 0.

641
00:38:55,660 --> 00:39:01,130
As dit is B, terug 1. As dit is C, terugkeer 2, en so meer.

642
00:39:01,130 --> 00:39:05,940
All 0 indeks, en wat jou sal toelaat om my in te voeg Alice en Bob en dan Charlie en so meer

643
00:39:05,940 --> 00:39:10,960
in hierdie datastruktuur. Maar daar is 'n probleem.

644
00:39:10,960 --> 00:39:13,060
Wat as Anita kom weer?

645
00:39:13,060 --> 00:39:17,510
Waar sit ons Anita? Haar naam, ook begin met die letter A,

646
00:39:17,510 --> 00:39:20,330
en dit voel soos ons gemaak het 'n nog groter gemors van hierdie probleem.

647
00:39:20,330 --> 00:39:24,380
Ons het nou onmiddellike invoeging, konstante tyd invoeging, in 'n datastruktuur

648
00:39:24,380 --> 00:39:27,100
eerder as erger geval lineêre,

649
00:39:27,100 --> 00:39:29,510
maar wat kan ons doen met Anita in hierdie geval?

650
00:39:29,510 --> 00:39:34,110
Wat is die twee opsies, regtig? Ja?

651
00:39:34,110 --> 00:39:37,410
[Student antwoord, onverstaanbaar] Okay, sodat ons kan 'n ander dimensie.

652
00:39:37,410 --> 00:39:42,320
Dis goed. Sodat ons kan bou dinge uit in 3D soos ons oor gepraat het mondelings op Maandag.

653
00:39:42,320 --> 00:39:46,700
Ons kon 'n ander toegang hier by te voeg nie, maar veronderstel dat Nee, ek probeer om te hou hierdie eenvoudige.

654
00:39:46,700 --> 00:39:50,160
Die hele doel hier is om onmiddellike konstante-time toegang te hê,

655
00:39:50,160 --> 00:39:52,170
sodat die toevoeging van te veel kompleksiteit.

656
00:39:52,170 --> 00:39:55,970
Wat is ander opsies wanneer ek probeer om Anita te voeg in hierdie data struktuur? Ja?

657
00:39:55,970 --> 00:39:58,610
[Student antwoord, onverstaanbaar] Goed. So kan ons almal af beweeg,

658
00:39:58,610 --> 00:40:03,040
soos Charlie nudges down Bob en Alice, en dan sit ons Anita waar sy regtig wil wees.

659
00:40:03,040 --> 00:40:05,660
>> Natuurlik, nou, daar is 'n newe-effek van hierdie.

660
00:40:05,660 --> 00:40:09,000
Hierdie data struktuur is waarskynlik nuttig nie omdat ons wil hê mense te voeg wanneer

661
00:40:09,000 --> 00:40:11,250
maar omdat ons wil om te kyk of hulle daar later

662
00:40:11,250 --> 00:40:13,600
as ons wil uit te druk al die name in die data struktuur.

663
00:40:13,600 --> 00:40:15,850
Ons gaan om iets te doen met hierdie data uiteindelik.

664
00:40:15,850 --> 00:40:20,810
So nou het ons soort geskroef oor Alice, wat is nie meer waar sy veronderstel is om te wees.

665
00:40:20,810 --> 00:40:23,880
Of is Bob, of is Charlie.

666
00:40:23,880 --> 00:40:26,060
So miskien is dit nie so 'n goeie idee.

667
00:40:26,060 --> 00:40:28,830
Maar in werklikheid is dit is een opsie. Ons almal kan skuif af,

668
00:40:28,830 --> 00:40:32,240
of Heck, Anita laat gekom het vir die spel, hoekom doen ons nie net sit Anita

669
00:40:32,240 --> 00:40:35,870
nie hier nie, nie hier nie, nie hier nie, laat haar net 'n bietjie laer in die lys.

670
00:40:35,870 --> 00:40:38,680
Maar dan is hierdie probleem weer begin oorgaan.

671
00:40:38,680 --> 00:40:41,630
Jy mag dalk in staat wees om Alice te vind onmiddellik, wat gebaseer is op haar eerste naam.

672
00:40:41,630 --> 00:40:44,320
En Bob onmiddellik, en Charlie. Maar dan moet jy kyk vir Anita,

673
00:40:44,320 --> 00:40:46,360
en jy sien, hmm, Alice is in die pad.

674
00:40:46,360 --> 00:40:48,770
Wel, laat ek kyk onder Alice. Bob is nie Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie is nie Anita. O, daar is Anita.

676
00:40:51,850 --> 00:40:54,720
En as jy nog steeds dat die trein van die logika al die pad,

677
00:40:54,720 --> 00:41:00,690
wat is die ergste geval looptyd van die bevinding of die invoeging van Anita in hierdie nuwe data struktuur?

678
00:41:00,690 --> 00:41:03,280
Dit is O (n), reg?

679
00:41:03,280 --> 00:41:06,280
Want in die ergste geval, daar is Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
al die pad af na iemand met die naam "Y", so daar is net een plek gelaat.

681
00:41:10,150 --> 00:41:13,950
Gelukkig, ons het niemand met die naam "Z", so ons sit Anita by die heel onderste.

682
00:41:13,950 --> 00:41:16,040
>> Ons het regtig nie dat die probleem opgelos nie.

683
00:41:16,040 --> 00:41:19,890
So miskien kan ons hierdie derde dimensie hoef in te voer.

684
00:41:19,890 --> 00:41:22,230
En dit blyk, as ons hierdie derde dimensie,

685
00:41:22,230 --> 00:41:25,240
ons kan dit nie doen nie perfek nie, maar die Heilige Graal is gaan te wees om

686
00:41:25,240 --> 00:41:28,370
konstante-time invoeging en dinamiese invoegings sodat

687
00:41:28,370 --> 00:41:30,960
ons het nie te hard-kode 'n skikking van grootte 26.

688
00:41:30,960 --> 00:41:34,400
Ons kan voeg soveel name as ons wil, maar laat ons 5-minute break hier

689
00:41:34,400 --> 00:41:38,790
en dan doen wat goed.

690
00:41:38,790 --> 00:41:46,020
Alles reg. Ek het die storie redelik kunsmatig daar

691
00:41:46,020 --> 00:41:48,670
deur die keuse van Alice en dan Bob en dan Charlie en dan Anita,

692
00:41:48,670 --> 00:41:51,000
wie se naam is natuurlik gaan om te bots met Alice.

693
00:41:51,000 --> 00:41:54,120
Maar die vraag wat ons op Maandag geëindig het met net hoe waarskynlik is dit

694
00:41:54,120 --> 00:41:56,370
wat jy sou kry hierdie soort van botsings? Met ander woorde,

695
00:41:56,370 --> 00:42:00,490
as ons begin om hierdie tabel struktuur te gebruik, wat eintlik net 'n skikking,

696
00:42:00,490 --> 00:42:02,460
in die geval van 26 plekke,

697
00:42:02,460 --> 00:42:05,740
wat as ons insette plaas eenvormig versprei?

698
00:42:05,740 --> 00:42:09,620
Dit is nie kunsmatig Alice en Bob en Charlie en Dawid en ensovoorts alfabeties,

699
00:42:09,620 --> 00:42:12,380
dit is eenvormig versprei oor A tot Z.

700
00:42:12,380 --> 00:42:15,220
>> Miskien sal ons net gelukkig en gaan ons nie twee A's of twee B's te hê

701
00:42:15,220 --> 00:42:17,640
met 'n baie hoë waarskynlikheid, maar as iemand daarop gewys,

702
00:42:17,640 --> 00:42:20,730
as ons algemene hierdie probleem en nie doen 0 25

703
00:42:20,730 --> 00:42:26,060
maar, sê, 0 tot 364 of 65, wat dikwels die aantal dae in 'n tipiese jaar,

704
00:42:26,060 --> 00:42:31,170
en vra die vraag, "Wat is die waarskynlikheid dat twee van ons in hierdie kamer het dieselfde verjaarsdag?"

705
00:42:31,170 --> 00:42:34,600
Sit dit 'n ander manier, wat is die waarskynlikheid dat twee van ons het 'n naam wat begin met A?

706
00:42:34,600 --> 00:42:37,190
Die soort van die vraag is dieselfde, maar hierdie adres ruimte,

707
00:42:37,190 --> 00:42:39,940
dit soek ruimte, is groter in die geval van verjaarsdae,

708
00:42:39,940 --> 00:42:42,820
want ons het so baie meer dae in die jaar as letters in die alfabet.

709
00:42:42,820 --> 00:42:44,910
Wat is die waarskynlikheid van 'n botsing?

710
00:42:44,910 --> 00:42:48,410
Wel, ons kan dink van hierdie uitzoeken die wiskunde in die teenoorgestelde rigting.

711
00:42:48,410 --> 00:42:50,580
Wat is die waarskynlikheid van geen botsings?

712
00:42:50,580 --> 00:42:53,970
Wel, hierdie uitdrukking hier sê wat is die waarskynlikheid

713
00:42:53,970 --> 00:42:58,770
indien daar is net een persoon in hierdie kamer, dat hulle 'n unieke verjaarsdag?

714
00:42:58,770 --> 00:43:01,190
Dit is 100%. Want as daar is slegs een persoon in die kamer,

715
00:43:01,190 --> 00:43:03,940
sy of haar verjaardag kan enige van die 365 dae uit die jaar.

716
00:43:03,940 --> 00:43:08,650
So 365/365 opsies gee my 'n waarde van 1.

717
00:43:08,650 --> 00:43:11,250
So die waarskynlikheid in die vraag op die oomblik is net 1.

718
00:43:11,250 --> 00:43:13,270
Maar as daar 'n tweede persoon in die kamer,

719
00:43:13,270 --> 00:43:16,490
wat is die waarskynlikheid dat hulle verjaarsdag is anders?

720
00:43:16,490 --> 00:43:20,680
Daar is slegs 364 moontlike dae, ignoreer skrikkeljare,

721
00:43:20,680 --> 00:43:23,580
vir hul verjaarsdag nie te bots met die ander persone.

722
00:43:23,580 --> 00:43:31,920
So 364/365. As 1/3 persoon kom, is dit 363/365, en so meer.

723
00:43:31,920 --> 00:43:35,790
Sodat ons hou hierdie breuke vermenigvuldig saam, wat kleiner en kleiner,

724
00:43:35,790 --> 00:43:40,720
om uit te vind wat is die waarskynlikheid dat almal van ons het 'n unieke verjaarsdae?

725
00:43:40,720 --> 00:43:43,570
Maar dan kan ons natuurlik, net die antwoord en draai dit rond

726
00:43:43,570 --> 00:43:47,210
en doen 1 minus alle van daardie, 'n uitdrukking wat ons sal uiteindelik

727
00:43:47,210 --> 00:43:51,250
as jy dink aan die agterkant van jou wiskunde boeke, dit lyk 'n bietjie iets soos hierdie,

728
00:43:51,250 --> 00:43:54,590
wat baie meer maklik geïnterpreteer grafies voor.

729
00:43:54,590 --> 00:43:57,820
En hierdie grafiese hier op die x-as die getal van verjaarsdae,

730
00:43:57,820 --> 00:44:02,030
of die aantal mense met verjaarsdae, en op die y-as is die waarskynlikheid van 'n wedstryd.

731
00:44:02,030 --> 00:44:06,060
En wat dit sê, is dat as jy het, laat ons sê, selfs,

732
00:44:06,060 --> 00:44:10,860
Kom ons kies iets soos 22, 23.

733
00:44:10,860 --> 00:44:13,160
As daar 22 of 23 mense in die kamer,

734
00:44:13,160 --> 00:44:17,100
die waarskynlikheid dat twee van dié wat baie min mense gaan dieselfde verjaarsdag te hê

735
00:44:17,100 --> 00:44:19,560
is eintlik super-hoë, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% kans dat in 'n klas van net 22 mense, 'n seminaar, prakties,

737
00:44:23,450 --> 00:44:25,790
2 van die mense gaan dieselfde verjaarsdag te hê.

738
00:44:25,790 --> 00:44:28,520
Want daar is so baie maniere waarop jy kan dieselfde verjaarsdag.

739
00:44:28,520 --> 00:44:31,110
Nog erger, as jy kyk na die regterkant van die grafiek,

740
00:44:31,110 --> 00:44:34,040
teen die tyd dat jy 'n klas met 58 studente in,

741
00:44:34,040 --> 00:44:39,270
die waarskynlikheid van 2 mense met 'n verjaarsdag is super, super hoog, byna 100%.

742
00:44:39,270 --> 00:44:41,880
Nou, dit is soort van 'n prettige feit oor die werklike lewe.

743
00:44:41,880 --> 00:44:45,850
>> Maar die implikasies, nou, vir datastrukture en stoor van inligting

744
00:44:45,850 --> 00:44:51,100
beteken dat net as jy het 'n mooi, skoon, eenvormige verspreiding van die data

745
00:44:51,100 --> 00:44:53,650
en jy het 'n groot genoeg verskeidenheid om 'n klomp van die dinge aan te pas

746
00:44:53,650 --> 00:44:59,360
beteken nie jy gaan om mense te kry in 'n unieke plekke.

747
00:44:59,360 --> 00:45:03,810
Jy gaan om botsings te hê. So hierdie idee van hashing, soos dit genoem word,

748
00:45:03,810 --> 00:45:07,450
die neem van 'n inset soos "Alice" en masseer dit in die een of ander manier

749
00:45:07,450 --> 00:45:10,190
en dan kry 'n antwoord soos 0 of 1 of 2 terug.

750
00:45:10,190 --> 00:45:17,500
Om terug n uitset van daardie funksie is geteister deur die waarskynlikheid van 'n botsing.

751
00:45:17,500 --> 00:45:19,530
So hoe kan ons daardie botsings hanteer?

752
00:45:19,530 --> 00:45:21,940
Wel, op die een geval, kan ons die idee dat is voorgestel.

753
00:45:21,940 --> 00:45:25,100
Ons kan net skuif almal af, of miskien 'n bietjie meer eenvoudig,

754
00:45:25,100 --> 00:45:29,870
eerder as skuif almal, laat ons net beweeg Anita aan die onderkant van die beskikbare plek.

755
00:45:29,870 --> 00:45:32,810
So as Alice in 0, Bob is in 1, Charlie is in 2,

756
00:45:32,810 --> 00:45:35,260
ons sal net sit Anita op plek 3.

757
00:45:35,260 --> 00:45:38,860
En dit is 'n tegniek in die data strukture genoem lineêre indringende.

758
00:45:38,860 --> 00:45:41,310
Lineêre omdat jy net loop hierdie lyn, en jy is soort van ondersoekende

759
00:45:41,310 --> 00:45:43,640
vir beskikbare plekke in die data struktuur.

760
00:45:43,640 --> 00:45:46,210
Natuurlik, dit oorgaan in O (n).

761
00:45:46,210 --> 00:45:49,590
As die data struktuur is regtig vol, daar is reeds 25 mense in dit,

762
00:45:49,590 --> 00:45:54,120
en dan Anita saam kom, het sy eindig op watter plek Z sou wees, en dit is goed.

763
00:45:54,120 --> 00:45:56,540
Sy pas nog steeds, en ons kan haar kry later.

764
00:45:56,540 --> 00:46:00,100
>> Maar dit was in stryd met die doel van die bespoediging dinge.

765
00:46:00,100 --> 00:46:02,530
So wat as ons plaas het hierdie derde dimensie?

766
00:46:02,530 --> 00:46:06,400
Hierdie tegniek is algemeen aparte aaneenskakeling genoem, of met kettings.

767
00:46:06,400 --> 00:46:10,030
En wat 'n hash tafel is nou hierdie tabel struktuur,

768
00:46:10,030 --> 00:46:13,450
jou tafel is net 'n verskeidenheid van wysers.

769
00:46:13,450 --> 00:46:18,230
Maar wat die wysers wys raai wat?

770
00:46:18,230 --> 00:46:21,970
'N geskakelde lys. So wat as ons die beste van beide van hierdie wêrelde?

771
00:46:21,970 --> 00:46:26,500
Ons maak gebruik van skikkings vir die aanvanklike indekse

772
00:46:26,500 --> 00:46:32,070
in die data struktuur sodat ons kan direk gaan na die [0] [1], [30] of ensovoorts,

773
00:46:32,070 --> 00:46:36,480
maar sodat ons 'n mate van buigsaamheid en ons kan inpas Anita en Alice en Adam

774
00:46:36,480 --> 00:46:38,630
en enige ander 'n naam,

775
00:46:38,630 --> 00:46:43,470
ons plaas laat die ander as arbitrêr groei.

776
00:46:43,470 --> 00:46:47,340
En ons uiteindelik, soos op Maandag, dat die ekspressiewe vermoë met geskakelde lys.

777
00:46:47,340 --> 00:46:49,530
Ons kan 'n datastruktuur arbitrêr groei.

778
00:46:49,530 --> 00:46:52,450
Alternatiewelik, kan ons maak net 'n groot 2-dimensionele skikking,

779
00:46:52,450 --> 00:46:57,190
maar dit gaan 'n vreeslike situasie wees as een van die rye in 'n 2-dimensionele skikking

780
00:46:57,190 --> 00:47:01,280
is nie groot genoeg vir die addisionele persoon wie se naam gebeur om te begin met A.

781
00:47:01,280 --> 00:47:04,200
God verbied ons het 'n groot 2-dimensionele struktuur te wysig

782
00:47:04,200 --> 00:47:06,600
net omdat daar so baie mense die naam van 'n,

783
00:47:06,600 --> 00:47:09,480
veral wanneer daar is so min mense met die naam Z iets.

784
00:47:09,480 --> 00:47:12,170
Dit is net gaan om 'n baie yl data struktuur.

785
00:47:12,170 --> 00:47:15,400
So dit is nie volmaak nie op enige manier nie, maar nou het ons ten minste die vermoë om

786
00:47:15,400 --> 00:47:19,090
direk te vind waar Alice of Anita behoort,

787
00:47:19,090 --> 00:47:21,090
ten minste in terme van die vertikale as,

788
00:47:21,090 --> 00:47:25,850
en dan het ons net om te besluit waar om te sit Anita of Alice in hierdie geskakelde lys.

789
00:47:25,850 --> 00:47:32,480
As ons nie omgee sorteer dinge, kan hoe vinnig ons voeg Alice in 'n struktuur soos hierdie?

790
00:47:32,480 --> 00:47:35,370
Dit is konstante tyd. Ons indeks in [0], en as niemand daar,

791
00:47:35,370 --> 00:47:37,550
Alice gaan aan die begin van die geskakelde lys.

792
00:47:37,550 --> 00:47:40,000
Maar dit is nie 'n groot deal. Want as Anita kom dan saam

793
00:47:40,000 --> 00:47:42,160
n aantal stappe later, waar Anita behoort?

794
00:47:42,160 --> 00:47:45,140
Wel, [0]. Oop. Alice is reeds in daardie geskakelde lys.

795
00:47:45,140 --> 00:47:47,760
>> Maar as ons nie omgee oor die sortering van hierdie name,

796
00:47:47,760 --> 00:47:53,580
ons kan net beweeg Alice oor insert Anita, maar selfs dit is 'n konstante tyd.

797
00:47:53,580 --> 00:47:57,010
Selfs al is daar Alice en Adam en al die ander 'n name,

798
00:47:57,010 --> 00:47:59,410
dit is regtig nie verskuif hulle fisies. Hoekom?

799
00:47:59,410 --> 00:48:04,090
Omdat ons net het hier met geskakelde lys, wie weet, is hierdie nodes is in elk geval?

800
00:48:04,090 --> 00:48:06,550
Al wat jy hoef te doen is skuif die broodkrummels.

801
00:48:06,550 --> 00:48:10,930
Skuif die pyle rond, jy hoef nie enige data om fisies te beweeg rond.

802
00:48:10,930 --> 00:48:14,610
Sodat ons kan voeg Anita, in daardie geval, onmiddellik. Konstante.

803
00:48:14,610 --> 00:48:20,250
So het ons 'n konstante-time lookup, en konstante-time invoeging van iemand soos Anita.

804
00:48:20,250 --> 00:48:22,740
Maar soort van oorvereenvoudig die wêreld.

805
00:48:22,740 --> 00:48:28,510
Wat gebeur as ons later wil Alice te vind?

806
00:48:28,510 --> 00:48:31,050
Wat gebeur as ons later wil Alice te vind?

807
00:48:31,050 --> 00:48:35,690
Hoeveel treë is dat gaan te neem?

808
00:48:35,690 --> 00:48:37,850
[Student antwoord, onverstaanbaar]

809
00:48:37,850 --> 00:48:40,950
Presies. Die aantal mense wat voor Alice in die geskakelde lys.

810
00:48:40,950 --> 00:48:45,420
So dit is nie heeltemal volmaak nie, want ons data struktuur, weer, het hierdie vertikale toegang

811
00:48:45,420 --> 00:48:50,240
en dan is dit hierdie geskakelde lyste hang - eintlik, laat ons nie trek dit 'n 'n skikking.

812
00:48:50,240 --> 00:48:56,020
Dit is hierdie geskakelde lyste hang af van dit wat lyk 'n bietjie iets soos hierdie.

813
00:48:56,020 --> 00:48:59,110
Maar die probleem is as Alice en Adam en al die ander 'n name

814
00:48:59,110 --> 00:49:01,720
beland daar meer en meer,

815
00:49:01,720 --> 00:49:04,810
vind iemand kan eindig met 'n klomp van die stappe,

816
00:49:04,810 --> 00:49:06,670
bcause jy die geskakelde lys te verken,

817
00:49:06,670 --> 00:49:08,090
wat is 'n lineêre werking.

818
00:49:08,090 --> 00:49:14,270
So regtig, dan, die invoeging van die tyd is uiteindelik O (n), waar n die aantal elemente in die lys.

819
00:49:14,270 --> 00:49:21,780
Gedeel deur, laat arbitrêr noem dit m, waar m die getal van geskakelde lyste

820
00:49:21,780 --> 00:49:24,500
dat ons 'n in hierdie vertikale as.

821
00:49:24,500 --> 00:49:27,180
Met ander woorde, as ons werklik aanvaar 'n eenvormige verspreiding van name,

822
00:49:27,180 --> 00:49:30,150
heeltemal onrealisties. Daar is natuurlik meer van 'n paar letters as ander.

823
00:49:30,150 --> 00:49:32,580
>> Maar as ons aanvaar vir die oomblik dat 'n eenvormige verspreiding,

824
00:49:32,580 --> 00:49:37,350
en ons het 'n totaal mense, en m totale kettings

825
00:49:37,350 --> 00:49:40,630
tot ons beskikking, dan is die lengte van elk van hierdie kettings

826
00:49:40,630 --> 00:49:44,380
redelik eenvoudig gaan die totaal, n, gedeel deur die aantal kettings.

827
00:49:44,380 --> 00:49:48,900
So N / m. Maar hier is waar ons almal wiskundig slim kan wees.

828
00:49:48,900 --> 00:49:53,030
m is 'n konstante, want daar is 'n vaste aantal van hierdie.

829
00:49:53,030 --> 00:49:54,620
Jy gaan jou skikking te verklaar aan die begin,

830
00:49:54,620 --> 00:49:58,450
en ons is nie resizing die vertikale as. Per definisie, bly dat vasgestel.

831
00:49:58,450 --> 00:50:01,220
Dit is net die horisontale as, om so te praat, wat verander.

832
00:50:01,220 --> 00:50:04,760
So tegnies, dit is 'n konstante. So nou, die invoeging van die tyd

833
00:50:04,760 --> 00:50:09,700
is pretty much O (n).

834
00:50:09,700 --> 00:50:12,410
Sodat nie alles wat veel beter voel.

835
00:50:12,410 --> 00:50:14,940
Maar wat is die waarheid? Wel, al hierdie tyd, vir weke,

836
00:50:14,940 --> 00:50:20,640
ons het gesê O (n ²). O (n), 2 x n ², - n, gedeel deur 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Dit is net n ². Maar nou, in hierdie deel van die semester,

838
00:50:23,580 --> 00:50:25,560
kan ons begin praat oor die werklike wêreld weer.

839
00:50:25,560 --> 00:50:31,520
En n / m is absoluut vinniger as net N alleen.

840
00:50:31,520 --> 00:50:35,170
As jy 'n duisend name, en jy breek hulle in verskeie emmers

841
00:50:35,170 --> 00:50:37,820
sodat jy net tien name in elk van hierdie kettings,

842
00:50:37,820 --> 00:50:41,670
absoluut soek tien dinge gaan wees vinniger as 'n duisend dinge.

843
00:50:41,670 --> 00:50:43,740
En so het een van die komende probleem stelle gaan jou uit te daag

844
00:50:43,740 --> 00:50:46,100
na te dink oor presies wat, selfs al is, ja,

845
00:50:46,100 --> 00:50:49,520
asimptoties en wiskundig, dit is nog steeds net lineêre,

846
00:50:49,520 --> 00:50:51,700
wat suig in die algemeen wanneer ek probeer om dinge te vind.

847
00:50:51,700 --> 00:50:54,530
In werklikheid, dit gaan vinniger wees as dit

848
00:50:54,530 --> 00:50:56,520
as gevolg van die deler.

849
00:50:56,520 --> 00:50:58,310
En so is daar weer aan die gang om hierdie trade-off

850
00:50:58,310 --> 00:51:01,390
en hierdie konflik tussen teorie en werklikheid,

851
00:51:01,390 --> 00:51:03,550
en een van die knoppies sal begin draai op hierdie punt in die semester

852
00:51:03,550 --> 00:51:07,510
meer van die werklikheid een is soos ons soort van voor te berei vir die einde van semester,

853
00:51:07,510 --> 00:51:09,280
stel ons die wêreld van die web programmering,

854
00:51:09,280 --> 00:51:11,530
waar is regtig, prestasie gaan om te tel, want jou gebruikers gaan

855
00:51:11,530 --> 00:51:14,880
begin om te voel en waardeer swak ontwerp besluite.

856
00:51:14,880 --> 00:51:19,950
>> So, hoe gaan jy oor die implementering van 'n gekoppelde - 'n hash tafel met 31 elemente?

857
00:51:19,950 --> 00:51:22,600
En die vorige voorbeeld was arbitrêr oor verjaarsdae.

858
00:51:22,600 --> 00:51:26,190
As iemand het 'n verjaardag van 1 Januarie of Februarie 1, sit ons hulle in die emmer.

859
00:51:26,190 --> 00:51:28,960
As dit is 2 Januarie, Februarie 2, Maart 2, sit ons hulle in die emmer.

860
00:51:28,960 --> 00:51:32,220
Dit is waarom dit was 31. Hoe verklaar jy 'n hash tafel?

861
00:51:32,220 --> 00:51:37,480
Dit kan redelik eenvoudige, node * tabel is my arbitrêre naam vir dit, [31].

862
00:51:37,480 --> 00:51:42,400
Dit gee my 31 pointers nodes,

863
00:51:42,400 --> 00:51:45,370
en wat toelaat dat my 31 pointers te geskakelde lyste te hê

864
00:51:45,370 --> 00:51:48,800
selfs as die kettings is aanvanklik NULL.

865
00:51:48,800 --> 00:51:54,860
Wat ek wil sit as ek wil om te stoor "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Wel, ons nodig het om daardie dinge te draai in 'n struktuur

867
00:51:57,010 --> 00:52:00,530
want ons moet Alice te wys Bob, om te wys op Charlie, en so meer.

868
00:52:00,530 --> 00:52:04,940
Ons kan net nie die name nie alleen nie, so ek kan 'n nuwe struktuur genoem node hier.

869
00:52:04,940 --> 00:52:08,310
>> Wat is 'n werklike node? Wat is 'n node in hierdie nuwe geskakelde lys?

870
00:52:08,310 --> 00:52:11,840
Die eerste ding wat genoem woord, is vir die persoon se naam.

871
00:52:11,840 --> 00:52:14,340
Lengte, vermoedelik, hou verband met die maksimum lengte van 'n mens se naam,

872
00:52:14,340 --> 00:52:18,210
wat dit ook al is, 20, 30, 40 karakters in 'n gek hoek gevalle,

873
00:52:18,210 --> 00:52:22,680
en 1 is vir wat? Dit is net die ekstra NULL karakter, \ 0.

874
00:52:22,680 --> 00:52:27,410
Hierdie node wikkel "iets" binnekant van homself,

875
00:52:27,410 --> 00:52:29,640
maar dit verklaar ook 'n wyser genoem volgende

876
00:52:29,640 --> 00:52:32,580
sodat ons kan ketting Alice Bob Charlie en so meer.

877
00:52:32,580 --> 00:52:36,700
Kan NULL, maar nie noodwendig hoef te wees.

878
00:52:36,700 --> 00:52:40,110
Enige vrae oor hierdie hash tabelle? Ja?

879
00:52:40,110 --> 00:52:46,190
[Student vra vraag, onverstaanbaar] 'n skikking - goeie vraag.

880
00:52:46,190 --> 00:52:50,120
Hoekom is hierdie char woord in 'n skikking eerder as net char *?

881
00:52:50,120 --> 00:52:53,830
In hierdie ietwat arbitrêre voorbeeld, het ek nie wil hê om plek

882
00:52:53,830 --> 00:52:56,190
malloc vir elk van die oorspronklike name.

883
00:52:56,190 --> 00:52:59,530
Ek wou 'n maksimum bedrag van die geheue vir die string te verklaar

884
00:52:59,530 --> 00:53:06,020
sodat ek kon kopieer in die struktuur Alice \ 0 en nie hoef te hanteer malloc en vry en dies meer.

885
00:53:06,020 --> 00:53:11,710
Maar ek kon doen dat as ek wou meer bewus wees van die ruimte gebruik. Goeie vraag.

886
00:53:11,710 --> 00:53:14,780
So laat ons probeer om te veralgemeen weg van hierdie

887
00:53:14,780 --> 00:53:18,350
en fokus op die res van vandag meer in die algemeen oor datastrukture

888
00:53:18,350 --> 00:53:21,170
en ander probleme wat ons kan oplos deur gebruik te maak van die dieselfde grondbeginsels

889
00:53:21,170 --> 00:53:24,590
selfs al is die data strukture self kan verskil in hul besonderhede.

890
00:53:24,590 --> 00:53:27,910
>> So dit blyk in rekenaarwetenskap, bome is baie algemeen.

891
00:53:27,910 --> 00:53:29,760
En jy kan dink van 'n boom soort van soos 'n stamboom,

892
00:53:29,760 --> 00:53:31,830
waar daar is 'n paar wortels, sommige matriarg of patriarg,

893
00:53:31,830 --> 00:53:34,540
ouma of oupa of vroeër terug,

894
00:53:34,540 --> 00:53:38,880
onder wat ma en pa of verskeie broers en susters, of die wil.

895
00:53:38,880 --> 00:53:42,500
So 'n boom struktuur nodes en dit het kinders,

896
00:53:42,500 --> 00:53:45,260
gewoonlik 0 of meer kinders vir elke node.

897
00:53:45,260 --> 00:53:47,320
En sommige van die jargon wat jy sien in hierdie foto hier

898
00:53:47,320 --> 00:53:50,630
enige van die klein kinders of kleinkinders op die kante

899
00:53:50,630 --> 00:53:52,330
wat geen pyle wat voortspruit uit hulle het,

900
00:53:52,330 --> 00:53:55,070
dit is die sogenaamde blare, en iemand aan die binnekant

901
00:53:55,070 --> 00:53:58,790
is 'n innerlike node, jy kan noem dit iets langs die lyne.

902
00:53:58,790 --> 00:54:01,430
Maar hierdie struktuur is redelik algemeen. Hierdie een is 'n bietjie arbitrêre.

903
00:54:01,430 --> 00:54:04,930
Ons het 'n kind aan die linkerkant, ons het drie kinders aan die regterkant,

904
00:54:04,930 --> 00:54:06,830
twee kinders op die bodem verlaat.

905
00:54:06,830 --> 00:54:10,740
Sodat ons kan verskillende grootte bome, maar as ons begin om dinge te standaardiseer,

906
00:54:10,740 --> 00:54:15,330
en jy kan onthou van Patrick se video op 'n binêre soek uit 'n vorige kort

907
00:54:15,330 --> 00:54:19,490
online, binêre soek, is nie geïmplementeer word met 'n verskeidenheid

908
00:54:19,490 --> 00:54:21,410
of stukkies papier op 'n swartbord.

909
00:54:21,410 --> 00:54:25,490
Veronderstel dat jy wou jou nommers op te slaan in 'n meer gesofistikeerde data-struktuur.

910
00:54:25,490 --> 00:54:27,680
Jy kan skep 'n boom soos hierdie.

911
00:54:27,680 --> 00:54:35,290
Jy kan 'n node verklaar in C, en dat die knoop kan ten minste twee elemente binnekant van dit.

912
00:54:35,290 --> 00:54:39,470
Een daarvan is die nommer wat jy wil op te slaan, en die ander is - goed, ons moet een meer.

913
00:54:39,470 --> 00:54:41,540
Die ander is sy kinders.

914
00:54:41,540 --> 00:54:45,150
So hier is 'n ander datastruktuur. Hierdie tyd, is 'n node gedefinieer as die stoor van 'n getal 'n

915
00:54:45,150 --> 00:54:49,060
en dan twee wysers, links kind en regs kind.

916
00:54:49,060 --> 00:54:52,100
En hulle is nie arbitrêr. Wat is interessant is oor hierdie boom?

917
00:54:52,100 --> 00:55:00,550
>> Wat is die patroon in hoe het ons gelê dit uit of hoe Patrick het dit in sy video?

918
00:55:00,550 --> 00:55:02,790
Dit is soort van voor die hand liggend dat daar is 'n paar te sorteer wat hier aan die gang is,

919
00:55:02,790 --> 00:55:04,460
maar wat is die eenvoudige reël? Ja?

920
00:55:04,460 --> 00:55:08,350
[Student antwoord, onverstaanbaar]

921
00:55:08,350 --> 00:55:12,040
Perfect. As jy blik op hierdie, sien jy die klein getalle aan die linkerkant,

922
00:55:12,040 --> 00:55:14,690
groot getalle aan die linkerkant, maar dit is waar vir elke node.

923
00:55:14,690 --> 00:55:20,370
Vir elke node, sy linker kind minder as dit, en sy reg kind groter as wat dit is.

924
00:55:20,370 --> 00:55:25,210
Wat beteken dit nou is as ek wil hierdie data struktuur te soek vir, sê, die getal 44,

925
00:55:25,210 --> 00:55:29,320
Ek het om te begin by die wortel, want met al hierdie meer komplekse datastrukture nou,

926
00:55:29,320 --> 00:55:31,910
ons het net 'n wyser na een ding, die begin.

927
00:55:31,910 --> 00:55:35,010
En in hierdie geval, die begin is die wortel. Dit is nie die linker kant,

928
00:55:35,010 --> 00:55:39,530
dit is die wortel van hierdie struktuur. So ek sien hier is 55, en ek is op soek na 44.

929
00:55:39,530 --> 00:55:41,430
Watter rigting wil ek om te gaan?

930
00:55:41,430 --> 00:55:45,680
Wel, ek wil om te gaan na die linkerkant, want natuurlik, aan die regterkant te groot gaan wees.

931
00:55:45,680 --> 00:55:49,050
So hier sien, jy is soort van konseptueel kap die boom in die helfte

932
00:55:49,050 --> 00:55:51,700
omdat jy nooit gaan aan die regterkant.

933
00:55:51,700 --> 00:55:55,410
So nou gaan ek van die 55 aan die 33. Dit is te klein van 'n getal.

934
00:55:55,410 --> 00:56:01,590
Ek is op soek na 44, maar nou weet ek as daar 44 is in hierdie boom, ek kan natuurlik gaan aan die regterkant.

935
00:56:01,590 --> 00:56:04,460
Dit weer doen, ek snoei die boom in die helfte.

936
00:56:04,460 --> 00:56:06,780
Dit is pretty much identies konseptueel aan die telefoon boek.

937
00:56:06,780 --> 00:56:09,510
Dit is identies aan wat ons gedoen het met die vraestelle op die bord,

938
00:56:09,510 --> 00:56:13,940
maar dit is 'n meer gesofistikeerde struktuur wat ons in staat stel om werklik te doen

939
00:56:13,940 --> 00:56:16,880
dit verdeel en oorwin deur die ontwerp van die algoritme,

940
00:56:16,880 --> 00:56:19,420
en in die feit, kameelkoei 'n struktuur soos hierdie - Oeps.

941
00:56:19,420 --> 00:56:22,870
Dwars deur 'n struktuur soos hierdie, waar dit net "gaan op hierdie manier of in daardie rigting gaan,"

942
00:56:22,870 --> 00:56:26,870
beteken al daardie kode wat buig jou gedagtes op die eerste wanneer die uitvoering daarvan in artikel

943
00:56:26,870 --> 00:56:31,270
of loop deur dit by die huis, vir 'n binêre soek, met behulp van rekursie of te wel iterasie,

944
00:56:31,270 --> 00:56:35,060
dit is 'n pyn in die nek. Vind die middelste element, doen dan jou afronding styg of daal.

945
00:56:35,060 --> 00:56:39,230
>> Daar is 'n skoonheid, want ons kan nou rekursie gebruik weer,

946
00:56:39,230 --> 00:56:43,760
maar veel meer netjies. Trouens, as jy by die getal 55 en jy wil te vind 44,

947
00:56:43,760 --> 00:56:48,450
gaan jy links in hierdie geval, dan wat doen jy? Jy loop die presiese dieselfde algoritme.

948
00:56:48,450 --> 00:56:51,560
Jy die waarde van die node, dan gaan jy links of regs.

949
00:56:51,560 --> 00:56:53,670
Toe jy die waarde van die node, gaan links of regs.

950
00:56:53,670 --> 00:56:56,710
Dit is uitstekend geskik vir rekursie.

951
00:56:56,710 --> 00:57:00,920
So selfs al is ons in die verlede gedoen het 'n paar redelik arbitrêre voorbeelde waarby rekursie

952
00:57:00,920 --> 00:57:03,430
wat nie nodig het om te wees rekursiewe, met data Strukture,

953
00:57:03,430 --> 00:57:07,820
veral bome, dit is 'n perfekte toepassing van hierdie idee van die neem van 'n probleem op te los,

954
00:57:07,820 --> 00:57:12,920
krimp dit, en dan die oplossing van die dieselfde soort van, maar kleiner, program.

955
00:57:12,920 --> 00:57:14,590
>> So daar is 'n ander datastruktuur wat ons kan stel.

956
00:57:14,590 --> 00:57:18,760
Hierdie een is ontwerp met die eerste oogopslag te kyk kriptiese, maar hierdie een is ongelooflik.

957
00:57:18,760 --> 00:57:25,090
So, dit is 'n datastruktuur Trie, Trie, wat geërf word van die woord herwinning genoem,

958
00:57:25,090 --> 00:57:30,210
wat nie uitgespreek re-drie-val, maar dit is wat die wêreld noem hierdie dinge. Probeer. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Dit is 'n boom struktuur van 'n soort, maar elk van die nodusse in 'n Trie

960
00:57:35,190 --> 00:57:41,280
blyk te wees, wat? En dit is 'n bietjie misleidend, want dit is soort van afgekort.

961
00:57:41,280 --> 00:57:45,960
Maar dit lyk asof elke node in hierdie Trie is eintlik 'n skikking.

962
00:57:45,960 --> 00:57:48,840
En selfs al is die outeur van hierdie diagram het nie getoon dat dit,

963
00:57:48,840 --> 00:57:54,130
in hierdie geval, hierdie Trie is 'n datastruktuur wie se doel in die lewe is om woorde op te slaan

964
00:57:54,130 --> 00:57:57,330
soos A-l-i-c-e of B-o-b.

965
00:57:57,330 --> 00:58:02,480
En die wyse waarop hierdie data winkels Alice en Bob en Charlie en Anita en so meer

966
00:58:02,480 --> 00:58:06,970
dit maak gebruik van 'n skikking waarvolgens Alice op te slaan in 'n Trie,

967
00:58:06,970 --> 00:58:09,820
ons begin by die wortel node wat lyk soos 'n skikking,

968
00:58:09,820 --> 00:58:12,080
en dit is geskryf in snelskrif notasie.

969
00:58:12,080 --> 00:58:15,070
Die skrywer weggelaat ABCDEFG, want daar was geen name met wat.

970
00:58:15,070 --> 00:58:19,150
Hulle het nie net gewys M en P en T, maar in hierdie geval,

971
00:58:19,150 --> 00:58:22,780
laat se weg van Alice en Bob en Charlie skuif na 'n paar name wat is hier.

972
00:58:22,780 --> 00:58:25,670
Maxwell is eintlik in hierdie diagram.

973
00:58:25,670 --> 00:58:29,570
So hoe het die skrywer winkel M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Hy of sy begin by die wortel node, en gaan na [M], so ongeveer 13, die 13de plek in die skikking.

975
00:58:36,990 --> 00:58:40,750
Dan van daar af, daar is 'n wyser.

976
00:58:40,750 --> 00:58:42,760
'N wyser wat lei tot 'n skikking.

977
00:58:42,760 --> 00:58:47,880
Van daar die skrywer geïndekseer in daardie skikking op plek A, soos uitgebeeld daar links bo,

978
00:58:47,880 --> 00:58:52,250
en dan sal hy of sy gevolg dat die wyser na 'n ander skikking,

979
00:58:52,250 --> 00:58:55,460
en gaan na die muis wyser op die plek X.

980
00:58:55,460 --> 00:58:59,840
Dan in die volgende array plek W, E, L, L, en so meer,

981
00:58:59,840 --> 00:59:03,090
en ten slotte, laat ons eintlik probeer om 'n foto te maak aan hierdie.

982
00:59:03,090 --> 00:59:05,380
Wat doen 'n node lyk in die kode?

983
00:59:05,380 --> 00:59:11,820
'N nodus in 'n Trie bevat 'n verskeidenheid van verwysings na meer nodes.

984
00:59:11,820 --> 00:59:16,090
Maar daar is ook het 'n soort van Boolese waarde wees, ten minste in die implementering van hierdie.

985
00:59:16,090 --> 00:59:18,770
Ek gebeur om dit te noem is_word. Hoekom?

986
00:59:18,770 --> 00:59:22,670
Want as jy Maxwell is die invoeging van, is jy nie die invoeging van

987
00:59:22,670 --> 00:59:25,300
enigiets in hierdie datastruktuur.

988
00:59:25,300 --> 00:59:27,480
Jy skryf nie M. Jy is nie die skryf van X.

989
00:59:27,480 --> 00:59:30,240
Al wat jy doen, is na aanleiding van wysers.

990
00:59:30,240 --> 00:59:33,360
Die wyser wat verteenwoordig M, dan die wyser wat 'n

991
00:59:33,360 --> 00:59:36,310
dan die wyser wat verteenwoordig X, dan W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
maar wat jy hoef te doen aan die einde is 'n soort van gaan, kyk, Ek hierdie plek bereik.

993
00:59:41,950 --> 00:59:45,560
Daar was 'n woord wat eindig hier in die data struktuur.

994
00:59:45,560 --> 00:59:48,190
>> So, wat 'n Trie werklik gevul met en die skrywer verkies te verteenwoordig

995
00:59:48,190 --> 00:59:51,880
hierdie bushaltes met min driehoeke.

996
00:59:51,880 --> 00:59:56,470
Dit beteken net dat die feit dat hierdie driehoek hier is, Boole-waarde van die ware

997
00:59:56,470 --> 00:59:59,200
beteken dat as jy gaan terug in die boom,

998
00:59:59,200 --> 01:00:02,420
wat beteken dat 'n woord met die naam Maxwell is in hierdie.

999
01:00:02,420 --> 01:00:04,870
Maar die woord foo, byvoorbeeld,

1000
01:00:04,870 --> 01:00:07,970
is nie in die boom, want as ek begin by die wortel node hier by die top,

1001
01:00:07,970 --> 01:00:14,030
Daar is geen f pointer, o pointer, o wyser. Foo is nie 'n naam in hierdie woordeboek.

1002
01:00:14,030 --> 01:00:22,460
Maar in teenstelling, Turing, t-u-r-i-n-g. Weereens, ek het nie stoor t of jy of r of i of n of g.

1003
01:00:22,460 --> 01:00:29,820
Maar ek het winkel in die data struktuur 'n waarde van die ware pad af hier in hierdie node in die boom

1004
01:00:29,820 --> 01:00:33,030
deur die oprigting van hierdie boolean waarde van is_word na ware.

1005
01:00:33,030 --> 01:00:35,740
So 'n Trie is 'n soort van hierdie baie interessante meta-struktuur,

1006
01:00:35,740 --> 01:00:39,810
waar jy regtig nie die stoor van die woorde self vir hierdie soort van 'n woordeboek.

1007
01:00:39,810 --> 01:00:45,100
Om duidelik te wees, het jy net die stoor ja of nee, daar is 'n woord wat eindig hier.

1008
01:00:45,100 --> 01:00:46,430
>> Nou wat is die implikasie?

1009
01:00:46,430 --> 01:00:51,120
As jy 'n 150,000 woorde in 'n woordeboek wat jy probeer om op te slaan in die geheue

1010
01:00:51,120 --> 01:00:53,400
die gebruik van iets soos 'n geskakelde lys,

1011
01:00:53,400 --> 01:00:56,870
jy gaan 150.000 nodes in jou geskakelde lys te hê.

1012
01:00:56,870 --> 01:01:00,250
En die vind van een van daardie woorde alfabeties O (n) tyd kan neem.

1013
01:01:00,250 --> 01:01:04,370
Lineêre tyd. Maar in die geval hier van 'n Trie,

1014
01:01:04,370 --> 01:01:09,210
wat is die looptyd van die vind van 'n woord?

1015
01:01:09,210 --> 01:01:17,390
Dit blyk uit die skoonheid hier is dat selfs as jy 149.999 woorde reeds in hierdie woordeboek,

1016
01:01:17,390 --> 01:01:20,170
soos met die data struktuur geïmplementeer,

1017
01:01:20,170 --> 01:01:25,560
hoeveel tyd dit neem om uit te vind of voeg een persoon in daardie, soos Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Wel, dit is slegs 5, dalk 6 stappe vir die afsluitende karakter.

1019
01:01:30,640 --> 01:01:32,880
Omdat die teenwoordigheid van die ander name in die struktuur

1020
01:01:32,880 --> 01:01:35,340
nie in die weg van die invoeging van Alice.

1021
01:01:35,340 --> 01:01:39,640
Verder, die vind van Alice wanneer daar is 150,000 woorde in hierdie woordeboek

1022
01:01:39,640 --> 01:01:41,960
nie kry in jou manier van die vind van Alice at all,

1023
01:01:41,960 --> 01:01:46,880
omdat Alice is. . . . . hier, want ek het gevind dat 'n Boolese waarde.

1024
01:01:46,880 --> 01:01:50,920
En as daar is geen boolean true, dan Alice is nie in hierdie data struktuur van woorde.

1025
01:01:50,920 --> 01:01:56,220
Met ander woorde, die looptyd van die vind van dinge en die invoeging van dinge in hierdie nuwe

1026
01:01:56,220 --> 01:02:01,920
data struktuur van Trie O - dit is nie Ñ.

1027
01:02:01,920 --> 01:02:05,730
Omdat die teenwoordigheid van 150.000 mense het geen effek op Alice, dit lyk.

1028
01:02:05,730 --> 01:02:11,560
So kom ons noem dit k, waar k is die maksimum lengte van 'n woord in Engels

1029
01:02:11,560 --> 01:02:14,050
wat is gewoonlik nie meer as 20-iets karakters.

1030
01:02:14,050 --> 01:02:17,940
So k 'n konstante. Dus is die Heilige Graal lyk ons ​​nou

1031
01:02:17,940 --> 01:02:26,000
is dié van 'n Trie, konstante tyd vir inserts vir soektogte vir skrappings.

1032
01:02:26,000 --> 01:02:29,170
Omdat die aantal van die dinge wat reeds in die struktuur,

1033
01:02:29,170 --> 01:02:32,600
wat nie eens fisies daar. Weereens, hulle sorteer net nagegaan af, ja of nee,

1034
01:02:32,600 --> 01:02:35,050
het geen impak op sy toekomstige looptyd.

1035
01:02:35,050 --> 01:02:37,940
>> Maar daar het 'n vangplek wees, anders sou ons nie vermors word nie so baie tyd

1036
01:02:37,940 --> 01:02:41,460
op al hierdie ander datastrukture net om uiteindelik na die geheime wat is ongelooflik.

1037
01:02:41,460 --> 01:02:46,410
So watter prys ons betaal om hierdie grootheid hier bereik? Ruimte.

1038
01:02:46,410 --> 01:02:49,010
Hierdie ding is groot. En die rede dat die skrywer

1039
01:02:49,010 --> 01:02:52,400
het dit nie hier sien dat al hierdie dinge wat lyk soos skikkings,

1040
01:02:52,400 --> 01:02:55,400
hy het nie die res van die boom, die res van die Trie,

1041
01:02:55,400 --> 01:02:58,060
want hulle is nie net relevant is vir die storie.

1042
01:02:58,060 --> 01:03:01,870
Maar al van hierdie nodes is super breed, en elke nodus in die boom neem

1043
01:03:01,870 --> 01:03:07,780
26 of eintlik, 27 karakters kan wees, want in hierdie geval het ek met inbegrip van ruimte vir die afkappingsteken

1044
01:03:07,780 --> 01:03:09,980
sodat ons kan apostrophized woorde.

1045
01:03:09,980 --> 01:03:14,450
In hierdie geval, dit is wye skikkings. So selfs al het hulle is nie picutured,

1046
01:03:14,450 --> 01:03:18,190
dit neem 'n massiewe bedrag van RAM.

1047
01:03:18,190 --> 01:03:20,670
Wat dalk goed wees, especilly in die moderne hardeware,

1048
01:03:20,670 --> 01:03:25,650
maar dit is die nadeel. Ons kry minder tyd deur die besteding van meer ruimte.

1049
01:03:25,650 --> 01:03:28,580
So waar dit alles gaan?

1050
01:03:28,580 --> 01:03:32,640
Wel, laat ons doen - laat ons hier te sien.

1051
01:03:32,640 --> 01:03:39,510
Kom ons doen 'n sprong na hierdie man hier.

1052
01:03:39,510 --> 01:03:43,450
>> Glo dit of nie, soveel pret soos C is vir 'n geruime tyd nou,

1053
01:03:43,450 --> 01:03:48,130
ons bereik die punt in die semester waar dit is tyd om te oorgang na dinge meer moderne.

1054
01:03:48,130 --> 01:03:50,950
Dinge wat op 'n hoër vlak. En selfs al vir die volgende paar weke

1055
01:03:50,950 --> 01:03:54,580
ons sal steeds voortgaan om onsself te verdiep in die wêreld van wysers en geheue-bestuur

1056
01:03:54,580 --> 01:03:57,210
dat die vertroosting waarmee ons kan bou op te kry,

1057
01:03:57,210 --> 01:04:01,270
die einde spel is uiteindelik bekend te stel, ironies genoeg, nie hierdie taal nie.

1058
01:04:01,270 --> 01:04:03,330
Ons sal spandeer, soos 10 minute van praat oor HTML.

1059
01:04:03,330 --> 01:04:05,950
Alle HTML word, is 'n opmaak taal, en wat 'n opmaak taal is

1060
01:04:05,950 --> 01:04:10,220
is hierdie reeks van oop hakies en geslote hakies wat sê: "maak dit vet"

1061
01:04:10,220 --> 01:04:12,000
"Maak hierdie kursief" "hierdie gesentreerde."

1062
01:04:12,000 --> 01:04:14,250
Dit is nie almal wat intellektueel interessant, maar dit is super nuttig.

1063
01:04:14,250 --> 01:04:16,650
En dit is beslis alomteenwoordig hierdie dae.

1064
01:04:16,650 --> 01:04:19,450
Maar wat is kragtig oor die wêreld van HTML en web programmering meer in die algemeen,

1065
01:04:19,450 --> 01:04:25,910
die bou van dinamiese dinge kode skryf in tale soos PHP of Python of Ruby of Java of C #.

1066
01:04:25,910 --> 01:04:30,360
Regtig, wat die taal van jou keuse is, en die generating HTML dinamies.

1067
01:04:30,360 --> 01:04:32,960
Om iets genoem CSS dinamies.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, wat ook oor estetika.

1069
01:04:35,810 --> 01:04:41,360
En so, selfs al is vandag, as ek gaan tot 'n webwerf soos die bekende Google.com,

1070
01:04:41,360 --> 01:04:46,100
en ek gaan om te sien, ontwikkelaar, sien die bron, wat miskien het jy nog nooit gedoen het,

1071
01:04:46,100 --> 01:04:49,800
maar gaan bron te besigtig, hierdie dinge lyk waarskynlik redelik kriptiese.

1072
01:04:49,800 --> 01:04:55,320
Maar dit is die onderliggende kode wat implemente Google.com.

1073
01:04:55,320 --> 01:04:57,940
Op die voorkant. En eintlik al hierdie fluffy estetika stuff.

1074
01:04:57,940 --> 01:05:01,740
Dit is CSS hier. As ek hou blaai af sal ons kry 'n kleur-gekodeerde dinge.

1075
01:05:01,740 --> 01:05:06,890
Dit is HTML. Google se kode lyk soos 'n gemors, maar as ek eintlik 'n ander venster oop te maak,

1076
01:05:06,890 --> 01:05:09,380
ons kan 'n bietjie struktuur sien.

1077
01:05:09,380 --> 01:05:12,640
As ek oop om dit hier sien, is dit 'n bietjie meer leesbare.

1078
01:05:12,640 --> 01:05:16,850
Ons gaan kort voor lank sien hierdie merker, [woord] is 'n tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, kop, liggaam, div, script, teks, span, gesentreerde, div.

1080
01:05:23,520 --> 01:05:26,770
En dit is ook met die eerste oogopslag sorteer van kriptiese-looking,

1081
01:05:26,770 --> 01:05:30,890
maar al hierdie gemors volg sekere patrone, en herhaal patrone,

1082
01:05:30,890 --> 01:05:33,850
sodat wanneer kry ons die basiese beginsels, sal jy in staat wees om kode soos hierdie te skryf

1083
01:05:33,850 --> 01:05:37,550
en dan manipuleer kode soos dit met nog 'n ander taal, genoem JavaScript.

1084
01:05:37,550 --> 01:05:40,440
En JavaScript is 'n taal wat loop binnekant van 'n leser

1085
01:05:40,440 --> 01:05:44,380
vandag wat ons gebruik op Harvard kursusse vir die kursus shopping instrument wat gebruik vir Google Maps

1086
01:05:44,380 --> 01:05:48,660
te gee jy 'n hele klomp van die dinamika, Facebook gee jou direkte status updates te wys,

1087
01:05:48,660 --> 01:05:51,430
Twitter gebruik dit om te wys jy tweets onmiddellik.

1088
01:05:51,430 --> 01:05:53,820
Al hierdie sal ons begin om onsself te verdiep.

1089
01:05:53,820 --> 01:05:57,190
Maar om daar te kom, moet ons 'n bietjie iets oor die Internet te verstaan.

1090
01:05:57,190 --> 01:06:01,130
Hierdie clip hier is net 'n minuut lank, en kom ons veronderstel vir nou is dit is, in werklikheid,

1091
01:06:01,130 --> 01:06:08,380
hoe om die Internet as 'n teaser vir wat gaan oor om te kom werk. Ek gee jou "Warriors van die Net."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow koor musiek ♫]

1093
01:06:14,720 --> 01:06:20,450
[Manlik verteller] Hy het gekom met 'n boodskap.

1094
01:06:20,450 --> 01:06:23,770
Met 'n protokol wat al sy eie.

1095
01:06:23,770 --> 01:06:37,270
[♫ Vinniger elektroniese musiek ♫]

1096
01:06:37,270 --> 01:06:41,330
Hy het gekom om 'n wêreld van die koel firewalls, uncaring routers,

1097
01:06:41,330 --> 01:06:45,690
en gevare veel erger as die dood.

1098
01:06:45,690 --> 01:06:55,400
Hy is vinnig. Hy is sterk. Hy is TCP / IP, en hy het jou adres.

1099
01:06:55,400 --> 01:06:59,250
Warriors van die Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Volgende week, dan. Die Internet. Web programmering. Dit is CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]