1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [6. nädalal Jätkub]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Harvardi Ülikool]

3
00:00:04,160 --> 00:00:08,720
[See on CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
See on CS50 ja see on lõpuks 6. nädal.

5
00:00:12,970 --> 00:00:17,970
Nii CS50x, üks Harvardi esimest kursust kaasatud EDX algatus

6
00:00:17,970 --> 00:00:20,590
tõepoolest debüteeris möödunud esmaspäeval.

7
00:00:20,590 --> 00:00:23,460
Kui soovite saada pilguheit mida teised Internetis

8
00:00:23,460 --> 00:00:27,180
nüüd pärast koos, saate pea x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
See suunab teid sobiva koha edx.org,

10
00:00:30,350 --> 00:00:34,160
mis oli, kus see ja teine ​​kursust MIT ja Berkeley nüüd elame.

11
00:00:34,160 --> 00:00:38,140
Sa pead sisse logida konto, leiad, et see materjal on üldjoontes sama

12
00:00:38,140 --> 00:00:42,170
kui teil on olnud see semester, kuigi paar nädalat edasi lükata, kui saame kõik valmis.

13
00:00:42,170 --> 00:00:46,930
Aga mida õpilased CS50x kuvatakse nüüd on liides, täiesti nagu see üks.

14
00:00:46,930 --> 00:00:50,040
See näiteks on Zamyla viib läbikäiguks jaoks probleem komplekt 0.

15
00:00:50,040 --> 00:00:54,230
Pärast sisselogimist edx.org, CS50x õpilane näeb asjadele

16
00:00:54,230 --> 00:00:57,170
ootate näha muidugi: loeng esmaspäev,

17
00:00:57,170 --> 00:01:01,650
loeng kolmapäev, erinevate lühikesed püksid, probleem komplekti, walkthroughs, PDF-faile.

18
00:01:01,650 --> 00:01:04,459
Lisaks, nagu näete siin, masintõlge

19
00:01:04,459 --> 00:01:08,390
inglise ärakirju hiina, jaapani, hispaania, itaalia,

20
00:01:08,390 --> 00:01:12,810
ja terve hunnik teisi keeli, et kindlasti ebatäiuslik

21
00:01:12,810 --> 00:01:15,840
nagu me veereta neid programmiliselt kasutades midagi, mida nimetatakse API

22
00:01:15,840 --> 00:01:18,360
või rakenduse programmeerimise liidest, Google

23
00:01:18,360 --> 00:01:21,360
mis võimaldab meil muuta inglise nendele teistes keeltes.

24
00:01:21,360 --> 00:01:24,100
Kuid tänu imeline vaimus paarisaja-pluss vabatahtlikega

25
00:01:24,100 --> 00:01:26,940
juhuslik inimesed internetis, kes on lahkelt pakutakse kaasa lööma

26
00:01:26,940 --> 00:01:30,180
selles projektis, siis me järk-järgult kvaliteedi parandamise need tõlked

27
00:01:30,180 --> 00:01:35,790
lastes inimestel parandada vigu, et meie arvutid on tehtud.

28
00:01:35,790 --> 00:01:42,330
>> Nii selgub olime veel mõned õpilased näitavad üles esmaspäeval kui me algselt lootsime.

29
00:01:42,330 --> 00:01:48,980
Tegelikult nüüd CS50x on 100.000 inimest pärast mööda kodus.

30
00:01:48,980 --> 00:01:54,430
Nii mõistad, sa on kõik osa sellest avaistung klassi muuta see muidugi infotehnoloogia

31
00:01:54,430 --> 00:01:57,370
haridus üldisemalt laiemalt kättesaadav.

32
00:01:57,370 --> 00:02:00,130
Ja reaalsus on nüüd, kusjuures mõned neist tohutu online kursused,

33
00:02:00,130 --> 00:02:04,070
nad kõik algab järgmiste väga suurtes kogustes, sest näib, et oleme siin teinud.

34
00:02:04,070 --> 00:02:08,759
Aga eesmärk lõpuks selleni, et CS50x on tõesti saada nii palju inimesi finišijoone kui võimalik.

35
00:02:08,759 --> 00:02:12,000
Autor disain, CS50x läheb antakse alates möödunud esmaspäev

36
00:02:12,000 --> 00:02:17,430
kõik teed läbi 15 aprill 2013, nii et inimesed, kes on kooli kohustused mujal

37
00:02:17,430 --> 00:02:20,990
töö, pere, muud konfliktid jms, on veidi rohkem paindlikkust

38
00:02:20,990 --> 00:02:23,640
kellega siis sukelduda sellesse muidugi, mis piisab, kui öelda,

39
00:02:23,640 --> 00:02:30,540
on üsna ambitsioonikalt teha, kui ainult jooksul vaid kolm kuud ajal tavaline poolaastal.

40
00:02:30,540 --> 00:02:34,190
Aga need õpilased on võidelda sama probleem komplekti, vaatamise sama sisu,

41
00:02:34,190 --> 00:02:36,350
kellel on juurdepääs sama lühikesed püksid jms.

42
00:02:36,350 --> 00:02:38,990
Nii mõistame, et me kõik oleme tõesti selles koos.

43
00:02:38,990 --> 00:02:42,360
Ja üks lõppeesmärgid CS50x ei ole lihtsalt saada nii palju toredaid inimesi

44
00:02:42,360 --> 00:02:45,720
kuni finišijoone ja anda neile seda taasleitud arusaam infotehnoloogia

45
00:02:45,720 --> 00:02:49,000
ja programmide, vaid ka lasta on see jagatud kogemus.

46
00:02:49,000 --> 00:02:52,010
Üks omaduste määratlemise 50 loengusse, loodame,

47
00:02:52,010 --> 00:02:56,260
on olnud selline ühiskondlik kogemus, hea või halb, mõnikord,

48
00:02:56,260 --> 00:02:59,480
kuid võttes need inimesed pöörduvad vasakule ja paremale,

49
00:02:59,480 --> 00:03:01,830
ja tööajal ja hackathon ja õiglane.

50
00:03:01,830 --> 00:03:04,560
See on natuke raskem teha, et inimene inimesed online,

51
00:03:04,560 --> 00:03:10,580
kuid CS50x lõppeb aprillis esmakordselt CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
mis on internetis kohandamine meie idee õiglane

53
00:03:13,630 --> 00:03:18,250
kus need tuhanded õpilased kogu palutakse esitada 1 - kuni 2-minutilise video,

54
00:03:18,250 --> 00:03:22,480
kas kaadrid oma lõpliku projekti või video neist viipab tere

55
00:03:22,480 --> 00:03:24,490
ja räägi oma projekti ja demoing see,

56
00:03:24,490 --> 00:03:27,610
palju nagu teie eelkäijad on teinud siin ülikoolilinnakus õiglane,

57
00:03:27,610 --> 00:03:31,400
nii et semestri lõpus, lootus on luua ülemaailmne näitus

58
00:03:31,400 --> 00:03:37,080
Euroopa CS50x õpilaste lõplik projekte, meelega, mis ootab sind selle aasta detsembris siin ülikooli.

59
00:03:37,080 --> 00:03:39,680
Nii et rohkem, et lähikuudel.

60
00:03:39,680 --> 00:03:43,640
>> Mis 100000 üliõpilastele, aga tekib vajadus veel mõned pädevad asutused.

61
00:03:43,640 --> 00:03:47,590
Arvestades, et kutid on lõõskav rada siin ja võttes CS50

62
00:03:47,590 --> 00:03:51,630
mitu nädalat enne seda materjali sattumist inimesed edasi EDX,

63
00:03:51,630 --> 00:03:55,330
realiseerida oleks tore kaasata võimalikult palju oma õpilastele kui võimalik selles algatuses

64
00:03:55,330 --> 00:03:58,720
nii poolaastal samuti sel talvel ja tuleval kevadel.

65
00:03:58,720 --> 00:04:01,620
Nii et kui soovid kaasa lüüa CS50x,

66
00:04:01,620 --> 00:04:07,450
eriti ühineda sisse CS50x arutada, EDX versioon CS50 arutada

67
00:04:07,450 --> 00:04:10,140
mis paljud teist on kasutanud loengusse, online teadetetahvel,

68
00:04:10,140 --> 00:04:13,040
palun tehke pea et link, andke teada, kes sa oled,

69
00:04:13,040 --> 00:04:16,450
sest meile meeldiks ehitada meeskond õpilased ja töötajad ja õppejõud nii

70
00:04:16,450 --> 00:04:19,630
ülikoolilinnakus, kes lihtsalt mängivad kaasa ja aitasid.

71
00:04:19,630 --> 00:04:21,720
Ja kui nad näevad küsimus, mis on tuttav neile,

72
00:04:21,720 --> 00:04:25,320
kuulete õpilane aru mõned bug kuskil seal mõnes riigis Internetis

73
00:04:25,320 --> 00:04:27,450
ja et rõngad kelluke, sest sa liiga oli sama teema

74
00:04:27,450 --> 00:04:32,620
oma d-hallis mõni aeg tagasi, loodetavasti siis saate Säestää ja jagada oma kogemusi.

75
00:04:32,620 --> 00:04:37,300
Nii et palun ärge osalema, kui soovid.

76
00:04:37,300 --> 00:04:39,360
>> Informaatika kursuste Harvardi on natuke traditsioon,

77
00:04:39,360 --> 00:04:44,730
CS50 nende seas, kellel oli ka rõivad, mõned riided, mida saab kanda uhkelt

78
00:04:44,730 --> 00:04:49,090
kell semestri lõppu, öeldes üsna uhkelt, et oled lõpetanud CS50

79
00:04:49,090 --> 00:04:51,830
ja võttis CS50 jms, ja me püüame alati kaasata üliõpilasi

80
00:04:51,830 --> 00:04:54,540
Selle protsessi nii palju kui võimalik, mille kutsume,

81
00:04:54,540 --> 00:04:56,900
umbes sel ajal poolaastal, õpilased esitada kujunduse

82
00:04:56,900 --> 00:04:59,330
kasutades Photoshop, või mis iganes soositud soovite kasutada

83
00:04:59,330 --> 00:05:02,330
kui sa oled disainer, esitama kujundused T-särgid ja dressipluusid

84
00:05:02,330 --> 00:05:06,100
ja vihmavarjud ja vähe bandanas koertele on meil nüüd jms.

85
00:05:06,100 --> 00:05:09,370
Ja kõik on siis - võitjate igal aastal on siis eksponeeritud

86
00:05:09,370 --> 00:05:12,700
rajal veebilehel store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Kõik on müüdud soetusmaksumuses olemas, kuid kodulehel lihtsalt jookseb ise

88
00:05:15,790 --> 00:05:18,330
ja võimaldab inimestel valida värve ja disaine, mis neile meeldib.

89
00:05:18,330 --> 00:05:20,420
Nii et ma arvasin, et me lihtsalt jagada mõningaid eelmisel aastal kujunduse

90
00:05:20,420 --> 00:05:25,130
mis olid veebilehel peale selle ühe siin, mis on iga-aastane traditsioon.

91
00:05:25,130 --> 00:05:29,410
"Iga päev ma olen Seg Faultn" oli ühes vastuses eelmisel aastal

92
00:05:29,410 --> 00:05:32,290
mis on kättesaadav seal vilistlased.

93
00:05:32,290 --> 00:05:35,820
Meil oli see üks, "CS50, Asutatud 1989."

94
00:05:35,820 --> 00:05:39,010
Üks meie Bowdens, Rob, oli väga populaarne eelmisel aastal.

95
00:05:39,010 --> 00:05:43,480
"Meeskond Bowden" sündis, see disain esitati seas top müüjad.

96
00:05:43,480 --> 00:05:49,040
Nagu oli see siin. Paljud inimesed olid "Bowden Fever" vastavalt müügi logisid.

97
00:05:49,040 --> 00:05:52,650
Aru, et see võiks nüüd olla oma disaini seal üleval internetis.

98
00:05:52,650 --> 00:05:57,510
Täpsemat infot selle kohta järgmise probleem seab tulla.

99
00:05:57,510 --> 00:06:00,330
>> Veel üks tööriist: teil on olnud mõned kokkupuute ja loodetavasti nüüd

100
00:06:00,330 --> 00:06:02,350
mõned praktilisi kogemusi koos GDB,

101
00:06:02,350 --> 00:06:04,570
mis on muidugi siluri ning võimaldab teil manipuleerida

102
00:06:04,570 --> 00:06:09,500
oma programmi üsna madalal tasemel, tehes milliseid asju?

103
00:06:09,500 --> 00:06:13,030
Mis GDB lase sul teha?

104
00:06:13,030 --> 00:06:15,030
Jah? Anna mulle midagi. [Student vastus, arusaamatult]

105
00:06:15,030 --> 00:06:18,120
Hea. Astu funktsioon, et sa ei lihtsalt tüüp joosta

106
00:06:18,120 --> 00:06:22,310
ja on programm löök läbi tervikuna, väljatrükk asjad standardväljundisse.

107
00:06:22,310 --> 00:06:25,190
Pigem saab astuda läbi rida-realt, kas kirjutades kõrval

108
00:06:25,190 --> 00:06:30,300
minna rida rea ​​kaupa või samm sukelduda funktsiooni, tavaliselt üks, mis sa kirjutasid.

109
00:06:30,300 --> 00:06:35,240
Mida veel ei GDB lase sul teha? Jah? [Student vastus, arusaamatult]

110
00:06:35,240 --> 00:06:38,100
Prindi muutujad. Nii et kui sa tahad teha vähe enesevaatluse sees oma programmi

111
00:06:38,100 --> 00:06:41,500
ilma et oleks vaja kasutada kirjutamise printf avaldusi üle kogu koht,

112
00:06:41,500 --> 00:06:44,600
Sa võid printida muutuja või kuvada muutuja.

113
00:06:44,600 --> 00:06:46,710
Mida saab teha siluri nagu GDB?

114
00:06:46,710 --> 00:06:49,170
[Student vastus, arusaamatult]

115
00:06:49,170 --> 00:06:52,080
Täpselt. Saate määrata murdepunktid; võite öelda pausi täitmine

116
00:06:52,080 --> 00:06:54,020
kell põhiülesanne või suva funktsioon.

117
00:06:54,020 --> 00:06:56,800
Võite öelda pausi täitmine real 123.

118
00:06:56,800 --> 00:06:58,950
Ja murdepunktid on tõesti võimas tehnika

119
00:06:58,950 --> 00:07:01,110
sest kui sul on üldises mõttes kui sinu probleem

120
00:07:01,110 --> 00:07:05,360
ilmselt on, sa ei pea aega raiskama astutakse läbi programmi tervikuna.

121
00:07:05,360 --> 00:07:08,250
Võite sisuliselt hüpata seal ja siis alustage tippimist -

122
00:07:08,250 --> 00:07:10,970
astutakse läbi see samm või järgmisel vms.

123
00:07:10,970 --> 00:07:14,340
Aga saak koos midagi GDB on see, et see teid aitab, inimeste,

124
00:07:14,340 --> 00:07:16,940
leida oma probleeme ja leida oma vigu.

125
00:07:16,940 --> 00:07:19,470
See ei pruugi tingimata leida neid nii palju teile.

126
00:07:19,470 --> 00:07:23,070
>> Nii et me tutvustas teisel päeval style50, mis on lühikese käsureatööriist

127
00:07:23,070 --> 00:07:27,500
mis üritab Tyylitellä oma koodi veidi puhtamalt kui sina, inimene, võib-olla teha.

128
00:07:27,500 --> 00:07:29,530
Aga see, liiga, on tõesti ainult esteetiline asi.

129
00:07:29,530 --> 00:07:34,110
Aga selgub seal on see teine ​​tööriist nimega Valgrind, mis on veidi rohkem keerulisse kasutada.

130
00:07:34,110 --> 00:07:36,860
Selle tulemused on atrociously segasena esimesel pilgul.

131
00:07:36,860 --> 00:07:39,420
Aga see on imeliselt kasulik, eriti nüüd, kui me oleme osa mõiste

132
00:07:39,420 --> 00:07:43,080
kus sa oled hakanud kasutama malloc ja dünaamiline mälu eraldamisel.

133
00:07:43,080 --> 00:07:45,420
Asjad võivad minna väga, väga vale kiiresti.

134
00:07:45,420 --> 00:07:49,320
Sest kui te unustate tasuta oma mälu, või sa dereference mõned NULL pointer,

135
00:07:49,320 --> 00:07:55,770
või sa dereference mõned prügi osuti, mis on tavaliselt sümptom, et tulemused?

136
00:07:55,770 --> 00:07:59,470
Seg süü. Ja sa saad selle tuum faili teatud arvu kilobaiti või megabaiti

137
00:07:59,470 --> 00:08:02,990
et esindab riiki oma programmi mällu kui see alla kukkus,

138
00:08:02,990 --> 00:08:05,730
kuid oma programmi lõpuks seg vead, killustatust süü,

139
00:08:05,730 --> 00:08:08,450
mis tähendab midagi halba juhtunud peaaegu alati seotud

140
00:08:08,450 --> 00:08:11,750
et mälu seotud viga, mis sa tegid kuskil.

141
00:08:11,750 --> 00:08:14,100
Nii Valgrind aitab teil leida selliseid asju.

142
00:08:14,100 --> 00:08:17,720
See on vahend, et sa jooksed, nagu GDB, kui olete koostanud oma programmi,

143
00:08:17,720 --> 00:08:20,330
kuid mitte käivitada oma programmi otse, sa jooksed Valgrind

144
00:08:20,330 --> 00:08:23,960
ja te kaotate seda oma programmi, nagu te teete GDB.

145
00:08:23,960 --> 00:08:26,220
Nüüd kasutamine, et saada parim liiki toodangut,

146
00:08:26,220 --> 00:08:30,410
on veidi pikk, nii et seal atop ekraani näed Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" peaaegu universaalselt tähendab verbose kui te kasutate programme Linuxi arvuti.

148
00:08:35,350 --> 00:08:38,770
Nii et see tähendab sülitama rohkem andmeid kui võite vaikimisi.

149
00:08:38,770 --> 00:08:45,510
"- Lekke-check = täis." See on lihtsalt öeldes kontroll kõigi võimalike mälu lekked,

150
00:08:45,510 --> 00:08:49,430
vigu, mida ma oleks võinud teha. Ka see on ühine paradigma Linux programmid.

151
00:08:49,430 --> 00:08:52,710
Üldiselt, kui sul on käsurea argument see "lüliti",

152
00:08:52,710 --> 00:08:55,830
See peaks muutma programmi käitumine, ja see on üks täht,

153
00:08:55,830 --> 00:09:00,310
see-V, kuid kui see on sisse lülitatud, lihtsalt disain programmeerija,

154
00:09:00,310 --> 00:09:05,150
on terve sõna või mitu sõna, käsurea argument algab -.

155
00:09:05,150 --> 00:09:08,190
Need on vaid inimese konventsioonid, aga näete neid järjest.

156
00:09:08,190 --> 00:09:12,410
Ja siis lõpuks, "a.out" on meelevaldne nimi programm sellel konkreetsel juhul.

157
00:09:12,410 --> 00:09:14,640
Ja siin on mõned esindaja väljund.

158
00:09:14,640 --> 00:09:22,890
>> Enne vaatame, mida see võiks tähendada, lase mul minna üle koodilõik siin.

159
00:09:22,890 --> 00:09:26,390
Ja lubage mul liigutada välja viis, varsti,

160
00:09:26,390 --> 00:09:32,120
ja võtame pilk memory.c, mis on selle lühikese näiteks siin.

161
00:09:32,120 --> 00:09:36,290
Nii et selles programmis, las ma suumida ülesanded ja küsimused.

162
00:09:36,290 --> 00:09:39,430
Meil on funktsiooni main, mis nõuab funktsiooni, f,

163
00:09:39,430 --> 00:09:45,590
ja siis mida see f edasi teha, pisut tehnilist inglise keelt?

164
00:09:45,590 --> 00:09:49,760
Mis f edasi teha?

165
00:09:49,760 --> 00:09:53,680
Kuidas ma alustan rida 20 ja tähtede asukohta ei ole oluline,

166
00:09:53,680 --> 00:09:56,720
kuid ma lihtsalt olla järjekindel siin viimane loeng.

167
00:09:56,720 --> 00:09:59,910
Mis rida 20 teha meie jaoks? Vasakul küljel. Me jaotada see veelgi.

168
00:09:59,910 --> 00:10:02,410
Int * x: mida see teeb?

169
00:10:02,410 --> 00:10:04,940
Okei. See kuulutab pointer, ja nüüd olgem veelgi tehniline.

170
00:10:04,940 --> 00:10:10,230
Mis see tähendab, väga konkreetselt, kuulutada pointer? Keegi teine?

171
00:10:10,230 --> 00:10:15,050
Jah? [Student vastus, arusaamatult] Liiga kaugele.

172
00:10:15,050 --> 00:10:17,060
Nii et sa loed paremal servas võrdusmärk.

173
00:10:17,060 --> 00:10:20,290
Olgem keskenduda ainult vasakul, just int * x.

174
00:10:20,290 --> 00:10:24,700
See "kuulutab" pointer, kuid nüüd olgem sukelduda sügavamale sellele.

175
00:10:24,700 --> 00:10:28,330
Mida see konkreetselt, tehniliselt tähendab? Jah?

176
00:10:28,330 --> 00:10:31,940
[Student vastus, arusaamatult]

177
00:10:31,940 --> 00:10:35,090
Okei. See valmistab säästa aadress mällu.

178
00:10:35,090 --> 00:10:40,680
Hea. Ja võtame selle ühe sammu edasi, see on, mis kuulutab muutuja x, mis on 32 bitti.

179
00:10:40,680 --> 00:10:44,440
Ja ma tean, et see 32 bitti, sest -?

180
00:10:44,440 --> 00:10:47,390
See ei ole, sest see on keskmine, sest see on osuti käesoleval juhul.

181
00:10:47,390 --> 00:10:49,650
Juhus, et see on üks ja sama int,

182
00:10:49,650 --> 00:10:51,970
kuid asjaolu, et seal on täht seal tähendab see pointer

183
00:10:51,970 --> 00:10:57,300
ja aparaat, nagu paljude arvutitega, kuid mitte kõik, osuti on 32 bitti.

184
00:10:57,300 --> 00:11:01,850
On moodsam riist nagu viimased Mac, hiljemalt arvutid, mida oleks võinud 64-bitine suunanäitajaks,

185
00:11:01,850 --> 00:11:04,160
kuid seadme, need asjad on 32 bitti.

186
00:11:04,160 --> 00:11:08,380
Nii et me ühtlustada selle kohta. Täpsemalt räägitakse järgmiselt:

187
00:11:08,380 --> 00:11:10,820
Me "kuulutab" osuti; mida see tähendab?

188
00:11:10,820 --> 00:11:12,810
Valmistame salvestada mälu aadressi.

189
00:11:12,810 --> 00:11:15,530
Mida see tähendab?

190
00:11:15,530 --> 00:11:19,810
Loome muutuja nimega x, et kulub 32 bitti

191
00:11:19,810 --> 00:11:23,810
et varsti salvestada aadress täisarv.

192
00:11:23,810 --> 00:11:26,470
Ja see on ilmselt umbes sama täpne kui saame.

193
00:11:26,470 --> 00:11:31,810
See on hea edasi liikuda lihtsustada maailma ja lihtsalt öelda kuulutada osuti nimetatakse x.

194
00:11:31,810 --> 00:11:35,380
Tuvastada pointer, kuid aru ja mõista, mis tegelikult toimub

195
00:11:35,380 --> 00:11:38,490
isegi lihtsalt need paar tähte.

196
00:11:38,490 --> 00:11:42,040
>> Nüüd, see on peaaegu veidi lihtsam, kuigi see on pikem väljend.

197
00:11:42,040 --> 00:11:48,160
Mis siis on see tee, mis on esile tõstetud nüüd: "malloc (10 * sizeof (int));" Jah?

198
00:11:48,160 --> 00:11:52,350
[Student vastus, arusaamatult]

199
00:11:52,350 --> 00:11:58,250
Hea. Ja ma võtan selle sealt. See eraldamise patakas mälu kümme täisarvud.

200
00:11:58,250 --> 00:12:02,190
Ja nüüd sukelduda pisut sügavamale, see on eraldamise patakas mälu kümme täisarvud.

201
00:12:02,190 --> 00:12:05,390
Mis on malloc siis tagasi?

202
00:12:05,390 --> 00:12:10,390
Aadress, et patakas, või, konkreetsemalt, aadress esimese baidi et patakas.

203
00:12:10,390 --> 00:12:14,080
Kuidas siis olen mina, programmeerija, et tean, kus see patakas mälu otsas?

204
00:12:14,080 --> 00:12:18,340
Ma tean, et see on piirnevad. Malloc määratluse järgi annab sulle külgnevas patakas mälu.

205
00:12:18,340 --> 00:12:21,240
Ei lüngad ta. Teil on juurdepääs iga bait selles patakas,

206
00:12:21,240 --> 00:12:26,760
tagasi seljad, aga kuidas ma tean, kus lõpuks selle tüki mälu on?

207
00:12:26,760 --> 00:12:28,850
Kui kasutate malloc? [Student vastus, arusaamatult] Hea.

208
00:12:28,850 --> 00:12:30,670
Sa ei tee seda. Te peate meeles pidama.

209
00:12:30,670 --> 00:12:35,960
Mul on meeles pidada, et ma kasutasin väärtus 10 ja ma isegi ei tundu olevat teinud, et siin.

210
00:12:35,960 --> 00:12:41,000
Aga lasub täielikult mulle. Strlen, mis me oleme saanud veidi sõltuv keelpillidele,

211
00:12:41,000 --> 00:12:45,860
töötab ainult tänu sellele konventsioonile võttes \ 0

212
00:12:45,860 --> 00:12:48,840
või see eriline nul iseloomu, NUL, lõpus stringi.

213
00:12:48,840 --> 00:12:51,740
See ei kehti aga lihtsalt suvalise mäluhulka.

214
00:12:51,740 --> 00:12:58,590
See on kuni teile. Nii et liin 20, siis jaotab patakas mälu

215
00:12:58,590 --> 00:13:02,590
et saab salvestada 10 täisarvud, samuti salvestab aadress esimene bait

216
00:13:02,590 --> 00:13:05,610
Selle tüki mälu muutuja nimega x.

217
00:13:05,610 --> 00:13:11,140
Ergo, mis on osuti. Nii et liin 21, kahjuks oli viga.

218
00:13:11,140 --> 00:13:16,110
Aga kõigepealt, mida ta teeb? See ütleb poe asukoht 10, 0 indekseeritud,

219
00:13:16,110 --> 00:13:19,480
on patakas mälu nimetatakse x väärtus 0.

220
00:13:19,480 --> 00:13:21,510
>> Nii märkate paar asja on pooleli.

221
00:13:21,510 --> 00:13:25,420
Isegi x on pointer, mäletate paar nädalat tagasi

222
00:13:25,420 --> 00:13:29,440
et saate siiski kasutada massiivi stiilis nurksulg märke.

223
00:13:29,440 --> 00:13:36,180
Sest see on tegelikult lühiajaline küljest märke rohkem segasena suunatud pointer aritmeetika.

224
00:13:36,180 --> 00:13:40,320
kus me teeks midagi sellist: Võtke aadress x, liikuda 10 laigud üle,

225
00:13:40,320 --> 00:13:44,550
siis sinna minna, et mis iganes aadress salvestatakse selles kohas.

226
00:13:44,550 --> 00:13:48,090
Aga ausalt öeldes, see on lihtsalt jõle lugeda ja saada rahul.

227
00:13:48,090 --> 00:13:52,900
Nii et maailm kasutab tavaliselt nurksulgudesse lihtsalt seetõttu, et nii palju inim-sõbralik lugeda.

228
00:13:52,900 --> 00:13:55,140
Aga see, mis tegelikult toimub all kapuuts;

229
00:13:55,140 --> 00:13:58,190
x on aadress, mitte massiiv, iseenesest.

230
00:13:58,190 --> 00:14:02,410
Nii et see on hoidmiseks 0. asukohta 10 x.

231
00:14:02,410 --> 00:14:06,120
Miks on see halb? Jah?

232
00:14:06,120 --> 00:14:17,370
[Student vastus, arusaamatult] Täpselt.

233
00:14:17,370 --> 00:14:21,100
Me ainult eraldatud 10 ints, kuid me loota 0 kui Programmeerimine C,

234
00:14:21,100 --> 00:14:25,690
nii et teil on juurdepääs 0 1 2 3 4 5 6 7 8 9, kuid mitte 10.

235
00:14:25,690 --> 00:14:30,270
Nii et kas programm läheb SEG süü või see ei ole.

236
00:14:30,270 --> 00:14:32,900
Aga me ei tea, see on omamoodi mittedetermineeritud käitumist.

237
00:14:32,900 --> 00:14:35,600
On tõesti sõltub, kas meil veab.

238
00:14:35,600 --> 00:14:40,650
Kui selgub, et operatsioonisüsteem ei pahanda, kui ma kasutan seda pildi bait,

239
00:14:40,650 --> 00:14:43,360
kuigi see pole andnud seda mulle, mu programm ei pruugi krahhi.

240
00:14:43,360 --> 00:14:46,780
See on toores, see on lollakas, aga sa ei pruugi näha, et sümptom,

241
00:14:46,780 --> 00:14:48,960
või võite näha seda ainult üks kord samal ajal.

242
00:14:48,960 --> 00:14:51,230
Kuid reaalsus on see, et viga on tegelikult olemas.

243
00:14:51,230 --> 00:14:54,320
Ja see on tõesti problemaatiline, kui olete kirjutanud programmi, mis sa tahad olla õige,

244
00:14:54,320 --> 00:14:58,840
et olete müünud ​​programm, et inimesed kasutavad, et iga kord samal ajal jookseb

245
00:14:58,840 --> 00:15:02,450
sest muidugi, see ei ole hea. Tegelikult, kui sul on Android telefon või iPhone

246
00:15:02,450 --> 00:15:05,550
ja sa alla laadida apps nendel päevadel, kui sa oled kunagi olnud app lihtsalt loobuda,

247
00:15:05,550 --> 00:15:10,040
äkki kaob see, mis on peaaegu alati tingitud mõnede mälu seotud probleem,

248
00:15:10,040 --> 00:15:12,830
kusjuures programmeerija silmamunad ja dereferenced pointer

249
00:15:12,830 --> 00:15:18,670
et ta ei peaks, ja tulemus iOS või Android on lihtsalt tappa programmi kokku

250
00:15:18,670 --> 00:15:23,080
mitte riski määratlemata käitumine või mingi turvalisuse kompromiss.

251
00:15:23,080 --> 00:15:25,950
>> On veel üks viga selles programmis peale selle ühe.

252
00:15:25,950 --> 00:15:30,180
Mida muud ma olen silmamunad selle programmiga?

253
00:15:30,180 --> 00:15:32,740
Ma ei ole harjutanud mida ma olen kuulutanud. Jah?

254
00:15:32,740 --> 00:15:34,760
[Student vastus, arusaamatult] Hea.

255
00:15:34,760 --> 00:15:36,880
Ma ei ole vabanenud mälu. Nii rusikareegel nüüd

256
00:15:36,880 --> 00:15:43,150
peab olema millal helistada malloc, peate helistama tasuta, kui olete teinud kasutades, et mälu.

257
00:15:43,150 --> 00:15:45,610
Nüüd, kui ma tahan, et vabastada see mälu?

258
00:15:45,610 --> 00:15:49,780
Tõenäoliselt, eeldades see esimene rida oli õige, ma tahan seda teha siin.

259
00:15:49,780 --> 00:15:55,710
Sest ma ei saanud näiteks seda siin all. Miks?

260
00:15:55,710 --> 00:15:57,860
Lihtsalt välja ulatus. Nii et kuigi me räägime suunanäitajaks,

261
00:15:57,860 --> 00:16:04,830
See on nädal 2 või 3 küsimust, kus x on ainult ulatuse sees looksulg kus see on deklareeritud.

262
00:16:04,830 --> 00:16:11,000
Nii et sa kindlasti ei saa vabastada seal. Minu ainus võimalus vabastada see on umbes pärast rida 21.

263
00:16:11,000 --> 00:16:15,170
See on üsna lihtne programm, see oli üsna lihtne, kui sa selline pakitud meelt

264
00:16:15,170 --> 00:16:17,870
ümber, mida programm teeb, kus vigu.

265
00:16:17,870 --> 00:16:20,500
Ja isegi kui sa ei näinud seda alguses, loodetavasti see on natuke ilmne nüüd

266
00:16:20,500 --> 00:16:23,870
et need vead on üsna lihtne lahendada ja lihtne teha.

267
00:16:23,870 --> 00:16:28,720
Aga kui programm on rohkem kui 12 rida pikk, see on 50 rida pikk, 100 rida pikk,

268
00:16:28,720 --> 00:16:31,150
jalgsi läbi oma koodi rida realt, läbi mõelda loogiliselt,

269
00:16:31,150 --> 00:16:35,110
on võimalik, kuid mitte eriti lõbus teha, pidevalt otsivad vigu,

270
00:16:35,110 --> 00:16:38,340
ja see on ka raske teha, ja sellepärast tööriista nagu Valgrind olemas.

271
00:16:38,340 --> 00:16:40,900
Lubage mul minna ja teha nii: lase mul avada minu terminaliakent,

272
00:16:40,900 --> 00:16:45,400
ja andke mulle mitte lihtsalt käivitada mälu, sest mälu pole midagi viga.

273
00:16:45,400 --> 00:16:49,180
Ma saan õnnelik. Lähen, et täiendav baidi lõpus massiivi

274
00:16:49,180 --> 00:16:51,060
ei tundu olevat liiga problemaatiline.

275
00:16:51,060 --> 00:16:56,370
Aga las ma siiski, teha meelerahu kontroll, mis tähendab lihtsalt, et kontrollida

276
00:16:56,370 --> 00:16:58,320
kas see on tegelikult õige.

277
00:16:58,320 --> 00:17:04,690
>> Teeme valgrind-V - lekke-check = täis,

278
00:17:04,690 --> 00:17:07,520
ja siis programmi nimi on sel juhul mälu, ei a.out.

279
00:17:07,520 --> 00:17:10,760
Nii et lubage mul minna ja seda teha. Enter.

280
00:17:10,760 --> 00:17:14,109
Kallis Jumal. See on oma toodang ja seda ma viitas varem.

281
00:17:14,109 --> 00:17:17,550
Aga kui sa õpid, et lugeda läbi kõik jama siin,

282
00:17:17,550 --> 00:17:20,760
enamus sellest on lihtsalt diagnostika väljund, et ei ole nii huvitav.

283
00:17:20,760 --> 00:17:24,829
Mis silma tahab otsivad on üldse mainimata viga või kehtetu.

284
00:17:24,829 --> 00:17:26,800
Sõnad, mis viitavad probleemidele.

285
00:17:26,800 --> 00:17:29,340
Ja tõepoolest, vaatame mis toimub vale siin.

286
00:17:29,340 --> 00:17:35,230
Mul on kokkuvõte mingi "kasutusel väljumise: 40 baiti 1 plokke."

287
00:17:35,230 --> 00:17:38,750
Ma ei ole tegelikult kindel, mida plokk on veel, kuid 40 baiti

288
00:17:38,750 --> 00:17:41,260
tegelikult tundub, nagu ma võiks aru saada, kus see on pärit.

289
00:17:41,260 --> 00:17:45,030
40 baiti. Miks on 40 baiti kasutusel väljumise?

290
00:17:45,030 --> 00:17:48,780
Ja täpsemalt, kui me keri siin,

291
00:17:48,780 --> 00:17:54,520
miks ma kindlasti kaotanud 40 baiti? Jah?

292
00:17:54,520 --> 00:17:59,520
[Student vastus, arusaamatult] Perfect. Jah, täpselt.

293
00:17:59,520 --> 00:18:03,540
Seal oli 10 täisarvud ja kõik need on suurus 4, või 32 bitti,

294
00:18:03,540 --> 00:18:08,300
nii et ma kaotasin just 40 baiti, sest nagu sa ettepanek, ma ei ole kutsutud tasuta.

295
00:18:08,300 --> 00:18:13,460
See on üks viga, ja nüüd vaatame allapoole veel veidi ja vaata kõrval see,

296
00:18:13,460 --> 00:18:16,900
"Vigane kirjutame suurus 4". Nüüd mis see on?

297
00:18:16,900 --> 00:18:21,150
See aadress on väljendatud mida baasi märke, ilmselt?

298
00:18:21,150 --> 00:18:23,640
See on kuueteistkümnendsüsteemis, ja iga kord, kui näen mitmeid alustades 0x,

299
00:18:23,640 --> 00:18:29,410
see tähendab kuueteistkümnendsüsteemi, mis me tegime nii tagasi, ma arvan, pset 0-osa küsimused,

300
00:18:29,410 --> 00:18:34,090
mis oli lihtsalt teha soojendus liikumine, teisendades koma Hex kahekomponentsete jne.

301
00:18:34,090 --> 00:18:39,220
Kuueteistkümnendsüsteemi, lihtsalt inimeste konventsiooni, mida tavaliselt kasutatakse esindama viiteid

302
00:18:39,220 --> 00:18:41,570
või üldisemalt tegeleb. See on lihtsalt printsiibist,

303
00:18:41,570 --> 00:18:45,340
sest see on natuke lihtsam lugeda, see on veidi kompaktsem kui midagi koma,

304
00:18:45,340 --> 00:18:47,720
ja binaarne on kasutu kõige inimestel kasutada.

305
00:18:47,720 --> 00:18:50,840
Nii et nüüd mida see tähendab? Noh, tundub, et seal on kehtetu kirjutada

306
00:18:50,840 --> 00:18:54,480
suurus 4 rida 21 memory.c.

307
00:18:54,480 --> 00:18:59,180
Nii et lähme tagasi liin 21, ja tõepoolest, siin on see, et vigane kirjutada.

308
00:18:59,180 --> 00:19:02,640
Nii Valgrind ei kavatse täiesti hoidke mu kätt ja ütle mulle, mida fix on

309
00:19:02,640 --> 00:19:05,520
kuid see on avastada, et ma teen vale kirjutada.

310
00:19:05,520 --> 00:19:08,800
Ma puudutan 4 baiti, et ma ei tohiks olla, ja ilmselt ongi, sest,

311
00:19:08,800 --> 00:19:13,960
nagu olete rõhutanud, ma teen [10] asemel [9] maksimaalselt

312
00:19:13,960 --> 00:19:16,660
või [0] või midagi vahepealset.

313
00:19:16,660 --> 00:19:19,690
Mis Valgrind, aru igal ajal sa nüüd kirjutamise programm

314
00:19:19,690 --> 00:19:24,190
mis kasutab viiteid ja kasutab mälu, ja malloc täpsemalt

315
00:19:24,190 --> 00:19:27,080
Kindlasti satuvad harjumus töötab nii kaua

316
00:19:27,080 --> 00:19:30,890
kuid väga kergesti kopeerida ja kleepida käsu Valgrind

317
00:19:30,890 --> 00:19:32,650
et näha, kas seal on mõned vead seal.

318
00:19:32,650 --> 00:19:34,820
Ja see saab olema valdav iga kord näed väljund,

319
00:19:34,820 --> 00:19:39,430
aga lihtsalt sõeluda läbi visuaalselt kogu võimsuse ja vaata, kas näed mainib vigu

320
00:19:39,430 --> 00:19:43,190
või hoiatusi või vigane või kadunud.

321
00:19:43,190 --> 00:19:46,200
Kõik sõnad, mis kõlavad nagu te silmamunad kusagil.

322
00:19:46,200 --> 00:19:48,580
Nii mõistame, et see on uus vahend oma tööriistakomplekti.

323
00:19:48,580 --> 00:19:51,270
>> Nüüd esmaspäeval oli meil terve hunnik inimesed siia tulla

324
00:19:51,270 --> 00:19:53,150
ja esindada mõiste seotud nimekirja.

325
00:19:53,150 --> 00:20:00,970
Ja me tutvustas seotud nimekirja lahendusena mida probleem?

326
00:20:00,970 --> 00:20:04,590
Jah? [Student vastus, arusaamatult] Hea.

327
00:20:04,590 --> 00:20:06,530
Massiivid ei saa mälu lisamist.

328
00:20:06,530 --> 00:20:09,440
Kui te eraldada massiivi suurus 10, see on kõik, mida saan.

329
00:20:09,440 --> 00:20:13,690
Teil on võimalik helistada funktsioon nagu RealLOC kui sa algselt nimega malloc,

330
00:20:13,690 --> 00:20:17,580
ja et võib proovida kasvatada massiivi kui on ruumi lõpu poole see

331
00:20:17,580 --> 00:20:21,610
et keegi teine ​​kasutab, ja kui seal ei ole, siis lihtsalt leida suurem patakas kusagil mujal.

332
00:20:21,610 --> 00:20:25,040
Aga siis kopeerib kõik need baidid uude massiivi.

333
00:20:25,040 --> 00:20:28,310
See kõlab väga õige lahendus.

334
00:20:28,310 --> 00:20:34,790
Miks on see ebameeldiv?

335
00:20:34,790 --> 00:20:36,940
Ma mõtlen see toimib, inimesed on lahendanud selle probleemi.

336
00:20:36,940 --> 00:20:40,710
Miks me peame seda lahendada esmaspäeval seotud nimekirjad? Jah?

337
00:20:40,710 --> 00:20:44,060
[Student vastus, arusaamatult] See võib võtta kaua aega.

338
00:20:44,060 --> 00:20:49,260
Tegelikult igal ajal olete helistaja malloc või RealLOC või calloc, mis on veel teine,

339
00:20:49,260 --> 00:20:52,470
iga kord, kui programm, räägime operatsioonisüsteemi,

340
00:20:52,470 --> 00:20:54,310
siis kipuvad aeglustada programmi alla.

341
00:20:54,310 --> 00:20:57,470
Ja kui sa teed selliseid asju silmad, sa oled tõesti aeglustub asju ette.

342
00:20:57,470 --> 00:21:00,740
Sa ei lähe märgata seda kõige lihtsam "Hello World" tüüpi programme,

343
00:21:00,740 --> 00:21:04,300
aga märksa suuremates programmides, paludes operatsioonisüsteemi ja jälle mälu

344
00:21:04,300 --> 00:21:07,520
või andes talle ikka ja jälle tagasi kipub mitte olema hea.

345
00:21:07,520 --> 00:21:11,210
Plus, see on lihtsalt omamoodi intellektuaalselt - see on täielik ajaraiskamine.

346
00:21:11,210 --> 00:21:16,490
Miks eraldada rohkem ja rohkem mälu, riski kopeerimine kõike uude massiivi

347
00:21:16,490 --> 00:21:21,980
kui teil on alternatiiv, mis võimaldab teil eraldada ainult nii palju mälu sa tegelikult vajad?

348
00:21:21,980 --> 00:21:24,130
Nii et seal on plussid ja miinused siit.

349
00:21:24,130 --> 00:21:26,730
Üks plussid on see, et meil on dünaamilisust.

350
00:21:26,730 --> 00:21:29,100
Vahet pole, kus mäluhulka on, mis on tasuta,

351
00:21:29,100 --> 00:21:32,070
Võin lihtsalt omamoodi luua nende leivapuru kaudu lähtekohtadeks

352
00:21:32,070 --> 00:21:34,470
string kogu mu lingitud nimekiri koos.

353
00:21:34,470 --> 00:21:36,470
Aga ma maksan vähemalt ühe hinnaga.

354
00:21:36,470 --> 00:21:40,060
>> Mida ma pean loobuma omandada seotud nimekirjad?

355
00:21:40,060 --> 00:21:42,470
Jah? [Student vastus, arusaamatult] Hea.

356
00:21:42,470 --> 00:21:45,650
Sa pead rohkem mälu. Nüüd on mul vaja ruumi neid viiteid,

357
00:21:45,650 --> 00:21:47,900
ja juhul, kui see super lihtne seotud nimekirja

358
00:21:47,900 --> 00:21:51,410
et on ainult üritab salvestada täisarvud, mis on 4 baiti, me ütleme

359
00:21:51,410 --> 00:21:54,240
Noh, osuti on 4 baiti, nii et nüüd ma olen sõna otseses mõttes kahekordistunud

360
00:21:54,240 --> 00:21:57,290
mälu mul on vaja lihtsalt hoida seda nimekirja.

361
00:21:57,290 --> 00:21:59,680
Aga jälle, see on pidev Miinuseks infotehnoloogia

362
00:21:59,680 --> 00:22:03,440
vahel ajas ja ruumis ja areng, jõudu ja muid ressursse.

363
00:22:03,440 --> 00:22:06,630
Mis on teine ​​negatiivne külg kasutades seotud loetelu? Jah?

364
00:22:06,630 --> 00:22:10,150
[Student vastus, arusaamatult]

365
00:22:10,150 --> 00:22:12,600
Hea. Ei ole nii lihtne ligi pääseda. Me ei saa enam võimendada

366
00:22:12,600 --> 00:22:15,530
nädal 0 põhimõtteid nagu jaga ja valitse.

367
00:22:15,530 --> 00:22:18,220
Ja täpsemalt, binaarne otsing. Sest kuigi me inimestele

368
00:22:18,220 --> 00:22:20,400
näete jämedalt kus keset seda nimekirja on

369
00:22:20,400 --> 00:22:25,840
arvuti ainult teab, et see on seotud nimekirja algab aadress helistama.

370
00:22:25,840 --> 00:22:28,250
Ja see on 0x123 või midagi sellist.

371
00:22:28,250 --> 00:22:30,990
Ja ainus viis programmi leida keset element

372
00:22:30,990 --> 00:22:33,350
on tegelikult otsida kogu nimekiri.

373
00:22:33,350 --> 00:22:35,500
Ja isegi siis, see sõna on otsida kogu nimekiri, sest

374
00:22:35,500 --> 00:22:38,950
isegi kui jõuad keskel element järgides suunanäitajaks,

375
00:22:38,950 --> 00:22:42,380
te, programmi, ei tea, kui kaua see nimekiri on potentsiaalselt

376
00:22:42,380 --> 00:22:45,250
kuni jõuate lõpuks see, ja kuidas sa tead, programmiliselt

377
00:22:45,250 --> 00:22:48,600
et sa oled lõpus seotud nimekirja?

378
00:22:48,600 --> 00:22:51,120
Seal on spetsiaalne NULL pointer, nii et jällegi konventsiooni.

379
00:22:51,120 --> 00:22:53,870
Selle asemel, et kasutada selle osuti, me kindlasti ei taha ta olla mõne prügi väärtus

380
00:22:53,870 --> 00:22:57,750
juhtides lavalt kuhugi, me tahame seda käe ette, NULL,

381
00:22:57,750 --> 00:23:01,530
nii et meil on see lõpp selles andmestruktuur nii et me teame, kus see lõpeb.

382
00:23:01,530 --> 00:23:03,410
>> Mis siis, kui me tahame muuta seda?

383
00:23:03,410 --> 00:23:05,980
Me tegime kõige selle visuaalselt, ja inimestega,

384
00:23:05,980 --> 00:23:07,630
aga mis siis, kui me tahame teha sisestamist?

385
00:23:07,630 --> 00:23:12,360
Nii esialgses nimekirjas oli 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Mis siis, kui me siis tahtsime malloc ruumi number 55, sõlm see,

387
00:23:16,730 --> 00:23:20,730
ja siis me tahame lisada 55 soodusravimite loetellu lihtsalt nagu tegime esmaspäeval?

388
00:23:20,730 --> 00:23:23,690
Kuidas me seda teeme? Noh, Anita tulid ja ta sisuliselt kõndis nimekirja.

389
00:23:23,690 --> 00:23:27,500
Ta alustas esimese osa, siis järgmine, järgmine, järgmine, järgmine, järgmine.

390
00:23:27,500 --> 00:23:29,500
Lõpuks tabas vasakpoolne täiesti alla

391
00:23:29,500 --> 00:23:34,480
ja mõistsin, oh, see on NULL. Mida pointer manipuleerimine vaja teha?

392
00:23:34,480 --> 00:23:37,980
Isik, kes oli lõpuks number 34, mis on vajalik tema vasak käsi tõsta

393
00:23:37,980 --> 00:23:46,220
punkti 55, 55 vaja oma vasaku käe suunaga allapoole tuleb uus NULL terminaator. Valmis.

394
00:23:46,220 --> 00:23:49,540
Päris lihtne lisada 55 arvesse järjestatud nimekirja.

395
00:23:49,540 --> 00:23:51,800
Ja kuidas võiks see välja näeb?

396
00:23:51,800 --> 00:23:55,690
>> Lubage mul minna ja avada mõned koodi näiteks siin.

397
00:23:55,690 --> 00:23:58,120
Avan gedit, ja lubage mul avada kaks faili esimene.

398
00:23:58,120 --> 00:24:02,050
Üks on list1.h, ja lubage mul meelde tuletada, et see oli patakas kood

399
00:24:02,050 --> 00:24:04,920
et me kujutamiseks kasutatakse sõlme.

400
00:24:04,920 --> 00:24:13,040
Sõlm on nii int nimetatakse n ja osuti nimetas tuleva et lihtsalt punkte Järgmine asi nimekirjas.

401
00:24:13,040 --> 00:24:15,450
See on nüüd. H faili. Miks?

402
00:24:15,450 --> 00:24:19,090
Seal on käesoleva konventsiooni, ja me ei ole seda ära tohutu end,

403
00:24:19,090 --> 00:24:22,220
aga inimene, kes kirjutas printf ja muud funktsioonid

404
00:24:22,220 --> 00:24:27,150
kinkis maailmale, kõik need funktsioonid, kirjutades faili nimega stdio.h.

405
00:24:27,150 --> 00:24:30,950
Ja siis on string, ja siis seal on map.h, ja seal on kõik need h failid

406
00:24:30,950 --> 00:24:34,410
et te olete näinud või kasutatud tähtaja jooksul kirjaliku teistele inimestele.

407
00:24:34,410 --> 00:24:38,470
Tavaliselt nendes. H failid on ainsad asjad, nagu typedefs

408
00:24:38,470 --> 00:24:42,310
või deklaratsioonide oma tüüpe või deklaratsioonide konstandid.

409
00:24:42,310 --> 00:24:47,890
Sa ei pane funktsioonid "realisatsioonid päisefaile.

410
00:24:47,890 --> 00:24:50,570
Sa panid selle asemel lihtsalt oma prototüübid.

411
00:24:50,570 --> 00:24:53,050
Paned asjad, mida soovite jagada maailma, mida nad vajavad

412
00:24:53,050 --> 00:24:55,640
selleks, et koguda oma kood. Nii lihtsalt sattuda see harjumus,

413
00:24:55,640 --> 00:24:59,110
me otsustasime teha sama asja. Seal ei ole palju list1.h,

414
00:24:59,110 --> 00:25:02,070
kuid me oleme panna midagi, mis võiks huvi pakkuda inimestele maailmas

415
00:25:02,070 --> 00:25:05,030
kes tahavad kasutada meie seotud nimekirja rakendamist.

416
00:25:05,030 --> 00:25:08,040
Nüüd, list1.c, ma ei lähe läbi kogu see asi

417
00:25:08,040 --> 00:25:11,390
sest see on natuke pikk, see programm, kuid olgem kestab see päris kiiresti käsureale.

418
00:25:11,390 --> 00:25:15,720
Lubage mul koostada List1, las ma siis kestab List1, ja mida te näete on

419
00:25:15,720 --> 00:25:18,070
oleme simuleeritud lihtne väike programm siin

420
00:25:18,070 --> 00:25:20,990
et läheb lubage mul lisada ja eemaldada numbrite nimekiri.

421
00:25:20,990 --> 00:25:24,310
Nii et lubage mul minna ja tüüp 3 menüüvalikut 3.

422
00:25:24,310 --> 00:25:27,880
Ma tahan sisestada number - teeme esimese numbri, mis oli 9,

423
00:25:27,880 --> 00:25:30,550
ja nüüd ma olen kuulnud, nimekiri on nüüd 9.

424
00:25:30,550 --> 00:25:33,760
Lubage mul minna ja teha teine ​​sisestamise, nii et ma tabanud menüü 3. variant.

425
00:25:33,760 --> 00:25:36,760
Mis number ma tahan lisada? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Ja ma teen veel üks.

427
00:25:39,220 --> 00:25:41,720
Lubage mul lisada number 22.

428
00:25:41,720 --> 00:25:45,850
Nii et meil on alguse seotud nimekirja, mis meil oli slaidi kujul hetk tagasi.

429
00:25:45,850 --> 00:25:48,740
Kuidas seda sisestamise tegelikult toimub?

430
00:25:48,740 --> 00:25:52,000
Tõepoolest, 22 on nüüd lõpuks nimekirjas.

431
00:25:52,000 --> 00:25:55,050
Nii et lugu me rääkisime laval esmaspäeval ja recapped lihtsalt nüüd

432
00:25:55,050 --> 00:25:57,460
tuleb tegelikult toimub kood.

433
00:25:57,460 --> 00:25:59,700
Võtame pilk. Las ma kerin alla see fail.

434
00:25:59,700 --> 00:26:01,720
Me ilustada teatud funktsioone,

435
00:26:01,720 --> 00:26:05,630
aga me läheme, ütleme, sisestada funktsiooni.

436
00:26:05,630 --> 00:26:11,720
>> Vaatame, kuidas me lisada uus tipp sellesse seotud nimekirja.

437
00:26:11,720 --> 00:26:14,550
Kui on nimekiri kuulutatud? Noh, olgem liikuda kogu tee kuni ülaosas,

438
00:26:14,550 --> 00:26:19,970
ja märkate, et minu lingitud nimekiri on sisuliselt deklareeritakse ühe osutiga, mis on algselt NULL.

439
00:26:19,970 --> 00:26:23,180
Nii et ma kasutan globaalse muutuja siin, mis üldiselt oleme kuulutanud vastu

440
00:26:23,180 --> 00:26:25,280
sest see muudab oma koodi veidi räpane säilitada,

441
00:26:25,280 --> 00:26:29,080
See on omamoodi laisk, tavaliselt, kuid see ei ole laisk ja see pole vale ja see ei ole halb

442
00:26:29,080 --> 00:26:33,660
Kui teie programmi ainus eesmärk elus on simuleerida ühe seotud nimekirja.

443
00:26:33,660 --> 00:26:35,460
Mis on täpselt see, mida me teeme.

444
00:26:35,460 --> 00:26:39,100
Nii et pigem deklareerima selle peamine ja siis pea seda iga funktsioon

445
00:26:39,100 --> 00:26:42,640
oleme kirjutanud selle programmi, me mitte aru oh, lähme siis tee seda maailma

446
00:26:42,640 --> 00:26:47,060
sest kogu eesmärk on see programm on näidata ainult üks seotud nimekirja.

447
00:26:47,060 --> 00:26:50,700
Nii et tundub okei. Siin on minu prototüüpe, ja me ei lähe läbi kõik need,

448
00:26:50,700 --> 00:26:55,800
aga ma kirjutasin Kustutamise funktsiooni, leida funktsiooni sisestada funktsioon ja traavers funktsioon.

449
00:26:55,800 --> 00:26:59,080
Kuid olgem nüüd minna tagasi alla insertfunktsioonide

450
00:26:59,080 --> 00:27:01,490
ja näha, kuidas üks töötab siin.

451
00:27:01,490 --> 00:27:09,940
Lisa on joonel - siin me läheme.

452
00:27:09,940 --> 00:27:12,850
Lisa. Nii et see ei võta mingeid argumente, sest me ei kavatse küsida

453
00:27:12,850 --> 00:27:15,930
kasutaja sees seda funktsiooni arvu nad tahavad lisada.

454
00:27:15,930 --> 00:27:19,410
Aga kõigepealt, me valmistume andma neile ruumi.

455
00:27:19,410 --> 00:27:22,050
See on omamoodi kopeeri ja kleebi teise näite.

456
00:27:22,050 --> 00:27:25,110
Sel juhul olime eraldades int; seekord me eraldades sõlme.

457
00:27:25,110 --> 00:27:27,910
Ma tõesti ei mäleta, kui palju baite sõlm on, kuid sellest pole midagi.

458
00:27:27,910 --> 00:27:30,460
Sizeof saab aru, et minu jaoks.

459
00:27:30,460 --> 00:27:33,340
Ja miks ma kontrollimine NULL kooskõlas 120?

460
00:27:33,340 --> 00:27:37,530
Mis võiks minna valesti line 119? Jah?

461
00:27:37,530 --> 00:27:40,530
[Student vastus, arusaamatult]

462
00:27:40,530 --> 00:27:43,440
Hea. Lihtsalt võib juhtuda, et ma käskisin liiga palju mälu

463
00:27:43,440 --> 00:27:47,020
või et midagi on valesti ja operatsioonisüsteemi ei ole piisavalt baiti mulle,

464
00:27:47,020 --> 00:27:50,640
nii see annab nii palju, tagastades NULL, ja kui ma ei kontrollige, et

465
00:27:50,640 --> 00:27:54,710
ja ma lihtsalt pimesi edasi kasutada aadressi tagastatakse, võiks see olla NULL.

466
00:27:54,710 --> 00:27:58,400
See võiks olla mingi tundmatu väärtuse; ei ole hea kui ma -

467
00:27:58,400 --> 00:28:00,590
tegelikult ei ole tundmatu väärtus. See võib olla NULL, nii et ma ei taha

468
00:28:00,590 --> 00:28:02,550
kuritarvitama ja riskida viite mahavõtmine ta.

469
00:28:02,550 --> 00:28:07,410
Kui see juhtub, siis lihtsalt tagasi ja me teeskleme, et ma ei saanud tagasi kõik mälu üldse.

470
00:28:07,410 --> 00:28:12,270
>> Muidu ma ütlen kasutaja anna mulle number sisestada, ma kutsun meie vana sõber GetInt,

471
00:28:12,270 --> 00:28:15,530
ja siis see oli uus süntaks tutvustasime esmaspäeval.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n 'tähendab võtta aadress, mida andsid malloc

473
00:28:20,320 --> 00:28:23,490
mis on esimene bait uus sõlm objekti,

474
00:28:23,490 --> 00:28:26,860
ja siis lähevad põllule nimetatakse n.

475
00:28:26,860 --> 00:28:35,270
Väike trivia küsimus: See on samaväärne sellega, mis rohkem segasena rida koodi?

476
00:28:35,270 --> 00:28:38,110
Kuidas muidu oleks ma olen kirjutanud seda? Tahad võtta pussitada?

477
00:28:38,110 --> 00:28:41,480
[Student vastus, arusaamatult]

478
00:28:41,480 --> 00:28:44,870
Hea. Kasutades. N, kuid see ei ole päris nii lihtne.

479
00:28:44,870 --> 00:28:47,090
Mida ma kõigepealt tegema? [Student vastus, arusaamatult]

480
00:28:47,090 --> 00:28:52,730
Hea. Ma pean tegema * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Nii et see ütleb uus pointer on ilmselt aadress. Miks?

482
00:28:55,610 --> 00:28:59,520
Sest see tagastati malloc. * Newptr öeldes: "sinna minna"

483
00:28:59,520 --> 00:29:02,970
ja siis kui sa oled seal, siis saate rohkem tuttav. n

484
00:29:02,970 --> 00:29:05,730
kuid see lihtsalt tundub natuke kole, eriti kui meie, inimesed hakkavad

485
00:29:05,730 --> 00:29:10,360
juhtida vihjeid nooltega kogu aeg; maailmas on standardiseeritud selle noole märke,

486
00:29:10,360 --> 00:29:12,320
mis ei täpselt sama asi.

487
00:29:12,320 --> 00:29:16,070
Nii et kasutate ainult -> märke, kui asi vasakul on kursor.

488
00:29:16,070 --> 00:29:18,790
Vastasel juhul, kui see on tegelik struct, kasutage. N.

489
00:29:18,790 --> 00:29:25,800
Ja siis selline: Miks ma initsialiseerida newptr-> kõrval NULL?

490
00:29:25,800 --> 00:29:28,610
Me ei taha rippuvad vasakul off etapi lõpus.

491
00:29:28,610 --> 00:29:31,630
Me tahame, juhtides otse alla, mis tähendab lõpuks seda nimekirja

492
00:29:31,630 --> 00:29:34,980
võiks olla see sõlm, nii et me parem veenduge, et see on NULL.

493
00:29:34,980 --> 00:29:38,460
Ja üldiselt initsialiseerimisel oma muutujate või oma andmete kohal ja structs

494
00:29:38,460 --> 00:29:40,470
et midagi on lihtsalt hea tava.

495
00:29:40,470 --> 00:29:45,170
Lihtsalt lase prügi olemas ja on endiselt olemas üldiselt saab teid hätta

496
00:29:45,170 --> 00:29:48,650
kui te unustate midagi hiljem.

497
00:29:48,650 --> 00:29:51,590
>> Siin on mõned juhtumid. See omakorda on lisada funktsioon,

498
00:29:51,590 --> 00:29:54,930
ja esimene asi, mida ma kontrollida on, kui muutuja nimega esmalt

499
00:29:54,930 --> 00:29:58,240
et globaalse muutuja on NULL, mis tähendab, et ei ole seotud nimekirja.

500
00:29:58,240 --> 00:30:02,460
Me ei ole sisestatud ühtegi arvu, nii et see on triviaalne lisada see praegune number

501
00:30:02,460 --> 00:30:05,240
nimistusse, sest see lihtsalt kuulub alguses nimekirja.

502
00:30:05,240 --> 00:30:08,100
Nii et see oli siis, kui Anita oli just püsti siin üksi, teeseldes

503
00:30:08,100 --> 00:30:11,390
keegi oli siin laval kuni me eraldatud sõlme,

504
00:30:11,390 --> 00:30:13,940
siis ta võiks tõsta oma käsi esimest korda,

505
00:30:13,940 --> 00:30:17,420
kui kõik teised olid tulnud lavale pärast teda esmaspäeval.

506
00:30:17,420 --> 00:30:22,900
Nüüd siin on vähe kontrolli, kus ma pean ütlema, kui uus sõlm väärtus n

507
00:30:22,900 --> 00:30:27,370
on <väärtus n praeguses esimese sõlme,

508
00:30:27,370 --> 00:30:29,930
See tähendab, et on seotud nimekirja, mis on alanud.

509
00:30:29,930 --> 00:30:32,330
Seal on vähemalt üks tipp nimekirjas, kuid see uus kutt

510
00:30:32,330 --> 00:30:37,230
kuulub enne seda, seega peame liikuma asju ümber.

511
00:30:37,230 --> 00:30:43,450
Teisisõnu, kui loetelu on alanud lihtsalt, ütleme,

512
00:30:43,450 --> 00:30:48,100
lihtsalt number 17, see on - tegelikult, me saame seda teha selgemalt.

513
00:30:48,100 --> 00:30:56,010
Kui alustame meie lugu pointer siin nimetatakse esmalt

514
00:30:56,010 --> 00:30:59,870
ja esialgu on see NULL, ja me sisestada number 9,

515
00:30:59,870 --> 00:31:02,510
number 9 selgelt kuulub alguses nimekirja.

516
00:31:02,510 --> 00:31:07,400
Nii oletame, me lihtsalt malloced aadress või number 9 ja pane see siia.

517
00:31:07,400 --> 00:31:13,170
Kui esimene on 9 vaikimisi esimese stsenaariumi me arutasime lihtsalt tähendab, olgem punkt see kutt siin,

518
00:31:13,170 --> 00:31:15,790
jätke see nagu NULL; nüüd on meil number 9.

519
00:31:15,790 --> 00:31:18,280
Järgmine number tahame lisada on 17.

520
00:31:18,280 --> 00:31:22,420
17 kuulub siia, et me ei kavatse teha mõned loogiline samm selle kaudu.

521
00:31:22,420 --> 00:31:26,060
Nii et olgem selle asemel, enne kui me seda teeme, oletame, et me tahtsime sisestada number 8.

522
00:31:26,060 --> 00:31:28,650
>> Nii lihtsalt mugavuse pärast, ma lähen teha siin.

523
00:31:28,650 --> 00:31:30,760
Kuid pidage meeles, malloc ei pane see kõige kõikjal.

524
00:31:30,760 --> 00:31:33,460
Aga joonistus pärast, ma panen selle siia.

525
00:31:33,460 --> 00:31:38,440
Nii teesklen, et ma olen lihtsalt eraldatud sõlm nr 8, see on NULL vaikimisi.

526
00:31:38,440 --> 00:31:42,800
Mis nüüd juhtub? Paar asja.

527
00:31:42,800 --> 00:31:47,090
Tegime seda viga laval esmaspäeval, kui me uuendatud osuti nagu see,

528
00:31:47,090 --> 00:31:51,890
siis tegin seda, ja siis me väitis - me orvuks kõik teisedki laval.

529
00:31:51,890 --> 00:31:54,350
Sest sa ei saa - selleks toimingute siin on oluline,

530
00:31:54,350 --> 00:31:58,760
sest nüüd me kaotasime selle sõlme 9, et on lihtsalt omamoodi ujuvad ruumi.

531
00:31:58,760 --> 00:32:01,150
Nii et see ei olnud õige lähenemine esmaspäeval.

532
00:32:01,150 --> 00:32:03,330
Peame esmalt teha midagi muud.

533
00:32:03,330 --> 00:32:06,280
Olukorda maailmas näeb välja selline. Esialgu, 8 on eraldatud.

534
00:32:06,280 --> 00:32:10,550
Mis oleks parem viis sisestamist 8?

535
00:32:10,550 --> 00:32:14,720
Selle asemel, uuendades seda osuti esimene, lihtsalt uuendada see siin mitte.

536
00:32:14,720 --> 00:32:17,720
Seega peame rida koodi, mis läheb omakorda see NULL sümbol

537
00:32:17,720 --> 00:32:22,020
arvesse tegelik osuti, mis on suunatud sõlme 9,

538
00:32:22,020 --> 00:32:27,970
ja siis saame ohutult muuta esimene, kes seda venda siin.

539
00:32:27,970 --> 00:32:31,330
Nüüd on meil nimekirjas, mis on seotud nimekirja, kahest elemendist.

540
00:32:31,330 --> 00:32:33,580
Ja mida see tegelikult välja näeb siin?

541
00:32:33,580 --> 00:32:36,900
Kui me vaatame koodi, märkate, et ma olen teinud täpselt seda.

542
00:32:36,900 --> 00:32:41,970
Ma olen öelnud newptr, ja selles loos, newptr oli suunatud seda venda.

543
00:32:41,970 --> 00:32:45,520
>> Nii et las ma joonistan veel üks asi, ja ma oleks pidanud vasakule rohkem ruumi seda.

544
00:32:45,520 --> 00:32:48,540
Nii andeks tilluke joonistus.

545
00:32:48,540 --> 00:32:52,140
See mees on nn newptr.

546
00:32:52,140 --> 00:32:57,940
See on muutuv me kuulutasime paar rida varem, liin - veidi üle 25.

547
00:32:57,940 --> 00:33:03,430
Ja see osutavad 8. Nii et kui ma ütlen newptr-> next, see tähendab minna struct

548
00:33:03,430 --> 00:33:07,910
mis kuramuse osutas poolt newptr, nii siin me oleme, sinna minna.

549
00:33:07,910 --> 00:33:13,990
Siis nool ütleb saada järgmisele väljale ja seejärel = ütleb pane milline väärtus on?

550
00:33:13,990 --> 00:33:17,280
Väärtus, mis oli esimene; milline väärtus oli esimene?

551
00:33:17,280 --> 00:33:21,930
Esiteks oli suunatud selles sõlme, et tähendab see peaks nüüd juhtida seda sõlme.

552
00:33:21,930 --> 00:33:25,660
Teisisõnu, milline näeb välja küll naeruväärne jama minu käekiri,

553
00:33:25,660 --> 00:33:28,620
mida on lihtne idee, et lihtsalt liiguvad need nooled ümber

554
00:33:28,620 --> 00:33:31,560
tõlgib koodi vaid selle ühe riba.

555
00:33:31,560 --> 00:33:38,110
Hoida mis on esimene järgmisele väljale ja seejärel värskendage mida esimesena tegelikult on.

556
00:33:38,110 --> 00:33:40,900
Lähme edasi ja edasi kerin natuke seda,

557
00:33:40,900 --> 00:33:44,220
ja vaatavad vaid see saba sisestamise nüüd.

558
00:33:44,220 --> 00:33:51,210
Oletame, et ma saan selle punktini, kus ma leian, et järgmise välja mõned sõlm on NULL.

559
00:33:51,210 --> 00:33:53,410
Ja siinkohal lugu, täpselt, et ma ilustamise

560
00:33:53,410 --> 00:33:58,170
on see, et ma olen kasutusele teise osuti siia üles rida 142, eelkäija pointer.

561
00:33:58,170 --> 00:34:01,320
Sisuliselt siinkohal lugu, kui nimekiri saab pikk,

562
00:34:01,320 --> 00:34:04,800
Ma vajan kõndida ta kaks sõrme, sest kui ma liiga kaugele,

563
00:34:04,800 --> 00:34:08,219
mäletan ühte pikkusega nimekirja, sa ei saa minna tagasi.

564
00:34:08,219 --> 00:34:13,659
Nii et see idee predptr on minu vasak sõrme ja newptr - ei newptr.

565
00:34:13,659 --> 00:34:17,199
Teine osuti, mis siin on minu teine ​​sõrm, ja ma olen lihtsalt selline kõndimine nimekirja.

566
00:34:17,199 --> 00:34:22,179
Sellepärast, et on olemas. Kuid olgem arvesse ainult üks lihtsamaid juhtumeid siin.

567
00:34:22,179 --> 00:34:26,620
Kui see osuti järgmiseks valdkonnas on NULL, mis on loogiline jätk?

568
00:34:26,620 --> 00:34:30,840
Kui te liiklevad see nimekiri ja põrkad NULL pointer?

569
00:34:30,840 --> 00:34:35,780
Sa oled lõpus nimekirja, ja nii koodi siis lisab see veel ühe elemendi

570
00:34:35,780 --> 00:34:41,230
on omamoodi intuitiivne võtab, et sõlm, kelle kõrval pointer on NULL,

571
00:34:41,230 --> 00:34:46,120
nii on see praegu NULL, ja seda muuta, kuigi oleks aadress uus sõlm.

572
00:34:46,120 --> 00:34:52,260
Nii et me lihtsalt joonist kood nool, et me juhtis laval tõstes kellegi vasaku käega.

573
00:34:52,260 --> 00:34:54,070
>> Ja nii, et ma siputan käed nüüd,

574
00:34:54,070 --> 00:34:58,020
lihtsalt sellepärast, et ma arvan, et see on lihtne ära eksida, kui me teeme seda selline keskkond,

575
00:34:58,020 --> 00:35:00,600
kontrollib lisamiseks kell listi keskel.

576
00:35:00,600 --> 00:35:03,220
Aga lihtsalt intuitiivselt, mida on vaja juhtuda, kui sa tahad aru saada,

577
00:35:03,220 --> 00:35:06,600
kus mõned number kuulub keskel on sa ei pea kõndima seda

578
00:35:06,600 --> 00:35:09,510
rohkem kui ühe sõrmega, rohkem kui üks pointer,

579
00:35:09,510 --> 00:35:12,920
nuputada, kuhu see kuulub kontrollides on element <praegust,

580
00:35:12,920 --> 00:35:15,450
> Praegust, ja kui sa leiad, et koht,

581
00:35:15,450 --> 00:35:20,400
siis sa pead tegema seda sorti koorimata mäng kus liigutad osuti ümber väga hoolikalt.

582
00:35:20,400 --> 00:35:23,850
Ja see vastus, kui soovite põhjusel kaudu seda kodus ise,

583
00:35:23,850 --> 00:35:28,340
taandub lihtsalt need kaks rida koodi, kuid et nende read on super oluline.

584
00:35:28,340 --> 00:35:31,390
Sest kui sa tilk kellegi käsi ja tõsta kellegi vales järjekorras,

585
00:35:31,390 --> 00:35:34,580
uuesti, siis võib lõpuks orvustumine nimekirja.

586
00:35:34,580 --> 00:35:39,500
Kokkuvõttes rohkem kontseptuaalselt sisestamise tagaosa on suhteliselt lihtne.

587
00:35:39,500 --> 00:35:42,940
Sisestamise eesotsas on ka suhteliselt lihtne,

588
00:35:42,940 --> 00:35:45,580
kuid teil on vaja ajakohastada täiendavaid osuti seekord

589
00:35:45,580 --> 00:35:47,930
pigistada number 5 esitatud loetellu siin,

590
00:35:47,930 --> 00:35:51,560
ja siis on asetatud keset hõlmab veelgi rohkem jõupingutusi,

591
00:35:51,560 --> 00:35:56,130
väga hoolikalt sisestada number 20 oma õigesse asukohta,

592
00:35:56,130 --> 00:35:58,350
mis on vahemikus 17 ja 22.

593
00:35:58,350 --> 00:36:02,700
Nii et sa pead tegema midagi sellist on uus sõlm 20 punktist 22,

594
00:36:02,700 --> 00:36:08,470
ja siis, mis sõlme osuti tuleb ajakohastada viimase?

595
00:36:08,470 --> 00:36:10,630
See on 17, tegelikult lisada.

596
00:36:10,630 --> 00:36:14,080
Nii et taas, ma lükata tegelikku koodi selle konkreetse rakendamise.

597
00:36:14,080 --> 00:36:17,280
>> Esmapilgul see on veidi ülepaisutatud, kuid tegelikult on see vaid lõputu silmuse

598
00:36:17,280 --> 00:36:21,770
mis on silmuspõletamise, silmuspõletamise, silmuspõletamise, silmuspõletamise ja murdsid niipea kui vajutad NULL pointer,

599
00:36:21,770 --> 00:36:24,590
misjärel saate teha vajalikud sisestamist.

600
00:36:24,590 --> 00:36:30,960
See on siis esindaja seotud nimekirja sisestamise koodi.

601
00:36:30,960 --> 00:36:34,590
See oli tõesti palju, ja tundub, nagu me oleme lahendada üks probleem,

602
00:36:34,590 --> 00:36:36,940
aga meil kasutusele terve teine. Ausalt öeldes, oleme kulutanud kogu selle aja

603
00:36:36,940 --> 00:36:40,540
aasta suur O ja Ω ja sõiduaega, püüdes lahendada probleeme kiiremini,

604
00:36:40,540 --> 00:36:43,270
ja siin me võtame suure sammu tahapoole, tundub.

605
00:36:43,270 --> 00:36:45,380
Ja veel, kui eesmärgiks on andmete salvestamiseks,

606
00:36:45,380 --> 00:36:48,010
tundub, nagu Püha Graal, kui me ütles esmaspäeval, oleks tõesti

607
00:36:48,010 --> 00:36:50,470
salvestada asju koheselt.

608
00:36:50,470 --> 00:36:53,930
>> Tegelikult arvan, et me tegime kõrvale panema seotud nimekirja hetkeks

609
00:36:53,930 --> 00:36:56,000
ja me asemel kasutusele mõiste tabelis.

610
00:36:56,000 --> 00:36:59,110
Ja olgem lihtsalt mõtlema tabelis hetkeks massiivina.

611
00:36:59,110 --> 00:37:03,790
See massiivi ja antud juhul on siin umbes 26 elementi, 0 kuni 25,

612
00:37:03,790 --> 00:37:07,940
ja oletame, et teil on vaja mõned patakas ladustamine nimed:

613
00:37:07,940 --> 00:37:10,350
Alice ja Bob ja Charlie jms.

614
00:37:10,350 --> 00:37:12,880
Ja sa pead mõned andmestruktuur salvestada need nimed.

615
00:37:12,880 --> 00:37:15,000
Noh, sa võiksid kasutada midagi seotud nimekirja

616
00:37:15,000 --> 00:37:20,260
ja sina võiks kõndida nimekirja lisada Alice enne Bob ja Charlie pärast Bob ja nii edasi.

617
00:37:20,260 --> 00:37:23,850
Ja tegelikult, kui soovite näha koodi niimoodi nagu kõrvale,

618
00:37:23,850 --> 00:37:27,230
tean, et list2.h, me teeme just nii.

619
00:37:27,230 --> 00:37:30,610
Me ei lähe läbi see kood, kuid see on variant esimene näide

620
00:37:30,610 --> 00:37:34,640
, mis tutvustab üht struct oleme näinud nn õpilane,

621
00:37:34,640 --> 00:37:40,330
ja siis mida see tegelikult kauplust seotud nimekirja on viit õpilane struktuur

622
00:37:40,330 --> 00:37:44,520
mitte lihtsalt väike täisarv, n.

623
00:37:44,520 --> 00:37:46,900
Nii aru, seal kood seal, mis hõlmab tegelik stringid,

624
00:37:46,900 --> 00:37:49,940
kuid kui eesmärgiks käepärast tõesti nüüd on tegeleda efektiivsuse probleem,

625
00:37:49,940 --> 00:37:53,380
kas ei oleks tore, kui me antud objekti nimega Alice,

626
00:37:53,380 --> 00:37:56,020
me tahame panna tema õigesse asukohta andmestruktuur,

627
00:37:56,020 --> 00:37:58,860
tundub, nagu see oleks tõesti tore lihtsalt panna Alice,

628
00:37:58,860 --> 00:38:01,180
kelle nimi algab esimeses kohas.

629
00:38:01,180 --> 00:38:05,270
Ja Bob, kelle nimi algab B, teises kohas.

630
00:38:05,270 --> 00:38:09,580
Mis array, või alustame nimetades seda tabelit, hash tabel, et

631
00:38:09,580 --> 00:38:13,650
me saame teha just nii. Kui oleme andnud nime nagu Alice,

632
00:38:13,650 --> 00:38:16,700
string nagu Alice, kus sa paned-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Me vajame hueristic. Meil on vaja funktsiooni, et võtta mõned sisend nagu Alice

634
00:38:20,540 --> 00:38:24,610
ja tagastab vastuse: "Pane Alice selles kohas."

635
00:38:24,610 --> 00:38:28,720
Ja see funktsioon, see must kast, läheb nimega räsifunktsiooniga.

636
00:38:28,720 --> 00:38:32,330
>> Räsifunktsiooniga on midagi, mis võtab sisendina, nagu "Alice",

637
00:38:32,330 --> 00:38:38,080
ja tagastab teile, tavaliselt numbriline asukoht mingis andmestruktuur, kus Alice kuulub.

638
00:38:38,080 --> 00:38:40,830
Sel juhul meie räsifunktsiooniga peaks olema suhteliselt lihtne.

639
00:38:40,830 --> 00:38:47,510
Meie räsifunktsiooniga peaks ütlema, kui sulle antakse "Alice", mis laadi peaks ma hoolin?

640
00:38:47,510 --> 00:38:55,660
Esimene. Nii et ma vaatan [0], ja siis ma ütlen, kui [0] märk on, tagastab arvu 0.

641
00:38:55,660 --> 00:39:01,130
Kui see on B, return 1. Kui see on C, tagastab 2, ja nii edasi.

642
00:39:01,130 --> 00:39:05,940
Kõik 0 indeks ning mis võimaldaks mul lisada Alice ja siis Bob ja siis Charlie ja nii edasi

643
00:39:05,940 --> 00:39:10,960
sellesse andmestruktuur. Aga seal on probleem.

644
00:39:10,960 --> 00:39:13,060
Mis siis, kui Anita tuleb mööda jälle?

645
00:39:13,060 --> 00:39:17,510
Kust me paneme Anita? Tema nimi ka, algab tähega,

646
00:39:17,510 --> 00:39:20,330
ja tundub, nagu oleme teinud isegi suurem jama selle probleemi.

647
00:39:20,330 --> 00:39:24,380
Meil on nüüd kohe sisestamise pidevalt aega sisestamisel arvesse andmestruktuur

648
00:39:24,380 --> 00:39:27,100
mitte halvimast lineaarne,

649
00:39:27,100 --> 00:39:29,510
kuid mida me saame teha koos Anita sel juhul?

650
00:39:29,510 --> 00:39:34,110
Millised on kaks võimalust, kas tõesti? Jah?

651
00:39:34,110 --> 00:39:37,410
[Student vastus, arusaamatult] Okei, nii et meil oleks teine ​​dimensioon.

652
00:39:37,410 --> 00:39:42,320
See on hea. Nii et me saame ehitada asju läbi 3D nagu me rääkisime suuliselt esmaspäeval.

653
00:39:42,320 --> 00:39:46,700
Võiksime lisada veel juurdepääsu siin, kuid arvan, et ei, ma üritan hoida seda lihtsat.

654
00:39:46,700 --> 00:39:50,160
Kogu eesmärk siin on kohe pidev tööajaga juurdepääsu,

655
00:39:50,160 --> 00:39:52,170
Nii et lisades liiga palju keerukust.

656
00:39:52,170 --> 00:39:55,970
Mis on ka teisi võimalusi, kui soovitakse sisestada Anita sellesse andmestruktuur? Jah?

657
00:39:55,970 --> 00:39:58,610
[Student vastus, arusaamatult] Hea. Nii et me võiks minna kõik teisedki maha,

658
00:39:58,610 --> 00:40:03,040
nagu Charlie Nudget alla Bob ja Alice, ja siis me paneme Anita kus ta tahab olla.

659
00:40:03,040 --> 00:40:05,660
>> Muidugi, nüüd, seal on kõrvalnäht seda.

660
00:40:05,660 --> 00:40:09,000
See andmestruktuur on ilmselt kasulik ei ole, sest me tahame lisada inimesed kord

661
00:40:09,000 --> 00:40:11,250
kuid kuna me tahame, et kontrollida, kas nad on sinna hiljem

662
00:40:11,250 --> 00:40:13,600
kui me tahame, et printida välja kõik nimed andmestruktuur.

663
00:40:13,600 --> 00:40:15,850
Me teeme midagi koos käesoleva andmete lõpuks.

664
00:40:15,850 --> 00:40:20,810
Nii et nüüd oleme omamoodi kruvitud üle Alice, kes ei ole enam, kus ta olema pidi.

665
00:40:20,810 --> 00:40:23,880
Samuti on Bob, ega Charlie.

666
00:40:23,880 --> 00:40:26,060
Nii et võibolla see ei ole nii hea idee.

667
00:40:26,060 --> 00:40:28,830
Aga tõesti, see on üks võimalus. Me võiks suunata kõik alla,

668
00:40:28,830 --> 00:40:32,240
või kuradit, Anita tulid hilja mängu, miks me lihtsalt ei pane Anita

669
00:40:32,240 --> 00:40:35,870
mitte siin, mitte siin, mitte siin, paneme ta veidi madalam nimekirjas.

670
00:40:35,870 --> 00:40:38,680
Aga siis see probleem algab delegeerida uuesti.

671
00:40:38,680 --> 00:40:41,630
Sul võib olla võimalik leida Alice koheselt, mis põhineb tema eesnimi.

672
00:40:41,630 --> 00:40:44,320
Ja Bob koheselt, ja Charlie. Aga siis sa ootad Anita,

673
00:40:44,320 --> 00:40:46,360
ja näed, hmm, Alice on viis.

674
00:40:46,360 --> 00:40:48,770
Noh, las ma vaatan alla Alice. Bob ei ole Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie ei Anita. Oh, seal on Anita.

676
00:40:51,850 --> 00:40:54,720
Ja kui te jätkate et rong loogika kogu tee,

677
00:40:54,720 --> 00:41:00,690
Mis on halvim sõiduaega leida või lisada Anita uude andmestruktuur?

678
00:41:00,690 --> 00:41:03,280
See on O (n), eks?

679
00:41:03,280 --> 00:41:06,280
Sest halvimal juhul, seal on Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
kõik tee alla keegi nimega "Y", nii seal on ainult üks koht on jäänud.

681
00:41:10,150 --> 00:41:13,950
Õnneks ei ole meil üks nn "Z", nii me paneme Anita väga põhjas.

682
00:41:13,950 --> 00:41:16,040
>> Me ei ole tegelikult lahendanud selle probleemi.

683
00:41:16,040 --> 00:41:19,890
Nii et võib-olla me ei vaja kehtestada selle kolmanda mõõtme.

684
00:41:19,890 --> 00:41:22,230
Ja selgub, kui me tutvustada see kolmas dimensioon,

685
00:41:22,230 --> 00:41:25,240
me ei saa seda teha ideaalselt, kuid Püha Graal saab olema saada

686
00:41:25,240 --> 00:41:28,370
konstantse aja sisestamise ja dünaamiline lisamised nii et

687
00:41:28,370 --> 00:41:30,960
me ei pea raskesti kood massiivi suurus 26.

688
00:41:30,960 --> 00:41:34,400
Me ei saa sisestada nii palju nimesid kui tahame, kuid võtame meie 5-minutilise vaheaja siin

689
00:41:34,400 --> 00:41:38,790
ja siis tee seda korralikult.

690
00:41:38,790 --> 00:41:46,020
Hea küll. Seadsin lugu üles päris kunstlikult seal

691
00:41:46,020 --> 00:41:48,670
valides Alice ja siis Bob ja siis Charlie ja siis Anita,

692
00:41:48,670 --> 00:41:51,000
kelle nimi oli ilmselt läheb põrkuvad Alice.

693
00:41:51,000 --> 00:41:54,120
Kuid küsimus meil lõppes esmaspäeval on lihtsalt kui tõenäoline on see

694
00:41:54,120 --> 00:41:56,370
et sa saaksid selliseid kokkupõrkeid? Teisisõnu,

695
00:41:56,370 --> 00:42:00,490
kui me hakkame kasutama seda tabelina struktuur, mis on tegelikult lihtsalt massiiv,

696
00:42:00,490 --> 00:42:02,460
antud juhul 26. asukohad,

697
00:42:02,460 --> 00:42:05,740
Mis siis, kui meie sisendite asemel ühtlaselt jaotatud?

698
00:42:05,740 --> 00:42:09,620
See ei ole kunstlikult Alice ja Bob ja Charlie ja David ja nii edasi tähtedega,

699
00:42:09,620 --> 00:42:12,380
see on jaotatud ühtlaselt läbi Z.

700
00:42:12,380 --> 00:42:15,220
>> Võib-olla me lihtsalt veab ja me ei kavatse on kaks poolt või kaks B

701
00:42:15,220 --> 00:42:17,640
väga suure tõenäosusega, kuid kui keegi märkis,

702
00:42:17,640 --> 00:42:20,730
kui me üldiste see probleem ja ei tee 0-25

703
00:42:20,730 --> 00:42:26,060
aga, ütleme, 0 kuni 364 või 65, sageli päevade tüüpiline aastal

704
00:42:26,060 --> 00:42:31,170
ja küsis: "Mis on tõenäosus, et kaks meist siin ruumis on sama sünnipäev?"

705
00:42:31,170 --> 00:42:34,600
Teisisõnu, mis on tõenäosus, et kaks meist on nimi algab?

706
00:42:34,600 --> 00:42:37,190
Selline küsimus on sama, kuid see aadress ruumi,

707
00:42:37,190 --> 00:42:39,940
see otsing ruum on suurem juhul, sünnipäevad,

708
00:42:39,940 --> 00:42:42,820
sest meil on nii palju rohkem päeval aastas kui tähte tähestikus.

709
00:42:42,820 --> 00:42:44,910
Mis on kokkupõrke tõenäosus?

710
00:42:44,910 --> 00:42:48,410
Noh, me ei mõtle seda figuring matemaatika vastupidi.

711
00:42:48,410 --> 00:42:50,580
Mis on tõenäosus ei kokkupõrkeid?

712
00:42:50,580 --> 00:42:53,970
Noh, see väljend siin ütleb, et mis on tõenäosus

713
00:42:53,970 --> 00:42:58,770
kas seal on ainult üks inimene siin ruumis, et neil on unikaalne sünnipäeva?

714
00:42:58,770 --> 00:43:01,190
See on 100%. Sest kui seal on ainult üks inimene toas,

715
00:43:01,190 --> 00:43:03,940
tema sünnipäev võib olla mis tahes 365 päeva läbi aasta.

716
00:43:03,940 --> 00:43:08,650
Nii et 365/365 valikutest annab mulle väärtus 1.

717
00:43:08,650 --> 00:43:11,250
Nii et tõenäosus kõnealuse hetkel on vaid 1.

718
00:43:11,250 --> 00:43:13,270
Aga kui seal on teine ​​inimene toas,

719
00:43:13,270 --> 00:43:16,490
Mis on tõenäosus, et nende sünnipäev on erinevad?

720
00:43:16,490 --> 00:43:20,680
Seal on vaid 364 võimaliku päeva, unustades liigaasta,

721
00:43:20,680 --> 00:43:23,580
oma sünnipäeva mitte sattuda vastuollu teiste isikutega.

722
00:43:23,580 --> 00:43:31,920
Nii et 364/365. Kui kolmas isik tuleb, see on 363/365, ja nii edasi.

723
00:43:31,920 --> 00:43:35,790
Nii et me hoiame korrutades koos nende fraktsioonid, mis on üha väiksemaid ja väiksemaid,

724
00:43:35,790 --> 00:43:40,720
selgitada, milline on tõenäosus, et kõik meist on unikaalne sünnipäevad?

725
00:43:40,720 --> 00:43:43,570
Aga siis me muidugi lihtsalt võtta seda vastust ja klapp selle ümber

726
00:43:43,570 --> 00:43:47,210
ja teha 1 miinus kõik, et väljend me lõpuks saada

727
00:43:47,210 --> 00:43:51,250
kui sa mäletad tagasi oma matemaatika raamatuid, tundub natuke midagi sellist,

728
00:43:51,250 --> 00:43:54,590
mis on palju kergem tõlgendada graafiliselt.

729
00:43:54,590 --> 00:43:57,820
Ja see graafiline siin on x-telg arvu sünnipäevad,

730
00:43:57,820 --> 00:44:02,030
või inimeste arv sünnipäevad, ja y-telg on tõenäosus sobi.

731
00:44:02,030 --> 00:44:06,060
Ja mida see ütleb on, et kui sul on, ütleme, isegi,

732
00:44:06,060 --> 00:44:10,860
Valime midagi 22, 23.

733
00:44:10,860 --> 00:44:13,160
Kui seal on 22 või 23 inimest ruumis,

734
00:44:13,160 --> 00:44:17,100
Tõenäosus, et kaks neist väga vähesed inimesed hakkavad olema sama sünnipäev

735
00:44:17,100 --> 00:44:19,560
on tegelikult super kõrge, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% tõenäosus, et klassi vaid 22 inimest, seminar, praktiliselt,

737
00:44:23,450 --> 00:44:25,790
2 need inimesed hakkavad olema sama sünnipäev.

738
00:44:25,790 --> 00:44:28,520
Sest seal on nii palju võimalusi, kus saab olema sama sünnipäev.

739
00:44:28,520 --> 00:44:31,110
Isegi hullem, kui te vaatate paremale küljele diagrammi,

740
00:44:31,110 --> 00:44:34,040
selleks ajaks teil on klassis ainult 58 õpilast seda,

741
00:44:34,040 --> 00:44:39,270
tõenäosus 2 inimest, kellel on sünnipäev on super, super suur, ligi 100%.

742
00:44:39,270 --> 00:44:41,880
Nüüd, see on omamoodi lõbus fakt reaalses elus.

743
00:44:41,880 --> 00:44:45,850
>> Aga mõju, nüüd, andmestruktuurid ja teabe hoidmise

744
00:44:45,850 --> 00:44:51,100
tähendab, et lihtsalt eeldades, et teil on kena, puhas, ühtlane jaotus andmeid

745
00:44:51,100 --> 00:44:53,650
ja sul on piisavalt suur massiiv mahtuda hunnik asju

746
00:44:53,650 --> 00:44:59,360
ei tähenda, sa lähed, et saada inimesi ainulaadne kohtades.

747
00:44:59,360 --> 00:45:03,810
Sa lähed on kokkupõrkeid. Nii et see mõiste segamist, nagu seda nimetatakse,

748
00:45:03,810 --> 00:45:07,450
võttes sisend nagu "Alice" ja massaging see kuidagi

749
00:45:07,450 --> 00:45:10,190
ja siis saada tagasi vastus nagu 0 või 1 või 2.

750
00:45:10,190 --> 00:45:17,500
Getting tagasi mõned väljund, et funktsioon on vaevanud see tõenäosus kokkupõrke.

751
00:45:17,500 --> 00:45:19,530
Niisiis, kuidas me saame hakkama neid kokkupõrkeid?

752
00:45:19,530 --> 00:45:21,940
Noh, ühel juhul saame idee, et pakuti.

753
00:45:21,940 --> 00:45:25,100
Me ei saa lihtsalt minema kõik maha, või ehk, veidi lihtsamalt,

754
00:45:25,100 --> 00:45:29,870
selle asemel et liikuda kõik teisedki, lihtsalt liikuda Anita põhjale saadaval kohapeal.

755
00:45:29,870 --> 00:45:32,810
Nii et kui Alice on 0, Bob on 1, Charlie on 2,

756
00:45:32,810 --> 00:45:35,260
me lihtsalt panna Anita at asukoht 3.

757
00:45:35,260 --> 00:45:38,860
Ja see on tehnika andmestruktuurid nimetatakse lineaarse katsetamine.

758
00:45:38,860 --> 00:45:41,310
Lineaarne, sest sa oled lihtsalt kõndides seda joont, ja sa oled omamoodi katsetamine

759
00:45:41,310 --> 00:45:43,640
olemasolevaid kohti andmestruktuur.

760
00:45:43,640 --> 00:45:46,210
Muidugi, see devolves O (n).

761
00:45:46,210 --> 00:45:49,590
Kui andmestruktuur on tõesti täis, seal on 25 inimest seda juba,

762
00:45:49,590 --> 00:45:54,120
ja siis Anita jõuab mööda, ta jõuab, mida oleks asukoha Z, ja see on hea.

763
00:45:54,120 --> 00:45:56,540
Ta ikka sobib, ja me leiame ta hiljem.

764
00:45:56,540 --> 00:46:00,100
>> Aga see oli vastuolus eesmärgiga kiirendada asju üles.

765
00:46:00,100 --> 00:46:02,530
Mis siis, kui me selle asemel kasutusele see kolmas mõõde?

766
00:46:02,530 --> 00:46:06,400
See meetod on üldiselt nimetatakse eraldi Aheldamise või kellel ketid.

767
00:46:06,400 --> 00:46:10,030
Ja mida hash tabelis nüüd on see tabelina struktuur,

768
00:46:10,030 --> 00:46:13,450
Teie lauas on vaid massiivi osuti.

769
00:46:13,450 --> 00:46:18,230
Aga mis need näpunäited käsk on guess what?

770
00:46:18,230 --> 00:46:21,970
Seotud nimekirja. Mis siis, kui me võtame parima mõlemad maailmad?

771
00:46:21,970 --> 00:46:26,500
Me kasutame massiivid esialgse indeksid

772
00:46:26,500 --> 00:46:32,070
arvesse andmete struktuuri, et saaksime koheselt minna [0] [1], [30] või nii edasi,

773
00:46:32,070 --> 00:46:36,480
kuid nii, et meil on teatud paindlikkust ja me ei sobi Anita ja Alice ja Adam

774
00:46:36,480 --> 00:46:38,630
ja muu nime,

775
00:46:38,630 --> 00:46:43,470
me selle asemel lasta teine ​​telg kasvada meelevaldselt.

776
00:46:43,470 --> 00:46:47,340
Ja me lõpuks alates esmaspäevast, on selle ilmekas võime koos seotud nimekirja.

777
00:46:47,340 --> 00:46:49,530
Meil võib kasvada andmestruktuur meelevaldselt.

778
00:46:49,530 --> 00:46:52,450
Teise me võiks lihtsalt teha suur 2-mõõtmeline massiiv,

779
00:46:52,450 --> 00:46:57,190
kuid see saab olema kohutav olukord, kui üks rida 2-mõõtmeline massiiv

780
00:46:57,190 --> 00:47:01,280
ei ole piisavalt suur, et täiendav isik, kelle nimi juhtub alustada A.

781
00:47:01,280 --> 00:47:04,200
Jumal hoidku me peame ümber tohutu 2-mõõtmeline struktuur

782
00:47:04,200 --> 00:47:06,600
lihtsalt sellepärast, et seal on nii palju inimesi nimega,

783
00:47:06,600 --> 00:47:09,480
eriti kui seal on nii vähe inimesi nimega Z midagi.

784
00:47:09,480 --> 00:47:12,170
See on lihtsalt saab olema väga hõre andmestruktuur.

785
00:47:12,170 --> 00:47:15,400
Nii see ei ole täiuslik igasuguste vahenditega, kuid nüüd me vähemalt on võime

786
00:47:15,400 --> 00:47:19,090
Et koheselt leida, kui Alice või Anita kuulub,

787
00:47:19,090 --> 00:47:21,090
vähemalt nii vertikaalteljel,

788
00:47:21,090 --> 00:47:25,850
ja siis me lihtsalt peame otsustama, kuhu panna Anita või Alice see seotud nimekirja.

789
00:47:25,850 --> 00:47:32,480
Kui me ei hooli sorteerimine asjad, kui kiiresti saaks me lisada Alice struktuuri, nagu see on?

790
00:47:32,480 --> 00:47:35,370
See on pidevalt aega. Me indeks [0], ja kui keegi seal,

791
00:47:35,370 --> 00:47:37,550
Alice läheb alguses, et seotud nimekirja.

792
00:47:37,550 --> 00:47:40,000
Aga see ei ole suur asi. Sest kui Anita siis tuleb mööda

793
00:47:40,000 --> 00:47:42,160
mõned mitmeid samme hiljem, kui ei Anita kuulub?

794
00:47:42,160 --> 00:47:45,140
Noh, [0]. OOP. Alice on juba selles seotud nimekirja.

795
00:47:45,140 --> 00:47:47,760
>> Aga kui me ei hooli sorteerimine nende nimed,

796
00:47:47,760 --> 00:47:53,580
me võime lihtsalt liikuda Alice üle, sisesta Anita, kuid isegi see on pidevalt aega.

797
00:47:53,580 --> 00:47:57,010
Isegi kui seal on Alice ja Aadam ja kõik need muud nimed,

798
00:47:57,010 --> 00:47:59,410
See ei ole tegelikult muudavad need füüsiliselt. Miks?

799
00:47:59,410 --> 00:48:04,090
Sest me lihtsalt ei siin lingitud nimekiri, kes teab olid need sõlmed on niikuinii?

800
00:48:04,090 --> 00:48:06,550
Kõik, mida selleks vaja on liikuda leivapuru.

801
00:48:06,550 --> 00:48:10,930
Liigu nooltega ringi, sa ei pea füüsiliselt liigutada andmeid ümber.

802
00:48:10,930 --> 00:48:14,610
Nii saame sisestada Anita, sellisel juhul koheselt. Pidev aeg.

803
00:48:14,610 --> 00:48:20,250
Nii et meil on pidevalt ajaga lookup, ja pidev aja sisestamise keegi nagu Anita.

804
00:48:20,250 --> 00:48:22,740
Aga selline Oversimplifying maailmas.

805
00:48:22,740 --> 00:48:28,510
Mis siis, kui me hiljem tahad leida Alice?

806
00:48:28,510 --> 00:48:31,050
Mis siis, kui me hiljem tahad leida Alice?

807
00:48:31,050 --> 00:48:35,690
Mitu sammu on, et aega võtab?

808
00:48:35,690 --> 00:48:37,850
[Student vastus, arusaamatult]

809
00:48:37,850 --> 00:48:40,950
Täpselt. Inimeste arv enne Alice seotud nimekirja.

810
00:48:40,950 --> 00:48:45,420
Nii et see ei ole päris täiuslik, sest meie andmestruktuur, jälle on see vertikaalne juurdepääsu

811
00:48:45,420 --> 00:48:50,240
ja siis on need seotud nimekirjad ripuvad - tegelikult, ärme joonistada massiivi.

812
00:48:50,240 --> 00:48:56,020
On need seotud nimekirjad ripuvad välja sellest, mis näeb välja natuke midagi sellist.

813
00:48:56,020 --> 00:48:59,110
Probleem on aga selles, kui Alice ja Aadam ja kõik need muud nimed

814
00:48:59,110 --> 00:49:01,720
lõpuks rohkem ja rohkem seal,

815
00:49:01,720 --> 00:49:04,810
leida keegi võiks lõpuks võtta hunnik samme,

816
00:49:04,810 --> 00:49:06,670
bcause teil läbida seotud nimekirja,

817
00:49:06,670 --> 00:49:08,090
mis on lineaarne operatsioon.

818
00:49:08,090 --> 00:49:14,270
Nii et tõesti, siis sisestamise aja lõpuks on O (n), kus n on elementide arv nimekirjas.

819
00:49:14,270 --> 00:49:21,780
Jagades, olgem meelevaldselt nimetame seda m, kus m on arv lingitud nimekirjad

820
00:49:21,780 --> 00:49:24,500
et meil on selles vertikaalteljel.

821
00:49:24,500 --> 00:49:27,180
Teisisõnu, kui me tõesti eeldada ühtlase jaotuse nimed,

822
00:49:27,180 --> 00:49:30,150
täiesti ebareaalne. Seal on ilmselt rohkem mõnede tähtede kui teised.

823
00:49:30,150 --> 00:49:32,580
>> Aga kui me eeldame hetkel ühtlase jaotuse,

824
00:49:32,580 --> 00:49:37,350
ja me oleme N Kokku inimesi, ja m kokku ketid

825
00:49:37,350 --> 00:49:40,630
meile kättesaadav, siis pikkus kummagi ketid

826
00:49:40,630 --> 00:49:44,380
üsna lihtsalt saab olema kokku, n arvuga ahelate.

827
00:49:44,380 --> 00:49:48,900
Nii n / m. Aga siin, kus me saame olla kõik matemaatiliselt tark.

828
00:49:48,900 --> 00:49:53,030
m on konstant, sest seal on fikseeritud hulk neid.

829
00:49:53,030 --> 00:49:54,620
Sa lähed kuulutada oma massiivi alguses,

830
00:49:54,620 --> 00:49:58,450
ja me ei ole saneerimist vertikaalteljel. Definitsiooni järgi, mis jääb samaks.

831
00:49:58,450 --> 00:50:01,220
See on ainult horisontaalteljel niiöelda, et muutub.

832
00:50:01,220 --> 00:50:04,760
Nii et tehniliselt on see pidev. Nii et nüüd, sisestusajaga

833
00:50:04,760 --> 00:50:09,700
on päris palju O (n).

834
00:50:09,700 --> 00:50:12,410
Nii et ei tunne kõik, et palju parem.

835
00:50:12,410 --> 00:50:14,940
Aga mis on tõde siin? Noh, kõik see aeg, nädalaid,

836
00:50:14,940 --> 00:50:20,640
oleme rääkinud O (n ²). O (n), 2 x n ², - n, jagatud 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
See on lihtsalt n ². Aga nüüd, selles osas semestri

838
00:50:23,580 --> 00:50:25,560
saame hakata rääkima reaalses maailmas uuesti.

839
00:50:25,560 --> 00:50:31,520
Ja n / m on täiesti kiiremini kui lihtsalt n üksi.

840
00:50:31,520 --> 00:50:35,170
Kui teil on tuhat nime, ja te murda neid mitmeks ämbrid

841
00:50:35,170 --> 00:50:37,820
nii et teil on ainult kümme nimed kõigis nendes ahelates,

842
00:50:37,820 --> 00:50:41,670
absoluutselt otsivad kümme asja, saab olema kiirem kui tuhat asja.

843
00:50:41,670 --> 00:50:43,740
Ja nii üks tulemas probleem komplekti läheb sulle väljakutse

844
00:50:43,740 --> 00:50:46,100
mõelda täpselt, et kuigi, jah,

845
00:50:46,100 --> 00:50:49,520
asümptootiliselt ja matemaatiliselt, see on ikka lihtsalt lineaarne,

846
00:50:49,520 --> 00:50:51,700
mis imeb üldiselt kui nad püüavad leida asju.

847
00:50:51,700 --> 00:50:54,530
Tegelikult see saab olema kiirem kui

848
00:50:54,530 --> 00:50:56,520
sest see jagaja.

849
00:50:56,520 --> 00:50:58,310
Ja nii pole jälle saab olema see kompromiss

850
00:50:58,310 --> 00:51:01,390
ja see vastuolu teooria ja tegelikkus,

851
00:51:01,390 --> 00:51:03,550
ja üks nupud hakkab keerates siinkohal semester

852
00:51:03,550 --> 00:51:07,510
on rohkem reaalsuseks, nagu me omamoodi valmistuda semster lõpuks,

853
00:51:07,510 --> 00:51:09,280
kui me võtame kasutusele maailmas veebi programmeerimine,

854
00:51:09,280 --> 00:51:11,530
kus tõesti, tulemuslikkust loen, sest teie kasutajad hakkavad

855
00:51:11,530 --> 00:51:14,880
enesetunne ja hindame halva disaini otsuseid.

856
00:51:14,880 --> 00:51:19,950
>> Niisiis, kuidas sa minna rakendamisel seotud - hash tabelis on 31 elementi?

857
00:51:19,950 --> 00:51:22,600
Ja eelmises näites oli omavoliliselt umbes sünnipäevad.

858
00:51:22,600 --> 00:51:26,190
Kui keegi ei ole sünnipäeva 1. jaanuaril või 1. veebruar me paneme neid selles ämber.

859
00:51:26,190 --> 00:51:28,960
Kui see on 2. jaanuar veebruar 2, 2. märts paneme neid selles ämber.

860
00:51:28,960 --> 00:51:32,220
Sellepärast oli 31. Kuidas kuulutada hash tabelit?

861
00:51:32,220 --> 00:51:37,480
See võib olla üsna lihtne, sõlme * tabelis on minu suvalise nime see, [31].

862
00:51:37,480 --> 00:51:42,400
See annab mulle 31 viiteid tippu,

863
00:51:42,400 --> 00:51:45,370
ja mis võimaldab mul on 31 viiteid seotud nimekirjad

864
00:51:45,370 --> 00:51:48,800
isegi kui need ketid on esialgu NULL.

865
00:51:48,800 --> 00:51:54,860
Mida ma tahan panna kui ma tahan salvestada "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Noh, me peame pakkima need asjad struktuur

867
00:51:57,010 --> 00:52:00,530
sest me vajame Alice osutada Bob, osutada Charlie, ja nii edasi.

868
00:52:00,530 --> 00:52:04,940
Me ei saa lihtsalt nimed üksi, nii et ma võiks luua uue struktuuri, mida nimetatakse sõlme siin.

869
00:52:04,940 --> 00:52:08,310
>> Mis on tegelik sõlme? Mis on sõlm selles uues seotud nimekirja?

870
00:52:08,310 --> 00:52:11,840
Esimene asi, mida nimetatakse sõna, on isiku nimi.

871
00:52:11,840 --> 00:52:14,340
PIKKUS, arvatavasti, puudutab pikkust inimese nimi,

872
00:52:14,340 --> 00:52:18,210
mis iganes see on, 20, 30, 40 tähemärki hull nurgas juhtudel,

873
00:52:18,210 --> 00:52:22,680
ja +1 on milleks? See on lihtsalt pildi NULL sümbol, \ 0.

874
00:52:22,680 --> 00:52:27,410
Nii et see sõlm on ümbriste "midagi" sees ise,

875
00:52:27,410 --> 00:52:29,640
kuid see kinnitab osuti nimetas tuleva

876
00:52:29,640 --> 00:52:32,580
et saaksime kett Alice Bobile Charlie ja nii edasi.

877
00:52:32,580 --> 00:52:36,700
Ei saa olla NULL, kuid ei pruugi olla.

878
00:52:36,700 --> 00:52:40,110
Kõik küsimused nende hash tabeleid? Jah?

879
00:52:40,110 --> 00:52:46,190
[Student küsib küsimuse, arusaamatult] massiivi - hea küsimus.

880
00:52:46,190 --> 00:52:50,120
Miks on see char sõna array asemel lihtsalt char *?

881
00:52:50,120 --> 00:52:53,830
Selles mõnevõrra meelevaldne näide, ma ei taha olla abiks

882
00:52:53,830 --> 00:52:56,190
kuni malloc iga algsed nimed.

883
00:52:56,190 --> 00:52:59,530
Tahtsin kuulutada maksimaalselt mälu string

884
00:52:59,530 --> 00:53:06,020
nii et ma võiksin kopeerida selle struktuuri Alice \ 0 ja ei pea tegelema malloc ja tasuta jms.

885
00:53:06,020 --> 00:53:11,710
Aga ma võiks teha, et kui ma tahtsin olla teadlik ruumi kasutamise. Hea küsimus.

886
00:53:11,710 --> 00:53:14,780
Nii et proovime üldistada eemale sellest

887
00:53:14,780 --> 00:53:18,350
ning keskenduda ülejäänud täna andmestruktuurid üldisemalt

888
00:53:18,350 --> 00:53:21,170
ja muid probleeme, et saame lahendada kasutades samu alused

889
00:53:21,170 --> 00:53:24,590
kuigi andmestruktuurid ise võib erineda oma andmed.

890
00:53:24,590 --> 00:53:27,910
>> Nii selgub infotehnoloogia, puud on väga levinud.

891
00:53:27,910 --> 00:53:29,760
Ja sa ei mõtle puu omamoodi nagu sugupuu,

892
00:53:29,760 --> 00:53:31,830
kui seal on mõned juured, mõned matriarh või patriarh,

893
00:53:31,830 --> 00:53:34,540
vanaema või vanaisa või varem tagasi,

894
00:53:34,540 --> 00:53:38,880
all, mis on ema ja isa või erinevate õed-vennad vms.

895
00:53:38,880 --> 00:53:42,500
Nii puu struktuuri on sõlmed ja tal on lapsed,

896
00:53:42,500 --> 00:53:45,260
tavaliselt 0 või enam last iga sõlme.

897
00:53:45,260 --> 00:53:47,320
Ja mõned kõnepruuki, et näed sellel pildil siin

898
00:53:47,320 --> 00:53:50,630
on mis tahes väikesed lapsed või lapselapsed äärealadel

899
00:53:50,630 --> 00:53:52,330
kellel ei ole nooled, mis tulenevad nende

900
00:53:52,330 --> 00:53:55,070
need on nn lehed, ja keegi sees

901
00:53:55,070 --> 00:53:58,790
on sisemine sõlme; võite helistada see midagi sarnast.

902
00:53:58,790 --> 00:54:01,430
Aga see struktuur on üsna tavalised. See üks on natuke meelevaldne.

903
00:54:01,430 --> 00:54:04,930
Meil on üks laps vasakul, meil on kolm last paremal

904
00:54:04,930 --> 00:54:06,830
kahe lapse all vasakul.

905
00:54:06,830 --> 00:54:10,740
Nii et meil on erineva suurusega puud, aga kui me hakkame standardiseerida asju,

906
00:54:10,740 --> 00:54:15,330
ja te võiks meenutada, seda alates Patricku video binaarne otsing eelmisest lühike

907
00:54:15,330 --> 00:54:19,490
internetis, binaarne otsing ei pea olema rakendatav massiivi

908
00:54:19,490 --> 00:54:21,410
või paberitükke tahvli.

909
00:54:21,410 --> 00:54:25,490
Oletame, et sa tahad säilitada oma numbrid keerukamaid andmete struktuuri.

910
00:54:25,490 --> 00:54:27,680
Sa võid luua puu niimoodi.

911
00:54:27,680 --> 00:54:35,290
Sul võib olla sõlme deklareeritud C, ja et sõlm võib olla vähemalt kaks elementi sees on.

912
00:54:35,290 --> 00:54:39,470
Üks on number, mida soovite salvestada, ja teine ​​on - noh, me vajame veel ühte.

913
00:54:39,470 --> 00:54:41,540
Teine on oma lapsed.

914
00:54:41,540 --> 00:54:45,150
Nii et siin on veel üks andmestruktuur. Seekord sõlm on määratletud ladustamiseks arv n

915
00:54:45,150 --> 00:54:49,060
ja siis kaks suunanäitajaks; vasak laps ja õigus lapse.

916
00:54:49,060 --> 00:54:52,100
Ja nad pole meelevaldne. Mis on huvitav see puu?

917
00:54:52,100 --> 00:55:00,550
>> Mis on muster, kuidas me ette selle välja või kuidas Patrick pani välja oma video?

918
00:55:00,550 --> 00:55:02,790
See on selline selge, et seal on mõned sorteerimine toimub siin,

919
00:55:02,790 --> 00:55:04,460
kuid milline on lihtne reegel? Jah?

920
00:55:04,460 --> 00:55:08,350
[Student vastus, arusaamatult]

921
00:55:08,350 --> 00:55:12,040
Perfect. Kui te pilk sellele, näete vähesel arvul vasakul,

922
00:55:12,040 --> 00:55:14,690
suured numbrid vasakul, aga see on tõsi iga sõlme.

923
00:55:14,690 --> 00:55:20,370
Iga sõlme, tema vasak lapse vähem kui see, ja tema õigus lapse üle ta.

924
00:55:20,370 --> 00:55:25,210
Mida see tähendab nüüd on, kui ma tahan, et otsida seda andmestruktuuri, ütleme, number 44,

925
00:55:25,210 --> 00:55:29,320
Ma pean alustama keskmes, sest kui kõiki neid keerulisem andmestruktuurid nüüd,

926
00:55:29,320 --> 00:55:31,910
meil on ainult kursor üks asi, alguses.

927
00:55:31,910 --> 00:55:35,010
Ja sel juhul, alguses on juur. See ei ole vasakus servas,

928
00:55:35,010 --> 00:55:39,530
see on just see struktuur. Nii et ma näen siin on 55, ja ma otsin 44.

929
00:55:39,530 --> 00:55:41,430
Millises suunas ma tahan minna?

930
00:55:41,430 --> 00:55:45,680
Noh, ma tahan minna vasakule, sest ilmselgelt, et õigus saab olema liiga suur.

931
00:55:45,680 --> 00:55:49,050
Nii märkate siin, sa oled omamoodi kontseptuaalselt tükeldamise puu pooleks

932
00:55:49,050 --> 00:55:51,700
sest sa oled kunagi alla paremas servas.

933
00:55:51,700 --> 00:55:55,410
Nii et nüüd ma lähen alates 55 kuni 33. See on liiga väike number.

934
00:55:55,410 --> 00:56:01,590
Otsin 44, kuid nüüd ma tean, et 44 on sellel puul, ma ei lähe ilmselt paremale.

935
00:56:01,590 --> 00:56:04,460
Nii et taas, ma olen pügamine puud pooleks.

936
00:56:04,460 --> 00:56:06,780
See on päris palju identne kontseptuaalselt kuuluv telefoniraamat.

937
00:56:06,780 --> 00:56:09,510
See on identne mida tegime paberid tahvel,

938
00:56:09,510 --> 00:56:13,940
aga see on keerukam struktuur, mis võimaldab meil tegelikult teha

939
00:56:13,940 --> 00:56:16,880
Selle jaga ja valitse, mille konstruktsioon on algoritm,

940
00:56:16,880 --> 00:56:19,420
ja tegelikult liiklevad struktuur niimoodi - Ups.

941
00:56:19,420 --> 00:56:22,870
Liikumine struktuur meeldib see, kus see on ainult "minna sel viisil või seda teed minna,"

942
00:56:22,870 --> 00:56:26,870
kaugeltki kõik, kood, painutatud meelt esimesel rakendamisel tuleks rubriigis

943
00:56:26,870 --> 00:56:31,270
või jalgsi läbi kodus, binaarne otsing, kasutades rekursiooni või iteratsiooni

944
00:56:31,270 --> 00:56:35,060
see on tüütu. Leia keset element, tehke oma ümardamine üles või alla.

945
00:56:35,060 --> 00:56:39,230
>> Seal on ilu, sest saame nüüd kasutada rekursiooni uuesti,

946
00:56:39,230 --> 00:56:43,760
aga palju puhtamalt. Tõepoolest, kui sa oled number 55 ja soovite leida 44,

947
00:56:43,760 --> 00:56:48,450
sa mine vasakule antud juhul siis mida sa teed? Sa jooksed täpselt sama algoritmi.

948
00:56:48,450 --> 00:56:51,560
Sa kontrolli väärtus sõlme, siis lähete vasakule või paremale.

949
00:56:51,560 --> 00:56:53,670
Siis kontrollida väärtust sõlme, mine vasakule või paremale.

950
00:56:53,670 --> 00:56:56,710
See sobib suurepäraselt rekursioon.

951
00:56:56,710 --> 00:57:00,920
Nii et kuigi varem oleme teinud mõned üsna meelevaldne näiteid erinevate rekursioon

952
00:57:00,920 --> 00:57:03,430
et ei pea olema rekursiivne, andmete STUCTURES,

953
00:57:03,430 --> 00:57:07,820
eriti puud, see on täiuslik käesoleva idee võtta probleemi,

954
00:57:07,820 --> 00:57:12,920
kahanemine ning seejärel lahendada sama tüüpi, kuid väiksem, programm.

955
00:57:12,920 --> 00:57:14,590
>> Nii et seal on teine ​​andmestruktuur, et saame tutvustada.

956
00:57:14,590 --> 00:57:18,760
See üks on mõeldud esmapilgul vaadata segasena, kuid see üks on hämmastav.

957
00:57:18,760 --> 00:57:25,090
Nii et see on andmestruktuur nimetatakse trie, trie, mis on päritud sõna leidmiseks,

958
00:57:25,090 --> 00:57:30,210
mis ei hääldata uuesti proovida-val, kuid see, mida maailm kutsub neid asju. Proovib. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
See on puu struktuuri mingisugune, kuid iga tippe trie

960
00:57:35,190 --> 00:57:41,280
tundub olevat mida? Ja see on natuke eksitav, sest see on selline lühendatud.

961
00:57:41,280 --> 00:57:45,960
Aga tundub iga sõlme see trie on tegelikult massiivi.

962
00:57:45,960 --> 00:57:48,840
Ja kuigi autor seda skeemi ei ole tõendanud seda,

963
00:57:48,840 --> 00:57:54,130
sel juhul see trie on andmestruktuur, mille eesmärk elus on salvestada sõnad

964
00:57:54,130 --> 00:57:57,330
nagu-l-i-c-e või B-o-b.

965
00:57:57,330 --> 00:58:02,480
Ja kuidas see info kauplustes Alice ja Bob ja Charlie ja Anita ja nii edasi

966
00:58:02,480 --> 00:58:06,970
on ta kasutab massiivi, mille salvestada Alice trie,

967
00:58:06,970 --> 00:58:09,820
alustame kell Juursõlme mis näeb välja nagu massiivi

968
00:58:09,820 --> 00:58:12,080
ja see on kirjutatud stenografisti märke.

969
00:58:12,080 --> 00:58:15,070
Autor jätta abcdefg sest puudusid nimed sellega.

970
00:58:15,070 --> 00:58:19,150
Nad näitasid ainult M ja P ja T, kuid sel juhul,

971
00:58:19,150 --> 00:58:22,780
liigume eemale Alice ja Bob ja Charlie, et mõned nimed, mis on siin.

972
00:58:22,780 --> 00:58:25,670
Maxwell on tegelikult selles diagramm.

973
00:58:25,670 --> 00:58:29,570
Kuidas siis autor poe M--x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Ta alustas keskmes sõlme, ja läks [M], nii umbes 13, 13 asukohta massiiv.

975
00:58:36,990 --> 00:58:40,750
Siis sealt, seal on osuti.

976
00:58:40,750 --> 00:58:42,760
Pointer viib teise massiivi.

977
00:58:42,760 --> 00:58:47,880
Sealt autor indekseeritud et reaga asukohta, mida on kujutatud seal üleval vasakul

978
00:58:47,880 --> 00:58:52,250
ja siis ta järgneb, et kursor teise massiivi,

979
00:58:52,250 --> 00:58:55,460
ja läks pointer asukoha X.

980
00:58:55,460 --> 00:58:59,840
Siis järgmise massiivi asukoha W, E, L, L, ja nii edasi,

981
00:58:59,840 --> 00:59:03,090
ja lõpuks, olgem tegelikult proovida panna pilt sellele.

982
00:59:03,090 --> 00:59:05,380
Mida tähendab sõlme välja nagu koodi?

983
00:59:05,380 --> 00:59:11,820
Sõlme trie sisaldab massiivi osuti rohkem tippe.

984
00:59:11,820 --> 00:59:16,090
Aga seal on ka ju olema mingi tõeväärtuse, vähemalt selle rakendamises.

985
00:59:16,090 --> 00:59:18,770
Satun nimetame seda is_word. Miks?

986
00:59:18,770 --> 00:59:22,670
Sest kui sa sisestamist Maxwell, sa ei sisestamist

987
00:59:22,670 --> 00:59:25,300
midagi sellele andmestruktuur.

988
00:59:25,300 --> 00:59:27,480
Sa ei kirjuta M. Sa ei kirjuta X.

989
00:59:27,480 --> 00:59:30,240
Kõik mida sa teed on pärast suunanäitajaks.

990
00:59:30,240 --> 00:59:33,360
Pointer, mis tähistab M, siis osuti, mis tähistab,

991
00:59:33,360 --> 00:59:36,310
siis osuti, mis tähistab X, siis W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
aga mida sa pead tegema, lõpus on omamoodi minna, vaadake, ma jõudnud sellesse asukohta.

993
00:59:41,950 --> 00:59:45,560
Seal oli sõna, mis lõpeb siin andmestruktuur.

994
00:59:45,560 --> 00:59:48,190
>> Mida trie on tõesti täis ja autor valis esindama

995
00:59:48,190 --> 00:59:51,880
Nende terminuses vähe kolmnurgad.

996
00:59:51,880 --> 00:59:56,470
See tähendab lihtsalt, et tegelikult on see kolmnurk on siin, see boolean väärtus tõene

997
00:59:56,470 --> 00:59:59,200
tähendab, et kui te lähete tagasi puus,

998
00:59:59,200 --> 01:00:02,420
mis tähendab sõna nimega Maxwell on selles.

999
01:00:02,420 --> 01:00:04,870
Aga sõna foo, näiteks

1000
01:00:04,870 --> 01:00:07,970
ei ole puu, sest kui ma alustan kell Juursõlme siin üleval,

1001
01:00:07,970 --> 01:00:14,030
Pole f kursor ei o pointer, ei o pointer. Foo ei ole nime see sõnastik.

1002
01:00:14,030 --> 01:00:22,460
Aga seevastu Turingi, t-U-R-i-n-g. Jällegi, ma ei salvestada t või u või r või i või n või g.

1003
01:00:22,460 --> 01:00:29,820
Aga ma tegin kaupluse andmete struktuur väärtus tõene siia alla selle sõlme - puus

1004
01:00:29,820 --> 01:00:33,030
seades selle tõeväärtuse kohta is_word true.

1005
01:00:33,030 --> 01:00:35,740
Nii trie on selline väga huvitav meta struktuur,

1006
01:00:35,740 --> 01:00:39,810
kus sa ei ole tõesti ladustamiseks sõnad ise seda tüüpi sõnaraamatut.

1007
01:00:39,810 --> 01:00:45,100
Et asi oleks selge, sa oled lihtsalt ladustamiseks jah või ei, seal on sõna, mis lõpeb siin.

1008
01:00:45,100 --> 01:00:46,430
>> Nüüd mis see tähendas?

1009
01:00:46,430 --> 01:00:51,120
Kui teil on 150.000 sõnu sõnastikku, et sa üritad salvestada mällu

1010
01:00:51,120 --> 01:00:53,400
kasutades midagi seotud nimekirja,

1011
01:00:53,400 --> 01:00:56,870
sa ei kavatse on 150000 tippe oma seotud nimekirja.

1012
01:00:56,870 --> 01:01:00,250
Ja leida üks neist sõnadest tähestiku järgi võiks O (n) ajaga.

1013
01:01:00,250 --> 01:01:04,370
Lineaarne aeg. Aga kui siin trie,

1014
01:01:04,370 --> 01:01:09,210
Mis sõiduaega leida sõna?

1015
01:01:09,210 --> 01:01:17,390
Selgub, ilu on selles, et isegi kui sul on 149999 sõnad juba selles sõnaraamat,

1016
01:01:17,390 --> 01:01:20,170
kui rakendatakse käesoleva andmete struktuuri,

1017
01:01:20,170 --> 01:01:25,560
kui palju aega läheb aega, et leida või lisada veel üks inimene sellesse, nagu Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Noh, see on ainult 5, ehk 6 samme, et lõpus on tühik.

1019
01:01:30,640 --> 01:01:32,880
Sest presense teiste nimede struktuuri

1020
01:01:32,880 --> 01:01:35,340
ei saa sel viisil sisestades Alice.

1021
01:01:35,340 --> 01:01:39,640
Lisaks leidis Alice kord on 150.000 sõnad selles sõnaraamat

1022
01:01:39,640 --> 01:01:41,960
ei saada oma teel leida Alice üldse

1023
01:01:41,960 --> 01:01:46,880
sest Alice on. . . . . siin, sest ma leidsin tõeväärtuse.

1024
01:01:46,880 --> 01:01:50,920
Ja kui ei ole tõeväärtus tõene, siis Alice ei ole selles andmestruktuur sõnu.

1025
01:01:50,920 --> 01:01:56,220
Teisisõnu, sõiduaega leida asju ja lisada asjad uude

1026
01:01:56,220 --> 01:02:01,920
andmete struktuuri trie on O - see ei ole n.

1027
01:02:01,920 --> 01:02:05,730
Sest presense 150.000 inimest ei mõjuta Alice tundub.

1028
01:02:05,730 --> 01:02:11,560
Nii et olgem kutsuvad seda k, kus k on maksimaalne pikkus sõna inglise keeles

1029
01:02:11,560 --> 01:02:14,050
mis on tavaliselt mitte rohkem kui 20-midagi tähemärki.

1030
01:02:14,050 --> 01:02:17,940
Nii et k on konstant. Nii et Püha Graal näib, et oleme leidnud nüüd

1031
01:02:17,940 --> 01:02:26,000
on see, et trie, pidev aega lisab, sest otsingud, kustutamiseks.

1032
01:02:26,000 --> 01:02:29,170
Kuna mitmed asjad juba struktuuris,

1033
01:02:29,170 --> 01:02:32,600
mis ei ole isegi füüsiliselt olemas. Jällegi, nad lihtsalt omamoodi kontrollitud maha, jah või ei,

1034
01:02:32,600 --> 01:02:35,050
ei mõjuta tema tulevasi sõiduaega.

1035
01:02:35,050 --> 01:02:37,940
>> Aga seal ju olema saagi, muidu me ei oleks raisata nii palju aega

1036
01:02:37,940 --> 01:02:41,460
kõigi nende teiste andmestruktuurid lihtsalt lõpuks ometi saladus üks, et on hämmastav.

1037
01:02:41,460 --> 01:02:46,410
Nii et mis hinnaga me pöörates seda saavutada ülevus siin? Space.

1038
01:02:46,410 --> 01:02:49,010
See asi on massiline. Ja põhjus, et autor

1039
01:02:49,010 --> 01:02:52,400
ei kujuta see siin, märkad, et kõik need asjad, mis näevad välja nagu massiivid,

1040
01:02:52,400 --> 01:02:55,400
ta ei tehta ülejäänud puud, ülejäänud trie,

1041
01:02:55,400 --> 01:02:58,060
sest nad lihtsalt ei puuduta lugu.

1042
01:02:58,060 --> 01:03:01,870
Aga kõik need sõlmed on super lai ja iga sõlme puu kulub

1043
01:03:01,870 --> 01:03:07,780
26 või tegelikult võiks olla 27 tähemärki, sest sel juhul ma ka ruumi ülakoma

1044
01:03:07,780 --> 01:03:09,980
nii et meil oleks apostrophized sõnu.

1045
01:03:09,980 --> 01:03:14,450
Sel juhul on need laia massiivid. Nii et kuigi nad ei picutured,

1046
01:03:14,450 --> 01:03:18,190
see võtab tohutu hulga RAM.

1047
01:03:18,190 --> 01:03:20,670
Milline võiks olla trahvi, especilly kaasaegse riistvara,

1048
01:03:20,670 --> 01:03:25,650
aga see on kompromiss. Me saame vähem aega veetes rohkem ruumi.

1049
01:03:25,650 --> 01:03:28,580
Nii et kui on see kõik läheb?

1050
01:03:28,580 --> 01:03:32,640
Noh, teeme ära - vaatame siin.

1051
01:03:32,640 --> 01:03:39,510
Teeme Hüppa see kutt siin.

1052
01:03:39,510 --> 01:03:43,450
>> Uskuge või mitte, sama palju rõõmu kui C on olnud juba mõnda aega,

1053
01:03:43,450 --> 01:03:48,130
me jõuda punktist semester, kus on aeg minna asju moodsam.

1054
01:03:48,130 --> 01:03:50,950
Asju kõrgemal tasemel. Ja kuigi järgmise paari nädala jooksul

1055
01:03:50,950 --> 01:03:54,580
me jätkuvalt kastke end maailma viiteid ja mälu haldamine

1056
01:03:54,580 --> 01:03:57,210
saada, et mugavus, millega saame siis toetuda,

1057
01:03:57,210 --> 01:04:01,270
aasta lõpus mäng on lõpuks tutvustada irooniliselt, mitte selles keeles.

1058
01:04:01,270 --> 01:04:03,330
Me kulutame, nagu 10 minutit räägime HTML.

1059
01:04:03,330 --> 01:04:05,950
Kõik HTML-is on märgistuskeel, ja mida märgistuskeel on

1060
01:04:05,950 --> 01:04:10,220
on need sarjad avatud sulgudes ja suletud sulgudes, et öelda "seda paksu"

1061
01:04:10,220 --> 01:04:12,000
"Seda kaldkirjas" "muuta see keskne."

1062
01:04:12,000 --> 01:04:14,250
See pole veel kõik, et intellektuaalselt huvitav, kuid see on super kasulik.

1063
01:04:14,250 --> 01:04:16,650
Ja see on kindlasti kõikjal nendel päevadel.

1064
01:04:16,650 --> 01:04:19,450
Aga mis on võimas umbes maailma HTML ja veebi programmeerimine üldisemalt

1065
01:04:19,450 --> 01:04:25,910
ehitab dünaamiline asju kirjalikult koodi keeltes nagu PHP või Python või Ruby või Java või C #.

1066
01:04:25,910 --> 01:04:30,360
Tõesti, sõltumata oma keele valik on, ja tekitavad HTML dünaamiliselt.

1067
01:04:30,360 --> 01:04:32,960
Luua midagi, mida nimetatakse CSS dünaamiliselt.

1068
01:04:32,960 --> 01:04:35,810
Kaskaadlaadistikke, mis on ka umbes esteetika.

1069
01:04:35,810 --> 01:04:41,360
Ja nii olgugi, täna, kui ma lähen teatud veebilehel nagu tuttav Google.com,

1070
01:04:41,360 --> 01:04:46,100
ja ma lähen, et näha, arendaja, et allikas, mis võib-olla olete teinud enne,

1071
01:04:46,100 --> 01:04:49,800
kuid läheb vaatamiseks allikas, seda kraami ilmselt tundub päris segasena.

1072
01:04:49,800 --> 01:04:55,320
Kuid see on aluseks koodi, mis rakendab Google.com.

1073
01:04:55,320 --> 01:04:57,940
Esiots. Ja tegelikult on see kõik kohev esteetika kraami.

1074
01:04:57,940 --> 01:05:01,740
See on CSS siin. Kui ma hoida kerimine alla lähme värvikoodiga asjad.

1075
01:05:01,740 --> 01:05:06,890
See on HTML. Google'i kood tundub jama, aga kui ma tegelikult avada erinevaid aknas

1076
01:05:06,890 --> 01:05:09,380
näeme mõningaid struktuur sellele.

1077
01:05:09,380 --> 01:05:12,640
Kui ma avada see üles, märkate siin, see on natuke paremini arusaadavaks.

1078
01:05:12,640 --> 01:05:16,850
Me näeme peagi seda tundnud, [sõna] on silt,

1079
01:05:16,850 --> 01:05:23,520
HTML, pea, keha, div, script, teksti ala, span, keskne, div.

1080
01:05:23,520 --> 01:05:26,770
Ja see on ka omamoodi segasena ilmega esmapilgul

1081
01:05:26,770 --> 01:05:30,890
kuid kõik see jama järgmiselt teatud mustrid ja korratav mustrid,

1082
01:05:30,890 --> 01:05:33,850
nii et kui saame põhitõdesid alla, on sul võimalik kirjutada koodi niimoodi

1083
01:05:33,850 --> 01:05:37,550
ja siis manipuleerida koodi niimoodi kasutades järjekordne keel, mida nimetatakse programmi JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Ja JavaScript on keel, mis töötab sees brauseri

1085
01:05:40,440 --> 01:05:44,380
täna, et me kasutame Harvardi kursused, kursus shopping vahend, et Google maps kasutab

1086
01:05:44,380 --> 01:05:48,660
teile terve hunnik dünaamikat, Facebook annab teile näidata instant staatus värskendusi,

1087
01:05:48,660 --> 01:05:51,430
Twitter kasutab seda näidata tweets koheselt.

1088
01:05:51,430 --> 01:05:53,820
Kõik see hakkame kastke end sisse

1089
01:05:53,820 --> 01:05:57,190
Aga sinna jõuda, peame mõistma vähe midagi internetist.

1090
01:05:57,190 --> 01:06:01,130
See klipp on siin just minut pikk, ja oletame nüüd on see tegelikult

1091
01:06:01,130 --> 01:06:08,380
kuidas Internet töötab teaser, mida on umbes tulla. Ma annan sulle "Warriors of the Net."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Aeglane koori muusika ♫]

1093
01:06:14,720 --> 01:06:20,450
[Mees jutustaja] Ta tuli sõnum.

1094
01:06:20,450 --> 01:06:23,770
Koos protokolliga kõik omal.

1095
01:06:23,770 --> 01:06:37,270
[♫ Kiirem elektroonilise muusika ♫]

1096
01:06:37,270 --> 01:06:41,330
Ta tuli maailma jahe tulemüürid, uncaring ruuterid,

1097
01:06:41,330 --> 01:06:45,690
ja ohtudest palju hullem kui surm.

1098
01:06:45,690 --> 01:06:55,400
Ta on kiire. Ta on tugev. Ta on TCP / IP, ja ta sai oma aadress.

1099
01:06:55,400 --> 01:06:59,250
Warriors of the Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Järgmisel nädalal siis. Interneti. Veebi programmeerimine. See on CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]